JPS6255192B2 - - Google Patents

Description

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

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

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

本発明は、上述した図形形状の識別分類を極め
て簡単な処理で実施できる装置を提供することを
目的とし、図形の輪郭線を直接近似しつつ追跡
し、隣接する二直線の交角から図形の角を検出す
る際の各種パラメータ値が常に最適な組み合わせ
に設定されるようにして認識精度を向上したこと
を特徴とするものであり、以下詳細に説明する。
第１図は本発明の第１の実施例のブロツク図であ
り、読取部１により読み取つた図形パターンの外
形である輪郭点を輪郭追跡部２にて追跡する。そ
の後、線分・角抽出部３により線分情報および、
角情報を抽出する。こうして得られた各種情報に
もとづいて、形状判定部４において読取図形の識
別分類を行なう。

なお輪郭点追跡部２は４連結―境界線追跡アル
ゴリズム〔電子通信学会論文誌56―Ｄ巻11号667
〜668頁（1973年11月）〕等公知の技術を用いて差
し支えなく、４連結―境界線追跡アルゴリズムに
て得られた輪郭線の一例を第２図に示した。第２
図Ａは長円の輪郭線例であり、第２図Ｂは菱形の
輪郭点線例である。

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

また交角θ_１が直線化判定角θ_Sよりも大きい
場合には、更に交角θ_１が角判定角θ_Lよりも大
きいか否かを調べ、大きい場合には検出角数に１
を加える。

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

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

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

ということになる。

上記操作を輪郭線に沿つて、輪郭線の１周分を
なぞり終るまで順次繰り返す。理解が容易なるよ
う、第４図の具体例を用いて説明を補うことにす
る。図中の黒点は輪郭点であり、破線は輪郭線の
一部分である。所定の間隔ｄ＝８、所定の閾値Δ
_l＝２の場合を仮定して説明を進める。まずP₁を
始点、P₉を終点とする線分を暫定線分Ｌとする
と、中間の輪郭点P₂〜P₈とＬとの距離D₂〜D₈は
すべてΔ_l以内であるから、Ｌを抽出線分S₁とす
る。

次にP₉を始点、P₁₇を終点とする線分₉・₁₇を
暫定線分Ｌとして、中間の輪郭点との距離を調べ
るとD₁₄＞Δ_lとなるから、暫定線分Ｌを線分₉・
P₁₄に変更し、抽出線分Ｓは線分₉・₁₄となる
〔第４図Ａ〕。そこでS₁とＳとの交角θ_１を調べる
と、直線化判定角θ_Sよりも小さいから、ＳをS₁
と一本化して、抽出線分S₁を線分₁・₁₄に変更
する。次いで線分₁₄・₂₂を暫定線分Ｌとして、
中間の輪郭点との距離を調べると、すべてΔ_l以
内であるからＬを抽出線分Ｓとする。そこでS₁と
Ｓとの交角θ_１を調べると、直線化判定角θ_Sよ
りも大きいからＳを抽出線分S₂として登録する。
すなわち抽出線分S₂＝線分₁₄・₂₂である。

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

次に線分₂₂・₃₀を暫定線分Ｌとして、中間の
輪郭点との距離を調べると、すべてΔ_l以内であ
るからＬを抽出線分Ｓとする。そこで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₁として登録しなおすことが必要であ
る。こうして、線分情報と角情報との抽出が完了
する。第２図に示した輪郭線例の線分・角抽出結
果の例を第５図に示す。なお各パラメータの設定
値を所定の間隔ｄ＝８、所定の閾値Δ_l＝２、直
線化判定角θ_S＝15゜、角判定角θ_L＝30゜とした
場合の抽出結果である。こうして得られた線分情
報および角情報とから図形の形状を識別分類する
ことができる。

第６図は形状判定のフローチヤートであり、説
明の便宜上認識対象図形種類が正三角形、正方
形、長方形、菱形、正五角形、正六角形、円およ
び長円に限定されている場合の例を説明する。

