JPH0991381A - オンライン文字認識装置 - Google Patents

Abstract

(57)【要約】 【課題】 オンライン手書き文字を筆順や画数によらず
高速に認識する。 【解決手段】 実時間で記入される文字の各ストローク
の始点から終点に至る点列を順番に１１に格納し、１３
において１４に格納してある認識対象文字ごとのストロ
ークの始点から終点に至る点列の情報と、各ストローク
間の類似度を計算する１２を用いて、認識辞書からもっ
とも似ている文字を選択し、該当する文字コードを出力
する際、１４において、記入される文字パタンと辞書パ
タンの類似度を、ストローク対応付けの逐次過程をスト
ロークの既対応／未対応の状態を示す画数分のフラグの
組をノードとするグラフ上での最適経路問題として、グ
ラフ間の飛び越し遷移を許容させながら動的計画法およ
びビームサーチを用いて求めた最適経路に対する距離で
定義することにより、文字を認識する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、電気的に入力され
た文字画像を文字コードに変換する文字認識装置に関
し、特にペンおよびダブレットから成る画像入力装置か
ら入力された文字画像を実時間で文字コードに変換する
オンライン文字認識装置に関する。

【０００２】

【従来の技術】従来、この種のオンライン文字認識装置
では、入力された文字を認識して文字コードを出力する
際に、文字画像を移動するペンの位置座標の時系列とし
て処理するため、入力された文字の筆順や画数が変化し
た場合にその文字を認識できないという欠点があった。
近年になって、例えば、１９８３年，若原他，選択的ス
トローク結合による画数・筆順に依存しないオンライン
文字認識（電子情報通信学会論文誌Ｊ６６−Ｄ，５号，
５９３〜６００頁）に示されているように、筆順や画数
に依存しないオンライン文字認識装置が提案されてきて
いる。これらの筆順や画数に依存しない文字認識装置の
中の初期段階の重要な処理の一つに、入力パタンと参照
パタンの間のストロークの対応づけによる類似度評価が
ある。つまり、入力パタンと参照パタンの間でストロー
クを最適に対応させた上で、整合性を評価し認識結果を
出力する必要がある。従来のオンライン文字認識装置に
おけるストロークの対応づけでは、考えられるあらゆる
対応づけの組み合わせを調べ、各々のストロークの整合
が取れるような最適な対応を選ぶという方法を採用して
いる。処理の高速化をより意識した別の方法としては、
互いに近いストローク同士から順に取り出してゆく、と
いうような一種の枝刈りに基づく探索を行う方法もあ
る。

【０００３】

【発明が解決しようとする課題】しかしながら、この種
のオンライン文字認識装置では、ストロークの対応づけ
において、あらゆる対応づけの組み合わせのすべてにつ
いて全探索を行うと、処理時間がストローク数の階乗の
オーダーで増加するため、実時間処理が困難であった。
また、互いに近いストローク同士から順に取り出してゆ
くような経験的な枝刈りに基づく探索を行った場合で
は、一つでも対応づけを取り違えると、対応づけの誤り
が波及的に広がってしまうため、読み取り性能低下の原
因となる。

【０００４】

【課題を解決するための手段】上述した課題を解決する
ため、本発明によるオンライン文字認識装置は、入力さ
れた複数個のストローク（座標点列）を記憶するストロ
ーク記憶手段と、あらかじめ用意されて入力パタンと比
較するための参照パタンを記憶する認識辞書記憶手段
と、２個のストロークを与えられたときにそれらの類似
度を評価するストローク類似度評価手段と、入力パタン
と参照パタンのストロークの対応づけを順次行い、また
上記ストローク類似度評価手段の結果を使い、かつスト
ローク間の対応づけをグラフのノードをたどる最適経路
問題として動的に探索する文字類似度評価手段とを備え
る。

【０００５】本発明によるオンライン文字認識装置で
は、入力パタンと参照パタンのストローク同士の最適な
対応を求めるために、各々のストロークを逐次的に対応
させてゆく際のストローク選択の各段階を、ストローク
数と同じ次元を持つ超立方体型のグラフのノードに対応
させて、コストつきグラフの最適経路探索問題を動的計
画法およびビームサーチ法で解くことにより、ストロー
クの最適な対応づけ、すなわち全探索を行ったのと同等
の結果を高速に探索して、文字の筆順に依存せずに文字
を認識することが可能となる。またノードの飛び越しを
許した最適経路探索を行うことにより、文字の画数に依
存せずに文字を認識することができる。

【０００６】

【発明の実施の形態】次に、本発明について図面を参照
して説明する。

