??? 摘 要： 視覺是象棋機器人軟件的重要組成部分，其核心工作是棋盤圖像二值化" title="二值化">二值化、棋子檢測和棋子識別。并對棋盤全局二值化存在的問題，提出了基于相鄰像素灰度差閾值的棋盤圖像二值化方法" title="二值化方法">二值化方法；針對棋子文字方向任意的現象，提出了基于年輪統計的棋子文字識別方法。實踐證明，該方法處理速度快、識別效果理想。
??? 關鍵詞： 棋盤識別? 圖像處理? 灰度差閾值? 年輪統計
?
??? 中國象棋變化多端，趣味無窮，是流傳了一千多年的優秀游戲，是中華文化的精粹之一。隨著機器人技術的發展，機器人的功能越來越豐富，娛樂機器人的研究已經成為一個重要的方向。象棋機器人是娛樂機器人的一種，在CCD攝像機的監視下，使人機下棋過程非常類似于人與人之間的對弈，更具有人性化和親切感。本文介紹的系統是象棋機器人的視覺部分，能識別出當前棋盤的狀態，提供給機器人下棋軟件進行進一步推理。
??? 象棋棋盤識別中的關鍵問題是對捕捉的棋盤圖像的二值化、棋子檢測和棋子文字的識別?？紤]光源變化和不良環境的影響，將圖像做全局單閾值二值化無法有效地將棋盤背景和網格線" title="網格線">網格線及棋子分開；棋子檢測是相對耗時的工作，棋子定位的準確性將直接影響后續識別的正確性；棋子文字識別的主要問題是文字方向的任意性?？紤]到下棋軟件搜索和推理比較費時(尤其是在較高級別時)，為使系統具有較短的響應時間，該視覺部分應盡可能快，故很多計算量大的處理方法在此不太適用。本文針對這些問題，以處理有效和計算簡單為目標，提出了基于像素差閾值的棋盤圖像二值化" title="圖像二值化">圖像二值化方法、棋子的兩趟檢測法和基于年輪統計的棋子文字識別方法。
1 象棋機器人視覺系統整體設計
1.1棋盤設計與表示
??? 棋盤的設計如圖1（a）所示，棋盤由對弈棋盤和輔助棋位組成。相機位于棋盤正上方，且保持固定狀態，靜止拍攝。輔助棋位是位于棋盤的兩側用于放置吃掉的棋子。棋子正反兩面帶有凹槽外框及標識點，根據紅、綠方棋子，槽內底色也分別為紅、綠兩種顏色；正反兩面的字符也分為紅、綠兩色，黑棋上的字符為將、象、士、車、馬、炮、卒，紅棋上的字符為帥、相、仕、車、馬、炮、兵。棋盤和棋子的底色為灰白，網格線為黑色。
?
??? 為表示棋子的位置，定義一個棋盤坐標系如圖1(b)所示。用兩維數組A(i，j)表示棋盤上各棋位的狀態，其中，(i，j)為棋位的豎軸、橫軸坐標。棋位的狀態用一組代碼表示，用“0”表示無棋子，一組大寫字母表示紅方棋子，一組小寫字母表示綠方棋子，具體為“R”表示紅車；“H”表示紅馬；“E”表示紅相；“A”表示紅仕；“K”表示紅帥；“C”表示紅炮；“P”表示紅兵?！皉”表示綠車；“h”表示綠馬；“e”表示綠象；“a”表示綠士；“k”表示綠將；“c”表示綠炮；“p”表示綠卒。
1.2 象棋棋盤識別程序出口參數
??? 程序被調用一次，將捕捉當前棋盤圖像并對其進行預處理、二值化、棋盤狀態檢測、棋子文字識別等工作。程序處理結果為棋盤狀態數組A(i，j)（i=0…9， j=0…12）和異常數組B(i)（i=0,1,…,6）(A(i，j)的定義如2.1中所述)。約定B(0)、B(1)、B(2)、B(3)、B(4)、B(5)、B(6)的值為0或1，分別表示圖像模糊不清、有手臂遮擋棋盤、有異物、僅缺失一個棋子、棋子缺失兩個或兩個以上、棋子多余、棋子過于偏離位置這七種異常情況的無或有，供后續的控制程序和博弈程序判斷使用。
1.3 象棋棋盤識別程序處理流程
??? 程序的處理過程為先捕捉棋盤灰度圖像并進行二值化，在此基礎上進行棋盤檢測并對分割出的棋子進行識別，同時應考慮光線、遮蓋、異物、棋子偏離等異常情況。具體處理流程如圖2所示。其中，對棋盤圖像的二值化、棋子檢測和棋子文字的識別是關鍵，下面分別介紹其中所存在的主要問題及所采取的解決方法。
?
2 基于像素差閾值的棋盤圖像二值化
??? 棋盤圖像二值化的目的是將棋盤背景與棋子及網格線分離，以便進行棋子等的檢測和識別。目前圖像二值化方法很多，可劃分為:全局閾值法" title="閾值法">閾值法、局部閾值法、動態閾值法[1-2]。全局閾值法實現簡單、速度快，對于具有明顯雙峰直方圖的圖像效果明顯,但對于光照不均勻的圖像效果不佳,抗噪能力差。局部閾值法能處理較為復雜的情況,但往往忽略了圖像的邊緣特征,容易出現偽影現象，且窗口較大時,算法的速度將受到很大影響。動態閾值法充分考慮了像素的鄰域特征,能夠根據圖像的不同背景情況自適應地改變閾值,可較精確地提取出二值圖像,但它過渡地夸大了像元的鄰域灰度的變化,會把不均勻灰度分布的背景分割到目標中去,帶來許多不應出現的假目標。
??? 在象棋機器人系統中裝有照明燈,為圖像捕捉提供光源。即使這樣，由于光照不均勻有時所捕捉的圖像仍存在一定的陰影、反光現象，致使圖像灰度層次較多。灰度圖像如圖3(a)所示。若采用全局閾值法的二值化圖像，結果出現某些背景變黑而一些棋子模糊和網格線斷線的現象，如圖3(b)所示。這直接影響了后續的棋子和異物檢測。
?
??? 分析灰度棋盤圖像特征，發現雖然背景灰度不均勻，但圖像清晰，網格線和棋子與鄰域背景灰度反差較大，而背景灰度在鄰域內變化緩慢。為此，綜合全局閾值法的速度優勢、局部閾值法和動態閾值法的鄰域特征，提出一種基于鄰像素差閾值的二值化方法。
2.1 基于鄰像素差閾值的棋盤圖像二值化算法思想
??? 基于鄰像素差閾值的棋盤圖像二值化算法是將常規灰度閾值的像素灰度判斷改為對鄰像素差閾值進行相鄰像素差的判斷來分割圖像。
??? 鄰像素差是指水平或垂直方向上的相鄰兩像素灰度的差。鄰像素差閾值是指對整幅圖像進行鄰像素差的統計，利用灰度閾值自動求取方法求取鄰像素差閾值。針對象棋棋盤圖像，進行逐行或逐列掃描圖像，求出水平或垂直相鄰像素灰度差直方圖。實驗發現，該灰度差直方圖呈現明顯的雙峰特征，故選擇峰谷點作為閾值。
??? 基于鄰像素差閾值的棋盤圖像二值化算法就是用鄰像素差閾值二值化圖像，即逐行或逐列掃描棋盤圖像，若判相鄰像素差小于閾值，則當前點的二值化值與前一個像素的二值化值相同，否則不同。
??? 設灰度棋盤圖像為A，二值棋盤圖像為BW，鄰像素差閾值為T，則水平方向的鄰像素差閾值的二值化方法為：
??? 
??? 垂直方向的鄰像素差閾值的二值化的表達為：
??? 
2.2 基于相鄰像素灰度差的棋盤二值化算法描述
??? (1) 準備一個存放二值化圖像的矩陣BW，并將第一個元素BW[1,1]的值賦為1（已知是白色背景），它是處理的起點。
??? (2) For i=1 to m ? //逐行掃描圖像，m為棋盤圖像行數
??????? {??
????????? For j=1 to n????? //逐列掃描像素行，n為棋盤
??????????????????????????????????????????? ?圖像列數
???????????? If P(i,j)-P(i,j-1)
??????????????????????????? //它是下一行二值化的起點
??? }
??? 以上為基于水平像素差閾值的二值化算法。若基于垂直像素差閾值，則二值化算法中將行列掃描順序調整即可。
3 棋子及異常檢測
??? 在二值化圖像上進行棋子和異物的檢測，以便進行下一步的識別或異常報警。檢測采用兩趟檢測法。
??? 第一趟：正常棋位棋子檢測
??? 沿網格線逐線水平掃描，在棋位處進行十字網格線的檢測，若有十字網格線則該棋位為空，否則通過一個模板圓進行匹配確認是否為棋子。將匹配成功的棋子分割下來傳給識別函數，并以1值（白色）填充棋位。
??? 模板圓匹配方法：模板圓圓心在以十字點為中心以
為邊長的正方形內進行試探，若圓周匹配率達95%則認為匹配成功。
??? 若采用逐行逐列順序匹配，一個1028×1024的盤棋的檢測時間約為2秒。在正常情況下，由于棋盤棋位和棋子吸鐵石的相互作用，棋子的位置偏離很少。為提高匹配速度，以十字交叉點為起點以螺旋線為移動路徑進行匹配，實測檢測速度提高約20倍。
??? 第二趟：異物和棋子超偏等異常檢測
??? 以網格為單位進行棋盤掃描，進行網格內的異物和棋子超偏等異常檢測。具體步驟如下：
??? (1)對當前網格內黑像素數進行統計，若統計值為0，則當前網格區中無物體，判下一個網格區；否則進入第2步。
??? (2)求當前網格區的水平投影和垂直投影，若水平或垂直投影寬度大于棋子直徑，則為異物退出，否則進入第3步。
??? (3)投影拼接：當前網格區中物體小于棋子則判物體水平鄰接關系，寬度大于棋子為異物退出；否則判物體垂直鄰接關系。若高度大于棋子，為異物退出；否則進行棋子檢測，是棋子置B(5)，不是棋子則置B(1)。
??? (4)當前網格區中有物體且無物體鄰接關系同時投影寬度接近棋子大小，則進行棋子檢測，若是棋子，則為棋子超偏置B(5)，否則棋子置B(1)。
4 基于年輪統計的棋子文字識別方法
??? 如圖4(a)所示的以棋子的圓形凹槽外框為特征，從上面二值化圖像中通過模板圓匹配法很容易檢測并分割出棋子，然后對棋子文字進行識別。由于棋子放置方向的隨意性，識別的關鍵問題是文字的方向。
??? 基于統計決策論的統計特征可以丟失方向信息，是適合識別棋子的方法。統計決策論其要點是提取待識別模式的一組統計特征, 然后按照一定準則所確定的決策函數進行分類判決。漢字的統計模式識別是將字符點陣看作一個整體, 從該整體上經過大量統計得到所用特征, 用盡可能少的特征模式來描述盡可能多的信息。所采用的方法有: 特征統計方法、整體變換分析法、幾何矩特征、筆劃密度特征、字符投影特征、外圍特征、微結構特征和特征點特征等。在這里，因文字方向任意，這些方法都不適用。由于棋子字符共有將、象、士、車、馬、炮、卒、帥、相、仕、車、馬、炮、兵14個，且系統要求視覺處理速度要快，所以不能采用計算量大的方法，故需要尋找針對這14個字的簡單、快速、有效的識別方法。受參考文獻[3]中過線數特征的啟發，本文提出一種基于統計特征的、與方向無關的、簡單快速的象棋棋子識別方法——年輪統計法。
4.1 有關定義
??? 所謂年輪，是指以字符中心為圓心，以小于棋子半徑的若干整數為半徑所做的一組同心圓，因其形狀而命名。如圖4(b)所示。
?
??? 過輪數定義為每個年輪穿越字符的次數，即每條年輪穿過黑像素區域的次數即為該年輪上的過輪數。
??? 年輪統計法是根據過輪數特征構造編碼器對文字進行識別。該方法結合了一定的棋子文字結構且與方向無關。
4.2 過輪數的計算方法
??? 過輪數的計算方法是：若圓心坐標為（x,y），半徑為r,則從（x,y+r）開始逆時針沿年輪線走一圈，像素值從白到黑變化一次則累計一次數。
4.3 年輪像素位置的確定
??? 計算過輪數的關鍵問題是確定年輪線上的像素位置。為減少統計時間，根據圓的八路對稱性，只需計算（x,y+r）-（x+r/sqr(2.0),y+r/sqr(2.0)）這1/8圓即可。在此可應用著名的Bresenham畫圓算法[4]來確定年輪上的像素。
??? Bresenham畫圓算法的基本思想是，在算法的每一步都選擇距離圓周最近的點。設Pi(xi, yi)是已經選取的一個像素點，根據該段圓的特點，可以判定下一個像素將從Hi(xi+1, yi)和Di(xi+1, yi+1)兩點中選取。
??? 判據d的初始值為：d0=3-2R
??? 如果di<0,應選擇Hi,則下一點(xi+1,yi)的判別式是: di+1=di+4xi+6
??? 若di>0,應選擇Di,則下一點(xi+1,yi+1)的判別式是: di+1=di+4(xi-yi)+10
4.4 編碼器的構造
??? 若將棋子圓形外框半徑記為r,則對半徑從0～r 的每條年輪的過輪數進行計算，構成一個字符串。然后對字符串進行分析和篩減，以尋求一個能區分各文字的最短字符串，并將其作為編碼器進行棋子文字的識別。
??? 篩減方法：若某過輪數刪除后每個文字的過輪數串均不相同即不出現重碼，則將該過輪數刪除；否則，將該過輪數保留。
??? 針對本系統中的棋子，篩減的結果是(1/4)R、(1/2)R、(3/4)R三條年輪的過輪數，任意刪除一個即出現重碼，則將這三個過輪數進行組合作為棋子文字的識別碼。表1給出了象棋棋子文字的特征值及編碼器。
?
??? 本軟件是鄭州市科技館象棋機器人系統的視覺部分，其中所采用的基于鄰像素差閾值的棋盤圖像二值化方法計算量小、二值化效果好，能使用較寬的光線條件。但它要求邊緣灰度有突變的使用前提，否則會造成累計誤差。基于年輪統計的棋子文字識別方法具有方向無關性，能很好地適應棋子方向隨意的情況。為提高處理速度，可先做相鄰灰度圖像的差分，在二值差分圖上檢測變化位置，在當前二值圖上只對變化部分進行處理，可大大縮短處理時間。在具體應用中由于棋子文字的字體不同，以上方法的具體特征值可能不能直接拿來使用，但方法的思想是可借鑒的。
參考文獻
[1] ?OTSU N. A threshold selection method from gray-level histograms[J]. IEEE Transactions on Systems,1979,9(1):62-66.
[2]?趙雪松,陳淑珍.綜合全局二值化與邊緣檢測的圖像分割方法[J].計算機輔助設計與圖形學學報,2001,13(2): 118-121.
[3]?嚴國莉，黃山，李岱漳，等．印刷體數字快速識別算法在身份證編碼數字識別中的應用[J]. 計算機工程, 2003,(1):178-179.
[4] ?張曦煌，杜俊俐.計算機圖形學[M].北京:北京郵電大學出版社，2006.