JPS646512B2

JPS646512B2 -

Info

Publication number: JPS646512B2
Application number: JP57139059A
Authority: JP
Inventors: Kazuhiko Yamamoto; Taiichi Saito
Original assignee: Agency of Industrial Science and Technology
Current assignee: National Institute of Advanced Industrial Science and Technology AIST
Priority date: 1982-08-10
Filing date: 1982-08-10
Publication date: 1989-02-03
Also published as: US4566124A; JPS5930179A

Description

【発明の詳細な説明】

この発明は、１回の輪郭追跡でパターンの凹凸
構造を抽出できるようにしたパターンの線分近似
方式に関するものであり、指定したしきい値の大
きさにより抽出したい凹凸の程度を制御すること
ができ、また、近似点に方向の属性が与えられる
ため凹凸構造の抽出が容易にできることを特徴と
するものである。パターンの特徴を抽出する場合、線分によつて
そのパターンを近似し、線分の連鎖でパターンの
凹凸構造を表現することが多い。本出願人による
特開昭53−41136号公報（パターン読取方式）に
記載した発明では、輪郭を追跡し16方向の最外点
を求める最外点リスト法でパターンの凹凸構造を
求め、凹構造の内部に凸構造がある場合は、その
凹構造の内部をもう一度追跡し最外点を見つける
ことによつて、内部凸構造を求めるという方法を
とつている。この発明はその最外点リスト法を改良し、１回
の輪郭追跡でパターンの凹凸構造を内部構造をも
含めその抽出を容易にしようとするもので、指定
した許容値以下の微細な凹凸を無視した多角形近
似が得られる方式である。以下、まず最外点リス
ト法について説明し、次いでこの発明の局所最外
点リスト法の説明を行う。第１図は最外点を求めるときの各方向ｉと、そ
の方向ベクトルe_iを示している。方向ｉの最外点
とは、第２図に示すように、輪郭点ベクトルa_jの
方向ベクトルe_iへの射影第(1)式｜a_j｜・cosθ_ij＝｜a_j｜・（a_j、e_i）／｜a_j｜、｜e
_i｜＝（a_j、e_j）／｜e_i｜ ………(1) が最大となる点で、a_kが方向ｉの最外点となる。
こゝで、θ_ijは輪郭点ベクトルa_jと方向ベクトルe_i
とのなす角である。各16方向について最外点を求
めるにはパターンの輪郭を追跡しながら各方向ご
とに第(1)式が最大となる点を記憶していくと、全
輪郭点につき１回追跡を行つた時点で記憶されて
いる点が最外点となり、この隣り合う方向の最外
点を結んだ線がそのパターンの凸閉包となる。こ
のとき最大値の検出は各方向ごとに行うため、第
(1)式の分母で割る必要はなく、また、e_iのｘ，ｙ
成分は第１図のように、０、±１、±２であるから
内積（a_ji、e_i）はシフト、加算、補数演算のみで
計算できる。以上が最外点リスト法であり、この発明の局所
最外点リスト法は、上述の内積計算に許容値との
大小判定と、局所最外点を出力した方向のスイツ
チ処理を加え、多角形近似がなされるように改良
したものである。以下、この発明について説明す
る。なお、簡単にするため第１図の16方向から偶
数番の方向を除いた８方向で説明する。第３図はこの発明の一実施例を説明するための
図である。まず、輪郭を追跡するときの開始点を発見す
る。これはパターンを走査することにより行わ
れ、最上部、最左端の点になる。第３図では点
P₁がこれにあたる。この点P₁から輪郭を追跡し
て行き、局所最外点を求めるわけであるが、点
P₁は方向13の最外点候補であり、右まわりに輪
郭追跡を行うことから、はじめは方向13、15、
１、３の局所最外点が出力される可能性がある。
そこで、第４図ａのように局所最外点出力スイツ
チのうち、方向５、７、９、11のものをオン（〇
で囲んで示す）、方向13、15、１、３のものをオ
フにしておく。こゝで局所最外点を出力する場合
の許容値εを設け、ある方向の局所最外点候補と
追跡中の輪郭点のその方向への射影の差がε以上
になつたとき、局所最外点候補を局所最外点とし
て出力するようにする。このεは吸収しようとす
る微細な凹凸の程度によつて決められるもので、
ε＝０とすればパターンの輪郭線そのままが表現
され、こゝでは“０”でない第３図に両端矢印で
示す値とする。射影計算は第(1)式で表わされ、｜e_i｜は必ずし
も“１”ではないが、これは各方向に対して、｜
e_i｜×εを用意することにより内積（a_j、e_i）計
算だけで済むことになる。点P₁から輪郭追跡し
て行き、各輪郭点で全方向について内積（a_j、e_i）
を計算し、局所最外点出力スイツチがオフの方向
全てに対し射影の差がε以上かどうか判定を行
う。ε以上でない場合は、現輪郭点と局所最外点
候補の射影の大きい方を局所最外点候補とする。
ε以上のものがあつた場合は、局所最外点候補を
局所最外点として出力し、出力した方向の局所最
外点出力スイツチをオン、出力した方向と180度
の方向の局所最外点出力スイツチをオフにし、現
輪郭点を局所最外点候補とする。局所最外点出力スイツチがオンの方向について
は、輪郭追跡方向がその方向とは離れる方向に進
んでおり、すでに局所最外点が出力されているこ
とから、強制的に現輪郭点を局所最外点候補とす
る。第３図では点P₂で点P₁との方向13に対する
射影の差δ₂′がε以上になり、点P₁を方向13の局
所最外点として出力し、第４図ａで、方向13の局
所最外点出力スイツチをオン、方向５の局所最外
点出力スイツチとオフにする。点P₃では点P₁と
の方向15に対する射影の差δ₃′がε以上になるた
め、点P₁を方向15の局所最外点として出力し、
方向15の局所最外点出力スイツチをオン、方向７
の局所最外点出力スイツチをオフにする。点P₄
を通過した時点では、第４図ｂのように局所最外
点出力スイツチは、方向１、３、５、７がオフ、
９、11、13、15がオンの状態になつており、点
P₅では点P₄との方向７に対する射影の差δ⁴ ₅がε以
上となり、点P₄を方向７の局所最外点として出
力する。このような方法で輪郭を追跡しながら許容値ε
以上になつた時点で局所最外点を出力することに
より、点P₃と点P₄の間や、点P₂₅と点P₂₆の間にあ
るε以下の微細な凹凸を無視したパターンの多角
形近似が得られる。第３図では局所最外点として
P₁，P₄，P₆，P₈，P₁₁，P₁₃，P₁₆，P₁₈，P₂₁，
P₂₄，P₂₆，P₂₉が出力される。従来の最外点リス
ト法では、P₁，P₁₀，P₁₈，P₂₁，P₂₆のみが最外点
として出力される。追跡開始時にいくつかの方向の局所最外点出力
スイツチをオンにしておく理由は、例えば第５図
の様なパターンの場合に全てのスイツチをオフに
しておくと支障をきたすためである。それは第５
図において、スイツチを全てオフにしておくと、
開始点q₀から追跡を始め、ある程度右方向（太線
矢印）に進んだ段階で方向９、７、11の順に開始
点q₀が局所最外点として出力されてしまう。開始
点q₀は方向13だけの局所最外点であり、方向７と
方向９の局所最外点は点q₁、方向11の局所最外点
は点q₂である。上記の不都合を防ぐために、いく
つかの方向のスイツチをオンにしておくのであ
る。実際のパターン（第６図）の多角形近似をε＝
０として行うと第７図のようになり、ε＝２とす
ると第８図のようになる。第８図の場合の局所最
外点リストを下記第１表に示す。また、第９図の
ようなうず巻状のパターンも第１０図のように多
角形近似される。以上の多角形近似から凹凸構造を抽出する１例
を第８図と第１表に従つて説明する。第８図中の
番号（No.）は第１表のNo.に一致する。第８図にお
いて、No.２からNo.11の点までの線分近似点が凹構
造であることを機械的に調べてみる。第１表でNo.
１からNo.４までの局所最外点方向は方向13から方
向16へ時計回りに進んでおり、No.５の点で方向16
と反対の方向８に逆転し、No.８の局所最外点方向
５へ反時計回りに進み、No.９でまた方向が逆転し
ている。これは局所最外点方向の逆転が凹と凸の
変り目付近であることを示している。これより局
所最外点方向の変化が時計回りから方向を逆転し
た点の３つ手前の点（No.２）と反時計回りから方
向を逆転した２つ先の点（No.11）までをとれば、
これが凹構造であると言える。凸についても同
様、第１表において反時計回りからNo.９で局所最
外点方向が逆転する１つ手前の点（No.８）と時計
回りから方向が逆転する点（No.17）をとると、No.
８からNo.17の点までが凸構造として抽出できる。
この様にこの発明の多角形近似方式による多角形
近似点から凹凸構造を抽出することが容易である
ことが示される。第１１図はこの発明を実施するための装置の一
例を示すブロツク図である。第１１図の装置の構
成を動作とともに説明する。まず、オアゲート１に開始信号P_sを入れ、フリ
ツプ・フロツプ２をＱ＝１とする。これでスター
ト・ポイント・サーチ・モード（走査モード）に
し、制御部３にその状態を知らせる。走査モード
では主走査をｘ方向、副走査をｙ方向とし、背景
“０”からパターン上の“１”に到達するまでメ
モ

