Фрактальное сжатие
Dec. 19th, 2012 02:21 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
thedeemonФракталы бывают очень разные по своему устройству, но объединяет их самоподобие: какие-то части в них похожи на другие их же части в другом масштабе. Фрактальный метод сжатия изображений берется сделать фрактал из любой картинки, ведь если взять произвольную фотку, там можно найти немало похожих фрагментов:
:)
Ну, может не везде столь же хорошо, но если для какого-то куска не находится похожего, его можно разбить на кусочки поменьше и поискать для них. В конце концов, на уровне отдельных пикселей найти похожие уж точно не проблема. Итак, возьмем картинку, разобъем ее на блоки и для каждого блока будем искать похожий блок большего размера. Он может быть где угодно. Он может быть как угодно повернут и растянут, даже нелинейно. Разрешим этому блоку также иметь другой контраст (вплоть до инвертированного) и яркость, лишь бы контраст был больше. Запишем найденное в виде набора соотношений "блок такой-то очень похож на такую-то область, к которой применили вот такое геометрическое преобразование, а яркости умножили на k и добавили константу b" (константы для разных блоков будут разные). Оказывается, что этих соотношений нам достаточно, чтобы восстановить картинку. Если геометрическое преобразование сжимающее (уменьшает расстояние между любыми двумя точками), и преобразование яркости тоже (константа k по модулю меньше единицы), то, слава матану, взяв произвольные начальные значения яркости и применив эти преобразования в цикле некоторое количество раз, мы придем к неподвижной точке всей системы преобразований, она и будет картинкой. Теперь отложите ваши айпады на помоечку и полюбуйтесь вот этими 58 килобайтами флэша.
Тут видны получающиеся на разных итерациях из изначального хаоса картинки, а поводив мышкой по блокам, можно видеть, какие блоки берутся за источники. Как вы догадались, в прошедшем соревновании картинка была сжата именно этим способом. Чем сложнее доступное геометрическое преобразование для блока, тем выше можно получить качество, но тем больше данных придется хранить. В данном случае исходные блоки брались ровно вдвое больше текущего, никаких поворотов не делалось, поэтому сохранялись лишь координаты блока (по 9 бит на координату) и коэффициенты k и b (7 и 10 бит соответственно). Изначально картинка была разделена на 64х64 блока, некоторые из них поделились рекурсивно на 4 поменьше, некоторые из тех еще на 4 поменьше, всего чуть меньше 9000 блоков, что заняло 40 КБ данных.
Интересным свойством этого метода является то, что результат формулируется в векторном виде, и декодировать картинку можно в произвольное разрешение. Выше она декодирована в 512х512, в контесте декодировалась в 1024х1024, а вот тут, например, ее фрагмент при разжатии в 2048х2048. При увеличении картинка получается заметно более четкая, чем при увеличении растровых картинок каким-нибудь Ланцошом, линии сохраняют плавность, но все заметнее становятся границы блоков. На этой идее работают некоторые фрактальные увеличивальщики картинок.
:)
Ну, может не везде столь же хорошо, но если для какого-то куска не находится похожего, его можно разбить на кусочки поменьше и поискать для них. В конце концов, на уровне отдельных пикселей найти похожие уж точно не проблема. Итак, возьмем картинку, разобъем ее на блоки и для каждого блока будем искать похожий блок большего размера. Он может быть где угодно. Он может быть как угодно повернут и растянут, даже нелинейно. Разрешим этому блоку также иметь другой контраст (вплоть до инвертированного) и яркость, лишь бы контраст был больше. Запишем найденное в виде набора соотношений "блок такой-то очень похож на такую-то область, к которой применили вот такое геометрическое преобразование, а яркости умножили на k и добавили константу b" (константы для разных блоков будут разные). Оказывается, что этих соотношений нам достаточно, чтобы восстановить картинку. Если геометрическое преобразование сжимающее (уменьшает расстояние между любыми двумя точками), и преобразование яркости тоже (константа k по модулю меньше единицы), то, слава матану, взяв произвольные начальные значения яркости и применив эти преобразования в цикле некоторое количество раз, мы придем к неподвижной точке всей системы преобразований, она и будет картинкой. Теперь отложите ваши айпады на помоечку и полюбуйтесь вот этими 58 килобайтами флэша.
Тут видны получающиеся на разных итерациях из изначального хаоса картинки, а поводив мышкой по блокам, можно видеть, какие блоки берутся за источники. Как вы догадались, в прошедшем соревновании картинка была сжата именно этим способом. Чем сложнее доступное геометрическое преобразование для блока, тем выше можно получить качество, но тем больше данных придется хранить. В данном случае исходные блоки брались ровно вдвое больше текущего, никаких поворотов не делалось, поэтому сохранялись лишь координаты блока (по 9 бит на координату) и коэффициенты k и b (7 и 10 бит соответственно). Изначально картинка была разделена на 64х64 блока, некоторые из них поделились рекурсивно на 4 поменьше, некоторые из тех еще на 4 поменьше, всего чуть меньше 9000 блоков, что заняло 40 КБ данных.
Интересным свойством этого метода является то, что результат формулируется в векторном виде, и декодировать картинку можно в произвольное разрешение. Выше она декодирована в 512х512, в контесте декодировалась в 1024х1024, а вот тут, например, ее фрагмент при разжатии в 2048х2048. При увеличении картинка получается заметно более четкая, чем при увеличении растровых картинок каким-нибудь Ланцошом, линии сохраняют плавность, но все заметнее становятся границы блоков. На этой идее работают некоторые фрактальные увеличивальщики картинок.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2012-12-19 07:43 am (UTC)no subject
Date: 2012-12-19 07:55 am (UTC)Google Chrome could not load the webpage because stuff.thedeemon.com took too long to respond
no subject
Date: 2012-12-19 10:13 am (UTC)Можно еще заменить stuff.thedeemon на data.infognition. В частности:
http://data.infognition.com/lj/frakshow.html
no subject
Date: 2012-12-22 09:10 pm (UTC)no subject
Date: 2013-01-07 06:19 pm (UTC)no subject
Date: 2012-12-19 08:21 am (UTC)То можно переопределить и дополнить 'понятие' похожести.
> Если геометрическое преобразование сжимающее
Можно сжимающее преобразование определить и по-другому.
Лишь бы оно было сжимающее относительно введённой метрики.
И оно совсем не обязательно будет всегда геометрически сжимающим картинку.
Относительно какой метрики описанное в посте преобразование является сжимающим?
Иначе говоря, что является функцией похожести?
Возможно, что стоит вспомнить и более широкие теоремы о неподвижной точке.
Хотя и известные мне тут применить куда сложнее.
Но может быть, как-то и можно. Но подумать стоит.
Собственно, я хотел высказать такую мораль — начинать надо с определения пространства. Если говорить про известную, гарантированно и понятно работающую классику, то с метрики пространства (то есть определения 'похожести').
no subject
Date: 2012-12-19 10:27 am (UTC)Было бы интересно посмотреть, что получится с какой-нибудь SSIM, например.
no subject
Date: 2012-12-19 11:27 am (UTC)Можно привести аналогию со словами над алфавитом — это похоже на метрику Хэмминга (лень уточнять, думаю, суть понятна).
В общем, уже просто придумывать получше метрику уже должно дать хорошее.
Замечание про L_2 может быть полезным (скорее, что нет) вот в каком смысле —
картинки, это пространство заметно получше, чем метрическое и у него есть дополнительные хорошие свойства.
Скажем, сходу, несложно его рассматривать не как кусочно постоянное, а как пару раз гладкое.
Пользовать напрямую L_2, это слишком примитивно, но возможно, что удастся сделать какую-то другую норму по-хитрее. Может быть, где-то удастся подобное применить для оптимизации.
Я оцениваю это, как маловероятное.
А вот усложнять метрику, как раз, считаю перспективным делом.
SSIM-подобное попробовать, для начала, что ли...
Метрическими пространствами можно описать очень, очень многое.
И в них есть хорошие быстрые алгоритмы.
Я пытался когда-то составлять метрику через триангулирование изображения и попытку сделать что-то типа "Левенштейна" дальше.
Если бы сейчас продолжил, то может быть, что-то бы и получилось.
Другое направление, это усложнять набор сжимающих отображений. Правда, это сильно специфично относительно заданной метрики.
Как-то так.
no subject
Date: 2012-12-19 12:35 pm (UTC)Например, можно фрактально сжимать не саму картинку, а вавлет-преобразование. И сжимать не RGB, а какое-нибудь YUV. И с разной степенью сжатия для разных компонент.
no subject
Date: 2012-12-19 01:40 pm (UTC)no subject
Date: 2012-12-19 01:49 pm (UTC)no subject
Date: 2012-12-19 02:13 pm (UTC)no subject
Date: 2012-12-19 02:17 pm (UTC)no subject
Date: 2012-12-19 02:33 pm (UTC)no subject
Date: 2012-12-19 08:27 am (UTC)А что если не делить картинку на блоки точно, а попробовать альтернативы:
- Базовые блоки с немного пересекающимися границами - насколько я понимаю, в области пересечения метод будет автоматически усреднять результат;
- Блок не в виде квадрата, а в виде какого-то "гауссового" облака - ближе к краям становится прозрачнее
Это я к проблеме проявляющихся квадратов при увеличении.
no subject
Date: 2012-12-19 09:31 am (UTC)no subject
Date: 2012-12-19 10:05 am (UTC)Да, в первом варианте с пересечением квадратных блоков, их просто станет чуть-чуть больше.
Не вижу других причин для увеличения алгоритмической сложности метода.
no subject
Date: 2012-12-19 10:20 am (UTC)С пересекающимися блоками вполне может сработать. Просто данных придется хранить больше. Как обычно - увеличение качества за счет уменьшения компрессии.
no subject
Date: 2012-12-19 08:32 am (UTC)no subject
Date: 2012-12-19 08:38 am (UTC)Этот метод, получается, даже решает проблему различных DPI у современных устройств. Красота.
no subject
Date: 2012-12-19 10:31 am (UTC)В целом метод не обрел популярности, ибо сжатие требует большого перебора, соотношение качество/размер не шибко крутое (чтобы обойти jpeg уже надо постараться), да и патенты не способствуют.
no subject
Date: 2012-12-19 10:58 am (UTC)Спасибо что показали этот замечательный кусочек реальности =) Пожалуй, это первое практическое применение фракталов, которое мне встретилось.
no subject
Date: 2012-12-20 02:44 pm (UTC)no subject
Date: 2013-01-30 09:09 pm (UTC)