Кодирование методом Хаффмана

Групповое сжатие

Сжатие изображений

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

– групповое сжатие;

– кодирование методом Хаффмана;

– сжатие по схеме LZW;

– арифметическое сжатие:

– сжатие с потерями;

– преобразование цветов RGB в цвета YUV.

В основе большинства схем сжатия лежит использование одного из следующих свойств графических данных: избыточность, предсказуемость и необязательность. В частности, групповое кодирование (RLE) основано на использовании первого свойства. Кодирование по методу Хаффмана и арифметическое кодирование, основанные на ста­тистической модели, используют предсказуемость, предлагая более короткие коды для более часто встречающихся пикселов. Алгоритмы сжатия с потерями основаны на из­быточности данных.

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

Рассмотрим подробнее несколько алгоритмов сжатия.

Групповое сжатие представляет собой одну самых простых схем сжатия файлов. Суть его заключается в том, что серия повторяющихся величин заменяется единственной ве­личиной и ее количеством. На примере можно заметить выгоду в длине между «aabbbbbbbcdddeeeeaaa» и «2а7b1c3d4e3a». Данный алгоритм прост в реализации и хо­рошо сжимает графические файлы с большими однотонными областями. Групповое коди­рование используется во многих форматах растровых файлов, таких как TIFF, PCX и т. д.

Смысл метода Хаффмана заключается в замене данных более эффективными кода­ми. Более короткие коды используются для замены более часто появляющихся вели­чии. Например в выражении abbbeceddeeeeeeeeef есть шесть уникальных величин, с частотами появления: а:1, b:3, c:3, d:2, e:9, f:l. Для образования минимального кода используется двоичное дерево. Алгоритм объединяет в пары элементы, появляющиеся наименее часто, затем пара объединяется в один элемент, а их частоты объединяются. Это действие повторяется до тех пор, пока элементы не объединятся в пары. В данном примере надо объединить а и f – это первая пара, а присваивается нулевая ветвь, a f – 1-я. Это означает, что 0 и 1 будут младшими битами кодов для а и f соответственно. Более старшие биты будут получены из дерена по мере его построения.

Суммирование частот дает в итоге 2. Теперь самая низкая частота – 2, поэтому пара а и f, объединяется с d (которая тоже имеет частоту 2). Исходной паре присваиваеся нулевая ветвь, а d – ветвь 1. Таким образом, код для а заканчивается на 00; для f на 01, d заканчивается на 1 и будет на один бит короче по сравнению с кодами для а и f.

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

Дата добавления: 2014-01-14