Local Versus Nonlocal Computation of Length of Digitized Curves

S. R. Kulkarni; S. K. Mitter; J. N. Tsitsiklis

doi:10.1109/34.297951

Local Versus Nonlocal Computation of Length of Digitized Curves

S. R. Kulkarni, S. K. Mitter, J. N. Tsitsiklis

Research output: Contribution to journal › Article › peer-review

12 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	711-718
Number of pages	8
Journal	IEEE Transactions on Pattern Analysis and Machine Intelligence
Volume	16
Issue number	7
DOIs	https://doi.org/10.1109/34.297951
State	Published - Jul 1994

All Science Journal Classification (ASJC) codes

Software
Computer Vision and Pattern Recognition
Computational Theory and Mathematics
Artificial Intelligence
Applied Mathematics

Keywords

Local
digitized curve
length
nonlocal
parallel computation

Access to Document

10.1109/34.297951

Cite this

@article{97762801622b46eab79aa51bd3806246,

title = "Local Versus Nonlocal Computation of Length of Digitized Curves",

abstract = "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.",

keywords = "Local, digitized curve, length, nonlocal, parallel computation",

author = "Kulkarni, {S. R.} and Mitter, {S. K.} and Tsitsiklis, {J. N.}",

note = "Funding Information: Manuscript received August 24, 1992; revised June 13, 1993. this work was supported in part by the U.S. Army Research Office under Contract DAAL03-86-K-017 1, by the Department of the Navy under Air Force Contract F19628-90-C-0002, and by the National Science Foundation under Contract ECS-8552419. Recommended for acceptance by Associate Editor D. P. Huttenlocher.",

year = "1994",

month = jul,

doi = "10.1109/34.297951",

language = "English (US)",

volume = "16",

pages = "711--718",

journal = "IEEE Transactions on Pattern Analysis and Machine Intelligence",

issn = "0162-8828",

publisher = "IEEE Computer Society",

number = "7",

}

TY - JOUR

T1 - Local Versus Nonlocal Computation of Length of Digitized Curves

AU - Kulkarni, S. R.

AU - Mitter, S. K.

AU - Tsitsiklis, J. N.

N1 - Funding Information: Manuscript received August 24, 1992; revised June 13, 1993. this work was supported in part by the U.S. Army Research Office under Contract DAAL03-86-K-017 1, by the Department of the Navy under Air Force Contract F19628-90-C-0002, and by the National Science Foundation under Contract ECS-8552419. Recommended for acceptance by Associate Editor D. P. Huttenlocher.

PY - 1994/7

Y1 - 1994/7

N2 - 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.

AB - 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.

KW - Local

KW - digitized curve

KW - length

KW - nonlocal

KW - parallel computation

UR - http://www.scopus.com/inward/record.url?scp=0028466532&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028466532&partnerID=8YFLogxK

U2 - 10.1109/34.297951

DO - 10.1109/34.297951

M3 - Article

AN - SCOPUS:0028466532

SN - 0162-8828

VL - 16

SP - 711

EP - 718

JO - IEEE Transactions on Pattern Analysis and Machine Intelligence

JF - IEEE Transactions on Pattern Analysis and Machine Intelligence

IS - 7

ER -

Local Versus Nonlocal Computation of Length of Digitized Curves

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this