背景
識(shí)別二維碼的項(xiàng)目數(shù)不勝數(shù)，每次都是開箱即用，方便得很。
這次想用 OpenCV 從零識(shí)別二維碼，主要是溫習(xí)一下圖像處理方面的基礎(chǔ)概念，熟悉 OpenCV 的常見操作，以及了解二維碼識(shí)別和編碼的基本原理。
作者本人在圖像處理方面還是一名新手，采用的方法大多原始粗暴，如果有更好的解決方案歡迎指教。
QRCode
二維碼有很多種，這里我選擇的是比較常見的 QRCode 作為探索對(duì)象。QRCode 全名是 Quick Response Code，是一種可以快速識(shí)別的二維碼。
尺寸
QRCode 有不同的 Version ，不同的 Version 對(duì)應(yīng)著不同的尺寸。將最小單位的黑白塊稱為 module ，則 QRCode 尺寸的公式如下：
Version V = ((V-1)*4 + 21) ^ 2 modules
常見的 QRCode 一共有40種尺寸：
Version 1 : 21 * 21 modules
Version 2 : 25 * 25 modules
…
Version 40: 177 * 177 modules
分類
QRCode 分為 Model 1、Model 2、Micro QR 三類：
- Model 1 ：是 Model 2 和 Micro QR 的原型，有 Version 1 到 Version 14 共14種尺寸。
- Model 2 ：是 Model 1 的改良版本，添加了對(duì)齊標(biāo)記，有 Version 1 到 Version 40 共40種尺寸。
- Micro QR ：只有一個(gè)定位標(biāo)記，最小尺寸是 11*11 modules 。
組成
QRCode 主要由以下部分組成：
- 1 - Position Detection Pattern：位于三個(gè)角落，可以快速檢測二維碼位置。
- 2 - Separators：一個(gè)單位寬的分割線，提高二維碼位置檢測的效率。
- 3 - Timing Pattern：黑白相間，用于修正坐標(biāo)系。
- 4 - Alignment Patterns：提高二維碼在失真情況下的識(shí)別率。
- 5 - Format Information：格式信息，包含了錯(cuò)誤修正級(jí)別和掩碼圖案。
- 6 - Data：真正的數(shù)據(jù)部分。
- 7 - Error Correction：用于錯(cuò)誤修正，和 Data 部分格式相同。
具體的生成原理和識(shí)別細(xì)節(jié)可以閱讀文末的參考文獻(xiàn)，比如耗子叔的這篇《二維碼的生成細(xì)節(jié)和原理》。
由于二維碼的解碼步驟比較復(fù)雜，而本次學(xué)習(xí)重點(diǎn)是數(shù)字圖像處理相關(guān)的內(nèi)容，所以本文主要是解決二維碼的識(shí)別定位問題，數(shù)據(jù)解碼的工作交給第三方庫（比如 ZBAR）完成。
OpenCV
在開始識(shí)別二維碼之前，還需要補(bǔ)補(bǔ)課，了解一些圖像處理相關(guān)的基本概念。
contours
輪廓（contour）可以簡單理解為一段連續(xù)的像素點(diǎn)。比如一個(gè)長方形的邊，比如一條線，比如一個(gè)點(diǎn)，都屬于輪廓。而輪廓之間有一定的層級(jí)關(guān)系，以下圖為例：
主要說明以下概念：
- external & internal：對(duì)于最大的包圍盒而言，2 是外部輪廓（external），2a 是內(nèi)部輪廓（internal）。
- parent & child：2 是 2a 的父輪廓（parent），2a 是 2 的子輪廓（child），3 是 2a 的子輪廓，同理，3a 是 3 的子輪廓，4 和 5 都是 3a 的子輪廓。
- external | outermost：0、1、2 都屬于最外圍輪廓（outermost）。
- hierarchy level：0、1、2 是同一層級(jí)（same hierarchy），都屬于 hierarchy-0 ，它們的第一層子輪廓屬于 hierarchy-1 。
- first child：4 是 3a 的第一個(gè)子輪廓（first child）。實(shí)際上 5 也可以，這個(gè)看個(gè)人喜好了。
在 OpenCV 中，通過一個(gè)數(shù)組表達(dá)輪廓的層級(jí)關(guān)系：
[Next, Previous, First_Child, Parent]
- Next：同一層級(jí)的下一個(gè)輪廓。在上圖中， 0 的 Next 就是 1 ，1 的 Next 就是 2 ，2 的 Next 是 -1 ，表示沒有下一個(gè)同級(jí)輪廓。
- Previous：同一層級(jí)的上一個(gè)輪廓。比如 5 的 Previous 是 4， 1 的 Previous 就是 0 ，0 的 Previous 是 -1 。
- First_Child：第一個(gè)子輪廓，比如 2 的 First_Child 就是 2a ，像 3a 這種有兩個(gè) Child ，只取第一個(gè)，比如選擇 4 作為 First_Child 。
- Parent：父輪廓，比如 4 和 5 的 Parent 都是 3a ，3a 的 Parent 是 3 。
關(guān)于輪廓層級(jí)的問題，參考閱讀：《Tutorial: Contours Hierarchy》
findContours
了解了 contour 相關(guān)的基礎(chǔ)概念之后，接下來就是在 OpenCV 里的具體代碼了。
findContours 是尋找輪廓的函數(shù)，函數(shù)定義如下：
cv2.findContours(image, mode, method) → image, contours, hierarchy
其中：
image：資源圖片，8 bit 單通道，一般需要將普通的 BGR 圖片通過 cvtColor 函數(shù)轉(zhuǎn)換。
mode：邊緣檢測的模式，包括：
CV_RETR_EXTERNAL：只檢索最大的外部輪廓（extreme outer），沒有層級(jí)關(guān)系，只取根節(jié)點(diǎn)的輪廓。
CV_RETR_LIST：檢索所有輪廓，但是沒有 Parent 和 Child 的層級(jí)關(guān)系，所有輪廓都是同級(jí)的。
CV_RETR_CCOMP：檢索所有輪廓，并且按照二級(jí)結(jié)構(gòu)組織：外輪廓和內(nèi)輪廓。以前面的大圖為例，0、1、2、3、4、5 都屬于第0層，2a 和 3a 都屬于第1層。
CV_RETR_TREE：檢索所有輪廓，并且按照嵌套關(guān)系組織層級(jí)。以前面的大圖為例，0、1、2 屬于第0層，2a 屬于第1層，3 屬于第2層，3a 屬于第3層，4、5 屬于第4層。
method：邊緣近似的方法，包括：
CV_CHAIN_APPROX_NONE：嚴(yán)格存儲(chǔ)所有邊緣點(diǎn)，即：序列中任意兩個(gè)點(diǎn)的距離均為1。
CV_CHAIN_APPROX_SIMPLE：壓縮邊緣，通過頂點(diǎn)繪制輪廓。
drawContours
drawContours 是繪制邊緣的函數(shù)，可以傳入 findContours
函數(shù)返回的輪廓結(jié)果，在目標(biāo)圖像上繪制輪廓。函數(shù)定義如下：
Python: cv2.drawContours(image, contours, contourIdx, color) → image
其中：
image：目標(biāo)圖像，直接修改目標(biāo)的像素點(diǎn)，實(shí)現(xiàn)繪制。
contours：需要繪制的邊緣數(shù)組。
contourIdx：需要繪制的邊緣索引，如果全部繪制則為 -1。
color：繪制的顏色，為 BGR 格式的 Scalar 。
thickness：可選，繪制的密度，即描繪輪廓時(shí)所用的畫筆粗細(xì)。
lineType: 可選，連線類型，分為以下幾種：
LINE_4：4-connected line，只有相鄰的點(diǎn)可以連接成線，一個(gè)點(diǎn)有四個(gè)相鄰的坑位。
LINE_8：8-connected line，相鄰的點(diǎn)或者斜對(duì)角相鄰的點(diǎn)可以連接成線，一個(gè)點(diǎn)有四個(gè)相鄰的坑位和四個(gè)斜對(duì)角相鄰的坑位，所以一共有8個(gè)坑位。
LINE_AA：antialiased line，抗鋸齒連線。
hierarchy：可選，如果需要繪制某些層級(jí)的輪廓時(shí)作為層級(jí)關(guān)系傳入。
maxLevel：可選，需要繪制的層級(jí)中的最大級(jí)別。如果為1，則只繪制最外層輪廓，如果為2，繪制最外層和第二層輪廓，以此類推。
moments
矩（moment）起源于物理學(xué)的力矩，最早由阿基米德提出，后來發(fā)展到統(tǒng)計(jì)學(xué)，再后來到數(shù)學(xué)進(jìn)行歸納。本質(zhì)上來講，物理學(xué)和統(tǒng)計(jì)學(xué)的矩都是數(shù)學(xué)上矩的特例。
物理學(xué)中的矩表示作用力促使物體繞著支點(diǎn)旋轉(zhuǎn)的趨向，通俗理解就像是擰螺絲時(shí)用的扭轉(zhuǎn)的力，由矢量和作用力組成。
數(shù)學(xué)中的矩用來描述數(shù)據(jù)分布特征的一類數(shù)字特征，例如：算術(shù)平均數(shù)、方差、標(biāo)準(zhǔn)差、平均差，這些值都是矩。在實(shí)數(shù)域上的實(shí)函數(shù) f(x) 相對(duì)于值 c 的 n 階矩為：
常用的矩有兩類：
- 原點(diǎn)矩（raw moment）：相對(duì)原點(diǎn)的矩，即當(dāng) c 為 0 的時(shí)候。1階原點(diǎn)矩為期望，也成為中心。
- 中心矩（central moment）：相對(duì)于中心點(diǎn)的矩，即當(dāng) c 為 E(x) 的時(shí)候。1階中心矩為0，2階中心矩為方差。
到了圖像處理領(lǐng)域，對(duì)于灰度圖（單通道，每個(gè)像素點(diǎn)由一個(gè)數(shù)值來表示）而言，把坐標(biāo)看成二維變量 (X, Y)，那么圖像可以用二維灰度密度函數(shù) I(x, y) 來表示。
簡單來講，圖像的矩就是圖像的像素相對(duì)于某個(gè)點(diǎn)的分布情況統(tǒng)計(jì)，是圖像的一種特征描述。
raw moment
圖像的原點(diǎn)矩（raw moment）是相對(duì)于原點(diǎn)的矩，公式為：
對(duì)于圖像的原點(diǎn)矩而言：
- M00 相當(dāng)于權(quán)重系數(shù)為 1 。將所有 I(x, y) 相加，對(duì)于二值圖像而言，相當(dāng)于將每個(gè)點(diǎn)記為 1 然后求和，也就是圖像的面積；對(duì)于灰度圖像而言，則是圖像的灰度值的和。
- M10 相當(dāng)于權(quán)重為 x 。對(duì)二值圖像而言，相當(dāng)于將所有的 x 坐標(biāo)相加。
- M01 相當(dāng)于權(quán)重為 y 。對(duì)二值圖像而言，相當(dāng)于將所有的 y 坐標(biāo)相加。
圖像的幾何中心（centroid）等于 (M10 / M00 , M01 / M00)。
central moment
圖像的中心矩（central moment）是相對(duì)于幾何中心的矩，公式為：
可以看到，中心矩表現(xiàn)的是圖像相對(duì)于幾何中心的分布情況。一個(gè)通用的描述中心矩和原點(diǎn)矩關(guān)系的公式是：
中心矩在圖像處理中的一個(gè)應(yīng)用便是尋找不變矩（invariant moments），這是一個(gè)高度濃縮的圖像特征。
所謂的不變性有三種，分別對(duì)應(yīng)圖像處理中的三種仿射變換：
- 平移不變性（translation invariants）：中心矩本身就具有平移不變性，因?yàn)樗窍鄬?duì)于自身的中心的分布統(tǒng)計(jì)，相當(dāng)于是采用了相對(duì)坐標(biāo)系，而平移改變的是整體坐標(biāo)。
- 縮放不變性（scale invariants）：為了實(shí)現(xiàn)縮放不變性，可以構(gòu)造一個(gè)規(guī)格化的中心矩，即將中心矩除以 (1+(i+j)/2) 階的0階中心矩，具體公式見 《Wiki: scale invariants》。
- 旋轉(zhuǎn)不變性（rotation invariants）：通過2階和3階的規(guī)格化中心矩可以構(gòu)建7個(gè)不變矩組，構(gòu)成的特征量具有旋轉(zhuǎn)不變性。具體可以看 《Wiki: rotation invariants》。
Hu moment 和 Zernike moment 之類的內(nèi)容就不繼續(xù)展開了，感興趣的可以翻閱相關(guān)文章。
OpenCV + QRCode
接下來就是將 QRCode 和 OpenCV 結(jié)合起來的具體使用了。
初步構(gòu)想的識(shí)別步驟如下：
- 加載圖像，并且進(jìn)行一些預(yù)處理，比如通過高斯模糊去噪。
- 通過 Canny 邊緣檢測算法，找出圖像中的邊緣
- 尋找邊緣中的輪廓，將嵌套層數(shù)大于 4 的邊緣找出，得到 Position Detection Pattern 。
- 如果上一步得到的結(jié)果不為 3 ，則通過 Timing Pattern 去除錯(cuò)誤答案。
- 計(jì)算定位標(biāo)記的最小矩形包圍盒，獲得三個(gè)最外圍頂點(diǎn)，算出第四個(gè)頂點(diǎn)，從而確定二維碼的區(qū)域。
- 計(jì)算定位標(biāo)記的幾何中心，連線組成三角形，從而修正坐標(biāo)，得到仿射變換前的 QRCode 。
在接下來的內(nèi)容里，將會(huì)嘗試用 OpenCV 識(shí)別下圖中的二維碼：
加載圖像
首先加載圖像，并通過 matplotlib 顯示圖像查看效果：
%matplotlib inline
import cv2
from matplotlib import pyplot as plt
import numpy as np
def show(img, code=cv2.COLOR_BGR2RGB):
cv_rgb = cv2.cvtColor(img, code)
fig, ax = plt.subplots(figsize=(16, 10))
ax.imshow(cv_rgb)
fig.show()
img = cv2.imread('1.jpg')
show(img)
OpenCV 中默認(rèn)是 BGR 通道，通過 cvtColor
函數(shù)將原圖轉(zhuǎn)換成灰度圖：
img_gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
邊緣檢測
有了灰度圖之后，接下來用 Canny 邊緣檢測算法檢測邊緣。
Canny 邊緣檢測算法主要是以下幾個(gè)步驟：
- 用高斯濾波器平滑圖像去除噪聲干擾（低通濾波器消除高頻噪聲）。
- 生成每個(gè)點(diǎn)的亮度梯度圖（intensity gradients），以及亮度梯度的方向。
- 通過非極大值抑制（non-maximum suppression）縮小邊緣寬度。非極大值抑制的意思是，只保留梯度方向上的極大值，刪除其他非極大值，從而實(shí)現(xiàn)銳化的效果。
- 通過雙閾值法（double threshold）尋找潛在邊緣。大于高閾值為強(qiáng)邊緣（strong edge），保留；小于低閾值則刪除；不大不小的為弱邊緣（weak edge），待定。
- 通過遲滯現(xiàn)象（Hysteresis）處理待定邊緣。弱邊緣有可能是邊緣，也可能是噪音，判斷標(biāo)準(zhǔn)是：如果一個(gè)弱邊緣點(diǎn)附近的八個(gè)相鄰點(diǎn)中，存在一個(gè)強(qiáng)邊緣，則此弱邊緣為強(qiáng)邊緣，否則排除。
在 OpenCV 中可以直接使用 Canny 函數(shù)，不過在那之前要先用 GaussianBlur 函數(shù)進(jìn)行高斯模糊：
img_gb = cv2.GaussianBlur(img_gray, (5, 5), 0)
接下來使用 Canny 函數(shù)檢測邊緣，選擇 100 和 200 作為高低閾值：
edges = cv2.Canny(img_gray, 100 , 200)
可以看到圖像中的很多噪音都被處理掉了，只剩下了邊緣部分。
尋找定位標(biāo)記
有了邊緣之后，接下來就是通過輪廓定位圖像中的二維碼。二維碼的 Position Detection Pattern 在尋找輪廓之后，應(yīng)該是有6層（因?yàn)橐粭l邊緣會(huì)被識(shí)別出兩個(gè)輪廓，外輪廓和內(nèi)輪廓）：
所以，如果簡單處理的話，只要遍歷圖像的層級(jí)關(guān)系，然后嵌套層數(shù)大于等于5的取出來就可以了：
img_fc, contours, hierarchy = cv2.findContours(edges, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)
hierarchy = hierarchy[0]
found = []
for i in range(len(contours)):
k = i
c = 0
while hierarchy[k][2] != -1:
k = hierarchy[k][2]
c = c + 1
if c >= 5:
found.append(i)
for i in found:
img_dc = img.copy()
cv2.drawContours(img_dc, contours, i, (0, 255, 0), 3)
show(img_dc)
定位篩選
接下來就是把所有找到的定位標(biāo)記進(jìn)行篩選。如果剛好找到三個(gè)那就可以直接跳過這一步了。然而，因?yàn)檫@張圖比較特殊，找出了四個(gè)定位標(biāo)記，所以需要排除一個(gè)錯(cuò)誤答案。
講真，如果只靠三個(gè) Position Detection Pattern 組成的直角三角形，是沒辦法從這四個(gè)當(dāng)中排除錯(cuò)誤答案的。因?yàn)椋环矫鏁?huì)有形變的影響，比如斜躺著的二維碼，本身三個(gè)頂點(diǎn)連線就不是直角三角形；另一方面，極端情況下，多余的那個(gè)標(biāo)記如果位置比較湊巧的話，完全和正確結(jié)果一模一樣，比如下面這種情況：
所以我們需要 Timing Pattern 的幫助，也就是定位標(biāo)記之間的黑白相間的那兩條黑白相間的線。解決思路大致如下：
- 將4個(gè)定位標(biāo)記兩兩配對(duì)
- 將他們的4個(gè)頂點(diǎn)兩兩連線，選出最短的那兩根
- 如果兩根線都不符合 Timing Pattern 的特征，則出局
尋找定位標(biāo)記的頂點(diǎn)
找的的定位標(biāo)記是一個(gè)輪廓結(jié)果，由許多像素點(diǎn)組成。如果想找到定位標(biāo)記的頂點(diǎn)，則需要找到定位標(biāo)記的矩形包圍盒。先通過 minAreaRect
函數(shù)將檢查到的輪廓轉(zhuǎn)換成最小矩形包圍盒，并且繪制出來：
draw_img = img.copy()
for i in found:
rect = cv2.minAreaRect(contours[i])
box = np.int0(cv2.boxPoints(rect))
cv2.drawContours(draw_img,[box], 0, (0,0,255), 2)
show(draw_img)
這個(gè)矩形包圍盒的四個(gè)坐標(biāo)點(diǎn)就是頂點(diǎn)，將它存儲(chǔ)在 boxes 中：
boxes = []
for i in found:
rect = cv2.minAreaRect(contours[i])
box = np.int0(cv2.boxPoints(rect))
box = [tuple(x) for x in box]
boxes.append(box)
定位標(biāo)記的頂點(diǎn)連線
接下來先遍歷所有頂點(diǎn)連線，然后從中選擇最短的兩根，并將它們繪制出來：
def cv_distance(P, Q):
return int(math.sqrt(pow((P[0] - Q[0]), 2) + pow((P[1] - Q[1]),2)))
def check(a, b):
# 存儲(chǔ) ab 數(shù)組里最短的兩點(diǎn)的組合
s1_ab = ()
s2_ab = ()
# 存儲(chǔ) ab 數(shù)組里最短的兩點(diǎn)的距離，用于比較
s1 = np.iinfo('i').max
s2 = s1
for ai in a:
for bi in b:
d = cv_distance(ai, bi)
if d < s2:
if d < s1:
s1_ab, s2_ab = (ai, bi), s1_ab
s1, s2 = d, s1
else:
s2_ab = (ai, bi)
s2 = d
a1, a2 = s1_ab[0], s2_ab[0]
b1, b2 = s1_ab[1], s2_ab[1]
# 將最短的兩個(gè)線畫出來
cv2.line(draw_img, a1, b1, (0,0,255), 3)
cv2.line(draw_img, a2, b2, (0,0,255), 3)
for i in range(len(boxes)):
for j in range(i+1, len(boxes)):
check(boxes[i], boxes[j])
show(draw_img)
獲取連線上的像素值
有了端點(diǎn)連線，接下來需要獲取連線上的像素值，以便后面判斷是否是 Timing Pattern 。
在這之前，為了更方便的判斷黑白相間的情況，先對(duì)圖像進(jìn)行二值化：
th, bi_img = cv2.threshold(img_gray, 100, 255, cv2.THRESH_BINARY)
接下來是獲取連線像素值。由于 OpenCV3 的 Python 庫中沒有 LineIterator
，只好自己寫一個(gè)。在《OpenCV 3.0 Python LineIterator》這個(gè)問答里找到了可用的直線遍歷函數(shù)，可以直接使用。
以一條 Timing Pattern 為例：
打印其像素點(diǎn)看下結(jié)果：
[ 255. 255. 255. 255. 255. 255. 255. 255. 255. 255. 255. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 255. 255. 255. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 255. 255. 255.
255. 255. 255. 255. 255. 255. 255. 255. 255. 255. 255. 255.
255. 255. 255. 255. 255. 255. 255. 255. 255. 255. 255. 255.
0. 0. 0. 255. 255. 255. 255. 255. 255. 255. 255. 255.
255. 0. 255. 255. 255. 255. 255. 255. 255. 255. 255. 255.
255. 255. 255. 255. 255. 255. 255. 255. 255.]
修正端點(diǎn)位置
照理說， Timing Pattern 的連線，像素值應(yīng)該是黑白均勻相間才對(duì)，為什么是上面的這種一連一大片的結(jié)果呢？
仔細(xì)看下截圖可以發(fā)現(xiàn)，由于取的是定位標(biāo)記的外部包圍盒的頂點(diǎn)，所以因?yàn)檎`差會(huì)超出定位標(biāo)記的范圍，導(dǎo)致沒能正確定位到 Timing Pattern ，而是相鄰的 Data 部分的像素點(diǎn)。
為了修正這部分誤差，我們可以對(duì)端點(diǎn)坐標(biāo)進(jìn)行調(diào)整。因?yàn)?Position Detection Pattern 的大小是固定的，是一個(gè) 1-1-3-1-1 的黑白黑白黑相間的正方形，識(shí)別 Timing Pattern 的最佳端點(diǎn)應(yīng)該是最靠里的黑色區(qū)域的中心位置，也就是圖中的綠色虛線部分：
所以我們需要對(duì)端點(diǎn)坐標(biāo)進(jìn)行調(diào)整。調(diào)整方式是，將一個(gè)端點(diǎn)的 x 和 y 值向另一個(gè)端點(diǎn)的 x 和 y 值靠近 1/14 個(gè)單位距離，代碼如下：
a1 = (a1[0] + (a2[0]-a1[0])*1/14, a1[1] + (a2[1]-a1[1])*1/14)
b1 = (b1[0] + (b2[0]-b1[0])*1/14, b1[1] + (b2[1]-b1[1])*1/14)
a2 = (a2[0] + (a1[0]-a2[0])*1/14, a2[1] + (a1[1]-a2[1])*1/14)
b2 = (b2[0] + (b1[0]-b2[0])*1/14, b2[1] + (b1[1]-b2[1])*1/14)
調(diào)整之后的像素值就是正確的 Timing Pattern 了：
[ 255. 255. 255. 255. 255. 255. 255. 255. 255. 255. 255. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 255. 255.
255. 255. 255. 255. 255. 255. 255. 255. 255. 255. 255. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 255. 255.
255. 255. 255. 255. 255. 255. 255. 255. 255. 255. 255. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 255. 255.
255. 255. 255. 255. 255. 255. 255. 255. 255. 255. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 255. 255.
255. 255. 255. 255. 255. 255. 255. 255. 255. 255. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 255. 255.
255. 255. 255. 255. 255. 255. 255. 255. 255.]
驗(yàn)證是否是 Timing Pattern
像素序列拿到了，接下來就是判斷它是否是 Timing Pattern 了。 Timing Pattern 的特征是黑白均勻相間，所以每段同色區(qū)域的計(jì)數(shù)結(jié)果應(yīng)該相同，而且旋轉(zhuǎn)拉伸平移都不會(huì)影響這個(gè)特征。
于是，驗(yàn)證方案是：
- 先除去數(shù)組中開頭和結(jié)尾處連續(xù)的白色像素點(diǎn)。
- 對(duì)數(shù)組中的元素進(jìn)行計(jì)數(shù)，相鄰的元素如果值相同則合并到計(jì)數(shù)結(jié)果中。比如 [0,1,1,1,0,0] 的計(jì)數(shù)結(jié)果就是 [1,3,2] 。
- 計(jì)數(shù)數(shù)組的長度如果小于 5 ，則不是 Timing Pattern 。
- 計(jì)算計(jì)數(shù)數(shù)組的方差，看看分布是否離散，如果方差大于閾值，則不是 Timing Pattern 。
代碼如下：
def isTimingPattern(line):
# 除去開頭結(jié)尾的白色像素點(diǎn)
while line[0] != 0:
line = line[1:]
while line[-1] != 0:
line = line[:-1]
# 計(jì)數(shù)連續(xù)的黑白像素點(diǎn)
c = []
count = 1
l = line[0]
for p in line[1:]:
if p == l:
count = count + 1
else:
c.append(count)
count = 1
l = p
c.append(count)
# 如果黑白間隔太少，直接排除
if len(c) < 5:
return False
# 計(jì)算方差，根據(jù)離散程度判斷是否是 Timing Pattern
threshold = 5
return np.var(c) < threshold
對(duì)前面的那條連線檢測一下，計(jì)數(shù)數(shù)組為：
[11, 12, 11, 12, 11, 12, 11, 13, 11]
方差為 0.47 。其他非 Timing Pattern 的連線方差均大于 10 。
找出錯(cuò)誤的定位標(biāo)記
接下來就是利用前面的結(jié)果除去錯(cuò)誤的定位標(biāo)記了，只要兩個(gè)定位標(biāo)記的端點(diǎn)連線中能找到 Timing Pattern ，則這兩個(gè)定位標(biāo)記有效，把它們存進(jìn) set 里：
valid = set()
for i in range(len(boxes)):
for j in range(i+1, len(boxes)):
if check(boxes[i], boxes[j]):
valid.add(i)
valid.add(j)
print valid
結(jié)果是：
set([1, 2, 3])
好了，它們中出了一個(gè)叛徒，0、1、2、3 四個(gè)定位標(biāo)記，0是無效的，1、2、3 才是需要識(shí)別的 QRCode 的定位標(biāo)記。
找出二維碼
有了定位標(biāo)記之后，找出二維碼就輕而易舉了。只要找出三個(gè)定位標(biāo)記輪廓的最小矩形包圍盒，那就是二維碼的位置了：
contour_all = np.array([])
while len(valid) > 0:
c = found[valid.pop()]
for sublist in c:
for p in sublist:
contour_all.append(p)
rect = cv2.minAreaRect(contour_ALL)
box = cv2.boxPoints(rect)
box = np.array(box)
draw_img = img.copy()
cv2.polylines(draw_img, np.int32([box]), True, (0, 0, 255), 10)
show(draw_img)
小結(jié)
后面仿射變換后坐標(biāo)修正的問題實(shí)在是寫不動(dòng)了，這篇就先到這里吧。
回頭看看，是不是感覺繞了個(gè)大圈子？
『費(fèi)了半天勁，只是為了告訴我第0個(gè)定位標(biāo)記是無效的，我看圖也看出來了??！』
是的，不過代碼里能看到的只是像素值和它們的坐標(biāo)，為了排除這個(gè)錯(cuò)誤答案確實(shí)花了不少功夫。
不過這也是我喜歡做數(shù)字圖像處理的原因之一：可用函數(shù)數(shù)不勝數(shù)，專業(yè)概念層出不窮，同樣的一個(gè)問題，不同的人去解決，就有著不同的答案，交流的過程便是學(xué)習(xí)的過程。
參考文獻(xiàn)：
二維碼的生成細(xì)節(jié)和原理
What is a QR code?
ISO/IEC 18004: QRCode Standard
What Are The Different Sections In A QR Code?
Decoding small QR codes by hand
How data matrix codes work
QR Code Tutorial
How to Read QR Symbols Without Your Mobile Telephone
OpenCV: QRCode detection and extraction
Tutorial Python: Contours Hierarchy
Wiki: Pixel Connectivity
Image Processing: Connect
Wiki: Image Moment
Wiki: Moment (Mathematics)
圖像的矩特征
統(tǒng)計(jì)數(shù)據(jù)的形態(tài)特征
圖像的矩（Image Moments）
OpenCV Doc: Structural analysis and shape descriptors
CS7960 AdvImProc MomentInvariants
OpenCV Doc: Canny
Wiki: Canny Edge Detector
Wiki: Hysteresis
OpenCV 3.0 Python LineIterator
完整代碼:
# -*- coding: utf-8 -*-
"""
Spyder Editor
This is a temporary script file.
"""
import cv2
import math
from matplotlib import pyplot as plt
import numpy as np
def show(img, code=cv2.COLOR_BGR2RGB):
cv_rgb = cv2.cvtColor(img, code)
fig, ax = plt.subplots(figsize=(16, 10))
ax.imshow(cv_rgb)
fig.show()
img = cv2.imread('qr_test.jpg')
img_gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
img_gb = cv2.GaussianBlur(img_gray, (5, 5), 0)
edges = cv2.Canny(img_gray, 100 , 200)
img_fc, contours, hierarchy = cv2.findContours(edges, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)
hierarchy = hierarchy[0]
found = []
for i in range(len(contours)):
k = i
c = 0
while hierarchy[k][2] != -1:
k = hierarchy[k][2]
c = c + 1 # count hierarchy
if c >= 5:
found.append(i) # store index
#for i in found:
# img_dc = img.copy()
# cv2.drawContours(img_dc, contours, i, (0, 255, 0), 3)
# #show(img_dc)
# 對(duì)圖像進(jìn)行二值化
th, bi_img = cv2.threshold(img_gray, 100, 255, cv2.THRESH_BINARY)
draw_img = img.copy()
boxes = []
for i in found:
rect = cv2.minAreaRect(contours[i])
box = np.int0(cv2.boxPoints(rect))
# cv2.drawContours(draw_img,[box], 0, (0,0,255), 2)
#box = map(tuple, box)
box = [tuple(x) for x in box]
boxes.append(box)
#show(draw_img)
#print("Length of Boxes is ",len(boxes))
def createLineIterator(P1, P2, img):
"""
Produces and array that consists of the coordinates and intensities of each pixel in a line between two points
Parameters:
-P1: a numpy array that consists of the coordinate of the first point (x,y)
-P2: a numpy array that consists of the coordinate of the second point (x,y)
-img: the image being processed
Returns:
-it: a numpy array that consists of the coordinates and intensities of each pixel in the radii (shape: [numPixels, 3], row = [x,y,intensity])
"""
#define local variables for readability
imageH = img.shape[0]
imageW = img.shape[1]
P1X = P1[0]
P1Y = P1[1]
P2X = P2[0]
P2Y = P2[1]
#difference and absolute difference between points
#used to calculate slope and relative location between points
dX = P2X - P1X
dY = P2Y - P1Y
dXa = np.abs(dX)
dYa = np.abs(dY)
#predefine numpy array for output based on distance between points
itbuffer = np.empty(shape=(np.maximum(dYa,dXa),3),dtype=np.float32)
itbuffer.fill(np.nan)
#Obtain coordinates along the line using a form of Bresenham's algorithm
negY = P1Y > P2Y
negX = P1X > P2X
if P1X == P2X: #vertical line segment
itbuffer[:,0] = P1X
if negY:
itbuffer[:,1] = np.arange(P1Y - 1,P1Y - dYa - 1,-1)
else:
itbuffer[:,1] = np.arange(P1Y+1,P1Y+dYa+1)
elif P1Y == P2Y: #horizontal line segment
itbuffer[:,1] = P1Y
if negX:
itbuffer[:,0] = np.arange(P1X-1,P1X-dXa-1,-1)
else:
itbuffer[:,0] = np.arange(P1X+1,P1X+dXa+1)
else: #diagonal line segment
steepSlope = dYa > dXa
if steepSlope:
slope = dX.astype(np.float32)/dY.astype(np.float32)
if negY:
itbuffer[:,1] = np.arange(P1Y-1,P1Y-dYa-1,-1)
else:
itbuffer[:,1] = np.arange(P1Y+1,P1Y+dYa+1)
itbuffer[:,0] = (slope*(itbuffer[:,1]-P1Y)).astype(np.int) + P1X
else:
slope = dY.astype(np.float32)/dX.astype(np.float32)
if negX:
itbuffer[:,0] = np.arange(P1X-1,P1X-dXa-1,-1)
else:
itbuffer[:,0] = np.arange(P1X+1,P1X+dXa+1)
itbuffer[:,1] = (slope*(itbuffer[:,0]-P1X)).astype(np.int) + P1Y
#Remove points outside of image
colX = itbuffer[:,0]
colY = itbuffer[:,1]
itbuffer = itbuffer[(colX >= 0) & (colY >=0) & (colX<imageW) & (colY<imageH)]
#Get intensities from img ndarray
itbuffer[:,2] = img[itbuffer[:,1].astype(np.uint),itbuffer[:,0].astype(np.uint)]
return itbuffer
def isTimingPattern(line):
# 除去開頭結(jié)尾的白色像素點(diǎn)
while line[0] != 0:
line = line[1:]
while line[-1] != 0:
line = line[:-1]
# 計(jì)數(shù)連續(xù)的黑白像素點(diǎn)
c = []
count = 1
l = line[0]
for p in line[1:]:
if p == l:
count = count + 1
else:
c.append(count)
count = 1
l = p
c.append(count)
# 如果黑白間隔太少，直接排除
if len(c) < 5:
return False
# 計(jì)算方差，根據(jù)離散程度判斷是否是 Timing Pattern
threshold = 5
return np.var(c) < threshold
def cv_distance(P, Q):
return int(math.sqrt(pow((P[0] - Q[0]), 2) + pow((P[1] - Q[1]),2)))
def check(a, b):
# 存儲(chǔ) ab 數(shù)組里最短的兩點(diǎn)的組合
s1_ab = ()
s2_ab = ()
# 存儲(chǔ) ab 數(shù)組里最短的兩點(diǎn)的距離，用于比較
s1 = np.iinfo('i').max
s2 = s1
for ai in a:
for bi in b:
d = cv_distance(ai, bi)
if d < s2:
if d < s1:
s1_ab, s2_ab = (ai, bi), s1_ab
s1, s2 = d, s1
else:
s2_ab = (ai, bi)
s2 = d
a1, a2 = s1_ab[0], s2_ab[0]
b1, b2 = s1_ab[1], s2_ab[1]
a1 = (a1[0] + np.int0((a2[0]-a1[0])*1/14), a1[1] + np.int0((a2[1]-a1[1])*1/14))
b1 = (b1[0] + np.int0((b2[0]-b1[0])*1/14), b1[1] + np.int0((b2[1]-b1[1])*1/14))
a2 = (a2[0] + np.int0((a1[0]-a2[0])*1/14), a2[1] + np.int0((a1[1]-a2[1])*1/14))
b2 = (b2[0] + np.int0((b1[0]-b2[0])*1/14), b2[1] + np.int0((b1[1]-b2[1])*1/14))
# 將最短的兩個(gè)線畫出來
#cv2.line(draw_img, a1, b1, (0,0,255), 3)
#cv2.line(draw_img, a2, b2, (0,0,255), 3)
lit1 = createLineIterator(a1,b1,bi_img)
lit2 = createLineIterator(a2,b2,bi_img)
if isTimingPattern(lit1[:,2]):
return True
elif isTimingPattern(lit2[:,2]):
return True
else:
return False
valid = set()
for i in range(len(boxes)):
for j in range(i+1, len(boxes)):
if check(boxes[i], boxes[j]):
valid.add(i)
valid.add(j)
#show(draw_img)
print(valid)
contour_all = []
while len(valid) > 0:
c = contours[found[valid.pop()]]
for sublist in c:
for p in sublist:
contour_all.append(p)
rect = cv2.minAreaRect(np.array(contour_all))
box = np.array([cv2.boxPoints(rect)],dtype=np.int0)
cv2.polylines(draw_img, box, True, (0, 0, 255), 3)
show(draw_img)
