Класс систем ортогональных функций Хаара, построенных на базе модифицированных комплексных функций Радемахера

Владикавказский математический журнал Январь-март, 2005, Том 7, Выпуск 1

УДК 519.72

КЛАСС СИСТЕМ ОРТОГОНАЛЬНЫХ ФУНКЦИЙ ХААРА, ПОСТРОЕННЫХ НА БАЗЕ МОДИФИЦИРОВАННЫХ КОМПЛЕКСНЫХ ФУНКЦИЙ РАДЕМАХЕРА

Г. Г. Арунянц, М. Л. Казарян

Вводится и исследуется новый класс ортогональных функций Хаара. Строится алгоритм быстрых ортогональных преобразований и оцениваются вычислительные затраты. Для введенного класса функций рассматривается преобразование Карунена — Лоэва.

Вопросы обработки сигналов-изображений остаются в центре внимания специалистов различных специальностей. Изображения выступают и как результат, и как объект исследований в физике, космонавтике, метеорологии, криминалистике и многих других областях науки и техники. Кроме того, системы обработки изображений в настоящее время используются для решения многих прикладных задач. Одним из наиболее полезных средств цифровой обработки сигналов является аппарат быстрых ортогональных преобразований (БОП). Особенный интерес представляют функции Уолша, Хаара, Радемахе-ра. В опубликованной в 1910 г. работе венгерского математика А. Хаара впервые были определены функции Хаара и исследованы некоторые важные свойства рядов Хаара. Наиболее замечательным из этих свойств является равномерная сходимость ряда Фурье непрерывной функции по системе Хаара к самой функции. В дальнейшем были введены системы функций Радемахера (1922 г.) и Уолша (1923 г.). Система Хаара оказалась полезной при решении некоторых актуальных вопросов общей теории ортогональных рядов. Многие принципиальные результаты в этой области принадлежат советским математикам С. В. Бочкареву, Н. Я. Виленкину, В. А. Талаляну, Ф. Г. Арутюняну, П. Л. Ульянову и др. [4]. Первые практические применения систем Уолша и Хаара относятся к области связи. Благодаря работам Х. Хармута функции Уолша вошли в технику телевидения. Им же, на основе упомянутых систем, построена теория секвентного анализа. Важнейшие приложения функции Хаара нашли в практике обработки изображений для эффективного кодирования и сокращения избыточности, фильтрации. Система функций Хаара не обладает некоторыми положительными свойствами тригонометрических функций, но имеет преимущества, делающие ее применение более выгодным. Например, при сжатии изображений система Хаара выделяется: простотой реализации; быстротой вычисления частичных сумм ряда (2(Ж — 1) операций вместо N2 операций, где N обычно имеет порядок 108-1012); сравнительно небольшой мощностью процессоров, реализующих быстрое преобразование Хаара.

Построим систему функций со следующими параметрами [1,2]: N = 2П — количество функций и количество отсчетов каждой функции, где п = 1, 2,...; г — номер системы

© 2005 Арунянц Г. Г., Казарян М. Л.

функций в классе, г = 0,1,...,

Д

где к — номер МФР (к = 1, 2,..., п); х — номер отсчета функции, х = 0,1,..., N — 1;

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

Если переменная пробегает значения 0,1,..., N — 1, то фаза функции й(к, х) меняется скачками на п2-г через интервал 2п-к-г. Вследствие цикличности фазы, функция й(к,х) является периодической с периодом Т = 2п-к+1. На интервале определения функции N укладывается 2к-1 периодов. Построим систему дискретных ортогональных функций, образованных на базе функций Радемахера, используя преобразования Хаара. Система дискретных модифицированных функций Хаара имеет следующий вид:

H

где n = 1, 2,...; r = 0,1,..., n — 1; N = 2n; k = 1, 2,..., n; x = 0,..., N — 1; mc — номер старшего ненулевого разряда в двоичном представлении k; (k) mod 2mc — величина k по

1, если 0 < x < 1, 0, в противном случае. Приведем в качестве примера матрицу H(k, x) третьего порядка, т. е. N = 23; = 0; r = 1;

модулю 2mc; rect(x) =

H(k, ж) =

1 1 1 1 1 1 1 1

1 1 -1 -1

л/2 -V2 V2 -V2

