JPH0789362B2 - 非線形正規化方法 - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明は、２次元図形の非線形正規下方式に関するも
のである。

〔従来の技術〕

パターン認識、特に文字認識の手法は、通常、重ね合せ
法と構造解析法の２つに分けられる。従来、重ね合せ法
は印刷文字に対して、また構造解析法は手書き文字に対
して用いられてきた。しかし、近年の手書き漢字認識の
研究においては、次のような理由により、手書き漢字に
対しても重ね合せ法が広く用いられるようになってきて
いる。

（１） 字種が多く、辞書の自動学習が容易であること （２） 形が複雑で、構造解析法では特徴の組合せ数が
発散すること （３） 高次特徴による重ぬ合せ法という考え方が導入
され、重ね合せ法の適用範囲が広がったこと等である。

重ね合せ法では、通常、未知入力パターンと標準パター
ンの整合（マッチング）に先立って、未知入力パターン
の大きさや位置をそろえる（規格化する）処理が行われ
る。これを正規化と呼ぶ。重ね合せ法では、標本点の位
置は固定であるとの仮定にたってマッチングを行うた
め、標本点の位置をなるべく合せる正規化の処理が特に
重要になるのである。

従来、正規化は、外接多角形の情報や、重心等モーメン
トの情報を用い、位置，大きさ，傾きが一定になるよう
変換するものであった。そこでの変換は、旧座標を（X,
Y）、変換後の新座標を（Ｘ′,Y′）としたとき、 で表される範囲に限られる。この変換はアフィン変換と
呼ばれ、旧座標の直線は新座標でも直線になるなどの性
質を持ち、数学的な扱いも容易である。しかし、手書き
文字では形が部分的に変形することを考えれば、この線
形的な変換だけでは不十分である。

このような線形的変換の持つ限界を克服するために、文
献Ａ（山田，斎藤，山本“非線形正規化の一手法”、電
子通信学会論文誌Ｄ、J67−Ｄ巻、11号、1984年11月）
では、線密度を均質化する非線形変換による正規化方式
が提案されている。そこでは、線密度として各点での縦
方向および横方向の線の数（黒成分との交差の数）が用
いられ、線の数と標本化間隔との積が一定になるように
X,Y軸それぞれ独立に再標本化のための非線形変換関数
の決定を行っている。すなわち、線密度として縦・横方
向の線の本数という大局的な特徴が用いられ、かつ縦・
横方向独立に（１次元的）非線形変換が行われている。
このような非線形変換によって２次元空間の有効利用と
標本点の位置の安定化が図られ、実験的にも認識率の向
上が得られたことが報告されている。

〔発明が解決しようとする問題点〕

しかし、変換がX,Yが互いに独立な１次元的変換である
ため、いくつかの不自然な例が見られる。その典型例が
第５図の“言”の下側の“口”の部分に如実に現れてい
る。すなわち、第５図（ａ）は入力図形、第５図（ｂ）
は従来の外接四角形による線形正規化図形、第５図
（ｃ）が文献Ａによる非線形正規化図形、第５図（ｄ）
がこの発明による非線形正規化図形であり、それぞれ1,
3,5,7,9,11,13の番号が付してあり、同じ番号のものが
それぞれ対応している。

入力像第５図（ａ）に対し、前記文献Ａによる非線形変
換（ｃ）では、左側の“三”の部分が異常に狭められて
いる。これは、“三”の横方向の線の数が０または１と
“口”の部分に比べて相対的に小さいため、縦方向に
“三”の部分が小さくなるように変換されたものであ
る。しかし、本来の線密度を均一化するように非線形変
換するという主旨からすれば第５図（ｄ）のように全体
のバランスを保った変形がされるべきである。第５図
（ｃ）のような不自然な変換は当然認識性能の向上に対
しても支障をきたしている。

この発明は、手書き文字のような不規則（非線形）に変
形するパターンに対する正規化において、２次元的、か
つ局所的な線密度を抽出することにより、自然な非線形
正規化を行う方式を提供することを目的とする。

〔問題点を解決するための手段〕

