JPH08201039A

JPH08201039A - 円ないし楕円の検出方法およびその装置

Info

Publication number: JPH08201039A
Application number: JP809095A
Authority: JP
Inventors: Masafumi Yamamoto; 雅史山本; Atsushi Kutami; 篤久田見; Masanori Kobayashi; 正典小林; Hiroyuki Yoshida; 博行吉田; Hiroyuki Takahashi; 弘行高橋
Original assignee: Mazda Motor Corp
Current assignee: Mazda Motor Corp
Priority date: 1995-01-23
Filing date: 1995-01-23
Publication date: 1996-08-09
Anticipated expiration: 2020-09-14
Also published as: JP3694911B2

Abstract

(57)【要約】【目的】入力画像を細線化して得られる入力線画を１
方向に走査して該入力線画と各走査線との交点の座標を
求め、次いで同一走査線上の交点間の中点の座標を各走
査線について求めて上記中点が描く図形からなる中点図
面を作成し、該中点図面から線分を抽出する場合に、不
必要な中点の算出の阻止等によって処理時間の短縮と処
理の信頼性の向上を図る。【構成】入力線画の走査を２方向について行なって、
各方向の各走査線と上記入力線画との交点の座標から第
１および第２の中点図面をそれぞれ作成し、次いで該第
１および第２の中点図面を合成して、両中点図面の論理
和を表す第３の中点図面を作成し、該第３の中点図面に
対してテンプレートマッチングを行なって、上記第３の
中点図面における上記２つの線分の交点座標を求め、該
交点座標を上記円または楕円の中心座標とする。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、入力画像から円ないし
楕円を検出する方法およびその装置に関する。

【０００２】

【従来の技術】従来より、入力画像を処理して、入力画
像の中から円ないし楕円パタンを検出する方法として、
パタン境界と走査線との交点の中点を利用する技術が知
られている（特開平５−１０７０３０号公報参照）。

【０００３】図１６は、このような従来の円ないし楕円
の検出方法の一例における処理の流れを示すフロ−チャ
−トであり、ステップＳ１〜Ｓ８の工程からなる。

【０００４】（１）画像入力〜細線化（Ｓ１〜Ｓ４）入力画像に微分フィルタを適用してエッジ画像を得、こ
のエッジ画像に対して、２値化および細線化処理を施
し、線幅が１の線画を得る。

【０００５】（２）中点画像の作成（Ｓ５）入力画像に図１７（ａ）に示すような座標系を設定し、
入力線画を水平方向（ｘ方向）に走査して、入力線画と
各走査線との交点の座標を求める。

【０００６】すなわち、図１７（ｂ）に示すように、走
査線ｙ＝ｋと入力線画Ａ，Ｂとの交点をｘ₁，ｘ₂，
…，ｘ_nとし、この中の２つの交点［ｘ_i，ｘ_j］の中
点の座標をＣ_ij（( ｘ_i＋ｘ_j)/２，ｋ）、２点間の距
離をｄ_ij＝｜ｘ_i−ｘ_j｜とする。そして、全ての交点
の組合わせについて中点の座標と距離とを求め、それを
中点図面の（( ｘ_i＋ｘ_j)/２，ｋ）の位置に重みｄ_ij
としてプロットする。この処理をｙ＝０からｙ＝Ｙ_MAX
まで繰り返し、図１７（ｃ）に示すような中点図面を得
る。

【０００７】中点図面では、円ないし楕円は直線に変換
され、同時に、平行線および長方形等も直線に変換され
る。

【０００８】（３）円ないし楕円の検出（Ｓ６）中点図面中の線分を抽出することにより、円ないし楕円
を検出する。線分の検出はハフ（Hough ）変換法を用い
る。この場合、上記重みを参照することにより、円ない
し楕円と長方形との区別が可能になる。すなわち、長方
形の場合、重みは線分に沿って一定の値を示すが、円な
いし楕円の場合、重みは線分の両端で最小値を、線分の
中央付近で最大値をとる。

【０００９】（４）円ないし楕円のパラメータ推定（Ｓ
７）検出した線分と重みとから円ないし楕円のパラメータ
（中心座標、半径、軸の傾き）を推定する。検出された
線分を構成する中点について、この中点から所定距離だ
け離れた位置にウインドウを設け、このウインドウない
に存在する点を候補点とする。そして、これら候補点に
対して最小二乗法を適用することにより、円ないし楕円
のパラメータを決定する。

