Читаем Суперфрактал онлайн бесплатно

Изображение кленового листа может быть воспроизведено с помощью относительно простой системы итерируемых функций, так как этот вид изображений обладает высокой степенью самоподобия. Это значит, что целое изображение состоит из уменьшенных копий его самого. Увеличивая такое изображение, мы будем наблюдать одну и ту же степень детализации независимо от разрешения. Реальные изображения не обладают высоким уровнем самоподобия, которое присутствует в изображениях, полученных с помощью систем итерируемых функций. Более того, реальные изображения могут быть представлены различной глубиной цвета от битовых— 1 bit/px (черный/белый) до TrueColor— 24 bit/px и более качественных. Если мы хотим представить такое изображение как результат действия системы итерируемых функций, то, очевидно, нам понадобятся разные системы итерируемых функций для разных фрагментов изображения.

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

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

Выявление структуры данных — ключевой аспект эффективного представления и хранения этих данных.

Широко распространено кодирование образов JPEG. Конкуренцию алгоритму сжатия JPEG составляет фрактальное кодирование изображений. Барнсли и Слоун впервые увидели возможность применения фрактального кодирования в середине 1980-х годов. В 1987 году они основали компанию «Iterated Systems Inc.». Оборот компании составил $1,5 млн в 1991 г., $4,5 млн— в 1992-м, $10,5 млн— в 1993-м и $10,5 млн — в 1994 г. В 2001 г. «Iterated Systems Inc.» была переименована в «MediaBin Inc.», а в 2003 г.— куплена компанией «Interwoven Inc.».

Для продвижения бизнеса Барнсли и его коллеги провели блестящую рекламную кампанию. Они опубликовали несколько искусственно созданных картин со сжатием 10 000:1, что значительно превосходит типовой коэффициент сжатия изображений по стандарту JPEG (50:1). Более того, обратный процесс извлечения изображения из фрактального кода — один из самых простых и быстрых. Как и в случае сжатия JPEG, фрактальное сжатие не исключает потери в том смысле, что восстановленное изображение может не соответствовать исходному изображению «точка в точку».

Еще в начале 1990-х годов этот растущий бизнес был защищен патентами: U.S. Patent 5065447 (англ), U.S. Patent 4941193, 5065447, 5384867, 5416856 и 5430812. Патенты покрывают широкий спектр возможных изменений фрактального сжатия и серьезно сдерживают его развитие. Сегодня срок действия большинства патентов истек или истекает в ближайшем будущем. Это, возможно, приведет к ренессансу фрактального метода сжатия изображений.

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

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