JPS6255191B2

JPS6255191B2 -

Info

Publication number: JPS6255191B2
Application number: JP56159467A
Authority: JP
Inventors: Shiro Atsumi; Sadamasa Hirogaki
Original assignee: Oki Electric Industry Co Ltd
Current assignee: Oki Electric Industry Co Ltd
Priority date: 1981-10-08
Filing date: 1981-10-08
Publication date: 1987-11-18
Also published as: JPS5862767A

Description

【発明の詳細な説明】本発明は、三角形、四角形、五角形、六角形、
円、長円および楕円等の図形形状や、物体形状を
識別分類する装置に関するものである。

例えば、電子計算機にプログラムを入力するた
めには、一般に、フローチヤートを作成した後コ
ーデイングを行ない、カードやテープなどにパン
チしてから入力機器により入力するという手順を
踏んでいる。このため、多くの手数を必要として
いる。そこで、フローチヤートを認識しうる入力
機器があれば、フローチヤートから直接電子計算
機にプログラムを入力することが可能であり、そ
の省力効果は絶大である。

ところで、フローチヤートを認識するために
は、まずフローチヤートに使用される記号、すな
わち処理（長方形）、判断（菱形、六角形）、端子
（長円）、結合子（五角形、円、三角形）などを識
別分類することが重要である。

本発明は、上述した図形形状の識別分類を極め
て簡単な処理で実施できるようにすることを目的
とし、図形の輪郭線を直線近似しつつ追跡し、隣
接する二直線の交角から図形の角を検出すると同
時に、抽出線分情報と抽出角情報とから図形を円
類と角類とに分類する認識論理を備え、認識精度
を向上したことを特徴とするものであり、以下詳
細に説明する。

第１図は本発明第１の実施例のブロツク図であ
り、読取部１は平面図形を光学的に読み取り、図
形を構成する線分の各点の座標に対応する電気信
号を提供する。読取部１の出力は、例えばデイジ
タル形式とする。読取部１により読み取つた図形
パターンの外形である輪郭点を、輪郭追跡部２に
て追跡する。その後、線分・角抽出部３により線
分情報、角情報を抽出した後、円／角分類部４に
おいて円類と角類との分類を行なう。こうして得
られた各種情報にもとづいて、形状判定部５にお
いて読取り図形の識別分類を行なう。なお輪郭点
追跡部２は、４連結―境界線追跡アルゴリズム
〔電子通信学会論文誌56―Ｄ巻11号667〜668頁
（1973年11月）〕等公知の技術を用いて差し支えな
く、４連結―境界線追跡アルゴリズムにて得られ
た輪郭線の一例を第２図に示した。

第２図Ａは長円の輪郭線例であり、第２図Ｂは
菱形の輪郭線例である。

線分および角の抽出方法について、第３図のフ
ローチヤートを用いて説明する。記憶装置に格納
されている輪郭点座標を所定の間隔ｄにて取り出
す。例えば一番最初は、輪郭の第１番目の点（P₁
と略称する）と第（１＋ｄ）番目の点（Ｐ_1+dと
略称する）が取り出される。この２点を各々始
点、終点とする線分を暫定線分Ｌとする。中間の
輪郭点、すなわち第２番目の点P₂と暫定線分Ｌと
の距離D₂が所定の閾値Δｌ以内であれば、第３
番目の点P₃との距離D₃…、第ｄ番目の点Ｐ_dとの
距離Ｄ_dという具合に順次所定の閾値Δｌ以内で
あるか否かを判別し、もし距離がΔｌをこえる点
があつたらその点を終点とし、D₁を始点とする
線分を抽出線分S₁とし、距離がすべてΔｌ以内で
あるときは、Ｌを抽出線分S₁とする。抽出線分S₁
の終点を始点とし、ｄだけ隔たつた点を終点とす
る線分を暫定線分Ｌとして、中間の輪郭点とＬと
の距離から上記と同様の操作を行なつて抽出線分
Ｓを決定する。抽出線分Ｓと、一回前に抽出され
た抽出線分（この場合はS₁）との交角θ_１を算出
し、θ_１が直線化判定角θ_sよりも大きい場合は
抽出線分Ｓを抽出線分S₂とし、θ_１が直線化判定
角θ_２よりも小さい場合は抽出線分Ｓと抽出線分
S₁とを一本化する。すなわち、S₁の始点を始点と
し、Ｓの終点を終点とする線分を改めて抽出線分
S₁とする。また、交角θ_１が直線化判定角θ_sよ
りも大きい場合には、更に交角θ_１が角判定角θ
_Lよりも大きいか否かを調べ、大きい場合には検
出角数に１を加える。

以上を整理すると、現在の抽出線分Ｓと一回前
に抽出された抽出線分S₁との交角θ_１を算出し、 θ_１≦θ_Sのとき S₁とＳとを一直線とみなした線分をS₁とす
る。

θ_S＜θ_１≦θ_LのときＳを抽出線分S₂とし、S₁とS₂とが弧をなして
いると判断する。

θ_L＜θ_１のときＳを抽出線分S₂とし、S₁とS₂との交点が図形
の角であると判断する。

ということになる。

上記操作を輪郭線に沿つて、輪郭線の１周分を
なぞり終るまで順次繰り返す。

理解が容易なるよう、第４図の具体例を用いて
説明を補うことにする。図中の黒点は輪郭点であ
り、破線は輪郭線の一部分である。所定の間隔ｄ
＝８、所定の閾値Δｌ＝２の場合を仮定して説明
を進める。まずP₁を始点、P₉を終点とする線分を
暫定線分Ｌとすると、中間の輪郭点P₂〜P₈とＬと
の距離D₂〜D₈はすべてΔｌ以内であるから、Ｌ
を抽出線分S₁とする。次にP₉を始点、P₁₇を終点
とする線分₉・₁₇を暫定線分Ｌとして、中間の
輪郭点との距離を調べるとD₁₄＞Δｌとなるか
ら、暫定線分Ｌを線分₉・₁₄に変更し、抽出線
分Ｓは線分₉・₁₄となる〔第４図Ａ〕。そこでS₁
とＳとの交角θ_１を調べると、直線化判定角θ_S
よりも小さいから、ＳをS₁と一本化して、抽出線
分S₁を線分₁・₁₄に変更する。次いで線分₁₄・
P₂₂を暫定線分Ｌとして、中間の輪郭点との距離
を調べると、すべてΔｌ以内であるからＬを抽出
線分Ｓとする。そこでS₁とＳとの交角θ_１を調べ
ると、直線化判定角θ_Sよりも大きいからＳを抽
出線分S₂として登録する。すなわち、抽出線分S₂
＝線分₁₄・₂₂である。

ところで、交角θ_１は角判定角θ_Lよりも大き
いから、検出角数に１を加え（最初は検出角数＝
０であるから、検出角数＝１となる）ると同時
に、抽出角K₁としてθ_１を登録する〔第４図
Ｂ〕。

次に線分₂₂・₃₀を暫定線分Ｌとして、中間の
輪郭点との距離を調べると、すべてΔｌ以内であ
るからＬを抽出線分Ｓとする。そこでS₂とＳとの
交角θ_２を調べると、直線化判定角θ_sよりも大
きいからＳを抽出部分S₃として登録する。すなわ
ち、抽出線分S₃＝線分₂₂・₃₀である。ところで
交角θ_２は角判定角θ_Lよりも小さいから、検出
角数は不変であり、抽出角Ｋの登録は行なわれ
ず、交角θ_２が格納されるだけである〔第４図
Ｃ〕。

このような操作を、輪郭線の１周分をなぞり終
るまで順次繰り返すわけである。

１周分をなぞり終つた時点には、抽出線分情報
と抽出角情報とが得られている。しかしながら、
きつちり１周をなぞつただけでは、最後の抽出線
分Ｓ_oと最初の抽出線分S₁との接続関係がわから
ないから、Ｓ_oとS₁との交角θ_oを求めて、上記と
同様の操作、すなわちθ_o＞θ_L＞θ_SのときＳ_oを
正式な抽出線分として登録すると共に検出角数に
１を加え、抽出角Ｋ_nとしてθ_oを登録する。また
θ_L≧θ_o＞θ_Sのとき、抽出線分Ｓ_oと交角θ_oを
正式に登録する。またθ_L＞θ_S≧θ_oのとき、Ｓ_o
とS₁とを一体化した線分を抽出線分S₁として登録
しなおすことが必要である。こうして、線分情報
と角情報との抽出が完了する。

第２図に示した輪郭線例の線分・角抽出結果例
を第５図に示す。なお、各パラメータの設定値を
所定の間隔ｄ＝８、所定の閾値Δｌ＝２、直線化
判定角θ_S＝15゜、角判定角θ_L＝30゜とした場合
の抽出結果である。

