JPH024948B2 - - Google Patents

Description

【発明の詳細な説明】 〔発明の属する技術分野〕 この発明は、TVカメラなどの撮像手段を用
い、重なりなどを含んで乱雑に配置されている食
品容器などの円形物体を分離して、個々の物体の
直径を計測する画像処理装置に関する。

〔従来技術とその問題点〕

TVカメラなどの撮像手段を用いて個々の物体
を撮像し、その撮像信号から物体の大きさ（面
積、直径、外周長）などを求めて物体を識別する
ことが、例えばコンベアにより搬送されてくる物
体の良否を識別して物体の仕分けなどを行なう場
合に用いられている。このような場合に、従来は
個々の物体がそれぞれ分離独立しているものを対
象としていたために、撮像信号から物体の大きさ
を求めることが簡単であつたが、TVカメラによ
る物体の識別が数多くの分野において適用されて
くると、当然のことながら、個々の物体が分離独
立しているのばかりではなく、重なり合つている
ような場合にも適用できることが要求されてく
る。ところが重なり合つている物体をTVカメラ
で撮像した場合には、撮像した画像は１つの物体
として映るため、各物体の正しい大きさを求める
ことができなかつた。

例えば、社員食堂などにおいて自動化を行なう
ために、食器容器の大きさに値段を対応づけてお
き、第１図に示すように盆１におかれた社員が自
由に選択した料理の容器２，３をTVカメラ４に
て撮像し、その撮像信号から容器２，３の大きさ
を求めて値段を算出することが考えられる。この
ような場合、上からみて容器２と３が重なる場合
には、撮像した画像は第２図に示すようになつて
しまい、容器２，３のそれぞれの大きさを求める
ことが困難であつた。このために、第１図に示す
ようにTVカメラ５を盆１の下方に配置し、盆１
の上方に照明８，９を配置して盆１に容器２，３
の糸尻部６，７が明確に写るようにして第３図に
示すような画像を得ることも考えられている。こ
の場合には糸尻部の大きさと値段を対応ずけてお
くことにより値段を求めることができ、また糸尻
部は絶対に重なり合うことがないために画像が第
３図に示すように必らず分離したものになるので
糸尻部の大きさを求めることは簡単である。

ところが、この装置の場合には糸尻部が鮮明に
出る必要があるために、 離れている他の容器の影が重なる場合、 容器同志が乗り合つている場合、 異物により、容器が浮いて糸尻の影が鮮明に
出ない場合、 などの要因で、独立した糸尻を撮像できないとき
は判別が不可能となる。

〔発明の目的〕

本発明は、前記の欠点を除き、食品容器などの
円形物体が重畳している場合でも、容器の個数、
位置、大きさなどを検知し得る画像処理装置に係
るもので、これにより、ランダムに置かれている
円形物体の位置、大きさを正確に知ることがで
き、従来の装置より、広範囲の応用分野に適用で
きる装置を提供することを目的とするものであ
る。

〔発明の要点〕

本発明の要点は、輪郭に円弧または円弧を包絡
線とする形状を有し、重畳したものを含む複数の
物体を撮像した画像をラスター走査したのち、２
値化手段を介して２値化画像に変換し、前記円形
物体の位置と大きさを検出する装置において、前
記２値化画像における前記円形物体のパターンの
走査セグメント（ラインセグメント）の端部の座
標、隣接の前走査セグメントとの重なり、を検出
する画像特徴抽出手段と、前記画像特徴抽出手段
による前記重なりの情報に基づき、前記２値化画
像の全ての走査セグメントに独立パターンごとの
パターン番号を付加する連結性解析手段と、同一
のパターン番号を有する走査セグメントの端部の
座標を前記独立パターンの境界点の座標として検
出する境界点検出手段と、を設けることにより独
立パターンごとの境界点データを分離したのち、
前記独立パターンを外周に沿つて左回り（右回
り）に１周して前記境界点を追跡し、追跡の順に
並ぶ各境界点の座標、該境界点から隣接の境界点
に向かう追跡方向を示す方向コード、からなる外
周点列データ、または独立パターンごとの前記境
界点のうち前記外周点列に属する境界点を除いた
ものを当該のパターンの内周に沿つて前記外周の
場合と同様に追跡し、前記外周点列データと同様
な内周点列データ、のいずれか一方又は両方のデ
ータを出力する外／内周点追跡演算手段と、前記
外／内周点列データにおける前記方向コードの値
が、前記の追跡の順に増加（減少）している区間
における外／内周点列の座標を区分抽出して凹み
画像部すなわち各物体円の接続部を除き、凸画像
部すなわち各物体円に対応すると思われる部分ご
との外／内周・凸部点列データとして出力する凸
画像部分離手段と、前記外／内周・凸部点列デー
タを構成する外／内周代表点として出力する外／
内周・代表点選択手段と、前記外内周点を、演算
時間を短縮するために順次隣接する複数個の外／
内周点ごとに選択し外／内周代表点における、順
次隣接する３点を通る個別円弧の複数個の各中心
座標、半径を演算出力する個別円弧演算手段と、
前記個別円弧のうち中心座標、半径の値が共に近
い値を持つものを同一円に属するものとして分離
する同一円・個別円弧群分離手段と、これらの個
別円弧群に最小二乗法を適用して導かれる推定円
すなわち、同一円に属する前記の各個別円弧に対
応する各データを用いて推定円の中心座標、半径
を演算出力する推定円演算手段と、を設け前記推
定円演算手段は、各個別円弧の中心座標、半径の
各各の平均値を推定円の中心座標、半径のそれぞ
れの第１次近似値とし、各個別円弧に対応する
外／内周代表点の少くとも１部からなる点の座標
と推定円の中心座標との距離から該推定円の半径
を差引いた残差の２乗の和を最小とするような所
要次数の逐次近似を行うことにより演算の収束を
早め、演算時間を短縮するようにした点にある。

〔発明の実施例〕

以下第４図〜第１２図に基づいて本発明を説明
する。第４図は本発明検出装置の実施例の構成を
示すブロツク図である。同図において、１０は背
景、１１は検出対象の円形物体、１２はテレビカ
メラなどの撮像手段、２２は円形物体検出装置で
あり、１３は２値化回路、１４は画像メモリや画
像特徴抽出部を含む画像情報入力回路、１５は連
結性解析部、１６は境界点検出部、１７は外／内
周点追跡演算部、１８は凸画像部分離部、外／内
周・代表点選択部、個別円弧演算部を含む円弧演
算部、１９は同一円・個別円弧群分離部、最小二
乗円演算部を含む推定円演算部、２０は検出結果
出力部、２１は円の個数、位置、大きさを示す物
体円検出データである。

まず細部の説明に先立ち、第４図の概略の動作
を説明すると、背景１０上に円形物体１１が乗つ
ていて、それらの形状によつては、上方から撮像
手段１２で撮像すると重畳していることがある。
その画像をラスター走査したビデオ信号を２値化
回路１３で２値化して、第５図２４のような２値
画像に変換する。この２値画像の画像情報は、画
像メモリや画像特徴抽出部を含む画像情報入力回
路１４で、画像メモリ上に、DMAモードで書き
込まれる。連結性解析部１５では、前記画像特徴
抽出部から抽出された前記画像メモリ内の２値画
像のラインセグメント情報（ラインセグメントの
端部の座標、長さ、隣接ラインセグメントとの重
なり部の有無に基づく、属するパターンの番号な
どラインセグメントの特徴抽出データ）に基づい
て、一画面の走査終了後ラインセグメントの連結
性を解析し、同一の独立パターンに属するライン
セグメントに同一のパターン番号を付し、独立パ
ターン間の分離が行われる。境界点検出部１６で
は、独立パターンの境界点座標が、境界点の属す
るパターン番号とともに検出される。この境界点
情報は外／内周点追跡演算部１７で解析されて、
左回り（または右回り）の外周点列データ、およ
び境界点情報から該外周点列データを除くことに
より、内周点列データが得られる。

なおこの内周点列データは多くの円形物体の重
畳した場合、該円形物体の外周の一部が重なつた
パターンの内周に表われる場合に用いられるの
で、このような可能性が無ければこのデータの抽
出や以後の処理は不要となる。内周点列データに
対する以後の処理は外周点列データの場合と全く
同様であり、以下外／内周と書くときは外周、内
周のいずれか一方または両方を意味するものとす
る。また以下の説明は主として外周を対象として
説明する。

