対応点探索方法および３次元位置計測方法
【課題】対応点の探索に要する計算量を大幅に減らし、短時間でかつ高精度に、対応付けの結果を得ることができるようにする。
【解決手段】対象物を異なる視点から見た複数の画像を取り込む。その画像の１つを基準画像、それ以外を参照画像とする。基準画像および参照画像から、カメラパラメータおよび基準点から計算されるエピポーラ線に沿って、所定幅Ｗの１次元の画素データ列を切り出す。この切り出した１次元の画素データ列から位相限定相関関数を計算することによって相関ピークの位置Ｐａ１を求め、この相関ピークの位置Ｐａ１から位置ずれ量ｄを求め、この位置ずれ量ｄから基準点ｐに対応する対応点ｑを探索する。
【解決手段】対象物を異なる視点から見た複数の画像を取り込む。その画像の１つを基準画像、それ以外を参照画像とする。基準画像および参照画像から、カメラパラメータおよび基準点から計算されるエピポーラ線に沿って、所定幅Ｗの１次元の画素データ列を切り出す。この切り出した１次元の画素データ列から位相限定相関関数を計算することによって相関ピークの位置Ｐａ１を求め、この相関ピークの位置Ｐａ１から位置ずれ量ｄを求め、この位置ずれ量ｄから基準点ｐに対応する対応点ｑを探索する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、立体的な物体、例えば人間の顔などを対象物とし、この対象物を異なる視点から見た複数の画像中の対応点を探索する対応点探索方法およびこの対応点探索方法を利用した３次元位置計測方法に関するものである。
【背景技術】
【０００２】
従来より、対象物を異なる視点から見た複数の画像中の対応点の探索は、画像センシング、画像・映像信号処理、コンピュータビジョン等の様々な分野で重要な技術とされている。これらの分野では、通常、ピクセル精度の対応付け手法を用いることが多いが、近年、サブピクセル精度の対応付け手法への要求が高まっている。
【０００３】
例えば、基線長の短いステレオビジョンシステムにおいて、十分な３次元計測精度を実現するためには、サブピクセル精度の対応付けアルゴリズムが不可欠である。また、超解像による映像の高解像度化技術などにおいても、サブピクセル精度の対応付けアルゴリズムが重要になる。このため、例えば特許文献１に示された立体像計測装置では、対象物を異なる視点から見た複数の画像中の対応点の探索を２次元位相限定相関法を用いて行うことにより、サブピクセル精度の対応付けの要求を満たしている。
【０００４】
図２０は上述の特許文献１に示された立体像計装置における画像入力部の概略を示す図である。同図において、１は第１のカメラ、２は第２のカメラ、Ｍは対象物（人間の顔）である。カメラ１，２は、そのレンズＬＮ１，ＬＮ２間の距離をＬとして、横方向に並んで配置されている。図では分かり易いように、カメラ１および２を上方向から見た図とし、対象物Ｍは横方向から見た図としている。
【０００５】
この立体像計測装置では、対象物Ｍをカメラ１で捉えた画像を入力画像Ｉ（図２１（ａ））とし、この入力画像Ｉの画像データをｍ×ｎ個の局所領域Ｉ（ｉ，ｊ）に分割する（図２１（ｂ））。そして、入力画像Ｉの画像データから局所領域Ｉ（ｉ，ｊ）を切り出し、この切り出した局所領域Ｉ（ｉ，ｊ）の画像データに２次元離散的フーリエ変換（ＤＦＴ）を施してフーリエ画像データ（入力フーリエ画像データ）を得る。
【０００６】
また、対象物Ｍをカメラ２で捉えた画像を参照画像Ｊ（図２１（ｃ））とし、この参照画像Ｊの画像データに２次元離散的フーリエ変換を施してフーリエ画像データ（参照フーリエ画像データ）を得る。
【０００７】
そして、この得られた入力フーリエ画像データと参照フーリエ画像データとを合成し、この合成したフーリエ画像データ（合成フーリエ画像データ）の振幅成分を正規化して、もう一度、２次元離散的フーリエ変換（もしくは２次元離散的逆フーリエ変換）を施す。
【０００８】
そして、この２次元離散的フーリエ変換が施された合成フーリエ画像データより所定の相関成分エリアの各画素の相関成分の強度（振幅）を求め、この相関成分エリア内の最も強度の高い画素の位置を相関ピークの位置Ｐａ１（図２１（ｄ））とする。
【０００９】
この場合、相関成分エリアの中心Ｐ０から相関ピークの位置Ｐａ１までの距離Ａが、入力画像Ｉの画像データにおける局所領域Ｉ（ｉ，ｊ）と参照画像Ｊの画像データにおける一致する画像データのある領域（対応領域）とのずれ量を示す。入力画像Ｉにおける局所領域Ｉ（ｉ，ｊ）中の画像と参照画像Ｊにおける対応領域中の画像とは視差によってその画像がずれており、これがずれ量Ａとして現れる。
【００１０】
このずれ量Ａによって、入力画像中の局所領域Ｉ（ｉ，ｊ）の中心点（基準点）と、参照画像Ｊ中の対応領域の中心点（対応点）とを対応付け、三角測量の原理に基づく下記（１）式によって、カメラから対象物Ｍの対応点（基準点）までの距離Ｒを計算する。なお、下記（１）式において、ｆはレンズＬＮ（ＬＮ１，ＬＮ２）の中心から撮像位置までの距離、Ｌはレンズ間距離である。
Ｒ＝ｆ・Ｌ／Ａ ・・・・（１）
【００１１】
【特許文献１】特開平１０−１３２５３４号公報
【非特許文献１】「写真から作る３次元ＣＧ」、著者：徐剛、発行所：株式会社 近代科学社、２００３年２月２５日 初版第２刷発行、３１〜３３頁。
【非特許文献２】ディジタル画像処理編集委員会、“ディジタル画像処理”、CG-ARTS協会、２００５。
【非特許文献３】D. Scharstein and R. Szeliski. “A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms”, IJCV ４７(１/２/３):７-４２, April-June ２００２.
【非特許文献４】Yi Ma, Stefano Soatto, Jana Kosecka, S. Shankar Sastry, “An Invitation to ３-D Vision: From Images to Geometric Models (Interdisciplinary Applied Mathematics)”, Springer, ２００４.
【非特許文献５】K. Takita, T. Aoki, Y. Sasaki, T. Higuchi, and K. Kobayashi, “High-accuracy subpixel image registration based on phase-only correlation,” IEICE Trans. Fundamentals, vol. E８６-A, no. ８, pp. １９２５-１９３４, Aug. ２００３.
【非特許文献６】K. Takita, M. A. Muquit, T. Aoki, and T. Higuchi, “A sub-pixel correspondence search technique for computer vision applications,” IEICE Trans. Fundamentals, vol. E８７-A, no. ８, pp. １９１３-１９２３, Aug. ２００４.
【非特許文献７】M. A. Muquit, T. Shibahara, and T. Aoki, “A high-accuracy passive ３D measurement system using phase-based image matching,” IEICE Trans. Fundamentals,vol.E８９-A, no. ３, pp. ６８６-６９７, Mar. ２００６.
【非特許文献８】徐 剛, 辻 三郎、“３次元ビジョン” 、共立出版、１９９８。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
上述した特許文献１に示された手法は、対応付けの精度が極めて高く、様々な画像に対して同一のアルゴリズムが適用できるという長所がある。しかしながら、この手法は、２次元離散的フーリエ変換に要する計算量が多く、短時間で対応付けの結果を得ることが要求される分野では採用し難いという問題があった。
【００１３】
本発明は、このような課題を解決するためになされたもので、その目的とするところは、対応点の探索に要する計算量を大幅に減らし、短時間でかつ高精度に、対応付けの結果を得ることが可能な対応点探索方法および３次元位置計測方法を提供することにある。
【課題を解決するための手段】
【００１４】
このような目的を達成するために、本発明に係る対応点探索方法（請求項１（第１発明））は、画像取込手段を介して、対象物を異なる視点から見た複数の画像を取り込む画像取込ステップと、画像取込手段のパラメータおよび基準点から計算されるエピポーラ線に沿って複数の画像より１次元の画素データ列を切り出す画素データ列切出ステップと、複数の画像から切り出された１次元の画素データ列の相関から複数の画像中の対応点を探索する対応点探索ステップとを設けたものである。
【００１５】
この発明において、例えば、画像取込手段を所定の距離隔てて配置された２台のカメラとした場合、第１のカメラと第２のカメラが対象物に対して等位置に傾斜なく配置されていれば、第１のカメラで撮像される画像および第２のカメラで撮像される画像におけるエピポーラ線は、いずれも水平となる。これに対し、第１のカメラおよび第２のカメラの何れかが傾斜していれば、第１のカメラで撮像される画像および第２のカメラで撮像される画像におけるエピポーラ線も傾斜する。このように、第１のカメラで撮像される画像および第２のカメラで撮像される画像におけるエピポーラ線は、第１および第２のカメラの位置関係（２つの画像間の基礎行列や、内部行列・外部行列などのカメラ固有のパラメータ）によって定まる。本発明では、このような画像取込手段のパラメータを保存しておき、対応点を探索する際の処理過程で用いる。
【００１６】
本発明において、画像取込手段は、複数台のカメラに限られるものではない。例えば、光学機構を設けることによって、１台のカメラから対象物を異なる視点から見た複数の画像を得るようにしてもよい。
【００１７】
本発明において、複数の画像のうちの１つを入力画像、もう１つを参照画像とした場合、画像取込手段のパラメータおよび基準点から計算されるエピポーラ線に沿って、入力画像および参照画像より１次元の画素データ列（例えば、３２画素の画素データ列）が切り出される。そして、このエピポーラ線に沿って切り出された１次元の画素データ列の相関から、入力画像中の基準点に対応する参照画像中の対応点が探索され、基準点と対応点とが対応付けられる。
【００１８】
この場合、基準点の画素データ列は１次元の画素データ列であり、参照画像中の画素データ列も１次元の画素データ列であるので、１次元の位相限定相関法（１次元ＰＯＣ）を利用することができる。すなわち、複数の画像から切り出された１次元の画素データ列から位相限定相関相関を計算することによって得られる相関ピークの位置から位置ずれ量を求め、この位置ずれ量から複数の画像中の対応点を探索することが可能である。
【００１９】
１次元ＰＯＣでは、１次元のフーリエ変換を施せばよいので、計算量を大幅に減らすことができる。これにより、対応点の探索に要する計算量が大幅に減り、短時間で対応付けの結果を得ることが可能となる。また、１次元ＰＯＣを用いることにより、エピポーラ線の垂直方向の相関誤差要因を少なくすることができ、高精度な対応点探索が可能となる。
【００２０】
本発明において、画像取込手段を介して取り込まれる画像に存在するエピポーラ線は水平であるとは限らず、傾斜している場合もある。理想的には水平であることが望まれるが、カメラの取り付け誤差などもあり、エピポーラ線は傾斜している場合が多い。
そこで、第２発明（請求項２に係る発明）では、複数の画像中の各画素データを、画像取込手段のパラメータおよび基準点から計算されるエピポーラ線に平行な軸を一軸とし、この一軸に対して垂直な軸を他軸とする座標系に変換し、この座標系が変換された複数の画像から１次元の画素データ列を切り出すようにする。なお、このような座標系の変換は必ずしも必要ではなく、エピポーラ線が傾斜した座標系のまま処理を進めて、対応点の探索を行うようにしてもよい。座標系を変換することにより、以降の処理が簡単となる。
【００２１】
本発明では、エピポーラ線に沿って複数の画像より１次元の画素データ列を切り出し、この切り出した１次元の画素データ列の相関から対応点を探索するが、その１次元の画素データ列の近傍のエピポーラ線に平行な線に沿う１次元の画素データ列を複数の画像から切り出し、これら複数組の１次元の画素データ列の相関から対応点を探索するようにしてもよい（第３発明（請求項３に係る発明））。このようにすると、ノイズの影響を受け難くなり、対応点探索の性能がより安定する。
【００２２】
また、複数の画像から対応点探索の対象領域としてオブジェクト領域を抽出するようにし、この複数の画像から抽出されたオブジェクト領域よりエピポーラ線に沿って１次元の画素データ列を切り出すようにしてもよい（第４発明（請求項４に係る発明））。画像内のオブジェクト領域外の画素データを処理対象から除外することで、これらの領域が対応点探索過程で精度を下げる外乱要因として働くことを未然に防止し、対応点探索精度の向上を図ることが可能となる。また、オブジェクト領域を対応点探索の対象領域とすることにより、次々に対応点の探索を行うような場合、基準点をずらす領域を狭め、処理すべきデータ量を削減することができる。
【００２３】
また、本発明の対応点探索方法を利用することにより、探索した対応点の３次元位置を計測することも可能である。請求項５に係る発明（第５発明）は、探索した対応点の３次元位置を計測する３次元位置計測方法に関するものであり、第１発明によって探索された対応点の視差に基づいてその対応点の３次元位置を計測する。これにより、対応点の探索に要する計算量を大幅に減らし、対象物における各点の３次元位置を短時間で計測することが可能となる。
【発明の効果】
【００２４】
本発明によれば、画像取込手段を介して、対象物を異なる視点から見た複数の画像を取り込み、画像取込手段のパラメータおよび基準点から計算されるエピポーラ線に沿って複数の画像より１次元の画素データ列を切り出し、複数の画像から切り出された１次元の画素データ列の相関から複数の画像中の対応点を探索するようにしたので、１次元ＰＯＣを利用することができ、対応点の探索に要する計算量を大幅に減らし、短時間で対応付けの結果を得ることが可能となる。また、１次元ＰＯＣを用いることにより、エピポーラ線の垂直方向の相関誤差要因を少なくすることができ、高精度な対応点探索が可能となる。
【発明を実施するための最良の形態】
【００２５】
以下、本発明を図面に基づいて詳細に説明する。図１はこの発明に係る対応点探索方法を利用した３次元位置計測装置の一実施の形態を示すブロック構成図である。同図において、１０は第１のカメラ（ＣＣＤカメラ）、１１は第２のカメラ（ＣＣＤカメラ）、１２は液晶表示装置（ＬＣＤ）、２０は処理部であり、処理部２０は、ＣＰＵを有する制御部２０−１と、ＲＯＭ２０−２と、ＲＡＭ２０−３と、ハードディスクドライブ（ＨＤＤ）２０−４と、フレームメモリ（ＦＭ）２０−５と、外部接続部（Ｉ／Ｆ）２０−６と、フーリエ変換部（ＦＦＴ）２０−７とを備えており、ＲＯＭ２０−２には３次元位置計測プログラムが格納されている。
【００２６】
カメラ１０，１１は、図２０に示した従来例と同様に、所定の距離Ｌを隔てて設置されている。すなわち、カメラ１０，１１は、そのレンズＬＮ１，１Ｎ２間の距離をＬとして、横方向に並んで配置されている。この図でも分かり易いように、３次元位置計測装置は上方向から見た図とし、対象物Ｍは横方向から見た図としている。
【００２７】
〔カメラパラメータの保存〕
カメラ１０および１１は所定の距離Ｌを隔てて配置されている。このカメラ１０および１１が互いの光軸が平行且つ、画像座標の水平軸が同一直線上で同じ向きになるように配置されていれば、図２（ａ）および（ｂ）に示すように、カメラ１０で撮像される画像Ｉにおける基準点ｐが存在する直線ＥＰ１およびカメラ１１で撮像される画像Ｊにおける対応点ｑが存在する直線ＥＰ２、すなわちエピポーラ線ＥＰ１およびＥＰ２は、いずれも水平となる。なお、エピポーラ線については、非特許文献１などに解説されているので、ここでの詳細な説明は省略する。
【００２８】
これに対し、カメラ１０および１１の何れかが傾斜していれば、カメラ１０で撮像される画像Ｉおよびカメラ１１で撮像される画像Ｊにおけるエピポーラ線ＥＰ１，ＥＰ２も傾斜する（図３（ａ），（ｂ）参照）。このように、カメラ１０で撮像される画像Ｉおよびカメラ１１で撮像される画像Ｊにおけるエピポーラ線ＥＰ（ＥＰ１，ＥＰ２）は、カメラ１０とカメラ１１との位置関係（２つの画像間の基礎行列や、内部行列・外部行列などのカメラ固有のパラメータ）によって定まる。本実施の形態では、このカメラ１０とカメラ１１との位置関係を示すパラメータ（カメラパラメータ）をハードディスクに保存させておき、後述する対応点を探索する際の処理過程で用いる。
【００２９】
〔３次元位置の計測〕
この３次元位置計測装置において、対象物Ｍを人間の顔とした場合、この対象物Ｍにおける各点の３次元位置の計測は次のようにして行われる。この３次元位置の計測処理は、ＲＯＭ２０−２に格納された３次元位置計測プログラムに従って、制御部２０−１が行う。
【００３０】
〔画像取り込み〕
制御部２０−１は、カメラ１０からの対象物Ｍを捉えた画像Ｉを入力画像（図４（ａ））として取り込む（図５に示すステップ１０１）。また、カメラ１１からの対象物Ｍを捉えた画像Ｊ（図４（ｂ））を参照画像として取り込む（ステップ１０２）。
【００３１】
〔座標系の変換〕
そして、ハードディスクに保存されているカメラパラメータを読み出し、入力画像Ｉおよび参照画像Ｊ中の各画素データを、カメラパラメータおよび基準点から計算されるエピポーラ線ＥＰに平行な軸をＸ軸とし、このＸ軸に対して垂直な軸をＹ軸とする座標系に変換する（ステップ１０３）。この座標系が変換された入力画像Ｉおよび参照画像Ｊを入力画像Ｉ’および参照画像Ｊ’とする（図４（ｃ），（ｄ））。
【００３２】
〔対象領域の抽出〕
次に、エッジ検出により、入力画像Ｉ’および参照画像Ｊ’中から、対象物Ｍ（人間の顔）が存在する領域だけを対応点探索の対象領域（以下、オブジェクト領域と呼ぶ）として抽出する（ステップ１０４）。これにより、図４（ｅ）および（ｆ）に示されるように、オブジェクト領域ＯＢ１およびＯＢ２を抽出した入力画像Ｉ”および参照画像Ｊ”が得られる。
【００３３】
なお、ここでは、説明を簡単とするために、入力画像Ｉおよび参照画像Ｊにおける対象物Ｍ以外の背景は無地であり、対象物Ｍが存在する領域だけがオブジェクト領域ＯＢ１およびＯＢ２として正しく抽出されるものとする。
【００３４】
〔対応点の探索〕
そして、制御部２０−１は、入力画像Ｉ”中のオブジェクト領域ＯＢ１と参照画像Ｊ”中のオブジェクト領域ＯＢ２とを対象領域として、対応点の探索を行う（ステップ１０５）。図６にステップ１０５における対応点の探索処理のフローチャートを示す。制御部２０−１は、このフローチャートに従って、対応点の探索を次のようにして行う。
【００３５】
先ず、入力画像Ｉ”において、Ｘ軸に平行な各線（１画素幅の線）のオブジェクト領域ＯＢ１内の起点（ＳＴ）と終点（ＥＮＤ）を求める（ステップ２０１）。
【００３６】
そして、オブジェクト領域ＯＢ１中の最上位の線の線番号をｎ＝１とし（ステップ２０２）、このｎ＝１番目の線上に基準点ｐを定め、その基準点ｐを中心とする所定幅Ｗの探索ウィンドウＳＷの画素データ列を基準点ｐの画素データ列として抽出する（ステップ２０３）。この例では、ｎ＝１番目の線（以下、探索ラインと呼ぶ）の起点ＳＴ（図７（ａ）参照）から、幅Ｗを３２画素とする探索ウィンドウＳＷ内の画素のデータ列を基準点ｐの画素データ列として抽出する。
【００３７】
この場合、ｎ＝１番目の探索ラインが基準点ｐのエピポーラ線ＥＰであり、このエピポーラ線ＥＰに沿って基準点ｐの画素データ列が切り出されるものとなる。この基準点の画素データ列は１次元の画素のデータ列である。
【００３８】
また、オブジェクト領域ＯＢ２中の基準点ｐに対応する座標点を候補点ｑ’とし、この候補点ｑ’を中心とする幅Ｗ＝３２画素の探索ウィンドウＣＷを定め、探索ウィンドウＣＷ内の画素のデータ列を候補点ｑ’の画素データ列として抽出する（ステップ２０４）。
【００３９】
この場合、ｎ＝１番目の探索ラインが候補点ｑ’のエピポーラ線ＥＰであり、このエピポーラ線ＥＰに沿って候補点ｑ’の画素データ列が切り出されるものとなる。この候補点の画素データ列は１次元の画素のデータ列である。
【００４０】
そして、ステップ２０３で抽出した基準点ｐの画素データ列とステップ２０４で抽出した候補点ｑ’の画素データ列とから位相限定相関関数を計算する（ステップ２０５）。この位相限定相関関数の計算には１次元位相限定相関法（１次元ＰＯＣ）を用いる。この１次元ＰＯＣによる位相限定相関関数の計算は次のようにして行う。
【００４１】
制御部２０−１は、ステップ２０３で抽出した基準点ｐの画素データ列を第１の画像データＧ１とし（図８（ａ）参照）、この第１の画像データＧ１をフーリエ変換部２０−７へ送り、この第１の画像データＧ１に１次元のフーリエ変換を施す。これにより、第１の画像データＧ１は、フーリエ画像データＦ１となる。
【００４２】
また、ステップ２０４で抽出した候補点ｑ’の画素データ列を第２の画像データＧ２とし（図８（ｂ）参照）、この第２の画像データＧ２をフーリエ変換部２０−７へ送り、この第２の画像データＧ２に１次元のフーリエ変換を施す。これにより、第２の画像データＧ２は、フーリエ画像データＦ２となる。
【００４３】
そして、制御部２０−１は、フーリエ画像データＦ１とフーリエ画像データＦ２とを合成し、この合成したフーリエ画像データ（合成フーリエ画像データ）の振幅成分を正規化してフーリエ変換部２０−７へ送り、もう一度、１次元のフーリエ変換を施す。
【００４４】
そして、この１次元のフーリエ変換が施された合成フーリエ画像データより所定の相関成分エリアの各画素の相関成分の強度（振幅）を求め、この相関成分エリア内の最も強度の高い相関成分の強度値を相関ピークとし、この相関ピークの位置Ｐａ１（図８（ｃ））を求める。この処理過程において、相関ピークを求める処理が位相限定相関関数を計算することに対応する。
【００４５】
この場合、相関成分エリアの中心Ｐ０から相関ピークの位置Ｐａ１までの距離ｄが、探索ウィンドウＳＷ中の画像と探索ウィンドウＣＷ中の画像とのずれ量、すなわち探索ウィンドウＳＷ中の基準点ｐと探索ウィンドウＣＷ中の対応点ｑとのずれ量を示す。制御部２０−１は、この基準点ｐと対応点ｑとのずれ量ｄを基準点ｐに対応付けて記憶する（ステップ２０６）。
【００４６】
以下同様にして、制御部２０−１は、オブジェクト領域ＯＢ１中のｎ＝１番目の探索ライン上の基準点を所定画素（例えば、１画素）ずつずらしながら、すなわち探索ウィンドウＳＷを所定画素づつずらしながら（ステップ２０８）、同様の処理を繰り返す。
【００４７】
そして、オブジェクト領域ＯＢ１中のｎ＝１番目の探索ラインの終点ＥＮＤまで対応点の探索が完了すれば（ステップ２０７のＹＥＳ）、オブジェクト領域ＯＢ１中のｎ＝２番目の探索ラインの起点に探索ウィンドウＳＷを移す（ステップ２０９）。以下同様にして、オブジェクト領域ＯＢ１中の最後の探索ラインの終点まで、同様動作を繰り返す。
【００４８】
〔３次元位置の計測〕
制御部２０−１は、オブジェクト領域ＯＢ１中の全ての基準点について対応点の探索が完了すると（ステップ２１０のＹＥＳ）、各基準点と各対応点とのずれ量ｄに基づいて、三角測量の原理に基づく下記（２）式によって、カメラから対象物Ｍの対応点（基準点）までの距離Ｒを計算する（ステップ１０６（図５））。
Ｒ＝ｆ・Ｌ／ｄ ・・・・（２）
【００４９】
そして、この計算したカメラから対象物Ｍの対応点（基準点）までの距離Ｒを３次元位置の計測データとし、各点の３次元位置の計測データをハードディスクに記憶させる。このハードディスクに記憶させた３次元位置の計測データ群は、必要に応じて読み出し、ＬＣＤ１２の画面上に表示したり、上位の装置へ送ったりする。
【００５０】
以上の説明から分かるように、本実施の形態において、基準点ｐの画素データ列は１次元の画素データ列であり、この基準点ｐの画素データ列との相関を求める候補点ｑ’の画素データ列も１次元の画素データ列であり、この基準点ｐの画素データ列と候補点ｑ’の画素データ列から１次元ＰＯＣを利用して位相限定相関関数を計算するようにしている。１次元ＰＯＣでは、１次元のフーリエ変換を施すので、対応点の探索に要する計算量が大幅に減り、短時間で対応付けの結果を得ることができる。また、１次元ＰＯＣを用いることにより、エピポーラ線ＥＰに垂直方向の相関誤差要因を取り除くことが可能となり、高精度な対応点探索が可能となる。
【００５１】
なお、上述した実施の形態では、基準点ｐの探索ウィンドウＳＷと候補点ｑ’の探索ウィンドウＣＷの幅Ｗを同じとしたが、候補点ｑ’の探索ウィンドウＣＷの幅Ｗは基準点ｐの探索ウィンドウＳＷの幅Ｗ以上あればよく、１本の探索ラインの起点ＳＴから終点ＥＮＤまでの全ての範囲を探索ウィンドウＣＷとしてもよい。
【００５２】
また、上述した実施の形態では、エピポーラ線ＥＰに沿って各画像より１次元の画素データ列を切り出し、この切り出した１次元の画素データ列の位相限定相関関数から対応点を探索するが、その１次元の画素データ列の近傍のエピポーラ線ＥＰに平行な線に沿う１次元の画素データ列を各画像から切り出し、これら複数組の１次元の画素データ列の位相限定相関関数から対応点を探索するようにしてもよい。このようにすると、ノイズの影響を受け難くなり、より対応点探索性能が安定する。
【００５３】
例えば、図９に示すように、入力画像Ｉ”における探索ウィンドウＳＷ（ＳＷ０）に対して平行に、この探索ウィンドウＳＷ０と同じ位置から同じ長さの近傍探索ウィンドウＳＷ１〜ＳＷ４を定め、この探索ウィンドウＳＷ０および近傍探索ウィンドウＳＷ１〜ＳＷ４内の画素データ列と参照画像Ｊ”における探索ウィンドウＣＷ０および近傍探索ウィンドウＣＷ１〜ＣＢ４内の画素データ列の各組の相関値を求め、相関値の平均を計算する。平均された相関値の最大ピーク位置を求めることで基準点ｐと対応点ｑとのずれ量を算出する。
【００５４】
この場合、探索ウィンドウＳＷ０および近傍探索ウィンドウＳＷ１〜ＳＷ４内の画素データ列に１次元のフーリエ変換を施し、探索ウィンドウＣＷ０および近傍探索ウィンドウＣＷ１〜ＣＢ４内の画素データ列に１次元のフーリエ変換を施し、フーリエ変換が施された探索ウィンドウＳＷ０内の画素データ列と探索ウィンドウＣＷ０内の画素データ列とを合成し、同様にして、フーリエ変換が施された近傍探索ウィンドウＳＷ１〜ＳＷ４内の画素データ列と近傍探索ウィンドウＣＷ１〜ＣＢ４内の画素データ列とを各個に合成し、これにより得られる５つの合成フーリエ画像データを平均して合成位相スペクトルを作成し、この合成位相スペクトルに対して１次元のフーリエ変換を施して最大相関ピークの位置を求めるようにすれば、５つの合成フーリエ画像データの１つひとつに１次元のフーリエ変換を施して相関ピークの位置を求めるようにする方法と比較して、格段に処理スピードがアップする。
【００５５】
図９では、探索ウィンドウＳＷ０に対して平行に、画像の水平方向に同じ位置から同じ長さの近傍探索ウィンドウＳＷ１〜ＳＷ４を定めたが、図１０に示すように、画像の水平方向に異なる位置から同じ長さの近傍探索ウィンドウＳＷ１〜ＳＷ４を定めるようにしてもよい。また、図１１に示すように、画像の水平方向に異なる位置から異なる長さの近傍探索ウィンドウＳＷ１〜ＳＷ４を定めるようにしてもよい。また、図１２に示すように、画像の異なる位置から異なる長さの近傍探索ウィンドウＳＷ１〜ＳＷ４を定めるようにしてもよい。
【００５６】
また、上述した実施の形態では、ステップ１０３において入力画像Ｉおよび参照画像Ｊを座標変換するようにしたが、必ずしも座標変換を行わなくてもよい。カメラ１０で撮像される画像およびカメラ１１で撮像される画像に存在するエピポーラ線ＥＰは水平であるとは限らず、傾斜している場合もある。理想的には水平であることが望まれるが、カメラ１０およびカメラ１１の取り付け誤差などもあり、エピポーラ線ＥＰは傾斜している場合が多い。このため、本実施の形態では、エピポーラ線ＥＰに平行な軸を一軸とし、この一軸に対して垂直な軸を他軸とする座標系に変換するようにした。エピポーラ線ＥＰが傾斜座標系のまま対応点の探索を進めるようにしてもよいが、座標系を変換することにより、以降の処理が簡単となる。なお、エピポーラ線ＥＰが平行である場合には、座標系の変換は不要である。
【００５７】
また、上述した実施の形態では、入力画像Ｉ’および参照画像Ｊ’からエッジ検出によってオブジェクト領域ＯＢ１およびＯＢ２を抽出するようにしたが、必ずしもオブジェクト領域ＯＢ１およびＯＢ２を抽出するようにしなくてもよい。例えば、オブジェクト領域ＯＢ１およびＯＢ２を抽出せずに、入力画像Ｉ’および参照画像Ｊ’の最上位の探索ラインの起点から最下位の探索ラインの終点まで、基準点ｐを移動しながら、すなわち探索ウィンドウＳＷを移動しながら、基準点ｐと対応点ｑとの対応付けを進めるようにしてもよい。
【００５８】
この場合、入力画像Ｉ’中の全領域において基準点ｐをずらしながら、その基準点ｐの画像データ列と参照画像Ｊ’中の候補点ｑ’の１次元の画素データ列との位相限定相関関数を１次元ＰＯＣによって計算することになるので、処理すべきデータ量が多くなる。これに対して、入力画像Ｉ’および参照画像Ｊ’からオブジェクト領域ＯＢ１およびＯＢ２を抽出し、この抽出したオブジェクト領域ＯＢ１およびＯＢ２を探索対象領域とすることにより、入力画像Ｉ’中の基準点ｐをずらす領域を小さくし、処理すべきデータ量を削減することができる。また、画像内のオブジェクト領域ＯＢ１，ＯＢ２外の画素データを処理対象から除外することで、これらの領域が対応点探索過程で精度を下げる外乱要因として働くことを未然に防止し、対応点探索精度の向上を図ることが可能となる。また、オブジェクト領域ＯＢ１中の探索ラインの起点から対応点の探索を始めることにより、常に対象物Ｍの輪郭に近い位置から対応点が求まるものとなり、対象物の３元位置の計測精度が向上する。
【００５９】
また、上述した実施の形態では説明しなかったが、対応点の探索を開始する際、入力画像Ｉ”および参照画像Ｊ”を低解像度として基準点の画素データ列と候補点の画素データ列との位相限定相関関数を計算し、この結果、相関ピークが得られれば、入力画像Ｉ”および参照画像Ｊ”の解像度を上げるということを段階的に繰り返して行くようにしてもよい。
【００６０】
また、上述した実施の形態では、カメラを２台としたが、光学機構を設けることによって、１台のカメラから入力画像Ｉと参照画像Ｊを得るようにしてもよい。また、カメラを３台以上設け、さらに複数の画像を得るようにしてもよい。カメラを１台とすると、ハードウェアで設計的に同期をとらずによいので、作りやすい。カメラがメガピクセルで高価な場合、安価になる場合がある。
【００６１】
また、上述した実施の形態では、基準点ｐの画素データ列と候補点ｑ’の画素データ列との相関関数を１次元の位相限定相関法で計算するようにしたが、１次元の帯域制限法で計算したり、１次元の相関係数法で計算したり、１次元の振幅抑制相関法で計算したりするようにしてもよい。
【００６２】
次に、１次元位相限定相関法を用いたエピポーラ幾何補正済み画像の対応付け手法について、さらに詳細に説明する。
【００６３】
１．１次元位相限定相関法に基づく画像の対応付けの基本手法
対応付けを行う２枚の画像を、そのエピポーラ線が平行になるように幾何補正（平行化）する（図１３（ａ）、（ｂ）参照）。図１３（ｂ）に示すように、この補正された２枚の画像を画像１および画像２とする。ここでは、図１３（ｂ）に示すように水平方向にエピポーラ線がそろう場合を考えるが、これは容易に一般的な平行化の場合に拡張できる。いま、画像１の基準点に対応する画像２の対応点を見つける問題を考える。
【００６４】
まず、図１３（ｂ）に示すように、平行化された画像１から、基準点ｐを中心とした１次元の画像信号を切り出し、ｆ(ｎ)とする。ここで、１次元画像信号ｆ(ｎ)はエピポーラ線と同じ方向に有限の長さで切り出すものとする。同様に平行化された画像２から、探索する対応点ｑの候補となる点ｑ’を中心として１次元画像信号ｇ(ｎ)を切り出す。このｇ(ｎ)は基準点ｐに対応するエピポーラ線上に存在する。ここで、１次元画像信号の離散空間インデックスを便宜上、ｎ＝−Ｍ,..,Ｍとする。ただし、Ｍは正の整数であり、１次元画像信号の長さＮはＮ＝２Ｍ＋１で与えられる。
【００６５】
なお、ここでは、説明を簡単にするために離散空間のインデックスを正負対称に取り、かつ１次元画像信号の長さを奇数にしているが、これは本手法の構成において必須ではない。すなわち、通常よく用いられるように０以上の離散空間インデックスを用い、１次元画像信号の長さＮを任意の正の整数に設定するように一般化することが可能である。通常はＮを２のべき乗の値にとり、高速フーリエ変換（ＦＦＴ）を利用して計算することが多い（後述する性能評価においても、Ｎを２のべき乗の値にとっている）。
【００６６】
以下では、フーリエ変換の記述の簡便さのために、上記のような設定を用いて説明を行う。また、１次元画像信号ｆ(ｎ)とｇ(ｎ)は、必ずしも基準点ｐとその対応候補点ｑ’を厳密に中心として切り出す必要はなく、一般にはそれらの上を通るように切り出すことができる。このとき、ｆ(ｎ)とｇ(ｎ)の１次元離散フーリエ変換を次式で定義する。
【００６７】
【数１】
【００６８】
ここで、ＡF(ｋ)及びＡG(ｋ)はそれぞれ１次元画像信号ｆ(ｎ)およびｇ(ｎ)の振幅成分であり、θF(ｋ)およびθG(ｋ)はそれぞれの位相成分である。また、離散周波数のインデックスをｋ＝−Ｍ,..,Ｍとする。ここで、離散空間のインデックスｎと同様に、離散周波数ｋのインデックスの選び方にも自由度がある。このとき、合成位相スペクトルＲ(ｋ)を次式で与える。
【００６９】
【数２】
【００７０】
しかし、実際のカメラで撮影された画像の場合、これは大きな問題にならない。ｆ(ｎ)とｇ(ｎ)の１次元位相限定相関関数ｒ(ｎ)を、合成位相スペクトルＲ(ｋ)の１次元逆離散フーリエ変換として定義する。
【００７１】
【数３】
【００７２】
ここで、ｎ＝−Ｍ,..,Ｍである。
【００７３】
次に、切り出した１次元画像信号ｆ(ｎ)とｇ(ｎ)が、互いに微小移動した関係にある場合を考える。つまり、このｆ(ｎ)とｇ(ｎ)に含まれる視差をサブピクセル分解能で推定する問題を考える。いま、ｆｃ(ｘ)を連続空間変数ｘの上で定義された１次元画像信号とする。これを実数値δだけ微小移動した１次元画像信号はｆｃ(ｘ−δ)と表される。このとき、ｆ(ｎ)とｇ(ｎ)が、ｆｃ(ｘ)およびｆｃ(ｘ−δ)を適当な空間サンプリング間隔Ｔでサンプリングしたものであると仮定する。すなわちｆ(ｎ)とｇ(ｎ)を次式で定義する。
【００７４】
【数４】
【００７５】
以下では、簡単のためにＴ＝１とする。このとき実数値の移動量δについて、サンプリング間隔を越える分解能で検出する方法を示す。まず、δが小さい場合、ｆ(ｎ)とｇ(ｎ)の１次元離散フーリエ変換Ｆ(ｋ)とＧ(ｋ)に関して、次式の近似が成り立つ。
【００７６】
【数５】
【００７７】
上式が近似であるのは、連続時間信号と離散時間信号に対するフーリエ変換の性質の違いに起因する。このとき、Ｆ(ｋ)とＧ(ｋ)の合成位相スペクトルＲ(ｋ)および１次元位相限定相関関数ｒ(ｎ)は次式で与えられる。
【００７８】
【数６】
【００７９】
ここで、α＝１、ｎ＝−Ｍ,..,Ｍである。上式は１次元画像信号がδだけ位置ずれした場合における１次元位相限定相関関数の一般形を表している。αは相関値のピークの高さを表現するために導入されたパラメータであり、画像にノイズが加わると、αの値が減少することが実験で確認されているため、実際にはα≦１となる。
【００８０】
δが整数の場合、式(１１)はデルタ関数となる。ただし、そのピークはｎ＝−δに位置し、ピークの高さはαとなる。実際の１次元位相限定相関関数ｒ(ｎ)の計算値から、このピークの位置を検出することにより、切り出した１次元画像信号ｆ(ｎ)とｇ(ｎ)の位置ずれδを検出することができる。すなわち、１次元画像信号ｆ(ｎ)における基準点ｐに対して、１次元画像信号ｇ(ｎ)におけるその対応点ｑは、対応点候補ｑ’とδを用いて次式のように求めることができる。
【００８１】
【数７】
【００８２】
ここで上式において、ｑおよびｑ’は直交座標系の位置ベクトルとして表現されているものとする。なお、その際、位置ずれδの方向を水平方向（ベクトル（１，０）の方向）にとっている。一般に、δが非整数（実数）の場合も、次節で述べるような、関数フィッティングなどの手法を用いてδを推定することによって、対応点ｑの座標をサブピクセル精度で求めることができる。
【００８３】
２．１次元位相限定相関法に基づく画像の対応付け手法の高精度化
本節では、前節で述べた基本手法をもとにして、それを発展させ、切り出した１次元画像信号ｆ(ｎ)とｇ(ｎ)の間の位置ずれ量を高精度に推定する手法を示す。
【００８４】
Ａ．位置ずれ量をサブピクセル精度で推定するための関数フィッティング手法
一般に、位置ずれ量δは実数値をとり、１次元位相限定相関関数のピーク座標はサンプリング格子点の間に存在するため、正確に位置ずれ量δを推定することが困難になる。そこで、１次元位相限定相関関数のピーク形状のモデルが式(１１)の右辺の関数で表わされることを考慮し、この関数そのもの、あるいは、式(１１)の右辺を近似的に表現する適当な関数（例えば、２次関数など）を、実際に計算された１次元位相限定相関関数の数値データに対してフィッティングすることによって、画像のピクセル間に存在するピークの位置を推定することができる。一般に、δ（および必要に応じてα）が推定されるパラメータとなる。
【００８５】
一例として、式(１１)の右辺に基づき、１次元位相限定相関関数の最大値とその周辺の数値データから、直接、δおよびαを推定する手法を示す。まず、１次元位相限定相関関数ｒ(ｎ)がｎ＝ａ（ａは整数）において最大値をとるものとする。このとき、ｒ(ａ)とその近傍ｒ（ａ−ｂ）およびｒ（ａ＋ｂ）の３つの値を用いて、δおよびαを推定することができる。ここで、ｂは−Ｍ≦ａ−ｂ＜ａ＜ａ＋ｂ≦Ｍを満たす小さい正の整数である。具体的には、δは次式から容易に求めることができる。
【００８６】
【数８】
【００８７】
ただし、ｕ(ａ，ｂ)とｖ(ａ，ｂ)は次式で与えられる。
【００８８】
【数９】
【００８９】
また、δと式(１１)により、αを求めることができる。上記の数式にはさまざまな近似表現が考えられ、実際には、この近似表現を用いて計算を簡単化できる。
【００９０】
ここで、上記はあくまで一例であり、計算された１次元位相限定相関関数の数値に対して、最小２乗法などを用いて適当な関数（２次関数など）をフィッティングすることにより、δ（および必要に応じてα）を高精度に推定することが可能である。なお、推定された相関ピークの高さαは、ｐとｑの対応付けの信頼性を表す尺度として使用することができる。αが大きい対応点ペア（ｐ，ｑ）のみを採用することにより、２つの画像から誤対応の少ない対応点ペアの集合を得ることができる。なお、αが非常に小さい場合は、ｇ( ｎ)上に対応点ｑが存在しないとみなすことができる。
【００９１】
Ｂ．離散フーリエ変換における不連続性を低減するための窓関数の適用
１次元離散フーリエ変換は信号が循環することを仮定するため、端点での信号の不連続性が問題となる。この不連続性の影響を低減するため、入力された１次元画像信号ｆ(ｎ)およびｇ(ｎ)に対して適当な窓関数（ハニング窓、ガウス窓など）を適用することが高精度化を実現する上で重要である。
【００９２】
例えば、窓関数の一例としては、次のようなハニング窓があげられる。
【００９３】
【数１０】
【００９４】
Ｃ．スペクトル重み付け関数の適用
一般に、自然画像の場合、そのエネルギーは低周波成分に集中し、高周波成分のエネルギーは相対的に小さいことが知られている。このため、エイリアシング、ぼけ、雑音、歪みなどの影響により高周波成分に外乱が加わると、画像の高周波成分のＳ／Ｎ比が大幅に劣化する。そこで、信頼性の低い高周波成分の影響を抑制するためにスペクトル重み付け関数を適用する。
【００９５】
具体的には、任意の特性を持つスペクトル重み付け関数Ｈ(ｋ)を合成位相スペクトルＲ(ｋ)に乗じることにより、周波数成分ごとに重み付けを行う。なお、通常は、低域通過型のスペクトル重み付け関数（方形フィルタ、ガウスフィルタなど）を適用し、信頼性の低い高周波成分の除去を行うと効果的である。ただし、スペクトル重み付け関数Ｈ(ｋ)を用いる場合、１次元位相限定相関関数ｒ(ｎ)はＨ(ｋ)・Ｒ(ｋ)の１次元逆離散フーリエ変換として定義されるため、そのピーク形状のモデルが式(１１)とは異なる。そこで、Ｈ(ｋ)に応じて異なるピーク形状のモデルを用いる必要がある。ただし、その場合も、基本的には本稿で述べる各種の手法が適用可能である。
【００９６】
例えば、最も単純なスペクトル重み付け関数Ｈ(ｋ)の一例として、次のようなものが考えられる。
【００９７】
【数１１】
【００９８】
ただし、０＜Ｕ≦Ｍである。このスペクトル重み付け関数を用いた場合、１次元位相限定相関関数ｒ(ｎ)のモデル式(１１)に対応するピーク形状のモデルは次式で与えられる。
【００９９】
【数１２】
【０１００】
ただし、Ｖ＝２Ｕ＋１である。したがって、前記項目Ａの関数フィッティングは、上式を想定して行う必要がある。このように、本稿で提案する手法は、スペクトル重み付け関数Ｈ(ｋ)に応じて異なるピーク形状のモデルを用いるように一般化することができる。
【０１０１】
Ｄ．１次元帯域制限位相限定相関関数の適用
信頼性の低い高周波成分の影響を排除するためにスペクトル重み付け関数を用いる代わりに、帯域制限型の位相限定相関関数を使用することも可能である。１次元帯域制限位相限定相関関数は式(６)を次のように変更したものである。
【０１０２】
【数１３】
【０１０３】
ただし、０＜Ｋ≦ＭおよびＬ＝２Ｋ＋１である。すなわち、１次元位相限定相関関数ｒ(ｎ)の計算に含まれる１次元逆離散フーリエ変換の定義域を信号の有効帯域（ｋ＝−Ｋ,..,Ｋ）にあわせて制限したものが１次元帯域制限位相限定相関関数である。式(１１)に対応するピーク形状のモデルは次式で与えられる。
【０１０４】
【数１４】
【０１０５】
なお、１次元帯域制限位相限定相関関数を用いた場合、相関ピークの位置はｎ＝−（Ｌ／Ｎ）δで与えられることに注意する必要がある。前記項目Ａの関数フィッティングは上式を想定して行うように容易に一般化できる。
【０１０６】
Ｅ．複数の１次元画像信号の利用による高信頼化
これまで、画像１における基準点ｐを中心として抽出した１次元画像信号ｆ(ｎ)と画像２における対応候補点ｑ’を中心として抽出した１次元画像信号ｇ(ｎ)を用いて、その位置ずれ量δを推定することにより、真の対応点ｑを求める手法について示してきた。しかし、実際に撮影した画像を用いた場合、ひと組の１次元画像信号を用いただけでは、高い信頼性でピークの位置を判定することはきわめて難しい。そこで以下では、複数の１次元画像信号の組を対応点の近傍から抽出し、それらの相関計算の結果を統合することによって、より信頼性の高いピーク位置の推定を行う方法について述べる。
【０１０７】
まず、画像１の基準点ｐの周辺からＢ個の１次元画像信号ｆi (ｎ)（ｉ＝１，２,..,Ｂ）を抽出する。一方、画像２の点ｑ’の周辺の対応する位置からもＢ個の１次元画像信号ｇi (ｎ)（ｉ＝１，２,..,Ｂ）を抽出する。例えば、図１４(a)に、ｆi (ｎ)とｇi (ｎ )の選び方の一例を示す。この例ではＢ＝５としており、ｐとｑ’の周辺から規則正しい配置で、１次元画像信号ｆi (ｎ)とｇi (ｎ)をそれぞれ５つずつ抽出している。これらの５つの１次元画像信号の対から位置ずれ量δを高精度に推定することによって、基準点ｐに対応する真の対応点ｑを求めることができる。
【０１０８】
１次元画像信号ｆi (ｎ)とｇi (ｎ)の１次元位相限定相関関数をｒi (ｎ)と表記するものとする。ただし、ｉ＝１，２,..,Ｂである。これらＢ個の１次元位相限定相関関数ｒi (ｎ)の重み付き平均として、累積相関関数ｒall (ｎ)を定義する。
【０１０９】
【数１５】
【０１１０】
ここで、ｗi はｒi (ｎ)に付随する重み係数であり、任意の定数に選ぶことができる。このように定義されたｒall (ｎ)は重み付き平均化された１次元位相限定相関関数である。ｒi (ｎ)およびｒall (ｎ)に対して、基本的にこれまでに述べてきたすべての高精度化手法を適用することができる。すなわち、これまでに述べてきた単一の１次元位相限定相関関数ｒ(ｎ)を用いた議論は、容易にｒi (ｎ)およびｒall (ｎ)を用いるように拡張することが可能である。
【０１１１】
なお、計算量を減少させる手法として次のようなことが考えられる。１次元画像信号ｆi (ｎ)とｇi (ｎ)の合成位相スペクトルをＲi (ｋ)と表記し、累積合成位相スペクトルＲall (ｋ)を次式で定義する。
【０１１２】
【数１６】
【０１１３】
このとき、ｒall (ｎ)はＲall (ｋ)の１次元逆離散フーリエ変換であるため、あらかじめＲall (ｋ)を計算してから、これを１次元逆離散フーリエ変換してｒall (ｎ)を計算することができる。Ｂが大きい場合は、この計算法は、Ｒi (ｋ)をｒi (ｎ)に個別に１次元逆離散フーリエ変換するよりも計算量が少ない。
【０１１４】
なお、ここで述べた手法は、さまざまなやり方で一般化することができる。２つの重要な拡張について以下に示す。
【０１１５】
・ｒi (ｎ)（ｉ＝１，２,..,Ｂ）からｒall (ｎ)への統合の仕方としては、式(２１)で定義した線形結合のほかにも多様な方法が考えられる。一般に、ｒi (ｎ)を適当な非線形オペレータで結合したものをｒall (ｎ)として用いることができる。
【０１１６】
・１次元画像信号ｆi (ｎ)およびｇi (ｎ)の選び方としては、図１４（ａ）のような規則的な配置である必要はなく、例えば、図１４（ｂ）のような例も含めて、任意の配置を取ることができる。また、必ずしもＢ個の１次元画像信号が同一の長さをもつ必要もない。その一例を図１４（ｃ）、（ｄ）に示す。Ｂ個の１次元画像信号が異なる長さを持つ場合は、Ｂ個のｒi (ｎ)も異なる長さを持つことになる。
【０１１７】
この場合は、式（２１）のｒi (ｎ)の加算において、基準となる位置（例えばｎ＝０）を合わせて加算することによってｒall (ｎ)を求めることができる。このような自由度を積極的に利用すると、画像に含まれるオブジェクトの境界（エッジ）をまたがないように１次元画像信号を抽出するなどの方法により、対応付けの精度を大幅に向上できる。図１４（ｅ）は、そのような１次元画像信号の配置の一例を示している。この例では、オブジェクト境界に、１次元画像信号の端点を合わせて配置している。
【０１１８】
以上、述べてきた手法Ａ〜Ｅは、用途に応じてさまざまに組み合わせることができる。
【０１１９】
３．１次元位相限定相関法と階層探索の組合せによる画像の対応付け手法
以下では、図１５に示すように、基準点ｐと対応候補点ｑ’の周辺から１次元画像信号ｆi (ｎ)およびｇi (ｎ)（ｉ＝１，２,..,Ｂ）を抽出する単純な場合を考える。ただし、以下で述べる手法は、他の場合についても容易に拡張することができる。
【０１２０】
このとき、図１５に示す破線で示したＮ×Ｂピクセルの画像領域を探索ウィンドウと呼ぶことにする。これまでに述べてきた手法では、探索ウィンドウ内の対応候補点ｑ’の付近に真の対応点ｑが存在すると暗に仮定してきた。この仮定を現実のステレオ画像の対応付けの際に常に成立させるための手法として、ここでは、１次元位相限定相関法による対応付けと粗密戦略に基づく階層探索との組合せについて述べる。これにより、一般的なステレオカメラなどから取得される画像ペアについてロバストな対応付けが可能になる。
【０１２１】
ここで記述するアルゴリズムは、すでに述べてきたように、対応付けを行う２枚の画像（画像１と画像２）を、そのエピポーラ線が平行になるように幾何補正（平行化）したうえで、画像１の基準点ｐに対応する画像２の対応点ｑを探し、それが存在する場合には、その座標をサブピクセルの分解能で返すものである。画像１の全域にわたって基準点ｐを変化させながら、このアルゴリズムによって対応点ｑを探索することによって、画像１と画像２の全体について、サブピクセル分解能の対応付けを行うことができる。
【０１２２】
この対応点の探索において粗密戦略を使用する。図１６に多重解像度画像を用いた場合の粗密戦略による階層探索の概念図を示す。多重解像度画像を用いて粗密戦略を行う場合、通常は探索ウィンドウのサイズ（Ｎ×Ｂピクセル）を固定し、画像１および画像２のそれぞれについて、解像度を段階的に低下させた複数の低解像度画像を準備して階層探索することにより、画像に対する相対的な探索の範囲を階層ごとに変更することが可能である。
【０１２３】
ただし、多重解像度画像を用いることは、粗密戦略においては必須ではなく、単純に、原画像上で探索ウィンドウのサイズを段階的に変更（徐々に縮小）しつつ階層探索することによって、対応点ｑの候補位置を絞っていくことも可能である。以下に、多重解像度画像を用いた場合の対応点探索アルゴリズムを示す。なお、全ての探索はエピポーラ線上（平行化した画像における同一の水平線上）で行う。
【０１２４】
１次元位相限定相関法と階層探索の組合せによる画像の対応付けアルゴリズム
（多重解像度画像を用いた場合）
【０１２５】
入力:
・画像１および画像２（あらかじめ平行化しておく）
・画像１における基準点ｐ（座標ベクトルをｐで表す）
【０１２６】
出力:
・画像２における対応点ｑ（座標ベクトルをｑで表す）
ただし、信頼できる対応点が存在しない場合は「対応点なし」を出力する。
【０１２７】
処理手順:
Step１：多重解像度画像を生成する。上位階層を低解像度画像とし、下位階層を高解像度画像とする。最下位の階層を原画像とする。なお、以下では、基準点ｐ、対応点ｑ、対応候補点ｑ’は、すべて原画像（画像１および画像２）に換算した画像座標系上の位置ベクトルで表現されているものとする。すなわち、上位階層の低解像度画像においては、その点の位置を原画像の座標系に換算して表示するものとする。また、画像１および画像２は共通の画像座標系上で定義されているものとする。
【０１２８】
Step２：最も解像度の低い最上位階層において、対応候補点の初期値をｑ’←ｐとして探索を開始する。すなわち、この仮定が成り立つために十分な階層の数を設定するものとする。現在の探索階層を最上位階層に設定する。
【０１２９】
Step３：現在の探索階層において、基準点ｐおよび対応候補点ｑ’を中心として、画像１および画像２の探索ウィンドウを設定し、前節までに述べてきた１次元位相限定相関法を用いて位置ずれ量δを高精度に推定する。
【０１３０】
Step４：この位置ずれ量δをもとにして、探索候補点ｑ’を次式によって更新する。
【０１３１】
【数１７】
【０１３２】
これは真の対応点を求める式(１２)に対応する。現在の探索階層が最下位階層（原画像階層）の場合は、Step５に進み、そうでない場合は、現在の探索階層を、ひとつ下の階層に設定し、Step３に進む。
【０１３３】
Step５：最下位階層（原画像階層）において、基準点ｐおよび対応候補点ｑ’を中心として、画像１および画像２の探索ウィンドウを設定する。なお、この際に、適当な補間技術を用いて、探索ウィンドウの位置をサブピクセル精度で調整する。前節までに述べてきた１次元位相限定相関法を用いて位置ずれ量δをサブピクセル精度で推定する。
【０１３４】
Step６：この位置ずれ量δをもとにして、探索候補点ｑ’を次式によって更新する。
【０１３５】
【数１８】
【０１３６】
Step５〜Step６を、位置ずれ量δが十分小さな値になるまで繰り返す。位置ずれ量δが微小な値に収束すればStep７へ進む。位置ずれ量δが微小な値に収束しない場合には、「対応点なし」を出力して終了する。なお、このステップは位置ずれ量δの値によらず、一定回数繰り返し、Step７へ進んでも良い。
【０１３７】
Step７：相関計算におけるピークの値αが小さい場合は、「対応点なし」を出力して終了する。それ以外の場合は、ｑ←ｑ’としてｑを出力して終了する。
【０１３８】
ここで述べたアルゴリズムは、図１５に示す標準的な１次元画像信号の配置を想定しているが、これは容易に一般化できる。また、階層探索の方法などについては、一般のブロックマッチングと同様にさまざまな拡張が考えられる。
【０１３９】
３．提案手法を用いた３次元計測システムの構成
前節で記述した画像の対応付けアルゴリズムは画像１の基準点ｐに対する画像２の対応点ｑを探索するものである。この基準点ｐを画像１の全域にわたって変化させながら対応点を探索することによって、画像の全体についてサブピクセル分解能の対応付けを行うことができる。この対応付け手法を（２つ以上の）複数のカメラを使用するステレオビジョンシステムに適用すると、きわめて高精度な受動型３次元計測システムを構築することができる。
【０１４０】
一般に、複数のカメラを使用する受動型のステレオビジョンシステムにおいて、３次元計測を行う２つのステレオカメラの間の距離（基線長）は、その計測性能を決定する重要なパラメータであり、次のようなトレードオフが存在する。
【０１４１】
・基線長の長いステレオカメラの場合：
３次元点の計測精度が高いという利点があるが、２つのステレオカメラの間の画像変形が大きいため、対応点探索の自動化が難しい。しかも、得られる対応点は、画像中のエッジなどの特別な点に限られる。どちらかというと、幾何学的な人工物には適用できるが、人間の顔のような自然物に適用することはきわめて困難であり、一般に汎用性がない。
【０１４２】
・基線長の短いステレオカメラの場合：
２つのステレオカメラの間の画像変形が小さいため、対応点探索の自動化が比較的容易であり、汎用性のあるシステムを構築できるポテンシャルを有する。しかし、通常のピクセル精度の対応づけアルゴリズムを用いた場合には、そもそも３次元計測精度がきわめて低く、ほとんど実用的ではない。
【０１４３】
以上のような理由により、従来の高精度なステレオビジョンシステムでは、基線長の長いステレオカメラを用いることがほとんどであり、ごく限られた用途にしか適用できず、実用上のインパクトが少なかった。しかし、本願で提案する画像の対応付け手法は、対応点の座標を安定に高いサブピクセル分解能で求めることが可能であり、短い基線長のステレオカメラに適用した場合も、高い計測精度を実現することが可能である。
【０１４４】
図１７に、提案する対応付けアルゴリズムを用いた３次元計測の流れを示す。ここでは、２つのカメラを用いた受動型のステレオビジョンシステムを想定しているが、これは、容易に３つ以上のカメラを用いる場合にも拡張できる。まず、あらかじめカメラ校正を行いステレオカメラシステムのカメラパラメータ（内部行列および外部行列）を取得しておくものとする（非特許文献２、４、８参照）。
【０１４５】
３次元計測の流れは、(i)ステレオ画像の撮影、(ii)ステレオ画像の幾何補正、(iii)ステレオ画像の対応付け、(iv)３次元復元の４ステップからなる。特に、ステレオ画像の対応付けステップにおいて、相関ピークの値αが大きい対応点ペアのみを出力することで、最終的に信頼性の高い高精度な３次元点群を得ることができる。
【０１４６】
４．提案手法を用いた３次元計測システムの評価
３次元計測システムを構築し、従来の対応付け手法と１次元位相限定相関法による対応付け手法との性能比較を行う。以下に性能評価を行う４つの手法を示す。
【０１４７】
・１次元位相限定相関法を用いる対応付け手法：本請求で提案する手法である。対応点の座標を安定に高いサブピクセル分解能で求めることができる。また、その際に必要とする計算量を少なく抑えることが可能である。
【０１４８】
・２次元位相限定相関法を用いる対応付け手法：画像の２次元離散フーリエ変換の位相情報を用いた対応付け手法であり、サブピクセル精度で２枚の画像を対応付けることが可能である（非特許文献５、６、７参照）。しかし、２次元フーリエ変換に起因する計算量が大きいことが問題となっている。
【０１４９】
・輝度差の総和法(SumofAbsoluteDifferences:ＳＡＤ）を用いる対応付け手法：ＳＡＤは次式で定義される（非特許文献２、３参照）。
【０１５０】
【数１９】
【０１５１】
ここで、Ｉ（ｎ1，ｎ2）およびＪ（ｎ1，ｎ2）は、ＳＡＤによって対応付けを行う画像１および画像２の画像ブロックである。また、画像ブロックのサイズをＮ1×Ｎ2ピクセルとする。加減算のみで計算を行うことができるため、高速処理を実現することが容易である。しかし、対応付け精度が極めて低いという問題がある。なお、対応点座標のサブピクセル推定のために等角直線フィッティングを行う手法を用いた（非特許文献２参照）。
【０１５２】
・輝度差の２乗和法（SumofSquaredDifferences:ＳＳＤ）を用いる対応付け手法：ＳＳＤは次式で定義される（非特許文献２、３、４参照）。
【０１５３】
【数２０】
【０１５４】
ここで、Ｉ（ｎ1，ｎ2）およびＪ（ｎ1，ｎ2）は、ＳＳＤによって対応付けを行う画像１および画像２の画像ブロックである。また、画像ブロックのサイズをＮ1×Ｎ2ピクセルとする。ＳＡＤと比較して計算量は増大するが、若干良い対応付け結果を得ることができる。なお、対応点座標のサブピクセル推定のためにパラボラフィッティングを行う手法を用いた（非特許文献２参照）。
【０１５５】
Ａ．計算量の評価
上で述べたように、１次元位相限定相関法と３つの従来手法との計算量の比較を行う。ここでは、対応点を１点だけ見つけるために必要となる計算量を比較する。１次元位相限定相関法を用いる場合には、前節で述べたようにＮピクセルの１次元画像信号をＢ個切り出して探索ウィンドウとする。ただし、簡単のためＮは２のべき乗とする。
【０１５６】
一方、２次元位相限定相関法を用いる対応付け手法において、切り出す画像ブロックのサイズをＮ1×Ｎ2ピクセルとする。ただし、Ｎ1およびＮ2は２のべき乗とする。なお、２次元離散フーリエ変換の計算においては、１次元高速フーリエ変換（ＦＦＴ）を利用した行列分解法を用いるものとする。また、１回の複素数乗算は４回の実数乗算と２回の実数加算として数え、複素数加算は２回の実数加算として数える。
【０１５７】
同様に、ＳＡＤ（あるいはＳＳＤ）を用いる対応付け手法においては、切り出す画像ブロックのサイズをＮ1×Ｎ2ピクセルとし、１点の探索に要するＳＡＤ（あるいはＳＳＤ）の計算回数をＮ1 回とする。なお、計算量の比較を行うための具体的な数値例として、Ｎ＝３２、Ｂ＝５、Ｎ1＝３２、Ｎ2＝３２を想定する。これはステレオ画像の対応付けを行う際に用いる標準的な値である。
【０１５８】
乗算の計算回数は次式で示される。
・１次元位相限定相関法：２（２Ｂ＋１）Ｎｌｏｇ2Ｎ＋６ＢＮ＝４，４８０回
・２次元位相限定相関法：６Ｎ1Ｎ2ｌｏｇ2（Ｎ1，Ｎ2）＋６Ｎ1Ｎ2＝６７，５８４回
・ＳＡＤ：０回
・ＳＳＤ：Ｎ12Ｎ2＝３２，７６８回
【０１５９】
加算の計算回数は次式で示される。
・１次元位相限定相関法：３（２Ｂ＋１）Ｎｌｏｇ2Ｎ＋（５Ｂ−１）Ｎ＝６，０１６回
・２次元位相限定相関法：９Ｎ1Ｎ2ｌｏｇ2（Ｎ1Ｎ2）＋３Ｎ1Ｎ2＝９５，２３２回
・ＳＡＤ：Ｎ1（２Ｎ1Ｎ2−１）＝６５，５０４回
・ＳＳＤ：Ｎ1（Ｎ1Ｎ2−１）＝３２，７３６回
【０１６０】
除算の計算回数は次式で示される。
・１次元位相限定相関法：２ＢＮ＋２Ｎ＝３８４回
・２次元位相限定相関法：２Ｎ1Ｎ2＝２，０４８回
・ＳＡＤ：０回
・ＳＳＤ：０回
【０１６１】
平方根の計算回数は次式で示される。
・１次元位相限定相関法：ＢＮ＝１６０回
・２次元位相限定相関法：Ｎ1Ｎ2＝１，０２４回
・ＳＡＤ：０回
・ＳＳＤ：０回
【０１６２】
このように、ステレオ画像の対応付けに１次元位相限定相関法を用いることで、２次元位相限定相関法に対して計算量を極めて少なく抑えることができる。上記の標準的な数値例では、乗算回数を約１／１５に、加算回数を約１／１６に削減することが可能である。また、ＳＡＤおよびＳＳＤを用いる手法と比較しても、十分な高速性を実現できると予想される。
【０１６３】
Ｂ．３次元復元性能の比較
評価対象となる４つの対応付け手法と粗密戦略に基づく階層探索を組み合わせてステレオ画像の対応付けを行い、３次元復元を行った結果を比較する。各手法のパラメータについては、前記項目Ａと同様のパラメータを用いた。すなわち、Ｎ＝３２、Ｂ＝５、Ｎ1 ＝３２、Ｎ2 ＝３２とした。なお、階層探索を行う際の多重解像度画像の階層数を５階層とする。
【０１６４】
図１９に実験で用いたステレオビジョンシステムを示す。ステレオビジョンシステムでは、人物の顔を被写体とするために、図１９（ｂ）に示すようにステレオカメラヘッドのカメラ配置を縦置きにとっている。次に、各手法の３次元復元結果を図１８に示す。図１８（ａ）はステレオカメラヘッドから取得されたステレオ画像である。ただし、ステレオカメラヘッドは縦置きのカメラ配置であるため、エピポーラ線は画像の垂直座標と平行に走ることになる。
【０１６５】
そこで、実際の対応付けでは図１８（ａ）のステレオ画像を９０度回転することで、エピポーラ線を画像の水平座標と平行になるように補正した。つまり、図１３（ｂ）と同様の画像が得られる。まず、図１８（ｂ）は１次元位相限定相関法に基づく対応付け手法を用いた場合の３次元計測結果である。これに対して、図１８（ｃ）〜（ｅ）は、それぞれ、２次元位相限定相関法を用いた場合、ＳＡＤを用いた場合、ＳＳＤを用いた場合の３次元計測結果である。ＳＡＤとＳＳＤを用いた場合では、３次元点が階段状に復元されている。
【０１６６】
これは、対応付けの際に、十分なサブピクセル精度が得られていないためである。一方、１次元位相限定相関法と２次元位相限定相関法を用いた場合では、顔の３次元的な曲面形状が滑らかに復元されている。次に、顔のふち部分の３次元復元結果に着目すると、ＳＡＤやＳＳＤを用いた場合では、対応付けに失敗していることがわかる。一方、１次元位相限定相関法は２次元位相限定相関法と比べて探索ウィンドウのサイズを小さくとることでオブジェクト境界の影響を軽減できるため、顔のふち部分について３次元復元精度の向上が見られる。このように、１次元位相限定相関法を用いることで、人物の顔の３次元形状を従来手法よりも高精度に復元できることがわかる。
【図面の簡単な説明】
【０１６７】
【図１】本発明に係る対応点探索方法を利用した３次元位置計測装置の一実施の形態を示すブロック構成図である。
【図２】対象物を異なる視点から見た２つの画像に水平なラインとして存在するエピポーラ線を説明する図である。
【図３】対象物を異なる視点から見た２つの画像に傾斜したラインとして存在するエピポーラ線を説明する図である。
【図４】この３次元位置計測装置の画像取り込みから対象領域の抽出までの処理過程を説明する図である。
【図５】この３次元位置計測装置における３次元位置の計測処理を示すフローチャートである。
【図６】この３次元位置計測装置における３次元位置の計測処理過程での対応点探索処理を示すフローチャートである。
【図７】入力画像から抽出されたオブジェクト領域中の最上位の線の起点から対応点の探索が始められる様子を説明する図である。
【図８】基準点のデータ列と候補点のデータ列との１次元位相限定相関法による相関関数の計算を説明する図である。
【図９】探索ウィンドウに対して平行に複数組の近傍探索ウィンドウを定めて対応点の探索を行う例を説明する図である。
【図１０】探索ウィンドウに対して平行に複数組の近傍探索ウィンドウを定めて対応点の探索を行う場合の変形例を示す図である。
【図１１】探索ウィンドウに対して平行に複数組の近傍探索ウィンドウを定めて対応点の探索を行う場合の変形例を示す図である
【図１２】探索ウィンドウに対して平行に複数組の近傍探索ウィンドウを定めて対応点の探索を行う場合の変形例を示す図である
【図１３】平行化された２つの画像と１次元画像信号を説明するための図である。
【図１４】１次元画像信号の抽出を説明するための図である。
【図１５】探索ウィンドウの設定方法を説明するための図である。
【図１６】画像ピラミッドを用いたサブピクセル対応付けアルゴリズムの概要を説明するための図である。
【図１７】３次元計測の流れを例示するフローチャートである。
【図１８】顔の３次元復元結果を示す説明図である。
【図１９】３次元計測精度を評価する実験で用いたステレオビジョンシステムを示す説明図である。
【図２０】特許文献１に示された立体像計装置における画像入力部の概略を示す図である。
【図２１】特許文献１に示された立体像計装置における２次元位相限定相関法を用いた立体像の計測処理を説明する図である。
【符号の説明】
【０１６８】
１０、１１…カメラ（ＣＣＤカメラ）、１２…液晶表示装置（ＬＣＤ）、２０…処理部、２０−１…制御部、２０−２…ＲＯＭ、２０−３…ＲＡＭ、２０−４…ハードディスクドライブ（ＨＤＤ）、２０−５…フレームメモリ（ＦＭ）、２０−６…外部接続部（Ｉ／Ｆ）、２０−７…フーリエ変換部（ＦＦＴ）、ＬＮ（ＬＮ１、ＬＮ２）…レンズ、ＥＰ…エピポーラ線、ＳＷ（ＳＷ０）…探索ウィンドウ、ＳＷ１〜ＳＷ４…近傍探索ウィンドウ、ＣＷ（ＣＷ０）…探索ウィンドウ、ＣＷ１〜ＣＷ４…近傍探索ウィンドウ、ＯＢ１、ＯＢ２…オブジェクト領域、ＳＴ…起点、ＥＮＤ…終点、Ｉ…入力画像、Ｊ…参照画像、Ｍ…対象物。
【技術分野】
【０００１】
この発明は、立体的な物体、例えば人間の顔などを対象物とし、この対象物を異なる視点から見た複数の画像中の対応点を探索する対応点探索方法およびこの対応点探索方法を利用した３次元位置計測方法に関するものである。
【背景技術】
【０００２】
従来より、対象物を異なる視点から見た複数の画像中の対応点の探索は、画像センシング、画像・映像信号処理、コンピュータビジョン等の様々な分野で重要な技術とされている。これらの分野では、通常、ピクセル精度の対応付け手法を用いることが多いが、近年、サブピクセル精度の対応付け手法への要求が高まっている。
【０００３】
例えば、基線長の短いステレオビジョンシステムにおいて、十分な３次元計測精度を実現するためには、サブピクセル精度の対応付けアルゴリズムが不可欠である。また、超解像による映像の高解像度化技術などにおいても、サブピクセル精度の対応付けアルゴリズムが重要になる。このため、例えば特許文献１に示された立体像計測装置では、対象物を異なる視点から見た複数の画像中の対応点の探索を２次元位相限定相関法を用いて行うことにより、サブピクセル精度の対応付けの要求を満たしている。
【０００４】
図２０は上述の特許文献１に示された立体像計装置における画像入力部の概略を示す図である。同図において、１は第１のカメラ、２は第２のカメラ、Ｍは対象物（人間の顔）である。カメラ１，２は、そのレンズＬＮ１，ＬＮ２間の距離をＬとして、横方向に並んで配置されている。図では分かり易いように、カメラ１および２を上方向から見た図とし、対象物Ｍは横方向から見た図としている。
【０００５】
この立体像計測装置では、対象物Ｍをカメラ１で捉えた画像を入力画像Ｉ（図２１（ａ））とし、この入力画像Ｉの画像データをｍ×ｎ個の局所領域Ｉ（ｉ，ｊ）に分割する（図２１（ｂ））。そして、入力画像Ｉの画像データから局所領域Ｉ（ｉ，ｊ）を切り出し、この切り出した局所領域Ｉ（ｉ，ｊ）の画像データに２次元離散的フーリエ変換（ＤＦＴ）を施してフーリエ画像データ（入力フーリエ画像データ）を得る。
【０００６】
また、対象物Ｍをカメラ２で捉えた画像を参照画像Ｊ（図２１（ｃ））とし、この参照画像Ｊの画像データに２次元離散的フーリエ変換を施してフーリエ画像データ（参照フーリエ画像データ）を得る。
【０００７】
そして、この得られた入力フーリエ画像データと参照フーリエ画像データとを合成し、この合成したフーリエ画像データ（合成フーリエ画像データ）の振幅成分を正規化して、もう一度、２次元離散的フーリエ変換（もしくは２次元離散的逆フーリエ変換）を施す。
【０００８】
そして、この２次元離散的フーリエ変換が施された合成フーリエ画像データより所定の相関成分エリアの各画素の相関成分の強度（振幅）を求め、この相関成分エリア内の最も強度の高い画素の位置を相関ピークの位置Ｐａ１（図２１（ｄ））とする。
【０００９】
この場合、相関成分エリアの中心Ｐ０から相関ピークの位置Ｐａ１までの距離Ａが、入力画像Ｉの画像データにおける局所領域Ｉ（ｉ，ｊ）と参照画像Ｊの画像データにおける一致する画像データのある領域（対応領域）とのずれ量を示す。入力画像Ｉにおける局所領域Ｉ（ｉ，ｊ）中の画像と参照画像Ｊにおける対応領域中の画像とは視差によってその画像がずれており、これがずれ量Ａとして現れる。
【００１０】
このずれ量Ａによって、入力画像中の局所領域Ｉ（ｉ，ｊ）の中心点（基準点）と、参照画像Ｊ中の対応領域の中心点（対応点）とを対応付け、三角測量の原理に基づく下記（１）式によって、カメラから対象物Ｍの対応点（基準点）までの距離Ｒを計算する。なお、下記（１）式において、ｆはレンズＬＮ（ＬＮ１，ＬＮ２）の中心から撮像位置までの距離、Ｌはレンズ間距離である。
Ｒ＝ｆ・Ｌ／Ａ ・・・・（１）
【００１１】
【特許文献１】特開平１０−１３２５３４号公報
【非特許文献１】「写真から作る３次元ＣＧ」、著者：徐剛、発行所：株式会社 近代科学社、２００３年２月２５日 初版第２刷発行、３１〜３３頁。
【非特許文献２】ディジタル画像処理編集委員会、“ディジタル画像処理”、CG-ARTS協会、２００５。
【非特許文献３】D. Scharstein and R. Szeliski. “A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms”, IJCV ４７(１/２/３):７-４２, April-June ２００２.
【非特許文献４】Yi Ma, Stefano Soatto, Jana Kosecka, S. Shankar Sastry, “An Invitation to ３-D Vision: From Images to Geometric Models (Interdisciplinary Applied Mathematics)”, Springer, ２００４.
【非特許文献５】K. Takita, T. Aoki, Y. Sasaki, T. Higuchi, and K. Kobayashi, “High-accuracy subpixel image registration based on phase-only correlation,” IEICE Trans. Fundamentals, vol. E８６-A, no. ８, pp. １９２５-１９３４, Aug. ２００３.
【非特許文献６】K. Takita, M. A. Muquit, T. Aoki, and T. Higuchi, “A sub-pixel correspondence search technique for computer vision applications,” IEICE Trans. Fundamentals, vol. E８７-A, no. ８, pp. １９１３-１９２３, Aug. ２００４.
【非特許文献７】M. A. Muquit, T. Shibahara, and T. Aoki, “A high-accuracy passive ３D measurement system using phase-based image matching,” IEICE Trans. Fundamentals,vol.E８９-A, no. ３, pp. ６８６-６９７, Mar. ２００６.
【非特許文献８】徐 剛, 辻 三郎、“３次元ビジョン” 、共立出版、１９９８。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
上述した特許文献１に示された手法は、対応付けの精度が極めて高く、様々な画像に対して同一のアルゴリズムが適用できるという長所がある。しかしながら、この手法は、２次元離散的フーリエ変換に要する計算量が多く、短時間で対応付けの結果を得ることが要求される分野では採用し難いという問題があった。
【００１３】
本発明は、このような課題を解決するためになされたもので、その目的とするところは、対応点の探索に要する計算量を大幅に減らし、短時間でかつ高精度に、対応付けの結果を得ることが可能な対応点探索方法および３次元位置計測方法を提供することにある。
【課題を解決するための手段】
【００１４】
このような目的を達成するために、本発明に係る対応点探索方法（請求項１（第１発明））は、画像取込手段を介して、対象物を異なる視点から見た複数の画像を取り込む画像取込ステップと、画像取込手段のパラメータおよび基準点から計算されるエピポーラ線に沿って複数の画像より１次元の画素データ列を切り出す画素データ列切出ステップと、複数の画像から切り出された１次元の画素データ列の相関から複数の画像中の対応点を探索する対応点探索ステップとを設けたものである。
【００１５】
この発明において、例えば、画像取込手段を所定の距離隔てて配置された２台のカメラとした場合、第１のカメラと第２のカメラが対象物に対して等位置に傾斜なく配置されていれば、第１のカメラで撮像される画像および第２のカメラで撮像される画像におけるエピポーラ線は、いずれも水平となる。これに対し、第１のカメラおよび第２のカメラの何れかが傾斜していれば、第１のカメラで撮像される画像および第２のカメラで撮像される画像におけるエピポーラ線も傾斜する。このように、第１のカメラで撮像される画像および第２のカメラで撮像される画像におけるエピポーラ線は、第１および第２のカメラの位置関係（２つの画像間の基礎行列や、内部行列・外部行列などのカメラ固有のパラメータ）によって定まる。本発明では、このような画像取込手段のパラメータを保存しておき、対応点を探索する際の処理過程で用いる。
【００１６】
本発明において、画像取込手段は、複数台のカメラに限られるものではない。例えば、光学機構を設けることによって、１台のカメラから対象物を異なる視点から見た複数の画像を得るようにしてもよい。
【００１７】
本発明において、複数の画像のうちの１つを入力画像、もう１つを参照画像とした場合、画像取込手段のパラメータおよび基準点から計算されるエピポーラ線に沿って、入力画像および参照画像より１次元の画素データ列（例えば、３２画素の画素データ列）が切り出される。そして、このエピポーラ線に沿って切り出された１次元の画素データ列の相関から、入力画像中の基準点に対応する参照画像中の対応点が探索され、基準点と対応点とが対応付けられる。
【００１８】
この場合、基準点の画素データ列は１次元の画素データ列であり、参照画像中の画素データ列も１次元の画素データ列であるので、１次元の位相限定相関法（１次元ＰＯＣ）を利用することができる。すなわち、複数の画像から切り出された１次元の画素データ列から位相限定相関相関を計算することによって得られる相関ピークの位置から位置ずれ量を求め、この位置ずれ量から複数の画像中の対応点を探索することが可能である。
【００１９】
１次元ＰＯＣでは、１次元のフーリエ変換を施せばよいので、計算量を大幅に減らすことができる。これにより、対応点の探索に要する計算量が大幅に減り、短時間で対応付けの結果を得ることが可能となる。また、１次元ＰＯＣを用いることにより、エピポーラ線の垂直方向の相関誤差要因を少なくすることができ、高精度な対応点探索が可能となる。
【００２０】
本発明において、画像取込手段を介して取り込まれる画像に存在するエピポーラ線は水平であるとは限らず、傾斜している場合もある。理想的には水平であることが望まれるが、カメラの取り付け誤差などもあり、エピポーラ線は傾斜している場合が多い。
そこで、第２発明（請求項２に係る発明）では、複数の画像中の各画素データを、画像取込手段のパラメータおよび基準点から計算されるエピポーラ線に平行な軸を一軸とし、この一軸に対して垂直な軸を他軸とする座標系に変換し、この座標系が変換された複数の画像から１次元の画素データ列を切り出すようにする。なお、このような座標系の変換は必ずしも必要ではなく、エピポーラ線が傾斜した座標系のまま処理を進めて、対応点の探索を行うようにしてもよい。座標系を変換することにより、以降の処理が簡単となる。
【００２１】
本発明では、エピポーラ線に沿って複数の画像より１次元の画素データ列を切り出し、この切り出した１次元の画素データ列の相関から対応点を探索するが、その１次元の画素データ列の近傍のエピポーラ線に平行な線に沿う１次元の画素データ列を複数の画像から切り出し、これら複数組の１次元の画素データ列の相関から対応点を探索するようにしてもよい（第３発明（請求項３に係る発明））。このようにすると、ノイズの影響を受け難くなり、対応点探索の性能がより安定する。
【００２２】
また、複数の画像から対応点探索の対象領域としてオブジェクト領域を抽出するようにし、この複数の画像から抽出されたオブジェクト領域よりエピポーラ線に沿って１次元の画素データ列を切り出すようにしてもよい（第４発明（請求項４に係る発明））。画像内のオブジェクト領域外の画素データを処理対象から除外することで、これらの領域が対応点探索過程で精度を下げる外乱要因として働くことを未然に防止し、対応点探索精度の向上を図ることが可能となる。また、オブジェクト領域を対応点探索の対象領域とすることにより、次々に対応点の探索を行うような場合、基準点をずらす領域を狭め、処理すべきデータ量を削減することができる。
【００２３】
また、本発明の対応点探索方法を利用することにより、探索した対応点の３次元位置を計測することも可能である。請求項５に係る発明（第５発明）は、探索した対応点の３次元位置を計測する３次元位置計測方法に関するものであり、第１発明によって探索された対応点の視差に基づいてその対応点の３次元位置を計測する。これにより、対応点の探索に要する計算量を大幅に減らし、対象物における各点の３次元位置を短時間で計測することが可能となる。
【発明の効果】
【００２４】
本発明によれば、画像取込手段を介して、対象物を異なる視点から見た複数の画像を取り込み、画像取込手段のパラメータおよび基準点から計算されるエピポーラ線に沿って複数の画像より１次元の画素データ列を切り出し、複数の画像から切り出された１次元の画素データ列の相関から複数の画像中の対応点を探索するようにしたので、１次元ＰＯＣを利用することができ、対応点の探索に要する計算量を大幅に減らし、短時間で対応付けの結果を得ることが可能となる。また、１次元ＰＯＣを用いることにより、エピポーラ線の垂直方向の相関誤差要因を少なくすることができ、高精度な対応点探索が可能となる。
【発明を実施するための最良の形態】
【００２５】
以下、本発明を図面に基づいて詳細に説明する。図１はこの発明に係る対応点探索方法を利用した３次元位置計測装置の一実施の形態を示すブロック構成図である。同図において、１０は第１のカメラ（ＣＣＤカメラ）、１１は第２のカメラ（ＣＣＤカメラ）、１２は液晶表示装置（ＬＣＤ）、２０は処理部であり、処理部２０は、ＣＰＵを有する制御部２０−１と、ＲＯＭ２０−２と、ＲＡＭ２０−３と、ハードディスクドライブ（ＨＤＤ）２０−４と、フレームメモリ（ＦＭ）２０−５と、外部接続部（Ｉ／Ｆ）２０−６と、フーリエ変換部（ＦＦＴ）２０−７とを備えており、ＲＯＭ２０−２には３次元位置計測プログラムが格納されている。
【００２６】
カメラ１０，１１は、図２０に示した従来例と同様に、所定の距離Ｌを隔てて設置されている。すなわち、カメラ１０，１１は、そのレンズＬＮ１，１Ｎ２間の距離をＬとして、横方向に並んで配置されている。この図でも分かり易いように、３次元位置計測装置は上方向から見た図とし、対象物Ｍは横方向から見た図としている。
【００２７】
〔カメラパラメータの保存〕
カメラ１０および１１は所定の距離Ｌを隔てて配置されている。このカメラ１０および１１が互いの光軸が平行且つ、画像座標の水平軸が同一直線上で同じ向きになるように配置されていれば、図２（ａ）および（ｂ）に示すように、カメラ１０で撮像される画像Ｉにおける基準点ｐが存在する直線ＥＰ１およびカメラ１１で撮像される画像Ｊにおける対応点ｑが存在する直線ＥＰ２、すなわちエピポーラ線ＥＰ１およびＥＰ２は、いずれも水平となる。なお、エピポーラ線については、非特許文献１などに解説されているので、ここでの詳細な説明は省略する。
【００２８】
これに対し、カメラ１０および１１の何れかが傾斜していれば、カメラ１０で撮像される画像Ｉおよびカメラ１１で撮像される画像Ｊにおけるエピポーラ線ＥＰ１，ＥＰ２も傾斜する（図３（ａ），（ｂ）参照）。このように、カメラ１０で撮像される画像Ｉおよびカメラ１１で撮像される画像Ｊにおけるエピポーラ線ＥＰ（ＥＰ１，ＥＰ２）は、カメラ１０とカメラ１１との位置関係（２つの画像間の基礎行列や、内部行列・外部行列などのカメラ固有のパラメータ）によって定まる。本実施の形態では、このカメラ１０とカメラ１１との位置関係を示すパラメータ（カメラパラメータ）をハードディスクに保存させておき、後述する対応点を探索する際の処理過程で用いる。
【００２９】
〔３次元位置の計測〕
この３次元位置計測装置において、対象物Ｍを人間の顔とした場合、この対象物Ｍにおける各点の３次元位置の計測は次のようにして行われる。この３次元位置の計測処理は、ＲＯＭ２０−２に格納された３次元位置計測プログラムに従って、制御部２０−１が行う。
【００３０】
〔画像取り込み〕
制御部２０−１は、カメラ１０からの対象物Ｍを捉えた画像Ｉを入力画像（図４（ａ））として取り込む（図５に示すステップ１０１）。また、カメラ１１からの対象物Ｍを捉えた画像Ｊ（図４（ｂ））を参照画像として取り込む（ステップ１０２）。
【００３１】
〔座標系の変換〕
そして、ハードディスクに保存されているカメラパラメータを読み出し、入力画像Ｉおよび参照画像Ｊ中の各画素データを、カメラパラメータおよび基準点から計算されるエピポーラ線ＥＰに平行な軸をＸ軸とし、このＸ軸に対して垂直な軸をＹ軸とする座標系に変換する（ステップ１０３）。この座標系が変換された入力画像Ｉおよび参照画像Ｊを入力画像Ｉ’および参照画像Ｊ’とする（図４（ｃ），（ｄ））。
【００３２】
〔対象領域の抽出〕
次に、エッジ検出により、入力画像Ｉ’および参照画像Ｊ’中から、対象物Ｍ（人間の顔）が存在する領域だけを対応点探索の対象領域（以下、オブジェクト領域と呼ぶ）として抽出する（ステップ１０４）。これにより、図４（ｅ）および（ｆ）に示されるように、オブジェクト領域ＯＢ１およびＯＢ２を抽出した入力画像Ｉ”および参照画像Ｊ”が得られる。
【００３３】
なお、ここでは、説明を簡単とするために、入力画像Ｉおよび参照画像Ｊにおける対象物Ｍ以外の背景は無地であり、対象物Ｍが存在する領域だけがオブジェクト領域ＯＢ１およびＯＢ２として正しく抽出されるものとする。
【００３４】
〔対応点の探索〕
そして、制御部２０−１は、入力画像Ｉ”中のオブジェクト領域ＯＢ１と参照画像Ｊ”中のオブジェクト領域ＯＢ２とを対象領域として、対応点の探索を行う（ステップ１０５）。図６にステップ１０５における対応点の探索処理のフローチャートを示す。制御部２０−１は、このフローチャートに従って、対応点の探索を次のようにして行う。
【００３５】
先ず、入力画像Ｉ”において、Ｘ軸に平行な各線（１画素幅の線）のオブジェクト領域ＯＢ１内の起点（ＳＴ）と終点（ＥＮＤ）を求める（ステップ２０１）。
【００３６】
そして、オブジェクト領域ＯＢ１中の最上位の線の線番号をｎ＝１とし（ステップ２０２）、このｎ＝１番目の線上に基準点ｐを定め、その基準点ｐを中心とする所定幅Ｗの探索ウィンドウＳＷの画素データ列を基準点ｐの画素データ列として抽出する（ステップ２０３）。この例では、ｎ＝１番目の線（以下、探索ラインと呼ぶ）の起点ＳＴ（図７（ａ）参照）から、幅Ｗを３２画素とする探索ウィンドウＳＷ内の画素のデータ列を基準点ｐの画素データ列として抽出する。
【００３７】
この場合、ｎ＝１番目の探索ラインが基準点ｐのエピポーラ線ＥＰであり、このエピポーラ線ＥＰに沿って基準点ｐの画素データ列が切り出されるものとなる。この基準点の画素データ列は１次元の画素のデータ列である。
【００３８】
また、オブジェクト領域ＯＢ２中の基準点ｐに対応する座標点を候補点ｑ’とし、この候補点ｑ’を中心とする幅Ｗ＝３２画素の探索ウィンドウＣＷを定め、探索ウィンドウＣＷ内の画素のデータ列を候補点ｑ’の画素データ列として抽出する（ステップ２０４）。
【００３９】
この場合、ｎ＝１番目の探索ラインが候補点ｑ’のエピポーラ線ＥＰであり、このエピポーラ線ＥＰに沿って候補点ｑ’の画素データ列が切り出されるものとなる。この候補点の画素データ列は１次元の画素のデータ列である。
【００４０】
そして、ステップ２０３で抽出した基準点ｐの画素データ列とステップ２０４で抽出した候補点ｑ’の画素データ列とから位相限定相関関数を計算する（ステップ２０５）。この位相限定相関関数の計算には１次元位相限定相関法（１次元ＰＯＣ）を用いる。この１次元ＰＯＣによる位相限定相関関数の計算は次のようにして行う。
【００４１】
制御部２０−１は、ステップ２０３で抽出した基準点ｐの画素データ列を第１の画像データＧ１とし（図８（ａ）参照）、この第１の画像データＧ１をフーリエ変換部２０−７へ送り、この第１の画像データＧ１に１次元のフーリエ変換を施す。これにより、第１の画像データＧ１は、フーリエ画像データＦ１となる。
【００４２】
また、ステップ２０４で抽出した候補点ｑ’の画素データ列を第２の画像データＧ２とし（図８（ｂ）参照）、この第２の画像データＧ２をフーリエ変換部２０−７へ送り、この第２の画像データＧ２に１次元のフーリエ変換を施す。これにより、第２の画像データＧ２は、フーリエ画像データＦ２となる。
【００４３】
そして、制御部２０−１は、フーリエ画像データＦ１とフーリエ画像データＦ２とを合成し、この合成したフーリエ画像データ（合成フーリエ画像データ）の振幅成分を正規化してフーリエ変換部２０−７へ送り、もう一度、１次元のフーリエ変換を施す。
【００４４】
そして、この１次元のフーリエ変換が施された合成フーリエ画像データより所定の相関成分エリアの各画素の相関成分の強度（振幅）を求め、この相関成分エリア内の最も強度の高い相関成分の強度値を相関ピークとし、この相関ピークの位置Ｐａ１（図８（ｃ））を求める。この処理過程において、相関ピークを求める処理が位相限定相関関数を計算することに対応する。
【００４５】
この場合、相関成分エリアの中心Ｐ０から相関ピークの位置Ｐａ１までの距離ｄが、探索ウィンドウＳＷ中の画像と探索ウィンドウＣＷ中の画像とのずれ量、すなわち探索ウィンドウＳＷ中の基準点ｐと探索ウィンドウＣＷ中の対応点ｑとのずれ量を示す。制御部２０−１は、この基準点ｐと対応点ｑとのずれ量ｄを基準点ｐに対応付けて記憶する（ステップ２０６）。
【００４６】
以下同様にして、制御部２０−１は、オブジェクト領域ＯＢ１中のｎ＝１番目の探索ライン上の基準点を所定画素（例えば、１画素）ずつずらしながら、すなわち探索ウィンドウＳＷを所定画素づつずらしながら（ステップ２０８）、同様の処理を繰り返す。
【００４７】
そして、オブジェクト領域ＯＢ１中のｎ＝１番目の探索ラインの終点ＥＮＤまで対応点の探索が完了すれば（ステップ２０７のＹＥＳ）、オブジェクト領域ＯＢ１中のｎ＝２番目の探索ラインの起点に探索ウィンドウＳＷを移す（ステップ２０９）。以下同様にして、オブジェクト領域ＯＢ１中の最後の探索ラインの終点まで、同様動作を繰り返す。
【００４８】
〔３次元位置の計測〕
制御部２０−１は、オブジェクト領域ＯＢ１中の全ての基準点について対応点の探索が完了すると（ステップ２１０のＹＥＳ）、各基準点と各対応点とのずれ量ｄに基づいて、三角測量の原理に基づく下記（２）式によって、カメラから対象物Ｍの対応点（基準点）までの距離Ｒを計算する（ステップ１０６（図５））。
Ｒ＝ｆ・Ｌ／ｄ ・・・・（２）
【００４９】
そして、この計算したカメラから対象物Ｍの対応点（基準点）までの距離Ｒを３次元位置の計測データとし、各点の３次元位置の計測データをハードディスクに記憶させる。このハードディスクに記憶させた３次元位置の計測データ群は、必要に応じて読み出し、ＬＣＤ１２の画面上に表示したり、上位の装置へ送ったりする。
【００５０】
以上の説明から分かるように、本実施の形態において、基準点ｐの画素データ列は１次元の画素データ列であり、この基準点ｐの画素データ列との相関を求める候補点ｑ’の画素データ列も１次元の画素データ列であり、この基準点ｐの画素データ列と候補点ｑ’の画素データ列から１次元ＰＯＣを利用して位相限定相関関数を計算するようにしている。１次元ＰＯＣでは、１次元のフーリエ変換を施すので、対応点の探索に要する計算量が大幅に減り、短時間で対応付けの結果を得ることができる。また、１次元ＰＯＣを用いることにより、エピポーラ線ＥＰに垂直方向の相関誤差要因を取り除くことが可能となり、高精度な対応点探索が可能となる。
【００５１】
なお、上述した実施の形態では、基準点ｐの探索ウィンドウＳＷと候補点ｑ’の探索ウィンドウＣＷの幅Ｗを同じとしたが、候補点ｑ’の探索ウィンドウＣＷの幅Ｗは基準点ｐの探索ウィンドウＳＷの幅Ｗ以上あればよく、１本の探索ラインの起点ＳＴから終点ＥＮＤまでの全ての範囲を探索ウィンドウＣＷとしてもよい。
【００５２】
また、上述した実施の形態では、エピポーラ線ＥＰに沿って各画像より１次元の画素データ列を切り出し、この切り出した１次元の画素データ列の位相限定相関関数から対応点を探索するが、その１次元の画素データ列の近傍のエピポーラ線ＥＰに平行な線に沿う１次元の画素データ列を各画像から切り出し、これら複数組の１次元の画素データ列の位相限定相関関数から対応点を探索するようにしてもよい。このようにすると、ノイズの影響を受け難くなり、より対応点探索性能が安定する。
【００５３】
例えば、図９に示すように、入力画像Ｉ”における探索ウィンドウＳＷ（ＳＷ０）に対して平行に、この探索ウィンドウＳＷ０と同じ位置から同じ長さの近傍探索ウィンドウＳＷ１〜ＳＷ４を定め、この探索ウィンドウＳＷ０および近傍探索ウィンドウＳＷ１〜ＳＷ４内の画素データ列と参照画像Ｊ”における探索ウィンドウＣＷ０および近傍探索ウィンドウＣＷ１〜ＣＢ４内の画素データ列の各組の相関値を求め、相関値の平均を計算する。平均された相関値の最大ピーク位置を求めることで基準点ｐと対応点ｑとのずれ量を算出する。
【００５４】
この場合、探索ウィンドウＳＷ０および近傍探索ウィンドウＳＷ１〜ＳＷ４内の画素データ列に１次元のフーリエ変換を施し、探索ウィンドウＣＷ０および近傍探索ウィンドウＣＷ１〜ＣＢ４内の画素データ列に１次元のフーリエ変換を施し、フーリエ変換が施された探索ウィンドウＳＷ０内の画素データ列と探索ウィンドウＣＷ０内の画素データ列とを合成し、同様にして、フーリエ変換が施された近傍探索ウィンドウＳＷ１〜ＳＷ４内の画素データ列と近傍探索ウィンドウＣＷ１〜ＣＢ４内の画素データ列とを各個に合成し、これにより得られる５つの合成フーリエ画像データを平均して合成位相スペクトルを作成し、この合成位相スペクトルに対して１次元のフーリエ変換を施して最大相関ピークの位置を求めるようにすれば、５つの合成フーリエ画像データの１つひとつに１次元のフーリエ変換を施して相関ピークの位置を求めるようにする方法と比較して、格段に処理スピードがアップする。
【００５５】
図９では、探索ウィンドウＳＷ０に対して平行に、画像の水平方向に同じ位置から同じ長さの近傍探索ウィンドウＳＷ１〜ＳＷ４を定めたが、図１０に示すように、画像の水平方向に異なる位置から同じ長さの近傍探索ウィンドウＳＷ１〜ＳＷ４を定めるようにしてもよい。また、図１１に示すように、画像の水平方向に異なる位置から異なる長さの近傍探索ウィンドウＳＷ１〜ＳＷ４を定めるようにしてもよい。また、図１２に示すように、画像の異なる位置から異なる長さの近傍探索ウィンドウＳＷ１〜ＳＷ４を定めるようにしてもよい。
【００５６】
また、上述した実施の形態では、ステップ１０３において入力画像Ｉおよび参照画像Ｊを座標変換するようにしたが、必ずしも座標変換を行わなくてもよい。カメラ１０で撮像される画像およびカメラ１１で撮像される画像に存在するエピポーラ線ＥＰは水平であるとは限らず、傾斜している場合もある。理想的には水平であることが望まれるが、カメラ１０およびカメラ１１の取り付け誤差などもあり、エピポーラ線ＥＰは傾斜している場合が多い。このため、本実施の形態では、エピポーラ線ＥＰに平行な軸を一軸とし、この一軸に対して垂直な軸を他軸とする座標系に変換するようにした。エピポーラ線ＥＰが傾斜座標系のまま対応点の探索を進めるようにしてもよいが、座標系を変換することにより、以降の処理が簡単となる。なお、エピポーラ線ＥＰが平行である場合には、座標系の変換は不要である。
【００５７】
また、上述した実施の形態では、入力画像Ｉ’および参照画像Ｊ’からエッジ検出によってオブジェクト領域ＯＢ１およびＯＢ２を抽出するようにしたが、必ずしもオブジェクト領域ＯＢ１およびＯＢ２を抽出するようにしなくてもよい。例えば、オブジェクト領域ＯＢ１およびＯＢ２を抽出せずに、入力画像Ｉ’および参照画像Ｊ’の最上位の探索ラインの起点から最下位の探索ラインの終点まで、基準点ｐを移動しながら、すなわち探索ウィンドウＳＷを移動しながら、基準点ｐと対応点ｑとの対応付けを進めるようにしてもよい。
【００５８】
この場合、入力画像Ｉ’中の全領域において基準点ｐをずらしながら、その基準点ｐの画像データ列と参照画像Ｊ’中の候補点ｑ’の１次元の画素データ列との位相限定相関関数を１次元ＰＯＣによって計算することになるので、処理すべきデータ量が多くなる。これに対して、入力画像Ｉ’および参照画像Ｊ’からオブジェクト領域ＯＢ１およびＯＢ２を抽出し、この抽出したオブジェクト領域ＯＢ１およびＯＢ２を探索対象領域とすることにより、入力画像Ｉ’中の基準点ｐをずらす領域を小さくし、処理すべきデータ量を削減することができる。また、画像内のオブジェクト領域ＯＢ１，ＯＢ２外の画素データを処理対象から除外することで、これらの領域が対応点探索過程で精度を下げる外乱要因として働くことを未然に防止し、対応点探索精度の向上を図ることが可能となる。また、オブジェクト領域ＯＢ１中の探索ラインの起点から対応点の探索を始めることにより、常に対象物Ｍの輪郭に近い位置から対応点が求まるものとなり、対象物の３元位置の計測精度が向上する。
【００５９】
また、上述した実施の形態では説明しなかったが、対応点の探索を開始する際、入力画像Ｉ”および参照画像Ｊ”を低解像度として基準点の画素データ列と候補点の画素データ列との位相限定相関関数を計算し、この結果、相関ピークが得られれば、入力画像Ｉ”および参照画像Ｊ”の解像度を上げるということを段階的に繰り返して行くようにしてもよい。
【００６０】
また、上述した実施の形態では、カメラを２台としたが、光学機構を設けることによって、１台のカメラから入力画像Ｉと参照画像Ｊを得るようにしてもよい。また、カメラを３台以上設け、さらに複数の画像を得るようにしてもよい。カメラを１台とすると、ハードウェアで設計的に同期をとらずによいので、作りやすい。カメラがメガピクセルで高価な場合、安価になる場合がある。
【００６１】
また、上述した実施の形態では、基準点ｐの画素データ列と候補点ｑ’の画素データ列との相関関数を１次元の位相限定相関法で計算するようにしたが、１次元の帯域制限法で計算したり、１次元の相関係数法で計算したり、１次元の振幅抑制相関法で計算したりするようにしてもよい。
【００６２】
次に、１次元位相限定相関法を用いたエピポーラ幾何補正済み画像の対応付け手法について、さらに詳細に説明する。
【００６３】
１．１次元位相限定相関法に基づく画像の対応付けの基本手法
対応付けを行う２枚の画像を、そのエピポーラ線が平行になるように幾何補正（平行化）する（図１３（ａ）、（ｂ）参照）。図１３（ｂ）に示すように、この補正された２枚の画像を画像１および画像２とする。ここでは、図１３（ｂ）に示すように水平方向にエピポーラ線がそろう場合を考えるが、これは容易に一般的な平行化の場合に拡張できる。いま、画像１の基準点に対応する画像２の対応点を見つける問題を考える。
【００６４】
まず、図１３（ｂ）に示すように、平行化された画像１から、基準点ｐを中心とした１次元の画像信号を切り出し、ｆ(ｎ)とする。ここで、１次元画像信号ｆ(ｎ)はエピポーラ線と同じ方向に有限の長さで切り出すものとする。同様に平行化された画像２から、探索する対応点ｑの候補となる点ｑ’を中心として１次元画像信号ｇ(ｎ)を切り出す。このｇ(ｎ)は基準点ｐに対応するエピポーラ線上に存在する。ここで、１次元画像信号の離散空間インデックスを便宜上、ｎ＝−Ｍ,..,Ｍとする。ただし、Ｍは正の整数であり、１次元画像信号の長さＮはＮ＝２Ｍ＋１で与えられる。
【００６５】
なお、ここでは、説明を簡単にするために離散空間のインデックスを正負対称に取り、かつ１次元画像信号の長さを奇数にしているが、これは本手法の構成において必須ではない。すなわち、通常よく用いられるように０以上の離散空間インデックスを用い、１次元画像信号の長さＮを任意の正の整数に設定するように一般化することが可能である。通常はＮを２のべき乗の値にとり、高速フーリエ変換（ＦＦＴ）を利用して計算することが多い（後述する性能評価においても、Ｎを２のべき乗の値にとっている）。
【００６６】
以下では、フーリエ変換の記述の簡便さのために、上記のような設定を用いて説明を行う。また、１次元画像信号ｆ(ｎ)とｇ(ｎ)は、必ずしも基準点ｐとその対応候補点ｑ’を厳密に中心として切り出す必要はなく、一般にはそれらの上を通るように切り出すことができる。このとき、ｆ(ｎ)とｇ(ｎ)の１次元離散フーリエ変換を次式で定義する。
【００６７】
【数１】
【００６８】
ここで、ＡF(ｋ)及びＡG(ｋ)はそれぞれ１次元画像信号ｆ(ｎ)およびｇ(ｎ)の振幅成分であり、θF(ｋ)およびθG(ｋ)はそれぞれの位相成分である。また、離散周波数のインデックスをｋ＝−Ｍ,..,Ｍとする。ここで、離散空間のインデックスｎと同様に、離散周波数ｋのインデックスの選び方にも自由度がある。このとき、合成位相スペクトルＲ(ｋ)を次式で与える。
【００６９】
【数２】
【００７０】
しかし、実際のカメラで撮影された画像の場合、これは大きな問題にならない。ｆ(ｎ)とｇ(ｎ)の１次元位相限定相関関数ｒ(ｎ)を、合成位相スペクトルＲ(ｋ)の１次元逆離散フーリエ変換として定義する。
【００７１】
【数３】
【００７２】
ここで、ｎ＝−Ｍ,..,Ｍである。
【００７３】
次に、切り出した１次元画像信号ｆ(ｎ)とｇ(ｎ)が、互いに微小移動した関係にある場合を考える。つまり、このｆ(ｎ)とｇ(ｎ)に含まれる視差をサブピクセル分解能で推定する問題を考える。いま、ｆｃ(ｘ)を連続空間変数ｘの上で定義された１次元画像信号とする。これを実数値δだけ微小移動した１次元画像信号はｆｃ(ｘ−δ)と表される。このとき、ｆ(ｎ)とｇ(ｎ)が、ｆｃ(ｘ)およびｆｃ(ｘ−δ)を適当な空間サンプリング間隔Ｔでサンプリングしたものであると仮定する。すなわちｆ(ｎ)とｇ(ｎ)を次式で定義する。
【００７４】
【数４】
【００７５】
以下では、簡単のためにＴ＝１とする。このとき実数値の移動量δについて、サンプリング間隔を越える分解能で検出する方法を示す。まず、δが小さい場合、ｆ(ｎ)とｇ(ｎ)の１次元離散フーリエ変換Ｆ(ｋ)とＧ(ｋ)に関して、次式の近似が成り立つ。
【００７６】
【数５】
【００７７】
上式が近似であるのは、連続時間信号と離散時間信号に対するフーリエ変換の性質の違いに起因する。このとき、Ｆ(ｋ)とＧ(ｋ)の合成位相スペクトルＲ(ｋ)および１次元位相限定相関関数ｒ(ｎ)は次式で与えられる。
【００７８】
【数６】
【００７９】
ここで、α＝１、ｎ＝−Ｍ,..,Ｍである。上式は１次元画像信号がδだけ位置ずれした場合における１次元位相限定相関関数の一般形を表している。αは相関値のピークの高さを表現するために導入されたパラメータであり、画像にノイズが加わると、αの値が減少することが実験で確認されているため、実際にはα≦１となる。
【００８０】
δが整数の場合、式(１１)はデルタ関数となる。ただし、そのピークはｎ＝−δに位置し、ピークの高さはαとなる。実際の１次元位相限定相関関数ｒ(ｎ)の計算値から、このピークの位置を検出することにより、切り出した１次元画像信号ｆ(ｎ)とｇ(ｎ)の位置ずれδを検出することができる。すなわち、１次元画像信号ｆ(ｎ)における基準点ｐに対して、１次元画像信号ｇ(ｎ)におけるその対応点ｑは、対応点候補ｑ’とδを用いて次式のように求めることができる。
【００８１】
【数７】
【００８２】
ここで上式において、ｑおよびｑ’は直交座標系の位置ベクトルとして表現されているものとする。なお、その際、位置ずれδの方向を水平方向（ベクトル（１，０）の方向）にとっている。一般に、δが非整数（実数）の場合も、次節で述べるような、関数フィッティングなどの手法を用いてδを推定することによって、対応点ｑの座標をサブピクセル精度で求めることができる。
【００８３】
２．１次元位相限定相関法に基づく画像の対応付け手法の高精度化
本節では、前節で述べた基本手法をもとにして、それを発展させ、切り出した１次元画像信号ｆ(ｎ)とｇ(ｎ)の間の位置ずれ量を高精度に推定する手法を示す。
【００８４】
Ａ．位置ずれ量をサブピクセル精度で推定するための関数フィッティング手法
一般に、位置ずれ量δは実数値をとり、１次元位相限定相関関数のピーク座標はサンプリング格子点の間に存在するため、正確に位置ずれ量δを推定することが困難になる。そこで、１次元位相限定相関関数のピーク形状のモデルが式(１１)の右辺の関数で表わされることを考慮し、この関数そのもの、あるいは、式(１１)の右辺を近似的に表現する適当な関数（例えば、２次関数など）を、実際に計算された１次元位相限定相関関数の数値データに対してフィッティングすることによって、画像のピクセル間に存在するピークの位置を推定することができる。一般に、δ（および必要に応じてα）が推定されるパラメータとなる。
【００８５】
一例として、式(１１)の右辺に基づき、１次元位相限定相関関数の最大値とその周辺の数値データから、直接、δおよびαを推定する手法を示す。まず、１次元位相限定相関関数ｒ(ｎ)がｎ＝ａ（ａは整数）において最大値をとるものとする。このとき、ｒ(ａ)とその近傍ｒ（ａ−ｂ）およびｒ（ａ＋ｂ）の３つの値を用いて、δおよびαを推定することができる。ここで、ｂは−Ｍ≦ａ−ｂ＜ａ＜ａ＋ｂ≦Ｍを満たす小さい正の整数である。具体的には、δは次式から容易に求めることができる。
【００８６】
【数８】
【００８７】
ただし、ｕ(ａ，ｂ)とｖ(ａ，ｂ)は次式で与えられる。
【００８８】
【数９】
【００８９】
また、δと式(１１)により、αを求めることができる。上記の数式にはさまざまな近似表現が考えられ、実際には、この近似表現を用いて計算を簡単化できる。
【００９０】
ここで、上記はあくまで一例であり、計算された１次元位相限定相関関数の数値に対して、最小２乗法などを用いて適当な関数（２次関数など）をフィッティングすることにより、δ（および必要に応じてα）を高精度に推定することが可能である。なお、推定された相関ピークの高さαは、ｐとｑの対応付けの信頼性を表す尺度として使用することができる。αが大きい対応点ペア（ｐ，ｑ）のみを採用することにより、２つの画像から誤対応の少ない対応点ペアの集合を得ることができる。なお、αが非常に小さい場合は、ｇ( ｎ)上に対応点ｑが存在しないとみなすことができる。
【００９１】
Ｂ．離散フーリエ変換における不連続性を低減するための窓関数の適用
１次元離散フーリエ変換は信号が循環することを仮定するため、端点での信号の不連続性が問題となる。この不連続性の影響を低減するため、入力された１次元画像信号ｆ(ｎ)およびｇ(ｎ)に対して適当な窓関数（ハニング窓、ガウス窓など）を適用することが高精度化を実現する上で重要である。
【００９２】
例えば、窓関数の一例としては、次のようなハニング窓があげられる。
【００９３】
【数１０】
【００９４】
Ｃ．スペクトル重み付け関数の適用
一般に、自然画像の場合、そのエネルギーは低周波成分に集中し、高周波成分のエネルギーは相対的に小さいことが知られている。このため、エイリアシング、ぼけ、雑音、歪みなどの影響により高周波成分に外乱が加わると、画像の高周波成分のＳ／Ｎ比が大幅に劣化する。そこで、信頼性の低い高周波成分の影響を抑制するためにスペクトル重み付け関数を適用する。
【００９５】
具体的には、任意の特性を持つスペクトル重み付け関数Ｈ(ｋ)を合成位相スペクトルＲ(ｋ)に乗じることにより、周波数成分ごとに重み付けを行う。なお、通常は、低域通過型のスペクトル重み付け関数（方形フィルタ、ガウスフィルタなど）を適用し、信頼性の低い高周波成分の除去を行うと効果的である。ただし、スペクトル重み付け関数Ｈ(ｋ)を用いる場合、１次元位相限定相関関数ｒ(ｎ)はＨ(ｋ)・Ｒ(ｋ)の１次元逆離散フーリエ変換として定義されるため、そのピーク形状のモデルが式(１１)とは異なる。そこで、Ｈ(ｋ)に応じて異なるピーク形状のモデルを用いる必要がある。ただし、その場合も、基本的には本稿で述べる各種の手法が適用可能である。
【００９６】
例えば、最も単純なスペクトル重み付け関数Ｈ(ｋ)の一例として、次のようなものが考えられる。
【００９７】
【数１１】
【００９８】
ただし、０＜Ｕ≦Ｍである。このスペクトル重み付け関数を用いた場合、１次元位相限定相関関数ｒ(ｎ)のモデル式(１１)に対応するピーク形状のモデルは次式で与えられる。
【００９９】
【数１２】
【０１００】
ただし、Ｖ＝２Ｕ＋１である。したがって、前記項目Ａの関数フィッティングは、上式を想定して行う必要がある。このように、本稿で提案する手法は、スペクトル重み付け関数Ｈ(ｋ)に応じて異なるピーク形状のモデルを用いるように一般化することができる。
【０１０１】
Ｄ．１次元帯域制限位相限定相関関数の適用
信頼性の低い高周波成分の影響を排除するためにスペクトル重み付け関数を用いる代わりに、帯域制限型の位相限定相関関数を使用することも可能である。１次元帯域制限位相限定相関関数は式(６)を次のように変更したものである。
【０１０２】
【数１３】
【０１０３】
ただし、０＜Ｋ≦ＭおよびＬ＝２Ｋ＋１である。すなわち、１次元位相限定相関関数ｒ(ｎ)の計算に含まれる１次元逆離散フーリエ変換の定義域を信号の有効帯域（ｋ＝−Ｋ,..,Ｋ）にあわせて制限したものが１次元帯域制限位相限定相関関数である。式(１１)に対応するピーク形状のモデルは次式で与えられる。
【０１０４】
【数１４】
【０１０５】
なお、１次元帯域制限位相限定相関関数を用いた場合、相関ピークの位置はｎ＝−（Ｌ／Ｎ）δで与えられることに注意する必要がある。前記項目Ａの関数フィッティングは上式を想定して行うように容易に一般化できる。
【０１０６】
Ｅ．複数の１次元画像信号の利用による高信頼化
これまで、画像１における基準点ｐを中心として抽出した１次元画像信号ｆ(ｎ)と画像２における対応候補点ｑ’を中心として抽出した１次元画像信号ｇ(ｎ)を用いて、その位置ずれ量δを推定することにより、真の対応点ｑを求める手法について示してきた。しかし、実際に撮影した画像を用いた場合、ひと組の１次元画像信号を用いただけでは、高い信頼性でピークの位置を判定することはきわめて難しい。そこで以下では、複数の１次元画像信号の組を対応点の近傍から抽出し、それらの相関計算の結果を統合することによって、より信頼性の高いピーク位置の推定を行う方法について述べる。
【０１０７】
まず、画像１の基準点ｐの周辺からＢ個の１次元画像信号ｆi (ｎ)（ｉ＝１，２,..,Ｂ）を抽出する。一方、画像２の点ｑ’の周辺の対応する位置からもＢ個の１次元画像信号ｇi (ｎ)（ｉ＝１，２,..,Ｂ）を抽出する。例えば、図１４(a)に、ｆi (ｎ)とｇi (ｎ )の選び方の一例を示す。この例ではＢ＝５としており、ｐとｑ’の周辺から規則正しい配置で、１次元画像信号ｆi (ｎ)とｇi (ｎ)をそれぞれ５つずつ抽出している。これらの５つの１次元画像信号の対から位置ずれ量δを高精度に推定することによって、基準点ｐに対応する真の対応点ｑを求めることができる。
【０１０８】
１次元画像信号ｆi (ｎ)とｇi (ｎ)の１次元位相限定相関関数をｒi (ｎ)と表記するものとする。ただし、ｉ＝１，２,..,Ｂである。これらＢ個の１次元位相限定相関関数ｒi (ｎ)の重み付き平均として、累積相関関数ｒall (ｎ)を定義する。
【０１０９】
【数１５】
【０１１０】
ここで、ｗi はｒi (ｎ)に付随する重み係数であり、任意の定数に選ぶことができる。このように定義されたｒall (ｎ)は重み付き平均化された１次元位相限定相関関数である。ｒi (ｎ)およびｒall (ｎ)に対して、基本的にこれまでに述べてきたすべての高精度化手法を適用することができる。すなわち、これまでに述べてきた単一の１次元位相限定相関関数ｒ(ｎ)を用いた議論は、容易にｒi (ｎ)およびｒall (ｎ)を用いるように拡張することが可能である。
【０１１１】
なお、計算量を減少させる手法として次のようなことが考えられる。１次元画像信号ｆi (ｎ)とｇi (ｎ)の合成位相スペクトルをＲi (ｋ)と表記し、累積合成位相スペクトルＲall (ｋ)を次式で定義する。
【０１１２】
【数１６】
【０１１３】
このとき、ｒall (ｎ)はＲall (ｋ)の１次元逆離散フーリエ変換であるため、あらかじめＲall (ｋ)を計算してから、これを１次元逆離散フーリエ変換してｒall (ｎ)を計算することができる。Ｂが大きい場合は、この計算法は、Ｒi (ｋ)をｒi (ｎ)に個別に１次元逆離散フーリエ変換するよりも計算量が少ない。
【０１１４】
なお、ここで述べた手法は、さまざまなやり方で一般化することができる。２つの重要な拡張について以下に示す。
【０１１５】
・ｒi (ｎ)（ｉ＝１，２,..,Ｂ）からｒall (ｎ)への統合の仕方としては、式(２１)で定義した線形結合のほかにも多様な方法が考えられる。一般に、ｒi (ｎ)を適当な非線形オペレータで結合したものをｒall (ｎ)として用いることができる。
【０１１６】
・１次元画像信号ｆi (ｎ)およびｇi (ｎ)の選び方としては、図１４（ａ）のような規則的な配置である必要はなく、例えば、図１４（ｂ）のような例も含めて、任意の配置を取ることができる。また、必ずしもＢ個の１次元画像信号が同一の長さをもつ必要もない。その一例を図１４（ｃ）、（ｄ）に示す。Ｂ個の１次元画像信号が異なる長さを持つ場合は、Ｂ個のｒi (ｎ)も異なる長さを持つことになる。
【０１１７】
この場合は、式（２１）のｒi (ｎ)の加算において、基準となる位置（例えばｎ＝０）を合わせて加算することによってｒall (ｎ)を求めることができる。このような自由度を積極的に利用すると、画像に含まれるオブジェクトの境界（エッジ）をまたがないように１次元画像信号を抽出するなどの方法により、対応付けの精度を大幅に向上できる。図１４（ｅ）は、そのような１次元画像信号の配置の一例を示している。この例では、オブジェクト境界に、１次元画像信号の端点を合わせて配置している。
【０１１８】
以上、述べてきた手法Ａ〜Ｅは、用途に応じてさまざまに組み合わせることができる。
【０１１９】
３．１次元位相限定相関法と階層探索の組合せによる画像の対応付け手法
以下では、図１５に示すように、基準点ｐと対応候補点ｑ’の周辺から１次元画像信号ｆi (ｎ)およびｇi (ｎ)（ｉ＝１，２,..,Ｂ）を抽出する単純な場合を考える。ただし、以下で述べる手法は、他の場合についても容易に拡張することができる。
【０１２０】
このとき、図１５に示す破線で示したＮ×Ｂピクセルの画像領域を探索ウィンドウと呼ぶことにする。これまでに述べてきた手法では、探索ウィンドウ内の対応候補点ｑ’の付近に真の対応点ｑが存在すると暗に仮定してきた。この仮定を現実のステレオ画像の対応付けの際に常に成立させるための手法として、ここでは、１次元位相限定相関法による対応付けと粗密戦略に基づく階層探索との組合せについて述べる。これにより、一般的なステレオカメラなどから取得される画像ペアについてロバストな対応付けが可能になる。
【０１２１】
ここで記述するアルゴリズムは、すでに述べてきたように、対応付けを行う２枚の画像（画像１と画像２）を、そのエピポーラ線が平行になるように幾何補正（平行化）したうえで、画像１の基準点ｐに対応する画像２の対応点ｑを探し、それが存在する場合には、その座標をサブピクセルの分解能で返すものである。画像１の全域にわたって基準点ｐを変化させながら、このアルゴリズムによって対応点ｑを探索することによって、画像１と画像２の全体について、サブピクセル分解能の対応付けを行うことができる。
【０１２２】
この対応点の探索において粗密戦略を使用する。図１６に多重解像度画像を用いた場合の粗密戦略による階層探索の概念図を示す。多重解像度画像を用いて粗密戦略を行う場合、通常は探索ウィンドウのサイズ（Ｎ×Ｂピクセル）を固定し、画像１および画像２のそれぞれについて、解像度を段階的に低下させた複数の低解像度画像を準備して階層探索することにより、画像に対する相対的な探索の範囲を階層ごとに変更することが可能である。
【０１２３】
ただし、多重解像度画像を用いることは、粗密戦略においては必須ではなく、単純に、原画像上で探索ウィンドウのサイズを段階的に変更（徐々に縮小）しつつ階層探索することによって、対応点ｑの候補位置を絞っていくことも可能である。以下に、多重解像度画像を用いた場合の対応点探索アルゴリズムを示す。なお、全ての探索はエピポーラ線上（平行化した画像における同一の水平線上）で行う。
【０１２４】
１次元位相限定相関法と階層探索の組合せによる画像の対応付けアルゴリズム
（多重解像度画像を用いた場合）
【０１２５】
入力:
・画像１および画像２（あらかじめ平行化しておく）
・画像１における基準点ｐ（座標ベクトルをｐで表す）
【０１２６】
出力:
・画像２における対応点ｑ（座標ベクトルをｑで表す）
ただし、信頼できる対応点が存在しない場合は「対応点なし」を出力する。
【０１２７】
処理手順:
Step１：多重解像度画像を生成する。上位階層を低解像度画像とし、下位階層を高解像度画像とする。最下位の階層を原画像とする。なお、以下では、基準点ｐ、対応点ｑ、対応候補点ｑ’は、すべて原画像（画像１および画像２）に換算した画像座標系上の位置ベクトルで表現されているものとする。すなわち、上位階層の低解像度画像においては、その点の位置を原画像の座標系に換算して表示するものとする。また、画像１および画像２は共通の画像座標系上で定義されているものとする。
【０１２８】
Step２：最も解像度の低い最上位階層において、対応候補点の初期値をｑ’←ｐとして探索を開始する。すなわち、この仮定が成り立つために十分な階層の数を設定するものとする。現在の探索階層を最上位階層に設定する。
【０１２９】
Step３：現在の探索階層において、基準点ｐおよび対応候補点ｑ’を中心として、画像１および画像２の探索ウィンドウを設定し、前節までに述べてきた１次元位相限定相関法を用いて位置ずれ量δを高精度に推定する。
【０１３０】
Step４：この位置ずれ量δをもとにして、探索候補点ｑ’を次式によって更新する。
【０１３１】
【数１７】
【０１３２】
これは真の対応点を求める式(１２)に対応する。現在の探索階層が最下位階層（原画像階層）の場合は、Step５に進み、そうでない場合は、現在の探索階層を、ひとつ下の階層に設定し、Step３に進む。
【０１３３】
Step５：最下位階層（原画像階層）において、基準点ｐおよび対応候補点ｑ’を中心として、画像１および画像２の探索ウィンドウを設定する。なお、この際に、適当な補間技術を用いて、探索ウィンドウの位置をサブピクセル精度で調整する。前節までに述べてきた１次元位相限定相関法を用いて位置ずれ量δをサブピクセル精度で推定する。
【０１３４】
Step６：この位置ずれ量δをもとにして、探索候補点ｑ’を次式によって更新する。
【０１３５】
【数１８】
【０１３６】
Step５〜Step６を、位置ずれ量δが十分小さな値になるまで繰り返す。位置ずれ量δが微小な値に収束すればStep７へ進む。位置ずれ量δが微小な値に収束しない場合には、「対応点なし」を出力して終了する。なお、このステップは位置ずれ量δの値によらず、一定回数繰り返し、Step７へ進んでも良い。
【０１３７】
Step７：相関計算におけるピークの値αが小さい場合は、「対応点なし」を出力して終了する。それ以外の場合は、ｑ←ｑ’としてｑを出力して終了する。
【０１３８】
ここで述べたアルゴリズムは、図１５に示す標準的な１次元画像信号の配置を想定しているが、これは容易に一般化できる。また、階層探索の方法などについては、一般のブロックマッチングと同様にさまざまな拡張が考えられる。
【０１３９】
３．提案手法を用いた３次元計測システムの構成
前節で記述した画像の対応付けアルゴリズムは画像１の基準点ｐに対する画像２の対応点ｑを探索するものである。この基準点ｐを画像１の全域にわたって変化させながら対応点を探索することによって、画像の全体についてサブピクセル分解能の対応付けを行うことができる。この対応付け手法を（２つ以上の）複数のカメラを使用するステレオビジョンシステムに適用すると、きわめて高精度な受動型３次元計測システムを構築することができる。
【０１４０】
一般に、複数のカメラを使用する受動型のステレオビジョンシステムにおいて、３次元計測を行う２つのステレオカメラの間の距離（基線長）は、その計測性能を決定する重要なパラメータであり、次のようなトレードオフが存在する。
【０１４１】
・基線長の長いステレオカメラの場合：
３次元点の計測精度が高いという利点があるが、２つのステレオカメラの間の画像変形が大きいため、対応点探索の自動化が難しい。しかも、得られる対応点は、画像中のエッジなどの特別な点に限られる。どちらかというと、幾何学的な人工物には適用できるが、人間の顔のような自然物に適用することはきわめて困難であり、一般に汎用性がない。
【０１４２】
・基線長の短いステレオカメラの場合：
２つのステレオカメラの間の画像変形が小さいため、対応点探索の自動化が比較的容易であり、汎用性のあるシステムを構築できるポテンシャルを有する。しかし、通常のピクセル精度の対応づけアルゴリズムを用いた場合には、そもそも３次元計測精度がきわめて低く、ほとんど実用的ではない。
【０１４３】
以上のような理由により、従来の高精度なステレオビジョンシステムでは、基線長の長いステレオカメラを用いることがほとんどであり、ごく限られた用途にしか適用できず、実用上のインパクトが少なかった。しかし、本願で提案する画像の対応付け手法は、対応点の座標を安定に高いサブピクセル分解能で求めることが可能であり、短い基線長のステレオカメラに適用した場合も、高い計測精度を実現することが可能である。
【０１４４】
図１７に、提案する対応付けアルゴリズムを用いた３次元計測の流れを示す。ここでは、２つのカメラを用いた受動型のステレオビジョンシステムを想定しているが、これは、容易に３つ以上のカメラを用いる場合にも拡張できる。まず、あらかじめカメラ校正を行いステレオカメラシステムのカメラパラメータ（内部行列および外部行列）を取得しておくものとする（非特許文献２、４、８参照）。
【０１４５】
３次元計測の流れは、(i)ステレオ画像の撮影、(ii)ステレオ画像の幾何補正、(iii)ステレオ画像の対応付け、(iv)３次元復元の４ステップからなる。特に、ステレオ画像の対応付けステップにおいて、相関ピークの値αが大きい対応点ペアのみを出力することで、最終的に信頼性の高い高精度な３次元点群を得ることができる。
【０１４６】
４．提案手法を用いた３次元計測システムの評価
３次元計測システムを構築し、従来の対応付け手法と１次元位相限定相関法による対応付け手法との性能比較を行う。以下に性能評価を行う４つの手法を示す。
【０１４７】
・１次元位相限定相関法を用いる対応付け手法：本請求で提案する手法である。対応点の座標を安定に高いサブピクセル分解能で求めることができる。また、その際に必要とする計算量を少なく抑えることが可能である。
【０１４８】
・２次元位相限定相関法を用いる対応付け手法：画像の２次元離散フーリエ変換の位相情報を用いた対応付け手法であり、サブピクセル精度で２枚の画像を対応付けることが可能である（非特許文献５、６、７参照）。しかし、２次元フーリエ変換に起因する計算量が大きいことが問題となっている。
【０１４９】
・輝度差の総和法(SumofAbsoluteDifferences:ＳＡＤ）を用いる対応付け手法：ＳＡＤは次式で定義される（非特許文献２、３参照）。
【０１５０】
【数１９】
【０１５１】
ここで、Ｉ（ｎ1，ｎ2）およびＪ（ｎ1，ｎ2）は、ＳＡＤによって対応付けを行う画像１および画像２の画像ブロックである。また、画像ブロックのサイズをＮ1×Ｎ2ピクセルとする。加減算のみで計算を行うことができるため、高速処理を実現することが容易である。しかし、対応付け精度が極めて低いという問題がある。なお、対応点座標のサブピクセル推定のために等角直線フィッティングを行う手法を用いた（非特許文献２参照）。
【０１５２】
・輝度差の２乗和法（SumofSquaredDifferences:ＳＳＤ）を用いる対応付け手法：ＳＳＤは次式で定義される（非特許文献２、３、４参照）。
【０１５３】
【数２０】
【０１５４】
ここで、Ｉ（ｎ1，ｎ2）およびＪ（ｎ1，ｎ2）は、ＳＳＤによって対応付けを行う画像１および画像２の画像ブロックである。また、画像ブロックのサイズをＮ1×Ｎ2ピクセルとする。ＳＡＤと比較して計算量は増大するが、若干良い対応付け結果を得ることができる。なお、対応点座標のサブピクセル推定のためにパラボラフィッティングを行う手法を用いた（非特許文献２参照）。
【０１５５】
Ａ．計算量の評価
上で述べたように、１次元位相限定相関法と３つの従来手法との計算量の比較を行う。ここでは、対応点を１点だけ見つけるために必要となる計算量を比較する。１次元位相限定相関法を用いる場合には、前節で述べたようにＮピクセルの１次元画像信号をＢ個切り出して探索ウィンドウとする。ただし、簡単のためＮは２のべき乗とする。
【０１５６】
一方、２次元位相限定相関法を用いる対応付け手法において、切り出す画像ブロックのサイズをＮ1×Ｎ2ピクセルとする。ただし、Ｎ1およびＮ2は２のべき乗とする。なお、２次元離散フーリエ変換の計算においては、１次元高速フーリエ変換（ＦＦＴ）を利用した行列分解法を用いるものとする。また、１回の複素数乗算は４回の実数乗算と２回の実数加算として数え、複素数加算は２回の実数加算として数える。
【０１５７】
同様に、ＳＡＤ（あるいはＳＳＤ）を用いる対応付け手法においては、切り出す画像ブロックのサイズをＮ1×Ｎ2ピクセルとし、１点の探索に要するＳＡＤ（あるいはＳＳＤ）の計算回数をＮ1 回とする。なお、計算量の比較を行うための具体的な数値例として、Ｎ＝３２、Ｂ＝５、Ｎ1＝３２、Ｎ2＝３２を想定する。これはステレオ画像の対応付けを行う際に用いる標準的な値である。
【０１５８】
乗算の計算回数は次式で示される。
・１次元位相限定相関法：２（２Ｂ＋１）Ｎｌｏｇ2Ｎ＋６ＢＮ＝４，４８０回
・２次元位相限定相関法：６Ｎ1Ｎ2ｌｏｇ2（Ｎ1，Ｎ2）＋６Ｎ1Ｎ2＝６７，５８４回
・ＳＡＤ：０回
・ＳＳＤ：Ｎ12Ｎ2＝３２，７６８回
【０１５９】
加算の計算回数は次式で示される。
・１次元位相限定相関法：３（２Ｂ＋１）Ｎｌｏｇ2Ｎ＋（５Ｂ−１）Ｎ＝６，０１６回
・２次元位相限定相関法：９Ｎ1Ｎ2ｌｏｇ2（Ｎ1Ｎ2）＋３Ｎ1Ｎ2＝９５，２３２回
・ＳＡＤ：Ｎ1（２Ｎ1Ｎ2−１）＝６５，５０４回
・ＳＳＤ：Ｎ1（Ｎ1Ｎ2−１）＝３２，７３６回
【０１６０】
除算の計算回数は次式で示される。
・１次元位相限定相関法：２ＢＮ＋２Ｎ＝３８４回
・２次元位相限定相関法：２Ｎ1Ｎ2＝２，０４８回
・ＳＡＤ：０回
・ＳＳＤ：０回
【０１６１】
平方根の計算回数は次式で示される。
・１次元位相限定相関法：ＢＮ＝１６０回
・２次元位相限定相関法：Ｎ1Ｎ2＝１，０２４回
・ＳＡＤ：０回
・ＳＳＤ：０回
【０１６２】
このように、ステレオ画像の対応付けに１次元位相限定相関法を用いることで、２次元位相限定相関法に対して計算量を極めて少なく抑えることができる。上記の標準的な数値例では、乗算回数を約１／１５に、加算回数を約１／１６に削減することが可能である。また、ＳＡＤおよびＳＳＤを用いる手法と比較しても、十分な高速性を実現できると予想される。
【０１６３】
Ｂ．３次元復元性能の比較
評価対象となる４つの対応付け手法と粗密戦略に基づく階層探索を組み合わせてステレオ画像の対応付けを行い、３次元復元を行った結果を比較する。各手法のパラメータについては、前記項目Ａと同様のパラメータを用いた。すなわち、Ｎ＝３２、Ｂ＝５、Ｎ1 ＝３２、Ｎ2 ＝３２とした。なお、階層探索を行う際の多重解像度画像の階層数を５階層とする。
【０１６４】
図１９に実験で用いたステレオビジョンシステムを示す。ステレオビジョンシステムでは、人物の顔を被写体とするために、図１９（ｂ）に示すようにステレオカメラヘッドのカメラ配置を縦置きにとっている。次に、各手法の３次元復元結果を図１８に示す。図１８（ａ）はステレオカメラヘッドから取得されたステレオ画像である。ただし、ステレオカメラヘッドは縦置きのカメラ配置であるため、エピポーラ線は画像の垂直座標と平行に走ることになる。
【０１６５】
そこで、実際の対応付けでは図１８（ａ）のステレオ画像を９０度回転することで、エピポーラ線を画像の水平座標と平行になるように補正した。つまり、図１３（ｂ）と同様の画像が得られる。まず、図１８（ｂ）は１次元位相限定相関法に基づく対応付け手法を用いた場合の３次元計測結果である。これに対して、図１８（ｃ）〜（ｅ）は、それぞれ、２次元位相限定相関法を用いた場合、ＳＡＤを用いた場合、ＳＳＤを用いた場合の３次元計測結果である。ＳＡＤとＳＳＤを用いた場合では、３次元点が階段状に復元されている。
【０１６６】
これは、対応付けの際に、十分なサブピクセル精度が得られていないためである。一方、１次元位相限定相関法と２次元位相限定相関法を用いた場合では、顔の３次元的な曲面形状が滑らかに復元されている。次に、顔のふち部分の３次元復元結果に着目すると、ＳＡＤやＳＳＤを用いた場合では、対応付けに失敗していることがわかる。一方、１次元位相限定相関法は２次元位相限定相関法と比べて探索ウィンドウのサイズを小さくとることでオブジェクト境界の影響を軽減できるため、顔のふち部分について３次元復元精度の向上が見られる。このように、１次元位相限定相関法を用いることで、人物の顔の３次元形状を従来手法よりも高精度に復元できることがわかる。
【図面の簡単な説明】
【０１６７】
【図１】本発明に係る対応点探索方法を利用した３次元位置計測装置の一実施の形態を示すブロック構成図である。
【図２】対象物を異なる視点から見た２つの画像に水平なラインとして存在するエピポーラ線を説明する図である。
【図３】対象物を異なる視点から見た２つの画像に傾斜したラインとして存在するエピポーラ線を説明する図である。
【図４】この３次元位置計測装置の画像取り込みから対象領域の抽出までの処理過程を説明する図である。
【図５】この３次元位置計測装置における３次元位置の計測処理を示すフローチャートである。
【図６】この３次元位置計測装置における３次元位置の計測処理過程での対応点探索処理を示すフローチャートである。
【図７】入力画像から抽出されたオブジェクト領域中の最上位の線の起点から対応点の探索が始められる様子を説明する図である。
【図８】基準点のデータ列と候補点のデータ列との１次元位相限定相関法による相関関数の計算を説明する図である。
【図９】探索ウィンドウに対して平行に複数組の近傍探索ウィンドウを定めて対応点の探索を行う例を説明する図である。
【図１０】探索ウィンドウに対して平行に複数組の近傍探索ウィンドウを定めて対応点の探索を行う場合の変形例を示す図である。
【図１１】探索ウィンドウに対して平行に複数組の近傍探索ウィンドウを定めて対応点の探索を行う場合の変形例を示す図である
【図１２】探索ウィンドウに対して平行に複数組の近傍探索ウィンドウを定めて対応点の探索を行う場合の変形例を示す図である
【図１３】平行化された２つの画像と１次元画像信号を説明するための図である。
【図１４】１次元画像信号の抽出を説明するための図である。
【図１５】探索ウィンドウの設定方法を説明するための図である。
【図１６】画像ピラミッドを用いたサブピクセル対応付けアルゴリズムの概要を説明するための図である。
【図１７】３次元計測の流れを例示するフローチャートである。
【図１８】顔の３次元復元結果を示す説明図である。
【図１９】３次元計測精度を評価する実験で用いたステレオビジョンシステムを示す説明図である。
【図２０】特許文献１に示された立体像計装置における画像入力部の概略を示す図である。
【図２１】特許文献１に示された立体像計装置における２次元位相限定相関法を用いた立体像の計測処理を説明する図である。
【符号の説明】
【０１６８】
１０、１１…カメラ（ＣＣＤカメラ）、１２…液晶表示装置（ＬＣＤ）、２０…処理部、２０−１…制御部、２０−２…ＲＯＭ、２０−３…ＲＡＭ、２０−４…ハードディスクドライブ（ＨＤＤ）、２０−５…フレームメモリ（ＦＭ）、２０−６…外部接続部（Ｉ／Ｆ）、２０−７…フーリエ変換部（ＦＦＴ）、ＬＮ（ＬＮ１、ＬＮ２）…レンズ、ＥＰ…エピポーラ線、ＳＷ（ＳＷ０）…探索ウィンドウ、ＳＷ１〜ＳＷ４…近傍探索ウィンドウ、ＣＷ（ＣＷ０）…探索ウィンドウ、ＣＷ１〜ＣＷ４…近傍探索ウィンドウ、ＯＢ１、ＯＢ２…オブジェクト領域、ＳＴ…起点、ＥＮＤ…終点、Ｉ…入力画像、Ｊ…参照画像、Ｍ…対象物。
【特許請求の範囲】
【請求項１】
画像取込手段を介して、対象物を異なる視点から見た複数の画像を取り込む画像取込ステップと、
前記画像取込手段のパラメータおよび基準点から計算されるエピポーラ線に沿って前記複数の画像より１次元の画素データ列を切り出す画素データ列切出ステップと、
前記複数の画像から切り出された１次元の画素データ列の相関から前記複数の画像中の対応点を探索する対応点探索ステップと
を備えることを特徴とする対応点探索方法。
【請求項２】
請求項１に記載された対応点探索方法において、
前記複数の画像中の各画素データを、前記画像取込手段のパラメータおよび基準点から計算されるエピポーラ線に平行な軸を一軸とし、この一軸に対して垂直な軸を他軸とする座標系に変換する座標系変換ステップを備え、
前記画素データ列切出ステップは、
前記座標系が変換された複数の画像から前記１次元の画素データ列を切り出す
ことを特徴とする対応点探索方法。
【請求項３】
請求項１に記載された対応点探索方法において、
前記画素データ列切出ステップは、
前記エピポーラ線に沿って前記複数の画像より１次元の画素データ列を切り出すとともに、この１次元の画素データ列の近傍の前記エピポーラ線に平行な線に沿う１次元の画素データ列を切り出し、
前記対応点探索ステップは、
前記複数の画像から切り出された前記複数組の１次元の画素データ列の相関から前記複数の画像中の対応点を探索する
ことを特徴とする対応点探索方法。
【請求項４】
請求項１に記載された対応点探索方法において、
前記複数の画像から対応点探索の対象領域としてオブジェクト領域を抽出するオブジェクト領域抽出ステップを備え、
前記画素データ列切出ステップは、
前記複数の画像から抽出されたオブジェクト領域より前記エピポーラ線に沿って１次元の画素データ列を切り出す
ことを特徴とする対応点探索方法。
【請求項５】
画像取込手段を介して、対象物を異なる視点から見た複数の画像を取り込む画像取込ステップと、
前記画像取込手段のパラメータおよび基準点から計算されるエピポーラ線に沿って前記複数の画像より１次元の画素データ列を切り出す画素データ列切出ステップと、
前記複数の画像から切り出された１次元の画素データ列の相関から前記複数の画像中の対応点を探索する対応点探索ステップと、
前記探索された対応点の視差に基づいてその対応点の３次元位置を計測する３次元位置計測ステップと
を備えることを特徴とする３次元位置計測方法。
【請求項１】
画像取込手段を介して、対象物を異なる視点から見た複数の画像を取り込む画像取込ステップと、
前記画像取込手段のパラメータおよび基準点から計算されるエピポーラ線に沿って前記複数の画像より１次元の画素データ列を切り出す画素データ列切出ステップと、
前記複数の画像から切り出された１次元の画素データ列の相関から前記複数の画像中の対応点を探索する対応点探索ステップと
を備えることを特徴とする対応点探索方法。
【請求項２】
請求項１に記載された対応点探索方法において、
前記複数の画像中の各画素データを、前記画像取込手段のパラメータおよび基準点から計算されるエピポーラ線に平行な軸を一軸とし、この一軸に対して垂直な軸を他軸とする座標系に変換する座標系変換ステップを備え、
前記画素データ列切出ステップは、
前記座標系が変換された複数の画像から前記１次元の画素データ列を切り出す
ことを特徴とする対応点探索方法。
【請求項３】
請求項１に記載された対応点探索方法において、
前記画素データ列切出ステップは、
前記エピポーラ線に沿って前記複数の画像より１次元の画素データ列を切り出すとともに、この１次元の画素データ列の近傍の前記エピポーラ線に平行な線に沿う１次元の画素データ列を切り出し、
前記対応点探索ステップは、
前記複数の画像から切り出された前記複数組の１次元の画素データ列の相関から前記複数の画像中の対応点を探索する
ことを特徴とする対応点探索方法。
【請求項４】
請求項１に記載された対応点探索方法において、
前記複数の画像から対応点探索の対象領域としてオブジェクト領域を抽出するオブジェクト領域抽出ステップを備え、
前記画素データ列切出ステップは、
前記複数の画像から抽出されたオブジェクト領域より前記エピポーラ線に沿って１次元の画素データ列を切り出す
ことを特徴とする対応点探索方法。
【請求項５】
画像取込手段を介して、対象物を異なる視点から見た複数の画像を取り込む画像取込ステップと、
前記画像取込手段のパラメータおよび基準点から計算されるエピポーラ線に沿って前記複数の画像より１次元の画素データ列を切り出す画素データ列切出ステップと、
前記複数の画像から切り出された１次元の画素データ列の相関から前記複数の画像中の対応点を探索する対応点探索ステップと、
前記探索された対応点の視差に基づいてその対応点の３次元位置を計測する３次元位置計測ステップと
を備えることを特徴とする３次元位置計測方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２０】
【図２１】
【図１８】
【図１９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２０】
【図２１】
【図１８】
【図１９】
【公開番号】特開２００８−１２３１４１（Ｐ２００８−１２３１４１Ａ）
【公開日】平成２０年５月２９日（２００８．５．２９）
【国際特許分類】
【出願番号】特願２００６−３０４６２０（Ｐ２００６−３０４６２０）
【出願日】平成１８年１１月９日（２００６．１１．９）
【出願人】（０００００６６６６）株式会社山武 (1,808)
【出願人】（５０４１５７０２４）国立大学法人東北大学 (2,297)
【Ｆターム（参考）】
【公開日】平成２０年５月２９日（２００８．５．２９）
【国際特許分類】
【出願日】平成１８年１１月９日（２００６．１１．９）
【出願人】（０００００６６６６）株式会社山武 (1,808)
【出願人】（５０４１５７０２４）国立大学法人東北大学 (2,297)
【Ｆターム（参考）】
[ Back to top ]