さて、こうして得られた線分情報と角情報とか
ら図形の形状を識別分類するわけであるが、検出
角数がｍだからといつて、いきなりｍ角形である
と決めることはできない。何故なら、線分・角抽
出結果例第５図Ａからも明らかな通り、長円、楕
円、円などの円類においても角が検出されてしま
うからである。勿論、角判定角θ_Lを大きく設定
しておけば、円類から角を検出しないようにする
ことはできるが、θ_Lを無制限に大きく設定する
ことはできない。というのは、六角形や菱形にお
いては交角θがかなり小さくなるため、θ_Lを大
きくすと、交角の小さな角を弧と誤判断してしま
う恐れがあるからである。この矛盾を解決するた
めには、円類／角数分類論理を併用することが非
常に有効である。すなわち、正三角形、正方形、
長方形、菱形、六角形など角類の角検出が正確に
行なわれるように角検出角θ_Lなどのパラメータ
値を設定しておき、角類の形状識別には検出角数
を最大限利用し、円類の形状識別においては検出
角数をあまり重視しないという考え方である。

第６図のフローチヤートを用いて、円類／角類
分類論理を説明する。

認識対象多角形の角数の上限値をｎ（例えば三
角形から六角形までを識別分類すればよい場合に
は、ｎ＝６である）とすると、検出角数が２以下
のときと検出角数が（ｎ＋１）以上のときは円類
であるが、ｎ≧検出角数≧３のときは円類である
可能性もあり、角類である可能性もある。

そこで、検出角数の検出線数に対する比（検出
角数／検出線数）を角数比と名付けると、もし角
数の抽出が角類に対して正確に行なわれるように
しておけば、角類では検出角数＝検出線数である
から角数比は１のはずであり、円数では多くの弧
が抽出されるが、検出角数は０のはずであるから
角数比は０となる。しかしながら、線分・角抽出
に多少の誤差を生じた場合には、角類の角数比は
１よりやや減少し、円類の角数比は０よりやや増
加する。第５図に示した実測例の場合も、円類で
ある長円が角数比＝３／11＝0.27、角類である菱
形が角数比＝４／６＝0.67となつている。

それゆえ、円類識別閾値k₀を０よりやや大きい
適当な値に設定し、角数比がk₀以下のものを円類
と識別する。また、角数識別閾値k₁を１よりやや
小さな適当な値に設定し、角数比がk₁以上のもの
を角類と識別する。かくして、ほとんどの図形は
円類と角類とに識別分類することができるが、確
実性を重視して、角類識別閾値k₁をかなり１に近
く設定し、円類識別閾値k₀をかなり０に近く設定
すると、k₁＞角数比＞k₀となつてしまう図形もあ
る。その場合には、更に交角偏差を利用すると確
実性が高くなる。交角偏差とは、抽出した交角θ
_１〜θ_oの最大値から最小値を引いた値であり、
円類の場合は交角偏差値が小さく、角類の場合は
交角偏差値が大きいから、適当な閾値Δθとの大
小に応じて各々角類、円類に識別分類することが
できる。その理由は、円類の場合、本来はすべて
の交角θ_１〜θ_oは直線化判定角θ_Sと角判定角θ
_Lとの間の値になるはずであるが、その時は検出
角数＝０であるから、交角偏差の判断に来る前に
すでに円類と識別分類されており、この判断部に
到達したということは、少なくとも１ケの検出角
があつたということである。すなわち、大半の交
角θはθ_L≧θ＞θ_Sであるか、たまたまθ＞θ_L
なる交角θもあつたということである。しかしな
がら、θ＞θ_Lなる交角もそう極端にθ_Lをこえて
いるはずはないから、交角偏差＝θ_nax―θ_nio
は、たかだかθ_L―θ_Sよりもやや大きな値をとる
にすぎない。また角類の場合、本来は弧は存在し
ないのだから、すべての交角θ_１〜θ_oは角判定
θ_Lよりも大きい値になるばずであるが、その時
は検出角数＝検出線数であるから角数比が１とな
り、交角偏差の判断に来る前にすでに角類と分類
されており、この判断部に到達したということ
は、検出角数＜検出線数すなわちθ_L≧θ＞θ_Sを
満足する交角θが少なくとも１ケは存在するとい
うことである。それゆえ交角偏差＝θ_nax―θ_nio
は、小さくともθ_nax―θ_Lである。であるから、
交角偏差の閾値Δθとして、 θ_nax―θ_L＞Δθ≫θ_L―θ_S …… を満足する値を選択すれば、円類と角類との選択
分類をすることができる。

