SIMD
swMATH ID:  3445 
Software Authors:  Chen, Ling; Chuang, Henry Y.H. 
Description:  An efficient algorithm for complete Euclidean distance transform on meshconnected SIMD The Euclidean distance transform (EDT) converts a binary image into one where each pixel has a value equal to its Euclidean distance to the nearest foreground pixel. It has important uses in image analysis, computer vision, and robotics where high speed computation is essential. A sequential algorithm which does not require global operations is first presented. We then apply a sequence of algorithm transformations to convert it into a parallel algorithm for meshconnected SIMD computers. For an n× n image on an equalsized processor array, the time complexity is O(n). An algorithm for computing large EDT problems on smaller processor arrays is also given. For an n× n image on a g× g processor array, the time complexity is O((n 2 /g) log(n/g)). 
Homepage:  http://www.sciencedirect.com/science/article/pii/016781919400103H 
Keywords:  Euclidean distance transform; Image analysis; Meshconnected SIMD computer; Complexity analysis 
Related Software:  
Referenced in:  3 Publications 
Standard Articles
1 Publication describing the Software, including 1 Publication in zbMATH  Year 

An efficient algorithm for complete Euclidean distance transform on meshconnected SIMD. Zbl 0875.68941 Chen, Ling; Chuang, Henry Y. H. 
1995

Referenced by 4 Authors
1  Chen, Ling 
1  Chuang, Henry Y. H. 
1  Hirata, Tomio 
1  Shen, Hong 
Referenced in 3 Serials
1  Acta Informatica 
1  Parallel Computing 
1  Japan Journal of Industrial and Applied Mathematics 
Referenced in 3 Fields
3  Computer science (68XX) 
1  Convex and discrete geometry (52XX) 
1  Numerical analysis (65XX) 