Основы фрактального сжатия изображений. Практическое применение фрактальных алгоритмов Фрактальное сжатие в пространстве

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

Цели и задачи

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

Идея работы - разработка новых модификаций методов отбора доменных блоков и способов их аппроксимации в ранговые блоки для повышения эффективности кодирования.

Для достижения указанной цели в магистерской работе поставлены и решены следующие задачи:

1. Изучение литературных источников и проведение теоретического анализа алгоритмов сжатия изображений с потерями.
2. Установление особенностей функционирования алгоритмов фрактального сжатия изображений, разработка реализующего их программного обеспечения.
3. Формирование набора изображений, проведение вычислительных экспериментов по установлению особенностей отбора доменных блоков и их аппроксимации, сравнительный анализ результатов, формулирование выводов.
4. Модификация отдельных этапов алгоритма, формирование его новой версии.
5. Разработка соответствующих программных компонент, проведение экспериментов, сравнительные результаты работы.

Предмет исследования - алгоритмы сжатия изображений с потерями.

Объект исследования - фрактальные алгоритмы сжатия изображений.

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

Предполагаемая научная новизна

Научная новизна уже проведенных и планируемых в работе исследований предполагается в следующем:

1. Разработано программное обеспечение, реализующее базовые алгоритмы фрактального сжатия и позволяющее проводить сопоставительный анализ.
2. Проведены вычислительные эксперименты, сделан сравнительный анализ и выявлены особенности отбора доменных блоков в базовых алгоритмах.
3. Анализ применимости нелинейных моделей отображений блоков изображений.
4. Предложены новые модификации алгоритма, направленные на повышение эффективности сжатия.

Описание результатов работы

Описание исследований

На текущем этапе проведены исследования двух алгоритмов фрактального сажатия изображений — базового и FE-алгоритма, которые хорошо описаны в литературе . Их можно отнести к числу основных.

Базовый алгоритм условно включает следующие этапы.

Шаг 1. В изображении f выделяют множество доменных блоков. Они могут перекрываться, а величина перекрытия определяется специально предусмотренным параметром.

Шаг 2. Изображение разбивают на не перекрывающиеся ранговые блоки {R k } . Они могут не быть одинакового размера, т.к. используется адап¬тивное разбиение методом квадро-дерева с переменным размером блоков. Это позволяет плотно заполнить ранговыми блоками маленького размера части изображения, содержащие мелкие детали.

Шаг 3. Для каждого рангового блока перебирают доменные блоки. При этом предусматривают изменение ориентации доменов (3 варианта вращения, 2 ва¬рианта вращения с отражением, 2 варианта отражения и 8-ой вариант - исходная ориентация без изменений). При каждом из вариантов ориентации домен сжимают до размеров рангового блока и вычисляют оптимальные значения коэффициентов a ij и b ij преобразования

методом наименьших квадратов и по формуле

вычисляют нормированное значение параметра L(R k , D" ij) , который характеризует соответствие преобразованного сжатого i -го доменного блока w ij (D" ij) в его j -ой ориентации ранговому блоку R k . Здесь r xy ∈ R k , d xy ∈ D" ij , D" ij — i -ый доменный блок в j -ой ориентации, сжатый до размеров рангового блока, N R k — количество пикселей в ранговом блоке. На этом шаге алгоритм работает в одном из двух режимах, выбираемом пользователем, — с поиском и без поиска наилучшего домена. В режиме поиска наилучшего домена для каждого ранга перебираются все домены, и выбирается тот i -ый домен и его j -ая ориентация, значение L kij которого является минимальным среди всех остальных. В режиме без поиска наилучшего домена полный перебор доменов останавливают, как только обнаруживается такой i -ый домен и его j -ая ориентация, что его значение L kij не превышает заданной допустимой погрешности (например, L kij ≤ 0.05). В обоих режимах, если после перебора всех доменных блоков не нашлось таких, значения L kij которых не превышают значение заданной допустимой погрешности, то делается проверка — находится ли рассматриваемый ранговый блок на максимально допустимом уровне разбиения рангов. Если нет, то этот ранговый блок разбивают на меньшие блоки и проводят данный шаг алгоритма для них. Если да, то из всех доменов выбирают тот домен и его вариант ориентации D ij , для которого значение L kij является минимальным среди всех остальных, и считают рассматриваемый ранговый блок покрытым этим доменом.

Шаг 3 требует наибольших вычислений, т.к. для каждого рангового блока R k алгоритм перебирает все (или многие, в зависимости от режима работы) доменные блоки и их варианты ориентации, проводя над каждым занимающие много машинного времени попиксельные операции изменения ориентации и нахождения коэффициентов преобразования. Хорошее сжатие зависит от возможности найти хорошее соответствие между доменными и ранговыми блоками без необходимости глубокого разбиения ранговых блоков. Чрезмерно глубокое разбиение рангов приводит к слишком большому их количеству, что ухудшает коэффициент сжатия, а недостаточно глубокое — к плохому качеству закодированного изображения.

FE-алгоритм. Сравнение рангов с доменами в базовом алгоритме требует значительных вычислительных ресурсов. С целью их снижения в FE-алгоритме (от англ. Feature Extraction — выделение особенностей) выделяется пять характеристик, описывающих доменные и ранговые блоки. И первоначально, проводится именно их сравнение, что значительно сокращает объем вычислений. Эти характеристики следующие:

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

Сам алгоритм включает следую¬щие этапы.

Шаг 1. Аналогично шагу 1 базового алгоритма.

Шаг 2. Дополняя шаг 2 базового алгоритма, производится вычисление и хранение значений вектора характеристик для каждого доменного блока.

