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

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

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

где φ – базисная функция, аc_i–весовые коэффициенты.

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

,

где

есть квадрат нормы или энергиябазисной функции φ(t).

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

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

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

Графически вейвлет Хаара представляется следующим образом (рис. 3.3.30):

@Рис. 3.3.30. Вейвлет Хаара

Однако пространственные (временные) и частотные характеристики не могут быть одновременно измерены со сколь угодно высокой точностью. Точность измерения пространственных характеристик x и частотных характеристикограниченна снизу неравенством Гейзенберга

Рассмотрим процесс разложения сигнала F(t) в системе базисных функций Хаара. Первая базисная функция, в отличие от всех последующих, представляет собой прямую линию. В случае нормированного базиса {_n(t)} свертка первой базисной функции с исходным сигналом будет определять его среднее значение. Последующие базисные функции разложения Хаара представляют собой масштабируемые по степени 2, сдвинутые «ступеньки», представленные выше на рис. 3.3.30. Таким образом система базисных функций Хаара в дискретном пространстве должна задаваться двумя параметрами:сдвигаичастоты(масштаба):

,

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

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

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

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

Для вейвлет преобразования также как и для ДПФ существует алгоритм быстрого преобразования. Рассмотрим преобразование Хаара. Из рис. 3.3.31. видно, что функции с малым масштабным коэффициентом a используют те же отсчеты сигнала для вычисления коэффициентов, что и функции с большим масштабным коэффициентом. При этом операция суммирования одних и тех же отсчетов повторяется неоднократно. Следовательно, для уменьшения объема вычислений целесообразно вычислять Вейвлет-преобразование с самого малого масштабного коэффициента. В результате получаем вейвлет-коэффициенты, представляющие собой средние значения и разности.Для коэффициентовповторяем данную процедуру. При этом усреднение коэффициентовбудет соответствовать усреднению четырех отсчетов сигнала, но при этом расходуется одна операция умножения и одна операция умножения и одна операция сложения. Процесс разложения повторяется до тех пор, пока не будут вычислены все коэффициенты спектра.

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

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

@Рис. 3.3.32. Исходное изображение

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

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

1.5. ВЫДЕЛЕНИЕ КОНТУРНЫХ ТОЧЕК (КОНТУРОВ) НА ПОЛУТОНОВЫХ ИЗОБРАЖЕНИЯХ. ЭВРИСТИЧЕСКИЕ МЕТОДЫ ВЫДЕЛЕНИЯ КОНТУРОВ. МЕТОДЫ, ОСНОВАННЫЕ НА ВЫЧИСЛЕНИИ ПРОИЗВОДНЫХ. КУСОЧНО-ПОСТОЯННАЯ И КУСОЧНО-ЛИНЕЙНАЯ МОДЕЛЬ ИЗОБРАЖЕНИЯ. ДВА ТИПА "КРАЕВ". ОПЕРАТОРЫ РОБЕРТСА, СОБЕЛА, ПРЕВИТТА, ЛАПЛАСА. ОПЕРАТОР МАРРА. ОБЩИЙ ПОДХОД К ЗАДАЧЕ ДИФФЕРЕНЦИРОВАНИЯ ЦИФРОВОГО ИЗОБРАЖЕНИЯ. РЕГУЛЯРИЗАЦИЯ. ОПТИМАЛЬНЫЕ ОПЕРАТОРЫ ВЫДЕЛЕНИЯ КОНТУРОВ.

СЕГМЕНТАЦИЯ ИЗОБРАЖЕНИЙ. ВЫДЕЛЕНИЕ ОБЛАСТЕЙ. КРИТЕРИИ ОДНОРОДНОСТИ. ГИСТОГРАММНАЯ СЕГМЕНТАЦИЯ.СЕГМЕНТАЦИЯ ПО ЦВЕТУ.МЕТОДЫ СЛИЯНИЯ/РАЗБИЕНИЯ.

Задача выделения контурных точек

Выделение контурных точек на бинарном изображении – задача вполне тривиальная. Здесь контурной точкой является любая точка, такая что в ее ближайшей окрестности (среди ее ближайших соседей) имеется хотя бы одна точка, значение которой отличается от значения данной точки.

Рассмотрим задачу выделения краев на полутоновом изображении. Пусть полутоновое изображение представляет собой двумерную функцию яркости (интенсивности сигнала) f(x,y), определенную на ограниченной прямоугольной области X, называемой «кадром». Традиционно рассматриваются две модели «края»: «ступенька» и «излом». «Ступенька» предполагает скачкообразное изменение яркости вдоль некоторого контура на изображении. Точки контура типа «ступенька» являются, таким образом, точками разрыва для функции f(x,y).Край типа «излом» – это совокупность точек разрыва первой производной функции f(x,y). Если же считать, что функция яркости непрерывна и два раза непрерывно дифференцируема во всех своих точках, то «ступенчатым» краевым точкам соответствуют точки смены знака второй производной (максимума первой производной), а «изломным» краевым точкам – точки смены знака первой производной (локальные максимумы яркостной функции). Рис. 3.4.1. иллюстрирует эти идеи для случая одномерной функции (например, профиля строки или столбца).

@Рис. 3.4.1. Идея определения краевых перепадов интенсивности типа «ступенька»:

а) функция интенсивности на границе перепада; б) первая производная функции;

в) вторая производная функции.