Задачи поиска по образцу

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:29, 19 декабря 2016.

Содержание

Постановка задачи

Обоснование необходимости разработки программного средства для решения задачи поиска по образцу

Введение

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

Определение исходных данных

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

Критерии надежности и качества алгоритма распознаваний

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


Теоретическое обоснование постановки задачи

Определение структуры входных и выходных данных

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

Распознавание образов

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


Классификация по форме

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

Поиск по шаблону

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

Рис. 1. Обход картинки шаблоном
Рис. 2. Определение вероятного местоположения

Техника расчета характеристики может быть различна. Чаще всего используется среднеквадратичная разность значений яркости изображений шаблона и анализируемого кадра.

Недостатком этого метода является его ресурсоемкость. Требуется неоднократное непоследовательное обращение к одним и тем же фрагментам памяти изображения. К тому же, изображение шаблона не является динамически масштабируемым – то есть, если объект в кадре несколько меньше или больше шаблонного – он, скорее всего не будет выделен. Решением данной проблемы может быть поиск объектов по аналитической зависимости, описывающей их форму. [11]

Поиск по аналитическому описанию формы

Распространена практика поиска объектов по форме, имеющей аналитическое описание. Например, эллипс (или его частный случай – окружность) могут быть описаны несложной формулой из курса аналитической геометрии.

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

Рис. 3. Вписывание эллипса в совокупность точек

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

Классификация по положению

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

Классификация по цвету

Многие объекты можно классифицировать в зависимости от их цвета: они либо постоянно имеют определенную окраску, либо в некоторые моменты их окраска может быть регламентирована достаточно четко. Более того, в связи с тем, что существует множество базисов представления цветовых компонент (RGB, YUV, YCrCb, HSV и т.д.), нередки случаи, когда в том или ином базисе данный объект можно классифицировать практически безошибочно. Однако информация о том, какой базис использовать и как лучше организовать поиск объекта, имея в распоряжении изображение в данном базисе, зачастую может быть получена исключительно экспериментальным путем.

Базовые положения теории распознавания образов

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

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

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

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

Обучением обычно называют процесс выработки в некоторой системе той или иной реакции на группы внешних идентичных сигналов путем многократного воздействия на систему внешней корректировки. Такую внешнюю корректировку в обучении принято называть «поощрениями» и «наказаниями». Механизм генерации этой корректировки практически полностью определяет алгоритм обучения. Самообучение отличается от обучения тем, что здесь дополнительная информация о верности реакции системе не сообщается.

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

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

Примеры задач распознавания образов:

  • pаспознавание букв;
  • pаспознавание штрих-кодов;
  • pаспознавание автомобильных номеров;
  • pаспознавание лиц и других биометрических данных;
  • pаспознавание изображений;
  • pаспознавание речи.

Методы распознавания образов

В целом, можно выделить следующие методы распознавания образов:

  • Метод перебора. В этом случае производится сравнение с базой данных, где для каждого вида объектов представлены всевозможные модификации отображения. Например, для оптического распознавания образов можно применить метод перебора вида объекта под различными углами, масштабами, смещениями, деформациями и т. д. Для букв нужно перебирать шрифт, свойства шрифта и т. д. В случае распознавания звуковых образов, соответственно, происходит сравнение с некоторыми известными шаблонами (например, слово, произнесенное несколькими людьми).
  • Второй подход - производится более глубокий анализ характеристик образа. В случае оптического распознавания это может быть определение различных геометрических характеристик. Звуковой образец в этом случае подвергается частотному, амплитудному анализу и т. д.
  • Следующий метод - использование искусственных нейронных сетей (ИНС). Этот метод требует либо большого количества примеров задачи распознавания при обучении, либо специальной структуры нейронной сети, учитывающей специфику данной задачи. Тем не менее, его отличает более высокая эффективность и производительность. [10].
  • Экспертный метод, основанный на непрерывном обучении экспертной системы в процессе эксплатации.

Персептрон как метод распознавания образов

Ф. Розенблатт, вводя понятие о модели мозга, задача которой состоит в том, чтобы показать, как в некоторой физической системе, структура и функциональные свойства которой известны, могут возникать психологические явления - описал простейшие эксперименты по различению. Данные эксперименты целиком относятся к методам распознавания образов, но отличаются тем, что алгоритм решения не детерминированный. Простейший эксперимент, на основе которого можно получить психологически значимую информацию о некоторой системе, сводится к тому, что модели предъявляются два различных стимула и требуется, чтобы она реагировала на них различным образом. Целью такого эксперимента может быть исследование возможности их спонтанного различения системой при отсутствии вмешательства со стороны экспериментатора, или, наоборот, изучение принудительного различения, при котором экспериментатор стремится обучить систему проводить требуемую классификацию. В опыте с обучением персептрону обычно предъявляется некоторая последовательность образов, в которую входят представители каждого из классов, подлежащих различению. В соответствии с некоторым правилом модификации памяти правильный выбор реакции подкрепляется. Затем персептрону предъявляется контрольный стимул и определяется вероятность получения правильной реакции для стимулов данного класса. В зависимости от того, совпадает или не совпадает выбранный контрольный стимул с одним из образов, которые использовались в обучающей последовательности, получают различные результаты: 1. Если контрольный стимул не совпадает ни с одним из обучающих стимулов, то эксперимент связан не только с чистым различением, но включает в себя и элементы обобщения. 2. Если контрольный стимул возбуждает некоторый набор сенсорных элементов, совершенно отличных от тех элементов, которые активизировались при воздействии ранее предъявленных стимулов того же класса, то эксперимент является исследованием чистого обобщения. Персептроны не обладают способностью к чистому обобщению, но они вполне удовлетворительно функционируют в экспериментах по различению, особенно если контрольный стимул достаточно близко совпадает с одним из образов, относительно которых персептрон уже накопил определенный опыт.

