JPH0420503B2

JPH0420503B2 -

Info

Publication number: JPH0420503B2
Application number: JP16766485A
Authority: JP
Inventors: Hirohisa Takusagawa
Original assignee: Fuji Electric Co Ltd
Current assignee: Fuji Electric Co Ltd
Priority date: 1985-07-31
Filing date: 1985-07-31
Publication date: 1992-04-03
Also published as: JPS6228887A

Description

【発明の詳細な説明】〔産業上の利用分野〕この発明は、画像処理装置により対象物を線図
形化して識別（検査）する識別方法に関する。

〔従来の技術〕

最近は、各種の産業分野において、対象物識別
のためのニーズが増えている。例えば、製品の自
動組立を行なうべく、その構成部品を識別してハ
ンドリングを行なう場合等がそれである。従来、
かゝる対象物識別方法としては、いわゆるSRI
（Stanford Research Institute）等やマツチング
法等が知られている。

マツチング法は、識別対象物パターンの全体ま
たは一部に関するデータを全て取り出し、これを
標準のものと照合して識別する方法である。

しかしながら、この方法には、イ対象物の姿勢が良くないと適用が難しい。

ロ各識別対象物が互いに分離した状態でないと
識別不可能である。

という問題または制約があるばかりでなく、対象
物パターンそのものを取り扱うためデータ量が膨
大となり、対象物の姿勢変動が大きくなればなる
程、位置の正規化や照合処理が複雑かつ困難にな
る。

一方、前記SRI法は以下の如く手法である。第
７図はかかるSRI法を説明するための参照図であ
る。

これは、まず対象物の２値化画像からランレン
グス（セグメント）によるコード化を行ない、次
いでランレングス化されたデータについて連結性
解析を行なうことにより、種々の特徴量を抽出す
る。そして、その基本特徴量とその組み合わせと
によつて多くの有用なパラメータを算出する。こ
の基本特徴量としては多くのものがあるが、例え
ば第７図の如き対象物１０の全面積Ｓおよび周囲
長Ｌ、対象物１０の中の穴Ｈの数、各穴Ｈの面積
和、対象物１０の重心Pc，x_c，y_c、重心から輪郭
までの半径の最大値R_nax，同じくその最小値
R_nio、Ｘ軸への投影最大値X_naxおよび最小値
X_nio、Ｙ軸への投影最大値Y_naxおよび最小値Y_nio
等がある。また、基本的特徴量の組合せパラメー
タとしては、例えばP_e（≡4πS／L²），R_r（≡R_nax
−R_nio），X_d（≡X_nax−X_nio），Y_d（≡Y_nax−Y_nio）
等がある。なお、識別処理は予め各対象物のシヨ
ーイング（Showing；画像処理装置に見せるこ
と）によりその登録をした後、識別すべき対象物
との間でそのパラメータを互いに比較、照合する
ことにより行なわれる。

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

以上のように、SRI法は対象物の幾何学的特徴
量に着目する方法であるが、以下の如き問題点を
有している。

ａ各識別対象パターンの形状差が大きくないと
識別ができない。

ｂ各識別対象物は互いに完全に分離した状態で
なければ識別不能である。

すなわちａ）は識別可能対象物の種類や図形の
複雑さに対する制約となり、ｂ）は各対象物の配
列や背景に対する制約であり、対象物が互いに重
なり合つたり組み合わさつた状態にないこと、ま
た背景部に他のパターンが存在しないこと等が条
件となる。

したがつて、この発明は、１識別対象パターン間の形状差が余り大きくな
くても対処できるようにする。

２各識別対象物が互いに完全に分離している場
合は勿論、或る一つの識別対象物の一部に他の
識別対象物の一部が重なつている場合でも類推
でできるようにする。

３識別精度の向上と識別時間の短縮（形状特徴
の保存とデータ圧縮）とを両立させる。

ことを目的とする。

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

対象物を画像として捉え、その画像情報から対
象物の各種特徴量を抽出し、これにもとづいて所
定の処理を行なう画像処理装置を設ける。

〔作用〕

上記画像処理装置によつて、以下の如き処理を
行なう。

１対象物の輪郭線追跡を行ない、これを線図形
化する。

２線図形からその特徴となる点（特徴点）と、
直線を含む標準線要素とを抽出するとともに、
そのいずれとしても抽出されない残りの部分を
複数に分割して部分線分を抽出し、これら各構
成要素について要素固有のデータと要素間接
続・配列データとを含む構成要素記述データを
抽出する。

３辞書登録モードでは、各標準対象物について
以上の如き処理を行ない、その結果抽出される
構成要素記述情報を所定のメモリに格納する。