【表】

【表】リ４を走査する。“１”がデータ・レジスタ５に
入つた時点のｘ方向のアドレス・レジスタ６と、
ｙ方向のアドレス・レジスタ７の内容を、それぞ
れｘ方向、ｙ方向のスタート・ポイント・レジス
タ８，９に格納し、フリツプ・フロツプ２を逆転
させ追跡モードにする。このスタート・ポイン
ト・レジスタ８，９は、次にアドレス・レジスタ
６，７がスタート・ポイント・レジスタ８，９と
同じになる。つまり輪郭追跡を一周した時点で処
理を終らせるためのものである。追跡を開始する前に、局所最外点出力スイツチ
１０の16方向のうち、５〜１２をオン、それ以外
をオフにし、内積演算器１１によりスタート・ポ
イントの各方向ベクトルへの射影（a_k、e_i）を計
算し、局所最外点候補内積レジスタ１２に各方向
ごとに（a_k、e_i）を入れ、局所最外点候補座標レ
ジスタ１３の全方向にスタート・ポイント座標を
入れる。こゝで、各方向に対する許容値｜e_i｜・εとベ
クトルe_iの要素は、それぞれ許容値レジスタ１４
とベクトル・レジスタ１５に前もつて入れてある
ものとする。追跡モードでは、各輪郭点a_jごとに内積演算器
１１で現輪郭点内積計算（a_j、e_i）を行い内積レ
ジスタ１６に格納する。その後、局所最外点出力
検出信号で、局所最外点出力スイツチ１０のオフ
の方向について、局所最外点候補内積レジスタ１
２のｉ方向の内積（a_k、e_i）と、内積レジスタ１
６のｉとは逆方向ｒ＝mod16（ｉ＋７）＋１の内積
（a_j、e_r）との和を加算器１７で計算する。方向
ｉと方向ｒにおける内積の和は、e_iとe_rが逆方向
の方向ベクトルで、e_r＝−e_iという関係があるこ
とから、（a_k、e_i）＋a_j、e_r）＝（a_k、e_i）−（a_j、e_i）とな
り、ｉの方向ベクトルへの射影の差を計算してい
ることに対応し、回路を簡単にするための和とし
て計算している。こゝで、局所最外点出力スイツチ１０、局所最
外点候補内積レジスタ１２のｉ方向の内容と、内
積レジスタ１６のｒ方向の内容は、これらのシフ
ト・レジスタがｉ―１回シフトされたときのそれ
ぞれ１番目、９番目のものを取り出す（以下同
様）。さて上記の和が許容値以上のとき比較器１８か
ら信号を出し、局所最外点候補座標レジスタ１３
のｘ，ｙ座標を局所最外点出力レジスタ１９に出
力し、局所最外点出力スイツチ１０の方向ｉをオ
ン、方向ｒをオフにする。この和が許容値以下の
ときは局所最外点候補内積レジスタ１２の（a_k、
e_i）と内積レジスタ１６の（a_j、a_i）を比較器２
０で比較し、（a_k、e_i）＜（a_j、e_i）の場合、局所最
外点候補内積レジスタ１２のｉ方向の内容を現輪
郭点a_jのものに入れかえ、（a_k、e_i）（a_j、e_i）
の場合は何もしない。局所最外点出力スイツチ１
０がオンの方向ｉについては強制的に現輪郭点の
（a_j、e_i）とｘ，ｙ座標をそれぞれ局所最外点候補
内積レジスタ１２と局所最外点候補座標レジスタ
１３に入れる。このことを全輪郭点について行うことにより、
局所最外点出力レジスタ１９に出力された点がパ
ターンの多角形近似点となる。なお、第１１図中、CMは比較器、PGはパル
ス発生器、RCはリングカウンタ、Ｇはゲートア
レーで、複線がデータの流れ、単線がデータの流
れを通過・阻止する信号である。ANDはアンド
ゲート、IANDはインヒビツトアンドゲート、
INHはインヒビツトゲート、ORはオアゲート、
INVはインバータである。これらの説明は省略
する。以上詳細に説明したように、この発明は局所最
外点リスト法において、内積計算に許容値との大
小判定を行なつて最大内積の出力を行うようにし
たので、１回の輪郭追跡によりパターンの多角形
近似ができ、許容値の大きさにより抽出したい凹
凸の程度を制御でき、さらに文字認識等に用いる
凹凸個数等の位相的特徴もまた容易に抽出できる
利点がある。

