Главная > Моделирование, обработка сигналов > Введение в цифровую обработку изображений
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

3.9. Преобразование Уолша и родственные ему

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

Начнем с преобразования Уолша. Выше уже приводилось определение функций Уолша (§ 1.3). Как и дискретное преобразование Фурье, дискретное преобразование Уолша строится как преобразование последовательности отсчетов сигнала по базису из отсчетов функций Уолша, взятых в дискретной последовательности точек:

Пусть количество отсчетов сигналов N равно Таково же количество базисных функций: Тогда, пользуясь формулой (1.46), значение базисной функции Уолша можно записать как

где — разряды кода Грея номера функции s, взятые в инверсном порядке (т. е. читаемые слева направо); — разряды двоичного кода номера отсчета.

Подставив (3.111) в (3.110), получим

Поскольку

суммирование в (3.112) по к можно выполнить как многомерное по

Такое представление является основой построения алгоритмов быстрых преобразований Уолша (см. гл. 4).

Формула обратного преобразования Уолша совпадает с формулой прямого преобразования (3.106):

Как следует из формулы (3.111), функции Уолша в преобразовании Уолша упорядочены в соответствии с двоично-инвертированными (т. е. читаемыми в обратном порядке) кодами Грея их номера. Если вспомнить, что функции Уолша порождаются функциями Радемахера, то смысл такого упорядочения в том, что каждая следующая по номеру функция Уолша отличается от предыдущей добавлением или изъятием только одной функции Радемахера.

Можно упорядочить те же функции просто по их двоичным номерам. Преобразование по таким функциям

носит название преобразования Уолша—Адамара (в некоторых источниках — преобразование Адамара или BIFOR-преобразование [80])

Способ упорядочения базисных функций определяется только соображениями удобства, так как независимо от нумерации каждый коэффициент преобразования соответствует своей базисной функции из одного и того же множества функций. Обычно удобно связывать порядок базисных функций со сходимостью представления по ним сигналов, считая, что каждый старший по номеру коэффициент представления, соответствующий старшей по номеру базисной функции, вносит меньший вклад в сигнал. С этой точки зрения иногда оказывается лучше упорядочение базисных функций Уолша в соответствии с двоично-инвертированным двоичным кодом. Такое упорядочение было введено Пэли [57]:

Описанные дискретные преобразования могут быть представлены в матричной форме как умножение матрицы-столбца исходной последовательности а на матрицу преобразования. В результате получается матрица-столбец преобразования а:

где — матрицы преобразования Уолша, в которых строки — базисные функции — определяются (3.116, 3.111 и 3.118) соответственно.

Например, матрицы таковы:

(см. скан)

Справа от каждой матрицы в (3.120) указано число перемен знака в соответствующей строке матрицы. Сравнивая эти данные, можно видеть, что строки матрицы Уолша упорядочены по числу перемен знака или так называемой «частости».

Матрицы преобразований Уолша являются симметрическими, т. е. не меняющимися при транспонировании, и ортогональными, так как они обратны самим себе.

Таким образом, преобразования Уолша, так же как и ДПФ, относятся к классу унитарных преобразований (для действительных матриц, какими являются матрицы

преобразований Уолша, понятия унитарности и ортогональности совпадают).

Матрицы WAL можно свести к матрице Адамара HAD; если домножить их на соответствующие матрицы перестановки, содержащие единицу на том элементе строки чей номер к совпадает с номером элемента переставляемой последовательности, который должен перейти с номера к на При умножении матрицы-столбца на такие матрицы происходит перестановка ее элементов, при умножении матрицы на матрицы перестановки происходит перестановка ее строк.

Пусть МТ—матрица двоичной инверсии; — матрица перестановки кода Грея в простой двоичный код. Тогда

Поскольку матрица Уолша-Пэли, матрица двоичной инверсии и матрица Адамара являются симметрическими, то справедливо также соотношение

Важной особенностью матрицы Адамара является то, что она принадлежит к так называемым кронекеровским матрицам т. е. может быть представлена в виде кронекеровского (прямого) произведения матриц Адамара второго порядка:

где Признак — обозначения кронекеровского произведения и двух матриц соответственно; — кронекеровское возведение в степень

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

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

где — двумерные последовательности (матрицы размером

<< Предыдущий параграф Следующий параграф >>
Оглавление