Геометрия природы

Фракталы. Странные объекты, взглянув на которые трудно отвести взгляд. Магическая и в чём-то таинственная красота, основанная на однообразии и бесконечном самоподобии.

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

По определению может показаться, что фракталы - что-то непонятное и далекое от реальности. Однако стоит взглянуть на картинку (например, на знаменитый лист папоротника Барнсли), и впечатление мгновенно изменится. Именно необычная правдоподобность, сходство с вещами из обычной жизни и привлекает внимание. Ведь перед вами - не отсканированная фотография и не рисунок, над которым долго корпел художник. Весь этот сложный объект определённым образом "запакован" (об этом - ниже) в небольшой набор чисел. Изображения фракталов оказывают потрясающий эмоциональный эффект. Неслучайно авторы известной книги "Красота фракталов" Пэйтген и Рихтер (H. O. Peitgen и P. H. Richter, "The Beauty of Fractals") обнаружили, что читателей привлекают в книге не сами статьи, а, скорее, иллюстрации к ним.

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

Рождение (или возрождение) фрактальной геометрии произошло благодаря математику компании IBM Бенойту Б. Мандельброту (Benoit B. Mandelbrot), опубликовавшему в 1977 свою работу "Фрактальная геометрия природы". В книге, которая произвела настоящий фурор, Мандельброт выдвинул тезис, что традиционная геометрия с прямыми линиями и гладкими поверхностями не походит для очертаний деревьев, облаков и гор. И математики получили новый мир геометрических объектов. Мир фрактальной геометрии.

Нелинейные системы

Фракталы - это не просто привлекательные картинки, которые могут приносить чисто эстетическое наслаждение. Фракталы интересуют нас не столько сами по себе, сколько как часть огромной области математики и кибернетики, так называемой нелинейной динамики, изучающей нелинейные системы.

В чем же особенности нелинейных систем, в чем их принципиальное отличие от привычных нам линейных? В линейной системе возмущение и реакция на него связаны однозначно, а законы функционирования таких систем описываются линейной алгеброй или системой линейных дифференциальных уравнений. Всё просто: параметр-значение, вопрос-ответ. Известно "чисто линейное" высказывание, что, зная координаты и скорости всех молекул в данный момент времени, можно воспроизвести их будущее поведение и, таким образом, предсказать историю мира. Однако на самом деле всё не так прямолинейно и просто. На практике схема начинает развиваться по законам нелинейных систем, когда малейшее искажение начальных условий вызывает цепную реакцию, так называемый "эффект бабочки": происходит катастрофическая потеря устойчивости, т.е. при малейшей погрешности в определении параметров развитие проходит совершенно иначе, чем в случае с невозмущенными (без погрешности) начальными условиями. Системы, не обладающие устойчивостью (как описанная выше система микромира) называются нелинейными.

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

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

Известный математик Девэйни (Devaney) считает, что функцию можно определить как хаотическую, если она сильно зависит от начальных условий, а точки диаграммы (графика) плотно сближаются как бы в одну цельную структуру. Хотя это и непредсказуемо, но все же содержит регулярность, так как на таком графике зависимости от параметра (его еще называют бифуркационной диаграммой) легко можно заметить чёткие, словно рукотворные, линии границ структуры, пересекающие весь этот, казалось бы, хаос, по определенным траекториям.

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

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

Век линейной алгебры закончился, и теперь в физике, математике, химии, а также на стыках дисциплин есть множество нелинейных задач. Среди них есть и нелинейная оптика, и колебательные реакции, и нелинейная оптимизация, но одна из самых перспективных возможностей применения нелинейных систем - фрактальное сжатие изображений.

В 1981 году вышла книга Джона Хатчинсона (John Hutchinson) "Фракталы и самоподобие", и в математике стало одной теорией больше, появилась теория итерируемых функций (iterated function theory), а в 1985г. Майкл Барнсли (Michael Barnsley), ведущий исследователь фирмы Georgia Tech, опубликовал свою работу, в которой ввёл в математику понятие системы итерируемых функций (IFS), доказав, что с её помощью можно представить любое изображение. В 1990г. Барнсли получил патент на технологию IFS, а в 1991г. запатентовал и усовершенствованную версию - PIFS. Хотя Барнсли доказал теоретически возможность компрессии изображений в сотни раз и даже опубликовал несколько искусственно созданных картин со сжатием 10000:1, он не мог автоматизировать процесс компрессии и всю работу приходилось делать вручную студентам университета, где Барнсли преподавал. И вот в 1992 году один из его студентов, которому, судя по всему, это надоело, - Арнод Жакуин (Arnaud Jacquin) - предложил первый практический метод автоматизированной компрессии изображений. Алгоритм Жакуина лёг в основу коммерческого компрессора/декомпрессора компании Iterated Systems Incorporated и используется до сих пор.

Рассмотрим механизмы IFS и усовершенствованной системы PIFS (Partition IFS). Упрощённо схему действия IFS можно представить так:

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

Оптимистические прогнозы для применения фрактальных методов сжатия основываются на том факте, что много природных объектов (например, облака) имеет такую форму и структуру, что их можно закодировать небольшим набором преобразований. Например, у папоротника Барнсли их только четыре. А каждое преобразование - это несколько чисел, поэтому размер сжатого образа будет минимален, вплоть до сжатия в десятки тысяч раз. Но это только в идеале. В природе нет таких же совершенных папоротников, как искусственное творение Барнсли, поэтому более практичным является разделённая система итерируемых функций (PIFS).

Принципиальное отличие PIFS - это то, что она оперирует не целой картиной, двигаясь от целого к частям, а разбивает изображение на отдельные области или доменные блоки (domain blocks) и "работает" уже с ними, генерируя меньшие, диапазонные блоки (range blocks). Это приносит результат, так как изображение очень часто неоднородно по составу (например, между облаками обычно находится небо). Каждый пиксел образа при этом обязательно будет принадлежать одному (как минимум) диапазонному блоку.

Если говорить в целом о фрактальных методах сжатия видеоизображения, нельзя не отметить, что эта тема до сих пор полностью не изучена, несмотря на всю её актуальность, а фрактальными архиваторами интересуются, скорее, любители эстетики и специалисты. Долларосодержащая руда средних пользователей так и остаётся неразработанной. До сих пор не решена проблема нахождения оптимального метода сжатия с максимальной точностью при приличной скорости компресии - так, для вычисления изображения формата 256x256 пикселов, используя метод Жакуина, нужно просчитать 31,748,976,072 вариантов.

А его метод вовсе не совершенен и Жакуин предложил алгоритм, будучи обыкновенным студентом простого американского вуза.

Так что... Господа студенты! Ваш ход!

Анатолий АЛИЗАР