0.299 0.596 0.211

1.000 1.000 1.000

0.587 -0.274 -0.523

0.956 -0.273 -1.104

0.114 -0.322 0.312

G В

0.621 y*^

-0.647 1.701

Цветное телевидение в Северной Америке использует представление YIQ.

Фишер [18] и Лу [26] обсуждают сжатие цветных изображу ний более подробно. Примеры из нашей книги будут относится к сжатию изображений в градациях серого.

Введение

29

[Основной объект внимания этой книги

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

Часть I

ФРАКТАЛЬНОЕ СЖАТИЕ ИЗОБРАЖЕНИЙ

Орстемы итерируемых функций

В начале 80-х годов Майкл Барнсли выдвинул идею получения заранее заданного изображения как аттрактора хаотического (chaotic) процесса. Еще раньше другие исследователи обнаружили, что хаотические системы способны создавать удивительные изображения, названные странными аттракторами (strange attractors). Барнсли, однако, был первым, кто сделал шаг к решению обратной задачи. Суть ее в следующем. Пусть задано определенное изображение. Можно ли построить хаотическую систему, для которой данное изображение будет являться странным аттрактором? Барнсли использовал специальную систему отображений, которые он назвал системой итерируемых функций (Iterated Function System - IFS). IFS - это, в лучшем случае, только лишь грубая форма сжатия изображений. Нужно подчеркнуть, что IFS в своей исходной форме и в том виде, в котором они представлены в этой главе, не являются основой современных подходов к фрактальному сжатию изображений (заблуждение, поддерживаемое некоторыми противниками фрактального сжатия изображений). Однако IFS вдохновили развитие фрактальных методов сжатия изображений. И хотя сами по себе IFS не могут быть использованы как готовые системы сжатия изображения, знание теории IFS необходимо для понимания того, как работают фрактальные методы сжатия изображений. В этой главе мы изложим математические основы теории IFS и покажем, как такие системы могут быть реализованы на компьютере.