A HIGH PERFORMANCE 3D EXACT EUCLIDEAN DISTANCE TRANSFORM ALGORITHM FOR DISTRIBUTED COMPUTING

作者: JULIO CESAR TORELLI , RICARDO FABBRI , GONZALO TRAVIESO , ODEMIR MARTINEZ BRUNO

DOI: 10.1142/S0218001410008202

关键词: MathematicsWorkstationImage (mathematics)AlgorithmPattern recognition (psychology)Data compressionImplementationDomain decomposition methodsCluster (physics)RoboticsArtificial intelligence

摘要: The Euclidean distance transform (EDT) is used in various methods pattern recognition, computer vision, image analysis, physics, applied mathematics and robotics. Until now, several sequential EDT algorithms have been described the literature, however they are time- memory-consuming for images with large resolutions. Therefore, parallel implementations of required specially 3D images. This paper presents a implementation based on domain decomposition well-known algorithm, analyzes its performance cluster workstations. use data compression tool to reduce communication time investigated discussed. Among obtained results, this work shows that an essential clusters low-bandwidth networks.

参考文章(32)
R.A. Lotufo, A.A. Falcao, F.A. Zampirolli, Fast Euclidean distance transform using a graph-search algorithm brazilian symposium on computer graphics and image processing. pp. 269- 275 ,(2000) , 10.1109/SIBGRA.2000.883922
WEN-FENG KUO, CHI-YUAN LIN, YUNG-NIEN SUN, REGION SIMILARITY RELATIONSHIP BETWEEN WATERSHED AND PENALIZED FUZZY HOPFIELD NEURAL NETWORK ALGORITHMS FOR BRAIN IMAGE SEGMENTATION International Journal of Pattern Recognition and Artificial Intelligence. ,vol. 22, pp. 1403- 1425 ,(2008) , 10.1142/S0218001408006788
Per-Erik Danielsson, Euclidean distance mapping Computer Graphics and Image Processing. ,vol. 14, pp. 227- 248 ,(1980) , 10.1016/0146-664X(80)90054-4
MARIA FRUCCI, OVERSEGMENTATION REDUCTION BY FLOODING REGIONS AND DIGGING WATERSHED LINES International Journal of Pattern Recognition and Artificial Intelligence. ,vol. 20, pp. 15- 38 ,(2006) , 10.1142/S0218001406004533
Yu-Hua Lee, Shi-Jinn Horng, Tzong-Wann Kao, Ferng-Shi Jaung, Yuung-Jih Chen, Horng-Ren Tsai, Parallel computation of exact Euclidean distance transform parallel computing. ,vol. 22, pp. 311- 325 ,(1996) , 10.1016/0167-8191(95)00066-6
Stanley Osher, James A Sethian, Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations Journal of Computational Physics. ,vol. 79, pp. 12- 49 ,(1988) , 10.1016/0021-9991(88)90002-2
Ling Chen, Henry YH Chuang, An efficient algorithm for complete Euclidean distance transform on mesh-connected SIMD parallel computing. ,vol. 21, pp. 841- 852 ,(1995) , 10.1016/0167-8191(94)00103-H
Frank Y. Shih, Christopher C. Pu, A skeletonization algorithm by maxima tracking on Euclidean distance transform Pattern Recognition. ,vol. 28, pp. 331- 341 ,(1995) , 10.1016/0031-3203(94)00104-T