あいまいな重複ビデオを見つけるためのいくつかの方法

分析が必要なかなり広範囲のタスク、現実の視聴覚モデルがあります。 これは静止画像とビデオに適用されます。











以下は、ファジー重複ビデオを検索および識別するためのいくつかの既存の方法の簡単な概要です。それらの利点と欠点が考慮されます。 ビデオの構造的なプレゼンテーションに基づいて、方法の組み合わせが構築されます。

レビューは非常に小さく、詳細については、ソースを参照することをお勧めします。



「ファジー複製」という用語は、オブジェクトが類似クラスの別のオブジェクトと不完全または部分的に一致することを意味します。 複製は自然で人工的なものです。 自然複製は、同様の条件下での同様のオブジェクトです。 人工ファジー複製-同じオリジナルに基づいて取得。



あいまいな重複の検索は、無人航空機の光学ナビゲーション（残念ながら、必ずしも平和的な目的とは限りません）、地形の性質の決定、ビデオカタログのコンパイル、検索エンジンスニペットのグループ化、ビデオ広告のフィルタリング、「海賊版」ビデオの検索に役立ちます。











ファジービデオ複製（NDV）の検索の問題は、分類（CV）およびビデオ検索（PV）の問題と密接に関連しています。 NDV検索のタスクは分類に、それから注釈とビデオ検索に減らすことができます。 | {NDV検索} | <| {KB} | <| {PV} |。 しかし、これらのタスクは独立しています。

一般的なアルゴリズム

NDVを検索するために、ビデオはセグメントに分割されます。 キーフレームは各セグメントから抽出されます。 キーフレームの特性は、ビデオ全体を表すために使用されます。 ビデオ間の類似性は、これらの特性のセットの類似性として計算されます。

アプローチ

NDVの検索方法には2つのカテゴリがあります。グローバル特性（GC）を使用する方法です。 ローカル特性（LH）を使用する方法。 カテゴリ間の区別は条件付きであり、非常に頻繁に混合技術が使用されます。 GCメソッドは、空間情報、色情報、および時間情報をモデリングするためのフレームレベルのシグネチャを抽出します。 GCは、低レベル機能のグローバル統計を要約します。 ビデオ間の類似性は、一連の署名（署名）間の対応として定義されます。 それらは「ほぼ同一の」ビデオを見つけるのに役立ち、時空領域での小さな編集を明らかにすることができます。 化粧品の編集の結果として得られた人工NDVを使用する場合、GCは無効です。 このようなグループの場合、セグメントまたはフレームの低レベルの特性を使用する方法がより便利です。 通常、これらのメソッドの動作は、一時的な順序の変更とフレームの挿入または削除の影響を受けます。 グローバルな方法と比較して、セグメントレベルのアプローチは遅くなります。 かなりの編集が行われたコピーを特定することはできますが、メモリの要求はより厳しくなります。

ローカル特性

追跡追跡

LHメソッドは、類似したビデオを検索するタスクを、重複画像を見つけるタスクに減らします。 画像を比較する際の主な手順：特別なポイントの識別。 特異点の近傍の選択; 特徴ベクトルの構築; 画像記述子の選択; 画像のペアの記述子を比較します。 ビデオコピー検出の動作のラベルに基づくロバスト投票アルゴリズムの作業では、フレームの特定のポイント（ハリス検出器を使用）が区別され、その位置がビデオ全体で監視されます。 その後、多くのポイントの軌跡が形成されます。











パターンマッチングは、ファジー検索に基づいています。 このアプローチにより、ファジー重複フラグメントのローカライズが容易になります。 ただし、この方法は特別なフレームポイントの割り当てのために高価です。 また、ポイントの軌跡がカメラの動きに敏感であるという事実により、アルゴリズムはビデオの正確なコピーの検索にのみ適用されます。

平均値

SIFTメソッドを使用した非同一重複ビデオ検出の作成者は、キーフレームの特別なポイントを強調表示し、SIFTに基づいてフレームの類似性を評価します。 フレームの類似性は、一致する特異点の数の算術平均として計算されます。 ただし、ビデオの類似性を判断するために、ビデオ全体のキーフレームの類似性の平均値として完全適合性評価（PIC）が使用されます。 すべての可能なフレームペアではなく、それらの一部についてのみ平均値を計算することが重要です。 これにより、コンピューティングリソースが節約されます。

縦フレーム

