СИСТЕМА И СПОСОБ ДЛЯ ОБНАРУЖЕНИЯ РУКОПИСНЫХ ОБЪЕКТОВ В РУКОПИСНОМ ВВОДЕ ЧЕРНИЛАМИ Российский патент 2009 года по МПК G06K9/46 G06T7/00 

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

Настоящее изобретение заявляет приоритет предварительной патентной заявки США № 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 может выполняться обнаружение содержимого для любого контейнера. На этом этапе может быть определено, принадлежит ли какое-либо содержимое, например распознанное слово, контейнеру, путем вычисления области пересечения ограничивающего его окна с каждым контейнером.

На фиг. 9 показана блок-схема, представляющая возможный вариант осуществления этапов, выполняемых при пространственном поиске для обнаружения контейнеров. На этапе 902 может генерироваться сетка изображения, и штрихи нарисованного объекта могут быть позиционированы на этой генерированной сетке. В одном варианте осуществления размер сетки может быть установлен на соответствующее значение, чтобы исключить промежутки между штрихами контейнеров, но при этом сохранить пустую область внутри контейнеров. Для выбора соответствующего значения размер сетки может быть эмпирически определен путем проверки тестовых данных, чтобы гарантировать обнаружение максимально возможного количества контейнеров. В результате такого определения размер сетки может быть установлен, например, на 2.5 мм. Ячейки, которые пересекаются с штрихом рисунка, могут быть маркированы на этапе 904. Для проверки того, какие ячейки пересеваются с штрихами рисунка, штрихи рисунка могут быть повторно дискретизированы в соответствии с регулярным размером шага дискретизации, и положения, где точки повторной дискретизации находятся на сетке изображения, могут быть подвергнуты проверке. Как показано на фиг. 10А, ячейки, которые пересекаются с штрихами рисунка контейнера 1004, соединительного звена 1006 и контейнера 1008, маркированы на сетке 1002 изображения. Контейнеры 1004 и 1008 становятся соединенными 8-образными смежными областями 1004 и 1008 на сетке 1002 изображения.

Начиная с внешних краев сетки изображения, самые крайние ячейки на этапе 906 могут быть заполнены заливкой до достижения маркированных ячеек, которые пересекаются с нарисованными штрихами. Как показано на фиг. 10В, контейнеры 1004 и 1008 могут представляться как островки пустых ячеек на сетке 1002 изображения. На этапе 908 островки пустых ячеек могут быть заполнены заливкой. Для каждого островка одна внутренняя пустая ячейка может быть выбрана в качестве начальной ячейки, начиная от которой все соседние пустые ячейки могут быть заполнены заливкой до достижения границы, образованной ячейками, пересекающими некоторые штрихи. При достижении границы островка штрихи, которые образуют контейнер-кандидат, могут регистрироваться. Например, на фиг. 10С показаны островки контейнеров 1004 и 1008 в виде заполненных заливкой. Границы вокруг заполненных заливкой островков пересекают нарисованные штрихи этих контейнеров-кандидатов.

Этап заполнения заливкой островков пустых ячеек может привести к идентификации контейнеров-кандидатов, которые могут не быть действительными контейнерами. Поэтому контейнеры-кандидаты могут проверяться на этапе 910, чтобы подтвердить, что они являются действительными контейнерами. Нарисованные штрихи каждого контейнера-кандидата могут включать в себя штрихи, которые находятся вне граничных ячеек островка, заполненного заливкой. Например, на фиг. 11А показана сетка 1002 изображения с контейнером-кандидатом 1108, который имеет штрихи 1114 и 1112, которые находятся вне граничных ячеек 1106, окружающих островок 1110, заполненный заливкой. Для всех ячеек, которые пересекают один штрих контейнера-кандидата, ячейки, которые являются смежными с ячейкой островка, заполненного заливкой, могут быть определены как действительные, а прочие могут быть определены как недействительные. Если отношение недействительных ячеек к действительным ячейкам больше, чем эмпирически установленное значение, например 0.2, то соответствующий штрих может быть определен как недействительный. Такие недействительные штрихи могут быть удалены. Например, штрихи 1104 и 112 на фиг. 11А являются недействительными штрихами. После удаления всех недействительных штрихов контейнер-кандидат является действительным, если он остается по-прежнему замкнутым (то есть образует замкнутую область). Для определения того, является ли контейнер по-прежнему замкнутым, могут использоваться те же этапы, что и использованные для обнаружения контейнера согласно фиг. 9. То есть островки пустых ячеек контейнера-кандидата могут быть заполнены заливкой, и если достижимы некоторые пустые ячейки вне островка, то контейнер-кандидат может быть определен как уже не замкнутый.