Общая характеристика задач распознавания образов и их типы

Общая структура системы распознавания и этапы в процессе ее разработки показаны на рис. 4.

Рис. 4. Пример структуры системы распознавания

Задачи распознавания — это информационные задачи, состоящие из двух этапов:

  • преобразование исходных данных к виду, удобному для распознавания;
  • собственно распознавание (указание принадлежности объекта определенному классу).

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

Выделяют следующие типы задач распознавания:

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

Распознавание образов, научное направление, связанное с разработкой принципов и построением систем, предназначенных для определения принадлежности данного объекта к одному из заранее выделенных классов объектов. Под объектами в распознавания образов понимают различные предметы, явления, процессы, ситуации, сигналы. Каждый объект описывается совокупностью основных характеристик (признаков, свойств) , где -я координата вектора определяет значения -й характеристики, и дополнительной характеристикой , которая указывает на принадлежность объекта к некоторому классу (образу). Набор заранее расклассифицированных объектов, т. е. таких, у которых известны характеристики и , используется для обнаружения закономерных связей между значениями этих характеристик, и поэтому называются обучающей выборкой. Те объекты, у которых характеристика неизвестна, образуют контрольную выборку. Отдельные объекты обучающей и контрольной выборок называются реализациями. Одна из основных задач Распознавания образов — выбор правила (решающей функции) , в соответствии с которым по значению контрольной реализации устанавливается её принадлежность к одному из образов, т. е. указываются «наиболее правдоподобные» значения характеристики для данного . [11]

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

Проблема распознавания образов тесно связана с задачей предварительной классификации, или таксономией.

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

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

В 60-х гг. 20 в. в связи с развитием, электронной техники, в частности ЭВМ, широкое применение получили автоматические системы распознавания. Под системами распознавания обычно понимают комплексы средств, предназначенных для решения описанных выше, задач. Методы Распознавания образов используются в процессе машинной диагностики различных заболеваний, для прогнозирования полезных ископаемых в геологии, для анализа экономических и социальных процессов, в психологии, криминалистике, лингвистике, океанологии, химии, ядерной и космической физике, в автоматизированных системах управления и т.д. Их применение оправдано практически всюду, где приходится иметь дело с классификацией экспериментальных данных.

Одним из способов решения задачи распознавания образов является использование спектральных методов.

Спектральные методы

Преобразование Фурье

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

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

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

На практике ряд Фурье ограничивается определенным количеством членов . Ограничение числа членов ряда значением означает аппроксимацию бесконечномерного сигнала –мерной системой базисных функций спектра сигнала с определенной погрешностью в зависимости от фактического спектра сигнала. Ряд Фурье равномерно сходится к по норме:

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

Разложение в ряд Фурье произвольной функции корректно, если функция принадлежит этому же пространству , т.е. квадратично интегрируема:

при этом она может быть периодически расширена и определена на всей временной оси пространства ; так, что:

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

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

Оконное преобразование Фурье

Частичным выходом из этой ситуации является оконное преобразование Фурье с движущейся по сигналу оконной функцией, имеющей компактный носитель. Временной интервал сигнала при большой его длительности разделяется на подынтервалы, и преобразование Фурье выполняется последовательно для каждого подынтервала в отдельности. Тем самым осуществляется переход к частотно-временному (частотно-координатному) представлению сигналов, при этом в пределах каждого подынтервала сигнал «считается» стационарным. Результатом оконного преобразования является семейство спектров, которым отображается изменение спектра сигнала по интервалам сдвига окна преобразования. Это в какой-то мере позволяет выделять на координатной оси и анализировать особенности нестационарных сигналов. Размер носителя оконной функции обычно устанавливается соизмеримым с интервалом стационарности сигнала. По существу, таким преобразованием один нелокализованный базис разбивается на определенное количество базисов, локализованных в пределах функции , что позволяет представлять результат преобразования в виде функции двух переменных - частоты и временного положения окна. При этом размер стационарности сигнала необходимо знать априори.

Оконное преобразование выполняется в соответствии с выражением:

Функция представляет собой функцию (в общем случае – комплексную) окна сдвига преобразования по координате , где параметром задаются фиксированные значения сдвига. При сдвиге окон с равномерным шагом значения принимаются равными . В качестве окна преобразования может использоваться как простейшее прямоугольное окно ( в пределах окна и за его границами), так и специальные весовые окна (Бартлетта, Гаусса, Кайзера и пр.), обеспечивающие малые искажения спектра за счет граничных условий вырезки оконных отрезков сигналов и нейтрализующие явление Гиббса. При этом для каждого положения окна на временной оси сигнала вычисляется свой комплексный спектр. Эффективная ширина оконной функции сохраняется постоянной по всему интервалу сигнала. [7]

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

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

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

