JP2017199285A - 情報処理装置、情報処理方法、プログラム - Google Patents

Abstract

【課題】 入力データ間の対応を表わす対応データを高速に精度よく推定する。
【解決手段】 第１のデータと第２のデータとを取得する取得手段と、前記第１のデータの部分データと前記第２のデータの部分データとの対応を表す対応データに基づいて、前記対応データの勾配を表す勾配データを導出する導出手段と、前記勾配データに基づいて、前記対応データを伝播させる伝播手段とを備える。
【選択図】 図１

Description

本発明は、データ間の対応を求めるための技術に関する。

従来から、複数のデータ間の対応を求めることにより、さまざまな処理に用いられてきた。例えば、複数の画像の局所領域間の対応を、画素値の整合度に基づいて推定する方法（例えば、画像のブロックマッチング）がある。これにより、ステレオ画像に基づく視差や距離の推定、画像上の物体の認識や追尾、画像の合成や編集をすることが可能になる。

また、対象のデータは画像に限られず、画像以外のデータを対象とすることもできる。例えば、音声や文字などの１次元のデータ、動画像やボクセルなどの３次元のデータなど、様々な種類のデータについて対応の推定方法が検討されている。

非特許文献１は、ステレオ画像上の各座標の対応を示す対応データ（視差データ）のマップを推定する方法を開示している。対応データのマップは、次の２つの処理を繰り返すことで推定される。まず、マップ上の各座標位置が示す対応データを周囲に伝播させ、評価値の高くなる対応データに置き換える。そして、マップ上の各座標の対応データをランダムに変動させることで、評価値の高くなる対応データに置き換える。なお、評価値は、対応データが示すステレオ画像上の２つの局所領域の整合度に応じて計算される

"ＰａｔｃｈＭａｔｃｈ ｓｔｅｒｅｏ − ｓｔｅｒｅｏ ｍａｔｃｈｉｎｇ ｗｉｔｈ ｓｌａｎｔｅｄ ｓｕｐｐｏｒｔ ｗｉｎｄｏｗｓ"， ＢＭＶＣ ２０１１， Ｍｉｃｈａｅｌ Ｂｌｅｙｅｒ１， Ｃｈｒｉｓｔｏｐｈ Ｒｈｅｍａｎｎ１， Ｃａｒｓｔｅｎ Ｒｏｔｈｅｒ

しかしながら、非特許文献１の方法では、対応データをランダムに変動させているため、高い評価値を持つ対応データを引き当てる確率が低い。そのため精度の良い対応データに収束させるのに時間がかかるという課題があった。

本発明は、上記の課題に鑑みてなされたものであり、入力データ間の対応を表わす対応データを高速に精度よく推定することを目的とする。

上記課題を解決するために、情報処理装置は、例えば、第１のデータと第２のデータとを取得する取得手段と、前記第１のデータの部分データと前記第２のデータの部分データとの対応を表す対応データに基づいて、前記対応データの勾配を表す勾配データを導出する導出手段と、前記勾配データに基づいて、前記対応データを伝播させる伝播手段とを備える。

本発明により、入力データ間の対応を表わす対応データを高速に精度よく推定することを目的とする。

第１の実施形態における処理の概要を説明する図である。 第１の実施形態における情報処理装置の機能ブロックを示す図である。 第１の実施形態における情報処理装置の処理フローチャートを示す図である。 第１の実施形態におけるマップの例を表す。 第２の実施形態における情報処理装置の機能ブロックを示す図である。 第２の実施形態における情報処理装置の処理のフローチャートを示す図である。 本願発明の情報処理装置のハードウェア構成の例を示す図である。

まず、本発明の各実施形態の詳細について説明する前に、各実施形態の情報装置のハードウェア構成について、図７を参照して説明する。同図において、ＣＰＵ７１０は、バス７００を介して接続する各デバイスを統括的に制御する。ＣＰＵ７１０は、読み出し専用メモリ（ＲＯＭ）７２０に記憶された処理ステップやプログラムを読み出して実行する。オペレーティングシステム（ＯＳ）をはじめ、本実施形態に係る各処理プログラム、デバイスドライバ等はＲＯＭ７２０に記憶されており、ランダムアクセスメモリ（ＲＡＭ）７３０に一時記憶され、ＣＰＵ７１０によって適宜実行される。また、入力Ｉ／Ｆ７４０は、外部の装置（撮像装置など）から画像を情報処理装置１で処理可能な形式で入力信号として入力する。また、出力Ｉ／Ｆ７５０は、外部装置に、該外部装置が処理可能な形式で、対応付けされた特徴などを出力信号として出力する。

（第１の実施形態）
本実施形態の概要を説明する。まず、２つの異なる視点位置から対象を撮像して得られたステレオ画像を取得する。取得したステレオ画像の一方の画像（第１の画像）の局所領域（部分データ）ごとに、他方の画像（第２の画像）の対応する局所領域を求める。そして、局所領域同士の対応を表す対応データ（本実施形態では視差データ）を推定する。そして、対応データの勾配に基づいてより整合のとれる対応データを伝播させる（置き換える）ことにより、対応データの精度を上げる処理を行う。

なお、本実施形態では、視差データを推定する例について説明するが、後述する変形例において説明するように、視差データ以外のものを対応データとして推定することももちろん可能である。そのため、本願発明における対応データは視差データに限られない。

また、本実施形態では、ステレオ画像上の各画素についての視差データを、画像と同じ解像度を有する配列の画像形式のマップとして保持する。さらに、マップは、視差データの勾配を表わす勾配データを保持する。視差データの勾配とは、マップ上の座標の変化に対する視差データの変化を表わす。

次に、図２を参照して本実施形態の情報処理装置２００の機能構成について説明する。本実施形態の情報処理装置２００は、取得部２１０、設定部２２０、更新部２３０、伝播部２４０からなる。

