Система и способ для распознавания формы рукописных объектов

Система и способ для распознавания формы рукописных объектов

Иллюстрации

Показать все

Реферат

Ссылки на связанные заявки

Настоящее изобретение заявляет приоритет предварительной патентной заявки США № 60/505,867 от 24 сентября 2003, включенной в настоящее описание во всей свой полноте.

Настоящее изобретение связано со следующими патентными заявками США, поданными одновременно с настоящей заявкой и включенными в настоящее описание во всей их полноте.

Досье № 4181/186706 «Система и способ для обнаружения рукописного объекта при рукописном вводе чернилами».

Досье № 4191/306517 «Система и способ для обнаружения списка при рукописном вводе чернилами».

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

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

Предшествующий уровень техники

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Фиг.10 - обобщенное представление штрихов формы с максимальным вписанным многоугольником в пределах конвексной (выпуклой) оболочки вокруг формы в соответствии с одним из аспектов настоящего изобретения.

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

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

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

Фиг.14 - обобщенное представление соединительного звена между двумя контейнерами в соответствии с одним из аспектов настоящего изобретения.

Фиг.15 - обобщенное представление примеров объединения линий или фрагментов линий скелета в соответствии с одним из аспектов настоящего изобретения.

Детальное описание

Пример операционной среды

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

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

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

На фиг.1 представлена приведенная для примера система для реализации изобретения, включающая в себя универсальное вычислительное устройство в форме компьютера 110. Компоненты компьютера 110 могут включать в себя, не ограничиваясь указанным, блок 120 обработки, системную память 130 и системную шину 121, которая связывает различные системные компоненты, включая системную память, с блоком 120 обработки. Системная шина 121 может быть любой из различных типов шинных структур, включая шину памяти или контроллер памяти, шину периферийных устройств, локальную шину, использующую любую из разнообразных шинных архитектур. В качестве примера, но не ограничения, такие архитектуры включают в себя шину ISA (Архитектура, соответствующая промышленному стандарту), шину MCA (Микроканальная архитектура), усовершенствованную шину ISA (EISA), локальную шину VESA (Ассоциации по стандартам в области видео электроники), шину соединения периферийных компонентов (PCI), также известную как шина Mezzanine.

Компьютер 110 в типовом случае включает в себя множество считываемых компьютером сред (носителей). Считываемые компьютером носители могут представлять собой любые известные носители, к которым компьютер 110 может осуществлять доступ, и включают в себя энергозависимые и энергонезависимые носители, съемные и несъемные носители. К примеру, но не в качестве ограничения, считываемые компьютером носители могут содержать компьютерные носители записи и коммуникационную среду. Компьютерные носители записи включают в себя энергозависимые и энергонезависимые носители, съемные и несъемные носители, реализованные любым методом или по любой технологии для хранения информации такой, как считываемые компьютером команды, структуры данных, программные модули или иные данные. Компьютерные носители записи содержат, не ограничиваясь указанным, оперативную память (RAM, ОЗУ), постоянную память (ROM, ПЗУ), электронно-стираемую программируемую постоянную память (EEPROM, ЭСППЗУ), память с групповой перезаписью (флэш-память) или другие технологии памяти, CD-ROM, универсальные цифровые диски (DVD) или иные устройства памяти на оптических дисках, магнитных кассетах, магнитных лентах, устройства памяти на магнитных дисках или иные магнитные устройства памяти, или любые иные носители, которые могут быть использованы для хранения желательной информации и к которым может быть обеспечен доступ компьютера 110. Коммуникационная среда (среда передачи) в типовом случае воплощает считываемые компьютером команды, структуры данных, программные модули или иные данные в модулированном сигнале данных, таком как несущее колебание или иной транспортный механизм (механизм передачи), и включает в себя любую среду доставки информации. Термин «модулированный сигнал данных» означает сигнал, у которого одна или более характеристик установлены или изменяются таким образом, чтобы кодировать информацию в сигнале. В качестве примера, но не ограничения, коммуникационная среда включает в себя проводные среды, такие как проводная сеть или прямое проводное соединение, и беспроводную среду передачи, такую как акустическая, радиочастотная, инфракрасная и другая беспроводная среда передачи. Комбинации любых вышеуказанных сред также должны быть включены в объем носителей (сред), считываемых компьютером.

