２つの動画の類似度を求める

ググっても意外と出てこなかったので、シンプルな実装をログ。より効率的なアルゴリズム、高パフォーマンスな方法が他にあることは明らかなので、見つけ次第追記していければと思う。

実験用リポジトリは以下。

github.com

画像の類似度

動画はただの画像の連続なので、基本的な仕組みは画像の場合と同じ。以下の記事が非常にわかりやすくて面白い。

qiita.com

Perceptual Hashを使っている。

動画の類似度

では、何が違い、何が問題となるのか？

動画間の比較は、言い換えると「時系列関係を持った画像集合間の比較」なので、主な違いとしては、単体の比較か？集合の比較か？だと思う。

また、大きく問題になってくるのは、特に「動画間のフレーム数が異なる」点だと考えられる。例として

• FPS が違う
• 前後に異なるフレームがある
  • トリミング
  • 広告の挿入など
• コマ落ち

等によって、時系列情報に違いが出得る。

よって、２つの動画を先頭から全フレーム比較するのは現実的ではない。

そこで、次のようなシンプルなアルゴリズムを考える。

1. ある動画をオリジナル動画、その動画を含んだ動画をターゲット動画とする
2. オリジナル動画の始点終点ランダムN点においてフレームをハッシュ化する
3. ターゲット動画の全フレームをハッシュ化する
4. オリジナル動画のハッシュとターゲット動画のハッシュで最もハミング距離の近いものを線形探索する
   • この時、オリジナル動画のハッシュiとターゲット動画のハッシュjをペアとして用いた場合、i+1のペアはk(k<j)となる
   • つまり時系列を加味する
5. 求めたハミング距離を配列として保存
6. 求めたハミング距離配列の平均を求める
7. (64 - 平均)/64 をスコアとする
   • ハミング距離の最大値が 64 なので
   • スコアの範囲は 0.0 ~ 1.0 だが確率ではない

これで動画の類似度を取れる。実際、実験コードではいい感じに類似度が取れている。

このアルゴリズムの問題点として、線形探索なのでオーダーが高い。

解決策としては、時系列情報を持った異なる長さのデータの比較をする最適なアルゴリズムを使うことだが、私の浅いバックグラウンドでは見つけられなかったので、今後調査したい。

以下に、このアルゴリズムのイメージ図を載せておく。