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

# はじめに

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

# TL;DR

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

## 前提条件

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

## 実装

画像パターン検出には **[sharp](https://www.npmjs.com/package/sharp)** を使っています。
ループが検出できなかったら `null` を返します。

```ts
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;
}
```

# 解説

## 画像パターン検出

```ts
  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しといてよかった。

```ts
  //ループ検出
  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)**

# さいごに

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