Методические ошибки преобразования Фурье

При обработке данных с помощью ЭВМ значения функции обычно заданы на дискретном множестве равноотстоящих точек. Интервал дискретизации (или квантования) равен, например, шагу разностной сетки, если значения функции в точках получены с помощью численного интегрирования уравнений, определяющих . В другой ситуации равно характерному времени срабатывания аналого-цифрового преобразователя сигналов (сокращённо АЦП) на входе системы сбора данных и т.д. В дискретном случае интегралы в выражениях для коэффициентов рядов следует заменить суммами. Предположим, что интервал определения разбит на частей Вычисления сильно упрощаются тем обстоятельством, что Фурье-гармоники оказываются ортогональными и на дискретном множестве точек. При вычислении ДПФ с помощью ЭВМ всегда имеют дело с массивом дискретных отсчётов (конечная выборка). При этом вынужденно предполагают, что этот массив содержит один или несколько периодов обрабатываемого сигнала . Конечность интервала выборки (временное ограничение) и дискретизация непрерывного сигнала приводят к неожиданным эффектам, рассмотренным ниже.

Влияние конечности выборки

Ограничение по времени, возникающее при обработке конечного массива отсчётов сигнала длиной , эквивалентно умножению сигнала на прямоугольный импульс:

Поэтому вместо исходной функции мы наблюдаем функцию . В соответствии с теоремой о свёртке преобразование Фурье этой функции есть

т.е. «обрезание» по времени сигнала эквивалентно свёртке его Фурье-преобразования с весовой функцией . Это означает, что каждый резкий пик на какой-либо частоте в Фурье-спектре функции «размывается» в функцию (см.рис.5) в спектре .

Рис. 5. "Размытие" резких пиков функции на определенной частоте

Её «ширина» - расстояние до первого нуля – порядка . Таким образом, чем больше время наблюдения сигнала , тем выше разрешающая способность Фурье-обработки. Превращение -функций в функцию из-за конечности выборки означает также уменьшение «энергии» Фурье-гармоник в центральном пике за счёт перетекания её в боковые максимумы функции (различные английские обозначения этого эффекта - leakage, ripples, side lobes). Для уменьшения искажений, связанных с конечностью выборки, при одном и том же Т необходимо в качестве весовых функций брать «окна» Ганна или Хэмминга:




Дискретизация сигнала и паразитные гармоники

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


Иными словами, при квантовании с шагом предельная допустимая частота (частота Найквиста - Котельникова) есть . Конечный размер выборки приводит, соответственно, к появлению минимально возможной частоты .

Дискретизация по времени приводит к появлению паразитных гармоник (к так называемому «элайзингу» - aliasing). Действительно, пусть в частотном спектре непрерывного сигнала имеется максимум («пик») на частоте . Тогда из-за симметрии и периодичности тригонометрических функций он появится для квантованных сигналов на частотах

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

Квантование по частоте и эффект «частокола»

Запишем выражения для дискретного преобразования Фурье с помощью комплексных экспонент



Оно применимо к дискретным и периодическим сигналам (предполагаем, что массив -отсчётов представляет собой период функции ). Соответственно частотный спектр должен быть также периодическим и дискретным. Квантование по частоте приводит к новому явлению: так называемому «эффекту частокола». Если в спектре непрерывного сигнала есть острый «пик», то его положение, вообще говоря, может не совпасть с какой-либо из разрешённых квантованных частот. Разрешённые частоты и образуют «частокол» (более строго, систему дискретных частотных фильтров), через который мы наблюдаем исходный спектр. «Негармонические» пики будут вносить вклад в значения амплитуд близких разрешённых Фурье-гармоник. Величина погрешности при определении амплитуд пиков, не совпадающих с разрешёнными, определяется степенью перекрытия соседних фильтров. При вычислении ДПФ мы имеем дело с конечной выборкой длиной . Для прямоугольного окна конечность выборки приводит к размытию в ; для окна Хэмминга характерный размер Фурье-преобразования больше в два раза и, соответственно, больше величина перекрытия соседних фильтров. Другими словами, использование окна Хэмминга при Фурье-обработке уменьшает эффект частокола наряду с эффектами «пролезания энергии в боковые лепестки».

Принцип вейвлет-преобразования

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

Рис. 6. Функции вейвлетов и спектр.

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

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

Для упрощения дальнейших выкладок значения переменных и примем целочисленными. При приведении функции к единичной норме, получаем:
Если для семейства функций выполняется условие ортогональности:

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

где коэффициенты представления сигнала – проекции сигнала на новый ортогональный базис функций, как и в преобразовании Фурье, определяются скалярным произведением
при этом ряд равномерно сходится, то есть

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

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

Рис. 7. Функции Хаара.

Определение вейвлета

В общем случае к вейвлетам относятся локализованные функции, которые конструируются из одного материнского вейвлета (или по любой другой независимой переменной) путем операций сдвига по времени и изменения временного масштаба :

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

Непрерывное (интегральное) вейвлет-преобразование сигнала , которое применяется для качественного частотно-временного анализа, по смыслу соответствует преобразованию Фурье с заменой гармонического базиса на вейвлетный :

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