この発明にかかる非線形正規化方法は、外界のパター
ンを一定の標本化間隔γで観測して電気信号に変換して
標本値の集合としての２次元パターンｆ（Xi,Yj）,i＝
１〜I,j＝１〜Ｊを得、前記２次元パターンｆ（Xi,Y
j）から、２次元の各点（Xi,Yj）において、点（Xi,Y
j）の周りのＸ方向の線間隔とＹ方向の線間隔を求め、
これらの線間隔の逆数の最大値から点（Xi,Yj）の線
密度関数ｈ（Xi,Yj）を求め、新しい標本点（Ｘ′i,
Y′ｊ）の標本間隔（δi,εｊ）を前記（Ｘ′i,Y′ｊ）
における線密度関数ｈ（Xi,Yj）の値とδｉの積がｉを
変化させても平坦になるようにするとともに、線密度関
数ｈ（Xi,Yj）の値とεｊの積がｊを変化させても平坦
になるように定め、新しい標本点（Ｘ′i,Y′ｊ）に
おける正規化された標本値を、前記標本化間隔（δi,ε
ｊ）に基づいて非等間隔に再観測して求めるようにする
か、もしくは２次元パターンｆ（Xi,Yj）から再計算し
て求め、前記〜の順序において、，，，，
を実行することにより正規化パターンを得るようにし
たものである。

〔作用〕

この発明においては、各標本点でX,Yそれぞれの方向に
ついて局所的な線間隔を求め、縦方向と横方向の線間隔
の逆数の最大値として線密度を計算し、線密度と標本化
間隔との間に一定の関係が成り立つように再標本化もし
くは変換する。

〔実施例〕

まず、この発明の原理について説明する。

紙等に書かれた外界の情報を、TVカメラ等の観測装置に
よって電気信号に変換したものを ｆ（Xi,Xj）,i＝1,2……Ｉ ｊ＝1,2……Ｊ ……（２） とする。この時、Xi,Yjは外界の紙に定義されたＸ軸,Y
軸のそれぞれ第ｉ番目，第ｊ番目の標本点の座標であ
り、標本点の間隔はγである。また、それぞれの点の標
本値ｆは、外界の情報が白の時0,黒の時１の２値図形と
する。ここで、標本化される対象となった元の図形の標
本点以外の点、すなわち、連続座標系上での値は、 ｆ（x,y）＝ｆ（Xi,Yj） ……（３） ただし、 （Xi−１＝）Xi−γ＜ｘ≦Xi,Xo＝０ （Yj−１＝）Yj−γ＜ｙ≦Yi,yo＝０ であると考える。すなわち、標本点以外の連続座標系上
の値は、その座標が属する標本点の標本値に等しいと考
える。

ここで、点（Xi,Yj）における線密度ρ（i,j）を以下の
処理で求める。まずｘ方向の右エッジ の位置L1,L2および左エッジ の位置L3,L4を検出する。L1およびL3は点（Xi,Xj）の左
側、L2およびL4は右側に存在するエッジである（第６
図）。

L1＝max｛ｉ′|i′＜i,f（ｉ′,j）， ^f（ｉ′＋1,j）＝１｝ L2＝min｛ｉ′|i′≧i,f（ｉ′,j）， ^f（ｉ′＋1,j）＝１｝ L3＝max｛ｉ′|i′＜i, ^f（ｉ′−1,j）,f（ｉ′,j）＝１｝ L4＝min｛ｉ′|i′≧i, ^f（ｉ′−1,j）,f（ｉ′,j）＝１｝ ……（４） ただし、^fはｆの論理否定である。また、該当するｉ′
がない場合はその旨の指標（不定）が入っている。

次にL1,L2,L3,L4から、点（Xi,Yj）におけるｘ方向の線
間隔L_Xを計算する。

第６図はこのL_Xを示したものであり、黒丸が求める（X
i,Yj）、斜線は黒地、残りは白地、１点鎖線は中心を表
している。L_Xの式の右辺の後のアルファベットは、第６
図（ａ）〜（ｆ）に対応している。ｗは入力像の幅であ
り、上式の（ｃ），（ｂ），（ｆ）の場合は、文字線の
内側に比べ、ある程度大きな値とするために2wおよび4w
を入れている。（ｅ）は一番外側の黒地においては、内
側の長さのみを用いることを示している。

以上、各点におけるＸ方向の線間隔L_Xを求める方法につ
いて述べたが、Ｙ方向についても同様にL_yを求める。

次に、L_X,L_yから線密度ρを、基本的には逆数の最大値
として求める。

次に、ρ（i,j）のＸ軸、Ｙ軸への射影 を求める。

この射影された関数も、第（３）式と同様に、連続座標
系上で、 h_X（ｘ）＝h_X（Xi）,xi−γ＜ｘ≦Xi h_y（ｙ）＝h_y（Yi）,Yi−γ＜ｙ≦Yj ……（８） と考える。

次に、それぞれの関数の総和 を求める。

