(57)【要約】【課題】  手描きオブジェクトの形状認識のためのシステムおよび方法を提供すること。【解決手段】  形状レコグナイザーは、描画内の、閉じたコンテナおよび／または開いたままのコネクタを認識することによって、インク入力から図面または図表のような描画を認識することができる。閉じたコンテナは、円形、楕円形、三角形、四角形、五角形、六角形などを含めて、認識することのできる形状を、いくつでも表すことができる。開いたままのコネクタは、直線、曲線、矢印などを含むいかなるタイプのコネクタでも含むことができる。ポリラインは、スケルトンの連続ストローク、オーバーラップするストローク、およびなぞるストロークを処理するために、コネクタのスケルトンを近似するために使用することができる。本発明を使用することにより、ユーザは、手描き入力に対する制約なしに、図面およびフローチャートを自由に描くことができる。【選択図】  図１
2005100417.tif 000002
【特許請求の範囲】
【請求項１】
手描き形状を認識するコンピュータシステムであって、
インク入力を受け取る形状レコグナイザーと、
インク入力内の閉じたコンテナを認識するための、前記形状レコグナイザーに動作可能に結合されたコンテナレコグナイザーと、
インク入力内のコネクタを認識するための、前記形状レコグナイザーに動作可能に結合されたコネクタレコグナイザーと
を備えたことを特徴とするシステム。
【請求項２】
インク入力を前記形状レコグナイザーに送るための、前記形状レコグナイザーに動作可能に結合されたインクパーサーをさらに備えたことを特徴とする請求項１に記載のシステム。
【請求項３】
描画ストロークをグループ化するための、前記インクパーサーに動作可能に結合されたチャートディテクターをさらに備えたことを特徴とする請求項２に記載のシステム。
【請求項４】
前記チャートディテクターは、前記チャートディテクターに動作可能に結合されたコンテナディテクターを含むことを特徴とする請求項３に記載のシステム。
【請求項５】
前記チャートディテクターは、前記チャートディテクターに動作可能に結合されたコネクタディテクターを含むことを特徴とする請求項３に記載のシステム。
【請求項６】
前記コンテナレコグナイザーは、前記コンテナレコグナイザーに動作可能に結合された楕円形／円形分類子を含むことを特徴とする請求項１に記載のシステム。
【請求項７】
前記コンテナレコグナイザーは、前記コンテナレコグナイザー動作可能に結合されたポリゴン分類子を含むことを特徴とする請求項１に記載のシステム。
【請求項８】
前記コンテナレコグナイザーは、前記コンテナレコグナイザーに動作可能に結合された三角形分類子を含むことを特徴とする請求項１に記載のシステム。
【請求項９】
前記コンテナレコグナイザーは、前記コンテナレコグナイザーに動作可能に結合された四角形分類子を含むことを特徴とする請求項１に記載のシステム。
【請求項１０】
前記コネクタレコグナイザーは、前記コネクタレコグナイザーに動作可能に結合されたスケルトンレコグナイザーを含むことを特徴とする請求項１に記載のシステム。
【請求項１１】
前記コネクタレコグナイザーは、前記コネクタレコグナイザーに動作可能に結合された矢印レコグナイザーを含むことを特徴とする請求項１に記載のシステム。
【請求項１２】
前記閉じたコンテナは、円形を含むことを特徴とする請求項１に記載のシステム。
【請求項１３】
前記閉じたコンテナは、楕円形を含むことを特徴とする請求項１に記載のシステム。
【請求項１４】
前記閉じたコンテナは、三角形を含むことを特徴とする請求項１に記載のシステム。
【請求項１５】
前記閉じたコンテナは、四角形を含むことを特徴とする請求項１に記載のシステム。
【請求項１６】
前記コネクタは、矢印を含むことを特徴とする請求項１に記載のシステム。
【請求項１７】
前記コネクタは、直線を含むことを特徴とする請求項１に記載のシステム。
【請求項１８】
前記コネクタは、曲線を含むことを特徴とする請求項１に記載のシステム。
【請求項１９】
前記コンテナは、テキストを含むことを特徴とする請求項１に記載のシステム。
【請求項２０】
請求項１のシステムを含んだコンピュータ実行可能なコンポーネントを有することを特徴とするコンピュータ可読媒体。
【請求項２１】
手描き形状を認識する方法であって、
インク入力を受け取るステップと、
前記インク入力内のコンテナごとにコンテナ認識を実行するステップと、
前記インク入力内のコネクタごとにコネクタ認識を実行するステップと
を備えたことを特徴とする方法。
【請求項２２】
前記インク入力をパースし、前記インク入力内の手書きと手描きを区別するステップをさらに備えたことを特徴とする請求項２１に記載の方法。
【請求項２３】
チャート検出を実行し、インク入力内の図面のストロークを特定するステップをさらに含むことを特徴とする請求項２１に記載の方法。
【請求項２４】
前記インク入力内の認識された各コンテナと各コネクタとにより描画を生成するステップをさらに備えたことを特徴とする請求項２１に記載の方法。
【請求項２５】
コンテナ認識を実行するステップは、真円度テストを実行するステップを含むことを特徴とする請求項２１に記載の方法。
【請求項２６】
コンテナ認識を実行するステップは、楕円形／円形認識を実行するステップを含むことを特徴とする請求項２１に記載の方法。
【請求項２７】
コンテナ認識を実行するステップは、ポリゴン認識を実行するステップを含むことを特徴とする請求項２１に記載の方法。
【請求項２８】
コンテナ認識を実行するステップは、三角形認識を実行するステップを含むことを特徴とする請求項２１に記載の方法。
【請求項２９】
コンテナ認識を実行するステップは、四角形認識を実行するステップを含むことを特徴とする請求項２１に記載の方法。
【請求項３０】
コンテナ認識を実行するステップは、コンテナに属するストロークの凸包を計算するステップを含むことを特徴とする請求項２１に記載の方法。
【請求項３１】
コンテナ認識を実行するステップは、薄さ率Ｐｃｈ２／Ａｃｈを計算するステップを含み、ＰｃｈとＡｃｈは、前記コンテナのストロークを囲む凸包の周囲の長さと面積とを示すことを特徴とする請求項２１に記載の方法。
【請求項３２】
楕円形／円形認識を実行するステップは、前記コンテナのストロークを囲む最小包囲矩形を判定するステップを含むことを特徴とする請求項２６に記載の方法。
【請求項３３】
前記最小包囲矩形を正方形にするよう前記ストロークを拡大縮小するステップをさらに備えたことを特徴とする請求項３２に記載の方法。
【請求項３４】
ポリゴン認識を実行するステップは、前記コンテナのストロークを囲む凸包内の最大限に内接したポリゴンを判定するステップを含むことを特徴とする請求項２７に記載の方法。
【請求項３５】
ポリゴン認識を実行するステップは、面積率Ａｎ／Ａｃｈを計算するステップを含み、Ａｎは、前記コンテナの前記ストロークを囲む凸包内の最大限に内接したｎ角形ポリゴンの面積を表し、Ａｃｈは、前記コンテナの前記ストロークを囲む前記凸包の面積を表すことを特徴とする請求項２７に記載の方法。
【請求項３６】
ポリゴン認識を実行するステップは、辺の数が最も少ない、および面積率Ａｎ／Ａｃｈが閾値よりも大きいｎ角形ポリゴンを選択するステップを含むことを特徴とする請求項２７に記載の方法。
【請求項３７】
ポリゴン認識を実行するステップは、認識されたポリゴンの辺を改善するステップを含むことを特徴とする請求項２７に記載の方法。
【請求項３８】
コネクタ認識を実行するステップは、前記コネクタのストロークをカスプで断片に分けるステップを含むことを特徴とする請求項２１に記載の方法。
【請求項３９】
コネクタ認識を実行するステップは、前記コネクタのスケルトンストロークを前記コネクタの矢印ストロークと類別するステップを含むことを特徴とする請求項２１に記載の方法。
【請求項４０】
請求項２１の方法を実行するコンピュータ実行可能な命令を有することを特徴とするコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、コンピュータシステムに関し、より詳細には、手描きオブジェクトの形状認識のための改善されたシステムおよび方法に関する。
【背景技術】
【０００２】
手描きオブジェクトの形状を認識する機能は、ユーザが、インク入力またはインクノードを使用してユーザ自身のコンピュータに直接描くことができるために重要である。現在のハードウェアおよびソフトウェアは、手書きを表すインクを概ね良好に取り込むことができるが、手描きオブジェクトの意味を同様に認識し、表すことは、現在のところ不可能である。したがって、ユーザは、オブジェクトの描画を作成するため、代わりにメニューベースのアプリケーションプログラムを使用する。ユーザが描画グリッド上で選択し、コピーするためのこのようなアプリケーションプログラムによって、様々な形状を示すことができる。コピーされた形状は、次いで所望の縮尺にサイズ変更することができ、ユーザは、描画が完成するまで描画グリッドに追加の形状を配置し、サイズ変更し続けることができる。
【０００３】
【非特許文献１】Computational Geometry in C (2nd Ed.) by Joseph O'Rourke, Cambridge University Press, 1988, ISBN:0-521-64976-5
【非特許文献２】J.E. Boyce and D.P.Dobkin, Finding External Polygons, SIAM Journal on Computing, 14(1):134-147, 1985
【非特許文献３】Sklansky J. and Gonzalez V., Fast Polygonal Approximation of Digitized Curves, Pattern Recognition, Vol.12, pp.327-331, 1980
【発明の開示】
【発明が解決しようとする課題】
【０００４】
手描きオブジェクトの形状認識を中心とした研究からは、今までのところ、僅かな成果しかあがっていない。例えば、円、ボックスのような単純な幾何学形状を、特定の順序で行われた特定数のストロークから認識することができる、増分認識アルゴリズムが使用されてきた。しかし、このような増分アルゴリズムは、ストロークの順序に依存し、かつ／または特定の手描き形状を認識するために、特定数のストロークを前提とする。このような手段は、いくつかの理由から堅牢ではない。第１に、この増分アルゴリズムはどれも、ストロークの集合体が特定の形状を表しているので、そのストロークの集合体は１つのグループを形成していると決定する、グループ化の問題を解決しない。１つの形状に属するストロークをグループ化する機能がないので、増分アルゴリズムは、矢印のようなマルチストローク形状に対応することはできない。さらに、増分アルゴリズムがストロークの順序に依存し、かつ／または１つの形状に対して特定数のストロークを前提とするので、増分アルゴリズムは、ある形状の描画中にストロークをなぞることができる場合、なぞりの問題を解決することができない。
【０００５】
必要なのは、任意の所与の形状を形成するために必要となる、ストロークの入力順序および／またはストローク数に左右されない、手描きオブジェクトの形状を認識するための方法である。いかなるこのようなシステムおよび方法でも、マルチストローク手描き形状を認識し、ストロークのどの集合体が様々な形状を表すグループに属するかを判断できるべきである。
【課題を解決するための手段】
【０００６】
簡単に言えば、本発明は、手描きオブジェクトの形状認識のためのシステムおよび方法を提供する。この目的のために、インク入力から図面または図表のような描画を認識することのできる、形状レコグナイザーが提供される。形状レコグナイザーは、描画内の、閉じたコンテナを認識するコンテナレコグナイザーと、開いたままのコネクタを認識するコネクタレコグナイザーを含むことができる。コンテナレコグナイザーは、楕円形／円形分類子、ポリゴン分類子、三角形分類子、四角形分類子などを含めて、形状分類子をいくつでも含むことができる。コネクタレコグナイザーは、描画のコンテナ間のコネクタのタイプを特定するための、スケルトンレコグナイザー、矢印レコグナイザー、および様々な他のレコグナイザーを含むことができる。
【０００７】
本発明は、コンテナごとにコンテナ認識をまず実行し、円形、三角形、四角形、五角形、六角形などを含む、閉じた形状を特定することによって、手描き形状を認識することができる。一実施形態は、三角形のような形状を特定するための全体の統計的特徴と、例えば正三角形や直角三角形から二等辺三角形を区別するなど、その特定された形状の特定のタイプの規則に基づく記述を組み合わせることのできる、決定ツリーを利用することができる。この実施形態では、全体の統計的特徴は、ストロークをなぞり、オーバーラップするなどの局所的変動に対して堅牢であり得、規則に基づく記述は、台形、平行四辺形、ひし形、長方形、および正方形のような、複数のタイプの四角形を含む形状のさらに詳細な情報を提供することができる。
【０００８】
この場合、コネクタ認識は、コネクタごとに実行し、スケルトン、矢印などを含む、開いたままのコネクタの形状を特定することができる。一実施形態では、スケルトンを近似するためにポリラインを使用することができる。この実施形態では、本発明は、スケルトンの連続ストローク、スケルトンのオーバーラップするストローク、およびスケルトンのなぞるストロークを処理することができる。コネクタのスケルトンが認識できると、そのスケルトンの一端または両端の矢印を認識することができる。
【０００９】
このシステムおよび方法は、ストロークの入力順序と手描き形状を形成することのできるストローク数に左右されない点で優れている。さらに、このシステムおよび方法を使用して、描画内のいかなる閉じたコンテナと開いたままのコネクタでも認識することができる。認識されると、形状のタイプ、位置、向き、およびサイズを提供することができる。
【００１０】
以下の詳細な説明を添付の図面と併せ読めば、他の利点が明らかになろう。
【発明を実施するための最良の形態】
【００１１】
（例示的な動作環境）
図１は、本発明を実装することのできる、適切なコンピューティングシステム環境１００の一例を示す。このコンピューティングシステム環境１００は、適切なコンピューティング環境の一例にすぎず、本発明の使用または機能の範囲について、いかなる限定をも示すことを意図しない。また、コンピューティング環境１００は、例示的な動作環境１００に示す複数あるコンポーネントのどれか１つ、またはそれらの組み合わせに関して、依存または要件を有するものと解釈されるべきでない。
【００１２】
本発明は、多数の他の汎用または専用コンピューティングシステム環境または構成と共に動作可能である。本発明と共に使用するのに適した、良く知られたコンピューティングシステム、環境、および／または構成の例は、限定ではないが、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドまたはラップトップデバイス、タブレットデバイス、ヘッドレスサーバ、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラム可能な家庭用電化製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記システムまたはデバイスのどれかを含む分散型コンピューティング環境などを含む。
【００１３】
本発明は、コンピュータによって実行中の、プログラムモジュールのようなコンピュータ実行可能命令の一般的状況で説明することができる。一般に、プログラムモジュールは、特定のタスクを実行するか、または特定の抽象データ型を実装する、ルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。本発明は、通信ネットワークを介してリンクされる遠隔処理装置によってタスクが実行される、分散型コンピューティング環境で実施することもできる。分散型コンピューティング環境で、プログラムモジュールは、メモリストレージデバイスを含めて、ローカルおよび／または遠隔コンピュータ記憶媒体に入れることができる。
【００１４】
図１を参照すると、本発明を実装するための例示的なシステムは、コンピュータ１１０の形式での汎用コンピューティングデバイスを含む。コンピュータ１１０のコンポーネントは、限定ではないが、処理装置１２０、システムメモリ１３０、およびシステムメモリを含む様々なシステムコンポーネントを処理装置１２０に結合するシステムバス１２１を含む。システムバス１２１は、メモリバスまたはメモリコントローラ、周辺バス、および様々なバスアーキテクチャの任意のものを使用したローカルバスを含めて、いくつかのタイプのバス構造のどれであってもよい。限定ではなく一例として、このようなアーキテクチャは、ＩＳＡ（Industry Standard Architecture）バス、ＭＣＡ（Micro Channel Architecture）バス、ＥＩＳＡ（Enhanced  ＩＳＡ）バス、ＶＥＳＡ（Video Electronics Standards Association）ローカルバス、およびメザニンバス（Mezzanine）としても知られているＰＣＩ（Peripheral Component Interconnect）バスを含む。
【００１５】
コンピュータ１１０は、通常、様々なコンピュータ可読媒体を含む。コンピュータ可読媒体は、コンピュータ１１０によってアクセス可能ないかなる利用可能な媒体であってもよく、揮発性／不揮発性媒体、およびリムーバブルな／固定の媒体の両方を含む。限定ではなく一例として、コンピュータ可読媒体には、コンピュータ記憶媒体および通信媒体を含めることができる。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータなどの情報を記憶するための任意の方法または技術において実装される、揮発性／不揮発性の、リムーバブルな／固定の媒体を含む。コンピュータ記憶媒体は、限定ではないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）または他の光ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージまたは他の磁気記憶装置、または所望の情報を記憶するために使用することができ、コンピュータ１１０によってアクセスすることのできる、いかなる他の媒体をも含む。通信媒体は、通常、コンピュータ可読命令、データ構造、プログラムモジュール、または搬送波または他の転送機構のような変調されたデータ信号形式における他のデータを実施し、任意の情報配信媒体を含む。「変調されたデータ信号」という用語は、特徴集合の１つまたは複数を有するか、または情報を信号に符号化するような方法で変更された信号を意味する。限定ではなく一例として、通信媒体は、有線ネットワークまたは直接有線接続のような有線媒体と、アコースティック、ＲＦ、赤外線および他の無線媒体のような無線媒体を含む。上記のどのような組み合わせでも、コンピュータ可読媒体の範囲に含まれるべきである。
【００１６】
システムメモリ１３０は、コンピュータ記憶媒体を、読み取り専用メモリ（ＲＯＭ）１３１およびランダムアクセスメモリ（ＲＡＭ）１３２のような、揮発性および／または不揮発性メモリの形式において含む。起動時などに、コンピュータ１１０の素子間で情報を転送するために役立つ基本ルーチンを収容した基本入出力システム１３３（ＢＩＯＳ）は、通常、ＲＯＭ  １３１に記憶される。ＲＡＭ  １３２は、通常、処理装置１２０によって直接アクセス可能であり、かつ／または処理装置１２０で現在動作中の、データおよび／またはプログラムモジュールを収録する。限定ではなく一例として、図１は、オペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６、およびプログラムデータ１３７を示す。
【００１７】
コンピュータ１１０は、他のリムーバブルな／固定の、揮発性／不揮発性コンピュータ記憶媒体も含むことができる。単なる一例として、図１は、固定の不揮発性磁気媒体から読み取り／に書き込むハードディスクドライブ１４１、リムーバブルな不揮発性磁気ディスク１５２から読み取り／に書き込む磁気ディスクドライブ１５１、ＣＤ  ＲＯＭまたは他の光媒体などの、リムーバブルな不揮発性光ディスク１５６から読み取り／に書き込む光ディスクドライブ１５５を示す。動作環境例で使用することのできる他のリムーバブルな／固定の揮発性／不揮発性コンピュータ記憶媒体は、限定ではないが、磁気テープカセット、フラッシュメモリカード、デジタル多用途ディスク、デジタルビデオテープ、半導体ＲＡＭ、半導体ＲＯＭなどを含む。ハードディスクドライブ１４１は、通常、インターフェース１４０などの固定のメモリインターフェースを介してシステムバス１２１に接続され、磁気ディスクドライブ１５１および光ディスクドライブ１５５は、通常、インターフェース１５０などのリムーバブルなメモリインターフェースによってシステムバス１２１に接続される。
【００１８】
上記で説明され、図１に示されるドライブおよびその関連するコンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、および他のデータのストレージをコンピュータ１１０に提供する。図１では、例えば、ハードディスクドライブ１４１は、オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６、およびプログラムデータ１４７を格納しているように示されている。これらのコンポーネントは、オペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６、およびプログラムデータ１３７と同じであっても、異なっていてもよいことに留意されたい。オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６、およびプログラムデータ１４７が少なくとも別物であることを示すために、本明細書ではこれらに別の番号を付した。ユーザは、タブレットすなわち電子デジタイザー１６４、マイクロフォン１６３、キーボード１６２、および一般にはマウス、トラックボール、またはタッチパッドと呼ばれるポインティングデバイス１６１のような入力装置により、コンピュータ１１０にコマンドおよび情報を入力することができる。図１には示されない他の入力装置は、ジョイスティック、ゲームパッド、衛星放送用受信アンテナ、スキャナ、もしくはバイオメトリックセンサー、環境センサー、位置センサー、または他のタイプのセンサーを収めた装置を含めて、他の装置を含むことができる。これらおよび他の入力装置は、システムバスに結合されたユーザ入力インターフェース１６０を介して処理装置１２０に接続されていることが多々あるが、パラレルポート、ゲームポート、またはユニバーサルシリアルバス（ＵＳＢ）のような他のインターフェースおよびバス構造によって接続することもできる。モニタ１９１または他のタイプの表示装置も、ビデオインターフェース１９０のようなインターフェースを介してシステムバス１２１に接続される。モニタ１９１は、タッチスクリーンパネルなどにより統合することもできる。モニタおよび／またはタッチスクリーンパネルは、タブレットタイプのパーソナルコンピュータのような、コンピューティングデバイス１１０が組み込まれた筐体に物理的に結合できることに留意されたい。さらに、コンピューティングデバイス１１０のようなコンピュータは、出力周辺インターフェース１９４などを介して接続できる、スピーカ１９５およびプリンタ１９６のような他の周辺出力装置も含むことができる。
【００１９】
コンピュータ１１０は、遠隔コンピュータ１８０のような１つまたは複数の遠隔コンピュータへの論理接続を使用して、ネットワーク接続環境で動作することができる。遠隔コンピュータ１８０は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、または他の共通ネットワークノードであってよく、通常は、コンピュータ１１０に関して上記で説明した要素の多くまたはすべてを含む。但し、図１には、メモリストレージデバイス１８１しか示さない。図１に示した論理接続は、ローカルエリアネットワーク（ＬＡＮ）１７１および広域ネットワーク（ＷＡＮ）１７３を含むが、他のネットワークも含むこともできる。このようなネットワーク接続環境は、オフィス、企業規模コンピュータネットワーク、イントラネット、およびインターネットでは一般的なものである。ＬＡＮネットワーク接続環境で使用される場合、コンピュータ１１０は、ネットワークインターフェースまたはアダプタ１７０を介してＬＡＮ  １７１に接続される。ＷＡＮネットワーク接続環境で使用される場合、コンピュータ１１０は、通常、インターネットなどのＷＡＮ  １７３を介して通信を確立するためのモデム１７２または他の手段を含む。内蔵であっても外付けであってもよいモデム１７２は、ユーザ入力インターフェース１６０または他の適切な機構を介して、システムバス１２１に接続することができる。ネットワーク接続環境では、コンピュータ１１０に関して示したプログラムモジュール、またはその一部は、遠隔メモリストレージデバイスに記憶することができる。限定でなく一例として、図１は、遠隔アプリケーションプログラム１８５を、メモリ装置１８１に常駐しているように示す。図示したネットワーク接続は例示であり、コンピュータ間に通信リンクを確立する他の手段を使用することができるということが理解されよう。
【００２０】
（手描きオブジェクトの形状認識）
本発明は、一般に手描きオブジェクトの形状認識を提供するためのシステムおよび方法を対象とする。本明細書で使用するように、手描きオブジェクトは、いかなる手書き文字でない形状または描画をも意味する。ユーザは、手描き入力に対する制約なしに、図面およびフローチャートを自由に描画することができる。このシステムおよび方法が、任意のインクを入力として受け入れることができるように、１つの形状は、多くのストロークを有することができ、ストロークの入力順序は任意であってよい。本明細書で使用するように、インクは、一般に、手書きの１つまたは複数のストロークを意味する。さらに、ストロークをなぞり、オーバーラップすることができる。いずれにせよ、このシステムおよび方法は、正確な形状を自動的に検出することができる。
【００２１】
具体的には、このシステムおよび方法は、コンテナおよびコンテナ間に描かれたコネクタの手描き形状を認識することができる。本明細書で使用するように、コンテナは、いかなる閉じた描画オブジェクトをも意味する。本明細書で使用するように、コネクタは、コンテナを連結するいかなる描画オブジェクトをも意味する。理解されるように、本明細書に記載する様々なブロック図、フローチャート、およびシナリオは一例に過ぎず、本発明が適用される多くの他のシナリオがある。
【００２２】
図面のうち図２を参照すると、手描きオブジェクトの形状認識のためのシステムコンポーネントの例示的なアーキテクチャを一般に表すブロック図が示されている。当業者には、図示したブロック内で実装される機能は、個別のコンポーネントとして実装してもよく、ブロックのいくつかまたはすべての機能は、単一コンポーネント内で実装してもよいことが理解されよう。例えば、チャートディテクター２０４の機能を、形状レコグナイザー２０６に含めることができる。または、コンテナレコグナイザー２０８の機能を、別個のコンポーネントとして実施することができる。
【００２３】
インクパーサー２０２は、描画オブジェクトのインクを含めて、いかなるインクをも受け入れることができる。インクパーサー２０２は、動作可能に結合されたチャートディテクター２０４と、動作可能に結合された形状レコグナイザー２０６を含むことができる。一般に、チャートディテクター２０４および形状レコグナイザー２０６は、カーネルコンポーネント、アプリケーションプログラム、リンクされたライブラリ、オブジェクトなどのような、いかなるタイプの実行可能なソフトウェアコードであってもよい。チャートディテクター２０４は、動作可能に結合されたコンテナディテクター２１２と、動作可能に結合されたコネクタディテクター２１４を含むことができ、形状レコグナイザー２０６は、動作可能に結合されたコンテナレコグナイザー２０８と、動作可能に結合されたコネクタレコグナイザー２１０を含むことができる。コンテナレコグナイザー２０８は、楕円形／円形分類子２１６、ポリゴン分類子２１８、三角形分類子２２０、四角形分類子２２２などのような、動作可能に結合された分類子をいくつでも含むことができる。コネクタレコグナイザー２１０は、スケルトンレコグナイザー２２４、矢印レコグナイザー２２６などの、動作可能に結合されたレコグナイザーをいくつでも含むことができる。これらのコンポーネントはそれぞれ、カーネルコンポーネント、アプリケーションプログラム、リンクされたライブラリ、オブジェクト、または他のタイプの実行可能なソフトウェアコードのような、任意のタイプの実行可能なソフトウェアコードであってよい。
【００２４】
図３は、手描きオブジェクトの形状認識のために行われるステップを一般に表すフローチャートを示す。ステップ３０２において、描画オブジェクトのインクを含めて、いかなるインクでもパースすることができる。例えば、一実施形態では、インクのページを入力として受け入れ、パースすることができる。この実施形態では、例えばインクパーサーは、ページ上のインクに関する推測的な知識を持たない。したがって、ワードグルーピング、手書き／手描き分類子、および描画グルーピングのような基礎的アルゴリズムを実行することができる。ワードグルーピングを実行するために、ストロークは、語、行、およびブロックの各階層にグループ化することができる。このように行うために、ワードグルーピングプロセスは、ストロークの特徴抽出を含み、距離、幾何学的相違点および直線性、ならびに他のストロークの特徴を取り込むことができる。ワードグルーピングプロセスは、動的プログラミングを含み、時間情報に従ってストロークをグループ化することもできる。ワードグルーピングプロセスは、クラスタ化を含み、空間情報に従ってストロークをグループ化することもできる。これらグループでの特定された語、行、およびブロックは、必ずしも実際の語義の語、行、およびブロックに対応させなくてよい。実際、これらのグループは、手描きオブジェクトのストロークを含むことができる。
【００２５】
手書き／手描き分類を実行するために、手書きを手描きと区別することのできる様々な特徴を特定することができる。例えば、手書きを手描きと区別するために、湾曲、密度、および他の手書きモデルの特徴のような単語の特徴を使用することができる。一実施形態では、手書きを手描きと区別するために、時間コンテキスト特徴および空間コンテキスト特徴のようなコンテキスト特徴を使用することができる。様々な特徴はそれぞれ、ファジー機能に対してマッピングすることができ、手書きと手描きの間の分類は、ファジー機能の組み合わせに従って決定することができる。
【００２６】
ワードグルーピングおよび手書き／手描き分類の実行後、描画グルーピングを実行することにより、描画ストロークを上手く体系付けることができる。描画グルーピングを実行するために、それらストローク間の空間的相関関係に従い、描画のストロークを独立したオブジェクトにグループ化することができる。インクストロークを適切なサイズのイメージグリッドに適合させるために、効率のよいグリッドベース方式を使用することができる。イメージグリッドは、ラベリングし、接続されたコンポーネントを見つけることができる。それぞれの接続されたコンポーネントは、描画オブジェクトに対応させることができる。この場合、描画オブジェクトを調整するために、ヒューリスティックな規則を適用することができる。
【００２７】
ステップ３０４において、描画オブジェクトに属する可能性のあるすべてのストロークを見つけることにより、描画のストロークをグループ化するようチャート検出を実行することができる。したがって、ユーザは、入力に対する制約なしに、図面およびフローチャートを自由に描くことができる。例えば、１つの形状は、多くのストロークを有することができ、入力順序は任意であってよい。さらに、ストロークは、なぞってもオーバーラップしてもよい。これらのどの場合でも、システムは、正確な形状を自動的に検出することができる。一実施形態では、コンテナとコネクタの間の相関関係を完全に表せるよう、図面およびフローチャートを表現するためにハイパーグラフを使用することができる。したがって、この実施形態では、２つ以上のコンテナを連結することのできるコネクタをサポートすることができる。
【００２８】
一実施形態では、コンテナディテクター２１２は、あるコンテナに属するすべてのストロークを見つけることができ、コネクタディテクター２１４は、あるコネクタに属するすべてのストロークを見つけることができる。これを行うために、最適の検索を時系列で実行し、コンテナを検出することができる。よって、コンテナとコネクタを検出するために、効率よい検索を実行することができる。最後に、検出されたコンテナごとに、内容検出を実行することができる。
【００２９】
ステップ３０６において、コンテナとコネクタを認識するために、形状認識を実行することができる。各コンテナおよび各コネクタに対してストロークのすべてがグループ化されると、一実施形態では、図面またはチャートのような描画で閉じたコンテナと開いたままのコネクタを認識するために、形状認識エンジン２０６を使用することができる。認識されると、形状のタイプ、位置、向き、およびサイズを提供することができる。好都合にも、ストロークの入力順序とストローク数は、認識に影響を与えない。閉じたコンテナと開いたままのコネクタを認識するために形状認識が実行されると、ステップ３０８において描画を生成することができる。
【００３０】
図４は、ステップ３０６において示されたコンテナおよびコネクタの形状認識のために行われたステップの一実施形態を全体的に表すフローチャートを示す。ステップ４０２において、円形、三角形、四角形、五角形、六角形などを含めて閉じた形状を特定するために、各コンテナに対してコンテナ認識を実行することができる。さらに、円形を楕円形と区別するか、もしくは二等辺三角形を正三角形または直角三角形と区別するなど、特定のタイプの形状を認識することができる。別の実施例では、台形、平行四辺形、ひし形、長方形、および正方形を含めて、いくつかのタイプの四角形を認識することができる。
【００３１】
一実施形態では、コンテナレコグナイザー２０８は、例えば、特定形状の全体の統計的特徴と規則ベースの記述の両方を組み合わせることのできる、決定ツリーを利用することができる。この実施形態では、全体の統計的特徴は、なぞるような局所的変動に対して堅牢であることができ、規則ベースの記述は、形状のさらに詳細な情報を提供することができる。例えば、二辺の長さが等しい三角形という記述を含むことができる、二等辺三角形に関する規則ベースの記述があってもよい。
【００３２】
ステップ４０４においては、コネクタごとにコネクタ認識を実行して、スケルトン、矢印などを含めた、開いたコネクタの形状を特定することができる。一実施形態では、ポリラインを使用してスケルトンを近似することができる。この実施形態では、コネクタレコグナイザー２１０は、例えば、スケルトンの連続ストローク、スケルトンのオーバーラップするストローク、およびスケルトンのなぞるストロークを処理することができる。コネクタのスケルトンが認識できた後、スケルトンの一端または両端の矢印を認識することができる。コネクタレコグナイザー２１０は、コネクタのスケルトンおよび矢印をそれぞれ特定するために、スケルトンレコグナイザー２２４および／または矢印レコグナイザー２２６を呼び出すことができる。
【００３３】
図５は、形状認識を実行する際に使用するための、特定形状の全体の統計的特徴と規則に基づく記述の両方を組み合わせることのできる、決定ツリーを一般に表す図を示す。あるコンテナに属するグループ化されたストローク５０２は、そのストロークの形状がどれだけ円形または楕円形である可能性があるかを判定するために、真円度テスト５０４に入力することができる。次いで真円度テスト５０４は、ストローク５０２の形状を特定するために、楕円形／円形分類子５０６またはポリゴン分類子５０８を適用するか否かを判定することができる。楕円形／円形分類子５０６は、ストロークの形状が楕円形５１０か円形５１２かを判定することができる。ポリゴン分類子５０８は、ストローク５０２の形状を特定するために、ストロークの形状が五角形５１８もしくは六角形５２０、または三角形分類子５１４もしくは四角形分類子５１６のどちらを適用するかを判定することができる。三角形分類子５１４は、ストロークの形状が三角形か否かを判定することができ、またその三角形が二等辺三角形５２２か、正三角形５２４か、直角三角形５２６かを区別するさらに詳細な情報を提供できる規則に基づく記述を利用することもできる。同様に、四角形分類子は、ストロークの形状が四角形か否かを判定することができ、またその四角形が正方形５２８か、長方形５３０か、ひし形５３２か、台形５３４か、平行四辺形５３６かを区別するためのさらに詳細な情報を提供できる規則に基づく記述を利用することもできる。
【００３４】
図６は、インク入力で特定された閉じたコンテナの形状を認識するために行われるステップの一実施形態を一般に表すフローチャートを示す。ステップ６０２において、その形状がどれだけ円形または楕円形である可能性があるかをテストするために、真円度テストを実行することができる。ステップ６０４において、真円度テストの結果、その形状が円形または楕円形である可能性があると示された場合、ステップ６０６において、円形または楕円形を認識するためのプロセスを実行することができる。ステップ６０４において、真円度テストの結果、その形状が円形または楕円形である可能性がないと示された場合、ステップ６０８において、ポリゴンを認識するためのプロセスを実行することができる。ステップ６０８においてポリゴンを認識するために実行されたプロセスは、ポリゴンが三角形または四角形である可能性を示す場合がある。ステップ６１０において、ポリゴンを認識するために実行されたプロセスの結果、そのポリゴンが三角形であると示された場合、ステップ６１２において、三角形の特定のタイプまたはサブクラスを認識するためにプロセスを実行することができる。例えば、特定のタイプの三角形は、二等辺三角形５２２、正三角形５２４、または直角三角形５２６である可能性がある。しかし、ステップ６１４において、ポリゴンを認識するために実行されたプロセスの結果、そのポリゴンが四角形である可能性があると示された場合、ステップ６１６において、四角形の特定のタイプまたはサブクラスを認識するためにプロセスを実行することができる。例えば、特定のタイプの四角形が、正方形５２８、長方形５３０、ひし形５３２、台形５３４、または平行四辺形５３６である可能性がある。もしくは、ステップ６０８においてポリゴンを認識するために実行されたプロセスが、そのポリゴンが五角形５１８か六角形５２０である可能性を示す場合がある。ステップ６１８において、ポリゴンを認識するために実行されたプロセスの結果、そのポリゴンが五角形であることが示された場合、ステップ６２０において、五角形を認識するためにプロセスを実行することができる。ステップ６２２において、ポリゴンを認識するために実行されたプロセスの結果、そのポリゴンが六角形である可能性が示された場合、ステップ６２４において、六角形を認識するためにプロセスを実行することができる。
【００３５】
図７は、ステップ６０２において示された真円度テストを実行するために行われるステップの一実施形態を一般に表すフローチャートを示す。閉じたコンテナの形状が円形／楕円形かポリゴンかを区別するために、真円度テストの結果を比較するために閾値を割り当てることができる。一実施形態では、真円度をテストするために、薄さ率Ｐｃｈ２／Ａｃｈのような特徴を使用することができる。ここで、ＰｃｈとＡｃｈは、それぞれ形状の凸包の周囲の長さと面積を示す。形状の薄さ率を計算する前に、最小包囲矩形を正方形にするよう形状のストロークを拡大縮小することができる。円形は最小の薄さ率、４＊πを有する場合があるので、円形と楕円形はどちらも４＊πの最小薄さ率を有する場合がある。ここで、π（パイ）は、円の直径に対する円周の比率と定義される。ステップ７０２で、ストロークの最小包囲矩形を特定することができ、ステップ７０４において、最小包囲矩形を正方形にするよう形状のストロークを拡大縮小することができる。次に、ステップ７０６において、形状のストロークの凸包をグラハムのアルゴリズム（非特許文献１参照）を使用して計算することができる。ステップ７０８において、薄さ率Ｐｃｈ２／Ａｃｈを計算することができる。ステップ７１０において、薄さ率Ｐｃｈ２／Ａｃｈの計算結果を閾値と比較することができる。一実施形態では、閾値４＊π＊１．０５を割り当てることができる。ステップ７１２において、薄さ率Ｐｃｈ２／Ａｃｈが４＊π＊１．０５の閾値に等しいか、またはそれ以上である場合、その形状は円形か楕円形である可能性があり、ステップ７１４において、分類子を使用して、閉じたコンテナの形状が円形か楕円形かをさらに区別することができる。ステップ７１２において、薄さ率が閾値４＊π＊１．０５よりも大きい場合、その形状はポリゴンである可能性があり、ステップ７１６で、ポリゴン分類子を使用して、閉じたコンテナの形状がそうである可能性があるポリゴンのタイプをさらに区別することができる。当業者には、真円度をテストするために他の閾値と他の特徴を使用することができることが理解されよう。
【００３６】
図８は、閉じたコンテナの形状が、ステップ７１４において示されたように円形か楕円形であるかを区別するために、分類子によって行われるステップを一般に表すフローチャートを示す。一般に、一実施形態では、最小包囲矩形の幅／高さ率（width-height ratio）のような特徴を使用して、円形を楕円形と類別することができる。ステップ８０２において、形状の最小包囲矩形の幅／高さ率を特定することができ、次いで、ステップ８０４において、所与の閾値に従って形状が円形８０６か楕円形８０８かを判定することができる。一実施形態では、幅／高さ率が、例えば０．８３と１．２０の範囲内などで、１に近い場合、この形状を円形に分類し、そうでない場合は楕円形に分類することができる。当業者には、他の閾値および他の特徴を使用して、円形を楕円形と類別することができることが理解されよう。
【００３７】
図９は、閉じたコンテナの形状がそうである可能性があるポリゴンのタイプを区別するために、分類子によって行われるステップを一般に表すフローチャートを示す。所望のタイプのｎ角形ポリゴンごとに、ポリゴン形状テストを実行し、ポリゴンの形状を特定することができる。一実施形態では、三角形、四角形、五角形、六角形に対してポリゴン形状テストを実行することができる。その形状がどのｎ角形ポリゴンである可能性があるかを区別するために、各所望のタイプのｎ角形ポリゴンに対して実行されたポリゴン形状テストの結果を比較するよう１つまたは複数の閾値をポリゴン形状テストに割り当てることができる。一実施形態では、面積率Ａｎ／Ａｃｈのような特徴を使用して、ポリゴンの形状を特定することができる。ここで、Ａｎは凸包内の最大限に内接したｎ角形ポリゴンの面積を表し、Ａｃｈはストロークの凸包の面積を表す。この実施形態では、ステップ９０２において、グラハムのアルゴリズム（非特許文献１参照）を使用してストロークの凸包を計算することができ、ストロークの凸包の面積を計算することができる。ステップ９０４において、最大限に内接したｎ角形ポリゴンとその面積Ａｎを、所望のタイプのｎ角形ポリゴンごとに計算することができる。最大の内接したｎ角形ポリゴンを、Ｂｏｙｃｅによる文献（非特許文献２）で提案されたアルゴリズムを使用して計算することができる。例えば、最大の内接した三角形、四角形、五角形、六角形、およびそれらそれぞれの面積Ａ３、Ａ４、Ａ５、およびＡ６を計算することができる。ステップ９０６において、所望のタイプのｎ角形ポリゴンごとに、面積率Ａｎ／Ａｃｈを計算することができる。ステップ９０８において、所望のタイプのｎ角形ポリゴンごとの面積率Ａｎ／Ａｃｈを、対応する閾値と比較することができる。最後に、ステップ９１０において、面積率Ａｎ／Ａｃｈが対応する閾値よりも大きい、辺の数が最も少ないｎ角形ポリゴンを、閉じたコンテナの形状を表すタイプのポリゴンとして選択することができる。一実施形態では、Ａ３、Ａ４、Ａ５、およびＡ６に対する閾値は、それぞれ０．７３、０．８４、０．９３、および０．９４であることが可能である。図１０は、形状１００２周囲の凸包１００６内の最大限に内接した四角形１００４を有する形状１００２のストロークの一例を示す。この例では、内接した四角形と凸包の面積率は、対応する閾値よりも大きく、および五角形または六角形のような、他のｎ角形ポリゴンの面積率と比較して最も少ない辺の数を有することができる。したがって、この形状を四角形に分類することができる。
【００３８】
面積率を計算するために凸包が使用されるので、一実施形態では、誤った分類を避けるために凹型をテストすることができる。ストロークの点と認識された形状の辺との最大距離を確認することにより、凹型をテストすることができる。例えば、図１１は、手描き形状１００２のストロークの点と、最大限に内接した四角形１００４である認識された形状の辺との間の最大距離１１０２を示す。最大距離１１０２が経験的閾値よりも大きい場合、その形状を四角形に分類することはできない。
【００３９】
最大面積の内接した三角形または四角形が計算されるので、一実施形態では、形状認識を実行する際に、特定のタイプの形状の規則に基づいた記述に従いサブクラスを決定することができる。例えば、三角形の二辺の長さが粗同じである場合、それをさらに二等辺三角形に分類することができる。一例として、三角形の三辺すべてが粗同じである場合、その三角形をさらに正三角形に分類することができる。さらに別の例では、どの二辺の二乗の合計でも、残りの一辺の二乗に粗等しい場合、その三角形をさらに直角三角形に分類することができる。
【００４０】
同様に、四角形の場合、四辺すべての長さが粗等しく、隣り合う二辺がどれも粗直角を成す場合、その形状をさらに正方形に分類することができる。四辺すべての長さが粗等しくなく、隣り合う二辺がどれも粗直角を成す場合、その形状をさらに長方形に分類することができる。向かい合う辺同士がいずれも粗平行であり、隣り合う二辺がどれも粗直角でなく、四辺すべての長さが粗等しい場合、その形状をさらにひし形に分類することができる。向かい合う辺同士がいずれも粗平行であり、隣り合う二辺がどれも粗直角でなく、四辺すべての長さが粗等しくない場合、その形状をさらに平行四辺形に分類することができる。向かい合う辺が一対だけ粗平行であり、隣り合う二辺がどれも粗直角でない場合、その形状をさらに台形に分類することができる。
【００４１】
ポリゴンの形状が分類された後、ステップ９１２で、より良い表現のためにそのポリゴン形状の辺を改善することができる。具体的には、入力されたストロークの各点が、認識されたポリゴンのどの一辺に属すかを判定するために、入力されたストロークの各点と認識されたポリゴンの辺との間の距離を演算することができる。次いで、認識されたポリゴンの各辺の位置と向きを、入力されたストロークの対応する点のロバスト回帰の結果に従い、再演算することができる。改善の結果、手描き形状１２０２のストロークから認識された形状１２０４の辺を、改善１２０６を施した形状で図１２に示すように、より良く表現することができる。
【００４２】
図１３は、インク入力内で特定されたコネクタの形状を認識するために行われるステップを一般に表すフローチャートを示す。コネクタの形状を認識するための入力は、図１４に示すように、チャートディテクターにより既に特定済みである可能性のあるストロークおよびコンテナとの接合点を含むことができる。本明細書で定義した接合点とは、コンテナに対する距離が最小限となるコネクタのストロークの一点のことである。例えば図１４に示すように、コネクタ１４０６の各端には接合点１４０４がある場合がある。ここで、この接合点は、コンテナ１４０２と１４１２の１つに付いてよい。一般に、各コネクタは、本明細書ではスケルトン１４０８と定義する、ある接合点または矢印と別の接合点または矢印の間の直線または曲線を含むことができ、各コネクタは、スケルトンの一端または両端の矢印１４１０を含むことができる。
【００４３】
コネクタを描く際、ユーザによっては、ストロークをオーバーラップさせる往復運動を使って、コネクタのスケルトンを描く場合がある。また、ユーザによっては、同様に、往復運動によりコネクタの矢印も描く場合がある。さらにまた、ユーザによっては、１回のストロークでコネクタのスケルトンと矢印とを描く場合がある。ユーザはスケルトンと矢印とを１回のストロークで描けるので、ストロークの様々な部分を別々にパースし、認識することができる。したがって、図１３のステップ１３０２では、ストロークを、本明細書においてカスプと定義する、曲率の高い点で複数の断片に分けることができる。１つのストロークを１つのポリラインとしてパースすることにより、そのストロークの各非終点のそれぞれが２つの線分の交点を形成する場合がある。一実施形態では、ストロークの各非終点それぞれでの２つの線分の角度を演算することができ、対応する角度が、例えば８０度などの閾値よりも小さい点でそのストロークを分けることができる。局所的変動でストロークをあまりに多くの無意味な断片に分けることを避けるために、一実施形態では、そのストロークを単純化し、および平滑化するため、まずそのストロークを、Ｓｋｌａｎｓｋｙのポリライン近似法（非特許文献３参照）を適用することによって平滑化することができる。
【００４４】
ステップ１３０４において、ストロークまたはストローク断片を、スケルトンストロークまたは矢印ストロークに分類することができる。これで、コネクタのスケルトンストロークとコネクタの矢印ストロークを別々に認識することができる。
【００４５】
ストロークまたはストローク断片のサイズが経験的閾値より小さく、そこから接合点への距離が短い場合、そのストロークまたはストローク断片を矢印ストロークと見なすことができる。一実施形態では、このような経験的閾値は、１２．８ミリメートルであり、そこから接合点への距離は８．５ミリメートルよりも短くてよい。矢印ストロークと見なされないストロークはどれも、スケルトンストロークと見なすことができる。短い矢印のストロークすべてを誤判別しないようにするには、コネクタの凸包中心への距離が最小のストロークまたはストローク断片を、スケルトンストロークまたはストローク断片と特定することができる。
【００４６】
ステップ１３０６において、スケルトンストロークまたはストローク断片をマージすることができる。マージされるべきスケルトンストロークまたは断片は、別のストロークまたは断片から分離される際に１つのストロークまたは断片、別のストロークまたは断片にオーバーラップする際に１つのストロークまたは断片、別のストロークまたは断片をなぞる際に１つのストロークまたは断片を発生する場合がある。これらの一般的な場合を図１５に示す。これらのそれぞれに対して、マージした場合に連続１５０２を形成する可能性のある分離したストロークまたはストローク断片の各端部、またはマージした場合にオーバーラップした連続１５０４を形成する可能性のあるオーバーラップしたストロークまたはストローク断片のオーバーラップした領域、またはマージした場合になぞった連続１５０６を形成する可能性のあるなぞったストロークまたはストローク断片のなぞった領域を囲んだ四角形を構築することにより、マージ可能領域１５０８を定めることができる。スケルトンストロークまたはストローク断片をマージするために、ストロークまたはストローク断片の各対に対して接続スコアを定義することができる。一実施形態では、接続スコアは、次のように定義することができる。すなわち、なぞった連続の場合とオーバーラップした連続の場合には、
【００４７】
【数１】
2005100417.tif 000003
【００４８】
であり、連続の場合には、
【００４９】
【数２】
2005100417.tif 000004
【００５０】
である。上式で、ｌは、２つのストロークまたはストローク断片の合計の長さであり、ｗ１、ｗ２は重みであり、ｄｍ、ｌｍはそれぞれ、画定したマージ可能領域の幅と長さである。一般に、この接続スコアは、２つのストロークまたはストローク断片が近接している場合は大きくなり、ストロークまたはストローク断片が離れている場合は小さくなる。すべてのスケルトンストロークまたはスケルトンストロークの断片に対して、再帰的マージプロセスは、マージ可能なストローク対がなくなるまで、２つのスケルトンストロークまたはスケルトンストロークの断片を最も高い接続スコアでマージすることにより、実行される。
【００５１】
ステップ１３０８において、それぞれのマージされたスケルトンストロークまたはストローク断片を正規化し、局所的変動を解消することができる。一実施形態では、正規化のために、マージされたスケルトンストロークまたはストローク断片ごとにＳｋｌａｎｓｋｙのポリライン近似法（非特許文献３参照）を用いることができる。最後にマージされたスケルトンが正規化されると、コネクタの最終スケルトンを完全に生成することができる。
【００５２】
ステップ１３１０において、矢印ストロークまたはストローク断片を認識することができる。一実施形態では、矢印ストロークまたはストローク断片の凸包をテストして形状が三角形の可能性があるか否かを確認することができる。三角形の形状を判定するために、面積率Ａｎ／Ａｃｈのような特徴を使用することができる。Ａｎはストロークの凸包内の最大限に内接した三角形の面積を表し、Ａｃｈはそのストロークの凸包の面積を表す。この実施形態では、Ｇｒａｈａｍのアルゴリズム（非特許文献１参照）を使用してストロークの凸包を計算することができ、次いでストロークの凸包の面積Ａｃｈを計算することができる。最大限に内接した三角形を、Ｂｏｙｃｅの提案したアルゴリズム（非特許文献２参照）を使用して計算することができ、次いでその面積Ａｎを計算することができる。次に、面積率Ａｎ／Ａｃｈを計算することができ、１に近い範囲内などの閾値と比較して、矢印ストロークまたはストローク断片の形状が三角形の可能性があると判定することができる。
【００５３】
一実施形態では、誤った分類をしないように、ストローク内の点と認識された三角形の辺の最長距離を確認することにより、凸型をテストすることができる。次いで、より良い表現のために三角形の辺を改善することができる。まず、矢印ストロークまたはストローク断片の各点と三角形の辺との間の距離を演算し、ストロークまたはストローク断片の各点が、認識された三角形のどの一辺に属すかを判定することができる。次いで、認識された三角形の各辺の位置と向きを、矢印ストロークまたはストローク断片の対応する点のロバスト回帰の結果に従い、再演算することができる。これで、最終スケルトンと認識された任意の矢印を組み合わせることにより、完全なコネクタを生成することができる。
【００５４】
上記のシステムおよび方法によって、すべてのコンテナとコネクタが生成されると、インク入力内の手描きオブジェクトを完全に認識し、生成することができる。本発明を使用して、ユーザは、手描き入力に対する制約なしに、図面とフローチャートを自由に描くことができる。このシステムおよび方法がいかなるインクでも入力として受け入れることができるように、１つの形状は多くのストロークを有することができ、ストロークの入力順序は任意であってよい。さらに、ストロークをなぞったり、オーバーラップしたりしてもよい。いずれにせよ、このシステムおよび方法は、正確な形状を自動的に検出することができる。
【００５５】
上記の詳細な説明から分かるように、本発明は、手書きオブジェクトの形状認識のためのシステムおよび方法を提供する。このシステムおよび方法は、ストロークの入力順序と手描き形状を形成することのできる複数のストロークに左右されない点で優れている。さらに、提供されたシステムおよび方法は、柔軟であり、および伸張性を有する。これで分かるように、図面および図表を含む描画において、いかなる閉じたコンテナおよび開いたままのコネクタでも認識するために、本発明を使用することができる。認識されると、形状のタイプ、位置、向き、およびサイズを提供することができる。したがって、この方法およびシステムは、今日の演算で必要とされる重要な利点および利得を提供する。
【００５６】
本発明には様々な変更および代替構成が成されるが、本発明の特定の例示の実施形態を図面に示し、上記で詳細に説明した。しかし、本発明を開示した特定の形式に限定することは意図せず、反対に、本発明の趣旨および範囲に含まれるすべての変更、代替構成、および等価形態を対象とすることを意図する。
ということを理解されたい。
【図面の簡単な説明】
【００５７】
【図１】本発明を組み込むことのできる、コンピュータシステムを全体的に表すブロック図である。
【図２】本発明の一態様により、手描きオブジェクトの形状認識のための、システムコンポーネントのアーキテクチャ例を全体的に表すブロック図である。
【図３】本発明の一態様により、手描きオブジェクトの形状認識のために行われるステップを全体的に表すフローチャートである。
【図４】本発明の一態様により、コンテナとコネクタの形状認識を行うステップの一実施形態を全体的に表すフローチャートである。
【図５】本発明の一態様により、形状認識を実行する際に使用するための、全体の統計的特徴と特定形状の規則ベースの記述の両方を組み合わせることのできる、決定ツリーを全体的に表す例図である。
【図６】本発明の一態様により、閉じたコンテナの形状を認識するために行われるステップの一実施形態を全体的に表すフローチャートである。
【図７】本発明の一態様により、真円度テストを実行するために行われるステップの一実施形態を全体的に表すフローチャートである。
【図８】本発明の一態様により、閉じたコンテナの形状が円形か楕円形かを区別するために、分類子によって行われるステップを全体的に表すフローチャートである。
【図９】本発明の一態様により、閉じたコンテナの形状がそうである可能性のあるポリゴンのタイプを区別するために、分類子によって行われるステップの一実施形態を全体的に表すフローチャートである。
【図１０】本発明の一態様により、形状周囲の凸包内の最大限に内接したポリゴンにより、形状のストロークを全体的に表す例図である。
【図１１】本発明の一態様により、形状周囲の凸包内の形状および最大限に内接したポリゴンのストローク間の最大距離を全体的に表す例図である。
【図１２】本発明の一態様により、手描き形状のストロークからの、認識されたポリゴンの辺の改善を全体的に表す例図である。
【図１３】本発明の一態様により、コネクタの形状を認識するために行われるステップを全体的に表すフローチャートである。
【図１４】本発明の一態様により、２つのコンテナ間にある１つのコネクタを全体的に表す例図である。
【図１５】本発明の一態様により、スケルトンストロークまたはストローク断片をマージする例を全体的に表す例図である。
【符号の説明】
【００５８】
１００  コンピューティングシステム環境
１１０  コンピュータ
【図１】
2005100417.tif 000005
【図２】
2005100417.tif 000006
【図３】
2005100417.tif 000007
【図４】
2005100417.tif 000008
【図５】
2005100417.tif 000009
【図６】
2005100417.tif 000010
【図７】
2005100417.tif 000011
【図８】
2005100417.tif 000012
【図９】
2005100417.tif 000013
【図１０】
2005100417.tif 000014
【図１１】
2005100417.tif 000015
【図１２】
2005100417.tif 000016
【図１３】
2005100417.tif 000017
【図１４】
2005100417.tif 000018
【図１５】
2005100417.tif 000019