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

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

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

2.2棋盤的圖像分割

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

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

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

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

0　引言

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

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

1　原理和方法

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

1.1幾何變換

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

1.2圖像分割

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

1.3形態學檢測

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

1.4圖像投影

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

2　實驗過程與結果分析

2.1棋盤預處理

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

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

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

2.2棋盤的圖像分割

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

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

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

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

用Gray表示棋盤圖像變換后的灰度值，R、G、B分別表示彩色圖像的三個分量，彩色圖像轉變為灰度圖像［8］的算法如式1所示：

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

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

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

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

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

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

（5）直方圖閾值分割結果

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

2.3棋子檢測與結果判定

（1）形態學運算

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

圖6　黑色棋子形態學運算處理結果

圖7　白色棋子形態學運算處理結果

（2）圖像投影

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

（3）棋子位置的識別和結果判定

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

2.4系統測試與分析

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

圖8　棋子識別結果圖

圖9　填補空格后效果

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

3　結語

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

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

經過大量測試發現，本文介紹的棋子識別算法可以準確、快速地識別棋子和棋盤，統計出黑白棋子的個數，可以在圍棋比賽中節省人工判讀的時間，提高工作效率。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

［15］趙玉環，王勤，張利偉，閆豐.數學形態學在紫外目標檢測中的應用［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

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

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

江蘇省自然科學基金（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.