４検査モードでは、未知対象物について同様の
処理を行ない、その結果抽出される構成要素記
述情報を所定のメモリに格納する。

５メモリに記憶された標準対象物と未知対象物
の各構成要素記述情報を、上記特徴点および標
準線分情報を優先し、かつ輪郭線に沿う形で順
次照合し、最も大きな類似度が得られる標準対
象物を未知対象物の該当物と判定する。

〔実施例〕

第１図はこの発明の実施例を説明するための参
照図、第１Ａ図は特徴点の抽出方法を説明するた
めの参照図、第１Ｂ図は直線の抽出方法を説明す
るための参照図、第１Ｃ図は円の抽出方法を説明
するための参照図、第１Ｄ図は部分線分の抽出方
法を説明するための参照図、第２図はこの発明が
実施される画像処理装置を示すブロツク図、第３
図はこの発明により得られる構成要素記述情報の
メモリへの記憶例を示す参照図、第４図は画素の
連なりからなる輪郭線の一例を示す参照図、第５
図は方向コードを説明するための参照図、第６図
は輪郭情報のメモリへの記憶例を示す参照図であ
る。

まず、第２図から説明する。同図において、１
０は識別対象物、１１は照明器、１２はテレビカ
メラ等の撮像装置、１３はアナログ／デイジタル
（Ａ／Ｄ）変換器、１４は前処理回路、１５はセ
グメント抽出回路、１６はデータメモリ１７はマ
イクロプロセツサ等の処理装置である。

照明器１１によつて照明される識別対象物１０
の光学像は、テレビカメラ１２によつて映像（ビ
デオ）信号に変換される。この映像信号はＡ／Ｄ
変換器１３によつて画素毎にデイジタル量に変換
され、さらに前処理回路１４にて雑音除去、平滑
化等が行なわれ、デイジタル画素として取り出さ
れる。セグメント抽出回路１５は、このデイジタ
ル画像から各セグメント毎の始点座標とセグメン
ト長を抽出し、データメモリ１６に格納する。処
理装置１７は、このセグメント情報を用いてセグ
メント毎に４連結または８連結による連結性解析
等を行い、１つの独立したパターンを抽出する。
次いで、この独立パターンの輪郭線を抽出し、輪
郭線追跡を行う。この輪郭線に関する情報は、上
記のデータメモリ１６内に格納される。

いま、輪郭線の一部が画素の連なりとして第４
図の如く表わされるものとすると、この輪郭線１
は各画素の座標位置P₁，P₂……P₉と各座標点に
おける方向コードD₀〜D₇とによつて表現するこ
とができる。こゝで、方向コードとは輪郭線を画
素単位で追跡する場合の方法（ベクトル）を表わ
すものであり、第５図にD₀〜D₇で示す如く８つ
の方向がある。なお、各方向ベクトル間の角度は
45°である。また、これらの輪郭データは、前述
のデータメモリ１６へ第６図の如く格納される。

この方向コードの利用の仕方としては種々考え
られるが、例えば輪郭線に沿う周囲長の演算に用
いることができる。すなわち、第４図のP₁点か
らP₉点までの周囲長は、方向コードD₀を0°として
0°，90°，180°，270°の場合はそれぞれ１画素分の
長さとし、方向コードが45°，135°，225°，315°
の場合は１画素分の長さを√２倍としたものと
考え、部分毎の和として求めることができる。し
たがつて、第４図のP₁点からP₉点迄の周囲長は、
（３×１＋５×√２）×である。

こうして、対象物の画像パターンは輪郭線によ
る線図形に変換される。この輪郭線による対象物
の記述（表現）は、対象物の形状情報、特徴情報
を充分に含んでいながら大幅なデータ圧縮を可能
にしている。なお、輪郭線の追跡に当たつては上
記の如きテレビカメラを用いる方法だけでなく、
フライングスポツトスキヤナやレーザ光を利用す
る方法も考えられる。

こうして取り出される対象物の輪郭線（線図
形）が例えば第１図の如く表わされるものとする
と、この発明では適宜な処理を施すことにより、
線図形１を以下の如き構成要素に分割する。