作品はまた、フレームの選択が通常のビデオのように時間軸に沿って行われるという点で興味深いものです。 このようなスライスを使用すると、通常のフレームと同じように、ビデオから一時的な情報を抽出し、空間比較方法を適用できます。SIFTは2つのビデオのスライスに適用され、PICが計算されます。











実験の結果によると、縦方向のフレーム割り当ての方法は通常よりも悪いです。 これは、ビデオのシャープなカメラの動きが多い場合に特に当てはまります。 一般的なアプローチの欠点には、SIFTの使用が含まれます。 実験は、小さな解像度（320×240）のビデオで行われました。 フレームサイズが大きくなると、特別なポイントを強調表示するのに非常にコストがかかります。 PICが通常のフレームにのみ適用される場合、一時的なビデオ情報は考慮されません。

視覚的な言葉

視覚的な単語を使用する方法は、特定のフレームポイントの直接比較の改良版です。 それらは、特異点の量子化、つまり「単語」の形成に基づいています。 フレーム（およびビデオ）の比較は、テキストと同様に、完全に周波数辞書で行われます。 Inria-Leararのビデオコピー検出システムは、優れたメソッド性能を実証しています。 キーフレームは、SIFTを使用して取得される機能によって表されます。 次に、これらの特性が視覚的な単語に量子化されます。 バイナリ署名は視覚的な単語から作成されます。 ただし、視覚的な単語を適用するには、既知の主題領域の周波数辞書を作成する必要があります。

グローバル特性

GCメソッドを使用して、色、空間、および時間の情報がビデオから抽出され、一連の文字として表示され、一致する線を見つける方法が適用されます。

ローカルに敏感なハッシュ

ランダムヒストグラムと機能のセットを効率的に一致させるには、ローカルセンシティブハッシュ（LF）を使用します。 各キーフレームのカラーヒストグラムをバイナリベクトルで表示するために使用されます。 フレームの特性は、画像の局所的な特徴とは区別されます。 これらの特性は、特性の空間内のポイントのセットとして表されます。 LFを使用して、ポイントは離散値にマッピングされます。 一連の機能に基づいて、フレームのヒストグラムが作成されます。 次に、ヒストグラムは通常のシーケンスとして比較されます。











実験結果により有効性が確認されました。 しかし、 大規模なほぼ重複したWebビデオ検索：課題と機会で指摘されているように、この方法にはメモリ消費量が多いという潜在的な問題があります。 一時的な情報は一切考慮されません。

序数署名

順序測定に基づく堅牢なビデオ署名は、順序署名を使用して、フレーム内の相対強度分布をモデル化します。 2つのフラグメント間の距離は、署名の一時的な類似性を使用して測定されます。 このアプローチを使用すると、解像度やフレームレートが異なるビデオのあいまいな複製を検索できますが、フレームの空間的な変化はわずかです。 このアルゴリズムの利点は、リアルタイムで機能することです。 欠点には、余分なフレームの大きな挿入に対する不安定性が含まれます。 この方法は、たとえば被写体が異なる光条件で撮影された場合など、自然なファジー複製の検索にはあまり適していません。











ビデオコピー検出のシーケンスマッチング技術の比較は 、時間の経過に伴う強度の相対的な変化をキャプチャするモーションシグネチャを示します。 カラー署名、モーション署名、シリアル署名が比較されます。 実験では、序数の署名がより効率的であることが示されています...

DNAのようなビデオ

複数の配列アライメントによるクラスタリングに基づく準複製ビデオ検索で提案されているアプローチは、ビデオのファジー複製を見つける問題をビデオ分類の問題に軽減します。 この方法は、マルチプルシーケンスアラインメント（MSA）に基づいています。 同様のアプローチがバイオインフォマティクスで使用され、DNA配列のアライメントを検索します。 著者は、 Muscleによって提案されたヒューリスティックアラインメントと反復法を使用しています 。 高精度と高スループットの複数のシーケンスアラインメントです。 この方法は、次の一連のステップで説明できます。

1. ビデオ用にDNA表現が作成されます。
2. データベースからのビデオは、それぞれがそれぞれと比較され、距離のマトリックスが構築されます。
3. 距離行列に基づいて、隣接結合法を使用してガイドツリーが構築されます。
4. ガイドツリーに基づいて、プログレッシブビデオ調整が実行されます。
5. アライメント結果は、ビデオのクラスターを形成するために使用されます。
6. データベースを検索するとき、クエリはクラスターの中心と比較されます。 リクエストとクラスターセンターの類似性が特定のしきい値を超える場合、クラスター内のすべてのクリップは、リクエストのあいまいな複製と見なされます。

