(57)【特許請求の範囲】
【請求項１】
画像の特徴点位置情報を符号化する方法であって、
複数の六角形セルを含む六角格子を生成するステップと、
前記六角格子を使用して画像の特徴点位置を量子化するステップであって、前記特徴点位置を量子化するステップは、各特徴点位置に関して、前記特徴点位置の2次元平面から3次元空間に変換された座標を生成するステップと、前記変換された座標を対応する最も近い整数に四捨五入するステップと、前記変換された座標が前記3次元空間における六角形平面に属することを検証するステップとを含む、ステップと、
各六角形セル内の特徴点位置の出現を記録するためにヒストグラムを生成するステップと、
各六角形セル内の特徴点位置の前記出現に従って前記ヒストグラムを符号化するステップとを含む、方法。
【請求項２】
六角格子を生成するステップは、
特徴点位置情報の所定の量子化レベルに従って前記六角形セルのサイズを決定するステップを含む、請求項1に記載の方法。
【請求項３】
前記変換された座標を検証するステップは、
前記変換された座標の合計を計算するステップと、
前記変換された座標の前記合計が0に等しいことを検証するステップとを含む、請求項1に記載の方法。
【請求項４】
ヒストグラムを生成するステップは、
各六角形セル内の特徴点位置の出現を含むように構成されたヒストグラムマップを生成するステップを含む、請求項1に記載の方法。
【請求項５】
各六角形セル内の特徴点位置の出現の数を記述するように構成されたヒストグラム計数を生成するステップをさらに含む、請求項4に記載の方法。
【請求項６】
ヒストグラムを符号化するステップは、
前記ヒストグラムを一意の辞書式インデックスに変換するステップと、
固定長符号を使用して前記一意の辞書式インデックスを符号化するステップとを含む、請求項1に記載の方法。
【請求項７】
ヒストグラムを符号化するステップは、
前記ヒストグラムの空のブロックをラスタ走査順にランレングスに変換するステップと、
エントロピーコーダを使用して前記ランレングスを符号化するステップとをさらに含む、請求項1に記載の方法。
【請求項８】
前記エントロピーコーダは、ゴロムライス符号を使用する、請求項7に記載の方法。
【請求項９】
前記エントロピーコーダは、ハフマン符号を使用する、請求項7に記載の方法。
【請求項１０】
前記エントロピーコーダは、算術符号を使用する、請求項7に記載の方法。
【請求項１１】
ヒストグラムを符号化するステップは、
前記ヒストグラム内の符号化すべき後続の六角形セルの情報を符号化するために、隣接する六角形セルのコンテキスト情報を適用するステップをさらに含む、請求項1に記載の方法。
【請求項１２】
前記コンテキスト情報は、
符号化すべき後続の六角形セルの1次隣接部からのコンテキスト情報を含む、請求項11に記載の方法。
【請求項１３】
前記コンテキスト情報は、
符号化すべき前記後続の六角形セルの2次隣接部からのコンテキスト情報をさらに含む、請求項12に記載の方法。
【請求項１４】
コンテキスト情報は、算術エンコーダに関する入力として使用される、請求項11に記載の方法。
【請求項１５】
画像を取得するように構成された画像モジュールと、
前記画像の符号化された特徴点位置情報を生成するように構成されたビジュアル探索モジュールと、
ワイヤレスネットワークを介して前記画像の前記符号化された特徴点位置情報をサーバに通信するように構成されたコントローラとを含む、モバイルデバイスであって、
前記ビジュアル探索モジュールは、
複数の六角形セルを含む六角格子を生成するためのロジックと、
前記六角格子を使用して画像の特徴点位置を量子化するためのロジックであって、特徴点位置を量子化するためのロジックは、各特徴点位置に関して、前記特徴点位置の2次元平面から3次元空間に変換された座標を生成するためのロジックと、前記変換された座標を対応する最も近い整数に四捨五入するためのロジックと、前記変換された座標が前記3次元空間における六角形平面に属することを検証するためのロジックとを含む、ロジックと、
各六角形セル内の特徴点位置の出現を記録するためにヒストグラムを生成するためのロジックと、
各六角形セル内の特徴点位置の前記出現に従って前記ヒストグラムを符号化するためのロジックとを含む、モバイルデバイス。
【請求項１６】
六角格子を生成するためのロジックは、
特徴点位置情報の所定の量子化レベルに従って前記六角形セルのサイズを決定するためのロジックを含む、請求項15に記載のモバイルデバイス。
【請求項１７】
前記変換された座標を検証するためのロジックは、
前記変換された座標の合計を計算するためのロジックと、
前記変換された座標の前記合計が0に等しいことを検証するためのロジックとを含む、請求項15に記載のモバイルデバイス。
【請求項１８】
ヒストグラムを生成するためのロジックは、
各六角形セル内の特徴点位置の出現を含むように構成されたヒストグラムマップを生成するためのロジックを含む、請求項15に記載のモバイルデバイス。
【請求項１９】
各六角形セル内の特徴点位置の出現の数を記述するように構成されたヒストグラム計数を生成するためのロジックをさらに含む、請求項18に記載のモバイルデバイス。
【請求項２０】
ヒストグラムを符号化するためのロジックは、
前記ヒストグラムを一意の辞書式インデックスに変換するためのロジックと、
固定長符号を使用して前記一意の辞書式インデックスを符号化するためのロジックとを含む、請求項15に記載のモバイルデバイス。
【請求項２１】
ヒストグラムを符号化するためのロジックは、
前記ヒストグラムの空のブロックをラスタ走査順にランレングスに変換するためのロジックと、
エントロピーコーダを使用して前記ランレングスを符号化するためのロジックとをさらに含む、請求項15に記載のモバイルデバイス。
【請求項２２】
前記ヒストグラムを符号化するためのロジックは、
前記ヒストグラム内の符号化すべき後続の六角形セルの情報を符号化するために、隣接する六角形セルのコンテキスト情報を適用するためのロジックをさらに含む、請求項15に記載のモバイルデバイス。
【請求項２３】
前記コンテキスト情報は、
符号化すべき後続の六角形セルの1次隣接部からのコンテキスト情報を含む、請求項22に記載のモバイルデバイス。
【請求項２４】
前記コンテキスト情報は、
符号化すべき前記後続の六角形セルの2次隣接部からのコンテキスト情報をさらに含む、請求項23に記載のモバイルデバイス。
【請求項２５】
画像を取得するように構成された画像モジュールと、
前記画像の符号化された特徴点位置情報を生成するように構成されたビジュアル探索モジュールと、
ワイヤレスネットワークを介して前記画像の前記符号化された特徴点位置情報をサーバに通信するように構成されたコントローラとを含む、モバイルデバイスであって、
前記ビジュアル探索モジュールは、
複数の六角形セルを含む六角格子を生成するための手段と、
前記六角格子を使用して画像の特徴点位置を量子化するための手段であって、特徴点位置を量子化するための手段は、各特徴点位置に関して、前記特徴点位置の2次元平面から3次元空間に変換された座標を生成するための手段と、前記変換された座標を対応する最も近い整数に四捨五入するための手段と、前記変換された座標が前記3次元空間における六角形平面に属することを検証するための手段とを含む、手段と、
各六角形セル内の特徴点位置の出現を記録するためにヒストグラムを生成するための手段と、
各六角形セル内の特徴点位置の前記出現に従って前記ヒストグラムを符号化するための手段とを含む、モバイルデバイス。
【請求項２６】
ヒストグラムを生成するための手段は、
各六角形セル内の特徴点位置の出現を含むように構成されたヒストグラムマップを生成するための手段を含む、請求項25に記載のモバイルデバイス。
【請求項２７】
各六角形セル内の特徴点位置の出現の数を記述するように構成されたヒストグラム計数を生成するための手段をさらに含む、請求項26に記載のモバイルデバイス。
【請求項２８】
前記ヒストグラムを符号化するための手段は、
前記ヒストグラム内の符号化すべき後続の六角形セルの情報を符号化するために、隣接する六角形セルのコンテキスト情報を適用するための手段をさらに含む、請求項25に記載のモバイルデバイス。
【請求項２９】
前記コンテキスト情報は、
符号化すべき後続の六角形セルの1次隣接部からのコンテキスト情報を含む、請求項28に記載のモバイルデバイス。
【請求項３０】
前記コンテキスト情報は、
符号化すべき前記後続の六角形セルの2次隣接部からのコンテキスト情報をさらに含む、請求項29に記載のモバイルデバイス。
【請求項３１】
画像の特徴点位置情報を符号化するためのコンピュータプログラムであって、
複数の六角形セルを含む六角格子を生成するためのコードと、
前記六角格子を使用して画像の特徴点位置を量子化するためのコードであって、特徴点位置を量子化するためのコードは、各特徴点位置に関して、前記特徴点位置の2次元平面から3次元空間に変換された座標を生成するためのコードと、前記変換された座標を対応する最も近い整数に四捨五入するためのコードと、前記変換された座標が前記3次元空間における六角形平面に属することを検証するためのコードとを含む、コードと、
各六角形セル内の特徴点位置の出現を記録するためにヒストグラムを生成するためのコードと、
各六角形セル内の特徴点位置の前記出現に従って前記ヒストグラムを符号化するためのコードとを含む、コンピュータプログラム。
【請求項３２】
ヒストグラムを生成するためのコードは、
各六角形セル内の特徴点位置の出現を含むように構成されたヒストグラムマップを生成するためのコードを含む、請求項31に記載のコンピュータプログラム。
【請求項３３】
各六角形セル内の特徴点位置の出現の数を記述するように構成されたヒストグラム計数を生成するためのコードをさらに含む、請求項32に記載のコンピュータプログラム。
【請求項３４】
前記ヒストグラムを生成するためのコードは、
前記ヒストグラム内の符号化すべき後続の六角形セルの情報を符号化するために、隣接する六角形セルのコンテキスト情報を適用するためのコードをさらに含む、請求項31に記載のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、デジタル画像データ処理の分野に関する。具体的には、本開示は、画像の特徴点位置情報の符号化に関する。
【０００２】
関連出願の相互参照
本出願は、2011年9月9日に出願した米国出願第13/229,654号、「Coding of Feature Location Information」の利益を主張し、この出願は、2011年8月10日に出願した米国仮出願第61/522,171号、「Coding of Feature Location Information」の利益を主張するものである。前述の米国出願は、その全体が参照により本明細書に組み込まれている。
【背景技術】
【０００３】
市場ではカメラ付電話および携帯情報端末(PDA)が広く採用されるようになり、これらが、ビジュアル探索アプリケーションおよびモバイル拡張現実アプリケーション用のユビキタスプラットフォームとなっている。画像の比較を必要とするアプリケーションをサポートするために、情報は、モバイルデバイスからサーバにアップロードされるか、またはサーバからモバイルデバイスにダウンロードされる必要がある。ワイヤレスネットワークを介して送信および/または受信されるデータ量は、そのようなアプリケーションの性能および使いやすさにとって重要になる。
【０００４】
従来の特徴点ベースの探索システムは、典型的には、位置情報を符号化するための簡単な方式を使用する。そのようなシステムでは、各特徴点の(x,y)座標は、1特徴点位置当たり8ビットなどのいくつかの固定された分解能で量子化される。次いで、そのような量子化された(x,y)の対は、記憶および送信される。たとえば、千個の特徴点および8ビット分解能を有する画像が使用される場合、この方式は、1画像当たり約2Kバイトのデータを必要とするであろう。そのようなデータ符号化方式は、ワイヤレスネットワークを介して送信する必要がある大量のデータをもたらすことになり、次々と、ビジュアル探索アプリケーションおよびモバイル拡張現実アプリケーションの性能および使いやすさに悪影響を及ぼすこととなる。
【０００５】
したがって、従来のシステムの上記の問題点に対処することができる特徴点位置情報を符号化するためのシステムおよび方法が求められる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Tsaiら、「Location coding for mobile image retrieval systems」、Proceedings of International Mobile Multimedia Communications Conference、2009年9月
【非特許文献２】Y. A. Reznik、「An Algorithm for Quantization of Discrete Probability Distributions」、Proceedings of Data Compression Conference(DCC'11)、333〜343頁、2011年3月
【発明の概要】
【課題を解決するための手段】
【０００７】
本開示は、画像の特徴点位置情報の符号化に関する。本開示の実施形態によれば、画像の特徴点位置情報を符号化する方法は、複数の六角形セルを含む六角格子を生成するステップと、六角格子を使用して画像の特徴点位置を量子化するステップと、各六角形セル内の特徴点位置の出現を記録するためにヒストグラムを生成するステップと、各六角形セル内の特徴点位置の出現の数に従ってヒストグラムを符号化するステップとを含む。
【０００８】
六角格子を生成する方法は、特徴点位置情報の所定の量子化レベルに従って六角形セルのサイズを決定するステップを含む。特徴点位置を量子化する方法は、各特徴点位置の2次元平面から3次元空間への座標の変換を実行するステップと、変換された座標を対応する最も近い整数に四捨五入するステップと、変換された座標が3次元空間における六角形平面に属することを検証するステップとを含む。この変換は可逆であることに留意されたい。変換された座標が3次元空間における六角形平面に属することを検証するために、本方法は、変換された座標の合計を計算し、変換された座標の合計が0に等しいかどうかを検証する。
【０００９】
ヒストグラムを生成する方法は、各六角形セル内の特徴点位置の出現を含むように構成されたヒストグラムマップを生成するステップと、各六角形セル内の特徴点位置の出現の数を記述するように構成されたヒストグラム計数を生成するステップとを含む。ヒストグラムを符号化する方法は、ヒストグラム内の符号化すべき後続の六角形セルの情報を符号化するために隣接する六角形セルのコンテキスト情報を適用するステップを含むことができるが、このコンテキスト情報は、1次隣接部からのコンテキスト情報と、符号化すべき後続の六角形セルの2次隣接部からのコンテキスト情報とを含む。
【００１０】
別の実施形態では、モバイルデバイスは、画像を取得するように構成された画像モジュールと、画像の符号化された特徴点位置情報を生成するように構成されたビジュアル探索モジュールと、ワイヤレスネットワークを介して画像の符号化された特徴点位置情報をサーバに通信するように構成されたコントローラとを含む。モバイルデバイスのビジュアル探索モジュールは、六角格子を生成するためのロジックを含み、この六角格子は、複数の六角形セルと、六角格子を使用して画像の特徴点位置を量子化するためのロジックと、各六角形セル内の特徴点位置の出現を記録するためにヒストグラムを生成するためのロジックと、各六角形セル内の特徴点位置の出現に従ってヒストグラムを符号化するためのロジックとを含む。
【００１１】
本開示の上述の特徴および利点、ならびに本開示の追加の特徴および利点は、以下の図面とともに本開示の実施形態の詳細な説明を読めば、より明確に理解できよう。
【図面の簡単な説明】
【００１２】
【図１ａ】本開示のいくつかの態様による、特徴点位置ヒストグラムを生成する方法を示す図である。
【図１ｂ】本開示のいくつかの態様による、特徴点位置ヒストグラムを生成する方法を示す図である。
【図２】本開示のいくつかの態様による、特徴点位置ヒストグラムを生成する別の方法を示す図である。
【図３ａ】本開示のいくつかの態様による、3次元(3D)空間内の六角形平面を有する特徴点位置情報を表す方法を示す図である。
【図３ｂ】本開示のいくつかの態様による六角形セルの性質を示す図である。
【図４ａ】本開示のいくつかの態様による、ヒストグラム値の統計的適応符号化のためのコンテキスト構成の適用を示す図である。
【図４ｂ】本開示のいくつかの態様による、ヒストグラム値の統計的適応符号化のためのコンテキスト構成の適用を示す図である。
【図５】本開示のいくつかの態様による、正方格子を利用する特徴点位置符号化方式と、六角形格子を利用する特徴点位置符号化方式との比較を示す図である。
【図６ａ】本開示のいくつかの態様によるビジュアル探索を実行するように構成されたモバイルデバイスのブロック図である。
【図６ｂ】本開示の実施形態による画像探索のための方法を示す図である。
【図６ｃ】本開示の実施形態による、画像の特徴点位置情報を符号化する方法を示す図である。
【図７ａ】本開示の実施形態によるビジュアル探索機能の例示的な実装形態を示す図である。
【図７ｂ】本開示の実施形態によるビジュアル探索機能の例示的な実装形態を示す図である。
【図８ａ】本開示の実施形態による、特徴点位置割出しにおける語彙ツリーおよび関連する転置インデックスの使用を示す図である。
【図８ｂ】本開示の実施形態による、特徴点位置割出しにおける語彙ツリーおよび関連する転置インデックスの使用を示す図である。
【発明を実施するための形態】
【００１３】
特徴点位置情報を符号化する実施形態を開示する。以下の説明は、いかなる当業者でも本開示を作成し使用することができるように提示される。特定の実施形態および適用の説明は、例としてのみ提供される。本明細書で説明する例の様々な修正および組合せが当業者には容易に明らかであり、本明細書で定義した一般原理は、本開示の趣旨および範囲から逸脱することなく他の例および適用に適用できる。したがって、本開示は、説明され示される例に限定されるものではなく、本明細書で開示される原理および特徴に一致する最大の範囲を与えられるものである。
【００１４】
図1aは、Tsaiら、「Location coding for mobile image retrieval systems」、Proceedings of International Mobile Multimedia Communications Conference、2009年9月によって説明される矩形グリッドを使用して特徴点位置ヒストグラムを生成する方法を示す。この文献は、その全体が参照により本明細書に組み込まれている。102では、黒いドットは、画像の特徴点を表す。104では、画像は、複数の正方セルを含む正方グリッドを上描きされる。各正方セルのサイズは、アプリケーションに応じて、2×2正方画素から32×32正方画素まで変化し得る。106では、画像の特徴点の位置を示すために、ヒストグラムマップが生成される。黒いドットを含む、ヒストグラムマップ内のセルは、グレーで示され、黒いドットを含まないセルは、白で示される。特徴点が2つの正方セルの間の境界線上にある場合、特徴点のより大きい領域を含む正方セルが選択される。特徴点が2つのセルの間に均等に分布している場合、セルのいずれか一方を選択することができる。108では、106のヒストグラムマップに基づいて、ヒストグラム計数が生成される。正方セルの数は、106のヒストグラムマップの正方セル内にある特徴点の数を表す。
【００１５】
本開示の実施形態によれば、nが画像の特徴点の数を示し、mがヒストグラム内のセルの数を示すものとする。次いで、ビデオグラフィックスアレイ(VGA)画像を与え、Scale-Invariant Feature Transform(SIFT)またはSpeed Up Robust Feature(SURF)を使用すれば、n=1000の場合、m=640*480/w2となるが、wはセルのサイズ(画素)である。
【００１６】
元が2度以上現れることが許される多重集合の概念が、特徴点位置情報のヒストグラムを表すために使用され得ることに留意されたい。要素が多重集合に属する度数は、その元の重複度である。繰り返された元を含む、多重集合内の要素の総数は、多重集合の濃度である。たとえば、多重集合{a,a,b,b,b,c}では、元a、b、およびcの重複度は、それぞれ、2、3、および1であり、多重集合の濃度は6である。
【００１７】
図1aに示される例では、要素が濃度mの有限集合から取られる、濃度nの多重集合の数は、多重集合係数(multiset coefficient)または多重集合数である。m個のセルおよびn個の総数を有する、考えられるヒストグラムの数は、多重集合係数
【００１８】
【数１】
0005911578.tif 000002
【００１９】
によって与えられる。
【００２０】
したがって、すべてのヒストグラムが等確率であると仮定すると、ヒストグラムを符号化するために、おおよそ
【００２１】
【数２】
0005911578.tif 000003
【００２２】
ビットを費やす可能性がある。上記の式において、Oは、ビッグO記法を表し、通常、より簡単な関数の観点から、独立変数が特定の値または無限大に向かう際の関数の限定的な挙動を説明する。ビッグO記法は、同じO記法を使用して同じ成長率を有する様々な関数を表すことができるように、それらの成長率に従う関数を特徴づける。また、αは定数であり、H(.)は、H(x)=-xlogx-(1-x)log(1-x)のようなエントロピー関数であると仮定される。
【００２３】
この公式を使用することによって得られる数は、n=1000の場合、m=640*480/w2と示されるが、wは位置ヒストグラムブロックサイズを表す。1特徴点位置当たりのビット数対位置ヒストグラムブロックサイズwのプロットが図1bに示される。このプロットでは、ブロックサイズが小さい(たとえば、2画素)とき、特徴点位置情報の符号化レートは大きい(約8ビット/特徴点)。ブロックサイズが増加するにつれて、特徴点位置情報の符号化レートは減少する。ブロックサイズが約30画素であるとき、符号化レートは約1ビット/特徴点である。図1bは、Tsaiらによって報告された経験的なエントロピー推定値を含む。経験的なエントロピー推定値がモデル情報の伝達コストの原因にならず、したがって、それらの推定値は、上記の公式によって予測される曲線よりもわずかに落ちることに留意されたい。一般に、それらの推定値は、位置ヒストグラムブロックサイズwに対して同様の傾向をたどる。
【００２４】
この方式によってもたらされるひずみ(半径をカバーする)は、ブロックサイズwに正比例する可能性があり、所与の点qおよびその対応する再構成された点q'では、
【００２５】
【数３】
0005911578.tif 000004
【００２６】
となることにも留意されたい。
【００２７】
上記の関係式を使用すると、ヒストグラム位置符号化に関する(たとえば、L2ノルムに関する)レートひずみ特性は、
【００２８】
【数４】
0005911578.tif 000005
【００２９】
と表すことができる。
ここで、WおよびHは、入力画像の幅および高さを示し、nは特徴点の数であり、右側の漸近式は、厳密に(ε→0)とすることで得られる。
【００３０】
図2は、本開示のいくつかの態様による、特徴点位置ヒストグラムを生成する別の方法を示す。202では、黒いドットは、画像の特徴点を表す。204では、画像は、複数の六角形セルを含む六角格子(六方格子とも呼ばれる)を上描きされる。206では、画像の特徴点の位置を示すために、ヒストグラムマップが形成され得る。この例では、黒いドットを含む、ヒストグラムマップ内のセルは、グレーで示され、黒いドットを含まないセルは、白で示される。特徴点が2つの六角形セルの間の境界線上にある場合、特徴点のより大きい領域を含む六角形セルが選択される。特徴点が2つのセルの間に均等に分布している場合、セルのいずれか一方を選択することができる。208では、206のヒストグラムマップに基づいて、ヒストグラム計数が形成され得る。六角形セルの数は、206のヒストグラムマップの六角形セル内にある特徴点の数を表す。1特徴点当たり4ビット、5ビット、または6ビットなどの、特徴点位置情報に関する様々な量子化レベルをもたらすために、様々なサイズの六角形セルを使用することができることに留意されたい。たとえば、六角格子内の六角形セルの辺は、2画素、4画素、8画素、16画素、または32画素のサイズを有することができる。六角形セルの各サイズにおいて、ヒストグラムマップのエントロピーは、1特徴点当たりの様々なビットレートおよび1画像当たりの様々なビットレートを有することができ、ヒストグラム計数のエントロピーは、1特徴点当たりの様々なビットレートを有することができるが、ビットレートは、画像が異なれば変化する可能性がある。同様に、六角形セルの各サイズ、すなわち2画素、4画素、8画素、16画素、または32画素は、特徴点位置情報に関する様々な量子化レベルをもたらすことができる。ヒストグラムマップおよびヒストグラム計数は、別々に符号化することができ、隣接する六角形セルの特徴点の空間的関係は、ヒストグラムマップを符号化する際に使用することができる。
【００３１】
図2に示す方法は、空間的特徴点位置の正方格子区画を六方格子区画に置き換える。この手法を用いると、六方格子に量子化される特徴点位置のヒストグラムが計算され、次いで、計算結果が符号化される。特徴点位置ヒストグラムを作成する目的は、各特徴点の位置情報を符号化するために必要なビットの数を低減させることである。1つの手法は、各特徴点の位置情報を符号化するのではなく、特徴点の位置情報を位置ヒストグラムに変換し、位置ヒストグラムを符号化することである。位置情報を位置ヒストグラムに変換し、そのヒストグラムを符号化する利点がある。第1に、このやり方は、符号化されるアイテムの程度に基づかない符号化方法を可能にし、したがって、符号化のビットレートを低減させる。加えて、特徴点が画像内の構造点である可能性があるので、符号化処理において、特徴点間の空間構造的関係を利用することができる。
【００３２】
図3aは、本開示のいくつかの態様による、3次元(3D)空間内の六角形平面を有する特徴点位置情報を表す方法を示す。図3aに示すように、3D空間は、u軸、v軸、およびw軸によって定義される立方体302として示される。六角形平面304は、305、306、307、308、309、および310における頂点を用いて示すように形成され得る。この例における六角形平面304の中心312は、座標(0.0,0.0,0.0)を有する立方体302の中心でもある。
【００３３】
本開示の実施形態によれば、六角形平面を有する特徴点位置情報を表す方法は、画像特徴点の座標(x,y)を2次元(2D)空間から3D空間内の六角形平面304に投影することができる。3D空間内の点は、六角形平面のu座標、v座標、およびw座標の合計がu+v+w=0の条件を満たす際の六角形平面上にある。
【００３４】
1つの例示的な手法では、2D空間内の点を3D空間に変換するために、以下の行列が使用される。
【００３５】
【数５】
0005911578.tif 000006
【００３６】
また、上記の行列は、以下の条件を満たす。
【００３７】
【数６】
0005911578.tif 000007
【００３８】
これは、変換(u,v,w)=(x,y)・M
が、(x,y)=(u,v,w)・MTというぐあいに可逆であり得ることを意味する。
【００３９】
そのような変換の例を図3aに示す。平面u+v+w=0上の六方格子は、整数座標
【００４０】
【数７】
0005911578.tif 000008
【００４１】
を有する、点314aおよび314bなどの点の組である。
【００４２】
本開示の実施形態によれば、3D空間内の変換された点を量子化する方法は、以下の計算を含む。
【００４３】
座標q=(uq,vq,wq)によって3D空間内の点qを与えて、点q'=(〈uq〉,〈vq〉,〈wq〉)と定義する。
ここで、〈x〉は、実際のxに最も近い整数を示す。
【００４４】
合計を計算し、量子化された点が六角形平面Δ=〈uq〉+〈vq〉+〈wq〉上にあるかどうかを検証する。
量子化された点が六角形平面上にあることを意味する、Δ=0の場合、この処理が完了する。言い換えれば、q'は六角形平面(u+v+w=0)に属し、したがって、q'は、有効な格子点である。
【００４５】
誤差δ=((uq-〈uq〉,vq-〈vq〉,wq-〈wq〉)を計算し、-1/2≦δ1≦δ2≦δ3≦1/2となるように誤差をソートする。
【００４６】
Δ>0の場合、誤差δiの最も高い値を有するq'のΔ成分から1を減算する。Δ<0の場合、誤差δiの最も小さい値を有するq'の|Δ|成分に1を加算する。格子点への画像特徴点位置(x,y)のマッピングの粗さを制御するために、スケールパラメータσを導入することができる。全量子化処理を一連の変換(x,y)→(u,v,w)=σ-1(x,y)M→(u,v,w)latticeとして記述することができることに留意されたい。
再構成された値(x',y')は、(u,v,w)lattice→σ(u,v,w)latticeMT→(x',y')のように得られる。
【００４７】
本開示の実施形態によれば、格子点を計数し、符号化することができるいくつかの技法が存在する。1つの手法は、本方法が画像の座標(x,y)のラスタ走査を行うときに六角形セルが現れる順序を追うことである。そうでない場合、本方法は、これらの座標の値の辞書式順序に従って六角形セルを計数する。
【００４８】
いくつかの実装形態では、本方法は、画像の座標を含むセルを走査し、各セルにマッピングされる特徴点の数を計数する。ヒストグラムが計算された後、そのヒストグラムを一意のインデックスにマッピングし、次いで符号化することができる。上記のように、m個のセルおよびn個の総数を有する、考えられるヒストグラムの数は、多重集合係数
【００４９】
【数８】
0005911578.tif 000009
【００５０】
によって与えることができ、ヒストグラムインデックスを表すために必要なレートは、
【００５１】
【数９】
0005911578.tif 000010
【００５２】
である。
【００５３】
本開示の実施形態によれば、図2のヒストグラムマップ206およびヒストグラム計数208を符号化するために、様々な符号化技法を使用することができる。1つの手法では、ヒストグラムは、一意の辞書式インデックスに変換され、次いで、R(m,n)ビットの固定長符号を使用して符号化され得る。m個のビン、n個の総数、および各ビンにおける個々の計数k1,...,kmを有するヒストグラムが与えられると、全体が参照により含まれている、Y. A. Reznik、「An Algorithm for Quantization of Discrete Probability Distributions」、Proceedings of Data Compression Conference(DCC'11)、333〜343頁、2011年3月によって説明される、一意のインデックスI(k1,...,km)は、次のように得ることができる。
【００５４】
【数１０】
0005911578.tif 000011
【００５５】
この公式は、帰納法に従い(m=2,3,...で開始する)、タイプの辞書式数え上げを行う。たとえば、
I(0,0,...0,n)=0、
I(0,0,...1,n-1)=1、
...
【００５６】
【数１１】
0005911578.tif 000012
【００５７】
別の手法では、ヒストグラムマップ内の空のブロックは、ラスタ走査の順序でランレングスに変換することができる。次いで、ランレングスは、エントロピーコーダを使用して符号化される。エントロピーコーダは、ゴロムライス符号、ハフマン符号、または算術符号のうちの少なくとも1つを使用することができる。別の手法では、本方法は、キーポイントの空間分布の性質を取り込む可変長符号化手法を使用する。さらに別の手法では、コンテキストとして、いくつかの周囲の六角形セルにおけるヒストグラム値が使用される。さらに、そのようなコンテキスト構成を図4aおよび図4bに関連して説明する。
【００５８】
図4aおよび図4bは、本開示のいくつかの態様による、ヒストグラム値の統計的適応符号化のためのコンテキスト構成の適用を示す。図4aでは、六角格子内の六角形セルXを符号化するために、六角形のヒストグラムマップおよびヒストグラム計数を符号化するのに、1次隣接部A、B、およびCからのコンテキスト情報を使用することができる。この例では、1次隣接部A、B、およびCは、前に符号化された六角形セルであり、六角形セルXは、符号化すべき後続の六角形セルである。図4bでは同様に、六角格子内の六角形セルYを符号化するために、六角形のヒストグラムマップおよびヒストグラム計数を符号化するのに、1次および2次の隣接部、すなわちA、B、C、D、E、F、G、H、およびIからのコンテキスト情報を使用することができる。1次および2次の隣接部A、B、C、D、E、F、G、H、およびIは、前に符号化された六角形セルであり、六角形セルYは、符号化すべき後続の六角形セルである。
【００５９】
六方格子は、正方格子と比較して、コンテキストとして使用することができる点のより良い配置を提供することに留意されたい。たとえば、図4aでは、コンテキストとして3つの1次の隣接する六角形セルA、B、およびCを使用することができる。一方、正方格子では、左から右への走査方向および上部から下部への走査方向を仮定すると、利用できるそのような1次の隣接する正方セルが2つだけ、すなわち上側の正方セルおよび左側の正方セルが存在する。
【００６０】
六方格子は、正方格子と比較して、2次元(2D)空間のより細かいカバーをもたらすことに留意されたい。このことにより、特徴点位置表現の精度が改善される。図4aおよび図4bに示すように、六角形空間へのマッピングは、コンテキストモデル化およびエントロピー符号化の観点から有利である。画像特徴点位置を六角形空間に変換する方法は、実際の画素値を変更せず、そのことは、計算資源の点で効果的に実行することができることを意味する。
【００６１】
以下のセクションは、六方格子を使用して特徴点位置情報を符号化する利点を分析する。1つの手法は、提案された方式のレートひずみ特性を推定し、正方格子を使用して特徴点位置情報を符号化する方式と比較することである。
【００６２】
2つの格子点(0,0,0)および(0,1,1)を考え、これらを画素領域に再び変換する。(u,v,w)lattice→σ(u,v,w)latticeMT→(x',y')のような変換がマッピングによって行われることを思い起こされたい。
ここで、σはスケールパラメータである。これは、
【００６３】
【数１２】
0005911578.tif 000013
【００６４】
および
【００６５】
【数１３】
0005911578.tif 000014
【００６６】
を生成する。
【００６７】
画素領域におけるこれらの点の間の距離は、
【００６８】
【数１４】
0005911578.tif 000015
【００６９】
である。
格子領域における同じ距離は、図3bに示す六角形セルの高さ
【００７０】
【数１５】
0005911578.tif 000016
【００７１】
に対応する。
画素領域におけるセルの半径は、
【００７２】
【数１６】
0005911578.tif 000017
【００７３】
と表すことができる。
同様に、単一の六角形セルによって占められる領域を
【００７４】
【数１７】
0005911578.tif 000018
【００７５】
と表すことができる。
H×W画素を有する画像が与えられると、それをカバーするのに少なくとも
【００７６】
【数１８】
0005911578.tif 000019
【００７７】
の六角形セルが必要であろう。この場合、L2ノルムベースの量子化誤差は、カバーする半径
【００７８】
【数１９】
0005911578.tif 000020
【００７９】
に等しい。
さらに、これは、以下の関係式
【００８０】
【数２０】
0005911578.tif 000021
【００８１】
およびレートひずみ関数
【００８２】
を生成する。
【００８３】
【数２１】
0005911578.tif 000022
【００８４】
比較すると、正方格子のレートひずみ関数は、
【００８５】
【数２２】
0005911578.tif 000023
【００８６】
である。
【００８７】
したがって、提案された量子化方式は、ほぼ
【００８８】
【数２３】
0005911578.tif 000024
【００８９】
ビット/特徴点を節約することができるが、最悪の精度は同じに維持される。
【００９０】
図5は、本開示のいくつかの態様による、正方格子を利用する特徴点位置符号化方式と、六角形格子を利用する特徴点位置符号化方式との比較を示す。プロット502は、六方格子符号化方式を使用した量子化誤差にわたる1特徴点位置当たりのビット数を表す。プロット504は、正方格子符号化方式を使用した量子化誤差にわたる1特徴点位置当たりのビット数を表す。どちらのプロットも、約1千特徴点を有するVGA画像を使用する。この例に示すように、位置符号化が5ビット/特徴点のビットレートで演算される場合、六方格子符号化方式は、正方格子符号化方式よりも約8.16%のビットレートの改善がある。
【００９１】
本開示の実施形態では、画像特徴点位置情報の符号化に関する改善された技法を説明する。本技法は、特徴点位置の量子化、格子セル内の特徴点位置の出現のヒストグラムの構築、およびこのヒストグラムの符号化に六方格子を使用する。本技法のパフォーマンスは、分析され、正方格子を使用したヒストグラム符号化(位置パラメータのスカラー量子化)のパフォーマンスと比較される。提案された方式は、位置符号化のビットレートのかなりの改善につながることが示される。本技法は、モバイルプラットフォーム上に実装するのに適している。
【００９２】
開示された方法は、ビジュアル探索および拡張現実(AR)システムがいくつかのタスクを実行するために特徴点位置情報に依存するモバイルデバイスに適用可能である可能性がある。たとえば、特徴点位置情報は、1)画像間のマッチングの幾何学的検証、2)同じオブジェクトの見方の間の幾何学的変換のパラメータを計算すること、3)注目するオブジェクトの境界線を位置特定し投影すること、および4)追加の情報によりキャプチャされた画像またはビデオ内の認識されたオブジェクトの見方を拡張すること、ならびに他の目的のために使用することができる。
【００９３】
いくつかの場合には、ARおよびビジュアル探索システムは、位置情報がコンパクトに表され、形式を使用しやすい場合、利益を得る可能性がある。位置情報がワイヤレスネットワークを介して送信される必要がある場合、コンパクト性が特に重要である。また、位置情報の精度の若干のロスは、検索精度ならびに領域/オブジェクトのマッチングの位置特定の精度および幾何学的変換のパラメータに影響を及ぼす可能性があるが、ある程度までなら許容することができる。
【００９４】
図6aは、本開示のいくつかの態様によるビジュアル探索を実行するように構成されたモバイルデバイスのブロック図を示す。モバイルデバイスにおいて、アンテナ602は、基地局から変調信号を受信し、受信信号をモデム604の復調器(DEMOD)部分に提供する。復調器は、受信信号の処理(たとえば、調整およびデジタル化)を行い、入力サンプルを取得する。それはさらに、入力サンプルに対して直交周波数分割多重(OFDM)復調を実行し、すべてのサブキャリア用の周波数領域受信シンボルを提供する。RXデータプロセッサ606は、周波数領域受信シンボルの処理(たとえば、シンボルデマップ、デインターリーブ、および復号)を行い、モバイルデバイスのコントローラ/プロセッサ608に復号データを提供する。
【００９５】
コントローラ/プロセッサ608は、ワイヤレスネットワークを介してサーバと通信するためにモバイルデバイスを制御するように構成することができる。TXデータプロセッサ610はシグナリングシンボル、データシンボル、およびパイロットシンボルを生成し、これらはモデム604の変調器(MOD)によって処理され、アンテナ602を介して基地局に送信され得る。加えて、コントローラ/プロセッサ608は、モバイルデバイスにおける様々な処理ユニットの動作を指示する。メモリ612は、モバイルデバイス用のプログラムコードおよびデータを記憶するように構成することができる。画像モジュール616は、画像を取得するように構成することができる。ビジュアル探索モジュール614は、画像の特徴点位置情報を符号化する方法および以下で説明する画像検索の方法を実施するように構成することができる。
【００９６】
本開示の実施形態によれば、コンテンツベースの画像検索は、「Bag of Features」(BoF)または「Bag of Words」(BoW)と呼ばれる手法を使用することができる。BoW手法は、テキスト文書の検索から導出される。ウェブベージなどの特定のテキスト文書を見つけるために、数個の十分に選択されたワードを使用することは十分である。データベースでは、同様に、文書自体は、顕著なワードが文書内のどこに現れるかにかかわらず、顕著なワードの「bag」によって表すことができる。画像に関して、特定の画像の特徴であるロバストな局部特徴点は、「ビジュアルワード」の役割を担う。テキストの検索と同様に、BoF画像検索は、少なくとも検索パイプラインの最初の段階では、特徴点が画像内のどこに発生するかを考えない。
【００９７】
図6bは、本開示の実施形態による画像探索のための方法を示す。ブロック622では、本方法は、クエリ画像を取得する。ブロック624では、局所的画像特徴点/記述子は、クエリ画像から抽出される。次いで、ブロック626では、そのような記述子は、データベース630に記憶された画像の記述子とマッチングされる。記述子マッチング機能は、局所的画像特徴点のマッチングと、最も高いスコアを有する画像を選択することと、幾何学的検証を実行することとをさらに含むことができる。次いで、ブロック628では、クエリ画像と共通する多くの特徴点を有する画像が選択され、列挙される。観察位置の変化によってはうまく説明することができない特徴点位置とのマッチングを拒絶するために、以下で説明する幾何学的検証ステップを使用することができる。
【００９８】
図6bに示す方法は、大規模な画像検索のためのパイプラインとして実施することができる。第1に、局所特徴点(記述子とも呼ばれる)は、クエリ画像から抽出される。クエリ画像とデータベース画像との間の類似性を評価するために、局所特徴点の組が使用される。個々の特徴点は、モバイルアプリケーションに有用であるように、ユーザがクエリ写真を対応するデータベース画像と比較して異なる視点から、および異なる照明により撮る際に遭遇する幾何学的ひずみおよび測光ひずみに対してロバストであるべきである。次に、クエリ特徴点が、データベースに記憶された画像の特徴点にマッチングされる。これは、特別なインデックス構造を使用することによって達成され、マッチングする特徴点を含む画像のリストへの高速アクセスを可能にすることができる。画像がクエリ画像との共通点を有する特徴点の数に基づいて、同様である可能性がある画像のショートリストが、データベースから選択される。最後に、幾何学的検証ステップは、データベースにおいて最も類似するマッチング要素に適用される。幾何学的検証は、マッチングが正しいことを保証するために、クエリ画像の特徴点と、候補となるデータベース画像の特徴点との間にコヒーレントな空間パターンを見つける。
【００９９】
図6cは、本開示の実施形態による、画像の特徴点位置情報を符号化する方法を示す。図6cに示すように、ブロック632では、本方法は、複数の六角形セルを含む六角格子を生成し、特徴点位置情報の所定の量子化レベル(1特徴点当たり4ビット、5ビット、または6ビットなど)に基づいて、六角形セルのサイズを決定する。
【０１００】
ブロック634では、本方法は、六角格子を使用して画像の特徴点位置を量子化する。各特徴点位置に関して、本方法は、特徴点位置の2次元平面から3次元空間に変換された座標を生成し、変換された座標を対応する最も近い整数に四捨五入し、変換された座標が3次元空間における六角形平面に属することを検証する。変換された座標の合計を計算することにより、変換された座標の検証が行われ、変換された座標の合計が0に等しいことを検証する。
【０１０１】
ブロック636では、本方法は、各六角形セル内の特徴点位置の出現を記録するためにヒストグラムを生成する。このヒストグラムは、各六角形セル内の特徴点位置の出現を含むように構成されたヒストグラムマップと、各六角形セル内の特徴点位置の出現の数を記述するように構成されたヒストグラム計数とを含む。
【０１０２】
ブロック638では、本方法は、各六角形セル内の特徴点位置の出現に従ってヒストグラムを符号化する。本方法は、ヒストグラムを一意の辞書式インデックスに変換し、固定長符号を使用して一意の辞書式インデックスを符号化する。加えて、本方法は、ヒストグラムの空のブロックをラスタ走査順にランレングスに変換し、エントロピーコーダを使用してランレングスを符号化する。エントロピーコーダは、ゴロムライス符号、ハフマン符号、または算術符号を使用することができる。
【０１０３】
別の手法では、ヒストグラムを符号化するのに、ヒストグラム内の符号化すべき後続の六角形セルの情報を符号化するために、隣接する六角形セルのコンテキスト情報を適用することができる。本コンテキスト情報は、符号化すべき後続の六角形セルの1次隣接部および2次隣接部からのコンテキスト情報を含む。コンテキスト情報は、算術エンコーダの入力として使用される。
【０１０４】
本開示の実施形態によれば、ゴロムライス符号化は、データ圧縮符号の群を使用した可逆データ圧縮方法であり、幾何学的分布に従うアルファベットは、適応符号化方式においてプレフィックス符号としてゴロムライス符号を有することができる。ゴロムライス符号は、2の累乗の調整可能なパラメータを有しており、このことにより、バイナリ算術において2による乗算および除算をより効率的に実施することができるので、ゴロムライス符号をコンピュータで使用するのに都合よくなる。ハフマン符号化は、可逆データ圧縮用にソースシンボルを符号化するための可変長符号テーブルを使用する。可変長符号テーブルは、ソースシンボルの考えられる各値の推定される出現確率に基づいて導出することができる。ハフマン符号化は、各シンボルに関する表現を選択するための特定の方法を使用し、より共通性が小さいソースシンボルに使用されるビット列よりも短いビット列を使用して最も共通性が大きいソースシンボルを表すプレフィックス符号をもたらす。均一な確率分布、および2の累乗のいくつかの元を有するシンボルの組に関して、ハフマン符号化は、バイナリブロック符号化に等しい。算術符号化は、可逆データ圧縮に使用される可変長エントロピー符号化の形態である。文字列は、ASCIIコードの場合のように、1文字当たり固定数のビットを使用して表すことができる。列が算術符号に変換される際、頻繁に使用される文字は、より少ないビットで記憶することができ、あまり頻繁に出現しない文字は、より多いビットで記憶することができ、合計で使用されるビットはより少なくなる。算術符号化は、入力を成分のシンボルに分離するのではなく、各々を符号に置き換えるという点で、ハフマン符号化などのエントロピー符号化の他の形態と異なり、算術符号化は、全メッセージを単一の数、すなわち少数n(0.0≦n<1.0)に符号化する。
【０１０５】
図7aおよび図7bは、本開示の実施形態によるビジュアル探索機能の例示的な実装形態を示す。本開示で説明する特徴点位置情報を符号化する方法は、図7aおよび図7bに示すクライアント/サーバ環境で実施することができる。
【０１０６】
図7aに示すように、本システムは、モバイルデバイス702(たとえば、モバイル電話)、ビジュアル探索サーバ704、およびワイヤレスネットワーク706を含む。モバイルデバイス702は、画像キャプチャモジュール703、画像符号化モジュール705、および処理/表示結果モジュール707を含む。ビジュアル探索サーバ704は、復号モジュール711、記述子抽出モジュール713、記述子マッチングモジュール715、探索結果モジュール717、およびデータベース719を含む。モバイルデバイス702、ワイヤレスネットワーク706、およびビジュアル探索サーバ704の構成要素は、図7aの流れ図に示すように通信可能に結合する。モバイルデバイス702は、クエリ画像を分析し、局所的画像特徴点(記述子)を抽出し、特徴点データを送信する。検索方法は、探索を実行するためのクエリとして送信される特徴点を使用してビジュアル探索サーバ704上で実行される。
【０１０７】
図7bに示す例では、本システムは、モバイルデバイス722(モバイル電話として示される)、ビジュアル探索サーバ724、およびワイヤレスネットワーク726を含む。モバイルデバイス722は、画像キャプチャモジュール723、記述子抽出モジュール725、記述子符号化モジュール727、記述子マッチングモジュール729、判断分岐731、処理/表示結果モジュール733、およびローカルデータベース(D/B)またはキャッシュ735を含む。ビジュアル探索サーバ724は、記述子復号モジュール741、記述子マッチングモジュール743、探索結果モジュール745、およびデータベース747を含む。モバイルデバイス722、ワイヤレスネットワーク726、およびビジュアル探索サーバ724の構成要素は、図7bの流れ図に示すように通信可能に結合する。モバイルデバイス722は、データベースのキャッシュを維持し、画像マッチングを局所的に実行する。一致点が見つからない場合、モバイルデバイス722は、ビジュアル探索サーバ724にクエリ要求を送信する。このようにして、モバイルデバイス722は、ネットワークを介して送信されるデータ量をさらに低減させる。
【０１０８】
図7aおよび図7bの各場合において、検索フレームワークは、厳しいモバイルシステム要件に適応することができる。モバイルデバイス上の処理は、高速で、電力消費量の点で経済的である必要がある。ネットワークを介して送信されるデータのサイズは、ネットワーク待ち時間を最小化し、したがって最高のユーザエクスペリエンスを提供するために、できる限り小さくする必要がある。検索に使用される方法は、極めて大きい可能性があるデータベースに拡張可能であり、少ない待ち時間で正確な結果をもたらすことができる必要がある。さらに、本検索システムは、様々な距離、視野角、および照明条件を含む広範囲の条件のもとで、または部分的な閉塞または運動のぼかしの存在下でキャプチャされるオブジェクトの確実な認識を可能にするためにロバストである必要がある。
【０１０９】
特徴点抽出処理は、画像内の顕著な関心点を特定する。ロバストな画像マッチングに関して、そのような関心点は、見方の変換(スケール変化、回転、および並進など)および照明変化のもとで反復可能である必要がある。スケール不変性を達成するために、関心点は、画像ピラミッドを使用して複数のスケールで計算することができる。回転不変性を達成するために、各関心点の周りのパッチは、支配的な勾配の方向に向けられる。さらに、各パッチの勾配は、照明変化に対して勾配をロバストにするために正規化される。
【０１１０】
様々な関心点検出器は、再現性および計算量において様々なトレードオフをもたらすことに留意されたい。たとえば、SIFTによって生成されるガウス差分(DoG)点は、計算するには遅いが、高い再現性がある可能性がある一方で、コーナー検出器手法は、速いが、より低い再現性をもたらす。再現性と計算量との間のうまいトレードオフを達成することができる様々な手法のうちで、Hessian-blob検出器は、積分画像により高速化される。VGA画像に対してこの手法を使用すると、関心点検出は、一部の現在のモバイル電話では約1秒未満で実行することができる。
【０１１１】
関心点検出の後、「ビジュアルワード」記述子は、そのような点の周りの小さい画像パッチを使用して計算される。特徴点記述子を計算する際の1つの課題は、画像または画像の小さい組の特徴の高い識別性を特徴点記述子に与えることである。ほとんどすべての画像で発生する記述子(たとえば、テキスト文書におけるワード「and」に相当)は、検索には有用でないであろう。
【０１１２】
一実装形態では、記述子を計算する処理は、次のように記述される。
・パッチは、空間的に局在化するいくつか(たとえば5〜9)のビンに分割される。
・次いで、空間的な各ビンにおけるジョイント(dx,dy)勾配ヒストグラムが計算される。CHoGヒストグラムビニングは、キーポイントの周りで抽出されたパッチに関して観測される勾配統計量における典型的なスキューを利用する。
・各空間的ビンからの勾配のヒストグラムは、記述子の一部として量子化され、記憶される。
【０１１３】
画像の特徴点を抽出するための上記の実施形態では、様々なスケールにおける関心点(たとえば、コーナー、ブロブ)が抽出される。様々なスケールにおけるパッチは、最も支配的な勾配に沿って向けられる。記述子は、カノニカルに向けられ正規化されたパッチを使用して計算される。パッチは、局在化する空間的ビンに分割され、関心点の局在化誤差にロバスト性を与える。各空間的ビンにおける勾配の分布は、パッチのコンパクトな記述を得るために直接圧縮される。
【０１１４】
ヒストグラムの使用により、画像特徴点間のミスマッチの程度を評価するために、KL発散などの情報距離測度を使用することが可能になる。また、ヒストグラムにより、単純で効果的な符号化が可能になる。いくつかの例では、各パッチを圧縮されたヒストグラムベースの記述子に変換するのに、50ビット〜60ビットしか必要としない。
【０１１５】
局所的画像特徴点を送信または記憶するモバイルARシステムおよびビジュアル探索システムは、特徴点および特徴点位置情報の組を効率的に符号化する(および/または多重化する)必要がある。また、特徴点位置情報は、幾何学的検証に必要とされるとき、符号化する必要がある。マッチング精度に関して、1つの手法では、通常、少なくとも500個の局所的特定が必要である。そのような特徴点は、通常、空間的に高く相関する。上記の図2〜図4に示すように、特徴点位置情報の符号化は、第1にその情報を2Dヒストグラムに量子化し、次いで、空間的相関を利用するためにコンテキストベースの算術符号化技法を使用することにより達成することができる。この技法は、約5ビット/特徴点符号化レートを達成し、特徴点位置情報の十分高い精度の表現をもたらすことができる。
【０１１６】
第1に特徴点位置ヒストグラムを送信し、次いで、その位置がヒストグラムを復号する際に現れる順序で特徴点を送信することにより、局所的特徴点およびその対応する位置の組全体の符号化を達成することができる。たとえば、ブロック(x,y)が3つの特徴点を含むことをヒストグラムが示す場合、エンコーダは、3つの対応する記述子の符号をビットストリームで連続的に出力することができる。
【０１１７】
上述の記述子などのコンパクトな記述子および特徴点位置符号化を使用すると、500個の特徴点を有するクエリ画像は、約4Kバイト(500×(60+5)/8)によって表すことができる。JPEG圧縮されたクエリ画像が通常、約40〜80Kバイトを費やすことを考えると、開示する手法は、ビットレートにおいて1桁の低減を表す。
【０１１８】
画像の大型データベース内の画像の特徴点を割り出し、マッチングするために、開示する実施形態は、クエリ画像とマッチする可能性が高いデータベース候補値のショートリストを戻すデータ構造を使用する。ショートリストは、正しいマッチングが含まれる限り、誤判定を含む可能性がある。その後、データベース全体ではなく、候補値のショートリストのみに関して、より遅い対比較を実行することができる。
【０１１９】
画像データベース内の局所的特徴点を割り出すために、様々なデータ構造を使用することができる。1つの手法は、best-bin-firstストラテジを含むSIFT記述子の近似最近傍(ANN)探索を使用することである。加えて、Bag of Features(BoF)モデルを使用することができる。BoFコードブックは、記述子の訓練セットのk-meansクラスタリングによって構築される。クエリ中、BoFコードブックに関連する逆ファイルインデックスを使用することにより、データベース画像のスコアリングを実行することができる。大きいコードブックを生成するために、語彙ツリー(VT)を生成するのに階層型のk-meansクラスタリングを利用することができる。局所性鋭敏型ハッシュ(LSH)などの他の探索技法および従来のツリーベースの手法の改善型も使用することができる。
【０１２０】
図8aは、本開示の実施形態による、訓練特徴点記述子の階層型のk-meansクラスタリングによって語彙ツリーを構築する方法を示す。この例に示す語彙ツリーは、2つのレベルを有する。分岐因子(branching factor)k=3を使用すると、語彙ツリーは、k^2=9のリーフノードを有する。図8bは、本開示の実施形態による、語彙ツリーおよび関連する転置インデックスを示す。転置インデックスは、ファイル内の特徴点の数が語彙ツリーにおいて同じパスをたどることを示す、画像およびカウンタのリストを含む。
【０１２１】
図8aおよび図8bに示すように、画像特徴点を割り出し、マッチングする際に、語彙ツリー(VT)およびその関連する転置インデックス構造が使用される。図8aに示すように、データベースを代表する訓練特徴点記述子の組に関して階層型のk-meansクラスタリングを実行することにより、データベース用のVTを構築することができる。最初に、すべての訓練記述子に関して、k個の大きいクラスタが生成される。これは、L2ノルムまたは対称的な形態のKL発散などの近似距離関数を用いて、k平均アルゴリズムを使用する(k個のセルに量子化)することによって行われる。次いで、大きい各クラスタに関して、k個のより小さいクラスタを生成するために、そのクラスタに割り当てられた訓練記述子に、k平均クラスタリングが適用される。記述子空間のこの再帰的分割は、良好な分類パフォーマンスを確実にするのに十分なビンが現れるまで繰り返される。たとえば、実際には、高さ6、分岐因子k=10を有するVT構造を使用し、100万(106)ノードを生成することができる。
【０１２２】
VTに関連する転置インデックスは、図8bに示すように、1リーフノード当たり2つのリストを維持する。リーフノードxに関して、どのNxデータベース画像がこのノードに関連するクラスタに属する特徴点を有するかを示す画像識別子のソートされた列{ix1,...,ixNx}が存在する。同様に、各対応する画像内の特徴点の数が同じクラスタ内にあることを示すカウンタの対応する列{Cx1,...,CxNx}が存在する。
【０１２３】
クエリ中、VTは、クエリ画像内の各特徴点に関して通過され、毎回リーフノードのうちの1つにおいて終了する。その後、これらの画像とクエリ画像との間の類似性スコアを計算するために、画像および頻度計数の対応するリストが使用される。そのようなスコアの計算のために、標準的なTerm Frequency-Inverse Document Frequency(TF-IDF)重み付け方式を使用することができる。これらのすべてのリストから画像を引き出し、スコアによりこれらの画像をランク付けすることにより、クエリ画像への真の一致を含む可能性が高いデータベース画像の部分集合を導出することができる。各クエリ特徴点につき、少数のルックアップのみを実行する必要があり、すべての関連するファイルリストは、転置インデックスから直接利用できるので、この方式は、大型のデータベースをサポートするために拡張することができる。
【０１２４】
特徴点マッチングの後、幾何学的検証が実行される。この段階では、クエリ画像およびデータベース画像の特徴点の位置情報は、特徴点の一致が2つの画像間の視点の変化に矛盾しないことを確認するのに使用される。クエリ画像とデータベース画像との間の幾何学的変換は、回帰技法を使用して推定される。この変換は、通常、3D幾何学モデル、ホモグラフィモデル、またはアフィンモデルを含む基本行列によって表される。
【０１２５】
段落0126、図2、図6a〜図6c、およびその対応する記述子は、複数の六角形セルを含む六角格子を生成するための手段と、六角格子を使用して画像の特徴点位置を量子化するための手段と、各六角形セル内の特徴点位置の出現を記録するためにヒストグラムを生成するための手段と、各六角形セル内の特徴点位置の出現に従ってヒストグラムを符号化するための手段とを提供することに留意されたい。段落0126、図2、図3a、図3b、図6a〜図6c、およびその対応する記述子は、特徴点位置の2次元平面から3次元空間に変換された座標を生成するための手段と、変換された座標を対応する最も近い整数に四捨五入するための手段と、変換された座標が3次元空間における六角形平面に属することを検証するための手段とを提供する。段落0126、図2、図6a〜図6c、およびその対応する記述子は、各六角形セル内の特徴点位置の出現を含むように構成されたヒストグラムマップを生成するための手段と、各六角形セル内の特徴点位置の出現の数を記述するように構成されたヒストグラム計数を生成するための手段とを提供する。段落0126、図4a、図4b、図6a〜図6c、およびその対応する記述子は、ヒストグラム内の符号化すべき後続の六角形セルの情報を符号化するために、隣接する六角形セルのコンテキスト情報を適用するための手段を提供する。
【０１２６】
本明細書で説明される方法およびモバイルデバイスは、用途に応じて様々な手段によって実施することができる。たとえば、これらの方法は、ハードウェア、ファームウェア、ソフトウェア、またはそれらの組合せで実施され得る。ハードウェア実装形態の場合、処理ユニットは、本明細書で説明される機能を実行するように設計された、1つもしくは複数の特定用途向け集積回路(ASIC)、デジタルシグナルプロセッサ(DSP)、デジタルシグナルプロセシングデバイス(DSPD)、プログラマブル論理デバイス(PLD)、フィールドプログラマブルゲートアレイ(FPGA)、プロセッサ、コントローラ、マイクロコントローラ、マイクロプロセッサ、電子デバイス、他の電子ユニット、またはそれらの組合せ内で実装され得る。本明細書では、「制御論理回路」という用語は、ソフトウェア、ハードウェア、ファームウェア、またはそれらの組合せによって実装された論理回路を包含する。
【０１２７】
ファームウェアおよび/またはソフトウェア実装形態の場合、これらの方法は、本明細書で説明される機能を実行するモジュール(たとえば、プロシージャ、関数など)によって実施され得る。命令を有形に具現化するいずれの機械可読媒体も、本明細書で説明される方法の実施において使用され得る。たとえば、ソフトウェアコードは、メモリに記憶され、処理ユニットによって実行され得る。メモリは、処理ユニット内に実装され、または処理ユニットの外部に実装される可能性がある。本明細書で用いられる「メモリ」という用語は、長期、短期、揮発性、不揮発性、または他の記憶デバイスのいずれかの種類を指し、特定のメモリの種類またはメモリの数には限定されず、あるいはメモリが格納される媒体の種類に関して限定されない。
【０１２８】
ファームウェアおよび/またはソフトウェアに実装する場合、機能は、コンピュータ可読媒体に1つまたは複数の命令またはコードとして記憶され得る。これらの例には、データ構造によって符号化されたコンピュータ可読媒体およびコンピュータプログラムによって符号化されたコンピュータ可読媒体が含まれる。コンピュータ可読媒体は製造物品の形態をとり得る。コンピュータ可読媒体は、物理的なコンピュータ記憶媒体を含む。記憶媒体は、コンピュータによってアクセスされ得る任意の使用可能な媒体である可能性がある。限定ではなく、例として、そのようなコンピュータ可読媒体は、RAM、ROM、EEPROM、CD-ROM、または他の光ディスクストレージ、磁気ディスクストレージまたは他の磁気記憶デバイス、あるいは所望のプログラムコードを命令またはデータ構造の形で記憶するのに使用することができ、かつコンピュータからアクセスすることのできる任意の他の媒体を備えてよく、本明細書で使用するディスク(diskおよびdisc)には、コンパクトディスク(disc)(CD)、レーザディスク(disc)、光ディスク(disc)、デジタル多用途ディスク(disc)(DVD)、フロッピー(登録商標)ディスク(disk)、およびブルーレイディスク(disc)が含まれ、ディスク(disk)は通常、データを磁気的に再生し、一方、ディスク(disc)はデータをレーザによって光学的に再生する。上記の組合せも、コンピュータ可読媒体の範囲内に含めるべきである。
【０１２９】
命令および/またはデータは、コンピュータ可読媒体に記憶されるのに加えて、通信装置に含まれる伝送媒体上の信号として提供され得る。たとえば、通信装置は、命令およびデータを示す信号を有する送受信機を含み得る。命令およびデータは、1つまたは複数のプロセッサに特許請求の範囲において概説する機能を実施させるように構成される。すなわち、通信装置は、開示する機能を実行するための情報を示す信号を有する伝送媒体を含む。第1の時間において、通信装置中に含まれる伝送媒体は、開示する機能を実行するための情報の第1の部分を含んでもよく、一方、第2の時間において、通信装置中に含まれる伝送媒体は、開示する機能を実行するための情報の第2の部分を含む可能性がある。
【０１３０】
本開示は、ワイヤレスワイドエリアネットワーク(WWAN)、ワイヤレスローカルエリアネットワーク(WLAN)、ワイヤレスパーソナルエリアネットワーク(WPAN)などのような、様々なワイヤレス通信ネットワークとともに実装され得る。「ネットワーク」および「システム」という用語は、しばしば互換的に使用される。「位置」および「ロケーション」という用語は、しばしば互換的に使用される。WWANは、符号分割多元接続(CDMA)ネットワーク、時分割多元接続(TDMA)ネットワーク、周波数分割多元接続(FDMA)ネットワーク、直交周波数分割多元接続(OFDMA)ネットワーク、シングルキャリア周波数分割多元接続(SC-FDMA)ネットワーク、Long Term Evolution(LTE)ネットワーク、WiMAX(IEEE802.16)ネットワークなどであり得る。CDMAネットワークは、cdma2000、広帯域CDMA(W-CDMA)などの1つまたは複数の無線アクセス技術(RAT)を実装することができる。cdma2000は、IS-95標準、IS-2000標準、およびIS-856標準を含む。TDMAネットワークは、Global System for Mobile Communications(GSM(登録商標))、Digital Advanced Mobile Phone System(D-AMPS)、または何らかの他のRATを実装することができる。GSM(登録商標)およびW-CDMAは、「第3世代パートナーシッププロジェクト」(3GPP)という名称の組織からの文書で説明される。cdma2000は、「3rd Generation Partnership Project2」(3GPP2)という名称のコンソーシアムの文書に記載されている。3GPPおよび3GPP2の文書は、公に利用可能である。WLANは、IEEE 802.11xネットワークでもよく、WPANはBluetooth(登録商標)ネットワーク、IEEE 802.15x、または何らかの他のタイプのネットワークである可能性がある。本技法はまた、WWAN、WLAN、および/またはWPANの任意の組合せとともに実装され得る。
【０１３１】
移動局は、セルラー通信デバイスまたは他のワイヤレス通信デバイス、パーソナル通信システム(PCS)デバイス、パーソナルナビゲーションデバイス(PND)、個人情報マネージャ(PIM)、携帯情報端末(PDA)、ラップトップ、あるいはワイヤレス通信および/またはナビゲーション信号を受信することができる他の適切なモバイルデバイスなどのデバイスを指す。「移動局」という用語はまた、短距離ワイヤレス接続、赤外線接続、ワイヤライン接続、または他の接続などによって、パーソナルナビゲーションデバイス(PND)と通信するデバイスを、衛星信号受信、支援データ受信、および/または位置関連処理がそのデバイスにおいて行われるか、またはPNDにおいて行われるかにかかわらず含むものである。また、「移動局」は、インターネット、Wi-Fi、または他のネットワークなどを介してサーバとの通信が可能である、ワイヤレス通信デバイス、コンピュータ、ラップトップなどを含むすべてのデバイスを、衛星信号受信、支援データ受信、および/または位置関連処理がそのデバイスにおいて行われるか、サーバにおいて行われるか、またはネットワークに関連する別のデバイスにおいて行われるかにかかわらず含むものである。上記の任意の動作可能な組合せも「移動局」と見なされる。
【０１３２】
何かが「最適化される」、「必要とされる」という指定または他の指定は、最適化されるシステム、または「必要とされる」要素が存在するシステムのみに本開示が適用されること(または他の指定に起因する他の制限)を示すものではない。これらの指定は、特定の説明された実装形態のみを指す。もちろん、多くの実装形態が可能である。開発中であるか今後開発されるプロトコルを含む、本明細書で論じるプロトコル以外のプロトコルで技法を使用できる。
【０１３３】
当業者は、同じ基本的な下位の機構および方法を依然用いながら、開示した実施形態の多くの可能な修正および組合せを使用してよいことを認識されよう。上記の説明は、説明の目的で、特定の実施形態に関して書かれている。しかしながら、上で示した論述は網羅的なものでも、あるいは本開示を開示された厳密な形態に限定するものでもない。多くの修正および変形が、上記の教示に鑑みて可能である。本開示の原理および実際の適用について説明するために、また、企図される特定の用途に合わせて様々な修正を加えて本開示および様々な実施形態を他の当業者が最善の形で利用できるように、実施形態が選択され、説明されている。
【符号の説明】
【０１３４】
304  六角形平面
305  六角形平面の頂点
306  六角形平面の頂点
307  六角形平面の頂点
308  六角形平面の頂点
309  六角形平面の頂点
310  六角形平面の頂点
312  六角形平面の中心
314a  六方格子上の点
314b  六方格子上の点
【図１ａ】
0005911578.tif 000025
【図１ｂ】
0005911578.tif 000026
【図２】
0005911578.tif 000027
【図３ａ】
0005911578.tif 000028
【図３ｂ】
0005911578.tif 000029
【図４ａ】
0005911578.tif 000030
【図４ｂ】
0005911578.tif 000031
【図５】
0005911578.tif 000032
【図６ａ】
0005911578.tif 000033
【図６ｂ】
0005911578.tif 000034
【図６ｃ】
0005911578.tif 000035
【図７ａ】
0005911578.tif 000036
【図７ｂ】
0005911578.tif 000037
【図８ａ】
0005911578.tif 000038
【図８ｂ】
0005911578.tif 000039