にせねこメモ

はてなダイアリーがUTF-8じゃないので移ってきました。

Python+OpenCVでアニメのカット検出

はじめに

編集された映像のまとまりで一番細かい単位をカット(英語ではshot)という。カットがつなぎ合わされて一つの映像作品が作られている。
一般的にカットの切り替え時にはカメラの位置や撮影対象の位置関係が不連続になるため、画の大きな変化から目で見て判別のつく場合が多い。

なので、このカットの切り替えを、画の変化から(ある程度)自動で検出することができる。

手法

CG-ARTS協会『ディジタル画像処理[改訂新版]』に、カット検出について、次のように書かれている。

カット検出は,隣り合うフレーム間の画像の差分画像を用いて行うことができ,差の絶対値が大きいとき,その場所がカットであると判定すればよい。しかし,画面中に大きく動く物体がある場合も差の絶対値が大きくなり,カットと誤ることが多いため,精度を上げる工夫が必要である。画像をM×Nの格子(長方形領域)に区分し,長方形領域ごとの画素値の平均値を求め,その平均値の差の絶対値を用いてカットの判定を行う。16×16など比較的少ない格子数を用いることにより,物体の動きに影響されにくいカット検出ができる。

CG-ARTS協会『ディジタル画像処理[改訂新版]』(2015年) p.303

これに従って、フレーム間差分を用いてカット検出を行う。
まず、現在のフレームとそのひとつ前のフレームの差分画像を用意し、それに対してMSE (Mean Squared Error, 平均二乗誤差)やMAE (Mean Absolute Error, 平均絶対誤差)など指標となる値を計算する。その値が閾値以上であるならそのフレームでカットの切替が行われたと考える。

また、『ディジタル画像処理[改訂新版]』では精度を上げる工夫として、元画像を縮小したものに対してカット判定するという手法が紹介されているので、これについても検討する。

カット検出コードの例

Python 3.5.3, OpenCV 3.1.0, NumPy 1.13.1 (Anaconda, Windows 10 64-bit)で動作。

評価

評価するのは結構面倒である。false-positiveはカットとして検出した画像がダブってるのをみれば大体わかるが、false-negativeは検出結果からはわからない。なので、映像に対するカット切り替えタイミングの正解データを用意しておいて、それと対照して正解不正解を確認するというのが妥当だと思う。正解データは手で用意する必要がある。

ここで、ワイプやディゾルブといったカット同士の切り替えがなめらかに行われる場合、はっきりどのフレームで切り替わったということが言えないため、うまい評価法が思いつかなかった。なので、それらについては評価から除外し、カットの切替と検出されてもされなくても同じ評価になるようにした。


閾値以上の値をもつフレームをカットだと判定することから、検証にはthreshold(閾値)を変化させて、その閾値に関してprecision (精度, 適合率)とrecall (再現率)を計算した。

precisionは、カットの切れ目だ!と予測した中で実際に正しくカットの切れ目を判定できていた割合で、
 \displaystyle
P = \frac{\mbox{予測のうち正しかった数}}{\mbox{予測した総数}}
で表される。

recallは、実際に動画の中に存在するカットの切れ目をどれだけ網羅して判定できたかという割合で、
 \displaystyle
R = \frac{\mbox{予測のうち正しかった数}}{\mbox{正解の総数}}
で表される。

ここで、例えば動画全体を通してカットの切れ目を1つしか予測せず、それが正解だった場合precisionは1になるが、動画全体のほとんどのカットの切れ目を取りこぼしているためにrecallは0に近い値になる。
また、逆に全てのフレームをカットの切れ目だと判定する場合、precisionは0に近い値をとるが、recallは1になる。
このように、予測の良さを計るにはprecisionもrecallも単体ではあまり適さないと考えられるため、F-measure (F値)という尺度を導入して指標とする。

F-measureは、precisionとrecallの調和平均である。
 \displaystyle
F = \frac{2PR}{P+R}
これはprecisionとrecallのどちらもが高い値を持つ場合に高くなり、いい感じに評価に使えそうである。高いほど(1に近いほど)性能がよい。

さて、評価用に動画を用意した。会話中心で動きの少ない日常系と、激しいアクションがあるものの2種類のつもり。

各動画はCM等が含まれず、本編映像のみのものである。
これらに対し、カットの切り替わりタイミングのリストを作成した。各ファイルへのリンクを次に挙げる。

