侯智新，李媛媛

(長(zhǎng)安大學(xué) 陜西 西安 710064)

模板匹配算法的改進(jìn)及在自動(dòng)發(fā)牌機(jī)中的應(yīng)用

侯智新，李媛媛

(長(zhǎng)安大學(xué) 陜西 西安 710064)

自動(dòng)發(fā)牌機(jī)是基于數(shù)字圖像處理的智能化體育比賽輔助用具，使用傳統(tǒng)模板匹配算法的自動(dòng)發(fā)牌機(jī)，由于算法中存在大量無(wú)效運(yùn)算，使得撲克識(shí)別耗時(shí)較長(zhǎng)。本文提出采用區(qū)域隔行掃描序貫算法改進(jìn)模板匹配算法，極大地降低了識(shí)別時(shí)間，提高了識(shí)別準(zhǔn)確率。

圖象識(shí)別；模板匹配；自動(dòng)發(fā)牌機(jī)；ARM平臺(tái)

現(xiàn)代橋牌已遠(yuǎn)遠(yuǎn)超出了游戲的范疇，而成為有嚴(yán)格規(guī)則的世界性體育比賽項(xiàng)目。以全國(guó)高校教職工橋牌比賽為例，僅決賽就采用12桌米切爾制，打11輪22副牌，這樣每天需要用的橋牌數(shù)量就是相當(dāng)大的一個(gè)數(shù)目。因此，不論在平時(shí)娛樂(lè)還是在大型比賽時(shí)，發(fā)牌就成了巨大的工作。

市面上的自動(dòng)發(fā)牌機(jī)主要有兩種[1]，一種是沒(méi)有圖像處理設(shè)備，僅通過(guò)發(fā)牌機(jī)把牌依次發(fā)放到相應(yīng)方位而已，不能實(shí)現(xiàn)指定排序的發(fā)放；另一種是基于圖像處理的撲克識(shí)別，可以發(fā)指定牌序，但存在著大量計(jì)算，在實(shí)時(shí)性要求下需要連接電腦來(lái)做識(shí)別工作，使得自動(dòng)發(fā)牌機(jī)造價(jià)昂貴且攜帶不便。對(duì)此，提出了一種基于模板匹配的區(qū)域隔行掃描序貫算法，設(shè)計(jì)出一種滿足實(shí)時(shí)性要求的本地識(shí)別且可以用于所有類型撲克的自動(dòng)發(fā)牌機(jī)。

1 基于模板匹配算法的撲克牌識(shí)別

1.1 模板匹配算法

簡(jiǎn)單而言，模板就是一幅已知的小圖像。模板匹配[2]就是在一幅大圖像中搜尋目標(biāo)，已知該圖中有要找的目標(biāo)，且該目標(biāo)同模板有相同的尺寸、方向和圖像，通過(guò)一定的算法可以在圖中找到目標(biāo)，確定其坐標(biāo)位置。模板匹配常用的一種測(cè)度為模板與源圖像對(duì)應(yīng)區(qū)域的誤差平方和。設(shè)f(x,y)為M*N的源圖像，t(j,k)為J*K的模板圖像，則歸一化互相關(guān)作為誤差平方和測(cè)度[3]，其定義為：

當(dāng)x和y變化時(shí)，t(j,k)在源圖像區(qū)域中移動(dòng)并得出R(x,y)所有值。R(x,y)的最大值便指出了與t(j,k)匹配的最佳位置。

1.2 基于模板匹配算法的撲克牌花色和點(diǎn)數(shù)識(shí)別

傳統(tǒng)的模板匹配算法[4]應(yīng)用于自動(dòng)發(fā)牌機(jī)時(shí)，是用已經(jīng)保存的花色模板和點(diǎn)數(shù)模板分別對(duì)一張撲克圖片進(jìn)行模板匹配，遍歷撲克圖的每一點(diǎn)，而且需要遍歷每一個(gè)模板，得到最大的R值，分別找到撲克圖的最佳匹配花色和最佳匹配點(diǎn)數(shù)。其中R為0到1的數(shù)字，當(dāng)R為1時(shí)表示模板完全匹配。匹配時(shí)，源圖像和模板都是預(yù)處理后二值化的圖像。

