JPH0844826A - 手書き入力照合方法 - Google Patents

Abstract

(57)【要約】 【目的】手書き筆跡を、文字コードに変換せずに、記憶
されているサンプルと照合することによって迅速に識別
する。 【構成】本発明は、ペン入力などの走り書き入力軌跡に
おける極小速度ポイントの識別を行う。次に、構文法的
照合、ワード照合および弾力的照合の３つの照合アルゴ
リズムを用いて、入力筆跡の照合を行う。構文法的照合
モジュールは極小速度領域における筆跡の形状に従って
筆跡を符号化する。ワード照合モジュールは、極小速度
ポイントの基準線に対する相対的高さに従って筆跡を符
号化する。弾力的照合モジュールは、極小速度と中間ポ
イントの分類に従って筆跡を符号化する。最後に、上記
３つのモジュールによる照合結果を加重平均して、総合
照合結果とする。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、手書き筆跡をＡＳＣＩ
Ｉ符号に変換することなく、電子インクの標本テキスト
を探索する方法と装置に関するものである。上記「電子
インク」とは、ペン入力型コンピュータなど手書き入力
を捕捉するコンピュータ入力装置を使用する際にユーザ
によって作成される動的軌跡を意味する。この技術を、
本明細書の以下の説明において、「走り書き照合」と呼
称する。

【０００２】

【従来の技術】ペン入力コンピュータ・システムに関し
て、手書き入力を認識する多くの既知のシステムがあ
る。そのようなシステムは、通常、入力の際に個々の文
字を認識し、ＡＳＣＩＩテキストへそれらを変換するこ
とによって、システムにおける次のステップとしての記
憶および処理に備える。この方法では、必要な認識精度
を高めれば、処理能力のオーバーヘッドが増大する。既
知のシステムにおいては、制約のない入力のために、認
識精度がむしろ制限されている。一部の手書き認識シス
テムにおいて、入力軌跡における最低速度を突き止め、
この情報を使用して、認識プロセスの１つのステップと
して、入力を複数のストロークに細分化する方法が知ら
れている。

【０００３】全面的手書き認識を行い、次に目標のＡＳ
ＣＩＩテキストの探索を行う方法に比較して、走り書き
照合は、次のようないくつかの利点を有する。 i）あるユーザの入力を同じユーザの以前の入力と比較
する個人向け装置においては、照合精度は比較的高い。
手書き認識では、人々が自然に書く際に用いる非常に多
様な文字形式に対処する能力に限界がある。走り書き照
合は、使用する文字形式が合理的に首尾一貫したもので
あることをユーザに要求するだけであり、その文字形式
が本質的に認識可能か否かは重要ではない。 ii）制約のない手書きの数百のエントリ（入力データ）
からなる相対的に小さい探索リストに関しては、ＡＳＣ
ＩＩテキストへの変換より、走り書き照合の方が処理コ
ストは安い。 iii）書き手は、特定の文字セットに制約されず、シス
テムを訓練する必要なしに、任意の記号を使用すること
ができる。小さなアイコン図柄、個人的記号、他の言語
が使用する記号などは、すべてそれらが十分に識別でき
安定している限り使用することができる。 以下の論文に、走り書き照合の既知の方法が記載されて
いる。 ・Daniel P.Lopresti, Andrew Tomkins両氏による" Pic
tographic naming（象形文字の命名）"(TechnialReport
007-mei-pti-mitl-228- 1, Matsushita Information T
echology Laboratory, Princeton, November, 1992)。 ・Daniel P. Lopresti, Andrew Tomldns両氏による"A c
omparison of techniques for graphical database que
ues（グラフィカル・データベース待ち行列に関する技
術の比較）"(Technial Report MITL-TR-45-93, Matsush
ita InformationTechology Laboratory, Princeton, Ma
y, 1993)。 ・Thierry Paquet, Yves Lecourtier両氏による"Recogn
ition of handwritten sentences using a restricted
lexicon（制約された辞書を使用した手書き文の認識"
（Pattern Recognition. 26(3):391 - 407, 1993）。

【０００４】最初の２つの参照論文は、１人の書き手の
中でも変動が大きいため難しい問題とされる象形文字の
照合に関するものであり、これらは、統計的パターン認
識技術であるヒデン・マルコフ（Ｈｉｄｄｅｎ Ｍａｒ
ｋｏｖ）モデルの使用を記述している。３番目の参照論
文は、本発明が課題とするものとは別の問題であるが、
オフラインすなわち静的なイメージ照合を記述してい
る。

【０００５】

【発明が解決しようとする課題】上記３つの参照論文す
べてに記載されている方法が提供する手書き照合の精度
は相対的に低く、精度の高い手書き筆跡の照合方法が必
要とされている。

【０００６】

【課題を解決するための手段】本発明に従って、電子的
に記憶される手書き入力のサンプルを別に記憶された他
の手書き入力と照合する方法が提供される。この方法
は、手書き入力軌跡において１つまたは複数の極小速度
ポイントを突き止めるステップと、極小速度ポイントに
おける手書き入力の特徴を表す一連の記号を使用して手
書き入力を符号化するステップと、ストリング編集距離
計測(すなわち、string edit distance metric)アルゴ
リズムを使用して、上記一連の符号を他の手書き入力サ
ンプルの符号と照合するステップとを含む。

【０００７】本発明は、位相的および／あるいは時間的
特徴に従った走り書き照合によって全面的手書き認識の
問題を回避し、相対的に高い合致率を達成する。走り書
き照合における極小速度ポイントの利用は、そのサンプ
ルを他のサンプルに対して照合を行うため、各サンプル
の相対的に安定したポイント（または点）のセットを提
供する。更に、極小速度ポイントの利用は、相対的に安
定したポイントのセットが走り書き入力を符号化するた
めに使用されることによって記憶装置と処理能力を節約
することを意味する。本発明に従う走り書き照合方法
は、既知の方法と比較してパフォーマンスの向上を示
す。

【０００８】本発明に従う方法は、広範囲にわたるアプ
リケーションで使うことができる。例えば、電子電話帳
における手書き入力の照合や、ファイルすなわちノート
や文書の検索、手書き電子ノートのメモの探索などにお
いて本発明の方法は使用される。符号化される特徴は、
極小速度ポイントの領域における手書き入力の形状とし
てもよく、記号は、複数の形状特性を表すものとしても
よい。以下の形状特性のセットを、符号化のために使用
することが可能である。すなわち、尖端、開放曲線、閉
鎖曲線、および線末であって、編集コスト（２つのスト
リングを照合する場合の手間を意味する用語であり、詳
細は後述される）は、形状特性に依存する。線末と上記
諸曲線特性との間の置き換えコストは、相対的に低い。

【０００９】形状特性のセットは、更に、その他の円滑
な曲線と分音記号を含む場合もあり、これらの特性に対
する挿入および削除のコストは、相対的に低い。この特
定の特徴セットは、良好な結果を生み出すことがわかっ
ており、また、避けがたいことではあるが同一書き手の
書き方の変動も、上記特徴セットによってマスクされ
る。編集コストは、照合プロセスにおいて挿入、削除ま
たは置き換えが行われる特性に従って、各特性に対する
そのような編集動作の各々の有効度が適切に考慮される
ように調整される。編集コストは、また、対応する編集
動作の発生の確率に依存する。この特徴は、変動発生の
可能性と変動の影響との間の相関関係を活用する。従っ
て、尖端へのループの変形のような非常にありそうな変
動の発生源が、ありそうもないが顕著な変形よりも、２
つのサンプルの間の相違を少なくすることに貢献する。

