Лекции / Лекция 9

//Лекция 9// Фрактальная графика

Фрактал – это объект, отдельные элементы которого наследуют свойства родительских структур.

Фрактальными свойствами обладают многие природные объекты, такие как снежинка, кристаллы, растения.

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

Сейчас исследование фракталов развивается по 2-м направлениям:

1. Фрактал – наилучшее направление живой природы

2. Фрактал как способ сжатия информации

Фрактальная геометрия появилась в конце 70-х годов.

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

В 1977г. Мандельброт издал книгу «Фрактальная геометрия в природе». Это и считается началом фрактальной графики и геометрии. В любом фрактале найдется такая часть, которая содержит информацию о всем фрактале.

Построение геометрического фрактала

Фракталы в 2-хмерном случае получают с помощью некоторой ломанной. В 3-хмерном случае некоторой поверхностью, называемой генератором.

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

Для снежинки Кох в 1-ом поколении каждый отрезок заменяется на 4 звена каждое по 1/3 отрезка.

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

Кривая n-го поколения при любом конечном n называется предфракталом. При n → ∞ получится фрактал.

Построение графического фрактала

Выбирается точка на комплексной плоскости.

Действуем на нее отображением х → х² + с, в результате чего точка перемещается на плоскость. На полученную точку повторно действуем отображением.

Если в результате точка убегает на бесконечность, красим ее в один цвет, если прыгает вокруг исходного положения, то красим ее в черный цвет. Эти действия повторяем для всех точек плоскости. Таким образом получаем 2-хцветный фрактал – он называется множеством Жулиа. Форма множества Жулиа меняется в зависимости от коэффициента с.

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

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

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

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

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

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

Наиболее популярен метод кодирования Fractal Transform. Именно он был предложен в 1986г. Майклом Барнсли. Это был первый алгоритм для математического описания, примененный для реального растрового изображения.

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

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

1. Возможность масштабирования фрактальных изображений без введения артефактов и потери деталей. Процесс фрактальной панарамизации не зависит от разрешения растрового изображения. Масштаб ограничивается только объемом свободной памяти компьютера.

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

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

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

Фрактальное сжатие – процесс ассиметричный. Сжатие длится в 1000 и 10000 раз дольше, чем распаковка. Фрактальное сжатие применяется в базах данных изображений.

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

Более эффективно сжимаются изображения с битовой глубиной 24 и 32 бита на пиксель, чем 8-битовые полутоновые изображения.

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