JPS6029878A - 円形物体検出装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

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

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

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

ところが重なり合っている物体をＴＶカメラで撮像した
場合には、撮像した画像は１つの物体として映るため、
各物体の正しい大きさをめることができなかった。

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

ところが、この装置の場合には糸尻部が鮮明に出る必要
があるためＫ。

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

〔発明の目的〕

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

〔発明の要点〕

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

〔発明の実施例〕

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

まず細部の説明に先立ち、第４図の概略の動作を説明す
ると、背景１０上に円形物体１１が乗っていて、それら
の形状によっては、上方から撮像手段１２で撮像すると
重畳していることがある。

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

なおこの内周点列データは多くの円形物体の重畳した場
合、該円形物体の外周の一部が重なったパターンの内周
に表われる場合に用いられるので、このような可能性が
無ければこのデータの抽出や以後の処理は不要となる。

内周点列データに対する以後の処理は外周点列データの
場合と全く同様であり、以下外／内周と書くときは外周
、内周のいずれか一方または両方を意味するものとする
。

また以下の説明は主として外周を対象として説明する。

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

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

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

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

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

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

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

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

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

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

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

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

まずこの中の凸画像部分＃齢の動作を述べる。

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

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

第１０図は３個の円形物体２Ｂ　、　２９　、３０の画
像を示す。独立パターンの数は、円形物体２９と３０が
重なっているために、１０１　、１０２の２個となる。

外周点の１ｈ報ば、前述の手順で各独立パターンごとに
められている。そこで、独立パターン１０１の」場合は
、方向コードは連続して１→２→３→４→５→６→７→
８→１→２→・・・の方向（増加方向）に変化する。方
向コードが外周点追跡の途中で逆に、８→７→６→５→
４→３→２→１→８→７→・・・の方向（減少方向）に
変化する場所を探すと、円形物体２９と３０の画像の境
界点が交叉する場所として交点３１と３２をみつけるこ
とができる。′／工おこの関係は内周において円形物体
の交点ン児付ける場合にも全く同様にあてはまる。

ただし輪郭の追跡の方向を右回りとしたときは前記の増
加方向と減少方向とが入れ替わる。

このようにして、交点３１と３２の近傍の境界点を削除
して、各凸画像部のデータのみからなる境界点データ は境界点（第１０図では外周点でもある）の座標（ｘｉ
、ｙｉ）　であり、同時に座標の原点Ｏから該境界点の
座標Ｐｉに向うベクトル（第１０図Ｖｉ）とみなされる
。な゛お以下境界点をこの座標で呼ぶこととする。

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

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

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

ここで同一の独立パターンについて層目すると前記境界
点データとしては、（Ｐｉ、Ｆ’ｉＪだ＾えれば良い・
次に後述のように外／内周・代表、侭選択部によって選
択された３つの境界点Ｐｉ−１，Ｐｉ。

Ｐｉ＋１（何れも第１０図）を考える。各点間の線分を
ベクトルσ１．σ２と表わすと、 σｌ　＝Ｐ　ｉ　−Ｐ（ｉ　−１’） Ｃ２＝１’（ｉ　＋　Ｄ−Ｐ　ｉ となる。ここで１０１１＝１σ２１のとき、つまり前記
２つの線分の長さが等しいとぎ、前記３つの境界点を通
る円弧（個別円弧）の半径Ｒ−ま下式でめられる。

ｋＬ？＝　Ｓ／　２−　ｓｉｎ　（９’／２１・−・−
・（１１ま ただしここでＳはベクトルσ１またはＣ２の絶対値（該
ベクトルを表わす線分の長さ）である。すなわち、 ｓ＝１σ１１−１σ２１　・・・・・・・・・・・・・
・・・・・　（２）で表わされ、またψはベクトルσ１
また（まＣ２に対する前記の円弧の中心角を第１０図の
ように９１゜ψ２とすると、 ψ＝ψ１−ψ２　・・・・・・・・・・・・・・・・・
・・・・・・・（３）でありこれらは後述のようにめら
れる。

