§ 48. Преобразования

В данном параграфе мы остановимся на реализации алгоритма БПФ (см. § 12). Изложенное будет также в некоторой степени относиться и к другим алгоритмам, таким, как преобразование Хаара и преобразование Адамара (или Уолша). Отметим, однако, что теорема свертки (см. § 7) справедлива только для БПФ и в этом его колоссальное преимущество. Преобразования Хаара и Адамара в основном используются при кодировании изображений, Нас интересует БПФ вещественных изображений, размеры которых по координатам равны степеням двойки. Эти ограничения, накладываемые на размер изображения, не очень существенны на практике. Например, в случае восстановления изображения изображение, которое является полной, т. е. неусеченной, сверткой (см. § 15), может быть расширено добавлением нулей (см. § 12) так, чтобы его протяженность в каждом направлении была равна степени двойки. В более общем случае усечения свертка может быть приведена к размерам, равным степеням двойки, с помощью подпрограммы интерполяции (см. § 45). После восстановления, очевидно, необходимо произвести обратный пересчет. Мы установили, что эта операция лишь несущественно снижает точность восстановления, если вносимый при этом шум квантования значительно ниже начального уровня шумов. Можно и написать программу, реализующую алгоритм БПФ для изображений с размерами, не равными степени двойки, но, как показано выше, в этом нет необходимости.

Существует много хороших программ и подпрограмм реализации алгоритма БПФ. Наилучшим источником такого программного обеспечения и документации по нему является Комитет по обработке цифровых сигналов Института инженеров по электротехнике и радиоэлектронике США. Существуют подпрограммы, реализующие двумерное БПФ полностью в ЗУПВ или двумерное БПФ большого изображения, записанного в НМД. Мы используем для выполнения прямого и обратного БПФ больших изображений, записанных в НМД в нашем стандартном формате, очень эффективные подпрограммы Фрэзера. БПФ вещественного изображения размером занимает столько же места в как и исходное изображение, и уплотняется (как описывается ниже), пока не уложится в массив комплексных чисел. В качестве стандартного мы приняли способ упаковки Фрэзера. Заметим, что результат БПФ массива вещественных чисел содержит комплексных чисел. Но в силу симметрии сопряженных значений относительно нулевой частоты строк оказываются избыточными, поскольку у них есть соответствующие комплексные сопряженные строки, а такие строки обладают внутренней симметрией комплексного сопряжения. Такие две строки могут быть объединены в одну, и тогда полученное изображение будет содержать комплексных чисел и уже не будет избыточным. В случае программ общего назначения, рассчитанных на комплексные данные, такой уплотненный формат нежелателен, поскольку его использование приводит к тому, что программы значительно усложняются и становятся эксплуатационно неудобными. Дело в том, что всякая программа, составленная для комплексных изображений, должна оперировать с упакованными строками как с исключениями, поскольку их формат не стандартен для комплексных данных. По этой причине мы используем отдельную программу, которая выполняет переход к стандартному неупакованному двумерному комплексному изображению, содержащему комплексных элементов изображения.

Если через обозначить -й элемент изображения размером а через отсчет его БПФ, то

при Выражение, обратное выражению (48.1), имеет вид

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

Укажем еще одну программу, используемую в сочетании с БПФ. Она преобразует комплексное изображение в 8-разрядное изображение, причем позволяет выбирать значения логарифма либо модуля, либо положительной вещественной или мнимой части результата БПФ. Каждое из этих изображений нормируется по амплитуде на значение в максимуме, равное 255. Логарифм положительной вещественной части особенно нужен при анализе искаженного изображения с целью идентификации ФРТ, имеющей простую форму, например отвечающую линейному смазу или геометрической дефокусировке. Точки перемены знака спектра в БПФ легко обнаруживаются по разрывам непрерывности логарифма. Когда такие точки разрыва располагаются на достаточно простых линиях в плоскости Фурье, например, на прямых окружностях или даже неправильных овалах, — они часто соответствуют вещественным нулям ОПФ (комплексные нули ОПФ при такой элементарной обработке определить, конечно, невозможно). Это относится к методам, которые будут рассмотрены в 52.