Вейвлет-анализ

Материал из Техническое зрение
Перейти к: навигация, поиск

Содержание

Вейвлет-анализ

$\textit{Вейвлет-анализ}$ в отличие от Фурье-анализа опирается на специальные "малые волны" (вейвлеты), ограниченные во времени (в случае изображений - в пространстве). Это позволяет в вейвлет-представлении сразу иметь и частотную, и пространственную информацию. Вейвлет-анализ предназначен, прежде всего, для одновременного анализа изображения в нескольких масштабах, который получил название $\it{кратномасштабного}$ анализа.

Пирамида изображений.

Исторически первой структурой для анализа изображений в различных масштабах являлась так называемая $\it{пирамида изображений.}$

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

Использование пирамидальной структуры данных в алгоритмах обработки изображений имеет две основные цели:


  1. сокращение времени обработки изображений;
  2. определение более точных начальных приближений для обработки нижних уровней по результатам обработки верхних уровней.

3-3-29.jpg

Принцип построения пирамиды изображений

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


Если позволяют вычислительное ресурсы, то для подавления высокочастотных шумов рекомендуется перед прореживанием использовать низкочастотную линейную фильтрацию. В качестве ядра линейного фильтра обычно выбирают функцию Гаусса. В этом случае пирамида называется $\it{гауссовой}$. Согласно теореме Котельникова сжатие в гауссовой пирамиде происходит с минимальной потерей информации.

Изображение $f_{N}(x,y)$ представляет собой уменьшенную копию исходного изображения $f_{1}(x,y)$. Размер пиксела изображения уровня $N$ равен

$$ p_{N} = 2^{N-1}. $$

Для координат пикселов изображений двух произвольных уровней пирамиды с номерами $n$ и $m$ справедливы следующие соотношения:

\begin{gather*} 2^{n-1} x_{n} = 2^{m-1}x_{m} ,\\ 2^{n-1}y_{n} = 2^{m-1}y_{m}. \end{gather*}

Помимо гауссовых пирамид изображений, часто рассматриваются также $\textit{пирамиды лапласианов}$. Для построения такой пирамиды выполняется следующая операция: на каждом уровне гауссовой пирамиды выше нулевого текущее изображение увеличивается в два раза по каждой координате (при этом его размер становится равен размеру изображения на предыдущем уровне пирамиды), после чего вычисляется его разность с предыдущим уровнем. Получившийся результат также представляет собой пирамиду изображений, эквивалентную результату применения $\textit{оператора Лапласа}$ соответствующего масштаба (см. описание оператора Лапласа ниже в разделе 3.4).

Вейвлет-преобразование.

$\it{Вейвлет-преобразование}$ - это математический инструмент для иерархической декомпозиции функций. С помощью $\it{вейвлетов}$ функции представляются как композиция грубой низкочастотной аппроксимации и уточняющих компонент (деталей), представляющих отсутствующие в аппроксимации элементы графика функции. Вне зависимости от вида функции (изображение, кривая, поверхность) вейвлет представляет функцию как иерархию уровней отображения с различной точностью детализации. В процедурах предобработки изображений вейвлет-преобразование используется для уменьшения уровня шумов, анализа текстур, выделения контуров объектов и сжатия изображений.

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

$$ f(x) = \sum\limits_i c_i \phi _i (x), $$

где $\phi_{i} (x)$ - $\textit{базисные функции}$, а $c_{i}$ - $\textit{весовые коэффициенты}$.

Коэффициенты этого представления определяются из соотношения

$$ C_n = \frac{1}{\vert\vert \phi_n \vert\vert^2} \int\limits_{t_1}^{t_2} f(x)\phi_n (x) dx, $$

где

$$ \vert\vert \phi_n \vert\vert^2 = \int\limits_{t_1}^{t_2} {\phi^2}_n (t) dt $$

есть квадрат нормы, или $\it{энергия}$ базисной функции $\phi_{n} (x)$.

Такое представление называется $\it{обобщенным рядом Фурье}$. Обобщенный ряд Фурье при заданной системе базисных функций и конечном числе слагаемых $N$ обеспечивает наилучший синтез по критерию минимума среднеквадратической ошибки. Так как базисные функции в разложении фиксированы, то вся информация о функции $f(x)$ содержится в весовых коэффициентах.