検出角数が３，５および６の場合は、該当する
図形種類が各々１種類しかないから、検出角数＝
３のときは正三角形、検出角数＝５のときは正五
角形、検出角数＝６のときは正六角形と判断して
差し支えない。

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

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

検出角数が２以下あるいは７以上の場合は、角
類（正三角形、正方形、長方形、菱形、正五角形
および正六角形）に該当する図形がないから円か
長円のいずれかである。ところで円は抽出線分が
すべて円弧部であるから、抽出線分の長さは短か
くかつかなり均等であるはずであり、長円は直線
部分を２本有するから、抽出線分の長さは２本だ
けが長く、他は短かくかつかなり均等であるはず
である。よつて抽出線分の長さを長い順にl₁，
l₂，l₃，l₄とし、（l₁＋l₂）／（l₃＋l₄）が辺長比閾値
Ｚよりも大きいときは長円であると判断し、辺長
比閾値Ｚ以下の時は円であると判断すればよいわ
けである。なお辺長比閾値Ｚは、識別したい長円
の直線部分長の最小値を、前述した所定の間隔ｄ
にて除した値近傍に設定するとよい。

こうして、正三角形、正方形、長方形、菱形、
正五角形、正六角形、円および長円を認識分類す
ることができる。

上述の判定論理で図形形状を確実に認識分類す
るためには、円や長円などの円類からは角が検出
されないことが望ましく、万一検出されても検出
角数は２以下である必要がある。ところが、線
分・角抽出部の各パラメータｄ，Δ_l，θ_Sおよび
θ_Lの設定値如何によつては、円類においても角
が検出されてしまうことがある。このことは線
分・角抽出結果の例第５図Ａからも明らかであ
る。

勿論、角判定角θ_Lを大きく設定しておけば、
円類から角を検出しないようにすることはできる
が、θ_Lを無制限に大きく設定することはできな
い。というのは、正六角形や菱形においては交角
θがかなり小さくなるため、θ_Lを大きくする
と、交角の小さい角を弧と誤判断してしまう恐れ
があるからである。

そこで各パラメータ設定値の最適化をはかる必
要がある。まず直線化判定角θ_Sの設定である
が、「２本の抽出線分の交角が何度以下だつたら
１本の直線とみなしたいか」という所望値に設定
すればよいわけであるが、所定の間隔ｄおよび所
定の閾値Δ_lとの関係よりある程度の目安が得ら
れる。すなわち、１メツシユ分のずれは読取部の
誤差などにより生ずるから、１メツシユ分ずれた
点があつても直線とみなしたいという前提条件に
おいて、Δ_l＞１に設定してあり、２本の抽出線
分とも中間輪郭点からの距離がΔ_l以下であつた
場合の交角θは、第７図Ａの如き関係になるか
ら、θをｄの関数として表わすと、 θ＝180゜−cos^-1−ｄ（ｄ−２）／（ｄ−１）^２＋１
…(1) なる式が得られ、(1)式をグラフに表わすと、第８
図Ａの曲線が得られる。それゆえ、θ_Sの設定値
は、第８図Ａから読み取つた値よりも少し大きめ
に設定すればよいことになる。

次いで角判定角θ_Lの設定であるが、「２本の抽
出線分の交角が何度以上だつたら角とみなしたい
か」により設定すればよいわけであり、設定値の
目安は次のようになる。

認識対象角類図形の最小交角θ_nioよりもθ_Lは
小さくなければならないから、正ｎ角形までを認
識したい場合は、 θ_L＜θ_nio＝180゜−内角 ＝180゜−180゜×（ｎ−２）／２ ＝360゜／ｎ となる。よつて正六角形までを認識したい場合
は、θ_L＜60゜となる。