具体例をあげると、角類が正三角形〜正六角形
までしかない場合、交角の最小値は正六角形の場
合の60゜であり、θ_L＝30゜，θ_S＝15゜とした場
合、Δθが満たすべき条件は式より30゜＞Δθ
≫15゜であるから、25゜程度に設定すればよい。

なお実験によれば、各パラメータの設定値を所
定の間隔ｄ＝８、所定の閾値Δｌ＝２、直線化判
定角θ_S＝15゜、角判定角θ_L＝30゜として線分・
角の抽出を行ない、角類識別閾値k₁＝0.85、円類
識別閾値k₀＝1.15、交角偏差の閾値Δθ＝30゜に
て40種の図形のパターンの円／角分類を行なつた
ところ、分類正答率は100％であつた。ここで40
種の図形パターンの内訳は、正三角形、正方形、
長方形、菱形（内角は60゜と120゜）、正六角形、
円、長円、楕円の８種につき、寸法を５段階に可
変したものである。

こうして得られた線分情報、角情報および円
類／角類情報とから、容易に図形の形状を識別分
類することができる。

第７図は、角類の形状判定のフローチヤートで
あり、説明の便宜上、角類の図形種類が正三角
形、正方形、長方形、菱形（内角は60゜と120
゜）、正五角形、正六角形に限定されている場合
の例を説明する。検出角数が３，５および６の場
合は、該当する図形種類が各々１種類しかないか
ら、検出角数＝３のときは正三角形、検出角数＝
５のときは正五角形、検出角数＝６のときは正六
角形と判断して差し支えない。

検出角数が４の場合は、該当する図形が正方
形、長方形および菱形の３種類であるから、その
識別分類のためまず４個の検出角度K₁〜K₄が
各々ほぼ直角であるか否かを調べ、ほぼ直角であ
る場合は正方形か長方形であり、そうでないとき
菱形である。なお、ほぼ直角であるか否かの判断
は、例えば80゜＜K₁〜K₄＜100゜であるか否かに
て行なえばよい。

４個の検出角度K₁〜K₄が各々ほぼ直角であ場
合は、抽出線分の長さと長い順にl₁，l₂，l₃，l₄と
し、（l₃＋l₄）／（l₁＋l₂）が辺長比閾値Ｈよりも大
きいときは正方形であると判断し、辺長比閾値Ｈ
以下のときは長方形であると判断する。辺長比閾
値Ｈは、識別したい長方形の辺長比に対応して、
それよりやや大きめの値に設定すればよい。

第８図は、円類の形状判定のフローチヤートで
あり、説明の便宜上、円類の図形種類が円、楕
円、長円に限定されている場合の例を説明する。
円および楕円は、抽出線分がすべて円弧部である
から、抽出線分の長さは短かく、かつかなり均等
であるはずである。それに対して、長は直線部分
を２本有するから、抽出線分の長さは２本だけが
長く、他は短かくかつかなり均等であるはずであ
る。よつて抽出線分の長さを長い順にl₁，l₂，
l₃，l₄とし、（l₁＋l₂）／（l₃＋l₄）が辺長比閾値Ｚよ
りも大きいときは長円であると判断し、辺長比閾
値Ｚ以下のときは円か楕円である。辺長比閾値Ｚ
は、識別したい長円の直線部分長の最小値を前述
した所定の間隔ｄにて除した値近傍に設定すると
よい。

円と楕円との識別分類は、図形パターンのＸ
軸、Ｙ軸への射影をとると、円の場合は理論的に
は、Ｘ_V＝Ｘ_H，Ｙ_V＝Ｙ_Hとなるはずであるから、
XHI＝Ｘ_V／Ｘ_H＝１，YHI＝Ｙ_V／Ｙ_H＝１となる
はずである。そこで、多少の誤差に対する余裕を
みてXHI≒１かつYHI≒１である場合を円と判断
し、それ以外の場合を楕円と判断する。

なお、円と楕円との識別分類に交角偏差、すな
わち抽出した交角θ_１〜θ_oの最大値から最小値
を引いた値を利用することもできる。何故なら、
円の場合は曲率半径が円周の１周にわたつて常に
一定であるから、交角θ_１〜θ_oはすべてほとん
ど均等であり交角偏差がかなり０に近づくのに対
し、楕円の場合は曲率半径が一定でないから、交
角偏差がある程度以上の値を示す性質を利用する
ことができるからである。

かくして、正三角形、正方形、長方形、菱形、
正五角形、正六角形、円、楕円、長円を確実に識
別分類することができる。

