薛江 王知衍 曹晓叶

(华南理工大学 计算机科学与工程学院，广东 广州 510006)

简化二维条码(简称Tcode)是一种用于手机上的基于二维条码思想的字符矩阵.传统二维条码在手机上只可以通过彩信传输，但与彩信相比短信有一定制约性，一是成本高(约10～20 倍以上)，二是成功到达率低.而基于手机字符的Tcode 是一种很好的替代方案.Tcode 在电子票据、电子优惠卷等电子凭证应用中将成为关键技术，在推动无线城市建设中起着关键作用［1］.

二维条码主要由编解码模块与识别模块组成［2］，传统的二维条码编解码模块设计的主要思想是对原始数据进行位流还原，再经过纠错编码后形成最终数据［3］.文中基本架构与之相似，但由于最终显示的是手机支持的常规字符，考虑到很多字符相似度很高(如字母O 和数字0)及最大限度地利用编码映射的特性，文中在编解码方案上基于传统二维条码的思想重新定义了适应于Tcode 的映射及编码方案.

二维条码识别的第一步就是基于定位算法的自动检测，传统二维条码定位算法有基于图像分块的边缘点检测算法［4-5］，基于边缘检测算子［6］的Hough变换找直线算法［7］及其改进算法［8］;另外，还有利用数学或形态学对图像进行版面分析、通过腐蚀或膨胀使条码区域形成一个连通域的方法，这种方法因计算简单而被广泛应用.由于Tcode 并没有明显边缘，而且算法需在嵌入式系统中使用，对实时响应要求很高，所以在文中并不能采用上述传统方法.文中字符矩阵设计时在矩阵三个角点加入了手机中唯一旋转不变的字符“实心黑圆点”(三点才可以确定矩阵的方向).为解决光照不均及背景复杂的问题，采用基于样本的滑动二值化算法来对输入图像二值化以保留定位点，再结合圆点滤波器及连通区域形状判定来确定定位点，并在定位的基础上将字符矩阵旋正.

字符切分是车牌识别和视频字符提取中的关键算法［9-11］.传统车牌字符切分时首先进行二值化处理，再利用一定的先验知识结合投影算法进行切分［12］.而从视频中提取字符需要由视频大小和经验值估计出字符的高度后再对其进行分割［13］.Tcode字符切分时，由于定位符不能与其他字符等宽，所以不能直接进行整体切分，而需要将整体切分思想与单独切分思想相结合来对整个字符矩阵进行切分.

文中首先给出了Tcode 的编码映射方案，然后详细讨论了识别过程中的关键算法，在定位算法中提出了基于采样阈值的分块滑动二值化算法来保留定位点，通过圆点滤波结合连通区域形状判定来寻找定位点，采用改进的投影法来进行字符切分.

1 Tcode 编码映射方案

1.1 定义Tcode

Tcode 是一种基于二维条码思想的字符矩阵.对原始信息经过编码后形成字符矩阵，在手机中以短信的方式传播，在终端识读器可以直接进行识别解码.

Tcode 在设计时主要考虑以下几个方面的因素:

(1)原始信息类型，支持数字、字母及其混合.

(2)支持最大信息长度.最大信息长度与矩阵大小、原始信息类型、显示字符个数及纠错等级有关.

1.2 编码方案

常用原始信息有大写字母A 至Z，小写字母a至z，数字0 至9，共62 个.对原始字符编码时采用压缩编码方式:即用4 b 可编码24=16 个字符，用5 b可编码25=32 个字符，用6 b 可编码26=64 个字符.显然，如果选用字母数字混合模式，需要按6 b方案进行编码，如果只需用到数字(或16 个以内的部分字母)，则只需要按4 b 的方案进行编码.

对原始信息按上述方案进行编码后，形成一个二进制的位流.使用Reed-Solomon 算法对其进行加密后可形成加密位流.

1.3 定义映射方案

经过上面的编码后，仍然不能在手机上直接显示，还需将其按规则映射成手机可以显示的字符.而用来映射的字符须从手机中可以显示的128 个ASCII 码字符中选取，且字符的个数必须为2N(这样才能保证传输的信息量最大)，而N 的取值决定于按多少位进行映射.即如果N=3，则选取8 个字符，对加密位流按3 位一次进行映射.

1.4 可传输的最大信息长度

设传输的最大信息长度为O(单位为B)，矩阵大小为W×H，选用的显示字符为V，纠错所需字节数为ECC(可纠错数为ECC/2)，定位符占用字节U，传输的最大信息长度计算公式如下(其中需对计算结果向下取整):