【００１０】

【発明が解決しようとする課題】ところで、上述した従
来の円ないし楕円の検出方法には下記に示すような種々
の問題点が存在する。

【００１１】（イ）従来方法では、中点検出は原画像中
で所定のしきい値よりも大きな値を持つ点である特徴点
の全てについて中点を作成していた。しかしながら、例
えば図１７（ｂ）に示すように、全ての点に対して中点
を作成すると、図１７（ｃ）に示すように、作成する中
点の数が画像中の特徴点の数の二乗のオーダーで増加す
るため、莫大な演算時間を必要とし、計算コストが増大
するする。

【００１２】（ロ）図１８（ａ）および図１９（ａ）に
示すように、画像を微分して２値化かつ細線化した入力
線画にノイズが含まれていると、図１８（ｂ）および図
１９（ｂ）に示すように不必要な中点が抽出されるた
め、処理時間の増大や検出精度および信頼性の低下を招
く。

【００１３】例えば、図１９（ａ）に示す入力線画の円
に対する中点画像は、図１９（ｂ）に示すように線分と
して検出できるが、入力線画に含まれている直線状のノ
イズは、余分な楕円として抽出されることになる。

【００１４】（ハ）線分の検出に用いられるハフ変換処
理は、莫大な演算時間を要するため、これによっても計
算コストが増大する。

【００１５】そこで、本発明は、入力画像を細線化して
得られる入力線画を１方向に走査して該入力線画と各走
査線との交点の座標を求め、次いで同一走査線上の交点
間の中点の座標を各走査線について求めて上記中点が描
く図形からなる中点図面を作成し、該中点図面から線分
を抽出する場合に、不必要な中点の算出の阻止等によっ
て処理時間の短縮と処理の信頼性の向上を図った円ない
し楕円を検出する方法およびその装置を提供することを
目的とする。

【００１６】

【課題を解決するための手段】本発明による円ないし楕
円の検出方法は、請求項１に記載されているように、上
記入力線画の存在する領域を、該線画の近傍に存在する
ノイズ領域をも含むように拡張してグルーピングし、該
グルーピングされた画像を細線化し、該細線化された画
像について、上記走査線との交点を求める処理を行なう
ことを特徴とする。

【００１７】また、本発明による円ないし楕円の検出方
法は、請求項２に記載されているように、上記入力線画
と走査線との交点の座標を求める処理に先立って、上記
入力線画から直線を除去する処理を行なうことを特徴と
する。

【００１８】この直線を除去する処理に際しては、請求
項３に記載されているように、上記入力線画から直線成
分を抽出して該直線をマスクするマスク画像を生成し、
該マスク画像と上記入力線画との論理積を求めることが
好ましい。

【００１９】さらに、本発明による円ないし楕円の検出
方法は、請求項４に記載されているように、上記入力線
画と走査線との交点の座標を求める処理に先立って、上
記入力線画に対しラベル付けを行ない、同一ラベルの付
された２点間の中点が描く図形からなる中点図面から線
分を抽出することを特徴とする。

【００２０】その場合に、請求項５に記載されているよ
うに、上記中点のラベルを調べ、上記同一ラベルの付さ
れた２点に対して異なるラベルが付されている中点のみ
から上記中点図面を作成することが好ましい。

【００２１】さらに、本発明による円ないし楕円の検出
方法は、請求項６に記載されているように、入力線画の
走査を２方向について行なって、各方向の各走査線と上
記入力線画との交点の座標から第１および第２の中点図
面をそれぞれ作成し、次いで該第１および第２の中点図
面を合成して、両中点図面の論理和を表す第３の中点図
面を作成し、該第３の中点図面に対してテンプレートマ
ッチングを行なって、上記第３の中点図面における上記
２つの線分の交点座標を求め、該交点座標を上記円また
は楕円の中心座標とすることを特徴とするその場合に、
請求項７に記載されているように、上記走査線の走査方
向を水平方向および垂直方向とし、上記第３の中点図面
を十字形パターンを有するものとすることが好ましい。

【００２２】さらに、本発明による円ないし楕円の検出
方法は、請求項８に記載されているように、請求項６ま
たは７に記載の方法に加えて、上記入力線画の存在する
領域を、該線画の近傍に存在するノイズ領域をも含むよ
うに拡張してグルーピングし、該グルーピングされた画
像を細線化し、該細線化された画像について、上記走査
線との交点の座標を求める処理を行なうことを特徴とす
る。

