3.11. Другие ортогональные преобразования. Обзор применений

На основе преобразований ДПФ, Уолша—Адамара и Хаара может быть построен целый ряд других ортогональных преобразований. Они могут определяться либо с помощью кронекеровского произведения, либо в виде суммы кронекеровских произведений. Например, в [117] предложено гибридное преобразование Адамара—Хаара, матрица которого порядка размерности определяется как

В работе [80] дано рекурсивное определение так называемого модифицированного преобразования Адамара

и указана его связь с преобразованием Хаара.

В [57, 77] рассматривается матрица так называемого обобщенного преобразования Уолша порядка размерности (преобразования по функциям Виленкина—Крестенсона ), определяемая как кронекеровская степень матрицы

В работе [118] описано так называемое -преобразование, которое строится на базе преобразования Уолша—Адамара путем замены каждой суммы в выражении (3.114) ее абсолютным значением. Это преобразование необратимо.

Следует упомянуть также предложенные для кодирования изображений слэнт-преобразование [115], «слэнт-Хаар» преобразование [88] и преобразование по дискретному базису [98].

Можно показать, что большинство используемых в настоящее время в обработке изображений унитарных преобразований может быть представлено в виде сумм кронекеровских произведений элементарных матриц матриц перестановки и некоторых других. Такое представление матриц Хаара, Адамара, Уолша, Уолша—Пэли, модифицированной матрицы Адамара, матрицы Адамара — Хаара, матрицы ДПФ, обобщенной матрицы Уолша показано в табл. 3.5 с использованием следующих обозначений:

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

(см. скан)

Продолжение табл. 3.5 (см. скан)

Это представление создает удобную основу для сравнения преобразований. Так, сравнивая представления для матрицы легко «заметить, что они отличаются инверсным порядком следования матриц в каждом слагаемом, матрица MHAD отличается от матрицы Адамара HAD тем, что она строится не на

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

На основе описанных одномерных преобразований могут быть построены соответствующие двумерные разделимые преобразования как двойные одномерные:

где М — одна из матриц преобразований, описанных выше; а — двумерный дискретный сигнал; а — его преобразование.

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

Так получаются смешанные преобразования, используемые в специализированных цифровых устройствах кодирования изображений (см., например, [78]).

Применения унитарных преобразований в обработке изображений можно разбить на три группы:

— кодирование изображений;

— выделение признаков для препарирования и распознавания изображений;

— обобщенная фильтрация.

Кодирование изображений — основное в настоящее время применение преобразований (кроме ДПФ). Более того, некоторые из преобразований (например, слэнт-преобразование и преобразование по дискретному линейному базису и др.) были введены специально для использования при кодировании.

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

Использование унитарных преобразований для фильтрации сигналов основано на обобщении понятия фильтрации в частотной области дискретного преобразования Фурье. При фильтрации сигналов с использованием ДПФ выполняется следующее преобразование сигнала:

где а — последовательность исходного сигнала; — матрица — диагональная матрица, состоящая из коэффициентов ДПФ импульсной реакции требуемого фильтра; — матрица обратного ДПФ; а — сигнал после фильтрации.

Если вместо ДПФ при таком преобразовании сигнала использовать другое преобразование Т, то матрица описывающая фильтр, должна быть заменена другой матрицей, вообще говоря, неднагональной:

Если надлежащим образом подобрать матрицу можно получить тот же результат фильтрации, что и с помощью ДПФ по (3.138). Очевидно, что для этого должно выполняться условие

или

где

— матрицы перехода от преобразования Т к ДПФ и наоборот.

Такой подход был предложен в [113, 114] для обобщения оптимальной линейной (винеровской) фильтрации (см. также [80]).

В зависимости от вида преобразования Т и свойств требуемого фильтра сложность выполнения операции фильтраций (3.139), оцениваемая, скажем, количеством операций, может меняться. В частности, может оказаться, что вместо ДПФ выгоднее использовать более быстрое преобразование Уолша—Адамара несмотря на большую сложность умножения на недиагональную матрицу фильтра в этом случае (см. также § 6.5).