Краткий
обзор
Я не стану повторять здесь то,
что уже написано о фракталах за последние
пятнадцать лет, этих компиляций и без меня
хватает на Web-страницах , а сразу приведу
несколько стандартных фрактальных рисунков вместе с формулами их
изготовления. Подробности можно прочитать и
самим, а я со своей стороны готов дать некоторые
разъяснения интересующимся.
Все формулы взяты из основополагающей работы Barnsley
M. "Fractals Everywhere", 1988. Книга эта
доступна, например, в Ленинке (РГБ), в зале для
чтения микрофишей или в ГПНТБ. Она особенно
хороша тем, что в ней много различных примеров и
задач.
Почему же такое внимание было уделено
фракталам?
А это из-за их регулярной структуры. Собственно
говоря из многообещающих приложений остались
лишь два: рисование (фактуры поверхностей,
имитация природных объектов) и сильное сжатие
изображений с потерей информации. Коэффициент
сжатия аналогичен методу JPEG.
Как можно увидеть в правой части таблицы,
количество параметров, задающих рисунок
несколько десятков, размер растрового рисунка в
пикселах можете вычислить сами. Затем разделите
эти два числа друг на друга и получите
многообещающий коэффициент сжатия, что и
послужило основанием для учреждения новой фирмы Iterated Systems, Inc
Поэтому у Barnsley M. и возникла
идея использовать фрактальное представление
изображений для их сжатия, которую реализовал
его аспирант Jacquin A., защитив докторскую
дисертацию около десяти лет назад.
После нескольких лет упорных исследований по
решению вставших практических проблем метод был
оконательно реализован. Краткую историю
становления метода вы можете прочесть здесь (извините,
адрес есть, а сама страница исчезла, позднее сам
добавлю несколько слов).
Сейчас Iterated Systems объединилась еще с одной фирмой
и предлагает услуги по поиску изображений в
Интернет по предъявляемому фрагменту, подобно
тому, как вы ищете страницы по набору слов..
Основываясь на идеях Jacquin A. и Barnsley
M. несколько других исследователей
разработали свои методы фрактального сжатия. С
ними можно познакомиться, например, по книге Y.
Fisher "Fractal Image Compression: Theory and
application", N.Y. 1995, доступной,например в
библиотеке БЕН (читайте ниже).
|
К слову говоря, формула для рисунков
одна - это т.н. афинное (линейное) преобразование
Евклидовой плоскости. А параметры у этого
преобразования могут быть какими угодно. От них
то и зависит все многообразие фракталов.Афинное
преобразование имеет следующий вид:
y = Ax + F,
где y=(y1, y2) и x=(x1, x2) - это
двумерные векторы,
A - это матрица размером 2 на 2,
F - это также двумерный вектор сдвига.
Метод сводится к чередующемуся
применению афинных преобразований из заданного
набора к каждому очередному образу точки.
Последовательность применения регулируется
заданными вероятностями P.
Все приводимые преобразования
состоят из четырех таких
"подпреобразований". Параметры каждого из
них сведены в таблицу:
| |
|
A |
F |
|
| Название |
№ |
a |
b |
c |
d |
e |
f |
P |
Треугольник
Серпинского |
1 |
0.5 |
0 |
0 |
0.5 |
1 |
1 |
1/3 |
| 2 |
0.5 |
0 |
0 |
0.5 |
50 |
1 |
1/3 |
| 3 |
0.5 |
0 |
0 |
0.5 |
50 |
50 |
1/3 |
| 4 |
0.5 |
0 |
0 |
0.5 |
50 |
50 |
0 |
| Лист
Папортника (Fern) |
1 |
0 |
0 |
0 |
0.16 |
0 |
0 |
0.01 |
| 2 |
0.85 |
0.04 |
-0.04 |
0.85 |
0 |
1.6 |
0.85 |
| 3 |
0.2 |
-0.26 |
0.23 |
0.22 |
0 |
1.6 |
0.07 |
| 4 |
-0.15 |
0.28 |
0.26 |
0.24 |
0 |
0.44 |
0.07 |
Дерево |
1 |
0 |
0 |
0 |
0.5 |
0 |
0 |
0.05 |
| 2 |
0.42 |
-0.42 |
0.42 |
0.42 |
0 |
0.2 |
0.04 |
| 3 |
0.42 |
0.42 |
-0.42 |
0.42 |
0 |
0.2 |
0.04 |
| 4 |
0.1 |
0 |
0 |
0.1 |
0 |
0.2 |
0.15 |
Где P - это вероятность применения
именно этой строки параметров. Желательно, чтобы
сумма вероятностей была равна единице.
Матрица преобразования A:
- (a, b) - первая строка матрицы,
- (c, d) - ее вторая строка.
Вектор сдвига F= (e, f). Этим
параметром определяются размеры рисунка,
поэтому приведенные значения для него весьма
условны. (В демонстрационных примерах я
использовал иные значения).
Вы можете загрузить демо-версии вместе с
исходным текстом:
frac_dos.zip (34 793 байт) (QuikBasic для
DOS),
fractal_VB5.zip (14 134 байта) (Visual
Basic для Win 98-2000, понадобится установленная DLL-билиотека). |
|
Книга Y. Fisher послужит ценным
вводным курсом в теорию методов Фрактального
Сжатия, изложенную четко и ясно. В ней в начале
рассматриваются соответствующие теоремы,
основанные на теории множеств. Среди них три
центральные теоремы:
О сжимающем преобразовании,
Collage Theorem,
Теорема о непреравной зависимости
предельной неподвижной точки от параметров,
составляющих фрактальное преобразование.
Также в ней рассматриваются сразу
несколько разных фрактальных методов сжатия
неподвижных и видео изображений. Приводятся
тексты программ на языке СИ с комментариями и
разъяснениями для
кодирования и декодирования изображений
фрактальным методом самого Y. Fisher,
который (метод) носит название QuadTree-метод
(метод иерархической организации Доменов
разбиением некоторых из них на квадранты).
Интересна и страница самого Y. Fisher (лучшая из
просмотренных мною на эту тему), со множеством
различных ссылок на другие страницы, в т.ч. и по
теме Fractal Image Compression.
В частности одна из ссылок приведет к огромной
библиотеке статей и программ на эту тему.
К сожалению большинство подборок и
изображений доступны только в виде *.gz-файлов,
которые сами перед этим были сохранены в
PostScript-формате (*.ps). Еще вам может понадобиться
разархиватор для *.tar-файлов. Все это видимо из-за
UNIX. |
Идея, на
которой основаны фрактальные методы
В качестве отправной точки для всех
фрактальных методов сжатия была взята известная теорема
Банаха о сжимающем преобразовании:
Каждое сжимающее преобразование
полного метрического пространства в себя имеет
неподвижную точку.
Используя результаты Jacquin A.,
строится точка (множество на плоскости), к
которой будет сходиться последовательность
итеративно преобразованных точек. Эта
предельная точка-множество не должна сильно
отличаться от искомой точки-изображения. Тогда
внешний вид восстановленного изображения не
будет сильно отличаться от исходного.
На практике подобрать формулу фрактала ко
всему, обычно большому, изображению - несбыточная
мечта, поэтому поступают стандартным способом -
разбивают изображение на отдельные маленькие
фрагменты, для каждого из которых строят свое
преобразование. Одновременно решается вопрос
быстродействия. Этими-то фрагментами и
ограничивается итоговая степень сжатия.
Неудивительно поэтому, что, судя по
результатам сравнения с
JPEG, проведенного Oleg Lavrovsky (теперь эта
страница недоступна), фрактальные методы
имеют преимущество только, если позволительно
иметь большие искажения. (Этот отчет выдается
за исследовательский результат, достойный
научной публикации). Сравнения были проведены
только на нескольких примерах без анализа
причин.
Тем не менее, на мой взгляд этот метод
должен использоваться наравне с JPEG, чего на
практике не заметно. Я думаю, что налицо
корпоративный сговор, а может еще и потому, что
фрактальные методы в НЕСКОЛЬКО раз более
наукоемки, чем JPEG, что создает трудности в
понимании его руководителями разработок от
бизнеса. Может я ошибаюсь? |
