识别二维码的项目数不胜数,每次都是开箱即用,方便得很。
这次想用 OpenCV 从零识别二维码,主要是温习一下图像处理方面的基础概念,熟悉 OpenCV 的常见操作,以及了解二维码识别和编码的基本原理。
作者本人在图像处理方面还是一名新手,采用的方法大多原始粗暴,如果有更好的解决方案欢迎指教。
二维码有很多种,这里我选择的是比较常见的 QRCode 作为探索对象。QRCode 全名是 Quick Response Code,是一种可以快速识别的二维码。
QRCode 有不同的 Version ,不同的 Version 对应着不同的尺寸。将最小单位的黑白块称为 module ,则 QRCode 尺寸的公式如下:
Version V = ((V-1)*4 + 21) ^ 2 modules
常见的 QRCode 一共有40种尺寸:
QRCode 分为 Model 1、Model 2、Micro QR 三类:
QRCode 主要由以下部分组成:
具体的生成原理和识别细节可以阅读文末的参考文献,比如耗子叔的这篇《 二维码的生成细节和原理 》。
由于二维码的解码步骤比较复杂,而本次学习重点是数字图像处理相关的内容,所以本文主要是解决二维码的识别定位问题,数据解码的工作交给第三方库(比如 ZBAR )完成。
在开始识别二维码之前,还需要补补课,了解一些图像处理相关的基本概念。
轮廓(contour)可以简单理解为一段连续的像素点。比如一个长方形的边,比如一条线,比如一个点,都属于轮廓。而轮廓之间有一定的层级关系,以下图为例:
主要说明以下概念:
在 OpenCV 中,通过一个数组表达轮廓的层级关系:
[Next, Previous, First_Child, Parent]
关于轮廓层级的问题,参考阅读:《 Tutorial: Contours Hierarchy 》
了解了 contour 相关的基础概念之后,接下来就是在 OpenCV 里的具体代码了。
findContours
是寻找轮廓的函数,函数定义如下:
cv2.findContours(image, mode, method) → image, contours, hierarchy
其中:
drawContours
是绘制边缘的函数,可以传入 findContours
函数返回的轮廓结果,在目标图像上绘制轮廓。函数定义如下:
Python: cv2.drawContours(image, contours, contourIdx, color) → image
其中:
矩(moment)起源于物理学的力矩,最早由阿基米德提出,后来发展到统计学,再后来到数学进行归纳。本质上来讲,物理学和统计学的矩都是数学上矩的特例。
物理学中的矩表示作用力促使物体绕着支点旋转的趋向,通俗理解就像是拧螺丝时用的扭转的力,由矢量和作用力组成。
数学中的矩用来描述数据分布特征的一类数字特征,例如:算术平均数、方差、标准差、平均差,这些值都是矩。在实数域上的实函数 f(x) 相对于值 c 的 n 阶矩为:
常用的矩有两类:
到了图像处理领域,对于灰度图(单通道,每个像素点由一个数值来表示)而言,把坐标看成二维变量 (X, Y),那么图像可以用二维灰度密度函数 I(x, y) 来表示。
简单来讲,图像的矩就是图像的像素相对于某个点的分布情况统计,是图像的一种特征描述。
图像的原点矩(raw moment)是相对于原点的矩,公式为:
对于图像的原点矩而言:
图像的中心矩(central moment)是相对于几何中心的矩,公式为:
可以看到,中心矩表现的是图像相对于几何中心的分布情况。一个通用的描述中心矩和原点矩关系的公式是:
中心矩在图像处理中的一个应用便是寻找不变矩(invariant moments),这是一个高度浓缩的图像特征。
所谓的不变性有三种,分别对应图像处理中的三种仿射变换:
Hu moment 和 Zernike moment 之类的内容就不继续展开了,感兴趣的可以翻阅相关文章。
接下来就是将 QRCode 和 OpenCV 结合起来的具体使用了。
初步构想的识别步骤如下:
在接下来的内容里,将会尝试用 OpenCV 识别下图中的二维码:
首先加载图像,并通过 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 中默认是 BGR 通道,通过 cvtColor
函数将原图转换成灰度图:
img_gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
有了灰度图之后,接下来用 Canny 边缘检测算法检测边缘。
Canny 边缘检测算法主要是以下几个步骤:
在 OpenCV 中可以直接使用 Canny
函数,不过在那之前要先用 GaussianBlur
函数进行高斯模糊:
img_gb = cv2.GaussianBlur(img_gray, (5, 5), 0)
接下来使用 Canny
函数检测边缘,选择 100 和 200 作为高低阈值:
edges = cv2.Canny(img_gray, 100 , 200)
执行结果如下:
可以看到图像中的很多噪音都被处理掉了,只剩下了边缘部分。
有了边缘之后,接下来就是通过轮廓定位图像中的二维码。二维码的 Position Detection Pattern 在寻找轮廓之后,应该是有6层(因为一条边缘会被识别出两个轮廓,外轮廓和内轮廓):
所以,如果简单处理的话,只要遍历图像的层级关系,然后嵌套层数大于等于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)
绘制结果如下:
接下来就是把所有找到的定位标记进行筛选。如果刚好找到三个那就可以直接跳过这一步了。然而,因为这张图比较特殊,找出了四个定位标记,所以需要排除一个错误答案。
讲真,如果只靠三个 Position Detection Pattern 组成的直角三角形,是没办法从这四个当中排除错误答案的。因为,一方面会有形变的影响,比如斜躺着的二维码,本身三个顶点连线就不是直角三角形;另一方面,极端情况下,多余的那个标记如果位置比较凑巧的话,完全和正确结果一模一样,比如下面这种情况:
所以我们需要 Timing Pattern 的帮助,也就是定位标记之间的黑白相间的那两条黑白相间的线。解决思路大致如下:
找的的定位标记是一个轮廓结果,由许多像素点组成。如果想找到定位标记的顶点,则需要找到定位标记的矩形包围盒。先通过 minAreaRect
函数将检查到的轮廓转换成最小矩形包围盒,并且绘制出来:
draw_img = img.copy()
for i in found:
rect = cv2.minAreaRect(contours[i])
box = cv2.boxPoints(rect)
box = np.int0(box)
cv2.drawContours(draw_img,[box], 0, (0,0,255), 2)
show(draw_img)
绘制如下:
这个矩形包围盒的四个坐标点就是顶点,将它存储在 boxes 中:
boxes = []
for i in found:
rect = cv2.minAreaRect(contours[i])
box = cv2.boxPoints(rect)
box = np.int0(box)
box = map(tuple, box)
boxes.append(box)
接下来先遍历所有顶点连线,然后从中选择最短的两根,并将它们绘制出来:
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):
# 存储 ab 数组里最短的两点的组合
s1_ab = ()
s2_ab = ()
# 存储 ab 数组里最短的两点的距离,用于比较
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]
# 将最短的两个线画出来
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)
绘制结果如下:
有了端点连线,接下来需要获取连线上的像素值,以便后面判断是否是 Timing Pattern 。
在这之前,为了更方便的判断黑白相间的情况,先对图像进行二值化:
th, bi_img = cv2.threshold(img_gray, 100, 255, cv2.THRESH_BINARY)
接下来是获取连线像素值。由于 OpenCV3 的 Python 库中没有 LineIterator
,只好自己写一个。在《 OpenCV 3.0 Python LineIterator 》这个问答里找到了可用的直线遍历函数,可以直接使用。
以一条 Timing Pattern 为例:
打印其像素点看下结果:
[ 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.]
照理说, Timing Pattern 的连线,像素值应该是黑白均匀相间才对,为什么是上面的这种一连一大片的结果呢?
仔细看下截图可以发现,由于取的是定位标记的外部包围盒的顶点,所以因为误差会超出定位标记的范围,导致没能正确定位到 Timing Pattern ,而是相邻的 Data 部分的像素点。
为了修正这部分误差,我们可以对端点坐标进行调整。因为 Position Detection Pattern 的大小是固定的,是一个 1-1-3-1-1 的黑白黑白黑相间的正方形,识别 Timing Pattern 的最佳端点应该是最靠里的黑色区域的中心位置,也就是图中的绿色虚线部分:
所以我们需要对端点坐标进行调整。调整方式是,将一个端点的 x 和 y 值向另一个端点的 x 和 y 值靠近 1/14 个单位距离,代码如下:
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)
调整之后的像素值就是正确的 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.]
像素序列拿到了,接下来就是判断它是否是 Timing Pattern 了。 Timing Pattern 的特征是黑白均匀相间,所以每段同色区域的计数结果应该相同,而且旋转拉伸平移都不会影响这个特征。
于是,验证方案是:
代码如下:
def isTimingPattern(line):
# 除去开头结尾的白色像素点
while line[0] != 0:
line = line[1:]
while line[-1] != 0:
line = line[:-1]
# 计数连续的黑白像素点
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
# 计算方差,根据离散程度判断是否是 Timing Pattern
threshold = 5
return np.var(c) < threshold
对前面的那条连线检测一下,计数数组为:
[11, 12, 11, 12, 11, 12, 11, 13, 11]
方差为 0.47 。其他非 Timing Pattern 的连线方差均大于 10 。
接下来就是利用前面的结果除去错误的定位标记了,只要两个定位标记的端点连线中能找到 Timing Pattern ,则这两个定位标记有效,把它们存进 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
结果是:
set([1, 2, 3])
好了,它们中出了一个叛徒,0、1、2、3 四个定位标记,0是无效的,1、2、3 才是需要识别的 QRCode 的定位标记。
有了定位标记之后,找出二维码就轻而易举了。只要找出三个定位标记轮廓的最小矩形包围盒,那就是二维码的位置了:
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)
绘制结果如下:
后面仿射变换后坐标修正的问题实在是写不动了,这篇就先到这里吧。
回头看看,是不是感觉绕了个大圈子?
『费了半天劲,只是为了告诉我第0个定位标记是无效的,我看图也看出来了啊!』
是的,不过代码里能看到的只是像素值和它们的坐标,为了排除这个错误答案确实花了不少功夫。
不过这也是我喜欢做数字图像处理的原因之一:可用函数数不胜数,专业概念层出不穷,同样的一个问题,不同的人去解决,就有着不同的答案,交流的过程便是学习的过程。
啊对了,如果有更好的解决方案,欢迎在评论里指出!
以及,文章里有一个红包彩蛋,你找到了吗 =。=
财富!名誉!地位!穷得叮当响的海贼汪,哥尔·D·汪海,他在临睡前的一句话让人们趋之若鹜奔向博客:『想要我的红包吗?想要的话可以全部给你,去找吧!我把所有红包都放在那里!』
参考文献: