本文引用自“螞蟻金服科技”公眾號，原文由支付寶技術團隊原創分享。 本次收錄時有改動。

1、引言

最早接觸2維碼掃碼功能，是在2011年，那會移動互聯網正是起步階段，大家都感覺智能手機可以更強大，但到底要做些什么功能，都是在探索和創新。2維碼掃描功能就是這些創新功能之一。

當然，2維碼掃描說到底還是圖像識別，這種技術不是一般的公司能搞定的，所以大家用的最多的2維碼掃描庫就是ZXing。這個庫，很多人應該非常熟悉，用過這個庫的人，基本都記住了下面這個圖片（ZXing的logo）。

▲ ZXing工程的logo

這個庫的使用前題就是需要手機攝像頭有自動對焦功能，那會手機成本還沒現在這么低，所以自動對焦功能不是所有手機都具備，也就限制了2維碼掃碼功能在一些較低端的手機上的使用，同時也制約了掃碼功能的普及。

后來的事情大家都知道了，微信這種社交IM越來越受歡迎，微信里可以用來掃碼加好友的“掃一掃”功能，讓2維碼掃描功能幾乎變成了IM軟件的標配。

 

▲ 早期微信里的“掃一掃”功能

現在的微信，不僅可以掃2維友加好友，還可以掃碼支付以及各種圖像識別方面的功能，越做越豐富。2維碼掃碼功能從一個單一的圖像識別技術，逐漸演變成了移動線聯網的入口功能。

從去年開始，微信對2維碼掃描功能進行了升級，不僅可以在UI上讓用戶知道被掃描2維碼的中心點，還能同時識別最多3個2維碼，相當強大。

 

▲ 現在的微信可以同時識別最多3個2維碼（注意綠點）

如上圖所示，原本大家都習以為常的2維碼掃描功能，原來還可以做的這么友好。

正好看到支付寶分享的這篇2維碼掃描優化文章，市面上真正分享這方面的技術的文章幾乎沒有，而2維碼掃碼加友作為IM中最常見的功能之一，對于即時通訊網的開發者來說，雖然不需要自已從底層開發，但了解這方面的知識，還是很有必要的。

本文要分享的是支付寶針對2維碼掃描功能，在2維碼殘缺、變形、變色等等惡劣條件下，是如何提升掃碼識別率、識別速度的技術實踐總結。希望能帶給你啟發。

學習交流：

- 即時通訊/推送技術開發交流5群：215477170[推薦]

- 移動端IM開發入門文章：《新手入門一篇就夠：從零開發移動端IM》

- 開源IM框架源碼：https://github.com/JackJiang2011/MobileIMSDK

（本文同步發布于：http://www.52im.net/thread-3150-1-1.html）

2、技術背景

隨著支付寶的線下場景不斷擴大，收錢碼、口碑、共享單車、充電寶、停車繳費等產品讓我們的生活越來越便利。

二維碼因為成本低、兼容性好成為了線上線上最主要的連接工具，也因此面臨更多新的挑戰。

因為二維碼是一種點陣式信息編碼方式，任何視覺上的缺損、彎曲以及光線作用都會極大的影響識別成功率，如果識別困難也就意味著用戶可能選擇放棄，影響支付體驗也影響用戶心智。

用戶掃碼體驗的最關鍵的主要有以下幾個因素：

• 1）識別率：這是掃碼服務的基礎指標，識別率能直接體現識別能力，識別率如果無法提高意味著大量的用戶將無法使用更便捷的服務；
• 2）識別耗時：包括 app 啟動耗時以及圖像識別耗時，這是衡量一個用戶從點擊 app 到正確識別到內容耗時，每增加 1s，將有相當大量的用戶放棄等待并離開；
• 3）精準反饋：識別結果不僅需要及時反饋給用戶，還需要非常精準，特別是在目前線下有多個二維碼的場景下，需要避免用戶二次操作。

本文將從以上三個方面，分享支付寶掃碼技術團隊是如何為用戶打造一個又準又快又穩的極致掃碼體驗。

我們對用戶反饋進行了大量統計分析，發現絕大部分識別失敗都是因為二維碼并不標準，并且很遺憾的是在使用我們早期的掃碼版本進行識別率測試時發現識別率只有 60%。下面的文字，將首先從提高識別率的方向著手。

