DjVu - все уже было

Архив

Рассказ о новом "тексто-графическом" формате я начну с воспоминаний о теплом летнем дне, когда выпускники художественного училища рисовали на асфальте "дембельский альбом". Больше всего меня поразила удивительно точная репродукция картины "Бурлаки на Волге". Изобразить такое цветными мелками - это отдельное искусство. Увы, я не сделал копии того рисунка и теперь только на словах могу объяснить, как велико влияние техники живописи на восприятие картины. Ну, например, нарисовать "Джоконду" акварелью - все равно что сыграть "Мурку" на арфе. Мы редко задумываемся над этим, когда дело касается репродукций виртуальных: BMP, JPG, TIFF... графические форматы если и интересуют неспециалистов, то только с точки зрения размеров файла.

С текстовой информацией ситуация совсем запущенна: прекрасно понимая разницу между словом рукописным и напечатанным, мы почти не публикуем в Сети первоисточников в их реальном формате [1]. Мировые музеи и библиотеки уже оцифровали все сколько-нибудь ценные рукописи, однако размеры полученных файлов не позволяют ознакомиться с ними через Internet.

Сжатие полноцветной информации о документе формата А4 до размера средней Web-странички (46 Кбайт согласно данным на 1999 г.) теоретически вполне возможно. Учитывая растущую общественную потребность [2] в доступе к "подлинникам", кажется удивительным, что стандарт на графику такого назначения формируется только сегодня.

Претенденты на роль законодателей нового формата уже появились. Успехи фирмы AT&T в этом направлении может оценить каждый, установив plug-in для браузера (www.djvu.att.com/download.html) и посетив виртуальный архив манускриптов (dejavu.research.att.com/links, krasnodar.online.ru/hamradio/sch.htm, русские ресурсы) в новом "тексто-графическом" формате DjVu.

Формат DjVu [3] - первый шаг к "цветному факсу" - ориентирован на передачу, просмотр в сети и распечатку преимущественно текстовых документов, для которых важное значение имеет не только содержание, но и форма: цвет и фактура пергамента, оторванный уголок и следы от складывания вчетверо, клякса после подписи и круглое пятно от винной бутылки рядом с печатью. Архивы всего мира накопили огромное число исторических бумаг с неповторимым колоритом такого рода.

Существующие компактные форматы JPG, GIF, факс-стандарт CCITT и JBIG обеспечивают достаточное сжатие, однако узко специализированны либо на фотографиях, либо на черно-белой графике и тексте. Поэтому смешанные изображения в их исполнении выглядят нечитаемыми. Хороший тому пример - JPG-скриншоты на сайтах софтверных фирм: либо текст не разберешь, либо грузятся по полчаса. Разработчики DjVu, должно быть, учли безуспешный опыт создания "универсального солдата", их детище представляет собой бригаду из трех форматов "в одном флаконе". В основу разделения "обязанностей" внутри DjVu положены простые наблюдения и факты.

- Текст и другие контрастные рисунки удобочитаемы при сканировании с разрешением не менее 300 dpi.

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

Параметры компонентов изображения в формате DjVu.

Имя слоя	Пояснение	Разрешение, dpi	Глубина цвета, bits/pix
Mask	монохромная маска-трафарет	300	1
Background	цветной фон	100	24
Foreground	цвета маски	25	24

- Основная проблема - отделить текст от фона, особенно если это цветной текст, и более того, разноцветный. К счастью, цвет текста в большинстве документов практически одинаков в рамках одного знака. Это позволяет сохранять цветовую информацию о тексте с разрешением всего 25 dpi (слой "foreground") (см. табл.).

Разделение изображения на текст и фон (формирование слоя-маски) основано на так называемой мультимасштабной кластеризации. Изображение разбивается на разноразмерные вложенные сетки, в каждой ячейке которых происходит распознавание текстовых и фоновых цветов по максимальным пикам на гистограмме. Отделив текст от фона в самой крупной сетке, алгоритм переходит к уточнению на основе данных из сеток меньшего размера. Разработчиками найдено эмпирическое соотношение: цвет, определенный как "текстовый" в наибольшей ячейке, смешивается с "текстовым" цветом в меньшей, вложенной ячейке в пропорции 20% к 80% [4]. Результат смешения принимается за цвет текста для расчетов в еще более мелкой сетке по тому же принципу 20/80.

