LOCAL VERSUS NONLOCAL COMPUTATION OF LENGTH OF DIGITIZED-CURVES

被引：10
作者：
KULKARNI, SR
MITTER, SK
RICHARDSON, TJ
TSITSIKLIS, JN
机构：
[1] MIT,INFORMAT & DECIS SYST LAB,CAMBRIDGE,MA 02139
[2] AT&T BELL LABS,MATH SCI RES CTR,MURRAY HILL,NJ 07974
来源：
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE | 1994年 / 16卷 / 07期
基金：
美国国家科学基金会;
关键词：
LOCAL; NONLOCAL; PARALLEL COMPUTATION; LENGTH; DIGITIZED CURVE;
D O I：
10.1109/34.297951
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
In this paper, we consider the problem of computing the length of a curve from digitized versions of the curve using parallel computation. Our aim is to study the inherent parallel computational complexity of this problem as a function of the digitization level. Precise formulations for the digitization, the parallel computation, and notions of local and nonlocal computations are given. We show that length cannot be computed locally from digitizations on rectangular tessellations. However, for a random tessellation and appropriate deterministic ones, we show that the length of straight line segments can be computed locally. Implications of our results for a method for image segmentation and a number of open problems are discussed.
引用
收藏
页码：711 / 718
页数：8
相关论文
共 29 条
[1]  
Abelson H., 1978, Theoretical Computer Science, V6, P41, DOI 10.1016/0304-3975(78)90004-X
[2]  
AMBARTZUMIAN RV, 1987, STOCHASTIC INTEGRAL
[3]  
AMBROSIO L, 1988, CICSP63 MIT CTR INT
[4]  
AMBROSIO L, 1988, CICSP86 MIT CONTR SY
[5]  
ATTOUCH H, 1984, VARIATION CONVERGENC
[6]  
BADDELEY AJ, 1986, CWI MONOGRAPHS
[7]  
Blake A., 1986, Proceedings CVPR '86: IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No.86CH2290-5), P62
[8]  
BLAKE A., 1987, VISUAL RECONSTRUCTIO
[9]   A COMMON FRAMEWORK FOR IMAGE SEGMENTATION [J].
GEIGER, D ;
YUILLE, A .
INTERNATIONAL JOURNAL OF COMPUTER VISION, 1991, 6 (03) :227-243
[10]   STOCHASTIC RELAXATION, GIBBS DISTRIBUTIONS, AND THE BAYESIAN RESTORATION OF IMAGES [J].
GEMAN, S ;
GEMAN, D .
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1984, 6 (06) :721-741
123