取得部２１０は、２つの異なる視点（撮像位置）で物体を撮影した２枚の画像を取得する。画像は撮像装置から有線、無線を介して直接取得しても良いし、あらかじめ撮影された画像が記録されたサーバ等からネットワークを介して取得しても良い。また、画像は、撮像装置により撮像されたものだけでなく、コンピュータグラフィックスのようにレンダリングされた画像でも良い。本実施形態では、２枚の画像は、水平に並べた２台の撮像装置それぞれによって撮像されたものであるとし、また、撮像装置の内部パラメータと外部パラメータはキャリブレーション済であり、既知の情報とする。また、画像間の視差データを精度良く推定するためには、撮影する物体にテクスチャが多く含まれていることが望ましいため、プロジェクタを用いて、撮影する物体にテクスチャを投影した状態で撮影した画像を用いてもよい。物体にテクスチャが投影されることで、例えば無地の物体についても正確に対応データを推定できるようになる。

設定部２２０は、取得部２１０で取得した２枚の画像の局所領域の対応を示す視差の初期値を設定する。視差データは、ステレオ画像のうち片側の画像を基準とし計算される。すでに述べたように、本実施形態では、画像と同じ解像度を有する配列の画像形式のマップの各座標位置に対応させて、視差データと勾配データを保持する。本実施形態では、画像Ｉ１を基準としたマップを保持する。以降、マップは、取得した画像と同じ要素数（画素数）を持つ２次元の配列形式を有するとする。この場合、例えば、マップ上の座標（ｕ，ｖ）に対応付けられる視差データＣ（ｕ，ｖ）は、画像Ｉ１上の座標（ｕ，ｖ）と、対応する画像Ｉ２上の座標との視差を表わす。ここで、視差は、画像のＸ軸方向の１次元の視差を表わす。すなわち、視差データＣ（ｕ，ｖ）は、（ｕ，ｖ）における２枚の画像間の視差の値を１次元の数値で示している。

勾配データＧｘ（ｕ，ｖ）とＧｙ（ｕ，ｖ）は、それぞれマップのＸ軸とＹ軸の方向におけるＣ（ｕ，ｖ）の勾配を表わす１次元の数値である。また、Ｇ（ｕ，ｖ）と表記した場合、Ｇｘ（ｕ，ｖ）とＧｙ（ｕ，ｖ）の両方を含めたベクトルを表わす。

更新部２３０は、マップの各画素の勾配データＧ（ｕ，ｖ）を、その画素の周辺の視差データの分布に基づいて更新（導出）する。更新の方法の詳細については後述する。本実施形態においては、勾配データを視差データの分布によって推定するが、外部センサを利用して勾配データを推定しても良い。例えば、距離センサを用意して、距離センサが計測する距離画像に基づいて、マップ上の勾配データを設定しても良い。

伝播部２４０は、マップ上の各座標位置（ｕ，ｖ）における視差データＣ（ｕ，ｖ）を、勾配データＧ（ｕ，ｖ）の示す傾きの方向に伝播させ、評価値が高くなる視差データに置き換える。

以上のように、設定部２２０、更新部２３０、伝播部２４０では、（ｉ）設定部２２０は、２つの画像の初期の視差データを設定する。（ｉｉ）そして、更新部２３０は、その初期の視差データに基づいて勾配データを生成する。（ｉｉｉ）そして、伝播部２４０は、生成された勾配データに基づいて視差データを伝播させる。（ｉｖ）そして、更新部２３０は、伝播させた視差データに基づいて勾配データを更新する。（ｖ）そして、伝播部２４０は、更新された勾配データに基づいて、視差データを再度伝播させる。繰り返し計算の１回目のみ（ｉ）、（ｉｉ）の処理が必要となるが、それ以外の計算では、（ｉｉｉ）〜（ｖ）の処理を繰り返すことにより、視差データの精度が真値に近づくように計算をする
次に、本実施形態の処理手順について説明する。図３は、本実施形態の処理手順を示すフローチャートである。

（ステップＳ３１０）
取得部２１０は、異なる撮影位置で物体を撮影した２つの画像を取得する。本実施形態では、２つの画像のうち、一方の画像をＩ１、右眼の画像をＩ２と表わす。また、以降の説明では、画像上の画素値は、Ｉ１（ｕ，ｖ）、Ｉ２（ｕ，ｖ）と表わす。ｕとｖは、画像上のＸ軸とＹ軸についての座標を表わす。

（ステップＳ３２０）
設定部２２０は、マップ上の各座標の視差データの初期値を設定する。本実施形態では、視差データを座標ごとにランダムに設定する。具体的には、式（１）を使って設定する。

式（１）は、ＣｍａｘからＣｍｉｎまでの数値をランダムに設定する。ここで、Ｒａｎｄは、０〜１までの範囲で発生する一様乱数を表わす。ＣｍａｘとＣｍｉｎは、ステレオ画像の視差の上限と下限を表わす。ＣｍａｘとＣｍｉｎの値は、予め設定する固定値とする。ランダムに設定することで、各座標で異なる視差が設定される。

マップ上の一部でも視差データの精度が高ければ、正しい視差データを伝播させることで、マップ全体の視差データの精度を向上できる。ランダムに設定した場合でも、マップ上の一部では精度の高い視差を設定することができるため本実施形態では上記のようにランダムに設定している。

しかしながら、本願発明の初期値の設定はランダム以外の設定方法でも良い。具体的には、画像上の各座標について、対応データを探索的に計算するブロックマッチングによって設定しても良い。さらに、Ｇｒａｐｈ ＣｕｔやＢｅｌｉｅｆ Ｐｒｏｐａｇａｔｉｏｎなどの最適化アルゴリズムを利用して対応データを推定し、設定しても良い。他にも、ステレオ画像から視差を推定する場合には、別途距離センサを用意して、距離センサが計測する距離画像に基づいて、対応データのマップの初期値を設定しても良い。具体的には、距離センサが計測する距離画像を３次元点群に変換し、この点群をステレオ画像の座標系に投影することで、ステレオ画像上の各座標における距離値を求める。次に各座標の距離値から視差に変化し、この視差の値を対応データの初期値として設定する。（距離値と視差値とは１対１の関係があり、相互に変換可能である。）

