模板匹配算法的改进及在自动发牌机中的应用

侯智新，李媛媛

(长安大学 陕西 西安 710064)

模板匹配算法的改进及在自动发牌机中的应用

侯智新，李媛媛

(长安大学 陕西 西安 710064)

自动发牌机是基于数字图像处理的智能化体育比赛辅助用具，使用传统模板匹配算法的自动发牌机，由于算法中存在大量无效运算，使得扑克识别耗时较长。本文提出采用区域隔行扫描序贯算法改进模板匹配算法，极大地降低了识别时间，提高了识别准确率。

图象识别；模板匹配；自动发牌机；ARM平台

现代桥牌已远远超出了游戏的范畴，而成为有严格规则的世界性体育比赛项目。以全国高校教职工桥牌比赛为例，仅决赛就采用12桌米切尔制，打11轮22副牌，这样每天需要用的桥牌数量就是相当大的一个数目。因此，不论在平时娱乐还是在大型比赛时，发牌就成了巨大的工作。

市面上的自动发牌机主要有两种[1]，一种是没有图像处理设备，仅通过发牌机把牌依次发放到相应方位而已，不能实现指定排序的发放；另一种是基于图像处理的扑克识别，可以发指定牌序，但存在着大量计算，在实时性要求下需要连接电脑来做识别工作，使得自动发牌机造价昂贵且携带不便。对此，提出了一种基于模板匹配的区域隔行扫描序贯算法，设计出一种满足实时性要求的本地识别且可以用于所有类型扑克的自动发牌机。

1 基于模板匹配算法的扑克牌识别

1.1 模板匹配算法

简单而言，模板就是一幅已知的小图像。模板匹配[2]就是在一幅大图像中搜寻目标，已知该图中有要找的目标，且该目标同模板有相同的尺寸、方向和图像，通过一定的算法可以在图中找到目标，确定其坐标位置。模板匹配常用的一种测度为模板与源图像对应区域的误差平方和。设f(x,y)为M*N的源图像，t(j,k)为J*K的模板图像，则归一化互相关作为误差平方和测度[3]，其定义为：

当x和y变化时，t(j,k)在源图像区域中移动并得出R(x,y)所有值。R(x,y)的最大值便指出了与t(j,k)匹配的最佳位置。

1.2 基于模板匹配算法的扑克牌花色和点数识别

传统的模板匹配算法[4]应用于自动发牌机时，是用已经保存的花色模板和点数模板分别对一张扑克图片进行模板匹配，遍历扑克图的每一点，而且需要遍历每一个模板，得到最大的R值，分别找到扑克图的最佳匹配花色和最佳匹配点数。其中R为0到1的数字，当R为1时表示模板完全匹配。匹配时，源图像和模板都是预处理后二值化的图像。

以花色匹配为例， 模板为：t1、t2、t3、t4、t5分别表示黑桃、红桃、梅花、方块和JOKER的花色模板。花色匹配时，首先找出t1模板在扑克图像上的最佳匹配值R1，然后依次找出所有花色模板的最大匹配值 R2、R3、R4和 R5，比较得出最大的，其下标i就表示这张扑克的最佳匹配花色。点数匹配原理与花色匹配原理一致。

1.3 算法存在的问题

用归一化互相关求匹配的计算工作量非常大，因为模板要在(M-J+1)*(N-K+1)个参考位置上做相关运算，且花色匹配时运算量还要增加为5倍，点数匹配时更要增加为13倍，实际测试时，在嵌入式 环境下的 上运行 识别的源图像分辨率为320×240，模板图像分比率为40*60时，在识别前和识别后分别打印出时间可以得到：识别扑克点数需要耗时43秒，这完全不在可以接受的范围内。而同样的算法的程序在酷睿i3的笔记本上仅耗时1 s不到，不难看出，嵌入式系统由于其运算能力的限制，需要精简优化的识别算法才能在扑克识别应用上满足实时性要求。

2 模板匹配算法的改进

2.1 特定区域匹配

在归一化互相关求匹配的计算中，除了最佳匹配点以外，其余做的都是无效运算。在本系统的应用中，一帧图像分辨率为320×240，视频流中抓取的一幅待识别的灰度图像如图1所示。

图1 原始采样图像Fig.1 Chart of original picture

而需要进行匹配计算的仅仅位于图像的左上角部分，系统在拍照的时候为定距离定角度，且扑克牌为中心对称图像，所以在识别点数的时候仅对源图像的左上角部分进行归一化互相关求匹配计算，需要计算的图像范围约为原图像的15%左右，这样计算量就缩减为原算法的15%左右。

2.2 隔行扫描匹配

在最佳模板匹配指定扑克时候，把源图像每一个像素点处的R值映射到像素空间，R的理论范围为0到1，把R值映射到灰度空间从0x00(黑色)到0xff(白色)。实际测试发现，R值实际在0.6到1之间，为了增加对比度，把R(x,y)值映射到灰度空间的方法为：