Шаг 3. При обработке рангового блока сначала вычисляют его вектор характеристик, затем вычисляют расстояния между вектором характеристик данного ранга и вектором характеристик каждого домена по формуле

где f j R и f j D - это j -ые характеристики рангового и доменного блоков соответственно. Для последующего полного сравнения отбирается только заданный q процент доменов (напри¬мер, q = 2%) с минимальными значениями расстояний между векторами характеристик. Последующие действия аналогичны тем, которые выполняются в шаге 3 базового алгоритма, но с той разницей, что при переборе доменов рассматриваются только выбранные q % и наилучший выбирается из них.

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

Описание разработанного ПО

Для проведения исследований было разработано специальное программное обеспечение на языке C# с использованием технологии Microsoft .NET Framework 2.0 и инструментальной оболочки Visual Studio 2005/2008. Оно позволяет кодировать растровые изображения в фрактальные и декодировать их рассмотренными выше алгоритмами. Пользователь может задавать настройки кодирования, регулирующие качество кодируемых изображений. Кроме того, программное обеспечение включает следующие средства анализа:

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

UML-диаграмма разработанного программного обеспечения представлена ниже (рисунок 1):

Рисунок 1 — UML-диаграмма разработанного программного обеспечения

Рисунок 2 — Экранные формы разработанного программного обеспечения

Эксперименты, результаты и выводы

С использованием разработанного программного обеспечения была проведена серия экспериментов, в которых использовалось произвольно выбранное изображение размером 256×256 пикселей, представленное на рисунке 3. Исходные данные, параметры настроек и результаты экспериментов приведены в таблице 1. На рисунке 4 представлено декодированное изображение, предварительно закодированное рассматриваемыми алгоритмами.

Рисунок 3 — Исходное изображение

Рисунок 4 — Визуализация восьми итераций декодирования изображения, закодированного базовым (а) и FE- (б) алгоритмами фрактального сжатия изображений. Анимация состоит из 9 кадров с задержкой в 50 мс между кадрами; задержка до повторного воспроизведения составляет 400 мс; количество циклов воспроизведения ограничено 10-ю.

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

где p x,y , p" x,y — значение пикселя в точке (x, y) исходного и декодированного изображений соответственно, I W , I H — соответственно ширина и высота (в пикселях) изображения, N I - количество пикселей в изображении.

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

Таблица 1 — Результаты экспериментов

Параметры	№ эксперимента
FE-алгоритм
Количество доменов
нач.ур.дом.
макс.ур.дом.
Коэфф. скольжения доменов
Количество рангов
Нач. уровень разбиения рангов
Допуст.погр.
Искать наилучший домен
Ср. пикс. ошибка, %
Коэфф.сжатия
Время кодирования, (с)
Время декодирования, (с)
Базовый алгоритм
Количество доменов
нач.ур.дом.
макс.ур.дом.
коэф.скольж.дом.
Количество рангов
Нач. уровень разбиения рангов
Макс. уровень разбиения рангов
Допуст.погр.
Искать наилучший домен
Ср. пикс. ошибка, %
Коэфф.сжатия
Время кодирования, (с)
Время декодирования, (с)

Полученные результаты позволяют сделать следующие выводы:

1. FE-алгоритм, по сравнению с базовым, позволяет сжимать изображения в десятки раз меньшее время при одинаковых параметрах настроек алгоритмов.
2. Различаются средние пиксельные ошибки алгоритмов. В зависимости от настроек, различие находится в пределах 5-16%.
3. В результате кодирования базовым алгоритмом во всех случаях достигается в среднем на 30-40% более высокий коэффициент сжатия.
4. Визуальное качество декодированного изображения заметно лучше при использовании FE-алгоритма.
5. Время декодирования закодированного изображения при различных настройках кодирования меньше при использовании базового алгоритма во всех экспериментах.

Некоторые из них вполне очевидны. Действительно, в FE-алгоритме, вместо сравнения блоков изображения происходит сравнение их векторов характеристик, что естественно отражается на быстродействии. Различие пиксельных ошибок и коэффициентов сжатия скорее всего объясняется тем, что при использовании FE-алгоритма в результате кодирования получается бoльшее количество рангов малого размера, что к тому же обеспечивает более высокую детализацию изображения, то есть - лучшее визуальное качество. Эти заключения подтверждает и рисунок 6, на котором представлено закодированное обоими алгоритмами изображение с сеткой рангов. Следует обратить внимание на то, что хотя при базовом алгоритме и получается на 5-16% худшее качество изображения, но при этом, достигается на 30-40% более высокий коэффициент сжатия.

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

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

В результате проведения экспериментов было установлено, что для 99.73 % ранговых блоков FE-алгоритм выбрал другие домены, т.е. - не наилучшие. Таким образом, по крайней мере, для данного изображения можно утверждать, что процедура отбора доменов, принятая в FE-алгоритме, не вполне отражает близость сравниваемых блоков.

Заключение

В результате проведенных исследований и экспериментов вытекают следующие соображения.

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

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

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

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

Основные положения отдельных этапов работы были доложены на III-й международной научно-технической конференции молодых учёных и студентов «Информатика и компьютерные технологии» (Донецк, ДонНТУ, 2007), IV-й международной научной конференции студентов, аспирантов и молодых ученых «Компьютерный мониторинг и информационные технологии» (Донецк, ДонНТУ, 2008).

Lifeng Xi,Liangbin Zhang. A Study of Fractal Image Compression Based on an Improved Genetic Algorithm. International Journal of Nonlinear Science. Vol.3, No. 2, 2007, pp. 116-124

M. Hassaballah, M.M. Makky, Youssef B. Mahdy. A Fast Fractal Image Compression Method Based Entropy. Electronic Letters on Computer Vision and Image Analysis 5(1), 2005, pp. 30-40

P. M. Кроновер. Фракталы и хаос в динамических системах. Основы теории. - М.: Постмаркет, 2000

Barnsley, Michael F., Sloan, Alan D., Iterated Systems, Inc. Methods and apparatus for image compression by iterated function system. United States Patent 4941193, July 10, 1990

* — При написании данного автореферата магистерская диссертация еще не завершена. Окончательное ее завершение состоится 1 декабря 2008 г. Текст и материалы диссертации могут быть получены у автора или его руководителя после этой даты.

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

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

В начале 80-х годов Майкл Барнсли выдвинул идею получения заранее заданного изображения как аттрактора хаотического процесса. Барнсли пытался ответить на вопрос: возможно ли для данного изображения построить хаотическую систему, которая будет являться для него странным аттрактором. Он использовал систему итерируемых функций (Iterated Function System - IFS).

Наиболее распространённым примером фрактального изображения, сгенерированного с помощью IFS является изображение папоротника (рис.1.10), использованное для создания данного изображения, состоит из 4-х аффинных преобразований. Каждое преобразование кодируется считанными байтами, хотя исходное изображение может быть любого размера. Таким образом, можно заключить, что фрактальная компрессия – это поиск самоподобных областей и определение для них параметров аффинных преобразований.

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

Рис. 1.10. Изображение папоротника, сгенерированного с помощью IFS

В основе фрактального сжатия лежат несколько основных определений и теорем. Рассмотрим их вкратце.

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

f: X 1  X 2 , если оно переводит пространство Х 1 в пространство Х 2 .

Преобразование f: X 1  X 2 в метрическом пространстве (X,d) называется сжимающим, если существует константа s , 0s<1 такая что:

d(f(x 1),f(x 2))  sd(x 1 ,x 2),

где d(x 1 ,x 2) – расстояние от точки х 1 до точки х 2 в пространстве X.

Константа s называется коэффициентом сжатия отображения f.

Рис. 1.11. Сжимающее отображение для точек в пространстве R 2

На рисунке 1.11 показан пример сжимающего отображения (R 2 ,d 2), примененного к множеству точек в R 2 . Здесь данное преобразование применялось более одного раза: сначала f(x) вычислялось для точки х, а затем преобразование f применялось к результату преобразования: f(f(x)). Такое последовательное, многократное применение преобразования называют итерациями и обозначают как: f on , т.е. f(f(…f(x)…)), где f применяется n раз.

Теорема о сжимающих отображениях : пусть f: X 1 X 2 сжимающее отображение на полном метрическом пространстве. Тогда f имеет всего одну и только одну неподвижную точку x f X и для любого х из Х последовательность { f on (x):n=1,2,…} сходиться к x f . Эта теорема лежит в основе всех подходов к фрактальному сжатию изображении.

Пусть {w 1 ,w 2 ,…,w n } конечный набор сжимающих отображений в пространстве (X,d) с коэффициентами сжатия s 1 ,s 2 ,…,s n , 0s<1. Определим отображение W, воздействующее на компактные множества точек B из Х:

W(B)=w 1 (B) w 2 (B)… w n (B)=U N n=1 (B) (1.21)

Таким образом, W осуществляет отображение в данном пространстве с коэффициентов сжатия s, где s=max{s 1 ,s 2 ,…,s n }.

Система итерирующих функций (IFS) состоит из полного метрического пространтсва (X,d) и конечного множества сжимающих отображений w n: XX c коэффициентами сжатия s n . Таким образом, IFS можно обозначить следующим образом: {X,w n:n=1,2,..,N}, или если рассматривать пространство точек в R 2 , то просто {w n }.

В теории фрактального сжатия доказывается теорема коллажа, которую можно сформулировать следующим образом.

Пусть есть двоичное изображение LR 2 и пусть есть сжимающие отображения, такие что: U N n =1 w n (L)

Покрывают L почти точно. Можно считать такое w n (L) уменьшенной копией L. Тогда теорема коллажа утверждает, что аттрактор А (аттрактором IFS называется изображение, которое является единственной неподвижной точкой IFS) системы {w n } близок к L. «Коллажом» является набор областей wn(L).

Так как аттрактор А – это результат бесконечного числа итераций IFS, то он является по своей сути фракталом.

Рис. 1.12. Иллюстрация теоремы коллажа.

(а) исходное изображение и четыре фрагмента изображения;

(б) изображение-аттрактор

Чтобы на практике применить теорему коллажа, необходимо выбрать преобразования, которые будут являться сжимающими отображениями. Одним из таких преобразований являются аффинные преобразования: T: R 2 R 2:

(1.23)

где a, b, c, d, e, f R. Аффинные преобразования могут осуществлять поворот, перемещение и масштабирование.

На рисунке 1.13 показано действие аффинного преобразования на множество точек вR 2 .

Рис. 1.13. Воздействие аффинного преобразования на точки в пространстве R 2

Чтобы создать IFS изображение – нужно найти хотя бы некоторое приблизительное самоподобие в изображении. Затем нужно выделить точки и преобразование IFS для каждой из фигур подобия на изображении. Когда точки и преобразования для IFS определены, то вычисляются коэффициенты аффинного преобразования, используя систему уравнений, основанную на выражении1 (1.23).

