Лекции - Технологии Мультимедиа, страница 9

Символы с малой вероятностью дальше от корня, и их коды длиннее.Чтобы декодировать, декомпрессор берет код и обрабатывает его в обратном порядке.Это значит, что он начинает с корня дерева. Если первый бит кода равен 1, то декомпрессоридет от корня в узел по ветви 1. Он продолжает чтение битов и проход по ветвям, пока недостигнет листа; символ в листе и есть декодированный символ.Следует упомянуть еще об одном свойстве дерева Хаффмана. Поскольку символывсегда являются листьями, узлы символов никогда не имеют потомков. Когда декомпрессорполучает лист, он знает, что он должен немедленно прекратить чтение, потому что он знает,что пришел в лист.

Другими словами, один код Хаффмана никогда не будет префиксом другого. Это значит, что хотя длина кода меняется, декомпрессор всегда знает, когда кончаетсяодин код и начинается другой, и нет необходимости явно помещать разделители между кодами.Динамическое кодирование ХаффманаСамой большой сложностью с кодами Хаффмана является необходимость иметь таблицы вероятностей для каждого типа сжимаемых данных. Это не представляет проблемы,47если вы знаете, что всегда будете сжиматьанглийский текст; вы просто предоставляетекомпрессору и декомпрессору подходящее для английского текста дерево.

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

Начальное дерево как в компрессоре, так и в декомпрессоре, имеет толькокорень и единственный пустой лист.Компрессор присоединяет символ к ветви 1 корня, оставляя пустой лист на ветви 0.Затем он посылает этот символ в декомпрессор как буквальный код ASCII, и декомпрессорвыполняет точно такое же действие над своим деревом.Для каждого символа, прочитанного после этого, компрессор выполняет следующиешаги.

Вначале он проверяет, находится ли код в кодовом дереве. Если код есть, компрессорвыдает его так же, как и в случае статического сжатия. Если же нет, он посылает код для пустого листа. Затем он посылает новый символ как буквальный код ASCII. Наконец, компрессор добавляет два кода, один для нового пустого листа на ветви 0, и один - для нового кодаветви 1. Когда дерево заполнится, т.е. когда в нем будут все символы, компрессор просто изменяет последний пустой лист на последний символ. Программа декомпрессии может делать уточнения в своем дереве, потому что у нее имеется в точности то же самое дерево, чтои у компрессора.

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

Вы должны также поддерживать список обозначений узлов (и весов), сортированный по весу.Каждый символ начинается с веса 1 (пустой лист начинается с 0). Всякий раз, когдакомпрессор передает символ, который находится в таблице, он инкрементирует вес узла, соответствующего этому символу. Если это изменение делает узел "тяжелее", чем узлы, которые выше него в списке, компрессор обменивает узел символа с самым тяжелым узлом, который, однако, легче, чем узел символа.

При обмене в дело идут только определения роди-48тельских узлов и ветвей; это не касается потомков обмениваемых узлов, так что не существует опасности, что лист станет внутренним узлом, а внутренний узел - листом.Компрессор затем проходит вверх по дереву к родителю символа, который мог бытьизменен во время последнего обмена. Он продолжает процесс с родителем, и далее по дереву, но не достигает корня.Алгоритмы сжатия с потерямиАлгоритмГрупповое кодированиеЦепочки, за счет которых происходит сжатие2 2 2 2 2 2 2 15 15 15 - Подряд идущие цветаLZW2 3 15 40 2 3 15 40 - Одинаковые подцепочкиХаффмана2 2 3 2 2 4 3 2 2 2 4 - Разная частота появления цветаJPEGОтсутствие резких границФрактальныйПодобие между элементами изображенияJPEG - один из самых новых и достаточно мощных алгоритмов. Практически он становится стандартом де-факто для полноцветных изображений. Алгоритм JPEG был разработан группой фирм под названием Joint Photographic Experts Group.

Целью проекта являлосьсоздание высокоэффективного стандарта сжатия как черно-белых, так и цветных изображений, эта цель и была достигнута разработчиками. В настоящее время JPEG находит широчайшее применение там, где требуется высокая степень сжатия - например, в Internet.В отличие от LZW-алгоритма JPEG-кодирование является кодированием с потерями.Сам алгоритм кодирования базируется на очень сложной математике, но в общих чертах егоможно описать так:Прежде всего, программа делит изображение на блоки - матрицы размером 8х8 пикселей. Поскольку при использовании метода JPEG время, затрачиваемое на сжатие изображения, пропорционально квадрату числа пикселей в блоке, обработка нескольких блоковменьшего размера делается значительно быстрее, чем обработка всего изображения целиком.Схема YUV использует три компоненты, Y – яркость (может быть использована какчёрно – белое изображение), U – голубизна, V – краснота.

