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

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

Эффективность сжатия по схеме Хаффмана изменяется с точностью алгоритма и типом изображения. Алгоритм меняется в зависимости от формата, но достигает сжатия, несколько превышающего 8:1. Схема Хаффмана работает не так хорошо для файлов, содержащих длинные последовательности повторяющихся величин пикселов, которые могут быть сжаты лучше с использованием групповой или какой-нибудь другой схемы кодирования.

Схема сжатия LZW

LZW – более современный алгоритм сжатия, названный по первым буквам авторов метода (Lempel и Ziv) и алгоритма (Welch). Алгоритм имеет несколько вариаций, многие из которых запатентованы, поэтому их полная реализация не раскрывается.

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

Метод LZW сжимает файлы обычно до 1/3 или 1/4 их первоначального размера. Сильно насыщенные узорами изображения, содержащие большие блоки однотонной окраски или повторяющиеся цветные узоры, могут сжиматься еще больше, до 1/10 первоначального размера.

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

Подобно групповому сжатию (RLE), метод LZW не является сам по себе форматом, но включен в несколько различных форматов файлов.

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

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

В общем случае, арифметическое сжатие включает отображение каждой отличной последовательности величин пикселов в диапазон цифр в строке воображаемого числа между 0 и 1. Эта область затем представляется как двоичная дробь переменной точности. Менее общие последовательности требуют более высокой точности.

Сжатие методом JPEG

Данный формат обеспечивает гораздо более высокий коэффициент сжатия, чем другие форматы, особенно для рисунков фотографического качества.

Метод сжатия JPEG породил новый термин машинной графики: потери. Сжатием без потерь считается такое, при котором не происходит утраты данных исходного изображения, и рисунок, сжатый этим методом, а затем восстановленный, в точности соответствует оригиналу. При сжатии с потерями происходит отбрасывание части данных исходного изображения. Метод JPEG поддерживает оба способа, причем получаемая степень сжатия может быть очень значительной (до 5% от исходного размера).

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

Первоначально изображение RGB преобразуется в пространство цвета освещенность/цветовая насыщенность (luminance/chrominance), после чего получается базовое изображение в градациях серого плюс два канала информации о различиях цветов. Затем используется дискретное косинусоидальное преобразование (DCT) для преобразования растровых данных в информацию об интенсивности изменений. Квантование округляет результаты DCT, приводя их в меньший диапазон величин. На этом шаге формируются потери, так как коэффициент квантования определяет количество теряемых данных и, следовательно, определяет диапазон сжатия и качество восстановленного изображения. Для получения окончательного результата выходные данные квантования сжимаются с использованием либо кодирования Хаффмана, либо арифметического кодирования.

Графические редакторы

 

Заключение

Таким образом, выбор растрового или векторного формата зависит от целей и задач работы с изображением. Если нужна фотографическая точность цветопередачи, то предпочтительнее растр. Логотипы, схемы, элементы оформления удобнее представлять в векторном формате. Понятно, что и в растровом и в векторном представлении графика (как и текст) выводятся на экран монитора или печатное устройство в виде совокупности точек. В Интернете графика представляется в одном из растровых форматов, понимаемых браузерами без установки дополнительных модулей – GIF, JPG, PNG.

Из-за описанных выше особенностей представления изображе­ния, для каждого типа приходится использовать отдельный графический редактор – растровый или векторный. Разумеется, у них есть общие черты – возможность открывать и сохранять файлы в различных форматах, использование инструментов с одинаковыми названиями (карандаш, перо и т.д.) или функциями (выделение, перемещение, масштабирование и т.д.), выбирать нужный цвет или оттенок. Однако принципы реализации процессов рисования и редактирования различны и обусловлены природой соответствующего формата. Так, если в растровых редакторах говорят о выделении объекта, то имеют в виду совокупность точек в виде области сложной формы, Процесс выделения очень часто является трудоемкой и кропотливой работой. При перемещении такого выделения появляется «дырка». В векторном же редакторе объект представляет совокупность графических примитивов, и для его выделения достаточно выбрать мыш­кой каждый из них. А если эти примитивы были сгруппированы со­ответствующей командой, то достаточно «щелкнуть» один раз в любой из точек сгруппированного объекта. Перемещение выделенного объекта обнажает нижележащие элементы.

С некоторыми особенностями работы с простым векторным редактором Microsoft Draw мы познакомились в разделе 4.2.3 «Создание рисунка». Этот редактор встроен в офисный интегрированный пакет программ MS Office.

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

Некоторые растровые редакторы способны грузить один из векторных форматов (обычно.wmf) в качестве фона или сразу переводить их в растр с возможностью непосредственного редактирования.

 

 

12	Поделиться:

Воспользуйтесь поиском по сайту: