4.2. ИТЕРАЦИОННЫЕ АЛГОРИТМЫ С ОГРАНИЧЕНИЯМИ

Обратимся к разложению обратного оператора в ряд Неймана (4.5):

Запишем выражение для члена ряда

Тогда для члена ряда получим

С учетом (4.15) итерационная схема разложения решения в ряд Неймана приобретает следующий вид:

На каждой последующей итерации здесь необходимо иметь только предыдущее значение

Выражение (4.16) позволяет использовать ограничения, накладываемые на решение Рассмотрим уравнение формирования изображения и видоизменим его с учетом некоторого оператора ограничений [68]:

Оператор ограничений будем определять следующим образом. Действие оператора на функцию тождественно тогда и только тогда, когда удовлетворяет ограничению

Иначе говоря, оператор можно рассматривать как оператор проекции функции на множество допустимых функций, ограниченных условием Оставляя пока в стороне вопрос о сходимости итерационного процесса, ряд (4.16) с учетом (4.17) и (4.18) может быть записан следующим образом:

Выражение (4.19) является основой всех итерационных алгоритмов с ограничениями. Обсудим смысл класса алгоритмов, описываемых (4.19). Итерационное решение задачи с ограничениями аппроксимирует обратный оператор

Решение (4.20), как правило, трудно выразить аналитически вследствие нелинейности оператора ограничения. Но запись итерационного процесса в форме (4.19) позволяет обойти сложное аналитическое решение (4.20), так как обратный оператор получается просто многократным применением прямого оператора. Физический смысл (4.19) чрезвычайно прост: мы требуем, чтобы на каждом шаге решение удовлетворило наложенным ограничениям и, разбивая последовательность приближений на большое число шагов, удерживаем его в рамках ограничений.

Рассмотрим один из наиболее важных операторов ограничений: оператор ограничения на неотрицательность решения Определим его следующим образом:

Этот оператор проецирует известную функцию на множество неотрицательных функций, приравнивая нулю все отрицательные участки. Итерации принимают вид

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

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

Обсудим влияние этих ограничений на качество решения. При этом необходимо различать три основных случая. В первом из них сигнал изображения имеет широкий динамический диапазон и при восстановлении возникают отрицательные выбросы. Для таких изображений ограничение на неотрицательность или на область допустимых значений играет решающее значение. Те же соображения относятся и к импульсным объектам, характерным для задач спектроскопии или астрономии. Эти объекты мы относим ко второму случаю. Третий случай возникает, когда объект нельзя разбить только на постоянную и импульсную составляющие. Такая ситуация характерна для большинства изображений протяженных объектов (см. изображения на рис. 2.6,а-о и кривые на рис. 2.7,а-о). Для таких изображений ограничение вида как правило, не играет существенной роли и приводит лишь к незначительному улучшению их качества, а решение задачи с ограничениями мало отличается от решения задачи без ограничений. Для того чтобы эффективно использовать ограничения, в этом случае необходимо учесть в восстанавливающем алгоритме информацию о фоновой составляющей изображения. Иначе говоря, возникает задача выделения в искаженном изображении тех участков, которые не подверглись искажению и, следовательно, могут быть приняты за оценку гладких областей в восстановленном изображении. Смысл такого ограничения очевиден: если значительные участки сигнала являются достаточно гладкими, то априорное знание этих участков не позволяет возникнуть осцилляциям решения. Более того, если удается выделить области пространства, в которых имеются импульсные объекты, то такое ограничение становится похожим на ограничение на пространственную протяженность функции, обобщенное на случай протяженных объектов.

Для решения поставленной задачи существует ряд приемов. В [84, 95] предлагается находить свертку искаженного изображения с гауссовским ядром, имеющим

характерный размер, в несколько раз превышающий характерный размер весовой функции системы формирования. При такой операции фоновые участки останутся мало искаженными, а участки, содержащие более высокочастотные компоненты, значительно размажутся. Другим вариантом, предлагаемым в [84], является медианная оценка фона.

В наших экспериментах наилучшие результаты дал другой алгоритм, основанный на введении ограничения вида где и -функции, ограничивающие значения решения. Оператор ограничения выглядит в этом случае следующим образом:

Для нахождения можно применять следующий алгоритм. Вначале ищется оценка получаемая из при помощи линейной фильтрации при достаточно большом параметре а. Требованием к оценке является почти полное отсутствие осцилляций решения. Затем искаженное изображение и оценка приводятся к одной постоянной составляющей и одному коэффициенту усиления и сравниваются. Вводится некоторый порог такой, что если то считается, что является хорошей оценкой фона, а если то принимается решение о наличии высокочастотных компонент в решении. Выбор величины производится исходя из уровня шума в искаженном изображении: Во всех участках координаты в которых задаются функции где константа, выбираемая из условия Величина берется исходя из допустимого отклонения действительного фона от его сглаженной оценки. Если то ограничения на фон снимаются и задается, например, Более качественные результаты дает алгоритм, который учитывает знак отклонения от Так, если то нижней оценкой решения понимается некоторая кривая, соединяющая значения на границах участка Аналогично (4.21) формируются ограничения на пространственную и спектральную протяженность: если известно, что отлична от нуля в промежутке то соответствующий оператор равен

