画像検索方法、システム、及びプログラム
【課題】大規模画像データベースから特定の平面オブジェクト検索をする。
【解決手段】クエリ画像からの特徴をセグメントまたはポリゴンとしてグループ化する（７００）。後続の変換においては少なくとも２つの特徴を利用する。セグメントまたはポリゴンの変換を実行してクエリ画像に対するインライア特徴を判定する（７０１）。変換は、ハフ変換であってもよい。クエリ画像のインライア特徴を、対応する登録画像のインライア特徴と比較する（７０２）。比較は、パラメータ空間またはハフ空間で行なってもよい。
【解決手段】クエリ画像からの特徴をセグメントまたはポリゴンとしてグループ化する（７００）。後続の変換においては少なくとも２つの特徴を利用する。セグメントまたはポリゴンの変換を実行してクエリ画像に対するインライア特徴を判定する（７０１）。変換は、ハフ変換であってもよい。クエリ画像のインライア特徴を、対応する登録画像のインライア特徴と比較する（７０２）。比較は、パラメータ空間またはハフ空間で行なってもよい。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に画像検索方法、システム、及びプログラムに関し、特に大規模データベースにおける改良された画像検索に関する。
【背景技術】
【０００２】
大規模データベースにおける特定の平面オブジェクトの検索問題に対する試みが幾つかなされている。平坦面を有する特定のオブジェクトを含むクエリ画像が与えられた場合に、大規模な画像コーパスからそのオブジェクトを表す代表的な画像のセットを見つけることが目的である。クエリ画像とそのターゲット画像との間の幾何変換の複雑さから、問題は２つのクラスに分類できる。すなわち、回転−拡大縮小−平行移動（Ｒｏｔａｔｉｏｎ−Ｓｃａｌｅ−Ｔｒａｎｓｌａｔｉｏｎ、ＲＳＴ）変換画像検索と、アフィン／ホモグラフィ変換画像検索とである。前者の技術に基づく具体的なアプリケーションとしては、ＥＭＭ特定と部分複製画像検出がある。ＥＭＭ特定においては、クエリ画像は、携帯電話で撮影された原画像の３Ｄ視点が僅かに変化した画像である。従ってマッチングした２つの画像間の主たる幾何学的変化は、ＲＳＴ変換であると言える。同様に、部分複製画像検出における画像変化は主として、原画像への２Ｄデジタル編集技術によるものである。従ってこの場合には、マッチングした画像間の幾何学的変化はＲＳＴ変換で十分に説明できる。
【０００３】
しかしながら多くの場合、画像は、アフィン変換や場合によってはホモグラフィ変換などのような、ＲＳＴよりももっと一般的で複雑な変換をしたものになっている。例えば、ユーザが街中である視点から映画のポスタ−写真を撮影したとしよう。この撮影されたクエリ画像に基づいて、ユーザはその高品質画像またはそれに関連するオンライン上の映画のレビューを見ようとする場合を考える。この様な場合には、検索適合率を上げるために後者の“アフィン／ホモグラフィ変換画像検索”技術が利用される。
【０００４】
Ｂａｇ−ｏｆ−Ｗｏｒｄｓ表現
【０００５】
逆ファイル索引法と共に、Ｂａｇ−ｏｆ−Ｗｏｒｄｓ表現は、拡張性と精度とにおいて見事な性能を実証してきた。しかし、Ｂａｇ−ｏｆ−Ｗｏｒｄｓ表現は、Ｖｉｓｕａｌ Ｗｏｒｄｓのすべての空間情報を捨象し、そのために表現能力が大いに制限されて、通常は検索適合率が非常に低い。検索精度を上げるために、空間情報の欠落を補う目的で多くの方法が提案されてきた。すべての幾何形状の検証を利用する方法がある。この方法はロバストで高い検索適合率を達成するが、かなり長い計算時間を必要とする。より効率的な方法として、隣接する特徴間の空間関係で基本的なＶｉｓｕａｌ−Ｗｏｒｄ表現を増強するものがあるが、このアイディアに基づく方法は現状ではメモリ容量を多く必要とする。
【０００６】
画像検索の最新の方法は、Ｂａｇ−ｏｆ−Ｗｏｒｄｓ表現と拡張可能なテキスト索引方式とに依拠する傾向にある。しかし、Ｂａｇ−ｏｆ−Ｗｏｒｄｓ表現はＶｉｓｕａｌ Ｗｏｒｄｓの空間配置情報をすべて無視するので、記述能力に大きな制限があり、検索適合率が低い。空間情報の欠落を補うために、空間ピラミッドマッチング方式を利用する方法がある。これは、画像を次第に微細なサブ領域に区分し、そのサブ領域の内部でのみＶｉｓｕａｌ Ｗｏｒｄｓのマッチングを行う。この方式は高速で実装が簡単であるが、大きな幾何変換によるサブ領域の配列のずれにハード的なグリッド分割方式が影響される。
【０００７】
全体幾何検証（Ｆｕｌｌ Ｇｅｏｍｅｔｒｉｃ Ｖｅｒｉｆｉｃａｔｉｏｎ）
【０００８】
全体幾何検証法は、ＲＡＮＳＡＣまたは最小二乗中間値（Ｌｅａｓｔ Ｍｅｄｉａｎ ｏｆ Ｓｑｕａｒｅｓ、ＬＥＭＥＤＳ）等のロバストな適合方法を利用するが、一般変換を扱うことが可能であり、通常、偽マッチングを除外するために用いられる。一般的に、２つの画像間の仮変換モデルは特徴に基づいて評価される。すべての特徴は評価モデルで検証され、モデルに一致しないものがアウトライア（ｏｕｔｌｉｅｒ）として除外される。しかし、全モデルフィッティング手法は計算機処理が膨大となる。それに加えて、アウトライアのかなりの部分が量子化誤差および背景雑音から来るものであり、通常、ＲＡＮＳＡＣやＬＭＥＤＳなどの全モデルフィッティング方法は性能が低い。
【０００９】
全体幾何検証の課題に対処するために、全モデルフィッティング手法を適用する前に、効果的ではあるがより弱い幾何学的検証に基づくアウトライア・フィルタリング方式を用いる方法もある。また別の方式としては、Ｂａｇ−ｏｆ−Ｗｏｒｄｓ表現を隣接するＶｉｓｕａｌ Ｗｏｒｄｓ間の空間関係で補強しようとするものもある。例えば、従来法の１つは、Ｖｉｓｕａｌ Ｗｏｒｄｓを検出された最大定常性極値領域（ｍａｘｉｍａｌｌｙ ｓｔａｂｌｅ ｅｘｔｒｅｍａｌ ｒｅｇｉｏｎｓ、ＭＳＥＲ）によってグループに束ねて、各グループ内に幾何学的制約条件のセットを強制する。しかし、そのような方法の性能はバンドル方式のロバスト性、すなわちＭＳＥＲ検出器の再現性に大きく依存し、均一領域が僅かしか検出されないテキスト文書画像ではうまくいかない可能性が高い。別の方法では、空間コーディング方式を利用する。これは、各特徴を中心にして、この特徴と隣接する特徴との間の相対位置をコード化する。残念ながらこの方式は、全特徴に対する空間マップを格納するのに非常に大きなメモリ空間を必要とする。従ってあまり現実的ではない。
【００１０】
ハフ変換
【００１１】
別の１つの方法としては、アウトライアすなわち偽マッチングを処理するためにハフ変換を利用する方法がある。ハフ変換は、画像解析、コンピュータビジョン、およびデジタル画像処理に利用される特徴抽出手法である。この手法の目的は、ある形状のクラス内におけるオブジェクトの不完全なインスタンスを投票方式により発見することである。この投票方式はパラメータ空間で行なわれ、そこから、ハフ変換を計算するアルゴリズムによって明示的に構築されるいわゆるアキュムレータ空間における極大値として、オブジェクト候補が得られる。
【００１２】
古典的なハフ変換は画像内の直線の特定に係わるものであったが、後にハフ変換は任意の形態、特に円や楕円の位置の特定に展開されるようになった。
【００１３】
一般化ハフ変換（Ｇｅｎｅｒａｌｉｚｅｄ Ｈｏｕｇｈ Ｔｒａｎｓｆｏｒｍ、ＧＨＴ）は、ハフ変換をテンプレートマッチングの原理を利用して変形したものである。この変形により、ハフ変換を解析方程式で記述されるオブジェクト（例えば直線や円など）の検出のみならず、モデルで記述される任意のオブジェクトの検出にも利用できるようになった。
【００１４】
画像中の（モデルで記述された）オブジェクトを見つけるという問題は、画像中のモデルの位置を見つけることで解決される。一般化ハフ変換においては、モデル位置を見つける問題は、そのモデルを画像にマッピングする変換パラメータを見つけるという問題になる。変換パラメータがわかっている限り、画像中でモデル位置を判定することができる。
【００１５】
ＧＨＴの実装では、エッジ情報を利用して、エッジポイントの方向から形状の参照ポイントへのマッピングを画定する。ピクセルが黒または白の２値画像の場合、画像のすべての黒ピクセルは所望パターンの黒ピクセルとなり、ハフ空間内の参照点の位置を形成する。画像の各ピクセルが、対応する参照点に投票する。最大得票を得たハフ空間内のセル位置が、画像のパターンパラメータを示す。
【００１６】
ＧＨＴの主たる問題点は、かなりの計算時間と記憶容量を必要とすることであり、オブジェクトの方向及びスケールを考慮する必要のある場合には特に深刻となる。計算コストを低減するために、エッジの方向情報が利用されてきた。別のＧＨＴ手法、例えばＳＣ−ＧＨＴ（ローカル特性として傾斜と曲率を利用する）等も提案されてきている。
【００１７】
ハフ変換は、明らかなアウトライア（特徴の偽マッチング）を除外し、整合した変換解釈を示すインライア（ｉｎｌｉｅｒ）（特徴の真マッチング）のクラスタを特定するために利用されてきた。或る方法では、マッチングした指標付けされた特徴に対するクエリ特徴の４つのパラメータ、すなわち２次元平面上の位置、スケール及び方向を利用して、ハフ空間内の粗く量子化されたビンの１つに投票する。ビンに４票以上投入された特徴のクラスタが、最小二乗法に基づくアフィン投影パラメータの評価に利用される。別の方法では、２つのマッチングしたＶｉｓｕａｌ Ｗｏｒｄ間のスケール及び方向の違いを利用して、主要ビンに投票しない組合せを単純に除外する。
【００１８】
しかし、今日のハフ変換法は、周囲の特徴からの拘束は考慮せずに、個別の対応する特徴対に基づいて実行され、アウトライアを除外するための重要なヒントとなっている。さらに、これらの方法においては、パラメータ評価が粗いために、大きなサイズの量子化ビンを予め定めてハフ空間の投票に使用する。これではインライアとアウトライアの分離に限界があり、後続の全体幾何検証に大きな計算負荷を掛けてしまう。このようなハフ変換手法は高速ではあるが、これらのすべての方法は、非常に大雑把に評価したパラメータと、粗い、予め設定されたハフ空間と、単純な投票方式とを利用する。従って、これらの方式では、インライアからアウトライアを分離する性能がＲＡＮＳＡＣほどないことが多く、特にアフィン変換またはホモグラフィ変換などの複雑な変換に対してそうである。
【発明の概要】
【発明が解決しようとする課題】
【００１９】
本発明の方法は、画像検索の従来技術に関する１つ又は複数の前記及びその他の問題を実質的に取り除くための方法、システム及びプログラムに係わる。
【課題を解決するための手段】
【００２０】
本発明の第１の態様によれば、インライア判定ユニットにより、クエリ画像の特徴をセグメントまたはポリゴンとしてグループ化することと、前記インライア判定ユニットにより、前記クエリ画像と少なくとも１つの登録画像との間の前記特徴のセグメントまたはポリゴンの変換を計算して変換パラメータを取得することと、前記インライア判定ユニットにより、前記変換パラメータにグループ化パターンを適用することと、前記インライア判定ユニットにより、投票方式を使用して前記クエリ画像に対するインライア特徴を投票することと、幾何検証ユニットにより、前記クエリ画像からのインライア特徴の投票を使用して前記少なくとも１つの登録画像から最適マッチング登録画像を判定することと、を含む方法が提供される。
【００２１】
本発明の第２の態様によれば、上記第１の態様において、前記変換は、ＲＳＴまたはアフィン変換であってもよく、前記変換パラメータにグループ化パターンを使用することは、ハフ空間における前記変換パラメータの高密度領域を特定することを含んでもよく、前記投票方式を使用することは、前記投票方式により特徴を破棄することをさらに含んでもよく、破棄されなかった特徴をインライア特徴と判定してもよい。
【００２２】
本発明の第３の態様によれば、上記第１の態様において、前記クエリ画像と登録画像との間の変換パラメータを取得することは、前記クエリ画像の変換特徴グループを前記少なくとも１つの登録画像の変換特徴グループと比較することを含んでもよく、前記変換は、ＲＳＴまたはアフィン変換であってもよく、前記変換パラメータは、前記クエリ画像と前記少なくとも１つの登録画像に対するハフ空間におけるインライア特徴を判定するために使用されてもよい。
【００２３】
本発明の第４の態様によれば、上記第１の態様において、前記クエリ画像と前記登録画像との間の変換パラメータを取得することは、空間領域において前記クエリ画像のインライア特徴と前記登録画像の変換されたインライア特徴とを比較することにより行われてもよく、前記変換は、ＲＳＴまたはアフィン変換であってもよく、前記変換パラメータは、ハフ空間における特徴の投票に使用されてもよい。
【００２４】
本発明の第５の態様によれば、上記第１の態様において、前記登録画像からの特徴をセグメントまたはポリゴンとしてグループ化することを更に含んでもよい。
【００２５】
本発明の第６の態様によれば、上記第２の態様において、ハフ空間における変換パラメータの高密度領域を特定することは、前記クエリ画像と前記少なくとも１つの登録画像との間の前記セグメントまたはポリゴンの変換パラメータをハフ空間へマッピングすることと、ハフ空間のグリッド内のセグメントまたはポリゴンの変換パラメータの総数のピークを特定することと、前記ピークに隣接する所定の閾値を満たすグリッドを特定することと、前記ピークと前記特定されたグリッドとに基づいて高密度領域を特定することと、を更に含んでもよい。
【００２６】
本発明の第７の態様によれば、クエリ画像を受信する装置と、前記クエリ画像からの特徴をセグメントまたはポリゴンとしてグループ化し、登録された各画像からの特徴をセグメントまたはポリゴンとしてグループ化し、セグメントまたはポリゴン変換を行なって前記クエリ画像及び各登録画像に対する変換パラメータを取得し、ハフ空間における変換パラメータの高密度領域からクエリ画像のインライア特徴を選択するプロセッサと、前記クエリ画像のインライア特徴と前記各登録画像の対応するインライア特徴とをマッチングする幾何検証ユニットと、を備えるシステムが提供される。
【００２７】
本発明の第８の態様によれば、上記第７の態様において、前記ハフ空間における変換パラメータの高密度領域からクエリ画像のインライア特徴を選択することは、ハフ空間における変換された特徴の高密度領域を特定し、変換された特徴を投票方式に基づいて破棄することを含んでもよく、前記変換は、ＲＳＴまたはアフィン変換またはホモグラフィ変換であってもよく、破棄されなかった変換された特徴をインライア特徴と判定してもよい。
【００２８】
本発明の第９の態様によれば、上記第７の態様において、前記クエリ画像と前記登録画像との間のインライア特徴変換を計測することにより、前記クエリ画像と前記各登録画像との間の変換パラメータを取得するパラメータ評価ユニットを更に備えてもよく、前記変換は、ＲＳＴ、アフィン変換、またはホモグラフィ変換であってもよく、前記変換パラメータは、ハフ空間における対応するインライア特徴の判定に使用されてもよい。
【００２９】
本発明の第１０の態様によれば、上記第７の態様において、前記クエリ画像のインライア特徴と前記登録画像の変換されたインライア特徴とを空間領域で比較することにより、前記クエリ画像と前記各登録画像との間の変換パラメータを取得するパラメータ評価ユニットを更に備えてもよく、前記変換は、ＲＳＴ、アフィン変換、またはホモグラフィ変換であってもよく、前記変換パラメータは、ハフ空間における対応するインライア特徴の判定に使用されてもよい。
【００３０】
本発明の第１１の態様によれば、上記第７の態様において、前記装置は、カメラであってもよい。
【００３１】
本発明の第１２の態様によれば、上記第８の態様において、前記ハフ空間における変換パラメータの高密度領域を特定することは、前記クエリ画像と前記各登録画像との間の前記セグメントまたはポリゴン変換をハフ空間へマッピングすることと、前記ハフ空間のグリッド内の前記クエリ画像と登録画像との間のセグメントまたはポリゴン変換の総数のピークを特定することと、前記ピークに隣接する所定の閾値を満たすグリッドを特定することと、前記ピークと前記特定されたグリッドとに基づいて高密度領域を特定することと、
を更に含んでもよい。
【００３２】
本発明の第１３の態様によれば、コンピュータに、クエリ画像からの特徴をセグメントまたはポリゴンとしてグループ化することと、ハフ空間において前記セグメントまたはポリゴンの変換を算出して、前記クエリ画像のインライア特徴を判定することと、前記クエリ画像のインライア特徴を使用して最適マッチング登録画像を判定することと、を含む処理を実行させるプログラムが提供される。
【００３３】
本発明の第１４の態様によれば、上記第１３の態様において、前記クエリ画像のインライア特徴を判定することは、ハフ空間における変換パラメータの高密度領域を特定することと、投票方式に基づいて特徴を破棄することとを含んでもよく、前記変換は、ＲＳＴ、アフィン変換、またはホモグラフィ変換であってもよく、破棄されなかった特徴をインライア特徴と判定してもよい。
【００３４】
本発明の第１５の態様によれば、上記第１３の態様において、前記処理は、変換されたクエリ画像のインライア特徴を前記各登録画像の変換されたインライア特徴と比較することにより、前記クエリ画像と各登録画像との間の変換パラメータを評価することを更に含んでもよく、前記変換は、ＲＳＴ、アフィン変換、またはホモグラフィ変換であってもよく、前記変換パラメータは、ハフ空間における対応するインライア特徴の判定に使用されてもよい。
【００３５】
本発明の第１６の態様によれば、上記第１３の態様において、前記処理は、前記クエリ画像のインライア特徴を空間領域における前記各登録画像の変換されたインライア特徴と比較することにより、前記クエリ画像と各登録画像との間の変換パラメータを評価することを更に含んでもよく、前記変換は、ＲＳＴまたはアフィン変換、またはホモグラフィ変換であってもよく、前記変換パラメータは、ハフ空間における対応するインライア特徴の判定に使用されてもよい。
【００３６】
本発明の第１７の態様によれば、上記第１３の態様において、前記処理は、各登録画像からの特徴をセグメントまたはポリゴンとしてグループ化することを更に含んでもよい。
【００３７】
本発明の第１８の態様によれば、上記第１４の態様において、ハフ空間における変換された特徴の高密度領域を特定することは、前記セグメントまたはポリゴンの変換されたパラメータをハフ空間中にマッピングし、前記ハフ空間のグリッド内のセグメントまたはポリゴン変換パラメータの総数のピークを特定し、前記ピークに隣接する所定の閾値を満たすグリッドを特定し、前記ピークと前記特定されたグリッドとに基づいて高密度領域を特定することを更に含んでもよい。
【００３８】
本発明に関するその他の態様は、以下の説明で部分的に説明され、また以下の説明で部分的に明らかであり、又は本発明の実行により習得することができる。本発明の態様は、以下の詳細な説明及び添付の特許請求の範囲において特に指摘された要素、及び種々の要素と態様との組合せによって、実現及び達成をすることができる。
【００３９】
上記及び以下の記述はいずれも、単に例示及び説明を目的とするものであり、特許請求の範囲に記載の発明もしくはその適用をいかなる形であれ限定することは全く意図されていないことを理解されたい。
【図面の簡単な説明】
【００４０】
本明細書に組み込まれ、本明細書の一部をなす添付の図面が、本発明の実施形態を例示し、説明と相俟って、本発明技術の原理の説明及び例示に供する。
【図１】本発明の実施形態による２次元高密度領域検出アルゴリズムの例を示す図である。
【図２】ＲＳＴ変換画像に対するハフ変換に基づくアウトライア・フィルタリング実装例を示す図である。
【図３】本発明の実施形態による粗いハフ変換による明らかなアウトライアの除外とインライアのクラスタリングのプロセス例を示す図である。
【図４】本発明の実施形態によるＲＳＴ画像検索に対する２段階ハフ変換の例示的実装を示す図である。
【図５】本発明の実施形態によるアフィン／ホモグラフィ変換画像検索のために２次元ハフ変換のセットをバンドルし、フィルタリングされたハフ空間におけるパラメータを正確に評価する例示的実装を示す図である。
【図６】本発明の実施形態によるアフィン／ホモグラフィ変換画像検索のために、２次元ハフ変換のセットをバンドルし、モデルフィルタリング法に基づいてパラメータを正確に評価する例示的実装を示す図である。
【図７】本発明の基本的実施形態による例示的フローチャートを示す図である。
【図８】本発明の実施形態による例示的機能図である。
【図９】本発明のシステムを実装するコンピュータプラットフォームの実施形態を示す図である。
【発明を実施するための形態】
【００４１】
以下の詳細な説明においては添付の図面を参照する。ここで、同一の機能的要素は同様の符号で示される。前述の添付図面は、本発明の原理に整合する特定の実施形態および実装を例示するものであり、それに限定するためのものではない。これらの実装形態は、当業者による本発明の実行を可能とすべく詳細に記述される。また、他の実装も利用可能であること、及び本発明の範囲及び精神から逸脱することなく様々な要素の構造上の変更及び／又は代替が行われてもよいことを理解されたい。従って、以下の詳細な記述は本発明を制限するものとして解釈されるべきではない。更に、記述される本発明の様々な実施形態は、汎用コンピュータ上で実行されるソフトウェア、専用ハードウェア、あるいはソフトウェアとハードウェアの組合せ、のいずれの形態において実施されてもよい。
【００４２】
大規模なデータベースにおける特定の平面オブジェクトの検索精度を上げ、検証プロセスを高速化するために、本発明の様々な実施形態ではハフ変換を利用する。既存のハフ変換をベースとする方法における限界に対処するために、画像全体におけるマッチングポイントの関係に基づくより高精度のパラメータ評価が実行される。従来手法に比べて、より高精度のパラメータ評価をすることにより、インライア−アウトライアをより正確に分離でき、その結果として、全体幾何検証の負荷が低減されて、検索適合率は向上する。さらに、予め設定された量子化ビンの境界効果に対処するために、２次元高密度領域検出という、よりロバストな手法を利用する。これは、任意の濃度で分散する一定の特徴のクラスタを特定することが可能であり、量子化サイズにあまり依存しない。ＲＳＴ画像を検索するために、検出された高密度領域をＲＳＴパラメータの正確な値の計算に直接利用することができ、領域内の重み付きの量子化値の平均を用いてもよく（この方法はメモリをあまり必要としない）、または領域内のＭＳＳにより評価された実際の値の平均を用いてもよい（精度は上がるが、より多くのメモリを必要とする）。２００ｋ以上の画像を有する大規模データベースにおける実験では、本発明の種々の実施形態は一貫して高精度が得られる傾向がある。すなわち、ＥＭＭ特定においては９９％を超えるトップ３の精度であり、部分複製画像検出においては８．５以上のトップ１０の適合率である。さらに、メモリ使用量と計算時間もまた低くなる傾向にある。すなわち、ＥＭＭ特定では５６０ｍｓ未満で１．２ＧＢのメモリ空間であり、部分複製画像検出では１．２ｓ未満で８８０ＧＢのメモリ空間である。
【００４３】
計算の複雑さを更に低減するために、特に複雑な変換を受けた画像に対して、粗段階のハフ変換が利用される。これは、早い段階で明らかなアウトライアを除外し、インライアをクラスタにグループ化する。そして、２段階のハフ変換をしてから、幾何検証をうける。
【００４４】
アフィン／ホモグラフィ変換画像の検索に関して、最小サンプルセット（ｍｉｎｉｍｕｍ ｓａｍｐｌｅ ｓｅｔｓ、ＭＳＳ）で評価されたパラメータを用いるハフ変換をベースとする検証における大きな課題は、高次元パラメータ空間においてアウトライアの割合が高いことである。全パラメータ空間を幾つかの２次元ハフ空間に分割すると、それぞれの２次元ハフ変換ではインライアよりもむしろアウトライアにモデルが合う可能性が高い。この問題に対処するには、ハフ変換のセットを一緒にバンドルして、インライアとアウトライアのセグメント化を行う。それぞれの２次元ハフ空間は、“弱い分類器”としてサンプルの分類に用いられる。そして投票方式によって最終判定がなされる。
【００４５】
ＲＳＴ変換画像検索のためのハフ変換に基づくアウトライアのフィルタリング
【００４６】
回転−拡大縮小−平行移動（ＲＳＴ）変換画像クエリに対して、本発明の実施形態ではハフ空間フィルタリング法を活用する。画像間のマッチングポイントの各対に対して、本発明の実施形態では、パラメータのセットを取得し、ハフ空間内に蓄積して、パラメータの評価を行う。
【００４７】
ＲＡＮＳＡＣやＬＭＥＤＳの問題を克服するために、本発明の実施形態ではハフ変換の手法を活用してアウトライアをフィルタリングして除外して、検証プロセスを高速化する。そして、画像全体においてマッチングポイントに基づくより高精度のパラメータ評価を実行する。通常のハフ変換システムに比べると、より高精度のパラメータ評価を活用することで、より良好にインライアとアウトライアを分離できる。インライアとアウトライアを良好に分離することにより、全体幾何検証の負荷がさらに軽減し、認識結果を向上することができる。アウトライアのフィルタリングには次の３つのコンセプトを活用する。
【００４８】
代表的パラメータの評価
代表的パラメータの評価は最小サンプルセット（ＭＳＳ）を用いて計算される。最小サンプルセットには、モデルパラメータを判定するための最小数のサンプルすなわち特徴が含まれている。
【００４９】
ハフ変換のための高密度領域の検出
投票して主ビン（最多得票ビン）を検出するために予め定義された量子化ビンを用いる代わりに、よりロバストな、これ以降２次元高密度領域検出と呼ぶ手法を利用して、任意の密度で一定の分布している特徴のクラスタを特定する。これは量子化サイズには過度に依存しない。そのようなインライアクラスタの検出方法を順番に利用することにより、計算及びメモリ空間の複雑さを軽減することができる。
【００５０】
検出された高密度領域に基づく正確なパラメータの計算
検出された高密度領域内の特徴である、検出されたインライアに基づいて、領域内の重み付き量子化値の平均化か、領域内のＭＳＳに基づいて評価された実際の値の平均化のいずれかにより、パラメータ値を直接計算することが可能である。
【００５１】
Ｖｉｓｕａｌ Ｗｏｒｄのランク付け
クエリ画像のＶｉｓｕａｌ Ｗｏｒｄが画像中心からの距離の近い順にランク付けされる。
【００５２】
代表パラメータの評価
【００５３】
指標ポイント［ｘ，ｙ］Ｔのクエリポイント［ｕ，ｖ］ＴへのＲＳＴ変換は次のように表現される。
【数１】
【００５４】
等方的な比例縮小、回転、および平行移動はそれぞれ、ｓ、θ、［ｔｘ，ｔｙ］Ｔで表される。
【００５５】
表記を簡単にするために、ａ＝ｓ＊ｃｏｓθ、ｂ＝ｓ＊ｓｉｎθと表すと、ＲＳＴ変換は次のように書き直される。
【数２】
【００５６】
４つの変換パラメータ（ａ，ｂ，ｔｘ，ｔｙ）を解くためには、少なくとも２つの特徴が必要である。従って変換は少なくとも２つの特徴に基づいて実行され、特徴のセグメントまたはポリゴンが利用される。Ｎ個の特徴から成るセグメントまたはポリゴンが与えられているものとすると、各ＭＳＳに基づくパラメータの評価によって、式（１）に示すように、Ｎ（Ｎ−１）／２のパラメータの評価が与えられる。
【数３】
【００５７】
ここで、［Δｕｉｊ，Δｖｉｊ］Ｔ、［Δｘｉｊ，Δｙｉｊ］Ｔがそれぞれクエリポイント［ｕｉ，ｖｉ］Ｔと［ｕｊ，ｖｊ］Ｔとの差、および対応するマッチングした指標ポイント［ｘｉ，ｙｉ］Ｔと［ｘｊ，ｙｊ］Ｔとの差である。（ａｉｊ，ｂｉｊ，ｔｘｉｊ，ｔｙｉｊ）は２つの特徴に基づいて計算されるパラメータである。
【００５８】
ハフ変換のための高密度領域の検出
【００５９】
パラメータが与えられると、標準的なハフ変換手順は３つのステップで行われる。ａ）全パラメータ空間を予め設定されたビンに量子化することによりアキュムレータ空間を構築する。ｂ）各パラメータをアキュムレータ空間のビンに投入する。ｃ）パラメータが最も多い主ビンを見つける。この手順においては、２つの大きな制約がある。第１に、全パラメータ空間において主ビンを探索するのに時間的空間的複雑さが大きい。これはＯ（Ｋ１，．．．Ｋｍ）のオーダであり、ここで、Ｋｉ（１≦ｉ≦ｍ）は次元ｉの範囲であり、ｍはパラメータ数である。第２に、検出された特徴の位置誤差により、インライアから成るＭＳＳのパラメータがパラメータ空間の１点に重ならないで、ある密度でのグループになる可能性がある。従って、インライアとアウトライアとの分離が、予め設定されたビンサイズで、すべての場合にうまく機能するわけではない。予め設定されたビンサイズが小さ過ぎると、真のインライアが隣接ビンに入ってしまい、主ビンの顕現性が損なわれる可能性がある。しかし、サイズが大き過ぎると、適正なビンに多くのアウトライアが入ってしまう。
【００６０】
この複雑さの問題に対処するために、本発明の実施形態においては、全体の４パラメータ空間を２つの２次元空間、すなわちａ−ｂ空間とｔｘ−ｔｙ空間とに分解し、それを順番に結合する。本発明の実施形態では、先ずａ−ｂ空間においてハフ変換を実行してインライアを特定し、次にこれらのインライアに基づいて正確なａ，ｂの値を取得する。その後に、正確なａ，ｂの値に基づいてそれぞれの対応のｔｘ，ｔｙを計算し、再度ｔｘ−ｔｙ空間においてハフ変換を実行して正確なｔｘ、ｔｙの評価を行う。
【００６１】
第２の問題に対処するために、本発明の実施形態においては、２次元高密度領域検出アルゴリズムを利用する。そのプロセスを下の表に示し、図１で説明する。
【数４】
【００６２】
図１は本発明の実施形態による２次元高密度領域検出アルゴリズムの例を示す。この実施例では、ａ−ｂ空間は８×８のグリッド１００に量子化される。ビンａｉとｂｊとが次元ａとｂに沿って最大得票を得た主ビンとして検知される。主ビンとして検知されたそれぞれに関して、最近接のビンが検査される。そのビンが十分な得票を得ていれば（この実施例では、ａの評価式１０２およびｂの評価式１０３に対して閾値を３に設定した）、この次元の範囲を拡大して、そのビンを含むようにする。そうでない場合には終了する。拡大範囲内の領域が、検出された高密度領域１０１として判定される。
【００６３】
検出された高密度領域に基づく正確なパラメータの計算
【００６４】
検出された高密度領域に基づいて、高精度のパラメータａ、ｂ、ｔｘ、ｔｙの計算を更に進めるために２つの方法がある。
ａ）領域内の重み付き量子化値を平均する。量子化値の重みは、検出された領域内において、この次元に沿うすべてのビン内のオブジェクトの総数に対する該当するビン内のオブジェクト数として定義することができる。この方式は、各ＭＳＳから取得されたパラメータの実際の値を格納する必要がないので、高速でありかつメモリ効率が良い。
ｂ）検出された領域内のＭＳＳに基づいて評価された実際の値を平均化する。この方式はより正確である。ただし、パラメータの実際の値を格納するためにより大きなメモリを必要とし、またそれにアクセスするのに時間も長くかかる。
【００６５】
Ｖｉｓｕａｌ Ｗｏｒｄのランク付け
【００６６】
すべての特徴を変換評価に利用して記録するには、時間もかかり、メモリも多く必要である。実際には、対象となるオブジェクトは一般的に、十分な画像空間を活用し、クエリ画像の中心付近に配置されているという事実に基づいて、特徴の部分集合のみが利用される。従って、クエリ画像の中心に近い特徴が、周辺部にある特徴に比べて、ターゲット画像上に現れる可能性が高い。この事実により、本発明の実施形態においては、クエリ画像のｖｉｓｕａｌ ｗｏｒｄｓを画像中心からの距離に従って昇順にランク付けする。そして、最高ランクのクエリ特徴をデータベースとマッチングさせる際に、それらの特徴をより容易かつより早く選択できるようにする。
【００６７】
図２は、ＲＳＴ変換画像に対するハフ変換を利用したアウトライア・フィルタリングのフローチャートの例を示す。
【００６８】
特徴の最初のフィルタリングとして、Ｂａｇ ｏｆ Ｗｏｒｄｓ（ＢｏＷ）クエリがクエリ画像に適用されて、画像中心からの距離に基づいて判定及びランク付けされる（２００）。ランク付けされたＢｏＷに基づき、データベース２０２中の画像に対して最初の対応構築２０１が実行される。幾何検証２０５に利用される特徴を精選するために、クエリ中心２０３に最近接する予め設定された個数のマッチングによってハフ変換が実行され、拡大縮小と回転を処理するために、２次元並進空間２０４で別のハフ変換が行なわれる。クエリ画像と登録画像との間でインライアが導出され、ランク付けされる（２０６）。
【００６９】
フィルタリングプロセス高速化のための２段階ハフ変換
【００７０】
全てのＭＳＳでパラメータを評価することは、パラメータ数が増すに連れて多大な時間を要するようになる。さらに、パラメータ数が増加するにつれハフ変換でのインライアの割合も下がってくる。
【００７１】
このような問題に対処するために、本発明の実施形態では２段階ハフ変換方式を利用する。これは、先ず粗いハフ変換を行なって、指標付けされた特徴の位置と高密度領域検出アルゴリズムとによって明らかなアウトライアを除外し、次いで、上述の精細なハフ変換を実行してインライアを更に精選して正確なパラメータを評価する。
【００７２】
２段階ハフ変換方法の説明
【００７３】
図３は、本発明の実施形態による粗いハフ変換による明らかなアウトライアの除外とインライアのクラスタリングのプロセスの例を示す。
【００７４】
図３に示すように、粗いハフ変換に用いられるパラメータは、明らかなアウトライアを迅速に特定可能であり、その一方で、見落とすインライアは僅かしかない。評価に使用されるクエリ特徴は、画像中心の近くに位置する。従って、対応する指標付けされた特徴、つまり真の変換を示すと思われる特徴は、まとまってグループを形成する筈である。そこで特徴は、図３（ａ）に示す高密度領域検出手法に基づいて指標付けされた特徴の位置に従ってグループ化される。しかし、最大得票数の１つの領域を選択するのではなく、本発明の実施形態では、ＭをＭＳＳの濃度とすると、Ｍ個より多い特徴を含むすべての候補領域を先ず検出する（候補領域の例を図３（ｂ）に示す）。その次に、それぞれの候補領域の近傍をチェックして（図３（ｃ）の点線の円に示すように）、他のすべての候補領域から離れている領域を削除する。そして最後に、本発明の実施形態によりインライアのクラスタが取得され、図３（ｄ）に示すように各検出領域内のパラメータがＭＳＳに基づいて計算される。
【００７５】
図４は、本発明の実施形態によるＲＳＴ画像検索に対する２段階ハフ変換の例示的実装を示す。図２で用いられたハフ変換に加えて、追加的な粗いハフ変換４００を用いてフィルタリングされたマッチング点のクラスタを得てもよい。考え方としては、図２のハフ変換を、対比的に精細なハフ変換４０１と見なすことが可能である。
【００７６】
アフィン変換またはホモグラフ変換画像への拡張方法
【００７７】
本発明の実施形態で、より一般的な変換、例えばアフィン変換またはホモグラフィ変換を含む画像の処理も試みる。
【００７８】
上記の方法を利用することにより、本発明の実施形態は大規模なＲＳＴ画像検索に対して優れた性能を発揮する。しかし、この方式をアフィン／ホモグラフィ変換画像に直接適用すると以下の２つの問題に直面する。
１）６または８個のパラメータに対する計算コストはＯ（ＮＣ）の割合で顕著に増加する。ここで、Ｎは評価に利用する特徴の数であり、Ｃはモデルを評価するためのＭＳＳの濃度である。
２）パラメータ数の増加と共に、アウトライアの割合が顕著に増大する。従って、全体のパラメータ空間を幾つかの２次元ハフ空間に分割すると、各２次元ハフ空間内のアウトライアが、インライアが形成する高密度領域よりも得票数の高い高密度領域を形成する可能性が非常に大きい。言い換えると、２次元ハフ変換は、インライアよりもアウトライアで構成されたモデルに合う可能性が高い。
【００７９】
アフィン変換またはホモグラフ変換画像への拡張方法の説明
【００８０】
高い計算コストに対処するために、本発明の実施形態は、２段階でＭＳＳの数を低減する。ａ）粗いハフ変換を適用してアウトライアのいくつかを除外し、対応セット全体をいくつかのグループに分割する。ｂ）各グループのＭＳＳの数が予め設定した値を超えると、各対応に基づいてＭＳＳの部分集合を選択することのみによりでＭＳＳを更に低減する。このやり方によって計算コストを大きく低減できる。例えば、ホモグラフィ変換に対する８つのパラメータの評価に５０の特徴が与えられたとすると、すべての特徴の組合わせは膨大であって２３０３０１個のＭＳＳになってしまう。粗い変換によって特徴を２つのグループに分けて、各グループが２５個ずつを含むと仮定すると、ＭＳＳの総数は２５３００に減らすことが可能である。さらに、個別対応関係からＭＳＳの７０％しか使わないとすると、ＭＳＳ数を更に６０７５に減らすことができる。
【００８１】
第２の問題に対処するために、本発明の実施形態はインライアとアウトライアを分離するために２次元ハフ変換のセットをバンドルする。事実として、インライアは、大部分の２次元ハフ空間において一定のグループを形成する。その一方で、アウトライアは、大部分の２次元ハフ空間において密にグループ化する確率がはるかに低い。従ってそれぞれの２次元ハフ空間を“弱い分類器”と見なすことができる。サンプルが検出された高密度領域に入っていれば、それはインライア候補とされ、そうでなければアウトライアとされる。“弱い分類器”がサンプルから十分な数のインライア候補を特定する場合に、それは保存され、そうでない場合には除外される。このプロセスにおいて、インライア／アウトライアの投票数が予め設定した閾値に到達すると、２次元ハフ空間での検索を停止することができる。より厳密でより高速なアウトライアの特定法としては、“弱い分類器”を直列に結合する方法がある。この場合には、１つの“弱い分類器”が対応関係をアウトライアであるとみなすと、それは除外される。
【００８２】
第３段階のハフ空間における高精度のアフィン／ホモグラフィ評価
【００８３】
インライアを取得した後、図５と図６に示す２つの方法で変換パラメータを正確に評価することが可能である。
【００８４】
図５は、本発明の実施形態による、アフィン／ホモグラフィ変換画像検索のために、２次元ハフ変換のセット５００をバンドルし、フィルタリングされたハフ空間におけるパラメータの正確な評価をするための例示的実装を示す。正確なアフィン／ホモグラフィ評価はフィルタリングされたハフ空間５０１で実行される。評価の実行には、インライアの重み付き量子化パラメータの平均を利用するか、またはインライアから評価された実パラメータ値の平均を利用するかのいずれかが行なわれる。
【００８５】
図６は、本発明の実施形態による、アフィン／ホモグラフィ変換画像検索のために、２次元ハフ変換のセットをバンドルし、モデルフィルタリング法に基づいてパラメータの正確な評価をするための例示的実装を示す。パラメータの評価は、パラメータを空間ドメインに戻してモデルフィッティング法６００で評価することにより実行できる。
【００８６】
評価
１．ＤＬＴ、ＬＭＥＤＳ、ＲＡＮＳＡＣと本発明の実施形態による方法との性能比較
【００８７】
ＲＳＴ画像検出への適用における本発明の実施形態による方法の性能をテストするために、よく知られた別の３つのフィッティング方法、すなわちＤＬＴとＬＭＥＤＳとＲＡＮＳＡＣとの比較を行った。性能は、５つの基準に関して評価した。それらは、マッチング画像がトップ１として検出される割合(トップ1精度)、クエリあたり２０００画像のマッチングに要するマッチング時間、真のマッチング画像に対する正検出割合（ＰＰ−Ｔ）、真のマッチング画像に対する負検出割合（ＮＮ−Ｔ）、偽マッチング画像に対する負検出割合（ＮＮ−Ｆ）である。表１は、４つの手法に対するこれら５つの基準での性能を示す。この結果から、ＲＳＴ画像の検出に関しては、本発明の方法が、他の方法に比べて、すべての評価基準において優れた結果が得られることがわかる。
【表１】
【００８８】
２．本発明の実施形態に基づく大規模ＥＭＭ特定と部分複製画像検出
【００８９】
大規模なデータベース上での本発明の基本的実施形態の性能を評価するために、２つの実際の適用例である部分複製画像検出とＥＭＭ特定とに関して実験を行った。部分複製画像検出に関しては、正確性の評価基準として、トップ１０適合率、すなわちトップ１０ランクリスト内での正しい画像の平均数を用いた。ＥＭＭ特定に関しては、評価基準として、トップ３精度、すなわちターゲット画像が検出されてトップ３内にランクされるクエリ画像の割合が用いられた。
【００９０】
表２は、異なるサイズのデータセット上での部分複製画像検出の性能を示し、表３と表４は、異なるサイズのデータセット上での文書画像と自然画像のＥＭＭ特定の性能を示す。表２、３、４の結果から、本発明の基本実施形態は、データベースサイズを増やして行ってもこれらのアプリケーションにおいては一貫して高いトップ１０適合率とトップ３精度を達成することがわかる。さらに、時間とメモリのコストはデータセットのサイズに比例して増大するが、２００以上の画像を有するデータセットに対しても妥当なものとなっている。
【００９１】
【表２】
【表３】
【表４】
【００９２】
図７は、本発明の基本的実施形態による例示的フローチャートを示す。
【００９３】
クエリ画像からの特徴をセグメントまたはポリゴンとしてグループ化する（７００）。後続の変換においては少なくとも２つの特徴を利用する。従って特徴のグループは特徴のセグメントまたはポリゴンで構成される。
【００９４】
セグメントまたはポリゴンの変換を実行してクエリ画像に対するインライア特徴を判定する（７０１）。変換は、ハフ変換であってもよい。
【００９５】
クエリ画像のインライア特徴を、対応する登録画像のインライア特徴と比較する（７０２）。比較は、パラメータ空間またはハフ空間で行なってもよい。
【００９６】
図８は、本発明の実施形態による例示的機能図８００を示す。
【００９７】
クエリ画像８０１は、カメラなどの装置８０２で受信され、インライア判定ユニット８０３に供給され、クエリ画像のインライアが判定される。インライア判定ユニットは、クエリ画像の特徴をセグメントまたはポリゴンとしてグループ化するグループ化ユニットと、クエリ画像と登録画像との間の特徴のセグメントまたはポリゴンの変換を計算して変換パラメータを取得する変換パラメータ取得ユニットと、変換パラメータにグループ化パターンを適用するパターン化ユニットと、該グループ化パターンを適用することは、ハフ空間における変換パラメータの高密度領域を特定することを含んでもよく、投票方式を使用してクエリ画像に対するインライア特徴を投票する投票ユニットと、を備えてもよい。結果が幾何検証ユニット８０４に供給され、そこでクエリ画像のインライアと登録画像のインライアとの比較が行なわれる。その結果がディスプレイ８０５に表示される。
【００９８】
図９は、本発明による方法の実施形態を実装することが可能なコンピュータ／サーバシステム９００の実施形態を示すブロック図である。システム９００は、当業者には周知の命令を実行するように作用するプロセッサ９０２とメモリ９０３を含むコンピュータ／サーバプラットフォーム９０１を含む。本明細書で用いられる「コンピュータ可読媒体」という用語は、プロセッサ９０２に実行命令を与えることに関与する任意の媒体を指す。さらに、コンピュータプラットフォーム９０１は、キーボード、マウス、タッチデバイスなどの複数の入力装置９０４、または音声命令からの入力を受信する。コンピュータプラットフォーム９０１はさらに、ポータブルハードディスク装置、光学媒体（ＣＤまたはＤＶＤ）、ディスク媒体、またはコンピュータが実行命令を読み込むことができるその他の任意の媒体などのリムーバブル記憶装置９０５に接続されていてもよい。コンピュータプラットフォームはさらに、インターネットに接続されるネットワークリソース９０６、またはその他のローカルな公共または私的なネットワーク部品に接続されていてもよい。ネットワークリソース９０６は、ネットワーク９０７上のリモートロケーションから命令およびデータをコンピュータプラットフォームへ供給してもよい。ネットワークリソース９０６への接続は、８０２．１１標準やＢｌｕｅｔｏｏｔｈ（登録商標）ブルートゥースやセルラープロトコル等の無線プロトコル経由で、または、電線やファイバ光学部品などの物理的伝送媒体経由であってもよい。ネットワークリソース９０６は、コンピュータプラットフォーム９０１からは隔離した場所にデータ及び実行可能な命令を格納するための記憶装置を含んでいてもよい。コンピュータはディスプレイ９０８と相互作用して、データやその他の情報をユーザへ出力したり、ユーザからの追加の指示と入力を要求したりする。従ってディスプレイ９０８は、ユーザと対話するための入力装置９０４としての作用をさらに有してもよい。
【００９９】
さらに、ここに開示した本発明の明細書を考察し、本発明を実施すれば、本発明の他の実装が当業者には明らかとなるであろう。前述の実施態様の様々な態様及び／又は構成要素は、画像識別システムに単独もしくは任意の組み合わせで使用することが可能である。明細書及び実施例は例示としてのみ理解されるべきであり、本発明の真の範囲と精神は添付の特許請求の範囲によって示されるものとする。
【技術分野】
【０００１】
本発明は一般に画像検索方法、システム、及びプログラムに関し、特に大規模データベースにおける改良された画像検索に関する。
【背景技術】
【０００２】
大規模データベースにおける特定の平面オブジェクトの検索問題に対する試みが幾つかなされている。平坦面を有する特定のオブジェクトを含むクエリ画像が与えられた場合に、大規模な画像コーパスからそのオブジェクトを表す代表的な画像のセットを見つけることが目的である。クエリ画像とそのターゲット画像との間の幾何変換の複雑さから、問題は２つのクラスに分類できる。すなわち、回転−拡大縮小−平行移動（Ｒｏｔａｔｉｏｎ−Ｓｃａｌｅ−Ｔｒａｎｓｌａｔｉｏｎ、ＲＳＴ）変換画像検索と、アフィン／ホモグラフィ変換画像検索とである。前者の技術に基づく具体的なアプリケーションとしては、ＥＭＭ特定と部分複製画像検出がある。ＥＭＭ特定においては、クエリ画像は、携帯電話で撮影された原画像の３Ｄ視点が僅かに変化した画像である。従ってマッチングした２つの画像間の主たる幾何学的変化は、ＲＳＴ変換であると言える。同様に、部分複製画像検出における画像変化は主として、原画像への２Ｄデジタル編集技術によるものである。従ってこの場合には、マッチングした画像間の幾何学的変化はＲＳＴ変換で十分に説明できる。
【０００３】
しかしながら多くの場合、画像は、アフィン変換や場合によってはホモグラフィ変換などのような、ＲＳＴよりももっと一般的で複雑な変換をしたものになっている。例えば、ユーザが街中である視点から映画のポスタ−写真を撮影したとしよう。この撮影されたクエリ画像に基づいて、ユーザはその高品質画像またはそれに関連するオンライン上の映画のレビューを見ようとする場合を考える。この様な場合には、検索適合率を上げるために後者の“アフィン／ホモグラフィ変換画像検索”技術が利用される。
【０００４】
Ｂａｇ−ｏｆ−Ｗｏｒｄｓ表現
【０００５】
逆ファイル索引法と共に、Ｂａｇ−ｏｆ−Ｗｏｒｄｓ表現は、拡張性と精度とにおいて見事な性能を実証してきた。しかし、Ｂａｇ−ｏｆ−Ｗｏｒｄｓ表現は、Ｖｉｓｕａｌ Ｗｏｒｄｓのすべての空間情報を捨象し、そのために表現能力が大いに制限されて、通常は検索適合率が非常に低い。検索精度を上げるために、空間情報の欠落を補う目的で多くの方法が提案されてきた。すべての幾何形状の検証を利用する方法がある。この方法はロバストで高い検索適合率を達成するが、かなり長い計算時間を必要とする。より効率的な方法として、隣接する特徴間の空間関係で基本的なＶｉｓｕａｌ−Ｗｏｒｄ表現を増強するものがあるが、このアイディアに基づく方法は現状ではメモリ容量を多く必要とする。
【０００６】
画像検索の最新の方法は、Ｂａｇ−ｏｆ−Ｗｏｒｄｓ表現と拡張可能なテキスト索引方式とに依拠する傾向にある。しかし、Ｂａｇ−ｏｆ−Ｗｏｒｄｓ表現はＶｉｓｕａｌ Ｗｏｒｄｓの空間配置情報をすべて無視するので、記述能力に大きな制限があり、検索適合率が低い。空間情報の欠落を補うために、空間ピラミッドマッチング方式を利用する方法がある。これは、画像を次第に微細なサブ領域に区分し、そのサブ領域の内部でのみＶｉｓｕａｌ Ｗｏｒｄｓのマッチングを行う。この方式は高速で実装が簡単であるが、大きな幾何変換によるサブ領域の配列のずれにハード的なグリッド分割方式が影響される。
【０００７】
全体幾何検証（Ｆｕｌｌ Ｇｅｏｍｅｔｒｉｃ Ｖｅｒｉｆｉｃａｔｉｏｎ）
【０００８】
全体幾何検証法は、ＲＡＮＳＡＣまたは最小二乗中間値（Ｌｅａｓｔ Ｍｅｄｉａｎ ｏｆ Ｓｑｕａｒｅｓ、ＬＥＭＥＤＳ）等のロバストな適合方法を利用するが、一般変換を扱うことが可能であり、通常、偽マッチングを除外するために用いられる。一般的に、２つの画像間の仮変換モデルは特徴に基づいて評価される。すべての特徴は評価モデルで検証され、モデルに一致しないものがアウトライア（ｏｕｔｌｉｅｒ）として除外される。しかし、全モデルフィッティング手法は計算機処理が膨大となる。それに加えて、アウトライアのかなりの部分が量子化誤差および背景雑音から来るものであり、通常、ＲＡＮＳＡＣやＬＭＥＤＳなどの全モデルフィッティング方法は性能が低い。
【０００９】
全体幾何検証の課題に対処するために、全モデルフィッティング手法を適用する前に、効果的ではあるがより弱い幾何学的検証に基づくアウトライア・フィルタリング方式を用いる方法もある。また別の方式としては、Ｂａｇ−ｏｆ−Ｗｏｒｄｓ表現を隣接するＶｉｓｕａｌ Ｗｏｒｄｓ間の空間関係で補強しようとするものもある。例えば、従来法の１つは、Ｖｉｓｕａｌ Ｗｏｒｄｓを検出された最大定常性極値領域（ｍａｘｉｍａｌｌｙ ｓｔａｂｌｅ ｅｘｔｒｅｍａｌ ｒｅｇｉｏｎｓ、ＭＳＥＲ）によってグループに束ねて、各グループ内に幾何学的制約条件のセットを強制する。しかし、そのような方法の性能はバンドル方式のロバスト性、すなわちＭＳＥＲ検出器の再現性に大きく依存し、均一領域が僅かしか検出されないテキスト文書画像ではうまくいかない可能性が高い。別の方法では、空間コーディング方式を利用する。これは、各特徴を中心にして、この特徴と隣接する特徴との間の相対位置をコード化する。残念ながらこの方式は、全特徴に対する空間マップを格納するのに非常に大きなメモリ空間を必要とする。従ってあまり現実的ではない。
【００１０】
ハフ変換
【００１１】
別の１つの方法としては、アウトライアすなわち偽マッチングを処理するためにハフ変換を利用する方法がある。ハフ変換は、画像解析、コンピュータビジョン、およびデジタル画像処理に利用される特徴抽出手法である。この手法の目的は、ある形状のクラス内におけるオブジェクトの不完全なインスタンスを投票方式により発見することである。この投票方式はパラメータ空間で行なわれ、そこから、ハフ変換を計算するアルゴリズムによって明示的に構築されるいわゆるアキュムレータ空間における極大値として、オブジェクト候補が得られる。
【００１２】
古典的なハフ変換は画像内の直線の特定に係わるものであったが、後にハフ変換は任意の形態、特に円や楕円の位置の特定に展開されるようになった。
【００１３】
一般化ハフ変換（Ｇｅｎｅｒａｌｉｚｅｄ Ｈｏｕｇｈ Ｔｒａｎｓｆｏｒｍ、ＧＨＴ）は、ハフ変換をテンプレートマッチングの原理を利用して変形したものである。この変形により、ハフ変換を解析方程式で記述されるオブジェクト（例えば直線や円など）の検出のみならず、モデルで記述される任意のオブジェクトの検出にも利用できるようになった。
【００１４】
画像中の（モデルで記述された）オブジェクトを見つけるという問題は、画像中のモデルの位置を見つけることで解決される。一般化ハフ変換においては、モデル位置を見つける問題は、そのモデルを画像にマッピングする変換パラメータを見つけるという問題になる。変換パラメータがわかっている限り、画像中でモデル位置を判定することができる。
【００１５】
ＧＨＴの実装では、エッジ情報を利用して、エッジポイントの方向から形状の参照ポイントへのマッピングを画定する。ピクセルが黒または白の２値画像の場合、画像のすべての黒ピクセルは所望パターンの黒ピクセルとなり、ハフ空間内の参照点の位置を形成する。画像の各ピクセルが、対応する参照点に投票する。最大得票を得たハフ空間内のセル位置が、画像のパターンパラメータを示す。
【００１６】
ＧＨＴの主たる問題点は、かなりの計算時間と記憶容量を必要とすることであり、オブジェクトの方向及びスケールを考慮する必要のある場合には特に深刻となる。計算コストを低減するために、エッジの方向情報が利用されてきた。別のＧＨＴ手法、例えばＳＣ−ＧＨＴ（ローカル特性として傾斜と曲率を利用する）等も提案されてきている。
【００１７】
ハフ変換は、明らかなアウトライア（特徴の偽マッチング）を除外し、整合した変換解釈を示すインライア（ｉｎｌｉｅｒ）（特徴の真マッチング）のクラスタを特定するために利用されてきた。或る方法では、マッチングした指標付けされた特徴に対するクエリ特徴の４つのパラメータ、すなわち２次元平面上の位置、スケール及び方向を利用して、ハフ空間内の粗く量子化されたビンの１つに投票する。ビンに４票以上投入された特徴のクラスタが、最小二乗法に基づくアフィン投影パラメータの評価に利用される。別の方法では、２つのマッチングしたＶｉｓｕａｌ Ｗｏｒｄ間のスケール及び方向の違いを利用して、主要ビンに投票しない組合せを単純に除外する。
【００１８】
しかし、今日のハフ変換法は、周囲の特徴からの拘束は考慮せずに、個別の対応する特徴対に基づいて実行され、アウトライアを除外するための重要なヒントとなっている。さらに、これらの方法においては、パラメータ評価が粗いために、大きなサイズの量子化ビンを予め定めてハフ空間の投票に使用する。これではインライアとアウトライアの分離に限界があり、後続の全体幾何検証に大きな計算負荷を掛けてしまう。このようなハフ変換手法は高速ではあるが、これらのすべての方法は、非常に大雑把に評価したパラメータと、粗い、予め設定されたハフ空間と、単純な投票方式とを利用する。従って、これらの方式では、インライアからアウトライアを分離する性能がＲＡＮＳＡＣほどないことが多く、特にアフィン変換またはホモグラフィ変換などの複雑な変換に対してそうである。
【発明の概要】
【発明が解決しようとする課題】
【００１９】
本発明の方法は、画像検索の従来技術に関する１つ又は複数の前記及びその他の問題を実質的に取り除くための方法、システム及びプログラムに係わる。
【課題を解決するための手段】
【００２０】
本発明の第１の態様によれば、インライア判定ユニットにより、クエリ画像の特徴をセグメントまたはポリゴンとしてグループ化することと、前記インライア判定ユニットにより、前記クエリ画像と少なくとも１つの登録画像との間の前記特徴のセグメントまたはポリゴンの変換を計算して変換パラメータを取得することと、前記インライア判定ユニットにより、前記変換パラメータにグループ化パターンを適用することと、前記インライア判定ユニットにより、投票方式を使用して前記クエリ画像に対するインライア特徴を投票することと、幾何検証ユニットにより、前記クエリ画像からのインライア特徴の投票を使用して前記少なくとも１つの登録画像から最適マッチング登録画像を判定することと、を含む方法が提供される。
【００２１】
本発明の第２の態様によれば、上記第１の態様において、前記変換は、ＲＳＴまたはアフィン変換であってもよく、前記変換パラメータにグループ化パターンを使用することは、ハフ空間における前記変換パラメータの高密度領域を特定することを含んでもよく、前記投票方式を使用することは、前記投票方式により特徴を破棄することをさらに含んでもよく、破棄されなかった特徴をインライア特徴と判定してもよい。
【００２２】
本発明の第３の態様によれば、上記第１の態様において、前記クエリ画像と登録画像との間の変換パラメータを取得することは、前記クエリ画像の変換特徴グループを前記少なくとも１つの登録画像の変換特徴グループと比較することを含んでもよく、前記変換は、ＲＳＴまたはアフィン変換であってもよく、前記変換パラメータは、前記クエリ画像と前記少なくとも１つの登録画像に対するハフ空間におけるインライア特徴を判定するために使用されてもよい。
【００２３】
本発明の第４の態様によれば、上記第１の態様において、前記クエリ画像と前記登録画像との間の変換パラメータを取得することは、空間領域において前記クエリ画像のインライア特徴と前記登録画像の変換されたインライア特徴とを比較することにより行われてもよく、前記変換は、ＲＳＴまたはアフィン変換であってもよく、前記変換パラメータは、ハフ空間における特徴の投票に使用されてもよい。
【００２４】
本発明の第５の態様によれば、上記第１の態様において、前記登録画像からの特徴をセグメントまたはポリゴンとしてグループ化することを更に含んでもよい。
【００２５】
本発明の第６の態様によれば、上記第２の態様において、ハフ空間における変換パラメータの高密度領域を特定することは、前記クエリ画像と前記少なくとも１つの登録画像との間の前記セグメントまたはポリゴンの変換パラメータをハフ空間へマッピングすることと、ハフ空間のグリッド内のセグメントまたはポリゴンの変換パラメータの総数のピークを特定することと、前記ピークに隣接する所定の閾値を満たすグリッドを特定することと、前記ピークと前記特定されたグリッドとに基づいて高密度領域を特定することと、を更に含んでもよい。
【００２６】
本発明の第７の態様によれば、クエリ画像を受信する装置と、前記クエリ画像からの特徴をセグメントまたはポリゴンとしてグループ化し、登録された各画像からの特徴をセグメントまたはポリゴンとしてグループ化し、セグメントまたはポリゴン変換を行なって前記クエリ画像及び各登録画像に対する変換パラメータを取得し、ハフ空間における変換パラメータの高密度領域からクエリ画像のインライア特徴を選択するプロセッサと、前記クエリ画像のインライア特徴と前記各登録画像の対応するインライア特徴とをマッチングする幾何検証ユニットと、を備えるシステムが提供される。
【００２７】
本発明の第８の態様によれば、上記第７の態様において、前記ハフ空間における変換パラメータの高密度領域からクエリ画像のインライア特徴を選択することは、ハフ空間における変換された特徴の高密度領域を特定し、変換された特徴を投票方式に基づいて破棄することを含んでもよく、前記変換は、ＲＳＴまたはアフィン変換またはホモグラフィ変換であってもよく、破棄されなかった変換された特徴をインライア特徴と判定してもよい。
【００２８】
本発明の第９の態様によれば、上記第７の態様において、前記クエリ画像と前記登録画像との間のインライア特徴変換を計測することにより、前記クエリ画像と前記各登録画像との間の変換パラメータを取得するパラメータ評価ユニットを更に備えてもよく、前記変換は、ＲＳＴ、アフィン変換、またはホモグラフィ変換であってもよく、前記変換パラメータは、ハフ空間における対応するインライア特徴の判定に使用されてもよい。
【００２９】
本発明の第１０の態様によれば、上記第７の態様において、前記クエリ画像のインライア特徴と前記登録画像の変換されたインライア特徴とを空間領域で比較することにより、前記クエリ画像と前記各登録画像との間の変換パラメータを取得するパラメータ評価ユニットを更に備えてもよく、前記変換は、ＲＳＴ、アフィン変換、またはホモグラフィ変換であってもよく、前記変換パラメータは、ハフ空間における対応するインライア特徴の判定に使用されてもよい。
【００３０】
本発明の第１１の態様によれば、上記第７の態様において、前記装置は、カメラであってもよい。
【００３１】
本発明の第１２の態様によれば、上記第８の態様において、前記ハフ空間における変換パラメータの高密度領域を特定することは、前記クエリ画像と前記各登録画像との間の前記セグメントまたはポリゴン変換をハフ空間へマッピングすることと、前記ハフ空間のグリッド内の前記クエリ画像と登録画像との間のセグメントまたはポリゴン変換の総数のピークを特定することと、前記ピークに隣接する所定の閾値を満たすグリッドを特定することと、前記ピークと前記特定されたグリッドとに基づいて高密度領域を特定することと、
を更に含んでもよい。
【００３２】
本発明の第１３の態様によれば、コンピュータに、クエリ画像からの特徴をセグメントまたはポリゴンとしてグループ化することと、ハフ空間において前記セグメントまたはポリゴンの変換を算出して、前記クエリ画像のインライア特徴を判定することと、前記クエリ画像のインライア特徴を使用して最適マッチング登録画像を判定することと、を含む処理を実行させるプログラムが提供される。
【００３３】
本発明の第１４の態様によれば、上記第１３の態様において、前記クエリ画像のインライア特徴を判定することは、ハフ空間における変換パラメータの高密度領域を特定することと、投票方式に基づいて特徴を破棄することとを含んでもよく、前記変換は、ＲＳＴ、アフィン変換、またはホモグラフィ変換であってもよく、破棄されなかった特徴をインライア特徴と判定してもよい。
【００３４】
本発明の第１５の態様によれば、上記第１３の態様において、前記処理は、変換されたクエリ画像のインライア特徴を前記各登録画像の変換されたインライア特徴と比較することにより、前記クエリ画像と各登録画像との間の変換パラメータを評価することを更に含んでもよく、前記変換は、ＲＳＴ、アフィン変換、またはホモグラフィ変換であってもよく、前記変換パラメータは、ハフ空間における対応するインライア特徴の判定に使用されてもよい。
【００３５】
本発明の第１６の態様によれば、上記第１３の態様において、前記処理は、前記クエリ画像のインライア特徴を空間領域における前記各登録画像の変換されたインライア特徴と比較することにより、前記クエリ画像と各登録画像との間の変換パラメータを評価することを更に含んでもよく、前記変換は、ＲＳＴまたはアフィン変換、またはホモグラフィ変換であってもよく、前記変換パラメータは、ハフ空間における対応するインライア特徴の判定に使用されてもよい。
【００３６】
本発明の第１７の態様によれば、上記第１３の態様において、前記処理は、各登録画像からの特徴をセグメントまたはポリゴンとしてグループ化することを更に含んでもよい。
【００３７】
本発明の第１８の態様によれば、上記第１４の態様において、ハフ空間における変換された特徴の高密度領域を特定することは、前記セグメントまたはポリゴンの変換されたパラメータをハフ空間中にマッピングし、前記ハフ空間のグリッド内のセグメントまたはポリゴン変換パラメータの総数のピークを特定し、前記ピークに隣接する所定の閾値を満たすグリッドを特定し、前記ピークと前記特定されたグリッドとに基づいて高密度領域を特定することを更に含んでもよい。
【００３８】
本発明に関するその他の態様は、以下の説明で部分的に説明され、また以下の説明で部分的に明らかであり、又は本発明の実行により習得することができる。本発明の態様は、以下の詳細な説明及び添付の特許請求の範囲において特に指摘された要素、及び種々の要素と態様との組合せによって、実現及び達成をすることができる。
【００３９】
上記及び以下の記述はいずれも、単に例示及び説明を目的とするものであり、特許請求の範囲に記載の発明もしくはその適用をいかなる形であれ限定することは全く意図されていないことを理解されたい。
【図面の簡単な説明】
【００４０】
本明細書に組み込まれ、本明細書の一部をなす添付の図面が、本発明の実施形態を例示し、説明と相俟って、本発明技術の原理の説明及び例示に供する。
【図１】本発明の実施形態による２次元高密度領域検出アルゴリズムの例を示す図である。
【図２】ＲＳＴ変換画像に対するハフ変換に基づくアウトライア・フィルタリング実装例を示す図である。
【図３】本発明の実施形態による粗いハフ変換による明らかなアウトライアの除外とインライアのクラスタリングのプロセス例を示す図である。
【図４】本発明の実施形態によるＲＳＴ画像検索に対する２段階ハフ変換の例示的実装を示す図である。
【図５】本発明の実施形態によるアフィン／ホモグラフィ変換画像検索のために２次元ハフ変換のセットをバンドルし、フィルタリングされたハフ空間におけるパラメータを正確に評価する例示的実装を示す図である。
【図６】本発明の実施形態によるアフィン／ホモグラフィ変換画像検索のために、２次元ハフ変換のセットをバンドルし、モデルフィルタリング法に基づいてパラメータを正確に評価する例示的実装を示す図である。
【図７】本発明の基本的実施形態による例示的フローチャートを示す図である。
【図８】本発明の実施形態による例示的機能図である。
【図９】本発明のシステムを実装するコンピュータプラットフォームの実施形態を示す図である。
【発明を実施するための形態】
【００４１】
以下の詳細な説明においては添付の図面を参照する。ここで、同一の機能的要素は同様の符号で示される。前述の添付図面は、本発明の原理に整合する特定の実施形態および実装を例示するものであり、それに限定するためのものではない。これらの実装形態は、当業者による本発明の実行を可能とすべく詳細に記述される。また、他の実装も利用可能であること、及び本発明の範囲及び精神から逸脱することなく様々な要素の構造上の変更及び／又は代替が行われてもよいことを理解されたい。従って、以下の詳細な記述は本発明を制限するものとして解釈されるべきではない。更に、記述される本発明の様々な実施形態は、汎用コンピュータ上で実行されるソフトウェア、専用ハードウェア、あるいはソフトウェアとハードウェアの組合せ、のいずれの形態において実施されてもよい。
【００４２】
大規模なデータベースにおける特定の平面オブジェクトの検索精度を上げ、検証プロセスを高速化するために、本発明の様々な実施形態ではハフ変換を利用する。既存のハフ変換をベースとする方法における限界に対処するために、画像全体におけるマッチングポイントの関係に基づくより高精度のパラメータ評価が実行される。従来手法に比べて、より高精度のパラメータ評価をすることにより、インライア−アウトライアをより正確に分離でき、その結果として、全体幾何検証の負荷が低減されて、検索適合率は向上する。さらに、予め設定された量子化ビンの境界効果に対処するために、２次元高密度領域検出という、よりロバストな手法を利用する。これは、任意の濃度で分散する一定の特徴のクラスタを特定することが可能であり、量子化サイズにあまり依存しない。ＲＳＴ画像を検索するために、検出された高密度領域をＲＳＴパラメータの正確な値の計算に直接利用することができ、領域内の重み付きの量子化値の平均を用いてもよく（この方法はメモリをあまり必要としない）、または領域内のＭＳＳにより評価された実際の値の平均を用いてもよい（精度は上がるが、より多くのメモリを必要とする）。２００ｋ以上の画像を有する大規模データベースにおける実験では、本発明の種々の実施形態は一貫して高精度が得られる傾向がある。すなわち、ＥＭＭ特定においては９９％を超えるトップ３の精度であり、部分複製画像検出においては８．５以上のトップ１０の適合率である。さらに、メモリ使用量と計算時間もまた低くなる傾向にある。すなわち、ＥＭＭ特定では５６０ｍｓ未満で１．２ＧＢのメモリ空間であり、部分複製画像検出では１．２ｓ未満で８８０ＧＢのメモリ空間である。
【００４３】
計算の複雑さを更に低減するために、特に複雑な変換を受けた画像に対して、粗段階のハフ変換が利用される。これは、早い段階で明らかなアウトライアを除外し、インライアをクラスタにグループ化する。そして、２段階のハフ変換をしてから、幾何検証をうける。
【００４４】
アフィン／ホモグラフィ変換画像の検索に関して、最小サンプルセット（ｍｉｎｉｍｕｍ ｓａｍｐｌｅ ｓｅｔｓ、ＭＳＳ）で評価されたパラメータを用いるハフ変換をベースとする検証における大きな課題は、高次元パラメータ空間においてアウトライアの割合が高いことである。全パラメータ空間を幾つかの２次元ハフ空間に分割すると、それぞれの２次元ハフ変換ではインライアよりもむしろアウトライアにモデルが合う可能性が高い。この問題に対処するには、ハフ変換のセットを一緒にバンドルして、インライアとアウトライアのセグメント化を行う。それぞれの２次元ハフ空間は、“弱い分類器”としてサンプルの分類に用いられる。そして投票方式によって最終判定がなされる。
【００４５】
ＲＳＴ変換画像検索のためのハフ変換に基づくアウトライアのフィルタリング
【００４６】
回転−拡大縮小−平行移動（ＲＳＴ）変換画像クエリに対して、本発明の実施形態ではハフ空間フィルタリング法を活用する。画像間のマッチングポイントの各対に対して、本発明の実施形態では、パラメータのセットを取得し、ハフ空間内に蓄積して、パラメータの評価を行う。
【００４７】
ＲＡＮＳＡＣやＬＭＥＤＳの問題を克服するために、本発明の実施形態ではハフ変換の手法を活用してアウトライアをフィルタリングして除外して、検証プロセスを高速化する。そして、画像全体においてマッチングポイントに基づくより高精度のパラメータ評価を実行する。通常のハフ変換システムに比べると、より高精度のパラメータ評価を活用することで、より良好にインライアとアウトライアを分離できる。インライアとアウトライアを良好に分離することにより、全体幾何検証の負荷がさらに軽減し、認識結果を向上することができる。アウトライアのフィルタリングには次の３つのコンセプトを活用する。
【００４８】
代表的パラメータの評価
代表的パラメータの評価は最小サンプルセット（ＭＳＳ）を用いて計算される。最小サンプルセットには、モデルパラメータを判定するための最小数のサンプルすなわち特徴が含まれている。
【００４９】
ハフ変換のための高密度領域の検出
投票して主ビン（最多得票ビン）を検出するために予め定義された量子化ビンを用いる代わりに、よりロバストな、これ以降２次元高密度領域検出と呼ぶ手法を利用して、任意の密度で一定の分布している特徴のクラスタを特定する。これは量子化サイズには過度に依存しない。そのようなインライアクラスタの検出方法を順番に利用することにより、計算及びメモリ空間の複雑さを軽減することができる。
【００５０】
検出された高密度領域に基づく正確なパラメータの計算
検出された高密度領域内の特徴である、検出されたインライアに基づいて、領域内の重み付き量子化値の平均化か、領域内のＭＳＳに基づいて評価された実際の値の平均化のいずれかにより、パラメータ値を直接計算することが可能である。
【００５１】
Ｖｉｓｕａｌ Ｗｏｒｄのランク付け
クエリ画像のＶｉｓｕａｌ Ｗｏｒｄが画像中心からの距離の近い順にランク付けされる。
【００５２】
代表パラメータの評価
【００５３】
指標ポイント［ｘ，ｙ］Ｔのクエリポイント［ｕ，ｖ］ＴへのＲＳＴ変換は次のように表現される。
【数１】
【００５４】
等方的な比例縮小、回転、および平行移動はそれぞれ、ｓ、θ、［ｔｘ，ｔｙ］Ｔで表される。
【００５５】
表記を簡単にするために、ａ＝ｓ＊ｃｏｓθ、ｂ＝ｓ＊ｓｉｎθと表すと、ＲＳＴ変換は次のように書き直される。
【数２】
【００５６】
４つの変換パラメータ（ａ，ｂ，ｔｘ，ｔｙ）を解くためには、少なくとも２つの特徴が必要である。従って変換は少なくとも２つの特徴に基づいて実行され、特徴のセグメントまたはポリゴンが利用される。Ｎ個の特徴から成るセグメントまたはポリゴンが与えられているものとすると、各ＭＳＳに基づくパラメータの評価によって、式（１）に示すように、Ｎ（Ｎ−１）／２のパラメータの評価が与えられる。
【数３】
【００５７】
ここで、［Δｕｉｊ，Δｖｉｊ］Ｔ、［Δｘｉｊ，Δｙｉｊ］Ｔがそれぞれクエリポイント［ｕｉ，ｖｉ］Ｔと［ｕｊ，ｖｊ］Ｔとの差、および対応するマッチングした指標ポイント［ｘｉ，ｙｉ］Ｔと［ｘｊ，ｙｊ］Ｔとの差である。（ａｉｊ，ｂｉｊ，ｔｘｉｊ，ｔｙｉｊ）は２つの特徴に基づいて計算されるパラメータである。
【００５８】
ハフ変換のための高密度領域の検出
【００５９】
パラメータが与えられると、標準的なハフ変換手順は３つのステップで行われる。ａ）全パラメータ空間を予め設定されたビンに量子化することによりアキュムレータ空間を構築する。ｂ）各パラメータをアキュムレータ空間のビンに投入する。ｃ）パラメータが最も多い主ビンを見つける。この手順においては、２つの大きな制約がある。第１に、全パラメータ空間において主ビンを探索するのに時間的空間的複雑さが大きい。これはＯ（Ｋ１，．．．Ｋｍ）のオーダであり、ここで、Ｋｉ（１≦ｉ≦ｍ）は次元ｉの範囲であり、ｍはパラメータ数である。第２に、検出された特徴の位置誤差により、インライアから成るＭＳＳのパラメータがパラメータ空間の１点に重ならないで、ある密度でのグループになる可能性がある。従って、インライアとアウトライアとの分離が、予め設定されたビンサイズで、すべての場合にうまく機能するわけではない。予め設定されたビンサイズが小さ過ぎると、真のインライアが隣接ビンに入ってしまい、主ビンの顕現性が損なわれる可能性がある。しかし、サイズが大き過ぎると、適正なビンに多くのアウトライアが入ってしまう。
【００６０】
この複雑さの問題に対処するために、本発明の実施形態においては、全体の４パラメータ空間を２つの２次元空間、すなわちａ−ｂ空間とｔｘ−ｔｙ空間とに分解し、それを順番に結合する。本発明の実施形態では、先ずａ−ｂ空間においてハフ変換を実行してインライアを特定し、次にこれらのインライアに基づいて正確なａ，ｂの値を取得する。その後に、正確なａ，ｂの値に基づいてそれぞれの対応のｔｘ，ｔｙを計算し、再度ｔｘ−ｔｙ空間においてハフ変換を実行して正確なｔｘ、ｔｙの評価を行う。
【００６１】
第２の問題に対処するために、本発明の実施形態においては、２次元高密度領域検出アルゴリズムを利用する。そのプロセスを下の表に示し、図１で説明する。
【数４】
【００６２】
図１は本発明の実施形態による２次元高密度領域検出アルゴリズムの例を示す。この実施例では、ａ−ｂ空間は８×８のグリッド１００に量子化される。ビンａｉとｂｊとが次元ａとｂに沿って最大得票を得た主ビンとして検知される。主ビンとして検知されたそれぞれに関して、最近接のビンが検査される。そのビンが十分な得票を得ていれば（この実施例では、ａの評価式１０２およびｂの評価式１０３に対して閾値を３に設定した）、この次元の範囲を拡大して、そのビンを含むようにする。そうでない場合には終了する。拡大範囲内の領域が、検出された高密度領域１０１として判定される。
【００６３】
検出された高密度領域に基づく正確なパラメータの計算
【００６４】
検出された高密度領域に基づいて、高精度のパラメータａ、ｂ、ｔｘ、ｔｙの計算を更に進めるために２つの方法がある。
ａ）領域内の重み付き量子化値を平均する。量子化値の重みは、検出された領域内において、この次元に沿うすべてのビン内のオブジェクトの総数に対する該当するビン内のオブジェクト数として定義することができる。この方式は、各ＭＳＳから取得されたパラメータの実際の値を格納する必要がないので、高速でありかつメモリ効率が良い。
ｂ）検出された領域内のＭＳＳに基づいて評価された実際の値を平均化する。この方式はより正確である。ただし、パラメータの実際の値を格納するためにより大きなメモリを必要とし、またそれにアクセスするのに時間も長くかかる。
【００６５】
Ｖｉｓｕａｌ Ｗｏｒｄのランク付け
【００６６】
すべての特徴を変換評価に利用して記録するには、時間もかかり、メモリも多く必要である。実際には、対象となるオブジェクトは一般的に、十分な画像空間を活用し、クエリ画像の中心付近に配置されているという事実に基づいて、特徴の部分集合のみが利用される。従って、クエリ画像の中心に近い特徴が、周辺部にある特徴に比べて、ターゲット画像上に現れる可能性が高い。この事実により、本発明の実施形態においては、クエリ画像のｖｉｓｕａｌ ｗｏｒｄｓを画像中心からの距離に従って昇順にランク付けする。そして、最高ランクのクエリ特徴をデータベースとマッチングさせる際に、それらの特徴をより容易かつより早く選択できるようにする。
【００６７】
図２は、ＲＳＴ変換画像に対するハフ変換を利用したアウトライア・フィルタリングのフローチャートの例を示す。
【００６８】
特徴の最初のフィルタリングとして、Ｂａｇ ｏｆ Ｗｏｒｄｓ（ＢｏＷ）クエリがクエリ画像に適用されて、画像中心からの距離に基づいて判定及びランク付けされる（２００）。ランク付けされたＢｏＷに基づき、データベース２０２中の画像に対して最初の対応構築２０１が実行される。幾何検証２０５に利用される特徴を精選するために、クエリ中心２０３に最近接する予め設定された個数のマッチングによってハフ変換が実行され、拡大縮小と回転を処理するために、２次元並進空間２０４で別のハフ変換が行なわれる。クエリ画像と登録画像との間でインライアが導出され、ランク付けされる（２０６）。
【００６９】
フィルタリングプロセス高速化のための２段階ハフ変換
【００７０】
全てのＭＳＳでパラメータを評価することは、パラメータ数が増すに連れて多大な時間を要するようになる。さらに、パラメータ数が増加するにつれハフ変換でのインライアの割合も下がってくる。
【００７１】
このような問題に対処するために、本発明の実施形態では２段階ハフ変換方式を利用する。これは、先ず粗いハフ変換を行なって、指標付けされた特徴の位置と高密度領域検出アルゴリズムとによって明らかなアウトライアを除外し、次いで、上述の精細なハフ変換を実行してインライアを更に精選して正確なパラメータを評価する。
【００７２】
２段階ハフ変換方法の説明
【００７３】
図３は、本発明の実施形態による粗いハフ変換による明らかなアウトライアの除外とインライアのクラスタリングのプロセスの例を示す。
【００７４】
図３に示すように、粗いハフ変換に用いられるパラメータは、明らかなアウトライアを迅速に特定可能であり、その一方で、見落とすインライアは僅かしかない。評価に使用されるクエリ特徴は、画像中心の近くに位置する。従って、対応する指標付けされた特徴、つまり真の変換を示すと思われる特徴は、まとまってグループを形成する筈である。そこで特徴は、図３（ａ）に示す高密度領域検出手法に基づいて指標付けされた特徴の位置に従ってグループ化される。しかし、最大得票数の１つの領域を選択するのではなく、本発明の実施形態では、ＭをＭＳＳの濃度とすると、Ｍ個より多い特徴を含むすべての候補領域を先ず検出する（候補領域の例を図３（ｂ）に示す）。その次に、それぞれの候補領域の近傍をチェックして（図３（ｃ）の点線の円に示すように）、他のすべての候補領域から離れている領域を削除する。そして最後に、本発明の実施形態によりインライアのクラスタが取得され、図３（ｄ）に示すように各検出領域内のパラメータがＭＳＳに基づいて計算される。
【００７５】
図４は、本発明の実施形態によるＲＳＴ画像検索に対する２段階ハフ変換の例示的実装を示す。図２で用いられたハフ変換に加えて、追加的な粗いハフ変換４００を用いてフィルタリングされたマッチング点のクラスタを得てもよい。考え方としては、図２のハフ変換を、対比的に精細なハフ変換４０１と見なすことが可能である。
【００７６】
アフィン変換またはホモグラフ変換画像への拡張方法
【００７７】
本発明の実施形態で、より一般的な変換、例えばアフィン変換またはホモグラフィ変換を含む画像の処理も試みる。
【００７８】
上記の方法を利用することにより、本発明の実施形態は大規模なＲＳＴ画像検索に対して優れた性能を発揮する。しかし、この方式をアフィン／ホモグラフィ変換画像に直接適用すると以下の２つの問題に直面する。
１）６または８個のパラメータに対する計算コストはＯ（ＮＣ）の割合で顕著に増加する。ここで、Ｎは評価に利用する特徴の数であり、Ｃはモデルを評価するためのＭＳＳの濃度である。
２）パラメータ数の増加と共に、アウトライアの割合が顕著に増大する。従って、全体のパラメータ空間を幾つかの２次元ハフ空間に分割すると、各２次元ハフ空間内のアウトライアが、インライアが形成する高密度領域よりも得票数の高い高密度領域を形成する可能性が非常に大きい。言い換えると、２次元ハフ変換は、インライアよりもアウトライアで構成されたモデルに合う可能性が高い。
【００７９】
アフィン変換またはホモグラフ変換画像への拡張方法の説明
【００８０】
高い計算コストに対処するために、本発明の実施形態は、２段階でＭＳＳの数を低減する。ａ）粗いハフ変換を適用してアウトライアのいくつかを除外し、対応セット全体をいくつかのグループに分割する。ｂ）各グループのＭＳＳの数が予め設定した値を超えると、各対応に基づいてＭＳＳの部分集合を選択することのみによりでＭＳＳを更に低減する。このやり方によって計算コストを大きく低減できる。例えば、ホモグラフィ変換に対する８つのパラメータの評価に５０の特徴が与えられたとすると、すべての特徴の組合わせは膨大であって２３０３０１個のＭＳＳになってしまう。粗い変換によって特徴を２つのグループに分けて、各グループが２５個ずつを含むと仮定すると、ＭＳＳの総数は２５３００に減らすことが可能である。さらに、個別対応関係からＭＳＳの７０％しか使わないとすると、ＭＳＳ数を更に６０７５に減らすことができる。
【００８１】
第２の問題に対処するために、本発明の実施形態はインライアとアウトライアを分離するために２次元ハフ変換のセットをバンドルする。事実として、インライアは、大部分の２次元ハフ空間において一定のグループを形成する。その一方で、アウトライアは、大部分の２次元ハフ空間において密にグループ化する確率がはるかに低い。従ってそれぞれの２次元ハフ空間を“弱い分類器”と見なすことができる。サンプルが検出された高密度領域に入っていれば、それはインライア候補とされ、そうでなければアウトライアとされる。“弱い分類器”がサンプルから十分な数のインライア候補を特定する場合に、それは保存され、そうでない場合には除外される。このプロセスにおいて、インライア／アウトライアの投票数が予め設定した閾値に到達すると、２次元ハフ空間での検索を停止することができる。より厳密でより高速なアウトライアの特定法としては、“弱い分類器”を直列に結合する方法がある。この場合には、１つの“弱い分類器”が対応関係をアウトライアであるとみなすと、それは除外される。
【００８２】
第３段階のハフ空間における高精度のアフィン／ホモグラフィ評価
【００８３】
インライアを取得した後、図５と図６に示す２つの方法で変換パラメータを正確に評価することが可能である。
【００８４】
図５は、本発明の実施形態による、アフィン／ホモグラフィ変換画像検索のために、２次元ハフ変換のセット５００をバンドルし、フィルタリングされたハフ空間におけるパラメータの正確な評価をするための例示的実装を示す。正確なアフィン／ホモグラフィ評価はフィルタリングされたハフ空間５０１で実行される。評価の実行には、インライアの重み付き量子化パラメータの平均を利用するか、またはインライアから評価された実パラメータ値の平均を利用するかのいずれかが行なわれる。
【００８５】
図６は、本発明の実施形態による、アフィン／ホモグラフィ変換画像検索のために、２次元ハフ変換のセットをバンドルし、モデルフィルタリング法に基づいてパラメータの正確な評価をするための例示的実装を示す。パラメータの評価は、パラメータを空間ドメインに戻してモデルフィッティング法６００で評価することにより実行できる。
【００８６】
評価
１．ＤＬＴ、ＬＭＥＤＳ、ＲＡＮＳＡＣと本発明の実施形態による方法との性能比較
【００８７】
ＲＳＴ画像検出への適用における本発明の実施形態による方法の性能をテストするために、よく知られた別の３つのフィッティング方法、すなわちＤＬＴとＬＭＥＤＳとＲＡＮＳＡＣとの比較を行った。性能は、５つの基準に関して評価した。それらは、マッチング画像がトップ１として検出される割合(トップ1精度)、クエリあたり２０００画像のマッチングに要するマッチング時間、真のマッチング画像に対する正検出割合（ＰＰ−Ｔ）、真のマッチング画像に対する負検出割合（ＮＮ−Ｔ）、偽マッチング画像に対する負検出割合（ＮＮ−Ｆ）である。表１は、４つの手法に対するこれら５つの基準での性能を示す。この結果から、ＲＳＴ画像の検出に関しては、本発明の方法が、他の方法に比べて、すべての評価基準において優れた結果が得られることがわかる。
【表１】
【００８８】
２．本発明の実施形態に基づく大規模ＥＭＭ特定と部分複製画像検出
【００８９】
大規模なデータベース上での本発明の基本的実施形態の性能を評価するために、２つの実際の適用例である部分複製画像検出とＥＭＭ特定とに関して実験を行った。部分複製画像検出に関しては、正確性の評価基準として、トップ１０適合率、すなわちトップ１０ランクリスト内での正しい画像の平均数を用いた。ＥＭＭ特定に関しては、評価基準として、トップ３精度、すなわちターゲット画像が検出されてトップ３内にランクされるクエリ画像の割合が用いられた。
【００９０】
表２は、異なるサイズのデータセット上での部分複製画像検出の性能を示し、表３と表４は、異なるサイズのデータセット上での文書画像と自然画像のＥＭＭ特定の性能を示す。表２、３、４の結果から、本発明の基本実施形態は、データベースサイズを増やして行ってもこれらのアプリケーションにおいては一貫して高いトップ１０適合率とトップ３精度を達成することがわかる。さらに、時間とメモリのコストはデータセットのサイズに比例して増大するが、２００以上の画像を有するデータセットに対しても妥当なものとなっている。
【００９１】
【表２】
【表３】
【表４】
【００９２】
図７は、本発明の基本的実施形態による例示的フローチャートを示す。
【００９３】
クエリ画像からの特徴をセグメントまたはポリゴンとしてグループ化する（７００）。後続の変換においては少なくとも２つの特徴を利用する。従って特徴のグループは特徴のセグメントまたはポリゴンで構成される。
【００９４】
セグメントまたはポリゴンの変換を実行してクエリ画像に対するインライア特徴を判定する（７０１）。変換は、ハフ変換であってもよい。
【００９５】
クエリ画像のインライア特徴を、対応する登録画像のインライア特徴と比較する（７０２）。比較は、パラメータ空間またはハフ空間で行なってもよい。
【００９６】
図８は、本発明の実施形態による例示的機能図８００を示す。
【００９７】
クエリ画像８０１は、カメラなどの装置８０２で受信され、インライア判定ユニット８０３に供給され、クエリ画像のインライアが判定される。インライア判定ユニットは、クエリ画像の特徴をセグメントまたはポリゴンとしてグループ化するグループ化ユニットと、クエリ画像と登録画像との間の特徴のセグメントまたはポリゴンの変換を計算して変換パラメータを取得する変換パラメータ取得ユニットと、変換パラメータにグループ化パターンを適用するパターン化ユニットと、該グループ化パターンを適用することは、ハフ空間における変換パラメータの高密度領域を特定することを含んでもよく、投票方式を使用してクエリ画像に対するインライア特徴を投票する投票ユニットと、を備えてもよい。結果が幾何検証ユニット８０４に供給され、そこでクエリ画像のインライアと登録画像のインライアとの比較が行なわれる。その結果がディスプレイ８０５に表示される。
【００９８】
図９は、本発明による方法の実施形態を実装することが可能なコンピュータ／サーバシステム９００の実施形態を示すブロック図である。システム９００は、当業者には周知の命令を実行するように作用するプロセッサ９０２とメモリ９０３を含むコンピュータ／サーバプラットフォーム９０１を含む。本明細書で用いられる「コンピュータ可読媒体」という用語は、プロセッサ９０２に実行命令を与えることに関与する任意の媒体を指す。さらに、コンピュータプラットフォーム９０１は、キーボード、マウス、タッチデバイスなどの複数の入力装置９０４、または音声命令からの入力を受信する。コンピュータプラットフォーム９０１はさらに、ポータブルハードディスク装置、光学媒体（ＣＤまたはＤＶＤ）、ディスク媒体、またはコンピュータが実行命令を読み込むことができるその他の任意の媒体などのリムーバブル記憶装置９０５に接続されていてもよい。コンピュータプラットフォームはさらに、インターネットに接続されるネットワークリソース９０６、またはその他のローカルな公共または私的なネットワーク部品に接続されていてもよい。ネットワークリソース９０６は、ネットワーク９０７上のリモートロケーションから命令およびデータをコンピュータプラットフォームへ供給してもよい。ネットワークリソース９０６への接続は、８０２．１１標準やＢｌｕｅｔｏｏｔｈ（登録商標）ブルートゥースやセルラープロトコル等の無線プロトコル経由で、または、電線やファイバ光学部品などの物理的伝送媒体経由であってもよい。ネットワークリソース９０６は、コンピュータプラットフォーム９０１からは隔離した場所にデータ及び実行可能な命令を格納するための記憶装置を含んでいてもよい。コンピュータはディスプレイ９０８と相互作用して、データやその他の情報をユーザへ出力したり、ユーザからの追加の指示と入力を要求したりする。従ってディスプレイ９０８は、ユーザと対話するための入力装置９０４としての作用をさらに有してもよい。
【００９９】
さらに、ここに開示した本発明の明細書を考察し、本発明を実施すれば、本発明の他の実装が当業者には明らかとなるであろう。前述の実施態様の様々な態様及び／又は構成要素は、画像識別システムに単独もしくは任意の組み合わせで使用することが可能である。明細書及び実施例は例示としてのみ理解されるべきであり、本発明の真の範囲と精神は添付の特許請求の範囲によって示されるものとする。
【特許請求の範囲】
【請求項１】
インライア判定ユニットにより、クエリ画像の特徴をセグメントまたはポリゴンとしてグループ化することと、
前記インライア判定ユニットにより、前記クエリ画像と少なくとも１つの登録画像との間の前記特徴のセグメントまたはポリゴンの変換を計算して変換パラメータを取得することと、
前記インライア判定ユニットにより、前記変換パラメータにグループ化パターンを適用することと、
前記インライア判定ユニットにより、投票方式を使用して前記クエリ画像に対するインライア特徴を投票することと、
幾何検証ユニットにより、前記クエリ画像からのインライア特徴の投票を使用して前記少なくとも１つの登録画像から最適マッチング登録画像を判定することと、
を含む方法。
【請求項２】
前記変換は、ＲＳＴまたはアフィン変換であり、
前記変換パラメータにグループ化パターンを使用することは、ハフ空間における前記変換パラメータの高密度領域を特定することを含み、
前記投票方式を使用することは、前記投票方式により特徴を破棄することをさらに含み、
破棄されなかった特徴をインライア特徴と判定する
請求項１に記載の方法。
【請求項３】
前記クエリ画像と登録画像との間の変換パラメータを取得することは、
前記クエリ画像の変換特徴グループを前記少なくとも１つの登録画像の変換特徴グループと比較することを含み、
前記変換は、ＲＳＴまたはアフィン変換であり、
前記変換パラメータは、前記クエリ画像と前記少なくとも１つの登録画像に対するハフ空間におけるインライア特徴を判定するために使用される
請求項１に記載の方法。
【請求項４】
前記クエリ画像と前記登録画像との間の変換パラメータを取得することは、空間領域において前記クエリ画像のインライア特徴と前記登録画像の変換されたインライア特徴とを比較することにより行われ、
前記変換は、ＲＳＴまたはアフィン変換であり、
前記変換パラメータは、ハフ空間における特徴の投票に使用される
請求項１に記載の方法。
【請求項５】
前記登録画像からの特徴をセグメントまたはポリゴンとしてグループ化することを更に含む
請求項１に記載の方法。
【請求項６】
ハフ空間における変換パラメータの高密度領域を特定することは、
前記クエリ画像と前記少なくとも１つの登録画像との間の前記セグメントまたはポリゴンの変換パラメータをハフ空間へマッピングすることと、
ハフ空間のグリッド内のセグメントまたはポリゴンの変換パラメータの総数のピークを特定することと、
前記ピークに隣接する所定の閾値を満たすグリッドを特定することと、
前記ピークと前記特定されたグリッドとに基づいて高密度領域を特定することと、
を更に含む請求項２に記載の方法。
【請求項７】
クエリ画像を受信する装置と、
前記クエリ画像からの特徴をセグメントまたはポリゴンとしてグループ化し、登録された各画像からの特徴をセグメントまたはポリゴンとしてグループ化し、セグメントまたはポリゴン変換を行なって前記クエリ画像及び各登録画像に対する変換パラメータを取得し、ハフ空間における変換パラメータの高密度領域からクエリ画像のインライア特徴を選択するインライア判定ユニットと、
前記クエリ画像のインライア特徴と前記各登録画像の対応するインライア特徴とをマッチングする幾何検証ユニットと、
を備えるシステム。
【請求項８】
前記ハフ空間における変換パラメータの高密度領域からクエリ画像のインライア特徴を選択することは、
ハフ空間における変換された特徴の高密度領域を特定し、変換された特徴を投票方式に基づいて破棄することを含み、
前記変換は、ＲＳＴまたはアフィン変換またはホモグラフィ変換であり、
破棄されなかった変換された特徴をインライア特徴と判定する
請求項７に記載のシステム。
【請求項９】
前記クエリ画像と前記登録画像との間のインライア特徴変換を計測することにより、前記クエリ画像と前記各登録画像との間の変換パラメータを取得するパラメータ評価ユニットを更に備え、
前記変換は、ＲＳＴ、アフィン変換、またはホモグラフィ変換であり、
前記変換パラメータは、ハフ空間における対応するインライア特徴の判定に使用される
請求項７に記載のシステム。
【請求項１０】
前記クエリ画像のインライア特徴と前記登録画像の変換されたインライア特徴とを空間領域で比較することにより、前記クエリ画像と前記各登録画像との間の変換パラメータを取得するパラメータ評価ユニットを更に備え、
前記変換は、ＲＳＴ、アフィン変換、またはホモグラフィ変換であり、
前記変換パラメータは、ハフ空間における対応するインライア特徴の判定に使用される
請求項７に記載のシステム。
【請求項１１】
前記装置は、カメラである
請求項７に記載のシステム。
【請求項１２】
前記ハフ空間における変換パラメータの高密度領域を特定することは、
前記クエリ画像と前記各登録画像との間の前記セグメントまたはポリゴン変換をハフ空間へマッピングすることと、
前記ハフ空間のグリッド内の前記クエリ画像と登録画像との間のセグメントまたはポリゴン変換の総数のピークを特定することと、
前記ピークに隣接する所定の閾値を満たすグリッドを特定することと、
前記ピークと前記特定されたグリッドとに基づいて高密度領域を特定することと、
を更に含む
請求項８に記載のシステム。
【請求項１３】
コンピュータに、
クエリ画像からの特徴をセグメントまたはポリゴンとしてグループ化することと、
ハフ空間において前記セグメントまたはポリゴンの変換を算出して、前記クエリ画像のインライア特徴を判定することと、
前記クエリ画像のインライア特徴を使用して最適マッチング登録画像を判定することと、
を含む処理を実行させるプログラム。
【請求項１４】
前記クエリ画像のインライア特徴を判定することは、ハフ空間における変換パラメータの高密度領域を特定することと、投票方式に基づいて特徴を破棄することとを含み、
前記変換は、ＲＳＴ、アフィン変換、またはホモグラフィ変換であり、
破棄されなかった特徴をインライア特徴と判定する
請求項１３に記載のプログラム。
【請求項１５】
前記処理は、変換されたクエリ画像のインライア特徴を前記各登録画像の変換されたインライア特徴と比較することにより、前記クエリ画像と各登録画像との間の変換パラメータを評価することを更に含み、
前記変換は、ＲＳＴ、アフィン変換、またはホモグラフィ変換であり、
前記変換パラメータは、ハフ空間における対応するインライア特徴の判定に使用される
請求項１３に記載のプログラム。
【請求項１６】
前記処理は、前記クエリ画像のインライア特徴を空間領域における前記各登録画像の変換されたインライア特徴と比較することにより、前記クエリ画像と各登録画像との間の変換パラメータを評価することを更に含み、
前記変換は、ＲＳＴまたはアフィン変換、またはホモグラフィ変換であり、
前記変換パラメータは、ハフ空間における対応するインライア特徴の判定に使用される
請求項１３に記載のプログラム。
【請求項１７】
前記処理は、各登録画像からの特徴をセグメントまたはポリゴンとしてグループ化することを更に含む
請求項１３に記載のプログラム。
【請求項１８】
ハフ空間における変換された特徴の高密度領域を特定することは、
前記セグメントまたはポリゴンの変換されたパラメータをハフ空間中にマッピングし、
前記ハフ空間のグリッド内のセグメントまたはポリゴン変換パラメータの総数のピークを特定し、
前記ピークに隣接する所定の閾値を満たすグリッドを特定し、
前記ピークと前記特定されたグリッドとに基づいて高密度領域を特定することを更に含む
請求項１４に記載のプログラム。
【請求項１】
インライア判定ユニットにより、クエリ画像の特徴をセグメントまたはポリゴンとしてグループ化することと、
前記インライア判定ユニットにより、前記クエリ画像と少なくとも１つの登録画像との間の前記特徴のセグメントまたはポリゴンの変換を計算して変換パラメータを取得することと、
前記インライア判定ユニットにより、前記変換パラメータにグループ化パターンを適用することと、
前記インライア判定ユニットにより、投票方式を使用して前記クエリ画像に対するインライア特徴を投票することと、
幾何検証ユニットにより、前記クエリ画像からのインライア特徴の投票を使用して前記少なくとも１つの登録画像から最適マッチング登録画像を判定することと、
を含む方法。
【請求項２】
前記変換は、ＲＳＴまたはアフィン変換であり、
前記変換パラメータにグループ化パターンを使用することは、ハフ空間における前記変換パラメータの高密度領域を特定することを含み、
前記投票方式を使用することは、前記投票方式により特徴を破棄することをさらに含み、
破棄されなかった特徴をインライア特徴と判定する
請求項１に記載の方法。
【請求項３】
前記クエリ画像と登録画像との間の変換パラメータを取得することは、
前記クエリ画像の変換特徴グループを前記少なくとも１つの登録画像の変換特徴グループと比較することを含み、
前記変換は、ＲＳＴまたはアフィン変換であり、
前記変換パラメータは、前記クエリ画像と前記少なくとも１つの登録画像に対するハフ空間におけるインライア特徴を判定するために使用される
請求項１に記載の方法。
【請求項４】
前記クエリ画像と前記登録画像との間の変換パラメータを取得することは、空間領域において前記クエリ画像のインライア特徴と前記登録画像の変換されたインライア特徴とを比較することにより行われ、
前記変換は、ＲＳＴまたはアフィン変換であり、
前記変換パラメータは、ハフ空間における特徴の投票に使用される
請求項１に記載の方法。
【請求項５】
前記登録画像からの特徴をセグメントまたはポリゴンとしてグループ化することを更に含む
請求項１に記載の方法。
【請求項６】
ハフ空間における変換パラメータの高密度領域を特定することは、
前記クエリ画像と前記少なくとも１つの登録画像との間の前記セグメントまたはポリゴンの変換パラメータをハフ空間へマッピングすることと、
ハフ空間のグリッド内のセグメントまたはポリゴンの変換パラメータの総数のピークを特定することと、
前記ピークに隣接する所定の閾値を満たすグリッドを特定することと、
前記ピークと前記特定されたグリッドとに基づいて高密度領域を特定することと、
を更に含む請求項２に記載の方法。
【請求項７】
クエリ画像を受信する装置と、
前記クエリ画像からの特徴をセグメントまたはポリゴンとしてグループ化し、登録された各画像からの特徴をセグメントまたはポリゴンとしてグループ化し、セグメントまたはポリゴン変換を行なって前記クエリ画像及び各登録画像に対する変換パラメータを取得し、ハフ空間における変換パラメータの高密度領域からクエリ画像のインライア特徴を選択するインライア判定ユニットと、
前記クエリ画像のインライア特徴と前記各登録画像の対応するインライア特徴とをマッチングする幾何検証ユニットと、
を備えるシステム。
【請求項８】
前記ハフ空間における変換パラメータの高密度領域からクエリ画像のインライア特徴を選択することは、
ハフ空間における変換された特徴の高密度領域を特定し、変換された特徴を投票方式に基づいて破棄することを含み、
前記変換は、ＲＳＴまたはアフィン変換またはホモグラフィ変換であり、
破棄されなかった変換された特徴をインライア特徴と判定する
請求項７に記載のシステム。
【請求項９】
前記クエリ画像と前記登録画像との間のインライア特徴変換を計測することにより、前記クエリ画像と前記各登録画像との間の変換パラメータを取得するパラメータ評価ユニットを更に備え、
前記変換は、ＲＳＴ、アフィン変換、またはホモグラフィ変換であり、
前記変換パラメータは、ハフ空間における対応するインライア特徴の判定に使用される
請求項７に記載のシステム。
【請求項１０】
前記クエリ画像のインライア特徴と前記登録画像の変換されたインライア特徴とを空間領域で比較することにより、前記クエリ画像と前記各登録画像との間の変換パラメータを取得するパラメータ評価ユニットを更に備え、
前記変換は、ＲＳＴ、アフィン変換、またはホモグラフィ変換であり、
前記変換パラメータは、ハフ空間における対応するインライア特徴の判定に使用される
請求項７に記載のシステム。
【請求項１１】
前記装置は、カメラである
請求項７に記載のシステム。
【請求項１２】
前記ハフ空間における変換パラメータの高密度領域を特定することは、
前記クエリ画像と前記各登録画像との間の前記セグメントまたはポリゴン変換をハフ空間へマッピングすることと、
前記ハフ空間のグリッド内の前記クエリ画像と登録画像との間のセグメントまたはポリゴン変換の総数のピークを特定することと、
前記ピークに隣接する所定の閾値を満たすグリッドを特定することと、
前記ピークと前記特定されたグリッドとに基づいて高密度領域を特定することと、
を更に含む
請求項８に記載のシステム。
【請求項１３】
コンピュータに、
クエリ画像からの特徴をセグメントまたはポリゴンとしてグループ化することと、
ハフ空間において前記セグメントまたはポリゴンの変換を算出して、前記クエリ画像のインライア特徴を判定することと、
前記クエリ画像のインライア特徴を使用して最適マッチング登録画像を判定することと、
を含む処理を実行させるプログラム。
【請求項１４】
前記クエリ画像のインライア特徴を判定することは、ハフ空間における変換パラメータの高密度領域を特定することと、投票方式に基づいて特徴を破棄することとを含み、
前記変換は、ＲＳＴ、アフィン変換、またはホモグラフィ変換であり、
破棄されなかった特徴をインライア特徴と判定する
請求項１３に記載のプログラム。
【請求項１５】
前記処理は、変換されたクエリ画像のインライア特徴を前記各登録画像の変換されたインライア特徴と比較することにより、前記クエリ画像と各登録画像との間の変換パラメータを評価することを更に含み、
前記変換は、ＲＳＴ、アフィン変換、またはホモグラフィ変換であり、
前記変換パラメータは、ハフ空間における対応するインライア特徴の判定に使用される
請求項１３に記載のプログラム。
【請求項１６】
前記処理は、前記クエリ画像のインライア特徴を空間領域における前記各登録画像の変換されたインライア特徴と比較することにより、前記クエリ画像と各登録画像との間の変換パラメータを評価することを更に含み、
前記変換は、ＲＳＴまたはアフィン変換、またはホモグラフィ変換であり、
前記変換パラメータは、ハフ空間における対応するインライア特徴の判定に使用される
請求項１３に記載のプログラム。
【請求項１７】
前記処理は、各登録画像からの特徴をセグメントまたはポリゴンとしてグループ化することを更に含む
請求項１３に記載のプログラム。
【請求項１８】
ハフ空間における変換された特徴の高密度領域を特定することは、
前記セグメントまたはポリゴンの変換されたパラメータをハフ空間中にマッピングし、
前記ハフ空間のグリッド内のセグメントまたはポリゴン変換パラメータの総数のピークを特定し、
前記ピークに隣接する所定の閾値を満たすグリッドを特定し、
前記ピークと前記特定されたグリッドとに基づいて高密度領域を特定することを更に含む
請求項１４に記載のプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１３−２５７９９（Ｐ２０１３−２５７９９Ａ）
【公開日】平成２５年２月４日（２０１３．２．４）
【国際特許分類】
【出願番号】特願２０１２−１４９７２６（Ｐ２０１２−１４９７２６）
【出願日】平成２４年７月３日（２０１２．７．３）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
【公開日】平成２５年２月４日（２０１３．２．４）
【国際特許分類】
【出願日】平成２４年７月３日（２０１２．７．３）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
[ Back to top ]