OCR форумы Добро пожаловать, Гость. Пожалуйста, выберите Вход или Регистрация
Всем привет!
Hi all!
 
  ГлавнаяСправкаПоискВходРегистрация Администратор Библиотека  
 
Переключение на Главную Страницу Страниц: 1
Послать Тему Печать
Утилита djvudict для исследования Djbz/Sjbz словарей (Прочитано 3462 раз)
truf
Активист
***
Вне Форума



Сообщений: 254
Утилита djvudict для исследования Djbz/Sjbz словарей
03.06.2019 :: 18:23:58
 
Я наколхозил для собственных нужд на основе проекта minidjvu консольную утилиту djvudict (назвал от балды, можно подобрать по-лучше).

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

Утилита предназначена для исследования словарей, кодированных в DjVu документе.
В отличие от djvudump из пакета DjVuLibre, она не просто выдирает чанки Djbz и Sjbz, но разбирает их на части, сохраняя элементы в формате BMP, а также считая статистику их использования на странице и в документе в целом.

Исходники и подробное описание на английском тут: https://github.com/trufanov-nok/djvudict
Бинарники, в т.ч. под Win64, тут: https://github.com/trufanov-nok/djvudict/releases


Я последнее время задался вопросом недостаточно, на мой взгляд, большого сжатия, достигаемого свободными opensource кодировщиками при кодировании многостраничных DjVu документов, по сравнению с проприетарными. Я кодировал одни и те же ч/б документы разными кодировщиками и использовал djvudict чтобы оценить организацию в них словарей и статистику их использования на страницах.

Простыми словами о теории, как я ее понимаю:

Если вкратце, то кодировщики сегментируют оригинальное изображение на то, что будет восприниматься как ч/б текст и то, что будет восприниматься, как изображение. Эти сегменты (чанки, chunk) кодируются разными методами и упаковываются в единый документ, что и можно назвать foreground и background слоями. Собственно, особую компактность по сравнению с другими форматами, DjVu документы достигают за счет компрессии именно слоя текста.

Текст кодируется в изображении в формате JB2, которые хранятся в документе в сегментах с id Sjbz, по одному на страницу. JB2 по-сути, является набором инструкций. Каждая инструкция может кодировать небольшой символ (букву), просить отрисовать его на изображении в заданной позиции И/ИЛИ может просить "запомнить его" для последующего использования. Следующая инструкция может не кодировать символ, а просто просить отрисовать на странице запомненный символ в новом месте.

Т.о. при последовательном чтении инструкций из JB2 изображения создается некий локальный словарь, и за счет его использования достигается компрессия. Это важно - даже в одностраничном документе всегда есть словарь.

Логично, что если у вас многостраничный документ, то словари символов на соседних страницах могут иметь много общих символов, и можно достичь куда большей компрессии сделав для них общий словарь. Этот общий словарь создается обычно на каждые 10-20 страниц и сохраняется в сегменте Djbz в формате такого же JB2 изображения (авторы не стали выдумывать велосипед). Только такое JB2 изображение имеет размеры 0x0 и в нем нет инструкций, которые бы просили что либо отрисовать - только запомнить для будущего использования.

Т.о. общие словари Djbz - это такие же изображения, как и Sjbz, только они 0-го размера и на них ничего не отрисовывается. Если JB2 изображение страницы из Sjbz сегмента кодировано с использованием общего словаря, то самой первой инструкцией будет требование найти этот общий словарь по id и считать из него N символов в свой локальный словарь. После чего JB2 изображение строится как обычно. Т.о. общий словарь просто инициализирует локальный словарь страницы.

Стоит добавить, что сами симолы в JB2 формате могут кодироваться как прямо (direct coding), так и на основе некого прототипа (refinement coding - уточняющее кодирование?). Во втором случае кодируется не каждый пиксель символа, а указывается символ-прототип (по индексу в словаре) и разница между ним и тем, что кодируется. Это позволяет дополнительно сэкономить на хранении похожих букв, например Ш и Щ. При этом прототип сам может быть кодирован на основе прототипа. Такое кодирование используется в том числе в рамках общего словаря (Djbz), где ничего не отрисовывается.

Что на самом деле делает djvudict

