(57)【特許請求の範囲】
【請求項１】
入力画像から得られる線画画像中の線画から、複数の画素によって構成される第１の線分を抽出し、次いで新たな画素を取り込んで、上記第１の線分を構成する上記複数の画素と上記新たな画素とによって構成される第２の線分を抽出し、上記第１の線分と上記第２の線分との一致度を判定する線分検出方法において、
上記線分抽出処理における上記画素に対する上記線分の始端からの離れ度合いに応じた重み付けと、上記一致度判定処理における上記第１の線分の長さに応じた重み付けとのうち、少なくとも上記一致度判定処理における重み付けを行なうとともに、
上記一致度判定処理を、上記第１および第２の線分間の誤差を所定のしきい値と比較することによって行ない、上記一致度判定処理における重み付けを、上記誤差に対して上記第１の線分の長さを乗算することによって行なうことを特徴とする線分検出方法。
【請求項２】
上記線分抽出処理における重み付けを、上記線分の始端から離れた画素の重みを軽くすることによって行なうことを特徴とする請求項１に記載の線分検出方法。
【請求項３】
上記線分抽出処理を最小二乗法を適用して行なうことを特徴とする請求項２に記載の線分検出方法。
【請求項４】
入力画像から得られる線画画像中の線画から、複数の画素によって構成される第１の線分を抽出し、次いで新たな画素を取り込んで、上記第１の線分を構成する上記複数の画素と上記新たな画素とによって構成される第２の線分を抽出する線分抽出部と、
該線分抽出部により抽出された上記第１および第２の線分が同一直線を形成するか否かを該第１および第２の線分間の誤差を所定のしきい値と比較することによって判別する直線判別部とを備え、
上記線分抽出部において上記画素に対して上記線分の始端からの離れ度合いに応じた重み付けを行う機能と、上記直線判別部において上記第１および第２の線分間の誤差に対して上記第１の線分の長さを乗算することによって重み付けを行う機能とのうち、少なくとも上記直線判別部において重み付けを行う機能が付与されていることを特徴とする線分検出装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、入力画像から線分を検出する線分検出方法およびその装置に関する。
【０００２】
【従来の技術】
例えば自動車組立て工場における作業の自動化のためには部品のハンドリングが非常に重要な問題である。特に、組立て領域の自動化において必要とされているようなロボットによる多機能で正確な自動ハンドリングを実現するためには、対象物の画像の細線化処理を行なって線分を検出し、この線分から対象物の形状を精度良く抽出する技術が必要となってくる。
【０００３】
従来の線分検出方法として、下記の方法が知られている。
(1) 入力画像に対して、エッジ検出、２値化、細線化等の前処理を行い、細線画像を得る。
(2) 上記細線画像に含まれる全てのセグメントについて、以下の処理(3) 〜(7)を行なう。ここで、「セグメント」とは、線幅１の、連続した画素列であって、分岐の無いものを意味する。
(3) 任意のセグメントの端点からｋ個の画素ｎ1 〜ｎk （ｋの初期値として、例えばｋ＝３とする）に対して、最小二乗法等を適用して直線を当てはめる。得られた直線をＬ1 とする。
(4) （ｋ＋１）番目の画素ｎk+1 が直線Ｌ1 に含まれるか否かを判別する。すなわち、画素ｎ1 〜ｎk+1 に対して、最小二乗法等を適用して直線を当てはめる。得られた直線をＬ2 とする。
(5) 直線Ｌ1 の傾きα1 と直線Ｌ2 の傾きα2 とを比較し、｜α1 −α2 ｜の値が所定のしきい値以下であれば、画素ｎk+1 は直線Ｌ1 上にあると判定し、｜α1 −α2 ｜の値が所定のしきい値よりも大きければ、画素ｎk+1 は直線Ｌ1 上にないと判定する。
(6) 画素ｎk+1 が直線Ｌ1 上にあれば、画素ｎ1 〜ｎk+1 に当てはまる直線をＬ2 として、処理(4) へ戻る。画素ｎk+1 が直線Ｌ1 上になければ、画素ｎ1 〜ｎk は１本の線分と見なし、画素ｎk+1 を端点とし、処理(3) へ戻って新たに直線を検出する。
(7) 処理(3) 〜(6) をセグメントの終点に達するまで反復する。
【０００４】
また、線分検出方法としては、上述以外に、画像情報から物体の輪郭を抽出して輪郭点座標を求め、該輪郭点座標からハフ（Hough ）変換を行なって関数ρ＝ｘｉｃｏｓθ＋ｙｉｓｉｎθで表される正弦波に変換し、パラメータθ，ρに従って２次元ヒストグラムを作成し、該ヒストグラム上のピーク点を検出することにより、上記輪郭点座標の示す線分情報を検出する方法がある（特開昭６４−７４６８０号公報参照）。
【０００５】
【発明が解決しようとする課題】
ところで、上述の処理(1) 〜(7) からなる従来の線分検出方法には、次のような問題点があり、それが原因で、正確な線分抽出が困難であった。すなわち、（１）ノイズの影響や量子化誤差のために、本来同一線分を構成する画素が、図５に示すように、同一直線上に位置しない。特に、上述の処理(5) で用いられるしきい値が小さいと、このような同一線分上にあるべき画素が、同一線分上にないものと判断され、多数の線分に細分化されてしまう。
（２）問題点（１）を解決しようとしてしきい値を大きくすると、曲線上の画素等に対しても線分が当てはめられ、図６に示すように、誤った線分検出結果を得ることになる。
【０００６】
また、ハフ変換を用いる方法は、複雑な処理を必要とし、使用メモリ量と処理コストの面で問題があった。
【０００７】
そこで、本発明は、上記問題点を解決するためになされたもので、入力画像から得られる線画画像からの正確な線分検出を容易になし得る線分検出方法およびその装置を提供することを目的とする。
【０００８】
【課題を解決するための手段】
本発明による線分検出方法は、入力画像から得られる線画画像中の線画から、複数の画素によって構成される第１の線分を抽出し、次いで新たな画素を取り込んで、上記第１の線分を構成する上記複数の画素と上記新たな画素とによって構成される第２の線分を抽出し、上記第１の線分と上記第２の線分との一致度を判定する線分検出方法において、
上記線分抽出処理における上記画素に対する上記線分の始端からの離れ度合いに応じた重み付けと、上記一致度判定処理における上記第１の線分の長さに応じた重み付けとのうち、少なくとも上記一致度判定処理における重み付けを行なうとともに、
上記一致度判定処理を、上記第１および第２の線分間の誤差を所定のしきい値と比較することによって行ない、上記一致度判定処理における重み付けを、上記誤差に対して上記第１の線分の長さを乗算することによって行なうことを特徴とする。
【０００９】
上記線分抽出処理における重み付けは、上記線分の始端から離れた画素の重みを軽くすることによって行なうことができる。
【００１０】
上記線分抽出処理は最小二乗法を適用して行なうことができる。
【００１１】
本発明による線分検出装置は、入力画像から得られる線画画像中の線画から、複数の画素によって構成される第１の線分を抽出し、次いで新たな画素を取り込んで、上記第１の線分を構成する上記複数の画素と上記新たな画素とによって構成される第２の線分を抽出する線分抽出部と、
該線分抽出部により抽出された上記第１および第２の線分が同一直線を形成するか否かを該第１および第２の線分間の誤差を所定のしきい値と比較することによって判別する直線判別部とを備え、
上記線分抽出部において上記画素に対して上記線分の始端からの離れ度合いに応じた重み付けを行う機能と、上記直線判別部において上記第１および第２の線分間の誤差に対して上記第１の線分の長さを乗算することによって重み付けを行う機能とのうち、少なくとも上記直線判別部において重み付けを行う機能が付与されていることを特徴とする。
【００１２】
【作用および発明の効果】
本発明の線分検出方法およびその装置によれば、曲線に対して誤って直線を当てはめたり、本来１本の線分が細分化されたりするような問題が解消され、正確な線分検出が可能になる。
【００１３】
特に、本発明の線分検出方法は、２つの線分の一致度判定処理において、線分探索開始直後では、線分候補点の小さなばらつきでも線分のパラメータの大きなばらつきとなるが、線分の長さを重み付けることによって、２本の線分の検出誤差を相対的に小さくすることができる。またこれとは逆に、線分探索が進むにつれて、線分候補点が大きくばらついても線分パラメータには小さなばらつきとしかならないが、線分の長さを重み付けることによって、上記検出誤差を相対的に大きくすることができる。
【００１４】
したがって、本発明によれば、２つの線分の一致度判定を安定的かつ正確に行なうことができる利点がある。
【００１５】
なお、上述の線分抽出処理において、線分の始端から離れた画素の重みを軽くする場合には、曲がった部分での直線の引っ張りを小さく押さえることができる。このため、線分のパラメータ検出をより正確に行なうことができる。
【００１６】
【実施例】
以下、図面を参照して本発明の実施例について説明する。
【００１７】
図１は、本発明による線分検出装置の構成を示すブロック図で、前処理部１、線分抽出部２および直線判別部３によって構成されている。
【００１８】
上記前処理部１は、入力画像に対して、エッジ検出、２値化、細線化およびラベル付け等の前処理を施して、線分候補点を抽出する機能を有する。上記線分抽出部２は、線分候補点に対して最小二乗法を適用して直線を当てはめる機能を有する。上記直線判別部３は、２つの線分が一致するか否か、すなわち２つの線分が同一直線を形成するか否かを判別する機能を有する。
【００１９】
次に、上記線分検出装置によって実行される処理の１例について、図２のフロ−チャ−トを参照して説明する。
【００２０】
（Ｉ）前処理
入力画像に対して、エッジ検出、２値化、細線化およびラベル付け等の各処理を順に行ない、ラベル付けされた線分候補点（画素）を得る（Ｓ１）。
【００２１】
（II）線分抽出
ラベル１が付された線分候補点群の端点からｉ番目の点（画素）の座標を（ｘi ，ｙi ）としたとき、１番目からｎ番目（例えばｎ＝３）までの点（画素）で規定される線分を１次の最小二乗法で算出する（Ｓ２〜Ｓ４）。
【００２２】
ただし、線分の始端から離れた終端部分のいくつかの点の重みを軽くして最小二乗法を適用する。例えば、終端の２０％の点の重みを軽くする場合は、１番目から 0.8ｎ番目未満までの点の重みを１とし、０．８ｎ番目からｎ番目までの点の重みを例えば０．５とする。そして実際には、下式から直線の方程式ｙ＝ａｘ＋ｂを計算する。ｗi は画素の座標値に対する重み付け係数である。
【００２３】
【数１】
0003651037.tif 000002
【００２４】
例えば、ｎ＝３であれば、１番目と２番目の点の重みを１とし、３番目の点の重みを０．５とする。また、ｎ＝６であれば、１番目から４番目までの点の重みのみを１とし、５番目と６番目の点の重みを０．５とする。
【００２５】
（III ）直線判別（一致度判定）
１番目からｎ番目までの点で規定される線分Ｌ1 を
ａ1 ｘ＋ｂ1 ｙ＋ｃ1 ＝０とし、
１番目からｎ＋１番目までの点で規定される線分Ｌ2 を
ａ2 ｘ＋ｂ2 ｙ＋ｃ2 ＝０とする。
【００２６】
線分Ｌ1 とＬ2 のパラメータをベクトルΛ1 ＝（ａ1 ，ｂ1 ，ｃ1 ），Λ2 ＝（ａ2 ，ｂ2 ，ｃ2 ）で表し、２本の線分Ｌ1 とＬ2 間のパラメータの誤差をｅ＝（Λ1 −Λ2 ）（Λ1 −Λ2 ）T LL1 とする。ただし、LL1 は線分Ｌ1 の長さを表す。
【００２７】
次に、線分Ｌ1 とＬ2 が一致するか否か、すなわち、線分Ｌ1 とＬ2 が同一直線を形成するか否かを上記誤差ｅの値によって判別する（Ｓ５）。すなわち、上記誤差ｅが所定のしきい値よりも小さければ、線分Ｌ1 とＬ2 は同一直線であると見做し（Ｓ６：ＹＥＳ）、１番目からｎ＋１番目までの点で線分Ｌ2 ：ａ2 ｘ＋ｂ2 ｙ＋ｃ2 ＝０が規定される。また、上記誤差ｅが所定のしきい値よりも大きければ、線分Ｌ1 とＬ2 は同一直線上にないと見做し（Ｓ６：ＮＯ）、１番目からｎ番目までの点で線分Ｌ1 ：ａ1 ｘ＋ｂ1 ｙ＋ｃ1 ＝０が規定され、ｎ＋１番目の点は異なる線分の端点とする。
【００２８】
（IV）候補点群の全ての点について処理（II）〜（III ）を反復する（Ｓ７〜Ｓ９）。
【００２９】
（Ｖ）次のラベルへ移動し、処理（II）〜（IV）を反復する（Ｓ１０，Ｓ１１）。
【００３０】
なお、直線判別（一致度判定）の方法として、上記２本の線分Ｌ1 とＬ2 のパラメータ誤差を求める方法の他に、図３に示すように、線分Ｌ1 の傾きα1 と線分Ｌ2 の傾きα2 との角度差によって求めることができる。
【００３１】
なお、本実施例では、上記（Ｉ）の前処理において、入力画像に対しエッジ検出、２値化、細線化およびラベル付け等の各処理を順に行ない、かつ上記（II）の線分検出において、線画画像に含まれる任意のセグメントの端点からｋ個の画素ｎ1 〜ｎk に対して当てはめられた第１の線分と、上記端点からｋ＋１個の画素ｎ1 〜ｎk+1 に対して当てはめられた第２の線分とのパラメータ誤差が所定のしきい値以下の場合に、画素ｎk+1 が上記第１の線分の延長線上にあると判定しているが、これに代わり、入力画像を微分して検出したエッジにおける各画素の濃度勾配のベクトル（方向および大きさ）を求め、互いに隣接する画素ｎk と画素ｎk+1 の濃度勾配のベクトルの差を所定のしきい値よりも小さい場合に、画素ｎk+1 が上記第１の線分の延長線上にあると判定するようにしても良い。
【００３２】
すなわち、図４に示すように、座標（ｘ0 ，ｙ0 ）を有する１つの画素ｎ0 の８近傍の画素の濃度をｆ1 〜ｆ8 とすると、画素ｐ0 の水平方向の濃度勾配ｕおよび垂直方向の濃度勾配ｖはそれぞれ下式で表される。
【００３３】
ｕ＝（ｆ3 ＋ｆ4 ＋ｆ5 ）−（ｆ1 ＋ｆ7 ＋ｆ8 ）
ｖ＝（ｆ5 ＋ｆ6 ＋ｆ7 ）−（ｆ1 ＋ｆ2 ＋ｆ3 ）
また、画素ｎ0 （ｘ0 ，ｙ0 ）の濃度勾配のベクトルの方向を示す直線をｙ＝ｋ×（ｘ−ｘ0 ）＋ｙ0 とすると、上記ベクトルの方向を表す係数ｋおよび上記ベクトルの大きさＰ0 はそれぞれ下記の式で表される。
【００３４】
ｋ ＝ tan-1（ｖ／ｕ）
Ｐ0 ＝√（ｕ2 ＋ｖ2 ）
このような画素の濃度勾配のベクトルの方向および大きさを求める演算を画素ｎk と画素ｎk+1 について行なって、両画素の濃度勾配のベクトルの方向および大きさの差がそれぞれ所定のしきい値以内である場合に、画素ｎ1 〜画素ｎk を含む線分と、画素ｎ1 〜画素ｎk+1 を含む線分とが同一直線上にあると判定すれば良い。そして、その判定時に互いに隣接する画素の濃度勾配のベクトルの方向および大きさの差に対して、上述と同様に線分の長さを乗算して重み付けを行なえば良い。
【００３５】
さらに、画素ｎ1 〜画素ｎk を含む線分の延長線に対して画素ｎk+1 から垂線を引き、この垂線の長さに関し同様の重み付けを行なった上で所定のしきい値と比較して、画素ｎ1 〜画素ｎk を含む線分と、画素ｎ1 〜画素ｎk+1 を含む線分とが同一直線上にあると判定するようにしても良い。
【図面の簡単な説明】
【図１】  本発明による線分検出装置の構成の１例を示すブロック図
【図２】  本発明による線分検出方法における処理の流れを表すフロ−チャ−ト
【図３】  同 作用の説明図
【図４】  画素の濃度勾配を該画素の８近傍の画素の濃度から求める方法の説明図
【図５】  従来の線分検出方法の問題点の説明図
【図６】  従来の線分検出方法の問題点の説明図
【符号の説明】
１ 前処理部
２ 線分抽出部
３ 直線判別部
【図１】
0003651037.tif 000003
【図２】
0003651037.tif 000004
【図３】
0003651037.tif 000005
【図４】
0003651037.tif 000006
【図５】
0003651037.tif 000007
【図６】
0003651037.tif 000008