【０００７】図１は、本発明の一実施例を示すブロック
図である。この実施例は、入力された複数個のストロー
ク（座標点列）を記憶するストローク記憶手段１１と、
あらかじめ用意されて入力パタンと比較するための参照
パタンを記憶する認識辞書記憶手段１４と、２個のスト
ロークを与えられたときにそれらの類似度を評価するス
トローク類似度評価手段１２と、入力パタンと参照パタ
ンのストロークの対応づけを順次行い、また上記ストロ
ーク類似度評価手段の結果を使い、かつストローク間の
対応づけをグラフのノードをたどる最適経路問題として
動的に探索する文字類似度評価手段１３とを備える。

【０００８】図１，図２，図３および図４を参照して、
本実施例の動作について説明する。ストローク記憶手段
１１に、入力文字を構成するＮ個のストロークＡ＝（Ａ
₁ ，Ａ₂ ，…，Ａ_N ）の情報、すなわちタブレット上を
ペンが移動した軌跡を表す座標点列が格納されると、文
字類似度評価手段１３は認識辞書記憶手段１４から同じ
ストローク数を持つ参照パタンを呼び出し、類似度を計
算する。このとき入力パタンＡと参照パタンＢ＝
（Ｂ₁ ，Ｂ₂ ，…，Ｂ_N ）との文字間距離Ｄ（Ａ，Ｂ）
を次式で評価する。

【０００９】

【数１】

【００１０】ここに、数列τ（１），τ（２），…，τ
（Ｎ）は数列１，２，…，Ｎの置換を表し、δ（Ａ_i,Ｂ
_j ）はパタンＡの第ｉストロークＡ_i とパタンＢの第ｊ
ストロークＢ_j とのストローク間距離を表す。ストロー
ク間距離は、ストローク間類似度評価手段１２によって
計算され、例えば双方のストロークから１個または複数
の代表点を同数ずつ選び出し、代表点間のユークリッド
距離を計算することによって求められる。あるいはま
た、対応づけられることがあり得ないと経験的にわかっ
ているストローク同士があれば、δ（Ａ_i,Ｂ_j ）の値を
あらかじめ大きく設定しておくこともできる。

【００１１】ストロークの対応づけ、すなわち置換τは
Ｎ！通り存在するため、本発明では右辺の括弧内の量の
最適化に、以下に示すような高速探索アルゴリズムを用
いる。図２に示すような、左から右へ向かう深さＮの有
向グラフ（Ｎ次元単位超立方体型グラフ）を準備する。
（図はＮ＝４の場合を表す。）グラフの左端のノードか
ら右端のノードへ経路をたどってゆくにしたがって、入
力パタンと参照パタンのストロークが逐次的に対応づけ
られてゆく。グラフの各々のノードにはＮ個のビット配
列が付随しており、第ｉ番目のビットが０であるとき、
入力パタンの第ｉストロークが未対応であることを表
し、第ｉ番目のビットが１であるとき、入力パタンの第
ｉストロークがすでに参照パタンのいずれかのストロー
クに対応づけられていることを表す。また、グラフのエ
ッジには入力パタンと参照パタンとの間のそれぞれのス
トローク間距離が付随している。すなわち、深さｋの位
置にある一つのエッジの両端のノードに付随するビット
配列を比べて、第ｉビットが異なっているとすると、そ
のエッジにはストローク間距離δ（Ａ_i Ｂ_k ）を付随さ
せておく。グラフの左端のノード（００００）から右端
のノード（１１１１）に至る経路と、置換τが一対一に
対応しており、経路上のエッジに付随したコストの総和
が、（１）式の括弧内の量と一対一に対応している。よ
って、（１）式の最小化問題の解が、図２のようなコス
トつきグラフ内最適経路探索問題を解くことによって求
められる。

【００１２】上記最適経路探索による最適コストを動的
計画法およびビームサーチ法を用いて解く。動的計画法
は、段として参照パタンのストローク番号ｋ、状態とし
てグラフのノード（ストロークの対応状況）、状態遷移
として第τ（ｋ）ビットの０→１反転、コストとしてグ
ラフのエッジに付随したストローク間距離

【００１３】

【外１】

【００１４】を設定する。動的計画法の漸化式は次式に
よって計算される。

【００１５】

【数２】