【００１０】本発明に従う別の方法には、極小速度ポイ
ントにおける手書き入力の正規化された（基準線に対し
相対的な）高さを符号化するステップが含まれる。この
場合、高さは、連続的尺度で符号化され、編集コスト
は、符号化される高さに依存する。この方法は、照合の
基礎として語（またはワード）の上昇区と下降区のパタ
ーン表示を使い、手書き筆跡の各節目ポイント（点）毎
に１つのエントリを持つ高さの符号ベクトルを生成す
る。節目の高さは、中線からの正規化された距離によっ
て表される。

【００１１】システムによっては、ストロークは、「上
昇区」、「下降区」または「本体」のような離散的カテ
ゴリに分類される。このアプローチの問題は、相対的に
互いが接近しているが、分割線の両側にある２つのポイ
ント（点）が、異なって類別されるため、その相違が誇
張される点にある。極小速度ポイントを単に「上昇
区」、「下降区」または「本体」として類別するのでは
なく、連続的高さ符号化アルゴリズムを使用することに
よって、特性の相違が誇張される境界線分類方式におけ
る正確度の減少が回避される。削除と挿入に関する編集
コストは、対象となる極小速度ポイントの符号化される
高さの度合いに対応し、置き換えに対する編集コスト
は、対象となる極小速度ポイントの高さの相違に対応す
る。

【００１２】本発明の更に別の実施方法には、手書き入
力の再サンプリングによって生成される極小速度ポイン
ト間の中間のポイントの特徴を表す一連の記号によっ
て、手書き入力を符号化するステップと、上記中間ポイ
ントの正規化された高さ、当該ポイントにおける手書き
入力の接線に対する角度、および、ポイントを電子イン
クの切れ目、極小速度ポイントまたは中間ポイントのい
ずれかへのポイント分類を含む３項目によって、極小速
度ポイントと中間のポイントを符号化するステップと、
高さ、角度およびポイント分類に従って編集コストを使
用するステップとが含まれる。この実施方法において、
多角形の再サンプリングが使われ、極小速度ポイント領
域の走り書きの形状だけでなく、走り書き全体の形状を
照合されるので、極小速度ポイントの間の手書きの形状
についての情報が活用され、ストローク間の識別の手段
が追加提供される。

【００１３】上記３つの照合方法を用いて照合を行い、
それぞれの照合スコアの加重平均を計算して総合照合ス
コアを求めることが、本発明の実施方法として好まし
い。

【００１４】

【実施例】本発明の好ましい実施例を添付の図面を参照
しながら以下説明する。本発明に従った３つの走り書き
照合アルゴリズムを説明する。それらを詳細に記述する
前に、走り書き照合プロセスと前処理ステップの概要を
先ず説明する。この概要の内容は、本発明の技術分野に
おける現在の技術水準の一端を形成する要素からなる。

【００１５】概要 走り書き照合は、各走り書き入力を符号化して、符号化
された入力を記憶されている走り書きの符号と照合する
ことを必然的に伴う。記憶されている走り書き符号が、
予め処理され、探索テーブルに記憶されていることが好
ましい。

【００１６】どの走り書き照合アルゴリズムも、２つの
構成要素、すなわち、符号化モジュールと照合モジュー
ルを有する。新しい走り書き符号が探索テーブルに加え
られる時は必ず、符号化モジュールが使われる。それ
は、探索を実行する際に役立てる上で十分に安定したい
くつかの書込みの様相を表す走り書きデータから１組の
特徴を抽出する。これらの抽出された符号は、検索の間
使用できるように一定の形式の探索テーブルに記憶され
る。

【００１７】照合モジュールは、探索の実行時に使わ
れ、照会語の符号を探索テーブルの符号と比較する。照
会の符号は、ユーザの書込みにおける多様性のため探索
テーブルの項目と厳密に合致することは殆どない。従っ
て、照合モジュールは、ある種の近似照合を用い、照会
符号が探索テーブルの各エントリとどれほど類似してい
るかを測定しなければならない。得られる結果は、探索
テーブルの各エントリに対する一組の距離スコアであっ
て、これを用いて、可能な合致を順番に並べたリストを
作成することができる。

【００１８】本明細書で説明するアルゴリズムの符号化
方式は、入力走り書きにおいて「節目」として知られる
ポイントのセットにラベルを付けることを基本とする。
これらの節目ポイントは、入力手書き軌跡における終端
ポイント、尖端、連結線などの有意なポイントを表す。
図１は、語'ｐａｄ'という一片の走り書き１０を図示
し、そこに節目１２が示されている。符号化モジュール
は、節目ポイント１２の各々に関する符号および／ある
いは節目ポイント１２の間のストローク部分に関する符
号を生成する。節目検出のプロセスが、図２に図示され
ている。

【００１９】図２を参照すると、節目ポイント検出が以
下の段階に分かれている。 １. ｘおよびｙ軸のストリームは、ノイズを減らす１Ｏ
Ｈｚのカットオフ周波数を用いて、図の符号１４におい
てフィルタされる第１の低周波通過帯域である。このス
テップについては、データ座標のストリームが時間的に
順にサンプルされると仮定して、単純な整数有限のイン
パルス応答フィルタで十分である。１００Ｈｚのサンプ
ル率に関して、フィルタ係数[2 6 12 18 20 18 12 6 2]
を使用できる。 ２. 次に図の符号１６において、フィルタされたストリ
ームが微分され、中央階差演算子Ｘ'_n＝Ｘ_n+1−Ｘ_n-1を
使用してその変化率が抽出される。実際には、組み合わ
されたフィルタ・カーネル[-2 -6 -10 -12 -8 0 8 12 1
0 6 2]で軸ストリームを渦巻き状に巻き付けることによ
って、ステップ１と２は同時に実行される。 ３. 次に、ｘとｙの別々の変化率が、図の符号１８で結
合され、その軌道に沿ってペンの速度

【００２０】

【数１】 が与えられる。ここでｋは、加重定数である。実験結果
は、ｋ＝３が最適であることを示している。実際は、相
対的に手間のかかる平方根の計算よりむしろ上記の式に
対するチェビシェフ（Ｃｈｅｂｙｓｈｅｖ）近似式

【００２１】

【数２】 が使用される。 ４．次に、この速度軌跡の極小値ポイント（複数）が、
節目ポイントとして使われる。極小値ポイントは、図の
符号２０で（２ＯＨｚ低周波通過フィルタを使用して）
平滑化し、速度軌跡を微分し、微分結果の加速軌跡がゼ
ロ交差するポイントを図の符号２２で見い出すことによ
って、その位置が定められる。ゼロ交差の位置は、離散
的な切り上げ切り捨て誤差のため１つのサンプル・ポイ
ントによるのは不正確である場合があるので、各ゼロ交
差の隣接部をチェックして隣接部が更に低い極小速度ポ
イントに対応しているかを調べる。節目ポイント検出の
間生成される一連の軌跡が、図３に示されている。

