模板匹配算法的改進及在自動發牌機中的應用

侯智新，李媛媛

(長安大學 陜西 西安 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—），男，陜西潼關人，碩士研究生。研究方向：信號與信息處理、計算機測控。