JPH0352083A - 直線近似方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔概要〕 入力点から近似直線を算出する直線近似方式に関し、 入力点から取り出した２点のうちから予想直線に対する
平行成分が所定閾値以上かつ垂直或分が所定閾値以下の
２点について、あるいは予想直線からの距離が所定闇値
以下の１点もしくは２点について、ρ−θ空間の値を求
めて最大頻度のパラメータ（ρ、θ）を出力し、計算量
を少なくして高速に直線近似のパラメータを求めること
を目的とし、 入力点から取り出した任意の２点を結ぶ線分と予想直線
との間の平行威分が所定閾値以上かつ垂直或分が所定闇
値以下の組み合せを選択し、これら選択した２点を結ん
だ線分のパラメータ（ρ、θ）を計算するパラメータ計
算部を備え、このパラメータ計算部によって計算したパ
ラメータ（ρ、θ）についてρ−θ空間をメッシュ状に
分割した領域に加算することを繰り返し、最大頻度の領
域の座標（ρ、♂）を近似直線のパラメータ（ρ、θ〉
とするように構或する．また、人力点から取り出した任
意のｌ点乙予想直線との間の距離が所定閾値以下の点を
選択し、これら選択したうちの任意の１点を通る直線の
パラメータ（ρ、θ）、もしくはこれら選択したうちの
任息の２点を結んだ線分のパラメータ（ρ、θ）を計算
するパラメータ計算部を備え、このパラメータ計夏部に
よって計算したパラメータ（ρ、θ）についてρ一θ空
間をメッシュ状に分割した領域に加算することを繰り返
し、最大頻度の領域の座ｔ１（ρ、θ）を近似直線のパ
ラメータ（ρ、θ）とするように構成する． 〔産業上の利用分野〕 本発明ば、入力点から近似直線を算出するｉｉＩ線近似
方式に関するものである．画像処理装置において、画像
中の複数の点に直線近似した直線を求めることは、物体
の方向や境界を抽出するのに非常に重要な技術である。

入力画像は多くの雑音を含んでいるため、物体の方向や
境界を見い出すために、物体上の複数の点や境界上の複
数の点について迅速かつ正確に直線近似した直線を求め
ることが望まれている． 〔従来の技術と発明が解決しようこする課題〕従来、画
像中の複数の点の直線近似は、ハフ技術を用い、第４図
（イ）に示す構威により、直線のパラメータ（ρ、θ）
を求めるようにしていた。

この際、第４図（ロ）に示すように、入力された各点か
ら下式（１１を満足するρおよびθを求め、これを第５
図（口）ρ−θ空間上の該当する分割領域の頻度に加算
する． Ｘｃｏｓ　　（θ）＋Ｙｓｉｎ（θ）−ρ−−−＋１＋
ここで、ρは原点０から直線までの距離を表し、θは直
線がＹ軸となす角度を表す． そして、最大頻度の座標（ρ、θ）を求め、これを直線
のパラメータ（ρ、θ）としていた．このため、各入力
点について式（１）からρおよびθの値をそれぞれ求め
る必要があり、計算量が多《なり、時間がかかり過ぎる
という問題があった．第４図および第５図を簡単に説明
する．第４図（イ）において、入力点格納部２１から取
り出した１つの点について、パラメータ計算部２２が上
式（１）によってρ−θ空間上の値を求め、パラメータ
格納部２３に格納する．パラメータ最大頻度計算部２４
は、最大頻度を持つ座標（ρ、θ）を検出し、これを結
果パラメータ格納部２５に格納する．この際、第４図（
ロ）に示すパラメータ計算部２２を構或する点データ制
御部２２一ｌが取り込んだ１つの点を１点一時格納部２
２−２に格納する．ｐ計算部２４−４がθ発生部２２−
３から順次通知されたθ値 θ＝　（ｎ／Ｎ）２π・・・・・・・・・・・Ｃ２）こ
こで、ｎ＝０、１、２・・・Ｎ を式（１１に代入すると共に、ｔつの点の座標値（Ｘ、
Ｙ）を代入し、ρを全て求める．これらθおよびＰをバ
ラメーター時格納部２２−５に順次格納する． 次に、第５図を用いてパラメータについて説明する．こ
こで、パラメータの距離ρおよび角度θは、第５図（イ
）に示すように、画面上の中心点０からの距離ρおよび
角度θである．ガイドラインの方程式は、上述した式＋
１１によって表される．ここで、ガイドライン上の１つ
の点（Ｘ．．Ｙ）を通るパラメータ（ρ、θ）は、上式
＋１１を満たす曲線となる． 第５図（ロ）は、ρ一θ空間をメソシュ上に分割し、パ
ラメータ（ρ、θ〉を分割した領域に加算し、最大頻度
のパラメータ（ρ、θ〉をガイドラインのパラメータと
して検出する． 本発明は、入力点から取り出した２点のうちから予想直
線に対する千行成分が所定閾値以上かつ垂直或分が所定
閾値以下の２点について、あるいは予想直線からの距離
が所定閾値以下の１点もしくは２点について、ρ−θ空
間の値を求めて最大頻度のパラメータ（ρ、θ〉を出力
し、計算量を少なくして高速に直線近似のパラメータを
求めることを目的としている。

〔課題を解決する手段〕

第１図を参照して課題を解決する手段を説明する。

第ｌ図において、パラメータ計算部２ば、入力点から取
り出した任意の２点を結ぶ線分ε予想直線との間の平行
成分が所定！ｉｍ以上かつ垂直成分が所定闇値以下の組
み合せを選択し、あるいは入力点から取り出した任意の
ｌ点と予想直線との間の距離が所定闇値以下の１つの点
もしくは２つの点を選択し、選択した１点を通る直線も
しくはこれら選択した２点を結んだ線分のパラメータ（
ρ、θ）を計算するものである． パラメータ最大頻度計算部４は、パラメータ計算部２に
よって計罪したパラメータ（ρ、θ）についてρ−θ空
間をメッシュ状に分割した領域に加算することを繰り返
し、最大頻度の領域の座標（ρ、θ）をパラメータとし
て求めるものである．Ｃ作用〕 本発明は、第ｌ図に示すように、パラメータ計算部２が
人力点から取り出した任意の２点を結ぶ線分と予想直線
との間の平行成分が所定闇値以上かつ垂直威分が所定闇
値以下の組み合せを選択し、これら選択した２点を結ん
だ線分のパラメータ（ρ、θ）を計算し、パラメータ最
大頻度計算部番がこれら計算したパラメータ（ρ、θ）
をρ−θ空間でメソシエ状に分割した領域に加算するこ
とを繰り．返し、最大頻度のｖｉ域の座標（ρ、θ）を
求め、これを近似直線のパラメータ（ρ、θ）として出
力するようにしている．また、パラメータ計算部２が入
力点から取り出した任意の１点ε予想直線との間の距離
が所定閾値以下のｉつの点もしくは２つの点を選択し、
この１点を通る直線もしくはこれらの２点を結んだ線分
のパラメータ（ρ、θ）を計算し、パラメータ最大頻度
計算部４がこれら計算したパラメータ（ρ、θ）をρ−
θ空間でメッシュ状に分割した領域に加算することを繰
り返し、最大頻度の領域の座標（ρ、θ）を求め、これ
を近似直線のパラメータ（ρ、θ）として出力するよう
にしている． 従って、入力点から取り出した２点のうちから予想直線
に対する平行或分が所定閾値以上かつ垂直威分が所定闇
値以下の２点について、あるいは予想直線からの距離が
所定閾値以下の１点もしくは２点について、ρ−θ空間
の値を求めて最大頻度のパラメータ（ρ、θ）を出力す
ることにより、計夏量を少なくし、高速に直線近似する
ことが可能となる． 〔実施例〕 次に、第ｌ図から第３図を用いて本発明のｌ実施例の構
或および動作を順次詳細に説明する．ここで、予想直線
からの距離が所定閾値以下の１点について、このｌ点を
通る直線のパラメータ（ρ、θ）を求めるものの実施例
の構成ぱ、従来の第４図点データ制御部２２−１におい
て、予想直線からの距離による制限を加えるようにして
いるので、割愛する． 第ｌ図において、入力点格納部ｌは、カメラを用いて撮
影した画像中からガイドラインに対応ずる色（例えば白
色）などの特徴を持つ点の座標を格納したものである．
ここで、ガイドラインは、例えば無人自走車の走路を路
上に引いた線や、沿って走るべき腺であり、作業をしつ
つ移動する自走車の場合、作業済区域と未作業区域の境
界線、あるいは直前の作業済領域の線がガイドラインと
なる．具体的に言えば、無人芝刈機の場合には、芝刈済
区域と、未芝刈区域との境界線がガイドラインとなる． パラメータ計算部２ば、２−１ないし２−６から構威さ
れ、入力点格納部１から取り出した任意の２点を結ぶ線
分と予想直線との間の平行或分が所定闇値以上かつ垂直
或分が所定閾値以下の組み合せを選択し、あるいは人力
点から取り出した任意の１点と予想直ｍ．＝の間の距離
が所定閾値以下の２つの点を選択し、これらの２点を結
んだ線分のパラメータ（ｐ，θ）を計算するものである
。