次に重畳円形画像の外／内周点列データから円
弧演算部１８において、外／内周上の各個別円弧
の半径と中心座標を求める。これらの個別円弧デ
ータにより、同一円に属する個別円弧データの集
合（同一円・個別円弧群データ）を求める。この
同一円・個別円弧群データから、推定円演算部１
９で推定円（最小または物体円とも呼ぶ）の位
置、大きさを求める。これにより、画像を構成す
る円形物体の個数、位置、大きさの３つの正確な
情報を得ることができる。これらの検出結果は検
出結果出力部２０から、物体円検出データ２１と
して外部に出力され、CRTなどのｉ／ｏ機器に
出力される。

円形物体は、重畳していない物体は勿論、重畳
しているものでも、完全に重なつて見えないもの
でない限り、輪部の一部が撮像手段１２により、
把えることができれば、この検出装置２２により
その全体を推定することができる。

以下に前記の各部の詳細な説明を行う。

第５図に２値化回路１３を介して２値化した後
の重畳した円形物体の２値画像２４を示す。有効
画面２３内に座標系Ｘ，Ｙが定義され、画像情報
入力回路１４によつて２値画像の幾何学的情報を
画像メモリに入力することができる。

第６図は、２個の物体の独立パターン２５，２
６を含む２値画像の例を示す。「Γ」印はパター
ン内の画素としての物体点２７を示す。独立パタ
ーン２５は孔がなく、独立パターン２６には１個
の孔２６１がある。

第７図は着目画素としての着目点Ａを中心とす
る８つの隣接画素からなる３×３マスクＭを示
し、Ｂを４近傍点、Ｃを８近傍点と呼ぶ。なお前
記物体点２７は次の５つに分類される。

(イ) 内点：４近傍点Ｂにすべて物体点２７がある
場合、 (ロ) 左点：左側に物体点２７がない場合、 (ハ) 右点：右側に物体点２７がない場合、 (ニ) 上点：左点でも右点でもなく、上側に物体点
２７がない場合、 (ホ) 下点：左点でも右点でもなく、下側に物体点
２７がない場合、 これで前記左点、右点、上点、下点の４つが境
界点（輪郭点）である。

１水平走査線上の物体点２７の連なりを前述の
ようにラインセグメントと呼び、画像情報入力回
路１４によつて抽出された前記ラインセグメント
情報に基づき、連結性解析部１５では、前述のよ
うに一画面の走査終了後各ラインセグメントの前
後の連結性を解析しラインセグメントの属する独
立パターンごとのパターン番号を各ラインセグメ
ントに与える。次に境界点検出部１６において、
各独立パターンの外周点および内周点を含む境界
点を求め、各境界点がどの独立パターンに属する
ものかを知ることができる。次に外／内周点追跡
演算部１７で、各独立パターンの境界点のデータ
から、各独立パターンごとの外周点列データ、内
周点列データすなわち外周または内周（孔２６
１）の境界点の座標と、該座標における後述の方
向コードを隣接の順に並べたデータ、を演算して
求める。

すなわち各独立パターンごとの境界点（左点、
右点、上点、下点）の左回り（または右回り）追
跡を行う。ここで左（右）回りとは、パターンの
輪郭の外周、内周を問はず、パターンを左（右）
側に見て追跡する方向を言うものとする。

第８図は、方向コードを示す。これは境界点を
追跡していく段階で、各着目点Ａと次の隣接の境
界点の位置との関係に応じて、図のように１〜８
の数字で追跡の方向を表現するものである。

この追跡の手順には種々の方法が知られてお
り、例えば本出願人による、特願昭58―9108号
「パターンの論郭追跡方法」に述べた方法を用い
ることができる。第６図はこのように各独立パタ
ーン２５，２６に外／内周点の左回り追跡を行つ
た結果を示す。このようにして各独立パターンご
とに、まず外周の輪郭点の追跡により各外周点の
座標と当該点における方向コードからなる前記外
周点列データが得られ、次に残りの輪郭点につい
て内周としての追跡により前記内周点列データが
求められる。

次に円弧演算部１８について説明する。この部
には凸画像部分離部、外／内周・代表点選択部、
個別円弧演算部が含まれる。

