JPH0479034B2

JPH0479034B2 -

Info

Publication number: JPH0479034B2
Application number: JP58169755A
Authority: JP
Inventors: Atsushi Tsukumo
Original assignee: Nippon Electric Co Ltd
Current assignee: NEC Corp
Priority date: 1983-09-14
Filing date: 1983-09-14
Publication date: 1992-12-14
Also published as: JPS6061874A

Description

【発明の詳細な説明】

本発明は二次元格子上の量子化パタンに変換さ
れた手書き文字パタン或いは図形パタンの照合を
行なうための類似度検出装置に関する。従来２つのパタン間の類似度を評価する手法と
しては、比較的手軽な処理によつて得られるユー
クリツド距離、ハミング距離、単純類似度や、印
刷漢字認識で用いられた複合類似度、音声認識で
用いられたDPマツチング法がある。複合類似度
は印刷文字のように比較的狭い範囲で統計的な変
動がある二次元パタンについては効果が知られて
おり、またDPマツチング法は一次元上の非線形
の変動を吸収することは知られているが、手書き
文字パタン或いは簡単な手書き図形パタン等のよ
うに二次元的でしかも局所的に異なつた変動をす
るパタンへの適用は困難であつた。そこで手書き文字の変形は、文字パタンにおい
て局所的に起こることから、入力文字パタンと、
標準文字パタンをそれぞれ部分パタンで表わし、
各部分パタンをそれぞれ独立にずらしながら整合
を行ない、各部分パタンにおいて、最もよく整合
のとれたものを対応させ、それらの全体から入力
文字パタンと標準文字パタンとの類似度を求める
手法が提案されている。（山田他「類似度法の一
改良−ずらし類似度−」電子通信学会論文誌
Vol、J64−Ｄ、No.10、1981／10）この類似度は例えば第１図ａに示すような位置
ずれの変形を吸収する反面、第１図ｂに示すよう
な文字パタンの構造を破壊した合わせすぎの悪影
響も伴なつており、合わせ過ぎを防止しようとす
ると、位置ずれの変形を吸収する能力に欠ける点
が問題である。上記の問題が起こる理由は、各部分パタンにお
いて最適整合値d_k,lを求めるときに、二次元図形
としての位相を無視していることから起こるもの
で、第１図ｂの合わせすぎの例はまさに位相を無
視することによつて起こつたものである。そこで上記問題を解決するために、上記各部分
パタンのずらしの整合を求めるときに、各部分パ
タン間の位相情報を考慮することにより、二次元
図形としての構造を保存しながら、従来通り位置
ずれの変形を吸収し、かつ文字パタンの構造を破
壊した合わせすぎを防止して類似度を求める方法
が同一出願人による特願昭58−125811号明細書
「類似度検出装置」により提案されている。さて文字認識や図形認識で類似度装置を使用す
る場合に、認識対象や認識環境によつて類似度装
置に対する要求が異なつていることはよく知られ
ている。認識環境としては、不特定筆記者用認識
と少人数または個人の特定筆記者用認識とに分け
ることができ、後者では、前者に比べて、認識対
象の文字或いは図形の変形が限られている。従つ
て後者の場合には前者の場合に比べて、変形の吸
収よりも合わせ過ぎを防止する必要がある。本発明の目的は、特定筆記者の認識環境で、部
分的な位置ずれの変形を吸収する類似度検出装置
を改良し、合わせ過ぎの防止の効果を強めた類似
度検出装置を提供することにある。以下本発明について図面を用いて詳細に説明を
行なう。第２図は、本発明の構成の一実施例を示すブロ
ツク図である。１はずらし対応検出部であり、一
方のパタンを分割した各部分パタンを信号１０と
して、前記各部分パタンに対応する他方のパタン
の複数個のずらし部分パタンを信号１１として入
力し、前記各部分パタンと、前記各部分パタンに
対応する前記複数個のずらし部分パタンとの整合
値d⁽ⁱ⁾ _klとずらしの位置情報（x⁽ⁱ⁾ _kl，y⁽ⁱ⁾ _kl）を信号
１２
として出力する。ここで記号d⁽ⁱ⁾ _klは、一方のパタ
ンをＫ×Ｌに分割したパタンA_kl（Ｋ＝１，…，
Ｋ：ｌ＝１，…，Ｌ）と前記部分パタンに対応す
る他方のパタンの複数個のずらし部分パタンB⁽ⁱ⁾ _kl
との整合値を表わし、記号（x⁽ⁱ⁾ _kl，y⁽ⁱ⁾ _kl）は、前記
部分パタンA_klと前記ずらし部分パタンB⁽ⁱ⁾ _klの位置
ずれ情報を表わしている。２は局所対応候補記憶
部であり、前記各ｋ、ｌについて、前記部分パタ
ンA_klに対する候補となる前記各ずらし部分パタ
ンB⁽ⁱ⁾ _klとの前記整合値d⁽ⁱ⁾ _klと前記位置ずれ情報とを
信号１２として入力し、格納する。３は局所対応
検出部であり、前記各部分パタンA_klに対する前
記候補となる各ずらし部分パタンB⁽ⁱ⁾ _klとの整合値
d⁽ⁱ⁾ _klと位置ずれ情報（x⁽ⁱ⁾ _kl，y⁽ⁱ⁾ _kl）とを信号１３
とし
て入力し、前記各部分パタンA_klに対応するずら
し部分パタンB^(ikl) _klを、前記候補となるずらし部分
パタンB⁽ⁱ⁾ _klの中から求め、前記各部分パタンA_klと
前記ずらし部分パタンB^(ikl) _klとの各位置ずれ情報
（x^(ikl) _kl，y^(ikl) _kl）を信号１４として出力する。４
は
局所対応補正部であり、信号１４として前記各位
置ずれ情報（x^(ikl) _kl，y^(ikl) _kl）を入力し、相互に隣
接
する位置ずれ情報を用いて、隣接する位置ずれの
量の変化を抑制するように補正した位置ずれ情報
（x′_kl，y′_kl）を求め、前記補正した位置ずれ情報
（x′_kl，y′_kl）を信号１５として出力する。５は類
似度検出部であり、信号１５として前記補正した
位置ずれ情報（x′_kl，y′_kl）を入力とし、前記局所
対応候補記憶部２から前記補正した位置ずれ情報
（x′_kl，y′_kl）と等しい前記候補となる位置ずれ情
報（x⁽ⁱ⁾ _kl，y⁽ⁱ⁾ _kl）に対応する整合値d⁽ⁱ⁾ _kl（＝d′_k
lとする）
を信号１３として読みだし、前記各整合値d′_klに
よつて２つのパタンの類似度を求め、信号１７と
して出力する。図中ずらし対応検出部１および局所対応検出部
２は、前述の特願昭58−125811号明細書「類似度
検出装置」の中で説明されているように、従来の
文字認識技術で容易に実現できるものである。次に局所対応検出部３の一実施例を図を用いて
詳細に説明する。第３図は前記局所対応候補記憶部２上の対応候
補の情報を示す図であり、d⁽ⁱ⁾ _klは整合値、x⁽ⁱ⁾ _kl，y^(
i) _kl
はずらしの位置情報である。ここで二次元図形構
造を保存する条件とは、単に相対位置関係を保存
する条件としては、前記各部分パタンA_klに対応
する前記ずらし部分パタンをB^(ikl) _klとし、前記部分
パタンA_klの座標を（I_kl，J_kl） I_kl＋x^(ikl) _kl＜I_k+1,l＋x^(ik+1,l) _k+1,l J_kl＋y^(ikl) _kl＜J_k+1,l＋y^(ik,l+1) _k,l+1 (1) を満たすことであり、上記条件を満さない場合に
は、左右または上下を逆転して対応させることに
なる。次に相対位置関係の他に各部分パタンの対
応が比較的滑らかに変化する条件を加えると I_kl＋x^(ikl) _kl＋C_kl＜I_k+1,l＋x^(ik+1,l) _k+1,l J_kl＋y^(ikl) _kl＋C_kl＜J_k,1+1＋y^(ik,l+1) _k,l+1 (2) となり、更に I_kl＋x^(ikl) _kl＋C_kl＜I_k+1,l＋x^(ik+1
,l) _k+1,l≦I_kl＋x^(ikl) _kl＋C′_kl I_kl＋x^(ikl) _kl＋C_kl＜I_k+1,l＋x^(ik+1
,l) _k+1,l≦I_kl＋x^(ikl) _kl＋C′_kl J_kl＋y^(ikl) _kl＋C_kl＜J_k,1+1＋y^(ik,l+1) _k,l+1≦J_kl＋y
^(ikl) _kl＋C′_kl(3) とすることもできる。条件(2)は部分対応をとつた
ときに、局所的に縮小する度合を制限するもので
あり、条件(3)は更に部分対応をとつたときに局所
的に伸長する度合を制限するものである。これは
手書き文字パタン等の変動が、局所的ではある
が、連続的な変化をしている条件と見ることがで
きる。前記局所対応検出部３は上記条件(1)または(2)ま
たは(3)を満たすような各部分パタンA_klに対応す
るx^(ikl) _kl，y^(ikl) _klを求め、前記x^(ikl) _kl，y^(ikl) _klに対応する
d^(ikl) _klによつて得られる評価値Ｄを最小にする
（x^(ikl) _kl，y^(ikl) _kl）の組合せを決定する。第４図は前記局所対応検出部３の具体的な構成
の一例を示すためのブロツク図である。６は部分
評価値検出部であり、信号１３として前記整合値
d⁽ⁱ⁾ _kl及び位置情報（x⁽ⁱ⁾ _kl，y⁽ⁱ⁾ _kl）とを読み込み、
ｄ（n
_０）０，ｌ，ｄ（n₁）１，ｌ，…，ｄ（n_k-1）ｋ−１，ｌ（n₀＝１，
…Ｎ；…；n_k-1＝１，…，Ｎ）の組み合わせに対
するあらかじめ定められた部分評価値d_l（n_p，…，
n_k-1）を求め、各部分評価値と位置情報（x⁽ⁱ⁾ _p,l，
y⁽ⁱ⁾ _p,l）、…，（x⁽ⁱ⁾ _k-1,l，y⁽ⁱ⁾ _k-1,l）（＝１，…
，Ｎ）とを
信号６１として出力する。前記部分評価値D_e
（n₀，…，n_k-1）はN^k通りあり、例えばＫ＝４，
Ｎ＝４のときはD_l（１，１，１，１）、…、D_l（４，
４，４，４）の256通りである。前記部分評価値
D_l（n₀，…，n_k-1）は各（x⁽ⁱ⁾ _kl，y⁽ⁱ⁾ _kl）が前記構造
を
保存する条件を満たさない場合には無限大とみな
し、充分大きな値を与える。７は累積局所対応記
憶部であり、前記位置情報（x⁽ⁱ⁾ _kl，y⁽ⁱ⁾ _kl）と累積部
分評価値D_l（n₀，…，n_k-1）を格納する。８は部
分評価値加算部であり、前記部分評価値検出部６
から信号６１として前記部分評価値d_l+1（n₀，…，
n_k-1）と前記位置情報（x⁽ⁱ⁾ _p,l+1，y⁽ⁱ⁾ _p,l+1）…
（x⁽ⁱ⁾ _k-1,l+1，y⁽ⁱ⁾ _k-1,l+1）（ｎ＝１，…，Ｎ）を読
み込
み、同時に前記累積局所対応記憶部７から各位置
情報（x⁽ⁱ⁾ _p,l，y⁽ⁱ⁾ _p,l）、…、（x⁽ⁱ⁾ _k-1,l，y⁽ⁱ⁾ _k-1
,l）（ｉ＝１，
…，Ｎ）と各累積部分評価値D_l（n′_p，…，n′_k-1）
を信号７１として読み込み、前記各累積部分評価
値D_l（n′_p，…，n′_k-1）について、前記各位置情報
が前記構造保存の条件を満たす関係にある前記部
分評価値d_l+1（n₀，…，n_k-1）のうち、最小のもの
を加算し、新しく得られた加算結果を新たにD_l+1
（n′₀，…，n′_k-1）とし前記位置情報（x⁽ⁱ⁾ _p,l+1，
y⁽ⁱ⁾ _p,l+1）、…、（x⁽ⁱ⁾ _k-1,l+1，y⁽ⁱ⁾ _k-1,l+1）とと
もに信号７
２として前記局所対応記憶部に書き込む。もし位
置情報（ｘ（n′₀）ｏ，ｌ，ｙ（n′₀）ｏ，ｌ）、…、（x⁽ⁿ′^k-1) _k-1,l，
y⁽ⁿ′^k-1) _k-1,l）と各位置情報（x⁽ⁱ⁾ _k,l+1，y⁽ⁱ⁾ _k,l+1）とが前記
構造保存の条件を満たさない場合には、前記新し
い累積部分評価値D_o+1（n′₀，…，n_k-1）は無限大
とみなし、充分大きな値を与える。この処理は次
のような漸化式を実行している D_l+1（n′₀，…，n′_k-1）＝D_l（n′₀，
…，n′_k-1）＋ min n₀ n_k-1（cond）｛d_l+1（n₀，…，n_k-1）｝ D_e0（n′₀，…，n′_k-1）＝０ただし記号min（cond）は前記構造保存を満た
すもののうちの最小値を示すものとする。９は最
小値検出部であり、前記漸化式の処理を繰り返し
行なうことによつて得られるK^N通りの累積評価
値D_L-1（n₀，…，n_k-1）を信号７３として入力し、最小値 min− １≦n₀≦Ｎ１≦n_k-1≦Ｎ D_L-1（n₀，…，n_k-1）となる（n₀，…，n_k-1）の
組合せに対応する各（x^(ikl) _kl，y^(ikl) _kl）を信号１４
と
して出力する。図中、部分評価値検出部６は構造保存の条件の
ための比較器や、評価値を求めるための加算器等
の演算器や、評価値を格納するためのレジスタ等
によつて容易に構成できる。また累積局所対応記
憶部７は一般に使用される記憶素子でよい。部分
評価値加算部８も評価値を格納するレジスタ、構
造保存の条件のための比較器、加算器等の演算器
等によつて容易に構成できる。また最小値検出部
９も比較器及びレジスタ等によつて容易に構成で
きる。続いて局所対応補正部４の一実施例を詳細に説
明する。信号１４として入力される前記各位置ず
れ情報（x^(ikl) _kl、y^(ikl) _kl）を簡単のため（x_kl、y_kl）と
書くことにすると、前記各補正した位置ずれ情報
（x′_kl、y′_kl）を例えば各ｋ、ｌ（ｋ＝２、…、Ｋ−
１；ｌ＝２、…、Ｌ−１）について