【００２３】さらに、本発明による円ないし楕円の検出
方法は、請求項９に記載されているように、請求項６ま
たは７に記載の方法に加えて、上記入力線画と走査線と
の交点の座標を求める処理に先立って、上記入力線画か
ら直線を除去する処理を行なうことを特徴とする。

【００２４】上記直線を除去する処理に際しては、請求
項１０に記載されているように、上記入力線画から直線
成分を抽出して該直線をマスクするマスク画像を生成
し、該マスク画像と上記入力線画との論理積を求めるこ
とが好ましい。

【００２５】さらに、本発明による円ないし楕円の検出
方法は、請求項１１に記載されているように、請求項６
ないし１０に記載の方法の１つに加えて、上記入力線画
と走査線との交点の座標を求める処理に先立って、上記
入力線画に対しラベル付けを行ない、同一ラベルの付さ
れた２点間の中点が描く図形からなる中点図面から線分
を抽出することを特徴とする。

【００２６】その場合に、請求項１２に記載されている
ように、上記中点のラベルを調べ、上記同一ラベルの付
された２点に対して異なるラベルを付されている中点の
みから、上記中点図面を作成することが好ましい。

【００２７】本発明による円ないし楕円の検出装置は、
請求項１３に記載されているように、上記入力線画の存
在する領域を、該線画の近傍に存在するノイズ領域をも
含むように拡張してグルーピングするグルーピング手段
と、該グルーピングされた画像を細線化する細線化処理
手段とを備えていることを特徴とする。

【００２８】また、本発明による円ないし楕円の検出装
置は、請求項１４に記載されているように、上記入力線
画から直線を除去する直線除去手段を備えていることを
特徴とする。

【００２９】上記直線除去手段は、請求項１５に記載さ
れているように、上記入力線画から直線成分を抽出して
該直線をマスクするマスク画像を生成し、かつ該マスク
画像と上記入力線画との論理積を求める手段よりなるこ
とが好ましい。

【００３０】さらに、本発明による円ないし楕円の検出
装置は、請求項１６に記載されているように、上記入力
線画に対しラベル付けを行なうラベル付け手段と、同一
ラベルの付された２点間の中点が描く図形からなる中点
図面を作成する中点図面作成手段とを備えていることを
特徴とする。

【００３１】上記中点図面作成手段は、請求項１７に記
載されているように、上記同一ラベルの付された２点に
対して異なるラベルを付されている中点のみから上記中
点図面を作成する手段よりなることが好ましい。

【００３２】さらに、本発明による円ないし楕円の検出
装置は、請求項１８に記載されているように、入力線画
の走査を２方向について行なって、各方向の各走査線と
上記入力線画との交点の座標から第１および第２の中点
図面をそれぞれ作成する中点図面作成手段と、該第１お
よび第２の中点図面を合成して、両中点図面の論理和を
表す第３の中点図面を作成する論理合成手段と、該第３
の中点図面に対してテンプレートマッチングを行なっ
て、上記第３の中点図面における上記２つの線分の交点
座標を求めるテンプレートマッチング手段とを備えてい
ることを特徴とする。

【００３３】その場合に、請求項１９に記載されている
ように、上記中点図面作成手段における上記走査線の走
査方向が水平方向および垂直方向よりなり、上記論理合
成手段により作成される上記第３の中点図面が十字形パ
ターンを有することが好ましい。

【００３４】さらに、本発明による円ないし楕円の検出
装置は、請求項２０に記載されているように、請求項１
８または１９に記載の構成に加えて、上記入力線画の存
在する領域を、該線画の近傍に存在するノイズ領域をも
含むように拡張してグルーピングするグルーピング手段
装置と、該グルーピングされた画像を細線化する細線化
処理手段とを備えていることを特徴とする。

【００３５】さらに、本発明による円ないし楕円の検出
装置は、請求項２１に記載されているように、請求項１
８または１９に記載の構成に加えて、上記入力線画から
直線を除去する処理を行なう直線除去手段を備えている
ことを特徴とする。

【００３６】上記直線除去手段は、請求項２２に記載さ
れているように、上記入力線画から直線成分を抽出して
該直線をマスクするマスク画像を生成し、かつ該マスク
画像と上記入力線画との論理積を求める手段よりなるこ
とが好ましい。

