(57)【要約】【課題】特徴点の誤対応を減らすことで、被写体認識やカメラ姿勢推定の高精度化を図ることができる対応点探索装置およびカメラ姿勢推定装置ならびにこれらのプログラムを提供する。【解決手段】対応点探索装置１０は、局所特徴量算出手法を利用して複数の画像から特徴点を検出し、特徴ベクトルを算出する特徴点抽出手段１２と、複数の画像間において特徴ベクトルが類似する特徴点の組み合わせを対応点として探索する対応点探索手段１３と、対応点として探索された各特徴点を頂点としてドロネー三角形分割を行うドロネー三角形分割手段１４と、複数の画像間において対応点を頂点とする三角形同士を比較し、各三角形の頂点の連結関係が同じであるか否かを判定することで、各三角形の位相が同型か否かを評価するトポロジー評価手段１５と、位相が同じではないと評価された三角形の頂点を、対応点から除外する誤対応除外手段１６と、を備えている。【選択図】図１
2014127068.tif 000002
【特許請求の範囲】
【請求項１】
複数の画像間において対応点の探索を行う対応点探索装置であって、
局所特徴量算出手法を利用して前記複数の画像のそれぞれから特徴点を検出し、各特徴点の特徴ベクトルを算出する特徴点抽出手段と、
前記複数の画像間において、前記特徴ベクトルが類似する特徴点の組み合わせを対応点として探索する対応点探索手段と、
前記対応点探索手段によって対応点として探索された各特徴点を頂点として、前記複数の画像のそれぞれでドロネー三角形分割を行うドロネー三角形分割手段と、
前記複数の画像間において、前記対応点を頂点とする三角形同士を比較し、各三角形の頂点の連結関係が同じであるか否かを判定することで、前記各三角形の位相が同型か否かを評価するトポロジー評価手段と、
前記トポロジー評価手段によって前記位相が同じではないと評価された三角形の頂点を、前記対応点から除外する誤対応除外手段と、
を備えることを特徴とする対応点探索装置。
【請求項２】
複数の画像間において対応点の探索を行う対応点探索装置であって、
局所特徴量算出手法を利用して前記複数の画像のそれぞれから特徴点を検出し、各特徴点の特徴ベクトルを算出する特徴点抽出手段と、
前記複数の画像間において、前記特徴ベクトルが類似する特徴点の組み合わせを対応点として探索する対応点探索手段と、
前記対応点探索手段によって対応点として探索された各特徴点を頂点として、前記複数の画像のそれぞれでドロネー三角形分割を行うドロネー三角形分割手段と、
前記複数の画像間において、前記対応点を頂点とする三角形同士を比較し、各三角形の頂点の連結関係が同じであるか否かを判定することで、前記各三角形の位相が同型か否かを評価するトポロジー評価手段と、
前記トポロジー評価手段によって前記位相が同じではないと評価された割合が予め定められた閾値を超える三角形の頂点を、前記対応点から除外する誤対応除外手段と、
を備えることを特徴とする対応点探索装置。
【請求項３】
前記トポロジー評価手段は、前記複数の画像間において、前記対応点を頂点とする三角形同士の２辺を示すベクトルの外積をそれぞれ比較し、当該外積が一致する場合に前記位相が同じであると評価することを特徴とする請求項１または請求項２に記載の対応点探索装置。
【請求項４】
カメラ姿勢を推定するカメラ姿勢推定装置であって、
請求項１から請求項３のいずれか一項に記載の対応点探索装置と、
バンドルアジャストメントを利用して、前記対応点探索装置によって探索された対応点から各特徴点の３次元位置を算出し、各特徴点の３次元位置と、前記対応点とを用いて、カメラ姿勢を推定するカメラ姿勢推定手段と、
を備えることを特徴とするカメラ姿勢推定装置。
【請求項５】
コンピュータを、請求項１から請求項３のいずれか一項に記載の対応点探索装置として機能させるための対応点探索プログラム。
【請求項６】
コンピュータを、請求項４に記載のカメラ姿勢推定装置として機能させるためのカメラ姿勢推定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、同一の被写体を撮影した複数の画像間において対応点の探索を行う対応点探索装置、および複数の画像間の対応点からカメラ姿勢を推定するカメラ姿勢推定装置、ならびにこれらのプログラムに関する。
【背景技術】
【０００２】
一般的なコンピュータビジョンでは、画像の特徴点の位置と特徴量（具体的には特徴ベクトル）を取り出し、例えば別の画像上の特徴点の特徴量とを比較して類似する特徴点を対応点、つまり同じ被写体部位あるいは類似する絵柄の部位である可能性が高いと判断する。そして、この対応関係に基づいて統計的な画像処理を行うことで、被写体の認識やカメラ姿勢の推定を行う。例えば、特許文献１では、複数の画像から特徴点を抽出して局所特徴量を算出し、複数の画像のそれぞれの局所特徴量を互いに比較することで複数の画像間の対応点を探索する発明が提案されている。
【先行技術文献】
【非特許文献】
【０００３】
【特許文献１】特開２０１２−１０３７５８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、特許文献１で提案された発明は、統計的な処理を行うことで、ある程度の誤差や外れ値を含んだ状態であっても真値に近い推定を行えるものの、特徴点の誤対応の割合が増えると被写体の認識精度やカメラ姿勢の推定精度が低下してしまうという問題があった。
【０００５】
そこで、本発明はかかる点に鑑みてなされたものであって、特徴点の誤対応を減らすことで、被写体認識やカメラ姿勢推定の高精度化を図ることができる対応点探索装置およびカメラ姿勢推定装置ならびにこれらのプログラムを提供することを課題とする。
【課題を解決するための手段】
【０００６】
前記課題を解決するために請求項１に係る対応点探索装置は、複数の画像間において対応点の探索を行う対応点探索装置であって、特徴点抽出手段と、対応点探索手段と、ドロネー三角形分割手段と、トポロジー評価手段と、誤対応除外手段と、を備える構成とした。
【０００７】
このような構成を備える対応点探索装置は、特徴点抽出手段によって、局所特徴量算出手法を利用して複数の画像のそれぞれから特徴点を検出し、各特徴点の特徴ベクトルを算出する。また、対応点探索装置は、対応点探索手段によって、複数の画像間において、特徴ベクトルが類似する特徴点の組み合わせを対応点として探索する。そして、対応点探索装置は、ドロネー三角形分割手段によって、対応点探索手段によって対応点として探索された各特徴点を頂点として、複数の画像のそれぞれでドロネー三角形分割を行う。このように、対応点探索装置は、ドロネー三角形分割手段によってドロネー三角形分割を行うことで、複数の画像における各対応点の連結関係を作成することができる。
【０００８】
また、対応点探索装置は、トポロジー評価手段によって、複数の画像間において、対応点を頂点とする三角形同士を比較し、各三角形の頂点の連結関係が同じであるか否かを判定することで、各三角形の位相が同型か否かを評価する。このように、対応点探索装置は、トポロジー評価手段によって複数の画像間における三角形の頂点の連結関係を比較することで、これらの三角形が位相幾何学（トポロジー）的に同相（位相同型）であるか否かを評価し、誤対応の対応点を検出することができる。そして、対応点探索装置は、誤対応除外手段によって、トポロジー評価手段によって位相が同じではないと評価された三角形の頂点を、対応点から除外する。
【０００９】
前記課題を解決するために請求項２に係る対応点探索装置は、複数の画像間において対応点の探索を行う対応点探索装置であって、特徴点抽出手段と、対応点探索手段と、ドロネー三角形分割手段と、トポロジー評価手段と、誤対応除外手段と、を備える構成とした。
【００１０】
このような構成を備える対応点探索装置は、特徴点抽出手段によって、局所特徴量算出手法を利用して複数の画像のそれぞれから特徴点を検出し、各特徴点の特徴ベクトルを算出する。また、対応点探索装置は、対応点探索手段によって、複数の画像間において、特徴ベクトルが類似する特徴点の組み合わせを対応点として探索する。そして、対応点探索装置は、ドロネー三角形分割手段によって、対応点探索手段によって対応点として探索された各特徴点を頂点として、複数の画像のそれぞれでドロネー三角形分割を行う。このように、対応点探索装置は、ドロネー三角形分割手段によってドロネー三角形分割を行うことで、複数の画像における各対応点の連結関係を作成することができる。
【００１１】
また、対応点探索装置は、トポロジー評価手段によって、複数の画像間において、対応点を頂点とする三角形同士を比較し、各三角形の頂点の連結関係が同じであるか否かを判定することで、各三角形の位相が同型か否かを評価する。このように、対応点探索装置は、トポロジー評価手段によって複数の画像間における三角形の頂点の連結関係を比較することで、これらの三角形が位相幾何学（トポロジー）的に同相（位相同型）であるか否かを評価し、誤対応の対応点を検出することができる。そして、対応点探索装置は、誤対応除外手段によって、トポロジー評価手段によって位相が同じではないと評価された割合が予め定められた閾値を超える三角形の頂点を、対応点から除外する。これにより、対応点探索装置は、誤対応の判定（すなわち位相が同じではないという評価）がなされた三角形の頂点を対応点から漏れなく除外するのではなく、誤対応の判定が一定程度を超えた三角形の頂点のみを対応点から除外することができる。
【００１２】
また、請求項３に係る対応点探索装置は、請求項１または請求項２に係る対応点探索装置において、トポロジー評価手段が、複数の画像間において、対応点を頂点とする三角形同士の２辺を示すベクトルの外積をそれぞれ比較し、当該外積が一致する場合に位相が同じであると評価する構成とした。すなわち、対応点探索装置は、ドロネー三角形分割された三角形の２辺を示すベクトルの外積を基準として、複数の画像間における三角形の位相が位相幾何学的に同型であるか否かを評価する。
【００１３】
前記課題を解決するために請求項４に係るカメラ姿勢推定装置は、カメラ姿勢を推定するカメラ姿勢推定装置であって、請求項１から請求項３のいずれか一項に記載の対応点探索装置と、カメラ姿勢推定手段と、を備える構成とした。
【００１４】
このような構成を備えるカメラ姿勢推定装置は、カメラ姿勢推定手段によって、バンドルアジャストメントを利用して、対応点探索装置によって探索された対応点から各特徴点の３次元位置を算出し、各特徴点の３次元位置と、対応点とを用いて、カメラ姿勢を推定する。これにより、対応点探索装置は、誤対応除外手段によって誤対応の対応点が予め除外された対応点に関する情報を利用してカメラ姿勢を推定することができる。
【００１５】
前記課題を解決するために請求項５に係る対応点探索プログラムは、コンピュータを、請求項１から請求項３のいずれか一項に記載の対応点探索装置として機能させることとした。
【００１６】
前記課題を解決するために請求項６に係るカメラ姿勢推定プログラムは、コンピュータを、請求項４に記載のカメラ姿勢推定装置として機能させることとした。
【発明の効果】
【００１７】
請求項１および請求項５に係る発明によれば、カメラ位置が変化しても特徴点の連結関係は保存されるという性質を利用して、予め探索された複数の画像間の対応点について、ドロネー三角形分割を利用した三角形の位相の評価を行い、対応点の数を絞っている。そのため、請求項１および請求項５に係る発明によれば、誤対応の対応点を減らし、後段の処理である被写体認識やカメラ姿勢推定の高精度化を図ることができる。
【００１８】
請求項２に係る発明によれば、誤対応の可能性が高い対応点のみを予め探索された対応点から除外するため、誤対応の対応点が増加するような、認識精度の低い局所特徴量算出手法によって特徴点が抽出された場合や、抽出された特徴点の数がもともと少ない場合であっても、対応点の数が極端に少なくなることがない。
【００１９】
請求項３に係る発明によれば、複数の画像間における誤対応の対応点を、三角形の２辺を示すベクトルの外積の比較という方法を利用して簡便に検出することができる。
【００２０】
請求項４および請求項６に係る発明によれば、カメラ位置が変化しても特徴点の連結関係は保存されるという性質を利用して、予め探索された複数の画像間の対応点について、ドロネー三角形分割を利用した三角形の位相の評価を行い、対応点の数を絞っている。そのため、請求項４および請求項６に係る発明によれば、誤対応の対応点を減らすことができるため、カメラ姿勢推定の高精度化を図ることができる。また、請求項４および請求項６に係る発明によれば、誤対応の対応点が予め除外された状態でカメラ姿勢を推定するため、処理時間を減らすことができる。
【図面の簡単な説明】
【００２１】
【図１】本発明の実施形態に係る対応点探索装置およびカメラ姿勢推定装置の全体構成を示すブロック図である。
【図２】本発明の実施形態に係る対応点探索装置のトポロジー評価手段における処理を説明するための概略図である。
【図３】本発明の実施形態に係る対応点探索装置による処理の一例を示す概略図である。
【図４】本発明の実施形態に係る対応点探索装置およびカメラ姿勢推定装置の動作（処理手順）を示すフローチャートである。
【発明を実施するための形態】
【００２２】
以下、本発明の実施形態に係る対応点探索装置およびカメラ姿勢推定装置ならびにこれらのプログラムについて、図面を参照しながら説明する。以下では、まず対応点探索装置の説明を行った後、カメラ姿勢推定装置、対応点探索プログラムおよびカメラ姿勢推定プログラムの説明を行うこととする。また以下では、同一もしくは同質の構成は同一の名称および符号によって示すこととし、詳細説明を適宜省略する。
【００２３】
ここで、複数の画像からそれぞれ特徴点を抽出し、画像間の特徴点の対応関係を求める際に、オクルージョン領域（被写体が重なって見えない領域）や、類似した特徴量を持つ特徴点の存在により、対応関係に誤り（誤対応）が含まれる場合がある。このような誤対応は、画像特徴の対応関係を用いるカメラ姿勢推定などの認識技術に誤差をもたらすことになる。
【００２４】
そこで、本発明は前記したような問題を解決するために、複数の画像上の被写体をそれぞれカメラに対して正対する平面とみなす。そして、カメラ姿勢が変わった場合に、誤対応のない領域では、各被写体の特徴点の連結関係がそのまま保存され、前記したオクルージョン領域や精度が不十分や特徴量が原因で誤対応が生じた領域では、前記した連結関係が保存されない、という性質を利用して誤対応を除去する。なお、前記したオクルージョン領域は、被写体領域境界付近で見え隠れする領域であるため、この領域およびその周辺領域における特徴点の連結関係は保存されない、あるいは保存されにくいという性質がある。
【００２５】
［対応点探索装置の構成］
以下、実施形態に係る対応点探索装置１０の構成について、図１および図２を参照しながら説明する。
【００２６】
対応点探索装置１０は、同一の被写体を撮影した複数の画像間において対応点を探索するものである。ここで、前記した「複数の画像」とは、例えば１つの映像中における、ある時点のフレーム（以下、基準画像という）と、そのフレームよりも時系列的に前または後に存在するフレーム画像（以下、対応点探索画像という）のことを示している。また、前記した「対応点」とは、複数の画像間において同じまたは類似する特徴を示す点（画素）の組み合わせのことを示している。以下の説明では、対応点探索装置１０が、映像中におけるある時点の基準画像と、当該基準画像よりも時系列的に後の対応点探索画像との間の対応点を探索することを前提に説明を行う。また、以下の説明では、カメラモデルを弱中心射影と仮定し、画像上の被写体を、被写体ごとにカメラＣａに正対した平面とみなす。
【００２７】
対応点探索装置１０は、図１に示すように、カメラＣａから入力された複数の画像から対応点を探索し、当該対応点に関する情報（特徴点の位置と対応関係）をカメラ姿勢推定手段２０に対して出力する。この対応点探索装置１０は、ここでは図１に示すように、画像蓄積手段１１と、特徴点抽出手段１２と、対応点探索手段１３と、ドロネー三角形分割手段１４と、トポロジー評価手段１５と、誤対応除外手段１６と、特徴点対応情報蓄積手段１７とを備えている。なお、対応点探索装置１０は、カメラＣａを除き、一般的なパソコン程度のハードウェア規模で実現可能である。以下、対応点探索装置１０の各構成について説明する。
【００２８】
画像蓄積手段１１は、カメラＣａによって撮影された画像を蓄積するものである。画像蓄積手段１１は、図１に示すように、カメラＣａから時系列に沿って入力される画像を蓄積する。そして、画像蓄積手段１１は、特徴点抽出手段１２の求めに応じて、複数の画像を出力する。ここで、画像蓄積手段１１は、具体的にはデータを記憶することができるメモリ、ハードディスクなどで構成される。また、画像蓄積手段１１は、ここでは対応点探索装置１０の内部に設けられているが、外部に設けられていても構わない。
【００２９】
特徴点抽出手段１２は、複数の画像から特徴点を抽出するものである。特徴点抽出手段１２は、具体的にはＳＩＦＴ（Scale Invariant Feature Transform）やＳＵＲＦ（Speeded Up Robust Feature）といった局所特徴量算出手法を利用して、画像蓄積手段１１から入力された複数の画像のそれぞれから特徴点の位置を検出するとともに、検出した各特徴点の特徴量、すなわち特徴ベクトルを算出する。そして、特徴点抽出手段１２は、図１に示すように、特徴点の位置およびその特徴ベクトルを対応点探索手段１３に対して出力する。
【００３０】
ここで、特徴点抽出手段１２は、局所特徴量算出手法として前記したＳＩＦＴおよびＳＵＲＦのいずれの手法も利用することができるが、ここではＳＵＲＦよりも認識精度に優れたＳＩＦＴを利用している。この場合、特徴点抽出手段１２は、例えば（１）特徴点の検出処理、（２）オリエンテーションの算出処理、（３）特徴ベクトルの算出処理、を行うことで複数の画像から特徴点を抽出する。以下、これらの処理を簡単に説明する。
【００３１】
（１）特徴点の検出処理
特徴点の検出処理では、特徴点抽出手段１２が、複数の画像のそれぞれについてＤｏＧ（Difference of Gaussian）フィルタを用いてスケール情報と特徴点の候補点を検出し、検出された候補点の中からＤｏＧ出力の小さい点とエッジ上の点を削除する。
【００３２】
（２）オリエンテーションの算出処理
オリエンテーションの算出処理では、特徴点抽出手段１２が、複数の画像のそれぞれで検出された特徴点についてその周辺領域を８×８の小領域に分割し、各小領域の輝度勾配方向を算出する。そして、特徴点抽出手段１２は、特徴点ごとに輝度勾配方向を３６ビンのヒストグラムで表現し、そのピーク（最高値）を特徴点のオリエンテーションとして決定する。
【００３３】
（３）特徴ベクトルの算出
特徴ベクトルの算出では、特徴点抽出手段１２が、複数の画像のそれぞれで検出された特徴点について予め設定された基準角度（例えば水平を示す０°）を基準として、決定されたオリエンテーションだけ、予め設定された回転方向（例えば右回り）に回転させる。そして、特徴点抽出手段１２は、回転後の各特徴点の周辺領域を４×４の合計１６ブロックに分割し、ブロックごとに輝度勾配を８方向に量子化することで、合計１２８次元の特徴ベクトルを算出する。
【００３４】
なお、前記したＳＩＦＴによる（１）〜（３）の処理は、例えば「藤吉他, “Gradientベースの特徴抽出-SIFTとHOG-”, 2007, 情報処理学会研究報告, CVIM 160, pp.211-224」に詳細に記載されている。
【００３５】
対応点探索手段１３は、複数の画像間における対応点を探索するものである。対応点探索手段１３は、複数の画像間において、特徴ベクトルが同じまたは類似する特徴点の組み合わせを対応点として探索する。そして、対応点探索手段１３は、図１に示すように、この対応点の情報、すなわち複数の画像間で対応している特徴点のそれぞれの座標および対応関係に関する情報（以下、特徴点対応情報という）をドロネー三角形分割手段１４に対して出力する。
【００３６】
ここで、対応点探索手段１３における対応点探索の具体的方法は特に限定されないが、対応点探索手段１３は、例えば以下のような方法を利用して複数の画像、すなわち基準画像および対応点探索画像から対応点を探索することができる。
【００３７】
対応点探索手段１３は、基準画像における各特徴点の特徴ベクトルと、対応点探索画像における各特徴点の特徴ベクトルとの各次元の差の総和をユークリッド距離として算出する。次に、対応点探索手段１３は、基準画像における特徴点Ｐｓ１を基準として、対応点探索画像においてユークリッド距離が最も近い特徴点Ｐｃ１と、２番目に近い特徴点Ｐｃ２とを探索する。そして、対応点探索手段１３は、以下の式（１）に示すように、特徴点Ｐｓ１および特徴点Ｐｃ１のユークリッド距離Ｄ１と、特徴点Ｐｓ１および特徴点Ｐｃ２のユークリッド距離Ｄ２との比が、予め定められた閾値を超える場合に、基準画像の特徴点Ｐｓ１と対応点探索画像の特徴点Ｐｃ１を対応点として探索する。なお、以下の式（１）における閾値は、実験的および経験的に導出される。また、前記した符号Ｐｓ１，Ｐｃ１，Ｐｃ２は、説明用の符号であり、図示は省略している。
【００３８】
（Ｄ１／Ｄ２）＞閾値  ・・・式（１）
【００３９】
ドロネー三角形分割手段１４は、複数の画像をドロネー三角形（以下、三角形という）に分割するものである。ここで、「ドロネー三角形分割」とは、空間内の点を連結して三角形の集まりに分割する幾何学的なアルゴリズムのことを示している。このドロネー三角形分割では、可能な限り細長い三角形にならないように、各三角形の角の最小値が最大となるように、どの三角形の外接円も他の点を内部に含まないように各点を連結していく。なお、ドロネー三角形分割はどのような手法を用いても構わないが、例えば『杉原厚吉著、「グラフィックスの数理」、共立出版、1995年1月、pp.177-184』に記載された手法を用いることができる。
【００４０】
ドロネー三角形分割手段１４は、図２（ａ）、（ｂ）に示すように、複数の画像、すなわち基準画像および対応点探索画像のそれぞれにおいて、対応点として探索された各特徴点を頂点として、当該頂点同士を線分で連結することでドロネー三角形分割を行い、複数の三角形の集合を構築する。なお、図２（ａ）、（ｂ）において、三角形の頂点を構成する円形部分は、対応点として探索された特徴点を示している。そして、ドロネー三角形分割手段１４は、図１に示すように、各三角形の頂点（特徴点）の連結関係に関する情報（以下、特徴点連結情報という）を、前記した特徴点対応情報とともにトポロジー評価手段１５に対して出力する。
【００４１】
トポロジー評価手段１５は、ドロネー三角形分割によって分割された三角形の位相幾何学（トポロジー）的な位相を評価するものである。トポロジー評価手段１５は、複数の画像間において対応関係にある三角形同士を比較し、各三角形の頂点の連結関係が同じであるか否かを判定することで、各三角形の位相が同型か否かを評価する。なお、前記した「対応関係にある三角形」とは、複数の画像間において、各頂点がそれぞれ対応点として探索された三角形のことを示している。そして、トポロジー評価手段１５は、図１に示すように、三角形の連結関係が同じであるかの判定結果（すなわち三角形の位相が位相幾何学的に同型であるか否かの評価結果）を、前記した特徴点対応情報とともに誤対応除外手段１６に対して出力する。
【００４２】
以下、トポロジー評価手段１５における処理の一例について、図２を参照しながら説明する。以下では、図２（ａ）、（ｂ）に示すように、特徴点抽出手段１２によって基準画像および対応点探索画像からそれぞれ９個の特徴点Ｐが抽出され、対応点探索手段１３によって図２（ａ）、（ｂ）の破線矢印で示すような各特徴点間の対応関係が探索された場合について説明する。
【００４３】
この場合、トポロジー評価手段１５は、図２（ａ）の基準画像の全て（ここでは合計８個）の三角形と、図２（ｂ）の対応点探索画像の全て（ここでは合計８個）の三角形とを比較する。例えば、トポロジー評価手段１５は、基準画像の特徴点Ａ，Ｂ，Ｃを頂点とする三角形Ｔ１と、対応点探索画像の特徴点Ａ，Ｂ，Ｃを頂点とする三角形Ｔ２とに注目した場合、以下のような処理を行う。なお、三角形Ｔ１と三角形Ｔ２とは、それぞれの頂点（特徴点Ａ，Ｂ，Ｃ）が対応点として探索された、対応関係にある三角形である。
【００４４】
この場合、トポロジー評価手段１５は、基準画像の三角形Ｔ１の頂点を、例えば特徴点Ａから左回りに選択し、特徴点Ａ，Ｂ，Ｃが配置されている順番を確認する。次に、トポロジー評価手段１５は、対応点探索画像の三角形Ｔ２の頂点についても、三角形Ｔ１と同様に特徴点Ａから左回りに選択し、特徴点Ａ，Ｂ，Ｃが配置されている順番を確認する。そして、トポロジー評価手段１５は、三角形Ｔ１，Ｔ２間で対応する特徴点Ａ，Ｂ，Ｃが同じ順番で配置されている場合は位相が同じであると評価し、異なる順番であれば位相が同じではないと評価する。
【００４５】
ここで、基準画像の三角形Ｔ１は、図２（ａ）に示すように左回りに特徴点Ａ，Ｂ，Ｃの順に配置され、対応点探索画像の三角形Ｔ２は、図２（ｂ）に示すように左回りに特徴点Ａ，Ｃ，Ｂの順に配置されている。そのため、トポロジー評価手段１５は、三角形Ｔ１，Ｔ２の位相が同じではないと評価し、その評価結果を誤対応除外手段１６に対して出力する。
【００４６】
ここで、トポロジー評価手段１５は、前記したように、基準画像および対応点探索画像の中で対応する三角形の頂点の順番を判定することで位相を評価しているが、例えば各三角形の２辺を示すベクトルの外積を基準として、複数の画像間における三角形の位相が位相幾何学的に同型であるか否かを評価してもよい。
【００４７】
この場合、トポロジー評価手段１５は、基準画像の三角形Ｔ１の２辺のベクトルの外積と、対応点探索画像の三角形Ｔ２の２辺のベクトルの外積をそれぞれ算出して比較し、当該外積が一致する場合は三角形Ｔ１，Ｔ２の位相が同じであると評価し、外積が一致しない場合は三角形Ｔ１，Ｔ２の位相が同じではないと評価する。なお、各三角形の外積は、例えば特徴点Ａ，Ｂを結んだベクトルＡＢと、特徴点Ｂ，Ｃを結んだベクトルＢＣの外積を求めればよい。このように、トポロジー評価手段１５は、複数の画像間における誤対応の対応点を、三角形の２辺を示すベクトルの外積の比較という方法を利用して簡便に検出することができる。
【００４８】
誤対応除外手段１６は、誤対応の対応点を除外するものである。誤対応除外手段１６は、前記した特徴点対応情報に含まれる対応点（特徴点）の中から、トポロジー評価手段１５によって位相が同じではないと評価された三角形の頂点（特徴点）を除外する。そして、誤対応除外手段１６は、図１に示すように、誤対応が除外された対応点に関する情報（以下、誤対応除外済特徴点対応情報という）を特徴点対応情報蓄積手段１７に対して出力する。
【００４９】
例えば、誤対応除外手段１６は、図２（ａ）、（ｂ）に示すように、基準画像の三角形Ｔ１と、対応点探索画像の三角形Ｔ２の位相とが同じではない場合、トポロジー評価手段１５から入力された「三角形Ｔ１，Ｔ２の位相が同じではない」という評価結果を受けて、対応点探索手段１３によって対応点として探索された９個の特徴点の中から、特徴点Ａ，Ｂ，Ｃを除外する。そして、誤対応除外手段１６は、残り６個の対応点（特徴点）の連結関係に関する情報が含まれる誤対応除外済特徴点対応情報を特徴点対応情報蓄積手段１７に対して出力する。
【００５０】
ここで、誤対応除外手段１６は、前記したように、トポロジー評価手段１５によって位相が同じではないと評価された三角形の頂点（特徴点）を対応点から漏れなく除外しているが、例えば前記した特徴点抽出手段１２において用いられる局所特徴量算出手法に応じて、別の基準で除外してもよい。
【００５１】
例えば、前記したようにＳＵＲＦはＳＩＦＴよりも認識精度が低いため、局所特徴量算出手法としてＳＵＲＦを利用して特徴点を抽出すると、トポロジー評価手段１５によって位相が同じではない、すなわち誤対応であると評価される特徴点の数が増える傾向がある。そのため、誤対応除外手段１６によって、位相が同じではないと評価された三角形の頂点（特徴点）を対応点から漏れなく除外すると、最終的に得られる対応点の数が少なくなりすぎる場合がある。
【００５２】
そこで、誤対応除外手段１６は、特徴点抽出手段１２において、例えば認識精度の低い局所特徴量算出手法を用いて特徴点が抽出された場合や、抽出された特徴点の数がもともと少ない場合は、前記した特徴点対応情報に含まれる対応点の中から、トポロジー評価手段１５によって位相が同じではないと評価された割合が予め定められた閾値を超える三角形の頂点（特徴点）を除外することが好ましい。
【００５３】
例えば、図２（ａ）、（ｂ）における特徴点Ｃは、特徴点Ａ，Ｂとの間で三角形を構成する他にも、５個の三角形の頂点を構成している。すなわち、特徴点Ｃは、６個の三角形に共有されている。この場合、誤対応除外手段１６は、特徴点Ｃについて、当該特徴点Ｃが属する６個の三角形に関する位相の評価（すなわちトポロジー評価手段１５による位相の評価）の中から、位相が同じでないと評価された回数（以下、ペナルティ数）をカウントする。そして、誤対応除外手段１６は、以下の式（２）および式（３）に示すように、特徴点Ｃペナルティ数を、特徴点Ｃによる三角形の共有数（ここでは「６」）で除算した評価値が、予め定められた閾値を超える場合に、対応点探索手段１３によって対応点として探索された９個の特徴点の中から、特徴点Ｃを除外する。なお、以下の式（３）における閾値は、実験的および経験的に導出される。
【００５４】
評価値＝ペナルティ数／共有数  ・・・式（２）
評価値＞閾値  ・・・式（３）
【００５５】
このような処理により、対応点探索装置１０は、誤対応の判定（すなわち位相が同じではないという評価）がなされた三角形の頂点を対応点から漏れなく除外するのではなく、誤対応の判定が一定程度を超えた三角形の頂点のみを対応点から除外することができる。これにより、対応点探索装置１０は、誤対応の可能性が高い対応点のみを予め探索された対応点から除外するため、誤対応の対応点が増加するような、認識精度の低い局所特徴量算出手法によって特徴点が抽出された場合や、抽出された特徴点の数がもともと少ない場合であっても、対応点の数が極端に少なくなることがない。
【００５６】
特徴点対応情報蓄積手段１７は、各特徴点の対応情報を蓄積するものである。特徴点対応情報蓄積手段１７は、図１に示すように、誤対応除外手段１６から入力される、対応点の座標と、対応関係に関する情報とを蓄積する。そして、特徴点対応情報蓄積手段１７は、後記するカメラ姿勢推定装置１のカメラ姿勢推定手段２０の求めに応じて、対応点の座標および対応関係に関する情報を出力する。ここで、特徴点対応情報蓄積手段１７は、具体的にはデータを記憶することができるメモリ、ハードディスクなどで構成される。また、特徴点対応情報蓄積手段１７は、ここでは対応点探索装置１０の内部に設けられているが、外部に設けられていても構わない。
【００５７】
以上のような構成を備える対応点探索装置１０は、ドロネー三角形分割手段１４によってドロネー三角形分割を行うことで、複数の画像における各対応点の連結関係を作成することができる。また、対応点探索装置１０は、トポロジー評価手段１５によって複数の画像間における三角形の頂点の連結関係を比較することで、これらの三角形が位相幾何学（トポロジー）的に同相（位相同型）であるか否かを評価し、誤対応の対応点を検出することができる。
【００５８】
従って、対応点探索装置１０によれば、カメラ位置が変化しても特徴点の連結関係は保存されるという性質を利用して、予め探索された複数の画像間の対応点について、ドロネー三角形分割を利用した三角形の位相の評価を行い、対応点の数を絞っている。そのため、対応点探索装置１０によれば、誤対応の対応点を減らすことができ、後段の処理である被写体認識やカメラ姿勢推定の高精度化を図ることができる。
【００５９】
なお、対応点探索装置１０によれば、誤対応の対応点が減るため、カメラ姿勢の推定では推定精度が向上するほか、推定の破綻が生じにくくなる。また、対応点探索装置１０を利用することで、画像認識において特徴点の対応関係を利用する手法全般において認識精度の向上が期待できる。
【００６０】
その他にも、例えば従来手法ではオクルージョン領域の検出には画像のスキャンライン上で相関を取って判定していた。しかし、コンピュータビジョンでは繰り返し処理を行うことが多いため、前記したような従来手法では画像の読み込みや判定の際に処理装置に対して高い負荷がかかるとともに、長い処理時間が要求されることになる。一方、対応点探索装置１０によれば、特徴点対応情報から誤対応の判定を行うため、処理装置に対する負荷や処理時間が従来手法ほど問題にはならなくなる。さらに、誤対応の対応点が多く含まれていると、カメラ姿勢の推定における統計処理で処理装置に対して負荷がかかるが、対応点探索装置１０は、カメラ姿勢の推定を行う前に誤対応を除去可能であるため、前記した統計処理時の負担が低減されることになる。
【００６１】
［対応点探索装置による処理の一例］
以下、対応点探索装置１０による処理の一例について、図３を参照しながら説明する。ここでは、図３（ａ）に示すように、ある映像中から１８５フレームと２５９フレームをそれぞれ取り出し、特徴点抽出手段１２による特徴点の抽出、対応点探索手段１３による対応点の探索、ドロネー三角形分割手段１４によるドロネー三角形分割、トポロジー評価手段１５による三角形の位相の評価を行った。その結果、図３（ｂ）における黒丸に示すように、主に同じ絵柄が交互に連続する被写体上（例えばチェッカー模様の被写体上）に誤対応が多く発見された。なお、図３（ｂ）において符号Ｐで示す三角形の頂点は、特徴点抽出手段１２によって抽出され、対応点探索手段１３によって対応点として探索された特徴点を示している。また、図３（ｂ）において符号Ｐｘで示す黒丸は、誤対応の対応点を示している。のように、対応点探索装置１０によれば、後段の処理である被写体認識やカメラ姿勢推定の前に予め誤対応の対応点を検出し、除外することが可能である。
【００６２】
［カメラ姿勢推定装置の構成］
以下、実施形態に係るカメラ姿勢推定装置１の構成について、図１を参照しながら説明する。
【００６３】
カメラ姿勢推定装置１は、カメラＣａのカメラ姿勢（カメラパラメータ）を推定するものである。このカメラ姿勢としては、例えばカメラＣａの位置または姿勢などの外部パラメータと、光学中心またはレンズ歪などの内部パラメータとが挙げられる。カメラ姿勢推定装置１は、ここでは図１に示すように、対応点探索装置１０と、カメラ姿勢推定手段２０とを備えている。なお、対応点探索装置１０の構成については既に説明済みであるため、以下ではそれ以外の構成について説明する。
【００６４】
カメラ姿勢推定手段２０は、対応点探索装置１０の特徴点対応情報蓄積手段１７から入力された対応点の情報を利用して、カメラ姿勢を推定するものである。カメラ姿勢推定手段２０は、具体的には、最適化の一手段であるバンドルアジャストメント（Bundle Adjustment：バンドル調整処理）によって、カメラ姿勢係数を未知数として最適化を行い、カメラ姿勢を推定する。すなわち、カメラ姿勢推定手段２０は、前記したバンドルアジャストメントによって、各撮影画像のカメラ位置情報と、各カメラ位置において撮影された画像に含まれる対応する特徴点、すなわち対応点の情報を利用して、特徴点の最も確からしい３次元位置を算出する。
【００６５】
そして、カメラ姿勢推定手段２０は、対応点に外れ値と呼ばれる誤対応点が含まれる場合があるため、ＲＡＮＳＡＣ、ＬＭｅｄＳなどのロバスト推定により外れ値を除外し、最適化によりカメラ姿勢を推定する。その際、カメラ姿勢推定手段２０は、最適化の評価関数として、仮定したカメラ姿勢で特徴点の３次元位置を画像に投影した座標と、対応点の座標との距離差の総和を用いることができる。この場合、カメラ姿勢推定手段２０は、最適化の評価関数の計算値が最小となるカメラ姿勢を繰り返し処理で推定し、図１に示すように、推定したカメラ姿勢を外部に出力する。なお、カメラ姿勢推定手段２０において利用されるバンドルアジャストメントは、例えば、ホームページ「http://phototour.cs.washington.edu/bundler/」に詳細に記載されている。
【００６６】
以上のような構成を備えるカメラ姿勢推定装置１によれば、カメラ位置が変化しても特徴点の連結関係は保存されるという性質を利用して、予め探索された複数の画像間の対応点について、ドロネー三角形分割を利用した三角形の位相の評価を行い、対応点の数を絞っている。そのため、カメラ姿勢推定装置１によれば、誤対応の対応点を減らすことができるため、カメラ姿勢推定の高精度化を図ることができる。また、カメラ姿勢推定装置１によれば、誤対応の対応点が予め除外された状態でカメラ姿勢を推定するため、処理時間を減らすことができる。
【００６７】
［対応点探索装置およびカメラ姿勢推定装置の動作］
以下、実施形態に係る対応点探索装置１０およびカメラ姿勢推定装置１の動作について、図４を参照（適宜図１を参照）しながら説明する。なお、以下では、まず対応点探索装置１０の動作を説明した後に、カメラ姿勢推定装置１の動作を補足的に説明することとする。
【００６８】
まず、対応点探索装置１０は、画像蓄積手段１１によって、カメラＣａから入力された複数の画像を蓄積する（ステップＳ１）。次に、対応点探索装置１０は、特徴点抽出手段１２によって、ＳＩＦＴなどの局所特徴量算出手法により、画像蓄積手段１１から入力された複数の画像（基準画像および対応点探索画像）の特徴点をそれぞれ検出して特徴ベクトルを算出する（ステップＳ２）。次に、対応点探索装置１０は、対応点探索手段１３によって、複数の画像間において、特徴ベクトルが類似する特徴点の組み合わせを対応点として探索する（ステップＳ３）。
【００６９】
次に、対応点探索装置１０は、ドロネー三角形分割手段１４によって、複数の画像の特徴点を連結して三角形に分割する（ステップＳ４）。次に、対応点探索装置１０は、トポロジー評価手段１５によって、複数の画像間において対応する三角形の位相を評価、すなわち三角形の頂点の連結関係を判定する（ステップＳ５）。そして、対応点探索装置１０は、トポロジー評価手段１５によって位相が同じではないと評価された三角形の頂点（特徴点）を対応点から除外し（ステップＳ６）、特徴点対応情報蓄積手段１７によって、誤対応除外済特徴点対応情報を蓄積する（ステップＳ７）。対応点探索装置１０は、以上の手順によって複数の画像間の対応点を探索する。
【００７０】
また、カメラ姿勢推定装置１は、前記した対応点探索装置１０のステップＳ１〜Ｓ７の後に、カメラ姿勢推定手段２０によって、各撮影画像のカメラ位置情報と、各カメラ位置において撮影された画像に含まれる対応する特徴点を利用してカメラ姿勢を推定する（ステップＳ８）。カメラ姿勢推定装置１は、以上の手順によってカメラ姿勢を推定する。
【００７１】
［対応点探索プログラムおよびカメラ姿勢推定プログラム］
ここで、前記した対応点探索装置１０およびカメラ姿勢推定装置１は、一般的なコンピュータを、前記した各手段および各部として機能させるプログラムにより動作させることで実現することができる。このプログラムは、通信回線を介して配布することも可能であるし、ＣＤ−ＲＯＭ等の記録媒体に書き込んで配布することも可能である。
【００７２】
以上、本発明に係る対応点探索装置１０およびカメラ姿勢推定装置１について、発明を実施するための形態により具体的に説明したが、本発明の趣旨はこれらの記載に限定されるものではなく、特許請求の範囲の記載に基づいて広く解釈されなければならない。また、これらの記載に基づいて種々変更、改変などしたものも本発明の趣旨に含まれることはいうまでもない。
【００７３】
例えば、前記した対応点探索装置１０およびカメラ姿勢推定装置１では、特徴点抽出手段１２が局所特徴量算出手法としてＳＩＦＴを用いた例について説明したが、ＳＵＲＦを用いても構わない。この場合、特徴点抽出手段１２は、例えば以下のような処理を行う。
【００７４】
（１）特徴点の検出処理
特徴点の検出処理では、特徴点抽出手段１２が、複数の画像のそれぞれについて近似ヘシアン行列（ヘッセ行列）の行列式を用いて、異なるスケールの画像に対してＬｏＧ（Laplacian of Gaussian）フィルタを畳み込むことで各画素のヘシアン値を算出し、特徴点を検出する。
【００７５】
（２）オリエンテーションの算出処理
オリエンテーションの算出処理では、特徴点抽出手段１２が、複数の画像のそれぞれで検出された特徴点について各特徴点を中心とした半径６ｓ（ｓ：スケール）の範囲から、Haar wavelet（４ｓ）を用いて輝度勾配方向を算出する。そして、特徴点抽出手段１２は、特徴点ごとに輝度勾配方向を３６ビンのヒストグラムで表現し、そのピーク（最高値）を特徴点のオリエンテーションとして決定する。
【００７６】
（３）特徴ベクトルの算出
特徴ベクトルの算出では、特徴点抽出手段１２が、複数の画像のそれぞれで検出された特徴点について予め設定された基準角度（例えば水平を示す０°）を基準として、決定されたオリエンテーションだけ、予め設定された回転方向（例えば右回り）に回転させる。次に、特徴点抽出手段１２は、回転後の各特徴点を中心として２０×２０の正方形領域を４×４のサブ領域に分割する。そして、特徴点抽出手段１２は、各サブ領域内における所定数（例えば２５個）のサンプル点について、Haar wavelet（２ｓ×２ｓ）を算出して４次元ベクトルを算出し、合計６４次元の特徴ベクトルを算出する。
【００７７】
なお、前記したＳＵＲＦによる（１）〜（３）の処理は、例えば「H. Bay, A. Ess, T. Tuytelaars, L. V. Gool:“Speeded-Up Robust Features(SURF)”, 2008, Computer Vision and Image Understanding, Vol.110, No.3, pp.346-359」に詳細に記載されている。
【００７８】
また、前記した対応点探索装置１０およびカメラ姿勢推定装置１では、対応点探索手段１３がユークリッド距離の比から対応点を探索していたが、対応点の探索方法はこの方法に限定されない。例えば、対応点探索装置１０およびカメラ姿勢推定装置１は、対応点探索手段１３によって、複数の画像間において、ユークリッド距離が最短である特徴点の組み合わせを対応点とすることができる。また、対応点探索装置１０およびカメラ姿勢推定装置１は、対応点探索手段１３によって、図２（ａ）の基準画像から見て対応点探索画像の対応点を探索するとともに、図２（ｂ）の対応点探索画像から見て基準画像の対応点を探索し、一致するものを対応点とすることもできる。
【符号の説明】
【００７９】
１  カメラ姿勢推定装置
１０  対応点探索装置
１１  画像蓄積手段
１２  特徴点抽出手段
１３  対応点探索手段
１４  ドロネー三角形分割手段
１５  トポロジー評価手段
１６  誤対応除外手段
１７  特徴点対応情報蓄積手段
２０  カメラ姿勢推定手段
【図１】
2014127068.tif 000003
【図４】
2014127068.tif 000004
【図２】
2014127068.tif 000005
【図３】
2014127068.tif 000006