（ステップＳ３３０）
更新部２３０は、マップ上の各座標の勾配データを、その周辺の視差データの分布に基づいて更新（生成）する。本実施形態では、Ｘ軸方向とＹ軸方向に対して、視差データの勾配を計量するフィルタを適用することで、マップ上の各座標の勾配データを計算する。

具体的にマップ上の各座標の勾配データは、式（２）、（３）によって計算する。

式（２）、（３）に示すように、勾配データは、注目する座標（ｕ，ｖ）を中心に、ｋ離れた２か所の対応データの傾き（変化率）として計算する。ここで、ｋの値は、予め設定する固定値とする。

勾配データの計算は、視差データの分布に基づいて計算する方法であれば、上記以外のような方法でも良い。例えば、ソベルフィルタによって計算しても良いし、マップ上の視差データを微分することで計算しても良い。注目する座標の周辺の視差データの値に対して、面フィッティングを行うことで、勾配を計算しても良い。

以上の処理により計算されるマップ上のそれぞれの座標について勾配データを示したのが、図１（Ａ）の線１０２である。本ステップでは、繰り返し計算の１回目では、Ｓ３２０で設定された視差データの初期値に基づいて、勾配データを生成する。繰り返し計算の２回目以降では、Ｓ３４０で伝播された視差データに基づき式（２）、（３）で計算される勾配データによりそれまでの勾配データを更新する処理を行う。なお、繰り返し計算の１回目では、視差データの精度が低いため、その視差データに基づいて勾配データを計算しても計算精度が低い。そのため、繰り返し計算の１回目においては勾配を０（Ｇｘ＝０、Ｇｙ＝０）として、設定しても良い。

また、マップ上の各座標の勾配データを、その周辺の勾配データに基づいて更に更新しても良い。例えば、注目する座標（ｕ，ｖ）の周辺の視差データから勾配データを計算し、さらに座標（ｕ，ｖ）の周辺の勾配データとの平均をとることで、座標（ｕ，ｖ）の勾配データを計算しても良い。
（ステップＳ３４０）
伝播部２４０は、マップ上の各座標の視差データを勾配データの示す傾きの方向に伝播させ、評価値が高くなる視差データに置き換える。更に、視差データの置き換えとともに勾配データも置き換える。 まず、マップ上の各座標を順番に選択する。本実施形態では、ラスタスキャンの要領で、マップ上の左上から右下に向けて順番に選択する。図４の４１０は、マップを表わす。４２０は、選択中の座標を表わす。以降、選択した座標は（ｕ，ｖ）と表わす。

次に、選択した座標（ｕ，ｖ）の周辺（近傍）の座標から視差データを伝播させる。本実施形態では、選択した座標（ｕ，ｖ）の左と上の座標、すなわち座標（ｕ−１，ｖ）と座標（ｕ，ｖ−１）の２か所の視差データを座標（ｕ，ｖ）に向かって伝播させる。このとき視差データは、勾配データの示す傾きの方向に変化させる。具体的には、伝播させる元の座標を（ｓ，ｔ）としたとき、式（４）、（５）によって計算する。

ここで、Ｃ′（ｕ，ｖ）、Ｇ′（ｕ，ｖ）は、座標（ｓ，ｔ）の視差データと勾配データとを、選択した座標（ｕ，ｖ）に向かって伝播させたそれぞれのデータを示している。式（４）に示すように、視差データＣ′（ｕ，ｖ）は、伝播元の視差データＣ（ｓ，ｔ）に勾配データＧ（ｓ，ｔ）の傾き分の変化を加えて計算する。なお、勾配データは伝播元の勾配データと同じであると推定して伝播させる。以降の説明で、座標（ｕ，ｖ）に元々ある（すなわち、更新前）視差データをＣ１とする。座標（ｕ−１，ｖ）と座標（ｕ，ｖ−１）の２か所の視差データを、伝播させることにより生成した視差データをＣ２、Ｃ３とする。

次に、Ｃ１、Ｃ２、Ｃ３について、評価値を計算する。視差データの評価は、基準となる画像Ｉ１上の座標（ｕ，ｖ）と、視差を加えた（視差を考慮することで決定された）画像Ｉ２上の座標（ｕ＋Ｃ（ｕ，ｖ），ｖ）との局所領域の整合度によって計算する。具体的に、本実施形態では、マップ上の座標（ｕ，ｖ）における視差データＣの評価値Ｅを、式（６）、式（７）に示すＳＡＤ（Ｓｕｍ ｏｆ Ａｂｓｏｌｕｔｅ Ｄｉｆｆｅｒｅｎｃｅ）に基づいて計算する。

式（６）における評価値Ｅは、Ｉ１とＩ２とで比較する局所領域が整合するほど、高い値となる。ｗは、ＳＡＤを計算する局所領域のサイズを表わす。ｗの値は、予め設定する固定値とする。式（７）のＤは、座標（ｕ，ｖ）を中心とした局所領域内の位置（ｍ，ｎ）について、視差データの示す２つの座標の画素値の差を計量する関数である。本実施形態では、視差データＣの値だけずれた２つの座標の画素値の差の絶対値を計量する。

次に、座標（ｕ，ｖ）における、Ｃ１、Ｃ２、Ｃ３の視差データのうち、最も評価値の高い視差データを、座標（ｕ，ｖ）の新しい視差データとして、マップ上に割り当てる。この処理により、座標（ｕ，ｖ）に元々ある視差データＣ１の評価値に比べ、伝播による視差データＣ２やＣ３の評価値が高い場合に、マップ上の視差データが置き換わる（更新される）。この場合、式（４）、（５）によって推定した視差データを、新しい視差データとして設定する。更に、座標(u,v)の視差データの置き換えとともに、勾配データも置き換える。なお、勾配データの置き換えを行わず、視差データのみ置き換えるようにしても良い。