すなわち、線図形１の特徴となる点（特徴点ま
たは特徴的小区間）と、直線や円（円弧を含む）
の如き標準線要素とみなせる部分と、それ以外の
部分との３種類である。第１図では部分Ａが特徴
的小区間（凸部）として、部分B₁〜B₃が標準線
分（B₁，B₂；直線、B₃……円弧）として、また
部分Ｃが上記以外の部分としてそれぞれ抽出され
る。なお、残りの部分Ｃは、さらに同図の如く部
分線分L₆，L₇……L₁₁等に分割される。したがつ
て、以上の如き構成要素の種別毎にその端点座標
または長さ（周囲長）等の構成要素に固有のデー
タと、構成要素間のなす角度または代表点（端
点、中心点）間の距離等で表現される構成要素間
接続・配列データとを取り出せば、１つの線図形
をこれらのデータによつて表現することができ
る。そこで、この構成要素に固有のデータと要素
間接続・配列データとを合わせて構成要素記述情
報と呼ぶことにすると、この発明はかかる構成要
素記述情報にもとづいて対象物の識別を行なうも
のと云うことができる。つまり、標準となる各対
象物について、上記の如き処理をして構成要素記
述情報を予め求めておけば、これと未知対象物を
処理して得られる構成要素記述情報とを照合する
ことにより、対象物を識別することができる。

上記の如き３種類の構成要素の抽出の仕方につ
いて、以下に具体的に説明する。

まず、第１Ａ図を参照して特徴点について説明
する。

いま、対象物の輪郭線が同図イの如く表わされ
るものとすると、この輪郭線１に沿つてその曲率
（半径の逆数）の変化を調べると、この場合は例
えば同図ロの如くなる。こゝで、P₁点はその曲
率が０から∞へと不連続的に変化することから、
これを折点とし、P₂〜P₄点では曲率が急激に変
化していることから、これを凸点として抽出す
る。なお、凹点についても同様である。

次いで、曲率が連続的になだらかに変化する部
分について、標準線要素が抽出できるか否かを調
べる。こゝで、標準線要素とは直線、円または楕
円（楕円弧を含む）の如く頻度が高く、演算の容
易な全ての曲線を含むことができる。つまり、人
工図形では直線と円が最も多いが、対象図形によ
つて予め予測ができる場合は、それと対応する曲
線を標準線要素とすることができる。

直線か否かの判別は、例えば第１Ｂ図の如く行
なう。

すなわち、輪郭線１上に連続するサンプリング
点P_i，P_i+1……P_j-1，P_jを考え、その各隣接点間
の凹凸値αの絶対値が許容値（零に近い値）より
も小さく、かつ、その線分の両端点を含むサンプ
リング点の組み合わせ（P_i，P_k，P_j）でαの絶対
値の許容値（零に近い値）よりも小さいとき、直
線と判定する。なお、上記P_k点は線分の中央部
に設定する。また、凹凸値αは曲がりの程度を表
わすものであり、着目点P_iと両隣接点P_i-1，P_i+1
を通る円の半径を考え、その逆数をもつて定義す
るものとする。

一方、円であるか否かの判定は、例えば第１Ｃ
図の如く行なわれる。

第１Ｂ図と同様に輪郭線１上にサンプリング点
P_o-1，P_o，P_o+1，_o+2……を考え、連続するサンプ
リング点で上記のα値が所定の範囲内にあつてそ
の符号が一方向であること、かつサンプリングさ
れた３点（P_o-1，P_o，P_o+1と、P_o，P_o+1，_o+2等）
を通る円を考えてその円の中心（O_o，O_o+1等）
と半径（R_o，R_o+1等）を演算したとき、これら
が許容範囲内にあることをもつて各部分は同一円
であると判定する。なお、演算精度を向上させる
には、サンプリング点を増加させたり、サンプリ
ング間隔を変えて演算し、それぞれにおいて上述
の如き条件が満足されたとき、同一円と判定する
ようにする。このようにして、第１図の対象図形
１０では、部分Ａは特徴的小区間、部分B₁，B₂
は直線、B₃は円弧と判定される。標準線要素
（直線または円等）として抽出されると、その図
形として記述は、例えば標準線要素の種類（直線
か円か等）、標準線要素のパラメータ（直線部の
長さ、円の半径、円弧部の角度）等によつて表現
される。

特徴点（特徴的小区間）または標準線要素のい
ずれとしても抽出されない残りの部分について
は、例えば第１Ｄ図の如き線分化処理が行なわれ
る。

まず、輪郭線１上にスタート点P₁（x₁，y₁）を
設定する。このスタート点としては、上記の如き
特徴点を用いることができる。次いで、輪郭線１
のP₁点における接線２を次式の如く求める。