まずこの中の凸画像部分離部の動作を述べる。
前記外周点列データ内の方向コードは第９図の実
線矢印に示すように、凸形状の独立パターン９１
では、方向コードは反時計方向（後述の増加方
向）に回転するだけであるが、凹形状部９２１，
９２２を持つ独立パターン９２では、当該部９２
１，９２２で逆戻り（後述の減少方向への回転）
を行う。

また内周点列の方向コードの場合は第９図のパ
ターン９２を孔のパターン（従つてこのパターン
に対する外周のパターンは図外にあるものと仮定
する）とすると、方向コードは点線矢印のように
推移し、前記の凹形状部９２１，９２２は、この
場合には凸形状部に置換わり、残りの前記の凸形
状部は凹形状部とみなされる。この時方向コード
は凸形状部９２１，９２２では外周追跡と全く同
様に反時計方向（増加方向）に回転し、残りの凹
形状部で逆戻り（減少方向への回転）を行う。

第１０図は３個の円形物体２８，２９，３０の
画像を示す。独立パターンの数は、円形物体２９
と３０が重なつているために、１０１，１０２に
２個となる。外周点の情報は、前述の手順で各独
立パターンごとに求められている。そこで、独立
パターン１０１の場合は、方向コードは連続して
１→２→３→４→５→６→７→８→１→２→……
の方向（増加方向）に変化する。方向コードが外
周点追跡の途中で逆に、８→７→６→５→４→３
→２→１→８→７→……の方向（減少方向）に変
化する場所を探すと、円形物体２９と３０の画像
の境界点が交叉する場所として交点３１と３２を
みつけることができる。なおこの関係は内周にお
いて円形物体の交点を見付ける場合にも全く同様
にあてはまる。ただし輪郭の追跡の方向を右回り
としたときは前記の増加方向と減少方向とが入れ
替わる。

このようにして、交点３１と３２の近傍の境界
点を削除して、各凸画像部のデータのみからなる
境界点データ｛Pi，Ni，Fi｝を求める。ここで
Piは境界点（第１０図では外周点でもある）の座
標（xi，yi）であり、同時に座標の原点０から該
境界点の座標Piに向うベクトル（第１０図Vi）
とみなされる。なお以下境界点をこの座標で呼ぶ
こととする。

またNiは境界点Piの属する独立パターン１０
２の番号、Fiは境界点Piから隣接の境界点に向う
方向コード、またｉは同一の独立パターン上の各
境界点列（外周点列または内周点列）に順次付さ
れた番号である。

なおこのようなパターンの輪郭上の凸画像部を
検出する方法として、上記の方法を用いれば演算
時間が短くできる利点があるが、他の方法として
本出願人により出願されている特願昭58―76771
〓輪郭特徴検出方式〓における輪郭曲率の符号の
変化を用いることもできる。

次に個別円弧演算部においては次のような手順
で境界点Piに対応する個別円弧の中心のデータ
（座標、半径）を求める。

ここで同一の独立パターンについて着目すると
前記境界点データとしては、｛Pi，Fi｝だけを考
えれば良い。次に後述のように外／内周・代表点
選択部によつて選択された３つの境界点Pi−１，
Pi，Pi＋１（何れも第１０図）を考える。各点間
の線分をベクトルσ1，σ2と表わすと、 σ1＝Pi−Ｐ（ｉ−１） σ2＝Ｐ（ｉ＋１）−Pi となる。ここで｜σ1｜＝｜σ2｜のとき、つまり
前記２つの線分の長さが等しいとき、前記３つの
境界点を通る円弧（個別円弧）の半径R^o _iは下式
で求められる。

R^o _i＝Ｓ／２・sin（／２） ……(1) ただしここでＳはベクトルσ1またはσ2の絶対
値（該ベクトルを表わす線分の長さ）である。す
なわち、 Ｓ＝｜σ1｜＝｜σ2｜ ……(2) で表わされ、またσはベクトルσ1またはσ2に対
する前記の円弧の中心角を第１０図のように1，
2とすると、 ＝1＝2 ……(3) でありこれらは後述のように求められる。

ここで前記外／内周・代表点選択部の動作を述
べると、前記個別円弧を求める３点としてPi−
１，Pi，Pi＋１を外周点列｛Pi｝（外周点Piの集
合）から選択する方法としては、通常はベクトル
σ1とσ2の長さ（絶対値）が同じになるように、
または近似的に等しくなるように選択する。この
場合、外周点列｛Pi｝のすべてについて、このよ
うな個別円弧の計算をやるのではなく、あらかじ
め例えば５点飛びなどの予備代表点を選んだの
ち、その中から前記のような３点の組となる代表
外周点をそれぞれ求める。このようにして演算の
回数従つてその時間を短縮するのである。そして
これらの代表外周点はほぼ等間隔になるように、
方向コードを利用した周知の近似周長の算出方法
によるほぼ等距離の点を代表外周点として選択す
る。すなわち境界点Pi−１から点Piまでの外周点
列｛Pi｝（境界点のつらなり）の中で、方向コー
ドが１，３，５，７となる点すなわち水平または
垂直方向に追跡する点の数をno方向コードが２，
４，６，８となる点すなわち斜め方向に追跡する
点の数をneとするとき、点Pi−１から点Piまで
の周の長さ（弧の長さ）はその長さが比較的短い
ので、同時に、この間の弦の長さ、すなわち前記
ベクトルσ1の長さＳ１（前記のＳをさらに区分
してこのように名付ける）にほぼ等しく、前記(2)
式は Ｓ１＝｜σ1｜＝｜Pi−Ｐ（ｉ−１）｜no＋√
２ne …(2)―１ となつて長さＳ１が求められる。境界点Pi＋１
は、点Piからの周の長さ、従つてベクトルσ2の
長さＳ２（前記と同様にＳを区分する）がこの長
さＳ１に近い値（距離）となるように選ばれ前記
(2)―１式と同様にして長さＳ２が求められる。

次に再び個別円弧演算部の説明に戻り、このよ
うにすると前記(2)式のベクトルの長さは長さＳ
１，Ｓ２の平均値とみなすことができ、 Ｓ＝（Ｓ１＋Ｓ２）／２ と置くことにより、前記(1)式は、次式(1)―１の
ように変形されて半径R^o _iが求められる。

R^o _i＝（Ｓ１＋Ｓ２）／４・sin（／２）
…(1)―１ なおここでsin（／２）については前記(3)式の
関係があるときは、角度は第１０図のベクトル
σ1とσ2とのなす角に等しいので、ベクトルσ1と
σ2とのスカラー積（内積）σ1・σ2を算出するこ
とにより下式(4)からcosを求め、 cos＝σ1・σ2／Ｓ１，Ｓ２ …(4) 本式(4)式に次式(5)の関係を用いて求められる。

sin（／２）＝√（１−）／２…(5) なお、ここで(4)式のスカラー積σ1・σ2は、
σ1x，σ2x，σ1y，σ2yをそれぞれ各ベクトルσ1，
σ2のｘ軸、Ｙ軸成分とするとき、 σ1x＝（xi−ｘ（ｉ＋１）），σ2y＝（ｘ（ｉ＋１）−
xi） σ1y＝（yi−ｙ（ｉ−１）），σ2y＝（ｘ（ｉ＋１）−
yi） で表わされるので、次式により算出される。

σ1・σ2＝σ1x・σ2x＋σ1y・σ2y ＝（xi−ｘ（ｉ−１））（ｘ（ｉ＋１）−xi）＋
（yi−ｙ（ｉ−１））（ｙ（ｉ＋１）−yi） 他方第１０図における個別円弧の中心座標Ci
（xoi，yoi）（これは原点０から座標Ciに到るベク
トルとも考える。）は下式で求められる。

Ci＝｛（σ2−σ1）／｜σ2−σ1｜｝・R^o _i＋Pi…(6) この式は境界点Piから、円弧の中心座標Ciに向
う単位ベクトルｕが、 ｕ＝（σ2−σ1）／｜σ2−σ1｜ で表わされるので、点Piから円弧の中心Ciに向う
ベクトルは ｕ・R^o _i＝｛（σ2−σ1）／｜σ2−σ1｜｝・R^o _i となる関係を用いたものである。

以上で、代表外周点（境界点）Pi−１，Pi，Pi
＋１の３点から定まる個別円弧の中心座標Ciと半
径R^o _iが求まる。ここで前記の３点の中央の点Pi
を個別円弧代表点と呼ぶ。

なお個別円弧の中心を求める別法として、第１
１図の方法がある。これは、境界点Pi−１とPiを
結ぶ線分ｄ１の垂直２等分線ｈ１と、同じく境界
点Pi＋１とPiを結ぶ線分ｄ２の垂直２等分線ｈ２
の交点を個別円弧の中心Ciとする方法で、境界点
Piと円弧の中心Ciとの距離を半径R^o _iとするもの
である。この方法の場合、線分ｄ１とｄ２が近似
的に等しくなくても良い。このようにして前記境
界点データ｛Pi，Ni，Fi｝から、代表外周点
｛Pi｝（代表外周点Piの集まり）に対応する各個別
円弧の中心座標Ci、半径R^o _iの集まりの個別円弧
群データ｛Ci，R^o _i｝が得られる。

次に推定円演算部１９の説明に入る。この部に
は同一円・個別円弧群分離部、最小二乗円演算部
が含まれ、まず該分離部において前記の個別円弧
群データを、異なる番号ｉとｊのもの同志で比較
したとき、次式の条件を満たすものに分ける。

｜R^o _i−R^o _i｜＜ΔR（一定微小値） ｜Ci−Cj｜＜ΔC（一定微小値） つまり、半径がほぼ等しく、中心座標が近い円
弧の集合に分割する。このようにして、同一円・
個別円弧群データ｛Ci，R^o _i，Nci｝が得られる。
ここでNciは上記の手順で求められた番号ｉの個
別に円弧が属すると考えられる推定円（最小二乗
円、物体円）の番号を示す。

次に最小二乗円演算部は同一の推定円に属する
と考えられる推定円群データ、｛ci，R^o _i，Nci，
Pi，Pi−１，Pi＋１，Ni｝（ただし内部の各符号
は前記の通りである）を用いて、最小２乗法で推
定円の座標Co、半径Roを推定する。

すなわち第１２図において代表外周点（の座
標）をＰ１〜Ｐ６とし、３つの点（Ｐ１，Ｐ２，
Ｐ３）から求まる円弧の中心座標、半径をそれぞ
れ（Ｃ２，R^o ₂）とし、同様に点（Ｐ２，Ｐ３，
Ｐ４）、（Ｐ３，Ｐ４，Ｐ５）、（Ｐ４，Ｐ５，Ｐ
６）から定まる円弧の中心座標、半径をそれぞれ
（Ｃ３，R^o ₃）、（Ｃ４，R^o ₄）としたときに、円弧の
中心座標Ｃ２〜Ｃ４、半径R^o ₂〜R^o ₄、外周点の座
標Ｐ１〜Ｐ６から推定円の中心CO、半径ROを求
めるものである。

そこで推定円の中心COと前記の各個別円弧代
表点Piとの距離Riから推定円の半径ROを差引い
た残差（誤差）の２乗の和を最小にし得る推定円
の半径および中心座標COを求める方法（最小二
乗法）を取る。すなわち２乗誤差の和Ｉは下式で
表わされる。

Ｉ＝ 〓ⁱ （Ri−Ro）² ……(7) 従つて和Ｉを最小とする、推定円の半径RO、
中心座標CO〔＝（xo，yo）〕については、下式を
満たす必要がある。

δI／δx0＝δI／δy0＝δI／δR0＝０……(8) 従つて(8)式から次の３式が得られる。