【００３７】さらに、本発明による円ないし楕円の検出
装置は、請求項２３に記載されているように、請求項１
８ないし２２の１つに記載の構成に加えて、上記入力線
画に対しラベル付けを行なうラベル付け手段と、同一ラ
ベルの付された２点間の中点が描く図形からなる中点図
面を作成する中点図面作成手段とを備えていることを特
徴とする。

【００３８】上記中点図面作成手段は、請求項２４に記
載されているように、上記同一ラベルの付された２点に
対して異なるラベルを付されている中点のみから上記中
点図面を作成する手段よりなることが好ましい。

【００３９】

【作用および発明の効果】請求項１および１３に記載さ
れた発明によれば、入力画像中の領域を拡張して実領域
とノイズ領域をグルーピングし、グルーピングされた画
像を細線化していることにより、ノイズ成分が除去され
るから、不必要な中点の抽出が防止され、処理時間の短
縮や、円ないし楕円の検出精度の向上および信頼性の向
上を図ることができる。

【００４０】また、請求項２および１４に記載された発
明によれば、入力線画と走査線との交点座標を求める処
理に先立って、入力線画から予め直線成分を除去してい
るから、長方形や平行線から生成される不必要な中点の
算出が防止され、処理の高速化および信頼性の向上を図
ることができる。

【００４１】さらに、請求項４および１６に記載された
発明によれば、同一ラベルの付された２点のみから中点
を求めていることにより、異なる２つの図形からの中点
生成や、ノイズにからの中点生成を防止することがで
き、これによって、円ないし楕円の検出精度の向上、誤
検出の防止、処理時間の短縮等を図ることができる。

【００４２】特に、請求項５および１７に記載されてい
るように、同一ラベルの付された２点に対して異なるラ
ベルを付されている中点のみから上記中点図面を作成す
ることにより、走査線に平行な線上に中点が無数に並ん
だ中点図形が生成されることが防止され、さらに円ない
し楕円の検出精度の向上、誤検出の防止、処理時間の短
縮等の効果を助長することができる。

【００４３】さらに、請求項６および１８に記載された
発明によれば、入力線画を２つの方向から走査した得ら
れた２枚の中点図面の論理和を求めて１つの新たな中点
図面を得、この新たな中点図面についてテンプレートマ
ッチングを行なっているから、入力線画から直接円ない
し楕円の中心を発見でき、従来のハフ変換を用いる場合
に比較して、処理速度を飛躍的に速めることが可能にな
る。

【００４４】

【実施例】以下、図面を参照して本発明の実施例につい
て説明する。

【００４５】図１は、本発明による円ないし楕円を検出
する装置の１実施例置の構成を示すブロック図で、図２
は、本装置における処理手順を示すフロ−チャ−トであ
る。図２のＳ１１〜Ｓ１９は各工程を示す。

【００４６】図１の装置は、画像を入力する（Ｓ１１）
撮像部１と、撮像部１からのアナログ信号をデジタル信
号へ変換するＡ／Ｄ変換部２と、デジタル画像データを
格納する画像メモリ３と、画像メモリ３に格納されてい
る画像の微分画像を得る（Ｓ１２）微分処理部４と、微
分画像を２値化する（Ｓ１３）２値化処理部５と、画像
の領域を拡張する（Ｓ１４）グルーピング装置６と、画
像を細線化する（Ｓ１５）細線化処理部７と、細線化さ
れた画像から直線を除去する（Ｓ１６）直線除去装置８
と、画像にラベルを付ける（Ｓ１７）ラベル付け装置９
と、円ないし楕円を抽出し（Ｓ１８）、該円ないし楕円
の中心座標を出力する（Ｓ１９）円抽出装置１０とによ
って構成されている。

【００４７】次に、各装置の機能について説明する。

【００４８】（イ）グルーピング装置６および細線化処
理部７このグルーピング装置６は、画像を微分して２値化した
入力画像に図１８（ａ）に示すようにノイズが含まれて
いると、図１８（ｂ）に示すように不必要な中点が抽出
されて複雑な中点図面が生成されるのを防止するために
設けられるもので、図３（ａ）に示すような入力画像中
の領域を拡張して、図３（ｂ）に示すように、実画像領
域とこれに隣接するノイズ領域とをグルーピングする。
そして、このグルーピングされた画像に対して細線化処
理部７で細線化を行なうことにより、図３（ｂ）に示す
ようにノイズの除去された細線化画像を得、この細線化
画像から図３（ｄ）に示すような中点図面を得るもので
ある。したがって、処理時間の短縮、精度および信頼性
の向上を図ることができる。

