ESTIMATING SHORTEST PATHS AND MINIMAL DISTANCES ON DIGITIZED 3-DIMENSIONAL SURFACES

被引:47
作者
KIRYATI, N [1 ]
SZEKELY, G [1 ]
机构
[1] SWISS FED INST TECHNOL,INST COMMUN TECHNOL,IMAGE SCI LAB,CH-8092 ZURICH,SWITZERLAND
关键词
CHAIN CODES; DISTANCE TRANSFORMATION; GEODESIC PATHS; PERIMETER ESTIMATION; SHORTEST PATHS; 3D SHAPE ANALYSIS;
D O I
10.1016/0031-3203(93)90018-R
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
The estimation of minimal distances and shortest paths between points on a continuous three-dimensional (3D) surface given in digitized form is considered. The suggested approach combines recently developed length estimators for digitized 3D curves with well-known algorithms for computing shortest paths in sparse graphs, to estimate the minimal distances and the corresponding shortest paths in a systematic, computationally efficient way. In comparison to differential geometry techniques for solving the continuous geodesic problem and to computational geometry algorithms for solving the discrete geodesic probelm, the suggested hybrid continuous-discrete approach is well suited to applications in which continuous surfaces are given in digitized form, computation time must be relatively short and an approximate solution is acceptable. In particular, the suggested method can be used to efficiently obtain a good initial approximation as an input to other algorithms, thus improving their speed of convergence and reducing their tendency to converge to insignificant local minima. Some confusion has recently arisen with respect to the relation between the design of length estimators and the optimization of local distances for distance transformations. Since 3D length estimation is a central concept in the suggested approach, an effort is made to resolve discrepancies and to highlight the similarities and differences between these problems. It is shown that while in two dimensions the design of length estimators and the design of local weights for distance transformations are rather similar, in three dimensions digital geometry dictates that these problems are different. The contexts in which each of the two approaches should be preferred are identified.
引用
收藏
页码:1623 / 1637
页数:15
相关论文
共 18 条
[1]   ESTIMATION OF LENGTH FOR DIGITIZED STRAIGHT-LINES IN 3 DIMENSIONS [J].
AMARUNNISHAD, TM ;
DAS, PP .
PATTERN RECOGNITION LETTERS, 1990, 11 (03) :207-213
[2]  
BECK JM, 1986, IEEE CG A, P18
[3]   OPTIMIZATION OF LENGTH MEASUREMENTS FOR ISOTROPIC DISTANCE TRANSFORMATIONS IN 3-DIMENSION [J].
BECKERS, ALD ;
SMEULDERS, AWM .
CVGIP-IMAGE UNDERSTANDING, 1992, 55 (03) :296-306
[4]   ESTIMATION OF THE ORIGINAL LENGTH OF A STRAIGHT-LINE SEGMENT FROM ITS DIGITIZATION IN 3 DIMENSIONS [J].
CHATTOPADHYAY, S ;
DAS, PP .
PATTERN RECOGNITION, 1992, 25 (08) :787-798
[5]   ON QUANTIZATION OF LINE-DRAWING DATA [J].
FREEMAN, H ;
GLASS, JM .
IEEE TRANSACTIONS ON SYSTEMS SCIENCE AND CYBERNETICS, 1969, SSC5 (01) :70-&
[6]  
Freeman H., 1974, Computing Surveys, V6, P57, DOI 10.1145/356625.356627
[7]  
GONDRAN M, 1984, GRAPHS ALGORITHMS, pCH2
[8]  
KIRYATI N, 1992, 11TH P ICPR HAG, VA, P259
[9]  
KIRYATI N, 1991, BIWITR125 I COMM TEC
[10]   DESIGN OF PERIMETER ESTIMATORS FOR DIGITIZED PLANAR SHAPES [J].
KOPLOWITZ, J ;
BRUCKSTEIN, AM .
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1989, 11 (06) :611-622