〓ⁱ （（Ri−Ro）／Ri）（xi−xo）＝０ …(9)―１ 〓ⁱ （（Ri−Ro）／Ri）（yi−yo）＝０ …(9)―２ 〓ⁱ （（Ri−Ro）／Ri）＝０ (9)―３ 上記(9)―１，(9)―２，(9)―３の３式を解いて中
心座標（x0，y0）、半径R0の３つの値を求めれば
よい。しかしながら上記方程式は無理数を含んだ
超越方程式となり単純に解けないので、この３式
から次のような逐次方程式を導いて逐次近似法に
より求める。即ち第ｎ次近似で求められた解とし
ての推定円の中心座標、半径をそれぞれ（xⁿ ₀，
yⁿ ₀）、Rⁿ ₀で表わしたとき第（ｎ＋１）次近似に解
である推定円の中心座標、半径（xⁿ⁺¹ ₀，yⁿ⁺¹ ₀）、
Rⁿ⁺¹ ₀は、 xⁿ⁺¹ ₀＝〔 〓ⁱ xi＋Rⁿ ₀・xⁿ ₀・ 〓ⁱ （１／Rⁿ _i） −Rⁿ ₀・ 〓ⁱ （xi／Rⁿ _i）〕／Ｎ ……(10)―１ Yⁿ⁺¹ ₀＝〔 〓ⁱ yi＋Rⁿ ₀・yⁿ ₀・ 〓ⁱ （１／Rⁿ _i） −Rⁿ ₀・ 〓ⁱ （xi／Rⁿ _i）〕／Ｎ ……(10)―２ Rⁿ⁺¹ ₀＝〔 〓ⁱ Rⁿ _i〕／Ｎ ……(10)―３ ただしここでRⁿ _iは第ｎ次の推定円の中心座標
（xⁿ ₀，yⁿ ₀）と、前記の各個別円弧代表点Piとの距
離、すなわち、 Rⁿ _i＝√（−ⁿ ₀）²＋（−ⁿ ₀）²……(10)
―４ であり、Ｎは前記個別円弧の数である。

次に前記の逐次式(10)―１〜(10)―４の具体的な演
算に当つては解の収束を早めるために、第１次の
解を次式のように前記の各個別円弧の半径R^o _iお
よび、その中心座標Ciの平均値として計算を進め
る。すなわち第１次の推定円の中心座標（x¹ ₀，
y¹ ₀）、半径R¹ ₀は x¹ ₀＝〔 〓ⁱ x0i〕／Ｎ (11)―１ y¹ ₀＝〔 〓ⁱ y0i）／Ｎ ……(11)―２ R¹ ₀＝〔 〓ⁱ R^o _i〕／Ｎ ……(11)―３ として第２，３……ｎ次と計算を進めるもので
ある。このようにすれば通常ｎの値としては１〜
５回で収束させることができる。

このようにして推定円（最小二乗円）の大きさ
と位置が、精度良く求められる。以上の結果から
画像に含まれる円の個数、大きさ、位置が分り、
これが検出結果出力部２０を介し判定結果物体円
検出データ２１として出力される。

〔発明の効果〕

まず以上述べた本発明の主要構成部の機能を効
果を含めつつ要約すれば、 連結性解析部１５により、２値画像を独立パ
ターンごとに分離し、これらのパターンごとの
処理が可能となり独立した円形物体について
は、正しく円の推定を行うことができる。

境界点検出部１６と外／内周点追跡演算部１
７により、重畳した円形物体の２値画像の輪郭
を追跡して外／内周点列として整理された外／
内周点列データ｛Pi，Fi，Ni｝を作成し、 円弧演算部１８により、外／内周点列の凹み
部を方向コードFiで検出することにより、前記
外／内周点列データを、個々の凸画像部ごとの
外／内周点列データに分離することができ、そ
れぞれの該データから代表外／内周点を選択し
て、対応する各個別円弧の中心座標と半径の個
別円弧群データ｛Ci，R^o _i｝が得られる。

推定円演算部では、前記個別円弧群データ
が、各個別円弧の中心座標と、大きさの近い集
合に分離され、このようにして得られる同一
円・個別円弧データにつて、それぞれ、最小２
乗法による円としての推定円を求める。

このようにして画像の輪郭点に着目し、点集合
から円径集合、同一円集合などに多段階で分離し
ていき、かつ速やかに物体円の推定を行うことが
できる。

このようにして本発明によれば次のような円形
物体の位置、大きさ、個数を知ることができる。

(イ) 輪郭が円形形状の任意物体について、孔を除
外して、位置、大きさを知ることができる。

(ロ) 円形物体が重畳していても、輪郭の一部が、
２値画像に表われていれば、分離して検出する
ことができる。

(ハ) 外形形状に含まれる円弧部分の位置を知りた
い場合それを検出することができる。

(ニ) 円形物体でないものを、除外することが可能
である。

(ホ) 最小２乗法を用いる推定により、なめらかな
円形形状でなくても、つまり縁がギザギザし
て、円を包絡線としているものでも、その形状
を近似する円、を、従つて前記包絡線となる円
も推定できる。

【図面の簡単な説明】

