JP2011113197A - 画像検索方法およびシステム - Google Patents

Abstract

【課題】窓や柱などの同一形状物を多数備える建物画像のように、似通った形状物を多く備える被写体の画像を比較する場合でも対応点を正確に識別できる画像検索方法およびシステムを提供する。
【解決手段】図１０(a)のクエリ画像Iqおよび図１０(b)の類似画像候補（街並画像）Iwcのペアからは２組の対応点候補[q1，w1]および[q2，w2]が抽出されている。一方の対応点候補[q1，w1]については、クエリ画像Iq側の対応点q1の縦位置が出現パターン[N1-N2-N3…]のN1の位置であるのに対して、類似画像候補Iwc側の対応点w1はN3の位置であり、両者はズレ量が多いので破棄される。他方の対応点候補[q2，w2]については、クエリ画像Iq側の対応点q1の縦位置が出現パターン[N1-N2-N3…]のN2の位置であり、類似画像候補Iwc側の対応点w2も同様にN2の位置であり、両者は距離が近いので対応点とされる。
【選択図】図１０

Description

本発明は、クエリ画像に類似した画像を多数の検索対象画像の中から検索する画像検索方法およびシステムに係り、特に各画像の局所特徴量同士を比較して画像間の類似性を判断する画像検索方法およびシステムに関する。

建物などの剛体を撮影した画像をロバストに検出する手法の一つとして、非特許文献１にSIFT(Scale Invariant Feature Transform)が開示されている。このSIFTでは、クエリ画像および検索対象画像の双方から予め局所特徴量が抽出され、各画像の局所特徴量間のユークリッド距離Lに基づいて最近傍探索が実行される。そして、距離の近い局所特徴量同士が対応点ペアとされ、最終的に対応点ペアの多い検索対象画像が検索結果とされる。

David G. Lowe，"Distinctive image features from scale-invariant keypoints" International Journal of Computer Vision, 60, 2 (2004), pp.91-110.

建築構造物、特にビルディングのように窓、柱あるいは壁などの直線を基調とする構成要素が一様に組み合わされる建物の画像では、これら構成要素の形状に建物間でのオブジェクト相違が小さい。したがって、異なる建物の画像同士を比較した場合でも、窓部等の局所特徴量は近い値を示してしまい、個々の対応点が実際に正しい対応点を示さない場合があった。すなわち、建物画像同士の比較では建物以外の画像同士を比較する場合に較べて対応点を誤認する場合があった。

また、対応点の一部が誤認であっても、同一の建物画像間での誤認であれば、対応点に基づいてクエリ画像と同一の建物を含む類似画像を検索対象の中から検索できる場合がある。しかしながら、検索結果の類似画像からクエリ画像の撮影位置すなわちユーザ位置を各対応点に基づいてさらに特定しようとすると、誤認された対応点の影響により撮影位置を正確に推定することができないことがあった。

本発明の目的は、上記した従来技術の課題を解決し、窓や柱などの同一形状物を多数備える建物画像のように、似通った形状物を多く備える被写体の画像を比較する場合でも対応点を高い確度で識別できる画像検索方法およびシステムを提供することにある。

上記の目的を達成するために、本発明は、クエリ画像に類似した画像を検索対象画像の集合から検索する画像検索システムにおいて、以下のような手段を講じた点に特徴がある。

(1)クエリ画像および各検索対象画像を、その被写体の平行成分が画像上でも平行となるように幾何変換する手段と、クエリ画像および各検索対象画像の特徴点から局所特徴量を抽出する局所特徴量抽出手段と、クエリ画像および検索対象画像の各特徴点から抽出した局所特徴量を比較し、類似度が上位の特徴点を対応点候補として抽出する対応点候補抽出手段と、幾何変換されたクエリ画像および検索対象画像からエッヂ成分を抽出する手段と、クエリ画像および各検索対象画像からエッヂ成分の出現パターンを検出する手段と、エッヂ成分の出現パターンに基づいて、前記対応点候補から対応点を抽出する対応点抽出手段と、抽出された対応点に基づいて、クエリ画像に類似した検索対象画像を決定する類似画像決定手段とを具備したことを特徴とする。