ここで前記外／内周・代表点選択部の１）ＩＩＩｆ′「
を姻Σべると、前記個別円弧をめる３点としてＰｉ−１
１Ｐｉ、　Ｐｉ＋１を外周点列（Ｐｉ）（外周点ＩＪ　
ｉσ）集合）から選択する方法としては、通當＆−１ベ
クトルσｌとＣ２の長さく絶対値）が同じになるように
、または近似的に等しくなるように選択する。この場合
、外周点列（Ｐ　ｉ　’１のすべてにすし−で、このよ
う７’、Ｃ（ｌ！ｊ別円弧の計算をやるのではなく、あ
ら力・じめ追・号えば５点飛びなどの予備代表点を選ん
プこσ）ち、そσつ中から前記のような３点の組となる
代表外Ｊｆｄ　ＡＬをそれぞれめる。このようにしてイ
寅ｊ４−の回数従ってその時間を短編するのである。そ
してこね、らσ）代表外周点はほぼ等間隔になるように
、方１１１」コードを利用した周知の近似周長の算出方
法によるｔ’ｔぼ等距離の点を代表外周点として選ルく
する。−４−１ぶわち境界点Ｐｉ−１から点Ｐｉでσ〕
外）月、＠１ｊＩＩ　（Ｐ　ｉ　）（境界点のつらなり
）の中で、方１１」コード力′−１゜３．５．７となる
点すなわち水平まプこ（ま垂直）ｊｌｌ」に追跡する点
の数をｎｏ方向コード力′−２、４、６、８となる点す
なわち斜め方向に追跡する。屯σ）数をｎｅとするとき
、点Ｐ　ｉ−１から点Ｐｉ　までの周の長さく弧の長さ
）はその長さが比較的短いので、同時罠。

この間の弦の長さ、すなわち前記ベクトルσ１の長さｓ
ｌ（前記の８をさらに区分してこのように名付ける）に
ほぼ等しく、前記（２）式はＳ　ｉ＝ｌ　ａ　１１＝ｉ
Ｐ　ｉ　−Ｐ＜１−１）ｌ；ｎ　ｏ　＋ＪＮ　ｎｅ−＝
（２）−１となって長さＳｌがめられる。境界点Ｐｉ＋
１は、点Ｐｉからの周の長さ、従ってベクトルσ２の長
さｓ２（前記と同様にＳを区分する）がこの長さＳｌに
近い値（距離）となるように選ばれ前記（２）−１式と
同様にして長さＳ２がめられる。

次にｆ）び個別円弧演算部の説明に戻り、このようにす
ると前記（２）式のベクトルの長さは長さＳｌ。

Ｓ２の平均値とみなすことができ、 Ｓ＝（Ｓ１＋８２）／２ と置くことにより、前記（１）式は、次式（１）−１の
ように変形されて半径Ｒがめられる。

！ Ｒ０＝　（Ｓ１＋８２）／４　・５ｉｎ（ψ／２）・・
・・・・（１）−１なおここで５ｉｎ（ψ／２）につい
ては前記（３）式の関係かあるときは、角度ψは第１０
図のベクトルσ１とＣ２とのなす角に等しいので、ベク
トルσ１とＣ２とのスカラー積（内積）σｌ・Ｃ２を丁
）−出することにより下式（４）からｃｏｓψをめ、ｃ
ｏｓψ＝σ１・Ｃ２／Ｓ１・Ｓ２・・・・・・・・・・
・・（４）本式（４）に次式（５）の関係を用いてめら
れろ。

５ｉｎ（ψ／２）−Ｊ（１−ＣＯ５−９＋）／２　・・
−（５１なお、ここで（４）式のスカラー積σＪ・Ｃ２
は、σ１ｘ＋σ２ｘ、σ１ｙ、σ２ｙをそれぞれ谷ベク
トルσ１．σ２のＸ軸、Ｙ軸成分とするとき、 σｌ　ｘ＝　（ｘ　ｉ　−ｘｔｉ　−１））　、　０２
ｙ＝（ｘｔｉ＋１ｌ−ｘｉ　）Ｃ１ｙ＝（ｙｉ　−ｙ（
ｉ　−１１）　、　”２ｙ＝（Ｘ（ｉ＋１ｌ−ｙｉ　）
で表わされるめで、次式により算出される。