ｙ−y₁＝ａ（ｘ−x₁）こゝに、ａは接線２の傾き（勾配）を表わして
おり、適宜な方法によつて求められる。そして、
この接線と輪郭線間の距離ｄ（または角度θ₀）が
所定の許容値に達した輪郭線上の点P₂（x₂，y₂）
を１つの線分の終点とする。このP₂（x₂，y₂）点
は１つの線分L₁の終点であるが、同時に次の線
分L₂のスタート点でもあり、以下同様にして線
分L₂，L₃……を得ることができる。線分化の別
の方法としては、輪郭線と接線間のずれ量ｄ（ま
たはθ₀）とその輪郭線上における周囲長との比に
対して許容値を設定する方法も考えられる。な
お、この場合も所定の許容比に達した輪郭線上の
点をその線分の終点とする。いずれにしても、か
かる線分化により、連続する１つの輪郭線のデー
タ、つまり対象物データを大幅に圧縮することが
できる。

こうして得られる線図形を、線分情報を用いて
記述する。こゝに、線分情報とは、イ線分固有の情報ロ各線分間の接続・配列情報を云うものとする。より具体的には、イ）は線分のラベル、線分の長さ、線分の両端
点座標等であり、ロ）は各線分の接続順序、２つの線分間のなす
角度、各線分間の代表点（端点、中心点など）間
の距離等である。

なお、上記イ），ロ）のデータは全て必要とい
うわけではなく、例えばイ）のラベルやロ）の接
続順序はメモリのアドレスと対応付けることによ
つて省略することができる。また、イ）の両端点
座標は、１組の情報で線分そのものゝ情報（固有
情報）だけでなく、隣り合う線分との接続関係を
表わす情報をも兼ねており、対象図形の位置正規
化を行なう前の原始データ等として有効なもので
ある。ロ）の隣接する線分となす角度θ（第１Ｄ
図参照）を利用すれば、記憶データ量が少なくな
つて処理も容易になるが、これは角度θが対象図
形の姿勢に依存しない正規化されたデータである
ためである。これはイ）の線分の長さ（₁，₂
……）についても同様である。

このようにして、１つの線図形は３種類の構成
要素によつて記述することができる。すなわち、ａ特徴点または特徴的小区間ｂ標準線要素とみなせる部分ｃ部分線分化される部分である。そして、その構成要素記述情報は、１各構成要素に固有の情報；構成要素（標準線
要素）の種類、構成要素の長さ、構成要素の両
端点座標等。

２各構成要素間の接続・配列情報；隣接する構
成要素の両端点を通る直線のなす角度、各構成
要素の代表点（端点、中心点）間の距離等。

があり、これらの情報は例えば第３図の如く所定
のメモリに格納される。

このように線図形を構成要素に分割して処理す
るようにしているので、大幅なデータ圧縮が可能
となつて演算速度も向上するばかりでなく、重畳
した物体の識別も可能となるものである。つま
り、対象物の特徴を充分に抽出しながら大幅なデ
ータ圧縮を実現しているので、逆にこのような構
成要素記述情報によつて原図形の復元が可能であ
る。

さて、識別処理は以下の如く行なわれる。

未知対象物の識別処理（検査モードともいう）
に先立つて、まず全ての標準対象物について学習
し、登録する（辞書登録モードともいう）。この
とき、各標準対象物を分離した状態で撮像し、画
像パターンを上述の如く線図形化し、構成要素に
分解して各構成要素毎の構成要素記述情報を抽出
し、これらを全て所定のメモリに格納する。

検査モードでは未知対象物について上記と同様
の処理を行ない、その構成要素記述情報を抽出し
て所定のメモリに格納する。

照合段階では、特徴点情報や標準線要素情報を
優先し、かつ輪郭線に沿う形で両者の比較、照合
を行ない、最も大きな類似度を与える標準対象物
を該当物と判別する。つまり、特徴点および標準
線分ならびに部分線分の各特徴データについて、
検査対象物と標準対象物の類似度Ｓを演算し、こ
れら類似度の合計（累積和）を演算する。こゝ
で、或る特徴量データについて、標準対象物のそ
れをｆ、検査対象物のそれをf′とすると、その類
似度Ｓは例えば次式の如く表わすことができる。

Ｓ＝〔ｆ−｜ｆ−f′｜〕／ｆしたがつて、両者が一致すれば（ｆ＝f′）、Ｓ
＝１となる。同様に、或る特徴量データについて
の類似度をS_iとし、w_iを重み係数（全体に対する
割合）とすれば、全要素（要素数；Ｎ）の類似度
S_tは、 S_t＝_N 〓ⁱ⁼¹ S_i×w_iN 〓ⁱ⁼¹ 〔f_i−｜f_i−f_i′｜×w_i／f_i の如く一般化することができる。なお、この場合
も、すべての要素についてｆ＝f′が成立すれば全
体の類似度S_tも“１”となり、完全に一致してい
るものと考えることができる。

〔発明の効果〕

