(57)【要約】      （修正有）【課題】クライアントにおけるリソース消費を削減しながら、画像探索のためのスケール不変の画像特徴のランダム化された埋込みを可能にする。【解決手段】画像からスケール不変の特徴が抽出される。それらの特徴は、それらの特徴にランダムエントリの行列を乗算することによって、より低い次元のランダム射影行列に射影される。ランダム射影の行列は量子化され、量子化インデックスの行列が生成される。量子化インデックスは、画像のデータベースを探索して画像に関するメタデータを検索するためのクエリベクトルを形成する。【選択図】図１Ａ
2014002723.tif 000002
【特許請求の範囲】
【請求項１】
画像を表現する方法であって、
前記画像から特徴を抽出するステップであって、前記特徴はスケール不変である、抽出するステップと、
前記特徴にランダムエントリの行列を乗算することによって、前記特徴を射影してランダム射影の行列を生成する、射影するステップと、
前記ランダム射影の行列を量子化して、量子化インデックスの行列を生成する、量子化するステップとを含み、前記ステップはクライアントにおいてプロセッサによって実行される、画像を表現する方法。
【請求項２】
前記クライアントは移動デバイスリソースである、請求項１に記載の方法。
【請求項３】
請求項１に記載の方法であって、
前記量子化行列はクエリベクトルであり、
前記方法は、
前記クエリベクトルをサーバに送信するステップと、
前記抽出、前記乗算、及び前記量子化に関して、前記画像と類似して表される画像を求めてデータベースを探索することによって、前記画像に関するメタデータを受信するステップと、
を更に含む、方法。
【請求項４】
前記送信のレートは前記量子化の間隔に依拠する、請求項３に記載の方法。
【請求項５】
前記送信は、前記量子化インデックスの要素ごとの固定長コーディングを用いる、請求項２に記載の方法。
【請求項６】
前記ランダムエントリの行列を生成するためのシードは前記クライアント及び前記サーバにおいて同一である、請求項３に記載の方法。
【請求項７】
前記クエリベクトルは、
【数１】
2014002723.tif 000028
ビットであり、ここで、前記ランダム射影の数はｋであり、前記量子化のレベル数はＬであり、特徴数はＭである、請求項３に記載の方法。
【請求項８】
請求項７に記載の方法であって、
前記ランダム射影の数ｋ、前記量子化のレベル数Ｌ、又は前記特徴数Ｍを削減することによって送信電力を最小化するステップを更に含む、方法。
【請求項９】
前記探索は最近傍探索である、請求項３に記載の方法。
【請求項１０】
前記サーバは、クエリ画像について合致発生数を求め、前記メタデータは、最も高い発生数を有する画像データベース内の前記画像に関する、請求項３に記載の方法。
【請求項１１】
前記最近傍探索は、前記画像と前記画像データベースとの間のユークリッド距離を用いる、請求項９に記載の方法。
【請求項１２】
前記量子化は、前記ランダム射影の行列の各要素に個々に適用される非均一スカラー量子化器を用いる、請求項１に記載の方法。
【請求項１３】
前記量子化は、前記ランダム射影の行列内の要素群に個々に適用されるベクトル量子化器である、請求項１に記載の方法。
【請求項１４】
前記量子化インデックスの行列の、サーバへの前記送信は、
前記量子化インデックスの可変長エントロピーコーディングを用いることを含む、請求項１に記載の方法。
【請求項１５】
請求項１に記載の方法であって、
前記射影によって前記特徴の次元を削減するステップを更に含む、方法。
【請求項１６】
請求項１５に記載の方法であって、
前記射影による前記次元削減と、前記量子化のレベル数との平衡をとるステップを更に含む、方法。
【請求項１７】
前記量子化は、前記各ランダム射影に別個に適用される均一スカラー量子化器を用いる、請求項１に記載の方法。
【請求項１８】
前記次元削減は前記特徴の対間の距離を保持する、請求項１５に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、画像から特徴を抽出することに関し、より詳細には、特徴を用いてデータベースに問い合わせることに関する。
【背景技術】
【０００２】
拡張現実は、演算デバイス、より詳細には移動デバイスにおける最近の進歩を利用する重要な用途である。移動デバイスには、移動電話（携帯電話）、個人用携帯情報端末（ＰＤＡ）、タブレットコンピューター等のクライアントを含めることができる。そのようなデバイスは、メモリリソース、処理リソース、計算リソース、及び電力リソースが限られている。このため、拡張現実用途は、移動環境において特別な課題を呈している。
【０００３】
上記デバイスは、カメラ又はネットワークを用いて画像又は映像を取得することができる。画像は、現実世界のシーン、又はコンピューターグラフィック画像若しくはアニメーション映像等の合成データとすることができる。次に、デバイスは、画像又は映像の上に有用な情報を重ねることによってユーザー体験を拡張させることができる。有用な情報はメタデータの形態をとることができる。
【０００４】
例えば、メタデータは、歴史的建造物に関する情報、食品に関する栄養成分情報、又は画像内の（線形の又は行列の）バーで識別された製品に関する情報とすることができる。
【０００５】
そのような用途を可能にするために、デバイスリソースに対する制限を認識しながら、画像認識における最近の進歩を利用することが必要である。このため、通常の拡張現実用途において、移動デバイスは、クエリ画像の顕著な特徴を、多数の画像又は映像を記憶するサーバにおけるデータベースに効率的に送信しなくてはならない。データベースサーバは、クエリ画像がデータベース内のエントリに合致するか否かを迅速に判断し、適切なメタデータを移動デバイスに返すべきである。
【０００６】
多くの画像ベースの拡張現実用途は、スケール不変の特徴変換（ＳＩＦＴ：Ｓｃａｌｅ−Ｉｎｖａｒｉａｎｔ  Ｆｅａｔｕｒｅ  Ｔｒａｎｓｆｏｒｍ）、高速化ロバスト特徴（ＳＵＲＦ：Ｓｐｅｅｄｅｄ  Ｕｐ  Ｒｏｂｕｓｔ  Ｆｅａｔｕｒｅ）、及びＧＩＳＴを用いる。例えば、米国特許出願公開第２０１１／０１９４７３７号を参照されたい。
【０００７】
ＳＩＦＴ及びＳＵＲＦは、画像内の局所的な詳細を取得し、したがって、局所的な特徴又はパッチをマッチングするのに用いられてきた。ＳＩＦＴ及びＳＵＲＦは、例えば一般的な「特徴バッグ（Ｂａｇ−ｏｆ−Ｆｅａｔｕｒｅｓ）」手法を用いて幾つかのパッチからの仮説を組み合わせることによる画像マッチング及び画像検索にも用いることができる。ＧＩＳＴは画像の大域特性を取得し、画像マッチングに用いられてきた。ＧＩＳＴベクトルは、シーンのカテゴリのメモリ表現、例えば、建物、風景、ランドマーク等をアクティベートすることができるシーンの抽象表現である。
【０００８】
ＳＩＦＴは、平行移動、回転、及び限られた量のスケーリング等の一般的な画像変形の存在下で最良の性能を有する。名目上、画像内の単一の角点（ｓａｌｉｅｎｔ  ｐｏｉｎｔ）のＳＩＦＴ特徴ベクトルは実数値の単位ノルム１２８次元ベクトルである。これによって、信頼性のあるマッチングのために幾つかの角点からの特徴が必要である場合に特に、クライアントが画像マッチングの目的でＳＩＦＴ特徴をデータベースサーバに送信するために必要とされる極めて大きなビットレートが要求される。
【０００９】
画像記述子を圧縮するための幾つかのトレーニングベースの方法が既知である。ブースト類似性感知コーディング（ＢｏｏｓｔＳＳＣ：Ｂｏｏｓｔｉｎｇ  Ｓｉｍｉｌａｒｉｔｙ  Ｓｅｎｓｉｔｉｖｅ  Ｃｏｄｉｎｇ）及び制約付きボルツマンマシン（ＲＢＭ）がコンテンツベースの画像検索のためのコンパクトＧＩＳＴコードを学習するために既知である。意味論的ハッシングがスペクトルハッシング問題に変換される。スペクトルハッシング問題では、ＧＩＳＴ特徴の固有関数を計算することしか必要でなく、ＢｏｏｓｔＳＳＣ及びＲＢＭよりも良好な検索性能が得られる。
【００１０】
これらの比較的最近開発された機械学習方法に加えて、主成分分析（ＰＣＡ）及び線形判別分析（ＬＤＡ）等の、幾つかの従来のトレーニングベースの技法も、コンパクトな画像記述子を生成するのに用いられてきた。特に、ＰＣＡは、直積量子化及び分散ソースコーディング等の技法を適用することによって小さな画像記述子を生成するのに用いられてきた。代替的に、ＳＩＦＴに似た記述子（ＳＩＦＴ−ｌｉｋｅ  ｄｅｓｃｒｉｐｔｏｒ）にＬＤＡを適用し、その後バイナリ量子化を適用することによって小さな画像記述子を得ることができる。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
トレーニングベースの方法は、従来の画像検索では正確に機能するが、新たなランドマーク、製品等が加えられるとともにデータベースが継続的に展開していき、結果として新たな画像統計が生じ、繰返しトレーニングすることが必要となる拡張現実用途では、これらの方法は煩雑になる可能性がある。
【００１２】
トレーニングベースの次元削減に対する、ソースコーディングベース代替案として、低ビットレート記述子が、特に拡張現実用途の場合に圧縮勾配ヒストグラム（ＣＨｏＧ：Ｃｏｍｐｒｅｓｓｅｄ  Ｈｉｓｔｏｇｒａｍ  ｏｆ  Ｇｒａｄｉｅｎｔｓ）を用いる。その方法において、勾配分布は明示的に圧縮され、結果として低レートのスケール不変の記述子が得られる。
【００１３】
計算的により単純であるが、ＣＨｏＧよりも帯域幅効率が低く、トレーニングを必要としない局所性鋭敏型ハッシュ（ＬＳＨ）に基づく効率的な遠隔画像マッチングのための他の技法が知られている。スケール不変の特徴からランダム射影が求められ、その後１ビット量子化が行われる。結果として得られる記述子を用いて、無線カメラネットワーク内で取得された画像間の視覚的対応が確立される。同じ技法は、コンテンツベースの画像検索にも適用することができ、最近傍探索の指定の精度を得るのに必要な最小ビット数について制限が得られる。しかしながら、これらの方法は、次元削減と量子化レベルとの間のトレードオフを考慮しない。
【課題を解決するための手段】
【００１４】
本発明の実施の形態は、画像から特徴を抽出することによって画像を表現する方法を提供する。１つの実施の形態では、画像はクエリ画像である。この表現はクライアントにおいて実行することができ、抽出された特徴は、マッチングのために、類似して表現された画像を求めてデータベースを探索するようにサーバに送信することができる。マッチング画像のメタデータはクライアントに返すことができる。
【００１５】
本方法は、クエリ画像からスケール不変の特徴を抽出する。次に、特徴の少数の量子化されたランダム射影が求められ、量子化される。量子化された射影を用いて、類似した形態で画像を記憶するサーバにおいてデータベースを探索する。
【００１６】
サーバは、量子化されたランダム射影の低次元部分空間において最近傍探索を実行し、クエリ画像に対応するメタデータを返す。
【００１７】
従来技術は、画像特徴のバイナリ埋込みによって効率的な画像検索が可能になることを示した。
【００１８】
本発明の実施の形態によって、ランダム射影の数と、射影を記憶するのに用いられるビット数、すなわち量子化レベルとの平衡をとるトレードオフが可能になる。
【００１９】
理論的結果によって、総ビットレート制約の下でのビット配分方式が提案される。多くの場合に、多数の粗く量子化されたランダム射影よりも、少数の細かく量子化されたランダム射影におけるビットを用いることが望ましい。
【００２０】
本方法は、移動クライアントデバイスが画像ごとに２．５ｋＢしかサーバに送信することを必要とせずに、最大で９４％の検索精度を達成する。これは、当該技術分野において既知の１ビット量子化方式を大幅に上回る改善である。
【００２１】
このため、本方法は、リソースが制約される移動クライアント用途に特に適している。
【発明の効果】
【００２２】
本発明の実施の形態は、従来技術のようにスケール不変の特徴を直接用いることと比較して、クライアントにおけるリソース消費を削減しながら、画像探索のためのスケール不変の画像特徴のランダム化された埋込みを可能にする。
【００２３】
帯域幅が制約される場合、非コヒーレントな射影数を増大させるようにビットを配分することが理にかなっている。一方、或る特定の最小数のランダム射影が満たされた後、粗く量子化されたランダム射影数を増大させ続けるのではなく、高い忠実度で射影を表すように任意の追加のビットを利用することがより有利である。
【図面の簡単な説明】
【００２４】
【図１Ａ】本発明の実施形態による、クライアントによって画像を表現する方法の流れ図である。
【図１Ｂ】本発明の実施形態による、画像を表現する方法の疑似コードである。
【図２】本発明の実施形態による、サーバにおいて画像を表現する方法の疑似コードである。
【図３】本発明の実施形態による、データベースを探索する方法の疑似コードである。
【図４】実施形態の動作の概略図である。
【発明を実施するための形態】
【００２５】
本発明の実施形態は、クライアントにおいてクエリ画像から特徴を抽出する方法を提供する。特徴はサーバに送信することができ、データベースを探索して、類似した画像、及び拡張現実用途において適切な画像固有のメタデータを検索するのに用いることができる。
【００２６】
図１は、画像１０１を表現する方法を示している。特徴１０２が画像から抽出される（１１０）。本方法は、映像内のような一連の画像に適用することができることが理解される。画像は実世界のシーン又は合成データからなることができる。画像は、内蔵のカメラによって直接取得することもできるし、ネットワークを介してダウンロードすることもできる。
【００２７】
特徴はスケール不変である。特徴は、ランダムエントリの行列１０３を乗算され（１２０）、ランダム射影の行列１２１が得られる。このランダム射影の行列は量子化され（１３０）、画像を表現する量子化インデックスの行列１０４が生成される。このインデックス行列はクエリベクトルに再構成することができる。
【００２８】
クエリベクトルはサーバに送信され、サーバは、類似した画像を求めてデータベース１５１を探索し（１４０）、クライアントのためのメタデータ１５２を検索する。
【００２９】
量子化されたランダム埋込み
本発明は、一つには、画像から抽出されたスケール不変の特徴の低次元の埋込みに基づく。埋込みの使用は、本発明者らの理論展開の開始点を成す以下の結果によって正当であるとされる。
【００３０】
定理１
ジョンソン−リンデンシュトラウスの補題：実数ε∈（０，１）及び点ｎの場合、正の整数ｋは以下の式となる。
【００３１】
【数１】
2014002723.tif 000003
【００３２】
この補題は、高次元空間内の点、例えば特徴の小さな集合を、点間の距離を依然として保持しながら、実質的により低い次元を有する空間内に埋め込むことができることを意味する。
【００３３】
このとき、ｎ個の点を含む任意の集合Ｘ⊂Ｒｄについて、ランダム多項式時間において計算可能なマッピングｆ：Ｒｄ→Ｒｋが存在し、それによって、全てのｕ，ｖ∈Ｘ、例えば画像Ｘ内のロケーション（ｕ，ｖ）にあるピクセルについて、以下の式が成り立つ。
【００３４】
【数２】
2014002723.tif 000004
【００３５】
上記の結果から、所与のεについて、ｆの範囲内の点の次元ｋが、Ｘ内の点の次元から独立しており、Ｘ内の点の数の対数に比例するという認識が得られる。ｋはｌｎ  ｎとともに増大するので、ジョンソン−リンデンシュトラウスの補題は次元削減結果を確立し、ここで、ｄ次元ユークリッド空間内のｎ個の点（特徴）からなる任意の集合をｋ次元のユークリッド空間に埋め込むことができる。これは、幾つかの属性、すなわち大きなｄを用いて非常に大きなデータベース、すなわち大きなｎに問い合わせる場合に非常に有益である。
【００３６】
埋込み関数ｆを構築する１つの方法は、Ｘからの点（特徴）を、原点を通る球状にランダムな超平面上に射影することである。実際には、これは、データベクトルを、独立同一分布を有する（ｉ．ｉ．ｄ．）各ランダム変数の行列１０３と乗算することによって達成される。特に、独立同一分布を有するＮ（０，１）個のエントリを有するランダム行列は、高い確率で定理１において距離保持特性を提供する。以下の結果によってこの概念（ｎｏｔｉｏｎ）が正確なものとなる。
【００３７】
定理２  実数ε，β＞０について、以下となるような正の整数ｋが存在するものとする。
【００３８】
【数３】
2014002723.tif 000005
【００３９】
行列Ａ∈Ｒｋ×ｄを検討する。この行列のエントリａ（ｉ，ｊ）は、Ｎ（０，１）の分布から独立同一分布で取り出される。ｎ個の点を含む集合Ｘ∈Ｒｄが存在するものとする。このとき、全てのｕ∈Ｘについて、マッピング
【数４】
2014002723.tif 000006
は、少なくとも１−ｎ−βの大きさの確率で定理１において距離保持特性を満たす。
【００４０】
構築によって、ｆ（ｕ）はｄ次元のベクトルのｋ次元の埋込みとなる。定理２は、正規分布に加えて、ａ（ｉ，ｊ）に対する他の分布についても成り立つ。一方、以下では正規ガウス分布のみを検討する。
【００４１】
本発明者らは、量子化された埋込みの場合、すなわちｆ（ｕ）及びｆ（ｖ）の各要素に対し均一スカラー量子化器が独立して用いられる場合の距離保持特性に関心を有する。定理２は、量子化されていない場合に、埋込みｆが確率１−ｎ−βでεの精度（ε−ａｃｃｕｒａｔｅ）であることを示す。本発明者らは、埋込みを記憶又は送信するのに必要とされるビットレートを削減するのに量子化が用いられるときの埋込み精度を記述する。さらに、本発明者らは、量子化レベル数と、特定の帯域幅を用いて送信することができる射影数ｋとの平衡をとるトレードオフに関心を有する。
【００４２】
以下の命題は、このトレードオフを理解する第１のステップである。
【００４３】
命題１
実数β＞０及びε∈（０，１）について、（１）を満たす正の整数ｋが存在するとする。行列Ａ∈Ｒｋ×ｄを検討する。この行列のエントリａ（ｉ，ｊ）は、Ｎ（０，１）の分布から独立同一分布で取り出される。ｎ個の点を含む集合Ｘ∈Ｒｄが存在するものとする。任意のベクトルｗについて、ｑ（ｗ）が、ｗの各要素に独立して適用されるステップサイズΔを有する均一スカラー量子化器であるとする。このとき、全てのｕ，ｖ∈Ｘについて、マッピング
【数５】
2014002723.tif 000007
は、少なくとも１−ｎ−βの大きさの確率で以下の式を満たす。
【００４４】
【数６】
2014002723.tif 000008
【００４５】
証明
まず、量子化ｑ（Ａｕ）によって、任意のｘについて、次元あたり最大でΔ／２の誤りが生じる、すなわち、
【数７】
2014002723.tif 000009
であることに留意されたい。これを、定理２のように
【数８】
2014002723.tif 000010
とともに用いて、
【数９】
2014002723.tif 000011
を得る。ここで、ε∈（０，１）について
【数１０】
2014002723.tif 000012
及び
【数１１】
2014002723.tif 000013
であることに留意して定理１のステートメント（ｓｔａｔｅｍｅｎｔ）の二乗根をとると、以下が得られる。
【００４６】
【数１２】
2014002723.tif 000014
【００４７】
このとき定理のステートメントの右辺（ｒｉｇｈｔ  ｈａｌｆ）は、三角不等式から以下のようになる。
【００４８】
【数１３】
2014002723.tif 000015
【００４９】
左辺（ｌｅｆｔ  ｈａｌｆ）の証明も同様である。
【００５０】
量子化された埋込みの精度は、スカラー量子化間隔Δに依拠する。そしてこのスカラー量子化間隔Δは、スカラー量子化器の設計及び各係数を符号化するのに用いられるビットレートＢに依拠する。
【００５１】
飽和レベル±Ｓを有する有限均一スカラー量子化器を検討する。この飽和レベル±Ｓは、飽和が十分稀であり、無視することができるように設定されると仮定する。このため、量子化器の範囲２Ｓを均一に分割するのにＢ個のビットが用いられ、量子化間隔Δ＝２−Ｂ＋１Ｓとなる。
【００５２】
Ｒを用いてｋ個の射影を送信するのに利用可能なビットレートを表すと、すなわち測定あたりＢ＝Ｒ／ｋ個のビットを設定すると、量子化間隔はΔ＝２−Ｒ／ｋ＋１Ｓとなる。このため、命題１に内在するトレードオフは、射影数と、測定あたりのビット数との平衡をとり、これは以下のように、より明示的となる。
【００５３】
【数１４】
2014002723.tif 000016
【００５４】
特に、固定レートＲの射影数を増大させると、測定あたりの平均レートが減少し、したがって量子化間隔Δが増大する。そして、これによって、加法因子
【数１５】
2014002723.tif 000017
によって与えられる量子化誤り曖昧性が増大する。
【００５５】
さらに、射影数を増大させることによってεが削減され、したがって、乗法因子（１±ε）によって与えられる、定理２に起因する曖昧性が削減される。固定のβ及びｎについて、εは小さい場合に
【数１６】
2014002723.tif 000018
に概ね比例してスケーリングする。
【００５６】
２つの更なる問題、すなわち非均一量子化及び飽和の問題が存在する。非均一スカラー量子化器を射影の分布に調整することによって、埋込みの性能を改善することができる。一方、量子化は依然として、測定あたりのビット数と、射影数との間の同じトレードオフを被る。同様に、均一な量子化器の飽和レートを調節することは、量子化器を射影の分布に調整する１つの方法である。量子化器Ｓの範囲を削減することによって、量子化間隔Δ及び量子化に起因した曖昧性が削減される。
【００５７】
しかしながら、飽和の確率は増大し、その結果、飽和に起因した無制限の誤りによって、上記のモデルが無効となり、理論限界が適用不可能となる。量子化されたランダム射影からの圧縮感知再構築に関連して、飽和レートの綿密な調整によって性能を改善することができる。
【００５８】
上記の理論的展開は、単に射影の正負符号を保持することによって実行される、射影あたり１ビットの量子化の場合に失敗する。対象の集合内の２つの信号が互いの正のスカラー倍である場合、それらは埋込み内で区別不可能である。制限されたノルム信号の場合、保証が依然として成立するが、制限は多くの場合に緩やか過ぎて有用でない。２つの信号間の角度、すなわちそれらの距離ではなく相関に関心があるとき、より厳しい制限を代わりに展開することができる。
【００５９】
スケール不変の画像特徴の埋込み
次に、スケール不変の特徴の量子化された埋込みを有するクエリ画像１０１を用いてサーバデータベースから画像固有のメタデータを検索するための本発明による方法を説明する。
【００６０】
例示的な用途では、移動クライアントデバイス、例えば携帯電話のユーザーが、遺跡の歴史、又は食品の栄養成分情報等の、クエリ画像に関する更なる情報を得ることを所望する。ユーザーは、デバイス内のカメラを用いてクエリ画像を取得するか、又はネットワークを介して画像をダウンロードすることができる。
【００６１】
デバイスは、クエリ画像の表現をデータベースサーバに送信する。サーバはデータベース内の類似した画像を特定する。その画像は、或る所定の距離判定基準に従ってクエリ画像と密に合致し、その画像に関連するメタデータがクライアントに送信される。
【００６２】
実際の用途では、以下の要件が満たされるべきである。限られたリソースを有する移動デバイスが、複雑度の低い方法を用いて、送信される画像の表現を生成する。表現を送信するのに必要とされる帯域幅は低い。サーバはクエリを迅速に処理するのに十分なリソースを有し、メタデータをクライアントに送信する。
【００６３】
本発明者らは、最も困難な最初の２つの要件を主に取り上げている。それでも、サーバベースのマッチング及び向上したメタデータ圧縮が本発明による方法の利点を補う。
【００６４】
図２の疑似コードに示すように、サーバがデータベース２０１を構築するためにとるステップを説明する。データベース内に記憶された画像の表現は、クエリの表現と類似していることが理解される。
【００６５】
本方法は、要素ａ（ｉ，ｊ）：Ｎ（０，１）を用いてランダム射影行列Ａ∈Ｒｋ×ｄを初期化する。ｓ個の実際のシーン又は合成シーンの画像Ｊ１，Ｊ２．．．，Ｊｔが取得され（ここで、ｓ≦ｔ）、オブジェクトごとにメタデータＤｉ（ここで、ｉ∈｛１，２，．．．，ｓ｝）が生成される。
【００６６】
スケール不変の特徴抽出方法が各画像Ｊｉ（ここで、ｉ∈｛１，２，．．．，ｔ｝）に適用される。この方法は、各画像から幾つかのｄ次元の特徴を抽出する。各画像から抽出される特徴数は等しい必要がない。
【００６７】
次に、このようにして得られた全ての特徴ベクトルを用いて、データベース内の全ての画像からの特徴ベクトルを含む行列Ｖ＝［ｖ１，ｖ２，．．．，ｖＮ］を構築する。通常、Ｎ＞＞ｓである。
【００６８】
ランダム行列Ｗ＝［ｗ１，ｗ２，．．．，ｗＮ］＝ＡＶ∈Ｒｋ×Ｎを求める。ここで、各ｗｉは対応するｖｉのｋ次元ランダム射影である。
【００６９】
ルックアップベクトル（ｌｏｏｋｕｐ  ｖｅｃｔｏｒ：検索ベクトル）Λ⊂｛１，２，．．．，ｓ｝Ｎを記憶する。ここで、要素λ（ｉ）（ここで、ｉ∈｛１，２，．．．，Ｎ｝）が、ベクトルｗｉが抽出された画像をインデックス付けする。
【００７０】
次に、クエリ手順を説明する。この手順は、移動デバイスによって、サーバと同じランダム射影行列Ａを用いて実行される。ａ（ｉ，ｊ）の分布は、擬似乱数発生器によって近似することができる。擬似乱数発生器のシード（ｓｅｅｄ）は、一時的な更新（ｏｎｅ−ｔｉｍｅ  ｕｐｄａｔｅ）として移動デバイスに送信されるか、又はクライアントソフトウェアインストールの一部として含まれる。シードによって、移動デバイス及びサーバが、同一のシードを有することにより、行列Ａの同じ実現を生成することが保証される。
【００７１】
ランダム射影行列Ａ∈Ｒｋ×ｄを初期化する。ここで、要素ａ（ｉ，ｊ）：Ｎ（０，１）である。クエリ画像Ｉ１０１を取得する。Ｉに対し、スケール不変の特徴抽出方法を適用し（１１０）、行列Ｘ＝［ｘ１，ｘ２，．．．，ｘＭ］１０２を導出する。ここで、ｘｉは画像Ｉからのｉ番目の主要点記述子（ｋｅｙ  ｐｏｉｎｔ  ｄｅｓｃｒｉｐｔｏｒ）に対応するｄ次元の特徴ベクトルである。
【００７２】
行列Ｙ＝［ｙ１，ｙ２，．．．，ｙＭ］＝ＡＸ∈Ｒｋ×Ｍ１０３を求める。ここで、各ｙｉは対応するｘｉのｋ次元ランダム射影である。
【００７３】
量子化されたランダム射影Ｑ＝ｑ（Ｙ）の行列１０４を求める。ここで、関数ｑ（・）は、各ｙ（ｉ，ｊ）（ここで、ｉ∈｛１，２，．．．，ｋ｝、ｊ∈｛１，２，．．．，Ｍ｝）をとるスカラー量子化器であり、整数量子化インデックスｑ（ｉ，ｊ）を生成する。すなわち、Ｌレベル量子化器の場合、ｑ（ｉ，ｊ）∈０，１，．．．，Ｌ−１である。
【００７４】
量子化インデックスの要素ごとの固定長コーディングを用いて、行列Ｑをサーバ１５０に送信する。このため、各ｑ（ｉ，ｊ）は、
【数１７】
2014002723.tif 000019
個のビットによって表される。
【００７５】
上記の手順に基づいて、移動デバイスにおける計算複雑度は、スケール不変特徴抽出方法及び１つの行列乗算によって主に求められる。クライアントによってサーバに送信されるビット数は
【数１８】
2014002723.tif 000020
個のビットである。
【００７６】
送信電力を最小にするために、クライアントは、ランダム射影の数ｋ、量子化レベルＬ、又はクエリ画像から抽出された特徴数Ｍを削減することができる。
【００７７】
図３は、サーバによって実行される概算の最近傍探索１４０のための疑似コードを示している。簡単に言うと、最近傍は、画像記述子の量子化された埋込みの空間内において見つけられる。最近傍は集約され、マッチング画像が得られ、そこから関連するメタデータ１５２が得られる。
【００７８】
図４は、動作を概略的に示している。ここで、ｒ＝１０である。図４において、クエリ画像２０１が取得される。サーバは、データベース１５１内の画像の表現と合致するランダム射影１２１を用いる。画像インデックス４０１が、合致発生数の関数として得られる。最も高い合致数を有するインデックスを用いて関連するメタデータ１５２が特定される。
【００７９】
最近傍手順は、ｓ次元ヒストグラムベクトルｈをオールゼロに初期化する。
【００８０】
クエリ画像１０１を表現するＱ＝［ｑ１，ｑ２，．．．，ｑＭ］１０４を受信する。量子化レベル数Ｌを受信する。
【００８１】
量子化関数ｑ（・）を反転し、再構成されたランダム射影行列
【数１９】
2014002723.tif 000021
１０３を得る。
【００８２】
ｓ個のオブジェクトのｔ個全ての画像に対応する全てのｋ次元のランダム射影の量子化された再構成を含む
【数２０】
2014002723.tif 000022
を求める。
【００８３】
各ｉ∈｛１，２，．．．，Ｍ｝について、
【数２１】
2014002723.tif 000023
の中から、
【数２２】
2014002723.tif 000024
の最近傍を特定する。これらのＭ個の再近傍対から、ユークリッド距離が最も近いｒ個の対
【数２３】
2014002723.tif 000025
を選択する。
【００８４】
各
【数２４】
2014002723.tif 000026
について、要素が発生したオブジェクトのインデックスαｊ∈｛１，２，．．．，ｓ｝を読み取る。これはルックアップテーブルΛから容易に入手可能である。そして、ｈ（αｊ）を１だけインクリメントする。
【００８５】
最も類似したオブジェクト／画像を、
【数２５】
2014002723.tif 000027
としてクエリ画像に設定し、このオブジェクトのメタデータを移動デバイスに返送する。
【００８６】
より多くの画像、又はより優れた品質の画像、又はより豊富なメタデータが利用可能になると、問合せ方法に影響を与えることなくそれらをデータベースに付加することができる。
【図１Ａ】
2014002723.tif 000029
【図１Ｂ】
2014002723.tif 000030
【図２】
2014002723.tif 000031
【図３】
2014002723.tif 000032
【図４】
2014002723.tif 000033
【外国語明細書】
2014002723.tif 000034
2014002723.tif 000035
2014002723.tif 000036
2014002723.tif 000037
2014002723.tif 000038
2014002723.tif 000039
2014002723.tif 000040
2014002723.tif 000041
2014002723.tif 000042
2014002723.tif 000043
2014002723.tif 000044
2014002723.tif 000045
2014002723.tif 000046
2014002723.tif 000047
2014002723.tif 000048
2014002723.tif 000049
2014002723.tif 000050
2014002723.tif 000051
2014002723.tif 000052
2014002723.tif 000053
2014002723.tif 000054
2014002723.tif 000055
2014002723.tif 000056
2014002723.tif 000057
2014002723.tif 000058
2014002723.tif 000059
2014002723.tif 000060
2014002723.tif 000061
2014002723.tif 000062