Системная память 130 включает в себя компьютерный носитель записи в форме энергозависимой и/или энергонезависимой памяти такой, как постоянная память (ПЗУ, ROM) 131 и оперативная память (ОЗУ, RAM) 132. Базовая система ввода/вывода (BIOS) 133, содержащая базовые подпрограммы, которые способствуют переносу информации между элементами в компьютере 110, например, при запуске, в типовом случае сохранена в ПЗУ 131. ОЗУ 132 в типовом случае содержит данные и/или программные модули, которые непосредственно доступны и/или обрабатываются блоком 120 обработки. В качестве примера, но не ограничения, на фиг.1 показаны операционная система 134, прикладные программы 135, другие программные модули 136 и программные данные 137.

Компьютер 110 может также включать в себя другие съемные/ несъемные, энергозависимые/энергонезависимые компьютерные носители записи. Например, на фиг.1 показан дисковод 141 жестких дисков для считывания с несъемного, энергонезависимого магнитного носителя и записи на него, дисковод 151 магнитных дисков для считывания со съемного энергонезависимого магнитного диска 152 и записи на него и дисковод 155 оптических дисков для считывания со съемного энергонезависимого оптического диска 156 или записи на оптический диск, такой как, например, ПЗУ на компакт-диске (CD-ROM) или иные оптические носители записи. Другие съемные и несъемные, энергозависимые и энергонезависимые компьютерные носители записи, которые могут быть использованы в приведенной для примера операционной среде, включают в себя, не ограничиваясь указанным, кассеты на магнитных лентах, карты флэш-памяти, DVD, цифровые видео магнитные ленты, твердотельные ОЗУ, твердотельные ПЗУ и т.п. Дисковод 141 жестких дисков в типовом случае соединен с системной шиной 121 посредством интерфейса несъемной памяти, такого как интерфейс 140, и дисковод 151 магнитных дисков и дисковод 155 оптических дисков соединены с системной шиной 121 в типовом случае посредством интерфейса схемной памяти, такого как интерфейс 150.

Дисководы и связанные с ними считываемые компьютером носители, описанные выше и показанные на фиг.1, обеспечивают хранение считываемых компьютером команд, структур данных, программных модулей и других данных для компьютера 110. На фиг.1, например, показано, что дисковод 141 жесткого диска хранит операционную систему 144, прикладные программы (приложения) 145, другие программные модули 146 и программные данные 147. Заметим, что эти компоненты могут быть теми же самыми или отличающимися от операционной системы 134, прикладных программ 135, других программных модулей 136 и программных данных 137. Операционная система 144, прикладные программы 145, другие программные модули 146 и программные данные 147 обозначены отличающимися ссылочными позициями для иллюстрации того, что они, как минимум, являются другими копиями. Пользователь может вводить команды и информацию в компьютер 110 посредством устройств ввода, например, планшета или электронного цифрового преобразователя 164, микрофона 163, клавиатуры 162 и координатно-указательного устройства 161, такого как мышь, трекбол или сенсорная панель. Другие устройства ввода (не показаны на фиг.1) могут включать в себя джойстик, игровую панель, спутниковую параболическую антенну, сканер или другие устройства, включая устройство, содержащее биометрический датчик, датчик окружающей среды, датчик положения и другие типы датчиков. Эти и другие устройства ввода часто соединяются с блоком 120 обработки через интерфейс 160 пользовательского ввода, связанный с системной шиной, но могут быть соединены и посредством других интерфейсов и структур шин, таких как параллельный порт, игровой порт или универсальная последовательная шина (USB) и т.д. Монитор 191 или иное устройство отображения также соединено с системной шиной 121 через интерфейс, например, такой как видеоинтерфейс 190. Монитор 191 может быть объединен с сенсорной панелью или подобным средством. Монитор и/или сенсорная панель могут быть физически связаны с корпусом, в котором размещается компьютер 110, например персональный компьютер планшетного типа. Кроме того, компьютеры, такие как компьютер 110, также могут включать в себя другие периферийные устройства вывода, например громкоговорители 195 и принтер 196, которые могут быть соединены через интерфейс 194 устройств вывода или подобное средство.

