JPH01116892A

JPH01116892A - 非線形正規化方法

Info

Publication number: JPH01116892A
Application number: JP62276900A
Authority: JP
Inventors: Hirozo Yamada; 山田　博三; Taiichi Saito; 泰一斉藤; Kazuhiko Yamamoto; 和彦山本
Original assignee: Agency of Industrial Science and Technology
Current assignee: National Institute of Advanced Industrial Science and Technology AIST
Priority date: 1987-10-30
Filing date: 1987-10-30
Publication date: 1989-05-09
Anticipated expiration: 2010-09-27
Also published as: JPH0789362B2

Abstract

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

Description

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

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

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

重ね合せ法では、通常、未知入カバターンと標準パター
ンの整合（マツチング）に先立って、未知入カバターン
の大きさや位置をそろえる（規格化する）ｌＡ理が行わ
れる。これを正規化と呼ぶ。

重ね合せ法では、標本点の位置は固定であるとの仮定に
たってマツチングを行うため、標本点の位置をなるべく
合せる正規化の処理が特に重要になるのである。

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

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

（発明が解決しようとする問題点〕しかし、変換がＸ、Ｙが互いに独立な１次元的変換であ
るため、いくつかの不自然な例が見られる。その典型例
が第５図の“言”の下側の“口”の部分に如実に現れて
いる。すなわち、第５図（ａ）は入力図形、第５図（ｂ
）は従来の外接四角形による線形正規化図形、第５図（
Ｃ）が文献Ａによる非線形正規化図形、第５図（ｄ）が
この発明による非線形正規化図形であり、それぞれ１゜
３．５，７，９．１１．１３の番号が付してあり、同じ
番号のものがそれぞれ対応している。

入力像第５図（ａ）に対し、前記文献Ａによる非線形変
換（Ｃ）では、左側の“三”の部分が異常に狭められて
いる。これは、“三”の横方向の線の数が０または１と
“口”の部分に比べて相対的に小さいため、縦方向に“
三”の部分が小さくなるように変換されたものである。

しかし、本来の線密度を均一化するように非線形変換す
るという主旨からすれば第５図（ｄ）のように全体のバ
ランスを保りた変形がされるべきである。第５図（Ｃ）
のような不自然な変換は当然認識性能の向上に対しても
支障をきたしている。

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

（問題点を解決するための手段〕この発明にかかる非線形正規化方式は、標本化間隔γで
標本化された２次元パターンｆ（Ｘｉ。

Ｙｊ）、ｉ＝１〜Ｉ、　ｊ＝ｘ〜Ｊから局所的な線密度
関数ｈ　（Ｘｉ、Ｙｊ）を線間隔の逆数として求める手
段と、新しい標本点（Ｘ′ｉ、ｙ′ｊ）の標本化間隔（
δｉ、εｊ）を（Ｘｉ、Ｙｊ）における前記線密度ｈ　
（Ｘｉ、Ｙｊ）と（δｉ、εｊ）との積が一定になるよ
うに定める手段と、前記新しい標本点（ｘ′ｉ、Ｙ′ｊ
）における正規化された標本値を、再標本化して求める
か、もしくは前記２次元パターンｆ　（Ｘｉ、Ｙｊ）か
ら再計算して求める手段とからなるものである。

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

〔実施例】

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

標本化間隔γで標本化された２値図形をｆ　（Ｘｉ、Ｙ
ｊ）、　　　ｉ＝１．２・・・・・・工ｊ＝ｔ、２・・
・・・・Ｊ・・・・・・　（２）とする。（Ｘｉ、Ｙｊ）はＸ軸、Ｙ軸のそれぞれ第１番
目、第ｊ番目の標本点の座標である。また、これをｆ　
（ｉ、ｊ）とも表す。ここで、標本化される対象となっ
た元の図形の標本点以外の点、すなわち、連続座標系上
での値は、ｆ　（ｘ、ｙ）＝ｆ　（Ｘｉ、ｙｊ）　　　
・・・・”　　（３）ただし、（Ｘｉ−１＝）Ｘｉ−ｙ＜ｘ≦Ｘｉ、Ｘｏ＝０（Ｙｊ−
１＝）Ｙｊ−γくｙ≦Ｙｊ、ｙｏ＝０であると考える。

