3D block-based medial axis transform and chessboard distance transform based on dominance

作     者：Lin, Shih-Ying Horng, Shi-Jinn Kao, Tzong-Wann Fahn, Chin-Shyurng Fan, Pingzhi Chen, Yuan-Hsin Khan, Muhammad Khurram Bourgeois, Anu Terano, Takao 

作者机构：Natl Taiwan Univ Sci & Technol Dept Elect Engn Taipei Taiwan Natl Taiwan Univ Sci & Technol Dept Comp Sci & Informat Engn Taipei Taiwan Natl United Univ Dept Elect Engn Miaoli Taiwan Technol & Sci Inst No Taiwan Dept Elect Engn Taipei Taiwan SW Jiaotong Univ Inst Mobile Commun Chengdu 610031 Peoples R China King Saud Univ Ctr Excellence Informat Assurance Riyadh 11451 Saudi Arabia Georgia State Univ Dept Comp Sci Atlanta GA 30302 USA Tokyo Inst Technol Dept Computat Intelligence & Syst Sci Tokyo Japan 

出 版 物：《IMAGE AND VISION COMPUTING》 (图像与视觉计算)

年 卷 期：2011年第29卷第4期

页      面：272-285页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 0702[理学-物理学] 

基　　金：National Science Council [NSC 96-2918-I-011-002, 96-2221-E-011-022-, 95-2221-E-011-032-MY3] 111 Project [111-2-14] 

主　　题：Parallel algorithm Image processing CREW PRAM model Block-based medial axis transform Chessboard distance transform Euclidean distance transform 

摘      要：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 N-3, 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. (C) 2010 Elsevier BM. All rights reserved.