Грамматический разбор визуальных структур документа

Грамматический разбор визуальных структур документа

Иллюстрации

Показать все

Реферат

Уровень техники

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

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

Даже когда текст был "распознан" компьютерной системой, важная дополнительная информация терялась в ходе процесса. Эта информация включает в себя такие аспекты, как форматирование текста, промежутки между знаками текста, ориентация текста и общая компоновка страницы и т.п. Таким образом, если бы страница имела две колонки с изображением в правом верхнем углу, сканированная страница после обработки в OCR могла представлять собой группы текста в текстовом редакторе без двойных колонок и изображения. Или, если изображение было включено, оно обычно внедрялось в некоторой случайной точке между частями текста. Еще одна большая проблема возникает, когда используются разные стандарты построения документа. Типичная технология OCR обычно не может "преобразовать" или правильно распознать структуру документа, сформированного в другом стандарте. Вместо этого она пытается распознать текст, ограничивая его или принудительно вписывая распознанные части в ассоциированный с нею стандарт. Когда такое происходит, процесс OCR обычно вводит маркеры "неизвестный", такие как вопросительные знаки, в распознанные участки для обозначения того, что он не может обработать эти компоненты документа.

Сущность изобретения

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

Предложены системы и способы, в которых используется грамматический анализ (разбор) для упрощения распознавания структур документа. Двумерное представление документа используется для выделения иерархической структуры, которая способствует распознаванию документа. Визуальную структуру документа грамматически анализируют, используя двумерную адаптацию алгоритмов статистического анализа. Это также обеспечивает возможность распознавания компоновки (например, колонок, фамилий авторов, заголовков, сносок и т.д.) и т.п. таким образом, что можно точно интерпретировать структурные компоненты документа. Также можно использовать дополнительные методики для облегчения распознавания компоновки документа. Например, методики грамматического анализа (разбора), в которых используется обучение машины, оценка анализа на основе представлений изображения, методик усиления и/или "признаков быстрого распознавания" и т.п., можно использовать для упрощения распознавания документа. Это обеспечивает возможность эффективного распознавания документа с существенно улучшенной точностью.

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

Краткое описание чертежей

На фиг.1 показана блок-схема системы анализа визуальной структуры документа в соответствии с аспектом варианта воплощения.

На фиг.2 показана другая блок-схема системы анализа визуальной структуры документа в соответствии с аспектом варианта воплощения.

На фиг.3 показана еще одна блок-схема системы анализа визуальной структуры документа в соответствии с аспектом варианта воплощения.

На фиг.4 приведена иллюстрация примера страницы из базы данных UWIII в соответствии с аспектом варианта воплощения.

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

На фиг.6 показана иллюстрация математического выражения в соответствии с аспектом варианта воплощения.

На фиг.7 показана блок-схема последовательности операций способа, способствующего анализу визуальной структуры документа в соответствии с аспектом варианта воплощения.

На фиг.8 показана другая блок-схема последовательности операций способа, способствующего анализу визуальной структуры документа в соответствии с аспектом варианта воплощения.

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

На фиг.10 иллюстрируется другая примерная операционная среда, в которой может функционировать вариант воплощения.

Подробное описание изобретения

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

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

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

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

На фиг.1 показана блок-схема системы 100 анализа визуальной структуры документа в соответствии с аспектом варианта воплощения. Система 100 анализа визуальной структуры документа состоит из компонента 102 анализа визуальной структуры документа, который принимает входные данные 104 и предоставляет выходные данные 106. Компонент 102 анализа визуальной структуры документа использует негенеративную грамматическую модель компоновки визуальной структуры документа для облегчения определения оптимального дерева анализа для компоновки визуальной структуры. Входные данные 104 включают в себя, например, визуальную компоновку страницы документа. Компонент 102 анализа визуальной структуры документа анализирует входные данные 104, используя процесс грамматического анализа (разбора) визуальной структуры документа, для получения выходных данных 106. Выходные данные 106 могут состоять, например, из оптимального дерева анализа для компоновки визуальной структуры документа. Глобально изученная "эталонная" грамматика также может быть установлена для получения решения анализа для разных задач, и при этом не требуются дополнительное изучение грамматики.