ビデオをゲノムとして表現するために、キーフレームが抽出され、グレースケールカラースペースに転送され、フレームが2×2ブロックに分割されます。たった24 =（2⋅2）！ 空間順序パターン。 このようなパターンはそれぞれ、ラテンアルファベットの文字に関連付けることができます。











距離行列は、サイズnのスライディングウィンドウを使用して構築されます。 したがって、ビデオ比較はn-gramに基づいています。 ビデオの2つのDNA表現の比較は、ウィンドウ内でのみ行われます。

ウィンドウサイズとステップサイズ（比較後にウィンドウをシフトする量）がパラメーターとして設定されます。



ガイドツリーは、ネイバーを結合するための貪欲なヒューリスティックアルゴリズムによって構築されます。 距離マトリックスに従って、2つの最も近いDNA表現が区別され、ビデオプロファイルとして単一のツリーノードに結合されます。 このモデルでは、各ビデオDNAはツリーの葉であり、プロファイルはツリーのノードに表示されます。 プロファイルも互いに比較され、シート表現と同様に接着されます。 結果は決定木です。



ガイドツリーを以下に示します。









このアプローチの利点：精度と完全性が高く、特別な計算コストを必要としません。 アプローチの短所-メソッドは、ビデオの時間情報を考慮しません。

シーンチェンジ

ビデオ共有ソーシャルネットワークでのビデオコピー検出への接尾辞配列アプローチにより、シーンの境界の定義に基づいたシグネチャが導入されました（撮影）。

3つの異なる概念があります。 フレームまたは写真フレーム-静止画像。 シーンまたは編集フレームは、場所と時間の統一によって接続されたフレームのセットです。 撮影またはシネマティックショット、撮影の単一性によって接続された多くのフレーム。 シーンには複数のショットが含まれる場合があります。 文献では、撮影はしばしば「シーン」と呼ばれます。 さらに撮影を検討しますが、同じことを「シーン」と呼びます。



ビデオには、単なる一連のフレームよりも多くの情報が含まれています。 ビデオ内のイベントは、その時間構造を一意に決定します。これは、キーフレームのセットで表すことができます。



この場合、キーフレームはIフレームとしてではなく、単に特別なビデオフレームとして理解されます。 イベントは、ビデオプロットのセマンティックコンポーネントとしてではなく、フレームのコンテンツの変化としてのみ理解されます。 キーフレームの強調表示は、輝度ヒストグラムの違いの検索に基づいています。 キーフレームを抽出した後、現在のキーフレームと前のキーフレームの間の長さが計算されます。 すべての長さは、1次元のシーケンスとして書き込まれます。 このシーンの長さのシーケンスは、ビデオの署名です。 実験によれば、2つの無関係なビデオクリップには、同じシーンの長さの連続したキーフレームの長いセットがありません。 ビデオ署名を一致させる効果的な方法が提案されています。 これには接尾辞配列が使用されます。 問題は、一般的な部分文字列を見つけることです。 ビデオ内のカメラまたはオブジェクトの動きが多く、シーン間のスムーズな移行中は、この方法はうまく機能しません。 欠点は、リアルタイムで作業できないことです。比較のために、ビデオ全体が必要です。



作業では、シーンの変化の階層の一致に基づいてビデオシーケンスのデータベースで重複を見つけるためのアルゴリズムが、シーンのツリーを一致させるためのアルゴリズムとして提案されています（撮影）。 見つかったシーンの変更に基づいて、バイナリツリーが構築されます。 サブツリーはビデオフラグメントに対応します。 サブツリーのルート頂点には、現在のフラグメントの支配的なシーンの変化の値と位置が格納されます。 比較する場合、1つのツリー（長いビデオ）で、2番目のツリーのルートに絶対値で最も近い頂点を検索し、座標を比較します。 この手順は、残りのシーンの変更に対して再帰的に実行されます。 この方法の利点は、人工的な複製を作成するほとんどの方法に対する耐性（一時的な情報のみが使用されるため）、2つのクリップを比較する複雑さが低いこと、および階層ムービーインデックスを作成できることです。 これにより、検証の初期段階で矛盾を見つけることができます。 このアプローチの欠点は、以前のアプローチと同様に、シーン自体の特性が考慮されていないことです。 あいまいな重複を判別するには、完全なビデオリクエストが必要です。これは常に可能とは限りません。

