JPH07320060A - 円および円弧の近似方法 - Google Patents

Abstract

(57)【要約】 【目的】 画像データ中にある点列を円または円弧に近
似するときの処理計算を速くでき、始点、終点を必ず通
りしかも計算のために特殊なＣＰＵを必要としない。 【構成】 ステップＳ１は画像データ中にある点列を円
または円弧に近似する際、対象とする点列の２つの端点
と、他の１点の合計３点を通る円／円弧を仮定するもの
である。ステップＳ２はステップＳ１で円／円弧を仮定
した際、点列の他の１点が円の円周上にあるかどうかを
判定し、ＹＥＳのときは、ステップＳ３で点列の全ての
要素の点が円周上にあると判定されて点列を仮定した円
弧として認識される。また、ＮＯのときは、ステップＳ
４に進んで円周上から一定以上離れた点があると判定さ
れて点列を円弧に近似しない。ステップＳ１は点列の代
表点を選択する処理で、これらの点列が円弧であるとき
は、その２つある端点が円弧の始点と終点である。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、画像処理において特
徴抽出を行う場合、特に高速に円および円弧を仮定する
計算方法を使用したエッジ画像データ中にある円および
円弧の近似方法に関する。

【０００２】

【従来の技術】画像処理において、カメラ或いはイメー
ジスキャナから入力した画像データを基にして、特徴と
しての円弧を抽出することが、様々な分野で広く行われ
ている。

【０００３】例えば、図面読み取り装置では、イメージ
スキャナから入力した図面のラスタデータから直線、
円、文字等を抽出してそれぞれ個別にＣＡＤデータに変
換する手段を採っている。この変換手段のときに図面デ
ータから円弧を抽出する処理が行われる。また、画像検
査装置では、対象部品の切り欠きや外周の位置と大きさ
を検査するときに入力した画像データからエッジを検出
し、得られるエッジ画像中から円弧を検出して、その位
置と大きさ（半径）を計測し、比較検査を行っている。
いずれの場合も、円弧を構成することが予測される点の
集合の座標（点列）をもとに、最小二乗法等の近似手段
を用いて円の方程式を近似し、中心位置と半径を計算し
て、この点列を円弧と決定する方法を採るのが一般的で
ある。

【０００４】

【発明が解決しようとする課題】上記円弧の最小二乗近
似は、常識的には広く使用されている方法であるが、第
１の難点は計算に時間がかかることであり、第２の難点
は円弧を近似したときに計算した円弧が必ずしも点列の
始点、終点を通らないことである。計算時間に関しては
上述した計算式でわかるように、点列を構成する点の数
によって大きく変動する。点の数をＮとすると、計算結
果を得るために必要な掛け算の回数は、２７Ｎ＋４５回
である。

【０００５】例えば、１０点のデータから円弧を近似す
るときは、３１５回、１００点の場合は、２７４５回の
掛け算が必要である。これは、１回の掛け算に１０μ秒
かかるＣＰＵを使用したときは、１００個の円弧を近似
すると掛け算だけで２.７秒かかる計算になる。近似し
た円弧が点列の始点終点を通らないと、ある曲線を複数
の円弧で近似したときにこれらが離れてつながらない状
態が発生し、もとの図面、または対象物の復元ができな
いことがあり、実用的に問題がある。

【０００６】この発明は上記の事情に鑑みてなされたも
ので、画像データ中にある点列を円または円弧に近似す
るときの処理計算を速くでき、始点、終点を必ず通りし
かも計算のために特殊なＣＰＵを必要としない円および
円弧の近似方法を提供することを目的とする。

【０００７】

【課題を解決するための手段】この発明は、上記の目的
を達成するために、第１発明は、画像データ中にある点
列を円および円弧に近似する方法において、対象とする
点列の２つの端点と他の１点の合計３点を通る円／円弧
を仮定した後、点列の他の点が円の円周上にあるかどう
かを判定し、判定後、点列の全ての要素の点が円周上に
あれば点列を仮定した円弧として認識し、円周上から一
定以上離れた点があれば点列を円弧に近似しないとした
ことを特徴とするものである。

【０００８】第２発明は、点列の他の１点は、点列の中
間点を選択することを特徴とするものである。

