(57)【要約】  一部の実施形態は、高速のロバストな特徴量（ＳＵＲＦ）軌跡構築と、ＬＳＨ（local sensitive hash）索引付けと、時空間スケール登録とに基づくビデオコピー検知方法を含む。まず、関心点の軌跡をＳＵＲＦにより抽出する。次に、効率的な投票に基づく時空間スケール登録方法を利用して、最適な変換パラメータ（シフトおよびスケール）を推定して、時空間およびスケール方向両方におけるビデオセグメントの伝播による最終的なビデオコピー検知結果を得る。検知速度を高めるために、ＬＳＨ索引を利用して候補の軌跡を高速にクエリするために軌跡を索引付けする。【選択図】図３
2012531130.tif 000002
【特許請求の範囲】
【請求項１】
参照ビデオからＳＵＲＦ（speeded up robust features：高速のロバストな特徴量）を抽出する段階と、
前記参照ビデオのＳＵＲＦ点を格納する段階と、
前記ＳＵＲＦ点に基づいて、前記参照ビデオの時空間特徴量として軌跡を決定する段階と、
前記軌跡を格納する段階と、
前記軌跡の索引を作成する段階と
を備えるコンピュータによる実装が可能な方法。
【請求項２】
抽出された前記ＳＵＲＦは、前記参照ビデオの局所特徴量を含む請求項１に記載の方法。
【請求項３】
前記索引を作成する段階は、
ＬＳＨ（Local Sensitive Hashing：場所に感度を有するハッシング）を利用して、ＳＵＲＦ特徴量の平均値により軌跡の索引を決定する段階を含む請求項１に記載の方法。
【請求項４】
映像クエリのＳＵＲＦを決定する段階と、
映像クエリフレームに関連するオフセットを決定する段階と、
決定された前記オフセットに一部基づき、前記映像クエリフレームがビデオコピークリップを含むかを判断する段階と
をさらに備える請求項１に記載の方法。
【請求項５】
前記オフセットを決定する段階は、
時空間オフセット空間を、可能性のある時間、ｘ、またはｙのオフセットの時空間オフセットパラメータに対応する各立方体に適合的に分割する段階を含む請求項４に記載の方法。
【請求項６】
前記オフセットを決定する段階は、
前記映像クエリフレームに関連する参照ビデオフレームの軌跡を決定する段階と、
時空間オフセットの各スケールに対して、前記映像クエリフレームと前記参照ビデオフレームとの間で類似している局所特徴量の数を累積する段階と
をさらに含む請求項５に記載の方法。
【請求項７】
前記映像クエリフレームがビデオコピークリップを含むかを判断する段階は、
前記映像クエリから抽出した前記ＳＵＲＦに類似している局所特徴量を有する参照ビデオフレームを特定する段階を含み、
特定された前記参照ビデオフレームの各ビデオフレームの局所特徴量は、前記映像クエリの前記ＳＵＲＦからの類似した時空間オフセットを有する請求項４に記載の方法。
【請求項８】
特徴量データベースと、
軌跡特徴量データベースと、
参照ビデオからＳＵＲＦを抽出し、前記特徴量を前記特徴量データベースに格納し、ＳＵＲＦ点を追跡して、前記参照ビデオの時空間特徴量の軌跡を形成し、前記軌跡を前記軌跡特徴量データベースに格納し、前記軌跡特徴量データベース用の索引を作成する軌跡構築論理と
を備える装置。
【請求項９】
前記軌跡構築論理は、
映像クエリの特徴量のクエリ要求を受信し、
前記映像クエリの前記特徴量に関連する軌跡を提供する
請求項８に記載の装置。
【請求項１０】
抽出された前記ＳＵＲＦは、前記参照ビデオの局所特徴量を含む請求項８に記載の装置。
【請求項１１】
前記軌跡特徴量データベース用の索引を作成するために、前記軌跡構築論理は、ＬＳＨを利用して、ＳＵＲＦ特徴量の平均値により軌跡を索引付けする請求項８に記載の装置。
【請求項１２】
映像クエリからＳＵＲＦを抽出し、前記軌跡構築論理から前記映像クエリの前記特徴量に関連する軌跡を受信し、前記映像クエリから抽出した前記ＳＵＲＦに類似している局所特徴量を有する参照ビデオフレームを前記特徴量データベースから特定するコピー検知モジュールをさらに備え、
特定された前記参照ビデオフレームの各ビデオフレームの局所特徴量は、前記映像クエリからの前記ＳＵＲＦからの類似した時空間オフセットを有する請求項８に記載の装置。
【請求項１３】
参照ビデオフレームを特定するために、前記コピー検知モジュールは、
映像クエリフレームに関連するオフセットを決定し、
決定された前記オフセットに一部基づき、前記映像クエリフレームがビデオコピークリップを含むかを判断する請求項１２に記載の装置。
【請求項１４】
オフセットを決定するために、前記コピー検知モジュールは、時空間オフセット空間を、可能性のある時間、ｘ、またはｙのオフセットの時空間オフセットパラメータに対応する各立方体に適合的に分割する請求項１３に記載の装置。
【請求項１５】
オフセットを決定するために、前記コピー検知モジュールはさらに、
前記映像クエリフレームに関する参照ビデオフレームの軌跡を決定し、
時空間オフセットの各スケールに対して、前記映像クエリフレームと前記参照ビデオフレームとの間で類似している局所特徴量の数を累積する請求項１４に記載の装置。
【請求項１６】
前記映像クエリフレームがビデオクリップを含むかを判断するために、前記コピー検知モジュールは、前記映像クエリから抽出した前記ＳＵＲＦに類似している局所特徴量を有する参照ビデオフレームを特定し、
特定された前記参照ビデオフレームの各ビデオフレームの局所特徴量は、前記映像クエリの前記ＳＵＲＦからの類似した時空間オフセットを有する請求項１３に記載の装置。
【請求項１７】
表示デバイスと、
特徴量データベース、軌跡特徴量データベース、軌跡構築論理、及びコピー検知論理を有し、前記表示デバイスに通信可能に連結されたコンピュータシステムと
を備え、
前記軌跡構築論理は、参照ビデオからＳＵＲＦを抽出し、前記ＳＵＲＦを前記特徴量データベースに格納し、前記ＳＵＲＦ点に基づいて前記参照ビデオの時空間特徴量の軌跡を決定し、前記軌跡を前記軌跡特徴量データベースに格納し、
前記コピー検知論理は、映像クエリのフレームがコピーかを判断し、前記映像クエリのフレームに類似している前記参照ビデオのビデオフレームを提供する
システム。
【請求項１８】
抽出された前記ＳＵＲＦは、前記参照ビデオの局所特徴量を含む請求項１７に記載のシステム。
【請求項１９】
前記軌跡構築論理はさらに、ＬＳＨを利用して、抽出された前記ＳＵＲＦの平均値により軌跡を索引付けすることで、抽出された前記ＳＵＲＦに関連する軌跡用の索引を作成する請求項１７に記載のシステム。
【請求項２０】
映像クエリのフレームがコピーかを判断するために、前記コピー検知論理は、前記映像クエリから抽出された前記ＳＵＲＦに類似している局所特徴量を有する参照ビデオフレームを特定し、
特定された前記参照ビデオフレームの各ビデオフレームの局所特徴量は、前記映像クエリの前記ＳＵＲＦからの類似した時空間オフセットを有する請求項１７に記載のシステム。
【請求項２１】
参照画像からＳＵＲＦを抽出する段階と、
前記ＳＵＲＦ点に基づいて、前記参照画像の局所空間特徴の軌跡を決定する段階と、
前記軌跡を格納する段階と、
格納された前記軌跡の索引を作成する段階と
を備える方法。
【請求項２２】
抽出された前記ＳＵＲＦは、前記参照画像の局所特徴量を含む請求項２１に記載の方法。
【請求項２３】
索引を作成する段階は、ＬＳＨを利用して、ＳＵＲＦ特徴量の平均値により軌跡の索引付けを行う請求項２１に記載の方法。
【請求項２４】
クエリ画像がコピーかを判断する段階は、前記クエリ画像から抽出した前記ＳＵＲＦに類似している局所特徴量を有する参照画像を特定する段階を含み、特定された各参照画像の局所特徴量は、前記クエリ画像の前記ＳＵＲＦからの類似した空間オフセットを有する請求項２１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
ここに開示する主題は概して、ビデオまたは画像コピーを検知する技術に係る。
【背景技術】
【０００２】
インターネットおよび個人利用のビデオが益々利用しやすくなっている昨今では、著作権制御、ビジネスインテリジェンス、および広告監視等の研究分野としてビデオコピー検知が活発になっている。ビデオコピーは、通常は、シフト、クロップ、照明（lighting）、コントラスト、カムコード（例えば、幅／高さの比を１６：９と４：３との間で変更する等）および／または再符号化する等によって追加、削除、および修正といった様々な変換技術を利用することで、別のビデオから得たセグメントのことである。図１は、ビデオコピーの幾つかの例を示している。具体的には、図１は、上の行に、左から右へと、それぞれ元のビデオ、ズームイン／ズームアウトされたバージョン、およびクロップされたビデオを示しており、下の行に、左から右へと、それぞれシフト、コントラスト、およびカムコードして再符号化処理を施したビデオを示している。再符号化には、異なるコーデックまたは圧縮品質を有するビデオの符号化が含まれる。これら変換は、ビデオの時空間スケールのアスペクトを変更するので、著作権制御およびビデオ／画像検索においてビデオコピー検知が非常に難しくなる。
【０００３】
既存のビデオコピー検知処理は、フレームベース法とクリップベース法とに大別される。フレームベースの方法は、キーとなるフレームセットが、ビデオコンテンツの要約版であるということを前提としている。Ｐ．Ｄｕｙｇｕｌｕ氏、Ｍ．Ｃｈｅｎ氏、および、Ａ．Ｈａｕｐｔｍａｎｎ氏による「２つの新規な商用検知方法の比較および組み合わせ：Comparison and Combination of Two Novel Commercial Detection Methods」、Ｐｒｏｃ．ＣＩＶＲ'０４（２００４年７月）に記載されている技術によると、視覚特徴量のセット（色、エッジ、およびＳＩＦＴ（スケール不変特徴量変換）特徴量）をこれらキーフレームから抽出している。ビデオコピークリップを検知するために、この技術では、これらキーフレームとのビデオセグメントの類似性を判断している。フレームベースの方法は、簡単であり効率的ではあるが、オブジェクトの時空間情報（例えば動きの軌跡）が失われることから、あまり正確ではないという欠点がある。加えて、２つのビデオセグメントをマッチングする統一キーフレーム選択スキームを考え付くのが難しい。
【０００４】
クリップベースの方法では、一連のフレームから時空間特徴量を特徴付けようとする試みが行われる。Ｊ．Ｙｕａｎ氏、Ｌ．Ｄｕａｎ氏、Ｑ．Ｔｉａｎ氏、およびＣ．Ｘｕ氏による「索引構造を利用する、高速およびロバスト、且つ短時間のビデオクリップ検索：Fast and Robust Short Video Clip Search Using an Index Structure」Ｐｒｏｃ．ＡＣＭ  ＭＩＲ'０４（２００４年）に記載されている技術は、元のパターンヒストグラムおよび累積色分布ヒストグラムを抽出して、ビデオの時空間パターンを特徴付ける方法である。この方法は、ビデオフレームの時間情報を探すが、グローバルカラーヒストグラムでは、例えばクロップ、シフト、およびカムコード処理等の局所変換されたビデオコピーを検知することができない。
【０００５】
Ｊ．Ｌａｗ−Ｔｏ氏、Ｏ．Ｂｕｉｓｓｏｎ氏、Ｖ．Ｇｏｕｅｔ−Ｂｒｕｎｅｔ氏、Ｎｏｚａｈａ  Ｂｏｕｊｅｍａａ氏による「ビデオコピー検知のための行動のラベルに基づくロバストな投票アルゴリズム：Robust Voting Algorithm Based on labels of Behavior for Video Copy Detection」、マルチメディア国際会議（２００６）に記載されている技術では、ビデオをビデオデータベース内の関心点の時空間軌跡との比較でテストするときに、非対称技術を利用して特徴点同士をマッチングさせる試みが行われる。この方法では、例えばシフト、照明、およびコントラストといった数多くのビデオコピー変換を検知することが可能となる。しかし、ハリス特徴点（Harris point feature）は、区別できず、大きさが不変でもなく、この技術が利用する時空間登録では、スケール関連の変換（例えばズームイン／ズームアウトおよびカムコード）を検知することができない。
【０００６】
本発明の実施形態は、限定を意図しない例を利用して説明されるが、図面において、同様の参照番号は同様の部材を示している。
【図面の簡単な説明】
【０００７】
【図１】ビデオコピーの幾つかの例を挙げている。
【図２】一実施形態におけるビデオコピー検知システムを示す。
【図３】一実施形態における、特徴点および軌跡のデータベースを作成するプロセスの一例を示す。
【図４】一実施形態におけるビデオコピーを判断するプロセスの一例を示す。
【図５】一実施形態における、一次元ビンの場合の最適オフセットを投票（voting）する一例を示す。
【図６】一実施形態における幾つかの映像クエリフレームから局所特徴量（local features）を検知する一例を示す。
【図７】システム性能を記述する作用特性曲線（ＲＯＣ：operation characteristic curves）の受信を示す。
【発明を実施するための形態】
【０００８】
明細書にわたり「一実施形態」あるいは「１つの実施形態」といった言い回しは、その実施形態との関連で記載されている特定の特徴量、構造、または特性が、本発明の少なくとも１つの実施形態に含まれていることを意味している。従って、「一実施形態」あるいは「１つの実施形態」といった言い回しがよく利用されているからといって、必ずしもそれらが同じ実施形態のことを言及している場合ばかりとは限らない。さらに、これら特定の特徴、構造、または特性は、１以上の実施形態では組み合わせることができる。
【０００９】
様々な実施形態では、ＳＵＲＦ（speeded up robust features：高速のロバストな特徴量法）による軌跡構築、ＬＳＨ（Local Sensitive Hashing：場所に感度を有するハッシング）による索引付け、および投票ベースの時空間スケール登録に基づくビデオコピー検知方法が提供されている。
【００１０】
ＳＵＲＦは、ビデオコピー検知における関心点の軌跡の特徴量を特徴付ける。様々な実施形態において、Ｌａｗ−Ｔｏ氏の文献に記載されているハリス特徴量を利用する方法よりもより良いパフォーマンスが発揮される。偽の正のフレームレートが１０％である場合、ハリス法に基づく方法では、真の正のフレームレートは６８％であるが、本発明の様々な実施形態では９０％の真の正のフレームレートを達成することができる。ＳＵＲＦ特徴法はハリス特徴点よりも識別力に優れており、Ｌａｗ−Ｔｏ氏の文献の結果に比べて、ズームイン／ズームアウトおよびカムコードといったスケール関連の変換におけるパフォーマンスが良好である。加えて、ＳＵＲＦ特徴量抽出における速度は、ＳＩＦＴの約６倍、且つ、ハリス特徴点方法とは同等である。
【００１１】
ＬＳＨ索引付け方法により、ビデオコピー検知における候補となる軌跡を高速にクエリすることができる。Ｌａｗ−Ｔｏ氏の文献では、ＬＳＨ索引付けではなくて確率類似検索が利用されている。
【００１２】
時空間スケール登録および伝播、並びにオフセットパラメータの統合により、最大累積登録スコアを有する、マッチングするビデオセグメントが検知される。Ｌａｗ−Ｔｏの文献に記載されている方法では、スケール変換の検知に弱い。離散オフセットパラメータ空間でこの投票ベースの登録を利用することにより、様々な実施形態で、時空間面およびスケール変換面の両方で（例えばクロップ、ズームイン／ズームアウト、スケーリングおよびカムコード処理等）検知を行うことができるようになる。
【００１３】
図２は、一実施形態におけるビデオコピー検知システムを示す。このビデオコピー検知システムは、オフライン軌跡構築モジュール２１０とオンラインコピー検知モジュール２５０とを含む。プロセッサおよびメモリを有し、有線および無線技術を利用してネットワークに通信可能に連結される任意のコンピュータシステムを、オフライン軌跡構築モジュール２１０およびオンラインコピー検知モジュール２５０が担う処理を行うように構成することができる。例えば、映像クエリは、ネットワークを介してコンピュータシステムへと通信されてよい。例えばコンピュータシステムは、ＩＥＥＥ８０２．０３、８０２．１１、または８０２．１６の一バージョンに準拠する技術を用いて、有線で、または１以上のアンテナを利用して、通信を行うことができる。コンピュータシステムは、表示デバイスを利用してビデオを表示してよい。
【００１４】
オフライン軌跡構築モジュール２１０は、ビデオデータベースの各フレームからＳＵＲＦ点を抽出して、ＳＵＲＦ点を特徴量データベース２１２に格納する。オフライン軌跡構築モジュール２１０は、関心点の軌跡を含む軌跡特徴量データベース２１４を構築する。オフライン軌跡構築モジュール２１０は、ＬＳＨを用いて、特徴量データベース２１２内の特徴点を、軌跡特徴量データベース２１４内の軌跡に対して索引付けする。
【００１５】
オンラインコピー検知モジュール２５０は、映像クエリのサンプリングフレームからＳＵＲＦ点を抽出する。オンラインコピー検知モジュール２５０は、抽出したＳＵＲＦ点で、特徴量データベース２１２をクエリして、同様の局所特徴量を有する、候補の軌跡を特定する。軌跡特徴量データベース２１４内の候補の軌跡のうち、同様の特徴点に対応するものが、ＬＳＨを利用して特定される。
【００１６】
映像クエリからの各特徴点について、オンラインコピー検知モジュール２５０は、投票ベースの時空間スケール登録法を利用して、映像クエリのＳＵＲＦ点と、軌跡特徴量データベース２１４内の候補の軌跡との間の、最適な時空間スケール変換パラメータ（つまりはオフセット）を推定する。オンラインコピー検知モジュール２５０は、時空間およびスケール方向の両面でマッチングしたビデオセグメント同士を伝播して、ビデオコピーを特定する。投票（voting）は、推定された関心点の時空間スケールの登録空間における累積である。時空間スケール登録空間は、ｘ、ｙ、ｔおよびスケールパラメータのシフトに対応して立方体に分割されている。ｘ、ｙ、ｔ、およびスケールパラメータが所与であれば、各立方体内で見つかる関心点の数が投票としてカウントされる。投票された関心点が最も多い立方体がコピーとみなされる。投票に基づく時空間スケール登録法の一例を図６に示す。
【００１７】
例えば、映像クエリＱにおいて、Ｍ＝１００個のＳＵＲＦ点を、各Ｐ＝２０枚のフレームから抽出する。映像クエリＱから選択されたフレームｋ上の各ＳＵＲＦ点ｍについて、ＬＳＨを利用して、Ｎ＝２０個の最近傍の軌跡を、軌跡特徴量データベース２１４における候補の軌跡として見つける。実際には、Ｍ、Ｐ、およびＮは、オンラインコピー検知における精度およびクエリ速度の間のバランスを考えて、調節することができる。各候補の軌跡ｎは、Ｒｍｎ＝「Ｉｄ、Ｔｒａｎ、Ｓｉｍｍｎ」として記述することができ、本式においてＩｄは、軌跡特徴量データベース２１４のビデオＩＤであり、Ｔｒａｎは、軌跡特徴量であり、Ｓｉｍｍｎは、（ｘｍ、ｙｍ）のＳＵＲＦ点と、候補の軌跡のＳｍｅａｎ特徴量との間の類似度を示す。
【００１８】
関連するビデオＩｄにより、候補の軌跡を、それぞれ異なるサブセットＲＩｄに分類する。軌跡特徴量データベース２１４の各ビデオＩＤおよび選択されたクエリフレームｋについて、高速で効率的な時空間スケール登録方法を利用して、最適な時空間スケール登録パラメータ：Ｏｆｓｅｔ（Ｉｄ、ｋ）を推定する。最適なオフセット（Ｉｄ、ｋ）を取得した後に、時空間方向およびスケール方向両方で登録される可能性のあるビデオセグメントについての最適な時空間スケールオフセットを伝播して、急峻なオフセットを取り除き、最終検知結果を取る。
【００１９】
ビデオコピー検知には数多くの変更が存在する。映像クエリＱを同じソースからデータベースのビデオＲとしてコピーする場合には、ＱおよびＲのＳＵＲＦ点の間に「一定数の時空間スケールオフセット」が存在する。従って様々な実施形態においてビデオコピー検知の目的は、Ｑとの間に略不変のオフセットを有する、データベース内のビデオセグメントＲを発見することである。
【００２０】
図３は、一実施形態における、特徴点および軌跡からなるデータベースを作成するプロセスの一例を示す。一部の実施形態では、オフライン軌跡構築モジュール２１０は、プロセス３００を実行してよい。ブロック３０２は、ビデオから、ＳＵＲＦ（高速のロバストな特徴量）を抽出することを含む。ＳＵＲＦの一例は、Ｈ．Ｂａｙ氏、Ｔ．Ｔｕｙｔｅｌａａｒｓ氏、Ｌ．Ｇｏｏｌ氏らの「ＳＵＲＦ：高速化されたロバストな特徴量（Speeded Up Robust Features）」ＥＣＣＶ、２００６年５月を参照のこと。様々な実施形態では、抽出する特徴量は、１フレームの局所特徴量である。
【００２１】
様々な実施形態では、各関心点において、領域を、３×３の正方形のサブリージョンに均等に分割する。Ｈａａｒウェーブレット応答（Haar wavelet response）ｄｘおよびｄｙを各サブリージョンで合計して、各サブリージョンが、４次元の記述子ベクトルｖ＝（Σｄｘ、Σｄｙ、Σ｜ｄｘ｜、Σ｜ｄｙ｜）を有するようにする。従って各関心点において、３６次元のＳＵＲＦ特徴量が存在することになる。
【００２２】
ＳＵＲＦは、Ｈｅｓｓｉａｎベースの検知器を構築するＨｅｓｓｉａｎマトリクスの推定に基づく。ＳＵＲＦは、計算時間短縮のために積分画像を利用している。ＳＵＲＦ抽出の速度は、ＳＩＦＴの約６倍であり、ハリスの速度とは同等である。ＳＵＲＦ特徴量は、ズームイン／ズームアウトおよびカムコードといったビデオコピー変換に対してロバストである。
【００２３】
コンピュータビジョンおよび画像検索には、カラーヒストグラム、序数特徴量（ordinal features）、および局所特徴量（ハリスおよびＳＩＦＴ等）等の数多くの特徴量が利用されている。ビデオコピー検知においては、全画像フレームのカラーヒストグラム特徴量といった大域特徴量は、局所変換（例えばクロップおよびスケール変換）の検知には利用できない。様々な実施形態では、局所特徴量がビデオをシフト、クロップ、またはズームイン／ズームアウトするときに変化しないことから、局所特徴量をビデオから抽出する手法を利用している。
【００２４】
ブロック３０４では、軌跡データベースを構築して、ビデオデータベースの軌跡用の索引を生成する。ビデオデータベースの各フレームからＳＵＲＦ点を抽出した後で、これらＳＵＲＦ点を追跡して、そのビデオの時空間特徴量として軌跡を構築する。各軌跡は、Ｔｒａｎ＝「ｘｍｉｎ、ｘｍａｘ、ｙｍｉｎ、ｙｍａｘ、ｔｉｎ、ｔｏｕｔ、Ｓｍｅａｎ」で表され、ｎ＝１、２、…Ｎであり、「ｘｍｉｎ、ｘｍａｘ、ｙｍｉｎ、ｙｍａｘ、ｔｉｎ、ｔｏｕｔ」は、時空間境界立方体（spatial-temporal bounding cube）を表しており、Ｓｍｅａｎは、軌跡のＳＵＲＦ特徴量の平均値である。
【００２５】
ｘ、ｙ方向に高速に移動する点については、その軌跡の空間位置を他から区別する用途に、軌跡立方体は大きすぎる。従って様々な実施形態では、これらの軌跡を幾つかの短期セグメントに分割することで、短い期間にすることで空間位置における軌跡立方体を十分小さくする。
【００２６】
高速なオンラインビデオコピー検知については、Ｓｍｅａｎ特徴量を利用して軌跡を索引付けする、ＬＳＨが利用される。例えば、Ｓｍｅａｎ特徴量のクエリを生成して軌跡を索引付けする。ＬＳＨでは、特徴量空間が極僅か変化した場合であっても、それに比例してハッシュ値が変化する（つまり、ハッシュ関数が場所に感度を有する）。様々な実施形態では、Ｅ２ＬＳＨ（Exact Euclidean LSH）を利用して軌跡を索引付けする。Ｅ２ＬＳＨは、例えばＡ．Ａｎｄｏｎｉ氏およびＰ．Ｉｎｄｙｋ氏のＥ２ＬＳＨ０．１ユーザ・マニュアル、２０００年６月に記載されている。
【００２７】
図４は、一実施形態におけるビデオコピーを判断するプロセス４００の一例を示す。一部の実施形態では、オンラインコピー検知モジュール２５０は、プロセス４００を実行することができる。ブロック４０２は、映像クエリフレームに関連する軌跡に基づいて投票ベースの時空間スケール登録を実行する。投票ベースの時空間スケール登録は、時空間スケールオフセット空間を、それぞれ異なるスケールおよび投票の３Ｄ立方体に適合的に分割して、同様のＳｉｍｍｎを対応する立方体へと投票する。適合的分割には、立方体サイズの変更が含まれる。各立方体は、可能性のある時空間オフセットパラメータに対応している。クエリフレームｋについては、最大累積スコアを有する立方体（つまり、クエリフレームｋの関心点を最も多く登録された軌跡を有する立方体）が、最適なオフセットパラメータに対応している。
【００２８】
候補の軌跡Ｔｒａｎの境界立方体は、間隔を置いた値のデータであり、時空間スケールパラメータオフセット（Ｉｄ、ｋ）も間隔を置いた値である。スケールパラメータスケールを「ｓｃａｌｅｘ、ｓｃａｌｅｙ」とすると、映像クエリの選択されたフレームｋ内のＳＵＲＦ点ｍと、軌跡データベースのビデオＩｄの候補の軌跡ｎとの間のＯｆｆｓｅｔｓｃａｌｅｍｎ（Ｉｄ、ｋ）は、以下のように表される。
【数Ａ】
2012531130.tif 000003
【００２９】
例えば、ｓｃａｌｅｘ＝ｓｃａｌｅｙ∈「０．６、０．８、１．０、１．２、１．４」として、ズームイン／ズームアウト等の一般的なスケール変換を検知する。他のスケール因子を利用することもできる。カムコード変換のｓｃａｌｅｘはｓｃａｌｅｙではないといったように、それぞれ異なるスケールパラメータを有するので、ｘ、ｙスケールパラメータを、「ｓｃａｌｅｘ＝０．９、ｓｃａｌｅｙ＝１．１」、および、「ｓｃａｌｅｘ＝１．１、ｓｃａｌｅｙ＝０．９」と設定する。
【００３０】
利用可能なオフセットであるＯｆｆｓｅｔｓｃａｌｅ（Ｉｄ、ｋ）は数千あり、時空間スケールオフセット空間は、直接リアルタイムに探すには大きすぎる。離散空間における投票パラメータへのＨｏｕｇｈ変換利用に類似したものとして、様々な実施形態では、三次元アレイを利用して、離散時空間でＯｆｆｓｅｔｓｃａｌｅ（Ｉｄ、ｋ）のＳｉｍｍｎの類似スコアを投票することが行われている。スケールパラメータスケールが所与であれば、時空間検索空間｛ｘ、ｙ、ｔ｝を適合的に、ｃｕｂｅｉ各々が基本投票単位である数多くの立方体に分割する。
【００３１】
一部の実施形態では、ｘ軸を、全ての候補の軌跡の開始点
【数Ｂ】
2012531130.tif 000004
および終了点
【数Ｃ】
2012531130.tif 000005
により、それぞれ異なるサイズの数多くの一次元ビンに適合的に分割する。間隔を置いた値の範囲Ｏｆｆｓｅｔｍｎがｃｕｂｅｉと交差する場合に、各候補の軌跡Ｔｒａｊｎにおいて、類似度Ｓｉｍｍｎを累積する。適合的分割処理は、ｙ軸およびｔ軸についても同様に行う。
【００３２】
これら立方体に基づいて、ビデオＩｄとクエリフレームｋとの間の最適な時空間登録パラメータＯｆｆｓｅｔｓｃａｌｅｍｎ（Ｉｄ、ｋ）により、互換性のあるクエリスコア（ｍ、ｎ、ｃｕｂｅｉ）の累積値を、以下の式を利用して最大化する。
【数Ｄ】
2012531130.tif 000006
【００３３】
ブロック４０４では、複数のフレームから決定されたオフセットを伝播および統合して、最適なオフセットパラメータを決定する。図６の説明では、最適なオフセットパラメータを決定するためにオフセットを伝播および合成する例が取り上げられた。異なる大きさの時空間スケールパラメータＯｆｆｓｅｔｓｃａｌｅ（Ｉｄ、ｋ）を判断した後で、これらＯｆｆｓｅｔｓｃａｌｅｍｎ（Ｉｄ、ｋ）パラメータを伝播および合成して、最終的なビデオコピー検知を行う。
【００３４】
空間方向で立方体の拡張を行った後で、オフセット立方体Ｏｆｆｓｅｔ（Ｉｄ、ｋ）をさらに時間方向およびスケール方向で伝播する。７つの選択されたフレームについて、「Ｏｆｆｓｅｔｓｃａｌｅ（Ｉｄ、ｋ−３）、Ｏｆｆｓｅｔｓｃａｌｅ（Ｉｄ、ｋ＋３）」で検索を行い、空間交差部を累積して、３つのスケールについて、「ｓｃａｌｅ−０．２、ｓｃａｌｅ＋０．２」を行い、それぞれ異なるスケールに対応するロバストな結果を得る。そして、最適なオフセットであるＯｆｆｓｅｔ（Ｉｄ、ｋ）が発見され、この最適なオフセットは、これら３＊７（つまり２１）オフセットの交差立方体で最大の累積投票値を有する。この伝播ステップにより、オフセット間の格差が平坦化され、同時に、急峻な／誤ったオフセットを取り除くことができる。
【００３５】
しかし、ランダムな摂動のために、実際の登録オフセットが、推定される最適なオフセットの近隣の立方体に位置してしまうこともある。加えて、動きのない軌跡は、推定されたオフセットを幾らか偏らせるが、これは、間隔ＯｆｆｓｅｔｘｍｉｎおよびＯｆｆｓｅｔｘｍａｘの間の間隔（あるいは、ＯｆｆｓｅｔｙｍｉｎおよびＯｆｆｓｅｔｙｍａｘの間の間隔）が非常に小さくて、近隣の立方体に投票できないからである。マルチスケールに伴う偏りはさらに、ノイズ攪乱および離散スケールパラメータによっても生じる。様々な実施形態では、最適なオフセット立方体のスコアが単純な閾値を越える場合に、隣接する立方体にまでｘ、ｙ方向に僅かに拡張させて、最終ビデオコピー検知段階で伝播および合成された最適なオフセットについての推定を行う。
【００３６】
ブロック４０６は、最適なオフセットに一部基づき、映像クエリフレームをビデオコピーと特定することを含む。特定されたビデオコピーは、クエリ内のフレームに類似した局所ＳＵＲＦ軌跡特徴量を有するデータベースからのビデオフレーム列であり、データベースのビデオフレーム各々は、映像クエリのものに類似したオフセット（ｔ、ｘ、ｙ）を有する。加えて、コピーされる可能性のあるビデオの時間セグメントを特定する時間オフセットを提供することができる。
【００３７】
様々な実施形態は、静止画像のコピーを検知してよい。画像コピー検知においては、時間方向に軌跡および移動情報がなく、時間オフセットについて考慮されない。しかし、空間ｘ、ｙ、およびスケールオフセットを、ビデオコピー検知のものと同様に考えることができる。例えば画像コピー検知において、ＳＵＲＦの関心点を抽出して索引付けする。ビデオコピー検知に関して記載される投票ベースの方法を利用して、画像コピーを検知するのに最適なオフセット（ｘ、ｙ、スケール）を発見することができる。
【００３８】
図５は、一実施形態における、一次元ビンの場合の最適オフセットを投票する一例を示す。ｘ軸は、４つの可能性あるオフセットによって７つのビン（立方体）に適合的に分割される。この例では、ｘ軸の範囲は、ｘ１ｍｉｎとｘ４ｍａｘの範囲である。この例では、各立方体がｘ個のオフセットの範囲を表す。例えば立方体１は、ｘ１ｍｉｎとｘ２ｍａｘの間にあるオフセットをカバーする第１のビンを表している。他のオフセットのビンは、時間であり、ｙオフセットである（不図示）。
【００３９】
この例において、各可能性のあるオフセットのＳｉｍｍｎを１と想定すると、最良のオフセットは、立方体４「ｘ４ｍｉｎとｘ１ｍａｘ」であり、最大投票スコアが４である。これらのそれぞれ異なるスケールの最適なオフセットＯｆｆｓｅｔｓｃａｌｅ（Ｉｄ、ｋ）を比較することで、最適な時空間スケール登録パラメータＯｆｆｓｅｔ（Ｉｄ、ｋ）は、全てのスケールにおける最大投票スコアで推定される。
【００４０】
図６は、一実施形態における幾つかの映像クエリフレームから局所特徴量を検知する一例を示す。映像クエリフレームの丸印は、関心点を示す。ビデオのデータベースのフレームの矩形印は、（ｔ、ｘ、ｙ）次元の境界立方体を示す。図５の立方体は、単一の次元（つまり、ｔ、ｘ、またはｙ）を表している。スケール変換パラメータを推定するためには、３Ｄ（ｘ、ｙ、ｔ）投票空間の時空間登録を、各離散スケール値に別個に適用して（ｓｃａｌｅｘ＝ｓｃａｌｅｙ∈「０．６、０．８、１．０、１．２、１．４」）、検知結果を組み合わせる。
【００４１】
この例においては、５０、７０、９０の時点におけるクエリフレームからの局所特徴量が、ビデオデータベースのフレームに見えるときに、決定を行う。時点５０におけるクエリフレームは、局所特徴量Ａ−Ｄを含む。ビデオデータベースの時点５０のフレームは、ローカルのフレームＡおよびＤを含む。従って２つの投票（各局所特徴量について１つの投票）が、ビデオデータベースのフレーム５０に起因している。局所特徴量ＡおよびＤは同時で、実質的に同様の位置にあるように見受けられるので、オフセット（ｔ、ｘ、ｙ）は（０、０、０）である。
【００４２】
時点７０におけるクエリフレームは、局所特徴量Ｆ−Ｉを含む。ビデオデータベースの時点１２０におけるフレームは、局所特徴量Ｆ−Ｉを含む。従って４つの投票が、ビデオデータベースのフレーム１２０に起因している。局所特徴量Ｆ−Ｉは５０フレーム後であり右下の方向にシフトされているように見受けられるので、オフセット（ｔ、ｘ、ｙ）は（５０フレーム、１００画素、１２０画素）である。
【００４３】
時点９０におけるクエリフレームは、局所特徴量Ｋ−Ｍを含む。ビデオデータベースの時点１４０におけるフレームは、局所特徴量Ｋ−Ｍを含む。従って3つの投票が、ビデオデータベースのフレーム１４０に起因している。局所特徴量Ｋ−Ｍは５０フレーム後であり右下の方向にシフトされているように見受けられるので、オフセット（ｔ、ｘ、ｙ）は（５０フレーム、１００画素、１２０画素）である。
【００４４】
時点５０におけるクエリフレームは局所特徴量Ｄを含む。ビデオデータベースの時点１６０におけるフレームは、局所特徴量Ｄを含む。従って、１つの投票が、ビデオデータベースのフレーム１６０に起因している。局所特徴量Ｄは１１０フレーム後であり左上の方向にシフトされているように見受けられるので、オフセット（ｔ、ｘ、ｙ）は（１１０フレーム、−５０画素、−２０画素）である。
【００４５】
ビデオデータベースのフレーム１００、１２０、および１４０は、同様のオフセット（ｔ、ｘ、ｙ）を有する。つまり、図５のスキームを参照すると、フレーム１００、１２０、および１４０からのオフセットは、同じ立方体内に収まる。最適なオフセットは、複数のフレームに関連するオフセットである。同様のオフセットを有するフレームは、連続したビデオクリップに統合される。
【００４６】
様々な実施形態のパフォーマンスを評価するために、ＩＮＡ（French Institut National de l'Audiovisuel）およびＴＲＥＣＶＩＤ２００７ビデオデータセットからランダムに撮られた２００時間分のＭＰＥＧ−１ビデオに広範な実験を行った。ビデオデータベースを、参照データベースと非参照データベースという２つの部分に分割した。参照データベースは７０時間の１００本のビデオである。非参照データベースは１３０時間の１５０本のビデオである。
【００４７】
２つの実験を行って、システム性能を評価した。まず、１ＧのＲＡＭを備えるＰｅｎｔｉｕｍ（登録商標）ＩＶ２．０ＧＨｚ上で動作させると、参照ビデオデータベースは、ＬＳＨによりオフライン索引された１，４６５，５３２ＳＵＲＦ軌跡のレコードを有した。オンラインビデオコピー検知モジュールは映像クエリの各サンプリングされたフレームにおいて最大でＭ＝１００個のＳＵＲＦ点を抽出した。時空間スケールオフセットを、Ｐ＝２０個のフレームごとに計算した。各クエリＳＵＲＦ点について、Ｎ＝２０個の候補の軌跡をＬＳＨにより発見するのに約１５０ｍｓかかった。７個のスケールパラメータで最適なオフセットを推定するのに、約１３０ｍｓの時空間スケール登録コストがかかった。
【００４８】
実験１では、ビデオコピー検知性能を、ＳＵＲＦ特徴量およびハリス特徴量それぞれへの異なる変換について比較した。２０個の映像クエリクリップを、参照データベースのみから、各ビデオクリップの長さを１０００フレームとしてランダムに抽出した。各ビデオクリップを、異なる変換法により変換して、映像クエリ（シフト、ズームアスペクト）を生成した。
【００４９】
表１は、ＳＵＲＦ特徴量およびハリス特徴量それぞれに異なる変換を行うビデオコピー検知方法を比較した結果を示す。
【表１】
2012531130.tif 000007
【００５０】
表１から、ＳＵＲＦ特徴量が、ハリス特徴量よりも、ズームイン／ズームアウトにおいて約２５から５０％優れていることが分かる。加えて、ＳＵＲＦ特徴量は、シフトおよびクロップ変換においてはハリスと類似した性能を発揮している。加えて、ハリス特徴量よりもＳＵＲＦ特徴量を利用することで、２１％から２７％程度、検知に成功したコピーフレーム数が多かった。
【００５１】
実際のより複雑なデータのテストにおいて、ＳＵＲＦ特徴量に基づく時空間スケール登録法は、Ｊ．Ｌａｗ−Ｔｏの文献に記載されているハリス特徴量に基づくビデオコピー検知法に匹敵する。映像クエリクリップは、１５個の変換された参照ビデオと１５個の非参照ビデオとからなり、総計すると１００分となる（１５０，０００フレーム）。参照ビデオは、実験１とは異なる変換および異なるパラメータで変換される。
【００５２】
図７は、システム性能を記述する作用特性曲線（ＲＯＣ：operation characteristic curves）の受信を示す。様々な実施形態で、Ｊ．Ｌａｗ−Ｔｏの文献に記載されているハリス特徴量に基づくビデオコピー検知法よりずっと優れたパフォーマンスが示されている。偽の正のフレームレートが１０％である場合、ハリスの方法における真の正のフレームレートは６８％であるが、様々な実施形態における方法では、９０％の真の正のフレームレートを達成することができる。Ｊ．Ｌａｗ−Ｔｏの文献の報告では、偽の正のフレームレートが１０％である場合、真の正のフレームレートは、８２％であった。しかし、Ｊ．Ｌａｗ−Ｔｏの文献は、スケール変換が０．９５−１．０５に制限されるとも述べている。様々な実施形態におけるこれよりも高いパフォーマンスは、ロバストなＳＵＲＦ特徴量、ひいては、効率的な時空間スケール登録に貢献する。加えて、伝播および合成を利用することで、可能な限り検知されたビデオクリップを伝播して、急峻な誤ったオフセットを平坦化／除去するときに非常に有用でもある。
【００５３】
ここに記載するグラフィックおよび／またはビデオ処理技術は、様々なハードウェアアーキテクチャで実装することができる。例えば、グラフィックおよび／またはビデオ機能はチップセットに統合することができる。または、離散グラフィックおよび／またはビデオプロセッサを利用することもできる。また別の実施形態として、グラフィックおよび／またはビデオ機能を、汎用プロセッサ（マルチコアプロセッサを含む）により実装することもできる。またさらなる実施形態では、これら機能を、家庭用電子機器に実装することもできる。
【００５４】
本発明の実施形態は、マザーボード、ハードワイヤ論理、メモリデバイスに格納され、マイクロプロセッサ、ファームウェア、特定用途向け集積回路（ＡＳＩＣ）、および／または、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）により実行されるソフトウェアを利用して相互接続された１以上のマイクロチップまたは集積回路のいずれか、または任意の組み合わせとして実装することもできる。「論理」という用語は、一例として、ソフトウェアまたはハードウェア、および／または、ソフトウェアとハードウェアの組み合わせを含んでよい。
【００５５】
本発明の実施形態は、例えば、コンピュータ、コンピュータネットワーク、その他の電子機器等の１以上の機械により実行されると、本発明の実施形態における処理を１以上の機械に実行させる機械実行可能命令を格納する１以上の機械可読媒体を含んでよいコンピュータプログラムプロダクトとして提供されてよい。機械可読媒体には、これらに限定はされないが、フロッピー（登録商標）ディスク、光ディスク、ＣＤ−ＲＯＭ、および光磁気ディスク、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、光磁気カード、フラッシュメモリ、その他の種類の、機械実行可能命令の格納に適した媒体／機械可読媒体を含んでよい。
【００５６】
図面および上述した内容は、本発明の例示である。複数の離散した機能アイテムが示されている場合であっても、当業者であれば、これらのエレメントの１以上を単一の機能エレメントに組み込むこともできることを理解する。また、一定のエレメントを複数の機能エレメントに分割することもできる。１つの実施形態のエレメントを別の実施形態に追加することもできる。例えば、ここで記載するプロセスの順序を変更することもでき、ここに記載した方法に限定はされない。さらに、フロー図の動作は、必ずしも示されている順序で実装される必要はなく、また、全ての動作を実行する必要もない。さらに、他の動作に依存しない動作は、他の動作と並列して実行することができる。本発明の範囲は、これら特定の例に限定されない。明細書に明示されていてもいなくてもよい、構造、寸法、および利用される材料が異なっている数多くの変形例が可能である。本発明の範囲は、以下の請求項と少なくとも同じ範囲を有する。
【図１】
2012531130.tif 000008
【図２】
2012531130.tif 000009
【図３】
2012531130.tif 000010
【図４】
2012531130.tif 000011
【図５】
2012531130.tif 000012
【図６】
2012531130.tif 000013
【図７】
2012531130.tif 000014
【国際調査報告】
2012531130.tif 000015
2012531130.tif 000016
2012531130.tif 000017