Фракталы бывают очень разные по своему устройству, но объединяет их самоподобие: какие-то части в них похожи на другие их же части в другом масштабе. Фрактальный метод сжатия изображений берется сделать фрактал из любой картинки, ведь если взять произвольную фотку, там можно найти немало похожих фрагментов:

:)
Ну, может не везде столь же хорошо, но если для какого-то куска не находится похожего, его можно разбить на кусочки поменьше и поискать для них. В конце концов, на уровне отдельных пикселей найти похожие уж точно не проблема. Итак, возьмем картинку, разобъем ее на блоки и для каждого блока будем искать похожий блок большего размера. Он может быть где угодно. Он может быть как угодно повернут и растянут, даже нелинейно. Разрешим этому блоку также иметь другой контраст (вплоть до инвертированного) и яркость, лишь бы контраст был больше. Запишем найденное в виде набора соотношений "блок такой-то очень похож на такую-то область, к которой применили вот такое геометрическое преобразование, а яркости умножили на k и добавили константу b" (константы для разных блоков будут разные). Оказывается, что этих соотношений нам достаточно, чтобы восстановить картинку. Если геометрическое преобразование сжимающее (уменьшает расстояние между любыми двумя точками), и преобразование яркости тоже (константа k по модулю меньше единицы), то, слава матану, взяв произвольные начальные значения яркости и применив эти преобразования в цикле некоторое количество раз, мы придем к неподвижной точке всей системы преобразований, она и будет картинкой. Теперь отложите ваши айпады на помоечку и полюбуйтесь вот этими 58 килобайтами флэша.

Тут видны получающиеся на разных итерациях из изначального хаоса картинки, а поводив мышкой по блокам, можно видеть, какие блоки берутся за источники. Как вы догадались, в прошедшем соревновании картинка была сжата именно этим способом. Чем сложнее доступное геометрическое преобразование для блока, тем выше можно получить качество, но тем больше данных придется хранить. В данном случае исходные блоки брались ровно вдвое больше текущего, никаких поворотов не делалось, поэтому сохранялись лишь координаты блока (по 9 бит на координату) и коэффициенты k и b (7 и 10 бит соответственно). Изначально картинка была разделена на 64х64 блока, некоторые из них поделились рекурсивно на 4 поменьше, некоторые из тех еще на 4 поменьше, всего чуть меньше 9000 блоков, что заняло 40 КБ данных.

Интересным свойством этого метода является то, что результат формулируется в векторном виде, и декодировать картинку можно в произвольное разрешение. Выше она декодирована в 512х512, в контесте декодировалась в 1024х1024, а вот тут, например, ее фрагмент при разжатии в 2048х2048. При увеличении картинка получается заметно более четкая, чем при увеличении растровых картинок каким-нибудь Ланцошом, линии сохраняют плавность, но все заметнее становятся границы блоков. На этой идее работают некоторые фрактальные увеличивальщики картинок.

(начало цикла здесь)

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

В предыдущей части мы на ровном месте переизобрели арифметическое сжатие и получили формулу среднего количества бит на символ при оптимальном сжатии для случая статического разбиения на интервалы. Внезапно она внешне совпала с Шенноновской формулой информационной энтропии.

Сам Шеннон получил свою знаменитую формулу совсем иначе. Он рассматривал источники, выдающие сообщения с вероятностями Pi, и искал такую функцию H, которая бы выражала объем информации в сообщении, была бы мерой неопределенности.

К искомой функции он предъявлял следующие требования:
1. H должна быть непрерывной функцией от Pi.
2. Если все сообщения равновероятны, т.е. Pi = 1/N, то H(N) должна монотонно возрастать c ростом N: чем больше вариантов разных равновероятных сообщений, тем больше информации несет одно сообщение.
3. Если сообщение разбивается на несколько последовательно идущих, то мера Н информации в нем должна быть взвешенной суммой значений Н для частей. Например, если нам нужно передать сегодняшнее число, то не важно, пошлем мы месяц и день в одном сообщении или сначала месяц, а потом день, количество переданной информации должно быть одинаковым в обоих вариантах. Если вероятности и сообщения представить в виде дерева, где в узлах стоят сообщения, а дугам приписаны вероятности посылки следующих сообщений (например, из корня идут дуги к вариантам первого бита сообщения, из них - к вариантам второго бита и т.д., примерно как при построении дерева для кодов Хаффмана),

то
H(узла) = сумма по исходящим веткам от: P(ветки)*H(ветки).

Оказывается, этих требований достаточно, чтобы искомую функцию вывести.( Read more... )