【０００９】第３発明は、平面上の３点の座標を、Ａ
（ｕ１，ｖ１），Ｂ（ｕ２，ｖ２），Ｍ（ｕ３，ｖ３）
とし、Ｍ点を共通点としてＡ，Ｂ点から第１、第２の線
分で結んでから、両線分の垂直二等分線を次式から求
め、

【００１０】

【数３】

【００１１】

【数４】

【００１２】求めた二等分線を延長して交差した点を円
の中心点Ｏ（ａ，ｂ）とし、この中心点とＭ点との距離
を、√｛（ｕ３−ａ）²＋（ｖ３−ｂ）²｝の式から求め
て円の半径ｒとして、円および円弧を仮定したことを特
徴とするものである。

【００１３】

【作用】この発明は上記のように構成することにより、
短時間で近似をおこなうことができるとともに、近似し
た円弧は必ず点列の端点を通る。また、計算は最大で３
つの三乗項を加算するだけなので、もとの座標データが
最大３桁の整数であるから、最大９桁の整数が計算でき
れば良いために、一般的なＣＰＵで処理が可能である。

【００１４】

【実施例】以下この発明の一実施例を図面に基づいて説
明する。図１はこの発明の一実施例を示すフローチャー
トで、図１において、Ｓ１は画像データ中にある点列を
円または円弧に近似する際、対象とする点列の２つの端
点と、他の１点の合計３点を通る円／円弧を仮定するス
テップである。ステップＳ２はステップＳ１で円／円弧
を仮定した際、点列の他の１点が円の円周上にあるかど
うかを判定するもので、ＹＥＳの場合は、ステップＳ３
で点列の全ての要素の点が円周上にあると判定されて点
列を仮定した円弧として認識される。また、ＮＯの場合
は、ステップＳ４に進んで円周上から一定以上離れた点
があると判定されて点列を円弧に近似しない。

【００１５】前記ステップＳ１は点列の代表点を選択す
る処理で、図面のラスタデータや画像検査のエッジ画像
から円／円弧と予想される点列を選択することは、従来
よりラベリングや特徴の切り出しなどで行われていた。
これらの点列が円弧であるときは、その２つある端点が
円弧の始点と終点である。点列が円の一部である場合も
点列の端点は円を仮定するときの重要なポイントとな
る。従って、この発明では、点列の代表点としてまず２
つの端点を選択する。

【００１６】円を仮定するためには、最低３つの点が必
要で、計算精度を上げるためにはこれらの３点が離れて
いることが望ましい。従って、この発明ではもう一つの
代表点として点列の中間点を選択する。つまり、この発
明では、点列が構成する円／円弧を、点列の始点と終点
および中間点の合計３点を通る円／円弧と仮定する。次
に３点を通る円の方程式について述べる。平面上で３点
の座標が与えられるとこれらを通る円の方程式は一意的
に求めることができる。円の中心が（ａ，ｂ）で半径が
ｒの円の方程式は、 （ｘ−ａ）²＋（ｙ−ｂ）²＝ｒ² であるから、３点の座標を、（ｕ１，ｖ１），（ｕ２，
ｖ２），（ｕ３，ｖ３）とすれば、次の三元連立方程式
が導かれる。

【００１７】（ｕ１−ａ）²＋（ｖ１−ｂ）²＝ｒ² （ｕ２−ａ）²＋（ｖ２−ｂ）²＝ｒ² （ｕ３−ａ）²＋（ｖ３−ｂ）²＝ｒ² 上記式を解けば３つの定数ａ，ｂ，ｒを求めることがで
きるのは明白である。次に３点を通る円の方程式を求め
るもう一つの方法について述べる。前記と同様に平面上
の３点を、Ａ（ｕ１，ｖ１），Ｂ（ｕ２，ｖ２），Ｍ
（ｕ３，ｖ３）としたときに図２に示すように、ＡＢＭ
を通る円の中心Ｏ（ａ，ｂ）は、線分ＡＭの垂直二等線
分と線分ＢＭの垂直二等線分の交点であることを利用す
るものである。線分ＡＭの垂直二等線分と線分ＢＭ垂直
二等線分の方程式は次式のようになる。

【００１８】

【数５】

【００１９】

【数６】

【００２０】この２本の直線の交点が（ａ，ｂ）ならば
上記式は次式のようになる。

【００２１】

