(3.236.100.6) 您好!臺灣時間:2021/04/24 02:23
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:朱國隆
研究生(外文):Kuo-lung Chu
論文名稱:以多邊型逼近二維曲線之理論與研究
論文名稱(外文):Optimal Polygonal Approximation of Digitized Curves Using a Genetic Algorithm Combined with Perimeter Object Function
指導教授:楊慶煜楊慶煜引用關係
指導教授(外文):Ching-yu Yang
學位類別:碩士
校院名稱:國立高雄應用科技大學
系所名稱:模具工程系碩士班
學門:工程學門
學類:機械工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:中文
論文頁數:75
中文關鍵詞:多邊型圖形逼近基因演算法
外文關鍵詞:Polygonal approximationgenetic algorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:617
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:20
  • 收藏至我的研究室書目清單書目收藏:2
一般來說,多邊型圖形逼近(Polygonal approximation)的作法分為兩大類,一、最佳化的方法(Optimal polygonal approximation),且大都使用動態規劃(Dynamic programming)方法來逼近圖形。二、規則性的逼近法(Heuristic algorithms),使用一定的運算規則去得到所需逼近的圖形。本研究的方法,以基因演算法結合最大周長法去逼近圖形,以達到最佳化之逼近。
本文中評量各種圖形逼近法,判別方法可分為兩大部分。一、干擾的資料,即當原圖檔因擷取上的誤差、或是擷取時的不穩定,造成圖形的平移或旋轉,依此作為評量各種圖形逼近法在此條件下的表現。二、改變比例放大係數,即當原圖檔因距離上的不同,造成圖形的放大或縮小,依此做為評量的依據。以基因演算法結合最大周長法去逼近圖形時,當圖形的平移或旋轉時,最大的周長並不會改變。當圖形放大或縮小時,周長值會改變,但所構成最大周長值的染色體,因其相對極大值不變,即構成最大周長的點位置不改變,所以不管是干擾的資料或是改變比例放大係數,基因演算法結合最大周長法去逼近圖形在此條件下都擁有極佳的表現。
Polygonal approximation divides into two catalogers, one is optimal polygonal approximation that uses the optimization algorithms to solve the problem, and the other is the heuristic algorithms that use the certain operational rule to approximate the polygonal.
In this paper, testify of the polygonal approximation can be divided two part. One is the performance of the perturbations of data that pretend perturbations of data by shift or rotation the data when capture image in instability environment in order to test polygonal approximation algorithms. The other changes the algorithms scale parameters that pretend perturbations of data by change scale parameter when capture image in different distant to compare the polygonal approximation algorithms. The results show that genetic algorithm combined with maximum perimeter of object function is stable and reliable whatever the image picture is rotated or shifted. The chromosome of perimeter is the same value in image picture whatever the image picture is shifted or rotated. Therefore, genetic algorithms combined with maximum perimeter objection function that performs well in most of cases.
摘 要 i
ABSTRACT ii
誌 謝 iii
目 錄 iv
圖目錄 vi
表目錄 viii
一、序論 1
1.1 前言 1
1.2 研究動機與目的 1
1.3 文獻回顧 1
1.4 本文架構 6
二、最佳化圖形逼近法 7
2.1 題目說明(PROBLEM FORMULATION) 7
2.2 誤差分析(ERROR MEASURES) 7
2.3 研究動機(MOTIVATION) 11
2.4 減少疊代之研究(ITERATIVE REDUCED SEARCH) 11
2.5 最少線段最佳化問題(OPTIMAL ALGORITHMS FOR MIN-ΕPROBLEM) 12
2.6 最小誤差問題之最佳化(OPTIMAL ALGORITHMS FOR MIN-# PROBLEM) 13
三、逼近法判定準則 14
3.1 前言 14
3.2 改變比例放大係數 14
3.3 單一度量測(MONOTONIC MEASURE) 16
3.4 和諧度量測(CONSISTENCY MEASURE) 17
3.5 端點的穩定性(ENDPOINT STABILITY) 20
3.6 資料變動時穩定性(DATA PERTURBATION STABILITY) 21
3.7 優越值(FIGURE OF MERIT) 23
3.8 實驗結果 23
四、基因演算法 28
4.1 前言 28
4.2 簡介 28
4.3 流程說明 29
4.3.1 隨機化(RANDOMIZE) 29
4.3.2 適應函數(EVALUATE FITNESS FUNCTION) 29
4.3.3 輪盤法(ROULETTE WHEEL SELECTION) 31
4.3.4 交配 31
4.3.5 突變 32
五、基因演算法結合最大周長與測試標準 34
5.1 前言 34
5.2 目標函數證明 34
5.3 端點的穩定性(ENDPOINT STABILITY)測試 40
5.4 資料變動時穩定性(DATA PERTURBATION STABILITY)測試 40
六、結果與討論 42
6.1 前言 42
6.2 四邊形驗證 42
6.3 圓形點資料取四點驗證 43
6.4 旋轉測試 43
6.5 基因演算法的收斂性 45
6.6 實例說明 51
6.7 標準曲線圖形測試 53
七、結論與建議 57
八、參考文獻 58
九、個人簡歷 62
1. F. Attneave, 1954, “Some informational aspects of visual perception”, Psychol. Rev, vol.61, no.3, pp. 183-193.
2. C. Teh, R. Chin, (1989), On the detection of dominant points in digital curves, IEEE Trans. PAMI 11, pp.859—872.
3. T. Phillips, A. Rosenfeld, 1987, A method of curve partitioning using arc-chord distance, Pattern Recognition Lett, pp.5285—288.
4. U. Ramer, 1972, An iterative procedure for the polygonal approximation of plane curves, Comput. Graphics Image Process. pp.1, 244—256.
5. Q. Ji, R. Haralick, (1998), Breakpoint detection using covariance propagation, IEEE Trans. PAMI 20 (8), pp.845—851.
6. T. X. Zhang, R. Haralick, V. Ramesh, 1994, Corner detection using the MAP technique, in: Proceedings of the 12th International Conference on Pattern Recognition, pp. 549—551.
7. T. Kadonaga, K. Abe, 1995, Comparison of methods for detecting corner points from digital curves, in: International Workshop on Graphics Recognition, pp. 3—12.
8. P.L. Rosin, 1997, Techniques for assessing polygonal approximations of curves, IEEE Trans. PAMI 19 (6) ,pp.659—666.
9. Kurozumi Y., Davis W.A. , 1982, Polygonal approximation by the minimax method, Computer Vision, Graphics and Image Processing, 19, pp.248-264.
10. Imai H., Iri M. , 1988, Polygonal approximations of a curve (formulations and algorithms), in Computational Morphology, G.T.Toussaint, (Ed), 71-86, North-Holland, Amsterdam.
11. Ph.D. Alexander Kolesnikov,2003,Efficient Algorithms for Vectorization and Polygonal approximation,http://cs.joensuu.fi/~koles/.
12. Montanari U. 1970, A note on a minimal length polygonal approximation to digitized curve, Comm. ACM, 13, pp.41-47.
13. Salotti M. , 2002, Optimal polygonal approximation of digitized curves using the sumof square deviations criterion, Pattern Recognition, 35(2),pp.435-443.
14. Schroeder K., Laurent P., October 1999, Efficient polygon approximations for shape signatures, Proc. Int. Conf. on Image Processing-ICIP’99, Kobe, Japan, 2,pp.811-814.
15. Chung K.-L., 2002, Yan W.-M., Chen W.-Y., Efficient algorithms for 3-D polygonalapproximation based on LISE criterion, Pattern Recognition, 35: pp.2539-2548.
16. Ray B.K., Ray K.S. , 1993, Determination of optimal polygon from digital curve using L1 norm, Pattern Recognition, 26(4),pp.505-509.
17. Heckbert P.S., Garland M. , 1997, Survey of polygonal surface simplification algorithms, Technical Report, CS Dept., Carnegie Mellon University.
18. Zhang H., Guo J. , 2001, Optimal polygonal approximation of digital planar curvesusing meta-heuristics, Pattern Recognition, 34, pp.1429-1436.
19. Perez J.C., Vidal E. , 1994, Optimum polygonal approximation of digitized curves, Pattern Recognition Letters, 15: pp.743-750.
20. Haugland D., Heber J., Husøy J., Optimization algorithm for ECG compression, Medical & Biological Engineering & Computing, 35,pp.420-424,1997.
21. Mori K., Wada K., Toraichi K. , 1999, Function approximated shape representation using dynamic programming with multi-resolution analysis, Proc. Int. Conf. on Signal Process. and Applications &Technology-ICSPAT''99, Orlando, USA.
22. Salotti M. , September 2000, Improvement of Perez and Vidal algorithm for the decomposition of digitized curves into line segments, Proc. Int. Conf. on Pattern Recognition-ICPR’00, Barcelona, Spain, 2: pp.882-886.
23. Salotti M. , 2001, An efficient algorithm for the optimal polygonal approximation of digitized curves, Pattern Recognition Letters, 22: pp.215-221.
24. Stone H. , 1961, Approximation of curves by line segments, Math. Comput., 15: pp.40-47.
25. Bellman R. , 1961, On the approximation of curves by line segments using dynamic programming, Comm. ACM, 4(6): pp.284.
26. Bellman R. , 1957, Dynamic Programming, Princeton University Press, New Jersey.
27. Gluss B. , 1962, Further remarks on line segment curve-fitting using dynamic programming, Comm. ACM, 5,pp.441-443.
28. Lawson C.L. , 1964, Characteristics properties of the segmentation rational minimax approximation problem, Numer. Math., 6: pp.293-301.
29. Cox M.G. , 1971, Curve fitting with piecewise polynomials, J. Inst. Math. Appl., 8: pp.36-52.
30. Cantoni A. , 1971, Optimal curve fitting approximation with piecewise linear functions, IEEE Trans. Computers, 20: pp.54-67.
31. Papakonstantinou G. , 1985, Optimal polygonal approximation of digital curves, Signal Processing, 8: pp.131-135.
32. Sklansky J., Gonzalez V. , 1980, Fast polygonal approximation of digitized curves.Pattern Recognition, 12: pp.327-331.
33. Dunham J. , 1986, Optimum uniform piecewise linear approximation of planar curves, IEEE Trans. Pattern Analysis and Machine Intelligence, 8(1): pp.67-75.
34. Imai H., Iri M. , 1986, Computational-geometric methods for polygonal approximations of a curve, Computer Vision, Graphics and Image Processing, pp.31-41.
35. Imai H., Iri M. , 1986, An optimal algorithm for approximating a piecewise linear function, J. of Information Processing, 9(3): pp.159-162.
36. Rosin, Paul L, 2003, “Assessing the behaviour of polygonal approximation algorithms” Pattern Recognition Volume: 36, Issue: 2, February, pp. 505-518.
37. J. Inesta, M. Buendia, M. Sarti, 1996, Local symmetries of digital contours from their chain codes, Pattern Recognition 29 (10) ,pp.1737—1749.
38. T. Deveau, 1985, Reducing the number of points in a plane curve representation, in: Proceedings on Auto-Carto, Vol. VII, pp. 152—160.
39. A. Fu, H. Yan, K. Huang, 1997, A curve bend function method to characterize contour shapes, Pattern Recognition 30 (10) ,pp.1661—1671.
40. T. Melen, T. Ozanian, 1993, A fast algorithm for dominant point detection on chain-coded contours, in: Proceedings of the Fifth International Conference on Computer Analysis of Images and Patterns, pp. 245—253.
41. F.-H. Cheng, W.-H. Hsu, 1988, Parallel algorithm for corner finding on digital curves, Pattern Recognition Lett. 8,pp.47—54.
42. J. Hu, H. Yan, Polygonal-approximation of digital curves based on the principles of perceptual organization, Pattern Recognition 30 (5) (1997) ,pp.701—718.
43. A. Deguchi, S. Aoki, 1990, Regularized polygonal approximation for analysis and interpretation of planar contour figures, in: International Conference on Pattern Recognition, Vol. 1, pp. 865—869.
44. Douglas, T. Peucker, 1973, Algorithms for the reduction of the number of points required to represent a digitized line or its caricature, Canad. Cartographer 10 111—122.
45. S. Pei, J. Horng, 1994, Corner point detection using nest moving average, Pattern Recognition 27 1533—1537.
46. A. Rosenfeld, E. Johnston, 1973, Angle detection on digital curves, IEEE Trans. Comp. 22, pp.875—878.
47. K. Wu, M. Levine, 2d shape segmentation: a new approach, Pattern Recognition Lett. 17 (2) (1996) pp.133—140.
48. T. Kadonaga, K. Abe, 1995, Comparison of methods for detecting corner points from digital curves, in: International Workshop on Graphics Recognition, pp. 3—12.
49. Y. Sato, 1992, “Piecewise Linear Approximation of Plane Curves by Perimeter Optimization” Pattern Recognition, vol. 25, pp. 1,535-1,543.
50. Shu-Chien Huang, Yung-Nien Sun, 1998, Determination of Optimal Polygonal Approximation Using Genetic Algorithms, IEEE International Conference on 4-9 May 1998.
51. 周鵬程,2001,遺傳演算法原理與應用,全華科技圖書.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
系統版面圖檔 系統版面圖檔