Существует два алгоритма построения изображения-аттрактора с помощью IFS. Один из них это прямое применение теоремы о сжимающих отображениях, а другой – применение так называемой «игры хаоса».

Детерминированный алгоритм для построения изображения являющегося аттрактором IFS, к любому начальному изображению B применяет теорему о сжимающих отображениях. Алгоритм строит последовательность изображений A n , многократно применяя IFS отображение W={w 1 ,w 2 ,…,w n }:

A n =W on (B) (1.24)

Детерминированный алгоритм полезен с точки зрения обучения, поскольку позволяет видеть результат преобразования на каждом шаге итерации (рис 1.14).

Вероятностный алгоритм связывает с каждым аффинным преобразованием w i в IFS вероятность p i . Эти вероятности определяют, насколько плотно каждая часть изображения-аттрактора покрыта точками. Вероятностный алгоритм создаёт изображение - аттракторы высокого качества быстрее, чем детерминированный алгоритм. Это происходит не только из-за того, что вероятностный алгоритм на каждом шаге итерации выполняет меньшую работу, но и сама выполненная работа даёт лучший результат.

Рис. 1.14. Детерминированный алгоритм, применённый к IFS папоротника.

Вид изображения A n после: a)2-х, b)3-х, c)10-и, d)30-и итераций.

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

Рис. 1.15. Отображение доменных блоков в ранговые

при фрактальном сжатии изображения

Базовый алгоритм фрактального кодирования изображения выполняется следующим образом (Рис 1.15):

1. Изображение f разбивается на не перекрывающиеся ранговые блоки {R i }. В самом простом случае блоки могут представлять собой прямоугольники, но могут быть и другие формы.

2. Изображение покрывается последовательностью доменных блоков, которые могут пересекаться. Домены могут быть разного размера, и их количество может исчисляться сотнями и тысячами.

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

4. Если достаточно точного соответствия не получилось, то разбиваем ранговые блоки на меньшие ранговые блоки. Данный процесс продолжается до тех пор пока, не получают приемлемого соответствия или размер рангового блока достигает определённых значений.

Блок-схема такого алгоритма представлена на рис.1.16.

В настоящее время известны следующие разновидности такого алгоритма .

Алгоритм Фишера. Идея алгоритма заключается в том, чтобы некоторым образом классифицировать D-блоки и R-блоки, а поиск близкого D-блока производить в том же классе, к которому относится ранговая область. Делается это следующим образом .

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

тип 1:
,

тип 2:
,

тип 3:
.

Понятно, что любой блок при помощи соответствующего аффинного преобразования квадрата в квадрат можно привести к виду, соответствующему одному из указанных типов. После того, как мы зафиксировали три основных класса, блоки классифицируются по дисперсии. Таким образом, в каждом из трех классов появляются 24 подкласса, итого 72 класса. Поиск близкого к R-блоку D-блока производится перебором в соответствующем классе.

Генетический алгоритм . Генетический алгоритм (ГА) представляет собой алгоритмический подход к решению экстремальных задач однокритериального выбора, основанный на моделировании основных факторов эволюционного развития популяции .

При использовании ГА для поиска оптимальных решений каждый элемент xX пространства оптимизации должен быть представлен как векторb B из N символов двоичного алфавита A = {0,1}, где B = A N . Необходимо также, чтобы пространство оптимизации X состояло из конечного числа элементов.

Популяцией П = (χ 1 , χ 2 ,…, χM) численности M считается вектор пространства B M , координаты которого называются генотипами особей данной популяции.

Шагом ГА является переход от текущего поколения к следующему, т.е. получение новой популяции
из
. В построении очередной особи новой популяции участвуют операторы кроссинговера (скрещивания), мутации и случайный оператор отбора,Select : B M
{1,…,M} действие которого состоит в выборе номера особи родителя при порождении очередного потомка.

Для определения ГА необходимо задать оператор кроссинговера Cross : BB
BB и оператор мутацииMut : B
B.

Действие кроссинговера
заключается в выборе случайным образом некоторой позицииj , равномерно распределенной от1 до N-1 , после чего результат формируется в виде

Влияние кроссинговера регулируют с помощью вероятности
срабатывания этого оператора (в противном случае все остается без изменений).

Рис. 1.16. Блок схема основных шагов фрактального кодирования изображения

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

Целевая функция исходной задачи, заменяется в ГА на неотрицательную функцию пригодности генотипа
, где
B.

Процесс работы алгоритма представляет собой последовательную смену поколений, на каждом шаге которой популяция
наполняется парами потомков от особей популяции
по формуле

где
- особи с наименьшей пригодностью популяции
. То есть индивиды извлекаются попарно из
и после кроссинговера и мутации помещаются в
. Изменение вероятностей мутации и кроссинговера позволяет регулировать работу ГА и настраивать его на конкретные задачи.

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

где в нижней части под знаком суммы – евклидово расстояние между исходным и преобразованным блоком. Данная функция удовлетворяет требования ГА (неотрицательна) и адекватна для оператора рулеточной селекции, при которой каждый индивид
популяции t оказывается родителем при формировании очередной особи
популяции  t+1 с вероятностью

.

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

Оператор мутации для данного алгоритма – стандартный, а оператор кроссинговера был модифицирован следующим образом:

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

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

Алгоритм 1.

Алгоритм 2.

Алгоритм восстановления изображения:

Создается два изображения одинакового размера А и Б. Размер изображений может быть не равен размеру исходного изображения. Начальный рисунок областей А и Б не имеет значения. Это могут быть случайные данные.

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