Утилита djvudict ищет в DjVu документе (поддерживается bundled multi-page) все JB2 изображения (Djbz и Sjbz сегменты) и для каждого вываливает в его подпапочку те символы локального словаря, которые в нем напрямую закодированы. Т.о. если этим JB2 изображением является общий словарь Djbz - то все его символы будут сохранены в bmp. Если это Sjbz в single-page DjVu (кодируется без Djbz) - то будут сохранены все символы из его локального словаря. Если это Sjbz в multi-page DjVu - то будут сохранены те символы локального словаря, которые не заимствованы из общего Djbz словаря.

Кроме того, сохраняется лог последовательности типов инструкций в JB2 изображении с индексами. Ведется статистика использования этих инструкций по странице и в документе. Сообщается размеры словарей, кол-во символов на странице, число обращений к локальному или общему словарю, число прямо и уточняющее кодированных символов. Также для Sjbz в папке рендерится BMP всей страницы. В идеале хотелось бы буквы цветом на ней маркировать, но лучшее - враг хорошего.

Ну и смотря на это можно пытаться угадать, за счет чего один ч.б. документ сжатый проприетарным кодировщиком на пол мегабайта меньше такого-же, сжатого свободным кодировщиком. Где там слишком маленький или большой словарь, слишком плохое его использование, где плохо ищутся прототипы для уточняющего кодирования и пр.

Я в отдельном посте напишу свои мысли по тому, что можно было бы в этом направлении сделать в кодировщике minidjvu.
Наверх
 
 
IP записан
 
AAW
Патриарх
*****
На Форуме


Старую детскую и НП литературу
ничем не заменить

Сообщений: 5571
Екатеринбург
Пол: male
Re: Утилита djvudict для исследования Djbz/Sjbz словарей
Ответ #1 - 10.06.2019 :: 07:40:16
 
truf писал(а) 03.06.2019 :: 18:23:58:
можно пытаться угадать, за счет чего один ч.б. документ сжатый проприетарным кодировщиком на пол мегабайта меньше такого-же, сжатого свободным кодировщиком

этакий анализ мыслей профессионалов?
а почему не проще влепить в minidjvu общие научные достижения в этой сфере? неужели трудно выйти на математиков, которые подскажут алгоритмы и идеи?

и несколько оффтоп:
Поюзал я весной pdf кодирование с использованием Ruby и бесплатного кодера jbig2enc. Не понравилось. Точнее, не рискую применять в публичных выкладках. Кодер имеет очень резкую зависимость вероятности подмены символов от параметра коэффициента похожести. Буквально так: ставлю 0,75 - множественные подмены различных букв налицо, ставлю 0,76 - подмен нет совсем. Не обнаруживаю их. И на разных книгах порог разный.
Опыта у меня тут нет, только кодер djvu (documenttodjvu). Там, всё-таки, настройка lossless|quasilossless|...|aggressive очень плавная.
Такая сильная чувствительность к настройкам заставляет провести полноценные тесты jbig2enc, как в своё время проводили с кодерами djvu. Например, книги с иероглифами как будут кодиться. Там ведь любая микрозакорючка несёт смысл. И тому подобное. Что-то там явно надо допилить. Может даже сам кодер и хорош, я до его доки пока не добрался, по уму к нему бы оболочку по типу djvusmall.
Хочу обратить внимание посетителей форума на эту проблемку.
Наверх
 

Если не я за себя - то кто за меня? Но если я только за себя - то зачем я нужен? И если не сейчас - то когда? (с) Гиллель, предположительно
155803224  
IP записан
 
truf
Активист
***
Вне Форума



Сообщений: 254
Re: Утилита djvudict для исследования Djbz/Sjbz словарей
Ответ #2 - 16.06.2019 :: 23:02:51
 
AAW писал(а) 10.06.2019 :: 07:40:16:
а почему не проще влепить в minidjvu общие научные достижения в этой сфере? неужели трудно выйти на математиков, которые подскажут алгоритмы и идеи?

С наукой там оказалось и так все в порядке. Там с инженерной частью проблемы. Про minidjvu я продолжаю тут: http://publ.lib.ru/cgi/forum/YaBB.pl?num=1560707465
Наверх
 
 
IP записан
 
Переключение на Главную Страницу Страниц: 1
Послать Тему Печать