https://github.com/xiangwangfeng/M80ImageMerger
緣起
經(jīng)常有這樣的場(chǎng)景：需要將微信的聊天記錄 / 網(wǎng)頁(yè)轉(zhuǎn)發(fā)給其他人翠拣，內(nèi)容很長(zhǎng)统阿，所以不得不一段一段地截圖發(fā)送，麻煩又常有亂序送達(dá)的情況發(fā)生炮姨。于是在 App Store 上找了款自動(dòng)拼接截圖的 App (截圖拼接)楚昭，很是好用，卻有一天只能保存一次的限制茂附。于是自己寫了一個(gè)玩正蛙，花了一天寫算法驗(yàn)證可行性，又花了一天將界面和流程整理好营曼，比那個(gè) App 快上數(shù)倍乒验，很是滿足。不過(guò)想想 2 天的工資怎么也超過(guò)那個(gè) App 的價(jià)格了…
實(shí)現(xiàn)
要實(shí)現(xiàn)兩張截圖的自動(dòng)拼接蒂阱，首要問(wèn)題是找到它們的重復(fù)內(nèi)容锻全。簡(jiǎn)單粗暴的想法就是對(duì)兩張圖片進(jìn)行逐行掃描并比較每一行的像素點(diǎn)以確定當(dāng)前行是否匹配，然后找出連續(xù)匹配的最大行數(shù)即可蒜危。但簡(jiǎn)單推演一下虱痕，iPhone 6 的截圖分辨率為 750 * 1334, 進(jìn)行上述操作至少需要上萬(wàn)億的匹配，計(jì)算量和效率可想而知辐赞。所以需要些小技巧減少計(jì)算量部翘。
提取圖片指紋
對(duì)于判斷圖片任意兩行是否一致來(lái)說(shuō)，行內(nèi)每個(gè)像素點(diǎn)信息其實(shí)并沒(méi)有什么意義响委，我們更關(guān)注的是整行的數(shù)據(jù)信息新思。一張寬為 750 的圖片，每行都有 3KB 字節(jié)數(shù)據(jù)赘风，逐一比對(duì)顯然數(shù)據(jù)量過(guò)大夹囚。所以第一步就是將行數(shù)據(jù)進(jìn)行 “壓縮”，用比較高大上的詞來(lái)說(shuō)就是 “提取圖片指紋”邀窃。最簡(jiǎn)單的方式是計(jì)算這一片數(shù)據(jù)的 MD5荸哟。這種方式既可以將 3KB 的數(shù)據(jù)壓縮至幾十個(gè)字節(jié)假哎，又可以保證唯一性。
然而這種強(qiáng)哈希的做法有兩個(gè)弊端：
計(jì)算量大
結(jié)果表現(xiàn)是形式為字符串鞍历，不利于下一步比較
所以最終選擇使用 CRC 這種弱哈希的方式來(lái)作為提取圖片指紋的方式舵抹。一方面計(jì)算快，另一方面得到的結(jié)果為數(shù)字劣砍，有利于加快后續(xù)的匹配速度惧蛹。而弱哈希帶來(lái)的沖突問(wèn)題則可以忽略不計(jì)：最終匹配時(shí)需要找出連續(xù)相同的行數(shù)據(jù)，使得偶現(xiàn)的沖突對(duì)整個(gè)匹配結(jié)果正確性影響微乎其微刑枝。
匹配圖片指紋
使用 CRC 提取圖片指紋后香嗓，能方便地將一張 iPhone 6 的截圖轉(zhuǎn)換為 1334 個(gè) unsigned long 的數(shù)字集合，整個(gè)問(wèn)題就簡(jiǎn)化為尋找兩個(gè)串內(nèi)的公共子串装畅。簡(jiǎn)單粗暴的方法是直接遍歷每一行靠娱，在某兩行匹配的情況下繼續(xù)比較下兩行，直到找到最大匹配項(xiàng)集合洁灵。最差情況下時(shí)間復(fù)雜度為 O(n^4), 這是理論上不可接受的時(shí)間復(fù)雜度饱岸。但是在實(shí)際測(cè)試中，由于圖片指紋的特殊性徽千，使得匹配速度并沒(méi)有想象中的那么差苫费，兩張 iPhone 6 的圖片指紋匹配大約需要 100 到 500 ms 之間。
一種改進(jìn)的方式是使用動(dòng)態(tài)規(guī)劃双抽，用空間換時(shí)間。假設(shè)圖 1 高為 m牍汹， 圖 2 高 為 n，圖 1 的第 i 行與圖 2 的 j 行內(nèi)容一致慎菲，用 c[i,j] 表示以 i,j 行作為結(jié)尾的最長(zhǎng)公共子串長(zhǎng)度嫁蛇，則有：c[i,j] = c[i-1,j-1] + 1露该。基于這個(gè)原理解幼，我們建立一個(gè) m * n 的二維數(shù)組，只需要一次遍歷就可以找出最大子串撵摆，復(fù)雜度為 O(n^2)。使用這種方法特铝，兩張 iPhone 6 圖片指紋匹配只需要 10 到 50 ms暑中。
多圖拼接
對(duì)于兩張圖而言壹瘟，一旦找到最大相同行，只需要將兩張圖分別切割成 上圖上部分鳄逾，共同部分和下圖下部分進(jìn)行拼接即可俐筋。但是如果有多張圖，情形則復(fù)雜得多严衬，相鄰兩對(duì)圖的相同部分可能有如下三種情況：包含，相交笆呆，不相交请琳。這使得預(yù)先計(jì)算多圖拼接后的圖片大小和各個(gè)圖的裁剪區(qū)域變得極其復(fù)雜和困難。(如果有什么好的方法可以直接計(jì)算出對(duì)應(yīng)關(guān)系赠幕，請(qǐng)告訴我)
所以在我的實(shí)現(xiàn)里使用了遞歸的方式來(lái)實(shí)現(xiàn)俄精。這個(gè)地方有個(gè)小 trick，當(dāng)前面兩張圖片合并為一張新圖后榕堰，由于新圖大小發(fā)生變化竖慧，導(dǎo)致后續(xù)兩張圖匹配行數(shù)也發(fā)生偏移，需要重新調(diào)整逆屡。但是考慮到所有的圖片都是從上往下進(jìn)行拼接圾旨，所以在匹配時(shí)直接使用距底部距離作為偏移值，這樣就避免了合并后的圖片需要重新計(jì)算匹配行偏移的情況魏蔗。