第１図は従来の円形物体検出装置の構成を示す
ブロツク図、第２図，第３図は第１図装置の画像
の例を示す図、第４図は本発明の構成を示すブロ
ツク図、第５図は円形物体の重畳した場合の２値
画像を示す図、第６図は一般の２値画像の境界点
を示す図、第７図は３×３マスクにより連結性の
定義を説明する図、第８図は外周点の方向コード
を示す図、第９図は左回りに輪郭点を追跡して方
向コードが動くとき、凸図形では減少方向に逆戻
りすることはないことを説明する図、第１０図は
重畳物体の画像の個別円弧の大きさ、中心を求め
る方法を示す図、第１１図は同じく個別円弧の中
心と大きさを求める別の方法を示す図、第１２図
は推定円（最小２乗法円）を求める方法を説明す
る図である。 符号説明、１１…円形物体、１２…撮像手段、
１３…２値化回路、１４…画像情報入力回路、１
５…連結性解析部、１６…境界点検出部、１７…
外／内周点追跡演算部、１８…円弧演算部、１９
…推定円演算部、２０…検出結果出力部、２１…
物体円検出データ、２２…円形物体検出装置。

Claims (1)

1. 【特許請求の範囲】 １ 輪郭に円弧または円弧を包絡線とする形状を
   有する複数の物体を撮像した画像をラスター走査
   したのち、２値化手段を介して２値化画像に変換
   し、前記円形物体の位置と大きさを検出する装置
   において、前記２値化画像における前記円形物体
   のパターンの走査セグメントの端部の座標、隣接
   の前走査セグメントとの重なり、を検出する画像
   特徴抽出手段と、前記画像特徴抽出手段による前
   記重なりの情報に基づき、前記２値化画像の全て
   の走査セグメントに独立パターンごとのパターン
   番号を付加する連結性解析手段と、同一のパター
   ン番号を有する走査セグメントの端部の座標を前
   記独立パターンの境界点の座標として検出する境
   界点検出手段と、前記独立パターンを外周に沿つ
   て左回り（右回り）に１周して前記境界点を追跡
   し、追跡の順に並ぶ各境界点の座標、該境界点か
   ら隣接の境界点に向かう追跡方向を示す方向コー
   ド、からなる外周点列データ、または独立パター
   ンごとの前記境界点のうち前記外周点列に属する
   境界点を除いたものを当該のパターンの内周に沿
   つて前記外周の場合と同様に追跡し、前記外周点
   列データと同様な内周点列データ、のいずれか一
   方又は両方のデータを出力する外／内周点追跡演
   算手段と、前記外／内周点列データから前記の境
   界点の追跡における凸画像部の外／内周点列の座
   標を区分抽出して外／内周・凸部点列データとし
   て出力する凸画像部分離手段と、前記外／内周・
   凸部点列データを構成する外／内周点を、順次隣
   接する複数個の外／内周点ごとに選択し外／内周
   代表点として出力する外／内周・代表点選択手段
   と、前記外／内周代表点における、順次隣接する
   ３点を通る個別円弧の複数個の各中心座標、半径
   を演算出力する個別円弧演算手段と、前記個別円
   弧のうち中心座標、半径の値が共に近い値を持つ
   ものを同一円に属するものとして分離する同一
   円・個別円弧群分離手段と、同一円に属する前記
   の各個別円弧に対応する各データを用いて推定円
   の中心座標、半径を演算出力する推定円演算手段
   と、からなることを特徴とする円形物体検出装
   置。 ２ 特許請求の範囲第１項に記載の検出装置にお
   いて、前記推定円演算手段は、各個別円弧の中心
   座標、半径の各々の平均値を推定円の中心座標、
   半径のそれぞれの第１次近似値とし、各個別円弧
   に対応する外／内周代表点の少くとも１部からな
   る点の座標と推定円の中心座標との距離から該推
   定円の半径を差引いた残差の２乗の和を最小とす
   るような所要次数の逐次近似を行うことを特徴と
   する円形物体検出装置。 ３ 特許請求の範囲第１項または第２項に記載の
   検出装置において、前記凸画像部分離手段は、前
   記外／内周点列データにおける前記方向コードの
   値が、前記の追跡の順に増加（減少）している区
   間における外／内周点列の座標を区分抽出する手
   段であることを特徴とする円形物体検出装置。