Данные из области Б преобразуются в область А. Этот шаг идентичен предыдущему, только изображения А и Б поменялись местами, т.е. теперь область А делится на блоки и ранговые области изображения Б отображаются на эти блоки.

Процедуры 2 и 3 повторяются до тех пор, пока изображения А и Б не станут неразличимыми.

Прямой и обратный ход (сжатие и восстановление) не эквивалентны по затратам. Прямое преобразование (сжатие) - значительно дольше, обратное преобразование (восстановление) - гораздо быстрее. Алгоритм фрактального сжатия - несимметричный алгоритм. Коэффициент симметричности (отношение времени архивации ко времени разархивации) колеблется в пределах 1000-10000.

К достоинствам фрактального метода можно отнести:

Высокие коэффициенты сжатия.

Высокую скорость обратного преобразования.

Возможность дальнейшего структурного анализа изображения .

При этом фрактальный метод обладает следующими недостатками:

Зависимостью результатов работы метода от принципов отбора базовых элементов и доменов.

Коэффициент сжатия зависит от повторяемости базовых элементов.

Алгоритм ориентирован на полноцветные изображения и изображения в градациях серого цвета. Фрактальное сжатие реализовано в формате FIF.

В настоящее время существует достаточно много алгоритмов сжатия изображений. Основой любых методов сжатия данных является использование естественной избыточности исходной информации. Сжатие изображений осуществляется либо в пространственной либо в частотной областях изображения. Наиболее яркими примерами пространственного сжатия изображений являются алгоритмы PCX, GIF, а частотного сжатия - JPEG.

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

В подобных алгоритмах можно выделить три основных шага:

Применение обратимых дискретных ортогональных преобразований к изображению.

Выбор наиболее значимых частотных коэффициентов.

Вторичное сжатие выбранных коэффициентов, например арифметическим или статистическим алгоритмом сжатия.

Фрактальный алгоритм

История фрактального сжатия

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

В 1981 году Джон Хатчинсон опубликовал статью "Фракталы и самоподобие", в которой была представлена теория построения фракталов с помощью системы итерируемых функций (IFS , Iterated Function System). Четыре года спустя появилась статья Майкла Барнсли и Стефана Демко, в которой приводилась уже достаточно стройная теория IFS. В 1987 году Барнсли основал Iterated Systems, компанию, основной деятельностью которой является создание новых алгоритмов и ПО с использованием фракталов. Всего через год, в 1988 году, он выпустил фундаментальный труд "Фракталы повсюду". Помимо описания IFS, в ней был получен результат, известный сейчас как Collage Theorem, который лежит в основе математического обоснования идеи фрактальной компрессии.

Первая статья об успехах Барнсли в области компрессии появилась в журнале BYTE в январе 1988 года. В ней не описывалось решение обратной задачи, но приводилось несколько изображений, сжатых с коэффициентом 1:10000, что было совершенно ошеломительно. Но практически сразу было отмечено, что несмотря на броские названия ("Темный лес", "Побережье Монтере", "Поле подсолнухов") изображения в действительности имели искусственную природу. Это, вызвало массу скептических замечаний, подогреваемых еще и заявлением Барнсли о том, что "среднее изображение требует для сжатия порядка 100 часов работы на мощной двухпроцессорной рабочей станции, причем с участием человека".

Отношение к новому методу изменилось в 1992 году, когда Арнауд Джеквин, один из сотрудников Барнсли, при защите диссертации описал практический алгоритм и опубликовал его. Этот алгоритм был крайне медленным и не претендовал на компрессию в 10000 раз (полноцветное 24-разрядное изображение с его помощью могло быть сжато без существенных потерь с коэффициентом 1:8 - 1:50); но его несомненным достоинством было то, что вмешательство человека удалось полностью исключить. Сегодня все известные программы фрактальной компрессии базируются на алгоритме Джеквина. В 1993 году вышел первый коммерческий продукт компании Iterated Systems. Ему было посвящено достаточно много публикаций, но о коммерческом успехе речь не шла, продукт был достаточно "сырой", компания не предпринимала никаких рекламных шагов, и приобрести программу было тяжело.

В 1994 году Ювал Фишер были предоставил во всеобщее пользование исходные тексты исследовательской программы, в которой использовалось разложение изображения в квадродерево и были реализованы алгоритмы оптимизации поиска. Позднее появилось еще несколько исследовательских проектов, которые в качестве начального варианта программы использовали программу Фишера. В июле 1995 года в Тронхейме (Швеция) состоялась первая школа-конференция, посвященная фрактальной компрессии.

Идея метода

Фрактальная архивация основана на том, что мы представляем изображение в более компактной форме – с помощью коэффициентов системы итерируемых функций (Iterated Function System – далее по тексту как IFS). Строго говоря, IFS представляет собой набор трехмерных аффинных преобразований , в нашем случае переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (х_координата, у_координата, яркость).

Наиболее наглядно этот процесс продемонстрировал Барнсли в своей книге "Fractal Image Compression". Там введено понятие Фотокопировальной Машины, состоящей из экрана, на котором изображена исходная картинка, и системы линз, проецирующих изображение на другой экран:

• Линзы могут проецировать часть изображения произвольной формы в любое другое место нового изображения.
• Области, в которые проецируются изображения, не пересекаются.
• Линза может менять яркость и уменьшать контрастность.
• Линза может зеркально отражать и поворачивать свой фрагмент изображения.
• Линза должна масштабировать (уменьшать) свой фрагмент изображения.

