Алгоритм JB2 умеет сжимать только монохромные (черно-белые, без промежуточных серых цветов) изображения. Файлы формата DjVu могут содержать и изображения в тонах серого, и цветные рисунки, но все равно в таком файле отдельно хранится монохромный рисунок, а отдельно добавочная информация о цвете. Поэтому чтобы сжать в таком виде любое изображение, содержащее текст, необходимо, сначала выделить из него монохромное.
Самый простой способ для этого — объявить все пиксели темнее половины белого черными, а остальные — белыми. Под Linux это выполняется командой pgmtopbm -threshold, а под Windows эту операцию выполняет стандартный редактор Paint, когда сохраняет цветные картинки как монохромные.
Этот способ хорошо работает только тогда, когда изображение уже похоже на монохромное. Однако, если в нем есть слишком бледные буквы или затемненные поля, то в результате одни контуры могут пропасть, а другие — появиться. Чтобы справляться с такими случаями, нужен алгоритм, который обращает больше внимания на резкость границ и правильность линий, чем на абсолютную величину цвета.
Предлагаемый алгоритм — шаг в этом направлении: он стремится выделить наиболее резкие контуры; при этом в качестве побочного эффекта удаляются черные поля вокруг отсканированного листа и между страницами книги.
Итак, сначала в изображении выделяются контуры — связные компоненты линий уровня (яркости), у которых уровень кратен заранее выбранной величине. В программе эта величина составляет одну четверть полного расстояния между белым и черным. При этом мы будем считать, что эта яркость проходит между уровнями пикселей, и таким образом, контур проходит между пикселями, а не через них. Топологически каждый контур эквивалентен окружности, и у него есть бесконечная внешняя и конечная внутренняя часть. Контур может быть осветляющим (внутри ярче) и затемняющим (внутри темнее).
Для каждого контура подсчитывается «резкость» — величина, равная по определению модулю суммы перепадов яркости по всем ребрам контура (ребро — это часть контура, проходящая между двумя пикселями). Перепад яркости у ребра равен разности яркости того пикселя, который внутри контура, и того, который снаружи. При этом для контуров, проходящих по краю всего изображения, будем считать пиксели, лежащие вне этого края абсолютно черными. При сканировании у краев рисунка обычно возникают черные поля; такое решение искусственно делает внешние контуры этих полей осветляющими и уменьшает их резкость.
Контуры могут быть вложены друг в друга (точнее, один во внутренность другого). Будем считать, что есть фиктивный контур, проходящий по краю изображения, в который вложены все остальные. Тогда контуры образуют ориентированное дерево по вложенности, и фиктивный контур — его корень.
Раскрасим контуры в черный и белый цвета так, чтобы максимизировать описанную ниже функцию. При этом каждый пиксель получит тот цвет, который имеет самый внутренний из содержащих его контуров.
Построим функцию выигрыша от раскраски дерева контуров, которую надо устремить к максимуму. При этом можно запретить некоторые раскраски, присвоив им специальное значение «минус бесконечность».
Положим выигрыш равным сумме по всем контурам следующей величины. Фиктивный корневой контур должен быть белым (этим и достигается удаление полей); таким образом, черный корневой контур запрещен. Контур, имеющий тот же цвет, что и родитель, дает нулевой вклад в выигрыш. В следующих случаях контуру запрещено иметь цвет, отличный от цвета родителя: если отдельный алгоритм для фильтрования ненужных контуров признал его мусором; если контур осветляющий, а родитель белый; или если контур затемняющий, а родитель черный. Если же родитель затемняющего контура белый, а сам контур черный, или родитель осветляющего контура черный, а сам контур белый, то его вклад в выигрыш равен резкости.
Для того чтобы найти раскраску с максимальным выигрышем, используются два прохода по дереву. Во время первого прохода — от листьев к корню — для каждой вершины ищется максимально возможный выигрыш от ее поддерева (включая ее саму) при условии, что ее родитель белый; и то же самое при условии, если ее родитель черный. Чтобы найти каждую из этих величин, разбираются два случая: вершина белая или вершина черная; наибольшим выигрыш в этих двух случаях даст искомую величину. Если и цвет родителя, и цвет самой вершины известен, то максимальный выигрыш в ее поддереве равен ее вкладу в выигрыш плюс сумма по всем потомкам выигрыша на их поддеревьях при известном цвете их родителя.
Во время второго прохода — от корня к листьям — по найденным величинам для каждой вершины проставляются окончательные цвета при известном цвете родителя так, чтобы выигрыш от поддерева каждой вершины была наибольшим.
Алгоритм для устранения мусора — часть, требующая наибольшей ручной настройки. Максимальный уровень яркости будем считать равным 255. В программе принято следующее правило: контур считается подозрительным, если он затемняющий и его уровень (как линии уровня) меньше 156 или если он осветляющий и его уровень больше 100; подозрительный контур считается мусором, если его резкость меньше 10000 или отношение его резкости к его длине меньше 100.
Время работы всего алгоритма пропорционально числу пикселей; время работы второй части, раскраски дерева, пропорционально числу контуров. На практике программа работает быстро, как ни странно, даже быстрее, чем pgmtopbm -threshold.
Ссылки
[1] Сайт DjVuLibre: https://djvu.sourceforge.net
С него можно скачать архиватор и программу для просмотра DjVu под Unix с исходным кодом.
[2] Сайте DjVuZone: http: //www. dj vuzone. org Разные ресурсы, посвященные DjVu.
[3] Сервер Any2DjVu: https://ciny2djvu.djvuzone.org
Сжимает присланные на него изображения с качеством коммерческих программ.
[4] Сайт фирмы LizardTech: https://www.lizardtech.com
С него можно скачать plug-in к Internet Explorer'y для Windows. Последняя версия на момент написания этой ссылки занимает 7,5 Мб.
[5] Plug-in на МЦНМО: https://www.mccme.ru/free-books/4djvu/djvuwebbrowserplugin_en.exe Сервер МЦНМО хранит старую версию того же plug-in'a для Windows, занимающую 1,7 Мб.
[6] Статьи, выложенные фирмой LizardTech (в том числе все нижеперечисленное) можно скачать отсюда: https://www.lizardtech.com/solutions/doc/doc_techpapers.php
[7] Artem Mikheev, Luc Vincent, Mike Hawrylycz, Leon Bottou. Electronic Document Publishing using DjVu. Proceedings DAS'02, Fifth IAPR International Workshop on Document Analysis Systems, Princeton, NJ, August 2002.
[8] Patrick Haffher, Leon Bottou, Yann LeCun, Luc Vincent, A General Segmentation Scheme for DjVu Document Compression. Proceedings ISMM'02, International Symposium on Mathematical Morphology, Sydney, Australia, April 2002.
[9] Leon Bottou, Patrick Haffner, Yann LeCun, Efficient Compression of Digital Documents to Multilayer Raster Formats. Proceedings ICDAR'Ol, International Conference on Document Analysis and Recognition, Seattle, WA, September 2001.
[10] Yann LeCun, Leon Bottou, Patrick Haffner, Jeffery Triggs, Luc Vincent, Bill Riemers, Overview of the DjVu Document Compression Technology. Proceedings SDIUT'Ol, Symposium on Document Understanding Technologies, pp.119-122, Columbia, MD, April 2001.
[11] Yann LeCun, Leon Bottou, Andrei Erofeev, Patrick Haffner, Bill Riemers, DjVu Document Browsing with On-Demand Loading and Rendering of Image Components. Proceedings of SPIE's Internet Imaging II, San Jose, CA, February 2001.
[12] Leon Bottou, Patrick Haffner, Yann Le Cun, Paul Howard, Pascal Vincent, DjVu: Un Systeme de Compression d'Images pour la Distribution Reticulaire de Documents Numerises. Actes de la Conference Internationale Francophone sur l'Ecrit et le Document, Lyon, France, July 2000.
[13] Patrick Haffner, Yann Le Cun, Leon Bottou, Paul Howard, Pascal Vincent. Color Documents on the Web with DjVu. Proceedings of the International Conference on Image Processing, Vol. 1, pp. 239-243, Kobe, Japan, October 1999.
[14] Patrick Haffner, Leon Bottou, Paul Howard, Yann Le Cun. DjVu: Analyzing and Compressing Scanned Documents for Internet Distribution. Proceedings ICDAR'99, International Conference on Document Analysis and Recognition, pp. 625-628, 1999.
[15] Yann Le Cun, Leon Bottou, Patrick Haffner, Paul Howard, DjVu: a Compression Method for Distributing Scanned Documents in Color over the Internet, Color 6, 1ST, 1998.
[16] Leon Bottou, Patrick Haffner, Paul Howard, Patrice Simard, Yoshua Bengio, Yann Le Cun, Browsing Through High Quality Document Images with DjVu. Proceedings of IEEE Advances in Digital Libraries'98, IEEE, 1998.
[17] Leon Bottou, Patrick Haffner, Paul Howard, Patrice Simard, Yoshua Bengio, Yann Le Cun, High Quality Document Image Compression with DjVu. Journal of Electronic Imaging, Vol. 7, No. 3, pp. 410-425, SPIE, 1988.
[18] Leon Bottou, Steven Pigeon, Lossy Compression of Partially Masked Still Images. Аннотация в Proceedings of IEEE Data Compression Conference DCC'98, pp. 528-537, Snowbird, March 1998; полная версия по адресу https://www.lizardtech.com/solutions/doc/techpapers/1998_lossy_masked.dj vu
[19] Leon Bottou, Paul Howard, Yoshua Bengio, The Z-Coder Adaptive Binary Coder. Proceedings of IEEE Data Compression Conference DCC'98, pages 13-22, Snowbird, March 1998.