Рассмотрим фиг.2, на которой представлена другая блок-схема системы 200 анализа визуальной структуры документа в соответствии с аспектом варианта воплощения. Система 200 анализа визуальной структуры документа состоит из компонента 202 анализа визуальной структуры документа, который принимает входные данные 204 визуальной структуры и формирует оптимальное дерево 206 анализа. Компонент 202 анализа визуальной структуры документа использует дискриминативную грамматическую модель компоновки визуальной структуры документа. Компонент 202 анализа визуальной структуры документа состоит из приемного компонента 208 и грамматического компонента 210. Приемный компонент 208 принимает входные данные 204 визуальной структуры и передает их 204 в грамматический компонент 210. В других случаях функциональные возможности приемного компонента 208 могут быть включены в грамматический компонент 210, что обеспечивает для грамматического компонента 210 возможность непосредственного приема входных данных 204 визуальной структуры. Грамматический компонент 210 также принимает грамматику 212 компоновки основной структуры. Грамматика 212 компоновки основной структуры обеспечивает исходные рамки (инфраструктуру) грамматики визуальной структуры для компоновки документа. Грамматический компонент 210 анализирует входные данные 204 визуальной структуры для получения оптимального дерева 206 анализа. 210 выполняет это путем использования процесса грамматического анализа, который анализирует визуальную структуру документа. Грамматический компонент 210 использует процесс динамического программирования для определения глобально оптимального дерева анализа. Это предотвращает ограничение оптимального дерева 206 анализа локальными оценками и позволяет получить улучшенные глобальные результаты.

Рассмотрим фиг.3, на которой представлена еще одна блок-схема системы 300 анализа визуальной структуры документа в соответствии с аспектом варианта воплощения. Система 300 анализа визуальной структуры документа состоит из компонента 302 анализа визуальной структуры документа, который принимает входные данные 304 визуальной структуры и выдает дерево 306 оптимального анализа. Компонент 302 анализа визуальной структуры документа использует дискриминативную грамматическую модель компоновки визуальной структуры документа для анализа. Компонент 302 анализа визуальной структуры документа состоит из приемного компонента 308 и грамматического компонента 310. Грамматический компонент 310 состоит из компонента 312 анализа( разбора) и компонента 314 выделения структуры документа. Компонент 312 анализа состоит из грамматической модели 316 визуальной структуры с функцией 318 грамматической стоимости. Входные данные 304 визуальной структуры включают в себя, например, визуальную компоновку страницы документа. Приемный компонент 308 принимает входные данные 304 визуальной структуры и передает их 304 в компонент 312 анализа. В других случаях функциональные возможности приемного компонента 308 могут быть включены в компонент 312 анализа, что обеспечивает возможность для компонента 312 анализа непосредственно принимать входные данные 304 визуальной структуры. Компонент 312 анализа анализирует визуальную структуру документа по входным данным 304 визуальной структуры, которые основаны первоначально на грамматике 320 компоновки визуальной структуры. Компонент 312 анализа взаимодействует с компонентом 314 выделения структуры документа, чтобы, в частности, способствовать выделению информации визуальной структуры из входных данных 304 визуальной структуры.

Компонент 314 выделения структуры документа использует сложные локальные и/или глобальные признаки для того, чтобы способствовать анализу, выполняемому компонентом 312 анализа входных данных 304 визуальной структуры. Этот компонент 314 может использовать различные необязательные механизмы для улучшения анализа компоновки визуальной структуры, выполняемого компонентом 312 анализа, включая в себя, но без ограничений, обучение 322 машины, усиление 324 анализа, признаки 326 быстрого распознавания, оценку 328 анализа и/или другие подходы 330 и т.п. Другие подходы 330 представляют другие подходы повышения эффективности и/или механизмы, ориентированные на визуальное представление, которые способствуют быстрому выполнению и/или расширению возможностей компонента 312 анализа.

