Тут длинно. Если в кратце, я начал сомневаться, что 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 умеет кодировать 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 документа по сути заключается в следующем:



Теперь лезем в код 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.

+0.81%

.

-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 я продолжу писать в этой ветке.

truf, спасибо!

truf писал(а) 16.06.2019 :: 20:51:05:

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

AAW

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

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

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

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

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

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

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

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

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

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

Кстати, разглядывая кодеки 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

AAW писал(а) 18.06.2019 :: 05:23:45:

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

truf писал(а) 17.06.2019 :: 22:43:23:


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

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.

truf писал(а) 16.06.2019 :: 23:37:25:


Я обновил сборки по этой ссылке 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 - это то же самое, но с различными выкрутасами, призванными компенсировать падение скорости составления словаря.

Добавил на 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.

У кого есть XP, скажите плз, запускается ли на нем последняя версия (собранная из  MSYS2)?

AAW писал(а) 11.07.2019 :: 16:19:40:

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

AAW писал(а) 12.07.2019 :: 05:19:37:

Хорошо, заменил libjemalloc.dll на старый jemalloc.dll. Перезалил minidjvu-distr-mingw32-multithread.rar. Как теперь?

AAW писал(а) 12.07.2019 :: 06:43:12:

Ок, откатил libtiff-5.dll на версию 4.0.9-2, убрал libzstd.dll. Попробуйте 32-х битную версию на XP теперь.

AAW писал(а) 12.07.2019 :: 21:38:25:

достаточно, хорошо.

truf писал(а) 17.07.2019 :: 17:53:30:

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

странно. говорит что не знает опции "C3". Файл от 20:08 17го числа.