Фракталы

Еще один интересный и перспективный метод сжатия графики − применение фракталов. Собственно, рождение фрактальной геометрии − дело рук Беноита Мандельброта (Benoit В. Mandelbrot), издавшего в 1977 г. книгу "Фрактальная геометрия природы" (The Fractal Geometry of Nature). Однако математики изучали подобные объекты еще в XIX в. Примером фрактала, является, скажем, ковер Серпинского. Представьте себе квадрат. Разделите его на 9 равных квадратов и центральный выбросите. Теперь повторите операцию с каждым оставшимся квадратом и так до бесконечности (рис. 4.27).

Рис. 4.27. Построение треугольника Серпинского

В результате получится структура, которая "как бы есть, но ее как бы нет". То есть фрактал имеет дробную размерность. Она больше 1 (размерности прямой линии), но меньше 2 (размерности плоскости). Одна из характерных особенностей фрактальных структур − то, что они часто встречаются в природе. Например, фракталоподобную структуру имеют снежинки, береговые линии материков, деревья и многое другое. В компьютерной графике фракталы используются для создания ранее не существовавших деталей при приближении камеры к объекту.

Но если фракталы позволяют создавать графику, имитирующую естественные образования, то почему бы не использовать их для реконструкции изображений. И действительно, Майкл Бернсли (Michael Barnsley) получил так называемую теорему Коллажа, которая описывает, какой должна быть итерационная система функций (тоже вид фрактала), чтобы она могла описывать заданное изображение.

Рис. 4.28. Папоротник Бернсли

Однако практического применения теоремы добиться сначала не удалось. Только в 1988 г. была получена другая система (Partitioned Iterated Function System), описывающая изображение через применение итерационных систем функций к отдельным его частям.

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

Рис. 4.29. Построение триадной кривой Кох (слева); Построение "дракона" Хартера-Хейтуэя (справа)

Алгебраические фракталы − это самая крупная группа фракталов. Получают их с помощью нелинейных процессов в n-мерных пространствах. Наиболее изучены двухмерные процессы. Интерпретируя нелинейный итерационный процесс как дискретную динамическую систему, можно пользоваться терминологией теории этих систем: фазовый портрет, установившийся процесс, аттрактор и т.д.

Рис.4. 30. Множество Мандельброта (слева); Участок границы множества Мандельброта, увеличенный в 200 (справа)

Опять же полностью описывать принцип фрактального сжатия будет долго и непонятно, так что объясним его кратко. Картинка разбивается на большие (16х16) и маленькие (8x8) блоки. Затем выбираются пары блоков, наиболее похожие друг на друга. Ищется преобразование (пространственное и цветовое), переводящее за ограниченное число применений большой блок в маленький (с ошибкой, меньше заданной). Полученные блоки и соответствующие им преобразования записываются в конечный файл и сжимаются без потерь. То есть алгоритм основан на том, что в любом изображении присутствуют похожие области, и на том, что при помощи заданного набора преобразования эти области можно восстановить из одного образца. Положительный момент фрактального сжатия − в принципе пропадает понятие разрешения, поскольку при увеличении картинки процесс реконструкции можно продлить, и мы опять получим похожую на себя картинку (в случае других форматов мы, в конце концов, увидим отдельные пикселы). На самом деле новых деталей тоже не появляется, но с точки зрения обычной интерполяции фракталы − это серьезный прорыв. В отличие от всех вышеперечисленных − фрактальное сжатие асимметрично: сжатие занимает больше времени, чем распаковка. Сейчас коммерческие продукты с фрактальным сжатием выпускает практически одна фирма Iterated Systems, основанная тем самым Бернсли. Что касается степени сжатия, то фракталы позволяют получить компрессию до 100 раз. Однако по уровню искажений они начинают выигрывать у JPEG только где-то на уровне 40-кратного сжатия.