Модуль обнаружения формул

Модуль обнаружения формул

Иллюстрации

Показать все

Реферат

УРОВЕНЬ ТЕХНИКИ

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

[2] В ситуациях, где нужна правка документа фиксированного формата, но исходный документ нефиксированного формата недоступен, документ фиксированного формата должен быть преобразован в документ нефиксированного формата. Преобразование включает в себя синтаксический анализ документа фиксированного формата и преобразование базовых элементов физического макета из документа фиксированного формата в более сложные логические элементы, используемые в документе нефиксированного формата. Существующие преобразователи документов, столкнувшись со сложными элементами, например математическими формулами и выражениями, прибегают к базовым методикам, предназначенным для сохранения визуальной точности макета документа фиксированного формата (например, рамки с текстом, междустрочный интервал, межзнаковый интервал и изображения) ценой "подвижности" выходного документа. Результатом является ограниченный документ нефиксированного формата, который требует от пользователя выполнение значительного ручного восстановления, чтобы получить действительно полезный документ нефиксированного формата. Именно относительно этих и других соображений создано настоящее изобретение.

КРАТКОЕ ИЗЛОЖЕНИЕ СУЩНОСТИ ИЗОБРЕТЕНИЯ

[3] Нижеследующее краткое изложение сущности изобретения предоставляется, чтобы представить подборку идей в упрощенном виде, которые дополнительно описываются ниже в Подробном описании. Данное Краткое изложение сущности изобретения не предназначено ни для определения ключевых признаков или существенных признаков заявленного изобретения, ни для использования в ограничении объема заявленного изобретения.

[4] Один вариант осуществления модуля обнаружения формул исполняет ассоциированный способ обнаружения формул как часть процесса преобразования, преобразующего документ фиксированного формата в документ нефиксированного формата. Модуль обнаружения формул создает начальные области формулы путем идентификации элементов, которые потенциально являются частью математической формулы, и группирования тех элементов в области формулы на основе относительного положения тех элементов. Модуль обнаружения формул начинает с идентификации исходных элементов формулы в проанализированных элементах. Исходный элемент формулы является текстовым элементом, который несет некоторое указание, что является частью формулы, например текстовые цепочки, записанные шрифтами, используемыми исключительно или почти исключительно для отображения математических выражений и математических операторов, символы или ключевые слова, которые исключительно или почти исключительно используются в математических формулах. Как только идентифицированы исходные элементы формулы, модуль обнаружения формул задает область формулы (то есть границу) вокруг каждого из обнаруженных исходных элементов формулы и расширяет границы, чтобы сгруппировать исходные элементы формулы и другие элементы на основе близости. Все элементы страницы, обведенные ограничивающим прямоугольником области формулы, считаются захваченными элементами.

[5] Далее модуль обнаружения формул устраняет перекрытие между областями формулы и любым окружающим обычным текстом (то есть текстовыми элементами, которые не являются частью математической формулы) путем подразделения областей формулы, перекрывающих обычный текст, на основе вертикального положения и разбиения областей формулы на основе горизонтального интервала. Модуль обнаружения формул начинает с анализа каждой области формулы для определения того, перекрывает ли область формулы какие-либо области обычного текста. Если область формулы перекрывает какой-либо обычный текст, то модуль обнаружения формул делит область формулы путем группирования захваченных элементов на основе вертикального положения. Вокруг каждой группы захваченных элементов создается новая область формулы. Модуль обнаружения формул анализирует содержимое новых областей формулы на предмет перекрытия с обычным текстом, и любая новая область формулы, все еще содержащая обычный текст, делится дальше. Как только поделены области формулы, модуль обнаружения формул разбивает каждую область формулы в соответствии с горизонтальным интервалом между захваченными элементами.

[6] В конечном счете, модуль обнаружения формул восстанавливает математические формулы в виде "плавающих" элементов путем объединения любых соседних областей формулы на основе близости. Модуль обнаружения формул использует информацию о положениях соседних текстовых элементов, чтобы предотвратить объединение областей формулы, появляющихся на разных строках на странице. Области формулы, которые перекрываются горизонтально (то есть по меньшей мере частично ориентированы вертикально) и находятся в пределах выбранного расстояния вертикального разделения, группируются в качестве кандидатов объединения. Модуль обнаружения формул упорядочивает (например, сортирует) кандидаты объединения в соответствии с вертикальным разделением между областями формулы и заменяет две области формулы у кандидата объединения новой областью формулы при условии, что две области формулы еще не объединены и не находятся на отдельных строках.

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

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