【００１６】ただし、ｎ（０≦ｎ≦２^N −１）は、各々
のノードに付随しノードを指定するビット配列を２進数
で表した数、すなわち状態を表す数で、状態遷移はビッ
ト配列の一つの要素の０→１反転によって行われる。以
下、図３，図４を用いて最適経路探索アルゴリズムを説
明する。図３，図４においてｍｂｅａｍ（ｋ）はグラフ
の深さｋに存在するノードの数、またｎｂｅａｍ（ｋ，
ｍ）は深さｋにおける各ノードの状態（ビット配列を表
す２進数）である。初期化ではＧ（１）＝Ｇ（２）＝…
＝Ｇ（２^N −１）＝∞，Ｇ（０）＝０，Ｇ_min ＝０，ｍ
ｂｅａｍ（０）＝１，ｎｂｅａｍ（０，１）＝０と設定
する（Ａ２）。以下、グラフの深さ０（左端のノード）
から始めて、それぞれの深さｋにおける最適経路を採っ
た場合のコストＧ（ｎ）を漸化式（２）を用いて順次計
算してゆき、最終的に右端のノードに達する最適経路の
コストＧ（２^N −１）、すなわち入力パタンと参照パタ
ンのすべてのストロークを最適に対応させた場合のパタ
ン間距離を算出する。

【００１７】以上のようにして、入力文字パタンと参照
パタンの間の距離を参照パタンごとに評価し、（１）式
の評価値が最も小さい参照パタンに対応する文字コード
を、認識結果として出力する。

【００１８】次に、図５を用いて、本発明の別の実施例
を説明する。

【００１９】本実施例の構成を説明する。図１に示すよ
うに、入力された複数個のストローク（座標点列）を記
憶するストローク記憶手段１１と、あらかじめ用意され
て入力パタンと比較するための参照パタンを記憶する認
識辞書記憶手段１４と、２個のストロークを与えられた
ときにそれらの類似度を評価するストローク類似度評価
手段１２と、入力パタンと参照パタンのストロークの対
応づけを順次行い、また上記ストローク類似度評価手段
の結果を使い、かつストローク間の対応づけをグラフの
ノードをたどる最適経路問題として動的に探索する文字
類似度評価手段１３とを備える。

【００２０】本実施例では、上記第一の実施例で説明し
た図２に示すような超立方体型グラフの代わりに、図５
に示すような拡張されたグラフを用いることにより、続
け書きでもストローク同士の対応をとることができ、画
数に依存しない文字認識を実現することができる。図５
の拡張されたグラフの構成を説明する。拡張されたグラ
フでは、超立方体型グラフの層ｃ＝０に加えて、ｃ＝
１，ｃ＝２で示す新たな層が付加されている。ある層で
深さｋにある状態は、その直下の層では深さｋ−１に配
置されている。したがって、グラフにおいて一段下の層
のノードに遷移すると、元の層で２回の遷移を完了した
のと同じ状態に移ることができる。したがって、入力文
字の参照パタン中の２つのストロークと、入力パタン中
の１つのストロークを対応づけることができるので、続
け書きで入力された文字を許容することが可能である。
図３，図４の例では、２つの層を付加したことにより、
最大２箇所までの続け書きを許容することができる。

【００２１】本実施例の動作について説明する。図１の
文字間類似度評価手段１３において、図５に示すグラフ
の左端のノードから始めてビット配列（１１１１）をも
ついくつかの右端のノードの一つに至る最適経路を、図
３，図４に示すフローチャートに従って探索することに
より、続け書きを許容した上で最適にストローク同士を
対応させた文字間類似度を計算することができる。

【００２２】次に、図６を用いて、本発明の第三の実施
例を説明する。

【００２３】本実施例の構成も、図１に示すように、入
力された複数個のストローク（座標点列）を記憶するス
トローク記憶手段１１と、あらかじめ用意されて入力パ
タンと比較するための参照パタンを記憶する認識辞書記
憶手段１４と、２個のストロークを与えられたときにそ
れらの類似度を評価するストローク類似度評価手段１２
と、入力パタンと参照パタンのストロークの対応づけを
順次行い、また上記ストローク類似度評価手段の結果を
使い、かつストローク間の対応づけをグラフのノードを
たどる最適経路問題として動的に探索する文字類似度評
価手段１３とを備える。

【００２４】本実施例では、上記第一の実施例で説明し
た図２に示すような超立方体型グラフの代わりに、図６
に示すような拡張されたグラフを用いることにより、ス
トロークの相互位置関係についても整合をとり、より正
確にストローク間の対応づけを行う。図６の拡張された
グラフの構成を説明する。拡張されたグラフでは、超立
方体型グラフの各々のノードについて、その時点で最後
に対応づけられたストロークの番号がいずれであったか
によって細分化しておく。そうして、グラフのエッジに
は次式で示されるようなコストを付与する。

【００２５】

【数３】