以上の準備のもとで、この発明の意図する正規化図形ｇ
（Ｘ′i,Y′ｊ）は次のように表現できる。

ｇ（Ｘ′i,Y′ｊ）,i＝1,2,……,I ｊ＝1,2,……Ｊ δ（ｉ）・h_x（Ｘ′ｉ）＝γ・C_x/I＝定数 Ｘ′ｉ−δ（ｉ）＝Ｘ′ｉ−１ ε（ｊ）・h_y（Ｙ′ｊ）＝γ・C_y/J＝定数 Ｙ′ｊ−ε（ｉ）＝Ｙ′ｊ−１ ……（10） すなわち、Ｘ軸の第ｉ番目の標本点Ｘ′ｉはその標本化
間隔δ（ｉ）と、その点における特性値h_x（Ｘ′ｉ）と
の積が一定になる場所に定められる。

Ｙ軸についても同様である（第４図（ｂ））。なお、定
数をγ・C_x/Iおよびγ・C_y/Jにするのは、正規化図形の
標本点数もＩ×Ｊにするためである。なお、第４図
（ａ）はＸ軸およびＹ軸への線密度の射影の図、第４図
（ｂ）は新しい標本点の位置を示す図、第４図（ｃ）は
正規化された図形の図である。

このような再標本化で得た正規化図形ｇ（Ｘ′i,Y′
ｊ）では線が均質に分布するようになり、２次元空間が
有効に利用されるようになる（第４図（ｃ））。このた
め、重ね合わせによるマッチングを行ったときに、変形
に対して安定な結果が得られるようになるのである。

以上がこの発明の原理であるが、第（10）式で表された
再標本化を行うため、まず、ｈの累積関数を次のように
定義する。

ここで、ｈは第（８）式で定義された連続座標系上での
関数である。

このようにすれば、正規化されあ標本化図形ｇ（Ｘ′i,
Y′ｊ）の標本点の位置（Ｘ′i,Y′ｊ）は、 Ｘ′ｉ＝｛x|dx（ｘ）＝ｉ・Cx/I｝ Ｙ′ｊ＝｛y|dy（ｙ）＝ｊ・Cy/J｝ ……（12） と計算される。

次にここの発明の実施例について説明する。

第１図にこの発明の一実施例のブロック図を示す。この
図において、101は対象となる像、102は標本化図形用バ
ッファ、103はＸ軸射影バッファ、104はＹ軸射影バッフ
ァ、105はＸ軸係数バッファ、106はＹ軸係数バッファ、
107は正規化図形用バッファ、110は観測装置、111は線
密度計算回路、112はＸ軸変換計算回路、113はＹ軸変換
計算回路、114は非線形正規化回路、121,122,123,124は
データバスを示す。

次に動作について説明する。

対象となる像101は、観測装置110を通して観測・２値化
され、標本化図形用バッファ102に蓄えられている。線
密度計算回路111において、この標本化図形を用い第
（５）式を計算し、次に第（６）式の計算を行い、さら
に第（７）式のごとくX,Y方向に加算を行い、結果をそ
れぞれＸ軸射影バッファ103およびＹ軸射影バッファ104
に入れる。

次にＸ軸変換計算回路112において、Ｘ軸射影用バッフ
ァ103の内容に対して第（11）式の計算を行うことによ
り、第（12）式の計算に用いるためのＩ個のＸ軸新座標
点の座標をＸ軸係数ハッファ105に入れる。ここで、第
（11）式および第（12）式ではdx（ｘ）は連続座標系上
で定義されているので、このままで計算できない。そこ
で、実際の計算は、 により行う。ｉ′は正規化図形のＸ軸の第ｉ番目の標本
点が元の標本図形の第ｉ′番目の標本点であることを示
すものである。このｉ′がＸ軸係数バッファ105の第ｉ
番目の考えられる。

同様にＹ軸についても、Ｙ軸変換計算回路113におい
て、Ｙ軸射影バッファ104の内容に対し、第（11）式
（実際は第（13）式と同様の式）に従って計算を行うこ
とにおり、Ｊ個のＹ軸新標本座標が求められ、Ｙ軸係数
バッファ106に入れられる。

最後に非線形正規化回路114の動作について説明する。