Фиг. 1 иллюстрирует систему, включающую в себя модуль обнаружения формул;

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

Фиг. 3 - логическая блок-схема, показывающая один вариант осуществления способа обнаружения формул;

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

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

Фиг. 5B графически иллюстрирует типовую операцию из одного варианта осуществления процесса создания начальных областей формулы;

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

Фиг. 7A-D графически иллюстрируют избранные типовые операции из одного варианта осуществления процесса устранения перекрытия между областями формулы и обычным текстом, используемого в одном варианте осуществления способа обнаружения формул;

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

Фиг. 9A-B графически иллюстрируют избранные типовые операции из одного варианта осуществления процесса восстановления отдельных формул, используемого в способе обнаружения формул;

Фиг. 10 иллюстрирует типовое планшетное вычислительное устройство, исполняющее вариант осуществления модуля обнаружения формул;

Фиг. 11 - упрощенная блок-схема типового вычислительного устройства, подходящего для осуществления на практике вариантов осуществления модуля обнаружения формул;

Фиг. 12A иллюстрирует один вариант осуществления мобильного вычислительного устройства, исполняющего один вариант осуществления модуля обнаружения формул;

Фиг. 12B - упрощенная блок-схема типового мобильного вычислительного устройства, подходящего для осуществления на практике вариантов осуществления модуля обнаружения формул; и

Фиг. 13 - упрощенная блок-схема типовой системы распределенных вычислений, подходящей для осуществления на практике вариантов осуществления модуля обнаружения формул.

ПОДРОБНОЕ ОПИСАНИЕ

[9] Модуль обнаружения формул и связанный с ним способ для идентификации математических формул и выражений в данных, извлеченных из документа фиксированного формата, описываются в этом документе и иллюстрируются на прилагаемых чертежах. Модуль обнаружения формул определяет местонахождение формул в части документа фиксированного формата путем идентификации исходного элемента формулы. Модуль обнаружения формул создает и расширяет границу вокруг исходного элемента формулы, чтобы задать область формулы. Чтобы устранить перекрытие с окружающим обычным текстом, область формулы делится на несколько областей формулы на основе вертикального положения и горизонтального интервала между захваченными элементами. Результирующие области формулы, упорядоченные вертикально, и горизонтально перекрывающиеся области формулы объединяются для восстановления формулы в виде плавающего элемента.

[10] Фиг. 1 иллюстрирует один вариант осуществления системы, заключающей в себе модуль 100 обнаружения формул. В проиллюстрированном варианте осуществления модуль 100 обнаружения формул работает как часть преобразователя 102 документов, исполняемого на вычислительном устройстве 104. Преобразователь 102 документов преобразует документ 106 фиксированного формата в документ 108 нефиксированного формата, используя синтаксический анализатор (парсер) 110, процессор 112 документов и параллельно-последовательный преобразователь (сериализатор) 114. Синтаксический анализатор 110 считывает и извлекает данные из документа 106 фиксированного формата. Данные, извлеченные из документа фиксированного формата, записываются в хранилище 116 данных, доступное процессору 112 документов и параллельно-последовательному преобразователю 114. Процессор 112 документов анализирует и преобразует данные в плавающие элементы, используя один или несколько модулей обнаружения и/или восстановления (например, модуль 100 обнаружения формул из настоящего изобретения). В конечном счете параллельно-последовательный преобразователь 114 записывает плавающие элементы в плавающий формат документа (например, формат обработки текстов).

