11. Алгебраические алгоритмы реконструкции изображений

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

Алгебраические алгоритмы реконструкции образуют большую группу алгоритмов реконструкции. Их название исторически сложилось абсолютно случайно: в них нет чего-либо более «алгебраического», чем в методе, который мы рассмотрим в следующей главе. Характерные особенности алгебраических алгоритмов реконструкции требуют тщательного анализа, который производится ниже.

11.1. ЧТО ТАКОЕ АЛГЕБРАИЧЕСКИЙ АЛГОРИТМ РЕКОНСТРУКЦИИ?

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

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

Величины в алгебраических алгоритмах получают из анализируя одно из -приближенных равенств [формула (6.23)]. На практике упомянутые равенства используют в циклической последовательности. Обозначим через величину т.е. через -мерный вектор-столбец -компонента которого равна Другими словами, представляет собой транспонированную строку

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

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

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

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

где угловые скобки обозначают скалярное произведение двух -мерных векторов, т.е.

Заметим, что в данном случае одна и та же для всех k.

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

т.е. приближенное равенство становится точным после шага итерации, что следует из соотношений (11.1) — (11.3). Правую часть выражения (11.4) можно записать в следующем виде:

что и утверждается в (11.4).

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

Рассмотрим, например, случай, когда базисные изображения являются изображениями, полученными при дискретизации [формула (6.17)]. При этом величина есть просто длина пересечения луча с элизом. Этот вывод имеет два следствия. Во-первых, большинство компонент вектора равно нулю. При разбиении изображения на элизов самое большее элизов может иметь пересечения с прямой линией. Таким образом, из компонент вектора только не более компонент (а обычно только порядка имеют ненулевые значения. Во-вторых, положение и величина ненулевых компонент легко можно определить, исходя из относительного геометрического расположения луча относительно -сетки. Таким образом, нет необходимости запоминать в ЭВМ всю проекционную матрицу За один цикл вычислений необходимо иметь лишь одну строку этой матрицы, всю информацию с которой легко рассчитать.

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

Предположим, что имеется набор чисел таких, что если только не является одним из этих чисел. Тогда вычисление по формуле (11.3) потребует только операций умножения, причем Аналогично величину можно рассчитать за V операций умножения. Имея вычисленное значение выполненное с помощью операций умножения и одной операции деления, обновление значений может производиться также путем последующих операций умножения. Это происходит потому, что необходимо изменить только те значения для которых при некотором и а изменение требует дополнительного умножения на фиксированную величину

Можно видеть [формула (11.2)], что отдельные шаги вычислений достаточно просты для эффективной реализации на ЭВМ.

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

а) только те элизы, которые пересекаются лучом, должны иметь измененные значения плотности;

б) изменение значения плотности в элизе должно быть пропорциональным разности т.е. «ошибке» в приближенном равенстве перед итерацией;

в) изменение в элизе должно быть пропорционально величине вектора .

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

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

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

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