対応問題

対応問題（たいおうもんだい、英 : "correspondence problem"）、または対応点問題（たいおうてんもんだい）とは、ある画像のある部分が、別の画像のどの部分に対応するかを特定する問題である 。ここで、違いはカメラの動き、時間の経過、および/または写真内のオブジェクトの動きにより生まれる。
対応（英 : correspondence）は、コンピュータビジョンの基本的な問題である。影響力のあるコンピュータビジョンの研究者である金出武夫氏は、コンピュータビジョンの3つの基本的な問題は、「対応、対応、対応」（英 : "“Correspondence, correspondence, and correspondence!”"）であると述べたことで有名である。実際、対応はオプティカルフロー（時間的に連続した2画像）、密ステレオビジョン（ステレオカメラペアによる2画像）、ストラクチャーフロムモーション（SfM）、ビジュアルSLAM（同一シーンの部分的に重複する異なる視点からの画像群）、クロスシーン対応（完全に異なるシーンからの画像）など、関連分野の多くの場面で重要な要素である。
概要.
対応問題とは、異なる視点から同じ3Dシーンを撮影した複数の画像が与えられたとき、画像間で同じ点として識別できる画像の点のセットを見つけることを指す。これを行うには、1つの画像の"点"または"特徴"を別の画像の点または特徴と照らし合わせ、対応点（英 : "corresponding points, homologous points"）または対応特徴（英 : "corresponding features, homologous features"）を確立する。ここで画像は、異なる視点や異なる時間、シーン内のオブジェクトがカメラに対して一般に動いている状態で撮影されているといった可能性が考えられる。
対応問題は、同じシーンを捉えた2つの画像が使用される「ステレオ」状況で起こる場合があり、またこれは、Nビュー対応問題に一般化することもできる。後者の場合、画像は同時に撮影しているN台の異なるカメラから、またはシーンに対して移動している1台のカメラから取得される。シーン内のオブジェクトがカメラに対して動いている場合、問題はさらに難しくなる。
対応問題の典型的な応用は、パノラマの作成または画像のスティッチング（重複部分がわずかしかない2つ以上の画像を大きな合成画像としてスティッチする作業）で行われる。この場合、一方の画像の変換を計算し他方の画像に貼り付けるために、画像間で対応する点のセットを識別できる必要がある。
基本的な方法.
2つの画像間の対応を見つけるには、2つの基本的な方法がある。
相関ベース – ある画像のある領域が別の画像の別の領域と似ているかをチェックする。
特徴ベース – 画像内の特徴を見つけ、特徴の集合の配置が2つの画像間で類似しているかどうかをチェックする。アパーチャ問題（英 : "aperture problem"）を回避するため、優れた特徴は2方向に局所的に変動する必要がある。
利用例.
コンピュータビジョンでは、コンピュータが画像のみを入力として自動的に解く必要がある場合の対応問題が研究されている。対応問題を解き、対応する画像上の点のセットが得られると、このセットを用いて他の方法を適用し、シーン内の対応する三次元点の位置や動きや回転を再構築（英 : "reconstruct"）できる。
対応問題は、流体力学の分野で流体運動を定量的に測定するために現在広く使用されている粒子画像流速測定技術の基礎でもある。
簡単な例.
セットA [1,2,3,4,5] とセットB [3,4,5,6,7] の間の対応を見つけるには、それらが重なっている場所と、一方のセットが他方のセットからどれだけ離れているかを見つける。ここで、セットAの最後の3つの数値がセットBの最初の3つの数値に対応していることがわかる。これは、BがAの左に2つ分オフセットされていることを示している。
簡単な相関ベースの例.
簡単な方法は、平行化された画像間の小さな部分を比較することである。これは、ほぼ同じ視点、あるいはほぼ同時、あるいはステレオ画像などの画像キャプチャ間でシーンがほとんどまたはまったく動かない画像に対して最適である。
小さな「窓」がある画像内の複数の位置に置かれる。各位置は他の画像の同じ位置とどの程度良く一致するかがチェックされる。付近のいくつかの箇所が比較されるが、これは他の画像の画像位置と全く異なる可能性がある。十分な一致率が得られない可能性がある。これは、対象物が両方の画像に存在しないか、検索対象よりも遠くに移動したか、変更が多すぎるか、画像の他の部分に隠れていることを意味している可能性がある。