[11] Фиг. 2 подробнее иллюстрирует один вариант осуществления последовательности операций в процессоре 112 документов. Процессор 112 документов включает в себя необязательный модуль 202 оптического распознавания символов (OCR), модуль 204 анализа макета и модуль 206 семантического анализа. Данные, содержащиеся в хранилище 116 данных, включают в себя объекты 208 физического макета и объекты 210 логического макета. В некоторых вариантах осуществления объекты 208 физического макета и объекты 210 логического макета иерархически организуются в древовидный массив групп (то есть объектов данных). В различных вариантах осуществления страница является группой верхнего уровня для объектов 208 физического макета, тогда как раздел является группой верхнего уровня для объектов 210 логического макета. Данные, извлеченные из документа 106 фиксированного формата, обычно сохраняются в виде объектов 208 физического макета, организованных по содержащей странице, в документе 106 фиксированного формата. Базовые объекты физического макета включают в себя текстовые цепочки, изображения и контуры. Текстовые цепочки являются текстовыми элементами в потоках содержимого страницы, задающими положения, где отрисовываются знаки при отображении документа фиксированного формата. Изображения являются растровыми изображениями (то есть картинками), сохраненными в документе 106 фиксированного формата. Контуры описывают элементы, такие как линии, кривые (например, кривые Безье третьего порядка) и текстовые структуры, используемые для создания векторной графики. Логические объекты данных включают в себя плавающие элементы, например разделы, абзацы, столбцы и таблицы.

[12] То, где начинается обработка, зависит от типа анализируемого документа 106 фиксированного формата. "Родной" документ 106a фиксированного формата, созданный непосредственно из исходного документа нефиксированного формата, содержит некоторые или все базовые элементы физического макета. Как правило, данные извлекаются из "родного" документа фиксированного формата. Внедренные структуры данных извлекаются синтаксическим анализатором и доступны для немедленного использования преобразователем документов; хотя в некоторых случаях применяется незначительное переформатирование или другая незначительная обработка для организации или стандартизации данных. В отличие от этого вся информация в основанном на изображениях документе 106b фиксированного формата, созданном с помощью оцифровки физического документа (например, сканирования или фотографирования), сохраняется в виде последовательности изображений страниц без дополнительных данных (то есть без текстовых цепочек или контуров). В этом случае необязательный модуль 202 оптического распознавания символов анализирует каждое изображение страницы и создает соответствующие объекты физического макета. Как только доступны объекты 208 физического макета, модуль 204 анализа макета анализирует макет документа фиксированного формата. После того как завершается анализ макета, модуль 206 семантического анализа "обогащает" объекты логического макета семантической информацией, полученной из анализа объектов физического макета и/или объектов логического макета.

[13] Фиг. 3 - логическая блок-схема, показывающая один вариант осуществления способа 300 обнаружения формул, исполняемого модулем 100 обнаружения формул. Модуль 100 обнаружения формул создает (302) начальные области формулы путем идентификации элементов в объектах физического макета, которые потенциально являются частью математической формулы, и группирования тех элементов в области формулы на основе относительного положения тех элементов. Далее, модуль 100 обнаружения формул устраняет (304) перекрытие между областями формулы и любым окружающим обычным текстом (то есть текстовыми элементами, которые не являются частью математической формулы) путем подразделения областей формулы, перекрывающих обычный текст, и разбиения областей формулы на основе горизонтального интервала. В конечном счете модуль 100 обнаружения формул восстанавливает (306) математические формулы в виде "плавающих" элементов путем объединения любых соседних областей формулы на основе близости.

[14] Фиг. 4 - логическая блок-схема, показывающая один вариант осуществления процесса создания (302) начальных областей формулы, используемого в способе 300 обнаружения формул. Модуль 100 обнаружения формул начинает с идентификации (402) исходных элементов формулы в проанализированных элементах. В более общем смысле исходный элемент формулы является текстовым элементом, который несет некоторое указание того, что он является частью формулы. Чтобы идентифицировать исходные элементы формулы, модуль 100 обнаружения формул ищет одно или несколько из следующего, без ограничения: текстовые цепочки, записанные шрифтами, используемыми исключительно или почти исключительно для отображения математических выражений и математических операторов, символы или ключевые слова, которые исключительно или почти исключительно используются в математических формулах.

