ВУЗ:
Составители:
Рубрика:
3. Дискретное WaveLet преобразование (DWT).
Фрактальное сжатие изображений
Всё началось в 1904 году, когда малоизвестный немецкий математик фон Кох, изучая работы Георга Кантора и Карла
Вейерштрассе, натолкнулся на описания некоторых "странных" кривых с необычным "поведением".
Странность заключалась в том, что любой, даже ничтожно малый отрезок кривой в точности повторяет по свойствам
саму кривую.
Взяв лист бумаги, Кох принялся выстраивать "собственную" линию, нисколько не догадываясь, что отныне она на-
всегда войдет в математические анналы под именем "снежинки" Коха (рис. 4.10).
Рождение фрактальной геометрии обычно связывают с выходом в 1977 году книги Бенуа Мандельброта "Фракталь-
ная геометрия природы".
Именно он ввёл термин фрактал (от английского "fractional" – дробный). Одна из основных идей книги заключалась
в том, что средствами традиционной геометрии (т.е. используя линии и поверхности), чрезвычайно сложно представить
природные объекты. Фрактальная геометрия задаёт их очень просто.
В 1981 году Джон Хатчинсон опубликовал статью "Фракталы и самоподобие", в которой была представлена теория
построения фракталов с помощью системы итерируемых функций (IFS, Iterated Function System). Четыре года спустя
появилась статья Майкла Барнсли и Стефана Демко, в которой приводилась уже достаточно стройная теория IFS. В 1987
году
Рис. 4.10. Фрактальные кривые ("снежинка" Коха)
Барнсли основал Iterated Systems, компанию, основной деятельностью которой является создание новых алгоритмов и ПО
с использованием фракталов. Всего через год, в 1988 году, он выпустил фундаментальный труд "Фракталы повсюду".
Помимо описания IFS, в ней был получен результат, известный сейчас как Collage Theorem, который лежит в основе ма-
тематического обоснования идеи фрактальной компрессии.
Если построение изображений с помощью фрактальной математики можно назвать прямой задачей, то построение
по изображению IFS – это обратная задача. Довольно долго она считалась неразрешимой, однако Барнсли, используя
Collage Theorem, построил соответствующий алгоритм. В 1990 и 1991 годах эта идея была защищена патентами. Если
коэффициенты занимают меньше места, чем исходное изображение, то алгоритм является алгоритмом архивации.
Первая статья об успехах Барнсли в области компрессии появилась в журнале BYTE в январе 1988 года. В ней не
описывалось решение обратной задачи, но приводилось несколько изображений, сжатых с коэффициентом 1:10000, что
было совершенно ошеломительно. Но практически сразу было отмечено, что несмотря на броские названия ("Тёмный
лес", "Побережье Монтере", "Поле подсолнухов"), изображения в действительности имели искусственную природу. Это
вызвало массу скептических замечаний, подогреваемых ещё и заявлением Барнсли о том, что "среднее изображение тре-
бует для сжатия порядка 100 часов работы на мощной двухпроцессорной рабочей станции, причём с участием человека".
Отношение к новому методу изменилось в 1992 году, когда Арнауд Джеквин, один из сотрудников Барнсли, при за-
щите диссертации описал практический алгоритм и опубликовал его. Этот алгоритм был крайне медленным и не претен-
довал на компрессию в 10000 раз (полноцветное 24-разрядное изображение с его помощью могло быть сжато без сущест-
венных потерь с коэффициентом 1:8 – 1:50). Но его несомненным достоинством было то, что вмешательство человека
удалось полностью исключить. Сегодня все известные программы фрактальной компрессии базируются на алгоритме
Джеквина. В 1993 году вышел первый коммерческий продукт компании Iterated Systems. Ему было посвящено достаточ-
но много публикаций, но о коммерческом успехе речь не шла, продукт был достаточно "сырой".
Фрактальная архивация основана на том, что с помощью коэффициентов системы итерируемых функций изображе-
ние представляется в более компактной форме. IFS – это набор трёхмерных преобразований подобия, переводящих одно
изображение в другое. Преобразованию подвергаются точки в трёхмерном пространстве (x-координата, у-координата,
яркость). Наиболее наглядно этот процесс продемонстрировал сам Барнсли в своей книге "Фрактальное сжатие изобра-
жения". В ней введено понятие Фотокопировальной Машины, состоящей из экрана, на котором изображена исходная
картинка, и системы линз, проецирующих изображение на другой экран. Каждая линза проецирует часть исходного изо-
бражения. Расставляя линзы и меняя их характеристики, можно управлять получаемым изображением. На линзы накла-
Страницы
- « первая
- ‹ предыдущая
- …
- 25
- 26
- 27
- 28
- 29
- …
- следующая ›
- последняя »
