(57)【要約】【課題】シンボル化の問題を回避し、アナログ的に構造を表現し、標準との柔軟かつ単純なマッチングが行えるようにする。【解決手段】手書き文字列を各画毎にパラメータ表現でとらえ、各画毎に折れ線近似し、折れ線近似された各折れ線を、始点から終点のベクトルとして、基準となる軸と各折れ線とのなす角度を折れ線角系列として求め、得られた折れ線の各頂点の外角系列を求め、外角系列の＋又は−が連続する同符号の外角の和を巻き角系列とし、求められた各系列による特徴抽出を基に、基準となる点であるノードを求め、そのノードの点としての属性とノード間の辺としての属性よりグラフ表現を与え、始点と終点を特に規定しない開いたマスク構成のテンプレートとのマッチングで、普通の上下、左右の関係を保持した文字に対しても、また回転不変を求められる場合においても、柔軟で、端のノイズや変形に強い頑健な認識を行う。【選択図】図１
2008046825.tif 000002
【特許請求の範囲】
【請求項１】
オンライン手書き文字を認識する手書き文字認識方法において、
入力された手書き文字列を、各画毎にパラメータ表現でとらえ、各画毎に折れ線近似を行い、
その折れ線近似された各折れ線を、始点から終点にいたるベクトルとして、基準となる軸と各折れ線とのなす角度を折れ線角系列として求め、
得られた折れ線の各頂点の外角系列を求め、
前記外角系列のプラス又はマイナスの同じ符号が連続する同符号の外角の和を、巻き角系列とし、
前記求められた各系列による特徴抽出を基にして、基準となる点であるノードを求め、そのノードの点としての属性とノード間の辺としての属性により、グラフ表現を与え、
始点と終点を特定しない開いたマスク構成によるテンプレートとのマッチングにより、普通の上下、左右の関係を保持した文字に対しても、また回転不変を求められる場合においても、柔軟で、端のノイズや変形に強い頑健な認識を行うことを特徴とする
文字認識方法。
【請求項２】
請求項１記載の文字認識方法において、
始点、終点、９０度の整数倍の巻き角を与える点、巻き角が変化する点をノードとし、ノードの点としての属性とノード間の辺の属性によりグラフ表現を与え、始点、終点を特定しない開いたマスク構成によるテンプレートとのマッチングにより、回転不変な認識手段を特徴とする
文字認識方法。
【請求項３】
請求項１記載の文字認識方法において、
回転不変が要求されない、通常の文字形の認識のために、上下の凹凸、左右の凹凸をノードとし、そのノードの点としての属性とノード間の辺としての属性により、グラフ表現を与え、始点と終点を特に規定しない開いたマスク構成によるテンプレートとのマッチングにより、文字認識を行うことを特徴とする
文字認識方法。
【請求項４】
請求項１記載の文字認識方法において、
複数の文字又は記号が包含関係にある場合には、定量的に整合部分が長い文字又は記号を優先することを特徴とする
文字認識方法。
【請求項５】
請求項１記載の文字認識方法において、
連続した文字列文字を認識と同時に切り出して認識を行うことを特徴とする
文字認識方法。
【請求項６】
オンラインの手書き文字を認識する手書き文字認識システムにおいて、
手書き文字がオンラインで入力される入力手段と、
入力された手書き文字列を、各画毎にパラメータ表現でとらえ、各画毎に折れ線近似を行う折線近似手段と、
前記折線近似手段で折れ線近似された各折れ線を、始点から終点にいたるベクトルとして、基準となる軸と各折れ線とのなす角度を折れ線角系列として求め、得られた折れ線の各頂点の外角系列を求め、前記外角系列のプラス又はマイナスの同じ符号が連続する同符号の外角の和を、巻き角系列とする処理手段と、
前記処理手段で求められた各系列による特徴抽出を基にして、基準となる点であるノードを求め、そのノードの点としての属性とノード間の辺としての属性により、グラフ表現を与え、始点と終点を特に規定しない開いたマスク構成によるテンプレートとのマッチングにより、普通の上下、左右の関係を保持した文字に対しても、また回転不変を求められる場合においても、柔軟で、端のノイズや変形に強い頑健な認識を行うステップとを備えることを特徴とする
文字認識システム。
【請求項７】
オンライン手書き文字を認識する手書き文字認識プログラムにおいて、
入力された手書き文字列を、各画毎にパラメータ表現でとらえ、各画毎に折れ線近似を行うステップと、
その折れ線近似された各折れ線を、始点から終点にいたるベクトルとして、基準となる軸と各折れ線とのなす角度を折れ線角系列として求めるステップと、
得られた折れ線の各頂点の外角系列を求めるステップと、
前記外角系列のプラス又はマイナスの同じ符号が連続する同符号の外角の和を、巻き角系列とするステップと、
前記求められた各系列による特徴抽出を基にして、基準となる点であるノードを求め、そのノードの点としての属性とノード間の辺としての属性により、グラフ表現を与えるステップと、
始点と終点を規定しない開いたマスク構成によるテンプレートとのマッチングにより、普通の上下、左右の関係を保持した文字に対しても、また回転不変を求められる場合においても、柔軟で、端のノイズや変形にも強い頑健な認識を行うステップとを備えたことを特徴とする
手書き文字認識プログラム。
【請求項８】
記憶されたプログラムを所定の演算処理装置に実装させることで、オンラインの手書き文字認識が可能な記憶媒体において、
記憶媒体に記憶されたプログラムとして、
入力された手書き文字列を、各画毎にパラメータ表現でとらえ、各画毎に折れ線近似を行うステップと、
その折れ線近似された各折れ線を、始点から終点にいたるベクトルとして、基準となる軸と各折れ線とのなす角度を折れ線角系列として求めるステップと、
得られた折れ線の各頂点の外角系列を求めるステップと、
前記外角系列のプラス又はマイナスの同じ符号が連続する同符号の外角の和を、巻き角系列とするステップと、
前記求められた各系列による特徴抽出を基にして、基準となる点であるノードを求め、そのノードの点としての属性とノード間の辺としての属性により、グラフ表現を与えるステップと、
始点と終点を規定しない開いたマスク構成によるテンプレートとのマッチングにより、普通の上下、左右の関係を保持した文字に対しても、また回転不変を求められる場合においても、柔軟で、端のノイズや変形に強い頑健な認識を行うステップとを備えたことを特徴とする
記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オンライン手書き文字認識を行う手書き文字認識方法及び手書き文字認識システム、並びにその認識方法を実現する手書き文字認識プログラム、さらにそのプログラムを格納した記憶媒体に関する。
【背景技術】
【０００２】
今までに多数の文字認識システムが提案され、実用化さているが、その基本原理には二つの立場があり、一つは構造解析の立場、もう一つはパターンマッチングの立場であり、前者は一般にはその認識システムは軽く、したがって、入力制限の強い場合、即ち、画数、筆順一定、または、どちらかを一定にした対象に適応され、他方後者は両者、画数、筆順を自由にした場合かそれに近い場合に適用されてきた。
【０００３】
構造解析の立場としては、電子通信学会論文誌，56−D，5，pp．312−319，“手書き数字・片仮名文字のオンライン実時間認識”や日本国特許庁発行の特開昭５９−１３１９７２号公報にあるように、基本ストローク方式と呼ばれているものがあり、ストロークを単純ストローク（４種）、複合ストローク（７種）に分類し、識別オートマトンにより認識するものであり、簡単ではあるが、辞書の作成、続け字や、略字に対処するのに問題があり、その発展性に問題があるとされてきた。
【０００４】
パターンマッチング法は大きく分けて２種類の方法がある。一つは、電子情報通信学会論文誌，J63−D，2，pp．153−160，“ストロークの点近似による手書き文字のオンライン認識”にあるように、ストロークを少数の点で近似しそれらを特徴点として、また端点での筆の運動方向を推定し、それらも特焦点とし、特徴ベクトルを構成する。辞書はストロークに分解され、それらが同様に特徴ベクトルをもち、入力ベクトルと各カテゴリ毎に用意された特徴ベクトルとの対応をとり、対応がとれた辞書について距離が計算され、最小の距離を与える辞書名が認識された文字名であり、基本的に筆順，画数に対し自由である。
【０００５】
もう一つのパターンマッチング法があり、特徴点の対応方式の原論文として、電子通信学会研究会論文PRL74−20）に記載された“Rubber String Matching法による手書き文字認識”があり、また日本国特許庁発行の特開昭５７−４５６７９号公報及び特開平８−２４９４２号公報に在る如く、入力文字と辞書の特徴点ベクトルをＤＰ（Dynamic Programming）方式により対応をとるものであり、これが手書き文字のオンライン認識の主流をなしている。
【０００６】
なお、最近はオフラインの文字認識技術をオンラインに適用されるようになってきた。
それは、今まで蓄積されてきたＯＣＲ技術があり、これはオンライン文字認識にも使える。
この立場から、ＯＣＲ技術を見ると、主流は方向特徴マッチングである。これについては膨大な文献があるが、基本的考え手法は、例えば原論文として、［電子情報通信学会論文誌，J62−D，3，pp．217−224，“文字認識のための相関法の一改良”］にある。この方法と構造解析の方法と根本的に異なる点は、特徴は一般にｎ×ｍの格子平面に割り付けられ、この平面上の特徴分布が最終の入力文字の表現とし、ｎ×ｍを例えば左隅から右に走査し、ｎ×ｍ次元のベクトルとする。識別は標準方向特徴ベクトルと入力文字方向特徴ベクトルとの内積（類似度）を計算し、その値の最も高い標準方向特徴ベクトルのカテゴリ名を答えとするものである。この際、特に変形の著しい手書き文字では、高度な非線形正規化の前処理が行われる。これが必要なのは、この方法がｎ×ｍの格子平面を基本的枠組みにしているからである。この手法の利点は一般にはベクトル空間、特に内積の定義されているヒルベルト空間論が適用されうるので、高度な識別理論が援用されることである。また実用的に言えばノイズに強い。しかし、せっかくのオンラインの最大の利点、セグメンテーションの容易さを殺している。オンラインでは、例えば同じ場所に何個も文字を書いても機械は認識できるようにすることが可能である。また、本当に著しい変形に対しては高度な非線形正規化といえども不十分であるし、例えば回転変形には、相当に高度で、かなりの計算量の正規化が必要である。［S．Mori，H. Nishida，H．Yamada，Optical Character Recognition，Wiley］の第3章に詳しい記述がある。
【０００７】
さて上の特徴として、例えば曲率をとることも可能である。この観点から、［電子情報通信学会論文誌，J62−D，3，pp．217−224，“文字認識のための相関法の一改良”］では特に筆記体の「ｇ」、「ｙ」、それにアラビア数字「９」が手書き文字では間違い易いということから、回転特徴と名づけて、湾曲部の接線角度差を求め、適当な量子化を行い、文字を従来の方向特徴ベクトルと局所的な回転特徴ベクトルで表現し、それらをまとめた全特徴ベクトルを求め、ぼかし処理を行う（これは実際には格子平面上で行う）。それぞれのカテゴリにつきぼかし全特徴標準ベクトルを求め、類似度計算を行い、答えを出す方法が提案されている。ところで、構造解析の立場では、筆記体の「ｇ」、「ｙ」と、アラビア数字「９」とはかなり異なる。それは上部の構造を陽に見ているからである。しかし、特徴マッチングでは、内積の過程で混ぜ合わされて一個のスカラー量にしてしまうので、上部構造は陰に見ることになり、三文字とも強度の直線構造があることから、この直線に埋没されてしまう。それでわざわざ、局所特徴面を用意したのである。しかし、後で述べるように、われわれの方法では、上で回転特徴と言われるものが、局所的ではなく、大域的に求められ、一貫した形で、自然に容易に表現される。したがって、上の3種の文字は非常に簡単に認識可能である。
【０００８】
図形，物流システムに置かれた物体，軍事では飛行機など、回転に不変な認識システムは広範囲の対象に対し要求されている。
【０００９】
したがって、昔から研究は行われ、多くの論文が現在もなお発表されている。１９９０年までの研究については、森 俊二，坂倉 栂子共著の画像認識の基礎（II））に詳しく述べられており、また１９９９年までの研究は、S．Mori，H.Nishida，H．Yamada著Optical Character Recognitionに詳しい記述があり、この研究の主流はモーメント法であり、高次のモーメントを位相角が相殺するように組み合わせるものであり、またフーリエ記述子なる名前で呼ばれているフーリエ変換法の応用があり、これは最近のPCが非常に高速になったことを反映して、研究自体は盛んになっているものの、実用としてはいまだ市場に現れていないが、一方この流れとは別に、情報処理学会論文誌第２７巻第5号：１９８６年5月，“画数，筆順，回転，区切りによらないオンライン手書き図形認識方式”にあるように対象を直線線分，弧の系列で近似し、それらの相対的角度変化で表現し、辞書の同様な表現との対象（入力図形）対応をとり、それぞれの角度変化の差の絶対値の和でお互いの距離を測って回転不変な方式としているが、鋭角の検出に弱いという欠点が論文自体の中で述べられている。
【００１０】
いわゆるマッチング方式は文字の置かれた、二次元平面上の特徴（例えばストロークの方向）マッチングである。またオンライン手書き文字認識ではいわゆるＤＰ（Dynamic Programming）マッチング、別名弾性ストリングマッチングである．前者に置いては、二次元上の特徴の分布を、ベクトル表現し、文字間の距離をこれらベクトルの内積として定義し、内積の定義された、ベクトル空間上の識別問題として、統計的手法で文字認識を行う。後者では、単純な重ね合わせのマッチングを拡張し、入力文字が標準文字に対し適応的、柔軟に、マッチングさせることにより文字認識を行うものである。
【００１１】
このような手法に対し、一般には構造解析的手法と呼ばれる文字認識法が研究されてきた。これは一般図形に対しても適用可能で、良い方法であるが、対象の、具体的には文字ストロークの記号化を必要とし、シンボルによるマッチングがなされてきた。しかし、このシンボル化するところに問題があり、シンボル化で柔軟性を失い、また設計が機械的に行かず、研究，開発が行き詰まっている。例えば上述した［電子通信学会論文誌，56−D，5，pp．312−319，“手書き数字・片仮名文字のオンライン実時間認識”］が発表されたのは古く１９７３年である。この段階で、オンライン文字の右回り左回りが特徴として使用されているが、これらの系列は全てシンボル化されている。これらは入力パターンのX-座標値の増減で検出され、11個のシンボルで、表現されている。このようなシンボル表現は柔軟性にかけ、実際特別な場合として部分的にしか使用されていない。その後構造解析的手法は１９８１年に電子通信学会論文誌 J64−D，8，ｐ705−712，“形の代数的構造表現”で統一的な観点を与える代数的な考えが導入され，１９９２年にIEEE Trans. on Pattern Analysis and Machine Intelligence Vol. 14,No.5,pp. 1029-1058,“Algebraic Description of Curve Structure”で実用的な代数的システムが構築されたが、依然としてシンボル表現であった。この様に構造解析的手法はシンボル表現水準に留まってきた。この壁を突破するには、シンボルでなく、アナログにしなければならないと言うこと自体は学会で、よく言われてきたのであるが、いままで、このアナログ化の具体的な方法が見付からなかった。
【００１２】
ところが、上記の従来技術では，下記のような基本問題がある。
構造解析は簡単であるが、柔軟性がなく、基本パターンの境が問題で、離散的で、ぎこちなく、辞書の作成に手間がかかる。
パターンマッチング法、特にＤＰ方式は処理が重たい。
パターンマッチング法はオフライン認識も含め、ただ読むだけ、すなわち入力文字を強引に辞書に当てはめることが主たる目的であり、原因結果の対応が見えず、時として理解に苦しむ誤読をきたし、その原因が設計者にもわからないことが珍しくない。
【００１３】
以上、単文字の認識について述べてきたが、連続的に書かれた、例えば筆記体の文字列に対し、これを効率よく認識する方法について以下に述べる。これにも、様々な技術が提案され、実用化されているが、それらは、大きく「セグメント方式」と「ホリスティック方式」という二つの方式に分けられる。
【００１４】
「ホリスティック方式」とは、文字列があたかも単独文字で在るかのごとく見て、全体として認識する方法である。しかし、この問題点は、テンプレートの数が、非常に大になることである。英単語の場合、５万個が少なくとも必要である。
【００１５】
一方、「セグメント方式」は、文字列を構成するそれぞれの文字を切り出し、認識するので、このような問題はない。しかし、問題はセグメント/切り出しをいかに行うかであり、これは昔から難問として知られている。（１９９５年までの研究を系統的かつ詳細に紹介したものとして、Richard G. Cassy と Elic Lecolinetによる論文がある：IEEE Transactions on Pattern and Machine Intelligence, Vol.18,  No.7, July 1996, pp690-706）。
【００１６】
この難問には、大きく分けて、２通りの解決方法がある。一つは、さまざまな特徴を用い、文字の切り出しを先に行い、それからこの切り出された文字を認識する方法である。これは「切断法」と呼ばれ、古典的な方法で、主に対象は印刷文字列などに用いられる。このような対象では文字間に若干の隙間があり、そのような隙間を対象のX軸上への濃度の射影などから検出する。しかし、文字が全体として傾く場合には、濃度の射影は無効となるので、傾きを正規化する必要があり、「切断法」には基本的に限界がある。
【００１７】
二つ目は、認識と切り出しを同時に行う「認識に基づく方法」である。即ち、文字を切り出す手段として、文字の認識を利用するものである。
【００１８】
最初の考えは、1962年に出されたもので、一つの窓枠を文字列の始めから連続的に走査し、連続的にその窓枠内の文字を認識していく方法である。しかしこの方法は、例えば「Ｗ」は２個の「Ｖ」と認識されてしまう。そこで、文字列全体を考え、考えられる範囲の窓枠列を想定し、それら窓枠内で認識される文字列を、全体として評価する方法が考えられた。このさい、組み合わせが大になるので、効率良い計算法として、ＤＰ（Dynamic Programming）法が採用された。この方法は、V.A.Kovalevsky により発表されたもので、”Character Readers and Pattern Recognition,” Washington, D.C., Spartan Books,1968,にある。
【００１９】
そこでは、例として、非常に劣化したタイプ文字、「Ａ」「Ｎ」「Ｈ」の３文字を取り上げている。文字列はロシヤ文字を想定する。この文字列を連続的に走査すると、「Ｎ」と「Ｈ」のセリフ（欧文活字の飾り）のため、ＮＨの中間に「Π」なる文字（ロシヤ文字）も認識検出されてしまう。しかし、これは文字列全体としては認識評価が低いため、Ａ、Ｎ、Ｈの３文字が文字列全体として認識評価される。すなわち、正しい切り出しと、認識が同時に行われることになる。
【００２０】
この考えは、革新的であったが、長い間、注目されなかった。この手法の再発見は、ＩＢＭに所属していたRichard G. Cassyである（上述の論文の執筆者の一人）。彼とN.Nagyは、この考え方に立って、再帰的切り出し法なる新しい方法を提案した。
【００２１】
例として挙げられているのは、やはり劣化したタイプ文字「ｒ」「ｍ」でｒとｍは完全につながっている。最初、窓枠は全文字例が含むようにとられる。この場合、「ｒｍ」である。その文字枠内にある文字例を認識し、認識できればそれで良い。これで終わりである。しかし認識出来なければ、右端から窓枠を狭めて行き、そこで認識を行い、窓枠内とその残部が認識できればそれで良い。「ｒｍ」の例ではこの段階で「ｒ」、「ｍ」と認識され、これで終了である。この方法は“Recursive Segmentation and Classification of Composite Patterns,”Proc.,Sixth International Conference on Pattern Recognition ,p.1923,1982.”に記載されている。
【００２２】
さて上述した方法は、オフラインの文字認識で、マッチングの流れはＸ軸上でその正の方向である。これが、マッチングの自然な軸を形成する。また、マッチングは濃度レベルの内積をとるものである。この点、局所的特徴を、平行移動に不変な、ｎ次自己相関法を基礎に２５種類の３×３のマスクで構成し、Ｘ軸に垂直な１×Ｍ（Ｍは文字枠の高さ）の窓を走らせ、これらの特徴を検出、それらのヒストグラム分布から、適当に設計された識別関数で、対象を認識する手法が提案された。これは主に大津による発明であり、米国特許が取得されている。
【００２３】
特許文献１は、上述した大津などによる米国特許である。
【特許文献１】米国特許４２８８７７９号
【発明の開示】
【発明が解決しようとする課題】
【００２４】
しかし、これらの方式は、いずれも複雑で、性能という面では実用的な水準を十分に満たしているとは言いがたいのが実情である。
柔軟な構造的マッチングとしては、文字認識よりは、むしろ情景認識の分野で、広く、研究がなされた。しかし、それらは２次元上の特徴の配置と、それらの関係を一般的に表現する２次元グラフ上でのマッチングであった。これに関しては、実に膨大な研究がある。
【００２５】
一方、オンライン文字認識では、人間が見てのイメージは２次元であるが、厳密に時間軸上に乗っていて、１次元である。すなわち、単なる１次元の線形グラフで表現できるのである。この観点が、問題を劇的に単純化するのである。しかも、巻き角により、時間軸上に、自然な切り出し候補点が陰に陽に整列している。この巻き角と線形（１次元）グラフとが、本件発明の核心となる。
【００２６】
本発明はかかる点に鑑みてなされたものであり、基本的には上に述べた構造解析的手法に属し、しかし、今までの問題点を克服し、柔軟な構造解析的手法の基礎を与えるものであり、それ故、シンボル化の問題を回避し、アナログ的に構造を表現し、標準との柔軟かつ単純なマッチングを行うことを目的とする。
【課題を解決するための手段】
【００２７】
本発明は、オンライン手書き文字を認識する場合において、入力された手書き文字列を、各画毎にパラメータ表現でとらえ、各画毎に折れ線近似を行い、その折れ線近似された各折れ線を、始点から終点にいたるベクトルとして、基準となる軸と各折れ線とのなす角度を折れ線角系列として求め、得られた折れ線の各頂点の外角系列を求め、外角系列のプラス又はマイナスの同じ符号が連続する同符号の外角の和を、巻き角系列とし、求められた各系列による特徴抽出を基にして、基準となる点であるノードを求め、そのノードの点としての属性とノード間の辺としての属性により、グラフ表現を与え、始点と終点を特に規定しない開いたマスク構成によるテンプレートとのマッチングにより、文字認識を行うものである。
【発明の効果】
【００２８】
本発明によると、オンライン手書き文字を認識する場合に、普通の上下、左右の関係を保持した文字に対しても、また回転不変を求められる場合においても、柔軟で、端のノイズや変形に強い頑健な認識を行い、また連続した文字列においても、それらを前処理として切り出すことなく、孤立して書かれている文字の認識法と同じ方法で認識を行うことができる。
【発明を実施するための最良の形態】
【００２９】
以下、本発明の一実施の形態を、添付図面を参照して説明する。
【００３０】
本実施の形態の例においては、オンライン手書き文字認識を行うシステムに適用してあり、図１には、各処理部をハードウエア構成とした場合の構成例を示してある。なお、図１に示すように各処理部を共通の演算処理部で実行する構成としてもよく、或いはパーソナルコンピュータ装置などの汎用の演算処理装置に、本例の手書き文字認識をプログラム化したものを実装させて、同様の手書き文字認識が行われるようにしてもよい。
【００３１】
また、以下の説明においては、本例での手書き文字認識に必要な概念を、次の表１に示す用語で定義している。
【００３２】
【表１】
2008046825.tif 000003
【００３３】
図１に示した構成について説明すると、紙１の上で、ペン２で文字を書くことで、その紙１の上の運筆（筆跡）１ａをペン２側で検出する。その運筆１ａの検出は、例えばペン２に内蔵されたカメラにより行う。或いは、加速度センサなどからペン２自体の動きを検出するようにしてもよい。さらに、ペン側で検出するのではなく、紙１の側を何らかのパネルで構成して、電気的に筆跡を検出できる構成としてもよい。いずれにしても、本例の場合にはオンライン手書き文字認識であるので、時間の経過による筆跡の変化を判断できる構成としてある。
【００３４】
これらの処理で検出された筆跡のデータは、入力処理部３に送られ、文字情報を検出するための入力処理が行われる。入力されたデータは、以下、折れ線近似部４、特徴抽出部５、識別部６、識別結果出力部７に送られて、それぞれの処理部で対応した処理が行われて、最終的に、識別結果出力部７で、識別された文字の表示や、識別された文字コードの出力などの出力処理が行われる。識別された文字コードに基づいた、識別文字の表示或いは印刷を行うようにしてもよい。
【００３５】
図２のフローチャートは、本例の文字認識の全体の処理例を示したものである。以下、図２に従って説明すると、入力処理部３から入力された文字／図形パターンは（ステップＳ１１）、折れ線近似部４で折れ線近似される（ステップＳ１２）。この近似から、入力パターンは、各折れ線をベクトルと見た時の、長さ、方向角、隣接する折れ線の方向角の差を要素とするベクトルとして表現される（ステップＳ１３）。また、方向角の差のベクトル表現から、同符号の角の差の和を求め、符号を含め一つの要素として、ここで巻き角と名づけたベクトル表現が求められる。次に、特徴抽出部５で折れ線近似表現から、状況に応じて、特徴が抽出され（ステップＳ１４）、その特徴の抽出結果に基づく１次元の線形グラフ表現を与え、（ステップＳ１５）、そのグラフ表現と始点、終点を特に規定しない開いたマスク構成によるテンプレートとのマッチングにより、文字認識が行われ（ステップＳ１６）、文字認識結果が出力される（ステップＳ１７）。
【００３６】
ここで、ステップＳ１６での文字認識処理の詳細の例を、図３のフローチャートを参照して説明する。まず、入力されたグラフ表現の各ノード形状の並びが一致していることがチェックされる（ステップＳ２１）。そして、ノードの点としての属性の一致がチェックされ、（ステップＳ２２）、続いて、ノード間の辺（エッジ）の属性の一致がチェックされる（ステップＳ２３）。最後に、交点の有無、ノード間距離関係などのその他の属性の一致がチェックされて（ステップＳ２４）、識別される。これらのチェックの結果で全てが一致している場合に、認識結果がＯＫとなり（ステップＳ２５）、１つでも一致しない場合に排除される（ステップＳ２６）。
【００３７】
本実施の形態における認識手法においては、基本的には上に述べた構造解析的手法に属し、しかし、今までの問題点を克服し、柔軟な構造解析的手法の基礎を与えるものである。それ故、シンボル化の問題を回避し、アナログ的に構造を表現し、標準との柔軟かつ単純なマッチングを行うものである。また構造解析を行うので、必然的に対象を適格に記述することが出来て、原因結果の対応が人間の視覚からみて明確である。従って、文字などの対象の形の評価が出来て、正しい拒否範囲を設定でき、より人間に近い能力をもつ認識システムを提供することができる。
【００３８】
ここまでは、本願の発明者が先に提案した構造解析的手法と基本的に同じである。加えて、連続した文字列（例えば筆記体など）において効率的な文字認識を行う上でも、本方式は非常に便利にできている。本発明では、巻き角により、時間軸上に、自然な切り出し候補点が陰に陽に整列していることに着目し、入力された文字列に対し、その候補点（ノード）とノード間の辺（エッジ）の属性を用いた1次元の線形グラフ表現を与え、認識と同時に切り出し（「切り出し認識」）を行い、前処理としての切り出しを行うことなく、孤立して書かれている文字の認識法と同じ方法で認識を可能とするものである。
【００３９】
本発明の効果を説明する上で、連続した文字列の認識から入ることがわかりやすいので、図４にある具体的な数字列の認識法の説明から入る。これは「８８８」である。これらの各文字は繋がっている。したがって、従来の文字認識では、これらの文字を、切り出して、それぞれ認識システムに送る必要があった。この処理は「切り出し前処理」と呼ばれる。しかし、本方式では、この「切り出し前処理」が不要であり、認識と切り出しを同時に行う。これを以下に説明する。
【００４０】
図４のイメージは、左から書かれたものであるが、これらの基本の表現は、連結する各折れ線の長さ、折れ線角、隣り合う折れ線の角から構成される外角、そして同一符号の外角を足し合わせた、巻き角を要素とする、長さ系列、角系列、外角系列、巻き角系列である。
【００４１】
そこで、これらを素材として、「切り出し認識」に適した一次元のグラフ表現に変換する。ここでの、グラフは最も簡単な線形グラフである。図４の最初の「８」の部分を敢えて切り出した図５を実例として、以下に記す。ここでは、始点、終点、９０度の整数倍の巻き角を与える点（±ｎ×９０度長点）、巻き角の符号が変化する点を「ノード」とし、ノードの属性としてその点の外角（△）と、そのノードが属する巻き角領域の巻き角値（Θ）、またノード間の辺（エッジ）の属性として、ノード間にある折れ線群における外角の絶対値の最大値（最大|Δ|）を用い、グラフ表現を与える。
【００４２】
ここで、<0> [  ｓ  ]、<1> [  −  ]、<2> [ −＋ ]、<3> [  ＋  ]、<4> [  ＋  ]、<5> [  ＋  ]、…<28> [  ｅ  ]  はこのグラフのノード番号と、それらの、特性を表現したシンボルである。<0> [  ｓ  ]  から始まり、<28> [  ｅ  ]で終わる。[  ｓ  ]、[  ｅ  ]はそれぞれ、スタート、エンドのシンボルである。<1> [  −  ]は、外角（Δ）系列で最初の巻き角−９０度点である。巻き角は離散的であるが、線形補間しているので、一般にα度長点として、アナログ的に求めることが出来る。<1> [  −  ]の「−」は左周りという、巻き角の符号を表現している。
【００４３】
＜図５のグラフ表現＞
<0> [  ｓ  ] 0 ( 326, 121 ), Θ = -172.83
↓
↓ 折れ線数(0〜4) = 4, 長さ = 0.07, 最大|Δ| = |-24.52|
↓
<1> [  −  ] 4 ( 156, 121 ), Θ = -172.83, Δ = -33.26
↓
↓ 折れ線数(4〜6) = 2, 長さ = 0.09, 最大|Δ| = |-72.64|
↓
<2> [ −＋ ] 6 ( 347, 279 ), Θ(-) = -172.83, Θ(+) = 304.42, Δ(-) = -72.64, Δ(+) = 21.27
↓
↓ 折れ線数(6〜8) = 2, 長さ = 0.02, 最大|Δ| = |45.06|
↓
<3> [  ＋  ] 8 ( 365, 346 ), Θ = 304.42, Δ = 49.31
↓
↓ 折れ線数(8〜12) = 4, 長さ = 0.07, 最大|Δ| = |30.07|
↓
<4> [  ＋  ] 12 ( 195, 329 ), Θ = 304.42, Δ = 20.39
↓
↓ 折れ線数(12〜15) = 3, 長さ = 0.03, 最大|Δ| = |35.79|
↓
<5> [  ＋  ] 15 ( 194, 258 ), Θ = 304.42, Δ = 38.45
↓
↓ 折れ線数(15〜16) = 1, 長さ = 0.05
↓
<6> [ ＋− ] 16 ( 330, 205 ), Θ(-) = 304.42, Θ(+) = -56.33, Δ(-) = 38.45, Δ(+) = -56.33
・
・
・
＜28>[  ｅ  ]
【００４４】
<1> [  −  ]、すなわち「−９０度点」は、５番目の頂点を少し越えたところにある。そこで、このノードの点の属性として、これが属する巻き角系列（Θ = -172.83）とこれに最も近い時間的に前の頂点（この場合５番目の頂点）の外角（Δ）値、Δ = -33.26を与える。また、巻き角の境界を示す<2> [ −＋ ]が重要である。これはすなわち、巻き角（−）から巻き角（＋）へ変化した点である。巻き角の境界は点ではなく、1個の折れ線を共有する。その共有する折れ線の、時間軸のプラス方向にある先端をノードとしている。この点の属性は、Θ(-) = -172.83, Θ(+) = 304.42, Δ(-) = -72.64, Δ(+) = 21.27である。すなわち、時間的に変化する前の巻き角Θ(-) = -172.83と、時間的に変化後の巻き角Θ(+) = 304.42、それと共通の折れ線の両端の外角（Δ）値、Δ(-) = -72.64, Δ(+) = 21.27である。
【００４５】
<2> [ −＋ ]以降、折れ線系列は巻き角（＋）の領域に入る。この最初が<3> [  ＋  ]で、これは９０度長点である。属性はΘ = 304.42, Δ = 49.31である。<4> [  ＋  ]は１８０度長点である。<5> [  ＋  ]は２７０度長点である。すなわち、このノード＜５＞で、巻き角は２７０を越えて巻いたことになる。次は<6> [ ＋− ]で、これは巻き角が＋から−へ変化する点である。
【００４６】
次にこれらのノードを結ぶ辺の属性として、折れ線数(0〜4) = 4, 長さ = 0.07, 最大|Δ| = |-24.52|の如く、それらのノード間の、折れ線数、長さ、|Δ|の最大値を取る。これらの特性は、回転不変である。
【００４７】
以上が入力のグラフ表現であり、これに対し、マスク構成によるテンプレートとのマッチングを行う。「８」の場合のマスク構成の一例を以下に示す。
【００４８】
＜「８」のマスクの一例＞
条件１： ＊ = −＋   （最初の鍵となるノード）
条件２： −200 ＜Θ(＊−)＜−100 & 200＜Θ(＊+) ＜360
（注：「Θ(＊−)」は最初の「−」巻き角、「Θ(＊+)」は後継する「＋」巻き角）
条件３：  -100 < Δ(*-) < -20 & 10 < Δ(*+) < 100
（注：「Δ(*-)」は「−」巻き角の境界の外角値、「Δ(*+)」は後継する「＋」巻き角の境界の 外角値。すなわち、境界線分の両端にある−側、＋側の外角値。）
条件４： (*-, *+),  Cross: nxm:n∈(*-)〜(*+)
（注：境界線分の両端間に交差点Crossが存在）
条件５： ＊+1 = ＋−  （２番目の鍵となるノード）
条件６：  200<Θ(*+1+) <360 & -200 <Θ(*+1-) <-10
（注：「/Θ(*+1+)」は+巻き角、「Θ(*+1-)」は次の−巻き角
条件７：  10 < Δ(*+1＋) < 100 & -100 < Δ(*+1−) < -20
（注：「 Δ(*+1＋)」は＋巻き角の境界の 外角値、「Δ(*+1−)」は次の−巻き角の境界の外角値。）
条件８： (*+1-, *+1+),  Cross: nxm:m∈(*+1＋)〜(*+1−)
（注：境界線分の両端間にCrossが存在）
文字［８］＝条件１＆条件２＆条件３＆条件４＆条件５＆条件６＆条件７＆条件８である。
【００４９】
このマスクは非常に簡単で、ノードは２個（「＊ = −＋」と「＊+1 = ＋−）で、それぞれ、−から＋への境界、＋から−への境界だけである。「±ｎ×９０度長点」は使用していない。ここで、「＊ = −＋」における「＊」の意味は、このノードがこのマスクの鍵になることを示し、巻き角が「マイナス」から「プラス」に変化するノードが必ず存在すること示している。「＊+1 = ＋−」は次に必要なノードとして、今度は反対に巻き角が「プラス」から「マイナス」に変化するノードをあげている。
【００５０】
加えて、条件２、条件３、で最初の鍵となるノードの、また条件６、 条件７で２番目の鍵となるノードの属性として、巻き角の値、境界線分の両端での外角Δに詳しい条件を与え、構造を締めている。また重要な、辺（エッジ）特性として、交点情報を使っている。それが、条件４と条件８である。m∈(*+1＋)〜(*+1−)は、次の巻き角変化点における境界線分間に交差点が存在することを要求している。交差点をCross: nxmと表現している。これらｎ、ｍは交差折れ線の番号であり、n∈(*-)〜(*+)はこの交差折れ線が、巻き角境界線分と一致することを示している。勿論交差点は回転不変特徴である。
【００５１】
以上、非常に簡単なマスクである。これを入力グラフ表現につき合わせて、この型がはまるノード範囲を探し、存在すれば、そこに「８」があるとするのである。注意しなければならないのは、上のマスクでは[  ｓ  ]、[  ｅ  ]ノードを使用していない。したがって、両端は開放された形になっている。このため、ともかく、時間の流れの中で、このマスクに当てはまるところ（範囲）があれば、そこに、「８」があるということになり、まったく、場所によらず、「切り出し前処理」が不要である。
【００５２】
実際、このマスクで、図４では３個の「８」が認識される。また、図６では、全く傾きが異なる、連結した「８」が、それぞれ認識されている。また、図７では、大きさが著しく異なる、２個の「８」が連結しているが、これらも正しくそれぞれ、「８」と認識される。当然のことながら、連結した文字によらず、単独の文字についても、同様のマスクと入力グラフ表現をつきあわせて、認識することが可能である。
【００５３】
なお、ここで、若干の注意点を述べる。それは、上に述べたマスクは全く、距離または長さと言う特性を含んでいない。それ故、連結の長さに全く、無関係に、どこでも、形がはまり、切り出し認識が出来たのである。しかし、反面、例えば、図７の場合のように２個の「８」の大きさの情報は失われ、人間が見るような、大きさの差が分からないのではと言う疑問がのこる。しかし、これは実は、簡単に求めることができるのである。
【００５４】
この入力表現は各ノードの位置座標を持つ。したがって、例えば「８」では、マスクの鍵である「＊」ノードから１８０度戻ったノード、図７では、これは殆ど＜ｓ＞ノードになるが、それと、＊＋１ノードから１８０度進んだノードの位置間のユークリッド距離を求める。
【００５５】
具体的には、それは大きな方の「８」では（286-38）２＋（562-449）２の平方根＝273、小さな「８」では（174-55）２＋（:625-611）２の平方根＝120で両者の比は約0.43となり、直感と合った結果が出る。若干複雑ではあるが図２の場合も両者の「８」の長軸と短軸のベクトルを求めることが出来て、傾き情報も知ることが出来る。このように、ノードの座標値は、長さ、角、方向などの、幾何的計量を求めるのに、有効に利用可能である。
【００５６】
＜±ｎ×９０度ノードの利用＞
上述の「８」のマスク構成の例では、本発明の本質を説明するために、±ｎ×９０度ノードを条件に加えない、簡単な構成の場合について説明したが、ここでは±ｎ×９０度ノードの有効性について、例をあげて説明する。これが特に有効なのは丸い形をもつもので、その典型は「円」である。
【００５７】
これは実際にも「○」として、良く使用される記号である。この円の形を、その本質は保持し、かつかなりの変形に耐える、マスクを作るのが課題である。
このマスクは以下のように作られる。
＜「○」マスクの一例＞
条件１： * = +90
条件２： 350< Θ(*) <600 & 0< Δ(*)< 95
条件３：(*.*+1); 0.1 ＜長さ＜0.35 & 0 ≦ |Δ| < 95
条件４： *+1 = +180
条件５： Θ(*+1)= Θ(*) & 0< Δ(*)< 95
条件６： (*+1.*+2); 0.1＜長さ＜0.35 & 0 ≦ |Δ| < 95
条件７： *+2 = +270
条件８： Θ(*+2)= Θ(*) & 0< Δ(*)< 95
条件９： (*+2.*+3); 0.1＜長さ＜0.35 & 0≦   |Δ| < 95
条件１０： *+2 = +360
条件１１： Θ(*+3)= Θ(*) & 0< Δ(*)< 95
条件１２：(*+3.*+4); 0.0＜長さ＜0.35  &  0 ≦ |Δ| < 95
記号「〇」＝条件１＆条件２＆条件３＆条件４＆条件５＆条件６＆条件７＆条件８＆条件９＆条件１０＆条件１１＆条件１２
【００５８】
このマスクのノードは４個（「＊=＋90」、「＊+1 =＋180」、「＊+2 =＋270」、「＊+3=＋360」）で、±ｎ×９０度ノードの存在（本件の場合は＋ｎ×９０度ノード）が、この形をおおまかに規定している。すなわち、この場合、ｎは１〜４で巻き角が９０度単位で３６０度まで巻くことを要請している。一方、ノードの属性としては、＋ｎ×９０度長点近傍では、急激な角度の増大が0< Δ(*)< 95で抑えられている。また辺の属性として、ノード間の長さが、ある決められた範囲にあることを要請している。これが、「0.1＜長さ＜0.35」である。また、その間に角の急激な増大がないようにも規定している。これが、「0 < |Δ| < 95」である。
【００５９】
このマスクは、十分、対ノイズに対し頑健な構成になっていて、両端は開いている。従って、図８に見られるように、外部にかなりのノイズがある場合にも、「○」が認識される。先にも述べた如く、長さを相対的に、例えば１８０度長点と３６０度長点間のユークリッド距離で、各長さを正規化すれば、これは、任意個の連結文字系列にも適用可能である。
【００６０】
＜凹凸ノード表現＞
ここでは、通常の回転不変を必要としない文字の認識の場合のグラフ表現について、述べる。このような場合には、±ｎ×９０度ノードを使うよりは、水平、垂直の直交座標系に基づく、凹凸をノードとした方が直感的で分かり易い。イメージとしての図９の説明図をご覧頂きたい。ここで、○がノードであり、矢印のついた→が辺である。
【００６１】
ここで、上下の凹凸を∪、∩と示し、左右から見ての凹凸を⊃、⊂と示す。このほかに実は、上下の凹凸と左右の凹凸が同時に存在する。例えば右上にとんがっているような場合には、∩と⊃が重なった∩＋⊃と示す。
【００６２】
ノードの属性は先に述べた如くであるが、辺の属性として、ノード間の折れ線群の平均方向角が加わる。これは、凹凸ノード表現では非常に重要な特徴となる。その他、曲がりの程度を示す折れ線群の方向分散がある。つぎに、重要なのは、ノード間の距離比である。例えば図９で言えば、始点は、終点よりある程度上になければならない。これらは、機械的に計算すると、かなりの数になるが、実際には要点だけ抑えれば良く、たいした数にはならない。ここで、例えばノード＜５＞のＹ軸値から始点＜ｓ＞ノードＹ軸値を引き、文字全体の長さの比で割った値を求める、といった具合である。
【００６３】
以下、この凹凸グラフ表現による「８」のマスクの一例を示す。
＜「８」のマスクの一例＞
条件１： *-1 = s/any
条件２： (*, *-1), 110< 加重平均角 <170
条件３： *  = ∩
条件４：  -420 < Θ(*) < -160
条件５：  -110 < Δ(*) < -10
条件６： *+1 =  ⊂
条件７：  Θ(*+1) = Θ(*)
条件８：  -110 < Δ(*+1) < -10
条件９： (*+1, *+2), -80 < 加重平均角 <-30
条件１０： (*+1, *+2),  長さ > 0.15
条件１１： *+2 = ⊃
条件１２： 250 < Θ(*+2) < 500
条件１３：  20 < Δ(*+2) < 100
条件１４： *+3 = ∪
条件１５：  Θ(*+3) = Θ(*+2)
条件１６：  10 < Δ(*+3) <120
条件１７： *+4 = ⊂
条件１８：  Θ(*+4) = Θ(*+2)
条件１９：  10 < Δ(*+4) <100
条件２０： (*+4, *+5), 20 < 加重平均角 < 75
条件２１： (*+4, *+5), Cross: nxm:n∈(*+1)〜(*+2), m∈(*+4)〜(*+5) 
条件２２： *+5 = e/any
条件２３： ((*+1, *+2)CrossY値-(*)Y値)/高さ 0.20＜Y＜0.70  
//交差点は高さでみてほぼ中心に位置する。符号に注意
文字「８」＝条件１＆条件２＆条件３＆条件４＆条件５＆条件６＆条件７＆条件８＆条件９＆条件１０＆条件１１＆条件１２＆条件１３＆条件１４＆条件１５＆条件１６＆条件１７＆条件１８＆条件１９＆条件２０＆条件２１＆条件２２＆条件２３
【００６４】
この場合は、特にノード間距離比は必要ない。その代わり、交差点に関する辺の属性である条件２３が、その役割を演じている。このように、ノード間距離比は実際には、組み合わせで生じる数よりはるかに少ない。それは、巻き角、外角、折れ線角の制限で、暗黙の内に制限されているからである。また、上のマスクにおける長さの制限は左から右に下がる、折れ線の長さを制限するだけである。実はこのために、非常に、端のノイズに強いマスクとなっている。
【００６５】
なお、これは、連続した文字系列用の切り出し認識マスクではない。それは、この長さの制限を入れているからである。この点、ノード*  = ∩とノード*+3 = ∪間のY軸値で、この長さを正規化してやれば、連続した文字系列用の切り出し認識マスクとなる。
【００６６】
この手法により、端に極端なノイズが発生した場合や、極端な変形が生じた場合においても、核となる「８」の形を持っていれば、その周りの状況と無関係に、正しい認識が行われる。
【００６７】
＜文字の形の包含関係＞
上に述べてきた、切り出しの認識法は、必然的に、複数の答えを出す可能性を持つ。
この、具体的例が図１０に示されている。図１０は「８」を意図して書かれたものであるが、しかし、この図形には「６」が隠されている。言葉を変えれば、元の図形から、「６」なる文字形が「切り出し認識」されているわけである。したがって、これは必然的な結果である。
【００６８】
そこで、意図された、「８」が正しく出力されるメカニズムが必要である。これは直感的に言えば、複雑な形を優先すると言うことであるが、定量的に正確に述べると、「６」のマスクにマッチしている折れ線の長さと、「８」のマスクにマッチしている折れ線の長さを比較すれば、当然、後者がより長くなる。
【００６９】
以下の例から、「８」は「６」より０．２７の長さ分、長い。したがって、「６」は定量的にも「８」のイメージに埋没し、「８」は「６」より０．２７長い整合部分を持ち、「８」と判定される。このほか、整合ノード数、折れ線数などの整合の測度が考えられる。
【００７０】
なお、本発明の手書き文字認識は、実施の形態の説明の最初でも説明したように、図１に示した処理構成に限定されるものではなく、実質的に同様の手書き文字認識が行われる構成であれば、種々の装置やシステムの構成で、認識処理を行うことが可能である。例えば、本発明の手書き文字認識をプログラム（ソフトウエア）化して、汎用のパーソナルコンピュータ装置に実装させるようにしてもよい。手書き文字認識プログラムは、各種記憶媒体に記憶させて、配布することが可能である。
【００７１】
ここではオンラインの文字を対象としたが、適当な細線化か、輪郭追跡などで、オフラインの文字に対しても、文字認識を行うようにしてもよい。
さらに、上述した実施の形態では、主として数字の認識を行う場合を例としたが、本発明の手書き文字認識は、基本的にどのような言語の文字や記号にも適用可能である。
【図面の簡単な説明】
【００７２】
【図１】本発明の一実施の形態によるシステム例を示す構成図である。
【図２】本発明の一実施の形態による文字認識全体の処理例を示すフローチャートである。
【図３】本発明の一実施の形態による文字認識処理の詳細例を示すフローチャートである。
【図４】本発明の一実施の形態による折れ線近似の例を示す説明図である。
【図５】本発明の一実施の形態によるノードの例を示す説明図である。
【図６】本発明の一実施の形態による折れ線近似の例を示す説明図である。
【図７】本発明の一実施の形態による折れ線近似の例を示す説明図である。
【図８】本発明の一実施の形態による折れ線近似の例を示す説明図である。
【図９】本発明の一実施の形態によるノードと辺の関係の例を示す説明図である。
【図１０】本発明の一実施の形態による判定例を示す説明図である。
【符号の説明】
【００７３】
１…紙、１ａ…運筆、２…ペン、３…入力処理部、４…折れ線近似部、５…前処理部、６…特徴抽出部、７…識別部、８…識別結果出力部
【図１】
2008046825.tif 000004
【図２】
2008046825.tif 000005
【図３】
2008046825.tif 000006
【図４】
2008046825.tif 000007
【図５】
2008046825.tif 000008
【図６】
2008046825.tif 000009
【図７】
2008046825.tif 000010
【図８】
2008046825.tif 000011
【図９】
2008046825.tif 000012
【図１０】
2008046825.tif 000013