この発明によれば、対象物の輪郭情報に着目し
対象物を線図形として扱うことにより、その形状
特徴を充分に抽出しながら大幅なデータ圧縮を行
なうことができるので、メモリ容量の低減化と演
算処理時間の短縮化とを図り得る利点がもたらさ
れる。また、線図形を３種類の構成要素に分解す
るようにしたので、特徴量の抽出が充分に行なわ
れるばかりでなく、特徴点や標準線要素情報を優
先的に照合することにより、照合の効率化（不要
な照合を極力少なくする）を図ることができる。
つまり、この発明によつて得られる抽出特徴量
は、SRI法の如き図形のマクロ的な特徴量でない
ため、形状そのものゝ情報が良好に保存される一
方、マツチング法のような膨大な図形データを必
要としないのが大きな特徴である。なお、対象図
形に応じて最適な標準線要素を選択することによ
り、識別精度の向上と処理時間の短縮を図ること
が可能である。されに、識別すべき対象物の一部
に他の識別対象物が重なつた場合でも、従来技術
で述べたSRI法のように識別のためのパラメータ
の全てに誤差を生じることがないので、例えば、
識別対象物の特徴点と標準線要素として抽出され
る部分以外に他の識別対象物の一部が重なつてい
る場合であれば、識別不能になることなく比較的
精度良く対象物が何かを類推することができる。
以上の説明から明らかのように、この発明によれ
ば、イ識別対象物の形状が単純でなく、その種類が
多い。

ロ識別対象物が分離状態にあるものばかりでな
く、重畳している状態（部分パターンとなる場
合）でも識別したい。

と云うようなニーズに対処することができる。す
なわち、上記イ），ロ）の如きニーズは各種オー
トメーシヨンFA，OA，LAの進展とともに多く
なり、次第に強くなつている中で従来のSRI法や
マツチング法ではこれらに対処できないため、こ
の発明によりこれらのニーズに応えられるように
したものである。

【図面の簡単な説明】

第１図はこの発明の実施例を説明するための参
照図、第１Ａ図は特徴点の抽出方法を説明するた
めの参照図、第１Ｂ図は直線の抽出方法を説明す
るための参照図、第１Ｃ図は円の抽出方法を説明
するための参照図，第１Ｄ図は部分線分の抽出方
法を説明するための参照図、第２図はこの発明が
実施される画像処理装置を示すブロツク図、第３
図はこの発明により得られる構成要素記述情報の
メモリへの記憶例を示す参照図、第４図は画素の
連なりからなる輪郭線の一例を示す参照図、第５
図は方向コードを説明するための参照図、第６図
は輪郭情報のメモリへの記憶例を示す参照図、第
７図はSRI法を説明するための参照図である。符号説明、１……輪郭線、２……接線、１０…
…対象物、１１……照明器、１２……テレビカメ
ラ、１３……Ａ／Ｄ変換器、１４……前処理回
路、１５……セグメント抽出回路、１６……デー
タメモリ、１７……処理装置。

Claims

【特許請求の範囲】１対象物を撮像しその画像処理を行なうことに
よつて対象物を線図形化し該線図形にもとづき所
定の処理をして対象物を識別する方法であつて、前記対象物の輪郭線に沿つてその曲率の変化を
調べ、その曲率が不連続的にあるいは急激に変化
している区間に含まれる輪郭線上の点を特徴点と
して抽出し、次いで、その曲率が連続的になだら
かに変化する区間に含まれる輪郭線上で連続する
複数の点をサンプリング点として、その隣接点間
の凹凸値αの絶対値が所定の許容値よりも小さ
く、かつ、その両端点と中央部の点の組合せで求
めた凹凸値αの絶対値が所定の許容値よりも小さ
いという条件を満たすとき、当該区間に含まれる
輪郭線を標準線要素として抽出するとともに、そ
のいずれとしても抽出されない残りの部分を複数
に分割して、部分線分を抽出し、これら各構成要
素について要素固有のデータと要素間接続・配列
データとを含む構成要素記述情報を抽出する処理
を各標準対象物について行なつた後、未知対象物
についても同様の処理を行ない、その結果得られ
た各標準対象物と未知対象物の各構成要素記述情
報を前記特徴点情報および標準線要素情報を優先
してかつ線図形に沿う形で順次照合し、最も大き
な類似度が得られる所定標準対象物をもつて未知
対象物の該当物とすることを特徴とする対象物識
別方法。２特許請求の範囲第１項に記載の対象物識別方
法において、前記要素固有のデータは構成要素の
種類、長さ、両端点座標を含み、前記要素間接続
配列データは隣接構成要素間の角度、各構成要素
の代表点間距離を含むことを特徴とする対象物識
別方法。