【００４９】（ロ）直線除去装置８直線除去装置８は、入力線画に図１７（ｂ）の右方に示
すような直線成分が含まれていると、図１７（ｃ）に示
すように不必要な中点が抽出されるのを防止するため
に、図４（ａ）に示すような入力線画から、図４（ｂ）
に示すように直線成分を除去して、図４（ｃ）に示すよ
うな中点図面を得るために設けられるものである。この
直線除去装置８を設けることによって、処理の高速化お
よび信頼性の向上を図ることができる。

【００５０】図５は、直線除去装置８の構成を示すブロ
ック図で、図６のＳ２１〜Ｓ２５は本装置における処理
手順を示すフロ−チャ−トである。直線除去装置８は、
線画入力部１１と、マスク画像生成部１２と、直線除去
部１３とによって構成されている。

【００５１】マスク画像生成部１２では、図７（ａ）に
示すような入力線画から、図７（ｂ）に示すように直線
成分を抽出し、この抽出した直線領域を拡張して、図７
（ｃ）に示すような直線をマスクする直線マスク画像を
生成する。そしてマスク部を０、それ以外の部分を１と
する。

【００５２】上記直線成分の抽出方法の１例として、例
えば直線成分が水平成分と垂直成分とからなる場合、微
分画像を水平方向および垂直方向に走査して、同一垂直
線上の微分値および同一水平線上の微分値をそれぞれ加
算すれば、直線成分の位置で大きな加算値が得られるこ
とによって、直線成分を抽出することができる。

【００５３】直線除去部１３では、図８（ａ）に示すよ
うな入力線画から、図８（ｂ）に示すようなマスク画像
のマスク部を除去して、図８（ｃ）に示すような直線除
去画像を作成する。具体的には、入力線画とマスク画像
との論理積を求めると、直線除去画像が得られる。ただ
し、入力線画中で線部を１、それ以外の部分を０とする
（表１参照）。

【００５４】

【表１】

【００５５】（ハ）ラベル付け装置９（１）ラベル付け装置９は、例えば図１９（ａ）に示す入力線
画の円に対する中点画像は、図１９（ｂ）に示すように
線分として検出できるが、入力線画に含まれている直線
状のノイズは、余分な楕円として抽出されることになる
のを防止するために、中点検出に先立って、入力線画中
の個々の連結成分に対して異なった名前のラベルを割り
当てる（ラベリング）装置である。

【００５６】例えば、図９（ａ）に示す入力線画では２
つの連結成分が存在しているために、各連結成分に対し
て１と２のラベルが付けられる。そして、同一のラベル
の付された連結成分毎に中点を検出するようにすれば、
図９（ｂ）に示すように、不要な中点を検出しなくても
良くなる。

【００５７】このように、同一のラベルの付された２点
のみから中点を求めることにより、ことなる２つの図形
から生成される中点や、ノイズにより生成される中点を
なくすことができ、これによって、円ないし楕円の検出
精度の向上、誤検出の防止および処理時間の短縮等を図
ることができる。

【００５８】（ニ）ラベル付け装置９（２）例えば、図１０（ａ）に示すように、入力線画が、各２
本の水平線（走査線と同一方向）および垂直線で構成さ
れた長方形を含み、上記（ハ）のラベル付け装置９
（１）において、この長方形に対しては同一のラベルを
付して、中点を検出するようにした場合、図１０（ｂ）
に示すように、垂直に並ぶ中点列の上下に、走査線と同
一線上に無数に並ぶ中点によって２本の水平線が作成さ
れて工字状を呈することになる。

【００５９】そこで、ラベル付け装置９（２）において
は、中点を求めたい同一ラベルの２点Ｐ_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とに同一のラベルが付いている
場合はＳ３８へ戻る。

【００６２】（ホ）円抽出装置１０円抽出装置１０は、入力線画に対し、水平、垂直の両方
向からの走査によってそれぞれ作成した２枚の中点図面
の論理和を求め、テンプレートマッチングを適用して円
ないし楕円の中心座標を出力する装置である。

