(57)【特許請求の範囲】
【請求項１】
コンピュータシステムに入力されたカイログラフを認識する方法において、
コンピュータ処理によって、カイログラフをコードポイントに変換するために１次認識器を利用可能にするステップと、
コンピュータ処理により、カイログラフが前記１次認識器に供給されたときに厳選されたコードポイントをもたらすカイログラフを、本訓練に基づいて自動的に区別するよう複数の２次認識器を訓練するステップであって、
複数のカイログラフと実際のコードポイントとを含む第１の訓練セットを供給するステップであって、前記実際のコードポイントは、ユーザが前記複数のカイログラフのために書くことを意図した文字を識別する正しいコードポイントを表すものである、そのようなステップと、
前記供給された第１の訓練セットに基づいて、前記複数のカイログラフの各々を前記１次認識器に供給し、最隣接（ＫＮＮ）手法による認識済みコードポイントを前記１次認識器から受け取るステップと、
前記複数のカイログラフの各々に対して受け取った前記認識済みコードポイントに基づいて、複数のセットの各々が、互いにしばしば混同されるカイログラフを示すコードポイントの混同セットを表すものとなるよう各カイログラフおよびその実際のコードポイントをグループ化するステップと、
どの２次認識器が前記１次認識器の認識精度を改善するかを判定するステップであって、
カイログラフを個別に他の訓練セットから前記１次認識器および前記２次認識器に供給するステップと、および各カイログラフ毎に、
各認識器から認識済みコードポイントを受け取るステップと、
前記１次認識器によって認識された前記コードポイントを前記カイログラフの前記実際のコードポイントと比較し、前記コードポイントが等しい場合に前記実際のコードポイントに関連する１次一致カウンタを増分するステップと、
前記２次認識器によって認識された前記コードポイントを前記カイログラフの前記実際のコードポイントと比較し、前記コードポイントが等しい場合に前記実際のコードポイントに関連する２次一致カウンタを増分するステップと、
各コードポイントに関する前記１次一致カウンタを前記２次一致カウンタと比較し、前記２次一致カウンタが前記１次一致カウンタ以下である場合にそのコードポイントに関する前記２次認識器を廃棄するステップと
により判定するステップと、
を含む前記２次認識器を訓練するステップと、
コンピュータ処理により、ユーザによる手書き文字の入力に基づき電気的に生成されたカイログラフを受け取るステップと、
コンピュータ処理により、前記カイログラフを、最隣接（ＫＮＮ）手法によってそれに対応するコードポイントを自動的に出力する前記１次認識器に供給するステップと、
コンピュータ処理により、前記１次認識器の認識精度を改善すると判定された前記２次認識器を基に、前記コードポイントが、関連する２次認識器を有する厳選されたコードポイントに対応するか否かを判定し、対応する場合に、前記カイログラフを前記２次認識器に渡し、前記２次認識器からコードポイントを返すステップと
を備えることを特徴とする方法。
【請求項２】
前記２次認識器のそれぞれがＣＡＲＴツリーであることを特徴とする請求項１に記載の方法。
【請求項３】
前記２次認識器を訓練する前記ステップは、選択されたセットとして前記グループ化のセットの１つを選択するステップと、複数の質問のうちの１つを前記選択されたセット内の前記カイログラフに適用するステップと、前記質問の結果に基づいて前記セットを２つのコードポイントサブセットに分割するステップと、前記サブセットの前記分割の品質を測定するステップと、前記複数の質問のうちのもう１つを前記選択されたセット内の前記カイログラフに適用するステップと、前記もう１つの質問の結果に基づいて前記セットを他の２つのコードポイントサブセットに分割するステップと、前記他の２つのサブセットの前記分割の品質を測定するステップと、前記分割の品質を比較してどちらの質問が最も良く前記サブセットを分割するかを判定するステップとをさらに含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記質問のそれぞれは少なくとも１つの値と組み合わされ、各質問の結果は前記値に関するカイログラフの比較に基づいて真または偽であることを特徴とする請求項３に記載の方法。
【請求項５】
前記カイログラフを含むデータに質問を適用し、前記質問に応答して値を受け取ることにより、各質問ごとに少なくとも１つの値を、コンピュータ処理により取得するステップをさらに備えることを特徴とする請求項４に記載の方法。
【請求項６】
前記分割の品質は前記サブセット内の前記コードポイントの均質性によって決定されることを特徴とする請求項３に記載の方法。
【請求項７】
前記コードポイントの前記均質性は各サブセット内のコードポイントの数量によって重み付けされることを特徴とする請求項６に記載の方法。
【請求項８】
前記分割の品質を比較してどちらの質問が最も良く前記サブセットを分割するかを判定する前記ステップは、どちらの分割が最も均質であったかを判定するステップを含むことを特徴とする請求項６に記載の方法。
【請求項９】
分割の品質に応じて構成されたＣＡＲＴツリー状に複数の質問を、コンピュータ処理により配置するステップをさらに備えることを特徴とする請求項３に記載の方法。
【請求項１０】
コンピュータ処理により、カイログラフを他の訓練セットから前記ＣＡＲＴツリーに供給するステップと、コンピュータ処理により、前記カイログラフの前記実際のコードポイントと前記質問によって決定されたコードポイントとを突き合わせる際に前記質問のどれが効果的ではないかを監視するステップと、コンピュータ処理により、効果的ではない質問を前記ＣＡＲＴツリーから除去するステップとをさらに備えることを特徴とする請求項９に記載の方法。
【請求項１１】
コンピュータシステムに入力されたカイログラフを認識するメカニズムにおいて、
カイログラフをコードポイントに変換するための１次認識器と、
カイログラフが前記１次認識器に供給されたときに指定されたコードポイントをもたらすカイログラフを、本訓練に基づいて自動的に区別するよう複数の２次認識器を訓練する手段であって、
複数のカイログラフと実際のコードポイントとを含む第１の訓練セットを供給する手段であって、前記実際のコードポイントは、ユーザが前記複数のカイログラフのために書くことを意図した文字を識別する正しいコードポイントを表すものである、そのような手段と、
前記供給された第１の訓練セットに基づいて、前記複数のカイログラフの各々を前記１次認識器に供給し、最隣接（ＫＮＮ）手法による認識済みコードポイントを前記１次認識器から受け取る手段と、
前記複数のカイログラフの各々に対して受け取った前記認識済みコードポイントに基づいて、複数のセットの各々が、互いにしばしば混同されるカイログラフを示すコードポイントの混同セットを表すものとなるよう各カイログラフおよびその実際のコードポイントをグループ化する手段と、
どの２次認識器が前記１次認識器の認識精度を改善するかを判定する手段であって、
カイログラフを個別に他の訓練セットから前記１次認識器および前記２次認識器に供給する手段と、および各カイログラフ毎に、
各認識器から認識済みコードポイントを受け取る手段と、
前記１次認識器によって認識された前記コードポイントを前記カイログラフの前記実際のコードポイントと比較し、前記コードポイントが等しい場合に前記実際のコードポイントに関連する１次一致カウンタを増分する手段と、
前記２次認識器によって認識された前記コードポイントを前記カイログラフの前記実際のコードポイントと比較し、前記コードポイントが等しい場合に前記実際のコードポイントに関連する２次一致カウンタを増分する手段と、
各コードポイントに関する前記１次一致カウンタを前記２次一致カウンタと比較し、前記２次一致カウンタが前記１次一致カウンタ以下である場合にそのコードポイントに関する前記２次認識器を廃棄する手段と
により判定する手段と、
を含む前記２次認識器を訓練する手段と、
ユーザによる手書き文字の入力に基づき電気的に生成されたカイログラフを受け取る手段と、
前記カイログラフを、最隣接（ＫＮＮ）手法によってそれに対応するコードポイントを自動的に出力する前記１次認識器に供給する手段と、
前記１次認識器の認識精度を改善すると判定された前記２次認識器を基に、前記コードポイントが、関連する２次認識器を有する指定されたコードポイントに対応するか否かを判定する手段と、
前記１次認識器から受け取ったコードポイントがそれに関連する２次認識器を有していないことを前記判定手段が示すときに前記１次認識器から受け取った前記コードポイントを返す手段と、
前記１次認識器から受け取ったコードポイントがそれに関連する２次認識器を有することを前記判定手段が示すときに前記２次認識器の１つから受け取ったコードポイントを返す手段であって、前記カイログラフを前記関連する２次認識器に渡す手段と前記関連する２次認識器からコードポイントを受け取る手段とを含む手段と
を備えたことを特徴とするメカニズム。
【請求項１２】
コンピュータシステムに入力されたカイログラフを認識する方法において、
コンピュータ処理によって、カイログラフを形状インデックスに変換するために１次認識器を利用可能にするステップと、
コンピュータ処理により、カイログラフが前記１次認識器に供給されたときに厳選された形状インデックスをもたらすカイログラフを、本訓練に基づいて自動的に区別しコードポイントに変換するよう複数の２次認識器を訓練するステップであって、
複数のカイログラフと実際のコードポイントとを含む第１の訓練セットを供給するステップであって、前記実際のコードポイントは、ユーザが前記複数のカイログラフのために書くことを意図した文字を識別する正しいコードポイントを表すものである、そのようなステップと、
前記供給された第１の訓練セットに基づいて、前記複数のカイログラフの各々を前記１次認識器に供給し、最隣接（ＫＮＮ）手法による認識済み形状インデックスを前記１次認識器から受け取るステップと、
前記複数のカイログラフの各々に対して受け取った前記認識済み形状インデックスに基づいて、複数のセットの各々が、互いにしばしば混同されるカイログラフを示すコードポイントの混同セットを表すものとなるよう各カイログラフおよびその実際のコードポイントをグループ化するステップと、
どの２次認識器が前記１次認識器の認識精度を改善するかを判定するステップであって、
カイログラフを個別に他の訓練セットから前記１次認識器および前記２次認識器に供給するステップと、および各カイログラフ毎に、
各認識器から認識済み形状インデックスまたはコードポイントを受け取るステップと、
前記１次認識器によって認識された前記形状インデックスに対応するコードポイントを前記カイログラフの前記実際のコードポイントと比較し、前記コードポイントが等しい場合に前記実際のコードポイントに関連する１次一致カウンタを増分するステップと、
前記２次認識器によって認識された前記コードポイントを前記カイログラフの前記実際のコードポイントと比較し、前記コードポイントが等しい場合に前記実際のコードポイントに関連する２次一致カウンタを増分するステップと、
各コードポイントに関する前記１次一致カウンタを前記２次一致カウンタと比較し、前記２次一致カウンタが前記１次一致カウンタ以下である場合にそのコードポイントに関する前記２次認識器を廃棄するステップと
により判定するステップと、
を含む前記２次認識器を訓練するステップと、
コンピュータ処理により、ユーザによる手書き文字の入力に基づき電気的に生成されたカイログラフを受け取るステップと、
コンピュータ処理により、前記カイログラフを、最隣接（ＫＮＮ）手法によってそれに対応する形状インデックスを自動的に出力するところの前記１次認識器に供給するステップと、
コンピュータ処理により、前記１次認識器の認識精度を改善すると判定された前記２次認識器を基に、前記２次認識器のどれが前記形状インデックスに関連するかを判定するステップと、
コンピュータ処理により、前記形状インデックスに対応する前記２次認識器に前記形状インデックスおよび前記カイログラフを渡し、前記２次認識器からコードポイントを返すステップと
を備えることを特徴とする方法。
【発明の詳細な説明】
発明の分野
本発明は、一般にコンピュータシステムへのユーザ情報の入力に関し、より詳細にはユーザによって入力された手書き文字の認識に関する。
発明の背景
手書き認識技術の最大の問題の１つは、エラー率を低減することである。カイログラフ（chirograph）と呼ばれる手書き文字をユーザが電子的に入力したときに頻繁に発生するタイプのエラー結果として、それは、コンピュータがカイログラフ、すなわち、１組の可能なコードポイント（code points）と突き合わせ（match）ようと試みる１セットに含まれる２つまたはそれ以上の可能な文字と厳密に突き合わせる。大多数のエラーの原因となる文字は、通常、人間であれば区別できるが現在の認識器では認識できないような単一の違いを除き、相互に等しいものである。たとえば、所与の日本語の記号は、単一の微妙な違いを除けば、相互にほぼ等しいものである。
問題は、ほとんどの手書き認識システムがニューラルネット、隠れマルコフモデル（ＨＭＭ）、またはＫ最隣接（K-Nearest-Neighbor）（ＫＮＮ）手法に基づく認識器を使用しているために発生する。このようなシステムは、それぞれの全体的な外観に基づいて文字を分類する作業では適度に十分な機能を果たすが、２つの文字が単一の違いを除いて等しい場合、しばしば失敗に終わる。特に厄介な対同士を区別するように認識器を手作業でコーディングしようという試みが行われてきたが、容易に相互に混同される文字セットは多数存在する。このため、コーディングプロセスは非常に大きな労働力を要し、単調で退屈なものになる。さらに、コーディングの結果は、文字同士を区別するために何をテストすべきかに関する個人の１つまたは複数の最良推測によって決まる。これは、必ずしも非常に最適なものになるわけではない。というのは、２つ（またはそれ以上）の近い文字を最もよく区別するものに関する可能性が数多く存在するからである。実際に、このようなシステムのうちの最良のものは、実質的にエラー率を低減するわけではない。最後に、認識器が変更されるたびに、認識器が混同する文字セットも変化し、大きな労働力を要するコーディングプロセスの多くを繰り返さなければならない。
もう１つのタイプの認識システムは、判断ツリー、特に分類回帰ツリー（ＣＡＲＴ）に基づくものであり、手書き認識のために試みられてきた。このようなタイプのシステムは、多数の文字から信頼できる判断を行うことができないので、拒否されている。一例として、日本語の文字セットを使用するシステムの場合、６６５０通りの文字がサポートされている。お分かりのように、６５５０通りの文字のいずれかを受け取り、その文字を繰り返しテストし、単一の正しい結果が見つかるまで適切な分岐を正しく降りていくことができるバイナリツリーの開発は、極めて難しく、大規模な企てになるだろう。
発明の目的および概要
したがって、本発明の一般的な目的は、手書き認識のエラー率を低減するために改良された方法およびメカニズムを提供することにある。
その目的を達成する際の関連目的は、通常は混同される文字同士を高し成功率で区別する方法およびメカニズムを提供することにある。
他の目的は、サンプルデータを使用して自動的に訓練することができる上記の種類の方法およびシステムを提供することにある。
さらに他の目的は、高速で信頼でき、費用対効果が高く、フレキシブルで拡張性のある上記の種類の方法およびメカニズムを提供することにある。
簡単に言うと、本発明は、コンピュータシステムに入力されたカイログラフを認識するための方法およびメカニズムを提供するものである。１次認識器はカイログラフをコードポイントに変換するために設けられ、２次認識器（たとえば、ＣＡＲＴツリー）は、選択されたコードポイントを生成するカイログラフを区別するように開発され訓練される。このような各２次認識器は選択された各コードポイントに関連付けられている。カイログラフを受け取ると、そのカイログラフは１次認識器に供給され、それにより、それに対応するコードポイントが受け取られる。このコードポイントが、それに関連する２次認識器を有する、選択されたコードポイントの１つに対応するかどうかの判定が行われる。対応しない場合は、１次認識器によって供給されるコードポイントが返される。対応する場合は、カイログラフが２次認識器に伝達され、２次認識器からコードポイントが返される。
他の目的および利点は、添付図面に関連して以下に示す詳細な説明から明らかになるだろう。
【図面の簡単な説明】
図１は、本発明を取り入れることができるコンピュータシステムを表すブロック図である。
図２は、本発明の一態様による１次手書き認識器を訓練するための機能構成要素を表すブロック図である。
図３は、本発明による２次認識システムを開発するために１次認識器によって認識されるカイログラフをコードポイントベースのファイルにソートするための機能構成要素を表すブロック図である。
図４は、図３の１次認識器によってソートされたファイル例の内容を表している。
図５は、カイログラフをソートするために行われる一般的なステップを表す流れ図である。
図６は、図３のファイルから２次認識システムを生成するための機能構成要素を表すブロック図である。
図７〜図９は、２次認識システムを構築し訓練するために行われる一般的なステップを表す流れ図を含む。
図１０は、本発明の認識メカニズムを最適化するための機能構成要素を表すブロック図である。
図１１〜図１３は、本発明の認識メカニズムを最適化するために行われる一般的なステップを表す流れ図を含む。
図１４は、本発明の認識メカニズムを使用してカイログラフを認識するための機能構成要素を表すブロック図である。
図１５は、本発明の認識メカニズムを使用してカイログラフを認識する場合に行われる一般的なステップを表す流れ図である。
好ましい実施例の詳細な説明
添付図面について検討し、まず図１を参照すると、本発明を取り入れることができ、全体が２０で示されているコンピュータシステムが示されている。コンピュータシステム２０は記憶装置２４に機能的に接続されたプロセッサ２２を含み、この記憶装置はランダムアクセスメモリ（ＲＡＭ）２６と、ハードディスクドライブ、光ドライブなどの不揮発性記憶装置２８とを含む。お分かりのように、不揮発性記憶装置は、ＲＡＭとともに使用すると、周知のスワッピング技法により比較的大量の仮想メモリを提供することができる。
また、プロセッサ２２は、入出力回路３２により、キーボードおよびマウスなどのポインティングデバイス、ペンタブレット、タッチデバイス、電子インクを取得する他の手段などの１つまたは複数の入力装置３０にも接続している。システム２０は、グラフィカルユーザインタフェースなどによりシステム２０のユーザに情報を伝達するために入出力回路３２に接続された少なくとも１つのローカル出力装置３４も含む。オペレーティングシステムは記憶装置２４内にロードされる。
本発明の一態様によれば、以下に詳述するように、認識器をしばしば混乱させるようなカイログラフが２次認識プロセスに供給される。このため、各入力カイログラフごとに従来の（１次）認識器がコードポイントを出力する。しかし、コードポイントを直接返すのではなく、コードポイントはまず、それが混同セット、すなわち、しばしば相互に混同されるカイログラフを示す２つ（またはそれ以上）のコードポイントのうちの１つに対応するかどうかを判定するために検査される。返されるコードポイント混同セットに属さない場合、本来は１次認識器から返されるコードポイントがこのメカニズムによって返される。しかし、コードポイントが混同セットを示す場合、特にその特定の混同セットを区別するように開発された２次認識器にカイログラフが与えられる。２次認識器は、１次認識器が行う場合より統制されたテストを使用してカイログラフを分析し、テストの結果に基づいて２つ（またはそれ以上）のコードポイントのうちの１つを返す。ただし、このようにしばしば混同されるカイログラフは２つずつのセットに限定されるわけではなく、２つまたはそれ以上の他のカイログラフとたびたび混同されることに留意されたい。
代替実施例では、似ているように見える複数のコードポイント（またはコードポイントのサブセット）を表す形状クラス（shape classes）を認識するよう、１次認識器を訓練することができる。したがって、カイログラフが供給されると、１次認識器は少なくとも１つの形状クラスインデックスを返す。次に２次認識器は、カイログラフがどのコードポイントを表すかを形状クラスインデックスから決定する。ただし、形状クラスインデックスはより一般的な概念であり、すなわち、コードポイントは特定のタイプの形状クラスインデックスであることに留意されたい。しかし、単純にするため、特に明記されている場合を除き、コードポイントを返す１次認識器に関して本発明を説明する。
したがって、本発明の明瞭な態様が２通り存在することに留意されたい。第１の態様は、複数（好ましくは数千などの多数）のユーザから取られた手書きサンプルデータを使用して、本発明の改良された認識メカニズムを開発することを含む。第２の態様は、カイログラフをコードポイントに変換するために、本発明の第１の態様により開発された認識メカニズムを使用することを含む。第１の態様である認識メカニズムの開発は、通常、比較的ハイパワーのコンピュータシステム上の開発環境で行われ、そのシステムはネットワーク接続などによりサンプルデータの大規模データベースに接続することができる。第２の態様である認識メカニズムの使用は、通常、ハンドヘルド（パームトップ）計算装置などで行われる。このような装置は、好ましくは、記憶装置２４にロードされたWindows CEオペレーティングシステムの下で動作し、手書き文字（カイログラフ）を入力するためにタッチセンシティブ液晶表示画面を含む。他の好ましいシステムとしては、Windows 95またはWindows NTオペレーティングシステムの下で動作するタブレットベースのデスクトップパーソナルコンピュータを含む。
次に、図２〜図４をまず参照して認識メカニズムの開発について検討すると、構築／訓練プロセス４２ではサンプル文字からなる第１の訓練セット４０を使用して、１次認識器４４（図３）を開発し訓練する。訓練セットは、それぞれの実際の正しいコードポイント、すなわち、ユーザが書き込む予定であった文字を識別するコードポイントとともに格納されたカイログラフを含むファイルである。１次認識器４４は、好ましくは、最隣接（ＫＮＮ）手法を使用するものである。このような認識器とその構築および訓練は既知のものであり、したがって、以下に詳述しないが、認識器４４がカイログラフを訓練済み認識器データ４６（終点情報など）と突き合わせ、コードポイントを出力することに留意されたい。また、認識器４４は実際には、それに入力されたカイログラフに応答して代替コードポイントの（確率でランク付けした）リストを返すことができるが、単純にするため、特に明記されていない限り、返された単一のコードポイントに関連して本発明を説明することにも留意されたい。ただし、１次認識器は、１次認識器を訓練するために形状コードを使用する、任意のタイプの形状インデックスを返すタイプにすることができることにも留意されたい。当業者であれば分かるように、この技法は、別個の提案を返す認識器またはパターン突合せ技法の場合に同様に機能するだろう。
本発明の一態様により、また図３以降に示すように、１次認識器４４を使用して、上記の２次認識メカニズムの構築を開始する。一般に、ソートプロセス４７は、そのカイログラフに関して１次認識器４４が返すコードポイント（または他の形状インデックス）に応じてカイログラフをソートし、それにより、それぞれの実際のコードポイントに関してカイログラフがソートされる方法によって、１次認識器４４が混同しがちなカイログラフが最終的に明らかになる。このため、１次認識器４４が構築されると（図２）、それぞれがその実際のコードポイントとともに格納されるサンプルカイログラフを含む第２の訓練セット４８が１次認識器４４に供給される。その訓練済み認識器データ４６を使用して、１次認識器４４はソートプロセス４７にコードポイントを返し、そのプロセスはカイログラフと実際のコードポイントを様々なファイル５０1〜５０nにソートする。ただし、他のタイプの形状インデックスを使用している場合、カイログラフは、１次認識器４４が返す形状インデックスに基づいて、各形状インデックスごとに同様にファイルにソートされる。
より具体的には、図５に示すように、ステップ５００でソートプロセス４７は、まず、認識メカニズムによってサポートすべき各コードポイントごとに個別のファイルを作成する。第２の訓練セット４８内の第１のカイログラフがステップ５０２で選択され、ステップ５０４で１次認識器４４に送られる。ステップ５０６では、コードポイント（実際には間違っている可能性のあるもの）が１次認識器４４からソートプロセス４７に返され、ステップ５０８で、訓練セット４８から分かった実際のコードポイントとともに、返されたコードポイントに関連するファイルに書き込まれる。たとえば、「Ａ」を識別するコードポイントが返された場合、ソートプロセス４７は、その実際のコードポイント（「Ａ」ではない可能性があるもの）とともに、「Ａ」という応答を誘発したカイログラフを「Ａ」ファイル５０2に書き込む。図５から明らかなように、訓練セット４８内のすべてのカイログラフがこのようにソートされるまで、ステップ５１０〜５１２は後続のカイログラフによりソートプロセス４７を繰り返す。ただし、このプロセスは、コードポイント以外の形状インデックスについても同じであることに留意されたい。
一例として、図４は、このようなファイル５０Xの内容を示し、その中の２つの混同カイログラフは互いに異なる実際のコードポイントＮXおよびＮYを有する。ソートプロセス中の任意の時点で、明瞭な各カイログラフ（コードポイントＮXまたはＮY）は、そのコードポイントとしてＮXを有するものとして、１次認識器４４によってすでに認識されている。したがって、ソートプロセス４７は、各カイログラフとその実際のコードポイントとをＮXファイル５０Xに書き込んだ。ただし、１次認識器４４が一切間違っていない場合、すべてのファイルは、そのファイルを識別するコードポイントと一致した対（カイログラフ、実際のコードポイント）のみを含むことになるだろう。しかし、いかなる１次認識器も、適当な大きさの訓練セットを備えている場合にこのような精度を有していないことがこれまでに判明している。
第２の訓練セット４８がファイル５０1〜５０nにソートされると、２次認識器開発／訓練プロセスがファイル５０1〜５０nを使用して２次認識器を開発する。
図６に示すように、分類回帰ツリー（ＣＡＲＴ、またはＣＡＲＴツリー）は２次認識器として使用する。ＣＡＲＴツリーは、参照によりその全体が本明細書に組み込まれる、Classification and Regression Treesというタイトルのテキスト（Breiman,Friedman,Olshen and Stone,Chapman and Hall,1984年）に記載されたバイナリ判断ツリーである。プロセスのこの時点では、サポートされる各コードポイント（または形状インデックス）ごとに、セット５４1〜５４n内の１つのＣＡＲＴツリーが開発され訓練される。
図７〜図９は、一般に各ＣＡＲＴツリーを開発する方法を記述するものである。まず、混同対を区別する際に関連すると思われる質問のリストをアセンブルする。このような質問は、「カイログラフ内の総ストローク数はいくつか」、「第１のストロークの長さはどのくらいか」、「第１のストロークに対する第３のストロークの角度はどのくらいか」など、手書きストロークに基づく場合が多い。この時点では、標準的な質問セットは一切存在しないが、質問は当業者の経験および観察のみに基づくものである。ただし、システムにとって既知のカイログラフ内のストロークカウントに応じて質問を調整することができることに留意されたい。これで明らかになるように、質問の順序は重要ではない。さらに、１次認識器は、インクのそれ自体の特徴付けに加え、構築プロセスが影響力を及ぼす可能性のある何らかの特徴付け情報をすでに供給している可能性がある。
一般に、ＣＡＲＴ構築プロセス５２は、所与のファイルについてどの質問が１次認識器の混同を最も良く解決するかを判定しランク付けするために、すべての質問をすべてのサンプル（各ファイル５０1〜５０n内のもの）に適用する。しかし、ＣＡＲＴを構築する前に、ステップ７００でサンプルデータを走査し、所与のファイル内の実際のコードポイントのすべてが同じである（そのファイルと一致する）かどうかを判定することにより、予備テストを行う。そうである場合、サンプル内のデータは純粋なものであり、それにより、２次認識が認識全体を改善することはないだろう。したがって、ＣＡＲＴ構築プロセス５２は、このようなサンプルファイルについては終了する。
しかし、多数のサンプルデータがファイル内に存在する、より典型的なケースでは、カイログラフの少なくとも一部は、１次認識器によって決定されたコードポイント（ならびに、その結果の対応するファイル）と直接一致しない実際のコードポイントを有することになる。したがって、ＣＡＲＴを構築するため、図７のステップ７０１ではリスト内の第１の質問を取得し、ステップ７０２で（ファイルの１つ、たとえば、５０1から）第１のサンプルカイログラフを取得し、ステップ７０４でこのサンプルに質問を適用し、結果を得る。たとえば、この質問では、第１のストロークの水平長に関して尋ね、その結果、第１のサンプル用として９という値（最高ｘ座標から最低ｘ座標を引くと９になる）が得られる可能性がある。
結果の値は、ステップ７０６でそのサンプルに関する実際のコードポイントとともに、たとえば、（値、実際のコードポイント）として保管され、ステップ７０８〜７１０では、選択されたファイル５０1内の次のサンプルについてプロセスを繰り返す。この間、ステップ７０６は、この第１の質問に関してこの次のサンプルからどのような結果が得られても、その結果（値、実際のコードポイント）をもう一度保管する。最終的に、ステップ７０８〜７１０により、第１の質問に対してファイル内のすべてのサンプルをテストし、それにより、結果の値とそれに関連するコードポイントのすべてが、この質問に関してＣＡＲＴツリーを開発中の所与のファイル内で既知のものになる。
この時点で、図８の諸ステップを実行し、一般に、いずれの値がそれに関連する実際のコードポイントの線に沿ってファイル内のカイログラフを分割する（分ける）かを見つけだす。ただし、一般に非実用的であるが、最良分割を決定するために力ずくの手法で各質問によって考えられるすべての値をテストすることは可能であることに留意されたい。たとえば、長さの質問に関して１から１０００のすべての長さをテストし、他の質問に関して他のより広い範囲の値についてテストすることができる。しかし、図７の諸ステップによって得られる実際の結果のみをこのために使用し、図８の分割テストプロセスをかなり加速する。さらに、分割を決定するために各サンプルに対してバイナリ質問として固有の各結果を適用することができるが、より最適な方法は、既存の結果データを使用して最良分割を決定することである。
より具体的には、ステップ７２０は、（図７で）所与の質問について得られた結果を（値、実際のコードポイント）の順序付けられた範囲にソートする。したがって、長さの例の場合、最短長は４０であり、最長長は１００であった可能性がある。分割の品質をテストするため、ステップ７２２で「４０という値」を有するコードポイントのそれぞれは１つの（たとえば、左の）サブセット内に移動され、他の値を有するすべてのコードポイントはもう１つのもの（たとえば、右のサブセット）の内に置かれる（またはそのまま残される）。コードポイントの移動は増分方式で行われる。次に、「４０」という値のすべてが移動されると、ステップ７２４で分割の品質を後述するように測定する。お分かりのように、ＣＡＲＴツリーはバイナリであり、したがって、この移動では、ファイル５０1内のすべてのサンプルに対して、「第１のストロークの水平長が４０以下であるか」すなわち「Ｘmaxｓ１−Ｘminｓ１＜＝４０であるか」という質問を効果的に行った。各カイログラフはこの質問に応じて効果的にソートされ、ｙｅｓという応答用のコードポイントは１つの（左の分岐）セット内に置かれ、ｎｏという応答用のコードポイントはもう１つの（右の分岐）セット内におかれる。
本発明により、ステップ７２４では、何らかの分割基準に応じて分割の品質を評価する。分割の品質を決定するための好ましい方法は、ジーニ（Gini）ダイバーシチインデックスを使用してセットの均質性（homogeneity）をテストすることである。一般に、ジーニダイバーシチインデックスは、左のセットと右のセットのそれぞれに含まれるコードポイントの数量を使用して、均質性（ｈ）に関する平方和方法を使用する。すなわち、
ｈLeft＝［ｃｐ1Left／（ｃｐ1Left＋ｃｐ2Left＋．．．ｃｐnLeft）］2＋［ｃｐ2Left／（ｃｐ1Left＋ｃｐ2Left＋．．．ｃｐnLeft）］2＋．．．［ｃｐnLeft／（ｃｐ1Left＋ｃｐ2Left＋．．．ｃｐnLeft）］2
および
ｈRight＝［ｃｐ1Right／（ｃｐ1Right＋ｃｐ2Right＋．．．ｃｐnRight）］2＋［ｃｐ2Right／（ｃｐ1Right＋ｃｐ2Right＋．．．ｃｐnRight）］2＋．．．［ｃｐnRight／（ｃｐ1Right＋ｃｐ2Right＋．．．ｃｐnRight）］2
であり、式中、LeftおよびRightという下付き文字は左および右のセットを示し、ｃｐ1、ｃｐ2．．．ｃｐnは各セット内の各コードポイント値のコードポイントの数を表す。次に、各セット内のコードポイントの数によって均質性の結果に重みを付け、この質問（Ｑ１）と値（Ｖ１）に関する最終的な均質性の等式は以下のようになる。
Ｈ（Ｑ１，Ｖ１）＝［（ｈLeft）（ｃｐ1Left＋ｃｐ2Left）＋（ｈRight）（ｃｐ1Right＋ｃｐ2Right）］／（ｃｐ1Left＋ｃｐ2Left＋ｃｐ1Right＋ｃｐ2Right）
ステップ７２６は前の結果がある場合にそれと照らし合わせて分割の品質をテストし、より良くなっている場合、ステップ７２７は最良品質分割として均質性結果Ｈ（Ｑ１、Ｖ１）を保管する。ただし、ステップ７２７は、おそらく現在の質問を含む、これまでのすべての質問における最良分割を保管し、それにより、ステップ７２６はそれぞれの後続分割を前に決定した最良のもの（質問、値）からの結果と比較することに留意されたい。
ステップ７２８〜７３０では、次の値に関する分割がテストされ、もう一度比較されるが、この場合はその範囲内の次の値、たとえば、４１を使用する。ステップ７２２でこの値に対応するコードポイントを増分方式で左の分割サブセットに移動することにより、４１以下の値を有するものである左のサブセット内のコードポイントによってサンプルを効果的に分割する。ただし、前に左のサブセットに移動させた４０に関連するコードポイントも４１未満であるので、このようなコードポイントはそこに存在することに留意されたい。次に、ステップ７２４で次の均質性Ｈ（Ｑ１、Ｖ２）を計算し、ステップ７２６でこれを比較し（これまで最良であった４０に関する値と照らし合わせる）、改良されていれば、ステップ７２７でそれに対応する質問の識別子とともに、最良値として保管する。
ステップ７２８で判定したように、すべての値をこのようにしてテストしたら、この第１の質問に関する最良値（すなわち、最も均質な分割をもたらす値）が決定されている。その後、次の質問を選択し（ステップ７３２〜７３４）、この次の質問を使用してファイル内のサンプルについてプロセスを繰り返す。全体的な最良の単一（質問、値）対が分かるまで、他の質問と値の分割との比較のために、最良の（質問、値）対を保管し続けることになる。
最終的に、すべての質問に関するすべての値を使用してサンプルを分割し、その均質性を計算し、最良の（質問、値）対が保管されていることになる。この時点で図９の諸ステップを実行し、それに応じてコードポイントの最良の（最も均質の）分割を生み出す最良の順序で最良の質問を適切に行うＣＡＲＴツリーを確立する。したがって、重要なことに、このプロセスは自動的に（使用可能な）最良の質問／値対を様々なレベルに配置する。その結果、このプロセスは、使用可能な最良質問が、本来はそれほど重要であると人間によって考えられていないが、にもかかわらず提示されたものになると判断する場合が多い。ただし、これは必ずしもサンプルセットを均質に分割するための理想的な質問と値の組合せではなく、使用可能な中で最良の質問と値に過ぎないことに留意されたい。
いずれにしても、最良の質問と値が分かると、次にステップ７４２でこの最良の質問／値対を使用して、サンプルセット（ファイル５０1）を２つのサブセットに分割する。次に、ステップ７４４に表すように、この２つのサブセットのそれぞれについてプロセスを反復して繰り返し、それぞれのサブセットを最も均質に分割するための次に最良の質問と値の対を見つける。このプロセスを再帰的に繰り返し（すなわち、プロセスは、２つのサブセットのそれぞれを最適に分割するために図７のステップ７００に戻る）、均質性がもはや改善されない点に達するまで、より均質なサブセットへと分岐する。理解できるように、より低いレベルでの再帰的操作は、各分岐およびレベルでの最良の質問／値対を確立し、混同対の区別をさらに洗練する。ステップ７４６では、様々なレベルのこのような質問と値の対からＣＡＲＴツリーを構築する。
しかし、主に使用可能なサンプルデータが限定されているので、ＣＡＲＴツリーは、特により低いレベルでは不完全なものになりがちである。さらに、ＣＡＲＴツリーは大きくなり、一般にハンドヘルド計算装置では得られないほどの大量の記憶域を必要とする可能性がある。したがって、ステップ７４８では新しいサンプルのセットをそのＣＡＲＴに適用し、その埋込み質問のいずれが正しい判断を行っているかをテストする。混同対を解決する際に効果的ではないと判定された質問はステップ７５０でツリーから除去される（取り除かれる）。これにより、認識精度に悪影響を及ぼさないが、サイズの点でより管理しやすいＣＡＲＴが残ることになる。
すべてのファイル５０1〜５０nが上記の方法でそのために開発されたＣＡＲＴツリーを備えると、システムによってサポートされる各コードポイントごとに１つずつのＣＡＲＴツリーが存在する。しかし、このようなＣＡＲＴツリーの一部は可能な出力を１つだけ有し、その出力は１次認識器によって出力されたものと同じコードポイントになる可能性がある。このようなＣＡＲＴツリーは認識を改善せず、したがって、廃棄される。
同様に、（１次認識器がコードポイントを返すものである場合）特定のＣＡＲＴツリーが１次認識器の認識精度を改善するという保証は一切ない。これは、より少ない量のデータでＣＡＲＴツリーを開発する場合に特に該当する。というのは、一般に、訓練データが多くなればなるほど、ＣＡＲＴツリーはより上手に混同を解決するからである。特定のＣＡＲＴツリーが何らかの限界量だけ（非常にわずかな改善である可能性があるもの）認識を改善しない場合、ＣＡＲＴツリーは記憶空間を要するので、それを保持する根拠は何もない。同様に、ＣＡＲＴツリーが極めて高速であっても、ＣＡＲＴツリーを使用する２次認識は総認識時間を増大し、やはりコストを増加する。
したがって、図１０および図１１〜図１３は、不要なＣＡＲＴツリーを廃棄することにより認識メカニズムを最適化するための１つのプロセスを表している。まず、ステップ９００で第３の訓練セット５６（図１０）からの第１のカイログラフを選択する。ステップ９０２でそのカイログラフを１次認識器４４に送る。ステップ９０４では、１次認識器４４から返されたコードポイントが実際の正しいコードポイントと同じである場合、ステップ９０６でそのＣＡＲＴツリー（すなわち、このファイル）に関する１次認識器一致カウント６２を増分する。
次に、ステップ９０８で、１次認識器４４から返されたコードポイントに対応する適切なＣＡＲＴツリーを選択する。ステップ９２０では、同じカイログラフを今度はＣＡＲＴツリーに供給し、それにより、ＣＡＲＴツリーによって判断を行い、それに関するコードポイントを返す。ステップ９２２では、ＣＡＲＴツリー５２から返されたコードポイントが実際の正しいコードポイントと同じである場合、ステップ９２４でこのＣＡＲＴツリーに関するＣＡＲＴ一致カウント６６を増分する。第３の訓練セット５６内のすべてのカイログラフをテストするまで、ステップ９２６〜９２８はプロセスを繰り返す。
最後に、図１３では、各ＣＡＲＴツリーごとに１次一致カウントとＣＡＲＴ一致カウントを比較し、そのＣＡＲＴツリーが認識を改善したかどうかを判定する。より具体的には、ステップ９４０で第１のサポートコードポイント（それぞれについてファイルが１つずつ存在する）を選択し、このＣＡＲＴツリーに関するＣＡＲＴ一致カウント６６を１次認識器一致カウント６２と比較する。ＣＡＲＴ一致カウントが１次一致カウント以下である場合、そのＣＡＲＴツリーは認識メカニズムを改善していないので、ステップ９４４でこれを廃棄する。そうではない場合、このコードポイントに関するＣＡＲＴツリーを保持する。すべてのサポートコードポイントをテストするまで、ステップ９４６〜９４８は比較を繰り返す。ただし、必要であれば、何らかの限界量だけ認識プロセスを改善しないＣＡＲＴツリーを廃棄するように、ステップ９４２をより複雑なテストにすることができることに留意されたい。たとえば、１次一致カウントに対するＣＡＲＴ一致カウントの割合が１に何らかの分数量を加えたものを超えない場合、そのＣＡＲＴツリーを廃棄することができる。しかし、上記の最適化の場合、ＣＡＲＴツリー（数百個になる可能性がある）は１メガバイトの１次認識器に約１８キロバイトを追加するだけであり、認識をめったに改善しないＣＡＲＴツリーを廃棄した結果得られるメモリの節約はおそらく認識精度の低減に値しないことに留意されたい。
実際に、本発明の１次および２次結合認識メカニズムは完全にテストされており、所与の混同対の場合、９９．７％の精度率を有する。０．３％のエラー率は、人間ですら見分けられないほど下手に書かれた文字の結果であると考えられ、実際に人間の認識エラー率に匹敵する。ただし、本発明は非常にフレキシブルであり、拡張性が高いことに留意されたい。たとえば、１次認識器が変化し、それにより、混同対を変更する場合、上記のように新しいＣＡＲＴツリーを自動的に生成し、テストすることができる。同様に、追加の質問を思いついた場合、その質問を他のものと照らし合わせて試みるだけで、それらが所与の分割の均質性、ならびにその結果、メカニズムの精度を改善するかどうかを判定することができる。
ただし、コードポイント以外の何かである形状インデックスを返す１次認識器の場合、形状インデックスをコードポイントにマッピングするための少なくとも最小限のＣＡＲＴツリーが必要であることに留意されたい。しかし、これによってＣＡＲＴ記憶域の量が増加するが、形状コードを使用して１次認識器を訓練し、ＣＡＲＴツリーを生成するためにデータを区分し、次に実際のコードポイントを使用してＣＡＲＴツリーを訓練すると、結果的に限定されるが、より小さく高速の１次認識器が得られる。一次認識器はカイログラフデータを複数クラスの形状に分解するよう最適化されるが、ＣＡＲＴツリーはカイログラフ内の細かい違いに集中するよう最適化されるので、この場合も利点が得られる。
ＣＡＲＴツリーを含む認識メカニズムが開発されると、その認識メカニズムは比較的ローパワーのシステム、たとえば、ハンドヘルドパーソナル計算装置で使用することができる。図１４〜図１５は、文字を認識するためにシステムをどのように使用するかを示している。まず、システムは、ステップ１１００でタッチセンシティブ画面上のペン入力などにより、既知の方法でユーザからカイログラフ８０（図１４）を受け取る。次に、本発明の認識メカニズムは、カイログラフを１次認識器４４に提示し、それからコードポイント（または形状インデックス）８２を受け取る（ステップ１１０２）。ステップ１１０４では、（ルックアッププロセス８４などにより）コードポイント８２を使用して、そのコードポイントがそれに関連するＣＡＲＴツリーを有するかどうかを判定する。有していない場合、１次認識器から返されたコードポイント８２は、返されたコードポイント８８として、ステップ１１０８で認識メカニズムによって返される。
しかし、ＣＡＲＴツリーがコードポイント８２に関連する場合、使用可能なＣＡＲＴツリー７２のセット内の適切なＣＡＲＴツリーを選択し、ステップ１１０６でカイログラフ８０をそれに提示する。ただし、それだけでコードポイントにはならない形状インデックスコードは、形状インデックスをコードポイントに変換する最小限のものだけであっても、それに関連する２次認識器（ＣＡＲＴツリー）を有することに留意されたい。選択されたＣＡＲＴツリーによって返されたコードポイントは、返されたコードポイント８８としてステップ１１０８で返される。ステップ１１１０で検出されるように、認識メカニズムは、ユーザが書込みを完了するまで繰り返す。
本発明にとって必要ではないが、１次認識器が代替コードポイントのリストを返す場合、リストを走査して関連のＣＡＲＴツリーを有するコードポイントの有無を調べ、リスト内のコードポイントの１つまたは複数について２次認識器を操作することができる。２次プロセスは、上に置かれたＣＡＲＴツリーからの結果によって、すなわち、最高の確率によって、リストを整理し直す。さらに、ＣＡＲＴツリーは、確率によってランク付けられた代替物を提供することができ、そのすべてを確率でランク付けられた複合リストに組み立てることができる。
さらに、複数のＣＡＲＴツリーを単一の文字に関連付けることもできる。たとえば、２ストロークの「Ａ」形文字を区別するために２次プロセスとして第１のＣＡＲＴツリーを設け、３ストローク以上の「Ａ」形文字を区別するために第２の別個のＣＡＲＴツリーを設けることができる。しかも、ストロークを分割するために１次認識器を配置することができ、たとえば、１ストロークの「Ａ」形文字を１次認識器によるその分析の前に１次認識器によってまず２つのストロークに分割することができる。１次または２次あるいは両方の認識器は、ストロークカウント以外の特徴を同様に使用することができる。
最後に、本発明はオンラインとオフライン両方の文字認識に適用可能であることが分かるだろう。オンライン文字認識では、文字内の点を（ｘ、ｙ、時間）という形式の座標として受け取り、すなわち、ペンアップおよびベンダウン位置とともにそれらの点が順に分かってくる。オフラインのカイログラフは特定の順序のないｘ−ｙ点にすぎない。本発明はどちらのタイプの認識でも価値のあるものであるが、１次認識器と２次認識器（たとえば、それに関する質問）は互いにかなり異なるものになるだろう。
上記の詳細な説明から分かるように、手書き認識のエラー率を低減するために改良された方法およびメカニズムを提供する。この方法およびメカニズムは、高い成功率で通常は混同される文字同士を区別し、サンプルデータを使用して自動的に訓練することができる。また、この方法およびメカニズムは、高速で信頼でき、費用対効果が高く、フレキシブルで拡張性のあるものである。
本発明は様々な変更および代替構築が可能であるが、例示した所与の実施形態を添付図面に示し、上記で詳細に説明してきた。しかし、開示した具体的な形式に本発明を限定する意図はなく、むしろ、本発明の精神および範囲内に該当するすべての変更、代替構築、および同等物を含むことを意図することを理解されたい。
【図１】
0004233612.tif 000002
【図２】
0004233612.tif 000003
【図３】
0004233612.tif 000004
【図４】
0004233612.tif 000005
【図５】
0004233612.tif 000006
【図６】
0004233612.tif 000007
【図７】
0004233612.tif 000008
【図８】
0004233612.tif 000009
【図９】
0004233612.tif 000010
【図１０】
0004233612.tif 000011
【図１１】
0004233612.tif 000012
【図１２】
0004233612.tif 000013
【図１３】
0004233612.tif 000014
【図１４】
0004233612.tif 000015
【図１５】
0004233612.tif 000016