Рис. 8. Вейвлеты Mhat и Wave.

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

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

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


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

Свойства вейвлета

  • Локализация. Вейвлет должен быть непрерывным, интегрируемым, иметь компактный носитель и быть локализованным как во времени (в пространстве), так и по частоте. Если вейвлет в пространстве сужается, то его «средняя» (доминирующая) частота повышается, спектр вейвлета перемещается в область более высоких частот и расширяется. Этот процесс должен быть линейным – сужение вейвлета вдвое должно повышать его доминирующую частоту и ширину спектра также вдвое.
    Вейвлетную функцию можно считать достаточно хорошо локализованной при выполнении условий:

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

    Такие вейвлеты называются вейвлетами -го порядка.
  • Ограниченность. Необходимое и достаточное условие:

    Оценка хорошей ограниченности и локализации может выполняться с использованием выражений:
    , или
где – средняя частота вейвлета.

Число должно быть как можно больше.

  • Автомодельность базиса или самоподобие. Форма всех базисных вейвлетов должна быть подобна материнскому вейвлету , т.е. должна оставаться одной и той же при сдвигах и масштабировании (растяжении/сжатии), иметь одно и то же число осцилляций.

Отображение преобразования.

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

Спектр одномерного сигнала представляет собой поверхность в трехмерном пространстве. [8]

Вейвлетные функции

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

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

Вейвлетный спектр

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

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

Основы вейвлет-преобразования

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

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

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

Базисные функции вейвлет – преобразования

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

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


Свойства вейвлет – преобразования

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

  • линейность

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


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

    Определения и свойства одномерного непрерывного вейвлет-преобразования обобщаются на многомерный и на дискретный случаи. [7]

Идея вейвлет-преобразования

Рис. 10. Примеры материнских вейвлетов

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


т.е. ; также предполагается, что


Материнский вейвлет преобразовывается следующим образом:

где
В общем случае вейвлет - преобразование записывается так:

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

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

где

В алгоритме JPEG2000 используются вейвлеты Добеши.

В матричном виде для действия на вектор длины 8 данное преобразование задается так:


где:
, , , , , , , .

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

Обычно полагают либо , либо . Использование вейвлет-преобразований при сжатии изображений аналогично использованию дискретного косинус-преобразования в алгоритме JPEG, т.е. само преобразование - лишь ступень конвейера сжатия.

Вейвлет - преобразования имеют очень хорошую частотно-пространственную локализацию и по этому показателю превосходят традиционные косинус-преобразования и другие преобразования Фурье. Таким образом, становится возможным применять более сильное квантование, улучшая свойства последовательности для последующего сжатия без потерь. Алгоритмы сжатия изображений, основанные на этом преобразовании, при той же степени сжатия показывают лучшие результаты по сохранению качества изображения. К тому же вычислительная сложность очень низка и составляет (здесь - длина последовательности, к которой применяется преобразование). Однако распространенность форматов, использующих сжатие на основе вейвлет - преобразования, невелика из-за наличия патентов, а также из-за большой распространенности обычного JPEG, дающего вполне приемлемые результаты. [4]

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

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

Непрерывным вейвлет - преобразованием (или вейвлетным образом) функции называют функцию двух переменных:

,

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

Порождающими функциями могут быть самые различные функции с компактным носителем - ограниченные по времени и местоположению на временной оси, и имеющие спектральный образ, в определенной степени локализованный на частотной оси. Как и для рядов Фурье, базис пространства целесообразно конструировать из одной порождающей функции, норма которой должна быть равна 1. Для перекрытия локальной функцией вейвлета всей временной оси пространства используется операция сдвига (смещения по временной оси): , где значение для НВП также является величиной непрерывной. Для перекрытия всего частотного диапазона пространства используется операция временного масштабирования вейвлета с непрерывным изменением независимой переменной: . Если временной образ вейвлета будет расширяться (изменением значения параметра ), то его «средняя частота» будет понижаться, а частотный образ (частотная локализация) перемещаться на более низкие частоты. Таким образом, путем сдвига по независимой переменной вейвлет имеет возможность перемещаться по всей числовой оси произвольного сигнала, а путем изменения масштабной переменной (в фиксированной точке временной оси) «просматривать» частотный спектр сигнала по определенному интервалу окрестностей этой точки.

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

где
.

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

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

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

Затем вейвлет масштаба сдвигается вправо на значение и процедура повторяется. Получаем значение, соответствующее в строке на частотно-временном плане. Процедура повторяется до тех пор, пока вейвлет не достигнет конца сигнала. Таким образом получаем строку точек на масштабно-временном плане для масштаба а=1\!.

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

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

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

Дискретное вейвлет – преобразование

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

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

где
пространство целых чисел
, параметр масштаба,
параметр сдвига.

Базис пространства в дискретном представлении:

Вейвлет-коэффициенты прямого преобразования:

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

Обратное дискретное преобразование для непрерывных сигналов при нормированном ортогональном вейвлетном базисе пространства:

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

Устойчивость дискретного базиса определяется следующим образом.

Функция . называется -функцией, если базис на ее основе является базисом Рисса (Riesz). Для базиса Рисса существуют значения и , для которых выполняется соотношение
,
если энергия ряда конечна. При этом для любой -функции существует базис , который ортогонален базису . Его называют ортогональным «двойником» базиса , таким, что:

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

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

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

