データベース (数百万) やフィンガープリントによって重複したビデオ ファイルを見つけますか?パターン認識？

StackOverflow https://stackoverflow.com/questions/3591731

質問

次のシナリオの場合:

現在約 1 万のビデオ ファイルのカタログを持つプロジェクトを入手しましたが、その数は劇的に増加する予定です。

ただし、それらの多くは重複しています。すべてのビデオ ファイルに意味論的および説明的な情報を関連付けており、重複したものをマージして、すべてのファイルについてより良い結果を実現したいと考えています。

ここで、データベース内のメタデータにインデックスを付ける何らかの手順が必要になります。新しいビデオがカタログに入るたびに、同じデータが計算されてデータベース内で照合されます。

問題は、ビデオが完全に複製されていないことです。品質が異なったり、アンビーにトリミングされたり、透かしが入ったり、続編/前編が含まれたりする場合があります。または、最初または最後が切れています。

残念ながら、比較が優れていればいるほど、CPU とメモリの負荷が高くなります。そのため、非常に優雅だが高速な比較 (10% の許容範囲でおそらくビデオの長さ) から始まり、最終比較で終わる、いくつかの層の比較を実装する予定です。それは実際には重複しています（それはコミュニティ投票になります）。

したがって、結果を検証するためのコミュニティがあるので、低いミス率で「適切な推測」を提供するだけで十分です。

そこで私の質問は、どのようなレイヤーが考えられますか、あるいはより良いアプローチはありますか?

メタデータを作成する労力は気にしません。それを行うのに十分なスレーブがあるからです。比較だけでも速いはずです。それで、それが役立つなら、ビデオを100回変換することもできます...

私の現在のアイデアは次のとおりです。

  • 動画の長さ (秒)

  • 最初と最後のフレーム画像の分析

画像をサムネイル サイズにリサンプリングして平均 rgb 値を取得し、このピクセルの色が 0 または 1 で表される平均より大きいか小さいかどうかをピクセルごとにシリアル化します。そこで、mysql に保存できるバイナリ文字列を取得し、ブール値ビットサム (mysql 内部でサポートされている) を実行し、残りの不等ビットをカウントします (同様に内部的にサポートされており、バイナリ文字列のレーベンシュタイン距離になります)。

  • 同じ VBR コーデックを使用した時間の経過によるビットレートの発展

まったく同じ設定でビデオを vbr ビデオファイルにトランスコードします。次に、特定の時点でのビットレート (ビデオが完了した割合または絶対秒数) を調べます。その場合、ビデオの一部のみを分析します)。写真と同じこと。ビットレートが平均より大きい場合は 1、それ以外の場合は 0。バイナリ文字列を作成して db に保存し、後でレーベンシュタイン距離を計算します

  • オーディオ分析 (ビデオのビットレートと同様に、時間の経過に伴うビットレートとデシベルの変化)

  • キーフレーム分析

最初と最後のフレームと同じように画像を比較しますが、キーフレームの位置は異なりますか?キーフレームはコーデックと設定に依存するため、ビットレートの計算に使用したものと同じソース ファイルを使用します。

  • 時間の経過とともに発色する

画像内の 1 つ以上の領域/ピクセルを取り出し、それらが時間の経過とともにどのように変化するかを見てみましょう。平均を上回る/下回る変化も同様です。黒/白で十分だと思います。

  • 最終的な承認のためにユーザーに提案を提示します...

それとも完全に間違った方向に進んでいるでしょうか？この問題を抱えているのは私が最初ではないと思いますが、解決策を見つけることができませんでした。

役に立ちましたか？

解決

これは大きな問題であるため、問題を解決しやすい部分に分解するために、かなり長い返信を書くことにしました。

利用可能なコンピューティング リソースと時間リソースを使用して比較を実行することが重要です。実行に数か月かかるソリューションが動的ビデオ データベースであまり役立つとは思えません。また、データベースのサイズにより、クラウド コンピューティング リソースの使用が不可能になる可能性があります。したがって、いくつかの異なるドメインでの各比較のローカル コストを実際に考慮します。1) データ ストレージ、2) コンピューティング リソース、3) 時間。

考慮すべき重要なコストの 1 つは、使用する比較指標に関係なく、各ビデオから必要なデータを抽出するコストです。抽出されたデータが利用可能になったら、比較を実行するコストを考慮する必要があります。最後に、すべてのビデオを相互に一致させるために必要な比較を実行する必要があります。

最初の 2 つのステップのコストは、ビデオの数に対して O(1) です。最後のステップのコストは O(1) よりも悪くなければならず、場合によってはさらに悪くなる可能性があります。したがって、初期の単純なステップを多数追加することになる場合でも、最後のステップのコストを最小限に抑えることが主な目標である必要があります。

このプロセスに最適なアルゴリズムは、データベースの特性、単一または複数の一致が存在するレベルに大きく依存します。ビデオの 100% が他のビデオと一致する場合、一致に成功するコストを最小限に抑える必要があります。ただし、より可能性の高いケースは、一致がまれであるため、一致が失敗した場合のコストを最小限に抑えたいと考えます。つまり、「これら 2 つのビデオは一致するはずがない」と言う簡単で汚い方法がある場合は、一致の確認を始める前に、まずそれを使用する必要があります。

データベースの特性を評価するには、まずサンプリングと手作業によるマッチングを実行して、データベース内の一致の程度を推定します。この実験では、冗長なビデオがどのように「固まった」のかを示す必要があります。特定のビデオに一致があった場合、複数の一致が存在する可能性はどのくらいですか?全試合のうち何パーセントが複数試合の一部でもありましたか?このプロセスにより、アルゴリズムの選択とシステムの調整を支援するために使用されるデータベースの「モデル」 (統計分布) が生成されます。

今後は、一致することは比較的まれであると仮定します。結局のところ、一致するものが多数ある場合、ビデオは「固まり」、事実上データベースが小さくなり、問題が単純になります。問題が可能な限り難しいままであると仮定しましょう。

私は、「これら 2 つのビデオは一致しない」/「これら 2 つのビデオは一致する可能性がある」という二項決定を繰り返し実行する一連のアルゴリズムを構築する、マルチレベルの分類アプローチを推奨します。チェーンの最後のアルゴリズムだけが、「これら 2 つのビデオは一致します」という答えを出力する必要があります。

分類/照合アルゴリズムは、次の 2 つの方法のいずれかまたは両方で失敗する可能性があります。偽陽性（一致しないビデオが一致すると誤ってラベル付けされる）と偽陰性（一致するビデオが一致しないと誤ってラベル付けされる）。これらの誤った決定にはそれぞれさまざまな確率が関連付けられており、私たちは両方を最小限に抑えたいと考えています。

アルゴリズム パイプラインを構築しているので、エラーなしで不一致を識別する能力に優れたアルゴリズムが必要です。つまり、アルゴリズムの誤拒否率が非常に低くなければならず、誤受理率はあまり気にしません。たとえば、Wierd Al のビデオのクローンは、見た目も音もオリジナルに非常によく似ている可能性がありますが、アルゴリズム パイプラインの後半までそれがオリジナルと一致しないことを示すことができない場合があります。

圧倒的に大多数のテストでは「一致しない」という結果が得られるため、最も単純、最速、最も信頼性の高いアルゴリズムを最初に実行する必要があります。最も簡単なチェックは、データベース内で同一のファイルを検索することです。これは、多くの高速でシンプルなファイル システムおよびデータベース メンテナンス ユーティリティによって実行されます。このスキャンの実行後、違いを検出するために実際にビデオ ファイルを開いて読み取る必要があると想定できます。

ビデオの比較は比較的難しいので、オーディオから始めましょう。データベースは、まず重複を含む可能性のある MP3 コレクションであると考えてください。結局のところ、音声が適切に一致すれば、ビデオも一致する可能性が高く、その逆も同様です。音声はビデオを「公正に」代表していると言って間違いありません。幸いなことに、Web を簡単に検索すると、信頼性が高く、高速で成熟したオーディオ フィンガープリントと比較のパッケージが多数見つかります。オーディオ フィンガープリントは、データベース内のビデオごとに生成する必要があります。オーディオ トラックのないビデオは、自動的に「一致する可能性がある」セットに分類されます。

