Approximating euclidean distance transform with simple operations in cellular processor arrays

Samad Razmjooei; Piotr Dudek

doi:10.1109/CNNA.2010.5430299

Approximating euclidean distance transform with simple operations in cellular processor arrays

Samad Razmjooei, Piotr Dudek

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

Abstract

This paper presents a new algorithm for computing a distance transform, particularly suitable for massively parallel cellular processor arrays. The proposed Enhanced City Block Distance Transform (ECBDT) achieves good approximation to Euclidean distances, operating with 'increment' and 'minimum' operations only, and requiring only local 4-neighbour communication. The distance values are calculated in a wavepropagating manner, and are suitable for implementation on asynchronous processor arrays. The performance of the algorithm is adjustable through parameters. Presented simulation results illustrate the operation of the algorithm, and discuss the accuracy of the distance approximation that is achieved in comparison to Euclidean, City Block, Chessboard and Chamfer distance transforms. © 2010 IEEE.

Original language	English
Title of host publication	2010 12th International Workshop on Cellular Nanoscale Networks and their Applications, CNNA 2010\|Int. Workshop Cell. Nanoscale Netw. Appl., CNNA
DOIs	https://doi.org/10.1109/CNNA.2010.5430299
Publication status	Published - 2010
Event	2010 12th International Workshop on Cellular Nanoscale Networks and their Applications, CNNA 2010 - Berkeley, CA Duration: 1 Jul 2010 → …

Conference

Conference	2010 12th International Workshop on Cellular Nanoscale Networks and their Applications, CNNA 2010
City	Berkeley, CA
Period	1/07/10 → …

Access to Document

10.1109/CNNA.2010.5430299

Cite this

@inproceedings{b837f19a9bde40bd9d29948f4e7efee6,

title = "Approximating euclidean distance transform with simple operations in cellular processor arrays",

abstract = "This paper presents a new algorithm for computing a distance transform, particularly suitable for massively parallel cellular processor arrays. The proposed Enhanced City Block Distance Transform (ECBDT) achieves good approximation to Euclidean distances, operating with 'increment' and 'minimum' operations only, and requiring only local 4-neighbour communication. The distance values are calculated in a wavepropagating manner, and are suitable for implementation on asynchronous processor arrays. The performance of the algorithm is adjustable through parameters. Presented simulation results illustrate the operation of the algorithm, and discuss the accuracy of the distance approximation that is achieved in comparison to Euclidean, City Block, Chessboard and Chamfer distance transforms. {\textcopyright} 2010 IEEE.",

author = "Samad Razmjooei and Piotr Dudek",

year = "2010",

doi = "10.1109/CNNA.2010.5430299",

language = "English",

isbn = "9781424466795",

booktitle = "2010 12th International Workshop on Cellular Nanoscale Networks and their Applications, CNNA 2010|Int. Workshop Cell. Nanoscale Netw. Appl., CNNA",

note = "2010 12th International Workshop on Cellular Nanoscale Networks and their Applications, CNNA 2010 ; Conference date: 01-07-2010",

}

Razmjooei, S & Dudek, P 2010, Approximating euclidean distance transform with simple operations in cellular processor arrays. in 2010 12th International Workshop on Cellular Nanoscale Networks and their Applications, CNNA 2010|Int. Workshop Cell. Nanoscale Netw. Appl., CNNA. 2010 12th International Workshop on Cellular Nanoscale Networks and their Applications, CNNA 2010, Berkeley, CA, 1/07/10. https://doi.org/10.1109/CNNA.2010.5430299

Approximating euclidean distance transform with simple operations in cellular processor arrays. / Razmjooei, Samad; Dudek, Piotr.
2010 12th International Workshop on Cellular Nanoscale Networks and their Applications, CNNA 2010|Int. Workshop Cell. Nanoscale Netw. Appl., CNNA. 2010.

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Approximating euclidean distance transform with simple operations in cellular processor arrays

AU - Razmjooei, Samad

AU - Dudek, Piotr

PY - 2010

Y1 - 2010

N2 - This paper presents a new algorithm for computing a distance transform, particularly suitable for massively parallel cellular processor arrays. The proposed Enhanced City Block Distance Transform (ECBDT) achieves good approximation to Euclidean distances, operating with 'increment' and 'minimum' operations only, and requiring only local 4-neighbour communication. The distance values are calculated in a wavepropagating manner, and are suitable for implementation on asynchronous processor arrays. The performance of the algorithm is adjustable through parameters. Presented simulation results illustrate the operation of the algorithm, and discuss the accuracy of the distance approximation that is achieved in comparison to Euclidean, City Block, Chessboard and Chamfer distance transforms. © 2010 IEEE.

AB - This paper presents a new algorithm for computing a distance transform, particularly suitable for massively parallel cellular processor arrays. The proposed Enhanced City Block Distance Transform (ECBDT) achieves good approximation to Euclidean distances, operating with 'increment' and 'minimum' operations only, and requiring only local 4-neighbour communication. The distance values are calculated in a wavepropagating manner, and are suitable for implementation on asynchronous processor arrays. The performance of the algorithm is adjustable through parameters. Presented simulation results illustrate the operation of the algorithm, and discuss the accuracy of the distance approximation that is achieved in comparison to Euclidean, City Block, Chessboard and Chamfer distance transforms. © 2010 IEEE.

U2 - 10.1109/CNNA.2010.5430299

DO - 10.1109/CNNA.2010.5430299

M3 - Conference contribution

SN - 9781424466795

BT - 2010 12th International Workshop on Cellular Nanoscale Networks and their Applications, CNNA 2010|Int. Workshop Cell. Nanoscale Netw. Appl., CNNA

T2 - 2010 12th International Workshop on Cellular Nanoscale Networks and their Applications, CNNA 2010

Y2 - 1 July 2010

ER -

Approximating euclidean distance transform with simple operations in cellular processor arrays

Abstract

Conference

Access to Document

Fingerprint

Cite this