2 2

22

22

2

2

Рассмотрим основные свойства модифицированной системы Хаара. Для этого дополнительно определим модифицированную систему Радемахера для непрерывного и дискретного случаев

Д1

где п = 1, 2,...; г = 0,1,..., п — 1; к = 1,..., п; х = 0,..., N — 1; N = 2п. Дискретная модифицированная система Радемахера имеет вид:

Я

Рассмотрим некоторые свойства функции Й1(к,х).

1. |Я1(к,х)| = 1.

< Действительно, / ni

expl2r

k+1+r

ж + afc+i

\ Í п

= cos —

/ \2r

k+1+r

ж + afc+i

• • , п

+i sin —

\2r

k+1+r

ж

ak+1

= 1. >

2. Справедливы следующие равенства:

а) Ш (й,ж + ) = М(й,ж), где р < й; б) £ Ш (й,ж + ¿г) = 0.

¿=0 4 у

< Рассмотрим следующие случаи: а) Пусть р ^ й.

м+2Р) =ех^ р

к+1+Г

пг

ехР I 27 х

2 + + ж +

Х + + ак+1

2^+1+г

• пг

2Г 2Р

пг

= ехР I 27

2к+1+г • ж + • ехр х 2пг) = Л1 (Л, ж).

б) £ Ш й,ж + ¿И =о. ¿=0 4 7

¿=0

¿=0

