11.3. СВЕРТКА С ИСПОЛЬЗОВАНИЕМ БПФ

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

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

.                    (11.3.1)

2. Записать матрицу исходного изображения в верхнем левом углу нулевой матрицы -го порядка и выполнить двумерное преобразование Фурье расширенной матрицы исходного изображения

.                      (11.3.2)

3. Выполнить скалярное умножение

,                (11.3.3)

где  и .

4. Произвести обратное преобразование Фурье

.                  (11.3.4)

5. После выбора нужных элементов сформировать искомую выходную матрицу

                (11.3.5а)

или

.               (11.3.5б)

Важно, чтобы порядок  расширенных матриц  и  удовлетворял соответствующим неравенствам. При  на левом и верхнем краях выходной матрицы будут находиться полосы ошибочных элементов, имеющие ширину в  отсчет (рис. 11.3.1,а,б). Они образуются в результате так называемой циклической ошибки, связанной с неправильным применением метода БПФ для вычисления свертки. Кроме того, при выполнении свертки конечных массивов (-свертка) будут потеряны элементы выходного массива, расположенные полосами в правой и нижней его частях. Если положить , то при -свертке выходная матрица будет полностью заполнена правильными отсчетами. Чтобы вычислить -свертку при , необходимо отсечь правый и нижний края исходной матрицы. Однако в результате получится, что элементы выходного массива, расположенные сверху и по левому краю, будут ошибочными.

Рис. 11.3.1. Циклические ошибки. (Нижняя и правая стороны матрицы  отсечены.)

а - фильтрация типа ; .

б - фильтрация типа ; .

в - фильтрация типа ; .

г - фильтрация типа ; .

При обработке сигналов во многих случаях оказывается, что на различные входные массивы воздействуют операторы с одним и тем же импульсным откликом и, следовательно, первый этап алгоритма (вычисление ) достаточно выполнить только один раз. При использовании алгоритма БПФ для случаев прямого и обратного преобразований требуется выполнить примерно по  арифметических операций. Скалярное умножение проводится за  операций, т. е. всего требуется  операций. Если входная матрица содержит  элементов, выходная , а матрица импульсного отклика  элементов, то для вычисления конечной свертки требуется  операций, а для дискретизованной свертки  операций. Если размер  матрицы импульсного отклика достаточно велик по сравнению с размером  исходной матрицы, то свертка с преобразованием оказывается эффективнее прямой свертки, причем число операций может уменьшиться раз в десять или более. На рис. 11.3.2 приведен график зависимости  от  для случая, когда оба метода вычисления свертки конечных массивов (прямой и с преобразованием Фурье) имеют одинаковую эффективность. Зубчатость графика объясняется тем, что с ростом  параметр  изменяется скачкообразно, принимая значения 64, 128, 256 и т. д.

Рис. 11.3.2. Сравнение эффективности двух методов получения конечной свертки: прямого и с преобразованием Фурье.

Для вычисления свертки с преобразованием Фурье требуется меньшее число операций, чем в случае ее прямого вычисления, если длина импульсного отклика достаточно велика. Однако если обрабатываемое изображение также имеет большие размеры, то относительная эффективность метода с использованием преобразования Фурье понижается. Кроме того, при вычислении преобразования Фурье больших матриц возникают трудности, связанные с обеспечением точности расчетов. Обе проблемы удается разрешить, прибегая к блочной фильтрации изображения, когда большую матрицу подразделяют на ряд перекрывающихся блоков, обрабатываемых поочередно [2, 7-9].

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

Рис. 11.3.3. Размещение блоков при блочной фильтрации изображения.

а - первый блок; б - вторые блоки в строке и столбце блоков.

Для получения свертки с помощью преобразования Фурье требуется

                     (11.3.6)

операций. При блочной обработке, когда размер блоков равен , необходимо

                      (11.3.7)

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