Главная > Моделирование, обработка сигналов > Быстрые алгоритмы в цифровой обработке изображений
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

Приложение 6.А.

Докажем теоремы 6.2 и 6.3. Нам нужна лемма.

Лемма Пусть и пусть для всех Если медиана и медиана где то или для каждого где или Далее, для всех для всех

Доказательство. Если медиана то среди отсчетов сегмента имеется, по крайней мере, отсчетов, исключая которые меньше или равны Аналогично среди отсчетов существуют, по крайней мере, отсчетов, отличных от которые будут больше или равны хт. Так как для всех и так как допускается, что мы имеем, по крайней мере, отсчетов, больших или равных .

и, по крайней отсчетов, меньших или равных в сегментах которые при объединении содержат только отсчетов. Поэтому среди отсчетов найдется точно отсчетов, меньших и равных отсчетов, больших и равных . Это доказывает первую часть леммы. Чтобы доказать ее вторую часть, достаточно заметить, что если существует где такое, что тогда, как вытекает из первой части леммы, исключая среди отсчетов имеется максимум отсчетов, которые больше и равны хт. Это противоречит допущению, что

Доказательство теоремы 6.2. Допустим, что сегмент который содержит отсчетов, является монотонно-возрастающим, т. е. в противном случае монотонен независимо от если

Если то сегмент который содержит отсчетов, монотонен и мы можем перейти к сегменту который также монотонен, и проверить Если то согласно лемме должно быть что противоречит допущению следовательно, должно быть Те же соображения можно высказать и относительно чтобы показать, что , следовательно, сегмент также монотонен. Доказательство завершается применением этих же рассуждений к

Доказательство теоремы 6.3. Предположим, что последовательность — стабильная точка и является Мы исследуем все возможности изменения состояния последовательности, скажем, в начале. Без потери общности допустим, что: Тогда по лемме имеем: или для каждого где или

Кроме того, имеем: 3)

Рассмотрим следующий случай: для всех —0. Пусть будет наименьшим целым, удовлетворяющим условию

Есла такого не существует, то должно выполняться -Если такое существует, то согласно лемме и допущению имеем, что для всех на самом деле так как — наименьшее число, удовлетворяющее Поэтому сегмент монотонен на длине это нарушает условие — есть Отсюда следует, что: а) в сегменте существует, по крайней мере, один отсчет, который меньше или равен и аналогично, б) в существует, по крайней мере, один отсчет, который больше или равен

Достаточно рассмотреть только 4а);

5) существует такое, что Если существует такое что то пусть будет наибольшим целым, таким, что Кроме того, пусть будет наименьшим, таким, что Очевидно, по 2). По лемме имеем или для каждоге Так то «ли или Это противоречит нашим допущениям. Отсюда вытекает, что: а) если где — и по аналогии, б) если где

Теперь рассмотрим: 6) пусть будет наибольшим целым, таким, что

По 2) и 5а) имеем, что Пусть будет наименьшим целым, таким, что Тогда По лемме имеем или для каждого Рассмотрим две возможности:

а) если то вышесказанное означает, что или ни то, ни другое не верно; б) если то имеем или для каждого по 46) и 56) должен существовать, по крайней мере, один отсчет такой, что что противоречит сделанному выше выводу.

Отсюда следует, что такое не существует или, что то же самое, или для каждого По аналогии, сказанное также справедливо для всех отсчетов По 4а) в сегменте существует, по крайней мере, один перепад и, аналогично, по 46) — один перепад в сегменте Доказательство завершается применением этих же рассуждений к перепадам в двух упомянутых сегментах вне их.

<< Предыдущий параграф Следующий параграф >>
Оглавление