Мультимедийные технологии в САПР. Часть 1. Майстренко Н.В - 24 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

4.3.1. Алгоритмы сжатия изображений без потерь
Методы сжатия без потерь разделяют на две категории:
1. Методы сжатия источников данных без памяти (т.е. не учитывающих последовательность символов).
2. Методы сжатия источников с памятью.
RLE (Run Length Encoding)
Данный алгоритм необычайно прост в реализации. Изображение в нём вытягивается в цепочку байт по строкам рас-
тра. Само сжатие в RLE происходит за счёт того, что в исходном изображении встречаются цепочки одинаковых байт.
Замена их на пары <счетчик повторений, значение> уменьшает избыточность данных.
RLE – первый вариант. В данном алгоритме признаком счётчика (counter) служат единицы в двух верхних битах
считанного файла. Соответственно оставшиеся 6 бит расходуются на счётчик, который может принимать значения от 1
до 64. Строку из 64 повторяющихся байтов мы превращаем в два байта, т.е. сожмём в 32 раза.
Алгоритм рассчитан на деловую графику – изображения с большими областями повторяющегося цвета. Ситуация,
когда файл увеличивается, для этого простого алгоритма не так уж редка. Её можно легко получить, применяя групповое
кодирование к обработанным цветным фотографиям. Для того, чтобы увеличить изображение в два раза, его надо приме-
нить к изображению, в котором значения всех пикселов больше двоичного 11000000 и подряд попарно не повторяются.
Данный алгоритм реализован в формате PCX.
RLE – второй вариант. Второй вариант этого алгоритма имеет большую максимальную степень сжатия и меньше
увеличивает в размерах исходный файл.
Признаком повтора в данном алгоритме является единица в старшем разряде соответствующего байта.
Как можно подсчитать, в лучшем случае этот алгоритм сжимает файл в 64 раза (а не в 32 раза, как в предыдущем ва-
рианте), в худшем увеличивает на 1/128. Средние показатели степени компрессии данного алгоритма находятся на уровне
показателей первого варианта. Похожие схемы компрессии использованы в качестве одного из алгоритмов, поддержи-
ваемых форматом TIFF, а также в формате TGA.
К положительным сторонам алгоритма RLE можно отнести только то, что он не требует дополнительной памяти при
архивации и разархивации, а также быстро работает.
Методы сжатия источников без памяти
1. Сжатие по Хаффману.
Самый известный и распространённый метод. Сдаёт позиции более мощному арифметическому сжатию. Использует
только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, которые встреча-
ются большее число раз, цепочку бит меньшей длины. И, напротив, встречающимся редко – цепочку большей длины. Для
сбора статистики требует двух проходов по изображению.
Алгоритм Хаффмена практически не применяется в чистом виде и обычно используется как один из этапов ком-
прессии в более сложных схемах. Характерной особенностью этого метода является "неувеличение" размера исходных
данных в худшем случае (если не считать необходимости хранить таблицу перекодировки вместе с файлом).
2. Арифметическое кодирование.
В 1970-е годы у алгоритма Хаффмена появился достойный конкурент – арифметическое кодирование. Этот метод
основан на идее преобразования входного потока в одно число с плавающей запятой. Естественно, что чем длиннее со-
общение, тем длиннее получающееся в результате кодирования число, т.е. на выходе арифметического компрессора по-
лучается число меньшее 1 и большее либо равное 0. Из этого числа можно однозначно восстановить последовательность
символов, из которых оно было построено.
Рассмотрим работу арифметического компрессора на примере сообщения "BILL GATES".
Поставим в соответствие каждому символу сообщения вероятность его появления в сообщении (табл. 4.1).
Затем присвоим каждому символу интервал вероятности в промежутке от 0 до 1. Длина интервала для символа рав-
на вероятности его появления в сообщении. Положение интервала вероятности каждого символа не имеет значения.
Важно только то, чтобы и кодер, и декодер располагали символы по одинаковым правилам. Интервалы вероятности для
символов нашего сообщения приведены в табл. 4.2.

Страницы