臺灣博碩士論文加值系統

相連像素標記演算法是針對一些區域性質相同且具連接性的像素做標記的動作，藉由給予不同的標記來區分不同的區塊，而圍棋的棋子間也有類似的關係，許多相連的棋子組成一棋串，許多棋串組成棋塊，彼此間構成連接的關係，最後計算由棋塊圍取的空地數，較多的一方為勝。
因此本論文的主要目的就是探討將相連像素標記演算法結合圍棋基本規則，以及建立輔助標記的棋形資料庫，包括連接點、斷點和邊界連接點等棋形，將其應用於圍棋的棋塊辨識以及圍空計算等，並經由實際的棋譜做驗證和探討。最後則是嘗試利用建構棋形資料庫的方法來建構一些定石基本棋形，經由定石棋形的的紀錄與再現來達到圍棋教學的目標。
關鍵詞：標記演算法、機器視覺、圍棋

Connected Components Labeling Algorithm is a labeling motion in connection with some pixels that have the same regional property and connectivity, to distinguish different blocks by giving the unique label. We can find there is a similar relation between stones in the game of Go, many connected stones consist of a stone string, many stone strings consist of a stone clustering. To determine the final result, we calculate the side with the much grounds surrounded by stone clustering is the winner.
Therefore, the main purpose of this thesis is to discuss how to combine connected components labeling algorithm with the basic rules of the game of Go, and creating the database of the patterns of the stones distribution, including connected, cut and connected to the boundary. It also applies to recognize the stone blocks and calculate the grounds surrounded by the game of Go. Then, we use some examples to put to the proof and discuss. In the end, we try to use the method of building database of the stone distribution to create basic corner evolution pattern, by way of pattern registering and displaying to reach the aim of learning the Go game.
Keywords: Connected Components Labeling Algorithm,
Binary, Go Game

誌謝……………………………………………………………………i
中文摘要………………………………………………………………ii
英文摘要………………………………………………………………iii
目錄……………………………………………………………………v
圖目錄…………………………………………………………………vii
第1章 緒論…………………………………………………1
第2章 二值化機器視覺基本理論
2.1 簡介……………………………………………………3
2.2 二值影像………………………………………………3
2.2.1 二值化處理…………………………………………4
2.3 近鄰點…………………………………………………5
2.3.1 路徑…………………………………………………6
2.3.2 連接性………………………………………………7
2.4 相連像素標記演算法…………………………………8
2.4.1 反覆法………………………………………………11
2.4.2 古典演算法…………………………………………12
2.4.3 局部等同法…………………………………………14
2.4.4 不定長度法…………………………………………15
第3章 點空系統架構描述
3.1 系統簡介………………………………………26
3.2 前置處理………………………………………27
3.3 系統流程………………………………………31
3.3.1 連接點與切斷辨識………………………………..33
3.3.2 古典演算及等同資料結構………………………..36
3.3.3 邊界連接點辨識與圍地計算……………………..40
3.4 模擬結果與探討………………………………………42
第4章 定石系統描述
4.1 系統簡介及研究動機…………………………45
4.2 資料結構說明…………………………………47
4.3 定石的學習……………………………………48
4.4 結果探討與分析………………………………55
第5章 結論與未來展望……………………………………56
參考文獻 …………………………………………………58

