(57)【特許請求の範囲】
【請求項１】
地球学的ロケーションに関連する第１の組の特徴記述子及びコンパクト分類子を受け取るステップと、
前記地球学的ロケーションに関連する、未知のクラスを有する画像を捕捉するステップと、
前記捕捉された画像から第２の組の特徴記述子を生成するステップと、
前記第２の組に含まれる各特徴記述子により、前記第１の組に含まれる特徴記述子ごとにＭｉｎ−Ｈａｓｈ値を計算するステップと、
前記第１の組に含まれる特徴記述子と類似するＭｉｎ−Ｈａｓｈ値を有する前記第２の組に含まれる特徴記述子ごとに類似度を生成するステップと、
前記捕捉された画像のクラスを決定するよう前記類似度に基づき前記コンパクト分類子を前記捕捉された画像へ適用するステップと
を有する、コンピュータによって実施される方法。
【請求項２】
第１の装置の地球物理学的ロケーションを含むリクエストにより、前記第１の装置から前記コンパクト分類子を要求するステップを更に有し、
前記コンパクト分類子は、前記第１の装置から遠く離れて位置する第２の装置によって受け取られる、
請求項１に記載の方法。
【請求項３】
前記コンパクト分類子は、複数のランダム決定木を有するランダム決定フォレストであり、
前記コンパクト分類子を前記捕捉された画像へ適用するステップは、
前記捕捉された画像が前記ランダム決定木のうちの特定の１つに関連する特定のクラスと一致する確率を得るよう、前記第２の組の特徴記述子の類似度に基づき各ランダム決定木を走査することを含む、
請求項１に記載の方法。
【請求項４】
前記確率は確率分布を有し、
当該方法は、前記捕捉された画像に関連しそうなクラスを決定するよう、全ての前記ランダム決定木にわたってクラス毎にそれぞれの確率分布を平均するステップを更に有する、
請求項３に記載の方法。
【請求項５】
ランダム決定木の各ノードは、閾値と関連づけられ、
各ランダム決定木を走査することは、前記第２の組の特徴記述子の類似度を、ランダム決定木に含まれる各ノードに関連する閾値と比較することを含む、
請求項３に記載の方法。
【請求項６】
プロセッサによって実行される場合に、該プロセッサに、
１又はそれ以上の特徴記述子を得る動作と、
捕捉された画像に関して、特徴記述子ごとに類似度を決定する動作であって、前記類似度は、特徴記述子と当該捕捉された画像における画像パッチとの最も近い一致を表し、前記捕捉された画像における画像パッチと一致する特徴記述子について計算され、該一致する特徴記述子は、Ｍｉｎ−Ｈａｓｈプロセスを用いて決定される、動作と、
前記類似度の使用により前記捕捉された画像を認識する動作と
を実行させるプロセッサ実行可能命令を記憶するコンピュータ可読記憶媒体。
【請求項７】
プロセッサによって実行される場合に、該プロセッサに、
共通の地球物理学的ロケーションに関連する１又はそれ以上のトレーニング画像から、１又はそれ以上の特徴記述子を得る動作と、
各トレーニング画像に関して、特徴記述子ごとに、当該特徴記述子と当該トレーニング画像における画像パッチに対応する全ての特徴記述子の中の最も類似した特徴記述子との間の類似を表す類似度を決定し、それらの一致する特徴記述子が、当該トレーニング画像に関して当該特徴記述子に適用されるＭｉｎ−Ｈａｓｈプロセスを用いて加速されるハミング距離計算を行うことによって決定される、動作と、
前記類似度の使用により分類子をトレーニングする動作と
実行させるプロセッサ実行可能命令を記憶するコンピュータ可読記憶媒体。
【請求項８】
前記プロセッサ実行可能命令は、前記プロセッサによって実行される場合に、該プロセッサに更に、
より顕著な特徴を有する前記トレーニング画像における画像パッチから前記特徴記述子を選択する動作
を実行させる、請求項７に記載のコンピュータ可読記憶媒体。
【請求項９】
前記プロセッサ実行可能命令は、前記プロセッサによって実行される場合に、該プロセッサに更に、
１又はそれ以上のランダム決定木を前記分類子として生成する動作
を実行させ、
各ランダム決定木は、前記特徴記述子と前記類似度とを用いてトレーニングされる、
請求項７に記載のコンピュータ可読記憶媒体。
【請求項１０】
前記プロセッサ実行可能命令は、前記プロセッサによって実行される場合に、該プロセッサに更に、
前記類似度をハミング距離として表す動作と、
トレーニング画像における画像パッチと一致する特徴記述子について前記ハミング距離を計算する動作と
を実行させる、請求項７に記載のコンピュータ可読記憶媒体。
【発明の詳細な説明】
【背景技術】
【０００１】
カメラを備えるモバイル装置の急増は、モバイル装置のカメラから撮られる画像を認識することができるロケーション認識アプリケーションの必要性を高めている。モバイル装置は記憶容量及び計算資源が限られているので、視覚的なロケーション認識のタスクは、しばしば、遠隔で行われる。モバイル装置は、撮られた画像をモバイル装置からサーバへアップロードしてよい。サーバは、その画像を、サーバ上に記憶されている類似画像とマッチングする。記憶されている画像は、その画像のロケーションに関連する地理的データにより注釈を付されている。サーバは、画像のロケーションをモバイル装置にダウンロードする。しかし、モバイル装置は、サーバと通信するための帯域幅が限られている。モバイル装置とサーバとの間で画像及びデータを送信することに伴うレイテンシは、モバイル装置が実時間でロケーション認識を行う障害である。
【発明の概要】
【課題を解決するための手段】
【０００２】
この項目は、詳細な説明において以下で更に記載される簡単化された形態において概念の選択を導入するために設けられている。この項目は、請求対象の重要な特徴又は必須の特徴を特定するよう意図されず、且つ、請求対象の適用範囲を決定する助けとして使用されるよう意図されない。
【０００３】
モバイル装置は、サーバからの最小限の支援を有して実時間のロケーション認識を行う。モバイル装置の地球物理学的ロケーションは、モバイル装置からサーバへアップロードされる。サーバは、モバイル装置の地球物理学的ロケーションに基づき、コンパクトな分類子及び特徴記述子をモバイル装置に与える。次いで、モバイル装置は画像を捕捉してよく、該画像は、次いで、コンパクトな分類子及び特徴記述子を用いて分類される。この分類の結果は、画像が特定のクラス又はランドマークであるとの確率の推定である。
【０００４】
分類子及び特徴記述子は、オフラインのトレーニング段階を通じて生成され、計算処理を最小限にするよう構成される。実施例において、分類子は、地球物理学的ロケーション及びクラスを同じくする記憶されている画像を用いてトレーニングされるランダム決定フォレストである。ランダム決定フォレストをトレーニングする方法は、画像において存在する最も特徴的な特徴を自動選択する。これは、コンパクトであり、従って、モバイル装置へ瞬時にダウンロードされ得、更には、分類ステップのための計算がモバイル装置において実時間で実行されることを可能にする分類子をもたらす。
【０００５】
これら及び他の特徴及び利点は、以下の詳細な説明を読むこと及び関連する図面の見ることから明らかであろう。当然に、上記の概要及び以下の詳細な説明は、請求される態様を説明するためであり、それらの限定ではない。
【図面の簡単な説明】
【０００６】
【図１】ロケーションを利用した認識のための例となるシステムのブロック図を表す。
【図２】トレーニング段階のための例となる方法を表すフローチャートである。
【図３】実時間のクエリ段階のための例となる方法を表すフローチャートである。
【図４】分類子をトレーニングするための例となる方法を表すフローチャートである。
【図５】特徴抽出のための例となる方法を表すブロック図である。
【図６】密マッチングのための例となる方法を表すブロック図である。
【図７】密マッチングのための他の例となる方法を表すブロック図である。
【図８】モバイル装置からロケーションを利用した認識を行うための例となる方法を表すフローチャートである。
【図９】分類子をトレーニングするための例となる方法を表すブロック図である。
【図１０】動作環境を表すブロック図である。
【図１１】動作環境におけるモバイル装置の例となる構成要素を表すブロック図である。
【図１２】動作環境におけるサーバの例となる構成要素を表すブロック図である。
【発明を実施するための形態】
【０００７】
種々の実施形態は、実時間のロケーションを利用した認識を行う技術に向けられている。ロケーション認識は、多大な記憶及び計算時間を要する計算上厄介なプロセスである。実時間のロケーション認識は、計算上効率的な技術が使用される場合に、モバイル装置にとって実用的である。ここで記載される技術は、認識の精度を下げることなくそのような計算負荷を減らすために圧縮データ構造及び技術の使用に依存する。
【０００８】
分類子は、モバイル装置におけるカメラによって捕捉された画像を、該画像を特定の地球物理学的ロケーション内の所定のクラス又はランドマークの組の中の１つとして分類することによって、認識するために使用されてよい。実施例において、分類子は、複数のランダム決定木を有するランダム決定フォレストであってよい。ランダム決定木は、捕捉された画像の特徴を、同じ地球物理学的ロケーション及びクラスを有するトレーニング画像と比較するために使用されてよい。クラスは、画像を記述する識別子、例えば、ランドマーク、特定の建物、又は構造物である。分類は、一連の比較を通じてルートノードからリーフノードまでランダム決定木を走査することを伴う。夫々の比較は、特定の特徴が捕捉画像において存在するかどうかを評価する二分試験に相当する。これは、最初に、捕捉画像からハミング距離のようなメトリックにより最も類似する特徴を探し、それを閾値と比較することによって、行われる。閾値は、トレーニング画像から分かる一致の可能性を定量化する。木の走査は、捕捉画像が特定のクラス又はランドマークであるとの可能性を示すリーフノードで終わる。分類は、ランダム決定フォレストにおける各ランダム決定木によって独立して行われる。各ランダム決定木を走査することにより生じる全ての確率の平均は、画像の最もありそうなクラスを推定するために使用されてよい。
【０００９】
実施例において、サーバは、モバイル装置をその実時間のロケーション認識において支援するために使用されてよい。サーバは、オフラインのトレーニング段階の間、夫々の地球物理学的ロケーション及びクラスについて、ランダム決定フォレストを生成する。ランダム決定フォレストにおけるランダム決定木は、地球物理学的ロケーション及びクラスを同じくする記憶された画像を用いてトレーニングされる。ランダム決定木は、画像の最も顕著な特徴を含むと解析された特徴記述子の組を用いて、生成される。
【００１０】
オフラインのトレーニング段階において、同じ地球物理学的ロケーションに関連するトレーニング画像は、画像の最も顕著な特徴を決定するよう解析される。特徴抽出プロセスが実行され、トレーニング画像から特徴を抽出し、それらを、特徴的な特徴を有するサブセットを選択するよう解析する。そのサブセットに含まれる夫々の特徴は、次いで、特徴記述子として知られる、よりコンパクトな表現に変換される。密マッチング（dense  matching）プロセスが実行され、どの特徴記述子が画像においてより顕著な特徴を表すのかを決定する。
【００１１】
顕著な特徴の検索は、各画像における特徴記述子ごとに、ハミング距離のような類似度を計算することによって、実行される。この検索に伴うハミング距離の計算の回数を最小限とするために、Ｍｉｎ−Ｈａｓｈプロセスが使用され、どの特徴記述子が類似しており、それによりハミング距離の計算を必要とするのかを決定する。ハミング距離の計算は、異なる特徴記述子について、それらの類似度が低めであろう場合に、回避される。各トレーニング画像に対応する特徴記述子を含むテーブルは、ランダム決定フォレストをトレーニングするために使用される。その特徴記述子の各要素は、各特徴記述子と画像全体において見られる最も類似する記述子との間の類似度を計算することによって、求められる。ランダム決定フォレストをトレーニングする方法は、様々なクラスの画像において存在する最も特徴的な特徴を自動選択する。これは、コンパクトであり、従って、モバイル装置へ瞬時にダウンロードされ得、更には、分類ステップのための計算がモバイル装置において実時間で実行されることを可能にする分類子をもたらす。
【００１２】
実施例において、モバイル装置は、モバイル装置の地球物理学的ロケーションのみを用いてクエリによりサーバからランダム決定フォレスト及び特徴記述子を得る。実施例において、地球物理学的ロケーションは、モバイル装置のＧＰＳ座標であってよい。このように、サーバとモバイル装置との間のデータの送受信におけるレイテンシは、最小限にされる。次いで、モバイル装置は画像を捕捉し、該画像は、次いで、ランダム決定フォレストを用いて分類される。その結果は、画像が特定のクラスである確率の推定をもたらす。ここで、ロケーションを利用した認識のための実施形態についてのより詳細な説明に注意を向ける。
【００１３】
図１を参照すると、ロケーションを利用した認識のためのシステム１００が示されている。システム１００は、１又はそれ以上のモバイル装置１０４と通信するサーバ１０２を含んでよい。実施例において、サーバ１０２及びモバイル装置１０４は、通信ネットワーク１０６を介して通信上結合されてよい。通信ネットワーク１０６は、様々なタイプの通信媒体から成ってよく、該通信媒体には、有線若しくは無線の通信媒体、又はそれらのあらゆる組み合わせが含まれてよい。例えば、モバイル装置１０４は、有線通信媒体を通じてサーバ１０２へ結合される無線アクセスポイントへ、無線通信媒体を通じて通信してよい。代替的に、モバイル装置１０４は、サーバ１０２へ直接に、無線通信媒体を通じて通信してよい。無線通信媒体は、あらゆる無線技術、例えば、制限なしで、ＩＥＥＥ８０２ファミリの無線標準、Ｗｉ−Ｆｉ、ＷｉＭａｘ、ブルートゥース、又はそれらのあらゆる組み合わせを用いて動作してよい。
【００１４】
サーバ１０２は、制限なしで、コンピュータ、パーソナルコンピュータ、デスクトップコンピュータ、ラップトップコンピュータ、ノートブックコンピュータ、手持ち式コンピュータ、サーバアレイ若しくはサーバファーム、ミニコンピュータ、メインフレームコンピュータ、スーパーコンピュータ、分散型コンピューティングシステム、マルチプロセッサシステム、又はそれらの組み合わせを含んでよい。モバイル装置１０４は、無線通信媒体、例えば、制限なしで、パーソナルデジタルアシスタント、モバイルコンピュータ装置、スマートホン、タブレット型パーソナルコンピュータ、携帯電話機、メッセージ装置又はそれらの組み合わせを介して通信する機能を備えるあらゆる手持ち式電子機器であってよい。
【００１５】
サーバ１０２は、画像データベース１０８と、分類子データベース１１０とを有してよい。画像データベース１０８に記憶されている画像は、地球物理学的ロケーション及びクラス識別子を含むジオタグにより注釈を付されている。実施例において、地球物理学的ロケーションは、地球上の場所の地理的な緯度及び経度による地理座標に基づく。地球物理学的ロケーションは、２つの数として表されよい。すなわち、１つの数は、地理緯度を示し、第２の数は地理経度を示す。クラスは、画像において見られるランドマーク又は場所を特定する。例えば、クラスは、具体的な場所又は道の曲がり角、建物、山等の市街ランドマークのタイプであってよい。クラス識別子は、特定のクラスを表す整数である。画像は、どのランドマーク又は建物が対応する画像において観測されるのかを示すクラス識別子と、関連する地球物理学的ロケーションとともに、画像データベースにおいて記憶されてよい。
【００１６】
分類子データベース１１０は、分類子を含む。分類子は、同じ地球物理学的ロケーション及びクラスを有する画像の組を用いてトレーニングされる学習機能である。実施例において、分類子は、ランダム決定フォレストであってよい。ランダム決定フォレストは、ランダム決定木の組を含み、各ランダム決定木は、クラス又はランドマークの組に関して確率分布を決定するために使用される。
【００１７】
トレーニング段階１１１は、分類子を計算するための複数のフェーズを含んでよい。トレーニング段階１１１は、画像データベース１０８において記憶されるランドマークに対応する地球物理学的ロケーション及びクラスを有する画像の組を用いる。次いで、各画像は、画像修正モジュール１１２を通じて、その画像において存在し得る遠近歪み（perspective  distortion）を除くよう修正される。画像修正は、遠近歪みが削除されるか又は最小限とされるように、異なる奥行きから撮られた画像を変換する幾何学変換である。
【００１８】
再現可能であり且つ異なるランドマークに一意である顕著な特徴は、特徴抽出モジュール１１４によって特定される。特徴抽出モジュール１１４は、それらの顕著な特徴の外観を、対応する画像パッチ内のペアワイズ・ピクセル比較から形成される２進列に符号化する。それらは、特徴記述子と称される。トレーニング密マッチングモジュール１１６は、特徴記述子の組の各記述子について、最も類似する画像パッチを検索する。画像パッチは、デジタル化された画像において顕著な特徴の位置の周囲の正方形領域内のピクセルに対応する。画像ごとに、特定の特徴記述子に最も類似する画像パッチが見つけられ、類似度が計算される。全ての特徴記述子に対応する類似度はテーブルにおいて記憶される。テーブルにおいて、画像ごとに１つの列が存在する。密マッチングは、画像全体における最も類似する特徴記述子の密検索を加速するために使用されるＭｉｎ−Ｈａｓｈプロセスを用いて加速される。
【００１９】
サーバ１０２は、モバイル装置１０４に該モバイル装置の概算の地球物理学的ロケーションに対応する分類子を与えることによって、モバイル装置１０４を、その実時間のロケーション認識において支援する。クエリ段階の間、ロケーション支援モジュール１２０は、モバイル装置１０４の地球物理学的ロケーションを含むクエリをモバイル装置１０４から受け取る（ブロック１２２）。これに応答して、サーバ１０２は、モバイル装置の概算の地球物理学的ロケーションに関連する分類子及び特徴記述子の組といったデータをモバイル装置１０４へ返送する（ブロック１２４）。
【００２０】
モバイル装置１０４は、その地球物理学的ロケーションを決定するためのメカニズムを有してよい。モバイル装置１０４は、モバイル装置の地球物理学的ロケーションを追跡する機載衛星受信器と相互作用するロケーションモジュール１２７を有してよい。実施例において、機載衛星受信器は、モバイル装置のＧＰＳ座標を示すＧＰＳ信号を受信するよう構成されてよい。代替的に、ロケーションモジュール１２７は、セルラーネットワークとの通信において無線受信器と相互作用してよい。ロケーションモジュール１２７は、モバイル装置のＧＰＳ座標を決定するためにセルラーネットワークを利用してよい。
【００２１】
モバイル装置１０４は、サーバ１０２と相互作用するサーバインターフェースモジュール１２６を更に有してよい。サーバインターフェースモジュール１２６は、モバイル装置の地球物理学的ロケーション（例えば、ＧＰＳ座標）を含むクエリをサーバへアップロードする（ブロック１２８）。サーバインターフェースモジュール１２６は、次いで、分類子及び特徴記述子等のデータをサーバ１０２から受信する（ブロック１３０）。写真捕捉モジュール１３２は、デジタル化された画像として記憶される対象又はランドマークの画像を捕捉するために使用されてよい。画像は、次いで、遠近歪みを除くよう画像修正モジュール１３４によって修正される。
【００２２】
クエリ段階の間、実時間密マッチングモジュール１３６は、ダウンロードされた特徴記述子の夫々に対応する最も類似する画像パッチを捕捉画像において密に検索することによって、捕捉画像について高次の特徴ベクトルを構築する。特徴ベクトルの各要素は、夫々のダウンロードされた特徴記述子と、捕捉画像において見られる最も類似する画像パッチ又は特徴記述子との間のハミング距離を計算することによって、求められる。Ｍｉｎ−Ｈａｓｈ技術が、この検索を加速するために使用される。同じＭｉｎ−Ｈａｓｈ値を有する特徴記述子の対は、類似する可能性が高い。従って、特定の特徴記述子に最も類似した記述子を検索する場合に、参照記述子のＭｉｎ−Ｈａｓｈ値とは異なるＭｉｎ−Ｈａｓｈ値を有する特徴記述子は、ハミング距離の計算を行うことなく早期に拒絶される。これは、不必要なハミング距離の計算を除き、計算全体におけるスピードアップをもたらす。
【００２３】
分類モジュール１３８は、所与の地球物理学的ロケーションに関連するクラスごとに確率推定をもたらす夫々のランダム決定木を走査するために、高次の特徴ベクトルを用いる。分類モジュール１３８の結果は、ディスプレイ１４０に表されてよく、画像においてクラスの確率によってソートされるランドマーク又は場所のリストの形をとってよい。代替的に、結果は、クラスごとに確率推定を視覚的に表すヒストグラムの形をとってよい。他の視覚的な表現が同様に分類結果を表すために使用されてよいことが、留意されるべきである。
【００２４】
ここで、様々な例となる方法を参照して、ロケーションを利用した認識システム１００の実施形態の動作のより詳細な議論に注意を向ける。当然に、表される方法は、別段示されない限り、必ずしも、提示されている順序において、又は如何なる特定の順序においても実行される必要はない。更に、方法に関連して記載される様々な動作は、直列若しくは並列に、又は直列及び並列な動作のあらゆる組み合わせにおいて、実行され得る。方法は、設計及び性能の制約の所与の組について望まれるように、記載される実施形態又は代替の実施形態の１又はそれ以上のハードウェア要素及び／又はソフトウェア要素を用いて実施され得る。例えば、方法は、論理デバイス（例えば、汎用又は特定目的のコンピュータ）による実行のために、ロジック（例えば、コンピュータプログラム命令）として実施されてよい。
【００２５】
図２を参照すると、サーバ１０２によって実行されるトレーニングが示されている（ブロック１５２）。実施例において、トレーニング段階は、クエリ段階に容易に利用可能な分類子を有するために、クエリ処理からオフラインで実行される。なお、トレーニングは、意図される実施のために望まれるように、ロケーション認識プロセスにおける別な時点で実行されてよい。
【００２６】
図３を参照すると、サーバ１０２は、モバイル装置１０４からのクエリが係属中であるかどうかを確認してよい（ブロック１５６）。クエリがモバイル装置１０４から受信される場合（ブロック１５６−“はい”）、サーバ１０２は、モバイル装置１０４の概算の地球物理学的ロケーションに対応する分類子及び特徴記述子を分類子データベース１１０から取り出し、それらをモバイル装置１０４へ送信する（ブロック１５８）。そうではない場合（ブロック１５６−“いいえ”）、サーバ１０２は、処理を終える（ブロック１６０−“はい”）べきかどうかを確認し、終えるべきでない場合（ブロック１６０−“いいえ”）、サーバ１０２は続けて、モバイル装置１０４からのクエリを確認する。
【００２７】
図４は、トレーニング段階１５２の間に実行される動作を表すフローチャートである。最初に、画像が収集され、画像データベース１０８に記憶される。各画像は、上述されたように、地理的な場所及びクラスにより注釈を付される。分類子は、画像データベース１０８から得られる特定の地理的な場所及びクラスに対応する画像に対してトレーニングされる（ブロック１７０）。
【００２８】
画像修正モジュール１１２は、次いで、画像における垂直及び水平な線が夫々、修正された画像における垂直及び水平な線として見られることを確かにするよう、画像における遠近歪みを除く幾何学変換である画像修正を実行する（ブロック１７２）。このように、密マッチングしか、画像における全ての位置にわたって且つスケールの範囲にわたって実行される必要がない。確実に直線を検出して、それらから消失点を推定することに依存する、市街画像において捕捉される画像の画像修正を実行するための既知の技術が複数存在し、それらの技術の中のいずれかが利用されてよい。加えて、モバイル装置において存在し得るモーションセンサからのモバイル装置の３次元回転から推定を得る他の技術も、利用されてよい。
【００２９】
次に、特徴抽出が実行される（ブロック１７４）。特徴抽出モジュール１１４は、画像において顕著且つ一意であり、更に再現可能である外観を有する特徴の組を特定する（ブロック１７６）。すなわち、特徴は、同じ場面の異なる画像において現れる。実施例において、特徴の候補の組が特定される。特徴の候補の組は、ブロブ検出、エッジ検出、コーナー検出、リッジ検出、及びスケールによって影響を受けない関心点検出のためのＳＩＦＴ（scale  invariant  feature  transform）、並びにそれらの組み合わせといった複数の既知の技術の中のいずれか１つを用いて特定されてよい。かかる特徴は、各画像におけるその場所、スケール及び方位によって表される。特徴記述子は、ＳＩＦＴ記述子のように、各画像における候補特徴ごとに計算される。ロバストなペアワイズ・マッチングが、同じクラスを有するトレーニング画像の全ての対の間で実行される。類似すると見なされる特徴の対は、特徴記述子のサブセットを形成するよう結び付けられる。最後に、候補特徴は、このサブセット内の全ての他の特徴記述子に対して最小の総ユークリッド距離を有する特徴記述子に関連する特徴を選択することによって、このサブセットから選択される。これは、各クラスに対応する候補特徴の組が更なる使用のために選択される方法である。
【００３０】
次に、特徴記述子は、夫々の選択された特徴について生成されてよい（ブロック１７８）。各特徴の外観は、特徴記述子として符号化される。実施例において、各特徴は、一意のＢＲＩＥＦ（binary  robust  independent  elementary  feature）記述子によって表されてよい。この記述子は、最初に、各特徴に対応する画像パッチを３２×３２のピクセルパッチに再サンプリングすることによって計算される２進ベクトルである。次に、ランダムピクセルのｋ個の対が、この３２×３２のパッチ内からサンプリングされる。特徴の中心に中心を置くガウス分布が、個々のピクセル位置を無作為サンプリングするために使用される。実施例において、ｋ＝１９２であり、特徴記述子は１９２ビット長である。特徴記述子における各ビットは、特徴における２つの無作為に選択されたピクセルの間の強度レベルの比較を表す。第１のピクセルが第２のピクセルよりも高い強度を有する場合は、ビットは‘１’に設定され、第２のピクセルが第１のピクセルよりも高い強度を有する場合は、ビットは‘０’に設定される。ｋ番目のビットは、ピクセルのｋ番目の対の間の比較の結果を表す。
【００３１】
図５を参照すると、画像１８０が示されている。特徴抽出モジュール１１４は、画像１８０の全体にわたって小さなボックスとして示されている複数の画像パッチ又は候補特徴を特定する。候補特徴のサブセットが選択される。例えば、特徴１８２が選択される。特徴１８２におけるピクセルの強度レベルのペアワイズ比較はブロック１８４において示されている。特徴抽出モジュール１１４は、次いで、ブロック１８４において示され且つ上述された比較からの結果を表す１９２ビットのＢＲＩＥＦ特徴記述子１８６を生成する。図５は１つの特徴についての特徴抽出モジュール１１４のプロセスを表すが、このプロセスは、トレーニング段階において使用される各画像の特徴ごとに実行される。そのようなものとして、単一のクラスについて生成される数百の特徴記述子が存在してよい。
【００３２】
図４に戻って、トレーニング密マッチングモジュール１１６は、特徴抽出モジュール１１４によって選択された特徴記述子に対して密マッチングを実行する（ブロック１８０）。密マッチングにおいて、各特徴は、画像の組における全ての位置及びスケールにわたって最も類似する特徴を決定するために、あらゆる画像における夫々の位置にわたってマッチングされる。類似性は、特徴記述子と、画像における画像パッチの特徴記述子との間の距離に基づく。幾つかの実施例において、最小距離はハミング距離であってよい。画像の大きなサイズ及びスケールに起因して、密マッチングは、計算時間及び記憶スペースの両方において計算上費用がかかるプロセスである。高速な認識を達成するために、Ｍｉｎ−Ｈａｓｈ（すなわち、最小値独立置換族（min-wise  independent  permutations））プロセスが、密マッチングを加速するために使用されてよい（ブロック１８２）。Ｍｉｎ−Ｈａｓｈは、画像内の特徴記述子に対応する最も類似する画像パッチを検索する間に実行されるハミング距離の計算の回数を減らすために使用される。
【００３３】
Ｍｉｎ−Ｈａｓｈ関数は、２つの２進特徴記述子が類似するかどうかを決定する組間のＪａｃｃａｒｄ類似性測度に基づく。２つの２進特徴記述子におけるビットの大部分が一致する場合は、Ｊａｃｃａｒｄ類似性は１により近く、特徴記述子は類似のＭｉｎ−Ｈａｓｈ値を有すると思われる。Ｍｉｎ−Ｈａｓｈ関数は、２進特徴記述子において含まれるビットに対する無作為置換として実施される。Ｍｉｎ−Ｈａｓｈ値は、その特徴記述子の無作為置換における最初の正ビット（‘１’）のインデックスである。スケッチは、独立したＭｉｎ−Ｈａｓｈ値の順序づけられたｎ組（n-tuple）である。記述子の対は、５つのスケッチの中の少なくとも２つが同一であると認められる場合に、類似すると見なされる（ブロック１８４）。
【００３４】
特徴記述子ごとに、画像において見られるその最も類似する記述子による類似度が、密マッチングテーブルにおいて記憶される（ブロック１８６）。実施例において、類似度はハミング距離である。画像ｙにおける特徴記述子ｘについての類似度は、記述子ｘと、画像ｙにおけるその最も近い一致を示す特徴記述子ｚとの間のハミング距離を表す。
【００３５】
図６は、Ｍｉｎ−Ｈａｓｈプロセスを表す。図６を参照すると、多数の特徴記述子の組から２つの特徴記述子１８８Ａ及び１８８Ｂが示されている。各特徴記述子１８８Ａ、１８８Ｂは、５つの関連するスケッチをもたらすようＭｉｎ−Ｈａｓｈを適用される。例示のためにのみ、図６において、夫々の特徴記述子１９０Ａ、１９０Ｂについて、３つのスケッチが示されている。各スケッチ１９２Ａ〜１９２Ｅ、１９４Ａ〜１９４Ｅは５つのＭｉｎ−Ｈａｓｈ値を示し、各Ｍｉｎ−Ｈａｓｈ値は、ＢＲＩＥＦ特徴記述子におけるビットの無作為置換の下で１に設定されるＢＲＩＥＦ特徴記述子における第１のビットのインデックスを表す。
【００３６】
全てのスケッチを含む組１９６が形成される。スケッチ１９８Ａ〜Ｆの対の間のＭｉｎ−Ｈａｓｈ値が比較される。少なくとも２つのＭｉｎ−Ｈａｓｈ値が同じである場合は、スケッチは一致すると見なされる。図６に示されるように、スケッチ１９８Ｂ及び１９８Ｃは、ともに丸で囲まれて示されている同じＭｉｎ−Ｈａｓｈ値を有する。スケッチ１９８Ｅ及び１９８Ｆは、同じくともに丸で囲まれて示されている同じＭｉｎ−Ｈａｓｈ値を有する。スケッチ１９８Ｂ及び１９８Ｃに関連する特徴記述子は一致すると見なされ、スケッチ１９８Ｅ及び１９８Ｆに関連する特徴記述子も一致すると見なされる。ハミング距離は、２つの特徴記述子をとる関数であり、異なるビットの数を決定することによってそれらの間の距離を決定する。ハミング距離は、記述子の全ての対について、それらのスケッチの中の少なくとも２つが同じである場合に、計算される。画像における最も近い特徴記述子は、参照特徴記述子から最小ハミング距離を有する特徴記述子である。
【００３７】
ここで、図７を参照すると、全てのスケッチ１９８Ａ〜１９８Ｆを含む組１９６から、一致するスケッチ１９８Ｂ、１９８Ｃ及び１９８Ｅ、１９８Ｆが示されている。密マッチングテーブル２００は、ｍ個の行及びｎ個の列を有するｍ×ｎの表として示されている。各行２０４Ａ〜２０４Ｍは特徴記述子を表し、各列２０２Ａ〜２０２Ｎは画像を表す。表における各セルは、特定の行に関連する特徴記述子と、特定の列に関連する画像において見られる最も類似する特徴記述子との間のハミング距離を含む。
【００３８】
図４に戻って、分類子トレーニングモジュール１１８は、分類子をトレーニングする（ブロック１８８）。実施例において、分類子は、ランダム決定フォレストとして実施されてよい。ランダム決定フォレストは、別個にトレーニングされる独立したランダム決定木の集合である。ランダム決定木は、内部ノード及びリーフノードを有する２分木として構成される。各内部ノードは、２つの特徴記述子の間のハミング距離を閾値と比較する特徴テストである。例えば、実施例において、特徴テストは、次のように：ＨＤ（ｘ，ｓ）＜Ｔｓと構成されてよい。ここで、関数ＨＤ（）は２つの特徴記述子の間のハミング距離であり、ｘ及びｓは特徴記述子であり、Ｔｓはｓについての閾ハミング距離である。リーフノードは、クラス又はランドマークの組に対して定義されるクラスの確率分布を記憶する。
【００３９】
ランダム決定木は、再帰的にルートノードから始まるよう構築される。特徴記述子は、ルートノードを左右の子ノードに分割するために使用される。各ノードにおいて、分割は、ジニ不純度基準（gini  impurity  criteria）のような何らかの情報理論基準に基づく。各ノードにおける特徴の分割は、選択されていない残りの特徴記述子から無作為に選択される。ランダム決定木は、現在のノードにおいて分割すべき特徴記述子がもはや存在しないか、又は木の深さが所定の限界を超える場合に、成長するのを止める。特徴記述子は、所定の数のランダム決定木が形成されるまで、他のランダム決定木を無作為にトレーニングするために再び使用される。ランダム決定フォレストは、次いで、全てのランダム決定木の総集合として形成されてよい。ランダム決定フォレストは、次いで、ランダム決定フォレストをトレーニングするために使用された特徴記述子とともに、分類子データベースにおいて記憶されてよい。
【００４０】
ランダム決定フォレストが形成されると、各ランダム決定木は、独立した分類決定を得るために走査され得る。各ランダム決定木は、高次の特徴ベクトルを用いて上から下まで走査される。特徴ベクトルの要素の夫々は、各内部ノードにおいて特定の閾値と比較される。走査がリーフノードに達する場合に、リーフノードによって表されるクラスに関連する確率分布が記録される。各木からのクラスごとの確率は平均化されて、最終のクラス確率を決定するために使用される。
【００４１】
ここで、ロケーションを利用した認識においてモバイル装置１０４によって実行される動作に注意を向ける。図８を参照すると、モバイル装置１０４は、サーバ１０２へ、モバイル装置の地球物理学的ロケーションを含むクエリをアップロードする（ブロック２２２）。実施例において、モバイル装置１０４は、モバイル装置１０４の地球物理学的ロケーションを直接に取得し追跡することができる衛星又は無線トランシーバを装備されてよい。衛星又は無線トランシーバは、ＧＰＳ（Global  Positioning  System）、ＧＬＯＮＡＳＳ、Ｇａｌｉｌｅｏ、及びＢｅｉｄｏｕ衛星を用いるＧＮＳＳ（Global  Navigation  Satellite  System）のようないずれかの衛星ポジションシステムから信号を受信するよう構成されてよい。他の実施例において、モバイル装置１０４は、セルラーネットワークからの無線周波数信号を受信することができる無線トランシーバを装備されてよい。無線トランシーバは、セルラーネットワークから間接的にその地球物理学的ロケーションを得て追跡するために使用され得る。実施例において、地球物理学的ロケーションは、モバイル装置の地球物理学的ロケーションに関連するＧＰＳ緯度及び経度座標から成ってよい。
【００４２】
モバイル装置１０４は、その概算の地球物理学的ロケーションに対応する分類子及び特徴記述子を受信する（ブロック２２４）。モバイル装置１０４は、ユーザが写真を捕捉する（ブロック２２６）ことを可能にするカメラを装備されてよい。捕捉された画像は、次いで、画像修正モジュール１３４によって修正されてよい（ブロック２２８）。他の実施例において、モーションセンサからモバイル装置の３Ｄ回転の推定を得る技術が、モバイル装置において存在する場合に画像修正を実行するために使用されてよい。
【００４３】
実時間の密マッチングが、ダウンロードされた特徴記述子について捕捉画像内のそれらの最も近い記述子に対する類似度を含む高次の特徴ベクトルを生成することによって、ダウンロードされた特徴記述子の夫々に対する最も近い一致を捕捉画像から探すよう実行される（ブロック２３０）。実時間密マッチングモジュール１３６は、ダウンロードされた特徴記述子と、捕捉された写真における画像パッチを表す特徴記述子とにＭｉｎ−Ｈａｓｈ技術を適用して、ダウンロードされた特徴記述子の中のどれが捕捉画像においてより類似する特徴を有するのかを特定する（ブロック２３２）。Ｍｉｎ−Ｈａｓｈ技術は、特徴記述子の夫々についてスケッチを生成し、類似するスケッチを有する特徴記述子を特定し、類似する特徴記述子について類似度を生成することにおいて、図６及び図７に関して先に記載されたように動作する。類似度の最小値は高次の特徴ベクトルにおいて記憶される（ブロック２３４）。
【００４４】
高次の特徴ベクトルは、次いで、分類を実行するために使用されてよい（ブロック２３６）。分類モジュール１３８は、様々な特徴記述子の類似度を含む高次の特徴ベクトルに基づき各ランダム決定木を走査する。分類の結果は、捕捉画像からマッチングされているクラスを表すクラスに関する確率である。結果は、確率が減少する順序において順位付けされたクラスのリストの形でユーザに表示されてよい（ブロック２３８）。
【００４５】
図９を参照すると、サーバから得られる特徴記述子２４２Ａ〜２４２Ｎの組が示されている。特徴記述子２４２Ａ〜２４２Ｎの夫々は、ハミング距離のような類似度の比較を通じて、捕捉画像における画像パッチを表す特徴記述子と密にマッチングされてよい。類似度は、高次の特徴ベクトル２４４において記録されてよい。各決定木は、当該決定木における各内部ノードに含まれる閾値及び特徴記述子に対応する類似度に基づき走査される。ランダム決定木の走査の結果は、リーフノードによって表される様々なクラスについての確率分布である。クラス確率分布は全ての木にわたって平均化され、画像の最も可能性が高いクラスが決定される。ここで、例となる動作実施形態の議論に注目を向ける。
【００４６】
ここで図１０を参照すると、例となる動作環境３００の略ブロック図が示されている。動作環境３００は、１又はそれ以上のサーバ３０６と通信フレームワーク３０４を介して通信する１又はそれ上のクライアント３０２を有してよい。実施例において、クライアント３０２は、モバイル装置１０４として実施されてよく、サーバ３０６は、サーバ１０２として実施されてよい。
【００４７】
クライアント３０２は、ハードウェア装置、ソフトウェアモジュール、又はそれらの組み合わせとして具現されてよい。そのようなハードウェア装置の例には、コンピュータ（例えば、サーバ、パーソナルコンピュータ、ラップトップ、等）、携帯電話機、パーソナルデジタルアシスタント、又はあらゆるタイプのコンピュータ装置、等があるが、これらに限られない。また、クライアント３０２は、単一の実行経路、複数の同時実行経路（例えば、スレッド、プロセス、等）、又はその他の方法において実行する命令を有するソフトウェアモジュールとして具現されてよい。
【００４８】
サーバ３０６は、ハードウェア装置、ソフトウェアモジュール、又はそれらの組み合わせとして具現されてよい。そのようなハードウェア装置の例には、コンピュータ（例えば、サーバ、パーソナルコンピュータ、ラップトップ、等）、携帯電話機、パーソナルデジタルアシスタント、又はあらゆるタイプのコンピュータ装置、等があるが、これらに限られない。また、サーバ３０６は、単一の実行経路、複数の同時実行経路（例えば、スレッド、プロセス、等）、又はその他の方法において実行する命令を有するソフトウェアモジュールとして具現されてよい。
【００４９】
通信フレームワーク３０４は、クライアント３０２とサーバ３０６との間の通信を助ける。実施例において、通信フレームワーク３０４は、通信ネットワーク１０６として具現されてよい。通信フレームワーク３０４は、あらゆる通信プロトコルを用いる有線又は無線ネットワークのようなあらゆるタイプの通信媒体を体現してもよい。
【００５０】
図１１を参照すると、モバイル装置１０４は、プロセッサ３１２、メモリ３１４、ネットワークインターフェース３１６、無線トランシーバ３１８、及びディスプレイ３２０を有してよい。プロセッサ３１２は、あらゆる市販のプロセッサであってよく、デュアルマイクロプロセッサ及びマルチプロセッサアーキテクチャを有してよい。ネットワークインターフェース３１６は、モバイル装置１０４とサーバ１０２との間に通信経路を設けるために、モバイル装置１０４と通信ネットワーク１０６との間の有線又は無線通信を助ける。無線トランシーバ３１８は、衛星に基づく無線信号、セルラーに基づく無線信号、及びそれらのあらゆる組み合わせであってよい無線周波数信号を送信及び受信する能力を有する。ディスプレイ３２０は、モバイル装置のユーザに視覚的な表現を表示することができるあらゆるタイプのスクリーンであってよい。
【００５１】
メモリ３１４は、プロセッサにより実行可能な命令、プロシージャ、アプリケーション、及びデータを記憶することができるあらゆるコンピュータ可読記憶媒体又はコンピュータ可読媒体であってよい。コンピュータ可読媒体は、搬送波により送信される変調データ信号のような伝播信号とは関係がない。それは、あらゆるタイプのメモリデバイス（例えば、ランダムアクセスメモリ、読出専用メモリ、等）、磁気記憶装置、揮発性記憶装置、不揮発性記憶装置、光学記憶装置、ＤＶＤ、ＣＤ、フロッピー(登録商標)ドライブ、ディスクドライブ、フラッシュメモリ、等であってよい。メモリ３１４はまた、１以上の外部記憶装置又は遠隔に置かれた記憶装置を有してよい。メモリ３１４は、次のような命令及びデータを含んでよい：
・オペレーティングシステム３２０；
・ロケーションモジュール１２７；
・写真捕捉モジュール１３２；
・画像修正モジュール１３４；
・実時間密マッチングモジュール１３６；
・分類モジュール１３８；
・サーバインターフェースモジュール１２６；及び
・様々な他のアプリケーション及びデータ３２２。
【００５２】
図１２を参照すると、サーバ１０２は、プロセッサ３３０、メモリ３３２、及びネットワークインターフェース３３４を有してよい。プロセッサ３３０は、あらゆる市販のプロセッサであってよく、デュアルマイクロプロセッサ及びマルチプロセッサアーキテクチャを有してよい。ネットワークインターフェース３３４は、モバイル装置１０４とサーバ１０２との間に通信経路を設けるために、サーバ１０２と通信ネットワーク１０６との間の有線又は無線通信を助ける。
【００５３】
メモリ３３２は、プロセッサにより実行可能な命令、プロシージャ、アプリケーション、及びデータを記憶することができるあらゆるコンピュータ可読記憶媒体又はコンピュータ可読媒体であってよい。コンピュータ可読媒体は、搬送波により送信される変調データ信号のような伝播信号とは関係がない。それは、あらゆるタイプのメモリデバイス（例えば、ランダムアクセスメモリ、読出専用メモリ、等）、磁気記憶装置、揮発性記憶装置、不揮発性記憶装置、光学記憶装置、ＤＶＤ、ＣＤ、フロッピードライブ、ディスクドライブ、フラッシュメモリ、等であってよい。メモリ３３２はまた、１以上の外部記憶装置又は遠隔に置かれた記憶装置を有してよい。メモリ３３２は、次のような命令及びデータを含んでよい：
・オペレーティングシステム３３６；
・画像データベース１０８；
・画像修正モジュール１１２；
・特徴抽出モジュール１１４：
・トレーニング密マッチングモジュール１１６；
・分類子トレーニングモジュール１１８；
・ロケーション支援モジュール１２０；
・分類子データベース１１０；及び
・他のアプリケーション及びデータ３３８。
【００５４】
ここで記載される技術は、モバイル装置が遠隔サーバからの支援を有して高速な実時間のロケーション認識を実行することを可能にするという利点を与える。当該技術は、通信媒体に起因するレイテンシを改善するために、モバイル装置とサーバとの間で送信されるデータの量を最小限とする。画像全体ではなく、地球物理学的な位置座標がサーバへ送信される。ランダム決定フォレストをトレーニングするアプローチは、様々なランドマークを区別するための最も特徴的な特徴を自動選択する。このアプローチは、より高速にダウンロードすることができ且つ低帯域幅通信アプリケーションとって有益であるよりコンパクトなデータ構造であるランダム決定フォレストをもたらす。かかる技術は、モバイル装置が実時間のロケーション認識の要求を満たすことを可能にする。
【００５５】
対象は、構造的な特徴及び／又は方法論的な動作に特有の言語において記載されてきたが、特許請求の範囲において定義される対象は、必ずしも、記載される具体的な特徴又は動作に制限されないことが理解されるべきである。むしろ、具体的な特徴及び動作は、特許請求の範囲を実施する例となる形態として開示される。
【００５６】
例えば、システム１００の様々な実施形態は、ハードウェア要素、ソフトウェア要素、又はそれらの組み合わせにより実施されてよい。ハードウェア要素の例には、デバイス、コンポーネント、プロセッサ、マイクロプロセッサ、回路、回路素子、集積回路、特定用途向け集積器回路、プログラム可能論理デバイス、デジタル信号プロセッサ、フィールドプログラマブルゲートアレイ、メモリユニット、論理ゲート等がある。ソフトウェア要素の例には、ソフトウェアコンポーネント、プログラム、アプリケーション、コンピュータプログラム、アプリケーションプログラム、システムプログラム、機械プログラム、オペレーティングシステムソフトウェア、ミドルウェア、ファームウェア、ソフトウェアモジュール、ルーチン、サブルーチン、関数、方法、プロシージャ、ソフトウェアインターフェース、アプリケーションプログラムインターフェース、命令セット、コンピュータコード、コードセグメント、及びそれらのあらゆる組み合わせがある。実施形態がハードウェア要素及び／又はソフトウェア要素により実施されるかどうかを決定することは、所与の実施について望まれるような所望の計算速度、電力レベル、帯域幅、計算時間、負荷バランス、メモリ資源、データバス速度、及び他の設計又は性能の制約等の要因のいずれかに従って変化しうる。
【００５７】
幾つかの実施形態は、命令又はロジックを記憶する記憶媒体を有してよい。記憶媒体の例には、揮発性メモリ又は不揮発性メモリ、リムーバブル又は非リムーバブルメモリ、消去可能又は消去不可能メモリ、書込可能又は書換可能メモリ、等を含む、電子データを記憶することができる１又はそれ以上のタイプのコンピュータ可読記憶媒体がある。ロジックの例には、プログラム、プロシージャ、モジュール、アプリケーション、コードセグメント、プログラムスタック、ミドルウェア、ファームウェア、方法、ルーチン等のような様々なソフトウェアコンポーネントがある。実施例において、例えば、コンピュータ可読記憶媒体は、プロセッサによって実行される場合に、プロセッサに、記載される実施形態に従って方法及び／又は動作を実行させる実行可能なコンピュータプログラム命令を記憶してよい。実行可能なコンピュータプログラム命令は、特定の機能を実行するようコンピュータに指示するための、予め定義されたコンピュータ言語、方法又はシンタックスに従って実施されてよい。命令は、あらゆる適切なハイレベル、ローレベル、オブジェクト指向の、視覚的な、コンパイルされた及び／又は解釈されたプログラミング言語を用いて実施されてよい。
【００５８】
様々な実施形態において、ここで記載されるシステム１００は、複数のコンポーネント、プログラム、プロシージャ、モジュールを備える、コンピュータにより実施されるシステムを有してよい。ここで使用されるように、それらの用語は、ハードウェア、ハードウェア及びソフトウェアの組み合わせ、又はソフトウェアのいずれかを有する、コンピュータ関連エンティティに言及するよう意図される。例えば、コンポーネントは、プロセッサで実行されるプロセス、ハードディスクドライブ、（光学及び／又は磁気記憶媒体の）複数の記憶デバイス、オブジェクト、実行ファイル、実行のスレッド、プログラム、及び／又はコンピュータとして実施されてよい。例として、サーバで実行されるアプリケーション及びサーバは両方とも、コンポーネントであってよい。１又はそれ以上のコンポーネントが実行のスレッド及び／又はプロセス内に存在してよく、コンポーネントは、所与の実施のために望まれるように、１のコンピュータにおいてローカライズされ、且つ／あるいは、２又はそれ以上のコンピュータの間で分配されてよい。実施形態はこの態様において制限されない。  
上記の実施形態に加えて、以下の付記を開示する。
（付記１）
地球学的ロケーションに関連する第１の組の特徴記述子及びコンパクト分類子を受け取るステップと、
前記地球学的ロケーションに関連する、未知のクラスを有する画像を捕捉するステップと、
前記捕捉された画像から第２の組の特徴記述子を生成するステップと、
前記第２の組に含まれる各特徴記述子により、前記第１の組に含まれる特徴記述子ごとにＭｉｎ−Ｈａｓｈ値を計算するステップと、
前記第１の組に含まれる特徴記述子と類似するＭｉｎ−Ｈａｓｈ値を有する前記第２の組に含まれる特徴記述子ごとに類似度を生成するステップと、
前記捕捉された画像のクラスを決定するよう前記類似度に基づき前記コンパクト分類子を前記捕捉された画像へ適用するステップと
を有する、コンピュータによって実施される方法。
（付記２）
第１の装置の地球物理学的ロケーションを含むリクエストにより、前記第１の装置から前記コンパクト分類子を要求するステップを更に有し、
前記コンパクト分類子は、前記第１の装置から遠く離れて位置する第２の装置によって受け取られる、
付記１に記載の方法。
（付記３）
前記コンパクト分類子は、複数のランダム決定木を有するランダム決定フォレストであり、
前記コンパクト分類子を前記捕捉された画像へ適用するステップは、
前記捕捉された画像が前記ランダム決定木のうちの特定の１つに関連する特定のクラスと一致する確率を得るよう、前記第２の組の特徴記述子の類似度に基づき各ランダム決定木を走査することを含む、
付記１に記載の方法。
（付記４）
前記確率は確率分布を有し、
当該方法は、前記捕捉された画像に関連しそうなクラスを決定するよう、全ての前記ランダム決定木にわたってクラス毎にそれぞれの確率分布を平均するステップを更に有する、
付記３に記載の方法。
（付記５）
ランダム決定木の各ノードは、閾値と関連づけられ、
各ランダム決定木を走査することは、前記第２の組の特徴記述子の類似度を、ランダム決定木に含まれる各ノードに関連する閾値と比較することを含む、
付記３に記載の方法。
（付記６）
各特徴記述子は、ＢＲＩＥＦ特徴記述子である、
付記１に記載の方法。
（付記７）
各対が前記第１の組からの１つの特徴記述子及び前記第２の組のからの他の１つの特徴記述子とを含む特徴記述子の対についてＭｉｎ−Ｈａｓｈ値を決定し、類似したＭｉｎ−Ｈａｓｈを有する対について類似度を計算することにより、類似度に基づき第３の組の特徴記述子を特定するステップ
を更に有する付記１に記載の方法。
（付記８）
前記類似度はハミング距離に基づく、
付記１に記載の方法。
（付記９）
前記コンパクト分類子及び前記特徴記述子は、オフラインのトレーニングフェーズを通じて生成される、
付記１に記載の方法。
（付記１０）
当該方法は、モバイル装置において実施される、
付記１に記載の方法。
（付記１１）
プロセッサによって実行される場合に、該プロセッサに、
１又はそれ以上の特徴記述子を得る動作と、
捕捉された画像に関して、特徴記述子ごとに類似度を決定する動作であって、前記類似度は、特徴記述子と当該捕捉された画像における画像パッチとの最も近い一致を表し、前記捕捉された画像における画像パッチと一致する特徴記述子について計算され、該一致する特徴記述子は、Ｍｉｎ−Ｈａｓｈプロセスを用いて決定される、動作と、
前記類似度の使用により前記捕捉された画像を認識する動作と
を実行させるプロセッサ実行可能命令を記憶するコンピュータ可読記憶媒体。
（付記１２）
前記プロセッサ実行可能命令は、前記プロセッサによって実行される場合に、該プロセッサに更に、
地球学的ロケーションに関連する特徴記述子を取得するために使用される前記地球学的ロケーションを決定する動作を
実行させる、付記１１に記載のコンピュータ可読記憶媒体。
（付記１３）
前記プロセッサ実行可能命令は、前記プロセッサによって実行される場合に、該プロセッサに更に、
前記特徴記述子に関連する地球学的ロケーションに関連する分類子を取得する動作と、
前記捕捉された画像があるクラスに関連する少なくとも１つの確率を決定するよう前記特徴記述子及び類似度に前記分類子を適用する動作と
を実行させる、請求項１１に記載のコンピュータ可読記憶媒体。
（付記１４）
前記プロセッサ実行可能命令は、前記プロセッサによって実行される場合に、該プロセッサに更に、
前記類似度の決定より前に前記捕捉された画像を修正する動作
を実行させる、付記１１に記載のコンピュータ可読記憶媒体。
（付記１５）
前記プロセッサ実行可能命令は、前記プロセッサによって実行される場合に、該プロセッサに更に、
前記類似度をハミング距離として表す動作と、
一致する画像パッチを有すると特定される特徴記述子について前記ハミング距離を計算する動作と
を実行させる、付記１１に記載のコンピュータ可読記憶媒体。
（付記１６）
プロセッサによって実行される場合に、該プロセッサに、
共通の地球物理学的ロケーションに関連する１又はそれ以上のトレーニング画像から、１又はそれ以上の特徴記述子を得る動作と、
各トレーニング画像に関して、特徴記述子ごとに、当該特徴記述子と当該トレーニング画像における画像パッチに対応する全ての特徴記述子の中の最も類似した特徴記述子との間の類似を表す類似度を決定し、それらの一致する特徴記述子が、当該トレーニング画像に関して当該特徴記述子に適用されるＭｉｎ−Ｈａｓｈプロセスを用いて加速されるハミング距離計算を行うことによって決定される、動作と、
前記類似度の使用により分類子をトレーニングする動作と
実行させるプロセッサ実行可能命令を記憶するコンピュータ可読記憶媒体。
（付記１７）
前記プロセッサ実行可能命令は、前記プロセッサによって実行される場合に、該プロセッサに更に、
より顕著な特徴を有する前記トレーニング画像における画像パッチから前記特徴記述子を選択する動作
を実行させる、付記１６に記載のコンピュータ可読記憶媒体。
（付記１８）
前記プロセッサ実行可能命令は、前記プロセッサによって実行される場合に、該プロセッサに更に、
１又はそれ以上のランダム決定木を前記分類子として生成する動作
を実行させ、
各ランダム決定木は、前記特徴記述子と前記類似度とを用いてトレーニングされる、
付記１６に記載のコンピュータ可読記憶媒体。
（付記１９）
前記プロセッサ実行可能命令は、前記プロセッサによって実行される場合に、該プロセッサに更に、
前記類似度をハミング距離として表す動作と、
トレーニング画像における画像パッチと一致する特徴記述子について前記ハミング距離を計算する動作と
を実行させる、付記１６に記載のコンピュータ可読記憶媒体。
（付記２０）
前記プロセッサ実行可能命令は、前記プロセッサによって実行される場合に、該プロセッサに更に、
類似するＭｉｎ−Ｈａｓｈ値を有する特徴記述子を決定するよう前記特徴記述子にＭｉｎ−Ｈａｓｈを適用する動作と、
類似するＭｉｎ−Ｈａｓｈスケッチを有する特徴記述子について前記ハミング距離を計算する動作と
を実行させる、付記１９に記載のコンピュータ可読記憶媒体。
【図１】
0005932992.tif 000002
【図２】
0005932992.tif 000003
【図３】
0005932992.tif 000004
【図４】
0005932992.tif 000005
【図５】
0005932992.tif 000006
【図６】
0005932992.tif 000007
【図７】
0005932992.tif 000008
【図８】
0005932992.tif 000009
【図９】
0005932992.tif 000010
【図１０】
0005932992.tif 000011
【図１１】
0005932992.tif 000012
【図１２】
0005932992.tif 000013