以上説明したように、第１の実施例では、図形
の輪郭線を直線近似しつつ追跡し、隣接する二直
線の交角から図形の角や円弧を検出し、図形形状
を識別分類する方法において、抽出線分情報と抽
出角情報とから図形を円類と角類とにまず分類す
る円／角分類部を備えているため、例えば円類図
形の曲率半径が小さくて、円弧相互のなす交角を
図形の角と誤半定してしまつた場合でも図形の分
類識別結果には誤りを生じないという利点があ
る。

また、円／角分類部を備えていない場合には、
円弧相互のなす交角を図形の角と誤判定しないた
めには角判定角θ_Lを大きくせざるを得ず、の結
果逆に本物の角を検出もれしてしまう可能性を生
ずるなど、θ_Lの設定値に余裕が少ない場合があ
る。ところが円／角分類部を備えることにより、
角判定角θ_Lは図形の角をもれなく検出すること
を第１義に考えて設定すればよいため、θ_Lの設
定値の余裕が前者の場合よりも大きくなるという
利点もある。

第１の実施例では、形状判定部において、抽出
線分の勾配を利用しない方法について説明した
が、各線分の始点座標、終点座標がわかつている
のであるから、各線分の勾配情報も得られている
わけであり、勾配情報をも利用することによつ
て、線分相互の平行関係なども検出容易であり、
より正確な識別分類が可能となる。また、識別対
象図形種類を増加することも可能である。

また第１の実施例では、図形の形状を識別分類
する方法のみについて説明したが、抽出線分の勾
配などを併用することにより、図形の傾斜角度を
も判定することが可能であることは言うまでもな
い。

また第１の実施例では、図形の形状を識別分類
する方法のみについて説明したが、抽出線分の長
さ情報や角検出点の座標情報などから、図形寸法
を求めることが可能であることも言うまでもな
い。

本発明は、基本的な図形形状を正確に識別分類
することができるのであるから、フローチヤート
の認識・入力機器に利用することができるのは勿
論のこと、部品等の物体識別分類にも利用するこ
とができる。また、印影の認識・照合における外
枠の識別分類にも利用することができる。

【図面の簡単な説明】

第１図は本発明第１の実施例のブロツク図、第
２図ＡおよびＢは輪郭線の一例、第３図は本発明
実施例の線分・角抽出部のフロー、第４図Ａ，Ｂ
およびＣは線分・角抽出方法の説明図、第５図Ａ
およびＢは本発明実施例の線分・角抽出結果の一
例、第６図は本発明実施例の円／角分類部のフロ
ー、第７図は本発明実施例の角類図形の形状判定
部のフロー、第８図は本発明実施例の円類図形の
形状判定部のフローである。１…読取部、２…輪郭追跡部、３…線分・角抽
出部、４…円／角分類部、５…形状判定部、θ_S
…直線化判定角、θ_L…角判定角、S₁〜Ｓ_o…抽出
線分、θ_１〜θ_o…交角、K₁〜Ｋ_n…抽出角、k₀
…円類識別閾値、k₁…角類識別閾値、Δθ…交角
偏差の閾値、Ｈ…辺長比閾値。

Claims

【特許請求の範囲】１用紙の上にえがかれた図形を構成する線分を
光学的に読取り該線分を構成する各点の座標に対
応する電気信号を提供する読取部と、読取部にて読み取つた図形パターンの輪郭点を
追跡する輪郭追跡部と、二輪郭点相互を接続した
暫定線分と、該二輪郭点にはさまれた輪郭点との
距離が常に所定閾値以下であり、かつ該条件に適
合する限りは該二輪郭点間の間隔を初期設定値に
保つべく分割するような、連続する暫定線分群に
て輪郭線を順次直線近似する手段と、前記暫定線分の相隣る二直線相互のなす交角
と、大・小２種の閾値との大小関係により、交角
が小なる閾値以下の場合は該二直線を一本の直線
に統合し、交角が小なる閾値より大きい場合に
は、該二直線を一本化せずに抽出線分として登録
し、なおかつ交角が大なる閾値より大きい場合に
は、該交角と検出角として登録するという操作を
繰り返して線分情報と角情報とを抽出する手段と
で構成される線分・角抽出部と、抽出された線分情報と角情報とから図形を識別分
類する形状判定部とを備え、検出した角の数を抽出した線分の数で除した値
と、２つの閾値との大小関係および抽出した交角
の最大値から最小値をひいた値と閾値との大小関
係とにより図形パターンを円類と角類とに分類す
る円／角分類部を備えたことを特徴とする図形形
状の識別分類装置。