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

Группа изобретений относится к технологиям обработки изображений, в частности к анализу документов со сложной пространственной разметкой. Техническим результатом является расширение арсенала технических средств, направленных на анализ логической структуры изображения документа. Предложен способ анализа логической структуры изображения документа. Способ содержит этап, на котором осуществляют выявление объектов на изображении документа. Далее, согласно способу, осуществляют построение разделяющего графа выявленных объектов на основе построения диаграммы для областей на выявленных объектах на изображении документа. А также осуществляют обнаружение по меньшей мере одного оптимального пути в разделяющем графе посредством присвоения значений весов ребрам разделяющего графа для определения местонахождения регионов на изображении документа. 3 н. и 23 з.п. ф-лы, 11 ил.

 

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

[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 в межколоночном графе может проводиться поиск всех компонент связности. Компонента связности может относиться к множеству вершин графа такому, что для любых двух вершин из этого множества существует путь от одной вершины к другой, и не существует пути от вершины из этого множества к вершине, которая не включена в это множество. Затем в блоке 460 межколоночные пути могут быть сопоставлены с найденными компонентами связности. В некоторых вариантах осуществления межколоночные пути могут быть сопоставлены с компонентами связности, используя алгоритм Дейкстры.

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

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

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

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

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

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

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

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

[0062] На Фиг. 5 показана блок-схема последовательности операций способа для разделения документа на регионы. Построенная система путей недостаточна для того, чтобы понять логическую структуру документа и получить результат сегментации документа, поэтому необходимо выполнить дополнительные этапы, чтобы выявить регионы в документе. В некоторых вариантах осуществления после обнаружения системы путей в разделяющем графе объекты могут быть приписаны тем регионам, которым они соответствуют. В одном варианте осуществления для этой цели может быть использован граф смежности 120. Те ребра, которые соответствуют построенной системе путей, удаляются из графа смежности. Каждое ребро разделяющего графа хранит информацию об объектах, которые оно разделяет (то есть об объектах, расположенных по обе стороны от этого ребра). Для каждого ребра путей 480 может быть извлечена информация об объектах, разделяемых этим ребром, при этом соответствующее ребро графа смежности, которое соединяет эти объекты, может быть удалено (510). Затем в блоке 520 можно использовать любой известный метод для выявления компонент связности в полученном графе смежности с удаленными соответствующими ребрами (520). Компоненты связности соответствуют искомым регионам и содержат именно те объекты, которые принадлежат этим регионам. В блоке 530 итоговые регионы выявляются на изображении документа (530) и отображаются в результатах сегментации. В итоге, изображение документа может быть разделено на регионы (160).

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

[0064] На Фиг. 11 показана система 1100, которая способна определить логическую структуру документа, используя описанные выше методы, в соответствии с некоторыми вариантами осуществления изобретения. Система 1100 обычно включает в себя по меньшей мере один процессор 1102, соединенный с памятью 1104. Процессор 1102 может представлять собой один или несколько процессоров (например, микропроцессоров), а память 1104 может представлять собой оперативные запоминающие устройства (ОЗУ), содержащие главное устройство хранения 1100 и/или любые дополнительные уровни памяти, например, кэш-память, энергонезависимые или резервные запоминающие устройства (например, программируемую или флэш-память), постоянные запоминающие устройства и т.д. Кроме того, память 1104 может включать запоминающее устройство, физически расположенное в какой-либо другой части системы 1100 (например, любую кэш-память в процессоре 1102), а также любое запоминающее устройство, используемое в качестве виртуальной памяти (например, запись в запоминающем устройстве 1110).

[0065] В некоторых вариантах осуществления система 1100 имеет несколько входов и выходов для внешнего обмена информацией. Система 1100 может включать в себя одно или несколько устройств пользовательских ввода 1006 (например, клавиатуру, мышь, сканер и т.д.), а также дисплей 1108 (например, панель с жидкокристаллическим дисплеем (ЖКД)) для взаимодействия с пользователем или оператором. Для дополнительного хранения оборудование системы 1100 может также включать в себя одно или несколько съемных запоминающих устройств 1110, например, накопитель на дискете или другом съемном диске, накопитель на жестком диске, запоминающее устройство с прямым доступом (DASD), привод на оптическом диске (например, накопитель на компакт-диске (CD), накопитель на универсальном цифровом диске формата DVD и т.д.) и/или накопитель на магнитной ленте и пр. Кроме того, система 1100 может включать в себя интерфейс с одной или несколькими сетями 1112 (например, с локальной сетью (LAN), глобальной сетью (WAN), беспроводной сетью, и/или сетью Интернет и др.) для обеспечения обмена информацией с другими компьютерами, подключенными к этим сетям. Следует учитывать, что система 1100 обычно включает в себя соответствующие аналоговые и/или цифровые интерфейсы между процессором 1102 и каждым из компонентов 1104, 1106, 1108 и 1112, что хорошо известно специалистам в этой области.

[0066] Система 1100 работает под управлением операционной системы 1114, она выполняет различные программные приложения, компоненты, программы, объекты, модули и т.д., которые помечены в совокупности ссылкой номер 1116 для осуществления описанных выше способов исправления.

[0067] В целом процедуры, выполняемые для вариантов осуществления изобретения, могут быть использованы как часть операционной системы или как конкретное приложение, компонента программы, объект, модуль или последовательность команд, которые называются «компьютерными программами». Как правило, компьютерная программа содержит одну или большее число команд, записанных в разное время в различных запоминающих устройствах и системах хранения компьютера, которые после считывания и выполнения одним или несколькими процессорами компьютера заставляют компьютер производить операции, необходимые для выполнения элементов, включая различные аспекты изобретения. Более того, хотя это изобретение было описано в контексте полностью работоспособных компьютеров и компьютерных систем, специалистам в данной области техники будет понятно, что различные варианты осуществления изобретения могут распространяться в виде программного продукта в различных формах, и что это изобретение применимо в равной степени независимо от конкретного типа устройства или машиночитаемого носителя, используемых для фактического осуществления распространения. Примеры машиночитаемых носителей включают, без ограничений, следующие типы носителей с возможностью записи: энергонезависимые и энергозависимые устройства памяти, гибкие диски и другие съемные диски, жесткие диски, оптические диски (например, постоянное запоминающее устройство на компакт-диске (CD ROM), универсальный цифровой диск формата DVD и т.д.), и носители с возможностью передачи данных, такие как цифровые и аналоговые каналы связи. Машиночитаемые носители, включенные в настоящее раскрытие изобретения, включают в себя только постоянные среды (то есть они не включают в себя кратковременные сигналы в пространстве).

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

1. Способ анализа логической структуры изображения документа, включающий:

выявление объектов на изображении документа;

построение разделяющего графа выявленных объектов на основе построения диаграммы для областей на выявленных объектах на изображении документа;

обнаружение по меньшей мере одного оптимального пути в разделяющем графе посредством присвоения значений весов ребрам разделяющего графа для определения местонахождения регионов на изображении документа;

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

2. Способ по п.у 1, дополнительно содержащий построение графа смежности на основе разделяющего графа, при этом построение графа смежности включает в себя:

назначение вершин графа, соответствующих выявленным объектам;

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

соединение каждой пары смежных объектов ребром графа смежности.

3. Способ по п. 1, отличающийся тем, что построение разделяющего графа дополнительно содержит:

выявление вершин графа и ребер графа в диаграмме для областей, а также

создание минимального графа относительно выявленных вершин графа и ребер графа.

4. Способ по п. 1, отличающийся тем, что значения весов, присвоенные ребрам разделяющего графа, основаны на анализе взаимных характеристик по меньшей мере одной пары выявленных объектов.

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

6. Способ по п. 1, отличающийся тем, что обнаружение по меньшей мере одного оптимального пути включает:

построение по меньшей мере одного подграфа для разделяющего графа;

выявление компонент связности в подграфе;

построение по меньшей мере одного пути относительно выявленных компонент связности и

фильтрацию по меньшей мере одного пути.

7. Способ по п. 1, отличающийся тем, что обнаружение оптимального пути дополнительно содержит исправление по меньшей мере одного оптимального пути путем добавления одного или нескольких ребер или одной или нескольких частей пути, являющихся кандидатами на включение в путь, с небольшим весом и/или штрафом.

8. Способ по п. 2, отличающийся тем, что разделение изображения документа на регионы дополнительно содержит:

удаление по меньшей мере одного ребра графа из графа смежности,

соответствующего по меньшей мере одному оптимальному пути;

выявление компонент связности в графе смежности;

построение регионов, соответствующих компонентам связности в графе смежности; и

разделение изображения документа на построенные регионы.

9. Система анализа логической структуры изображения документа, включающая:

память, сконфигурированную для хранения команд, исполняемых процессором;

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

выявлять объекты на изображении документа;

построить разделяющий граф выявленных объектов на изображении документа;

обнаружить по меньшей мере один оптимальный путь в разделяющем графе для определения местонахождения регионов на изображении документа и

разделить изображение документа на регионы по меньшей мере частично на основе обнаруженного оптимального пути.

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

11. Система по п. 9, отличающаяся тем, что процессор дополнительно имеет возможность:

построить граф смежности на основе разделяющего графа, отличающийся тем, что для построения графа смежности процессор дополнительно имеет возможность:

назначать вершины графа, соответствующие выявленным объектам;

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

соединять каждую пару смежных объектов ребром графа смежности.

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

13. Система по п. 9, отличающаяся тем, что процессор дополнительно имеет возможность присваивать значения весов ребрам разделяющего графа, в котором значения весов основаны на анализе взаимных характеристик по меньшей мере одной пары выявленных объектов.

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

15. Система по п. 9, отличающаяся тем, что процессор дополнительно имеет возможность:

построить по меньшей мере один подграф для разделяющего графа;

выявить компоненты связности в подграфе;

построить по меньшей мере один путь относительно выявленных компонент связности и

отфильтровать по меньшей мере один путь.

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

17. Система по пункту 11, отличающаяся тем, что процессор дополнительно имеет возможность:

удалить по меньшей мере одно ребро графа из графа смежности, соответствующее по меньшей мере одному оптимальному пути;

выявить компоненты связности в графе смежности;

построить регионы, соответствующие компонентам связности в графе смежности; и

разделить изображение документа на построенные регионы.

18. Постоянный машиночитаемый носитель данных, в котором записаны машиночитаемые исполняемые процессором вычислительной системы команды, отличающийся тем, что эти команды включают:

команды для выявления объектов на изображении документа;

команды для построения разделяющего графа выявленных объектов на изображении документа;

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

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

19. Постоянный машиночитаемый носитель данных по п. 18, дополнительно содержащий:

команды для построения диаграммы для областей на выявленных объектах.

20. Постоянный машиночитаемый носитель данных по п. 18, дополнительно содержащий:

команды для построения графа смежности на основе разделяющего графа, отличающийся тем, что построение графа смежности дополнительно включает:

команды для назначения вершин графа, соответствующих выявленным объектам;

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

команды для соединения каждой пары смежных объектов ребром графа смежности.

21. Постоянный машиночитаемый носитель данных по п. 19, дополнительно содержащий:

команды для выявления вершин графа и ребер графа в диаграмме для областей, а также

команды для построения минимального графа на основе выявленных вершин графа и ребер графа.

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

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

24. Постоянный машиночитаемый носитель данных по п. 19, дополнительно содержащий:

команды для построения по меньшей мере одного подграфа для разделяющего графа;

команды для выявления компонент связности в подграфе;

команды для построения по меньшей мере одного пути относительно выявленных связанных компонент, а также

команды для фильтрации по меньшей мере одного пути.

25. Постоянный машиночитаемый носитель данных по п. 18, дополнительно содержащий:

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

26. Постоянный машиночитаемый носитель данных по п. 20, дополнительно содержащий:

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

команды для выявления компонент связности в графе смежности;

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

команды для разделения изображения документа на построенные регионы.