ФРАКТАЛЬНОЕ СЖАТИЕ ИЗОБРАЖЕНИЙ
Фрактальное сжатие изображений обеспечивает большой коэффициент сжатия. Речь пойдет о том, как сжатые данные восстанавливаются в изображение,
а также как кодируется изображение.
Кодирование
Рассмотрим изображение, представляющее собой квадрат. Заменим этот квадрат тремя его различными деформированными копиями.
Первая из них получается из оригинала сжатием в два раза. Вторая копия получена сжатием оригинала в два раза и перемещением
в левый верхний угол, а третья сжатием и перемещением в правый верхний угол исходного квадрата. (Можно сделать это
достаточно легко с помощью программы MacDraw). Результатом чего являются три маленьких квадрата. Затем необходимо сделать в
точности те же действия, что и с оригиналом, но уже с каждой из полученных копий. Фактически, необходимо повторять весь
процесс более четырех раз. В результате пяти раз рекурсивного применения подобного преобразования получим представленный
ниже треугольник. В результате повторения этой операции бесконечное число раз мы получим известный фрактал, называемый
салфеткой Серпинского. Таким образом, исходный квадрат в совокупности с тремя простыми преобразованиями - это все данные,
которые необходимы для описания этого детального изображения. Фактически, коэффициент сжатия даже лучше чем тот.
Удивительное результирующее изображение
Результирующее изображение отлично от исходного, что однозначно обусловлено одними только преобразованиями. Таким образом,
для задания салфетки Серпинского достаточно трех преобразований и ничего больше. Можно это продемонстрировать, взяв в
качестве инициализатора, т.е. исходной фигуры, совершенно разные изображения, например, эллипс, значительно отличается от
квадрата. Применяя в точности те же преобразования с ним, пять раз, получим результат представленный ниже. Можно увидеть,
однако, маленькие эллипсы на этой диаграмме. Но в пределе, повторяя эту операцию, бесконечное число раз, даже самые разные
инициализаторы неразличимы. Однако, если взять другое множество преобразований, то будет получен совсем другой результат.
Здесь взяты четыре копии полученной на предыдущей итерации фигуры и различным образом перемещены. Результат такого
построения существенно отличается от салфетки Серпинского.
Аффинные преобразования
Каждое из представленных здесь фрактальных изображений задано посредством множества аффинных преобразований. Аффинное
преобразование - это линейное (масштабирование, поворот, сдвиг, отражение) преобразование, описанное матрицей A (2x2) и
вектором переноса b: newx=A*x+b. Таким образом, одно аффинное преобразование задано с помощью 6 действительных чисел.
Салфетка Серпинского определена посредством трех аффинных преобразований или 18 действительных чисел. Это является
фантастическим коэффициентом сжатия, возможным при фрактальном сжатии изображений.
Семейство изображений
Если два изображения связаны посредством линейного преобразования t, то результаты их кодирования тоже связаны.
Таким образом, кодируя одно изображение, мы автоматически кодируем другие изображения, связанные с ним посредством
линейных преобразований.
Рандомизированный алгоритм
Устанавливая параметры аффинных преобразований, можно восстанавливать изображение, как было описано выше - посредством
использования графической программы копировать области экрана, сжимать, поворачивать и сдвигать их. Но это не самый лучший
способ их программного отображения. Вместо этого, можно использовать Rendering Algorithm:
После большого количества итераций получаем изображение, сходное с салфеткой Серпинского. В пределе, это изображение
сходится к тому же результату, независимо от случайно выбранной последовательности преобразований. (Таким образом, разные
процессоры могут использовать разные случайные последовательности, и результаты будут сходными).
Алгоритм Коллажа
Таким образом, задав преобразования, можно восстанавливать изображение. Для того чтобы сжать изображение, прежде всего,
необходимо найти преобразования. Алгоритм Коллажа позволяет это сделать: полное покрытие исходного изображения множеством
уменьшенных трансформированных копий его самого.
Изображение вверху слева в форме листа, покрыто тремя маленькими, подобно листве. Верхнее изображение справа определено
посредством этих преобразований. Внизу расположен коллаж и изображение не очень похожее на лист.
Теорема Коллажа
Алгоритм Коллажа рассказывает о том, как найти преобразования, а теорема Коллажа говорит о том, каким образом сжатое
изображение впоследствии может быть преобразовано в исходное. Если разница (погрешность) d (Хаусдорфова мера) между
оригиналом и коллажом меньше e, то расхождение между оригиналом и сгенерированным изображением меньше чем отношение
e/(1-s), где s - это размер самого большого фрагмента коллажа (так что не используйте большие фрагменты коллажа!).
d(оригинал, коллаж) < e ==> d(оригинал, результат) < e/(1-s)
Это дает объективную погрешность (меру ошибки) сжатия. Ошибка может быть снижена посредством увеличения количества
фрагментов коллажа, что ведет к лучшему покрытию исходного изображения, но уменьшению коэффициента сжатия. Так что, это
действительно некий компромисс.
Устойчивость и интерполяция
Сжатие не выявляет малую зависимость в начальных условиях. Что хорошо, так как кодирование было бы бесполезным, если
бы небольшие изменения в преобразованиях, стали причиной большого различия в изображениях. Но малые изменения в
кодированиях дают лишь малые изменения в результирующих изображениях (этот результат обусловлен теоремой Коллажа).
Таким образом, стало возможным интерполировать между двумя изображениями посредством интерполяции между их
преобразованиями. Данный рисунок демонстрирует интерполяцию между двумя изображениями, представляющими облака.