(57)【要約】      （修正有）【課題】画像の第１のシーケンス及び画像の第２のシーケンスを処理して比較する。【解決手段】第１のシーケンス内の複数の画像のそれぞれ、及び第２のシーケンス内の複数の画像のそれぞれについて、画像内の複数の画素近傍集合のそれぞれに対する画像データを処理し、前記画素近傍集合のそれぞれに対して少なくとも１つの記述子要素を生成し、各記述子要素は１つ又は複数のビットを含み、画像の記述子要素から、複数のワードであって、各ワードが記述子要素ビットの固有の組合せを含むような、複数のワードを形成する。第２のシーケンスに対するワードは、それぞれ、第１のシーケンスに対するワードと同じ組合せの記述子要素ビットから生成される。第１のシーケンス内の複数の画像に対して生成されるワードと、第２のシーケンス内の複数の画像に対して生成されるワードとを比較することによって、第１のシーケンスと第２のシーケンスとを比較する。【選択図】図２
2010191954.tif 000002
【特許請求の範囲】
【請求項１】
画像の第１のシーケンス及び画像の第２のシーケンスを処理して、前記第１のシーケンスと前記第２のシーケンスとを比較する方法であって、
前記方法は、
（ａ）前記第１のシーケンス内の複数の前記画像のそれぞれ、及び前記第２のシーケンス内の複数の前記画像のそれぞれを、
前記画像内の複数の画素近傍集合のそれぞれに対する前記画像データを処理することであって、前記画素近傍集合のそれぞれに対して少なくとも１つの記述子要素を生成し、各前記記述子要素は１つ又は複数のビットを含む、処理すること、及び
前記画像の前記記述子要素から、複数のワードであって、各前記ワードが記述子要素ビットの固有の組合せを含むような、複数のワードを形成すること、
によって処理することであって、
前記第２のシーケンスに対する前記ワードのそれぞれは、前記第１のシーケンスに対する前記ワードのそれぞれと同じ組合せの記述子要素ビットから生成される、処理すること、並びに、
（ｂ）前記第１のシーケンス内の前記複数の画像に対して生成された前記ワードと、前記第２のシーケンス内の前記複数の画像に対して生成された前記ワードとを比較することによって、前記第１のシーケンスと前記第２のシーケンスとを比較する処理を実施すること、
を含む、方法。
【請求項２】
前記第１のシーケンスと前記第２のシーケンスとを比較する処理は、前記第１のシーケンス及び前記第２のシーケンス内に異なるワード値が発生する頻度を比較する処理を含む、請求項１に記載の方法。
【請求項３】
前記第１のシーケンスと前記第２のシーケンスとを比較する処理は、
前記第１のシーケンスに対する発生データを生成するために、前記第１のシーケンス内の各前記ワードに対する各可能なワード値の発生回数を求めること、
前記第２のシーケンスに対する発生データを生成するために、前記第２のシーケンス内の各前記ワードに対する各可能なワード値の発生回数を求めること、及び
前記第１のシーケンスに対する前記発生データと、前記第２のシーケンスに対する前記発生データとを比較すること、
を含む、請求項１又は２に記載の方法。
【請求項４】
前記第１のシーケンスに対する前記発生データと、前記第２のシーケンスに対する前記発生データとが比較されて、各前記ワードについての比較結果が生成され、前記それぞれの比較結果はマージされて全体の比較結果を生成する、請求項３に記載の方法。
【請求項５】
各前記ワードに対して、双方のシーケンス内に発生する前記ワード値を求めること、
各前記ワードに対して、双方のシーケンス内における前記ワード値の時間的な発生順序を求めること、及び
前記時間的な発生順序を比較すること、
をさらに含む、請求項１〜４のいずれか１項に記載の方法。
【請求項６】
一致する画像対であって、前記第１のシーケンスからの１つの画像と前記第２のシーケンスからの１つの画像とを含む画像対を特定すること、及び
少なくとも１つの特定された画像対間の類似度を求めるために、さらなる対応性試験を実施すること
を含む、請求項１〜５のいずれか１項に記載の方法。
【請求項７】
画像を規定する画像データを処理して、前記画像を表す少なくとも１つの値を生成する方法であって、
前記方法は、
前記画像内の複数の画素近傍集合のそれぞれに対する前記画像データを処理することであって、前記画素近傍集合のそれぞれに対して少なくとも１つの記述子要素を生成し、各前記記述子要素は１つ又は複数のビットを含む、処理すること、及び
前記記述子要素から、少なくとも１つのワードであって、各前記ワードが１つ又は複数の前記記述子要素からの１つ又は複数のビットを含むと共に、前記ワードのすべてにおける総ビット数が前記記述子要素のすべてにおける総ビット数を下回るような、少なくとも１つのワードを形成すること、
を含む、方法。
【請求項８】
画像を規定する画像データを処理して、前記画像を表す複数の値を生成する方法であって、
前記方法は、
前記画像内の複数の画素近傍集合のそれぞれに対する前記画像データを処理することであって、前記画素近傍集合のそれぞれに対して少なくとも１つの記述子要素を生成し、各前記記述子要素は１つ又は複数のビットを含む、処理すること、及び
前記記述子要素から、複数のワードであって、各前記ワードが記述子要素ビットの固有の組合せを含むような、複数のワードを形成すること、
を含む、方法。
【請求項９】
前記方法は、各前記記述子要素を量子化するステップをさらに含み、
各前記ワードは、前記量子化された記述子要素から形成される、請求項７又は８に記載の方法。
【請求項１０】
各前記記述子要素を量子化する前記プロセスは、各前記記述子要素について１ビットの２値結果を形成するために各前記記述子要素を量子化することを含む、請求項９に記載の方法。
【請求項１１】
前記記述子要素は、複数の異なる画素解像度で前記画像に対して生成され、
異なる画素解像度で生成される前記記述子要素からの１つ又は複数のビットを組み合わせることによって、少なくとも１つのワードが生成される、請求項７〜１０のいずれか１項に記載の方法。
【請求項１２】
画像を規定する画像データを処理して、前記画像を表す少なくとも１つの値を生成する方法であって、
前記方法は、
前記画像内の複数の画素近傍集合のそれぞれに対する前記画像データを処理することであって、前記画素近傍集合のそれぞれに対して少なくとも１つの記述子要素を生成し、各前記記述子要素は１つ又は複数のビットを含む、処理すること、
各前記記述子要素を量子化すること、及び
前記量子化された記述子要素から前記画像を表す少なくとも１つの値を形成すること、
を含む、方法。
【請求項１３】
各前記記述子要素を量子化する前記プロセスは、各前記記述子要素について１ビットの２値結果を形成するために各前記記述子要素を量子化することを含む、請求項１２に記載の方法。
【請求項１４】
画像のシーケンスの表現を記憶する方法であって、
前記方法は、
請求項７又は８に記載の方法を実施することによって、前記シーケンス内の各前記画像に対する複数の記述子要素、及び前記シーケンス内の各前記画像を表す少なくとも１つのワードを生成すること、
いずれのワードが前記画像のシーケンス内に現れるか、及び現れる頻度を規定するヒストグラムデータを生成すること、並びに
前記シーケンス内の前記画像に対する前記ヒストグラムデータ、前記ワード、及び前記記述子要素を記憶すること、
を含む、方法。
【請求項１５】
前記方法は、各前記記述子要素を量子化することをさらに含み、
各前記ワードは、前記量子化された記述子要素から見つけられ、
前記方法は、前記ヒストグラムデータを量子化することをさらに含み、
前記量子化されたヒストグラムデータ、前記ワード、及び前記量子化された記述子要素が記憶される、請求項１４に記載の方法。
【請求項１６】
画像のシーケンスの表現を記憶する方法であって、前記方法は、
請求項１２に記載の方法を実施することによって、前記シーケンス内の各前記画像に対する複数の記述子要素、及び前記シーケンス内の各前記画像を表す少なくとも１つの値を生成すること、
前記画像を表すいずれの値が現れるか、及び現れる頻度を規定するヒストグラムデータを生成すること、
前記ヒストグラムデータを量子化すること、並びに
前記シーケンス内の前記画像に対する、前記量子化されたヒストグラムデータ、前記画像及び前記量子化されたヒストグラムデータを表す値、ワード、並びに量子化された記述子要素を記憶すること、
を含む、方法。
【請求項１７】
前記画像のシーケンスはビデオシーケンスの断片を含む、請求項１４〜１６のいずれか１項に記載の方法。
【請求項１８】
前記ヒストグラムデータ、前記画像を表す値、及び前記記述子要素は前記ビットストリーム内に記憶される、請求項１４〜１７のいずれか１項に記載の方法。
【請求項１９】
画像の第１のシーケンス及び画像の第２のシーケンスを処理して、前記第１のシーケンスと前記第２のシーケンスとを比較する装置であって、
前記装置は、
前記第１のシーケンス内の複数の前記画像のそれぞれ、及び前記第２のシーケンス内の複数の前記画像のそれぞれを、前記画像内の複数の画素近傍集合のそれぞれに対する前記画像データを処理して、前記画素近傍集合のそれぞれに対して少なくとも１つの記述子要素を生成することによって処理するように構成される記述子要素生成手段であって、各前記記述子要素は１つ又は複数のビットを含む、記述子要素生成手段と、
各前記画像の前記記述子要素から、複数のワードであって、各前記ワードが記述子要素ビットの固有の組合せを含むような、複数のワードを形成するように構成されるワード生成手段であって、前記ワード生成手段は、前記第２のシーケンスに対する前記ワードのそれぞれを、前記第１のシーケンスに対する前記ワードのそれぞれと同じ組合せの記述子要素ビットから生成するように構成される、ワード生成手段と、
前記第１のシーケンス内の前記複数の画像に対して生成される前記ワードと、前記第２のシーケンス内の前記複数の画像に対して生成される前記ワードとを比較することによって、前記第１のシーケンスと前記第２のシーケンスとを比較する処理を実施するように構成されるシーケンス比較手段と、
を備える、装置。
【請求項２０】
画像を規定する画像データを処理して、前記画像を表す少なくとも１つの値を生成する装置であって、
前記装置は、
前記画像内の複数の画素近傍集合のそれぞれに対する前記画像データを処理するように構成される記述子要素生成手段であって、前記画素近傍集合のそれぞれに対して少なくとも１つの記述子要素を生成し、各前記記述子要素は１つ又は複数のビットを含む、記述子要素生成手段と、
前記記述子要素から、少なくとも１つのワードであって、各前記ワードが、１つ又は複数の前記記述子要素からの１つ又は複数のビットを含むと共に、前記ワードのすべてにおける総ビット数が前記記述子要素のすべてにおける総ビット数を下回るような、少なくとも１つのワードを形成するように構成されるワード生成手段と、
を備える、装置。
【請求項２１】
画像を規定する画像データを処理して、前記画像を表す複数の値を生成する装置であって、
前記装置は、
前記画像内の複数の画素近傍集合のそれぞれに対する前記画像データを処理するように構成される記述子要素生成手段であって、前記画素近傍集合のそれぞれに対して少なくとも１つの記述子要素を生成し、各前記記述子要素は１つ又は複数のビットを含む、記述子要素生成手段と、
前記記述子要素から、複数のワードであって、各前記ワードが、記述子要素ビットの固有の組合せを含むような、複数のワードを形成するように構成されるワード生成手段と、
を備える、装置。
【請求項２２】
画像を規定する画像データを処理して、前記画像を表す少なくとも１つの値を生成する装置であって、
前記装置は、
前記画像内の複数の画素近傍集合のそれぞれに対する前記画像データを処理するように構成される記述子要素生成手段であって、前記画素近傍集合のそれぞれに対して少なくとも１つの記述子要素を生成し、各前記記述子要素は１つ又は複数のビットを含む、記述子要素生成手段と、
各前記記述子要素を量子化するように構成される量子化手段と、
前記量子化された記述子要素から前記画像を表す少なくとも１つの値を形成するように構成される表現値形成手段と、
を備える、装置。
【請求項２３】
画像のシーケンスを規定する画像データを処理して、前記シーケンスの表現を生成及び記憶する装置であって、
前記装置は、
前記シーケンス内の各前記画像に対して、前記画像内の複数の画素近傍集合のそれぞれに対する前記画像データを処理するように構成される記述子要素生成手段であって、前記画素近傍集合のそれぞれに対して少なくとも１つの記述子要素を生成し、各前記記述子要素は１つ又は複数のビットを含む、記述子要素生成手段と、
前記シーケンス内の各前記画像に対して、前記画像の前記記述子要素から、少なくとも１つのワードを形成するように構成されるワード生成手段であって、各前記ワードが、１つ又は複数の前記記述子要素からの１つ又は複数のビットを含むと共に、前記画像の前記ワードのすべてにおける総ビット数が、前記画像の前記記述子要素のすべてにおける総ビット数を下回るような、少なくとも１つのワードを形成するように構成されるワード生成手段と、
いずれのワードが前記画像のシーケンス内に現れるか、及び現れる頻度を規定するヒストグラムデータを生成するように構成されるヒストグラムデータ生成手段と、
前記シーケンス内の前記画像に対する前記ヒストグラムデータ、前記ワード、及び前記記述子要素を、記憶装置に書き込むように構成されるデータ書込み手段と、
を備える、装置。
【請求項２４】
画像のシーケンスを規定する画像データを処理して、前記シーケンスの表現を生成及び記憶する装置であって、
前記装置は、
前記シーケンス内の各前記画像に対して、前記画像内の複数の画素近傍集合のそれぞれに対する前記画像データを処理するように構成される記述子要素生成手段であって、前記画素近傍集合のそれぞれに対して少なくとも１つの記述子要素を生成し、各前記記述子要素は１つ又は複数のビットを含む、記述子要素生成手段と、
前記シーケンス内の各前記画像に対して、前記画像の前記記述子要素から複数のワードを形成するように構成されるワード生成手段であって、各前記ワードが、記述子要素ビットの固有の組合せを含むような、複数のワードを形成するように構成されるワード生成手段と、
いずれのワードが前記画像のシーケンス内に現れるか、及び現れる頻度を規定するヒストグラムデータを生成するように構成されるヒストグラムデータ生成手段と、
前記シーケンス内の前記画像に対する前記ヒストグラムデータ、前記ワード、及び前記記述子要素を、記憶装置に書き込むように構成されるデータ書込み手段と、
を備える、装置。
【請求項２５】
画像のシーケンスを規定する画像データを処理して、前記シーケンスの表現を生成及び記憶する装置であって、
前記装置は、
前記シーケンス内の各前記画像に対して、前記画像内の複数の画素近傍集合のそれぞれに対する前記画像データを処理するように構成される記述子要素生成手段であって、前記画素近傍集合のそれぞれに対して少なくとも１つの記述子要素を生成し、各前記記述子要素は１つ又は複数のビットを含む、記述子要素生成手段と、
各前記記述子要素を量子化するように構成される記述子要素量子化手段と、
各前記画像に対して、前記画像の前記量子化された記述子要素から前記画像を表す少なくとも１つの値を形成するように構成される表現値形成手段と、
前記画像を表すいずれの値が前記画像のシーケンス内に現れるか、及び現れる回数を規定するヒストグラムデータを生成するように構成されるヒストグラムデータ生成手段と、
前記ヒストグラムデータを量子化するように構成されるヒストグラムデータ量子化手段と、
前記量子化されたヒストグラムデータ、前記画像を表す値、及び前記量子化された記述子要素を記憶装置に書き込むように構成される、データ書込み手段と、
を備える、装置。
【請求項２６】
プログラム可能処理装置を、請求項１〜１８の少なくとも１項に記載の方法を実施するように動作可能になるようにプログラミングする、コンピュータプログラム命令を含むコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的な編集操作（カメラ取込み、アナログ／デジタル変換、再圧縮等）に対してロバストである、高速且つ信頼できるビデオ識別のための方法、装置、及びコンピュータプログラム製品に関する。
【背景技術】
【０００２】
専門家及び消費者によって記憶されているビデオの数が急速に増大している。専門家に関しては、ビデオコンテンツの作成、記憶、及び編集のコストの問題及び技術的な問題は減少してきている。消費者に関しては、セットトップボックス、パーソナルビデオレコーダ、ビデオカメラ、及びコンピュータの選択の幅が広がっていること、並びに、これらのコストが減少していることによって、ビデオコンテンツの増大に拍車がかかっている。過去数年にわたって、インターネット上で利用可能な合法及び非合法のコンテンツが共に爆発的に増大している。このコンテンツをインデックス付けし、検索し、監視する能力がますます重要な問題になってきている。ＭＰＥＧ−７標準規格は、コンテンツベースの検索及び取出しの領域における初期の仕事であった。この標準規格の元のバージョンにおいて欠けていた領域が、複製類似ビデオ（near-duplicate video）検出である。
【０００３】
複製類似ビデオ検出は、問合せビデオシーケンスが与えられると、データベース内のすべての複製を発見するものと定義することができる。複製（複製類似）の概念及び解釈はさまざまである。しかしながら、本発明に関しては、複製とは、オリジナルに対する一般的なビデオ編集／処理操作によって作成されたシーケンスであるとみなす。このような操作の例は、より多くの例の中でも、色変更、圧縮、トランスコーディング、フォーマット変更、フレームレート変更、アナログＶＣＲ再取込み、及びカメラ再取込みを含む。本発明は、複製部分が問合せシーケンスの一部のみを形成する場合がある問題にも対処する。
【０００４】
この領域における従来の仕事（非特許文献１）は、複数のカットを撮影し、境界を使用してビデオシーケンスのシグネチャを形成していた。これは、ビデオの非常にコンパクトな表現を提供するが、短いシーケンスに対しては非常に不満足にしか機能せず、使用されるショット検出アルゴリズムの影響を非常に受けやすい（非特許文献２）。
【０００５】
ビデオ内の複製（複製類似）検出に対する、特徴点を用いる一般的な当該技術水準の手法は、非特許文献３に与えられており、ｉ）キーフレームを検出し、ｉｉ）該フレーム内のキーポイントを検出し、ｉｉｉ）該ポイントの周囲の領域から特徴を検出し、ｉｖ）特徴を使用してシーケンスを照合し、ｖ）シーケンス内の物体の空間的結束性（spatial cohesion）に関する試験を適用する、というように概説することができる。この概説した手法にはいくつかの欠点がある。まず、キーフレームを使用するということは、この方法が短いクリップに対してはあまり良好に機能しない可能性があることを意味している。特徴の抽出（ｉｉｉ）は計算コストが高い方法であり、その結果ストレージ要求が大きくなる。ステップ（ｉｖ）に関して、データのクラスタリングから学習される視覚的語彙が使用される。これは特定のデータセットに対する過剰適合をもたらす可能性があり、これは一般化の失敗を伴う。非特許文献４のような関連方法は、使用されるハッシュテーブルに対する高メモリ要件と引き換えに高速の検索を提供する。これはいくつかのシナリオに対しては適切であり得るものの、一般的にメモリ資源が非常に限られている家庭用電化製品の環境においては適切でない。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】T. Hoad及びJ. Zobel著「Video similarity detection for digital rights management」（Proceedings of Australasian Computer Science Conference, pages 237-245, Adelaide, Australia, 2003）
【非特許文献２】T. Hoad及びJ. Zobel、Proceedings of the 5th ACM SIGMM international workshop on Multimedia information retrieval, pages 262-269, Berkeley, US, 2003
【非特許文献３】J. Sivic、A. Zisserman著「Efficient Visual Search for Objects in Videos」（Proceedings of the IEEE, April 2008, 96 (4), pages 548-566）
【非特許文献４】Ondrej Chum、James Philbin、Michael Isard、及びAndrew Zisserman著「Scalable near identical image and shot detection」（Proceedings of the 6th ACM international conference on Image and video retrieval, pages 549-556, Amsterdam, The Netherlands, 2007）
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明は、少なくとも、このような従来技術の方法の制限のうちの１つ又は複数に対処することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の特定の態様を添付の特許請求の範囲に記載している。他の態様は下記の実施の形態に記載しており、当業者であれば本明細書を読むことによって理解されよう。
【０００９】
要約すると、本発明は、画像の第１のシーケンス及び画像の第２のシーケンスを処理して、該第１のシーケンスと該第２のシーケンスとを比較する装置であって、
該装置は、
第１のシーケンス内の複数の画像のそれぞれ、及び第２のシーケンス内の複数の画像のそれぞれを、画像内の複数の画素近傍集合のそれぞれに対する画像データを処理することによって、該画素近傍集合のそれぞれに対して少なくとも１つの記述子要素を生成することによって処理するように構成される記述子要素生成手段であって、各記述子要素は１つ又は複数のビットを含む、記述子要素生成手段と、
各画像の記述子要素から、複数のワード（word）であって、各ワードが記述子要素ビットの固有の組合せを含むような、複数のワードを形成するように構成されるワード生成手段であって、該ワード生成手段は、第２のシーケンスに対するワードのそれぞれを第１のシーケンスに対するワードのそれぞれと同じ組合せの記述子要素ビットから生成するように構成される、ワード生成手段と、
第１のシーケンス内の複数の画像に対して生成されるワードと、第２のシーケンス内の複数の画像に対して生成されるワードとを比較することによって、第１のシーケンスと第２のシーケンスとを比較する処理を実施するように構成されるシーケンス比較手段とを備える、装置を提供する。
【００１０】
シーケンス比較手段は、第１のシーケンス及び第２のシーケンス内に異なるワード値が発生する頻度を比較する処理を含む、第１のシーケンスと第２のシーケンスとを比較する処理を実施するように構成することができる。
【００１１】
シーケンス比較手段は、
第１のシーケンスに対する発生データを生成するために、第１のシーケンス内の各ワードに対する各可能なワード値の発生回数を求めること、
第２のシーケンスに対する発生データを生成するために、第２のシーケンス内の各ワードに対する各可能なワード値の発生回数を求めること、及び、
第１のシーケンスに対する発生データと、第２のシーケンスに対する発生データとを比較することを含む、第１のシーケンスと第２のシーケンスとを比較する処理を実施するように構成することができる。
【００１２】
シーケンス比較手段は、第１のシーケンスに対する発生データと、第２のシーケンスに対する発生データとを比較して、各ワードについての比較結果を生成すると共に、該それぞれの比較結果をマージして全体の比較結果を生成するように構成することができる。
【００１３】
本装置は、
各ワードに対して、双方のシーケンス内に発生するワード値を求める手段と、
各ワードに対して、双方のシーケンスにおけるワード値の時間的な発生順序を求める手段と、
該時間的な発生順序を比較する手段と
をさらに備えることができる。
【００１４】
本装置は、
一致する画像対であって、第１のシーケンスからの１つの画像と第２のシーケンスからの１つの画像とを含む画像対を特定する手段と、
少なくとも１つの特定された画像対間の類似度を求めるためにさらなる対応性試験を実施する手段と
をさらに備えることができる。
【００１５】
本発明はまた、画像を規定する画像データを処理して、該画像を表す少なくとも１つの値を生成する装置であって、
該装置は、
画像内の複数の画素近傍集合のそれぞれに対する画像データを処理するように構成される記述子要素生成手段であって、該画素近傍集合のそれぞれに対して少なくとも１つの記述子要素を生成し、各記述子要素は１つ又は複数のビットを含む、記述子要素生成手段と、
記述子要素から、少なくとも１つのワードであって、各ワードが、１つ又は複数の記述子要素からの１つ又は複数のビットを含むと共に、該ワードのすべてにおける総ビット数が記述子要素のすべてにおける総ビット数を下回るような、少なくとも１つのワードを形成するように構成されるワード生成手段と
を備える、装置を提供する。
【００１６】
本発明はまた、画像を規定する画像データを処理して、該画像を表す複数の値を生成する装置であって、
該装置は、
画像内の複数の画素近傍集合のそれぞれに対する画像データを処理するように構成される記述子要素生成手段であって、該画素近傍集合のそれぞれに対して少なくとも１つの記述子要素を生成し、各記述子要素は１つ又は複数のビットを含む、記述子要素生成手段と、
記述子要素から、複数のワードであって、各ワードが、記述子要素ビットの固有の組合せを含むような、複数のワードを形成するように構成されるワード生成手段とを備える、装置を提供する。
【００１７】
本装置は、各記述子要素を量子化する量子化手段をさらに備えることができ、ワード生成手段は、量子化された記述子要素から各ワードを形成するように構成することができる。
【００１８】
量子化器は、各記述子要素を量子化して、それぞれの１ビットの２値結果を形成するように構成することができる。
【００１９】
記述子要素生成手段は、複数の異なる画素解像度で画像に対する記述子要素を生成するように構成することができ、ワード生成手段は、複数の異なる画素解像度で生成された記述子要素からの１つ又は複数のビットを組み合わせることによって、少なくとも１つのワードを生成するように構成することができる。
【００２０】
本発明はまた、画像を規定する画像データを処理して、該画像を表す少なくとも１つの値を生成する装置であって、
該装置は、
画像内の複数の画素近傍集合のそれぞれに対する画像データを処理するように構成される記述子要素生成手段であって、該画素近傍集合のそれぞれに対して少なくとも１つの記述子要素を生成し、各記述子要素は１つ又は複数のビットを含む、記述子要素生成手段と、
各記述子要素を量子化するように構成される量子化手段と、
量子化された記述子要素から画像を表す少なくとも１つの値を形成するように構成される表現値形成手段と
を備える、装置を提供する。
【００２１】
量子化器は、各記述子要素を量子化して、それぞれの１ビットの２値結果を形成するように構成することができる。
【００２２】
本発明はまた、画像のシーケンスを規定する画像データを処理して、シーケンスの表現を生成及び記憶する装置であって、
該装置は、
シーケンス内の各画像に対して、画像内の複数の画素近傍集合のそれぞれに対する画像データを処理するように構成される記述子要素生成手段であって、該画素近傍集合のそれぞれに対して少なくとも１つの記述子要素を生成し、各記述子要素は１つ又は複数のビットを含む、記述子要素生成手段と、
シーケンス内の各画像に対して、画像の記述子要素から、少なくとも１つのワードであって、各ワードが、１つ又は複数の記述子要素からの１つ又は複数のビットを含むと共に、画像の該ワードのすべてにおける総ビット数が、該画像の記述子要素のすべてにおける総ビット数を下回るような、少なくとも１つのワードを形成するように構成されるワード生成手段と、
いずれのワードが画像のシーケンス内に現れるか、及び現れる回数を規定するヒストグラムデータを生成するように構成されるヒストグラムデータ生成手段と、
シーケンス内の画像に対するヒストグラムデータ、ワード、及び記述子要素を記憶装置に書き込むように構成されるデータ書込み手段と
を備える、装置を提供する。
【００２３】
本装置は、各記述子要素を量子化するように構成される記述子要素量子化手段をさらに備えることができ、ワード生成手段は、量子化された記述子要素から各ワードを形成するように構成することができる。加えて、本装置は、ヒストグラムデータを量子化するように構成されるヒストグラムデータ量子化手段をさらに備えることができ、データ書込み手段は、量子化されたヒストグラムデータ、ワード、及び量子化された記述子要素を記憶装置に書き込むように構成することができる。
【００２４】
本装置は、ビデオシーケンスの断片を含む画像シーケンスを処理するように動作可能とすることができる。
【００２５】
データ書込み手段は、ヒストグラムデータ、ワード、及び記述子要素をビットストリーム内に記憶するように構成することができる。
【００２６】
本発明はまた、画像のシーケンスを規定する画像データを処理して、シーケンスの表現を生成及び記憶する装置であって、
該装置は、
シーケンス内の各画像に対して、画像内の複数の画素近傍集合のそれぞれに対する画像データを処理するように構成される記述子要素生成手段であって、該画素近傍集合のそれぞれに対して少なくとも１つの記述子要素を生成し、各記述子要素は１つ又は複数のビットを含む、記述子要素生成手段と、
シーケンス内の各画像に対して、画像の記述子要素から、複数のワードであって、各ワードが、記述子要素ビットの固有の組合せを含む、複数のワードを生成するように構成されるワード生成手段と、
いずれのワードが画像のシーケンス内に現れるか、及び現れる回数を規定するヒストグラムデータを生成するように構成されるヒストグラムデータ生成手段と、
シーケンス内の画像に対するヒストグラムデータ、ワード、及び記述子要素を記憶装置に書き込むように構成される、データ書込み手段とを備える、装置を提供する。
【００２７】
本装置は、各記述子要素を量子化するように構成される記述子要素量子化手段をさらに備えることができ、ワード生成手段は、量子化された記述子要素から各ワードを形成するように構成することができる。加えて、本装置は、ヒストグラムデータを量子化するように構成されるヒストグラムデータ量子化手段をさらに備えることができ、データ書込み手段は、量子化されたヒストグラムデータ、ワード、及び量子化された記述子要素を記憶装置に書き込むように構成することができる。
【００２８】
本装置は、ビデオシーケンスの断片を含む画像のシーケンスを処理するように動作可能とすることができる。
【００２９】
データ書込み手段は、ヒストグラムデータ、ワード、及び記述子要素をビットストリーム内に記憶するように構成することができる。
【００３０】
本発明はまた、画像のシーケンスを規定する画像データを処理して、シーケンスの表現を生成及び記憶する装置であって、
該装置は、
シーケンス内の各画像に対して、画像内の複数の画素近傍集合のそれぞれに対する画像データを処理するように構成される記述子要素生成手段であって、該画素近傍集合のそれぞれに対して少なくとも１つの記述子要素を生成し、各記述子要素は１つ又は複数のビットを含む、記述子要素生成手段と、各記述子要素を量子化するように構成される記述子要素量子化手段と、
シーケンス内の各画像に対して、量子化された記述子要素から画像を表す少なくとも１つの値を形成するように構成される表現値形成手段と、画像を表すいずれの値が画像のシーケンス内に現れるか、及び現れる回数を規定するヒストグラムデータを生成するように構成されるヒストグラムデータ生成手段と、
ヒストグラムデータを量子化するように構成されるヒストグラムデータ量子化手段と、
量子化されたヒストグラムデータ、画像を表す値、及び量子化された記述子要素を記憶装置に書き込むように構成される、データ書込み手段と
を備える、装置を提供する。
【００３１】
本装置は、ビデオシーケンスの断片を含む画像のシーケンスを処理するように動作可能とすることができる。
【００３２】
データ書込み手段は、ヒストグラムデータ、画像を表す値、及び記述子要素をビットストリーム内に記憶するように構成することができる。
【００３３】
本発明の一実施の形態は、
‐ビデオシーケンスの非常にコンパクトな表現を提供し、
‐トレーニングデータに依存せず、
‐非常に高速の検索及び照合を提供し、
‐一般的な編集／処理操作に対してロバストであり、且つ
‐照合フレーム位置の正確な位置特定を提供する、
ビデオ識別のための新規の方法及び装置を提供する。
【００３４】
ここで、本発明の実施形態を、添付の図面を参照して例示としてのみ説明する。
【図面の簡単な説明】
【００３５】
【図１】一実施形態における、記述子要素を生成する処理を示す図である。
【図２】一実施形態における、記述子要素からワードを生成する処理を示す図である。
【図３】一実施形態における２値化を示す図である。
【図４】一実施形態における、時間シフト及びフレームレート変化の決定を示す図である。
【図５】一実施形態の処理動作を実施する処理装置の一例を示す図である。
【発明を実施するための形態】
【００３６】
これより、本発明の一実施形態における処理装置によって実施される方法を説明する。本方法は、いくつかの処理動作を含む。本明細書の末尾において説明するように、これらの処理動作は、ハードウェア、ファームウェア、コンピュータプログラム命令に従って動作する処理ユニット、又はそれらの組合せを使用する処理装置によって実施することができる。
【００３７】
複数のビデオフレームｆi（ｃ，ｘ，ｙ）から成るシーケンスを考える。ここで、ｉはフレームインデックスであり、たとえばｉ∈［０，Ｔ−１］であり、ここで、Ｔはシーケンス内のフレームの総数である。ｃはｌ（エル）個のカラーチャネルにおけるインデックスであり、たとえばｌ（エル）＝３ではｃ∈｛Ｙ，Ｕ，Ｖ｝である。ｘ及びｙは空間座標であり、たとえばｘ∈［０，Ｍ−１］、ｙ∈［０，Ｎ−１］であり、ここでＭは水平フレーム解像度であり、Ｎは垂直フレーム解像度である。
【００３８】
本発明の好ましい一実施形態では、各フレームをその画素強度(pixel intensity)及び差分に関して記述する。このような記述子は、本発明の同時継続出願である欧州特許出願第１６４０９１３号及び欧州特許出願第１６４０９１４号に記載されており、これらは参照によりその全体が本明細書に援用される。本発明の好ましい一実施形態では、空間的に再サンプリングされたｍ×ｍ画素解像度のフレームを考える。ここで、ｍは２の累乗である。好ましくは、ｍは小さな値、たとえばｍ＝１６又はｍ＝３２であるが、これは限定ではない。ここで、各フレームは重複しない２×２画素近傍集合（pixel neighbourhoods）に分割され、各近傍集合において記述子要素が以下のように計算される。
【００３９】
【数１】
2010191954.tif 000003
【００４０】
これは、図１において、ｍ＝８及びｃ＝Ｙについて一般性を損なうことなく示されている。式（１）による記述子要素は平均強度であり、フレーム全体に対してとられ、そのフレームを（ｍ／２）×（ｍ／２）画素解像度で再サンプリングしたものを与え、これが式（１）〜（４）に従って再処理される。このプロセスは、フレーム全体に対する平均強度が計算されるまで継続する。したがって、フレームｆiに対する完全な記述子は、異なる複数の画素解像度（すなわち、ｍ×ｍ，ｍ／２×ｍ／２，…，４×４，２×２）における、そのフレームに対する複数の記述子要素を含み、したがって、
【００４１】
【数２】
2010191954.tif 000004
【００４２】
によって与えられる。本発明の好ましい一実施形態では、フレームは自身の輝度チャネルＹによって表され、記述子ｄiはこの輝度情報から抽出される。
【００４３】
任意選択で、記述子要素は所望のビット数に量子化される。該所望のビット数は異なるものであってもよく、要素ごとに、またはカラーチャネルごとに異なってもよい。本発明の好ましい一実施形態では、記述子要素は以下のように２値化される。
【００４４】
【数３】
2010191954.tif 000005
【００４５】
…（５）
ここで、ｒはダイナミックレンジであり、たとえば８ビット画素値についてｒ＝２５６である。
【００４６】
【数４】
2010191954.tif 000006
【００４７】
…（６）
ここで、
【００４８】
【数５】
2010191954.tif 000007
【００４９】
は式（１）による平均を示し、
【００５０】
【数６】
2010191954.tif 000008
【００５１】
は式（２）〜（４）による差分を示す。（５）及び（６）の利点は、それらを、要素の整数部分の２値表現のＭＳＢ（最上位ビット）を維持することと等価となるように実施することができることである。
【００５２】
代替的な実施形態では、位置センシティブハッシング（locality sensitive hashing）のような他の量子化／２値化技法を採用することもできる。この方法は、本明細書においては検討しないが、Samet H.著「Foundations of Multidimensional and Metric Data Structures」（Morgan Kaufmann, 2006）に記載されている。
【００５３】
次いで、フレームに対する完全な記述子が使用されて、少なくとも１つのコンパクトなワード(word)が、記述子要素のうちの１つ又は複数の、１つ又は複数のビットに基づいて形成される。これは図２（ａ）に示されている。「ワード」という用語は、本明細書においては任意のビット数を有し得るワードを指すのに使用され、いくつかのコンピュータ分野の刊行物にあるような特定のビット数に具体的に限定されるわけではないことに留意されたい。より具体的には、本発明の好ましい一実施形態では、２値化された
【００５４】
【数７】
2010191954.tif 000009
【００５５】
に含まれる要素のいくつかからなる、小さな順序集合が連結されて、１つのワードを生成する。いずれの要素が選択されるかに対する限定は存在せず、ワードは、異なる複数のカラーチャネルから、異なるレベルの（たとえば１６×１６又は４×４の解像度で抽出される）粗さ（coarseness）からの要素を、式（１）による平均であっても式（２）〜（４）による差分であっても混合することができる。たとえば、本発明の１つの実施形態では、要素はすべての利用可能な要素の中からランダムに選択することができる。本発明の別の実施形態では、要素は、たとえばビデオフレームの特定の空間領域のみを覆う或る幾何パターンに従って選択することができる。本発明のさらに別の実施形態では、要素はそれらのエントロピーに従って順序付けることができ、エントロピーが最も高い要素が選択されてワードを形成する。したがって、ワード形成のプロセスはΦ次元空間からΨ次元空間への射影であり、好ましくはΨ＜＜Φである。２つのビデオフレームに関して、２つの対応するワード（すなわち、順序を有する選択された要素からなるビットパターンのうち対応するもの）間の距離は、フレーム記述子全体の距離の近似である。
【００５６】
ワードを構成する、順序付けされている要素のすべての可能な値のすべての可能な組合せは、そのワードに対する語彙(vocabulary)を与える。すなわち、ワードは複数の記述子要素からなる固有の組合せであり、或るワードに対する語彙はそのワードがとることができる異なる複数の値から成る集合である。たとえば、ワードが２つの記述子要素を含み、各記述子要素が１ビット長であり、各ビットが値０又は１を自由にとることができる場合、そのワードに対する語彙は００、０１、１０、及び１１である。
【００５７】
本発明の好ましい一実施形態では、図２（ｂ）に示すように、各フレームから複数のワードが抽出され、各ワードは２値化された
【００５８】
【数８】
2010191954.tif 000010
【００５９】
に含まれる要素のいくつかからなる、小さな順序集合から与えられる。好ましくは、各ワードの要素は任意の適切な方法（ランダム射影、幾何学的制約、エントロピー順序付け等）に従って選択される。各ワードは語彙を有し、各ワードを生成するビットの組合せは固有であるが、部分的に重複する可能性を排除するものではない。たとえば、いくつかの要素は２つ以上のワードに現れる。さらに、各ワードは任意の他のワードと同じ長さを有してもよいし、有しなくてもよい。すなわち、ΦからΨ1、Ψ2へ等の次元削減を行うことができる。
【００６０】
本発明の代替的な実施形態では、その元の解像度及びダイナミックレンジにおける記述子ｄiの任意のバージョン（量子化されていても２値化されていても）からワードを形成することができる。このような実施形態では、１つの要素が１つのワードに対して２ビット以上寄与することができ、また異なるワードに対して異なるビット数寄与することができ、１つのワードはさまざまな要素からのさまざまな数のビットを含むことができる。
【００６１】
ビデオシーケンスは上述のように、そのフレームのうちの１つ又は複数によって記述される。次いで、１つ又は複数の語彙のそれぞれにおいて異なるワードが発生する頻度を計算する。より具体的には、本発明の好ましい実施形態では、シーケンス内の複数のフレームが処理され、各フレームｆiからΦ次元の完全な記述子及び複数のワードｗik（ｋ∈［０，Ｑ−１］）が抽出され、各ワードがＱ個の語彙のうちの１つに対応する。次いで、各語彙ｋについて、フレームシーケンス内に見られるワードのヒストグラムｈkがプロットされる。簡単に言えば、このようなヒストグラムは、いずれのワードがフレームシーケンス内に現れるか、及び現れる頻度を示す。より具体的には、各ワードについて、一方の軸に、そのワードがとり得る各値（すなわち、ワードの語彙内の各値）に対するそれぞれのビンを有し、他方の軸に、各値の発生回数を記録するヒストグラムが生成される。
【００６２】
２つのフレームシーケンスｆ1i及びｆ2jについて、各語彙ｋに対するヒストグラムｈ1kとｈ2kとを比較してその結果をマージして決定に至ることによって、それらの類似度を評価することができる。この比較は、ヒストグラムインターセクションのような適切な距離測度を使用して達成することができる。本発明の好ましい一実施形態では、ヒストグラムは２値化される。ここで、このような２値化ヒストグラムは多く存在するワードを示す。２値化は、複数の適切な方法（単純な閾値化、適応的な閾値化等）のうちの任意の方法によって達成することができる。２値化ヒストグラム
【００６３】
【数９】
2010191954.tif 000011
【００６４】
及び
【００６５】
【数１０】
2010191954.tif 000012
【００６６】
について、それらの距離は、好ましくは以下の式によって与えられるJaccard距離測度によって測定される。
【００６７】
【数１１】
2010191954.tif 000013
【００６８】
…（７）
簡単に言えば、式（７）は、所与の語彙におけるフレームシーケンスｆ1i及びｆ2jの距離を、それらが共通に有する各ワードと、それらが全体で含む全てのワードとの関数として測定する。
【００６９】
Ｑ個の語彙について、Ｑ個のJaccard距離
【００７０】
【数１２】
2010191954.tif 000014
【００７１】
がある。本発明の好ましい一実施形態では、以下のように、これらの距離が融合されて、複合距離
【００７２】
【数１３】
2010191954.tif 000015
【００７３】
が与えられる。
【００７４】
【数１４】
2010191954.tif 000016
【００７５】
…（８）
したがって、
【００７６】
【数１５】
2010191954.tif 000017
【００７７】
の処理（好ましくは閾値化）によって、フレームシーケンスが類似しているか否かについての決定に至ることができる。この事例において、
【００７８】
【数１６】
2010191954.tif 000018
【００７９】
が或る閾値未満である場合、シーケンスは一致すると宣言され、そうでない場合は一致しないと宣言される。
【００８０】
明らかに、トリム平均、メジアン、最大値等のような、式（８）に対する多くの代替物が存在する。さらに、代替的な実施形態は、距離融合ではなく、決定融合（各
【００８１】
【数１７】
2010191954.tif 000019
【００８２】
を適切な閾値を用いて個々に閾値化して、次いで個々の決定をたとえば多数決によって融合すること）によって、フレームシーケンスの類似度に対する決定に至ることができる。本発明の代替的な一実施形態では、距離融合と決定融合と組み合わせること、すなわち、複合の
【００８３】
【数１８】
2010191954.tif 000020
【００８４】
を計算し、続いて閾値化することによって決定に至ることも可能であるが、一致の決定を、少なくともある設定された数の
【００８５】
【数１９】
2010191954.tif 000021
【００８６】
距離によってサポートする必要もある。
【００８７】
任意選択で、各語彙に関してビデオシーケンス内の一致するワードの発生の時間的順序を考慮することによって、検出された一致が検証される。好ましい一実施形態では、各語彙ｋに関して、双方のビデオシーケンスｆ1i及びｆ2jにおいて発生するワードの集合が見つけられる。好ましくは、これらは、双方のヒストグラムｈ1k及びｈ2kにおいて非ゼロである要素（２値ヒストグラム
【００８８】
【数２０】
2010191954.tif 000022
【００８９】
及び
【００９０】
【数２１】
2010191954.tif 000023
【００９１】
の共通部分）を特定することによって見つけられる。各ヒストグラムの各要素が語彙からの
１つのワードに対応することを想起すると、共通部分は、ｚ個の要素を有する、双方のフレームに共通であるワードの集合Ｗ12k＝｛ｗλk，λ∈［０，ｚ−１］｝＝｛ｗα，…，ｗζ｝を生成する。好ましくは、この集合は、語彙に従って、たとえば数値順又はアルファベット順に順序付けされる。次いで、各ビデオシーケンスについて、順序集合Ｗ12kにおけるワードそれぞれについての最初の発生を記録したフレーム番号の集合Ωk＝｛ωλk，λ∈［０，ｚ−１］｝＝｛ｆα，…，ｆζ｝が生成される。
【００９２】
フレーム番号の２つの集合Ω1k及びΩ2k（それぞれｆ1i及びｆ2jに対応する）が比較されて、それらの間の距離が求められる。好ましい実施形態では、Ω1k及びΩ2kは２値化され、それらの間の距離が正規化ハミング距離によって与えられる。好ましい一実施形態では、２値化は、集合
【００９３】
【数２２】
2010191954.tif 000024
【００９４】
…（９）
に含まれる互いに隣接する要素の間の差を評価することによって、図３に示されるように実施される。
【００９５】
２値化集合は
【００９６】
【数２３】
2010191954.tif 000025
【００９７】
と表され、正規化ハミング距離は
【００９８】
【数２４】
2010191954.tif 000026
【００９９】
と表される。簡単に言えば、このような２値化集合は、順序集合Ｗ12k内の各ワードがビデオシーケンスにおいて最初に現れるのが、ワードの順序集合Ｗ12k内におけるその次のワードの前であるか又は後であるかを記録する。
【０１００】
本発明の代替的な実施形態では、Ω1k及びΩ2kは２値化することなく、適切な距離測度（たとえば、一方のシーケンス内のワードの発生状況が他方のシーケンスと異なるようなフレームすべての数を与えるＬ１）を使用して比較することができる。
【０１０１】
Ｑ個の語彙について、Ｑ個の正規化ハミング距離
【０１０２】
【数２５】
2010191954.tif 000027
【０１０３】
がある。本発明の好ましい一実施形態では、以下のように、これらの距離が融合されて、複合距離
【０１０４】
【数２６】
2010191954.tif 000028
【０１０５】
が、
【０１０６】
【数２７】
2010191954.tif 000029
【０１０７】
…（１０）
として与えられる。
したがって、
【０１０８】
【数２８】
2010191954.tif 000030
【０１０９】
の処理（好ましくは閾値化）によって、フレームシーケンスが類似しているか否かについての決定に至ることができる。この事例において、
【０１１０】
【数２９】
2010191954.tif 000031
【０１１１】
が或る閾値未満である場合、シーケンスは一致すると宣言され、そうでない場合は一致しないと宣言される。
【０１１２】
明らかに、トリム平均、メジアン、最大値等のような、式（１０）に対する多くの代替物が存在する。さらに、代替的な実施形態は、距離融合ではなく、決定融合（すなわち、各
【０１１３】
【数３０】
2010191954.tif 000032
【０１１４】
を適切な閾値を用いて個々に閾値化して、次いで個々の決定をたとえば多数決によって融合すること）によって、フレームシーケンスの類似度に対する決定に至ることができる。本発明の代替的な一実施形態では、距離融合と決定融合と組み合わせること、すなわち、複合の
【０１１５】
【数３１】
2010191954.tif 000033
【０１１６】
を計算し、続いて閾値化することによって決定に至ることも可能であるが、一致の決定を、少なくともある設定された数の
【０１１７】
【数３２】
2010191954.tif 000034
【０１１８】
距離によってサポートする必要もある。
【０１１９】
任意選択で、さらなる改良及び位置特定段階が適用されて、ビデオシーケンスが一致するか否かが非常に高いレベルの精度まで決定され、２つのシーケンスにおける対応するフレームの位置が求められる。双方のシーケンスからの一致するワードの集合が使用されて、可能性のあるフレームの対応性が求められる。次いで、シーケンス間の時間的変化を推定することができる。好ましい実施形態では、図４に示すように、シーケンス間の時間シフト及びフレームレート差が求められる。次いで、対応する可能性のある複数のフレームからの記述子を使用して、対応の妥当性を判断し且つ／又は時間変化パラメータを改良することができる。
【０１２０】
より具体的には、各語彙ｋについて、共通部分Ｗ12k＝｛ｗλk，λ∈［０，ｚ−１］｝＝｛ｗα，…，ｗζ｝内のワードのそれぞれは、ビデオシーケンスのそれぞれからの１つ又は複数のフレームに対応し、ここで「１つ又は複数」とは、各シーケンスについて異なる数であり得る。たとえば、あるシーケンス内の１つのみのフレームと、第２のフレーム内の多数のフレームとによって１つのワードを生成することができる。一対のビデオシーケンスについて、また各語彙ｋについて、またＷ12k内のｚ個のワードのそれぞれについて、シーケンスｆ1i及びｆ2j内においてそのワードに対応するフレーム番号対を含む集合を構築する。したがって、Ｗ12k内のｚ個のワードのうちの１つが、ｆ1i及びｆ2j内のフレームの単一の対によって生成される場合、そのワードに対する集合は一対のみのフレーム番号を含む。別のワードが、ｆ1i及びｆ2j内の複数対のフレームによって生成される場合、そのワードに対する集合はこれと同じ複数の対のフレーム番号を含む。
【０１２１】
次いで、Ｗ12k内の各ワードについて、また各語彙ｋについて、そのワードに対応するフレーム番号対は、単一の２次元ヒストグラムＧ12ij（ただしｉ∈［０，Ｔ1−１］，ｊ∈［０，Ｔ2−１］）内にプロットされ、ここでＴ1はシーケンスｆ1i内のフレームの数であり、Ｔ2はシーケンスｆ2j内のフレームの数である。簡単に言えば、Ｇ12ijにおいて、ビン値０は、検討中のフレーム対、すなわち（ｉ，ｊ）がＱ個の語彙のいずれにおいても一致するワードを生成しなかったことを表し、ｋ＜Ｑのビン値は、検討中のフレーム対がＱ個の語彙のうちのｋ個のみにおいて一致するワードを生成したことを表し、ビン値Ｑは、検討中のフレーム対がＱ個すべての語彙において一致するワードを生成したことを表す。
【０１２２】
ｆ1i及びｆ2j内のフレームは、１つ又は複数の語彙において同じワードを有する場合には対応しているとみなされ、これは対応性の弱試験であるとみなすことができる、すなわち、これらのフレームは弱く対応している。弱く対応しているフレーム対のそれぞれについて、それらをより詳細な記述子に従って比較することによって、対応性のより強い試験が実行される。好ましくは、上述のようにｆ1i及びｆ2jから抽出される２値記述子
【０１２３】
【数３３】
2010191954.tif 000035
【０１２４】
及び
【０１２５】
【数３４】
2010191954.tif 000036
【０１２６】
が使用される。このような２値記述子間の距離は好ましくは、ハミング距離
【０１２７】
【数３５】
2010191954.tif 000037
【０１２８】
として計算される。
【０１２９】
本発明の代替的な実施形態では、その元の解像度及びダイナミックレンジにおける、式（１）〜（４）に記述されている記述子ｄの任意のバージョン（量子化されていても２値化されていても）、又はこの記述子の適切な部分集合を使用することができ、ハミング距離
【０１３０】
【数３６】
2010191954.tif 000038
【０１３１】
は適切な距離測度、たとえばＬ１に置き換えられる。
【０１３２】
弱く対応するフレーム対が多数存在する場合、処理時間を有益に低減するために、限られた数のフレーム対のみを強く対応するフレーム対であると確認することができる。好ましくは、これらの対は共通のワードが最も多い順に試験される。すなわち、Ｑ個の共通のワードを有する対が最初に試験され、次いで、Ｑ−１個の共通のワードを有する対が試験され、以下同様である。共通のワードの数によるこのタイプの順序付けは、２ＤヒストグラムＧ12ijによって容易に提供される。弱く対応するフレーム対は、フレーム記述子間の距離が特定の基準を満たす場合に（すなわち、好ましくは所定の閾値を下回る場合に）、強く対応するフレーム対として受容される。これは、残りの弱く対応する対がなくなるか、又は強く対応する対が特定数発見されるまで繰り返される。上記から、Ｑ個よりも少ない一致ワードを有するフレーム対、又はただ１つの一致ワードしか有しないフレーム対であっても、強く対応するフレーム対であると確認される場合があり、一方で、Ｑ個の語彙内でＱ個の一致ワードを有するフレーム対が、それらの詳細な記述子によれば類似性に乏しいために、強く対応するフレーム対であると確認されない場合があることになる。このように、一般的に、より多数の弱く対応するフレーム対は、より少数の強く対応するフレーム対に低減される。
【０１３３】
次いで、強く対応する対が使用されて、フレームシーケンス間の時間パラメータ変化が推定される。好ましい一実施形態では、時間パラメータは時間シフト及びフレームレート変化である。これらは線形特性であり、したがって２つの強く対応する対を使用して推定することができる。好ましくは、ハフ変換(Hough transform)が使用されて時間パラメータが推定される。ハフ空間内のピークは最も可能性のある時間パラメータに対応する。ハフ変換及びラドン変換(Radon transform)はここでは検討しないが、van Ginkel, M.、Hendriks, C. L.、van Vliet, L. J.著「A short introduction to the Radon and Hough transforms and how they relate to each other」（Number QI-2004-01 in the Quantitative Imaging Group Technical Report Series, Delft University of Technology）に専門的に記載されている。
【０１３４】
ハフ変換は一般的に、パラメータの粗い推定値を得るのに使用される。これらのパラメータを使用して、２つのビデオシーケンス間のフレーム対応性が確立される。好ましい一実施形態では、フレーム対応性をより正確に求めることができる。単一の記述子は一定レベルの精度を提供するが、複数の記述子を組み合わせることによってより高いレベルの精度が達成される。好ましい一実施形態では、記述子間のハミング距離が使用され、このハミング距離は全記述子にわたって加算される。好ましくは、２つのシーケンスからの複数の対応するフレームが選択されて、該フレームからの記述子の組合せの間の距離を試験することによって、該シーケンス間の距離が求められる。好ましい一実施形態では、一群の（たとえば７つの）連続するフレームが第１のシーケンスの開始部分から選択され、第２のシーケンスからの対応するフレームと比較される。代替的に、各フレームはシーケンスの複数の部分（中央、終了部分等）からのものであってもよく、且つ／又はフレームは不連続であってもよい。好ましい一実施形態では、対応する対のうち一方のフレームを固定しておき、他方の対応するフレームの周辺領域（locality）においてより良好に対応するフレームを求めて検索することによって、フレームの対応性が改良される。
【０１３５】
一実施形態では、効率的な記述子記憶方式が使用されて、ビデオシーケンスのコンパクトな表現が形成される。好ましい実施形態では、シーケンスは、たとえば１秒の断片に分割される。各断片について、Ｑ個の２値ヒストグラム
【０１３６】
【数３７】
2010191954.tif 000039
【０１３７】
がビットストリーム内に記憶される。２値ヒストグラムに続いて、断片内のフレームのそれぞれに対する記述子
【０１３８】
【数３８】
2010191954.tif 000040
【０１３９】
が記憶される。シーケンス内のすべての断片が、このようにしてビットストリーム内に連続して記憶される。任意選択で、ビットストリームの先頭に、シーケンスのフレームレート、フレームの数、断片の数等のような情報を記憶することができる。
【０１４０】
代替的な一実施形態では、シーケンスは、ビットストリーム内で複数のフレーム表現によって表現することができる。ここで、各フレームはＱ個のワードと１つの２値記述子
【０１４１】
【数３９】
2010191954.tif 000041
【０１４２】
とによって表される。シーケンス内のフレームのすべてをこのように記憶することができる。別の代替形態では、最初に全てのフレーム内のすべてのワードを記憶し、続いてすべての記述子を記憶することが望ましい場合がある。明らかに、ヒストグラム、ワード、及び記述子の量子化されたバージョン又は元のバージョンを記憶することが可能である。
【０１４３】
本発明の代替的な一実施形態では、ビデオフレームから抽出された記述子を、適切なフレーム記述子（たとえば色ヒストグラム又はエッジ強度ヒストグラム）に変更することができ、これらはその元の形態、量子化された形態、又は２値化された形態で記憶することができ、これらからワードを形成することができる。本発明の異なる実施形態では、さまざまな決定段階を省略することができる。たとえば、各語彙に関するビデオシーケンス内の一致ワードの発生の時間的な順序付けに基づく処理及び決定段階は、その全体を省略することができる。これは、処理を、対応するフレームの改良、位置特定、及び決定に直接進めることによってなされる。本発明の代替的な実施形態では、各ビデオシーケンス内で発見される一致ワードによる決定段階を省略することができ、処理を、ビデオシーケンス内の一致ワードの発生の時間的な順序付けに基づく処理及び決定段階に直接進めることができる。
【０１４４】
上述の処理動作を実施するデータ処理装置１を図５に示す。装置１は、たとえば、パーソナルデスクトップコンピュータ又はポータブルコンピュータとすることができる。
【０１４５】
装置１は、データ処理装置の従来の要素を備える。これらの要素は当業者に既知であるため、詳細な説明は必要ない。手短に、図５の装置１は、コンピュータプログラム製品（記憶媒体５又は信号７等）からコンピュータプログラム命令及び処理されるビデオデータを受信する入力データインタフェース３を備える。処理システムはたとえば、ＣＰＵ９、ランダムアクセスメモリ１１、及び読出し専用メモリ１３（これらはバス１５によって接続される）によって提供される。ＣＰＵ９は動作全体を制御する。ＲＡＭ１１は、ＣＰＵ９によって、プログラムを実行すると共にＲＯＭ４（プログラム及び他のデータを記憶する）を制御するのに使用される作業メモリである。装置１の処理装置は、本明細書において上述したように画像を規定する画像データを処理する方法を実施するように構成される。この処理の結果は出力インタフェース１７によって出力される。
【０１４６】
上述の処理装置１はコンピュータプログラム命令に従って処理を実施するが、代替的な処理装置を、ハードウェア、ソフトウェア、又はハードウェア及びソフトウェアの任意の適切な組合せとして、任意の適切な又は望ましい方法で実施することができる。本発明を、コンピュータプログラム（プログラム可能処理装置内にロードされ、該装置上で実行されると、上述の画像データ処理方法のうちの１つを実行するもの）として具現化することができ、また、コンピュータプログラム製品（たとえばこのようなコンピュータプログラムを記憶するデータキャリア）として具現化することもできることにさらに留意されたい。
【０１４７】
本発明の実施形態の上記の記載は、例示及び説明を目的として提示されている。網羅的であること、又は本発明を開示されている厳密な形態に限定することは意図されていない。本発明の範囲から逸脱することなく変更、改変、及び変形を行うことができる。
【図１】
2010191954.tif 000042
【図２】
2010191954.tif 000043
【図３】
2010191954.tif 000044
【図４】
2010191954.tif 000045
【図５】
2010191954.tif 000046
【外国語明細書】
2010191954.tif 000047
2010191954.tif 000048
2010191954.tif 000049
2010191954.tif 000050
2010191954.tif 000051
2010191954.tif 000052
2010191954.tif 000053
2010191954.tif 000054
2010191954.tif 000055
2010191954.tif 000056
2010191954.tif 000057
2010191954.tif 000058
2010191954.tif 000059
2010191954.tif 000060
2010191954.tif 000061
2010191954.tif 000062
2010191954.tif 000063
2010191954.tif 000064
2010191954.tif 000065
2010191954.tif 000066
2010191954.tif 000067
2010191954.tif 000068
2010191954.tif 000069
2010191954.tif 000070
2010191954.tif 000071
2010191954.tif 000072
2010191954.tif 000073
2010191954.tif 000074
2010191954.tif 000075
2010191954.tif 000076
2010191954.tif 000077
2010191954.tif 000078
2010191954.tif 000079
2010191954.tif 000080
2010191954.tif 000081
2010191954.tif 000082
2010191954.tif 000083
2010191954.tif 000084