3D block-based medial axis transform and chessboard distance transform based on dominance |
| |
Authors: | Shih-Ying LinShi-Jinn Horng Tzong-Wann KaoChin-Shyurng Fahn Pingzhi FanYuan-Hsin Chen Muhammad Khurram KhanAnu Bourgeois Takao Terano |
| |
Affiliation: | a Department of Electrical Engineering, National Taiwan University of Science and Technology, Taipei, Taiwan, ROCb Department of Computer Science and Information Engineering, National Taiwan University of Science and Technology, Taipei, Taiwan, ROCc Department of Electronic Engineering, National United University, Miaoli, Taiwan, ROCd Department of Electronic Engineering, Technology and Science Institute of Northern Taiwan, Taipei, Taiwan, ROCe Institute of Mobile Communications, Southwest Jiaotong University, 610031, Chengdu, Chinaf Center of Excellence in Information Assurance, King Saud University, Kingdom of Saudi Arabiag Department of Computer Science, Georgia State University, Atlanta, GA 30302-4110, United Statesh Dept. Computational Intelligence and Systems Science, Tokyo Institute of Technology, Japan |
| |
Abstract: | Traditionally, the block-based medial axis transform (BB-MAT) and the chessboard distance transform (CDT) were usually viewed as two completely different image computation problems, especially for three dimensional (3D) space. In fact, there exist some equivalent properties between them. The relationship between both of them is first derived and proved in this paper. One of the significant properties is that CDT for 3D binary image V is equal to BB-MAT for image V' where it denotes the inverse image of V. In a parallel algorithm, a cost is defined as the product of the time complexity and the number of processors used. The main contribution of this work is to reduce the costs of 3D BB-MAT and 3D CDT problems proposed by Wang [65]. Based on the reverse-dominance technique which is redefined from dominance concept, we achieve the computation of the 3D CDT problem by implementing the 3D BB-MAT algorithm first. For a 3D binary image of size N3, our parallel algorithm can be run in O(logN) time using N3 processors on the concurrent read exclusive write (CREW) parallel random access machine (PRAM) model to solve both 3D BB-MAT and 3D CDT problems, respectively. The presented results for the cost are reduced in comparison with those of Wang's. To the best of our knowledge, this work is the lowest costs for the 3D BB-MAT and 3D CDT algorithms known. In parallel algorithms, the running time can be divided into computation time and communication time. The experimental results of the running, communication and computation times for the different problem sizes are implemented in an HP Superdome with SMP/CC-NUMA (symmetric multiprocessor/cache coherent non-uniform memory access) architecture. We conclude that the parallel computer (i.e., SMP/CC-NUMA architecture or cluster system) is more suitable for solving problems with a large amount of input size. |
| |
Keywords: | Parallel algorithm Image processing CREW PRAM model Block-based medial axis transform Chessboard distance transform Euclidean distance transform |
本文献已被 ScienceDirect 等数据库收录! |
|