JPS6017573A - 類似度検出装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 本発明は二次元格子上の量子化バタンに変換された手書
き文字バタン或いは図形バタンの照合全行なうだめの類
似度検出装置に関する。

従来２つのバタン間の類似度を評価する手法としては、
比較的手軽な処理によって得らハるコークリッド距離、
ハミング距離、午純類似度や、印刷漢字認識で用いらＪ
また複合類似度、音声認識で用いられたｆ）Ｐマツチン
グ法がある。複合類似度は印刷文字のように比較的狭い
範囲で統計的な変動がある二次元バタンについＣは効果
が知られておリ、またＤＰマツ（−フグ法は一次元上の
非線形の変動を吸収することは知られ”Ｃいるが、手書
き文字バタン或いは簡歩な手書き図形バタン等のように
二次元的でしか本局所的に異な−）だ変動音するバタン
への適用は困難であった。

そこで手書き文字の変形は、文字バタンにおいて局所的
に起こることから、入力文字バタンと、標準文字バタン
をそれぞれ部分バタンで表わし、各部分バタンをそわぞ
れ独立に、ずらし、なから整合を行ない、各部分バタン
において、最もよく整合のとれたものを対応させ、それ
らの全体から入力文字バタンと標準文字バタンとの類似
度をめる手法が提案されている。（山田他［類似度法の
−改良−一すらし類似度−−」重子通信学会論文誌Ｖｏ
ｌ、　Ｊ　６４−Ｄ、　Ｎｎ１０．１９８１／　１０　
）この類似度は例えば次のような手順でめられる。例え
ば標準文字バタンをｆ、（ｉｔｊ）としたとき、これを
ＫＸＬに分割した部分バタンｆ　（Ｌｊ；に、Ｊ）（た
だＬ　ｋ＝０　、１　、・・・、ｋ−１；　ｅ＝０　、
　ｌ　、−、Ｌ−１）であるとする。（ただし、■トー
１に一１１＝−定、Ｊ／−、Ｊｓ−＋＝一定）一方入力
文字バタンをｆＮ、ｊ）　と１７だとき、前記標準文字
バタンｆ、（ｉｔｊ）の部分バタンｆａ　（ｉ、ｊ；に
、ｌ）に対する入力文字バタンｆ（ｉｔｊ）のずらし部
分バタンｆ　（＋　＋ｊ；に＋ｌ；Ｘ＋Ｙ）はであると
する。（ただし−Ｗｈ４．ｘ〈；Ｗｈ、ｗｔ、４ｙ偉−
）このとき各に％ｉで定まる部分バタンについて、ユク
リノド距離、シティブロック距離或は他の手段で定まる
評価手段ｄを用いて、−ｗｂ　＝Ｑｘ＜（−Ｗ−及び−
ＷＩ、４ｔ４ｗ８、の範囲内のずらしバタンとの間で最
適整合値ｄａ、ｌをめる。ここで Ｗｌ、４７４九 であり、ｄｋ、７は値が小さい程より良い整合値とする
。以上のようにに＝０　＋　１　＋・・・、に−１及び
ｌ　＝−０、１。

・・・、Ｌ−１についてｒｈ、ｌをめ、標準文字バタン
ｆ−（ｉｔｊ）　と入力文字バタンｆ（ｉｔｊ）との類
似度金、あらかじめ定められた、ｄｈ、ｌを変数とする
評価関数りによって定まる値Ｄ（ｄ、、。、・・・ｌｄ
６＋Ｌ　＋＋４・・。

ｄｋ−１＋ｅｌ　・＋・ｊ　ｄｈ−１＋Ｌ−１）として
決定する。

ここですら１〜の範囲を決定するＷｋ　、！：Ｗ［、の
値が大きい場合は、第１図（ａｌに示すような位１れの
変形を吸収する反面、第１図（ｂｌに示すような文字バ
タンの構造を破壊した合わせすぎの悪影響も伴なってお
り、反対に県とＷ　Ｈ４の値を小さくすると、合わせす
ぎが減少する反面、位置ずれの変形を吸収する能力に欠
ける点が問題である。

上記の問題が起こる理由は、各部分バタンにおいて最適
整合値ｄｋ、７をめるときに、二次元図形としての位相
を無視していることから起こるもので、第１図（ｂ）の
合わせずぎの例はまさに位相を無視することによって起
こったものである。

