OCR форумы Добро пожаловать, Гость. Пожалуйста, выберите Вход или Регистрация
Всем привет!
Hi all!
 
  ГлавнаяСправкаПоискВходРегистрация Администратор Библиотека  
 
Страниц: 1 
Послать Тему Печать
Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu (Прочитано 17422 раз)
truf
Активист
***
Вне Форума



Сообщений: 254
Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
16.06.2019 :: 20:51:05
 
Тут длинно. Если в кратце, я начал сомневаться, что DjVuLibre/minidjvu кодирует многостраничные документы хуже коммерческих кодировщиков. Он просто жутко медленный. Мотайте до красного - до тестов варианта minidjvu с открученной в нём оптимизацией скорости.



Год назад я решил запихнуть в Scab Tailor Universal еще один этап обработки - создание DjVu документа.
Хотелось достичь следующего:

1. Делать кодирование по методу разделенных сканов (background и foreground отдельно) напрямую из STU, избавив от необходимости делать экспорт и пользоваться DjVu Imager.
2. Позволить устанавливать индивидуальные параметры кодирования для каждой страницы.
3. В реальном времени видеть изменения, чтобы ирать с параметрами.

С прицелом на дальнейшее прикручивание добавления Оглавления и внедрения слоя распознанного текста в hOCR.
Я еще и поддержку различных кодеров вынес в QML (скрипт) плагины, чтобы их без меня могли добавлять. На Linux'ах, а для меня это - основная платформа, все это должно было работать на кодерах пакета DjVuLibre.

В общем, замах был на рубль.

В результате получалось так (кликабельно):
...

Все работало, странички кодировались в single-page DjVu, бодро отображались и я дошел до сборки их в готовый документ.  И тут я обнаружил, что страшно лоханулся. Собираемый утилитой djvm из пакета DjVuLibre bundled multi-page DjVu документ оказался неподъёмно большого размера. Все от того, что он просто составляет djvu страницы стопочкой, но не производит перекодирования их словарей и создания общего словаря.
djvm используется в DjVu Imager (он меня и запутал), но там он потрошит уже готовый bundled multi-page djvu, по сути превращая его в indirect multi-page DjVu. Затем меняет/добавляет чанки картинок в этих отдельных страницах с помощью djvumake и собирает их обратно в bundled multi-page DjVu при помощи djvm. В общем, словари сохраняются as is.

В DjVu Libre никакой возможности создания Djbz словарей я не обнаружил. Проект minidjvu я в тот момент вообще не рассматривал, а может и рассматривал - попробовал, увидел результат и расстроился еще больше.

Делать дефолтным djvu кодировщиком проприетарный кодировщик, который собран только под винду, и тащить зависимость от wine, необходимого для запуска виндовых программ под линуксом - это не в какие ворота не лезет. В итоге я расстроился и забил на весь этот зоопарк кодеров, на данный функционал, и, закинув код в отдельную ветку, прекратил все это делать.

И вот, прошло еще пол года, и неделю назад с мыслью "Да чеж там так всё плохо-то?" я полез разбираться в свободные opensource'ные кодировщики DjVu и DjVu формате вообще.

Я в этом деле профан, могу ошибаться. Вот чему я пришел.

Проприетарный кодировщик multi-page документа состоит из зашитого в него сегментатора, кодировщиков и сборщика djvu документа из отдельных чанков в страницы. В пакете DjVuLibre все это представлено россыпью - отдельными консольными утилитами. Всё, кроме сегментатора - его там нет.

Сегментатор отделяет на исходном изображении текст от цветных/серых изображений, чтобы позднее можно было кодировать их отдельно с помощью разных алгоритмов в разные слои страницы. Свободного специализированного opensource'ного сегментатора я не встретил, но он мне нафиг и не нужен был, так как планировалось использовать кодирование по методу раздельных сканов. И вообще - в ST есть свой, по-сути, сегментатор, который авто-поиском изображений и занимается. ST - один большой сегментатор и есть.

Что касается кодировщиков, то я не проверял, но уверен, что разница между кодировщиками видна только при кодировании текста. Не верю, что авторы в реализации кодеров смогли изобрести что-то новое в кодировании слоев изображений. Они могут иметь разные профили с разными дефолтными параметрами кодирования изображений по стандартному алгоритму и всё. Но вот менять сам алгоритм - вряд ли. Кроме того, кодирование изображений в single-page и multi-page ничем не отличается - нет там ни словарей и ничего такого, что позволяло бы выиграть от помещения изображений в один файл.

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

Итак, сосредоточимся на кодировщиках для foreground слоев с id Djbz/Sjbz.

DjVuLibre не умеет кодировать multi-page документы сходу. Он умеет собирать их из single-page документов, но от этого лучше не становится, т.к. он их просто копирует внутрь без создания общего словаря.
Я полез изучать эти словари. Краткое описание того, как оно все устроено, я приводил недавно тут: http://publ.lib.ru/cgi/forum/YaBB.pl?num=1559575438