【００２２】基本的走り書き照合プロセスが、図４に示
されている。照会走り書き３０が、照会走り書き３０の
符号化された形式を生成する符号化モジュール３２に提
供される。次に、符号化された走り書き３４が、符号化
された走り書き３４と探索テーブルのエントリの各々と
に関する距離スコアを計算する照合モジュール３６に提
供される。

【００２３】すべての照合モジュールは、照合近似に関
する同一のアプローチ、すなわち、動的計画法によって
計算されるストリング編集距離アルゴリズムを使用す
る。基本的な動的計画法エンジンの実施方法は、標準的
なものであり、起動する照合モジュールによって設定さ
れる限定的ビーム幅を活用する。このアプローチを記載
する論文の例は、Okuda氏その他による"Correction of
garbled words based onLevenstein metric（レベンシ
ュタイン計測に基づく混同ワードの補正）" (theIEEE t
ransactions on computing, C-25(2), Feb,1976)とR.A.
Wagner, M.J Fisher両氏による"The string-to-string
correction problem（ストリング補正問題）" (Journal
of the Association for Computing Machinery, pg 21
68, 1974)である。

【００２４】動的計画法の照合モジュールが実際には単
に文字ラベルではなく広範囲の記号を使用するとはい
え、編集距離の概念は、（１つは照会走り書きの符号に
関し、１つは候補目標走り書きに関する）２つのストリ
ング照合の観点から見れば最も簡単に考察できる。編集
距離計測は、第１のストリングを第２のストリングに編
集するコスト（すなわち手間）の最低値として、ストリ
ング間の距離を定義する。次の３つの基本的編集動作を
利用できると仮定する。 ・記号S_iの挿入。そのコスト関数はins(S_i)と表記され
る（insは挿入の略称）。 ・記号S_iの削除。そのコスト関数はdel(S_i)と表記され
る（delは削除の略称）。 ・新しい記号S'_iによる記号S_{i ノ}置き換え。そのコスト関
数はsubs(S_i,S'_i）と表記される（subsは置き換えの略
称）。

【００２５】どのような所与のストリングのペアについ
ても、あるストリングを他のストリングに変換できる任
意の数の異なる編集シーケンスがあり、計測はそれらの
可能なシーケンスすべてに対する最小編集コストとして
定義される。例えば、２つのストリングａｂｂｂｃとａ
ｃｂｂを照合し、挿入／削除／置き換えコストがそれぞ
れ１、１、２の動作を編集することを試みると仮定す
る。この場合、第１のｂをｃに置き換え、最後のｃを削
除することに対応して、これらの２つのストリングの間
の編集距離値は３である。本明細書に記述する３つの走
り書き照合モジュールの各々において、編集コストのセ
ットは、挿入され削除されあるいは置き換えられる特定
の記号に依存する。編集距離コストを計算するために使
われるアルゴリズムは、動的計画法アルゴリズムであ
る。このアルゴリズムは、２次元配列のコストという観
点から見れば最も容易に考察できる（図１８のテーブル
参照）。２つのストリングａ_1...nとｂ_1...mが与えられ
るとすれば、テーブルのエントリd(i,j)が、先ず最も低
いコスト、すなわち、部分ストリングａ_1...iをｂ_1...j
に編集するコストを与える。次に、次式数３を使用し
て、テーブルの１つのパスにおけるd(i,j)エントリを単
純に計算することができる。

【００２６】

【数３】 上記式で、⊥はヌルのストリングを表す。最終的な編集
距離は、図１８の最下行最右欄に到来する値である。

【００２７】走り書き照合モジュールで使われるアルゴ
リズムの実際の実施に際しては、このような全面的テー
ブルが明示的に構築されることはなく、多くても２行、
すなわち、１つは更新されつつある行でもう１つは更新
前の行という２行だけでよい。更に、走査されるテーブ
ルの領域はある部分に限定される。すなわち、テーブル
の対角線のある小さい距離の範囲内にあるセルだけが考
慮される。この走査領域の制限は、編集距離を計算する
コストをΟ（ｎ²）からΟ（ｎｂ）に減少させる（ｎ
は、ストリングの長さで、ｂは、ｎより５から１０倍小
さい走査領域サイズであり、Οは（）内の次数を表
す）。

【００２８】本明細書に記述される走り書き照合モジュ
ールの各々において、照合距離は、これを、照合される
２つのストリングの長さの平均で除することによって正
規化される。ポイント当たりの編集コストというこの計
測方法は、短い照合ストリングの方向へあまりバイアス
されず、実際には、小さいが有用な精度の向上をもたら
す。

【００２９】節目検出に加えて、基本的走り書き照合プ
ロセスの前に実行されるなければならないその他の前処
理ステップがあり、それらは図５に示されている。第１
のステップは、離群ステップ４０である。一部のプラッ
トフォームでは、入力筆跡サンプル・ポイントが不正確
にタイム・スタンプを押され、速度に基づく処理がうま
く動作しないような場合がある。特に、ウインドウズの
プラットホームでは、特別なペン・ドライバを使用する
代わりにマウス・ドライバを介して手書き軌跡座標を捕
捉することが可能である。この場合、手書き軌跡座標
（複数）は、同一のタイムスタンプを押されてグループ
（群）として到着する。時間間隔はその群によって表さ
れるが、個々のサンプルは等間隔であるという仮定のも
とに、個々のサンプルのタイムスタンプを補正するため
次のような単純な前処理ステップが使われる。一連のポ
イント(p₁,t₁), (p₂,t₁)... (P_n,t₁) (P_n+1,t₂)...を受
け取ると仮定すると、離群アルゴリズムは、Δｔ＝（ｔ
₂−ｔ₁）／ｎを計算し、 (p₁,t₁),(p₂,t₁)+Δt)...(p_n,t₁+(n-1).Δt)(p_n+1,
t₂)... という順序でポイント（複数）にラベルを付け直す。

【００３０】次のステップは、鈎取り除きステップ４２
である。デジタイジング・タブレットによって捕捉され
る筆跡における非常に共通の人為的産物は、鈎（フッ
ク）である。書き手がストロークを開始したいと望む位
置に書き手の手がまさに到達する前にペンがインク出し
を始めてしまう場合に鈎が発生する。そのような鈎は、
非常に不安定である。同一の書き手であっても同一語を
数回書くと、見つけだされる鈎の数は非常に変動する。
このように、走り書き符号化ステップが、鈎によって影
響を受けるならば、この変動発生源は、走り書き照合精
度を悪くする。従って、そのような鈎を取り除くように
筆跡を前処理すことには価値がある。

【００３１】通常、図５の符号４１で示される節目検出
プロセスは、所望のストローク開始位置に対応する尖端
における節目を突き止める。従って、鈎取り除きアルゴ
リズムは、各ストロークの最初と最後のセグメントだけ
を考慮する。該アルゴリズムは、下記の式（数４）に該
当するセグメントは鈎であると判定し、それを除去す
る。

【００３２】

【数４】 正確なパラメータ（１ｍｍ、０.２５および４５）は、
例示データの範囲での実験の後選択された。最適値は、
筆跡捕捉システムの特性（ペン適性、ペン接触検出の履
歴、表面摩擦、書込サイズに影響する書き込み領域な
ど）に依存する。