本発明の目的は上記各部分バタンのずらしの整合をめる
ときに、各部分バタン間の位相情報を考虜することによ
り、−二次元図形としての構造を保存ｌ−ながら、従来
ｊ１胸り位ＩＲずれの変形を吸収１７、かつ文字バタン
の構造を破欺゛シた合わせずぎを防１−することのでき
る、文字バタン等の二次元バタンの類似度検出装置を提
供することである。

以下本発明の詳細な説明を行なう。

第２図は、不発１．ｌＩ４の構成の一例を示４−ブロッ
ク図である。

１は局所対応検出部であり、前記枦準文字バタンｆ−（
Ｌｊ）　の部分バタ／ｌ’、（ｉｔｊ；に＋ｌ）を信号
】（）として、前記入力文字バタンの前記部分バタンｆ
ｓ（１ｔにに＋ｌ）に対応する前記各ずらし部分バタン
ｆ（１＋ｊ：に＋ｌ；Ｘ＋Ｙ）　を信号１１として入力
し、各ｘ、ｙに対する整合ｆｔａ　ｄ（ｆ、ｉｔｊ；ｋ
ｔｌ）ｔｆ（Ｌｊ；ｋにｘ、ｙ）を信号１２として出力
４るへ２は局所対応候補記憶部であり、前記各に、ｌニ
ツイテ部分バタ７　ｆ＊（Ｌｊ；に４）Ｉこ対ｋＦｉす
る候補となる前記各すらし部分バタンｆ（＋　＋にに＋
７＋；Ｘ＋）’）の整合値と位置情報を信号１２として
入力し格納する。３は類似度検出部であり、前記局所対
応候補記憶ｇ＋＋　２から、前記部分バタンｆ、ｃｉ！
ｊ：ｋｌｌ）に対応する候補となる各」゛らし−↑ＸＩ
ｔ分バタンｆ（Ｌｊ：ｋにｘ＋ｙ）　の整合１自と位置
情報ど１［号１３として読み出し、あらかじめ定めた二
次元図形構造を保存する条件を満たず絹合わせのうちＭ
適７；ｃｉ山をとるものを選び、前記最適値を類似度信
号１４として出力する。図中局所対応検出部１は、２つ
の部分バタンを読み出し、その位置情報とあらかじめ定
められた手段による整合価とをめ出力するもので、これ
までの文字認識技術で容易に実現できるものであり、同
じく図中局所対応候補記憶部２は一般の記憶素子である
。

第３図は前記局所対応候補記憶部２上の対応候＋ｎ＋　
＋＠＋ 補の情報を示す図であり、ｄ　は整合値、ｘｋ、！、ｋ
、１ （−１ ｙ　はすら１〜の位置情報である。ここで二次元図す、
Ｊ 形構造を保存する条件とは、単に相対位置関係を保存す
る条件としては、前記各部分バタンｆ＊（ｉ、ｊ；に、
ｌ）に対応する前記ずらし部分バタン全ｔ、ｌ（，１ ｆ（ｉ＋ｊ；に＋Ａ！；ｘｋ１．、ｙｋ、Ｉ）とすると
）を満たすことであり、上記条件を満たさない場合１と
は、左右または上下を逆転１７て対応させることになる
。次に相対位置関係の他に各部分バタンの対応が比較的
滑らかに変化する条件を加えるととなり、更に どすることもできる。条件（２）は部分対応をとったと
きに、局所的に縮小する度合を制限するものであり、条
件（３）は更に部分対応金とったときに局所的に伸長す
る度合を制限するものである。これは手書き文字バタン
等の変動が、局所的ではあるが、連続的な変化をしてい
る条件と見ることができる。

前記類似度検出部３は上記条件（１）また＋ｉ　（２）
または（３）を満たずような各部分バタンＬ（１）Ｊ：
Ｊｌ）に対（、＋　（ｎｌ　ｔＩＩｌ　ｔｆｉ＋ 応するＸ　ｓＶ　をめ、前記Ｘ２２．、ｙｋ、１に対応
ずに、ｌ　ｈμ るｄ（“ゝによって得られる前記評価値りを最小にずに
、す るイ１〃全類似度として決定する。