Расставляя линзы и меняя их характеристики, мы можем управлять получаемым изображением. Одна итерация работы машины заключается в том, что по исходному изображению с помощью проектирования строится новое, после чего новое берется в качестве исходного. Утверждается, что в процессе итераций мы получим изображение, которое перестанет изменяться. Оно будет зависеть только от расположения и характеристик линз, и не будет зависеть от исходной картинки. Это изображение называется "неподвижной точкой" или аттрактором данной IFS . Соответствующая теория гарантирует наличие ровно одной неподвижной точки для каждой IFS.

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

Наиболее известны два изображения, полученных с помощью IFS : "треугольник Серпинского" и "папоротник Барнсли".

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

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

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

Математические основы фрактального сжатия

Определение. Преобразование w:R 2 –> R 2 , представимое в виде

где a, b, c, d, e, f, p, q, r, s, t, u действительные числа и (x y z) принадлежит R 3 называется трехмерным аффинным преобразованием.

Определение. Пусть f:X –> X – преобразование в пространстве Х. Точка x f принадлежащая X такая, что f(x f)=x f называется неподвижной точкой (аттрактором) преобразования.

Определение. Пусть f:X–>X в метрическом пространстве (Х, d) называется сжимающим, если существует число s: 0 <= s < 1, такое, что d(f(x),f(y)) <= s * d(x,y) длялюбых x,y принадлежащих X.

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

Теорема (О сжимающем преобразовании). Пусть f:X –> X в полном метрическом пространстве (Х, d). Тогда существует в точности одна неподвижная точка x f принадлежащая X этого преобразования, и для любой точки x принадлежащей X последовательность {f n (x): n=0,1,2…} сходится к x f .

Более общая формулировка этой теоремы гарантирует нам сходимость.

Определение. Изображением называется функция S, определенная на единичном квадрате и принимающая значения от 0 до 1 или S(x,y) принадлежит для любых x,y принадлежащих .

Пусть трехмерное аффинное преобразование w f:R 3 –> R 3 , записано в виде

При этом, если интерпретировать значение S как яркость соответствующих точек, она уменьшится в p раз (преобразование обязано быть сжимающим) и изменится на сдвиг q.

Определение. Конечная совокупность W сжимающих трехмерных аффинных преобразований w i , определенных на областях D i , таких, что w i (D i) = R i и пересечение R i с R j является пустым множеством, называется системой итерируемых функций (IFS).

Системе итерируемых функций однозначно сопоставляется неподвижная точка – изображение. Таким образом, процесс компрессии заключается в поиске коэффициентов системы, а процесс декомпрессии – в проведении итераций системы до стабилизации полученного изображения (неподвижной точки IFS). На практике бывает достаточно 7-16 итераций. Области R i в именуются ранговыми, а области D i – доменными.

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

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

1. D i по размерам больше R i .
2. w i (R i) имеет ту же форму, размеры и положение, что и R i .
3. Коэффициент преобразования должен быть меньше единицы.
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 , а также разбиение изображения на домены.

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

Различия начинаются, если мы рассмотрим время, необходимое алгоритмам для архивации/разархивации. Так, фрактальный алгоритм сжимает в сотни и даже в тысячи раз дольше, чем JPEG . Распаковка изображения, наоборот, произойдет в 5-10 раз быстрее. Поэтому, если изображение будет сжато только один раз, а передано по сети и распаковано множество раз, то выгодней использовать фрактальный алгоритм.

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

Вытеснение JPEG фрактальным алгоритмом в повсеместном использовании произойдет еще не скоро (хотя бы в силу низкой скорости архивации последнего), однако в области приложений мультимедиа, в компьютерных играх его использование вполне оправдано.

Характеристики фрактального алгоритма

Коэффициенты компрессии: 2-2000 (Задается пользователем).

Класс изображений: Полноцветные 24 битные изображения или изображения в градациях серого без резких переходов цветов (фотографии). Желательно, чтобы области большей значимости (для восприятия) были более контрастными и резкими, а области меньшей значимости - неконтрастными и размытыми.

Симметричность: 100-100000.

Характерные особенности: Может свободно масштабировать изображение при разархивации, увеличивая его в 2-4 раза без появления "лестничного эффекта". При увеличении степени компрессии появляется "блочный" эффект на границах блоков в изображении.

Назад

К cодержанию

Вперёд

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

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

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

