4.1.2. Рекурсивная вычислимость

Выражение (4.4), определяющее способ вычисления отсчета  можно переписать следующим образом:

.   (4.5)

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

Рис. 4.1. Использование входной и выходной масок для вычисления последовательных отсчетов на выходе рекурсивного фильтра.

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

Простейшим примером двумерной выходной маски, позволяющей провести рекурсивное вычисление выходные данных, является фильтр первого квадранта, или «каузальный» фильтр. В этом случае коэффициенты  имеют ненулевые значения в конечной области . Форма выходной маски представлена на рис. 4.2. Если значения выходного массива даны как граничные условия в области, имеющей форму буквы , обозначенной на рисунке светлыми кружками, выходная маска может перемещаться вверх столбец за столбцом, позволяя вычислить оставшиеся члены выходного массива и никогда не перекрывая ни одного неизвестного значения. Однако для этой маски такой путь не является единственным возможным способом упорядочивания. Мы можем также вычислять выходные отсчеты строка за строкой слева направо, начиная с нижних строк и двигаясь наверх. Кроме того, выходной массив можно сканировать также по диагонали. В общем случае эта маска скользит вдоль любого семейства параллельных прямых, при условии, что они имеют отрицательный наклон, как показано на рис. 4.3.

Рис. 4.2. Выходная маска, соответствующая рекурсивно вычислимому фильтру первого квадранта. Темными кружками отмечены выходные отсчеты, которые уже вычислены; светлыми кружками отмечены начальные условия, а точками - отсчеты, которые предстоит вычислить. Выходная маска имеет размеры  точек.

Рис. 4.3. Допустимые направления рекурсии для выходной маски первого квадранта (показана темными кружками). Сплошными линиями указаны допустимые направления, штриховыми - недопустимые.

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

На рис. 4.4 изображены две маски, не допускающие рекурсивное вычисление. Как и маска на рис. 4.2, эти маски имеют прямоугольную форму, но отверстие в обоих случаях расположено не в углу маски. Для маски с отверстием в середине начальные условия или предварительно вычисленные выходные отсчеты должны полностью заполнять пространство маски вокруг вычисляемой точки. Таким образом рекурсия не может самоподдерживаться. Аналогичная ситуация возникает, когда отверстие находится на границе маски. В этом случае рекурсия возможна вдоль строки или столбца, но невозможен переход от строки к строке или со столбца на столбец.

Рис. 4.4. Два примера выходных масок, не являющихся рекурсивно вычислимыми.

а - маска с отверстием в центре; б - маска с отверстием на краю (но не в углу).

Маска с отверстием в угловой точке и расположенная в одном квадрате не является, однако, единственной, соответствующей рекурсивно вычислимой системе. Рассмотрим маску, показанную на рис. 4.5 для несимметричного полуплоскостного фильтра [1,2]. Этот фильтр имеет импульсный отклик, простирающийся на сектор плоскости , имеющий угол меньше 180°. Точное значение угла сектора зависит от размеров маски. Естественное упорядочение для вычисления выходных отсчетов с этой маской состоит в перемещении вдоль каждой строки слева направо, начиная со строки, находящейся непосредственно над начальными условиями, и в повторении этой процедуры вверх строка за строкой.

Рис. 4.5. Допустимые направления рекурсии для несимметричной полуплоскостной выходной маски (показана темными кружками). Как и на рис. 4.3, сплошные линии соответствуют допустимым направлениям, штриховые - недопустимым.

Однако возможны и другие направления перемещения, как показано на рис. 4.5. Начальные условия, необходимые для этого конкретного несимметричного полуплоскостного фильтра (НПП-фильтра), приведены на рис. 4.6. Заметим, что форма зоны начальных условий зависит от порядка фильтра. НПП-фильтры можно обобщить с помощью отражения или вращения выходной маски, а также комбинации этих операций.

Рис. 4.6. Выходная маска, соответствующая рекурсивно вычислимому НПП-фильтру. Светлыми кружками отмечен допустимый набор начальных значений.

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

; .                  (4.6)

Это преобразование приводит к маске одного квадранта, показанной на рис. 4.7.

Рис. 4.7. Выходная маска, приводимая на рис. 4.5 и 4.6 и отображенная на первый квадрант (или маска одной четверти плоскости).

Светлые кружки соответствуют ненулевым коэффициентам, точки - нулевым коэффициентам, а крестики - выходным отсчетам, подлежащим вычислению. Начальные условия рис. 4.6 отображаются в заштрихованную область в форме буквы , заключенную между осями координат и штриховыми линиями.