1. Фракталы и история возникновения метода фрактального сжатия
Понятия «фрактал» и «фрактальная геометрия» (fractus – состоящий из фрагментов, лат.) были предложены математиком Б. Мандельбротом в 1975 г. для обозначения нерегулярных, но самоподобных структур. Рождение фрактальной геометрии связывают с выходом в 1977 г. книги Б. Мандельброта «Фрактальная геометрия природы», в которой объединены в единую систему научные результаты учёных, работавших в период 1875-1925 гг. в этой области (Пуанкаре, Жюлиа, Кантор и др.).
Одним из основных свойств фракталов является самоподобие. В самом простом случае небольшая часть фрактала содержит информацию о всём фрактале.
С точки зрения машинной графики, фрактальная геометрия незаменима при генерации сложных неевклидовых объектов, образы которых весьма похожи на природные, и когда требуется с помощью нескольких коэффициентов задать линии и поверхности очень сложной формы.
Существует большое разнообразие фракталов. Потенциально наиболее полезным видом фракталов являются фракталы на основе системы итеративных функций (Iterated Function System – IFS). Метод IFS применительно к построению фрактальных изображений, изобретённый большим их знатоком Майклом Барнсли (Michael Barnsley) и его коллегами из Технологического института шт. Джорджия (Georgia Institute of Technology), базируется на самоподобии элементов изображения и заключается в моделировании рисунка несколькими меньшими фрагментами его самого. Специальные уравнения позволяют переносить, поворачивать и изменять масштаб участков изображения; таким образом, эти участки служат компоновочными блоками остальной части картины.
Одним из наиболее поразительных (и знаменитых) IFS-изображений является чёрный папоротник, в котором каждый лист в действительности представляет собой миниатюрный вариант самого папоротника (см. рис.). Несмотря на то, что картинка создана компьютером методом аффинных преобразований, папоротник выглядит совершенно как настоящий. Выдвинуто предположение, что природа при кодировании генетической структуры растений и деревьев пользуется чем-то близким к методу IFS-фракталов.
IFS-фракталы имеют одно вполне реальное и полезное применение: с их помощью можно сжимать большие растровые изображения до долей их нормальных размеров. Этот утверждение следует из теоремы Банаха о сжимающих преобразованиях (также известной как Collage Theorem) и является результатом работы исследователя Технологического института шт. Джорджия Майкла Барнсли в области IFS. Вооружившись этим выводом, он ушёл из института, запатентовал своё открытие и основал компанию Iterated Systems Incorporated. О своём достижении он рассказал миру в журнале Byte за январь 1988 г. Однако там отсутствовали какие-либо сведения о решении обратной задачи: как по заданному изображению найти аффинные преобразования. К тому моменту у этой задачи не было даже намёка на решение. В статье Барнсли было показано несколько реалистичных фрактальных изображений, но все они были созданы вручную.
В идеале хотелось бы уметь находить для любого изображения систему аффинных преобразований (IFSM), воспроизводящую изображение с заданной точностью. Однако решение находилось немного в стороне. Первым нашёл его именно студент Барнсли, Арно Жакан (Arnaud Jacquin). Предложенный метод получил название «Система итерируемых кусочно-определённых функций» (Partitioned Iterated Function System – PIFS). Согласно этой схеме, отдельные части изображения подобны не всему изображению, а только его частям.
Итак, рассмотрим математическое обоснование возможности фрактального сжатия.
Есть отображение , где – множество всех возможных изображений. W является объединением отображений w i :
где R – изображение, а d i – какие-то (возможно, перекрывающиеся) области изображения D . Каждое преобразование w i переводит d i в r i . Таким образом:
Будет логично представить изображение в виде функции двух переменных f (x, y) . На множестве всех таких функций введём метрику (расстояние между изображениями), например, таким образом:
Согласно теореме Банаха, существует определённый класс отображений, для которых существует константа c < 1 такая, что для любых изображений f и g выполняется неравенство
Такие отображения называются сжимающими , и для них справедливо следующее утверждение:
Если к какому-то изображению F 0 мы начнём многократно применять отображение W таким образом, что то в пределе, при i , стремящемся к бесконечности, мы получим одно и то же изображение вне зависимости от того, какое изображение мы взяли в качестве F 0 :
Это конечное изображение F называют аттрактором , или неподвижной точкой отображения W . Также известно, что если преобразования w i являются сжимающими, то их объединение W тоже является сжимающим.
С учётом вышесказанного, схема компрессии выглядит так: изображение R разбивают на кусочки r i , называемые ранговыми областями . Далее для каждой области r i находят область d i и преобразование w i такие, что выполняются следующие условия:
Первые три условия означают, что отображение w i будет сжимающим. А в силу четвёртого условия кодируемое изображение R и его образ W (R) будут похожи друг на друга. В идеале R = W (R) . А это означает, что наше изображение R и будет являться неподвижной точкой W . Именно здесь используется подобие различных частей изображения (отсюда и название – «фрактальная компрессия» ). Как оказалось, практически все реальные изображения содержат такие похожие друг на друга, с точностью до аффинного преобразования, части.
Таким образом, для компрессии изображения W нужно:
Соответственно, для декомпрессии изображения нужно будет:
Пусть дано изображение M x N точек (где M и N кратны 8), 256 градаций серого. Ранговые и доменные области будем брать квадратными. Исходное изображение разобьём на ранговые области размером 8 х 8 точек. Доменные области будем искать размером 16 х 16 точек путём перебора всех возможных положений. Существует всего 8 аффинных преобразований, переводящих квадрат в квадрат (повороты на 0°, 90°, 180°, 270°, зеркальные отражения относительно центральной горизонтали, центральной вертикали, от главной и побочной диагоналей). Осталось найти только коэффициенты для преобразования цвета. Но значения u и v (контрастности и яркости) можно легко найти аналитически.
Если есть две последовательности значений цвета пикселов a 1 , a 2 , …, a N (доменной области) и b 1 , b 2 , …, b N (ранговой области), то можно минимизировать среднеквадратичное отклонение цвета пикселов, представляющее собой вариант метрики различия изображений:
Для этого достаточно приравнять частные производные R по u и по v к нулю, и решить уравнение относительно u и v . Получатся такие выражения:
при этом, если
Итак, какие же данные необходимо хранить в результате. Сетка разбиения на ранговые области постоянная для всех изображений, её хранить не надо. Остаётся положение ранговых областей (верхнего левого угла), номер преобразования и коэффициенты яркости и контрастности.
Размер данных для полного определения ранговой области рассчитывается по формуле:
где X – количество бит, необходимых для хранения координат нижнего левого угла домена, T – количество бит, необходимых для хранения типа аффинного преобразования, U и V – для хранения коэффициентов контраста и яркости.
где Nb и Mb – количество бит, необходимых для хранения каждой из координат, рассчитываются по следующим формулам:
Здесь CEIL – функция округления до максимального целого, Md и Nd – количество доменов, умещающихся по горизонтали и вертикали, которые рассчитываются по формулам:
где V и H – вертикальный и горизонтальный размеры изображения, Size – размер доменного блока, Step – шаг поиска доменной области.
Для хранения преобразования T необходимо 3 бита.
Для хранения U и V необходимо 9 и 7 бит соответственно.
Для примера возьмём изображение размером 256 x 256 пикселей, и будем исследовать доменную область с шагом 4 пикселя.
Nd = Md = (256 - 8 + 1) / 4 = 62
Nb = Mb = CEIL (log 2 62) = 6
Z = 12 + 3 + 6 + 6 = 27
Коэффициент сжатия S составляет
S = (8 * 8 * 8) / 27 = 19
Коэффициент сжатия не так велик, как хотелось бы, но и параметры сжатия далеко не оптимальны, и коэффициент может увеличиваться в разы.
А теперь оценим вычислительную сложность данного алгоритма. На этапе компрессии мы должны перебрать все доменные области – 1 024 штуки, для каждой – все ранговые – 58 081 штука (при шаге 1), а для каждой из них, в свою очередь, – все 8 преобразований. Итого получается 1 024 х 58 081 х 8 = 475 799 552 действия. При этом эти действия не тривиальны и включают несколько матричных операций, которые, в свою очередь, включают операции умножения и деления чисел с плавающей точкой.
К сожалению, даже на современном ПК (а именно для таких машин хотелось реализовать алгоритм) понадобится недопустимо много времени для того, чтобы сжать изображение размером всего 256 х 256 пикселов. Очевидно, что рассмотренный алгоритм нуждается в оптимизации.
Алгоритм нуждается в оптимизации по нескольким направлениям: по скорости, по качеству получаемого изображения, по степени компрессии.
Для снижения вычислительных затрат можно предпринять следующие меры:
Для улучшения качества: в случае необнаружения доменной области, удовлетворяющей заданному E , ранговую область можно разбить на 4 подобласти и произвести поиск домена для каждой из них. Это можно делать и дальше рекурсивно, до достижения некоторого минимального размера либо единичного пиксела. Но это увеличит вычислительные затраты и снизит коэффициент сжатия.
Для увеличения коэффициента компрессии можно идентифицировать однотонные блоки. Однотонным блоком будем называть ранговую область, у которой среднеквадратичное отклонение от собственного среднего значения не превышает некоторого E" . При этом в выходной файл будет записана только средняя яркость точки, за счёт чего будет достигнуто сжатие 1 к 64 (для ранговых областей размером 8).
В данной статье описываеться лишь простейший вариант алгоритма фрактального сжатия. Майкл Барнслн и Алан Слоун нашли метод решения данной задачи, который действует в отношении любого растрового изображения, даже если в нём не заметны очевидные элементы самоподобия. Все подробности этого метода не обнародованы, но то обстоятельство, что пакет Microsoft Encarta использует библиотеку сжатия Барнсли, служит достаточным свидетельством в пользу его эффективности и обшей применимости к изображениям всех типов.
О методе Барнсли-Слоуна нам известно лишь то, что с помощью стандартных приёмов обработки изображений (кстати, описание многих из них Вы так же можете найти на этом сайте), таких, как выделение краёв и анализ текстурных вариаций, изображение делится на сегменты нерегулярной формы. Затем выполняется ряд преобразований, определяющих изображение как объединение этих сегментов, и преобразования записываются в виде IFS-наборов. Посредством итерационного процесса, подобного тому, который использовался при построении изображения папоротника, с поразительной точностью осуществляется реконструкция изображения. Число аффинных преобразований не фиксируется на 8; в некоторых кодированных изображениях может использоваться 100 или более афинных преобразований.
Я, в свою очередь, могу представить вариант реализации описанного выше алгоритма, который не отличаеться ни скоростью, ни высоким качеством, но тем не менее может служить несложным средством исследования. В архиве.rar, доступном для скачивания , также представлены исходные тексты.
Более совершенный вариант реализации Вы можете найти на сайте
Рождение фрактальной геометрии обычно связывают с выходом в 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 такие, что выполняются следующие условия:
Первые три условия означают, что отображение w i будет сжимающим. А в силу четвёртого условия кодируемое изображение R и его образ W(R) будут похожи друг на друга. В идеале R = W(R). А это означает, что изображение R и будет являться неподвижной точкой W. Именно здесь используется подобие различных частей изображения. Как оказалось, практически все реальные изображения содержат такие похожие друг на друга, с точностью до аффинного преобразования , части.
Таким образом, для компрессии изображения W нужно:
Соответственно, для декомпрессии изображения нужно будет:JPEG существует возможность увеличить степень сжатия за счет увеличения потерь. Кроме того, оба алгоритма очень хорошо распараллеливаются.
Различия начинаются, если мы рассмотрим время, необходимое алгоритмам для архивации/разархивации. Так, фрактальный алгоритм сжимает в сотни и даже в тысячи раз дольше, чем JPEG . Распаковка изображения, наоборот, произойдет в 5-10 раз быстрее. Поэтому, если изображение будет сжато только один раз, а передано по сети и распаковано множество раз, то выгодней использовать фрактальный алгоритм.
JPEG использует разложение изображения по косинусоидальным функциям, поэтому потери в нем (даже при заданных минимальных потерях) проявляются в волнах и ореолах на границе резких переходов цветов. Именно за этот эффект его не любят использовать при сжатии изображений, которые готовят для качественной печати: там этот эффект может стать очень заметен. Фрактальный алгоритм избавлен от этого недостатка. Более того, при печати изображения каждый раз приходится выполнять операцию масштабирования, поскольку растр печатающего устройства не совпадает с растром изображения. При преобразовании также может возникнуть несколько неприятных эффектов, с которыми можно бороться либо масштабируя изображение программно, либо снабжая устройство печати своим процессором, винчестером и набором программ обработки изображений. Как можно догадаться, при использовании фрактального алгоритма таких проблем практически не возникает.
Вытеснение JPEG фрактальным алгоритмом в повсеместном использовании произойдет еще не скоро (хотя бы в силу низкой скорости архивации последнего), однако в области приложений мультимедиа, в компьютерных играх его использование вполне оправдано.
Коэффициенты компрессии: 2-2000 (Задается пользователем).
Класс изображений: Полноцветные 24 битные изображения или изображения в градациях серого без резких переходов цветов (фотографии). Желательно, чтобы области большей значимости (для восприятия) были более контрастными и резкими, а области меньшей значимости - неконтрастными и размытыми.
Симметричность: 100-100000.
Характерные особенности: Может свободно масштабировать изображение при разархивации, увеличивая его в 2-4 раза без появления "лестничного эффекта". При увеличении степени компрессии появляется "блочный" эффект на границах блоков в изображении.
| Назад | К cодержанию | Вперёд |
В декабре 1992 года, перед самым Рождеством, компания Microsoft выпустила свой новый компакт-диск Microsoft Encarta. С тех пор эта мультимедиа-энциклопедия, содержащая информацию о животных, цветах, деревьях и живописных местах, не покидает списки наиболее популярных энциклопедий на компакт-дисках. В недавнем опросе Microsoft Encarta опять заняла первое место, опередив ближайшего конкурента - Комптоновскую мультимедиа-энциклопедию. Причина подобной популярности кроется в удобстве использования, высоком качестве статей и, главное, в большом количестве материалов. На диск записано 7 часов звука, 100 анимационных роликов, примерно 800 масштабируемых карт, а также 7000.качественных фотографий. И все это - на одном диске! Напомним, что обычный компакт-диск в 650 Мбайт без использования компрессии может содержать либо 56 минут качественного звука, либо 1 час видео разрешения с разрешением 320х200 в формате MPEG-1, либо 700 полноцветных изображений размером 640х480. Чтобы разместить больше информации, необходимы достаточно эффективные алгоритмы архивации. Мы не будем останавливаться на методах архивации для видео и звука, рассмотрим историю фрактального сжатия графической информации. Рождение фрактальной геометрии обычно связывают с выходом в 1977 году книги Б. Мандельброта "Фрактальная геометрия природы". Одна из основных идей книги заключалась в том, что средствами традиционной геометрии (то есть, используя линии и поверхности), чрезвычайно сложно представить природные объекты. Фрактальная геометрия задает их очень просто. В 1981 году Джон Хатчинсон опубликовал статью "Фракталы и самоподобие", в которой была представлена теория построения фракталов с помощью системы итерируемых функций (IFS, Iterated Function System). Спустя четыре года появилась статья Майкла Барнсли и Стефана Демко, в которой приводилась уже достаточно стройная теория IFS. В 1987 году Барнсли основал Iterated Systems, компанию, основной деятельностью которой является создание новых алгоритмов и ПО с использованием фракталов. Всего через год, в 1988 году, он выпустил фундаментальный труд "Фракталы повсюду". Помимо описания IFS, в ней был получен результат, известный сейчас как Collage Theorem, который лежит в основе математического обоснования идеи фрактальной компрессии. Если построение изображений с помощью фрактальной математики можно назвать прямой задачей, то построение по изображению IFS - это обратная задача. Довольно долго она считалась неразрешимой. Первая статья об успехах Барнсли в области компрессии появилась в журнале BYTE в январе 1988 года. В ней не описывалось решение обратной задачи, но приводилось несколько изображений, сжатых с коэффициентом 1:10000, что было совершенно ошеломительно. Но практически сразу было отмечено, что несмотря на броские названия ("Темный лес", "Побережье Монтере", "Поле подсолнухов") изображения в действительности имели искусственную природу. Это, вызвало массу скептических замечаний, подогреваемых еще и заявлением Барнсли о том, что "среднее изображение требует для сжатия порядка 100 часов работы на мощной двухпроцессорной рабочей станции, причем с участием человека". Когда в 1991 году впервые была опубликована информация о возможностях фрактального сжатия, она наделала много шуму. Майкл Барнсли, один из разработчиков алгоритма, утверждал, что разработан способ нахождения коэффициентов фрактала, сколь угодно близкого к исходной картинке. Фракталы, эти красивые образы динамических систем, ранее использовались в машинной графике в основном для построения изображений неба, листьев, гор, травы. Красивое и, что важнее, достоверно имитирующее природный объект изображение могло быть задано всего несколькими коэффициентами. Неудивительно, что идея использовать фракталы при сжатии возникала и раньше, но считалось практически невозможным построить соответствующий алгоритм, который подбирал бы коэффициенты за приемлемое время. Итак, в 1991 году такой алгоритм был найден. Кроме того, в дальнейших его статьях декларировался ряд уникальных возможностей новой технологии. Так, фрактальный архиватор позволяет, например, при распаковке произвольно менять разрешение (размеры) изображения без появления эффекта зернистости. Более того, он распаковывает гораздо быстрее, чем ближайший конкурент, JPEG, и не только статическую графику, но и видео. В качестве примера приводилась программа, показывающая на машине с процессором i386/33 МГц цветной видеофильм с частотой 20 кадров в секунду без всякой аппаратной поддержки. В отличие от JPEG, в алгоритм изначально заложена возможность управлять степенью потерь на участках с максимальными потерями качества. Коэффициент сжатия изображений в целом примерно как у JPEG, но на некоторых реальных картинках достигалось сжатие в 10000 (!) раз. В 1992 году Арнауд Джеквин, один из сотрудников Барнсли, при защите диссертации описал практический алгоритм и опубликовал его. Этот алгоритм был крайне медленным и не претендовал на компрессию в 10000 раз (полноцветное 24-разрядное изображение с его помощью могло быть сжато без существенных потерь с коэффициентом 1:8 - 1:50); но его несомненным достоинством было то, что вмешательство человека удалось полностью исключить. Сегодня все известные программы фрактальной компрессии базируются на алгоритме Джеквина. В 1993 году вышел первый коммерческий продукт компании Iterated Systems. Ему было посвящено достаточно много публикаций, но о коммерческом успехе речь не шла, продукт был достаточно "сырой", компания не предпринимала никаких рекламных шагов, и приобрести программу было тяжело. В 1994 году Ювал Фишер были предоставил во всеобщее пользование исходные тексты исследовательской программы, в которой использовалось разложение изображения в квадродерево и были реализованы алгоритмы оптимизации поиска. Позднее появилось еще несколько исследовательских проектов, которые в качестве начального варианта программы использовали программу Фишера. В июле 1995 года в Тронхейме (Швеция) состоялась первая школа-конференция, посвященная фрактальной компрессии. Таким образом, многие важные события в области фрактальной компрессии произошли за последние три года: алгоритм только-только начинает развиваться. Как уже отмечалось, недостатком алгоритма фрактального сжатия является большое время кодирования. Решение этой проблемы в 1999 году предложил Д.С.Ватолин в своей статье "Использование ДКП для ускорения фрактального сжатия изображения". В работе рассматривается применение дискретного косинусоидального преобразования (ДКП) для ускорения работы фрактального алгоритма сжатия изображений. ДКП используется для разбиения всего множества блоков в изображении на 256 классов, что позволяет достичь почти 100-кратного ускорения работы алгоритма при приемлемых потерях в качестве изображения. В отличие от других работ, в данной статье детально описан разработанный алгоритм и полученные результаты.
1. Фракталы и история возникновения метода фрактального сжатия
В декабре 1992 года, перед самым Рождеством, компания Microsoft выпустила свой новый компакт-диск Microsoft Encarta. С тех пор эта мультимедиа-энциклопедия, содержащая информацию о животных, цветах, деревьях и живописных местах, не покидает списки наиболее популярных энциклопедий на компакт-дисках. В недавнем опросе Microsoft Encarta опять заняла первое место, опередив ближайшего конкурента - Комптоновскую мультимедиа-энциклопедию. Причина подобной популярности кроется в удобстве использования, высоком качестве статей и, главное, в большом количестве материалов. На диск записано 7 часов звука, 100 анимационных роликов, примерно 800 масштабируемых карт, а также 7000.качественных фотографий. И все это - на одном диске! Напомним, что обычный компакт-диск в 650 Мбайт без использования компрессии может содержать либо 56 минут качественного звука, либо 1 час видео разрешения с разрешением 320х200 в формате MPEG-1, либо 700 полноцветных изображений размером 640х480. Чтобы разместить больше информации, необходимы достаточно эффективные алгоритмы архивации. Мы не будем останавливаться на методах архивации для видео и звука. Речь пойдет о новом перспективном алгоритме - фрактальном сжатии графической информации.
Понятия «фрактал» и «фрактальная геометрия» (fractus - состоящий из фрагментов, лат.) были предложены математиком Б. Мандельбротом в 1975 г. для обозначения нерегулярных, но самоподобных структур. Рождение фрактальной геометрии обычно связывают с выходом в 1977 году книги Б. Мандельброта "Фрактальная геометрия природы". Одна из основных идей книги заключалась в том, что средствами традиционной геометрии (то есть используя линии и поверхности), чрезвычайно сложно представить природные объекты. Фрактальная геометрия задает их очень просто.
Определение фрактала, данное Мандельбротом, звучит так: "Фракталом называется структура, состоящая из частей, которые в каком-то смысле подобны целому"
Одним из основных свойств фракталов является самоподобие. В самом простом случае небольшая часть фрактала содержит информацию о всём фрактале. Фракталы, эти красивые образы динамических систем, ранее использовались в машинной графике в основном для построения изображений неба, листьев, гор, травы. Красивое и, что важнее, достоверно имитирующее природный объект изображение могло быть задано всего несколькими коэффициентами.
Существует большое разнообразие фракталов. Потенциально наиболее полезным видом фракталов являются фракталы на основе системы итеративных функций (Iterated Function System - IFS) . Метод IFS применительно к построению фрактальных изображений, изобретённый большим их знатоком Майклом Барнсли (Michael Barnsley) и его коллегами из Технологического института шт. Джорджия (Georgia Institute of Technology) , базируется на самоподобии элементов изображения и заключается в моделировании рисунка несколькими меньшими фрагментами его самого. Специальные уравнения позволяют переносить, поворачивать и изменять масштаб участков изображения; таким образом, эти участки служат компоновочными блоками остальной части картины.
Одним из наиболее поразительных (и знаменитых) IFS -изображений является чёрный папоротник, в котором каждый лист в действительности представляет собой миниатюрный вариант самого папоротника (см. рис.). Несмотря на то, что картинка создана компьютером методом аффинных преобразований, папоротник выглядит совершенно как настоящий. Выдвинуто предположение, что природа при кодировании генетической структуры растений и деревьев пользуется чем-то близким к методу IFS -фракталов.
IFS -фракталы имеют одно вполне реальное и полезное применение: с их помощью можно сжимать большие растровые изображения до долей их нормальных размеров. Этот утверждение следует из теоремы Банаха о сжимающих преобразованиях (также известной как Collage Theorem ) и является результатом работы исследователя Технологического института шт. Джорджия Майкла Барнсли в области IFS . Вооружившись этим выводом, он ушёл из института, запатентовал свое открытие и основал компанию Iterated Systems Incorporated . О своём достижении он рассказал миру в журнале Byte за январь 1988 г. Однако там отсутствовали какие-либо сведения о решении обратной задачи: как по заданному изображению найти аффинные преобразования. К тому моменту у этой задачи не было даже намёка на решение. В статье Барнсли было показано несколько реалистичных фрактальных изображений, но все они были созданы вручную.
В идеале хотелось бы уметь находить для любого изображения систему аффинных преобразований (IFSM) , воспроизводящую изображение с заданной точностью. Однако решение находилось немного в стороне. Первым нашёл его именно студент Барнсли, Арно Жакан (Arnaud Jacquin) . Предложенный метод получил название «Система итерируемых кусочно-определённых функций» (Partitioned Iterated Function System - PIFS) . Согласно этой схеме, отдельные части изображения подобны не всему изображению, а только его частям.
2. Математические основы фрактального сжатия
Фрактальные методы сжатия позволяют сжать информацию в 10 000 раз. Все известные программы фрактальной компрессии базируются на алгоритме Джеквина - сотрудника Барнсли, который в 1992 году при защите диссертации описал практический алгоритм фрактального сжатия. Несомненным достоинством работы было то, что вмешательство человека в процесс сжатия удалось полностью исключить.
Рассмотрим механизм фрактального сжатия данных. Фрактальная архивация основана на том, что с помощью коэффициентов системы итерируемых функций изображение представляется в более компактной форме. Прежде чем рассматривать процесс архивации, разберем, как IFS строит изображение. Строго говоря, IFS - это набор трехмерных аффинных преобразований, переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (x координата, у координата, яркость). Наиболее наглядно этот процесс продемонстрировал сам Барнсли в своей книге "Фрактальное сжатие изображения". В ней введено понятие Фотокопировальной Машины, состоящей из экрана, на котором изображена исходная картинка, и системы линз, проецирующих изображение на другой экран. Каждая линза проецирует часть исходного изображения. Расставляя линзы и меняя их характеристики, можно управлять получаемым изображением. На линзы накладывается требование они должны уменьшать в размерах проектируемую часть изображения. Кроме того, они могут менять яркость фрагмента и проецируют не круги, а области с произвольной границей. Одна шаг Машины состоит в построении с помощью проецирования по исходному изображению нового. Утверждается, что на некотором шаге изображение перестанет изменяться. Оно будет зависеть только от расположения и характеристик линз и не будет зависеть от исходной картинки. Это изображение называется неподвижной точкой или аттрактором данной IFS. Collage Theorem гарантирует наличие ровно одной неподвижной точки для каждой IFS. Поскольку отображение линз является сжимающим, каждая линза в явном виде задает самоподобные области в нашем изображении. Благодаря самоподобию мы получаем сложную структуру изображения при любом увеличении. Наиболее известны два изображения, полученных с помощью IFS треугольник Серпинского и папоротник Барнсли Первое задается тремя, а второе - питью аффинными преобразованиями (или, в нашей терминологии, линзами). Каждое преобразование задается буквально считанными байтами, в то время, как изображение, построенное с их помощью, может занимать и несколько мегабайт. Становится понятно, как работает архиватор, и почему ему требуется так много времени. Фактически, фрактальная компрессия - это поиск самоподобных областей в изображении и определение для них параметров аффинных преобразований. В худшем случае, если не будет применяться оптимизирующий алгоритм, потребуется перебор и сравнение всех возможных фрагментов изображения разного размера. Даже для небольших изображений при учете дискретности мы получим астрономическое число перебираемых вариантов. Даже резкое сужение классов преобразований, например, за счет масштабирования только в определенное число раз, не позволит добиться приемлемого времени. Кроме того, при этом теряется качество изображения. Подавляющее большинство исследований в области фрактальной компрессии сейчас направлены на уменьшение времени архивации, необходимого для получения качественного изображения.
Итак, рассмотрим математическое обоснование возможности фрактального сжатия.
Есть отображение, где - множество всех возможных изображений. W является объединением отображений w i :
Такие отображения называются сжимающими , и для них справедливо следующее утверждение:
Если к какому-то изображению F 0 мы начнём многократно применять отображение W таким образом, что
Это конечное изображение F называют аттрактором , или неподвижной точкой отображения W . Также известно, что если преобразования w i являются сжимающими, то их объединение W тоже является сжимающим.
3. Типовая схема фрактального сжатия
С учётом вышесказанного, схема компрессии выглядит так: изображение R разбивают на кусочки r i , называемые ранговыми областями . Далее для каждой области r i находят область d i и преобразование w i такие, что выполняются следующие условия:
1. d i по размерам больше r i .
2. w i (r i ) имеет ту же форму, размеры и положение, что и r i .
3. Коэффициент u преобразования w i должен быть меньше единицы.
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 , а также разбиение изображения на домены.
Соответственно, для декомпрессии изображения нужно будет:
1. Создать какое-то (любое) начальное изображение R 0 .
2. Многократно применить к нему отображение W (объединение w i ).
3. Так как отображение W сжимающее, то в результате, после достаточного количества итераций, изображение придёт к аттрактору и перестанет меняться. Аттрактор и является нашим исходным изображением. Декомпрессия завершена.
Именно это и позволяет при развертывании увеличивать его в несколько раз. Особенно впечатляют примеры, в которых при увеличении изображений природных объектов проявляются новые детали, действительно этим объектам присущие (например, когда при увеличении фотографии скалы она приобретает новые, более мелкие неровности).
4. Оценка коэффициента сжатия и вычислительных затрат
Размер данных для полного определения ранговой области рассчитывается по формуле:
где Nb и Mb - количество бит, необходимых для хранения каждой из координат, рассчитываются по следующим формулам:
где V и H - вертикальный и горизонтальный размеры изображения, Size - размер доменного блока, Step - шаг поиска доменной области.
Для хранения преобразования T необходимо 3 бита.
Для хранения U и V необходимо 9 и 7 бит соответственно.
Для примера возьмём изображение размером 256x256 пикселей, и будем исследовать доменную область с шагом 4 пикселя.
Nd = Md = (256 - 8 + 1) / 4 = 62
Nb = Mb = CEIL (log 2 62) = 6
Z = 12 + 3 + 6 + 6 = 27
Коэффициент сжатия S составляет
S = (8 * 8 * 8) / 27 = 19
Коэффициент сжатия не так велик, как хотелось бы, но и параметры сжатия далеко не оптимальны, и коэффициент может увеличиваться в разы.
А теперь оценим вычислительную сложность данного алгоритма. На этапе компрессии мы должны перебрать все доменные области - 1"024 штуки, для каждой - все ранговые - 58"081 штука (при шаге 1), а для каждой из них, в свою очередь, - все 8 преобразований. Итого получается 1"024 х 58"081 х 8 = 475"799"552 действия. При этом эти действия не тривиальны и включают несколько матричных операций, которые, в свою очередь, включают операции умножения и деления чисел с плавающей точкой.
К сожалению, даже на современном ПК (а именно для таких машин хотелось реализовать алгоритм) понадобится недопустимо много времени для того, чтобы сжать изображение размером всего 256 х 256 пикселов. Очевидно, что рассмотренный алгоритм нуждается в оптимизации.
Во многом недостатки в качестве восстановленного изображения по сжатому формату согласно 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 , 0s<1 такая что:
d(f(x 1),f(x 2)) sd(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 , 0s<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: XX c коэффициентами сжатия s n . Таким образом, IFS можно обозначить следующим образом: {X,w n:n=1,2,..,N}, или если рассматривать пространство точек в R 2 , то просто {w n }.
В теории фрактального сжатия доказывается теорема коллажа, которую можно сформулировать следующим образом.
Пусть есть двоичное изображение LR 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-блока производится перебором в соответствующем классе.
Генетический алгоритм . Генетический алгоритм (ГА) представляет собой алгоритмический подход к решению экстремальных задач однокритериального выбора, основанный на моделировании основных факторов эволюционного развития популяции .
При использовании ГА для поиска
оптимальных решений каждый элемент x
X
пространства оптимизации должен быть
представлен как векторb
B
из N символов двоичного алфавита A =
{0,1}, где B = A N . Необходимо также,
чтобы пространство оптимизации X состояло
из конечного числа элементов.
Популяцией П = (χ 1 , χ 2 ,…, χM) численности M считается вектор пространства B M , координаты которого называются генотипами особей данной популяции.
Шагом ГА является переход от текущего
поколения к следующему, т.е. получение
новой популяции
из
.
В построении очередной особи новой
популяции участвуют операторы
кроссинговера (скрещивания), мутации и
случайный оператор отбора,Select
:
B M
{1,…,M}
действие которого состоит в выборе
номера особи родителя при порождении
очередного потомка.
Для определения ГА необходимо задать
оператор кроссинговера Cross
: B
B
B
B
и оператор мутацииMut
: B
B.
Действие кроссинговера
заключается в выборе случайным образом
некоторой позицииj
, равномерно
распределенной от1
до
N-1
,
после чего результат формируется в виде
Влияние
кроссинговера регулируют с помощью
вероятности
срабатывания этого оператора (в противном
случае все остается без изменений).
Рис. 1.16. Блок схема основных шагов фрактального кодирования изображения
Оператор
мутации в каждой позиции аргумента с
заданной вероятностью
заменяет ее содержимое
на случайный
элемент двоичного алфавита A, выбранный
в соответствии с равномерным распределением
(в противном случае все остается без
изменений).
Целевая функция исходной задачи,
заменяется в ГА на неотрицательную
функцию пригодности генотипа
,
где
B.
Процесс работы алгоритма представляет
собой последовательную смену поколений,
на каждом шаге которой популяция
наполняется парами потомков от особей
популяции
по формуле
где
- особи с наименьшей пригодностью
популяции
.
То есть индивиды извлекаются попарно
из
и
после кроссинговера и мутации помещаются
в
.
Изменение вероятностей мутации и
кроссинговера позволяет регулировать
работу ГА и настраивать его на конкретные
задачи.
Модифицированный генетический
алгоритм.
Опишем схему ГА в применении
к задаче фрактального сжатия . В
качестве генотипа ГА удобно взять
вектор, компонентами которого будут
пиксельные координаты области
исходного изображения, определенного
на тороидальной поверхности, и число
кодирующее аффинное преобразование
.
Имеется восемь способов аффинного
преобразования квадрата в квадрат:
поворот на четыре стороны или зеркальное
отражение и поворот на четыре стороны.
Следовательно, на кодировку этого
преобразования достаточно трех бит.
Функцию пригодности положим равной
где в нижней части под знаком суммы –
евклидово расстояние между исходным и
преобразованным блоком. Данная функция
удовлетворяет требования ГА (неотрицательна)
и адекватна для оператора рулеточной
селекции, при которой каждый индивид
популяции
t
оказывается родителем при формировании
очередной особи
популяции
t+1
с вероятностью
.
При таком представлении хромосом, определяющих данный генотип, любой вектор пространства решений всегда допустим и имеет ненулевую пригодность.
Оператор мутации для данного алгоритма – стандартный, а оператор кроссинговера был модифицирован следующим образом:
Увеличение быстродействия алгоритма.
Недостатком данного метода сжатия
является очень большой объем вычислений
для кодирования изображений. Для программ
реализующих данный метод, применяются
как обычные методы увеличения скорости
программ: целочисленная арифметика,
ассемблерная реализация и другие, так
и некоторые специфические приемы:
использование аффинных преобразований
только одного типа, различные варианты
разбиения изображения на области
.
Приведем схемы двух алгоритмов, которые
для некоторых классов изображений могут
значительно уменьшить объем вычислений.
Параметрами первого алгоритма служат
уровень потерь при кодировании и
минимальный размер областей
.
Этот алгоритм обеспечивает равномерное
качество кодирования всего изображения.
Параметром второго алгоритма является
количество областей
,
используемых для кодирования изображения,
что прямо влияет на объем вычислений,
но он не обеспечивает достаточной
точности кодирования отдельных фрагментов
изображения .
Алгоритм 1.
Алгоритм 2.
Алгоритм восстановления изображения:
Создается два изображения одинакового размера А и Б. Размер изображений может быть не равен размеру исходного изображения. Начальный рисунок областей А и Б не имеет значения. Это могут быть случайные данные.
Данные из области А преобразуются в область Б. Для этого сначала изображение Б делится на домены также как и на первой стадии процесса сжатия (расположение доменов описано в заголовке файла). Теперь для каждого домена области Б проводится соответствующее аффинное преобразование ранговых областей изображения А, описанное коэффициентами из сжатого файла. Результат помещается в область Б. На этой стадии создается совершенно новое изображение.
Данные из области Б преобразуются в область А. Этот шаг идентичен предыдущему, только изображения А и Б поменялись местами, т.е. теперь область А делится на блоки и ранговые области изображения Б отображаются на эти блоки.
Процедуры 2 и 3 повторяются до тех пор, пока изображения А и Б не станут неразличимыми.
Прямой и обратный ход (сжатие и восстановление) не эквивалентны по затратам. Прямое преобразование (сжатие) - значительно дольше, обратное преобразование (восстановление) - гораздо быстрее. Алгоритм фрактального сжатия - несимметричный алгоритм. Коэффициент симметричности (отношение времени архивации ко времени разархивации) колеблется в пределах 1000-10000.
К достоинствам фрактального метода можно отнести:
Высокие коэффициенты сжатия.
Высокую скорость обратного преобразования.
Возможность дальнейшего структурного анализа изображения .
При этом фрактальный метод обладает следующими недостатками:
Зависимостью результатов работы метода от принципов отбора базовых элементов и доменов.
Коэффициент сжатия зависит от повторяемости базовых элементов.
Алгоритм ориентирован на полноцветные изображения и изображения в градациях серого цвета. Фрактальное сжатие реализовано в формате FIF.
В настоящее время существует достаточно много алгоритмов сжатия изображений. Основой любых методов сжатия данных является использование естественной избыточности исходной информации. Сжатие изображений осуществляется либо в пространственной либо в частотной областях изображения. Наиболее яркими примерами пространственного сжатия изображений являются алгоритмы PCX, GIF, а частотного сжатия - JPEG.
В пространственной области нельзя добиться достаточно большого коэффициента сжатия, поэтому в настоящее время большинство алгоритмов сжатия работают в частотной области изображения, поскольку наиболее явно выраженная избыточность исходных данных проявляется при их спектральном анализе, как результата разложения в некотором ортогональном базисе.
В подобных алгоритмах можно выделить три основных шага:
Применение обратимых дискретных ортогональных преобразований к изображению.
Выбор наиболее значимых частотных коэффициентов.
Вторичное сжатие выбранных коэффициентов, например арифметическим или статистическим алгоритмом сжатия.
