Фрактальное сжатие
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. При увеличении картинка получается заметно более четкая, чем при увеличении растровых картинок каким-нибудь Ланцошом, линии сохраняют плавность, но все заметнее становятся границы блоков. На этой идее работают некоторые фрактальные увеличивальщики картинок.