【００３３】次のステップは、フィルタ・ステップ４４
である。これは、同じ１０ＨＺ低周波通過フィルタのス
テップであって、速度検出が後の処理のため軌跡を平滑
化するために使われる前にノイズを減らすためこのステ
ップが使われる。ある種のアルゴリズムでは、特に語
（ワード）形状照合モジュールでは、フィルタされてい
ない軌跡を使用する方が若干ではあるが精度が高いの
で、そのような場合は、このフィルタ・ステップは前処
理段階から除かれる。

【００３４】次のステップは、再サンプリングのステッ
プ４６である。詳細な時間依存の情報を抽出した後、軌
跡を再サンプリングすることは、後の処理を単純化する
（そしてそのコストを低減する）ために有益である。い
くつかの可能な再サンプリング技術のうち、走り書き照
合のために最も有効な多目的技術は、多角形再サンプリ
ングである。この技術は、筆跡認識において一般に使わ
れている。それは、複雑な曲線を、その曲線全体に非常
に近い一連の線分セグメントによって置き換える。本明
細書の実施例において、節目ポイントは、固定的なもの
として取り扱われ、連続した節目ポイントの間のセグメ
ントだけが、多角形として再サンプリングされる。使用
されるアルゴリズムは、図６で示されるように、単純な
帰納的分割アルゴリズムである。

【００３５】軌跡のセグメントＡＢが、再サンプリング
されるべき部分である。初期的には、これは、２つの連
続した節目ポイントの間のセグメントである。再サンプ
リング・アルゴリズムの要点は、次の通りである。 １. ＡとＢの間に直線的セグメントを仮想する。 ２．線ＡＢから最大距離（ｔ）にあるデータ点を定め
る。図６では、これは点Ｃである。 ３．ｔ＜しきい値であれば、終了する（線ＡＢが十分な
近似線である）。そうでなければ、点Ｃを頂点として追
加し、線ＡＣと線ＣＢを再帰的に再サンプリングする。
実施上は、この基本アプローチをスピードアップするた
めに次に述べるように最適化を図ることができる。 ・点Ａを（０，０）座標軸に置き、線ＡＢが勾配ｍを持
つとすると、ｔは次式で計算される。

【００３６】

【数５】 但し、上式で、ｈは、チェビシェフ（Chebyshev）近似
式を用いて、

【００３７】

【数６】 である。このようにして、探索ステップ２において、ｈ
は、単純な整数演算を使用して計算されることができ
る。更に、ｈは、テストされているポイントから独立し
ているので、探索の内部ループの外側で計算することが
できる。 ・曲線セグメントは大部分単純な凸面でほぼ対称的であ
るので、ステップ２の探索は、ＡとＢの間の中間のデー
タ点から坂を登ることで始め、先ず、局所的な極大点を
見つける。この局所的極大点がステップ３の距離テスト
を通過する場合だけ、その他の極大点のチェックが行わ
れる。「しきい値」パラメータは、多角形の近似がオリ
ジナルの筆跡にどれくらい合致するかを決定する。この
パラメータを小さくすれば、近似の正確度は増加する
が、多角形セグメントの数は増加する（従って記憶コス
トと探索時間が増加する）。本明細書に記述されるすべ
ての実施例に対しては、０.１ｍｍというパラメータ設
定が使われている。これは、曲線に対しかなり密接な近
似を与えるもので、１対３.６のデータ減少を生み出
す。

【００３８】具体的実施方法 構文法的照合モジュール 本発明の第１の実施例は、構文法的照合モジュールであ
る。構文法的照合モジュールは、節目ポイントの局所に
おける走り書きの形状を表す記号で、節目ポイントの各
々にラベルをつけることによって走り書きを符号化す
る。使用される特定のラベルは以下の通りである。 ・尖端：上、下、左および右向きの尖端に対してｌ！＜
＞ ・開放曲線：上方に凸形／凹形曲線に対してｎｕ ・閉鎖曲線：ｏｐｙｅ ・その他円滑な曲線：〜 ・分音符号： . ・線末ポイント：ＩＬ｛｝ＮＵＹ この方法で、図１に示される走り書きは、Ｌ！ｐ＜＞ｏ
ｌｕ＞ｏｌＵと符号化される。図１で示される走り書き
は、１１個の節目ポイントを持つようにみえるが、２つ
の節目が文字「ａ」の符号１１の位置で重ね合っている
ため、実際には、１２個の節目ポイントがある。符号
は、各節目ポイント毎に１つの文字ラベルを持つ単純な
ストリングとして記憶される。

