これは大きな問題なので、問題を解決しやすい部分に分解するために、かなり長い返信を書くことにしました。
利用可能なコンピューティング リソースと時間リソースを使用して比較を実行することが重要です。実行に数か月かかるソリューションが、動的なビデオ データベースで非常に役立つとは思えません。また、データベースのサイズにより、クラウド コンピューティング リソースの使用が実現不可能になる可能性があります。そのため、1) データ ストレージ、2) コンピューティング リソース、3) 時間など、いくつかの異なるドメインでの各比較のローカル コストを非常に気にかけています。
考慮すべき重要なコストの 1 つは、使用する比較指標に関係なく、各ビデオから必要なデータを抽出するコストです。抽出されたデータが利用可能になったら、比較を実行するためのコストを考慮する必要があります。最後に、すべてのビデオを互いに一致させるために必要な比較を実行する必要があります。
最初の 2 つのステップのコストは、動画の数に対して O(1) です。最後のステップのコストは O(1) より悪くなければなりません。したがって、私たちの主な目標は、初期の単純なステップを多く追加することを意味する場合でも、最後のステップのコストを最小限に抑えることです。
このプロセスに最適なアルゴリズムは、データベースの特性、単一および複数の一致が存在するレベルに大きく依存します。動画の 100% が他の動画と一致する場合、一致の成功のコストを最小限に抑える必要があります。ただし、より可能性が高いのは、一致がまれになる可能性があるため、一致しない場合のコストを最小限に抑えることです。つまり、「これらの 2 つのビデオは一致するはずがない」という簡単で下品な言い方がある場合は、一致を確認する前に、まずそれを使用する必要があります。
データベースを特徴付けるには、まずサンプリングとハンド マッチングを行い、データベース内の一致度を推定します。この実験では、冗長な動画がどのように「凝集」したかを示す必要があります。特定の動画に一致があった場合、複数の一致があった可能性はどのくらいでしたか? 全試合の何パーセントが複数試合の一部でもありましたか? このプロセスにより、データベースの「モデル」(統計分布) が生成され、アルゴリズムの選択とシステムの調整に使用されます。
今後は、一致は比較的まれであると想定します。結局、多数の一致がある場合、ビデオは「凝集」し、事実上データベースが小さくなり、問題がより単純になります。問題が可能な限り難しいままであると仮定しましょう。
私は、「これらの 2 つのビデオは一致しない」/「これらの 2 つのビデオは一致する可能性がある」というバイナリ決定を繰り返し実行する一連のアルゴリズムを構築する、マルチレベルの分類アプローチを提唱します。チェーンの最後のアルゴリズムだけが、「これら 2 つのビデオが一致する」という回答を出力する必要があります。
分類/マッチング アルゴリズムは、次の 2 つの方法のいずれかまたは両方で失敗する可能性があります: 偽陽性 (一致しないビデオが一致すると誤ってラベル付けされる) および偽陰性 (一致するビデオが一致しないと誤ってラベル付けされる)。これらの誤った決定のそれぞれには、それに関連する確率の範囲があり、両方を最小限に抑えたいと考えています.
アルゴリズム パイプラインを構築しているので、エラーなしで不一致を識別するのに非常に優れたアルゴリズムが必要です。つまり、False Reject 率が非常に低くなければならず、False Accept 率はあまり気にしません。たとえば、Wierd Al の動画のクローンは、見た目も音声もオリジナルと非常によく似ている場合があり、アルゴリズム パイプラインの後半までオリジナルと一致しないことを示すことができない場合があります。
圧倒的多数のテストで「不一致」の結果が得られるため、最も単純で、最速で、最も信頼性の高いアルゴリズムを最初に実行する必要があります。最も単純なチェックは、データベース内で同一のファイルを検索することです。これは、多くの高速で単純なファイルシステムおよびデータベース メンテナンス ユーティリティによって行われます。このスキャンが実行された後、違いを検出するために実際にビデオ ファイルを開いて読み取る必要があると想定できます。
映像比較は割と難しいので、まずは音声から。データベースは、重複を含む可能性のある最初の MP3 コレクションであると考えてください。結局のところ、オーディオの一致が良好であれば、ビデオの一致が得られる可能性が非常に高く、その逆も同様です。オーディオはビデオの「公正な」代表であると言えます。幸いなことに、簡単な Web 検索で、信頼性が高く、高速で成熟した多くのオーディオ フィンガープリンティングおよび比較パッケージが見つかります。オーディオ フィンガープリントは、データベース内のすべてのビデオに対して生成する必要があります。オーディオ トラックがないビデオは、自動的に「一致する可能性がある」セットに分類されます。
しかし、ここに「落とし穴」があります。ナレーションについてはどうでしょうか。特定のビデオがナレーションありとナレーションなしで 2 回エンコードされている場合、それらは一致するかどうか? フランス語の音声とスペイン語または英語の音声はどうですか? これらがすべて一致していると見なされる場合は、オーディオ テストをスキップする必要があります。
この時点で、ファイルシステム エントリはすべて「十分に異なる」ことがわかり、オーディオ トラックもすべて「十分に異なる」ことがわかります (テストした場合)。幸いなことに、これはビデオ データベースのごく一部に対してのみ実行する必要があるため、多少のコストは許容できます。前と同じように、一致を肯定的にラベル付けする前に、最初に、より多くの不一致をすばやく排除しようとする必要があります。
解像度の変更を考慮する必要があるため (たとえば、1080p から iPod へ)、解像度に依存しないだけでなく、ビデオ情報の一部として追加されたノイズやデータの損失を許容できるビデオ情報を特徴付ける方法が必要になります。解像度を変更します。フレーム レートの変更を許容する必要があります (たとえば、映画の 24 fps からビデオの 30 fps へ)。また、4:3 NTSC から 16:9 HD へのアスペクト比の変更も考慮する必要があります。カラーからモノクロなど、色空間の変更を処理したいと考えています。
次に、HD と PAL の間のトランスコードなど、これらすべてに一度に影響を与える変換があり、色空間、フレームレート、アスペクト比、および解像度に同時に影響を与える可能性があります。キャラクタライゼーションは、4:3 と 16:9 の縦横比の間で行ったり来たりすることで発生するような、ある程度の切り取りや塗りつぶし (パン & スキャンではなくレターボックス化) に対しても許容する必要があります。長編映画の最後からクレジットを削除するなど、切り捨てられたビデオも処理する必要があります。そして、明らかに、同じビデオ ストリームが供給された異なるエンコーダーによって作成された違いも処理する必要があります。
それはかなりのリストです！考慮しないことを選択する可能性のあるいくつかのことを考えてみましょう: アナモフィック ワーピングが珍しくないという事実にもかかわらず、画像のワーピングが存在する場合、一致を見つけられなくても問題ないと思います。アナモフィック再構成なしでスキャンされます (背が高く痩せた人)。また、フレームの中央に大きな透かしが存在する場合は失敗することを選択することもありますが、隅にある小さな透かしは許容したいと考えています。最後に、一方が他方のスローモーションである場合や、左右に反転された場合など、時間的に歪んだり、空間的に反転されたビデオを一致させなくてもかまいません。
それはビデオスペースをほぼカバーしていますか？ファイルシステムとオーディオから始めることがなぜ重要なのか、お分かりいただけたと思います! つまり、ビデオ コレクションと見なす前に、まずデータベースを MP3 コレクションのように考えてください。
オーディオを無視すると、ビデオは静止画像の順序付けられたシーケンスにすぎません。したがって、実際には、1 つまたは複数の時系列比較アルゴリズムと組み合わせた 1 つまたは複数の画像比較アルゴリズムを探しています。これは、個別のアルゴリズムのペア (各フレームを特徴付けてから、フレームのシーケンスを特徴付けます) にするか、単一のアルゴリズムにマージする (フレーム間の違いを調べます) かのいずれかです。
画像自体は、モノクロの「構造」画像とカラーの「オーバーレイ」にさらに分解される場合があります。計算上都合がよければ、色情報を安全に無視できると思います。
以上のことから、比較を行うにはビデオを完全にデコードする必要があると想定しているように聞こえるかもしれません。必ずしもそうであるとは限りませんが、エンコードされたデータの比較には、その有用性を制限する多くの困難があります。これに対する 1 つの重要な例外は、MP4 などのオブジェクト レベルのビデオ エンコーディングで、非常に高レベルのマルチフレーム比較が実行されています。残念ながら、MP4 ストリーム間のオブジェクト比較はあまり研究されておらず、この機能を実行できるパッケージがないことを私は認識しています。でも見つけたら使ってね！
他のほとんどのデジタル ビデオ ストリームは、MPEG2、Quicktime などのエンコード方式を使用しています。これらのスキームはすべて、キー フレームと差分フレームの概念を使用していますが、実装方法はそれぞれ異なります。異なるビデオ (サイズが異なるビデオ) を比較する場合、キー フレームと差分フレームが有用な程度に一致する可能性はほとんどありません。ただし、これは不可能という意味ではなく、完全なデコードを実行せずにそのようなストリームから有用な情報を抽出しようとするパッケージが存在します。高速なものが見つかった場合は、「試してみない理由」のテスト カテゴリに分類される可能性があります。
私が使用する 1 つのトリックは、フレームを完全にデコードする代わりに、フレームを個別のコンポーネント チャネル (HSV、HSL、YUV など) にのみデコードし、RGB フレームバッファーまではデコードしません (もちろん、それがエンコードされている場合を除きます)。 ）。ここから、関連するドメインで比較を実行できるように、個別の輝度フレームとクロミナンス (色) フレームを作成します。RGB フレームバッファまでデコードするとエラーが発生し、一致を見つけるのが難しくなる場合があります。
次に、色情報を破棄します。モノクロのビデオは元のカラーと一致する必要があるため、色は気にしません。
得られたモノクロ フレームのシーケンスを、非常に異なるように見えても一致する可能性がある別のシーケンスと比較するにはどうすればよいでしょうか? この分野では文字通り何十年にもわたる研究が行われており、その多くは「スケール不変一致検出」に分類されています。残念ながら、ビデオが一致するかどうかを判断するために直接適用されたこの研究はほとんどありません。
私たちの目的のために、いくつかの方向からこの問題に取り組むことができます。まず、モノクロ領域で何が一致し、何が一致しないかを自分自身で知る必要があります。たとえば、ピクセル レベルの違いは気にしません。一致するが異なる 2 つのビデオの解像度が同じであっても、エンコーダの違いなどによるある程度のノイズを許容する必要があるためです。
簡単な (ただし遅い) 方法は、各画像を解像度と縦横比の両方に依存しない形式に変換することです。そのような変換の 1 つは空間周波数領域への変換であり、2D FFT はこれに最適です。虚数成分を破棄した後、実数成分を高周波で切り捨ててノイズを除去し、低周波でアスペクト比の影響を除去してから、標準スケールに正規化して解像度の違いを除去します。結果のデータは、ビデオ ストリーム間で直接比較できる奇妙な小さな画像のように見えます。
他にも多くの可能なフレーム変換戦略があり、その多くは FFT よりもはるかに効率的であり、文献検索でそれらを強調する必要があります。残念ながら、FFT と同じくらい使いやすいソフトウェア ライブラリに実装されているものはほとんどありません。
モノクロ フレームをより小さく、より有用なドメインに変換したら、別のビデオからの別のストリームとの比較を実行する必要があります。そして、そのビデオがフレーム間で一致しないことはほぼ確実であるため、単純な比較は確実に失敗します。追加/削除されたフレームやフレーム レートの違いなど、時間領域の違いを考慮した比較が必要です。
FFT フレームのシーケンスを見ると、いくつかの非常に明確な動作に気付くでしょう。シーンのフェードは急激で非常に見つけやすく、カットも区別できます。通常、カット間の FFT ではゆっくりとした変化しか見られません。一連の FFT から、各フレームをカット/フェード後の最初のフレームとして、またはカット/フェード間のフレームとしてラベル付けできます。重要なのは、各カット/フェード間の時間であり、それらの間のフレーム数とは無関係です。これにより、フレーム レートに大きく依存しないシグネチャまたはフィンガープリントが作成されます。
このビデオ全体のフィンガープリントを取得すると、ビデオ自体よりもはるかに小さいデータが生成されます。これはまた、オーディオによく似た単純な時系列ベクトルである数値の線形シーケンスであり、多くの同じツールを使用して分析できます。
最初のツールは、相関を実行して、あるビデオのカットのパターンが別のビデオのカットのパターンとほぼ一致しているかどうかを判断することです。大きな違いがある場合、ビデオは異なります。それらがほぼ一致する場合は、各相関カットの後の数個の FFT のみを比較して、フレームが一致するほど十分に類似しているかどうかを判断する必要があります。
ここでは 2D FFT の比較には立ち入りません。なぜなら、私よりもはるかに優れた仕事をしている参考文献が豊富にあるからです。
注: 追加のフィンガープリントを取得するためにモノクロ フレームに適用できる (2D FFT 以外の) 他の多くの操作があります。実際の画像コンテンツの表現は、画像の内部エッジを抽出する (文字通り FBI 指紋のようなもの) か、画像を選択的にしきい値処理して「ブロビング」操作を実行する (関連する領域記述子のリンクされたリストを作成する) ことによって作成できます。フレーム間のエッジやブロブの進化を追跡することは、カット リストを生成するためだけでなく、2D FFT を使用すると失われる追加の高レベルの画像特性を抽出するためにも使用できます。
非一致を非常に高速に検出し、最終的に一致を判断するのにあまり時間を必要としない一連の比較アルゴリズムを構築しました。残念ながら、アルゴリズムを持っていても解決策にはなりません! これらのアルゴリズムを最適に実装する方法に関連するいくつかの問題を考慮する必要があります。
まず、各ビデオ ファイルを必要以上に開いたり読み取ったりしたくありません。そうしないと、CPU がディスクからのデータを待機して停止する可能性があります。また、必要以上にファイルを読み取ることは望ましくありませんが、読み取りをすぐに停止して後の一致を見逃す可能性は避けたいと考えています。各ビデオを特徴付ける情報を保存する必要がありますか、それとも必要に応じて再計算する必要がありますか? これらの問題に対処することで、効率的で効果的なビデオ比較システムを開発、テスト、展開できるようになります。
私たちは、非常に変化しやすい条件の下で計算効率を上げて一致を見つけることを期待して、ビデオを比較することが可能であることを示しました。
残りは、読者の演習として残されています。;^)