まず、Ｘ軸係数バッファ105の第ｉ番目の内容をｉ′、
Ｙ軸係数バッファ106の第ｊ番目の内容をｊ′とする。
このとき、非線形正規化回路114は標本化図形バッファ1
02からＸ軸の第ｉ′番目、Ｙ軸の第ｊ′番目の内容を取
り出して、正規化図形用バッファ107のＸ軸の第ｉ番
目、Ｙ軸の第ｊ番目に入れる。この操作をｉ＝1,2,…
…,I,J＝1,2,……,Jについて行うことにより正規化図形
用バッファ107の正規化図形が完成する。

［変形例１］ 上記実施例では、非線形正規化の際に、既に標本化され
た図形（第１図の標本化図形用バッファ102）を用いた
が、第１図の観測装置110から非線形正規化回路114への
破線で示すように、実施例のＸ軸係数バッファ105およ
びＹ軸係数バッファ106に求めた変換係数を用いて非線
形変換しながら観測装置110から再観測することができ
る。こ方式を実施例と比較すると、よりきめの細かい正
規化図形が得られる。また、第１図において、標本化図
形用バッファ102と正規化図形用バッファ107が共用でき
るのも特徴である。

［変形例２］ 上記実施例では、各点で線密度を求めた後、X,Y軸への
射影を取りX,Y軸の１次元の変換関数として再標本化の
点を求めている。結果的には、第４図においてメッシュ
分割は非等間隔ではあるが、分割線は直線であるのが特
徴である。

これに対して、より２次元的な変換とするために射影は
取らず、２次元上の密度関数そのものを用い、２次元的
な変換を行うことができる。そこでは、結果としてでき
るメッシュは非等間隔であると同時に分割線は曲線（実
際は折線）である。以下、その例を示す。

第（６）式において、各点で線密度ρ（i,j）を求めた
後、 を求める。これは、線密度を２×２に分割して加算した
ものである。その上で非線形変換（Xi,Yj）→（Ｘ′i,
Y′ｊ）を次のように行う。

Yj≦Y J/4のとき Yj≧Y 3J/4のとき Y J/4＜Yj＜Y 3J/4のとき Ｘ′ｉ＝Ｘ′（i,j） ＝（Y3J/4−Yj）・Ｘ′（i,J/4）/Y J/2 ＋（Yj−Y J/4）・Ｘ′（i,3J/4）/Y J/2 ……（15） Ｙ方向の変換Yj→Ｙ′ｊ＝Ｙ′（i,j）もＸ方向と同様
に求める。

上記Ｘ′（i,j）、Ｙ′（i,j）により、変換（Xi,Yj）
→（Ｘ′i,Y′ｊ）を行う。ここでＸ′,Y′は、点（i,
j）毎に、すなわち、２次元的に求まっている点が第（1
0），（12），（13）式による実施例と異なる点であ
る。

第２図は、h11:h21:h21:h22＝1:3:4:2の場合の非線形変
換による空間の歪みの例を示している。なお、アイウエ
オ…は対応する領域を示す。

なお、この例では、２×２分割によって変換を求めてい
るが、この方式を1/4の領域に対して繰り返し階層的に
適用することにより、より精密な変換が可能である。

第３図に上記の方式を実現するための回路構成を示す。

第３図において、201は対象とする像、202は標本化図形
用バッファ、203は線密度バッファ、204は正規化図形用
バッファ、210は観測装置、211は線密度計算回路、212
は非線形正規化回路、221,222,223,224はデータバスを
示す。

第３図を、第１図の実施例と比較すると、線密度計算回
路111または211の出力が、上記実施例ではX,Y独立なバ
ッファであったのに対し、変形例２で線密度バッファ20
3が２次元的になっている。したがって、非線形正規化
回路212における入力も２次元情報に変わっている。な
お、第３図破線のように再観測によるより精密な正規化
が可能なのは実施例の場合と同様である。

［変形例３］ ２×２の粗い分割に対して、変形例２の方式を用いた
後、４×４に分割されたマス目に対して、実施例に述べ
た射影による方式を用いることが可能である。

この場合、大局的な２次元的変形に対しては、変形例２
の２次元的変形を行い、局所的変形の吸収は処理が単純
な射影方式を用いることになる。

第５図（ａ），（ｂ），（ｃ），（ｄ）は、先に説明し
たようにこの発明の実施例に示された方法により正規化
された図形と、従来の正規化図形とを比較したものであ
る。この図からこの発明によれば従来の非線形正規化法
に比べてより自然的な正規化図形が得られていることが
わかる。

この方法の効果については、手書き文字認識実験によっ
ても確かめられている。下記の表にその結果を示す。

実験条件 実験データ：電総研手書き教育漢字データベースETL8
（956字種160データセット）計956×160字のうち、奇数
番データセットを辞書作成に用いデータセット２および
34で評価を行った。

