Сегментация многостолбцового документа

Сегментация многостолбцового документа

Иллюстрации

Показать все

Реферат

ОБЛАСТЬ ТЕХНИКИ

[0001] Предмет настоящей заявки относится к способу и системе в области обработки изображений, в частности к анализу документов со сложной пространственной разметкой со сложным пространственным расположением.

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

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

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

РАСКРЫТИЕ ИЗОБРЕТЕНИЯ

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

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

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

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

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

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

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

[0010] Вышеизложенное и другие объекты, аспекты, особенности и преимущества данного раскрытия изобретения станут более очевидными и более понятными при обращении к последующему описанию, рассматриваемому вместе с прилагаемыми чертежами, на которых:

[0011] Фиг. 1 представляет собой блок-схему способа обнаружения логической структуры документа в соответствии с иллюстративным вариантом осуществления изобретения;

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

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

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

[0015] Фиг. 5 представляет собой блок-схему способа разделения документа на регионы в соответствии с иллюстративным вариантом осуществления изобретения;

[0016] Фиг. 6 иллюстрирует пример изображения документа с искаженными колонками в соответствии с иллюстративным вариантом осуществления изобретения (Эта фигура несла иллюстративный характер. Приведенный в ней текст не нес смысловой нагрузки, переводить ее текст не представляется возможным и текстовая часть заменена на произвольный иллюстративный русский текст. Ни иллюстративный английский текст (фотография), ни заменяющий русский текст не являются частью заявки и приведены как пример иллюстрации);

[0017] Фиг. 7 иллюстрирует пример изображения документа с врезками в соответствии с иллюстративным вариантом осуществления изобретения (Эта фигура несла иллюстративный характер. Приведенный в ней текст не нес смысловой нагрузки, переводить ее текст не представляется возможным и текстовая часть заменена на произвольный иллюстративный русский текст. Ни иллюстративный английский текст (фотография), ни заменяющий русский текст не являются частью заявки и приведены как пример иллюстрации);

[0018] Фиг. 8 иллюстрирует примеры объектов на изображении документа в соответствии с иллюстративным вариантом осуществления изобретения;

[0019] Фиг. 9 иллюстрирует первый пример графа объектов на изображении документа в соответствии с иллюстративным вариантом осуществления изобретения;

[0020] Фиг. 10 иллюстрирует второй пример графа объектов на изображении документа в соответствии с иллюстративным вариантом осуществления изобретения;

[0021] Фиг. 11 представляет собой блок-схему системы для обнаружения логической структуры документа в соответствии с иллюстративным вариантом осуществления изобретения.

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

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

[0023] Ссылка в этом описании на «один вариант осуществления» или «вариант осуществления» означает, что конкретная особенность, структура или характеристика, описанная в связи с осуществлением изобретения, включена по меньшей мере в один из вариантов осуществления настоящего изобретения. Неоднократное появление выражения «в одном из вариантов осуществления» в различных местах описания не обязательно относятся к одному и тому же варианту осуществления, а отдельные или альтернативные варианты осуществления изобретения не являются взаимоисключающими по отношению к другим вариантам осуществления. Кроме того, приведено описание различных особенностей, которые могут использоваться в некоторых вариантах осуществления изобретения и не использоваться в других вариантах его осуществления. Аналогично приведены описания различных требований, которые могут предъявляться к некоторым вариантам осуществления этого изобретения, но не к другим вариантам его осуществления.

[0024] Сегментация является важным шагом при распознавании изображения документа. Процесс сегментации позволяет выявить различные регионы на изображениях документов. Регионы могут представлять собой колонки, рисунки, таблицы, фрагменты текста, заголовки и т.д.

[0025] Настоящее изобретение относится к способам и системам обнаружения (или выявления) основной структуры документа. В некоторых вариантах осуществления документ может содержать колонки текста, изображения, таблицы и т.д. Настоящее изобретение также относится к обнаружению (выявлению) границ объектов любой сложности, расположенных в документе, например, границы объектов в документе могут частично или полностью врезаться в колонки. В некоторых вариантах осуществления обнаружение границ включает обнаружение просветов между колонками, например, на изображении документа. Просветы на изображениях документов могут быть изогнутыми, узкими или искаженными. В некоторых вариантах осуществления объекты в документе могут иметь произвольную форму, что увеличивает сложность определения границ. Пример документа с изогнутыми колонками 62 показан на Фиг. 6. Документ может содержать различные регионы, такие как фрагменты текста, картинки, колонки, таблицы, схемы и т.д. Описанные в настоящем документе способы и системы могут разделить документ на такие регионы для того, чтобы правильно понять их логическую взаимосвязь.