(2)対応点候補抽出手段は、クエリ画像の特徴点ごとに、各検索対象画像から類似度が上位Nベストの特徴点を抽出する手段と、Nベスト特徴点の局所特徴量をクエリ画像の対応する特徴点の局所特徴量と比較し、局所領域のスケールおよびオリエンテーションの差分で定義されるプロットの分布を算出する手段と、プロットの分布に基づいて、対応点としての尤度が高い複数の特徴点ペアを対応点候補として抽出する手段とを具備し、各プロットには、クエリ画像および各検索対象画像の各特徴点の局所特徴量の類似度に応じた重み値が付与されていることを特徴とする。

本発明によれば、以下のような効果が達成される。

(1)クエリ画像および各検索対象画像から抽出したエッジ成分に基づいてクエリ画像および各検索対象画像のエッヂ成分に関する出現パターンを検出し、この出現パターンに基づいて、各対応点候補のクエリ画像Iq側の位置と検索対象画像Iw(k)側の位置とのズレ量を算出し、ズレ量が小さい対応点候補のみが真の対応点とされるようにしたので、対応点以外を対応点と判定してしまう誤りを防止できるようになる。

(2)クエリ画像Iqおよび各検索対象画像Iwからエッヂ成分に関する出現パターンを検出する前に、クエリ画像Iqおよび各検索対象画像Iwに対して、その被写体の平行成分が画像上でも平行となるように幾何変換するようにしたので、エッヂ成分に関する出現パターンの検出精度を向上させることができる。

(3)クエリ画像Iqの各特徴点と局所特徴量が類似したNベストの特徴点を各検索対象画像から抽出する際、各画像の特徴点間の局所特徴量に関する類似性を「オリエンテーションの角度差」および「スケール比」の２つのパラメータで定義されるプロットの分布で表すと共に、各プロットに各局所特徴量間の類似度に関するユークリッド距離に依存した重み値を付与するようにしたので、局所特徴量間の類似性を前記プロットの分布から正確に求められるようになる。

本発明の画像検索システムを適用した位置案内システムのブロック図である。 対応点抽出部３０４のブロック図である。 相違分布の算出方法を模式的に示した図である。 相違分布の一例を示した図である。 対応点候補の抽出方法の一例を示した図である。 対応点候補の抽出方法の他の一例を示した図である。 画像補正部４０７による幾何変換を説明するための図である。 領域分割部４０８による領域分割を説明するための図である。 エッジ出現パターンの検出方法を示した図である。 エッジ出現パターンに基づく対応点候補の評価方法を示した図である。 本発明の一実施形態の動作を示したメインフローである。 対応点候補抽出処理の手順を示したフローチャートである。 対応点抽出処理の手順を示したフローチャートである。

以下、図面を参照して本発明の実施形態について詳細に説明する。図１は、本発明の画像検索システムが適用される位置案内システムの主要部の構成を示したブロック図であり、ここでは、本発明の説明に不要な構成は図示が省略されている。

位置案内システムは、車両等の移動体に搭載されて街並みを全方位カメラで撮影する撮影装置１と、撮影された静止画像から検索対象となる多数の街並画像Iwを生成し、さらに各街並画像Iwから局所特徴量fwを抽出してデータベース化すると共に、ユーザ端末２で撮影された目印画像（クエリ画像Iq）に類似した街並画像Iwを前記データベースから検索する画像検索部３と、クエリ画像Iqに最も類似した街並画像Iw(best)に基づいてユーザの現在位置を推定し、これをユーザ端末２へ応答する位置推定部４とを主要な構成としている。

前記撮影装置１において、全方位カメラ１０１は多数の撮像部を備えて全方位の静止画像を撮影する。位置検知部１０２は、撮影タイミングの現在位置（撮影位置）を、例えば複数のGPS信号により測位する。撮影された各静止画像は、その撮影位置の情報と紐付けられて画像蓄積部１０３に次々と蓄積される。なお、例えばGoogle マップのストリートビューのように、街並画像Iwを撮影して構築された外部のデータベースを利用できるならば、前記撮影装置１に代えて、このような既存の外部データベースから街並画像を取得するようにしても良い。