如果选择W=8，H=6，V=3，ECC=4，U=3，则O=12，如果只传输数字，按4 b 进行编码，则最多可传输12 ×(8/4)=24 个数字.

2 Tcode 定位识别算法

2.1 算法流程图

Tcode 定位识别算法流程图见图1.

图1 Tcode 识别算法流程图Fig.1 Flowchart of Tcode recognition algorithm

2.2 定位算法

定位算法在图像识别中起着关键作用.如在人耳识别中自动定位轮廓点，在人脸识别中自动定位眼睛［14］.定位算法是Tcode 识别的第一步，由于该算法需要连续运行，在实际使用中用户对该算法的等待时间往往是该算法运行时间的2 倍.原因是摄像头在捕捉到目标图像时，程序仍在处理上一帧图像，到处理完成当前帧图像时，定位算法运行了两次.故定位算法对效率要求尤其高.定位算法由三部分组成，每部分单独处理一个问题.首先由输入的原始图像得到二值化图像，要求二值化图像不能丢失定位点;然后是从图像中确定定位点位置;最后找出3 个定位点的实际对应关系，并根据旋转角度将图像旋正.在下文中未曾特别说明的θ 或θi都是一个判定阈值，取值依赖程序具体环境.

2.2.1 二值化

描述:已知输入RGB 彩色图像，求输入图像的二值化结果.

要求:输入图像是包含如图1 所示的圆点定位符的图像，二值化结果要保留圆点.

问题难点:由于光照不均，手机屏幕背景复杂，传统的全局阈值二值化算法经常会将圆点整体丢失或部分与背景融合.

文中采用基于中心采样阈值的分块滑动阈值二值化算法，算法描述如下.

(1)首先对图像取中心区域(大小为e×e)作为采样区域，由于字符区一定过图像中心区域，采用Otsu［15］法求得采样区域的阈值t 作为参考阈值.

(2)将原始图像进行分块(分成f ×f 块)，对每一块单独使用Otsu 法求得该区域的阈值ti.

(4)令t' =0.5(ti+t)，ti=t'，进入步骤(3).

2.2.2 求定位点位置

描述:已知二值化图像，求定位点位置.

要求:如果该二值化图像包含Tcode 定义的定位点，则求出其坐标位置.

问题难点:首先要找候选定位点，这一步中关键是将其他明显非定位点的区域排除;然后是在所有的候选定位点中找出真实的定位点.

文中采用连通区域标记结合圆点滤波算法来排除杂质区域，然后对候选点进行判定，最终求得真实定位点.算法描述如下.

(1)排除较大连通区域.对输入的二值图像进行连通区域标记，将明显太大的连通区域首先排除.判定条件为

其中Q 为连通区域的像素个数，R、L、T、J 分别为连通区域右、左、上、下边界的坐标，μ 为连通区域的半径，定义为Max(R-L，T-J).判定条件依次说明:连通区域不能太大，即像素个数不能超过一定范围;连通区域属于圆点，即上下长度和左右长度不能相差太大;连通区域不能是空心的，即其像素个数要和一个等半径圆的像素个数相似.

(2)排除较小连通区域.采用圆点滤波算法，将较小的杂质排除.定义一个圆点滤波模板，该模板和定位符相似，但较定位符稍小.用该模板对原图像执行滤波操作，只有符合模板形状(或包含模板)的连通区域被保留，其余部分被过滤.

(3)执行单点骨格化，即将每一个剩余的连通区域用其中心点代替，所得到点的坐标即为候选定位点坐标.

(4)判定候选点.将所有侯选点3 个一组进行判定，设候选点为p、q、k，rpq、rpk、rqk分别表示各点之间的距离.判定算法如下:首先求得最大的r =Max(rpq，rpk，rqk)，不失一般性，设r = rpq，再根据判定条件＜θ(由Tcode 定义知，3 个定位点满足等腰直角三角形)来判定候选点.

2.2.3 最终确定定位点及旋转角度

描述:已知3 个定位点A、B、C 坐标，求哪个是直角定位点，哪个是左下定位点，哪个是右上定位点，并求旋转角度.

文中定位点的选择主要是基于以下理由:由于一个或两个定位点都不能得到图像的旋转方向，所以要将图像旋转成正方向(即人类阅读方向)至少需要3 个定位点.定位点的安排一般是在4 个角点，而定位点与其他字符不能选择为等宽字符，原因是不同手机在接收短信后圆点都会被默认的字体格式所代替，所以包含定位点行的字符与其他行的字符并不对齐.观察发现，如果定位点只出现在某一行字符的尾部，则不影响该行与其它行对齐.为保证定位点能尽量放在行尾，其中的两个定位点可放在首行和尾行的行尾，而另一个定位点则只能放在行首，文中为了符合人类的观察习惯，将第3 个定位点放于尾行行首，即左下角.