[0026] В документе могут присутствовать регионы двух типов: регионы колонок и неколоночные регионы. Регионы колонок можно рассматривать как участки документа, содержащие текст, который по форме напоминает колонку. В документе может присутствовать одна или несколько колонок текста. Неколоночные регионы в некоторых вариантах осуществления могут представлять собой участки документа, содержащие картинки, рамки с текстом, заголовки или таблицы, в дальнейшем они могут упоминаться как «врезки».

[0027] Врезка может представлять собой регион документа, который содержит текст, рамку с текстом, заголовок, таблицу и/или рисунок. В некоторых вариантах осуществления главным признаком врезки является то, что она частично или полностью врезается в колонку основного текста. В дальнейшем врезка, которая частично врезается в колонку, может называться «частичной» врезкой. Кроме того, врезка, которая полностью врезается в колонку, далее может называться «полной» врезкой. Отметим, что основной текст колонки может располагаться либо слева, либо справа от частичной врезки. Таким образом, возможны два типа частичных врезок: правая частичная врезка и левая частичная врезка.

[0028] На Фиг. 7 показан пример изображения документа, содержащего врезки. Изображение документа на Фиг. 7 включает в себя врезку 71, первую колонку 72, среднюю колонку 73, третью колонку 74, полные врезки 75 и границу средней колонки 76. Сложная врезка 71 на Фиг. 7 является врезкой для каждой колонки. Для первой колонки врезка 71 является правой частичной (прямоугольной) врезкой. Для средней колонки врезка 71 является полной врезкой. Для третьей колонки 74 врезка 71 является частичной левой (не прямоугольной) врезкой.

[0029] В некоторых вариантах осуществления врезки могут располагаться в верхней, нижней или средней части колонки текста. Для верхней врезки основной текст может располагаться ниже врезки. Таким образом, эта врезка примыкает к верхней части контекста. Для нижней врезки основной текст может быть расположен выше врезки, причем врезка может примыкать к нижней части контекста. В случае средней врезки текст может располагаться выше, ниже и/или с одной стороны (справа или слева) в зависимости от того, является ли эта врезка правой врезкой или левой врезкой. Например, врезка «В МИРЕ ОЖИВШИХ ЗВУКОВ» (75) на Фиг. 7 является верхней (полной) врезкой для всех колонок. В некоторых вариантах осуществления средние полные врезки могут разделять колонку на две несвязанные части. В одном варианте осуществления заголовок можно рассматривать как особый случай верхней полной врезки.

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

[0031] В блоке 105 выявляются объекты на этом изображении документа. В некоторых вариантах осуществления для того, чтобы найти границы между регионами, первоначально в документе 105 могут быть определены объекты. Объектами в документе могут быть, например, фрагменты строк текста, строки, фрагменты рисунков, рисунки, слова, разделители и т.д. На Фиг. 8 показаны примеры текстовых объектов 82 на изображении документа. На Фиг. 8 показаны фрагменты строк текста, которые могут быть объектами 82. Границы объектов 84 обозначены черной линией.

[0032] В настоящем раскрытии изобретения изображение документа сегментируется на регионы с использованием диаграммы Вороного для областей (которая ниже именуется «»AVD» от англ. area Voronoi diagram), а выявленные объекты используются в качестве областей Вороного. Возвращаясь к Фиг. 1, на этапе 110 построена AVD. Диаграмма Вороного для областей может быть построена любым удобным способом. Для целей сегментации приближенная диаграмма Вороного для областей может быть построена, используя, например, способ, показанный на Фиг. 2.

[0033] На Фиг. 2 показана блок-схема последовательности операций способа построения приближенной диаграммы Вороного для областей. В блоке 200 получается изображение с выделенными объектами. В блоке 210 каждый объект сначала аппроксимируется с помощью набора точек 210. В некоторых вариантах осуществления набор точек может называться «аппроксимирующими точками». На Фиг. 8 показаны примеры объектов 82 и один из способов их аппроксимации с помощью набора точек 86. После того как аппроксимирующие точки были определены для всех объектов, в блоке 220 для них строится диаграмма Вороного 220. В построенной диаграмме Вороного множество точек, каждая из которых располагается к заданной аппроксимирующей точке ближе, чем ко всем остальным, может называться ячейкой Вороного для аппроксимирующей точки. В блоке 230 исключаются границы между ячейками Вороного, принадлежащими одним и тем же объектам (230). В блоке 240 полученная диаграмма представляет собой приближенную диаграмму Вороного для областей. Следует отметить, что AVD содержит полезную дополнительную информацию, связанную с топологией объектов. Например, ее можно использовать для уточнения границ между объектами. В некоторых вариантах осуществления для этого используется специальная структура данных, называемая «разделяющий граф».

