ПРЕОБРАЗОВАНИЯ ФУРЬЕ-УОЛША В ЦИФРОВОЙ ОБРАБОТКЕ СИГНАЛОВ ИЗОБРАЖЕНИЙ

Толеуханова Р.Ж., Кервенев К.Е., Зулхажав А.

Карагандинский государственный университет

имени академика Е.А.Букетова

С бурным развитием вычислительной техники выявились преимущества, которые дают при цифровой обработке информации преобразования Фурье. Опубликован ряд фундаментальных работ Х.Хармута, А.М.Трахтмана, Л.А.Залманзона, оказавших большое влияние на развитие данного направления. Реальные сигналы всегда являются функциями с ограниченным интервалом определения, поскольку их наблюдение, регистрация и обработка не могут выполняться бесконечно долго (см. [1], [2]). При восстановлении исходного фрагмента сигнала изображения выявлены некоторые особенности коэффициентов преобразований Уолша.

Система Уолша является ортогональной на интервалах определения сигналов и удобна для их разложения, поэтому двумерную систему   можно рассматривать в роли базисной системы  .

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

                                            (3)

При этом спектр и равенство Парсеваля запишутся следующим образом:

;                                              (4)

     .                                      

Усечённые двумерные ряды Уолша

                               (5)

обладают теми же видами сходимости, что и усечённые одномерные ряды Уолша, и могут быть использованы для аппроксимации двумерных непрерывных сигналов.

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

                                    (6)

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

         Пусть  множество дискретных функций Уолша, определённых на прямоугольнике со сторонами N и M . Для двумерных сигналов с известным аналитическим описанием используем формулу расчёта спектральных коэффициентов вида

,

где  и   -  дискретные функции Уолша.

Здесь выражение 

                                         (7)

определяет двумерный дискретный ряд Фурье-Уолша или двумерное дискретное преобразование Уолша. Коэффициенты этого ряда   - суть двумерный дискретный спектр.

         Они, также как и коэффициенты двумерного непрерывного ряда Уолша, могут быть получены двукратным применением одномерного дискретного преобразования Уолша соответственно по координатам  i  и  j:

                       (8)

         Эффективные значения составляющих спектра (обобщённых гармоник) есть коэффициенты Фурье-Уолша.        В случае использования при обработке сигналов спектральной формы представления сигналов возникает необходимость в операции анализа спектра.

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

                       (9)

В случае плоского (двумерного) или многомерного сигнала для распознавания используются двумерные или соответственно многомерные спектры [3]. Многомерный сигнал можно преобразовать в одномерный за счёт увеличения объёма этого числового массива. Тогда встаёт задача установления соотношений между спектром многомерного массива и спектром преобразованного из него одномерного сигнала. Покажем возможность преобразования двумерного спектра Уолша  в одномерный, путём построчного сканирования с сохранением номера в каждой строке.

         Спектр ,  (,) двумерного сигнала , определим соотношением

                        (10)

         Существование зависимости между ортогональным спектром двумерного сигнала и ортогональным спектром для одномерного массива, полученным из двумерного путём построчного сканирования в одномерный, обнаружено Жуковым Д.М. [4]. Нашей задачей является проверка существования этой зависимости для базиса из кусочно-непрерывных функций Уолша.

Лемма [3]. Для любых 

                   справедливы равенства

                           (11)

Теорема.    Пусть  - спектр двумерного сигнала   и 

       - спектр, полученный для одномерного

      сигнала  в котором при    

     , положено .

         Тогда при , справедливы

      соотношения  .

         В теореме показано то, что при переходе от одномерного спектра  к двумерному  путём расположения по М элементов в каждой строке можно получить транспонированный исходный спектр.

Для сокращения объёма вычислений разработан ряд специальных алгоритмов, учитывающих те или иные особенности СБФ. Из совокупности специализированных алгоритмов анализа спектра наибольшей вычислительной эффективностью обладают итерационные вычислительные процедуры, называемые быстрыми преобразованиями. Суть их состоит в том, что исходная выборка анализируемого сигнала путём прореживания разбивается на ряд промежуточных выборок и спектр сигнала выражается через спектр этих выборок. Так как расчёт промежуточных спектров требует меньшего числа вычислительных операций, чем расчёт спектра исходной выборки, и для вычисления всех спектральных коэффициентов используются одни и те же промежуточные спектры, то достигается существенная экономия операций.

Известно, что для обеспечения высокой помехоустойчивости применяют сложные сигналы [5]. Для их формирования часто используют ансамбль М-последовательностей (максимального периода), отличающихся тем, что все циклические сдвиги и нулевая последовательность длины N=2**n – 1, где  n – количество информационных символов, образуют код максимальной длины. Корреляционное декодирование подобных последовательностей при многомерном входном сигнале включает процедуру вычисления корреляционного вектора и поиск его максимальной компоненты, по которой осуществляется идентификация блока информационных символов. Существенное снижение затрат на реализацию данного алгоритма достигается при использовании быстрого преобразования Уолша по Адамару (БПУА) и его модификаций.

БПУ представляет собой алгоритм для вычисления преобразования Уолша с помощью сложения и вычитания без умножения на множитель 1/N. Вычисляются коэффициенты Фурье в базисе Уолша. В этом алгоритме используется граф типа Кули-Тьюки, а сам алгоритм осуществляется за N log2N  операций сложения и вычитания.

Массив данных (N*M) располагается в виде вектора размерностью 1*NM. С помощью одномерного БПУ с упорядочением по Адамару вычисляются коэффициенты.

         Алгоритм, известный как алгоритм БПУА, намного сокращает количество арифметических операций и объём памяти, необходимый, например, для вычисления дискретного преобразования [6].

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

 

Литература

 

1.     Игнатов В.А. Теория информации и передачи сигналов. – М.: Радио и связь, 1991. – 257 с.

2.     Смирнов Ю.М. и др. Проектирование специализированных информационно-вычислительных систем. – М.: Высшая школа, 1984. – 359 с.

3.     Голубов Б.И., Ефимов А.В., Скворцов В.А.  Ряды и преобразования Уолша. Теория и применения. – М.: Наука, 1987. – 343 с.

4.     Жуков Д.М. Эквивалентность одномерного и двумерного преобразования Крестенсона-Леви // Методы цифровой обработки изображений. – М.: МИЭТ, 1982. – С.65-70.

5.     Блейхут Р.  Быстрые алгоритмы цифровой обработки сигналов. – М.: Мир. – 1989.

6.     Ахмед Н., Рао К.Р.  Ортогональные преобразования при обработке цифровых сигналов. – М.: Связь. – 1980. – 248 с.