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

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

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

Интересным свойством этого метода является то, что результат формулируется в векторном виде, и декодировать картинку можно в произвольное разрешение. Выше она декодирована в 512х512, в контесте декодировалась в 1024х1024, а вот тут, например, ее фрагмент при разжатии в 2048х2048. При увеличении картинка получается заметно более четкая, чем при увеличении растровых картинок каким-нибудь Ланцошом, линии сохраняют плавность, но все заметнее становятся границы блоков. На этой идее работают некоторые фрактальные увеличивальщики картинок.
thedeemon: (Default)
В предыдущих частях мы без особенных усилий построили компрессор, который жмет сильнее, чем zip, rar, bz2 и 7z в их режимах по-умолчанию. Однако примененным технологиям хоть и не 30 лет, как LZ, но не меньше 15. Куда продвинулся прогресс за это время?
Read more... )
thedeemon: (Default)
(начало цикла здесь)

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

В предыдущей части мы увидели, что вычисленная в лоб по вероятностям символов информационная энтропия файла дает оценку снизу по сжатию для оперирующего этими вероятностями арифметического кодера, однако простой zip умудряется сжать текст в полтора раза лучше. Все дело в том, что до этого момента мы рассматривали лишь индивидуальные символы, не обращая внимания на то, что их порядок не совсем случаен: текст состоит не из произвольной последовательности символов, а из слов языка и знаков пунктуации. Если мы прочитали последовательность букв "функц", то можем быть почти уверены, что следующая буква будет "и". Когда в английском тексте встречается буква "q", то если этот текст не про Аль-Каиду, следующая буква почти наверняка будет "u". Как это можно формализовать? Рассматривая текущий символ как случайную величину Х, можно предыдущий символ считать другой наблюдаемой одновременно с Х случайной величиной Y. Понятно, что мат.ожидание и дисперсия у них будут одинаковые, но раз они как-то связаны, можно предположить, что между ними будет корреляция. Попробуем посчитать коэффициенты корреляции для символов i и i-k:Read more... )
thedeemon: (Default)
В предыдущей части мы на ровном месте переизобрели арифметическое сжатие и получили формулу среднего количества бит на символ при оптимальном сжатии для случая статического разбиения на интервалы. Внезапно она внешне совпала с Шенноновской формулой информационной энтропии.

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

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

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

Оказывается, этих требований достаточно, чтобы искомую функцию вывести.Read more... )
thedeemon: (Default)
Некоторое время назад я заметил, что большое количество работников индустрии информационных технологий имеют крайне смутное представление о том, что такое информация, что одновременно смешно и печально. Кто-то по этому вопросу ударяется в неконструктивную философию, кто-то вспоминает полторы формулы из теории информации, не особо вникая в их смысл. Между тем, мне кажется, есть довольно хороший путь к пониманию, и этот путь пролегает через сжатие данных. Когда речь заходит о сжатии, большинство вспоминают про RLE, алгоритмы семейства LZ и коды Хаффмана (на них основана zlib, а что еще нужно?). Но это все равно что сказать "Программирование? Да-да, знаю. Фортран и Кобол".
Поскольку мне наивно кажется, что в сжатии данных я кое-что понимаю, я решил сделать образовательную серию постов, в которой мы, пользуясь школьной математикой и несколькими банальными идеями и наблюдениями, выведем некоторые важные факты теории информации и напишем на чистом функциональном языке компрессор, который будет сжимать лучше, чем zip, rar, bzip2 и 7z в их дефолтных режимах. Потом оглядимся вокруг, в том числе на физику, и в результате, надеюсь, что-то поймем об информации.

Часть 1. Изобретаем арифметик


Read more... )

Profile

thedeemon: (Default)
Dmitry Popov

September 2017

S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627282930

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 26th, 2017 07:23 am
Powered by Dreamwidth Studios