Сравните результаты сжатия файла с помощью алгоритма rle лучшие результаты

Обновлено: 07.07.2024

Выделим несколько наиболее важных для нас критериев сравнения алгоритмов компрессии, которые и будем использовать в дальнейшем.

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

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

Симметричность. Отношение характеристики алгоритма кодирования к аналогичной характеристике при декодировании. Характеризует ресурсоемкость процессов кодирования и декодирования. Для нас наиболее важной является симметричность по времени: отношение времени кодирования ко времени декодирования. Иногда нам потребуется симметричность по памяти.

Есть ли потери качества? И если есть, то за счет чего изменяется коэффициент архивации? Дело в том, что у большинства алгоритмов сжатия с потерей информации существует возможность изменения коэффициента сжатия.

Характерные особенности алгоритма и изображений, к которым его применяют. Здесь могут указываться наиболее важные для алгоритма свойства, которые могут стать определяющими при его выборе.

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

1.Первый вариант алгоритма.

Данный алгоритм необычайно прост в реализации. Групповое кодирование – от английского Run Length Encoding (RLE) – один из самых старых и самых простых алгоритмов архивации графики. Изображение в нем (как и в нескольких алгоритмах, описанных ниже) вытягивается в цепочку байт по строкам растра. Само сжатие в RLE происходитза счет того, чтов исходном изображении встречаются цепочки одинаковых байт. Замена их на пары <счетчик повторений, значение> уменьшает избыточность данных.

В данном алгоритме признаком счетчика (counter) служат единицы в двух верхних битах считанного файла:

Рис. 1. Сжатие файла с использованием первого варианта алгоритма

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

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

2.Второй вариант алгоритма.

Второй вариант этого алгоритма имеет больший максимальный коэффициент архивации и меньше увеличивает в размерах исходный файл.

Признаком повтора в данном алгоритме является единица в старшем разряде соответствующего байта:

Рис. 2. Сжатие файла с использованием второго варианта алгоритма

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

Похожие схемы компрессии использованы в качестве одного из алгоритмов, поддерживаемых форматом TIFF, а также в формате TGA.

Характеристики алгоритма RLE:

Коэффициенты компрессии: Первый вариант: , , . Второй вариант: , , . (Лучший, средний, худший коэффициенты).

Класс изображений: Ориентирован алгоритм на изображения с небольшим количеством цветов: деловую и научную графику.

Симметричность: Примерно единица.

Характерные особенности: К положительным сторонам алгоритма, пожалуй, можно отнести только то, что он не требует дополнительной памяти при архивации и разархивации, а также быстро работает. Интересная особенность группового кодирования состоит в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения.

Алгоритм RLE — это алгоритм сжатия данных, который поддерживается большинством форматов файлов растровых изображений: TIFF, BMP и PCX. RLE подходит для сжатия любого типа данных независимо от его информационного содержимого, но содержание данных влияет на коэффициент сжатия. Несмотря на то что большинство алгоритмов RLE не могут обеспечить высокие коэффициенты сжатия более сложных методов, данный инструмент легко реализовать и быстро выполнить, что делает его хорошей альтернативой.

На чем основан алгоритм сжатия RLE?

RLE работает, уменьшая физический размер повторяющейся строки символов. Эта строка, называемая run, обычно кодируется в два байта. Первый байт представляет количество символов в пробеге и называется счетчиком прогона. На практике кодированный прогон может включать от 1 до 128 и 256 символов. Счетчик обычно содержит число символов минус один (значение в диапазоне значений от 0 до 127 и 255). Второй байт — это значение символа в прогоне, которое содержится в диапазоне значений от 0 до 255 и именуется значением запуска.

Без сжатия символьный пробег в 15 символов обычно требует 15 байтов для хранения:

В той же строке после RLE-кодирования потребуется только два байта: 15А.

Кодировка 15A, сгенерированная для обозначения символьной строки, называется RLE-пакетом. В данном коде первый байт, 15, является счетчиком прогона и содержит необходимое количество повторений. Второй байт, A, является значением run и содержит фактическое повторяющееся значение в пробеге.

Новый пакет генерируется каждый раз, когда символ запуска изменяется, или каждый раз, когда количество символов в пробеге превышает максимальное количество. Предположим, что 15-символьная строка согласно условиям содержит 4 разных символа:

Используя кодировку с длиной строки, она может быть сжата в четыре двухбайтовых пакета:

После кодирования по длине строки для 15-байтовой строки потребуется всего восемь байтов данных для представления строки, в отличие от исходных 15 байтов. В этом случае кодирование во время выполнения давало коэффициент сжатия почти 2 к 1.

Особенности

Длинные прогоны редки в некоторых типах данных. Например, открытый текст ASCII редко содержит длинные прогоны. В предыдущем примере последний пробег (содержащий символ t) был только одним символом в длину. 1-символьный прогон все еще работает. И счет запуска, и значение запуска должны быть записаны для каждого пробега в 2 символа. Для кодирования пробега с помощью алгоритма RLE требуется информация, состоящая не менее чем из двух символов. В связи с чем запуск одиночных символов на самом деле занимает больше места. По тем же причинам данные, состоящие полностью из 2-символьных прогонов, остаются неизменными после кодирования RLE.

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

Варианты кодирования по длине

Существует несколько вариантов кодировки во время выполнения. Данные изображения, как правило, закодированы в последовательном процессе, который обрабатывает визуальный контент как 1D-поток, а не как 2D-карту данных. При последовательной обработке растровое изображение кодируется, стартуя с верхнего левого угла, и направляется слева направо по каждой строке сканирования в нижний правый угол растрового изображения. Но альтернативные схемы RLE также могут быть записаны для кодирования данных по длине растрового изображения вдоль столбцов для сжатия в 2D-плитки или даже для кодирования пикселей по диагонали зигзагообразным способом. Нечетные варианты RLE могут использоваться в узкоспециализированных приложениях, но обычно встречаются довольно редко.

