Айтишникам: С интересом прочитал про формат DjVu – в нем часто распространяются книги, ноты, рукописи. Оказалось, что механизм сжатия, используемый там, в 20-100 раз лучше, чем привычные нам JPEG и GIF – до 15Кб на страницу. Как работают внутри эти два формата я знаю, но как можно выжать из них еще почти на два порядка, мне стало интересно.
Оказывается, вся соль в том, что изображение делится на три слоя, которые сжимаются по-разному – передний план, задний план и чёрно-белая (однобитовая) маску. Маска сохраняется с разрешением исходного файла; именно она содержит изображение текста и прочие чёткие детали. Разрешение заднего плана, в котором остаются иллюстрации и текстура страницы, по умолчанию понижается для экономии места. Передний план содержит цветовую информацию о маске; его разрешение обычно понижается ещё сильнее. Затем задний и передний планы сжимаются с помощью вейвлет-преобразования, а маска — алгоритмом JB2.
Вейвлет-преобразование, если совсем в двух словах, представляет собой разделение изображения на высокочастотные и низкочастотные области, которые по-отдельности сжимаются лучше, т.к. там ниже энтропия. Высокочастотные – это контрастные фрагменты, где яркость скачет, низкочастотные – это гладкие, где яркость меняется плавно. Совсем упрощенно говоря, это как много раз взятие производной от изображения – из-за чего гладкие структуры выражаются меньшим числом бит. JPEG работает похожим образом, только там используется другой алгоритм сглаживания (ДКП) и там работают с квадратиками 8х8, чего в вейвлетах нет.
Особенностью алгоритма JB2 является то, что он ищет на странице повторяющиеся символы и сохраняет их изображение только один раз – т.е. кластеризует картинку на похожие области. Примерами таких кластеров, например, могут служить все буквы ‘a’, напечатанные одним шрифтом одинакового размера. Немного отличающиеся буквы ‘a’, например, с искажениями от сканирования, или напечатанные другим шрифтом, попадут в другие кластеры. В результате получается словарь, в котором объединены часто встречающиеся одинаковые буквы. Затем для каждой буквы запоминается её место. Получается весьма компактно. В целом он аналогичен JBIG2, о котором информации в сети значительно больше. В многостраничных документах каждые несколько подряд идущих страниц пользуются общим «словарём» изображений.
Интересная же эта область, компьютерная графика. Когда-то же увлекался.
Being in America 