Способ разделения текстов и иллюстраций в изображениях документов с использованием дескриптора спектра документа и двухуровневой кластеризации

Способ разделения текстов и иллюстраций в изображениях документов с использованием дескриптора спектра документа и двухуровневой кластеризации

Иллюстрации

Показать все

Реферат

Область техники

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

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

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

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

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

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

Описание связанных документов уровня техники

[0006] Одно из самых популярных семейств способов разделения текст или не текст основано на извлечении простых признаков из ROI, а затем классификации этих признаков с помощью нескольких продуманных, построенных вручную эвристик, направленных на отделение текстовых областей от нетекстовых областей. Типичные признаки, используемые в таких подходах, основаны на компонентах связности, статистике по длинам серий, взаимной корреляции между линиями сканирования, проекционных профилях или распределении пикселей черного цвета. Одним экземпляром такого семейства подходов является патент США US 6,937,766, опубликованный 30 августа 2005 года, в котором текст извлекают из видеопоследовательности (см. реферат патента `766). Такие подходы являются быстрыми и эффективными для такого материала, в котором иллюстрациями являются фотографии, картины, кадры видеопоследовательности или другие виды красочных изображений, которые существенно отличаются от текста по своей структуре. Однако, для схематических чертежей, особенно текстовых блок-схем, электрических схем и подобного материала, такие подходы часто демонстрируют гораздо более худшую точность. Одним из их основных недостатков является то, что их эвристики обычно выводятся из наблюдений, относящихся к иллюстрациям, принадлежащим некоторому конкретному классу (или классам), и могут плохо обобщаться для других классов, что является особенно проблематичным для документов, содержащих очень разнообразный набор классов иллюстраций (например, для иллюстраций в патентных документах), в которых некоторые из классов не полностью соответствуют таким эвристикам. В качестве примера, способы, основанные на гистограммах длин серий, могут неправильно классифицировать в качестве текстовых областей блок-схемы, содержащие большие объемы текста.

[0007] Этот недостаток решается другим семейством подходов, основанных на алгоритмах машинного обучения с учителем, применяемых либо к признакам того же типа, что и описан выше, или к данным пикселей изображения. Поскольку задача разделения текста и иллюстраций может быть сформулирована как проблема бинарной классификации, подходы этого семейства обычно используют обучение на наборе размеченных вручную данных, чтобы изучить различие между текстовыми и нетекстовыми областями. В данном семействе подходов применяется классификация основанных на форме признаков, использующая классификатор k-ближайших соседей (KNN), многослойный перцептрон (MLP) или классификатор по методу опорных векторов (SVM), использующий основанный на градиенте дескриптор T-HOG. Одним экземпляром такого семейства подходов является патент США US 7,570,816, для корректного обучения классификатора которого требуется большой набор размеченных вручную данных (см. абзац [0008] патента `816).

[0008] Такие подходы могут по-прежнему страдать от недостаточной различающей способности построенных вручную признаков, которая не может быть компенсирована классификатором. Таким образом, были разработаны более эффективные подходы в работе с данными пикселей изображения или низкоуровневыми признаками. Один заметный подход такого рода основан на методах разреженного кодирования. Например, был предложен анализ морфологическиx компонент (MCA), использующий два предварительно построенных различающих переопределенных словаря (curvelet-преобразование для графики и вейвлет-преобразование для текста).

