Фрактальное сжатие.

Фракталы — удивительные математические объекты, подкупающие своей простотой и богатыми возможностями по построению объектов сложной природы при помощи всего лишь нескольких коэффициентов и простой итеративной схемы.
Именно эти возможности и позволяют использовать их для сжатия изображений, особенно для фотографий природы и прочих сложных самоподобных изображений.
В этой статье я постараюсь коротко дать ответ на простой вопрос: «Как же это делается?».

Для начала все-таки придется немного углубиться в математику и ввести несколько определений.
Нам пригодятся следующие:

· Метрика — функция, заданная на пространстве, возвращающая расстояние между двумя точками этого пространства. Например, привычная нам Эвклидова метрика. Если на пространстве задана метрика, оно называется метрическим. Метрика должна удовлетворять определенным условиям, но не будем углубляться.

· Сжимающее отображение (преобразование) — функция на метрическом пространстве, равномерно уменьшающая расстояние между двумя точками пространства. Например, y=0.5x.

Сжимающие отображения обладают важным свойством. Если взять любую точку и начать итеративно применять к ней одно и то же сжимающее отображение: f(f(f...f(x))), то результатом будет всегда одна и та же точка. Чем больше раз применим, тем точнее найдем эту точку. Называется она неподвижной точкой и для каждого сжимающего отображения она существует, причем только одна.

Несколько аффинных сжимающих отображений образуют систему итерированных функций (СИФ). По сути, СИФ — это множительная машина. Она принимает исходное изображение, искажает его, перемещает, и так несколько раз.
Например, вот так при помощи СИФ из трех функций строится треугольник Серпинского:

Исходный треугольник три раза множится, уменьшается и переносится. И так далее. Если так продолжать до бесконечности, получим известный фрактал площадью 0 и размерностью 1,585.

Если функции, входящие в СИФ,— сжимающие, то сама СИФ тоже имеет неподвижную точку. Вот только эта «точка» будет уже не привычной нам точкой в N-мерном пространстве, а множеством таких точек, то есть изображением. Оно называетсяаттрактором СИФ. Для СИФ, приведенной выше, аттрактором будет треугольник Серпинского.

Тут мы переходим на следующий уровень — в пространство изображений. В этом пространстве:

· Точка пространства — это изображение.

· Расстояние между точками показывает, насколько похожи изображения между собой, насколько «близки» (естественно, если его задать соответствующим образом).

· Сжимающее отображение делает два любых изображения более похожими (в смысле заданной метрики).

Имея СИФ, найти аттрактор просто. Во всяком случае, имея под рукой компьютер. Можно взять абсолютно любое начальное изображение и начать применять к нему СИФ. Пример с тем же треугольником, но уже построенным из квадрата:

Получается, что для построения довольно сложной фигуры нам потребовалось 18 коэффициентов. Выигрыш, как говорится, налицо.
Вот если бы мы умели решать обратную задачу — имея аттрактор, строить СИФ… Тогда достаточно взять аттрактор-изображение, похожее на фотографию вашей кошки и можно довольно выгодно его закодировать.

Вот здесь, собственно, начинаются проблемы. Произвольные изображения, в отличие от фракталов, не самоподобны, так что так просто эта задача не решается. Как это сделать придумал в 1992 году Арнольд Жакин, в то время — аспирант Майкла Барнсли, который считается отцом фрактального сжатия.

Самоподобие нам нужно обязательно — иначе ограниченные в своих возможностях аффинные преобразования не смогут правдоподобно приблизить изображения. А если его нет между частью и целым, то можно поискать между частью и частью. Примерно так, видимо, рассуждал и Жакин.

Упрощенная схема кодирования выглядит так:

· Изображение делится на небольшие неперекрывающиеся квадратные области, называемые ранговыми блоками. По сути, разбивается на квадраты. См. картинку ниже.

· Строится пул всех возможных перекрывающихся блоков в четыре раза больших ранговых — доменных блоков.

· Для каждого рангового блока по очереди «примеряем» доменные блоки и ищем такое преобразование, которое делает доменный блок наиболее похожим на текущий ранговый.

· Пара «преобразование-доменный блок», которая приблизилась к идеалу, ставится в соответствие ранговому блоку. В закодированное изображение сохраняются коэффициенты преобразования и координаты доменного блока. Содержимое доменного блока нам ни к чему — вы же помните, нам все равно с какой точки стартовать.

http://www.compression.ru/arctest/descript/fract-comp.htm

https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%84%D1%80%D0%B0%D0%BA%D1%82%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%B6%D0%B0%D1%82%D0%B8%D1%8F