根据视频生成可以头尾衔接的循环视频

最近手头有一个视频，基本上是一个部分重复循环的，我想把循环的一段提取出来造成动态壁纸，但怎奈何不会用 pr，只能用 ffmpeg 配合 pillow 搞了……

实现的关键在于找到可以首位相接的两帧画面，这就要求两个画面有极高的相似度。判断画面相似度首先需要对图像进行量化，一般有两种方案，一种是提取特征向量，一种是计算哈希。考虑到我手头视频的特征，我选择了比较简单的哈希。

开始之前，需要安装必要的包以及 ffmpeg，执行

pip install ffmpeg-python Pillow numpy imagehash

!Notice 简略起见，以下代码不重要部分折叠，具体实现参照文末链接

首先需要把视频分离成帧，存入数组：

def extract_frames(input_video) -> Generator[np.ndarray, None, None]:
    # 一个生成器，生成每一帧的数据存入 numpy 数组
    ...

图像的哈希算法有多种，比如均值哈希（aHash）、感知哈希（pHash）以及差异哈希（dHash），各有优劣，但选择哪一种对接下来的算法影响不大，我这里以 pHash 为例。以上图像哈希算法在 imagehash 中均有提供，由于本篇主要讨论循环视频生成，哈希算法的具体原理就不研究了（肯定不是因为我不会）。

def generate_hashes(input_video: str) -> Generator[int, None, None]:
    for frame in extract_frames(input_video):
        # 将 numpy 数组转换为 PIL 图像
        pil_image: ImageHash = Image.fromarray(frame)

        # 生成 pHash 值
        phash_value = int(str(phash(pil_image)), 16)

        yield phash_value

图像哈希越相似，图像就越相似。两个哈希值的相似度可以用汉明距离表示，汉明距离表两个二进制数差异的位数，可以通过异或和中 \(1\) 的个数计算。

def hamming_distance(hash1: int, hash2: int) -> int:
    return bin(hash1 ^ hash2).count('1')

接下来遍历每一帧的哈希找到距离最近的两帧即可。遍历过程如果有确定起始或结束帧可以直接遍历，复杂度 \(\mathcal{O}(n)\)；如果没有固定起始帧，根据汉明权重（也就是与 \(0\) 的汉明距离）排序后遍历即可，复杂度 \(\mathcal{O}(n\log n)\)。

最后完整代码在github gist。