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, доступном для скачивания , также представлены исходные тексты.
Более совершенный вариант реализации Вы можете найти на сайте
Ключевые слова: нейронные сети; сжатие изображений; машинное обучение; фракталы.
В данной работе представлен метод сокращения времени кодирования для фрактального сжатия изображений. Данный подход сочетает выделение характеристик вместе с классификацией доменов, используя самоорганизующуюся нейронную сеть. Выделение особенностей сокращает объем задачи и позволяет нейронной сети обучаться на изображении, отличном от кодируемого. Самоорганизующаяся нейронная сеть для классификации вводит понятие кластерной топологии, а также устраняет необходимость априорного задания множества подходящих классов изображения. Сеть организует сама себя в соответствии с распределением характеристик изображения, получаемым в процессе обучения. В работе представлены результаты, которые показывают, что классификационный подход может сократить время кодирования на два порядка, сохраняя при этом сравнительную точность и эффективность сжатия.
Фрактальное кодирование изображений представляет собой подающий надежды подход в приложениях сжатия изображений, таких как веб-сайты Интернет . Однако, потребность во времени для этапа кодирования в этом подходе было сдерживающим препятствием его принятию как практического метода. Процесс кодирования заключается в отображении доменных блоков в ранговые блоки изображения. Для каждого рангового блока алгоритм ищет такой доменный блок и соответствующее преобразование, которые обеспечат наилучшее соответствие ранговому блоку. Классификация доменных блоков может значительно ускорить выполнение кодирования, сокращая количество доменов, среди которых нужно проводить поиск . Использование самоорганизующихся нейронных сетей с целью классификации доменов уже было исследовано . Эти сети дают улучшение, по сравнению с базовыми подходами к классификации, благодаря определению топологии кластеров классов. Вклад данной работы состоит в комбинировании классификации доменов с помощью самоорганизующейся нейронной сети вместе с выделением характеристик с целью обеспечения еще более быстрого кодирования изображений. Небольшой набор характеристик изображения, измеряющих тоновые и текстурные качества, вычисляются для каждого доменного и рангового блока. Таким образом, каждый блок имеет ассоциированный с ним вектор характеристик, размер которого не зависит от размера блока. Выделение характеристик является выгодным по двум причинам. Во-первых, получаемое в результате снижение объема задачи сокращает количество вычислений, необходимых в процессе поиска доменов. Во-вторых, так как характеристики независимы от структуры конкретных доменов, то становится возможным обучать самоорганизующуюся сеть на одном изображении и применять полученную в результате сеть для классификации на других изображениях. Таким образом, время обучения сети не является частью общего времени кодирования. Измерения времени фрактального кодирования изображений обычно выражают в терминах времени выполнения на рабочей станции Sun или Silicon Graphics. Представленный здесь подход обеспечивает сопоставимые измерения при выполнении на ПК Pentium 120 MHz.
Фрактально кодирование изображений основано на теории систем итерируемых функций (далее сокращенно СИФ, от англ. Iterated Function System - IFS). Теория СИФ имеет в своей основе теорему о сжимающих отображениях (далее сокращенно ТОС, от англ. Contraction Mapping Theorem - CMT) из классического анализа, которая используется для построения фрактальных изображений итеративным образом. Фрактальное изображение является фиксированной точкой в пространстве изображения, что гарантируется ТОС, и это изображение называется аттрактором СИФ. Обратная задача, решаемая фрактальным кодированием изображений, начинается с рассмотрения заданного изображения и вычисления СИФ, представляющей изображение, близкое к заданному, - его аттрактор. Код фрактального изображения обычно (хотя, не всегда) требует меньшего объема для хранения, чем изображение-оригинал, что проявляет этот метод как метод сжатия. Эмпирические результаты показывают, что во многих случаях фрактальный метод настолько же хорош, как и JPEG, который считают стандартом сжатия на сегодня .
Фрактальное сжатие изображений использует специальную разновидность СИФ, называемую системой итерируемых кусочно-определенных функций (далее сокращенно СИКФ, от анг. Partitioned Iterated Function System - PIFS). СИКФ состоит из полного метрического пространства X , набора поддоменов D i ⊂ X, i = 1,...,n , и набора сжимающих преобразований w i ~ : D i → X, i = 1,...,n . Мы рассматриваем изображения в градациях серого как функции действительные значений f(x, y) , определенные на квадратной области I 2 = I×I . Пусть w i ~ (x, y) - аффинное преобразование I 2 → I 2 , такое что
при условии, что w i ~ - обратимо и (x,y) ∈ R i . Константа s i расширяет или сужает диапазон значений функции f и, коль скоро мы говорим об изображениях в градациях серого, то она управляет контрастностью. Аналогично, константа o i увеличивает или уменьшает значения градаций серого, или управляет яркостью. Преобразование w i ~ называется пространственной составляющей преобразования w i .
Базовый алгоритм выполняется следующим образом. Разбиваем изображение на не перекрывающиеся прямоугольные ранговые блоки {R i } . Блоки R i могут быть одинакового размера, но чаще используется некоторая разновидность разбиения с переменным размером блоков, что дает возможность плотно заполнять ранговыми блоками маленького размера части изображения, содержащие мелкие детали. Представленные здесь результаты, были получены с использованием схемы разбиения методом квадро-дерева (quadtree partition scheme), описанной в . Покрываем изображение последовательностью доменных блоков, возможно перекрывающихся. Домены могут быть разных размеров и обычно их количество исчисляется сотнями и тысячами. Аффинное преобразование (2.1) является пространственным сжимающим преобразованием, если |det A i |
 |
