(57)【特許請求の範囲】
【請求項１】
入力画像を細線化して得られる入力線画を１方向に走査して該入力線画と各走査線との交点の座標を求め、次いで同一走査線上の交点間の中点の座標を各走査線について求めて上記中点が描く図形からなる中点図面を作成し、該中点図面から線分を抽出することにより、円ないし楕円を検出する方法において、
上記入力線画の存在する領域を、該線画の近傍に存在するノイズ領域をも含むように拡張してグルーピングし、該グルーピングされた画像を細線化し、該細線化された画像について、上記走査線との交点の座標を求める処理を行なうとともに、
上記入力線画と走査線との交点の座標を求める処理に先立って、上記入力線画から直線成分を抽出して該直線をマスクするマスク画像を生成し、該マスク画像と上記入力線画との論理積を求めることにより、上記入力線画から直線を除去する処理を行なうことを特徴とする円ないし楕円の検出方法。
【請求項２】
入力画像を細線化して得られる入力線画を１方向に走査して該入力線画と各走査線との交点の座標を求め、次いで同一走査線上の交点間の中点の座標を各走査線について求めて上記中点が描く図形からなる中点図面を作成し、該中点図面から線分を抽出することにより、円ないし楕円を検出する装置において、
上記入力線画の存在する領域を、該線画の近傍に存在するノイズ領域をも含むように拡張してグルーピングするグルーピング手段と、
上記グルーピングされた画像を細線化する細線化処理手段と、
上記入力線画から直線を除去する直線除去手段とを備え、
上記直線除去手段が、上記入力線画から直線成分を抽出して該直線をマスクするマスク画像を生成し、かつ該マスク画像と上記入力線画との論理積を求める手段よりなることを特徴とする円ないし楕円の検出装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、入力画像から円ないし楕円を検出する方法およびその装置に関する。
【０００２】
【従来の技術】
従来より、入力画像を処理して、入力画像の中から円ないし楕円パタンを検出する方法として、パタン境界と走査線との交点の中点を利用する技術が知られている（特開平５−１０７０３０号公報参照）。
【０００３】
図１６は、このような従来の円ないし楕円の検出方法の一例における処理の流れを示すフロ−チャ−トであり、ステップＳ１〜Ｓ８の工程からなる。
【０００４】
（１）画像入力〜細線化（Ｓ１〜Ｓ４）
入力画像に微分フィルタを適用してエッジ画像を得、このエッジ画像に対して、２値化および細線化処理を施し、線幅が１の線画を得る。
【０００５】
（２）中点画像の作成（Ｓ５）
入力画像に図１７（ａ）に示すような座標系を設定し、入力線画を水平方向（ｘ方向）に走査して、入力線画と各走査線との交点の座標を求める。
【０００６】
すなわち、図１７（ｂ）に示すように、走査線ｙ＝ｋと入力線画Ａ，Ｂとの交点をｘ1，ｘ2，…，ｘnとし、この中の２つの交点［ｘi，ｘj］の中点の座標をＣij（(ｘi＋ｘj)/２，ｋ）、２点間の距離をｄij＝｜ｘi−ｘj｜とする。そして、全ての交点の組合わせについて中点の座標と距離とを求め、それを中点図面の（(ｘi＋ｘj)/２，ｋ）の位置に重みｄijとしてプロットする。この処理をｙ＝０からｙ＝ＹMAXまで繰り返し、図１７（ｃ）に示すような中点図面を得る。
【０００７】
中点図面では、円ないし楕円は直線に変換され、同時に、平行線および長方形等も直線に変換される。
【０００８】
（３）円ないし楕円の検出（Ｓ６）
中点図面中の線分を抽出することにより、円ないし楕円を検出する。線分の検出はハフ（Hough）変換法を用いる。この場合、上記重みを参照することにより、円ないし楕円と長方形との区別が可能になる。すなわち、長方形の場合、重みは線分に沿って一定の値を示すが、円ないし楕円の場合、重みは線分の両端で最小値を、線分の中央付近で最大値をとる。
【０００９】
（４）円ないし楕円のパラメータ推定（Ｓ７）
検出した線分と重みとから円ないし楕円のパラメータ（中心座標、半径、軸の傾き）を推定する。検出された線分を構成する中点について、この中点から所定距離だけ離れた位置にウインドウを設け、このウインドウないに存在する点を候補点とする。そして、これら候補点に対して最小二乗法を適用することにより、円ないし楕円のパラメータを決定する。
【００１０】
【発明が解決しようとする課題】
ところで、上述した従来の円ないし楕円の検出方法には下記に示すような種々の問題点が存在する。
【００１１】
（イ）従来方法では、中点検出は原画像中で所定のしきい値よりも大きな値を持つ点である特徴点の全てについて中点を作成していた。しかしながら、例えば図１７（ｂ）に示すように、全ての点に対して中点を作成すると、図１７（ｃ）に示すように、作成する中点の数が画像中の特徴点の数の二乗のオーダーで増加するため、莫大な演算時間を必要とし、計算コストが増大するする。
【００１２】
（ロ）図１８（ａ）および図１９（ａ）に示すように、画像を微分して２値化かつ細線化した入力線画にノイズが含まれていると、図１８（ｂ）および図１９（ｂ）に示すように不必要な中点が抽出されるため、処理時間の増大や検出精度および信頼性の低下を招く。
【００１３】
例えば、図１９（ａ）に示す入力線画の円に対する中点画像は、図１９（ｂ）に示すように線分として検出できるが、入力線画に含まれている直線状のノイズは、余分な楕円として抽出されることになる。
【００１４】
（ハ）線分の検出に用いられるハフ変換処理は、莫大な演算時間を要するため、これによっても計算コストが増大する。
【００１５】
そこで、本発明は、入力画像を細線化して得られる入力線画を１方向に走査して該入力線画と各走査線との交点の座標を求め、次いで同一走査線上の交点間の中点の座標を各走査線について求めて上記中点が描く図形からなる中点図面を作成し、該中点図面から線分を抽出する場合に、不必要な中点の算出の阻止等によって処理時間の短縮と処理の信頼性の向上を図った円ないし楕円を検出する方法およびその装置を提供することを目的とする。
【００１６】
【課題を解決するための手段】
本発明による円ないし楕円の検出方法は、請求項１に記載されているように、上記入力線画の存在する領域を、該線画の近傍に存在するノイズ領域をも含むように拡張してグルーピングし、該グルーピングされた画像を細線化し、該細線化された画像について、上記走査線との交点を求める処理を行なうことを特徴とする。
【００１７】
また、本発明による円ないし楕円の検出方法は、上記入力線画と走査線との交点の座標を求める処理に先立って、上記入力線画から直線を除去する処理を行なうことを特徴とする。
【００１８】
この直線を除去する処理に際しては、上記入力線画から直線成分を抽出して該直線をマスクするマスク画像を生成し、該マスク画像と上記入力線画との論理積を求めることが好ましい。
【００１９】
本発明による円ないし楕円の検出装置は、請求項２に記載されているように、上記入力線画の存在する領域を、該線画の近傍に存在するノイズ領域をも含むように拡張してグルーピングするグルーピング手段と、該グルーピングされた画像を細線化する細線化処理手段とを備えていることを特徴とする。
【００２０】
また、本発明による円ないし楕円の検出装置は、上記入力線画から直線を除去する直線除去手段を備えていることを特徴とする。
【００２１】
上記直線除去手段は、上記入力線画から直線成分を抽出して該直線をマスクするマスク画像を生成し、かつ該マスク画像と上記入力線画との論理積を求める手段よりなることが好ましい。
【００２２】
【作用および発明の効果】
請求項１および２に記載された発明によれば、入力画像中の領域を拡張して実領域とノイズ領域をグルーピングし、グルーピングされた画像を細線化していることにより、ノイズ成分が除去されるから、不必要な中点の抽出が防止され、処理時間の短縮や、円ないし楕円の検出精度の向上および信頼性の向上を図ることができる。
【００２３】
また、入力線画と走査線との交点座標を求める処理に先立って、入力線画から予め直線成分を除去しているから、長方形や平行線から生成される不必要な中点の算出が防止され、処理の高速化および信頼性の向上を図ることができる。
【００２４】
【実施例】
以下、図面を参照して本発明の実施例について説明する。
【００２５】
図１は、本発明による円ないし楕円を検出する装置の１実施例の構成を示すブロック図で、図２は、本装置における処理手順を示すフロ−チャ−トである。図２のＳ１１〜Ｓ１９は各工程を示す。
【００２６】
図１の装置は、画像を入力する（Ｓ１１）撮像部１と、撮像部１からのアナログ信号をデジタル信号へ変換するＡ／Ｄ変換部２と、デジタル画像データを格納する画像メモリ３と、画像メモリ３に格納されている画像の微分画像を得る（Ｓ１２）微分処理部４と、微分画像を２値化する（Ｓ１３）２値化処理部５と、画像の領域を拡張する（Ｓ１４）グルーピング装置６と、画像を細線化する（Ｓ１５）細線化処理部７と、細線化された画像から直線を除去する（Ｓ１６）直線除去装置８と、画像にラベルを付ける（Ｓ１７）ラベル付け装置９と、円ないし楕円を抽出し（Ｓ１８）、該円ないし楕円の中心座標を出力する（Ｓ１９）円抽出装置１０とによって構成されている。
【００２７】
次に、各装置の機能について説明する。
【００２８】
（イ）グルーピング装置６および細線化処理部７
このグルーピング装置６は、画像を微分して２値化した入力画像に図１８（ａ）に示すようにノイズが含まれていると、図１８（ｂ）に示すように不必要な中点が抽出されて複雑な中点図面が生成されるのを防止するために設けられるもので、図３（ａ）に示すような入力画像中の領域を拡張して、図３（ｂ）に示すように、実画像領域とこれに隣接するノイズ領域とをグルーピングする。そして、このグルーピングされた画像に対して細線化処理部７で細線化を行なうことにより、図３（ｂ）に示すようにノイズの除去された細線化画像を得、この細線化画像から図３（ｄ）に示すような中点図面を得るものである。したがって、処理時間の短縮、精度および信頼性の向上を図ることができる。
【００２９】
（ロ）直線除去装置８
直線除去装置８は、入力線画に図１７（ｂ）の右方に示すような直線成分が含まれていると、図１７（ｃ）に示すように不必要な中点が抽出されるのを防止するために、図４（ａ）に示すような入力線画から、図４（ｂ）に示すように直線成分を除去して、図４（ｃ）に示すような中点図面を得るために設けられるものである。この直線除去装置８を設けることによって、処理の高速化および信頼性の向上を図ることができる。
【００３０】
図５は、直線除去装置８の構成を示すブロック図で、図６のＳ２１〜Ｓ２５は本装置における処理手順を示すフロ−チャ−トである。直線除去装置８は、線画入力部１１と、マスク画像生成部１２と、直線除去部１３とによって構成されている。
【００３１】
マスク画像生成部１２では、図７（ａ）に示すような入力線画から、図７（ｂ）に示すように直線成分を抽出し、この抽出した直線領域を拡張して、図７（ｃ）に示すような直線をマスクする直線マスク画像を生成する。そしてマスク部を０、それ以外の部分を１とする。
【００３２】
上記直線成分の抽出方法の１例として、例えば直線成分が水平成分と垂直成分とからなる場合、微分画像を水平方向および垂直方向に走査して、同一垂直線上の微分値および同一水平線上の微分値をそれぞれ加算すれば、直線成分の位置で大きな加算値が得られることによって、直線成分を抽出することができる。
【００３３】
直線除去部１３では、図８（ａ）に示すような入力線画から、図８（ｂ）に示すようなマスク画像のマスク部を除去して、図８（ｃ）に示すような直線除去画像を作成する。具体的には、入力線画とマスク画像との論理積を求めると、直線除去画像が得られる。ただし、入力線画中で線部を１、それ以外の部分を０とする（表１参照）。
【００３４】
【表１】
0003694911.tif 000002
【００３５】
（ハ）ラベル付け装置９（１）
ラベル付け装置９は、例えば図１９（ａ）に示す入力線画の円に対する中点画像は、図１９（ｂ）に示すように線分として検出できるが、入力線画に含まれている直線状のノイズは、余分な楕円として抽出されることになるのを防止するために、中点検出に先立って、入力線画中の個々の連結成分に対して異なった名前のラベルを割り当てる（ラベリング）装置である。
【００３６】
例えば、図９（ａ）に示す入力線画では２つの連結成分が存在しているために、各連結成分に対して１と２のラベルが付けられる。そして、同一のラベルの付された連結成分毎に中点を検出するようにすれば、図９（ｂ）に示すように、不要な中点を検出しなくても良くなる。
【００３７】
このように、同一のラベルの付された２点のみから中点を求めることにより、ことなる２つの図形から生成される中点や、ノイズにより生成される中点をなくすことができ、これによって、円ないし楕円の検出精度の向上、誤検出の防止および処理時間の短縮等を図ることができる。
【００３８】
（ニ）ラベル付け装置９（２）
例えば、図１０（ａ）に示すように、入力線画が、各２本の水平線（走査線と同一方向）および垂直線で構成された長方形を含み、上記（ハ）のラベル付け装置９（１）において、この長方形に対しては同一のラベルを付して、中点を検出するようにした場合、図１０（ｂ）に示すように、垂直に並ぶ中点列の上下に、走査線と同一線上に無数に並ぶ中点によって２本の水平線が作成されて工字状を呈することになる。
【００３９】
そこで、ラベル付け装置９（２）においては、中点を求めたい同一ラベルの２点Ｐi，Ｐjの中点Ｃijのラベルを調べ、点Ｐiと点Ｃijのラベルが同一であれば、中点を作成しないようにしている。このようにすることにより、図１０（ｃ）に示すように、不要な上下の冗長な水平線を削除することができ、さらに処理時間の短縮を図ることができる。
【００４０】
図１１は、ラベル付け装置９（２）における処理のフロ−チャ−トを示す。先ずＸＹ座標の初期値をＸ＝１，Ｙ＝１とし（Ｓ３１）、点（Ｘ，Ｙ）にラベルが付いているか否かを調べる（Ｓ３２）。点（Ｘ，Ｙ）にラベルが付いていなければ（Ｓ３２：ＮＯ）、探索するＸ座標の値を１増やし（Ｓ３３）、Ｘ座標の右端か否かを調べ（Ｓ３４）、右端に達しない間は（Ｓ３４：ＮＯ）、Ｓ３２へ戻る。Ｘ座標の右端に達した場合は（Ｓ３４：ＹＥＳ）、探索するＹ座標の値を１増やし（Ｓ３５）、Ｙ座標の下端か否かを調べ（Ｓ３６）、下端に達しない間は（Ｓ３６：ＮＯ）、Ｓ３２へ戻り、下端に達した場合は（Ｓ３６：ＹＥＳ）、この処理を終了する。
【００４１】
一方、点（Ｘ，Ｙ）にラベルが付いている場合は（Ｓ３２：ＹＥＳ）、中点を求めたい点ＰiおよびＰjのＸＹ座標を（Ｘi，Ｙi），（Ｘj，Ｙj）として（Ｓ３７）、Ｘjの値を１増やし（Ｓ３８）、Ｘ座標の右端か否かを調べ（Ｓ３９）、右端に達しない間は（Ｓ３９：ＮＯ）、点Ｐjにラベルが付いているか否かを調べる（Ｓ４０）。右端に達したときは、Ｓ３３へ進む。点Ｐjにラベルが付いていれば（Ｓ４０：ＹＥＳ）、ＰiとＰjとに同一のラベルが付いているか否かを調べ（Ｓ４１）、ＰiとＰjとに同一のラベルが付いていれば（Ｓ４１：ＹＥＳ）、中点Ｃij（ＣX，ＣY）＝（(Ｘi＋Ｙi)/２，(Ｘj＋Ｙj)/２）を計算し（Ｓ４２）、点Ｐiと中点Ｃijとに同一のラベルが付いているか否かを調べる（Ｓ４３）。そして、点Ｐiと中点Ｃijとに異なるラベルが付いている場合に限り（Ｓ４３：ＮＯ）、中点Ｃijを中点画面にプロットし（Ｓ４４）、点Ｐiと中点Ｃijとに同一のラベルが付いている場合はＳ３８へ戻る。
【００４２】
（ホ）円抽出装置１０
円抽出装置１０は、入力線画に対し、水平、垂直の両方向からの走査によってそれぞれ作成した２枚の中点図面の論理和を求め、テンプレートマッチングを適用して円ないし楕円の中心座標を出力する装置である。
【００４３】
図１２は、円抽出装置１０の構成を示すブロック図で、線画入力部２１と、中点図面作成部２２と、論理合成部２３と、テンプレートマッチング部２４と、結果出力部２５とによって構成されている。また、図１３のＳ５１〜Ｓ５６は円抽出装置１０における処理手順を示すフロ−チャ−ト、図１４（ａ）〜（ｅ）は処理手順の説明図である。
【００４４】
中点図面作成部２２では、図１４（ａ）に示すような入力線画を水平方向に走査して、図１４（ｂ）に示すような中点図面を作成する（Ｓ５２）。このとき、入力線画に付されているラベルが同一の２点から中点を得る。同様に、入力線画を垂直方向に走査して、図１４（ｃ）に示すような中点図面を作成する（Ｓ５３）。
【００４５】
論理合成部２３では、入力線画を水平方向に走査して得られた中点図面と、入力線画を垂直方向に走査して得られた中点図面との論理和を求め、図１４（ｄ）に示すような新たな１つの中点図面を得る（Ｓ５４）。この中点図面では、円パタンは十字形パタンに変換されている。
【００４６】
テンプレートマッチング部２４では、テンプレートとして、図１５に示すような５×５のパタンを用いる。そして、このテンプレートを全画面上を走査させながら相関値を計算する。テンプレートが十字の交点の位置にあるとき相関値が最大となり、この点が円の中心となる。
【００４７】
結果出力部２５は、円の中心座標を出力する。
【００４８】
このような円抽出装置１０を用いることにより、画面中から直接、円ないし楕円の中心を発見することができ、またハフ変換を用いる従来の方法に比較して、処理速度を著しく速めることが可能になる。
【００４９】
以上の説明により、本発明による円ないし楕円の検出方法およびその装置の１実施例が明らかとなったが、図１にブロックで示されている各構成要素ならびに図２に示されている各ステップは、入力画像の性質に応じて適宜一部を省略しても本発明の目的を達成できることは言うまでもない。
【図面の簡単な説明】
【図１】  本発明による円ないし楕円の検出装置の１実施例の構成を示すブロック図
【図２】  図１の装置における処理手順を示すフロ−チャ−ト
【図３】  同  グルーピング装置の作用の説明図
【図４】  同  直線除去装置の作用の説明図
【図５】  同  直線除去装置の構成を示すブロック図
【図６】  図５の装置における処理手順を示すフロ−チャ−ト
【図７】  図１の装置におけるマスク画像生成部の作用の説明図
【図８】  同  直線除去部の作用の説明図
【図９】  同  ラベル付け装置の作用の説明図
【図１０】  同  他のラベル付け装置の作用の説明図
【図１１】  同  他のラベル付け装置における処理手順を示すフロ−チャ−ト
【図１２】  同  円抽出装置の構成を示すブロック図
【図１３】  図１２の装置における処理手順を示すフロ−チャ−ト
【図１４】  同  円抽出装置の作用の説明図
【図１５】  同  円抽出装置で用いられるテンプレートパタンを示す図
【図１６】  従来の円ないし楕円の検出方法の一例における処理の流れを示すフロ−チャ−ト
【図１７】  同  中点図面の作成方法を示す説明図
【図１８】  従来の方法の問題点の説明図
【図１９】  従来の方法の問題点の説明図
【符号の説明】
６      グルーピング装置
７      細線化処理部
８      直線除去装置
９      ラベル付け装置
１０    円抽出装置
１２    マスク画像生成部
２２    中点図面作成部
２３    論理合成部
２４    テンプレートマッチング部
【図１】
0003694911.tif 000003
【図２】
0003694911.tif 000004
【図３】
0003694911.tif 000005
【図４】
0003694911.tif 000006
【図５】
0003694911.tif 000007
【図６】
0003694911.tif 000008
【図７】
0003694911.tif 000009
【図８】
0003694911.tif 000010
【図９】
0003694911.tif 000011
【図１０】
0003694911.tif 000012
【図１１】
0003694911.tif 000013
【図１２】
0003694911.tif 000014
【図１３】
0003694911.tif 000015
【図１４】
0003694911.tif 000016
【図１５】
0003694911.tif 000017
【図１６】
0003694911.tif 000018
【図１７】
0003694911.tif 000019
【図１８】
0003694911.tif 000020
【図１９】
0003694911.tif 000021