3、提高識別率策略1：優化樁點查找算法長寬比耐受

以往的掃碼算法，檢查長寬比例時允許差異 40%，但是由于使用前向誤差，判斷結果跟長寬的先后順序相關，這會導致有些長寬比失調的碼，橫著掃不出來，但是旋轉 90 度豎著卻能掃出來了(^OMG^)。

優化策略總結：

• 1）通過修改長寬比的判定規則，長寬比將不再受先后順序影響；
• 2）對于已知長度，修改規則將可接受的寬度范圍擴大，增強長寬比的耐受。

在我們對比測試集中，識別率提高了 1% 左右。

4、提高識別率策略2：新增1:5:1樁點識別模式模式

在一張圖片中，要找到二維碼，關鍵在找二維碼特征定位點: 

三個角的回字型圖案，這就是二維碼特征定位點。

中間區域的黑白色塊比例是1:1:3:1:1：

以往的掃碼算法，樁點識別是通過狀態機 查找11311模式后 取中間位置確定x位置（此時掃描線在第一行11311比例處）在x位置縱向搜索11311模式， 確定y位置再以 (x,y) 位置橫向搜索11311比例，修正x位置。

這種模式在樁點污損的情況下，識別能力較差只要在任何一次11311模式搜索中遇到干擾點，哪怕是一個像素的椒鹽噪聲也能使樁點查找失敗。（支付寶藍的樁點，會在藍色區域產生大量噪點，導致識別率低下）

為此，我們新增了一種樁點識別方式。在狀態機達到151模式的時候，開始嘗試確認樁點。（此時掃描線在第一行151比例處）。

優化效果：

• 1）新的查找方法將不再受樁點中心或邊緣部分被污損的影響，支付寶藍色樁點碼識別率明顯提升；
• 2）修改后識別率整體提升了接近 1%，但識別失敗的耗時有所提升。

5、提高識別率策略3：添加一種對角線過濾規則

在枚舉所有可能樁點組合 O(N^3) 之前，對所有可疑樁點進行一次對角線檢查過濾。由于樁點對角線也應該滿足 11311模式 ，用這個規則做一次過濾可疑有效減少運算量，也就有效降低了識別成功和失敗的耗時。

6、提高識別率策略4：基于 Logistic Regression 的二維碼分類器

在以往的掃碼算法中在拿到三個樁點后，基于夾角，長度偏差，單位長度查三個數值，用簡單公式計算得到閾值，判斷是否為可能的二維碼，誤判概率較大。

為此，我們引入機器學習中的邏輯回歸算法模型。

基于支付寶豐富的二維碼數據集，訓練出邏輯回歸模型，作為二維碼分類器，明顯降低了誤判概率，也將明顯降低無二維碼時識別失敗的耗時。

7、提高識別率策略5：修改跳行掃描的間隔數

由于輸入的相機幀分辨率高，像素點多，運算量大，以往的掃碼算法在水平跟垂直方向跳行采樣進行計算。但在實際運算中，由于跳過了太多列，錯過了11311模式中某些1位置的點，導致樁點查找失敗。

我們通過將跳行計算行數修改為可配置項，通過線上 AB 灰度測試得到最合適的跳行策略，整體配置此跳行策略后，識別率得到明顯提升。

上述優化在測試集的表現： 

綜上優化：掃碼核心識別能力，在7744張圖片測試集上提高了6.95個百分點。

8、特殊策略優化

除此上述通用掃碼優化之外，我們還對特殊場景掃碼能力進行提高。

8.1 畸變？不怕不怕！

線下場景復雜多變。飲料瓶身上變形的二維碼、超市小票卷起邊角彎曲的二維碼、路邊小販凹凸不平甚至折疊的二維碼......這些畸變的二維碼容易增加識別難度，甚至導致識別失敗。

以往的掃碼算法抗畸變策略中，先用透視變換關系建立映射關系。

優點是：適應性好，滿足大多數應用場景。

不足也明顯：對 Version 1 的碼，因為映射關系退化為仿射變換，效果較差，手機必須和碼平面平行才能方便識別。當物料表面不是平面的時候，效果較差。

優化策略：

• 1）假設采樣坐標系到二維碼坐標系遵守一個更復雜的映射關系，并且假設物料表面的卷曲較小，通過使用二次函數可以較好的擬合這個映射關系；
• 2）實際發票上的二維碼版本普遍大于等于 7，高版本二維碼具有多個輔助定位點，更利于構造二次映射表；
• 3）基于以上推論，使用新的映射代替舊的透視變換，進行更精準的采樣。