第４図は前記類似度検出部３の具体的な構成の一例を示
すだめのブロック図である。４は部分評価値検出部であ
り、信号１３として前記整合値（謁１）　（ａｋ−＋） ｄ　１　・・・　ｄ　（ｎ０＝１、・・・、Ｎ　：　・
・・；ｎｋ−１二ｌ　、６＋＋、Ｎ）１、ｊ　ゝ　ｈ−
１，ｊ の組み合わせ１こ対するあらかじめ定められた部分評価
値ｄｇ　（ｎｏ、・・・、ｒ＋ｂ−＋）をめ、各部分評
価値と（ａｌ　ｔａｌ　ｔ、＋　（麹） 位置情報（ｘ　ｓＶ　Ｋ・・・、（χ　、ｙ　）Ｏμ　
ｏ、ｔ　ｋ−（、ｔ　ｈ−１，１（ｎ＝１、・・・、Ｎ
）　とを信号４】として出力する。

前記部分評価イーＤｉ　（ｎｏ、・・・、ｎｋ−＋）は
Ｎｋ通りあり、例えばに＝４、Ｎ＝４のときはＤＩ（Ｌ
、１．１．１）１１．・、ＤＪ（４％４．４，４）　の
２５６通りである。前記部分評価値ｔ、Ｉ　（、Ｉ Ｄｉ　（ｎｏ　、６・・、ｎｌ１）は、各（Ｘ、Ｖ）が
前記構造り、Ｉ　ｋ、ｊ を保存する条件を満たさない場合には無限大とみなし、
充分大きな値を与える。５は累積局所対応記憶部であり
、前記位ｆｗ（ｉ腎！（、ｘ　％Ｍ）　と累り、Ｉ　ｙ
ｌ 積部分評価仙１）／（ｎ、％・・・、ｎｋ−１）を格納
する。６は部分評価値加算部であり、前記部分評１ｉｌ
ｌｉ値検出部４から信号４１として前記部分評価値ｄｚ
１＋　（ｎｏ　、・・・、（Ｉ＋） ｎｈ−４）と前記位置端４１　（Ｘｏ、十、　、ｙｌ、
、　）＝−（ｘｋ−１、累積局所対応記憶部５がら各位
１４１Ｎ報（Ｘ・、ｔ　、ｙ、、／）、・・・、（Ｘｂ
−１，／’を、、＞　（ｎ＝１、・・・、Ｎ］と各免〃
部分評価イｉ＠、　Ｉ）ｚ　（ｎ’、　、　、、、、ｎ
’、＋）を信号５１として′Ｉａ−’ｙ込み、前Ｈ；シ
各累積部分評価値Ｉ）ｚ　（ｎ’ｏ　、・・・、ｎ’に
−１）について、前記各（ｔ７：　ｌｉ！情報が前記構
造保存の条件を満たず関係にある前記部分評仙白ｊｂ、
　ｄｌ、十’　（ｎｏ　、・・・、ｎｈ−１）のうち、
最小のものを加ａ５［７、新しく得られた加算結果を新
たにＤ’（−ｘ　（ｎ’ｏ　ｓ　・・・、ｎ’ｈ−ｒ）
とし前記位１青情報（Ｘｓ　（、ｅ４−４、（，１’　
（，１ ｙｏｔｊ４＋ン、・・・、（ｘｈ−１、、／＋１　”、
−１＋、　ｇ−Ｈンとともに信号５２として前記局所対
応記憶部に書き込む。もし位置（ａＱ）　（ｓ’ｎ）　
、　（＋＆−１）　（ｎＣ−ｑ）情報（Ｘｏ　＋　、ｙ
ｌ、　ｌ　）、°、％１．１　％　Ｖｋ−１，１）と各
位置端＋１ １．１　＋、１ 報（ｘ、　、　２−）ζｙＬ　、　ｄ＋１）とが前記構
造保存の条件を満たさ／、（い蔦−冶（（二（１，１）
［１猷１ｊ）ｉ１〜い累積部分評価（（自１．）７−）
１１）ｚ旧（，１・。１２．９、。’ｈ−＋）は無限大
とツメ・なＩ〜・充分大きな値をＩｊえる。この処理は
次のようなｔ’ｆｌｉ化ｊ（を実や−［している ただしｍ１号ｍ１ｎ（ｃｏｎｄ）　は前記構造保存をｒ
ｉｂ−か−４−も（Ｉ）のうちの穀小値を示すものとす
る。７は最小１１ｔ１検出部であり、前記順化式の処理
を縁り返し１行なうことによって得ら第１るＫＮ通りの
累積評イ＋ｌｌｉ　Ｉｉ倉の条件のための比較器や、評
価値をめるための加算器等の演算器や評価値を格納する
ためのレジスタ等によ−って容易に構成できる。また累
積局所対応記憶部５は一般に使用される記憶累子でよい
。

部分評価値加算部６も評価値を格納するレジスタ、構造
保イエの条件のだめの比較器、加ｎ器■−の演鐙器等に
より千賀−易に構成できる。ま／こ、最小値検出部７も
肚較器及びｌ／レジスタによ−）て容易に構成でき２）
。

以上の説明により本発明に」、れば（１へ造を保育した
状態での局所的なずらＬ変形を吸収する類似度をめるこ
とができる。」−記の説、明でイｈ号１４として得られ
た類似度は値が小さければ、２つの文字（図形）バタン
か似ていることを示し７ている。

また以上のようにしてめた類似度金前記標準バタン或は
前記入力バタンの濃度仙等で値を正規化してあらためて
類似度とし′Ｃ扱うこともできる。

（、＋　＋、＋　＋−１（ｎ＋ また上記説明では（ｘ　、ｙ　）、・・・、（Ｘ　ｙ　
）ａ、ｌ　６，１　ｋ−１，ｌ、ｇ、ｔ をＪつの組として逐次処理全行なったが、ｉｎ）　＋ｎ
＋’　ｔ、］　ｔ、１ （ｘ　、、ｙ　）、・・、（ｘ　、ｙ　）　を１つの組
としｈ　、Ｌ−１ｈ　、ｌ−＋−１ て逐次処理を行なっても同「結果が得ら」１．る。また
本発明で（１漸化式の処理を単１する加算で示したが、
扱うバタンの性質がわかっているときには、重みをつ（
することも可能であるが、本発明の本質的な問題ではな
い。

また本発明における構造保存の条件を前記ｋまたはｉの
一方向についてのみ定めて、処理数の簡略化全図ること
もできる。また詳細ブ！説明の中ではずら１７の範囲を
長方形と１７だが、これに限るものではなく、また標準
バタンと入力バタンの取り扱か℃・を逆にすることも可
能である。

４　図面の簡却ｌＪ、餅、明 第１図は２つの文字バタンのＶ＠の例を示し、同図（ａ
）は位１バずれを吸収するととによつ℃正当ブ疋整合を
行なう例を示ず図で、同図（ｂ）は文字バタンの構造全
無視してあわせ禍ぎを行なっている例を示す図て゛ある
。ｌＡ２図は本発明の構成の一実施例を示すグｒコック
図、第３図は局所対応候補記憶部２の対応候補の情報全
示づ同図、第４図は類似度検出部３の具体的な構成の一
実施例に示すだめの７０ツク図である。図中１は局所対
応検出部、２は局所対応候補記憶部、３は類似度検出部
、４は部分評価値検出部、５は累積局所対応記憶部、６
は部分評価値加算部、７は最小値検出部である。

訓・１図 （ａ）　（ｂ） ″”４７７図 １　２　５ 第３図 第４図 −−／

Claims (1)

【特許請求の範囲】
1. 一嘴子化された文字バタン或いは図形バタンから４４１
   られるｌ特徴バタンを用いて類似度をめる袋層において
   、一方のバタンを分割した各部分バタンと前記各Ｍｌｊ
   分パクンに対応する他力（・つバタンの複数個のずらし
   ７部分バタンとの間の部分整合値と位置ずれ情報をめ、
   前記各部分バタンの対応の候補となるずらし部分バタン
   との部分整合値と位ｅずれ情報をめる局所対応検出部と
   、前記局所対応検出部で得られた対応候補情報を記憶す
   る局所対応記憶部と、前記局所対応候補記憶部に格納さ
   れた前記部分整合値と位置ずれ情報のうち、位置ずれ情
   報を用いて、対応する部分バタン間の位相の相対関係１
   保存するようにあらかじめ定められた構造保存の条件を
   満足する標準バタンの各部分バタンと入力バタンの各す
   ら１〜部分バタンの複数の対応関係をめ、前記複数の対
   応関係について、それぞれ前記部分整合価を用いてあら
   かじめ定められた評価関数によ、って得ら第１る全体の
   整合値をめ、前記複数の整合値の中から最逼値を類似度
   とし２て出力する類似度検出部とを有することにより、
   二次元バタンとしての構造に保存り、　７；ｃがら、位
   置ずれ吸収した類似度をめることを特徴とした類似度検
   出装置。