物體變形技術為一項功能強大之技術，此技術可以在兩個或兩個以上物體之間產生一平滑形狀轉換序列。變形技術可應用於多項領域----從娛樂工業的特殊與華麗的變形效果到醫學影像之應用(例如：影像內差、器官動態可視化技術與虛擬手術)與科學可視化技術，毫無疑問，變形技術在近幾年來已成為一項重要且熱門之研究並且已成為電腦圖學核心的基礎技術。
　　本論文描述一項新的三維物體變形整合架構，在此架構下所要處理的資料型態為封閉且拓撲結構為two-manifold之三維網格物體，此方法流程簡述如下：首先，將兩個來源物體參數化並轉換到單位球上，為了控制物體的變形，我們提供使用者點選任何數量之特徵對應點，然後使用無摺疊形變技術(foldover-free warping method)透過這些已定義的特徵對應點將兩個參數化單位球調正(align). 此三維物體變形整合架構不需要產生一個共有的高複雜度的網格物體(meta-mesh)或對原始物體進行重新網格化(re-meshing)以產生相同連接關係(common connectivity)，取而代之的是利用一項新技術直接進行來源與目的物體之間幾何與連接結構之轉換，此項新技術稱為漸進式連接結構之轉換(progressive connectivity transformation)，此技術藉由動態增加或移除頂點的方式從來源物體到目的物體逐漸地進行連接結構轉換同時使用線性位置內差來產生一序列中間物體。除此之外，我們還建立一個優先順序控制函數(priority control function)以提供動畫製作者可在變形序列中更容易和彈性去控制物體特徵的顯現與消失，對動畫製作者而言，這會是一項實用的工具。另外我們也發展出的半重疊(semi-overlay)配合著幾何平滑轉換(geomorph)之技術，此技術是用來解決由連接結構轉換所產生的跳動現像(popping effects)。最後我們會展示數個由本篇論文所提的多項技術整合而成的三維物體變形架構所產生的三維物體變形。
　　除了三維物體變形之外，本論文也介紹以特徵點為基礎之影像變形技術，並且將此技術應用於醫學影像內差，我們稱此影像內差技術為以形狀為基礎並以特徵為導引之醫學影像內差，此方法是以形狀為基礎以特徵線段做導引之內差方法，此方法可求得更佳的物體形狀內差，在此方法中我們使用一自動偵測方法來產生特徵線段並自動完成特徵線段之對應，當影像相似度高時，此內差方法可以處理物體的平移、旋轉與縮放，當影像相似度低時，此方法也可以順利產生中間影像。

　　Morphing is a powerful technique to produce a shape transformation between two or more existing models.Morphing and warping have various applications ranging from special effects in the entertainment industry to medical imaging and scientific visualization. Not surprisingly, morphing and warping have received a lot of interest lately. They have been the cores of fundamental operations in computer graphics.
　　This thesis describes a new integrated scheme for metamorphosis between two closed manifold genus-0　polyhedral models. This new morphing scheme includes several novel techniques. In the correspondence　establishment process, spherical parameterizations of the source and target models are created first. To control the morphing, several feature vertex pairs are specified and a fold-over free warping method is presented to align two spherical embeddings. In the transformation process, the proposed method does not create a merged meta-mesh or execute re-meshing to construct a common connectivity for morphs. Alternatively, a novel technique for the connectivity transformation of two spherical　parameterizations is employed to generate the intermediate meshes. This technique dynamically adds or removes vertices to gradually transform the connectivity of 3D polyhedrons from a source model into a target model and simultaneously creates the intermediate shapes. In addition, a priority control function provides the animators to control arising or dissolving of input models’ features in a morphing sequence. This is a useful tool to control a morphing sequence more easily and flexibly. Furthermore, a novel semi-overlay with a geomorph scheme is proposed to reduce the popping effects caused by the connectivity transformation. We demonstrate several examples of aesthetically pleasing morphing sequences using the proposed scheme.
　　Besides the mesh metamorphosis, this thesis introduces the feature-based image warping and applies the image warping techniques in the medical image interpolation. This interpolation method is named shape-based feature-guided medical image interpolation. The proposed method is an effective and improved method. It integrates feature line-segments to guide the shape-based method for better shape interpolation. An automatic method for finding these line segments is given. The proposed interpolation method can manage translation, rotation and scaling situations when the slices have similar shapes. It can also interpolate intermediate shapes when the successive slices do not have similar shapes.

