３次元位置合わせにおける照合方法およびそのプログラム
【課題】精度よく３次元位置合わせが可能な照合方法及びプログラムを提供すること。
【解決手段】対象物の画像データから第１及び第２の３次元復元点集合、第１及び第２特徴量集合を求めるステップＳ２〜４と、
第１及び第２特徴量集合を照合して、第１及び第２の３次元復元点集合の対応点を決定するステップＳ５〜１０とを含み、
第１及び第２の３次元復元点集合がセグメントの３次元位置座標を含み、
第１及び第２特徴量集合がセグメントの頂点に関する３次元情報を含み、
ステップＳ５で、第１及び第２の３次元復元点集合のセグメントの初期照合を行い、
ステップＳ６で、第１特徴量集合の中から特徴点を選択し、
ステップＳ７で、選択された特徴点を含む調整領域を指定し、
ステップＳ８において調整領域に含まれる第１及び第２の３次元復元点集合のセグメントに関して照合の微調整を行い、
調整領域を拡大及び特徴点を選択する毎にステップＳ６〜８を実行する。
【解決手段】対象物の画像データから第１及び第２の３次元復元点集合、第１及び第２特徴量集合を求めるステップＳ２〜４と、
第１及び第２特徴量集合を照合して、第１及び第２の３次元復元点集合の対応点を決定するステップＳ５〜１０とを含み、
第１及び第２の３次元復元点集合がセグメントの３次元位置座標を含み、
第１及び第２特徴量集合がセグメントの頂点に関する３次元情報を含み、
ステップＳ５で、第１及び第２の３次元復元点集合のセグメントの初期照合を行い、
ステップＳ６で、第１特徴量集合の中から特徴点を選択し、
ステップＳ７で、選択された特徴点を含む調整領域を指定し、
ステップＳ８において調整領域に含まれる第１及び第２の３次元復元点集合のセグメントに関して照合の微調整を行い、
調整領域を拡大及び特徴点を選択する毎にステップＳ６〜８を実行する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の部分的３次元データ群を１つの３次元データに統合する場合や、モデルベース物体認識技術などに必要となる３次元位置合わせにおける照合方法およびそのプログラムに関する。
【背景技術】
【０００２】
ステレオ画像処理、レーザーレンジファインダ等によって得られた複数の部分的３次元データ群を統合して一つの形状データとする技術は３次元位置合わせ（registration, aligning）と呼ばれ、測量、遺跡調査、モデリング、工業部品検査など幅広い分野で活用されている。位置合わせ時における各データ群の相互位置関係は計測データ以外の外部情報（事前のカメラ校正等）によって与えられる。
【０００３】
位置合わせ時にはこの相互位置関係情報に含まれる誤差が問題となるが、完全に正しい位置関係が分かっていなくとも、ＩＣＰ（Iterative Closest Point）アルゴリズムによ
る微調整によって正確な位置合わせが行えることが知られており、広く使われている。
【０００４】
対象物を異なる視点から撮像した２枚の画像から、対象物の３次元データを得る方法は、下記非特許文献１及び２などに開示されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】富田文明，高橋裕信：ステレオ画像の境界線表現に基づく対応，電子情報通信学会論文誌D，vol.J71-D，No.6，pp.1074-1082，1988年6月．
【非特許文献２】角保志，富田文明：ステレオビジョンによる３次元物体の認識，電子情報通信学会論文誌D-II，vol.J80-D-II，No.5，pp.1105-1112，1997年5月．
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、ＩＣＰアルゴリズムは、基準としたデータ近傍にある他のデータ群の情報のみを用いて修正処理を行うため、相互位置関係に関する事前情報が不正確である場合、真値が得られない恐れがある。例えば図９に示す直方体のように測定対象の少なくとも１辺が他の辺に比べてかなり短い条件で、初期情報が不正確な場合には、図９のように計測データ１の直線が計測データ２の、正解とは異なる直線に接近した状態の初期情報が与えられてしまうことがある。この状況下でＩＣＰによる微調整を行っても、近傍の誤った照合データ（図９中の灰色の楕円で示す部分）の影響で正解に収束しない問題がある。
【０００７】
上記はデータ群同士の問題であるが、これ以外にも、モデルベース物体認識技術、すなわち３次元計測情報に対し、あらかじめ用意された３次元幾何モデルを照合し、そのモデルで表現される現実物体の位置姿勢を計測する技術も広い意味ではこの３次元位置合わせの範疇に入り、同様の問題が発生する。
【０００８】
また、データ群間の位置関係に関する事前情報が得られない場合、データ群全ての情報の組合せを検証して位置合わせすることは時間コストの面から現実的ではないため、通常、頂点等の特徴を利用した初期照合を行うことで計算時間の短縮を図る。しかしこの照合ではデータ特徴点が含むノイズが原因で真値からずれた照合結果が得られることがある。一例として特徴量が頂点の場合、それを構成する２直線の位置姿勢には当然ながら計測ノイズが混入し、照合結果に影響する。図９のような初期照合結果が得られることもあり、
その後に全データを用いたＩＣＰアルゴリズム等による微調整を行っても上記と同様の理由で正解には収束しない問題がある。
【０００９】
本発明は、上記した問題を解決すべく、初期の位置合わせ情報が不正確でも精度よく３次元位置合わせが可能な照合方法およびそのプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の目的は、以下の手段によって達成される。
【００１１】
即ち、本発明に係る３次元位置合わせにおける第１の照合方法は、
相互に異なる２つの視点から対象物を撮像して得られた２枚の画像データから第１の３次元復元点集合および第１特徴量集合を求める第１ステップと、
前記視点と異なり、相互に異なる２つの視点から前記対象物を撮像して得られた２枚の画像データから第２の３次元復元点集合および第２特徴量集合を求める第２ステップと、
前記第１特徴量集合を前記第２特徴量集合と照合することにより、第２の３次元復元点集合の中から前記第１の３次元復元点集合の点に対応する点を決定する第３ステップとを含み、
前記第１及び第２の３次元復元点集合が、対応する前記画像データ中の前記対象物の境界線を分割したセグメントの３次元位置座標を含み、
前記第１及び第２特徴量集合が、前記セグメントの頂点に関する３次元情報を含み、
前記第３ステップが、
前記第１及び第２の３次元復元点集合のセグメントに関して初期照合を行う第４ステップと、
前記第１特徴量集合の中から特徴点を選択する第５ステップと、
選択された前記特徴点を内部に含む領域を調整領域として指定する第６ステップと、
前記調整領域内に含まれる前記第１及び第２の３次元復元点集合のセグメントに関して、照合の微調整を行う第７ステップとから構成され、
前記調整領域を段階的に拡大する毎に前記第７ステップを実行し、
前記特徴点を選択する毎に前記第６及び第７ステップを実行する
ことを特徴としている。
【００１２】
本発明に係る３次元位置合わせにおける第２の照合方法は、上記の第１の照合方法において、
前記セグメントが、直線、円弧、又は、直線及び円弧の組み合わせで近似され、
前記頂点に関する前記３次元情報が、前記頂点の３次元位置座標および２つの３次元接線ベクトルであり、
前記照合が、前記第１特徴量集合の一部を、前記第２特徴量集合の一部に一致するように３次元座標変換する変換行列を求める処理であり、
前記第２の３次元復元点集合の中から前記第１の３次元復元点集合の点に対応する点を決定する処理が、前記変換行列を用いて前記第１の３次元復元点集合の点を３次元座標変換した結果と、前記第２の３次元復元点集合の点との一致性を評価する処理であることを特徴としている。
【００１３】
本発明に係る３次元位置合わせにおける第３の照合方法は、
相互に異なる２つの視点から対象物を撮像して得られた２枚の画像データから３次元復元点集合および特徴量集合を求める第１ステップと、
前記対象物のモデルデータ集合およびモデル特徴量集合を求める第２ステップと、
前記モデル特徴量集合を前記特徴量集合と照合することにより、前記３次元復元点集合の中から前記モデルデータ集合の点に対応する点を決定する第３ステップとを含み、
前記３次元復元点集合が、対応する前記画像データ中の前記対象物の境界線を分割した
セグメントの３次元位置座標を含み、
前記特徴量集合が、前記セグメントの頂点に関する３次元情報を含み、
前記第３ステップが、
前記３次元復元点集合のセグメントに関して前記モデル特徴量集合との初期照合を行う第４ステップと、
前記モデル特徴量集合の中から特徴点を選択する第５ステップと、
選択された前記特徴点を内部に含む領域を調整領域として指定する第６ステップと、
前記調整領域に含まれる前記モデルデータ集合及び前記３次元復元点集合のセグメントに関して、照合の微調整を行う第７ステップとから構成され、
前記調整領域を段階的に拡大する毎に前記第７ステップを実行し、
前記特徴点を選択する毎に前記第６及び第７ステップを実行する
ことを特徴としている。
【００１４】
本発明に係る３次元位置合わせにおける第４の照合方法は、上記の第３の照合方法において、
前記セグメントが、直線、円弧、又は、直線及び円弧の組み合わせで近似され、
前記頂点に関する前記３次元情報が、前記頂点の３次元位置座標および２つの３次元接線ベクトルであり、
前記照合が、前記モデル特徴量集合の一部を、前記特徴量集合の一部に一致するように３次元座標変換する変換行列を求める処理であり、
前記３次元復元点集合の中から前記モデルデータ集合の点に対応する点を決定する処理が、前記変換行列を用いて前記モデルデータ集合の点を３次元座標変換した結果と、前記３次元復元点集合の点との一致性を評価する処理であることを特徴としている。
【００１５】
本発明に係る３次元位置合わせにおける第１の照合プログラムは、
コンピュータに、
相互に異なる２つの視点から対象物を撮像して得られた２枚の画像データから第１の３次元復元点集合および第１特徴量集合を求める第１機能と、
前記視点と異なり、相互に異なる２つの視点から前記対象物を撮像して得られた２枚の画像データから第２の３次元復元点集合および第２特徴量集合を求める第２機能と、
前記第１特徴量集合を前記第２特徴量集合と照合することにより、第２の３次元復元点集合の中から前記第１の３次元復元点集合の点に対応する点を決定する第３機能とを実現させ、
前記第１及び第２の３次元復元点集合が、対応する前記画像データ中の前記対象物の境界線を分割したセグメントの３次元位置座標を含み、
前記第１及び第２特徴量集合が、前記セグメントの頂点に関する３次元情報を含み、
前記第３機能が、
前記第１及び第２の３次元復元点集合のセグメントに関して初期照合を行う第４機能と、
前記第１特徴量集合の中から特徴点を選択する第５機能と、
選択された前記特徴点を内部に含む領域を調整領域として指定する第６機能と、
前記調整領域に含まれる前記第１及び第２の３次元復元点集合のセグメントに関して、照合の微調整を行う第７機能とから構成され、
前記コンピュータに、
前記調整領域を段階的に拡大する毎に前記第７機能を実現させ、
前記特徴点を選択する毎に前記第６及び第７機能を実行させる
ことを特徴としている。
【００１６】
本発明に係る３次元位置合わせにおける第２の照合プログラムは、上記の第１の照合プログラムにおいて、
前記セグメントが、直線、円弧、又は、直線及び円弧の組み合わせで近似され、
前記頂点に関する前記３次元情報が、前記頂点の３次元位置座標および２つの３次元接線ベクトルであり、
前記照合が、前記第１特徴量集合の一部を、前記第２特徴量集合の一部に一致するように３次元座標変換する変換行列を求める処理であり、
前記第２の３次元復元点集合の中から前記第１の３次元復元点集合の点に対応する点を決定する処理が、前記変換行列を用いて前記第１の３次元復元点集合の点を３次元座標変換した結果と、前記第２の３次元復元点集合の点との一致性を評価する処理であることを特徴としている。
【００１７】
本発明に係る３次元位置合わせにおける第３の照合プログラムは、
コンピュータに、
相互に異なる２つの視点から対象物を撮像して得られた２枚の画像データから３次元復元点集合および特徴量集合を求める第１機能と、
前記対象物のモデルデータ集合およびモデル特徴量集合を求める第２機能と、
前記モデル特徴量集合を前記特徴量集合と照合することにより、前記３次元復元点集合の中から前記モデルデータ集合の点に対応する点を決定する第３機能とを実現させ、
前記３次元復元点集合が、対応する前記画像データ中の前記対象物の境界線を分割したセグメントの３次元位置座標を含み、
前記特徴量集合が、前記セグメントの頂点に関する３次元情報を含み、
前記第３機能が、
前記３次元復元点集合のセグメントに関して前記モデル特徴量集合との初期照合を行う第４機能と、
前記モデル特徴量集合の中から特徴点を選択する第５機能と、
選択された前記特徴点を内部に含む領域を調整領域として指定する第６機能と、
前記調整領域内に含まれる前記モデルデータ集合及び前記３次元復元点集合のセグメントに関して、照合の微調整を行う第７機能とから構成され、
前記コンピュータに、
前記調整領域を段階的に拡大する毎に前記第７機能を実現させ、
前記特徴点を選択する毎に前記第６及び第７機能を実現させる
ことを特徴としている。
【００１８】
本発明に係る３次元位置合わせにおける第４の照合プログラムは、上記の第３の照合プログラムにおいて、
前記セグメントが、直線、円弧、又は、直線及び円弧の組み合わせで近似され、
前記頂点に関する前記３次元情報が、前記頂点の３次元位置座標および２つの３次元接線ベクトルであり、
前記照合が、前記モデル特徴量集合の一部を、前記特徴量集合の一部に一致するように３次元座標変換する変換行列を求める処理であり、
前記３次元復元点集合の中から前記モデルデータ集合の点に対応する点を決定する処理が、前記変換行列を用いて前記モデルデータ集合の点を３次元座標変換した結果と、前記３次元復元点集合の点との一致性を評価する処理であることを特徴としている。
【発明の効果】
【００１９】
本発明によれば、初期照合後の微調整を行うときに、対象領域を段階的に大きくして照合する（伝播照合）ことによって、複数の部分的３次元データ群を１つの３次元データに統合する場合や、モデルベース物体認識技術などにおいて、ローカルミニマムなどに陥ることなく、精度よく３次元位置合わせが可能となる。
【図面の簡単な説明】
【００２０】
【図１】本発明を実施するための装置の概略構成を示すブロック図である。
【図２】本発明の実施の形態に係るに係る照合方法を示すフローチャートである。
【図３】調整領域の拡大を示す図である。
【図４】実施例の照合対象物を示す三面図である。
【図５】照合対象物を撮像した写真である。
【図６】特徴点セグメント対のみによる微調整時点での位置合わせ結果を示す図である。
【図７】従来の方法による照合結果を示す図である。
【図８】本発明による照合結果を示す図である。
【図９】照合の失敗を示す斜視図である。
【発明を実施するための形態】
【００２１】
以下、本発明に係る実施の形態を、添付した図面に基づいて説明する。
【００２２】
図１は、本発明を実施するための装置の概略構成を示すブロック図である。本装置は、コンピュータＰＣ及び撮像部Ｃ１、Ｃ２から構成されている。コンピュータＰＣは、演算処理部（以下、ＣＰＵと記す）１と、データを記録する記録部２と、記憶部（以下、メモリと記す）３と、インタフェース部４と、操作部５と、表示部６と、これら各部の間でデータ（制御信号を含む）を交換するための内部バス７とを備えて構成されている。
【００２３】
ＣＰＵ１は、記録部２から所定のプログラムをメモリ３に読み出し、メモリ３の一部をワークエリアとして使用して、所定のデータ処理を実行する。ＣＰＵ１は、実行途中の演算結果や、処理完了後の最終結果を適宜記録部２に記録する。ＣＰＵ１は、インタフェース部４を介して操作部５からの指示やデータの入力を受け、それらに応じた処理を実行する。また、ＣＰＵ１は、適宜インタフェース部４を介して、所定の情報を表示部６に表示する。例えば、操作部５からの入力を受け付けるためのグラフィカルなユーザインタフェース画像を表示部６に表示する。ＣＰＵ１は、人による操作部５の操作状況の情報を取得して、それに応じた処理を実行する。例えば、入力されたデータを記録部２に記録し、指示された処理を実行する。操作部５には、コンピュータ用のキーボードやマウスを使用することができ、表示部６には、ＣＲＴディスプレイ、液晶ディスプレイなどを使用することができる。
【００２４】
第１及び第２撮像部Ｃ１、Ｃ２は、所定の間隔で所定の位置に配置され、撮像の対象物Ｔを撮像し、撮像された画像データをコンピュータＰＣに伝送する。コンピュータＰＣでは、インタフェース部４を介して取得した各撮像部からの画像データを、区別可能に、例えば、各撮像部に対応させて異なるファイル名を付けて、記録部２に記録する。第１及び第２撮像部Ｃ１、Ｃ２からの出力信号がアナログ信号の場合、コンピュータＰＣは、ＡＤ（アナログデジタル）変換部（図示せず）を備えて、所定の時間間隔で入力されるアナログ信号をサンプリングしてデジタルデータに変換する。第１及び第２撮像部Ｃ１、Ｃ２からの出力信号がデジタルデータであれば、ＡＤ変換部は不要である。第１及び第２撮像部Ｃ１、Ｃ２は、少なくとも静止画像を撮像できる装置であればよく、ビデオ映像を撮像できる装置であってもよい。例えば、デジタルカメラ、デジタル又はアナログのビデオカメラなどを使用することができる。
【００２５】
以下、本発明の実施の形態について、図２に示したフローチャートに従って説明する。理解を容易にするために、以下では、２つの３次元復元画像の位置合わせを行う場合を説明する。即ち、２つの３次元復元画像が対象物Ｔの領域Ｔcを共通に含んでいる、即ち、
一方の３次元復元画像が、対象物Ｔの領域Ｔaと領域Ｔcとで構成され、他方の３次元復元画像が、対象物Ｔの領域Ｔbと領域Ｔcとで構成されているとする。従って、この共通する領域Ｔcを基準として２つの３次元復元画像が統合される。３つ以上の３次元復元画像の
位置合わせを行う場合も同様に行うことができる。
【００２６】
また、以下においては、特に断らない場合、ＣＰＵ１が行う処理、即ちＣＰＵ１が各部を制御して行う処理として記載する。また、第１及び第２撮像部Ｃ１、Ｃ２の内部及び外部パラメータは、予め校正実験によって求められ、記録部２に記録されているとする。
【００２７】
ステップＳ１において、初期設定を行う。初期設定は、ステップＳ２以降の処理を行うために必要な処理であり、例えば、第１及び第２撮像部Ｃ１、Ｃ２とのデータ伝送経路や制御プロトコルを確立し、第１及び第２撮像部Ｃ１、Ｃ２を制御可能とする。
【００２８】
ステップＳ２において、異なる２つの位置で第１及び第２撮像部Ｃ１、Ｃ２で対象物Ｔを撮像する。撮像された画像は、コンピュータＰＣに伝送され、所定のファイル名で記録部２に記録される。これによって、記録部２には、異なる２つの位置で撮像された２組の２枚の２次元画像データが記録される。ここでは、得られた２次元画像データをＭijで表す。ｉ、ｊはそれぞれ撮像位置を区別するため、第１及び第２撮像部Ｃ１、Ｃ２を区別するためのものである。
【００２９】
ステップＳ３において、ステップＳ２で撮像され記録部２に記録された２組の２次元画像データを読み出し、それぞれの３次元復元画像を生成する。即ち、２枚の画像Ｍ11、Ｍ12（以下ペア画像と記す）を読み出して３次元復元画像を生成し、別途２枚の画像Ｍ21、Ｍ22を読み出して３次元復元画像を生成する。ここでは、ステレオ対応による３次元復元像を求めるが、点単位（画素単位）ではなく、より大局的な「セグメント」単位で対応を求める。これによって、点単位で処理する場合よりも、探索空間をかなり狭くすることが可能である。具体的な方法は、上記非特許文献１に開示されている公知の方法を用いる。従って、以下には、本発明と直接関係する内容のみ説明する。
【００３０】
具体的には、ペア画像の各画像に対し（ａ）エッジ抽出、（ｂ）セグメント生成、及び（ｃ）各画像間でのセグメントの連結性と対応評価による３次元復元、の一連の処理を順次行う。以後、本ステップＳ３で得られたペア画像に関する３次元復元点集合をＦiで表
す。ｉは、上記したように撮像位置を区別する添え字であり、ペアを区別する添え字でもある。
【００３１】
（ａ）エッジ抽出
各画像のエッジ抽出に関しては、公知の画像処理方法を用いて行えばよい。例えば、１次微分オペレータにより画像の各点についてエッジの強さと方向を求め、エッジの細線化、しきい値処理、延長処理により、ある領域を囲む閉じたエッジ（境界線とも記す）を得る。
【００３２】
（ｂ）セグメント生成
上記の処理によって得られた２枚のエッジ画像を対象として、セグメントを生成する。セグメントとは、エッジを複数の線分（直線）に分割したものである。最初に境界線を所定の条件で仮に分割し、各セグメントを最小２乗法によって直線で近似した場合、誤差が大きいセグメントがあれば、そのセグメントの両端を結ぶ直線から最も離れた点（直線への垂線が最も大きいセグメント上の点）でセグメントを分割する。これを繰り返して、境界線を分割する点（分割点）を決定する。これによって、２枚の画像の各々に対してセグメントが生成され、セグメントを近似する直線が生成される。
【００３３】
処理結果は、境界線表現（構造データ）として記録部２に記録される。即ち、画像は複数の領域の集合によって表現される。具体的には、各領域Ｒは、その領域の外側の境界線Ｂと領域の内側の穴に対する境界線Ｈのリストによって表現され、各境界線Ｂ、Ｈはそれ
を構成するセグメントＳのリストによって表現される。領域は、それを囲む外接長方形と明るさとをその値にもつ。セグメントは、それが属する領域を右側に見るように方向づけられており、始点及び終点の座標と、そのセグメントを近似する直線の方程式とをその値にもつ。以上の記述を２枚の画像に対して行う。以下の対応処理はこの記述されたデータ構造上で行われる。
【００３４】
（ｃ）３次元復元
次に、２枚の画像で対応するセグメントを求める。同じ対象物を表すセグメントであるが、照明条件、オクルージョン、ノイズなどの影響によって、対応を決定するのは容易ではない。従って、まず、領域単位で粗く対応を求める。１対の領域が対応する必要条件として、領域の明るさの差が一定値（例えば２５６レベルの画像の場合、２５レベル）以下であること、且つ、領域内にエピポーラ条件を満足する点が存在することを採用する。これは十分条件ではないので、１つの領域が多数の領域に対応する場合もある。つまり、この段階では、その境界線のセグメントが対応する可能性のある領域の対をすべて求めており、次にセグメント単位で対応を求める場合に、その探索空間を減らす役割を果たしており、一種の粗密解析となる。
【００３５】
粗対応する領域の境界線を構成するセグメント間で対応の候補を求め、その対応リストを作成する。一対のセグメントが対応の候補となる条件は、エピポーラ条件を満足する対応部分が存在し、セグメントの方向（それが属する領域を右側に見るように方向づけられている）が上向きか下向きかで一致しており、方向の角度の差が一定値（例えば４５°）以内であることである。そして、対応の候補となるそれぞれのセグメント対に対して、その類似度を示す値Ｃ、Ｄを計算する。Ｃはプラスの要囚を表し、対応する２つのセグメントの短い方のセグメントの長さである。Ｄはマイナスの要因を表し、対応するセグメントの始点から終点までの視差のずれである。この段階で求められた対応の候補には、１つのセグメントが同じｙ軸（垂直方向）上で複数のセグメントに対応する多重対応も存在する。次に説明するように、セグメントの類似度とセグメントの接続関係から偽の対応を除去する。
【００３６】
次に、２枚の画像の各々について、セグメントの連結リストを作成する。２つのセグメントが連結する条件は、それぞれが属する領域の明るさの差が一定値（例えば２５レベル）以下であり、一方のセグメントの終点と他方のセグメントの始点との距離が一定値（例えば３画素）以下であることである。連続するセグメントは、原則的に、その対応も連続していなければならない。そこで、この連結リストと対応リストとを利用して、各セグメントの前後から、連続して対応するセグメントの列であるパスを、次のようにして求める。
・対応する２つのパスの両者の端点が丁度対応している場合には、それぞれの端点から接続するセグメントで対応の候補となっているセグメント対が存在すればそれらをパスに追加する。
・一方の端点が他方の中間点と対応している場合には、１つのセグメントに接続するセグメントに関して、対応候補であるセグメントが存在すれば、それをパスに追加する。
【００３７】
また、直接的には連結していない場合でも、連続性を仮定できる場合がある。例えば、１つのセグメントに２つのセグメントが対応している場合には、２つのセグメントの両端間の距離が最大となる線分を、２つのセグメントの代わりのセグメントと仮定する。また、点Ａで連続する２つのセグメントに、連続していない２つのセグメントが対応している場合がある。この場合には、連続していない２つのセグメントを延長して、点Ａを通る水平線と交わる２つの交点の距離が小さければ、延長した２つの線分（一方の端点が交点）を２つのセグメントと仮定する。但し、不必要に多くの仮のセグメントを生成しないように、仮のセグメントと実セグメントとの類似度は、Ｃ＞｜Ｄ｜の場合に限る。以下同様に
して、パスに追加するセグメントが無くなるまで、上記の処理を繰り返す。以上の処理の結果、仮のセグメントが新たに付け加えられることになる。
【００３８】
次に、パスを３次元空間上に逆射影した場合に、同一の平面を構成するセグメントをグループ化する。これは、正しいセグメントの対を得る拘束条件となるばかりでなく、出力形式として３次元の面領域の境界線を得る手続きでもある。セグメントが同一平面を構成するかどうかの検証には、次の平面拘束定理を利用する。
平面拘束定理： 標準カメラモデルにおいて、平面上の任意の図形に関して、一方のカメラ画像上の投影像と、他方のカメラ画像上の投影像とはアフィン変換可能である。
【００３９】
この定理は、透視投影により得られる画像上のセグメントであっても、同一平面上にあるセグメントの集合は、ステレオ画像間でアフィン変換可能であることを表す。これによりセグメントを直接的に３次元空間に逆射影することなく画像上で平面性を検証できる。この平面拘束定理を用いてセグメントをグループ化する過程は次のとおりである。
【００４０】
まず、対応するパスの対から任意の連続する２つの対応するセグメント対を取り出し、最小のグループ対を形成する。
【００４１】
次に、２枚の画像のそれぞれのセグメントに連続するセグメントを求め、求められた３つのセグメントの端点がすべて同一平面上にあると仮定して、最小２乗法によリ２組の連続するセグメント（各３つのセグメント）間のアフィン変換行列を求める。この３つのセグメントが得られた平面に存在するかどうかは、左右いずれかの端点をアフィン変換することにより得られた点が、他方の端点に一致するか否かで検証する。本明細書において、２つの点が一致するとは、２点間の距離が所定値以下であることを意味する。従って、それらの距離が所定値（例えば３画素）以下であれば、３つのセグメントは同一平面上にあると判断する。
【００４２】
上記で、３つのセグメントが同一平面上にあると判断された場合、再び左右それぞれのセグメントに連続するセグメントを求める。上記と同様に、４つの対応するセグメントについてアフィン変換行列を求め、対応する各端点が得られた変換行列を満たすか否かを検証する。更に、この平面拘束条件を満たす場合には、順次、連続するセグメントを加え、検証を繰り返す。
【００４３】
以上の処理の結果、平面を構成するセグメントのグループ対が得られる。しかし、１つのセグメント対（平面を構成する連続する複数のセグメント）に対して複数のグループ対が得られる場合もある。そこで、各グループ対に対してその形状の類似度を計算し、１つのセグメント対に対して最大の類似度を有する１つのグループ対を割り当てる。グループ対の類似度Ｇは、そのグループ対に含まれる各セグメント対の類似度Ｃ、Ｄの合計で与えられる。このとき、マイナス因子Ｄには、マイナス符号を付けて−Ｄとして加算する。多重対応の場合はいずれかの対応が誤りである。偽の対応となっているセグメント対は、対応する部分が少なく（Ｃが小さくなる）、始点と終点の間で視差が大きく（｜Ｄ｜は大きくなる）、また連続するセグメントも少ないので、その対を含むグループ対の類似度Ｇの値は小さくなる。そこで、類似度Ｇが最大となるグループ対を順に選び、他の対応は除去する。これによって、２枚の画像間で対応するセグメント対を特定することができる。
【００４４】
以上の処理の結果、２枚の画像で対応するセグメント対の視差から３次元空間上のセグメントの座標を求めることができる。視差は、セグメントの関数表現を用いて計算することができるのでサブピクセルの精度で得られ、セグメント上の視差はばらつきもない。例えば、２枚の画像間で対応する２つのセグメントｊの方程式を、ｘ＝ｆj(ｙ)、ｘ＝ｇj(
ｙ)とすると、２つのセグメント間の視差ｄは、ｄ＝ｆj(ｙ)−ｇj(ｙ)で計算される。実
際には、３次元セグメントは３次元の直線の方程式で表現される。
【００４５】
得られた対応セグメントの情報と視差ｄとを用い、２つのカメラ（撮像部）の配置を考慮して、３次元復元点集合Ｆiを求める。対応する画像上の２点と、それらの視差から、
３次元座標を計算する方法は、２台のカメラの光軸が、平行に配置される場合、輻輳角を有して配置される場合の何れにおいても、公知であるので詳細説明を省略する。
【００４６】
以上で得られた結果は、所定のデータ構造で記録部２に記録される。そのデータ構造は、３次元の面を表すグループＧ*の集合からなり、各グループＧ*は、その面の境界線を構成する３次元セグメントＳ*のリストの情報で構成されている。各グループＧ*は、その面の法線方向を有し、各セグメントは、始点および終点の３次元座標と、直線の方程式とを有する。
【００４７】
ステップＳ４において、ペア画像データについて特徴量の計算を行う。ここでは、２つの３次元復元画像の位置合わせ（モデル照合の場合も同様）に必要な特徴量である「頂点」の集合を求める。ここで、頂点とは、空間的に隣接する３次元セグメントに当てはめられた直線によって決まる２つのベクトルから成る、いわば仮想直線交点のことである。即ち、３次元復元点集合Ｆiに関して、隣り合う２つのセグメントに当てはめられた直線の
端点における接線（ここではセグメントを直線で近似しているので、その直線と同じ）を用いて、近傍の２接線の交点を求める。得られた交点を頂点とする。頂点の集合をＶiで
表す。また、接線ベクトル間の角度（以後、挟角と呼ぶ）を求める。
【００４８】
即ち、具体的な特徴量は、頂点の３次元位置座標、頂点における挟角、及び２法線ベクトル成分である。特徴量を求める具体的な方法には、上記非特許文献２に開示されている公知の方法を用いればよい。
【００４９】
ステップＳ５において、２つの３次元復元画像データの初期照合を行う。即ち、上記で得られた頂点集合Ｖi（ｉ＝１、２）に対して、その挟角値が近い頂点の組み合わせ（候
補番号ｊで表す）に対する４×４（４行４列）の座標変換行列Ｔjを全て求めて解の候補
群Ｃa（Ｃa＝ΣＣj）とする。
【００５０】
具体的な方法は、上記非特許文献２に開示されている公知の方法を用いる。従って、ここでは、直接関係する内容のみ説明する。
【００５１】
３次元座標ベクトルａ＝[ｘ ｙ ｚ]tから３次元座標ベクトルａ’＝[ｘ’ ｙ’ ｚ’]tへの変換は（添字ｔは転置を表す）、３×３の３次元座標の回転行列Ｒと３×１の平行移動ベクトルｔとを用いて、ｘ’＝Ｒｘ＋ｔで表される。従って、対象物Ｔを異なる位置で撮像して得られた２つの３次元復元画像中の対象物Ｔの相互の位置姿勢関係は、一方の３次元復元画像データ中の３次元構造を他方の３次元復元画像データ中の対応する３次元構造に一致するように移動させる４×４座標変換行列Ｔで記述できる。
【００５２】
【数１】
【００５３】
上記したように初期照合は、２つの頂点集合Ｖ1、Ｖ2を照合し、変換行列Ｔを算出する
処理である。但し、２つの頂点集合Ｖ1、Ｖ2との間で、頂点の正しい対応を前もって知ることはできないので、可能性が高いと推定される全ての組み合わせを対応候補とする。
【００５４】
頂点集合Ｖ1中の頂点ＶMを、頂点集合Ｖ2中の頂点ＶDに一致するよう移動させることを考える。頂点ＶM及びＶDの３次元位置座標の関係から行列Ｔの平行移動ベクトルｔが決まる。各頂点を構成している２つの３次元ベクトルの方向から回転移動行列Ｒが決まる。頂点を構成する２つのベクトルのなす角θが大きく異なる組み合わせについては、正しい対応である可能性が低いと考えられるので、候補から除外する。すなわち、ＶM(ｉ)（ｉ＝
１，・・・，ｍ）とＶD(ｊ)（ｊ＝１，・・・，ｎ）について、｜θM(ｉ)−θD(ｊ)｜＜
θthを満足する全ての組み合わせＡ(ｉ，ｊ)を対応の候補として、前述の座標変換行列Ｔjに対応する行列Ｔij(０)（括弧内の０は、後述する微調整前の状態を意味する）を算出
する。ここで、ｍ、ｎはそれぞれ、２つの頂点集合Ｖ1、Ｖ2中に存在する頂点数である。しきい値θthは、例えば経験的に決定すればよい。
【００５５】
次に、ステップＳ６〜Ｓ１０を繰り返し実行し、微調整を行う。
【００５６】
ステップＳ６において、一方の３次元復元画像データに関して１つ特徴点を指定する。ここでは、上記で求めた頂点集合Ｖ1中の１つの頂点を指定するとする。
【００５７】
ステップＳ７において、微調整を行う領域を指定する。例えば、半径ｒ0を指定し、ス
テップＳ６で指定された特徴点（頂点）を中心とする半径ｒ0の球形領域を微調整領域と
する。例えば、図３において、明るさの異なる複数の円のうち、最も小さい円で表された領域（球形領域）を微調整領域とする。図３の２つの直方体は、２つの３次元復元画像中に含まれる対象物Ｔの共通領域Ｔcを模式的に示している（異なる領域Ｔa、Ｔbは省略）
。図３は、図９と同様に初期照合の結果が間違っている状況を示している。
【００５８】
ステップＳ８において、ステップＳ８で指定された微調整領域内の点を対象として微調整を実行する。微調整は、２つの３次元復元点集合Ｆ1、Ｆ2間で点を照合する処理であり、Ａ(ｉ，ｊ)の妥当性を判別すると同時に、行列Ｔij(０)に含まれる誤差を小さくする。頂点集合Ｖ1、Ｖ2に関する初期照合によって求めた座標変換行列Ｔij(０)によって移動させ、例えば頂点集合Ｖ1の頂点に対応する画像データ点（３次元復元点集合Ｆ2中の点）を探索し、最小２乗法により座標変換行列を更新するという処理を繰り返す。具体的な処理は公知の方法を用いる（例えば、上記非特許文献２の「３．２微調整」の項参照）。
【００５９】
具体的には、次のサブステップ１〜７を行う。
【００６０】
サブステップ１： 対応点探索のための空間として、データ点列の２次元座標をプロットした画像を用意する。
【００６１】
サブステップ２： Ｐ(ｋ)をＴij(０)によってＰ’(ｋ)に移動させる。
Ｐ(ｋ)の３次元座標Ｐ(ｋ)と、その法線方向単位ベクトルＮ(ｋ)は、それぞれ、
Ｐ’(ｋ)＝Ｒij(０)Ｐ(ｋ)＋ｔij(０)
Ｎ’(ｋ)＝Ｒij(０)Ｎ(ｋ)
に移動する。ここで、Ｐ(ｋ)、Ｎ(ｋ)は３×１ベクトルである。
【００６２】
サブステップ３： Ｐ’(ｋ)のうち、
ｃｏｓ-1（Ｓ’t(ｋ)・Ｎ’t(ｋ)／｜Ｓ’(ｋ)｜）＞π／２
を満足するものをＰ(ｎ)（ｎ＝１，・・・，ｐ’；ｐ’≦ｐ）とする。ここで、Ｓ’(ｋ)は、Ｐ’(ｋ)に対応する観測方向ベクトルであり、Ｃをステレオカメラシステムの観測位置を表す３×１ベクトルとすると、
Ｓ’(ｋ)＝Ｐ’(ｋ)＋ｔij(０)−Ｃ
である。即ち、Ｐ(ｎ)はＴij(０)によって一方の３次元復元画像データの頂点を移動した後に、他方の３次元復元画像中に観測可能な頂点を表している。
【００６３】
サブステップ４： Ｐ(ｎ)の３次元座標Ｐ(ｎ)を画像座標[ｃｏｌn，ｒｏｗn]に投影し、観測可能な頂点に対応する、他方の３次元復元画像中のデータ点を探索する。Ｐ(ｎ)の法線と垂直方向に画像上をトレースし、一定の距離範囲内にデータ点Ｄ(ｌ)（ｌ＝１，・・・，ｑ）が存在すれば、それをＰ(ｎ)の対応点とする。ここでは、ｑはデータ点数である。
【００６４】
サブステップ５： Ｐ(ｎ)とＤ(ｌ)の組み合わせβ(ｎ，ｌ)について、Ｐ(ｎ)を、Ｄ(
ｌ)の３次元座標Ｄ(ｌ)に一致するように移動させる最適な変換行列Ｔ’ijを、
Ｊ＝Σβ｜Ｒ’ijＰ(ｎ)＋ｔij’−Ｄ(ｌ)｜2
を最小にする最小２乗法によって算出する。Σβはβ(ｎ，ｌ)に関する和を意味する。
【００６５】
サブステップ６： サブステップ４における対応点探索の平均２乗誤差、即ち、
ε2＝Σβ｛（ｃｏｌn−ｃｏｌl）2＋（ｃｏｒn−ｒｏｗl）2｝／ｒ
がしきい値以下になるまで、
Ｔ(ｕ)＝Ｔ’Ｔ（ｕ−１）
としてサブステップ２〜５の処理を繰り返す。ここでｒは、β(ｎ，ｌ)の総数、すなわち、対応点探索によって見つけられた対応点の数であり、ｒ≦ｐである。
観測可能な頂点数に対する対応点数の割合ｒ／ｐが小さい、または、一定回数上記の処理を繰り返してもε2が収束しならば、対応候補Ａ(ｉ，ｊ)は誤りとして破棄する。
【００６６】
サブステップ７： すべての対応候補Ａ(ｉ，ｊ)について上記の処理を行い、ｒが最大で、対応の誤差、すなわち、
ε2＝Σβ｜（Ｒij(ｕ)Ｐ(ｎ)＋ｔij(ｕ)−Ｄ(ｌ)｜2／ｒ
が最小であるＴij(ｕ)を認識結果として選ぶ。
【００６７】
なお、初期照合は、局所的な幾何特徴を用いた照合であるため、Ｔij(０)の算出に用いた頂点位置の近傍にある復元点を除き、対応点探索が有効であるほどの認識精度を得られないことがある。このため、微調整の処理は、次に示すように２段階に適用することが望ましい。
・初期微調整：初期照合に用いた頂点を構成するセグメント上の復元点のみを使って対応誤差を大まかに調整する。
・主微調整：全ての復元点を使って更に精度を向上させる。
【００６８】
ステップＳ９において、最大の微調整領域について微調整を完了したか否かを判断し、完了していなければステップＳ７に戻り、微調整範囲を広くする。例えば、半径ｒ0を所
定値Δｒだけ大きくし、ｒ0＋Δｒにする。例えば、図３において、明るさの異なる複数
の円で示したように、最も小さい円で表される領域から段階的に大きい円で表される領域（球形領域）を微調整領域とする。このように、予め設定された最大の微調整領域について微調整が完了するまで、ステップＳ７〜ステップＳ９の処理を繰り返す。
【００６９】
最大の微調整領域について微調整が完了すれば、ステップＳ１０において、頂点集合Ｖ1中の全特徴点について微調整が完了したか否かを判断する。完了していなければステッ
プＳ６に戻り、既に指定された特徴点以外の特徴点を指定する。このように、全特徴点について微調整が完了するまで、ステップＳ６〜Ｓ１０の処理を繰り返す。
【００７０】
以上によって、従来、正確な位置姿勢計測に失敗していた条件下でも、誤った相互関係
でＩＣＰによる微調整が行われることなく、最終的に正確な２つの３次元復元画像データの統合が可能となる。
【００７１】
以上、実施の形態を用いて本発明を説明したが、本発明は上記の実施の形態に限定されず、種々に変更して実施することができる。
【００７２】
例えば、上記では特徴点を指定して、微調整領域を段階的に拡大して処理した後、別の特徴点に関して同様に処理する場合を説明したが、特定の大きさの微調整領域を指定して各特徴点に関して処理を行った後、微調整領域を拡大して各特徴点に関して処理を行ってもよい。
【００７３】
また、上記では特徴点を中心とする半径で微調整領域を指定し、半径を段階的に所定値だけ大きくする場合を説明したが、これに限定されない。微調整領域を段階的に大きく指定できればよく、特徴点を内部に含む任意形状の立体として指定すればよい。領域の拡大方法も任意であり、例えば、相似形で拡大しても、異なる形状で拡大しても、一定の比率で拡大しても、異なる比率で拡大してもよい。各段階で微調整領域を特定する情報を、全て予め記録部に記録しておいてもよい。例えば、領域の拡大パラメータを、数値列として記録しておいてもよい。
【００７４】
また、上記では計測された３次元復元画像データを統合する場合の位置合わせについて説明したが、本発明は、モデルベース物体認識技術、すなわち３次元計測情報に対し、あらかじめ用意された３次元幾何モデルを照合し、そのモデルで表現される現実物体の位置姿勢を計測する場合にも、同様に適用可能である。この場合にはモデル側の幾何構造は事前に分かっているため、その頂点ごとに領域の拡大パラメータを数値列として記録しておいてもよい。また、２次元画像の統合処理にも適用可能である。さらには、時間軸を考慮した４次元画像に関しても適用可能である。なお、微調整領域の次元は、処理対象データの次元に応じて適切に定めればよい。
【００７５】
また、上記では、セグメントを直線で近似する場合を説明したが、セグメントを直線または円弧で近似してもよい。その場合、頂点に加えて、円弧（例えば、円弧の半径、円弧の中心から両端点への方向ベクトルと法線ベクトルなど）を特徴量とすることができる。また、セグメントを、直線と円弧の組み合わせ（複数の円弧のみの組み合わせを含む）で近似してもよい。その場合、頂点に加えて、セグメントの両端に当てはめられた円弧のみを、そのセグメントの特徴としてもよい。
【００７６】
セグメントが円弧で近似されている場合（直線と円弧の組み合わせで近似されている場合を含む）、ステップＳ４における頂点の算出には、円弧の両端における接線を使用する。円弧の接線は、円弧の中心から両端点への方向ベクトルから求めることができる。また、ステップＳ５において、頂点に関する処理と同様に、モデルと撮像画像データの円弧の組み合わせについても対応候補を求める。円弧の両端点の３次元座標によって平行移動ベクトルｔを決定することができ、円弧の中心から両端点への方向ベクトルと法線ベクトルによって回転行列Ｒを決定することができる。また、半径が大きく異なる円弧の組み合わせについては候補から除外するのが望ましい。頂点と円弧それぞれによって算出された対応候補を合わせたＡ(ｉ，ｊ)およびＴij(０)が、最終的な初期照合の結果とする。
【００７７】
また、上記では、コンピュータを用い、ソフトウェアプログラムによって実施する場合を説明したが、これに限定されない。上記の機能を、複数の機能に分割し、その一部または全てを１つまたは複数のハードウェア（例えば、専用の半導体チップ（ＡＳＩＣ）及びその周辺回路）によって実現してもよい。例えば、複数のハードウェアで構成する場合、各ペア画像データを用いたステレオ対応による３次元復元像および照合に必要な特徴量を
求める３次元復元計算部と、２つの３次元復元画像データの特徴量の類似性から対応する点を照合する照合調整部とで構成してもよい。
【実施例】
【００７８】
以下に実施例を示し、本発明の有効性をより明らかにする。
【００７９】
２台のカメラを用いて、特定の対象物を撮像し、得られた画像データとモデルデータとの照合を、図２に示したフローチャートに従って行った。ここでは、２つの３次元復元画像データの一方をモデルデータとして処理を行ったが、２つの３次元復元画像データを対象とする場合と同様の処理である。
【００８０】
対象物（実物およびモデル）として、図４の三面図に示すように直方体の胴体中央付近にくびれ部のある形状を使用した。
【００８１】
図４の対象物を２つのカメラで撮像して、図５に示す左右２枚の画像データを得た。そして、図５の画像データを用いて、図２のステップＳ３〜Ｓ５の処理を実施した。
【００８２】
図６は、頂点を形成するセグメント対のみ（画像上部）で照合を行う初期微調整後、つまり本発明の照合（伝播照合）過程に進入前の段階での位置合わせ結果を示す。点線は対象物のデータを表し、実線は画像から得られたエッジを表す。伝播照合の有無に関わらずこの状態を通過することになるが、図６から分かるように計測データの精度不足（不適正な露光時間／ピント、カメラ校正の不良、撮像素子の持つ画像ノイズ等が原因として考えられる）で不正確な位置合わせ状態となっている。
【００８３】
図７は従来の方法による位置合わせ過程の最終結果であるが、画像下側領域でモデル底面とデータ上面とで照合が進み、正しい位置合わせが行われなかったことが分かる。
【００８４】
図８は伝播照合を組み込んだ本発明による位置合わせ過程の最終結果であるが、本発明による手法により正しい位置合わせが行われたことが分かる。
【００８５】
以上のように、従来の方法では、初期照合結果が間違っていた場合、その後に全データを用いたＩＣＰアルゴリズム等による微調整を行っても正解には収束しないのに対して、本発明によれば、初期照合結果が間違っていた場合でも、正解に収束させることができる。従来の方法で正解に収束しない問題は、対象物の大きさや形状によらず、セグメントが小さい場合に発生し易い。従って、本発明は、対象物の大きさや形状によらず、セグメントが小さい場合に特に有効である。
【符号の説明】
【００８６】
１ 演算処理部（ＣＰＵ）
２ 記録部
３ 記憶部（メモリ）
４ インタフェース部
５ 操作部
６ 表示部
７ 内部バス
ＰＣ コンピュータ
Ｃ１ 第１撮像部
Ｃ２ 第２撮像部
Ｔ 撮像対象物
【技術分野】
【０００１】
本発明は、複数の部分的３次元データ群を１つの３次元データに統合する場合や、モデルベース物体認識技術などに必要となる３次元位置合わせにおける照合方法およびそのプログラムに関する。
【背景技術】
【０００２】
ステレオ画像処理、レーザーレンジファインダ等によって得られた複数の部分的３次元データ群を統合して一つの形状データとする技術は３次元位置合わせ（registration, aligning）と呼ばれ、測量、遺跡調査、モデリング、工業部品検査など幅広い分野で活用されている。位置合わせ時における各データ群の相互位置関係は計測データ以外の外部情報（事前のカメラ校正等）によって与えられる。
【０００３】
位置合わせ時にはこの相互位置関係情報に含まれる誤差が問題となるが、完全に正しい位置関係が分かっていなくとも、ＩＣＰ（Iterative Closest Point）アルゴリズムによ
る微調整によって正確な位置合わせが行えることが知られており、広く使われている。
【０００４】
対象物を異なる視点から撮像した２枚の画像から、対象物の３次元データを得る方法は、下記非特許文献１及び２などに開示されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】富田文明，高橋裕信：ステレオ画像の境界線表現に基づく対応，電子情報通信学会論文誌D，vol.J71-D，No.6，pp.1074-1082，1988年6月．
【非特許文献２】角保志，富田文明：ステレオビジョンによる３次元物体の認識，電子情報通信学会論文誌D-II，vol.J80-D-II，No.5，pp.1105-1112，1997年5月．
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、ＩＣＰアルゴリズムは、基準としたデータ近傍にある他のデータ群の情報のみを用いて修正処理を行うため、相互位置関係に関する事前情報が不正確である場合、真値が得られない恐れがある。例えば図９に示す直方体のように測定対象の少なくとも１辺が他の辺に比べてかなり短い条件で、初期情報が不正確な場合には、図９のように計測データ１の直線が計測データ２の、正解とは異なる直線に接近した状態の初期情報が与えられてしまうことがある。この状況下でＩＣＰによる微調整を行っても、近傍の誤った照合データ（図９中の灰色の楕円で示す部分）の影響で正解に収束しない問題がある。
【０００７】
上記はデータ群同士の問題であるが、これ以外にも、モデルベース物体認識技術、すなわち３次元計測情報に対し、あらかじめ用意された３次元幾何モデルを照合し、そのモデルで表現される現実物体の位置姿勢を計測する技術も広い意味ではこの３次元位置合わせの範疇に入り、同様の問題が発生する。
【０００８】
また、データ群間の位置関係に関する事前情報が得られない場合、データ群全ての情報の組合せを検証して位置合わせすることは時間コストの面から現実的ではないため、通常、頂点等の特徴を利用した初期照合を行うことで計算時間の短縮を図る。しかしこの照合ではデータ特徴点が含むノイズが原因で真値からずれた照合結果が得られることがある。一例として特徴量が頂点の場合、それを構成する２直線の位置姿勢には当然ながら計測ノイズが混入し、照合結果に影響する。図９のような初期照合結果が得られることもあり、
その後に全データを用いたＩＣＰアルゴリズム等による微調整を行っても上記と同様の理由で正解には収束しない問題がある。
【０００９】
本発明は、上記した問題を解決すべく、初期の位置合わせ情報が不正確でも精度よく３次元位置合わせが可能な照合方法およびそのプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の目的は、以下の手段によって達成される。
【００１１】
即ち、本発明に係る３次元位置合わせにおける第１の照合方法は、
相互に異なる２つの視点から対象物を撮像して得られた２枚の画像データから第１の３次元復元点集合および第１特徴量集合を求める第１ステップと、
前記視点と異なり、相互に異なる２つの視点から前記対象物を撮像して得られた２枚の画像データから第２の３次元復元点集合および第２特徴量集合を求める第２ステップと、
前記第１特徴量集合を前記第２特徴量集合と照合することにより、第２の３次元復元点集合の中から前記第１の３次元復元点集合の点に対応する点を決定する第３ステップとを含み、
前記第１及び第２の３次元復元点集合が、対応する前記画像データ中の前記対象物の境界線を分割したセグメントの３次元位置座標を含み、
前記第１及び第２特徴量集合が、前記セグメントの頂点に関する３次元情報を含み、
前記第３ステップが、
前記第１及び第２の３次元復元点集合のセグメントに関して初期照合を行う第４ステップと、
前記第１特徴量集合の中から特徴点を選択する第５ステップと、
選択された前記特徴点を内部に含む領域を調整領域として指定する第６ステップと、
前記調整領域内に含まれる前記第１及び第２の３次元復元点集合のセグメントに関して、照合の微調整を行う第７ステップとから構成され、
前記調整領域を段階的に拡大する毎に前記第７ステップを実行し、
前記特徴点を選択する毎に前記第６及び第７ステップを実行する
ことを特徴としている。
【００１２】
本発明に係る３次元位置合わせにおける第２の照合方法は、上記の第１の照合方法において、
前記セグメントが、直線、円弧、又は、直線及び円弧の組み合わせで近似され、
前記頂点に関する前記３次元情報が、前記頂点の３次元位置座標および２つの３次元接線ベクトルであり、
前記照合が、前記第１特徴量集合の一部を、前記第２特徴量集合の一部に一致するように３次元座標変換する変換行列を求める処理であり、
前記第２の３次元復元点集合の中から前記第１の３次元復元点集合の点に対応する点を決定する処理が、前記変換行列を用いて前記第１の３次元復元点集合の点を３次元座標変換した結果と、前記第２の３次元復元点集合の点との一致性を評価する処理であることを特徴としている。
【００１３】
本発明に係る３次元位置合わせにおける第３の照合方法は、
相互に異なる２つの視点から対象物を撮像して得られた２枚の画像データから３次元復元点集合および特徴量集合を求める第１ステップと、
前記対象物のモデルデータ集合およびモデル特徴量集合を求める第２ステップと、
前記モデル特徴量集合を前記特徴量集合と照合することにより、前記３次元復元点集合の中から前記モデルデータ集合の点に対応する点を決定する第３ステップとを含み、
前記３次元復元点集合が、対応する前記画像データ中の前記対象物の境界線を分割した
セグメントの３次元位置座標を含み、
前記特徴量集合が、前記セグメントの頂点に関する３次元情報を含み、
前記第３ステップが、
前記３次元復元点集合のセグメントに関して前記モデル特徴量集合との初期照合を行う第４ステップと、
前記モデル特徴量集合の中から特徴点を選択する第５ステップと、
選択された前記特徴点を内部に含む領域を調整領域として指定する第６ステップと、
前記調整領域に含まれる前記モデルデータ集合及び前記３次元復元点集合のセグメントに関して、照合の微調整を行う第７ステップとから構成され、
前記調整領域を段階的に拡大する毎に前記第７ステップを実行し、
前記特徴点を選択する毎に前記第６及び第７ステップを実行する
ことを特徴としている。
【００１４】
本発明に係る３次元位置合わせにおける第４の照合方法は、上記の第３の照合方法において、
前記セグメントが、直線、円弧、又は、直線及び円弧の組み合わせで近似され、
前記頂点に関する前記３次元情報が、前記頂点の３次元位置座標および２つの３次元接線ベクトルであり、
前記照合が、前記モデル特徴量集合の一部を、前記特徴量集合の一部に一致するように３次元座標変換する変換行列を求める処理であり、
前記３次元復元点集合の中から前記モデルデータ集合の点に対応する点を決定する処理が、前記変換行列を用いて前記モデルデータ集合の点を３次元座標変換した結果と、前記３次元復元点集合の点との一致性を評価する処理であることを特徴としている。
【００１５】
本発明に係る３次元位置合わせにおける第１の照合プログラムは、
コンピュータに、
相互に異なる２つの視点から対象物を撮像して得られた２枚の画像データから第１の３次元復元点集合および第１特徴量集合を求める第１機能と、
前記視点と異なり、相互に異なる２つの視点から前記対象物を撮像して得られた２枚の画像データから第２の３次元復元点集合および第２特徴量集合を求める第２機能と、
前記第１特徴量集合を前記第２特徴量集合と照合することにより、第２の３次元復元点集合の中から前記第１の３次元復元点集合の点に対応する点を決定する第３機能とを実現させ、
前記第１及び第２の３次元復元点集合が、対応する前記画像データ中の前記対象物の境界線を分割したセグメントの３次元位置座標を含み、
前記第１及び第２特徴量集合が、前記セグメントの頂点に関する３次元情報を含み、
前記第３機能が、
前記第１及び第２の３次元復元点集合のセグメントに関して初期照合を行う第４機能と、
前記第１特徴量集合の中から特徴点を選択する第５機能と、
選択された前記特徴点を内部に含む領域を調整領域として指定する第６機能と、
前記調整領域に含まれる前記第１及び第２の３次元復元点集合のセグメントに関して、照合の微調整を行う第７機能とから構成され、
前記コンピュータに、
前記調整領域を段階的に拡大する毎に前記第７機能を実現させ、
前記特徴点を選択する毎に前記第６及び第７機能を実行させる
ことを特徴としている。
【００１６】
本発明に係る３次元位置合わせにおける第２の照合プログラムは、上記の第１の照合プログラムにおいて、
前記セグメントが、直線、円弧、又は、直線及び円弧の組み合わせで近似され、
前記頂点に関する前記３次元情報が、前記頂点の３次元位置座標および２つの３次元接線ベクトルであり、
前記照合が、前記第１特徴量集合の一部を、前記第２特徴量集合の一部に一致するように３次元座標変換する変換行列を求める処理であり、
前記第２の３次元復元点集合の中から前記第１の３次元復元点集合の点に対応する点を決定する処理が、前記変換行列を用いて前記第１の３次元復元点集合の点を３次元座標変換した結果と、前記第２の３次元復元点集合の点との一致性を評価する処理であることを特徴としている。
【００１７】
本発明に係る３次元位置合わせにおける第３の照合プログラムは、
コンピュータに、
相互に異なる２つの視点から対象物を撮像して得られた２枚の画像データから３次元復元点集合および特徴量集合を求める第１機能と、
前記対象物のモデルデータ集合およびモデル特徴量集合を求める第２機能と、
前記モデル特徴量集合を前記特徴量集合と照合することにより、前記３次元復元点集合の中から前記モデルデータ集合の点に対応する点を決定する第３機能とを実現させ、
前記３次元復元点集合が、対応する前記画像データ中の前記対象物の境界線を分割したセグメントの３次元位置座標を含み、
前記特徴量集合が、前記セグメントの頂点に関する３次元情報を含み、
前記第３機能が、
前記３次元復元点集合のセグメントに関して前記モデル特徴量集合との初期照合を行う第４機能と、
前記モデル特徴量集合の中から特徴点を選択する第５機能と、
選択された前記特徴点を内部に含む領域を調整領域として指定する第６機能と、
前記調整領域内に含まれる前記モデルデータ集合及び前記３次元復元点集合のセグメントに関して、照合の微調整を行う第７機能とから構成され、
前記コンピュータに、
前記調整領域を段階的に拡大する毎に前記第７機能を実現させ、
前記特徴点を選択する毎に前記第６及び第７機能を実現させる
ことを特徴としている。
【００１８】
本発明に係る３次元位置合わせにおける第４の照合プログラムは、上記の第３の照合プログラムにおいて、
前記セグメントが、直線、円弧、又は、直線及び円弧の組み合わせで近似され、
前記頂点に関する前記３次元情報が、前記頂点の３次元位置座標および２つの３次元接線ベクトルであり、
前記照合が、前記モデル特徴量集合の一部を、前記特徴量集合の一部に一致するように３次元座標変換する変換行列を求める処理であり、
前記３次元復元点集合の中から前記モデルデータ集合の点に対応する点を決定する処理が、前記変換行列を用いて前記モデルデータ集合の点を３次元座標変換した結果と、前記３次元復元点集合の点との一致性を評価する処理であることを特徴としている。
【発明の効果】
【００１９】
本発明によれば、初期照合後の微調整を行うときに、対象領域を段階的に大きくして照合する（伝播照合）ことによって、複数の部分的３次元データ群を１つの３次元データに統合する場合や、モデルベース物体認識技術などにおいて、ローカルミニマムなどに陥ることなく、精度よく３次元位置合わせが可能となる。
【図面の簡単な説明】
【００２０】
【図１】本発明を実施するための装置の概略構成を示すブロック図である。
【図２】本発明の実施の形態に係るに係る照合方法を示すフローチャートである。
【図３】調整領域の拡大を示す図である。
【図４】実施例の照合対象物を示す三面図である。
【図５】照合対象物を撮像した写真である。
【図６】特徴点セグメント対のみによる微調整時点での位置合わせ結果を示す図である。
【図７】従来の方法による照合結果を示す図である。
【図８】本発明による照合結果を示す図である。
【図９】照合の失敗を示す斜視図である。
【発明を実施するための形態】
【００２１】
以下、本発明に係る実施の形態を、添付した図面に基づいて説明する。
【００２２】
図１は、本発明を実施するための装置の概略構成を示すブロック図である。本装置は、コンピュータＰＣ及び撮像部Ｃ１、Ｃ２から構成されている。コンピュータＰＣは、演算処理部（以下、ＣＰＵと記す）１と、データを記録する記録部２と、記憶部（以下、メモリと記す）３と、インタフェース部４と、操作部５と、表示部６と、これら各部の間でデータ（制御信号を含む）を交換するための内部バス７とを備えて構成されている。
【００２３】
ＣＰＵ１は、記録部２から所定のプログラムをメモリ３に読み出し、メモリ３の一部をワークエリアとして使用して、所定のデータ処理を実行する。ＣＰＵ１は、実行途中の演算結果や、処理完了後の最終結果を適宜記録部２に記録する。ＣＰＵ１は、インタフェース部４を介して操作部５からの指示やデータの入力を受け、それらに応じた処理を実行する。また、ＣＰＵ１は、適宜インタフェース部４を介して、所定の情報を表示部６に表示する。例えば、操作部５からの入力を受け付けるためのグラフィカルなユーザインタフェース画像を表示部６に表示する。ＣＰＵ１は、人による操作部５の操作状況の情報を取得して、それに応じた処理を実行する。例えば、入力されたデータを記録部２に記録し、指示された処理を実行する。操作部５には、コンピュータ用のキーボードやマウスを使用することができ、表示部６には、ＣＲＴディスプレイ、液晶ディスプレイなどを使用することができる。
【００２４】
第１及び第２撮像部Ｃ１、Ｃ２は、所定の間隔で所定の位置に配置され、撮像の対象物Ｔを撮像し、撮像された画像データをコンピュータＰＣに伝送する。コンピュータＰＣでは、インタフェース部４を介して取得した各撮像部からの画像データを、区別可能に、例えば、各撮像部に対応させて異なるファイル名を付けて、記録部２に記録する。第１及び第２撮像部Ｃ１、Ｃ２からの出力信号がアナログ信号の場合、コンピュータＰＣは、ＡＤ（アナログデジタル）変換部（図示せず）を備えて、所定の時間間隔で入力されるアナログ信号をサンプリングしてデジタルデータに変換する。第１及び第２撮像部Ｃ１、Ｃ２からの出力信号がデジタルデータであれば、ＡＤ変換部は不要である。第１及び第２撮像部Ｃ１、Ｃ２は、少なくとも静止画像を撮像できる装置であればよく、ビデオ映像を撮像できる装置であってもよい。例えば、デジタルカメラ、デジタル又はアナログのビデオカメラなどを使用することができる。
【００２５】
以下、本発明の実施の形態について、図２に示したフローチャートに従って説明する。理解を容易にするために、以下では、２つの３次元復元画像の位置合わせを行う場合を説明する。即ち、２つの３次元復元画像が対象物Ｔの領域Ｔcを共通に含んでいる、即ち、
一方の３次元復元画像が、対象物Ｔの領域Ｔaと領域Ｔcとで構成され、他方の３次元復元画像が、対象物Ｔの領域Ｔbと領域Ｔcとで構成されているとする。従って、この共通する領域Ｔcを基準として２つの３次元復元画像が統合される。３つ以上の３次元復元画像の
位置合わせを行う場合も同様に行うことができる。
【００２６】
また、以下においては、特に断らない場合、ＣＰＵ１が行う処理、即ちＣＰＵ１が各部を制御して行う処理として記載する。また、第１及び第２撮像部Ｃ１、Ｃ２の内部及び外部パラメータは、予め校正実験によって求められ、記録部２に記録されているとする。
【００２７】
ステップＳ１において、初期設定を行う。初期設定は、ステップＳ２以降の処理を行うために必要な処理であり、例えば、第１及び第２撮像部Ｃ１、Ｃ２とのデータ伝送経路や制御プロトコルを確立し、第１及び第２撮像部Ｃ１、Ｃ２を制御可能とする。
【００２８】
ステップＳ２において、異なる２つの位置で第１及び第２撮像部Ｃ１、Ｃ２で対象物Ｔを撮像する。撮像された画像は、コンピュータＰＣに伝送され、所定のファイル名で記録部２に記録される。これによって、記録部２には、異なる２つの位置で撮像された２組の２枚の２次元画像データが記録される。ここでは、得られた２次元画像データをＭijで表す。ｉ、ｊはそれぞれ撮像位置を区別するため、第１及び第２撮像部Ｃ１、Ｃ２を区別するためのものである。
【００２９】
ステップＳ３において、ステップＳ２で撮像され記録部２に記録された２組の２次元画像データを読み出し、それぞれの３次元復元画像を生成する。即ち、２枚の画像Ｍ11、Ｍ12（以下ペア画像と記す）を読み出して３次元復元画像を生成し、別途２枚の画像Ｍ21、Ｍ22を読み出して３次元復元画像を生成する。ここでは、ステレオ対応による３次元復元像を求めるが、点単位（画素単位）ではなく、より大局的な「セグメント」単位で対応を求める。これによって、点単位で処理する場合よりも、探索空間をかなり狭くすることが可能である。具体的な方法は、上記非特許文献１に開示されている公知の方法を用いる。従って、以下には、本発明と直接関係する内容のみ説明する。
【００３０】
具体的には、ペア画像の各画像に対し（ａ）エッジ抽出、（ｂ）セグメント生成、及び（ｃ）各画像間でのセグメントの連結性と対応評価による３次元復元、の一連の処理を順次行う。以後、本ステップＳ３で得られたペア画像に関する３次元復元点集合をＦiで表
す。ｉは、上記したように撮像位置を区別する添え字であり、ペアを区別する添え字でもある。
【００３１】
（ａ）エッジ抽出
各画像のエッジ抽出に関しては、公知の画像処理方法を用いて行えばよい。例えば、１次微分オペレータにより画像の各点についてエッジの強さと方向を求め、エッジの細線化、しきい値処理、延長処理により、ある領域を囲む閉じたエッジ（境界線とも記す）を得る。
【００３２】
（ｂ）セグメント生成
上記の処理によって得られた２枚のエッジ画像を対象として、セグメントを生成する。セグメントとは、エッジを複数の線分（直線）に分割したものである。最初に境界線を所定の条件で仮に分割し、各セグメントを最小２乗法によって直線で近似した場合、誤差が大きいセグメントがあれば、そのセグメントの両端を結ぶ直線から最も離れた点（直線への垂線が最も大きいセグメント上の点）でセグメントを分割する。これを繰り返して、境界線を分割する点（分割点）を決定する。これによって、２枚の画像の各々に対してセグメントが生成され、セグメントを近似する直線が生成される。
【００３３】
処理結果は、境界線表現（構造データ）として記録部２に記録される。即ち、画像は複数の領域の集合によって表現される。具体的には、各領域Ｒは、その領域の外側の境界線Ｂと領域の内側の穴に対する境界線Ｈのリストによって表現され、各境界線Ｂ、Ｈはそれ
を構成するセグメントＳのリストによって表現される。領域は、それを囲む外接長方形と明るさとをその値にもつ。セグメントは、それが属する領域を右側に見るように方向づけられており、始点及び終点の座標と、そのセグメントを近似する直線の方程式とをその値にもつ。以上の記述を２枚の画像に対して行う。以下の対応処理はこの記述されたデータ構造上で行われる。
【００３４】
（ｃ）３次元復元
次に、２枚の画像で対応するセグメントを求める。同じ対象物を表すセグメントであるが、照明条件、オクルージョン、ノイズなどの影響によって、対応を決定するのは容易ではない。従って、まず、領域単位で粗く対応を求める。１対の領域が対応する必要条件として、領域の明るさの差が一定値（例えば２５６レベルの画像の場合、２５レベル）以下であること、且つ、領域内にエピポーラ条件を満足する点が存在することを採用する。これは十分条件ではないので、１つの領域が多数の領域に対応する場合もある。つまり、この段階では、その境界線のセグメントが対応する可能性のある領域の対をすべて求めており、次にセグメント単位で対応を求める場合に、その探索空間を減らす役割を果たしており、一種の粗密解析となる。
【００３５】
粗対応する領域の境界線を構成するセグメント間で対応の候補を求め、その対応リストを作成する。一対のセグメントが対応の候補となる条件は、エピポーラ条件を満足する対応部分が存在し、セグメントの方向（それが属する領域を右側に見るように方向づけられている）が上向きか下向きかで一致しており、方向の角度の差が一定値（例えば４５°）以内であることである。そして、対応の候補となるそれぞれのセグメント対に対して、その類似度を示す値Ｃ、Ｄを計算する。Ｃはプラスの要囚を表し、対応する２つのセグメントの短い方のセグメントの長さである。Ｄはマイナスの要因を表し、対応するセグメントの始点から終点までの視差のずれである。この段階で求められた対応の候補には、１つのセグメントが同じｙ軸（垂直方向）上で複数のセグメントに対応する多重対応も存在する。次に説明するように、セグメントの類似度とセグメントの接続関係から偽の対応を除去する。
【００３６】
次に、２枚の画像の各々について、セグメントの連結リストを作成する。２つのセグメントが連結する条件は、それぞれが属する領域の明るさの差が一定値（例えば２５レベル）以下であり、一方のセグメントの終点と他方のセグメントの始点との距離が一定値（例えば３画素）以下であることである。連続するセグメントは、原則的に、その対応も連続していなければならない。そこで、この連結リストと対応リストとを利用して、各セグメントの前後から、連続して対応するセグメントの列であるパスを、次のようにして求める。
・対応する２つのパスの両者の端点が丁度対応している場合には、それぞれの端点から接続するセグメントで対応の候補となっているセグメント対が存在すればそれらをパスに追加する。
・一方の端点が他方の中間点と対応している場合には、１つのセグメントに接続するセグメントに関して、対応候補であるセグメントが存在すれば、それをパスに追加する。
【００３７】
また、直接的には連結していない場合でも、連続性を仮定できる場合がある。例えば、１つのセグメントに２つのセグメントが対応している場合には、２つのセグメントの両端間の距離が最大となる線分を、２つのセグメントの代わりのセグメントと仮定する。また、点Ａで連続する２つのセグメントに、連続していない２つのセグメントが対応している場合がある。この場合には、連続していない２つのセグメントを延長して、点Ａを通る水平線と交わる２つの交点の距離が小さければ、延長した２つの線分（一方の端点が交点）を２つのセグメントと仮定する。但し、不必要に多くの仮のセグメントを生成しないように、仮のセグメントと実セグメントとの類似度は、Ｃ＞｜Ｄ｜の場合に限る。以下同様に
して、パスに追加するセグメントが無くなるまで、上記の処理を繰り返す。以上の処理の結果、仮のセグメントが新たに付け加えられることになる。
【００３８】
次に、パスを３次元空間上に逆射影した場合に、同一の平面を構成するセグメントをグループ化する。これは、正しいセグメントの対を得る拘束条件となるばかりでなく、出力形式として３次元の面領域の境界線を得る手続きでもある。セグメントが同一平面を構成するかどうかの検証には、次の平面拘束定理を利用する。
平面拘束定理： 標準カメラモデルにおいて、平面上の任意の図形に関して、一方のカメラ画像上の投影像と、他方のカメラ画像上の投影像とはアフィン変換可能である。
【００３９】
この定理は、透視投影により得られる画像上のセグメントであっても、同一平面上にあるセグメントの集合は、ステレオ画像間でアフィン変換可能であることを表す。これによりセグメントを直接的に３次元空間に逆射影することなく画像上で平面性を検証できる。この平面拘束定理を用いてセグメントをグループ化する過程は次のとおりである。
【００４０】
まず、対応するパスの対から任意の連続する２つの対応するセグメント対を取り出し、最小のグループ対を形成する。
【００４１】
次に、２枚の画像のそれぞれのセグメントに連続するセグメントを求め、求められた３つのセグメントの端点がすべて同一平面上にあると仮定して、最小２乗法によリ２組の連続するセグメント（各３つのセグメント）間のアフィン変換行列を求める。この３つのセグメントが得られた平面に存在するかどうかは、左右いずれかの端点をアフィン変換することにより得られた点が、他方の端点に一致するか否かで検証する。本明細書において、２つの点が一致するとは、２点間の距離が所定値以下であることを意味する。従って、それらの距離が所定値（例えば３画素）以下であれば、３つのセグメントは同一平面上にあると判断する。
【００４２】
上記で、３つのセグメントが同一平面上にあると判断された場合、再び左右それぞれのセグメントに連続するセグメントを求める。上記と同様に、４つの対応するセグメントについてアフィン変換行列を求め、対応する各端点が得られた変換行列を満たすか否かを検証する。更に、この平面拘束条件を満たす場合には、順次、連続するセグメントを加え、検証を繰り返す。
【００４３】
以上の処理の結果、平面を構成するセグメントのグループ対が得られる。しかし、１つのセグメント対（平面を構成する連続する複数のセグメント）に対して複数のグループ対が得られる場合もある。そこで、各グループ対に対してその形状の類似度を計算し、１つのセグメント対に対して最大の類似度を有する１つのグループ対を割り当てる。グループ対の類似度Ｇは、そのグループ対に含まれる各セグメント対の類似度Ｃ、Ｄの合計で与えられる。このとき、マイナス因子Ｄには、マイナス符号を付けて−Ｄとして加算する。多重対応の場合はいずれかの対応が誤りである。偽の対応となっているセグメント対は、対応する部分が少なく（Ｃが小さくなる）、始点と終点の間で視差が大きく（｜Ｄ｜は大きくなる）、また連続するセグメントも少ないので、その対を含むグループ対の類似度Ｇの値は小さくなる。そこで、類似度Ｇが最大となるグループ対を順に選び、他の対応は除去する。これによって、２枚の画像間で対応するセグメント対を特定することができる。
【００４４】
以上の処理の結果、２枚の画像で対応するセグメント対の視差から３次元空間上のセグメントの座標を求めることができる。視差は、セグメントの関数表現を用いて計算することができるのでサブピクセルの精度で得られ、セグメント上の視差はばらつきもない。例えば、２枚の画像間で対応する２つのセグメントｊの方程式を、ｘ＝ｆj(ｙ)、ｘ＝ｇj(
ｙ)とすると、２つのセグメント間の視差ｄは、ｄ＝ｆj(ｙ)−ｇj(ｙ)で計算される。実
際には、３次元セグメントは３次元の直線の方程式で表現される。
【００４５】
得られた対応セグメントの情報と視差ｄとを用い、２つのカメラ（撮像部）の配置を考慮して、３次元復元点集合Ｆiを求める。対応する画像上の２点と、それらの視差から、
３次元座標を計算する方法は、２台のカメラの光軸が、平行に配置される場合、輻輳角を有して配置される場合の何れにおいても、公知であるので詳細説明を省略する。
【００４６】
以上で得られた結果は、所定のデータ構造で記録部２に記録される。そのデータ構造は、３次元の面を表すグループＧ*の集合からなり、各グループＧ*は、その面の境界線を構成する３次元セグメントＳ*のリストの情報で構成されている。各グループＧ*は、その面の法線方向を有し、各セグメントは、始点および終点の３次元座標と、直線の方程式とを有する。
【００４７】
ステップＳ４において、ペア画像データについて特徴量の計算を行う。ここでは、２つの３次元復元画像の位置合わせ（モデル照合の場合も同様）に必要な特徴量である「頂点」の集合を求める。ここで、頂点とは、空間的に隣接する３次元セグメントに当てはめられた直線によって決まる２つのベクトルから成る、いわば仮想直線交点のことである。即ち、３次元復元点集合Ｆiに関して、隣り合う２つのセグメントに当てはめられた直線の
端点における接線（ここではセグメントを直線で近似しているので、その直線と同じ）を用いて、近傍の２接線の交点を求める。得られた交点を頂点とする。頂点の集合をＶiで
表す。また、接線ベクトル間の角度（以後、挟角と呼ぶ）を求める。
【００４８】
即ち、具体的な特徴量は、頂点の３次元位置座標、頂点における挟角、及び２法線ベクトル成分である。特徴量を求める具体的な方法には、上記非特許文献２に開示されている公知の方法を用いればよい。
【００４９】
ステップＳ５において、２つの３次元復元画像データの初期照合を行う。即ち、上記で得られた頂点集合Ｖi（ｉ＝１、２）に対して、その挟角値が近い頂点の組み合わせ（候
補番号ｊで表す）に対する４×４（４行４列）の座標変換行列Ｔjを全て求めて解の候補
群Ｃa（Ｃa＝ΣＣj）とする。
【００５０】
具体的な方法は、上記非特許文献２に開示されている公知の方法を用いる。従って、ここでは、直接関係する内容のみ説明する。
【００５１】
３次元座標ベクトルａ＝[ｘ ｙ ｚ]tから３次元座標ベクトルａ’＝[ｘ’ ｙ’ ｚ’]tへの変換は（添字ｔは転置を表す）、３×３の３次元座標の回転行列Ｒと３×１の平行移動ベクトルｔとを用いて、ｘ’＝Ｒｘ＋ｔで表される。従って、対象物Ｔを異なる位置で撮像して得られた２つの３次元復元画像中の対象物Ｔの相互の位置姿勢関係は、一方の３次元復元画像データ中の３次元構造を他方の３次元復元画像データ中の対応する３次元構造に一致するように移動させる４×４座標変換行列Ｔで記述できる。
【００５２】
【数１】
【００５３】
上記したように初期照合は、２つの頂点集合Ｖ1、Ｖ2を照合し、変換行列Ｔを算出する
処理である。但し、２つの頂点集合Ｖ1、Ｖ2との間で、頂点の正しい対応を前もって知ることはできないので、可能性が高いと推定される全ての組み合わせを対応候補とする。
【００５４】
頂点集合Ｖ1中の頂点ＶMを、頂点集合Ｖ2中の頂点ＶDに一致するよう移動させることを考える。頂点ＶM及びＶDの３次元位置座標の関係から行列Ｔの平行移動ベクトルｔが決まる。各頂点を構成している２つの３次元ベクトルの方向から回転移動行列Ｒが決まる。頂点を構成する２つのベクトルのなす角θが大きく異なる組み合わせについては、正しい対応である可能性が低いと考えられるので、候補から除外する。すなわち、ＶM(ｉ)（ｉ＝
１，・・・，ｍ）とＶD(ｊ)（ｊ＝１，・・・，ｎ）について、｜θM(ｉ)−θD(ｊ)｜＜
θthを満足する全ての組み合わせＡ(ｉ，ｊ)を対応の候補として、前述の座標変換行列Ｔjに対応する行列Ｔij(０)（括弧内の０は、後述する微調整前の状態を意味する）を算出
する。ここで、ｍ、ｎはそれぞれ、２つの頂点集合Ｖ1、Ｖ2中に存在する頂点数である。しきい値θthは、例えば経験的に決定すればよい。
【００５５】
次に、ステップＳ６〜Ｓ１０を繰り返し実行し、微調整を行う。
【００５６】
ステップＳ６において、一方の３次元復元画像データに関して１つ特徴点を指定する。ここでは、上記で求めた頂点集合Ｖ1中の１つの頂点を指定するとする。
【００５７】
ステップＳ７において、微調整を行う領域を指定する。例えば、半径ｒ0を指定し、ス
テップＳ６で指定された特徴点（頂点）を中心とする半径ｒ0の球形領域を微調整領域と
する。例えば、図３において、明るさの異なる複数の円のうち、最も小さい円で表された領域（球形領域）を微調整領域とする。図３の２つの直方体は、２つの３次元復元画像中に含まれる対象物Ｔの共通領域Ｔcを模式的に示している（異なる領域Ｔa、Ｔbは省略）
。図３は、図９と同様に初期照合の結果が間違っている状況を示している。
【００５８】
ステップＳ８において、ステップＳ８で指定された微調整領域内の点を対象として微調整を実行する。微調整は、２つの３次元復元点集合Ｆ1、Ｆ2間で点を照合する処理であり、Ａ(ｉ，ｊ)の妥当性を判別すると同時に、行列Ｔij(０)に含まれる誤差を小さくする。頂点集合Ｖ1、Ｖ2に関する初期照合によって求めた座標変換行列Ｔij(０)によって移動させ、例えば頂点集合Ｖ1の頂点に対応する画像データ点（３次元復元点集合Ｆ2中の点）を探索し、最小２乗法により座標変換行列を更新するという処理を繰り返す。具体的な処理は公知の方法を用いる（例えば、上記非特許文献２の「３．２微調整」の項参照）。
【００５９】
具体的には、次のサブステップ１〜７を行う。
【００６０】
サブステップ１： 対応点探索のための空間として、データ点列の２次元座標をプロットした画像を用意する。
【００６１】
サブステップ２： Ｐ(ｋ)をＴij(０)によってＰ’(ｋ)に移動させる。
Ｐ(ｋ)の３次元座標Ｐ(ｋ)と、その法線方向単位ベクトルＮ(ｋ)は、それぞれ、
Ｐ’(ｋ)＝Ｒij(０)Ｐ(ｋ)＋ｔij(０)
Ｎ’(ｋ)＝Ｒij(０)Ｎ(ｋ)
に移動する。ここで、Ｐ(ｋ)、Ｎ(ｋ)は３×１ベクトルである。
【００６２】
サブステップ３： Ｐ’(ｋ)のうち、
ｃｏｓ-1（Ｓ’t(ｋ)・Ｎ’t(ｋ)／｜Ｓ’(ｋ)｜）＞π／２
を満足するものをＰ(ｎ)（ｎ＝１，・・・，ｐ’；ｐ’≦ｐ）とする。ここで、Ｓ’(ｋ)は、Ｐ’(ｋ)に対応する観測方向ベクトルであり、Ｃをステレオカメラシステムの観測位置を表す３×１ベクトルとすると、
Ｓ’(ｋ)＝Ｐ’(ｋ)＋ｔij(０)−Ｃ
である。即ち、Ｐ(ｎ)はＴij(０)によって一方の３次元復元画像データの頂点を移動した後に、他方の３次元復元画像中に観測可能な頂点を表している。
【００６３】
サブステップ４： Ｐ(ｎ)の３次元座標Ｐ(ｎ)を画像座標[ｃｏｌn，ｒｏｗn]に投影し、観測可能な頂点に対応する、他方の３次元復元画像中のデータ点を探索する。Ｐ(ｎ)の法線と垂直方向に画像上をトレースし、一定の距離範囲内にデータ点Ｄ(ｌ)（ｌ＝１，・・・，ｑ）が存在すれば、それをＰ(ｎ)の対応点とする。ここでは、ｑはデータ点数である。
【００６４】
サブステップ５： Ｐ(ｎ)とＤ(ｌ)の組み合わせβ(ｎ，ｌ)について、Ｐ(ｎ)を、Ｄ(
ｌ)の３次元座標Ｄ(ｌ)に一致するように移動させる最適な変換行列Ｔ’ijを、
Ｊ＝Σβ｜Ｒ’ijＰ(ｎ)＋ｔij’−Ｄ(ｌ)｜2
を最小にする最小２乗法によって算出する。Σβはβ(ｎ，ｌ)に関する和を意味する。
【００６５】
サブステップ６： サブステップ４における対応点探索の平均２乗誤差、即ち、
ε2＝Σβ｛（ｃｏｌn−ｃｏｌl）2＋（ｃｏｒn−ｒｏｗl）2｝／ｒ
がしきい値以下になるまで、
Ｔ(ｕ)＝Ｔ’Ｔ（ｕ−１）
としてサブステップ２〜５の処理を繰り返す。ここでｒは、β(ｎ，ｌ)の総数、すなわち、対応点探索によって見つけられた対応点の数であり、ｒ≦ｐである。
観測可能な頂点数に対する対応点数の割合ｒ／ｐが小さい、または、一定回数上記の処理を繰り返してもε2が収束しならば、対応候補Ａ(ｉ，ｊ)は誤りとして破棄する。
【００６６】
サブステップ７： すべての対応候補Ａ(ｉ，ｊ)について上記の処理を行い、ｒが最大で、対応の誤差、すなわち、
ε2＝Σβ｜（Ｒij(ｕ)Ｐ(ｎ)＋ｔij(ｕ)−Ｄ(ｌ)｜2／ｒ
が最小であるＴij(ｕ)を認識結果として選ぶ。
【００６７】
なお、初期照合は、局所的な幾何特徴を用いた照合であるため、Ｔij(０)の算出に用いた頂点位置の近傍にある復元点を除き、対応点探索が有効であるほどの認識精度を得られないことがある。このため、微調整の処理は、次に示すように２段階に適用することが望ましい。
・初期微調整：初期照合に用いた頂点を構成するセグメント上の復元点のみを使って対応誤差を大まかに調整する。
・主微調整：全ての復元点を使って更に精度を向上させる。
【００６８】
ステップＳ９において、最大の微調整領域について微調整を完了したか否かを判断し、完了していなければステップＳ７に戻り、微調整範囲を広くする。例えば、半径ｒ0を所
定値Δｒだけ大きくし、ｒ0＋Δｒにする。例えば、図３において、明るさの異なる複数
の円で示したように、最も小さい円で表される領域から段階的に大きい円で表される領域（球形領域）を微調整領域とする。このように、予め設定された最大の微調整領域について微調整が完了するまで、ステップＳ７〜ステップＳ９の処理を繰り返す。
【００６９】
最大の微調整領域について微調整が完了すれば、ステップＳ１０において、頂点集合Ｖ1中の全特徴点について微調整が完了したか否かを判断する。完了していなければステッ
プＳ６に戻り、既に指定された特徴点以外の特徴点を指定する。このように、全特徴点について微調整が完了するまで、ステップＳ６〜Ｓ１０の処理を繰り返す。
【００７０】
以上によって、従来、正確な位置姿勢計測に失敗していた条件下でも、誤った相互関係
でＩＣＰによる微調整が行われることなく、最終的に正確な２つの３次元復元画像データの統合が可能となる。
【００７１】
以上、実施の形態を用いて本発明を説明したが、本発明は上記の実施の形態に限定されず、種々に変更して実施することができる。
【００７２】
例えば、上記では特徴点を指定して、微調整領域を段階的に拡大して処理した後、別の特徴点に関して同様に処理する場合を説明したが、特定の大きさの微調整領域を指定して各特徴点に関して処理を行った後、微調整領域を拡大して各特徴点に関して処理を行ってもよい。
【００７３】
また、上記では特徴点を中心とする半径で微調整領域を指定し、半径を段階的に所定値だけ大きくする場合を説明したが、これに限定されない。微調整領域を段階的に大きく指定できればよく、特徴点を内部に含む任意形状の立体として指定すればよい。領域の拡大方法も任意であり、例えば、相似形で拡大しても、異なる形状で拡大しても、一定の比率で拡大しても、異なる比率で拡大してもよい。各段階で微調整領域を特定する情報を、全て予め記録部に記録しておいてもよい。例えば、領域の拡大パラメータを、数値列として記録しておいてもよい。
【００７４】
また、上記では計測された３次元復元画像データを統合する場合の位置合わせについて説明したが、本発明は、モデルベース物体認識技術、すなわち３次元計測情報に対し、あらかじめ用意された３次元幾何モデルを照合し、そのモデルで表現される現実物体の位置姿勢を計測する場合にも、同様に適用可能である。この場合にはモデル側の幾何構造は事前に分かっているため、その頂点ごとに領域の拡大パラメータを数値列として記録しておいてもよい。また、２次元画像の統合処理にも適用可能である。さらには、時間軸を考慮した４次元画像に関しても適用可能である。なお、微調整領域の次元は、処理対象データの次元に応じて適切に定めればよい。
【００７５】
また、上記では、セグメントを直線で近似する場合を説明したが、セグメントを直線または円弧で近似してもよい。その場合、頂点に加えて、円弧（例えば、円弧の半径、円弧の中心から両端点への方向ベクトルと法線ベクトルなど）を特徴量とすることができる。また、セグメントを、直線と円弧の組み合わせ（複数の円弧のみの組み合わせを含む）で近似してもよい。その場合、頂点に加えて、セグメントの両端に当てはめられた円弧のみを、そのセグメントの特徴としてもよい。
【００７６】
セグメントが円弧で近似されている場合（直線と円弧の組み合わせで近似されている場合を含む）、ステップＳ４における頂点の算出には、円弧の両端における接線を使用する。円弧の接線は、円弧の中心から両端点への方向ベクトルから求めることができる。また、ステップＳ５において、頂点に関する処理と同様に、モデルと撮像画像データの円弧の組み合わせについても対応候補を求める。円弧の両端点の３次元座標によって平行移動ベクトルｔを決定することができ、円弧の中心から両端点への方向ベクトルと法線ベクトルによって回転行列Ｒを決定することができる。また、半径が大きく異なる円弧の組み合わせについては候補から除外するのが望ましい。頂点と円弧それぞれによって算出された対応候補を合わせたＡ(ｉ，ｊ)およびＴij(０)が、最終的な初期照合の結果とする。
【００７７】
また、上記では、コンピュータを用い、ソフトウェアプログラムによって実施する場合を説明したが、これに限定されない。上記の機能を、複数の機能に分割し、その一部または全てを１つまたは複数のハードウェア（例えば、専用の半導体チップ（ＡＳＩＣ）及びその周辺回路）によって実現してもよい。例えば、複数のハードウェアで構成する場合、各ペア画像データを用いたステレオ対応による３次元復元像および照合に必要な特徴量を
求める３次元復元計算部と、２つの３次元復元画像データの特徴量の類似性から対応する点を照合する照合調整部とで構成してもよい。
【実施例】
【００７８】
以下に実施例を示し、本発明の有効性をより明らかにする。
【００７９】
２台のカメラを用いて、特定の対象物を撮像し、得られた画像データとモデルデータとの照合を、図２に示したフローチャートに従って行った。ここでは、２つの３次元復元画像データの一方をモデルデータとして処理を行ったが、２つの３次元復元画像データを対象とする場合と同様の処理である。
【００８０】
対象物（実物およびモデル）として、図４の三面図に示すように直方体の胴体中央付近にくびれ部のある形状を使用した。
【００８１】
図４の対象物を２つのカメラで撮像して、図５に示す左右２枚の画像データを得た。そして、図５の画像データを用いて、図２のステップＳ３〜Ｓ５の処理を実施した。
【００８２】
図６は、頂点を形成するセグメント対のみ（画像上部）で照合を行う初期微調整後、つまり本発明の照合（伝播照合）過程に進入前の段階での位置合わせ結果を示す。点線は対象物のデータを表し、実線は画像から得られたエッジを表す。伝播照合の有無に関わらずこの状態を通過することになるが、図６から分かるように計測データの精度不足（不適正な露光時間／ピント、カメラ校正の不良、撮像素子の持つ画像ノイズ等が原因として考えられる）で不正確な位置合わせ状態となっている。
【００８３】
図７は従来の方法による位置合わせ過程の最終結果であるが、画像下側領域でモデル底面とデータ上面とで照合が進み、正しい位置合わせが行われなかったことが分かる。
【００８４】
図８は伝播照合を組み込んだ本発明による位置合わせ過程の最終結果であるが、本発明による手法により正しい位置合わせが行われたことが分かる。
【００８５】
以上のように、従来の方法では、初期照合結果が間違っていた場合、その後に全データを用いたＩＣＰアルゴリズム等による微調整を行っても正解には収束しないのに対して、本発明によれば、初期照合結果が間違っていた場合でも、正解に収束させることができる。従来の方法で正解に収束しない問題は、対象物の大きさや形状によらず、セグメントが小さい場合に発生し易い。従って、本発明は、対象物の大きさや形状によらず、セグメントが小さい場合に特に有効である。
【符号の説明】
【００８６】
１ 演算処理部（ＣＰＵ）
２ 記録部
３ 記憶部（メモリ）
４ インタフェース部
５ 操作部
６ 表示部
７ 内部バス
ＰＣ コンピュータ
Ｃ１ 第１撮像部
Ｃ２ 第２撮像部
Ｔ 撮像対象物
【特許請求の範囲】
【請求項１】
相互に異なる２つの視点から対象物を撮像して得られた２枚の画像データから第１の３次元復元点集合および第１特徴量集合を求める第１ステップと、
前記視点と異なり、相互に異なる２つの視点から前記対象物を撮像して得られた２枚の画像データから第２の３次元復元点集合および第２特徴量集合を求める第２ステップと、
前記第１特徴量集合を前記第２特徴量集合と照合することにより、第２の３次元復元点集合の中から前記第１の３次元復元点集合の点に対応する点を決定する第３ステップとを含み、
前記第１及び第２の３次元復元点集合が、対応する前記画像データ中の前記対象物の境界線を分割したセグメントの３次元位置座標を含み、
前記第１及び第２特徴量集合が、前記セグメントの頂点に関する３次元情報を含み、
前記第３ステップが、
前記第１及び第２の３次元復元点集合のセグメントに関して初期照合を行う第４ステップと、
前記第１特徴量集合の中から特徴点を選択する第５ステップと、
選択された前記特徴点を内部に含む領域を調整領域として指定する第６ステップと、
前記調整領域に含まれる前記第１及び第２の３次元復元点集合のセグメントに関して、照合の微調整を行う第７ステップとから構成され、
前記調整領域を段階的に拡大する毎に前記第７ステップを実行し、
前記特徴点を選択する毎に前記第６及び第７ステップを実行する
ことを特徴とする３次元位置合わせにおける照合方法。
【請求項２】
前記セグメントが、直線、円弧、又は、直線及び円弧の組み合わせで近似され、
前記頂点に関する前記３次元情報が、前記頂点の３次元位置座標および２つの３次元接線ベクトルであり、
前記照合が、前記第１特徴量集合の一部を、前記第２特徴量集合の一部に一致するように３次元座標変換する変換行列を求める処理であり、
前記第２の３次元復元点集合の中から前記第１の３次元復元点集合の点に対応する点を決定する処理が、前記変換行列を用いて前記第１の３次元復元点集合の点を３次元座標変換した結果と、前記第２の３次元復元点集合の点との一致性を評価する処理であることを特徴とする請求項１に記載の照合方法。
【請求項３】
相互に異なる２つの視点から対象物を撮像して得られた２枚の画像データから３次元復元点集合および特徴量集合を求める第１ステップと、
前記対象物のモデルデータ集合およびモデル特徴量集合を求める第２ステップと、
前記モデル特徴量集合を前記特徴量集合と照合することにより、前記３次元復元点集合の中から前記モデルデータ集合の点に対応する点を決定する第３ステップとを含み、
前記３次元復元点集合が、対応する前記画像データ中の前記対象物の境界線を分割したセグメントの３次元位置座標を含み、
前記特徴量集合が、前記セグメントの頂点に関する３次元情報を含み、
前記第３ステップが、
前記３次元復元点集合のセグメントに関して前記モデル特徴量集合との初期照合を行う第４ステップと、
前記モデル特徴量集合の中から特徴点を選択する第５ステップと、
選択された前記特徴点を内部に含む領域を調整領域として指定する第６ステップと、
前記調整領域に含まれる前記モデルデータ集合及び前記３次元復元点集合のセグメントに関して、照合の微調整を行う第７ステップとから構成され、
前記調整領域を段階的に拡大する毎に前記第７ステップを実行し、
前記特徴点を選択する毎に前記第６及び第７ステップを実行する
ことを特徴とする３次元位置合わせにおける照合方法。
【請求項４】
前記セグメントが、直線、円弧、又は、直線及び円弧の組み合わせで近似され、
前記頂点に関する前記３次元情報が、前記頂点の３次元位置座標および２つの３次元接線ベクトルであり、
前記照合が、前記モデル特徴量集合の一部を、前記特徴量集合の一部に一致するように３次元座標変換する変換行列を求める処理であり、
前記３次元復元点集合の中から前記モデルデータ集合の点に対応する点を決定する処理が、前記変換行列を用いて前記モデルデータ集合の点を３次元座標変換した結果と、前記３次元復元点集合の点との一致性を評価する処理であることを特徴とする請求項３に記載の照合方法。
【請求項５】
コンピュータに、
相互に異なる２つの視点から対象物を撮像して得られた２枚の画像データから第１の３次元復元点集合および第１特徴量集合を求める第１機能と、
前記視点と異なり、相互に異なる２つの視点から前記対象物を撮像して得られた２枚の画像データから第２の３次元復元点集合および第２特徴量集合を求める第２機能と、
前記第１特徴量集合を前記第２特徴量集合と照合することにより、第２の３次元復元点集合の中から前記第１の３次元復元点集合の点に対応する点を決定する第３機能とを実現させ、
前記第１及び第２の３次元復元点集合が、対応する前記画像データ中の前記対象物の境界線を分割したセグメントの３次元位置座標を含み、
前記第１及び第２特徴量集合が、前記セグメントの頂点に関する３次元情報を含み、
前記第３機能が、
前記第１及び第２の３次元復元点集合のセグメントに関して初期照合を行う第４機能と、
前記第１特徴量集合の中から特徴点を選択する第５機能と、
選択された前記特徴点を内部に含む領域を調整領域として指定する第６機能と、
前記調整領域に含まれる前記第１及び第２の３次元復元点集合のセグメントに関して、照合の微調整を行う第７機能とから構成され、
前記コンピュータに、
前記調整領域を段階的に拡大する毎に前記第７機能を実現させ、
前記特徴点を選択する毎に前記第６及び第７機能を実行させる
ことを特徴とする３次元位置合わせにおける照合プログラム。
【請求項６】
前記セグメントが、直線、円弧、又は、直線及び円弧の組み合わせで近似され、
前記頂点に関する前記３次元情報が、前記頂点の３次元位置座標および２つの３次元接線ベクトルであり、
前記照合が、前記第１特徴量集合の一部を、前記第２特徴量集合の一部に一致するように３次元座標変換する変換行列を求める処理であり、
前記第２の３次元復元点集合の中から前記第１の３次元復元点集合の点に対応する点を決定する処理が、前記変換行列を用いて前記第１の３次元復元点集合の点を３次元座標変換した結果と、前記第２の３次元復元点集合の点との一致性を評価する処理であることを特徴とする請求項５に記載の照合プログラム。
【請求項７】
コンピュータに、
相互に異なる２つの視点から対象物を撮像して得られた２枚の画像データから３次元復元点集合および特徴量集合を求める第１機能と、
前記対象物のモデルデータ集合およびモデル特徴量集合を求める第２機能と、
前記モデル特徴量集合を前記特徴量集合と照合することにより、前記３次元復元点集合
の中から前記モデルデータ集合の点に対応する点を決定する第３機能とを実現させ、
前記３次元復元点集合が、対応する前記画像データ中の前記対象物の境界線を分割したセグメントの３次元位置座標を含み、
前記特徴量集合が、前記セグメントの頂点に関する３次元情報を含み、
前記第３機能が、
前記３次元復元点集合のセグメントに関して前記モデル特徴量集合との初期照合を行う第４機能と、
前記モデル特徴量集合の中から特徴点を選択する第５機能と、
選択された前記特徴点を内部に含む領域を調整領域として指定する第６機能と、
前記調整領域内に含まれる前記モデルデータ集合及び前記３次元復元点集合のセグメントに関して、照合の微調整を行う第７機能とから構成され、
前記コンピュータに、
前記調整領域を段階的に拡大する毎に前記第７機能を実現させ、
前記特徴点を選択する毎に前記第６及び第７機能を実現させる
ことを特徴とする３次元位置合わせにおける照合プログラム。
【請求項８】
前記セグメントが、直線、円弧、又は、直線及び円弧の組み合わせで近似され、
前記頂点に関する前記３次元情報が、前記頂点の３次元位置座標および２つの３次元接線ベクトルであり、
前記照合が、前記モデル特徴量集合の一部を、前記特徴量集合の一部に一致するように３次元座標変換する変換行列を求める処理であり、
前記３次元復元点集合の中から前記モデルデータ集合の点に対応する点を決定する処理が、前記変換行列を用いて前記モデルデータ集合の点を３次元座標変換した結果と、前記３次元復元点集合の点との一致性を評価する処理であることを特徴とする請求項７に記載の照合プログラム。
【請求項１】
相互に異なる２つの視点から対象物を撮像して得られた２枚の画像データから第１の３次元復元点集合および第１特徴量集合を求める第１ステップと、
前記視点と異なり、相互に異なる２つの視点から前記対象物を撮像して得られた２枚の画像データから第２の３次元復元点集合および第２特徴量集合を求める第２ステップと、
前記第１特徴量集合を前記第２特徴量集合と照合することにより、第２の３次元復元点集合の中から前記第１の３次元復元点集合の点に対応する点を決定する第３ステップとを含み、
前記第１及び第２の３次元復元点集合が、対応する前記画像データ中の前記対象物の境界線を分割したセグメントの３次元位置座標を含み、
前記第１及び第２特徴量集合が、前記セグメントの頂点に関する３次元情報を含み、
前記第３ステップが、
前記第１及び第２の３次元復元点集合のセグメントに関して初期照合を行う第４ステップと、
前記第１特徴量集合の中から特徴点を選択する第５ステップと、
選択された前記特徴点を内部に含む領域を調整領域として指定する第６ステップと、
前記調整領域に含まれる前記第１及び第２の３次元復元点集合のセグメントに関して、照合の微調整を行う第７ステップとから構成され、
前記調整領域を段階的に拡大する毎に前記第７ステップを実行し、
前記特徴点を選択する毎に前記第６及び第７ステップを実行する
ことを特徴とする３次元位置合わせにおける照合方法。
【請求項２】
前記セグメントが、直線、円弧、又は、直線及び円弧の組み合わせで近似され、
前記頂点に関する前記３次元情報が、前記頂点の３次元位置座標および２つの３次元接線ベクトルであり、
前記照合が、前記第１特徴量集合の一部を、前記第２特徴量集合の一部に一致するように３次元座標変換する変換行列を求める処理であり、
前記第２の３次元復元点集合の中から前記第１の３次元復元点集合の点に対応する点を決定する処理が、前記変換行列を用いて前記第１の３次元復元点集合の点を３次元座標変換した結果と、前記第２の３次元復元点集合の点との一致性を評価する処理であることを特徴とする請求項１に記載の照合方法。
【請求項３】
相互に異なる２つの視点から対象物を撮像して得られた２枚の画像データから３次元復元点集合および特徴量集合を求める第１ステップと、
前記対象物のモデルデータ集合およびモデル特徴量集合を求める第２ステップと、
前記モデル特徴量集合を前記特徴量集合と照合することにより、前記３次元復元点集合の中から前記モデルデータ集合の点に対応する点を決定する第３ステップとを含み、
前記３次元復元点集合が、対応する前記画像データ中の前記対象物の境界線を分割したセグメントの３次元位置座標を含み、
前記特徴量集合が、前記セグメントの頂点に関する３次元情報を含み、
前記第３ステップが、
前記３次元復元点集合のセグメントに関して前記モデル特徴量集合との初期照合を行う第４ステップと、
前記モデル特徴量集合の中から特徴点を選択する第５ステップと、
選択された前記特徴点を内部に含む領域を調整領域として指定する第６ステップと、
前記調整領域に含まれる前記モデルデータ集合及び前記３次元復元点集合のセグメントに関して、照合の微調整を行う第７ステップとから構成され、
前記調整領域を段階的に拡大する毎に前記第７ステップを実行し、
前記特徴点を選択する毎に前記第６及び第７ステップを実行する
ことを特徴とする３次元位置合わせにおける照合方法。
【請求項４】
前記セグメントが、直線、円弧、又は、直線及び円弧の組み合わせで近似され、
前記頂点に関する前記３次元情報が、前記頂点の３次元位置座標および２つの３次元接線ベクトルであり、
前記照合が、前記モデル特徴量集合の一部を、前記特徴量集合の一部に一致するように３次元座標変換する変換行列を求める処理であり、
前記３次元復元点集合の中から前記モデルデータ集合の点に対応する点を決定する処理が、前記変換行列を用いて前記モデルデータ集合の点を３次元座標変換した結果と、前記３次元復元点集合の点との一致性を評価する処理であることを特徴とする請求項３に記載の照合方法。
【請求項５】
コンピュータに、
相互に異なる２つの視点から対象物を撮像して得られた２枚の画像データから第１の３次元復元点集合および第１特徴量集合を求める第１機能と、
前記視点と異なり、相互に異なる２つの視点から前記対象物を撮像して得られた２枚の画像データから第２の３次元復元点集合および第２特徴量集合を求める第２機能と、
前記第１特徴量集合を前記第２特徴量集合と照合することにより、第２の３次元復元点集合の中から前記第１の３次元復元点集合の点に対応する点を決定する第３機能とを実現させ、
前記第１及び第２の３次元復元点集合が、対応する前記画像データ中の前記対象物の境界線を分割したセグメントの３次元位置座標を含み、
前記第１及び第２特徴量集合が、前記セグメントの頂点に関する３次元情報を含み、
前記第３機能が、
前記第１及び第２の３次元復元点集合のセグメントに関して初期照合を行う第４機能と、
前記第１特徴量集合の中から特徴点を選択する第５機能と、
選択された前記特徴点を内部に含む領域を調整領域として指定する第６機能と、
前記調整領域に含まれる前記第１及び第２の３次元復元点集合のセグメントに関して、照合の微調整を行う第７機能とから構成され、
前記コンピュータに、
前記調整領域を段階的に拡大する毎に前記第７機能を実現させ、
前記特徴点を選択する毎に前記第６及び第７機能を実行させる
ことを特徴とする３次元位置合わせにおける照合プログラム。
【請求項６】
前記セグメントが、直線、円弧、又は、直線及び円弧の組み合わせで近似され、
前記頂点に関する前記３次元情報が、前記頂点の３次元位置座標および２つの３次元接線ベクトルであり、
前記照合が、前記第１特徴量集合の一部を、前記第２特徴量集合の一部に一致するように３次元座標変換する変換行列を求める処理であり、
前記第２の３次元復元点集合の中から前記第１の３次元復元点集合の点に対応する点を決定する処理が、前記変換行列を用いて前記第１の３次元復元点集合の点を３次元座標変換した結果と、前記第２の３次元復元点集合の点との一致性を評価する処理であることを特徴とする請求項５に記載の照合プログラム。
【請求項７】
コンピュータに、
相互に異なる２つの視点から対象物を撮像して得られた２枚の画像データから３次元復元点集合および特徴量集合を求める第１機能と、
前記対象物のモデルデータ集合およびモデル特徴量集合を求める第２機能と、
前記モデル特徴量集合を前記特徴量集合と照合することにより、前記３次元復元点集合
の中から前記モデルデータ集合の点に対応する点を決定する第３機能とを実現させ、
前記３次元復元点集合が、対応する前記画像データ中の前記対象物の境界線を分割したセグメントの３次元位置座標を含み、
前記特徴量集合が、前記セグメントの頂点に関する３次元情報を含み、
前記第３機能が、
前記３次元復元点集合のセグメントに関して前記モデル特徴量集合との初期照合を行う第４機能と、
前記モデル特徴量集合の中から特徴点を選択する第５機能と、
選択された前記特徴点を内部に含む領域を調整領域として指定する第６機能と、
前記調整領域内に含まれる前記モデルデータ集合及び前記３次元復元点集合のセグメントに関して、照合の微調整を行う第７機能とから構成され、
前記コンピュータに、
前記調整領域を段階的に拡大する毎に前記第７機能を実現させ、
前記特徴点を選択する毎に前記第６及び第７機能を実現させる
ことを特徴とする３次元位置合わせにおける照合プログラム。
【請求項８】
前記セグメントが、直線、円弧、又は、直線及び円弧の組み合わせで近似され、
前記頂点に関する前記３次元情報が、前記頂点の３次元位置座標および２つの３次元接線ベクトルであり、
前記照合が、前記モデル特徴量集合の一部を、前記特徴量集合の一部に一致するように３次元座標変換する変換行列を求める処理であり、
前記３次元復元点集合の中から前記モデルデータ集合の点に対応する点を決定する処理が、前記変換行列を用いて前記モデルデータ集合の点を３次元座標変換した結果と、前記３次元復元点集合の点との一致性を評価する処理であることを特徴とする請求項７に記載の照合プログラム。
【図１】
【図２】
【図４】
【図３】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図４】
【図３】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１１−１９８３３０（Ｐ２０１１−１９８３３０Ａ）
【公開日】平成２３年１０月６日（２０１１．１０．６）
【国際特許分類】
【出願番号】特願２０１０−６７４４５（Ｐ２０１０−６７４４５）
【出願日】平成２２年３月２４日（２０１０．３．２４）
【出願人】（３０１０２１５３３）独立行政法人産業技術総合研究所 (6,529)
【Ｆターム（参考）】
【公開日】平成２３年１０月６日（２０１１．１０．６）
【国際特許分類】
【出願日】平成２２年３月２４日（２０１０．３．２４）
【出願人】（３０１０２１５３３）独立行政法人産業技術総合研究所 (6,529)
【Ｆターム（参考）】
[ Back to top ]