梁澄宇，丁堯，袁杰，，朱廣浩

（1.南京大學電子科學與工程學院，南京210023；2.南京大學金陵學院，南京　210089）

2.2棋盤的圖像分割

采集的棋盤圖像經(jīng)過幾何變換后僅存在黑色棋子、白色棋子和黃色的棋盤。分割黑色棋子可以使用灰

圍棋比賽圖像識別算法研究

梁澄宇1，丁堯2，袁杰1，2，朱廣浩1

（1.南京大學電子科學與工程學院，南京210023；2.南京大學金陵學院，南京210089）

0　引言

在目前的大多數(shù)采用普通棋盤和實體棋子的圍棋比賽中，結(jié)果的統(tǒng)計一般采用傳統(tǒng)紙筆記錄法或計算機輔助記譜，前者比較傳統(tǒng)，依靠紙和筆記錄棋譜和統(tǒng)計結(jié)果，而后者雖然擺脫了紙和筆，但仍需要人工錄入，記譜員的工作量較大，耗費的時間較長，而且因為是人工操作，準確度的問題也難以避免，因此也沒有從根本上解決問題［1-2］。

在計算機視覺技術(shù)日益普及的今天，圖像處理和模式識別是一個熱門的研究領(lǐng)域，特別是機器視覺很多國內(nèi)外學者都在研究。圍棋在中國有著悠久的歷史和眾多的愛好群體，隨著科學技術(shù)的進步與發(fā)展，在棋譜的識別方面也有一些學者開展了研究，例如基于鏈編碼理論的棋譜識別系列算法，通過掃描的紙質(zhì)棋譜圖像，經(jīng)過二值化、傾斜檢測及校正、版面分析及棋譜區(qū)域的抓取、對棋譜區(qū)域進行識別等過程識別出棋譜，主要應用于紙質(zhì)棋譜的識別。本文介紹了一種基于投影的棋盤識別算法，可以應用于圍棋比賽結(jié)果的判讀，使用圖像處理技術(shù)對采集的棋盤圖像進行識別和處理，縮短判讀時間，減輕人工操作負擔，還可以保證結(jié)果的準確度，旨在為圍棋比賽結(jié)果的識別和判讀提出一個行之有效的方法。本文介紹的棋盤識別算法的處理流程包括幾何變換、棋子識別、圖像形態(tài)學處理、棋盤線的識別以及結(jié)果統(tǒng)計。

1　原理和方法

本文主要運用到的原理和方法有幾何變換、圖像分割、形態(tài)學檢測、圖像投影。

1.1幾何變換

圖像的幾何變換是在空間域上的運算，包括兩個基本操作步驟，即通過空間變換重新安排圖像平面上的像素，以及利用灰度級插值為空間變換后圖像中像素賦值［3-4］。

1.2圖像分割

圖像分割是指根據(jù)灰度、彩色、空間紋理、幾何形狀等特征把圖像劃分成若干個互不相交的區(qū)域，使得這些特征在同一區(qū)域內(nèi)，表現(xiàn)出一致性或相似性，而在不同的區(qū)域間表現(xiàn)出明顯不同的特性。圖像閾值化分割是一種最常用也是最簡單的圖像分割方法，它特別適用于目標和背景占據(jù)不同灰度級范圍的圖像，利用圖像中不同區(qū)域在灰度值或彩色值特性上的差異，通過設定不同的特征閾值，把圖像像素點分為若干類［5］。直方圖閾值分割是根據(jù)圖像中直方圖的特征來確定分割閾值進行圖像分割。

1.3形態(tài)學檢測

圖像數(shù)學形態(tài)學是一種新方法，在圖像處理和模式識別領(lǐng)域有著廣泛的應用。經(jīng)過形態(tài)學檢測，能夠得到比原始圖像更顯著突出物體特征信息的圖像［6］。首先提出所要描述的物體幾何結(jié)構(gòu)模式，然后根據(jù)該模式選擇相應的結(jié)構(gòu)元素，用選定的結(jié)構(gòu)元素對圖像進行擊中與否變換即可。

1.4圖像投影