以花色匹配為例， 模板為：t1、t2、t3、t4、t5分別表示黑桃、紅桃、梅花、方塊和JOKER的花色模板?；ㄉヅ鋾r(shí)，首先找出t1模板在撲克圖像上的最佳匹配值R1，然后依次找出所有花色模板的最大匹配值 R2、R3、R4和 R5，比較得出最大的，其下標(biāo)i就表示這張撲克的最佳匹配花色。點(diǎn)數(shù)匹配原理與花色匹配原理一致。

1.3 算法存在的問(wèn)題

用歸一化互相關(guān)求匹配的計(jì)算工作量非常大，因?yàn)槟０逡?M-J+1)*(N-K+1)個(gè)參考位置上做相關(guān)運(yùn)算，且花色匹配時(shí)運(yùn)算量還要增加為5倍，點(diǎn)數(shù)匹配時(shí)更要增加為13倍，實(shí)際測(cè)試時(shí)，在嵌入式 環(huán)境下的 上運(yùn)行 識(shí)別的源圖像分辨率為320×240，模板圖像分比率為40*60時(shí)，在識(shí)別前和識(shí)別后分別打印出時(shí)間可以得到：識(shí)別撲克點(diǎn)數(shù)需要耗時(shí)43秒，這完全不在可以接受的范圍內(nèi)。而同樣的算法的程序在酷睿i3的筆記本上僅耗時(shí)1 s不到，不難看出，嵌入式系統(tǒng)由于其運(yùn)算能力的限制，需要精簡(jiǎn)優(yōu)化的識(shí)別算法才能在撲克識(shí)別應(yīng)用上滿足實(shí)時(shí)性要求。

2 模板匹配算法的改進(jìn)

2.1 特定區(qū)域匹配

在歸一化互相關(guān)求匹配的計(jì)算中，除了最佳匹配點(diǎn)以外，其余做的都是無(wú)效運(yùn)算。在本系統(tǒng)的應(yīng)用中，一幀圖像分辨率為320×240，視頻流中抓取的一幅待識(shí)別的灰度圖像如圖1所示。

圖1 原始采樣圖像Fig.1 Chart of original picture

而需要進(jìn)行匹配計(jì)算的僅僅位于圖像的左上角部分，系統(tǒng)在拍照的時(shí)候?yàn)槎ň嚯x定角度，且撲克牌為中心對(duì)稱圖像，所以在識(shí)別點(diǎn)數(shù)的時(shí)候僅對(duì)源圖像的左上角部分進(jìn)行歸一化互相關(guān)求匹配計(jì)算，需要計(jì)算的圖像范圍約為原圖像的15%左右，這樣計(jì)算量就縮減為原算法的15%左右。

2.2 隔行掃描匹配

在最佳模板匹配指定撲克時(shí)候，把源圖像每一個(gè)像素點(diǎn)處的R值映射到像素空間，R的理論范圍為0到1，把R值映射到灰度空間從0x00(黑色)到0xff(白色)。實(shí)際測(cè)試發(fā)現(xiàn)，R值實(shí)際在0.6到1之間，為了增加對(duì)比度，把R(x,y)值映射到灰度空間的方法為：

其中，Gray為映射后的灰度值，255為十六進(jìn)制0xff的十進(jìn)制表示。這樣組成一幅匹配值R圖，R值越高，對(duì)應(yīng)像素點(diǎn)的灰度越大，在圖片上顯示就越白。最佳匹配點(diǎn)出的R值最大，得到的匹配值R圖中對(duì)應(yīng)的最佳匹配點(diǎn)處顏色最白。對(duì)圖1中圖像繪制的匹配值R圖如圖2所示。

