Одномерное сжатие с помощью элементарных волн Хаара

Чтобы понять, как можно использовать элементарные волны Хаара для сжа­тия изображения в одном направлении, воспользуемся примером:

Рассмотрим строку из восьми значений данных, которые могут быть рядом из матрицы 8x8 пикселов, значение каждого из которых соответствует яркости. Их значения равны.

Мы будем преобразовывать изображение в три этапа, используя процесс, на­зываемый усреднением и дифференцированием:

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

· Этот процесс обратим. Путем соответствующих сложений и вычитаний мы мжем снова получить из последнего ряда исходный ряд.

· Этот процесс можно обобщить применительно к строкам любой длины. Для троки из 2^k элементов требуются k этапов обработки. Любая строка, длина которой не равна степени 2, может быть дополнена нулями.

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

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

· Значительно большей степени сжатия, хотя и с потерями данных, можно добиться, игнорируя области малых изменений.

Чтобы продемонстрировать последнее утверждение, зададим некоторое по­роговое значение ε и обнулим все элементы преобразованной строки, модуль которых не превышает ε. Например, при пороговом значении 4 из строки удаляет­ся второй элемент, в результате чего получится строка (43, 0,16, 10, 8, -8, 0, 12). Поместим эту строку в последний ряд пустой таблицы и вычислим по ней ис­ходные данные:

На рис. 10.6 (а) полученный результат сравнивается с исходными данными. Со­ответствие оказывается довольно близким. На черно-белом дисплее эти два изоб­ражения были бы практически идентичными. Теперь установим пороговое значе­ние ε = 8. При этом мы устраним еще два элемента в сжатой строке и получим строку (43,0,16,10, 0,0,0,12). Распакуем эту строку: (59,59, 27, 27, 53, 53,45, 21). Этот результат сравнивается с исходными данными на рис. 10.6 (б). Данное прибли­жение основывается только на пяти из исходных восьми значений, но приближе­ние остается довольно неплохим.

Рис. 10.6. Сжатие при помощи элементарных волн Хаара