[1] F. Lazarus and A. Verroust, “Three-Dimensional Metamorphosis: A Survey”, The Visual Computer, Vol. 14, pp. 373-389,1998.
[2] M. Alexa, “Mesh Morphing”, STAR: State of The Art Report, EUROGRAPHICS 2001.
[3] A. Lerious, C. D. Garfinkle, M. Levoy, “Feature-Based Volume Metamorphosis”, In ACM SIGGRAPH Conference Poceedings, pp. 449-456, 1995.
[4] D. Cohen-Or, D. Levin, and A. Solomovici, “Three-dimensional Distance Field Morphing“, ACM Transactions on Graphics, Vol. 17, No. 2, pp.116-141, 1998.
[5] T. Kanai, H. Suzuki and F. Kimura, “ Three-dimensional geometric metamorphosis based on harmonic maps”, The Visual Computer, pp. 166-176, 1998.
[6] T. Kanai, H. Suzuki and F. Kimura, “Metamorphosis of Arbitrary Triangular Meshes”, IEEE Computer Graphics and Applications, pp. 62-75, 2000.
[7] A. Gregory, A. State, M. Lin, D. Manocha and M. Livingston, “ Interactive Surface Decomposition for Polyhedra Morphing”, The Visual Computer, Vol. 15, No. 9, pp. 453-470, 1999.
[8] M. Zockler, D. Stalling and H.-C. Hege, “Fast and Intuitive Generation of Geometric Shape Transitions”, The Visual Computer, Vol. 16, No. 5, pp. 241-253, 2000.
[9] T.-Y. Lee and P.-H. Hung, “Fast and Intuitive Metamorphosis of 3D Polyhedral Models Using SMCC Mesh Merging Scheme”, IEEE Trans. on Visualization and Computer Graphics, Vol. 9, No. 1, pp. 85-98, 2003.
[10] M. Alexa, “Merging Polyhedral Shapes with Scattered Features”, The Visual Computer, Vol. 16, No. 1, pp. 26-37, 2000.
[11] S. Shlafman, A. Tal and S. Katz, “Metamorphosis of Polyhedral Surfaces using Decomposition”, EUROGRAPHICS, Vol. 21, No. 3, pp.219-228, 2002.
[12] T. Michikawa, T. Kanai, M. Fujita and H. Chiyokura, “Multiresolution Interpolation Meshes”. Proc. 9th Pacific Graphics International Conference (Pacific Graphics 2001), IEEE CS Press, Los Alamitos, pp.60-69, CA, October 2001.
[13] E. Praun, W. Sweldens and P. Schroder, ”Consistent Mesh Parameterization”, In ACM SIGGRAPH Conference Proceedings, pp. 179-184, 2001.
[14] C.-H. Lin and T.-Y. Lee, ”Metamorphosis of 3D Polyhedral Models Using Progressive Connectivity Transformations“, accepted to IEEE Trans. on Visualization and Computer Graphics, 2004.
[15] T.-Y. Lee and C.-H. Lin ,”Morphology-based three-dimensional interpolation “, IEEE Trans. of Medical Image, Vol. 21, No. 12, pp. 1479-1489, 2002
[16] C.-H. Lin and T.-Y. Lee, ”Mesh Metamorphosis without a Common Connectivity“, Submitted to ACM Transactions on Graphics, 2004.
[17] M. Ahn and S. Lee, “Mesh metamorphosis with topology transformation”, In Proc. of Pacific Graphics, Beijing, China, IEEE Computer Society, pp. 481-482, 2002.
[18] G. Wolberg, ”Digital Image Warping”, Computer Society Press, 1990.
[19] T. Beier and S. Neely, “Feature-based image metamorphosis’’, In ACM SIGGRAPH Conference Proceedings, Vol. 26, pp. 35-42, 1992.
[20] N. Arad, N. Dyn, D. Reisfeld and Y. Yeshurun, “Image Warping by Radial Basis Functions: Application to Facial Expressions”, CVGIP: Graphical Models and Image Processing, Vol. 56, No. 2, pp. 161-172, March 1994.
[21] D. Ruprecht and H. Muller, “Image warping with scattered data interpolating”, IEEE Comput Graph Appl, Vol. 15, pp. 37-43, 1995.
[22] S.Y. Lee, K.Y. Chwa, S.Y. Shin and G. Wolberg, “Image Metamorphosis Using Snakes and Free-Form Deformations”, In ACM SIGGRAPH Conference Proceedings, pp. 439-448, 1995.
[23] P. Gao and T. W. Sederberg, “A work minimization approach to image morphing”, The Visual Computer, Vol. 14, pp. 390-400, 1998.
[24] A. Tal and G. Elber, “Image Morphing with Feature Preserving Texture”, Proceedings of EUROGRAPHICS, Vol. 18, No. 3, pp. 339-348, 1999.
[25] A. Lee, D. Dobkin, W. Sweldens and P. Schroder, “Multiresolution Mesh Morphing”, In ACM SIGGRAPH Conference Proceedings, pp. 343-350, 1999.
[26] M. Alexa, D. Cohen-Or and D. Levin, “As-rigid -as-possible shape interpolation,” In ACM SIGGRAPH Conference Proceedings, pp. 157-164, 2000.
[27] S. Lee, G. Wolberg, K.-Y., Chwa and S.-Y. Shin, “Image Metamorphosis with Scattered Feature Constraints”, IEEE Trans. on Visualization and Computer Graphics, Vol. 2, No. 4, pp. 337-354, 1996.
[28] A. Lerious, C. D. Garfinkle and M. Levoy, “Feature-Based Volume Metamorphosis”, In ACM SIGGRAPH Conference Proceedings, pp. 449-456, 1995.
[29] G. Herman and C. Coin, “The Use of 3D Computer Display in the Study of Disk Disease”, Computer Assisted Tomography, Vol. 4, No. 4, pp. 564-567, Aug. 1980.
[30] C. C. Liang, C. T. Chen and W.C. Lin, “Intensity Interpolation for Reconstructing 3-D Medical Images from Serial cross-sections”, IEEE Eng. Med. Bio. Soc. 10th Int. Conf. (New Orleans, LA), CH2566-8, pp. 1389-1390, Nov. 1988.
[31] C. C. Liang, C. T. Chen and W. C. Lin, “Intensity Interpolation for Branching in Reconstructing Three-dimensional Objects from Serial cross-sections”, SPIE Conf. Medical Imaging V: Image Processing (San Jose, CA, Feb.-March 1991), vol. 1445.
[32] G. J. Grevera and J. K. Udupa, “Shape-based Interpolation of Multidimensional Grey-level Images”, IEEE Trans. on Medical Imaging, Vol. 15, No. 6, pp. 881-892, 1996.
[33] R.G. Keys, “Cubic Convolution Interpolation for Digital Image Processing”, IEEE Trans. Acoust., Speech, Signal Processing, Vol. ASSP-29 pp. 1153-1160, Dec. 1981.
[34] W.-C. Lin, C.-C. Liang and C.-T. Chen, “Dynamic Elastic Interpolation for 3-D Medical Image Reconstruction from Cross Sections”, IEEE Trans. on Medical Imaging, Vol. 7, No. 3, pp.225-232, Sept. 1988.
[35] S.-Y. Chen, W.-C. Lin, “Automated Surface Interpolation Technique for 3-D Object Reconstruction From Serial Cross Sections”, Computerized Medical Imaging and Graphics, Vol. 15, No. 4, pp. 265-276, 1991.
[36] S. P. Raya and J. K. Udupa, “Shape-based Interpolation of Multi-dimensional Objects”, IEEE Trans. on Medical Imaging, Vol. 9, No. 1, pp. 32-42, March 1990.
[37] G. T. Herman, J. Zheng and C. A. Bucholtz, “Shaped-based Interpolation”, IEEE Computer Graphics & Applications, pp. 69-79, May 1992.
[38] J.-F. Guo, Y.-L. Cai and Y.-P. Wang, “Morphology-based Interpolation For 3D Medical Image Reconstruction”, Computerized Medical Imaging and Graphics, Vol. 19, No.3, pp.267-279, 1995.
[39] Y.-H. Liu, Y.-N. Sun, C.-W. Mao and C.-J. Lin, “Edge-Shrinking Interpolation for Medical Images”, Computer Vision, Graphics and Image Processing, Vol. 21, No. 2, 1997, pp.91-101, 1997.
[40] T.-Y. Lee and W.-H. Wang, “Morphology-based Three-dimensional Interpolation“, IEEE Transactions on Medical Imaging, Vol. 19, No. 7, pp. 711-721, 2000.
[41] A. Goshtasby, D. A. Tuner and L. V. Ackerman, “Matching Tomographic Slices for Interpolation“, IEEE Trans. on Medical Imaging, Vol. 11, pp. 507-516, 1992.
[42] D. T. Puff, D. Eberly and S. M. Pizer, “Object-based Interpolation via Cores,” in Proc. SPIE: Med. Img. 94, Image Process, Vol. 2167, pp. 143-150, 1994.
[43] B.S. Morse, S. M. Pizer and D. S. Fritsch, ”Robust Object representation Through Object-relevant Use of Scale”, In Proc. SPIE: Med. Imag. , Vol. 2167, pp. 104-115, 1994.
[44] V. Chatzis and I. Pitas, “Interpolation of 3-D Binary Images Based on Morphological Skeletonization”, IEEE Trans. on Medical Imaging, Vol. 19, No. 7, pp. 699-710, July 2000.
[45] Cohen-Or, Daniel, D. Levin and A. Solomovici, “Three-dimensional Distance Field Morphing“, ACM Transactions on Graphics, Vol. 17, No. 2, 1998.
[46] I. Kompatsiaris, D. Tzovaras, V. Koutkias and M. G. Strintzis, ”Deformable boundary detection of stents in angiographic images”, IEEE Trans. on Medical Imaging, Vol. 19, pp. 652-661, 2000.
[47] M. Salotti, “An efficient algorithm for the optimal polygonal approximation of digitized curves”, Pattern Recognition Letters, Vol. 22, pp 215-221, 2001.
[48] M. D. Carmo, “Differential Geometry of Curves and Surfaces”, Prentice-Hall, NJ, 1976.
[49] S. Cohen, G. Elber and R. Bar Yehuda, “Matching of freeform curves”, Computer-Aided Design, Vol. 29, No. 5, pp 369-378,1997.
[50] H. Hoppe, T. DeRose, T. Dunchamp, J. McDonald, and Werner Stuetzle, "Mesh Optimization", In ACM SIGGRAPH Conference Proceedings, pp. 19-25, 1993.
[51] H. Hoppe, T. DeRose, T. Dunchamp, J. McDonald and W. Stuetzle, “Mesh optimization. Technical Report”, TR 93-01-01, University of Washington, 1993.
[52] Jonathan Richard Shewchuk, “Updating and constructing constrained delaunay and constrained regular triangulations by flips”, Symposium on Computational Geometry, pp. 181-190, 2003.
[53] R. Seidel, “A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and Triangulating Polygons,” Computational Geometry: Theory and Applications, pp. 51-64, 1991.
[54] S. Hanke, Th. Ottmann and S. Schuierer, “The Edge-flipping Distance of Triangulations”, J. Universal Computer Science, Vol. 2, No.8, pp. 570-579, Aug 1996.
[55] C. Gotsman, X. Gu and A. Sheffer, “Fundamentals of Spherical Parameterization for 3D Meshes”, In ACM SIGGRAPH Conference Proceedings, pp. 358 – 363, 2003
[56] K. Fujimura and M. M. Makarov, “Foldover-free image warping”, Graphical models and image processing: GMIP, Vol. 60, No.2, pp.100-111, 1998.
[57] H. Hoppe, “Progressive Meshes”, In ACM SIGGRAPH Conference Proceedings, pp. 99-108. 1996.
[58] M. S. Floater, “Parameterization and Smooth Approximation of Surface Triangulations”, Computer Aided Geometric Design, Vol. 14, pp. 231-250, 1997.