すなわち、標本点以外の連続座標系上の値は、その座標
が属する標本点の標本値に等しいと考える。

ここで、点（Ｘｉ、Ｙｊ）における線密度ρ（ｔ、ｊ）
を以下の処理で求める。まずＸ方向の右エツジ（−シ〕
の位置Ｌｌ、Ｌ２および左エツジ（Ｊ）の位置Ｌ３．Ｌ
４を検出する。ＬｌおよびＬ３は点（ｘｉ、Ｙｊ）の左
側、Ｌ２およびＬ４は右側に存在するエツジである（第
６図）。

Ｌｌ−ｍａｘ（ｉ’　　ｌｉ’　　＜ｉ、ｆ（ｉ’　　
、ｊ）、”ｆ（ｉ’　　＋１．ｊ）−１）Ｌ２−ｍｉｎ
（ｉ’　　ｌｉ’　　≧ｉ、　　ｆ（ｉ’　　、ｊ）、
”ｆ（ｉ’　　＋１．ｊ）−１）Ｌ３−ｍａｘ　（ｉ’
　　ｌ　ｉ’　＜　ｉどｆ（ｉ’　−１，Ｊ）、　ｆ（
ｉ’　　、ｊ）−１）Ｌ４＝ｍｉｎ（ｉ’　Ｉｆ’≧ｉ
、’ｆ（ｉ’　−１，ｊ）　、　ｆ（ｉ’　、ｊ）−１
）・・・・・・（４）ただし、−ｆはｆの論理否定である。また、該当するｉ
′がない場合はその旨の指標（不定）が人フている。

次にＬｌ、Ｌ２．Ｌ３．Ｌ４から、点（Ｘｉ。

Ｙｊ）におけるＸ方向の線間隔Ｌ８を計算する。

［（Ｌ２−Ｌ１＋Ｌ４−Ｌ３）／２その他　　　　（ａ
）　　（ｄ）・・・・・・　（５）第６図はこのＬ８を示したものであり、黒丸が求める（
Ｘｌ、ＹＪ）％斜線は黒地、残りは白地、１点鎖線は中
心を表している。Ｌｘの式の右辺の後のアルファベット
は、第６図（ａ）〜（ｆ）に対応している。Ｗは入力像
の幅であり、上式の（Ｃ）　、　（ｂ）　、　（ｆ）の
場合は、文字線の内側に比べ、ある程度大きな値とする
ために２Ｗおよび４Ｗを入れている。（ｅ）は一番外側
の黒地においては、内側の長さのみを用いることを示し
ている。

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

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

・・・・・・　（６）次に、ρ（ｉ　、ｊ）のＸ軸、Ｙ軸への射影を求める。

この射影された関数も、第　（３）式と同様に、連続座
標系上で、ｈＸ（ｘ）　＝　ｈｘ（Ｘ　ｉ　）　、　Ｘ　ｉ−ｙ＜
ｘ≦Ｘ１ｈｙ（ｙ　）　−ｈｙ（Ｙ　ｉ　）　、　Ｙ　
Ｊ−γくｙ≦Ｙｊ・・・−（８）と考える。

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

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

ｇ　（Ｘ’　　ｉ、Ｙ’　　ｊ）、１＝＝ｌ、２．・・
・・・・、Ｉｊ＝ｔ、２．・・・・・・Ｊ δ（ｉ）　・ｈＸ（ｘ’　　ｔ）＝γ・Ｃｘ／Ｉ＝定数
Ｘ’定数Ｘ−δ（ｉ）＝Ｘ’ｉ−１ ε（ｊ）・ｈｙ（Ｙ′ｊ）＝γ・Ｃ，／Ｊ＝定数Ｙ′　
ｊ−ε（ｉ）＝Ｙ′ｊ−１・・・・・’−（ｔｏ）すなわち、Ｘ軸の第ｉ番目の標本点ｘ′　ｉはその標本
化間隔δ（ｉ）と、その点における特性値り、（Ｘ’　
　ｉ）との積が一定になる場所に定められる。

Ｙ軸についても同様である（第４図（ｂ））。

