2. Пространственная локализация. Кроме частотной локализации, базисные функции должны быть локальными и в пространстве. Необходимость в пространственной локализации. Преобразования возникает тогда, когда информация о местоположении деталей изображения является важнейшей. Эта локальность, однако, не должна быть «абсолютной», блочной, как при ДКП, так как это ведет к потере свойства локальности в частотной области.
Наиболее часто применяемый подход при анализе заключается в следующем: сигнал дискретизируется, затем выполняется ДПФ. В результате сначала сигнал раскладывается по базису единичного импульса, который не имеет частотной локальности, а затем по базису синусоид с четными и нечетными фазами, не имеющих пространственной локальности. Конечно, представление сигнала в частотной области исключительно важно для его анализа. Однако это не означает, что выбор функций импульса и синусоиды для решения этой задачи является наилучшим. Еще в 1946 году Д.Габор предложил класс линейных преобразований, которые обеспечивают локальность и в частотной, и во временной области. Базис единичного импульса и базис синусоиды могут рассматриваться как два экстремальных случая этих преобразований. Вейвлеты являются еще одним примером функций, хорошо локализованных в пространственной и частотной областях.
3. Ортогональность. Преобразование не обязательно должно быть ортогональным. Так, ортогональность обычно не рассматривается в контексте субполосного кодирования, хотя вейвлет как правило, является ортогональным. Ортогональность функций упрощает многие вычисления. Кроме того «сильно» неортогональное преобразование может быть неприемлемо для кодирования.
4. Быстрые алгоритмы вычисления. Это, наверное, наиболее важное свойство. Так как невозможность практической реализации преобразования в реальном масштабе времени сводит на нет все его положительные свойства.
2. ПРИМЕНЕНИЕ ВЕЙВЛЕТ – ПРЕОБРАЗОВАНИЯ ДЛЯ СЖАТИЯ ИЗОБРАЖЕНИЯ
В последнее десятилетие в мире наблюдается значительный интерес к сжатию изображений. Это вызвано стремительным развитием вычислительной техники, графических мониторов, цветных принтеров, а также цифровой техники связи. Изображение представляется в цифровом виде достаточно большим количеством бит. Так, цветная картинка размером 512х512 требует для своего хранения 768 кБайт. Если передавать видеопоследовательность таких картинок со скоростью 25 кадров в секунду, требуемая скорость составит 188.7 Мбит / с.
Различают сжатие изображений без потерь и с потерями. Первое характеризуется незначительными коэффициентами сжатия (от 3 до 5 раз) и находит применение в телевидении, медицине, аэрофотосъемке и других приложениях. При сжатии изображения с допустимыми потерями коэффициент сжатия может достигать сотен раз. Популярность вейвлет – приобразования (ВП) во многом объясняется тем, что оно успешно может использоваться для сжатия изображения как без потерь, так и с потерями. Так, коэффициент сжатия видеосигнала в видеокодеках семейства ADV6xx варьируется от 3 до 350 и больше раз.
Причин успешного применения несколько.
1. Известно, что вейвлет - хорошо аппроксимирует преобразование Карунена - для фрактальных сигналов, к которым относятся и изображения.
2. Дисперсии коэффициентов субполос ортонормального вейвлет – приобразования распределены в широком диапазоне значений. Пусть дисперсии кодируются простым энтропийным кодером. Тогда стоимость кодирования всего изображения есть сумма кодирования субполос. Различные энтропии субполос приведут к стоимости кодирования значительно меньшей, чем при непосредственном кодировании изображения.
3. В результате этого перераспределения дисперсий коэффициенты вейвлет - имеют существенно негауссовскую статистику и, таким образом, меньшую энтропию, чем гауссовский сигнал той же дисперсии.
4.Наконец, коэффициенты вейвлет - имеют регулярные пространственно-частотные зависимости, которые с успехом используются в ряде алгоритмов кодирования.
Рассмотрим основные проблемы, возникающие при сжатии изображения при помощи вейвлет – приобразования и возможные пути их решения.
2.1. Базовый вейвлет – кодер изображения
Вейвлет – кодер изображения устроен так же, как и любой другой кодер с преобразованием. Назовем такой кодер базовым. Он состоит из трех основных частей: декоррелирующее преобразование, процедура квантования и энтропийное кодирование. В настоящее время во всем мире проводятся исследования по усовершенствованию всех трех компонент базового кодера.
2.1.1. Выбор вейвлетов для сжатия изображения
Выбор оптимального базиса вейвлетов для кодирования изображения является трудной и вряд ли решаемой задачей. Известен ряд критериев построения «хороших» вейвлетов, среди которых наиболее важными являются: гладкость, точность аппроксимации, величина области определения, частотная избирательность фильтра. Тем не менее, наилучшая комбинация этих свойств неизвестна.
Простейшим видом вейвлет – базиса для изображений является разделимый базис, получаемый сжатием и растяжением одномерных вейвлетов. Использование разделимого преобразования сводит проблему поиска эффективного базиса к одномерному случаю, и почти все известные на сегодняшний день кодеры используют его. Однако неразделимые базисы могут быть более эффективными, чем разделимые.
Прототипами базисных функций для разделимого преобразования являются функции ф(х)ф(у), ф(х)(у), (х)ф(у) и (х)(у). На каждом шаге преобразования выполняется два разбиения по частоте, а не одно. Предположим, имеем изображение размером N х N. Сначала каждая из N строк изображения делится на низкочастотную и высокочастотную половины. Получается два изображения размерами N × N / 2. Далее, каждый столбец делится аналогичным образом. В результате получается четыре изображения размерами N / 2 × N / 2: низкочастотное по горизонтали и вертикали, высокочастотное по горизонтали и вертикали, низкочастотное по горизонтали и высокочастотное по вертикали и высокочастотное по горизонтали и низкочастотное по вертикали.
Известно, что для кодирования изображений хорошо подходят сплайновые вейвлеты. Эксперименты, проведенные рядом исследователей, показывают важность гладкости базисных функций для сжатия. Практически столь же большое значение имеет число нулевых моментов вейвлетов, которое тесно связано с гладкостью. Несмотря на это, некоторые исследователи считают, что важность гладкости для приложений цифровой обработки сигналов остается открытым вопросом. Наиболее широко на практике используют базисы, имеющие от одной до двух непрерывных производных. Увеличение гладкости не приводит к увеличению эффективности кодирования.
Д.Вилласенор систематически протестировал все биортогональные блоки фильтров минимального порядка с длиной фильтров <=36. В дополнение к вышеперечисленным критериям учитывалась также чувствительность аппроксимации с низким разрешением к сдвигам функции f(x). Наилучшим фильтром, найденным в этих экспериментах, оказался сплайновый фильтр 7/9. Этот фильтр наиболее часто используется в вейвлет - изображений. В частности, в видеокодеках семейства ADV6xx применяются именно эти фильтры.
Необходимо сделать одно замечание относительно этих результатов. Д.Вилласенор сравнивал пиковое отношение сигнал/шум, получаемое при использовании различных фильтров в простой схеме кодирования. Алгоритм размещения бит, применяемый им, хорошо работает с ортогональными базисами. В случае биортогональных фильтров должен применяться другой, более эффективный алгоритм. В силу этой причины некоторые заслуживающие внимания биортогональные фильтры были им обойдены.
Для биортогонального преобразования квадрат ошибки в области преобразования не равен квадрату ошибки в восстановленном изображении. В результате проблема минимизации ошибки становится намного более трудной, чем в ортогональном случае. Можно уменьшить ошибку в области изображения путем применения схемы взвешенного распределения бит. Тогда целый ряд фильтров по своей эффективности становится равным фильтру 7/9. Один из таких базисов – интерполирующий вейвлет Деслаури – Дубук порядка 4, преимуществом которого является то, что коэффициенты фильтра - рациональные числа, кратные степени 2. Оба этих вейвлета имеют 4 нулевых момента и две непрерывные производные.
Семейство многообещающих фильтров было разработано И.Баласингамом и Т.Рамстадом. Процедура разработки заключалась в комбинировании классических методов разработки фильтров с идеями теории вейвлетов. Получившиеся фильтры значительно превосходят популярные фильтры 7/9.
2.1.2. Осуществление преобразования на границах изображения
Для эффективного сжатия необходимо тщательно обрабатывать границы изображения. Альтернативным методом является конструирование граничных фильтров, сохраняющих ортогональность преобразования вблизи границы. Проблеме конструирования граничных фильтров посвящен ряд статей Е.Ковачевич. При применении лифтинговой схемы границы учитываются автоматически.