[0009] Тем не менее, основанные на обучении с учителем алгоритмы часто являются чрезмерно медленными на больших наборах данных (что имеет место в случае, например, патентных документов, содержащих миллионы областей), и они лучше всего работают, когда в обучающем наборе данных все релевантные классы иллюстраций представлены в достаточной степени так, чтобы алгоритм обучения знал, как отличить каждый из указанных классов от текста. Такой обучающий набор данных может не быть легкодоступным для многих видов документов, например, когда классы иллюстраций настолько многочисленны и обладают очень высокой изменчивостью внутри класса, создание такого набора данных с помощью ручной разметки (маркировки областей) было бы непомерно трудоемким (см., например, абзац [0008] патента `816). Чтобы устранить необходимость в обучающем наборе размеченных вручную данных были разработаны основанные на обучении без учителя способы, в которых в частности может быть использован алгоритм k-средних для кластеризации статистических признаков, вычисляемых с использованием, например, высокочастотных вейвлет-коэффициентов или карт краев. Такие способы описаны в работах C. Liu, C. Wang и R. Dai «Text detection in images based on unsupervised classification of edge-based features» (2005 год) и J. Gallavata, R. Ewerth и B. Freisleben «Text detection in images based on unsupervised classification of high-frequency wavelet coefficients» (2004 год). Далее в этой заявке будет продемонстрированно, что алгоритм k-средних сам по себе неспособен работать с невыпуклыми, вложенными и удлиненными кластерами, а также обладает рядом недостатков в вопросе разделения текста и иллюстраций, особенно при использовании Евклидова расстояния. Вследствие этого, эти способы также не приспособлены для разделения текста и схематических чертежей, особенно текстовых блок-схем, электрических схем или подобной бизнес-графики.

[0010] Наконец, в отношении ранее разработанных способов и настоящего изобретения необходимо отметить следующую важную информацию: большинство из ранее разработанных способов сконцентрированы особенно на задаче извлечения текста, в то время как настоящее изобретение сконцентрировано на извлечении иллюстраций из изображений документов. Кроме того, большинство вышеописанных способов обычно работают над естественными сценами (фотографиями или видеопоследовательностями). Тем не менее, такой тип данных сильно отличаются по своей структуре и свойствам содержащейся в них графики от структуры и свойств иллюстраций, например, схематических чертежей, возможно также имеющих некоторый текст в своем составе, в документах, подобных патентным документам, которые находятся в центре настоящего изобретения. Также необходимо обратить внимание на то, что во многих предыдущих работах используются хорошо известные наборы данных UW-III и ICDAR 2009 для создания построенных вручную признаков или обучения классификаторов, что может отрицательно повлиять на возможности обобщения как признаков, так и классификаторов в контексте задачи настоящего изобретения, поскольку эти наборы данных содержат только небольшое подмножество классов иллюстраций, присутствующих в документах, подобных патентным документам.

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

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

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

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

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

[0015] Наконец, в этом предпочтительном варианте осуществления способа классификация каждого из извлеченных признаковых векторов в один из двух классов: текст или иллюстрация, содержит подэтапы, на которых: осуществляют аппроксимирующее ядро преобразование признаковых векторов; осуществляют кластеризацию первого уровня преобразованных признаковых векторов с использованием алгоритма мини-пакетных k-средних для получения кластеров преобразованных признаковых векторов и их центроидов; осуществляют кластеризацию второго уровня центроидов кластеров, полученных на предшествующем подэтапе, с использованием усовершенствованного алгоритма кластеризации для получения соответствующих им суперкластеров; и проверяют, больше ли число полученных суперкластеров, чем два: если нет - используют операцию логического вывода разметки (S103.4.1) для классификации каждого из этих двух суперкластеров в один из двух классов: текст или иллюстрация; или если да - используют операцию распространения разметки с частичным привлечением учителя для классификации каждого из этих более двух суперкластеров в один из двух классов: текст или иллюстрация.

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

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

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

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

[Фиг. 2] Фигура 2 иллюстрирует подэтапы этапа сегментирования (S101) изображения страниц документов на области интереса согласно предпочтительному варианту осуществления настоящего изобретения.

[Фиг. 3] Фигура 3 иллюстрирует подэтапы этапа извлечения (S102) признакового вектора для каждой области интереса согласно предпочтительному варианту осуществления настоящего изобретения.

[Фиг. 4] Фигура 4 иллюстрируют подэтапы этапа классифицирования (S103) каждого из извлеченных признаковых векторов в один из двух классов: текст или иллюстрация согласно предпочтительному варианту осуществления настоящего изобретения.

[Фиг. 5] Фигура 5(а) иллюстрирует оригинальную страницу патента с пятью иллюстрациями; Фигура 5(б) иллюстрирует результат применения алгоритма RLSO к странице, показанной на фигуре 5(а): заполненные пиксели фона окрашены серым цветом, компоненты связности выделены четырехугольными ограничительными рамками.

[Фиг. 6] Фигура 6 иллюстрирует области интереса, извлекаемые посредством алгоритма RLSO из изображения страницы патента, в содержимом которой имеются как текст, так и иллюстрации.

[Фиг. 7] Фигура 7 иллюстрирует пары ближайших соседних центроидов компонент связности типичной ROI иллюстрации.

[Фиг. 8] Фигура 8 иллюстрирует пары ближайших соседних центроидов компонент связности типичной ROI текста.

[Фиг. 9] Фигуры 9(а)-(б) иллюстрируют используемые в настоящем изобретении Docstrum-дескрипторы: Docstrum-дескриптор (гистограмма слева - Фигура 9(а)) ROI иллюстрации; Docstrum-дескриптор (гистограмма справа - Фигура 9(б)) ROI текста. Данные Docstrum-дескрипторы вычислялись для областей интереса (ROI), размер которых составлял 500×500 пикселей, с использованием 64 бинов углов и 20 бинов расстояния.

[Фиг. 10] Фигуры 10(а)-(б) иллюстрируют используемые в настоящем изобретении Docstrum-дескрипторы: Docstrum-дескриптор (гистограмма слева - Фигура 10(а)) ROI иллюстрации и Docstrum-дескриптор (гистограмма справа - Фигура 10(б)) ROI текста. Данные Docstrum-дескрипторы вычислялись для областей интереса (ROI), размер которых составлял 300×300 пикселей, с использованием 16 бинов углов и 20 бинов расстояния.

[Фиг. 11] Фигура 11 иллюстрирует подэтапы этапа классифицирования (S103) каждого из извлеченных признаковых векторов в один из двух классов: текст или иллюстрация, с добавленной ветвью оценки качества классификации.

[Фиг. 12] Фигура 12 иллюстрирует архитектуру сиамской нейронной сети, используемой для обучения отображения признаков для аппроксимации ядра Жаккара.

[Фиг. 13] Фигура 13 иллюстрирует примеры кластеров, получаемых в результате выполнения подэтапа (S103.2) способа, на котором осуществляют кластеризацию первого уровня преобразованных признаковых векторов с использованием алгоритма мини-пакетных k-средних.

[Фиг. 14] Фигуры 14(а)-(б) иллюстрируют кривые точность - полнота для варианта с аппроксимированным ядром раскрытого способа. Фигура 14(а): кривые точность - полнота для разных алгоритмов кластеризации второго уровня. Фигура 14(б): кривые точность - полнота для разных аппроксимированных ядер. Маркеры указывают лучшие точки F₁.

[Фиг. 15] Фигуры 15(а)-(б) иллюстрируют кривые точность - полнота для варианта с точным ядром раскрытого способа. Фигура 15(а): кривые точность - полнота для разных алгоритмов кластеризации второго уровня. Фигура 15(б): кривые точность - полнота для разных ядер. Маркеры указывают лучшие точки F₁.

[Фиг. 16] Фигура 16 иллюстрирует точечную диаграмму компонент t-SNE, вычисленных для Docstrum-признаковых векторов ROI, классифицированных как ROI текста и ROI иллюстраций согласно раскрытому способу.

Подробное описание вариантов осуществления изобретения

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

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

[0020] Поскольку разделение текста и иллюстраций обычно используется в качестве стадии предварительной обработки для подготовки данных для последующих гораздо более сложных стадии, специалист в данной области поймет, что в идеале такой способ разделения должен быть относительно быстрым и легким (по сравнению с последующими стадиями, которыми, например, могут быть OCR или механизм индексирования и поиска изображений). Это требование подразумевает использование легкого алгоритма извлечения глобального дескриптора (а не более дорогостоящую агрегацию локальных дескрипторов, таких как VLAD или Fisher Vector для SIFT-дескрипторов), создающего низкоразмерные признаковые векторы. В случае черно-белых (бинарных) изображений документов (например, патентов) также вполне логично использовать алгоритм извлечения дескриптора, специально предназначенный для и приспособленный под изображения документов, содержащих области текста и иллюстраций, возможно, по меньшей мере частично, также наполненных текстом.

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

[0022] Наконец, для того, чтобы последующая обработка областей текста или иллюстраций, была полной и эффективной, необходим алгоритм разделения текста и иллюстраций, который обеспечивает высокий уровень полноты (recall) и хорошую точность (precision). Поскольку основной акцент в настоящем изобретении делается на выделение иллюстраций из изображений документов для их последующей индексации и использования в поиске, автор настоящего изобретения установил минимальные уровни для показателя полноты ROI иллюстраций на ~ 90%, а для показателя точности на ~ 75%, что означает, что теряется не более 10% иллюстраций, содержащихся во всех обрабатываемых заявленным способом изображениях документов, и допустимым является не более 25% насыщенности текстом в некотором выбранном наборе ROI. Поддержание как показателя полноты, так и показателя точности, по меньшей мере, на таком высоком уровне имеет решающее значение для задачи поиска иллюстраций, поскольку низкий показатель полноты приведет в результате к тому, что слишком много иллюстраций не будет проиндексировано, тогда как низкий показатель точности значительно увеличит избыточные вычисления, выполненные для текстовых ROI. Далее приведены детали способа разделения текстов и иллюстраций в изображениях страниц документов в соответствии с настоящим изобретением.

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

[0024] На этапе (S100) способа получают изображения страниц документов. Данный этап может быть реализован любым известным из уровня техники способом.

[0025] На этапе (S101) способа сегментируют изображения страниц документов на области интереса (ROI). Поскольку страницы патентного документа представляют собой черно-белые (бинарные) изображения документов, которые обычно используют Манхэттенскую схему размещения текста и иллюстраций, в предпочтительном варианте осуществления данного этапа может быть использован алгоритм сегментации, использующий сглаживание по длинам серий с операцией логическое ИЛИ (RLSO). Подходящий для настоящего изобретения алгоритм RLSO может быть вариантом алгоритма сглаживания по длинам серий (RLSA). Детали подэтапов данного этапа ниже будут подробно описаны и проиллюстрированы со ссылкой на фигуры 2, 5(a), 5(б), 6.

[0026] На этапе (S102) способа извлекают признаковый вектор для каждой области интереса (ROI). Для ROI изображений, извлеченных с помощью упрощенного алгоритма RLSO, были опробованы несколько глобальных дескрипторов изображений, предназначенных для черно-белых изображений документов: моменты Ху (Hu), признаки Харалика (Haralick), дескриптор контекста формы (SCD), гистограмма длин серий (RLH), локальные бинарные шаблоны (LBP), адаптивная иерархическая гистограмма плотности (AHDH) и дескриптор спектра документа (далее упоминаемый как Docstrum-дескриптор). В результате было определено, что наиболее отчетливое и стойкое различие между признаковыми векторами для областей текста и иллюстраций из анализируемого набора данных обеспечивается Docstrum-дескриптором. Этот результат вполне оправдан, поскольку моменты Ху, признаки Харалика и LBP разрабатывались в основном для классификации текстур, SCD направлен на сопоставление форм, а RLH и AHDH хорошо подходят для поиска документов, тогда как Docstrum-дескриптор предназначен для анализа разметки и компоновки страницы в содержащих только текст документах. Таким образом, Docstrum-дескриптор может быть использован на данном этапе (S102) для извлечения признакового вектора для каждой ROI согласно предпочтительному варианту осуществления настоящего изобретения. Однако, специалисту будет понятно, что в других вариантах осуществления данного этапа (S102) любой из вышеперечисленных глобальных дескрипторов может быть использован вместо или вместе с Docstrum-дескриптором для извлечения признакового вектора, хоть и не столь эффективно. Использование Docstrum-дескриптора приводит в результате к тому, что для нетекстовых областей этап (S102) извлекает более ʺхаотичныеʺ признаковые векторы, делая их легко отличимыми от более «регулярных» признаковых векторов, извлекаемых для текстовых областей. Детали подэтапов данного этапа ниже будут подробно описаны и проиллюстрированы со ссылкой на фигуры 3, 7, 8, 9(а), 9(б), 10(а), 10(б).

[0027] Фигура 2 иллюстрирует подэтапы этапа сегментирования (S101) изображения страниц документов на области интереса согласно предпочтительному варианту осуществления настоящего изобретения.

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

[0029] На подэтапе (S101.2) способа заполняют цветом переднего плана вертикальные серии пикселей фона, длины которых ниже некоторого предварительно установленного порогового значения. На подэтапе (S101.3) способа применяют операцию логическое ИЛИ к изображениям, полученным в результате упомянутых заполнений. На подэтапе (S101.4) способа извлекают компоненты связности из изображения, полученного в результате применения операции логическое ИЛИ.

[0030] На подэтапе (S101.5) способа выбирают ограничительные рамки полученных в результате компонент связности в качестве областей интереса. Слишком маленькие ROI, площадь которых (в пикселях) менее 0,1% от всей площади изображения, но без ограничения упомянутым значением процента, могут быть отброшены.

[0031] Используемый в предпочтительном варианте осуществления данных подэтапов алгоритм RLSO отличается от известного алгоритма RLSA тем, что первый использует логическую операцию ИЛИ между сглаженными по горизонтали и по вертикали изображениями вместо логической операции И. Таким образом, используемая в предпочтительном варианте осуществления настоящего изобретения модификация RLSO еще больше упрощает данные подэтапы, заменяя сложную оценку пороговых значений сглаживания вычислением 90-го и 80-го процентилей длин серий пикселей фона, соответственно, для горизонтального и вертикального сглаживания. Однако, специалист поймет, что в других вариантах осуществления вместо вышеуказанный процентилей могут быть использованы другие процентили длин серий пикселей фона, соответственно, для горизонтального и вертикального сглаживания, без выхода за рамки настоящего раскрытия.

[0032] Пример применения алгоритма RLSO к иллюстрациям патента проиллюстрирован на фигурах 5(а), 5(б), а на фигуре 6 проиллюстрированы области интереса (ROI), извлеченные из изображения страницы патента, в содержимом которой имеются как текст, так и иллюстрации. В целях иллюстрации на фигуре 5(б) позицией 501 показана компонента связности, а позицией 502 ограничительная рамка. В целях иллюстрации на фигуре 6 позицией 601 показана область интереса.

[0033] Фигура 3 иллюстрирует подэтапы этапа извлечения (S102) признакового вектора для каждой области интереса согласно предпочтительному варианту осуществления настоящего изобретения.

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

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

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

[0037] На подэтапе (S102.5) способа переформировывают двумерную гистограмму в Docstrum - признаковый вектор. На данном подэтапе двумерная гистограмма может быть дополнительно нормализована так, чтобы ее L₁-норма была равна 1. Docstrum - признаковый вектор, получаемый из двумерной гистограммы путем разворачивания ее в вектор на данном подэтапе и, в одном варианте осуществления, нормировки по L₁-норме может альтернативно именоваться Docstrum-дескриптором в целях кратности и ясности.

[0038] Важно отметить, что изменение размера области интереса на подэтапе (S102.1) способа и нормализация расстояний при построении двумерной гистограммы на подэтапе (S102.4) способа отличает используемую в настоящем изобретении версию Docstrum-дескриптора от известного оригинального алгоритма, описанного в работе L. O'Gorman, «The Document Spectrum for Page Layout Analysis» IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 15, no. 11, pp. 1162-1173, 1993. Эти подэтапы используются в предпочтительном варианте осуществления заявленного способа для следующего: изменение размера ROI используется, чтобы уменьшить вычислительную сложность способа (поскольку большинство ROI имеют размеры намного больше, чем 500×500 пикселей), нормализация расстояний используется, чтобы сделать дескриптор инвариантным к масштабированию. Кроме того, сохранение соотношения сторон ROI при изменении ее размера на подэтапе (S102.1) способа используется для предотвращения перекоса распределения расстояний и углов вследствие неизотропного изменения размера ROI. Целевой размер ROI (в предпочтительном варианте осуществления - 500×500 пикселей) для использования на подэтапе изменения размера может быть выбран как компромисс между вычислительной сложностью дескриптора и сохранением деталей иллюстраций. Также может быть использован размер ROI 300×300 или любой размер ROI NxN, выбираемый из диапазона размеров ROI от 300×300 пикселей до 500×500 пикселей. Для того, чтобы построить двумерную гистограмму расстояний и углов в предпочтительном варианте осуществления способа используют 64 бина угла и 20 бинов расстояния, что приводит в результате к 1280-мерному признаковому вектору. «Бин» может быть определен как интервал гистограммы. Эти параметры могут быть выбраны как компромисс между размерностью дескриптора и его различающей способностью для различения текста и иллюстраций в изображениях документов.

[0039] Примеры пар ближайших соседних центроидов компонент связности для типичной ROI иллюстрации и типичной ROI текста показаны, соответственно, на фигурах 7 и 8. В целях иллюстрации на фигуре 7 позицией 701 показана пара ближайших соседних центроидов, а позициями 702 показаны соответствующие ей компоненты связности. В целях иллюстрации на фигуре 8 позицией 801 показана пара ближайших соседних центроидов, а позициями 802 показаны соответствующие ей компоненты связности.

[0040] Docstrum-дескрипторы (изображенные как одномерные гистограммы), вычисленные с использованием вышеуказанных предпочтительных параметров для тех же самых типичной ROI иллюстрации и типичной ROI текста с фигур 7 и 8 показаны, соответственно, на фигурах 9(а) и 9(б). Как можно видеть на фигурах 9(а) и 9(б), гистограмма для типичной ROI текста демонстрирует регулярно-разнесенные пики, в отличие от гистограммы для типичной ROI иллюстрации, которая выглядит намного более хаотичной.

[0041] Кроме того, в других вариантах осуществления настоящего изобретения размерность дескриптора может быть уменьшена (и, следовательно, вычислительная сложность вычисления и обработки дескриптора может быть уменьшена) путем дальнейшего уменьшения размера ROI и размерности гистограммы в бинах. Например, в варианте осуществления настоящего изобретения, в котором используют 16 бинов углов и 20 бинов расстояния, могут быть получены 320-мерные признаковые векторы. Docstrum-дескрипторы, использующие такие параметры и вычисленные для тех же самых типичных ROI, размер которых составляет 300×300 пикселей, проиллюстрированы на фигурах 10(а) и 10(б). Несмотря на то, что различающая способность таких дескрипторов с такими альтернативными параметрами видится ухудшенной (т.е. гистограмма для ROI текста имеет менее регулярную структуру), гистограммы по-прежнему являются достаточно подходящими для задачи отделения текста от иллюстраций согласно настоящему изобретению.

[0042] Фигура 4 иллюстрируют подэтапы этапа классифицирования (S103) каждого из извлеченных признаковых векторов в один из двух классов: текст или иллюстрация согласно предпочтительному варианту осуществления настоящего изобретения. В общем, в предпочтительном варианте осуществления раскрытого способа этот этап (S103) осуществляют следующим образом: сначала, признаковые векторы дескриптора преобразуют с помощью аппроксимирующего ядро (kernel, скалярное произведение) отображения признаков, затем осуществляют кластеризацию полученных в результате преобразованных признаковых векторов, используя алгоритм мини-пакетных k-средних, затем осуществляют кластеризацию центроидов кластеров, полученных в результате выполнения предшествующего подэтапа, используя один из возможных более сложных алгоритмов кластеризации. Полученные в результате кластеры центроидов, по сути, агрегируют кластеры, соответствующие таким центроидам (выходные данные с кластеризации 1-го уровня), в суперкластер (который может именоваться как «больший кластер»). Наконец, полученные суперкластеры классифицируют посредством либо операции логического вывода разметки (Zero-Shot Label Inference), либо операции распространения разметки с частичным привлечением учителя (Semi-Supervised Label Propagation), которая использует подмножество размеченных признаковых векторов.

[0043] Для оценки качества классификации в настоящем изобретении к блок-схеме с фигуры 4 может быть добавлена параллельная ветвь оценки качества классификации как показано на фигуре 11. Более подробное описание этой ветви оценки качества классификации и результатов этой оценки приведено ниже со ссылкой на фигуру 11.

[0044] Ниже по тексту приводится подробное описание вариантов осуществления подэтапов этапа (S103).

[0045] На подэтапе (S103.1) способа осуществляют аппроксимирующее ядро преобразование признаковых векторов. Под «ядром» здесь понимается обобщенное действительное скалярное произведение, т.е. действительнозначная функция, определенная на парах признаковых векторов, являющаяся симметричной и положительно-определенной, но не обязательно линейной. Этот подэтап хоть и не является обязательным, но отличает способ классификации дескрипторов согласно настоящему изобретению от способов классификации дескрипторов, известных из уровня техники. Поскольку Docstrum-дескриптор представляет собой гистограмму, Евклидовы расстояния (или скалярные произведения), используемые на последующих по