Для того чтобы найти раскраску с максимальным выигрышем, используются два прохода по дереву. Во время первого прохода — от листьев к корню — для каждой вершины ищется максимально возможный выигрыш от ее поддерева (включая ее саму) при условии, что ее родитель белый; и то же самое при условии, если ее родитель черный. Чтобы найти каждую из этих величин, разбираются два случая: вершина белая или вершина черная; наибольшим выигрыш в этих двух случаях даст искомую величину. Если и цвет родителя, и цвет самой вершины известен, то максимальный выигрыш в ее поддереве равен ее вкладу в выигрыш плюс сумма по всем потомкам выигрыша на их поддеревьях при известном цвете их родителя.
Во время второго прохода — от корня к листьям — по найденным величинам для каждой вершины проставляются окончательные цвета при известном цвете родителя так, чтобы выигрыш от поддерева каждой вершины была наибольшим.
Алгоритм для устранения мусора — часть, требующая наибольшей ручной настройки. Максимальный уровень яркости будем считать равным 255. В программе принято следующее правило: контур считается подозрительным, если он затемняющий и его уровень (как линии уровня) меньше 156 или если он осветляющий и его уровень больше 100; подозрительный контур считается мусором, если его резкость меньше 10000 или отношение его резкости к его длине меньше 100.
Время работы всего алгоритма пропорционально числу пикселей; время работы второй части, раскраски дерева, пропорционально числу контуров. На практике программа работает быстро, как ни странно, даже быстрее, чем pgmtopbm -threshold.
Ссылки
[1] Сайт DjVuLibre: http://djvu.sourceforge.net
С него можно скачать архиватор и программу для просмотра DjVu под Unix с исходным кодом.
[2] Сайте DjVuZone: http: //www. djvuzone. org Разные ресурсы, посвященные DjVu.
[3] Сервер Any2DjVu: http://ciny2djvu.djvuzone.org
Сжимает присланные на него изображения с качеством коммерческих программ.
[4] Сайт фирмы LizardTech: http://www.lizardtech.com
С него можно скачать plug-in к InternetExplorer'y для Windows. Последняя версия на момент написания этой ссылки занимает 7,5 Мб.
[5] Plug-in на МЦНМО: http://www.mccme.ru/free-books/4djvu/djvuwebbrowserplugin_en.exe Сервер МЦНМО хранит старую версию того же plug-in'a для Windows, занимающую 1,7 Мб.
[6] Статьи, выложенные фирмой LizardTech (в том числе все нижеперечисленное) можно скачать отсюда: http://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; полнаяверсияпоадресу http://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.