Parallel distance transforms on a linear array architecture

Tsorng Lin Chia; Kuang Bor Wang; Zen Chen; Der Chyuan Lou

doi:10.1016/S0020-0190(01)00250-2

Parallel distance transforms on a linear array architecture

Tsorng Lin Chia^*, Kuang Bor Wang, Zen Chen, Der Chyuan Lou

^*Corresponding author for this work

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

3 Scopus citations

Abstract

Distance transformation (DT) has been widely used for image matching and shape analysis. In this paper, a parallel algorithm for computing distance transformation is presented. First, it is shown that the algorithm has an execution time of 6N-4 cycles, for an N×N image using a parallel architecture that requires [N/2] parallel processors. By doing so, the real time requirement is fulfilled and its execution time is independent of the image contents. In addition, a partition method is developed to process an image when the parallel architecture has a fixed number of processing elements (PEs); say two or more. The total execution time for an N×N image by employing a fixed number of PEs is 2[N²/M+2(M-1)], when M is the fixed number of PEs.

Original language	English
Pages (from-to)	73-81
Number of pages	9
Journal	Information Processing Letters
Volume	82
Issue number	2
DOIs	https://doi.org/10.1016/S0020-0190(01)00250-2
State	Published - 30 04 2002
Externally published	Yes

Keywords

Distance transformation
Linear array
Parallel processing
Partition method

Access to Document

10.1016/S0020-0190(01)00250-2

Cite this

@article{3983a21159a6461499fe87d9bf1f2459,

title = "Parallel distance transforms on a linear array architecture",

abstract = "Distance transformation (DT) has been widely used for image matching and shape analysis. In this paper, a parallel algorithm for computing distance transformation is presented. First, it is shown that the algorithm has an execution time of 6N-4 cycles, for an N×N image using a parallel architecture that requires [N/2] parallel processors. By doing so, the real time requirement is fulfilled and its execution time is independent of the image contents. In addition, a partition method is developed to process an image when the parallel architecture has a fixed number of processing elements (PEs); say two or more. The total execution time for an N×N image by employing a fixed number of PEs is 2[N2/M+2(M-1)], when M is the fixed number of PEs.",

keywords = "Distance transformation, Linear array, Parallel processing, Partition method",

author = "Chia, {Tsorng Lin} and Wang, {Kuang Bor} and Zen Chen and Lou, {Der Chyuan}",

year = "2002",

month = apr,

day = "30",

doi = "10.1016/S0020-0190(01)00250-2",

language = "英语",

volume = "82",

pages = "73--81",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Parallel distance transforms on a linear array architecture

AU - Chia, Tsorng Lin

AU - Wang, Kuang Bor

AU - Chen, Zen

AU - Lou, Der Chyuan

PY - 2002/4/30

Y1 - 2002/4/30

N2 - Distance transformation (DT) has been widely used for image matching and shape analysis. In this paper, a parallel algorithm for computing distance transformation is presented. First, it is shown that the algorithm has an execution time of 6N-4 cycles, for an N×N image using a parallel architecture that requires [N/2] parallel processors. By doing so, the real time requirement is fulfilled and its execution time is independent of the image contents. In addition, a partition method is developed to process an image when the parallel architecture has a fixed number of processing elements (PEs); say two or more. The total execution time for an N×N image by employing a fixed number of PEs is 2[N2/M+2(M-1)], when M is the fixed number of PEs.

AB - Distance transformation (DT) has been widely used for image matching and shape analysis. In this paper, a parallel algorithm for computing distance transformation is presented. First, it is shown that the algorithm has an execution time of 6N-4 cycles, for an N×N image using a parallel architecture that requires [N/2] parallel processors. By doing so, the real time requirement is fulfilled and its execution time is independent of the image contents. In addition, a partition method is developed to process an image when the parallel architecture has a fixed number of processing elements (PEs); say two or more. The total execution time for an N×N image by employing a fixed number of PEs is 2[N2/M+2(M-1)], when M is the fixed number of PEs.

KW - Distance transformation

KW - Linear array

KW - Parallel processing

KW - Partition method

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

U2 - 10.1016/S0020-0190(01)00250-2

DO - 10.1016/S0020-0190(01)00250-2

M3 - 文章

AN - SCOPUS:0037197529

SN - 0020-0190

VL - 82

SP - 73

EP - 81

JO - Information Processing Letters

JF - Information Processing Letters

IS - 2

ER -

Parallel distance transforms on a linear array architecture

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this