以上の操作を、選択する座標（ｕ，ｖ）を変えて行うことで、マップ全体について視差データおよび勾配データの置き換えを行う。

なお、本発明は、マップ上の左上から右下に向けて順番に選択することに限られない。例えば、マップ上の右下から左上に向けて選択しても良い。選択する方向は、何れの方向でも良い。画像を複数のブロック分割し、そのブロック毎に所定の方向に順番に選択しても良い。ランダムに座標を選択しても良い。また、伝播部を含む繰り返しの毎に、伝播部における座標の選択方法を変えても良い。例えば、奇数番の繰り返しでは、マップ上の左上から右下に向けて選択し、偶数番の繰り返しでは、マップ上の右下から左上に向けて選択するようにしても良い。

また、選択した座標（ｕ，ｖ）の左と上の座標、すなわち座標（ｕ−１，ｖ）と座標（ｕ，ｖ−１）の２か所の視差データを座標（ｕ，ｖ）に向かって伝播させる処理を説明したが、伝播させる元の座標は、左と上以外の座標でも良い。選択した座標（ｕ，ｖ）の右と下の座標、すなわち座標（ｕ＋１，ｖ）と座標（ｕ，ｖ＋１）の座標から伝播させても良い。２か所以上の複数の座標から伝播させても良いし、１つの座標から伝播させても良い。１つ以上離れた座標から伝播させても良い。また、周辺の座標から選択した座標に向かって伝播させても良いし、これとは逆に、選択した座標から周辺の座標に向かって伝播させても良い。

（ステップＳ３５０）
Ｓ３５０では、伝播部２４０は、終了条件を満たしているかの判定を行う。本実施形態では、Ｓ３３０における更新部２３０の処理とＳ３４０における伝播部２４０の処理を、所定回数以上繰り返していることを終了条件とする。所定回数以上繰り返している場合には、処理を終了し、所定回数未満であれば、ステップ３３０の処理に戻る。所定回数の繰り返しの後、図１（Ｃ）のように、黒丸で示される求められた視差データは、破線で示される真値に収束する。

なお、繰り返し処理の終了の判定は、マップ上の視差データの変化量に基づいて行っても良い。例えば、繰り返し計算の度に、マップ上の視差データの変化量を計算し、変化量が所定値以下であれば終了するように、判定を行っても良い。マップ上の視差データの変化量は、異なる繰り返し時点のマップの差に基づく指標であれば、どのような指標でも良い。マップ上の各座標の要素の差の平均値でも良いし、最大値や最小値でも良い。本実施形態の場合、更新部２３０の処理の後のマップの状態に基づいて変化量を計算しても良いし、伝播部２４０の処理の後のマップの状態に基づいて変化量を計算しても良い。

本願発明は、各座標の周辺の視差データから勾配データを更新し、勾配データの示す傾きの方向に視差データを伝播させることにより、視差データの伝播をより精度よく行うことができる。

以上説明した本発明にかかる処理によって視差データおよび勾配データが真値に近づいていく様子を図１を参照して説明する。
図１は、簡単のため１次元で表した各座標を横軸にし、各座標に対して視差の値を縦軸にして表したグラフである。黒丸１０１はそれぞれの座標に対応する視差データを表し、線１０２は視差データの勾配データを示す。図１（Ａ）は、繰り返し計算の１回目の処理が終わった後の視差データ、および勾配データである。上記で説明したように、視差データの初期値はランダムに与えられるため、１回の計算ではまだ破線１０３によって示される視差データの真値かれている。図１（Ｂ）は、２回目の繰り返し計算における勾配データの更新後のデータ１０４を示す。すなわち、図１（Ａ）の視差データの分布に基づいて勾配データを更新した後のデータである。図１（Ｃ）は図１（Ｂ）の後に再び伝播の処理を行った後のデータであり真値に収束していることを示している。すなわち、上記説明したように、勾配データの更新処理、視差データおよび勾配データの伝播処理を繰り返すことにより、視差データを真値に収束させることができる。ここでは簡単のため、２回の繰り返し計算で真値に収束した例を示したが、物体が複雑な形状をしている場合には更に多くの繰り返し計算が必要となる。

以上述べたように、本発明では、入力データの対応を表わすマップを推定する上で、対応データの分布から計算する勾配データに応じて対応データを伝播させる。これにより、精度の高いマップを推定できる。

（第２の実施形態）
第１の実施形態では、（ｉ）設定部２２０は、２つの画像の初期の視差データを設定する。（ｉｉ）そして、更新部２３０は、その初期の視差データに基づいて勾配データを生成する。（ｉｉｉ）そして、伝播部２４０は、生成された勾配データに基づいて視差データを伝播させる。（ｉｖ）そして、更新部２３０は、伝播させた視差データに基づいて勾配データを計算し、それまで保持していた勾配データを更新する。（ｖ）そして、伝播部２４０は、更新された勾配データに基づいて、視差データを再度伝播させる。繰り返し計算の１回目のみ（ｉ）、（ｉｉ）の処理が必要となるが、それ以外の計算では、（ｉｉｉ）〜（ｖ）の処理を繰り返すことにより、視差データの精度が真値に近づくように計算をした。

それに対して、第２の実施形態では、（ｉｖ）で求められた勾配データを保持することをせず、（ｖ）において伝播によって変化する視差データの分布に応じて、その都度勾配データを計算しながら、視差データの伝播を行う。すなわち、一部の視差データが伝播によって変更された場合に、勾配データを計算しなおす。そして、計算された新たな勾配データでその他の視差データを伝播させる処理を行う。これにより、伝播される視差データの分布が即座に反映された勾配データを計算するので、より少ない繰り返し計算で真値に収束する効果が期待できる。

本実施形態では、第１の実施形態と同様に、ステレオ画像を入力データとして、画像上の各座標の対応データを高精度に推定する方法を説明する。上記で説明したように、本実施形態では、第１の実施形態とは異なり、マップは視差データのみを保持し、勾配データは保持しない。勾配データは、伝播によって変化する視差データの分布に応じてその都度周辺の視差データより計算する。

