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