其中，Gray为映射后的灰度值，255为十六进制0xff的十进制表示。这样组成一幅匹配值R图，R值越高，对应像素点的灰度越大，在图片上显示就越白。最佳匹配点出的R值最大，得到的匹配值R图中对应的最佳匹配点处颜色最白。对图1中图像绘制的匹配值R图如图2所示。

图2 对应的匹配值R图Fig.2 Chart of corresponding marching value R

图像中最右边和最下边的灰色为初始图像，设置初始灰度为0x7f，模板匹配算法中，横向需要减去模板宽度，纵向需要减去模板高度来匹配，故右下边缘不进行匹配运算，得到的匹配值R图有边缘。通过匹配值R图可以知道：只有在最佳匹配点处R取得最大值，同时也是附近区域的极大值。打印出最佳匹配点附近的R值，观察最大值处R的逼近过程，如图3所示。

图3 最佳匹配逼近过程记录图Fig.3 Chart of best matching approximation process record

可以看到：第13×19个像素点可以取到最大的R值，而这一像素点在第13列及第19行也为极大值。为了减少运算，可以进行隔行匹配，仅计算第 11、13、15列和第 17、19、21行相交的像素。这样取得的最大值仍在实际最大值附近，不影响匹配结果的前提下减少了运算量。一张m*n分辨率的图像，匹配一个像素点的时间设为t，则匹配整个图像的时间他T1=m*n*t。新算法下，行列匹配时分别隔a行，b列，则新算法下匹配时间T2为：

应用于点数匹配时，a=1，b=1；应用于花色匹配时，a=2，b=1。

2.3 序贯抽样匹配

在多模板匹配时，记录每一个模板的最佳匹配点出的R值，将其打印出来，发现最佳匹配模板的最佳匹配点处的R值基本在0.915以上，而其他模板的最佳匹配点值在0.85以下。这样，可以继续优化算法为：当检测到某个模板的某个点出的R值为0.915以上时，就认为已经找到了最佳匹配的模板，停止本张图像的其他识别工作，以减少识别时间。本系统花色匹配模板的顺序为方块、梅花、红桃、黑桃、王，点数匹配模板的顺序为A、2…Q、K，这样，在识别方块A的时候，首先匹配花色模板，先匹配方块模板，R值为0.915以上，认为已经匹配成功，然后匹配点数，先匹配A点模板，R值为 以上，这样，花色和点数都仅匹配一次即可识别，计算量减少为原来的1/4*13，即1.2%，而识别黑桃K的计算量没有变。

3 基于改进算法的自动发牌系统设计

3.1 硬件系统结构

自动发牌机工作时，一沓牌花色朝下放入母牌盒，光电检测机构自动对最下面的一张牌进行拍照并传递数据给处理器以做判决，判决输出到执行传动装置，取出一张牌，经传动装置传输到对应的牌套上方落下，牌套上方有四组光电传感器，当扑克落入牌套中，传感器会触发并传输信号给控制器，当扑克落入正确位置后会开始下一张扑克的发送过程。这样经过一系列的操作，一张牌就正确的送入了牌套的指定位置中。自动发牌机的系统框图如图4所示。

图4 发牌机系统框图Fig.4 Schematic diagram of automatic cards dealer

本自动发牌机系统设计以三星公司的S3C6410为开发平台，辅以必要的外围电路，运行嵌入式LINUX系统，并连接摄像头进行拍照分析，实现对扑克的自动识别。

3.2 系统工作流程

本次设计的自动发牌机方案为在本地可以识别普通扑克并根据需要发送扑克的方案。其软件流程图如图5所示。

图5 系统软件流程图Fig.5 Flow chart of the system software design

系统开始时，对一切设备和参数进行初始化，并载入事先保存好的花色模板，载入已经保存的训练牌库。然后利用V4L2，在linux下开启摄像头，完成视频预览。由于系统用的是USB摄像头，输出的视频格式为YUV422，故从视频流中读取一帧图片后首先转化为RGB用于显示。其中读视频帧用了内存映射技术，使应用程序可以直接访问设备内存，减少了从内核态到用户态的数据拷贝，提高了运行速度。把每一帧图像都重绘在屏幕上，这样就完成了视频的预览。

当初始化完毕开始发牌时，或者上一张牌成功发送后，对接下来的一帧图像进行图像预处理。包括图像的灰度化，二值化。

接着，对二值图像进行分割，由于本系统的母牌储存盒与摄像头间的距离为固定距离，且本系统运行在嵌入式linux平台上，基于识别速度的考虑，设置摄像头和扑克牌关系为定距离定角度的拍摄，这样，就免去了扑克图像边缘增效，霍夫变换和图像旋转等操作，大大简化了预处理流程，提高了识别速度。