Перевод из RGB осуществляетсяпо схеме:Y = 0.299R + 0.587G + 0.114B49U = 0.1687R - 0.3313G + 0.5BV = 0.5R - 0.1187G + 0.0813BЭто преобразование, в принципе, не имеет потерь, но на практике вводится ошибкаокругления, обусловленная необходимостью округления результата до целого. Так как глазчеловека более чувствителен к первой компоненте, чем к двум другим, то в JPEG допускаетдискретизацию различных компонент с различной частотой. Наиболее общий случай – использование одной выборки U и V для четырёх выборок Y. Это позволяет сохранять лишь50% используемого объёма при практически неизменном качестве изображения.

Технологиядискретизации, при которой некоторые компоненты оцифровываются с меньшей частотой,чем другие, называется поддескритизацией.К значениям пикселей применяется формула, названная дискретным косинусоидальным преобразованием (Discrete Cosine Transform - DCT). DCT переводит матрицу значенийпикселей 8х8 в матрицу значений амплитуд такой же размерности, соответствующую определенным частотам синусоидальных колебаний. Левый верхний угол матрицы соответствуетнизким частотам, а правый нижний - высоким.Дискретное косинусоидальное преобразование (DCT) превращает массив данных интенсивности в массив данных частоты, который содержит информацию о том, как быстроизменяется интенсивность. В JPEG применяется DCT для квадратов 8*8 данных о пикселяхдля каждого компонента цвета.

Точки в каждом блоке нумеруются от (0,0) в верхнем левомдо (7,7) в нижнем правом углах. F(x,y) есть значение данных в точке (x,y). Создаётся новыйблок по формуле: 7 71(2 x  1)u(2 y  1)v F (u , v)  C (u )C (v)   f ( x, y ) coscos41616 x 0 y 0C ( z)  12C ( z )  1,, z  0,z  0.Обратное преобразование имеет вид:f ( x, y ) 1 7 7(2 x  1)u(2 y  1)v C (u )C (v) F (u, v) coscos4  u 0 v 01616По физическому смыслу преобразование сводится к представлению изображения ввиде суммы (ко)синусоидальных гармоник (волн). Значения F определяют амплитуды гармоник, u,v – их частоты.

F(u,v) указывает на степень изменения величин для каждой измножества частот. Значение F(0,0) указывает что уровень значения не изменился, F(7,7)определяет наиболее быстрое изменение величины в обоих направлениях. Более высокие частоты “отвечают” за передачу более “тонких” деталей изображения.50Для блоков 8*8 выходные данные на 4 бита длиннее входных. Отличие интенсивностей от частот в том, что медленные изменения гораздо заметнее, чем быстрые, так что данные низкой частоты более важны, чем высокой для восстановления изображения.Коэффициент качества, введенный пользователем, используется в простой формуле,которая генерирует значения элементов другой матрицы 8х8, названной матрицей квантования. Чем ниже коэффициент качества, тем большие значения будут иметь элементы матрицы.Каждое значение в матрице, получившееся после DCT - преобразования, делится насоответствующее значение из матрицы квантования, затем округляется до ближайшего целого числа.

Так как большие числа находятся в правой нижней половине матрицы квантования,то основная часть высокочастотной информации изображения будет отброшена. Поэтомунижняя правая часть матрицы пикселей будет состоять в основном из нулей. Конкретнаяматрица квантования задаётся кодером, например, для сжатия видео часто применяется матрица81619 22 22 26 26 2722 26 27 29 34 24 27 29 34 37 27 29 34 34 38 27 29 34 37 40 u v29 32 35 40 48 32 35 40 48 58 34 38 46 56 69 38 46 56 69 83 16 19162222 2622 2626 2727 2927 2929 35Далее программа, двигаясь по матрице зигзагообразно, считывает элементы матрицыи кодирует их последовательно методами без потерь.F(00)(01)F(10)(11)F(21)(22)F(31)(32)F(02)FF(03)F(12)FF(23)F(33)FF51Заметим, что сжатие существенно зависит от нулей в правой нижней половине матрицы.

Чем ниже коэффициент качества, тем больше нулей в матрице и, следовательно, тем выше степень сжатия.Декодирование JPEG-изображения начинается с шага обратного кодированию без потерь, в результате чего восстанавливается матрица квантования пикселей.Значения из матрицы пикселей умножаются на значения из матрицы квантования,чтобы восстановить, насколько это возможно, матрицу, которая была вычислена на шагеприменения DCT. На этапе квантования была потеряна некоторая часть информации, поэтому числа в матрице будут близки к первоначальным, но не будет абсолютного совпадения.Обратная к DCT формула (IDCT) применяется к матрице для восстановления значений пикселей исходного изображения.Еще раз отметим, что полученные цвета не будут полностью соответствовать первоначальным из - за потери информации на шаге квантования.

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