σＩＩＩσ２−σ１ｘＩＩσ２ｘ＋σ１ｙ・Ｃ２ｙ＝（
ｘｉ　−ｘ（ｉ−Ｄ）（ｘ＋＋ｐ−ｘｉ　）＋（ｙｉ　
−ｙ（ｉ−１す（ｙｉ＋１Ｍ”　１他方第１０図におけ
る個別円弧の中心座標Ｃ１（ｘｏｉ。

ｙｏｉ）（これは原点Ｏから座標Ｃ１に到るベクトルと
も考える。）は下式でめられろ。

Ｃ１＝（（Ｃ２−ａ　ｌ　）／４１σ２−σ１１）・）
Ｌ、＋Ｐｉ・・・・・・（６）この式は境界点Ｐｉから
、円一連の中心座Ｊ　Ｃｉに向う単位ベクトルＵが、 ｕ　＝（ａ　２−ａ　１　）　／　ｌ　ａ　２−ａ　ｌ
　ｌで表わされるので、点Ｐ！から円弧の中心Ｃｉに向
うベクトルは ｕ　−Ｒ？＝　（（ａ　２−ａ　１　）／Ｉσ２−σ月
ｓ　・Ｒ？１　宣 となる関係を用いたものである。

以上で、代表外周点（境界点）　Ｐｉ　−１、Ｐｉ　、
Ｐｉ＋１０３点から足まる個別円弧の中心座標Ｃｉと半
径Ｒ０かまる。ここで前記の３点の中央の点Ｐｉ乞個別
円弧代表点と呼ぶ。

なお個別円弧の中心をめる別法として、第１１図の方法
がある。これは、境界点Ｐｉ−１とＰｉを結ぷ線分ｄ１
の垂直２等分線ｈ１と、同じく境界点Ｐｉ＋１とＰｌを
結ぶ線分ｄ２の垂直２等分線ｈ２の叉点を個別円弧の中
心Ｃｉとする方法で、境界点ＦＩと円弧の中心Ｃｉとの
距離を半径Ｒ１とするもの！ である。この方法の場合、線分ｄ１とｄ２が近似的に等
しくなくても良い。このようにして前記境界点データ（
Ｐｉ、　Ｎｉ、　Ｆｉ　）から、代表外周点（Ｆｉｌ（
代表外周点Ｐｉの集まり）に対応する各個別円弧の中心
座ａｔ　Ｃｉ　ｌ半径牡几、の集まりの個別円弧群デー
次に推定用演算部１９の説明に入る。この部には同一円
・個別円弧群デ一部、最小二乗円演算部が含まれ、まず
該分離部において前記の個別円りｔデータを、異なる番
号ｉとｊのもの同志で比較したとき、次式の条件を満た
すものに分ける。

１几、　−、ａ、　１　＜ΔＲ（一定微小値）葺　」 １ｃｉ−Ｃｊｌ＜ΔＣ（一定微小値） つまり、半径がほぼ等しく、中心座標が近い円弧の集合
に分割１−る。このようにして、同一円に含まれると考
えられる同一円・個別円弧群データ（Ｃｉ、Ｒ，、Ｎｃ
ｉＪが得られる。ここでＮｃｉは上記の手順でめられた
番号ｉの個別の円弧が属すると考えられる推定用（最小
二乗円、物体円）の番号を示す。

次に最小二乗円演算部は同一の推定用に属すると考えら
れる推定内押データ、（（−＋、ｉ（・、、ＮＣＩ。

Ｐｉ　、　Ｐｉ　−１、Ｐｉ十ｔ　、　Ｎｉ　ｌ　（た
だし内部の各符号は前記の通りである）を用いて、最小
２乗法で推定用の座標Ｃｏ、半径Ｒｏな推定１−る。

すなわち第１２図において代表外周点（の座標）をＰ１
〜Ｐ６とし、３つの点（ＰＬ、Ｐ２．Ｐ３）からまる円
弧の中心座標、半径をそれぞれ（Ｃ２ＪＬ２）とし、同
様に点（Ｐ２．Ｐ３．Ｐ４）、（Ｐ３．Ｐ４．Ｐ５　）
、（Ｐ４．ｉ’５．Ｐ６）から定まる円弧の中心座標、
半径をそれぞれ（Ｃ３，几）、（Ｃ４，几、）としたと
きに、円弧の中心座標Ｃ２〜Ｃ４、半径Ｒ２〜Ｒ４、外
周点の座標Ｐ１〜Ｐ６から推定用の中心ＣＯ２半径几０
をめるものである。

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