圖像在某一方向上的投影可以定義為該圖像像素灰度值在該方向上累加之和。圖像投影是將其特征空間由二維壓縮為一維，將大量的圖像信息壓縮為少量的圖像特征信息，從而可以有效地進行圖像識別［7］。

2　實驗過程與結(jié)果分析

2.1棋盤預處理

對采集的圖像進行幾何變換，去除圖像中的無關(guān)區(qū)域，使得變換后的圖像僅包含棋盤。經(jīng)過空間變換和灰度級插值從采集的圖像中得到只包含棋盤的圖像。變換前后的結(jié)果如圖1所示，其中1.a為采集得到的棋盤圖像，1.b為經(jīng)過預處理后得到的圖像。度特征，將幾何變換后的圖像轉(zhuǎn)換成灰度圖像，在灰度直方圖中選取合適的閾值即可區(qū)分黑色棋子與白色棋子和棋盤。在分割白色棋子與黃色棋盤時，因為兩者在灰度值上有交叉，所以需要使用彩色特征進行分割，對比黑色、白色與黃色的RGB分量可知它們的藍色分量相差比較大，所以可以通過彩色圖像中的藍色分量的特征進行閾值分割。黑色棋子和白色棋子閾值分割的流程圖如圖2和圖3所示。

針對關(guān)鍵知識，事先做好預習微課程，以問題引導逐步呈現(xiàn)，整體構(gòu)建知識，讓學生課前觀看微課程，對整體知識進行整體了解，對于不懂的知識點先做好記錄，課堂上專心聽教師答疑，使學生消除疑惑并獲得知識內(nèi)化，給學生清晰的學習邏輯主線，有效地幫助學生主動構(gòu)建知識.

圖1　棋盤預處理前后效果對比

2.2棋盤的圖像分割

采集的棋盤圖像經(jīng)過幾何變換后僅存在黑色棋子、白色棋子和黃色的棋盤。分割黑色棋子可以使用灰

圖2　黑色棋子分割流程示意圖

圖3　白色棋子分割流程示意圖

（1）彩色圖像灰度化與藍色分量提取

用Gray表示棋盤圖像變換后的灰度值，R、G、B分別表示彩色圖像的三個分量，彩色圖像轉(zhuǎn)變?yōu)榛叶葓D像［8］的算法如式1所示：

依據(jù)式（1）將彩色圖像轉(zhuǎn)換化為灰度圖像，得到如圖4所示的效果，其中4.a為灰度化后效果，4.b為藍色分量提取后效果。

圖4　灰度化與藍色分量提取效果圖

（2）求灰度直方圖與鄰域平滑法濾波

統(tǒng)計每個像素在圖像中出現(xiàn)的次數(shù)，繪制出灰度直方圖曲線和藍色分量的直方圖曲線。通過直方圖曲線的極值點確定分割的閾值，因為繪制出的直方圖曲線上尖刺過多，直接求極值的話會得到很多結(jié)果，難以確定閾值，所以要對直方圖曲線進行鄰域平滑濾波［9］。

鄰域平均法的基本原理是用鄰域的平均值替換原始的灰度值，即用原始圖像中一個像素點的灰度值和它周圍鄰近的多個像素點的灰度值地平均值作為新圖中該像素的灰度值［10-12］。經(jīng)過鄰域平滑線性濾波后的曲線更加平滑，這樣可以更加準確的確定直方圖曲線的極值。本文使用鄰域平滑方法來平滑一維信號，用濾波掩模確定的鄰域內(nèi)每個點的平均值代替原始信號每個點的值，繪制出新的曲線。設一維信號h（n），濾波掩模的大小為M，M取奇數(shù)，平滑線性濾波器的輸出h'（n）如式2表示：

式（2）中，T是一維平滑濾波的閾值，由此可以去除由于鄰域平滑濾波產(chǎn)生的模糊效應。經(jīng)過大量測試，最終對灰度圖像和藍色分量分別選取平滑線性濾波的長度為13和15進行平滑濾波。

（5）直方圖閾值分割結(jié)果

圖5　棋盤圖像閾值分割后效果

2.3棋子檢測與結(jié)果判定

（1）形態(tài)學運算