画像検索部３において、街並画像生成部３０１は、前記全方位カメラ１０１で撮影された多数の静止画像に基づいてパノラマ画像を生成し、このパノラマ画像から所定の規則で多数の画像を街並画像Iw(k)として切り出す。符号kは各街並画像Iwの識別子である。

局所特徴量抽出部３０２は、クエリ画像Iqおよび各街並画像Iw(k)の各特徴点i，jを基準にして局所特徴量fq(i)，fw(k,j)を抽出する。本実施形態では、SIFTを利用して特徴点の抽出および対応付けが行われる。局所領域の特定には、非特許文献１に開示されているDifference of Gaussian (DoG)によるスケールスペース内の極値に基づく特徴点抽出が用いられる。この特徴点抽出の結果、特徴点の位置およびその局所領域の範囲（スケール）が算出され、この局所領域の特徴記述子として、輝度勾配の方向ヒストグラムが用いられる。

このような方向ヒストグラムは、特徴領域の各ピクセルの輝度勾配を算出し、それに重みを付けてヒストグラムを生成し、最も多いbin領域の方向を基準にして、その方向に特徴領域の回転（オリエンテーション）を行い、再度輝度方向の方向ヒストグラムを作成し、さらに前記ヒストグラムをブロックに分割し、各ブロック内で方向ヒストグラムを算出し、これを正規化してベクトル化することにより得られる。本実施形態では、ブロック内の輝度方向を８方向、対象領域内を１６分割しているため、一つの特徴記述子は８＊１６＝１２８次元となる。

これら特徴記述子の特徴として、局所領域の特徴を生成するのでオクルージョンに耐性があり、特徴点に対してスケールを決定するので画像サイズに不変であり、また輝度勾配に基づき画像平面内でオリエンテーションを行うので、画像平面に対する回転に不変であることなどが挙げられる。さらに、エッヂ成分を利用しているので輝度変化に耐性がある。このような特徴点検出が画像の全てのピクセルに対して行われるが、ある特徴点が極値を取った場合でも特徴点として不適な場合は特徴領域から除外される。

本実施形態では、クエリ画像Iqの各局所特徴量fq(i)が次式(1)で表される。pq(i)は同次座標で表した特徴点の位置、op(i)は特徴点のオリエンテーション、σq(i)は特徴点が発見されたスケール、dq(i)は特徴記述子であり、符号iはクエリ画像Iqの特徴点識別子である。

fq(i)＝｛pq(i)，op(i), σq(i)，dq(i)｝ ・・・(1)

同様に、各街並画像Iw(k)の局所特徴量fw(k,j)は次式(2)で表される。pw(k,j)は同次座標で表した特徴点の位置、ow(k,j)は特徴点のオリエンテーション、σw(k,j)は特徴点が発見されたスケール、dw(k,j)は特徴記述子であり、符号jは街並画像Iw(k)の特徴点識別子である。

fw(k,j)＝｛pw(k,j)，ow(k,j),σw(k,j)，dw(k,j)｝ ・・・(2)

このようにして抽出された局所特徴量fw(k,j)は、その街並画像Iw(k)と共に画像データベース３０３に蓄積される。

対応点抽出部３０４は、後に詳述するように、クエリ画像Iqの各局所特徴量fq(i)を各街並画像Iw(k)の各局所特徴量fw(k,j)と比較して対応点候補を求めると共に、この対応点候補の数に基づいて各街並画像Iw(k)から類似画像候補Iwc(k)を抽出し、さらに各類似画像候補Iwc(k)の対応点候補を、クエリ画像Iqおよび各類似画像候補Iwc(k)の幾何拘束の条件に基づいて尤度の高い真の対応点まで絞り込む。
類似画像決定部３０５は、対応点が最も多い各類似画像候補Iwc(k)を抽出し、これを検索結果Iw(best)として出力する。あるいは更に、前記抽出された複数の対応点を利用して射影変換を行い、このうち、射影変換できた対応点の個数が最も多い各類似画像候補Iwc(k)を検索結果Iw(best)とするようにしても良い。

