(57)【要約】【課題】異なる位置にほぼ平行に設置された２つのカメラによって撮影された画像を入力し、撮影画像に基づく視差オフセットの算出を実行する構成を実現する。【解決手段】２つのカメラの撮影画像に含まれる特徴点ペアを検出し、特徴点ペアの解析により２つのカメラの撮影画像における視差オフセットを算出する。まず、特徴点ペアのフィルタリングにより信頼度の高いと判断される特徴点ペアを選択し、選択特徴点ペアに対応する視差オフセットデータのヒストグラムを生成し、ヒストグラムを利用して視差オフセットの値の拘束条件を設定し、設定した拘束条件に基づいて視差オフセット最適値を算出する。本構成によれば、一方のカメラについてのパラメータの一部が不明である場合にも、各カメラの撮影画像に基づいて最適な視差オフセットを算出可能となり、３次元マップ生成が実現される。【選択図】図２
2009048516.tif 000002
【特許請求の範囲】
【請求項１】
異なる位置にほぼ平行に設置された２つのカメラによって撮影された画像を入力し、撮影画像に基づく視差オフセットの算出を実行する情報処理装置であり、
前記２つのカメラの撮影画像に含まれる特徴点を抽出する特徴点抽出部と、
前記２つのカメラの撮影画像から抽出された特徴点の比較処理により、類似する特徴点の組み合わせからなる特徴点ペアを検出する特徴点マッチング処理部と、
前記特徴点ペアの解析により、前記２つのカメラの撮影画像における視差オフセットを算出する視差オフセット算出部を有し、
前記視差オフセット算出部は、
前記特徴点ペアのフィルタリングにより信頼度の高いと判断される特徴点ペアを選択し、選択特徴点ペアに対応する視差オフセットデータの発生頻度分布情報としてのヒストグラムを生成し、生成したヒストグラムを利用して視差オフセットの許容値の拘束条件を設定し、設定した拘束条件に基づいて視差オフセットの最適値を算出する構成であることを特徴とする情報処理装置。
【請求項２】
前記視差オフセット算出部は、
前記選択特徴点ペアに対応する視差オフセットとして、水平方向（Ｘ）と垂直方向（Ｙ）に対応する視差オフセット（ｄｘ，ｄｙ）の、［ｄｘ］のヒストグラムと［ｄｙ］のヒストグラムを生成し、生成したヒストグラムを利用して視差オフセットの許容値の拘束条件を設定し、設定した拘束条件に基づいて視差オフセットの最適値を算出する構成であることを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記視差オフセット算出部は、
垂直方向（Ｙ）の視差オフセットを規定する［ｄｙ］のヒストグラムのピーク位置を、垂直方向（Ｙ）に対応する視差オフセット（ｄｙ）の最適値として決定する処理を実行することを特徴とする請求項２に記載の情報処理装置。
【請求項４】
前記視差オフセット算出部は、
水平方向（Ｘ）の視差オフセットを規定する［ｄｘ］のヒストグラムにおいて、予め設定した出現頻度率に応じて［ｄｘ］の最小許容値［ｄｘ，ｍｉｎ］と、最大許容値［ｄｘ，ｍａｘ］を視差オフセットの許容値の拘束条件として設定し、設定した拘束条件に基づいて、水平方向（Ｘ）の視差オフセットの最適値を算出する構成であることを特徴とする請求項２に記載の情報処理装置。
【請求項５】
前記視差オフセット算出部は、
前記最小許容値［ｄｘ，ｍｉｎ］と、最大許容値［ｄｘ，ｍａｘ］の間において設定した複数の［ｄｘ］の値を適用した場合の特徴点のエラーおよび遊離（Ｏｕｔｌｉｅｒｓ）データ数を検証し、エラーおよび遊離（Ｏｕｔｌｉｅｒｓ）データ数が最小となる［ｄｘ］の値を水平方向（Ｘ）の視差オフセットの最適値として決定する処理を実行することを特徴とする請求項４に記載の情報処理装置。
【請求項６】
前記視差オフセット算出部は、
信頼度の高いと判断される特徴点ペアを選択するフィルタリング処理として、
前記特徴点ペアに対応する視差オフセットとして、水平方向（Ｘ）と垂直方向（Ｙ）に対応する視差オフセット（ｄｘ，ｄｙ）の値について、
（ａ）ｄｙが、予め設定した範囲にあることを条件とするエピポーラ拘束（Ｅｐｉｐｏｌａｒ  ｃｏｎｓｔｒａｉｎｔ）
（ｂ）ｄｘが、予め設定した範囲にあることを条件とする視差拘束（Ｄｉｓｐａｒｉｔｙ  ｃｏｎｓｔｒａｉｎｔ）、
（ｃ）上記（ａ），（ｂ）の両者を満足する複数のペア（１対多）がある場合、これらのペアは、あいまい性が高い特徴点ペアであると判定して排除する固有対応拘束、
上記（ａ）〜（ｃ）の少なくともいずれかの拘束条件を満足するか否かの定を実行して、拘束条件を満足するもののみを残存させるフィルタリング処理を実行する構成であることを特徴とする請求項１に記載の情報処理装置。
【請求項７】
前記情報処理装置は、さらに、
前記視差オフセット算出部の算出した視差オフセットの最適値を適用したカメラキャリブレーションおよび３次元マップの生成処理を実行する３次元マップ生成部を有することを特徴とする請求項１〜６いずれかに記載の情報処理装置。
【請求項８】
情報処理装置において、異なる位置にほぼ平行に設置された２つのカメラによって撮影された画像を入力し、撮影画像に基づく視差オフセットの算出を実行する情報処理方法であり、
特徴点抽出部が、前記２つのカメラの撮影画像に含まれる特徴点を抽出する特徴点抽出ステップと、
特徴点マッチング処理部が、前記２つのカメラの撮影画像から抽出された特徴点の比較処理により、類似する特徴点の組み合わせからなる特徴点ペアを検出する特徴点マッチング処理ステップと、
視差オフセット算出部が、前記特徴点ペアの解析により、前記２つのカメラの撮影画像における視差オフセットを算出する視差オフセット算出ステップを有し、
前記視差オフセット算出ステップは、
前記特徴点ペアのフィルタリングにより信頼度の高いと判断される特徴点ペアを選択し、選択特徴点ペアに対応する視差オフセットデータの発生頻度分布情報としてのヒストグラムを生成し、生成したヒストグラムを利用して視差オフセットの許容値の拘束条件を設定し、設定した拘束条件に基づいて視差オフセットの最適値を算出するステップであることを特徴とする情報処理方法。
【請求項９】
前記視差オフセット算出ステップは、
前記選択特徴点ペアに対応する視差オフセットとして、水平方向（Ｘ）と垂直方向（Ｙ）に対応する視差オフセット（ｄｘ，ｄｙ）の、［ｄｘ］のヒストグラムと［ｄｙ］のヒストグラムを生成し、生成したヒストグラムを利用して視差オフセットの許容値の拘束条件を設定し、設定した拘束条件に基づいて視差オフセットの最適値を算出するステップであることを特徴とする請求項８に記載の情報処理方法。
【請求項１０】
前記視差オフセット算出ステップは、
垂直方向（Ｙ）の視差オフセットを規定する［ｄｙ］のヒストグラムのピーク位置を、垂直方向（Ｙ）に対応する視差オフセット（ｄｙ）の最適値として決定する処理を実行するステップであることを特徴とする請求項９に記載の情報処理方法。
【請求項１１】
前記視差オフセット算出ステップは、
水平方向（Ｘ）の視差オフセットを規定する［ｄｘ］のヒストグラムにおいて、予め設定した出現頻度率に応じて［ｄｘ］の最小許容値［ｄｘ，ｍｉｎ］と、最大許容値［ｄｘ，ｍａｘ］を視差オフセットの許容値の拘束条件として設定し、設定した拘束条件に基づいて、水平方向（Ｘ）の視差オフセットの最適値を算出するステップであることを特徴とする請求項９に記載の情報処理方法。
【請求項１２】
前記視差オフセット算出ステップは、
前記最小許容値［ｄｘ，ｍｉｎ］と、最大許容値［ｄｘ，ｍａｘ］の間において設定した複数の［ｄｘ］の値を適用した場合の特徴点のエラーおよび遊離（Ｏｕｔｌｉｅｒｓ）データ数を検証し、エラーおよび遊離（Ｏｕｔｌｉｅｒｓ）データ数が最小となる［ｄｘ］の値を水平方向（Ｘ）の視差オフセットの最適値として決定する処理を実行するステップであることを特徴とする請求項１１に記載の情報処理方法。
【請求項１３】
前記視差オフセット算出ステップは、
信頼度の高いと判断される特徴点ペアを選択するフィルタリング処理として、
前記特徴点ペアに対応する視差オフセットとして、水平方向（Ｘ）と垂直方向（Ｙ）に対応する視差オフセット（ｄｘ，ｄｙ）の値について、
（ａ）ｄｙが、予め設定した範囲にあることを条件とするエピポーラ拘束（Ｅｐｉｐｏｌａｒ  ｃｏｎｓｔｒａｉｎｔ）
（ｂ）ｄｘが、予め設定した範囲にあることを条件とする視差拘束（Ｄｉｓｐａｒｉｔｙ  ｃｏｎｓｔｒａｉｎｔ）、
（ｃ）上記（ａ），（ｂ）の両者を満足する複数のペア（１対多）がある場合、これらのペアは、あいまい性が高い特徴点ペアであると判定して排除する固有対応拘束、
上記（ａ）〜（ｃ）の少なくともいずれかの拘束条件を満足するか否かの定を実行して、拘束条件を満足するもののみを残存させるフィルタリング処理を実行するステップであることを特徴とする請求項８に記載の情報処理方法。
【請求項１４】
前記情報処理方法は、さらに、
３次元マップ生成部が、前記視差オフセット算出ステップにおいて算出した視差オフセットの最適値を適用したカメラキャリブレーションおよび３次元マップの生成処理を実行する３次元マップ生成ステップを有することを特徴とする請求項８〜１３いずれかに記載の情報処理方法。
【請求項１５】
情報処理装置において、異なる位置にほぼ平行に設置された２つのカメラによって撮影された画像を入力し、撮影画像に基づく視差オフセットの算出を実行させるコンピュータ・プログラムであり、
特徴点抽出部に、前記２つのカメラの撮影画像に含まれる特徴点を抽出させる特徴点抽出ステップと、
特徴点マッチング処理部に、前記２つのカメラの撮影画像から抽出された特徴点の比較処理により、類似する特徴点の組み合わせからなる特徴点ペアを検出させる特徴点マッチング処理ステップと、
視差オフセット算出部に、前記特徴点ペアの解析により、前記２つのカメラの撮影画像における視差オフセットを算出させる視差オフセット算出ステップを有し、
前記視差オフセット算出ステップは、
前記特徴点ペアのフィルタリングにより信頼度の高いと判断される特徴点ペアを選択し、選択特徴点ペアに対応する視差オフセットデータの発生頻度分布情報としてのヒストグラムを生成し、生成したヒストグラムを利用して視差オフセットの許容値の拘束条件を設定し、設定した拘束条件に基づいて視差オフセットの最適値を算出させるステップであることを特徴とするコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、および情報処理方法、並びにコンピュータ・プログラムに関する。さらに詳細には、２つのカメラによる撮影画像を用いた視差オフセットの算出や、３次元マップの作成処理を実行する情報処理装置、および情報処理方法、並びにコンピュータ・プログラムに関する。
【背景技術】
【０００２】
異なる方向から２台のカメラにより画像を撮影し、撮影画像の解析に基づいて３次元マップを作成する技術がある。この手法はステレオ法と呼ばれ、撮影に用いるカメラはステレオカメラと呼ばれる。
【０００３】
ステレオ法により３次元マップを作成するためには、カメラの撮影画像の各画素（ピクセル）と、実空間における３次元位置の対応関係を求める処理いわゆるカメラキャリブレーションが必要であり、このカメラキャリブレーションにはステレオカメラ各々のパラメータを適用した計算が必要となる。
【０００４】
カメラキャリブレーションに使用するカメラパラメータとしては、例えば、各ステレオカメラのレンズ焦点距離、レンズによって生じる歪み（ｄｉｓｔｏｒｔｉｏｎ）パラメータ、画像中心位置などのカメラ内部パラメータや、さらにカメラの位置姿勢情報などの外部パラメータがある。これらのパラメータを入力した計算によりカメラキャリブレーションが行われ３次元マップが作成される。なおステレオ法に基づく３次元マップの作成技術について開示した従来技術としては、例えば特許文献１（ＵＳ特許６００９３５９）、特許文献２（ＵＳ公開特許２００５／０２３７３８５）、特許文献３（ＵＳ特許６６０６４０４）、特許文献４（ＵＳ公開特許２００３／０１５６７５１）などがある。
【０００５】
使用するカメラの内部パラメータおよび外部パラメータが既知である場合、これらのパラメータを用いたカメラキャリブレーションおよび３次元マップの作成が可能であるが、そのためには、ステレオカメラに利用する２台のカメラは、全てのパラメータが既知であるステレオカメラの使用が必須となり、ステレオカメラの変更が許容されるだけでなく、２台のカメラの位置姿勢も完全に固定しておく必要がある。カメラの変更や、カメラのセット位置や姿勢のずれが発生した場合には、既知のパラメータの利用は不可能となる。
【特許文献１】ＵＳ特許６００９３５９
【特許文献２】ＵＳ公開特許２００５／０２３７３８５
【特許文献３】ＵＳ特許６６０６４０４
【特許文献４】ＵＳ公開特許２００３／０１５６７５１
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、上述の問題点に鑑みてなされたものであり、例えば、ステレオ法に基づく３次元マップヘの作成に利用する画像を撮影するカメラのパラメータの少なくとも一部のパラメータが未知である場合でも、カメラの撮影画像から効率的にパラメータを算出してカメラキャリブレーションを行ない、３次元マップを作成することを可能とした情報処理装置、および情報処理方法、並びにコンピュータ・プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の第１の側面は、
異なる位置にほぼ平行に設置された２つのカメラによって撮影された画像を入力し、撮影画像に基づく視差オフセットの算出を実行する情報処理装置であり、
前記２つのカメラの撮影画像に含まれる特徴点を抽出する特徴点抽出部と、
前記２つのカメラの撮影画像から抽出された特徴点の比較処理により、類似する特徴点の組み合わせからなる特徴点ペアを検出する特徴点マッチング処理部と、
前記特徴点ペアの解析により、前記２つのカメラの撮影画像における視差オフセットを算出する視差オフセット算出部を有し、
前記視差オフセット算出部は、
前記特徴点ペアのフィルタリングにより信頼度の高いと判断される特徴点ペアを選択し、選択特徴点ペアに対応する視差オフセットデータの発生頻度分布情報としてのヒストグラムを生成し、生成したヒストグラムを利用して視差オフセットの許容値の拘束条件を設定し、設定した拘束条件に基づいて視差オフセットの最適値を算出する構成であることを特徴とする情報処理装置にある。
【０００８】
さらに、本発明の情報処理装置の一実施態様において、前記視差オフセット算出部は、前記選択特徴点ペアに対応する視差オフセットとして、水平方向（Ｘ）と垂直方向（Ｙ）に対応する視差オフセット（ｄｘ，ｄｙ）の、［ｄｘ］のヒストグラムと［ｄｙ］のヒストグラムを生成し、生成したヒストグラムを利用して視差オフセットの許容値の拘束条件を設定し、設定した拘束条件に基づいて視差オフセットの最適値を算出する構成であることを特徴とする。
【０００９】
さらに、本発明の情報処理装置の一実施態様において、前記視差オフセット算出部は、垂直方向（Ｙ）の視差オフセットを規定する［ｄｙ］のヒストグラムのピーク位置を、垂直方向（Ｙ）に対応する視差オフセット（ｄｙ）の最適値として決定する処理を実行することを特徴とする。
【００１０】
さらに、本発明の情報処理装置の一実施態様において、前記視差オフセット算出部は、水平方向（Ｘ）の視差オフセットを規定する［ｄｘ］のヒストグラムにおいて、予め設定した出現頻度率に応じて［ｄｘ］の最小許容値［ｄｘ，ｍｉｎ］と、最大許容値［ｄｘ，ｍａｘ］を視差オフセットの許容値の拘束条件として設定し、設定した拘束条件に基づいて、水平方向（Ｘ）の視差オフセットの最適値を算出する構成であることを特徴とする。
【００１１】
さらに、本発明の情報処理装置の一実施態様において、前記視差オフセット算出部は、前記最小許容値［ｄｘ，ｍｉｎ］と、最大許容値［ｄｘ，ｍａｘ］の間において設定した複数の［ｄｘ］の値を適用した場合の特徴点のエラーおよび遊離（Ｏｕｔｌｉｅｒｓ）データ数を検証し、エラーおよび遊離（Ｏｕｔｌｉｅｒｓ）データ数が最小となる［ｄｘ］の値を水平方向（Ｘ）の視差オフセットの最適値として決定する処理を実行することを特徴とする。
【００１２】
さらに、本発明の情報処理装置の一実施態様において、前記視差オフセット算出部は、信頼度の高いと判断される特徴点ペアを選択するフィルタリング処理として、前記特徴点ペアに対応する視差オフセットとして、水平方向（Ｘ）と垂直方向（Ｙ）に対応する視差オフセット（ｄｘ，ｄｙ）の値について、
（ａ）ｄｙが、予め設定した範囲にあることを条件とするエピポーラ拘束（Ｅｐｉｐｏｌａｒ  ｃｏｎｓｔｒａｉｎｔ）
（ｂ）ｄｘが、予め設定した範囲にあることを条件とする視差拘束（Ｄｉｓｐａｒｉｔｙ  ｃｏｎｓｔｒａｉｎｔ）、
（ｃ）上記（ａ），（ｂ）の両者を満足する複数のペア（１対多）がある場合、これらのペアは、あいまい性が高い特徴点ペアであると判定して排除する固有対応拘束、
上記（ａ）〜（ｃ）の少なくともいずれかの拘束条件を満足するか否かの定を実行して、拘束条件を満足するもののみを残存させるフィルタリング処理を実行する構成であることを特徴とする。
【００１３】
さらに、本発明の情報処理装置の一実施態様において、前記情報処理装置は、さらに、前記視差オフセット算出部の算出した視差オフセットの最適値を適用したカメラキャリブレーションおよび３次元マップの生成処理を実行する３次元マップ生成部を有することを特徴とする。
【００１４】
さらに、本発明の第２の側面は、
情報処理装置において、異なる位置にほぼ平行に設置された２つのカメラによって撮影された画像を入力し、撮影画像に基づく視差オフセットの算出を実行する情報処理方法であり、
特徴点抽出部が、前記２つのカメラの撮影画像に含まれる特徴点を抽出する特徴点抽出ステップと、
特徴点マッチング処理部が、前記２つのカメラの撮影画像から抽出された特徴点の比較処理により、類似する特徴点の組み合わせからなる特徴点ペアを検出する特徴点マッチング処理ステップと、
視差オフセット算出部が、前記特徴点ペアの解析により、前記２つのカメラの撮影画像における視差オフセットを算出する視差オフセット算出ステップを有し、
前記視差オフセット算出ステップは、
前記特徴点ペアのフィルタリングにより信頼度の高いと判断される特徴点ペアを選択し、選択特徴点ペアに対応する視差オフセットデータの発生頻度分布情報としてのヒストグラムを生成し、生成したヒストグラムを利用して視差オフセットの許容値の拘束条件を設定し、設定した拘束条件に基づいて視差オフセットの最適値を算出するステップであることを特徴とする情報処理方法にある。
【００１５】
さらに、本発明の情報処理方法の一実施態様において、前記視差オフセット算出ステップは、前記選択特徴点ペアに対応する視差オフセットとして、水平方向（Ｘ）と垂直方向（Ｙ）に対応する視差オフセット（ｄｘ，ｄｙ）の、［ｄｘ］のヒストグラムと［ｄｙ］のヒストグラムを生成し、生成したヒストグラムを利用して視差オフセットの許容値の拘束条件を設定し、設定した拘束条件に基づいて視差オフセットの最適値を算出するステップであることを特徴とする。
【００１６】
さらに、本発明の情報処理方法の一実施態様において、前記視差オフセット算出ステップは、垂直方向（Ｙ）の視差オフセットを規定する［ｄｙ］のヒストグラムのピーク位置を、垂直方向（Ｙ）に対応する視差オフセット（ｄｙ）の最適値として決定する処理を実行するステップであることを特徴とする。
【００１７】
さらに、本発明の情報処理方法の一実施態様において、前記視差オフセット算出ステップは、水平方向（Ｘ）の視差オフセットを規定する［ｄｘ］のヒストグラムにおいて、予め設定した出現頻度率に応じて［ｄｘ］の最小許容値［ｄｘ，ｍｉｎ］と、最大許容値［ｄｘ，ｍａｘ］を視差オフセットの許容値の拘束条件として設定し、設定した拘束条件に基づいて、水平方向（Ｘ）の視差オフセットの最適値を算出するステップであることを特徴とする。
【００１８】
さらに、本発明の情報処理方法の一実施態様において、前記視差オフセット算出ステップは、前記最小許容値［ｄｘ，ｍｉｎ］と、最大許容値［ｄｘ，ｍａｘ］の間において設定した複数の［ｄｘ］の値を適用した場合の特徴点のエラーおよび遊離（Ｏｕｔｌｉｅｒｓ）データ数を検証し、エラーおよび遊離（Ｏｕｔｌｉｅｒｓ）データ数が最小となる［ｄｘ］の値を水平方向（Ｘ）の視差オフセットの最適値として決定する処理を実行するステップであることを特徴とする。
【００１９】
さらに、本発明の情報処理方法の一実施態様において、前記視差オフセット算出ステップは、信頼度の高いと判断される特徴点ペアを選択するフィルタリング処理として、前記特徴点ペアに対応する視差オフセットとして、水平方向（Ｘ）と垂直方向（Ｙ）に対応する視差オフセット（ｄｘ，ｄｙ）の値について、
（ａ）ｄｙが、予め設定した範囲にあることを条件とするエピポーラ拘束（Ｅｐｉｐｏｌａｒ  ｃｏｎｓｔｒａｉｎｔ）
（ｂ）ｄｘが、予め設定した範囲にあることを条件とする視差拘束（Ｄｉｓｐａｒｉｔｙ  ｃｏｎｓｔｒａｉｎｔ）、
（ｃ）上記（ａ），（ｂ）の両者を満足する複数のペア（１対多）がある場合、これらのペアは、あいまい性が高い特徴点ペアであると判定して排除する固有対応拘束、
上記（ａ）〜（ｃ）の少なくともいずれかの拘束条件を満足するか否かの定を実行して、拘束条件を満足するもののみを残存させるフィルタリング処理を実行するステップであることを特徴とする。
【００２０】
さらに、本発明の情報処理方法の一実施態様において、前記情報処理方法は、さらに、３次元マップ生成部が、前記視差オフセット算出ステップにおいて算出した視差オフセットの最適値を適用したカメラキャリブレーションおよび３次元マップの生成処理を実行する３次元マップ生成ステップを有することを特徴とする。
【００２１】
さらに、本発明の第３の側面は、
情報処理装置において、異なる位置にほぼ平行に設置された２つのカメラによって撮影された画像を入力し、撮影画像に基づく視差オフセットの算出を実行させるコンピュータ・プログラムであり、
特徴点抽出部に、前記２つのカメラの撮影画像に含まれる特徴点を抽出させる特徴点抽出ステップと、
特徴点マッチング処理部に、前記２つのカメラの撮影画像から抽出された特徴点の比較処理により、類似する特徴点の組み合わせからなる特徴点ペアを検出させる特徴点マッチング処理ステップと、
視差オフセット算出部に、前記特徴点ペアの解析により、前記２つのカメラの撮影画像における視差オフセットを算出させる視差オフセット算出ステップを有し、
前記視差オフセット算出ステップは、
前記特徴点ペアのフィルタリングにより信頼度の高いと判断される特徴点ペアを選択し、選択特徴点ペアに対応する視差オフセットデータの発生頻度分布情報としてのヒストグラムを生成し、生成したヒストグラムを利用して視差オフセットの許容値の拘束条件を設定し、設定した拘束条件に基づいて視差オフセットの最適値を算出させるステップであることを特徴とするコンピュータ・プログラムにある。
【００２２】
なお、本発明のコンピュータ・プログラムは、例えば、様々なプログラム・コードを実行可能な汎用コンピュータ・システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。
【００２３】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【００２４】
本発明の一実施例の構成によれば、異なる位置に設置された２つのカメラによって撮影された画像を入力し、撮影画像に基づく最適な視差オフセットの算出を実行する構成において、２つのカメラの撮影画像から特徴点ペアを検出し、特徴点ペアの解析により２つのカメラの撮影画像における視差オフセットを算出する。視差オフセット算出処理においては、特徴点ペアのフィルタリングにより信頼度の高いと判断される特徴点ペアを選択し、選択した特徴点ペアに対応する視差オフセットデータの発生頻度分布情報としてのヒストグラムを生成し、生成したヒストグラムを利用して視差オフセットの許容値の拘束条件を規定し、規定した拘束条件に基づいて視差オフセットの最適値を算出する。本構成によれば、一方のカメラについてのパラメータの一部が不明である場合にも、各カメラの撮影画像に基づいて最適な視差オフセット（ｄｘ，ｄｙ）を算出可能となり、全てのパラメータが既知であるカメラを用いなくても３次元マップを生成することができる。
【発明を実施するための最良の形態】
【００２５】
以下、図面を参照しながら本発明の実施形態に係る情報処理装置、および情報処理方法、並びにコンピュータ・プログラムの詳細について説明する。
【００２６】
本発明の一実施例に係る情報処理装置は、撮影画像に基づく３次元マップ（３Ｄｍａｐ）の作成処理を行う。具体的には撮影画像に基づいて、視差オフセットを算出し、算出した視差オフセットによってパラメータを取得し、取得パラメータによるカメラキャリブレーションを実行して３次元マップ（３Ｄｍａｐ）を作成する。以下この処理の詳細について説明する。図１は、本発明の情報処理装置の一実施例構成を示図である。
【００２７】
まず、図１を参照して本発明の情報処理装置の実行する処理の概要について説明する。個々の構成部の処理の詳細については後述する。２つのカメラ１０１ａ，１０１ｂ、異なる位置に設定され、画像を異なる方向から撮影する。なお、これらのカメラ１０１ａ，１０１ｂのパラメータは、少なくとも一方のカメラについては、一部のみが取得済みであり一部が不明である。具体的には、例えば、
（ａ）内部パラメータ
イメージサイズ、ピクセルサイズ、焦点距離、歪曲収差、
（ｂ）外部パラメータ
ステレオベースライン
これらのパラメータが２つのカメラ１０１ａ，１０１ｂの双方において既知であり、
（ａ）内部パラメータ
画像中心（ｐｒｉｎｃｉｐａｌ  ｐｏｉｎｔ）
（ｂ）外部パラメータ
カメラ位置姿勢（ｈｏｍｏｇｒａｐｈｉｅｓ）
これらのパラメータが２つのカメラ１０１ａ，１０１の一方において既知であり他方において未知である。
【００２８】
特徴点抽出部１０２は、２つのカメラ１０１ａ，１０１ｂの撮影画像を解析し、特徴点の抽出処理を行う。特徴点マッチング処理部１０３は、特徴点抽出部１０２の抽出した２つのカメラ１０１ａ，１０１ｂの撮影画像の各々の特徴点のマッチング処理を実行する。視差オフセット算出部１０４は、特徴点マッチング処理部１０３の生成した特徴点のマッチング情報を入力して、２つのカメラ１０１ａ，１０１ｂの視差オフセット（Ｄｉｓｐａｒｉｔｙ  Ｏｆｆｓｅｔ）を算出する。
【００２９】
キャリブレーション＆３Ｄマップ生成部１０５は、視差オフセット算出部１０４が算出した２つのカメラ１０１ａ，１０１ｂの視差オフセット（Ｄｉｓｐａｒｉｔｙ  Ｏｆｆｓｅｔ）を適用してカメラキャリブレーションを実行し、撮影画像に基づく３次元マップ（３Ｄｍａｐ）の作成処理を行う。
【００３０】
図２に示すフローチャートは、本発明の一実施例に係る情報処理装置において実行する３次元マップ（３Ｄｍａｐ）の作成処理の全体シーケンスである。本発明の情報処理装置では、図１に示すフローチャートに従った処理によって３次元マップの作成を行う。
【００３１】
まず、ステップＳ１０１において、２台のカメラによる撮影画像取得処理を実行する。図１に示す異なる位置に設定され、画像を異なる方向から撮影するカメラ１０１ａ，１０１ｂによって画像の撮影を行う。
【００３２】
次に、ステップＳ１０２において、２台のカメラによる撮影画像からの特徴点抽出を実行する。これは、図１に示す特徴点抽出部１０２において実行され、特徴点抽出部１０２は、２つのカメラ１０１ａ，１０１ｂの撮影画像を解析し、特徴点の抽出処理を行う。
【００３３】
特徴点抽出処理の一例として、ハリスコーナーディテクター（Ｈａｒｒｉｓ  Ｃｏｒｎｅｒ  Ｄｅｔｅｃｔｏｒ）を用いた処理例について図３を参照して説明する。情報処理装置のデータ処理部は、特徴点抽出に際して図３に示すようにカメラによって撮影された画像２００から複数のハリスコーナーイメージ２１０〜２１２と、ラプラシアンイメージ２２０〜２２２を生成する。
【００３４】
ハリスコーナーイメージは、取得イメージに対してハリスコーナーディテクター（Ｈａｒｒｉｓ  Ｃｏｒｎｅｒ  Ｄｅｔｅｃｔｏｒ）を適用して生成されるイメージデータである。これらのハリスコーナーイメージ２１０〜２１２から、例えば周囲８画素に比較して値の高い画素ポイント（ｍａｘｉｍａ  ｐｏｉｎｔ）２１５を検出点として抽出する。さらに、取得イメージ２００に対して、ＬｏＧ（Ｌａｐｌａｃｉａｎ  ｏｆ  Ｇａｕｓｓｉａｎ）フィルタを適用して複数レベル（解像度）のラプラシアンイメージ２２０〜２２２を生成する。ＬｏＧ（Ｌａｐｌａｃｉａｎ  ｏｆ  Ｇａｕｓｓｉａｎ）フィルタは、画像の輪郭強調のために用いられる２次微分フィルタの一種であり、人間の視覚系で網膜からの情報が外側膝状体で中継されるまでに行われている処理の近似モデルとして用いられるものである。
【００３５】
特徴点抽出処理は、ＬｏＧフィルタ出力画像であるラプラシアンイメージ２２０〜２２２の所定のレベル範囲内の解像度変化によって位置の変化がないかハリスコーナーイメージ２１０〜２１２から得られた検出点の位置に対応する箇所に対して調べ、変化がない点を特徴点とする。これにより、画像の拡大縮小操作に対してロバストな特徴点間のマッチングが実現できる。なお、これらの特徴点抽出処理の詳細については、例えば、特開２００４−３２６６９３号公報（特願２００３−１２４２２５）に記載されており、特徴点抽出部１０２における本発明における特徴点抽出処理としてこの手法の適用が可能である。
【００３６】
この特徴点の検出は、画像を異なる方向から撮影する図１に示すカメラ１０１ａ，１０１ｂによって撮影された画像の各々について実行され、検出された特徴点情報が、図１に示す特徴点マッチング処理部１０３に入力され、図２に示すフローのステップＳ１０３の処理、すなわち、各カメラの撮影画像の特徴点マッチング処理が実行される。
【００３７】
この特徴点マッチング処理の詳細シーケンスについて、図４に示すフローチャートを参照して説明する。ステップＳ２０１において第１カメラの特徴点を抽出し、ステップＳ２０２において第２カメラの特徴点を抽出する。これらの特徴点は、特徴点抽出部１０２において抽出された特徴点である。
【００３８】
次に、ステップＳ２０３において特徴点ペアを検出する。特徴点ペアの検出は、第１カメラの特徴点と第２カメラの特徴点との対応付け処理である。具体的には、例えば先に紹介した特開２００４−３２６６９３号公報（特願２００３−１２４２２５）に記載された手法を適用することができる。
【００３９】
この特開２００４−３２６６９３号公報（特願２００３−１２４２２５）に記載された特徴点ペアの検出手法の概要について説明する。まず、抽出された各特徴点について特徴量を抽出し保持する。特徴量としては、特徴点の近傍領域各点の濃度勾配情報（勾配強度及び勾配方向）を用いる。特徴量を算出する特徴点近傍領域としては、回転変化に対して構造の変わらないような、特徴点に関して対称なものを選択することが好ましい。これにより、回転変化に対するロバスト性を実現することができる。例えば、（ｉ）特徴点から半径ｒピクセルの範囲内を特徴点近傍領域とする手法や、（ｉｉ）特徴点を中心に幅σの特徴点に関して対称な２次元ガウス重みを濃度勾配に掛ける手法を用いることができる。また、特徴点近傍の勾配方向に関するヒストグラム（方向ヒストグラム）も特徴量として取得する。
【００４０】
次に、２つのカメラから取得された特徴点に対応する特徴量を比較して、類似する特徴量を有する特徴点のペア（候補対応特徴点ペア）を選択する。例えば、第１のカメラの撮影画像から選択した１つの特徴点の特徴量（方向ヒストグラム）と相違度の小さいＫ個の特徴点を第２のカメラの撮影画像から選択し、ｋ個の特徴点ペア候補を選択し、予め定めた閾値以上の誤差を有する特徴点ペア候補を除去する処理を行い、確からしい特徴点ペアのみを残存させる。
【００４１】
図１に示す特徴点マッチング処理部１０３は、このような処理によって、各カメラの撮影画像の特徴点マッチング処理を実行する。なお、この特徴点マッチング処理の詳細は、前述したように特開２００４−３２６６９３号公報（特願２００３−１２４２２５）に記載されている。
【００４２】
上述の特徴点マッチングが終了すると、次に、図２に示すフローのステップＳ１０４の処理を実行する。ステップＳ１０４の処理は視差オフセット算出のための第１段階処理であり、具体的には、視差拘束（Ｄｉｓｐａｒｉｔｙ  ｃｏｎｓｔｒａｉｎｔ）の算出処理である。その後、ステップＳ１０５において、ステップＳ１０４で算出した視差拘束（Ｄｉｓｐａｒｉｔｙ  ｃｏｎｓｔｒａｉｎｔ）を適用して、視差オフセットの算出処理が行われる。これらの処理は、図１に示す視差オフセット算出部１０４において実行される。
【００４３】
まず、視差オフセットについて、図５、図６を参照して説明する。視差オフセットは、２台のカメラ、すなわち図１に示すカメラ１０１ａと、カメラ１０１ｂの対応する特徴点の物理的位置関係および測定誤差を含む画素ずれに対応する値である。
【００４４】
図５を用いて平行化画像について述べる。例えば任意の姿勢に配置された２台のカメラで撮影された画像は、図５（ａ）に示す画像２１１，２１２のように異なる方向からの画像データとなる。この撮影画像をそのまま利用しても、撮影画像上に設定されるエピポーラ線は平行なラインにならず、例えば対応点探索を、エピポーラ線を探索ラインとして行う場合、計算量が膨大となってしまう。そこで、図５（ａ）に示す画像２１１，２１２を変換して、平行な配置にあるカメラで撮影したと同様の画像、すなわち平行化画像２１５，２１６を生成し、この平行化画像２１５上に設定したエピホーララインでの対応点探索を行う。
【００４５】
平行化画像データの例が、図５（ｂ）に示すようなデータであり、図５（ｂ）に示す画像２１１，２１２のように異なる方向からの画像データを変換して、平行な配置にあるカメラで撮影したと同様の画像、すなわち平行化画像２１５，２１６を生成し、この平行化画像２１５上に設定したエピホーララインでの対応点探索を行うことで容易な対応点抽出が可能となる。
【００４６】
この平行化処理に適用する変換行列は、平面間変換行列と呼ばれる。図５（ｂ）に示す撮影画像２１１に対して平面間変換行列Ｈ１を適用した画像変換を行うことで、平行化画像２１５が取得され、図５（ｂ）に示す撮影画像２１２に対して平面間変換行列Ｈ２を適用した画像変換を行うことで、平行化画像２１６が取得される。これらの平行化画像２１５，２１６に設定されたエピポーララインは平行に設定され、対応点（特徴点ペア）探索が容易に実行できる。平面間変換行列を適用した画像変換処理はステレオ画像の並行化処理と呼ばれる。
【００４７】
図６には、互いの姿勢がほぼ平行に設置された２つのカメラによって生成した２つの画像２１５，２１６を示し、それぞれの画像２１５，２１６に平行化画像の撮影画像中心（ｐｒｉｎｃｉｐａｌ  ｐｏｉｎｔ）２３１、２３２を示している。カメラの位置・姿勢は厳密に平行化されていないため、平行化画像の撮影画像中心（ｐｒｉｎｃｉｐａｌ  ｐｏｉｎｔ）２３１、２３２は、互いにずれた位置にある。
【００４８】
第１画像２１５の平行化画像の撮影画像中心（ｅｘ１，ｅｙ１）は、第１画像２１５の中心（画像中心（Ｉｍａｇｅ  Ｃｅｎｔｅｒ））からの座標として示される。横方向がｘ、縦方向をｙとして示している。同様に、第２画像２１６の平行化画像の撮影画像中心（ｅｘ２，ｅｙ２）は、第２画像２１６の中心（画像中心（Ｉｍａｇｅ  Ｃｅｎｔｅｒ））からの座標として示される。
【００４９】
このような平行化画像の撮影画像中心（ｐｒｉｎｃｉｐａｌ  ｐｏｉｎｔ）２３１、２３２を有し、且つ互いの姿勢がほぼ平行となるように設置された２つのカメラによって撮影された２つの画像２１５，２１６に基づいて、視差オフセット（Ｄｉｓｐａｒｉｔｙ  Ｏｆｆｓｅｔ）の算出が行われる。視差オフセットは、２つの画像の対応画素各々について算出され、対応画素各々のｘ方向のずれ（ｄｘ）とｙ方向のずれ（ｄｙ）との組データ（ｄｘ，ｄｙ）として表すことができる。互いの姿勢がほぼ平行に設置されているという前提条件を用いると、視差オフセット（ｄｘ，ｄｙ）は、
第１画像の平面間変換行列：Ｈ１＝（ｔｘ１，ｔｙ１）
第２画像の平面間変換行列：Ｈ２＝（ｔｘ２，ｔｙ２）
第１画像の画像中心：（ｅｘ１，ｅｙ１）
第２画像の画像中心：（ｅｘ２，ｅｙ２）
と近似することができ、
視差オフセット（ｄｘ，ｄｙ）＝（ｅｘ１＋ｔｘ１−ｅｘ２−ｔｘ２，ｅｙ１＋ｔｙ１−ｅｙ２−ｔｙ２）
として表現することができる。
【００５０】
この視差オフセットを算出することができれば、カメラキャリブレーションが可能となる。すなわち、例えば一方のカメラ（第１カメラ）を固定して、第１画像の平行化画像の撮影画像中心：（ｅｘ１，ｅｙ１）を平行化画像の画像中心（イメージ中心（Ｉｍａｇｅ  Ｃｅｎｔｅｒ））に設定（０，０）するような構成とすれば、他方のカメラ（第２カメラ）について、
（ａ）内部パラメータ
画像中心（ｐｒｉｎｃｉｐａｌ  ｐｏｉｎｔ）
（ｂ）外部パラメータ
カメラ位置姿勢（ｈｏｍｏｇｒａｐｈｉｅｓ）
これらのパラメータが未知である場合でも、第１カメラの撮影画像に基づく平行化画像である第１画像の画像中心データ：（ｅｘ１，ｅｙ１）を利用して、各カメラの撮影画像における対応点（特徴点ペア）について、視差オフセットを算出することが可能となり、カメラキャリブレーションが可能となる。
【００５１】
図２に示すフローのステップＳ１０４の処理、すなわち、視差オフセット算出のための第１段階処理として行われる視差拘束（Ｄｉｓｐａｒｉｔｙ  ｃｏｎｓｔｒａｉｎｔ）等の算出処理の詳細シーケンスについて、図７のフローチャートを参照して説明する。この処理は、図１に示す視差オフセット算出部１０４において実行される。
【００５２】
この視差オフセット算出のための第１段階処理として行われる視差拘束（Ｄｉｓｐａｒｉｔｙ  ｃｏｎｓｔｒａｉｎｔ）の算出処理は、視差オフセットの拘束条件を設定する処理であり、２つの平行化画像の対応画素各々のｘ方向のずれ（ｄｘ）とｙ方向のずれ（ｄｙ）との組データである視差オフセット（ｄｘ，ｄｙ）の許容範囲を設定する処理である。具体的には、視差オフセット（ｄｘ，ｄｙ）のｙ方向の最適値（ｄｙ，ｂｅｓｔ）の算出、および、ｘ方向の最小許容値（ｄｘ，ｍｉｎ）、最大許容値（ｄｘ，ｍａｘ）の算出が実行される。
【００５３】
まず、図７に示すフローチャートのステップＳ３０１において、視差オフセットの拘束条件としての視差拘束の初期設定を行う。この初期値は、おおよそのカメラの設定位置データや撮影画像に基づいて決定することができる。
【００５４】
例えば、視差オフセット（ｄｘ，ｄｙ）の許容範囲を示す視差拘束の初期設定例として、視差オフセット（ｄｘ，ｄｙ）のｄｘ，ｄｙ各々についての許容範囲を、最小許容値：ｄ'ｘ，ｍｉｎ，ｄ'ｙ，ｍｉｎと、最大許容値：ｄ'ｘ，ｍａｘ，ｄ'ｙ，ｍａｘを用いて、
ｄ'ｘ，ｍｉｎ＜ｄｘ＜ｄ'ｘ，ｍａｘ、
ｄ'ｙ，ｍｉｎ＜ｄｙ＜ｄ'ｙ，ｍａｘ、
上記のように表現した場合、
ｄ'ｘ，ｍｉｎ＝−５０、
ｄ'ｘ，ｍａｘ＝５０、
ｄ'ｙ，ｍｉｎ＝−５０、
ｄ'ｙ，ｍａｘ＝５０、
このような初期設定とする。
なお、−５０、５０の単位は、例えば画素（ｐｉｘｅｌ）数である。なお単位は、画素数に限らず、画像上の実距離や、実空間の距離などを利用してもよい。
【００５５】
ステップＳ３０１では、視差オフセット（ｄｘ，ｄｙ）の許容範囲を示す視差拘束の初期設定例として、視差オフセット（ｄｘ，ｄｙ）のｄｘ，ｄｙ各々について、例えば、
−５０＜ｄｘ＜５０、
−５０＜ｄｙ＜５０、
このような初期設定を行う。
【００５６】
次に、ステップＳ３０２において、互いの姿勢がほぼ平行に設置された２つのカメラによって撮影された画像に対して、ステレオフィルタを適用し、ステップＳ３０１で設定した視差拘束等を満足しない特徴点ペア（対応点）を削除する。
【００５７】
この処理は、図２に示すフローのステップＳ１０１、Ｓ１０２において抽出した特徴点ペア、すなわち、先に図４のフローを参照して説明した特徴点ペア抽出処理によって抽出した特徴点ペアの各々について、ステップＳ３０１で設定した視差拘束を満足しない特徴点ペアを削除する処理である。
【００５８】
視差拘束等の拘束条件を満足しない特徴点ペアを削除するためのフィルタを、ここではステレオフィルタと呼ぶ。ステレオフィルタは、以下の処理を行う。
（入力）
（１）特徴点ペア：（ｆｌ，ｆｒ）＝（ｘｌ，ｙｌ），（ｘｒ，ｙｒ）、
（２）視差オフセット（ｄｘ，ｄｙ）のｄｘ，ｄｙ各々についての最小許容値：ｄ'ｘ，ｍｉｎ，ｄ'ｙ，ｍｉｎと、最大許容値：ｄ'ｘ，ｍａｘ，ｄ'ｙ，ｍａｘ、
とする。なお、（ｆｌ，ｆｒ）＝（ｘｌ，ｙｌ），（ｘｒ，ｙｒ）は、図２に示すフローのステップＳ１０１、Ｓ１０２において抽出した２台のカメラの撮影画像から取得した特徴点ペアの平行化画像における座標位置を示している。
特徴点ペア中、左側のカメラ（カメラＬ）の特徴点の座標位置をｆｌ＝（ｘｌ，ｙｌ）とし、右側のカメラ（カメラＲ）の特徴点の座標位置をｆｒ＝（ｘｒ，ｙｒ）として表現している。
【００５９】
これらの入力情報に基づいて、各特徴点ペアが、以下の条件を満足するか否かを判定する。
（判定処理）
（ｆｌ，ｆｒ）＝（ｘｌ，ｙｌ），（ｘｒ，ｙｒ）
が、
（ａ）エピポーラ拘束（Ｅｐｉｐｏｌａｒ  ｃｏｎｓｔｒａｉｎｔ）
ｄｙ，ｍｉｎ−δｙ＜ｙｌ−ｙｒ＜ｄｙ，ｍａｘ＋δｙ、
なお、δｙは、予め設定されたエピポーララインの設定誤差である。
（ｂ）視差拘束（Ｄｉｓｐａｒｉｔｙ  ｃｏｎｓｔｒａｉｎｔ）
ｄｘ，ｍｉｎ＜ｘｌ−ｘｒ、
（ｃ）固有対応拘束（Ｕｎｉｑｕｅ  ｍａｔｃｈ  ｃｏｎｓｔｒａｉｎｔ）
上記（ａ），（ｂ）の両者を満足する複数のペア（１対多）がある場合、これらのペアは、あいまい性が高い特徴点ペアであると判定して排除、
【００６０】
（出力）
上記（ａ）〜（ｃ）の拘束条件を全て満足する特徴点ペアのみを選択して出力する。
【００６１】
ステップＳ３０２では、平行化画像に対するステレオフィルタを適用し、上記の処理を実行して、視差拘束等を満足しない特徴点ペアを削除し信頼性の高い特徴点ペアのみを残存させる特徴点ペア選択処理を行う。
【００６２】
上記（ａ）〜（ｃ）のフィルタリング処理の具体例について、図８〜図１０を参照して説明する。
図８（Ａ）は、
（ａ）エピポーラ拘束（Ｅｐｉｐｏｌａｒ  ｃｏｎｓｔｒａｉｎｔ）
ｄｙ，ｍｉｎ−δｙ＜ｙｌ−ｙｒ＜ｄｙ，ｍａｘ＋δｙ、
この拘束条件を適用した特徴点ペアの削除、選択処理例を示す図である。
【００６３】
図８（Ａ）において、第１カメラ画像（Ｌ）から選択された特徴点［ｆｌ１＝（ｘｌ１，ｙｌ１）］に対応する特徴点ペアとして、第２カメラ画像（Ｒ）から２つの特徴点［ｆｒ１ａ＝（ｘｒ１ａ，ｙｒ１ａ）］と、［ｆｒ１ｂ＝（ｘｒ１ｂ，ｙｒ１ｂ）］が選択されている場合、
第１の特徴点ペア：［ｆｌ１＝（ｘｌ１，ｙｌ１）］と［ｆｒ１ａ＝（ｘｒ１ａ，ｙｒ１ａ）］
この第１の特徴点ペアのｙ座標データは、
エピポーラ拘束条件：ｄｙ，ｍｉｎ−δｙ＜ｙｌ−ｙｒ＜ｄｙ，ｍａｘ＋δｙ、
を満足しないが、
第２の特徴点ペア：［ｆｌ１＝（ｘｌ１，ｙｌ１）］と［ｆｒ１ｂ＝（ｘｒ１ｂ，ｙｒ１ｂ）］
この第２の特徴点ペアのｙ座標データは、
エピポーラ拘束条件：ｄｙ，ｍｉｎ−δｙ＜ｙｌ−ｙｒ＜ｄｙ，ｍａｘ＋δｙ、
を満足する。
この場合、
第１の特徴点ペア：［ｆｌ１＝（ｘｌ１，ｙｌ１）］と［ｆｒ１ａ＝（ｘｒ１ａ，ｙｒ１ａ）］は、削除され、
第２の特徴点ペア：［ｆｌ１＝（ｘｌ１，ｙｌ１）］と［ｆｒ１ｂ＝（ｘｒ１ｂ，ｙｒ１ｂ）］
この特徴点ペアが、エピポーラ拘束（Ｅｐｉｐｏｌａｒ  ｃｏｎｓｔｒａｉｎｔ）を満足する特徴点ペアとして選択される。
【００６４】
図８（Ｂ）は、
（ｂ）視差拘束（Ｄｉｓｐａｒｉｔｙ  ｃｏｎｓｔｒａｉｎｔ）
ｄｘ，ｍｉｎ＜ｘｌ−ｘｒ、
この拘束条件を適用した特徴点ペアの削除、選択処理例を示す図である。
【００６５】
図８（Ｂ）において、第２カメラ画像（Ｒ）から選択された１つの特徴点［ｆｒ２ａ＝（ｘｒ２ａ，ｙｒ２ａ）］に対応する特徴点ペアとして第１カメラ画像（Ｌ）から選択された特徴点［ｆｌ２ａ＝（ｘｌ２ａ，ｙｌ２ａ）］と、［ｆｌ２ｂ＝（ｘｌ２ｂ，ｙｌ２ｂ）］が選択されている場合、
第１の特徴点ペア：［ｆｌ２ａ＝（ｘｌ２ａ，ｙｌ２ａ）］と［ｆｒ２ａ＝（ｘｒ２ａ，ｙｒ２ａ）］
この第１の特徴点ペアのｘ座標データは、
視差拘束：ｄｘ，ｍｉｎ＜ｘｌ−ｘｒ、
を満足しないが、
第２の特徴点ペア：［ｆｌ２ｂ＝（ｘｌ２ｂ，ｙｌ２ｂ）］と［ｆｒ２ａ＝（ｘｒ２ａ，ｙｒ２ａ）］
この第２の特徴点ペアのｘ座標データは、
視差拘束：ｄｘ，ｍｉｎ＜ｘｌ−ｘｒ、
を満足する。
この場合、
第１の特徴点ペア：［ｆｌ２ａ＝（ｘｌ２ａ，ｙｌ２ａ）］と［ｆｒ２ａ＝（ｘｒ２ａ，ｙｒ２ａ）］は、削除され、
第２の特徴点ペア：［ｆｌ２ｂ＝（ｘｌ２ｂ，ｙｌ２ｂ）］と［ｆｒ２ａ＝（ｘｒ２ａ，ｙｒ２ａ）］この特徴点ペアが、視差拘束（Ｄｉｓｐａｒｉｔｙ  ｃｏｎｓｔｒａｉｎｔ）を満足する特徴点ペアとして選択される。
【００６６】
図９は、（ｃ）固有対応拘束（Ｕｎｉｑｕｅ  ｍａｔｃｈ  ｃｏｎｓｔｒａｉｎｔ）の非適合例と適合例を示している。固有対応拘束は、上記のエピポーラ拘束と、視差拘束の両者を満足する複数のペア（１対多）がある場合、これらのペアは、あいまい性が高い特徴点ペアであると判定して排除する拘束条件である。
【００６７】
図９（Ａ）は、固有対応拘束の非適合例を示している。第１カメラ画像（Ｌ）から選択された特徴点［ｆｌ１ａ＝（ｘｌ１ａ，ｙｌ１ａ）］と、第２カメラ画像（Ｒ）の特徴点［ｆｒ１ａ＝（ｘｒ１ａ，ｙｒ１ａ）］とは特徴点ペアとして選択され、かつ、この特徴点ペアはエピポーラ拘束と、視差拘束の両者を満足する。
しかし、この第１カメラ画像（Ｌ）から選択された特徴点［ｆｌ１ａ＝（ｘｌ１ａ，ｙｌ１ａ）］は、第２カメラ画像（Ｒ）の他の特徴点［ｆｒ１ｂ＝（ｘｒ１ｂ，ｙｒ１ｂ）］とも特徴点ペアとして選択され、かつ、この特徴点ペアも、エピポーラ拘束と、視差拘束の両者を満足する。
【００６８】
さらに、図９（Ａ）に示す第１カメラ画像（Ｌ）から選択されたもう１つの特徴点［ｆｌ１ｂ＝（ｘｌ１ｂ，ｙｌ１ｂ）］についても、第２カメラ画像（Ｒ）の２つの特徴点［ｆｒ１ａ＝（ｘｒ１ａ，ｙｒ１ａ）］、［ｆｒ１ｂ＝（ｘｒ１ｂ，ｙｒ１ｂ）］のいずれとも、エピポーラ拘束と、視差拘束の両者を満足する特徴点ペアとして選択されている。
【００６９】
このように、エピポーラ拘束と、視差拘束の両者を満足する複数のペア（１対多）がある場合、これらのペアは、あいまい性が高い特徴点ペアであると判定して排除する。
【００７０】
図９（Ｂ）は、固有対応拘束の適合例を示している。第１カメラ画像（Ｌ）（平行化画像）から選択された特徴点［ｆｌ１ａ＝（ｘｌ１ａ，ｙｌ１ａ）］と、第２カメラ画像（Ｒ）（平行化画像）の特徴点［ｆｒ１ａ＝（ｘｒ１ａ，ｙｒ１ａ）］とは特徴点ペアとして選択され、かつ、この特徴点ペアはエピポーラ拘束と、視差拘束の両者を満足する。
【００７１】
この第１カメラ画像（Ｌ）から選択された特徴点［ｆｌ１ａ＝（ｘｌ１ａ，ｙｌ１ａ）］は、第２カメラ画像（Ｒ）の他の特徴点［ｆｒ１ｂ＝（ｘｒ１ｂ，ｙｒ１ｂ）］とも特徴点ペアとして選択されているが、この特徴点ペアは、エピポーラ拘束と、視差拘束の両者を満足しない。
【００７２】
この場合は、第１カメラ画像（Ｌ）の特徴点［ｆｌ１ａ＝（ｘｌ１ａ，ｙｌ１ａ）］と、第２カメラ画像（Ｒ）の特徴点［ｆｒ１ａ＝（ｘｒ１ａ，ｙｒ１ａ）］からなる特徴点ペアは、固有対応拘束の適合条件を満足する特徴点ペアとして選択される。
【００７３】
同様に、図９（Ｂ）に示す第１カメラ画像（Ｌ）から選択された特徴点［ｆｌ１ｂ＝（ｘｌ１ｂ，ｙｌ１ｂ）］と、第２カメラ画像（Ｒ）の特徴点［ｆｒ１ｂ＝（ｘｒ１ｂ，ｙｒ１ｂ）］とは特徴点ペアとして選択され、かつ、この特徴点ペアはエピポーラ拘束と、視差拘束の両者を満足する。
【００７４】
この第１カメラ画像（Ｌ）から選択された特徴点［ｆｌ１ｂ＝（ｘｌ１ｂ，ｙｌ１ｂ）］は、第２カメラ画像（Ｒ）の他の特徴点［ｆｒ１ａ＝（ｘｒ１ａ，ｙｒ１ａ）］とも特徴点ペアとして選択されているが、この特徴点ペアは、エピポーラ拘束と、視差拘束の両者を満足しない。
【００７５】
この場合は、第１カメラ画像（Ｌ）の特徴点［ｆｌ１ｂ＝（ｘｌ１ｂ，ｙｌ１ｂ）］と、第２カメラ画像（Ｒ）の特徴点［ｆｒ１ｂ＝（ｘｒ１ｂ，ｙｒ１ｂ）］からなる特徴点ペアは、固有対応拘束の適合条件を満足する特徴点ペアとして選択される。
【００７６】
上述したように、図７に示すフローのステップＳ３０２では、互いの姿勢がほぼ平行となるように設置された２つのカメラによって撮影された画像対して、ステレオフィルタを適用し、ステップＳ３０１で設定した視差拘束等を満足しない特徴点ペア（対応点）を削除する。具体的には、上述したように、
（ａ）エピポーラ拘束（Ｅｐｉｐｏｌａｒ  ｃｏｎｓｔｒａｉｎｔ）
（ｂ）視差拘束（Ｄｉｓｐａｒｉｔｙ  ｃｏｎｓｔｒａｉｎｔ）
（ｃ）固有対応拘束（Ｕｎｉｑｕｅ  ｍａｔｃｈ  ｃｏｎｓｔｒａｉｎｔ）
これらの拘束条件を満足しない特徴点ペアを、信頼性の低い特徴点ペアであると判断して削除する。
【００７７】
このように信頼性の低い特徴点ペアの排除処理による特徴点ペアの削減例を図１０に示す。図１０（Ａ）は、図２のフローにおけるステップＳ１０２，Ｓ１０３の処理、さらに図４に示すフローに従った特徴点ペア抽出処理によって抽出された特徴点ペアの抽出例を示している。第１カメラ画像（Ｌ）、第２カメラ画像（Ｒ）に示す黒の矩形枠が特徴点ペアとして選択された領域である。
【００７８】
この図１０（Ａ）に示すデータに対して、ステレオフィルタを適用して、
（ａ）エピポーラ拘束（Ｅｐｉｐｏｌａｒ  ｃｏｎｓｔｒａｉｎｔ）
（ｂ）視差拘束（Ｄｉｓｐａｒｉｔｙ  ｃｏｎｓｔｒａｉｎｔ）
（ｃ）固有対応拘束（Ｕｎｉｑｕｅ  ｍａｔｃｈ  ｃｏｎｓｔｒａｉｎｔ）
これらの拘束条件を満足しない特徴点ペアを、信頼性の低い特徴点ペアであると判断して削除することで、図１０（Ｂ）に示すように信頼性の高い特徴点ペアのみが選択される。
【００７９】
図１０（Ｂ）に示す第１カメラ画像（Ｌ）、第２カメラ画像（Ｒ）に示す黒の矩形枠がステレオフィルタの適用後に残存した特徴点ペアであり、信頼性の高い特徴点ペアとして選択された領域である。
【００８０】
次に、図７に示すフローのステップＳ３０３に進み、残存する特徴点ペアに基づく、視差オフセット・ヒストグラムを生成する。すなわち、ステレオフィルタを適用して、
（ａ）エピポーラ拘束（Ｅｐｉｐｏｌａｒ  ｃｏｎｓｔｒａｉｎｔ）
（ｂ）視差拘束（Ｄｉｓｐａｒｉｔｙ  ｃｏｎｓｔｒａｉｎｔ）
（ｃ）固有対応拘束（Ｕｎｉｑｕｅ  ｍａｔｃｈ  ｃｏｎｓｔｒａｉｎｔ）
これらの拘束条件を満足する特徴点ペア、具体的には、図１０（Ｂ）に示すような信頼性の高い特徴点ペアに基づく、視差オフセット・ヒストグラムを生成する。
【００８１】
視差オフセットは前述したように、互いの姿勢がほぼ平行に設置された２つカメラ画像の特徴点ペアである対応画素各々について算出され、対応画素各々の水平方向（ｘ方向）のずれ（ｄｘ）と、垂直方向（ｙ方向）のずれ（ｄｙ）との組データ（ｄｘ，ｄｙ）、すなわち、
視差オフセット（ｄｘ，ｄｙ）＝（ｅｘ１＋ｔｘ１−ｅｘ２−ｔｘ２，ｅｙ１＋ｔｙ１−ｅｙ２−ｔｙ２）
として表すことができる。ただし、
第１画像の平面間変換行列：Ｈ１＝（ｔｘ１，ｔｙ１）
第２画像の平面間変換行列：Ｈ２＝（ｔｘ２，ｔｙ２）
第１画像の画像中心：（ｅｘ１，ｅｙ１）
第２画像の画像中心：（ｅｘ２，ｅｙ２）
と近似している。
【００８２】
ステップＳ３０３では、ステレオフィルタの適用によって残された信頼性の高い特徴点ペアについての視差オフセット（ｄｘ，ｄｙ）の各値［ｄｘ］、［ｄｙ］のヒストグラム（頻度分布）を生成する。すなほち、水平方向（Ｘ）と垂直方向（Ｙ）に対応する［ｄｘ］のヒストグラムと［ｄｙ］のヒストグラムを生成する。
【００８３】
例えば、図１１、図１２に示すヒストグラムが生成される。図１１は、ステレオフィルタの適用によって残された信頼性の高い特徴点ペアについての視差オフセット（ｄｘ，ｄｙ）の値［ｄｙ］のヒストグラム（頻度分布）であり、図１２は、［ｄｘ］のヒストグラム（頻度分布）である。
【００８４】
次にステップＳ３０４において、視差オフセット・ヒストグラムに基づいて、新たな視差拘束（Ｄｉｓｐａｒｉｔｙ  ｃｏｎｘｔｒａｉｎｔ）を設定する。この新たな視差拘束の設定は、
視差オフセット（ｄｘ，ｄｙ）の各値［ｄｘ］、［ｄｙ］について、
ｄｘ：許容最小値［ｄｘ，ｍｉｎ］と許容最大値［ｄｘ，ｍａｘ］
ｄｙ：最適値［ｄｙ，ｂｅｓｔ］
これらの値を決定する処理として行われる。
【００８５】
まず、図１１に示すステレオフィルタの適用によって残された信頼性の高い特徴点ペアについての視差オフセット（ｄｘ，ｄｙ）の値［ｄｙ］のヒストグラム（頻度分布）からｄｙの最適値［ｄｙ，ｂｅｓｔ］を決定する処理について説明する。
【００８６】
ｄｙは、左右の画像にあるエピポーラ線のＹ軸方向のずれを表している。ｄｙは全てのマッチングペアに共通するパラメータであるので、ｄｙの最適値［ｄｙ，ｂｅｓｔ］は、ｄｙのヒストグラムのピーク位置となるｄｙの値に設定する。図１１に示すように、ｄｙのヒストグラムのピーク位置となるｄｙの値をｄｙの最適値［ｄｙ，ｂｅｓｔ］として決定する。
【００８７】
次に、図１２に示すステレオフィルタの適用によって残された信頼性の高い特徴点ペアについての視差オフセット（ｄｘ，ｄｙ）の値［ｄｘ］のヒストグラム（頻度分布）からｄｘの許容最小値［ｄｘ，ｍｉｎ］と許容最大値［ｄｘ，ｍａｘ］を決定する処理について説明する。
【００８８】
ｄｘの許容最小値［ｄｘ，ｍｉｎ］と許容最大値［ｄｘ，ｍａｘ］は、予め設定した閾値［ｔｈｏｕｔ］、［ｔｈｉｎｆ］に基づいて決定する。
閾値［ｔｈｏｕｔ］は、ｄｘの許容最小値［ｄｘ，ｍｉｎ］を決定する閾値であり、例えば、ｄｘの最小値からスタートして出現頻度が１％に達する視差オフセット［ｄｘ＝ｘｌ−ｘｒ］のポイントに設定する。
これは、出現頻度が１％以下のデータは誤り（ｏｕｔｌｉｅｒ）である可能性が高いという前提に基づいている。
【００８９】
一方、閾値［ｔｈｉｎ］は、ｄｘの許容最大値［ｄｘ，ｍａｘ］を決定する閾値であり、例えば、ｄｘの最小値からスタートして出現頻度が１０％となるｘ方向の視差オフセット［ｄｘ＝ｘｌ−ｘｒ］のポイントに設定する。
これは、想定される最大の遊離点（Ｏｕｔｌｉｅｒ）出現頻度が１０％であるという前提に基づいている。この遊離点には視差が０の無限遠点も含む。
撮影画像に含まれる画素の多くの部分は、２つのカメラ間の視差に比較して十分に遠い位置にある被写体（Ｏｂｊｅｃｔ）の撮影画像であり、この場合これらの画素は無限遠点として仮定することができる。このような無限遠点の特徴点ペア（対応点）は、正しい視差データを算出する要素とはなり得ないデータであり、閾値［ｔｈｉｎ］は、これらのデータを排除する閾値である。
【００９０】
図１２に示す視差オフセット（ｄｘ，ｄｙ）の値［ｄｘ］のヒストグラム（頻度分布）において示すｄｘ,ｍａｘのポイントで、ヒストグラムの急激な立ち上がりが発生しているが、このような急激な立ち上がりは、無限遠点の被写体に対応するデータがカウントされていることを示している。このようなデータを排除するため、閾値［ｔｈｉｎ］に基づいて、ｄｘの許容最大値［ｄｘ，ｍａｘ］を決定する。
【００９１】
以上の処理により、図７に示すフローのステップＳ３０４において、視差オフセット・ヒストグラムに基づいて、新たな視差拘束（Ｄｉｓｐａｒｉｔｙ  ｃｏｎｘｔｒａｉｎｔ）の設定、すなわち、
視差オフセット（ｄｘ，ｄｙ）の各値［ｄｘ］、［ｄｙ］について、
ｄｘ：許容最小値［ｄｘ，ｍｉｎ］と許容最大値［ｄｘ，ｍａｘ］
ｄｙ：最適値［ｄｙ，ｂｅｓｔ］
これらの値が決定される。
【００９２】
これらの処理により、図２に示すフローのステップＳ１０４の処理、すなわち、視差オフセット算出のための第１段階処理として行われる視差拘束（Ｄｉｓｐａｒｉｔｙ  ｃｏｎｓｔｒａｉｎｔ）の算出処理が終了し、その後、ステップＳ１０５において、ステップＳ１０４で算出した視差拘束（Ｄｉｓｐａｒｉｔｙ  ｃｏｎｓｔｒａｉｎｔ）を適用して、視差オフセットの算出処理を実行する。この処理は、図１に示す視差オフセット算出部１０４において実行される。
【００９３】
ステップＳ１０５の視差オフセットの算出処理の詳細シーケンスについて、図１３に示すフローチャートを参照して説明する。
【００９４】
まず、ステップＳ３５１において、図７の処理フローの結果として設定したｘ方向の視差オフセットｄｘの許容最小値［ｄｘ，ｍｉｎ］と許容最大値［ｄｘ，ｍａｘ］間から、視差オフセット［ｄｘ］を選択する。図１３に示すフローでは、ｘ方向の視差オフセットｄｘの許容最小値［ｄｘ，ｍｉｎ］と許容最大値［ｄｘ，ｍａｘ］間で、例えば等間隔に一定数（ｎ個）の視差オフセット値ｄｘ１〜ｄｘｎを選択し、ステップＳ３５１〜３５３を実行する。
【００９５】
ステップＳ３５２では、ステップＳ３５１で選択した特徴点ペアのｘ方向の視差オフセット［ｄｘ］を適用した場合のエラーおよび遊離データ（Ｏｕｔｌｉｅｒ）の発生状況を検証する。この処理の詳細シーケンスについて、図１４のフローを参照して説明する。
【００９６】
まず、ステップＳ３８１において、ステレオフィルタを適用し、視差拘束等を満足しない特徴点ペアを削除する。この処理は、先に説明した図７のフローのステップＳ３０２において適用したステレオフィルタと同様のフィルタリング処理であり、
（ａ）エピポーラ拘束（Ｅｐｉｐｏｌａｒ  ｃｏｎｓｔｒａｉｎｔ）
ｄｙ，ｍｉｎ−δｙ＜ｙｌ−ｙｒ＜ｄｙ，ｍａｘ＋δｙ、
δｙは、予め設定されたエピポーララインの設定誤差である。
（ｂ）視差拘束（Ｄｉｓｐａｒｉｔｙ  ｃｏｎｓｔｒａｉｎｔ）
ｄｘ，ｍｉｎ＜ｘｌ−ｘｒ、
（ｃ）固有対応拘束（Ｕｎｉｑｕｅ  ｍａｔｃｈ  ｃｏｎｓｔｒａｉｎｔ）
上記（ａ），（ｂ）の両者を満足する複数のペア（１対多）がある場合、これらのペアは、あいまい性が高い特徴点ペアであると判定して排除、
これらの少なくともいずれかの判定処理を実行して、各拘束条件を満足するもののみを残存させる処理である。
【００９７】
ただし、このステップＳ３５２の処理では、
判定条件に適用する視差オフセット（ｄｘ，ｄｙ）のｄｙについての最小許容値と最大許容値：ｄ'ｙ，ｍｉｎ，ｄ'ｙ，ｍａｘを、図２のステップＳ１０４の処理で算出したｄｙ：最適値［ｄｙ，ｂｅｓｔ］とする。すなわち、
ｄ'ｙ，ｍｉｎ＝ｄ'ｙ，ｍｉｎ＝ｄｙ，ｂｅｓｔ
とする。
また、判定条件に適用する視差オフセット（ｄｘ，ｄｙ）のｄｘについての最小許容値と最大許容値：ｄ'ｘ，ｍｉｎ，ｄ'ｘ，ｍａｘについては、
最大許容値ｄ'ｘ，ｍａｘは、図２のステップＳ１０４の処理で算出した最大値［ｄｘ，ｍａｘ］として、一方、最小許容値ｄ'ｘ，ｍｉｎは、図１３のフローのステップＳ３５１で選択したｄｘとする。すなわち、
ｄ'ｘ，ｍｉｎ＝ｄｘ
とする。
【００９８】
この条件で、
（入力）
（１）特徴点ペア：（ｆｌ，ｆｒ）＝（ｘｌ，ｙｌ），（ｘｒ，ｙｒ）、
（２）視差オフセット（ｄｘ，ｄｙ）のｄｘ，ｄｙ各々についての最小許容値：ｄ'ｘ，ｍｉｎ，ｄ'ｙ，ｍｉｎと、最大許容値：ｄ'ｘ，ｍａｘ，ｄ'ｙ，ｍａｘ、
（判定処理）
（ｆｌ，ｆｒ）＝（ｘｌ，ｙｌ），（ｘｒ，ｙｒ）
が、
（ａ）エピポーラ拘束（Ｅｐｉｐｏｌａｒ  ｃｏｎｓｔｒａｉｎｔ）
ｄｙ，ｍｉｎ−δｙ＜ｙｌ−ｙｒ＜ｄｙ，ｍａｘ＋δｙ、
なお、δｙは、予め設定されたエピポーララインの設定誤差である。
（ｂ）視差拘束（Ｄｉｓｐａｒｉｔｙ  ｃｏｎｓｔｒａｉｎｔ）
ｄｘ，ｍｉｎ＜ｘｌ−ｘｒ、
（ｃ）固有対応拘束（Ｕｎｉｑｕｅ  ｍａｔｃｈ  ｃｏｎｓｔｒａｉｎｔ）
上記（ａ），（ｂ）の両者を満足する複数のペア（１対多）がある場合、これらのペアは、あいまい性が高い特徴点ペアであると判定して排除、
（出力）
上記（ａ）〜（ｃ）の拘束条件を全て満足する特徴点ペアのみを選択して出力する。
これらのステレオフィルタリング処理を実行する。
【００９９】
ここで選択された特徴点ペアのみを対象として、次のステップＳ３８２の処理を実行する。ステップＳ３８２では、処理対象とする検証画像とモデル画像データとの照合処理を実行し、検証画像に含まれる特徴点ペアからエラーおよび遊離（Ｏｕｔｌｉｅｒ）データ数を検証することである。モデル画像とは、信頼度の高い特徴点ペア情報を有するステレオ画像であり、例えば検証対象画像の1フレーム前のステレオ画像があげられる。
ステップＳ３８２の処理について図１５を参照して説明する。
【０１００】
図１５（Ｂ）は、検証対象画像とする第１カメラ画像（Ｌ）と、第２カメラ画像（Ｒ）を示している。これらの画像中に示す黒の矩形枠は、ステップＳ３８１のステレオフィルタリング処理において選択された信頼度の高い特徴点ペアである。
【０１０１】
図１５（Ａ）は、モデル画像であり、例えば検証対象画像の１フレーム前の先行画像が利用される。このモデル画像にも、検証画像と同様、第１カメラ画像（Ｌ）と、第２カメラ画像（Ｒ）の画像中にステレオフィルタリング処理において選択された信頼度の高い特徴点ペアを示している。
【０１０２】
ステップＳ３８２の処理の手順を述べる。まず、検証画像とモデル画像データとの照合処理により、両者に含まれない特徴点ペアを削除する。例えば検証対象画像とする第１カメラ画像（Ｌ）と、モデル画像の第１カメラ画像（Ｌ）を比較して、両者に共通に含まれない特徴点ペアのデータを検証画像から削除する。
【０１０３】
次に、検証対象画像とモデル画像両者に含まれる特徴点ペア情報を用いて、検証対象画像の特徴点ペアに含まれるエラーおよび遊離（Ｏｕｔｌｉｅｒ）データ数を検証する。この処理について説明する。
【０１０４】
モデル画像および検証画像のどちらか一方の画像、例えば第１カメラ画像（Ｌ）を用いて処理を行う。
モデル画像の第１カメラ画像（Ｌ）の特徴点の３次元位置の集合データを、
Ｐ＝｛ｐ１，ｐ２，・・・ｐｎ｝
検証画像の第１カメラ画像（Ｌ）の特徴点の３次元位置の集合データ集合を、
Ｑ＝｛ｑ１，ｑ２，・・・ｑｎ｝
とする。ｐ１〜ｐｎとｑ１〜ｑｎはそれぞれ３次元データにおける位置情報を有する。
【０１０５】
また、第１カメラ画像（Ｌ）を撮影したカメラのモデル画像と検証画像の撮影時における位置姿勢変化を、
ξ＝（Ｒ，Ｔ）
とする。
ただし、Ｒはカメラの姿勢変化情報であり、ｘ，ｙ，ｚ軸に対応するオイラー角、
Ｒ＝ｒｏｔ（α，ｚ）・ｒｏｔ（β，ｙ）・ｒｏｔ（γ，ｘ）
である。
また、Ｔは、カメラの３次元位置変化である並進ベクトルを示し、
Ｔ＝（ｔｘ，ｔｙ，ｙｚ）
である。
【０１０６】
ここで、モデル画像の第１カメラ画像（Ｌ）の特徴点集合、
Ｐ＝｛ｐ１，ｐ２，・・・ｐｎ｝
検証画像の第１カメラ画像（Ｌ）の特徴点集合を、
Ｑ＝｛ｑ１，ｑ２，・・・ｑｎ｝
これらのデータを適用して、ユークリッド距離（Ｅｕｃｌｉｄ  ｄｉｓｔａｎｃｅ）、
【数１】
2009048516.tif 000003
を算出する。
【０１０７】
モデル画像と検証画像から抽出した特徴点集合［Ｐ］、［Ｑ］に正しくないデータ、例えば遊離点やエラーが含まれる場合、上記のユークリッド距離は大きな値となり、遊離点やエラーが少ない場合には小さな値が算出される。
【０１０８】
なお、カメラの位置姿勢変化を、
ξ＝（Ｒ，Ｔ）
としているが、カメラの姿勢変化［Ｒ］が小さい場合は、
ｘ，ｙ，ｚ軸に対する回転角：α，β，γ≒０と仮定することが可能であり、この場合、
ｃｏｓ（α）≒１、
ｓｉｎ（α）≒α、
ｓｉｎ（α）ｓｉｎ（β）≒０
と近似することができる。以上の近似式を用いることで、カメラの姿勢変化［Ｒ］は以下のように近似することができる。
【数２】
2009048516.tif 000004
【０１０９】
ここでの処理は、検証対象画像の特徴点ペアに含まれるエラーデータまたは遊離点（Ｏｕｔｌｉｅｒ）データの数を検出することが目的である。まず、証対象画像の特徴点ペアに含まれる遊離点（Ｏｕｔｌｉｅｒ）の数は、以下のようにして求める。
【０１１０】
モデル画像の第１カメラ画像（Ｌ）の特徴点集合、
Ｐ＝｛ｐ１，ｐ２，・・・ｐｎ｝
検証画像の第１カメラ画像（Ｌ）の特徴点集合を、
Ｑ＝｛ｑ１，ｑ２，・・・ｑｎ｝
これらの検証対象画像の特徴点と、モデル画像における対応する特徴点データを利用してハフ変換（Ｈｏｕｇｈ  ｔｒａｎｓｆｏｒｍａｔｉｏｎ）を適用したヒストグラムフィルタリングにより、証対象画像の特徴点ペアに含まれる遊離点（Ｏｕｔｌｉｅｒ）を検出する。
【０１１１】
ハフ空間（Ｈｏｕｇｈ  ｓｐａｃｅ）はカメラの位置姿勢変化を定義するξ＝（Ｒ，Ｔ）を構成する６次元（α，β，γ，ｔｘ，ｔｙ，ｔｚ）である。
モデル画像の第１カメラ画像（Ｌ）の特徴点集合、
Ｐ＝｛ｐ１，ｐ２，・・・ｐｎ｝
検証画像の第１カメラ画像（Ｌ）の特徴点集合を、
Ｑ＝｛ｑ１，ｑ２，・・・ｑｎ｝
これらの対応する特徴点のペアの各々の組のデータによって、ハフドメインにおける４次元カーブが定義され、この４次元カーブを適用して上述のカメラの位置姿勢変化を定義するξ＝（Ｒ，Ｔ）を構成する６次元データ（α，β，γ，ｔｘ，ｔｙ，ｔｚ）を求めることができる。
【０１１２】
ここでは、β＝０，γ＝０，ｔｚ＝０として、３次元のハフ空間（α，ｔｘ，ｔｙ）とした実験データ例について、図１６、図１７を参照して説明する。
【０１１３】
図１６は、第１カメラ（Ｌ）のモデル画像の特徴点集合［Ｐ］と、検証画像の特徴点集合［Ｑ］の対応点によって生成した、回転角［α］のヒストグラムの例であり、図１７は、並進ベクトル［ｔｘ，ｔｙ］［ｔｘ，ｔｙ］のヒストグラムの例を示す図である。
【０１１４】
図１６（ａ）は、第１カメラ（Ｌ）のモデル画像であり、特徴点集合：Ｐ＝｛ｐ１，ｐ２，・・・ｐｎ｝が含まれる画像である。図１６（ｂ）は、第１カメラ（Ｌ）の検証画像であり、特徴点集合：Ｑ＝｛ｑ１，ｑ２，・・・ｑｎ｝が含まれる画像である。
【０１１５】
図１６（ｃ）は、図１６（ａ）のモデル画像と、図１６（ｂ）の検証画像のそれぞれの対応特徴点（ｐ１，ｑ１）〜（ｐｎ，ｑｎ）に基づいて算出されるｎ個の回転角（α）データの度数分布としてのヒストグラムである。このヒストグラムにおいて、ピーク位置を中心とした予め設定した閾値以内の領域をサポート領域（Ｓｕｐｐｏｒｔ  ｒｅｇｉｏｎ）とし、このサポート領域に含まれる回転角（α）を算出した特徴点を正しい特徴点とし、このサポート領域以外の回転角を算出した特徴点を遊離点（ｏｕｔｌｉｅｒ）とする。
【０１１６】
図１７は、並進ベクトル［ｔｘ，ｔｙ］のヒストグラムの例を示す図である。図１７（ａ）は、第１カメラ（Ｌ）のモデル画像であり、特徴点集合：Ｐ＝｛ｐ１，ｐ２，・・・ｐｎ｝が含まれる画像である。図１７（ｂ）は、第１カメラ（Ｌ）の検証画像であり、特徴点集合：Ｑ＝｛ｑ１，ｑ２，・・・ｑｎ｝が含まれる画像である。
【０１１７】
図１７（ｃ）は、図１７（ａ）のモデル画像と、図１７（ｂ）の検証画像のそれぞれの対応特徴点（ｐ１，ｑ１）〜（ｐｎ，ｑｎ）に基づいて算出されるｎ個の並進ベクトル［ｔｘ，ｔｙ］データの度数分布としてのヒストグラムである。このヒストグラムにおいて、ピーク位置を中心とした予め設定した閾値以内の領域をサポート領域（Ｓｕｐｐｏｒｔ  ｒｅｇｉｏｎ）とし、このサポート領域に含まれる並進ベクトル［ｔｘ，ｔｙ］を算出した特徴点を正しい特徴点とし、このサポート領域以外の並進ベクトル［ｔｘ，ｔｙ］を算出した特徴点を遊離点（ｏｕｔｌｉｅｒ）とする。
【０１１８】
このようにして、検証画像に含まれる特徴点［Ｑ＝｛ｑ１，ｑ２，・・・ｑｎ｝］から、遊離点（ｏｕｔｌｉｅｒ）を判別してその数をカウントする。このカウント数が遊離点数とされる。
【０１１９】
また、検証対象画像の特徴点ペアに含まれるエラーデータの数の算出には、前述のユークリッド距離（Ｅｕｃｌｉｄ  ｄｉｓｔａｎｃｅ）の算出式を用いる。
モデル画像の第１カメラ画像（Ｌ）の特徴点集合、
Ｐ＝｛ｐ１，ｐ２，・・・ｐｎ｝
検証画像の第１カメラ画像（Ｌ）の特徴点集合を、
Ｑ＝｛ｑ１，ｑ２，・・・ｑｎ｝
これらのデータを適用して、ユークリッド距離（Ｅｕｃｌｉｄ  ｄｉｓｔａｎｃｅ）、
【数３】
2009048516.tif 000005
を算出する。
【０１２０】
前述したように、モデル画像と検証画像から抽出した特徴点集合［Ｐ］、［Ｑ］に正しくないデータ、例えば遊離点やエラーが含まれる場合、上記のユークリッド距離は大きな値となり、遊離点やエラーが少ない場合には小さな値が算出される。そこで、エラー指標値を上記式の算出値とする。
【０１２１】
この処理によって、図１４に示すフローチャートのステップＳ３８２の処理が終了する。ステップＳ３８３では、ステップＳ３８２において求めた特徴点のエラー指標値および遊離点（Ｏｕｔｌｉｅｒ）データ数を、図１３に示すフローのステップＳ３５１で選択したｘ方向の視差オフセット［ｄｘ］に対応するエラー指標値および遊離点（Ｏｕｔｌｉｅｒ）データ数として設定する。
【０１２２】
この処理の後、図１３のフローのステップＳ３５３に進み、ステップＳ３５２において算出したエラー指標値および遊離点（Ｏｕｔｌｉｅｒ）のカウント数を、図１３に示すフローのステップＳ３５１で選択したｘ方向の視差オフセット［ｄｘ］に対応するエラー指標値および遊離点（Ｏｕｔｌｉｅｒ）数として記録する。
【０１２３】
次に、ステップＳ３５４に進み、未処理の［ｄｘ］データの有無を判定する。先にステップＳ３５１の処理の説明において説明したように、ステップＳ３５１〜Ｓ３５３の処理は、図７の処理フローの結果として設定したｘ方向の視差オフセットｄｘの許容最小値［ｄｘ，ｍｉｎ］と許容最大値［ｄｘ，ｍａｘ］間から、例えば等間隔に一定数（ｎ個）の視差オフセット値ｄｘ１〜ｄｘｎを検証対象データとして設定して、繰り返し実行する。
【０１２４】
ステップＳ３５４では、全ての検証対象データｄｘ１〜ｄｘｎについての検証が終了したか否かを判定する。終了していない場合は、未処理データについて、ステップＳ３５１〜Ｓ３５３の処理を実行する。すべての検証対象データについてステップＳ３５１〜Ｓ３５４の処理が終了すると、ステップＳ３５５に進む。
【０１２５】
ステップＳ３５５では、エラー、遊離データ（Ｏｕｔｌｉｅｒ）数が最小となる視差オフセット［ｄｘ］を、最適視差オフセット［ｄｘ，ｂｅｓｔ］として決定する。ステップＳ３５４の判定がＹｅｓとなる段階において、全ての検証対象データｄｘ１〜ｄｘｎに対応するエラー指標値および遊離点（Ｏｕｔｌｉｅｒ）の数が算出されている。すなわち、例えば、
ｄｘ１：エラー指標値＝Ｘａ、遊離データ（Ｏｕｔｌｉｅｒ）数＝Ｙａ個
ｄｘ２：エラー指標値＝Ｘｂ、遊離データ（Ｏｕｔｌｉｅｒ）数＝Ｙｂ個
ｄｘ３：エラー指標値＝Ｘｃ、遊離データ（Ｏｕｔｌｉｅｒ）数＝Ｙｃ個
：
ｄｘｎ：エラー指標値＝Ｘｐ、遊離データ（Ｏｕｔｌｉｅｒ）数＝Ｙｐ個
これらのデータが算出済みである。
【０１２６】
ステップＳ３５５では、これらの算出データから、エラー、遊離データ（Ｏｕｔｌｉｅｒ）数が最小となる視差オフセット［ｄｘ］を、最適視差オフセット［ｄｘ，ｂｅｓｔ］として決定する。この処理によって、ステップＳ３５５の処理が終了し、最適視差オフセット［ｄｘ，ｂｅｓｔ］が決定される。
【０１２７】
この処理によって、図２に示すフローのステップＳ１０５の処理が終了する。この結果、視差オフセット（ｄｘ，ｄｙ）のｘ方向、ｙ方向の最適値［ｄｘ，ｂｅｓｔ］，［ｄｙ，ｂｅｓｔ］が算出されたことになる。
【０１２８】
ステップＳ１０６では、この視差オフセットの最適値［ｄｘ，ｂｅｓｔ］，［ｄｙ，ｂｅｓｔ］を図１に示す２つのカメラ１０１ａ，１０１ｂの視差オフセットであるとして、カメラキャリブレーションおよび３次元マップ生成処理を実行する。
【０１２９】
先に、図６を参照して説明したように、異なる位置にほぼ平行に設置された２つのカメラによって撮影された画像を用いて視差オフセットを算出することができれば、カメラキャリブレーションが可能となり、３次元マップの生成が可能となる。すなわち、先に図６を参照して説明したように、視差オフセットは、２つの平行化画像の対応画素各々について算出され、対応画素各々のｘ方向のずれ（ｄｘ）とｙ方向のずれ（ｄｙ）との組データ（ｄｘ，ｄｙ）として表すことができるデータであり、視差オフセット（ｄｘ，ｄｙ）は、
第１画像の平面間変換行列：Ｈ１＝（ｔｘ１，ｔｙ１）
第２画像の平面間変換行列：Ｈ２＝（ｔｘ２，ｔｙ２）
第１画像の画像中心：（ｅｘ１，ｅｙ１）
第２画像の画像中心：（ｅｘ２，ｅｙ２）
と近似したとき、
視差オフセット（ｄｘ，ｄｙ）＝（ｅｘ１＋ｔｘ１−ｅｘ２−ｔｘ２，ｅｙ１＋ｔｙ１−ｅｙ２−ｔｙ２）
として表現できる。
【０１３０】
この視差オフセット（ｄｘ，ｄｙ）を算出できれば、例えば、第１画像の画像中心：（ｅｘ１，ｅｙ１）このデータを利用してカメラキャリブレーションが可能となる。すなわち、例えば一方のカメラ（第１カメラ）を固定して、第１画像の画像中心：（ｅｘ１，ｅｙ１）を平行化画像の中心（イメージ中心（Ｉｍａｇｅ  Ｃｅｎｔｅｒ））に設定（０，０）するような構成とすれば、他方のカメラ（第２カメラ）について、
（ａ）内部パラメータ
画像中心（ｐｒｉｎｃｉｐａｌ  ｐｏｉｎｔ）
（ｂ）外部パラメータ
カメラ位置姿勢（ｈｏｍｏｇｒａｐｈｉｅｓ）
これらのパラメータが未知である場合でも、第１カメラの撮影画像に基づく平行化画像である第１画像の画像中心データ：（ｅｘ１，ｅｙ１）を利用して、各カメラの撮影画像における対応点（特徴点ペア）について、視差オフセットを算出することが可能となり、カメラキャリブレーションが可能となる。
【０１３１】
本発明の構成では、図２に示すフローのステップＳ１０４において算出したｙ方向の視差オフセット最適値［ｄｙ，ｂｅｓｔ］と、ステップＳ１０５において算出したｘ方向の視差オフセット最適値［ｄｘ，ｂｅｓｔ］を適用してカメラキャリブレーションを実行し、３次元マップを生成する。
【０１３２】
上述した処理によれば、一方のカメラについてのパラメータの一部が不明である場合にも、各カメラの撮影画像に基づいて最適な視差オフセット（ｄｘ，ｄｙ）を算出することが可能となり、３次元マップを生成することができる。
【０１３３】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、特許請求の範囲の欄を参酌すべきである。
【０１３４】
また、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。例えば、プログラムは記録媒体に予め記録しておくことができる。記録媒体からコンピュータにインストールする他、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネットといったネットワークを介してプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることができる。
【０１３５】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【産業上の利用可能性】
【０１３６】
以上、説明したように、本発明の一実施例の構成によれば、異なる位置にほぼ平行に設置された２つのカメラによって撮影された画像を入力し、撮影画像に基づく視差オフセットの算出を実行する構成において、２つのカメラの撮影画像からペアを検出し、特徴点ペアの解析により２つのカメラの撮影画像における視差オフセットを算出する。視差オフセット算出処理においては、特徴点ペアのフィルタリングにより信頼度の高いと判断される特徴点ペアを選択し、選択した特徴点ペアに対応する視差オフセットデータの発生頻度分布情報としてのヒストグラムを生成し、生成したヒストグラムを利用して視差オフセットの許容値の拘束条件を規定し、規定した拘束条件に基づいて視差オフセットの最適値を算出する。本構成によれば、一方のカメラについてのパラメータの一部が不明である場合にも、各カメラの撮影画像に基づいて最適な視差オフセット（ｄｘ，ｄｙ）を算出可能となり、全てのパラメータが既知であるカメラを用いなくても３次元マップを生成することができる。
【図面の簡単な説明】
【０１３７】
【図１】本発明の一実施例の情報処理装置構成例を示す図である。
【図２】本発明の情報処理装置において実行する処理シーケンスについて説明するフローチャートを示す図である。
【図３】ハリスコーナー（Ｈａｒｒｉｓ  Ｃｏｒｎｅｒ）イメージを用いた特徴点抽出処理例について説明する図である。
【図４】特徴点マッチング処理のシーケンスについて説明するフローチャートを示す図である。
【図５】視差オフセットについて説明する図である。
【図６】視差オフセットについて説明する図である。
【図７】視差拘束（Ｄｉｓｐａｒｉｔｙ  ｃｏｎｓｔｒａｉｎｔ）の算出処理の詳細シーケンスについて説明するフローチャートを示す図である。
【図８】ステレオフィルタを適用したるフィルタリング処理の具体的な処理例について説明する図である。
【図９】ステレオフィルタを適用したるフィルタリング処理の具体的な処理例について説明する図である。
【図１０】ステレオフィルタを適用したるフィルタリング処理の具体的な処理例について説明する図である。
【図１１】ステレオフィルタの適用によって残された信頼性の高い特徴点ペアについての視差オフセット（ｄｘ，ｄｙ）の値［ｄｙ］のヒストグラム（頻度分布）を示す図である。
【図１２】ステレオフィルタの適用によって残された信頼性の高い特徴点ペアについての視差オフセット（ｄｘ，ｄｙ）の値［ｄｘ］のヒストグラム（頻度分布）を示す図である。
【図１３】視差オフセットの算出処理の詳細シーケンスについて説明するフローチャートを示す図である。
【図１４】特徴点ペアのｘ方向の視差オフセット［ｄｘ］を適用した場合のエラーおよび遊離データ（Ｏｕｔｌｉｅｒ）の発生状況を検証する処理シーケンスについて説明するフローチャートを示す図である。
【図１５】検証画像に含まれる特徴点ペアからエラーおよび遊離データ（Ｏｕｔｌｉｅｒ）と判断されるデータ数をカウントする処理について説明する図である。
【図１６】第１カメラ（Ｌ）のモデル画像の特徴点集合［Ｐ］と、検証画像の特徴点集合［Ｑ］の対応点によって生成した回転角［α］のヒストグラムの例を示す図である。
【図１７】第１カメラ（Ｌ）のモデル画像の特徴点集合［Ｐ］と、検証画像の特徴点集合［Ｑ］の対応点によって生成した、並進ベクトル［ｔｘ，ｔｙ］［ｔｘ，ｔｙ］のヒストグラムの例を示す図である。
【符号の説明】
【０１３８】
１０１  カメラ
１０２  特徴点抽出部
１０３  特徴点マッチング処理部
１０４  視差オフセット算出部
１０５  キャリブレーション＆３Ｄマップ生成部
２００  画像
２１０〜２１２  ハリスコーナーイメージ
２２０〜２２２  ラプラシアンイメージ
【図１】
2009048516.tif 000006
【図２】
2009048516.tif 000007
【図４】
2009048516.tif 000008
【図６】
2009048516.tif 000009
【図７】
2009048516.tif 000010
【図１１】
2009048516.tif 000011
【図１２】
2009048516.tif 000012
【図１３】
2009048516.tif 000013
【図１４】
2009048516.tif 000014
【図３】
2009048516.tif 000015
【図５】
2009048516.tif 000016
【図８】
2009048516.tif 000017
【図９】
2009048516.tif 000018
【図１０】
2009048516.tif 000019
【図１５】
2009048516.tif 000020
【図１６】
2009048516.tif 000021
【図１７】
2009048516.tif 000022