Software & Systems

С развитием Интернет-технологий и удешевлением стоимости хранения электронной информации, возрастает актуальность создания и развития электронных библиотек. Электронные библиотеки стали уже привычным явлением в нашей жизни и содержат широчайший спектр научно-технической и гуманитарной информации. В цифровом виде сейчас хранится громадное количество различных публикаций и изданий: журналы, диссертации, технические отчеты, материалы конференций и многое другое. Растет и количество книг, которые теперь, кроме традиционной бумажной версии, имеют и электронный вариант. Распространена технология publish-on-demand, в которой пользователь имеет возможность на месте получить печатную копию книги.

Существует достаточно большое количество форматов электронных документов и программных средств, обеспечивающих широкие возможности по их взаимной конвертации, например PDF, PostScript, TeX, HTML.

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

Получается, что для того, чтобы создать цифровую копию возможно более близкой по содержанию и оформлению бумажному оригиналу, приходится хранить отсканированную с высоким разрешением цифровую копию в одном из растровых форматов – gif, tiff или jpeg. Но ни один из подобных форматов не содержит всей совокупности качеств, требующихся для хранения документов в электронных библиотеках. Кроме того, возникает проблема контекстного поиска в таких документах и защита их от копирования и тиражирования.

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

Формат DjVu (Digital View – цифровой вид, или цифровая фотография) – технология сжатия изображений с потерями, разработанная специально для хранения сканированных документов (книг, журналов, рукописей и пр.), где обилие формул, схем, рисунков и рукописных символов делает чрезвычайно трудоемким их полноценное распознавание. Этот формат также является эффективным решением при передаче всех нюансов оформления, например, исторических документов, где важное значение имеет не только содержание, а цвет и фактура бумаги, дефекты пергамента (трещинки, следы от складывания, исправления, кляксы, отпечатки пальцев, следы, оставленные другими предметами).

Формат оптимизирован для передачи по сети таким образом, что страницу можно просматривать еще до завершения скачивания. DjVu-файл может содержать текстовый (OCR) слой, что позволяет осуществлять полнотекстовый поиск по файлу. Кроме того, DjVu-файл может содержать встроенное интерактивное оглавление и активные области – ссылки, реализуя удобную навигацию в DjVu-книгах.

Формат DjVu был разработан фирмой AT&T, которая в дальнейшем продала технологию компании LizardTech, но сама спецификация формата открыта для создания и просмотра документов DjVu; существует свободно распространяемое на условиях GPL программное обеспечение, доступное для различных платформ.

В основе формата DjVu лежит несколько технологий, разработанных в AT&T Labs: алгоритм отделения текста от фона на отсканированном изображении; вейвлетный алгоритм сжатия фона IW44; алгоритм сжатия черно-белых изображений JB2; универсальный алгоритм сжатия ZP; алгоритм распаковки по запросу и алгоритм маскировки изображений.

Формат DjVu предусматривает возможность наличия текстового слоя, который может содержать текст страницы.

Используя эти идеи, попробуем построить дальнейшее развитие технологий, заложенных в формате DjVu.

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

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

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

На первом этапе буквы выделяем в отдельные элементы графики. Это достаточно простая процедура может быть сделана стандартными методами [1].

Следующий этап – выделение контуров в полученных буквах. Эту задачу можно решать, например, использованием метода маркированных квадратов [2].

Далее предполагаем, что все контуры начинаются с самой левой и верхней точки и обходятся по часовой стрелке. Тогда можно считать, что каждый контур есть параметрическая функция:

, (1)

где m – число точек в контуре.

Однако прямое использование такого представления не очень удобно. Полученные контуры могут быть представлены в виде кодов Фрима- на [3], являющихся, по сути, первой производной по контуру, или нормалью к контуру:

. (2)

Таким образом решается проблема представления объектов инвариантно по отношению к сдвигу.

Далее строится вектор признаков для каждого контура. Как известно, компоненты вектора признаков должны быть ортогональны, поэтому используем Фурье-преобразование [4].

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

, (3)

коэффициенты , i=0,1…, то есть

(4)

где

В качестве вектора признаков объекта рассмотрим конечный набор коэффициентов bk для функций x(t) и y(t). Поскольку f(t) полагается кусочно-линейной, то есть , , , причем

