OPTIMUM POLYGONAL-APPROXIMATION OF DIGITIZED-CURVES

被引:159
作者
PEREZ, JC
VIDAL, E
机构
[1] Departamento de Sistemas Informáticos y Computación (DSIC), Universidad Politécnica de Valencia, 46071 Valencia, Camino de Vera s/n
关键词
POLYGONAL APPROXIMATION; SHAPE REPRESENTATION; DOMINANT POINTS; DYNAMIC PROGRAMMING;
D O I
10.1016/0167-8655(94)90002-7
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Given N ordered points in the plane and a constant M < N, an efficient algorithm is proposed to find M points, among those given, which define a polygonal curve that is a globally optimal approximation.to the given points. The algorithm accommodates any properly defined error measure and the use of the most popular of these measures is studied in detail to maximize the computational efficiency. Experiments are reported showing the performance and usefulness of the proposed method.
引用
收藏
页码:743 / 750
页数:8
相关论文
共 34 条
[1]   ON DETECTING DOMINANT POINTS [J].
ANSARI, N ;
DELP, EJ .
PATTERN RECOGNITION, 1991, 24 (05) :441-451
[2]   NONPARAMETRIC DOMINANT POINT DETECTION [J].
ANSARI, N ;
HUANG, KW .
PATTERN RECOGNITION, 1991, 24 (09) :849-862
[3]   AN EFFICIENTLY COMPUTABLE METRIC FOR COMPARING POLYGONAL SHAPES [J].
ARKIN, EM ;
CHEW, LP ;
HUTTENLOCHER, DP ;
KEDEM, K ;
MITCHELL, JSB .
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1991, 13 (03) :209-216
[4]   ON THE APPROXIMATION OF CURVES BY LINE SEGMENTS USING DYNAMIC PROGRAMMING [J].
BELLMAN, R .
COMMUNICATIONS OF THE ACM, 1961, 4 (06) :284-284
[5]  
Bellman R., 1986, METHODS APPROXIMATIO
[6]   A NONSTATIONARY MODEL FOR THE ANALYSIS OF TRANSIENT SPEECH SIGNALS [J].
CASACUBERTA, F ;
VIDAL, E .
IEEE TRANSACTIONS ON ACOUSTICS SPEECH AND SIGNAL PROCESSING, 1987, 35 (02) :226-228
[7]  
Duda R. O., 1973, PATTERN CLASSIFICATI, V3
[9]   AN ADAPTIVE REDUCTION PROCEDURE FOR THE PIECEWISE LINEAR-APPROXIMATION OF DIGITIZED-CURVES [J].
FAHN, CS ;
WANG, JF ;
LEE, JY .
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1989, 11 (09) :967-973
[10]   FURTHER REMARKS ON LINE SEGMENT CURVE-FITTING USING DYNAMIC PROGRAMMING [J].
GLUSS, B .
COMMUNICATIONS OF THE ACM, 1962, 5 (08) :441-443