記事の目的

前回はOpenCVを導入したので、今回は切り出しに使った考え方、アルゴリズムを説明する。

仕様

今回扱うゲームは基地運営系のサンドボックス・シミュレーションゲームで、複雑な物理法則に基づいている性質上、シミュレーションの時間を止めて次の作業を考える時間が結構長い。
そのため時間が流れていない部分をすべてカットする編集を行おうと考えている。

最終的な編集ソフトが「指定範囲のフレームを削除する」機能があるAviutlのため、動画を読み込み、カット編集対象となるフレーム範囲を出力する機能を作成する。

判別メカニズム

ゲーム中はほぼ必ず、画面左上の固定された場所にゲームスピードを調整するためのUIが表示されている。
下記のような内訳だ。

今回はUIの位置が完全に固定されているため、パターンマッチやその他時間がかかる方法は使わずに、基準となる絵からの差分を取ってそれが一定以上の差かどうかを判定させる。
UI部分だけ差分をとってみると、次のような感じになる。
(一時停止を解除しているUIとの差分をとった)

一時停止されていない状態を基準のフレームとして、UI部分に一定以上の差があればカット編集対象とする。
そうすればシステムメニューを出しているときやタイトル画面も対象外になってちょっとお得だ。

具体的には、下のような単純な関数の戻り値が基準以上かどうかで振り分けていた。
今になって思えば出力されたスカラの値は足し合わせてdouble型を戻り値にしても問題なかった気がする。


        /// <summary>
        /// 対象フレームと現在のフレームの間の差分を取る
        /// </summary>
        /// <param name="frame"></param>
        /// <returns></returns>
        private int GetFrameDiffPoint(int frame)
        {
            Mat diffMat = GetTargetFrameMat(frame).SubMat(startY, endY, startX, endX);
            Mat absmat = (diffBaseMat - diffMat).Abs();
            return (int)getScalarMean(absmat.Mean());
        }

        private double getScalarMean(Scalar sc)
        {
            return (sc.Val0 + sc.Val1 + sc.Val2) / 3;
        }

計算軽量化

単純に考えればすべてのフレームを切り出し対象かどうか判別しなければいけないが、ゲームと操作の都合上、ポーズやポーズ解除は短い期間で連続して行うことはない。
つまり、ポーズしてるフレームと解除してるフレームの境界は、数秒は離れていることが保証されている。

上記のような考え方なら、境界を抜き出すためにはまず一定フレームおきにカット対象かどうかを調査して、ちょっと前のフレームからカット対象かどうかが切り替わったらその周辺を念入りに探索すれば、カット対象の範囲は比較的早く見つけることができる。
コードで表現するならこんな感じ。


// カット対象を出力するための変数
SkipFrameResult = new List<MatchedFramePair>();

int framePointer = 0;
int lastCutStartFrame = 0;

bool lastFrame = FrameIsMatch(framePointer);
bool nextFrame = false;

// MaxSkipFrames：チェックする間隔
// Frames：動画の最終フレーム
int nextFramePointer = Math.Min(framePointer + MaxSkipFrames, Frames);

while(framePointer < Frames)
{
    // 次の切り出しフレームまでに値が変更になっているかチェック
    nextFrame = FrameIsMatch(nextFramePointer);
    if (lastFrame != nextFrame)
    {
        if (lastFrame)
        {
            // カット対象→非カット対象の境界フレームを検索
            MatchedFramePair pair = new MatchedFramePair(lastCutStartFrame, GetFrameBeforeChange(framePointer, nextFramePointer, lastFrame));
            SkipFrameResult.Add(pair);
        }
        else
        {
            // 非カット対象→カット対象の境界フレームを検索
            lastCutStartFrame = GetFrameBeforeChange(framePointer, nextFramePointer, lastFrame) + 1;
        }
    }

    // 次の切り出しフレームの準備
    lastFrame = nextFrame;
    framePointer = nextFramePointer;
    nextFramePointer = Math.Min(framePointer + MaxSkipFrames, Frames);
}

// 最後切り出しで終わってたときの判定は行うこと。
if (lastFrame)
{
    SkipFrameResult.Add(new MatchedFramePair(lastCutStartFrame, Frames));
}

画像で表現するならこんな感じ。

境界の位置がふんわりと絞り込めれば、そこからは二分探索を使えば効率よく見つけることができる。
参考：二分探索アルゴリズムを一般化〜めぐる式二分探索法のススメ〜

この考えをうまく使えば、フレーム数をN、チェックする間隔をMと置くと、チェックに必要な計算量はO(N)からO(NlogM/M)へと大幅に減ったことになる。
自分の場合、1時間の動画の中に10回ポーズがあるかどうかのレベルなので、実際の計算量はO(N/M)に限りなく等しい。

切り出しは完成した。あとはこれをUIに落とし込むだけだ。
次回に続く。