【００２６】ここに、ρ（Ａ_i,Ａ_j,Ｂ_k ）は、文字パタ
ンＡの第ｉ番目のストロークＡ_i から第ｊ番目のストロ
ークＡ_j へ移動するときの移動ベクトルと、文字パタン
Ｂの第ｋ−１番目のストロークＢ_k-1 から第ｋ番目のス
トロークＢ_k へ移動するときの移動ベクトルとの間の距
離の絶対値である。例えば、Ａ_i の終点とＡ_j の始点の
間の移動ベクトルをｕ、Ｂ_k-1 の終点とＢ_k の始点の間
の移動ベクトルをｖとおけば、 ρ（Ａ_i,Ａ_j,Ｂ_k ）＝‖ｕ−ｖ‖ （４） によってρを計算することができる。あるいはまた、Ａ
_i とＡ_j が連続して入力されることがあり得ないと経験
的にわかっている場合は、ρ（Ａ_i,Ａ_j,Ｂ_k ）の値をあ
らかじめ大きく、例えば無限大に設定しておくこともで
きる。

【００２７】本実施例の動作について説明する。図１の
文字間類似度評価手段１３において、図６に示すグラフ
の左端のノードから始めてビット配列（１１１１）をも
ついくつかの右端のノードのいずれかに至る最適経路
を、図３，図４に示すフローチャートに従って探索する
ことにより、連続する２つのストロークの相互位置関係
による類似度を評価しつつ、最適にストローク同士を対
応させた文字間類似度を計算することができる。

【００２８】

【発明の効果】以上説明したように本発明によれば、筆
順や画数に依存しないオンライン手書き文字認識におい
て、認識辞書に登録してあるストローク情報との対応付
けを、コスト付きグラフの最適経路問題として解く際
に、ストローク対応付けの逐次過程をストロークの対
応、未対応の状態を示す画数分のフラグの組をノードと
してグラフを作り、そのグラフ上での最適経路問題をダ
イナミックプログラミング法、およびビームサーチ法を
用いて解くことにより、（ストローク数）×（２の（ス
トローク数−１）乗）のオーダーの計算量で最適解が計
算可能となり、従来実時間で不可能だった辞書との照合
が可能になり、さらに前述のグラフにおいて、グラフ間
の飛び越し遷移を許容することにより画数フリーも実現
でき、文字の認識速度、および認識精度が著しく向上す
る。

【図面の簡単な説明】

【図１】本発明の一実施例の機能的な構成を表したブロ
ック図。

【図２】基本的な超立方体型グラフ（画数４の場合）を
示す図。

【図３】動的計画法とビームサーチ法を用いたグラフ内
最適経路探索アルゴリズムを示すフローチャート。

【図４】動的計画法とビームサーチ法を用いたグラフ内
最適経路探索アルゴリズムを示すフローチャート。

【図５】ストローク数が異なる文字同士の対応を許容す
るグラフを示す図。

【図６】ストロークの相互位置関係を考慮して構成した
グラフを示す図。

【符号の説明】

１１ ストローク記憶手段 １２ ストローク類似度評価手段 １３ 文字類似度評価手段 １４ 認識辞書記憶手段

Claims (4)

【特許請求の範囲】
1. 【請求項１】実時間で記入される文字の各ストロークの
   始点から終点に至る点列を順に格納するストローク記憶
   手段と、入力された文字を識別するためにあらかじめ用
   意された認識辞書のストローク情報を記憶する認識辞書
   記憶手段と、上記ストローク情報を用いてストロークと
   ストロークの類似度を評価するストローク類似度評価手
   段と、上記ストローク類似度評価手段が出力する類似度
   評価結果に基づいて、入力パタンと参照パタンの最適な
   ストローク対応づけを、その逐次過程における既対応／
   未対応を表した状態を各ノードに割り当て、かつ個々の
   ストローク間の距離をエッジに割り当てたグラフの最適
   経路問題として、動的計画法およびビームサーチ法を用
   いて探索しながら、入力パタンと参照パタンの間の類似
   度を評価する文字類似度評価手段を備えることを特徴と
   するオンライン文字認識装置。
2. 【請求項２】前記文字類似度評価手段が、入力パタンと
   参照パタンのストロークを逐次的に対応づける際に、一
   度に複数個のストロークが対応づけされた状態への遷移
   を許容する、請求項１記載のオンライン文字認識装置。
3. 【請求項３】前記文字類似度評価手段が入力パタンと参
   照パタンのストロークを逐次的に対応づける際に、個々
   のストローク間距離に、直前に入力されたストロークか
   らの移動量を加えた距離値をエッジに割り当てたグラフ
   の最適経路を探索することにより、文字間の類似度を評
   価することを特徴とする請求項１記載のオンライン文字
   認識装置。
4. 【請求項４】前記文字類似度評価手段が入力パタンと参
   照パタンのストロークを逐次的に対応づける際に、実際
   上起こり得ない筆順と対応しないようにすることを特徴
   とする請求項１記載のオンライン文字認識装置。