Сходу нагуглилась opensource утилита JB2unify, позволяющая не просто собирать single-page DjVu в multi-page DjVu, но и создающая общие словари для них. (https://github.com/velwant/jb2unify) Результат ее работы оказался недостаточно хорош, т.к. она объединяет в общий словарь только символы абсолютно идентичные на обеих страницах. А они обычно, хоть на бит, но отличаются. В общем, слишком бесхитростно и соответствующе плохой результат.

Затем я обратил внимание на кодировщик minidjvu, который до этого не рассматривал, т.к. когда я о нем читал, он назван "игрушечным". Цитирую (http://www.djvu-scan.ru/forum/index.php?topic=52.0):
Цитата:
Использовать minidjvu v0.8 (MiniDjVu Plus) всерьёз для реального чёрно-белого DjVu-кодирования КРАЙНЕ не рекомендуется!!! (Для этого существуют коммерческие DjVu-кодировщики.)
<...>
Т.е. minidjvu v0.8 (в лице MiniDjVu Plus) - это "игрушечный" чёрно-белый DjVu-кодировщик.


minidjvu умеет кодировать multi-page DjVu из чего угодно, включая single-page DjVu, но есть одно но - только чёрно-белые.
В принципе, больше-то и не нужно, т.к. инструменты DjVuLibre позволяют сделать все остальное. Т.е. minidjvu способен сделать ч./б. multi-page DjVu, в который подобно DjVu Imager все остальное можно допихать. DjVu Imager в общем-то именно через утилиты DjVuLibre и работает.

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

Тут, если еще не читали, можно прочесть про формат JB2 из моего поста http://publ.lib.ru/cgi/forum/YaBB.pl?num=1559575438
и станет понятно, что Djbz от Sjbz принципиально не отличается ничем. Вообще.
Djbz в стандарт bundled multi-page DjVu был добавлен позже и, видимо, поэтому его поддержку не реализовали в DjVuLibre сразу (ничем не подтвержденное предположение). Но все алгоритмы, необходимые для составления общих словарей там есть, потому что они же необходимы для составления локального словаря страницы.

Т.о. нельзя сделать single-page кодировщик, который невозможно было бы "легким движением руки" превратить в multi-page кодировщик с поддержкой Djbz словарей. И качество этих словарей не может быть принципиально хуже качества словарей в single-page djvu.

Возникает парадокс, результаты "игрушечного" minidjvu действительно не ахти, а код в нем от "серьезного" DjVuLibre. И я полез этот код смотреть.
Выяснился даже более интересный факт - основанный на DjVuLibre код игрушечного minidjvu чуть ли не полностью этим же DjVulibre включен в себя, и используется именно для организации словаря, но только локального - Sjbz...

Кодирование multi-page документа по сути заключается в следующем:

Спойлер:
1. Берем ч.б. изображение с текстом. Применяем всякие despeckle, если нужно.
2. Режем ее на буквы/символы. Слишком большие откладываем как какую-то графику.
3. Классифицируем все символы на всех страницах (по дефолту пучок из 10 страниц) по классам. Класс объединяет очень похожие символы. Т.е. заглавная "А", строчная "а", греческая альфа, "а" курсивом, "а" другим шрифтом, "а" с грязью - это все разные классы. Это важно, т.к. все вхождения экземпляров класса на страницах будут заменены одним изображением. Вот за счет именно этого достигается львиная доля компрессии. И именно этот этап может породить проблему "ННЙ", если в класс "И" отнесут поврежденную "Н".
4. Смотрим на наши классы, если класс встречается лишь раз, то кодируем тупо в страницу. Если более двух раз появляется на странице, но нет на других - кодируем в локальный словарь страницы (т.е. тупо кодируем в страницу, но помечаем, что символ нужно запомнить и в дальнейшим ссылаемся на него по индексу). Если класс обнаружился более чем на 1й странице - кодируем в общий словарь (т.е. в локальный словарь виртуальной страницы нулевого размера).
5. Для каждого класса выбираем изображение символа, который заменит все его вхождения. minidjvu берет первое попавшееся, но по ключу -A может пробежать по всем изображениям и сделать из них усредненное. Это должно выручать, если потертая Н правильно попала в класс Н, но первым изображением этого класса в кодируемом пучке из 10 страниц встречается именно это потертое изображение.
5. Ищем в рамках страниц (включая виртуальную страницу общего словаря) прототипы для уточняющего кодирования. Важно понимать, что этот этап не может быть источником проблемы "ННЙ", т.к. тут идет lossless кодирование  изображений и ноль может уточняюще кодироваться на основе "О" из соображений экономии места, но выглядеть он будет нормально. Судя по-всему, этот этап дает сравнительно малый вклад в сжатие файла по ср. с этапом 3.
6. Пишем все это.


Теперь лезем в код minidjvu, естественно в классификатор - самое главное.
А там (https://github.com/barak/minidjvu/blob/master/src/alg/classify.c#L179):

Code (C++):
 if (c->last_page < page - 1) continue; /* multipage optimization */ 


в цикле, объединающем одинаковые классы на разных страницах в один.

Т.е. в угоду скорости поиск осуществляется не по всем кодируемым единым общим словарем страницам, а только по соседним страницам. Если вы нашли "А" на странице 2, но не встретили её на странице 3, то такая же "А" на странице 4 будет ей не равна. Если они были также на страницах 1 и 5, то в общий словарь попадут обе. А если нет, то они останутся в локальных словарях, а то и вообще закодируются в страницу как единичные образцы.

Казалось бы, случай редкий. А давайте потеструем.

Комментируем эту строку, компиллируем minidjvu (я обозвал эту версию minidjvu_mod) и сравниваем с оригинальным minidjvu и с documenttodjvum.exe, который я вытащил из djvu_small_v0_4_4 и использую для изготовления книг по методу разделенных сканов с профилем User B&W 600.
Учтем, что documenttodjvum.exe программа виндовая и вызовы ее будут исполняться в Wine, что снизит её производительность.
documenttodjvum.exe передадим ключ --profile=my_600 (подсмотрено в логе DjVu Small).

Дальше я написал bash скрипт, который вызывает их для кодирования всех tiff файлов из папки и сохраняет время работы + размер результата. И посмотрел, сколько у меня в папках со сканами осталось подпапок ./out/export/txt/ (туда STU сохраняет foreground слой при экспорте). Нашлось аж
38
.

Результаты тестирования (кликабельно):

...


Здесь small - это documenttodjvum.exe из DjVu Small 0.4.4
orig - minidjvu
mod - minidjvu_mod (с отключенной оптимизацией в составлении Djbz)

Проценты размера документа берутся от сравнения с результатом documenttodjvum.exe. Размеры в байтах.
Проценты изменения скорости minidjvu_small берутся от скорости minidjvu (т.к. с documenttodjvum.exe сравнивать бессмысленно).

Признаюсь, что тестов было больше 38, но на двух завис documenttodjvum.exe, а на 2-х не справился minidjvu*, заявив, что tiff'ы не ч./б. Но это скорее всего у меня там tiff'ы с альфа каналом попались. Помню правил что-то такое в STU.

Итого, minidjvu с отключенной оптимизацией скорости, не просто ожидаемо превосходит оригинальный minidjvu везде, но и в среднем отстает от коммерческого documenttodjvum.exe всего на
+0.81%
.
А если выкинуть явный выброс с каким-то одностраничником на 7кб, который documenttodjvum.exe сжал в 2 раза лучше, то minidjvu еще и обойдет documenttodjvum.exe с профилем User B&W 600 на
-1.87%
.

Если рассмотреть вопрос производительности, то "оптимизация" дала minidjvu в среднем 22.85% прирост в скорости, но увеличила размер документа на 23.42% и даже после этого он остался в 6 раз медленнее documenttodjvum.exe Т.о. проблему производительности minidjvu не решил, а качество словаря потерял. (оптимизация, судя по всему, появилась в minidjvu 0.4 от 2005-06-15). DjVuLibre, содержащий minidjvu, естественно никакой оптимизации не содержит, т.к. многостраничные документы кодировать и не пытается.

Отключенная оптимизация не должна повлиять на вероятность возникновения проблемы "ННЙ" (если она вообще возникает - я ни разу с ней не сталкивался, но я OCR не занимаюсь и мог не заметить. Чукча не читатель). Наоборот, если раньше эта проблема могла проявится в масштабе пары страниц, то теперь она расползётся на 10 и ее будет проще обнаружить.

Касательно производительности, мне кажется, в наш век эта медлительность уже не так критична. Вот при царе горохе, когда documenttodjvum.exe кодировал бы что-то 5 минут, а minidjvu бы по пол часа, то да. А при нынешних CPU уже не так страшно. К тому же есть как минимум один тупой способ ускорить все в 2-3 раза - разбить кодирование и кодировать 10-ти страничные словари в 2х-4х параллельных потоках, чтобы они могли разойтись по разным ядрам процессора. Ну и в целом, в коде minidjvu много TODO пометок о неоптимальности кода и необходимости дальнейшей оптимизации.

А вообще, я бы не отказался от сверхмедленного, но сверхэффективного кодировщика. Пусть он хоть всю ночь кодирует (или перекодирует имеющийся документ), но выдаст лучший словарь и файл на 30% меньше коммерческого кодера.

Итого

Учитывая, что сегментер мне не нужен, что в серьёзную разницу нетекстовых кодировщиков я не верю и они имеются в DjVuLibre, и что minidjvu как кодировщик foreground слоя может показывать результат не хуже коммерческого, то может я и допилю когда нибудь платформу для сборки книжки из STU.

Собранные бинарники модифицированного minidjvu я прилеплю сюда чуть позднее (надо для Win собирать). Но сборку под Винду я настроил только через cygwin и будет куча лишних библиотек, а возможно и еще бОльшая просадка по производительности. Ну, посмотрим. Версии для Win32 не будет.

Все дальнейшие измышлизмы по поводу minidjvu я продолжу писать в этой ветке.
Наверх
 
 
IP записан
 
truf
Активист
***
Вне Форума



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #1 - 16.06.2019 :: 23:37:25
 
Читать можно, как обычно, с конца.

Этот пост выше я, на самом деле, написал еще полторы недели назад, но, не будь дурак - не запостил, а полез сперва компиллировать модифицированный minidjvu под винду. Действительно, с этим возникли сложности, но в итоге я его собрал при помощи Cygwin.

ОДНАКО. Выяснилось, что под богомерзкую винду программа на тестовых примерах выдавала производительность не в 4-6 раз хуже, как на линуксе, а была раз в 25 медленнее! Т.е. на одном и том же ПК (HDD Только другой марки, я их переставляю в hdd drive ноутбука заместо dvd привода) один и тот же код показывает в разы худший результат. Я погрешил на Cygwin, скачал оригинальный бинарник minidjvu под винду, собранный авторами - результат пропорционален. При этом разницы в скорости работы documenttodjvum.exe - никакой. Ну это и понятно, под линуксом она работала в симуляции Wine.

Есть вероятность, что у меня просто кривая винда. Я ставил первую попавшуюся, и ей оказалась Win 7 в конфигурации Embedded. Там пол функционала вырезано, вплоть до Task Manager'а. Поди и драйверов каких нет, так что хотелось бы проверить на нормальных системах, а не полудохлых обрезках.
По той же причине, профилировать программу на Винде и выяснить, что именно там в 6 раз медленнее по ср с Линуксами работает, я не смог. Но за профилировку таки взялся, но на Линуксе.

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

В итоге удалось ускорить работу почти вдвое, даже не прибегая к тривиальной многопоточности (в принципе обработка каждых 10-ти страниц не зависит от других и это можно делать параллельно. Но documenttodjvum в такой хитрости замечен не был - и я не стал). На этом мой энтузиазм пока кончился и я решил выкладывать что есть.

Следует заметить, что под моей виндой мой вариант minidjvu остается на порядок медленнее. Но теперь не в ~20 раз, а в ~10. Ну а под линуксом православным все гораздо лучче и трава зеленее.


Сборки я заготовил тут: https://github.com/trufanov-nok/minidjvu_mod/releases/tag/perf_test
Там куча dll - это из-за компиляции в Cygwin. На практике можно собрать без них, но мне лень разбираться.
Та версия, что not_optimized - это оригинальный код с отключенной оптимизацией составления общего словаря.
Та версия, что просто _mod - это то же, но с моим колхозным творчеством для компенсации потери производительности. Увеличение размера экзешника объясняется попыткой прикрутить библиотеку линейной алгебры Eigen - там железо-зависимые оптимизации работы с векторами есть.
Код изменений, естественно, опубликован рядом.

С высокой долей вероятности, переименовав minidjvu_mod в minidjvu, его можно подложить (с dll'ками) под MiniDjVu Plus и пр. GUI/скрипты. Командный интерфейс программы не менялся.

Наверх
« Последняя редакция: 17.06.2019 :: 02:09:29 от truf »  
 
IP записан
 
AAW
Патриарх
*****
Вне Форума


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

Сообщений: 5544
Екатеринбург
Пол: male
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #2 - 17.06.2019 :: 09:42:20
 
truf, спасибо!

truf писал(а) 16.06.2019 :: 20:51:05:
Класс объединяет очень похожие символы

А в чём причина проблемы инь?
На ум приходит, что при определении "схожести" должна была делаться какая-нибудь псевдовекторизация. Хотя бы для случая типичного размера матрицы. Определили осевые линии (как при ocr) символа, и схожесть вычисляется с учетом осей. Но я, наверное, наивен Улыбка
Наверх
 

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


Всем привет!

Сообщений: 890
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #3 - 17.06.2019 :: 15:51:59
 
Мне кажется вы немного не туда смотрите.

вот в FSD    вызывается либо msepdjvu  из DEE, либо csepdjvu из DjvuLibre.
Если разделение фон/маска уже произошло (а оно произошло), то остальные утилиты уже и не нужны.

Оба делают многостраничное кодирование.   Мне кажется, я видел где-то пост леона боту об отличиях кодирования в csepdjvu, но пока не могу найти.   

Зачем тут вообще minidjvu ??? 
Для WinXp   можно просто точно также дать возможность вместо csepdjvu  вызывать msepdjvu, прописав путь.
Наверх
 
 
IP записан
 
truf
Активист
***
Вне Форума



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #4 - 17.06.2019 :: 22:42:10
 
@
AAW

По поводу проблемы инь:

Технически minidjvu делает следующее (как я это понимаю). Режет изображение текста (после сглаживания) на изображения букв, т.е. достаточно маленьких черных объектов. Из каждого такого объекта он делает "паттерн" путем скелетонизации. При этом, все что было черным, становится серым (grayscale) - чем ближе к скелету, тем темнее. Т.о. буква O будет представлять из себя черное кольцо толщиной в 1-2 пикселя, проходящее примерно посередине между внутренним и внешним контурами буквы, и градации серых пикселей спадающей до 0 окраски от этого кольца до контуров. Дальше работа ведется с такими паттернами.

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

Это все классификация. Теперь о сравнениях 2х паттернов. Они упорядочены по возрастанию трудозатратности, чтобы не терять время, если самый первый ответит "нет".

1. Простое - сравнивают размеры и массу (сумму всех пикселей) паттернов. Они не должны отличаться более чем на N процентов.

2. Для всех паттернов заранее рассчитаны два вектора длиной 32. Сравнивается расстояние между парами этих векторов. Вектора представляют собой площади (массу) участков изображения. Если я правильно понял, изображение режется вдоль так, чтобы с обоих сторон было примерно поровну площади, затем поперек. Считаются площади таких участков. Затем каждый кусок снова режется вдоль и поперек. И т.д. пока не получат 32 числа. Т.о. паттерн будет разделен сеткой, отцентрированной по распределению его площади и посчитана площадь на разных уровнях детализации. Векторов два, т.к. один считается с учетом пикселей, закрашенных в градацию серого, а второй все не ч/б пиксели считает черными (т.е. считается по оригиналу изображения).
Вектора рассчитываются один раз при создании паттерна и сравнивать их быстро. При сравнении важность площадей разных участков имеет разный вес (то ли убывает от крупных к мелким, то ли наоборот - не помню) - настраивается параметрами.

3. Проводится попиксельное сравнение двух паттернов. При этом все серые пиксели считают черными. Перед сравнением отличные по размеру паттерны слегка выравнивают по центру масс. Первый паттерн слегка утолщают, второй утоньшают. Вычисляют пенальти за непопадание второго в первый. Превысила n% от площади - операцию прерывают и говорят "нет". Затем паттерны меняют местами и повторяют еще раз. Утолщенные и утоньшенные версии паттернов вычисляются заранее при создании паттерна.

4. Последнее сравнение выполняется только если применяется сжатие с потерями. Тут сравнивают два паттерна попиксельно напрямую (без уменьшения/утолщения). Пенальти считается за несовпадение скелетов паттернов. Серые пиксели смягчают штраф. Тоже есть механизм прекращения сравнения если штраф превышает критическое значение.

Все эти сравнения регулируются набором параметров, таких как N% откланения разницы размеров и площадей, затухание важности компонентов векторов. Пороги того, где уже "нет" или "да", а не еще "не знаю". Они подобраны авторами и жестко закодированы в программе. В зависимости от желаемой агрессивности сжатия с потерями (передается командной строкой) их интерполируют в ту или др сторону.

После того, как все паттерны раскиданы по классам программа прикидывает, какие из этих классов состоят из более чем одного паттерна. Такие классы пойдут в локальные (если все паттерны с одной страницы) или глобальный (если паттерны встречаются на разных страницах) словари.
Затем для каждого класса выбирается эталонное изображение. Берется либо первое попавшееся, либо усредняются изображения всех изображений паттернов в классе. Оно помещается в словарь, а все вхождения всех прочих паттернов этого класса заменяются ссылкой на него с нужными координатами.
Наверх
 
 
IP записан
 
truf
Активист
***
Вне Форума



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #5 - 17.06.2019 :: 22:43:23
 
@
xyz

Касательно csepdjvu/msepdjvu

msepdjvu, насколько я понимаю - коммерческий и виндовый. Что он там делает неизвестно. Нужно кодировать и смотреть, что внутри DjVu документа получается.
А вот насчет csepdjvu понятно всё из открытого кода (но я его не запускал, мне sep файлы создавать лень).

И minidjvu тут очень даже причем. Он заявлен как основанный на DjVuLibre, но по факту, кусок minidjvu находится в этом самом DjVuLibre. Он лежит в папочке ./tools/jb2cmp/ и это именно что классификатор и сравнивалка паттернов от словаря. Этот классификатор завернули в 2 функции - tune_jb2image_lossy() и tune_jb2image_lossless(). Они принимают ссылку на одну единственную страницу. Первую функцию дергает только кодировщик cjb2, а вторую (lossless) - кодировщики cjb2, cpaldjvu, csepdjvu. Т.о. все, что в DjVuLibre сталкивается с необходимостью кодировать текст, исползует классификатор minidjvu. При этом, несмотря на то, что локальные словари Sjbz создаются, никаких попыток создать из них общий Djbz словарь не предпринимается. И csepdjvu не исключение - он просто сшивает странички стопочкой, как и djvum. Это в коде прекрасно видно.

А без составления общих словарей можно забыть о сравнимым с коммерческими кодерами размере документа.
DjVuLibre умеет делать с Djbz чанками только 2 вещи - выдирать из djvu документа при помощи djvudump, и засовывать обратно при помощи djvumake. А создавать с нуля не умеет.

Т.о. DjVuLibre в части кодирования словарей текста полагается на minidjvu, но никаких попытак использовать их наработки для составления общих словарей не делает. А если бы и делал - столкнулся бы с вопросом производительности. Возможно в это все и уперлось, а может они и не особо хотели с коммерческими кодеками бодаться.
Наверх
 
 
IP записан
 
truf
Активист
***
Вне Форума



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #6 - 17.06.2019 :: 23:12:37
 
Кстати, разглядывая кодеки DjVuLibre я отметил, что все они умеют малоцвет в foreground, а не background слое. И полез посмотреть, как это вообще делается. Оказывается все довольно просто. В документ для каждой страницы добавляется чанк FGbz, содержащий номер цвета из указанной палитры цветов для каждой буквы. Т.о. при наличии FGbz во время рендеринга djvu документа программа-рендерер достает очередной (номер N) ч/б символ из JB2 изображения или его словаря и смотрит, какой должен быть цвет номер N в таблице FGbz. Если надо, перекрашивает черные пиксели, после чего ставит куда велено. И т.д. до упора.

Такой малоцвет легко прикрутить в сам minidjvu. Сейчас он просто плюется от любого не монохромного изображения. А можно все color изображения предварительно на лету пастеризовать и запомнить результат. Затем бинаризовать его в ч/б и сжать бинаризованное в JB2 как обычно. В процессе добавления каждой новой буквы в JB2 изображение смотреть по её координатам в участок пастеризованного изображения её размера, прикидывать, какой в этой позиции доминирующий 'не белый' цвет, и добавлять его в FGbz. И всё - малоцвет готов.

Подробнее про FGbz написано в статье Метод раскраски маски http://www.djvu-soft.narod.ru/scan/mask_color.htm
Наверх
 
 
IP записан
 
AAW
Патриарх
*****
Вне Форума


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

Сообщений: 5544
Екатеринбург
Пол: male
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #7 - 18.06.2019 :: 05:23:45
 
truf писал(а) 17.06.2019 :: 23:12:37:
прикидывать, какой в этой позиции доминирующий 'не белый' цвет

будет проблема усреднённого цвета. когда не-белые куски соприкасаютсся не по координатным осям. хорошо в DSM-справке описано.
пример усреднения тут: http://publ.lib.ru/cgi/forum/YaBB.pl?num=1156785706/270#270
Наверх
 

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



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #8 - 18.06.2019 :: 17:04:52
 
AAW писал(а) 18.06.2019 :: 05:23:45:
будет проблема усреднённого цвета. когда не-белые куски соприкасаютсся не по координатным осям. хорошо в DSM-справке описано.
пример усреднения тут: http://publ.lib.ru/cgi/forum/YaBB.pl?num=1156785706/270#270

Тогда, навскидку:
Берем изображение, если цветов больше N - пастеризуем до N.
Дальше для каждого цвета делаем копию изображения, на которым присутствует только этот цвет и белый цвет (расслаиваем исходное изображение). Рассматриваем каждый слой. Если белого цвета нет вообще - то этот цвет - фон. Если есть, но мало, то это белый текст на фоне. В остальных случаях - это цветной текст без фона (на белом фоне).
Последовательно режем все эти слои на буквы, запоминая их цвет(в Fgbz). Потом буквы сваливаем в кучу и сортируем в ней по координатам (емнип, они должны помещаться в JB2 по мере появления с левого верхнего угла).
Считаем все буквы черными и строим локальный и общий словари как обычно. Сохраняем вместе с Fgbz и указанием найденного цвета фона.
Наверх
 
 
IP записан
 
AAW
Патриарх
*****
Вне Форума


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

Сообщений: 5544
Екатеринбург
Пол: male
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #9 - 19.06.2019 :: 06:49:45
 
truf писал(а) 18.06.2019 :: 17:04:52:
если цветов больше N - пастеризуем до N

идеология обычно вроде такая: если входные файлы не соответствуют типу запроса, то давать отказ (не пытаться получить результат любой ценой).
А в остальном, наверное, правильный алгоритм.
Наверх
 

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



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #10 - 20.06.2019 :: 19:23:03
 
truf писал(а) 17.06.2019 :: 22:43:23:
И minidjvu тут очень даже причем. Он заявлен как основанный на DjVuLibre, но по факту, кусок minidjvu находится в этом самом DjVuLibre. Он лежит в папочке ./tools/jb2cmp/ и это именно что классификатор и сравнивалка паттернов от словаря. Этот классификатор завернули в 2 функции - tune_jb2image_lossy() и tune_jb2image_lossless(). Они принимают ссылку на одну единственную страницу. Первую функцию дергает только кодировщик cjb2, а вторую (lossless) - кодировщики cjb2, cpaldjvu, csepdjvu. Т.о. все, что в DjVuLibre сталкивается с необходимостью кодировать текст, исползует классификатор minidjvu. При этом, несмотря на то, что локальные словари Sjbz создаются, никаких попыток создать из них общий Djbz словарь не предпринимается. И csepdjvu не исключение - он просто сшивает странички стопочкой, как и djvum. Это в коде прекрасно видно.


У меня поправочка:

1. tune_jb2image_lossless() классификатор не использует вообще за ненадобностью, а только производит refinement encoding символов (тоже алгоритм из minidjvu) для компрессии того что есть.

2. В DjVuLibre, судя по всему, старый классификатор из minidjvu версии 0.33 от 2005 года. Там поддержки multipage encoding'a вообще еще не было. Она появилась в minidjvu со сл версии - 0.4. Кроме того, классификатор несколько отличается от того, что сейчас в версии 0.8:
а). Несколько иные дефолтные параметры агрессии и интерполяции её уровня.
б). Паттерн относят к классу если только никто не сказал "нет" (в версии 0.88 для этого требуется еще что бы хоть кто-нибудь сказал "да")
в). Сравнение 3 было другим.

В общем, можно считать отличия существенными. И нужно отмечать, что в DjVuLibre не просто классификатор minidjvu, а старый классификатор minidjvu.
Наверх
 
 
IP записан
 
truf
Активист
***
Вне Форума



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #11 - 20.06.2019 :: 19:25:54
 
Меня в личке попросили прокомментировать "какой классификатор (какие алгоритмы) использует кодер jbig2enc? https://github.com/agl/jbig2enc"
Положу ответ также в общий доступ:

truf писал(а) 20.06.2019 :: 17:48:35:
Прежде всего оговоримся, что JBIG2 от PDF'а - это другой формат, конкурент JB2 от DjVu, хотя по заверениям они очень похожи.
Вот тут есть отличная цитата Bottou об истории их возникновения: http://www.djvu-soft.narod.ru/scan/bookscan_pdf.htm

Словари и Общие словари в нем, судя по всему, есть. Я код не запускал, но, похоже там все сильно попроще и, соответственно, побыстрее.
У них 2 варианта классификатора и всего одна функция сравнения, которую используют оба.

Функция сравнения тут: https://github.com/agl/jbig2enc/blob/master/src/jbig2comparator.cc
Одна на весь файл. Проверки там следующие:

а. Сразу бросается в глаза, что она требует точного совпадения размеров паттернов. (К примеру, minidjvu допускает отклонение в размерах аж на 10% и  может даже немного сдвинуть одно по отношение к центру масс другого, но не более чем на 2 пикселя.)

б. Потом проверяют, отличаются ли паттерны более чем на 25% (сравнивают площадь первого паттерна с площадью разницы между двумя паттернами (xor)).

в. Дальше они страдают извращениями, либо я навскидку не разобрался - код сложный. Они берут эту разницу между двумя паттернами (полученную путем побитового XOR'а) и, по-сути, режут её на квадрат 18x18, заполняя значениями площади в этих участках. Запоминают площадь ячейки в этом квадрате в пикселях оригинального изображения. С этого момента работают только с этим квадратом:

1. Проверяется сумма значений каждого столбца квадрата, она не должна превышать ~10% от площади сответствующей ей вертикальной линии на изображении.
2. Тоже делается для значений построчных сумм.
3. Дальше этот квадрат площадей угрубляется до 9x9, т.е. 81 ячейки. В этом квадрате рассматривают все подквадратики размером 3x3 и считают площадь в ячейках по двум его диагоналям. Суммарная площадь любой из этих диагоналей не должна превышать ~10% от площади горизонтальной линии.
д. В квадрате 9x9 рассматриваются все подквадраты 2x2. Площадь в них просто суммируется. Она не должна превышать ~1% площади оригинального изображения.

Вот как-то так, в деталях и процентах я мог напутать.
В общем они, как я понимаю, пытаются проверить разницу между изображениями на плотность. У равных изображений допустим ореол из несовпадающих пикселей, разбрызганный вокруг контуров. Но не, допустим, какой-то жирный элемент. Например если вычесть из А букву Л (если писать Л углом) останется жирная палочка.

Никаких "не знаю" сравнивалка не выдает - только "да" или "нет". Т.о. она очень жесткая. Одно только требование на равный размер чего стоит.

Благодаря этой жесткости возможно применить простой классификатор.

Их два.
1й - простой. Просто сравниваются все паттерны. Если на две буквы сравнивалка сказала "да" - они помещаются в один класс. Без всяких там опросов уже отнесенных к этому классу паттернов.
2й - это 1й с поиском по хэшу. Он используется по дефолту и может быть сброшен на первый из командной строки. Сначала для каждого паттерна вычисляется хэш. Затем проводится такая же классификация, как и в 1м случае, но только для паттернов у которых хэш совпал. Хэш представляет собой три числа: ширину, высоту (это очевидно, учитывая жесткое требование совпадения размера в функции сравнения) и количество дырок.

Количество дырок вычисляется как кол-во компонентов сильной связности в (видимо инвертированном) паттерне изображения.  Т.о. 'О' в принципе никогда не будет сравниваться с 'Э'  (если её не "порвать", конечно).
Вот это - интересная идея, которую можно попробовать применить в minidjvu в попытке ускорить классификацию.

Наверх
 
 
IP записан
 
truf
Активист
***
Вне Форума



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #12 - 21.06.2019 :: 16:18:21
 
truf писал(а) 16.06.2019 :: 23:37:25:
Следует заметить, что под моей виндой мой вариант minidjvu остается на порядок медленнее. Но теперь не в ~20 раз, а в ~10. Ну а под линуксом православным все гораздо лучче и трава зеленее.


Сборки я заготовил тут: https://github.com/trufanov-nok/minidjvu_mod/releases/tag/perf_test
Там куча dll - это из-за компиляции в Cygwin. На практике можно собрать без них, но мне лень разбираться.
Та версия, что not_optimized - это оригинальный код с отключенной оптимизацией составления общего словаря.
Та версия, что просто _mod - это то же, но с моим колхозным творчеством для компенсации потери производительности. Увеличение размера экзешника объясняется попыткой прикрутить библиотеку линейной алгебры Eigen - там железо-зависимые оптимизации работы с векторами есть.
Код изменений, естественно, опубликован рядом.

С высокой долей вероятности, переименовав minidjvu_mod в minidjvu, его можно подложить (с dll'ками) под MiniDjVu Plus и пр. GUI/скрипты. Командный интерфейс программы не менялся.


Я обновил сборки по этой ссылке https://github.com/trufanov-nok/minidjvu_mod/releases/tag/perf_test

Теперь там не только x64, но и x32. И оба, я надеюсь, с поддержкой XP.

Они пересобраны при помощи MS Visual Studio 2013 со всеми оптимизациями. На скорости это не отразилось никак. Но зато библиотек тянут по-минимуму и пропал баг, при котором временный файл, создаваемый при помощи функции tmpfile(), помещался в корень диска с:/ (куда не всегда есть право доступа). У MS реализации этой функции файл создается в правильном временном каталоге. Где-то в users\AppData\local\temp... Так что при запуске на машине, где у вас ограничены права, программа не должна падать с ошибкой "Can't create temporary file".

Напомню, что версия _mod_no_optimization - это просто minidjvu с отключенной оптимизацией скорости составления Djbz, которая была в ущерб размеру файла.
а просто _mod - это то же самое, но с различными выкрутасами, призванными компенсировать падение скорости составления словаря.
Наверх
 
 
IP записан
 
AAW
Патриарх
*****
Вне Форума


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

Сообщений: 5544
Екатеринбург
Пол: male
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #13 - 22.06.2019 :: 06:05:06
 
truf писал(а) 21.06.2019 :: 16:18:21:
оба, я надеюсь, с поддержкой XP

неа. "not valid Win32 application" и "Access is denied" Печаль
почему-то в свойствах появляется кнопка Unblock. Как у chm. но снятие блокировки ничем не помогает.
Наверх
 

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



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #14 - 27.06.2019 :: 14:34:34
 
Добавил на https://github.com/trufanov-nok/minidjvu_mod/releases/tag/perf_test еще 2 версии minidjvu - multithreaded для 64 и 32 бит.

Идеи по оптимизации у меня кончились и я решил прикрутить многопоточность. Теперь при кодировании multipage документа страницы, принадлежащие к разным Djbz словарям, кодируются параллельно в разных потоках . Это позволило Win версии почти догнать по производительности Linux версию и теперь они оба всего лишь в 2 раза медленнее documenttodjvum.exe на моих 4х ядрах.

Дистрибутивы тяжелые, т.к. собраны не при помощи MSVC. Я многопоточность прикрутил при помощи стандарта OpenMP. Компилятор Visual Studio 13-го года его, видимо, не до конца поддерживает, и на выходе многопоточность хоть и наблюдается, но совсем не такая, как ожидалось. Поэтому 64битная версия собрана в Cygwin64, а 32битную удалось собрать из него же, но через MinGW32. У них с OpenMP все как положено. Установить более свежую версию Visual Studio я не могу.
Зато, скорее всего, проблем с WinXP не будет.

Многопоточность можно регулировать новым аргументом командной строки: -t. Он задает макс число одновременно порождающихся потоков. По умолчанию оно совпадает с количеством ядер в процессоре, если их 1 или 2, и на единицу меньше количества ядер, если их больше. Т.о. на 2 ядерных машинах программа будет жрать 90-98% CPU вместо 50, на 4х ядерных - 75% вместо 25.
Наверх
« Последняя редакция: 27.06.2019 :: 15:09:56 от truf »  
 
IP записан
 
truf
Активист
***
Вне Форума



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #15 - 30.06.2019 :: 02:10:00
 
Перезалил *-multithread версии. https://github.com/trufanov-nok/minidjvu_mod/releases

Т.к. из-за OpenMP я отказался от MSVC компиллятора, то в предыдущей версии вновь всплыла проблема с сохранением временного файла в корень диска. Теперь она решена окончательно.

Обе *-multithread версии собраны MinGW, но из MSYS2, а не Cygwin
Сегодня попробовал заменить стандартный malloc на  jemalloc. На Линуксе получил неплохой прирост скорости на 10-15%, решил прикрутить его и к Win версии. Но в WIn версии ускорить получилось куда скромнее.
На линуксе сравнивал jemalloc со свежим mimalloc от MS - jemalloc чуть лучше. На винде сравнить было лень.
Наверх
 
 
IP записан
 
truf
Активист
***
Вне Форума



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #16 - 11.07.2019 :: 00:55:41
 
У кого есть XP, скажите плз, запускается ли на нем последняя версия (собранная из  MSYS2)?
Наверх
 
 
IP записан
 
AAW
Патриарх
*****
Вне Форума


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

Сообщений: 5544
Екатеринбург
Пол: male
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #17 - 11.07.2019 :: 16:19:40
 
truf писал(а) 11.07.2019 :: 00:55:41:
скажите плз, запускается ли на нем последняя версия

Попробовал запустить просто в командном окне без опций и файлов. Говорит во всплывающем окошке (отдельном) "the procedure entry point GetTickCount64 could not be located in the dinamic link library KERNEL32.dll."
Наверх
 

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



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #18 - 11.07.2019 :: 20:25:02
 
AAW писал(а) 11.07.2019 :: 16:19:40:
Попробовал запустить просто в командном окне без опций и файлов. Говорит во всплывающем окошке (отдельном) "the procedure entry point GetTickCount64 could not be located in the dinamic link library KERNEL32.dll."

Похоже MSYS2 с 2019 перестал WinXP поддерживать. Поменял libwinphread-1.dll на версию декабря 2018-го. В нем нет GetTickCount64. Перезалил minidjvu-distr-mingw32-multithread.rar тут: https://github.com/trufanov-nok/minidjvu_mod/releases/tag/perf_test
Попробуйте теперь.
Наверх
 
 
IP записан
 
AAW
Патриарх
*****
Вне Форума


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

Сообщений: 5544
Екатеринбург
Пол: male
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #19 - 12.07.2019 :: 05:19:37
 
truf писал(а) 11.07.2019 :: 20:25:02:
Попробуйте теперь.

Всплывающее сообщение в части названия функции изменилось на "...AcquireSRWLockExclusive...".
На всякий проверил версию kernel32 через Properties. Вроде родная: 5.1.2600.5512 (xpsp.080413-2111).
Наверх
 

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



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #20 - 12.07.2019 :: 06:27:34
 
AAW писал(а) 12.07.2019 :: 05:19:37:
Всплывающее сообщение в части названия функции изменилось на "...AcquireSRWLockExclusive...".

Хорошо, заменил libjemalloc.dll на старый jemalloc.dll. Перезалил minidjvu-distr-mingw32-multithread.rar. Как теперь?
Наверх
 
 
IP записан
 
AAW
Патриарх
*****
Вне Форума


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

Сообщений: 5544
Екатеринбург
Пол: male
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #21 - 12.07.2019 :: 06:43:12
 
Теперь "...InitializeConditionVariable..."
Наверх
 

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



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #22 - 12.07.2019 :: 17:34:22
 
AAW писал(а) 12.07.2019 :: 06:43:12:
Теперь "...InitializeConditionVariable..."

Ок, откатил libtiff-5.dll на версию 4.0.9-2, убрал libzstd.dll. Попробуйте 32-х битную версию на XP теперь.
Наверх
 
 
IP записан
 
AAW
Патриарх
*****
Вне Форума


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

Сообщений: 5544
Екатеринбург
Пол: male
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #23 - 12.07.2019 :: 21:38:25
 
выдал справку. этого достаточно, или нужно кодирование проверить?
Наверх
 

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



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #24 - 12.07.2019 :: 21:59:18
 
AAW писал(а) 12.07.2019 :: 21:38:25:
выдал справку. этого достаточно, или нужно кодирование проверить?

достаточно, хорошо.
Наверх
 
 
IP записан
 
truf
Активист
***
Вне Форума



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #25 - 17.07.2019 :: 17:53:30
 
Перезалил оба  Перезалил minidjvu-distr-mingw32-multithread.rar. и  minidjvu-distr-mingw64-multithread.rar.
https://github.com/trufanov-nok/minidjvu_mod/releases/tag/perf_test

  • Исправлены серьезные баги, делавшие предыдущую версию неработоспособной на Win.
  • Для 64-бит версии предприняты те же меры, что и для 32 бит, для обеспечения совместимости с XP.
  • Главное:
    модифицирован классификатор
    .

Теперь программа поддерживает аргумент -C (чувствительно к регистру), задающий 3 режима работы классификатора.

-C 1 - (по умолчанию), это то же что и было, но чуть быстрее работает.
-C 2 - после отработки штатного классификатора предпринимаются дополнительные усилия для поиска кластеров, допустимых к слиянию. Этот режим жрет сильно больше CPU и занимает дольше времени. Он ускорен кэшем, который жрет сильно больше памяти. На моей 4-х ядерной машине с 8 Gb RAM, при загрузке 3-х ядер для кодирования 320 стр. 600 dpi документа требуется 4 минуты и 1.3 Gb RAM (на Windows c HDD). Если памяти мало, то можете уменьшить число потоков до одного (-t 1), что повлечет рост времени, необходимой на обработку. Кэш веделяется на поток.
Для чего такие усилия? В этом режиме
без потери качества кодирования
, а исключительно
за счет лучшей организации словаря
достигается
на 20-30% меньший размер выходного ч.б. документа
по ср. с documenttodjvum.exe.

-C 3 - то же что и -C 2, но позволяет уменьшить словарь еще на пару килобайт за счет несколько большего расхода CPU (потребление RAM такое же). Разница между -C 3 и -С 2 не так разительна, как между -C 2 и -C1, так что выбирать советую сразу -C 3.


Итого, я поразбирался с классификаторами и пришел к выводу, что все они решают задачу плотностной кластеризации точек в пространстве высокой размерности (Density-Based Spatial Clustering). То, что в minidjvu - это некая модификация алгоритма DBRS, а то что в documenttodjvum, судя по скорости его работы, аппроксимирует ядро кластера центроидами (knn, K-means?), вместо честного пересчета расстояния до всех входящих в него точек. Что грубее minidjvu, при слиянии небольших кластеров.

И тот и другой рассчитаны на получение скорее быстрого, чем оптимального результата. Если сместить компромисс быстро/оптимально в сторону последнего и пожертвовать скоростью (что требует кэша операций, т.е. жертвуем еще и RAM), то размер выходного файла удается значительно подсократить. При этом функции сравнения изображений остаются прежними, влияющие на них параметры агрессивности не меняются. Minidjvu демонстрирует оптимизацию размера выходного файла даже в lossless (без -l) режиме. Хотя он не совсем такой уж и lossless изначально. Я отдельным длинным постом наверное распишу, что я про классификацию в DjVu думаю.

Просьба, проверить качество ч.б. документа и размер оного в режиме -C 3:
minidjvu_mod.exe -C 3 -l <input_files> <out.djvu>
Наверх
« Последняя редакция: 18.07.2019 :: 21:31:21 от truf »  
 
IP записан
 
AAW
Патриарх
*****
Вне Форума


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

Сообщений: 5544
Екатеринбург
Пол: male
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #26 - 17.07.2019 :: 20:29:28
 
truf писал(а) 17.07.2019 :: 17:53:30:
minidjvu_mod.exe -C3 -l <input_files> <out.djvu>

Улыбка проверять так проверять: как подать на вход 1000-страничный документ? это разве влезет в командную строку?
Наверх
 

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



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #27 - 17.07.2019 :: 22:09:23
 
AAW писал(а) 17.07.2019 :: 20:29:28:
это разве влезет в командную строку?

влезет   Подмигивание
Наверх
 
 
IP записан
 
AAW
Патриарх
*****
Вне Форума


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

Сообщений: 5544
Екатеринбург
Пол: male
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #28 - 18.07.2019 :: 18:50:58
 
странно. говорит что не знает опции "C3". Файл от 20:08 17го числа.
Наверх
 

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



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #29 - 18.07.2019 :: 21:30:50
 
AAW писал(а) 18.07.2019 :: 18:50:58:
странно. говорит что не знает опции "C3". Файл от 20:08 17го числа.

Сори, я опечатался. 3 через пробел. "minidjvu_mod.exe -C 3 -l "
Наверх
 
 
IP записан
 
truf
Активист
***
Вне Форума



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #30 - 01.08.2019 :: 18:19:35
 
Я обновил файлы  *-multithread.rar
https://github.com/trufanov-nok/minidjvu_mod/releases/tag/perf_test

Благодаря AAW найдены и исправлены несколько ошибок при кодировании. Ускорена работа режима -C 3
Наверх
 
 
IP записан
 
truf
Активист
***
Вне Форума



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #31 - 15.08.2019 :: 23:05:07
 
Еще раз обновил файлы  *-multithread.rar
https://github.com/trufanov-nok/minidjvu_mod/releases/tag/perf_test

Исправлен серьезный баг.

Теперь у minidjvu_mod будут версии в форме AAmBB, где AA - версия модифицированного minidjvu, а BB - версия модификации. На практке это будут 0.9m1, 0.9m2 и т.д.

Также добавил 2 архива с GUI к утилите (аналог minidjvu Plus), написанном на Qt. Они для 64 и 32 бит, но 32-х битный на XP может не заработать,т.к. собран со слишком свежим Qt.
GUI архивы идут уже с minidjvu_mod внутри.
Наверх
 
 
IP записан
 
truf
Активист
***
Вне Форума



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #32 - 26.03.2020 :: 21:44:56
 
Я хотел, но видимо забыл, оставить здесь ссылку на обсуждение minidjvu_mod на странице проекта DjVuLibre (на английском).

Вот она: https://sourceforge.net/p/djvu/discussion/103286/thread/1b0de7aa93

Но т.к. я давно minidjvu_mod не занимался, то и новостей ни там ни тут никаких нет. Я скорее всего сперва (когда-нибудь) затолкаю поддержку сборки bundled DjVu в STU, а потом уже буду на практике полировать кодировщик.
Наверх
 
 
IP записан
 
truf
Активист
***
Вне Форума



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #33 - 08.07.2021 :: 19:13:35
 
Я выпустил новый релиз minidjvu-mod - 9m02: https://github.com/trufanov-nok/minidjvu-mod/releases/tag/0.9m02

В программу добавлены некоторые ключи, обновлена справка и русская локализация (для Линукса).
Из главного - ключ -S, который позволяет все настройки кодирования документа передавать через файл настроек. У этого файла специфичный формат, похожий на формат установки outlines через djvused из пакета DjvuLibre. С его помощью можно:

- задать персональные настройки кодирования для определенного изображения
- контролировать, какие изображения пойдут в какой общий словарь djbz
- задать персональные настройки для определенного общего словаря djbz

Формат описан в wiki проекта на eng и rus. Но, он составлен из предположения, что пользователь не будет набирать руками, а его составит за него некая программа. В частности этот файл будет генерировать ScanTailor ver. 0.3. Собственно, под него все эти фишки и заточены.

Кроме того, minidjvu-mod ver. 9m02 наконец собран (32 и 64 bit) при помощи Visual Studio 2013, а не MinGW.
Возможно, он даже поддерживает Windows XP - но это стоит проверить. По кр. мере везде где мог я эту настройку выставлял.


Вместе с minidjvu-mod обновлен minidjvu-mod-gui - простенький GUI для него:
https://github.com/trufanov-nok/minidjvu-mod-gui/releases/tag/0.2.2

Он пересобран с Qt 5.7 (32 и 64 bit), и в нем тоже должна быть поддержка Windows XP. В zip архивах GUI для Windows также положен minidjvu-mod в подпапочку bin. GUI должен автоматически его там видеть.
Но, никаких дополнений в плане функционала к нему не сделано, поэтому создавать файлы настроек он не умеет.

Хочу написать новость о релизе на ЛОР, поэтому прошу потестировать.
Наверх
 
 
IP записан
 
truf
Активист
***
Вне Форума



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #34 - 14.07.2021 :: 15:33:10
 
В качестве исторический справки скопирую сюда ответ Ильи Межирова, касательно создания minidjvu:

Цитата:
Историю разработки расскажу, почему бы и нет.

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

В djvulibre вместо сравнивателя буковок была по сути заглушка из-за того, что автор подписался LizardTech'у, что не будет делать эту часть нормально. Поэтому не улучшить djvulibre было просто невозможно. Идея простая: заглушка попросту подсчитывает различающиеся пиксели, но ясно, что различия около границ букв должны настораживать намного меньше, чем различия внутри, поэтому надо брать не простую, а взвешенную сумму. В обработке изображений я тогда ничего не понимал, поэтому нахождение границ букв усиленно написал сам, вместо того, чтобы взять готовое. Также я не понимал, что калибровать параметры надо на большой базе вроде тренировочных данных Тессеракта - minidjvu откалиброван на глаз по результатам сжатия одной конкретной страницы. Потом мне показали другую страницу, в которой minidjvu смешивал "и" и "н", и я немного подкрутил параметры в сторону осторожности.

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

Потом подключился Алексей Крюков и стал все это приводить в более человеческий вид, добавил локализацию и разные улучшения, за что ему большое спасибо. minidjvu 0.8 уже выпустил он.

Вот и вся история.


И частично цитату Leon Bottou:
Цитата:
<...> This is not so easy because one needs to cleanly extract the pattern matching code and reuse the djvulibre bit encoding code. In fact Ilya Mezhirov already did that for an earlier version of minidjvu, and his code can be found in djvulibre-3.5/tools/jb2cmp. <...>


В общем, как я и предполагал, алгоритмы составления локальных Sjb2 словарей в DjVuLibre перекочевали из minidjvu.
Наверх
 
 
IP записан
 
truf
Активист
***
Вне Форума



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #35 - 29.07.2021 :: 15:35:21
 
Поправил баги, обновил до 0.9m03: https://github.com/trufanov-nok/minidjvu-mod/releases/tag/0.9m03
Наверх
 
 
IP записан
 
truf
Активист
***
Вне Форума



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #36 - 07.09.2021 :: 22:24:07
 
Вышел minidjvu-mod 0.9m05
И GUI к нему ver 0.2.3

Это большое обновление в котором поправлены некоторые баги кодирования и заменен классификатор.
Мне прислали набор 300dpi сканов, с которыми minidjvu-mod 0.9m03 не справлялся - ошибки классификации [il1]. В попытке их устранения было принято решение отказаться от 3-х классификаторов и заменить их одним общим и более пессимистичным. Так что теперь опции -C нет, а minidjvu-mod нацелен скорее на повторение результатов documenttodjvu.exe,чем на их превосхождение. В общем, решено сосредоточится на надежности и точности.

Пессимистичный классификатор быстро принимает решение о различии классов, посему резко упало кол-во сравнений, а значит выросла скорость. В итоге я смог отказаться от кэша, а значит потребление RAM теперь сравнимо с documenttodjvu.exe. Скорость тоже сравнима. Параметры классификации подогнаны так, чтобы с дефолтной агрессией быть чуть лучше результатов documenttodjvu.exe.

В итоге, minidjvu-mod стал гораздо сильнее походить на documenttodjvu.exe по всем параметрам.

К сожалению, есть не все проблемы выявленные на присланных мне сканах удалось исрправить ценой увеличение вменяемого % размера документа. В частности есть пара символов, напечатанных жирным, которые minidjvu-mod путает с нежирными аналогами. Разница в площади там всего 4% и их даже на глаз без контекста тяжело отличать. Но documenttodjvu.exe это умеет. Т.е. есть куда расти.

В общем версия 0.9m05 существенно отличается от предыдущих и требует тщательного тестирования. Сборки доступны подо всё.

https://github.com/trufanov-nok/minidjvu-mod/releases/tag/0.9m05
https://github.com/trufanov-nok/minidjvu-mod-gui/releases/tag/0.2.3
Наверх
 
 
IP записан
 
truf
Активист
***
Вне Форума



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #37 - 08.09.2021 :: 21:24:17
 
И еще раз обновил бинарник без изменения версии - закрыт баг с утратой примыкающих к правому краю изображения рамок после smooth.
Наверх
 
 
IP записан
 
Dimitriy89
Новичок
*
Вне Форума


Всем привет!

Сообщений: 19
Пол: male
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #38 - 11.09.2021 :: 12:07:23
 
Спасибо за труды. Есть планы сделать/переделать такие вещи как DjvuSmall с этим кодером?
Наверх
 
 
IP записан
 
truf
Активист
***
Вне Форума



Сообщений: 254
Re: Свободные кодеры DjVu не хуже коммерческих? Неигрушечный minidjvu
Ответ #39 - 11.09.2021 :: 14:54:55
 
Dimitriy89 писал(а) 11.09.2021 :: 12:07:23:
Спасибо за труды. Есть планы сделать/переделать такие вещи как DjvuSmall с этим кодером?


Нет. DjVu Small использует коммерческий documenttodjvu.exe. Тот умеет кодировать не только ч/б, но и цветные изображения. Т.е. имеет встроенный сегментатор, который как-то отделяет текст от изображений. Текст и изображения кодируются в DjVu по-рузному. Minidjvu-mod умеет кодировать только текст, т.е. только монохромные изображения. Поэтому в тупую заменить documenttodjvu.exe на minidjvu-mod нельзя.
Сегментатор создать можно, и скорее всего это не сложно. Судя по тому, как documenttodjvu.exe кодирует текст поверх изображений - там какой-то тупой порог на оттенки черного просто выделяется. Но пока таких планов нет.

Но, minidjvu-mod может использоваться как кодировщик в "методе раздельных сканов". Где сканы предварительно кто-то разделил на текст и изображения, отдельно то и то закодировал, а потом собрал DjVu Imager'ом. Таким "кто-то" могут быть сейчас форки ScanTailor с поддержкой экспорта слоев изображений. И вот что я планирую, и почти сделал - так это засунуть minidjvu-mod в ScanTailor Universal, и фактически засунуть ему под капот генерацию djvu документов по методу раздельных сканов. Текущие исходники лежат в ветке djvu3.
Наверх
 
 
IP записан
 
Страниц: 1 
Послать Тему Печать