[15] Например, текстовый процессор может представлять формулы с помощью математического шрифта, например Cambria® Math Корпорации Майкрософт, тогда как система подготовки документов (например, LaTeX) может использовать несколько семейств математических шрифтов, например математические шрифты Computer Modern. Модуль 100 обнаружения формул также рассматривает наличие математических операторов, символов и ключевых слов, чтобы идентифицировать исходные элементы формулы, поскольку некоторые процессоры документов не используют никакие специальные математические шрифты для математики. Примеры математических операторов, символов или ключевых слов, используемых для обнаружения формул, включают в себя операторы, например "Σ" и "±", символы, например "π", и ключевые слова, например "cos", представляющий косинусную функцию. Как правило, модуль 100 обнаружения формул использует ключевые слова, которые не имеют смысла в обычном языке (например, "tan"). В различных вариантах осуществления шрифты, используемые для идентификации исходных элементов формулы, включают в себя, но не ограничиваются, некоторые или все из следующих шрифтов: Cambria® Math, Computer Modern math Italic (cmmi), Computer Modern math bold Italic (cmmib), Computer Modern math extension (cmex), Computer Modern math symbols (cmsy), Computer Modern bold math symbols (cmbsy), дополнительные математические символы American Math Society - первая последовательность (masm), дополнительные математические символы American Math Society - вторая последовательность (msbm), расширенный набор интегралов для Computer Modern (esint), MathTime TeX math italic (mtmi), MathTime TeX math symbols (mtsy), MathTime TeX math extension (mtex) и символы Roland Waldi (wasy). В некоторых вариантах осуществления исходные элементы формулы включают в себя, но не ограничиваются, некоторые или все знаки или наборы знаков Unicode в диапазонах #2200-#22FF (математические операторы), #27C0-#27EF (разнообразные математические символы-A), #2980-#29FF (разнообразные математические символы-B) и #2A00-#2AFF (дополнительные математические операторы) в качестве исходных элементов формулы. В различных вариантах осуществления исходные элементы формулы включают в себя, но не ограничиваются, некоторые или все из следующих текстовых ключевых слов: det, sin, cos, tg, tan, ctg, ctan, sinh, cosh, tanh, ctanh, log, In, gcd, arcsin, arcos, arctan, sec, csc, max, min, inf, sup, lim, sgn, exp, mod и var.

[16] Как только идентифицированы исходные элементы формулы, модуль 100 обнаружения формул задает (404) область формулы (то есть границу) вокруг каждого из обнаруженных исходных элементов формулы. Далее модуль 100 обнаружения формул расширяет (406) границы вокруг исходных элементов формулы, чтобы создать начальные области формулы. В одном варианте осуществления он добавляет все элементы страницы в окрестности исходного элемента формулы, которые обладают свойствами математических элементов, до тех пор, пока больше не останется таких элементов. Чтобы решить, следует ли включить элемент страницы в область формулы, модуль 100 обнаружения формул ищет свойства, идентифицирующие элемент страницы как возможный элемент математической формулы. В различных вариантах осуществления модуль 100 обнаружения формул рассматривает свойства, включающие в себя, но не только, евклидово расстояние от области формулы до элемента страницы, шрифт текста у элемента страницы, наличие математических операторов, символов и/или цифровых знаков (то есть цифр) в элементе страницы и размеры элемента страницы (то есть выше ли он либо шире стандартных текстовых элементов). Все элементы страницы, обведенные ограничивающим прямоугольником области формулы, считаются захваченными элементами.

[17] Фиг. 5A графически иллюстрирует выбранную часть данных 500, полученных посредством синтаксического разбора из документа фиксированного формата, примерами исходных элементов 502a-d формулы, идентифицированных модулем 100 обнаружения формул. Исходные элементы формулы, идентифицированные по шрифту 502a, обводятся прямоугольниками из пунктирной линии, а исходные элементы формулы, идентифицированные по математическим операторам 502b, символам 502c и ключевым словам 502d, обводятся овалами из сплошной линии.

[18] Фиг. 5B графически иллюстрирует начальную область 504 формулы, созданную модулем 100 обнаружения формул, очерченную ограничивающим прямоугольником. В проиллюстрированном варианте осуществления результатом является область формулы, ограниченная прямоугольниками, которые содержат одну или несколько математических формул. Там, где математические формулы достаточно разнесены друг от друга, каждая область формулы будет захватывать одну математическую формулу; однако в случаях, где несколько математических формул находятся в непосредственной близости, можно захватить отдельные математические формулы в одной области формулы. Кроме того, когда захватывается больше одной формулы в одной области формулы, расширенная область формулы может перекрывать окружающий обычный текст. В проиллюстрированном варианте осуществления расширенная область формулы захватила несколько математических формул 506 и перекрывает обычный текст 508, окружающий математические формулы.