Очевидно, смешение одинаковых цветов даст тот же самый цвет. В этом случае вложенные ячейки игнорируются, и общий объем информации о слое-маске уменьшается на 10...30% по сравнению с разбиением одноразмерной сеткой наименьшего шага.

Мультимасштабная кластеризация не всегда дает ожидаемые результаты (рис. 1). При переводе некоторых документов (например, обложка "Компьютерры" #331, www.computerra.ru/2000/2) в формат DjVu даже человеку порой непонятно, что является значимой информацией, а что - фоном. Программные конвертеры (я пользовался DjVuerPro [5], www.feith.com) предоставляют возможность выбора параметров границы фон-текст. Как правило, это фильтры размера, цвета и инверсии. Фильтр размера позволяет отнести к фону слишком большие буквы (аршинный заголовок и т. п.). Действие двух других фильтров не столь очевидно - их функция в чем-то схожа с системами OCR (оптического распознавания текста).

Мне представляется такая некомпьютерная аналогия формата DjVu, в виде набора инструментов художника-агитатора: баллончики с красками для быстрого и грубоватого "подмалева" фона (например, небо и радуга) - слой "background"; аккуратный трафарет для основного лозунга (или логотипа) - слой-маска "blaсk&white", и поролоновый валик для накатки трафарета - слой "foreground".

Используя эту аналогию, легко понять еще один принцип экономии битов в DjVu: если трафаретный текст занимает значительную площадь изображения, следует ли сначала вырисовывать фон в тех местах, которые позже будут все равно закрашены по трафарету? Даже для живого художника это вопрос эвристической логики, если учитывать не только расход красок, но и время выполнения работы.

В DjVu для сжатия фона, маски и цветовой информации о маске применяются различные алгоритмы. Фон сжимается вейвлет-алгоритмом IW44 (4х4 wavelets), слой-маска, не содержащая цветовой информации, упаковывается методом JB2, аналогичным применяемому в факсах. Цветовая информация о тексте так же кодируется IW44, но предварительно загрубляется до 25 dpi.

Формат IW44 очень близок к новому стандарту JPEG2000 ("КТ" #331, стр. 7), но, по заверениям разработчиков, менее требователен к системным ресурсам при декомпрессии изображения во время просмотра. Попробуйте открыть в любом графическом редакторе какой-нибудь стандартный JPG размером 2500х3500 точек, и вы оцените важность этого преимущества.

Слой-маска перед упаковкой JB2 претерпевает оптимизацию с целью освобождения от "случайных" штрихов и "шума сканера" на основе так называемого Soft pattern matching algorithm, описываемого непереводимым для меня бытовым английским в манере стихов В. Маяковского:

Segment image into marks
for each mark do
Find "acceptable match", if any
if there is a match
Code index of matching mark
Code bitmap using matching mark
Conditionally add new mark to library
else
Code bitmap directly
Add new mark to library
end if
Code mark location as offset
end for

В результате каждый пиксел маски кодируется менее чем одним (!) битом, но только в том случае, если алгоритм способен предсказать его цвет на основе 3...8 рядом лежащих точек с вероятностью более 50%. Это не так сложно - каждый из нас производит подобные расчеты в виндусовской игре "Сапер".


Описание DjVu в более научных терминах вы можете найти на страницах разработчиков: (dejavu.research.att.com/djvu/sci/djvuspec), откуда я позаимствовал рисунок 2.

У нового формата много применений: онлайновые книжные магазины, картографическая информация и даже е-хиромантия, где отправленная по почте фотография ладони обрабатывается подобным образом.

Переход к DjVu с его четким текстом, по мнению экспертов, начнется с сайтов СМИ, копирующих свои бумажные издания. Освойте новинку сегодня, возможно, завтра она потребуется, чтобы прочитать "Компьютерру On-line".

---

1 (обратно к тексту) - Согласитесь, известное слово, нацарапанное в лифте гвоздиком, приобретет иную весомость, если высветится на LCD-панели указателя этажей.

2 (обратно к тексту) - Особенно перед выборами.

3 (обратно к тексту) - Произносится [дежавю], с французским прононсом.

4 (обратно к тексту) - Закон Парето - буквально повсюду. - Г.Б.

5 (обратно к тексту) - Дистрибутив занимает всего 2 Мбайт, а вот лицензия стоит уже 750 зеленых.