(57)【特許請求の範囲】
【請求項１】
以下の段階：
（ｉ）参照画像、即ちその各々が少なくとも単一の参照物体を表す画像、及び少なくとも１つのクエリ画像、即ち識別すべき未知の物体を表す画像の双方のための次の工程を含む特徴抽出段階：
（ａ）キーポイント、即ち顕著な画像領域の識別；
（ｂ）識別プロセスに有用ではないキーポイントを除去するキーポイントの後処理；
（ｃ）前記キーポイントの記述子、即ち表示のコンピュータ化（computation）、
（ｉｉ）以下の工程を含む参照画像のインデクス化段階：
（ａ）キーポイント抽出；
（ｂ）識別プロセスに有用ではないキーポイントを除去するキーポイントの後処理；
（ｃ）トレーニング画像の収集物から創出される視覚語語彙の視覚語へのキーポイントの割り当てであって、該視覚語はキーポイント記述子のクラスタの中心である上記割り当て；
（ｄ）前記参照画像の視覚語のすべての発生率を保存する各視覚語に対する一つのヒットリストを反転ファイル構築物が有し、各ヒットはキーポイントが検出される参照画像の識別子を保存する、反転ファイル構築物へのキーポイントの付加；
及び
（ｉｉｉ）次の工程を含む、前記クエリ画像に存在する物体の認識段階：
（ａ）キーポイント抽出；
（ｂ）識別プロセスに有用ではないキーポイントを除去するキーポイントの後処理；
（ｃ）視覚語語彙の視覚語へのキーポイントの割り当て；
（ｄ）クエリ画像からのキーポイントと、同じ視覚語に割り当てられるヒットのキーポイントの各々のペアに対して、前記ヒットの前記参照画像に対応するアキュムレータ（accumulator）へ票を集め；
（ｅ）該アキュムレータの票に基づいて前記参照画像に対応するマッチングスコアの識別；
を有し、
前記後処理が、
参照物体の対象である領域にしたがってキーポイントのスケールを標準化し；かつ
その標準化スケールに基づいて、前記識別プロセスに有効に寄与することができないキーポイントを除去する工程
を有することを特徴とする、画像中の物体の識別方法。
【請求項２】
前記（ｉｉｉ）物体の認識段階が、マッチングスコアにしたがってクエリに関連性ある物体又は複数の物体を選択する工程をさらに有する請求項１記載の方法。
【請求項３】
前記後処理が、検出されたキーポイントの位置に基づいて、対象である領域の自動検出を含む請求項１又は２記載の方法。
【請求項４】
参照画像の場合、対象である領域の中心が、検出されたキーポイントのすべての位置のセットの質量の中心として見積もられ、その初期幅及び初期高さは、キーポイント位置の標準偏差の関数として水平方向及び垂直方向に独立に算出され、前記キーポイント位置は、前記標準化キーポイントスケールにしたがって重み付けされ、前記初期幅及び初期高さは、対象の領域がキーポイントのない域をカバーするときはいつでも、縮む、請求項３記載の方法。
【請求項５】
キーポイントのスケールは、対象である領域の大きさの関数として標準化され、対象である領域外に位置するキーポイント及び所定値よりも小さい標準化スケールを有するキーポイントは除去される請求項３又は４記載の方法。
【請求項６】
段階（ｉｉ）及び段階（ｉｉｉ）は、物体の認識のプロセスにおいてその重要さを反映する、各キーポイントへの重み付け係数を伴うことを含み、該重み付け係数は前記標準化キーポイントスケールに基づく請求項１記載の方法。
【請求項７】
前記重み付け係数は、検出されたキーポイントのスケールに基づき、前記キーポイントスケールは前記標準化キーポイントスケールであり、かつ前記重み付け係数は、考慮したキーポイントと同じ視覚語に割り当てられ且つ類似の向き及びスケールを有する同じ画像からのキーポイントの数に基づく請求項６記載の方法。
【請求項８】
工程（ｉｉｉ）（ｄ）において、前記重み付け係数は、票を集めるプロセスに用いられ、該重み付け係数は、前記標準化キーポイントスケールに基づく請求項６又は７記載の方法。
【請求項９】
工程（ｉｉ）（ｄ）において、各ヒットは、キーポイントが検出された、参照画像の識別子並びにそのスケール及び向きについての情報を保存し、各ヒットは、入力画像の視覚語の発生率に応じて、対応する物体の存在を支持できる証拠の関連強さを有する、請求項１又は２記載の方法。
【請求項１０】
工程（ｉｉｉ）（ｄ）において、前記ヒットの前記参照画像に対応するアキュムレータが２次元テーブルとして実行され、該アキュムレータの一つの次元は前記参照物体の回転に対応し、他の次元は前記参照物体のスケーリングに対応し、各セルは参照物体のある回転及びスケーリングに対応し、票が特定の回転及びスケーリング変換を有する参照物体の出現に対するものである請求項９記載の方法。
【請求項１１】
工程（ｉｉｉ）（ｅ）において、各アキュムレータ内の最大数の票を有するセルを識別する請求項１０記載の方法。
【請求項１２】
工程（ｉｉｉ）（ｅ）において、最も高いマッチングスコアを有する参照画像が最も関連ある物体として選択される請求項１１記載の方法。
【請求項１３】
票の最大数を有するビン（bin）を識別するためにアキュムレータをスキャンし、それらの最大値に蓄積された票を最終的なマッチングスコア、即ちこれらの最大値が見出されたアキュムレータに対応する参照画像がいかにクエリ画像とマッチするかを示すスコアとして取り扱われる請求項１０記載の方法。
【請求項１４】
請求項１〜１３のいずれか１項記載の工程を実行するコンピュータプログラムコード手段を有するコンピュータプログラムであって、該プログラムがコンピュータで作動されるコンピュータプログラム。
【請求項１５】
請求項１〜１３のいずれか１項記載の工程を実行する手段を有するシステム。
【発明の詳細な説明】
【発明の背景】
【０００１】
技術分野
本発明は、マルチメディア内容検索（Content-based Multimedia Information Retrieval）［ＬＳＤＪ０６］及びコンピュータビジョンの分野に関する。特に、本発明は、内容に基づいて画像の大量の収集物をサーチする問題に関連するマルチメディア内容検索の領域、及び、コンピュータビジョンにおいて、ある画像又はビデオシーケンスに任意の物体を見出すタスクである物体認識（Object Recognition）の領域に寄与する。
【関連技術の説明】
【０００２】
画像の収集物においてある特定（同一）の物体を識別することは、現在、ある成熟期に達している［ＳＺ０３］。物体の外観は、視点、照明条件の変化により、又は部分的な遮りにより、異なるので、この問題は未だにやりがいがあるようであるが、小規模の収集物で比較的良好に実行される解決法が既に存在する。現在、存続する最大の障害は、複雑な背景内に『埋もれた』小さな物体を部分マッチングさせ、認識すること、及び本当に大規模な収集物を処理するのに必要なシステムのスケーラビリティにあるように思われる。
【０００３】
現在、認識性能の分野における関連する最近の進歩は、特に、高画質参照画像の大規模な収集物に基づいて、複雑なシーンにおける複数の小さな物体を迅速に識別することにおいて、議論されている。
【０００４】
９０年代後半、David Loweは、スケール不変特徴変換（Scale-Invariant Feature Transform）（ＳＩＦＴとして広く知られている）［ＬＯＷ９９］（米国特許６７１１２９３号）を提案したことにより、物体認識への新規なアプローチを開拓した。Ｌｏｗｅのアプローチにある基本的な考えは、極めてシンプルである。そのシーン（scene）からの物体を、いくつかの関心点（interest point）でその物体の外観を表現する局所記述子（local descriptor）（顕著な画像パッチ）により、特徴づける。局所記述子は、そのシーンに存在するスケール及び回転に不変である方法で抽出される。図１は、著しく異なる観点から同じシーンの２つの写真に対して検知した、ＳＩＦＴの関心キーポイント（interest key-point）［ＬＯＷ９９、ＬＯＷ０４］の例を示す。関心点を円で示す。円の中心はキーポイントの局在を示し、その半径はそのスケールを示す。ＳＩＦＴ関心点の直感的な解釈は、そのＳＩＦＴ関心点が小塊状（blob-like）又は角状（corner-like）構造に関連し、そのスケールが該構造の大きさと密接に関連することにある。見る角度に無関係に、キーポイントの多くは、そのシーンの同じ場所に検出されることに留意すべきである。オリジナル画像は、Mikolajczykらによって創出されたデータセットに属する［ＭＳ０４］。
【０００５】
参照物体の単一のトレーニング画像から抽出される記述子をその後用いて、新規画像（クエリ）内の物体のインスタンス（instance）を識別することができる。ＳＩＦＴ点に依存するシステムは、物が散らかったシーン内の物体を、そのスケール、向き、ノイズなどに無関係に、且つ観点及び照明の変化にある程度まで無関係に、堅牢性よく識別することができる。Loweの方法は、画像検索及び画像分類、物体認識、ロボット局在化（robot localization）、画像スティッチング（image stitching）並びにその他の多くを含む多くの応用を見出した。
【０００６】
ＳＩＦＴ法の性能に自信を持って、多くの研究者は、そのアプローチの可能性をさらにのばすことに研究を集中させた。例えば、Mikolajczyk及びSmith［ＭＳ０４］は、見る角度の変化に、先例のない堅牢性を可能とするアフィン共変検出子（affine covariant detector）を提案した。Matasら［ＭＣＵＰ０２］は、最大安定極値領域（Maximally Stable Extremal Regions）と名付けた特徴点を抽出する代替法を提案した。これは、ＳＩＦＴ検出子で選択される関心点とは異なる関心点を抽出する。かなり最近、Bayら［ＢＴＧ０６］は、高速化堅牢特徴（Speeded Up Robust Features）（ＳＵＲＦ）と名付けたＳＩＦＴ法のコンピュータ上有効なバージョンを提案した。驚くべきことに、ＳＵＲＦ検出子は、ＳＩＦＴ検出子よりも３倍速いだけでなく、いくつかの応用において、優れた認識性能を提供できる。ＳＵＲＦの応用の最も興味深い例の一つとして、２００の芸術品を含む屋内美術館の芸術作品の物体の認識にあり、８５．７％の認識率を提供する。
【０００７】
多くの応用域において、特徴点アプローチの成功は、実に壮観である。しかしながら、最近まで、画像の大量の収集物内の物体を有効に認識することができるシステムを組み立てることは未だ不可能であった。Sivic及びZissermanがテキスト検索システムを模倣する方法［ＳＺ０３、ＳＩＶ０６］で特徴点を用いることを提案したとき、この状況は改善した。彼らが“ビデオ・グーグル（Video Google）”と名付けた、このアプローチで、［ＭＳ０４］及び［ＭＣＵＰ０２］からの特徴点は、いわゆる視覚語（Visual Word）の語彙へとｋ平均（k-means）クラスタ化することにより量子化される（quantize）。結果として、各顕著な領域は、最も近い視覚語へと容易にマッピングすることができる。即ち、キーポイントは視覚語により表される。画像は、その後、『視覚語のバッグ（Bag of Visual Words）』（ＢｏＷ）として表され、これらは、その後のクエリ又は検索のインデクスへと入る。このアプローチは、画像の非常に大量な収集物で効率のよい認識を可能とする。例えば、４千画像の収集物からユーザによって選択される小領域の認識は、０．１秒でできる。
【０００８】
“ビデオ・グーグル”の結果は、当時入手可能な他の方法と比較すると特に、非常に印象的であったが、全体のシーン又は大領域を探索するのは、未だに非常に遅い。例えば、サイズが７２０×５７６ピクセルの画像を用いて表されるシーンを４千の画像の収集物内でマッチングさせることには約２０秒かかった［ＳＩＶ０６］。この限界は、Nister及び Stewenius［ＮＳ０６］により、ある程度まで緩和された。彼らは、より大量の収集物でのリアルタイム画像認識に近いことを行うことができる、高度最適化画像をベースとするサーチエンジンを提案した。特に、このシステムは、リアルタイムで、４万のＣＤ表紙について良い認識結果を提供できた。
【０００９】
最後に、非常に最近、Philbinら［ＰＣＩ＋０７、ＰＣＩ＋０８］は、“ビデオ・グーグル”アプローチの改善変形体を提案し、Flickr［ＦＬ１］から収集した高解像度（１０２４×７６８）の５千の画像の収集物から１１の異なるオックスフォード“ランドマーク”の画像を迅速に検索できることを例証した。
【００１０】
視覚物体認識の領域における最近の壮観な進歩は、産業から非常に興味を持たれはじめている。現在、いくつかの会社は、上述の進歩に、少なくとも一部、基づいた技術及びサービスを提供している。
【００１１】
Kooaba［ＫＯＯ］、ＥＴＨチューリヒからスピンオフし、ＳＵＲＦアプローチの発明者らによって２００６年末に設立された会社、は、物体認識技術を用いて、携帯電話からのデジタル・コンテントにアクセス及びサーチを提供する。Kooabaのサーチ結果は、クエリとして画像を送ることにより、アクセスする。彼らは、映画のポスター、新聞又は雑誌の記事などの現実世界の物体を、及び将来においては旅行者の見たことさえ、文字通り“クリック”できる技術と主張する。
【００１２】
パサディナ、カリフのエボリューション・ロボティックス（Evolution Robotics in Pasadena, Calif）［ＥＶＯ］は、ユーザが撮った写真の物体を認識でき、その後、広告者がそれを用いて、ユーザの携帯電話へ関連するコンテンツを売り込む、視覚サーチエンジンを開発した。彼らは、来る１０年に、携帯電話をかざすと、その前のすべてのものに視覚的にタグ付けられるであろう、と予言する。エボリューション・ロボティックスのアドバイザーの一人は、David Lowe博士であり、ＳＩＦＴアプローチ［ＬＯＷ９９］の発明者である。
【００１３】
アポロ（Apollo）画像認識システムを開発した会社である、スーパーワイズ・テクノロジーＡＧ（SuperWise Technologies AG）［ＳＵＰ］は、アイ-フォン（eye-Phone）と呼ばれる携帯電話の新規プログラムを開発した。これは、ユーザに、ユーザがいつでも、旅行者の情報を提供できるものである。換言すると、アイ-フォンは、ユーザが見ているときユーザが見ているものについての情報を提供できる。該プログラムは、今日の現代的なテクノロジーを３つ組み合わされている：衛星ナビゲーション位置確認サービス（satellite navigation localization services）、先進物体認識及び関連するインターネット検索情報。ユーザの電話にアイ-フォンがあると、例えば、外出散歩時、ユーザが携帯電話で写真を撮って、カーソルで関心のあるアイテムを選択することができる。選択された領域はその後、衛星ナビゲーション位置確認データで、物体認識を行い且つインターネットのデータベースとインターフェースで接続する中央システムへ転送され、該物体の情報が得られる。見出された情報は、該携帯電話に戻され、ユーザに表示される。
【００１４】
現存するアプローチは、関連性がある限界がある。ただ、現在、局所画像特徴に依存する方法は、写真に応答する結果を伝えるサーチエンジンに求められるほとんどの要求をほぼ満たしているように見える。
【００１５】
この方法のカテゴリに属し且つ画像１０枚の収集物でリアルタイム物体認識を行う第１のシステムの一つは、ＳＩＦＴ［ＬＯＷ９９、ＬＯＷ０４］の発明者であるDavid Loweにより提案された。このアプローチの第１の工程において、キーポイントは、ベスト-ビン-ファースト（Best-Bin-First）と呼ばれる最近接近傍系（nearest neighbours）を見出す近似法を用いる、参照画像から抽出したキーポイントのデータベースと独立にマッチングさせた。これらの初期のマッチングはさらに、ハフ変換（Hough transform）を用いる［ＨＯＵ６２］ポーズ空間（pose space）にクラスタ化することにより第２の段階で確認した。このシステムは、乱雑さと遮りの存在下での物体認識に非常に適切であろうと思われるが、画像１０枚よりも大規模な収集物に応じて調整することができるという文献の証拠はない。
【００１６】
スケーラビリティを改善するために、他の研究者は、テキスト検索システムを模倣する方法［ＳＺ０３、ＳＩＶ０６］で特徴点を用いることを提案した。Sivic及びZisserman［ＳＺ０３、ＳＩＶ０６、ＰＣＩ＋０７、ＰＣＩ＋０８］は、ｋ平均クラスタ化し且ついわゆる『視覚語の語彙（”Vocabulary of Visual Words”）』を創出することにより、キーポイントの記述子を量子化することを提案した。認識は２段階で行われる。第１の段階は、情報検索のベクトル空間モデルに基づいている［ＢＹＲＮ９９］。ここでは、視覚語の収集物が、クエリに対する画像の関連性のスコアである、標準の単語出現頻度−逆文書頻度（Term Frequency Inverse Document Frequency）（TF-IDF）をもって用いられる。これは、クエリに対して潜在的に関連性のある上位ｎ個の候補の初期リストという結果になる。典型的には、視覚語の画像位置についての空間情報は第１の段階で用いないということに留意すべきである。第２の工程は典型的には、キーポイントの空間情報を用いて候補の初期リストをフィルタリングする、空間一貫性チェック（spatial consistency check）のいくつかのタイプを含む。このカテゴリからのアプローチの大きな限界は、乱雑なシーンに『埋もれた』小さな物体を識別するのに特別には適していない、ＴＦ−ＩＤＦスコアの信頼性に端を発する。複数の小さな物体の識別には、初期にマッチングした候補のリストよりも大いに長いリストを受け容れることが必要である。初期段階のコストと比較すると、次に続く空間一貫性の確認がコンピュータ上高価であるため、これは、マッチングの総合的なコストの増大となる。また、ＴＦ−ＩＤＦスコアはその他の人によって製造された物体を含むシーンに共通する視覚語にしばしば割り当てられる物体の境界からのキーポイントによってしばしばバイアスが掛けられるので、これらのタイプの方法は、例えばソーダの缶、ＤＶＤボックスなどの多くのタイプの現実の商品の識別に適していないということが我々の経験から示されている。
【００１７】
空間一貫性の確認工程のコンピュータ上のコストのため、Nister及びStewenius［ＮＳ０６］は、大量のデータベースにスケールアップするためには重要であると彼らが示唆する、検索の原幾何学（pre-geometry）段階の質を高めるのに集中した。解法として、彼らは、視覚語のより効率的なルックアップを可能とする語彙ツリーを形成する、階層的に定義した視覚語を提案した。これにより、視覚語の幾何学レイアウトについて考慮することなく、その結果の質を改善する結果となることを示すより大規模な語彙を用いることができる。このアプローチは、大規模収集物に非常に良く調整できるが、マッチングすべき物体が画像のほとんどをカバーするときにだけ、うまく行くことがわかった。この限界は、ＴＦ−ＩＤＦスコアの変数の信頼性及び空間一貫性の確認の欠落により生じるようである。
【発明の概要】
【００１８】
本発明の目的は、テキスト言語の代わりに写真に対応した結果を届けるサーチエンジンを開発することにある。シナリオは、認識すべき物体を含むクエリ画像をユーザが供給する場面で仮定され、該システムは、大規模なコーパスから検索した、同じ物体を含む参照画像のランク付けられたリストを返す。特に、例えば、本、ＣＤ／ＤＶＤ、食品店のパック商品、街のポスター、新聞及び雑誌の写真、及び特有の商標を有するいかなる物体などの多くの魅力的な使用場面のシナリオに潜在的に関連性のある、広範囲の３Ｄ製品の認識に特に適する方法を開発するのが目的である。
【００１９】
代表的なクエリ画像は、複雑なシーン内に置かれ、認識すべき複数の物体を含むと予想される。また、クエリ画像として、低画質（例えば、携帯電話のカメラで撮られた）であるのは異常ではない。他方、各参照画像は、良い位置にあり且つただ一つの参照物体を含み、且つ比較的単純な背景を含むと仮定される。システムは、大量の参照画像（＞１０００）をインデクス化し、クエリ画像とインデクス化画像とを比較することにより、クエリ画像に存在する物体を迅速に（＜５秒）識別できることが望ましい。サーチエンジンは、クエリ画像の物体の位置、スケール、及び向きとは無関係に、意味ある結果を提供すべきであり、ノイズに対して、並びに視点及び照明の変化に対してはある程度まで、堅牢性があるべきである。最後に、サーチエンジンは、新規の物体をデータベースに迅速に（オンザフライ（on-the-fly））挿入できるべきである。
【００２０】
これらの目的の少なくとも一部に応じるために、本発明により、独立請求項の方法及びシステムが提供される。好ましい態様は、従属請求項に規定される。
【００２１】
提案する発明の基本的な考えは、視覚語の語彙及び反転ファイル構築物（inverted file structure）の我々の拡張を直接用いることにより、マッチングした視覚語間の空間一貫性の一部確認を行って、単一の工程でクエリ画像から物体を識別することである。
【００２２】
換言すると、提案する発明は、記述子を視覚語の語彙へクラスタ化することに依存する方法［ＳＺ０３、ＳＩＶ０６、ＮＳ０６、ＰＣＩ＋０７、ＰＣＩ＋０８］の例外的なスケーラビリティを、ハフ変換を用いる空間一貫性確認に依存する方法［ＨＯＵ６２、ＬＯＷ９９、ＬＯＷ０４］の乱雑さと部分的な遮りへの堅牢性と組み合わせる。ある観点から、本発明は、視覚語の語彙に基づくアプローチから、ベクトル空間モデル（ＴＦ−ＩＤＦスコア）に依存する初期認識段階を除外する試みとして見ることができ、その代わりに、マッチングした視覚語間の空間一貫性の確認を含む単一の工程で認識を行うことができる。他方、本発明は、［ＬＯＷ９９、ＬＯＷ０４］で提案された方法からの最近接近傍系近似サーチを、視覚語の語彙を用いるマッチングで置換する試みとしても見ることができる。
【００２３】
本発明は、各参照画像が、良い位置にある唯一の参照物体（即ちモデル）及び比較的単純な背景を含むと仮定することを、多くの応用シナリオにおいて受け容れられる、という事実を利用することを意図している。クエリ画像において物体の数及び背景の複雑さに関する仮定を一切行わないことに注意すべきである。これは、クエリ画像及び参照画像が、典型的には、その双方が、同じ方法で効率的に処理される、現存の方法と対照的である。また、本発明は、例えば、本、ＣＤ／ＤＶＤ、食品店のパック商品、街のポスター、新聞及び雑誌の写真、並びに特有の商標を有するいかなる物体などの多くの魅力的な使用場面のシナリオに潜在的に関連性のある、広範囲の３Ｄ製品の認識に良好に適する方法を開発することにあった。クエリ画像が、商標の共通するサブセットを有する商品のファミリに属する認識すべき物体を含む場合、例えば多くのコカコーラ商品がコカコーラのロゴを含む場合、該システムは、類似の商標を有する関連する商品の全てのランク付けしたリストを挙げるべきである。
【００２４】
実験で、本発明が認識性能の点で、特に高画質参照画像の大規模収集物に基づいて複雑なシーンの中から複数の小さな物体を迅速に識別するという面において、著しい進歩を残していることがわかる。
【００２５】
本願のアプローチは、局所画像特徴に依存する。全画像は、“顕著な”領域（キーポイント）に対してスキャンされ、各領域に対して高次元の記述子がコンピュータ化される。非常に低く且つ非常に高いスケールで検出されたキーポイントは除外され、参照画像の場合、キーポイントのスケールは、描写された参照物体の見積りサイズに関して標準化される。オフライン処理において、大多数の記述子の例が、記述子空間の量子化を定義する視覚語の語彙へとクラスタ化される。この瞬間から、すべてのキーポイントは、近接する視覚語へとマッピング化することができる。
【００２６】
しかしながら、このカテゴリの他のアプローチとは対照的に、画像は、視覚語のバッグ（Bags of Visual Words）としては表現されない。代わりに、［ＳＺ０３］で提案された反転ファイル構築物を拡張することを提案し、よく知られたハフ変換を模した方法で、ポーズ空間（pose space）におけるマッチングのクラスタを支持する。コンピュータコストを低く維持するため、ポーズ空間を向き及びスケールのみに限定するように提案する。反転ファイル構築物は、各視覚語へのヒットリストを有し、全ての参照画像の語についての全ての発生率（occurrence）を保存する。他のアプローチとは対照的に、各ヒットは、キーポイントが当初検出された参照画像の識別子だけでなく、そのスケール及び向きについての情報をも保存する。また、各ヒットは、関連する物体の存在をサポートすることができる証拠の関連強さを有する。ヒットの強さは、そのスケール（より高いスケールで検出されたキーポイントはより独特である）、同じ視覚語に割り当てられ且つ類似の向き及びスケールを有するヒットの数に基づいて算出される。類似の方法により、クエリ画像からの各キーポイントは、提供できる証拠の関連強さを有する。この場合、各強さは、同じ視覚語に割り当てられ且つ類似の向き及びスケールを有するクエリからのキーポイントの数だけに依存する。認識は、クエリ画像からのキーポイントを最近接の視覚語に割り当てることにより始まる。事実、この工程は、各クエリのキーポイントを同じ視覚語に関連するヒットのリスト全体に割り当てることと等価である。その後、キーポイントとリストからのヒットの一つとからなる各ペアは、ヒットが見出された参照画像が関連するポーズアキュムレータ（pose accumulator）に一票を投じる。キーポイント／ヒットの各ペアは、参照画像により表されるモデルの特異な向き及びスケールを予測する。各一票の強さは、キーポイント及びヒットの強さのドット成果物として算出される。全ての投票が一旦なされると、少なくとも一つの票を受け取るアキュムレータからのすべてのビン（bin）は、投票の最大数を有するビンを識別するために、スキャンされる。これらのビンに蓄積された値は、関連する参照画像の最終関連性スコアとして取り扱われる。最後に、参照画像は、関連性スコアにしたがって順番づけされ、最も関連性ある物体が［ＲＯＳ０１］からの動的しきい値法の拡張に基づいて選択される。
【００２７】
本発明のこれらの面及び他の面は、後述する態様から明らかになり、且つ後述する態様を参照することにより説明できるであろう。
【図面の簡単な説明】
【００２８】
本発明がより理解され、その多数の目的及び利点は、添付する明細書と共に以下の図を参照することにより、当業者に明らかになるであろう。
【図１】図１は、先行技術による画像のキーポイントの検出を示す。
【図２】図２は、本発明の態様による方法の概観を示し、主要構成要素の関係を示す。
【図３】図３は、図２に示す方法の物体認識プロセスの概観を示す。
【図４】図４は、図２に示す方法のインデクスプロセスの概観を示す。
【図５】図５は、本発明の方法に用いる反転ファイル構築物の一例を示す。
【図６】図６は、本発明の方法での小さな物体の識別の一例を示す。
【図７】図７は、本発明の方法での困難なポーズの物体の識別の一例を示す。
【図８】図８は、本発明の方法での遮られた物体の識別の一例を示す。
【図９】図９は、本発明の方法での乱雑なシーンにおける小さな物体の識別の一例を示す。
【図１０】図１０は、本発明の方法での複数の小さな物体の識別の一例を示す。
【図１１】図１１は、本発明の方法の産業用途の一例を示す。
【発明の詳細な説明】
【００２９】
例示する態様は、本発明にしたがった画像における特定の物体の識別方法について説明する。
【００３０】
提案するアプローチは、４つの主要な構成成分（段階）からなる。
１．特徴抽出は、“顕著な”画像領域（キーとなる点）の識別及びその表現（記述子）の算出を含む。図１を参照のこと。この段階は、認識プロセスに有用ではないキーとなる点が除外された、キーとなる点の後処理も含む。特徴抽出は、双方、即ち、参照物体を表す画像（参照画像）及び識別すべき未知の物体を表す画像（クエリ画像）に対して行われることに注意すべきである。
【００３１】
２．視覚語語彙の構築は、オフラインプロセスであり、多くの記述子の例が視覚語の語彙へとクラスタ化される。そのような語彙の役割は、記述子空間を量子化することにある。語彙が一旦創出されると、参照画像及びクエリ画像からのキーポイントは、最近接の視覚語へとマッピング化することができる。換言すると、キーポイントは、多次元記述子の代わりに、視覚語の識別子によって表すことができる。
【００３２】
３．参照画像のインデクス化は、参照画像の局所特徴の抽出及びクエリ画像から抽出した特徴と素早くマッチング化できる構築物へのその組織化を含む。このプロセスは、(i)キーポイントの抽出及び(ii)後処理、(iii)キーポイントの視覚語への割り当て、(iv)投票重み付けの見積り、及び(v)キーポイントをいわゆるヒットとしての反転ファイル構築物へ付加すること、からなる。図４のインデクス化プロセスの概観を参照のこと。新規の参照物体をデータベースに加えることは、キーポイントを表すヒットを反転ファイル構築物へ加えることを含む。反転ファイル構築物には、各視覚語に対しての一つのリスト（ヒットリスト）があり、参照画像におけるその語のすべての発生率（ヒット）を保存する。図５を参照のこと。各ヒットは、参照画像からの一つのキーポイントと関連し、キーポイントが検出された、参照画像の識別子並びにそのスケール及び向きについての情報を保存する。また、各ヒットは、入力画像中の視覚語の発生率に応じて関連する参照物体の存在をサポートすることができる、関連重み付け（強さ）を有する。
【００３３】
４．クエリ画像に存在する物体の認識は、次の工程からなる。(i)キーポイントの抽出及び(ii)後処理、(iii)キーポイントの視覚語への割り当て、(iv)各キーポイントに関連する、投票重み付けの計算、(v)ペア（クエリ・キーポイント、ヒット）によって提供される証拠を投票アキュムレータへ集合させること、(vi)各参照画像に関連するマッチングスコアの識別、及び最後に(vii)［ＲＯＳ０１］からの動的しきい値法の拡張に基づく最も関連性のある結果の順番づけ及び選択。認識プロセスの概観は、図３に見受けられる。
【００３４】
このアプローチの主要な構成要素間の関係又は “段階”間の関係を図２に例示する。語彙の創出、インデクス化及び認識は、特徴抽出工程を必要とすることに注意すべきである。また、インデクス化及び認識は、トレーニング画像の大規模な収集物から創出した視覚語の語彙を用いる必要がある。上述の段階を全て、以下に、より詳細に議論する。
【００３５】
特徴抽出及び後処理
局所特徴
提案するアプローチでは、画像は、非常に独特な局所特徴（キーポイント）のセットによって表される。この局所特徴は、データベースに保存し且つ比較することができる特異的且つ不変の特徴を有する、顕著な画像パッチとして見ることができる。換言すると、提案するサーチエンジンは、各画像は、その各々が特異的な位置、スケール、向き及び記述子を有するキーポイントのセットとして表現することが必要である。
【００３６】
物体認識に有用とするために、キーポイントは、物体の位置、サイズ、向き、ノイズ、乱雑さ並びに照明及びカメラの視点の変化に無関係で、一貫した方法で検出可能でなければならない。各画像に検出されるポイントの数は、そのシーンの潜在的に興味ある要素のすべてを表現するのに十分でなければならない。また、キーポイントの記述子は、異なる画像から関連するキーポイントを識別するのを促進するために、合理的に独特でなければならない。最後に、物体認識は、クエリ画像においてキーポイントのオンライン検出を含むため、コンピュータ上で効率よくなければならない。有用なキーポイントの例を図１に示す。
【００３７】
開発したプロトタイプでは、スケール不変特徴変換（ＳＩＦＴ）［ＬＯＷ９９、ＬＯＷ０４］（米国特許第6711293号）を用いて局所特徴を抽出した。しかしながら、提案するサーチエンジンは、例えば高速化堅牢特徴（ＳＵＲＦ）［ＢＴＧ０６］（欧州特許EP1850270）、最大安定極値領域（Maximally Stable Extremal Regions）［ＭＣＵＰ０２］又はアフィン共変検出子（Affine Covariant Detectors）［ＭＳ０４］などの他の代替表現で用いるとき、同じか又はより良好な性能を提供すべきである。
【００３８】
キーポイント後処理
行った実験から、キーポイントのすべてが物体認識に等しく有用であるとはいえないことがわかった。例えば、高解像度の画像の場合、最低限のスケールで検出されたキーポイントの多くは、識別力あるパターンを表さない（represent）が、異なるタイプのノイズ又は欠陥には単に対応する。
【００３９】
例えばＳＩＦＴのような、最も一般的に用いられる検出子は、キーポイントの数及び分析するスケールの範囲を、入力画像の解像度に合わせるために、コントローすることができる。このメカニズムは、表される物体のサイズに用いられるスケールの範囲に関連させることができない。これは、意味ある比較を保証するために、すべての参照画像がほぼ同じ解像度を有するべきであることを意味する。
【００４０】
この問題を緩和するために、付加的な後処理工程を行うことが提案される。(i)参照物体のサイズに応じてキーポイントのスケールを標準化し、(ii)標準化スケールに基づいて、認識プロセスに効率的に寄与できないキーポイントを除く。各参照画像は、参照物体の一例だけ及び比較的単純で且つ均一な背景を含むべきであると仮定される。キーポイントの多くは、参照物体に関連する域で検出されるべきである一方、背景は、著しい数のキーポイントを発生させるべきではない。そのような画像において、検出されたキーポイントの位置に基づいて、いわゆる対象となる領域（Region of Interest）（ＲＯＩ）を自動的に検出できる。単純さのために、長方形のＲＯＩのみを考慮する。
【００４１】
参照画像の場合、ＲＯＩの中央は、一連の検出されるキーポイントのすべての位置の質量の中心としてみなされる。その初期の幅及び高さは、キーポイント位置の標準偏差の値の４倍として、水平方向及び垂直方向に独立に算出される。ノイズ領域の影響を最小限にするため、キーポイント位置は、キーポイントのスケールに応じて重みづけられる。最後に、初期の境界は、いかなるキーポイントもない域をカバーするときにいつでも、調整される（“縮む”）。
【００４２】
ＲＯＩの対角線の長さを用いて、すべてのキーポイントのスケールを標準化する。ＲＯＩは、描写された物体のサイズのみに依存するため、それらは、画像解像度に独立した方法で、キーポイントのスケールを標準化するための理想的な参照を提供することに注意すべきである。
【００４３】
ＲＯＩが一旦識別されると、ＲＯＩの外側に位置するキーポイントは、排除される。その後、所定値よりも小さな標準化スケールを有するキーポイントも排除される。残りのキーポイントはすべて、その標準化スケールにしたがって種別され、最も大きなスケールを有する所定数のポイントだけが保持される。多くの応用において、参照画像のキーポイントの数を８００までに限定することにより、良好な結果がもたらされる。
【００４４】
クエリ画像の場合、単純な背景が期待できないので、そのＲＯＩは、画像全体をカバーするように設定する。次のキーポイントの後処理は、参照画像の場合と同様のスキームで続く。行われた実験により、クエリ画像のキーポイントの数を１２００までに限定することが、“乱雑なシーンに埋もれた”小さな物体の認識を確実にするのに十分であることがわかる。
【００４５】
上記の後処理工程及びスケール標準化工程がマッチング化プロセスの全体に重要な役割を果たし且つ高認識性能を確実にするのに重要であることは、強調すべきである。
【００４６】
視覚語語彙の構築
物体認識は、クエリ画像及び全参照画像からのキーポイント間の対応関係を確立することが必要である。参照画像の大規模な収集物の場合、キーポイント間の対応関係の徹底的なサーチは、コンピュータ上のコストの観点から、うまく行きそうにない。提案する解法において、可能性のある全てのキーポイント対応関係／マッチング間の徹底的なサーチを、［ＳＺ０３、ＳＩＶ０６］で議論される方法と同様な方法で、記述子空間をクラスタへ量子化することにより、避ける。この文献において、そのようなクラスタはしばしば、“視覚語”と呼ばれ、全視覚語の収集物はしばしば語彙と呼ばれる。語彙は、キーポイントを、最も類似する記述子を有する視覚語に割り当てることができる。この作業により、クエリ画像の各キーポイントが、同じ視覚語に対応する参照画像からのキーポイントの全リストに、効率的に割り当てられる。
【００４７】
実施したプロトタイプでは、よく知られたＫ平均クラスタ化により、量子化を行う。しかしながら、［ＮＳ０６］（米国特許第20070214172号）からの階層化Ｋ平均などの他のクラス化法を盛り込むこともできる。
【００４８】
クラスタ化は、ある任意の応答シナリオに代表的な画像からのキーポイントを用いることによりオフラインで行われる。画像の大規模な収集物を用いることにより、より一般的なディクショナリが提供され、より良好な認識性能をもたらす。しかしながら、視覚ディクショナリを創出するコンピュータ上のコストは、キーポイントの数に依存するため、利用可能な画像のサブセットだけをランダムに選択することがしばしば必要である［ＳＺ０３］。
【００４９】
クラスタの数（即ちディクショナリのサイズ）は、認識性能並びに認識及びインデクス化のスピードに影響する。より大きなディクショナリ（非常に小さな量子化セル）により、より独特なものを提供するが、ノイズの存在下の再現性が減ずるかもしれない。また、より大きなディクショナリは、創出するのがコンピュータ上高価であり、より遅い認識となる。［ＳＺ０３］に続いて、独特性、再現性及び認識スピードの良好なバランスをもたらす１００００視覚語を含むディクショナリを用いることを我々は選択した。
【００５０】
原則として、新規な参照画像を加えることは、視覚ディクショナリのアップデートに必要ではない。一方、参照画像の収集物において著しい変化があった後にディクショナリを再創出することにより、認識性能を向上させることができる。このようなディクショナリの再創出は、全参照画像の再インデクス化を含む。ディクショナリのアップデート及び再インデクス化の双方を、オフラインで行うことができる。
【００５１】
［ＳＺ０３、ＳＩＶ０６、ＮＳ０６］の示唆に続いて、非常に一般的な視覚語に割り当てられるキーポイントを認識プロセスから除去するメカニズムを盛り込んだ。この文献には、これらの非常に一般的な視覚語は、英語の’and’又は’the’のような非常に一般的な語が識別力のないテキスト検索問題とのある類似性のため、一般に“視覚停止語（visual stop word）”と呼ばれる。視覚語の頻度は、参照画像の収集物全体の発生率に基づいて算出される。頻度は、参照画像の収集物に著しい変化があるときはいつでも、アップデートできる。視覚語の所定のパーセンテージ（典型的には１％）が停止される。換言すると、最も一般的な視覚語に割り当てられるクエリ画像からのキーポイント（この場合、１００）が、認識プロセスで、考慮外となる。停止語を除去するのに用いられるメカニズムが、［ＳＺ０３、ＳＩＶ０６、ＮＳ０６］で提案されたものと微妙に異なることに注意すべきである。本願の場合、停止語は、参照画像のインデクス化に含まれる。停止語に割り当てられるクエリ画像からのキーポイントがマッチングプロセスから除去されるとき、停止語は、認識段階でのみ考慮に入れる。この解法により、収集物への追加により停止語が変化するとき、全データベースの再インデクス化を頻回に行うことを避けることができる。語停止メカニズムを盛り込むことによって、認識性能における改善が、行われた実験により示唆されるが、この拡張は、提案する認識エンジンの性能には重要ではない。
【００５２】
参照画像のインデクス化
一般的な表現において、参照画像のインデクス化は、クエリ画像から抽出した特徴との迅速なマッチング化が可能である、局所特徴の抽出及び構築物内のその組織化を含む。
【００５３】
インデクス化プロセスの概要を図４に示す。新規参照画像のインデクス化は、(i)キーポイント抽出及び(ii)“キーポイント後処理”の項で述べる後処理から始まる。次の工程で、(iii)抽出したキーポイントを最近接視覚語（即ち、それらを最もよく表現する語）に割り当てる。具体的には、各キーポイントは、最も類似する記述子を有する語彙から視覚語（クラスタ）に割り当てられる。全キーポイントが関連する視覚語で一旦表現されると、続く工程(iv)は、認識プロセスにおける各重要性（重み付け）が見積もられる。重み付けは、キーポイントのスケールに基づいて見積もられ、且つ同じ視覚語に属する同じ画像であって類似の向き及びスケールを有する同じ画像内のキーポイントの数に基づいても見積もられる。最後に、(v)全キーポイント及びその重み付けは、いわゆるヒットとしての反転ファイル構築物に付加される。
【００５４】
“特徴抽出及び後処理”の項で最初の２工程を述べたので、この項の残りは、インデクス化プロセスに特有な最後の３工程についてのみ詳細に述べる。
【００５５】
キーポイント分類化（Classification）
この工程では、画像からの各キーポイントを、最も類似する記述子を有する視覚語に割り当てる。これは、キーポイント記述子を視覚語の記述子と比較することを含む。現在の実施において、この割り当ては、語彙全体の徹底的なサーチにより行われる［ＳＺ０３、ＳＩＶ０６］。現在、これは、インデクス化プロセス及び認識プロセスの最もコンピュータ上集中的な（intensive）工程であることに注意すべきである。しかしながら、将来、［ＮＳ０６］で提案される方法のように迅速なキーポイント分類のための最も近年の方法を盛り込むことができるべきである
【００５６】
キーポイント重み付けの見積り
提案するアプローチにおいて、各キーポイントは、マッチングプロセスにおいてその重要性を反映する重み付け因子（強さ）を関連づけた。現在の実施において、この重み付けは、２つの主な因子に基づく：(i)キーポイントが検出されたスケール、及び(ii)考慮されたキーポイントと同じ視覚語に割り当てられ且つ類似の向き及びスケールを有する画像内のキーポイントの数。
【００５７】
キーポイントのスケールを重み付けに盛り込むことは、より高度なスケールで検出されるキーポイントが非常に低いスケールで検出されたキーポイントよりも識別力があるという事実によって動機づけられる。実際、非常に低いスケールで検出された多くのキーポイントは、そのシーンの重要ではない要素に関連する。そのようなキーポイントはしばしば、種々の参照画像の多くにおいて非常に一般的であるため、識別力が非常に乏しい。同時に、より高度なスケールで検出されたキーポイントは典型的には、そのシーンの大分部と関連し、より識別力を有する。
【００５８】
このような観察に基づいて、重み付けは、そこで検出されたキーポイントのスケールと比例するように選択された。具体的には、そこで検出されたキーポイントｉのスケールｓｉに対応する重み付け係数ｗｉＳは、次のように算出される。
【００５９】
【数１】
0005863786.tif 000002
【００６０】
式中、Ｔｓは、非常に高いスケールで検出されたキーポイントの影響を制限する、経験的に選択されるしきい値である。
【００６１】
第２の重み付け係数ｗｉＭは、同じ視覚語に割り当てられ且つ類似の向き及びスケールを有する同じ画像からのキーポイントのグループの影響を制限するために、導入される。具体的には、キーポイントｉに対する重み付け係数ｗｉＭは、次のように算出される。
【００６２】
【数２】
0005863786.tif 000003
【００６３】
式中、ＮｉＳは、ｉと同じ視覚語に割り当てられ且つ同じ向き及びスケールを有する同じ画像からのキーポイントの数を意味する。２つのキーポイントは、それらの向き及びスケール因子が経験的に決められたしきい値以下となる場合、同じ向き及びスケールを有するものとしてみなされる。
【００６４】
画像中の１以上のキーポイントが同じ視覚語により表現され且つ類似の向き及びスケールを有する場合が非常に一般的ではないので、重み付けｗｉＭは、認識プロセスでのそのようなグループの影響を調整するのに重要な役割を担う。その正確な役割は、投票スキームを記述する項目で詳しく説明する。
キーポイントｉに割り当てられる最終投票重み付けｗｉＫは、２つの上記重み付け係数に対する重み付けのドットプロダクト（dot product）として算出される。
【００６５】
【数３】
0005863786.tif 000004
【００６６】
上記重み付けの導入は、提案する解法において、非常に有効であることが証明された。しかしながら、他の重み付け係数及び／又は組合せが、類似の効果を達成できるであろう。
【００６７】
最後に、提案する重み付けスキームは、新重み付け係数の付加を容易に行える。将来、これにより、キーポイントの空間位置（例えば、画像の中心により近接するヒットをより重要性あるように割り当てることができる）又は向き（例えば画像内の非常に一般的な向きを有するキーポイントを重要性低く割り当てることができる）を盛り込むことができる。
【００６８】
反転ファイル構築物の構築
インデクス化段階の目的は、参照画像から抽出された局所特徴を、クエリ画像から抽出した特徴と迅速にマッチング化できるように、組織化することにある。［ＳＺ０３、ＮＳ０６］で示したように、迅速な物体認識のキーの一つとして、局所特徴をいわゆる反転ファイル構築物へと組織化することがある。興味深いことに、この解法は、［ＢＰ９８］に記載されるもののような、普及しているテキストサーチエンジンによって動機づけられた。テキスト検索の場合、反転ファイルは、各テキストの語に対して一つのエントリ（ヒットリスト）を有し、各リストは、全文書の語のすべての発生率を保存する。視覚サーチの場合、構築物は、全参照画像の語のすべての発生率を保存する各視覚語に対して一つのヒットリストを有する。辞書が参照画像の数に比較して十分大きい場合、ヒットリストは比較的短く、非常に迅速なマッチングをもたらすことに注意すべきである。
【００６９】
本アプローチにおいて、マッチング解法に好適である、反転ファイル構築物へのある拡張が盛り込まれた。［ＳＺ０３、ＮＳ０６］に示すように、反転ファイルには、参照画像全てにおける視覚語の全発生率（ヒット）を保存する各視覚語に対する１つのリストがある。図５を参照のこと。かつてのアプローチにあるように、各ヒットは、１つの参照画像からの１つのキーポイントに関連する。即ち、各ヒットは、それを記述する画像の識別子を保存する。しかしながら、本ケースにおいて、各ヒットは、キーポイントのスケール、向き及び票数についての付加情報も保存する。
【００７０】
該ヒットに保存される情報は、対比する画像の数を制限する（［ＳＺ０３、ＮＳ０６］に記載されるように）のに用いられるだけでなく、物体認識プロセスに中心的な役割を果たすことは、強調すべきである。
【００７１】
物体認識
クエリ画像に存在する物体の識別は、参照画像のインデクス化と同じ４工程で始まる。図３の認識プロセスの概観を参照のこと。このプロセスは、“特徴抽出及び後処理”の項で述べたように、（ｉ）キーポイント抽出及び（ｉｉ）後処理で始まる。次に、抽出したキーポイントは、（ｉｉｉ）視覚語に割り当てられ（より詳細のためには“キーポイント分類”を参照のこと）、全キーポイントの投票重み付けが算出される。クエリキーポイントを視覚語に割り当てることは、該キーポイントを同じ視覚語に伴うヒットの全リストに割り当てることと事実上等価であることに注意すべきである。上記４工程が一旦なされると、（ｖ）異なる参照画像に対する投票の集計が始まる。クエリ画像からのキーポイントと同じ視覚語に割り当てられたヒットの一つとの各ペアは、該ヒットが見出される参照画像に関連するポーズアキュムレータへ票を投じる。換言すると、各ペア（クエリキーポイント、ヒット）は、特異的な回転及びスケーリングを有して現出する参照物体の一つの存在に対して投票する。各票の強度は、クエリキーポイントの重み付けとヒットのドット生成物として算出される。すべての票が一旦投じられると、（ｖｉ）少なくとも１つの投票を受け取ったアキュムレータは、最大数の投票を有するビンを識別するために、スキャンされる。これらのビンで蓄積した値は、対応する参照画像に対する最終関連性スコアとしてみなされる。最後に、（ｖｉｉ）参照画像を、そのマッチングスコアにしたがって順番付けして、最も関連性ある物体を、［ＲＯＳ０１］の動的しきい値法の拡張に基づいて選択する。ここで、マッチングプロセスに特有の工程をより詳細に記載する。
【００７２】
キーポイント重み付けの見積り
クエリ画像の場合、キーポイントに伴う票重み付けは、同じ視覚語を伴い且つ類似のスケール及び向きを有する同じ画像中のキーポイントの数だけに基づいて算出される。よって、あるキーポイントｉに対する重み付け係数ｗｉＱＫは、次のように算出される。
【００７３】
【数４】
0005863786.tif 000005
【００７４】
式中、ＮｉＳは、ｉと同じ視覚語に割り当てられ且つ類似の向き及びスケールを有するクエリ画像からのキーポイントの数を意味する。
【００７５】
クエリ画像の場合、重み付けからスケールが除外されることにより、サイズに無関係に、シーンに存在する物体を認識できることに注意すべきである。同時に、参照画像からのヒットの重み付けにスケールを含めることにより、小物体を認識する能力に悪影響を及ぼさずに、典型的にはより識別力のあるヒットに、より重要性を与えられる。参照画像をインデクス化する“キーポイント重み付けの見積り”の項を参照のこと。
【００７６】
投票
投票の段階は、文献に記載される方法と比較して、提案アプローチのより特色ある構成成分である。主な概念は、視覚語語彙を用いるマッチングしたキーポイントと反転ファイル構築物との間に、ポーズ一貫性（回転及びスケーリング）をもたせることにある。本ケースにおいて、ヒットは、関連する参照画像の識別子（identificator）だけでなく、オリジナルのキーポイントの向き及びスケールについても保存するため、この解法が可能となる。この付加情報により、クエリ画像からのキーポイントと、異なる参照画像に関連するヒットとの間の回転及びスケーリングの見積りができる。換言すると、各マッチングの仮説（クエリキーポイントとヒットとのペア）に対して、参照物体の回転及びスケーリングを予想する変換エントリを創出することができる。
【００７７】
投票が始めることができる前に、１つの空の投票アキュムレータを各参照画像に割り当てる。該アキュムレータは、各呼び出し（ビン）が参照物体のある特定の回転及びスケーリングに対応する２次元テーブルとして実行する。この構築物は、参照物体のポーズ変換パラメータを単に量子化する。該アキュムレータの一つの次元は参照物体の回転に対応し、他の次元はそのスケーリングに対応する。
【００７８】
上記で説明したように、クエリ画像からのキーポイントに、ある視覚語を割り当てることは、同じ視覚語に対応する参照画像からのヒットのリスト全体に割り当てることに事実上等価である。割り当ての結果から得られるペア（クエリキーポイント、ヒット）により、マッチング仮説が提供される。
【００７９】
投票プロセスの間、各マッチング仮説（クエリからのキーポイントと、同じ視覚語に割り当てられたヒットの一つとのペア）は、該ヒットが見出された参照画像に対応するアキュムレータに票を投じる。また、そのような各ペア（クエリキーポイント、ヒット）は、一つの参照物体の存在に対してだけでなく、事実、特有の回転及びスケーリング変換を有する、その外観に対しても、投票する。
【００８０】
既に上述したように、重み付けスキームは、同じ視覚語に割り当てられ且つ類似の向き及びスケールを有するキーポイントの存在を説明する。この付加的な重み付け因子の理由は、投票スキームを詳細に分析することにより最も良好に説明することができる。理想的には、対応するキーポイントの一つのペア（一つのキーポイントはクエリ画像から、その他は参照画像から）は、参照画像に対応するアキュムレータに一票を投じるであろう。しかしながら、一つの参照画像からの複数のヒットが、同じ視覚語に割り当てられ且つ類似の向き及びスケールを有する場合、同じ視覚語に割り当てられた該クエリ画像からの各キーポイントは、同じアキュムレータ・ビンへ複数票（各々がそのようなヒットを有する）を投じる。例えば、参照画像が、同じ視覚語で表現され且つ同じ向き及びスケールを有する、３つのキーポイントを生じる場合、同じ視覚語に割り当てられるクエリからの各キーポイントは、（１票の代わりに）３票を同じアキュムレータ・ビンに投じる。この重み付けスキームは、そのようなグループによって投じられた複数票がマッチングスコアの算出に適当な役割を果たすことを、単に保証する。
【００８１】
スコアの算出
全ての票が一旦投じられると、最大数の投票を有するビンを識別するために、アキュムレータがスキャンされる。この最大に蓄積された票は、最終マッチングスコア、即ち、この最大値が見出されたアキュムレータに対応する参照画像がいかに良くクエリ画像とマッチングするかを示すスコア、としてみなされる。換言すると、ある任意のクエリに対して、各参照画像のマッチングスコアは、この参照画像に対応するアキュムレータに見出される票の最大数を有するビンに蓄積された投票を採用することにより得られる。これらのビンは、クエリ画像と関連する参照画像との間の、最も類似するポーズ変換（即ち、回転及びスケーリング）を表すことに注意すべきである。
【００８２】
提案アプローチが、クエリ画像において参照物体が存在するか又は存在しないかを検出するのに、主として意図されているのに注意すべきである。よって、各アキュムレータに最も投票されたビンだけを識別し、同じ参照物体の複数の発生率を無視するので十分である。同じ参照物体のポーズの全ての例を識別するには、対応するアキュムレータ中のすべての局所最大値を識別することを要することに注意すべきである。
【００８３】
関連する参照物体の順番付け及び選択
サーチの最終段階は、クエリ画像と関連する結果の順番付け及び選択を含む。多くの応用において、このタスクは、最高スコアを得た参照物体のささいな選択まで減ずることができる。
【００８４】
対照的に、本アプローチは、クエリに存在する複数の関連性ある物体を識別することができる。図１０の例の結果を参照のこと。物体の返されるリストは、得られたスコアにしたがって順番づけられる。また、システムは、関連ある物体がクエリ画像に存在しない場合に結果を全く返さない。
【００８５】
換言すると、この段階の目的は、先の段階で生じたマッチングスコアを用いて、クエリに存在する最も顕著な物体だけを識別することにあり、同時に関連のない結果を避けることにある。このアプローチの基本的な考えは、マッチングスコアにしたがって参照画像を順番付けし、その後、［ＲＯＳ０１］の動的しきい値法の拡張を用いて、仕分けしたリストからトップの物体だけを選択することにある。
【００８６】
動的しきい値を盛り込むことの動機付けは、関連ある物体で得られた代表的なスコアが広範囲に変化し得る（数少ないキーポイントを有するクエリに対しての〜４０から多数のキーポイントを有するクエリに対しての〜３００まで）という事実によって提供されるということに注意すべきである。そのような極端なケースに対して意味ある結果をもたらすであろう固定化しきい値を選択することができないので、スコアの順番付けしたリストによって創出された曲線の形状を用いて最も適切なしきい値を識別することを提案する。
【００８７】
動的しきい値の選択は、得られたマッチングスコア及び［ＲＯＳ０１］で提案されたしきい値法の応用にしたがって参照画像を仕分けすることから始まる。これにより、順番付けしたリストを２つのグループにする初期選別をもたらす：（ｉ）リストのトップにある潜在的に関連性ある物体、及び（ｉｉ）リストの残りにある、多分、関連性のない物体。この工程に続いて、潜在的に関連性のない物体を含むリストの第２の部分から、スコアの平均値を算出することが行われる。この値（Ｔｉｒという）は、現在のクエリ画像に関連性のない物体に代表的な参照スコアを提供する。動的しきい値Ｔｄは、Ｔｄ＝αＴｉｒとして算出される。式中、αの値は、経験上、４に設定される。最終しきい値Ｔｃは、Ｔｃ＝ｍａｘ（Ｔｄ、Ｔｆ）として算出される。式中、Ｔｆは、固定化しきい値であり、経験上、３０に設定され、それ以下では関連性ある結果と遭遇しそうではない、しきい値の最小値を提供する。Ｔｆは、代表的には非常に低いスコアとなるクエリに対して意味ある結果であって動的しきい値が関連性のない結果を返すことができるであろう結果を保証する。
【００８８】
最終しきい値Ｔｃが一旦算出されると、システムは、クエリ画像に存在するしきい値以上のスコアを得たトップの参照物体を分類する。
本発明は、一般目的のプロセッサに読み込んだ好適なコンピュータプログラムによって実行されるのが好ましい。
【００８９】
結果
図６〜１０は、本発明の最も興味深い能力を例示する、選択された結果を含む。全ての実験は、参照画像を７０有する収集物で行われた。代表的には、好結果となる識別に必要な時間は、標準ＰＣで実行した場合、２秒を超えない。また、認識時間は、参照画像の収集物のサイズと共に、非常にゆっくりと増大する。
【００９０】
図６は、小物体の識別の一例を示す。第一欄はクエリ画像を含み、残りの欄は、スコアにしたがって左から右へと順番付けした、検索済みの製品を含む。
【００９１】
図７は、むずかしいポーズを有する物体の識別の一例を示す（傾き：約４５°）。第一欄はクエリ画像を含み、残りの欄は、スコアにしたがって左から右へと順番付けした、検索済みの製品を含む。第二の検索済み製品がクエリ（“Juver”）と同一の商標を有することに注意すべきである。
【００９２】
図８は、遮られた物体の識別の一例を示す。第一欄はクエリ画像を含み、残りの欄は、スコアにしたがって左から右へと順番付けした、検索済みの製品を含む。
【００９３】
図９は、乱雑なシーンにおける小物体の識別の一例を示す。第一欄はクエリ画像を含み、残りの欄は、スコアにしたがって左から右へと順番付けした、検索済みの製品を含む。
【００９４】
図１０は、複数の小物体の識別の一例を示す。第一欄はクエリ画像を含み、残りの欄は、スコアにしたがって左から右へ及び上から下へと順番付けした、検索済みの製品を含む。
【００９５】
産業用途
提案する発明によって、テキスト言語に代わって、写真に応じて結果を届ける効率のよい認識エンジンの新規なタイプをもたらすことができる。このようなエンジンは、多数の産業用途に対してキーとなり得る技術となる潜在能力を有する。
【００９６】
携帯電話用用途
本発明の主な動機は、ユーザが携帯電話のカメラで写真を単に撮って、それを送信し、関連するサービスを受けることができるシステムのための巨大な商品的潜在能力を信じることによって提供された。図１１の本発明の具体的態様（“移動式視覚サーチ”）を参照のこと。このシステムにより、ユーザは、携帯電話のカメラで写真を単に撮って、それを送信し、関連するサービスを受けることができる。
【００９７】
提案する発明が、広範囲の３Ｄ製品（例えば、本、ＣＤ／ＤＶＤ、食料品店のパック商品）、街のポスター、新聞及び雑誌の写真、及び商標などを認識するのに非常に好適であることを保証するのに、多くの努力がなされた。上記性能により、携帯電話ユーザへの広範囲に亘る新規サービスを開発することができ、これにより、ユーザの好奇心を利用するか、及び／又はいわゆる衝動買いを促進させるであろう。ユーザがある製品についての情報をチェックする（例えば、価格比較）か、又はある特定の物体の写真を撮ることにより直接買い入れるという、多くの魅力ある使用ケースのシナリオを想像するのは容易である。このカテゴリのある例として、雑誌の広告（ads）の写真を撮ることによってオーディオビジュアルのコンテンツを買うこと、街のポスターの写真を単に撮ることによって音楽のコンサートのチケットを購入することが挙げられる。また、提案する発明は、魅力ある広告の新規なモデルを開発するのに大きな役割を果たすことができる。例えば、ユーザは、街で出会った広告の写真を撮ることによって抽選に参加することができる。
【００９８】
将来、提案する技術を、ジオロケーション（geolocation）と組み合わせて、ユーザがその携帯電話を掲げて写真を撮るだけで、現実世界のシーンについての情報をタグ付けし且つ検索することができる現実技術を増大させることができる。
【００９９】
他の応用
繰り返し検出（near-duplicate detection）
本発明は、著作権違反検出及び写真アーカイビング、例えば写真の収集物の組織化における応用を有する、繰り返し写真（near-duplicate photo）の検出に用いることができるであろう。
【０１００】
文脈上の広告
本発明は、コンテンツプロバイダによってもたらされ、文脈上の広告の新規モデルを導入する、画像及びビデオに現れる商標の検出に用いることができる。
【０１０１】
種々のメディア間をモニターする広告
本発明は、例えばテレビ及びインターネットなどの種々のタイプのメディアに亘る商品キャンペーンの自動モニター化を提供するツールのためのコア技術として用いることができる。このようなツールは、例えば、ある特定の商業キャンペーンの衝撃度を分析するために、商標又は特有のキャンペーンの特定の広告の発生率をサーチする、テレビ番組及びインターネットを自動的にモニターできる（双方のユーザはコンテンツ及びオンライン雑誌を創出した）。
【０１０２】
本発明を、図面及び上述の説明で、例示し且つ詳細に説明したが、そのような例示及び記述は、例証又は例示とみなされるべきであり、限定とみなすべきではない。本発明は、開示した態様に限定されない。
【０１０３】
請求する発明を実施する上で、当業者は、図面、開示、及び添付の特許請求の範囲を研究することによって、開示した態様への他の変形を理解し且つ実行することができる。請求項において、“有する”の語は、他の構成要素又は工程を除外しない。不定冠詞“a”又は“an”は、複数形を除外しない。単一のプロセッサ又は他のユニットが、請求項に挙げる、いくつかの構成の機能を満たすことができる。ある手段が互いに異なる従属項に記載されるという単なる事実は、これらの手段の組合せを用いて有利とできないことを意味するわけではない。コンピュータプログラムは、共に供給されるか又は他のハードウエアの一部として供給される光学保存メディア又はソリッドステートメディアなどの好適なメディアに保存／配置されてもよいが、インターネットを介して、又は他の有線もしくは無線遠距離通信システムを介してなどの他の形態で配置されてもよい。
【０１０４】
参考文献
[BL97]   J. Beis and D. G. Lowe. Shape indexing using approximate nearestneighbour search in high-dimensional spaces. In Conference on Computer Vision and Pattern Recognition, Puerto Rico, 1997.
[BP98]   S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. In Computer Networks and ISDN Systems, 1998.
[BTG06]  Herbert Bay, Tinne Tuytelaars, and Luc Van Gool. Surf: Speeded up robust features. In ECCV, 2006.
[BYRN99]   R. Baeza-Yates and B. Ribeiro-Neto. Modern information retrieval. In ACM Press, ISBN: 020139829, 1999.
[EVO]   Evolution. www.evolution.com.
[FLI]   Flickr. http://www.flickr.com/.
[HOU62]   P.V.C. Hough. Method and means for recognizing complex patterns. In U.S. Patent 3069654, 1962.
[KOO]   Kooaba. http://www.kooaba.com.
[LOW99]   D. Lowe. Object recognition from local scale-invariant features. In ICCV, 1999.
[LOW04]   D. Lowe. Distinctive image features from scale-invariant keypoints, cascade altering approach. In IJCV, 2004.
[LSDJ06]   M. Lew, N. Sebe, Ch. Djeraba, and R. Jain. Content-based multimedia information retrieval: State of the art and challenges. In ACM Transactions on Multimedia Computing, Communications, and Applications, 2006.
[MCUP02]   J. Matas, O. Chum, M. Urban, and T. Pajdla. Robust wide-baseline stereo from maximally stable extremal regions. In Proc. of the British Machine Vision Conference, Cardiff, UK, 2002.
[MS04]   K. Mikolajczyk and C. Schmid. Scale and affine invariant interest point detectors.In IJCV, 2004.
[NS06]   D. Nister and H. Stewenius. Scalable recognition with a vocabulary tree. In Proc. of the IEEE Conference on Computer Vision and Pattern Recognition, 2006.
[PCI+07]   J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman. Object retrieval with large vocabularies and fast spatial matching. In Proc. CVPR, 2007.
[PCI+08]   J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman. Lost in quantization: Improving particular object retrieval in large scale image databases. 2008.
[ROS01]   P. Rosin. Unimodal thresholding. In Pattern Recognition, vol. 34, no. 11, pp. 2083-2096, 2001.
[SIV06]   Josef Sivic. Efficient visual search of images and videos. In PhD thesis at University of Oxford, 2006.
[SUP]   Superwise. www.superwise-technologies.com.
[SZ03]   J. Sivic and A. Zisserman. Video google: A text retrieval approach to object matching in videos. In Proc. ICCV, 2003.
【図１】
0005863786.tif 000006
【図２】
0005863786.tif 000007
【図３】
0005863786.tif 000008
【図４】
0005863786.tif 000009
【図５】
0005863786.tif 000010
【図６】
0005863786.tif 000011
【図７】
0005863786.tif 000012
【図８】
0005863786.tif 000013
【図９】
0005863786.tif 000014
【図１０】
0005863786.tif 000015
【図１１】
0005863786.tif 000016