Алгоритм фрактального сжатия

Фрактальное сжатие изображений — алгоритм сжатия изображений c потерями, основанный на применении систем итерируемых функций (как правило являющимися аффинными преобразованиями) к изображениям. Данный алгоритм известен тем, что в некоторых случаях позволяет получить очень высокие коэффициенты сжатия (лучшие примеры — до 1000 раз при приемлемом визуальном качестве) для реальных фотографий природных объектов, что недоступно для других алгоритмов сжатия изображений в принципе. Из-за сложной ситуации с патентованием широкого распространения алгоритм не получил.

Описание

Основа метода фрактального кодирования — это обнаружение самоподобных участков в изображении. Впервые возможность применения теории систем итерируемых функций (англ. Iterated Function System, IFS) к проблеме сжатия изображения была исследована Майклом Барнсли (англ. Michael Barnsley) и Аланом Слоуном (англ. Alan Sloan). Они запатентовали свою идею в 1990 и 1991 годах ([www.google.com/patents/US5,065,447 U.S. Patent 5 065 447]). А. Жакен (фр. Arnaud Jacquin) представил метод фрактального кодирования, в котором используются системы доменных и ранговых блоков изображения (англ. domain and range subimage blocks), блоков квадратной формы, покрывающих всё изображение. Этот подход стал основой для большинства методов фрактального кодирования. Он был усовершенствован Ювалом Фишером (англ. Yuval Fisher) и рядом других исследователей.

В соответствии с данным методом изображение разбивается на множество неперекрывающихся ранговых подизображений (англ. range subimages) и определяется множество перекрывающихся доменных подизображений (англ. domain subimages). Для каждого рангового блока алгоритм кодирования находит наиболее подходящий доменный блок и аффинное преобразование, которое переводит этот доменный блок в данный ранговый блок. Структура изображения отображается в систему ранговых блоков, доменных блоков и преобразований.

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

По теореме Банаха, такие итерации всегда приводят к неподвижной точке, то есть к исходному изображению. На практике трудность заключается в отыскании по изображению наиболее подходящего сжимающего отображения и в компактном его хранении. Как правило, алгоритмы поиска отображения (то есть алгоритмы сжатия) в значительной степени переборные и требуют больших вычислительных затрат. В то же время, алгоритмы восстановления достаточно эффективны и быстры.

Вкратце, метод, предложенный Барнсли, можно описать следующим образом. Изображение кодируется несколькими простыми преобразованиями (в нашем случае аффинными), то есть определяется коэффициентами этих преобразований (в нашем случае A, B, C, D, E, F).

Например, изображение кривой Коха можно закодировать четырьмя аффинными преобразованиями, однозначно определив его с помощью всего 24-х коэффициентов.

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

В результате точка обязательно перейдёт куда-то внутрь чёрной области на исходном изображении. После применения такой операции много раз будет заполнено всё чёрное пространство, что восстановит картинку.

Сложность метода

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

На данный момент^{[когда?]} известно достаточно большое количество алгоритмов оптимизации перебора, возникающего при фрактальном сжатии, поскольку большинство статей, исследовавших алгоритм, были посвящены этой проблеме и во время активных исследований (1992—1996 года) выходило до 300 статей в год. Наиболее эффективными оказались два направления исследований: метод выделения особенностей (feature extraction) и метод классификации доменов (classification of domains).

Патенты

Майклом Барнсли и другими было получено несколько патентов на фрактальное сжатие в США и других странах. Например, [www.google.com/patents/US4941193 4,941,193], [www.google.com/patents/US5065447 5,065,447], [www.google.com/patents/US5384867 5,384,867], [www.google.com/patents/US5416856 5,416,856] и [www.google.com/patents/US5430812 5,430,812]. Эти патенты покрывают широкий спектр возможных изменений фрактального сжатия и серьёзно сдерживают его развитие.

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

См. также

• Фрактал
• JPEG 2000
• en:List of fractals by Hausdorff dimension
• [jre.cplire.ru/jre/nov12/1/text.pdf Сжатие изображений на базе дифференциального анализа]

Ссылки

• [www.compression-links.info/Fractal Resources on fractal compression]
• [www.compression.ru/download/fractal.html Коллекция статей по фрактальному сжатию: Fractal Papers Leipzig Collection]
• [web.archive.org/web/20001204165500/www.howell1964.freeserve.co.uk/MSc/FIC/FIC_00.htm Fractal Image Compression for Spaceborne Transputers] (недоступная ссылка с 18-05-2013 (3989 дней) — история)
• [www.verrando.com/pulcini/gp-uw1.html Pulcini and Verrando’s Compressor]
• [fic.bos.ru/ Сообщество фрактального сжатия изображений]

Отрывок, характеризующий Алгоритм фрактального сжатия

