臺灣博碩士論文加值系統

機器視覺近年來已被廣泛應用於日常生活中。相關應用中，偵測物件輪廓之支配點可當成特徵，進而計算其特徵值以達成物件辨識之目的。
於本文中運用蟻群尋優法於物件支配點之偵測，針對單純背景之封閉物件影像開發一套物件支配點偵測系統，其流程為對所擷取物件影像透過影像前處理，再進行物件輪廓追蹤及斷點偵測，最後，應用蟻群尋優法偵測物件支配點。物件支配點偵測根據限制條件又可為分三種問題：(1)固定誤差問題：其限制條件乃固定逼近多邊形與原始圖形之誤差，目標函數即為最小化逼近多邊形之線段數。先前已有學者成功將蟻群尋優法應用於此類問題中，但其所提出最小誤差法之混合策略需大量運算時間。於此類問題中提出利用弦長比概念之混合策略，以改善演算法計算之效率。(2)固定線段數問題：其限制條件乃固定逼近多邊形之線段數，目標函數即為最小化逼近多邊形與原始圖形之誤差。於此類問題中首先提出於節點轉換法則中導入蟻群可行走之最遠距離概念，以符合本此類問題之限制條件。此外，針對最小誤差法、最大距離法、隨機選擇法等三種不同方法混合策略進行實驗比較。(3)無限制問題：並無任何限制條件，根據演算法特性自定目標函數。於此類問題中首先定義一適應值以將蟻群演算應用於此類問題。並且，針對最小誤差法、最大距離法、隨機選擇法等三種不同混合策略進行實驗比較。實驗結果顯示所使用之混合策略此三類問題中，均可提高計算效率。

Recently, the application of machine vision has used in our life widely. One of the applications of machine vision is object dominant point detection.
In this paper, the object dominant point detection consists of four steps: (1) Image Pre-processing: thresholding is used to extract the object i need, and then noise is reduced and object contour is smoothed by closing and opening, respectively; (2) Contour Tracking: search for the contour of extracted object; (3) Break Point Detection: detect break points using freeman chain code, and (4) Dominant Point Detection: perform ant colony optimization to approximate curve.
Dominant point detection can be classified into three categories according to restriction places in the problem: (1) Error-bounded problem: the error between approximated polygonal and object is fixed and the objective function is minimum the number of segment of approximated polygonal. Ant colony optimization has been successfully utilized in this problem. However, the hybrid strategy is time consuming. Here, a method which combines the concept of corner detection as well as the error-bounded constraint is used to segment the curves; (2) Segment-bounded problem: the number of segment of approximated polygonal is fixed and the objective function is minimum the error between approximated polygonal and object. Here, the farthest distance ant can go is conduced in node transition rule to satisfy the constraint in this problem. Moreover, three hybrid strategies, minimum error method, maximal distance method, and random selection method has been performed in this problem, and (3) No restriction problem: there is not any constrain. A fitness value has been proposed to suit this constrain. Moreover, three hybrid strategies, minimum error method, maximal distance method, and random selection method has been performed in this problem. The experimental results show that the hybrid strategies used in three problems are effectively and they takes less time than previous method.

摘要 I
Abstract II
目錄 III
圖目錄 VI
表目錄 IX
第一章 緒論 1
第一節 研究動機與目的 1
第二節 研究流程 2
第二章 文獻回顧 3
第一節 接角點偵測法 3
第二節 多邊形逼近法 5
第三節 蟻群尋優法 7
第三章 研究方法 10
第一節 影像前處理 10
第二節 輪廓追蹤 12
第三節 斷點偵測 13
第四節 曲線支配點分割 14
第四章 實驗結果與分析 25
第一節 研究限制 25
第二節 實驗結果 25
第五章 結論及建議 60
參考文獻 61
附錄一 最小誤差法螞蟻數為1於第二類問題之評估表 64
附錄二 最小誤差法螞蟻數為10於第二類問題之評估表 65
附錄三 最小誤差法螞蟻數為20於第二類問題之評估表 66
附錄四 最小誤差法螞蟻數為50於第二類問題之評估表 67
附錄五 最大距離法螞蟻數為1於第二類問題之評估表 68
附錄六 最大距離法螞蟻數為10於第二類問題之評估表 69
附錄七 最大距離法螞蟻數為20於第二類問題之評估表 70
附錄八 最大距離法螞蟻數為50於第二類問題之評估表 71
附錄九 隨機選擇法螞蟻數為1於第二類問題之評估表 72
附錄十 隨機選擇法螞蟻數為10於第二類問題之評估表 73
附錄十一 隨機選擇法螞蟻數為20於第二類問題之評估表 74
附錄十二 隨機選擇法螞蟻數為50於第二類問題之評估表 75
附錄十三 最小誤差法螞蟻數為1於第三類問題之評估表 76
附錄十四 最小誤差法螞蟻數為10於第三類問題之評估表 77
附錄十五 最小誤差法螞蟻數為20於第三類問題之評估表 78
附錄十六 最小誤差法螞蟻數為50於第三類問題之評估表 79
附錄十七 最大距離法螞蟻數為1於第三類問題之評估表 80
附錄十八 最大距離法螞蟻數為10於第三類問題之評估表 81
附錄十九 最大距離法螞蟻數為20於第三類問題之評估表 82
附錄二十 最大距離法螞蟻數為50於第三類問題之評估表 83
附錄二十一 隨機選擇法螞蟻數為1於第三類問題之評估表 84
附錄二十二 隨機選擇法螞蟻數為10於第三類問題之評估表 85
附錄二十三 隨機選擇法螞蟻數為20於第三類問題之評估表 86
附錄二十四 隨機選擇法螞蟻數為50於第三類問題之評估表 87