(2.3) |
была небольшой. Для оцифрованных изображений интеграл (2.3) заменяется суммированием по пикселям. Если после нахождения наилучшего w i величина (2.3) оказывается все еще больше некоторой заранее определенной погрешности, то схема разбиения методом квадро-дерева разбивает ранг на четыре более малых прямоугольника, и процесс поиска оптимального преобразования повторяется для этих меньших блоков. Этот процесс продолжается до тех пор, пока величина (2.3) не станет меньше допустимой погрешности или пока не достигается заранее определенная максимальная глубина квадро-дерева. Изображение декодируется итеративным применением преобразования W к изображению f , где
W(f)(x,y) = w i (f)(x,y) для (x,y) ∈ R i
Если преобразования {w i } были выбраны корректно, то итерирование W 0n (f) будет близко к исходному изображению при некотором достаточном значении n . Этап кодирования требует значительных вычислений из-за большого количества доменов, среди которых нужно осуществлять поиск для каждого рангового блока, а также из-за вычислений, проводимых при каждом сравнении домена с рангом. В этой работе сокращение вычислительных потребностей этапа кодирования решается в двух направлениях. Во-первых, вводится понятие характеристик изображения, определяемых для каждого доменного и рангового блока. Тогда потенциально подходящие домены могут быть выбраны на основе значений небольшого количества этих характеристик, чем значений самих пикселей. Во-вторых, предлагается организация доменных блоков в кластерную топологию посредством самоорганизующейся нейронной сети. Это еще больше сокращает время кодирования, позволяя сети быстро определять месторасположение в пространстве характеристик тех доменных блоков, которые похожи на ранговые блоки.
Один из способов ускорить процесс фрактального кодирования изображений - это выделение небольшого количества характеристик, описывающих доменные и ранговые блоки. Тогда сравнение доменных и ранговых блоков проводится на основании этих характеристик, а не по отдельным пикселям, что сокращает объем работы. В данной работе используется шесть характеристик, которые описывают распределение текстуры и контрастности изображения. Выделение характеристик само по себе обеспечивает значительное ускорение процесса кодирования.
Здесь используются следующие шесть характеристик: 1) стандартное отклонение (standard deviation), σ; 2) асимметрия (skewness), которая представляет собой сумму кубов разностей между значениями пикселей и средним значением блока, нормированных кубом σ; 3) межпиксельная контрастность (neighbor contrast), которая измеряет разность между значениями соседних пикселей; 4) бета (beta), которая показывает насколько сильно отличаются значения пикселей от значения в центре блока; 5) горизонтальный градиент (horizontal gradient), который характеризует изменение значений пикселей блока по горизонтали; 6) вертикальный градиент (vertical gradient), который характеризует изменение значений пикселей блока в направлении сверху вниз. Среднее пиксельное значение не используется в качестве характеристики, поскольку контрастность и яркость меняются в процессе сопоставления доменного и рангового блоков. При сравнении расстояний в пространстве характеристик, вектор характеристик нормализуют для того, чтобы набольшие значения характеристик не доминировали при сравнении.
Следующее улучшение, которое может быть сделано - это классификация доменов и рангов на основе этих характеристик и сравнение рангов только с доменными похожих классов. Используемая здесь схема классификации доменов основана на самоорганизующейся нейронной сети Кохонена . Этот тип сети состоит из решетки (lattice) узловых позиций (node positions). С каждым узлом решетки связан весовой вектор, который имеет ту же размерность, что и размерность векторов характеристик. Размерность используемых здесь векторов характеристик составляет 6. А используемая здесь решетка узлов состоит из 10 строк и 10 столбцов. Каждый узел представляет класс доменных блоков изображения, поэтому общее количество узлов мы стремимся сохранить довольно малым. Можно рассматривать и другие способы организации узлов, такие как матрицы более высокой размерности.
Процесс обучения происходит независимо, без какого-либо контроля со стороны человека. Сеть весовых векторов инициализируется случайными значениями. Затем в сеть поступает входной вектор характеристик, и мы отыскиваем весовой вектор, самый близкий к входному вектору. То есть, мы находим i’j’ , такие что
||v – w i’j’ || ≤ ||v – w ij || для всех i, j
где v - это входной вектор характеристик, а w - весовой вектор в узле ij . Веса, смежные по решетке с выбранным весом w i’j’ адаптируются, чтобы больше походить на входной вектор. Эта адаптация выражается формулой
w ij new = w ij old + ε·exp(α·||v–w ij old || 2)·(v– w ij old)
где ij - это индексы узлов, которые находятся в окрестности узла i’j’ . Размер этой окрестности сокращается с каждой новой итерацией процесса обучения. Параметр ε - это шаг итерации, и α обратно пропорционально этому шагу. Программная реализация представленных результатов приведена в .
Коль скоро сеть была обучена, доменные блоки для данного изображения классифицируются путем сопоставления каждому из них весового вектора, самого близкого к нему в пространстве характеристик. Когда вектор характеристик рангового блока поступает в сеть, ему так же сопоставляется весовой вектор сети. Затем ранговый блок сравнивается с доменами, которые сопоставлены данному весовому вектору, а также с доменами, сопоставленными смежным на решетке сети весовым векторам. Преимущество классификации на основе самоорганизующейся нейронной сети заключается в идеи организации классов изображения в соседствующие между собой, что обеспечивается решеткой сети. Другое преимущество состоит в том, что такая кластеризация типов изображений происходит без необходимости предопределять классы изображений заранее.
В таблице 1 представлены результаты сравнения фрактального сжатия изображений с использованием трех различных методов, применительно к изображениям, показанным на рисунках 1 и 2. «Базовый» («base») метод - это стандартный метод разбиения квадро-деревом, обсуждаемый в , без классификации доменов. Величина «уровень квадро-дерева» («quadtree level») обозначает максимально допустимую глубину квадро-дерева. Здесь большое число обуславливает более малые ранговые блоки, что приводит к лучшему качеству декодируемого изображения, но при этом к худшей компрессии. «Порог ошибки» («error threshold») - это параметр, контролирующий условие разбиения ранговых блоков на более малые блоки следующего более высокого уровня квадро-дерева. Значения ошибок вычисляются путем сравнения исходного растрового изображения с изображением, декодированным с использованием 6 итераций (большее количество итераций дало бы немного меньшие ошибки). «Средняя ошибка, %» («average error») - это средняя ошибка, приходящаяся на один пиксель, в то время как «PSNR» - это пиковое отношение сигнал-шум, вычисляемое как в . Метод «FO» (features-only) на основе только характеристик сравнивает доменные и ранговые блоки по шести характеристикам, рассмотренных в разделе 3. Последний метод («SO») классифицирует домены с использованием самоорганизующейся нейронной сети с выделением характеристик, как было рассмотрено выше. В каждом случае всего было использовано 320 доменных блоков. Большее количество доменов привело бы к увеличению времени кодирования и в какой-то степени лучшим коэффициентам сжатия.
Коэффициенты сжатия оцениваются отношением в среднем 4 байт для каждого рангового блока к 66614 байтам исходного растрового изображения. SO-метод работает приблизительно в два раза быстрее FO-метода и в сто раз быстрее базового метода («время на блок» выражает меру времени выполнения, которая не зависит от конечной точности изображения; приведенные здесь значения времени соответствуют ПК Pentium 120MHz). Самоорганизующаяся сеть была обучена отдельно на изображении, отличном от представленных здесь двух изображений, поэтому время обучения не включено в общее время для этого метода. Степень сжатия и качество декодированного изображения, как при ускоренных методах, так и при базовом методе, соизмеримы.
Таблица 1 — Результаты фрактального сжатия изображений при использовании самоорганизующейся классификации доменов («SO»-метод), сравнении доменов на основе только характеристик («FO»), и базовом методе («Base»)
Изображение |
Порог ошибки |
Уровень квадро-дерева |
Количество блоков |
Время, (с) |
Время на блок, (с) |
Средняя ошибка, % |
Коэфф. сжатия |
||
|---|---|---|---|---|---|---|---|---|---|
 |