Компьютер 110 может работать в сетевой среде с использованием логических соединений с одним или более удаленными компьютерами, такими как удаленный компьютер 180. Удаленный компьютер 180 может представлять собой ПК, портативное устройство, сервер, маршрутизатор, сетевой ПК, одноранговое устройство или другой обычный сетевой узел и в типовом случае включает в себя многие или все из элементов, описанных выше применительно к компьютеру 110, хотя на фиг.1 показано только устройство 181 памяти. Логические соединения, показанные на фиг.1, включают в себя локальную сеть (LAN) 171 и глобальную сеть (сеть широкого охвата - WAN) 173, но могут включать в себя и другие сети. Такие сетевые среды являются общеизвестными в офисах, компьютерных сетях предприятий, интранетах и в Интернет. При использовании в сетевой среде локальной сети (LAN) компьютер 110 соединяется с локальной сетью 171 через сетевой интерфейс или адаптер 170. При использовании в сетевой среде глобальной сети (WAN) компьютер 110 в типовом случае включает в себя модем 172 или иное средство для установления связи в глобальной сети 173, такой как Интернет. Модем 172, который может быть внутренним или внешним, соединен с системной шиной 121 через интерфейс 160 пользовательского ввода или иной подходящий механизм. В сетевой среде программные модули, изображенные по отношению к компьютеру 110, или их части могут быть сохранены в удаленном устройстве памяти. В качестве примера, но не ограничения, фиг. 1 иллюстрирует удаленные прикладные программы 185 как хранящиеся в устройстве 181 памяти. Следует иметь в виду, что показанные сетевые соединения приведены для примера, и что могут быть использованы и другие средства установления канала связи между компьютерами.

Распознавание формы рукописных объектов

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

Более конкретно, система и способ могут обеспечивать распознавание рукописных форм или нарисованных контейнеров и соединительных звеньев между контейнерами. Термин «контейнер», как он используется в настоящем описании, означает любой замкнутый нарисованный объект. Термин «соединительное звено», как он используется в настоящем описании, означает любой нарисованный объект, соединяющий контейнеры. Понятно, что различные блок-схемы, схемы алгоритмов и сценарии, упоминаемые в настоящем описании, приведены только для примера, и существуют и многие другие сценарии, в которых применимо настоящее изобретение.

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

Анализатор 202 рукописного ввода чернилами может анализировать любой рукописный ввод чернилами, включая нарисованный объект. Анализатор 202 рукописного ввода чернилами может включать в себя оперативно подключаемый блок 204 обнаружения диаграмм и оперативно подключаемый блок 206 распознавания формы. В общем случае блок 204 обнаружения диаграмм и блок 206 распознавания формы могут представлять собой исполняемый программный код любого типа, такой как компонент ядра, прикладная программа, связанная библиотека, объект и т.д. Блок 204 обнаружения диаграмм может включать в себя оперативно подключаемый блок 212 обнаружения контейнера и оперативно подключаемый блок 214 обнаружения соединительного звена, а блок 206 распознавания формы может включать в себя оперативно подключаемый блок 208 распознавания контейнера и оперативно подключаемый блок 210 распознавания соединительного звена. Блок 208 распознавания контейнера может включать в себя любое число оперативно подключаемых классификаторов, таких как классификатор 216 эллипса/окружности, классификатор 218 многоугольника, классификатор 220 треугольника, классификатор 222 четырехугольника и т.д. Блок 210 распознавания соединительного звена может включать в себя любое число оперативно подключаемых распознавателей, таких как распознаватель 224 скелета, распознаватель 226 стрелки и т.д. Каждый из этих компонентов также может представлять собой исполняемый программный код любого типа, такой как компонент ядра, прикладная программа, связанная библиотека, объект и т.д.

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

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

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

На этапе 304 для группы штрихов рисунка может выполняться обнаружение диаграммы путем поиска всех штрихов, которые могут принадлежать к нарисованному объекту. Таким образом, пользователь может рисовать диаграммы и блок-схемы свободно, без ограничений при рукописном вводе. Например, одна форма может иметь много штрихов, и порядок ввода штрихов может быть произвольным. Кроме того, штрихи могут перерываться без слияния или перекрываться со слиянием. В любом таком случае система обеспечивает автоматическое обнаружение корректных форм. В одном варианте для представления диаграмм и блок-схем алгоритмов может использоваться гиперграф, за счет чего обеспечивается полное представление соотношений между контейнерами и соединительными звеньями. Таким образом, в данном варианте принимаются во внимание и соединители, которые могут соединять более двух контейнеров.

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

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

На фиг.4 представлена блок-схема, представляющая возможный вариант осуществления этапов, выполняемых в процедуре распознавания формы контейнеров и соединительных звеньев, обозначенной этапом 306. Распознавание контейнера может выполняться на этапе 402 для каждого контейнера, чтобы идентифицировать замкнутые формы, включая окружности, треугольники, четырехугольники, пятиугольники, шестиугольники и т.д. Более того, могут распознаваться конкретные типы форм, например, отличающие окружность от эллипса или отличающие равнобедренный треугольник от равностороннего или прямоугольного треугольника. В качестве другого примера, могут распознаваться различные формы четырехугольников, такие как трапецоид, параллелограмм, ромб, прямоугольник и квадрат.

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

На этапе 404 может выполняться распознавание соединителя для каждого соединителя, чтобы идентифицировать форму незамкнутых соединителей, включая скелеты (основы, каркасы), стрелки и т.д. В одном варианте для аппроксимации скелета могут использоваться полилинии. В этом варианте блок 210 распознавания соединительного звена могут обрабатывать, например, продолжения (продления) штрихов скелета, перекрывающиеся со слиянием штрихи скелета и перекрывающиеся без слияния штрихи скелета. После распознавания скелета соединительного звена может быть распознана стрелка на одном или обоих концах скелета. Блок 210 распознавания соединительного звена может обратиться к блоку 224 распознавания скелета и/или блоку 226 распознавания стрелки для идентификации скелета и стрелки соединительного звена соответственно.

На Фиг.5 приведено обобщенное представление дерева решений, которое может объединять глобальные статистические признаки и основанные на правилах описания конкретных форм для использования при распознавании формы. Штрихи 502, сгруппированные вместе как принадлежащие контейнеру, могут быть введены в процедуру проверки 504 на кругообразность, чтобы определить, с какой вероятностью форма штрихов может представлять круг или эллипс. Проверка 504 на кругообразность может затем определять то, следует ли применять классификатор 506 эллипса/окружности или классификатор 508 многоугольника для идентификации формы штрихов 502. Классификатор 506 эллипса/окружности может определить, может ли форма штрихов представлять собой эллипс 510 или окружность 512. Классификатор 508 многоугольника может определить, может ли форма штрихов представлять собой пятиугольник 518 или шестиугольник 520, или следует применить классификатор 514 треугольников или классификатор 516 четырехугольников для идентификации формы штрихов 502. Классификатор 514 треугольников может определить, может ли форма штрихов представлять собой треугольник, а также может использовать основанные на правилах описания, которые обеспечат более детальную информацию для различения того, является ли треугольник равнобедренным треугольником 522, равносторонним треугольником 524 или прямоугольным треугольником 526. Аналогичным образом, классификатор 516 четырехугольников может определить, может ли форма штрихов представлять собой четырехугольник, а также может использовать основанные на правилах описания, которые обеспечат более детальную информацию для различения того, является ли четырехугольник квадратом 528, прямоугольником 530, ромбом 532, трапецоидом 534 или параллелограммом 536.

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

На этапе 602 выполняется проверка на кругообразность, чтобы определить, с какой вероятностью форма штрихов может представлять круг или эллипс. Если результат проверки на кругообразность показывает на этапе 604, что форма, вероятно, является окружностью или эллипсом, то на этапе 606 выполняется процесс распознавания окружности или эллипса. Если результат проверки на кругообразность показывает на этапе 604, что форма едва ли является окружностью или эллипсом, то на этапе 608 выполняется процесс распознавания многоугольника. Процесс, выполняемый на этапе 608 для распознавания многоугольника, может определить, что многоугольник может представлять собой треугольник или четырехугольник. Если процесс, выполняемый для распознавания многоугольника, определяет на этапе 610, что многоугольник может представлять собой треугольник, то на этапе 612 выполняется процесс для распознавания конкретного типа или подкласса треугольника. Например, конкретным типом треугольника может быть равнобедренный треугольник 522, равносторонний треугольник 524 или прямоугольный треугольник 526. Однако если процесс распознавания многоугольника, выполняемый на этапе 614, показывает, что многоугольник может представлять собой четырехугольник, то на этапе 616 может выполняться процесс распознавания конкретного типа или подкласса четырехугольника. Например, конкретный тип четырехугольника может быть квадратом 528, прямоугольником 530, ромбом 532, трапецоидом 534 или параллелограммом 536. Процесс, выполняемый на этапе 608 для распознавания многоугольника, может указать на то, что многоугольник может представлять собой пятиугольник 518 или шестиугольник 520. Если результат выполнения процесса распознавания многоугольника показывает на этапе 618, что многоугольник может представлять собой пятиугольник, то на этапе 620 выполняется обработка для распознавания пятиугольника. Если результат выполнения процесса распознавания многоугольника показывает на этапе 622, что многоугольник может представлять собой шестиугольник, то на этапе 624 выполняется обработка для распознавания пятиугольника.

На фиг.7 показана блок-схема, п