JP4180137B2 - オンライン手書き文字認識方法 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は、オンライン手書き文字認識の方法、特に楷書のみならず、続け字や崩し字をも正確に認識する手書き文字認識の方法に関する。
【０００２】
【従来の技術】
ペン入力の電子手帳、ワードプロセッサ、コンピュータなどで重要な役割を演じるオンライン手書き文字認識については、既に多くの方法が報告されている。例えば、特開平８−１０１８８９号公報には、続け字や崩し字に強い方法であるリパラメトライズド・アングル・バリエーション法が開示されている。この方法に関するその他の文献としては、小林充ら、「Reparametrized Angle Variations を用いるon-line 手書き文字認識」、信学技報、PRU94-121, pp. 23-30 (1995) や、宮本修ら、「On-line 文字認識アルゴリズムReparametrized Angle Variations を高速に実行するハードウェアボードについて」、信学技報、PRU94-136, pp. 49-56 (1995) がある。これらの方法は、独特のデータ圧縮手順を含み、続け字や崩し字に対する文字認識に関しては、先行技術を相当程度上回る精度を示したが、圧縮データと辞書データのマッチングは、ダイナミックプログラミング（ＤＰ）の手法を利用していた。
【０００３】
そのほか、総括的な論文として、Tappert, C.C., et al., IEEE Trans. Patt. Anal. Machine Intell., vol. 12, No. 18, August, pp. 787-808 (1990) があるほか、最近の論文では、鶴田彰ら、「オンライン手書き文字認識システム」、シャープ技報 57, pp5-8 (1993) 、秋山勝彦ら、「ストロークのつながりに寛容なオンライン手書き文字認識」、画像の認識・理解シンポジウム(1994)、趙鵬ら、「オンライン手書き走り書き文字認識における汎用辞書の作成」、情報処理 Vol.34, No. 3, pp.418-425などがある。
より広く携帯電子機器が広まっている現状においては、認識困難な雑な手書き文字を、より精度よく認識することができる方法が求められている。
【０００４】
【発明が解決しようとする課題】
本発明は、上述の従来技術とは全く別の観点から文字の認識と学習を行う、精度の高い手書き文字の認識方法を提供することを目的とする。本発明の方法は、電子手帳などの携帯電子機器の現行の標準的なハードウェアにより実行可能なプログラムに実施可能なものである。
【０００５】
【課題を解決するための手段】
本発明は、高速隠れマルコフモデルと呼ばれるパラダイムをオンラインの手書き文字認識方法に適用することを提案するものである。
【０００６】
本発明は、隠れマルコフモデルを用いた、手書き文字の筆跡の座標の移動と入力用ペンの入力装置表面に対するアップまたはダウンの状態を表す時系列データに基づくオンライン手書き文字認識方法であって、与えられた時系列データから、その時系列データに含まれる点の間の角度情報と距離情報とに基づいて特徴点を抽出して、該時系列データを圧縮する特徴点抽出・データ圧縮ステップと、該特徴点を結ぶ隣り合う線のなす角度とその線の長さと、該ペンのアップまたはダウンとに応じて圧縮された時系列データを量子化する量子化ステップと、量子化された時系列的なデータに、ペンアップとペンダウンの状態変化に基づいて、あるいはペンアップとペンダウンの状態変化および上記角度に関する所定の条件に基づいて区切りを入れて、区切りに挟まれたデータの１個の集まりを隠れマルコフモデルにおける１個の状態に対応させる対応ステップと、この量子化され区切られた時系列的なデータについて、認識すべき文字に対応して予め求められた複数の隠れマルコフモデルのもとで、該データが得られる確率を計算する確率計算ステップとを含み、該確率が最大になる隠れマルコフモデルに対応する文字を最も確からしい文字とする文字認識方法を提供する。
【０００７】
本発明の一実施態様として、上記文字認識方法において、特徴点抽出・データ圧縮ステップは、上記与えられた時系列データのうち、連続してペンダウンの状態にあるデータ点について、隣り合う３個以上のデータ点を選択する選択ステップと、選択された複数個のデータ点の先頭点と最終点を結んだ線分と、該選択された複数個のデータ点の内の隣り合う２点を結ぶ線分とがなす角度と、該隣り合う２点を結ぶ線分の長さを求める角度距離算出ステップと、上記角度と予め定めたしきい角度値との間または上記線分の長さと予め定めたしきい線分長値との間に所定の関係が成立するかを判断する判定ステップと、上記所定の関係が成立すると判定された場合に、上記選択された複数個のデータ点のうちの予め定めるものを特徴点として抽出し、その他のデータ点を捨てる特徴点抽出ステップと、上記に対して、上記連続してペンダウンの状態にあるデータ点に対して、上記選択ステップと、角度距離算出ステップと、判定ステップと、特徴点抽出ステップとが行われるよう、これらのステップを繰り返すステップとを含み、ペンアップを示すデータ点については、データ圧縮を行わない。
【０００８】
また、本発明の別の実施態様として、隠れマルコフモデルにおけるＮ個の状態の間で状態ｊから状態ｉへの遷移確率a _ijをｉ＝ｊとｉ＝ｊ＋１以外の場合には、ゼロに拘束し、さらにa _NNを１に拘束し、初期状態をq _i に固定する。
【０００９】
さらに、本発明のさらに別の実施態様として、上記の文字認識方法は、学習フェーズにおいて、隠れマルコフモデルにおける状態間の遷移確率a _ijを、１に拘束するa _NN以外については、上記区切りに挟まれたデータの集まりそれぞれにある上記量子化されたデータの記号列の数に基づいて得ることを特徴とする。
【００１０】
本発明のさらに別の実施態様として、上記の文字認識方法は、学習フェーズにおいて、上記区切りに挟まれたデータの集まりのそれぞれにある上記量子化されたデータの記号列の数に基づいて、隠れマルコフモデルにおける各状態からの出力確率を得る。
【００１１】
本発明のもう一つの実施態様として、上記文字認識方法は、学習フェーズにおいて、限られた数のデータを学習に用いて生じる過度のオーバーフィットを避けるため、上記遷移確率及び出力確率に対してスムージング処理を行うことを特徴とする。
【００１２】
本発明のさらにまた別の実施態様として、上記文字認識方法は、認識フェーズにおいて、文字の部分的な対応による誤認を防止するため、全ての状態に対する完全な周辺化は行わず、最終時刻における状態を隠れマルコフモデルの最後の状態に拘束して、隠れマルコフモデルに対するある時系列データの確率を計算する。
【００１３】
本発明のもう一つの実施態様として、上記文字認識方法は、学習フェーズにおいて、同一文字に対して複数セットの学習用データがあるとき、第１データセットにより作成した第１隠れマルコフモデルの第１データセットのデータに対する確率を上記の最後の状態への拘束のもとで計算し、該確率の対数値を該データ列の時間の最終値で除して、第１除算結果を得て、また、第１隠れマルコフモデルの第２データセットのデータに対する確率を上記の最後の状態への拘束のもとで計算し、該確率の対数値を該データ列の時間の最終値で除して第２除算結果を得て、ついで、第１除算結果を第２除算結果で除算して得られる値が、所定の正のしきい値より大きい場合に、該第２データセットのデータに基づいて、第２の隠れマルコフモデルを作成する。
【００１４】
本発明において「文字」とは、数字、ローマ字のアルファベット、ひらがな、カタカナ、漢字、漢字の偏や旁などの部分、発音記号、編集記号、編集操作を指示するための記号、ハングルやアラビア語など日本語以外の言語の文字、図形、符号、アイコンなど、手書きすることができ、コンピュータに入力される信号を生み出す二次元的、場合によっては三次元的な情報をいうものである。通念的な「文字」の定義にとらわれず、本明細書では、単に言葉を表すのみならず、何らかの意味または音を表す記号を全て「文字」と呼ぶことに留意されたい。また、本発明おいて、利用できる入力手段としては、ペン入力タブレットといったものが考えられるが、それに限定されるものではない。例えば、カメラによる入力画像の解析などによる身体動作に基づく入力方法なども可能である。
【００１５】
本発明の方法は、実行可能なコンピュータ・プログラムとして、ＣＤ−ＲＯＭや、フロッピーディスク、ハードディスク、メモリーチップ、その他の適当な記憶媒体に記憶させた形で、提供することができるほか、ペン入力の電子手帳、ワードプロセッサ、コンピュータ、ペン入力タブレットなどの装置に組み込んで、提供することができる。
【００１６】
【発明の実施の形態】
［生データ］
タブレットなどの入力機器から入力される生データは、通常、二次元の位置情報x(t _i )=(x₁(t i ), x₂(t i ))とあるストロークの終点か否かを判別する情報p(t _i )(ペンのアップまたはダウンに関する情報）を含んでいる。ここで、t _i は、ある一点の時間を表す。つまり、ある文字や偏や旁その他の適切な文字の一部である筆跡の最初のデータが得られた時刻をt₀とし、その後一定のタイミングでサンプリングをしたとき、i+1 番目の点のサンプリングの時刻はt _i となる。Δt=t _i+1-t i は、通常一定であるが、一定であることには必ずしも拘束されない。通常、Δｔが十分に小さければ、Δｔを一定にして、Δｔ毎にペンがアップ状態またはダウン状態のどちらにあるかをサンプリングすれば十分である。しかし、Δｔを比較的大きくとるときは、例えば、ストロークの開始部と終端部とで、ペンが入力タブレットに接し、入力タブレットから離れる時点をとらえて、Δｔ以外のタイミングで、サンプリングすることもできる。
【００１７】
このような生データの集合を、
【数１】

と表す。ここで、Ｍは取り込まれた生データの点の数を表す。１画の漢字で１０から２０程度、１５画の漢字で８０から１００程度である。Ｒ² は二次元実空間を意味し、｛０，１｝は、ストロークの終点か否かを判断する情報p(t _i ) が０と１の二値のいずれかをとることを意味する。この０と１の数値の選定は任意であり、ここでは、単に例として、０と１を選ぶ。ストロークの終点を、「ペンアップ」として、たとえば、p(t _i )=0 とし、それ以外のストローク上の点を「ペンダウン」として、p(t _i )=1 とするものである。後に行う実験例などにおいては、データベースなどで提供されている文字データを、上記のデータ形式に変換しておく必要がある。
【００１８】
［特徴抽出を含むデータ圧縮］
上述の形式の生データから、本発明の方法にふさわしい特徴を抽出し、かつ、できる限りデータを圧縮する。そのやり方は、以下に述べるようなフローにより処理を行うものをここでは採用するが、本発明は、下記の特徴抽出とデータ圧縮方法に限定されるものではない。
【００１９】
ちなみに、生データには、図４に示すように、手書きストロークの前後には余計な短いベクトル（「ひげ」と呼ぶ）がついていることが多く、学習・認識の妨げになるので、除去する必要がある。
【００２０】
まず、
【数２】

とおき、その点がペンアップの点であるか、ペンダウンの点であるかに応じて、異なる処理を施す。
【００２１】
［特徴抽出とデータ圧縮のためのフロー］
ペンダウンのとき
t₁からt _D-1 の時点まで、ペンがタブレットに接触しているあるストローク内の点を表すペンダウンの状態にあったとすると、
p(t₀)=p(t₁)=p(t₂)=p(t₃)=・・・=p(t_D-1)=0
であり、t _D においては、ストロークの終点であるので、上述の定義によりペンアップの状態となり、p(t _D )=1 である。このような場合、もし１ストローク内のデータ点の数Ｄが３未満（Ｄ＜３）であれば、データの圧縮は行わない。Ｄが３以上であるときは、以下の処理を行う。
【００２２】
この処理において、θ^* はベクトル圧縮のための角度のしきい値であり、以下に検討するベクトルの角度がこの値より小さければベクトルを結合する。ｌ^* は、「ひげ」の除去のための長さのしきい値で、ベクトルの長さがこの値より小さいときは、ひげであると見なす。θ^* とｌ^* の値は、経験的に選択することができるものであり、以下の各式において異なる値を採用することも可能であるが、共通の値にする方が簡明であろう。
ステップ１
３個のデータx(t₀), x(t₁), x(t₂) を選択する。これらの３点は、得られた筆跡データのうちの連続した点である。もし連続してペンダウンの状態にある１ストローク中に３点以上の連続したデータ点がない場合には、データ圧縮の操作は行わない。この図１に示される３点の座標データから、次式
【数３】

に従って、角度△θ_i を求める。図１の場合には、Δθ₁ とΔθ₂ の２個が得られる。つまり、図１に示すように、Δθ_i は、x(t₂)-x(t₀) を基準としたときの、x(t₂)-x(t₀) とx(t _i )-x(t _i-1)のなす角度である。
【００２３】
もし、i=1 または2 について、
【数４】

であれば、ステップ２へゆく。ここで、θ^* とｌ^* は、経験的に選ぶことができる正のしきい値である。そうでなければ、角度差と線の長さが比較的大きいと判断されるので、特徴のある部分であるものとして、x(t₀) とx(t₁) を特徴点とし、さらにx(t₀):=x(t₁)として、すなわち、処理すべき３点を１点だけ先へ進めて、ステップ１へと戻る。このしきい値θ^* は、数度から９０度程度の範囲で選択でき、データ圧縮率と認識率のかねあいから選ばれるものである。その目安としては、漢字では、４５度程度でも十分な認識率が得られる一方、ひらがな等ではこれより小さい値、例えば１０数度程度が望ましいことがわかっている。また、ｌ^* の値は、特に限定されないが、一文字が縦横２４０×２４０の要素の枠内に書き込まれたとして、通常、１５程度以下、４以上の範囲で選ぶことができる。
【００２４】
ステップ２
x(t₀),・・・, x(t₃) の４個の隣接する点のデータに対して、
【数５】

とおく。これは、数３の式と同様に、x(t₃)-x(t₀) を基準として、x(t₃)-x(t₀) とx(t _i )-x(t _i-1)の角度を表すものである（図２参照）。もし、i=1,2,3 のすべてのｉの値について、
【数６】

であれば、ステップ３へ、そうでなければ圧縮データを（x(t₀),x(t₂) ）で定義し、x(t₁) は捨てる。そして、x(t₀):=x(t₂)としてステップ１へゆく。
続くステップへゆく場合には、このような作業を点の数を一つづつ増やして繰り返すが、一般的にステップｋにおいては、次のような操作を行う。
【００２５】
ステップｋ
k+2 個のデータx(t _k+1), …, x(t₀) に対して、
【数７】

を定義する。角度は、x(t _k+1)-x(t₀)を基準とする。もし、i=1,…,k+1すべての値について、
【数８】

であれば、ステップｋ＋１へ、そうでなければ、（x(t₀),x(t _k+1)）を圧縮データとする。つまり、x(t₁),…,x(t_k ) はすべて捨て去る。
【００２６】
たとえば、ステップ１において、「ひげ」となるような短くて角度のついたx(
t₂)-x(t₁) が、絶対値が比較的大きなx(t₁)-x(t₀) の後に続いているとすると、
｜Δθ₂ ｜＞θ^* ，｜x(t₂)-x(t₁) ｜＜l ^* ，｜Δθ₁ ｜＜θ^* ，｜x(t₁)-x(t₀) ｜＞l ^* となり、ステップ２へと進むことになる。｜Δθ₂ ｜が小さい場合も同様である。その結果、その後の処理がどのようなものになっても、少なくと もx(t₁) のデータは捨て去られることとなる。また、もし、x(t₂)-x(t₁) が比較的長さが大きく、x(t₁)-x(t₀) の長さも大きく、相対的な角度も大きいとすると
、｜Δθ₂ ｜＞θ^* ，｜x(t₂) -x(t₁)｜＞l ^* ，｜Δθ₁ ｜＞θ^* ，｜x(t₁) -x(t₀)｜＞l ^* となり、データ圧縮することなく、次のデータセットへとステップ１の処理が進められる。
【００２７】
このような操作を、入力されたストロークの座標点数Ｄに達するまで繰り返して、データ圧縮及び特徴抽出の処理が終了する。
【００２８】
ペンアップのとき
ペンアップのとき入力用のタブレットなどから入力されるp(t)の情報は、たとえば、t _i-1 ≦t ≦t _i の期間はペンアップの状態(p(t)=0)にあり、t<t _i-1, t_i <tでは、ペンダウン(p(t)=1)である。このとき、t _i-1<t<t i の期間ではペンの位置情報が得られず、x(t _i-1)とx(t _i ) のみが得られる。したがって、この場合には、データ圧縮を行わない。
【００２９】
ここで、以上の処理を行った結果残った点を「特徴点」と呼ぶ。上述のように、漢字の場合は、θ^* =45 °程度であるならば、認識率を犠牲にすることなくデータを圧縮することができる。得られた特徴点から、生データよりも美しい字が得られることもある。そのような例を、「木」という漢字を例にとって、図４（ａ）と図５に示す。図４（ａ）がタブレットに入力された手書きデータであり、図５がデータ圧縮の処理を行った後のデータを示す。
【００３０】
［量子化］
前処理としてのデータ圧縮を行ったデータを、改めて
【数９】

とし、このデータのペンアップとペンダウン、角度、そして長さの情報を次のように量子化する。時間t _i は時間のインデクスであるｔ(1,2, …,M）で置き換えられる。まず、ペンのアップとダウンに応じて、
【数１０】

を定義し、また、x(t)から得られる角度情報
【数１１】

を、角度の大きさにおいて均等に分割したＬ_M 個の角度範囲（図６参照）のどこにはいるかにより、量子化あるいはシンボル化して、
【数１２】

とする。図６と後に述べる数値実験では、Ｌ_M ＝１６であるが、Ｌ_M は特定の数値に限定されるものではない。データのもつ長さ情報は、量子化されたデータセット(v_1k, v_2l ) の繰り返しで表現することができる。繰り返しの回数はベクトルの長さをｌとすると、ある定数l₀を基準として、(1/l₀)+ ｌの小数部を切り捨てた値で表される。これにより、例えば、上記のフローにより圧縮された図５の「木」という字は、l₀を適当に定めると、次のような記号列に変換される。
【数１３】

ここでのｔは、上記のｔとは異なるものとなるが、時系列的なインデクスであることには変わりはないので、そのまま用いる。ｔは１からＴまでの整数であるものとする。なお、上記の定数l₀は、例えば、２４０×２４０要素の文字入力範囲を用いたとき、４０から１２０程度の広い範囲から、経験的に選ぶことができることがわかっている。
【００３１】
［隠れマルコフモデル］
次に、モデル化に用いる隠れマルコフモデル(hidden Markov Model; ＨＭＭと略す) は、二重確率的モデルとして知られているパラダイムであるが、混乱などを避けるため、その概要を略説するとともに、記号の定義を整理して示す（隠れマルコフモデルについては、Rabiner, L.R., Proceedings of the IEEE, Vol. 77, No. 2, February, 1989を参照）。後に述べる認識フェーズにおけるオンライン手書き文字での特殊性を考慮する際にも明確な記述が必要になる。
【００３２】
隠れマルコフモデルは、次のような要素により特徴付けられる。
まず、あるモデルにある状態の数をＮとする。ここでの状態とは、一般に隠されたものであるが、以下に説明するように、ある特定の物理的な意味を付与することができるものである。ここでは、個々の状態をq₁,q₂,…,q_N と表す。ある時点の状態Ｑ(t) は、q₁,q₂,…,q_N のいずれかの状態にあることになる。
【００３３】
また、上記の状態一つ当たりの観察可能な値（場合によってはシンボルともいう）の数をＭと表す。この観察可能な値は、モデル化されるシステムの物理的な出力を表すものである。個々の値は、v₁,v₂,…,v_M と表すことができる（この値の集合をＶ＝｛v₁,v₂,…,v_M ｝とする）。たとえば、統計学での古典的な例であるコイン・トスの例を考えると、「表」と「裏」という観察可能な状態がここでいう値v₁とv₂に対応することとなる。
【００３４】
そして、これらの状態間の遷移確率a _ijを考える。ある状態から全ての状態に遷移できるとすると、この遷移確率a _ijは全てのｉとｊについて正の値をとることとなるが、以下に説明するように、必要なモデル化の方法により、遷移確率を特定のｉとｊについてゼロに設定しても、実用的な問題を生じないことが多い。
【００３５】
さらに、ある状態q _i から観察可能な値ｖ_h への出力確率、言い換えれば、ある状態における観察可能な値の確率分布を、出力確率b _ihとする。
【００３６】
そして、初期状態の分布πを考える。これは、起点となる時点での状態q₁,q₂,…,q_N の空間における確率分布で表される（π＝Ｑ(1) ＝｛π₁,π₂,… ,π_N ｝）。
【００３７】
このように、Ｎ，Ｍ，a _ij, b _ih, πが与えられれば、ある観察可能な符号列としてのＯ＝Ｏ₁ Ｏ₂ Ｏ₃ …Ｏ_T （ここで、各Ｏ_i (i=1,2,...,T) は、値Ｖの一つであり、Ｔは一連の観察の回数を表す）を得るための生成方法として、隠れマルコフモデル（ＨＭＭ）を用いることができる。逆に言えば、Ｎ，Ｍ，ａ_ij, b _ih, πがＨＭＭであるということができる。
【００３８】
このようなＨＭＭを現実の応用例に適用するためには、一般に次のような三つの基本的な問題を解く必要がある。
【００３９】
［問題１］
観察された符号列Ｏ＝Ｏ₁ Ｏ₂ Ｏ₃ …Ｏ_T とＨＭＭが与えられたとして、その符号列が得られる確率をどのようにして効率的に計算するか。
【００４０】
［問題２］
観察された符号列Ｏ＝Ｏ₁ Ｏ₂ Ｏ₃ …Ｏ_T とＨＭＭが与えられたとして、どの
ようにしてある意味のあるやり方で最適な対応する状態列q₁q₂q₃…q _T を選べばよいのか、言い換えれば、観察の結果をどのような状態列を選べば最もよく説明できるのか。
【００４１】
［問題３］
上記の符号列を得る確率を最大にするモデルパラメータａ_ij，ｂ_ih，πの値をどのように調整するのか。
【００４２】
上記の問題１は、評価の問題である。あるモデルと観察された結果が与えられているとして、そのモデルによってその観察結果が生成される確率をどのように計算するかという問題である。見方を変えて見れば、ある観察結果が与えられたときに、あるモデルがどれほど上手くマッチするかということを数値により評価する問題と見ることもできる。つまり、ある観察結果が与えられたときに、それに最もよく適合するモデルを選ぶことができる。文字認識においては、認識フェーズともいわれる部分である。
【００４３】
問題２は、モデルの隠された部分、すなわち「正しい」状態列を見いだそうとすることである。ただし、一般的には、「正しい」状態列といったものはなく、実際上、ある最適化条件を用いて、可能な限り上手くこの問題を解こうとする程度のことしかできない。そして、最適化条件は、モデルの対象となる事象（本発明では、手書き文字入力情報）の構造に依存することとなる。
【００４４】
問題３は、どのようにして与えられた観察結果が得られたかを上手く記述するためのモデルパラメータを最適化する問題である。これは、「学習」の問題であり、学習フェーズともいわれる。この問題を解くことにより、現実の事象に最もよく適合するモデルを作成する、つまり、観察された学習データにモデルパラメータを最適に合わせることができる。
【００４５】
手書き文字認識の方法を得るためには、各文字に対するＨＭＭを作成する必要がある。それには、まず、各文字モデルのパラメータ値を見積もって、上記問題３を解決する必要がある。また、モデルにおいて用いる状態の物理的な意味を理解しつつ、学習用に用いる入力された筆跡を区分けして、ある状態列に対応させる必要がある。これは、問題２を解いて、状態の数、ＨＭＭ作成前の前処理の方法、その他のモデル化の詳細を調整して、モデルをよりよいものとすることにほかならない。最後に、各文字に対応して作成されたモデルを用いて、上記の問題１を解くことにより、文字の認識、すなわち最も尤もらしいモデルの評価を行う。
【００４６】
上に略説したＨＭＭの考え方が、本発明の手書き文字認識方法においてどのように適用されるのかを見る。
【００４７】
上で定義された(v_1k, v_2l ), k=1,2, l=1,2,…,L_M は、上記の一般的な説明における観察可能な符号v₁に対応するベクトル量として考えられる。この観察結果である、ある文字の隠れマルコフモデル
【数１４】

は、次の諸量で定義される。
【００４８】
状態Ｑ(t)
【数１５】

とその遷移確率
【数１６】

状態の初期確率分布
【数１７】

出力確率
【数１８】

【００４９】
これらの隠された（観察されない）状態Ｑ(t) と出力確率の存在を考えることが隠れマルコフモデル（ＨＭＭ）を単なるマルコフモデルに対して特徴付けるものである。すなわち、ある時点ｔでの隠された状態Ｑ(t) は、状態q₁,q₂,…,q_N のいずれか一つの状態にある。これらの状態は、ＨＭＭで表現しようとするシステム（ここでは、文字またはその部分あるいは図形）に対して適切に選ぶことができる。後ほどより具体的に説明するが、ここではこれらの状態は、一般的に存在する状態を表すものとして考える。
【００５０】
そしてＱ(t) がある状態q _i にあるとき、この状態qiから観察可能な状態V₁(t) を表す数値v_1k へと遷移する確率がb¹ _ikである。これに対し、遷移確率a _ijは、状態ｊから状態ｉへの遷移確率を示すもので、ここでは隠された状態に対するものとして与えられているが、その意味するところは、普通のマルコフモデルにおける遷移確率と同じである。
【００５１】
実際に入力された文字またはその一部を表す数値列（上述の符号列に対応する）
【数１９】

に対して、すでに記憶されているテンプレートとなる文字
【数２０】

が与えられたとすると、この文字に対する
【数２１】

の結合確率は、次の式で与えられる。
【数２２】

この式が隠れマルコフモデルを定義するものとも言えるもので、本発明における文字の学習と認識の出発点となるものである。
【００５２】
学習とは、入力されたデータに基づく、
【数２３】

といったパラメータとＮの決定である。そして、認識とは、学習されたパラメータからなるＨＭＭに基づき、しかるべき基準で、入力され前処理されたデータＯ(t) がどの文字から発生したものであるのかを決定することである。
【００５３】
一般に、あるパラダイムが具体的問題に対してそのまま有効に働くことはまれである。本発明の場合もその例外ではなく、与えられた問題に固有な拘束条件を工夫することによって、よい結果になりうる。まず、例として隠れマルコフモデル自体に次の拘束条件を付けるが、本発明は、この拘束条件に限定されるものではなく、種々の異なる拘束条件の付け方が可能である。例としてここで用いる拘束条件は、
【数２４】

とするものである。これは、 a_ij の行列を次の形に拘束することを意味する。
【数２５】

さらに、
π＝（１，０，・・・，０）
とする。すなわち、初期状態Ｑ(1) は、常にq₁である。上記のように遷移確率を拘束することは、インデクスが２以上小さいか大きい状態からの遷移確率をゼロとし、インデクスが一つ上の状態に移る可能性がゼロではないものと仮定することになる。このように仮定することにより、前処理済みのデータＯ(t) の時間に関する因果性と連続性を保つことができる。若干異なるが、類似の拘束条件として、i<j のときa _ij=0として、それ以外ではa _ijが正の値をとることとするものも考えることができる。さらに、i<j, i>j+ Δで、a _ij=0という条件も可能である（ここで、Δは正の整数である）。また、初期状態をq₁に拘束することは、学習に関して下記に説明する、状態と観察された数値列の「対応付け」から明らかとなる。
【００５４】
［文字認識］
以下、オンライン手書き文字認識であることの特殊性を考慮した認識と学習の方法を説明する。隠れマルコフモデルにおける認識と学習は表裏一体の関係にあるが、ここでは、まず認識について説明する。
【００５５】
まず、後に述べる学習によって、認識すべき各文字に対する隠れマルコフモデル（ＨＭＭ）
【数２６】

を少なくとも一つ用意する。
【００５６】
そして、各ＨＭＭに対して、与えられ、ある予備的な処理を行った観測値Ｏ(t) （予備的な処理については下記）の確率（蓋然性）を計算する。そして、最も高い確率値を与えるＨＭＭをもっとも確からしい文字と判断する。これは、上述の隠れマルコフモデルの基本的な問題１に該当する。すなわち、ある観測値列Ｏ＝Ｏ(1) Ｏ(2) Ｏ(3) …Ｏ(T) とＨＭＭが与えられたとして、その観測値列が得られる確率を効率的に計算するという課題である。
【００５７】
効率的な計算のために、まず、α_i (t) を次のように定義する。
【数２７】

【００５８】
これは、あるＨＭＭが与えられたとして、時刻ｔまでのＯ(1),Ｏ(2),・・・, Ｏ(t) の部分的な観測値列が得られ、時刻ｔにＱ(t) となる確率を意味する。このα_i (t) は、次のようにして解くことができる。
【００５９】
（１）開始ステップ
α_i (1) ＝π_i b _i ( Ｏ(1)) i=1,…,N
（２）誘導ステップ
【数２８】

（３）終了ステップ
【数２９】

【００６０】
まず、開始ステップにおいて、状態q _i と初期観測値Ｏ₁ との結合確率として、前進方向確率の初期化を行う。ここでb _i （Ｏ(1))は、Ｏ(1) への出力確率である。次いで、誘導ステップにおいて、時刻ｔにおけるＮ個の可能な状態q _i (1≦i ≦N)から、どのようにして時刻t+1 において状態q _j に到達できるかを考えるのである。すなわち、α_i (t) がＯ(1),Ｏ(2),...,Ｏ(t) という観測値が得られ、時刻ｔでの状態q _i を経由して時刻t+1 に状態q _j に到達する結合確率は、α_i (t)a_jiとなる。可能なＮ個の状態q _i の全てについて、時刻ｔにおけるこの積の和をとると、それに伴うそれ以前の全ての部分的な観測値を含む、時刻t+1 におけるq _j の確率を得ることができる。これにより、q _j の確率が分かれば、状態q _j におけるＯ(t+1) を考慮に入れることで、すなわち、b _j (t+1) の出力確率を上記の和に掛けてやることで、α_j (t+1) が得られることは、容易に看取できる。誘導ステップの計算は、与えられた時刻ｔについて、状態を示すインデクスｊ（１≦ｊ≦Ｎ）の全ての値に関して行われる。これをt=1,2,…,T-1について繰り返す。最後に、終了ステップにおいて、あるＨＭＭのもとで観測値列Ｏ＝Ｏ(1),Ｏ(2),...,Ｏ(T) が得られる確率が、α_j (T) の単なる和として求められる。
【００６１】
以上が、ＨＭＭと観測値列が与えられたときに、その確率を計算する一般的な方法である。ある観測値列、すなわちある入力された筆跡データに対して、尤も高い確率値を与えるＨＭＭに対応する文字が、文字認識の回答となるべきものである。この計算の結果が数２２に対応するものである。ところが、本発明方法においては、上記の終了ステップで行われたような q_i ^N _t=1 に関する完全な周辺化は行わず、次式で表される確率が最大となるＨＭＭを最も確からしい文字に対するＨＭＭを考える。従って、上記の数２９における和をとる終了ステップは行われないこととなる。
【００６２】
【数３０】

ここで、arg max は、最大値をとるＨＭＭのインデクスを算出することを意味する。
【００６３】
ここでは、上述のように、すべての隠された状態 q _i ^N _t=1 に関する完全な周辺化は行わず、Q(T)=q_N という拘束条件が付いている。もし完全な周辺化を行ったならば、Ｑ(T) は、上記の式には残らないはずである。いいかえれば、時刻ＴにおけるＱ(t) をＨＭＭの最終的な状態であるq _N に強制的に固定して、確率を計算する。このような拘束条件を付ける理由を以下に説明する。
【００６４】
例えば、漢字「口」と「品」を考える。いま、ペン入力をする筆者は、「口」をタブレットなどの入力装置に記入する。この入力情報に対応する記号列
【数３１】

が得られる。ところが、「口」は「品」の部分集合であるので、「品」のＨＭＭである
【数３２】

に対しては、
【数３３】

というＰ(i) の中には、少なくとも一つはかなり大きな値を有するものが含まれていることが多い。すなわち、ある一つ以上のｉの値においては、Ｐ(i) の値がかなり大きくなりうる。従って、次式により周辺化した結果、かなり大きな値が得られる可能性があり、これは誤認につながるので、避けなければならない。
【数３４】

【００６５】
そのため、最終状態の時点ＴでのＱ(T) をｑ_i として、異なるｉの値についての和をとるのではなく、「品」という漢字に対するＨＭＭのｑ_N に拘束してしまうものである。これにより、上記のような誤認を激減させることができる。同様の理由から、「一」と「二」と「三」、「木」と「林」と「森」などの間での誤認を防ぐことができる。
【００６６】
次に、ＨＭＭにおける学習について説明する。ここで留意されるべきであるのは、よく知られたＨＭＭの学習法であるBaum-Welch法は、与えられた学習データ｛Ｏ(t) ｝に対して、周辺尤度
【数３５】

のグラディエントを幾つかのパラメータに関して計算し、「山登り」を行って最大化する方法である。パラメータ空間内のある点から出発して、この周辺尤度があるパラメータに関して凸になっている保証はない。従って、局所最適解の問題は深刻であり、加えて、収束するまでに多大の計算を要するという問題がある。これは、例えば、教育漢字の８８１程度の文字数で、学習セットが数十という場合であっても、膨大な時間を要するので、実用的ではない。以下に説明する本発明のある実施態様に係る方法では、Baum-Welch法におけるような反復計算は必要としない。
【００６７】
本発明の実施態様において、いま、ある一つの漢字について、学習データがＣセット与えられたと考える。すなわち、第ｃ番目の学習データを Ｏ_c (t) ^Tc _t=1 としたとき、ｃの値が１からＣまであるとすると、データセットは、
【数３６】

と表すことができる。このデータセットの内、まず第１セットについて、下記のような処理を行う。
【００６８】
［ステップ１：第１データセットに基づく遷移確率の算出］
第１データセット
【数３７】

に対して、
(i) Ｖ₁(t)の値が変化する時刻、すなわち、ペンのアップまたはダウンの状態が変化するとき、及び、
(ii)予め与えられた正のしきい値であるθ₀ に対して、Ｖ₂(t)の表す角度の変化がそのしきい値以上になるとき、
の各時点毎に、「区切り」を入れ、ある区切りと次の区切りの間を一つの状態と考えて、状態q _i を対応させる。
あるいは、上記しきい値θ₀ は考慮せずに、Ｖ₁(t)の値が変化する時刻、すなわち、ペンのアップまたはダウンの状態が変化する時点毎に「区切り」を入れるようにすることも、同様にできる。
【００６９】
例えば、上記の「木」という入力文字に対して得られたＯ(t) については、
【数３８】

となる。つまり縦の線がここで加えた「区切り」を表す。従って、画数Ｋを有する入力文字情報を表す｛Ｏ(t) ｝を学習させるＨＭＭは、少なくとも２Ｋ−１個の状態を持ち、さらに、上記のようにデータ圧縮した筆跡の角度の変化が前記しきい値θ₀ を越える度に状態数が増加する。このしきい値θ₀ は、量子化の角度幅以上で１２０度以内の広い範囲で、経験的に求めることができる。なお、ここでの「画数」とは、通常の国語辞典や漢字辞典などにおいて採用されている正式な画数と、手書き文字における手書き入力の際の画数のいずれをも広く意味するものである。
【００７０】
このように、「区切り」を入れて、ペンのアップまたはダウンがあったときのみならず、筆跡の角度が大きく変化した場合に状態を加えるのは、続け字を認識するために、一筆で書かれていても曲がりの大きいものは分割して学習と認識の対象としようとするためである。例えば、図４（ｂ）に示すような手書きの「木」の字の場合、右上の手書きで連続している部分があるため、数３８ではｑ₁ 及びｑ₂ の二つの状態に対応していた横の棒と縦の棒が同じ状態ｑ₁ に対応する（つまり、数３８の第４，第５の要素である（２，１１）と（２，１１）がペンダウンを示す（１，１１）と（１，１１）なってしまう）など、文字の構造を全く反映しないモデルになってしまうため、数３９のように区切る必要が生じる。
【数３９】

そして、現実にはペンダウンの状態にあるが、文字の形態の上からはアップ状態に対応しているｑ₂ からも（さらに同様にアップ状態に対応しているｑ₄ とｑ₆ からも）、ある程度の確率でダウン状態を出力できるように、パラメータを調節する（以下に述べるスムージング手続）ので、数３８を登録したＨＭＭが、図４（ｂ）に示した文字に対応する数３９の観測値列を出力する確率Ｐ（Ｏ₂ ｜Ｈ）を最大にする状態遷移Ｑを、後に詳細に説明するやり方で求める。
【００７１】
次に、上記のＨＭＭの一般的な説明において定義した状態の遷移確率a _ijと状態の初期確率分布πを決定する。
上のステップで得られた区切り付きの状態列において、各状態q _i は幾つかの数値ペアを含んでいる。例えば、上記の例においては、q₁は３個の数値ペアを、q₃は５個の数値ペアを含んでいる。このような数値ペアの数をｎ（Ｏ₁,q i ）とおき、上述した状態の遷移確率a _ijと状態の初期確率分布πを次のように定める。
【数４０】

【００７２】
ここで、a _ijを上記のように定めたのは、ある学習データＯ₁(t)にある、q _i に対応する数値ペアの数がｎ（Ｏ₁,q i ）であるので、数２５の式で規定した拘束条件のもとで、q _j からq _i （i=j またはi=j+1 ）への転移が特定の状態の性質に依存せずに、数値ペアの数に単純に比例して起こるとしたものである。
【００７３】
上記のように初期状態分布πを定めたのも、必ず状態q₁から出発するという状態の定義から明らかである。
【００７４】
また、ここで指摘しておきたいのは、Ｏ₁(t)の第２成分であるＶ₂(t)は角度情報のみであり、第１成分であるＶ₁(t)はペンのオンオフに関する情報を表すだけであるが、この隠れマルコフモデルには長さの情報も含まれていることである。すなわち、｛Ｏ₁(t)｝は、ある基準長をもとに導出されており、各状態q _i における数値ペアの繰り返し回数ｎ｛Ｏ₁,q i ｝に対応した長さ情報が含まれている。
【００７５】
次に、出力確率の集合｛b¹ _ik｝と｛b² _ik｝の各要素の値を定義する必要があるが、状態q _i に対応するｎ（Ｏ₁,q i ）個の数値ペアのうち、
Ｖ₁(t)=v_1kとなる個数をｎ（Ｏ₁,q i_,v_1k ）、
Ｖ₂(t)=v_2kとなる個数をｎ（Ｏ₁,q i v_2k ）とし、
【数４１】

とする。すなわち、全体の数値ペアの数に対して、特定のＶ_ikの値をとるものを数えて、その確率を出力確率とするものである。
【００７６】
以上のようにa _ij、π、b _ijを定めることは、数３６の拘束条件から自然であると考えられるが、このように定めなければならないという積極的な理由があるわけでもない。別の定義を採用することも可能である。
【００７７】
［ステップ２：スムージング］
上記のようにして得られた｛a _ij 、｛b¹ _ik｝、｛b² _ik｝は、第１データ｛Ｏ₁(t)｝のみから決定されているので、極端なオーバーフィット、すなわち、同一文字について、特定の筆跡のみを認識するが他の筆跡をうまく認識できない現象が起こるのが普通である。このオーバーフィットの問題は、ある一つの文字について数千といったオーダーの数の筆跡例のデータと、適当なアルゴリズムを用いれば自然に解消する可能性はありあるが、学習に要する時間を考えると筆跡例の数は、せいぜい数十程度が現実的であろう。したがって、ここでは、オーバーフィットを解消するために用いられるレギュラリゼーション（正則化）的な考え方を用いる。つまり、上記のようにして得られた｛a _ij 、｛b¹ _ik｝、｛b² _ik｝に対して、適当なスムージングと呼ばれる処理を行う。スムージングの目的は、数３６の拘束条件の範囲内で、a _ijや、b¹ _ik、b² _ikの値がゼロになることを防ぐことにある。それには、いくつかのやり方があるが、ここでは、もっとも簡略で代表的な例を以下に採用する。いうまでもないが、本発明の範囲はこの下記の例に限定されるものではない。かきのようなスムージングは、簡単に行える一方、後に見るようにきわめて有効である。
【００７８】
スムージング手続きＡ
｛a _ij｝と｛b¹ _ik｝を次の式により修正する。OLD が上記のもので、NEW がついているのがスムージングにより新たに定義されるものである。
【数４２】

【００７９】
スムージング手続きＢ
｛b² _ik｝を次の式により修正する。手続きＡの場合と同様、OLD が上で求めたもので、NEW がついているのがスムージングにより新たに定義されるものである。
【数４３】

ここで、ｗ_1nは、
【数４４】

を満たすように選ばれる。
【００８０】
上記の手続きＡは、いわゆるフロアリングであり、数２５の拘束条件の範囲内で、ゼロの値をとる要素を避けようとするものである。後に述べる実験では、caとcbは、０．７〜０．９の値で良好な結果が得られている。
また、上記の手続きＢは、フロアリングに加えて、出力確率の高い方向に近い方向のベクトル（上記数値ペア）もある程度の確率で出力されるようにするための手続きである。ｗ_1nの選び方は、いくつか考えられる。以下に示す数値実験では、
【数４５】

を用いた。g(l,n)は、v_2l とv_2n のなす角度であり（図６参照）、ｆ( θ) は区間(-π，π のガウス分布にフロアリングとして(1- α)/2 πを加えて、規格化定数Ｚ（α，σ）で割った値である。なお、Ｌ_M は、上記のように、角度情報を量子化したときの両指数を示す値である。
【００８１】
なお、αとσは、経験により適切に選ぶことができる値であり、それぞれ、0.7 ≦α≦0.9 、π／16≦σ≦π／６程度の範囲内で有効な結果が得られる。図７にｆ( θ) の概形を示す。
【００８２】
［ステップ３：複数のデータセットに基づく学習］
これまでは、第１データに基づく隠れマルコフモデルの作成について述べてきたが、認識率を向上させるためには、複数のデータセットを用いて学習を行うことが望まれる。次に、第２以降のデータセット｛Ｏ_c (t) ｝，c=2,...,C に基づく学習法について述べる。ここで、C は、データ数を表す正の整数である。
【００８３】
最尤状態遷移｛Ｏ_c (t) ｝を求める。ある学習データセット｛Ｏ_c (t) ^Tc _t=1 のうちc=2,...,C のそれぞれの値の学習データについて、次式
【数４６】

より、順にt=T _c からt=1 へと、最尤状態遷移 Ｑ_c (t) ^Tc _t=1 を求めることができる。すなわち、まず数４６の第１式により、Ｑ_c (T_c ) が求まれば、それを第２式に代入して、順次、Q _c (T_c-1), Q c (T_c-2),..., Q c (1) が求まる。そして、c=2,...,C のそれぞれのc の値について（すなわち、第２から第Ｃ番目のデータについて）、第１のデータの場合と同様にして、ｎ( Ｏ_c ,q_i ) 、ｎ( Ｏ_c ,q_i ,v_1k) 、ｎ( Ｏ_c ,q_i ,v_2l) を求めることができる。
【００８４】
数４６の式は、よく知られたViterbi アルゴリズムを用いて解くことができる。たとえば、
【数４７】

というＨＭＭがＯ＝｛３，３，１，２，３｝という観測値列を出力するときの最適状態推移は、
【数４８】

より、Ｑ（５）＝ｑ₃
【数４９】

より（Ａ＝｛ａ_ij｝，Ｂ＝｛ｂ_ij｝）、Ｑ（４）＝ｑ₃ というようにして、順次、Ｑ＝｛ｑ₁ ，ｑ₁ ，ｑ₂ ，ｑ₃ ，ｑ₃ ｝と求められる。
【００８５】
上記のようにして得られた、第１データセットに基づく結果と、第２から第Ｃデータセットに基づいて求めた結果とをあわせて、次の式により、Ｃ個のデータについての平均を求めることができる。
【数５０】

【００８６】
［ステップ４：筆順違いなどのモデルの作成］
ここまでの学習では、
【数５１】

の数は、認識のカテゴリ数に一致している。例えば、教育漢字８８１文字の認識を行う場合には、モデルの数も８８１個となる。しかし、学習データの中には同じ文字でも異なる筆順で書かれているものや、著しく変形したものなど、同一のモデルに学習させるのは不適当であるものが含まれている。
【００８７】
同一文字に対して、例えば数十セットの学習データがあったとき、いくつ、どのようにしてＨＭＭを作るかは大きな問題である。全データセットにおける筆順と変形を目でチェックして、別のＨＭＭを作るべきか否かを決定するのは不可能に近い。従って、このような決定を自動的に行う方法の検討が必要である。
【００８８】
以下に述べる方法は、各データの持つある種の統計量に基づく自動化された方法で、後に実証してみるように、有効である。
【００８９】
この方法を説明するため、数３０の式を思い起こし、
【数５２】

に注目する。これは、認識評価基準（数３０の式）の対数をとったものである。教育漢字８８１文字の典型的なデータセットに対して、数４８の式をすべてのＨＭＭに対して、Ｔ₁ を横軸にとって、プロットしたのが図８である。
【００９０】
正確には、各文字ごとに一つのデータセットであるので、
【数５３】

などとすべきであるが、記号の煩雑さを避けるため、簡単に表した。注目すべきなのは、数５２の式が、Ｔ₁ に関して、ほぼ完全な直線に乗ることである。
【００９１】
次に述べる手順では、数５２をＴ₁ で割ることにより規格化し、ＨＭＭとc=2,…,Cのそれぞれのｃの値に対するデータセット｛Ｏ_c (t) ^Tc _t=1 ｝とについて、相対的な類似度とも呼べるものを計算し、それをもとに自動的に新しいＨＭＭを作成するか否かを決定する。
【００９２】
すなわち、ステップ１において第１データにより得られたＨＭＭ（隠れマルコフモデル）を
【数５４】

とし、
【数５５】

であるとき、ステップ１の手続きで新たなＨＭＭ
【数５６】

を作ることとする。ここで、r _thは経験的に求められる値である。また、分母のq _N は、第１データセットに基づくものであって、第ｃデータセットによるものではないことに留意されたい。
【００９３】
すなわち、数５５により、分子中の
【数５７】

のＴ₁ に関する傾きと、分母中の
【数５８】

のＴ_c に関する傾きとを比べて、これがあるしきい値r _th以上に異なる場合には、同一文字であっても類似度が低いと判断し、新しいＨＭＭを作成する。
以上説明してきた方法は、Baum-Welchアルゴリズムに見られるような繰り返し計算を必要としないため、短時間で計算することができる。そのため、この方法は、高速ＨＭＭ法と呼ぶことができる。
【００９４】
［高速化］
上述した文字認識方法においては、
【数５９】

の値を全てのＨＭＭについて計算する。具体的には、
【数６０】

とすると、
【数６１】

が得られる。
【００９５】
これをそのまま実行すると、
【数６２】

の順に求まる。これには多くの無駄が含まれている。ここで提案した方法の拘束条件から、 t<iであるとき、α_i (t)=0 であり、t>T-N+i となるとき、α_i (t) はα_N (T) に影響を与えない。
【００９６】
従って、これらの場合は、α_i (t) を計算する必要がない。また、t<i であるときα_i (t)=0 であるので、T<N のとき、α_N (T)=0 である。
【００９７】
このような考察により、計算の量をさらに減少させ、より高速な文字認識が可能となる。この高速化は任意のものであるが、認識処理の時間を短縮するためには、望ましい。
【００９８】
以上説明した文字認識と学習の各ステップの流れが、それぞれ、図９及び図１０に示されている。図９には、文字認識フェーズの全体的な流れが記載されている。図１０には、学習フェーズの全体的な流れが説明されている。
【００９９】
【実施例】
［認識実験］
オンライン手書き文字データベース（農工大kuchibue-d-96-02）（中川正樹ら、「文章形式字体制限なしオンライン手書き文字パターン収集と利用」、信学技報、PRU 95-110, pp.43-48 (1995))を用いて認識実験を行った。図９に、用いた文字データのごく一部の例を示す。ここでは、教育漢字８８１文字のみを対象とした。
【０１００】
学習データとしては、kuchibue-d-96-02のmdb0006 〜mdb0030 と別途用意した教育漢字データ６種類の合計３１種類のデータセットを用いた。学習後に、評価データとしてkuchibue-d-96-02のmdb0001 〜mdb0005 の５種類を用いて、第１候補が正解である認識率と第３位候補までの中に正しい認識結果があったら正解とする認識率（第３位候補率）をそれぞれ計算した。
【０１０１】
その結果を実施例として表１に示す。
【表１】

【０１０２】
極めて高い認識率が得られていることがわかる。教育漢字８８１文字に対して、平均認識率は、８９．３％であり、３位までの累積認識率は、９５．３％となった。ここで、各パラメータの値は、θ^* = ４５度、２４０×２４０のスペースにおいてｌ^* = ８であり。さらに、用いられたスムージング用パラメータの値は、c _a =c_b = ０．８であり、α= ０．９、σ= π／１６であった。量子化のためのｌ₀ は、６０とした。角度の量子化は、Ｌ_M ＝１６にて行った。ここでは、区切りの付与のためのθ₀ は考慮しなかった。すなわち、ペンアップダウンに対応した区切りのみで、角度変化に対応した区切りは入れなかった。また、r _thの値は、０．８であった。
【０１０３】
このようなパラメータ値に対して、すでに報告されている特開平８−１０１８８９号公報に開示されている方法で、上記実施例と同じ文字データセットにより学習させ、同じ文字データセットを認識させた結果は、表１に比較例として示すように、平均認識率が８６．９９％、第３位までの累積認識率は９２．５９％となった。本発明方法では認識率が向上していることがわかる。
【０１０４】
これらの実施例と比較例において用いたプログラムは、ＣおよびＣ⁺⁺により書かれたものであった。上記実施例のプログラムをペンティアム１２０ＭＨｚのＤＯＳ／Ｖマシンにおいて、ＭＳ−ＷＩＮＤＯＷＳ３．１上で走らせた結果、８８１文字の教育漢字（ｍｄｂ０００１）の認識を８分５４秒で完了することができた。同じプログラムがＷＩＮＤＯＷＳ９５においては約３倍の速度で動くことがわかっているので、ＷＩＮＤＯＷＳ９５上では、約３分で認識が完了するものと考えられる。これは、上述の高速化を行ったものである。これに対し、比較例による同様の文字認識は、ＷＩＮＤＯＷＳ９５上で平均１５分程度かかった。本願発明の方法は、従来技術による方法より認識速度が相当程度向上していることがわかる。したがって、本発明の方法は、より安価で、消費電力の少ないシステムにおいても稼働させることができる。
【０１０５】
【発明の効果】
上述のように、本願発明の方法によれば、これまで認識が困難であった続け字や筆順違いの文字の認識率が向上すると同時に、勾配の計算と山登りを反復して行って最尤状態を求める方法におけるような、膨大な計算量と局在最大値による結果の不安定性を避けることができる。また、認識速度が向上するので、より簡易なシステムにおいても、高速に文字認識を行うことができる。
【図面の簡単な説明】
【図１】三つのデータ点とΔθ_i (i=1,2) の定義を示す図である。
【図２】四つのデータ点とΔθ_i (i=1,2,3) の定義を示す図である。
【図３】図２と同様であるが、Δθ₃ がしきい値θ^* よりも大きい様子を示す図である。
【図４】「木」という字の手書き生データの例を示す。
【図５】図４の生データに前処理を施したデータを示す。
【図６】方向の量子化のパターンの例を示す。
【図７】数４４のｆ（θ）の概形を示す。
【図８】ｌｏｇＰの分布をＴの関数として示す。
【図９】本発明の実施例による認識フェーズのフローチャートである。ここで、ＨＭＭは、「隠れマルコフモデル」を表す。
【図１０】本発明の実施例による学習フェーズのフローチャートである。ここで、ＨＭＭは、「隠れマルコフモデル」を表す。
【図１１】認識実験において用いた手書き文字データ（kuchibue-d-96-02）の例を示す。

Claims (8)

1. 隠れマルコフモデルを用いた、手書き文字の筆跡の座標の移動と入力用ペンの入力装置表面に対するアップまたはダウンの状態を表す時系列データに基づくオンライン手書き文字認識方法であって、
   与えられた時系列データから、その時系列データに含まれる隣り合うデータ点の間をつなぐ第１と第２の線分の間の角度または線分の長さが所定のしきい値以上であるか、未満であるかに基づいて、しきい値以上であれば、その第１の線分をつなぐデータ点を特徴点として抽出し、しきい値未満であればその線分をつなぐデータ点を特徴点としないことで、角度情報と距離情報とに基づいて特徴点を抽出して、該時系列データを圧縮する特徴点抽出・データ圧縮ステップと、
   該特徴点を結ぶ隣り合う線のなす角度を量子化し、その線の長さを量子化された角度の繰り返しの数として表現した一次元のデータと、該ペンのアップまたはダウンとに応じた二値の一次元データとを含む二次元の時系列データを作成する量子化ステップと、
   この時系列的なデータに、ペンアップとペンダウンの状態変化に基づいて、あるいはペンアップとペンダウンの状態変化および上記角度に関する所定の条件に基づいて区切りを入れて、区切りに挟まれたデータの１個の集まりを隠れマルコフモデルにおける１個の状態に対応させる対応ステップと、
   この量子化され区切られた時系列的なデータについて、認識すべき文字に対応して予め求められた複数の隠れマルコフモデルのもとで、該データが得られる確率を計算する確率計算ステップと
   を含み、
   該確率が最大になる隠れマルコフモデルに対応する文字を最も確からしい文字とする文字認識方法。
2. 隠れマルコフモデルにおけるＮ個の状態の間で状態ｊから状態ｉへの遷移確率a_ijをｉ＝ｊとｉ＝ｊ＋１以外の場合には、ゼロに拘束し、さらにa_NNを１に拘束し、初期状態をq_iに固定することを特徴とする請求項１に記載の文字認識方法。
3. 学習フェーズにおいて、隠れマルコフモデルにおける状態間の遷移確率a_ijを、１に拘束するa_NNを除いて、上記区切りに挟まれたデータの集まりのそれぞれにある上記量子化されたデータの記号列の数に基づいて得ることを特徴とする請求項２に記載の文字認識方法。
4. 学習フェーズにおいて、上記区切りに挟まれたデータの集まりそれぞれにある上記量子化されたデータの記号列の数に基づいて、隠れマルコフモデルにおける各状態からの出力確率を得ることを特徴とする請求項２または３に記載の文字認識方法。
5. 学習フェーズにおいて、限られた数のデータを学習に用いて生じる過度のオーバーフィットを避けるため、上記遷移確率及び出力確率に対してスムージング処理を行うことを特徴とする請求項１から４のいずれかに記載の文字認識方法。
6. 認識フェーズにおいて、全ての状態に対する完全な周辺化は行わず、最終時刻における状態を隠れマルコフモデルの最後の状態に拘束して、隠れマルコフモデルに対するある時系列データの確率を計算することを特徴とする請求項１から５のいずれかに記載の文字認識方法。
7. 学習フェーズにおいて、同一文字に対して複数セットの学習用データがあるとき、第１データセットにより作成した第１隠れマルコフモデルの第１データセットのデータに対する確率を、全ての状態に対する完全な周辺化は行わず最終時刻における状態を隠れマルコフモデルの最後の状態に拘束して計算し、該確率の対数値を該データ列の時間の最終値で除して、第１除算結果を得て、また、第１隠れマルコフモデルの第２データセットのデータに対する確率を、全ての状態に対する完全な周辺化は行わず最終時刻における状態を隠れマルコフモデルの最後の状態に拘束して計算し、該確率の対数値を該データ列の時間の最終値で除して第２除算結果を得て、ついで、第１除算結果を第２除算結果で除算して得られる値が、所定の正のしきい値より大きい場合に、該第２データセットのデータに基づいて、第２の隠れマルコフモデルを作成することを特徴とする請求項１から６のいずれかに記載の文字認識方法。
8. 請求項１から７のいずれかに記載の文字認識方法を実施するためのコンピュータプログラムを記憶させた記憶媒体。

Images