なお、定数をγ・Ｃ，／Ｉおよびγ・Ｃ，／Ｊにするの
は、正規化図形の標本点数もＩＸＪにするためである。

なお、第４図（ａ）はＸ軸およびＹ軸への線密度の射影
の図、第４図（ｂ）は新しい標本点の位置を示す図、第
４図（Ｃ）は正規化された図形の図である。

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

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

ｄｘ　（ｘ）　＝　ｆ　　ｈｘ　（ｕ）／ｙ　　ｄｕｄ
ｙ　（ｙ）　＝　ｆ　　ｈｙ　（ｖ）／ｙ　　ｄｖ・・
・・・・（１１）ここで、ｈは第　（８）式で定義された連続座標系上で
の関数である。

このようにすれば、正規化された標本化図形ｇ（ｘ′ｉ
、Ｙ′ｊ）の標本点の位置（Ｘ′ｉ、Ｙ′ｊ）は、Ｘ’１＝（ｘｌｄｘ（ｘ）＝ｉ　　−Ｃｘ／Ｉ）Ｙ′ｊ
＝（ｙｌｄｙ（ｙ）＝Ｊ　　−Ｃｙ／Ｊ）・・・・・−
（１２）と計算される。

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

第１図にこの発明の一実施例のブロック図を示す。この
図において、１０１は対象となる像、１０２は標本化図
形用バッファ、１０３はＸ軸射影バッファ、１０４はＹ
軸射影バッファ、１０５はＸ軸係数バッファ、１０６は
Ｙ軸係数バッファ、１０７は正規化図形用バッファ、１
１０は観測装置、１１１は線密度計算回路、１１２はＸ
軸変換計算回路、１１３はＹ軸変換計算回路、１１４は
非線形正規回路、１２１，１２２，１２３゜１２４はデ
ータバスを示す。

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

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

次にＸ軸変換計算回路１１２において、Ｘ軸線密度用バ
ッファ１０３の内容に対して第　（１１）式の計算を行
うことにより、第（１２）式の計算に用いるための１個
のＸ軸新座標点の座標をＸ軸体数バッファ１０５に入れ
る。ここで、第　（１１）式および第　（１２）式では
ｄｘ　（ｘ）は連続座標系上で定義されているので、こ
のままでは計算できない。そこで、実際の計算は、により行う。ｉ′は正規化図形のＸ軸の第ｉ番目の標本
点が元の標本図形の第ｉ′番目の標本点であることを示
すものである。このｉ′がＸ軸体数バッファ１０５の第
ｉ番目に蓄えられる。

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

最後に非線形伸縮回路１１４の動作について説明する。

まず、Ｘ軸係数バッファ１０５の第ｉ番目の内容をｉ′
、Ｙ軸係数バッファ１０６の第ｊ番目の内容をｊ′とす
る。このとき、非線形伸縮回路１１４は標本化図形バッ
ファ１０２からＸ軸の第ｉ′番目、Ｙ軸の第ｊ′番目の
内容を取り出して、正規化図形、用バッファ１０７のＸ
軸の第ｉ番目、Ｙ軸の第ｊ番目に入れる。この操作をｉ
＝１．２．・・・・・ｅ、Ｉ、Ｊ＝１．２．・・・−、
Ｊについて行うことにより正規化図形用バッファ１０７
の正規化図形が完成する。

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

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

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

以下、その例を示す。

第　（６）式において、各点で線密度ρ（ｔ、ｊ）を求
めた後、を求める。これは、線密度を２×２に分割して加算した
ものである。その上で非線形変換（Ｘｉ。

Ｙｊ）→（Ｘ’　　ｉ、Ｙ’　　ｊ）を次のように行う
。

■Ｙｊ≦ＹＪ／４のときｘ′　ｉ＝Ｘ′　（ｉ、ｊ）／　（ｈｌｌ＋ｈ２１）　。

ＸＩ／２　＜Ｘ　ｉ　＜ＸＩ ■Ｙｊ≧Ｙ３Ｊ／４のときＸ’　　ｉ＝Ｘ’　　（ｉ、ｊ）／　（ｈ１２＋ｈ２２）。

