(57)【特許請求の範囲】
【請求項１】
ハンド・ドローされた形状を検出するコンピュータ・システムであって、
ハンド・ドローされた形状を含むインク入力を受け取るチャート・ディテクタと、
前記チャート・ディテクタに動作可能に結合された、前記インク入力内の閉じたコンテナを検出するコンテナ・ディテクタと、
前記チャート・ディテクタに動作可能に結合されたコネクタ・ディテクタであって、前記インク入力内の閉じたコンテナの全てを検出した後に、分離された前記コンテナに膨張処理を施すことにより、前記インク入力内のコネクタを検出して、前記の検出されたコネクタを、対応するコンテナに隣接させるコネクタ・ディテクタと、
を備えることを特徴とするコンピュータ・システム。
【請求項２】
前記チャート・ディテクタに動作可能に結合された、前記チャート・ディテクタにインク入力を送るインク・パーサをさらに備えることを特徴とする、請求項１に記載のシステム。
【請求項３】
前記インク・パーサに動作可能に結合された、ハンド・ドローされた形状を認識する形状リコグナイザをさらに備えることを特徴とする、請求項２に記載のシステム。
【請求項４】
前記形状リコグナイザは、前記形状リコグナイザに動作可能に結合されたコンテナ・リコグナイザを備えることを特徴とする、請求項３に記載のシステム。
【請求項５】
前記形状リコグナイザは、前記形状リコグナイザに動作可能に結合されたコネクタ・リコグナイザを備えることを特徴とする、請求項３に記載のシステム。
【請求項６】
請求項１に記載の前記システムを備えるコンピュータ実行可能コンポーネントを有することを特徴とするコンピュータ可読媒体。
【請求項７】
チャート・ディテクタと、該チャート・ディテクタに動作可能に結合されたコンテナ・ディテクタと、前記チャート・ディテクタに動作可能に結合されたコネクタ・ディテクタとを備えるコンピュータ・システムにおいて、ハンド・ドローされた形状を検出する方法であって、
前記チャート・ディテクタが、ハンド・ドローされた形状を含むインク入力を受け取るステップ、
前記コンテナ・ディテクタが前記インク入力内の閉じたコンテナを検出するステップ、および
前記インク入力内の閉じたコンテナの全てが検出された後に、前記コネクタ・ディテクタが、分離された前記コンテナに膨張処理を施すことにより、前記インク入力内のコネクタを検出して、前記の検出されたコネクタを、対応するコンテナに隣接させるステップ
を備えることを特徴とする方法。
【請求項８】
前記インク入力を解析して、前記インク入力内でライティングをドローイングから区別するステップをさらに備えることを特徴とする、請求項７に記載の方法。
【請求項９】
チャート検出を実行して、インク入力内の図のストロークを識別するステップをさらに備えることを特徴とする、請求項７に記載の方法。
【請求項１０】
形状認識を実行して、前記インク入力内で検出された各コンテナおよび各コネクタの形状を認識するステップをさらに備えることを特徴とする、請求項７に記載の方法。
【請求項１１】
前記インク入力内で認識された各コンテナおよび各コネクタを用いてドローイングを生成するステップをさらに備えることを特徴とする、請求項１０に記載の方法。
【請求項１２】
コンテナ検出を実行するステップは、空間検索を実行してコンテナを検出するステップを備えることを特徴とする、請求項７に記載の方法。
【請求項１３】
コンテナ検出を実行するステップは、イメージ・グリッドを生成するステップ、および前記生成されたイメージ・グリッド上で前記インク入力からのストロークを位置決めするステップを備えることを特徴とする、請求項７に記載の方法。
【請求項１４】
コンテナ検出を実行するステップは、イメージ・グリッド上で位置決めされた前記インク入力のストロークが交差する前記イメージ・グリッドのグリッドをマークするステップを備えることを特徴とする、請求項７に記載の方法。
【請求項１５】
コンテナ検出を実行するステップは、イメージ・グリッド上で位置決めされた前記インク入力のストロークと交差するマークされたグリッドに達するまで、前記イメージ・グリッドの最も外の空白グリッドを塗りつぶすステップを備えることを特徴とする、請求項７に記載の方法。
【請求項１６】
コンテナ検出を実行するステップは、イメージ・グリッド上で位置決めされた前記インク入力のストロークと交差するマークされたグリッドに達するまで、前記イメージ・グリッドの空白グリッドの島を塗りつぶすステップを備えることを特徴とする、請求項７に記載の方法。
【請求項１７】
コンテナ検出を実行するステップは、コンテナ候補が有効なコンテナであることを検査するステップを備えることを特徴とする、請求項７に記載の方法。
【請求項１８】
コンテナ候補が有効なコンテナであることを検査するステップは、イメージ・グリッドで位置決めされた前記コンテナ候補のストロークと交差するすべての境界グリッドが、塗りつぶされた島グリッドに隣接することを検査するステップを備えることを特徴とする、請求項１７に記載の方法。
【請求項１９】
コンテナ候補が有効なコンテナであることを検査するステップは、イメージ・グリッド内の境界グリッドと交差しない、前記イメージ・グリッド上で位置決めされた候補コンテナのすべてのストロークを除去するステップを備えることを特徴とする、請求項１７に記載の方法。
【請求項２０】
コンテナ候補が有効なコンテナであることを検査するステップは、前記コンテナ候補が閉じたコンテナであることを決定するステップを備えることを特徴とする、請求項１７に記載の方法。
【請求項２１】
コンテナ候補が有効なコンテナであることを検査するステップは、コンテナ候補の間で共有されるすべてのドローイング・ストロークを分離するステップを備えることを特徴とする、請求項１７に記載の方法。
【請求項２２】
すべてのドローイング・ストロークを分離するステップは、前記ドローイング・ストロークの各点の前記ドローイング・ストロークを共有する各候補コンテナの中央までの平均距離を計算するステップと、前記ドローイング・ストロークの各点のその中心までの最短の平均距離を有するコンテナ候補に属するものとして、ドローイング・ストロークを割り当てるステップとを備えることを特徴とする、請求項２１に記載の方法。
【請求項２３】
コンテナ検出を実行するステップは、コンテナを検出するために時間順検索を実行するステップを備えることを特徴とする、請求項７に記載の方法。
【請求項２４】
時間順検索を実行するステップは、有効境界長を総境界長で割ったものとして定義される有効境界比を計算するステップを含み、境界は、イメージ・グリッド上で位置決めされた前記インク入力のストロークと交差するマークされたグリッドを備えることを特徴とする、請求項２３に記載の方法。
【請求項２５】
時間順検索を実行するステップは、有効領域面積を総面積で割ったものとして定義される有効面積比を計算するステップを含み、領域面積が、マークされたグリッドの境界内の、イメージ・グリッド上で位置決めされた前記インク入力のストロークと交差する面積を備えることを特徴とする、請求項２３に記載の方法。
【請求項２６】
時間順検索を実行するステップは、入力ストロークのシーケンスがコンテナを形成する尤度を計算することによって、前記インク入力の前記ストロークから前記コンテナを決定するステップを備えることを特徴とする、請求項２３に記載の方法。
【請求項２７】
入力ストロークのシーケンスがコンテナを形成する前記尤度を計算するステップは、前記入力ストロークを、それぞれがコンテナを形成するセグメントにグループ化する動的計画法を使用するステップを備えることを特徴とする、請求項２６に記載の方法。
【請求項２８】
コンテナ検出を実行するステップは、コンテナに属するすべてのコンテンツを検出するためにコンテンツ検出を実行するステップを備えることを特徴とする、請求項７に記載の方法。
【請求項２９】
コンテンツ検出を実行するステップは、前記コンテンツを囲む最小の境界長方形を決定するステップ、および、その面積を計算するステップを備えることを特徴とする、請求項２８に記載の方法。
【請求項３０】
コンテンツ検出を実行するステップは、前記最小の境界長方形と各交差するコンテナとの交差面積比を計算するステップ、および、各交差するコンテナとの前記最小の境界長方形の最大の交差面積比を有する前記コンテナを選択するステップを備えることを特徴とする、請求項２８に記載の方法。
【請求項３１】
前記インク入力内の各コネクタに対してコネクタ検出を実行するステップは、イメージ・グリッドに位置決めされた前記インク入力の辿っていないストロークと交差するグリッドに隣接しない境界を有するコンテナを膨張させるステップを備えることを特徴とする、請求項７に記載の方法。
【請求項３２】
コンテナを膨張させるステップは、前記辿っていないストロークと交差するグリッドに達するまで、前記コンテナの前記境界を囲むグリッドをマークするステップを備えることを特徴とする、請求項３１に記載の方法。
【請求項３３】
コンテナを膨張させるステップは、別のコンテナの境界グリッドに達するまで、前記コンテナの前記境界を囲むグリッドをマークするステップを備えることを特徴とする、請求項３１に記載の方法。
【請求項３４】
前記インク入力内のコネクタごとにコネクタ検出を実行するステップは、イメージ・グリッド上で位置決めされた前記インク入力の辿っていないストロークと交差するグリッドを塗りつぶすステップを備えることを特徴とする、請求項７に記載の方法。
【請求項３５】
コネクタ検出を実行するステップは、コネクタ候補が有効なコネクタであることを検査するステップを備えることを特徴とする、請求項７に記載の方法。
【請求項３６】
コネクタ候補が有効なコネクタであることを検査するステップは、前記コネクタ候補のストロークがコンテナに接続されることを検証するステップを備えることを特徴とする、請求項３５に記載の方法。
【請求項３７】
コネクタ候補が有効なコネクタであることを検査するステップは、コネクタ候補の前記ストロークの交差する点の数が、前記コネクタ候補がつなぐ可能性がある隣接するコンテナの数を超えないことを検証するステップを備えることを特徴とする、請求項３５に記載の方法。
【請求項３８】
コネクタ候補の前記ストロークの交差する点の数が、前記コネクタ候補がつなぐ可能性がある隣接するコネクタの数を超えないことを検証するステップは、前記コネクタ候補に沿って移動することができるスライディング・ウィンドウを使用するステップを備えることを特徴とする、請求項３７に記載の方法。
【請求項３９】
請求項７に記載の方法を実行するコンピュータ実行可能命令を有することを特徴とするコンピュータ可読媒体。
【請求項４０】
ハンド・ドローされた形状を検出するコンピュータ・システムであって、
ハンド・ドローされた形状を含むインク入力を受け取る手段と、
前記チャート・ディテクタに動作可能に結合された、前記インク入力内の閉じたコンテナを検出するコンテナ検出手段と、
前記チャート・ディテクタに動作可能に結合されたコネクタ検出手段であって、前記インク入力内の閉じたコンテナの全てを検出した後に、分離された前記コンテナに膨張処理を施すことにより、前記インク入力内のコネクタを検出して、前記の検出されたコネクタを、対応するコンテナに隣接させるコネクタ検出手段と
を備えることを特徴とするコンピュータ・システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全般的にはコンピュータ・システムに関し、具体的には、インク入力内のハンド・ドローされたオブジェクト（hand-drawn object）を検出する改善されたシステムおよび方法に関する。
【背景技術】
【０００２】
ハンド・ドローされたオブジェクトの形状を検出し、認識する能力は、ユーザがインク入力またはインク・ノートを使用して自分のコンピュータに直接に描く（draw）ことを可能にするのに重要である。現在のハードウェアおよびソフトウェアは、（handwriting：手書き文字）を表すインクを適度に取り込むことができる場合があるが、現在は、ハンド・ドローされたオブジェクトの意味を同様に認識し、表すことができない。その結果、ユーザは、その代わりに、メニュー・ベースのアプリケーション・プログラムを使用して、オブジェクトのドローイングを作成する。ユーザがドローイング・グリッドを選択し、それにコピーするために、さまざまな形状を、そのようなアプリケーション・プログラムによって提示することができる。コピーされた形状は、所望のスケールにサイズを変更することができ、ユーザは、ドローイングが完了するまで、ドローイング・グリッドに追加の形状を配置し、サイズを変更することを継続することができる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
ハンド・ドローされたオブジェクトの形状認識に焦点を合わせた研究は、今日まで、重要な結果を産んでいない。たとえば、特定の順序で作られる特定の数のストロークから円または箱などの単純な幾何形状を認識できる増分認識アルゴリズム（incremental recognition algorithm）が、使用されてきた。しかし、そのような増分アルゴリズムは、特定のハンド・ドローされた形状を認識するために、ストロークの順序に頼り、かつ／または特定の個数のストロークを前提とする。そのような手法は、複数の理由から、堅牢になることができない。まず第１に、増分アルゴリズムのどれもが、ストロークのどの集合が、これらが特定の形状を表すという理由で、一緒に属するか（グループをなすか）ということを決定するというグループ化問題を解決しない。ある形状に属するストロークを一緒にグループ化する能力がないので、増分アルゴリズムは、矢印などのマルチ・ストローク形状に対処することができない。さらに、増分アルゴリズムは、形状に関して、ストロークの順序に頼り、かつ／または特定の数のストロークを前提とするので、増分アルゴリズムは、形状のドローイング中にストロークが上書きされる可能性のあるオーバー・トレーシング問題を解決することができない。
【０００４】
必要なものは、所与の形状を形成するのに必要なストローク入力順序および／またはストローク数に左右されない（敏感ではない）、ハンド・ドローされたオブジェクトの形状を検出し、認識する方法ある。そのようなシステムおよび方法は、マルチ・ストロークのハンド・ドローされた形状を検出でき、異なる形状を表すストロークのどの集合が一緒に属するか（グループをなすか）を決定できなければならない。
【課題を解決するための手段】
【０００５】
簡単に言えば、本発明は、インク入力内のハンド・ドローされたオブジェクトを検出するシステムおよび方法を提供する。このために、インク入力内の図またはチャートなどのドローイングを検出できるディテクタ（detector）を提供する。ディテクタに、コンテナに属するストロークを見つけるコンテナ・ディテクタと、コネクタに属するストロークを見つけるコネクタ・ディテクタを含めることができる。ハンド・ドローされた形状は、空間検索および時間順検索を実行して各コンテナのストロークを識別することによって検出することができる。
【０００６】
一実施形態では、適当なサイズのイメージ・グリッドにインク・ストロークをあてはめ（fit）、ドローイング・ストロークと交差する（intersect：重なる）グリッドをマーク（mark）することができる。イメージ・グリッドの外側のエッジから始めて、最も外側の空白グリッドを、ドローイング・ストロークと交差するマークされたグリッドに達するまで、塗りつぶす（flood-fill）ことができる。次に、マークされたグリッドの中に現れる空白グリッドの島を、島の境界に達するまで塗りつぶすことができる。コンテナ候補のドローイング・ストロークを、塗りつぶされた島を囲む境界から識別することができる。コンテナ候補を検査して、それが有効なコンテナであることを確認することができる。
【０００７】
一実施形態で、時間順検索を、空間検索の後に実行して、ドローイング・ストロークのオーバーラップを処理することもできる。一般に、連続するストロークのシーケンスから形成されるコンテナは、時間順検索を使用して、入力ストロークのシーケンスがコンテナを形成する尤度（likelihood）を決定することによって見つけることができる。時間順検索を実行することによって見つけられる別のコンテナを、空間検索に使用されるイメージ・グリッド内でマークすることができ、その結果、見つけられるコンテナのすべてを、後にコンテンツ検出およびコネクタ検出中に使用するためにイメージ・グリッドに含めることができる。
【０００８】
コンテナおよびそれに関連付けられるコンテンツが、イメージ・グリッド内で検出されたならば、コネクタ検出を実行することができる。一般に、検索は、コンテナをマークされたイメージ・グリッド内で、実行され、辿っていないドローイング・ストロークのグリッドの間でコネクタを検出することができる。辿っていないドローイング・ストロークに隣接しないすべてのコンテナを、コンテナの境界を囲むマークされたグリッドを用いて膨張させることができ、その結果、コネクタが対応するコンテナに隣接するようにすることができる。次に、辿っていないドローイング・ストロークのグリッドを、塗りつぶし、膨張したコンテナを含む複数のコンテナに達するこの塗りつぶされたグリッドによって、コネクタ候補の対応するドローイング・ストロークを識別することができる。すべてのコネクタ候補を検査して、それらが有効なコンテナであることを確認することができる。
【０００９】
有利なことに、このシステムおよび方法は、ハンド・ドローされた形状を形成する可能性があるストロークの入力順序およびストロークの個数に、左右されない（insensitive）。さらに、このシステムおよび方法を使用して、ドローイング内のすべての閉じたコンテナおよび閉じていないコネクタを検出することができる。検出されたならば、その形状のタイプ、位置、方位、およびサイズを認識することができる。
【００１０】
他の長所は、図面と共に解釈される時に、下記の詳細な説明から明白になる。
【発明を実施するための最良の形態】
【００１１】
例示的なオペレーティング環境  
図１に、本発明を組み込むことができる適切なコンピューティング・システム環境１００の例を示す。コンピューティング・システム環境１００は、適切なコンピューティング環境の１例にすぎず、本発明の使用または機能性の範囲に関する制限を提案することを意図されたものではない。コンピューティング環境１００を、例示的なオペレーティング環境１００に示されたコンポーネントのいずれかまたはその組合せに関する依存性または要件を有するものと解釈されるべきではない。
【００１２】
本発明は、多数の他の汎用のまたは特殊目的のコンピューティング・システム環境またはコンピューティング構成を使用して動作する。本発明と共に使用するのに適する可能性がある周知のコンピューティング・システム、コンピューティング環境、および／またはコンピューティング構成の例に、パーソナル・コンピュータ、サーバ・コンピュータ、ハンドヘルド・デバイス、ラップトップ・デバイス、タブレット・デバイス、ヘッドレス・サーバ、マルチ・プロセッサ・システム、マイクロ・プロセッサ・ベースのシステム、セットトップボックス、プログラマブル民生用電子機器、ネットワークＰＣ、ミニ・コンピュータ、メインフレーム・コンピュータ、上記のシステムまたはデバイスのいずれかを含む分散コンピューティング環境、および類似物が含まれるが、これらに制限はされない。
【００１３】
本発明を、プログラム・モジュールなど、コンピュータによって実行されるコンピュータ実行可能命令の全般的な文脈で説明することができる。一般に、プログラム・モジュールには、特定のタスクを実行するか特定の抽象データ型を実装する、ルーチン、プログラム、オブジェクト、コンポーネント、データ構造などが含まれる。本発明を、通信ネットワークを介してリンクされたリモート処理デバイスによってタスクが実行される分散コンピューティング環境で実施することもできる。分散コンピューティング環境では、プログラム・モジュールを、メモリ・ストレージ・デバイスを含むローカルおよび／またはリモートのコンピュータ・ストレージ・メディアに配置することができる。
【００１４】
図１を参照すると、本発明を実施する例示的システムに、コンピュータ１１０の形の汎用コンピューティング・デバイスが含まれる。コンピュータ１１０のコンポーネントに、処理ユニット１２０、システム・メモリ１３０、およびシステム・メモリを含むさまざまなシステム・コンポーネントを処理ユニット１２０に結合するシステム・バス１２１が含まれる。システム・バス１２１は、メモリ・バスまたはメモリ・コントローラ、周辺バス、およびさまざまなバス・アーキテクチャのいずれかを使用するローカル・バスを含む複数のタイプのバス構造のいずれかとすることができる。制限ではなく例として、そのようなアーキテクチャに、Ｉｎｄｕｓｔｒｙ  Ｓｔａｎｄａｒｄ  Ａｒｃｈｉｔｅｃｔｕｒｅ（ＩＳＡ）バス、マイクロチャネル・アーキテクチャ（ＭＣＡ）バス、Ｅｎｈａｎｃｅｄ  ＩＳＡ（ＥＩＳＡ）バス、Ｖｉｄｅｏ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｓｔａｎｄａｒｄｓ  Ａｓｓｏｃｉａｔｉｏｎ（ＶＥＳＡ）ローカル・バス、およびメザニン・バスとも称するＰｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ（ＰＣＩ）バスが含まれる。
【００１５】
コンピュータ１１０に、通常は、さまざまなコンピュータ可読メディアが含まれる。コンピュータ可読メディアは、コンピュータ１１０によってアクセスできるすべての使用可能メディアとすることができ、コンピュータ可読メディアには、揮発性メディアおよび不揮発性メディア、ならびに取外し可能メディアおよび取外し不能メディアの両方が含まれる。制限ではなく例として、コンピュータ可読メディアに、コンピュータ・ストレージ・メディアと通信メディアが含まれる。コンピュータ・ストレージ・メディアには、コンピュータ可読命令、データ構造、プログラム・モジュール、または他のデータなどの情報のストレージに関してあらゆる方法またはテクノロジで実装される、揮発性および不揮発性の、取外し可能および取外し不能のメディアが含まれる。コンピュータ・ストレージ・メディアには、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュ・メモリ、または他のメモリ・テクノロジ、ＣＤ−ＲＯＭ、ディジタル多用途ディスク（ＤＶＤ）、または他の光ディスク・ストレージ、磁気カセット、磁気テープ、磁気ディスク・ストレージ、または他の磁気ストレージデバイス、あるいは所望の情報を保管するのに使用でき、コンピュータ１１０によってアクセスできる他のメディアが含まれるが、これに制限はされない。通信メディアによって、通常は、搬送波または他のトランスポート機構などの変調されたデータ信号内にコンピュータ可読命令、データ構造、プログラム・モジュール、または他のデータが具現化され、通信メディアには、すべての情報配信メディアが含まれる。用語「変調されたデータ信号」は、信号内で情報をエンコードする形でその１つまたは複数の特性を設定され、または変更された信号を意味する。制限ではなく例として、通信メディアに、有線ネットワークまたは直接配線接続などの有線メディアと、音響、ＲＦ、赤外線、および他の無線メディアなどの無線メディアが含まれる。上記のいずれかの組合せも、コンピュータ可読メディアの範囲に含まれなければならない。
【００１６】
システム・メモリ１３０に、読取専用メモリ（ＲＯＭ）１３１およびランダム・アクセス・メモリ（ＲＡＭ）１３２など、揮発性メモリおよび／または不揮発性メモリの形のコンピュータ可読メディアが含まれる。起動中などにコンピュータ１１０内の要素の間での情報の転送を助ける基本ルーチンを含む基本入出力システム１３３（ＢＩＯＳ）が、通常はＲＯＭ１３１に保管される。ＲＡＭ１３２には、通常は、処理ユニット１２０から直接にアクセス可能な、および／または処理ユニット１２０によって現在操作されている、データおよび／またはプログラム・モジュールが含まれる。制限ではなく例として、図１に、オペレーティング・システム１３４、アプリケーション・プログラム１３５、他のプログラム・モジュール１３６、およびプログラム・データ１３７を示す。
【００１７】
コンピュータ１１０に、他の取外し可能／取外し不能、揮発性／不揮発性コンピュータ・ストレージ・メディアを含めることもできる。例としてのみ、図１に、取外し不能不揮発性磁気メディアから読み取ったり、これに書き込んだりするハードディスク・ドライブ１４１、取外し可能不揮発性磁気ディスク１５２から読み取ったり、これに書き込んだりする磁気ディスク・ドライブ１５１、ＣＤ  ＲＯＭまたは他の光メディアなどの取外し可能不揮発性光ディスク１５６から読み取ったり、これに書き込んだりする光ディスク・ドライブ１５５を示す。例示的オペレーティング環境で使用することができる他の取外し可能／取外し不能、揮発性／不揮発性コンピュータ・ストレージ・メディアに、磁気テープ・カセット、フラッシュ・メモリ・カード、ディジタル多用途ディスク、ディジタル・ビデオ・テープ、ソリッド・ステートＲＡＭ、ソリッド・ステートＲＯＭ、および類似物が含まれるが、これに制限はされない。ハードディスク・ドライブ１４１は、通常、インターフェース１４０などの取外し不能メモリ・インターフェースを介してシステム・バス１２１に接続され、磁気ディスク・ドライブ１５１および光ディスク・ドライブ１５５は、通常は、インターフェース１５０などの取外し可能メモリ・インターフェースによってシステム・バス１２１に接続される。
【００１８】
上で説明し、図１に示したドライブおよびそれに関連するコンピュータ・ストレージ・メディアは、コンピュータ１１０に、コンピュータ可読命令、データ構造、プログラム・モジュール、および他のデータのストレージを提供する。図１では、たとえば、ハードディスク・ドライブ１４１が、オペレーティング・システム１４４、アプリケーション・プログラム１４５、他のプログラム・モジュール１４６、およびプログラム・データ１４７を格納するものとして図示されている。これらのコンポーネントを、オペレーティング・システム１３４、アプリケーション・プログラム１３５、他のプログラム・モジュール１３６、およびプログラム・データ１３７と同一または異なるもののいずれかとすることができることに留意されたい。オペレーティング・システム１４４、アプリケーション・プログラム１４５、他のプログラム・モジュール１４６、およびプログラム・データ１４７は、最低限でもこれらが異なるコピーであることを示すために、本明細書では別の符号を与えられている。ユーザは、タブレットまたは電子ディジタイザ１６４、マイクロホン１６３、キーボード１６２、および通常はマウス、トラック・ボール、またはタッチ・パッドと称するポインティング・デバイス１６１などの入力デバイスを介してコンピュータ１１０にコマンドおよび情報を入力することができる。図１に示されていない他の入力デバイスに、ジョイスティック、ゲーム・パッド、衛星パラボラ・アンテナ、スキャナ、あるいは、バイオメトリック・センサ、環境センサ、位置センサ、または他のタイプのセンサを含むデバイスを含む他のデバイスを含めることができる。上記および他の入力デバイスは、しばしば、システム・バスに結合されたユーザ入力インターフェース１６０を介して処理ユニット１２０に接続されるが、パラレル・ポート、ゲームポート、またはＵＳＢ（universal serial bus）など、他のインターフェースおよびバス構造によって接続することができる。モニタ１９１または他のタイプのディスプレイ・デバイスも、ビデオ・インターフェース１９０などのインターフェースを介してシステム・バス１２１に接続することができる。モニタ１９１は、タッチ・スクリーン・パネルまたは類似物と一体化することもできる。タブレット・タイプのパーソナル・コンピュータなどで、モニタおよび／またはタッチ・スクリーン・パネルを、コンピューティング・デバイス１１０が組み込まれるハウジングに物理的に結合できることに留意されたい。さらに、コンピューティング・デバイス１１０などのコンピュータに、スピーカ１９５およびプリンタ１９６など、出力周辺インターフェース１９４を介して接続できる他の周辺出力デバイスを含めることもできる。
【００１９】
コンピュータ１１０は、リモート・コンピュータ１８０など、１つまたは複数のリモート・コンピュータへの論理接続を使用して、ネットワーク化された環境で動作することができる。リモート・コンピュータ１８０は、パーソナル・コンピュータ、サーバ、ルータ、ネットワークＰＣ、ピア・デバイス、または他の一般的なネットワーク・ノードとすることができ、リモート・コンピュータ１８０には、通常、コンピュータ１１０に関して上で説明した要素の多数またはすべてが含まれるが、図１にはメモリ・ストレージ・デバイス１８１だけを示した。図１に示された論理接続に、ローカル・エリア・ネットワーク（ＬＡＮ）１７１および広域ネットワーク（ＷＡＮ）１７３が含まれるが、他のネットワークも含めることができる。そのようなネットワーキング環境は、オフィス、会社全体のコンピュータ・ネットワーク、イントラネット、およびインターネットでありふれたものである。ＬＡＮネットワーキング環境で使用される時に、コンピュータ１１０は、ネットワーク・インターフェースまたはネットワーク・アダプタ１７０を介してＬＡＮ１７１に接続される。ＷＡＮネットワーキング環境で使用される時に、コンピュータ１１０に、通常、インターネットなどのＷＡＮ１７３を介する通信を確立する、モデム１７２または他の手段が含まれる。モデム１７２は、内蔵または外付けとすることができるが、ユーザ入力インターフェース１６０または他の適当な機構を介してシステム・バス１２１に接続することができる。ネットワーク化された環境では、コンピュータ１１０に関して示したプログラム・モジュールまたはその一部を、リモート・メモリ・ストレージ・デバイスに保管することができる。制限ではなく例として、図１に、メモリ・デバイス１８１に常駐するものとしてリモート・アプリケーション・プログラム１８５を示す。図示のネットワーク接続が、例示的であり、コンピュータの間の通信リンクを確立する他の手段を使用できることを諒解されたい。
【００２０】
ハンド・ドローされたオブジェクトの検出  
本発明は、全般的に、インク入力内の図（diagram）またはチャート（chart）などのドローイング（drawing：線描）を検出するシステムおよび方法を対象とする。本明細書で使用されるハンド・ドローされたオブジェクトは、手で書かれた、文字以外の形状またはドローイングを意味する。ユーザは、ハンド・ドローされた入力に対する制約なしに、自由に図およびフローチャートを描くことができる。ある形状が、複数のストロークを有することができ、ストロークの入力順序を任意とすることができ、その結果、このシステムおよび方法は、入力としてすべてのインクを受け入れることができる。本明細書で使用されるインクは、全般的に、手書きの１つまたは複数のストロークを意味する。さらに、ストロークは、オーバー・トレースまたはオーバーラップすることができる。どの場合でも、このシステムおよび方法は、正しい形状を自動的に検出する。
【００２１】
具体的に言うと、このシステムおよび方法は、形状認識の目的で、コンテナおよびコンテナの間に描かれるコネクタのハンド・ドローされた形状を検出することができる。本明細書で使用されるコンテナは、閉じたドローイング・オブジェクトを意味する。本明細書で使用されるコネクタは、コンテナをつなぐドローイング・オブジェクトを意味する。理解されるように、本明細書に記載のさまざまなブロック図、流れ図、およびシナリオは、例にすぎず、本発明が適用される多数の他のシナリオがある。
【００２２】
図面の図２に移ると、ハンド・ドローされたオブジェクトの検出および形状認識に関するシステム・コンポーネントの例示的なアーキテクチャを全般的に示すブロック図が示されている。当業者は、この図に示されたブロック内で実施される機能性を、別々のコンポーネントとして実施することができ、あるいは、複数またはすべてのブロックの機能性を、単一のコンポーネント内で実施できることを諒解するであろう。たとえば、チャート・ディテクタ２０４の機能性を、形状リコグナイザ（recognizer）２０６に含めることができる。あるいは、コンテナ・ディテクタ２１２の機能性を、別々のコンポーネントとして実施することができる。
【００２３】
インク・パーサ２０２は、ドローイング・オブジェクトを有するインクを含む、すべてのインクを受け入れることができる。インク・パーサ２０２に、動作可能に結合されたチャート・ディテクタ２０４および動作可能に結合された形状リコグナイザ２０６を含めることができる。一般に、チャート・ディテクタ２０４および形状リコグナイザ２０６は、カーネル・コンポーネント、アプリケーション・プログラム、リンクされたライブラリ、オブジェクトなど、すべてのタイプの実行可能ソフトウェア・コードとすることができる。チャート・ディテクタ２０４に、動作可能に結合されたコンテナ・ディテクタ２１２および動作可能に結合されたコネクタ・ディテクタ２１４を含めることができ、形状リコグナイザ２０６に、動作可能に結合されたコンテナ・リコグナイザ２０８および動作可能に結合されたコネクタ・リコグナイザ２１０を含めることができる。コンテナ・リコグナイザ２０８に、楕円／円クラシファイヤ（classifier）２１６、ポリゴン・クラシファイヤ２１８、三角形クラシファイヤ２２０、四辺形クラシファイヤ２２２などの任意の個数の動作可能に結合されたクラシファイヤを含めることができる。コネクタ・リコグナイザ２１０に、スケルトン・リコグナイザ２２４、矢印リコグナイザ２２６などの任意の個数の動作可能に結合されたリコグナイザを含めることができる。これらのコンポーネントのそれぞれを、カーネル・コンポーネント、アプリケーション・プログラム、リンクされたライブラリ、オブジェクト、または他のタイプの実行可能ソフトウェア・コードなど、すべてのタイプの実行可能ソフトウェア・コードとすることができる。
【００２４】
図３に、ハンド・ドローされたオブジェクトの検出および形状認識のために行われるステップを全般的に表す流れ図を示す。ステップ３０２で、ドローイング・オブジェクトを示すインクを含む、すべてのインクを解析することができる。たとえば、一実施形態で、インクのページを、入力として受け入れ、解析することができる。この実施形態では、インク・パーサが、たとえば、ページ上のインクについての先験的知識を有しないものとすることができる。したがって、ワード・グルーピング（word grouping）、ライティング／ドローイング分類（writing/drawing classification）、およびドローイング・グルーピング（drawing grouping）などの基本的なアルゴリズムを実行することができる。ワード・グルーピングを実行するために、ストロークを、ワード（語）、行、およびブロックの階層にグループ化することができる。それを行うために、ワード・グルーピング・プロセスに、距離、幾何学的な相違点、および線形性ならびに他のストローク特徴を取り込むためのストロークの特徴抽出を含めることができる。ワード・グルーピング・プロセスに、時間情報に従ってストロークをグループ化するために動的計画法（dynamic programming）を含めることもできる。ワード・グルーピング・プロセスに、空間的情報に従ってストロークをグループ化するためにクラスタ化（clustering）を含めることもできる。グループ内で識別されるワード（語）、行、およびブロックは、必ずしも実際の意味論的なワード、行、およびブロックに対応しないものとすることができる。実際に、これらのグループに、ハンド・ドローされたオブジェクトのストロークが含まれる場合がある。
【００２５】
ライティング（writing）／ドローイング（drawing）分類を実行するために、ライティングをドローイングから区別することができるさまざまな特徴を識別することができる。たとえば、曲率、密度、および他の手書きモデル特徴などの単一ワード特徴を使用して、ライティングをドローイングから区別することができる。一実施形態で、時間的コンテキスト特徴および空間的コンテキスト特徴などのコンテキスト特徴を使用して、ライティングをドローイングから区別することができる。さまざまな特徴のそれぞれを、ファジイ関数にマッピングすることができ、ライティングとドローイングの間の分類を、ファジイ関数の組合せによって決定することができる。
【００２６】
ワード・グルーピングおよびライティング／ドローイング分類を実行した後に、ドローイング・グルーピングを実行することによって、複数のドローイング・ストロークも体系付けることができる。ドローイング・グルーピングを実行するために、ドローイング・ストロークを、それらの間の空間的関係に従って独立のオブジェクトにグループ化することができる。効率的なグリッド・ベースの手法を使用して、インク・ストロークを、適当なサイズのイメージ・グリッドにあてはめる（fit）ことができる。イメージ・グリッドにラベルを付けて、接続されたコンポーネントを見つけることができる。各接続されたコンポーネントは、ドローイング・オブジェクトに対応するものとすることができる。次に、ヒューリスティック・ルール（Heuristic rules）を適用して、ドローイング・オブジェクトを調整する。
【００２７】
ステップ３０４で、ドローイング・オブジェクトに属する可能性があるすべてのストロークを見つけることによって、ドローイング・ストロークをグループ化するチャート検出が実行される。したがって、ユーザは、入力に関する制限なしで、自由に図およびフローチャートを描くことができる。たとえば、ある形状が多数のストロークを有することができ、入力順序を任意とすることができる。さらに、ストロークを、オーバー・トレースまたはオーバーラップすることができる。これらのすべての場合に対して、システムは、正しい形状を自動的に検出する。一実施形態で、ハイパー・グラフを使用して、図および流れ図を表すことができ、その結果、コンテナとコネクタの間の関係を完全に表すことができるようになる。したがって、複数のコンテナをつなぐコネクタを、この実施形態でサポートすることができる。
【００２８】
一実施形態で、コンテナ・ディテクタ２１２が、コンテナに属するすべてのストロークを見つけることができ、コネクタ・ディテクタ２１４が、コネクタに属するすべてのストロークを見つけることができる。それを行うために、最適検索を時間順で実行して、すべてのコンテナを検出することができる。効率的な検索を実行して、コンテナおよびコネクタを検出することもできる。最後に、コンテンツ検出を、検出されたコンテナごとに実行することができる。
【００２９】
ステップ３０６で、形状認識を実行して、コンテナおよびコネクタを認識することができる。すべてのストロークを、各コンテナおよび各コネクタについてグループ化した後に、一実施形態で、形状認識エンジン２０６を使用して、図またはチャートなどのドローイング内で、閉じたコンテナおよび閉じていないコネクタを認識することができる。認識されると、形状のタイプ、位置、方位、およびサイズを供給することができる。有利なことに、ストローク入力の順序およびストロークの数は、認識に影響しない。形状認識が実行されて、閉じたコンテナおよび閉じていないコネクタが認識された時に、ステップ３０８でドローイングを生成することができる。
【００３０】
図４に、ハンド・ドローされたオブジェクトの検出および形状認識を実行する際に使用される、インク入力内の手書きオブジェクトの構造的関係を全般的に表す例示的な図を示す。ルート４０２は、インク入力のページなどのインク入力を表すことができ、これには、ドローイング・オブジェクト４０４および４０６などの１つまたは複数のドローイング・オブジェクトを含めることができる。ドローイング・オブジェクト４０４は、テキストなどの関連コンテンツを有することができ、これは、ストローク４１４によって形成されるワード４１２を有する行４１０からなるものとすることができる段落４０８によって構造的に表すことができる。ドローイング・オブジェクト４０４および４０６は、インク入力内のハンド・ドローされたオブジェクトの検出および形状認識を実行することによって、検出し、認識することができる。
【００３１】
ハンド・ドローされたオブジェクトは、通常はコンテナおよびコネクタを含む、図またはチャートなどのドローイングとすることができる。図５Ａから５Ｃに、ハンド・ドローされたオブジェクトの検出および形状認識のためにサポートされているインク入力内のコンテナのタイプを全般的に表す例示的な図を示す。検出して認識することができるサポートされているコンテナは、囲まれた区域（enclosed area）を形成することができるすべてのタイプのコンテナとすることができる。そのようなコンテナの例が、図５Ａのコンテナ５０２、図５Ｂのコンテナ５０４、および図５Ｃのコンテナ５０６である。テキストなどのコンテンツを、コンテナの囲まれた区域内に含めることができる。図６Ａから６Ｄに、ハンド・ドローされたオブジェクトの検出および形状認識のためにサポートされているインク入力内のコネクタのタイプを全般的に表す例示的な図を示す。検出して認識することができるサポートされているコネクタは、複数のコンテナをつなぐすべてのタイプのコネクタとすることができる。そのようなコネクタに、図６Ａのコネクタ６０６などの矢印なし、図６Ｂのコネクタ６１２などの１つの矢印、図６Ｃのコネクタ６１８などの２つの矢印、または図６Ｄのコネクタ６２６などの３つの矢印を含めることができる。コネクタに、それがつなぐコンテナと同数の矢印を含めることができる。
【００３２】
図７に、コンテナおよびコネクタを有するチャートの検出のために行われるステップの一実施形態を全般的に表す流れ図を示す。コンテナ検出は、ステップ７０２で、ドローイング・オブジェクト内のコンテナごとに実行することができる。次に、ステップ７０４で、ドローイング・オブジェクト内のコネクタごとにコネクタ検出を実行することができる。一般に、ドローイング・オブジェクト内のコンテナは、２次元平面内の島とみなすことができ、コネクタは、それらの間の橋を形成する。一実施形態で、ドローイング・オブジェクトのストロークを、イメージ・グリッド上で位置決めすることができ、塗りつぶしアルゴリズムを使用して、コンテナおよびコネクタを検出することができる。
【００３３】
図８に、インク入力内のコンテナを検出するために行われるステップの一実施形態を全般的に表す流れ図を示す。ステップ８０２で、空間検索を実行して、コンテナを検出することができる。有利なことに、空間検索では、ストロークの任意の入力およびストロークのオーバー・トレーシングを扱うことができる。時間順の検索が、ストロークのオーバーラップを処理するのにより適するので、ステップ８０４で、時間順検索も実行して、オーバーラップする連続するストロークを用いて描かれたコンテナを検出することができる。時間順検索を実行することによって見つかる追加コンテナを、空間検索に使用されるイメージ・グリッド内でマークすることができ、その結果、見つかったコンテナのすべてを、後にコンテンツ検出およびコネクタ検出中に使用するためにイメージ・グリッドに含められるようになる。ステップ８０６で、すべてのコンテナに関して、コンテンツ検出を実行することができる。このステップでは、認識されるワードなどのコンテンツが、その境界ボックス（bounding box）の各コンテナとの交差面積（intersection area：共通面積、重なり面積）を計算することによって、一つのコンテナに属する可能性があるかどうかを決定することができる。
【００３４】
図９に、コンテナを検出する空間検索の実行のために行われるステップの一実施形態を全般的に表す流れ図を示す。ステップ９０２で、イメージ・グリッドを生成することができ、ドローイング・オブジェクトのストロークを、生成されたグリッドに位置決めすることができる。一実施形態で、グリッドサイズは、コンテナ・ストロークの間のギャップが除去されるが、コンテナの内部の中空区域が残される適当な値にセットすることができる。適当な値を選択するために、できる限り多数のコンテナが検出されることを保証するために、グリッドサイズを、テストデータを検査することによって経験的に決定することができる。そのような決定の結果として、グリッドサイズを、２．５ｍｍにセットすることができる。ステップ９０４で、ドローイング・ストロークと交差するグリッドをマークすることができる。どのグリッドがドローイング・ストロークと交差するかを検査するために、均一なステップ・サイズに従ってドローイング・ストロークを再サンプリングすることができ、再サンプリングされた点がイメージ・グリッド内で配置される位置を、検査することができる。図１０Ａからわかるように、コンテナ１００４、コネクタ１００６、およびコンテナ１００８のドローイング・ストロークと交差するグリッドが、イメージ・グリッド１００２内でマークされる。コンテナ１００４および１００８は、イメージ・グリッド１００２内で８の近傍を接続された区域になる。
【００３５】
ステップ９０６で、イメージ・グリッドの外側の辺（edge）から始めて、ドローイング・ストロークと交差するマークされたグリッドに達するまで、最も外側の空白グリッド（outmost blank grids）を塗りつぶすことができる。図１０Ｂに示されているように、コンテナ１００４および１００８は、イメージ・グリッド１００２内の空白グリッドの島に見える。ステップ９０８で、空白グリッドの島を、塗りつぶすことができる。島ごとに、１つの内側の空白グリッドを開始グリッドとして選択し、そのグリッドから、ストロークと交差するグリッドによって形成される境界に達するまで、隣接するすべての空白グリッドを塗りつぶすことができる。島の境界に達した時に、コンテナ候補を形成するストロークが記録される。たとえば、図１０Ｃに、コンテナ１００４および１００８の島が塗りつぶされて示されている。塗りつぶされた島の周囲の境界は、これらの候補コンテナのドローイング・ストロークと交差する。
【００３６】
空白グリッドの島を塗りつぶすステップは、有効なコンテナでない可能性がある候補コンテナの識別をもたらす場合がある。したがって、ステップ９１０で、候補コンテナを検査して、それが有効なコンテナであることを確認することができる。各候補コンテナのドローイング・ストロークが、塗りつぶされた島の境界グリッドの外にあるストロークを有する場合がある。たとえば、図１１Ａに、塗りつぶされた島１１１０を囲む境界グリッド１１０６の外側にあるストローク１１０４および１１１２を有する候補コンテナ１１０８を有するイメージ・グリッド１１０２を示す。候補コンテナの１ストロークと交差するすべてのグリッドについて、塗りつぶされた島グリッドに隣接するグリッドを、有効と定義することができ、他のグリッドを、無効と定義することができる。有効なグリッドに対する無効なグリッドの比が、０．２などの経験的な値より大きい場合に、対応するストロークを、無効と定義することができる。そのような無効ストロークを、除去することができる。たとえば、図１１Ａのストローク１１０４および１１１２は、無効なストロークである。すべての無効なストロークを除去した後に、コンテナ候補は、それがまだ閉じている（すなわち、囲まれた区域を形成する）場合に有効である。コンテナがまだ閉じているかどうかを決定するために、図９でコンテナ検出に使用されたもの同一のステップを使用することができる。すなわち、コンテナ候補の空白グリッドの島を、塗りつぶすことができ、島の外の空白グリッドに達することができる場合に、そのコンテナ候補は、もはや閉じていないと決定することができる。
【００３７】
有効な閉じたコンテナが、内側のドローイング・ストロークなどの他のドローイング・ストロークが含む場合があり、あるいは、有効な閉じたコンテナが、別のコンテナ候補とドローイング・ストロークを共有する場合がある。有効なコンテナが内側のドローイング・ストロークを含む場合には、一実施形態で、内側のドローイング・ストロークを、図１１Ｂに示されたようにそのコンテナのコンテンツとして扱うことができる。イメージ・グリッド１１１４内のコンテナ１１１６は、コンテナ１１１６のコンテンツとして扱うことができる内側のドローイング・ストローク１１１８を含んでいる。コンテナ候補が、別のコンテナ候補とドローイング・ストロークを共有する場合には、一実施形態で、共有されるストロークは、分離されて、候補コンテナの１つに属すると決定することができる。たとえば、図１１Ｃは、イメージ・グリッド１１２０内のコンテナ候補１１２２および１１２４を示す、そこでは有効な境界の一部が各コンテナ候補によって共有されている。図１１Ｃには、境界の共有部分のグリッドと交差する２つのドローイング・ストロークが存在する。境界の共有部分のストロークごとに、ドローイング・ストロークの点を再サンプリングし、各候補コンテナの中央までの平均距離を計算する。そのドローイング・ストロークは、その中心への最短平均距離を有する候補コンテナに属するものとして割り当てられる。他方の候補コンテナは、ドローイング・ストロークを失った結果としてもはや閉じていない場合に、無効な候補コンテナになる場合がある。しかし、図１１Ｃに示されているように、コンテナ候補１１２２および１１２４の有効な境界の共有部分と交差する２つのドローイング・ストロークを、それぞれ、その中心からの最短平均距離を有するコンテナ候補に属するものとして割り当てることができる。各コンテナ候補に、２つのドローイング・ストロークのうちの１つがそれぞれ割り当てられるので、両方のコンテナ候補は、閉じたままであることができ、したがって、依然として有効である。
【００３８】
一実施形態で、時間順検索が、ストロークのオーバーラップを扱うのにより適する可能性があるので、空間検索の後に時間順検索を実行することもできる。一般に、連続するストロークのシーケンスから形成されるコンテナは、入力ストロークのシーケンスがコンテナを形成する尤度（likelihood）を決定することによって、時間順検索を使用して見つけることができる。この実施形態では、ｐ（ｉ、ｊ）が、ｉからｊまでの入力ストローク・シーケンス（ｉ、ｊ）がコンテナである尤度を表すとする。ｐ（ｉ、ｊ）は、次のように定義することができる。
【００３９】
【数１】
0004723840.tif 000002
【００４０】
ここで、ｖｂは、有効境界比、ｖａは、有効面積比、ｓ（ｉ、ｊ）は、ストローク数、ｗ１、ｗ２、およびｗ３は、重み、ＶＢおよびＶＡは、それぞれｖｂおよびｖａの閾値である。有効境界比は、ｖｂ＝有効境界長／総境界長と定義することができる。コンテナ候補の無効領域面積は、そのコンテナ候補に属さない内側ドローイング・ストロークと交差する領域と定義することができ、有効領域面積は、コンテナ候補内の面積から無効領域面積を除いた面積と定義することができる。有効面積比は、ｖａ＝有効領域面積／総面積と定義することができる。図１２に、内側ドローイング・オブジェクト１２０６と交差する無効領域面積を含む候補コンテナ１２０２の有効領域面積１２０４の例示的な図を示す。当業者は、有効境界長、総境界長、有効領域面積、および総面積の特性（feature）を、図９に関して前に説明した空間検索中に候補コンテナの境界を識別するのに使用されたものと同一のプロセスで、イメージ・グリッドを使用して決定できることを諒解するであろう。０．１５および０．２５などの経験的な値を、ＶＢおよびＶＡに使用することができ、経験的な値０．４、０．４、および０．２をｗ１、ｗ２、およびｗ３に使用することができる。ストローク数ｓ（ｉ、ｊ）は、ｓ（ｉ、ｊ）＝ｊ−ｉ＋１と定義することができる。ストローク数の特性は、図１３に示されているように、コンテナの近くの小さなストロークの誤ったグループ化を避けるのに使用することができる。コンテナ１３０２を形成するのに使用されるストローク数を、囲む領域１３０８について決定でき、コンテナ１３０２とコネクタ１３０４の一部を形成する領域１３０６内で見つかるストローク数から区別することができる。
【００４１】
図１４に、時間順検索を実行するために行われるステップの実施形態を全般的に示す流れ図を示す。ステップ１４０２で、有効境界比ｖｂを決定することができる。ステップ１４０４で、有効面積比ｖａを決定することができる。ステップ１４０６で、ストローク数ｓ（ｉ、ｊ）を決定することができる。ステップ１４０８で、入力ストローク・シーケンスからコンテナを決定することができる。一実施形態で、コンテナは、入力ストローク・シーケンス（ｍ、ｎ）内で、Ｐ（ｍ、ｎ）を解くことによって見つけることができる。入力ストローク・シーケンス（ｍ、ｎ）のｋ個のサブシーケンスｉ１、ｉ２、…、ｉｋへのセグメント化に対して、Ｐ（ｍ、ｎ）を、次のように定義することができる。  
Ｐ（ｍ、ｎ）＝ｍａｘ（ｐ（ｍ、ｉ１）＋ｐ（ｉ１＋１、ｉ２）＋…＋ｐ（ｉｋ＋１、ｎ））  
Ｐ（ｍ、ｎ）を計算することによって、入力ストロークを正しいコンテナにグループ化することができる。一実施形態で、動的計画法を使用して、Ｐ（ｍ、ｎ）を計算することができ、ここで、Ｐ（ｍ、ｎ）は、次のように再起的手順として表すことができる。
【００４２】
【数２】
0004723840.tif 000003
【００４３】
時間順検索を実行することによって見つかるすべての追加コンテナを、空間検索に使用されたイメージ・グリッド内でマークすることができ、その結果、見つかったすべてのコンテナが、後にコンテンツ検出およびコネクタ検出中に使用するためにイメージ・グリッドに含められることになる。
【００４４】
空間検索および時間順検索を実行してコンテナを検出した後に、コンテンツ検出を、コンテナに属する可能性がある、認識されたワードなどのすべてのコンテンツについてイメージ・グリッド内で実行することができる。たとえば、書かれたワードを、その境界ボックスとコンテナの境界グリッドとの交差面積を計算することによって、一つのコンテナに属するかどうかを検査することができる。図１５に、コンテナのコンテンツ検出を実行するために行われるステップの実施形態を全般的に示す流れ図を示す。ステップ１５０２で、イメージ・グリッド内で識別されたすべてのテキストについて、最小の囲む長方形およびその面積を決定することができる。ステップ１５０４で、最小の囲む長方形と各コンテナの交差面積を決定することができる。ステップ１５０６で、交差面積と最小の境界長方形の面積との比を計算することができる。ステップ１５０８で、最大の交差面積比を有するコンテナを、そのコンテンツが属するコンテナとして選択することができる。たとえば、図１６に、イメージ・グリッド１６０２内のワード「ｈｅｌｌｏ」を囲む境界長方形１６０６を示す。ワード「ｈｅｌｌｏ」を、コンテナ１６０４に属すると決定することができる。というのは、コンテナ１６０４との交差比が、コンテナ１６０８との交差比より大きいからである。一実施形態で、交差比が、０．５５などの経験的閾値を超えることも必要とすることができる。
【００４５】
すべてのコンテナおよびそれに関連するコンテンツをイメージ・グリッド内で検出したならば、コネクタ検出を実行することができる。図１７に、インク入力内のコネクタの検出のために行われるステップの実施形態を全般的に示す流れ図を示す。一般に、コンテナをマークされたイメージ・グリッド内で検索を実行して、すべての非コンテナ・ストロークを含む、辿っていないドローイング・ストロークのグリッドの中からすべてのコネクタを検出する。一部のユーザが、コンテナから離れている可能性がある小さいコネクタを描く傾向がある場合があるので、コンテナを膨張させることができ、その結果、これらのコネクタが、対応するコンテナに隣接するようにすることができる。図１８Ａに、コネクタ１８０６と交差する辿っていないグリッドと、コンテナのマークされた境界１８０４および１８０８との間の塗りつぶされたグリッドを有するイメージ・グリッド１８０２を示す。そのようなコネクタを検出するために、ステップ１７０２で、辿っていないドローイング・ストロークに隣接しない分離されたコンテナを、コンテナの境界を囲んでマークされたグリッドを用いて膨張させることができる。この膨張処理は、辿っていないグリッドまたは別のコンテナのいずれかに達すると、停止することができる。この形で、図１８Ｂに示されているように、コネクタを、対応する膨張したコンテナに隣接させることができる。図１８Ｂのイメージ・グリッド１８１０に示されたコンテナは、膨張したコンテナ１８１２および１８１６を生成するために、マークされたグリッドによって囲まれた境界を有している。その結果、コネクタ１８１４の辿っていないドローイング・ストロークと交差するグリッドを、膨張したコンテナのグリッドに隣接させることができる。
【００４６】
図１７のステップ１７０４で、辿っていないグリッドを塗りつぶすことができる。１つの辿っていないグリッドを、開始グリッドとして選択することができ、そのグリッドから、すべての隣接する辿っていないグリッドを塗りつぶすことができる。これらの塗りつぶされるグリッドが、膨張したコンテナを含む複数のコンテナに達する場合に、対応するドローイング・ストロークを、１つのコネクタ候補として記録する。図１９Ａのイメージ・グリッド１９０２からわかるように、膨張したコンテナ１９０４および１９０８の間のこの塗りつぶされたグリッドが、コネクタ候補１９０６を形成する。一実施形態で、イメージ・グリッド内のコンテナの境界が、コネクタを形成する、辿っていない、ドローイング・ストロークに既に隣接する場合がある。この場合に、まずコンテナを膨張させることなく、辿っていないグリッドを塗りつぶすことができる。図１９Ｂは、イメージ・グリッド１９１０にこの場合を示す、そこでは、塗りつぶされるグリッドが、膨張なしのコンテナ１９１２および１９１６の間のコネクタ候補１９１４を形成する。
【００４７】
ドローイング・ストロークの辿っていないグリッドを塗りつぶすステップが、有効なコネクタでない可能性がある候補コネクタの識別をもたらす場合がある。したがって、ステップ１７０６で、コネクタ候補を検査して、それが有効なコネクタであることを確認することができる。候補コネクタは、コンテナに接続されないドローイング・ストロークを有する場合に無効とすることができる。コンテナに接続されない候補コネクタのドローイング・ストロークがある可能性があることを検出する一実施形態では、コネクタ候補に沿ってスライディング・ウィンドウを移動して、スライディング・ウィンドウの境界とのドローイング・ストロークの交差する点の数が、その候補コネクタがつなぐ可能性がある隣接コンテナの数を超えないことを検証することができる。局所的な変化部分との誤った交差を避けるために、スライディング・ウィンドウのサイズに経験的なサイズをセットすることができる。一実施形態で、ウィンドウの半径が４ｍｍである。たとえば、候補コネクタが、Ｎ個（Ｎ≧２）のコンテナをつなぎ、Ｍが、候補コネクタのドローイング・ストロークの、スライディング・ウィンドウの境界との交差する点の数であると仮定して、スライディング・ウィンドウがコネクタ候補に沿って移動される時に、ある点でＭ＞Ｎになる場合に、そのコネクタ候補は無効とみなすことができる。たとえば、図２０Ａに、３つのコンテナ、コンテナ２００２、コンテナ２００６、およびコンテナ２００８をつなぐ候補コネクタ２０１０に沿って移動されるスライディング・ウィンドウ２００４の３つの位置を示す。図示の各位置で、交差する点の数は、候補コンテナがつなぐ可能性があるコンテナの数を超えない。交差する点の数が、つながれるコンテナの数を超えないので、このコネクタ候補は有効である。その一方で、図２０Ｂに、無効なコネクタ候補２０２０の検出を示すが、この場合に、スライディング・ウィンドウ２０１４の境界での交差する点の数が、つながれるコンテナ２０１２、２０１６、および２０１８の数より大きい。候補コネクタは、コンテナをつながないドローイング・ストロークを含む場合も無効とすることができる。たとえば、図２０Ｃに、コンテナ２０２２、２０２６、および２０２８のどれにもつながらない、スライディング・ウィンドウ２０２４内の候補コネクタ２０３０のドローイング・ストロークを示す。その結果、候補コネクタ２０３０は、無効なコネクタである。
【００４８】
コンテナおよびコネクタが検出されると、手書きオブジェクトの構造的関係を理解することができる。図２１は、ドローイング・オブジェクトの検出を実行した後の、インク入力内の手書きオブジェクトの構造的関係を全般的に表す例示的な図である。ルート２１０２は、インク入力のページなどのインク入力を表すことができ、それはドローイング・オブジェクト２１０６などの１つまたは複数のドローイング・オブジェクトを含めることができる。チャート２１０４などのドローイング・オブジェクトは、インク入力内のハンド・ドローされたオブジェクトの検出および形状認識を実行することによって、検出して認識することができる。チャート２１０４は、コネクタ２１１２によってつながれたコンテナ２１０８および２１１０によって形成することができる。コンテナ２１０８は、ストローク２１２０によって形成されるワード２１１８を有する行２１１６からなるものとすることができる段落２１１４によって構造的に表すことができるテキストなどの関連するコンテンツを含めることができる。
【００４９】
すべてのコンテナおよびコネクタを、上で説明したシステムおよび方法によって検出した後に、インク入力内のハンド・ドローされたオブジェクトを、完全に認識し、生成することができる。本発明を使用することによって、ユーザは、自由に、ハンド・ドローされた入力に対する制限なしに、図（diagrams）およびフローチャートを描くことができる。このシステムおよび方法は、すべてのインクを入力として受け入れることができるように、１つの形状が多数のストロークを有することが可能であり、ストロークの入力順序を任意とすることが可能である。さらに、そのストロークを、オーバー・トレースされたり、またはオーバーラップされたりすることも可能である。このいずれかの場合に、このシステムおよび方法は、正しい形状を自動的に検出する。
【００５０】
前述の詳細な説明からわかるように、本発明は、ハンド・ドローされたオブジェクトを検出するシステムおよび方法を提供する。有利なことに、このシステムおよび方法は、ハンド・ドローされた形状を形成する可能性があるストローク入力順序およびストローク数に敏感でない。さらに、提供されるシステムおよび方法は、柔軟であり、拡張可能である。理解されるように、本発明は、図またはチャートを含むドローイング内の閉じたコンテナおよび閉じていないコネクタのすべてを検出するのに使用することができる。検出されたならば、形状のタイプ、位置、方位、およびサイズを認識することができる。したがって、この方法およびシステムは、現代のコンピューティングに必要とされる大きな意義を有する長所および利益を提供する。
【００５１】
本発明は、さまざまな修正形態および代替構成を許すが、そのある種の例示的な実施形態を、図面に示し、上で詳細に説明した。しかし、本発明を、開示された特定の形態に制限する意図はなく、逆に、本発明が、本発明の趣旨および範囲に含まれるすべての修正形態、代替構成、および同等物を含むことを理解されたい。
【図面の簡単な説明】
【００５２】
【図１】本発明を組み込むことができるコンピュータ・システムを全般的に表す図である。
【図２】本発明の態様による、インク入力内の手描きされたオブジェクトの検出および手描きされたオブジェクトの形状認識に関するシステム・コンポーネントの例示的なアーキテクチャを全般的に示すブロック図である。
【図３】本発明の態様による、インク入力内の手描きされたオブジェクトの検出および手描きされたオブジェクトの形状認識のために行われるステップを全般的に表す流れ図である。
【図４】本発明の態様による、手描きされたオブジェクトの検出および形状認識を実行する際に使用される、インク入力内の手書きオブジェクトの構造的関係を全般的に表す例示的な図である。
【図５Ａ】本発明の態様による、手描きされたオブジェクトの検出および形状認識のためにサポートされるインク入力内のコンテナのタイプを全般的に表す例示的な図である。
【図５Ｂ】本発明の態様による、手描きされたオブジェクトの検出および形状認識のためにサポートされるインク入力内のコンテナのタイプを全般的に表す例示的な図である。
【図５Ｃ】本発明の態様による、手描きされたオブジェクトの検出および形状認識のためにサポートされるインク入力内のコンテナのタイプを全般的に表す例示的な図である。
【図６Ａ】本発明の態様による、手描きされたオブジェクトの検出および形状認識のためにサポートされるインク入力内のコネクタのタイプを全般的に表す例示的な図である。
【図６Ｂ】本発明の態様による、手描きされたオブジェクトの検出および形状認識のためにサポートされるインク入力内のコネクタのタイプを全般的に表す例示的な図である。
【図６Ｃ】本発明の態様による、手描きされたオブジェクトの検出および形状認識のためにサポートされるインク入力内のコネクタのタイプを全般的に表す例示的な図である。
【図６Ｄ】本発明の態様による、手描きされたオブジェクトの検出および形状認識のためにサポートされるインク入力内のコネクタのタイプを全般的に表す例示的な図である。
【図７】本発明の態様による、インク入力内のコンテナおよびコネクタを検出するために行われるステップの一実施形態を全般的に表す流れ図である。
【図８】本発明の態様による、インク入力内のコンテナを検出するために行われるステップの一実施形態を全般的に表す流れ図である。
【図９】本発明の態様による、コンテナを検出する空間検索の実行のために行われるステップの一実施形態を全般的に表す流れ図である。
【図１０Ａ】本発明の態様による、空間検索のさまざまなステップ中のイメージ・グリッド内のコンテナについての描写を全般的に表す例示的な図である。
【図１０Ｂ】本発明の態様による、空間検索のさまざまなステップ中のイメージ・グリッド内のコンテナについての描写を全般的に表す例示的な図である。
【図１０Ｃ】本発明の態様による、空間検索のさまざまなステップ中のイメージ・グリッド内のコンテナについての描写を全般的に表す例示的な図である。
【図１１Ａ】本発明の態様による、空間検索中のイメージ・グリッド内の検証の候補であるコンテナについての描写を全般的に示す例示的な図である。
【図１１Ｂ】本発明の態様による、空間検索中のイメージ・グリッド内の検証の候補であるコンテナについての描写を全般的に示す例示的な図である。
【図１１Ｃ】本発明の態様による、空間検索中のイメージ・グリッド内の検証の候補であるコンテナについての描写を全般的に示す例示的な図である。
【図１２】本発明の態様による、候補コンテナの有効領域面積についての描写を全般的に示す例示的な図である。
【図１３】本発明の態様による、候補コンテナの複数のストロークのグループ化についての描写を全般的に示す例示的な図である。
【図１４】本発明の態様による、時間順検索を実行するために行われるステップの実施形態を全般的に示す流れ図である。
【図１５】本発明の態様による、コンテナのコンテンツ検出を実行するために行われるステップの実施形態を全般的に示す流れ図である。
【図１６】本発明の態様による、コンテナのコンテンツの検出を全般的に表す例示的な図である。
【図１７】本発明の態様による、インク入力内のコネクタの検出のために行われるステップの実施形態を全般的に示す流れ図である。
【図１８Ａ】本発明の態様による、イメージ・グリッド内のコネクタの検出についての描写を全般的に示す例示的な図である。
【図１８Ｂ】本発明の態様による、イメージ・グリッド内のコネクタの検出についての描写を全般的に示す例示的な図である。
【図１９Ａ】本発明の態様による、イメージ・グリッド内のコネクタ候補についての描写を全般的に示す例示的な図である。
【図１９Ｂ】本発明の態様による、イメージ・グリッド内のコネクタ候補についての描写を全般的に示す例示的な図である。
【図２０Ａ】本発明の態様による、有効なコネクタ候補および無効なコネクタ候補についての描写を全般的に示す例示的な図である。
【図２０Ｂ】本発明の態様による、有効なコネクタ候補および無効なコネクタ候補についての描写を全般的に示す例示的な図である。
【図２０Ｃ】本発明の態様による、有効なコネクタ候補および無効なコネクタ候補についての描写を全般的に示す例示的な図である。
【図２１】本発明の態様による、ドローイング・オブジェクトの検出を実行した後の、インク入力内の手書きオブジェクトの構造的関係を全般的に表す例示的な図である。
【符号の説明】
【００５３】
１１０  コンピュータ
１２０  処理ユニット
１２１  システム・バス
１３０  システム・メモリ
１３１  （ＲＯＭ）
１３２  （ＲＡＭ）
１３３  ＢＩＯＳ
１３４  オペレーティング・システム
１３５  アプリケーション・プログラム
１３６  他のプログラム・モジュール
１３７  プログラム・データ
１４０  取外し不能不揮発性メモリ・インターフェース
１４１  ハードディスク・ドライブ
１４４  オペレーティング・システム
１４５  アプリケーション・プログラム
１４６  他のプログラム・モジュール
１４７  プログラム・データ
１５０  取外し可能不揮発性メモリ・インターフェース
１５１  ディスク・ドライブ
１５２  取外し可能不揮発性磁気ディスク
１５５  光ディスク・ドライブ
１５６  取外し可能不揮発性光ディスク
１６０  ユーザ入力インターフェース
１６１  マウス
１６２  キーボード
１６３  マイクロホン
１６４  タブレット
１７０  ネットワーク・インターフェース
１７１  ローカル・エリア・ネットワーク
１７２  モデム
１７３  広域ネットワーク
１８０  リモート・コンピュータ
１８１  メモリ・ストレージ・デバイス
１８５  リモート・アプリケーション・プログラム
１９０  ビデオ・インターフェース
１９１  モニタ
１９２  タッチ・スクリーン・インターフェース
１９３  出力周辺インターフェース
１９４  スピーカ
１９５  プリンタ
２０２  インク・パーサ
２０４  チャート・ディテクタ
２０６  形状リコグナイザ
２０８  コンテナ・リコグナイザ
２１０  コネクタ・リコグナイザ
２１２  コンテナ・ディテクタ
２１４  コネクタ・ディテクタ
２１６  楕円／円クラシファイヤ
２１８  ポリゴン・クラシファイヤ
２２０  三角形クラシファイヤ
２２２  四辺形クラシファイヤ
２２４  スケルトン・リコグナイザ
２２６  矢印リコグナイザ
４０２  ルート
４０４  ドローイング・オブジェクト
４０６  ドローイング・オブジェクト
４０８  段落
４１０  行
４１２  ワード
４１４  ストローク
５０２、５０４、５０６  コンテナ
６０２、６０４、６０８、６１０、６１４、６１６、６２０、６２２、６２４  コンテナ
６０６、６１２、６１８、６２６  コネクタ
１００２  イメージ・グリッド
１００４、１００８  コンテナ
１００６  コネクタ
１１００、１１１０  島
１１０４、１１１２  ストローク
１１０６  境界グリッド
１１０８  候補コンテナ
１１１０、１１１２  ストローク
１１１４、１１２０  イメージ・グリッド
１１１６  コンテナ
１１１８  ドローイング・ストローク
１１２２、１１２４  コンテナ候補
１２０２  候補コンテナ
１２０４  有効領域面積
１２０６  内側ドローイング・オブジェクト
１３０２  コンテナ
１３０４  コネクタ
１３０６  コネクタ１３０４の一部である領域
１６０２  イメージ・グリッド
１６０４、１６０８  コンテナ
１６０６  イメージ・グリッド１６０２内のワード「ｈｅｌｌｏ」を囲む境界長方形
１８０２、１８１０  イメージ・グリッド
１８０４、１８０８  コンテナのマークされた境界
１８０６  コネクタ
１８１２、１８１６  コンテナ
１８１４  コネクタ
１９０２、１９１０  イメージ・グリッド
１９０４、１９０８  膨張したコンテナ
１９０６、１９１４  コネクタ候補
１９１２、１９１６  コンテナ
１９１４  コネクタ候補
２００２、２００６、２００８  コンテナ
２００４、２０１４  スライディング・ウィンドウ
２０１０  候補コネクタ
２０１２、２０１６、２０１８  コンテナ
２０２０  無効なコネクタ候補
２０２２、２０２６、２０２８  コンテナ
２０２４  スライディング・ウィンドウ
２０３０  スライディング・ウィンドウ２０２４内の候補コネクタ
２１０２  ルート
２１０４  チャート
２１０６  ドローイング・オブジェクト
２１０８、２１１０  コンテナ
２１１２  コネクタ
２１１４  段落
２１１６  行
２１１８  ワード
２１２０  ストローク
【図１】
0004723840.tif 000004
【図２】
0004723840.tif 000005
【図３】
0004723840.tif 000006
【図４】
0004723840.tif 000007
【図５Ａ】
0004723840.tif 000008
【図５Ｂ】
0004723840.tif 000009
【図５Ｃ】
0004723840.tif 000010
【図６Ａ】
0004723840.tif 000011
【図６Ｂ】
0004723840.tif 000012
【図６Ｃ】
0004723840.tif 000013
【図６Ｄ】
0004723840.tif 000014
【図７】
0004723840.tif 000015
【図８】
0004723840.tif 000016
【図９】
0004723840.tif 000017
【図１０Ａ】
0004723840.tif 000018
【図１０Ｂ】
0004723840.tif 000019
【図１０Ｃ】
0004723840.tif 000020
【図１１Ａ】
0004723840.tif 000021
【図１１Ｂ】
0004723840.tif 000022
【図１１Ｃ】
0004723840.tif 000023
【図１２】
0004723840.tif 000024
【図１３】
0004723840.tif 000025
【図１４】
0004723840.tif 000026
【図１５】
0004723840.tif 000027
【図１６】
0004723840.tif 000028
【図１７】
0004723840.tif 000029
【図１８Ａ】
0004723840.tif 000030
【図１８Ｂ】
0004723840.tif 000031
【図１９Ａ】
0004723840.tif 000032
【図１９Ｂ】
0004723840.tif 000033
【図２０Ａ】
0004723840.tif 000034
【図２０Ｂ】
0004723840.tif 000035
【図２０Ｃ】
0004723840.tif 000036
【図２１】
0004723840.tif 000037