【００６３】図１２は、円抽出装置１０の構成を示すブ
ロック図で、線画入力部２１と、中点図面作成部２２
と、論理合成部２３と、テンプレートマッチング部２４
と、結果出力部２５とによって構成されている。また、
図１３のＳ５１〜Ｓ５６は円抽出装置１０における処理
手順を示すフロ−チャ−ト、図１４（ａ）〜（ｅ）は処
理手順の説明図である。

【００６４】中点図面作成部２２では、図１４（ａ）に
示すような入力線画を水平方向に走査して、図１４
（ｂ）に示すような中点図面を作成する（Ｓ５２）。こ
のとき、入力線画に付されているラベルが同一の２点か
ら中点を得る。同様に、入力線画を垂直方向に走査し
て、図１４（ｃ）に示すような中点図面を作成する（Ｓ
５３）。

【００６５】論理合成部２３では、入力線画を水平方向
に走査して得られた中点図面と、入力線画を垂直方向に
走査して得られた中点図面との論理和を求め、図１４
（ｄ）に示すような新たな１つの中点図面を得る（Ｓ５
４）。この中点図面では、円パタンは十字形パタンに変
換されている。

【００６６】テンプレートマッチング部２４では、テン
プレートとして、図１５に示すような５×５のパタンを
用いる。そして、このテンプレートを全画面上を走査さ
せながら相関値を計算する。テンプレートが十字の交点
の位置にあるとき相関値が最大となり、この点が円の中
心となる。

【００６７】結果出力部２５は、円の中心座標を出力す
る。

【００６８】このような円抽出装置１０を用いることに
より、画面中から直接円ないし楕円の中心を発見するこ
とができ、またハフ変換を用いる従来の方法に比較し
て、処理速度を著しく速めることが可能になる。

【００６９】以上の説明により、本発明による円ないし
楕円の検出方法およびその装置の１実施例が明らかとな
ったが、図１にブロックで示されている各構成要素なら
びに図２に示されている各ステップは、入力画像の性質
に応じて適宜一部を省略しても本発明の目的を達成でき
ることは言うまでもない。

【図面の簡単な説明】

【図１】本発明による円ないし楕円の検出装置の１実施
例置の構成を示すブロック図

【図２】図１の装置における処理手順を示すフロ−チャ
−ト

【図３】同グルーピング装置の作用の説明図

【図４】同直線除去装置の作用の説明図

【図５】同直線除去装置の構成を示すブロック図

【図６】図５の装置における処理手順を示すフロ−チャ
−ト

【図７】図１の装置におけるマスク画像生成部の作用の
説明図

【図８】同直線除去部の作用の説明図

【図９】同ラベル付け装置の作用の説明図

【図１０】同他のラベル付け装置の作用の説明図

【図１１】同他のラベル付け装置における処理手順を
示すフロ−チャ−ト

【図１２】同円抽出装置の構成を示すブロック図

【図１３】図１２の装置における処理手順を示すフロ−
チャ−ト

【図１４】同円抽出装置の作用の説明図

【図１５】同円抽出装置で用いられるテンプレートパ
タンを示す図

【図１６】従来の円ないし楕円の検出方法の一例におけ
る処理の流れを示すフロ−チャ−ト

【図１７】同中点図面の作成方法を示す説明図

【図１８】従来の方法の問題点の説明図

【図１９】従来の方法の問題点の説明図

【符号の説明】

６グルーピング装置７細線化処理部８直線除去装置９ラベル付け装置１０円抽出装置１２マスク画像生成部２２中点図面作成部２３論理合成部２４テンプレートマッチング部

フロントページの続き (72)発明者吉田博行広島県安芸郡府中町新地３番１号マツダ株式会社内 (72)発明者高橋弘行広島県安芸郡府中町新地３番１号マツダ株式会社内

Claims

【特許請求の範囲】

