(57)【要約】      （修正有）【課題】視点不変オブジェクトマッチングに用いるマンハッタンシーンをマッチングするためのグローバル記述子を提供する。【解決手段】記述子は、最初に、消失点１０１の周囲の角度領域を、事前に設定された数の角度量子化ビンに量子化することによって画像内の消失点に関連付けられ、各角度量子化ビンの重心は、その角度量子化ビンの方向を示す。各角度量子化ビンについて、ピクセル勾配の方向がその角度量子化ビンの方向と一致した画像内のピクセルのピクセル勾配の大きさの合計が求められる。これらのステップは、プロセッサ１５０において実行される。【選択図】図１
2015133101.tif 000002
【特許請求の範囲】
【請求項１】
シーンの画像の記述子を構成する方法であって、前記記述子は、画像内の消失点に関連付けられ、
前記方法は、
前記消失点の周囲の角度領域を事前に設定された数の角度量子化ビンに量子化するステップであって、各角度量子化ビンの重心は、前記角度量子化ビンの方向を示す、ステップと、
前記各角度量子化ビンについて、前記画像内のピクセルのピクセル勾配の大きさの合計と、前記角度量子化ビンの前記方向と一致した前記ピクセル勾配の方向とを求めるステップと、
を含み、
前記ステップは、プロセッサにおいて実行される、
シーンの画像の記述子を構成する方法。
【請求項２】
前記シーンは、マンハッタンワールド仮説を有するマンハッタンシーンである、
請求項１に記載の方法。
【請求項３】
前記角度量子化ビンは、一様である、
請求項１に記載の方法。
【請求項４】
前記角度量子化ビンは、前記ピクセル勾配の前記方向のクラスタリングによって求められ、
前記方向は、前記消失点のロケーションに関して測定される、
請求項１に記載の方法。
【請求項５】
前記ピクセル勾配は、各ピクセルにおいて個別に求められる、
請求項１に記載の方法。
【請求項６】
前記ピクセル勾配は、画像上でエッジ検出を実行してエッジ強度を求めるとともに、指定された百分位数の閾値よりも大きなエッジ強度を有する前記ピクセルのみの前記ピクセル勾配をピークとして決定するためのものである、
請求項１に記載の方法。
【請求項７】
前記勾配は、サブピクセルロケーションにおいて求められる、
請求項１に記載の方法。
【請求項８】
前記シーンの異なる視点から取得された２つの画像から構成された第１の記述子と第２の記述子とを比較するステップ、
を更に含む、請求項１に記載の方法。
【請求項９】
マッチングの品質を測定するメトリックを構成するステップ、
を更に含む、請求項８に記載の方法。
【請求項１０】
各画像の前記記述子から、指定された百分位数の閾値よりも大きなエッジ強度を有する前記ピクセルをピークとして識別するステップと、
所与のスケール及び変位の値に従ってクロスマッピングされた、前記第１の記述子から選ばれたピークの対が前記第２の記述子から選ばれたピークの対に対応するように、スケール−変位プロットを生成するステップと、
前記スケール−変位プロットにおいて１つ又は複数の極大値を識別するステップと、
各極大値における前記スケール及び変位の値を用いて２つの記述子を比較するステップと、
を更に含む、請求項８に記載の方法。
【請求項１１】
前記比較するステップは、
前記記述子の前記スケール及び前記変位が同一となるように各記述子を変更するステップと、
前記第１の記述子における前記ピークと前記第２の記述子における前記ピークとの差を求めるステップと、
前記差が閾値未満であるとき、前記２つの画像間の一致を宣言するステップと、
を更に含む、請求項１０に記載の方法。
【請求項１２】
前記差を求めるステップは、
前記第１の記述子及び前記第２の記述子における対応するピークについて、前記ピークの角度近傍における累積エッジ強度を計算するステップと、
前記ピークの前記角度近傍における前記エッジ強度の合計が１になるように前記累積エッジ強度を正規化するステップと、
前記第１の記述子の前記正規化された累積エッジ強度と前記第２の記述子の前記正規化された累積エッジ強度との間の距離を算出するステップと、
を更に含む、請求項１１に記載の方法。
【請求項１３】
前記記述子に基づいて画像のデータベースから類似の画像を取り出すステップ、
を更に含む、請求項１に記載の方法。
【請求項１４】
前記消失点のピクセルセットは、
【数１】
2015133101.tif 000016
であり、
ここで、前記画像内のロケーション（ｘ，ｙ）におけるピクセルの前記勾配の前記方向がψｇ（ｘ，ｙ）であり、
θｊ（ｘ，ｙ）は、前記消失点において水平基準ラインに対してなす角度であり、
τは、前記方向が前記消失点の前記方向と一致していない量に基づいて選択された閾値である、
請求項１に記載の方法。
【請求項１５】
【数２】
2015133101.tif 000017
であるような、角度範囲［θｍｉｎ，θｍａｘ］内のφｋ，１≦ｋ≦Ｋを中心とする所定の数（Ｋ）のビンに前記方向を量子化するステップ、
を更に含む、請求項１に記載の方法。
【請求項１６】
前記記述子は、
【数３】
2015133101.tif 000018
であり、
ここで、φｋ，１≦ｋ≦Ｋｊは、前記ビンの前記方向を表し、ｒは、範囲が半ピクセル解像度で変化する、
請求項１５に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、コンピュータービジョンに関し、より詳細には、視点不変オブジェクトマッチングに用いることができるマンハッタンシーンをマッチングするためのグローバル記述子に関する。
【背景技術】
【０００２】
視点不変オブジェクトマッチングは、回転、平行移動、照明、クロッピング、及びオクルージョン等の要因によって引き起こされる画像歪に起因して難しい。視覚的シーンの理解は、コンピュータービジョンにおいてよく知られた問題である。特に、２次元（２Ｄ）画像平面上への投影に基づく３Ｄシーン内のオブジェクトの識別は、手に負えそうもない課題を提起する。
【０００３】
人間の視覚野は、視野内の個々のオブジェクトを識別するために物理的なオブジェクト境界におけるエッジの存在に大きく依拠していることが知られている。エッジ、テクスチャ、及び色からの手がかりを用いて、脳は、通例、視点にかかわらず３次元（３Ｄ）シーンを視覚化して理解することができる。これとは対照的に、現代のコンピューターは、視覚野等の高レベルの処理アーキテクチャが欠如しているので、低レベルの視点不変性をシーン記述子内に明示的に組み込まなければならない。
【０００４】
シーンの理解のための方法は、２つの広い部類を含む。１つの部類は、回転、平行移動、及び他の視点の変化にかかわらず正確に検出することができるローカルなキーポイントに依拠したものである。この場合、視点の変化に対して不変のままである、勾配、テクスチャ、色、及び他の情報のローカルな構造を捕捉するために、それらのキーポイント用の記述子が構成される。スケール不変特徴変換（ＳＩＦＴ）及び高速化ロバスト特徴（ＳＵＲＦ）が、２つのキーポイントベースの記述子の例である。
【０００５】
もう１つの部類の方法は、グローバルスコープにおいて特徴を捕捉することを伴う。ローカルな平均化と、色及び勾配の分布の他の統計的な性質を用いることとによって正確さが得られる。このグローバルな手法は、勾配ヒストグラム（ＨＯＧ）及びＧＩＳＴ記述子において用いられる。
【０００６】
ローカルな手法及びグローバルな手法は、相補的な特徴を有する。ローカル記述子は、対応するローカルキーポイントにとっては正確かつ弁別的であるが、より大きなオブジェクトについてのグローバルな構造的手がかりが欠けており、それらのキーポイントに関連付けられた幾つかのローカル記述子間の対応関係を確立した後にしか推測することができない。グローバル記述子は、画像についての集約的な統計情報を捕捉する傾向があるが、シーンの理解に関係していることが多い特定の幾何学的手がかり又は構造的手がかりを含んでいない。
【０００７】
多くの人工シーンは、マンハッタンワールド仮説を満たす。この仮説では、ライン（ｌｉｎｅ：線）は、３つの主直交方向に沿って配向されている。マンハッタン幾何学の非常に重要な側面は、優性方向を有する全ての平行なラインが２Ｄ画像平面内の消失点において交差するということである。３つの直交方向が存在しない場合があるシーンでは、ラインは、例えば垂直若しくは水平な単一の優性方向を満たすことができるか、又は、例えば、室内の家具のオブジェクトといった複数の優性非直交方向を含むことができる。
【発明の概要】
【０００８】
本発明の実施の形態は、マンハッタンシーンのためのグローバル記述子を提供する。マンハッタンシーンは、通常は３つの直交方向に優性方向性配向を有する。したがって、優性方向にある３Ｄにおける全ての平行なエッジは、２Ｄ画像平面内の対応する消失点（ＶＰ）において例外なく交差する。全てのシーンエッジは、ＶＰから視認されるような相対的な空間ロケーション及び強度を保持する。グローバル記述子は、消失点の周囲のマンハッタンシーン内の画像エッジの空間ロケーション及び輝度に基づいている。本方法は、記述子当たり８キロビット及び画像当たり３つまでの記述子（各ＶＰにつき１つ）を用いて、ＳＩＦＴ等のローカルキーポイント記述子と比較して、マッチングするための効率的な記憶及びデータ転送を提供する。
【０００９】
方法が、画像を横断する平行なラインが消失点において交差するとき、それらのラインの角度順序（ａｎｇｕｌａｒ  ｏｒｄｅｒｉｎｇ）を厳密に維持することによってグローバル記述子を構成する。消失点で交わるこれらの平行なラインの相対的な長さ及び相対的な角度（配向又は方向）は、ほぼ同じである。
【００１０】
マンハッタンシーンのためのコンパクトなグローバル画像記述子は、消失方向に沿ったエッジの相対的なロケーション及び強度を捕捉する。この記述子を構成するために、エッジマップが消失点ごとに求められる。このエッジマップは、消失点について測定された角度又は方向の範囲にわたるエッジ強度を符号化する。
【００１１】
オブジェクトマッチングのために、２つのシーンからの記述子が、複数の候補のスケール及び変位にわたって比較される。マッチング性能は、ヒストグラムの形式のスケール−変位プロットの極大値におけるエッジ形状を比較することによって改良される。
【図面の簡単な説明】
【００１２】
【図１】本発明の実施形態によるグローバル記述子が構成される２つの消失点を含むマンハッタンシーンの画像を示す図である。
【図２】本発明の実施形態による、消失点ロケーションにおいて水平基準ラインに対してなす様々な角度、及び角度量子化ビンを示す概略図である。
【図３】本発明の実施形態によるエッジマップのビニングされたピクセル輝度の概略図である。
【図４】本発明の実施形態による建物の２つの異なるビューの角度ビンの図式化されたエッジ強度を示す図である。
【図５】本発明の実施形態によるグローバル記述子を構成するための方法の流れ図である。
【図６】本発明の実施形態による２つの画像のアフィン変換の概略図である。
【図７】本発明の実施形態によるスケール−変位プロット上のエッジ強度のヒストグラムである。
【図８】本発明の実施形態によるグローバル記述子を用いてオブジェクトをマッチングするための方法の流れ図である。
【図９】本発明の実施形態によるマッチングの品質を測定するためのメトリックを説明する図である。
【発明を実施するための形態】
【００１３】
本発明の実施形態は、マンハッタンシーン１００のためのグローバル記述子２５０を提供する。マンハッタンシーンは、通常は３つの直交方向に優性方向性配向を有し、或る優性方向にある３Ｄにおける全ての平行なエッジは、２Ｄ画像平面内の対応する消失点（ＶＰ１０１）で交差する。マンハッタンシーンは、屋内のものとすることもできるし、屋外のものとすることもでき、任意の数のオブジェクトを含むことができることに留意されたい。
【００１４】
記述子２５０は、カメラ１１０によって取得された画像１２０から構成される（５００）。これらの記述子は、次に、オブジェクトマッチング８００又は他の関連したコンピュータービジョンアプリケーションに用いることができる。これらの構成及びマッチングは、当該技術分野において知られているようにバスによってメモリ及び入力／出力インターフェースに接続されたプロセッサ１５０において実行することができる。
【００１５】
消失点ベースの画像記述子
記述子は、同じオブジェクトの複数の画像１２０（ビュー）についての以下の認識に基づいている。第１に、実際の３Ｄシーンにおける平行なラインは、それらのラインが消失点で交差するとき、２Ｄ画像にわたって（反転するまで（ｕｐ  ｔｏ  ａｎ  ｉｎｖｅｒｓｉｏｎ））それらの角度順序を厳密に維持する。第２に、消失点で交わる平行なラインの相対的な長さ及び相対的な角度は、ほぼ同じである。これらの認識は、記述子を構成するのに、消失方向に沿って配向されたエッジの相対的なロケーション及び強度を用いることができることを示唆している。記述子２５０を構成する（５００）こと、及びこれらの記述子をマッチングに用いることに関与するステップを以下に説明する。
【００１６】
各消失点における記述子のシーディング
消失点は、２Ｄ画像１００が入手可能である３Ｄシーンにおいて平行であるライン１０２を投影したものの交点として定義される。ＶＰは、３Ｄシーンにおける平行なラインによって与えられる方向の無限遠にある３Ｄ点の２Ｄ投影とみなすことができる。
【００１７】
一般に、平行なラインによって決定される複数のシーン方向に対応する多くの消失点が存在する。しかしながら、多くの人工の構造、例えば、都市景観は、規則的な立方形の幾何学的形状を有する。したがって、通常は３つの消失点が画像投影から得られ、これらのうちの２つが図１に示されている。
【００１８】
ＶＰは、コンピュータービジョンにおいて、画像修正、カメラ較正、及び関連した問題に用いられてきた。ＶＰの識別は、基礎となる３Ｄシーンにおける平行なラインがラベル付けされている場合には簡単であるが、ラベル付けが利用可能でないときはより難しくなる。消失点を求めるための方法には、エッジをＶＰに割り当てるための、エッジの凝集クラスタリング、１Ｄハフ変換、マルチレベルランダムサンプルコンセンサス（ＲＡＮＳＡＣ）ベースの手法、及び期待値最大化法（ＥＭ）が含まれる。
【００１９】
図２に示すように、ＶＰロケーション２００は、
【数１】
2015133101.tif 000003
によって示すことができる。ここで、通常、マンハッタンシーンの場合には、ｍ≦３である。さらに、ＶＰ
【数２】
2015133101.tif 000004
において水平基準ライン２０１に対してなす角度をθｊ（ｘ，ｙ）とする。したがって、
【数３】
2015133101.tif 000005
である。
【００２０】
記述子２５０は、各ＶＰに収束するエッジの相対的なロケーション及び強度を符号化することによって構成される。したがって、記述子は、関数Ｄ：Θ→Ｒ＋とみなすことができ、その定義域は、ＶＰに収束するエッジの角度配向を含み、その値域は、正しい順序によるこれらのエッジの強度の測定量を含む。記述子は、以下で説明する方法５００に従ってＶＰごとに求められる。
【００２１】
エッジロケーションの符号化
ライン検出手順は、多くの場合、途切れたライン及びクロッピングされたラインを生成し、重要なエッジを見つけ損ない、偽のラインを生成する。したがって、図３に示すように、正確さを得るために、画像エッジに適合するラインではなく、エッジピクセルの輝度を直接取り扱うことにする。消失点の周囲のエッジの角度ロケーションの関数としてのエッジ強度の表現は、エッジマップ３００と呼ばれる。具体的には、ピクセルが記述子を構成するための消失点に従って配向されていることを勾配が示すとき、図２に示すように、角度ビン２０２内のピクセルの輝度を記憶し、個別に合計する。これを行うために、図５に示すように、最初に、画像内のあらゆるピクセルについて、２Ｄベクトルである勾配ｇ（ｘ，ｙ）を求める（５１０）。
【００２２】
画像内のロケーション（ｘ，ｙ）におけるピクセルの勾配の方向ψｇ（ｘ，ｙ）５１１は、大きな輝度変化がそれに沿って存在する方向を指す。勾配の大きさ｜ｇ（ｘ，ｙ）｜５１２は、その勾配方向に沿ったそのピクセルにおける輝度差を指す。
【００２３】
次に、以下のように、消失点ＶＰ
【数４】
2015133101.tif 000006
のピクセルセットＰｊを求める（５２０）。
【数５】
2015133101.tif 000007
ここで、τは、勾配方向がＶＰの方向と一致していない量に基づいて選択された閾値である。このセットＰｊが求められると、基礎となるエッジロケーションは、以下のように符号化される。
【００２４】
ピクセル角度（方向）が、
【数６】
2015133101.tif 000008
であるような、画像にわたる角度範囲［θｍｉｎ，θｍａｘ］２０４内のφｋ，１≦ｋ≦Ｋを中心とする（２０３）一様な角度ビン２０２の事前に設定された数（Ｋ）に量子化され、そのため、角度量子化ビンの重心は、角度量子化ビンの方向、すなわち、ピクセル角度を示す。
【００２５】
エッジ強度の符号化
人間の視覚系に関する研究は、エッジの相対的な顕著さ（ｐｒｏｍｉｎｅｎｃｅ）が、弁別的なオブジェクトパターンを視覚化する際に役割を果たすことを示唆している。画像エッジの顕著さは、エッジの長さ、厚さ、及びエッジに対して垂直な方向の横変化（輝度及びフォールオフ特性）の関数である。
【００２６】
エッジ強度メトリックを構成する幾つかの方法がある。例えば、エッジ検出器が、特定のＶＰの記述子を構成するのに用いられる場合、強度は、エッジの長さ及びエッジに沿ったピクセル単位の累積勾配の関数とすることができる。しかしながら、上記で説明したように、エッジ検出器を用いることは、常に正確であるとは限らない。したがって、ピクセル単位の勾配のクラスタリング又は量子化に基づく方法が好ましい。このプロセスは、以下で詳細に説明する。
【００２７】
ピクセルセットＰｊが角度ビン２０２に一様に量子化されるとき、エッジ強度を符号化する１つの方法は、各角度量子化ビン内の勾配の大きさ｜ｇ（ｘ，ｙ）｜５１２の合計を求めることである。これを行うために、図２に示すように、端点（ｒｋ，ｍｉｎｃｏｓφｋ，ｒｋ，ｍｉｎｓｉｎφｋ）及び（ｒｋ，ｍａｘｃｏｓφｋ，ｒｋ，ｍａｘｓｉｎφｋ）を有するあらゆる角度量子化ビンの中央を通過するラインセグメント（ｌｉｎｅ  ｓｅｇｍｅｎｔ：線分）２０３を考える。
【００２８】
この場合、記述子２５０は、以下の総和となる。
【数７】
2015133101.tif 000009
ここで、φｋ，１≦ｋ≦Ｋｊは、ＶＰ
【数８】
2015133101.tif 000010
に対する量子化ビンに関連付けられた角度配向又は方向を表し、ｒは、半ピクセル（ｈａｌｆ−ｐｉｘｅｌ）解像度における範囲内で変化することができる。
【００２９】
正確さを得るために、双一次補間が、サブピクセルロケーションにおけるピクセル勾配を得るのに用いられる。記述子Ｄ（ｋ）２５０の構成５００は、サブピクセル解像度において実行される。各角度ビン内のエッジ強度を求めることによって上記のように得られた記述子の例が、図４において、同じ（建物）オブジェクト４０１の２つの異なるビューについて示されている。対応するグラフは、正規化された輝度の合計をビンインデックスの関数として示している。
【００３０】
構成方法
図５は、構成方法の基本的なステップを要約したものである。画像１２０内の各ピクセルについて、勾配の方向５１１及び大きさ５１２を求めることにする。次に、消失点と一致した方向を有する勾配のセット５２１が求められる。消失点は、最大３つ存在し得る。次に、各セットについて勾配の大きさが個別に合計され、エッジ強度として符号化されて（５３０）、各消失点の記述子２５０が得られる。
【００３１】
射影変換
グローバル記述子２５０を構成すること（５００）の背後にある本発明者らの動機は、異なる視点から取得された画像内のオブジェクトのマッチング８００を実行することである。各画像は、同じ実世界のシーンの２Ｄ投影であるので、画像の対における対応するキーポイント又はエッジ間には、通常、幾何学的な関係が存在する。例えば、構成しているものの平坦な正面の画像間にはホモグラフィー関係が存在する。本発明者らの認識は、同じオブジェクトの画像について求められた記述子Ｄ（ｋ）２５０間にアフィン対応関係が存在することを示唆している。
【００３２】
以下では、この認識が理論的正当性を有することを説明する。特に、記述子を構成している（５００）間のビニングステップにおいて用いられる画像ライン（エッジ）間の角度の変換が近似的にアフィンであることを示す。
【００３３】
図６に示すように、消失点を通過するラインの「束（ｐｅｎｃｉｌ）」からなる同じシーンの２つの画像（ビュー）を考える。第１のビューの消失点は原点に位置しているものとする。同種の表現を用いると、ｘ軸及びｙ軸は、ｅｘ＝（０１０）Ｔ及びｅｙ＝（１００）Ｔによって与えられる。ここで、Ｔは転置演算子である。これらのベクトルを用いると、任意のラインｌλは、以下のように表される。
【数９】
2015133101.tif 000011
ここで、λ∈Ｒである。
【００３４】
一般性を失うことなく、検討されている相互角（ｉｎｔｅｒ−ａｎｇｌｅ）は、ｘ軸とｌλとの間の角度であると仮定する。θλ＝ｔａｎ−１（−λ）であることに留意されたい。本発明者らの目標は、ｘ軸とｌλとの間の角度が、一方の画像から他方の画像へ近似的なアフィン変換を受けることを示すことである。これを示すために、２つのビュー間の３×３ホモグラフィーを、行列Ｈを用いて示すことにする。一般に、ホモグラフィーの下では、消失点は、もはや第２のビューの原点にはなく、Ｈｅｘは、もはやｘ軸に沿っていない。ここで、図６に示すように、消失点を平行移動させて原点に戻すとともにＨｅｘを回転させてｘ軸に戻す別の３×３行列Ｔによって与えられる変換を選ぶことにする。
【００３５】
ｌλのＴＨ変換をｌγによって示し、ｌγとｘ軸との間の角度をθγによって示すことにする。この場合、以下の式となる。
【数１０】
2015133101.tif 000012
ここで、
【数１１】
2015133101.tif 000013
であり、（ａ１，ａ２，ｂ１，ｂ２）は、Ｔ及びＨの要素から導出された変換パラメーターである。消失点が画像から遠く離れており、そのため、θｍａｘ−θｍｉｎが小さいという仮定の下では、テーラー級数近似ｔａｎ−１（α）≒αを用いることができる。ここで、αは、小さな角度（ラジアンで表される）である。したがって、以下の式となる。
【数１２】
2015133101.tif 000014
【００３６】
小さな相互角の仮定を用いると、２次の項θγθλは、無視できるほど小さくなる。この交差項を無視した場合、θλからθγへの変換は、近似的にアフィンとなる。
【００３７】
記述子マッチング
マンハッタンシーンにおけるオブジェクトは、３つのＶＰまで有することができ、したがって、３つの記述子まで有することができる。したがって、事前の配向情報なしで２つの視点から見えるオブジェクトをマッチングすることは、９対までのマッチング操作を伴う。上記で説明したように、角度エッジロケーションは、視点の変更を伴う近似的なアフィン変換を受ける。したがって、本発明者らは、マッチングされている記述子の対におけるエッジ強度の相対的な形状を比較する前にこの変換を反転することを提案する。この反転ステップは、幾つかの候補のスケール及び変位、すなわち、幾つかの候補のアフィン変換を用いて実行される。これらの候補のアフィン変換から、優性アフィン変換（スケール−変位）対を選ぶことができる。方法８００が、以下で説明するように記述子を比較するのに用いられる。
【００３８】
エッジに関する対応マッピング
視点間で記述子を平行移動させる近似的なアフィン変換を求めるために、正しい対応関係の下では、同一平面上のエッジの対は、スケール−変位対（ｓ，ｄ）によって与えられる近似値に等しいアフィンパラメーターを生成するということを利用する。したがって、エッジの対の（ｓ，ｄ）空間におけるハフ変換型投票手順の結果、真のスケールｓ＊及び変位ｄ＊における極大値が得られる。
【００３９】
複数の極大値は、オブジェクトが、ＶＰ方向軸によってサポートされた複数の平面を有するときに生じる。正確さ及び効率性を得るために、顕著なエッジが、それらのエッジ強度に基づいて識別される。指定された百分位数の閾値よりも大きな強度を有するエッジ上のピクセルが選択される。さらに、エッジオクルージョンに対する正確さを得るために、密接に近接した角度範囲内のエッジのみが票を投じるために対にされ、例えば、各顕著なエッジがＣ個の最も近いエッジと対にされる。
【００４０】
記述子Ｄ１（ｋ），１≦ｋ≦Ｋは、Ｎ１個のピーク対（ｋｉ、ｋ’ｉ），１≦ｉ≦Ｎ１のセットを生成することができる。同様に、Ｄ２（ｍ）は、Ｎ２個のピーク対（ｍｊ、ｍ’ｊ），１≦ｊ≦Ｎ２のセットを生成する。これらの識別されたピークの対は、２つのセット間でクロスマッピングされ、
【数１３】
2015133101.tif 000015
及びｄ＝ｍｊ−ｓｋｉを用いて（ｓ，ｄ）ヒストグラムの票が生成される。角度反転、すなわち、ＶＰの回りの上部／底部及び左／右の回転を可能にするために、上記２つのセットのうちの一方の中のピークの順序を逆にすることによって、追加の票が生成される。
【００４１】
図７に示すように、（ｓ，ｄ）票の粗いヒストグラム７００を、ここでは、極大値（ｓ＊，ｄ＊）を突き止めるのに用いることができる。このヒストグラムは、２つのＶＰベースの記述子が最良の一致を有するスケール及び変位を識別する。極大値は、オブジェクトの２つのビューにおけるエッジ間の関係を提供する。極大値が含む票が過度に少ない場合、その（ｓ＊，ｄ＊）対について不一致が宣言される。極大値のいずれもが十分な票を含んでいない場合、それらの記述子は同じオブジェクトを表していない。
【００４２】
したがって、各記述子は、それらの記述子のスケール及び変位が同一となるように変更される。次に、第１の記述子におけるピークの形状と第２の記述子における対応するピークの形状との差が求められ、この差が閾値未満であるとき、２つの画像間の一致を示すことができる。
【００４３】
マッチング方法
図８は、マッチング方法８００の基本的なステップを要約したものである。画像８０１及び８０２について、それぞれの記述子８１１及び８１２が、上記で説明したように構成される（５００）。ピーク８２１及び８２２が識別され（８２０）、ヒストグラム７００の票が生成される（８３０）。これらのピークは、２つのＶＰベースの記述子が最良の一致を有するスケール及び変位を識別する。
【００４４】
記述子は、類似したシーンの画像を取り出すために画像のデータベースへのクエリとして用いることができることにも留意すべきである。
【００４５】
対応するエッジにおける形状マッチング
各極大値（ｓ＊，ｄ＊）において、比較されている２つの記述子におけるエッジ強度プロット、例えば、図４のプロットのローカルな形状を利用して、マッチングプロセスを改良することができる。本質的には、スケーリングファクターｓ＊及び変位ｄ＊を補償した後、次に残っているものは、（ｓ＊，ｄ＊）に投票したエッジ対の近傍におけるエッジ強度プロットの形状を比較することである。これを行う方法は幾つかある。以下に１つの実施形態を説明する。
ａ）図９に示すように、一致の品質を測定するためのメトリックを構成するために、各顕著なピークについて以下のステップを実行する。
ｂ）第１の記述子のピークの角度近傍における領域を考える。
ｃ）この近傍における累積エッジ強度ベクトルを求め、全てのエッジ強度の合計が１になるようにこのベクトルを正規化する。
ｄ）第２の記述子における各マッチングする顕著なピークについて、このプロセスを繰り返す。
ｅ）各記述子から１つずつ取られたマッチングするピークの各対について、正規化された累積エッジ強度ベクトル間の絶対距離を求める。
ｆ）ステップ（ｄ）で得られた絶対距離が、場合によっては複数のビンから生成された全てのマッチングするピーク対にわたって平均化され、閾値と比較される。
ｇ）正規化された累積エッジ強度ベクトル間の平均距離が上記閾値未満である場合、２つの記述子間の一致が宣言される。
【図１】
2015133101.tif 000019
【図２】
2015133101.tif 000020
【図３】
2015133101.tif 000021
【図４】
2015133101.tif 000022
【図５】
2015133101.tif 000023
【図６】
2015133101.tif 000024
【図７】
2015133101.tif 000025
【図８】
2015133101.tif 000026
【図９】
2015133101.tif 000027
【外国語明細書】
2015133101.tif 000028
2015133101.tif 000029
2015133101.tif 000030
2015133101.tif 000031
2015133101.tif 000032
2015133101.tif 000033
2015133101.tif 000034
2015133101.tif 000035
2015133101.tif 000036
2015133101.tif 000037
2015133101.tif 000038
2015133101.tif 000039
2015133101.tif 000040
2015133101.tif 000041
2015133101.tif 000042
2015133101.tif 000043
2015133101.tif 000044
2015133101.tif 000045
2015133101.tif 000046
2015133101.tif 000047
2015133101.tif 000048
2015133101.tif 000049
2015133101.tif 000050
2015133101.tif 000051
2015133101.tif 000052
2015133101.tif 000053
2015133101.tif 000054
2015133101.tif 000055
2015133101.tif 000056