Требования к алгоритмам компрессии

Типы изображений.

Для того чтобы корректно оценивать степень сжатия, нужно разделить изображения на несколько типов.

· Схематические изображения. Изображения с небольшим количеством цветов, и большими областями, заполненными одним цветом (деловая графика, чертежи).

· Фотореалистичные изображения (цифровые или отсканированные фотографии, изображения созданные в программах 3D –визуализации).

· Текстуры, накладываемые на поверхности.

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

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

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

· Высокое качество изображения, которое, вообще говоря, противоречит выполнению предыдущего. Кстати, довольно часто алгоритм предоставляет возможность выбора качества архивации (например, JPEG), и соответственно, степени архивации. В случае необходимости 100% соответствия используются алгоритмы сжатия без потерь.

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

Стоит также отметить, что важно также не только сама скорость, а скорее ее зависимость от, например, размеров изображения. Реализация фрактального алгоритма “в лоб” приведет вообще говоря, к зависимости n² от площади изображения.

· Высокая скорость декомпрессии. Достаточно универсальное требование, хотя стоит отметить, что иногда более, а иногда менее актуально.

· Возможность постепенного проявления изображения, т.е. возможность показать огрубленное изображение, использовав только начало файла. Данное требование стало актуально в web, когда пользователь может, например, решить, продолжать ему закачку большой картинки или нет, скачав только его часть. Иногда эта возможность является свойством алгоритма (например, wavelet), иногда алгоритм можно модифицировать. (В алгоритме Motion JPEG, например, изменили порядок записи коэффициентов, чтобы сначала шли низко, потом средне, а потом высокочастотные компоненты изображения. В алгоритме Interlaced GIF поступили еще проще, просто записывая строчки изображения не подряд, а через четыре)

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

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

· Небольшая стоимость аппаратной и (или) эффективность программной реализации. Это требование важно, например, при проектировании алгоритмов сжатия текстур, с учетом дальнейшей интеграции этих алгоритмов в видеочип. Также стоит оценить эффективность таких технологий MMX, 3DNow! и Katmai, и возможность эффективного распараллеливания алгоритмов.

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