圖2 對(duì)應(yīng)的匹配值R圖Fig.2 Chart of corresponding marching value R

圖像中最右邊和最下邊的灰色為初始圖像，設(shè)置初始灰度為0x7f，模板匹配算法中，橫向需要減去模板寬度，縱向需要減去模板高度來(lái)匹配，故右下邊緣不進(jìn)行匹配運(yùn)算，得到的匹配值R圖有邊緣。通過(guò)匹配值R圖可以知道：只有在最佳匹配點(diǎn)處R取得最大值，同時(shí)也是附近區(qū)域的極大值。打印出最佳匹配點(diǎn)附近的R值，觀察最大值處R的逼近過(guò)程，如圖3所示。

圖3 最佳匹配逼近過(guò)程記錄圖Fig.3 Chart of best matching approximation process record

可以看到：第13×19個(gè)像素點(diǎn)可以取到最大的R值，而這一像素點(diǎn)在第13列及第19行也為極大值。為了減少運(yùn)算，可以進(jìn)行隔行匹配，僅計(jì)算第 11、13、15列和第 17、19、21行相交的像素。這樣取得的最大值仍在實(shí)際最大值附近，不影響匹配結(jié)果的前提下減少了運(yùn)算量。一張m*n分辨率的圖像，匹配一個(gè)像素點(diǎn)的時(shí)間設(shè)為t，則匹配整個(gè)圖像的時(shí)間他T1=m*n*t。新算法下，行列匹配時(shí)分別隔a行，b列，則新算法下匹配時(shí)間T2為：

應(yīng)用于點(diǎn)數(shù)匹配時(shí)，a=1，b=1；應(yīng)用于花色匹配時(shí)，a=2，b=1。

2.3 序貫抽樣匹配

在多模板匹配時(shí)，記錄每一個(gè)模板的最佳匹配點(diǎn)出的R值，將其打印出來(lái)，發(fā)現(xiàn)最佳匹配模板的最佳匹配點(diǎn)處的R值基本在0.915以上，而其他模板的最佳匹配點(diǎn)值在0.85以下。這樣，可以繼續(xù)優(yōu)化算法為：當(dāng)檢測(cè)到某個(gè)模板的某個(gè)點(diǎn)出的R值為0.915以上時(shí)，就認(rèn)為已經(jīng)找到了最佳匹配的模板，停止本張圖像的其他識(shí)別工作，以減少識(shí)別時(shí)間。本系統(tǒng)花色匹配模板的順序?yàn)榉綁K、梅花、紅桃、黑桃、王，點(diǎn)數(shù)匹配模板的順序?yàn)锳、2…Q、K，這樣，在識(shí)別方塊A的時(shí)候，首先匹配花色模板，先匹配方塊模板，R值為0.915以上，認(rèn)為已經(jīng)匹配成功，然后匹配點(diǎn)數(shù)，先匹配A點(diǎn)模板，R值為 以上，這樣，花色和點(diǎn)數(shù)都僅匹配一次即可識(shí)別，計(jì)算量減少為原來(lái)的1/4*13，即1.2%，而識(shí)別黑桃K的計(jì)算量沒(méi)有變。

3 基于改進(jìn)算法的自動(dòng)發(fā)牌系統(tǒng)設(shè)計(jì)

3.1 硬件系統(tǒng)結(jié)構(gòu)

自動(dòng)發(fā)牌機(jī)工作時(shí)，一沓牌花色朝下放入母牌盒，光電檢測(cè)機(jī)構(gòu)自動(dòng)對(duì)最下面的一張牌進(jìn)行拍照并傳遞數(shù)據(jù)給處理器以做判決，判決輸出到執(zhí)行傳動(dòng)裝置，取出一張牌，經(jīng)傳動(dòng)裝置傳輸?shù)綄?duì)應(yīng)的牌套上方落下，牌套上方有四組光電傳感器，當(dāng)撲克落入牌套中，傳感器會(huì)觸發(fā)并傳輸信號(hào)給控制器，當(dāng)撲克落入正確位置后會(huì)開始下一張撲克的發(fā)送過(guò)程。這樣經(jīng)過(guò)一系列的操作，一張牌就正確的送入了牌套的指定位置中。自動(dòng)發(fā)牌機(jī)的系統(tǒng)框圖如圖4所示。