В своей простейшей форме базисные функции могут быть представлены как смещенные вдоль пространственной или временной оси единичные импульсные функции. Такое отображение дает представление о локальных (пространственных или временных) параметрах функции. Если в качестве базисной функции выбрана синусоида, то получается известное преобразование Фурье - дающее информацию о поведении частотных (спектральных) компонент функции $f(x)$. Однако во многих приложениях, включая обработку изображений, необходимо одновременно иметь информацию и о пространственных, и о спектральных характеристиках функции $f(x)$.

Вейвлет-преобразование сигнала - это его представление в виде обобщенного ряда Фурье или интеграла Фурье по системе базисных функций, локализованных как в пространственной, так и в частотной областях. Примером такой базисной функции может служить $\textit{вейвлет Хаара}$, который определяется выражением

$$\phi (t)= \begin{cases} 1,& \mbox{при } 0 \le t\le 1/2 ,\cr -1,& \mbox{при } 1/2 \le t\le 1 ,\cr 0,& \mbox{при } 0<t, t>1. \end{cases} $$

Графическое изображение вейвлета Хаара приведено на рис. 30.

3-3-30.jpg

Вейвлет Хаара

Однако пространственные (временные) и частотные характеристики не могут быть одновременно измерены со сколь угодно высокой точностью. Точность измерения пространственных характеристик $\Delta x$ и частотных характеристик $\Delta \omega $ ограничена снизу соотношением Гейзенберга\looseness=-1


$$ \Delta x \Delta \omega \geqslant \frac {1}{2} . $$

Рассмотрим процесс разложения сигнала $F(t)$ в системе базисных функций Хаара. Первая базисная функция, в отличие от всех последующих, представляет собой прямую линию. В случае нормированного базиса $\{\phi _{n}(t)\}$ свертка первой базисной функции с исходным сигналом будет определять его среднее значение. Последующие базисные функции разложения Хаара представляют собой масштабируемые по

3-3-31.jpg

Вид базисных функций Хаара для различных масштабов

степени $2$ сдвинутые "ступеньки", представленные выше на рис. 30. Таким образом, система базисных функций Хаара в дискретном пространстве должна задаваться двумя параметрами: $\it{сдвига}$ и $\it{частоты}$ (масштаба):

$$ \phi_{ab} (t)= \frac {1}{\sqrt{a}} \phi \left( {\frac {t-b} {a}}\right), $$

где $a$ - масштаб базисной функции; $b$ - сдвиг. В дискретном случае параметр масштаба $a = 2^{m}$, где $m$ - любое целое положительное число, параметр сдвига $b = k2^{m}$. Таким образом, все множество базисных функций можно записать как

$$ \phi_{mk} (t)= \frac {1}{\sqrt{2^m}} \phi \left( {2^{-m}n - k}\right). $$

На рис. 31 представлен вид базисных функций Хаара для различных масштабов.

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

Для вейвлет-преобразования, так же как и для ДПФ, существует алгоритм быстрого преобразования. Рассмотрим преобразование Хаара. Из рис. 31 видно, что функции с малым масштабным коэффициентом $a$ используют те же отсчеты сигнала для вычисления коэффициентов, что и функции с большим масштабным коэффициентом. При этом операция суммирования одних и тех же отсчетов повторяется неоднократно. Следовательно, для уменьшения объема вычислений целесообразно вычислять Вейвлет-преобразование с самого малого масштабного коэффициента. В результате получаем вейвлет-коэффициенты, представляющие собой средние значения $C_{1,k} =\left( {x_i +x_{i+1} } \right)/2$ и разности $C_{1,j} =\left( {x_i -x_{i+1} } \right)/2$. Для коэффициентов $C_{1,k} =\left( {x_i +x_{i+1} } \right)/2$ повторяем данную процедуру. При этом усреднение коэффициентов $\left( {C_{1,k} +C_{1,k+1} } \right)/2$ будет соответствовать усреднению четырех отсчетов сигнала, но при этом расходуется одна операция умножения и одна операция умножения и одна операция сложения. Процесс разложения повторяется до тех пор, пока не будут вычислены все коэффициенты спектра.

3-3-32.jpg

Исходное изображение

3-3-33.jpg

Пример двумерного вейвлет-преобразования Хаара

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


На рис. 32 представлены исходное изображение, а на рис. 33 - четыре компонента вейвлет-образа. Размер каждого компонента в два раза меньше соответствующего линейного размера исходного изображения.

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

Полезные ссылки

  1. ☝ К началу
  2. ☜ Линейная фильтрация изображений в пространственной и частотной области
Личные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты