Фрактальное сжатие

История возникновения метода фрактального сжатия

Понятия «фрактал» и «фрактальная геометрия» (fractus – состоящий из фрагментов, лат.) были предложены математиком Б. Мандельбротом в 1975 г. для обозначения нерегулярных, но самоподобных структур. Рождение фрактальной геометрии связывают с выходом в 1977 г. книги Б. Мандельброта «Фрактальная геометрия природы», в которой объединены в единую систему научные результаты учёных, работавших в период 1875-1925 гг. в этой области (Пуанкаре, Жюлиа, Кантор и др.).

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

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

Существует большое разнообразие фракталов. Потенциально наиболее полезным видом фракталов являются фракталы на основе системы итеративных функций (Iterated Function System – IFS). Метод IFS применительно к построению фрактальных изображений, изобретённый большим их знатоком Майклом Барнсли (Michael Barnsley) и его коллегами из Технологического института шт. Джорджия (Georgia Institute of Technology), базируется на самоподобии элементов изображения и заключается в моделировании рисунка несколькими меньшими фрагментами его самого. Специальные уравнения позволяют переносить, поворачивать и изменять масштаб участков изображения; таким образом, эти участки служат компоновочными блоками остальной части картины. Одним из наиболее поразительных (и знаменитых) IFS-изображений является чёрный папоротник, в котором каждый лист в действительности представляет собой миниатюрный вариант самого папоротника (см. рис.). Несмотря на то, что картинка создана компьютером методом аффинных преобразований, папоротник выглядит совершенно как настоящий. Выдвинуто предположение, что природа при кодировании генетической структуры растений и деревьев пользуется чем-то близким к методу IFS-фракталов. IFS-фракталы имеют одно вполне реальное и полезное применение: с их помощью можно сжимать большие растровые изображения до долей их нормальных размеров. Это утверждение следует из теоремы Банаха о сжимающих преобразованиях (также известной как Collage Theorem) и является результатом работы исследователя Технологического института шт. Джорджия Майкла Барнсли в области IFS. Вооружившись этим выводом, он ушёл из института, запатентовал своё открытие и основал компанию Iterated Systems Incorporated. О своём достижении он рассказал миру в журнале Byte за январь 1988 г. Однако там отсутствовали какие-либо сведения о решении обратной задачи: как по заданному изображению найти аффинные преобразования. К тому моменту у этой задачи не было даже намёка на решение. В статье Барнсли было показано несколько реалистичных фрактальных изображений, но все они были созданы вручную.

В идеале хотелось бы уметь находить для любого изображения систему аффинных преобразований (IFSM), воспроизводящую изображение с заданной точностью. Однако решение находилось немного в стороне. Первым нашёл его именно студент Барнсли, Арно Жакан (Arnaud Jacquin). Предложенный метод получил название «Система итерируемых кусочно-определённых функций» (Partitioned Iterated Function System – PIFS). Согласно этой схеме, отдельные части изображения подобны не всему изображению, а только его частям.

Типовая схема фрактального сжатия

Схема компрессии выглядит так: изображение R разбивают на кусочки r_i, называемые ранговыми областями. Далее для каждой области r_i находят область d_i и преобразование w_i такие, что выполняются следующие условия:

1. d_i по размерам больше r_i.
2. w_i (r_i) имеет ту же форму, размеры и положение, что и r_i.
3. Коэффициент u преобразования w_i должен быть меньше единицы.
4. Значение должно быть как можно меньше.

Первые три условия означают, что отображение w_i будет сжимающим. А в силу четвёртого условия кодируемое изображение R и его образ W (R) будут похожи друг на друга. В идеале R = W (R). А это означает, что наше изображение R и будет являться неподвижной точкой W. Именно здесь используется подобие различных частей изображения (отсюда и название – «фрактальная компрессия»). Как оказалось, практически все реальные изображения содержат такие похожие друг на друга, с точностью до аффинного преобразования, части.

Таким образом, для компрессии изображения W нужно:

1. Разбить изображение на ранговые области r_i (непересекающиеся области, покрывающие все изображение).
2. Для каждой ранговой области r_i найти область d_i (называемую доменной), и отображение w_i, с указанными выше свойствами.
3. Запомнить коэффициенты аффинных преобразований W, положения доменных областей d_i, а также разбиение изображения на домены.

