[2]Настоящая заявка относится к автоматической обработке изображений отсканированных документов и других изображений, содержащих текст, и, в частности, к способам и системам эффективного преобразования изображений символов, полученных из отсканированных документов, в кодовые комбинации соответствующих символов.
[3]ПРЕДПОСЫЛКИ СОЗДАНИЯ ИЗОБРЕТЕНИЯ
[4]Печатные, машинописные и рукописные документы на протяжении долгого времени используются для записи и хранения информации. Несмотря на современные тенденции отказа от бумажного делопроизводства, печатные документы продолжают широко использоваться в коммерческих организациях, учреждениях и домах. С развитием современных компьютерных систем создание, хранение, поиск и передача электронных документов превратились, наряду с непрекращающимся применением печатных документов, в чрезвычайно эффективный и экономически выгодный альтернативный способ записи и хранения информации. Из-за подавляющего преимущества в эффективности и экономической выгоде, обеспечиваемого современными средствами хранения и передачи электронных документов, печатные документы легко преобразуются в электронные с помощью различных способов и систем, включающих преобразование печатных документов в цифровые изображения отсканированных документов с использованием электронных оптико-механических сканирующих устройств, цифровых камер, а также других устройств и систем, и последующую автоматическую обработку изображений отсканированных документов для получения электронных документов, закодированных в соответствии с одним или более различными стандартами кодирования электронных документов. Например, в настоящее время можно использовать настольный сканер и сложные программы оптического распознавания символов (OCR), позволяющие персональному компьютеру преобразовывать печатный документ в соответствующий электронный документ, который можно просматривать и редактировать с помощью текстового редактора.
[5]Хотя современные системы OCR развились до такой степени, что позволяют автоматически преобразовывать в электронные документы сложные печатные документы, включающие в себя изображения, рамки, линии границ и другие нетекстовые элементы, а также текстовые символы множества распространенных алфавитных языков, остается нерешенной проблема преобразования печатных документов, содержащих китайские и японские иероглифы или корейские морфо-слоговые блоки.
[6]КРАТКОЕ ОПИСАНИЕ ИЗОБРЕТЕНИЯ
[7]Настоящий документ относится к способам и системам распознавания символов, соответствующих изображениям символов, полученных из изображения отсканированного документа или другого изображения, содержащего текст, включая символы, соответствующие китайским или японским иероглифам или корейским морфо-слоговым блокам, а также символам других языков, в которых применяется большое количество знаков для записи и печати. В одном варианте осуществления способы и системы, описанные в настоящем документе, осуществляют начальную обработку одного или более отсканированных изображений для идентификации подмножества общего числа символов, часто используемых в изображении или изображениях отсканированного документа. Затем один или более списков графем для языка текста упорядочиваются от наиболее часто до наименее часто встречающихся для облегчения второй стадии оптического распознавания символов, во время которой изображения символов, полученные из одного или более изображений отсканированных документов, связываются с одной или более графемами, которые наиболее вероятно соответствуют отсканированному изображению символа.
[8]КРАТКОЕ ОПИСАНИЕ РИСУНКОВ
[9]На рисунках 1А-В показан печатный документ.
[10]На рисунке 2 показаны обычный настольный сканер и персональный компьютер, которые используются вместе для преобразования печатных документов в электронные, которые можно хранить на запоминающих устройствах и/или в электронной памяти.
[11]На рисунке 3 показана работа оптических компонентов настольного сканера, изображенного на рисунке 2.
[12]На рисунке 4 представлена общая архитектурная схема разных типов компьютеров и других устройств, управляемых процессором.
[13]На рисунке 5 показано цифровое представление отсканированного документа.
[14]На рисунке 6 показан гипотетический набор символов.
[15]На рисунках 7А-С показаны различные аспекты наборов символов естественных языков.
[16]На рисунках 8А-В показаны признаки и значения признаков, рассчитанные для изображений символов.
[17]На рисунке 9 показана таблица значений признаков, рассчитанных для всех символов из набора, изображенного в качестве примера на рисунке 6.
[18]На рисунке 10 показан трехмерный график для символов из набора, изображенного в качестве примера на рисунке 6, на котором каждое из измерений представляет значения одного из трех разных признаков.
[19]На рисунках 11А-В показаны символы, содержащиеся в каждом из кластеров, представленных точками трехмерного пространства, изображенного на рисунке 10.
[20]На рисунке 12А показан отдельный признак, который можно использовать в сочетании с тремя признаками, соответствующими каждому из измерений трехмерного пространства признаков, изображенного на рисунке 10, для полного распознавания каждого из символов в кластере 8.
[21]На рисунке 12B показано значение дополнительного признака для каждого символа из кластера 8, которое следует рассматривать со ссылкой на рисунок 12А.
[22]На рисунке 13 показано небольшое изображение, содержащее текст, которое было изначально обработано системой OCR для получения сетки окон символов 1300, в каждом из которых содержится изображение символа.
[23]На рисунке 14 показан общий подход к обработке сетки окон символов, показанной на рисунке 13.
[24]На рисунке 15 показан первый подход к реализации функции «process» (1404 на рисунке 14).
[25]На рисунках 16А-В показан второй вариант осуществления функции «process» (1404 на рисунке 14).
[26]На рисунке 17 показан третий вариант осуществления функции «process», рассмотренной в предыдущем подразделе, с использованием тех же иллюстраций и условных обозначений в псевдокоде, которые использовались в предыдущем подразделе.
[27]На рисунке 18 показаны структуры данных, обеспечивающие кластеризацию и предварительную обработку в одном варианте осуществления системы OCR, включающей в себя третий вариант осуществления функции «process», описанный выше.
[28]На рисунках 19А-Н показана предварительная обработка изображения символа с использованием структур данных, рассмотренных выше со ссылкой на рисунок 18.
[30]Настоящий документ относится к способам и системам, которые эффективно сопоставляют символы языка с изображениями символов, полученными из одного или более изображений отсканированных документов или других изображений, содержащих текст. Способы и системы используют первый просмотр изображений символов для идентификации подмножества графем языка, которые наиболее вероятно присутствуют в тексте одного или более изображений отсканированных документов или других изображений, содержащих текст. Символы языка объединены в один или более кластеров связанных символов и графем, а графемы в каждом кластере сортируются по вероятности появления в одном или более изображениях, содержащих текст. На второй стадии изображения символов извлекаются из одного или более изображений, содержащих текст, а затем сопоставляются с одним или более символами языка, которые они с наибольшей вероятностью представляют. В следующем подразделе рассматриваются изображения отсканированных документов и электронные документы. Во втором подразделе рассматриваются некоторые существующие в настоящее время способы и системы оптического распознавания символов. Третий подраздел включает в себя подробное описание способов и систем, к которым относится настоящий документ.
[31]Изображения отсканированных документов и электронные документы
[32]На рисунках 1А-В показан печатный документ. На рисунке 1А показан исходный документ с текстом на японском языке. Печатный документ 100 включает в себя фотографию 102 и пять разных содержащих текст областей (104-108), включающих в себя японские иероглифы. Этот документ будет использоваться в качестве примера при рассмотрении способа и систем определения смысла, к которым относится настоящая заявка. Текст на японском языке может писаться слева направо, построчно, как пишется текст на английском языке, но также может использоваться способ написания сверху вниз в вертикальных столбцах. Например, область 107 явно содержит вертикально написанный текст, в то время как текстовый блок 108 содержит текст, написанный горизонтально. На рисунке 1B печатный документ, изображенный на рисунке 1А, показан переведенным на русский язык.
[33]Печатные документы могут быть преобразованы в цифровые изображения отсканированных документов с помощью различных средств, включающих электронные оптико-механические сканирующие устройства и цифровые камеры. На рисунке 2 показаны обычный настольный сканер и персональный компьютер, которые используются вместе для преобразования печатных документов в электронные, которые можно хранить на запоминающих устройствах и/или в электронной памяти. Настольное сканирующее устройство 202 включает в себя прозрачное стекло 204, на которое лицевой стороной вниз помещается документ 206. Запуск сканирования приводит к получению оцифрованного изображения отсканированного документа, которое можно передать на персональный компьютер (ПК) 208 для хранения на запоминающем устройстве. Программа, предназначенная для отображения отсканированного документа, может вывести оцифрованное изображение отсканированного документа на экран 210 устройства отображения ПК 212.
[34]На рисунке 3 показана работа оптических компонентов настольного сканера, изображенного на рисунке 2. Оптические компоненты этого CCD-сканера расположены под прозрачным стеклом 204. Перемещаемый фронтально источник яркого света 302 освещает часть сканируемого документа 304, свет от которой отражается вниз. Этот свет отражается от фронтально перемещаемого зеркала 306 на неподвижное зеркало 308, которое отражает излучаемый свет на массив CCD-элементов 310, генерирующих электрические сигналы пропорционально интенсивности света, поступающего на каждый из них. Цветные сканеры могут включать в себя три отдельных строки или массива CCD-элементов с красным, зеленым и синим фильтрами. Перемещаемые фронтально источник яркого света и зеркало двигаются вместе вдоль документа для получения изображения сканируемого документа. Другой тип сканера, использующего контактный датчик изображения, называется CIS-сканером. В CIS-сканере подсветка документа осуществляется перемещаемыми цветными светодиодами (LED), при этом отраженный свет светодиодов улавливается массивом фотодиодов, который перемещается вместе с цветными светодиодами.
[35]На рисунке 4 представлена общая архитектурная схема разных типов компьютеров и других устройств, управляемых процессором. Архитектурная схема высокого уровня позволяет описать современную компьютерную систему (например, ПК, изображенный на рисунке 2), в которой программы отображения отсканированного документа и программы оптического распознавания символов хранятся на запоминающих устройствах для передачи в электронную память и выполнения одним или более процессорами, что позволяет преобразовать компьютерную систему в специализированную систему оптического распознавания символов. Компьютерная система содержит один или множество центральных процессоров (ЦП) 402-405, один или более модулей электронной памяти 408, соединенных с ЦП при помощи шины подсистемы ЦП/память 410 или множества шин, первый мост 412, который соединяет шину подсистемы ЦП/память 410 с дополнительными шинами 414 и 416 или другими средствами высокоскоростного взаимодействия, включающими в себя множество высокоскоростных последовательных линий. Эти шины или последовательные линии, в свою очередь, соединяют ЦП и память со специализированными процессорами, такими как графический процессор 418, а также с одним или более дополнительными мостами 420, взаимодействующими с высокоскоростными последовательными линиями или с множеством контроллеров 422-427, например с контроллером 427, которые предоставляют доступ к различным типам запоминающих устройств 428, электронным дисплеям, устройствам ввода и другим подобным компонентам, подкомпонентам и вычислительным ресурсам.
[36]На рисунке 5 показано цифровое представление отсканированного документа. На рисунке 5 небольшой круглый фрагмент изображения 502 печатного документа 504, используемого в качестве примера, показан в увеличенном виде 506. Соответствующий фрагмент оцифрованного изображения отсканированного документа 508 также представлен на рисунке 5. Оцифрованный отсканированный документ включает в себя данные, которые представляют собой двухмерный массив значений пикселей. В представлении 508 каждая ячейка сетки под символами (например, ячейка 509) представляет собой квадратную матрицу пикселей. Небольшой фрагмент 510 сетки показан с еще большим увеличением (512 на рисунке 5), при котором отдельные пиксели представлены в виде элементов матрицы (например, элемента матрицы 514). При таком уровне увеличения края символов выглядят зазубренными, поскольку пиксель является наименьшим элементом детализации, который можно использовать для излучения света заданной яркости. В файле оцифрованного отсканированного документа каждый пиксель представлен фиксированным числом битов, при этом кодирование пикселей осуществляется последовательно. Заголовок файла содержит информацию о типе кодировки пикселей, размерах отсканированного изображения и другую информацию, позволяющую программе отображения оцифрованного отсканированного документа получать данные кодировок пикселей и передавать команды устройству отображения или принтеру, позволяющие по этим кодировкам воспроизвести двухмерное изображение исходного документа. Для представления оцифрованного отсканированного документа в виде монохромных изображений с оттенками серого обычно используют 8-разрядное или 16-разрядное кодирование пикселей, в то время как при представлении цветного отсканированного изображения может выделяться 24 или более бит для кодирования каждого пикселя, в зависимости от стандарта кодирования цвета. Например, в широко применяемом стандарте RGB для представления интенсивности красного, зеленого и синего цветов используются три 8-разрядных значения, закодированных с помощью 24-разрядного значения. Таким образом, оцифрованное отсканированное изображение, по существу, представляет собой документ в той же степени, в какой цифровые фотографии представляют визуальные образы. Каждый закодированный пиксель содержит информацию о яркости света в определенных крошечных областях изображения, а для цветных изображений в нем также содержится информация о цвете. В оцифрованном изображении отсканированного документа отсутствует какая-либо информация о значении закодированных пикселей, например информация, что небольшая двухмерная зона соседних пикселей представляет собой текстовый символ. Фрагменты изображения, соответствующие изображениям символов, могут обрабатываться для получения битов изображения символа, в котором биты со значением «1» соответствуют изображению символа, а биты со значением «0» соответствуют фону. Растровое отображение удобно для представления как полученных изображений символов, так и эталонов, используемых системой OCR для распознавания конкретных символов.
[37]В отличие от этого обычный электронный документ, созданный с помощью текстового редактора, содержит различные типы команд рисования линий, ссылки на представления изображений, таких как оцифрованные фотографии, а также текстовые символы, закодированные в цифровом виде. Одним из наиболее часто используемых стандартов для кодирования текстовых символов является стандарт Юникод. В стандарте Юникод обычно применяется 8-разрядный байт для кодирования символов ASCII и 16-разрядные слова для кодирования символов и знаков множества языков, включая японский, китайский и другие неалфавитные текстовые языки. Большая часть вычислительной работы, которую выполняет программа OCR, связана с распознаванием изображений текстовых символов, полученных из оцифрованного изображения отсканированного документа, и с преобразованием изображений символов в соответствующие кодовые комбинации стандарта Юникод. Очевидно, что для хранения текстовых символов стандарта Юникод будет требоваться гораздо меньше места, чем для хранения растровых изображений текстовых символов. Кроме того, текстовые символы стандарта Юникод можно редактировать, используя различные шрифты, а также обрабатывать всеми доступными в текстовых редакторах способами, в то время как оцифрованные изображения отсканированного документа можно изменить только с помощью специальных программ редактирования изображений.
[38]На начальном этапе преобразования изображения отсканированного документа в электронный документ печатный документ (например, документ 100, показанный на рисунке 1) анализируется для определения в нем различных областей. Во многих случаях области могут быть логически упорядочены в виде иерархического ациклического дерева, состоящего из корня, представляющего документ как единое целое, промежуточных узлов, представляющих области, содержащие меньшие области, и конечных узлов, представляющих наименьшие области. Дерево, представляющее документ, включает в себя корневой узел, соответствующий всему документу, и шесть конечных узлов, каждый из которых соответствует одной определенной области. Области можно определить, применяя к изображению разные методы, среди которых различные типы статистического анализа распределения пикселей или значений пикселей. Например, в цветном документе фотографию можно выделить по большему изменению цвета в области фотографии, а также по более частым изменениям значений яркости пикселей по сравнению с областями, содержащими текст.
[39]Как только начальный анализ выявит различные области на изображении отсканированного документа, области, которые с большой вероятностью содержат текст, дополнительно обрабатываются подпрограммами OCR с целью выявления и преобразования текстовых символов в символы стандарта Юникод или любого другого стандарта кодировки символов. Для того чтобы подпрограммы OCR могли обработать содержащие текст области, определяется начальная ориентация содержащей текст области, благодаря чему в подпрограммах OCR эффективно используются различные способы сопоставления с эталоном для определения текстовых символов. Следует отметить, что изображения в документах могут быть не выровнены должным образом в рамках изображений отсканированного документа из-за погрешности в позиционировании документа на сканере или другом устройстве, создающем изображение, из-за нестандартной ориентации содержащих текст областей или по другим причинам. Области, содержащие текст, затем делят на фрагменты изображений, содержащие отдельные иероглифы или символы, после чего эти фрагменты обычно масштабируются и ориентируются, а изображения символов центрируются относительно этих фрагментов для облегчения последующего автоматического распознавания символов, соответствующих изображениям символов.
[40]Существующие в настоящее время способы и системы OCR
[41]Для перехода к конкретному обсуждению различных методов оптического распознавания символов в качестве примера будет использоваться набор символов для некоторого гипотетического языка. На рисунке 6 показан гипотетический набор символов. На рисунке 6 показаны 48 различных символов, расположенных в 48 прямоугольных областях, таких как прямоугольная область 602. В правом верхнем углу каждой прямоугольной области указан числовой индекс или код символа, вписанный в круг; например, индекс или код «1» 604 соответствует первому символу 606, показанному в прямоугольной области 602. Данный пример выбран для демонстрации работы как существующих в настоящее время способов и систем OCR, так и новых способов и систем, описанных в настоящем документе. Фактически для письменных иероглифических языков, включая китайский и японский языки, для печати и письма могут использоваться десятки тысяч различных символов.
[42]На рисунках 7А-В показаны различные аспекты наборов символов для естественных языков. На рисунке 7А в столбце показаны различные формы изображения восьмого символа из набора, показанного на рисунке 6. В столбце 704 для восьмого символа 702 из набора символов, показанного на рисунке 6, представлены разные формы написания, встречающиеся в разных стилях текста. Во многих естественных языках могут использоваться различные стили текста, а также различные варианты написания каждого символа.
[43]На рисунке 7B показаны разные подходы к распознаванию символов естественного языка. На рисунке 7B конкретный символ естественного языка представлен узлом 710 на графе 712. Конкретный символ может иметь множество различных общих письменных или печатных форм. В целях оптического распознавания символов каждая из этих общих форм представляется в виде отдельной графемы. В некоторых случаях определенный символ может соответствовать двум или более графемам. Например, китайские иероглифы могут содержать комбинацию из двух или более графем, каждая из которых присутствует в других иероглифах. Корейский язык, на самом деле, основан на алфавите, при этом используются корейские морфо-слоговые блоки, содержащие ряд буквенных символов в различных позициях. Таким образом, корейский морфо-слоговой блок может представлять собой символ более высокого уровня, состоящий из множества компонентов графем. Для символа 710, показанного на рисунке 7B, имеется шесть разных графем 714-719. Кроме того, есть одна или более различных печатных или письменных форм начертания графем, каждая из которых представлена соответствующим эталоном. На рисунке 7B каждая из графем 714 и 716 имеет два возможных варианта начертания, представленных эталонами 720-721 и 723-724 соответственно. Каждая из графем 715 и 717-719 связана с одним эталоном 722 и 725-727 соответственно. Например, восьмой символ из набора, показанного в качестве примера на рисунке 6, может быть связан с тремя графемами, первая из которых соответствует начертаниям 702, 724, 725 и 726, вторая - 728 и 730, а третья - 732. В этом примере к первой графеме относятся начертания, в которых используются прямые горизонтальные элементы, ко второй графеме относятся начертания, в которых используются горизонтальные элементы и короткие вертикальные элементы с правой стороны, а к третьей графеме относятся начертания, включающие в себя изогнутые (а не прямые) элементы. Кроме того, все начертания восьмого символа 702, 728, 724, 732, 725, 726 и 730 можно представить в виде эталонов, связанных с единственной графемой для восьмого символа. В определенной степени выбор графем осуществляется произвольно. В некоторых типах иероглифических языков можно определить много тысяч разных графем. Эталоны можно рассматривать в качестве альтернативного представления или изображения символа, при этом они могут быть представлены в виде набора пар «признак - значение признака», как описано ниже.
[44]Хотя отношение между символами, графемами и эталонами показано на рисунке 7B как строго иерархическое, при котором каждая графема связана с одним конкретным родительским символом, фактические отношения не могут быть так просто структурированы. На рисунке 7С показан несколько более сложный набор отношений, когда два символа 730 и 732 являются родительскими для двух разных графем 734 и 736. В качестве еще одного примера можно привести следующие символы английского языка: строчная буква «о», прописная буква «О», цифра «0» и символ градусов «°», которые могут быть связаны с кольцеобразной графемой. Отношения также могут быть представлены в виде графов или сетей. В некоторых случаях графемы (в отличие от символов или в дополнение к ним) могут отображаться на самых высоких уровнях в рамках выбранного представления отношений. В сущности, идентификация символов, графем, выбор эталонов для конкретного языка, а также определение отношений между ними осуществляются в большой степени произвольно.
[45]На рисунках 8А-В показаны признаки и значения признаков, рассчитанные для изображений символов. Следует заметить, что словосочетание «изображение символа» может описывать печатный, рукописный или отображаемый на экране символ или графему. В следующем примере признаки и значения признаков рассматриваются применительно к изображениям символов, но в фактическом контексте реального языка признаки и значения признаков часто применяются для характеристики и представления изображений графем. На рисунке 8А показано изображение прямоугольного символа 802, полученное из содержащего текст изображения, которое соответствует 22-му символу из набора, показанного в качестве примера на рисунке 6. На рисунке 8B показано изображение прямоугольного символа 804, полученное из содержащего текст изображения, которое соответствует 48-му символу из набора, показанного в качестве примера на рисунке 6. При печати и письме на гипотетическом языке, соответствующем набору символов, приведенному в качестве примера, символы размещаются в середине прямоугольных областей. Если это не так, системы OCR произведут начальную обработку изображений, изменив ориентацию, масштаб и положение полученных изображений символов относительно фоновой области с целью нормализации полученных изображений символов для дальнейших стадий обработки.
[46]На рисунке 8А показаны три разных признака, которые могут использоваться системой OCR для характеристики символов. Следует заметить, что область изображения символа, или окно символа, характеризуется вертикальным размером окна символа 806, обозначаемым сокращенно «vw», и горизонтальным размером окна символа 808, обозначаемым сокращенно «hw». Первым признаком является самый длинный в изображении символа непрерывный горизонтальный отрезок линии, обозначаемый «h» 810. Это самая длинная последовательность смежных темных пикселей на фоне в основном белых пикселей в окне символа. Вторым признаком является самый длинный в изображении символа непрерывный вертикальный отрезок линии 812. Третий признак представляет собой отношение пикселей изображения символа к общему числу пикселей в окне символа, выраженное в процентах; в данном примере это процент черных пикселей по отношению ко всем пикселям, составляющим символ. Во всех трех случаях значения признаков могут быть непосредственно рассчитаны сразу после того, как будет создано растровое отображение окна символа. На рисунке 8B показаны два дополнительных признака. Первым признаком является число внутренних горизонтальных белых полос в изображении символа; изображение символа, показанного на рисунке 8B, имеет одну внутреннюю горизонтальную белую полосу 816. Вторым признаком является число внутренних вертикальных белых полос в изображении символа. В 48-м символе из набора, представленном изображением в окне символа 804 на рисунке 8B, имеется одна внутренняя вертикальная белая полоса 818. Число горизонтальных белых полос обозначается как «hs», а число внутренних вертикальных белых полос - «vs».
[47]На рисунке 9 показана таблица значений признаков, рассчитанных для всех символов из набора, изображенного в качестве примера на рисунке 6. В каждой строке таблицы 902, показанной на рисунке 9, представлены значения признаков, рассчитанные для конкретного символа. Представлены следующие признаки: (1) отношение самого длинного непрерывного горизонтального отрезка линии к окну символа, 
, 904; (2) отношение самого длинного непрерывного вертикального отрезка линии к вертикальному размеру окна символа, 
, 906; (3) выраженная в процентах общая площадь, соответствующая изображению символа или черной области, b, 908; (4) количество внутренних вертикальных полос, vs, 910; (5) количество внутренних горизонтальных полос, hs, 912; (6) общее количество внутренних вертикальных и горизонтальных полос, vs+hs, 914; и (7) отношение самого длинного вертикального отрезка линии к самому длинному горизонтальному отрезку линии, 
916. Как и следовало ожидать, в первой строке 920 таблицы 902, представленной на рисунке 9, первый символ набора (606 на рисунке 6) представляет собой вертикальную черту, и численное значение признака 
, равное 0,6, значительно больше численного значения признака , равного 0,2. Символ 606 занимает всего 12 процентов всего окна символа 602. У символа 606 нет ни внутренних горизонтальных, ни внутренних вертикальных белых полос, поэтому значения признаков vs, hs и vs+hs равны 0. Соотношение равно 3. Поскольку используемые в качестве примера символы имеют относительно простую блочную структуру, то значения каждого из признаков в таблице 902 отличаются незначительно.
[48]Несмотря на то, что значения каждого из признаков, рассмотренных выше в отношении рисунка 9, имеют относительно небольшие отличия для используемых в качестве примера 48 символов, всего трех признаков достаточно для разделения всех этих символов на 18 частей, или кластеров. На рисунке 10 показан трехмерный график для символов из набора, изображенного в качестве примера на рисунке 6, на котором каждое из измерений представляет значения одного из трех разных признаков. На рисунке 10 первая горизонтальная ось 1002 представляет признак (916 на рисунке 9), вторая горизонтальная ось 1004 представляет признак vs+hs (914 на рисунке 9), а третья вертикальная ось 1006 представляет признак b (908 на рисунке 9). На графике есть 18 различных точек (таких как нанесенная точка 1008), каждая из которых показана в виде небольшого черного диска с вертикальной проекцией на горизонтальную плоскость, проходящую через оси 1002 и 1004; эта проекция представлена в виде вертикальной пунктирной линии, такой как вертикальная пунктирная линия 1010, соединяющая точку 1008 с ее проекцией на горизонтальную плоскость 1012. Код или номер последовательности символов, которые соответствуют определенной точке на графике, перечислены в скобках справа от соответствующей точки. Например, символы 14, 20 и 37 (1014) соответствуют одной точке 1016 с координатами (1, 0, 0,32) относительно осей 1002, 1004 и 1006. Каждая точка связана с номером части или кластера, который указан в небольшом прямоугольнике слева от точки. Например, точка 1016 связана с кластером под номером «14» 1018. На рисунках 11А-В показаны символы, содержащиеся в каждом из кластеров, представленных точками трехмерного пространства, изображенного на рисунке 10. Рассмотрев символы, входящие в состав этих кластеров или частей, можно легко заметить, что три признака, используемые для распределения символов в трехмерном пространстве, показанном на рисунке 10, эффективно разбивают 48 символов, используемых в качестве примера, на связанные наборы символов.
[49]Можно использовать дополнительные признаки для однозначного распознавания каждого символа в каждом кластере или части. Рассмотрим, например, кластер 8 (1102), показанный на рисунке 11А. Этот кластер символов включает в себя четыре угловых (L-образных) символа, отличающихся углом поворота и имеющих коды 26, 32, 38 и 44, а также Т-образный символ с кодом 43 и крестообразный символ с кодом 45. На рисунке 12А показан отдельный признак, который можно использовать в сочетании с тремя признаками, соответствующими каждому из измерений трехмерного пространства признаков, изображенного на рисунке 10, для полного распознавания каждого символа в кластере 8. Как показано на рисунке 12А, окно символа 1202 делится на четыре квадранта: Q1 1204, Q2 1205, Q3 1206 и Q4 1207. После этого в каждом квадранте вычисляется площадь, занимаемая изображением символа, которая указывается рядом с квадрантом. Например, в квадранте Q1 1204 часть изображения символа занимает 13,5 единиц площади 1210. Затем вычисленные значения единиц площади каждого квадранта присваиваются переменным Q1, Q2, Q3 и Q4. Следовательно, в примере, представленном на рисунке 12А, переменной Q1 присвоено значение 13,5, переменной Q2 присвоено значение 0, переменной Q3 присвоено значение 18, а переменной Q4 присвоено значение 13,5. Затем согласно небольшому фрагменту псевдокода 1212, представленному на рисунке 12А под окном символа, рассчитывается значение нового признака p. Например, если все четыре переменные Q1, Q2, Q3 и Q4 имеют одинаковые значения, то признаку p будет присвоено значение 0 (1214), что указывает на равенство четырех квадрантов в окне символа относительно количества единиц площади, занимаемой изображением символа. На рисунке 12B показано значение дополнительного признака для каждого символа из кластера 8, которое следует рассматривать со ссылкой на рисунок 12А. Как можно увидеть из значений признаков, связанных с символами на рисунке 12B, новый признак, описанный выше касательно рисунка 12А, имеет разное значение для каждого из шести символов в кластере 8. Другими словами, можно использовать комбинацию трех признаков, используемых для создания трехмерного графика, показанного на рисунке 10, и дополнительного признака, рассмотренного выше на рисунке 12А, для однозначной идентификации всех символов в кластере 8.
[50]На рисунке 13 показано небольшое изображение, содержащее текст, которое было изначально обработано системой OCR для получения сетки окон символов 1300, в каждом из которых содержится изображение символа. Для большей наглядности на рисунке 13 показана сетка окон символов 1300, не содержащая изображений символов. Для упорядочивания окон символов используется вертикальный индекс i 1302 и горизонтальный индекс у 1304. Для облегчения понимания примера, рассматриваемого ниже, в нем будет идти речь о символах и изображениях символов, а не о графемах. В этом примере предполагается, что существует однозначное соответствие между символами, графемами и эталонами, используемыми для идентификации изображений символов в окнах символов. Кроме сетки окон символов 1300, на рисунке 13 также показан массив, или матрица 1306 эталонов, каждая ячейка которой (например, ячейка 1308) включает в себя эталон. Эталоны представляют собой наборы пар «признак - значение признака», где признаки выбираются для однозначного распознавания изображений символов, как было описано выше со ссылкой на рисунки 8А-12B. На рисунке 13 также показан массив признаков 1310, представленный в виде набора пар фигурных скобок, таких как фигурные скобки 1312. Каждая пара фигурных скобок представляет собой функционал, который рассчитывает значение признака относительно изображения символа.
[51]На рисунке 14 показан общий подход к обработке сетки окон символов, показанной на рисунке 13. На самом высоком уровне обработка может рассматриваться как вложенный цикл for 1402, в котором вызывается метод «process» 1404 для анализа каждого окна символа 1406 с целью формирования соответствующего кода символа 1408. Другими словами, в примере с псевдокодом сетка окон символов представляет собой двухмерный массив «page_of_text», а система OCR формирует двухмерный массив кодов символов «processed_text» на основе двухмерного массива окон символов «page_of_text». На рисунке 14 дугообразные стрелки, такие как дугообразная стрелка 1410, используются для демонстрации порядка обработки первой строки двухмерного массива или сетки окон символов 1300, а горизонтальные стрелки, такие как стрелка 1412, показывают обработку следующих строк, осуществляемую в цикле for 1402. Другими словами, сетка окон символов 1300 обрабатывается согласно указанному выше порядку обработки, при этом каждое окно символа в сетке обрабатывается отдельно для формирования соответствующего кода символа.
[52]На рисунке 15 показан первый подход к реализации функции «process» (1404 на рисунке 14). Изображение символа, находящееся в окне символа 1502, используется в качестве входного признака для метода «process». Метод «process» используется для расчета значений восьми разных признаков p1-p8, используемых в данном примере для получения отличительных особенностей изображений символов путем восьмикратного вызова метода «parameterize» 1504, как показано на рисунке 15. Метод «parameterize» использует в качестве аргументов изображение символа и целочисленное значение, указывающее, для какого признака необходимо рассчитать и вернуть рассчитанное значение. Значения признаков хранятся в массиве значений признаков «p_values». Затем, как показано дугообразными стрелками, такими как дугообразная стрелка 1506, метод «process» перебирает все эталоны 1508, соответствующие символам языка, сравнивая рассчитанные значения признаков для изображения символа, хранящиеся в массиве «p_values», с предварительно рассчитанными значениями признаков каждого эталона, как показано на иллюстрации операции сравнения 1510 на рисунке 15. Эталон, признаки которого больше всего соответствуют рассчитанным признакам для изображения символа, выбирается в качестве эталона соответствия, а код символа, который соответствует этому эталону, используется в качестве возвращаемого значения метода «process». В качестве примера псевдокода, используемого для этого первого варианта осуществления метода «process», приведен псевдокод 1512 на рисунке 15. В первом цикле for 1514 рассчитываются значения признаков для входного символа s. Затем в нескольких вложенных циклах for внешнего цикла for 1516 анализируется каждый эталон из массива или вектора эталонов 1508 согласно порядку, указанному дугообразными стрелками, такими как дугообразная стрелка 1506. Во внутреннем цикле for 1518 вызывается метод «compare» для сравнения каждого рассчитанного значения признака изображения символа с соответствующим предварительно рассчитанным значением признака эталона, а общий результат сравнения записывается в локальную переменную t. Максимальное значение, накопленное в результате сравнения, хранится в локальной переменной score, а индекс эталона, который наиболее точно соответствует изображению символа, хранится в переменной p 1520. Код символа, связанный с эталоном p, возвращается методом «process» 1520 в качестве результата.
[53]Наконец, на рисунке 15 показана грубая оценка вычислительной сложности первого варианта осуществления метода «process» 1522. Количество окон символов для содержащего текст изображения равно N=i×j. В текущем примере N=357. Конечно, количество изображений символов, которое необходимо обработать, зависит от типа документа и количества изображений в нем, а также от языка и других обстоятельств. Однако обычно количество изображений символов Сможет изменяться от нескольких десятков до нескольких сотен для каждого изображения документа. Количество эталонов, с которыми сравниваются изображения символов, представлено параметром Р. Для многих алфавитных языков, включая большинство европейских языков, количество эталонов может быть относительно небольшим, что соответствует относительно небольшому множеству символов алфавита. Однако для таких языков, как китайский, японский и корейский, количество эталонов может изменяться от десятков тысяч до сотен тысяч. Поэтому при обработке таких языков значение параметра Р значительно превышает значение параметра N. Количество признаков, используемых для оценки отличительных особенностей каждого изображения символа и эталона, представлено параметром R. Следовательно, общая вычислительная сложность оценивается как NPR. Коэффициент N берется из внешних вложенных циклов for, показанных на рисунке 14. Коэффициенты PR берутся из вложенных циклов for 1516 и 1518 варианта осуществления метода «process» 1512, показанного на рисунке 15. Другими словами, метод «process» вызывается один раз для каждого из N изображений символов, при этом каждый вызов или обращение к методу «process» приводит к R сравнениям с каждым из Р эталонов. При таком способе анализа изначально вычисленное значение признака считается постоянной величиной. Вариант осуществления алгоритма, приведенного на рисунке 15, можно улучшить различными способами. Например, можно сравнивать только определенное подмножество признаков из общего количества признаков, необходимое для однозначного сопоставления изображения символа с конкретным эталоном. Таким образом, может потребоваться произвести среднее количество сравнений признаков 
, а не R сравнений. Кроме того, вместо сравнения каждого изображения символа со всеми эталонами можно задать относительно высокий порог значения соответствия, при превышении которого последовательный перебор эталонов будет прекращаться. В этом случае количество эталонов, которые будут сравниваться с каждым изображением символа, будет равно 
, а не Р. Но даже при подобных улучшениях вычислительная сложность будет близка к значению наибольшего из параметров NPR.
[54]На рисунках 16А-В показан второй вариант осуществления функции «process» (1404 на рисунке 14). Во втором варианте осуществления изображение символа 1602 также используется в качестве входного параметра метода «process». Однако в данном варианте осуществления алгоритма эталоны группируются в кластеры, такие как кластеры, рассмотренные ранее на примере рисунков 11А-В. Метод «process» используется для расчета определенного количества значений признаков 1604, достаточного для определения наиболее подходящего кластера при переборе кластеров эталонов 1606. Таким образом, для выбора наиболее подходящего кластера эталонов сначала используется относительно простая операция сравнения 1608. Затем эталоны 1610 из выбранного кластера эталонов 1611 перебираются с помощью второй довольно простой операции сравнения 1612, для которой используются некоторые дополнительные значения признаков 1614, необходимые для определения наиболее подходящего эталона среди относительно малого числа эталонов 1610, содержащихся в кластере. Псевдокод для второго варианта осуществления метода «process» представлен на рисунке 16B. В первом вложенном цикле for 1620 выбирается наиболее подходящий или лучший среди имеющихся кластер эталонов, а во втором вложенном цикле for 1622 определяется наиболее подходящий эталон среди представленных в выбранном кластере. Начальный набор признаков, используемых для определения наилучшего кластера, рассчитывается в цикле for 1624, а дополнительные признаки, необходимые для выбора эталона в из числа эталонов выбранного кластера, рассчитываются в цикле for 1626. На рисунке 16B также представлена приблизительная оценка вычислительной сложности второго варианта осуществления метода «process» 1630. Как указано, оценочная вычислительная сложность для второго варианта осуществления метода «process» составляет:
[56]где количество символов на странице =N;
[57]количество кластеров =С;
[58]количество эталонов/кластер =Р’;
[59]количество исходных признаков =R;
[60]количество дополнительных признаков =R2.
[61]Поскольку значение Р’ по существу намного меньше значения Р, а значение С еще меньше, то вычислительная сложность второго варианта осуществления метода «process» вполне приемлема по сравнению с вычислительной сложностью первого варианта осуществления метода «process».
[62]Другим подходом к улучшению первого варианта осуществления метода «process», рассмотренного выше со ссылкой на рисунок 15, является сортировка эталонов в векторе, или массиве эталонов, чтобы наиболее вероятные эталоны, соответствующие наиболее часто встречающимся символам, рассматривались в самом начале перебора вектора, или массива эталонов. Когда поиск подходящего эталона прерывается вследствие нахождения эталона, результат сравнения которого превышает некоторое пороговое значение, и когда эталоны отсортированы по частоте употребления, соответствующей вероятности появления символов в обрабатываемом изображении, содержащем текст, вычислительная сложность значительно снижается. Однако частота появления символов в конкретных изображениях, содержащих текст, может сильно варьироваться в зависимости от типа документа или страницы, которые были отсканированы для получения изображения, и неизвестна до обработки системой OCR. Сортировка эталонов, приводящая к значительному снижению вычислительной сложности для одного типа документа, может значительно повысить вычислительную сложность для другого типа документа. Например, общий статистический анализ различных типов текстовых документов на определенном языке, включая романы, рекламные объявления, учебники и другие подобные документы, может позволить получить общий вариант сортировки эталонов по частоте появления символов. Однако в некоторых документах и текстах, относящихся к профильным сферам деятельности, частота появления символов может совершенно отличаться. В этом случае для документов, относящихся к определенным сферам деятельности, наиболее часто встречающиеся символы могут оказаться расположены ближе к концу обрабатываемого вектора, или матрицы эталонов, отсортированных в соответствии с общей частотой появления символов. Второй вариант осуществления метода «process», рассмотренный выше со ссылкой на рисунки 16А-В, по существу приводит к значительному уменьшению сложности вычислений и соответствующему увеличению скорости обработки. Как правило, требуется произвести значительно меньше сравнений, для того чтобы найти соответствующий эталон для каждого изображения символа. Однако второй вариант осуществления связан с потенциально серьезной проблемой, которая состоит в том, что при неудачном выполнении первого вложенного цикла for, в котором осуществляется выбор кластера, метод «process» не сможет найти правильный соответствующий символ. В этом случае правильный соответствующий символ будет находиться в другом кластере, который не будет анализироваться во втором вложенном цикле for. Хотя примеры наборов символов и кластеров, представленные выше, являются относительно простыми, как и признаки, используемые для определения их отличительных особенностей, для таких языков, как китайский и японский, подобная задача является более сложной и подверженной ошибкам из-за несовершенства печати, повреждения документа, а также из-за различных типов ошибок, которые могут возникнуть при сканировании и на начальных стадиях процесса OCR. Таким образом, вероятность неправильного выбора кластера в реальных условиях очень высока.
[63]Способы и системы, к которым относится настоящий документ
[64]На рисунке 17 показан третий вариант осуществления функции «process», рассмотренной в предыдущем подразделе, с использованием тех же иллюстраций и условных обозначений в псевдокоде, которые использовались в предыдущем подразделе. Третий вариант осуществления метода «process» представляет собой очень общее описание одного варианта осуществления способов и систем, к которым относится настоящий документ.
[65]Как показано на рисунке 17, третий вариант осуществления метода «process» применяет дополнительную структуру данных 1702, обозначаемую как «голоса» («votes»). Структура данных votes содержит целочисленное значение для каждого эталона. При начальной инициализации эта структура содержит нулевые значения для всех эталонов. После этого на первой стадии предварительной обработки, представленной двойным вложенным циклом for 1704 на рисунке 17, для каждого изображения символа в текстовом документе 1300 назначается новый набор кластеров, а эталоны в кластерах упорядочиваются согласно голосам, собранным в структуре данных «votes». Другими словами, эталоны упорядочиваются в заново выделенном наборе, или списке, кластеров, благодаря чему эталоны, с наибольшей вероятностью соответствующие изображению текущего символа, встречаются в начале перебора эталонов. Значения набора сравниваемых признаков, рассчитанные для текущего изображения символа, сравниваются со значениями признаков каждого эталона, при этом голоса отдаются тем эталонам, которые (по результатам сравнения) имеют сходство с изображением символа, превышающее установленный порог. В некоторых вариантах осуществления кластеры также могут быть отсортированы в пределах набора кластеров по общему сходству их эталонов с изображением символа.
[66]После стадии предварительной обработки, осуществляемой вложенными циклам for 1704, каждое изображение символа обрабатывается третьим вариантом осуществления метода «process». Псевдокод для третьего варианта осуществления метода «process» 1710 представлен на рисунке 17. В данном варианте осуществления метод «process» принимает в качестве входных признаков изображение символа и набор кластеров, подготовленный для изображения символа на стадии предварительной обработки и хранящийся в массиве NxtLvlClusters, а возвращает указатель на список потенциально соответствующих эталонов. В первом цикле for 1712 рассчитываются значения признаков, которые используются для определения эталонов, соответствующих принятому изображению символа. Во втором внешнем цикле for 1714 рассматриваются все кластеры, пока не заполнится список потенциально соответствующих эталонов. Другими словами, когда находится максимальное количество потенциально соответствующих эталонов, этот внешний цикл for прерывается. Во внутреннем цикле for 1716 для каждого эталона в кластере вызывается функция «similar», осуществляющая определение того, является ли эталон достаточно похожим на изображение символа, чтобы его можно было добавить в список потенциально соответствующих эталонов. Когда список потенциально соответствующих эталонов заполнен, внутренний цикл for также прерывается. На рисунке 17 представлена оценка вычислительной сложности третьего варианта осуществления метода «process» 1720. Поскольку как внешний, так и внутренний циклы for 1714 и 1716 прерываются, когда найдено достаточное количество потенциально соответствующих эталонов, а векторы, или списки эталонов в каждом кластере могут быть отсортированы по частоте появления в обрабатываемом документе, то в третьем варианте осуществления метода «process» требуется выполнить лишь относительно небольшое количество сравнений по сравнению со вторым вариантом осуществления метода, что и показано дробью 
1722. Существует, конечно, штраф за начальную предварительную обработку, представленный коэффициентом «е» 1744. Однако, как указывалось выше, количество обрабатываемых изображений символов N по существу значительно меньше значения признаков Р или Р’ для таких языков, как китайский, японский и корейский, и, следовательно, третий вариант осуществления метода «process» обеспечивает значительное снижение вычислительной сложности по сравнению как с первым, так и со вторым вариантами осуществления, рассмотренными выше. Что более важно, в третьем варианте осуществления метода «process» гарантируется просмотр всех кластеров, пока не будет обнаружено некоторое максимальное количество потенциально соответствующих символов. Когда порог сходства для кластеров имеет относительно низкое значение, а порог сходства для эталонов имеет относительно высокое значение, существует очень большая вероятность, что список потенциально соответствующих символов, возвращаемый методом «process», будет включать в себя именно тот символ, который наиболее точно соответствует входному изображению символа.
[67]Рассмотренная выше информация, включая третий вариант осуществления, представленный на рисунке 17, создает основу для описания определенного аспекта этого обобщенного третьего варианта осуществления, к которому относится настоящий документ. Следует четко понимать, что описанные выше варианты осуществления представляют собой обобщенные варианты осуществления и что конкретный вариант осуществления системы OCR может применять любой из большого количества возможных альтернативных вариантов осуществления.
[68]Настоящий документ относится к описанию логики управления и структур данных в системе OCR, которые можно использовать как для кластеризации эталонов, так и на стадии предварительной обработки, рассмотренной выше, в ходе которой графемы в эталонах могут быть отсортированы по частоте появления в отсканированном изображении, содержащем текст, или в наборе отсканированных изображений. Эти логика управления и структуры данных применяются в системе OCR для реализации стадий предварительной обработки/кластеризации, в ходе которых фиксированный набор признаков связывается с каждым кластером и применяется при сравнении изображения символа с эталонами, содержащимися в кластере. Кластеры можно использовать в различных локальных операциях или на разных этапах сложной задачи оптического распознавания символов, при этом конкретные признаки (а также количество этих признаков), используемые для сравнения изображения символа с эталонами, содержащимися в кластере, могут отличаться в различных локальных операциях и на разных этапах, а также часто могут быть различными в разных кластерах. На рисунке 18 показаны структуры данных, обеспечивающие кластеризацию и предварительную обработку в одном варианте осуществления системы OCR, включающей в себя третий вариант осуществления функции «process», описанный выше. Первой структурой данных является массив, или вектор 1802, обозначенный как «votes» («голоса»). В описанном варианте осуществления массив «votes» содержит один элемент для каждой графемы языка. Массив «votes» индексируется целыми значениями кодов графем. Другими словами, каждой графеме присваивается уникальный целочисленный идентификатор или код графемы, который используется в качестве индекса массива «votes». Как показано на рисунке 18, массив «votes» может содержать n элементов, где n представляет собой количество графем в языке, а коды графем монотонно возрастают от 0 до n. Конечно, структура данных «votes» может быть альтернативно реализована в виде разреженного массива, когда коды графем возрастают немонотонно, в виде списка, или с использованием других типов структур данных.
[69]На рисунке 18 показана вторая структура данных 1804, которая представляется собой массив экземпляров класса «parameter». Как и в случае со структурой данных «votes», массив «parameters» может быть реализован альтернативными способами с использованием разных структур данных, включая списки, разреженные массивы и другие структуры данных. В текущем рассматриваемом варианте осуществления массив «parameters» включает в себя р записей или элементов, которые проиндексированы с помощью монотонно увеличивающихся чисел 0, 1, 2, …, р. Каждый экземпляр класса «parameter» представляет один из различных признаков, используемых для определения отличительных особенностей изображений символов и эталонов, как описывалось выше.
[70]На рисунке 18 также показана структура данных кластера 1806, которая представляет собой кластер или набор эталонов. Структура данных кластера включает в себя массив «clusterParameters» 1808, в котором содержатся признаки, применяемые для определения отличительных особенностей эталонов в кластере в определенный момент времени, а также для определения отличительных особенностей изображений символов для их сравнения с эталонами, содержащимися в кластере. Каждый элемент в массиве «clusterParameters» содержит индекс для массива «parameters» 1804. Используя индексы в массиве «parameters» 1804, можно легко изменить или переконфигурировать конкретные признаки, а также количество признаков, используемых для сравнения, вследствие чего конфигурация кластера может быть эффективно изменена для различных локальных операций или этапов. Структура данных кластера также включает в себя целочисленный параметр пит 1810, который указывает количество индексов признаков, содержащихся в массиве «clusterParameters». Структура данных кластера дополнительно содержит параметр «cutoff» («отсечка») 1812, имеющий формат с плавающей запятой (или формат двойной точности) и содержащий пороговое значение для оценки эталонов, находящихся в кластере, на предмет их соответствия изображению символа. Наконец, структура данных кластера 1806 содержит ряд структур данных эталона 1814-1822. Структуры данных эталона рассматриваются ниже.
[71]На рисунках 19А-Н показана предварительная обработка изображения символа с использованием структур данных, рассмотренных выше со ссылкой на рисунок 18. На рисунке 19А показана структура данных «votes» 1802, рассмотренная выше со ссылкой на рисунок 18, а также структура данных одного эталона 1902, выбранная из эталонов, содержащихся в структуре данных кластера 1806, также рассмотренной выше со ссылкой на рисунок 18. Каждая структура данных эталона содержит номер эталона 1904 и набор значений признаков 1905, рассчитанных для эталона с помощью признаков, ссылки на которые получены из индексов, содержащихся в массиве «clusterParameters» 1808, который находится в структуре данных кластера 1806. Как отмечалось выше, важно помнить, что изображения символов масштабируются, поворачиваются и преобразуются для создания нормированных изображений, чтобы облегчить процедуру сравнения изображений символов и эталонов на основе признаков. Структура данных эталонов дополнительно содержит целочисленный параметр 1906, указывающий количество индексов в структуре данных эталона, а также значения самих индексов 1908. Эти индексы связаны с различными возможными весами, которые могут быть рассчитаны при сравнении изображения символа с эталоном. В одном варианте осуществления в структуре данных эталона может быть столько индексов, сколько имеется возможных рассчитанных весов, при этом каждый индекс включает в себя целочисленный индекс и рассчитанный вес, связанный с этим индексом. Возможны и другие варианты осуществления. Вес рассчитывается, когда рассчитываются признаки для изображения символа и значения признаков изображения символа сравниваются с эталоном, представленным структурой данных эталона. Чем больше значение веса, тем меньше изображение символа похоже на эталон. Этот вес применяется для выбора из указателей соответствующего индекса, который используется для выбора графем, соответствующих эталону, за которые необходимо проголосовать на этапе предварительной обработки. Каждая структура данных эталона включает в себя целочисленное значение, указывающее количество графем, соответствующих эталону 1910, а также коды всех графем набора, соответствующих эталону 1912. Во других вариантах осуществления эти коды графем могут быть отсортированы по сходству или по близости к эталону в порядке убывания сходства.
[72]На рисунках 19В-Н показана предварительная обработка изображения одного символа, выбранного из отсканированного изображения, содержащего текст. В примере, изображенном на рисунках 19В-Н, изображение символа 1914 представляет собой иероглиф одного из азиатских языков. На рисунке 19В также показаны массив «parameters» 1804, рассмотренный выше со ссылкой на рисунок 18, и небольшой фрагмент структуры данных кластера 1806, включающей в себя массив «clusterParameters» 1808 и целочисленный параметр num 1810.
[73]Как показано на рисунке 19С, для всех признаков num, индексы которых включены в массив «clusterParameters» 1808, индекс признака 1916 извлекается из массива «clusterParameters» 1808 и используется для доступа к экземпляру класса «parameter» 1918 в массиве «parameters» 1804. Для расчета значения признака 1920, которое затем хранится в локальной переменной 1922, вызывается функция-член «parameterize» экземпляра класса «parameter» 1918. На рисунке 19С показан расчет значения первого признака для изображения символа. На рисунке 19D показан расчет значения второго признака для изображения символа. Когда все экземпляры пит класса «parameter» задействованы для расчета значений признаков пит для изображения символа, формируется список, или массив, значений признаков изображения символа 1924, как показано на рисунке 19Е.
[74]Затем, как показано на рисунке 19F, из предварительно рассчитанного значения признака для эталона, представленного структурой данных эталона, вычитается соответствующий признак для изображения символа с целью получения ряда рассчитанных значений, по одному для каждого признака. Например, как показано на рисунке 19F, из первого значения признака 1926, хранящегося в структуре данных эталона 1902, вычитается первое значение признака 1922, рассчитанное для изображения символа, с целью получения промежуточного значения 1928. Аналогичным образом из остальных предварительно определенных значений признаков для эталона 1930-1933 вычитаются остальные значения признаков для изображения символа 1934-1938 для получения дополнительных промежуточных расчетных значений 1940-1944. Абсолютные величины этих промежуточных значений 1928 и 1940-1944 суммируются 1946 для получения веса 1948, который численно представляет собой основанное на признаках сравнение изображения символа и эталона, представленного структурой данных эталона 1902. И в этом случае, чем больше значение рассчитанного веса, тем меньше изображение символа похоже на эталон, поскольку вес представляет собой накопленное различие между значениями признаков для изображения символа и эталона.
[75]Как показано на рисунке 19G, когда рассчитанный вес 1948 превышает вес отсечки «cutoff» 1812 для кластера, предварительная обработка изображения символа в отношении рассматриваемого эталона, представленного структурой данных эталона 1902, прекращается 1950. В противном случае, на этапе предварительной обработки изображения символа происходит голосование за одну или более графем, соответствующих эталону, представленному структурой данных эталона 1952.
[76]На рисунке 19Н показан случай, когда рассчитанный вес, представляющий собой сравнение изображения символа с эталоном, представленным структурой данных эталона, меньше или равен весу отсечки для данного кластера. В этом случае для выбора индекса 1954 из набора индексов 1908 используется рассчитанный вес 1948. Как описывалось выше, каждый из индексов 1908 может содержать индекс и связанный с ним вес, что позволяет выбрать один конкретный индекс 1954 согласно рассчитанному весу 1948 из индекса, который является индексом извлекаемых кодов графем. Этот извлеченный индекс указывает 1956 на конкретный код графемы 1958 в наборе кодов графем 1912, хранящемся в структуре данных эталонов для представления тех графем, которые соответствуют эталону. Затем для всех кодов графем, начиная с первого кода графемы 1960 и до кода графемы 1958, на который указывает извлеченный индекс 1956, увеличивается соответствующий элемент из структуры данных «votes» 1802, как показано стрелками (такими как стрелка 1962), исходящими из элементов, содержащих коды графем между элементами 1960 и 1958 включительно.
[77]Таким образом, если рассчитанный вес, используемый для сравнения изображения символа с эталоном, меньше веса отсечки, значит изображение символа достаточно похоже на эталон, чтобы по меньшей мере за некоторые из графем, соответствующих эталону, были отданы голоса на этапе предварительной обработки. Графемы, достаточно похожие на изображение символа, выбираются на основе рассчитанного веса с использованием индекса, выбранного из индексов 1908 в соответствии с рассчитанным весом. Затем элементы структуры данных «votes», соответствующие этим графемам, увеличиваются для отражения количества голосов, отданных этим графемам во время предварительной обработки изображения символа.
[78]Далее приводится псевдокод, напоминающий код на языке C++, для иллюстрации предварительной обработки изображения символа с учетом эталонов в кластере, как показано на рисунках 19А-Н. Используется относительно простой псевдокод, похожий на язык C++, включающий массивы фиксированного размера и простые структуры управления. Конечно, в реальных системах OCR могут использоваться более эффективные, но и более сложные варианты осуществления, включающие итераторы, структуры данных, реализующие ассоциативную память, а также другие подобные структуры данных и связанные с ними способы.
[79]Сначала определяется ряд структур данных и объявляются классы:
[80]
[81]
[82]В строке 1 осуществляется объявление структуры данных «votes» 1802. Частичное объявление класса «parameter» представлено в строках 2-5. В данном примере единственно важным аспектом класса «parameter» является то, что базовый класс включает в себя виртуальную функцию-член «parameterize», которая в качестве входных данных принимает изображение символа, а возвращает значение признака с плавающей запятой. Конечно, в некоторых случаях конкретный признак может иметь только целые значения, а не значения с плавающей запятой. Структура данных «parameters» 1804 объявляется в строке 6. Частичное объявление класса «pattern» происходит в строках 7-21. Класс «pattern» включает в себя следующие private-компоненты: «patternNo» (1904 на рисунке 19А), объявленный в строке 10, массив значений признака «parameters» (1906 на рисунке 19А), объявленный в строке 11, количество индексов «numlndices» (1906 на рисунке 19А), объявленное в строке 12, набор индексов (1908 на рисунке 19А) элементов множества «numlndices», объявленный в строке 13, целочисленное значение «numGraphemes» (1910 на рисунке 19А), а также набор кодов графем «graphemes» (1912 на рисунке 19А) элементов множества «numGraphemes». Класс «pattern» включает функцию-член «getParameter», объявленную в строке 17, которая возвращает значение признака из набора значений «parameters», функцию-член «getlndex», объявленную в строке 18, которая возвращает индекс, соответствующий рассчитанному весу, а также функцию-член «getGrapheme», объявленную в строке 19, которая возвращает код графемы из набора кодов «graphemes», объявленного в строке 15. Наконец, в строках 22-37 объявляется класс «cluster», который представляет структуру данных кластера 1806 на рисунке 18. Класс «cluster» содержит следующие private - компоненты: num (1810 на рисунке 18), объявленный в строке 25, «clusterParameters» (1808 на рисунке 18), объявленный в строке 26, «cutoff» (1812 на рисунке 18), объявленный в строке 27, целочисленное значение «numPattems», указывающее на количество эталонов в кластере, объявленное в строке 28, а также указатель на эталоны в кластере «patterns», объявленный в строке 29. Класс «cluster» включает функции-члены «getCutoff» и «getNum», используемые для получения веса отсечки и количества эталонов, объявленные в строках 31 и 32, функцию-член «getParameter», используемую для получения индексов признаков из массива «clusterParameters», объявленную в строке 32, функцию-член «getPattem», возвращающую определенный эталон, хранящийся в кластере, объявленную в строке 33, и функцию-член «getNumPattems», объявленную в строке 34, которая возвращает количество эталонов, хранящееся в структуре данных кластера.
[83]На примере следующего псевдокода функции «vote» показана реализация способа предварительной обработки для одного изображения символа и одного кластера:
[84]
[85]
[86]Функция «vote» получает в качестве аргументов указатель на изображение символа и указатель на кластер. Локальные переменные включают в себя массив «params», объявленный в строке 38, в котором хранятся рассчитанные значения признаков для изображения символа, итерационные целочисленные значения i, j, k и l, объявленные в строке 39, переменные с плавающей запятой «weight» и «t», используемые для хранения рассчитанного веса, полученного в результате сравнения входного изображения символа и эталона из кластера, а также указатель р, объявленный в строке 41 и указывающий на эталон во входном кластере. В цикле for, в строках 43-44, значения всех признаков, используемых кластером, рассчитываются для входного изображения символа и записываются в массив «params» (1924 на рисунке 19Е). Затем во внешнем цикле for, содержащем вложенные циклы for, представленные в строках 45-58, рассматривается каждый признак входного кластера. В строке 46 получается указатель на рассматриваемый эталон путем вызова функции-члена кластера «getPattem». В строке 48 локальной переменной «weight» присваивается значение 0. Затем в цикле for, в строках 49-53, рассчитывается вес, который представляет собой сравнение входного изображения символа с эталоном, как описывалось выше со ссылкой на рисунок 19F. Когда вес превышает вес отсечки для кластера, как определено в строке 54, текущая итерация, выполняемая во внешнем цикле for, в строках 44-58, прерывается, поскольку входное изображение символа недостаточно похоже на рассматриваемый эталон, чтобы можно было за него проголосовать. В противном случае локальная переменная k принимает значение последнего индекса кода графемы для голосования в строке 55. Затем в цикле for, в строках 56-57, выполняется голосование за все графемы до графемы с индексом k.
[87]Существует множество различных альтернативных подходов к осуществлению предварительной обработки и формированию описанных выше структур данных. Например, вместо использования веса отсечки для всего кластера можно использовать вес отсечки для конкретных эталонов, при этом вес отсечки может включаться в структуру данных эталона. В другом примере индексы, хранящиеся в эталоне, могут представлять собой экземпляры классов, которые содержат списки кодов графем, а не индексы, указывающие на упорядоченный список кодов графем, как это реализуется в последнем варианте осуществления. Также возможны и многие другие альтернативные варианты осуществления. Например, функция «vote» может принимать в качестве второго аргумента указатель на массив «params», а в цикле for, в строках 43-44, могут вычисляться значения признаков только в том случае, если они еще не были рассчитаны при обработке изображения символа для других кластеров. В других вариантах осуществления можно применять разные типы расчета веса и сравнения изображения символа с эталоном. В некоторых случаях большее значение веса может указывать на большее сходство изображения символа с эталоном в отличие от приведенного выше примера, когда увеличение значения веса означало уменьшение сходства изображения символа с эталоном. В ряде систем OCR с графемами могут связываться вещественные коэффициенты, позволяющие при голосовании использовать дробные значения и значения больше 1. В некоторых системах OCR графемы, эталоны и/или кластеры могут быть отсортированы на основании голосов, накопленных в течение предварительной обработки, для более эффективного последующего распознавания символов. В определенных вариантах осуществления структура данных кластера может включать в себя только количество структур данных эталона или ссылок на структуры данных эталона, при этом вес отсечки и эталоны, связанные с кластером, указываются в алгоритме управления, а не хранятся в структуре данных кластера.
[88]Как только, после предварительной обработки изображения символа при помощи эталонов, содержащихся в кластере, голоса в массиве (структуре данных) «votes» для конкретного изображения символа были, массив «votes» может быть в дальнейшем обработан, чтобы упорядочить список кодов графем, для которых получены голоса, в порядке убывания количества голосов. Можно считать, что количество голосов, накопленных для конкретной графемы, представляет собой рассчитанную степень сходства данной графемы с анализируемым изображением символа. В другом варианте реализации метода в качестве степени сходства может использоваться какая-либо другая метрика, рассчитанная по накопленному для данной графемы количеству голосов. Вышеупомянутый упорядоченный список открывают графемы, имеющие наибольшую степень сходства с анализируемым изображением символа, за ними следуют графемы с меньшей степенью сходства, и так далее, в порядке убывания степени сходства. В ином варианте реализации метода, описанный массив голосов может использоваться, чтобы накопить голоса, полученные в ходе предварительной обработки изображения символа при использовании не одного, а множества кластеров, после чего список графем может быть упорядочен аналогичным образом. В других вариантах реализации метода голоса могут одновременно накапливаться для двух или более изображений символов. Другими словами, есть много возможных способов накопления голосов в массиве «votes», и есть много способов использования накопленных голосов для получения различных результатов, таких как упорядоченный по убыванию степени сходства список графем.
[89]Хотя настоящее изобретение описывается на примере конкретных вариантов осуществления, предполагается, что оно не будет ограничено только этими вариантами осуществления. Специалистам в данной области будут очевидны возможные модификации сущности настоящего изобретения. Например, любой из множества возможных вариантов осуществления структур данных и методов, используемых для предварительной обработки в соответствии с обобщенным третьим вариантом осуществления системы OCR, описанным выше, может быть достигнут путем изменения любого из различных параметров проектирования и реализации, среди которых: структуры данных, структуры управления, модульное исполнение, язык программирования, используемая операционная система и аппаратное обеспечение, а также многие другие подобные параметры проектирования и реализации.
[90]Следует понимать, что представленное выше описание раскрытых вариантов осуществления предоставлено для того, чтобы дать возможность любому специалисту в данной области повторить или применить настоящее изобретение. Специалистам в данной области будут очевидны возможные модификации представленных вариантов осуществления, при этом общие принципы, представленные здесь, могут применяться к другим вариантам осуществления без отступления от сущности или объема описания. Таким образом, настоящее описание не ограничено представленными здесь вариантами осуществления, оно соответствует широкому кругу задач, связанных с принципами и новыми отличительными признаками, раскрытыми в настоящем документе.
