Вейвлет-преобразование: определение, применение, пример

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

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

Что такое цифровое изображение

Визуальная информация в компьютере представляется в виде чисел. Говоря простым языком, фото, сделанное цифровым аппаратом, представляет собой таблицу, в ячейки которой вписаны значения цвета каждого из его пикселей. Если речь идет о монохромном изображении, то их заменяют значениями яркости из отрезка [0, 1], где 0 используют для обозначения черного цвета, а 1 — белого. Остальные оттенки задаются дробными числами, но с ними неудобно работать, поэтому диапазон расширяют и значения выбирают из отрезка между 0 и 255. Почему именно из этого? Все просто! При таком выборе в двоичном представлении для кодирования яркости каждого пикселя требуется ровно 1 байт. Очевидно, что для хранения даже небольшого изображения требуется довольно много памяти. Например, фотография размером 256 х 256 пикселей займет 8 кБайт.

Несколько слов о методах сжатия изображений

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

К алгоритмам сжатия с потерями относятся:

  • JPEG. На данный момент это один из наиболее популярных алгоритмов. Он основан на применении дискретного косинусного преобразования. Справедливости ради нужно отметить, что существуют варианты JPEG, осуществляющие сжатие без потерь. К ним относятся Lossless JPEG и JPEG-LS.
  • JPEG 2000. Алгоритм используется на мобильных платформах и основан на применении дискретного вейвлет-преобразования.
  • Алгоритм фрактального сжатия. В некоторых случаях он позволяет получать изображения превосходного качества даже при сильном сжатии. Однако из-за проблем с патентованием этот метод продолжает оставаться экзотикой.

Без потерь сжатие осуществляют посредством алгоритмов:

  • RLE (используется в качестве основного метода в форматах TIFF, BMP, TGA).
  • LZW (применяется в формате GIF).
  • LZ-Huffman (используется для формата PNG).

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

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

Оно выглядит так:

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

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

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

Что такое вейвлет

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

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

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

Такой способ преобразования сигнала (функции) позволяет переводить его из временного в частотно-временное представление.

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

  • Если для некой функции ψ (t) Фурье-преобразование имеет вид

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

то должно выполняться условие:

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

Кроме того:

  • вейвлет должен обладать конечной энергией;
  • он должен быть интегрируемым, непрерывным и иметь компактный носитель;
  • вейвлет должен быть локализованным как по частоте, так и во времени (в пространстве).

Виды

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

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

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

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

Сначала нужно вспомнить, что у фотографий яркость соседних пикселей, как правило, отличается на небольшую величину. Если даже на реальных изображениях присутствуют участки с резкими, контрастными перепадами яркости, то они занимают только малую часть изображения. В качестве примера возьмем всем известное тестовое изображение Lenna в градациях серого. Если взять матрицу яркости его пикселей, то часть первой строки будет выглядеть как последовательность чисел 154, 155, 156, 157, 157, 157, 158, 156.

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

В результате получится последовательность: 154,1,1,1,0,0,1,-2.

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

Для преодоления этого недостатка числа делят на пары и для каждой находят полусумму (об. a) и полуразность (об. d), т. е. для (154,155),(156,157),(157,157),(158,156) имеем (154.5,0.5),(156.5,0.5),(157,0.0),(157,-1.0). В таком случае в любой момент можно найти значение обоих чисел в паре.

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

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

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

Сжатие

Как уже было сказано, одной из сфер применения вейвлет-преобразования является алгоритм JPEG 2000. Сжатие с использованием метода Хаара основано на переводе вектора из двух пикселей X и Y в вектор (X + Y)/2 и (X - Y)/2. Для этого достаточно умножить исходный вектор на матрицу, представленную ниже.

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

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

Фильтры

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

Теперь разберемся с тем, что показывают разности. Они «выделяют» межпиксельные «всплески», устраняя константную составляющую, т. е. «отфильтровывают» значения с низкими частотами.

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

Пример

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

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

Для увеличения степени сжатия можно применить преобразование Хаара несколько раз к низкочастотным данным.

Применение к двумерным массивам

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

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

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

Декодирование

Обратное преобразование в изображение производится по следующему алгоритму:

  • архив распаковывается;
  • применяется обратное преобразование Хаара;
  • декодированная матрица преобразуется в изображение.

Преимущества по сравнению с JPEG

При рассмотрении алгоритма Joint Photographic Experts Group было сказано, что он основан на ДКП. Такое преобразование осуществляется поблочно (8 х 8 пикселей). В результате, если сжатие сильное, то на восстановленном изображении становится заметной блочная структура. При сжатии с использованием вейвлетов такая проблема отсутствует. Однако могут появиться искажения другого типа, которые имеют вид ряби около резких границ. Считается, что подобные артефакты в среднем менее заметны, чем «квадратики», которые создаются при применении алгоритма JPEG.

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

Статья закончилась. Вопросы остались?
Комментарии 0
Подписаться
Я хочу получать
Правила публикации
Редактирование комментария возможно в течении пяти минут после его создания, либо до момента появления ответа на данный комментарий.