[19] Фиг. 6 - логическая блок-схема, показывающая один вариант осуществления процесса устранения (304) перекрытия между областями формулы и обычным текстом, используемого в способе 300 обнаружения формул. Модуль 100 обнаружения формул начинает с анализа (600) каждой области формулы для определения, перекрывает ли область формулы какие-либо области обычного текста. Если область формулы перекрывает какой-либо обычный текст, то модуль 100 обнаружения формул продолжает выполнение группированием (602) каждого захваченного элемента на основе вертикального положения захваченного элемента. Вокруг каждой новой группировки захваченных элементов создается (604) новая область формулы. Модуль 100 обнаружения формул анализирует содержимое новых областей формулы на предмет перекрытия с обычным текстом, и любая новая область формулы, содержащая обычный текст, делится дальше. Многократный анализ, разбиение и уменьшение каждой новой области формулы по мере необходимости позволяет модулю 100 обнаружения формул справляться со случаями, где область формулы перекрывает несколько строк текста. Как только области формулы сгруппированы вертикально, модуль 100 обнаружения формул продолжает выполнение разбиением (606) каждой области формулы в соответствии с горизонтальным интервалом между захваченными элементами.

[20] Фиг. 7A-D графически иллюстрируют подпроцесс устранения (304) перекрытия между областями формулы и обычным текстом, используемый в способе 300 обнаружения формул, применяемом к начальной области 504 формулы. Фиг. 7A показывает начальную область 504 формулы, поделенную двумя горизонтальными делителями 700a, 702a, используемыми для группирования захваченных элементов начальной области 504 формулы на основе вертикального положения. Горизонтальные линии 700a, 702a соответствуют высоте строки обычного текста. Первая горизонтальная линия 700a соответствует верхнему краю (то есть границе) прямоугольника, ограничивающего строку обычного текста, содержащую математическую формулу. Вторая горизонтальная линия 702a соответствует нижнему краю прямоугольника, ограничивающего строку обычного текста, содержащую математические формулы.

[21] Делители 700a, 702a делят начальную область 504 формулы на верхнюю область 704a, среднюю область 706a и нижнюю область 708a, которые соответствуют областям выше, на уровне и ниже строки обычного текста. Если один из основных делителей 700a, 702a пересекает захваченные элементы, то модуль 100 обнаружения формул по необходимости устанавливает вспомогательную верхнюю горизонтальную разделительную линию 710a и вспомогательную нижнюю горизонтальную разделительную линию 712a выше и ниже самого верхнего и самого нижнего положений пересеченных захваченных элементов. Специалистам в данной области техники следует принять во внимание, что вспомогательные делители 710a, 712a не нужно устанавливать, если основные делители 700a, 702a не пересекают никакие захваченные элементы. В качестве альтернативы вспомогательные делители 710a, 712a могут быть коллинеарными с основными делителями 700a, 702a.

[22] Только те захваченные элементы, которые находятся целиком выше самой верхней разделительной линии 700a, 710a, установленной модулем 100 обнаружения формул, помещаются в первую группу, соответствующую верхней области 704a. В проиллюстрированном варианте осуществления в первую группу попадают только символы "n" и "∞". Аналогичным образом только те захваченные элементы, которые находятся целиком ниже самой нижней разделительной линии 702a, 712a, установленной модулем 100 обнаружения формул, помещаются во вторую группу, соответствующую нижней области 708a. В проиллюстрированном варианте осуществления члены "k=0" и "n=1" и текст, уравнения и формулы на строке ниже тех членов становятся частью второй группы. Все захваченные элементы, которые не попадают ни в одну из первой группы и второй группы, помещаются в третью группу, соответствующую средней области 706a. Другими словами, третья группа содержит захваченные элементы, которые находятся целиком между основными делителями 700a, 702a, пересекаются одним или обоими основными делителями 700a, 702a либо вертикально перекрывают пересеченный захваченный элемент. Любые пустые группы отбрасываются.