パラメータ格納部３は、パラメータ計算部２によって計
算したパラメータを格納するものである．パラメータ最
大頻度計蒐部４は、パラメータ計算部２によって計算し
たパラメータ（ρ、θ）についてρ−θ空間でメッシュ
状に分割した領域に加算することを繰り返し、最大頻度
の領域の座標（ρ、θ）をパラメータとして求めるもの
である．結果パラメータ格納部５は、パラメータ最大頻
度計算部４によって算出した直線のパラメータを格納す
るものである。

次に、パラメータ計算部２の構成および動作を詳細に説
明する． 点データ＠御部２−１ば、入カデータから２つの点の座
標を取り込み、第１点一時格納部２−２および第２点一
時格納部２−３に格納するものである．この際、取り込
む２点のデータは、既述したように、｛１｝任意の２点
の予想直線に対する水平或分が所定閾値以上、かつ垂直
成分が所定閾値以下の２点について、あるいは（２）予
想直線に対する距離が所定閾値以下の２点について、第
１点一時格納部２−２および第２点一時格納部２−３に
格納するようにしている。

θ計算部２−４は、２点の座［（Ｘｉ，Ｙｌ）、（Ｘ２
、Ｙ２）から下式（３）によってθを求めるものである
． θ−ａｒｃｔａｎ　（ＸＺ−ＸＩ）／　（Ｙ：’−Ｙ１
）・・・・・・・・・・・・・・・・・・・０）ρ計算
部２−５は、下式（４）によってρを求めるものである
。

ρ＝　　（Ｘｉ）　　ｃｏｓ　　（θ）＋（Ｙｌ）ｓｉ
ｎ（θ）・・　・　・　・　・　・　・　・　・　・　
・　・　・　・　・　・　・　・　・（４）パラメータ
ー時格納部２−６は、θ計算部２４およびρ計算部２−
５によってそれぞれ求めたθおよびρを格納するもので
ある。

次に、第２図を用いて第１図構或の動作を詳細に説明す
る． 第２図において、［株］は、画像入力する。これば、カ
メラを用いてガイドラインを含む画像を取り込む． ０は、任意の２点を取り出し、予想直線に対する平行成
分および垂直或分を算出する．これは、左側に示すよう
に、任意の２点Ａ．．Ｂを結んだ線分について、予想直
線に対ずる平行或分および垂直成分を算出する． Ｏば、平行成分≧閾値ｌ，かつ垂直威分５閾値２か否か
を判別する．ＹＥＳの場合には、パラメータ計算対象と
し、■を行う．Ｎｏの場合には、パラメータ計算対象か
ら外し、［相］を行う．■は、２点を結んだパラメータ
（ρ、θ）を算出する．これは、既述した式（３）、式
（４）によってθおよびρを算出する． ［相］は、全ての組み合せが終了か否かを判別する。

ＹＥＳの場合には、＠を行う．ＮＯの場合には、■で次
の組み合せを選択し、■以降を操り返し行う． ■は、最大頻度を持つブロックを求める。これは、■で
求めたθおよびρについて、ρ−θ空間上の分割した領
域に頻度を加算し、最大頻度の座標を求め、これを代表
値（ρ３、θ０）とする。

この際、最大頻度のブロックが複数存在する場合には、
その中心を代表値（ρ４、θｍ）とする。

［相］は、結果出力する．これは、■で求めた代表値（
ρ１、θ０）を直線のパラメータとして出力する． 以上の処理によって、任意の２点を結んだ線分の予想直
線に対する平行或分が所定閾値以上かつ垂直或分が所定
閾値以下の２点についてのみ、パラメータ抽出・最大頻
度のパラメータ検出を行い、直線のパラメータ（ρ０、
θ０〉を求めるここにより、計算対象数を減らし、高速
に直線のパラメータを求めることが可能となる． 第３図を用いて第１図構成の動作を詳細に説明する． 第３図において、［相］は、画像入力する．これば、カ
メラを用いてガイドラインを含む画像を取り込む． ［相］は、任意の１点を取り出し、予想直線からの距離
を求める．これは、左側に示すように、任意の１点Ａか
ら予想直ＮＩＡまでの距離を求める．０は、距離≦Ｐｉ
｛ｆか否かを判別する．ｙＥｓの場合には、０でパラメ
ータ計算対象とし、［相］を行い。ＮＯの場合には、パ
ラメータ計算対象から外し、［相］を行う． ［相］は、終わりか否かを判別する．ＹＥＳの場合には
、■以降を行う．ＮＯの場合には、［相］で次の点を取
り出し、［相］以降を繰り返し行う．■は、任意の２点
を取り出す．これは、ＯＹＥＳ，ｏで計算対象とした点
のうちから任意の２点を取り出す． ［相］は、２点を結ぶ直線のパラメータ（ρ、θ）を算
出する．これば、既述した式（３）、式（４）によって
θおよびρを算出する． Ｏば、全ての組み合せが終了か否かを判別する．ＹＥＳ
の場合には、［相］を行う．ＮＯの場合には、■で次の
組み合せを選び、■以降を繰り返し行う．［相］は、最
大頻度を持つブロンクを求める．これば、＠で算出した
直線のパラメータ（ρ、θ）について、ρ一θ空間上で
メッシュ状に分割した該当ブロンク（ｖｉ域）の頻度を
加算し、最大頻度のブロックの代表４１！　（ρ９、θ
８）を求める．０は、結果を出力する． 以上の処理によって、予想直線との距離が所定閾値以下
の点についてのみ、パラメータ計算・最大頻度のパラメ
ータ検出を行い、直線のパラメータ（ρ０、θ０）を求
めることにより、計算対象数を減らし、高速に直線のパ
ラメータを求めることが可能となる。