然后就是利用模板匹配的方法对当前帧图像进行识别，其识别具体算法将在后文介绍。识别出扑克的点数和花色后，根据预先设计的牌库，把指定的牌应发送的位置信息传递给传动装置，使其正确发送。

当指定位置牌位的传感器接收到牌已经正确发送的信号后，传递给系统，此时，开始抓取下一帧图像，进行下一张扑克的识别和发送。若2秒内系统没有收到传感器发送来的扑克正确入位的信号时，在LCD显示屏上给出警告信号，说明发送失败。当所有的牌都已经发送完毕时，在LCD显示屏上给出提示信息，表示已经成功完成发牌。

3.3 设计实现

本次设计的自动发牌机可以使用市面上任意品种的扑克牌，其原理就是获取一套特定牌的模板即可。不同厂家生产的扑克，虽然花色及点数的样子不完全一样，但是同一副扑克所有的同类牌都一样，如图6所示。

图6 模板获取流程图Fig.6 Flow chart of the template acquisition

模板的获取方法为：把一副牌按照黑、红、梅、方，且按照点数从A、2…到K的顺序放好，放入母牌盒，选择获取模板按钮。此时，发牌机的工作流程如图7所示为。

读取图像后，进行灰度化，滤波去噪、边缘增强，二值化，图像分割等步骤，获取到仅包含花色和仅包含点数的两张小图片，保存为jpg文件到SD卡中，并记录对应模板的文件名。然后把这张牌移动到牌套里，开始读取下一张的工作。这样等到全部读取完毕，就可以得到一套新的扑克模板。

4 测试分析

在6410上运行本程序以检测基于改进模板匹配算法的自动发牌系统的扑克识别的鲁棒性和实时性是否满足要求，测试结果如表1所示。

表1 测试结果Tab.1 Test result of poker recognition

通过两组测试可以发现基于改进模板匹配算法的自动发牌系统的扑克识别，其识别准确率高，识别速度快，可以满足实际使用要求。

5 结论

对传统模板匹配算法的三点改进：特定区域匹配，隔行扫描匹配及序贯抽样匹配，经测试验证，有效的提高了在嵌入式平台上进行扑克识别的速度，而不降低其识别鲁棒性。设计的自动发牌系统能满足扑克自动识别、指定发牌的要求，系统可靠、有效。

[1]寇永军.图像识别在发牌机上的应用研究[D].长沙 湖南大学,2006.

[2]田娟,郑郁正.模板匹配技术在图像识别中的应用 [J].传感器与微系统,2008,27(1):112-114.

TIAN Juan,ZHENG Yu-zheng.Application oftemplate matching technique in image recognition[J].Transducer and Microsystems Technologies,2008,27(1):112-114.

[3]陈国彬,张广泉.一种基于特征加权模板匹配方法在纸币字符识别中的应用 [J].微电子学与计算机,2013,30(3):115-117.

CHEN Guo-bin,ZHANG Guang-quan.Application of Paper Currency Character Recognition Based on Feature Weight Template Matching[J].Microelectronics&Computer,2013,30(3):115-117.

[4]蒋美君,蒋廷彪.高鲁棒的实时扑克字符识别方法研究[J].桂林电子科技大学学报,2011,31(5):377-381.

JIANG Mei-jun,JIANG Yan-biao.Research on robust recognition method of real-time poker image characters[J].Journal of Guilin University of Electronic Technology,2011,31(5):377-381.

[5]郝俊,孟传良.基于V4L2的ARM11USB视频采集终端的设计与实现[J].贵州大学学报:自然科学版,2011,28(4):74-78.

HAO Jun,MENG Chuan-liang.Design and Implement of the ARM11 USB Video Capture Terminal Based on V4L2[J].Journal of Guizhou University：Natural Science,2011,28(4):74-78.

[6]张玉萍,邹澎.基于Qt/Embedded视频采集方案的设计与实现[J].电视技术,2012,36(23):65-68.

ZHANG Yu-ping,ZOU Peng.Design and IMplementation of Video Capture Programs Based on Qt/Embedded[J].Video Engineering,2012,23(36):65-68.

Improve of template matching arithmetic and applied in Automatic cards dealer

HOU Zhi-xin，LI Yuan-yuan
(Chang’An University,Xi’an 710064,China)

The automatic cards dealer machine is an intelligent sports aids based on digital image processing,using traditional template matching algorithm leads to a large number of invalid algorithm and it take a long time to realize poker recognition.This paper propose a regional interlaced scanning sequential algorithm to improve the template matching algorithm,which can reduce the recognition time greatly and improve recognition accuracy efficaciously.

Image identification;Template matching;Automatic cards dealer;ARM

TP391.4

A

1674-6236（2014）13-0145-04

2014-01-07 稿件编号：201401056

陕西省科技攻关（2013K06-27，2012K09-07）

侯智新（1990—），男，陕西潼关人，硕士研究生。研究方向：信号与信息处理、计算机测控。