[23] Фиг. 7B иллюстрирует операцию создания (604) новых областей формулы вокруг групп на основе вертикального положения захваченных элементов. Из начальной области 504 формулы создается вплоть до трех новых областей формулы. Модуль 100 обнаружения формул при желании уменьшает размеры каждой новой области формулы в подходящей степени, достаточной для обведения всех захваченных там элементов формулы. В проиллюстрированном варианте осуществления начальная область 504 формулы подразделена на три новые области 714, 716 и 718 формулы, а начальная область 500 формулы отброшена. Каждая из новых областей 714, 716 и 718 формулы подвергается операции 600 идентификации перекрытия. В проиллюстрированном варианте осуществления две самые верхние новые области 714, 716 формулы не требуют никакого дополнительного вертикального деления. Третья новая область 718 формулы все еще содержит вертикальное перекрытие между областями формулы и обычным текстом. Соответственно, модуль 100 обнаружения формул повторяет операцию 602 группирования по вертикальному положению и операцию 604 создания новой области формулы над третьей новой областью 718 формулы. Нижняя разделительная линия 702b пересекает оператор суммирования, а верхняя разделительная линия 700b пересекает оператор квадратного корня и оператор суммирования. Отметим, что вспомогательный верхний делитель 710b устанавливается выше самого высокого пересеченного захваченного элемента (то есть оператора квадратного корня). Как и раньше, делители 700b, 702b разбивают область 718 формулы на верхнюю область 704b, среднюю область 706b и нижнюю область 708b. Модуль 100 обнаружения формул перегруппирует захваченные элементы в области 718 формулы описанным выше способом.

[24] Фиг. 7C иллюстрирует конечный результат многократного применения операции 600 идентификации перекрытия, операции 602 группирования по вертикальному положению и операции 604 создания новой области формулы. Третья новая область 718 формулы поделена на две новые области 724, 726 формулы. Первая область 724 формулы соответствует верхней области 704b у области 718 формулы, а вторая область 726 формулы соответствует средней области 706b у области 718 формулы. Пустая группа, соответствующая средней области 706b у области 718 формулы, отброшена. Ни одна из оставшихся областей 724, 726 формулы не требует никакого дополнительного вертикального группирования.

[25] Фиг. 7D иллюстрирует операцию разбиения (606) областей формулы на основе горизонтального интервала между захваченными элементами. Модуль 100 обнаружения формул начинает с горизонтального сканирования каждой области формулы и определения горизонтального расстояния между каждой парой последовательных захваченных элементов в области формулы. В некоторых вариантах осуществления направление горизонтального сканирования соответствует направлению чтения в языке документа. В других вариантах осуществления направление горизонтального сканирования идет слева направо или справа налево независимо от языка документа. Модуль 100 обнаружения формул делит область формулы между двумя последовательными захваченными элементами, разделенными горизонтальным расстоянием больше выбранного порогового расстояния, для создания новых областей формулы. В различных вариантах осуществления горизонтальное расстояние между последовательными захваченными элементами определяется из пробельного символа. Пунктирные линии 730 разрыва, показанные на фиг. 7D, указывают, где горизонтальное разделение превышает выбранную пороговую величину. В некоторых вариантах осуществления используется одна пороговая величина. В других вариантах осуществления пороговая величина меняется на основе окружающего текста.

