Кодирование с преобразованием.
Кодирование с преобразованием является эффективным методом сжатия информации при обработке изображений. Детальный анализ этой группы алгоритмов сжатия будет дан при изучении последующих разделов курса. В данной лекции приведем лишь общие характеристики методов.
Кодирование с преобразованием проводится сразу над группой пикселов в пределах кадра изображения. Массив отсчетов изображения трансформируется в матрицу коэффициентов. Преимущества кодирования, получаемые в результате преобразования коэффициентов, заключаются в следующем:
- значительное количество элементов матрицы коэффициентов имеют нулевое значение;
- декорреляция связей между пикселами, получаемая в результате преобразования, повышает эффективность статистического кодирования.
Преобразование изображения следует рассматривать как его разложение в обобщенный двумерный спектр по базисным функциям, где амплитуда каждой спектральной составляющей характеризует яркость. Так при дискретном косинусном преобразовании (ДКП) обработка ведется блоками 8х8 пиксел. Размер блока выбран экспериментально и соответствует интервалу корреляции элементов изображения. В результате выполнения ДКП формируется матрица из 64 коэффициентов, характеризующих пространственные частоты – двумерные (x,y) – функции яркости изображения. После операции ДКП дальнейшая обработка требует квантованного представления этих коэффициентов. Заключительной операцией при квантовании является Z –упорядочивание, при котором коэффициенты выстраиваются в последовательности возрастания пространственных частот. Из ряда коэффициентов образуются пары чисел, одно из которых равно ненулевому коэффициенту, а другие числу предшествующих этому элементу нулей. Далее эти сочетания чисел кодируются кодом Хаффмана.
Wavelat - преобразование
В случае WAVELAT –преобразования (W – преобразования), как и при ДКП, осуществляется переход из плоскости изображения в двумерную частотную область. В отличие от ДКП этот переход осуществляется с помощью гребенки цифровых фильтров, что позволяет отказаться от блочной структуры преобразования и устранить основной недостаток ДКП, связанный со скачкообразным изменением шумов квантования при переходе от одного блока ДКП к другому. Сигнал изображения разделяется с помощью фильтров верхних и нижних частот на две равные части. Поскольку НЧ- и ВЧ- компоненты имеют полосу в два раза меньшую, чем исходный сигнал, частота их дискретизации может быть понижена в два раза. Входной сигнал является цифровым. Поэтому после ВЧ- и НЧ – фильтрации производится исключение каждого второго отсчета. При этом результирующее количество отсчетов на выходе всей гребенки фильтров равно количеству отсчетов в исходном изображении. Таким образом при W – преобразовании кадр изображения переводится в частотную область, где описывается тем же количеством отсчетов, что и до преобразования. Для кодирования спектральных отсчетов изображения, полученных в результате W – преобразования, используются те же операции, что и при ДКП.
Кодирование с предсказанием.
Основная идея способа кодирования с предсказанием заключается в том, что каждый отсчет aj можно предсказать на основе анализа одного или нескольких предыдущих отсчетов aj1, a j2 ..ajn . В результате предсказания получается некоторая оценка δj i – го отсчета как функция предыдущих отсчетов. Для представления сигнала используются разности между предсказанным и измеренным значением отсчетов, называемые ошибками предсказания
έ = аj – ajи,
где аj – предсказанное значение отсчета
аjи – измеренное значение.
Если известны значения отсчетов в нескольких опорных точках и матрица ошибок предсказания, то можно восстановить сигнал. При правильно выбранной функции предсказания энтропия ошибок существенно меньше энтропии отсчетов, рассматриваемых без учета взаимосвязи, что позволяет экономить объем памяти и полосу пропускания канала передачи информации. В частности, при дельта – модуляции, представляющей собой разновидность импульсно – кодовой модуляции для представления разности используется всего один бит, обозначающий знак разности. Недостатком данного метода является необходимость достаточно высокой частоты отсчетов, чтобы не было “запаздывания” изменений передаваемого сигнала по сравнению с реальными изменениями. Дифференциальная ИКМ отличается от дельта – модуляции тем, что знак разности передается только в момент пересечения измеряемой величиной отсчета одного из уровней квантования. В адаптивной ДИКМ величина шага отсчетов адаптируется к динамике изменений величины сигнала. Более детальное описание перечисленных методов будет дано в процессе обсуждения возможностей повышения эффективности алгоритмов сжатия данных.
В практике классификации методов сжатия информации пользуются также такими понятиями как “сжатие с потерями” и “сжатие без потерь”. Сжатие с потерями применяется в основном для графики (JPEG), звука (МР3), видеоинформации (MPEG), т. е. там, где степень сжатия (эффективность применяемого метода обработки) играет важную роль при обработке больших объемов данных и можно пожертвовать деталями, не существенными для восприятия информации в целом. Наилучшие возможности для сжатия информации имеются при обработке видеоданных. В ряде случаев большая часть изображения передается из кадра в кадр без изменений, что позволяет применять алгоритмы сжатия на основе выборочного отслеживания только части “картинки”. Достаточно высока эффективность применения алгоритмов сжатия при обработке графики. Однако, применение алгоритмов сжатия с потерями не всегда приемлемо. Например, обработка алгоритмом JPEG фотоснимков легких для представления их на медэкспертизу, так как может быть утеряна существенная, сточки зрения медиков, информация. Еще одна причина, по которой ограничивается область использования алгоритмов сжатия с потерями, заключается в том, что повторное применение данных алгоритмов приводит к накоплению погрешностей.
Сжатие без потерь может применяться при обработке любой информации, поскольку может быть полностью восстановлена исходная информация после применения данных алгоритмов. Наиболее известны следующие алгоритмы сжатия без потерь: это арифметическое кодирование, кодирование Хаффмана и LZW – кодирование (по начальным буквам имен создателей Lempel, Ziv, Welch). Кодирование Хаффмана и метод арифметического кодирования рассмотрены нами выше.