Например, обучение 322 машины может быть предусмотрено компонентом 314 выделения структуры документа, для того чтобы способствовать компоненту 312 анализа при генерировании диаграммы. Этот компонент 312 затем преобразует эту диаграмму в последующий набор примеров с метками, которые передаются на процесс классификации. В процессе классификации используется последующий набор примеров с метками вместе с обучением машины для тестирования набора классификаторов. Процесс классификации затем определяет признаки идентификации между положительными и отрицательными примерами. Свойства идентификации позволяют классификаторам назначать правильную стоимость для правильных и/или неправильных результатов анализа. Компонент 312 анализа затем использует набор классификаторов в функции 318 грамматической стоимости модели 316 грамматики визуальной структуры с тем, чтобы способствовать начислению очков вспомогательным элементам анализа в последующем наборе примеров с метками. Таким образом, процесс продолжается итерационно до тех пор, пока не будет получено оптимальное дерево 306 анализа (например, больше не будет получаться дерево анализа с большей оценкой или больше не будет получаться дерево анализа с меньшей стоимостью).

Аналогично, механизм 324 усиления анализа может быть предусмотрен для компонента 312 анализа, который способствует более эффективному обучению правильному анализу. Механизм 326 признаков быстрого распознавания может быть предусмотрен для вычисления изображений анализа путем вычисления интегральных изображений признаков документа и/или использования совокупностей интегральных изображений для повышения эффективности анализа. Механизм 328 оценки анализа изображения может способствовать анализу, предоставляя оценку анализируемых изображений для функции 318 грамматической стоимости. Эти механизмы 322-330 являются необязательными и не требуются для анализа входных данных 304 визуальной структуры.

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

Таким образом, при использовании интегрального изображения становится возможным быстро вычислить количество белых и/или черных пикселей в пределах прямоугольника изображения. Расчет интегрального изображения для изображения является дорогостоящим, но после его выполнения могут быть быстро рассчитаны прямоугольные суммы. Когда задан набор объектов, которые могут быть или могут не быть изображением, существует экспоненциальное количество изображений, которые могут быть получены из этого изображения (степенное множество P(N)). Получение этих изображений и вычисление прямоугольных сумм для каждого из полученных изображений является непомерно дорогостоящим. Поэтому вместо этого для каждого из объектов получают интегральное изображение и обозначают его "совокупностью интегральных изображений". Таким образом, прямоугольная сумма для каждого поднабора изображений представляет собой сумму прямоугольных сумм из совокупностей.

В еще одном конкретном варианте осуществления раскрыта система распознавания. Система распознавания использует упомянутую ранее систему анализа визуальной структуры документа для импорта и/или экспорта визуальных структур документа.

Двумерный анализ

Хотя существует ряд конкурирующих алгоритмов анализа, одна простая, но характерная для всего класса основа называется "анализом по диаграмме" (см. публикацию М. Kay "Algorithm schemata and data structures in syntactic processing," pp. 35-70, 1986). В ходе анализа по диаграмме делаются попытки заполнить элементы диаграммы C(A, R). В каждом элементе сохраняются наилучшие оценки неконечного элемента А как интерпретация вспомогательной последовательности конечных элементов R. Стоимость любого неконечного элемента может быть выражена как следующее рекуррентное соотношение:

где {BC} охватывает всю продуктивность для A_, и R₀ представляет собой подпоследовательность конечных элементов (обозначенную как "область"), и R₁ и R₂ представляют собой подпоследовательности, которые разделены и объединение которых представляет собой R₀ (то есть они формируют "раздел"). По существу, рекуррентность указывает, что величину оценки анализа для A рассчитывают путем поиска декомпозиции с малой стоимостью конечных элементов в двух разъединенных наборах. Каждому порождению назначают стоимость (либо потери или отрицательную логарифмическую вероятность) в таблице l (А → BC). Элементы диаграммы (иногда называемые кромками) могут быть заполнены в любом порядке, как сверху вниз, так и снизу вверх. Сложность процесса анализа возникает из-за большого количества элементов диаграммы, которые следует заполнить, и объема работы, необходимой для заполнения каждого элемента. Диаграмма, построенная при анализе линейной последовательности N конечных элементов с использованием грамматики, включающих в себя P не конечных элементов, имеет O(PN ²) записей (существует непрерывных подпоследовательностей {i, j}, так что 0 ≤ i < j и j < N). Поскольку работа, требуемая для заполнения каждой записи, представляет собой О(N), общая сложность представляет собой O(PN ³).