Действительный замкнутый контейнер может включать в себя другие нарисованные штрихи, такие как внутренние нарисованные штрихи, или может использовать штрихи совместно с другим контейнером-кандидатом. В случае, когда действительный контейнер включает в себя внутренние нарисованные штрихи, эти внутренние нарисованные штрихи могут интерпретироваться согласно одному варианту осуществления как содержимое этого контейнера, как показано на фиг. 11В. Контейнер 1116 на сетке 1114 изображения включает в себя внутренние нарисованные штрихи 1118, которые могут интерпретироваться как содержимое контейнера 1116. В случае, когда контейнер-кандидат использует нарисованные штрихи совместно с другим контейнером-кандидатом, эти совместно использованные штрихи в одном варианте осуществления могут быть отделены и определены как принадлежащие одному из контейнеров-кандидатов. Например, фиг. 11С иллюстрирует контейнеры-кандидаты 1122 и 1124 на сетке 1120 изображения, где часть действительных границ используется совместно с другим контейнером-кандидатом. Имеются два нарисованных штриха, которые пересекают ячейки совместно используемой части границы. Для каждого штриха в совместно используемой части границы точки нарисованного штриха повторно дискретизируются, и вычисляется среднее расстояние до центра каждого контейнера-кандидата. Нарисованный штрих принимается как принадлежащий контейнеру-кандидату с кратчайшим средним расстоянием до его центра. Если другой контейнер-кандидат в результате потери нарисованного штриха оказывается незамкнутым, то он может стать недействительным контейнером-кандидатом. Однако, как показано на фиг. 11С, каждый из двух нарисованных штрихов, пересекающих совместно используемую часть действительной границы контейнеров-кандидатов 1122 и 124, может быть принят как принадлежащий контейнеру-кандидату с кратчайшим средним расстоянием до его центра. Оба контейнера-кандидата могут остаться замкнутыми и останутся действительными, поскольку к каждому из них отнесен один из двух нарисованных штрихов.

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

(v _b >V _B , v _a >V _A ) в противном случае

где v _b - коэффициент действительной границы; v _a - коэффициент действительной площади; s(i,j)- число штрихов; w ₁ , w ₂ , w ₃ - весовые коэффициенты; V _B и V _A - пороговые значения для v _b и v _a соответственно. Коэффициент действительной границы может быть определен следующим образом: v _b = длина действительной границы/общая длина границы. Площадь недействительной области контейнера-кандидата может быть определена как область, которая пересекает некоторые внутренние нарисованные штрихи, которые не принадлежат контейнеру-кандидату, а площадь действительной области зоны может быть определена как площадь внутри контейнера-кандидата, которая меньше любых площадей недействительных областей. Коэффициент действительной площади может быть определен следующим образом: v _b = площадь действительной области/общая площадь. Фиг. 12 показывает пример площади 1204 действительной области контейнера-кандидата 1202, которая включает в себя недействительную область, которая пересекает внутренние нарисованные штрихи 1206. Специалистам в данной области техники должно быть понятно, что признаки длины действительной границы, общей длины границы, площади действительной области и полной площади могут быть определены с использованием сетки изображения на основе того же самого процесса, который использовался для идентификации границ контейнеров-кандидатов при выполнении пространственного поиска, как описано выше со ссылкой на фиг. 9. Могут быть использованы эмпирически установленные значения 0,15 и 0,25 для V _B и

V _A и эмпирически установленные значения 0,4, 0,4 и 0,2 для весовых коэффициентов w ₁ , w ₂ , w ₃ . Число штрихов s(i,j) может быть определено как s(i,j)=j-i+1. Признак числа штрихов может быть использован для того, чтобы исключить некорректное группирование любых мелких штрихов рядом с контейнером, как показано на фиг. 13. Число штрихов, используемых для формирования контейнера 1302, может быть определено для окружающей области 1308 и может отличаться от числа штрихов, найденных в области 1306, которая образует контейнер 1303 и часть соединительного звена 1304.

На фиг. 14 показана блок-схема, представляющая возможный вариант осуществления этапов, выполняемых при поиске во временном порядке. На этапе 1402 может быть определен коэффициент действительной границы v _b . На этапе 1404 может быть определен коэффициент действительной площади v _a. На этапе 1406 может быть определено число штрихов s(i,j). На этапе 1408 из последовательности штрихов в рукописном вводе могут быть определены контейнеры. В одном варианте осуществления контейнеры могут быть найдены в последовательности (m,n) штрихов в рукописном вводе путем решения P(m,n). Для сегментирования последовательности (m,n) штрихов в рукописном вводе на k подсегментов i₁, i₂,..,i_k, P(m,n) может быть определено следующим образом:

Штрихи рукописного вода могут быть сгруппированы в корректные контейнеры путем вычисления P(m,n). В одном варианте осуществления для вычисления P(m,n) может быть использовано динамическое программирование, причем P(m,n) может быть выражено как рекурсивная процедура следующим образом:

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

После выполнения пространственного поиска и поиска во временном порядке для обнаружения контейнеров может быть выполнено обнаружение содержимого в сетке изображения для любого содержимого, такого как распознанное слово, которое принадлежит контейнеру. Например, написанное слово может быть проверено на принадлежность контейнеру путем вычисления площади пересечения ограничивающего его окна (прямоугольника) и граничных ячеек контейнера. На фиг. 15 показана блок-схема, представляющая возможный вариант осуществления этапов, выполняемых при обнаружении содержимого контейнера. На этапе 1502 для любого текста, идентифицированного на сетке изображения, может быть определен минимальный ограничивающий прямоугольник и его площадь. На этапе 1504 может быть определена площадь пересечения минимального ограничивающего прямоугольника с каждым контейнером. На этапе 1506 может быть вычислено отношение этой площади пересечения и площади минимального ограничивающего прямоугольника. Контейнер с максимальным полученным коэффициентом пересечения может быть выбран на этапе 1508 в качестве контейнера, к которому принадлежит содержимое. Например, на фиг. 16 показан ограничивающий прямоугольник 1606, окружающий слово “hello” на сетке 1602 изображения. Слово “hello” может быть определено, как принадлежащее контейнеру 1604, поскольку коэффициент пересечения с контейнером 1604 больше, чем коэффициент пересечения с контейнером 1608. В одном варианте осуществления может потребоваться, чтобы коэффициент пересечения превышал установленное эмпирически пороговое значение 0,55.

После того как любые контейнеры и связанное с ними содержимое обнаружены на сетке изображения, может быть выполнено обнаружение соединительных звеньев. На фиг. 17 показана блок-схема, представляющая возможный вариант осуществления этапов, выполняемых для обнаружения соединительных звеньев в рукописном вводе чернилами. В принципе, поиск может быть выполнен по сетке изображения, которая была маркирована контейнерами для обнаружения любых соединительных звеньев среди ячеек неподсоединенных рукописных штрихов, которые включают в себя все «неконтейнерные» (не принадлежащие контейнерам) штрихи. Поскольку некоторые пользователи могут иметь привычку рисовать короткие соединительные звенья, которые могут оказаться на расстоянии от контейнеров, то контейнеры можно расширить, чтобы соединительные звенья оказались смежными с соответствующими контейнерами. На фиг. 18А показана сетка 1802 изображения с заполненными заливкой ячейками между несвязанными ячейками, пересекающимися с соединительным звеном 1806, и маркированными границами контейнеров 1804 и 1808. Для обнаружения такого соединительного звена отдельные контейнеры, которые не являются смежными с неподсоединенными нарисованными штрихами, могут быть на этапе 1702 расширены маркированными ячейками, окружающими границу контейнеров. Процесс расширения может быть остановлен при достижении либо несвязанной ячейки, либо другого контейнера. Таким путем соединительные звенья могут стать смежными с соответствующими расширенными контейнерами, как показано на фиг. 18В. У контейнеров, показанных на сетке 1810 изображения на фиг. 18В, границы окружены маркированными ячейками для создания расширенных контейнеров 1812 и 1816. В результате ячейки, пересекающиеся с неподсоединенными нарисованными штрихами соединительного звена 1814, могут теперь оказаться смежными с ячейками расширенных контейнеров.

На этапе 1704 по фиг. 17 несвязанные ячейки могут быть заполнены заливкой. Одна несвязанная ячейка может быть выбрана в качестве начальной ячейки, начиная с которой все смежные несвязанные ячейки могут быть заполнены заливкой. Если эти заполненные заливкой ячейки достигают двух или более контейнеров, включая расширенные контейнеры, то соответствующие нарисованные штрихи записываются как соединительное звено-кандидат. Как показано на сетке 1902 изображения на фиг. 19А, заполненные заливкой ячейки между расширенными контейнерами 1904 и 1908 образуют соединительное звено-кандидат 1906. В одном варианте осуществления границы контейнеров сетки изображения могут уже быть смежными с неподсоединенными нарисованными штрихами, которые образуют соединительное звено. В этом случае несвязанные ячейки могут быть заполнены заливкой без предварительного расширения контейнеров. На фиг. 19В иллюстрируется этот случай для сетки 1910 изображения, где заполненные заливкой ячейки могут образовать соединительное звено-кандидат 1914 между контейнерами 1212 и 1916 без использования расширения контейнеров.