＋１１　　また、画像処理装置において、第２図を適用
する際に、予想直線をＹ軸方向にした場合、２点（Ｘｉ
、Ｙｌ）、（Ｘ２、Ｙ２）を結ぶ線分と予想直線である
Ｙ軸に対する平行成分は（Ｙｌ〜Ｙ２）、垂直成分は（
Ｘｉ，Ｘ２）となり、計算が極めて簡単となる．これは
、例えば無人自走車のカメラによって撮影した画像上の
ガイドラインがほぼＹ軸となることが多く、このときの
直線のパラメータを算出する際に、計算量を極めて少な
くすることができる． （２）　　また、画像処理装置において、第３図を適用
する際に、予想直線をＹ軸方向にした場合、入力点から
取り出した点（Ｘｉ、Ｙｌ）と、予想直線であるＹ軸と
の距離は、Ｘｉとなり、計算が極めて簡単となる．これ
は、例えば無人自走車のカメラによって撮影した画像上
のガイドラインがほぼＹ軸となることが多く、このとき
の直線のパラメータを算出する際に、計算量を極めて少
なくすることができる． 〔発明の効果〕 以上説明したように、本発明によれば、入力点より取り
出した２点のうちから予想直線に対する千行或分が所定
閾値以上かつ垂直威分が所定閾値以下の２点について、
あるいは予想直線からの距離が所定閾値以下のｌ点もし
くは２点について、直線のパラメータ計算・最大頻度の
パラメータ検出を行う構成を採用しているため、計算量
を少なくし、直線近似した直線のパラメータを高速に算
出することができる．

【図面の簡単な説明】

第１図は本発明の１実施例構成図、第２図、第３図は本
発明の動作説明フローチャート、第４図は従来技術の構
成図、第５図はパラメータ説明図を示す． 図中、１ば入力点格納部、２ばパラメータ計算部、２−
１は点データ制御部、２−４はθ計算部、２−５はρ計
算部、３ばパラメータ格納部、４ばパラメータ最大頻度
計算部を表す．

Claims (2)

【特許請求の範囲】
1. （１）入力点から近似直線を算出する直線近似方式にお
   いて、 入力点から取り出した任意の２点を結ぶ線分と予想直線
   との間の平行成分が所定閾値以上かつ垂直成分が所定閾
   値以下の組み合せを選択し、これら選択した２点を結ん
   だ線分のパラメータ（ρ、θ）を計算するパラメータ計
   算部（２）を備え、このパラメータ計算部（２）によっ
   て計算したパラメータ（ρ、θ）についてρ−θ空間を
   メッシュ状に分割した領域に加算することを繰り返し、
   最大頻度の領域の座標（ρ、θ）を近似直線のパラメー
   タ（ρ、θ）とするように構成したことを特徴とする直
   線近似方式。
2. （２）入力点から近似直線を算出する直線近似方式にお
   いて、 入力点から取り出した任意の１点と予想直線との間の距
   離が所定閾値以下の点を選択し、これら選択したうちの
   任意の１点を通る直線のパラメータ（ρ、θ）、もしく
   はこれら選択したうちの任意の２点を結んだ線分のパラ
   メータ（ρ、θ）を計算するパラメータ計算部（２）を
   備え、 このパラメータ計算部（２）によって計算したパラメー
   タ（ρ、θ）についてρ−θ空間をメッシュ状に分割し
   た領域に加算することを繰り返し、最大頻度の領域の座
   標（ρ、θ）を近似直線のパラメータ（ρ、θ）とする
   ように構成したことを特徴とする直線近似方式。