次に本実施形態にかかる情報処理装置５００の機能構成を、図５を参照しながら説明する。報処理装置５００は、取得部５１０、設定部５２０、伝播部５３０からなる。

取得部５１０と設定部５２０の処理は、第１の実施形態における取得部２１０、設定部２２０と同じである。

伝播部５３０は、マップ上の各座標の視差データを、勾配データの示す傾きの方向に伝播させ、評価値が高くなる視差データに置き換える。そして、視差データが置き換えられた場合には、新しい視差データの分布から勾配データを計算しなおす
本実施形態の以降の説明では、画像上の画素の表現や、マップ上の各座標の対応データの表現は、第１の実施形態と同じである。

次に、本実施形態の処理手順について説明する。図６は、本実施形態の処理手順を示すフローチャートである。

（ステップＳ６１０）
取得部５１０は、異なる撮影位置で物体を撮影した２枚の画像Ｉ１とＩ２を取得する。本ステップは第１の実施形態におけるＳ３１０と同様である。

（ステップＳ６２０）
設定部２２０は、マップ上の各座標の視差データの初期値を設定する。本ステップは、第１の実施形態のＳ３２０と同じである。

（ステップＳ６３０）
伝播部２５０は、まず、マップ上の各座標の勾配データを、周辺の視差データの分布から計算（生成）する。そして生成された勾配データの示す傾きの方向に視差データを伝播させ、評価値が高くなる視差データで設定部２２０で設定された視差データの初期値を置き換える。

具体的には、マップ上の各座標位置について、その周辺の視差データから勾配フィルタを使って勾配データを計算し、勾配データの傾きの方向に視差データを伝播させる。

これを行うために、まず、マップ上の各座標を順番に選択する。ここでは、第１の実施形態と同じように、ラスタスキャンの要領で、マップ上の左上から右下に向けて順番に選択する。図４の４１０は、マップを表わす。３２０は、選択中の座標を表わす。以降、選択した座標は（ｕ，ｖ）と表わす。

次に、選択した座標（ｕ，ｖ）の周辺の座標から視差データを伝播させる。本実施形態では、選択した座標（ｕ，ｖ）の左と上の座標、すなわち座標（ｕ−１，ｖ）と座標（ｕ，ｖ−１）の２か所の視差データを座標（ｕ，ｖ）に向かって伝播させる。このとき視差データは、勾配データの示す傾きの方向に変化させる。具体的には、伝播させる元の座標を（ｓ，ｔ）としたとき、式（８）によって計算する。ただし、第１の実施形態とは異なり、マップは勾配データを保持していないため、勾配データは現在のマップ上の視差データの分布に応じて計算する。具体的に、式（８）の勾配データＧｘ（ｓ，ｔ）、Ｇｙ（ｓ，ｔ）は、式（９）、（１０）に示す勾配フィルタを使って計算する。

ここで、Ｃ′（ｕ，ｖ）は、座標（ｓ，ｔ）の視差データを、選択した座標（ｕ，ｖ）に向かって伝播させた対応データを示す。式（８）に示すように、対応データＣ′（ｕ，ｖ）は、伝播元の対応データＣ（ｓ，ｔ）に勾配データＧ（ｓ，ｔ）の傾き分の変化を加えて計算する。
以降の説明で、座標（ｕ，ｖ）に元々ある視差データをＣ１とする。座標（ｕ−１，ｖ）と座標（ｕ，ｖ−１）の２か所の対応データを、伝播させることにより生成した対応データをＣ２、Ｃ３とする。

次に、Ｃ１、Ｃ２、Ｃ３について、評価値を計算する。具体的な評価値の計算は、第１の実施形態と同じであり、式（６）、（７）に基づいて計算する。

次に、座標（ｕ，ｖ）における、Ｃ１、Ｃ２、Ｃ３の視差データのうち、最も評価値の高い視差データを、座標（ｕ，ｖ）の新しい視差データとして、マップ上に割り当てる。

この処理により、座標（ｕ，ｖ）に元々ある視差データＣ１の評価値に比べ、伝播による視差データＣ２やＣ３の評価値が高い場合に、マップ上の視差データが置き換わる。

以上の操作を、選択する座標（ｕ，ｖ）を変えて行うことで、マップ全体について視差データの置き換えを行う。

（ステップＳ６４０）
Ｓ６４０では、本フローの終了判定を行う。具体的な内容は、第１の実施形態と同じである。

本実施形態によれば、伝播される視差データの分布が即座に反映された勾配データを計算するので、より少ない繰り返し計算で真値に収束する効果が期待できる。

（第３の実施形態）
本実施形態では、上記実施形態において求められた視差データを利用するアプリケーションについて説明する。

上記実施形態では、マップとしてステレオ画像における部分領域の視差を推定した。推定した視差を以下の式を用いて計算することにより、距離値を求めることが可能となる。すなわち、ステレオ画像を撮像したカメラの相対的な位置姿勢が既知の場合、画像間の視差と距離値は１対１の関係を持つため、視差と距離値は相互に変換できる。

ここで、ｆはカメラの焦点距離、Ｂはステレオカメラのベースライン（ステレオカメラの間隔）、Ｄは距離値、Ｃは視差を表わす。また、距離値は、３次元座標に変換して出力しても良い。距離値や３次元座標を出力することで、物体の３次元形状を計測するために利用できる。上記のように、対応データを変換する場合、上記実施形態の情報処理装置は、さらに対応データ変換部を備えても良い。また、対応データとして、視差ではなく距離値をマップ上に保持するように変更しても良い。

また、出力した距離値や３次元座標に基づいて、画像上で観測する物体の位置姿勢を計測しても良い。例えば、画像上で観測する物体の３次元モデルが既知の場合、３次元モデルと推定した距離値とのＩＣＰ（Ｉｔｅｒａｔｉｖｅ Ｃｌｏｓｅｓｔ Ｐｏｉｎｔ）を行うことで、物体の位置姿勢を推定できる。