圖4 發(fā)牌機(jī)系統(tǒng)框圖Fig.4 Schematic diagram of automatic cards dealer

本自動(dòng)發(fā)牌機(jī)系統(tǒng)設(shè)計(jì)以三星公司的S3C6410為開發(fā)平臺(tái)，輔以必要的外圍電路，運(yùn)行嵌入式LINUX系統(tǒng)，并連接攝像頭進(jìn)行拍照分析，實(shí)現(xiàn)對(duì)撲克的自動(dòng)識(shí)別。

3.2 系統(tǒng)工作流程

本次設(shè)計(jì)的自動(dòng)發(fā)牌機(jī)方案為在本地可以識(shí)別普通撲克并根據(jù)需要發(fā)送撲克的方案。其軟件流程圖如圖5所示。

圖5 系統(tǒng)軟件流程圖Fig.5 Flow chart of the system software design

系統(tǒng)開始時(shí)，對(duì)一切設(shè)備和參數(shù)進(jìn)行初始化，并載入事先保存好的花色模板，載入已經(jīng)保存的訓(xùn)練牌庫(kù)。然后利用V4L2，在linux下開啟攝像頭，完成視頻預(yù)覽。由于系統(tǒng)用的是USB攝像頭，輸出的視頻格式為YUV422，故從視頻流中讀取一幀圖片后首先轉(zhuǎn)化為RGB用于顯示。其中讀視頻幀用了內(nèi)存映射技術(shù)，使應(yīng)用程序可以直接訪問(wèn)設(shè)備內(nèi)存，減少了從內(nèi)核態(tài)到用戶態(tài)的數(shù)據(jù)拷貝，提高了運(yùn)行速度。把每一幀圖像都重繪在屏幕上，這樣就完成了視頻的預(yù)覽。

當(dāng)初始化完畢開始發(fā)牌時(shí)，或者上一張牌成功發(fā)送后，對(duì)接下來(lái)的一幀圖像進(jìn)行圖像預(yù)處理。包括圖像的灰度化，二值化。

接著，對(duì)二值圖像進(jìn)行分割，由于本系統(tǒng)的母牌儲(chǔ)存盒與攝像頭間的距離為固定距離，且本系統(tǒng)運(yùn)行在嵌入式linux平臺(tái)上，基于識(shí)別速度的考慮，設(shè)置攝像頭和撲克牌關(guān)系為定距離定角度的拍攝，這樣，就免去了撲克圖像邊緣增效，霍夫變換和圖像旋轉(zhuǎn)等操作，大大簡(jiǎn)化了預(yù)處理流程，提高了識(shí)別速度。

然后就是利用模板匹配的方法對(duì)當(dāng)前幀圖像進(jìn)行識(shí)別，其識(shí)別具體算法將在后文介紹。識(shí)別出撲克的點(diǎn)數(shù)和花色后，根據(jù)預(yù)先設(shè)計(jì)的牌庫(kù)，把指定的牌應(yīng)發(fā)送的位置信息傳遞給傳動(dòng)裝置，使其正確發(fā)送。

當(dāng)指定位置牌位的傳感器接收到牌已經(jīng)正確發(fā)送的信號(hào)后，傳遞給系統(tǒng)，此時(shí)，開始抓取下一幀圖像，進(jìn)行下一張撲克的識(shí)別和發(fā)送。若2秒內(nèi)系統(tǒng)沒(méi)有收到傳感器發(fā)送來(lái)的撲克正確入位的信號(hào)時(shí)，在LCD顯示屏上給出警告信號(hào)，說(shuō)明發(fā)送失敗。當(dāng)所有的牌都已經(jīng)發(fā)送完畢時(shí)，在LCD顯示屏上給出提示信息，表示已經(jīng)成功完成發(fā)牌。

