您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 程式開發 >> iOS 開發基礎

業餘時間搗鼓的小工具:一鍵拼接聊天記錄截圖

編輯:iOS 開發基礎

前陣子做了個把截圖自動拼接的小玩具,能實現聊天記錄、朋友圈截圖的自動縫合,玩起來挺有意思,索性記錄下來與大家分享。

緣起

生活中常有這樣的場景:想把微信聊天記錄或某個網頁轉發給別人,內容太長,只能一段一段截圖再發,既麻煩又容易出現亂序送達的尷尬。於是跑到 App Store 上翻了款自動拼接截圖的 App(截圖拼接),起初用得挺爽,直到某天發現它只能保存一次,實在憋屈。乾脆自己動手寫一個,第一天專攻算法驗證可行性,第二天把界面和流程打磨順暢,速度還比那款 App 快上好幾倍,成就感滿滿。只不過轉念一想,這兩天的「工資成本」怕是早就超過那款 App 的售價了……

實現思路

要拼接兩張截圖,核心問題是找出它們的重疊內容。最直白的想法是逐行掃描、逐像素比對,判斷每一行是否匹配,再找出連續匹配的最大行數。但稍微算一下就會頭皮發麻:iPhone 6 的截圖分辨率是 750 × 1334,若真這麼幹,匹配次數動輒上萬億,計算量與效率完全無法接受。所以必須借助一些技巧來降低開銷。

提取圖片指紋

判斷兩行是否相同時,行內每個像素的具體數值其實並不重要,我們真正關心的是整行的整體數據。一張寬 750 的圖片,每行就有 3KB 字節,逐個比對數據量實在太大。所以第一步,是對行數據做一次「壓縮」,說得時髦點就是「提取圖片指紋」。最直接的做法是計算這段數據的 MD5,既能把 3KB 壓到幾十個字節,又能保證唯一性。

但這種強哈希有兩個明顯短板:

  • 計算開銷偏大

  • 結果是字符串形式,不利於後續比較

權衡之下,最終改用 CRC 這種弱哈希來提取指紋。一方面算得快,另一方面結果是數字,能顯著加快後續匹配速度。至於弱哈希可能帶來的碰撞問題,其實可以忽略:最終匹配要求的是「連續多行完全相同」,偶爾的個別碰撞對整體結果的正確性幾乎毫無影響。

匹配圖片指紋

用 CRC 提取指紋後,一張 iPhone 6 截圖就被轉換成了 1334 個 unsigned long 組成的數字集合,問題瞬間簡化為「在兩個序列裡找最長公共子串」。最粗暴的做法是遍歷每一行,一旦某兩行匹配就繼續往下比,直到找出最大的匹配塊。理論上最差時間復雜度會達到 O(n^4),這在紙面上無法接受。但實測下來,由於指紋數據的特殊性,匹配速度並沒有想象中那麼糟,兩張 iPhone 6 圖片的指紋匹配大約在 100 到 500 毫秒之間。

一種更聰明的改進是用動態規劃,以空間換時間。設圖 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 毫秒。

多圖拼接

對兩張圖來說,找到最大相同行後,只需把兩張圖分別切成「上圖的上半部分」「公共部分」「下圖的下半部分」再拼起來即可。但當圖片變多,情況就複雜了:相鄰兩對圖的公共部分可能呈現包含、相交、不相交三種關係,這使得預先計算最終尺寸與各圖裁剪區域變得異常棘手。(如果你有能直接算出對應關係的妙招,歡迎指教。)

因此我的實現採用了遞歸。這裡有個小技巧:當前兩張圖合併成一張新圖後,尺寸變化會導致後續兩張圖的匹配行數發生偏移,需要重新校正。但考慮到所有圖片都是自上而下拼接的,我在匹配時乾脆直接以「距底部的距離」作為偏移基準,這樣就巧妙地避開了合併後重新計算行偏移的麻煩。

最終效果

拼接效果相當理想,可謂天衣無縫:


可改進之處

  • 動態規劃在合併超長圖時申請的內存可能高達幾十兆,但其實比對過程只需保留上一行數據和最大值,並不需要 m × n 的二維數組,用 2 × n 的大小就足夠了。(攤手,實在懶得改了。)

  • 對含動態內容的圖片會匹配失敗,比如聊天記錄裡有跳動的表情。想到的思路是用 SIFT、SURF 這類算法計算出興趣點(Interesting Point),再配合前面的算法匹配,但這種方案實現難度高、可行性也有限。

源碼

具體的實現細節可參考 M80ImageMerger。

  1. 上一篇文章:
  2. 下一篇文章:
蘋果刷機越獄教程| IOS教程問題解答| IOS技巧綜合| IOS7技巧| IOS8教程
Copyright © IOS教程網 All Rights Reserved