Если известно, что спектр изображения ограничен частотой то оператор ограничения в спектральной области записывается как

Переводя его в пространственную область, получим

Некоторые другие ограничения будут рассмотрены в § 4.3. Здесь же отметим, что метод проектирующих операторов является менее общим, чем метод нелинейного программирования с ограничениями (см. § 3.4). Так, ограничения вида суммарной яркости или интенсивности изображения и шума в рассмотренной итерационной схеме учесть нельзя.

Разложение обратного оператора задачи в ряд Неймана является в действительности частным приемом итерационного решения обратных задач. Более общая схема такого рода может быть получена на основе решения нелинейного операторного уравнения [68] Итерационное решение записывается следующим образом:

Рассмотрим, каким образом можно получить итерационную схему из основного интегрального уравнения в операторной форме. Запишем тождество

Ясно, что его можно рассматривать как результат применения некоторого оператора :

Отсюда находим

В выражении (4.26а) X — некоторый параметр, который управляет сходимостью процесса. Нетрудно видеть, что если в (4.26а) положить X равным единице, то автоматически приходим к ряду Неймана вида (4.16), Так как ряд Неймана сходится только при положительно определенном самосопряженном операторе то разработаны методы для обеспечения сходимости разложения (4.16) в более общем случае. При этом вместо уравнения рассматривается

эквивалентное уравнение Тогда получим следующий итерационный процесс:

В дальнейшем будем предполагать, что — самосопряженный положительно определенный оператор. Это требование эквивалентно тому, что частотная характеристика действительная и . В противном случае необходимо пользоваться формулой (4.26б).

Нетрудно провести то же логическое построение и для решения задачи с ограничениями. Пусть тогда

и соответственно получим

Таким образом, и (4.26а) и (4.26в) при являются аналогами разложения обратного оператора задачи в ряд Неймана. Замечательным свойством итерационных алгоритмов является существование строгих математических результатов, позволяющих в определенных случаях гарантировать сходимость итерационных схем.

Будем рассматривать изображения как элементы пространства Обратимся к уравнению Оператор будем называть оператором сжатия или просто сжатием, если выполнено условие

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

Если выполнено (4.27), то выполняется и следующее соотношение:

которое определяет скорость сходимости итерационного процесса. Применительно к (4.26) условием сходимости будет

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

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

Согласно (4.26) для решения этого уравнения получим итерационную схему:

Отметим, что при эта схема полностью совпадает с итерационным алгоритмом Бургера — Ван Циттерта (4.8), (4.9).

Рассмотрим вопрос о сходимости процесса (4.29). Поскольку оператор в нашем случае выглядит как то для расстояния между изображениями получим

Обозначим Заменим на его максимальное значение

и находим

Таким образом, для сходимости процесса (4.29) требуется, чтобы оператор являлся сжатием, т. е. чтобы выполнялось условие

Если то это условие совпадает с условием сходимости ряда Неймана. В более общем случае величина К выбирается

из соображений выполнения (4.30). Так, если , то X должно быть выбрано из условия

Если или то условия сходимости (4.26а) нарушаются и применяют следующую итерационную схему:

При этом X выбирается из условия

Отметим важную особенность условия (4.30). Если положить при и попытаться экстраполировать полосу пространственных частот, то получим

Это означает, что в точках за пределами интервала -сое, оператор уже не является сжатием и, следовательно, сходимость процесса нарушается. Этот факт демонстрирует невозможность экстраполяции спектра при помощи линейного алгоритма.

Теперь представим себе, что требуется учесть некоторый оператор ограничений так что во всех действиях надо заменить на Вместо выражения (4.30) получим

Пусть оператор ограничения удовлетворяет условиям

Тогда имеем

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

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

Рассмотрим используемые на практике ограничения и исследуем вопросы сходимости. В случае ограничения на неотрицательность (4.21) итерационный алгоритм может быть представлен в виде

Нас интересует уклонение в метрике

Рассматривая случаи возможной отрицательности и неотрицательности функций можно показать, что всегда

Таким образом,

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

Можно также показать, что в случае ограничения на пространственную протяженность (4.24) выполняется условие

где

При этом и если обе функции удовлетворяют оператору ограничений .

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

который иногда называют алгоритмом Папулиса [136].

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

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