3.3 設(shè)計(jì)實(shí)現(xiàn)

本次設(shè)計(jì)的自動(dòng)發(fā)牌機(jī)可以使用市面上任意品種的撲克牌，其原理就是獲取一套特定牌的模板即可。不同廠家生產(chǎn)的撲克，雖然花色及點(diǎn)數(shù)的樣子不完全一樣，但是同一副撲克所有的同類牌都一樣，如圖6所示。

圖6 模板獲取流程圖Fig.6 Flow chart of the template acquisition

模板的獲取方法為：把一副牌按照黑、紅、梅、方，且按照點(diǎn)數(shù)從A、2…到K的順序放好，放入母牌盒，選擇獲取模板按鈕。此時(shí)，發(fā)牌機(jī)的工作流程如圖7所示為。

讀取圖像后，進(jìn)行灰度化，濾波去噪、邊緣增強(qiáng)，二值化，圖像分割等步驟，獲取到僅包含花色和僅包含點(diǎn)數(shù)的兩張小圖片，保存為jpg文件到SD卡中，并記錄對(duì)應(yīng)模板的文件名。然后把這張牌移動(dòng)到牌套里，開始讀取下一張的工作。這樣等到全部讀取完畢，就可以得到一套新的撲克模板。

4 測(cè)試分析

在6410上運(yùn)行本程序以檢測(cè)基于改進(jìn)模板匹配算法的自動(dòng)發(fā)牌系統(tǒng)的撲克識(shí)別的魯棒性和實(shí)時(shí)性是否滿足要求，測(cè)試結(jié)果如表1所示。

表1 測(cè)試結(jié)果Tab.1 Test result of poker recognition

通過(guò)兩組測(cè)試可以發(fā)現(xiàn)基于改進(jìn)模板匹配算法的自動(dòng)發(fā)牌系統(tǒng)的撲克識(shí)別，其識(shí)別準(zhǔn)確率高，識(shí)別速度快，可以滿足實(shí)際使用要求。

5 結(jié)論

對(duì)傳統(tǒng)模板匹配算法的三點(diǎn)改進(jìn)：特定區(qū)域匹配，隔行掃描匹配及序貫抽樣匹配，經(jīng)測(cè)試驗(yàn)證，有效的提高了在嵌入式平臺(tái)上進(jìn)行撲克識(shí)別的速度，而不降低其識(shí)別魯棒性。設(shè)計(jì)的自動(dòng)發(fā)牌系統(tǒng)能滿足撲克自動(dòng)識(shí)別、指定發(fā)牌的要求，系統(tǒng)可靠、有效。

[1]寇永軍.圖像識(shí)別在發(fā)牌機(jī)上的應(yīng)用研究[D].長(zhǎng)沙 湖南大學(xué),2006.

[2]田娟,鄭郁正.模板匹配技術(shù)在圖像識(shí)別中的應(yīng)用 [J].傳感器與微系統(tǒng),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]陳國(guó)彬,張廣泉.一種基于特征加權(quán)模板匹配方法在紙幣字符識(shí)別中的應(yīng)用 [J].微電子學(xué)與計(jì)算機(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]蔣美君,蔣廷彪.高魯棒的實(shí)時(shí)撲克字符識(shí)別方法研究[J].桂林電子科技大學(xué)學(xué)報(bào),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視頻采集終端的設(shè)計(jì)與實(shí)現(xiàn)[J].貴州大學(xué)學(xué)報(bào):自然科學(xué)版,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視頻采集方案的設(shè)計(jì)與實(shí)現(xiàn)[J].電視技術(shù),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 稿件編號(hào)：201401056

陜西省科技攻關(guān)（2013K06-27，2012K09-07）

侯智新（1990—），男，陜西潼關(guān)人，碩士研究生。研究方向：信號(hào)與信息處理、計(jì)算機(jī)測(cè)控。