4.1.2. Рекурсивная вычислимостьВыражение (4.4), определяющее способ вычисления отсчета
Графическая интерпретация этого выражения приведена на рис. 4.1. Входная маска, или окно конечной площади, форма которой определена массивом Рис. 4.1. Использование входной и выходной масок для вычисления последовательных отсчетов на выходе рекурсивного фильтра. Для вычисления значения конкретного выходного отсчета, выходная маска должна накрывать только известные значения отсчетов (конечно, за исключением отсчета, отмеченного кружком). Это означает, что определенные отсчеты следует вычислять ранее других. Если не существует способа упорядочивания, позволяющего последовательно вычислить выходные данные по набору начальных условий, система не является рекурсивно вычислимой. Если существует несколько различных способов упорядочивания, у нас появляется выбор; некоторые из этих способов упорядочивания могут оказаться лучше других. Количество возможных способов упорядочивания зависит как от формы выходной маски, так и от положения выходного отсчета в этой маске. Простейшим примером двумерной выходной маски, позволяющей провести рекурсивное вычисление выходные данных, является фильтр первого квадранта, или «каузальный» фильтр. В этом случае коэффициенты Рис. 4.2. Выходная маска, соответствующая рекурсивно вычислимому фильтру первого квадранта. Темными кружками отмечены выходные отсчеты, которые уже вычислены; светлыми кружками отмечены начальные условия, а точками - отсчеты, которые предстоит вычислить. Выходная маска имеет размеры Рис. 4.3. Допустимые направления рекурсии для выходной маски первого квадранта (показана темными кружками). Сплошными линиями указаны допустимые направления, штриховыми - недопустимые. Важно понять, что выходные сигналы, вычисленные для любого из этих направлений перемещения, идентичны. При этом для вычисления одних и тех же выходных отсчетов выполняются одни и те же арифметические операции; с изменением направления перемещения меняется только порядок вычисления выходных значений. На рис. 4.4 изображены две маски, не допускающие рекурсивное вычисление. Как и маска на рис. 4.2, эти маски имеют прямоугольную форму, но отверстие в обоих случаях расположено не в углу маски. Для маски с отверстием в середине начальные условия или предварительно вычисленные выходные отсчеты должны полностью заполнять пространство маски вокруг вычисляемой точки. Таким образом рекурсия не может самоподдерживаться. Аналогичная ситуация возникает, когда отверстие находится на границе маски. В этом случае рекурсия возможна вдоль строки или столбца, но невозможен переход от строки к строке или со столбца на столбец. Рис. 4.4. Два примера выходных масок, не являющихся рекурсивно вычислимыми. а - маска с отверстием в центре; б - маска с отверстием на краю (но не в углу). Маска с отверстием в угловой точке и расположенная в одном квадрате не является, однако, единственной, соответствующей рекурсивно вычислимой системе. Рассмотрим маску, показанную на рис. 4.5 для несимметричного полуплоскостного фильтра [1,2]. Этот фильтр имеет импульсный отклик, простирающийся на сектор плоскости Рис. 4.5. Допустимые направления рекурсии для несимметричной полуплоскостной выходной маски (показана темными кружками). Как и на рис. 4.3, сплошные линии соответствуют допустимым направлениям, штриховые - недопустимым. Однако возможны и другие направления перемещения, как показано на рис. 4.5. Начальные условия, необходимые для этого конкретного несимметричного полуплоскостного фильтра (НПП-фильтра), приведены на рис. 4.6. Заметим, что форма зоны начальных условий зависит от порядка фильтра. НПП-фильтры можно обобщить с помощью отражения или вращения выходной маски, а также комбинации этих операций. Рис. 4.6. Выходная маска, соответствующая рекурсивно вычислимому НПП-фильтру. Светлыми кружками отмечен допустимый набор начальных значений. НПП-фильтр является обобщением фильтра одного квадранта и очень тесно связан с ним, поскольку любой НПП-фильтр можно отобразить на фильтр одного квадранта с помощью линейного отображения, введенного в разд. 1.2.8. Например, выходную маску, приведенную на рис. 4.5, можно отобразить в маску фильтра одного квадранта преобразованием
Это преобразование приводит к маске одного квадранта, показанной на рис. 4.7. Рис. 4.7. Выходная маска, приводимая на рис. 4.5 и 4.6 и отображенная на первый квадрант (или маска одной четверти плоскости). Светлые кружки соответствуют ненулевым коэффициентам, точки - нулевым коэффициентам, а крестики - выходным отсчетам, подлежащим вычислению. Начальные условия рис. 4.6 отображаются в заштрихованную область в форме буквы
|