物体認識用のヒストグラム方法及びシステム
多次元ヒストグラムが、画像（又は物体）を特徴付けるために使用され、一以上の参照画像（又は物体）とのマッチングする候補を特定するために使用される。例示的な実装形態は、二つの次元には色相情報、第３の次元には輝度に基づく２次導関数を使用する。説明する構成の単純性及び速度のために、これらの構成は、例えば視覚探索用途において画像／物体認識用の技術を使用することができる、携帯電話及び他の携帯デバイスでの使用に十分に適している。
【発明の詳細な説明】
【関連出願データ】
【０００１】
本技術は、本件の譲受人による他の特許出願において開示した技術を基礎とし、それを拡張するものである。したがって、出願人が本技術を適用しようと意図しており、当業者が精通してものと想定する詳細な構成を与える以下の出願に、読者を向ける。
２００８年１０月３１日に出願した米国特許出願第６１／１１０，４９０号
２００８年１１月１４日に出願した米国特許出願第１２／２７１，６９２号（米国特許出願公開第２０１０００４６８４２号として公開された）
２００８年１１月１４日に出願した米国特許出願第１２／２７１，７７２号（米国特許出願公開第２０１００１１９２０８号として公開された）
２００９年２月５日に出願した米国特許出願第６１／１５０，２３５号
２００９年３月３日に出願した米国特許出願第６１／１５７，１５３号
２００９年４月８日に出願した米国特許出願第６１／１６７，８２８号
２００９年４月１４日に出願した米国特許出願第６１／１６９，２６６号
２００９年５月８日に出願した米国特許出願第６１／１７６，７３９号
これらの文献の開示を、参照することにより本明細書に援用する。
【技術分野】
【０００２】
本技術は、画像及びビデオ処理に関するものであり、より詳細には、色ヒストグラムのような簡単な特徴によって画像を表現することに関するものである。
【背景及び概要】
【０００３】
一側面では、本明細書は、画像（又はビデオ）をデータベース内に記憶された多くのものの一つとして認識する技術に関する。本技術は、画像内の物体を認識するために使用することもできる。
【０００４】
これらの技術の多くの背後の基本概念は、幾何学的変換、視点の変化、ノイズ、オクルージョン、バックグラウンド、輝度変化、及び照明の変化に対して不変であるか、又はこれらの影響に伴って緩やかに変化する簡単な特徴によって、画像（又は物体）を表現することである。そのような表現の一つが、３Ｄ色ヒストグラム（Ｓｗａｉｎ及びＢａｌｌａｒｄ、「Ｃｏｌｏｒ Ｉｎｄｅｘｉｎｇ」、Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ、７（１）、１１〜３２頁、１９９１年を参照）である。
【０００５】
色ヒストグラムは、比較的高速で計算することができ、認識及び索引（インデックス）付けタスクに広く使用されている。しかし、従来の色ヒストグラムは、明度、コントラスト及び輝度の変化、並びに照度変化に対する感度の高さといった様々な欠点を有する。
【０００６】
本技術の種々の側面は、そのような影響に対して感度がより低い簡単な表現を生成する色ヒストグラムの概念の拡張に関している。また、ストグラムパラメータ及び集合理論に基づき、幾何学的変換の下でより良好なロバスト性をもたらす簡単なマッチング技術を開示する。高速データベース探索及び探索空間の縮小のためにヒストグラム表現を使用する技術も説明する。
【０００７】
説明する技術は、それらの単純性及び速度に主として起因して、携帯デバイス又はエンベデッドシステム上での演算に良く適している。
【０００８】
上記説明は、添付の図面を参照して進める以下の詳細な説明から、より容易に明らかとなる。
【図面の簡単な説明】
【０００９】
【図１Ａ】第１の参照画像を示す図である。
【図１Ｂ】輝度に８個のビン（ｂｉｎ）、赤−緑及び青−黄の反対色方向にそれぞれ１６個のビン（即ち、２０４８データ要素）を用いた、図１Ａの画像の３Ｄヒストグラムを示す図であり、球体は、非ゼロヒストグラムのビンの個数を示し、球体のサイズは、各ビンのピクセルの数を示す。
【図２Ａ】図１Ａに類似しているが、第２の参照画像を示す図である。
【図２Ｂ】図１Ｂに類似しているが、第２の参照画像を示す図である。
【図３】三つのレベルに閾値処理した後の、図１Ａの輝度の２次微分値を示す図である。
【図４Ａ】図１Ｂに類似しているが、輝度軸の代わりに、２次微分のような関数が三つのレベルのみに量子化され、成分色軸を不均一に量子化した図である。
【図４Ｂ】図２Ｂに類似しているが、輝度軸の代わりに、２次微分のような関数が三つのレベルのみに量子化され、成分色軸を不均一に量子化した図である。
【図５Ａ】照度変化が色の変化をどのように引き起こす可能性があるかを示す、図１Ａの参照画像である。
【図５Ｂ】照度変化が色の変化をどのように引き起こす可能性があるかを示す、図１Ａの参照画像である。
【図６】ヒストグラム、又は他の分析用のズームアウト画像の候補部分の区分けを示す流れ図である。
【図７】選択した幾何学的変換及び他の変形についての、参照画像とテスト画像との間の整合性を示す表である。
【図８】本技術との使用に適した携帯電話のブロック図である。
【発明を実施するための形態】
【００１０】
＜３Ｄ色ヒストグラム＞
【００１１】
Ｓｗａｉｎ及びＢａｌｌａｒｄ（上記参照）は、認識タスク用に色物体を表現するために、色ヒストグラムの使用を導入している。彼らは、色ヒストグラムがオクルージョン及び視野の変化が存在しても安定した表現をもたらし、多数の物体を区別することができることを示している。彼らは、マッチング用にテストヒストグラムと参照ヒストグラムとを比較するヒストグラム共通度（インタセクション）と呼ばれる評価尺度を導入している。
【００１２】
色ヒストグラムは、ある色が画像内に現れる回数を計数したものである。色は、ＲＧＢ、ＨＳＶ、又は輝度と反対色との組合せといった別個の色空間表現において特定することができる。図１Ａ及び１Ｂは、画像と、輝度（Ｌ）、赤−緑（ＲＧ）、及び青−黄（ＢＹ）により表現される色軸を有する画像の３Ｄ色ヒストグラムとを示している。輝度は、８個のビン（ｂｉｎ）で定量化され、他の色軸はそれぞれ、１６個のビンで定量化されている（即ち、３Ｄヒストグラムでは２０４８データ要素）。Ｌ、Ｒ−Ｇ、及びＢ−Ｙ色値は、以下のようにＲＧＢ値から得られる。
Ｌ＝０．３３３＊（Ｒ＋Ｇ＋Ｂ）
ＲＧ＝０．５＊（Ｒ−Ｇ）
ＢＹ＝０．５＊Ｂ−０．２５＊（Ｒ＋Ｇ）
【００１３】
図２Ａ及び２Ｂは、別の画像と当該別の画像に対応する色ヒストグラムとを示している。図１及び図２のヒストグラムを比較すると、ヒストグラムは、各画像を区別する色特徴を表わしていることが示唆されている。
【００１４】
＜ヒストグラムを使用した物体認識、類似性、及びマッチング＞
【００１５】
３Ｄヒストグラム（又は色ヒストグラム）は、画像内の各タイプの色成分の量又は比率を測定するものである。３Ｄヒストグラムは、画像の色に関して画像の特性化を可能とする。例えば、三つのヒストグラム軸として赤、緑、及び青の成分を含む３Ｄヒストグラムを考える。この場合に、緑のバックグラウンドに対する赤い花を含む簡単な画像は、赤軸及び緑軸に沿って支配的な色成分を有することとなる。また、ピクセルの２５％が赤で、残りのピクセルが緑であることを想定する。この場合に、ヒストグラムが赤及び緑の成分のみを有する画像全体は、花の画像に「類似する」ものとみなすことができる。ヒストグラムが、花の画像と略同じ比率（１：３）で赤及び緑のみを有する画像は、花の画像によりマッチングするものとみなすことができる。わずかに異なる姿勢を通して得られる緑のバックグラウンドに対する花の画像を認識することもできる。
【００１６】
＜ヒストグラム共通度＞
【００１７】
ヒストグラム共通度（ヒストグラムインタセクション）は、二つのヒストグラム間の類似性の評価尺度を与えるものである。Ｎ個のビンを含むヒストグラムに関するヒストグラム共通度評価尺度は、双方のヒストグラムに共通するカウント値の合計により与えられる。Ｓｗａｉｎ及びＢａｌｌａｒｄは、ヒストグラム共通度を以下のように定義している。
【数１】
ここで、ｈ（ｔ，ｒ）は、テスト画像ｔと参照画像ｒとの間のヒストグラム共通度である。基本的に、ヒストグラム共通度の評価値は、テストヒストグラム及び参照ヒストグラムに共通するピクセル数のカウント値を与える。ｈ（ｔ，ｒ）が高い値であることは、テストヒストグラムが参照ヒストグラムにマッチングすることを示す。
【００１８】
Ｓｗａｉｎ及びＢａｌｌａｒｄは、以下のように、正規化ヒストグラム共通度評価尺度も定義している。
【数２】
【００１９】
正規化ヒストグラム共通度評価尺度Ｈ（ｔ，ｒ）は、テスト画像が参照画像と同一であるときに、１．０となる。異種の画像では、正規化ヒストグラム共通度評価尺度は、ゼロにより近づく。
【００２０】
ヒストグラム共通度評価尺度は、二つの組の間、即ちテスト画像のヒストグラムを表現する一方の組と、参照画像のヒストグラムを表現する他方の組との間の共通度と解釈することができる。
【００２１】
＜基本的なヒストグラム手法の拡張＞
【００２２】
色ヒストグラムは、平行移動、及び画像に垂直な軸線の周りの回転に対して不変である。（画像が側方に変位するか、又は回転するとき、色及び色の比率は、変化しない。）色ヒストグラムは、オクルージョン及びバックグラウンドコンフュージョン（ｂａｃｋｇｒｏｕｎｄ ｃｏｎｆｕｓｉｏｎ）に伴って緩やかに変化する傾向もある。
【００２３】
一方、色ヒストグラムは、輝度変化及び照明（照度）変化に影響されやすい傾向がある。Ｓｗａｉｎ及びＢａｌｌａｒｄの元の技術の改良に基づく種々の手法が提案されている。一つのこのような手法は、多次元受容野ヒストグラムを採用しており、当該ヒストグラムにおいては、物体がガボールフィルタといった局所近傍オペレータの結合統計量により表現される（例えば、Ｓｃｈｉｅｌｅら、「Ｒｅｃｏｇｎｉｔｉｏｎ Ｗｉｔｈｏｕｔ Ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ Ｕｓｉｎｇ Ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ Ｒｅｃｅｐｔｉｖｅ Ｆｉｅｌｄ Ｈｉｓｔｏｇｒａｍｓ」、Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ、３６（１）、３１〜５２頁、２０００年を参照）。しかしながら、これらの手法は、計算量が多いか、又はハードウェアアクセラレータの使用を必要とする。
【００２４】
以下、本明細書は、ヒストグラム概念を拡張し、さらに簡単な計算を含み、より広い範囲の照明及び輝度変化の下で使用することができる種々の新しい手法、並びに幾何学的変換を説明する。
【００２５】
＜規格化ヒストグラム＞
【００２６】
上述した正規化ヒストグラム共通度は、テスト画像又は物体のスケール及び解像度の同時変化（即ちサイズが増加するか、又は減少するか）に影響されやすい。例えば、サイズ１０００ｘ１０００ピクセルの参照画像と、各方向に１０倍にスケーリングされ、１００ｘ１００ピクセルのサイズになったテスト画像とを考える。これら二つの画像間の正規化されたヒストグラム共通度Ｈは、低くなる。
【００２７】
本技術の一側面によれば、サイズの変化を考慮するために、共通度を計算する前に、ヒストグラムが規格化される。規格化の一手法は、ヒストグラムの合計カウント値を１単位（又は割合を示すよう１００などの一定の定数）に正規化することである。
【００２８】
規格化ヒストグラムの各ビンＣｉは、元のヒストグラムの対応するビンｃｉから以下のように計算される。
【数３】
ここで、Ｎは、ヒストグラムにおけるビンの合計個数である。図１及び２に示すヒストグラムは、規格化ヒストグラムである。
【００２９】
規格化ヒストグラムに対して計算されたヒストグラム共通度は、スケール及び解像度の同時変化（即ちサイズの変化）に対して不変である。上述の例では、規格化ヒストグラムを使用して計算されたヒストグラム共通度は、１００のままである。
【００３０】
＜照明及び輝度変化に対する感度の低減＞
【００３１】
上述したヒストグラム及びヒストグラム共通度は、輝度変化に対して影響されやすい。デジタル画像の場合には明度／コントラストの変化により、物理的物体の場合には照度変化により、輝度変化がもたらされ得る。
【００３２】
本技術の別の側面によれば、輝度の変化に対処する一つの手法は、３Ｄヒストグラムの輝度軸を粗く量子化することである。例えば、図１の輝度のビンの数を８の代わりに４に低減することができる。輝度を粗く量子化することは、輝度の小さい変化がヒストグラムのビンのカウント値を大きく変化させないという利点を有する。
【００３３】
照明及び輝度変化に対する感度を低減する別の手法は、輝度平面の２次微分値を計算し、第３の次元として（二つの反対色方向に加えて）、輝度の代わりに、当該２次微分値を使用することである。
【００３４】
２次微分値は、いくつかの方法で計算又は概算することができる。いくつかの方法は、ラプラシアンガウシアンオペレータ、ガウス関数の差（ＤｏＧ）法、ラプラシアンオペレータなど（本明細書ではそれぞれ「２次導関数」と呼ぶ）の使用を含む。以下に報告する結果には、ＤｏＧ演算が使用されている。
【００３５】
（種々の実施形態では、２次微分値よりも高次の微分値、及びそのような高次の微分値の概算値を使用することができる。）
【００３６】
２次導関数自体は、輝度平面に関するダイナミックレンジの変化といった輝度変化に対してある程度の影響を受ける。本技術の別の側面によれば、そのような変化に対する感度は、２次微分値の極性（符号）のみを考慮することによって、より低減される。さらに、比較的小さい量の２次微分値は、ノイズとみなされ、正及び負の微分値とは独立に取り扱うことができる。
【００３７】
小さい量は、閾値との比較により特定することができる。この場合には、閾値自体は、輝度平面のダイナミックレンジに応じて調整される。この演算は、輝度平面の２次微分値から三つの量子化レベル、即ち、閾値を超える負の２次微分値に対応する第１のレベル、量（絶対値）が閾値以下の２次微分値に対応する第２のレベル、及び閾値よりも大きい正の２次微分値に対応する第３のレベルを、生成する。
【００３８】
一例を図３に示す。これら三つの量子化レベルは、変更された「輝度」軸のビンを表現するのに使用することができる。
【００３９】
説明した特定の例（即ち、輝度の２次微分値が第３のヒストグラムの次元として使用される）は、エッジ境界に存在する色に関して画像／物体を特徴付ける表現クラスの一つであることが理解されよう。同様の効果をもたらすのに、他の様々な関数、オペレータ、及び変換を使用することができることが当業者には理解されよう。
【００４０】
ここで説明した構成は、物体形状の一定の概念をヒストグラムに導入する。さらに、このヒストグラム手法によりもたらされる安定性及び不変性／ロバスト特性が、維持される。その結果、認識は、色に加えてエッジ情報に依存する。（従来のヒストグラム手法の典型的な欠点は、従来のヒストグラム手法が、赤白チェック柄のコップと赤白チェック柄の皿とを識別することができないことがある点にある。これは、色の構成が同一であり得るからである。一方、ここで説明した構成は、エッジに関する情報の導入により容易に識別することができる。）
【００４１】
Ｓｈｉｍ及びＣｈｏｉは、方向性エッジ情報を有する色ヒストグラム（「Ｅｄｇｅ Ｃｏｌｏｒ Ｈｉｓｔｏｇｒａｍ ｆｏｒ Ｉｍａｇｅ Ｒｅｔｒｉｅｖａｌ」、Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ、９５７〜９６０頁、Ｖｏｌ．３、２００２年６月）を提案している。しかしながら、本手法は、方向性エッジ情報に依存しない。方向性エッジ情報は、回転などの幾何学的操作により変化する。本構成は、失敗することがない。（また、Ｓｈｉｍは三つの色ヒストグラムを計算したが、ここで説明した構成は一つの３Ｄヒストグラムのみを計算する。）
【００４２】
Ｓｃｈｉｅｌｅ(先に引用した)及びＧｅｕｓｅｂｒｏｅｋら（「Ｃｏｍｐａｃｔ Ｏｂｊｅｃｔ Ｄｅｓｃｒｉｐｔｏｒｓ ｆｒｏｍ Ｌｏｃａｌ Ｃｏｌｏｕｒ Ｉｎｖａｒｉａｎｔ Ｈｉｓｔｏｇｒａｍｓ」、Ｂｒｉｔｉｓｈ Ｍａｃｈｉｎｅ Ｖｉｓｉｏｎ Ｃｏｎｆｅｒｅｎｃｅ、ｖｏｌｕｍｅ３、１０２９〜１０３８頁、２００６年）は、ヒストグラム表現のために微分値を採用している。しかしながら、上述した表現は、より簡単であり、計算がより少なく、従って、携帯電話及び他の携帯デバイスへの実装により使用しやすい。
【００４３】
輝度の２次微分値に基づく三つの量子化レベルを使用することに対する代案は、ある閾値を上回る正の値と、同じ閾値（又は別の閾値）の負の値を下回る負の値との二つを使用することである。この代案は、ヒストグラム計算から画像のより平坦な領域を効果的に破棄し、エッジ領域のみを強調する。１軸に沿ったこの両極性の２次微分値、及び他の２軸に沿った反対色の使用により、ヒストグラム比較用の計算量も低減する。（しかし、この両極性手法の欠点は、両極性手法がクロッピング及びオクルージョンによる影響をより受け得る点であり、その理由は、画像の平坦部分が無視され、エッジ情報が優位になるからである。多くのアプリケーションにおいては、これは重要ではない。）
【００４４】
他の実装形態では、両極性手法は、先に説明した３レベル手法（例えば、画像の異なる部分）と組み合わせることができる。
【００４５】
＜不均一な量子化＞
【００４６】
不飽和の色では、反対色軸に含まれる大部分の情報は、小さいダイナミックレンジを有する。例えば、赤−緑軸を考察する。赤及び緑値が、０〜２５５の間にあるとき、ＲＧ値は、−１２７．５〜＋１２７．５の間にある。不飽和領域では、大部分の値がほぼ０である。これにより不飽和画像における識別性は低下する。本技術の別の側面によれば、この識別性の低下を克服するのに、色軸の不均一な量子化が使用される。例えば、ＲＧ軸は、０付近の値が細かく量子化され、一方では端部における値が粗く量子化されるように、ビンに分割することができる。このことは、ロバスト性（例えば正確にマッチングする数）を増大させることを示している。
【００４７】
図４Ａは、上述した図１Ａの画像に関する３Ｄヒストグラムを示し、Ｚ軸は輝度成分の３レベルのガウス関数の差であり、Ｘ及びＹ軸に沿って色成分が不均一に量子化されている。図４Ｂは、同様であるが、図２Ａの画像に対応する。
【００４８】
＜照度変化の下での色の不変性＞
【００４９】
照度変化は、色の変化をもたらし得る。色に関する照度変化の影響のシミュレーションを図５Ａ及び５Ｂに示す。左に元の画像、右に変化後の画像がある。人間の視覚系は、知覚した色が同じに見えるように照度変化を補償するのが得意である。しかし、デジタル系は、許容しない。
【００５０】
本技術の別の側面によれば、照度に対する感度は、輝度変化に対する感度がより低い色成分を用いて処理することにより、低減される。例えば、色相は、入射光の増大又は減少といった照度変化の下で不変のままである傾向がある。（色相は、Ｒ、Ｇ、Ｂ色チャネルに加えられる加法変化及び乗法変化に対して不変である。）ヒストグラムの次元の一つ又は二つとして色相を使用し、別の次元として輝度の両極性又は三つのレベルの２次微分値を使用することにより、照度変化の下でのロバスト性を提供することができる。
【００５１】
本技術の別の側面によれば、照度変化の下での安定性は、各ピクセルにおける最大値と最小値との間の差により反対色方向を正規化することによって、向上される。
ＭａｘＶａｌ＝Ｍａｘ（Ｒ，Ｇ，Ｂ）（各ピクセルにおいて）
ＭｉｎＶａｌ＝Ｍｉｎ（Ｒ，Ｇ，Ｂ）（各ピクセルにおいて）
ＲＧ’＝（Ｒ−Ｇ）／（ＭａｘＶａｌ−ＭｉｎＶａｌ）
ＢＹ’＝（Ｂ−０．５＊（Ｒ＋Ｇ））／（ＭａｘＶａｌ−ＭｉｎＶａｌ）
であるものとする。
【００５２】
この計算は、色相の計算と同様のものである（Ｍａｎｊｕｎａｔｈら、「Ｃｏｌｏｒ ａｎｄ Ｔｅｘｔｕｒｅ Ｄｅｓｃｒｉｐｔｏｒｓ」、ＩＥＥＥ Ｔｒａｎｓ．ｏｎ Ｃｉｒｃｕｉｔｓ ａｎｄ Ｓｙｓｔｅｍｓ ｆｏｒ Ｖｉｄｅｏ Ｔｅｃｈｎｏｌｏｇｙ、Ｖｏｌ．１１、Ｎｏ．６、７０３〜７１５頁、２００１年６月を参照）。（ＭａｘＶａｌ−ＭｉｎＶａｌ）による正規化により、色チャネルへの加法変化及び乗法変化に対して不変の色成分が生成される。
【００５３】
このような正規化のない図５の二つの画像間のヒストグラム共通度は、３７．８３であり、正規化があれば、ヒストグラム共通度は、８１．１０に増加する。
【００５４】
さらに、照度変化の下で色不変性を達成する別の手法は、直接の色の代わりに色のコントラストの評価尺度を使用することである。更に別の代案は、色平面における遷移（空間微分）を使用することである（上で引用したＧｅｕｓｅｂｒｏｅｋを参照）。遷移を得る簡単な方法は、上述の輝度平面上の２次微分値を使用することである。
【００５５】
＜ヒストグラム評価値及び特徴＞
【００５６】
先に説明したヒストグラム共通度評価値に加えて、物体又は画像をマッチングするのにヒストグラムを比較するときに役立つ可能性がある他の評価値及び特徴が存在する。これらの評価値のいくつかは、
・テスト及び参照の占有（即ち、非ゼロ個の）ビンの数<Ｎｔ及びＮｒ>
・両ヒストグラムに共通の占有ビンの数（ビン共通度）<Ｎｉ>
・両ヒストグラムを合わせた占有ビンの数（ビン和集合）<Ｎｕ>
・両ヒストグラムに共通のピクセルの数（ヒストグラム共通度）<Ｈ（ｔ，ｒ）>
・参照ヒストグラムに占めるテストヒストグラムの占有ビンの割合（ビン類似性及び部分集合）
・ヒストグラム共通度とテストヒストグラムの占有ビンの数との比率
・テストの非ゼロビン<Ｂｔ>
・参照の非ゼロビン
・参照画像の非ゼロビンの部分集合であるテスト画像の非ゼロビン<Ｂｔｒ>
・参照画像の非ゼロビンの部分集合であるテスト画像の非ゼロビンの数<Ｎｔｒ>
・テスト画像の非ゼロビンの部分集合である参照画像の非ゼロビン<Ｂｒｔ>
・テスト画像の非ゼロビンの部分集合となる参照画像の非ゼロビンの数<Ｎｒｔ>
【００５７】
これらの評価値を結合して（例えば、比率、差、積、和をとることにより）、他の評価値を得ることができる。
【００５８】
本明細書に説明する構成を通して、ロバスト性を増大させるために、寄与がわずかであるビン（例えば１％、０．３％、０．１％、０．０３％、などよりも小さいビン計数）は、占有されないもの（即ちゼロビンのカウント値を有するもの）として取り扱うことができる。
【００５９】
＜ヒストグラムに関する集合演算＞
【００６０】
上述したように、ヒストグラム共通度は、二つのヒストグラムを比較する集合演算である。ヒストグラム共通度は、ヒストグラムのビンのコンテンツに対して演算を行うものである。本技術の別の側面によれば、共通度は、各ヒストグラム内の非ゼロビンの組に対して計算することもできる。部分集合、差集合などの他の集合演算は、物体及び画像のマッチング用にヒストグラムを比較することにおいても役立つこともわかっている。このことを以下に更に説明する。
【００６１】
ヒストグラムに関する集合演算を使用する一例は、バックグラウンドのコンテンツをフィルタで除去することである。テスト画像及び参照画像を比較するとき、バックグラウンドのコンテンツに関連する色は、参照画像内に存在しないものと仮定することができる。テスト画像の非ゼロビンの部分集合となる参照画像の非ゼロビンのみを考慮することにより、バックグラウンドをフィルタ除去することができる。（以下の図６の説明も参照。）
【００６２】
別の例は、類似していない二つの画像の場合である。この場合には、これらの画像の非ゼロビンの共通集合は小さく、相対的に差集合は大きい。
【００６３】
＜多次元ヒストグラム＞
【００６４】
上述した輝度及び反対色方向の構成は、多次元ヒストグラムを生成するのに使用することができる表現の一例にすぎない。ＹＵＶ、ＹＣｂＣｒ、ＨＳＶ、ＨＳＬ、Ｌａｂなどの他の色空間を使用することもできる。また、ヒストグラムは、追加の次元に沿ったエッジ又は他の空間統計量などの特徴を含むことにより、２より大きい次元を含むことができる（上で引用したＳｃｈｉｅｌｅを参照）。（いくつかの実施形態では、１又は２次元を使用することもできる。）
【００６５】
＜幾何学的変換の下での認識＞
【００６６】
以下のセクションは、様々なタイプの幾何学的変換の下で認識及びマッチングのために、多次元ヒストグラムに基づく画像及び物体の特徴付けをどのように使用することができるかを説明する。
【００６７】
＜平行移動＞
【００６８】
（クロッピングのない）平行移動は、例示の３Ｄヒストグラムに影響を及ぼさず、したがって、３Ｄヒストグラムは平行移動に対して不変である。規格化ヒストグラム共通度評価尺度自体は、元の画像に対して平行移動した画像をマッチングするのに適する。
【００６９】
平行移動用のテストは、ヒストグラム共通度が、マッチング閾値Ｔｍ（例えば１００％の最大値に正規化された規格化ヒストグラム共通度において７５％）よりも大きいか否かをチェックすることになる。
【００７０】
＜クロッピング＞
【００７１】
画像がクロッピングを受けると、クロッピングされた画像は、元の画像の特徴の一部を保持する。その際、クロッピングされた画像の多数（しばしば大多数）の非ゼロビンは、元の画像の非ゼロビンの部分集合となるはずである。クロッピングのチェックは、Ｎｔｒ＞Ｔｃ×Ｎｔであるか否かをテストすることとなる。ここで、Ｔｃは、許容することができるクロッピング量を特定するクロッピング閾値である。
【００７２】
クロッピングされた画像のビンの値は、元の画像の対応するビンと任意の関係を有することができる。しかし、規格化ヒストグラム共通度が設定閾値を超えるか否かをチェックすることにより、ヒストグラム共通度に基づく追加のチェックを実行することもできる。
【００７３】
＜回転＞
【００７４】
例示の３Ｄヒストグラムは、クロッピングを含まない場合に、回転による影響を受けない。ヒストグラム共通度評価尺度は、そのような場合に適している。バックグラウンドが、参照画像又はテスト画像に類似する特徴を共有する場合に、バックグラウンドコンフュージョン（即ち参照画像内に存在しないバックグラウンドのコンテンツ）は、回転の下でのヒストグラム共通度に悪影響を及ぼすことに留意されたい。テスト画像内に存在する参照画像のビンのみを考慮することにより、バックグラウンドの影響を克服することができる（例えば以下のズームアウトの説明を参照）。
【００７５】
＜スケール変化＞
【００７６】
スケール変化の場合には、画像は、元の画像と比較ではサイズにおいて拡大又は縮小される。三つの異なる場合を以下に説明する。スケール及び解像度の何れもが変化するもの（即ち、画像がスケーリングされるにつれて、画像サイズがピクセルについても変化する）、画像コンテンツ（即ち画像内の物体）がスケールアップ（即ちズームイン及びクロッピング）されるが、得られた画像サイズがピクセル数では同じままであるもの、並びに、画像コンテンツがスケールダウン（即ちズームアウト及び新しいバックグラウンドの追加）されるが、得られた画像サイズがピクセル数では同じままであるものである。
【００７７】
＜スケール及び解像度の変化（画像サイズ変化）＞
【００７８】
画像サイズを変化させるスケール変化は、画像ヒストグラム内のピクセルの数を、参照ヒストグラム内のピクセルの数と一致させなくする。先に説明したように、両ヒストグラムを規格化することにより、この不一致を補償することができる。例えば、ヒストグラムビンの合計が１００になるように、ヒストグラムのビンを正規化することができる。この規格化は、画像サイズの変化を補償する。
【００７９】
＜画像サイズを一定に維持するズームイン（拡大及びクロッピング）＞
【００８０】
この場合には、画像コンテンツが拡大される（即ち画像内の物体がより大きく見える）が、画像サイズは、元のサイズの外側の画像コンテンツをクロッピングすることにより不変に保たれる。クロッピングが含まれるので、元の画像の色の一部分が欠落する。しかし、ズーム／クロッピングされた画像内に存在する多数（しばしば大多数）の色は、元の画像内にも存在するはずである。この場合のテストは、テスト画像の大多数の非ゼロビンが、参照画像内の非ゼロビンの部分集合となるか否かをチェックすることである。また、部分集合ビンの少なくともいくつかについては、ビンのカウント値は、参照画像の対応するカウント値よりも多くなるはずである。このことにより、拡大が確認される。回帰技術を使用して、倍率（又はズーム値）（即ち、最小２乗法の意味においてテストビンのカウント値と参照ビンのカウント値との間の関係を表わる倍率がどうなるか）を求めることができる。
【００８１】
＜画像サイズを一定に維持するズームアウト（縮小及びバックグラウンド）＞
【００８２】
この場合には、元の画像のサイズが縮小され、元の画像コンテンツは、新しいバックグラウンドのコンテンツに取り囲まれる。
【００８３】
ズームアウトは、新しい（ダウンサンプリングされた）ピクセル値を得るために平均化といった演算を必要とすることがある。この演算は、参照画像内に厳密には見つけられない新しい色を導入し得る。しかしながら、比較的少数のビンに色データを量子化することにより、これら新しい中間色は、参照画像内に既に存在しているビンに含まれることになる。
【００８４】
ズームアウトにより元の画像のコンテンツに類似しない新しいバックグラウンドピクセルが導入される場合に（一般的にはこの場合となる）、新しいバックグラウンド領域は、参照画像の非ゼロビンの部分集合であるテスト画像のビンのみを考慮することにより、効果的にフィルタ除去することができる。
【００８５】
マッチングする参照画像に関して、参照画像の多数（しばしば大多数）の非ゼロビンは、テスト画像内でも非ゼロとなるはずである（クロッピング部分を考慮する余地が認められ得る）。その際、規格化ヒストグラム共通度は、これらのビン（即ち、テスト及び参照の何れにも共通するビン）のみを使用して計算することができる。この共通度値を閾値と比較することができる。倍率（又はズーム値）は、対応するビンの値と比較することにより回帰によって求めることができる。
【００８６】
更なる絞込みは、更なる分析のために、（例えばズームアウトされた）テスト画像からピクセル候補領域を特定し、それを空間的に分離することである。この絞込みは、参照画像の非ゼロビンの部分集合であるテスト画像のビンを参照して再び行うことができる。
【００８７】
図６を参照すると、元の画像（全てが赤いピクセル「Ｒ」）は、ズームアウトされ、新しいバックグラウンドピクセル（元の画像内のビンに偶然にマッチングする唯一の赤いピクセルＲを除く「他」を意味する「Ｏ」のラベルが付いた）に取り囲まれる。参照画像の非ゼロビンの部分集合であるテスト画像のビンのみを考慮することは、図６の左下に示すピクセルの組１２を特定するのに役立つ。元の画像に対応するピクセルは、ピクセル領域内で隣接すべきであり、その結果、隣接していない異常値（例えばピクセル１３）のみを無視することができる。このことにより、テスト画像から図６の右下に示す部分１４を効果的に分離する。その際、元の画像にマッチングするために、（例えば、本明細書に説明したヒストグラム技術、又はＳＩＦＴなどの他の技術により）この部分をチェックすることができる。
【００８８】
＜視野＞
【００８９】
ヒストグラムは、視点の変化により生じる視野の変化と共に緩やかに変化する。その結果、ヒストグラムに基づくマッチングは、大部分の視野変換の下でロバスト性がある。
【００９０】
＜幾何学的変換及び他の変形の下での結果＞
【００９１】
図７は、変換／変形された画像に対する上述の技術のいくつかを使用したマッチングの結果を示す。テスト画像は、参照画像の一つに対する様々な変換及び／又は変形からなる。各画像に対して生成されたヒストグラムは、１軸に沿った輝度の閾値処理された３レベルの２次微分値（ガウス関数の差）と、他の２軸に沿った（不均一に１６個のビンに量子化された）ＲＧ及びＢＹ要素とからなる。
【００９２】
「共通度」評価尺度は、テスト画像と参照画像との間の規格化ヒストグラム共通度を示す。「整合性」評価尺度は、参照画像の占有ビンの部分集合であるテスト画像の占有ビンの割合、及びテスト画像の占有ビンの部分集合である参照画像の占有ビンの割合の最大値を示す。特定の変換が、各テスト画像の下に列挙されている。
【００９３】
共通度評価値及び整合性評価値は、正確にマッチングする場合には高くなることを結果が示している。テスト画像を分類するために、共通度評価値及び整合性評価値のいずれか、及び／又は双方に一以上の閾値を適用することができる。例えば、共通度スコアが６０よりも大きく、整合性スコアが９０よりも大きい場合に、テスト画像の一部分又は全体が、参照画像とマッチングする可能性がある。共通度スコアが４５よりも小さいか、又は整合性スコアが８０よりも小さいとき、マッチングしない可能性がある。他の場合を不定状態に割り当てることができる。
【００９４】
これらの評価値の組合せ、例えば、それらの積又は多項式合成といった組合せを計算することもでき、閾値に対してテストすることができる。例えば、共通度と整合性との積が４０００よりも大きいとき、テスト画像の一部分又は全体が、参照画像とマッチングする可能性がある。積が３５００よりも小さいとき、マッチングがしない可能性がある。ここでも、他の場合を不定状態に割り当てることができる。
【００９５】
当然に、他の評価値及び他のヒストグラムを使用することができる。
【００９６】
特定の用途によっては、そのようなテストの結果は、整合の特定に対する決定的な回答を与えなくてもよい。しかし、このプロセスは、テスト画像と整合し得る参照画像の母集団を限定するスクリーニング関数として常に役立つ。次いで、回答を更に絞り込むために、他の技術を使用することができる。（或いは、そのような別の技術を最初に適用することができ、次いで、最終的な回答を得るのに本技術を使用することができる。）
【００９７】
＜更なる拡張＞
【００９８】
これまで説明した概念は、用途による要求に適応するよう、又はロバスト性を向上させるよう、更に拡張することができる。そのようないくつかの拡張を以下に説明する。
【００９９】
＜テスト画像及び参照画像のサブ画像への分割＞
【０１００】
これまで、一つのヒストグラムをテスト画像から計算し、一つのヒストグラムを参照画像から計算してきた。その代わりに、例えば、画像をサブブロック若しくは他の適当な区画に分割するか、又は画像分割技術を使用することにより（例えば、クラスタ形成、エッジ検出、領域成長、分水界変換などを含む方法により）、画像をより小さいサブ画像、又はサブ領域に分割することができる。そして、これらのサブ画像を、マッチング及び認識に使用することができる。
【０１０１】
これらの手法の多くは、形状及び構造に関する一部の情報をマッチングプロセスに導入し、マッチングの信頼性を向上させることができる。例えば、二つの画像の共通度が大きく、これらの画像間のいくつかのサブブロックも共通度が大きい場合を考える。このとき、マッチングが正確である確率が高い。評価値及び閾値の組合せに関して上述の構成を、ここでも使用することができる。
【０１０２】
＜粗から微細への戦略＞
【０１０３】
マッチング用の探索の際に、粗から微細への戦略を使用することができる。この戦略では、複数のヒストグラムが、各参照画像用のデータベース内に記憶される。最初にヒストグラムの次元の粗い量子化を使用し、次いで連続的に微細な量子化を使用することにより、複数のヒストグラムが形成される。マッチング用の探索は、最初に粗い量子化ヒストグラムを使用して探索空間を縮小し、次いで次第に微細な量子化を使用してマッチングを絞り込むことにより進行する。
【０１０４】
＜ヒストグラム情報と他の認識特徴との組合せ＞
【０１０５】
ヒストグラムに基づくマッチングは、より良好な識別を可能とするよう、他の認識特徴と組み合わせることができる。例えば、特徴点（Ｓａｌｉｅｎｔ Ｐｏｉｎｔｓ）、局所記述子、ＳＩＦＴ、形状、構造、及びテクスチャを明示的に使用して、近いヒストグラム間の曖昧さを除去することができる。ヒストグラム表現自体の中で、そのような特徴を使用することもできる。或いは、ヒストグラムを使用して探索空間を大幅に縮小することができ、次いで、他の技術を使用して最終的な認識又は特定を行うことができる。
【０１０６】
＜ビデオへの適用＞
【０１０７】
粗い量子化ヒストグラムの時間変化により、ビデオを特徴付けることができる。例えば、輝度及び二つの反対色軸のそれぞれについて二つのビンを考える。このとき、ビデオの各フレームは、八つのビンにより特徴付けることができる。
【０１０８】
一実装形態では、ビンのカウント値は、記憶することができ、それによってビデオを認識することができるフィンガプリントとして機能することができる。或いは、ビンのカウント値を記憶する代わりに、前のフレームのカウント値との差を記憶することができる。或いは、差の符号のみを記憶することができる。或いは、各ビンを、一つ又はいくつかの先行し連続するフレーム内の対応するビンと比較し、時間コンテキストにおいてビデオフレームを表すビット列を導出することができる。そして、ビデオのマッチング又は特定用に、これらのビット列又はシグネチャを使用することができる。
【０１０９】
＜探索空間縮小＞
【０１１０】
大規模認識システムでは、特徴点の局所記述子、ＳＩＦＴ、形状、テクスチャといった他の認識特徴を補完するのに、本発明の技術を使用することができる。他の認識特徴のいくつかをマッチングする探索空間を縮小することができる高速ルックアップ（又は二分探索）に、ヒストグラムマッチング技術の変更形態を使用することができる。ヒストグラムは、探索空間縮小のために使用して、各軸上に少数のビンで粗く構築することができる。
【０１１１】
＜ヒストグラムビンインデックスを使用したルックアップ＞
【０１１２】
この手法では、テスト画像の非ゼロビンのインデックスを使用して、対応するビンが非ゼロである参照データベース内の画像を分離する。一例として、８個のビンを有する１Ｄヒストグラムを考える。最初の三つのビンが、テスト画像については非ゼロであると仮定する。このとき、最初の三つの非ゼロビンを有する参照データベース内の画像をルックアップすることにより、マッチング用の参照データベースを縮小することができる。この概念は、一般性を失うことなく、３Ｄヒストグラム（又は任意の次元のヒストグラムでも）に拡張することができる。
【０１１３】
＜２値参照＞
【０１１４】
高速探索空間縮小の別の手法は、ビンの占有状態に基づいて、ビンの位置を２値化することである。８個のビンを有する１Ｄヒストグラムの上記の例では、各ビンを２値、即ち、ビンが占有されるとき（ビンのカウント値、非ゼロ又は上記のいくつかの占有閾値）には１、その他の場合は０で表現することができる。そして、上記のルックアップの例では、最初の三つの位置に値１を有する参照データベース内の全ての画像のルックアップを高速で行うために、８ビットのベクトルを使用することができる。この概念を多次元ヒストグラムに拡張することができる。例えば、ヒストグラムが、２次微分値輝度情報に４つのビン、色方向にそれぞれ８つのビンを含むとき、２０ビットのベクトルによって、非ゼロビン位置を表現することができる。ロバスト性を改善するために、占有ビンに隣接するビンの位置に値１のラベルを付けることができ、（例えば、ノイズ又は他の環境による）隣接するビンに入る可能性がある境界の場合の量子化値が失われないことを確実にする。
【０１１５】
＜バックグラウンドコンフュージョン＞
【０１１６】
探索空間縮小技術は、バックグラウンドコンフュージョンが存在する場合に、機能停止する傾向がある。バックグラウンド色及び特徴は、参照画像内には存在しない。バックグラウンドに対応するビンを含まない参照画像を無視すると、マッチングが失敗する。この課題に対処する一つの解決策は、上述したように、画像をより小さいサブ領域に分割し、バックグラウンドを含まない少なくとも一つのサブ領域が確実に存在するようにすることである。
【０１１７】
＜ＳＩＦＴ＞
【０１１８】
説明したように、他の画像認識技術と共に、本技術を使用することができる。そのような一つの普及した技術がＳＩＦＴである。
【０１１９】
ＳＩＦＴは、Ｓｃａｌｅ−Ｉｎｖａｒｉａｎｔ Ｆｅａｔｕｒｅ Ｔｒａｎｓｆｏｒｍ（スケール不変特徴変換）の略語で、Ｄａｖｉｄ Ｌｏｗｅにより開拓されたコンピュータビジョン技術であり、「Ｄｉｓｔｉｎｃｔｉｖｅ Ｉｍａｇｅ Ｆｅａｔｕｒｅｓ ｆｒｏｍ Ｓｃａｌｅ−Ｉｎｖａｒｉａｎｔ Ｋｅｙｐｏｉｎｔｓ」、Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ、６０、２（２００４）、９１〜１１０頁と、「Ｏｂｊｅｃｔ Ｒｅｃｏｇｎｉｔｉｏｎ ｆｒｏｍ Ｌｏｃａｌ Ｓｃａｌｅ−Ｉｎｖａｒｉａｎｔ Ｆｅａｔｕｒｅｓ」、Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ、Ｃｏｒｆｕ、Ｇｒｅｅｃｅ（１９９９年９月）、１１５０〜１１５７頁と、米国特許第６，７１１，２９３号とを含むＤａｖｉｄ Ｌｏｗｅの様々な論文に記載されている。
【０１２０】
ＳＩＦＴは、局所画像特徴の特定、記述、及び後続の検出によって機能する。ＳＩＦＴの特徴は、局所的であり、特定の着目点における物体の出現に基づくものであり、画像スケール、回転、及びアフィン変換に対して不変である。ＳＩＦＴの特徴は、照度変化、ノイズ、及び視点のいくつかの変化に対してもロバスト性がある。これらの特性に加えて、ＳＩＦＴの特徴は、独特であり、比較的抽出しやすく、不一致の確率が低い正確な物体識別を可能にし、局所特徴の（大きい）データベースに対してマッチングするのが容易である。ＳＩＦＴ特徴の組による物体記述は、部分的なオクルージョンに対してもロバスト性があり、位置及び姿勢を計算するために、物体からのわずか三つのＳＩＦＴ特徴で十分であり得る。
【０１２１】
この技術は、参照画像内のキーポイントである局所画像特徴を特定することにより開始する。この技術は、異なるスケール（解像度）で画像とガウスぼかしフィルタとを畳み込み、連続するガウスぼかし画像間の差を求めることにより行われる。キーポイントは、複数のスケールにおいて生じるガウス関数の差の最大値又は最小値を有する画像特徴である。（ガウス関数の差によるフレームの各ピクセルが、同じスケールにおける八つの隣接ピクセル、及び複数の隣接スケール（例えば他の９つのスケール）の各々の対応するピクセルと比較される。ピクセル値がこれら全てのピクセルからの最大値又は最小値であるとき、このピクセル値が候補キーポイントとして選ばれる。
【０１２２】
（ここで説明した手順は、画像の局所スケールラプラス変換の空間スケール極値を検出するブロブ検出法であることが理解されよう。ガウス関数の差の手法は、ピラミッド配置で表現される、そのようなラプラス演算の概算値である。）
【０１２３】
上記の手順は、例えば、コントラストが低い（従って、ノイズに影響を受けやすい）か、又はエッジに沿って不十分に求められた位置を有することにより、不適当な多くのキーポイントを通常特定する（ガウス関数の差は、エッジに沿った応答が強く、多くの候補キーポイントをもたらすが、これらの候補キーポイントはノイズに対してロバスト性がない）。これらの信頼性のないキーポイントは、正確な位置、スケール、及び主曲率に関する近傍データに候補キーポイントを詳細にフィッティングすることにより、スクリーニング除去される。この方法は、コントラストが低いか、又はエッジに沿って不十分に位置判定されるキーポイントを棄却する。
【０１２４】
より詳細には、このプロセスは、キーポイント位置をより正確に決定するために、各候補キーポイントに関して近傍データを内挿することにより開始する。このプロセスは、最大／最小位置の精密な推定量を決定するために、キーポイントを原点とするテイラー展開により、行われることが多い。
【０１２５】
２次のテイラー展開の値を使用して、低コントラストのキーポイントを特定することもできる。コントラストが閾値（例えば０．０３）よりも低いとき、キーポイントは無視される。
【０１２６】
強いエッジ応答を有するが、局所性が不十分であるキーポイントを除去するために、コーナー検出手順の変形が適用される。つまり、この手順は、エッジにわたって主曲率を計算するステップと、端部に沿って主曲率を比較するステップと、を含む。この手順は、２次ヘッセ行列の固有値を求めることにより行われる。
【０１２７】
不適当なキーポイントが破棄されると、残ったキーポイントが、局所画像勾配関数によって方向（Ｏｒｉｅｎｔａｔｉｏｎ）について評価される。勾配の大きさ及び方向は、ガウスぼかし画像内のキーポイントの周りの近傍領域内の全てのピクセルに関して（そのキーポイントのスケールで）計算される。そして、３６個のビンを有する方向ヒストグラムが集計される。なお、各ビンは、１０段階の方向を含む。近傍の各ピクセルは、その勾配の大きさと、キーポイントのスケールの１．５倍のσを有するガウス関数により重み付けされた寄与率でヒストグラムに寄与する。このヒストグラム内のピークは、キーポイントの主方向を規定する。この方向データにより、ＳＩＦＴは、回転に対するロバスト性を達成する。その理由は、主方向に対してキーポイント記述子を表現することができるからである。
【０１２８】
上述のことから、異なるスケールである複数のキーポイントは、それぞれ対応する方向を用いて特定される。このデータは、画像平行移動、スケーリング、及び回転に対して不変である。そして、各キーポイントに関して、１２８個の要素記述子が生成され、照度及び３Ｄ視点に対するロバスト性を可能にする。
【０１２９】
このオペレーションは、ここで検討した方向評価手順に類似している。キーポイント記述子は、（４ｘ４）近傍ピクセル上の方向ヒストグラムの組として計算される。方向ヒストグラムは、キーポイント方向に関連しており、方向データは、キーポイントスケールにスケールが最も近いガウス画像から生じる。上述したように、各ピクセルの寄与率は、勾配の大きさと、キーポイントのスケールの１．５倍のσを有するガウス関数により重み付けされる。ヒストグラムはそれぞれ、８個のビンを含み、各記述子は、キーポイントの周りに４×４配列の１６個のヒストグラムを含む。このことは、（４×４×８＝１２８要素）を有するＳＩＦＴ特徴ベクトルにつながる。このベクトルは、照度変化に対する不変性を向上させるために正規化される。
【０１３０】
上述の手順は、参照データベースをコンパイルするために、トレーニング画像に適用される。そして、未知の画像が、キーポイントデータを生成するために上述のように処理され、データベース内の最もマッチングする画像が、ユークリッド距離のような評価尺度により特定される。（通常は、純粋なユークリッド距離計算の代わりに、「ｂｅｓｔ−ｂｉｎ−ｆｉｒｓｔ」アルゴリズムを使用して、数オーダー規模の速度改善を達成する。）誤判定可を避けるために、最適マッチング率の距離スコアが、次の最適マッチング率の距離スコアに近いとき、例えば２５％であるとき、「不一致」出力が生成される。
【０１３１】
更に性能を改善するために、画像をクラスタリングによりマッチングすることができる。この方法は、同じ参照画像に属する特徴を特定し、クラスタリングされていない結果を偽として無視することができる。ハフ変換を使用して、同じ物体姿勢に投票する特徴のクラスタを特定することができる。
【０１３２】
次世代携帯電話の実装に適した、ＳＩＦＴ手順を行う特定のハードウェア実施形態を説明する記事は、Ｂｏｎａｔｏら、「Ｐａｒａｌｌｅｌ Ｈａｒｄｗａｒｅ Ａｒｃｈｉｔｅｃｔｕｒｅ ｆｏｒ Ｓｃａｌｅ ａｎｄ Ｒｏｔａｔｉｏｎ Ｉｎｖａｒｉａｎｔ Ｆｅａｔｕｒｅ Ｄｅｔｅｃｔｉｏｎ」、ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｃｉｒｃｕｉｔｓ ａｎｄ Ｓｙｓｔｅｍｓ ｆｏｒ Ｖｉｄｅｏ Ｔｅｃｈ、Ｖｏｌ．１８、Ｎｏ．１２、２００８年である。
【０１３３】
ＳＩＦＴ技術を実行する別のハードウェアアーキテクチャは、Ｓｅら、「Ｖｉｓｉｏｎ Ｂａｓｅｄ Ｍｏｄｅｌｉｎｇ ａｎｄ Ｌｏｃａｌｉｚａｔｉｏｎ ｆｏｒ Ｐｌａｎｅｔａｒｙ Ｅｘｐｌｏｒａｔｉｏｎ Ｒｏｖｅｒｓ」、Ｐｒｏｃ．ｏｆ Ｉｎｔ．Ａｓｔｒｏｎａｕｔｉｃａｌ Ｃｏｎｇｒｅｓｓ（ＩＡＣ）、２００４年１０月に記載されている。
【０１３４】
ＳＩＦＴは、おそらくロバスト性のある局所記述子を生成する最もよく知られた技術であるが、用途によっては、略適当であり得る他の技術が存在する。これらの技術は、ＧＬＯＨ（Ｍｉｋｏｌａｊｃｚｙｋら、「Ｐｅｒｆｏｒｍａｎｃｅ Ｅｖａｌｕａｔｉｏｎ ｏｆ Ｌｏｃａｌ Ｄｅｓｃｒｉｐｔｏｒｓ」、ＩＥＥＥ Ｔｒａｎｓ．Ｐａｔｔｅｒｎ Ａｎａｌ．Ｍａｃｈ．Ｉｎｔｅｌｌ．、Ｖｏｌ．２７、Ｎｏ．１０、１６１５〜１６３０頁、２００５年を参照）と、ＳＵＲＦ（Ｂａｙら、「ＳＵＲＦ：Ｓｐｅｅｄｅｄ Ｕｐ Ｒｏｂｕｓｔ Ｆｅａｔｕｒｅｓ」、Ｅｕｒ．Ｃｏｎｆ．ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ（１）、４０４〜４１７頁、２００６年と、Ｃｈｅｎら、「Ｅｆｆｉｃｉｅｎｔ Ｅｘｔｒａｃｔｉｏｎ ｏｆ Ｒｏｂｕｓｔ Ｉｍａｇｅ Ｆｅａｔｕｒｅｓ ｏｎ Ｍｏｂｉｌｅ Ｄｅｖｉｃｅｓ」、Ｐｒｏｃ．ｏｆ ｔｈｅ ６ｔｈ ＩＥＥＥ ａｎｄ ＡＣＭ Ｉｎｔ．Ｓｙｍｐ．Ｏｎ Ｍｉｘｅｄ ａｎｄ Ａｕｇｍｅｎｔｅｄ Ｒｅａｌｉｔｙ、２００７年と、Ｔａｋａｃｓら、「Ｏｕｔｄｏｏｒｓ Ａｕｇｍｅｎｔｅｄ Ｒｅａｌｉｔｙ ｏｎ Ｍｏｂｉｌｅ Ｐｈｏｎｅ Ｕｓｉｎｇ Ｌｏｘｅｌ−Ｂａｓｅｄ Ｖｉｓｕａｌ Ｆｅａｔｕｒｅ Ｏｒｇａｎｉｚａｔｉｏｎ」、ＡＣＭ Ｉｎｔ．Ｃｏｎｆ．ｏｎ Ｍｕｌｔｉｍｅｄｉａ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖａｌ、２００８年１０月とを参照）とを含む。
【０１３５】
上述したように、本ヒストグラム技術は、ＳＩＦＴ又はこれら他の技術と共に使用することができる。
【０１３６】
＜結論的見解＞
【０１３７】
上述のことから、多次元ヒストグラムに基づく様々な技術は、物体及び画像を特徴付け、マッチングし、認識するために使用することができることが理解されよう。これらの技術は、幾何学的変換、並びに輝度変化及び照度変化の下でロバスト性を有することができる。これらの技術は簡単な計算を含むので、これらの構成は、携帯電話及び他の携帯デバイス、又はエンベデッドシステムに効率的に実装することができる。
【０１３８】
例示的な実施形態及び構成を参照して我々の技術の原理を説明し、図示してきたが、詳細な実装形態は、例示的なものにすぎず、我々の技術範囲を限定するものとみなすべきでないことが理解されよう。
【０１３９】
例えば、詳細な技術を、空間（ピクセル）ドメインで表現される画像データのコンテキストで説明したが、他のドメインで表現される画像情報に同じ技術を適用することができる。異なる色軸及び／又は輝度軸のそれぞれに関して、ＦＦＴデータを生成することができるが、説明した技術は、得られた空間周波数ドメインデータに適用することができる。（参照することにより援用する文献は、他の様々なドメインを説明している。）
【０１４０】
同様に、様々なフィルタ技術によりフィルタリングすることを含む、他の方法で処理された画像データに、本発明の技術を適用することができる。（サンプルフィルタリング演算は、メジアン、ラプラシアン、ウィーナ、ソーベル、ハイパス、ローパス、バンドパス、ガボール、符号などを含む。Ｄｉｇｉｍａｒｃの特許、米国特許第６，４４２，２８４号、第６，４８３，９２７号、第６，５１６，０７９号、第６，６１４，９１４号、第６，６３１，１９８号、第６，７２４，９１４号、第６，９８８，２０２号、第７，０１３，０２１号、及び第７，０７６，０８２号は、そのような様々なフィルタを示す。）テスト画像又は参照画像は、様々な幾何学的変換を受ける可能性もある。米国特許第７，５０８，９７８号に説明されるように、非平面の原型からブックページの平面スキャンを行うときにＧｏｏｇｌｅにより使用されるデワープ処理構成が、例示的なものである。
【０１４１】
本明細書は、参照しやすいようにセクション見出しを使用してきたが、セクション見出しは、開示した技術の適用性又は汎用性を限定するものとみなすべきでない。
【０１４２】
輝度軸をしばしば参照してきた。輝度自体を使用する必要がないことを理解されたい。軸は、ガウス関数の差といった輝度情報から導出された値に対応することができる。当然、他の実装形態では、輝度軸を全く使用しない場合があり、即ち、別の画像パラメータで代用することができる。
【０１４３】
本明細書の焦点は画像（従ってビデオも）にあるが、同じヒストグラム技術及び比較基準値の多くが、同様にオーディオ処理及び認識に関連する。従って、本明細書は、オーディオアナログから、説明した画像構成まで教示するものとして読むべきである。
【０１４４】
本明細書に個々に説明した特徴は、説明した特徴及び構成の他のものと組み合わせて使用することができることが理解されよう。同様に、本明細書に説明した特徴は、参照により組み込まれる特許明細書に記載された技術と組み合わせて使用することができる（逆も同様）。
【０１４５】
本発明の技術は、様々な画像応答システムに使用することができる。実例は、Ｄｉｇｉｍａｒｃの米国特許第６，９４７，５７１号、米国特許出願公開第２００６０２４０８６２号及び第２００６００１２６７７号（どちらもＧｏｏｇｌｅ）、第２００７０１７５９９８号、第２００２０１０２９６６号（どちらもＬｅｖ）、第２００６００５６７０７号（Ｎｏｋｉａ）、第２００６００２６１４０号（ＥｘＢｉｂｌｉｏ）、第２００３００８３０９８号（Ｃａｎｏｎ）、第２００１０００１８５４号（ＡｉｒＣｌｉｃ）、米国特許第７，０１６，５３２号（Ｅｖｒｙｘ）、第６，４９１，２１７号（Ｐｈｉｌｉｐｓ）、及び本明細書で参照する他の特許明細書に説明される。
【０１４６】
詳細な技術は、ロバスト性のある画像のフィンガプリント処理の形態とみなすことができる。コンテンツのフィンガプリント処理及び関連するシステムに関する追加の情報は、例えば、米国特許出願公開第２００５０００４９４１号、第２００５０１０８２４２号、第２００６００４１７５３号、第２００６００７５２３７号、第２００６０２１８１２６号、第２００７００７１３３０号（全てＰｈｉｌｉｐｓ）、第２００７０２３９７５６号（Ｍｉｃｒｏｓｏｆｔ）、第２００７０２３７３６４号（Ｆｕｊｉ Ｐｈｏｔｏ Ｆｉｌｍ）、米国特許第７，１３０，４６６号（Ｃｏｂｉｏｎ）、第７，１９４，７５２号（Ｋｅｎｙｏｎ）、米国特許出願公開第２００７０２５３５９４号（Ｖｏｂｉｌｅ）、第２００２００４４６５９号（ＮＥＣ）、及び第２００７０２５０７１６号（Ｄｉｇｉｍａｒｃ）特許明細書に見られる。
【０１４７】
補完技術であるデジタル透かしデコーディングを、いくつかの実施形態に使用することができる。透かしエンコーディング／デコーディングの技術は、例えば、Ｄｉｇｉｍａｒｃの米国特許第６，５９０，９９６号及び第６，１２２，４０３号、並びに２００８年５月２２日に出願したＳｈａｒｍａらによる米国特許仮出願第１２／１２５，８４０号に記載されている。デジタル透かしとフィンガプリントとを組み合わせた使用は、例えば、Ｄｉｇｉｍａｒｃの米国特許第７，２８９，６４３号に記載されている。
【０１４８】
幾何学的校正データは、一般にデジタル透かしにより伝えられる。デジタル透かしは、画像のアフィン変換及び他の変換を容易に特定し、必要に応じて、補償することを可能とする。そのような構成は、例えば、米国特許第６，６１４，９１４号、第６，５８０，８０９号、第７，０７２，４９０号、及び第７，３１９，７７５号、並びに米国特許出願公開第２００６００３１６８４号に記載されている。米国特許第６，９５９，０９８号は、可視画像特徴（例えば、直線的な物体の端部）と共に、そのような透かし校正信号により変形をどのように特徴付けることができるかを教示している。そのようなアフィン変換情報から、携帯電話の撮像素子に対する透かし物体の６Ｄ位置を決定することができる。
【０１４９】
いくつかの実施形態では、視覚刺激に対する応答は、携帯電話カメラにより取得された画像データ上の、携帯電話スクリーン上にもたらされるグラフィックオーバーレイを含むことができる。オーバーレイは、画像データの特徴と共に幾何学的に校正され、画像に示される物体のアフィン変形に対応してアフィン変形され得る。そのような技術は、例えば、Ｄｉｇｉｍａｒｃの米国特許出願公開第２００８０３０００１１号にさらに記載されている。
【０１５０】
（例えば、テスト画像と参照画像／元の画像との）画像マッチングを最も多く参照した。しかし、テスト画像内に取得された物体をマッチングするのに、同じ構成を使用することができることを当業者には理解されよう。従って、画像（又は画像データ）のマッチングを参照することは、物体（又は物体データ）のマッチングを参照するものとしても理解されるべきである。
【０１５１】
ＳＩＦＴ技術が様々な倍率で画像を操作するように、本技術も同様にすることができる。含まれる計算の単純性のために、様々な倍率のヒストグラムに基づくデータを高速に計算することができる。
【０１５２】
携帯電話を参照してきたが、本発明の技術は、携帯も固定も何れでも、全ての方式のデバイスに利用可能であることが認識されよう。ＰＤＡ、オーガナイザ、携帯音楽プレーヤ、デスクトップコンピュータ、ウェアラブルコンピュータ、サーバなどは全て、本明細書に説明した原理を使用することができる。特に、企図した携帯電話は、ＡｐｐｌｅのｉＰｈｏｎｅ、ＧｏｏｇｌｅのＡｎｄｒｏｉｄ仕様に追随する携帯電話（例えば、ＨＴＣ Ｃｏｒｐ．によりＴ−Ｍｏｂｉｌｅ用に製作されたＧ１ ｐｈｏｎｅ）を含む。用語「携帯電話」は、厳密な意味での携帯又は電話でなくとも、そのような全てのデバイスを含むものと解釈すべきである。
【０１５３】
（タッチインタフェースを含むｉＰｈｏｎｅの詳細は、米国特許出願公開第２００８０１７４５７０号に記載されている。）
【０１５４】
本開示の方法を実施するのに使用することができる、携帯電話及び他のコンピュータの構造には、当業者であれば精通している。一般的な用語では、それぞれが、一以上のプロセッサ、一以上のメモリ（例えばＲＡＭ）、記憶装置（例えばディスク又はフラッシュメモリ）、ユーザインタフェース（例えば、キーパッド、ＴＦＴ ＬＣＤ、又はＯＬＥＤ ディスプレイスクリーン、タッチ又は他のジェスチャセンサ、カメラ又は他の光センサ、マイクロフォンなどと共に、グラフィカルユーザインタフェースをもたらすソフトウェア命令を含むことができる）、バッテリ、及び他のデバイスと通信するインタフェース（ＧＳＭ、ＣＤＭＡ、Ｗ−ＣＤＭＡ、ＣＤＭＡ２０００、ＴＤＭＡ、ＥＶ−ＤＯ、ＨＳＤＰＡ、ＷｉＦｉ、ＷｉＭａｘ、若しくはブルートゥースなどの無線、及び／又はイーサネットローカルエリアネットワーク、Ｔ−１インターネット接続などによる有線とすることができる）を含む。説明した構成の一部分又は全てを実施するのに使用することができる例示的な携帯電話を図８に示す。
【０１５５】
プロセッサは、特定目的のハードウェアデバイスであり得、メモリ若しくは記憶装置から、又はそれらの組合せにより読み出されるソフトウェア命令を実行するプログラム可能デバイスによって実装され得る。（Ａｒｍ，Ｌｉｍｉｔｅｄにより開発された３２ビットＲＩＳＣアーキテクチャを使用したＡＲＭシリーズのＣＰＵは、多くの携帯電話で使用される。）従って、「プロセッサ」を参照することは、実装の特定の形態ではなく、機能を参照しているものと理解すべきである。
【０１５６】
専用のハードウェア、又はソフトウェアで制御されるプログラム可能ハードウェアに加えて、プロセッサは、Ｘｉｌｉｎｘ、Ｖｉｒｔｅｘシリーズデバイスなどのフィールドプログラマブルゲートアレイを含むこともできる。或いは、プロセッサは、Ｔｅｘａｓ Ｉｎｓｔｒｕｍｅｎｔｓ ＴＭＳ３２０シリーズデバイスなどの一以上のデジタル信号プロセッシングコアを含むことができる。
【０１５７】
詳細な機能を実装するソフトウェア命令は、本明細書に記載した説明、結論、及び上述の他の規定から、当業者なら容易に書くことができる。
【０１５８】
通常、説明した方法を実施するデバイスは、ハードウェアデバイスへのインタフェース及び汎用の機能を提供するオペレーティングシステムソフトウェアを含み、ユーザが要求する特定のタスクを実行するのに選択的に呼び出すことができる応用ソフトウェアも含む。既知のブラウザソフトウェア、通信ソフトウェア、及びメディア処理ソフトウェアは、本明細書に説明した使用に適合させることができる。いくつかの実施形態は、エンベデッドシステムとして、即ち、（例えば、通常の基本的携帯電話の場合のように）オペレーティングシステムソフトウェア及び応用ソフトウェアがユーザには見分けがつかない特定目的コンピュータシステムとして実装することができる。本明細書に説明した機能は、オペレーティングシステムソフトウェア及び応用ソフトウェア内で、並びに／又はエンベデッドシステムソフトウェアとして実装することができる。
【０１５９】
様々な機能を様々なデバイスに実装することができる。例えば、携帯電話が遠隔のサービスプロバイダのサーバと通信するシステムでは、様々なタスクをいずれか一つのデバイスで独占的に実行することができるか、又はデバイス間で実行を分散することができる。例えば、携帯電話上のテスト画像からのヒストグラムデータの抽出、及び遠隔サーバ上の対応する参照画像のデータベースの探索は、一つのアーキテクチャとなるが、他の多くのものが存在する。例えば、参照画像に関する情報は、携帯電話上に記憶することができ、携帯電話は、全ての外部デバイスに依存することなく、テスト画像を取得し、ヒストグラムデータを生成し、参照画像に関する記憶されたヒストグラムデータと比較することができる。従って、特定のデバイス（例えば携帯電話）で実行される演算の記述は、限定的なものでなく、例示的なものであり、別のデバイス（例えば遠隔サーバ）又はデバイス間で共有される演算の実行も企図されることが明らかであることを理解されたい。（さらに、二つよりも多いデバイスを通常、使用することができる。例えば、サービスプロバイダは、いくつかのタスク、機能、又は演算をそのようなタスク専用のサーバに問い合わせることができる。）
【０１６０】
同様に、データは、局所デバイス、遠隔デバイス、クラウド、分散など、どこでも記憶することができる。
【０１６１】
演算は、特定の識別可能ハードウェアにより独占的に実行する必要はない。むしろ、いくつかの演算を、さらに一般に匿名のシステムにより実行処理する他のサービス（例えばクラウドコンピューティング）に問い合わせることができる。そのような分散システムは、大規模（例えば世界中のコンピューティング資源を含む）、又は局所的に（例えば、携帯デバイスが、ブルートゥース通信により近接するデバイスを特定するとき、演算中に近接するデバイスの一つ又は複数を含むように）することができる。
【０１６２】
本明細書を極度に長くすることなく包括的な開示を行うために、出願人は、上述した特許、特許出願、及び他の文献を参照にすることにより明示的に援用する。（そのような文献は、特定の教示に関して上述したとしても、全体が援用される。）これらの参考文献は、本明細書に説明した構成に援用することができる技術及び教示を開示し、本明細書に説明した技術及び教示をこれらの参考文献に援用ことができる。
【０１６３】
私は、私の技術の一部分として、以下の特許請求の範囲の範囲及び技術的思想、並びに均等物に入る可能性がある、そのような全ての変更形態を請求する。（特許請求の範囲は、説明した多数の発明概念を考慮して、出願人が発明とみなす技術の一部分のみを対象とする。出願人は、上述の他の発明概念を引き出す追加の特許請求の範囲を提出する権利を保持する。）
【関連出願データ】
【０００１】
本技術は、本件の譲受人による他の特許出願において開示した技術を基礎とし、それを拡張するものである。したがって、出願人が本技術を適用しようと意図しており、当業者が精通してものと想定する詳細な構成を与える以下の出願に、読者を向ける。
２００８年１０月３１日に出願した米国特許出願第６１／１１０，４９０号
２００８年１１月１４日に出願した米国特許出願第１２／２７１，６９２号（米国特許出願公開第２０１０００４６８４２号として公開された）
２００８年１１月１４日に出願した米国特許出願第１２／２７１，７７２号（米国特許出願公開第２０１００１１９２０８号として公開された）
２００９年２月５日に出願した米国特許出願第６１／１５０，２３５号
２００９年３月３日に出願した米国特許出願第６１／１５７，１５３号
２００９年４月８日に出願した米国特許出願第６１／１６７，８２８号
２００９年４月１４日に出願した米国特許出願第６１／１６９，２６６号
２００９年５月８日に出願した米国特許出願第６１／１７６，７３９号
これらの文献の開示を、参照することにより本明細書に援用する。
【技術分野】
【０００２】
本技術は、画像及びビデオ処理に関するものであり、より詳細には、色ヒストグラムのような簡単な特徴によって画像を表現することに関するものである。
【背景及び概要】
【０００３】
一側面では、本明細書は、画像（又はビデオ）をデータベース内に記憶された多くのものの一つとして認識する技術に関する。本技術は、画像内の物体を認識するために使用することもできる。
【０００４】
これらの技術の多くの背後の基本概念は、幾何学的変換、視点の変化、ノイズ、オクルージョン、バックグラウンド、輝度変化、及び照明の変化に対して不変であるか、又はこれらの影響に伴って緩やかに変化する簡単な特徴によって、画像（又は物体）を表現することである。そのような表現の一つが、３Ｄ色ヒストグラム（Ｓｗａｉｎ及びＢａｌｌａｒｄ、「Ｃｏｌｏｒ Ｉｎｄｅｘｉｎｇ」、Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ、７（１）、１１〜３２頁、１９９１年を参照）である。
【０００５】
色ヒストグラムは、比較的高速で計算することができ、認識及び索引（インデックス）付けタスクに広く使用されている。しかし、従来の色ヒストグラムは、明度、コントラスト及び輝度の変化、並びに照度変化に対する感度の高さといった様々な欠点を有する。
【０００６】
本技術の種々の側面は、そのような影響に対して感度がより低い簡単な表現を生成する色ヒストグラムの概念の拡張に関している。また、ストグラムパラメータ及び集合理論に基づき、幾何学的変換の下でより良好なロバスト性をもたらす簡単なマッチング技術を開示する。高速データベース探索及び探索空間の縮小のためにヒストグラム表現を使用する技術も説明する。
【０００７】
説明する技術は、それらの単純性及び速度に主として起因して、携帯デバイス又はエンベデッドシステム上での演算に良く適している。
【０００８】
上記説明は、添付の図面を参照して進める以下の詳細な説明から、より容易に明らかとなる。
【図面の簡単な説明】
【０００９】
【図１Ａ】第１の参照画像を示す図である。
【図１Ｂ】輝度に８個のビン（ｂｉｎ）、赤−緑及び青−黄の反対色方向にそれぞれ１６個のビン（即ち、２０４８データ要素）を用いた、図１Ａの画像の３Ｄヒストグラムを示す図であり、球体は、非ゼロヒストグラムのビンの個数を示し、球体のサイズは、各ビンのピクセルの数を示す。
【図２Ａ】図１Ａに類似しているが、第２の参照画像を示す図である。
【図２Ｂ】図１Ｂに類似しているが、第２の参照画像を示す図である。
【図３】三つのレベルに閾値処理した後の、図１Ａの輝度の２次微分値を示す図である。
【図４Ａ】図１Ｂに類似しているが、輝度軸の代わりに、２次微分のような関数が三つのレベルのみに量子化され、成分色軸を不均一に量子化した図である。
【図４Ｂ】図２Ｂに類似しているが、輝度軸の代わりに、２次微分のような関数が三つのレベルのみに量子化され、成分色軸を不均一に量子化した図である。
【図５Ａ】照度変化が色の変化をどのように引き起こす可能性があるかを示す、図１Ａの参照画像である。
【図５Ｂ】照度変化が色の変化をどのように引き起こす可能性があるかを示す、図１Ａの参照画像である。
【図６】ヒストグラム、又は他の分析用のズームアウト画像の候補部分の区分けを示す流れ図である。
【図７】選択した幾何学的変換及び他の変形についての、参照画像とテスト画像との間の整合性を示す表である。
【図８】本技術との使用に適した携帯電話のブロック図である。
【発明を実施するための形態】
【００１０】
＜３Ｄ色ヒストグラム＞
【００１１】
Ｓｗａｉｎ及びＢａｌｌａｒｄ（上記参照）は、認識タスク用に色物体を表現するために、色ヒストグラムの使用を導入している。彼らは、色ヒストグラムがオクルージョン及び視野の変化が存在しても安定した表現をもたらし、多数の物体を区別することができることを示している。彼らは、マッチング用にテストヒストグラムと参照ヒストグラムとを比較するヒストグラム共通度（インタセクション）と呼ばれる評価尺度を導入している。
【００１２】
色ヒストグラムは、ある色が画像内に現れる回数を計数したものである。色は、ＲＧＢ、ＨＳＶ、又は輝度と反対色との組合せといった別個の色空間表現において特定することができる。図１Ａ及び１Ｂは、画像と、輝度（Ｌ）、赤−緑（ＲＧ）、及び青−黄（ＢＹ）により表現される色軸を有する画像の３Ｄ色ヒストグラムとを示している。輝度は、８個のビン（ｂｉｎ）で定量化され、他の色軸はそれぞれ、１６個のビンで定量化されている（即ち、３Ｄヒストグラムでは２０４８データ要素）。Ｌ、Ｒ−Ｇ、及びＢ−Ｙ色値は、以下のようにＲＧＢ値から得られる。
Ｌ＝０．３３３＊（Ｒ＋Ｇ＋Ｂ）
ＲＧ＝０．５＊（Ｒ−Ｇ）
ＢＹ＝０．５＊Ｂ−０．２５＊（Ｒ＋Ｇ）
【００１３】
図２Ａ及び２Ｂは、別の画像と当該別の画像に対応する色ヒストグラムとを示している。図１及び図２のヒストグラムを比較すると、ヒストグラムは、各画像を区別する色特徴を表わしていることが示唆されている。
【００１４】
＜ヒストグラムを使用した物体認識、類似性、及びマッチング＞
【００１５】
３Ｄヒストグラム（又は色ヒストグラム）は、画像内の各タイプの色成分の量又は比率を測定するものである。３Ｄヒストグラムは、画像の色に関して画像の特性化を可能とする。例えば、三つのヒストグラム軸として赤、緑、及び青の成分を含む３Ｄヒストグラムを考える。この場合に、緑のバックグラウンドに対する赤い花を含む簡単な画像は、赤軸及び緑軸に沿って支配的な色成分を有することとなる。また、ピクセルの２５％が赤で、残りのピクセルが緑であることを想定する。この場合に、ヒストグラムが赤及び緑の成分のみを有する画像全体は、花の画像に「類似する」ものとみなすことができる。ヒストグラムが、花の画像と略同じ比率（１：３）で赤及び緑のみを有する画像は、花の画像によりマッチングするものとみなすことができる。わずかに異なる姿勢を通して得られる緑のバックグラウンドに対する花の画像を認識することもできる。
【００１６】
＜ヒストグラム共通度＞
【００１７】
ヒストグラム共通度（ヒストグラムインタセクション）は、二つのヒストグラム間の類似性の評価尺度を与えるものである。Ｎ個のビンを含むヒストグラムに関するヒストグラム共通度評価尺度は、双方のヒストグラムに共通するカウント値の合計により与えられる。Ｓｗａｉｎ及びＢａｌｌａｒｄは、ヒストグラム共通度を以下のように定義している。
【数１】
ここで、ｈ（ｔ，ｒ）は、テスト画像ｔと参照画像ｒとの間のヒストグラム共通度である。基本的に、ヒストグラム共通度の評価値は、テストヒストグラム及び参照ヒストグラムに共通するピクセル数のカウント値を与える。ｈ（ｔ，ｒ）が高い値であることは、テストヒストグラムが参照ヒストグラムにマッチングすることを示す。
【００１８】
Ｓｗａｉｎ及びＢａｌｌａｒｄは、以下のように、正規化ヒストグラム共通度評価尺度も定義している。
【数２】
【００１９】
正規化ヒストグラム共通度評価尺度Ｈ（ｔ，ｒ）は、テスト画像が参照画像と同一であるときに、１．０となる。異種の画像では、正規化ヒストグラム共通度評価尺度は、ゼロにより近づく。
【００２０】
ヒストグラム共通度評価尺度は、二つの組の間、即ちテスト画像のヒストグラムを表現する一方の組と、参照画像のヒストグラムを表現する他方の組との間の共通度と解釈することができる。
【００２１】
＜基本的なヒストグラム手法の拡張＞
【００２２】
色ヒストグラムは、平行移動、及び画像に垂直な軸線の周りの回転に対して不変である。（画像が側方に変位するか、又は回転するとき、色及び色の比率は、変化しない。）色ヒストグラムは、オクルージョン及びバックグラウンドコンフュージョン（ｂａｃｋｇｒｏｕｎｄ ｃｏｎｆｕｓｉｏｎ）に伴って緩やかに変化する傾向もある。
【００２３】
一方、色ヒストグラムは、輝度変化及び照明（照度）変化に影響されやすい傾向がある。Ｓｗａｉｎ及びＢａｌｌａｒｄの元の技術の改良に基づく種々の手法が提案されている。一つのこのような手法は、多次元受容野ヒストグラムを採用しており、当該ヒストグラムにおいては、物体がガボールフィルタといった局所近傍オペレータの結合統計量により表現される（例えば、Ｓｃｈｉｅｌｅら、「Ｒｅｃｏｇｎｉｔｉｏｎ Ｗｉｔｈｏｕｔ Ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ Ｕｓｉｎｇ Ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ Ｒｅｃｅｐｔｉｖｅ Ｆｉｅｌｄ Ｈｉｓｔｏｇｒａｍｓ」、Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ、３６（１）、３１〜５２頁、２０００年を参照）。しかしながら、これらの手法は、計算量が多いか、又はハードウェアアクセラレータの使用を必要とする。
【００２４】
以下、本明細書は、ヒストグラム概念を拡張し、さらに簡単な計算を含み、より広い範囲の照明及び輝度変化の下で使用することができる種々の新しい手法、並びに幾何学的変換を説明する。
【００２５】
＜規格化ヒストグラム＞
【００２６】
上述した正規化ヒストグラム共通度は、テスト画像又は物体のスケール及び解像度の同時変化（即ちサイズが増加するか、又は減少するか）に影響されやすい。例えば、サイズ１０００ｘ１０００ピクセルの参照画像と、各方向に１０倍にスケーリングされ、１００ｘ１００ピクセルのサイズになったテスト画像とを考える。これら二つの画像間の正規化されたヒストグラム共通度Ｈは、低くなる。
【００２７】
本技術の一側面によれば、サイズの変化を考慮するために、共通度を計算する前に、ヒストグラムが規格化される。規格化の一手法は、ヒストグラムの合計カウント値を１単位（又は割合を示すよう１００などの一定の定数）に正規化することである。
【００２８】
規格化ヒストグラムの各ビンＣｉは、元のヒストグラムの対応するビンｃｉから以下のように計算される。
【数３】
ここで、Ｎは、ヒストグラムにおけるビンの合計個数である。図１及び２に示すヒストグラムは、規格化ヒストグラムである。
【００２９】
規格化ヒストグラムに対して計算されたヒストグラム共通度は、スケール及び解像度の同時変化（即ちサイズの変化）に対して不変である。上述の例では、規格化ヒストグラムを使用して計算されたヒストグラム共通度は、１００のままである。
【００３０】
＜照明及び輝度変化に対する感度の低減＞
【００３１】
上述したヒストグラム及びヒストグラム共通度は、輝度変化に対して影響されやすい。デジタル画像の場合には明度／コントラストの変化により、物理的物体の場合には照度変化により、輝度変化がもたらされ得る。
【００３２】
本技術の別の側面によれば、輝度の変化に対処する一つの手法は、３Ｄヒストグラムの輝度軸を粗く量子化することである。例えば、図１の輝度のビンの数を８の代わりに４に低減することができる。輝度を粗く量子化することは、輝度の小さい変化がヒストグラムのビンのカウント値を大きく変化させないという利点を有する。
【００３３】
照明及び輝度変化に対する感度を低減する別の手法は、輝度平面の２次微分値を計算し、第３の次元として（二つの反対色方向に加えて）、輝度の代わりに、当該２次微分値を使用することである。
【００３４】
２次微分値は、いくつかの方法で計算又は概算することができる。いくつかの方法は、ラプラシアンガウシアンオペレータ、ガウス関数の差（ＤｏＧ）法、ラプラシアンオペレータなど（本明細書ではそれぞれ「２次導関数」と呼ぶ）の使用を含む。以下に報告する結果には、ＤｏＧ演算が使用されている。
【００３５】
（種々の実施形態では、２次微分値よりも高次の微分値、及びそのような高次の微分値の概算値を使用することができる。）
【００３６】
２次導関数自体は、輝度平面に関するダイナミックレンジの変化といった輝度変化に対してある程度の影響を受ける。本技術の別の側面によれば、そのような変化に対する感度は、２次微分値の極性（符号）のみを考慮することによって、より低減される。さらに、比較的小さい量の２次微分値は、ノイズとみなされ、正及び負の微分値とは独立に取り扱うことができる。
【００３７】
小さい量は、閾値との比較により特定することができる。この場合には、閾値自体は、輝度平面のダイナミックレンジに応じて調整される。この演算は、輝度平面の２次微分値から三つの量子化レベル、即ち、閾値を超える負の２次微分値に対応する第１のレベル、量（絶対値）が閾値以下の２次微分値に対応する第２のレベル、及び閾値よりも大きい正の２次微分値に対応する第３のレベルを、生成する。
【００３８】
一例を図３に示す。これら三つの量子化レベルは、変更された「輝度」軸のビンを表現するのに使用することができる。
【００３９】
説明した特定の例（即ち、輝度の２次微分値が第３のヒストグラムの次元として使用される）は、エッジ境界に存在する色に関して画像／物体を特徴付ける表現クラスの一つであることが理解されよう。同様の効果をもたらすのに、他の様々な関数、オペレータ、及び変換を使用することができることが当業者には理解されよう。
【００４０】
ここで説明した構成は、物体形状の一定の概念をヒストグラムに導入する。さらに、このヒストグラム手法によりもたらされる安定性及び不変性／ロバスト特性が、維持される。その結果、認識は、色に加えてエッジ情報に依存する。（従来のヒストグラム手法の典型的な欠点は、従来のヒストグラム手法が、赤白チェック柄のコップと赤白チェック柄の皿とを識別することができないことがある点にある。これは、色の構成が同一であり得るからである。一方、ここで説明した構成は、エッジに関する情報の導入により容易に識別することができる。）
【００４１】
Ｓｈｉｍ及びＣｈｏｉは、方向性エッジ情報を有する色ヒストグラム（「Ｅｄｇｅ Ｃｏｌｏｒ Ｈｉｓｔｏｇｒａｍ ｆｏｒ Ｉｍａｇｅ Ｒｅｔｒｉｅｖａｌ」、Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ、９５７〜９６０頁、Ｖｏｌ．３、２００２年６月）を提案している。しかしながら、本手法は、方向性エッジ情報に依存しない。方向性エッジ情報は、回転などの幾何学的操作により変化する。本構成は、失敗することがない。（また、Ｓｈｉｍは三つの色ヒストグラムを計算したが、ここで説明した構成は一つの３Ｄヒストグラムのみを計算する。）
【００４２】
Ｓｃｈｉｅｌｅ(先に引用した)及びＧｅｕｓｅｂｒｏｅｋら（「Ｃｏｍｐａｃｔ Ｏｂｊｅｃｔ Ｄｅｓｃｒｉｐｔｏｒｓ ｆｒｏｍ Ｌｏｃａｌ Ｃｏｌｏｕｒ Ｉｎｖａｒｉａｎｔ Ｈｉｓｔｏｇｒａｍｓ」、Ｂｒｉｔｉｓｈ Ｍａｃｈｉｎｅ Ｖｉｓｉｏｎ Ｃｏｎｆｅｒｅｎｃｅ、ｖｏｌｕｍｅ３、１０２９〜１０３８頁、２００６年）は、ヒストグラム表現のために微分値を採用している。しかしながら、上述した表現は、より簡単であり、計算がより少なく、従って、携帯電話及び他の携帯デバイスへの実装により使用しやすい。
【００４３】
輝度の２次微分値に基づく三つの量子化レベルを使用することに対する代案は、ある閾値を上回る正の値と、同じ閾値（又は別の閾値）の負の値を下回る負の値との二つを使用することである。この代案は、ヒストグラム計算から画像のより平坦な領域を効果的に破棄し、エッジ領域のみを強調する。１軸に沿ったこの両極性の２次微分値、及び他の２軸に沿った反対色の使用により、ヒストグラム比較用の計算量も低減する。（しかし、この両極性手法の欠点は、両極性手法がクロッピング及びオクルージョンによる影響をより受け得る点であり、その理由は、画像の平坦部分が無視され、エッジ情報が優位になるからである。多くのアプリケーションにおいては、これは重要ではない。）
【００４４】
他の実装形態では、両極性手法は、先に説明した３レベル手法（例えば、画像の異なる部分）と組み合わせることができる。
【００４５】
＜不均一な量子化＞
【００４６】
不飽和の色では、反対色軸に含まれる大部分の情報は、小さいダイナミックレンジを有する。例えば、赤−緑軸を考察する。赤及び緑値が、０〜２５５の間にあるとき、ＲＧ値は、−１２７．５〜＋１２７．５の間にある。不飽和領域では、大部分の値がほぼ０である。これにより不飽和画像における識別性は低下する。本技術の別の側面によれば、この識別性の低下を克服するのに、色軸の不均一な量子化が使用される。例えば、ＲＧ軸は、０付近の値が細かく量子化され、一方では端部における値が粗く量子化されるように、ビンに分割することができる。このことは、ロバスト性（例えば正確にマッチングする数）を増大させることを示している。
【００４７】
図４Ａは、上述した図１Ａの画像に関する３Ｄヒストグラムを示し、Ｚ軸は輝度成分の３レベルのガウス関数の差であり、Ｘ及びＹ軸に沿って色成分が不均一に量子化されている。図４Ｂは、同様であるが、図２Ａの画像に対応する。
【００４８】
＜照度変化の下での色の不変性＞
【００４９】
照度変化は、色の変化をもたらし得る。色に関する照度変化の影響のシミュレーションを図５Ａ及び５Ｂに示す。左に元の画像、右に変化後の画像がある。人間の視覚系は、知覚した色が同じに見えるように照度変化を補償するのが得意である。しかし、デジタル系は、許容しない。
【００５０】
本技術の別の側面によれば、照度に対する感度は、輝度変化に対する感度がより低い色成分を用いて処理することにより、低減される。例えば、色相は、入射光の増大又は減少といった照度変化の下で不変のままである傾向がある。（色相は、Ｒ、Ｇ、Ｂ色チャネルに加えられる加法変化及び乗法変化に対して不変である。）ヒストグラムの次元の一つ又は二つとして色相を使用し、別の次元として輝度の両極性又は三つのレベルの２次微分値を使用することにより、照度変化の下でのロバスト性を提供することができる。
【００５１】
本技術の別の側面によれば、照度変化の下での安定性は、各ピクセルにおける最大値と最小値との間の差により反対色方向を正規化することによって、向上される。
ＭａｘＶａｌ＝Ｍａｘ（Ｒ，Ｇ，Ｂ）（各ピクセルにおいて）
ＭｉｎＶａｌ＝Ｍｉｎ（Ｒ，Ｇ，Ｂ）（各ピクセルにおいて）
ＲＧ’＝（Ｒ−Ｇ）／（ＭａｘＶａｌ−ＭｉｎＶａｌ）
ＢＹ’＝（Ｂ−０．５＊（Ｒ＋Ｇ））／（ＭａｘＶａｌ−ＭｉｎＶａｌ）
であるものとする。
【００５２】
この計算は、色相の計算と同様のものである（Ｍａｎｊｕｎａｔｈら、「Ｃｏｌｏｒ ａｎｄ Ｔｅｘｔｕｒｅ Ｄｅｓｃｒｉｐｔｏｒｓ」、ＩＥＥＥ Ｔｒａｎｓ．ｏｎ Ｃｉｒｃｕｉｔｓ ａｎｄ Ｓｙｓｔｅｍｓ ｆｏｒ Ｖｉｄｅｏ Ｔｅｃｈｎｏｌｏｇｙ、Ｖｏｌ．１１、Ｎｏ．６、７０３〜７１５頁、２００１年６月を参照）。（ＭａｘＶａｌ−ＭｉｎＶａｌ）による正規化により、色チャネルへの加法変化及び乗法変化に対して不変の色成分が生成される。
【００５３】
このような正規化のない図５の二つの画像間のヒストグラム共通度は、３７．８３であり、正規化があれば、ヒストグラム共通度は、８１．１０に増加する。
【００５４】
さらに、照度変化の下で色不変性を達成する別の手法は、直接の色の代わりに色のコントラストの評価尺度を使用することである。更に別の代案は、色平面における遷移（空間微分）を使用することである（上で引用したＧｅｕｓｅｂｒｏｅｋを参照）。遷移を得る簡単な方法は、上述の輝度平面上の２次微分値を使用することである。
【００５５】
＜ヒストグラム評価値及び特徴＞
【００５６】
先に説明したヒストグラム共通度評価値に加えて、物体又は画像をマッチングするのにヒストグラムを比較するときに役立つ可能性がある他の評価値及び特徴が存在する。これらの評価値のいくつかは、
・テスト及び参照の占有（即ち、非ゼロ個の）ビンの数<Ｎｔ及びＮｒ>
・両ヒストグラムに共通の占有ビンの数（ビン共通度）<Ｎｉ>
・両ヒストグラムを合わせた占有ビンの数（ビン和集合）<Ｎｕ>
・両ヒストグラムに共通のピクセルの数（ヒストグラム共通度）<Ｈ（ｔ，ｒ）>
・参照ヒストグラムに占めるテストヒストグラムの占有ビンの割合（ビン類似性及び部分集合）
・ヒストグラム共通度とテストヒストグラムの占有ビンの数との比率
・テストの非ゼロビン<Ｂｔ>
・参照の非ゼロビン
・参照画像の非ゼロビンの部分集合であるテスト画像の非ゼロビン<Ｂｔｒ>
・参照画像の非ゼロビンの部分集合であるテスト画像の非ゼロビンの数<Ｎｔｒ>
・テスト画像の非ゼロビンの部分集合である参照画像の非ゼロビン<Ｂｒｔ>
・テスト画像の非ゼロビンの部分集合となる参照画像の非ゼロビンの数<Ｎｒｔ>
【００５７】
これらの評価値を結合して（例えば、比率、差、積、和をとることにより）、他の評価値を得ることができる。
【００５８】
本明細書に説明する構成を通して、ロバスト性を増大させるために、寄与がわずかであるビン（例えば１％、０．３％、０．１％、０．０３％、などよりも小さいビン計数）は、占有されないもの（即ちゼロビンのカウント値を有するもの）として取り扱うことができる。
【００５９】
＜ヒストグラムに関する集合演算＞
【００６０】
上述したように、ヒストグラム共通度は、二つのヒストグラムを比較する集合演算である。ヒストグラム共通度は、ヒストグラムのビンのコンテンツに対して演算を行うものである。本技術の別の側面によれば、共通度は、各ヒストグラム内の非ゼロビンの組に対して計算することもできる。部分集合、差集合などの他の集合演算は、物体及び画像のマッチング用にヒストグラムを比較することにおいても役立つこともわかっている。このことを以下に更に説明する。
【００６１】
ヒストグラムに関する集合演算を使用する一例は、バックグラウンドのコンテンツをフィルタで除去することである。テスト画像及び参照画像を比較するとき、バックグラウンドのコンテンツに関連する色は、参照画像内に存在しないものと仮定することができる。テスト画像の非ゼロビンの部分集合となる参照画像の非ゼロビンのみを考慮することにより、バックグラウンドをフィルタ除去することができる。（以下の図６の説明も参照。）
【００６２】
別の例は、類似していない二つの画像の場合である。この場合には、これらの画像の非ゼロビンの共通集合は小さく、相対的に差集合は大きい。
【００６３】
＜多次元ヒストグラム＞
【００６４】
上述した輝度及び反対色方向の構成は、多次元ヒストグラムを生成するのに使用することができる表現の一例にすぎない。ＹＵＶ、ＹＣｂＣｒ、ＨＳＶ、ＨＳＬ、Ｌａｂなどの他の色空間を使用することもできる。また、ヒストグラムは、追加の次元に沿ったエッジ又は他の空間統計量などの特徴を含むことにより、２より大きい次元を含むことができる（上で引用したＳｃｈｉｅｌｅを参照）。（いくつかの実施形態では、１又は２次元を使用することもできる。）
【００６５】
＜幾何学的変換の下での認識＞
【００６６】
以下のセクションは、様々なタイプの幾何学的変換の下で認識及びマッチングのために、多次元ヒストグラムに基づく画像及び物体の特徴付けをどのように使用することができるかを説明する。
【００６７】
＜平行移動＞
【００６８】
（クロッピングのない）平行移動は、例示の３Ｄヒストグラムに影響を及ぼさず、したがって、３Ｄヒストグラムは平行移動に対して不変である。規格化ヒストグラム共通度評価尺度自体は、元の画像に対して平行移動した画像をマッチングするのに適する。
【００６９】
平行移動用のテストは、ヒストグラム共通度が、マッチング閾値Ｔｍ（例えば１００％の最大値に正規化された規格化ヒストグラム共通度において７５％）よりも大きいか否かをチェックすることになる。
【００７０】
＜クロッピング＞
【００７１】
画像がクロッピングを受けると、クロッピングされた画像は、元の画像の特徴の一部を保持する。その際、クロッピングされた画像の多数（しばしば大多数）の非ゼロビンは、元の画像の非ゼロビンの部分集合となるはずである。クロッピングのチェックは、Ｎｔｒ＞Ｔｃ×Ｎｔであるか否かをテストすることとなる。ここで、Ｔｃは、許容することができるクロッピング量を特定するクロッピング閾値である。
【００７２】
クロッピングされた画像のビンの値は、元の画像の対応するビンと任意の関係を有することができる。しかし、規格化ヒストグラム共通度が設定閾値を超えるか否かをチェックすることにより、ヒストグラム共通度に基づく追加のチェックを実行することもできる。
【００７３】
＜回転＞
【００７４】
例示の３Ｄヒストグラムは、クロッピングを含まない場合に、回転による影響を受けない。ヒストグラム共通度評価尺度は、そのような場合に適している。バックグラウンドが、参照画像又はテスト画像に類似する特徴を共有する場合に、バックグラウンドコンフュージョン（即ち参照画像内に存在しないバックグラウンドのコンテンツ）は、回転の下でのヒストグラム共通度に悪影響を及ぼすことに留意されたい。テスト画像内に存在する参照画像のビンのみを考慮することにより、バックグラウンドの影響を克服することができる（例えば以下のズームアウトの説明を参照）。
【００７５】
＜スケール変化＞
【００７６】
スケール変化の場合には、画像は、元の画像と比較ではサイズにおいて拡大又は縮小される。三つの異なる場合を以下に説明する。スケール及び解像度の何れもが変化するもの（即ち、画像がスケーリングされるにつれて、画像サイズがピクセルについても変化する）、画像コンテンツ（即ち画像内の物体）がスケールアップ（即ちズームイン及びクロッピング）されるが、得られた画像サイズがピクセル数では同じままであるもの、並びに、画像コンテンツがスケールダウン（即ちズームアウト及び新しいバックグラウンドの追加）されるが、得られた画像サイズがピクセル数では同じままであるものである。
【００７７】
＜スケール及び解像度の変化（画像サイズ変化）＞
【００７８】
画像サイズを変化させるスケール変化は、画像ヒストグラム内のピクセルの数を、参照ヒストグラム内のピクセルの数と一致させなくする。先に説明したように、両ヒストグラムを規格化することにより、この不一致を補償することができる。例えば、ヒストグラムビンの合計が１００になるように、ヒストグラムのビンを正規化することができる。この規格化は、画像サイズの変化を補償する。
【００７９】
＜画像サイズを一定に維持するズームイン（拡大及びクロッピング）＞
【００８０】
この場合には、画像コンテンツが拡大される（即ち画像内の物体がより大きく見える）が、画像サイズは、元のサイズの外側の画像コンテンツをクロッピングすることにより不変に保たれる。クロッピングが含まれるので、元の画像の色の一部分が欠落する。しかし、ズーム／クロッピングされた画像内に存在する多数（しばしば大多数）の色は、元の画像内にも存在するはずである。この場合のテストは、テスト画像の大多数の非ゼロビンが、参照画像内の非ゼロビンの部分集合となるか否かをチェックすることである。また、部分集合ビンの少なくともいくつかについては、ビンのカウント値は、参照画像の対応するカウント値よりも多くなるはずである。このことにより、拡大が確認される。回帰技術を使用して、倍率（又はズーム値）（即ち、最小２乗法の意味においてテストビンのカウント値と参照ビンのカウント値との間の関係を表わる倍率がどうなるか）を求めることができる。
【００８１】
＜画像サイズを一定に維持するズームアウト（縮小及びバックグラウンド）＞
【００８２】
この場合には、元の画像のサイズが縮小され、元の画像コンテンツは、新しいバックグラウンドのコンテンツに取り囲まれる。
【００８３】
ズームアウトは、新しい（ダウンサンプリングされた）ピクセル値を得るために平均化といった演算を必要とすることがある。この演算は、参照画像内に厳密には見つけられない新しい色を導入し得る。しかしながら、比較的少数のビンに色データを量子化することにより、これら新しい中間色は、参照画像内に既に存在しているビンに含まれることになる。
【００８４】
ズームアウトにより元の画像のコンテンツに類似しない新しいバックグラウンドピクセルが導入される場合に（一般的にはこの場合となる）、新しいバックグラウンド領域は、参照画像の非ゼロビンの部分集合であるテスト画像のビンのみを考慮することにより、効果的にフィルタ除去することができる。
【００８５】
マッチングする参照画像に関して、参照画像の多数（しばしば大多数）の非ゼロビンは、テスト画像内でも非ゼロとなるはずである（クロッピング部分を考慮する余地が認められ得る）。その際、規格化ヒストグラム共通度は、これらのビン（即ち、テスト及び参照の何れにも共通するビン）のみを使用して計算することができる。この共通度値を閾値と比較することができる。倍率（又はズーム値）は、対応するビンの値と比較することにより回帰によって求めることができる。
【００８６】
更なる絞込みは、更なる分析のために、（例えばズームアウトされた）テスト画像からピクセル候補領域を特定し、それを空間的に分離することである。この絞込みは、参照画像の非ゼロビンの部分集合であるテスト画像のビンを参照して再び行うことができる。
【００８７】
図６を参照すると、元の画像（全てが赤いピクセル「Ｒ」）は、ズームアウトされ、新しいバックグラウンドピクセル（元の画像内のビンに偶然にマッチングする唯一の赤いピクセルＲを除く「他」を意味する「Ｏ」のラベルが付いた）に取り囲まれる。参照画像の非ゼロビンの部分集合であるテスト画像のビンのみを考慮することは、図６の左下に示すピクセルの組１２を特定するのに役立つ。元の画像に対応するピクセルは、ピクセル領域内で隣接すべきであり、その結果、隣接していない異常値（例えばピクセル１３）のみを無視することができる。このことにより、テスト画像から図６の右下に示す部分１４を効果的に分離する。その際、元の画像にマッチングするために、（例えば、本明細書に説明したヒストグラム技術、又はＳＩＦＴなどの他の技術により）この部分をチェックすることができる。
【００８８】
＜視野＞
【００８９】
ヒストグラムは、視点の変化により生じる視野の変化と共に緩やかに変化する。その結果、ヒストグラムに基づくマッチングは、大部分の視野変換の下でロバスト性がある。
【００９０】
＜幾何学的変換及び他の変形の下での結果＞
【００９１】
図７は、変換／変形された画像に対する上述の技術のいくつかを使用したマッチングの結果を示す。テスト画像は、参照画像の一つに対する様々な変換及び／又は変形からなる。各画像に対して生成されたヒストグラムは、１軸に沿った輝度の閾値処理された３レベルの２次微分値（ガウス関数の差）と、他の２軸に沿った（不均一に１６個のビンに量子化された）ＲＧ及びＢＹ要素とからなる。
【００９２】
「共通度」評価尺度は、テスト画像と参照画像との間の規格化ヒストグラム共通度を示す。「整合性」評価尺度は、参照画像の占有ビンの部分集合であるテスト画像の占有ビンの割合、及びテスト画像の占有ビンの部分集合である参照画像の占有ビンの割合の最大値を示す。特定の変換が、各テスト画像の下に列挙されている。
【００９３】
共通度評価値及び整合性評価値は、正確にマッチングする場合には高くなることを結果が示している。テスト画像を分類するために、共通度評価値及び整合性評価値のいずれか、及び／又は双方に一以上の閾値を適用することができる。例えば、共通度スコアが６０よりも大きく、整合性スコアが９０よりも大きい場合に、テスト画像の一部分又は全体が、参照画像とマッチングする可能性がある。共通度スコアが４５よりも小さいか、又は整合性スコアが８０よりも小さいとき、マッチングしない可能性がある。他の場合を不定状態に割り当てることができる。
【００９４】
これらの評価値の組合せ、例えば、それらの積又は多項式合成といった組合せを計算することもでき、閾値に対してテストすることができる。例えば、共通度と整合性との積が４０００よりも大きいとき、テスト画像の一部分又は全体が、参照画像とマッチングする可能性がある。積が３５００よりも小さいとき、マッチングがしない可能性がある。ここでも、他の場合を不定状態に割り当てることができる。
【００９５】
当然に、他の評価値及び他のヒストグラムを使用することができる。
【００９６】
特定の用途によっては、そのようなテストの結果は、整合の特定に対する決定的な回答を与えなくてもよい。しかし、このプロセスは、テスト画像と整合し得る参照画像の母集団を限定するスクリーニング関数として常に役立つ。次いで、回答を更に絞り込むために、他の技術を使用することができる。（或いは、そのような別の技術を最初に適用することができ、次いで、最終的な回答を得るのに本技術を使用することができる。）
【００９７】
＜更なる拡張＞
【００９８】
これまで説明した概念は、用途による要求に適応するよう、又はロバスト性を向上させるよう、更に拡張することができる。そのようないくつかの拡張を以下に説明する。
【００９９】
＜テスト画像及び参照画像のサブ画像への分割＞
【０１００】
これまで、一つのヒストグラムをテスト画像から計算し、一つのヒストグラムを参照画像から計算してきた。その代わりに、例えば、画像をサブブロック若しくは他の適当な区画に分割するか、又は画像分割技術を使用することにより（例えば、クラスタ形成、エッジ検出、領域成長、分水界変換などを含む方法により）、画像をより小さいサブ画像、又はサブ領域に分割することができる。そして、これらのサブ画像を、マッチング及び認識に使用することができる。
【０１０１】
これらの手法の多くは、形状及び構造に関する一部の情報をマッチングプロセスに導入し、マッチングの信頼性を向上させることができる。例えば、二つの画像の共通度が大きく、これらの画像間のいくつかのサブブロックも共通度が大きい場合を考える。このとき、マッチングが正確である確率が高い。評価値及び閾値の組合せに関して上述の構成を、ここでも使用することができる。
【０１０２】
＜粗から微細への戦略＞
【０１０３】
マッチング用の探索の際に、粗から微細への戦略を使用することができる。この戦略では、複数のヒストグラムが、各参照画像用のデータベース内に記憶される。最初にヒストグラムの次元の粗い量子化を使用し、次いで連続的に微細な量子化を使用することにより、複数のヒストグラムが形成される。マッチング用の探索は、最初に粗い量子化ヒストグラムを使用して探索空間を縮小し、次いで次第に微細な量子化を使用してマッチングを絞り込むことにより進行する。
【０１０４】
＜ヒストグラム情報と他の認識特徴との組合せ＞
【０１０５】
ヒストグラムに基づくマッチングは、より良好な識別を可能とするよう、他の認識特徴と組み合わせることができる。例えば、特徴点（Ｓａｌｉｅｎｔ Ｐｏｉｎｔｓ）、局所記述子、ＳＩＦＴ、形状、構造、及びテクスチャを明示的に使用して、近いヒストグラム間の曖昧さを除去することができる。ヒストグラム表現自体の中で、そのような特徴を使用することもできる。或いは、ヒストグラムを使用して探索空間を大幅に縮小することができ、次いで、他の技術を使用して最終的な認識又は特定を行うことができる。
【０１０６】
＜ビデオへの適用＞
【０１０７】
粗い量子化ヒストグラムの時間変化により、ビデオを特徴付けることができる。例えば、輝度及び二つの反対色軸のそれぞれについて二つのビンを考える。このとき、ビデオの各フレームは、八つのビンにより特徴付けることができる。
【０１０８】
一実装形態では、ビンのカウント値は、記憶することができ、それによってビデオを認識することができるフィンガプリントとして機能することができる。或いは、ビンのカウント値を記憶する代わりに、前のフレームのカウント値との差を記憶することができる。或いは、差の符号のみを記憶することができる。或いは、各ビンを、一つ又はいくつかの先行し連続するフレーム内の対応するビンと比較し、時間コンテキストにおいてビデオフレームを表すビット列を導出することができる。そして、ビデオのマッチング又は特定用に、これらのビット列又はシグネチャを使用することができる。
【０１０９】
＜探索空間縮小＞
【０１１０】
大規模認識システムでは、特徴点の局所記述子、ＳＩＦＴ、形状、テクスチャといった他の認識特徴を補完するのに、本発明の技術を使用することができる。他の認識特徴のいくつかをマッチングする探索空間を縮小することができる高速ルックアップ（又は二分探索）に、ヒストグラムマッチング技術の変更形態を使用することができる。ヒストグラムは、探索空間縮小のために使用して、各軸上に少数のビンで粗く構築することができる。
【０１１１】
＜ヒストグラムビンインデックスを使用したルックアップ＞
【０１１２】
この手法では、テスト画像の非ゼロビンのインデックスを使用して、対応するビンが非ゼロである参照データベース内の画像を分離する。一例として、８個のビンを有する１Ｄヒストグラムを考える。最初の三つのビンが、テスト画像については非ゼロであると仮定する。このとき、最初の三つの非ゼロビンを有する参照データベース内の画像をルックアップすることにより、マッチング用の参照データベースを縮小することができる。この概念は、一般性を失うことなく、３Ｄヒストグラム（又は任意の次元のヒストグラムでも）に拡張することができる。
【０１１３】
＜２値参照＞
【０１１４】
高速探索空間縮小の別の手法は、ビンの占有状態に基づいて、ビンの位置を２値化することである。８個のビンを有する１Ｄヒストグラムの上記の例では、各ビンを２値、即ち、ビンが占有されるとき（ビンのカウント値、非ゼロ又は上記のいくつかの占有閾値）には１、その他の場合は０で表現することができる。そして、上記のルックアップの例では、最初の三つの位置に値１を有する参照データベース内の全ての画像のルックアップを高速で行うために、８ビットのベクトルを使用することができる。この概念を多次元ヒストグラムに拡張することができる。例えば、ヒストグラムが、２次微分値輝度情報に４つのビン、色方向にそれぞれ８つのビンを含むとき、２０ビットのベクトルによって、非ゼロビン位置を表現することができる。ロバスト性を改善するために、占有ビンに隣接するビンの位置に値１のラベルを付けることができ、（例えば、ノイズ又は他の環境による）隣接するビンに入る可能性がある境界の場合の量子化値が失われないことを確実にする。
【０１１５】
＜バックグラウンドコンフュージョン＞
【０１１６】
探索空間縮小技術は、バックグラウンドコンフュージョンが存在する場合に、機能停止する傾向がある。バックグラウンド色及び特徴は、参照画像内には存在しない。バックグラウンドに対応するビンを含まない参照画像を無視すると、マッチングが失敗する。この課題に対処する一つの解決策は、上述したように、画像をより小さいサブ領域に分割し、バックグラウンドを含まない少なくとも一つのサブ領域が確実に存在するようにすることである。
【０１１７】
＜ＳＩＦＴ＞
【０１１８】
説明したように、他の画像認識技術と共に、本技術を使用することができる。そのような一つの普及した技術がＳＩＦＴである。
【０１１９】
ＳＩＦＴは、Ｓｃａｌｅ−Ｉｎｖａｒｉａｎｔ Ｆｅａｔｕｒｅ Ｔｒａｎｓｆｏｒｍ（スケール不変特徴変換）の略語で、Ｄａｖｉｄ Ｌｏｗｅにより開拓されたコンピュータビジョン技術であり、「Ｄｉｓｔｉｎｃｔｉｖｅ Ｉｍａｇｅ Ｆｅａｔｕｒｅｓ ｆｒｏｍ Ｓｃａｌｅ−Ｉｎｖａｒｉａｎｔ Ｋｅｙｐｏｉｎｔｓ」、Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ、６０、２（２００４）、９１〜１１０頁と、「Ｏｂｊｅｃｔ Ｒｅｃｏｇｎｉｔｉｏｎ ｆｒｏｍ Ｌｏｃａｌ Ｓｃａｌｅ−Ｉｎｖａｒｉａｎｔ Ｆｅａｔｕｒｅｓ」、Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ、Ｃｏｒｆｕ、Ｇｒｅｅｃｅ（１９９９年９月）、１１５０〜１１５７頁と、米国特許第６，７１１，２９３号とを含むＤａｖｉｄ Ｌｏｗｅの様々な論文に記載されている。
【０１２０】
ＳＩＦＴは、局所画像特徴の特定、記述、及び後続の検出によって機能する。ＳＩＦＴの特徴は、局所的であり、特定の着目点における物体の出現に基づくものであり、画像スケール、回転、及びアフィン変換に対して不変である。ＳＩＦＴの特徴は、照度変化、ノイズ、及び視点のいくつかの変化に対してもロバスト性がある。これらの特性に加えて、ＳＩＦＴの特徴は、独特であり、比較的抽出しやすく、不一致の確率が低い正確な物体識別を可能にし、局所特徴の（大きい）データベースに対してマッチングするのが容易である。ＳＩＦＴ特徴の組による物体記述は、部分的なオクルージョンに対してもロバスト性があり、位置及び姿勢を計算するために、物体からのわずか三つのＳＩＦＴ特徴で十分であり得る。
【０１２１】
この技術は、参照画像内のキーポイントである局所画像特徴を特定することにより開始する。この技術は、異なるスケール（解像度）で画像とガウスぼかしフィルタとを畳み込み、連続するガウスぼかし画像間の差を求めることにより行われる。キーポイントは、複数のスケールにおいて生じるガウス関数の差の最大値又は最小値を有する画像特徴である。（ガウス関数の差によるフレームの各ピクセルが、同じスケールにおける八つの隣接ピクセル、及び複数の隣接スケール（例えば他の９つのスケール）の各々の対応するピクセルと比較される。ピクセル値がこれら全てのピクセルからの最大値又は最小値であるとき、このピクセル値が候補キーポイントとして選ばれる。
【０１２２】
（ここで説明した手順は、画像の局所スケールラプラス変換の空間スケール極値を検出するブロブ検出法であることが理解されよう。ガウス関数の差の手法は、ピラミッド配置で表現される、そのようなラプラス演算の概算値である。）
【０１２３】
上記の手順は、例えば、コントラストが低い（従って、ノイズに影響を受けやすい）か、又はエッジに沿って不十分に求められた位置を有することにより、不適当な多くのキーポイントを通常特定する（ガウス関数の差は、エッジに沿った応答が強く、多くの候補キーポイントをもたらすが、これらの候補キーポイントはノイズに対してロバスト性がない）。これらの信頼性のないキーポイントは、正確な位置、スケール、及び主曲率に関する近傍データに候補キーポイントを詳細にフィッティングすることにより、スクリーニング除去される。この方法は、コントラストが低いか、又はエッジに沿って不十分に位置判定されるキーポイントを棄却する。
【０１２４】
より詳細には、このプロセスは、キーポイント位置をより正確に決定するために、各候補キーポイントに関して近傍データを内挿することにより開始する。このプロセスは、最大／最小位置の精密な推定量を決定するために、キーポイントを原点とするテイラー展開により、行われることが多い。
【０１２５】
２次のテイラー展開の値を使用して、低コントラストのキーポイントを特定することもできる。コントラストが閾値（例えば０．０３）よりも低いとき、キーポイントは無視される。
【０１２６】
強いエッジ応答を有するが、局所性が不十分であるキーポイントを除去するために、コーナー検出手順の変形が適用される。つまり、この手順は、エッジにわたって主曲率を計算するステップと、端部に沿って主曲率を比較するステップと、を含む。この手順は、２次ヘッセ行列の固有値を求めることにより行われる。
【０１２７】
不適当なキーポイントが破棄されると、残ったキーポイントが、局所画像勾配関数によって方向（Ｏｒｉｅｎｔａｔｉｏｎ）について評価される。勾配の大きさ及び方向は、ガウスぼかし画像内のキーポイントの周りの近傍領域内の全てのピクセルに関して（そのキーポイントのスケールで）計算される。そして、３６個のビンを有する方向ヒストグラムが集計される。なお、各ビンは、１０段階の方向を含む。近傍の各ピクセルは、その勾配の大きさと、キーポイントのスケールの１．５倍のσを有するガウス関数により重み付けされた寄与率でヒストグラムに寄与する。このヒストグラム内のピークは、キーポイントの主方向を規定する。この方向データにより、ＳＩＦＴは、回転に対するロバスト性を達成する。その理由は、主方向に対してキーポイント記述子を表現することができるからである。
【０１２８】
上述のことから、異なるスケールである複数のキーポイントは、それぞれ対応する方向を用いて特定される。このデータは、画像平行移動、スケーリング、及び回転に対して不変である。そして、各キーポイントに関して、１２８個の要素記述子が生成され、照度及び３Ｄ視点に対するロバスト性を可能にする。
【０１２９】
このオペレーションは、ここで検討した方向評価手順に類似している。キーポイント記述子は、（４ｘ４）近傍ピクセル上の方向ヒストグラムの組として計算される。方向ヒストグラムは、キーポイント方向に関連しており、方向データは、キーポイントスケールにスケールが最も近いガウス画像から生じる。上述したように、各ピクセルの寄与率は、勾配の大きさと、キーポイントのスケールの１．５倍のσを有するガウス関数により重み付けされる。ヒストグラムはそれぞれ、８個のビンを含み、各記述子は、キーポイントの周りに４×４配列の１６個のヒストグラムを含む。このことは、（４×４×８＝１２８要素）を有するＳＩＦＴ特徴ベクトルにつながる。このベクトルは、照度変化に対する不変性を向上させるために正規化される。
【０１３０】
上述の手順は、参照データベースをコンパイルするために、トレーニング画像に適用される。そして、未知の画像が、キーポイントデータを生成するために上述のように処理され、データベース内の最もマッチングする画像が、ユークリッド距離のような評価尺度により特定される。（通常は、純粋なユークリッド距離計算の代わりに、「ｂｅｓｔ−ｂｉｎ−ｆｉｒｓｔ」アルゴリズムを使用して、数オーダー規模の速度改善を達成する。）誤判定可を避けるために、最適マッチング率の距離スコアが、次の最適マッチング率の距離スコアに近いとき、例えば２５％であるとき、「不一致」出力が生成される。
【０１３１】
更に性能を改善するために、画像をクラスタリングによりマッチングすることができる。この方法は、同じ参照画像に属する特徴を特定し、クラスタリングされていない結果を偽として無視することができる。ハフ変換を使用して、同じ物体姿勢に投票する特徴のクラスタを特定することができる。
【０１３２】
次世代携帯電話の実装に適した、ＳＩＦＴ手順を行う特定のハードウェア実施形態を説明する記事は、Ｂｏｎａｔｏら、「Ｐａｒａｌｌｅｌ Ｈａｒｄｗａｒｅ Ａｒｃｈｉｔｅｃｔｕｒｅ ｆｏｒ Ｓｃａｌｅ ａｎｄ Ｒｏｔａｔｉｏｎ Ｉｎｖａｒｉａｎｔ Ｆｅａｔｕｒｅ Ｄｅｔｅｃｔｉｏｎ」、ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｃｉｒｃｕｉｔｓ ａｎｄ Ｓｙｓｔｅｍｓ ｆｏｒ Ｖｉｄｅｏ Ｔｅｃｈ、Ｖｏｌ．１８、Ｎｏ．１２、２００８年である。
【０１３３】
ＳＩＦＴ技術を実行する別のハードウェアアーキテクチャは、Ｓｅら、「Ｖｉｓｉｏｎ Ｂａｓｅｄ Ｍｏｄｅｌｉｎｇ ａｎｄ Ｌｏｃａｌｉｚａｔｉｏｎ ｆｏｒ Ｐｌａｎｅｔａｒｙ Ｅｘｐｌｏｒａｔｉｏｎ Ｒｏｖｅｒｓ」、Ｐｒｏｃ．ｏｆ Ｉｎｔ．Ａｓｔｒｏｎａｕｔｉｃａｌ Ｃｏｎｇｒｅｓｓ（ＩＡＣ）、２００４年１０月に記載されている。
【０１３４】
ＳＩＦＴは、おそらくロバスト性のある局所記述子を生成する最もよく知られた技術であるが、用途によっては、略適当であり得る他の技術が存在する。これらの技術は、ＧＬＯＨ（Ｍｉｋｏｌａｊｃｚｙｋら、「Ｐｅｒｆｏｒｍａｎｃｅ Ｅｖａｌｕａｔｉｏｎ ｏｆ Ｌｏｃａｌ Ｄｅｓｃｒｉｐｔｏｒｓ」、ＩＥＥＥ Ｔｒａｎｓ．Ｐａｔｔｅｒｎ Ａｎａｌ．Ｍａｃｈ．Ｉｎｔｅｌｌ．、Ｖｏｌ．２７、Ｎｏ．１０、１６１５〜１６３０頁、２００５年を参照）と、ＳＵＲＦ（Ｂａｙら、「ＳＵＲＦ：Ｓｐｅｅｄｅｄ Ｕｐ Ｒｏｂｕｓｔ Ｆｅａｔｕｒｅｓ」、Ｅｕｒ．Ｃｏｎｆ．ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ（１）、４０４〜４１７頁、２００６年と、Ｃｈｅｎら、「Ｅｆｆｉｃｉｅｎｔ Ｅｘｔｒａｃｔｉｏｎ ｏｆ Ｒｏｂｕｓｔ Ｉｍａｇｅ Ｆｅａｔｕｒｅｓ ｏｎ Ｍｏｂｉｌｅ Ｄｅｖｉｃｅｓ」、Ｐｒｏｃ．ｏｆ ｔｈｅ ６ｔｈ ＩＥＥＥ ａｎｄ ＡＣＭ Ｉｎｔ．Ｓｙｍｐ．Ｏｎ Ｍｉｘｅｄ ａｎｄ Ａｕｇｍｅｎｔｅｄ Ｒｅａｌｉｔｙ、２００７年と、Ｔａｋａｃｓら、「Ｏｕｔｄｏｏｒｓ Ａｕｇｍｅｎｔｅｄ Ｒｅａｌｉｔｙ ｏｎ Ｍｏｂｉｌｅ Ｐｈｏｎｅ Ｕｓｉｎｇ Ｌｏｘｅｌ−Ｂａｓｅｄ Ｖｉｓｕａｌ Ｆｅａｔｕｒｅ Ｏｒｇａｎｉｚａｔｉｏｎ」、ＡＣＭ Ｉｎｔ．Ｃｏｎｆ．ｏｎ Ｍｕｌｔｉｍｅｄｉａ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖａｌ、２００８年１０月とを参照）とを含む。
【０１３５】
上述したように、本ヒストグラム技術は、ＳＩＦＴ又はこれら他の技術と共に使用することができる。
【０１３６】
＜結論的見解＞
【０１３７】
上述のことから、多次元ヒストグラムに基づく様々な技術は、物体及び画像を特徴付け、マッチングし、認識するために使用することができることが理解されよう。これらの技術は、幾何学的変換、並びに輝度変化及び照度変化の下でロバスト性を有することができる。これらの技術は簡単な計算を含むので、これらの構成は、携帯電話及び他の携帯デバイス、又はエンベデッドシステムに効率的に実装することができる。
【０１３８】
例示的な実施形態及び構成を参照して我々の技術の原理を説明し、図示してきたが、詳細な実装形態は、例示的なものにすぎず、我々の技術範囲を限定するものとみなすべきでないことが理解されよう。
【０１３９】
例えば、詳細な技術を、空間（ピクセル）ドメインで表現される画像データのコンテキストで説明したが、他のドメインで表現される画像情報に同じ技術を適用することができる。異なる色軸及び／又は輝度軸のそれぞれに関して、ＦＦＴデータを生成することができるが、説明した技術は、得られた空間周波数ドメインデータに適用することができる。（参照することにより援用する文献は、他の様々なドメインを説明している。）
【０１４０】
同様に、様々なフィルタ技術によりフィルタリングすることを含む、他の方法で処理された画像データに、本発明の技術を適用することができる。（サンプルフィルタリング演算は、メジアン、ラプラシアン、ウィーナ、ソーベル、ハイパス、ローパス、バンドパス、ガボール、符号などを含む。Ｄｉｇｉｍａｒｃの特許、米国特許第６，４４２，２８４号、第６，４８３，９２７号、第６，５１６，０７９号、第６，６１４，９１４号、第６，６３１，１９８号、第６，７２４，９１４号、第６，９８８，２０２号、第７，０１３，０２１号、及び第７，０７６，０８２号は、そのような様々なフィルタを示す。）テスト画像又は参照画像は、様々な幾何学的変換を受ける可能性もある。米国特許第７，５０８，９７８号に説明されるように、非平面の原型からブックページの平面スキャンを行うときにＧｏｏｇｌｅにより使用されるデワープ処理構成が、例示的なものである。
【０１４１】
本明細書は、参照しやすいようにセクション見出しを使用してきたが、セクション見出しは、開示した技術の適用性又は汎用性を限定するものとみなすべきでない。
【０１４２】
輝度軸をしばしば参照してきた。輝度自体を使用する必要がないことを理解されたい。軸は、ガウス関数の差といった輝度情報から導出された値に対応することができる。当然、他の実装形態では、輝度軸を全く使用しない場合があり、即ち、別の画像パラメータで代用することができる。
【０１４３】
本明細書の焦点は画像（従ってビデオも）にあるが、同じヒストグラム技術及び比較基準値の多くが、同様にオーディオ処理及び認識に関連する。従って、本明細書は、オーディオアナログから、説明した画像構成まで教示するものとして読むべきである。
【０１４４】
本明細書に個々に説明した特徴は、説明した特徴及び構成の他のものと組み合わせて使用することができることが理解されよう。同様に、本明細書に説明した特徴は、参照により組み込まれる特許明細書に記載された技術と組み合わせて使用することができる（逆も同様）。
【０１４５】
本発明の技術は、様々な画像応答システムに使用することができる。実例は、Ｄｉｇｉｍａｒｃの米国特許第６，９４７，５７１号、米国特許出願公開第２００６０２４０８６２号及び第２００６００１２６７７号（どちらもＧｏｏｇｌｅ）、第２００７０１７５９９８号、第２００２０１０２９６６号（どちらもＬｅｖ）、第２００６００５６７０７号（Ｎｏｋｉａ）、第２００６００２６１４０号（ＥｘＢｉｂｌｉｏ）、第２００３００８３０９８号（Ｃａｎｏｎ）、第２００１０００１８５４号（ＡｉｒＣｌｉｃ）、米国特許第７，０１６，５３２号（Ｅｖｒｙｘ）、第６，４９１，２１７号（Ｐｈｉｌｉｐｓ）、及び本明細書で参照する他の特許明細書に説明される。
【０１４６】
詳細な技術は、ロバスト性のある画像のフィンガプリント処理の形態とみなすことができる。コンテンツのフィンガプリント処理及び関連するシステムに関する追加の情報は、例えば、米国特許出願公開第２００５０００４９４１号、第２００５０１０８２４２号、第２００６００４１７５３号、第２００６００７５２３７号、第２００６０２１８１２６号、第２００７００７１３３０号（全てＰｈｉｌｉｐｓ）、第２００７０２３９７５６号（Ｍｉｃｒｏｓｏｆｔ）、第２００７０２３７３６４号（Ｆｕｊｉ Ｐｈｏｔｏ Ｆｉｌｍ）、米国特許第７，１３０，４６６号（Ｃｏｂｉｏｎ）、第７，１９４，７５２号（Ｋｅｎｙｏｎ）、米国特許出願公開第２００７０２５３５９４号（Ｖｏｂｉｌｅ）、第２００２００４４６５９号（ＮＥＣ）、及び第２００７０２５０７１６号（Ｄｉｇｉｍａｒｃ）特許明細書に見られる。
【０１４７】
補完技術であるデジタル透かしデコーディングを、いくつかの実施形態に使用することができる。透かしエンコーディング／デコーディングの技術は、例えば、Ｄｉｇｉｍａｒｃの米国特許第６，５９０，９９６号及び第６，１２２，４０３号、並びに２００８年５月２２日に出願したＳｈａｒｍａらによる米国特許仮出願第１２／１２５，８４０号に記載されている。デジタル透かしとフィンガプリントとを組み合わせた使用は、例えば、Ｄｉｇｉｍａｒｃの米国特許第７，２８９，６４３号に記載されている。
【０１４８】
幾何学的校正データは、一般にデジタル透かしにより伝えられる。デジタル透かしは、画像のアフィン変換及び他の変換を容易に特定し、必要に応じて、補償することを可能とする。そのような構成は、例えば、米国特許第６，６１４，９１４号、第６，５８０，８０９号、第７，０７２，４９０号、及び第７，３１９，７７５号、並びに米国特許出願公開第２００６００３１６８４号に記載されている。米国特許第６，９５９，０９８号は、可視画像特徴（例えば、直線的な物体の端部）と共に、そのような透かし校正信号により変形をどのように特徴付けることができるかを教示している。そのようなアフィン変換情報から、携帯電話の撮像素子に対する透かし物体の６Ｄ位置を決定することができる。
【０１４９】
いくつかの実施形態では、視覚刺激に対する応答は、携帯電話カメラにより取得された画像データ上の、携帯電話スクリーン上にもたらされるグラフィックオーバーレイを含むことができる。オーバーレイは、画像データの特徴と共に幾何学的に校正され、画像に示される物体のアフィン変形に対応してアフィン変形され得る。そのような技術は、例えば、Ｄｉｇｉｍａｒｃの米国特許出願公開第２００８０３０００１１号にさらに記載されている。
【０１５０】
（例えば、テスト画像と参照画像／元の画像との）画像マッチングを最も多く参照した。しかし、テスト画像内に取得された物体をマッチングするのに、同じ構成を使用することができることを当業者には理解されよう。従って、画像（又は画像データ）のマッチングを参照することは、物体（又は物体データ）のマッチングを参照するものとしても理解されるべきである。
【０１５１】
ＳＩＦＴ技術が様々な倍率で画像を操作するように、本技術も同様にすることができる。含まれる計算の単純性のために、様々な倍率のヒストグラムに基づくデータを高速に計算することができる。
【０１５２】
携帯電話を参照してきたが、本発明の技術は、携帯も固定も何れでも、全ての方式のデバイスに利用可能であることが認識されよう。ＰＤＡ、オーガナイザ、携帯音楽プレーヤ、デスクトップコンピュータ、ウェアラブルコンピュータ、サーバなどは全て、本明細書に説明した原理を使用することができる。特に、企図した携帯電話は、ＡｐｐｌｅのｉＰｈｏｎｅ、ＧｏｏｇｌｅのＡｎｄｒｏｉｄ仕様に追随する携帯電話（例えば、ＨＴＣ Ｃｏｒｐ．によりＴ−Ｍｏｂｉｌｅ用に製作されたＧ１ ｐｈｏｎｅ）を含む。用語「携帯電話」は、厳密な意味での携帯又は電話でなくとも、そのような全てのデバイスを含むものと解釈すべきである。
【０１５３】
（タッチインタフェースを含むｉＰｈｏｎｅの詳細は、米国特許出願公開第２００８０１７４５７０号に記載されている。）
【０１５４】
本開示の方法を実施するのに使用することができる、携帯電話及び他のコンピュータの構造には、当業者であれば精通している。一般的な用語では、それぞれが、一以上のプロセッサ、一以上のメモリ（例えばＲＡＭ）、記憶装置（例えばディスク又はフラッシュメモリ）、ユーザインタフェース（例えば、キーパッド、ＴＦＴ ＬＣＤ、又はＯＬＥＤ ディスプレイスクリーン、タッチ又は他のジェスチャセンサ、カメラ又は他の光センサ、マイクロフォンなどと共に、グラフィカルユーザインタフェースをもたらすソフトウェア命令を含むことができる）、バッテリ、及び他のデバイスと通信するインタフェース（ＧＳＭ、ＣＤＭＡ、Ｗ−ＣＤＭＡ、ＣＤＭＡ２０００、ＴＤＭＡ、ＥＶ−ＤＯ、ＨＳＤＰＡ、ＷｉＦｉ、ＷｉＭａｘ、若しくはブルートゥースなどの無線、及び／又はイーサネットローカルエリアネットワーク、Ｔ−１インターネット接続などによる有線とすることができる）を含む。説明した構成の一部分又は全てを実施するのに使用することができる例示的な携帯電話を図８に示す。
【０１５５】
プロセッサは、特定目的のハードウェアデバイスであり得、メモリ若しくは記憶装置から、又はそれらの組合せにより読み出されるソフトウェア命令を実行するプログラム可能デバイスによって実装され得る。（Ａｒｍ，Ｌｉｍｉｔｅｄにより開発された３２ビットＲＩＳＣアーキテクチャを使用したＡＲＭシリーズのＣＰＵは、多くの携帯電話で使用される。）従って、「プロセッサ」を参照することは、実装の特定の形態ではなく、機能を参照しているものと理解すべきである。
【０１５６】
専用のハードウェア、又はソフトウェアで制御されるプログラム可能ハードウェアに加えて、プロセッサは、Ｘｉｌｉｎｘ、Ｖｉｒｔｅｘシリーズデバイスなどのフィールドプログラマブルゲートアレイを含むこともできる。或いは、プロセッサは、Ｔｅｘａｓ Ｉｎｓｔｒｕｍｅｎｔｓ ＴＭＳ３２０シリーズデバイスなどの一以上のデジタル信号プロセッシングコアを含むことができる。
【０１５７】
詳細な機能を実装するソフトウェア命令は、本明細書に記載した説明、結論、及び上述の他の規定から、当業者なら容易に書くことができる。
【０１５８】
通常、説明した方法を実施するデバイスは、ハードウェアデバイスへのインタフェース及び汎用の機能を提供するオペレーティングシステムソフトウェアを含み、ユーザが要求する特定のタスクを実行するのに選択的に呼び出すことができる応用ソフトウェアも含む。既知のブラウザソフトウェア、通信ソフトウェア、及びメディア処理ソフトウェアは、本明細書に説明した使用に適合させることができる。いくつかの実施形態は、エンベデッドシステムとして、即ち、（例えば、通常の基本的携帯電話の場合のように）オペレーティングシステムソフトウェア及び応用ソフトウェアがユーザには見分けがつかない特定目的コンピュータシステムとして実装することができる。本明細書に説明した機能は、オペレーティングシステムソフトウェア及び応用ソフトウェア内で、並びに／又はエンベデッドシステムソフトウェアとして実装することができる。
【０１５９】
様々な機能を様々なデバイスに実装することができる。例えば、携帯電話が遠隔のサービスプロバイダのサーバと通信するシステムでは、様々なタスクをいずれか一つのデバイスで独占的に実行することができるか、又はデバイス間で実行を分散することができる。例えば、携帯電話上のテスト画像からのヒストグラムデータの抽出、及び遠隔サーバ上の対応する参照画像のデータベースの探索は、一つのアーキテクチャとなるが、他の多くのものが存在する。例えば、参照画像に関する情報は、携帯電話上に記憶することができ、携帯電話は、全ての外部デバイスに依存することなく、テスト画像を取得し、ヒストグラムデータを生成し、参照画像に関する記憶されたヒストグラムデータと比較することができる。従って、特定のデバイス（例えば携帯電話）で実行される演算の記述は、限定的なものでなく、例示的なものであり、別のデバイス（例えば遠隔サーバ）又はデバイス間で共有される演算の実行も企図されることが明らかであることを理解されたい。（さらに、二つよりも多いデバイスを通常、使用することができる。例えば、サービスプロバイダは、いくつかのタスク、機能、又は演算をそのようなタスク専用のサーバに問い合わせることができる。）
【０１６０】
同様に、データは、局所デバイス、遠隔デバイス、クラウド、分散など、どこでも記憶することができる。
【０１６１】
演算は、特定の識別可能ハードウェアにより独占的に実行する必要はない。むしろ、いくつかの演算を、さらに一般に匿名のシステムにより実行処理する他のサービス（例えばクラウドコンピューティング）に問い合わせることができる。そのような分散システムは、大規模（例えば世界中のコンピューティング資源を含む）、又は局所的に（例えば、携帯デバイスが、ブルートゥース通信により近接するデバイスを特定するとき、演算中に近接するデバイスの一つ又は複数を含むように）することができる。
【０１６２】
本明細書を極度に長くすることなく包括的な開示を行うために、出願人は、上述した特許、特許出願、及び他の文献を参照にすることにより明示的に援用する。（そのような文献は、特定の教示に関して上述したとしても、全体が援用される。）これらの参考文献は、本明細書に説明した構成に援用することができる技術及び教示を開示し、本明細書に説明した技術及び教示をこれらの参考文献に援用ことができる。
【０１６３】
私は、私の技術の一部分として、以下の特許請求の範囲の範囲及び技術的思想、並びに均等物に入る可能性がある、そのような全ての変更形態を請求する。（特許請求の範囲は、説明した多数の発明概念を考慮して、出願人が発明とみなす技術の一部分のみを対象とする。出願人は、上述の他の発明概念を引き出す追加の特許請求の範囲を提出する権利を保持する。）
【特許請求の範囲】
【請求項１】
一以上の動作を実行するように構成されたプロセッサを有し、画像データを取得するカメラ部分を有するシステムを使用する方法であって、
システムプロセッサが、前記画像データから多次元ヒストグラムデータを生成するステップであり、前記ヒストグラムデータは、複数の次元を有し、より多い複数のヒストグラムのビンを含み、前記複数の次元の第１及び第２の次元は、量子化された色相情報に対応し、第３の次元は、２次導関数を用いて処理された量子化された照度情報に対応する、該ステップと、
取得された前記画像データに対応する一以上の候補画像を特定するために、生成された前記ヒストグラムデータに基づいて、様々な画像に対応する参照ヒストグラムデータの集合に対応するデータを処理するステップと、
を含む、方法。
【請求項２】
三つのレベルに照度情報を量子化するステップを含む、請求項１に記載の方法。
【請求項３】
厳密に二つのレベルに照度情報を量子化するステップを含む、請求項１に記載の方法。
【請求項４】
生成された前記ヒストグラムデータを基準に対して正規化するステップと、
次いで、前記正規化されたヒストグラムデータと複数の組の参照ヒストグラムデータの各々との間のヒストグラム共通度評価尺度を計算するステップと、
を含む請求項１に記載の方法。
【請求項５】
前記生成されたヒストグラムデータを基準に対して正規化するステップと、
次いで、前記正規化されたヒストグラムデータと参照ヒストグラムデータの複数の組の各々との間のヒストグラム整合性評価尺度を計算するステップとを含む、請求項１に記載の方法。
【請求項６】
一以上の動作を実行するように構成されたプロセッサを備え、画像データを取得するカメラ部分を備えるシステムを使用する方法であって、
前記画像データから多次元ヒストグラムデータを生成するステップと、
前記多次元ヒストグラムデータを参照して候補マッチング画像を特定するステップと、を含み、
前記生成された多次元ヒストグラムデータを正規化し、規格化されたヒストグラムデータを使用してヒストグラム共通度の計算を行うことを特徴とする方法。
【請求項７】
一以上の作業を実行するように構成されたプロセッサを備え、画像データを取得するカメラ部分を備えるシステムを使用する方法であって、
前記画像データから多次元ヒストグラムデータを生成するステップと、
前記多次元ヒストグラムデータを参照して候補マッチング画像を特定するステップと、
を含み、
候補マッチング画像を特定することに使用する前記多次元ヒストグラムデータは、前記画像データの輝度の２次以上の微分値に対応する量子化された微分データを含むことを特徴とする方法。
【請求項８】
前記微分データに対応する符号データを参照して候補マッチング画像を特定することを含む、請求項７に記載の方法。
【請求項９】
前記微分データを少なくとも二つのビン、即ち、閾値を上回る正の値と、閾値を上回る負の値とに量子化することを含む、請求項７に記載の方法。
【請求項１０】
前記微分データを前記二つのビンのみに量子化して、候補マッチング画像を特定することに使用される両極性データを取得することを含む、請求項９に記載の方法。
【請求項１１】
前記微分データを少なくとも三つのビン、即ち、閾値を上回る正の値と、閾値を上回る負の値と、他の値とを量子化することを含む、請求項７に記載の方法。
【請求項１２】
前記微分データを、ラプラスオペレータ、ラプラシアンガウシアンオペレータ、又はガウス関数の差法により生成することを含む、請求項７に記載の方法。
【請求項１３】
色ヒストグラムデータを参照して画像をマッチングする方法であって、
第１の画像の色ヒストグラムデータを生成するステップと、
対応する参照データ格納部内の色ヒストグラムデータを特定するステップと、
を含み、
前記色ヒストグラムデータは、少なくとも一つの色次元内で不均一に量子化されることを特徴とする方法。
【請求項１４】
前記色ヒストグラムデータが、色情報に対応する量子化された２次微分データを含む、請求項１３に記載の方法。
【請求項１５】
前記色ヒストグラムデータが、色情報に対応する量子化された色相データを含む、請求項１３に記載の方法。
【請求項１６】
色ヒストグラムデータを参照して画像をマッチングする方法であって、
第１の画像の色ヒストグラムデータを生成するステップと、
対応する参照データ格納部内の色ヒストグラムデータを特定するステップと、
を含み、
前記画像は、ピクセルを含み、各ピクセルにおける最大値と最小値との間の差分で反対色方向を正規化することを特徴とする方法。
【請求項１７】
色ヒストグラムデータを参照して画像をマッチングする方法であって、
第１の画像の色ヒストグラムデータを生成するステップと、
対応する参照データ格納部内の色ヒストグラムデータを特定するステップと、
を含み、
色コントラスト情報に関する色情報を表現することを特徴とする方法。
【請求項１８】
色ヒストグラムデータを参照して画像をマッチングする方法であって、
量子化されたビンにおいてテスト画像の色ヒストグラムデータを生成するステップと、
量子化されたビンにおいて前記テスト画像に対応する参照画像色ヒストグラムデータを特定するステップと、
を含み、
前記マッチングに関連して以下の基準値、
ａ．前記テスト画像ヒストグラム及び参照画像ヒストグラムの占有ビンの数、
ｂ．前記テスト画像ヒストグラム及び参照画像ヒストグラムの何れにも共通の占有ビンの数、
ｃ．前記テスト画像ヒストグラム及び参照画像ヒストグラムの双方を合わせた占有ビンの数、
ｄ．前記テスト画像ヒストグラム及び参照画像ヒストグラムの何れにも共通のピクセルの数（ヒストグラム共通度）、
ｅ．前記参照ヒストグラムを占有する前記テスト画像ヒストグラムの占有ビンの割合、
ｆ．前記ヒストグラム共通度と前記テスト画像ヒストグラムの占有ビンの数との比率、
ｇ．テスト画像ヒストグラムの非ゼロビン、
ｈ．参照画像ヒストグラムの非ゼロビン、
ｉ．参照画像ヒストグラムの非ゼロビンの部分集合であるテスト画像ヒストグラムの非ゼロビン、
ｊ．参照画像ヒストグラムの非ゼロビンの部分集合であるテスト画像ヒストグラムの非ゼロビンの数、
ｋ．テスト画像ヒストグラムの非ゼロビンの部分集合である参照画像ヒストグラムの非ゼロビン、並びに
ｌ．テスト画像ヒストグラムの非ゼロビンの部分集合である参照画像ヒストグラムの非ゼロビンの数
のうち一以上を求めることを特徴とする方法。
【請求項１９】
前記マッチングに関して、基準値（ａ）〜（ｌ）の二つ以上を結合することを含む、請求項１８に記載の方法。
【請求項２０】
閾値より小さい値を有するあらゆるビンを空として扱うことを含む、請求項１８に記載の方法。
【請求項２１】
色ヒストグラムデータを参照して画像をマッチングする方法であって、
量子化されたビンにおいてテスト画像の色ヒストグラムデータを生成するステップと、
量子化されたビンにおいて前記テスト画像に対応する参照画像色ヒストグラムデータを特定するステップと、
を含み、
前記参照画像ヒストグラム内を占有する前記テスト画像のヒストグラムのビンを無視し、前記テスト画像ヒストグラムの残りのビンと前記参照画像ヒストグラムのビンとの比較を行うことを特徴とする方法。
【請求項２２】
閾値より小さい値を有するあらゆるビンを非占有として扱うことを含む、請求項２１に記載の方法。
【請求項２３】
色ヒストグラムデータを参照して画像をマッチングする方法であって、
量子化されたビンにおいてテスト画像の色ヒストグラムデータを生成するステップと、
量子化されたビンにおいて前記テスト画像に対応する参照画像色ヒストグラムデータを特定するステップと、
を含み、
（ａ）前記テスト画像ヒストグラムの少なくとも大多数の占有ビンが、前記参照画像ヒストグラムの占有ビンの部分集合であるか否かをチェックし、
（ｂ）前記テスト画像ヒストグラムの少なくともいくつかのビンのカウント値が、前記参照画像ヒストグラムの対応するカウント値よりも大きいことをチェックすることを特徴とし、画像は、ズームインに依らずマッチングすることができる、方法。
【請求項２４】
閾値より小さい値を有するあらゆるビンを非占有として扱うことを含む、請求項２３に記載の方法。
【請求項２５】
前記テスト画像ヒストグラムのビンのカウント値と参照画像ヒストグラムのビンのカウント値との間の関係を表現する倍率を求めるために、回帰分析を行うことを更に含む、請求項２３に記載の方法。
【請求項２６】
色ヒストグラムデータを参照して画像をマッチングする方法であって、
第１の画像の色ヒストグラムデータを生成するステップと、
対応する参照データ格納部内の色ヒストグラムデータを特定するステップと、
を含み、
前記色ヒストグラムデータは、エッジの方向とは独立に、該エッジに存在する色に関して前記第１の画像を特徴付ける、方法。
【請求項２７】
第１の画像の色ヒストグラムデータの生成が、携帯電話内のプロセッサにより実行される、請求項１〜２６のいずれか一項に記載の方法。
【請求項２８】
プロセッサ、メモリ、カメラシステム、及び無線インタフェースを含む携帯電話と、
プロセッサ、メモリ、カメラシステム、及び前記携帯電話とのデータ交換を可能にするインタフェースを含む遠隔コンピュータと、
を備え、
前記メモリは、
前記カメラシステムから画像データのフレームを取得するオペレーション、
画像データの前記取得されたフレームから多次元ヒストグラムデータを生成するオペレーションであり、前記ヒストグラムデータが、複数の次元を有し、より多い複数のヒストグラムのビンを規定し、前記複数の次元の第１及び第２の次元は、量子化された色相情報に対応し、第３の次元は、２次導関数により処理される量子化照度情報に対応する、オペレーション、
前記生成されたヒストグラムデータを参照ヒストグラムデータの複数の組と比較するオペレーション、及び
前記比較により、前記取得された画像に対応する、一以上の候補マッチング画像を特定するオペレーション
を前記プロセッサに実行させる命令を記憶する、
システム。
【請求項１】
一以上の動作を実行するように構成されたプロセッサを有し、画像データを取得するカメラ部分を有するシステムを使用する方法であって、
システムプロセッサが、前記画像データから多次元ヒストグラムデータを生成するステップであり、前記ヒストグラムデータは、複数の次元を有し、より多い複数のヒストグラムのビンを含み、前記複数の次元の第１及び第２の次元は、量子化された色相情報に対応し、第３の次元は、２次導関数を用いて処理された量子化された照度情報に対応する、該ステップと、
取得された前記画像データに対応する一以上の候補画像を特定するために、生成された前記ヒストグラムデータに基づいて、様々な画像に対応する参照ヒストグラムデータの集合に対応するデータを処理するステップと、
を含む、方法。
【請求項２】
三つのレベルに照度情報を量子化するステップを含む、請求項１に記載の方法。
【請求項３】
厳密に二つのレベルに照度情報を量子化するステップを含む、請求項１に記載の方法。
【請求項４】
生成された前記ヒストグラムデータを基準に対して正規化するステップと、
次いで、前記正規化されたヒストグラムデータと複数の組の参照ヒストグラムデータの各々との間のヒストグラム共通度評価尺度を計算するステップと、
を含む請求項１に記載の方法。
【請求項５】
前記生成されたヒストグラムデータを基準に対して正規化するステップと、
次いで、前記正規化されたヒストグラムデータと参照ヒストグラムデータの複数の組の各々との間のヒストグラム整合性評価尺度を計算するステップとを含む、請求項１に記載の方法。
【請求項６】
一以上の動作を実行するように構成されたプロセッサを備え、画像データを取得するカメラ部分を備えるシステムを使用する方法であって、
前記画像データから多次元ヒストグラムデータを生成するステップと、
前記多次元ヒストグラムデータを参照して候補マッチング画像を特定するステップと、を含み、
前記生成された多次元ヒストグラムデータを正規化し、規格化されたヒストグラムデータを使用してヒストグラム共通度の計算を行うことを特徴とする方法。
【請求項７】
一以上の作業を実行するように構成されたプロセッサを備え、画像データを取得するカメラ部分を備えるシステムを使用する方法であって、
前記画像データから多次元ヒストグラムデータを生成するステップと、
前記多次元ヒストグラムデータを参照して候補マッチング画像を特定するステップと、
を含み、
候補マッチング画像を特定することに使用する前記多次元ヒストグラムデータは、前記画像データの輝度の２次以上の微分値に対応する量子化された微分データを含むことを特徴とする方法。
【請求項８】
前記微分データに対応する符号データを参照して候補マッチング画像を特定することを含む、請求項７に記載の方法。
【請求項９】
前記微分データを少なくとも二つのビン、即ち、閾値を上回る正の値と、閾値を上回る負の値とに量子化することを含む、請求項７に記載の方法。
【請求項１０】
前記微分データを前記二つのビンのみに量子化して、候補マッチング画像を特定することに使用される両極性データを取得することを含む、請求項９に記載の方法。
【請求項１１】
前記微分データを少なくとも三つのビン、即ち、閾値を上回る正の値と、閾値を上回る負の値と、他の値とを量子化することを含む、請求項７に記載の方法。
【請求項１２】
前記微分データを、ラプラスオペレータ、ラプラシアンガウシアンオペレータ、又はガウス関数の差法により生成することを含む、請求項７に記載の方法。
【請求項１３】
色ヒストグラムデータを参照して画像をマッチングする方法であって、
第１の画像の色ヒストグラムデータを生成するステップと、
対応する参照データ格納部内の色ヒストグラムデータを特定するステップと、
を含み、
前記色ヒストグラムデータは、少なくとも一つの色次元内で不均一に量子化されることを特徴とする方法。
【請求項１４】
前記色ヒストグラムデータが、色情報に対応する量子化された２次微分データを含む、請求項１３に記載の方法。
【請求項１５】
前記色ヒストグラムデータが、色情報に対応する量子化された色相データを含む、請求項１３に記載の方法。
【請求項１６】
色ヒストグラムデータを参照して画像をマッチングする方法であって、
第１の画像の色ヒストグラムデータを生成するステップと、
対応する参照データ格納部内の色ヒストグラムデータを特定するステップと、
を含み、
前記画像は、ピクセルを含み、各ピクセルにおける最大値と最小値との間の差分で反対色方向を正規化することを特徴とする方法。
【請求項１７】
色ヒストグラムデータを参照して画像をマッチングする方法であって、
第１の画像の色ヒストグラムデータを生成するステップと、
対応する参照データ格納部内の色ヒストグラムデータを特定するステップと、
を含み、
色コントラスト情報に関する色情報を表現することを特徴とする方法。
【請求項１８】
色ヒストグラムデータを参照して画像をマッチングする方法であって、
量子化されたビンにおいてテスト画像の色ヒストグラムデータを生成するステップと、
量子化されたビンにおいて前記テスト画像に対応する参照画像色ヒストグラムデータを特定するステップと、
を含み、
前記マッチングに関連して以下の基準値、
ａ．前記テスト画像ヒストグラム及び参照画像ヒストグラムの占有ビンの数、
ｂ．前記テスト画像ヒストグラム及び参照画像ヒストグラムの何れにも共通の占有ビンの数、
ｃ．前記テスト画像ヒストグラム及び参照画像ヒストグラムの双方を合わせた占有ビンの数、
ｄ．前記テスト画像ヒストグラム及び参照画像ヒストグラムの何れにも共通のピクセルの数（ヒストグラム共通度）、
ｅ．前記参照ヒストグラムを占有する前記テスト画像ヒストグラムの占有ビンの割合、
ｆ．前記ヒストグラム共通度と前記テスト画像ヒストグラムの占有ビンの数との比率、
ｇ．テスト画像ヒストグラムの非ゼロビン、
ｈ．参照画像ヒストグラムの非ゼロビン、
ｉ．参照画像ヒストグラムの非ゼロビンの部分集合であるテスト画像ヒストグラムの非ゼロビン、
ｊ．参照画像ヒストグラムの非ゼロビンの部分集合であるテスト画像ヒストグラムの非ゼロビンの数、
ｋ．テスト画像ヒストグラムの非ゼロビンの部分集合である参照画像ヒストグラムの非ゼロビン、並びに
ｌ．テスト画像ヒストグラムの非ゼロビンの部分集合である参照画像ヒストグラムの非ゼロビンの数
のうち一以上を求めることを特徴とする方法。
【請求項１９】
前記マッチングに関して、基準値（ａ）〜（ｌ）の二つ以上を結合することを含む、請求項１８に記載の方法。
【請求項２０】
閾値より小さい値を有するあらゆるビンを空として扱うことを含む、請求項１８に記載の方法。
【請求項２１】
色ヒストグラムデータを参照して画像をマッチングする方法であって、
量子化されたビンにおいてテスト画像の色ヒストグラムデータを生成するステップと、
量子化されたビンにおいて前記テスト画像に対応する参照画像色ヒストグラムデータを特定するステップと、
を含み、
前記参照画像ヒストグラム内を占有する前記テスト画像のヒストグラムのビンを無視し、前記テスト画像ヒストグラムの残りのビンと前記参照画像ヒストグラムのビンとの比較を行うことを特徴とする方法。
【請求項２２】
閾値より小さい値を有するあらゆるビンを非占有として扱うことを含む、請求項２１に記載の方法。
【請求項２３】
色ヒストグラムデータを参照して画像をマッチングする方法であって、
量子化されたビンにおいてテスト画像の色ヒストグラムデータを生成するステップと、
量子化されたビンにおいて前記テスト画像に対応する参照画像色ヒストグラムデータを特定するステップと、
を含み、
（ａ）前記テスト画像ヒストグラムの少なくとも大多数の占有ビンが、前記参照画像ヒストグラムの占有ビンの部分集合であるか否かをチェックし、
（ｂ）前記テスト画像ヒストグラムの少なくともいくつかのビンのカウント値が、前記参照画像ヒストグラムの対応するカウント値よりも大きいことをチェックすることを特徴とし、画像は、ズームインに依らずマッチングすることができる、方法。
【請求項２４】
閾値より小さい値を有するあらゆるビンを非占有として扱うことを含む、請求項２３に記載の方法。
【請求項２５】
前記テスト画像ヒストグラムのビンのカウント値と参照画像ヒストグラムのビンのカウント値との間の関係を表現する倍率を求めるために、回帰分析を行うことを更に含む、請求項２３に記載の方法。
【請求項２６】
色ヒストグラムデータを参照して画像をマッチングする方法であって、
第１の画像の色ヒストグラムデータを生成するステップと、
対応する参照データ格納部内の色ヒストグラムデータを特定するステップと、
を含み、
前記色ヒストグラムデータは、エッジの方向とは独立に、該エッジに存在する色に関して前記第１の画像を特徴付ける、方法。
【請求項２７】
第１の画像の色ヒストグラムデータの生成が、携帯電話内のプロセッサにより実行される、請求項１〜２６のいずれか一項に記載の方法。
【請求項２８】
プロセッサ、メモリ、カメラシステム、及び無線インタフェースを含む携帯電話と、
プロセッサ、メモリ、カメラシステム、及び前記携帯電話とのデータ交換を可能にするインタフェースを含む遠隔コンピュータと、
を備え、
前記メモリは、
前記カメラシステムから画像データのフレームを取得するオペレーション、
画像データの前記取得されたフレームから多次元ヒストグラムデータを生成するオペレーションであり、前記ヒストグラムデータが、複数の次元を有し、より多い複数のヒストグラムのビンを規定し、前記複数の次元の第１及び第２の次元は、量子化された色相情報に対応し、第３の次元は、２次導関数により処理される量子化照度情報に対応する、オペレーション、
前記生成されたヒストグラムデータを参照ヒストグラムデータの複数の組と比較するオペレーション、及び
前記比較により、前記取得された画像に対応する、一以上の候補マッチング画像を特定するオペレーション
を前記プロセッサに実行させる命令を記憶する、
システム。
【図１Ａ】
【図２Ａ】
【図３】
【図５Ａ】
【図５Ｂ】
【図６】
【図８】
【図１Ｂ】
【図２Ｂ】
【図４Ａ】
【図４Ｂ】
【図７】
【図２Ａ】
【図３】
【図５Ａ】
【図５Ｂ】
【図６】
【図８】
【図１Ｂ】
【図２Ｂ】
【図４Ａ】
【図４Ｂ】
【図７】
【公表番号】特表２０１２−５２７７０５（Ｐ２０１２−５２７７０５Ａ）
【公表日】平成２４年１１月８日（２０１２．１１．８）
【国際特許分類】
【出願番号】特願２０１２−５１１９９９（Ｐ２０１２−５１１９９９）
【出願日】平成２２年５月１９日（２０１０．５．１９）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０３５４４９
【国際公開番号】ＷＯ２０１０／１３５４５５
【国際公開日】平成２２年１１月２５日（２０１０．１１．２５）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＧＳＭ
２．イーサネット
【出願人】（３１００２１９７３）ディジマーク コーポレイション (13)
【Ｆターム（参考）】
【公表日】平成２４年１１月８日（２０１２．１１．８）
【国際特許分類】
【出願日】平成２２年５月１９日（２０１０．５．１９）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０３５４４９
【国際公開番号】ＷＯ２０１０／１３５４５５
【国際公開日】平成２２年１１月２５日（２０１０．１１．２５）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＧＳＭ
２．イーサネット
【出願人】（３１００２１９７３）ディジマーク コーポレイション (13)
【Ｆターム（参考）】
[ Back to top ]