[26] Фиг. 8 - логическая блок-схема, показывающая один вариант осуществления подпроцесса восстановления (306) отдельных формул путем группирования блоков формул. Модуль 100 обнаружения формул начинает с определения местонахождения (800) элементов обычного текста, появляющихся слева и справа от каждой области формулы. Модуль 100 обнаружения формул использует информацию о положениях соседних текстовых элементов, чтобы предотвратить объединение областей формулы, появляющихся на разных строках на странице. Модуль 100 обнаружения формул затем формирует наборы кандидатов объединения из доступных областей формулы. Области формулы, которые перекрываются горизонтально (то есть по меньшей мере частично ориентированы вертикально) и находятся в пределах выбранного расстояния вертикального разделения, группируются (802) в качестве кандидатов объединения. Модуль обнаружения формул упорядочивает (например, сортирует) (804) кандидатов объединения в соответствии с вертикальным расстоянием между областями формулы. В некоторых вариантах осуществления кандидаты объединения сортируются в возрастающем порядке. В других вариантах осуществления кандидаты объединения сортируются в убывающем порядке. Проходя по сортированным кандидатам объединения от первого к последнему, модуль 100 обнаружения формул заменяет (806) две области формулы, образующие кандидата объединения, новой областью формулы при условии, что две области формулы еще не объединены в одну область формулы и их вертикальные положения не ассоциированы с вертикальными положениями отдельных строк. В некоторых вариантах осуществления то, находятся ли области формулы на одной и той же строке на странице, определяется из обычного текста справа и/или слева от каждой области формулы. Если обычный текст справа или слева от каждой области формулы является одинаковым, то области формулы определяются как расположенные в пределах одной строки на странице. Наоборот, несходство обычного текста справа или слева от областей формулы указывает, что области формулы располагаются на разных строках на странице. Граница объединенной области формулы задается максимальными размерами двух областей формулы, образующих кандидата объединения. Другими словами, новая область формулы задается путем выбора самой верхней, самой нижней, самой левой и самой правой границы из верхней, нижней, левой и правой границ кандидатов объединения.

[27] Фиг. 9A и 9B графически иллюстрируют избранные операции из подпроцесса восстановления (306) отдельных формул, применяемого к текстовой цепочке 500. Фиг. 9A показывает выбранные области формулы, сгруппированные в кандидаты объединения. Первая группа 900a кандидатов объединения включает в себя области 914a, 916a и 924a формулы. Вторая группа 900b кандидатов объединения включает в себя области 914b, 916b и 924b формулы. Области 924a и 924b формулы не являются кандидатами объединения с областями 926a и 926b формулы соответственно, потому что расстояние вертикального разделения превышает выбранную пороговую величину. Более того, области 926a и 926b формулы не объединяются с группами 900a и 900b объединения соответственно, потому что обычный текст слева и справа отличается между ними (то есть области формулы находятся на разных строках на странице). Фиг. 9B показывает окончательное решение с каждой из четырех формул 902a-d, должным образом отделенных друг от друга и от окружающего обычного текста.

[28] При использовании в данном документе термины "область", "граница", "прямоугольник" используются взаимозаменяемо. Аналогичным образом термины "строка" и "делитель" используются взаимозаменяемо. Специалистам в данной области техники следует принять во внимание, что границы и делители, описанные в этом документе, в действительности не должны визуально представляться и/или отображаться во время способа обнаружения формул. Более того, границы и делители не ограничиваются прямоугольниками или строками. Границы и делители могут принимать другие формы (например, кривые) без отклонения от объема и сущности настоящего изобретения. Кроме того, границы и делители просто используют координаты или другие системы отсчета. Термины, ассоциирующиеся с формами (например, прямоугольник, линия и овал), не следует толковать как ограничивающие, а следует широко интерпретировать по обстоятельствам как включающие в себя любую подходящую границу или делитель, пока описание изобретения ясно не укажет иное.

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

[30] Хотя изобретение описано в общем контексте программных модулей, которые исполняются в сочетании с прикладной программой, которая выполняется в операционной системе на компьютере, специалисты в данной области техники признают, что изобретение также можно реализовать совместно с другими программными модулями. Как правило, программные модули включают в себя процедуры, программы, компоненты, структуры данных и другие типы структур, которые выполняют конкретные задачи или реализуют конкретные абстрактные типы данных.

[31] Варианты осуществления и функциональные возможности, описанные в этом документе, могут функционировать посредством множества вычислительных систем, включающих в себя, без ограничения, настольные компьютерные системы, проводные и беспроводные вычислительные системы, мобильные вычислительные системы (например, мобильные телефоны, нетбуки, компьютеры планшетного типа, блокнотные компьютеры и переносные компьютеры), наладонные устройства, многопроцессорные системы, микропроцессорную или программируемую бытовую электронику, мини-компьютеры и мэйнфреймы. Фиг. 10 иллюстр