【００３９】構文法的照合モジュールの符号化アルゴリ
ズムは、入力インク表示（すなわち筆跡）からラベル・
ストリングを生成するタスクを有する。符号化されるべ
き筆跡は、上述の通り、既に離群され、鈎取り除きさ
れ、そして多角形再サンプリングされていて、節目ポイ
ントが検出されている。アルゴリズムの中心は、単一の
ストローク（すなわちペン下ろしとペン上げとの間の軌
跡）に関して次のステップを実行する。 label stroke: if isDiacritical(stroke) then emit '.' else （ isDiacritical(stroke)が真であれば'.'を出力し、
さもなければ） label start of stroke（ストロークの開始ラベル） ストロークにおける各内部節目ポイント毎に、{label k
not}(節目にラベル付け） label end of stroke（ストロークの終了ラベル） このアルゴリズムの構成要素の各々は、履歴的に設定さ
れたいくつかのしきい値を使用する。これらのしきい値
は、データ・セットの手作業のラベルづけとの比較によ
って実験的に選択することができ、さほど重大な要素で
はない。アルゴリズムが、例えば、ある節目を、主観的
には円滑な曲線のように見えるのに尖端としてラベル付
けをしたとしても、問題ではない。判定されるポイント
は、それがどのようなものであれ、同一の書き手の同一
のワードであれば複数の筆跡にわたって十分安定してい
る。

【００４０】構文法的照合アルゴリズムの構成要素を以
下に詳細に記述する。 isDiacritical- 次の場合にストロークは、分音符号のストロークとみな
される（従ってラベル．が付けられる）。 １. それが単純で小さいこと （節目が５個未満で、そ
の開始点と終了点の間の距離がＤ未満でストロークと直
線の最大離間距離がＤ未満であること）、または、２.
それが、非常に単純で小さいか、または短く水平的であ
ること（節目が２つだけであり、長さがＤ未満である
か、または、ストロークと直線の最大離間距離がＤ未満
であり、かつ、ストロークが水平から３０度の範囲内で
あること）。ここで、任意の限界ＤはＤ＝ｈ／１５によ
って定義され、ｈは符号化される走り書き全体の高さで
ある。これらの基準は、英語のテキストに特有のもので
ある。しかし、分音符号は、照合プロセスにおいて重要
でなく、従って、アルゴリズムのこの部分の正確度は重
大ではない。 角度に関する注− 分音符号フィルタの場合の上記２において、また、下記
のステップのいくつかにおいて、角度をテストする必要
がある。このアルゴリズムの実施において、 １バイト
を使用して、0, 64, 128, 192という角度が上、右、下
および左にそれぞれ対応する角度符号を記憶する。手書
き軌跡は順序があるので、ペンが動く方向はわかる。例
えば、上方向のストロークは、下方向のものと区別でき
る。以下に記述するアルゴリズムの疑似コード定義のす
べてにおいて、この角度表示が使われる。

【００４１】label start of stroke (ストロークの開
始ラベル)− ストロークの開始にラベルをつけるため、以下のような
ストローク開始ラベルを使用する。 label start of stroke: 最初の多角形セグメントの角度αをテストする α∈［-40,40］ ⇒'Ｌ'の出力 （下向ストローク） α∈（40,100） ⇒'｝'の出力 （右向ストローク） α∈［100,156］ ⇒'｜'の出力 （上向ストローク） α∈（156,216） ⇒'｛'の出力 （左向ストローク） このようにして、角度は主な方向について対照的にテス
トされるが、下向ストロークについては若干広い範囲で
テストされる。

【００４２】label end of stroke (ストロークの終了
ラベル)− 走り書きのストロークにおいて、終端でなければ合字で
あるような位置で線が終端となる場合があり、このステ
ップの目的は、そのようなものにしかるべくラベル付け
を行うことである。使用される発見的手法は以下の通り
である。 label end of stroke: ｄ＝（最後の多角形セグメントの角度）−（最後のただ
し１つのセグメントの角度） 最後の多角形のセグメント角度αをテストする α∈［-40,40］ ⇒'Ｌ'の出力 （下向ストローク） α∈（40,100） ⇒ if d>0 then 'Ｎ'の出力 else 'Ｕ'の出力 （右向ストローク） α∈［100,156］ ⇒'｜'の出力 （上向ストローク） α∈（156,216） ⇒ if d>0 then 'Ｙ'の出力 else '｛'の出力 （左向ストローク） これは、水平線末ポイントが、上方または下方に向いて
いるかどうかに応じて若干異なるラベルを持つことを除
いて、本質的にストロークの開始時にラベルをつけるこ
とと同じである。

【００４３】label knot（節目ラベル）− ラベル付けアルゴリズムの最後のコンポーネントは、内
部の節目ポイント、すなわち、ストロークの開始でも終
端でもない節目にラベルをつけることである。 label knot: if isCusp then(isCuspが真か、そうであれば) 尖端の角度αをテストする α∈［-40,40］ ⇒'ｌ'の出力 （下向ストローク） α∈（40,100） ⇒'＞'の出力 （右向ストローク） α∈［100,156］ ⇒'！'の出力 （上向ストローク） α∈（156,216） ⇒'＜'の出力 （左向ストローク） else if isSmoothInflexion then（さもなくば、isSmoo
thInflexionが真か、そうであれば） '〜'の出力 else(さもなければ） if isPositive & isDown then （isPositiveとisDownが
真であれば） 'ｙ'の出力 if isNegative & isUp then （isNegativeとisUpが真で
あれば） 'ｅ'の出力 if isLoop & isPositive then （isLoopとisPositiveが
真であれば） 'ｐ'の出力 if isLoop & isNegative & isClosed then （isLoopとi
sNegativeとisClosedが真であれば）'ｏ'の出力 otherwise（さもなければ） if isUp then（isUpが真であれば） 'ｎ'の出力 if isDown then（isDownが真であれば） 'ｕ'の出力 上記のアルゴリズムで使われるいくつかの発見的な手法
のテストがある。 isCusp 尖端は、節目のいずれかの側の角度変化率に比較して鋭
い角度変化を持つ節目として定義される。「角度変化」
とは、ポイントの何れかの側における多角形セグメント
間の角度の差である。図７は尖端を図示し、図８は対応
する角度を示す。尖端計測は次の通り使われる。

【００４４】

【数７】 尖端計測のｃが、与えられたしきい値（現在７０にセッ
トされている）より大であれば、isCuspは「真」を戻
す。

【００４５】isSmoothInflexion これは、軌跡の円滑な屈折ポイント、すなわち、曲率変
化が小さく、曲率の正負符号が節目を横切って切り換わ
るポイントをテストする。再び図８で示される角度を使
用すれば、isSmoothInflexionは、以下の条件の場合真
を戻す。

【００４６】

【数８】 isPositive/isNegative これらは、軌跡の角度が増加しているか、あるいは減少
しているかを単に表す。再び図８の表記法を使用すれ
ば、isPositiveは、 α₂＞Οならば真を戻す。isNegati
veは、その逆である。

【００４７】isDown/isUp これらは、節目ポイントにおいて軌跡に関して正常な方
向をテストする。その目的のために、図８における２つ
の方向のベクトルＡＢとＣＢの平均として正常な角度β
が扱われる。isDownは、β∈［100,190］ならば真を戻
し、isUpは、β∈［-40,60］ならば真を戻す。これらの
テストは、傾斜した書き手の方向への若干のバイアスを
反映して非対称的である。

【００４８】isLoop/isClosed これらの述部の目的は、開放曲線（'u'と'n'）と閉鎖曲
線（'o'と'p'）を区別することである。これらのテスト
は、前の節目ポイントから次の節目ポイントまでの全範
囲の軌跡を調べ、ｘ値の極小と極大ポイントの位置を定
める。図９のは、３個の節目を持つ開放曲線を示してい
る。図９の（ａ）に示されているように、４つの計測項
目が取られている。ｌｇａｐまたはｒｇａｐが負であれ
ば、それらは、次の計算式（数９）においてゼロにセッ
トされる。もしも

【００４９】

【数９】 ならば、isLoop は真を戻し、もしも

【００５０】

【数１０】 ならば、isClosedは真を戻す。

【００５１】照合は、前述の通り、ストリング編集距離
コストに基づいて行われる。挿入、削除および置き換え
コストのセットは、書き方の多様性（例えば合字の分
断）とラベル付けアルゴリズムの不安定性（例えば、ル
ープのテストで'u'であるべきを'o'としたりあるいはそ
の逆であったりする弱点）に対処するように設定され
る。コストを設定するプロシージャは、次の通りであ
る。 １. コストの初期セットを手作業で定義する。 ２．上記のコスト・セットを使用して、語のペアに関す
る大規模なテスト・データベースにおいて、各ペアの間
の最小コストの編集シーケンスを見い出す。 ３．各記号または記号ペアが置き換え、挿入、および削
除される相対的頻度を測定する。 ４．各記号または記号ペアに関して式Ｃ_i=−ｌｏｇＰ_i
を使用してコストを更新する。 ５．テスト・セットのパフォーマンスについて更新され
たコストを検証する。パフォーマンスが向上した場合、
ステップ２へ進み、さもなければ、前ステップのコスト
・セットを設定値とする。 この結果、低いコストを伴うループから尖端への変形の
ようなありそうな変形を含めた局所的多様性の確率を反
映する固定的コストのテーブルが作成される。実際問題
として、最初に手作業で設定されるコストは、十分に正
確であり、１サイクルの反復的な改善だけで、最終的な
コスト・テーブルを生成することができる。

【００５２】語（ワード）形状照合モジュール 以下に語（ワード）形状照合モジュールの実施例を説明
する。語形状照合モジュールは、例えば図１０で示され
るようにその外周の輪郭線における上昇と下降のパター
ンを反映する走り書きの全体形状の表示を使用する。図
１０で示される語'pad'は、下降区５０から始まり、正
常な文字高さの区域５２に続き、上昇区５４で終わる。
符号化モジュールは、時間の順序で取られる節目の正規
化された高さを表わす整数の符号ベクトルを生成する。
節目の高さは、（たぶん傾斜する）中線および当該走り
書きに関する平均節目高さに対して正規化される。

【００５３】符号化アルゴリズムの概要は以下の通りで
ある。 １．符号ストリングをクリアする。 ２．走り書きのｙ軸密度の度数分布グラフを作成し、そ
の中央値（すなわち中線）を見い出す。 ３．中央値から各節目までの垂直距離の平均値を出す。 ４．時間の順序で、各節目に対して、 ４.１ 節目の高さから中央値を差し引く ４.２ ４.１の結果をステップ３の平均値で除する ４.３ この結果を符号ストリングの最後に追加する。 更に公式的に表現すれば、語形状符号は、Ｓ＝Ｓ₁，
Ｓ₂，．．．．Ｓ_Nのような時間順序で並ぶＮ個の整数Ｓ
_iからなるシーケンスＳとして定義される。ここで、

【００５４】

【数１１】 であり、ｙ_iは、節目ｉのｙ座標の値であり、ｙ_median
は、節目ｉと同じｘ座標における走り書きの中線のｙ座
標であり、

【００５５】

【数１２】 は、中央値から各節目までの垂直距離の平均値である。
これらのパラメータは、図１１に図解されている。

【００５６】比較される２つの走り書きが、走り書きの
範囲内で筆跡の経路を定義するために使われる座標系の
基点に対して異なるグロ―バル位置を持つことはよくあ
りそうなことである。例えば、走り書きテーブル用の入
力書式が、インクを捕捉するために使われるタブレット
の下半分に置かれ、一方、照会走り書き用の入力書式が
上半分に置かれている場合がある。この問題は、節目の
高さを走り書きの中線に比較した相対値で表現すること
によって克服できる。中線は、図１２に図示されている
ように、走り書きの密度をｙ軸に沿って度数分布グラフ
６０で表すことによって見い出される。中線６２の高さ
は、その点よりも高さが高いポイントの数と低いポイン
トの数が等しくなるようなポイントを含む度数分布グラ
フの中点の高さとされる。密度度数分布グラフは、走り
書きをその経路に沿って等距離間隔で再サンプリング
し、再サンプリングされたポイントのｙ座標が度数分布
グラフのそれぞれの柱に該当する度数を数えることによ
って、作成される。正規化は、柱の数と幅にあまり敏感
ではない。本発明の実施例では、走り書きの高さに対し
て均一に広がる５０個の柱が使われる。

【００５７】同様に、比較される２つの走り書きが、サ
イズの点で異なることも非常にありそうなことである。
尺度の一定化は、走り書きのすべての節目と中線との距
離の平均値を分母として、中線とそれぞれの節目との距
離を分子とする比で表すことによって達成される。この
測定は、ある中心位置から節目までの距離の分散値に関
するものである。１片の走り書きのスケールを２倍にす
ることは、この因子のサイズを２倍にし、その結果所望
の正規化を達成する。平均ではなく密度度数分布グラフ
の中位値が、中央点として使われるのは、それが、異常
に長い下降区または上昇区に起因するかけ離れた節目に
対して比較的敏感でないからである。

【００５８】同様に、照合される２つの走り書きの基線
が、水平方向に同じ角度でないこともありそうなことで
ある。図１３に示される方法によって、変化する傾斜へ
の部分的な頑健さが与えられ、傾斜が多少変化したとし
ても耐えることができる。図１３で示されるアプローチ
では、走り書きの境界ボックス６４は、垂直線６５によ
ってサイズが等しい２つの領域、領域１と領域２、に分
割される。密度度数分布グラフは、それぞれの区域に対
してそのそれぞれの中央値を見つけるために、別々に
（上述のように）作成される。区域１に対する中線（中
央値の線）は、先頭中線６６と呼ばれ、区域２に対する
中線は、末尾中線６８と呼ばれる。次に、走り書き全体
に対する傾斜中線７０は、先頭中線６６と走り書きの境
界ボックス６４の左辺の交点と、末尾中線６８と走り書
きの境界ボックス６４の右辺の交点を結ぶ線とされる。
このアプローチは、水平線に対する走り書き基線の実際
の傾斜に関する良好な推定を与えるものではなく、ま
た、特定の走り書きに関しては、下降区と上昇区のパタ
ーンが推定をバイアスする可能性がある。しかしなが
ら、走り書き照合については、２片の走り書きの相対的
傾斜の推定値だけが必要とされ、しかも、上昇区と下降
区のパターンが正しく合致する走り書きにおいては傾斜
は同じであるので、この推定値は信頼できるものであ
る。

【００５９】照合モジュールは、再び、ストリング編集
距離計測アルゴリズムを使用する。このアプローチを使
用するには、基本的挿入、削除および置き換え演算子の
コストを定義することが必要である。符号ストリングの
要素が整数であるので、演算子コストは、下記のような
単純な算術関数として定義することができる。置き換え
コスト

【００６０】

【数１３】 挿入コスト

【００６１】

【数１４】 削除コスト

【００６２】

【数１５】 上記の式においてＣ_inは符号ストリングｎの要素ｉを表
す。これらのコストは、図１４で図解されていて、明示
のため、２つの走り書きは共通の中線を共有していると
仮定している。図１４において、

【００６３】

【数１６】 である点、すなわち、２つの節目の間の置き換えコスト
は、１つを削除してもう一方を挿入するコストに等しい
かそれ以下である点が認められる。

【００６４】もっとも低いコスト編集シーケンスは、同
じ高さを持つ節目の置き換えを含むシーケンスとなる傾
向がある。上昇区（または下降区）の端部にある節目を
他の種類の節目と置き換えること、またはその削除また
は挿入は、高い限界コストを生みだし、全般的照合距離
を増加させる傾向を持つであろう。従って、もっとも低
い全般的照合距離は、意図した通り、下降部、上昇部お
よび本体文字のパターンが同じ２つ走り書きの間のもの
となる傾向がある。更に、中線の近くの節目の挿入と削
除に関する限界コストは低く、従って、全般的照合距離
にあまり影響を及ぼさない。かくして、この照合モジュ
ールは、本体文字の範囲内での節目の配置と合字の使用
における不安定性に対して強く、走り書きの内部の細部
というよりは全体形状に力点を置くことを反映してい
る。

【００６５】弾力的照合モジュール 弾力的形状照合モジュールは、節目における形状でなく
走り書き全体の形状を照合する。比較される走り書き
は、いくつかの標準軸線に関して、例えば、左下の筆点
に始点の位置を定めることによって正確に計測されると
仮定する。サンプル点が少ないことと複数のサンプルの
多様性を考慮して、能率的に類似性を計算するため、こ
れらのポイントを直接使用することを避け、別の方法
で、もっと便利に比較できる一組の特徴を生成すること
をこのモジュールは目的とする。

【００６６】走り書きの複数のサンプルの変動は、スト
ロークのサブセットが異なる順序で入れられる場合に発
生する場合もある。文字ｉのドットや文字ｔの短い横線
のような添加記号をフィルタし、これらの短いストロー
クを比較に使用しないことによって、大部分の一般のス
トロークの変動による影響をなくすことができる。これ
らのストロークは、上述の'isDiacritical'と言う表題
の節で記述されているように、決定される。

【００６７】ペン上げは、ストロークに対するセパレー
タの役目を果たし、ペン下ろし座標軸が同じである可能
性のあるストローク・シーケンス間での曖昧さをなくす
のに役立つ。しかし、それらは繰り返して起きることは
ないかもしれないし、また、同じ走り書きの２つのサン
プルは、ペン上げの数と位置の点で相違するかもしれな
い。ペン上げは、２つのポイント・シーケンスの間のセ
パレータとして記録される。

【００６８】ストローク・シーケンスは、以下のプロセ
スによってポイント・シーケンスから生成される形状符
号ベクトルのシーケンスによって符号化される。 ＊細分化とサブサンプリング ストローク（すなわち２つのペン上げの間のポイントの
シーケンス）は、再サンプリング前処理ステップと連係
して上述の極小速度ポイント情報を使用して、細分化さ
れる。照合の複雑さを減らすため、極小速度ポイントに
よって境界を定められるセグメントは、サブサンプリン
グされ、多角形再サンプリングを使用する一組の直線に
よってセグメントに近似させられる。 ＊サブサンプリングされるポイントの符号化 以下の情報が、サブサンプリングされる空間のポイント
の各々について記録される。 １. 境界ボックスのコーナーからの相対変位ｙ。 ２．該ポイントにおける曲線に対する接線の角度θ（こ
のポイントがペン上げであれば、前のストロークの最後
のポイントと次のストロークの最初のポイントの間の角
度を計算する）。ここで、

【００６９】

【数１７】 である。 ３. ポイントが節目、ペン上げ、または多角形にサブサ
ンプルされた中間ポイントであるかどうかを示す識別
子。 この情報は、適切に数量化され、対精度記憶域要求を最
適化する。本実施例の設定は、変位ｙに対して６ビット
と１符号ビットを、そして、接線角度に対して６ビット
と１符号ビットを使用する。ペン上げの場合、現在のポ
イントは、ペン上げに続くストロークの最初のポイント
であるとみなされる。

【００７０】公式的には、ストローク・シーケンスに対
する形状符号は、以下のタイプのベクトルによって表さ
れる。

【００７１】

【表１】 １. (x,y)は、調べられる現在ポイントを表し、derivat
ive(x,y)は、該ポイントにおけるペン速度の近似値を表
す。 ２. (x',y')は、前のポイントを表す。 ３. centroid(x,y)は、ストローク・シーケンスの中心
を表す。 ４. penup?は、ペン上げを示すブール代数である。 ５. knot-point?は、符号化されたポイントが極小速度
ポイントとして識別されたか否かを示すブール代数であ
る。penup?がセットされている場合これは意味がない。

【００７２】弾力的形状照合モジュールは、構文法的照
合モジュールおよび語形状照合モジュールと同じ動的計
画法アルゴリズムを使用する。要するに、それはプロト
タイプとの照合を試みるために曲線を変形させることを
試みる。２つのストロークの間の位置的距離が、位置の
距離の線形加重総和と、ストロークの各サンプル・ポイ
ントにおける手書き軌跡への接線によって計算される。
距離は以下の理由で起きる。 １．２つのストローク上の対応するポイントの位置的距
離 ２．２つのストロークの内の一方の上に存在する余分な
ポイント。 当該２つのポイントが節目またはサブサンプリングされ
たポイントである場合、あるストロークの中のポイント
pと対応するプロトタイプの中のポイントqとの間の置き
換えコストは、次のように定義される。 subs(p,q)=m(y_p-y_q)+n(θ_p-θ_q) 上記の式において、mとnは、適切に選択される加重パラ
メータである。

【００７３】多角形を用いて再サンプリングされたポイ
ントをペン上げに変形させるコストは、より大きな不一
致を伴うため、再サンプリングされた２つのポイントを
照合するよりも高い。ポイントの挿入は、また、変形コ
ストよりも高いコストがかかる。置き換えコストに対す
る現行の量子化レベルと加重パラメータが図１５のテー
ブルで示されている。

【００７４】節目ポイントに関する多角形サンプル・ポ
イントの置き換えコストが高いので、照合アルゴリズム
は、多数の中間の多角形サンプルの挿入または削除を必
要とすることを意味するとしても、２つの走り書きの節
目ポイントを一致させることを強く試みる。

【００７５】挿入と削除コストは、対称的である。節目
または多角形再サンプリングされるポイントに関する挿
入／削除コストは、節目および多角形再サンプリングさ
れるポイント・ペアに関する最大置き換えコストと等し
い。ペン上げに関するコストは、多角形再サンプルされ
るポイントをペン上げポイントに置き換えるコストに等
しい。コストの例が、図１６のテーブルで示されてい
る。次に、照合プロセスは、これらのコスト関数を使用
して、上述された標準的編集距離アルゴリズムを進め
る。

【００７６】弾力的照合モジュールの可能な変更は、部
分的な照合モジュールとしてそれを使用する点である。
すなわち、有効筆跡のある部分、例えば、５０％だけを
使用したり、最後のｎ個だけの節目の走査を行うなどの
部分照合を行う点である。これは、速度と精度の間のト
レードオフを可能にする。例えば、接頭辞が類似してい
る一部のアプリケーションでは、先頭の筆跡の照合だけ
を行うことによって、すべての走り書きを高速に識別す
ることが可能になる。

【００７７】実際には、複数の走り書き照合アルゴリズ
ムが、速度と精度を最大にするように組み合わされる。
たとえば既知の刈り込みアルゴリズムが、後続の照合段
階をスピードアップできるように探索空間を減らすため
に使われる場合もある。刈り込みアルゴリズムは、照合
の候補となるにはあまりにも照会軌跡と類似してないよ
うな探索テーブル中のエントリを破棄する。刈り込みア
ルゴリズムの誤りは、後に照合プロセスで回復させるこ
とはできないので、通常は、非常に保守的な刈り込み戦
略が使われる。典型的な刈り込みモジュールは、探索空
間を最大でも半分にする。次に、合致候補数を相対的小
さい数Ｎに減少させることによって探索空間を更に減少
させるため、（プロファイル、角度、度数分布グラフ照
合モジュールなどの）線形照合アルゴリズムが使われ
る。最後に、本発明に従った相対的に計算コストの高い
動的計画法走り書き照合モジュール（複数）が、残って
いるＮ個の候補に対して使用され、それらの組み合わさ
れたスコアを用いて最終スコアが生成される。

【００７８】上述の３つの走り書き照合モジュールは、
様々な方法で、例えば、パイプライン方式または並列的
に、組み合わせることができる。１つの可能な組合せ
は、照合の距離値の線形総和を基にするものである。こ
の組合せ技術では、各照合モジュールは、図１７に示さ
れているように、照会走り書きと走り書きテーブルの各
エントリとの間の距離を見い出し、その距離を共通の尺
度に正規化し、それらを総和して、全体距離値d_nを作成
する。

【００７９】正規化される距離値d_nは、該照合モジュー
ルの最良照合距離値の平均d_mと所定のテーブルエントリ
に関して見い出される距離値ηとの差を該照合モジュー
ルの最良照合距離値の標準偏差σで除することによって
得られる。すなわち、d_n=(dm-η)/σ である。ηおよび
σに関する値は、開発試験セットにおいて描かれた複数
の書き手の最良照合距離ポイントを観察することによっ
て得られる。正規化の効果は、すべての照合距離値を１
つの尺度に置くことであり、そのため、それは、照合の
信頼度として解釈される。このようにして、全般的正規
化距離アルゴリズムが、低い信頼性の照合を拒絶するた
めに使われることができる。実際問題として、最良と次
善の照合の間のギャップを見い出すことによって、より
よい拒絶発見手法が見い出される。

【００８０】本発明に従った走り書き照合方法は、受容
可能な照合速度を保ちながら、高い照合精度の達成を可
能にする。速度と精度に対する要求はアプリケーション
に従って変化し、そのような要求に応じて、上述のよう
に照合モジュールを組み合わせることができる。

【００８１】上述された方法のすべては、ソフトウェア
で実施されている。ハードウェアの実施も専用装置にお
いて同様に可能であることは理解されることであろう。

【００８２】本発明が、走り書きを入力するため特定の
入力手段に限定されず、走り書きを入力するため、ペン
入力、指先入力、マウス入力およびその他の手段を活用
する方法と装置を使用することができる点は、理解され
ることであろう。

【００８３】本発明には、例として次のような実施様態
が含まれる。 （１）電子的に記憶される手書き入力の１つのサンプル
を別に記憶された他の複数の手書き入力サンプルと照合
する方法であって、手書き入力軌跡における１つまたは
複数の極小速度ポイントの位置を定めるステップと、上
記極小速度ポイントにおける手書き入力の特徴を表す記
号のシーケンスによって、上記手書き入力軌跡を符号化
するステップと、ストリング編集距離計測を使用して、
上記シーケンスを、別の手書き入力サンプルの符号と照
合するステップと、を含む手書き入力照合方法。 （２）符号化される上記特徴は、極小速度区域における
手書き入力の形状であり、上記記号は１組の形状特性を
表し、上記ストリング編集距離計測は上記形状特性に依
存する、上記（１）に記載の方法。 （３）上記１組の形状特性が、尖端、開放曲線、閉鎖曲
線および線末を含む、上記（２）に記載の方法。 （４）線末と曲線特性の間での置き換えコストが相対的
に低い、上記（３）に記載の方法。 （５）上記１組の形状特性が、その他の円滑な曲線と分
音記号をさらに含み、それらの形状特性に対する挿入と
削除コストが相対的に低い、上記（３）または（４）に
記載の方法。 （６）編集コストが、対応する編集動作の発生確率に依
存している、上記（１）、（２）、（３）、（４）また
は（５）に記載の方法。 （７）上記極小速度ポイントにおける手書き入力軌跡の
高さを１つの基準線に対して正規化させた値を符号化す
るステップをさらに含み、上記高さが連続的尺度で符号
化され、上記編集コストは上記符号化された高さに依存
する、上記（１）に記載の方法。

【００８４】（８）削除と挿入に対する編集コストが、
関連した極小速度ポイントの符号化された高さの大きさ
に対応し、置き換えに対する編集コストが、関連した極
小速度ポイントの高さの距離に対応する、上記（７）に
記載の方法。 （９）上記極小速度ポイントの中間にあり、その部分の
手書き入力軌跡を再サンプリングすることによって生成
される中間ポイントの特徴を表す記号のシーケンスによ
って、手書き入力軌跡を符号化するステップと、当該ポ
イントの正規化された高さ、関連したポイントにおける
手書き入力の接線に対する角度、および、電子的筆跡の
中断ポイント、極小速度ポイントまたは中間ポイントと
しての当該ポイントの分類を含む３項目によって、ま
た、上記高さ、上記角度および上記分類におけるが距離
に依存する編集コストを使用することによって、上記極
小速度ポイントおよび上記中間ポイントを符号化するス
テップと、を含む上記（１）に記載の方法。 （１０）上記再サンプリングのステップが、多角形の再
サンプリングを含む、上記（９）に記載の方法。 （１１）上記（２）から（６）までの何れかに記載の方
法、上記（７）と（８）に記載の方法、および上記
（９）と（１０）に記載の方法の３つの方法を組合せる
ステップと、上記３つの方法から得られる個別の照合ス
コアの加重平均を計算して、総合照合スコアを作成する
ステップと、を含む方法。 （１２）上記（１）から（１１）のうちのどの１つにで
も記載されている方法を実施するように構成される手書
き照合装置。

【００８５】

【発明の効果】本発明に従う上記３つの照合アルゴリズ
ムとそれらの最適な組合せによって、ペン入力コンピュ
ータなどにおける手書き入力を使用するアプリケーショ
ンのため、それぞれのアプリケーションによって異なる
処理速度と精度の要求に対応して、受容可能な照合速度
を保ちながら、手書き入力筆跡の高い照合精度を達成す
ることができる。

【図面の簡単な説明】

【図１】１片の走り書きとその複数の節目ポイントを示
す図である。

【図２】節目検出プロセスを示すブロック図である。

【図３】節目検出の際の軌跡シーケンスを示す図であ
る。

【図４】既知の基本的走り書き照合プロセスを示すブロ
ック図である。

【図５】前処理を示すブロック図である。

【図６】再帰的分割を使用する多角形再サンプリングを
示す図である。

【図７】尖端を示す図である。

【図８】多角形セグメントの角度を示す図である。

【図９】開放ループと関連計測因子を示す図である。

【図１０】ワード形状照合モジュールによる符号化に関
連する図である。

【図１１】ワード形状符号のコンポーネントを示す図で
ある。

【図１２】中線を抽出する度数分布グラフを示す図であ
る。

【図１３】傾斜補正のステップを示す図である。

【図１４】ワード照合モジュールに連係する編集コスト
のテーブルを示す図である。

【図１５】弾力的照合モジュールのための置き換えコス
トのテーブルを示す図である。

【図１６】弾力的照合モジュールのための挿入／削除コ
ストのテーブルを示す図である。

【図１７】３つの照合モジュールを組み合わせて総合照
合スコアを得るプロセスを示すブロック図である。

【図１８】動的計画法コストの配列テーブルを示す図で
ある。

【符号の説明】

１０ 走り書き １２、４１ 節目 ３０ 照会走り書き ３２ 符号化モジュール ３４ 符号化された走り書き ３６ 照合モジュール ４０ 離群ステップ ４２ 鈎取り除きステップ ４４ フィルタ ４４ 再サンプリング ５０ 下降区 ５２ 通常文字高さ区間 ５４ 上昇区 ６０ 度数分布グラフ ６２ 中線 ６４ 境界ボックス ６５ 垂直線 ６６ 先頭中線 ６８ 末尾中線 ７０ 傾斜中線

───────────────────────────────────────────────────── フロントページの続き (72)発明者 ディパンカー・グプタ イギリス、ビーエス16、３エルゼット、ブ リストル、フィッシュポンズ、フィツロ イ・ロード 18

Claims (1)

【特許請求の範囲】
1. 【請求項１】電子的に記憶される手書き入力の１つのサ
   ンプルを別に記憶された他の複数の手書き入力サンプル
   と照合する方法であって、 手書き入力軌跡における１つまたは複数の極小速度ポイ
   ントの位置を定めるステップと、 上記極小速度ポイントにおける手書き入力の特徴を表す
   記号のシーケンスによって、上記手書き入力軌跡を符号
   化するステップと、 ストリング編集距離計測を使用して、上記シーケンス
   を、別の手書き入力サンプルの符号と照合するステップ
   と、 を含む手書き入力照合方法。