一种基于三维小波变换的视频编码新方法.pdf
史志锋
摘要： 传统的QR码识别算法只适用于打印在平面上的条码，提出了一种有效识别打印在饮料瓶等圆柱面上的QR码。通过对图像轮廓进行角点检测确定回字定位图形，在此基础上筛选条码关键轮廓并对其进行霍夫变换提取圆柱面上的透视椭圆信息，同时结合透视椭圆的参数和三维透视变换，有效构建了圆柱面条码像素从二维图像平面直接映射到三维图像空间的变换矩阵，重构打印在平面或圆柱面上的QR码目标。实验结果表明，该算法对平面或圆柱面QR条码的识别有较高的准确率。
关键词： QR码提取； 霍夫变换； 圆柱面； 三维透视变换
中图分类号： TN919⁃34 文献标识码： A文章编号： 1004⁃373X（2014）08⁃0015⁃04
Recognition of QR codes on cylindrical surface based on 3D perspective transformation
SHI Zhi⁃feng
（Department of Electronic Engineering， Xiamen University， Xiamen 361005， China）
Abstract： Traditional QR code recognition algorithm is usually applied to the barcode printed on flat surface only. A low⁃cost approach to recognize the curved QR codes printed on bottles or cans is proposed in this paper. The width proportion and corners of image contours are extracted to confirm the positioning patterns and an efficient Hough transformation ellipse fitting method is employed to extract the elliptic information. In combination with the parameters of perspective ellipse and 3D perspective transformation， the transformation matrix of barcode pixels on a cylindrical surface is constructed by direct mapping from the 2D image plane to 3D image space. The experiment result proves the algorithm has the high⁃accuracy recognition ability of barcodes no matter on the flat or the cylindrical surface.
Keywords： QR code extraction； Hough transform； cylindrical surface； 3D perspective transformation
QR码作为一种成本低廉、识别率高的二维条码，在智能的系统中发挥着重大的作用[1]。识别QR码的关键问题就是定位和校正，QR码通常被打印在平面或圆柱面上，对于平面QR码。文献[2]利用霍夫变换定位出条码的四个角，但该方法要求图像中只存在一个条码并且条码背景简单；文献[3]将条码图像分拆成多块并使用边界检测的方法找出条码的四角；文献[4]通过Candy边界检测提取条码的外部轮廓；文献[5]利用条码的梯度特征获得条码区域。但这些方法只能识别平面QR码。当条码被打印在瓶子等圆柱面上时，使用传统透视变换方法将导致条码信息定位错误。文献[1]通过检测寻像图形（timing pattern）来获取采样点信息，但这种方法对寻像图形的清晰度十分敏感。本文利用定位图形（finder pattern）的轮廓特征，通过改进的霍夫变换提取条码的轮廓，并通过三维透视变换的方法将条码采样点的信息映射到原图，针对平面和圆柱面的条码提取有较好的效果。
1条码定位
QR码的结构如图 1所示， 包含回字型的定位图形（finder pattern）以及黑白相间的寻像图形（timing pattern），还包含版本、格式等信息[6]。
图1 QR码的符号结构
在图像预处理阶段，利用自适应门限提取[7]的方法将灰度源图像转换为二值图像，并通过轮廓追踪[8]记录所有的轮廓点信息，经过这些处理后，利用每个闭合轮廓的重心位置和角点信息获得定位图形的位置及其对应的轮廓。
1.1定位图形提取
定位图形有很明显的特征：三个闭合轮廓有相同的重心。轮廓的重心可以通过式（1）计算得出[9]：
[gx=xyx⋅f(x,y)xyf(x,y) ， gy=xyy⋅f(x,y)xyf(x,y)] （1）
式中：[gx]和[gy]分别代表重心点的x，y轴坐标；[f(x,y)]是[(x,y)]处图像的灰度值。在轮廓图像中取逻辑值0或1，因此式（1）可以简化为：
[gx=1ni=1nxi， gy=1ni=1nyi] （2）
式中：n为轮廓上的像素个数。
将重心重合的几个轮廓作为候选轮廓，使用角点检测[10]的方法得出轮廓中的角点位置：一个轮廓可以表述为n个点的集合[P={pi=(xi,yi),i=1,2,…,n}]，轮廓中的一定相邻点构成的线段有一个协方差矩阵：
[C=c11c12c21c22] （3）
[c11=[12k+1i=-kkxi2]-[12k+1i=-kkxi]2 c12=[12k+1i=-kkxi⋅yi]-[12k+1i=-kkxi]⋅[12k+1i=-kkyi]c21=c12c22=[12k+1i=-kkyi2]-[12k+1i=-kkyi]2] （4）
矩阵C的两个特征值可以用来获取线段的形状信息，较小的特征值[λs]可以用来表述线段在某点处的尖锐程度[10]：
[λs=12[c11+c22-(c11-c22)2+4c212]] （5）
因此当某点处的[λs]大于某预设值并比附近点的[λs]都大时认为该点是轮廓的一个角点。图2说明定位图形的提取结果：轮廓的重心使用+标出，角点使用*标出。
1.2条码边界提取
在定位图形轮廓已知的基础上使用霍夫变换[11]用于提取条码的边界。霍夫变换将线上的点变换到参数空间，并投票计算最有可能的直线或曲线方程。以直线为例，直线可以描述为[ρi=xcosθi+ysinθi]，其中[ρi]表示直线到原点的距离，而[θi]表示直线与y轴的夹角。通过计算每个点（x，y）对应的参数空间（ρ，θ）的可能值进行累加比较最终得出（ρ，θ）的取值并确定直线。霍夫变换同样适用于曲线的提取[12]。
图2 定位图形的提取结果
传统的霍夫变换计算量较大，可以通过缩小参数空间的方法来减小计算量[13]，由于本文的定位图形的轮廓已知，可以利用该信息计算出可能的参数空间取值组合，再针对该缩小的参数空间使用霍夫变换，最终得到轮廓的方程，大大减小计算量。使用上述方法提取出的轮廓如图 3所示。
图3 提取出的轮廓
2条码几何校正
当摄像头的角度或方向不是正对条码时，捕获的图像就存在失真，利用反透视变换[14]可以校正条码实际采样点的位置以重构条码。在使用线性摄像头拍摄条码的场景中，可以使用3×4的矩阵来建模从世界坐标到图像坐标的变换，这个矩阵称为射影矩阵[14]：
[kuv1=m11m12m13m14m21m22m23m24m31m32m33m34xyz1]（6）
式中：u和v代表一个点在图像平面中的坐标值； （x，y，z） 描述了这个点在世界坐标系中的位置；k为比例系数；[m11]~[m34]构成了射影矩阵。
2.1平面条码的采样点提取
当条码打印在平面上时，式（6）中的z轴坐标全为0，可以化简为式（7）：
[kuv1=m11m12m13m21m22m23m31m32m33xy1]（7）
将式中的k消去，可以得到式（8）所描述的关系：
[x1y11000-u1x1-u1y1…………………………………………xnyn1000-unxn-unyn000x1y11-u1x1-u1y1…………………………………………000xnyn1-unxn-unynm11m12m13m21m22m23m31m32=m33u1u2…unv1v2…vn] （8）
可以令[m33=1]（[k]乘以某个系数），那么式（8）变成了有8个未知数的方程，因此只要得到4个点在两个坐标系中的对应位置[(xi,yi)][(ui,vi)]，就可以解出射影矩阵[m11]~[m32]（这里可以利用条码轮廓四个角对应的坐标），进而获得所有条码采样点对应到图像平面的坐标，其映射关系可以描述为：
[u=m11x+m12y+m13m31x+m32y+1 , v=m21x+m22y+m23m31x+m32y+1]（9）
2.2圆柱面条码的采样点提取
当条码被印刷在圆柱面上时，采样点的提取过程和平面类似。不同的是，需要考虑世界坐标系中z轴取值，此时射影矩阵的大小变为3×4，因而需要6个点的对应关系来解出11个未知数的方程，在之前4个点的基础上增加两个定位图形的角点作为输入。类似的，u和v可以通过式（10）计算出来：
[u=m11x+m12y+m13z+m14m31x+m32y+m33z+1 , v=m21x+m22y+m23z+m24m31x+m32y+m33z+1]（10）
为了获取6个点在世界坐标系中的坐标，将世界坐标系的三个轴定为图 4所示的位置，将条码的轮廓边长归一化，于是圆柱面上点的坐标值x，y，z可以通过半径r计算出来，将r作为一个未知数代入，可以得到一个12元方程，并解出射影矩阵。
图4 圆柱曲面条码的坐标示意图
将归一化的条码图像中的采样点反向映射到原图中得到二进制值，并按照QR码的解码规则提取出条码中的信息。
3结果与分析
使用本文算法对平面和圆柱面条码处理的效果如图 5和图 6所示，图 5中打印在条码上点标记了使用本文算法后获得圆柱表面条码的各模块采样点。而图 6则分别显示了使用本文算法对平面、圆柱面条码处理之后重构出的新条码。
图 5和图 6都说明该算法能较好的得到平面或圆柱面条码的模块采样点进而完成条码的重构。
图5 圆柱面条码处理后的采样点
图6 圆柱面条码的解码结果
为进一步验证算法的效果，针对平面和圆柱表面分别获取在各种不同大小的图像进行处理识别，并和文献[1]的BSE算法以及开源QR码识别库libqrencode比较。
图7解码结果表明，算法不仅对平面条码具有很好的识别能力，对圆柱面条码也具有较强的适应性。与文献[1]相比，识别圆柱面条码的准确率不依赖寻像图形的清晰度，能提高识别系统的鲁棒性。
图7 圆柱面条码和平面条码的识别率比较
参考文献
[1] CHU C H， YANG D N， PAN Ya⁃lan， et al. Stabilization and extraction of 2D barcodes for camera phones [J]. ACM Multimedia System Journal， 2011， 2： 113⁃133.
[2] WANG Hao， ZOU Yan⁃ming. Camera readable 2D bar codes design and decoding for mobile phones [C]// Proceedings of International Conference on Image Processing. [S.l.]： ICIP， 2006： 469⁃472.
[3] CHANG Yu⁃Hsuan， CHU Chung⁃Hua， CHEN Ming⁃Syan. A general scheme for extracting QR code from a non⁃uniform background in Camre phones and applications [C]// Ninth IEEE International Symposium on Multimedia. [S.l.]： IEEE， 2007： 123⁃130.
[4] SUN Ai⁃dong， SUN Yan， LIU Cai⁃xing. The QR⁃code reorganization in illegible snapshots taken by mobile phone [C]// International Conference on Computational Science and its Applications. S.l.]： ICCSA， 2007： 532⁃538.
[5] OUAVIANI E， PAVAN A， BOTTAZZI M， et al. A common image processing framework for 2D barcode reading [C]// Seventh International Conference on Image Processing and Its Applications.[S.l.]： ICIPA， 1999： 652⁃655.
[6] ISO. International Standard ISO/IEC 18004 [S/OL]. [2013⁃12⁃06]. http：//www.eweima.com/thread⁃8293⁃1⁃1.
[7] BRADLEY Derek， ROTH Gerhard. Adaptive thresholding using the integral image [J]. Journal of Graphics， GPU & Game Tools， 2007， 2： 13⁃21.
[8] CHANG Fu， CHEN Chun⁃Jen. A component⁃labeling algorithm using contour tracing technique [C]// Seventh International Conference on Document Analysis and Recognition. [S.l.]： ICDAR， 2003： 741⁃745.
[9] 谷口庆治.数字图像处理——应用篇[M].北京：科学出版社， 2002.
[10] TSAI Du⁃ming， HOU H T， SU H J. Boundary⁃based corner detection using eigenvalues of covariance matrices [J]. Pattern Recognition Letters， 1999， 1： 31⁃40.
[11] DUDA R O， HART P E. Use of the hough transformation to detect lines and curves in pictures [J]. Comm， ACM， 1972， 15： 11⁃15.
[12] GONZALEZ R C，WOODS R E.数字图像处理[M].2版.北京： 电子工业出版社，2007.
[13] 孙明，傅隆生，杨信廷，等.用于QR码自动识读的图像分析方法[J].电子科技大学学报，2009（6）：123⁃126.
[14] SONKA Milan， HLAVAC Vaclav， BOYLE Roger. Image processing， analysis and machine vision [M]. Third Edition. [S.l.]： Thomson Learning， 2008.
[15] LIAO Zhao⁃lai， HUANG Ting⁃lei， WANG Rui， et al. A method of image analysis for QR code recognition [C]// 2010 International Conference on Intelligent Computing and Integrated Systems. [S.l.]： ICISS， 2010： 250⁃253.
[7] BRADLEY Derek， ROTH Gerhard. Adaptive thresholding using the integral image [J]. Journal of Graphics， GPU & Game Tools， 2007， 2： 13⁃21.
[8] CHANG Fu， CHEN Chun⁃Jen. A component⁃labeling algorithm using contour tracing technique [C]// Seventh International Conference on Document Analysis and Recognition. [S.l.]： ICDAR， 2003： 741⁃745.
[9] 谷口庆治.数字图像处理——应用篇[M].北京：科学出版社， 2002.
[10] TSAI Du⁃ming， HOU H T， SU H J. Boundary⁃based corner detection using eigenvalues of covariance matrices [J]. Pattern Recognition Letters， 1999， 1： 31⁃40.
[11] DUDA R O， HART P E. Use of the hough transformation to detect lines and curves in pictures [J]. Comm， ACM， 1972， 15： 11⁃15.
[12] GONZALEZ R C，WOODS R E.数字图像处理[M].2版.北京： 电子工业出版社，2007.
[13] 孙明，傅隆生，杨信廷，等.用于QR码自动识读的图像分析方法[J].电子科技大学学报，2009（6）：123⁃126.
[14] SONKA Milan， HLAVAC Vaclav， BOYLE Roger. Image processing， analysis and machine vision [M]. Third Edition. [S.l.]： Thomson Learning， 2008.
[15] LIAO Zhao⁃lai， HUANG Ting⁃lei， WANG Rui， et al. A method of image analysis for QR code recognition [C]// 2010 International Conference on Intelligent Computing and Integrated Systems. [S.l.]： ICISS， 2010： 250⁃253.
[7] BRADLEY Derek， ROTH Gerhard. Adaptive thresholding using the integral image [J]. Journal of Graphics， GPU & Game Tools， 2007， 2： 13⁃21.
[8] CHANG Fu， CHEN Chun⁃Jen. A component⁃labeling algorithm using contour tracing technique [C]// Seventh International Conference on Document Analysis and Recognition. [S.l.]： ICDAR， 2003： 741⁃745.
[9] 谷口庆治.数字图像处理——应用篇[M].北京：科学出版社， 2002.
[10] TSAI Du⁃ming， HOU H T， SU H J. Boundary⁃based corner detection using eigenvalues of covariance matrices [J]. Pattern Recognition Letters， 1999， 1： 31⁃40.
[11] DUDA R O， HART P E. Use of the hough transformation to detect lines and curves in pictures [J]. Comm， ACM， 1972， 15： 11⁃15.
[12] GONZALEZ R C，WOODS R E.数字图像处理[M].2版.北京： 电子工业出版社，2007.
[13] 孙明，傅隆生，杨信廷，等.用于QR码自动识读的图像分析方法[J].电子科技大学学报，2009（6）：123⁃126.
[14] SONKA Milan， HLAVAC Vaclav， BOYLE Roger. Image processing， analysis and machine vision [M]. Third Edition. [S.l.]： Thomson Learning， 2008.
[15] LIAO Zhao⁃lai， HUANG Ting⁃lei， WANG Rui， et al. A method of image analysis for QR code recognition [C]// 2010 International Conference on Intelligent Computing and Integrated Systems. [S.l.]： ICISS， 2010： 250⁃253.