しかし、ここには「落とし穴」があります。ナレーションについてはどうですか？特定のビデオがナレーションありとなしで 2 回エンコードされた場合、それらは一致しますか?フランス語音声とスペイン語または英語はどうですか?これらがすべて一致するとみなされる場合は、オーディオ テストをスキップする必要がある場合があります。

この時点で、ファイルシステムのエントリはすべて「十分に異なっている」ことがわかっており、オーディオ トラックも (テストした場合は) すべて「十分に異なっている」ことがわかっています。つまり、ビデオ データの確認をこれ以上先延ばしにすることはできないということです。幸いなことに、これを行う必要があるのはビデオ データベースのごく一部だけであるため、ある程度のコストは許容できます。以前と同様に、一致を積極的にラベル付けする前に、まずより多くの不一致を迅速に削除することを試みる必要があります。

解像度の変更（たとえば、1080p から iPod へ）を考慮する必要があるため、解像度に依存しないだけでなく、解像度の一部として追加されるノイズやデータ損失にも耐えられるビデオ情報を特徴付ける方法が必要になります。解像度を変更します。フレーム レートの変更 (たとえば、映画の 24 fps からビデオの 30 fps へ) を許容する必要があります。4:3 NTSC から 16:9 HD へなど、アスペクト比の変更も考慮する必要があります。カラーからモノクロなど、色空間の変更を処理したいと考えています。

さらに、HD と PAL の間のトランスコーディングなど、これらすべてに一度に影響を与える変換があり、色空間、フレーム レート、アスペクト比、解像度に同時に影響を与える可能性があります。特性評価は、4:3 と 16:9 のアスペクト比の間の切り替え (レターボックス、パン & スキャンは不可) などによって発生するような、ある程度のトリミングや塗りつぶしを許容する必要もあります。また、長編映画の終わりからクレジットを削除するなど、切り詰められたビデオも処理する必要があります。そして当然のことながら、同一のビデオ ストリームを供給された異なるエンコーダーによって生じた差異にも対処する必要があります。

かなりのリストですね！考慮しないことを選択できるいくつかの事柄について考えてみましょう。アナモルフィック ワーピングは珍しいことではありませんが、特にアナモルフィック再構成なしで直接スキャンされた 35 mm ワイドスクリーン ムービー (背が高く痩せた人) では、画像の歪みが存在する場合に一致を見つけることができなくても問題ないと思います。また、フレームの中央に大きな透かしが存在する場合は失敗することを選択することもありますが、隅にある小さな透かしは許容する必要があります。そして最後に、一方が他方のスローモーションである場合や、左右が反転している場合など、時間的に歪んだり空間的に反転したビデオの一致に失敗しても問題ありません。

それはビデオスペースをほぼカバーしているでしょうか?ファイルシステムとオーディオから始めることがなぜ重要なのかが明らかになったことを願っています。つまり、データベースをビデオ コレクションとして考える前に、まず MP3 コレクションに似たものとして考えてください。

オーディオを無視すると、ビデオは単なる静止画像の順序付けされたシーケンスです。したがって、実際には、1 つまたは複数の時系列比較アルゴリズムと組み合わせた 1 つまたは複数の画像比較アルゴリズムを探しています。これは、個別のアルゴリズムのペア (各フレームを特徴付けてからフレームのシーケンスを特徴付ける) であることも、単一のアルゴリズムにマージすることもできます (フレーム間の違いに注目します)。

画像自体はさらに、モノクロの「構造」画像とカラーの「オーバーレイ」に分解できます。計算上都合がよければ、色情報を無視しても問題ないと思います。

上記のことから、比較を実行するにはビデオを完全にデコードする必要があると想定しているように聞こえるかもしれません。必ずしもそうとは限りませんが、エンコードされたデータの比較には、その有用性を制限する多くの困難があります。これに対する 1 つの重要な例外は、MP4 などのオブジェクト レベルのビデオ エンコーディングの場合であり、非常に高度なマルチフレーム比較が実行されます。残念ながら、MP4 ストリーム間のオブジェクト比較についてはあまり研究が行われておらず、この機能を実行できるパッケージが存在しないことを私は知っています。でも、見つけたらぜひ使ってみてください！