文中算法首先确定直角定位点，然后再根据向量叉乘原则确定另外两个定位点，最后由另外两个定位点计算旋转角度θ(0≤θ ＜2 )，算法描述如下.

(1)计算3 条边的长度求得其最大值，假设A点所对边长度最大，则A 点为直角点，即为字符矩阵的右下角点.

(2)要确定B 点和C 点，可利用平面向量叉乘公式.平面向量的叉乘公式如下.

设点A 到点B 向量X =(a，b)，点A 到点C 向量Y=(c，d)，则

(3)要求得顺时针的旋转角度θ(0≤θ ＜2 )，只需将由A 点(右下角点，即直角点)与C 点(左下角点)确定的直线段旋转到水平方向，且C 在左，A 在右即可.由A(a，b)、C(c，d)首先求得sqrt((a-c)2+(b-d)2)，则锐角θ' = cos-1((a-，如果b ＞d，则θ=θ'，否则θ=2-θ'.

2.3 Tcode 字符切分算法

找到字符图像的定位点并将图像旋正之后，问题就转化为如何将字符区域进行切分，最终得到单个字符.字符切分主要解决三个问题:一是二值化后粘连字符的切分，二是二值化后一个字符被分割成不同连通区域的问题，三是二值化产生的噪声的去除.整个算法流程如下.

(1)将所得到的字符区域二值化.由于预先知道字符区主要由M ×N 个字符组成，所以首先将图像等分成M×N 份，对每份单独二值化，以避免光照不均等影响.

(2)将图像在水平方向进行投影，求得字符的高度及每行字符的起始位置坐标.注意到短信在每行都是等高的，且在投影后行与行之间的噪声点较少(相对于字符)，所以在进行投影判定时，可以直接设定一个阈值I，投影点数量大于I 的才认为是字符投影.求得M 行字符每行的起始与结束位置.

(3)由于图像的前N-1 行字符是等宽字符，可以对其进行统一切分，切分方法同步骤(2).并求得字符的平均宽度Z 和字符间的平均间距G.

(4)而对最后一行，由于它在两端都含有定位符，与其他行不等宽，需要单独切分.对一行字符进行单独切分时，由于字符在投影时产生的投影点数量不足以区分字符与字符间噪声，所以在设定阈值I 时，一些图像必然会在其投影后保留噪声点，而在另一些图像上将一个字符切分成两部分或更多部分.为解决此问题，需要进行步骤(5).

(5)设图像最后一行的垂直投影矩阵为D［M］，其中D［i］(0≤i ＜M)表示坐标i 处水平投影上点的个数.首先标记各段连通区域的起始点并计算其长度，假设得到K 段连通区域，每段的起点为S［i］(0≤i ＜K)，终点为F［i］(0≤i ＜K)，长度L［i］=F［i］-S［i］+1，首先确定长度为L［i］的线段是否为投影区域，L［i］约等于平均长度的一定为字符投影区域.找到部分(可能是全部)字符区域后，如果字符个数小于N，则需要继续查找字符.查找时以如下原则进行.首先查找字符内部的连通区域.即如果找到的E个字符从左开始起始编号为E1，终止编号为E2，从E1开始依次查找非字符的连通区域，每找到一块非字符连通区域P 后，判定它与离它最近的字符区域(在其左边)的间距是否约等于平均间距，如果是，则看它的下一块相邻区域P +1 是否同为非字符区域且与它最近的字符区域(在其右边)间距约等于平均间距，如果同样找到，则判定如果进行合并后产生的新区域长度F［P +1］-S［P］是否约等于平均长度，如果是，则进行合并并且认定它们合并后是一个字符区域.在判定过程中有一步不符合，则跳过该连通区域后继续往下查找.在将内部连通区域查找完之后，一般就找到了所有的字符区域.原因是该行的两端为两个实心黑圆点，二值化算法可以很好地保留该圆点.在投影后该圆点同样不会产生断裂.

(6)进行完整的切分之后，再对实际的每个字符单独二值化，可以得到较好的二值化结果.进行顶格裁剪(即将字符上下左右的空部分裁剪掉)后进行归一缩放.缩放到统一大小后即可进行模板匹配得到识别结果.

3 实验结果

