(57)【要約】本発明は、ビデオ信号２のよりロバストなフィンガープリント１を生成する新規の技術を提供する。本発明のある実施例は、各フレーム２０の中央部分２２のブロック２１からのみビデオ・フィンガープリントを得、残りの外側部分２３を無視する。得られるフィンガープリント１は、クロッピング又はシフトを含む変形に対してよりロバストである。他の実施例は、各フレーム（又はその中央部分）を、例えば、パイ状又は環状ブロックのような非長方形ブロックに分割し、かかるブロックからフィンガープリントを生成する。ブロックの形状は、特定の変形に対するロバスト性を提供するよう選択され得る。例えば、パイ状ブロックはスケーリングに対するロバスト性を提供し、環状ブロックは回転に対するロバスト性を提供する。他の実施例は、異なるサイズのブロックを使用する。これより、フレームの異なる部分は、フィンガープリントで異なる重み付けを与えられ得る。
2009542081.tif 000002
【特許請求の範囲】
【請求項１】
データフレームのシーケンスを有するビデオ信号の内容を示すフィンガープリントを生成する方法であって：
各フレームの中央部分のみを複数のブロックに分割し、前記中央部分以外の各フレームの残りの部分をブロックに分割されないままとするステップ；
各ブロックでデータの特徴を取り出すステップ；及び
前記取り出された特徴からフィンガープリントを計算するステップ；
を有する方法。
【請求項２】
前記残りの部分は前記中央部分を囲む、請求項１記載の方法。
【請求項３】
前記中央部分は前記フレームの中心部分を囲み、
当該方法は、前記中心部分をブロックに分割されないままとするステップを更に有する、請求項１記載の方法。
【請求項４】
前記複数のブロックは、複数の異なったサイズを有するブロックを有する、請求項１記載の方法。
【請求項５】
前記複数のブロックは、複数の異なったサイズを有する複数の長方形ブロックを有する、請求項１記載の方法。
【請求項６】
前記長方形ブロックのサイズは、前記フレームの中心から外側に向かう少なくとも１つの方向で増大する、請求項５記載の方法。
【請求項７】
前記複数のブロックは、複数の長方形でないブロックを有する、請求項１記載の方法。
【請求項８】
前記複数の長方形でないブロックは複数の略扇形ブロックを有し、
夫々の前記略扇形ブロックは、前記フレームの中心から夫々の対の半径によって境界を定められる、請求項７記載の方法。
【請求項９】
前記複数の長方形でないブロックは複数の略環状同心ブロックを有する、請求項７記載の方法。
【請求項１０】
データフレームのシーケンスを有するビデオ信号の内容を示すフィンガープリントを生成する方法であって：
各フレームを複数の異なったサイズを有する複数のブロックに分割するステップ；
各ブロックでデータの特徴を取り出すステップ；及び
前記取り出された特徴からフィンガープリントを計算するステップ；
を有する方法。
【請求項１１】
前記複数のブロックは複数の長方形ブロックを有する、請求項１０記載の方法。
【請求項１２】
前記長方形ブロックのサイズは、前記フレームの中心から外側に向かう少なくとも１つの方向で増大する、請求項１１記載の方法。
【請求項１３】
データフレームのシーケンスを有するビデオ信号の内容を示すフィンガープリントを生成する方法であって：
各フレームを複数の長方形でないブロックに分割するステップ；
各ブロックでデータの特徴を取り出すステップ；及び
前記取り出された特徴からフィンガープリントを計算するステップ；
を有する方法。
【請求項１４】
前記複数の長方形でないブロックは複数の略扇形ブロックを有し、
夫々の前記略扇形ブロックは、前記フレームの中心から夫々の対の半径によって境界を定められる、請求項１３記載の方法。
【請求項１５】
前記複数の長方形でないブロックは複数の略環状同心ブロックを有する、請求項１３記載の方法。
【請求項１６】
各フレームの中心部分をブロックに分割されないままとするステップを更に有する、請求項１３記載の方法。
【請求項１７】
データフレームのシーケンスを有するビデオ信号の内容を示すフィンガープリントを生成する方法であって、各データフレームは複数のブロックを有し、各ブロックはビデオ画像の夫々の領域に対応する方法において：
選択されたサブセットが前記ビデオ画像の中央部分に対応するよう、フレームごとに前記複数のブロックのサブセットのみを選択するステップ；
前記選択されたサブセットの各ブロックでデータの特徴を取り出すステップ；及び
前記取り出された特徴からフィンガープリントを計算するステップ；
を有する方法。
【請求項１８】
前記中央部分は外側部分によって囲まれる、請求項１７記載の方法。
【請求項１９】
前記中央部分は前記ビデオ画像の中心部分を囲み、
前記選択されたサブセットは前記中心部分に対応するブロックを含まない、請求項１７記載の方法。
【請求項２０】
データフレームのシーケンスを有するビデオ信号を受信し、請求項１記載の方法によって前記ビデオ信号の内容を示すフィンガープリントを生成するよう配置される信号処理装置。
【請求項２１】
請求項１記載の方法の実行を可能にするコンピュータプログラム。
【請求項２２】
請求項２２記載のコンピュータプログラムを記憶する記録媒体。
【請求項２３】
放送監視方法；信号フィルタリング方法；自動索引作成方法；選択的記録方法；不正変更検出方法；及び送信エラー検出方法を含むリストから選択される信号処理用途における請求項１記載のフィンガープリント生成方法の使用。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データフレームのシーケンスを有するビデオ信号の内容を示すフィンガープリントの生成に関する。
【背景技術】
【０００２】
データフレームのシーケンスを有するビデオ信号のフィンガープリントは、その信号の内容を示す情報の一部分である。フィンガープリントは、ある環境で、ビデオ信号の要約として考えられることがある。これに関連して、フィンガープリントは、また、シグニチャー又はハッシュとして記述されることもある。このようなフィンガープリントの知られている使用は、当該フィンガープリントをデータベースに記憶されているフィンガープリントと比較することによって、未知のビデオ信号の内容を識別することである。例えば、未知のビデオ信号の内容を識別するよう、その信号のフィンガープリントは、生成されて、既知のビデオオブジェクト（例えば、テレビ番組、フィルム、広告等。）のフィンガープリントと比較され得る。フィンガープリントの一致が認められる場合は、その内容の同一性がこのようにして決定される。明らかに、既知の内容を有するビデオ信号のフィンガープリントを生成し、それらのフィンガープリントをデータベースに記憶することも知られている。
【０００３】
ビデオ信号が処理され、劣化し、変形され、又は別なふうに得られるバージョンの、その内容を有する他のビデオ信号である場合でさえ、フィンガープリントが正確に内容を識別するために使用され得る点で、フィンガープリントを生成する方法にとって、得られるフィンガープリントが内容に関するロバストな表示であることが望ましい。このようなロバスト性要求を呈する代替の方法は、同じコンテンツの異なるバージョン（すなわち、異なるビデオ信号。）のフィンガープリントが、その共通する内容の身元証明が作られることを可能にするよう十分に類似すべきであることである。例えば、画素データのフレームのシーケンスを有する元のビデオ信号はフィルム（film）を含むことができる。その元のビデオ信号のフィンガープリントは、生成され、例えば、フィルムの名称のようなメタデータとともに、データベースに記憶され得る。次いで、元のビデオ信号のコピー（すなわち、他のバージョン。）が作られ得る。理想的には、コピーのいずれか１つで使用される場合に、コピーの内容がデータベースを閲覧することによって識別可能であるよう元のビデオ信号のフィンガープリントと十分に類似するフィンガープリントをもたらすフィンガープリント生成方法が好ましい。しかし、多数の要因により、この目的の達成が困難なものとされる。例えば、元のビデオ信号のコピーで、１又はそれ以上のフレームにおける広範囲明度及び／又はコントラストは変更されていることがある。同様に、色及び／又は画像の鮮明さが変更されていることがある。加えて、コピーは異なるフォーマットであることがあり、且つ／あるいは、１又はそれ以上のフレームでの画像は、スケーリング、シフト、又は回転をされていることがある。また、異なるバージョンのビデオコンテンツは異なるフレームレートを用いうる。極端な場合には、１つのバージョンのフィルム（例えば、コピー。）のフレームでの画素データは、同じフィルムの他のバージョン（例えば、オリジナル。）の対応するフレームでの画素データとは全く異なることがある。従って、課題は、上述したような要因のうちの１又はそれ以上に対してある程度ロバスト（すなわち、鈍感。）であるフィンガープリントをもたらすフィンガープリント生成方法を発明することである。
【０００４】
国際公開第０２／０６５７８２号パンフレット（特許文献１）は、オーディオ信号及び画像又はビデオ信号を含む情報信号のロバストなハッシュ（実際上、フィンガープリント。）を生成する方法を開示する。１つの開示される実施例で、フレームのシーケンスを有するビデオ信号のハッシュは、３０個の連続したフレームから取り出され、３０個（すなわち、シーケンスのフレームの夫々について１つずつ。）のハッシュワードを有する。ハッシュは、最初に各フレーム全体をサイズの等しい長方形ブロックに分割することによって生成される。ブロックごとに、画素の輝度値の平均は計算される。次いで、ハッシュを輝度の全体的なレベル及びスケールから独立させるために、２つの連続したブロックの間の輝度差が計算される。また、時間方向でのハッシュワードの相関を減らすよう、連続したフレームにおける空間微分平均輝度値の差も計算される。このように、得られる２進ハッシュで、各ビットは、ビデオ信号の夫々のフレームでの夫々の２つの連続するブロックの平均輝度から、及び直前のフレームでの同じ２つのブロックの輝度平均から導出される。
【０００５】
特許文献１で開示される方法は、ある程度のロバスト性を有するハッシュを提供するが、ハッシュが依然として上記の多数の要因、具体的に、それだけではないが、スケーリング、シフト、及び回転を含む変形や、フォーマットの変更や、ハッシュが導出される信号のフレームレート等に敏感である点で、問題は残っている。
【特許文献１】国際公開第０２／０６５７８２号パンフレット
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、上記の要因のうちの少なくとも１つに関して少なくともある程度よりロバストであるフィンガープリントをもたらす、ビデオ信号の内容を示すフィンガープリントを生成する方法を提供することを目的とする。本発明のある実施例は、スケーリング及び回転変更に対して改善されたロバスト性を具えたフィンガープリントを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の第１の態様は、データフレームのシーケンスを有するビデオ信号の内容を示すフィンガープリントを生成する方法であって：
各フレームの中央部分のみを複数のブロックに分割し、前記中央部分以外の各フレームの残りの部分をブロックに分割されないままとするステップ；
各ブロックでデータの特徴を取り出すステップ；及び
前記取り出された特徴からフィンガープリントを計算するステップ；
を有する方法を提供する。
【０００８】
このように、当該方法は、フィンガープリントを得るために各フレームの中央部分のみを使用する。各フレームの残りの外側部分は、その内容がフィンガープリントに寄与しないという意味で、無視される。この方法は、得られるフィンガープリントが、クロッピング（cropping）又はシフトを含む変形に対してよりロバストであり、更に、レターボックス・（letterboxed）フォーマットにあるビデオのフィンガープリンティングに特に適するという利点を提供する。
【０００９】
好ましくは、ブロックから特徴を取り出す前記ステップは、例えば、そのブロック内の画素の特性の計算等の計算を含みうる。
【００１０】
有利に、ある実施例で、前記残りの部分は前記中央部分を囲む。これより、当該方法は、前記中央部分の上、下、及び両側の一定量のフレームを無視する。このことは、通常フレームの最も知覚的に重要な部分であるものに更にフィンガープリントを集中させることとなるので、ロバスト性を更に改善する（ビデオ信号を捕捉する際に、カメラのオペレータは、当然、通常フレームの中央に主要な対称／動作を位置付ける。）。
【００１１】
ある実施例で、前記中央部分は前記フレームの中心部分を囲み、当該方法は、前記中心部分をブロックに分割されないままとするステップを更に有する。このように、周辺データを無視することに加えて、当該方法は、また、中心部分も無視することができる。このことは、フィンガープリントがスケーリング及びシフト変形に対してよりロバストにされるという利点を提供する。スケーリング及びシフト変形に対して、前記中心部分の内容は極めて敏感である。
【００１２】
ある実施例で、前記複数のブロックは、複数の異なったサイズを有するブロックを有する。このことは、フレームの異なる部分が異なる重み付け（すなわち、得られるフィンガープリントへの影響。）を与えられ得るという利点を提供する。
【００１３】
例えば、ある実施例で、前記複数のブロックは、複数の異なったサイズを有する複数の長方形ブロックを有し、前記長方形ブロックのサイズは、前記フレームの中心から外側に向かう少なくとも１つの方向で増大する。このように、前記中央部分の周辺に向かってより大きいブロックが存在し、一方、中心に向かってより小さいブロックが存在する。このことは、ブロックの密度がフレームの中心に向かって大きくなり、従って、フレームの知覚的により有意な部分が、最終的なフィンガープリントに対するより大きな影響力を与えられるという利点を提供する。
【００１４】
ある実施例で、前記複数のブロックは、複数の長方形でないブロックを有する。このことは、ブロック形状が、得られるフィンガープリントに特定の変形に対するロバスト性を与えるよう選択され得るという利点を提供する。
【００１５】
例えば、前記複数の長方形でないブロックは、幾つかの実施例で、複数の略扇形ブロックを有し、夫々の前記略扇形ブロックは、前記フレームの中心から夫々の対の半径によって境界を定められる。言い換えると、ブロックは、概して、パイ（pie）・セグメント形状を有することができる（とはいえ、この一般的な形状は、ブロックが前記中央部分に対して直角境界線によって１つの径方向端部で、例えば、また、フィンガープリント生成処理から除外されるあらゆる中心部分の形状によって内径端部で境界を定められる場合は変形され得る。）。このようなブロック形状の使用は、得られるフィンガープリントがスケーリング変形に対して特にロバストであるという利点を提供する。
【００１６】
ある実施例で、前記複数の長方形でないブロックは複数の略環状同心ブロックを有する。このことは、生成されるフィンガープリントが回転変形に対して特にロバストであるという利点を提供する。
【００１７】
好ましくは、各フレームの中心部分を無視する前記ステップは、ブロック形状のいずれかに関連して使用され得る。
【００１８】
本発明の他の態様は、請求項１０及び１３で定義されるフィンガープリントの生成方法を提供する。それらの関連する利点は上記から明らかであろう。
【００１９】
本発明の他の態様は、データフレームのシーケンスを有するビデオ信号の内容を示すフィンガープリントを生成する方法であって、各データフレームは複数のブロックを有し、各ブロックはビデオ画像の夫々の領域に対応する方法において：
選択されたサブセットが前記ビデオ画像の中央部分に対応するよう、フレームごとに前記複数のブロックのサブセットのみを選択するステップ；
前記選択されたサブセットの各ブロックでデータの特徴を取り出すステップ；及び
前記取り出された特徴からフィンガープリントを計算するステップ；
を有する方法を提供する。
【００２０】
このように、本発明の態様は、予めブロックに分割されたフレームを有する信号（例えば、圧縮されたビデオ信号。）からフィンガープリントを生成する方法を提供する。前記中央部分からのみフィンガープリントを得ることによって、本態様は、先と同じく、フィンガープリントが、クロッピング又はシフトを含む変形に対してよりロバストであり、また、レターボックス・フォーマットにあるビデオのフィンガープリンティングに特に適するという利点を提供する。
【００２１】
前記ビデオ信号が圧縮信号である場合に、ブロックからの特徴の抽出は計算を有しても良く、あるいは、代替的に、各ブロック内でデータのある部分（例えば、圧縮されていないソース信号で画素の対応するグループのあるＤＣ成分を示す、ＤＣＴ法を介して得られるブロックにおけるデータ。）を単純に複製するステップを有しても良い。
【００２２】
他の態様は、上記の態様のいずれかの発明方法を実行するよう配置される信号処理装置を提供する。
【００２３】
更なる態様は、上記の態様のいずれかの発明方法の実行を可能にするコンピュータプログラムと、そのようなプログラムが記録される記録媒体とを提供する。
【００２４】
更なる他の態様は、本発明のフィンガープリント生成方法を用いる放送監視方法、信号フィルタリング方法、自動ビデオライブラリ体系化方法、選択的記録方法、及び不正変更検出方法を提供する。
【００２５】
本発明のこれらの及び他の態様、並びに本発明の実施例の更なる特徴及びそれらの関連する利点は、実施例に関する以下の記載及び特許請求の範囲から明らかであろう。
【発明を実施するための最良の形態】
【００２６】
本発明の実施例について、添付の図面を参照して記載する。
【００２７】
ここで図１を参照して、図１は、本発明に従うフィンガープリント生成方法を表す図である。ビデオ信号２は、第１のフレームレートを有するデータフレーム２０の第１の列を有する。説明を簡単にするため、データフレーム２０のうちの２つしか図示されない。しかし、実際には、フィンガープリントを生成されている信号におけるデータフレームの数がよりずっと多いことは明らかである。第１のデータフレーム２０のシーケンスは、時系列に沿った位置に示されている。フレーム２０のシーケンスのフレームレートは一定である。言い換えると、データフレームは、一定間隔ごとの時間間隔の画像コンテンツのサンプルとして考えることができる。ある実施例で、ビデオ信号２は、ある適切な媒体に記憶されているフィルムの形をとる。代替の実施例で、信号２は、例えば、時系列上に示される２つのフレームの間の時間間隔が、連続するフレームの放送又は送信の間の実際の時間間隔（ひいては、あるあて先での連続するフレームの受信の間の実際の時間間隔）であるような放送信号であっても良い。
【００２８】
当該方法は、各フレーム２０の中央部分２２のみを複数のブロック２１に分割し、中央部分２２以外の各フレームの残りの部分をブロックに分割されないままとする処理ステップ２６を有する。この第１実施例で、中央部分２２はフレームの全幅であり、残りの部分２３は、中央部分２２の上及び下の２つの帯域（長方形領域）を有する。しかし、代替の実施例では、選択される中央部分は、以下の更なる記載から明らかにされるように、異なった形状及び／又は範囲を有しても良い。簡単のため、図１では、中央部分２２は、ちょうど４個のブロックｂ１〜ｂ４に分割されるよう示されている。しかし、実際には、より多くのブロックが使用され得る。
【００２９】
次いで、当該方法は、各ブロック２１でデータの特徴Ｆを取り出す処理ステップ２７と、取り出した特徴からフィンガープリント１を計算するステップとを更に有する。この例では、特徴を取り出すステップ２７は、ソース信号２と同じフレームレートを有して、特徴を取り出されたフレーム５０のシーケンス５を生成するステップを有する。各特徴を取り出されたフレーム５０は、中央部分２２から分割されたブロック２１の夫々に対応する特徴データＦ１〜Ｆ４を含む。フィンガープリント１を計算するステップは、この例では、特徴を取り出されたフレーム５０から、ソースフレームレートでのサブフィンガープリント３０のシーケンス３を生成する処理ステップ５３と、サブフィンガープリント３０のシーケンス３に作用して、それらをフィンガープリント１を形成するよう集める更なる処理ステップ３１とを有する。サブフィンガープリント３０の夫々は、ソースビデオ信号の少なくとも１フレームにある中央部分のデータコンテンツから得られ、そのデータコンテンツに依存する。得られるフィンガープリント１は信号２の内容を示す。しかし、好ましくは、フィンガープリントは、各フレームの残りの部分２３に含まれる元の信号の如何なるコンテンツからも独立である。このように、フィンガープリントは、事実上、中央部分２２の上及び下の帯域にあるソース信号の内容を無視する。
【００３０】
ソースビデオ信号に関する場合のように、処理ステップ５３によって生成されるサブフィンガープリントのシーケンス３は、適切な媒体に記憶されているファイルの形をとっても良く、あるいは、代替的に、適切に配置されたプロセッサから出力されるサブフィンガープリント３０の実時間遷移であっても良い。
【００３１】
ここで、図２を参照して、代替の実施例で、フィンガープリントを導出する各フレーム２０の中央部分２２はフレーム２０の全幅に及ばない。しかし、この例で、中央部分２２はフレームの全高に及ぶ。残りの部分２３は、その両側の垂直な帯域を有する。
【００３２】
図３には、本発明の他の実施例におけるブロックへのビデオフレームの分割が表される。この場合に、中央部分は円形の外側周囲を有し、残りの部分２３は中央部分を囲む。更に、中央部分はフレームの中心部分２９を囲む。その中心部分２９は、ブロックに分割されない。このように、フィンガープリント生成方法は、フレームの中心にある中心部分２９、及び周辺部分２３の両方のデータコンテンツを無視する。中央部分は、この例では、概して環状であり、複数の環状ブロック２１に分割される（言い換えると、この例で、ブロックはリングである。）。環状ブロックの使用は、結果として生ずるフィンガープリントで回転ロバスト性の利点を提供する。
【００３３】
ここで、図４を参照して、ある他の実施例で、各フレーム２０は、複数の長方形でないブロックに分割される。この例で、各ブロック２１は、フレームの公称中心Ｃからの夫々の対の半径２１０によって、並びにフレームの境界線及び中心部分２９の境界線によって境界を定められた略扇形である（すなわち、概して、パイ部分の形状をとる。）。中心部分２９は、先と同じく、ブロック分割処理から除外される。扇形ブロック２１及び除外される中心部分２９の使用は、得られるフィンガープリントがスケーリングに対してロバスト性を示すという利点を提供する。
【００３４】
ここで図５を参照して、これは、画素データを夫々有するビデオフレーム２０のシーケンスを有するビデオ信号の形をとる情報信号２のデジタルフィンガープリントを生成する、本発明を具現するフィンガープリント生成方法の部分を示す。当該方法は、ソースフレーム２０の夫々の中央部分２２を複数のブロック２１に分割する処理ステップ２６を有する。簡単のために、各中央部分２２は、ｂ１〜ｂ４と符号を付されるちょうど４個のブロック２１に分割されるよう示される。明らかなように、このブロックの数は単なる例示であって、実際には、異なる数のブロックが使用され得る。当該方法は、各ブロック２１の特徴を計算するステップを更に有する。次いで、計算した特徴データを用いて、特徴を取り出されたフレーム５０のシーケンス５が生成される。これより、各特徴を取り出されたフレーム５０は、フレームの第１のシーケンスの夫々の１つの複数のブロックごとに、計算したブロック特徴データを含む。表される例で、処理ステップ２７で計算される特徴は、各ブロック２１での画素のグループの平均輝度Ｌである。このように、各特徴を取り出されたフレーム５０は、４つの平均輝度値Ｌ１〜Ｌ４を含む。次いで、処理ステップ５４で、データフレーム４０の第２のシーケンス４が、特徴を取り出されたフレームのシーケンス５から構成される。第２のシーケンスのフレーム４０の夫々は、ソースフレームから分割された４つのブロックの夫々について１つである、４つの平均輝度値を含む。データフレーム４０の第２のシーケンス４は、この例で、ソースビデオ信号２のフレームレートから独立した所定のレートにある。従って、この所定のレートは、一般に、ソースフレームレートとは異なり、故に、第２のシーケンスのフレーム４０のうちの幾つかは、特徴を取り出されたフレーム５０の位置の間にある時間上の位置に対応する。このように、本例では、第２のシーケンスのデータフレーム４０に含まれる平均輝度値は、補間を含む処理によって、特徴を取り出されたフレーム５０の内容から得られる。図中、第２のシーケンス４の最初に描かれるフレームは、特徴を取り出されたフレーム５０の第１のシーケンスの時系列上の位置に厳密に対応しており、従って、それに含まれる平均輝度値は、その特徴を取り出されたフレーム５０から単純に複製され得る。しかし、データフレーム４０のシーケンスにおける２番目のフレームは、特徴を取り出されたフレーム５０の最初のものと２番目のものとの間にある時系列上の位置で発生する。従って、この２番目のフレーム４０の平均輝度値の夫々は、時系列上で、“周囲の”特徴を取り出されたフレーム５０からの２つの平均輝度値を用いた計算を伴う処理によって導出されている。次いで、処理ステップ４３で、サブフィンガープリント３０のシーケンスが、データフレーム４０のシーケンスでのブロック平均輝度値から計算（導出）される。本例では、各サブフィンガープリント３０は、第２のシーケンス４のフレーム４０の中の夫々１つの内容から、及びその第２のシーケンス４にある直前のフレーム４０から得られる。
【００３５】
次いで、独立したレートでのサブフィンガープリントのシーケンスは、フィンガープリントがソースフレームの中央部分２２からのみ得られる結果として、ある程度のフレームレートロバスト性と、例えばクロッピング及びシフトのような変形に対するロバスト性とを具えるフィンガープリントを提供するよう処理され得る。
【００３６】
ここで、情報信号、及び具体的にはビデオ信号のフィンガープリンティングに関する更なる背景情報が、本発明の更なる実施例及び実施例の更なる特徴に関する記載とともに与えられる。
【００３７】
ビデオ・フィンガープリントは、ある実施例では、ビデオのセグメントの内容を識別するコード（例えば、情報のデジタル部分。）である。理想的には、特定の内容に関するビデオ・フィンガープリントは、一意である（すなわち、異なる内容を有する全ての他のビデオセグメントのフィンガープリントと異なる。）のみならず、ひずみ及び変形に対してロバストでなければならない。
【００３８】
ビデオ・フィンガープリントは、また、ビデオオブジェクトの要約としても考えられ得る。望ましくは、フィンガープリント関数Ｆは、（他のフィンガープリントとの整合のために）データベースへの記憶及び有効な検索を容易にするために、大きく且つ可変な数のビットを有するビデオオブジェクトＸを、より小さく且つ固定の数のビットしか有さないフィンガープリントにマッピングするべきである。
【００３９】
また、フィンガープリントが良好なコンテンツ分類子であるためのビデオ・フィンガープリントの要件について、以下の通りに簡単に述べる。理想的には、ビデオクリップのフィンガープリントは一意であり、異なったビデオクリップのフィンガープリントが類似する確率は低いことを意味する。同じビデオクリップの異なるバージョンに対するフィンガープリントは類似すべきであり、元のビデオ及びその処理されたバージョンのフィンガープリントの類似の確率は高いことを意味する。
【００４０】
以下の記載を理解するのに有用な幾つかの定義は、以下の通りである：
サブフィンガープリントは、情報信号のフレームのシーケンスの一部の内容を示すデータの一部分である。ビデオ信号の場合には、サブフィンガープリントは、ある実施例では２進ワードであり、特定の実施例では３２ビット列である。本発明の実施例で、サブフィンガープリントは、１よりも多いフレームの内容から得られ、この内容に依存しうる；
ビデオセグメントのフィンガープリントは、そのサブフィンガープリントの順序正しい集合を表す；
フィンガープリントブロックは、“フィンガープリント”クラスのサブグループとして考えることができ、ある実施例では、ビデオフレームの隣接するシーケンスを表す２５６個のサブフィンガープリントのシーケンスである；
メタデータは、しばしば、‘映像の名称’、‘アーティスト’等のパラメータを有するビデオクリップの情報であり、エンドアプリケーション（end-application）はこのメタデータの取得に関心がある；
ハミング距離：２つのビットパターンを比較する際に、ハミング距離は、２つのパターンにおけるビット差の総数（count）である。より一般的には、２つの順序付き項目リストが比較される場合に、ハミング距離は、完全に同じように一致しない項目の数である。この距離は、符号化情報に適用可能であり、シティブロック（city-block）距離（座標軸に沿った距離の絶対値の和）又はユークリッド距離（座標軸に沿った距離の二乗の和の平方根）よりもしばしば有用である、特に簡単な比較メトリックである。
【００４１】
ビットエラーレート（ＢＥＲ）：２つのフィンガープリントの間のビットエラーレートは、その２つでの異なるビットの数を表す比である。それは、また、フィンガープリントブロックにおけるビットの数（すなわち、２５６×３２＝８１９２）に対する、２つのフィンガープリントブロックのビット列の間のハミング距離の比とも呼ばれることがある。
【００４２】
クラス間ＢＥＲ比較：クラス間ＢＥＲは、２つの異なるビデオシーケンスに対応する２つのフィンガープリントブロックの間のビットエラーレートを指す。
【００４３】
クラス内ＢＥＲ比較：クラス内ＢＥＲ比較は、同じビデオシーケンスに属する２つのフィンガーブロックの間のビットエラーレートを指す。２つのビデオシーケンスは、それらが幾何学的又は他の定性的な変形を受けているという意味で異なることがあることが知られうる。しかし、それらは、知覚的に人間の目に類似する。
【００４４】
本発明を具現するビデオフィンガープリンティングシステムが図６に示される。このビデオフィンガープリンティングシステムは、２つの機能、すなわち、フィンガープリントの生成及びフィンガープリントの識別を提供する。フィンガープリントの生成は、前処理段階及び識別段階の両方で行われる。前処理段階で、ビデオファイル６２のフィンガープリント１（映画、テレビ番組及びコマーシャル等。）が生成され、データベース６５に格納される。図６には、この段階が箱６１に示されている。識別段階の間、フィンガープリント１は、先と同じく、このような手順（入力ビデオクエリ６８）から生成され、クエリとしてシステムへ送信される。フィンガープリント識別段階は、第１に、データベース検索方法を有する。データベース内の大量のフィンガープリントのために、フィンガープリントを検索するためにブルートフォース（brute-force）アプローチを使用することは実際上不可能であることが知られうる。効率的に実時間でフィンガープリントを検索するための別のアプローチは、本発明のある実施例で導入されている。この段階での入力はフィンガープリントブロッククエリ６８であり、出力は識別結果を含むメタデータ６２５である。
【００４５】
わずかにより詳細に、図６に示される実施例で、ビデオファイル６２からの符号化データ６２３は、デコーダ及び正規化部６３によって、正規化（これは、例えば、一定分解能へのビデオ分解能のスケーリングを含みうる。）され且つ復号される。次いで、この段階６３は、正規化された復号ビデオフレームをフィンガープリント抽出段階６４へ供給する。フィンガープリント抽出段階６４は、ソースビデオファイルのフィンガープリント１を生成するよう、入来するフレームをフィンガープリント抽出アルゴリズムにより処理する。このフィンガープリント１は、ビデオファイル６２に関して、対応するメタデータ６２５とともにデータベース６５に格納される。入力ビデオクエリ６８は、同じくデコーダ／正規化部６３によって処理される符号化データ６８３を有し、フィンガープリント抽出段階６４は、このクエリに対応するフィンガープリント１を生成し、そのフィンガープリントをフィンガープリント検索モジュール６６へ供給する。フィンガープリント検索モジュール６６は、データベース６５内の一致するフィンガープリントを探し、そのクエリに関して一致するものが見つかった場合は、対応するメタデータ６２５が出力６７として供給される。
【００４６】
ビデオフィンガープリンティングシステムで考慮すべきパラメータは、以下の通りである：
ロバスト性：深刻な信号劣化の後に、ビデオクリップは依然として識別され得るか？高いロバスト性を達成するために、フィンガープリントは、信号劣化に対して（少なくともある程度）不変である知覚的特徴に基づくべきである。望ましくは、ひどく劣化した映像は、依然として、極めて類似するフィンガープリントをもたらす。本人拒否率（ＦＲＲ（false  rejection  rate））が、一般に、ロバスト性を表すために使用される。本人拒否は、知覚的に類似するビデオクリップのフィンガープリントが肯定的一致を得ることができないほどに異なる場合に発生する。
【００４７】
信頼性：どれくらいの頻度で映像が誤って識別されるか？これが発生する割合は、通常、他人受入率（ＦＡＲ（false  acceptance  rate））と呼ばれる。
【００４８】
フィンガープリントのサイズ：どれくらいのストレージがフィンガープリントに必要とされるか？高速な検索を可能にするよう、フィンガープリントは、通常、ＲＡＭメモリに格納される。従って、フィンガープリントのサイズは、通常はビット毎秒又はビット毎映画で表され、フィンガープリントのデータベースサーバに必要とされるメモリリソースをかなり決める。
【００４９】
精度（granularity）：映像のどれだけの秒数がビデオクリップを識別するのに必要とされるか？精度は、用途に依存するパラメータである。ある用途では、映画全体が識別のために使用され得、他の用途では、ほんの一部の映像しか用いずに映画を識別することが好まれる。
【００５０】
検索速度及び拡張性：フィンガープリントデータベース内でフィンガープリントを見つけるのにかかる時間はどれくらいか？データベースは数千の映画を含むかどうか？ビデオフィンガープリンティングシステムの商業的配備のために、検索速度及び拡張性は重要なパラメータである。検索速度は、限られた計算リソース（例えば、わずかにハイエンドのＰＣ。）を用いて１０，０００本を越える映画を含むデータベースに関してミリセカンドのオーダーでなければならない。
【００５１】
フィンガープリントに対する変形の影響：ビデオ・フィンガープリントは、ビデオシーケンスに適用される様々な変形及び処理により変化しうる。このような変形には、例えば、平滑化及び圧縮が含まれる。これらの変形は、元のビデオシーケンス及び変形されたシーケンスについて異なったフィンガープリントブロックをもたらし、従って、元のバージョン及び変形されたバージョンのフィンガープリントが比較される場合に、ビットエラーレート（ＢＥＲ）が生ずる。ある場合に、低ビットレートへの圧縮は、ビデオシーケンスにおけるフレームの単なる平滑化（ノイズ低減）と比較して極めて骨の折れる処理である。従って、前者の場合におけるＢＥＲは、後者に比べてずっと高い。
【００５２】
２つのフィンガープリントブロックの間の相関は、また、変形の程度に依存して変化する。変形の程度が少なければ少ないほど、相関は高くなる。
【００５３】
データベースでのフィンガープリントの検索は、容易な作業ではない。本発明の実施例で使用され得る検索技術は、上記特許文献１に記載されている。その課題の簡単な説明は以下の通りである。
【００５４】
本発明のある実施例で、ビデオフィンガープリンティングシステムは、５５ヘルツ（Ｈｚ）でサブフィンガープリントを生成する。従って、存続期間が２時間である映像から生成されるサブフィンガープリントの数は、（２×６０×６０）ｓ×５５サブフィンガープリント／ｓ＝３９６０００サブフィンガープリントである。２０００時間の映像のフィンガープリント（３９，６００万のサブフィンガープリント）を含むデータベースでは、ブルートフォース検索アルゴリズムは実時間で結果を生成することができない。検索タスクは、３９，６００万のサブフィンガープリントでの立場を見つける必要がある。ブルートフォース検索を用いると、これは３９，６００万のフィンガープリントブロック比較を要する。最新のＰＣを用いると、毎秒およそ２００，０００のフィンガープリントブロック比較のレートが達成され得る。従って、本例の全体的な検索時間は３０分程度である。
【００５５】
ブルートフォースアプローチは、インデックス付きリストを用いることによって改善され得る。例えば、以下のシーケンス：
“ＡＭＳＴＥＲＤＡＭＢＥＲＬＩＮＮＥＷＹＯＲＫＰＡＲＩＳＬＯＮＤＯＮ”
を考える。
【００５６】
各都市の頭文字によってリストはインデックスを付される。語“ＰＡＲＩＳ”を見つけたい場合は、“Ｐ”に関するサブリストに直接進み、その語を検索することができる。しかし、フィンガープリントが本例で表されるほど簡単でない場合がある。これは、質問「クエリは、正確な語“ＰＡＲＩＳ”を含みますか？」から明らかである。クエリは、“ＱＡＲＩＳ”、“ＱＢＲＩＳ”、“ＱＡＳＩＳ”、“ＰＢＲＨＳ”若しくは“ＯＢＳＩＴ”又はその他の近い語を含みうる。従って、検索を開始するためのインデックスでの正しい開始位置さえ得られない可能性があり、システムはスケーリングを受けたバージョンのクリップを不等に拒否するであろう。その解決法は、近しい一致を見つけることである。従って、クエリ語“ＯＢＳＪＴ”の正確な一致を見つけることができない場合に、この語に含まれる文字の夫々は切り替えられ、得られた語について一致が検索される。
【００５７】
このように、本発明のある実施例で、サブフィンガープリントを計算しながら、サブフィンガープリントの各ビットがその強さ（strength）に従ってランク付けされる。正確な一致がサブフィンガープリント（文字）のいずれについても見つけられない場合は、弱いビットは、その強さが大きくなる順で、サブフィンガープリントの中で切り替えられる。従って、最も弱いビットは最初に切り替えられ、結果として得られる新しいフィンガープリントについて一致が検索される。一致が見つけられない場合は、次に最も弱いビットが切り替えられ、以降同様に続く。所定の最大数のビットを切り替えることによって１よりも多い一致が見つけられる場合に、最小ＢＥＲ（＜閾値）を有するものが極めて最も近い一致として考えられる。従って、クエリが“ＱＡＲＩＳ”であって、強さ推定アルゴリズムが“Ｑ”を最も弱いビットとランク付けする場合は、例えば、“Ｑ”を“Ｐ”に切り替えた直後に一致が見つけられ得る。しかし、“Ｑ”が最も強いとランク付けられる場合は、検索にはより多くの時間を要する。
【００５８】
アルゴリズムの性能の解析において、用語データベースヒットがしばしば使用される。データベースヒットは、データベースにおいて一致（正確な一致であっても、又は近しい一致であっても良い。）が見つけられる状況に相当する。
【００５９】
ここで、本発明の実施例でのビデオフィンガープリンティング応用について、より詳細に論じる。ビデオフィンガープリンティングは別として、第三者送信の範囲内のビデオシーケンスの識別に適用可能な、例えばウォータマーク挿入のような他の技術がある。しかし、この処理は、変更されるビデオシーケンス、及びビデオストリームに挿入されるウォータマークに依存する。次いで、ウォータマークは、後にストリームから取り出されて、データベースエントリと比較される。このことは、ウォータマークがビデオ要素とともに送られることを要する。他方で、ビデオ・フィンガープリントは主として記憶されて、それはビデオ要素とともに送られる必要はない。従って、ビデオ・フィンガープリントは、ビデオ要素がウェブ上で送信された後、依然としてビデオ要素を識別することができる。ビデオフィンガープリンティングの多数の応用が考えられてきた。それらを以下に挙げる：
ファイル共有のためのフィルタリング技術：世界中の映画産業は、ピア・ツー・ピア（ｐ２ｐ）のネットワークにわたるビデオファイル共有により大きな損失に見舞われている。一般に、映画が公開される場合に、映像の“ハンディカム（handy  cam）”プリントが所謂共有サイト（sharing  sites）を既に数巡している。とはいえ、ファイル共有プロトコルは互いに極めて異なるが、それらのほとんどは暗号化されない方法を用いてファイルを共有する。フィルタリングは、このようなコンテンツ配給における積極的介入（active  intervention）を指す。ビデオフィンガープリンティングは、このようなフィルタリングメカニズムの適切な候補と考えられている。更に、それは、ウォータマークが映像とともに送られる必要がある場合に、コンテンツ認識のために使用され得るウォータマークのようなその他技術である。ウォータマークが映像とともに送られる必要がある場合には、コンテンツ認識は保証され得ない。このように、本発明の１つの態様は、本発明の第１の態様に従うフィンガープリント生成方法を利用するフィルタリング方法及びフィルタリングシステムを提供する。
【００６０】
放送監視：監視は、とりわけ、著作権使用料の回収、プログラム検証及び視聴率のためのラジオ、テレビ又はウェブ放送のトラッキングを指す。この用途は、放送しているものに対して直接的な影響を有さない点で受動的である。この用途の主たる目的は、観察及び報告をすることである。フィンガープリンティングに基づく放送監視システムは、幾つかの監視サイトと、フィンガープリントサーバが配置されているホストコンピュータサイトとを有する。監視サイトでは、フィンガープリントは、全ての（ローカルな）放送チャネルから取り出される。ホストコンピュータサイトは、監視サイトからフィンガープリントを集める。その後に、巨大なフィンガープリントデータベースを備えるフィンガープリントサーバは、夫々の放送チャネルの再生リストを生成する。このように、本発明の他の態様は、本発明の第１の態様に従うフィンガープリント生成方法を利用する放送監視方法及び放送監視システムを提供する。
【００６１】
マルチメディアライブラリの自動索引作成：多数のコンピュータユーザは、数百、時に数千のビデオファイルを含むビデオライブラリを有する。ファイルが、例えば、ＤＶＤからのリッピング、画像の走査及びファイル共有サービスからのダウンロードのように、様々なソースから得られる場合に、かかるライブラリは、しばしば、上手く編成されない。フィンガープリンティングによりこれらのファイルを識別することによって、ファイルは、例えば、アーティスト、音楽アルバム又はジャンルに基づく容易な編成を可能にしながら、正確なメタデータにより自動的にラベルを付され得る。このように、本発明の他の態様は、本発明の第１の態様に従うフィンガープリント生成方法を利用する自動索引作成方法及びシステムを提供する。
【００６２】
テレビジョンコマーシャルの遮断及び選択的記録：テレビジョンコマーシャルの遮断は、デジタル放送方式で実現され得る。例えば、デジタルビデオ放送（ＤＶＢ）規格に基づくマルチメディアホームプラットフォーム（ＭＨＰ）方式で、テレビジョンは外界に接続される。フィンガープリント生成機能を具えたフィンガプリンティングサーバ及びテレビ受像機へのこのような接続の１つにより、テレビジョンコマーシャルは視聴者から遮断され得る。この用途は、また、コマーシャルのフィルタリングに関する追加の利点を有して、番組の選択的な記録を可能にするツールとしても使用され得る。このように、本発明の他の態様は、本発明の第１の態様に従うフィンガープリント生成方法を利用するコマーシャル遮断及び選択的記録の方法及びシステムを提供する。
【００６３】
伝送ラインでの映像の不正変更又はエラーの検出：先に論じられたように、元の映画及びその変形された（又は処理された）バージョンのフィンガープリントは、概して、互いに異なる。ＢＥＲ機能は、２つの間の差を確認するために使用され得る。フィンガープリントのこのような特性は、正確なビデオシーケンスを送信するはずの伝送ラインの異常を検出するために使用され得る。また、それは、映画又は映像要素が不正に変更されているかどうかを自動的に（手動介入を伴わずに）検出するために使用され得る。このように、本発明の他の態様は、本発明の第１の態様に従うフィンガープリント生成方法を利用する不正変更及びエラー検出方法及びシステムを提供する。
【００６４】
ビデオ・フィンガープリント試験は、本発明の実施例で使用されるフィンガープリント抽出アルゴリズムを評価するために使用されている。かかる試験は、信頼性試験及びロバスト性試験を含む。アルゴリズムによって生成されるフィンガープリントの信頼性は、他人受入率に密接に関わる。信頼性試験では、２つのフィンガープリントブロックの比較から得られるビットのＢＥＲ分布が、理論上の他人受入率を提供するために検討されている。クラス間ＢＥＲ分布は、例えば、アルゴリズムの性能のロバストな表示として働く。
【００６５】
本発明の実施例で使用されるフィンガープリント抽出アルゴリズムを評価するために使用されるロバスト性試験では、４つのビデオクリップと、それらの変形バージョンの幾つかとを含む小さなデータベースが作られた。映像は、幾つかの変形を受けうる。開発されたフィンガープリントアルゴリズムを試験するために、画像に対する以下の変形が考えられる。例えば、変形には、スケーリング、水平スケーリング、垂直スケーリング、回転、上方シフト、下方シフト、ＣＩＦ（共通交換フォーマット（Common  Interchange  Format））スケーリング、ＱＣＩＦ（Quarter  Common  Interchange  Format）スケーリング、ＳＩＦ（標準共通交換フォーマット（Standard  Common  Interchange  Forma））スケーリング、メジアンフィルタリング、明度変更、コントラスト変更、圧縮、フレームレート変更がある。このようにして、このような様々な変形を用いる、元のクリップの変形されたバージョンが作られ、元のバージョン及び変形されたバージョンのフィンガープリントが比較される。
【００６６】
ここで、本発明を具現するビデオフィンガープリンティング方法及びシステムで使用されるアルゴリズムについて記載する。最初に、所謂差動ブロック輝度アルゴリズム（differential  block  luminance  algorithm）について記載する。次いで、アルゴリズムのロバスト性を増すための、基本アルゴリズムに対する改善について記載する。
【００６７】
差動ブロック輝度アルゴリズムで、アルゴリズムは時空間領域で特徴を計算する。更に、ビデオフィンガープリンティングのための主な応用のうちの１つは、ピア・ツー・ピアネットワーク上のビデオファイルのフィルタリングである。システムが利用可能な圧縮データのストリームは、特徴抽出がブロックに基づくＤＣＴ（離散コサイン変換）係数を使用する場合に、有利に使用され得る。
【００６８】
このアルゴリズムの基本理念は、以下の通りである：
１．  フレームごとにビデオシーケンスを一意に表す特徴を得ること；
２．  知覚的に重要な特徴を得ること。画像では、色成分に比べて輝度特性が重要であることが知られる。また、ＹＵＶ色空間は、全てのビデオエンコーダに関して、世の中一般に通用する一次サブサンプリングエンコーダである。従って、輝度値は、特徴を取り出すために使用される；
３．  同様にほとんどの圧縮されたビデオストリームからの容易な特徴抽出を可能にするよう、ブロックに基づくＤＣＤ係数から容易に計算され得る特徴を選択する。これらの係数に基づき、提案されるアルゴリズムは、比較的大きな領域にわたって計算される単純な統計値、すなわち、平均輝度に基づく。
【００６９】
サブフィンガープリントは、以下のように取り出される。
【００７０】
１．  各ビデオフレームはＲ行及びＣ列の格子で分割され、Ｒ×Ｃ個のブロックが得られる。これらのブロックの夫々について、画素の輝度値の平均が計算される。フレームｐにあるブロック（ｒ，ｃ）の平均輝度は、ｒ＝１，２，．．．，Ｒ及びｃ＝１，２，．．．，Ｃに関してＦ（ｒ，ｃ，ｐ）と表される。
【００７１】
図７は、このようにしてブロック２１に分割されたビデオデータフレーム２０を表す。フレームの表示は、Ｒ＝４及びＣ＝９に関してＲ×Ｃ個のブロック示す（すなわち、本例では、ブロックは全部で３６個である。）。輝度値の平均はブロックの夫々について計算され、Ｒ×Ｃ個の平均値が得られる。数字の夫々は、入力ビデオフレームにおける対応する領域を表す。
【００７２】
２．  ステップ１で計算された平均輝度値は、フレーム（特徴を取り出されたフレーム）においてＲ×Ｃ個の“画素”として視覚化され得る。言い換えると、これらはフレームの異なる部分のエネルギを表す。カーネル（kernel）［−１  １］を有する（すなわち、同じ行の隣り合うブロックの間の差をとる）空間フィルタ、及びカーネル［−α  １］を有する時間フィルタが、低分解能のグレースケール画像のこのシーケンスで適用される。従って、現在のフレーム上の領域１３及び１４から得られる平均値であるＭ１３及びＭ１４と、次のフレームにおける対応する領域から得られる平均値であるＭ｀１３及びＭ｀１４とを考えると、値（サブフィンガープリントと呼ばれる。）は
【数１】
2009542081.tif 000003
のように計算される。
【００７３】
３．  ＳｆｔＦＰｎのサイン（sign）値は、サブフィンガープリントでのビットの値を決定する。より具体的には、ｎ＝１．．３２に関して、
【数２】
2009542081.tif 000004
である。
【００７４】
簡単に且つより厳密に述べると、ｒ＝１，２，．．．，Ｒ及びｃ＝１，２，．．．，Ｃに関して、
【数３】
2009542081.tif 000005
を有する。このアルゴリズムは、“差動ブロック輝度アルゴリズム”と呼ばれる。それは、サブフィンガープリントのシーケンスをもたらす。サブフィンガープリントは、それが作用する“ソース（source）”画像フレームの夫々について１つである。それらのフィンガープリントのビットは、上記のＢ（ｒ，ｃ，ｐ）によって与えられる。
【００７５】
このアルゴリズムで、アルファ（α）は重み付け係数として考えることができ、“次”のフレームでの値がどの程度考慮されるかを表す。別の実施例は、αに異なる値を使用しても良い。ある実施例では、例えば、αは１に等しい。
【００７６】
ここで、上記アルゴリズムに関連して、可変なフレームレートに対するロバスト性の問題について論じる。動画、テレビ、及びコンピュータ映像表示で、フレームレートは、毎秒投影又は表示されるフレーム又は画像の数である。フレームレートは、フィルム、テレビ又は映像に関わらず、オーディオ及びピクチャを同期させる際に使用される。２４、２５及び３０フレーム毎秒のフレームレートは一般的であり、それらは夫々異なる産業分野での使用を有する。米国では、動画についての専門的なフレームレートは２４フレーム毎秒であり、一方、テレビについては、３０フレーム毎秒のフレームレートである。しかし、異なる規格が世界中のビデオ放送で見られるので、これらのフレームレートは変更可能である。上述される基本の差動ブロック輝度フィンガープリント抽出アルゴリズムは、フレームごとに機能する。従って、サブフィンガープリント生成レートは、ビデオソースによって提供されるフレームレートのそれと同じである。例えば、フィンガープリントがアメリカ合衆国で放送中の映画から取り出される場合は、３０個のサブフィンガープリントが１秒で取り出され得る。従って、データベースに記録される対応するフィンガープリントブロックは、２５６／３０＝８．５３秒の映像に相当しうる。欧州からのビデオクエリがシステムに与えられる場合は、それは２５Ｈｚのフレームレートを有しうる。この場合に、フィンガープリントブロックは、２５６／２５＝１０．２４秒に相当しうる。原理上は、これら２つのフィンガープリントブロックは、それらが２つの異なる時間フレームに相当するので、互いに一致しない。
【００７７】
一般論としてこれを見ると、フィンガープリントシステムは、基本的に２つの機能を提供することができる。第１に、フィンガープリントは、データベースでの記録のために生成される。第２に、フィンガープリントは、識別目的のためにビデオクエリから生成される。一般に、これら２つの段階でのビデオソースが夫々ν及びμとしてフレームレートを有する場合に、かかる２つの場合における（２５６個のサブフィンガープリントを有する）フィンガープリントブロックは、夫々、（２５６／ν）秒及び（２５６／μ）秒の映像に相当しうる。これらの時間フレームは異なっており、従って、これらの存続期間の間に生成されるそれらのサブフィンガープリントは異なるフレームに由来する。従って、それらは一致しない。
【００７８】
ある程度のフレームレートロバスト性を提供するための、基本の差動ブロック平均輝度アルゴリズムの変形について、以下に記載する。
【００７９】
本発明の実施例におけるフレームレートロバスト性は、ビデオソースのフレームレートに関わりなく一定レートでサブフィンガープリントを生成することによって、組み入れられる。映像の２つの最も一般的なフレームレートは、２５（ＰＡＬ）及び３０（ＮＴＳＣ）Ｈｚである。その場合に、所定のサブフィンガープリント生成レートのための１つの選択は、これらの２つの平均、すなわち、（２５＋３０）／２＝２７．５である。従って、このレートで生成される２５６個のサブフィンガープリントから形成されるフィンガープリントブロックは、２５６／２７．５＝９．３秒の映像に相当しうる。ビデオフィンガープリンティングの応用の幾つか（例えば、テレビジョンコマーシャル遮断。）で、より高い精度（granularity）が必要とされうる。従って、ある実施例では、２７．５×２＝５５Hzの代替の（より高い）周波数がフィンガープリント生成のために使用される。以下で記載される更なる例は、この周波数をフィンガープリント抽出のために使用する（しかし、明らかなように、周波数はそれ自体単なる一例に過ぎず、更なる実施例は異なった所定周波数を利用することができる。）。
【００８０】
差動ブロック平均輝度アルゴリズムでフレームレートロバスト性を組み入れるために、上述されるアルゴリズムにおいてステップ１と２との間で変更がなされる。ビデオソースの周波数がνＨｚである場合に、Ｆ（ｒ，ｃ，ｐ）．．．Ｆ（ｒ，ｃ，ｐ＋ν）のシーケンスは５５Ｈｚへと補間される。この処理は、毎秒５５個のサブフィンガープリントの発生をもたらす（ｐ≧１の場合に、５４個のサブフィンガープリントが生成されうる最初の秒を除く。）。これは、サブフィンガープリントの生成をビデオソースのフレームレートから独立したものとする。この場合に、生成されるサブフィンガープリントは、ビデオソースの時間フレームに関わりなく一定の時間フレームに関してフレームを表す。図８は、上述される方法を表す。ビデオフレームは２５Ｈｚの周波数を有するとする。従って、Ｆ（ｒ，ｃ，２）及びＦ（ｒ，ｃ，３）は、夫々、時間２／２５及び３／２５での平均フレームを表す。平均フレームＦ｀（ｒ，ｃ，４）、Ｆ｀（ｒ，ｃ，５）、Ｆ｀（ｒ，ｃ，６）及びＦ｀（ｒ，ｃ，７）は、夫々、時間４／５５、５／５５、６／５５及び７／５５での、線形補間された平均フレームを表す。言い換えると、これらの線形補間された平均フレームの内容は、ソースフレームのシーケンスから直接に得られた平均フレームの内容から、計算によって、再生されている。このように、変形されたアルゴリズムは、所定のフレームレート（例えば、５５Ｈｚ。）を有する、（平均輝度値を含む）特徴を取り出されたフレームのシーケンスの生成を有する。それらのフレームの内容は、（必要に応じ）補間を含む処理によって、（直接に特徴を取り出されたフレームのシーケンスを介して）ソースフレームの内容から得られる。線形補間が上記の例では使用されているが、他の補間技術が代替の実施例では使用され得る。
【００８１】
（特徴を取り出されたフレームを所定のレートで生成するために補間を用いる）上記の変形された差動ブロック平均輝度アルゴリズムから得られるフィンガープリントの特性は、上記の様々な変形によるビットエラーレートを評価する試験の実行を含め、解析されてきた。試験において、（ビットの切替（toggling）を用いる）上記の検索方法は、正確な一致の検索に加えて、元のバージョンのフィンガープリント及び変形されたバージョンのフィンガープリントの近しい一致を見つけるために使用された。
【００８２】
以下の特徴がその結果から分かった：
好ましい程度のフレームレートロバスト性が達成された。
【００８３】
しかし、水平スケーリング及び垂直スケーリングは、大きい場合に、高いＢＥＲをもたらしうる。これは、水平及び垂直スケーリングの間に、フレームにある画素が隣のブロックへ移動するという事実から理解され得る。このことは、異なる平均の計算を生じさせる。水平スケーリングの影響は、ブロックのサイズが垂直方向より水平方向で小さい場合により顕著である。従って、平均は垂直スケーリングの場合にはほとんど変わらず、従って、これはより小さいＢＥＲをもたらす。
【００８４】
スケーリングのように、大きな回転は同様に高いＢＥＲをもたらしうる。
【００８５】
静止しているか、又は多大な暗領域を有するクリップは、その高速且つ明るい対照部分に比べてより低いＢＥＲをもたらす傾向がある。
【００８６】
ある場合に、変形が多大なスケーリング又は回転と同程度に激しい場合は、唯１つの正確な一致さえ見つけることは不可能である。しかし、回転の場合は、近しい一致を見つけることは可能である。また、極めて低いビットレートへの圧縮の場合に、近しい一致の数は大幅に高まる。近しい一致を見つけるために弱いビットを切り替えることは、様々な変形に対するアルゴリズムのロバスト性を高めるのに有用である。
【００８７】
このように、変形された差動ブロック平均輝度アルゴリズムを用いる上記のフィンガープリント生成方法は、先行技術に対してずっと改善されたフレームレートロバスト性を提供するが、試験はアルゴリズムが多大なスケーリング及び回転に対して弱いことを示している。従って、更なる変形がアルゴリズムに対してなされる必要があり、これについて以下に記載する。かかる変形は、アルゴリズムを、特にスケーリング及び回転に対して、よりロバストなものとすることを目的とする。
【００８８】
第１の更なる変形について中心指向性差動ブロック輝度アルゴリズム（Centrally-Oriented  Differential  Block  Luminance  Algorithm）を例に記載する。このアルゴリズムは、フレームのより代表的な特徴を考慮する点で前出のアルゴリズムと相違する。そのために、当該アルゴリズムは、ビデオフレームの中心位置からフィンガープリントを取り出す。この変形されたアルゴリズムの開発は以下の認識に基づく：
ａ）フレームの黒色（black）部分はフィンガープリントにほとんど寄与しない情報であることが前出のアルゴリズムの使用から知られる。なお、ビデオフォーマットの多くは“レターボックス型”である。レターボックスは、元のアスペクト比を保ちながらビデオフォーマットにワイドスクリーンフィルムを写す常套手段である。ビデオ表示は、ほとんどの場合、元のフィルムよりも正方形に近いアスペクト比であるから、得られるマスターは、ピクチャ領域の上及び下にマスクオフ領域（masked-off  areas）を含まなければならない（これらは、しばしば、レターボックス投入口のように、“ブラックバー（black  bar）”と呼ばれる。）。フィンガープリントの信頼性は、これらの領域のフィンガープリントをとらないことによって高められ得る。
【００８９】
ｂ）一般に、ビデオフレームの中の動作のほとんどは指向性がある（oriented-oriented）。このことは、カメラマンが撮影する場面の中心に自身のカメラを向けるという事実から理解され得る。
【００９０】
ｃ）時々、映画は、フレームの夫々の下部に字幕を含む。これらの字幕は、概して、多数のフレームにわたって不変であり、定性的に如何なる情報もフィンガープリントに生じさせない。
【００９１】
ｄ）映画は、また、映画の全長さで不変のままであるロゴを上部に含みうる。これらのロゴは、また、同じプロダクションバナーの下の様々な映画に存在しうる。
【００９２】
これらの要因を考慮すると、中心指向性差動ブロック平均輝度アルゴリズムは、差動ブロック輝度アルゴリズムに極めて類似する。しかし、中心指向性アルゴリズムは、ソースフレームをブロックに分割する点で相違する。フレーム全体をブロックに分割することに代えて、これらのブロック又は領域２１は、図９に示されるように定められる。このように、フレーム２０の中央部分２２のみがブロックに分割されている。フレームの外側にある部分２３は使用されていない。これは、信頼性を改善するのに有用である。このようにフレームをブロックに分割すると、アルゴリズムの残りは、先に記載されたアルゴリズムと全く同じようにサブフィンガープリントのシーケンスを計算する。このように、ブロック／領域の夫々での輝度値の平均が計算され、フレームごとの３６個の平均値が得られる（３６は単なる例示であって、様々な数のブロックが同じく使用され得る。）。同様に、平均値は次のフレームから得られる。フレームレートロバスト性は、望ましい所定のフレームレートでシーケンスを形成するよう補間平均フレームを構成／生成することによって、この段階で組み入れられ得る（更に、実際には、ＣＯＤＢＬＡに関するその後の結果は、フレームレートロバスト性機構を含むアルゴリズムに基づく。）。
【００９３】
試験は、（同じく、フレームレートロバスト性を組み入れる）前出の全フレーム（非中心指向性）差動ブロック輝度アルゴリズム（ＤＢＬＡ）に対する中心指向差動ブロック輝度アルゴリズム（ＣＯＤＢＬＡ）の性能を解析するために実行されている。ＣＯＤＢＬＡの性能は、ある場合、例えば、クロッピング又はシフトを含む変形の場合に、結果として得られるフィンガープリントのロバスト性に関して、より良いことが分かっている。この結果は、ビデオフレームの上部分は一般にほとんど動作を有さず、従って、それらはほとんど情報を提供しないので、理解され得る。また、ＣＯＤＢＬＡは、レターボックス・フォーマットにある映像のフィンガープリンティングに特に適する。
【００９４】
（フレームの中央部分に集中する）ＣＯＤＢＬＡの原理を基礎とすると、フィンガープリント抽出アルゴリズムは、スケーリング及び回転変形に対するロバスト性を改善するために更に変形される。これは、以下のように、差動パイ状ブロック輝度アルゴリズム（ＤＰＢＬＡ（Differential  Pie-Block  Luminance  Algorithm））を提供する。
【００９５】
差動パイ状ブロック輝度アルゴリズムは、それがビデオフレームのジオメトリ（geometry）を考慮する点で前出のアルゴリズムと相違する。当該アルゴリズムは、スケーリング及びシフトに対してより耐久性を備えたセクタ状のブロックでフレームから特徴を取り出す。ＣＯＤＢＬＡでは、輝度の平均は長方形ブロックから取り出された。これらの平均は、フレームのその部分を表しており、時空間フィルタリング及び閾値化の後の代表的なビットを提供する。かかるビットのシーケンスはフレームに相当する。しかし、長方形ブロックの使用はスケーリングに対して弱い。従って、ビデオフレームがスケーリングを受ける場合に、ブロックが対象とするフレームの部分もスケーリングを受け、一意的には元の部分に相当しない。従って、ＤＰＢＬＡでは、平均（すなわち、平均輝度値又はデータ。）は、円のセクタ状であって且つ水平スケーリングに耐性を備えたフレームの部分から取り出される。言い換えると、ＤＰＢＬＡでは、フレームをブロックに分割するステップは、図１０に示されるようにフレームを分割する。先と同じく、フレームの中央部分２２のみがブロック２１に分割されている（故に、この特定のＤＰＢＬＡも中心指向性を有する。）。外側の周辺部分２３は、中心の円部分２９と同様に除かれている。各ブロック２１は、概して、半径の各対の間にあって扇形である。
【００９６】
ブロック分割ステップでのこのような相違は別として、ＤＰＢＬＡは、ＤＢＬＡ及びＣＯＤＢＬＡと同じように、ブロックで画素の輝度からサブフィンガープリントを生成する働きをする。ＤＰＢＬＡのこのような具体例で、ビデオフレーム２０は、以下で説明される時計回りの空間微分によって３２個の値を取り出すために、３３個の“ブロック”２１に分割される。この場合に、ブロックは、円のセクタと同様の形状をしている。半径方向でのセクタ面積の一様な増大は、セクタをスケーリングに対してより耐性のあるものとする。フレームの外側にある部分２３は使用されないことが知られる。また、フレームの中心部分２９は、平均を計算するためには使用されない。この部分は、スケーリング、シフト及び小さい量の回転に対してさえ極めて弱い。これは、信頼性を改善するのに有用である。数字の夫々は、入力ビデオフレームにおける対応する領域を表す。これらの領域の夫々での輝度値の平均が計算される。この処理は３３個の平均値をもたらす。
【００９７】
フレームレートロバスト性は、補間された平均フレームを得るために、この段階で適用され得る。この手順については、先に詳細に記載しており、ここでは繰り返さない。前の２つのアルゴリズムとは異なり、この場合に、軽微な相違は、フレームがＦ（ｒ，ｃ，ｐ）ではなくＦ（ｎ，ｐ）と表される点である。従って、平均フレームは、同じように補間される。ステップ１で計算される平均輝度値は、フレームにおいて３３個の“画素領域”として視覚化され得る。言い換えると、これらはフレームの異なる領域のエネルギを表す。カーネル［−１  １］を有する（すなわち、同じ行の隣り合うブロックの間の差をとる）空間フィルタ、及びカーネル［−１  １］を有する時間フィルタは、説明されたように、低分解能のグレースケール画像のこのシーケンスで適用される。
【００９８】
従って、現在のフレーム上の領域１３及び１４から得られる平均値であるＭ１３及びＭ１４と、次のフレームにおける対応する領域から得られる平均値であるＭ｀１３及びＭ｀１４とを考えると、値（サブフィンガープリントと呼ばれる。）は
【数４】
2009542081.tif 000006
のように計算される。一般的に、
【数５】
2009542081.tif 000007
であり、ここで、ｎ＝１〜３２である。
【００９９】
４．  ＳｆｔＦＰｎのサイン（sign）値は、ビットの値を決定する。より具体的には、ｎ＝１．．３２に関して、
【数６】
2009542081.tif 000008
である。
【０１００】
試験は、中心指向差動ブロック輝度アルゴリズム（ＣＯＤＢＬＡ）に対する、回転補償を伴わない差動パイ状ブロック輝度アルゴリズム（ＤＰＢＬＡ１）の性能を解析するために実行されている。両方向での等しいスケーリング及び水平スケーリングに関して、パイアルゴリズムはより良く実行する。しかし、それは、回転、垂直スケーリング及び上方シフトに対して弱い。多大な回転に対する脆弱性は、回転がセクタを空間領域で変化させ、従って、サブフィンガープリントビットの夫々が影響を受けるので、理解され得る。
【０１０１】
ＤＰＢＬＡを回転に対して回復力を有するものとするために、更なる変形が行われ得る。すなわち、補正係数が当該アルゴリズムで使用される。この場合に、特定の領域の平均は、また、隣接する領域の平均の空間和を有する。これは、クラス間ＢＥＲ分布の標準偏差を少しずつ大きくしながら回転に対するロバスト性を高めるのに有用である。当該アルゴリズムは、また、垂直スケーリングに対する改善されたロバスト性を提供する。従って、回転補償を伴うパイ状ブロックアルゴリズムの変形は、元の信号及び変形された信号のフィンガープリント間の近しい一致を見つける際に有意な改善を提供する。
【０１０２】
解析から得られる幾つかの結論は以下の通りである。回転補償を伴うパイ状差動ブロック輝度アルゴリズムは、ほとんどの場合に、中心指向差動ブロック輝度アルゴリズムよりも適切に実行する。クラス間及びクラス内ＢＥＲ分布は、それが中心指向差動ブロック輝度アルゴリズムよりも良い分類ツールとして働くことを示す。（テレビジョンにおける放送監視、選択的記録及びコマーシャルのフィルタリングのように）映像が変更される可能性がほとんどない用途に関し、このアルゴリズムは、先に論じられたものよりも一層良く実行することができる。しかし、それは回転に対してはより弱い。これは、小さい量の回転さえも有意にフィンガープリントを変更するためである。かかる変更は、圧縮及び輝度レベルの変更等のような他のどこにでもある変形のために追い打ちをかけられることがある。
【０１０３】
ここで、本発明の実施例で使用される他のアルゴリズムについて記載する。それは、差動サイズ可変ブロック輝度アルゴリズム（ＤＶＳＢＬＡ（Differential  Variable  Size  Block  Luminance  Algorithm））と呼ばれる。背景として、中心指向差動ブロック輝度アルゴリズムは多大な回転及びスケーリングに対して弱いことが思い出される。回転補償を伴うパイ状差動ブロック輝度アルゴリズムは、スケーリングに対しては極めてロバストであるが、回転に対しては弱いフィンガープリントをもたらす。ＤＶＳＢＬＡに関する当該記載において、どのように中心指向差動ブロック輝度アルゴリズムの性能が、可変なサイズの輝度ブロックを用いることによって、スケーリング及びシフトのような変形に対して改善され得るかを記載する。
【０１０４】
上述された基本のＣＯＤＢＬＡでは、輝度平均は長方形ブロックから取り出された。これらの平均は、フレームのその部分を表しており、時空間フィルタリング及び閾値化の後の代表的なビットを提供する。なお、幾何学変形の間、最も影響を受ける領域は、処理されるビデオフレームの外側にある領域である。これらの領域は、ほとんどの場合、弱いビットをもたらす。従って、これらの領域がより大きくされる場合は、これらの領域から弱いビットを得る確率は実質的に下がる。
【０１０５】
ＤＶＳＢＬＡの抽出アルゴリズムは、ＣＯＤＢＬＡのブロック輝度アルゴリズムと類似する。しかし、ＤＶＳＢＬＡでは、領域（ブロック２１）は、図１１に示されるように定められる。この具体例における様々なブロックのサイズは、以下の表１及び２で与えられており、フレーム幅のパーセンテージに関して表されている。“残り”は、両側で除外される領域に相当する。
【０１０６】
【表１】
2009542081.tif 000009
【０１０７】
【表２】
2009542081.tif 000010
ブロックは、中心指向差動ブロック輝度アルゴリズムで使用されるものと同様に長方形である。しかし、この場合に、それらは可変なサイズを有する。そのサイズは、ビデオフレームの中心へ向かって常に減少し続ける。フレームの中心からの長方形の面積の幾何学的な増大は、クロッピング、スケーリング及び回転のような幾何学変形の間に最も影響を受ける領域である外側領域に、より大きな補償範囲を与えるのに有用である。シフトの場合には、全ての領域が等しく影響を受ける。フレームの外側にある部分は使用されないことが知られる。これは、より少ない小さいビットを得ることによって信頼性を高めるのに有用である。
【０１０８】
フレームレートロバスト性は、補間された平均フレームを得るために、この段階で適用され得る。この手順については、先に詳細に記載されている。次いで、サブフィンガープリントは、ＤＢＬＡ及びＣＯＤＢＬＡに関連して上述されたのと同じように、（所定のレートで、補間により構成される）平均フレームのシーケンスから得られる。
【０１０９】
ＤＶＳＢＬＡの性能の解析は、幅広い様々な変形についてＢＥＲを見て、ＢＥＲが固定ブロックサイズのバージョンに比べて著しく減少していることを示している。このように、アルゴリズムは、全ての種類の変形に対してよりロバストとなった。ＤＶＳＢＬＡは、それらにより大きい面積を与えることによって、（より広い部分から得られる）より弱いビットに対する更なる耐性を提供する。
【０１１０】
実際には、試験は、ある用途に関し、サイズ可変なブロックを伴う差動ブロック輝度アルゴリズムが、（他のアルゴリズムに比べて同様に信頼性を有し且つよりロバストである）これまで論じられた他の全てのアルゴリズムに比べてより良く実行することを示している。（映画のカムプリントのｐ２ｐファイルシェアリングのように）映像が変更される可能性が高い用途に関し、このアルゴリズムは、先に論じられたものよりもより良く実行することができる。
【０１１１】
上述された４つの主なアルゴリズムを試験したところ、それらの相対性能を以下のようにまとめることができる：
ビデオフィンガープリンティングシステムのロバスト性は、ビデオシーケンスの変形バージョンを正確に識別する際のアルゴリズムの信頼性に関する。ロバスト性対種々の変形に関する様々なアルゴリズムの性能は、以下の表３に挙げられている。
【０１１２】
【表３】
2009542081.tif 000011
差動サイズ可変ブロック輝度アルゴリズム（ＤＶＳＢＬＡ）はロバスト性に関して特に適切に実行することが分かる。従って、ＤＶＳＢＬＡを用いるフィンガープリンティングシステムは、種々の変形に対して極めてロバストである。しかし、明らかなように、表中の４つのアルゴリズム（それらは全て、所定のレートにあるサブフィンガープリントを取り出すことによってフレームレートロバスト性を組み入れる。）の夫々は、様々な種類の変形のうちの少なくとも幾つかに関して、先行技術に対して改善されたロバスト性を提供する。
【０１１３】
ビデオフィンガープリンティングシステムの信頼性は、システムの他人受入率に関連する。様々なアルゴリズムの他人受入率を見つけるために、それらのクラス間ＢＥＲ分布が検討される。その分布は正規分布に密接に従うことが知られる。従って、分布が正規であるとすると、外れ値のパーセンテージ及び標準偏差が計算される。このようにして計算される標準偏差は、システムの理論上の他人受入率の考えを与える。それらのパラメータは、４つのアルゴリズムに関し、以下、表４で示されている。
【０１１４】
【表４】
2009542081.tif 000012
回転補償を伴う差動パイ状ブロック輝度アルゴリズム（ＤＰＢＬＡ２）は極めて良好な特性を有することが分かる。しかし、差動サイズ可変ブロック輝度アルゴリズム（ＤＶＳＢＬＡ）は近く、その高いロバスト性により、ある用途ではＤＰＢＬＡ２より性能が優れている。従って、ＤＶＳＢＬＡに基づくフィンガープリントは、他人受入率が極めて低い。
【０１１５】
全てのアルゴリズムに関して、フィンガープリントサイズは８８０ｂｐｓで一定である。従って、５０００時間の映像に対応するフィンガープリントを記憶するためには、３９６０ＭＢの記憶容量が必要とされる。しかし、種々の用途に関し、異なる量の映像に対応するフィンガープリントがデータベースに格納される必要がある。以下の表５は、上述された様々な用途に関する典型的な記憶モデルを表す。
【０１１６】
【表５】
2009542081.tif 000013
実際には、これらの必要メモリは、上述される検索アルゴリズムによって極めてうまく扱われ得る。従って、本発明を具現するビデオフィンガープリンティングシステムの必要メモリは実際的である。
【０１１７】
精度に関して、本発明を具現するビデオフィンガープリンティングシステムは約５秒の存続期間のシーケンスから確実に映像を識別することができることが結果として示される。
【０１１８】
２４時間の映像を含むデータベースの検索速度は、１００ミリ秒程度であると推定されている。
【０１１９】
上記から、本発明を具現するあるビデオフィンガープリンティングシステムは、フィンガープリント抽出アルゴリズムモジュールと、フィンガープリントデータベースでこのようなフィンガープリント検索する検索モジュールとを有する。本発明のある実施例で、サブフィンガープリントは、（ビデオソースのフレームレートとは関わりなく）フレームごとに一定周波数で取り出される。これらのサブフィンガープリントは、ある実施例では、時間及び空間の両方の軸に沿ってエネルギ差から得られる。研究により、このようなサブフィンガープリントのシーケンスは一意にビデオシーケンスを識別できるほど十分な情報を含むことが明らかにされている。
【０１２０】
ある実施例で、検索モジュールは、例えば、上記特許文献１に記載される整合方法に基づいてビデオ・フィンガープリントを“整合”させる検索方法を使用する。この検索方法は、データベース内の莫大なフィンガープリントに起因してそのようにすることによって実時間で結果を生成することが不可能であるため、単純なブルートフォース検索アプローチを使用しない。また、フィンガープリントの正確なビットコピーは、入力ビデオクエリが（意図的に又は無意図的に）幾つかの画像又はビデオ変形を受けている場合には、検索モジュールへ入力として与えられ得ない。従って、検索モジュールは、（フィンガープリント抽出の間に計算される）フィンガープリントにおけるビットの強さを用いて、それらの夫々の信頼性を推定し、それらを公正な一致を得るよう然るべく切り替える。
【０１２１】
より良い性能を有するアルゴリズムが大規模に設計され、研究され、試験されてきた。本発明を具現するビデオフィンガープリンティングシステムは試験されて、極めて信頼性が高いことが分かっており、ある場合にはクリップを正確に識別するのにたった５秒の映像しか必要としない。５０００時間の映像に対応する、フィンガープリントのための必要メモリは、ある例では、およそ４ＧＢである。あるシステムにおける検索モジュールは、実時間（ミリ秒のオーダー）で結果を生成するに足りるほど適切に動作することが分かっている。本発明を具現するフィンガープリンティングシステムは、また、極めて拡張性があることが分かっており、ウィンドウズ（登録商標）、リナックス（登録商標）、及びプラットフォームのような他のユニックスで配置可能である。本発明を具現するあるビデオフィンガープリンティングシステムは、また、それらが使用するアルゴリズムで内在する並列処理を利用するためにＭＭＸインストラクションを使用することによって、性能に関して最適化される。
【０１２２】
ある実施例は、各フレームの中央部分のみからビデオ・フィンガープリントを得ることによって、様々な変形に対してよりロバストであるフィンガープリントをもたらすという利点を提供する。
【０１２３】
同様に、ある実施例は、長方形でないブロックに分割されたフレームからビデオ・フィンガープリントを得ることによって、様々な変形に対してよりロバストであるフィンガープリントをもたらすという利点を提供する。
【０１２４】
また、ある実施例は、異なったサイズを有するブロックに分割されたフレームからビデオ・フィンガープリントを得ることによって、様々な変形に対してよりロバストであるフィンガープリントをもたらすという利点を提供する。
【０１２５】
要約すると、本発明は、ビデオ信号（２）のよりロバストなフィンガープリント（１）を生成する新規の技術を提供する。本発明のある実施例は、各フレーム（２０）の中央部分（２２）にあるブロック（２１）からのみビデオ・フィンガープリントを得て、残りの外側部分（２３）を無視する。得られるフィンガープリント（１）は、クロッピング又はシフトを含む変形に対してよりロバストである。他の実施例は、各フレーム（又はその中央部分）を、例えば、パイ状又は環状ブロックのような非長方形ブロックに分割し、かかるブロックからフィンガープリントを生成する。ブロックの形状は、特定の変形に対するロバスト性を提供するよう選択され得る。例えば、パイ状ブロックはスケーリングに対するロバスト性を提供し、環状ブロックは回転に対するロバスト性を提供する。他の実施例は、異なるサイズのブロックを使用する。これより、フレームの異なる部分は、フィンガープリントで異なる重み付けを与えられ得る。
【０１２６】
特許請求の範囲を含む本明細書の全体を通して、語“有する（comprising）（comprises）”は、それらが他の要素又はステップを除外しないという意味で解釈されるべきであることは明らかである。また、“１つの（a，an）”は複数個を除外せず、単一の処理装置又は他のユニットは明細書又は特許請求の範囲で挙げられている幾つかのユニット、機能ブロック、又は段階の機能を満たすことができることは明らかである。また、特許請求の範囲の参照番号は、特許請求の範囲の適用範囲を限定するよう解釈されるべきでないは明らかである。
【図面の簡単な説明】
【０１２７】
【図１】本発明を具現するフィンガープリント生成方法を表す図である。
【図２】本発明を具現する他のフィンガープリント生成方法におけるフレームの中央部分の選択を表す図である。
【図３】本発明を具現する更なる他のフィンガープリント生成方法におけるブロックへのフレームの中央部分の分割を表す図である。
【図４】本発明を具現する更なる他のフィンガープリント生成方法におけるブロックへのフレームの分割を表す図である。
【図５】ビデオ信号の内容を示すサブフィンガープリントを生成する、本発明を具現する更なる他のフィンガープリント生成方法の部分を表す図である。
【図６】本発明を具現するビデオ・フィンガープリンティング・システムを表す図である。
【図７】ブロックに分割されたビデオ信号のフレームを表す図である。
【図８】本発明を具現する方法で生成される、特徴を取り出されたフレームのシーケンスの一部を表す図である。
【図９】本発明のある実施例で使用される、ブロックへのビデオ信号のフレームの分割を表す図である。
【図１０】本発明のある実施例で使用される、ブロックへのビデオ信号のフレームの分割を表す図である。
【図１１】本発明のある実施例で使用される、ブロックへのビデオ信号のフレームの分割を表す図である。
【図１】
2009542081.tif 000014
【図２】
2009542081.tif 000015
【図３】
2009542081.tif 000016
【図４】
2009542081.tif 000017
【図５】
2009542081.tif 000018
【図６】
2009542081.tif 000019
【図７】
2009542081.tif 000020
【図８】
2009542081.tif 000021
【図９】
2009542081.tif 000022
【図１０】
2009542081.tif 000023
【図１１】
2009542081.tif 000024
【手続補正書】
【提出日】平成20年12月24日(2008.12.24)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データフレームのシーケンスを有するビデオ信号の内容を示すフィンガープリントを生成する方法であって：
各フレームの中央部分のみを複数のブロックに分割し、前記中央部分以外の各フレームの残りの部分をブロックに分割されないままとするステップ；
各ブロックでデータの特徴を取り出すステップ；及び
前記取り出された特徴からフィンガープリントを計算するステップ；
を有し、
前記中央部分は前記フレームの中心部分を囲み、
当該方法は、前記中心部分をブロックに分割されないままとするステップを更に有する、方法。
【請求項２】
前記残りの部分は前記中央部分を囲む、請求項１記載の方法。
【請求項３】
前記複数のブロックは、複数の異なったサイズを有するブロックを有する、請求項１記載の方法。
【請求項４】
前記複数のブロックは、複数の異なったサイズを有する複数の長方形ブロックを有する、請求項１記載の方法。
【請求項５】
前記長方形ブロックのサイズは、前記フレームの中心から外側に向かう少なくとも１つの方向で増大する、請求項４記載の方法。
【請求項６】
前記複数のブロックは、複数の長方形でないブロックを有する、請求項１記載の方法。
【請求項７】
前記複数の長方形でないブロックは複数の略扇形ブロックを有し、
夫々の前記略扇形ブロックは、前記フレームの中心から夫々の対の半径によって境界を定められる、請求項６記載の方法。
【請求項８】
前記複数の長方形でないブロックは複数の略環状同心ブロックを有する、請求項６記載の方法。
【請求項９】
データフレームのシーケンスを有するビデオ信号の内容を示すフィンガープリントを生成する方法であって：
各フレームを複数の異なったサイズを有する複数の長方形ブロックに分割するステップ；
各ブロックでデータの特徴を取り出すステップ；及び
前記取り出された特徴からフィンガープリントを計算するステップ；
を有し、
前記長方形ブロックのサイズは、前記フレームの中心から外側に向かう少なくとも１つの方向で増大する、方法。
【請求項１０】
各フレームの残りの部分をブロックに分割されないままとするステップを更に有し、
前記残りの部分は前記フレームの中央部分の外側にある、請求項９記載の方法。
【請求項１１】
データフレームのシーケンスを有するビデオ信号の内容を示すフィンガープリントを生成する方法であって：
各フレームを複数の長方形でないブロックに分割するステップ；
各ブロックでデータの特徴を取り出すステップ；及び
前記取り出された特徴からフィンガープリントを計算するステップ；
を有する方法。
【請求項１２】
前記複数の長方形でないブロックは複数の略扇形ブロックを有し、
夫々の前記略扇形ブロックは、前記フレームの中心から夫々の対の半径によって境界を定められる、請求項１１記載の方法。
【請求項１３】
前記複数の長方形でないブロックは複数の略環状同心ブロックを有する、請求項１１記載の方法。
【請求項１４】
各フレームの中心部分をブロックに分割されないままとするステップを更に有する、請求項１１記載の方法。
【請求項１５】
データフレームのシーケンスを有するビデオ信号の内容を示すフィンガープリントを生成する方法であって、各データフレームは複数のブロックを有し、各ブロックはビデオ画像の夫々の領域に対応する方法において：
選択されたサブセットが前記ビデオ画像の中央部分に対応するよう、フレームごとに前記複数のブロックのサブセットのみを選択するステップ；
前記選択されたサブセットの各ブロックでデータの特徴を取り出すステップ；及び
前記取り出された特徴からフィンガープリントを計算するステップ；
を有し、
前記中央部分は前記ビデオ画像の中心部分を囲み、
前記選択されたサブセットは前記中心部分に対応するブロックを含まない、方法。
【請求項１６】
前記中央部分は外側部分によって囲まれる、請求項１６記載の方法。
【請求項１７】
データフレームのシーケンスを有するビデオ信号を受信し、請求項１記載の方法によって前記ビデオ信号の内容を示すフィンガープリントを生成するよう配置される信号処理装置。
【請求項１８】
請求項１記載の方法の実行を可能にするコンピュータプログラム。
【請求項１９】
請求項１８記載のコンピュータプログラムを記憶する記録媒体。
【請求項２０】
放送監視方法；信号フィルタリング方法；自動索引作成方法；選択的記録方法；不正変更検出方法；及び送信エラー検出方法を含むリストから選択される信号処理用途における請求項１記載のフィンガープリント生成方法の使用。
【国際調査報告】
2009542081.tif 000025
2009542081.tif 000026
2009542081.tif 000027