次にθ_Lの下限値につき検討する。第７図Ｂに
図示した如く、半径ｒ〔mm〕の円の円周をｄで分
割して直線近似した時、すべての中間輪郭点から
対応する抽出線分までの距離がΔ_l以下であれ
ば、直線近似円の交角数Ｎは、 Ｎ＝２πｒ／（ｄ／α） である。ただしαはメツシユの分解能であり、以
下の計算はα＝８メツシユ／mmの場合につき行な
う。

よつて交角数 Ｎ＝２πｒ／（ｄ／８） よつて交角 θ＝360゜＝Ｎ ＝45°×ｄ／２πｒ よつて直線近似円の検出角数を０としたいなら、
θ_L＞45゜×ｄ／２πｒとすることが望まれる。
よつて 360゜／ｎ＞θ_L＞45゜×ｄ／２πｒ …(2) が得られる。

これらの関係を第８図Ｂ１，Ｂ２，Ｂ３に示
す。

なお以上の計算式は、計算式の導出を容易にす
べく、仮定を設けて導いたものであり、やや厳密
性を欠く部分もあるが実験によりかなり実情と符
合することが確かめられたのみならず、定量的な
数値にはやや誤差の入りこむ余地はあるが定性的
には正しいものである。

こうして得られた第８図を参照するに、θ_Sは
曲線Ａよりもやや上の値に設定すればよく、θ_L
の設定可能範囲は60゜（正六角形までを認識した
い場合はθ_L＜60°であるから）以下かつ直線Ｂ
以上である。であるから、ｒが小さいほどθ_Lの
設定可能範囲は狭くなり、ｒが大きいほどθ_Lの
設定可能範囲は広がつて予裕度が大きくなるか
ら、認識対象図形の最小なものにつき認識可能で
あるならば、もつと大きい図形は当然もつと認識
しやすいということになる。そこでｒ＝２mmの場
合を考えれば、まず通常の入力図形としては十分
すぎると考えられるので、以下の議論は直線Ｂと
してＢ１を用いて進めることとする。

例として、ｄ＝８の場合におけるθ_Lとθ_Sの設
定可能範囲をそれぞれ破線と白抜き矢印とで第８
図に記入する。

曲線Ａと直線Ｂ１との交点ｑのｄの値をdq
（≒６）とすると、 ｄ＜dqのとき、θ_Sの設定可能値が大きくなる
ばかりではなく、Ａの方がＢ１より上方にきてし
まうため「２直線の１本化」と「弧の抽出」との
切り分けが難かしくなるため、ｄ＜dqであるこ
とは望ましくない。

ｄ≧dqのとき、ｄを大きくすればするほどθ_S
の設定可能値を小さくすることができ「２直線の
１本化」と「弧の抽出」との切り分けが容易にな
る反面θ_Lの下限値が大きくなつてしまうためθ_L
の設定可能範囲が狭くなつてしまい「弧の抽出」
と「角の抽出」との切り分けが難かしくなつてし
まう。

よつて所定の間隔ｄはdqよりもやや大きい値
に設定することが望ましい。またその時のθ_Lは
(2)式から得られた範囲の中央値近傍に設定し、θ
_Sは(1)式から得られた値よりもやや大きい値に設
定すればよい。

数値例をあげるなら、dq≒６であるからｄ＝
８と設定するならば(2)式より60゜＞θ_L＞29゜で
あるからθ_Lは45゜近傍に(1)式よりθ≒16゜であ
るからθ_Lは18゜近傍に設定すればよい。

実験によれば、各パラメータの設定値を所定の
間隔ｄ＝８、所定の閾値Δ_l＝＝２、直線化判定
角θ_S＝18゜、角判定角θ_L＝40゜として、曲率半
径２mm以上の図形パターン40種に関し認識分類を
行なつた結果良好な分類正答率が得られた。