本文中主要使用的是形態(tài)學運算中的腐蝕、膨脹和開運算操作。形態(tài)學運算的結(jié)果如圖6和圖7所示，有效地消除了圖像上細小的噪聲，并且平滑物體邊界［13-15］。

圖6　黑色棋子形態(tài)學運算處理結(jié)果

圖7　白色棋子形態(tài)學運算處理結(jié)果

（2）圖像投影

使用圖像投影的方法檢測棋盤中的棋盤線，首先將分割出的黑白棋子圖像相加，然后對相加后的圖像做一次腐蝕操作，分別在水平和垂直方向上對腐蝕后的圖像做投影并進行鄰域平滑濾波，觀察濾波后的結(jié)果看出，兩條投影曲線均有19個峰值，對應橫坐標的值就是棋盤中棋盤線的位置。求出兩條曲線每個峰值對應的橫坐標的位置，利用求出的棋盤線的位置構(gòu)造出圍棋棋盤。

（3）棋子位置的識別和結(jié)果判定

定義兩個二維數(shù)組分別存放黑白棋子位置，將黑色棋子的位置轉(zhuǎn)換成對應的數(shù)組時，將空白棋盤位置的值設為0，將黑色棋子位置的值設為-1，類似地，在獲取白色棋子位置的數(shù)組時，將白色棋子位置的值設為1。然后將兩數(shù)組相加，對每一行按照圍棋規(guī)則進行填補棋子，統(tǒng)計出矩陣中-1和1的個數(shù)即為黑色棋子與白色棋子的個數(shù)。

2.4系統(tǒng)測試與分析

棋子識別結(jié)果和填補結(jié)果如圖8所示，與圖1.b相比較，棋盤中所有棋子的位置都是一致的。

圖8　棋子識別結(jié)果圖

圖9　填補空格后效果

為了進一步確定此算法的可行性，又測試了大量的真實棋局圖像，根據(jù)多次測試的統(tǒng)計結(jié)果，本算法在采集的棋盤圖像完整清晰的情況下，識別率高達95%以上，表明了上述棋盤識別算法可以準確地檢測出棋子位置，統(tǒng)計出比賽結(jié)果。

3　結(jié)語

針對目前圍棋比賽結(jié)果的統(tǒng)計主要靠人工操作，耗費大量時間精力的現(xiàn)狀，本文介紹了一種棋盤圖像自動識別算法。通過對圍棋棋局進行圖像采集，使用幾何變換去掉除棋盤之外的其他物體。分割黑色棋子時，根據(jù)灰度特征的差異，使用了灰度直方圖閾值分割的方法；分割白色棋子時，根據(jù)彩色值的差異，通過藍色分量的直方圖進行閾值分割。

為了盡量去除圖像的噪聲，需要將分割出的黑白棋子圖像分別進行形態(tài)學處理，平滑物體邊界。接著將經(jīng)過形態(tài)學處理后的黑白棋子圖像相加并進行圖像投影，然后再做一次腐蝕操作來避免棋子圖像的粘連導致投影不準確。此時，經(jīng)過水平和垂直方向上的投影，二維圖像就轉(zhuǎn)化為一維的信號，通過投影曲線確定棋盤線的位置，然后根據(jù)棋盤線的位置來識別黑白棋子的位置。

經(jīng)過大量測試發(fā)現(xiàn)，本文介紹的棋子識別算法可以準確、快速地識別棋子和棋盤，統(tǒng)計出黑白棋子的個數(shù)，可以在圍棋比賽中節(jié)省人工判讀的時間，提高工作效率。

本文研究已經(jīng)獲得國家發(fā)明專利授權(quán)，“一種基于圖像處理技術(shù)的圍棋比賽結(jié)果分析方法”，專利號：201210150815.9，申請時間2012年5月16日，授權(quán)公告日：2016年4月27日。

［1］黃穗.基于鏈編碼的棋譜識別算法研究［D］.華東師范大學，2007.

［2］齊超男.一種中國象棋殘局棋譜自動生成算法［J］.黑龍江科技信息2012.31：202-202.

［3］馮珂，彭曙蓉，陳立福，楊京渝.基于MATLAB圖像配準方法的相關(guān)研究［J］.電子測試，2012.11：18-22.

