(57)【特許請求の範囲】
【請求項１】
画像を処理するための方法であって、
前記画像中のキーポイントの第１のグループを識別するステップと、
前記第１のグループの各キーポイントについて、
ａ）前記各キーポイントに関連した少なくとも１つの対応するキーポイント局所的特徴を識別するステップと、
ｂ）前記少なくとも１つのキーポイント局所的特徴について、対応する局所的特徴関連確率を計算するステップと、
ｃ）前記少なくとも１つの局所的特徴の前記局所的特徴関連確率に基づいてキーポイント関連確率を計算するステップと、
キーポイントの第２のグループを形成するために、前記第１のグループの前記キーポイントの中から最も高いキーポイント関連確率を有するキーポイントを選択するステップと、
前記画像を分析するために前記第２のグループの前記キーポイントを利用するステップと
を含み、
キーポイントの局所的特徴について計算された前記局所的特徴関連確率は、前記局所的特徴により仮定された値を前記局所的特徴の値の対応する参照統計的分布と比較することにより得られる、方法。
【請求項２】
各参照統計的分布が複数のビンを有する対応するヒストグラムの形式に配置されており、各ビンが対応する前記局所的特徴の所定の範囲の値に対応し、各ビンの度数が、
ａ）正しい特徴一致を含むことが確認され、前記ビンの範囲に入る前記対応する局所的特徴の値を有する参照キーポイントの数と、
ｂ）前記ビンの範囲に入る前記対応する局所的特徴の値を有する参照キーポイントの総数と
の比率に対応する、請求項１に記載の方法。
【請求項３】
前記各キーポイントに関連する前記少なくとも１つのキーポイント局所的特徴が、
前記キーポイントの座標、
前記キーポイントが識別されたスケール、
前記キーポイントの主要な方向、
前記キーポイントのピーク、及び
前記キーポイントの記述子
のうち少なくとも１つを含む、請求項１又は２に記載の方法。
【請求項４】
キーポイントの局所的特徴についての前記局所的特徴関連確率を計算する前記ステップは、
ｃ）前記キーポイントの前記局所的特徴により仮定される値に適合する前記ヒストグラムの前記ビンを識別するために、前記局所的特徴に対応する前記ヒストグラムを検査するステップと、
ｄ）前記局所的特徴関連確率を識別された前記ビンの度数に設定するステップと
を含む、請求項２、又は請求項２に従属する場合の請求項３に記載の方法。
【請求項５】
前記第１のグループの１つのキーポイントのキーポイント関連確率を計算する前記ステップは、前記対応するキーポイントの前記少なくとも１つの局所的特徴のうちのそれぞれ一つの局所的特徴関連確率を結合するステップを含む、請求項１から４のいずれか一項に記載の方法。
【請求項６】
前記第１のグループのキーポイントのキーポイント関連確率を計算する前記ステップは、前記対応するキーポイントの前記少なくとも１つの局所的特徴のそれぞれ１つの局所的特徴関連確率を１つのものから別のものに乗算するステップを含む、請求項５に記載の方法。
【請求項７】
画像を処理するためのシステムであって、
前記画像中のキーポイントの第１のグループを識別するように構成された第１の処理装置と、
前記第１のグループの各キーポイントについて、
ａ）前記各キーポイントに関連した少なくとも１つの対応するキーポイント局所的特徴を識別する動作と、
ｂ）前記少なくとも１つのキーポイント局所的特徴について、対応する局所的特徴関連確率を計算する動作と、
ｃ）前記少なくとも１つの局所的特徴の前記局所的特徴関連確率に基づいてキーポイント関連確率を計算する動作と
を実行するように構成された第２の処理装置と、
キーポイントの第２のグループを形成するために、前記第１のグループの前記キーポイントの中から最も高いキーポイント関連確率を有するキーポイントを選択するように構成された第３の処理装置と、
前記画像を分析するために前記第２のグループの前記キーポイントを利用するように構成された第４の処理装置と
を備え、
キーポイントの局所的特徴について計算された前記局所的特徴関連確率は、前記局所的特徴により仮定された値を前記局所的特徴の値の対応する参照統計的分布と比較することにより得られる、システム。
【請求項８】
複数の参照画像の対において識別される複数の参照キーポイントの中から局所的特徴の値を収集するステップであって、局所的特徴の前記値は、参照画像の対であって該対の参照画像の間に正しい特徴一致を含むことが確認された参照画像の対の各々の参照キーポイントに対応する、ステップ
を含む、請求項１から６のいずれか一項に記載の方法において使用されるキーポイント局所的特徴の値の参照統計的分布を生成するための方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像分析の分野に関する。
【背景技術】
【０００２】
画像分析の分野においては、２つの画像の両方が同一の場面又は同一の物体の少なくとも部分を含む場合に２つの画像の間において発生する関連を発見するために、共通の操作が２つの画像の比較を提供する。
【０００３】
多数の用途の間において、画像比較は映像撮影の２つのフレーム間において発生する動きを評価するために、また画像（例えば写真）内の物体の認識のために、マルチカメラシステムに属するビデオカメラを調整するために最も重要である。後者の用途は、いわゆる視覚的検索エンジン、すなわち写真から開始してその中に撮影された物体（複数可）を識別して識別された物体（複数可）に関連する情報を提供することが可能である自動化されたサービスにおいて使用されるように具体的に設計された物体認識アルゴリズムの最近の開発に起因して、現在ますます重要性が高まっている。このタイプの既知のサービスの例は、グーグル・ゴーグルズ（Google Goggles）、ノキア・ポイント・アンド・ファインド（Nokia Point&Find）及びクアバ・スマート・ビジュアルズ（kooaba Smart Visuals）を含む。物体認識アプリケーションは、典型的には専門用語において、認識されるべき物体を示す「クエリ画像」と呼ばれる第１の画像の複数のモデル画像との比較を提供する。各モデル画像は、既知の各物体を示す。このことは、クエリ画像中に示された物体と複数のモデル画像中に示された複数の物体の間の比較を実行することを可能にする。
【０００４】
モデル画像は、典型的には適切なモデルデータベースに配置されている。例えば、物体認識がオンラインショッピングシナリオにおいて利用される場合には、各モデル画像はオンラインストアにより用意される商品（例えば本の表紙、ＤＶＤカバー及び／又はＣＤカバーの写真）に対応する。そのようなタイプのデータベースに含まれるモデル画像の数は非常に多く、例えばオンラインショッピングサービスのモデルデータベースは数百万の異なるモデル画像を含み得る。
【０００５】
２つの画像の間の比較動作を実行する非常に効率的な方法は、第１の画像において専門用語ではキーポイントと呼ばれるポイントのセットを選択して、その後当該セットの各キーポイントを第２の画像中の対応するキーポイントに対してマッチングすることを提供する。第１の画像のいずれのポイントがキーポイントにならなければならないかの選択は、例えばポイント抽出スケール、領域の特権を有する方向及びいわゆる「記述子」のような当該ポイント自体を取り囲む当該画像の領域の局所的特徴を抽出することにより有利に実行される。画像分析の分野においては、キーポイントの記述子はキーポイントに中心がある（パッチと呼ばれる）画像の領域の輝度勾配を記述する数学的演算子であり、そのようなパッチはパッチ自体の主な輝度勾配に従って方向付けられている。
【０００６】
Ｄａｖｉｄ  Ｇ．  Ｌｏｗｅ著「Ｄｉｓｔｉｎｃｔｉｖｅ  ｉｍａｇｅ  ｆｅａｔｕｒｅｓ  ｆｒｏｍ  ｓｃａｌｅ−ｉｎｖａｒｉａｎｔ  ｋｅｙｐｏｉｎｔｓ（スケール不変キーポイントからの明確な画像特徴）」（Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｕｒｎａｌ  ｏｆ  ｃｏｍｐｕｔｅｒ  ｖｉｓｉｏｎ、２００４年）においては、スケール不変性特徴変形（ＳＩＦＴ）記述子が提案され、簡潔には、信頼可能な画像認識を可能にするために各キーポイントに対応する画像から抽出された局所的な特徴が画像スケール、ノイズ及び照明における変化の下においてさえ検出可能であるべきであることを考慮して、ＳＩＦＴ記述子が生成される。そのためＳＩＦＴ記述子はスケール、方向を均一にするために不変であり、かつアフィン歪及び照明変更に対して部分的に不変である。
【０００７】
ＳＩＦＴ記述子は極めて強力なツールであり、正確な画像比較を実行するためのキーポイントを選択することを可能にする。しかし、この正確さは極めて大きな量のデータの使用によってのみ達成され得る。例えば、典型的なＳＩＦＴ記述子は１２８データバイトの配列である。各画像中のキーポイントの数は比較的多く（例えば標準的なＶＧＡ画像について１０００〜１５００キーポイント）、各キーポイントは対応するＳＩＦＴ記述子に関連付けられているため、処理されるべき全体のデータの量は効率的に管理される量を超過しうる。
【０００８】
この欠点は、状況が移動体端末の使用を伴う場合（例えばスマートフォンのカメラにより撮影された写真から抽出される物体の識別）に悪化させられる。実際、画像分析を実行するために実行されるべき動作は計算負荷の観点から極めて複雑かつ厳しいため、この場合には分析を実行するために必要とされる全ての情報を有するために、殆どの動作は通常サーバ側において実行される。サーバは移動体端末から、全てのキーポイントについてのＳＩＦＴ記述子を含む全ての必要とされるデータを受信する必要がある。そのため、端末からサーバに送信されるべきデータの量はサービスの良好な効率性を保証する量を超過しうる。
【０００９】
例えばグーグル・ゴーグルズにより使用される解決法のような当該技術において知られる解決法によれば、上記の欠点は移動体端末からサーバに記述子ではなく画像を直接送信することによるルートにおいて解決される。実際、極めて多数のキーポイントのために、対応するＳＩＦＴ記述子のデータの量が標準ＶＧＡ画像自体のサイズを（バイト数の観点から）超過し得る。
【発明の概要】
【発明が解決しようとする課題】
【００１０】
出願人は、当該技術において知られるアプローチが効率的でなく、依然サーバ側における動作の大部分の集中及び／又は大量のデータの管理を必要とし、システムの拡張性及び全体の性能を制限することを発見した。
【００１１】
例えば、グーグル・ゴーグルズにより使用される解決法は、移動体端末からサーバへの記述子ではなく画像の直接的な送信を提供し、全体の計算負荷がサーバに向かって移動させられることを必要とし、サーバは過負荷になり得る。さらに、圧縮された画像の送信は依然相当な量のデータ（例えばＶＧＡ画像について数十キロバイト）を必要とする。
【００１２】
出願人は、処理されるべきデータの量の観点からどのように上記のアプローチを改善するかの問題に取り組んだ。
【００１３】
具体的には、出願人は削減された量の管理されるべきデータを必要とする画像を処理するための方法を提供するために前記問題に取り組んだ。
【００１４】
出願人は、参照統計的分布に基づいて計算された局所的特徴関連可能性に従って、画像中において識別された複数のキーポイントの間から複数のキーポイントの最適なサブセットを選択することにより、画像分析手順を実行するために処理されるべきデータの量が有利に削減され得ることを発見した。
【課題を解決するための手段】
【００１５】
本発明の１つの態様によれば、画像を処理するための方法が提案される。方法は、画像中の複数のキーポイントの第１のグループを識別することを含む。第１のグループの各キーポイントについて、方法は前記各キーポイントに関連する少なくとも１つの対応するキーポイント局所的特徴を識別することと、前記少なくとも１つのキーポイント局所的特徴について対応する局所的特徴関連可能性を計算することと、前記少なくとも１つの局所的特徴の局所的特徴関連可能性に基づいてキーポイント関連可能性を計算することを提供する。方法はさらに、複数のキーポイントの第２のグループを形成するために、第１のグループの複数のキーポイントの間から最も高いキーポイント関連可能性を有する複数のキーポイントを選択することと、画像を分析するために第２のグループの複数のキーポイントを利用することを含む。キーポイントの局所的特徴について計算された局所的特徴関連可能性は、前記局所的特徴により仮定された値を前記局所的特徴の複数の値の対応する参照統計的分布と比較することにより取得される。
【００１６】
本発明の一実施形態によれば、対応する前記各参照統計的分布が、複数の参照画像対において識別された複数の参照キーポイントの間から各参照画像対の参照キーポイントに対応する局所的特徴値を収集することにより生成された、対応する統計的分布に統計的に等しく、これらの各参照画像対の参照キーポイントは、そのような対の参照画像の間において正しい特徴一致を含むことが確認されている。
【００１７】
好適には、前記各キーポイントに関連する前記少なくとも１つのキーポイント局所的特徴は、当該キーポイントの複数の座標の間からの少なくとも１つの座標と、当該キーポイントが識別されたスケールと、当該キーポイントの主要な方向と、当該キーポイントのピークと、当該キーポイントの記述子とを含む。
【００１８】
本発明の一実施形態によれば、各参照統計的分布は複数のビンを有する対応するヒストグラムの形式に配置される。各ビンは、対応する局所的特徴の所定の範囲の値に対応する。各ビンの度数は、
ａ）正しい特徴一致を含むことが確認された参照キーポイントであって、前記ビンの範囲内に入る対応する局所的特徴の値を有する参照キーポイントの数と、
ｂ）前記ビンの範囲内に入る対応する局所的特徴の値を有する参照キーポイントの合計数
との間の比率に対応する。
【００１９】
本発明の一実施形態によれば、前記のキーポイントの局所的特徴についての局所的特徴関連可能性の計算は、当該キーポイントの局所的特徴により仮定される値に適合するヒストグラムのビンを識別するためにそのような局所的特徴に対応するヒストグラムを検査することと、局所的特徴関連可能性を識別されたビンの度数に設定することを含む。
【００２０】
有利には、前記の第１のグループの１つのキーポイントのキーポイント関連可能性の計算は、対応するキーポイントの前記少なくとも１つの局所的特徴のうちのそれぞれ１つの局所的特徴関連可能性を組み合わせることを含む。
【００２１】
好適には、前記の第１のグループの１つのキーポイントのキーポイント関連可能性の計算は、対応するキーポイントの前記少なくとも１つの局所的特徴のうちのそれぞれ１つの局所的特徴関連可能性を１つのものから別のものに乗算する（multiplying）ことを含む。
【００２２】
本発明の別の態様は、画像を処理するためのシステムを提供する。前記システムは、画像中の複数のキーポイントの第１のグループを識別するように構成された第１の処理装置と、第１のグループの各キーポイントについて以下の動作を実行するように構成された第２の処理装置を備えている。
【００２３】
ａ）前記各キーポイントに関連する少なくとも１つの対応するキーポイント局所的特徴を識別する動作と、
ｂ）前記少なくとも１つのキーポイント局所的特徴について、対応する局所的特徴関連可能性を計算する動作と、
ｃ）前記少なくとも１つの局所的特徴の局所的特徴関連可能性に基づいてキーポイント関連可能性を計算する動作。
【００２４】
前記システムはさらに、複数のキーポイントの第２のグループを形成するために第１のグループの複数のキーポイントの間から最も高いキーポイント関連可能性を有する複数のキーポイントを選択するように構成された第３の処理装置と、画像を分析するために第２のグループの複数のキーポイントを利用するように構成された第４の処理装置とを備えている。キーポイントの局所的特徴について計算される局所的特徴関連可能性は、前記局所的特徴により仮定される値を対応する前記局所的特徴の値の参照統計的分布と比較することにより取得される。
【００２５】
本発明のさらなる態様は、キーポイント局所的特徴の値の参照統計的分布を生成するための方法に関する。
【００２６】
本発明のこれらの及び他の特徴及び利点は、添付の図面と共に読まれるべきいくつかの例示的かつ非制限的なその実施形態の以下の説明により明白にされるであろう。
【図面の簡単な説明】
【００２７】
【図１】本発明の実施形態によるクエリ画像からキーポイントの最適なセットを抽出して記述子の圧縮されたセットを生成することに向けられた抽出手順を機能ブロックの観点から示す。
【図２Ａ】本発明の例示的実施形態によるキーポイントの対応する選択された局所的特徴の統計的分布である。
【図２Ｂ】本発明の例示的実施形態によるキーポイントの対応する選択された局所的特徴の統計的分布である。
【図２Ｃ】本発明の例示的実施形態によるキーポイントの対応する選択された局所的特徴の統計的分布である。
【図２Ｄ】本発明の例示的実施形態によるキーポイントの対応する選択された局所的特徴の統計的分布である。
【図２Ｅ】本発明の例示的実施形態によるキーポイントの対応する選択された局所的特徴の統計的分布である。
【図２Ｆ】本発明の例示的実施形態によるキーポイントの対応する選択された局所的特徴の統計的分布である。
【図２Ｇ】図１の抽出手順により処理された例示的な写真である。
【図３】図３ＡはＳＩＦＴタイプの例示的な記述子を示す。図３Ｂは図３Ａの記述子の例示的な記述子配列を示す。
【図４Ａ】当該技術において知られる解決法による例示的な記述子配列圧縮を示す。
【図４Ｂ】当該技術において知られる別の解決法による例示的な記述子配列圧縮を示す。
【図５】本発明の一実施形態による相関ファミリー（correlation families）における記述子のサブヒストグラムの配置を示す。
【図６Ａ】本発明の例示的実施形態により記述子配列がどのように圧縮されるかを示す。
【図６Ｂ】本発明の例示的実施形態により記述子配列がどのように圧縮されるかを示す。
【図６Ｃ】本発明の例示的実施形態により記述子配列がどのように圧縮されるかを示す。
【図６Ｄ】本発明の例示的実施形態により記述子配列がどのように圧縮されるかを示す。
【図７Ａ】キーポイントＫＰの例示的分布を示す。
【図７Ｂ】図７Ａのキーポイントの座標を量子化するためにどのように格子がクエリ画像上に重ね合わされ得るかを示す。
【図７Ｃ】図７Ａの複数のキーポイントＫＰのセット上に図７Ｂの格子を重ね合わせることにより得られたヒストグラムの例示的な図形的表現である。
【図７Ｄ】いずれのキーポイントも含まないセルにより全体的に形成された図７Ｂの格子の列及び行を識別する。
【図７Ｅ】ランク１サポート（rank-1 support）上の例示的なヒストグラムを示す。
【図７Ｆ】図７Ｅのランク１サポート上のヒストグラムに対応するヒストグラムマップを示す。
【図８】図８Ａはワードヒストグラムの例を示す。図８Ｂはヒストグラムマップの例を示す。
【図９】本発明の一実施形態による２つの画像の間の比較を実行することに向けられたマッチング手順を機能ブロックの観点からを示す。
【図１０】モデルデータベースからクエリ画像中に示された同一の物体／場面を示すモデル画像を取り出すことに向けられた、この発明による取り出し手順を機能ブロックの観点から示す。
【発明を実施するための形態】
【００２８】
抽出手順（図１）
図１は、以下「抽出手順」と呼ばれ、参照符号１００により識別される、最適なキーポイントのセットを取得するために入力画像を処理して対応する記述子のセットを生成することに向けられた、この発明の一実施形態による手順を機能ブロックの観点から示す。その後、キーポイント及び記述子は画像分析目的のために利用される。以下の本説明において、一般的表現「画像分析」及び「画像を分析する」は、ある画像を少なくとも１つの別の画像と比較することを提供する全ての動作を含むことが意図されなければならない。これらの動作は、複数の異なるピクチャから開始して単一のパノラマピクチャの作成を提供するアプリケーションだけでなく、例えば物体認識アプリケーションのような各種のアプリケーションにおいても実行され得る。
【００２９】
後述される通り、本発明の一実施形態による抽出手順は、最適なキーポイントのサブセットを選択することと、そのようなキーポイントの記述子を後続の手順の効率性を大きく改善するような程度に圧縮することをさらに提供する。
【００３０】
本節において説明される抽出手順１００のステップは、適切な処理装置により実行され得て、処理装置の構造及び機能はそれらが目的を定められたアプリケーションの特定の分野に依存する。例えば、各処理装置は、本方法の１つ又は複数のステップを実行するように具体的に設計されたハードウェア装置であり得る。さらに、本方法のステップは対応する命令のセットの制御下においてプログラム可能な機械（例えばコンピュータ）により実行され得る。
【００３１】
キーポイント抽出（段階１１０）
抽出手順１００の第１の段階１１０は、クエリ画像１１５を受け取ることとそこからキーポイントＫＰの第１のセットを抽出することを提供し、各キーポイントＫＰはクエリ画像１１５内のそのようなキーポイントＫＰの位置を識別する空間座標Ｃの対応する対に関連付けられている。
【００３２】
この動作は、既知のガウシアン差分（ＤｏＧ）キーポイント抽出アルゴリズムを利用することにより実行され得る。しかし、例えばヘッセの行列式（ＤｏＨ）キーポイント抽出アルゴリズムのような異なるキーポイント抽出アルゴリズムが使用される場合において、同様の考慮が適用される。ＤｏＧキーポイント抽出アルゴリズムを参照すると、クエリ画像１１５は異なるスケールにおいてある順序によりガウシアンフィルタにより畳み込み積分される。次に、ガウシアンにより不鮮明にされた近接する画像の対の間において、差分演算がその順序により実行される。次に、キーポイントＫＰが複数のスケールにおいてガウシアン差分（ＤｏＧ）の最大／最小値を有するポイントとして選択される。特に、ＤｏＧ画像中の各画素は、同一のスケールにおいて８つの近接部（neighbors）と比較され、近接するスケール（すなわちその順序における後続及び前のスケール）のそれぞれにおいて９つの近接する画素と比較される。全ての比較される画素の間において画素値が最大又は最小である場合には、そのポイントは候補キーポイントＫＰであると考えられる。
【００３３】
段階１１０は、各キーポイントＫＰが局所的画像輝度勾配方向に基づいて１つ又は複数の方向に割り当てられることをも提供する。例えば、各ビンが対応する度数間隔をカバーする複数のビンを有する方向ヒストグラムが形成される。ヒストグラムビンに加えられる隣接するウィンドウ内の各サンプルはその勾配の大きさにより重み付けされ、かつガウシアン重み付けされた（Gaussian-weighted）円形のウィンドウにより重み付けされる。結果として生じるヒストグラムのピークは、主要な方向に対応する。ヒストグラムが満たされると、最も高いピーク及び最も高いピークの８０％以内である局所的ピークに対応する方向がキーポイントＫＰに割り当てられる。複数の方向が割り当てられた場合には、各追加方向について元のキーポイントと同一の位置及びスケールを有する追加のキーポイントＫＰが作成される。
【００３４】
段階１１０の終わりにおいて、対応する座標Ｃ、キーポイントが抽出されるスケールＳ、キーポイントの主要な方向Ｏ及びピークＰ、すなわちそのようなキーポイントに対応するＤｏＧの絶対値（キーポイントのコントラストを示す）と共に、複数のキーポイントＫＰのセットがこのように生成される。
【００３５】
記述子生成（段階１２０）
続く段階１２０は、各キーポイントＫＰについて対応する記述子Ｄを計算するためにクエリ画像を処理することを提供する。問題の例においては、段階１２０において計算された記述子ＤはＳＩＦＴタイプの記述子である。キーポイントＫＰは画像位置、スケール及び回転に対する不変性を保証するような方法により抽出された一方で、ＳＩＦＴ記述子Ｄは非常に特徴的であって照明及び視点に対して部分的に不変であるような方法により計算される。具体的には、各キーポイントＫＰについて、キーポイントＫＰ位置に中心を置かれキーポイントＫＰの主要な方向に従って方向付けられている４×４グリッド上において１６個のサブヒストグラムのセットが計算される。各サブヒストグラムは８つのビンを含み、各ビンは主要な方向に対して角度ｎ＊π／４（ｎ＝０，１，．．．７）を有する方向に対応する。サブヒストグラムの各ビンの度数は、そのようなビンにより識別される方向に沿って考慮されたそのようなサブヒストグラムに対応するグリッドセル（以下、サブ領域と呼ばれる）の輝度勾配に比例する。そのような方向ヒストグラムの値はアレイに配置され、キーポイントＫＰの記述子Ｄを形成する。それぞれ８つのビンを有する４×４＝１６個のサブヒストグラムが存在するため、記述子Ｄは１２８個のアイテムを有するアレイである。
【００３６】
本発明の概念は、ＳＩＦＴ記述子が異なる数のセル及び／又はヒストグラム毎の異なる数のビンを含むグリッド上において計算される場合にも適用されることが可能である。
【００３７】
さらに、問題の実施例においてＳＩＦＴタイプの記述子に参照が行われた場合であっても、例えば迅速ロバスト特徴（ＳＵＲＦ）及び方向付けられた勾配のヒストグラム（ＨＯＧ）、又は場合によっては他のもののような異なるタイプの記述子が使用された場合に同様の考慮が適用される。さらに、輝度勾配に関連するデータを含む記述子に対する参照が行われた場合及び以下において行われる場合であっても、異なるパラメータの勾配が考慮される場合に同様の考慮が適用される。実際に、当業者には良く知られている通り、輝度は色の物理的特性のうちの１つでしかない。そのため、輝度が画像分析目的のために考慮されるべき最良の（すなわち最も堅固な）物理的特性であると確認された場合であっても、例えばクロミナンス勾配、彩度勾配又は（輝度と彩度及びクロミナンスの両方を含む）色彩勾配にさえ関連するデータを含む、異なるタイプの記述子も考慮され得る。
【００３８】
既に上述した通り、画像分析動作の実行は非常に大きな量のデータの管理を伴う。実際に各キーポイントＫＰは、１２８個のアイテムの配列により形成される対応する記述子Ｄと共に、座標Ｃ、スケールＳ、主要な方向Ｏ及びピークＰを含む複数の局所的特徴（以下、全体的に参照符号ＬＦｋｐにより識別される）に関連付けられる。この目的のために、管理されるべき（例えば記憶及び／又は送信されるべき）データの全体量を削減するために、本発明の一実施形態による抽出手順１００は２つの手段、すなわち
１）複数のキーポイントＫＰの最適なサブセットＳＵＢを取得するために、（画像比較視点から）最も関連性がある複数のキーポイントＫＰを選択することにより、以前に生成されたキーポイントＫＰの数を削減する手段
２）複数の座標Ｃと複数の記述子Ｄの両方を適切に圧縮する手段
を提供する。
【００３９】
抽出手順１００の段階１３０は最適なサブセットＳＵＢの選択のために費やされ、段階１４０は記述子Ｄの圧縮のために費やされ、段階１５０は座標Ｃの圧縮のために費やされる。
【００４０】
複数のキーポイントの最適なサブセットの選択（段階１３０）
本発明の一実施形態によれば、最適なサブセットＳＵＢの選択は、クエリ画像１１５の各キーポイントの少なくとも１つの局所的特徴ＬＦｋｐ−座標Ｃ、スケールＳ、主要な方向Ｏ、ピークＰ及び記述子Ｄについて、少なくとも１つの対応する特徴関連確率ＦＲＰを計算し、その局所的特徴ＬＦｋｐの特徴関連確率ＦＲＰに基づくキーポイント関連確率ＫＲＰに従って複数のキーポイントＫＰをソートし、次に最も高いキーポイント関連確率ＫＲＰを有する複数のキーポイントＫＰを選択することにより実行される。
【００４１】
本発明の一実施形態によれば、一般的キーポイントＫＰの各局所的特徴ＬＦｋｐの特徴関連確率ＦＲＰは、対応する参照統計的分布Ｒｓｄを利用することにより計算され、参照統計的分布Ｒｓｄは既にベンチマーク画像データベース上において前もって統計的評価を実行した後に予め定められている。
【００４２】
参照統計的分布Ｒｓｄは、画像分析目的のために有用であると考えられる複数のキーポイントＫＰの局所的特徴ＬＦｋｐの統計的挙動を反映するような方法により作成される。
【００４３】
例えば、物体認識手順の場合においては、ベンチマーク画像データベースは複数の画像対を含むデータベースであり、各画像対は同一の物体／場面を示す２つのピクチャから構成される。本発明の一実施形態によれば、参照統計的分布は以下のように生成される。
【００４４】
最初に、複数のキーポイントがベンチマークデータベースの全ての画像から抽出される。次に、選択された局所的特徴の第１の統計的分布を生成するように、全ての抽出されたキーポイントの１つ又は複数のそのような選択された局所的特徴について第１の統計的分析が実行される。局所的特徴の第１の統計的分布のそれぞれは、複数の所定の局所的特徴値間隔（ビン）のそれぞれの範囲内に入るそのような局所的特徴の値を有する、ベンチマークデータベースの複数の画像から抽出された複数のキーポイントの全体の中から、キーポイントの数（キーポイント度数）を計数することにより取得されたヒストグラムの形式に配置される。次に、各画像対について、１つのピクチャの複数のキーポイントが別のピクチャの複数のキーポイントとマッチングされる。そのようなキーポイントの間のマッチングは、いずれの一致が正しく（正常値であり）いずれが正しくない（異常値である）かを識別するために、（画像特徴マッチングに基づく既知の画像比較手順の間の任意の１つのような）画像比較手順を使用して処理される。次に、特徴関連確率ＦＲＰを計算するために使用されるべき参照統計的分布Ｒｓｄを生成するために、同一の特徴又は以前に考慮された複数の特徴について第２の統計的分析が実行される。このとき、参照統計的分布Ｒｓｄの生成は、各ビンについて正常値に属しており前記ビンの範囲内に入る対応する局所的特徴の値を有するキーポイントの数と、同一のビンの範囲内に入る対応する局所的特徴の値を有するキーポイント（正常値に属するものと異常値に属するものの両方）の総数との間の比率を計算することにより実行される。出願人は、第１の統計的分布と参照統計的分布Ｒｓｄが互いに極めて異なることを観察した。参照統計的分布Ｒｓｄは正しい特徴一致（正常値）を含む複数のキーポイントを考慮して生成されるため、出願人はそのような統計的分布が画像分析目的のために関連する複数のキーポイント（以下、「関連キーポイント」とする）の統計的挙動の良い見本であって、特に画像比較手順において効率的に使用されるのに適していることを発見した。
【００４５】
図２Ａ〜図２Ｆは、本発明のいくつかの例示的実施形態による複数のキーポイントＫＰの対応する選択された局所的特徴ＬＦｋｐのいくつかの統計的分布Ｒｓｄを示す。具体的には、図２Ａ〜図２Ｆの統計的分布Ｒｓｄは物体認識アプリケーションのために特に調整されたベンチマークデータベースの画像から生成された。例えば複数の異なるピクチャから開始する単一のパノラマピクチャの作成のような異なる画像分析アプリケーションが考慮される場合には、ベンチマークの画像は異なり、したがって結果として生じる統計的分布Ｒｓｄは異なるであろう。
【００４６】
図２Ａは、キーポイントＫＰの座標Ｃに関連する統計的分布Ｒｓｄである。対応するヒストグラムの各ビンは、一般的キーポイントＫＰの画像の中心からの（画素による）距離を表す。問題の実施例において、検討される画像はＶＧＡタイプの（すなわち６４０×４８０の解像度を有する）ものであり、そのため中心は座標（３２０，２４０）に対応する。図２Ａに示されたヒストグラムによると、最も高いキーポイントＫＰ度数を有するビンは画像の中心に対応するビンである。このことは、キーポイントＫＰがより中心に近くなるほどキーポイントＫＰが関連キーポイントである確率がより高くなり、中心からの距離が増加するとヒストグラム度数の傾向が単調に減少することを意味する。このことは、物体が写真撮影されるときに、前記物体は写真の中心においてフレームに入れられる可能性が高いという事実により容易に説明され得る。この場合において、ヒストグラムのビンは全て同一の幅を有しないことが十分に理解されなければならない。これは、各ビンの幅が少数のビンを計算するような方法により（スカラ及び／又はベクトル）量子化器により適切に決定され、これにより過剰適合現象発生が起こることを回避したという事実に起因する。本発明の概念は、（スカラ及び／又はベクトル）均一量子化が使用される場合、すなわちヒストグラムの全てのビンが同一の幅を有する場合にも適用される。
【００４７】
図２Ｂは、複数のキーポイントＫＰの主要な方向Ｏに関連する統計的分布Ｒｓｄである。対応するヒストグラムの各ビンは、（０ラジアンに対応する）水平に対して一般的キーポイントＫＰの主要な方向の角度を（ラジアンにより）表す。図２Ｂに示されたヒストグラムによれば、最も高いキーポイント度数を有するビンは、水平方向に平行又は垂直である方向に対応する（すなわち、π／２，０，−π／２，−πに対応する）ビンである。このことは、あるキーポイントＫＰの方向が前記方向のうちの１つにより近くなるほど、そのようなキーポイントＫＰが関連キーポイントである確率がより高くなることを意味する。このことは、ある物体が写真撮影されたときに前記物体が主に水平線に平行及び／又は垂直に伸びるようにフレームに入れられる可能性が高いという事実により説明され得る。この場合にも同様に、ビンの幅は量子化器によって決定される。
【００４８】
図２Ｃは、複数のキーポイントＫＰのピークＰに関連する統計的分布Ｒｓｄである。対応するヒストグラムの各ビンは、一般的キーポイントＫＰと隣接する複数のポイントの中で最も類似するポイントとの間のコントラストを表す。図２Ｃに示されたヒストグラムによれば、最も高いキーポイントＫＰ度数を有するビンは最も高いピーク値に対応するビンである。このことはキーポイントＫＰのコントラストがより高くなるほど、そのようなキーポイントＫＰが関連キーポイントである確率がより高くなり、コントラストが増加するとヒストグラム度数の傾向が単調に増加することを意味する。このことは、高いコントラストを有するピクチャの点が容易に認識可能かつ識別可能であるという事実により容易に説明され得る。この場合にも同様に、ビンの幅は量子化器によって決定される。
【００４９】
図２Ｄは、キーポイントＫＰのスケールＳに関連する統計的分布Ｒｓｄである。対応するヒストグラムの各ビンは、キーポイントＫＰが抽出され得る特定のスケールＳを表す。図２Ｄに示されるヒストグラムによれば、最も高いキーポイントＫＰ度数を有するビンは真ん中低めのスケールに対応する。この場合にも同様に、ビンの幅は量子化器によって決定される。
【００５０】
図２Ｅは、複数のキーポイントＫＰの記述子Ｄに関連する第１の統計的分布Ｒｓｄである。この場合において、対応するヒストグラムは三次元であり、その各ビンは一般的キーポイントＫＰの記述子Ｄの２つのパラメータの区間値、すなわち記述子Ｄの平均（ｘ軸）及び分散（ｙ軸）に対応する。より大きい度数値は、より大きい直径の円により示される。平均と分散は互いにリンクされているため、これらは同一のヒストグラムを形成するように一緒に考慮された。そのようなヒストグラムによれば、より大きい円により表される最も高いキーポイントＫＰ度数を有するビンは、最も高い平均及び最も低い分散に対応するビンである。このことは、あるキーポイントＫＰの記述子Ｄの平均がより高くなるほど、そのようなキーポイントＫＰに対応する輝度勾配がより高くなり、あるキーポイントＫＰの記述子Ｄの分散がより低くなるほど、そのようなキーポイントＫＰに影響を与える望まれないノイズがより低くなるという事実により説明され得る。
【００５１】
図２Ｆは、キーポイントＫＰの記述子Ｄに関連する第２の統計的分布Ｒｓｄである。この場合において、各ビンはあるキーポイントＫＰの記述子Ｄと同一の画像の他の複数のキーポイントＫＰの複数の記述子Ｄとの間の特定の最大距離に対応する。例えば、最大距離は複数の記述子の間のユークリッド距離に基づいて計算され得る。例えば、対称カルバック−ライブラー（Kullback-Leibler）発散を利用するなどの他の既知の方法も検討され得る。
【００５２】
図１に戻って、本発明の一実施形態によれば、抽出手順１００の段階１３０は、段階１１０において抽出された各キーポイントＫＰについて以下のものの計算を提供する。
【００５３】
−  前記キーポイントＫＰの座標Ｃに関連する統計的分布Ｒｓｄから取得された第１の特徴関連確率ＦＲＰ１。前記分布に対応するヒストグラムは前記キーポイントＫＰの座標Ｃに適合するそのビンを識別するために検査され、次に特徴関連確率ＦＲＰ１が識別されたビンのキーポイント度数に等しく設定される。
【００５４】
−  前記キーポイントＫＰの主要な方向Ｏに関連する統計的分布Ｒｓｄから取得された第２の特徴関連確率ＦＲＰ２。前記分布に対応するヒストグラムは前記キーポイントＫＰの主要な方向Ｏに適合するそのビンを識別するために検査され、次に特徴関連確率ＦＲＰ２が識別されたビンのキーポイント度数に等しく設定される。
【００５５】
−  前記キーポイントＫＰのピークＰに関連する統計的分布Ｒｓｄから取得された第３の特徴関連確率ＦＲＰ３。前記分布に対応するヒストグラムは前記キーポイントＫＰのピークＰに適合するそのビンを識別するために検査され、次に特徴関連確率ＦＲＰ３が識別されたビンのキーポイント度数に等しく設定される。
【００５６】
−  前記キーポイントＫＰのスケールＳに関連する統計的分布Ｒｓｄから取得された第４の特徴関連確率ＦＲＰ４。前記分布に対応するヒストグラムは前記キーポイントＫＰのスケールＳに適合するそのビンを識別するために検査され、次に特徴関連確率ＦＲＰ４が識別されたビンのキーポイント度数に等しく設定される。
【００５７】
−  前記キーポイントＫＰの記述子Ｄの平均と分散に関連する統計的分布Ｒｓｄから取得された第５の特徴関連確率ＦＲＰ５。前記分布に対応するヒストグラムは前記キーポイントＫＰの記述子Ｄの要素の平均と分散に適合するそのビンを識別するために検査され、次に特徴関連確率ＦＲＰ５が識別されたビンのキーポイント度数に等しく設定される。
【００５８】
−  前記キーポイントＫＰの記述子Ｄと他の複数のキーポイントＫＰの記述子Ｄとの間の最大距離（例えばユークリッド距離）に関連する統計的分布Ｒｓｄから取得された第６の特徴関連確率ＦＲＰ６。前記分布に対応するヒストグラムはそのような距離に適合するそのビンを識別するために検査され、次に特徴関連確率ＦＲＰ６が識別されたビンのキーポイント度数に等しく設定される。
【００５９】
したがって、各キーポイントＫＰについて、キーポイント関連確率ＫＲＰはその局所的特徴の特徴関連確率ＦＲＰのうちの少なくとも１つにより取得されるか、又はその局所的特徴の特徴関連確率ＦＲＰの中から特徴関連確率ＦＲＰを組み合わせることにより取得される。例えば、複数の特徴関連確率ＦＲＰが互い独立しているとの仮定により開始して、一般的キーポイントＫＰのキーポイント関連確率ＫＲＰはその対応する特徴関連確率ＦＲＰに互いに乗算んすることにより計算される。一般的に、キーポイント関連確率ＫＲＰを計算するために使用される異なる特徴関連確率ＦＲＰの数がより高くなるほど、そのような方法を使用することにより取得可能な結果はより良好になる。視覚的検索アプリケーションのためのＳＩＦＴ記述子の例を考慮することにより、キーポイント関連確率の計算のために考慮される特徴関連確率がスケール、ピーク及び中心からの距離に対応するものを少なくとも含むことが望ましい。
【００６０】
図２Ｇは、複数のキーポイントが、当該キーポイントの関連確率ＫＲＰに比例する直径をそれぞれ有する対応する円形スポットによって識別される例示的なピクチャである。
【００６１】
段階１１０において抽出された全てのキーポイントＫＰのキーポイント関連確率ＫＲＰが計算されると、前記キーポイントＫＰはキーポイント関連確率ＫＲＰが減少する順序に従ってある配列にソートされる。次に、（管理されるべきデータの量における所望の削減に基づいて）順序付けられた配列の最初のものから多数のキーポイントＫＰを取得することにより最適なサブセットＳＵＢが形成される。最適なサブセットＳＵＢに属する選択された複数のキーポイントＫＰは、結果として段階１１０において抽出された複数のキーポイントＫＰの全体の間において（画像比較視点から）最も関連性のある複数のキーポイントＫＰとなる。このように、データの全体の量の削減は、関連するキーポイントＫＰのみを考慮に入れて有用性が低いものを破棄して、洗練された効率的な方法により実行される。
【００６２】
上述された本発明の実施形態による最適なキーポイントのサブセットの選択は、その各ビンについて前記ビンの範囲内に入る対応する局所的特徴の値を有するキーポイント正常値と、同一のビンの範囲内に入る対応する局所的特徴の値を有するキーポイントの総数との間の比率を計算することにより取得された対応する統計的分布Ｒｓｄを利用する各特徴関連確率を計算することを提供するが、本発明の概念は異なる統計的に等価である、手作業でさえある異なる方法により取得される統計的分布が使用される場合においても適用可能であることが強調される。以下の説明において、２つの統計的分布は、それらが同一のキーポイントのセットから開始する類似の特徴関連確率を取得することを可能にする場合には、一方から他方に対して統計的に等価であると考えられる。
【００６３】
記述子の圧縮（段階１４０）
本発明の一実施形態によれば、記述子Ｄの圧縮は、削減された数の最適化されたコードブックを利用することにより、ベクトル量子化を通じて実行される。
【００６４】
図３Ａは、一般的キーポイントＫＰに対応するＳＩＦＴタイプの例示的な記述子Ｄ（最適なサブセットＳＵＢの一部であるように選択された、図１の抽出手順１００の段階１２０において生成された複数の記述子Ｄのうちの１つ）を示す。既に上述した通り、記述子Ｄは１６個のサブヒストグラムｓｈｉ（ｉ＝１，２，．．．，１６）を含み、各サブヒストグラムｓｈｉはキーポイントＫＰに近い画像の各サブ領域の輝度勾配が８つの方向に沿ってどのように分布するかを示す。具体的には、各サブヒストグラムｓｈｉは、キーポイントＫＰの位置に中心を置かれてキーポイントＫＰの主要な方向Ｏに従って方向付けられている４×４グリッドの１６のセルのうちの１つに対応するサブ領域に関連付けられている。各サブヒストグラムｓｈｉは８つのビンを含み、各ビンは主要な方向Ｏに対して角度ｎ＊π／４（ｎ＝０，１，．．．７）を有する方向に対応する。
【００６５】
図３Ｂに示される通り、記述子Ｄの全ての方向ヒストグラムｓｈｉの値は対応する記述子アレイに配置され、図中においては参照符号ＤＡにおり識別される。記述子アレイＤＡは１６個の要素ａｉ（ｉ＝１，２，．．．，１６）を含み、各ａｉは対応するサブヒストグラムｓｈｉ（ｉ＝１，２，．．．，１６）により取得された複数の値を格納する。次いで各要素ａｉはそれぞれの８つのサブ要素を含み、各サブ要素はサブヒストグラムｓｈｉの８つのビンのうちのそれぞれ１つに対応する度数値を格納する。このように、各記述子アレイＤＡは１６×８＝１２８個のサブ要素を含む。ＳＩＦＴ記述子Ｄにおいて典型的な度数値が０から２５５まで変動し得ることを考慮することにより、記述子アレイＤＡの各サブ要素はバイトにより表現され得る。したがって、記述子アレイＤＡのメモリ占有は１２８バイトに等しい。そのため、再度図１の抽出手順１００への参照を行うと、選択された最適なサブセットＳＵＢに属するキーポイントＫＰの全ての記述子Ｄに対応するデータの量は、（バイト数では）１２８が最適なサブセットＳＵＢのキーポイントＫＰの数により掛けられた数に等しい。
【００６６】
このデータの量を削減するために、そのような記述子Ｄに対応する記述子アレイＤＡはベクトル量子化を通じて圧縮される。
【００６７】
当業者に良く知られている通り、ベクトル量子化を利用することによるｎ個の要素（ｎ−タプル）により形成されるデータアレイの圧縮は、データアレイがより低い数のｎ−タプル値（これらの値は量子化されるべきセットの値からさえ異なり得る）を含む削減されたセットに仮定される全ての可能なｎ−タプル値のセットを一緒に量子化することを提供する。削減されたセットはより低い数のｎ−タプル値を含むため、より小さい記憶装置空間を必要とする。削減されたセットを形成するｎ−タプル値は、「コードワード」と呼ばれる。各コードワードは、当該アレイが仮定され得る異なるｎ−タプル値の対応するセットに関連付けられる。データアレイのｎ−タプル値とコードワードとの間の関連関係は、対応するコードブックによって決定される。
【００６８】
特に記述子アレイＤＡへの参照を行うと、記述子アレイＤＡは０から２５５まで変動する値をそれぞれ有する８つのサブ要素により順次形成された１６個の要素ａｉを含み、記述子アレイＤＡは異なる１６−タプル値の数Ｎ＝２５６１２８を採り得る。ベクトル量子化を通じた圧縮を適用することにより、そのようなＮ個の異なる１６−タプル値はコードブックのコードワードの数Ｎ１＜Ｎにより概算される。当該コードブックは、各コードワードと、記述子アレイＤＡの１６−タプル値の対応するセットとの間の関連関係を決定する。したがって、当該コードブックの各コードワードは、記述子アレイＤＡの１６−タプル値の対応するセットを「概算する」ために使用される１６−タプル値である。ベクトル量子化は損失の多いデータ圧縮であり、その正確性は歪みと呼ばれるパラメータを通じて測定され得る。歪みは、例えばコードブックの一般的コードワードと、そのようなコードワードにより概算されるアレイのｎ−タプル値のセットとの間のユークリッド距離として計算され得る。歪みが異なる方法により計算される場合においてさえ、同様の検討が適用される。いずれにせよ、大まかに言えばコードブックのコードワードの数Ｎ１が高くなるほど、圧縮の歪みは低くなる。
【００６９】
当業者には良く知られている通り、コードブックのコードワードの生成は、典型的には非常に多数の訓練アレイの集合を含む訓練データベース上において統計的演算（訓練演算と呼ばれる）を実行することにより実行される。特に記述子アレイＤＡへの参照を行うと、訓練データベースは数百万個の訓練記述子アレイを含み得、ここで各訓練記述子アレイは、記述子アレイＤＡが仮定し得るＮ＝２５６１２８個の可能な１６−タプル値のうちの１つである。
【００７０】
図４Ａに示された解決法によれば、全体の記述子アレイＤＡはＮ１個の１６−タプル値コードワードＣＷｊ（ｊ＝１，２，．．．，Ｎ１）を含む単一のコードブックＣＢＫを使用して圧縮される。したがって、Ｎ１個の異なるコードワードＣＷｊにより、コードワードを識別するために必要とされる最小数のビットはｌｏｇ２Ｎ１に等しい。既に上述した通り、そのような単一のコードブックＣＢＫのＮ１個の異なるコードワードＣＷｊの生成は、複数の訓練記述子アレイ上において訓練演算を実行することにより実行される。ここで、各訓練記述子アレイは、記述子アレイＤＡが仮定し得るＮ＝２５６１２８個の可能な１６−タプル値のうちの１つである。
【００７１】
後続の画像分析演算の結果を損なわないように十分に削減された閾値の下における圧縮歪みを維持するために、必要とされるコードワードの数Ｎ１は非常に大きくなり得る。余りに大きい数Ｎ１のコードワードにより形成されたコードブックを有することは、異なる視点の下においては不利益である。実際に、コードワードを生成するために使用されるべき訓練アレイの数は過剰になり、処理時間は余りに長くなるであろう。さらに、コードブックを利用することによる圧縮演算を実行するために、コードブックを形成する全体のＮ１個のコードワードは、無視できないほどの量のメモリ空間を占有してどこかに記憶されなければならない。画像分析アプリケーションのために使用されるハードウェア（例えばグラフィック処理装置、ＧＰＵ）には余り容量が大きくないメモリが備えられ得るため、無視できないほどの量のメモリ空間を占有するという欠点は非常に致命的である。
【００７２】
図４Ｂへの参照を行うと、歪みを増加させることなく管理されるべきコードワードＣＷｊの全体数を削減するために、記述子アレイＤＡは複数のサブアレイＳＤＡｋ（ｋ＝１，２，．．．）にさらに分割され得る。各サブアレイＳＤＡｋは記述子アレイＤＡのそれぞれの数ｍｋ個の要素ａｉを含み、次に各サブアレイＳＤＡｋはＮ２個のｍｋ−タプル値コードワードＣＷｊ（ｊ＝１，２，．．．，Ｎ２）を含む各コードブックＣＢＫｋを使用して個別に圧縮される。
【００７３】
図４Ｂに示された実施例において、記述子アレイＤＡは４つのサブアレイＳＤＡｋ（ｋ＝１，２，３，４）にさらに分割され、各サブアレイＳＤＡｋは記述子アレイＤＡのｍｋ＝４個の要素ａｉを含む。
【００７４】
−  第１のサブアレイＳＤＡ１は要素配列ａ１，ａ２，ａ３，ａ４により形成される。
【００７５】
−  第２のサブアレイＳＤＡ２は要素配列ａ５，ａ６，ａ７，ａ８により形成される。
【００７６】
−  第３のサブアレイＳＤＡ３は要素配列ａ９，ａ１０，ａ１１，ａ１２により形成される。
【００７７】
−  第４のサブアレイＳＤＡ４は要素配列ａ１３，ａ１４，ａ１５，ａ１６により形成される。
【００７８】
各サブアレイＳＤＡｋの圧縮は、Ｎ２個の４−タプル値コードワードＣＷｊ（ｊ＝１，２，．．．，Ｎ２）を含む各コードブックＣＢＫｙ（ｙ＝ｋ）を使用して実行される。したがって、４×Ｎ２の異なるコードワードＣＷｊにより、全てのコードワードを識別するために必要とされる最小のビット数は４×ｌｏｇ２Ｎ２に等しい。検討される場合において各サブアレイＳＤＡｋが同一の数Ｎ２個のコードワードＣＷｊを含むコードブックＣＢＫｙを使用して圧縮された場合であっても、各サブアレイＳＤＡｋがそれぞれの異なる数のコードワードＣＷｊを使用して圧縮される場合に同様の考慮が適用される。
【００７９】
図４Ｂに示される場合において、各コードブックＣＢＫｙのＮ２個の異なるコードワードＣＷｊの生成は、訓練記述子アレイの各サブセット上において訓練演算を実行することにより実行される。コードブックＣＢＫｋの訓練記述子アレイの各サブセットは４つのサブアレイＳＤＡｋのうちの１つに対応し、図４Ａの単一のコードブックＣＢＫを生成するために使用される各訓練記述子アレイから、サブアレイＳＤＡｋに対応するコードブックＣＢＫの部分のみを検討することにより取得され得る。例えば、コードブックＣＢＫ１を生成するために、図４Ａの単一のコードブックＣＢＫを生成するために使用される１６−タプル訓練記述子アレイの最初の４つの要素ａ１，ａ２，ａ３，ａ４のみが使用される。
【００８０】
記述子アレイＤＡ自体（１６個の要素）と同一の次元を有するコードワードＣＷｊにより形成される単一のコードブックＣＢＫを使用して全体の記述子アレイＤＡが圧縮される図４Ａの場合と比較すると、そのサブアレイＳＤＡｋの（より小さい）次元ｍｋ（例えばｍｋ＝４個の要素）を有するコードワードＣＷｊにより形成されるコードブックＣＢＫｙの使用は、同一の数のコードワードＣＷｊによってより小さい歪みを得ることを可能にする。
【００８１】
コードワードＣＷｊの総数を修正すると、記述子アレイＤＡがさらに分割されたサブアレイＳＤＡｋの数がより大きくなるほど歪みは小さくなるが、同時に全てのコードワードＣＷｊを識別するために必要とされる最小のビット数はより大きくなる。
【００８２】
本発明の一実施形態によれば、圧縮目的のためのサブアレイＳＤＡｋへの記述子アレイＤＡの細分割は、記述子アレイＤＡの複数の要素ａｉの間の相互関係の発生を考慮に入れることにより実行される。
【００８３】
図３Ａ及び図３Ｂを参照して既に説明した通り、記述子アレイＤＡの各要素ａｉは各サブ領域に関連付けられたサブヒストグラムｓｈｉにより採られる複数の値を格納し、そのサブ領域はそのような記述子アレイＤＡに対応するキーポイントＫＰに中心を置かれる４×４グリッドのセルに順次対応する。
【００８４】
図５に示される本発明の一実施形態によれば、（例えば訓練データベースの訓練記述子アレイを利用して）大量の記述子アレイＤＡについて統計的挙動分析を実行した後に、各相関ファミリーＣＦｘ（ｘ＝１，２，３，４）が類似の統計的挙動、すなわち類似のビン度数の傾向を有する相互に関連付けられたサブヒストグラムｓｈｉのセットを含んで、一般的キーポイントＫＰのサブヒストグラムｓｈｉが相関ファミリーＣＦｘに配置され得ることが発見された。例えば、同一の相関ファミリーＣＦｘに属する２つのサブヒストグラムｓｈｉは同一（又は類似）のビンにおいて類似の数の度数ピークを有し得る。
【００８５】
相関ファミリーＣＦｘを形成するために使用される統計的挙動分析は、記述子アレイＤＡの圧縮のために使用されるべきコードワードＣＷｊの最大数を修正すると、（異なる複数の相関ファミリーＣＦｘに複数のサブヒストグラムｓｈｉを割り当てることにより）相関ファミリーＣＦｘ内のサブヒストグラムｓｈｉの配置が変化させられた場合に、それに応じて結果として生じる歪みが変化することを示した。このように、相関ファミリーＣＦｘは全ての可能なサブヒストグラムｓｈｉ細分割の中で最も低い歪みに対応する細分割を検討することにより形成される。
【００８６】
そのような統計的挙動分析を実行した後に、２つのサブヒストグラムｓｈｉの統計的挙動の間の相関関係が２つの主要なパラメータ、すなわちキーポイントＫＰからのサブヒストグラムｓｈｉに関連付けられた複数のサブ領域の距離とキーポイントＫＰの主要な方向とに依存することも発見された。
【００８７】
図５への参照を行うと、キーポイントＫＰの１６個のサブヒストグラムｓｈｉは４つの相関ファミリー、すなわち
−  サブヒストグラムｓｈ１，ｓｈ４，ｓｈ１３及びｓｈ１６を含む第１の相関ファミリーＣＦ１と、
−  サブヒストグラムｓｈ２，ｓｈ３，ｓｈ１４及びｓｈ１５を含む第２の相関ファミリーＣＦ２と、
−  サブヒストグラムｓｈ５，ｓｈ８，ｓｈ９及びｓｈ１２を含む第３の相関ファミリーＣＦ３と、
−  サブヒストグラムｓｈ６，ｓｈ７，ｓｈ１０及びｓｈ１１を含む第４の相関ファミリーＣＦ４と
に配置される。
【００８８】
本発明の一実施形態によれば、上記の識別された相関ファミリーＣＦｘは削減された数の最適化されたコードブックＣＢＫｙを使用して記述子アレイＤＡを圧縮するために有利に利用される。サブアレイＳＤＡｋにおける記述子アレイＤＡの細分割は、少なくとも２つのサブアレイＳＤＡｋが同一の全体的な（すなわちそれらの全ての要素を考慮する）統計的挙動を有するような方法により実行される。この方法において、複数のサブアレイＳＤＡｋを圧縮するために単一のコードブックＣＢＫｙを使用することが可能である。この目的のために、記述子アレイＤＡの細分割は、各グループについてグループの全てのサブアレイＳＤＡｋにおいて同一の位置を占める要素ａｉが同一の相関ファミリーＣＦｘに属するサブアレイＳＤＡｋのグループ（複数可）を取得するような方法により実行される。したがって、同一のグループに属する全てのサブアレイＳＤＡｋは同一の対応するコードブックＣＢＫｙを使用して有利に圧縮され得て、コードブックＣＢＫｙのコードワードＣＷｊは、図４Ａの単一のコードブックＣＢＫを生成するために使用される各訓練記述子アレイから、グループのサブアレイＳＤＡｋの要素ａｉが属する相関ファミリーＣＦｘに属するその要素のみを検討することにより取得される。
【００８９】
図６Ａに示される本発明の例示的実施形態によれば、記述子アレイＤＡは、単一のグループに配置される４つのサブアレイＳＤＡ１〜ＳＤＡ４に細分割される。したがって、全てのサブアレイＳＤＡｋは同一のコードブックＣＢＫ１を使用して圧縮される。具体的には、
−  第１のサブアレイＳＤＡ１は、要素配列ａ１，ａ２，ａ６，ａ５により形成され、
−  第２のサブアレイＳＤＡ２は、要素配列ａ４，ａ３，ａ７，ａ８により形成され、
−  第３のサブアレイＳＤＡ３は、要素配列ａ１６，ａ１５，ａ１１，ａ１２により形成され、
−  第４のサブアレイＳＤＡ４は、要素配列ａ１３，ａ１４，ａ１０，ａ９により形成される。
【００９０】
この場合において、
−  各サブアレイＳＤＡｋの第１の要素ａｉは第１の相関ファミリーＣＦ１に属し、
−  各サブアレイＳＤＡｋの第２の要素ａｉは第２の相関ファミリーＣＦ２に属し、
−  各サブアレイＳＤＡｋの第３の要素ａｉは第４の相関ファミリーＣＦ４に属し、
−  各サブアレイＳＤＡｋの第４の要素ａｉは第３の相関ファミリーＣＦ３に属する。
【００９１】
一般的サブアレイＳＤＡ１〜ＳＤＡ４を圧縮するためのコードブックＣＢＫ１はＮ３個のコードワードＣＷｊを含み、ここで各コードワードＣＷｊは、第１の相関ファミリーＣＦ１に属する第１の要素と、第２の相関ファミリーＣＦ２に属する第２の要素と、第４の相関ファミリーＣＦ４に属する第３の要素と、第３の相関ファミリーＣＦ３に属する第４の要素を有する。
【００９２】
Ｎ３個の異なるコードワードＣＷｊにより、全てのコードワードを識別するために必要とされる最小のビット数は４×（ｌｏｇ２Ｎ３）に等しい。
【００９３】
図６Ｂに示される本発明の別の例示的な実施形態によれば、記述子アレイＤＡは単一のグループに配置される２つのサブアレイＳＤＡ１，ＳＤＡ２に細分割される。したがって、全てのサブアレイＳＤＡｋは同一のコードブックＣＢＫ１を使用して圧縮される。具体的には、
−  第１のサブアレイＳＤＡ１は、要素配列ａ１，ａ２，ａ３，ａ４，ａ５，ａ６，ａ７，ａ８により形成され、
−  第２のサブアレイＳＤＡ２は、要素配列ａ１３，ａ１４，ａ１５，ａ１６，ａ９，ａ１０，ａ１１，ａ１２により形成される。
【００９４】
この場合において、
−  各サブアレイＳＤＡｋの第１及び第４の要素ａｉは第１の相関ファミリーＣＦ１に属し、
−  各サブアレイＳＤＡｋの第２及び第３の要素ａｉは第２の相関ファミリーＣＦ２に属し、
−  各サブアレイＳＤＡｋの第５及び第８の要素ａｉは第３の相関ファミリーＣＦ３に属し、かつ
−  各サブアレイＳＤＡｋの第６及び第７の要素ａｉは第４の相関ファミリーＣＦ４に属する。
【００９５】
一般的サブアレイＳＤＡ１，ＳＤＡ２を圧縮するためのコードブックＣＢＫ１はＮ４個のコードワードＣＷｊを含み、ここで各コードワードＣＷｊは、第１の相関ファミリーＣＦ１に属する第１及び第４の要素と、第２の相関ファミリーＣＦ２に属する第２及び第３の要素と、第３の相関ファミリーＣＦ３に属する第５及び第８の要素と、第３の相関ファミリーＣＦ３に属する第６及び第７要素を有する。
【００９６】
Ｎ４個の異なるコードワードＣＷｊにより、全てのコードワードを識別するために必要とされる最小のビット数は２×（ｌｏｇ２Ｎ４）に等しい。
【００９７】
図６Ｃに示される本発明の別の例示的な実施形態によれば、記述子アレイＤＡは６つのサブアレイＳＤＡ１〜ＳＤＡ６に細分割され、それらのうちの４つ（ＳＤＡ１〜ＳＤＡ４）は第１のグループに配置され、それらのうちの２つ（ＳＤＡ５，ＳＤＡ６）は第２のグループに配置される。したがって、サブアレイＳＤＡ１〜ＳＤＡ４は同一の第１のコードブックＣＢＫ１を使用して圧縮され、一方サブアレイＳＤＡ５〜ＳＤＡ６は同一の第２のコードブックＣＢＫ２を使用して圧縮される。具体的には、
−  第１のサブアレイＳＤＡ１は要素配列ａ５，ａ１，ａ２により形成され、
−  第２のサブアレイＳＤＡ２は要素配列ａ８，ａ４，ａ３により形成され、
−  第３のサブアレイＳＤＡ３は要素配列ａ９，ａ１３，ａ１４により形成され、
−  第４のサブアレイＳＤＡ４は要素配列ａ１２，ａ１６，ａ１５により形成され、
−  第５のサブアレイＳＤＡ５は要素配列ａ６，ａ７により形成され、
−  第６のサブアレイＳＤＡ６は要素配列ａ１０，ａ１１により形成される。
【００９８】
この場合において、
−  第１のグループの各サブアレイＳＤＡ１〜ＳＤＡ４の第１の要素ａｉは第３の相関ファミリーＣＦ３に属し、
−  第１のグループの各サブアレイＳＤＡ１〜ＳＤＡ４の第２の要素ａｉは第１の相関ファミリーＣＦ１に属し、
−  第１のグループの各サブアレイＳＤＡ１〜ＳＤＡ４の第３の要素ａｉは第２の相関ファミリーＣＦ２に属し、
−  第２のグループの各サブアレイＳＤＡ５〜ＳＤＡ６の第１及び第２の要素ａｉは第４の相関ファミリーＣＦ４に属する。
【００９９】
第１のグループに属する一般的サブアレイＳＤＡ１〜ＳＤＡ４を圧縮するためのコードブックＣＢＫ１はＮ５個のコードワードＣＷｊを含み、ここで各コードワードＣＷｊは第３の相関ファミリーＣＦ３に属する第１の要素と、第１の相関ファミリーＣＦ１に属する第２の要素と、第２の相関ファミリーＣＦ２に属する第３の要素を有する。第２のグループに属する一般的サブアレイＳＤＡ５〜ＳＤＡ６を圧縮するためのコードブックＣＢＫ２はＮ６個のコードワードＣＷｊを含み、ここで各コードワードＣＷｊは第４の相関ファミリーＣＦ４に属する第１及び第２の要素を有する。
【０１００】
Ｎ５＋Ｎ６個の異なるコードワードＣＷｊにより、全てのコードワードを識別するために必要とされる最小のビット数は４×（ｌｏｇ２Ｎ５）＋２×（ｌｏｇ２Ｎ６）に等しい。
【０１０１】
図６Ｄに示される本発明の別の例示的な実施形態によれば、記述子アレイＤＡは８つのサブアレイＳＤＡ１〜ＳＤＡ８に細分割され、それらのうちの４つ（ＳＤＡ１〜ＳＤＡ４）は第１のグループに配置され、それらのうちの４つ（ＳＤＡ５〜ＳＤＡ８）は第２のグループに配置される。したがって、サブアレイＳＤＡ１〜ＳＤＡ４は同一の第１のコードブックＣＢＫ１を使用して圧縮され、一方サブアレイＳＤＡ５〜ＳＤＡ８は同一の第２のコードブックＣＢＫ２を使用して圧縮される。具体的には、
−  第１のサブアレイＳＤＡ１は要素配列ａ５，ａ１により形成され、
−  第２のサブアレイＳＤＡ２は要素配列ａ８，ａ４により形成され、
−  第３のサブアレイＳＤＡ３は要素配列ａ９，ａ１３により形成され、
−  第４のサブアレイＳＤＡ４は要素配列ａ１２，ａ１６により形成され、
−  第５のサブアレイＳＤＡ５は要素配列ａ６，ａ２により形成され、
−  第６のサブアレイＳＤＡ６は要素配列ａ７，ａ３により形成され、
−  第７のサブアレイＳＤＡ７は要素配列ａ１０，ａ１４により形成され、
−  第８のサブアレイＳＤＡ８は要素配列ａ１１，ａ１５により形成される。
【０１０２】
この場合において、
−  第１のグループの各サブアレイＳＤＡ１〜ＳＤＡ４の第１の要素ａｉは第３の相関ファミリーＣＦ３に属し、
−  第１のグループの各サブアレイＳＤＡ１〜ＳＤＡ４の第２の要素ａｉは第１の相関ファミリーＣＦ１に属し、
−  第２のグループの各サブアレイＳＤＡ５〜ＳＤＡ８の第１の要素ａｉは第４の相関ファミリーＣＦ４に属し、
−  第２のグループの各サブアレイＳＤＡ５〜ＳＤＡ８の第２の要素ａｉは第２の相関ファミリーＣＦ２に属する。
【０１０３】
第１のグループに属する一般的サブアレイＳＤＡ１〜ＳＤＡ４を圧縮するためのコードブックＣＢＫ１はＮ７個のコードワードＣＷｊを含み、ここで各コードワードＣＷｊは第３の相関ファミリーＣＦ３に属する第１の要素と、第１の相関ファミリーＣＦ１に属する第２の要素を有する。第２のグループに属する一般的サブアレイＳＤＡ５〜ＳＤＡ８を圧縮するためのコードブックＣＢＫ２はＮ８個のコードワードＣＷｊを含み、ここで各コードワードＣＷｊは第４の相関ファミリーＣＦ４に属する第１の要素と、第２の相関ファミリーＣＦ２に属する第２の要素を有する。
【０１０４】
したがって、Ｎ７＋Ｎ８個の異なるコードワードＣＷｊにより、全てのコードワードを識別するために必要とされる最小のビット数は４×（ｌｏｇ２Ｎ７）＋４×（ｌｏｇ２Ｎ８）に等しい。
【０１０５】
当然、本発明の概念は異なる数のサブアレイへの細分割及び／又は異なる数のコードブックによっても適用可能である。さらに、本説明の参照がヒストグラム毎に８つのビンを有する４×４個のセルを含むグリッド上において計算されるＳＩＦ記述子の圧縮に対して行われた場合であっても、セルの数及び／又はヒストグラム毎のビンの数が異なる場合には同様の考慮が適用されるだけでなく、他のタイプの記述子が考慮される。
【０１０６】
既知の解決法と比較して、同一の圧縮歪みを有する場合には、記述子アレイＤＡのサブアレイＳＤＡｋへの細分割と複数のサブアレイＳＤＡｋについての同一のコードブックＣＢＫｙの使用との組み合わされた使用は、記述子アレイＤＡを圧縮するために使用されるコードブック（複数可）ＣＢＫｙを格納するために必要とされるメモリ空間を大幅に削減することを可能にする。このことは、既に上述した通り画像分析アプリケーションのために使用されるハードウェア（例えばグラフィック処理装置、ＧＰＵ）には余り容量が大きくないメモリが備えられ得るため、大きな利点である。記述子アレイＤＡのサブアレイＳＤＡｋへの細分割と複数のサブアレイＳＤＡｋについての同一のコードブックＣＢＫｙの使用との組み合わされた使用により与えられる別の利点は、コードブック（複数可）ＣＢＫｙの生成のための訓練手順が結果としてより高速になることにある。
【０１０７】
受け取られた各記述子Ｄについて抽出手順１００の段階１４０（図１参照）において実行される圧縮動作は、結果として対応する圧縮された記述子アレイＣＤＡを生成し、圧縮された記述子アレイＣＤＡは各記述子アレイＤＡにより取得された値を概算する。より具体的には、記述子アレイＤＡを圧縮するために使用される各コードブックＣＢＫｙについて、そのようなコードブックＣＢＫｙの各コードワードＣＷｊは対応する圧縮インデックスＣｙにより識別される。コードブックＣＢＫｙがある数Ｎ個の異なるコードワードＣＷｊにより形成される場合には、圧縮インデックスＣｙは少なくともｌｏｇ２Ｎビットにより形成される。サブアレイＳＤＡｋのセットに細分割された記述子アレイＤＡについて、対応する圧縮された記述子アレイＣＤＡはセットの各サブアレイＳＤＡｋについて圧縮インデックスＣｙを含み、ここで各圧縮インデックスＣｙは前記サブアレイＳＤＡｋを概算するために使用されるコードブックＣＢＫｙのコードワードＣＷｊを識別する。
【０１０８】
座標の圧縮（段階１５０）
本発明の一実施形態によれば、画像分析動作を実行するために管理されるべき（例えば記憶及び／又は送信されるべき）データの量は、抽出手順１００の段階１３０（図１参照）において計算された最適なサブセットＳＵＢに属する複数のキーポイントＫＰの座標Ｃを圧縮することによりさらに削減される。
【０１０９】
図７Ａは、クエリ画像１１５に対応する二次元空間内の最適なサブセットＳＵＢの複数のキーポイントＫＰの例示的な分布を示す。各キーポイントＫＰは、クエリ画像１１５内のそのようなキーポイントＫＰの位置を識別する空間座標Ｃの対応する対に関連付けられている。
【０１１０】
最初に、サブセットＳＵＢの全てのキーポイントＫＰの座標Ｃが量子化される。この目的のために、ｎ×ｍのグリッドがクエリ画像１１５に重ね合わせられる。図７Ｂに示された実施例において、グリッドはｎ＝１０の行とｍ＝１５の列を有する。
【０１１１】
次に、（ヒストグラムのビンに対応する）グリッドの各セルについて、その中に存在するキーポイントＫＰの数を数えることにより二次元ヒストグラムが生成される。図７Ｃは、図７ＡのキーポイントＫＰのセットの上に図７Ｂのグリッドを重ね合わせることにより取得されたヒストグラムの例示的な図形的表現である。図７Ｃの図形的表現において、キーポイントＫＰを欠くセルは黒く着色されており、一方少なくとも１つのキーポイントＫＰを含むセルは灰色に着色されている。（最も多数のキーポイントを含むセルが２つのキーポイントを含む）問題の実施例において、単一のキーポイントＫＰを含むセルは暗灰色に着色されており、一方２つのキーポイントＫＰを含むセルはより薄い灰色に着色されている。
【０１１２】
キーポイント計数から得られたヒストグラムは、度数がゼロに等しい、すなわちいかなるキーポイントＫＰも含まない対応するセル（図７Ｃに示される黒いセル）を有する、多数のビンを有する。
【０１１３】
ヒストグラムを表すデータは、ゼロ度数のビンに対応するその部分が、対応するセルがいかなるキーポイントも含まないとの情報を提供するのみであることを考慮に入れて有利に圧縮され得る。
【０１１４】
この目的のために、いかなるキーポイントＫＰも含まないセルにより全体に形成されたグリッドの行及び列は有利に除去され得る。しかし、そのような行及び／又は列の除去はキーポイントＫＰの絶対的及び相対的位置を変更するであろうため、（除去されるべき行及び列に対応するものを含む）キーポイントＫＰを欠く全ての行及び／又は列の位置の表示が記録されるべきである。
【０１１５】
この目的のために、２つのアレイｒ及びｃは以下のように定義される。
【０１１６】
−  アレイｒはグリッドの各行のための要素を含むアレイであり、ここで当該グリッドの対応するセルがいかなるキーポイントＫＰも含まない場合にはアレイの一般的要素は第１の値（例えば０）に設定され、当該グリッドの対応するセルが少なくとも１つのキーポイントＫＰを含む場合にはアレイの一般的要素は第２の値（例えば１）に設定される。
【０１１７】
−  アレイｃはグリッドの各列のための要素を含むアレイであり、ここで当該グリッドの対応するセルがいかなるキーポイントＫＰも含まない場合にはアレイの一般的要素は第１の値（例えば０）に設定され、当該グリッドの対応するセルが少なくとも１つのキーポイントＫＰを含む場合にはアレイの一般的要素は第２の値（例えば１）に設定される。
【０１１８】
アレイｒ及びｃが生成されると、次のステップはいかなるキーポイントＫＰも含まないセルにより全体に形成された行及び／又は列を識別することを提供する。問題の実施例への参照を行うと、そのような行及び列は図７Ｄにおいて黒色により示されている。
【０１１９】
次に、いかなるキーポイントＫＰも含まないセルにより全体に形成されたグリッドの行及び／又は列は除去され、結果として生じるグリッドの部分は除去により残された空の空間を満たすために詰められる（compacted）。そのため、ランク１サポートと呼ばれる結果として生じる（詰められた）グリッドにおいて、全ての行と全ての列は少なくとも１つのキーポイントＫＰを含む少なくとも１つのセルを含む。問題の実施例に対応するランク１サポート上のヒストグラムは、図７Ｅに示される。
【０１２０】
そのようなヒストグラムから、２つの異なる情報の断片、すなわち
１）少なくとも１つのキーポイントＫＰを含むランク１サポートの複数のセルの位置と、
２）ポイント１）において識別されたランク１サポートの各セルについて、その中に含まれるキーポイントＫＰの数と
が抽出され得る
有利には、Ｓ．  Ｔｓａｉ、Ｄ．  Ｃｈｅｎ、Ｇ．  Ｔａｋａｃｓ、Ｖ．  Ｃｈａｎｄｒａｓｅｋｈａｒ、Ｊ．  Ｐ．  Ｓｉｎｇｈ及びＢ．  Ｇｉｒｏｄにより「Ｌｏｃａｔｉｏｎ  ｃｏｄｉｎｇ  ｆｏｒ  ｍｏｂｉｌｅ  ｉｍａｇｅ  ｒｅｔｒｉｅｖａｌ（移動体画像取り出しのための位置符号化）」Ｐｒｏｃ．  Ｉｎｔ．  Ｍｏｂｉｌｅ  Ｍｕｌｔｉｍｅｄｉａ  Ｃｏｎｆｅｒｅｎｃｅ  （ＭｏｂｉＭｅｄｉａ）、２００９年において提案されたように、ポイント１）に対応する情報はいわゆる「ヒストグラムマップ」を利用して抽出され得て、一方ポイント２）に対応する情報はいわゆる「ヒストグラムカウント」に配置され得る。
【０１２１】
ヒストグラムマップは、１以上の度数を有するヒストグラムのビンを識別するランク１サポート上のヒストグラムの二次元マッピングである。図７Ｅのランク１サポート上のヒストグラムに対応するヒストグラムマップは、図７Ｆに示される。
【０１２２】
ヒストグラムマップは対応する行列により表され得て、ランク１サポートの対応するセルがいかなるキーポイントＫＰも含まない場合に行列の一般的要素はゼロに等しく、ランク１サポートの対応するセルが少なくとも１つのキーポイントＫＰを含む場合に１に等しい。図７Ｆに示されるヒストグラムマップの行列は、以下のものである。
【０１２３】
【数１】
0005845361.tif 000002
【０１２４】
本発明の一実施形態によれば、ヒストグラムマップにより提供される情報は、多数の訓練画像の分析から学習された例示的なランク１サポートヒストグラムの統計的挙動に基づいて最適化されたエントロピー符号化を使用して有利に圧縮され得る。
【０１２５】
そのような分析から、一般的画像中のキーポイントＫＰの位置はヒストグラムマップの行列内の「１」の共通の統計的分布を必要とするようなものであることが発見された。
【０１２６】
エントロピー符号化は、以下のように実行される。
【０１２７】
ヒストグラムマップの行列が、それぞれ同一の長さｘを有する複数のワードに細分割されるように（例えば列毎に）スキャンされる。訓練画像上において実行された統計的分析に基づいて、一般的なワードのｘ−タプルが採り得る可能な各値について、ワードのｘ−タプルがそのようなビンに関連付けられた値を採る確率を示す各ビンの度数を有するビンを含むワードヒストグラムが生成される。簡潔には、そのような統計的分析はヒストグラムマップの行列の要素が互いに独立しているとの仮定を行うことにより実行された。非常に多数の訓練画像を分析することにより、行列においてｎ個の「０」毎に「１」が発生する確率がいずれであるかが識別され得る。次に、そのような確率に基づいてワードヒストグラムが生成される。
【０１２８】
図８Ａはワードの長さｘが６に等しいワードヒストグラムの例を示し、ここでは各ビンは対応するｘ−タプル値の十進値により識別される。期待される通り、ランク１サポートの一般的セルがいかなるキーポイントＫＰも含まない非常により高い確率が存在するため、最も高い度数はｘ−タプル（０，０，０，０，０，０）に対応する。以下の最も高い確率（ｘ−タプル（１，０，０，０，０，０），（０，１，０，０，０，０），（０，０，１，０，０，０），（０，０，０，１，０，０），（０，０，０，０，１，０），（０，０，０，０，０，１））はセルについての単一のキーポイントＫＰに対応するものであり、次にセルについての２つのキーポイントＫＰに対応するものなどである。
【０１２９】
ワードは、各ワードについて符号化されたワードｂｃｉ（ｉ＝１，２，．．．）を使用することによってエントロピー符号化技術（例えばハフマン技術又は算術符号化技術）により符号化される。ワードｂｃｉは、ワードヒストグラムにおける対応するビンの確率に依存する多数のビットを有する。ワードの確率が高くなるほど、そのようなワードを符号化するために使用される符号化されたワードｂｃｉのビット数は小さくなる。
【０１３０】
ランク１サポート上においてヒストグラムから抽出され得る他の情報は、少なくとも１つのキーポイントＫＰを含むヒストグラムマップの各セルに含まれるキーポイントＫＰの数を考慮する。そのような情報は対応するヒストグラムに配置され、ヒストグラムカウントと呼ばれる。ヒストグラムカウントの各ビンは、少なくとも１つのキーポイントＫＰを含むランク１サポートの複数のセルの中の対応する１つのセルに対応する。ヒストグラムカウントは、各ビンについて対応するセルに含まれるキーポイントＫＰの数をリストにする。問題の実施例のヒストグラムマップは図８Ｂに示され、ここでは１１個のセルがそれぞれ単一のキーポイントＫＰを含み、２つのセルがそれぞれ２つのキーポイントＫＰを含む。図８Ｂのヒストグラムマップのビンは、ランク１サポートの列方向スキャンに従って順序付けされる。
【０１３１】
ヒストグラムカウントにより提供されるキーポイント計数情報は、異なる長さの符号化されたワードｗｊ（ｊ＝１，２，．．．）のセットに符号化され、セットの符号化された各ワードｗｊはヒストグラムカウントビンの各セットのいずれのビン（複数可）が特定の値以上のキーポイントＫＰの数に対応するかを示す。
【０１３２】
より具体的には、各ビン内において計数された最も多いキーポイントＫＰの数がＮｍａｘに等しい場合には、そのような符号化されたワードｗｊのセットはＮｍａｘ−２に等しい数の符号化されたワードｗｊを含む。符号化された各ワードｗｊの生成は、Ｎｍａｘ−２個の手順ステップのセットの中の対応する１つのステップを実行することにより実行される。本発明の一実施形態によれば、そのような手順ステップは以下に説明される。
【０１３３】
ステップ１−  第１の符号化されたワードｗ１がヒストグラムマップの各ビンについて１つの要素を含むように設定される。そのため、第１の符号化されたワードｗ１はヒストグラムマップのビンの数に等しい数の要素を含む。ヒストグラムカウントの対応するビンが１より大きいキーポイントＫＰの数に対応する場合には、第１の符号化されたワードｗ１の各要素は第１の値（例えば「１」）に設定され、そうでない場合には第２の値（例えば「０」）に設定される。Ｎｍａｘが２より大きい場合には第２の符号化されたワードｗ２を生成するために第２のステップが実行され、そうでない場合には処理は終了させられる。後者の場合において、ヒストグラムカウントにより提供される全体の情報は結果として第１の符号化されたワードｗ１のみにより符号化される。
【０１３４】
ステップｊ（ｊ＞１）−  ｊ番目の符号化されたワードｗｊが生成される。ｊ番目の符号化されたワードｗｊは、ｊより多い数のキーポイントＫＰを含むヒストグラムマップの各ビンについて１つの要素を含むように設定される。したがって、ｊ番目の符号化されたワードｗｊはｊ−１番目の符号化されたワードｗ（ｊ−１）以下の数の要素を含む。ヒストグラムカウントの対応するビンがｊより大きいキーポイントＫＰの数に対応する場合にはｊ番目の符号化されたワードｗｊの各要素は第１の値に設定され、そうでない場合には第２の値に設定される。Ｎｍａｘがｊ＋１より大きい場合には（ｊ＋１）番目の符号化されたワードｗ（ｊ＋１）を生成するために（ｊ＋１）番目のステップが実行され、そうでない場合には処理は終了させられる。後者の場合において、ヒストグラムカウントにより提供される全体の情報は符号化されたワードｗ１〜ｗｊにより符号化される。
【０１３５】
抽出手順１００の段階１５０（図１参照）において実行される圧縮動作は、サブセットＳＵＢに属する複数のキーポイントＫＰの複数の座標Ｃについて、
−  アレイｒ及びアレイｃと、
−  符号化されたワードｂｃｉと、
−  符号化されたワードｗｊと
を含む対応する圧縮された座標セットＣＣを取得することを可能にする。
【０１３６】
圧縮された座標セットＣＣを管理する（記憶及び／又は送信する）ために必要とされるデータの量は、（非圧縮の）複数の座標Ｃのセットを管理するために必要とされるデータの量より目立って低い。
【０１３７】
マッチング手順（図９）
図９は、この発明の一実施形態による画像分析手順を機能ブロックの観点から示し、画像分析手順は以下「マッチング手順」と呼ばれて参照符号９００により識別され、図１の抽出手順１００により生成された複数の座標並びに複数のキーポイントのそれぞれ最適なサブセット及び対応する圧縮された記述子を各画像について利用することにより、２つの画像Ｉ１，Ｉ２の間の比較を実行することに向けられている。
【０１３８】
マッチング手順９００の複数のステップは、適切な処理装置により実行され得る。例えば、各処理装置は当該手順の１つ又は複数のステップを実行するように具体的に設計されたハードウェア装置であり得る。可能なシナリオは、画像比較サービス（サーバ側）を利用することを所望するユーザ（クライアント側）のために画像Ｉ１を画像Ｉ２と比較することを提供する。この場合においては、複数のキーポイントの最適なサブセット並びに対応する圧縮された複数の記述子及び複数の座標の生成のために、図１の抽出手順１００に従ってクライアントにおいて画像Ｉ１及びＩ２が処理され得る。次に、複数のキーポイントの最適なサブセット並びに対応する圧縮された複数の記述子及び複数の座標はサーバに送信され、サーバは受信されたデータを利用するマッチング手順９００を実行してその後結果をクライアントに提供する。この場合において、抽出手順１００は例えばユーザのスマートフォンによってクライアントに位置する処理装置により実行され得て、一方マッチング手順９００は例えば画像比較サービスを提供するように適応した１つ又は複数のサーバ装置によってサーバに位置する処理装置により実行され得る。別の可能なシナリオが、マッチング手順９００がクライアントにおいて直接実行されることを代わりに提供し得る。混合されたシナリオもまた考慮され、ここではマッチング手順９００がサーバにより送信された複数の圧縮された記述子及び複数の座標によりクライアントにおいて実行される。
【０１３９】
画像Ｉ１の圧縮された座標は参照符号ＣＣ１により識別され、一方画像Ｉ１の圧縮された記述子は参照符号ＣＤＡ１により識別される。同様に、画像Ｉ２の圧縮された座標は参照符号ＣＣ２により識別され、一方画像Ｉ２の圧縮された記述子は参照符号ＣＤＡ２により識別される。
【０１４０】
第１の画像Ｉ１の圧縮された記述子ＣＤＡ１は、対応する（解凍された）記述子Ｄ１を取り出すために解凍される（段階９０２）。同様に、第２の画像Ｉ２の圧縮された記述子ＣＤＡ２は、対応する（解凍された）記述子Ｄ２を取り出すために解凍される（段階９０４）。記述子の解凍は、抽出手順１００の段階１４０において実行される圧縮動作の逆のバージョンによって実行され得る。ＳＩＦＴタイプの記述子への参照を行うと、段階９０２及び９０４の後に記述子Ｄ１及びＤ２は１２８個のサブ要素により形成される対応する記述子アレイによりこのように表現される。
【０１４１】
段階９０６において、例えばユークリッド距離比試験のような当該技術において知られる特徴マッチングアルゴリズムの中の任意の１つを利用することにより、第１の画像Ｉ１の記述子Ｄ１と第２の画像Ｉ２の記述子Ｄ２との間において一致が形成される。
【０１４２】
次に段階９０８において、段階９０６において形成された一致の中のいずれの一致が正しく（正常値であり）、いずれの一致が正しくない（異常値である）かを確認するために、幾何学的検証動作が実行される。当業者には知られている通り、このタイプの動作は記述子に加えて各キーポイントの座標を必要とする。それら各キーポイントに対応する記述子は、別の１つのキーポイントの記述子に一致している。この目的のために、例えば抽出手順１００の段階１５０において実行される圧縮動作の逆のバージョンによって、画像Ｉ１の圧縮された複数の座標ＣＣ１と画像Ｉ２の圧縮された複数の座標ＣＣ２もまた解凍されるべきである。圧縮された複数の座標ＣＣ１の解凍に費やされる段階は図９において参照符号９１０により識別される一方、圧縮された複数の座標ＣＣ２の解凍に費やされる段階は図９において参照符号９１２により識別される。正常値が識別されると、幾何学的検証は画像Ｉ１とＩ２との間の一致の度合を示すパラメータＤＯＭを結果として提供し得る。例えば、そのようなパラメータＤＯＭが所定の閾値より高い場合には、画像Ｉ１及びＩ２は同一の物体（複数可）／場面（複数可）を示すと考えられる。
【０１４３】
加えて、２つの画像Ｉ１，Ｉ２中のそのような同一の物体（複数可）／場面（複数可）の位置（複数可）Ｌを取り出すために、局所化動作（段階９１４）がさらに実行され得る。
【０１４４】
前述したクライアント−サーバ画像比較シナリオへの参照を行うと、マッチング手順９００は削減された数のキーポイント（抽出手順１００によって生成されたサブセットＳＵＢに属するキーポイントのみ）により動作するように構成されており、かつそのような削減された数のキーポイントの記述子及び座標は圧縮された方法により受信されるため、提案される解決法によってクライアントからサーバに送信されるべき全体のデータの量は、既知の解決法と比較して目立って削減される。
【０１４５】
取り出し手順（図１０）
図１０は、以下において「取り出し手順」と呼ばれ、参照符号１０００により識別される本発明の一実施形態による画像分析手順を機能ブロックの観点から示し、その画像分析手順において、図１のクエリ画像１１５のような認識されるべき物体／場面を示すクエリ画像は、クエリ画像中に示された同一の物体／場面を示すモデル画像（複数可）を取り出すために、モデルデータベースに格納された複数のモデル画像と比較される。各モデル画像は、それぞれ既知の物体／場面を示す。
【０１４６】
図９のマッチング手順９００と同様に、取り出し手順１０００の複数のステップは適切な処理装置により実行され得る。例えば、各処理装置は手順の１つ又は複数のステップを実行するように具体的に設計されたハードウェア装置であり得る。典型的なシナリオは、クエリ画像１１５に示された物体／場面を自動的に認識するために画像認識サービス（サーバ側）を利用することを所望するユーザ（クライアント側）に備え得る。この場合において、クエリ画像１１５は複数のキーポイントの最適なサブセットＳＵＢ並びに対応する圧縮された複数の記述子ＣＤＡ及び複数の座標ＣＣの生成のために、図１の抽出手順１００に従ってクライアントにおいて処理され得る。次に、複数のキーポイントの最適なサブセット並びに対応する圧縮された複数の記述子及び複数の座標はサーバに送信され、サーバは受信されたデータを利用する取り出し手順１０００を実行して、その後クライアントに結果を提供する。クエリ画像１１５中に示された物体／場面の認識のために使用されるべき複数のモデル画像はモデルデータベース１００２に格納され、モデルデータベース１００２はサーバ側に位置する。
【０１４７】
圧縮された複数の記述子ＣＤＡは、対応する（解凍された）複数の記述子ＤＤを取り出すために解凍される（段階１００４）。記述子の解凍は、抽出手順１００の段階１４０において実行される圧縮動作の逆のバージョンによって実行され得る。再びＳＩＦＴタイプの記述子に対するモデルを作成して、段階１００４の後に記述子ＤＤはこのように１２８個のサブ要素により形成される対応する記述子アレイにより表される。
【０１４８】
典型的には標準的な物体認識手順はクエリ画像と非常に多数のモデル画像（例えば、モデルデータベース１００２に含まれるモデル画像は数百万枚であり得る）との間の比較動作の実行を必要とするため、そのような手順は多大な時間とメモリの両方を必要とする。この目的のために、既知の解決法は２つの明確な段階においてそのような比較動作を実行することを提供する。クエリ画像の記述子を全てのモデル画像の記述子と直接的に比較する代わりに、クエリ画像から抽出されたビジュアルワードとモデル画像から抽出されたビジュアルワードとの間により高速で大まかな比較が予備的に行われる。次に、記述子の（詳細な）比較が、予備的比較に基づいて選ばれた複数のモデル画像の削減されたセットの記述子とクエリ画像の記述子との間においてのみ実行される。ビジュアルワードは記述子のベクトル量子化を実行することにより得られるアレイであり、換言すれば各ビジュアルワードはビジュアルコードブックのコードワードである。ビジュアルワードの生成は、当該クエリ画像の各記述子と複数のモデル画像の各記述子について実行される。例えば、当該クエリ画像と各モデル画像との間において共通のビジュアルワードの数を計数することにより、予備的比較が実行される。次に各モデル画像について、共通のビジュアルワードの数のカウントに基づいて相似ランクが計算される。代替的な方法を使用してビジュアルワードを比較することにより相似ランクが生成された場合においては、同様の考慮が適用される。この方法において、複数の記述子の間の詳細な比較は、最も高い相似ランクを有するモデル画像（すなわち最も多数の、クエリ画像と共通のビジュアルワードを有するモデル画像）とクエリ画像の間においてのみ有利に実行され得る。このアプローチは、テキスト分析の分野から導出されたものであり、「特徴のバッグ（ＢｏＦ）によるランク付け」としても知られている。
【０１４９】
再度図１０への参照を行うと、ＢｏＦによるランク付けの実行を可能にするために、当該クエリ画像の各記述子についてのビジュアルワードＶＤと各モデル画像の各記述子についてのビジュアルワードＶＤＲが生成されなければならない。
【０１５０】
複数のビジュアルワードの間の比較を可能にするために、ビジュアルワードＶＤとビジュアルワードＶＤＲの両方は同一のコードブックを使用して生成されるべきであることが指摘される。
【０１５１】
演算回数を目立って削減するために、クエリ画像１１５のビジュアルワードＶＤは取り出し手順１０００が実行される度に毎回に生成されなければならない（段階１００６）一方で、複数のモデル画像のビジュアルワードＶＤＲの生成は一回のみ有利に実行され得て、その後結果として生じる複数のビジュアルワードＶＤＲはモデルデータベース１００２に直接的に格納され得る。代替的には、ビジュアルワードＶＤＲは周期的に更新され得る。
【０１５２】
クエリ画像の各記述子ＤＤについて対応するビジュアルワードＶＤを生成すると、次に段階１００８においてＢｏＦ手順によってランク付けが実行される。この方法により、各モデル画像について、クエリ画像のビジュアルワードＶＤでもあるそのようなモデル画像のビジュアルワードＶＤＲの数を計数することにより、ランク指数が計算される。そのような計数は、インバーテッドインデックス（Invertedindex）としても知られるＢｏＦの実施によって、既知のランキングを使用して実行され得る。しかし、異なる実施が適用される場合において同様の考慮が適用される。全てのランク指数が計算されると、ランク指数減少順に従ってデータベースのモデル画像がソートされるリストが生成される。次に、後続の（詳細な）比較動作の対象となるために、最も高いランク指数値を有する複数のモデル画像のセットＳＲが選択される。
【０１５３】
本発明の一実施形態によれば各画像の記述子の数は有利に削減されるため、関連性があると考えられる複数のキーポイントの最適なサブセットＳＵＢのみに対応して（図１の抽出手順１００の段階１３０参照）、作業メモリ（例えばサーバ側に位置するＲＡＭバンク）にロードされなければならない、ＢｏＦ手順によってランク付けを実行する（段階１００８）ために必要とされるデータの量は大きく削減され、処理の速度を目立って改善することが指摘される。さらに、比較は関連性があると考えられるキーポイントの記述子のみを考慮に入れて行われるため、ノイズが削減されるという理由により、比較の正確さは増加させられる。速度及び正確さをさらに改善するために、モデルデータベース１００２に含まれる各モデル画像について、削減された数の記述子を含む最適なサブセットもまた生成される。
【０１５４】
最適なサブセットＳＵＢを形成するキーポイントの数がＢｏＦによるランク付けの結果に大きく影響を与えることが発見された。実際に、同一の考慮される画像の数によれば、最適なサブセットＳＵＢのキーポイントの数が減少すると、クエリ画像１１５に示された物体／場面が複数のモデル画像の選択されたセットＳＲに属する少なくとも１つのモデル画像にも示される確率は増加する。しかし、そのような最適なサブセットＳＵＢのキーポイントの数がより低い閾値より下に下降すると、サブセットＳＵＢに含まれるキーポイントの数が各画像を満足に表現するには余りに小さくなるため、手順の性能は減少する。
【０１５５】
この点において、クエリ画像１１５と複数のモデル画像のセットＳＲとの間に第２の詳細な比較が実行される（段階１０１０）。既知の特徴マッチング手順のうちの１つが、例えば複数の記述子の間のユークリッド距離を計算することによって、クエリ画像１１５の複数の記述子ＤＤをセットＳＲのモデル画像の複数の記述子とマッチングするために利用され得る（サブ段階１０１２）。そして次に、いずれのマッチングが正常値であっていずれが異常値であるかを確認するために、幾何学的検証が実行される（サブ段階１０１４）。この方法により、クエリ画像１１５にも示される物体／場面を示すセットＳＲのモデル画像ＲＩが存在すれば、モデル画像ＲＩは本段階の最後に取り出される。
【０１５６】
本発明の一実施形態によれば、クエリ画像１１５の記述子ＤＤとセットＳＲのモデル画像の記述子とについて特徴マッチング動作を直接的に実行する代わりに、対応する記述子アレイをサブアレイに細分割して、ベクトル量子化に基づいてコードブックによって各サブアレイを圧縮することにより得られた記述子の圧縮されたバージョンについて、特徴マッチング動作が実行される。この目的のために、例えば対応する記述子アレイを４つのサブアレイに細分割して前記４つのサブアレイのそれぞれをそれぞれのコードブックにより圧縮することにより、クエリ画像１１５の記述子ＤＤが段階１０１６において圧縮される。ビジュアルワードの生成と同様に、モデルデータベース１００２は、各モデル画像について、対応する予め計算されたモデル画像の圧縮されたバージョンを格納する。モデル画像の圧縮されたバージョンは、クエリ画像１１５の記述子ＤＤを圧縮するために使用されたものと同一のコードブックを使用して圧縮された。本実施形態によれば、特徴マッチング（サブ段階１０１２）は非常に高速かつ効率的な方法により実行され得る。実際に、特徴マッチングは（クエリ画像の記述子とモデル画像の記述子の両方が圧縮されている）圧縮された空間において実行され、考慮されるべき記述子の数は（最適なサブセットのキーポイントのみに対応して）削減されているため、モデルデータベースのモデル画像を表すデータをもメインメモリに直接ロードすることが可能である。さらに、記述子アレイの圧縮は記述子アレイをサブアレイに細分割することにより実行され、これにより対応するコードブックのコードワードの数を大きく削減するため、各コードブックの各コードワードの間の全ての可能性があるユークリッド距離を含むリストが前もって予め計算されてメインメモリにロードされ得て、サブ段階１０１２の速度をさらに増加させる。特徴マッチングがユークリッド距離の使用を行わない異なるアルゴリズムを利用することにより実行される場合には、同様の考慮が適用される。
【０１５７】
本発明の一実施形態によれば、サブ段階１０１２は、図１の抽出手順１００の段階１４０において使用されるものと同様のアプローチを使用して、同一のコードブックを使用する各記述子のサブアレイを圧縮することによりさらに改善され得る。
【０１５８】
幾何学的検証（サブ段階１０１４）は、記述子に加えて、その対応する記述子が別のキーポイントの記述子に一致したキーポイントの座標を必要とするため、クエリ画像１１５のキーポイントの圧縮された座標ＣＣもまた解凍されるべきである（段階１０１８）。
【０１５９】
ここまでの説明は、本発明のいくつかの実施形態を詳細に提示及び論述する。それにもかかわらず、添付の特許請求の範囲に定義された範囲から逸脱することなく、説明された実施形態に対するいくつかの変更並びに異なる発明実施形態も可能である。
【図１】
0005845361.tif 000003
【図２Ａ】
0005845361.tif 000004
【図２Ｂ】
0005845361.tif 000005
【図２Ｃ】
0005845361.tif 000006
【図２Ｄ】
0005845361.tif 000007
【図２Ｅ】
0005845361.tif 000008
【図２Ｆ】
0005845361.tif 000009
【図２Ｇ】
0005845361.tif 000010
【図３Ａ】
0005845361.tif 000011
【図３Ｂ】
0005845361.tif 000012
【図４Ａ】
0005845361.tif 000013
【図４Ｂ】
0005845361.tif 000014
【図５】
0005845361.tif 000015
【図６Ａ】
0005845361.tif 000016
【図６Ｂ】
0005845361.tif 000017
【図６Ｃ】
0005845361.tif 000018
【図６Ｄ】
0005845361.tif 000019
【図７Ａ】
0005845361.tif 000020
【図７Ｂ】
0005845361.tif 000021
【図７Ｃ】
0005845361.tif 000022
【図７Ｄ】
0005845361.tif 000023
【図７Ｅ】
0005845361.tif 000024
【図７Ｆ】
0005845361.tif 000025
【図８Ａ】
0005845361.tif 000026
【図８Ｂ】
0005845361.tif 000027
【図９】
0005845361.tif 000028
【図１０】
0005845361.tif 000029