さらに、別の利用アプリケーションを説明する。２つの画像間の視差データに基づいて、画像間の視差データの示すずれを最小化するように２つの画像を重ねることで、２枚の画像からパノラマ画像を合成する方法として利用できる。また、異なる視差データの傾向を閾値によって分けることで、画像上に映る背景と前景の物体を分けて、物体を検出する方法として利用できる。例えば、ステレオ画像から計算した距離値の情報に基づいて、距離センサを利用するＳＬＡＭ（Ｓｉｍｕｌｔａｎｅｏｕｓ Ｌｏｃａｌｉｚａｔｉｏｎ ａｎｄ Ｍａｐｐｉｎｇ）の入力データに利用できる。例えば、３次元のボクセルデータの対応データを表わすマップを推定する場合、複数の３次元のボクセルデータを対応データに基づいて合成し、精度を向上させることができる。

以降、第１と第２の実施形態に対する変形例を説明する。なお、以下の変形例による変形が施された実施形態の処理結果を用いて、第３の実施形態の処理を行うことはもちろん可能である。

（変形例１）
本変形例では、対応データとして視差データ以外の情報を推定する例を説明する。まず、２次元のベクトルを用いる例を説明する。

上記実施形態では、画像のＸ軸方向の１次元の視差を対応データとした。本変形例では、画像のＸ軸とＹ軸方向における２次元の視差を対応データとする。なお、２次元の視差を推定する場合、画像上の局所領域の対応が必ずしも画像のＸ軸方向にない条件においても、２枚の画像の対応データを精度良く推定できる。

本変形例では、２枚の画像の対応を表わすマップを推定する。対応を計算する２枚の画像のうち、片方をＩ１、もう片方をＩ２と表わす。画像上の画素値は、Ｉ１（ｕ，ｖ）、Ｉ２（ｕ，ｖ）と表わす。ｕとｖは、画像上のＸ軸とＹ軸上の座標を表わす。

また、マップは、２枚の画像のうち片側の画像を基準としたパラメータを保持する。本変形例では、画像Ｉ１を基準としたマップを保持する。従って、マップは、画像と同じ要素数（画素数）を持つ２次元の配列とする。この場合、例えば、マップ上の座標（ｕ，ｖ）にある２次元の視差データは、画像Ｉ１上の座標（ｕ，ｖ）と、対応する画像Ｉ２上の座標との差を表わす。ここで、２次元の視差データは、Ｘ軸とＹ軸についての座標の差を表わす２次元のベクトルである。

また、マップ上の各座標の視差データをＣ（ｕ，ｖ）、勾配データをＧｘ（ｕ，ｖ）、Ｇｙ（ｕ，ｖ）と表わす。対応データＣ（ｕ，ｖ）は、２枚の画像上の視差を表わす２次元ベクトルである。ここで、Ｃ（ｕ，ｖ）は、Ｘ軸方向の差Ｃｘ（ｕ，ｖ）と、Ｙ軸方向の差Ｃｙ（ｕ，ｖ）の２つの成分を含む。勾配データＧｘ（ｕ，ｖ）とＧｙ（ｕ，ｖ）は、マップのＸ軸とＹ軸の方向におけるＣ（ｕ，ｖ）の勾配を表わす２次元のベクトルである。また、Ｇ（ｕ，ｖ）と表記した場合、Ｇｘ（ｕ，ｖ）とＧｙ（ｕ，ｖ）の両方を含めたベクトルを表わす。なお、第２の実施形態に示すように、マップ上に勾配データを保持しないようにしても良い。

本変形例の構成は、第１或いは第２の実施形態と同じである。本変形例の処理手順は、第１或いは第２の実施形態で説明した計算式を、本変形例の対応データの次元に変更して計算する。例えば、設定部では、２次元の対応データの２つの成分について、初期値を設定する。更新部では、２次元の対応データの２つの成分について、勾配を計算する。伝播部では、マップ上の各座標の視差データを、勾配データの２つの成分の示す傾きの方向に伝播させ、評価値が高くなる視差データに置き換える。また伝播部の、式（６）、式（７）で求める評価値については、２次元の対応データの２つの成分を用いて、式（７）を変形した式（１２）により計算する。

ここで、Ｃｘ（ｕ，ｖ）とＣｙ（ｕ，ｖ）は、視差データＣ（ｕ，ｖ）に含まれるＸ軸とＹ軸に関する視差を表わす。式（１１）は、Ｘ軸とＹ軸それぞれに視差のある条件について、画素値の差を計量する。

以上のように操作を変更することで、対応データは２つの成分を持つ２次元のベクトルに拡張可能である。

以上示すように、本発明における対応データは２次元のベクトルでも良い。同様に、本発明における対応データは２次元以上のベクトルでも良い。例えば、画像上の局所領域のスケールを表わす情報や、局所領域の回転を表わす情報などを、対応データに加えても良い。勾配データは、対応データの次元数に応じて保持する。すなわち、対応データの次元の成分毎に、勾配データを保持する。

例えば、視差データとしてスケールや回転を表わす情報を保持する場合、視差データの評価値は、視差データに含まれるスケールや回転に応じて計算する。具体的には、例えば、スケールＣｓを視差データの成分として加える場合、式（１２）は式（１３）のように変形する。

式（１２）では、比較を行う画像Ｉ１上の注目座標（ｕ，ｖ）を基準に、局所領域の内の各座標にスケールＧｓ分の変化を加えて、画像Ｉ２上の座標との画素の比較を行う。また、視差データに局所領域の回転を表わす情報を加える場合も同様で、回転による座標の変化を加えて、Ｉ１とＩ２上の画素の比較を行う。

また、対応データとして画像間の視差データの代わりに、距離値を利用しても良い。ステレオカメラの相対的な位置姿勢が既知の場合、画像間の視差と距離値は１対１の関係を持つため、視差と距離値は相互に変換できる。

