臺灣博碩士論文加值系統

在本篇論文當中，針對封閉多邊形，我們提出了兩階段封閉多邊形估計演算法。在第一階段的演算法裡，我們利用圖形分析得知覆蓋某一點的所有線段中，必定有一條屬於近似多邊形的最佳解，因此提出一個有效率的方法，可以降低傳統方法的複雜度。在第二階段的演算法當中，我們巧妙的引入曲率的運算以及量度，針對第一階段演算法所估計出來的多邊形結果再做修正，以期我們的估計結果有更良好的視覺表現。最後，實驗結果說明此方法的執行時間與影像品質皆明顯優於傳統的多邊形估計演算法。

Given a closed polygonal curve C with n points, the closed
polygonal approximation (CPA) problem is defined to find a closed
polygon P to approximate C under some error tolerance criteria.
Based on the local integral square error (LISE) and the curvature
constraint criteria, this paper presents a novel two-pass
O(Fn+mn^2)-time algorithm for solving the CPA problem where m
(<<n) denotes the minimal number of covering feasible segments for
one vertex and empirically the value of $m$ is rather small; F
(<<n^2) denotes the number of feasible approximate segments. The
first pass of our proposed algorithm can be performed in O(Fn+mn^2)
time under the given LISE; the second pass of our proposed algorithm
can be performed in O(n) time under the given curvature constraint
and the longest vertical distance consideration. Note that under the
same LISE criterion, the set of polygonal segments determined by the
first pass of our proposed CPA algorithm is minimal and is the same
as that obtained by the currently published CPA algorithm by {\sl
Chung et al.} whose algorithm takes O(n^3) time. Based on two real
closed curves for representing French and Italy, experimental results
demonstrate that our proposed two-pass CPA algorithm is faster and
more robust than the previous algorithm by Chung {\sl et al.} Based
on two real closed curves for representing a semicircle and a
chromosome, experimental results demonstrate that under the same
number of segments used, our proposed two-pass algorithm has a
better quality, but has a little execution-time degradation when
compared to the currently published CPA algorithm by {\sl Wu}.

1 Introduction 1
2 Error Criteria 4
3 Determining Feasible Approximate Segments and Covering Segment
Sets 8
3.1 O(n2){time method for determining all feasible approximate segments 8
3.2 O(Fn){time method for determining all covering segment sets 11
4 The Proposed Two{Pass Algorithm for Solving CPA Problem 15
4.1 First{pass of the proposed CPA algorithm 15
4.2 Second{pass of the proposed CPA algorithm 17
5 Experimental Results 20
6 Conclusions 26

[1] K.L. Chung, W.M. Yan, W.Y. Chen, E cient algorithms for 3-D polygonal approximation based on LISE criterion, Pattern Recognition 35 (2002) 2539-2548.
[2] T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, Section 25.2: Dijkstra's Algorithm, The MIT Press, Cambridge, MA, (1990).
[3] J.G. Dunham, Optimum uniform piecewise linear approximation of planar curves,IEEE Trans. Pattern Analysis Machine Intelligence 8 (1986) 67-75.
[4] R.C. Gonzalez, R.E. Woods, Digital Image Processing, Section 11:1.2: Polygonal Approximations, 2nd Edition, Prentice Hall, New York, (2002).
[5] J.H. Horng, J.T. Li, An automatic and e cient dynamic programming algorithm
for polygonal approximation of digital curves, Pattern Recognition Lett. 23 (2002)171-182.
[6] J. Hu, H. Yan, Polygonal approximation of digital curves based on the principles of perceptual organization, Pattern Recognition 30 (1997) 701-718.
[7] S.C. Huang, Y.N. Sun, Polygonal approximation using genetic algorithms, Pattern Recognition 32 (1999) 1409-1420.
[8] C.L.B Jordan, T. Ebrahimi, M. Kunt, Progressive content{based shape compression for retrieval of binary images, Comput. Vision Image Understanding 71 (1998) 198-212.
[9] U. Montanari, A note on minimal length polygonal approximation to a digitized curve, Comm. ACM 13 (1970) 41-47.
[10] A. Pikaz, I. Dinstein, Optimal polygonal approximation of digital curves, Pattern Recognition 28 (1995) 373-379.
[11] J.C. Perez, E. Vidal, Optimum polygonal approximation of digitized curves, Pattern Recognition Lett. 15 (1994) 743-750.
[12] P.L. Rosin, Techniques for assessing polygonal approximations of curves, IEEE Trans.Pattern Anal. Mach. Intell. 19 (6) (1997) 659-666.
[13] B.K. Ray, K.S. Ray, A non-parametric sequential method for polygonal approximation of digital curves, Pattern Recognition Lett. 15 (1994) 161-167.
[14] A. Rosenfeld and E. Johnston, Angle detection on digital curves, IEEE Trans. Comput., vol. C-22, pp. 875-878, Sept. 1973.
[15] Y. Sato, Piecewise linear approximation of planar curves by perimeter optimization,Pattern Recognition 25 (12) (1992) 1535-1543.
[16] C.H. Teh, R.T. Chin,On the detection of dominant points on digital curves, IEEE Trans. Pattern Analysis Machine Intelligence 11 (8) (1989) 859-872.
[17] W.Y. Wu, M.J. Wang, Detecting the dominant points by the curvature-based polygonal approximation, CVGIP: Graphical Model Image Process. 55 (1993) 79-88.
[18] W.Y Wu, An adaptive method for detecting dominant points, Pattern Recognition 36 (2003) 2231-2237.
[19] Y. Zhu, L.D. Seneviratne, Optimal polygonal approximation of digitized curves, IEE Proc. Vision Image and Signal Processing 144 (1997) 8-14.