И, наконец, в работе [35] авторы показали, что в контексте вычислительной сложности фрактальное кодирование имеет NP-сложность. Они показали, что даже при конечном числе допустимых значений контрастности и яркости (s и о) количество возможных кодов возрастает экспоненциально относительно количества ранговых блоков или размера изобра" жения. Более того, они показали, что любой код, создаваемый стандартными методами фрактального кодирования (например, доменно-ранговое сопоставление), является пре' доптимальным (suboptimal) решением.

Часть II

ВЕЙВЛЕТ-СЖАТИЕ ИЗОБРАЖЕНИЙ

стые вей влеты

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

Введение

Идея вейвлет-сжатия изображений, как и других методов с преобразованием, довольно проста. Сначала к изображению применяется вейвлет-преобразование, а затем из данных преобразованного изображения удаляются некоторые коэффициенты. К оставшимся коэффициентам может быть применено кодирование. Сжатое изображение восстанавливается путем декодирования коэффициентов, если это необходимо, и применением обратного преобразования к результату. Предполагается, что в процессе удаления части коэффициентов преобразования теряется не слишком много информации. Рис. 5.1.1 иллюстрирует этот процесс.

Фракталы и вейвлеты для сжатия изображений в действ^