Соответственно, для декомпрессии изображения нужно будет:

1. Создать какое-то (любое) начальное изображение R₀.
2. Многократно применить к нему отображение W (объединение w_i).
3. Так как отображение W сжимающее, то в результате, после достаточного количества итераций, изображение придёт к аттрактору и перестанет меняться. #Аттрактор и является нашим исходным изображением. Декомпрессия завершена.

Основная сложность метода

Основная сложность фрактального сжатия заключается в том, что для нахождения соответствующих доменных блоков вообще говоря требуется полный перебор. Поскольку при этом переборе каждый раз должны сравниваться два массива, данная операция получается достаточно длительной. Сравнительно простым преобразованием её можно свести к операции скалярного произведения двух массивов, однако даже скалярное произведение вычисляется сравнительно длительное время.

На данный момент известно достаточно большое количество алгоритмов оптимизации перебора, возникающего при фрактальном сжатии, поскольку большинство статей, исследовавших алгоритм были посвящены этой проблеме, и во время активных исследований (1992—1996 года) выходило до 300 статей в год. Наиболее эффективными оказались два направления исследований: метод выделения особенностей (feature extraction) и метод классификации доменов (classification of domains).

Оптимизация алгоритма компрессии

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

Для снижения вычислительных затрат можно предпринять следующие меры: Исследовать доменную область не полностью, а с некоторым шагом. Это также позволит увеличить степень сжатия, но скажется на качестве изображения. Искать не лучшую доменную область, а удовлетворяющую некоторому E. Хотя это может значительно увеличить скорость сжатия, но такой приём так же может значительно снизить качество результирующего изображения. В данном случае качество в значительной степени зависит от адекватности метрики различия между изображениями. При поиске доменной области подвергать преобразованию не доменную область, а ранговую. Для этого удобно хранить 8 вариантов ранговых областей с различными преобразованиями. При этом в результирующий файл нужно записать обратное преобразование. Для всех преобразований, кроме двух, обратным является само это преобразование. Для поворота на 90° и 270° необходимо записать поворот на 270° и 90° соответственно. Это значительно сократит вычислительные затраты, но также значительно увеличатся затраты оперативной памяти. Для поиска доменной области можно использовать не перебор, а какой-либо из алгоритмов условной нелинейной глобальной оптимизации, такой, как алгоритм моделирования отжига или генетический алгоритм. В этом случае будет всего три варьируемых параметра (координаты доменной области и номер аффинного преобразования), а целевой функцией – среднеквадратичное отклонение доменной области от ранговой.

Для улучшения качества: в случае необнаружения доменной области, удовлетворяющей заданному E, ранговую область можно разбить на 4 подобласти и произвести поиск домена для каждой из них. Это можно делать и дальше рекурсивно, до достижения некоторого минимального размера либо единичного пиксела. Но это увеличит вычислительные затраты и снизит коэффициент сжатия.

Для увеличения коэффициента компрессии можно идентифицировать однотонные блоки. Однотонным блоком будем называть ранговую область, у которой среднеквадратичное отклонение от собственного среднего значения не превышает некоторого E'. При этом в выходной файл будет записана только средняя яркость точки, за счёт чего будет достигнуто сжатие 1 к 64 (для ранговых областей размером 8).

Патенты

Майклом Барнсли и другими было получено несколько патентов на фрактальное сжатие в США и других странах. Эти патенты покрывают широкий спектр возможных изменений фрактального сжатия и серьёзно сдерживают его развитие.

Патенты не ограничивают исследований в этой области, то есть можно придумывать свои алгоритмы на основе запатентованных и публиковать их. Также можно продавать алгоритмы в страны, на которые не распространяются полученные патенты. Кроме того срок действия большинства патентов — 17 лет с момента принятия и он истекает для большинства патентов в ближайшее время, соответственно использование методов, покрывавшихся этими патентами станет гарантированно свободным.

См. также

• Barrett - программное обеспечение

Ссылки

• http://stanislaw.ru/rus/research/fractal.asp#.Tu9ui5fcj3F
• http://ru.wikipedia.org/wiki/Алгоритм_фрактального_сжатия
• http://compression.ru/arctest/descript/fract-comp.htm