【請求項１】入力画像を細線化して得られる入力線画
を１方向に走査して該入力線画と各走査線との交点の座
標を求め、次いで同一走査線上の交点間の中点の座標を
各走査線について求めて上記中点が描く図形からなる中
点図面を作成し、該中点図面から線分を抽出することに
より、円ないし楕円を検出する方法において、上記入力線画の存在する領域を、該線画の近傍に存在す
るノイズ領域をも含むように拡張してグルーピングし、
該グルーピングされた画像を細線化し、該細線化された
画像について、上記走査線との交点の座標を求める処理
を行なうことを特徴とする円ないし楕円の検出方法。
【請求項２】入力画像を細線化して得られる入力線画
を１方向に走査して該入力線画と各走査線との交点の座
標を求め、次いで同一走査線上の交点間の中点の座標を
各走査線について求めて上記中点が描く図形からなる中
点図面を作成し、該中点図面から線分を抽出することに
より、円ないし楕円を検出する方法において、上記入力線画と走査線との交点の座標を求める処理に先
立って、上記入力線画から直線を除去する処理を行なう
ことを特徴とする円または楕円の検出方法。
【請求項３】上記直線を除去する処理が、上記入力線
画から直線成分を抽出して該直線をマスクするマスク画
像を生成し、該マスク画像と上記入力線画との論理積を
求めることよりなることを特徴とする請求項２に記載の
円ないし楕円の検出方法。
【請求項４】入力画像を細線化して得られる入力線画
を１方向に走査して該入力線画と各走査線との交点の座
標を求め、次いで同一走査線上の交点間の中点の座標を
各走査線について求めて上記中点が描く図形からなる中
点図面を作成し、該中点図面から線分を抽出することに
より、円ないし楕円を検出する方法において、上記入力線画と走査線との交点の座標を求める処理に先
立って、上記入力線画に対しラベル付けを行ない、同一
ラベルの付された２点間の中点が描く図形からなる中点
図面から線分を抽出することを特徴とする円ないし楕円
の検出方法。
【請求項５】上記中点のラベルを調べ、上記同一ラベ
ルの付された２点に対して異なるラベルが付されている
中点のみから上記中点図面を作成することを特徴とする
請求項４に記載の円ないし楕円の検出方法。
【請求項６】入力画像を細線化して得られる入力線画
を１方向に走査して該入力線画と各走査線との交点の座
標を求め、次いで同一走査線上の交点間の中点の座標を
各走査線について求めて上記中点が描く図形からなる中
点図面を作成し、該中点図面から線分を抽出することに
より、円ないし楕円を検出する方法において、入力線画の走査を２方向について行なって、各方向の各
走査線と上記入力線画との交点の座標から第１および第
２の中点図面をそれぞれ作成し、次いで該第１および第
２の中点図面を合成して、両中点図面の論理和を表す第
３の中点図面を作成し、該第３の中点図面に対してテン
プレートマッチングを行なって、上記第３の中点図面に
おける上記２つの線分の交点座標を求め、該交点座標を
上記円または楕円の中心座標とすることを特徴とする円
ないし楕円の検出方法。
【請求項７】上記走査線の走査方向が水平方向および
垂直方向よりなり、上記第３の中点図面が十字形パター
ンを有することを特徴とする請求項６に記載の円ないし
楕円の検出方法。
【請求項８】上記入力線画の存在する領域を、該線画
の近傍に存在するノイズ領域をも含むように拡張してグ
ルーピングし、該グルーピングされた画像を細線化し、
該細線化された画像について、上記走査線との交点の座
標を求める処理を行なうことを特徴とする請求項６また
は７に記載の円ないし楕円の検出方法。
【請求項９】上記入力線画と走査線との交点の座標を
求める処理に先立って、上記入力線画から直線を除去す
る処理を行なうことを特徴とする請求項６または７に記
載の円ないし楕円の検出方法。
【請求項１０】上記直線を除去する処理が、上記入力
線画から直線成分を抽出して該直線をマスクするマスク
画像を生成し、該マスク画像と上記入力線画との論理積
を求めることよりなることを特徴とする請求項９に記載
の円ないし楕円の検出方法。
【請求項１１】上記入力線画と走査線との交点の座標
を求める処理に先立って、上記入力線画に対しラベル付
けを行ない、同一ラベルの付された２点間の中点が描く
図形からなる中点図面から線分を抽出することを特徴と
する請求項６ないし１０の１つに記載の円ないし楕円の
検出方法。
【請求項１２】上記中点のラベルを調べ、上記同一ラ
ベルの付された２点に対して異なるラベルを付されてい
る中点のみから、上記中点図面を作成することを特徴と
する請求項１１に記載の円ないし楕円の検出方法。
【請求項１３】入力画像を細線化して得られる入力線
画を１方向に走査して該入力線画と各走査線との交点の
座標を求め、次いで同一走査線上の交点間の中点の座標
を各走査線について求めて上記中点が描く図形からなる
中点図面を作成し、該中点図面から線分を抽出すること
により、円ないし楕円を検出する装置において、上記入力線画の存在する領域を、該線画の近傍に存在す
るノイズ領域をも含むように拡張してグルーピングする
グルーピング手段と、該グルーピングされた画像を細線
化する細線化処理手段とを備えていることを特徴とする
円ないし楕円の検出装置。
【請求項１４】入力画像を細線化して得られる入力線
画を１方向に走査して該入力線画と各走査線との交点の
座標を求め、次いで同一走査線上の交点間の中点の座標
を各走査線について求めて上記中点が描く図形からなる
中点図面を作成し、該中点図面から線分を抽出すること
により、円ないし楕円を検出する装置において、上記入力線画から直線を除去する直線除去手段を備えて
いることを特徴とする円または楕円の検出装置。
【請求項１５】上記直線除去手段が、上記入力線画か
ら直線成分を抽出して該直線をマスクするマスク画像を
生成し、かつ該マスク画像と上記入力線画との論理積を
求める手段よりなることを特徴とする請求項１４に記載
の円ないし楕円の検出装置。
【請求項１６】入力画像を細線化して得られる入力線
画を１方向に走査して該入力線画と各走査線との交点の
座標を求め、次いで同一走査線上の交点間の中点の座標
を各走査線について求めて上記中点が描く図形からなる
中点図面を作成し、該中点図面から線分を抽出すること
により、円ないし楕円を検出する装置において、上記入力線画に対しラベル付けを行なうラベル付け手段
と、同一ラベルの付された２点間の中点が描く図形から
なる中点図面を作成する中点図面作成手段とを備えてい
ることを特徴とする円ないし楕円の検出装置。
【請求項１７】上記中点図面作成手段が、上記同一ラ
ベルの付された２点に対して異なるラベルを付されてい
る中点のみから上記中点図面を作成する手段よりなるこ
とを特徴とする請求項１６に記載の円ないし楕円の検出
装置。
【請求項１８】入力画像を細線化して得られる入力線
画を１方向に走査して該入力線画と各走査線との交点の
座標を求め、次いで同一走査線上の交点間の中点の座標
を各走査線について求めて上記中点が描く図形からなる
中点図面を作成し、該中点図面から線分を抽出すること
により、円ないし楕円を検出する装置において、入力線画の走査を２方向について行なって、各方向の各
走査線と上記入力線画との交点の座標から第１および第
２の中点図面をそれぞれ作成する中点図面作成手段と、
該第１および第２の中点図面を合成して、両中点図面の
論理和を表す第３の中点図面を作成する論理合成手段
と、該第３の中点図面に対してテンプレートマッチング
を行なって、上記第３の中点図面における上記２つの線
分の交点座標を求めるテンプレートマッチング手段とを
備えていることを特徴とする円ないし楕円の検出装置。
【請求項１９】上記中点図面作成手段における上記走
査線の走査方向が水平方向および垂直方向よりなり、上
記論理合成手段により作成される上記第３の中点図面が
十字形パターンを有することを特徴とする請求項１８に
記載の円ないし楕円の検出装置。
【請求項２０】上記入力線画の存在する領域を、該線
画の近傍に存在するノイズ領域をも含むように拡張して
グルーピングするグルーピング手段装置と、該グルーピ
ングされた画像を細線化する細線化処理手段とを備えて
いることを特徴とする請求項１８または１９に記載の円
ないし楕円の検出装置。
【請求項２１】上記入力線画から直線を除去する処理
を行なう直線除去手段を備えていることを特徴とする請
求項１８または１９に記載の円ないし楕円の検出装置。
【請求項２２】上記直線除去手段が、上記入力線画か
ら直線成分を抽出して該直線をマスクするマスク画像を
生成し、かつ該マスク画像と上記入力線画との論理積を
求める手段よりなることを特徴とする請求項２１に記載
の円ないし楕円の検出装置。
【請求項２３】上記入力線画に対しラベル付けを行な
うラベル付け手段と、同一ラベルの付された２点間の中
点が描く図形からなる中点図面を作成する中点図面作成
手段とを備えていることを特徴とする請求項１８ないし
２２の１つに記載の円ないし楕円の検出装置。
【請求項２４】上記中点図面作成手段が、上記同一ラ
ベルの付された２点に対して異なるラベルを付されてい
る中点のみから上記中点図面を作成する手段よりなるこ
とを特徴とする請求項２３に記載の円ないし楕円の検出
装置。