（変形例２）
上記実施形態では、２次元データであるステレオ画像について、各画像間における座標の対応を表わす２次元のマップを推定する例を説明した。ただし、本発明の方法は、２次元以外の入力データにも拡張できる。２次元以外のデータのバリエーションとしては、例えば、音声や文字列などの１次元の入力データや、動画像や３次元のボクセルなどの３次元の入力データがある。

１次元のデータを入力とする場合、第１と第２の実施形態の処理は、次のように変更する必要がある。まず、入力データの各座標の対応を表わすマップは、入力データの次元数と同じ１次元のマップで表現する。つまり、１次元の入力データの各座標についての対応データを１次元のマップとして保持する。また、対応データの勾配を表わす勾配データは、１次元の座標に対する対応データの勾配を計算する（第１と第２の実施形態では、入力データは２次元であるため、Ｘ軸とＹ軸のそれぞれに対する対応データの勾配を計算する）。

具体的に、１次元の入力データとして、２つの音声データから、各座標（音声データの場合、時刻とも表現できる）の対応データを推定する例を説明する。音声の場合、入力データの各座標の値は画素値ではなく、周波数で表わすものとする。この場合、マップは、音声の要素数と同じ要素数を持つ１次元の配列とする。対応データは、２つの音声データの座標の差を１次元のベクトルとして表わす。勾配データは、マップ上の１次元の座標空間における対応データの勾配を表わす。上記データ構造に基づいて、第１或いは第２の実施形態で説明した処理の順序で、マップ上の対応データの分布から勾配データを計算し、勾配データに応じて視差データを伝播させることで、マップ上の対応データの精度を向上させる。

また、多次元のデータを入力とする場合、第１と第２の実施形態の処理は、次のように変更する必要がある。まず、入力データの各座標の対応を表わすマップは、入力データの次元数と同じ次元数で表現する。対応データの勾配を表わす勾配データは、入力データの各次元の方向についての勾配を保持する。

具体的に、３次元の入力データを扱う例として、２つの動画像から、各座標の対応データを推定する変形例を説明する。この場合、マップは、動画像と同じ要素数（画素数×フレーム数）を持つ３次元の配列とする。対応データは、注目する座標と対応する座標との差を３次元のベクトルとして表わす。勾配データは、対応データの３つの成分のそれぞれについて、Ｘ軸とＹ軸と時間軸のそれぞれの方向に対する勾配を表わす。上記データ構造に基づいて、第１或いは第２の実施形態で説明した処理の順序で、マップ上の対応データの分布から勾配データを計算し、勾配データに応じて対応データを伝播させることで、マップ上の対応データの精度を向上させる。

（変形例３）
第１と第２の実施形態では、ステレオ画像が入力された場合に、それぞれの画像の部分領域同士の対応を見つける処理を示した。しかしながら、本願発明は、ステレオ画像のように複数のデータの入力に限られるものではなく、入力データは１つでも良い。例えば、１つの画像を入力として、各座標について最も類似する領域を、同一の画像内で対応付けるように計算しても良い。この場合、ステレオ画像の代わりに、同一の画像を入力するように、第１と第２の実施形態を変更する（具体的には、Ｉ１＝Ｉ２として処理を行えば良い）。

ただし、画像上の局所領域を同一の画像内で対応付ける場合、第１と第２の実施形態をそのまま適応すると、マップ上の対応データは視差＝０として推定されることが予想される。これは、視差＝０の状態が最も対応データの評価値が高いためである。これを避けるためには、対応データの視差の値がほぼ０の時に、視差データの評価値が悪くなるように、評価値の計算式にペナルティを加えるようにすればよい。

また、入力データは３つ以上でも良い。例えば、３台のカメラで撮影した画像に基づいてマップを推定する場合を考える。この場合、所定のカメラの画像の座標系を基準にマップを作成し、マップ上で保持する視差データが示す３台のカメラの画像の各領域の整合度を利用して評価値を計算する。３台分のカメラの画像情報を利用することで、マップ上の視差データの評価値をより正確に計算できる。

（変形例４）
上記実施形態では、視差データの評価値を行う際に、ＳＡＤを利用して画像領域の比較を行う処理をもって説明した。ただし、視差データの評価は、比較する画像上の局所領域が整合するほど、評価値が高くなるような計算方法であれば、どのような方法でも良い。ＳＳＤ（Ｓｕｍ ｏｆ Ｓｑｕａｒｅｄ Ｄｉｆｆｅｒｅｎｃｅ）を利用しても良いし、ＮＣＣ（Ｎｏｒｍａｌｉｚｅｄ Ｃｒｏｓｓ−Ｃｏｒｒｅｌａｔｉｏｎ）を利用しても良い。

また、局所領域の比較計算は、勾配データに応じて、比較する局所領域の部位ごとに視差データを変化させても良い。この場合、式（６）、式（７）で求める評価値は、式（７）を変形した式（１４）、（１５）により計算する。

ここで、式（１５）の関数Ｆに示すように、勾配データＧｘ，Ｇｙと、局所領域の中心を基準とした位置（ｍ，ｎ）に応じて、視差データＣ（ｕ，ｎ）の値（視差の値）を増減させる。勾配データに基づいて、局所領域の部位ごとに比較する座標を計算することで、より精度よく評価値を計算できる。

（変形例５）
第１の実施形態では、更新部２３０と伝播部２４０とを含む処理を繰り返す例を説明した。しかし、本発明では、繰り返しの度に、マップ上の視差データ、勾配データをリセットしなければ、更新部２３０と伝播部２４０の順序はどちらでも良い。繰り返し計算の中で、少なくとも１回は更新部２３０で計算した勾配データを、伝播部２４０で利用できる方法であればどのような処理順序でも良い。この条件下であれば、繰り返し毎に更新部２３０と伝播部２４０の処理の並びを変えても良いし、更新部２３０と伝播部２４０の処理の回数を減らしても増やしても良い。

