Разложение изображений с помощью двумерного дискретного вейвлет-преобразования и быстрого преобразования Хаара

РАЗЛОЖЕНИЕ ИЗОБРАЖЕНИЙ С ПОМОЩЬЮ ДВУМЕРНОГО ДИСКРЕТНОГО ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЯ И БЫСТРОГО ПРЕОБРАЗОВАНИЯ ХААРА

Т. Т. Ч. Буй, В. Г. Спицын

Институт кибернетики Национального исследовательского Томского политехнического университета, 634034, Томск, Россия

УДК 004.932

Рассматриваются вопросы двумерного дискретного вейвлет-преобразования и быстрого преобразования Хаара для разложения изображений. Представлены формулы для разложения изображений.

Ключевые слова: обработка изображения, двумерное дискретное вейвлет-преобразова-ние, быстрое преобразование Хаара.

It is considered questions of two-dimensional discrete wavelet transform and fast Haar wavelet transform for expansion of images. Formulas for expansion of images are presented.

Key words: image processing, two-dimensional discrete wavelet transform, fast Haar wavelet transform.

Введение. Интерес к цифровым системам обработки изображений обусловлен простотой их использования и экономической эффективностью. Недостатком этих систем является низкое пространственное разрешение по сравнению с традиционными пленочными фотоаппаратами. При любом способе обработки изображения главной задачей является нахождение эффективного представления, которое позволяет представить изображение в компактной форме. В современной теории и практике сигналов, в частности при спектральном анализе, используются сигналы специального вида — вейвлеты [1, 2].

В работах [3-5] представлены теория и практические применения различных вейвлетов. Практически важные вейвлеты традиционно определяются как функции одной вещественной переменной с вещественными значениями. В зависимости от математической модели (структуры области определения, структуры области возможных значений и вида преобразований) различаются дискретные и непрерывные вейвлеты. Поскольку разложение сигналов в базисе вейвлетов осуществляется с использованием арифметики с плавающей точкой, возникают ошибки, величина которых зависит от степени приближения сигнала.

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

Вейвлеты Хаара [6] представляют собой кусочно-постоянные функции, заданные на конечных интервалах различных масштабов и принимающие два значения {-1; +1}. Вейвлет Хаара единичного масштаба и нулевого смещения (материнский вейвлет Хаара) — функция,

равная +1 на интервале [0; 1/2) и -1 на интервале [1/2; 1). Вейвлеты Хаара хорошо зарекомендовали себя в практических задачах обработки дискретных сигналов, таких как массивы отсчетов аудиосигналов и цифровые фотографии. Характерная особенность преобразования Хаара заключается в том, что оно является разделимым и легко вычисляется.

1. Преобразование и быстрое преобразование Хаара. Преобразование Хаара (ПХ) является одним из простейших базисных вейвлет-преобразований. Пусть имеется одномерный дискретный сигнал / = (/1, /2, • • • , /м) • ПХ разлагает каждый сигнал на два компонента, один из которых называется средним, а другой известен как разность [6]. Первое среднее значение подсигнала а1 = (а1, а2, • • •, ам/2) на первом уровне для одного сигнала длиной N (/ = (/1, /2, • • • , /и)) вычисляется по формуле [6]

/2п- 1 + /

2п

л/2

и первый детализирующий подсигнал С = (С1, С2, ляется как

, п = 1, 2, 3, • • .,N/2,

, См/2) на таком же уровне представ-

с

п

/2п-1 — /:

2п

у/2

п

1, 2, 3,

N/2.

Эти значения формируют два новых сигнала: а = {ап},п Е Ъ и С = {Сп},п Е Ъ, один из которых является огрубленной версией исходного сигнала (каждой паре элементов / соответствует их среднее арифметическое), а другой содержит информацию (будем называть ее детализирующей), необходимую для восстановления исходного сигнала. Действительно:

/2п-1 = ап + Сп, /г.

2п

— Сп, п Е Ъ

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

Для того чтобы определить принцип работы вейвлет-преобразования, рассмотрим следующий пример. Предположим, что

В случае применения одномерного ПХ вдоль первой строки коэффициенты аппроксимации следующие: (1 + 2)/^ , (3 + 4)Д/2, коэффициенты различия — (1 -2)/^, (3-4)/л/2. То же преобразование применяется к другим строкам I. Располагая коэффициенты аппроксимации каждой строки в первых двух столбцах и соответствующие коэффициенты различия в последних двух столбцах, получаем

( 1 2 3 4 \ 4567 8912

3456

(

1

71

37 9 13 17 3 7 11

-1 -1 -1 -1 -1 -1 11

\

а

п

а

п

—>

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

(

1

71

V

3 7 . - -1 -1

9 13 . - -1 -1

17 3 . - -1 -1

7 11 . - 11

\

1

72

Таким образом, имеем 12 20

А

24 14

Н

-2 -2 22

V

12 20

24 14

-6 -6

\ 10 -8

-6 -6 10 8

-2 -2 22

0 0

0 0

В =

00 00

Каждая часть одномерного ПХ, показанного в примере, имеет размерность (число строк/2) х (число столбцов/2), эти области обозначены А, Н, V, В соответственно. Область А (область приближения) включает информацию о глобальных свойствах проанализированного изображения. Удаление спектральных коэффициентов от этой области приводит к наибольшему искажению исходного изображения. Область Н (горизонтальная область) включает информацию о вертикальных строках, спрятанных (скрытых) в изображении. Удаление спектральных коэффициентов от этой области исключает горизонтальные детали из исходного изображения. Область V (вертикальная область) содержит информацию о горизонтальных строках, спрятанных (скрытых) в изображении. Удаление спектральных коэффициентов от этой области приводит к исчезновению вертикальных деталей из исходного изображения. Область В (диагональная область) включает информацию о диагональных деталях, скрытых в изображении. Удаление спектральных коэффициентов от этой области приводит к минимальному искажению исходного изображения. Таким образом, ПХ применимо в случае, когда матрица изображения содержит число строк и столбцов, кратное двум.

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

2. Двумерное вейвлет-преобразование. Двумерное вейвлет-преобразование представляет собой поочередное одномерное вейвлет-преобразование строк и столбцов этой матрицы. Сначала выполняются одномерные вейвлет-преобразования каждой строки, после чего преобразованная строка записывается на прежнее место. Элементы нумеруются способом, указанным выше. Далее вейвлет-преобразования применяются ко всем столбцам. В результате изображение разбивается на четыре равные части (рис. 1). На рис. 1 показаны стандартные обозначения квадрантов преобразованного изображения: ЬЬ, ЬН, НЬ, НН. Квадрант ЬЬ соответствует низкочастотным вейвлет-коэффициентам, НН — высокочастотным [7].

Если не оговорено иное, под Ж-кратным двумерным вейвлет-преобразованием понимается применение N раз двумерного вейвлет-преобразования, причем очередное двумерное

—>

ьь нь

ьн ии

ььз ньз НЬ2 НЬ1

ьнз низ

ЬН2 НН2

ЬН1 НН1

Рис. 1. Однократное применение двумерного вейвлет-преобразования к квадратному изображению

Рис. 2. Трехкратное применение двумерного вейвлет-преобразования

вейвлет-преобразование применяется к младшей четверти матрицы (квадрант ЬЬ на рис. 1). Полученное ^кратное преобразование показано на рис. 2 N = 3). На рис. 2 приведены стандартные обозначения квадрантов изображения. Квадранты ^кратного двумерного вейвлет-преобразования обозначаются аналогично.

Обратное двумерное вейвлет-преобразование рекурсивно восстанавливает младший квадрант. В случае, представленном на рис. 2, для получения (восстановления) нового квадранта ЬЬ2 используются квадранты ЬЬ3, ЬН3, НЬ3 и НН3. Далее, для восстановления квадранта ЬЬ1 используются квадранты ЬЬ2, ЬН2, НЬ2, НН2 и т. д. Аналогично выполняется N-кратное обратное вейвлет-преобразование.

Заметим, что указанное преобразование является иерархическим. Иными словами, если при использовании обратного вейвлет-преобразования вычисляются не все уровни, а меньшее их количество, то в квадранте ЬЬ образуется уменьшенная копия изображения (рис. 3). Если обратное вейвлет-преобразование не используется, то младший квадрант также является уменьшенной копией изображения. В силу этого свойства обратное вейвлет-преобразование позволяет вырезать фрагменты изображений различного масштаба. Однако заметим, что, во-первых, доступные масштабы определяются количеством уровней вейвлет-преобразования, и, во-вторых, масштабы не произвольны, а увеличены в два раза.

Рис. 3. Однократное применение двумерного вейвлет-преобразования или применение (Ж—1)-кратного обратного вейвлет-преобразования к изображению, полученному Ж-кратным вейвлет-преобразованием

а 6 в

Рис. 4. Вейвлет-преобразование изображения с использованием быстрого преобразования Хаара первого (а), второго (б) и третьего (в) порядков

3. Результаты быстрого преобразования Хаара. В результате исследования средствами C# создано приложение, реализующее быстрое преобразование Хаара. Это приложение способно обрабатывать файлы формата *.gif размером 256x256 пикселей. Изображения, представленные на рис. 4, получены с использованием быстрого преобразования Хаара в качестве функций (базисных функций).

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

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

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

Список литературы

1. Gonzalez R. C. Digital image processing / R. C. Gonzalez, R. E. Woods. Boston: Addison-Wesley, 2001. 813 p.

2. Pratt W. K. Digital image processing. N. Y.: Wiley Intersci., 2001. 738 p.

3. Чуи Ч. Введение в вейвлеты. М.: Мир, 2001. 412 с.

4. Яковлев А. Н. Введение в вейвлет-преобразования. Новосибирск: НГТУ, 2003. 104 с.

5. Mallat S. A wavelet tour of signal processing. N. Y.: Acad. Press, 1999. 851 p.

6. Anüj B., Rashid A. Image compression using modified fast Haar wavelet transform // World Appl. Sci. J. 2009. V. 7, N 5. P. 647-653.

7. Шокуров А. В., Михалев А. В. Оптимальное использование вейвлет-компонент // Успехи мат. наук. 2007. Т. 62, № 4. С. 171-172.

Буй Тхи Тху Чанг — асп. Института кибернетики ТПУ;

тел.(3822) 41-89-12; e-mail: trangbt.084@gmail.com; Спицын Владимир Григорьевич — д-р техн. наук, проф. Института кибернетики ТПУ; тел. (3822) 41-89-12; e-mail: spvg@tpu.ru

Дата поступления — 25.02.11 г.