为了验证文中提出的算法的有效性，进行了实验测试.文中程序远行环境为RC550，运行嵌入式wince6.0 系统，带一个摄像头用来进行光学字符识别(OCR)，硬件条件为:内存56 MB，处理器为基于ARM 的1176JZF-S-S3C6410，工作上频率可达667 MHz.所涉及的手机均为常见机型，包括基于IOS5.0 的iphone4(iphone 4S)，基于Andriod2.2 的Moto ME722，基于SybainS60 的Nokia5230 及非智能机Nokia5310XM 等各种机型.编程语言为VC++.

3.1 定位算法实验验证与分析

定位算法主要包括原始图像阈值分割、二值图像定位点位置的确定、以及最终定位点信息的还原，而图像阈值分割又是其中的核心部分.本实验将改进算法与图像分割中最常用的两种算法进行了对比，一种是基于直方图形状分析的方法，选取的是文献［16］的GVM 算法;另一种是基于测度空间聚焦度的方法，选取的是文献［15］的Otsu 算法.GVM 算法是将图像灰度直方图各个谷的深度作为准则函数，通过使用遍历方法求全局最大深度，从而得到阈值.而Otsu 算法同样采用遍历的方法，以类内方差和类间方差作为准则函数，当类内方差最小且类间方差最大时求得阈值.本实验选择了9 种不同情况的样本进行测试，如图2 所示，每行从左到右依次为经过处理的灰度图像、使用F 准则的GVM 算法测试结果、使用K 准则的GVM 算法测试结果、大津法测试结果以及文中算法的测试结果.

图2 二值化结果Fig.2 Binarization results

可以看出，当图像受光照不均影响时(见图2(b)、(c))，GVM 算法表现较差，而大津法也会受到一定影响;当图像杂质较多时(如图2(e))，GVM算法效果同样较差;当图像出现明显的三峰分布时(如图2(h))，GVM 算法和大津法都不能很好地获取目标.而文中算法利用中心字符作为样本区域，对图像进行分块，并利用滑动阈值法求取每块的阈值，能较好地解决上述情况下存在的问题.

3.2 关键算法实验效果展示

3.2.1 原始图像二值化

原始图像二值化的过程主要包括提取识别区域、目标图像灰度化、二值化保留定位点，如图3所示.

图3 原始图像二值化过程Fig.3 Binarization of original image

3.2.2 确定定位点

确定定位点主要有两个过程:一是去除较大连通区域以及模板滤波，二是单点骨格化后再对候选点进行判定，并通过平面向量叉乘原理分别确定3 个定位点.如图4 所示，3 个从大到小的白方格标示的点分别为右下角点、右上角点、左下角点.最终可以通过将定位点旋转至正方向而求出字符区.

图4 确定定位点过程Fig.4 Determination of anchor points

3.2.3 字符切分

字符切分主要是在二值化后将整体切分与单独切分相结合，从而求得切分结果，如图5 所示(右图结果已经过直方图增强处理).

图5 字符切分过程Fig.5 Character segmentation

3.3 系统整体表现

Tcode 的要求是，平均响应时间应该在1 s 以内，应该能对主流的手机短信进行识别.识读终端的应用设计是一个连续循环的响应设计，若识读正确则退出该循环，一旦识读过程中有一步识读失败都将返回循环开始处重新执行.其中，主要的几个可能失败点为:①原始图像二值化后定位点丢失;②疑似定位点太多导致难以确定最终定位点;③对图像投影后切分失败，包括行切分失败和列切分失败;④识读字符错误数量超过纠错等级.

笔者对机型进行分类，对基于IOS、Andrid 和Sybain 的手机分别进行了连续100 次的识读测试，得到两个重要的参数:0.5 s 内的识别率和1 s 内的识别率.3 种不同系统0.5 s 内的识别率依次为93%、89%、95%，平均识别率为92.4%;而1 s 内识别率依次为97%、93%、99%，平均识别率为96.2%.

4 结语

文中开发了一个嵌入式的简化二维条码编解码识别系统.其中，定位部分主要解决了二值化保留定位点、确定定位点位置以及求最终旋转角度的问题;而切分部分主要克服了字符二值化不理想造成的粘连等问题.实验部分将一些典型的二值化算法与文中改进算法进行了对比，验证了文中算法的可行性，并同时证明系统的响应时间是符合要求的.

显然，大规模地运用本系统，还需要在更复杂的环境中对更多的机型进行测试，同时也要对定位过程及切分过程实行进一步的优化.其中，定位过程优化包括传输信息量和信息种类的进一步提升、定位点的取消或精简、以及二值化时定位点更为高效准确的保留;而切分过程优化则要进一步提高切分的正确率和识别的正确率，并降低系统的影响时间.这些都是需要进一步研究的内容.