用新的策略，發票碼這個場景的二維碼識別能力提升明顯。

▲注意：由于采用了增強算法，請對準二維碼稍作等待

樣本測試結果：

8.2 容錯識別能力提升

商戶或者供應商生成二維碼后，通常會在二維碼的中間部分貼上 Logo，這部分有可能會使二維碼 Decode 時出錯。

優化策略:

對于采樣后拿到的 BitMatrix，對于中間部分一塊矩形區域內的點，采用某些策略來改變中間點的值，使它能夠通過容錯邊界的檢查。目前采用兩種策略，第一種是反轉，第二種是每一個點隨機取值。目前所取的矩形區域是長、寬的四分之一。

通過此項優化后，掃碼的容錯能力也得到明顯提升。

9、更小的識別耗時

針對識別效率，我們使用了GPU計算二值化，降低識別單幀耗時。

所謂圖像二值化就是將圖像上的像素點的灰度值設置為 0 或 255，也就是將整個圖像呈現出明顯的只有黑和白的視覺效果。下圖左邊為原圖，右邊是二值化處理過的圖。

在掃碼算法解碼前，有二值化計算，圖像的二值化計算能使圖像中數據量大為減少，并弱化圖像模糊、顏色對比度不強、光線過強/太弱、圖像污損等情況下其他信息的干擾，更利于檢測識別。

傳統算法是在 CPU 上進行二值化運算，非常消耗 CPU 資源，但其實 GPU 更擅長大規模并行計算，所以我們選擇使用 GPU 來做二值化計算。在安卓平臺上使用 RenderScript，iOS 平臺上使用 Metal，都是很底層的框架。

1）iOS優化結果：統一電池、角度、光線等環境變量， 在iPhone6上測試掃碼核心5種攝像頭二值化算法。

表現如下: 

 

可以看出，在圖像二值化方面 Metal 有相當高的優勢，相比原來的單純 CPU 處理快了接近 150%, 同時降低了近50個百分點的CPU資源。

2）Andriod優化結果：由于Android機型眾多，我們抽取了線上數據，可以看到GPU 在二值化處理中顯著降低了單幀耗時30%以上。 

10、算法分級、場景分類、科學調度

線下物料千奇百怪，掃碼算法為了解決一些不理想的場景，如二維碼有遮擋、污損、模糊或角度很不好的特殊情況，需要使用一些比較耗時但比較強大的算法，但普通情況不需要這些算法。

所以，我們對識碼算法定了優先級，通過時間推移、跳幀觸發等方式調度。

優先級：

• 1）高優先級：每幀執行；
• 2）中優先級：降幀率執行；
• 3）低優先級：低幀率執行。

不同優先級的功能執行時機可配置。不同功能屬于哪個優先級可配置

特殊場景算法能力：

• 1）反色碼識別能力；
• 2）容錯邊界碼識別能力；
• 3）污損樁點識別能力等；
• 4）條碼識別能力。

附錄：更多阿里團隊分享的文章

《社交軟件紅包技術解密(七)：支付寶紅包的海量高并發技術實踐》

《阿里釘釘技術分享：企業級IM王者——釘釘在后端架構上的過人之處》

《來自阿里OpenIM：打造安全可靠即時通訊服務的技術實踐分享》

《淘寶技術分享：手淘億級移動端接入層網關的技術演進之路》

《阿里技術分享：深度揭秘阿里數據庫技術方案的10年變遷史》

《阿里技術分享：阿里自研金融級數據庫OceanBase的艱辛成長之路》

《作者談《阿里巴巴Java開發手冊(規約)》背后的故事》

《淘寶技術分享：手淘億級移動端接入層網關的技術演進之路》

《《阿里巴巴Android開發手冊(規約)》背后的故事》

《手機淘寶消息推送系統的架構與實踐(音頻+PPT) [附件下載]》

《重磅發布：《阿里巴巴Android開發手冊(規約)》[附件下載]》

《阿里技術結晶：《阿里巴巴Java開發手冊-v1.6.0-泰山版》[附件下載]》

（本文同步發布于：http://www.52im.net/thread-3150-1-1.html）