– Вот глупости! Очень мне нужно, – сказал Ростов, бросая письмо под стол.
– Зачем ты это бросил? – спросил Борис.
– Письмо какое то рекомендательное, чорта ли мне в письме!
– Как чорта ли в письме? – поднимая и читая надпись, сказал Борис. – Письмо это очень нужное для тебя.
– Мне ничего не нужно, и я в адъютанты ни к кому не пойду.
– Отчего же? – спросил Борис.
– Лакейская должность!
– Ты всё такой же мечтатель, я вижу, – покачивая головой, сказал Борис.
– А ты всё такой же дипломат. Ну, да не в том дело… Ну, ты что? – спросил Ростов.
– Да вот, как видишь. До сих пор всё хорошо; но признаюсь, желал бы я очень попасть в адъютанты, а не оставаться во фронте.
– Зачем?
– Затем, что, уже раз пойдя по карьере военной службы, надо стараться делать, коль возможно, блестящую карьеру.
– Да, вот как! – сказал Ростов, видимо думая о другом.
Он пристально и вопросительно смотрел в глаза своему другу, видимо тщетно отыскивая разрешение какого то вопроса.
Старик Гаврило принес вино.
– Не послать ли теперь за Альфонс Карлычем? – сказал Борис. – Он выпьет с тобою, а я не могу.
– Пошли, пошли! Ну, что эта немчура? – сказал Ростов с презрительной улыбкой.
– Он очень, очень хороший, честный и приятный человек, – сказал Борис.
Ростов пристально еще раз посмотрел в глаза Борису и вздохнул. Берг вернулся, и за бутылкой вина разговор между тремя офицерами оживился. Гвардейцы рассказывали Ростову о своем походе, о том, как их чествовали в России, Польше и за границей. Рассказывали о словах и поступках их командира, великого князя, анекдоты о его доброте и вспыльчивости. Берг, как и обыкновенно, молчал, когда дело касалось не лично его, но по случаю анекдотов о вспыльчивости великого князя с наслаждением рассказал, как в Галиции ему удалось говорить с великим князем, когда он объезжал полки и гневался за неправильность движения. С приятной улыбкой на лице он рассказал, как великий князь, очень разгневанный, подъехав к нему, закричал: «Арнауты!» (Арнауты – была любимая поговорка цесаревича, когда он был в гневе) и потребовал ротного командира.
– Поверите ли, граф, я ничего не испугался, потому что я знал, что я прав. Я, знаете, граф, не хвалясь, могу сказать, что я приказы по полку наизусть знаю и устав тоже знаю, как Отче наш на небесех . Поэтому, граф, у меня по роте упущений не бывает. Вот моя совесть и спокойна. Я явился. (Берг привстал и представил в лицах, как он с рукой к козырьку явился. Действительно, трудно было изобразить в лице более почтительности и самодовольства.) Уж он меня пушил, как это говорится, пушил, пушил; пушил не на живот, а на смерть, как говорится; и «Арнауты», и черти, и в Сибирь, – говорил Берг, проницательно улыбаясь. – Я знаю, что я прав, и потому молчу: не так ли, граф? «Что, ты немой, что ли?» он закричал. Я всё молчу. Что ж вы думаете, граф? На другой день и в приказе не было: вот что значит не потеряться. Так то, граф, – говорил Берг, закуривая трубку и пуская колечки.
– Да, это славно, – улыбаясь, сказал Ростов.
Но Борис, заметив, что Ростов сбирался посмеяться над Бергом, искусно отклонил разговор. Он попросил Ростова рассказать о том, как и где он получил рану. Ростову это было приятно, и он начал рассказывать, во время рассказа всё более и более одушевляясь. Он рассказал им свое Шенграбенское дело совершенно так, как обыкновенно рассказывают про сражения участвовавшие в них, то есть так, как им хотелось бы, чтобы оно было, так, как они слыхали от других рассказчиков, так, как красивее было рассказывать, но совершенно не так, как оно было. Ростов был правдивый молодой человек, он ни за что умышленно не сказал бы неправды. Он начал рассказывать с намерением рассказать всё, как оно точно было, но незаметно, невольно и неизбежно для себя перешел в неправду. Ежели бы он рассказал правду этим слушателям, которые, как и он сам, слышали уже множество раз рассказы об атаках и составили себе определенное понятие о том, что такое была атака, и ожидали точно такого же рассказа, – или бы они не поверили ему, или, что еще хуже, подумали бы, что Ростов был сам виноват в том, что с ним не случилось того, что случается обыкновенно с рассказчиками кавалерийских атак. Не мог он им рассказать так просто, что поехали все рысью, он упал с лошади, свихнул руку и изо всех сил побежал в лес от француза. Кроме того, для того чтобы рассказать всё, как было, надо было сделать усилие над собой, чтобы рассказать только то, что было. Рассказать правду очень трудно; и молодые люди редко на это способны. Они ждали рассказа о том, как горел он весь в огне, сам себя не помня, как буря, налетал на каре; как врубался в него, рубил направо и налево; как сабля отведала мяса, и как он падал в изнеможении, и тому подобное. И он рассказал им всё это.
В середине его рассказа, в то время как он говорил: «ты не можешь представить, какое странное чувство бешенства испытываешь во время атаки», в комнату вошел князь Андрей Болконский, которого ждал Борис. Князь Андрей, любивший покровительственные отношения к молодым людям, польщенный тем, что к нему обращались за протекцией, и хорошо расположенный к Борису, который умел ему понравиться накануне, желал исполнить желание молодого человека. Присланный с бумагами от Кутузова к цесаревичу, он зашел к молодому человеку, надеясь застать его одного. Войдя в комнату и увидав рассказывающего военные похождения армейского гусара (сорт людей, которых терпеть не мог князь Андрей), он ласково улыбнулся Борису, поморщился, прищурился на Ростова и, слегка поклонившись, устало и лениво сел на диван. Ему неприятно было, что он попал в дурное общество. Ростов вспыхнул, поняв это. Но это было ему всё равно: это был чужой человек. Но, взглянув на Бориса, он увидал, что и ему как будто стыдно за армейского гусара. Несмотря на неприятный насмешливый тон князя Андрея, несмотря на общее презрение, которое с своей армейской боевой точки зрения имел Ростов ко всем этим штабным адъютантикам, к которым, очевидно, причислялся и вошедший, Ростов почувствовал себя сконфуженным, покраснел и замолчал. Борис спросил, какие новости в штабе, и что, без нескромности, слышно о наших предположениях?