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

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

Иллюстрации

Показать все

Реферат

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

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

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

Досье № 4201/306517 «Система и способ для распознавания формы при рукописном вводе чернилами»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Фиг. 13 - представление группирования числа штрихов контейнера-кандидата в соответствии с одним из аспектов настоящего изобретения,

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

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

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

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

Фиг. 18А-18В - представление, иллюстрирующее обнаружение соединительного звена на сетке изображения в соответствии с одним из аспектов настоящего изобретения,

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

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

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

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

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

Фиг. 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 обнаружения диаграмм могут быть включены в блок 206 распознавания формы. Либо функции блока 212 обнаружения контейнера могут быть реализованы отдельным компонентом.

Анализатор 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 показано обобщенное представление структурного соотношения в рукописных объектах в рукописном вводе чернилами для использования при выполнении обнаружения и распознавания формы рукописных объектов. Корневой объект 402 может представлять рукописный ввод чернилами, такой как страница рукописного ввода чернилами, которая может включать в себя один или более нарисованных объектов, например таких как объекты 404 и 406. Нарисованный объект 404 может иметь связанное с ним содержимое, такое как текст, структурно представленный абзацем 408, выполненным из строки 408, имеющей слово 412, образованное штрихами 414. Нарисованные объекты 404 и 406 могут быть обнаружены и распознаны путем выполнения обнаружения и распознавания формы рукописных объектов в рукописном вводе чернилами.

Рукописные объекты могут представлять собой рисунки, такие как диаграмма или график, в типовом случае включающие в себя контейнеры и соединительные звенья. На фиг. 5А-5С показаны примеры типов контейнеров в рукописном вводе чернилами, поддерживаемых при обнаружении и распознавании формы рукописных объектов в рукописном вводе чернилами. Поддерживаемые контейнеры, которые могут быть обнаружены и распознаны, могут являться любым типом контейнера, который может образовывать замкнутую область. Примерами таких контейнеров являются контейнер 502 на фиг. 5А, контейнер 504 на фиг. 5В и контейнер 506 на фиг. 5С. Содержимое, такое как текст, может быть включено в замкнутую область контейнера. На фиг. 6А-6D показаны примеры типов соединительных звеньев в рукописном вводе чернилами, поддерживаемых при обнаружении и распознавании формы рукописных объектов в рукописном вводе чернилами. Поддерживаемые типы соединительных звеньев, которые могут обнаруживаться и распознаваться, могут представлять собой любой тип соединительного звена, соединяющего два или более контейнера. Такое соединительное звено может не включать в себя стрелок, подобно соединительному звену 606 на фиг. 6А, или включать в себя одну стрелку, как соединительное звено 612 на фиг. 6В, или две стрелки, как соединительное звено 618 на фиг. 6С, или три стрелки, как соединительное звено 626 на фиг. 6D. Соединительное звено может включать в себя столько стрелок, сколько имеется контейнеров, которые оно соединяет.

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

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