【表】とすることにより位置ずれの量を平滑化すること
ができる。第５図は位置ずれの補正の効果を示すものであ
る。ａに示す16個の点a₁₁、…、a₄₄に対してｂに
示す各位置ずれ情報〓_kl＝（x_kl、y_kl）（ｋ＝１、
…、４；ｌ＝１、…４）を用いて対応づけを行な
うと、かなり歪んだ対応となり異なつた図形或い
は文字間の合わせ過ぎの原因となる。そこで前述
の(4)を用いて補正を行なつた各位置ずれ情報〓′_k
_ｌ（x′_kl、y′_kl（ｋ＝１、…、４；ｌ＝１、…４）に
よる対応づけはｃに示すようになり、ｂに比べ歪
みが緩和され合わせ過ぎが防止できる。また(4)は
補正の一例であり、実験的に補正の式の重みづけ
を求めてもよい。このような補正を行なう局所対
応補正部は加算器、レジスター等によつて容易に
構成できる。また類似度検出部５は前記各整合値
d′_klを用いて等の式によつて類似度を決定するものであり、従
来の文字認識技術で容易に構成することができ
る。また類似度を決定する式は(5)の３個の例に限
るものではない。以上の説明より本発明によれば、文字或いは図
形の認識において、文字或いは図形の変形がある
程度限定される少人数或いは個人の特定筆記者と
いう認識環境での合わせ過ぎを防止することがで
きる。

