11.3. АДДИТИВНЫЙ АЛГЕБРАИЧЕСКИЙ АЛГОРИТМ РЕКОНСТРУКЦИИ

В данном разделе будут рассмотрены вопросы применения релаксационных методов к реконструкции изображения. Указанные методы называют аддитивными алгебраическими алгоритмами реконструкции, поскольку в процессе единственной итерации текущая оценка обновляется путем добавления к ней скалярной величины, кратной транспонированной строке матрицы проекций [соотношения (11.1) и (11.2)].

Наиболее простая реализация алгоритма предполагает использование релаксационного метода решения системы уравнений, описываемого выражениями (11.22) и (11.23) при Основываясь на результатах, полученных в предыдущем разделе, мы получаем последовательность векторов которые сходятся к величине оценки так что при условии что она существует. Проблема состоит в том, что из-за существующего соотношения между вектором изображения и вектором измеренных данных у [выражение (6.24)] оценка может не существовать, а даже если такая и существует, то не пригодна для реконструкции в дискретном варианте. С этой точки зрения вызывает приятное удивление тот факт, что даже такой простой подход дает приемлемое качество реконструкции, особенно в тех случаях, когда параметр релаксации выбран достаточно малым (например, 0,05), что иллюстрируется примерами разд. 11.5.

Один из способов применить теорию, полученную в предыдущем разделе, к решению проблемы реконструкции изображений состоит в использовании методов решения системы неравенств [выражение (6.42)]. Большое число исследований было проведено именно в этом направлении; в частности, были разработаны близкие к алгебраическим алгоритмам реконструкции процедуры нахождения решения системы неравенств с минимальной нормой. Указанные процедуры требуют более сложного математического описания, чем то, что было дано в рамках соотношения (11.1). В дополнение к последовательности -мерных векторов в этом случае получают и используют последовательность -мерных векторов

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

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

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

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

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

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

является совместной, поскольку, рассматривая произвольный -мерный вектор и полагая

делаем вывод, что решение II удовлетворяет системе (11.27).

Причина введения системы уравнений (11.27) состоит в том, что если векторы, для которых I I является решением системы уравнений (11.27) с минимальной нормой, и если также

то вектор минимизирует величину (11.26).

Для проверки этого утверждения рассмотрим произвольный -мерный

вектор Пусть

а определяется согласно соотношению (11.28), тогда

Отсюда следует, что

поскольку решение системы (11.27) с минимальной нормой.

Учитывая, что удовлетворяют уравнениям (11.27) и (11.29), получаем

что в сочетании с выражениями (11.29) и (11.32) приводит к неравенству вида

Поскольку произвольный -мерный вектор, то из этого следует, что минимизирует (11.26).

Из приведенного анализа следует также, что любой метод, позволяющий получать решение системы (11.27) с минимальной нормой, автоматически дает нам вектор, минимизирующий значение (11.26). Одним из способов нахождения решения с минимальной нормой совместной системы уравнений является релаксационный метод решения уравнений. Заметим, что, применяя итерацию (11.22) к системе уравнений (11.27), получим

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

Отметим также, что если определено выражением (11.24), то нулевой вектор содержится в Следовательно, единственным способом, обеспечивающим сходимость к решению с минимальной нормой системы (11.27) [в рамках релаксационного метода решения системы уравнений в сочетании с процедурой итерации, аналогичной используемой в (11.35)], является выбор в качестве нулевых векторов соответствующей размерности.

Для всех значений к положим

Если последовательность сходится к то последовательность сходится к величине определяемой условием (11.29) и минимизирующей значение (11.26).

На практике нет необходимости вводить в алгоритм вычислений величины Используя выражения также условие, что нулевые векторы, можно получить иной алгоритм. Последовательность оценок получается при их сходимости к байесовской оценке [при условии что параметры релаксации удовлетворяют соотношению (11.10)], т.е.

где

Заметим, что указанный алгоритм нельзя получить в рамках соотношения (11.1), однако его применение гораздо сложнее, чем метод описываемый выражением (11.2), поскольку в первом из них требуется дополнительное определение последовательности -мерных векторов и. На итерации требуется использовать или заменить лишь один элемент последовательности а именно ее элемент. Поскольку индекс определяется круговой перестановкой ( и т.д.), компоненты вектора можно занести во вспомогательный блок памяти ЭВМ с последовательной адресацией (доступом) и вводить в основную память ЭВМ один за другим (или по несколько значений за один раз), когда это потребуется. Аналогичные замечания относятся и к элементам вектора измерений у. Как уже отмечалось в разд. 11.1, в наших приложениях значения обычно полностью не запоминаются, а положение и величины ненулевых элементов гц вычисляются по мере необходимости. Следовательно, алгоритм, описываемый соотношениями (11.38) и (11.39), так же как и простой алгебраический алгоритм реконструкции, рассмотренный в разд. 11.1, обладает высокой эффективностью по использованию объема памяти. Легко показать, что близки и вычислительные характеристики этих алгоритмов.

Алгоритм, описываемый соотношениями (11.38) и (11.39), является типичным примером аддитивного алгебраического алгоритма реконструкции. Оставляя подробное рассмотрение этого алгоритма до следующего раздела,

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

где [выражение (6.40)], так что

где в свою очередь

а означает среднее значение (медиану) трех величин .

Алгоритм, описываемый выражениями (11.41) и (11.42), в литературе получил название ART-4 и отличается от других модификаций алгебраических алгоритмов, имеющих другие особенности сходимости.