おわりに

NDVの検索にはさまざまな方法が使用されます。 現時点では、GCメソッドが最も有望と思われます。 これにより、多くの計算コストをかけずに問題をほぼ解決できます。 ただし、明確にするために、LHメソッドが必要になる場合があります。 大規模なほぼ重複したWebビデオ検索の課題である「挑戦と機会」で示されているように、組み合わせたアプローチを使用すると、個々の方法よりも高い精度が得られます。

組み合わせ

興味深いのは、ビデオの構造モデルが構築されている作品です。 ビデオは、時間とともに発展する一連の事実として見ることができます。 さらに、異なるビデオでは、事実自体とその順序の両方が異なる場合があります。 ファクトのプロパティはビデオの空間特性を形成し、ファクトの期間と順序は一時的なものです。 ビデオから事実を抽出する最も簡単な方法は、シーンの変化点を使用することです。 2つの異なる動画の時間は異なる場合があることに注意してください。 シーンの長さと隣接するシーンの長さの比を使用することを提案します... 2つのファジー複製のシーンの相対的な長さはめったに一致しません。 これは、とりわけ、シーンの境界を認識する際のエラーによるものです。 この問題を解決するために、配列アライメントアルゴリズムを適用できます。 しかし、そのため、ビデオファクトの順序のみを比較します。 ファクト自体を比較するには、シーンの内部特性、たとえば初期フレームと最終フレームの特性が必要です。 LHメソッドの手法として、ここで視覚的な単語を使用すると便利です。 シーンハンドルを取得しました。



正式には、シーンは「撮影」されます。映画のフレームは、時間領域内の多くの写真フレームの集まりであり、隣接する領域のフレームとは大幅に異なります。 下の画像-いくつかのビデオのシーンの最初のフレーム。











ソースビデオが異なるコーデックで圧縮されている場合、このビデオのあいまいな複製が得られます。 各ビデオのシーンを強調表示すると、これら2つのファイルのシーン変更ポイントが一致していないことがわかります。



この問題を解決するために、シーンの相対的な長さを使用することが提案されています。 シーンの相対的な長さは、ビデオの残りのシーンの絶対的な長さに対するシーンの絶対的な長さの比のベクトルとして計算されます。 実際の問題では、すべてではなく、前の3つのシーンの長さの比率を計算する方が便利です。 これは、ビデオ全体にアクセスできず、リアルタイムタスクなどでビデオストリームを処理している場合にも便利です。



2つのあいまいな複製のシーンの相対的な長さはめったに一致しません。 さらに、多くのシーンは単に認識されない場合があります。 これは、とりわけ、シーンの境界を認識する際のエラーによるものです。



1つのビデオの相対的なシーンの長さが別のビデオのシーンの長さと2倍以下だけ異なり、以前のすべてのシーンが整列している場合、現在のシーンのペアは、両方のビデオが互いにファジーな複製であるという条件で同じ現象を表します（ 仮説ゲイル教会 ）。 同様のアプローチが数学言語学で使用され、異なる言語のテキストの並行事例を調整します。 シーンの相対的な長さの差が小さいほど、シーンが似ている可能性が高くなります。 長さが2倍以上異なる場合、小さいシーンの長さが同じビデオの次のシーンの長さに加算され、結合されたシーンは1つと見なされます。 ビデオシーンの相対的な長さが一致する場合、シーンの内部プロパティの比較が適用されます。



したがって、提案されたシーン記述子を正式に記述することができます。 これは、シーンの長さと他のシーンの長さ、および初期フレームと最終フレームの特性の関係のベクトルで構成されています。 Gale Churchの仮説を前提として、隣接するシーン（以前の3つのシーン）の関連付けを使用して、すぐに保存すると便利です。

そして...

このような記述子とさまざまな技術的なトリック（セマンティックハッシュ）のおかげで、かなり明白なアルゴリズムが構築されました。











しかし、その実用的な実装はまだ初期段階です。 それにもかかわらず、いくつかの結果が得られました*が、何らかの外部の理由で作業が一時的に停止しました。



私はコメントや追加を非常にうれしく思います。



UPD 1：



素材に関する追加情報は、プレゼンテーションで見つけることができます。 あいまいな重複ビデオを見つけるための要素



トピックの詳細：

• ビデオコンテンツの分析に基づいて類似のビデオを検索する（アナトリーボリソフ）
  
  

謝辞

文法エラーを修正してくれたgoodokに感謝します。