, , (5)

то

с учетом предыдущего и того, что , имеем

. (6)

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

Все операции повторяют для каждого выделенного из объекта контура и используют количество контуров в объекте как дополнительный элемент вектора признаков.

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

В качестве аппарата кластеризации используется адаптивная модель вычисления оценок [5].

Пусть есть конечное множество K классов графических объектов. Каждый класс целиком описывается своим характеристическим вектором признаков , где n – размерность вектора признаков, одинаковая для всех классов (). Без нарушения общности предполагаем, что для всех j и k.

Алгоритм вычисления оценок сравнивает описание кластеризуемого объекта с и формирует расстояние между образцом и текущим классом объектов. Расстояние вычисляется на основе степени сходства кластеризуемого объекта с характеристическими векторами классов .

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

. (7)

Величины входят как параметры в модель класса алгоритмов, а соотношение (7) суть решающее правило, на основании которого принимается решение о принадлежности w к клас- су .

Принятие решения о кластеризации может быть формализовано различными способами. В частности, можно считать, что объект , если неравенство (7) выполняется для всех . В этом случае считается, что имеет место отказ в кластеризации, если указанный критерий не выполняется ни для одного k из множества классов K. Отказов не будет, если в качестве критерия для отнесения объекта выбирается минимальное число индексов s, для которых нарушается неравенство (7). Очевидно, что при любом из указанных решающих правил возможна ситуация, когда объект оказывается принадлежащим сразу нескольким (или всем) классам Uk.

После процедуры кластеризации внутри класса мы можем провести статистическую обработку объектов, например, простым усреднением по компонентам bk. Результат такого усреднения рассмотрим в качестве процедуры построения элемента внутреннего адаптивного шрифта электронного документа.

Следует отметить, что хотя все предложенное основано на технологиях оптического распознавания текста, сама задача распознавания напрямую не решается. Элементы приближенного распознавания используются только в системе контекстного поиска внутри графического документа.

После получения типичного представителя класса можно восстановить вид графического объекта путем обратного Фурье-преобразования. Причем точность восстановления объекта будет зависеть от количества компонент в обратном Фурье-преобразовании. Таким образом, используя лишь один параметр – количество компонент Фурье-разложения, можно регулировать качество восстанавливаемого графического объекта и размер данных, которые необходимы для восстановления вида документа.

Предположим, что нужно получить твердую копию документа, тогда следует использовать максимальное количество компонент разложения и наилучшее качество восстановления электронного документа. Однако если речь идет о выводе документа на экран монитора или выставление его в электронной библиотеке в экранном качестве, то можно уменьшить в 2 или 3 раза число элементов разложения Фурье: вид объекта будет сохранен, необходимый сетевой трафик резко уменьшен, а качество будет вполне приемлемым для экранного разрешения, что позволит на стороне клиента контролировать создание твердых копий.

Еще одной особенностью данной технологии может быть возможность построения системы контекстного поиска внутри графического документа. Для этого растеризуем введенные буквы, обрабатываем полученные изображения по приведенной технологии, получаем векторs признаков для объектов строки поиска и находим в базе объектов наиболее близкие компоненты. Ясно, что поиск будет приближенным, но это – поиск внутри графического файла без его полного распознавания и восстановления макета документа.

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

Изложенный подход к дополнительной обработке графических документов лежит в основе реализации программного комплекса сайта электронной библиотеки «Научного наследия РАН».

Список литературы

1. Ziou, D. and Tabbone, S.: Edge Detection Techniques An Overview, International Journal of Pattern Recognition and Image Analysis, 8(4):537--559, 1998.

2. Эйнджел Э. Интерактивная компьютерная графика. Вводный курс на базе OpenGL. - С.498.

3. Прэтт У. Цифровая обработка изображений – М.: Мир, 1982. – 790 с.

4. Джексон Д. Ряды Фурье и ортогональные полиномы. - M.: Изд-во иностр. лит-ры, 1948. - С. 12-56.

5. Березнев В.А., Сотников А.Н., Чередниченко И.Н. Адаптивная статистическая модель распознавания образов. // Информационные технологии и вычислительные системы. – 1996. - № 1. - С. 55-63.