他のほとんどのデジタル ビデオ ストリームは、MPEG2、Quicktime、または類似のものなどのエンコード スキームを使用します。これらのスキームはすべて、キー フレームと差分フレームの概念を使用していますが、それぞれの実装方法は異なります。異なるビデオ (同じサイズではないビデオ) を比較する場合、キー フレームと差分フレームが有用な程度に一致する可能性はほとんどありません。ただし、これは不可能という意味ではなく、完全なデコードを実行せずにそのようなストリームから有用な情報を抽出しようとするパッケージが存在します。高速なテストが見つかった場合は、「試してみてはいかがでしょうか」というカテゴリーのテストに分類される可能性があります。

私が使用する 1 つのトリックは、フレームを完全にデコードするのではなく、RGB フレームバッファまでではなく、個別のコンポーネント チャネル (HSV、HSL、YUV など) にのみデコードすることです (もちろん、それがエンコードされている場合を除きます)。 ）。ここから、次に、関連するドメインで比較を実行できるように、個別の輝度フレームとクロミナンス (カラー) フレームを作成します。RGB フレームバッファまでデコードするとエラーが発生し、一致するものを見つけることがより困難になる可能性があります。

次に、色の情報を破棄します。モノクロ ビデオはカラーのオリジナルと一致する必要があるため、色はまったく気にしません。

結果として得られるモノクロ フレームのシーケンスを、非常に異なって見えても一致する可能性がある別のシーケンスと最もよく比較するにはどうすればよいでしょうか?この分野では文字通り何十年にもわたって研究が行われており、その多くは「スケール不変の一致検出」に分類されています。残念ながら、この調査のうち、ビデオが一致するかどうかの判断に直接適用されたものはほとんどありません。

私たちの目的のために、この問題にはいくつかの方向からアプローチできます。まず、モノクロ領域で何が一致し、何が一致しないのかを自分で知る必要があります。たとえば、一致するが異なる 2 つのビデオの解像度が同じであっても、エンコーダーの違いなどによるある程度のノイズを許容する必要があるため、ピクセル レベルの違いは気にしません。

簡単な (ただし時間がかかる) 方法は、各画像を解像度とアスペクト比の両方に依存しない形式に変換することです。このような変換の 1 つは空間周波数領域への変換であり、2D FFT はこれに最適です。虚数成分を破棄した後、実数成分はノイズを除去するために高周波で切り詰められ、アスペクト比の影響を除去するために低周波で切り詰められ、その後標準スケールに正規化されて解像度の差が除去されます。結果として得られるデータは、ビデオ ストリーム間で直接比較できる奇妙な小さな画像のように見えます。

他にも多くの可能なフレーム変換戦略があり、その多くは FFT よりもはるかに効率的であり、文献検索によりそれらが明らかになるはずです。残念ながら、FFT ほど使いやすいソフトウェア ライブラリに実装されているものを私はほとんど知りません。

モノクロ フレームをより小さく、より有用なドメインに変換した後も、別のビデオからの別のそのようなストリームとの比較を実行する必要があります。そして、そのビデオはフレームごとに一致しないことがほぼ確実なので、単純な比較は間違いなく失敗します。フレームの追加/削除やフレームレートの違いなど、時間領域での違いを考慮した比較が必要です。

FFT フレームのシーケンスを見ると、いくつかの非常に特徴的な動作に気づくでしょう。シーンのフェードは突然で非常に見つけやすく、カットも区別できます。通常、カット間の FFT ではゆっくりとした変化しか見られません。FFT のシーケンスから、各フレームをカット/フェード後の最初のフレームとして、またはカット/フェード間のフレームとしてラベル付けできます。重要なのは、各カット/フェードの間のフレーム数とは無関係な、各カット/フェード間の時間です。これにより、フレーム レートにほとんど依存しないシグネチャまたはフィンガープリントが作成されます。

