深度探索二维码及其应用
前言
二維碼在目前我們生活中是太常見了，掃碼登陸、掃碼支付、加好友......二維碼又稱QR Code，是一個在移動設備上非常流行的編碼方式。
這一篇博客里將從原理和藝術二維碼生成的角度來談一談，先給大家看看最終的效果:
二維碼原理
二維碼的前身是超市購物時的條形碼(一維碼):
但是很明顯這個一維碼的局限性太大了，只能識別0-9數字編成的標識符；所以在這個信息化社會，二維碼的產生我認為是自然而然的。首先，我們先說一下二維碼最常見的有黑白兩種顏色:
一共有40個尺寸。官方叫版本Version。Version 1是21 x 21的矩陣，Version 2是 25 x 25的矩陣，Version 3是29的尺寸，每增加一個version，就會增加4的尺寸，公式是：(V-1)*4 + 21（V是版本號）
最高Version 40，(40-1)*4+21 = 177，所以最高是177 x 177 的正方形。
下面是一張二維碼的簡單示意圖:
翻譯一下是這樣的:
定位圖案
任何一個二維碼除了右下角，其他的三個方塊就是定位圖案，用來標記二維碼矩形的大小，之所以用3個就和為什么TCP是三次握手一樣，少了無法確定信息、多了則顯得贅余。定位圖形是用作標準線，為了防止尺寸過大后掃描可能會發生掃歪的情況。矯正圖形是(Version$\ge$2)時定位用的。
功能性數據
格式信息存放格式化數據，版本信息在Version$\ge$7時需要預留兩塊3*6的區域存放版本信息。
數據碼和糾錯碼
圖中整個灰色區域就是放置數據碼和糾錯碼的地方，為什么有糾錯碼我們放在后面詳談。
QR碼支持以下編碼方式:數字編碼、字符編碼、字節編碼、雙字節編碼、特殊字符集、混合編碼以及特殊編碼.....不同版本（尺寸）的二維碼，對于，數字，字符，字節和Kanji模式下，對于單個編碼的2進制的位數:
舉個簡單具體例子來說明是如何進行數據編碼的:
我們現在有個"HELLO WORLD"的字符串需要編碼，我們從字符索引表中找到這幾個字母的索引：
為(17,14,21,21,24,36,32,24,27,21)，然后兩兩分組(17,14),(21,21),(24,36),(32,24),(27,21)。把每一組轉成11bits的二進制，比如(17,14)就是17*45+14=779轉成01100001011，全部轉換后拼接起來為:01100001011 01111000110 10001011100 10110111000 10011010100 001101，然后把字符的個數11專程二進制000001011(Version 1-H為9 bits),最前面加上字符編碼0010，其他字符的形式見下表:
| Numeric Mode | 0001 |
| Alphanumeric Mode | 0010 |
| Byte Mode | 0100 |
| Kanji Mode | 1000 |
| ECI Mode | 0111 |
結尾加上結束符0000。現在總共有78bits，但是部位8的倍數我們還要加上足夠的0，然后按8個bits分好組:
00100000 01011011 00001011 01111000 11010001 01110010 11011100 01001101 01000011 01000000
如果最后還沒有達到我們的最大bits數的限制，還要加上一些補齊碼(魔數11101100 00010001 )，重復這個補齊碼就行了，假設我們需要編碼的是Version 1的Q糾錯級，那么，其最大需要104個bits，而我們上面只有80個bits，所以，還需要補24個bits，也就是需要3個Padding Bytes，我們就添加三個，于是得到下面的編碼：
00100000 01011011 00001011 01111000 11010001 01110010 11011100 01001101 01000011 01000000 11101100 00010001 11101100
上面的編碼就是數據碼了，叫Data Codewords，每一個8bits叫一個codeword，我們還要對這些數據碼加上糾錯信息。
糾錯碼數學原理
上面我們說到了一些糾錯級別，Error Correction Code Level，二維碼中有四種級別的糾錯，這就是為什么二維碼有殘缺還能掃出來，也就是為什么有人在二維碼的中心位置加入圖標。
| L | Recovers 7% of data |
| M | Recovers 15% of data |
| Q | Recovers 25% of data |
| H | Recovers 30% of data |
那么，QR是怎么對數據碼加上糾錯碼的？首先，我們需要對數據碼進行分組，也就是分成不同的Block，然后對各個Block進行糾錯編碼，對于如何分組，可以查看下表:
而這里的糾錯方法采用的是Reed-Solomon Error correction ，有興趣的可以前去閱讀這一篇博客。這里簡要的講解一下，該算法運營比較廣泛，在二維碼中，為了抵抗掃描錯誤或污點，在磁盤中，為了抵抗媒體碎片的丟失，在高級存儲系統中，比如谷歌的gfs和bigtable，為了抵抗數據丟失，也為了減少讀取延遲（讀取可以在不等待所有響應到達的情況下完成）。 \(GF(2^{m})\)可以在計算機上有效地實現，這意味著我們可以基于數學定理實現系統，而不必擔心在對整數或實數建模時通常會遇到的溢出問題。
而在這個糾錯過程中，糾錯編碼采用多項式長除法。為此，需要兩個多項式。要使用的第一個多項式稱為消息多項式。消息多項式使用來自數據編碼步驟的數據碼字作為其系數。例如，如果轉換為整數的數據碼字為25、218和35，則消息多項式將為\(25x^{2}+218x+35\)。在實際中，標準QR碼的實際消息多項式要長得多，但這只是一個例子。消息多項式將被除以生成多項式。生成多項式是通過乘積\((x-\alpha^{0})......(x-\alpha^{n-1})\)生成的多項式.其中n是必須生成的糾錯碼字數(參見糾錯表),α等于2,這些在我的博客中也有提到過。在這里也貼上一點:
假如我們現在有一個n-k循環碼的生成多項式:\(g(x)=1+x^{2}+x^{4}\),則生成的(6,2)循環碼的碼字矢量和碼字多項式如下:
| \((u_{0}，u_{1})\) | \((v_{0},v_{1},v_{2},v_{3},v_{4},v_{5})\) | |
| (0,0) | (0,0,0,0,0,0) | \(v_{0}(x)=0*g(x)=0\) |
| (0,1) | (1,0,1,0,1,0) | \(v_{1}(x)=1*g(x)=g(x)\) |
| (1,0) | (0,1,0,1,0,1) | \(v_{2}(x)=x*g(x)=x+x^{3}+x^{5}\) |
| (1,1) | (1,1,1,1,1,1) | \(v_{3}(x)=(x+1)*g(x)=1+x+x^{2}+x^{3}+x^{4}+x^{5}\) |
最終編碼
在形成最終編碼之前，還要把數據碼和糾錯碼的各個codewords交替放在一起。如何交替呢，規則如下： 不論數據碼還是糾錯碼，把每個塊的第一個codewords先拿出來按順度排列好，然后再取第一塊的第二個，如此類推。
塊1 67 85 70 134 塊2 246 246 66 7 塊3 182 230 247 119 塊4 70 247 118 86先取第一列:67,246,182,70，然后再取第二列:67,246,182,70,85,246,230,247，如此類推就行了，最后把兩組放在一起就是我們的數據區。
畫二維碼圖
1.首先，先把Position Detection圖案畫在三個角上。（無論Version如何，這個圖案的尺寸就是這么大）
2.然后把Alignment圖案畫上
Alignment的位置可以根據QR Code關于Table-E.1的定義表:
例如Version8，它的校正圖形(Alignment Patterns)的數量在表格中為6個，位置分別為(6,24,42)，畫在圖中為:
3.接下來畫定位圖形(Timing Pattern)的線，很簡單將上方和左邊的線連起來就OK:
4.然后將格式信息(Format Information)畫在圖中，由于格式信息是一個15bits的信息，所以按下圖來畫:
由于Position Detection圖案的大小是固定的，所以格式信息始終是圖中的標識；而這15bits中包括:5個數據bits（其中，2個bits用于表示使用什么樣的Error Correction Level， 3個bits表示使用什么樣的Mask）以及10個糾錯bits(主要通過BCH Code來計算）；然后15個bits還要與101010000010010做XOR操作。這樣就保證不會因為選用了00的糾錯級別和000的Mask，從而造成全部為白色，這會增加掃描器的圖像識別的困難。
5.版本信息(Version大于等于7)如下藍色部分:
總共18個bits，其中6個bits為版本號、12bits為糾錯碼，例如Version7:
其填充位置是這樣的:
BCH碼是一種有限域中的線性分組碼，具有糾正多個隨機錯誤的能力，通常用于通信和存儲領域中的糾錯編碼。
這里簡要介紹一下BCH編碼，想深入的了解如何encode的可以去看我的這一篇博客
若循環碼的生成多項式具有如下形式\(g(x)=LCM[m_{1}(x),m_{3}(x)..m_{2t-1}(x)]\)
其中LCM表示最小公倍式，t為糾錯個數，\(m_{i}(x)\)為素多項式，則由此生成的循環碼稱為BCH碼，其最小碼距\(d\ge d_{0}=2t+1\)，其中\(d_{0}\)為設計碼距，則這個碼能糾正t個隨機獨立差錯。
舉個例子來有個先驗感知:BCH(15,5)碼，可糾正3個隨機獨立差錯(t=3)，求它的生成多項式。
碼距應該為\(d\ge d_{0}=2*3+1=7\)
n=15，根據\(n=2^{m}-1\)，得出m等于4；查下表不可約多項式可知:
| 2 | 1 | 111 |
| 3 | 1 | 1101 |
| 4 | 1 3 5 | 010011 011111 000111 |
| 5 | 1 3 5 | 100101 111101 110111 |
于是就有了\(m_{1}(x)=x^{4}+x+1\),\(m_{3}(x)=x^{4}+x^{3}+x^{2}+x+1\),\(m_{5}(x)=x^{2}+x+1\)
這樣就得出：
\(g(x)=LCM[m_{1}(x),m_{3}(x),m_{5}(x)]=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1\)
6.接著就是加上我們的最終編碼，最終編碼的填充方式如下:數據位從矩陣的右下角開始放置，并在兩個模塊寬的列中向上移動。0使用白色像素，1使用黑色像素。當列到達頂部時，下一個2模塊列將立即從前一列的左邊開始，并繼續向下。每當當前列到達矩陣的邊緣時，移動到下一個2模塊列并更改方向。如果遇到函數模式或保留區域，則將數據位放置在下一個未使用的模塊中。
具體的放置方式為:
當然，已經復雜成這樣了，我覺得到這里就可以了；但是QR Code并沒有讓我們到此為止。因為最終編碼形成的區域可能會存在點不均衡，可能有大面積的空白或者黑塊，掃描識別就會變得非常的困難。所以還要加上Masking(掩碼圖案)操作，該操作只能應用在數據碼和糾錯碼放置的區域，操作會遵循以下四個規則:
對于第一個評估條件，逐個檢查每一行。如果有五個連續模塊相同的顏色，增加3的懲罰。如果在前五個之后有更多相同顏色的模塊，則為相同顏色的每個附加模塊添加一個。然后，逐個檢查每一列，檢查相同的條件。將水平和垂直總數相加以獲得懲罰分數。所以說是行與列都要進行計算，最后累加:
對于第二個評估條件，查找至少2x2模塊或更大的相同顏色的區域。QR碼規范規定，對于大小為m×n的實色塊，懲罰分數為3×(m-1)×(n-1)。然而，QR代碼規范并沒有指定在有多種方法分割實色塊時如何計算懲罰。因此，與其尋找大于2x2的實色塊，只需將QR代碼中相同顏色的2x2塊中的每個2x2塊的懲罰分數增加3，確保計算重疊的2x2塊。例如，相同顏色的3x2塊應該被計算為兩個2x2塊，一個重疊另一個。
第三個懲罰規則尋找黑白黑黑黑白黑的模式，在兩邊任意一邊存在有四個白模塊。換句話說，它查找以下兩種模式中的任何一種：
每次發現這種模式時，將40分加到罰分上。在下面的示例中，有兩個這樣的模式。
最終的評估條件是基于黑與白模塊的比例。若要計算此懲罰規則，請執行以下步驟：
舉個例子:
該二維碼有228個白模塊，213個黑模塊，總共有441個模塊。黑模塊占比為48.2993%。該比例是在45-50之間，計算|45-50|=|-5|=5，|50-50|=0，除以5得到答案:1與0.這兩個數字中最小的是0。乘以10，這仍然是0。所以該二維碼的第四個規則中懲罰分數為0.
最后將這四個規則計算的懲罰分數加起來，再代入Mask計算后選擇分數最小的，官方文件說QR有8個Mask可以使用:
上面的例子如下圖，應該選擇Mask Pattern 0:
Mask的標識符如下:
選擇不同的Mask算法會有不同的結果
這樣才是最終的二維碼圖。
整體流程簡要的提及了一下，更為詳細的步驟可以去參看一下這篇博客
最后根據"HELLO WORLD"生成的二維碼如下，大家不妨掃一下試試:
藝術二維碼
一些思路
首先推薦一下這篇文章里提到的方法:https://research.swtch.com/qart，此外還有一篇Halftone QR Codes與這一篇Embedding grayscale halftone pictures in QR Codes using Correction Trees
首先通過前文二維碼的分析我們已經知道了，二維碼利用了Reed-Solomon進行了糾錯，同時最后會通過一個Mask進行黑白區塊調整。
在QR中放置圖片。我們可以設計編碼的值，在沒有固有錯誤的代碼中創建圖像，而不是在多余的部分上涂鴉或依靠錯誤更正來保留意義。而在Halftone QR Codes這篇論文中，通過一種新的二進制模式優化方法，即把數據點(信息點)進行縮小，在二維碼圖形中生成某種具象圖形，從技術層面自動生成一種新的視覺QR碼即半色調的QR。而在Embedding grayscale halftone pictures in QR Codes using Correction Trees中則是提出了嵌入灰度半色調圖片的設計方法，相當于是前一篇論文在色彩上的改進。
論文中提及的基本都是思想與數學原理，如Halftone QR Codes這篇文章中，就是考慮了可讀性與正則性兩者，并以一個優化目標作為結果來考慮的。如果要實現的話，還是需要看看代碼。
所以下面將就這幾個方法進行討論與實現:
方法1
這個方法是按照https://research.swtch.com/qart進行實現的，7sDream的pyqart實現了這一個算法。基本原理大致是將數據碼和糾錯碼劃分了新的區域，經過旋轉或者經過其他變換使得仍然是具有意義的編碼方式。
簡要談一下代碼結構:
pyqart.qr 這一部分是一個基本上完整的二維碼生成器， data 模塊是數據編碼， ec 模塊是生成糾錯碼， args 是二維碼的參數， painter.canvas 生成二維碼的框架， painter.painter 的作用是把 canvas 、 data 、 ec 三部分組合起來，最后交給 printer 里的各種生成器輸出二維碼。
pyqart.art 里的 QArtSourceImage 是處理輸入圖像的，做一些二值化，dithering，計算對比度之類的操作。 QrArtist 里的 bis 函數是 QArt 的關鍵算法。
該方法產生的效果圖如下:
方法2
這個方法在sylnsfar的qrcode中已經有完整的代碼實現，sylnsfar自己實現了繪制二維碼的代碼，在該項目的mylibs中進行了實現，有興趣的可以前去觀摩一下。
首先看MyQR/mylibs/constant.py,這里的都是一些參數設置，供其他文件調取的。
MyQR/mylibs/matrix.py文件,其中有下面這些部分代碼:
def get_qrmatrix(ver, ecl, bits):num = (ver - 1) * 4 + 21qrmatrix = [[None] * num for i in range(num)]# [([None] * num * num)[i:i+num] for i in range(num * num) if i % num == 0] # Add the Finder Patterns & Add the Separatorsadd_finder_and_separator(qrmatrix)# Add the Alignment Patternsadd_alignment(ver, qrmatrix)# Add the Timing Patternsadd_timing(qrmatrix)# Add the Dark Module and Reserved Areasadd_dark_and_reserving(ver, qrmatrix) maskmatrix = [i[:] for i in qrmatrix] # Place the Data Bitsplace_bits(bits, qrmatrix) # Data Maskingmask_num, qrmatrix = mask(maskmatrix, qrmatrix)# Format Informationadd_format_and_version_string(ver, ecl, mask_num, qrmatrix)return qrmatrix通過注釋我們可以知道就是生成二維碼的步驟！
MyQR/mylibs/data.py是對數據進行編碼，MyQR/mylibs/ECC.py是利用Reed-Solomon進行糾錯。MyQR/mylibs/structure.py是將data.py文件和ECC.py文件生成的數據碼和糾錯碼進行聯合并組織好最終編碼形式。
MyQR/mylibs/draw.py是一個繪圖程序，繪制邊界與黑色模塊。
最終匯集所有功能代碼至MyQR/mylibs/theqrmodule.py中得到最終qrcode。
而將自己的圖像與qrcode結合在一起的代碼位于myqr.py中的combine函數。
效果圖如下:
該二維碼跳轉至sylnsfar的github個人首頁。
方法3
實現時，我們需要引入一個qrcode的package，這樣我們就不用像方法2中那樣手動按步驟生成二維碼了。
首先實驗一下這個qrcode包:
import qrcode # ERROR_CORRECT_L # About 7% or less errors can be corrected. # ERROR_CORRECT_M (default) # About 15% or less errors can be corrected. # ERROR_CORRECT_Q # About 25% or less errors can be corrected. # ERROR_CORRECT_H. # About 30% or less errors can be corrected. qr = qrcode.QRCode(version=1,error_correction=qrcode.constants.ERROR_CORRECT_L,box_size=10,border=4, ) qr.add_data('Some data is here,BY YunLambert') # 這里放鏈接也是OK的 qr.make(fit=True)img = qr.make_image(fill_color="black", back_color="white") img.save("test.png")結果出來的圖片是這樣的:
這里主要參考了chinuno的CuteR，具體的一些解釋我也放在代碼注釋里了。值得一說的是，chinuno的代碼對于gif處理是通過PIL將一張gif圖一幀一幀進行處理，然后集中到一起播放的，生成的代碼如下:
if len(result) == 1 or output.upper()[-3:] != "GIF": # 如果成功生成1張圖片或者文件后綴不為GIF的多張圖片 result[0].save(output) elif len(result) > 1: # 如果是動圖 result[0].save(output, save_all=True, append_images=result[1:], duration=100, optimize=True)考慮了加入images2gif這個package，原本想要使得處理gif會更加得體一些，但是花了很長時間研究images2gif后我發現結果生成的效果并不好(-_-||).......
代碼中也加了images2gif這部分，如果是python3以上的話，很有可能會出現無法導入的情況，這里可以參照這一篇博客或者這些辦法進行修改。
生成的結果如下:
最后放上Code,使用方法見這里。
轉載于:https://www.cnblogs.com/yunlambert/p/10290367.html
總結
以上是生活随笔為你收集整理的深度探索二维码及其应用的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 每天从百度疯抢1000000IP
- 下一篇： HTML5 Canvas编写五彩连珠（6