ＸＩ／２　＜Ｘ　ｉ　＜ＸＩ ■ＹＪ／４　＜Ｙ　ｊ　＜Ｙ３Ｊ／４のときＸ’　　１
＝＝Ｘ’　　（ｉ、ｊ）＝　（Ｙ３Ｊ／４−Ｙｊ）　・Ｘ’（ｉ、Ｊ／４）／Ｙ
Ｊ／２　　＋　　（Ｙ　ｊ　−ＹＪ／４　　）　　・Ｘ
′（ｉ　、　　３Ｊ／４）　／ＹＪ／２・・・・・・（１５）Ｙ方向の変換Ｙｊ−４ｙ’　ｊ＝Ｙ’　　（ｉ、ｊ）も
Ｘ方向と同様に求める。

上記Ｘ’　　（ｉ、ｊＬ　Ｙ’　　（ｉ、ｊ）により、
変換（Ｘｉ、Ｙｊ）−＋　（Ｘ’　　ｔ、Ｙ’　ｊ）を
行う。ここでＸ’　、Ｙ’は、点（ｔ、ｊ）毎に、すな
わち、２次元的に求まっている点が第　（１０）　。

（１２）　、　（１３）式による実施例と異なる点であ
る。

第２図は、ｈｌｌ：　ｈ２１：　ｈ２１：　ｈ２２冨１
：３：４：２の場合の非線形変換による空間の歪みの例
を示している。なお、アイウェオ・・・は対応する領域
を示す。

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

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

第３図において、・２０１は対象とする像、２０２は標
本化図形用バッファ、２０３は線密度バッファ、２０４
は正規化図形用バッファ、２１０は観測装置、２１１は
線密度計算回路、２１２は非線形正規化回路、２２１，
２２２．２２３はデータバスを示す。

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

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

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

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

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

実験条件実験データ：電総研手書き教育漢字データベースＥＴＬ
８　（９５６字種１６０データセツト）計９５６Ｘ１６０字のうち、奇数番データセットを辞・書作成に用いデータセット２および３４で評価を行った。

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

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

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

〔発明の効果〕

以上詳細に述べたように、この発明は、標本化間隔δで
標本化された２次元パターンｆ　（Ｘｉ。

Ｙｊ）、ｉ＝１〜Ｉ、　ｊ＝１〜Ｊから局所的な線密度
関数ｈ　（Ｘｉ、Ｙｊ）を線間隔の逆数として求める手
段と、新しい標本点（Ｘ′ｉ、Ｙ′ｊ）の標本化間隔（
δｉ、εｊ）を（Ｘｉ、Ｙｊ）における線密度ｈ　（Ｘ
ｉ、Ｙｊ）と（δｉ、εｊ）との積が一定になるように
定める手段と、前記新しい標本点（Ｘ′ｉ、Ｙ′ｊ）に
おける正規化された標本値を、再標本化して求めるか、
もしくは２次元パターンｆ　（Ｘｉ、Ｙｊ）から再計算
して求める手段を持つようにしたので、部分的に標本化
間隔を変えながら変換しつつ、より自然な正規化図形を
得ることができる。このため、手書き文字のように部分
的に変換したパターンに対しても、重ね合せ法を有効に
用いることができる利点がある。

【図面の簡単な説明】

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

Claims

【特許請求の範囲】

標本化間隔γで標本化された２次元パターンｆ（Ｘｉ、
Ｙｊ）、ｉ＝１〜Ｉ、ｊ＝１〜Ｊから局所的な線密度関
数ｈ（Ｘｉ、Ｙｊ）を線間隔の逆数として求める手段と
、新しい標本点（Ｘ′ｉ、Ｙ′ｊ）の標本化間隔（δｉ
、εｊ）を（Ｘｉ、Ｙｊ）における前記線密度ｈ（Ｘｉ
、Ｙｊ）と（δｉ、εｊ）との積が一定になるように定
める手段と、前記新しい標本点（Ｘ′ｉ、Ｙ′ｊ）にお
ける正規化された標本値を、再標本化して求めるか、も
しくは前記２次元パターンｆ（Ｘｉ、Ｙｊ）から再計算
して求める手段を持つことを特徴とする非線形正規化方
式。