(57)【要約】【課題】エッジ点の集合から、少数の頂点によって表される輪郭形状を、少ない処理で獲得する。【解決手段】エッジ抽出装置１は対象物の撮影画像からエッジ点の集合を抽出する。輪郭生成機構１０２は、最初に各エッジ点の集合が直線上に乗っていると見なせるまで、エッジ点集合を十分に小さく分割した画素列とし、隣り合う画素列の組を順次併合して画素列集合を順次生成する。輪郭評価機構１０５は、この画素列集合に対して評価値を算出する。併合ペア選択機構１０３は、輪郭評価機構１０５が出力する評価値を元にして、輪郭生成機構１０２が併合すべき画素列のペアを決定する。輪郭選択機構１０４は、輪郭生成機構１０２が生成し列挙したすべての画素列集合を評価し、その評価が最も高いものを選択し、選択された画素列集合から輪郭を生成して出力装置１０６に出力する。【選択図】  図１
2004234278.tif 000002
【特許請求の範囲】
【請求項１】
画像中の輪郭に含まれる画素列から、線分列として輪郭を抽出する方法であって、
画素列を分割して得られる画素列集合を、分割を変えて複数列挙する手順と、
該列挙された画素列集合に対して評価値を算出する手順と、
該評価値に基づいて該列挙された画素列集合を選択する手順と、
該選択された画素列集合から輪郭を構成する線分列を生成する手順と、を備える
ことを特徴とする輪郭線分抽出方法。
【請求項２】
請求項１に記載の輪郭線分抽出方法において、
評価値を算出する手順では、
画素列集合に対して、該画素列集合から生成される線分列と、該画素列集合に含まれる画素列とのずれを算出する手順と、
該ずれに基づいて該画素列集合の評価値を算出する手順と、を備える
ことを特徴とする輪郭線分抽出方法。
【請求項３】
請求項１に記載の輪郭線分抽出方法において、
評価値を算出する手順では、
画素列集合に対して、該画素列集合から生成される線分列の頂点数を算出する手順と、
該頂点数に基づいて該画素列集合の評価値を算出する手順と、を備える
ことを特徴とする輪郭線分抽出方法。
【請求項４】
請求項１ないし３のいずれかに記載の輪郭線分抽出方法において、
画素列集合を、分割を変えて複数列挙する手順では、
画素列集合のなかで隣り合う画素列を一つの画素列に併合することで画素列集合を生成する手順と、
該生成された画素列集合を列挙する手順と、を備える
ことを特徴とする輪郭線分抽出方法。
【請求項５】
請求項４に記載の輪郭線分抽出方法において、
画素列集合を生成する手順では、
画素列集合のなかで隣り合う画素列を併合して生成される画素列集合に対し、評価値を算出する手順と、
該評価値に基づいて併合する画素列のペアを選択する手順と、を備える
ことを特徴とする輪郭線分抽出方法。
【請求項６】
画像中の輪郭に含まれる画素列から、線分列として輪郭を抽出する装置であって、
画素列を分割して得られる画素列集合を、分割を変えて複数列挙する手段と、
該列挙された画素列集合に対して評価値を算出する手段と、
該評価値に基づいて該列挙された画素列集合を選択する手段と、
該選択された画素列集合から輪郭を構成する線分列を生成する手段と、を備える
ことを特徴とする輪郭線分抽出装置。
【請求項７】
請求項６に記載の輪郭線分抽出装置において、
評価値を算出する手段では、
画素列集合に対して、該画素列集合から生成される線分列と、該画素列集合に含まれる画素列とのずれを算出する手段と、
該ずれに基づいて該画素列集合の評価値を算出する手段と、を備える
ことを特徴とする輪郭線分抽出装置。
【請求項８】
請求項６に記載の輪郭線分抽出装置において、
評価値を算出する手段では、
画素列集合に対して、該画素列集合から生成される線分列の頂点数を算出する手段と、
該頂点数に基づいて該画素列集合の評価値を算出する手段と、を備える
ことを特徴とする輪郭線分抽出装置。
【請求項９】
請求項６ないし８のいずれかに記載の輪郭線分抽出装置において、
画素列集合を、分割を変えて複数列挙する手段では、
画素列集合のなかで隣り合う画素列を一つの画素列に併合することで画素列集合を生成する手段と、
該生成された画素列集合を列挙する手段と、を備える
ことを特徴とする輪郭線分抽出装置。
【請求項１０】
請求項９に記載の輪郭線分抽出装置において、
画素列集合を生成する手段では、
画素列集合のなかで隣り合う画素列を併合して生成される画素列集合に対し、評価値を算出する手段と、
該評価値に基づいて併合する画素列のペアを選択する手段と、を備える
ことを特徴とする輪郭線分抽出装置。
【請求項１１】
請求項１ないし５のいずれかに記載の輪郭線分抽出方法における手順を、コンピュータに実行させるためのプログラムとした
ことを特徴とする輪郭線分抽出プログラム。
【請求項１２】
請求項１ないし５のいずれかに記載の輪郭線分抽出方法における手順を、コンピュータに実行させるためのプログラムとし、
該プログラムを、該コンピュータが読み取りできる記録媒体に記録した
ことを特徴とする輪郭線分抽出プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、エッジ点の列から得られた細かな線分を併合していくことにより、線分の集合として輪郭を得る方法及び装置に関するものである。
【０００２】
【従来の技術】
画像から物体の２次元形状を獲得することは、画像の利用において基本的な処理であり、さまざまな応用において使われる。具体的には以下のような例が挙げられる。
・上空から撮影された航空写真から建物の形状を獲得して地図を作成する。
・監視カメラに移った物体を認識する。
・工業用ロボットが対象物を加工する際の位置決めをする。
【０００３】
ここで述べる「画像」とは、一般的なＣＣＤカメラによって撮像されたものだけではなく、レーザープロファイラによるＤＳＭ（Ｄｉｇｉｔａｌ  Ｓｕｒｆａｃｅ  Ｍｏｄｅｌ）や超音波の診断結果なども対象としている。この対象を観測することによって得られた数値情報が「画素値」として２次元平面上に広がっているデータであれば「画像」として扱うことができ、すなわち、本発明の対象としている「画像」に類するものである。
【０００４】
一般的な２次元形状の獲得方法としては以下のような方法がある（図１３）。
ステップ１：画素値がある一定値以上の領域を抽出する。
ステップ２：各領域において、境界上に存在する画素（エッジ点）を集める。
ステップ３：その画素の集合から輪郭線を生成し、対象物の形状とする。
【０００５】
上記の方法において、ステップ２の時点では、エッジ点の集まりとして形状が表されている。しかし、最終的には少数の頂点集合として形状を表現できたほうが、データ量を少なくでき、また、形状の拡大縮小なども簡単にできるため、望ましいことが多い。特に対象物が建物などの人工物で、線分から構成されているとわかっている場合には、エッジ点集合から直線を得ることで画像に含まれるノイズを除去できる可能性が高い。
【０００６】
たとえば、図１３の例では、途中結果として、エッジ点の集合として輪郭が得られているが、この状態では多数の点としてデータを保存しなければならない。しかし、線分を連結した形式で輪郭を得た最終結果では、輪郭情報として５つの頂点を保存すればよい。
【０００７】
点の集合から直線を獲得する方法としては、最小二乗法がある。また輪郭線を生成する方法としては、動的輪郭法（スネークス）［非特許文献１］や、輪郭線の折り曲がり具合が大きい点を頂点とする方法［非特許文献３］、などが提案されている。
【０００８】
上記のステップ３は以下のような処理に分割される。
処理１：輪郭を形成するエッジ点の列を複数に分割する。
処理２：次に各画素列から直線を求める。
処理３：それらの直線の交点を輪郭の頂点とする。
【０００９】
処理２においては、直線を求める際に最小二乗法を使うことで、元となるエッジ点と得られた輪郭とのずれを小さくすることができる。しかし、単にずれを小さくしようとすると輪郭を多数の線分から構成しなければならず、頂点数が増加し、輪郭のデータ量が増加するという問題がある。よって、ずれの量と頂点数のバランスをとるように、エッジ点の集合を適当に分割する方法が必要となる。
【００１０】
エッジ点の数が多い場合、処理１における分割の方法が非常に多数となり、すべてについて輪郭を生成して比較すると非常に時間がかかる（図１４）。この問題を解決するために、エッジ点を分類し、集合を分割する方法として、非特許文献２などが提案されている。
【００１１】
【非特許文献１】
Ｍ．Ｋａｓｓ，  Ａ．Ｗｉｔｋｉｎ，  ａｎｄ  Ｄ．Ｔｅｒｚｏｐｏｕｌｏｓ．  Ｓｎａｋｅｓ：  Ａｃｔｉｖｅ  Ｃｏｎｔｏｕｒ  Ｍｏｄｅｌｓ，  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ，  ｐｐ．３２１−３３１，１９８８．
【００１２】
【非特許文献２】
Ｋ．Ｆｕｊｉｉ  ａｎｄ  Ｔ．Ａｒｉｋａｗａ．  Ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ  ｏｆ  ３Ｄ  ｕｒｂａｎ  ｍｏｄｅｌ  ｕｓｉｎｇ  ｒａｎｇｅ  ｉｍａｇｅ  ａｎｄ  ａｅｒｉａｌ  ｉｍａｇｅ，  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｇｅｏｓｃｉｅｎｃｅ  ａｎｄ  Ｒｅｍｏｔｅ  Ｓｅｎｓｉｎｇ  Ｓｙｍｐｏｓｉｕｍ，  ２００１．
【００１３】
【非特許文献３】
Ｃ．Ｈ．Ｔｅｈ，  Ｒ．Ｔ．Ｃｈｉｎ．  Ｏｎ  ｔｈｅ  Ｄｅｔｅｃｔｉｏｎ  ｏｆ  Ｄｏｍｉｎａｎｔ  Ｐｏｉｎｔｓ  ｏｎ  Ｄｉｇｉｔａｌ  Ｃｕｒｖｅｓ．  −ＩＥＥＥ  Ｔｒ．ＰＡＭＩ，  １９８９，  ｖ．１１，  Ｎ０．８，  ｐ．８５９−８７２．
【００１４】
【発明が解決しようとする課題】
上記のように、従来の技術では、直線を求める際に最小二乗法を使うことで、元となるエッジ点と得られた輪郭とのずれを小さくすることができるが、単にずれを小さくしようとすると輪郭を多数の線分から構成せねばならず、頂点数が増加し、輪郭のデータ量が増加するという問題があり、ずれの量と頂点数のバランスをとるように、エッジ点の集合を適当に分割する方法が必要となる。
【００１５】
しかし、輪郭を形成するエッジ点の数が多い場合、エッジ点の列を複数に分割する方法の数は非常に多数となり、すべてについて輪郭を生成して比較すると非常に時間がかかることが問題となり、これを解決するため、非特許文献２に記載された、エッジ点を分類し、集合を分割する方法を用いると、ノイズの影響によってグループが非常に細かく分割されてしまい、輪郭の頂点数が多くなりすぎる可能性がある。さらに、分割の候補を複数生成した場合に、輪郭を選択する方針が明確でない。
【００１６】
一方、動的輪郭法は、抽出する対象物の輪郭線が滑らかな曲線であることが想定されている。そのため、少数の頂点から成る線分の集合として輪郭線を獲得する場合には向いていない。また、輪郭線の曲がり具合を用いて頂点を選択する方法では、ノイズによるわずかな突起などに影響されやすく、十分に頂点を削減することは難しい。
【００１７】
本発明は、上記従来技術の問題点を解決するためになされたものであり、エッジ点の集合から、少数の頂点によって表される輪郭形状を、少ない処理で獲得することができる輪郭線分抽出方法、および輪郭線分抽出装置を提供することが課題である。
【００１８】
【課題を解決するための手段】
上記の課題を解決するため、本発明は、画像中の輪郭に含まれる画素列から、線分列として輪郭を抽出する方法であって、画素列を分割して得られる画素列集合を、分割を変えて複数列挙する手順と、該列挙された画素列集合に対して評価値を算出する手順と、該評価値に基づいて該列挙された画素列集合を選択する手順と、該選択された画素列集合から輪郭を構成する線分列を生成する手順と、を備えることを特徴とする輪郭線分抽出方法を、その解決の手段とする。
【００１９】
あるいは、上記の輪郭線分抽出方法において、評価値を算出する手順では、画素列集合に対して、該画素列集合から生成される線分列と、該画素列集合に含まれる画素列とのずれを算出する手順と、該ずれに基づいて該画素列集合の評価値を算出する手順と、を備えることを特徴とする輪郭線分抽出方法を、その解決の手段とする。
【００２０】
あるいは、上記の輪郭線分抽出方法において、評価値を算出する手順では、画素列集合に対して、該画素列集合から生成される線分列の頂点数を算出する手順と、該頂点数に基づいて該画素列集合の評価値を算出する手順と、を備えることを特徴とする輪郭線分抽出方法を、その解決の手段とする。
【００２１】
あるいは、上記の輪郭線分抽出方法において、画素列集合を、分割を変えて複数列挙する手順では、画素列集合のなかで隣り合う画素列を一つの画素列に併合する（まとめる）ことで画素列集合を生成する手順と、該生成された画素列集合を列挙する手順と、を備えることを特徴とする輪郭線分抽出方法を、その解決の手段とする。
【００２２】
あるいは、上記の輪郭線分抽出方法において、画素列集合を生成する手順では、画素列集合のなかで隣り合う画素列を併合して生成される画素列集合に対し、評価値を算出する手順と、該評価値に基づいて併合する画素列のペアを選択する手順と、を備えることを特徴とする輪郭線分抽出方法を、その解決の手段とする。
【００２３】
あるいは、画像中の輪郭に含まれる画素列から、線分列として輪郭を抽出する装置であって、画素列を分割して得られる画素列集合を、分割を変えて複数列挙する手段と、該列挙された画素列集合に対して評価値を算出する手段と、該評価値に基づいて該列挙された画素列集合を選択する手段と、該選択された画素列集合から輪郭を構成する線分列を生成する手段と、を備えることを特徴とする輪郭線分抽出装置を、その解決の手段とする。
【００２４】
あるいは、上記の輪郭線分抽出装置において、評価値を算出する手段では、画素列集合に対して、該画素列集合から生成される線分列と、該画素列集合に含まれる画素列とのずれを算出する手段と、該ずれに基づいて該画素列集合の評価値を算出する手段と、を備えることを特徴とする輪郭線分抽出装置を、その解決の手段とする。
【００２５】
あるいは、上記の輪郭線分抽出装置において、評価値を算出する手段では、画素列集合に対して、該画素列集合から生成される線分列の頂点数を算出する手段と、該頂点数に基づいて該画素列集合の評価値を算出する手段と、を備えることを特徴とする輪郭線分抽出装置を、その解決の手段とする。
【００２６】
あるいは、上記の輪郭線分抽出装置において、画素列集合を、分割を変えて複数列挙する手段では、画素列集合のなかで隣り合う画素列を一つの画素列に併合する（まとめる）ことで画素列集合を生成する手段と、該生成された画素列集合を列挙する手段と、を備えることを特徴とする輪郭線分抽出装置を、その解決の手段とする。
【００２７】
あるいは、上記の輪郭線分抽出装置において、画素列集合を生成する手段では、画素列集合のなかで隣り合う画素列を併合して生成される画素列集合に対し、評価値を算出する手段と、該評価値に基づいて併合する画素列のペアを選択する手段と、を備えることを特徴とする輪郭線分抽出装置を、その解決の手段とする。
【００２８】
あるいは、上記の輪郭線分抽出方法における手順を、コンピュータに実行させるためのプログラムとしたことを特徴とする輪郭線分抽出プログラムを、その解決の手段とする。
【００２９】
あるいは、上記の輪郭線分抽出方法における手順を、コンピュータに実行させるためのプログラムとし、該プログラムを、該コンピュータが読み取りできる記録媒体に記録したことを特徴とする輪郭線分抽出プログラムを記録した記録媒体を、その解決の手段とする。
【００３０】
本発明では、エッジ点集合を十分に小さく分割するとともに、分割されたそれぞれの集合である画素列から隣り合う画素列の組を順次併合し、画素列集合を順次生成することにより、生成される輪郭の数をエッジ点の数より少なくし、かつ、評価値の高い輪郭のみを生成して、少ない処理と処理時間で、少数の頂点によって表される最適な輪郭形状を獲得する。
【００３１】
【発明の実施の形態】
以下、本発明の実施の形態について図を用いて詳細に説明する。
【００３２】
本発明の一実施形態による構成を図１に示す。本発明は、エッジ抽出装置１と出力装置１０６の間に、輪郭生成機構１０２、併合ペア選択機構１０３、輪郭選択機構１０４、輪郭評価機構１０５、を備えて構成される。
【００３３】
本実施形態では、エッジ抽出装置１により、既存の技術を使って、対象物を撮影した画像から、エッジ点の集合が既に抽出されているものとし、そのエッジ点の集合から、輪郭を線分の集合として得る方法の一例を説明する。
【００３４】
輪郭生成機構１０２は、最初に各エッジ点の集合が直線上に乗っていると見なせるまで、エッジ点集合を十分に小さく分割する。分割されたそれぞれの集合を画素列と呼び、画素列をすべて集めたものを画素列集合と呼ぶ。輪郭生成機構１０２は隣り合う画素列の組を順次併合し、画素列集合を順次生成する。併合する画素列の組は次に述べる併合ペア選択機構１０３によって決定する。このような方法を用いることで、生成される輪郭の数はエッジ点の数より少なくでき、かつ、評価値の高い輪郭のみを生成することができるため、少ない処理で最適な輪郭の候補を列挙することができる。
【００３５】
併合ペア選択機構１０３は、画素列集合を入力とし、輪郭評価機構１０５が出力する評価値を元にして、併合すべき画素列のペアを決定する。併合ペア選択機構１０３は、隣り合う画素列を併合し、その結果得られる輪郭に対して輪郭評価機構１０５により評価値を算出する。この処理を、すべての隣り合う画素列の組に対して行い、評価が一番高かった組を併合すべきペアとして出力する。
【００３６】
輪郭評価機構１０５は、入力された画素列集合に対して評価値を算出する。輪郭のエッジ点からのずれＳが小さいほど、あるいは、輪郭の頂点数Ｋが少ないほど、あるいは、Ｓが小さいほどおよびＫが少ないほど、望ましい輪郭であるとして、高い評価を出力するものとする。輪郭は、Ｓが小さければ、観測された画素値の情報を反映した輪郭であるといえる。また、Ｋが小さければ、保存するデータ量が少なく済む。
【００３７】
輪郭選択機構１０４は、輪郭生成機構１０２が生成し列挙したすべての画素列集合を評価の手段で評価し、その評価が最も高いものを選択の手段により選択し、選択された画素列集合から輪郭の生成手段により輪郭を生成して出力装置１０６に出力する。
【００３８】
以上の工夫により、データ量が少なく、かつ、画像情報を十分に反映した輪郭形状を、少ない処理時間で抽出することができる。
【００３９】
続いて、上記実施形態の詳細を説明する。始めに、輪郭評価機構１０５の処理の流れを図２に示す。
【００４０】
輪郭評価機構１０５は、画素列集合を入力として受け取り、輪郭の評価値を算出するために、輪郭に対するずれＳと、輪郭の頂点数Ｋを算出する。まず、各集合に対して、最小二乗法で直線を求める。次に各集合に含まれる点と求めた直線との距離の分散を求め、すべての画素列について分散の平均値をとってＳとする。一方、Ｋは、画素列の数とする。輪郭の評価値として、ｃをＳとＫの重みパラメータとして、Ｓ＋ｃ×Ｋを計算し、出力する。
【００４１】
上述したように、輪郭は、ＳおよびＫのどちらも、低い値の方が望ましいので、本例での評価値Ｓ＋ｃ×Ｋは、低い値ほど望ましい輪郭であることを示す、ものとする。
【００４２】
なお、評価値の関数は上記の形に限定するものではなく、Ｓ×Ｓ＋ｃ×Ｋ×Ｋや、Ｓのみの関数、あるいはＫのみの関数などであっても良い。
【００４３】
７つの画素列をもつ画素列集合に対して、評価値を算出する例として、処理の例を図３に示す。各画素列に対して、最小二乗法で直線を求め、分散の平均値を２．５と算出している。また、重みパラメータｃを０．５に設定する。頂点数が７なので、２．５＋０．５×７＝６と評価値を算出する。得られた画像が鮮明でエッジ点にノイズが乗っていない場合、ｃを小さく設定することで、多少頂点数が多くなっても画像から得られたエッジ点に忠実な輪郭を得ることができる。
【００４４】
輪郭生成機構１０２の処理の流れを図４に示す。
【００４５】
輪郭生成機構１０２は、対象物を撮影した画像から得られたエッジ点の集合を入力として受け取る。画像の場合、画素が格子状に並んでいるので、一つの画素から隣り合う画素に対し、８つの方向に分類することができる（図５）。エッジ点は連続した画素の列として輪郭線を構成しているため、方向が変わったところでエッジ集合を分割し、初期の画素列を得ることができる（図６）。初期の画素列は非常に数が多くなる場合が多いが、各集合に含まれるエッジ点は直線上に並んでいる。
【００４６】
輪郭生成機構１０２は、画素列のうちから、併合ペア選択機構１０３の出力に従って、画素列のペアを選択し、併合する。併合した結果、得られた新しい画素列のセットＢｉを保存し、この処理を画素列の数が３個未満になるまで繰り返す。最終的に得られた、画素列のセットをすべて（Ｂ１，Ｂ２，Ｂ３，…，Ｂｎ）を出力する。図７に、１０個の画素列を含む画素列集合Ｂ１から、併合ペア選択機構１０３の出力に従って、併合処理を行う例を示す。
【００４７】
なお、画素列生成の処理の停止条件は、本例のように画素列の数で決める他に、画素列を生成する毎に評価値を算出し、事前に設定した閾値との比較を行って処理を停止する、という方法も考えられる。
【００４８】
併合ペア選択機構１０３の処理の流れを図８に示す。
【００４９】
併合ペア選択機構１０３は、エッジ点の画素列を入力とする。隣接している画素列のペアしか、画素列を併合することができないため、隣接しているペアに対してのみ評価値を算出する。この工夫により処理時間を短縮できる。なお、画素列｛Ａ１，…，Ａｎ｝は順に並んで輪郭を形成しているので、Ａ１とＡｎも隣接しており、Ａ１とＡｎについても併合すべきペアの候補として評価を行う。
【００５０】
併合ペア選択機構１０３は、各隣接ペアＡｉ，Ａｉ＋１に対して、そのペアをマージしたときの画素列のセットを生成し、輪郭評価機構１０５に基づいて評価値を算出し、評価値の一番高いペアを出力する。
【００５１】
処理の例を図９に示す。入力された画素列集合Ｂについて、まずＡ１とＡ２を併合した場合の輪郭について評価値Ｅ１を算出する。評価値の算出は、実際には輪郭評価機構１０５で行われ、１２．５という値を得る。次に、Ａ２とＡ３を併合した場合の輪郭について評価値Ｅ２を算出し、１３．３を得る。以下順にＥ３，…，Ｅ７まで値を算出する。その結果、最小となるのはＥ１であり、よって、Ａ１とＡ２を併合すべきペアとして選択する。このような選択方法により、輪郭生成機構１０２では、評価が高い輪郭が生成されるようになる。
【００５２】
輪郭選択機構１０４の処理の流れを図１０に示す。
【００５３】
輪郭選択機構１０４は、輪郭生成機構１０２が生成し列挙したすべての画素列集合を入力とする。これらの各画素列集合に対して、評価の手段により評価値を算出し、選択の手段によりその評価が最も高い画素列集合Ｂｊを見つける（図１１）。ここでの評価は輪郭評価機構１０５と同様に行う。Ｂｊが画素列｛Ａ１，…，Ａｋ｝から構成されるとすると、輪郭の生成手段は、各Ａｉに含まれるエッジ点から最小二乗法によって直線Ｌｉを求め、ＬｉとＬｉ＋１の交点を輪郭の一つの頂点ｖｉとする。ただし、ｖｋはＬｋとＬ１との交点とする（図１２）。このようにして得られた頂点集合を、最適な輪郭として、出力装置１０６に出力する。
【００５４】
なお、輪郭選択機構１０４においては、改めて評価値を算出する代わりに、併合ペア選択機構１０３において輪郭評価機構１０５により算出した評価値を保存しておき、これを用いても構わない。このような処理を行えば、さらに処理時間を短縮することが可能となる。
【００５５】
［応用分野］
本発明は、例えば以下のような利用が考えられる。特に建物や工業用部品は直線で構成される輪郭を持つことが多いと考えられ、本発明の適用が適している。
【００５６】
・広域を写した航空写真や、上空から計測したレーザープロファイラのデータから、多数の建物の輪郭形状を実用的な時間で獲得し、地図を自動作成することが考えられる。
【００５７】
例えば、一つの建物の周囲長が５０ｍであるとすると、平均的な航空写真の解像度１０ｃｍ／画素を用いて、５００点のエッジから輪郭が構成される。１点が８ビットのグレースケールで表されているとすると、エッジデータは５００バイトになる。本発明によりこの建物の輪郭を６つの頂点から構成される多角形として抽出できたとする。各頂点のｘ座標、ｙ座標のデータをそれぞれ２バイト、２つの頂点のリンク情報に２バイト使ったとしても、６×（２＋２）＋５×２＝３４バイトにしかならない。データサイズは約１／１５となり、格段のデータ圧縮効果を挙げることができる。
【００５８】
・工業用ロボットのカメラから得られる画像に対して適用し、輪郭形状を得るまでの処理時間が短いことから、対象物を認識してから、素早く適切な対処をとることができる。
【００５９】
・監視カメラにおいて得られる画像から対象物を抽出して保存する場合、少ない頂点数で輪郭を保持できるので、長時間の監視によるデータの増加量を抑制できる。
【００６０】
なお、図１で示した装置における各部の一部もしくは全部の機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、あるいは、図２、図４、図８、図１０で示した処理の手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもなく、コンピュータでその機能を実現するためのプログラム、あるいは、コンピュータにその処理の手順を実行させるためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えば、フレキシブルディスクや、ＭＯ、ＲＯＭ、メモリカード、ＣＤ、ＤＶＤ、リムーバブルディスクなどに記録して、保存したり、配布したりすることが可能である。また、上記のプログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。このように、記録媒体やネットワークにより提供されたプログラムをコンピュータにインストールすることで、本発明が実施可能となる。
【００６１】
【発明の効果】
本発明によれば、エッジ点の集合から、少数の頂点によって表される輪郭形状を、少ない処理で獲得することができる。
【図面の簡単な説明】
【図１】本発明の一実施形態により装置構成を説明するブロック図
【図２】上記実施形態における輪郭評価機構の処理の流れ図
【図３】上記輪郭評価機構の処理の例を説明する図
【図４】上記実施形態における輪郭生成機構の処理の流れ図
【図５】画素の８方向を説明する図
【図６】初期の画素列の生成を説明する図
【図７】上記輪郭生成機構の処理の詳細を説明する図
【図８】上記実施形態における併合ペア生成機構の処理の流れ図
【図９】上記併合ペア生成機構の処理の例を説明する図
【図１０】上記実施形態における輪郭選択機構の処理の流れ図
【図１１】上記輪郭選択機構の処理の例を説明する図
【図１２】画素列集合から輪郭を生成する処理を説明する図
【図１３】一般的な２次元形状の獲得方法を説明する図
【図１４】生成される輪郭のバリエーションを説明する図
【符号の説明】
１０１…エッジ抽出装置
１０２…輪郭生成機構
１０３…併合ペア選択機構
１０４…輪郭選択機構
１０５…輪郭評価機構
１０６…出力装置
【図１】
2004234278.tif 000003
【図２】
2004234278.tif 000004
【図３】
2004234278.tif 000005
【図４】
2004234278.tif 000006
【図５】
2004234278.tif 000007
【図６】
2004234278.tif 000008
【図７】
2004234278.tif 000009
【図８】
2004234278.tif 000010
【図９】
2004234278.tif 000011
【図１０】
2004234278.tif 000012
【図１１】
2004234278.tif 000013
【図１２】
2004234278.tif 000014
【図１３】
2004234278.tif 000015
【図１４】
2004234278.tif 000016