連番画像からループ部分を抜き出す / パターン配列からループ部分を抜き出す

はじめに

タイトルの通りですが、連番画像からループ部分を取り出す必要があり、軽く検索したくらいでは望みの参考文献が出てこなかったので、メモします。

TL;DR

記述は TypeScript ですが、考え方はどの言語でも共通で使えると思います。

前提条件

• 画像やパターンは毎ループ完全一致する事(ゆらぎ許容度0)
• ループは2回以上繰り返している事

実装

画像パターン検出には sharp を使っています。
ループが検出できなかったら null を返します。

import sharp from "sharp";

export async function detectLoop(
  files: string[]
): Promise<{
  start: number;
  end: number;
} | null> {
  // 画像パターン検出
  const pattern: number[] = [];
  const buffers: Buffer[] = [];
  main: for (const file of files) {
    const b = await sharp(file).raw().toBuffer();
    for (let i = 0; i < buffers.length; i++) {
      if (buffers[i].equals(b)) {
        pattern.push(i);
        continue main;
      }
    }
    buffers.push(b);
    pattern.push(buffers.length - 1);
  }

  //ループ検出
  for (
    let loopStartIndex = 0;
    loopStartIndex < pattern.length;
    loopStartIndex++
  ) {
    length: for (
      let loopFrameLength = 2;
      loopFrameLength < pattern.length / 2;
      loopFrameLength++
    ) {
      for (
        let checkIndex = loopStartIndex + loopFrameLength;
        checkIndex < pattern.length;
        checkIndex++
      ) {
        const org =
          ((checkIndex - loopStartIndex) % loopFrameLength) + loopStartIndex;
        if (pattern[org] !== pattern[checkIndex]) continue length;
      }
      return {
        start: loopStartIndex,
        end: loopStartIndex + loopFrameLength - 1
      };
    }
  }
  return null;
}

解説

画像パターン検出

  const pattern: number[] = []; // A
  const buffers: Buffer[] = []; // B
  main: for (const file of files) {
    const b = await sharp(file).raw().toBuffer(); // C
    for (let i = 0; i < buffers.length; i++) {
      if (buffers[i].equals(b)) { // D
        pattern.push(i);
        continue main;
      }
    }
    // E
    buffers.push(b);
    pattern.push(buffers.length - 1);
  }

まずパターン配列を用意します。(A/B)
配列が2種類ありますが、A が後でループ検出に使用するパターン配列、 B が画像の一致判定に使う Buffer の配列です。実際には B だけでも成立するのですが、処理が重くなりそうなので B を使ってパターン判別をした後、パターン番号を A に格納するという方法を採っています。

C で画像の Buffer を取得した後 D で今までに取得した Buffer と比較し、一致するものがあればインデックスをパターン番号として記録して次のループに進みます。
(全く同じ画像だった場合、buffers[i].equals(b) が true を返します。)

もし今までにない Buffer だった場合は、 E に進んで Buffer を登録し、最後のインデックスをその画像のパターン番号として記録します。

これで画像のパターンリスト (A) が出来ました。

ループ検出

どうやってループを検出するか？

基本的には力業です。
例えば先程作ったパターン配列の中身が以下のようなものだったとしましょう。

000111222333000111222333000111222333

総当たりでチェックする

(1)
000111222333000111222333000111222333
**
--1×

(2)
000111222333000111222333000111222333
***
---×

(3)
000111222333000111222333000111222333
****
----×

…省略

(n)
000111222333000111222333000111222333
************
------------●●●●●●●●●●●●●●●●●●●●●●●●

ちょっと分かりにくいですが…
***(アスタリスク)**で表されているのがチェックするパターン、その下にあるのが合否判定です。チェックするパターンの長さを1つずつ変えて判定していっています。
(1)は最初の1つだけ合致していますが、その次で失格。(2)(3)は、最初から合致していません。これを繰り返していき、最後まで失格しなかったパターンをループとして判定します。

開始点をずらす

では、次は以下のようなパターンだったとしましょう。

00000111222333000111222333000111222333

基本的には同じパターンですが、最初に余計な 00 が入ってしまっています。
このように、例えば「映像を手動でキャプチャした」等で 最初のパターンがループの開始点ではない可能性があります。
この場合、ループが成立せず検出が不可能になってしまいます。

これを回避するため、 ループ開始点をずらしたパターンもチェックします。

00000111222333000111222333000111222333
*************************************
-------------------------------------×

[↑全パターン失格したので次へ]

00000111222333000111222333000111222333
 **
 --●×

…省略

00000111222333000111222333000111222333
  ***********
  -----------●●●●●●●●●●●●●●●●●●●●●●●●●

制約「ループは2回以上繰り返している事」について

最後に以下のようなパターンを想定してみます。

0000011122233300011122233300011122233300

前項のサンプルに加えて、パターンの最後がループの最後ではないケースです。
この場合、今回の「最後まで失格しなかったらループとみなす」ロジックだと 「長いパターンを持ち、配列内に1つしか現れないループ」 として検出されてしまいます。

0000011122233300011122233300011122233300
**************************************
--------------------------------------●●

そのため、今回のロジックでは制約として ループは2回以上繰り返している事が必要 なのです。

実際のコード

やっとここに来ました。最初にTL:DRしといてよかった。

  //ループ検出
  for ( // A
    let loopStartIndex = 0;
    loopStartIndex < pattern.length;
    loopStartIndex++
  ) {
    length: for ( // B
      let loopFrameLength = 2;
      loopFrameLength < pattern.length / 2;
      loopFrameLength++
    ) {
      for ( // C
        let checkIndex = loopStartIndex + loopFrameLength;
        checkIndex < pattern.length;
        checkIndex++
      ) {
        const org =
          ((checkIndex - loopStartIndex) % loopFrameLength) + loopStartIndex;
        if (pattern[org] !== pattern[checkIndex]) continue length; //D
      }
      // E
      return {
        start: loopStartIndex,
        end: loopStartIndex + loopFrameLength - 1
      };
    }
  }
  return null; //F

• A -- 開始点をずらす
• B -- チェックするパターンの長さを変える
• C -- 実際にループの中身をチェックする

という流れになっています。
B の繰り返しが pattern.length / 2 になっているのは、「ループは2回以上繰り返している事」 を満たすためです。配列の半分の長さまでチェックして合格しなかったら、そのパターンは失格とみなします。

D は失格ルートなので、B に戻ってやり直します。失格しなかった場合は E に入り、ループ情報を返します。
E に入らずに全ループが終了したという事はループ検出が出来なかったという事なので、今回は null を返します。(F)

さいごに

ちょっとループ検出ロジックの説明が分かりにくかったかもしれませんね…
僕が想定できていないケースで不具合があるかもしれませんが、とりあえず今回僕が使用したケースではこのロジックでうまく検出できました。
同じような事で参考を探している方のお役に立てれば幸いです。