１　＝　Ｘ　（Ｒｉ　−Ｒｏ　）・・・・・・・・・・
・・・・・・・・・・・・・・・・・（７）従って和■
を最小とする、推定用の半径１−ＬＯ，中心座標ＣＯ（
−＝（ｘ　ｏ　ｒ　ｙｏ　）　）については、下式を満
たす必要がある。

δ１／δｘｇ＝δ■／δｙＯ＝ｂＩ／δＲＯ＝　０　・
・・・−＋８１従ってり８）式から次の３成力″−得ら
れる。

Ｊ（（Ｒｉ−几ｏ）／Ｒｉ）（ｘｉ−ｘｏ）＝Ｏ・・−
（９１１Σ（（Ｒ１−Ｒｏ）／Ｒｉ　）（ｙｉ−ｙｏ）
＝０・・・・・・（９）−２五 ハ（則−Ｒｏ）／Ｒｉ）＝Ｏ・・・・・・・・・・・・
＋９）−３上記（９）−１、（９）−２、（９）−３の
３式を解〜・て中心座標（ｘｏ、ｙＯ）、半径九００３
つの値をめれ（′ｆ。

よい。しかしながら上記方程式は無理数を含んだ超越方
程式となり単純にｊ！＃けな（・ので、この３式から次
のような逐次方程式を導〜・て逐次近似法によりめる。

即ち第１次近似でめられた解としての推定用の中心座標
、半径をそれぞれ（ＸＳ　＋　’／”０）　＋Ｐで表わ
したとき第（ｎ＋１）次近似の解である推ｎ＋１　ｎ＋
１　ｎ＋１ 定日の中心座標、半径（ｘｏｔＹ　ＬＲ０＆ｔ、ｘ”’
　＝（Ｊ　ｘｉ　＋Ｒ”、−ｘ”、−Ｘ（１／１（７）
−Ｒ”、・Ｊ（ｘｉ／１（７））／　Ｎｏ　１　１ ・・・・・・・・・（１０）　−１ ・・・・・・・・・（１０）　−ま ただしここでＰは第１次の推定用の中・し・座標（’＋
ｙ”）と、前記の各個別円弧代表点Ｐｉとの距離、０　
０ すなわち、 ｉｔ↑＝　（ｘｉ−ｘ”　）”＋　（冒７ｙ　・・・・
・・・・・・・・（１０）　−４１００ であり、Ｎは前記個別円弧の数である。

次に前記の逐次式（１０）−１〜（１０）−４の具体的
な演算に当っては解の収束を早めるために、第１次の解
を次式のように前記の各個別円弧の半径Ｒ。

および、その中心座標Ｃ！の平均値として計算を進める
。すなわち第１次の推定円の中心座標（ｘｏ。

ｙ）、半径Ｒは ０ ｘ　＝（賓ｘＯｉ）／Ｎ　・−・−・・・−（１１）　
−１ｏ。

Ｙ　＝Ｃ：ｙＯｉ〕／Ｎ　・・・・・・・・・（１１）
　−２０鳳 几＝〔ギ几）／Ｎ　・・・・・・・・・（１１）　−３
１１ として第２，３・・・・・・ｎ次と計算を進めるもので
ある。このようにすれば通常ｎの値としては１〜５回で
収束させることができる。

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

〔発明の効果〕

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

■　境界点検出部１６と外／内周点追跡演算部１７によ
り、重畳した円形物体の２値画像の輪郭を追跡し【外／
内周点列として整理された外／内周点列データ（Ｐｉ　
、Ｆｉ　、Ｎｉ　）を作成し、データを、個々の凸画像
部ごとの外／内周点列データに分離することができ、そ
れぞれの該データから代表外／内周点を選択して、対応
する各個別円弧の中心座標と半径の個別円弧群データ（
Ｃｉ。

Ｒ，）が得られる。

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

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

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

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

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

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

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

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

【図面の簡単な説明】

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

Claims (1)

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