Основа метода фрактального кодирования - это обнаружение самоподобных участков в изображении. Впервые возможность применения теории систем итерируемых функций к проблеме сжатия изображения была исследована Майклом Барнсли (англ. Michael Barnsley и Аланом Слоуном (англ. Alan Sloan).

Майкл Барнсли.

Они запатентовали свою идею в 1990 и 1991 годах. Фрактальная архивация основана на том, что с помощью коэффициентов системы итерируемых функций изображение представляется в более компактной форме. Наиболее наглядно этот процесс продемонстрировал сам Барнсли в своей книге "Фрактальное сжатие изображения". В ней введено понятие Фотокопировальной Машины, состоящей из экрана, на котором изображена исходная картинка, и системы линз, проецирующих изображение на другой экран. Каждая линза проецирует часть исходного изображения. Расставляя линзы и меняя их характеристики, можно управлять получаемым изображением. На линзы накладывается требование: они должны уменьшать в размерах проектируемую часть изображения. Кроме того, они могут менять яркость фрагмента и проецируют не круги, а области с произвольной границей.

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

Наиболее известны два изображения, полученных с помощью СИФ: треугольник Серпинского и папоротник Барнсли. Первое задается тремя, а второе - пятью аффинными преобразованиями (или, в нашей терминологии, линзами). Каждое преобразование задается буквально считанными байтами, в то время, как изображение, построенное с их помощью, может занимать и несколько мегабайт.

Папоротник Барнсли (слева) и треугольник Серпинского (справа).

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

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

Применение фракталов в медицине.

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

Примеры фракталоподобных структур в организме человека: бронхи, сосуды, мышцы.

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

Пример кардиограммы.

Также фракталы могут использоваться (пока на стадии успешных экспериментов) в обработке медицинских рентгеновских изображений.

Пример рентгеновского снимка.

Рентгеновские снимки обработанные с помощью фрактальных алгоритмов дают более качественную картинку а соответственно и более качественную диагностику!!

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

Пример электрогастроэнтерограммы.

Он основан на регистрации изменений электрического потенциала от органов ЖКТ, то есть снятие электрогастроэнтерограмм (ЭГЭГ). Применение фрактального анализа к получаемым биоэлектрическим сигналам от органов, позволяет эффективно судить о моторной функции органов и ЖКТ и успешно диагностировать различные заболевания.

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

Карты адгезии поверхностей раковых и нормальных клеток

Применение фракталов в естественных науках.

Применение фракталов в естественно-научных дисциплинах чрезвычайно огромно. Если описывать всё, то не хватит и целой книги. Поэтому остановимся на некоторых самых интересных аспектах.

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

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

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

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

Пример твёрдого тела - кристаллы.

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

Турбулентность.

Применение фракталов в телекоммуникациях.

В телекоммуникациях фракталы используются для создания фрактальных антенн. Фрактальные антенны – относительно новый класс электрически малых антенн (ЭМА), принципиально отличающийся своей геометрией от известных решений. По сути, традиционная эволюция антенн базировалась на евклидовой геометрии, оперирующей объектами целочисленной размерности (линия, круг, эллипс, параболоид и т. п.). Фрактальная антенны с удивительно компактным дизайном обеспечивает превосходную широкополосную производительность в маленьком форм-факторе. Достаточно компактны для установки или встраивания в различных местах, фрактальные антенны используются для морских, воздушных транспортных средств, или персональных устройств. На изображении выше пример фрактальной антенны.

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

Фракталы как элементы визуализации и спецэффектов.

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

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

Моделирование ландшафта на основе фрактальных алгоритмов с помощью программы Fractal Landscapes.

Скриншот игры Minecraft.

Не обходится без фракталов и в кино. По сути в кино для создания различных фантастических пейзажей, как и в играх используются тот же принцип. Действительно, зачем каждый раз создавать новое дерево или гору, тратя на это кучу времени, когда всё это можно во много раз быстрее сделать с помощью компьютерных программ работающих на фрактальных алгоритмах. Интересный факт: в известном космическом хорроре Ридли Скотта "Чужой" в эпизоде когда команда спускается на поверхность планеты, монитор в корабле передаёт изображение поверхности планеты в виде сетки. Как раз таки это изображение и было создано при помощи фрактальной геометрии. Фрактальная геометрия позволяет художникам по спецэфффектам без труда создавать такие объекты как облака, дым, пламя, звёздное небо и т.д.

Теперь немного затронем тему фрактальной анимации. Фрактальные изображения, созданные в различных генераторах необычайно красивы. Что уж тогда говорить о фрактальной анимации, это действительное потрясающее зрелище. В первую очередь здесь стоит упомянуть о ресурсе Electric sheep. Electric sheep - ресурс использующий распределённые вычисления для создания фрактальной анимации основанной на алгоритме fractal flame (разработан Скотом Дрейвсом). Проще говоря на ваш компьютер устанавливается программное обеспечение, которое использует вашу машину для вычисления и рендера фрактальной анимации, одновременно с этим загружая и демонстрируя вам уже готовую фрактальную анимацию в виде так называемых "живых" обоев. При этом эти самые обои сохраняются на компьютере в определённой папке и их можно оттуда вытащить, чтобы затем использовать для своих целей, например в видеомонтаже (правда длина роликов коротковата - 5 секунд). Но имея в своём распоряжении программу Апофизис и скрипт к ней Apophymator, вы сможете без особого труда создавать свою анимацию (благо уроков по этой теме в сети множество) сколь угодно длинную, главное чтобы ваша машина была достаточно мощной.

Скриншоты анимации Electric sheep:

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

Фрактальную анимацию в качестве визуализации используют разработчики программ напрямую не относящиеся к фракталогенераторам. К примеру хорошо известный проигрыватель Winamp имеет в своём наборе большое количество визуализаций (плагин milkdrop) в которых явно прослеживаются элементы фракталов (например анимированное множество Жюлиа). Скриншоты визуализаций в плагине milkdrop для проигрывателя Winamp:

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

Оригинал статьи можно прочесть в мартовском номере журнала Компьюарт.

В радиотехнике и теории связи фракталы позволили разработать высокоэффек­тивные методы сжатия информации. В 1988 г. известный американский специалист в теории динамических систем и эргодической теории Барнсли (Barnsley) предло­жил некоторые идеи для сжатия и хранения графической информации. Он назвал свой метод фрактальным сжатием информации. Происхождение названия связано с тем, что геометрические образы, возникающие в этом методе, обычно имеют фрактальную природу в смысле Мандельброта.

Фрактальное сжатие основано на том, что изображение представляется в бо­лее компактной форме с помощью коэффициентов так называемой системы итерируемых функций (Iterated Function System - IFS ). Система итерирую­щих функций - это совокупность сжимающих аффинных преобразований. Как известно, аффинные преобразования - геометрические преобразования плоскости или пространства, включающие в себя масштабирование, поворот и параллельный перенос, при котором фигуры сохраняют свои свойства. В изображениях преобразованию подвергаются точки в трехмерном пространст­ве (координата X , координата Y , яркость). По существу IFS представляет со­бой систему из некоторого фиксированного класса функций, отображающих одно многомерное множество на другое. Аффинное преобразование считается сжимающим, если коэффициент масштабирования меньше единицы.

Наиболее наглядна процесс сжатия информации Барнсли продемонстри­ровал в своей книге «Fractal Image Compression» (Фрактальное сжатие изо­бражения). Там введено понятие Фотокопировальной Машины (рис. 2.69), состоящей из экрана, на котором изображена исходная картинка, и системы линз, проецирующих изображение на другой экран. На линзы накладывается ряд специфических требований:

линзы могут проецировать часть изображения произвольной формы в любое другое место нового изображения;

области, в которые проецируются изображения, не пересекаются;

линзы могут менять яркость и уменьшать контрастность;

линзы могут зеркально отражать и поворачивать свой фрагмент изобра­жения;

Линзы должны уменьшать (масштабировать) свой фрагмент изображения.

Каждая линза проецирует часть исходного изображения. Расставляя линзы и меняя их характеристики, можно управлять получаемым изображением. Одна итерация работы Машины заключается в том, что по исходному изо­бражению с помощью проектирования строится новое, после чего новое бе­рется в качестве исходного. В процессе итераций получается изображение, которое перестанет изменяться. Оно будет зависеть только от расположения и характеристик линз, и не будет зависеть от исходной картинки. Это изобра­жение является аттрактором данной IFS. Соответствующая теория гарантиру­ет наличие ровно одного аттрактора для каждой IFS.

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

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

Рассмотрим фрактальный алгоритм, который преобразует изображение не­которым заданным способом. Например, этот способ предполагает уменьше­ние линейных размеров исходного изображения (например, рисунок «улыбающееся лицо») в два раза и тройное его копирование (рис. 2.70).

Пусть имеется три разных изображения: «улыбающееся лицо», буква А и салфетка Серпинского, показанных слева на рис. 2.71. Если процесс выбран­ного способа преобразования повторять к данным изображениям итеративно несколько раз, то возникающие из различных исходных изображений рисун­ки станут похожими друг на друга.

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

оно не зависит от начального изображения, поскольку при достаточно большом числе итераций исходное изображение уменьшится до аттрактора (точки);

оно определяется исключительно процедурой преобразования;

последующие преобразования преобразуют его в самое себя;

оно может иметь сколь угодно мелкие детали.

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

На практике достаточно большое количество преобразований можно описать с помощью матричного уравнения, определяющего линейное преобразование координат x и у:

где a i , b i , c i , d i , g i , и h i - параметры аффинного преобразования.

На рис. 2.72 показаны ряд процедур преобразования и их аттракторов.

Последний случай (рис. 2.72, в - правый крайний рисунок) относится к так называемому «папоротнику Барнсли». Это внешне сложное изображение полу­чено за счет четырех аффинных преобразований, каждое из которых имеет шесть параметров (см. уравнение (2.281)). С аналитической точки зрения тот же папоротник Барнсли создается с помощью IFS четырьмя аффинными преобра­зованиями (в нашей терминологии «линзами»). Каждое преобразование кодиру­ется буквально считанными байтами, в то время как изображение, построенное с их помощью, может занимать и несколько мегабайт.

Если для штрихового изображения папоротника Барнсли перемножить число преобразований (4), число параметров (6) и число бит под хранение каждого из параметров (например 32), то получим 4 х 6 х 32 = 768 бит - столько бит необ­ходимо для хранения способа получения этого изображения. В то же время изо­бражение папоротника (1 бит/пиксел) имеет разрешение 256 х 256 пиксел. Для прямого хранения такого изображения необходимо 65536 бит, т. е. рассматри­ваемая схема позволяет «сжать» изображение примерно в 85 раз. Такое опреде­ление коэффициента сжатия в некоторой мере условно. Дело в том, что для хра­нения алгоритма преобразования требуется определенное, заранее известное, количество бит. Но этот алгоритм позволяет создать изображение любого раз­мера с достаточно мелкими деталями, для хранения которого требуется другое (возможно, большее) число друг на друга бит. Соответственно размеру изображения будет меняться и коэффициент сжатия. Возникает вопрос: можно ли для любой детали изображения подобрать деталь, которая после некоторых преобразований станет достаточно похожей на исходную?

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

где х, у - координаты пикселов.

Пусть z имеет 256 фиксированных уровней. Само аффинное преобразова­ние /-го блока полутонового изображения имеет вид:

где a i , b i , c i , d i , g i , и h i - параметры аффинного преоб­разования; s i , r i - коэффициенты преобразования контраста и яркости блока.

Теперь исходное изображение необходимо разбить на блоки (домены), для которых будут подбираться подобные блоки (ранговые области). Вычисление оп­тимальных коэффициентов преобразования контраста и яркости квадратов путем минимизации среднеквад­ратичной разности яркостей пикселов домена и кан­дидата в ранговую область может быть произведено по разным формулам, приведенным в специальной литературе.

Итак, понятие фрактала привело к развитию новойматематической модели, дающей единое описание форм, присущих многим природным явлениям. Оказывается, природа устроена так, что именно фрак­тальные модели хорошо описывают многие реальные объекты, структура кото­рых не отражается традиционными моделями. Этим объясняется современная популярность фрактального подхода к анализу различных объектов и процессов в физике, радиотехнике, системах передачи информации и др. В частности, сей­час большое внимание специалистов уделяется разработке широкополосных фрактальных антенн (рис. 2.73).

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