実際にはフレーム番号で計算したが、動画プレーヤでの確認のしやすさから時間表記(分:秒.ミリ秒)に直している。
カットの切り替わりタイミングを各行記載した。また、行末に"?"がついているものはカット検出の評価から除外する部分であり、ディゾルブなどで切り替わりに幅があるものについては"-"で繋いで範囲を示した。

評価結果1: ごちうさ

ご注文はうさぎですか?』1話について、いくつかの画像サイズで前フレームとのMSEとMAEを計算し、thresholdに対する検出性能の指標を計算し、グラフを描いた。

1280x720 MSE

f:id:nixeneko:20170903033850p:plain

Max F-measure 0.8344370860927152
Threshold 6947.407446108217
1280x720 MAE

f:id:nixeneko:20170903033858p:plain

Max F-measure 0.9038461538461539
Threshold 55.61545464409722
640x360 MSE

f:id:nixeneko:20170904213100p:plain

Max F-measure 0.8344370860927152
Threshold 6904.933479456018
640x360 MAE

f:id:nixeneko:20170904213115p:plain

Max F-measure 0.9020866773675763
Threshold 55.55679398148148
128x72 MSE

f:id:nixeneko:20170903033732p:plain

Max F-measure 0.8344370860927152
Threshold 6904.933479456018
128x72 MAE

f:id:nixeneko:20170903033756p:plain

Max F-measure 0.9020866773675763
Threshold 55.55679398148148
64x36 MSE

f:id:nixeneko:20170904213140p:plain

Max F-measure 0.8344370860927152
Threshold 6904.933479456018
64x36 MAE

f:id:nixeneko:20170904213148p:plain

Max F-measure 0.9020866773675763
Threshold 55.55679398148148
32x18 MSE

f:id:nixeneko:20170903033808p:plain

Max F-measure 0.8308207705192631
Threshold 5792.83275462963
32x18 MAE

f:id:nixeneko:20170903033816p:plain

Max F-measure 0.888888888888889
Threshold 48.49363425925926
16x9 MSE

f:id:nixeneko:20170903033827p:plain

Max F-measure 0.8264462809917356
Threshold 4685.99537037037
16x9 MAE

f:id:nixeneko:20170903033837p:plain

Max F-measure 0.8803827751196172
Threshold 44.44675925925926
F-measure最大値まとめ

まとめると次のようになる(数値の小数点以下桁数は適当)。

尺度 size max F-measure threshold
MSE 1280x720 0.8344 6947.4
MSE 640x360 0.8344 6904.9
MSE 128x72 0.8344 6904.9
MSE 64x36 0.8344 6904.9
MSE 32x18 0.8308 5792.8
MSE 16x9 0.8264 4686.0
MAE 1280x720 0.9039 55.6
MAE 640x360 0.9021 55.6
MAE 128x72 0.9021 55.6
MAE 64x36 0.9021 55.6
MAE 32x18 0.8889 48.5
MAE 16x9 0.8804 44.4

評価結果2: フリップフラッパーズ2話

フリップフラッパーズ』2話について、いくつかの画像サイズで前フレームとのMSEとMAEを計算し、thresholdに対する検出性能の指標を計算し、グラフを描いた。

1280x720 MSE

f:id:nixeneko:20170904213740p:plain

Max F-measure 0.7517401392111369
Threshold 4725.544186559607
1280x720 MAE

f:id:nixeneko:20170904213750p:plain

Max F-measure 0.8178528347406515
Threshold 49.28785517939815
640x360 MSE

f:id:nixeneko:20170904213759p:plain

Max F-measure 0.7522123893805309
Threshold 4287.165564236111
640x360 MAE

f:id:nixeneko:20170904213810p:plain

Max F-measure 0.8178528347406515
Threshold 49.19312789351852
256x144 MSE

f:id:nixeneko:20170904214121p:plain

Max F-measure 0.7552140504939626
Threshold 4102.424325448495
256x144 MAE

f:id:nixeneko:20170904214112p:plain

Max F-measure 0.8183962264150942
Threshold 47.06980613425926
128x72 MSE

f:id:nixeneko:20170904213833p:plain

Max F-measure 0.7603485838779955
Threshold 3877.8117042824074
128x72 MAE

f:id:nixeneko:20170904213842p:plain

Max F-measure 0.820754716981132
Threshold 46.62550636574074
64x36 MSE