Алгоритм кодирования с ошибкой длины пробега

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

Кросс-кодирование

Кросс-кодирование — это объединение строк сканирования, которое происходит, когда процесс сжатия теряет различие между исходными линиями. Если данные отдельных линий объединены алгоритмом кодирования повторов RLE, точка, где одна линия сканирования остановлена, а другая - потеряна, является уязвимой и сложной для обнаружения.

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

Как с помощью алгоритма RLE закодировать изображение?

Индивидуальное кодирование строк сканирования имеет преимущества в тех случаях, когда приложение должно использовать только некоторую часть изображения. Предположим, что фото содержит 512 строк развертки, и необходимо отображать только строки от 100 до 110. Если мы не знали, где строки сканирования начинались и заканчивались данными кодированного изображения, нашему приложению пришлось бы декодировать строки с 1 по 100, прежде чем найти десять строк, которые требуются. Если переходы между линиями сканирования были отмечены каким-то легко узнаваемым маркером разграничения, приложение могло бы просто считывать закодированные данные, подсчитывая маркеры, пока не дойдет до нужных ему строк. Но этот подход был бы довольно неэффективным.

Альтернативный вариант

Другим вариантом для определения начальной точки любой конкретной строки сканирования в блоке кодированных данных является построение таблицы строк развертки. Данная табличная структура обычно содержит один элемент для каждой строки сканирования на изображении, и каждый элемент содержит значение смещения соответствующей строки сканирования. Чтобы найти первый RLE-пакет строки 10 сканирования, все, что нужно сделать декодеру, — это найти значения позиции смещения, хранящегося в десятом элементе таблицы поиска строки сканирования. Таблица строк развертки также может содержать количество байтов, используемых для кодирования каждой строки. Используя этот метод с целью найти первый RLE-пакет строки сканирования 10, ваш декодер будет объединять значения первых 9-ти элементов таблицы строк развертки. Первый пакет для строки 10 сканирования будет начинаться с этого смещения байта от начала данных изображения с кодированием RLE.

Единицы измерения

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

Качество сжатия

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

Исключения

Схемы RLE на уровне байта кодируют прогоны одинаковых байтовых значений, игнорируя некоторые биты и границы слов в строке сканирования. Наиболее распространенная схема RLE на байтовом уровне кодирует прогоны байтов в 2-байтовые пакеты. Первый байт содержит счетчик от 0 до 255, а второй — содержит значение байтового запуска. Также распространено дополнение двухбайтовой схемы кодирования с возможностью хранения литеральных, незаписанных прогонов байтов в потоке кодированных данных.

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

Схемы RLE на уровне пикселей используются, когда два или более последовательных байта данных изображения используются для хранения значений одного пикселя. На уровне пикселей биты игнорируются, а байты подсчитываются только для идентификации каждого значения пикселя. Размер кодированных пакетов зависит от размера кодируемых значений пикселей. Количество бит или байтов на пиксель сохраняется в заголовке файла изображения. Запуск данных изображения, сохраненных в виде 3-байтовых значений пикселей, кодируется в 4-байтовый пакет, с одним байтом подсчета количества операций, за которым следуют три байта с байтами. Метод кодирования остается таким же, как и с байтовым RLE.

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

1.Первый вариант алгоритма.

В данном алгоритме признаком счетчика (counter) служат единицы в двух верхних битах считанного файла:

Рис. 1. Сжатие файла с использованием первого варианта алгоритма

2.Второй вариант алгоритма.

Признаком повтора в данном алгоритме является единица в старшем разряде соответствующего байта:

Рис. 2. Сжатие файла с использованием второго варианта алгоритма

Характеристики алгоритма RLE:

Коэффициенты компрессии: Первый вариант: , , . Второй вариант: , , . (Лучший, средний, худший коэффициенты).

Симметричность: Примерно единица.

для упаковки и распаковки текстовых строк;
для упаковки и распаковки файлов любого формата;
для анализа предельных возможностей сжатия файлов;
для сравнения эффективности алгоритмов сжатия.

Программы работают под управлением операционных систем линейки Windows на любых современных компьютерах.

Алгоритм RLE

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

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

Если вы заметили ошибку или у вас есть предложения, замечания, жалобы, просьбы и заявления, пишите.

Алгоритмы Хаффмана, Шеннона-Фано и LZW

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

После щелчка по кнопке (клавиша F4) текст, введенный в текстовом редакторе, сжимается. Сжатые данные показываются в нижней части окна программы в виде строки, содержащей двоичный код. В правой части показывается таблица кодов символов, использованная при сжатии.

Кнопка Анализ файла позволяет определить для любого файла предельный теоретически достижимый коэффициент сжатия при побайтном кодировании.

Если вы заметили ошибку или у вас есть предложения, замечания, жалобы, просьбы и заявления, пишите.

Лицензия

Программы являются бесплатными для некоммерческого использования. Исходные тексты программ не распространяются.

При размещении программ на других веб-сайтах ссылка на первоисточник обязательна.

1) публикация материалов в любой форме, в том числе размещение материалов на других Web-сайтах;
2) распространение неполных или измененных материалов;
3) включение материалов в сборники на любых носителях информации;
4) получение коммерческой выгоды от продажи или другого использования материалов.

Использование и скачивание материалов означает, что вы приняли условия этого лицензионного соглашения.

В архив включены следующие файлы:

После распаковки архивов программы находятся в работоспособном состоянии и не требуют никаких дополнительных установок.

Читайте также: