11.1. Алгоритмы сжатия без потерь

Одним из старых и самых простых алгоритмов архивации без потерь является алгоритм RLE (Run Length Encoding [11.2] - групповое кодирование). Сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт, которые можно экономно кодировать. Различные модификации алгоритма RLE реализованы в огромном количестве форматов (например, в PCX, GIF, TIFF, РМР [11.3]). Следует отметить, что многие современные форматы поддерживают запись данных (не только изображений) с использованием нескольких алгоритмов архивации либо без них. Например, формат TIFF 6.0 может сохранять изображения с использованием алгоритмов сжатия RLE-PackBits, RLE-CCIT, LZW, Хаффмана с фиксированной таблицей кодов, JPEG-Lossless [11.2] (хотя может сохранять изображение и без архивации). Здесь алгоритм LZW (от фамилий авторов Lempel-Ziv-Welch) является более сложным и универсальным алгоритмом (по отношению к RLE), сжимающим изображения за счет поиска, выделения и кодирования одинаковых подцепочек в потоке байт. Алгоритм Хаффмана обеспечивает сжатие с помощью предварительного вычисления частоты появления одинаковых байт в изображении.

Говоря о лучших на сегодня алгоритмах сжатия изображений без потерь, необходимо отметить, что в 1994 году был принят стандарт ISO/JPEG- Lossless [11.4]. JPEG-Lossless ориентирован на полноцветные 24-битовые или 8-битовые в градациях яркости изображения без палитры. На восемнадцати 8-битовых тестовых изображениях нескольких категорий (космических, медицинских, фото- и компьютерно-графических, смешанных) средний уровень сжатого по JPEG-Lossless изображения составил 3.98 бит/точку.

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

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