位置推定部４は、クエリ画像Iqおよび当該クエリ画像Iqに最も類似する街並画像Iw(best)に基づいてユーザの撮影位置および撮影方向を推定し、これをユーザ端末２へ応答する。

図２は、前記対応点抽出部３０４の主要部の構成を示したブロック図であり、前記と同一の符号は同一または同等の内容を示している。

検索範囲絞込部４０１は、ユーザ端末２のGPSシステムにより測位されているユーザの現在位置に基づいて街並画像Iw(k)の検索範囲を予め絞り込む。Nベスト抽出部４０２は、クエリ画像Iqの各特徴点の局所特徴量と前記検索範囲内の全ての街並画像Iw(k)の各特徴点の局所特徴量とを比較し、クエリ画像Iqの特徴点ごとに、各街並画像Iw(k)から局所特徴量の類似度が高い上位N個の特徴点をNベスト特徴点として抽出する。したがって、クエリ画像Iqにm個の特徴点が設定されていれば、(m×N)個のNベスト特徴点が、前記検索範囲内の街並画像Iw(k)から抽出されることになる。

本実施形態では、クエリ画像Iqの各特徴点について、全ての街並画像Iw(k)の各特徴点を対象に局所特徴量の最近傍探索が行われ、街並画像Iw(k)ごとに、局所特徴量間の距離に基づいて類似度が算出される。本実施形態では、各特徴点の局所特徴量fq(i)，fw(k,j)間の類似度が、次式(3)で与えられる各特徴記述子dq(i)，dw(k,j)間のユークリッド距離Lで代表される。

L＝|dq(i)−dw(k,j)| ・・・(3)

相違分布算出部４０３は、Nベスト特徴点の局所特徴量をクエリ画像Iqの対応する特徴点の局所特徴量と比較し、各局所領域の相違に関する分布を算出する。本実施形態では、初めに局所領域のスケール比（または差）、およびオリエンテーションの角度差（または角度比）に関する分布が算出される。

次いで、図３に一例を示したように、Nベスト特徴点ごとに、その局所特徴量とクエリ画像Iqの対応する局所特徴量との局所領域（スケール）のサイズ比およびオリエンテーションの角度差を算出して対応付け、これを全てのNベスト特徴点について実施して仮想的な二次元空間上にプロットすることにより、図４に一例を示した相違分布を算出する。
なお、本実施形態では各プロットに前記ユークリッド距離Lに基づく重み値が設定されている。すなわち、前記ユークリッド距離Lの短いNベスト特徴点ほど大きな重み値が付与される。図４に示した例では、各プロットの重み値が便宜的にプロットの大きさで代表されている。
図２へ戻り、対応点候補抽出部４０４は、前記相違分布に基づいて、対応点としての尤度が高い複数の対応点候補を抽出する。

図５は、対応点候補の抽出方法の一例を示した図であり、本実施形態では、分布密度の最も高い位置を中心に所定の範囲内に存在するNベスト特徴点が対応点候補とされ、それ以外のNベスト特徴点はノイズとして除去される。なお、前記分布密度に基づいて対応点候補を抽出する方法は上記に限定されるものではなく、図６に一例を示したように、前記相違分布をクラスタリングし、各クラスタから大きく外れるNベスト特徴点を除去し、残りを対応点候補とするようにしても良い。

図２へ戻り、類似画像候補抽出部４０５は、対応点候補の多い上位M個の街並画像Iwを類似画像候補Iwcとして抽出する。正規化部４０６は、各類似画像候補Iwc(k)の大きさを、その対応点候補の局所特徴量fwc(k)のスケール比等に基づいて正規化する。
画像補正部４０７は、各類似画像候補Iwc(k)およびクエリ画像Iqから水平成分および垂直成分を抽出し、各成分に基づいて消失点を抽出することで撮影の視点方向を求めると共に、この視点方向に基づいて、被写体の平行線が画像上でも平行となるように各画像に幾何変換を実施する。これ以後、幾何変換により被写体の平行線が画像上でも平行とされている画像を「平面化画像」と表現する場合もある。

図７は、前記画像補正部４０７において、被写体の平行線が画像上でも平行となるようにクエリ画像Iqおよび各類似画像候補Iwc(k)に対して実行される幾何変換を説明するために図であり、同図(a)は幾何変換の対象となる原画像を示している。

本実施形態では、初めにクエリ画像Iqおよび各各類似画像候補Iwc(k)を対象に、Canny法[J. Canny:"A computational approach to edge detection,"IEEE Transactions on Pattern Analysis and Machine Intelligence, 8(6), November 1986]を適用することでエッヂが検出される。次いで、前記検出されたエッヂを対象にHough変換[Duda, R. O. and P. E. Hart, "Use of the Hough Transformation to Detect Lines and Curves in Pictures," Comm. ACM, Vol. 15, pp. 11-15 (January, 1972).]が実行され、同図(b)に示したように垂直成分および水平成分のエッヂが抽出される。

次いで、無限平面を有限の変形領域に変換する消失点抽出方法[松藤，齋藤：" 無限平面内での消失点抽出，"情報処理学会研究報告，Vol.99, No.70, pp.25-30, 1999]に基づいて、同図(c)に示したように消失点が求められる。次いで、この消失点に基づいて撮影時の視点方向が求められ、この視点方向に基づいて各画像が幾何変換されることにより、同図(d)に示したように、被写体の平行線が画像上でも平行な平面化画像が得られる。

領域分割部４０８は、クエリ画像Iqおよび各類似画像候補Iwc(k)を領域分割し、画像認識に不適な領域を予め検索対象から除外する。図８は、前記領域分割部４０８による領域分割の様子を示した図であり、本実施形態では、(1)道路領域の白線、(2)車や樹木などの移動体あるいは形態が変化する物体、のように、対応点検出に悪影響を及ぼす物体の領域が、同図(a)の原画像から予め除外される。

本実施形態では、初めに学習用の街並画像に対して手動で領域のラベリングが行われ、画像内の各領域が、例えば建物・空・道路・車・人・植物といった複数のカテゴリに分類される。次いで、各領域内のSIFT特徴点を利用して学習が行われ、この学習データを利用して、クエリ画像Iqおよび各類似画像候補Iw(k)が複数のブロックに分割されると共に、各ブロックがいずれかのカテゴリに分類される。この学習には、例えばSVM(Support Vector Machine)を利用できる。このような領域分割により、同図(b)に示したように、移動体や季節によって変化する物体、あるいは似たような形状が多い道路の白線などの、対応点検出に悪影響を及ぼす物体の領域が検索対象から予め除外され、四角枠で示した領域のみが検索対象とされることになる。
エッヂ検出部４０９は、クエリ画像Iqおよび各類似画像候補Iwc(k)からエッヂ成分を検出する。垂直エッヂ抽出部４１０は、各エッヂ成分から垂直エッヂを抽出する。エッヂ出現パターン検出部４１１は、クエリ画像Iqおよび各類似画像候補Iwc(k)の垂直エッヂの出現パターンを検出する。

対応点抽出部４１２は、対応点候補が抽出されているクエリ画像Iqおよび類似画像候補Iwc(k)の画像ペアについて、各対応点候補のクエリ画像側の位置と類似画像候補側の位置とのズレ量を、各画像の垂直エッヂの出現パターンに基づいて算出するズレ量算出部４１２ａを具備し、このズレ量の算出結果に基づいて、前記対応点候補から真の対応点を抽出する。

図９は、前記エッヂ検出および垂直エッヂ抽出により得られた垂直エッヂの一例を示した図であり、窓が配置されている領域では多数の垂直エッヂが検出されている。このような垂直エッヂの出現パターンは各建物に固有なので、本実施形態ではクエリ画像Iqおよび各類似画像候補Iwc(k)に関して、前記エッヂ出現パターン検出部４１１により、所定の単位間隔で垂直エッヂ数Nxが計数され、さらに垂直エッヂの出現パターン[N1-N2-N3-N4…]が検出される。

前記対応点抽出部４１２は、クエリ画像Iqおよび各類似画像候補Iwc(k)のエッヂ出現パターンに基づいて各画像間の相対的な位置関係を把握し、各対応点候補のズレ量を検出する。そして、ズレ量の小さい対応点候補を真の対応点とする一方、ズレ量の多い対応点候補を誤対応として破棄する。

図１０は、前記垂直エッヂの出現パターンに基づいて対応点候補を評価し、真の対応点を抽出する方法を説明するための図であり、同図(a)はクエリ画像Iqの一例を示しており、同図(b)は当該クエリ画像Iqとの間で対応点候補が抽出されている類似画像候補Iwc(k)の一例を示している。ここでは、図面を見やすくするために垂直エッヂの表示が省略されている。

図１０では、対応点候補が抽出されているクエリ画像Iqおよび類似画像候補Iwcのペア（以下、対応画像ペアと表現する場合もある）間で２組の対応点候補[q1，w1]および[q2，w2]が抽出されている。そして、一方の対応点候補[q1，w1]については、クエリ画像Iq側の対応点q1の縦位置が出現パターン[N1-N2-N3-N4…]のN1の位置であるのに対して、類似画像候補Iwc側の対応点w1の縦位置は出現パターン[N1-N2-N3-N4…]のN2〜N3の位置であり、両者はズレ量が多いので破棄される。

これに対して、他方の対応点候補[q2，w2]については、クエリ画像Iq側の対応点q1の縦位置が出現パターン[N1-N2-N3-N4…]のN2の位置であり、類似画像候補Iw側の対応点w2の縦位置も同様に出現パターン[N1-N2-N3-N4…]のN2の位置であり、両者は距離が近いので対応点とされる。

図１へ戻り、類似画像決定部３０５は、以上のようにして抽出された真の対応点が最も多い類似画像候補Iwc(k)を抽出し、これを検索結果Iw(best)として出力する。あるいは更に、前記抽出された複数の対応点を利用して射影変換を行い、このうち、射影変換できた対応点の個数が最も多い類似画像候補Iwc(k)を検索結果Iw(best)とするようにしても良い。

前記位置推定部４は、前記検索結果の街並画像Iw(best)と類似する街並画像を前記データベース３０３から抽出する。本実施形態では、検索対象の街並画像が道路に沿って離散的に撮影されているので、街並画像Iw(best)の両隣の街並画像Iw(best-1)，Iw(best+1)のうち、前記街並画像Iw(best)により類似する一方（ここでは、例えばIw(best-1)がデータベース３０３から抽出される。次いで、これら２つの画像Iq，Iw(best-1)の対応点が上記と同様に検出されてエピポーラ拘束が算出され、撮影位置が既知の２枚の画像Iq，Iw(best-1)から特徴点の３次元位置が推定される。

未知の空間上の点X を画像Iw(best)に射影した点x = [u v 1]^T と画像Iw(best-1)に射影した点x'= [u' v' 1]^T とには次式(4)の関係が成立する。

x^TFx'= 0 … (4)

これはエピポーラ拘束と呼ばれ、F は基礎行列である。上記関係に基づいて街並画像のデータベース内での対応点の３次元位置が推定されたのち、クエリ画像Iqと街並画像Iw(best)とに関しても同様に対応関係が算出され、これに基づいてユーザ位置が推定される。

次いで、フローチャートを参照して本発明の一実施形態の動作を詳細に説明する。図１１は、本発明の一実施形態の動作を示したメインフローであり、主に前記対応点抽出部３０４の動作を示している。

ステップＳ１では、ユーザ端末２からクエリ画像Iqと共に受信されている当該ユーザ端末２の現在位置に基づいて、前記検索範囲絞込部４０１により街並画像Iwの検索範囲がユーザ位置近傍に予め絞り込まれる。ステップＳ２では、前記Nベスト抽出部４０２により、クエリ画像Iqの各特徴点の局所特徴量と各街並画像Iw(k)の各特徴点の局所特徴量とがクエリ画像Iqおよび街並画像Iw(k)の組み合わせ毎に比較され、クエリ画像Iqの特徴点ごとに、局所特徴量が類似するNベストの特徴点が各街並画像Iw(k)から抽出される。ステップＳ３では、前記Nベスト特徴点の中から対応点候補が抽出される。

図１２は、前記対応点候補の抽出手順を示したフローチャートであり、主に前記違分布算出部４０３および対応点候補抽出部４０４の動作を示している。

ステップＳ１０１では、前記検索範囲内の街並画像Iw(k)の一つが今回の注目画像として選択される。ステップＳ１０２では、今回の街並画像Iwから抽出されているNベスト特徴点の一つに注目し、これに対応するクエリ画像Iqの特徴点が取得される。ステップＳ１０３では、前記取得された各特徴点の局所特徴量同士が比較され、そのサイズ比およびオリエンテーションの角度差が算出される。ステップＳ１０４では、前記図３を参照して説明したように、今回のNベスト特徴点が、前記サイズ比およびオリエンテーション角度差に基づいて仮想的な二次元空間にプロットされる。

ステップＳ１０５では、今回の街並画像Iwから抽出されている全てのNベスト特徴点に関して上記のプロットが完了したか否かが判定される。完了していなければステップＳ１０２へ戻り、残りのNベスト特徴点について同様の手順が繰り返される。

全てのNベスト特徴点に関してプロットが完了し、前記図４の相違分布が完成するとステップＳ１０６へ進み、分布密度の最大位置が検出（図５）され、あるいはクラスタリングが実施（図６）される。ステップＳ１０７では、前記分布密度に基づいて所定の範囲内のNベスト特徴点が対応点候補とされ、それ以外のNベスト特徴点は誤対応のノイズとして破棄される。

図１１へ戻り、ステップＳ４では、前記類似画像候補決定部４０５において、対応点候補が多い上位M個の街並画像Iw(k)が抽出され、これが類似画像候補Iwcとして出力される。ステップＳ５では、前記M個の類似画像候補Iwcを対象に改めて対応点探索が実行され、真の対応点が抽出される。

図１３は、前記M個の類似画像候補Iwcから真の対応点を抽出する処理の手順を示したフローチャートであり、主に前記対応点抽出部４１２の動作を示している。

ステップＳ２０１では、類似画像候補Iwcの一つが今回の注目画像として選択される。ステップＳ２０２では、今回の注目画像Iwcから抽出されている対応点候補の一つが今回の注目候補として選択される。ステップＳ２０３では、今回の注目画像Iwcの対応点候補の一つと当該対応点候補と対応するクエリ画像Iq側の特徴点とのズレ量が、前記エッヂ出現パターン検出部４１１により別途に検出されているエッヂ出現パターンに基づいて検出される。ステップＳ２０４では、前記ズレ量の算出結果が所定の許容範囲内であるか否かが判定され、許容範囲外であればステップＳ２０５へ進み、誤対応点と判定されて破棄される。

ステップＳ２０６では、今回の注目画像Iwcから抽出されている全ての対応点候補に関して上記の処理が完了したか否かが判定される。完了していなければステップＳ２０２へ戻り、注目する対応点候補を切り替えながら上記の処理が繰り返される。今回の注目画像Iwcの全ての対応点候補に関して上記の処理が完了するとステップＳ２０７へ進み、破棄されることなく残っている全ての対応点候補が真の対応点とされる。ステップＳ２０８では、全ての類似画像候補Iwcに関して上記の処理が完了したか否かが判定され、完了していなければステップＳ２０１へ戻り、注目する類似画像候補Iwcを切り替えながら上記の各処理が繰り返される。

前記類似画像決定部３０５は、対応点が最も多い類似画像候補Iwc(k)を抽出し、これを検索結果Iw(best)として出力する。あるいは更に、前記抽出された複数の対応点を利用して射影変換が行われ、このうち、射影変換できた対応点の個数が最も多い類似画像候補Iwc(k)が検索結果Iw(best)として出力される。