£Ш( ж + ^ ) = £ ехр ( Р 2к+1+г • (ж + -+т ) + ак+1

¿=0

Е етР ( р [2'+1+Г • ж + ак+1] + ^ • ) Ш (й, ж) • £ ехр (пг • з) = 0. >

¿=0

3. Если й ^ < йп-1 < • • • < &1, а £1,..., £га принимают значения 1 или —1, то

[ й^1 (й1, ж) • й^2 (й2, ж) •... • #[п (йга, ж) ^ж = 0. 0 1 1 1

< На основании того, что: 1

0

/ Я1£1 (йЬж)Я162 (й2,ж) ••• Й1£(й„,ж)^ж 0

2к"-1 1 „ л__I 3+1

2кп + 2кп + 1

ЕЕ

Л1(й1, ж) • • • Ш(й„, ж)^ж

г=0 ¿=0 2кп —

2кп +1

2к" — 1 „ __| 1 1

2кп + 2кп + 1

«=0 2 кп

2к"-1 I__| , 1

2кп 2кп+1

Е

г=0 2к" -

Е

^Й1£1 ( й1,ж + ¿=0

ж + 1 •••й",ж +

2кп+1

1

Й1£1 (йьж) • (й„-Ьж)^ Й1£п I йп,ж +

з

г=0 " ¿=0

Используя предыдущие свойства, получаем, что последняя сумма равна

2к" + 1 У '

2к" — 1 „ ^__|__

1

Е

2кп 2кп + 1

Й1£1 (йь ж) • • • Й[п-1 (й„-1, ж)£ Й1£п ( , ж + 3 , ) ^ж = 0. >

2к" + 1

г=0 2кп ¿=0

Из свойств 1 и 3 получаем, что {Ш(й,ж)^=0} — ортонормальная система.

1

з

1

Модифицированная система Хаара для непрерывного случая имеет вид:

H 1

где n = 1, 2,...; r = 0,1,..., n — 1; k = 1, 2,..., n; x = 0,..., N — 1; mc — номер старшего ненулевого разряда в двоичном представлении k; (k) mod 2mc — величина k по модулю

2mc.

Дискретная модифицированная система Хаара определяется следующим образом:

H

Введенная система обладает следующими свойствами:

1. Система функций ортонормирована:

1 ,

j H 1(k, x)H 1(p,x) dx = J° P = k, J 1, p = k.

0 4

< Пусть p = k,

1 ¿mc

Jh 12(k,x) dx = 2mc J 1  1 dx = 1,

0 ¿mF (k) mod 2mc

так как R12(mc + 1, x) = 1,

rect(x  2mc — (k) mod 2mc) = 1, если 0 ^ x  2mc — (k) mod 2mc < 1,

то

— (k) mod 2mc < x < —1— ((k) mod 2mc + 1). Пусть p = k, p > k;

1 1 J H 1(k, x)H 1(p, x) dx = y 2m R1mc+1(x)  rect(x2mc — (k) mod 2mc) 00 mc

x2~R1mj+1(x)  rect (x2mc — (p) mod 2mc) dx = 0. >

2. Функции H(k,x) принимают только пф = r значений: учитывая вид функции R1(k,x), а также вид функции H(l,x), можно сделать следующий вывод: функции H 1(k,x) принимают следующие пф = r значений

2m exp (ni  2-r)  rect(2n-r-1 — (l) mod 2m).

3. Функции H(l,x) при l = 0, a^ =0 совпадают с МФР.

H(0, x) = 20  exp (ni2-r [21+r-n  x + 0])  rect (x20 — (0) mod (2°)) = exp (ni2-r [21+r-nx]) = R (1,x).

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

5. При Пф= 0, = 0, где к = 1, 2,..., п, система функций совпадает с системой функций Хаара, так как Я(к,ж) при г = 0 является действительной и совпадает с Я1(к,ж).

6. Матрица Н(I, ж) несимметрична, так как Н(р, ж) = Н(ж,р).

Исследуем введенную систему модифицированных функций Хаара на близость к системе ДЭФ (дискретных экспоненциальных функций [2]). Рассмотрим следующую функцию:

1 _

Рр? = N ^ Н

ж=0

Рр? < 1.

Здесь 5= 0,... —1 — номер функции ДЭФ, def(q, ж) — это произвольная функция ДЭФ. Возьмем в качестве показателя близости Н(р, ж) к системе функций ДЭФ величину Рр тах — максимальное по 5 значение . рр тах это модуль нормированного скалярного произведения вектора функции Н(р, ж) и вектора ближайшей функции ДЭФ, а р^тах — это доля энергии функции Н(р, ж), содержащаяся в максимальном спектральном компоненте ее дискретного спектра. В качестве показателей близости системы Н(р, ж) к системе функций ДЭФ примем рск — среднеквадратическое значение рр тах, а также ртш — минимальное по р значение рртах. Чем больше значение показателей рск, ртш, тем точнее можно разделять преобразуемые дискретные сигналы на узкополосные составляющие и, следовательно, тем лучше частотно-избирательные свойства системы функций Н(р, ж).

Приведем расчеты для двух вариантов системы при = 0; = 0.5.

Рассмотрим различные значения N, Пф и соответствующие им значения рск, ртш. Результаты приведены в таблице 1.

Таблица 1

Пф Вариант системы показатель N=4 N=8 N=16

0 I ртш 0.707 0.5 0.177

I Рск 0.3558 0.3205 0.2454

II ртт 0.0238 0.5 0.177

II Рск 0.3558 0.3355 0.2417

1 I Ртт 0.707 0.5 0.177

I Рск 0.4464 0.4392 0.3768

II Ртт 0.707 0.5 0.177

II Рск 0.4464 0.4392 0.3768

2 I Ртт 0.5 0.177

I Рск 0.4392 0.3768

II Ртт 0.5 0.177

II Рск 0.4392 0.3768

3 I Ртт 0.177

I Рск 0.3768

II Ртт 0

II Рск 0.3768

Избирательные свойства обоих вариантов системы ухудшаются с увеличением N и с уменьшением Пф. При Пф = 0 оба варианта системы равноценны. При Пф = 0 вариант обладает лучшими частотно-избирательными свойствами.

Построим для введенной системы функций алгоритм быстрого преобразования. Целесообразность БОП при обработке сигналов в целом обосновывается тем, что БОП обладают рядом желательных свойств для обработки сигналов-изображений (независимостью обработки строк и столбцов при двумерной обработке, линейностью операций над данными, инвариантностью к сдвигу и др.). За последние несколько десятилетий опубликованы обзорные статьи и монографии по синтезу ортогональных преобразований, анализу отдельных свойств БОП, по отдельным вопросам приложения БОП в обработке сигналов по реализации алгоритмов БОП [1, 2].

Для практического применения введенного ДПФ важно наличие способа его быстрого вычисления — алгоритма быстрого преобразования. Основным критерием алгоритма при его реализации на ЭВМ является число арифметических операций. Основная идея быстрого вычисления ДОП состоит в разложении матрицы преобразования в произведение слабозаполненных матриц. Это, так называемая, факторизация матриц, из-за чего достигается уменьшение числа арифметических операций необходимых для вычисления ДОП. Начиная с 1965 г., с опубликования Кули и Тьюки [1] алгоритма БПФ, были получены многочисленные алгоритмы как быстрого преобразования Фурье, так и других ортогональных преобразований. Объектом нашего изучения будет введенный класс ортогональных преобразований Хаара. Рассмотрим прямое и обратное преобразования в системе Н(р, х), определяемые выражениями:

Г = Н2, 2 = N НУ,

где У — вектор-столбец отсчетов У (х) преобразуемого сигнала, 2 — вектор-столбец спектральных коэффициентов 2(р) сигнала в системе Н(р, х).

Быстрое прямое преобразование вычисляется итерационно:

Уо = У, Ут = НтУт-1 при т = 1,2,..., п,

где Ут — вектор-столбец промежуточных коэффициентов Ут(х) прямого преобразования; т — номер итерации. Быстрое обратное преобразование вычисляется аналогично:

2о = 2, Ут = N12п, 2т = Нт2т-1 при т = 1,..., п, где 2т — вектор-столбец промежуточных коэффициентов 2т(р). Здесь Нт слабозапол-

п—1 п—1

ненная матрица, причем Н = П Е Н»- Рассмотрим процесс факторизации. Пусть дана

¿=0 »=0

матрица Хаара порядка п = 3

1111111 1

1 1 1 1 -1 -1 -1 -1 у/2 /2 л/2 /2

нак2, = /2 /2 /2 •

Матрицы Хаара могут быть представлены в виде суммы кронекеровских произведений. Действительно, матрицы Хаара П-го порядка могут быть разбиты на (П + 1) подматрицу кронекеровского типа в соответствии с номером старшего, равного единице разряда, номера строки, как показано в (9) штриховыми линиями. Определим следующие элементы функции:

V*0 =

1 0

V* =

и20 = [1 1]; /2 =

1 0

0 1

С помощью кронекеровских произведений этих элементарных функций матрица обобщенного преобразования Хаара может быть записана следующим образом [3]:

п и I Г -1

Н (р,ж) = У (2¥ ^  ^(0) У^

¿=0

<Х>

0 )[п-*]

л 0, г = 0, где * = \1, г = 0.

Представим Н(р, ж) в виде произведения слабозаполненных матриц. Обозначим

п-1 п—1

Н (р X) Г7 I ГТ

=1 Ф 2 ' 2 2  /21, где ф — знак прямой суммы, ^ — знак прямой суммы п

¿=0 ¿=0

матриц. Тогда

Н(р,ж) = ^(р

[п—¿]

>2-г[21+г-п-х+а']  V1  (/2)[г-1]и201 5г  (и2°)[п-г] ;

¿=0

Н(р, ж) = ^2!(р ,х)  Н(р, ж).

Обозначим Ъ = в^2 Г [2'+Г "х+а1]. Выделим

слагаемое с номером г = п:

Н(2п, ж) = V,0

п- 1

0 )[п-1-,]

2

<8

¿=0

!0)[п-1-«]

и20 + Ъп  V,1  (/2)[п-1]  и0 =

Н(2п-1,ж)  и20 Ъп  (/2)[п-1]  и0

Так как /

[п-1] 2

/2П-1, то справедлива следующая теорема:

Теорема 1. Если М = М^У <8 М^, то М = (м^У <8 <8 М^). Поэтому

Н(2п, ж) =

Н

Ъп/2п-1

Н

Воспользуемся следующей теоремой из [3]:

ГГЛ ™ * ,т М

Теорема 2. Известно, что, если М

м

то М =

Мг(1) ф М^3

Применив ее к предыдущей формуле, получим:

Н(2п, ж) = Н(2п-1,ж) ф /2п-1

/2п-1 ^ и0 Ъп  /2"- 1  и20

М М

й

Эта формула является рекуррентным выражением обобщенных матриц Хаара. Выразим Н(2п—1,х) через Н(2п—2,х):

Н(2п, х) =

Н(2п—2, х) 0 /2п-2

Н(2п—2, х) 0 12п-2

12п-2  и2

Ьп— 112п-2 <8

12п-2 <8 и0 Ьп— 1/2п-2  и,0 j

0 /2п-1

0 /2П-1 /2п-1

/2п-1  и2 Ьп^п—

12п-1 <8> и0 Ьп/^п—

1  и20

Н (2п,х) =

Н(2п—2,х) 0 /2п—2 0 /2п-1

/2п-2  Ц20

Ьп—112п-2 <8> и0

0 /2п-1

/2"-1  и20

Ьп/2п—1 ^ и2 _

Выше было использовано свойство прямой суммы матриц:

А1А2 • • • Ап 0 В1В2 • • • Вп = (А1 0 В1)(А2 0 В2) ... (Ап 0 Вп).

Следовательно,

Н(2п, х) = Н(2п—2, х 0 /3.2п-2

/2^—2 0 /2п—1 — 12п—2+2п—1 — 1"з-2п—2 ,

0 /2п-1

/2п-2 <8 и0

Ьп— 1/2п-2 <8 и0_

/2п-1  и0

_ Ьп/2П— 1  и20

Продолжая этот процесс, окончательно получим

п— 1 Г Г т- _ тт0

<8 и0

Н (р, х) =

¿=0

ь»+1/2<  и2

0 /2П —

2^—2»+1

Таким образом, обобщенная матрица Хаара представлена в виде произведения п сла-бозаполненных матриц. В каждой ¿-ой матрице такого произведения строк с только двумя отличными от нуля элементами и 2п - 2г+1 строк с только одним не равным 0 элементом. Поэтому умножение матрицы-столбца на такую матрицу требует 2г+1 операций сложения и вычитания. Общее число операций сложения-вычитания:

п— 1

Жсл. = =2  (2п - 1).

¿=0

Умножение на ^П^'^ требует 2п операций умножения. Для наглядности алгоритма быстрого преобразования представим его в виде графа на рис. 1, где п = 3.

Обратное преобразование обобщенной функции Хаара можно представить как произведение матрицы Хаара на матрицу-столбец: Н(р, х)—1 = (Н(р, х))т; так как (М1М2 ... Мп)т = МТ1 ... М2ТМТ, а (А1 0 А2 0    0 Ап)т = АТ 0 АТ 0    0 А^, то

п1

Н (р,х)—1 =

/2п—1—»  и20

Ьn—i—2I2n-l-i

0 /2^—2

п_оп-

1

Как известно, среди всех линейных ортогональных преобразований оптимальным в смысле наименьшего значения среднеквадратической ошибки является преобразование по собственным векторам ковариационной матрицы данных и ПКЛ (преобразования Карунена — Лоэва). ПКЛ — единственное унитарное преобразование, в котором достигается полная декорреляция обрабатываемого сигнала. В связи с этим возникает вопрос определения процесса, для которого заданное преобразование (в данном случае преобразование введенных модифицированных функций Хаара) является преобразованием Карунена — Лоэва. Пусть Jn — случайный сигнал с ковариационной матрицей

Kn : Kn = N Rn RN i Rn = VÑHnA1j/2Mn , где Mn — матрица Уолша — Адамара по-

p-i Е kljl

рядка N, т. е. mt,j = (—1)1=0 , t = 1,... , (t0,... ,tp-1) и (jo,...,jp-i) — двоичные представления чисел t — 1 и j — 1 соответственно. Тогда справедливы равенства

KnHn = HnAn, An = diag(Xi, X2,..., Xn)• Литература

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

2. Дагман Э. П., Кухарев Г. А. Быстрые дискретные ортогональные преобразования.—Новосибирск: Наука, 1983.—232 с.

3. Ярославский Л. П. Цифровая обработка сигналов в оптике и голографии. Введение в цифровую оптику—М.: Радио и связь, 1987.—312 с.

4. Голубов Б. И. Ряды по системе Хаара // Итоги науки и техники. Мат. анализ.—М.: 1971.—С. 109— 146.

Статья поступила 23 июля 2002 г.

Арунянц Геннадий Георгиевич, д.т.н., профессор Владикавказ, Владикавказский научный центр РАН E-mail: suro99@mail.ru

Казарян Мариетта Левоновна, к. ф.-м. н. Владикавказ, Северо-Осетинский госуниверситет E-mail: mariettak@alanianet.ru