• 0

Алгоритмы сжатия изображений

 
Алгоритмы сжатия изображений


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

Фотоснимки потрясающего качества в сжатом форматеФотоснимки потрясающего качества в сжатом формате


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

Зависимость качества изображения от степени сжатияЗависимость качества изображения от степени сжатия


RLE (Run Length Encoding - кодирование длин серий) - самый простейший алгоритм сжатия, в котором обработчик отслеживает последовательность одинаковых байт и меняет ее на пару "длина серии - значение байта". Например, серию байт в файле 55555555 алгоритм заменяет на пару 85. Данная технология очень хорошо применяется в тех файлах, где присутствуют большие области, залитые одним цветом (блок-схемы, диаграммы). Сегодня данный алгоритм используется для предварительной обработки в таких форматах, как BMP, PCX, TIFF, JPEG.

LZW (Lempel-Ziv-Welch) - авторы данного алгоритма заложили в основу технологии ведение специального словаря повторяющихся цепочек битов. В отличие от RLE байты здесь не должны повторяться? учитывается лишь последовательность. При нахождении последовательности цепочка помещается в специальный словарь, а на ее место кодировщик проставляет код данной цепочки из словаря. Соответственно, итоговый файл преобразования содержит в себе словарь, коды, указывающие на элементы словаря, и неповторяющиеся элементы. Сегодня алгоритм используется в форматах цифровых файлов: GIF, PNG, TIFF.

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


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

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

JPEG - разработка "Группы экспертов в области фотографии" для изображений с 24-битной цветовой глубиной. Сегодня это почти стандарт полноцветных изображений. Технология использует дискретное косинусное преобразование (DCT), применяемой к матрице изображения размеров 8х8 для получения некоторой новой матрицы коэффициентов. Само кодирование проходит в четыре этапа.
На первом этапе идет выборка (sampling), где цветовые данные преобразуются в модель YCbCr. Затем выполняется прореживающая выборка (down-sampling), где компоненты цветности (Cb, Cr) снижаются в качестве, так как для глаза человека эти потери наиболее несущественны.
На втором этапе происходит DCT, где изображение разбивается на матричные блоки 8х8 для последующего преобразования.
Третьим этапом в алгоритме является квантование (quantization), где из изображения удаляются последние элементы матрицы DCT, которые влияют на конечный результат изображения в наименьшей степени. Оставшиеся коэффициенты DCT колируются по методу Хоффмана.
Описанный алгоритм применяется повсеместно, за исключением кодирования простых рисунков, где глаз человека видит четкие переходы от одного цвета к другому. В таких изображениях при использовании алгоритма сжатия JPEG пользователь получит на границах перехода эффект Гиббса (размазанные границы с грязным ореолом).

JPEG-сжатиеJPEG-сжатие


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

Рекурсивное волновое преобразование - данный алгоритм сжатия использует обработку фильтрами (низко- и высокочастотным) по строкам и столбцам с последующей операцией прореживания. Суть метода заключается в том, что при сжатии фильтр в виде небольшой области сканирует изображение. Значения цветовых элементов (пикселей), попавших в фильтр, умножаются на определенные коэффициенты, а значения суммируются. Далее фильтр сканирует следующую область изображения. В итоге на выходе из изображения размером XY получается четыре размером в половину первоначального. Первая картинка здесь - уменьшенное исходное изображение, а другие - картины наибольших разностей между пикселями по горизонтали, вертикали и диагонали. Далее все изображения подвергаются квантованию, где все коэффициенты, близкие к значению 0, отбрасываются. Данный метод позволяет преобразовывать не отдельные блоки имеющегося рисунка (как в алгоритме JPEG), а целые картинки, что позволяет получать более качественные изображения на выходе. Волновой метод нашел свое применение сегодня в формате файлов JPEG-2000.

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


Информация
Посетители, находящиеся в группе Гости, не могут оставлять комментарии к данной публикации.