趙茂凱、吳文言、王冠捷(2004)，簡易的物體輪廓追蹤法，二○○四通信電子科技與應用研討會論文集，樹德科技大學，高雄，2004年5月28日。
趙茂凱(2004)，基因演算法在曲線支配點擷取之應用，義守大學工業工程與管理學系碩士論文。
趙淳威(2004)，熵理論在人臉辨識之研究，義守大學工業工程與管理學系碩士論文。
謝宗丞(2005)，路標辨識系統，義守大學工業工程與管理學系碩士論文。
Attneave, F. (1954), Some information aspects of visual perception, Psychological Review, 61(3), 83-193.
Carmona-Poyato, A., Fernández-García, N.L., Medina-Carnicer, R., and Madrid-Cuevas, F.J. (2005), Dominant point detection : A new proposal, Image and Vision Computing, 23, 1126-1236.
Chang, C. C., Hwang, S. M. and Buehrer, D J. (1991), A shape recognition scheme based on relative distances of feature points from the centroid, Pattern Recognition, 24, 1053-1063.
Dorigo, M. (1992). Optimizaiton, learning and natural algorithms, Ph.D. Thesis, Dip. Elettronica e Informazione, Politecnico di Milano, Italy.
Dorigo, M., Maniezzo, V. and Colorni, A. (1996), The ant system: optimization by a colony of cooperating agents, IEEE Trans. Systems, Man, Cybernetic. B, 26(1), 29-42.
Dunham, J.G. (1986), Optimum uniform piecewise linear approximation of planar curves, IEEE Trans. Pattern Analysis and Machine Intelligence, PAMI-8, 67-75.
Gonzalez, R. C. and Woods, R. E. (2002), Digital Image Processing (2nd ed.), New Jersey: Prentice Hall.
Maes, M. (1991), Polygonal shape recognition using string-matching techniques, Pattern Recognition, 24, 433-440.
Marji, M. and Siy, P. (2004), Polygonal representation of digital planar curves through dominant point detection – a nonparametric algorithm, Pattern Recognition, 37, 2113-2130.
Otsu, N. (1978), A threshold selection method from gray-level histograms, IEEE Trans. Systems, Man, and Cybernetics, SMC-8, 62-66.
Ray, B.K. and Ray, K.S. (1992), Detection of significant points and polygonal approximation of digitized curves, Pattern Recognition Letters, 13, 443-452.
Ray, B.K. and Ray, K.S. (1995), A new split-and-merge technique for polygonal approximation of chain coded curves, Pattern Recognition Letters, 16, 161-169.
Rosenfeld, A. and Wesaka, J.S. (1973), Angle detection on digital curves, IEEE Trans. Computers, 22, 875-878.
Rosenfeld, A. and Wesaka, J.S. (1975), An improved method of angle detection on digital curves, IEEE Trans. Computers, 24, 940-941.
Shearer, M. and Zou, J.J. (2005). Detection of dominant points based on noise suppression and error minimization. Proceedings of the Third International Conference on Information Technology and Applications, IEEE, 2005.
Sirjani, A. and Cross, G.R. (1988), An algorithm for polygonal approximation of a digital object, Pattern Recognition Letters, 7, 299-303.
Sklnsky, J. and Gonzalez, V. (1980), Fast polygonal approximation of digital curves, Pattern Recognition, 12, 327-331.
Stutzle, T. and Hoos, H. H. (2000), Max-Min ant system, Future Generation Computer Systems, 16, 889-914.
Teh, C. H. and Chin, R. T. (1989), On the detection of dominant points on digital curves, IEEE Trans. Pattern Analysis and Machine Intelligence, 11,859-872.
Tsai, D. M. (1997), Boundary-based corner detection using neural networks, Pattern Recognition, 30(1), 85-97.
Wall, K. and Danielsson, P. E. (1984), A fast sequential method for polygonal approximation of digitized curves, Computer Vision, Graphics, and Image Processing, 28, 220-227.
Wang, M. J., Wu, W. Y., Huang, L.K. and Wang, D.M. (1995), Corner detection using bending value, Pattern Recognition Letters, 16, 575-583
Wu, W. Y. and Wang, M. J. (1993), Detecting the dominant points by the curvature-based polygonal approximation, GVGIP: Graphical Models and Image Processing, 55, 79-88.
Wu, W. Y. (2001a), A simple method for dominant point detection, The Imaging Science Journal, 49, 125-134.
Wu, W. Y. (2001b), Two-dimensional object recognition through string matching, The Imaging Science Journal, 49, 231-221.
Wu, W. Y. (2003a), A dynamic method for dominant point detection, Graphical Models, 64, 304-315.
Wu, W. Y. (2003b), Dominant point detection using adaptive bending value, Image and Vision Computing, 21, 517-525.
Yin, P. Y. (1999), Genetic algorithms for polygonal approximation of digital curves, International Journal of Pattern Recognition and Artificial Intelligence, 13, 1061-1082.
Yin, P. Y. (2000), A tabu search approach to polygonal approximation of digital curves, International Journal of Pattern Recognition and Artificial Intelligence, 14, 243-255.
Yin, P. Y. (2003), Ant colony search algorithms for optimal polygonal approximation of plane curves, Pattern Recognition, 36, 1783-1797.