１…撮影装置，２…ユーザ端末，３…画像検索部，４…位置推定部，１０１…全方位カメラ，１０２…位置検知部，１０３…画像蓄積部，３０１…街並画像生成部，３０２…局所特徴量抽出部，３０３…データベース，３０４…対応点抽出部，３０５…類似画像決定部，４０１…検索範囲絞込部，４０２…Nベスト抽出部，４０３…相違分布算出部，４０４…対応点候補抽出部，４０５…類似画像候補抽出部，４０６…正規化部，４０７…画像補整部，４０８…領域分割部，４０９…エッヂ検出部，４１０…垂直エッヂ抽出部，４１１…エッヂ出現パターン検出部，４１２…対応点抽出部

Claims (5)

1. クエリ画像に類似した画像を検索対象画像の集合から検索する画像検索システムにおいて、
   クエリ画像および各検索対象画像の特徴点から局所特徴量を抽出する局所特徴量抽出手段と、
   クエリ画像および各検索対象画像を、その被写体の平行成分が画像上でも平行となるように幾何変換する手段と、
   前記クエリ画像および検索対象画像の各特徴点から抽出した局所特徴量を比較し、類似度が上位の特徴点を対応点候補として抽出する対応点候補抽出手段と、
   前記幾何変換されたクエリ画像および検索対象画像からエッヂ成分の出現パターンを検出する手段と、
   対応点候補が抽出されているクエリ画像および検索対象画像のペアについて、各対応点候補のクエリ画像側の位置と検索対象画像側の位置とのズレ量を、各画像のエッヂ成分の出現パターンに基づいて算出する手段と、
   前記ズレ量の算出結果に基づいて、前記対応点候補から対応点を抽出する対応点抽出手段と、
   前記抽出された対応点に基づいて、クエリ画像に類似した検索対象画像を決定する類似画像決定手段とを具備したことを特徴とする画像検索システム。
2. 前記対応点候補抽出手段は、
   クエリ画像の特徴点ごとに、各検索対象画像から類似度が上位Nベストの特徴点を抽出する手段と、
   前記Nベスト特徴点の局所特徴量をクエリ画像の対応する特徴点の局所特徴量と比較し、局所領域のスケールおよびオリエンテーションの差分で定義されるプロットの分布を算出する手段と、
   前記プロットの分布に基づいて、対応点としての尤度が高い複数の特徴点ペアを対応点候補として抽出する手段とを具備し、
   前記各プロットには、クエリ画像および各検索対象画像の各特徴点の局所特徴量の類似度に応じた重み値が付与されていることを特徴とする請求項１に記載の画像検索システム。
3. 前記幾何変換する手段は、
   クエリ画像および各検索対象画像から直線成分を抽出する手段と、
   前記直線成分に基づいて消失点を検知する手段とを具備し、
   前記消失点に基づいて各画像の視点方向を算出する手段とを具備し、
   前記指定方向に基づいて、被写体の平行成分が画像上でも平行となるように各画像が幾何変換されることを特徴とする請求項１または２に記載の画像検索システム。
4. 前記検索対象画像が、建物が被写体となる街並画像であることを特徴とする請求項１ないし３のいずれかに記載の画像検索システム。
5. クエリ画像に類似した画像を検索対象画像の集合から検索する画像検索方法において、
   クエリ画像および各検索対象画像を、その被写体の平行成分が画像上でも平行となるように幾何変換する手順と、
   クエリ画像および各検索対象画像の特徴点から局所特徴量を抽出する手順と、
   前記クエリ画像および検索対象画像の各特徴点から抽出した局所特徴量を比較し、類似度が上位の特徴点を対応点候補として抽出する手順と、
   前記幾何変換されたクエリ画像および検索対象画像からエッヂ成分の出現パターンを検出する手順と、
   対応点候補が抽出されているクエリ画像および検索対象画像のペアについて、各対応点候補のクエリ画像側の位置と検索対象画像側の位置とのズレ量を、各画像のエッヂ成分の出現パターンに基づいて算出する手順と、
   前記ズレ量の算出結果に基づいて、前記対応点候補から対応点を抽出する手順と、
   前記抽出された対応点に基づいて、クエリ画像に類似した検索対象画像を決定する手順とを含むことを特徴とする画像検索方法。