在本論文中我們發展了平行技術有效率地在影像處理中來解三維區塊式中軸轉換(3D BB-MAT) 問題以及三維棋盤式距離轉換 (3D CDT) 問題。對於這些問題我們拿來和王氏學者的結果作比較，我們的演算法結果能降低作出來的成本。
特別地，區塊式中軸轉換 (BB-MAT)以及棋盤式距離轉換 (CDT) 一般而言皆被視為兩種全然不同地影像計算問題。事實上，它們之間彼此存在一些關聯的特性。在本論文的研究中首先導出且證明它們兩者之間彼此的關係特性。
由支配優勢 (dominance) 的觀念重新定義成為反向-支配優勢 (reverse-dominance) 技術，運用此技術執行三維區塊式中軸轉換 (3D BB-MAT) 演算法、我們亦達成三維棋盤式距離轉換 (3D CDT) 問題的計算。對一個大小是N3的三維二元影像而言，我們的平行演算法能夠解出三維區塊式中軸轉換 (3D BB-MAT) 問題也就能夠解出三維棋盤式距離轉換 (3D CDT) 問題。所有我們的演算法結果是架構在可重置光匯流排陣列 (AROB) 或同時讀唯一寫(CREW)平行隨機存取機器 (PRAM) 計算模型上。
據我們所知，在本論文中的結果，三維區塊式中軸轉換(3D BB-MAT) 以及三維棋盤式距離轉換 (3D CDT)是至目前為止已知成本最低的。

In this dissertation we present parallel techniques for solving the three dimensional block-based medial axis transform (3D BB-MAT) problem and the three dimensional chessboard distance transform (3D CDT) problem in image processing efficiently. The costs of resulting algorithms are reduced in comparison with those of Wang’s for these problems.
Specifically, the BB-MAT and CDT were usually viewed as two completely different image computation problems. In fact, there exist some equivalent properties between them. The relationship between both of them is first derived and proved in this study.
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. For a 3D binary image of size N3, our parallel algorithms can solve both 3D BB-MAT and 3D CDT problems. All of our results are for the on the arrays with reconfigurable optical buses (AROB) or the concurrent read exclusive write (CREW) parallel random access machine (PRAM) computational models.
To the best of our knowledge, this work is the lowest costs for the 3D BB-MAT and 3D CDT algorithms known.

