基于链编码的棋谱识别算法研究
|
摘要
随着数字图像处理和模式识别技术的不断发展与成熟，图像的编码技术得到了飞速发展，并以其优良的特性在图像处理领域得到越来越多的运用。
本文指出了原顶点链编码算法在标定的时候存在的一些问题：在某些情况下会漏标定链编码。本文接着提出一种新的顶点链编码标定方法及其改进方法解决了这个问题。创新之处是通过使用边缘矩阵的结构改进了标定的方法，提高了算法的可靠性，同时又没有牺牲算法的效率。接下来，本文在新的链编码基础上作了一系列应用：嵌套结构分析、填充、区域统计。并且和同类算法相比，有较高的效率。
另外，本文又将新的顶点链编码技术应用到围棋棋谱识别领域。在市场上，有较大的需求把传统的物理介质棋谱转换为电子棋谱，但现今却没有成熟且广泛使用的方法。
本文首先在分析了棋谱识别问题，用顶点链编码作为主框架，辅以Freeman链编码、投影法等其他模式识别技术来对棋谱进行识别。本文提出的算法，经过实验，比市场上现存的产品在效率上和效果上有较大改进。
本文前半部分研究对象是通用算法，后半部分是在棋谱识别这个具体领域的应用。前半部分是后半部分的基础。
The technology of coding for image has a rapid growth due to the continual growth and maturation in the field of digital image processing and pattern recognition. And it is used more and more in the field of digital image processing because of its good features.
This paper indicates that there are some problems when old vertex chain code labeling algorithm labels the contours of regions. Sometimes old algorithm may miss some of contours. So this paper proposes a new labeling algorithm to solve this problem, and then gives a further solution to optimize this algorithm in efficiency. This new method uses a data structure named edge matrix to improve the old method, enhance the reliability of algorithm, and have good efficiency. And then, this paper also develops a series of applications based on vertex chain code: nested analysis, region filling and region counting. Compared to similar algorithms, these algorithms have better efficiency.
This paper also uses new vertex chain code technology to solve the problem of chess manual recognition. There are strong desires to recognize chess manual in paper, but there are no mature method to fulfil it.
After analyzing the problem of chess manual recognition, this paper uses new vertex chain code technology as main framework, and also uses freeman chain code technology, projection method and some other algorithms to solve this problem. By amount of experiments, the algorithm proposed by this paper is proved to have obvious enhancement both in quality and efficiency, compared with the similar product in the market.
The first half of this paper mainly focuses on common algorithms, and the second half of this paper mainly focuses on specific field (chess manual recognition). The first half is the basis of the second half.
本文指出了原顶点链编码算法在标定的时候存在的一些问题：在某些情况下会漏标定链编码。本文接着提出一种新的顶点链编码标定方法及其改进方法解决了这个问题。创新之处是通过使用边缘矩阵的结构改进了标定的方法，提高了算法的可靠性，同时又没有牺牲算法的效率。接下来，本文在新的链编码基础上作了一系列应用：嵌套结构分析、填充、区域统计。并且和同类算法相比，有较高的效率。
另外，本文又将新的顶点链编码技术应用到围棋棋谱识别领域。在市场上，有较大的需求把传统的物理介质棋谱转换为电子棋谱，但现今却没有成熟且广泛使用的方法。
本文首先在分析了棋谱识别问题，用顶点链编码作为主框架，辅以Freeman链编码、投影法等其他模式识别技术来对棋谱进行识别。本文提出的算法，经过实验，比市场上现存的产品在效率上和效果上有较大改进。
本文前半部分研究对象是通用算法，后半部分是在棋谱识别这个具体领域的应用。前半部分是后半部分的基础。
The technology of coding for image has a rapid growth due to the continual growth and maturation in the field of digital image processing and pattern recognition. And it is used more and more in the field of digital image processing because of its good features.
This paper indicates that there are some problems when old vertex chain code labeling algorithm labels the contours of regions. Sometimes old algorithm may miss some of contours. So this paper proposes a new labeling algorithm to solve this problem, and then gives a further solution to optimize this algorithm in efficiency. This new method uses a data structure named edge matrix to improve the old method, enhance the reliability of algorithm, and have good efficiency. And then, this paper also develops a series of applications based on vertex chain code: nested analysis, region filling and region counting. Compared to similar algorithms, these algorithms have better efficiency.
This paper also uses new vertex chain code technology to solve the problem of chess manual recognition. There are strong desires to recognize chess manual in paper, but there are no mature method to fulfil it.
After analyzing the problem of chess manual recognition, this paper uses new vertex chain code technology as main framework, and also uses freeman chain code technology, projection method and some other algorithms to solve this problem. By amount of experiments, the algorithm proposed by this paper is proved to have obvious enhancement both in quality and efficiency, compared with the similar product in the market.
The first half of this paper mainly focuses on common algorithms, and the second half of this paper mainly focuses on specific field (chess manual recognition). The first half is the basis of the second half.
引文
[1] Fu Chang, Chun-Jen Chen, Chi-Jen Lu, A linear-time component-labeling algorithm using contour tracing technique[J], Computer Vision and Image Understanding, 2004, 93(2): 206～220.
[2] Bribiesca E, A Chain Code for Representing 3D Curves, Pattern Recognition, 2000, 33(5): 755～765
[3] Yuan J、Suen C Y, An Optimal O(n) Algorithm for Identifying Line Segments form a Sequence of Chain Codes, Pattern Recognition, 1995, 28(5): 635～645
[4] 石秀、施泽生，FCC到VCC的转化[J]，小型微型计算机系统，2001，22(11)：1326～1330．
[5] 尚振宏、刘明业，运用Freeman准则的直线检测算法，计算机辅助设计与图形学学报，2005，17(1)：49～53．
[6] G. Y. TANG, A Discrete Version of Green's Theorem[J], IEEETransactions on Pattern Analysis and Machine Intelligence, 1982, 4(3): 242～250
[7] 陈优广、张薇、黄穗，图像区域边界抽取与链码树结构生成算法，华东师范大学学报(自然科学版)，2006年3月77～85．
[8] 姜一女，简谱识别方法的研究，浙江大学博士学位论文，2006
[9] 陈根方，OMR研究与原型系统开发，浙江大学博士学位论文，2003
[10] David Bainbridge、Tim Bel, An extensible Optical Music Recognition system, 1996 Australasian Computer Science Conference. (Melbourne, Australia): 308~317.
[11] K. Todd Reed, J. R. Parker, Automatic Computer Recognition of Printed Music, Laboratory for computer Vision, Department of Computer Science, University of Calgary, i015-4651/96 IEEE 1996
[12] 陈优广、顾国庆等，一种新的表格单元格矩形识别算法，计算机工程-2006年13期
[13] 黄锦德、郝红卫等，一种新的表格识别特征提取方法，计算机工程-2006年6期
[14] 汤英，面向对象的表格图像版面分析方法研究，华中科技大学学报：自然科学版-2005年12期
[15] 管继斌、明德烈，基于游程的倾斜表格图像的快速检测和校正，华中科技 大学学报：自然科学版-2005年8期
[16] Kenneth R．Castleman，数字图像处理，电子工业出版社，2006
[17] John E．Hopcroft等，自动机理论、语言和计算导论，机械工业出版社，2004
[18] Freeman H, Computer processing of line-drawing images, Computing Surveys, 1974, 6(1): 57-97
[19] Freeman H, On the encoding of arbitrary geometric configuration, IRE Trans, 1961, EC-10(2): 260-268
[20] Freeman H, Techniques for the digital computer analysis of chain-encoded arbitrary plane curves, Proc. Natl. Elect. Conf, 1961, 17 (Oct.): 421-432
[21] Freeman H, A technique for the classification and recognition of geometric patterns, Proc. 3rd. Intl. Congress on Cybernetics Namtur, 1961: 348-368
[22] Sidhu G S, Boute R T. Property encoding:applications in binary picture encoding and boundary following, IEEE Trans. Comp, 1972, C-21 (11): 1206-1216
[23] Merrill R. D, Representation of contours and regions for efficient computer search. Comm, ACM, 1973, 16(2): 69-82
[24] Bribiesca E, A new chain code. Pattern Recognition, 1999, 32: 235-251
[25] 顾国庆、许彦冰，数字图像区域标定的方法，上海理工大学学报，Vol．23，No．4，2001：295-299
[26] 许彦冰, 顾国庆, Method to generate vertex chain code and the calculation of geometric quantities, Journal of Shanghai University, Vol. 5 Suppl. (Sep. 2001) 144-146
[27] 顾国庆, 陈可, Region-Labeling-Automata for Images in Square, Triangular and Hexagonal Lattice, Advances in Computer and Information Technology, The Journal of Three Dimensional Images, 17(2003)161-165
[28] 顾国庆、陈可, Region-Labeling-Automata for Images in Square, Triangular and Hexagonal Lattice, Advances in Computer and Information Technology, The Proceedings of 2002 International Conference on Computer and Information Technology, (Aizu-Wakamatsu City, Japan, Sept. 11-14, 2002) 134-138
[29] 王涤琼、张薇、顾国庆，用顶点链编码计算图像区域的密集度和体态比， 华东师范大学学报(自然科学版)，2005，1：59～62。
[30] Charles Petzold，Windows程序设计，北京大学出版社
[31] 黄穗、张薇，基于边缘矩阵的链编码追踪算法，石河子大学学报 2005，Vol．23，No．5，P．644-646
[32] 杨素娣、顾国庆、黄穗，基于区域标定自动机的区域个数统计算法，计算机应用，2006年09期
[33] 顾国庆、许彦冰，数字图像区域标定的方法，上海理工大学学报，Vol．23，No．4，2001：295-299
[34] Geraets W. G. M.、van Daatselaar A. N、Vermeil J. G. C, An efficient filling algorithm for counting regions[J], Computer Methods and Programs in Biomedicine, 2004, 76, (1): 1-11
[35] Marius C. Codrea, Note: An algorithm for contour-based region filling, Computers & graphics. 29(2005) p441～450
[36] T. Pavlidis, Filling algorithms for raster graphics, Comput. Graphics Image Process, 1979, 10: 126～141.
[37] Gregory Y. Tang, Region Filling with the Use of the Discrete Green Theorem[J], Computer Vision, Graphics, and Image Processing, 1988, 42: 297～305.
[38] Mingwu Ren、Wangkou Yang、Jingyu Yang, A new and fast contour-filling algorithm, Pattern Recognition, 2005, 38: 2564～2577
[39] 任明武、杨静宇、孙涵，一种新的基于链码描述的轮廓填充方法，中国图象图形学报，2001，6(4)：348～352
[40] Mingwu Ren, Wangkou Yang, Jingyu Yang, A new and fast contour-filling algorithm, Pattern Recognition, 2005, 38: 2564～2577
[41] 李国强、张薇、顾国庆，顶点链编码和区域面积的计算方法，上海理工大学学报，Vol．25，No．3，2003
[42] 王涤琼、张薇、顾国庆，利用顶点链编码计算图像区域密集度和体态比，华东师范大学学报2005 Vol．1
[43] 张薇，链编码技术及其在图像处理中的应用，上海理工大学硕士学位论文，2003
[44] 翟燕生、徐莹，围棋入门，金盾出版社，2005
[45] 王志鹏、贺君平，围棋死活1000题，北京体育大学出版社，2004
[46] 黄希文，阶梯围棋教室：从入门到业余初段，辽宁科学技术出版社，2002
[47] 严德甫、晏天章，围棋圣经：玄玄棋经·珍珑棋局破解，团结出版社，2005
[48] http://bigo.baduk.org/chinese/ocr.html
[49] 沈晗，非均匀光照文本图像的分割，华东师范大学硕士论文，2006
[50] 张圣希、张薇、李国强、顾国庆，利用顶点链编码探测表格的斜率，华东师范大学学报，2005，No．3．54-58
[51] 腾弘飞、高轩，中国围棋棋谱在装填布局中的工程应用，《大连理工大学学报》，1995年35卷4期，487-492
[52] 腾弘飞、刘峻，一种布尔代数——围棋布尔代数及其应用，《大连理工大学学报》，1998年38卷1期，43-46
[53] 李星原、高文，一种鲁棒性的结构未知表格分析方法[J]，软件学报，1999，10(11)：1216-1224
[54] IllingworthJ, Kittler J, A Survey of the Hough Transform[J], Computer Vision, Graphics, and Image Processing, 1998, 44(1): 87
[55] 郑冶枫、刘长松、丁晓青等，基于有向单连通链的表格框线检测算法[J]，软件学报，2002，13(4)：790-796．
[56] 朱泓，围棋定式一月通，上海文化出版社，1997
[57] Microsoft Corp, Microsoft Developer Network Online Document
[58] 史文革，微机图像格式大全，海洋大学出版社，1996
[59] 何斌、马天予、王运坚、朱红莲，Visual C++数字图像处理，人民邮电出版社，2001：4-674
[60] 张力，Visual C++高级编程，人民邮电出版社，2002
[61] 周长发，精通Visual C++图像编程，电子工业出版，1999
[62] 候俊杰，深入浅出MFC(第二版)，华中科技大学出版社，2001
[63] David J．Kruglinski、Scot Wingo、George Shepherd，Programming Visual C++6.0技术内幕(第五版)，北京希望电子出版社，1999
[64] Walter Savitch，C++面向对象程序设计(第五版)，清华大学出版社，2004
[65] 罗希平、田捷、诸葛婴等，图像分割方法综述，模式识别和人工智能，1999：300-304
[66] 勒宏磊、朱蔚萍、李立源等，二维灰度直方图的最佳分割方法，模式识别与人工智能，Vol．12，No．3，Sept 1999．
[67] 高永英、张利、吴国威，一种基于灰度期望值的图像二值化算法，中国图像图形学报，Vol．4(A)，No．6，June 1999．
[2] Bribiesca E, A Chain Code for Representing 3D Curves, Pattern Recognition, 2000, 33(5): 755～765
[3] Yuan J、Suen C Y, An Optimal O(n) Algorithm for Identifying Line Segments form a Sequence of Chain Codes, Pattern Recognition, 1995, 28(5): 635～645
[4] 石秀、施泽生，FCC到VCC的转化[J]，小型微型计算机系统，2001，22(11)：1326～1330．
[5] 尚振宏、刘明业，运用Freeman准则的直线检测算法，计算机辅助设计与图形学学报，2005，17(1)：49～53．
[6] G. Y. TANG, A Discrete Version of Green's Theorem[J], IEEETransactions on Pattern Analysis and Machine Intelligence, 1982, 4(3): 242～250
[7] 陈优广、张薇、黄穗，图像区域边界抽取与链码树结构生成算法，华东师范大学学报(自然科学版)，2006年3月77～85．
[8] 姜一女，简谱识别方法的研究，浙江大学博士学位论文，2006
[9] 陈根方，OMR研究与原型系统开发，浙江大学博士学位论文，2003
[10] David Bainbridge、Tim Bel, An extensible Optical Music Recognition system, 1996 Australasian Computer Science Conference. (Melbourne, Australia): 308~317.
[11] K. Todd Reed, J. R. Parker, Automatic Computer Recognition of Printed Music, Laboratory for computer Vision, Department of Computer Science, University of Calgary, i015-4651/96 IEEE 1996
[12] 陈优广、顾国庆等，一种新的表格单元格矩形识别算法，计算机工程-2006年13期
[13] 黄锦德、郝红卫等，一种新的表格识别特征提取方法，计算机工程-2006年6期
[14] 汤英，面向对象的表格图像版面分析方法研究，华中科技大学学报：自然科学版-2005年12期
[15] 管继斌、明德烈，基于游程的倾斜表格图像的快速检测和校正，华中科技 大学学报：自然科学版-2005年8期
[16] Kenneth R．Castleman，数字图像处理，电子工业出版社，2006
[17] John E．Hopcroft等，自动机理论、语言和计算导论，机械工业出版社，2004
[18] Freeman H, Computer processing of line-drawing images, Computing Surveys, 1974, 6(1): 57-97
[19] Freeman H, On the encoding of arbitrary geometric configuration, IRE Trans, 1961, EC-10(2): 260-268
[20] Freeman H, Techniques for the digital computer analysis of chain-encoded arbitrary plane curves, Proc. Natl. Elect. Conf, 1961, 17 (Oct.): 421-432
[21] Freeman H, A technique for the classification and recognition of geometric patterns, Proc. 3rd. Intl. Congress on Cybernetics Namtur, 1961: 348-368
[22] Sidhu G S, Boute R T. Property encoding:applications in binary picture encoding and boundary following, IEEE Trans. Comp, 1972, C-21 (11): 1206-1216
[23] Merrill R. D, Representation of contours and regions for efficient computer search. Comm, ACM, 1973, 16(2): 69-82
[24] Bribiesca E, A new chain code. Pattern Recognition, 1999, 32: 235-251
[25] 顾国庆、许彦冰，数字图像区域标定的方法，上海理工大学学报，Vol．23，No．4，2001：295-299
[26] 许彦冰, 顾国庆, Method to generate vertex chain code and the calculation of geometric quantities, Journal of Shanghai University, Vol. 5 Suppl. (Sep. 2001) 144-146
[27] 顾国庆, 陈可, Region-Labeling-Automata for Images in Square, Triangular and Hexagonal Lattice, Advances in Computer and Information Technology, The Journal of Three Dimensional Images, 17(2003)161-165
[28] 顾国庆、陈可, Region-Labeling-Automata for Images in Square, Triangular and Hexagonal Lattice, Advances in Computer and Information Technology, The Proceedings of 2002 International Conference on Computer and Information Technology, (Aizu-Wakamatsu City, Japan, Sept. 11-14, 2002) 134-138
[29] 王涤琼、张薇、顾国庆，用顶点链编码计算图像区域的密集度和体态比， 华东师范大学学报(自然科学版)，2005，1：59～62。
[30] Charles Petzold，Windows程序设计，北京大学出版社
[31] 黄穗、张薇，基于边缘矩阵的链编码追踪算法，石河子大学学报 2005，Vol．23，No．5，P．644-646
[32] 杨素娣、顾国庆、黄穗，基于区域标定自动机的区域个数统计算法，计算机应用，2006年09期
[33] 顾国庆、许彦冰，数字图像区域标定的方法，上海理工大学学报，Vol．23，No．4，2001：295-299
[34] Geraets W. G. M.、van Daatselaar A. N、Vermeil J. G. C, An efficient filling algorithm for counting regions[J], Computer Methods and Programs in Biomedicine, 2004, 76, (1): 1-11
[35] Marius C. Codrea, Note: An algorithm for contour-based region filling, Computers & graphics. 29(2005) p441～450
[36] T. Pavlidis, Filling algorithms for raster graphics, Comput. Graphics Image Process, 1979, 10: 126～141.
[37] Gregory Y. Tang, Region Filling with the Use of the Discrete Green Theorem[J], Computer Vision, Graphics, and Image Processing, 1988, 42: 297～305.
[38] Mingwu Ren、Wangkou Yang、Jingyu Yang, A new and fast contour-filling algorithm, Pattern Recognition, 2005, 38: 2564～2577
[39] 任明武、杨静宇、孙涵，一种新的基于链码描述的轮廓填充方法，中国图象图形学报，2001，6(4)：348～352
[40] Mingwu Ren, Wangkou Yang, Jingyu Yang, A new and fast contour-filling algorithm, Pattern Recognition, 2005, 38: 2564～2577
[41] 李国强、张薇、顾国庆，顶点链编码和区域面积的计算方法，上海理工大学学报，Vol．25，No．3，2003
[42] 王涤琼、张薇、顾国庆，利用顶点链编码计算图像区域密集度和体态比，华东师范大学学报2005 Vol．1
[43] 张薇，链编码技术及其在图像处理中的应用，上海理工大学硕士学位论文，2003
[44] 翟燕生、徐莹，围棋入门，金盾出版社，2005
[45] 王志鹏、贺君平，围棋死活1000题，北京体育大学出版社，2004
[46] 黄希文，阶梯围棋教室：从入门到业余初段，辽宁科学技术出版社，2002
[47] 严德甫、晏天章，围棋圣经：玄玄棋经·珍珑棋局破解，团结出版社，2005
[48] http://bigo.baduk.org/chinese/ocr.html
[49] 沈晗，非均匀光照文本图像的分割，华东师范大学硕士论文，2006
[50] 张圣希、张薇、李国强、顾国庆，利用顶点链编码探测表格的斜率，华东师范大学学报，2005，No．3．54-58
[51] 腾弘飞、高轩，中国围棋棋谱在装填布局中的工程应用，《大连理工大学学报》，1995年35卷4期，487-492
[52] 腾弘飞、刘峻，一种布尔代数——围棋布尔代数及其应用，《大连理工大学学报》，1998年38卷1期，43-46
[53] 李星原、高文，一种鲁棒性的结构未知表格分析方法[J]，软件学报，1999，10(11)：1216-1224
[54] IllingworthJ, Kittler J, A Survey of the Hough Transform[J], Computer Vision, Graphics, and Image Processing, 1998, 44(1): 87
[55] 郑冶枫、刘长松、丁晓青等，基于有向单连通链的表格框线检测算法[J]，软件学报，2002，13(4)：790-796．
[56] 朱泓，围棋定式一月通，上海文化出版社，1997
[57] Microsoft Corp, Microsoft Developer Network Online Document
[58] 史文革，微机图像格式大全，海洋大学出版社，1996
[59] 何斌、马天予、王运坚、朱红莲，Visual C++数字图像处理，人民邮电出版社，2001：4-674
[60] 张力，Visual C++高级编程，人民邮电出版社，2002
[61] 周长发，精通Visual C++图像编程，电子工业出版，1999
[62] 候俊杰，深入浅出MFC(第二版)，华中科技大学出版社，2001
[63] David J．Kruglinski、Scot Wingo、George Shepherd，Programming Visual C++6.0技术内幕(第五版)，北京希望电子出版社，1999
[64] Walter Savitch，C++面向对象程序设计(第五版)，清华大学出版社，2004
[65] 罗希平、田捷、诸葛婴等，图像分割方法综述，模式识别和人工智能，1999：300-304
[66] 勒宏磊、朱蔚萍、李立源等，二维灰度直方图的最佳分割方法，模式识别与人工智能，Vol．12，No．3，Sept 1999．
[67] 高永英、张利、吴国威，一种基于灰度期望值的图像二值化算法，中国图像图形学报，Vol．4(A)，No．6，June 1999．