где
скейлин-коэффициенты, которые обычно называют коэффициентами аппроксимации сигнала,
– вейвлет-коэффициенты или коэффициенты детализации.

Частотно-временная локализация вейвлет-анализа

Реальные сигналы, как правило, конечны и принадлежат пространству . Частотный спектр сигналов обратно пропорционален их длительности. Соответственно, достаточно точный низкочастотный анализ сигналов должен производиться на больших интервалах его задания, а высокочастотный – на малых. Если частотный состав сигнала претерпевает существенные изменения на интервале его задания, то преобразование Фурье дает только усредненные данные частотного состава сигнала с постоянным частотным разрешением. Определенная частотно-временная локализация анализа создается применением оконного преобразования Фурье, что дает семейства частотных спектров, локализованных во времени, но в пределах постоянной ширины окна оконной функции, а, следовательно, также с постоянным значением и частотного, и временного разрешения.

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

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

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

Рис. 11 Частотно-временные окна преобразования

Если по этим функциям определить центры и радиусы вейвлетов и их фурье-образов, то временная локализация происходит с центрами окон шириной ,а частотная – с центрами , и с шириной окна . При этом значение отношения центральной частоты к ширине окна не зависит от местоположения центральной частоты. Частотно-временное окно сужается при высокой центральной частоте, и расширяется при низкой. Схематическое изображение частотно-временных окон преобразования приведено на рис. 11. Таким образом, на высоких частотах лучше разрешение по времени, а на низких - по частоте. Для высокочастотной компоненты сигнала можно точнее указать ее временную позицию, а для низкочастотной - ее значение частоты.


Изменение частотно-временного окна вейвлета определяет угол влияния значений функции в произвольных точках на значения коэффициентов . И наоборот, угол влияния из точки на ось определяет интервал значений функции, которые принимают участие в вычислении данного коэффициента – область достоверности. Схематически это показано на рис. 12.


Рис. 12 Угол влияния значений функции

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

Образное представление преобразования

Представим себе длинный и узкий стеклянный ларь, произвольно заполненный шарами трех разных диаметров: 5, 10 и 15 см. Взглянем на ларь сбоку, и линию высоты насыпки будем считать значением сигнала в зависимости от расстояния от одного из торцов ларя (условно – нулевого).

Возьмем первый «вейвлет» – идеальное дифференциальное сито с диаметром отверстий d=5 см, через которое проходят только пятисантиметровые шары (аналог значения ). Передвигаясь вдоль ларя, «просеем» через это сито шары в ларе, не перемешивая их по расстоянию от нулевого торца ларя и размещая отсеиваемые шары в таком же ларе, сохраняя расстояние от начала ларя. Сменим масштаб «вейвлета» и повторим эту операцию ситом с диаметром отверстий 10, а затем 15 см. Если все три ларя расположить радом, мы получим двумерную «поверхность» насыпки отсеянных шаров, которая наглядно покажет распределение шаров в ларе и по размерам, и по их концентрации в различных участках ларя.

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

Один уровень дискретного вейвлет - преобразования

ДВП сигнала получают применением набора фильтров. Сначала сигнал пропускается через низкочастотный (low-pass) фильтр с импульсным откликом , и получается свёртка:

Одновременно сигнал раскладывается с помощью высокочастотного (high-pass) фильтра . В результате получаются детализирующие коэффициенты (после ВЧ-фильтра) и коэффициенты аппроксимации (после НЧ-фильтра). Эти два фильтра связаны между собой и называются квадратурными зеркальными фильтрами (QMF).

