An efficient algorithm for the optimal polygonal approximation of digitized curves

被引：63

作者：

Salotti, M ^{[1
]}

机构：

[1] Lab Univ Sci Appl Cherbourg, F-50100 Cherbourg, France

来源：

PATTERN RECOGNITION LETTERS | 2001年 / 22卷 / 02期

关键词：

polygonal approximation; dynamic programming; heuristic search; A*;

D O I：

10.1016/S0167-8655(00)00088-X

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Perez and Vidal have proposed an optimal algorithm for the polygonal approximation of digitized curves in 1994. The complexity of their algorithm is O((PS)-S-2), where P is the number of points and S is the number of segments. We address the same problem using the framework of heuristic search strategies to find the shortest path in a graph and show that the complexity of our algorithm is close to O(P-2). (C) 2001 Elsevier Science B.V. All rights reserved.

引用

页码：215 / 221

页数：7

共 9 条

[1] POLYGONAL-APPROXIMATION USING A COMPETITIVE HOPFIELD NEURAL-NETWORK [J].

CHUNG, PC ;

TSAI, CT ;

CHEN, EL ;

SUN, YN .

PATTERN RECOGNITION, 1994, 27 (11) :1505-1512

[2] OPTIMUM UNIFORM PIECEWISE LINEAR-APPROXIMATION OF PLANAR CURVES [J].

DUNHAM, JG .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1986, 8 (01) :67-75

[3] A NEW APPROACH FOR AGGREGATING EDGE POINTS INTO LINE SEGMENTS [J].

GUPTA, AK ;

CHAUDHURY, S ;

PARTHASARATHY, G .

PATTERN RECOGNITION, 1993, 26 (07) :1069-1086

[4] POLYGONAL-APPROXIMATION OF 2-D SHAPES THROUGH BOUNDARY MERGING [J].

LEU, JG ;

CHEN, L .

PATTERN RECOGNITION LETTERS, 1988, 7 (04) :231-238

[5] APPLICATION OF HEURISTIC SEARCH METHODS TO EDGE AND CONTOUR DETECTION [J].

MARTELLI, A .

COMMUNICATIONS OF THE ACM, 1976, 19 (02) :73-83

[6]

Pavlidis T., 1977, STRUCTURAL PATTERN R

[7] OPTIMUM POLYGONAL-APPROXIMATION OF DIGITIZED-CURVES [J].

PEREZ, JC ;

VIDAL, E .

PATTERN RECOGNITION LETTERS, 1994, 15 (08) :743-750

[8] Techniques for assessing polygonal approximations of curves [J].

Rosin, PL .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1997, 19 (06) :659-666

[9]

SALOTTI M, 2000, RES VISION IMAGE ANA

← 1 →