ビデオ全体のこのフィンガープリントを取得すると、ビデオ自体よりもはるかに小さいデータが得られます。これは、オーディオとよく似た線形の数値シーケンス、単純な時系列ベクトルでもあり、多くの同じツールを使用して分析できます。

最初のツールは、相関関係を実行して、あるビデオのカット パターンが別のビデオのカット パターンとよく一致するかどうかを判断することです。大きな違いがある場合、ビデオは異なります。それらがよく一致する場合、フレームが一致するほど類似しているかどうかを判断するために、各相関カット後の少数の FFT のみを比較する必要があります。

2D FFT の比較については、私よりもはるかに優れた参考文献が豊富にあるため、ここでは触れません。

注記：追加のフィンガープリントを取得するためにモノクロ フレームに適用できる操作 (2D FFT 以外にも) は他にもたくさんあります。実際の画像コンテンツの表現は、画像の内部エッジを抽出することによって (文字通り FBI の指紋のように)、または画像を選択的にしきい値処理して「ブロビング」操作を実行することによって作成できます (関連領域記述子のリンク リストの作成)。フレーム間のエッジやブロブの変化の追跡は、カット リストの生成に使用できるだけでなく、2D FFT を使用すると失われる可能性のある追加の高レベルの画像特性を抽出するためにも使用できます。

私たちは、不一致を見つけるのに非常に高速であり、最終的に一致を判断するのにあまり時間を必要としない、一連の比較アルゴリズムを構築しました。残念ながら、アルゴリズムを持っているだけでは解決策は得られません。これらのアルゴリズムを最適に実装する方法に関連するいくつかの問題を考慮する必要があります。

まず、必要以上に各ビデオ ファイルを開いたり読み取ったりすることは望ましくありません。そうしないと、CPU がディスクからのデータを待機して停止する可能性があります。また、必要以上にファイルを読み込むことも望ましくありませんが、すぐに読み込みを停止して後の一致を見逃してしまう可能性も避けたいと考えています。各ビデオを特徴づける情報は保存されるべきですか、それとも必要なときに再計算されるべきですか?これらの問題に対処することで、効率的かつ効果的なビデオ比較システムを開発、テスト、展開できるようになります。

私たちは、非常に変化しやすい条件下で、計算効率を高めてビデオを比較し、一致するものを見つけることができることを示しました。

残りは読者のための演習として残されています。;^)

他のヒント

素晴らしい質問！テストのみが、これらの要因のどれが最良の指標になるかを示します。いくつかのアイデア：

  • 同じVBRコーデックを使用して、時間の経過とともにビットレートの開発：非常にCPU集約型に聞こえますが、大きな結果が得られると思います。オーディオ分析は、作業が少ないと同様の結果が得られるようです。
  • 最初と最後のフレーム画像分析：これらの50％は黒ではないでしょうか？より良いアイデアは、真ん中のフレームを使用することかもしれませんが、私はこのテクニックが信頼できることを期待していません。
  • ベイジアン統計を使用します どの要因がポジティブな一致に最適な貢献をするかを記録する。これは、テストフェーズで、役に立たない高価な比較を発揮するために行うことができます。
  • ユーザーに助けてもらいましょう！ ユーザーが一緒にグループ化して、見つけた複製をします。彼らは最高の品質を持つものに投票し、それはグループ内のプライマリ/公式バージョンとして機能します。
  • 最も簡単な比較から始めます そして、単純なものの欠点を見つけると、より洗練されたテストを追加します。ビデオの長さは、最初から良いものになり、おそらくいくつかの初歩的なオーディオ分析を行い、そこからあなたの道を進むでしょう。

この製品を試してみてください - 複製ビデオ検索 （Ex。VisualSearch Pony）、さまざまなビットレート、フォーマット、解像度などの複製ビデオファイルを見つけることができます。

たとえば、Star -Wars.avi（640x480 H.264）およびSW.MPG（1280x720 MPEG）は、両方が素晴らしい映画のコピーである場合に重複として検出されます。

彼らのウェブサイトによると、この製品は、キーフレームの興奮やSMTHなどのビデオフィンガープリント技術を使用しています。このように、ビデオエンコード、解像度、品質、ビットレートなどから独立してください。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top