Так как половина частотного диапазона сигнала была отфильтрована, то, согласно теореме Котельникова (если аналоговый сигнал имеет спектр, ограниченный частотой , то он может быть однозначно и без потерь восстановлен по своим дискретным отсчётам, взятым с частотой: , где — верхняя частота в спектре, или, по-другому, по отсчётам, взятым с периодом: Tдискр≤1/(2·Fmax), отсчёты сигналов можно проредить в 2 раза:

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

Рис. 13. Схема разложения сигнала в ДВП

С помощью оператора прореживания

вышеупомянутые суммы можно записать короче:


Вычисление полной свёртки с последующим прореживанием — это излишняя трата вычислительных ресурсов.

Схема лифтинга является оптимизацией, основанной на чередовании этих двух вычислений. [1]

Каскадирование и банки фильтров

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

Рис. 14. Трехуровневый банк (гребенка) фильтров

На каждом уровне вышеприведённой диаграммы сигнал раскладывается на низкие и высокие частоты. В силу двукратного прореживания, длина сигнала должна быть кратна , где — число уровней разложения. [7]

Например, для сигнала из 32 отсчётов с частотным диапазоном от до трёхуровневое разложение даст 4 выходных сигнала в разных масштабах:

Таблица 1. Выходные сигналы трехуровневого разложения
Уровень Частоты

Длина сигнала

3 0...fn/8 4
fn/8...fn/4 4
2 fn/4...fn/2 8
1 fn/2...fn 16


Рис. 15. Представление ДВП в частотной области


Алгоритм вейвлет – преобразования

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

Для работы с дискретными изображениями используется вариант вейвлет-преобразования, известный как алгоритм Малла, названный в честь его изобретателя Стефана Малла́. Исходное изображение раскладывается на две составляющие — высокочастотные детали (состоящие в основном из резких перепадов яркости), и сглаженную уменьшенную версию оригинала. Это достигается применением пары фильтров, причём каждая из полученных составляющих вдвое меньше исходного изображения. Как правило, используются фильтры с конечным импульсным откликом, в которых пиксели, попавшие в небольшое «окно», умножаются на заданный набор коэффициентов, полученные значения суммируются, и окно сдвигается для расчёта следующего значения на выходе.

Поскольку изображения двумерны, фильтрация производится и по вертикали, и по горизонтали. Этот процесс повторяется многократно, причём каждый раз в качестве входа используется сглаженная версия с предыдущего шага. Так как изображения «деталей» состоят обычно из набора резких границ, и содержат обширные участки где интенсивность близка к нулю. Если допустимо пренебречь некоторым количеством мелких деталей, то все эти значения можно просто обнулить. В результате получается версия исходного изображения, хорошо поддающаяся сжатию. Для восстановления оригинала снова применяется алгоритм Малла, но с парой фильтров, обратной к исходным.

Алгоритмы JPEG и MPEG, в отличие от вейвлетного, сжимают по отдельности каждый блок исходного изображения размером 8 на 8 пикселов. В результате, за счёт потери данных при сжатии, на восстановленном изображении может быть заметна блочная структура. При вейвлетном сжатии такой проблемы не возникает, но могут появляться искажения другого типа, имеющие вид «призрачной» ряби вблизи резких границ. Считается, что такие артефакты в среднем меньше бросаются в глаза наблюдателю, чем «квадратики», создаваемые JPEG.

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

На основе частотного подхода к ВП прямое ВП изображения происходит следующим образом.

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

Рис. 16. Результат вейвлет-преобразования изображения

На рис. 17 даны реальное изображение (слева) и результат первого уровня его вейвлет-анализа, т.е. четыре изображения (слева направо, сверху вниз): НЧНЧ1, ВЧНЧ1, НЧВЧ1 и ВЧВЧ1. [6]

Рис. 17. Пример вейвлет-преобразования изображения.

Любую упорядоченную последовательность данных, заданную аналитически (в виде некоторой функции) или перечислением ее значений, будем называть сигналом. Значение сигнала может зависеть от одного параметра (например, от времени) или от нескольких. Например, фотографическое изображение можно считать двумерным сигналом, значением которого является яркость каждой точки изображения, а параметрами – координаты точки по горизонтали и по вертикали. При цифровой обработке сигнала над ним обычно выполняют некоторое преобразование, выявляющее характерные особенности данного сигнала и, выполнив определенные действия (например, подавление шума), делают обратное преобразование. Классическим примером является преобразование Фурье, переводящее сигнал из временной области в частотную и обратно. Преобразование, как прямое, так и обратное, рассчитывается путем вычисления свертки сигнала в каждой его точке с некоторой функцией, называемой фильтром. В дискретном случае фильтры задаются просто перечислением их значений (коэффициентов) в точках дискретизации. Учитывая статистические особенности большинства сигналов (полезная информация расположена в низкочастотной области спектра сигнала, а помехи или шум – в высокочастотной), сигнал обычно преобразуют с использованием двух дополняющих друг друга фильтров – низких и высоких частот. Вейвлеты, относятся к классу квадратурных зеркальных фильтров (КЗФ). Особенностью этого класса фильтров является то, что фильтр высоких частот получается из соответствующего фильтра низких частот простой перестановкой его коэффициентов в обратном порядке и изменением знака половины из них (только четных или только нечетных). При этом вейвлет выделяет локальные особенности сигнала в каждой точке и является, таким образом, фильтром высоких частот, а соответствующий фильтр низких частот описывается так называемой масштабирующей функцией.

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

Таблица 2. Матрица процесса преобразования
C0 C1 C2 C3 0 0 ... 0 0 0 0 x F0
0 C0 C1 C2 C3 0 ... 0 0 0 0 F1
0 0 C0 C1 C2 C3 ... 0 0 0 0 F2
0 0 0 C0 C1 C2 ... 0 0 0 0 F3
... ... ... ... ... ... ... ... ... ... ... ...
0 0 0 0 0 0 ... C0 C1 C2 C3 Fn-3
C3 0 0 0 0 0 ... 0 C0 C1 C2 Fn-2
C2 C3 0 0 0 0 ... 0 0 C0 C1 Fn-1
C1 C2 C3 0 0 0 ... 0 0 0 C0 Fn

Здесь означают коэффициенты фильтра длиной 4, – значения отсчетов сигнала, символ – операция умножения матрицы на вектор. Коэффициенты в последних четырех строках матицы означают, что сигнал продолжается на всей числовую прямой периодическим образом (т.е. после значения снова идет значение ). В результате умножения матрицы размерностью на вектор длиной получается вектор такой же длины, а с учетом того, что в преобразовании участвуют два фильтра, даже два вектора длины вместо одного – казалось бы, никакого выигрыша мы не получили. Однако вейвлеты Добеши обладают следующим свойством: как сглаженное представление сигнала (т.е. обработанное масштабирующей функцией), так и его локальные особенности (полученные в результате вейвлет-преобразования) обладают избыточностью в два раза. Другими словами, для вейвлета длиной результат преобразования сигнала в каждой точке представляет собой некоторое «усреднение» сигнала и набор «деталей», отличающих исходный сигнал от усредненного – причем усредненный сигнал является в 2 раза «более гладким», чем исходный. Таким образом, каждый четный или каждый нечетный отсчет преобразования может быть исключен из рассмотрения, и в результате преобразования получаются два вектора вдвое меньшей длины, один из которых содержит сглаженную версию сигнала (или представление сигнала в половинном масштабе), а другой – набор локальных особенностей (то есть помехи на данном уровне детализации)! Что это дает? Во-первых, анализ сглаженного сигнала упрощает выявление его характерных свойств (например, нейросети гораздо лучше обучаются на сигналах, очищенных от шума, чем на зашумленных). Во-вторых, анализ локальных особенностей сигнала позволяет не только определить характер и параметры помех, но и четко локализовать «особые точки» сигнала – такие как выбросы, пропущенные значения, резкие скачки уровня и т.д. Более того, если полученный сигнал все еще недостаточно очищен от помех, мы можем повторно применить к нему вейвлет-преобразование и получить еще более гладкую версию сигнала (уже в четыре раза короче, чем исходный) и локальные особенности сигнала уже на следующем уровне детализации. [5]

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

Таблица 3. Матрица преобразования
C0 C1 C2 C3 0 0 ... 0 0 0 0 x F0
0 0 C0 C1 C2 C3 ... 0 0 0 0 F1
0 0 0 0 C0 C1 ... 0 0 0 0 F2
0 0 0 0 0 0 ... 0 0 0 0 F3
... ... ... ... ... ... ... ... ... ... ... ...
0 0 0 0 0 0 ... 0 0 0 0 Fn-3
0 0 0 0 0 0 ... C2 C3 0 0 Fn-2
0 0 0 0 0 0 ... C0 C1 C2 C3 Fn-1
C2 C3 0 0 0 0 ... 0 0 C0 C1 Fn


C3 -C2 -C1 -C0 0 0 ... 0 0 0 0 x F0
0 0 C3 -C2 C1 -C0 ... 0 0 0 0 F1
0 0 0 0 C3 -C2 ... 0 0 0 0 F2
0 0 0 0 0 0 ... 0 0 0 0 F3
... ... ... ... ... ... ... ... ... ... ... ...
0 0 0 0 0 0 ... 0 0 0 0 Fn-3
0 0 0 0 0 0 ... C1 -C0 0 0 Fn-2
0 0 0 0 0 0 ... C3 -C2 C1 -C0 Fn-1
C1 -C0 0 0 0 0 ... 0 0 C3 -C2 Fn


Для нахождения значений коэффициентов можно использовать следующие свойства вейвлетов Добеши:

  • cдвиги вейвлета образуют ортонормированный базис пространства, т.е. другими словами, при попарном перемножении строк матрицы преобразования, должен получиться 0, а при умножении строки на саму себя – 1. Свойство ортогонормированности базиса означает, что матрица обратного преобразования представляет собой просто транспонированную матрицу прямого преобразования.
  • вейвлет длиной ( – четное) имеет нулевых начальных моментов, т.е.

    Поскольку начальные моменты вейвлета инвариантны относительно сдвига вдоль его области определения, можно взять произвольные последовательные значения – например, . Количество нулевых моментов вейвлета означает, что если аппроксимировать исходный сигнал полиномиальными сплайнами степени , то вейвлет-преобразование «погасит» все полиномиальные составляющие степени от до (т.е. вейвлет-преобразование полинома определенной «гладкости» будет давать нулевой отклик).

Таким образом, для нахождения значений коэффициентов вейвлет-фильтра длиной 4, нужно решить систему из 4 алгебраических уравнений:

, где первые два условия являются условиями ортогональности, а остальные — нулевыми моментами. Решением этой системы являются следующие значения:
, , ,
или

С0 = 0.4829629131445341

С1 = 0.8365163037378097

C2 = 0.2241438680420134

C3 = –0.1294095225512604

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






Для выполнения обратного преобразования достаточно вычислить произведение транспонированных матриц коэффициентов на «сглаженный» вектор и вектор «деталей» соответственно и выполнить покомпонентное сложение результатов. Сдвиг коэффициентов в матрице на 2 означает в этом случае вставку нулей между отсчетами, при этом вектор длины дополняется до длины исходного вектора. [4.]

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

Для вычисления вейвлет-преобразования двумерного сигнала (например, изображения), представленного прямоугольной матрицей отсчетов, нужно вначале выполнить преобразование над каждой строкой исходной матрицы, а затем над каждым столбцом полученного результата (или наоборот). В результате получаются 4 матрицы, каждая высотой и шириной вдвое меньше исходной, соответствующих «сглаженному» изображению и наборам деталей по горизонтали, по вертикали и по диагонали соответственно. Аналогичным образом может быть выполнено и преобразование сигналов больших размерностей.

В результате первого уровня разложения изображений получают:

Рис. 18. Результат первого уровня разложения изображений.

– аппроксимирующие коэффициенты (в результате применения низкочастотного фильтра),

– горизонтальные детализирующие коэффициенты,

– вертикальные детализирующие коэффициенты,

– диагональные детализирующие коэффициенты (в результате применения высокочастотного фильтра).

Если сигнал имел размерность , то коэффициенты первого уровня разложения , , , будут иметь размерность . [1]

Поиск ведется по 20 максимальным детализирующим коэффициентам (горизонтальным, вертикальным и диагональным).


Обратное преобразование

Так как форма базисных функций зафиксирована, то вся информация о сигнале переносится на значения функции . Точность обратного интегрального вейвлет-преобразования зависит от выбора базисного вейвлета и способа построения базиса, т.е. от значений базисных параметров , . Строго теоретически вейвлет может считаться базисной функцией только в случае его ортонормированности. Для практических целей непрерывного преобразования часто бывает вполне достаточна устойчивость и «приблизительность» ортогональности системы разложения функций. Под устойчивостью понимается достаточно точная реконструкция произвольных сигналов. Для ортонормированных вейвлетов обратное вейвлет-преобразование записывается с помощью того же базиса, что и прямое:

где
- нормализующий коэффициент:

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

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

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

где индексом обозначен ортогональный «двойник» базиса , о котором будет изложено ниже.

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

Достоинства и недостатки вейвлетных преобразований

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

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

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

Рис. 19 Анализируемый сигнал

Однако базисы на основе непрерывных вейвлетов, как правило, не являются строго ортонормированными, поскольку элементы базиса бесконечно дифференцируемы и экспоненциально спадают на бесконечности. У дискретных вейвлетов эти проблемы легко снимаются, что обеспечивает более точную реконструкцию сигналов. [2]

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


Обоснование выбора вейвлет-преобразования в качестве ядра ПО

Результат преобразования Фурье – амплитудно-частотный спектр, по которому можно определить присутствие некоторой частоты в исследуемом сигнале.

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

Одним из таких методов является обобщенный метод Фурье (локальное преобразование Фурье). Этот метод состоит из следующих этапов:

  1. В исследуемой функции создается «окно» – временной интервал, для которого функция , и для остальных значений;
  2. Для этого «окна» вычисляется преобразование Фурье
  3. «Окно» сдвигается, и для него также вычисляется преобразование Фурье. «Пройдя» таким «окном» вдоль всего сигнала, получается некоторая трехмерная функция, зависящая от положения «окна» и частоты.

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

Вейвлетные базисы могут быть хорошо локализованными как по частоте, так и по времени.

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

Вейвлет - преобразование исключает методические ошибки преобразования Фурье и дает более точный результат.

Разработка структуры и алгоритма ПО для решения задачи поиска по образцу

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

Алгоритм ПО для решения задачи поиска по образцу

  • Выбор изображения для поиска.
  • Задание папки для поиска.
  • Выбор вейвлета и способа вывода изображения.
  • Поиск изображения.
  1. Вычисление коэффициентов двухмерного вейвлет - преобразования выбранного изображения, средние значения коэффициентов(M0) и СКО(S).
  2. Если выбран режим вывода изображений с ограничениями, то проверяются значения коэффициентов M (проверяемого изображения в папке); если хотя бы у одной разновидности M0-S>=M<=M0+S, то вычисляется средняя погрешность этих коэффициентов и коэффициентов исходного изображения. Если без ограничений - то средняя погрешность вычисляется у всех найденных изображений.
  3. Сортируется список найденных изображений по возрастанию погрешности.
  4. Выводится полученный список и первые два изображения с указанием меры близости.

Интерфейс ПО для решения задачи поиска по образцу

Для того, чтобы загрузить изображение, необходимо нажать кнопку «Исходное изображение». Для выбора папки, в которой будет осуществляться поиск по образцу, необходимо нажать кнопку «Папка для поиска» и выбрать папку. Для вывода всех изображений в папке с указанием погрешности, необходимо выбрать «Без ограничений», для вывода только тех изображений, погрешность коэффициентов которых находится в пределах СКО, необходимо выбрать «Ст. ограничения». Нажать кнопку «Поиск».

Результаты работы ПО для решения задачи поиска по образцу

Рис. 20. Пример поиска.
Рис. 21. Пример папки для поиска.

Если образец задан достаточно точно, то СКО меньше у вейвлетов с меньшим количеством коэффициентов (Добеши 4, Хаар).
На значение коэффициентов, а, следовательно, и на работу поиска, сильно влияют ракурс, размеры и формат исходного изображения.
При изменении ракурса, размеров объектов время поиска увеличивается (до 10%).

Рис. 22. Результат поиска.
Рис. 23. Результат поиска “простого” изображения.
Рис. 24. Пример поиска по образцу плохого качества.

Для таких случаев погрешность меньше при использовании вейвлетов с большим количеством коэффициентов.
Время поиска увеличивается с увеличением коэффициентов используемого фильтра. Т.е. время, затрачиваемое на поиск, вейвлетом Добеши 4 (4 коэффициента фильтра) больше на 10 %, чем время поиска при использовании вейвлета Хаара (при использовании Добеши 6 время увеличивается на 10% по сравнению с использованием вейвлета Добеши 4).