转载

记一个小工具：实现聊天记录/朋友圈截图的自动拼接

最近做了一个截图拼接的小玩具，实现聊天记录/朋友圈截图的自动拼接，感觉还是比较有趣，所以记上一笔和大家分享。

缘起

经常有这样的场景：需要将微信的聊天记录/网页转发给其他人，内容很长，所以不得不一段一段地截图发送，麻烦又常有乱序送达的情况发生。于是在 App Store 上找了款自动拼接截图的 App ( 截图拼接 )，很是好用，却有一天只能保存一次的限制。于是自己写了一个玩，花了一天写算法验证可行性，又花了一天将界面和流程整理好，比那个 App 快上数倍，很是满足。不过想想 2 天的工资怎么也超过那个 App 的价格了...

实现

要实现两张截图的自动拼接，首要问题是找到它们的重复内容。简单粗暴的想法就是对两张图片进行逐行扫描并比较每一行的像素点以确定当前行是否匹配，然后找出连续匹配的最大行数即可。但简单推演一下，iPhone 6 的截图分辨率为750 * 1334,进行上述操作至少需要上万亿的匹配，计算量和效率可想而知。所以需要些小技巧减少计算量。

提取图片指纹

对于判断图片任意两行是否一致来说，行内每个像素点信息其实并没有什么意义，我们更关注的是整行的数据信息。一张宽为 750 的图片，每行都有 3KB 字节数据，逐一比对显然数据量过大。所以第一步就是将行数据进行"压缩"，用比较高大上的词来说就是“提取图片指纹”。最简单的方式是计算这一片数据的 MD5。这种方式既可以将 3KB 的数据压缩至几十个字节，又可以保证唯一性。

然而这种强哈希的做法有两个弊端：

计算量大
结果表现是形式为字符串，不利于下一步比较

所以最终选择使用 CRC 这种弱哈希的方式来作为提取图片指纹的方式。一方面计算快，另一方面得到的结果为数字，有利于加快后续的匹配速度。而弱哈希带来的冲突问题则可以忽略不计：最终匹配时需要找出连续相同的行数据，使得偶现的冲突对整个匹配结果正确性影响微乎其微。

匹配图片指纹

使用 CRC 提取图片指纹后，能方便地将一张 iPhone 6的截图转换为 1334 个 unsigned long 的数字集合，整个问题就简化为寻找两个串内的公共子串。简单粗暴的方法是直接遍历每一行，在某两行匹配的情况下继续比较下两行，直到找到最大匹配项集合。最差情况下时间复杂度为 O(n^4) ,这是理论上不可接受的时间复杂度。但是在实际测试中，由于图片指纹的特殊性，使得匹配速度并没有想象中的那么差，两张 iPhone 6的图片指纹匹配大约需要 100 到 500 ms之间。

一种改进的方式是使用动态规划，用空间换时间。假设图 1 高为 m，图 2 高为 n，图 1 的第 i 行与图 2 的 j 行内容一致，用 c[i,j] 表示以 i,j 行作为结尾的最长公共子串长度，则有： c[i,j] = c[i-1,j-1] + 1 。基于这个原理，我们建立一个 m * n 的二维数组，只需要一次遍历就可以找出最大子串，复杂度为 O(n^2) 。使用这种方法，两张 iPhone 6 图片指纹匹配只需要 10 到 50 ms。

多图拼接

对于两张图而言，一旦找到最大相同行，只需要将两张图分别切割成上图上部分，共同部分和下图下部分进行拼接即可。但是如果有多张图，情形则复杂得多，相邻两对图的相同部分可能有如下三种情况：包含，相交，不相交。这使得预先计算多图拼接后的图片大小和各个图的裁剪区域变得极其复杂和困难。(如果有什么好的方法可以直接计算出对应关系，请告诉我)

所以在我的实现里使用了递归的方式来实现。这个地方有个小 trick，当前面两张图片合并为一张新图后，由于新图大小发生变化，导致后续两张图匹配行数也发生偏移，需要重新调整。但是考虑到所有的图片都是从上往下进行拼接，所以在匹配时直接使用距底部距离作为偏移值，这样就避免了合并后的图片需要重新计算匹配行偏移的情况。

效果

效果还是不错的，天衣无缝：

记一个小工具：实现聊天记录/朋友圈截图的自动拼接

可改进的点

动态规划在超长图合并时申请的内存数可能会超过几十兆，但实际进行比较时其实只需要记录上一行数据和最大值即可，所以并不需要申请 m * n 的二维数组，只需要 2 * n 大小的二维数组即可。(=。= 懒得改了)
对于非静态的内容匹配会失败，如聊天内容中带有会动的表情。能够想到的方法是使用类似 SIFT 或者 SURF 之类的算法计算出相应的 Interesting Point 并配合前面的算法进行匹配，但这种方法难度太高，可行性也不高。