|||||||||
| (а) | (б) |
Рисунок 2 — (а): Исходное растровое изображение «Leaves» (256×256, 256 градаций серого); (б): Декодированное изображение (6 итераций, уровень квадро-дерева равен 7, средняя пиксельная ошибка равна 3.05%, сжатие 1.6:1). Более высокий уровень детализации в этом изображении приводит к уменьшению быстродействия
Сочетание выделения характеристик с классификацией доменов самоорганизующейся нейронной сетью обеспечивает значительное ускорение кодирования. Классификация изображения на основе небольшого количества характеристик не только снижает степень вычислений, но также позволяет производить обучение сети на изображении, отличном от кодируемого, что таким образом исключает время обучения из общего времени кодирования. Самоорганизующаяся сеть устанавливает свое собственное множество репрезентативных классов доменов, а также определяет кластерную топологию классов доменов.
BC/NW 2008, №2 (13): 11 .1
ИССЛЕДОВАНИЕ СПОСОБОВ УСКОРЕНИЯ МЕТОДА ФРАКТАЛЬНОГО СЖАТИЯ ИЗОБРАЖЕНИЙ
Калязин Н.А., Гольцов А.Г.
(Москва, Московский энергетический институт(технический университет), Россия)
Метод фрактального сжатия изображений представляет собой метод сжатия с потерями. Это означает, что в общем случае восстановленное изображение не совпадает с исходным. Метод фрактального сжатия основан на устранении избыточности информации, возникающей в изображениях вследствие их самоподобия. Проще говоря, изображение содержит информацию о себе самом.
Рассматриваемый метод имеет ряд преимуществ, среди которых:
- потенциально высокая степень сжатия,
- малое время распаковки,
- возможность восстанавливать лишь часть изображения,
- возможность восстанавливать изображение произвольного размера,
- широкие возможности в выборе параметров сжатия.
Метод ярко выраженно асимметричный. Это означает, что время сжатия существенно больше времени распаковки. Коэффициент симметричности метода (отношение времени сжатия ко времени распаковки) может достигать 1000-10000 . Таким образом, задача ускорения работы метода фрактального сжатия весьма актуальна.
Рассмотрим принципы, лежащие в основе метода.
Ключевым понятием метода является система итерируемых функций (IFS , Iterated Function System ), возможность применения которых к проблеме сжатия изображений впервые была исследована Майклом Барнсли .
IFS представляет собой набор трехмерных аффинных преобразований, переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (координата по оси X , координата по оси Y , яркость).
Наиболее наглядно этот процесс продемонстрировал Барнсли в . Им введено понятие фотокопировальной машины (рис. 1), состоящей из экрана, на котором изображена исходная картинка, и системы линз, проецирующих изображение на другой экран и обладающих следующими свойствами:
- линзы могут проецировать часть изображения произвольной формы в любое другое место нового изображения,
- области, в которые проецируются изображения, не пересекаются,
- линза может менять яркость и уменьшать контрастность,
- линза может зеркально отражать и поворачивать свой фрагмент изображения,
- линза должна масштабировать (причем только уменьшая) свой фрагмент изображения.
Рис.1. Машина Барнсли
Расставляя линзы и меняя их характеристики, можно управлять получаемым изображением. Одна итерация такой машины заключается в том, что по исходному изображению с помощью проектирования строится новое, после чего новое берется в качестве исходного. Утверждается, что в процессе итераций получится изображение, которое перестанет меняться. Оно будет зависеть только от расположения и характеристик линз, и не будет зависеть от исходной картинки. Это изображение называется «неподвижной точкой» или аттрактором данной IFS . Теория гарантирует наличие ровно одной неподвижной точки для каждой IFS .
Поскольку отображение линз является сжимающим, каждая линза в явном виде задает самоподобные области в изображении. Благодаря самоподобию при любом увеличении наблюдается сложная структура изображения. Таким образом, система итерируемых функций задает фрактал (самоподобный математический объект дробной размерности).
Наиболее известны два изображения, полученных с помощью IFS : «треугольник Серпинского» (рис.2) и «папоротник Барнсли» (рис. 3).
Рис. 2. «Треугольник Серпинского»
Рис.3. «Папоротник Барнсли»
«Папоротник Серпинского» задается тремя, а «папоротник Барнсли» - четырьмя аффинными преобразованиями (или «линзами»). Каждое преобразование кодируется несколькими байтами, в то время как изображение, построенное с его помощью, может занимать и несколько мегабайт.
Фактически, фрактальная компрессия – это поиск самоподобных областей в изображении и определение для них параметров аффинных преобразований.
Рис. 4. Самоподобные области в изображениях
,(1)
где a , b , c , d , e , f – действительные числа и , называется двумерным аффинным преобразованием.
Преобразование , представимое в виде
,(2)
где
a
,
b
,
c
,
d
,
e
,
f
,
q
,
r
,
s
,
t
,
u
– действительные числа и 
, называется трехмерным аффинным преобразованием.
Пусть - преобразование в пространстве X . Точка , такая что , называется неподвижной точкой (аттрактором преобразования).
Преобразование в метрическом пространстве ( X , d ) называется сжимающим, если существует число s : , такое, что
.(3)
Теорема о сжимающем преобразовании.
Пусть - сжимающее
преобразование в полном метрическом пространстве (
X
,
d
).
Тогда
существует в точности одна неподвижная точка этого преобразования и для любой точки последовательность 
сходится к .
Изображением называется функция S , определенная на единичном квадрате и принимающая значения от 0 до 1 или .
Пусть трехмерное аффинное преобразование записано в виде
(4)
и определено на компактном множестве декартова квадрата . Тогда оно переведет часть поверхности S в область , расположенную со сдвигом ( e , f ) и поворотом, заданным матрицей
.(5)
При этом если интерпретировать значения
функции 
как яркость
соответствующих точек, она уменьшится в
p
раз (преобразование должно быть сжимающим) и
измениться на сдвиг
q
.
Конечная совокупность
W
сжимающих
трехмерных аффинных преобразований , определенных на областях , таких, что и 
, называется системой итерируемых функций (IFS
) .
Системе итерируемых функций однозначно ставится в соответствие неподвижная точка – изображение. Таким образом, процесс компрессии заключается в поиске коэффициентов системы, а процесс декомпрессии – впроведений итераций системы до стабилизации полученного изображения (неподвижной точки IFS ).
В дальнейшем области будут именоваться блоками, а области - доменными (рис. 5).
Рис. 5. Перевод доменного блока в ранговый
Проиллюстрируем итерационный процесс восстановления ранее сжатого изображения (рис. 6).
Рис. 6. Исходное изображение
На каждой итерации производится применение IFS к текущему изображению. На рис. 7. показаны изображения, соответствующие каждой из 10-ти первых итераций (включая 0-ю).
Рис. 7. Процесс восстановления изображения
Для оценки качества восстановленного изображения применяется количественная оценка искажений, называемая пиковым соотношением сигнал/шум (PSNR – peak signal - to - noise ratio ) . Она рассчитывается по следующим формулам:
(6)
(7)
где и - количества столбов и строк, M – максимальное значение яркости пикселя, - пиксельное значение исходного изображения в i -ой строке и j -м столбце, а - пиксельное значение декодированного изображения, rms – погрешность, вычисленная по методу наименьших квадратов.
Для выявления наиболее узких мест (с точки зрения быстродействия) мною был реализован простейший алгоритм фрактального сжатия.
Опишем более подробно последовательность действий, выполняемых при сжатии изображения.
Исходное изображение разбивается на некоторое количество ранговых блоков. В общем случае ранговые блоки могут быть любой формы и размера, однако должны покрывать все изображение и не должны пересекаться.
Кроме того, исходное изображение разбивается на доменные блоки. В общем случае доменные блоки также могут быть любой формы, могут пересекаться, но обязательно должны быть больше ранговых блоков.
Далее, для каждого из ранговых блоков находится наиболее подобный ему доменный блок. При этом доменный блок может подвергаться аффинным преобразованиям, то есть может поворачиваться на любой угол, зеркально отражаться, у него могут изменяться яркость и контрастность.
В выходной файл для каждого рангового блока записываются координаты соответствующего ему доменного блока, а также коэффициенты аффинных преобразований, которые необходимо произвести над доменным блоком, чтобы он стал максимально подобен этому ранговому блоку.
В таком виде задача не имеет решения, так как для каждого из ранговых блоков необходимо перебрать бесконечное количество разнообразных по размерам и форме доменных блоков. Поэтому на практике накладываются довольно жесткие ограничения, позволяющие сократить количество перебираемых доменных блоков . Разумеется, при этом страдает качество восстановленного изображения. Приведем ограничения, наложенные при реализации алгоритма:
1. Все блоки являются квадратами со сторонами, параллельными сторонам изображения. Таким образом, изображение равномерной сеткой разбивается на набор ранговых блоков (рис. 8а).
2. При переводе доменного блока в ранговый уменьшение размеров производится ровно в 2 раза. Это существенно упрощает как компрессор, так и декомпрессор, так как задача масштабирования небольших блоков является нетривиальной.
3. Доменные блоки берутся «через точку» и по вертикали, и по горизонтали (рис. 8б).
4. При переводе доменного блока в ранговый поворот квадрата возможен только на 0, 90, 180 и 270 градусов. Также допускается зеркальное отражение. Общее число возможных преобразований (считая пустое) – 8.
Рис. 8. Принцип разбиения изображения на ранговые (а) и доменные блоки (б)
Степень подобия рангового и доменного блоков я вычислял при помощи следующей формулы:
,(8)
где r и d – соответственно значения яркостей пикселей рангового и доменного блоков, M – математическое ожидание значений яркостей соответствующего блока.
Эта формула основана на расчете коэффициента корреляции.
При восстановлении исходного изображения была использована формула
,(9)
где r – значение блока восстанавливаемого изображения, d – значение блока преобразовываемого изображения, p – изменение контраста блока, q – сдвиг по яркости блока.
Чтобы найти коэффициент p , я использовал квадратный корень из отношения дисперсий рангового и доменного блоков:
,(10)
где D – дисперсия значений яркости пикселей соответствующего блока; для тех доменных блоков, у которых msr > 0, и формулу
(11)
для тех доменных блоков, у которых msr < 0.
Чтобы найти коэффициент q , я использовал формулу:
.(12)
Очевидно, что для того, чтобы найти для каждого из ранговых блоков наиболее подобный ему доменный блок, необходимо выполнить гигантский объем вычислений.
Предположим, что n x m - размер исходного изображения в пикселях, rsz – сторона рангового блока.
Тогда количество ранговых блоков в изображении будет
,(13)
а доменных (помня, что сторона доменного блока всегда вдвое больше стороны рангового)
.(14)
Таким образом, необходимо произвести rnum x dnum поблочных сопоставлений, что уже для изображения размером 512 x 512 и стороной рангового блока 8 пикселей составляет 251 920 384. Не стоит забывать, что в рассматриваемом нами алгоритме в каждом таком сопоставлении необходимо организовать цикл по всем пикселям блока для расчета математического ожидания и дисперсии. Более того, время, затрачиваемое на сжатие изображения в градациях серого, в простейшем случае утраивается, если речь идет о цветном изображений (так как для представления информации о яркости и цвете пикселя требуется как минимум три составляющих).
Теперь очевидно, почему множество исследований направлено на ускорение метода фрактального сжатия.
Существует два основных направления таких исследований :
Сокращение числапоблочных сопоставлений,
Ускорение сопоставлений путем повышений производительности вычислений.
К первому направлению относятся методы:
Выделение особенностей доменных блоков,
Классификация доменов.
Второе направление подразумевает использование высокопроизводительных систем и параллельных вычислений.
Метод фрактального сжатия, на мой взгляд, легко подвергается распараллеливанию. Это следует из того, что каждый ранговый блок изображения обрабатывается независимо от других. Следовательно, в идеальном случае, можно достичь коэффициента ускорения, близкого к числу ранговых блоков (разумеется, при возможности запустить вычислительных процессов по числу ранговых блоков).
Основываясь на данной предпосылке, я попытался написать параллельную программу на языке Си с использованием библиотеки MPI (Message Passing Interface ). Для эксперимента использовался вычислительный кластер МЭИ, имеющий в своем составе 16 узлов, каждый из которых состоит из двух двухъядерных процессоров AMD Opteron x86_64 , 2.2 ГГц . Пиковая производительность кластера составляет 281.6 GFlop/s.
Оказалось, что для реализации параллельного алгоритма необходим лишь один вызов функции широковещательной рассылки данных. Это означает, что рассматриваемая задача крайне слабосвязная, а значит, на пересылки данных между процессами тратится минимальное количество времени.
Замер времени производился лишь в той части программы, которая непосредственно реализовывала алгоритм сжатия. То есть операции чтения из файла исходного изображения и записи в файл результатов оказались вне учета времени.
На рис. 9 представлены зависимости времени сжатия изображения от числа параллельных процессов (рис. 9а) и коэффициента ускорения от числа параллельных процессов (рис. 9б) для изображения с разрешением 256 x 256 пикселей. Из диаграммы на рис. 9а следует, что характер зависимости времени сжатия изображения от числа параллельных процессов не меняется при изменении значения стороны рангового блока. Из диаграммы на рис. 9б следует, коэффициент ускорения не зависит от значения стороны рангового блока и численно весьма близок числу параллельных процессов. Последнее наблюдение подтверждает тезис о том, что метод фрактального сжатия хорошо поддается распараллеливанию.
Рис. 9. Зависимости времени сжатия изображения от числа параллельных процессов (а) и коэффициента ускорения от числа параллельных процессов (б) для изображения с разрешением 256 x 256 пикселей. Линии на каждой из диаграмм соответствуют различным значениям стороны рангового блока
На рис. 10 представлены зависимости времени сжатия изображения от числа параллельных процессов (рис. 10а) и коэффициента ускорения от числа параллельных процессов (рис. 10б) при стороне рангового блока равной 4 пикселя. Из диаграммы на рис. 10а следует, что характер зависимости времени сжатия от числа процессов не меняется при изменении разрешения сжимаемого изображения. Из диаграммы на рис. 10б следует, что коэффициент ускорения не меняется и от разрешения сжимаемого изображения. Это говорит о том, что фрактальный метод сжатия одинаково хорошо распараллеливается для изображений всех размеров.
Рис. 10. Зависимости времени сжатия изображения от числа параллельных процессов (а) и коэффициента ускорения от числа параллельных процессов (б) при стороне рангового блока равной 4 пикселя. Линии на каждой из диаграмм соответствуют разрешениям исходного изображения
В дальнейшем планируется исследование методов ускорения, основанных на сокращении числапоблочных сопоставлений, а также возможность их распараллеливания. Известно , что выделение особенностей доменных блоков и классификация доменов существенно сокращают время сжатия сами по себе – параллельный алгоритм, включающий в себя эти методы ускорения, выглядит еще более перспективным. Однако написание такого параллельного алгоритма может стать довольно сложной задачей.
ЛИТЕРАТУРА
1. Ватолин Д. С. Тенденции развития алгоритмов сжатия статических растровых изображений // Открытые системы сегодня. - 1995. - № 8 (29). – с. 25–30.
2. Barnsley Michael F. Fractal Image Compression, AK Peters, Ltd., 1993.
3. Barnsley Michael F. Fractals Everywhere, second edition, Academic Press, San Diego , 1993.
4. Jacquin A. Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations // IEEE Transactions on Image Processing. 1992. Vol . 1, N 1. P . 18–30.
5. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. – М.: ДИАЛОГ-МИФИ, 2003. – 384 с.
6. Уэльстид С. Фракталы и вейвлеты для сжатия изображений в действии: Учебное пособие. – М.: Издательство Триумф, 2003, - 320 с.
7. Информационно-аналитический центр parallel . ru , “Кластерные установки России и СНГ”,http://parallel.ru/russia/russian_clusters.html.
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 пикселов. Очевидно, что рассмотренный алгоритм нуждается в оптимизации.
В декабре 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-кратного ускорения работы алгоритма при приемлемых потерях в качестве изображения. В отличие от других работ, в данной статье детально описан разработанный алгоритм и полученные результаты.
