Тема 11. Фракталы и Фрактальные методы архивации

Существуют алгоритмы архивации (сжатия) больших информационных массивов, информационных хранилищ и складов данных с помощью фракталов. Они основаны на теореме Банаха о сжимающих преобразованиях (также известной как Collage «Theorem») и являются результатом работы исследователя Технологического института шт. Джорджия Майкла Барнсли.

1. Фракталы и история возникновения метода фрактального сжатия

Понятия «фрактал» и «фрактальная геометрия» (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). Согласно этой схеме, отдельные части изображения подобны не всему изображению, а только его частям.