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

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

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

Первый вид – сжатие без потерь, который основывается на снижение объема выходного потока информации без потери информационной структуры.

RLE (run-length encoding) – один из самых старых и самых простых алгоритмов архивации графики. Изображение в нем вытягивается в цепочку байт по строкам растра. Само сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт. Применим алгоритм для изображений с небольшим количеством цветов: деловую и научную графику. Применяется в форматах РСХ, TIFF, ВМР. На его принципах и комбинациях основываются более эффективные и сложные алгоритмы.

Алгоритм Лемпеля – Зива – Велча (Lempel-Ziv-Welch, LZW). Идея алгоритма LZW в том, что с входного потока последовательно считываются символы, далее в созданной таблице проверяются строки. Если данная строка имеется, то следующий символ считывается, а если строки нет, тогда в поток записывается код для предыдущей найденной строки, строка вносится в таблицу. В настоящий момент алгоритм применяют во многих известных программах сжатия данных – ZIP, ARJ, LHA, и в файлах формата TIFF, PDF, GIF, PostScript и других.

Кодирование Хоффмана. В данном случае также применяется кодирование повторяющихся данных, где для кодирования часто повторяющихся последовательностей используют коды меньшей длины, в отличие от более редких последовательностей. Словарь кодов – это двоичное дерево, где редко встречающиеся повторяющиеся цепочки располагаются дальше от корня дерева. Тут номера веток от корня до самой цепочки и представляют собой код последовательности. В 21 веке этот алгоритм считай, не применяется в чистом виде, но используется в файлах PNG, JPEG.

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

JPEG (Joint Photographic Expert Group) является популярным графическим форматом, который чаще всего используют для хранения фотоизображений. В целом алгоритм основан на дискретном косинусоидальном преобразовании, применяемом к матрице изображения для получения некоторой новой матрицы коэффициентов. Для получения исходного изображения используется обратное преобразование. Сжатие в JPEG производиться за счет плавного изменения цвета в изображении. JPEG обеспечивает высокий коэффициент сжатия. Бывают ситуации, в которых алгоритм создает “ореол” вокруг резких вертикальных и горизонтальных границ в изображении (эффект Гиббса). При слишком высокой степени сжатия изображение делится на блоки 8х8 пикселов. Поддерживается алгоритм JPEG в форматах Quick Time, PostScript Level 2, Tiff 6.0.

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

Следующий алгоритм JPEG 2000. Он использует технологию вейвлет-преобразования, которая основывается на представлении сигнала в виде суперпозиции базовых функций — волновых пакетов. Таким образом, изображение не только станет более четким и гладким, но и размер файла по сравнению с JPEG при таком же качестве уменьшится. Из-за применения вейвлетов, изображения в данном формате, при высоких степенях сжатия устраняются недостатки более ранней версии. JPEG-2000 применяется для цифровых охранных систем, а так же в разных алгоритмах распознавания и в биометрии. JPEG-2000 можно использовать для создания изображения глубиной цвета в 48 бит. Широкое распространение данного алгоритма способствует введению новационных технологий работы с изображениями и приложений.

Алгоритм фрактального сжатия изображения основан на применение систем итерируемых функций. Майкл Барнсли впервые исследовал возможность применения теории IFS к проблеме сжатия изображения. Джеквин предоставил метод фрактального кодирования, применяющего систему доменных и ранговых блоков изображения. Из этого метода следует, что изображение необходимо разбить на большинство неперекрывающихся ранговых подизображений и определить множество перекрывающихся доменных подизображений. Алгоритм кодирования для каждого рангового блока ищет подходящий доменный блок и аффинное преобразование, которое переводит этот доменный блок в данный ранговый блок. Структура изображения отображается в систему ранговых блоков, доменных блоков и преобразований. Идея заключается в следующем: пусть исходное изображение является неподвижной точкой некоего сжимающего отображения. Тогда достаточно лишь вместо изображения запомнить каким-либо образом это отображение, и для восстановления необходимо многократно использовать это отображение к любому стартовому изображению. Согласно теореме Банаха, итерации сводятся к неподвижной точке, а именно к исходному изображению. Главной сложностью фрактального сжатия является то, что для поиска соответствующих доменных блоков, необходим полный перебор. Так как при данном переборе нужно каждый раз сравнивать два массива, то данная операция требует много времени и значительных вычислительных ресурсов.

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

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

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

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