Этап заполнения заливкой несвязанных ячеек нарисованных штрихов может привести в результате к идентификации соединительных звеньев-кандидатов, которые могут не быть действительными соединительными звеньями. Поэтому соединительные звенья-кандидаты могут быть проверены на этапе 1706 для подтверждения того, что они являются действительными соединительными звеньями. Соединительное звено-кандидат может быть недействительным, если соединительное звено-кандидат имеет нарисованные штрихи, которые не соединяются с контейнером. В одном варианте осуществления для обнаружения того, что могут иметься нарисованные штрихи соединительного звена-кандидата, которые не соединяются с контейнером, может использоваться скользящее окно, перемещаемое вдоль соединительного звена-кандидата, чтобы проверить, что число точек пересечения нарисованных штрихов с границей скользящего окна не превышает число смежных контейнеров, которые может соединять соединительное звено-кандидат. Размер скользящего окна может быть установлен на эмпирически установленную величину, чтобы избежать ложных пересечений с локальными флуктуациями. В одном варианте осуществления радиус окна может быть равен 4 мм. Предположим, например, что соединительное звено-кандидат соединяет N контейнеров (N>=2), и М есть число точек пересечения нарисованных штрихов соединительного звена-кандидата с границей скользящего окна, тогда соединительное звено-кандидат может рассматриваться как недействительное, если M>N в некоторой точке при перемещении скользящего окна вдоль соединительного звена-кандидата. Например, фиг. 20А иллюстрирует три положения скользящего окна 2004, перемещаемого вдоль соединительного звена-кандидата 2010, которое соединяет три контейнера: контейнер 2002, контейнер 2006 и контейнер 2008. В каждом показанном положении число точек пересечения меньше, чем число соединяемых контейнеров, которые может соединять соединительное звено-кандидат. Поскольку число точек пересечения не превышает число соединяемых контейнеров, то соединительное звено-кандидат является действительным. С другой стороны, на фиг. 20В иллюстрируется обнаружение недействительного соединительного звена-кандидата 2020, где число точек пересечения на границе скользящего окна 2014 больше, чем число соединяемых контейнеров 2012, 2016 и 2018. Соединительное звено-кандидат также может быть недействительным, если оно включает в себя нарисованный штрих, который не соединяется с контейнером. Например, на фиг. 20С иллюстрируется нарисованный штрих соединительного звена-кандидата 2030 в скользящем окне 2004, который не соединяется ни с одним из контейнеров 2022, 2026 и 2028. В результате соединительное звено-кандидат 2030 является недействительным соединительным звеном.

После того как контейнеры и соединительные звенья обнаружены, становятся понятными структурные взаимосвязи рукописного объекта. На фиг. 21 - обобщенное представление структурных взаимосвязей в рукописных объектах рукописных объектов в рукописном вводе чернилами для использования после выполнения обнаружения нарисованного объекта. Корневой объект 2002 может представлять рукописный ввод чернилами, такой как страница рукописного ввода чернилами, которая может включать в себя один или более нарисованных объектов, например таких как объекты 2106. Нарисованный объект, например, график (диаграмма) 2104, может быть обнаружен и распознан путем выполнения обнаружения и распознавания формы рукописных объектов в рукописном вводе чернилами. Диаграмма 2104 может быть образована контейнерами 2108 и 2110, которые соединяются соединительным звеном 2112. Контейнер 2108 может иметь связанное с ним содержимое, такое как текст, структурно представленный абзацем 2114, выполненным из строки 2116, имеющей слово 2118, образованное штрихами 2120.

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

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

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

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

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

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

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

4. Система по п.3, отличающаяся тем, что блок распознавания формы содержит блок распознавания контейнера, оперативно связанный с блоком распознавания формы.

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

6. Считываемый компьютером носитель, содержащий исполняемые компьютером программы, которые, при исполнении процессором, вызывают выполнение компьютерной системой по любому из пп.1-5 способа по любому из пп.7-34.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

34. Способ по п.33, отличающийся тем, что проверка того, что число точек пересечения штрихов соединительного звена-кандидата не превышает числа смежных контейнеров, которые может соединять соединительное звено-кандидат, включает использование скользящего окна, которое может перемещаться вдоль соединительного звена-кандидата.

35. Считываемый компьютером носитель, содержащий исполняемые компьютером команды для выполнения способа по п.7.

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