【図面の簡単な説明】

第１図ａ，ｂは２つの文字パタンの整合の例を
示し、同図ａは位置ずれを吸収することによつて
正当な整合を行なう例を示す図で、同図ｂは文字
パタンの構造を無視してあわせ過ぎを行なつてい
る例を示す図、第２図は本発明の構成の一例を示
すブロツク図、第３図は局所対応候補記憶部２の
対応候補の情報を示す図、第４図は局所対応検出
部３の構成の一例を示すためのブロツク図、第５
図ａ，ｂ，ｃは位置ずれの補正の効果を示す図で
ある。図中１はずらし対応検出部、２は局所対応候補
記憶部、３は局所対応検出部、４は局所対応補正
部、５は類似度検出部、６は部分評価値検出部、
７は累積局所対応記憶部、８は部分評価値加算
部、９は最小値検出部、１０は一方のパタンの部
分パタン信号、１１は他方のパタンのずらし部分
パタン信号、１３は部分パタン間の候補となる整
合値とずらし位置情報を示す信号、１４は位置ず
れ情報を示す信号、１５は補正した位置ずれ情報
を示す信号、１７は類似度となる出力信号を示し
ている。

Claims

【特許請求の範囲】

１量子化された文字パタン或いは図形パタンか
ら得られる特徴パタンを用いて類似度を求める装
置において、一方のパタンを分割した各部分パタ
ンと、前記各部分パタンに対応する他方のパタン
の複数個のずらし部分パタンとの間の各部分整合
値と位置ずれ情報を求め、前記各部パタンの対応
の候補となるずらし部分パタンとの部分整合値と
位置ずれ情報を求めるずらし対応検出部と、前記
ずらし対応検出部で得られた対応候補情報を記憶
する局所対応候補記憶部と、前記局所対応候補記
憶部に格納された前記部分整合値と位置ずれ情報
のうち、位置ずれ情報を用いて、対応する部分パ
タン間の位相の相対関係を保存するように、あら
かじめ定められた構造保存の条件を満足する、一
方のパタンの各部分パタンと他方のパタンの各ず
らし部分パタンのずらしの対応関係を求める局所
対応検出部と、前記局所対応検出部で得られたず
らしの対応関係を、相互に隣接する前記対応関係
を用いて相対的なずらしの量を平滑化することに
よつて、前記ずらしの対応関係を補正する局所対
応補正部と、前記局所対応補正部によつて得られ
た対応関係と、前記局所対応候補記憶部に格納さ
れている前記部分整合値と位置ずれ情報とを用い
ることにより類似度を求める類似度検出部を有す
ることにより、位置ずれを吸収し、かつ合わせ過
ぎを防止することを特徴とする類似度検出装置。