［4］王偉.基于類推思想的車牌字符圖像清晰度提升［D］.西安電子科技大學，2012.

［5］鐘雪君.一種改進的Otsu雙閾值二值化圖像分割方法［J］.電子世界，2013.4：104.

［6］朱士虎.形態(tài)學高帽變換與低帽變換功能擴展及應用［J］.計算機工程與應用，2011.34：190-192，218.

［7］管業(yè)鵬，顧偉康.二維場景陰影區(qū)域的自動魯棒分割［J］.電子學報，2006.4：624-627.

［8］宋玉婷.基于三維彩色直方圖均衡化的彩色圖像增強算法研究［D］.山東財經(jīng)大學，2013.

［9］劉松濤，王維，殷福亮.基于動態(tài)廣義直方圖均衡的紅外圖像增強方法［J］.系統(tǒng)工程與電子技術(shù)，2010.7：1411-1414，1451.

［10］李兵.基于機器視覺的黑片缺陷檢測圖像預處理技術(shù)的研究［D］.沈陽理工大學，2010.

［11］李晶.基于機器視覺的指針式儀表自動判讀［D］.山東科技大學，2012.

［12］王立飛.基于NAM圖像處理系統(tǒng)的算法設計及實現(xiàn)［D］.華中科技大學，2010.

［13］張博聞，田小林，孫延奎.基于改進的數(shù)學形態(tài)學的OCT圖像快速邊緣提取算法［J］.計算機科學，2013.Z1：173-175.

［14］彭慧玲.基于數(shù)學形態(tài)學的邊緣檢測研究［D］.遼寧工程技術(shù)大學，2011.

［15］趙玉環(huán)，王勤，張利偉，閆豐.數(shù)學形態(tài)學在紫外目標檢測中的應用［J］.計算機工程與應用，2009.29：220-222.

Image Segmentation；Image Projection；Transformation Detection

Research on Go Chess Game Image Recognition Algorithm

LIANG Cheng-yu1，DING Yao2，YUAN Jie1，2，ZHU Guang-hao1
（1.School of Electronic Science and Engineering，Nanjing University，Nanjing 210023；2.Jingling College，Nanjing University，Nanjing 210089）

1007-1423（2016）24-0039-05DOI：10.3969/j.issn.1007-1423.2016.24.010

梁澄宇（1972-），男，在讀碩士研究生，研究方向為圖像處理

丁堯（1981-），男，碩士，教師，研究方向為圖像處理，E-mail：ammdistin@nju.edu.cn

袁杰（1975-），男，博士，教師，研究方向為圖像處理

2016-05-26

2016-08-20

研究圍棋比賽圖像識別算法的目的主要是為了能夠快速準確地判斷圍棋比賽結(jié)果。介紹一種高效精確的圍棋棋盤識別算法，能夠?qū)Σ杉钠灞P圖像進行圖像識別，自動統(tǒng)計黑白棋子數(shù)目。算法主要包括對圖像進行幾何變換、分割棋子以及棋盤線的識別。首先，使用幾何變換去除原始圖像中的無關(guān)物體，使圖像中僅包含棋盤，其次使用直方圖閾值方法分割棋子，然后使用圖像投影方法識別棋盤線，根據(jù)檢測到的棋盤線的位置，分別檢測黑白棋子的位置，統(tǒng)計出比賽結(jié)果。

圖像分割；圖像投影；變換檢測

江蘇省自然科學基金（No.BK20131280）

The reason to research Go chess game image recognition algorithm is to determine the result of a Go chess game quickly and accurately. Introduces a Go chess chessboard recognition algorithm，which can recognize the captured image of the chessboard and get the number of black and white chess pieces automatically.The recognition algorithm mainly includes geometric transformation of the image，segmentation of chess pieces and recognition of chessboard lines.First of all，uses geometric transformation to remove useless part of original image so that the image only contains the chessboard part，then uses histogram threshold method to segment image.Moreover，proposes a line detection algorithm based on projection to detect lines on the chessboard.In the end，detects the position of all chess pieces according to the detected chessboard lines.