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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

P_ch ²/A_ch, где P_ch и A_ch представляют периметр и площадь выпуклой оболочки формы соответственно. Перед вычислением коэффициента сужения для формы штрихи формы могут быть масштабированы так, чтобы минимальный ограничивающий прямоугольник стал квадратом. Поскольку окружность может иметь минимальный коэффициент сужения 4·π, то как окружности, так и эллипсы могут иметь минимальный коэффициент сужения 4·π, где π определяется как отношение длины окружности к ее диаметру. На этапе 702 может определяться минимальный ограничивающий прямоугольник штрихов, и затем штрихи формы могут масштабироваться на этапе 704 таким образом, чтобы минимальный ограничивающий прямоугольник стал квадратом. Затем на этапе 706 может вычисляться выпуклая оболочка штрихов формы с использованием алгоритма Грэхэма (см. “Computational Geometry in C (2^nd Ed.), Joseph O'Rourke, Cambridge University Press, 1998, ISBN:0-521-64976-5). Затем коэффициент сужения P_ch ²/A_ch может быть вычислен на этапе 708. Результат вычисления коэффициент сужения P_ch ²/A_ch может сравниваться с пороговым значением на этапе 710. В одном варианте осуществления пороговое значение может быть выбрано равным 4·π·1.05. Если на этапе 712 определено, что коэффициент сужения P_ch ²/A_ch меньше или равен пороговому значению 4·π·1.05, то принимается решение, что форма может представлять собой окружность или эллипс, и затем на этапе 714 может применяться классификатор, чтобы обеспечить различение того, является ли форма замкнутого контейнера окружностью или эллипсом. Если на этапе 712 определено, что коэффициент сужения

P_ch ²/A_ch больше порогового значения 4·π·1.05, то принимается решение, что форма может представлять собой многоугольник, и затем на этапе 716 может применяться классификатор многоугольника, чтобы обеспечить различение типа многоугольника, форму которого может иметь замкнутый контейнер. Специалистам в данной области техники должно быть понятно, что для проверки кругообразности могут применяться другие пороговые значения и другие признаки.

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

На фиг.9 показана блок-схема, представляющая возможный вариант осуществления этапов, выполняемых классификатором для различения того, каким типом многоугольника может быть форма замкнутого контейнера. Проверка формы многоугольника может выполняться для каждого желательного типа n-стороннего многоугольника, чтобы определить форму многоугольника. В одном варианте проверка формы многоугольника может выполняться в отношении треугольника, четырехугольника, пятиугольника и шестиугольника. Для проверки формы многоугольника может быть установлено одно или более пороговых значений для сравнения результата выполнения проверки формы многоугольника для каждого желательного типа n-стороннего многоугольника, чтобы определить, каким n-сторонним многоугольником является распознаваемая форма. В одном варианте осуществления для определения формы многоугольника может использоваться отношение площадей A_n/A_ch, где A_n представляет площадь максимального n-стороннего многоугольника, вписанного в выпуклую оболочку, а A_ch представляет площадь выпуклой оболочки для штрихов. В этом варианте осуществления выпуклая оболочка штрихов может вычисляться с использованием алгоритма Грэхэма (см. “Computational Geometry in C (2^nd Ed.), Joseph O'Rourke, Cambridge University Press, 1998, ISBN:0-521-64976-5), и на этапе 902 может вычисляться площадь выпуклой оболочки штрихов. Затем для каждого желательного типа n-стороннего многоугольника на этапе 904 может вычисляться максимальный вписанный n-сторонний многоугольник и его площадь А_n. Максимальный вписанный n-сторонний многоугольник может вычисляться с использованием алгоритма Бойсе (см.J.E. Boice and D.P.Dobkin, Finding Extremal Polygons, SIAM Journal on Computing, 14(1):134-147, 1985). Например, могут быть вычислены максимальные вписанные треугольник, четырехугольник, пятиугольник, шестиугольник и их соответствующие площади А₃, А₄, А₅, А₆. На этапе 906 для каждого желательного типа n-стороннего многоугольника может быть вычислено отношение площадей A_n/A_ch. На этапе 908 отношение площадей A_n/A_ch для каждого желательного типа n-стороннего многоугольника может сравниваться с соответствующим пороговым значением. И, наконец, на этапе 910 n-сторонний многоугольник с наименьшим числом сторон, отношение площадей A_n/A_ch которого больше соответствующего порогового значения, может быть выбран в качестве типа многоугольника, который представляет форму замкнутого контейнера. В одном варианте пороговое значение для А₃, А₄, А₅, А₆ может быть выбрано как 0.73, 0.84, 0.93 и 0.94 соответственно. На фиг.10 показан пример штрихов формы 1002 с максимальным четырехугольником 1004, вписанным в выпуклую оболочку 1006, ограничивающую форму 1002. В этом примере отношение площадей вписанного четырехугольника и выпуклой оболочки может быть больше, чем соответствующее пороговое значение, и соответствовать меньшему числу сторон по сравнению с отношением площадей для других n-сторонних многоугольников, таких как пятиугольник и шестиугольник. Соответственно, форма может классифицироваться как четырехугольник.

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

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

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

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

На фиг.13 показана блок-схема, представляющая этапы, выполняемые для распознавания формы соединительного звена, идентифицированного в представлении рукописного ввода чернилами. Указанный ввод для распознавания формы соединительного звена может включать в себя штрихи и точки соединения с контейнерами, как показано на фиг.14, что может быть предварительно идентифицировано блоком обнаружения диаграмм. Точка соединения, как определено в настоящем описании, означает точку штрихов соединительного звена, которая имеет минимальное расстояние до контейнера. Например, как показано на фиг.14, может иметься точка 1404 соединения на каждом конце соединительного звена 1406, где точка соединения может связываться с одним из контейнеров 1402 и 1412. В общем случае каждое соединительное звено может включать в себя линию или кривую между точкой соединения или стрелкой и другой точкой соединения или стрелкой, указанная линия определена здесь как «скелет» (основа, каркас) 1410, и каждое соединительное звено может включать в себя стрелку 1410 на одном или обоих концах скелета.

При вычерчивании соединительного звена некоторые пользователи могут проводить скелет соединительного звена с использованием движения вперед и назад с перекрывающимися со слиянием штрихами. Другие пользователи могут сходным образом вычерчивать стрелку соединительного звена с использованием движения вперед и назад. Также некоторые пользователи могут вычерчивать скелет и стрелку соединительного звена одним штрихом. Поскольку пользователи могут вычерчивать скелет и стрелку одним штрихом, различные части штрихов могут анализироваться и распознаваться по отдельности. Соответственно на этапе 1302 на фиг.13 штрихи могут быть разбиты на сегменты в точках высокой кривизны, определяемых здесь как точки заострения (возврата). Путем анализа одного штриха как полилинии каждая неконечная точка штриха может формировать пересечение двух линейных сегментов. В одном варианте осуществления угол между двумя сегментами линии в каждой неконечной точке штриха может вычисляться, и штрихи могут разбиваться в точках, где соответствующий угол меньше, чем пороговое значение, такое как 80 градусов. Во избежание разбиения штриха на слишком много не несущих информации сегментов в местах локальных флуктуаций, в одном варианте осуществления штрихи могут сначала сглаживаться путем применения аппроксимации полилинии, предложенной Склански (см. Sklansky and Gonzalez V., Fast Polygonal Approximation of Digitized Curves, Pattern Recognition. Vol.12, pp.327-331, 1980), для упрощения и сглаживания штрихов.

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

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

На этапе 1306 может быть осуществлено объединение штрихов или сегментов штрихов скелета. Объединение штрихов или сегментов штрихов скелета может осуществляться для одного штриха или сегмента, отделенного от другого штриха или сегмента, для штриха или сегмента, перекрывающегося со слиянием с другим штрихом или сегментом, или для штриха или сегмента, перекрывающегося без слияния с другим штрихом или сегментом. Эти основные случаи показаны на фиг.15. Для каждого из них область 1508 объединения может быть определена путем построения четырехугольника, который может содержать концы отдельных штрихов или сегментов штрихов, которые могут формировать продолжение 1502 в результате объединения, или может содержать область перекрытия со слиянием перекрывающихся штрихов или сегментов штрихов, которые могут формировать продолжение 1504 перекрытия со слиянием в результате объединения, или может содержать область перекрытия без слияния перекрывающихся штрихов или сегментов штрихов, которые могут формировать продолжение 1506 перекрытия без слияния в результате объединения. Для объединения штрихов или сегментов штрихов скелета может быть определена количественная оценка (показатель) соединения для каждой пары штрихов или сегментов штрихов. В одном варианте осуществления показатель соединения может быть определен следующим образом:

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

для случае непрерывного продолжения,

где l - общая длина двух штрихов или фрагментов штрихов, w₁ и w₂ - весовые коэффициенты и d _m , l _m - ширина и длина определенной объединяемой области соответственно. В принципе, этот показатель соединения имеет большее значение, если два штриха или сегмента штриха расположены близко, и имеет меньшее значение, если штрихи или сегменты штрихов существенно разнесены друг от друга. Для всех штрихов или сегментов штрихов скелета процесс рекурсивного объединения выполняется путем объединения двух штрихов или сегментов штрихов скелета с наивысшим значением показателя соединения до тех пор, пока не останется пар штрихов, которые могут быть объединены.

На этапе 1308 каждый объединяемый штрих или сегмент штриха может быть нормализован для исключения локальных флуктуаций. В одном варианте для каждого объединяемого штриха или сегмента штриха скелета для нормализации может быть применена аппроксимации полилинии, предложенная Склански (см. Sklansky and Gonzalez V., Fast Polygonal Approximation of Digitized Curves, Pattern Recognition. Vol.12, pp.327-331, 1980). После того как последний объединяемый штрих скелета нормализован, может быть полностью генерирован результирующий скелет соединительного звена.

На этапе 1310 могут распознаваться штрихи стрелки или сегменты штрихов стрелок. В одном варианте осуществления может осуществляться проверка выпуклой оболочки штрихов или сегментов штрихов стрелок для определения, может ли форма быть треугольником. Такой признак, как отношение площадей A_n/A_ch, где A_n представляет площадь максимального вписанного треугольника, а A_ch представляет площадь выпуклой оболочки штрихов, может быть использован для определения формы треугольника. В этом варианте осуществления выпуклая оболочка штрихов может быть вычислена с использованием алгоритма Грэхэма (см. “Computational Geometry in C (2^nd Ed.), Joseph O'Rourke, Cambridge University Press, 1998, ISBN:0-521-64976-5), и затем может быть вычислена площадь A_ch выпуклой оболочки штрихов. Наибольший вписанный треугольник может быть вычислен с использованием с использованием алгоритма Бойсе (см.J.E. Boice and D.P.Dobkin, Finding Extremal Polygons, SIAM Journal on Computing, 14(1):134-147, 1985), и затем может быть вычислена его площадь A_n. Затем может быть вычислено отношение площадей A_n/A_ch, которое сравнивается с пороговым значением, например, близким к 1, чтобы определить, что штрихи или сегменты стрелки могут представлять собой треугольник.

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

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

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

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

Изобретение относится к системе и способу для распознавания формы рукописных объектов. Изобретение позволяет распознавать форму рукописных объектов вне зависимости от порядка ввода штрихов и/или от числа штрихов, требуемых для формирования любой заданный формы. Блок распознавания формы может распознавать рисунок, такой как диаграмма или график на рукописном вводе чернилами путем распознавания замкнутых контейнеров и/или незамкнутых соединителей на рисунке. Замкнутые контейнеры могут представлять любое число распознаваемых форм, включая окружности, эллипсы, треугольники, четырехугольники, пятиугольники, шестиугольники и т.д. Незамкнутые соединительные звенья могут быть любым типом соединительного звена, включая линии, кривые, стрелки и т.д. Могут использоваться полилинии для аппроксимирования скелета соединительного звена для обработки продолжений штрихов, перекрывающихся со слиянием штрихов и перекрывающихся без слияния штрихов скелета. С использованием настоящего изобретения пользователь может свободно рисовать диаграммы и блок-схемы алгоритмов без каких-либо ограничений, накладываемых на рукописный ввод. 3 н. и 28 з.п. ф-лы, 15 ил.

1. Компьютерная система (100) для распознавания рукописной формы, причем форма имеет один или более штрихов, и распознавание является независимым от порядка ввода и числа штрихов, содержащая
анализатор (202) рукописного ввода чернилами;
блок (204) обнаружения диаграммы, оперативно связанный с анализатором рукописного ввода чернилами, для группирования штрихов рисунка в независимые объекты в соответствии с их пространственным соотношением;
блок (206) распознавания формы, оперативно связанный с анализатором (202) рукописного ввода чернилами, предназначенный для приема рукописного ввода чернилами из анализатора (202) рукописного ввода чернилами, причем рукописный ввод чернилами означает один или более рукописных штрихов;
блок (208) распознавания контейнера, оперативно связанный с блоком (206) распознавания формы, для распознавания замкнутого контейнера (1402, 1412) в рукописном вводе чернилами;
блок (210) распознавания соединительного звена, оперативно связанный с блоком (206) распознавания формы, для распознавания соединительного звена (1406) в рукописном вводе чернилами, причем распознавание соединительного звена включает в себя сглаживание штрихов и затем разбиение штрихов соединительного звена на сегменты в точках заострения для идентификации частей скелета и частей стрелки, причем части штриха, которые имеют минимальное расстояние до центра выпуклой оболочки соединительного звена, идентифицированы как части скелета.

2. Система по п.1, в котором блок (204) обнаружения диаграммы содержит блок (212) обнаружения контейнера, оперативно связанный с блоком (204) обнаружения диаграммы.

3. Система по п.1, в которой блок (204) обнаружения диаграммы содержит блок (214) обнаружения соединительного звена, оперативно связанный с блоком (204) обнаружения диаграммы.

4. Система по п.1, в которой блок (208) распознавания контейнера содержит классификатор (216) эллипса/окружности, оперативно связанный с блоком распознавания контейнера.

5. Система по п.1, в которой блок (208) распознавания контейнера содержит классификатор (218) многоугольника, оперативно связанный с блоком распознавания контейнера.

6. Система по п.1, в которой блок (208) распознавания контейнера содержит классификатор (220) треугольника, оперативно связанный с блоком распознавания контейнера.

7. Система по п.1, в которой блок (208) распознавания контейнера содержит классификатор (222) четырехугольника, оперативно связанный с блоком распознавания контейнера.

8. Система по п.1, в которой замкнутый контейнер содержит окружность.

9. Система по п.1, в которой замкнутый контейнер содержит эллипс.

10. Система по п.1, в которой замкнутый контейнер содержит треугольник.

11. Система по п.1, в которой замкнутый контейнер содержит четырехугольник.

12. Система по п.1, в которой соединительное звено содержит стрелку.

13. Система по п.1, в которой соединительное звено содержит линию.

14. Система по п.1, в которой соединительное звено содержит кривую.

15. Система по п.1, в которой контейнер содержит текст.

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

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

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

19. Способ по п.16, в котором выполнение распознавания контейнера включает в себя выполнение распознавания эллипса/окружности.

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

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

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

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

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

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

26. Способ по п.25, в котором дополнительно выполняют масштабирование штрихов для приведения минимального описанного прямоугольника к форме квадрата.

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

28. Способ по п.20, в котором выполнение распознавания многоугольника включает вычисление отношения площадей A_n/A_ch, где A_n представляет площадь максимального n-стороннего многоугольника, вписанного в выпуклую оболочку, окружающую штрихи контейнера, a A_ch представляет площадь выпуклой оболочки, окружающей штрихи контейнера.

29. Способ по п.20, в котором выполнение распознавания многоугольника включает в себя выбор n-стороннего многоугольника с наименьшим числом сторон и с отношением площадей A_n/A_ch большим, чем пороговое значение.

30. Способ по п.20, в котором выполнение распознавания многоугольника включает в себя коррекцию сторон распознаваемого многоугольника.

31. Машиночитаемый носитель, содержащий исполняемые компьютером команды для выполнения способа по п.16.