【図面の簡単な説明】

第１図は局所最外点を求めるときの各方向ｉと
その方向ベクトルを示す図、第２図はこの発明に
用いる最外点抽出の原理説明図、第３図は同じく
この発明に用いる局所最外点抽出による抽出過程
説明図、第４図ａ，ｂは局所最外点出力スイツチ
の動作説明図、第５図は局所最外点出力スイツチ
の初期セツトを求める特殊パターン例を示す図、
第６図は対象とする文字パターンの図、第７図、
第８図はその読みとりパターンの図、第９図は対
象とするうず巻状パターンの図、第１０図はその
読みとりパターンの図、第１１図はこの発明の局
所最外点抽出回路図である。図中、１はオアゲート、２はフリツプ・フロツ
プ、３は制御部、４はメモリ、５はデータ・レジ
スタ、６，７はアドレス・レジスタ、８，９はス
タートポイント・レジスタ、１０は局所最外点出
力スイツチ、１１は内積演算器、１２は局所最外
点候補内積レジスタ、１３は局所最外点候補座標
レジスタ、１４は許容値レジスタ、１５はベクト
ル・レジスタ、１６は内積レジスタ、１７は加算
器、１８は比較器、１９は局所最外点出力レジス
タ、２０は比較器である。

Claims

【特許請求の範囲】

１対象とするパターンの輪郭または中心の座標
点を追跡し、その部分座標点列の中で座標点ベク
トルといくつかの限定した方向ベクトルの内積が
最大になる点を最大内積点として求め、各方向ベ
クトルとの内積と前記最大内積点の内積との差が
定められたしきい値以上のとき前記最大内積点を
出力し、この出力された最大内積点をパターンの
輪郭または中心等の線分近似点とすることを特徴
とするパターンの線分近似方式。