線形正規化：文字の外接四角形を正方形に正規化する。

非線形正規化1:前述の文献Ａに述べられている方式。

非線形正規化2:この発明の実施例による正規化。

〔発明の効果〕

以上詳細に述べたように、この発明は、外界のパター
ンを一定の標本化間隔γで観測して電気信号に変換して
標本値の集合としての２次元パターンｆ（Xi,Yj）,i＝
１〜I,j＝１〜Ｊを得、前記２次元パターンｆ（Xi,Y
j）から、２次元の各点（Xi,Yj）において、点（Xi,Y
j）の周りのＸ方向の線間隔とＹ方向の線間隔を求め、
これらの線間隔の逆数の最大値から点（Xi,Yj）の線
密度関数ｈ（Xi,Yj）を求め、新しい標本点（Ｘ′i,
Y′ｊ）の標本間隔（δi,εｊ）を前記（Ｘ′i,Y′ｊ）
における線密度関数ｈ（Xi,Yj）の値とδｉの積がｉを
変化させても平坦になるようにするとともに、線密度関
数ｈ（Xi,Yj）の値とεｊの積がｊを変化させても平坦
になるように定め、新しい標本点（Ｘ′i,Y′ｊ）に
おける正規化された標本値を、前記標本化間隔（δi,ε
ｊ）に基づいて非等間隔に再観測して求めるようにする
か、もしくは２次元パターンｆ（Xi,Yj）から再計算し
て求め、前記〜の順序において、〜を実行する
ことにより正規化パターンを得るようにしたので、部分
的に標本化間隔を変えながら変換しつつ、より自然な正
規化図形を得ることができる。このため、手書き文字の
ように部分的に変換したパターンに対しても、重ね合せ
法を有効に用いることができる利点がある。

【図面の簡単な説明】

第１図はこの発明の一実施例を示すブロック図、第２図
はこの発明の変形例において２次元的変換の際の分割升
目の変化の様子を示した図、第３図はこの変形例を実現
するためのブロック図、第４図（ａ），（ｂ），（ｃ）
は実施例による処理過程を示す図、第５図（ａ），
（ｂ），（ｃ），（ｄ）はこの発明の実施例により正規
化された図形および従来の方式により正規化された図形
を示す図、第６図はＸ方向の線間隔の定義を示す図であ
る。 図中、101は像、102は標本化図形用バッファ、103はＸ
軸射影バッファ、104はＹ軸射影バッファ、105はＸ軸係
数バッファ、106はＹ軸係数バッファ、107は正規化図形
用バッファ、108は正規化図形用バッファ、110は観測装
置、111は線密度計算回路、112はＸ軸変換計算回路、11
3はＹ軸変換計算回路、114は非線形正規化回路、121,12
2,123,124はデータバスである。

───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 昭60−251482（ＪＰ，Ａ) 電子通信学会論文誌，Ｖｏｌ．67−Ｄ, Ｎｏ．11，（1984−11），Ｐ．1379−1383

Claims (1)

【特許請求の範囲】
1. 【請求項１】外界のパターンを一定の標本化間隔γで
   観測して電気信号に変換して標本値の集合としての２次
   元パターンｆ（Xi,Yj）,i＝１〜I,j＝１〜Ｊを得、前
   記２次元パターンｆ（Xi,Yj）から、２次元の各点（Xi,
   Yj）において、点（Xi,Yj）の周りのＸ方向の線間隔と
   Ｙ方向の線間隔を求め、これらの線間隔の逆数の最大
   値から点（Xi,Yj）の線密度関数ｈ（Xi,Yj）を求め、
   新しい標本点（Ｘ′i,Y′ｊ）の標本間隔（δi,εｊ）
   を前記（Ｘ′i,Y′ｊ）における線密度関数ｈ（Xi,Yj）
   の値とδｉの積がｉを変化させても平坦になるようにす
   るとともに、線密度関数ｈ（Xi,Yj）の値とεｊの積が
   ｊを変化させても平坦になるように定め、新しい標本
   点（Ｘ′i,Y′ｊ）における正規化された標本値を、前
   記標本化間隔（δi,εｊ）に基づいて非等間隔に再観測
   して求めるようにするか、もしくは２次元パターンｆ
   （Xi,Yj）から再計算して求め、前記〜の順序にお
   いて、，，，，を実行することにより、線間
   隔が均一化された正規化パターンを得るようにしたこと
   を特徴とする非線形正規化方法。