BIBLIOGRAPHY
[1] N. Amenta and M. W. Bern, “Surface reconstruction by Voronoi filtering,” Discrete & Computational Geometry, vol. 22, no. 4, pp. 481-504, 1999.
[2] C. Arcelli and G. Sanniti di Baja, “Finding local maxima in a pseudo-Euclidian distance transform,” Computer Vision, Graphics, and Image Processing, vol. 43, no. 3, pp. 361-367, 1988.
[3] H. Blum, “Models for the perception of speech and visual form,” MIT press 11, pp. 362-380, 1967.
[4] A. Bonnassie, F. Peyrin, and D. Attali, “A new method for analyzing local shape in three-dimensional images based on medial axis transformation,” IEEE Trans. on System, Man, and Cybernetics — Part B: Cybernetics, vol. 33, no. 4, pp. 700-705, 2003.
[5] G.. Borgefors, “Distance transformations in digital images,” Computer Vision, Graphics, and Image Processing, vol. 34, pp. 344-371, 1986.
[6] G. Borgefors, I. Ragnemalm, and G. Sanniti di Baja, “The Euclidean distance transform: finding the local maxima and reconstructing the shape,” Proc. of the 7th Scandinavian Conference on Image Analysis, Aalborg, Denmark, vol. 2, pp. 974-981, 1991.
[7] J. W. Bruce and P. J. Giblin, Curves and Singularities: A Geometrical Introduction to Singularity Theory, Cambridge University Press, Cambridge, U.K., 2nd Edition, 1992.
[8] L. Calabi and W. E. Hartnett, “Shape recognition, prairie fires, convex deficiencies and skeletons,” American Mathematical Monthly, vol. 75, pp. 335–342, 1968.
[9] S. Chandran, S. K. Kim, and D. M. Mount, “Parallel computational geometry of rectangles,” Algorithmica, vol. 7, no. 1, pp. 25-49, 1992.
[10] S. Chandran and D. Mount, “Shared memory algorithms and the medial axis transform,” IEEE Workshop on Computer Architecture for PAMI, pp. 44-50, 1987.
[11] L. Chen and H. Y. H. Chuang, “A fast algorithm for Euclidean distance maps of a 2-D binary image,” Information Processing Letters, vol. 51, pp.25-29, 1994.
[12] Y. J. Chen, S. J. Horng, T. W. Kao, and H. R. Tsai, “Parallel algorithm for the medial axis transform of binary images,” The Australian Computer Journal, vol. 30, no. 1, pp.12-19, 1998.
[13] T. Culver, J. Keyser, and D. Manocha, “Accurate computation of the medial axis of a polyhedron,” Proc. of the 5th Symposium ACM on Solid Modeling, pp. 179-190, 1999.
[14] P. E. Danielsson, “Euclidean distance mapping,” Computer Vision, Graphics, and Image Processing, vol. 14, pp. 227-248, 1980.
[15] A. Datta, “Constant-time algorithm for medial axis transform on the reconfigurable mesh,” Proc. of the 13th International Symposium on Parallel Processing and the 10th Symposium on Parallel and Distributed Processing, pp. 431-435, 1999.
[16] T. K. Dey and S. Goswami, “Tight cocone: a water-tight surface reconstructor,” Journal of Computing and Information Science in Engineering, vol. 3, no. 4, pp. 302-307, 2003.
[17] T. K. Dey and W. Zhao, “Approximating the medial axis from the Voronoi diagram with a convergence guarantee,” Algorithmica, vol. 38, pp. 179-200, 2003.
[18] A. Ferreira, I. Guérin-Lassous, K. Marcus, and A. Rau-Chaplin, “Parallel computation on interval graphs using PC clusters: algorithms and experiments,” Proc. Europar'98, Lecture Notes in Computer Science, Southampton, UK, vol. 1470, pp. 875-886, 1998.
[19] A. Ferreira and S. Ubéda, “Parallel complexity of the medial axis transform,” Proc. of International Conference on Image Processing (ICIP'95), vol. 2, pp. 105-107, 1995.
[20] A. Ferreira and S. Ubéda, “Computing the medial axis transform in parallel with eight scan operations,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 21, no. 3, pp. 277-282, 1999.
[21] A. Fujiwara, M. Inoue, T. Masuzawa, and H. Fujiwara, “A simple parallel algorithm for the medial axis transform,” IEICE Trans. on Information and System, vol. E79D, no. 8, pp. 1038-1045, 1996.
[22] P. J. Giblin and B. B. Kimia, “On the local form of symmetry sets, and medial axes, and shocks in 3D,” Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 566–573, 2000.
[23] P. J. Giblin and B. B. Kimia, “On the local form and transitions of symmetry sets, medial axes, and shocks,” International Journal of Computer Vision, vol. 54, no. 1-3, pp. 143-157, 2003.
[24] P. J. Giblin and B. B. Kimia, “A formal classification of 3D medial axis points and their local geometry,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 26, pp. 238-251, 2004.
[25] P. J. Giblin, B. B. Kimia, A. J. Pollitt, “Transitions of the 3D medial axis under a one-parameter family of deformations,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 31, no. 5, pp. 900-918, 2009.
[26] J. JáJá, An Introduction to Parallel Algorithms, Addison-Wesley, 1992.
[27] J. F. Jenq and S. Sahni, “Serial and parallel algorithms for the medial axis transform,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 14, no. 12, pp. 1218-1224, 1992.
[28] S. K. Kim, “Optimal parallel algorithms for region labeling and medial axis transform of binary images,” SIAM Journal of Discrete Mathematics, vol. 4, no. 3, pp. 385-396, 1991.
[29] B. B. Kimia, A. Tannenbaum, and S. W. Zucker, “Shapes, shocks, and deformations,” IJCV, vol. 15, pp. 189–224, 1995.
[30] M. N. Kolountzakis and K. N. Kutulakos, “Fast computation of the Euclidean distance maps for binary image,” Information Processing Letters, vol. 43, pp. 181-184, 1992.
[31] L. Lam, S. W. Lee and C. Y. Suen, “Thinning methodologies-a comprehensive survey,” IEEE Trans. on PAMI, vol. 14, pp. 869 – 885, 1992.
[32] L. J. Latecki, Q. N. Li, B. X. Bai, and W. Y. Liu, “Skeletonization using SSM of the distance transform,” IEEE International Conference on image Processing, vol. 5, pp. 349-352, 2007.
[33] D. T. Lee, “Medial axis transformation of a planar shape,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 4, pp. 363-369, 1982.
[34] Y. H. Lee, “Designing efficient parallel algorithms for some digital image processing problems,” Ph.D. Dissertation, NTUST, Taiwan, 2003.
[35] Y. H. Lee and S. J. Horng, “Chessboard distance transform and the medial axis transform are interchangeable,” Proc. of the IEEE Symposium on Parallel and Distributed Processing, pp. 424-428, 1996.
[36] Y. H. Lee and S. J. Horng, “Equivalence of the chessboard distance transform and the medial axis transform,” International Journal of Computer Mathematics, vol. 65, pp. 165-177, 1997.
[37] Y. H. Lee and S. J. Horng, “Optimal computing the chessboard distance transform on parallel processing systems,” Computer Vision and Image Understanding, vol. 73, pp. 374-390, 1999.
[38] F. F. Leymarie and B. B. Kimia, “The medial scaffold of 3D unorganized point clouds,” IEEE Trans. on PAMI, vol. 29, no. 2, pp. 313-330, 2007.
[39] F. F. Leymarie and B. B. Kimia, “The shock scaffold for representing 3D shape,” Visual Form, vol. 2059 in Lecture Notes in Computer Science, pp. 216–229, 2001.
[40] F. F. Leymarie and M. D. Levine, “Simulating the grassfire transform using an active contour model,” IEEE Trans. on PAMI, vol. 14, no. 1, pp. 56–75, 1992.
[41] S. Y. Lin, S. J. Horng, T. W. Kao, and Y. R. Wang, “An O(1) time parallel algorithm for the dominance counting and 3D block-based medial axis transform on AROB,” Proc. of the 6th International Conference on Parallel and Distributed Computing Applications and Technologies (PDCAT'05), pp. 603-609, 2005.
[42] S. Y. Lin, S. J. Horng, T. W. Kao, C. S. Fahn, P. Fan, C. L. Lee, A. G. Bourgeois, “3D block-based medial axis transform and chessboard distance transform on the CREW PRAM,” ICA3PP, pp. 83-96, 2008.
[43] J. Matousek, “Geometric range searching,” ACM Computing Surveys, vol. 26, no. 4, 1994.
[44] C. M. Ma and M. Sonka, “A fully parallel 3D thinning algorithm and its applications,” CVIU, vol. 64, no. 3, pp. 420–433, 1996.
[45] A. Montanvert, “Medial line: graph representation and shape description,” Proc. of the 8th International Conference on Pattern Recognition, pp. 430-432, 1986.
[46] P. Morrison and J. J. Zou, “An effective skeletonization method based on adaptive selection of contour points,” Proc. of the 3th International Conference on Information Technology and Applications (ICITA'05), vol.1, pp. 644-649, 2005.
[47] Kálmán Palágyi, “A 3-subiteration 3D thinning algorithm for extracting medial surfaces,” Pattern Recognition Letters, vol. 23, pp. 663-675, 2002.
[48] Kálmán Palágyi, “A 3D fully parallel surface-thinning algorithm,” Theoretical Computer Science, vol. 406, pp. 119-135, 2008.
[49] M. Peternell, “Geometric properties of bisector surfaces,” Graphical Models, vol. 62, no. 3, pp. 202–236, 2000.
[50] F. P. Preparata and M.I. Shamos, Computational Geometry An Introduction, Springer-Verlag, 1985.
[51] M. Ramanathan and B. Gurumoorthy, “Constructing medial axis transform of extruded and revolved 3D objects with free-form boundaries,” Computer-Aided Design, vol. 37, Issue 13, pp. 1370-1387, 2005.
[52] E. Remy and E. Thiel, “Medial axis for chamfer distances: computing look-up tables and neighbourhoods in 2D or 3D,” Pattern Recognition Letters, vol. 23, no. 6, pp. 649–661, 2002.
[53] E. Remy and E. Thiel, “Look-Up tables for medial axis on squared Euclidean distance transform,” Proc. of the 11th DGCI, Discrete Geometry for Computer Image, Naples, Italy, vol. 2886, pp. 224–235, 2003.
[54] A. Rosenfeld and J. L. Pfalz, “Sequential operations in digital picture processing,” Journal of the ACM, vol. 13, pp, 471-494, 1966.
[55] A. Rosenfeld and J. L. Pfaltz, “Computer representation of planar regions by their skeletons,” Communications of the ACM, vol. 10, pp. 119-125, 1967.
[56] A. V. Saúde, M. Couprie and R. A. Lotufo, “Discrete 2D and 3D Euclidean medial axis in higher resolution,” Image and Vision Computing, vol. 27, pp. 354-363, 2009.
[57] O. Schwarzkopf, “Parallel computation of distance transforms,” Algorithmica, vol. 6, pp. 685-697, 1991.
[58] E. C. Sherbrooke, N. M. Patrikalakis, and E. Brisson, “Computation of medial axis transform of 3D polyhedra,” Proc. of the 3th ACM Solid Modeling Conference, Salt Lake City, Utah, pp. 187-199, 1995.
[59] E. C. Sherbrooke, N. M. Patrikalakis, and E. Brisson, “An algorithm for the medial axis transform of 3D polyhedral solids,” IEEE Trans. on Visualization and Computer Graphics, vol. 2, no. 1, 1996.
[60] F. Y. Shih and C. C. Pu, “Medial axis transformation with single-pixel and connectivity preservation using Euclidean distance computation,” Proc. 10th IEEE Inter. Conf. Pattern Recognition, Atlantic City, NJ, pp. 723-725, June 1990.
[61] H. R. Tsai, “Parallel algorithms for the medial axis transform on linear arrays with a reconfigurable pipelined bus system,” Proc. of the 9th International Conference on Parallel and Distributed Systems (ICPADS'02), pp. 123-128, 2002.
[62] L. G. Valiant, “A bridging model for parallel computation,” Communications of the ACM, vol. 38, no. 8, pp.103-111, 1990.
[63] K. P. Vo, “Prob 80-4,” Journal of Algorithms, vol. 4, no. 3, pp.366-368, 1982
[64] Y. R. Wang, “Fast algorithms for block-based medial axis transform on the LARPBS,” Proc. of the IEEE International Conference on Systems, Man, and Cybernetics, 2005.
[65] Y. R. Wang, “A novel O(1) time algorithm for 3D block-based medial axis transform by peeling corner shells,” Parallel Computing, vol. 35, no. 2, pp. 72-82, 2009.
[66] Y. R. Wang and S. J. Horng, “An O(1) time algorithm for the 3D Euclidean distance transform on the CRCW PRAM Model,” IEEE Trans. on Parallel and Distributed Systems, vol. 14, no. 10, pp. 973-982, 2003.
[67] Y. R. Wang and S. J. Horng, “Parallel algorithms for arbitrary dimensional Euclidean distance transforms with applications on arrays with reconfigurable optical buses,” IEEE Trans. on System, Man, and Cybernetics — Part B: Cybernetics, vol. 34, no. 1, pp. 517-532, 2004.
[68] H. Yamada, “Complete Euclidean distance transformation by parallel operation,” Proc. of the 7th International Conference on Pattern Recognition, vol. 1, pp. 69-71, 1984.
[69] C. H. Wu, S. J. Horng and H. R. Tsai, ”Efficient Parallel Algorithms for Hierarchical Clustering on Arrays with Reconfigurable Optical Buses,” Journal of Parallel and Distributed Computing, vol. 60, no. 9, pp.1137-1153, 2000.
[70] C.H. Wu, S.J. Horng, “Fast and Scalable Selection Algorithms with Applications to Median Filtering,” IEEE Trans. Parallel and Distributed Systems, vol. 14, no. 10, pp. 983-992, 2003.
[71] C.H. Wu, S.J. Horng, and H.R. Tsai, ”Optimal Parallel Algorithms for Computer Vision Problems,” J. Parallel and Distributed Computing, vol. 62, no. 6, pp. 1021-1041, 2002.
[72] S. Pavel and S.G. Akl, ”Matrix Operations Using Arrays with Reconfigurable Optical Buses,” Parallel Algorithms and Applications, vol. 8, pp. 223-242, 1996.
[73] S. Pavel and S. G. Akl, ”On the Power of Arrays with Reconfigurable Optical Bus,” Int. Conf. on Parallel and Distributed Processing Techniques and Applications, pp. 1443-1454, 1996.
[74] S. Pavel and S. G. Akl, “Integer sorting and routing in arrays with reconfigurable optical buses,” Int. J. Foundations Comput., vol. 9, pp. 99-120, 1998.
[75] Y. Ben-Asher, D. Peleg, R. Ramaswami and A. Schuster, “The Power of Reconfiguration,” Journal of Parallel and Distributed Computing, vol. 13, no. 2, pp. 139-153, 1991.
[76] Z. Guo, R. G. Melhem, R.W. Hall, D. M. Chiarulli and S. P. Levitan, “Pipelined Communication in Optically Interconnected Arrays,” Journal of Parallel and Distributed Computing, vol. 12, no. 3, pp. 269-282, 1991.
[77] K. Li, Y. Pan and S. Q. Zheng, “Fast and Processor Efficient Parallel Matrix Multiplication Algorithms on a Linear Array with a Reconfigurable Pipelined Bus System,” IEEE Trans. Parallel and Distributed Systems, vol. 9, no. 8, pp. 705-720, Aug. 1998.
[78] K. Li, Y. Pan and S. Q. Zheng, “Parallel Computing Using Optical Interconnections,” Kluwer Academic, 1998.
[79] Y. Pan and M. Hamdi, “Quicksort on a Linear Array with a Reconfigurable Pipelined Bus,” Proc. International Symposium on Parallel Architectures, Algorithms, and Networks, pp. 313-319, 1996.
[80] Y. Pan and K. Li, ”Linear Array with a Reconfigurable Pipelined Bus System – Concepts and Applications,” Journal of Information Sciences, vol. 106, no. 3-4 pp. 237-258, 1998.