OPTIMAL POLYGONAL-APPROXIMATION OF DIGITAL CURVES

被引：39

作者：

PIKAZ, A ^{[1
]}

DINSTEIN, I ^{[1
]}

机构：

[1] BEN GURION UNIV NEGEV,IL-84105 BEER SHEVA,ISRAEL

来源：

PATTERN RECOGNITION | 1995年 / 28卷 / 03期

关键词：

OPTIMAL POLYGONAL APPROXIMATION; CITY-BLOCK METRIC; BREADTH-FIRST-SEARCH;

D O I：

10.1016/0031-3203(94)00108-X

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

An algorithm for optimal polygonal approximation is presented. Given a value for the maximal allowed distance between the approximation and the curve, the algorithm finds an approximation with the minimal number of vertices. The city-block metric is used to measure the distance between the approximation and the curve. The algorithm worst case complexity is O(n(2)), where n is the number of points in the curve. An efficient and optimal solution for the case of closed curves where no initial point is given, is also presented.

引用

页码：373 / 379

页数：7

共 25 条

[1] THE CURVATURE PRIMAL SKETCH
ASADA, H
BRADY, M
[J]. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1986, 8 (01) : 2 - 14
[2] SOME INFORMATIONAL ASPECTS OF VISUAL PERCEPTION
ATTNEAVE, F
[J]. PSYCHOLOGICAL REVIEW, 1954, 61 (03) : 183 - 193
[3] DAVIS LS, 1977, IEEE T COMPUT, V26, P236, DOI 10.1109/TC.1977.1674812
[4] OPTIMUM UNIFORM PIECEWISE LINEAR-APPROXIMATION OF PLANAR CURVES
DUNHAM, JG
[J]. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1986, 8 (01) : 67 - 75
[5] A COMPARISON OF SPLITTING METHODS FOR THE IDENTIFICATION OF CORNER-POINTS
ESPELID, R
JONASSEN, I
[J]. PATTERN RECOGNITION LETTERS, 1991, 12 (02) : 79 - 83
[6] EVEN S, 1979, GRAPH ALGORITHMS
[7] Hart PE, 1973, PATTERN CLASSIFICATI, P271
[8] COMPUTATIONAL-GEOMETRIC METHODS FOR POLYGONAL APPROXIMATIONS OF A CURVE
IMAI, H
IRI, M
[J]. COMPUTER VISION GRAPHICS AND IMAGE PROCESSING, 1986, 36 (01): : 31 - 41
[9] KUROZUMI Y, 1970, COMMUN ASS COMPUT MA, V13, P41
[10] LIAO YZ, 1981, P PATTERN RECOGNITIO, P224

← 1 2 3 →