Алгоритм сжатия видеоинформации WAVELET

Алгоритм сжатия видеоинформации WAVELET

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

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

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

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

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

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

Далее на рисунках показано оригинальное изображение и восстановленное после сжатия по JPEG-алгоритму и по WAVELET-алгоритму. Легко заметить, что при практически одинаковых размерах закодированных файлов качество "WAVELET-картинки" значительно выше. Требование одинаковости, предъявляемое к качеству картинки, приводит к выигрышу по размерам 1.5-2 раза.

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

По материалам поиска в Internet на тему Wavelet - преобразование