К сожалению, непосредственное применение анализа диаграммы для двумерных компоновок конечных элементов требует экспоненциального увеличения времени. Ключевая проблема состоит в том, что конечные элементы больше не имеют линейный порядок последовательности. Вернувшись к уравнению (1), можно видеть, что область R₀ теперь представляет собой поднабор, и R₁ и R₂ представляют собой поднаборы, которые разъединены и объединение которых составляет R₀ (то есть они формируют раздел). Размер диаграммы можно проанализировать, он составляет О(P|P(N)|), где P(N) представляет собой набор всех поднаборов N конечных элементов. Поскольку существует экспоненциальное количество поднаборов, алгоритм является экспоненциальным.

Hull ввел геометрический критерий, который сокращает поиск в случаях, когда геометрический компонент стоимости слишком велик (см., J. F. Hull, "Recognition of mathematics using a two-dimensional trainable context-free grammar," Master's thesis, MIT, June 1996). Miller и Viola ввели эвристический анализ на основе выпуклых оболочек, который отбрасывает области R_1, R_2, которые нарушают равенство chull(R₁) ∩ R₂ = Ш или chull(R₂) ∩ R₁ = Ш (см., E. G. Miller and P. A. Viola, "Ambiguity and constraint in mathematical expression recognition," in Proceedings of the National Conference of Artificial Intelligence, American Association of Artificial Intelligence, 1998). Теперь эти наборы можно соответственно назвать областями, поскольку каждый из этих наборов находится в пределах выпуклой области страницы. Следует отметить, что, если конечные элементы располагаются вдоль линии (и поэтому имеют строгую линейную упорядоченность), критерий выпуклой оболочки позволяет получить О(N ²) областей, и это эквивалентно линейной последовательности, используемой при обычном анализе.

Используя ограничения выпуклой оболочки, а также другие геометрические ограничения, набор рассматриваемых поднаборов во время анализа можно существенно уменьшить. Эти ограничения в комбинации позволяют получить сложность приблизительно О(N ²) для большинства типов печатных документов.

Анализ компоновки документа

Цель анализа компоновки документа состоит в определении информации, необходимой для преобразования сканированного документа в полностью редактируемый входной файл для программы подготовки документа, такой как, например, LaTeX и/или текстовый редактор и т.п. Хотя текст в виде сканированного файла можно легко извлечь, используя OCR, такая информация недостаточна для получения легко редактируемого файла. Также необходима дополнительная информация, такая как границы абзацев, колонки, выравнивание строк и, что еще более важно, поток считывания. Такая информация о структуре документа также часто отсутствует в файлах в формате переносимого документа (формат PDF, ФПД) и файлах на языке Postscript. Если к сканированным изображениям в виде файлов PDF и/или на языке Postscript добавить информацию о структуре документа, получается очень похожий на оригинал документ, в котором можно изменять количество страниц, форматирование и/или который можно редактировать и т.п. Таким образом, наличие такой возможности существенно повышает возможность использования документа.

Программы подготовки документов часто разделяют печатную страницу на секции. Каждая секция имеет некоторое количество колонок, и каждая колонка имеет некоторое количество параграфов. Такая рекурсивная структура выражена как грамматика в ТАБЛИЦЕ 1, приведенной ниже. Знание такой структуры достаточно для точного получения пригодного для редактирования файла из сканированного документа.

ТАБЛИЦА 1: Пример грамматики, которую можно использовать для описания печатных страниц
(Page (страница) → ParList)
(ParList → Par ParList)
(ParList → Par)
(Par → LineList)
(LineList → Line (строка) LineList)
(LineList → Line)
(Line → WordList)
(WordList → Word WordList)
(WordList → Word (Слово)(Word → terminal (конечный элемент)

Были выполнены эксперименты с использованием базы данных UWIII изображений документов (см., I. Philips, S. Chen, and R. Haralick, "Cd-rom document database standard," in Proceedings of 2nd International Conference on Document Analysis and Recognition, 1993). База данных содержит сканированные документы, которые содержат контрольные данные в отношении строк, параграфов, областей и порядка считывания. На фиг.4 показана примерная страница 400 из базы данных UWIII. Входные данные для алгоритма анализа представляют собой ограничивающие прямоугольники (например, прямоугольник 402, ограничивающий параграф, и прямоугольник 404, ограничивающий строку) строк. Выходные данные представляют собой иерархическую декомпозицию на секции/колонки/параграфы. Для большинства документов метки контрольных данных легко преобразуются в упомянутую выше грамматику. Тренировку и оценку выполняли, используя набор из 60 документов, которые включают в себя страницы из научно-исследовательских публикаций, книг и журналов.

Интерпретация печатных математических текстов

В академическом исследовательском сообществе практически все новые публикации доступны либо в формате PDF или в формате Postscript. Хотя эти форматы удобны для печати, они не поддерживают простое повторное использование или изменение формата. Один из очевидных примеров представляет включенные в текст уравнения, которые легко выделить, редактировать или исследовать. Другие примеры включают в себя таблицы, сноски и библиографии и т.п. Фактически, стандарт научных публикаций представляет собой LaTeX, в частности, поскольку обеспечивает мощную и высококачественную компоновку математических текстов. Ни документы в формате PDF, ни документы на языке Postscript не обеспечивают информацию, требуемую для реконструкции уравнений LaTeX, используемых для генерирования оригинала.

Для заданного набора обучающих документов LaTeX можно использовать набор макросов LaTeX для "инструментального" исследования процесса получения документа. В результате получают набор файлов, содержащий инструменты, независимые от устройства (DVI, ИНУ), которые можно обрабатывать для выделения ограничивающих прямоугольников символов на странице и соответствующих выражений LaTeX. Эти макросы применяли для набора файлов LaTeX, которые были доступны на сервере предпечатных документов ArXiv (см., фиг.5 - примерное уравнение 500, используемое для обучения распознавателя математических выражений).

После последующей обработки обучающие данные представляли собой набор выражений, каждое из которых составляло хорошо сформированное синтаксическое дерево конечных элементов. Такие деревья обеспечивают возможность непосредственного ввода грамматики, поскольку порождения грамматики можно непосредственно наблюдать по входным деревьям (такая грамматика часто называется грамматикой "банка деревьев"). Индуцированная грамматика показана в приведенной ниже ТАБЛИЦЕ 2. Следует отметить, что конечные элементы грамматики не включены и обозначены неконечным элементом RawItem. Набор RawItem представляет собой знаки, цифры и символы, используемые для построения математических выражений. Конечные элементы грамматики представляют собой примитивно соединенные компоненты черных чернил.

ТАБЛИЦА 2: Грамматика для математических выражений
(Expr → Row (строка))
(Row → Row Item)
(Row → Item (элемент))
(Item → SubItem (подэлемент))
(Item → FracItem )
(Item → RawItem )
(Item → SupItem)
(FracItem →Row FracItem 1)
(FracItem 1→ BAR Row)
(SubItem → SupItem Row )
(SubItem → RawItem Row)
(SupItem → RawItem Row)

В отличие от других работ математического разбора не предполагается, что конечные элементы были сегментированы и распознаны перед тем, как началась интерпретация. Распознавание конечных элементов представляет собой неотъемлемую часть процесса анализа. Каждый тип символа имеет ассоциированное грамматическое правило, которое описывает порождение конечных элементов. Например, (RawItem→ EQUALS (равняется)) и (EQUALS → CC1 CC2), что указывает, что "знак равенства" состоит из пар соединенных компонентов. Функцию стоимости, ассоциированную с порождением EQUALS, требуется определять для назначения малой стоимости для пар соединенных компонентов, которые выглядят как "=". Общая установка этой задачи является механически простой. Грамматику создают на примере файлов LaTeX, и свойства выбирают автоматически из большого набора, в общем, ценных признаков, которые определены ниже.

Признаки

Признаки, используемые для изучения функций оценки порождения, в общем случае, применяют и используют для широкого диапазона задач. Набор свойств геометрических ограничивающих прямоугольников доказал свою ценность при измерении степени выравнивания компонентов. Первый тип связан с ограничивающими прямоугольниками наборов R₀, R₁ и R₂. Они измеряют положение углов, X_i, Y_i и размер W, H прямоугольника в координатах страницы. Существует всего 360 признаков измерения, которые обозначаются как {m_j (R)}. Второй набор признаков является комбинаторным и сопоставляет все пары признаков измерения прямоугольника: g(m_j R_а), m_j(R_b)), где a и b представляют собой {0,1,2} и функция g может представлять собой сложение, вычитание, умножение, деление, минимум или максимум. Третий набор признаков измеряет свойства ограничительных прямоугольников конечных элементов, включенных в области. Это включает в себя измерение минимума, максимума, среднего значения, среднеквадратичного отклонения и медиану некоторых признаков измерения, оцениваемых для конечных элементов во всей области.

Кроме того, существует большой набор признаков распознавания шаблонов, которые были разработаны для того, чтобы различать области на основе внешнего вида. Эти признаки работают с полученными изображениями конечных элементов в областях. На фиг.6 показана иллюстрация 600 математического выражения 602. Во время анализа встречается выражение Z₀ 604 и его требуется интерпретировать. Здесь представлены четыре изображения 606, используемые как входные данные для процесса оценки порождения. Визуальные признаки необходимы, когда сами конечные элементы требуется распознавать на основе внешнего вида. Применяют свойства прямоугольника, предложенные Viola и Jones (см., P. Viola and M. Jones, "Rapid object detection using a boosted cascade of simple features," in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2001). Они являются эффективными для компьютерных вычислений и доказали свою эффективность для широкого диапазона задач. Каждое входное изображение представлено 121 признаком простого прямоугольника, выбранным однородно в соответствии с местоположением и масштабом. Намного больший набор использовали для более сложных задач распознавания изображения, но он оказался достаточным для этих задач.

Геометрическая нормализация представляет собой критический вопрос при построении функции классификации изображения. В этом случае выбирают эталонную рамку, которая нормализует размер и местоположение R₀. Цель R₀ состоит в том_, чтобы заполнить 80% визуального изображения. Выполняют поиск конечных элементов R₁ и R₂ в этой рамке координат. Это обеспечивает признаки изображения со входным изображением, содержащим информацию об относительных положениях R₁ и R₂. Так, например, если R₂ представляет собой подстрочный индекс, тогда положение его полученных компонентов будет направлено вниз эталонной рамки. Наконец, выполняют поиск конечных элементов всего документа в эталонной рамке R_0, но в намного меньшем масштабе. Такое изображение кодирует "контекст" документа, и его можно использовать для разрешения местных неоднозначностей определенных типов.

Во время анализа каждую потенциальную область и подобласть кодируют как набор изображений. Когда существует множество областей, процесс кодирования изображения, который включает в себя изменение масштаба изображения, наивно привел бы к большему объему вычислений. Для исключения таких объемных вычислений используют представление интегрального изображения, введенное Viola и Jones, для расчета прямоугольных фильтров с любым масштабом без дополнительных затрат.

ПРИМЕРЫ

Два набора экспериментов были выполнены с использованием признаков, описанных выше. Общий процесс изучения грамматических параметров описан в приведенной ниже ТАБЛИЦЕ 3. В каждом раунде изучения AdaBoost используют конечные ветви по решениям. Это предусматривает очень простой механизм управления сложностью (ранние остановки). Такой подход также предусматривает механизм выбора признаков, поскольку каждый раунд усиления выбирает одиночную конечную ветвь, которая, в свою очередь, ассоциирована с одним признаком.

ТАБЛИЦА 3: Псевдокод для алгоритма тренировки
0) Установить исходные значения весовых коэффициентов, равные нулю для всех порождений
1) Анализировать набор примеров обучения, используя текущие параметры
2) Для каждого порождения в грамматике
a) Собрать все примеры из всех диаграмм.
Примеры из всех истинных результатов анализа имеют значение TRUE.
Все другие имеют значение FALSE.