f:id:nixeneko:20170904214100p:plain

Max F-measure 0.7656249999999999
Threshold 3832.808449074074
64x36 MAE

f:id:nixeneko:20170904214051p:plain

Max F-measure 0.8232502965599051
Threshold 46.094907407407405
32x18 MSE

f:id:nixeneko:20170904213856p:plain

Max F-measure 0.7734553775743707
Threshold 3645.484953703704
32x18 MAE

f:id:nixeneko:20170904213907p:plain

Max F-measure 0.8177570093457943
Threshold 43.302083333333336
16x9 MSE

f:id:nixeneko:20170904213922p:plain

Max F-measure 0.7842227378190255
Threshold 3205.7291666666665
16x9 MAE

f:id:nixeneko:20170904213931p:plain

Max F-measure 0.8189349112426034
Threshold 41.75231481481482
F-measure最大値まとめ

まとめると次のようになる(数値の小数点以下桁数は適当)。

尺度 size max F-measure threshold
MSE 1280x720 0.7517 4725.5
MSE 640x360 0.7522 4287.2
MSE 256x144 0.7552 4102.4
MSE 128x72 0.7603 3877.8
MSE 64x36 0.7656 3832.8
MSE 32x18 0.7734 3645.5
MSE 16x9 0.7842 3205.7
MAE 1280x720 0.8179 49.3
MAE 640x360 0.8179 49.2
MAE 256x144 0.8184 47.1
MAE 128x72 0.8208 46.6
MAE 64x36 0.8233 46.1
MAE 32x18 0.8178 43.3
MAE 16x9 0.8189 41.8

考察

  • 全体的にごちうさの方がフリップフラッパーズより検出性能がよい。これは、フリップフラッパーズには激しいアクションが多く、それが誤判定されがちだということが考えられる。
  • MSEよりMAEの方が検出性能がよい。
    • 画素値を[0.0, 1.0]の範囲にスケーリングしたらまた変わるのだろうか。
  • 差分画像を計算するサイズは64x36程度が一番良いようだ。
    • 差分画像はごちうさでは1280x720が最高で次に256x144, 128x72, 64x36が同じ性能で続き、解像度が大きいほど(原サイズに近いほど)性能が良いようにも見えるが、フリップフラッパーズでは64x36のパフォーマンスが一番高かった。
    • ある程度縮小することで計算速度を速くすることができる。
  • 64x36でMAEを計算した場合、最大のF-measureをたたき出したthresholdは、ごちうさ55.6、フリップフラッパーズ46.1程度とそれなりの開きがある。このため、一つのthresholdが任意の動画に対して最高の性能を出すということはない。

前のフレーム一つと比較しただけでは繋がった一続きのカットであるかどうかの判定が難しいものが必ず出てくるため、そういうものに対しても正しく判定するためには、過去や未来のフレームも参考にカット判定をしないといけないが、計算コストも高くなるということもあり、実用上そこまで重要でないような気がする。

例えば、動画エンコードで、カットの切り替わりが検出されたところをIフレームとしたい時などの場合、カットという切れ目よりは画面が大きく動いたことの方が重要であると考えられ、今回のような検出手法でも効果を発揮すると思う。

まとめ

ごちうさ1話とフリップフラッパーズ2話について検討した結果、差分画像を計算してカット検出を行うには、

  • 元画像を64x36程度に縮小
  • 尺度にMAEを用いる
  • 閾値は45~55程度(動画によって最適なものは異なる)

とするとよさそうで、0.8~0.9程度の最大F-measureが達成できるようである。
とはいえ、2つの動画作品に対してしか検証していないので、どこまで一般化できるかはわからない。

応用例: 映像のダイジェスト作成

カットの切り替わりが検出できるのであるから、カットごとに一つの画像を取り出すことで、映像のダイジェストを作成することができる。
f:id:nixeneko:20170904225533p:plain
見るとわかるが、画面のなかの大きな部分が動いたり色が変わる場面では誤検出が起きている。

他に試す価値があるかもしれないもの

  • ヒストグラムを利用したカット検出
  • SURF, ORBなどの画像特徴量の利用

*1:ウサ耳の生えたココナちゃんが齧歯類特有の前歯を削るために硬い構造物に齧りつき、唾液の糸が引くシーン、最高です。あと、色彩設計的にもポップで楽しい回。