本文的目的在於建立一套文字辨識系統，提出新的觀點以單一字元為基礎，利用切割演算法提升系統的效率。本系統包含了兩個部分，切割字元模組與辨識模組。
本研究提出的切割字元模組，模擬中文字型的特性，利用切割演算法將一個中文字的結構切割成為兩個字旁的區塊。辨識模組則是使用總像素(Total pixel count)、筆劃穿越數(crossing count features)以及周圍的背景區域(Peripheral background area features)，利用此三種特徵值來做六個階段的特徵篩選，進而由資料庫中得到候選名單。最後經由樣本比對的方法，找出候選名單中與文字影像最相似的結果 
最後分別測試典型辨識系統與加了切割式系統的差異，在效率方面後者明顯的快出了許多。

In this paper, we purpose to construct a printed Chinese OCR system by segmenting an optical character, which included character segmentation kernel and character recognition kernel. Character segmentation kernel segments Chinese character into two parts by the distinctions of Chinese. Character recognition kernel achieves 6-layers feature filters by three character features, which are total pixel count feature, crossing count feature and peripheral background area feature. After these feature filters processed, the system will evaluate the remaining candidate characters by template matching. Our experiment shows that the OCR with segmentation method has better performance on the template-matching stage.

目錄
第1章 前言	1
1.1 研究背景與動機	1
1.2 研究目的	2
1.3 研究概念	3
1.4 研究前提假設	3
1.5 研究系統架構	4
1.6 論文結構	8
第2章 文獻探討	9
2.1 名詞解釋	9
2.2 路徑計算技術	10
2.2.1 代克思托演算法 (Dijkstra's algorithm)	10
2.2.2 A*演算法 (A* Algorithm)	11
2.2.3 Floyd-Warshall演算法 (Floyd-Warshall Algorithm)	13
2.2.4 小節結論	13
2.3 特徵擷取(feature extraction)	14
2.3.1 輪廓方向特徵(contour directional feature)	14
2.3.2 Oka’s cellular特徵(Oka’s cellular feature)	15
2.3.3 總黑色像素個數 (Total pixel count)	16
2.3.4 筆劃穿越數 (Crossing count)	16
2.3.5 周圍的背景區域(Peripheral background area)	17
2.3.6 小結結論	18
第3章 文字的切割與分類	19
3.1 前言	19
3.2 中文字的分類	19
3.3 文字分類的定義與演算法	20
3.3.1 文字切割線	20
3.3.2 切割路徑圖	21
3.3.3 切割路徑圖的定義	21
3.3.4 建立切割路徑圖	23
3.3.5 建立縱向切割路徑圖演算法	25
3.3.6 建立橫向切割路徑圖演算法	27
3.4 文字物件	28
3.5 本章結論	29
第4章 文字的辨識過程	30
4.1 前言	30
4.2 字元尺寸的調校	31
4.3 文字位置調整	32
4.4 文字辨識過程的特徵擷取	32
4.5 文字辨識過程的特徵值篩選	32
4.5.1 第一大類「橫向排列類」的篩選	33
4.5.2 第二大類「縱向排列類」的篩選	36
4.5.3 第三大類「無法切割類」的篩選	39
4.6 文字辨識過程的樣本比對	40
4.6.1 相似度比對(Match measure)	40
4.6.2 樣本比對的方法	41
4.6.3 樣本比對演算法	43
第5章 系統概述與實驗結果	44
5.1 系統概述	44
5.2 實驗結果	45
5.2.1 實驗一：效能比較	45
5.2.2 實驗二：樣本比對次數統計	46
第6章 結論與未來展望	47
6.1 結論	47
6.2 研究貢獻	47
6.3 未來展望	47
參考文獻          49
附錄	52

表目錄
表 3-1：文字分類個數表	20
表 3-2：文字物件	28
表 3-3：子圖物件	28
表 5-1：樣本測試	45
表 5-2：掃瞄測試	45
表 5-3：樣本比對次數比較表	46

圖目錄
圖 1-1：本研究概念	3
圖 1-2：典型字元辨識系統架構	6
圖 1-3：切割式文字辨識系統架構	7
圖 2-1：Dijkstra’s Algorithm在一個起點與兩節點的運作	11
圖 2-2：Dijkstra演算法(左為無障礙，右為有障礙)	12
圖 2-3：Best-First-Search(左為無障礙，右為有障礙)	12
圖 2-4：A*演算法(左為無障礙，右為有障礙)	12
圖 2-5：黑色像素的3x3鄰居	15
圖 2-6：四個角度群組	15
圖 2-7：Oka’s Cellular	16
圖 2-8: 筆劃穿越數示意圖	16
圖 2-9：周圍的背景區域範例圖	17
圖 3-1：文字切割線	20
圖 3-2：最短路徑圖	21
圖 3-3：橫向排列切割的範例	22
圖 3-4：縱向排列切割的範例	22
圖 3-5：文字切割範例(橫向排列)	22
圖 3-：切割方向優先權意示圖	23
圖 3-7：無界定範圍的切割線(左為非期望的切割線)	24
圖 3-8：橫向排列切割線範圍	24
圖 3-9：橫向排列實際切割情形	24
圖 3-10：縱向排列切割線範圍	25
圖 3-11：縱向排列實際切割情形	25
圖 4-1：典型文字辨識系統示意圖	30
圖 4-2：文字對齊至左上角	32
圖 4-3：第一大類篩選流程圖	35
圖 4-4：第二大類篩選流程圖	38
圖 4-5：第三大類篩選流程圖	40
圖 4-6：圖片由中向右橫移一格(灰色與淺灰色部份為位移後不同的部份	41
圖 4-7：輸入影像經過八個方向位移。	42
圖 5-1：程式執行畫面	44

[1]	A. Zramdini and R. Ingold, "Optical font recognition using typographical features," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.20, No.8, pp.877-882, Aug 1998.
[2]	Anil K. Jain, S. Prabhakar, Lin Hong, "A multichannel approach to fingerprint classification", IEEE Trans. on PAMI, Vol.21, No.4, pp.348-359, 1999.
[3]	C.Y. Suen, Y.Y. Tang, Q.R. Wang, Feature Extraction in the Recognition of Chinese Characters Printed in Different Fonts, ICCC6, 136-143.
[4]	D. Gabor, "Theory of communication," J. IEE Vol.93, pp.429-459, 1946
[5]	E. W. Dijkstra, "A note on two problems in connexion with graphs". Numerische Mathematik. 1 (1959), S. 269–271 
[6]	F. Sun, S. Omachi, and H. Aso, "Precise selection of candidates for handwritten character recognition using feature regions," IEICE Trans. Inf. & Syst. Vol.E79-D, no.5, pp.510-515, 1996.
[7]	G. Nagy, "Chinese character recognition: a twenty-five-year retrospective" ICPR88: 9th Int'l Conf. on Pattern Recognition, Vol.1,pp.163-167, 1998
[8]	H. Fujisawa, Y. nakano, and K. Kurino, "Segmentation Methods for Character Recognition: From Segmentation to Document Structure Analysis," Proc. IEEE, Vol. 80, No. 7, July 1992, pp. 1079-1091.
[9]	Hart, P. E.; Nilsson, N. J.; Raphael, B.. "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Transactions on Systems Science and Cybernetics SSC4 (2): pp. 100–107,  1968
[10]	J. Fan, D.K.Y Yau, A.K. Elmagarmid, and W.G. Aref, "Automatic image segmentation by integrating color-edge extraction and seeded region growing," IEEE Transactions on Image Processing, vol. 10, pp.1454-1466, Oct.2001.
[11]	J. G. Daugman, "High confidence visual recognition of  persons by a test of statistical independence," IEEE Trans. on PAMI, Vol. 15, No.I1, pp.1148-1161, 1993.
[12]	J. Wang and J. Jean, "Segmentation of Merged Characters by Neural Networks and Shortest Path," Pattern Recognition, vol. 27, No.5, pp.649-658, 1994.
[13]	J.R. Parker, "Algorithms, for image processing and computer vision," John Wiley and Sons Inc., New York, pp116-145, 1996.
[14]	K. W. Seo, J. Y. Kim, J. M. Yoon, and K. S. Chung. "Comparison of feature performance and its application to feature combination in off-line handwritten Korean Alphabet recognition," International Jounal Pattern Recognition and Artical Intelligence, vol.12, no.2 pp.251-261, 1998.
[15]	K. Yamada,"Optimal sampling intervals for Gabor features and printed Japanese character recognition", Proc, ICDAR-95, 1995, pp.I-150-153.
[16]	L. Tu, et al., "Recognition of handprinted Chinese characters by feature matching," Int. Conf. on Computer Processing of CHinese and Oriental Languages, pp.154-157, 1991.
[17]	L. Y. Tseng And R. C. Chen, "Segmenting handwritten Chinese characters based on heuristic merging of stroke bounding boxes and dynamic programming," Pattern Recognition Letters, Volumn, Issue 10, August, 1998, pp. 963-973.
[18]	M. Lades et al.,"Disortion invariant object recognition in the dynamic link architecture,"IEEE Trans. on Computer, Vol.42 No.3 pp.300-311, 1993.
[19]	N. Otsu, "A threshold selection method from gray-level histograms," IEEE Trans. System, Man, and Cybernetics, vol.9 no.1 pp.377-393, 1979.
[20]	Q. Huo, "A study on the use of gabor features for Chinese OCR" IEEE Vol.93, pp.389-392, 2001
[21]	R. G. Casey and G. Nagy, "Recursive Segmentation and Classification of  Composite Character patterns," Proc. 6th Int. Conf. pattern Recognition (Munich, Germany), 1982, pp.1023-1026.
[22]	R. Oka, "Handwitten Chinese-Japanese Characters Recognition by Using Cellular Feature", Proceedings 6th International Joint Conference on Pattern Recognition, p783-785 , 1982 
[23]	Richard G. Casey and Eric Lecolinet, "A survey of Methods and Strategies in Character Segmentation," IEEE Trans. Pattern Anal. Mach. Intell., vol18, no.7, pp.690-706, 1996
[24]	S. Mori,C.Y. Suen, "Historical review of OCR research and development," Proceedings of the IEEE, Vol.80,No.7,pp.1029-1058,1992
[25]	Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. "Introduction to Algorithms, Second Edition. " MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 24.3: Dijkstra's algorithm, pp.595–601. 
[26]	Y. Hamamoto et al., "Recognition of handprinted Chinese characters using Gabor features," Proc. ICDAR-95, 1995, pp.I1-819-823.
[27]	晏士信, “《說文解字》指事象形考辨”, 成功大學中國文學研究所, 90年
[28]	陳映舟, “中文草書書法字帖的文字切割與辨識”, 交通大學資訊工程所, 90年
[29]	陳嘉亨, “利用決策樹方法及直接使用系統字型資料作多種類文字辨識及電子書自動建構”, 交通大學資訊科學所, 91年
[30]	趙善隆, “中文文件處理系統中使用之多核心辨識方法與簡化行語言模式”, 交通大學資訊工程所, 89年
[31]	蘇義明, “中文信封文字辨識與雜訊文字筆劃擷取”, 成功大學資訊工程所, 92年