參考文獻
[1] Tao, H., Huang, T. S. ,”Color Image Edge Detection Using Cluster Analysis”, Proceedings. International Conference on Image Processing, p.834-6 vol.1, 1997.
[2] Kunihiko Fukushima, ”Neocogntiron: A Hierarchical Neural Network Capable of Visual Pattern Recognition, Neural Network,” vol.1, pp.119-130, 1988.
[3] Yuan-Kai Wang; Kuo-Chin Fan, ”Applying genetic algorithm on pattern recognition: an analysis and survey” Proceedings of the 13th International conference on pattern recognition,pp.740-4 vol.2
[4] Saupe D., Hartenstein H., ”Lossless acceleration of fractal image compression by fast convolution ”,
Proceedings.1996 International Coference on Image Processing, p.185-8 vol.1.
[5] A. Rosenfeld and J. L. Pfltz, ”Sequential Operators in Digital Picture Processing,” J. ACM, vol.13, pp.471-494, 1966
[6] R. Lumia, Linda G. Shapiro, and Oscar. Euniga, ”A new Connected Components Algorithm for Virtual Memory Computers,” CVGIP, vol.22, pp.287-300, 1983.
[7] Christian Ronse, and Pierre A. Devijver, ”Connected Components in Binary Images: the Detection Problem,” RESEACH STUDIES Press, England, 1984.
[8] Ramesh Jain, and Rangachar Kasturi, and Brian G.Schunck, ”MACHINE VIOSION,” McGRAW-HILL Book Co., 1995.
[9] M. Sonka, V. Hlavac, and R. Boyle, ”Image processing, analysis, and machine vision, 2nd Edition,” PWS, New York, 1998.
[10] Robert M. Haralick, and Linda G. Shapiro,” Computer And Robot Vision Volume I,” Addison-Wesley Pub. co., 1992.
[11] Harley R. Myler, and Arthur R. weeks, “Computer Imaging Recipes in C,” P T R Prentice-Hall, 1993.
[12] H. Smart, “The design and analysis of spatial data structures,” Addison-Wesley, New York, 1990.
[13] Pafael C. Gonzalez, and Richard E. Woods,” Digital image Processing”, Addison-Wesley Pub.co.
[14] J. D. Foley, A. V. Dam, S. K. Feiner, and J. F. Hughes, “Computer graphics, principle, and practice, 2nd Edition,” Addison Wesley, Reading, Mass., 1990.
[15] I. M. Spiliotis and B. G. Mertzios, ”Real-time computation of two-dimensional moments on binary image block representation,” IEEE Trans. on Image Processing, vol.7, No.11, pp.1609-1615, 1998.
[16] Di Stefano, L.; Bulgarelli, A. ”A simple and efficient connected components labeling algorithm,” IEEE Trans. on Image Analysis and Processing, pp.322-327,
1999.
[17] H. Samet, M. Tamminen. ”An Improved Approach to connected component labeling of images,”Proceedings of CVPR’86, pp.312-318, 1986.
[18] M. Abramson, and H. Wechsler, ”Competitive Reinforcement Learning for Combinatorial Problems,” IEEE Trans. on Neural Networks, page2333-2338, vol.4, 2001.
[19] Millen J. K., ”Programming the Game of Go, ”Byte Magazine, April 1981.
[20] S. Santini, R. Jain, ”Similarity Measures, Transactions on Pattern Analysis and Machine Intelligence,”Vol21, No.9, September 1999.
[21] R. Cypher, J. L. C. Sanz, and L. Snyder, “Algorithms for image component labeling on SIMD mesh connected computers,” IEEE Trans. Computer, 39:2, pp. 279-281, 1990.
[22] R. M. Haralick and L. G. Shapiro, “The consistent labeling problem: Part I,” IEEE Trans PAMI, 1, pp.173-183, 1979.
[23] R. M. Haralick and L. G. Shapiro, “The consistent labeling problem: Part II,” IEEE Trans PAMI, 1, pp.193-203, 1980.
[24] W. B. Tong, and G. Z. Lu, “Data structure for segmenting binary image,” IEEE Trans. Computer, Communication, Control and Power Engineering, pp.1146-1149, vol. 2, 1993.
[25] 顏士淨, “電腦圍棋程式Jimmy5.0之設計與製作,” 台灣大學資訊工程研究所博士論文, 1999.
[26] 原武雄, “戰鬥中的定石,” 世界文物出版社, 1982.
[27] 原武雄, “子的感覺,” 世界文物出版社, 1981.
[28] 小林光一,”圍棋必勝講座 3,” 世界文物出版社, 1984.
[29] 連國珍, “數位影像處理,” 儒林出版社, 2001.