具体的には、例えば、繰り返しの１回目には伝播部２４０の処理のみを行い、繰り返しの２回目以降には更新部２３０と伝播部２４０の処理を行うようにしても良い。

（その他の実施形態）
本発明は、上述の実施形態の１以上の機能を実現するプログラムを、ネットワーク又は記憶媒体を介してシステム又は装置に供給し、そのシステム又は装置のコンピュータにおける１つ以上のプロセッサーがプログラムを読出し実行する処理でも実現可能である。また、１以上の機能を実現する回路（例えば、ＡＳＩＣ）によっても実現可能である。

＜効果＞
本発明では、入力データの対応を表わすマップを推定する上で、対応データの分布から計算する勾配データに応じて対応データを伝播させる。これにより、精度の高いマップを推定できる。

＜定義＞
本発明において、入力データとは、対応を推定する対象である。入力データは、情報を所定の次元で保持する。例えば、周波数を１次元のデータとして保持する音声データや、輝度値を２次元のデータとして保持する画像データなどがある。対応データは、入力データの２つの領域の対応関係を表わす情報であれば、どのような情報でも良い。入力データの２つの領域の座標の差を表わす情報でも良いし、さらにスケールや回転を加えた情報でも良い。マップは、入力データの少なくとも一部の座標についての対応データを要素として保持する。勾配データは、マップ上の対応データの勾配を表わす。ここで、勾配とは、マップ上の座標の変化に対する対応データの変化を表わす。マップは、さらに勾配データを保持しても良い。

設定部は、マップ上の対応データの初期値を設定する。設定部は、マップ上の少なくとも一部の対応データについて、真値に近い値を設定できる方法であれば、どのような方法でも良い。ランダムに設定しても良いし、ブロックマッチングなどの他の対応データの推定方法を利用して設定しても良い。

更新部は、対応データの分布に基づいて、勾配データを計算する。

伝播部は、マップ上の各座標の対応データを、勾配データの示す傾きの方向に伝播させる。このとき、伝播させた対応データの評価値が、マップ上に元々あった対応データの評価値よりより高くなる場合に、マップ上の対応データを置き換える。伝播部では、対応データのみを伝播させても良いし、さらに勾配データを伝播させても良い。

評価値は、対応データが示す入力データの２つの領域の整合度に応じて計算する。評価値は、２つの領域が整合する場合に高くなる計算方法であれば、どのような計算方法でも良い。

Claims (14)

1. 第１のデータと第２のデータとを取得する取得手段と、
   前記第１のデータの部分データと前記第２のデータの部分データとの対応を表す対応データに基づいて、前記対応データの勾配を表す勾配データを導出する導出手段と、
   前記勾配データに基づいて、前記対応データを伝播させる伝播手段とを備えることを特徴とする情報処理装置。
2. 前記対応データが所定の条件を満たすまで前記導出手段による処理と前記伝播手段による処理を繰り返すように、前記導出手段と、前記伝播手段とを制御する制御手段とを更に備えることを特徴とする請求項１に記載の情報処理装置。
3. 前記導出手段は、前記伝播手段による対応データの伝播により更新された対応データに基づいて新たに勾配データを導出し、
   前記伝播手段は、前記新たに導出された勾配データに基づいて対応データを伝播させることを特徴とする請求項２に記載の情報処理装置。
4. 前記第１のデータと前記第２のデータは、異なる撮像位置から物体を撮像して得られる第１の画像と第２の画像であり、
   前記対応データは、前記第１の画像の部分領域と前記第２の画像の部分領域の間の視差を表すデータであることを特徴とする請求項１乃至３のいずれか１項に記載の情報処理装置。
5. 前記対応データは、前記第１の画像および前記第２の画像と同じ配列形式を有するマップとして保持されることを特徴とする請求項４に記載の情報処理装置。
6. 前記視差を表すデータは、前記第１の画像の部分領域の座標位置または前記第２の画像の部分領域の座標位置のいずれかを基準としてデータであることを特徴とする請求項４または５に記載の情報処理装置。
7. 更に、前記対応データを評価する評価手段を備え、
   前記伝播手段は、前記勾配データと前記評価手段の結果とに基づいて、前記対応データを伝播させることを特徴とする請求項５または６に記載の情報処理装置。
8. 前記評価手段は、前記対応データによって決定される前記第１のデータの部分データと前記第２のデータの部分データとが整合しているほど高くなるような値を評価値として求めることを特徴とする請求項７に記載の情報処理装置。
9. 前記伝播手段は、前記マップにおいて、所定の対応データの評価値が近傍の対応データの評価値よりも高い場合に、前記所定の対応データで前記近傍の対応データを置き換えるように対応データを伝播させることを特徴とする請求項８に記載の情報処理装置。
10. 前記評価手段は、更に、前記勾配データに基づいて前記対応データを評価することを特徴とする請求項８または９に記載の情報処理装置。
11. 入力データから第１のデータと第２のデータとを取得する取得手段と、
    前記第１のデータと前記第２のデータとの対応を表す対応データに基づいて、前記対応データの勾配を表す勾配データを導出する導出手段と、
    前記勾配データに基づいて、前記対応データを伝播させる伝播手段とを備えることを特徴とする情報処理装置。
    
12. 第１のデータと第２のデータとを取得する取得工程と、
    前記第１のデータの部分データと前記第２のデータの部分データとの対応を表す対応データに基づいて、前記対応データの勾配を表す勾配データを導出する導出工程と、
    前記勾配データに基づいて、前記対応データを伝播させる伝播工程とを備えることを特徴とする情報処理方法。
13. 入力データから第１のデータと第２のデータとを取得する取得工程と、
    前記第１のデータと前記第２のデータとの対応を表す対応データに基づいて、前記対応データの勾配を表す勾配データを導出する導出工程と、
    前記勾配データに基づいて、前記対応データを伝播させる伝播工程とを備えることを特徴とする情報処理方法。
14. コンピュータを、請求項１乃至１１のいずれか１項に記載の情報処理装置の各手段として機能させるためのプログラム。