[0034] На Фиг. 3 показана блок-схема способа осуществления для построения разделяющего графа (120 на Фиг. 1). В блоке 300 строится диаграмма Вороного для областей. В некоторых вариантах реализации ребрами разделяющего графа означаются непрерывные участки границ между ячейками Вороного, например ячейками Вороного в диаграмме Вороного для областей. Ребра в разделяющем графе могут начинаться и заканчиваться в точках разветвления соответствующих линий границ. Точкой ветвления может быть точка, в которой встречаются три или более ячейки Вороного. В некоторых вариантах ребро снабжено дополнительной информацией, например, ребро может указывать пару объектов, разделенных соответствующей линией границы.

[0035] На Фиг. 9 схематично иллюстрируется первый пример разделяющего графа. На Фиг. 9 показано ребро Eab 91, которое разделяет соседние ячейки А 92 и В 93. Вершинами в разделяющем графе могут быть точки ветвления 102 и концевые точки 104 на AVD, как схематически показано на Фиг. 10, которая иллюстрирует второй пример разделяющего графа. В некоторых вариантах осуществления вершины, соответствующие концевым точкам, могут назваться «концевыми вершинами». Концевые вершины могут быть вершинами, расположенными вдоль границы графа. Из концевой вершины может выходить только одно ребро. В некоторых вариантах осуществления, если объект имеет более или менее случайную форму, то ровно 3 ребра будет исходить из каждой неконцевой вершины. Это следует из свойств диаграммы Вороного.

[0036] Возвращаясь к Фиг. 3, в блоках 310 и 320 при построении разделяющего графа могут использоваться точки ветвления и концевые точки на AVD. В некоторых вариантах осуществления каждой из этих точек соответствует вершина графа 310, а каждому отрезку, разделяющему ячейки Вороного, соответствует ребро графа 320. В блоке 330 полученный граф может быть сведен к минимальному гомеоморфному графу, то есть узлы степени 2 (вершины, имеющие всего два выходящих ребра). В некоторых вариантах осуществления для того, чтобы привести полученный граф к минимальному графу, вершины, из которых выходит только два ребра, могут быть удалены, а два соответствующих ребра могут быть объединены в одно ребро 330. В одном варианте осуществления ребра объединяются только тогда, когда они разделяют одну и ту же пару объектов. Полученный граф является разделяющим графом 340.

[0037] Теперь обратимся к Фиг. 1, где в блоке 120 строится граф смежности. В некоторых вариантах осуществления граф смежности объектов может являться двойственным представлением AVD. В отличие от разделяющего графа, вершины графа смежности могут иметь четко определенный физический смысл и соответствовать объектам на изображении документа. Ребра графа смежности соединяют смежные объекты, в то время как ребра разделяющего графа разделяют их. В некоторых вариантах осуществления разделяющий граф может использоваться для построения графа смежности. В одном из вариантов осуществления процедура построения графа смежности с использованием разделяющего графа может включать выявление вершин графа смежности. В некоторых вариантах осуществления вершины графа смежности могут соответствовать объектам, найденным на изображении документа, и две вершины графа смежности могут быть соединены ребром, если объекты, соответствующие этим вершинам, разделены по меньшей мере одним ребром в разделяющем графе (дополнительная информация ребра разделяющего графа указывает объекты, которые данное ребро разделяет). В некоторых вариантах осуществления невозможно однозначно восстановить разделяющий граф из графа смежности объектов. Это связано с тем фактом, что из графа смежности не всегда можно узнать, должны ли два ребра в разделяющем графе быть смежными (то есть иметь общую вершину) или нет.

[0038] Снова возвращаясь к Фиг. 1, в блоке 140 производится поиск путей. Поиск путей может производиться после построения разделяющего графа и графа смежности, причем поиск путей осуществляется в разделяющем графе.

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

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

[0041] В одном варианте осуществления для корректного разделения документа на регионы определяется оптимальный путь. Для этого возвратимся к Фиг. 4, в блоке 400 ребра разделяющего графа взвешиваются. В некоторых вариантах осуществления ребра разделяющего графа взвешиваются на основе анализа совместимости объектов, между которыми проходят ребра разделяющего графа. Такой анализ может также включать сравнение характеристик выделенных объектов на изображении документа. Например, такой анализ может включать, без ограничений, сравнение текстового качества объектов, положений базовых линий, высоты и т.п. В некоторых вариантах осуществления на основе полученных результатов ребру, разделяющему рассматриваемые объекты, может быть назначен вес или штраф. В одном варианте осуществления штраф (вес) может иметь некоторое числовое значение. В некоторых вариантах осуществления значения весов могут быть основаны на анализе взаимных и/или похожих характеристик по меньшей мере одной пары выявленных объектов. Например, если два объекта очень похожи на куски строки, то ребру, разделяющему эти два объекта, может быть назначен большой штраф. В других вариантах осуществления, если типы двух объектов несовместимы (например, текстовый объект и картинка), то ребрам между этими двумя объектами может быть назначен меньший штраф.

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

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

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

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

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

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

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

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

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

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

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

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