［1］许统.手机二维码在国内的发展及应用［J］.电脑与信息技术，2011，19(3):62-63，69.Xu Tong.Mobile two-dimensional bar code development and application in China［J］.Computer and Information Technology，2011，19(3):62-63，69.

［2］Hee Il Hahn，Joung Koo Joung.Implementation of algorithm to decode two-dimensional barcode PDF-417［C］∥Proceedings of 2002 6th International Conference on Signal Processing.［S.l.］:IEEE，2002:1791-1794.

［3］刘悦，刘明业.QR code 二维条码数据编码的研究［J］.北京理工大学学报，2005，25(4):352-355.Liu Yue，Liu Ming-ye.Research on data encoding of twodimensional QR code barcode［J］.Transactions of Beijing Institute of Technology，2005，25(4):352-355.

［4］刘宁钟.复杂背景中条码检测定位技术的研究［J］.南京航空航天大学学报，2005，37(1):65-69.Liu Ning-zhong.Detection and localization of bar code in complicated background［J］.Journal of Nanjing University of Aeronautics ＆ Astronautics，2005，37(1):65-69.

［5］Sun Ai-dong，Sun Yan，Liu Cai-xing.The QR-code reorganization in illegible snapshots taken by mobile phones［C］∥Proceeding of Fifth International Conference on Computational Science and Applications.Washington D C:IEEE，2007:532-536.

［6］胡东红，谭辉，陈莘萌.Radon 变换在二维条码图像识别中的应用［J］.武汉大学学报:理学版，2005，51(5):584-588.Hu Dong-hong，Tan Hui，Chen Xin-meng.The application of Radon transform in 2D barcode image recognition［J］.Journal of Wuhan University:Natural Science Edition，2005，51(5):584-588.

［7］Ballard D H.Generalizing the Hough transform to detect arbitrary shapes［J］.Pattern Recognition，1981，13(2):111-122.

［8］Heikki Kälviäinen，Petri Hirvonen，Erkki Oja.Houghtool—a software package for the use of the Hough trans-form［J］.Pattern Recognition Letters，1996，17(8):889-897.

［9］骆雪超，刘桂雄，冯云庆，等.一种基于车牌特征信息的车牌识别方法［J］.华南理工大学学报:自然科学版，2003，31(4):70-73.Luo Xue-chao，Liu Gui-xiong，Feng Yun-qing，et al.A vehicle license plate recognition method based on the characteristics of vehicle license plate［J］.Journal of South China University of Technology:Natural Science Edition，2003，31(4):70-73.

［10］秦钟，徐建闽，史胜利，等.基于字符角点信息的车牌定位方法［J］.华南理工大学学报:自然科学版，2006，34(4):19-23.Qin Zhong，Xu Jian-min，Shi Sheng-li，et al.Locating of license plate based on character corner information［J］.Journal of South China University of Technology:Natural Science Edition，2006，34(4):19-23.

［11］陶泽明，裴玉龙.事故车辆图像特征点的自动匹配［J］.华南理工大学学报:自然科学版，2009，37(3):138-143.Tao Ze-ming，Pei Yu-long.Automatic matching of image feature points of accident vehicle［J］.Journal of South China University of Technology:Natural Science Edition，2009，37(3):138-143.

［12］任明亮，范勇，蒋欣荣，等.一种快速精确的汽车牌照字符切分算法［J］.四川大学学报:自然科学版，2002，39(3):450-454.Ren Ming-liang，Fan Yong，Jiang Xin-rong，et al.A fast algorithm for accurate char segmentation of license plate［J］.Journal of Sichuan University:Natural Science Edition，2002，39(3):450-454.

［13］杨武夷，张树武.一种视频中字符的集成型切分与识别算法［J］.自动化学报，2010，36(10):1468-1476.Yang Wu-yi，Zhang Shu-wu.An integrated segmentation and recognition algorithm for text in video［J］.Acta Automatica Sinica，2010，36(10):1468-1476.

［14］Kyong Chang，Kevin W Bowyer，Sudeep Sarkar.Barnabas Victor，comparison and combination of ear and face images in appearance-based biometrics［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25(9):1160-1165.

［15］Otsu.A threshold selection method from gray-level histograms［J］.IEEE Transactions on Systems，Man and Cybernetics，1979，9(1):62-66.

［16］Davies E R.Stable bi-level and multi-level thresholding of images using a new global transformation ［J］.IET Computer Vision，2008，2(2):60-74.