【数７】

【００２２】

【数８】

【００２３】上記式からｂを消去すると容易にａが導け
る。ａは次式のようになる。

【００２４】

【数９】

【００２５】点（ａ，ｂ）は線分ＢＭの垂直二等線分上
にあるので、ｂはａをもとにして次式のように求まる。

【００２６】

【数１０】

【００２７】また、円の半径ｒは中心点Ｏと中間点Ｍと
の距離として次の（３）式のように求めることができ
る。

【００２８】 ｒ＝√｛（ｕ３−ａ）²＋（ｖ３−ｂ）²｝ ………（３） 上記の方法は、（イ）３点Ａ，Ｂ，Ｍが一直線上にあ
る、（ロ）線分ＡＭがｘ軸またはｙ軸と平行、（３）線
分ＢＭがｘ軸またはｙ軸と平行の場合には上記（１）、
（２）、（３）式の導入に使用した垂直二等分線の方程
式の仮定が成立しないので、上記（１）式〜（３）式は
適用できない。

【００２９】これらのうち、上記（イ）の「３点Ａ，
Ｂ，Ｍが一直線上にある場合」は、この点列は円弧では
ないとすることができる。しかしながら、これ以外の場
合は垂直二等分線の方程式が異なるだけで、同一の考え
方で円の方程式、中心と半径を導くことができる。な
お、（１）式において、分母が０のときはａを求めるこ
とが出来ないが、このとき、 （ｕ３−ｕ１）（ｖ３−ｖ２）−（ｕ３−ｕ２）（ｖ３−ｖ１）＝０ から、次式が得られる。

【００３０】 （ｕ３−ｕ１）／（ｖ３−ｖ１）＝（ｕ３−ｕ２）／（ｖ３−ｖ２）…（４） 上記（４）式は、線分ＡＭと線分ＢＭの傾きが等しい、
すなわち、３点Ａ，Ｂ，Ｍが一直線上にあることを意味
しており。この場合、円弧に近似することは出来ない。

【００３１】上記（ロ）における「線分ＡＭがｘ軸と平
行な場合」について次に述べる。この場合、線分ＡＭの
垂直二等分線の方程式は、ｘ＝（ｕ３＋ｕ１）／２であ
るから、ａ＝（ｕ３＋ｕ１）／２となり、従って、点
（ａ，ｂ）は線分ＡＭの垂直二等分線上にあるので、
「ｂ」は「ａ」をもとにして次式のようになる。

【００３２】

【数１１】

【００３３】上記（ロ）における「線分ＡＭがｙ軸と平
行な場合」について述べると以下のようになる。線分Ａ
Ｍの垂直二等分線の方程式は、ｙ＝（ｖ３＋ｖ１）／２
であるから、ｂ＝（ｖ３＋ｖ１）／２となり、点（ａ，
ｂ）は線分ＢＭの垂直二等分線上にあるので、「ａ」は
「ｂ」をもとにして次式のようになる。

【００３４】

【数１２】

【００３５】上記（ハ）における「線分ＢＭがｘ軸と平
行な場合」は上記「線分ＡＭがｘ軸と平行な場合」と同
様に線分ＢＭの垂直二等分線の方程式から、ａ＝（ｕ３
＋ｕ２）／２であるから、点（ａ，ｂ）は線分ＡＭの垂
直二等分線上にあるので「ｂ」は「ａ」をもとにして次
式のようになる。

【００３６】

【数１３】

【００３７】上記（ハ）における「線分ＢＭがｙ軸と平
行な場合」は前述と同様に線分ＢＭの垂直二等分線の方
程式から、ｂ＝（ｖ３＋ｖ２）／２であるから、点
（ａ，ｂ）は線分ＢＭの垂直二等分線上にあるので
「ａ」は「ｂ」をもとにして次式のようになる。

【００３８】

【数１４】

【００３９】次に点列が仮定した円／円弧に近似できる
かを判断するかについて述べる。前述した（１）〜
（３）式は点列が円または円の一部であると仮定したと
きの一つの円の候補である。点列をこの円に近似するた
めには、点列を構成する各点が仮定した円周上にあるこ
とをチェックしなければならない。この発明の方法で
は、点列の全ての点が（１）〜（３）式で仮定した円の
円周上にあるときは、点列をこの円弧に近似し、ある点
が仮定した円周上にないときは、点列は円または円弧で
はないと決定する。

【００４０】図面読み取りや画像検査の場合、点列が円
／円弧でないときは、この点列は直線か、複数の直線と
円弧の集合であると考えられる。その場合は別途、何ら
かの方法で点列を細分化して再度直線や円弧の近似を行
うものとする。各点が仮定した円周上にあるかどうかの
チェックは例えば以下の方法で行う。チェックの対象点
Ｐの座標を（ｕｉ，ｖｉ）とすると、点Ｐと円の中心Ｏ
の距離「１」は次式のようになる。

【００４１】１＝√｛（ｕｉ−ａ）²＋（ｖｉ−ｂ）²｝ 上記式から点Ｐが仮定した円周上にあれば、１＝ｒで判
断することが出来る。

【００４２】次に前述した方法を使用した場合の計算時
間について考察して見る。（１）〜（３）式を利用すれ
ば、円の中心、半径を仮定するために、必要な掛け算の
数は１７回である。上述した各点が仮定した円周上にあ
るかどうかのチェックは、最小に上方で円を近似した場
合にも本来必要である。この発明の方法では必ずチェッ
クを行う必要があるので、Ｎ点のチェックに要する掛け
算の回数は、３Ｎ回である。これらを合計すると例え
ば、１０点の点列の近似計算には４７回、１００点の場
合は３１７回の掛け算を行う。これは従来の最小二乗法
の計算に比べて１１〜１５％の計算時間で円の近似が終
了することになるから計算時間を短くできる。すなわ
ち、計算を速く出来ることを意味する。

【００４３】上述したように点列を円弧に近似するとき
に近似した円弧が点列の端点を通ることは重要である。
この発明の方法では、仮定する円弧は点列の２つの端点
を含む３点を通る一意的な円の一部であり、原理的に２
つの端点を通過する。すなわち、近似した円弧の場合は
必ず始点、終点を通過する。

【００４４】

【発明の効果】以上述べたように、この発明によれば、
最小二乗法による近似計算と比較して短時間で近似を行
うことができるので、計算が速くなる。また、この発明
では、近似した円弧は必ず点列の端点、すなわち、始
点、終点を通る。さらに、この発明では、計算が最大で
３つの三乗項を加算するだけなので、もとの座標データ
が最大３桁の整数であることを考えれば、最大９桁の整
数が計算できれば良いため、特殊なＣＰＵが不要となる
とともに、計算が速くなる要因ともなる。

【図面の簡単な説明】

【図１】この発明の実施例を示すフローチャート。

【図２】実施例を説明するための説明図。

フロントページの続き (51)Int.Cl.⁶ 識別記号 庁内整理番号 ＦＩ 技術表示箇所 9365−5Ｌ Ｇ０６Ｆ 15/72 ３５５ Ｐ

Claims (3)

【特許請求の範囲】
1. 【請求項１】 画像データ中にある点列を円および円弧
   に近似する方法において、対象とする点列の２つの端点
   と他の１点の合計３点を通る円／円弧を仮定した後、点
   列の他の点が円の円周上にあるかどうかを判定し、判定
   後、点列の全ての要素の点が円周上にあれば点列を仮定
   した円弧として認識し、円周上から一定以上離れた点が
   あれば点列を円弧に近似しないとしたことを特徴とする
   円および円弧の近似方法。
2. 【請求項２】 点列の他の１点は、点列の中間点を選択
   することを特徴とする請求項１記載の円および円弧の近
   似方法。
3. 【請求項３】 平面上の３点の座標を、Ａ（ｕ１，ｖ
   １），Ｂ（ｕ２，ｖ２），Ｍ（ｕ３，ｖ３）とし、Ｍ点
   を共通点としてＡ，Ｂ点から第１、第２の線分で結んで
   から、両線分の垂直二等分線を次式から求め、 【数１】 【数２】 求めた二等分線を延長して交差した点を円の中心点Ｏ
   （ａ，ｂ）とし、この中心点とＭ点との距離を、√
   ｛（ｕ３−ａ）²＋（ｖ３−ｂ）²｝の式から求めて円の
   半径ｒとして、円および円弧を仮定したことを特徴とす
   る請求項１記載の円および円弧の近似方法。