以上説明したように、第１の実施例では、図形
の輪郭線を直線近似しつつ分割し、隣接する２直
線の交角から図形の角や円弧を検出し、その抽出
線分情報や抽出角情報とから図形形状を認識分類
する方法において、線分・角抽出部において使用
する各種パラメータ値を認識対象図形に応じた最
適な組み合わせに設定するものであるから、認識
分類の精度が高いという利点がある。

第１の実施例では、各種パラメータの最適設定
値選定の際、認識対象図形の最小なものにつき認
識可能であるならば、もつと大きい図形は当然も
つと認識しやすいはずだからということで、認識
対象図形の最小曲率半径を基準において設定値を
算出する場合を説明したが、例えば図形パターン
のＸ，Ｙ両軸への射影をとり図形パターンの幅や
高さを求め、その幅や高さと図形パターンの輪郭
点数との関係から図形パターンの概略寸法を求
め、図形パターンの曲率半径を推定してから各種
パラメータの最適組み合わせを設定することによ
り、今認識しようとしている対象図形によりふさ
わしいパラメータ値を対象図形毎に設定し直す方
法も可能であり、この方法は、認識対象図形の寸
法可変範囲が大きい場合には特に有効である。

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

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

【図面の簡単な説明】

第１図は本発明の第１の実施例のブロツク図、
第２図ＡおよびＢは輪郭線の一例を示す図、第３
図は本発明の実施例の線分・角抽出部を示すフロ
ー、第４図Ａ〜Ｃは線分・角抽出方法の説明図、
第５図Ａ及びＢは本発明の実施例の線分・角抽出
結果の一例、第６図は本発明の実施例の形状判定
部のフロー、第７図Ａ及びＢはパラメータ値設定
の原理説明図、第８図はパラメータ相互の関係グ
ラフである。 １…読取部、２…輪郭追跡部、３…線分・角抽
出部、４…形状判定部、θ_S…直線化判定角、θ_L
…角判定角、S₁〜Ｓ_o…抽出線分、θ_１〜θ_o…交
角、K₁〜Ｋ_n…抽出角、α…メツシユの分解能、
ｑ…交点。

Claims (1)

1. 【特許請求の範囲】 １ 平面図形を光学的に読取り図形を構成する各
   点の座標の電気信号を出力する読取部と、読取部
   にて読み取つた図形パターンの輪郭点を追跡する
   輪郭追跡部と、二輪郭点相互を接続した暫定線分
   と、該二輪郭点にはさまれた輪郭点との距離が常
   に所定値以下であり、かつ該条件に適合する限り
   は該二輪郭点間の間隔を初期設定間隔ｄに保つべ
   く分割するような、連続する暫定線分群にて輪郭
   線を順次直線近似する手段と、前記暫定線分の相
   隣る二直線相互のなす交角と、大・小２種の閾値
   との大小関係により、交角が小なる閾値θ_S以下
   の場合は該二直線を一本の直線に結合し、交角が
   小なる閾値θ_Sより大きい場合には、該二直線を
   一本化せずに抽出線分として登録し、なおかつ交
   角が大なる閾値θ_Lより大きい場合には該交角を
   検出角として登録するという操作を繰り返して線
   分情報と各情報とを抽出する手段とで構成される
   線分・角抽出部と、抽出された線分情報と角情報
   とから図形を識別分類する形状判定部とを備え、
   前記、初期設定間隔ｄ、小なる閾値θ_Sおよび大
   なる閾値θ_Lの設定値をｄは、 θ＝180゜−cos^-1−ｄ（ｄ−２）／（ｄ−１）^２＋１
   …(1) θ＝360゜×ｄ／（α×２πｒ） …(2) （ここでαはメツシユの分解能） の両式を連立させて解いた値dqの値よりもやや
   大きい値に設定し、θ_Sは、(1)式にｄの設定値を
   代入して得たθの値よりもやや大きい値に設定
   し、θ_Lは、認識対象図形の最小交角と、(2)式に
   ｄの設定値を代入して得たθの値との中間値近傍
   に設定することを特徴とする図形認識装置。