臺灣博碩士論文加值系統

將影像變形(image morphing ) 應用在虛擬實境的建構上，不僅可以彌補照片拍攝的不連續所造成的缺點，而且可以減少建構的成本。儘管如此，若影像變形後的結果有所失真，造成物體形狀的改變。則對建構後的結果會產生格格不入的感覺。因此，本論文所要探討的問題是對兩張彩色圖像中的物體骨架化(skeletonization)後，然後，做影像變形並使得在變形後的物體保持完整的外形以及對人物的骨架做影像變形產生適當的人物動畫。所謂的骨架化指的是將一個二維的物體轉換成一維的線來代表，結果就像是柴枝的外形。就物體的區別而言，可分為人工物件(artifact object)及非人工物件(non-artifact object)兩類，並且分別採用不同的骨架化的方法:人工物件的骨架可由其內部的邊來決定物體的骨架。若無法取出其內部的邊，則可利用內切圓圓心在物體內所連接成的軌跡來決定該物體的骨架; 非人工物件的骨架，則採用Robert L. Ogniewigz所提出的Discrete Voronoi Skeletons的方法來建立物體的骨架。有了骨架的資訊，接著便可以從中取出主要的骨架。然後，利用L. Paul Chew所提的Constrained Delaunay Triangulation 的方法對此主要的骨架建立Constrained Delaunay Triangles。以往的方法在處理圖像合成時，是以像素(pixel)為單位，進行像素對應;而本論文是以三角形為對應單位，分別將兩張圖像中的物體所分割成的三角形兩兩對應，藉此可求出變形後的三角形，然後利用反向映射(inverse mapping)貼圖技術處理像素的對應問題，以Barycentric 座標轉換的方法取得像素的座標，完成三角形的對應。最後，即可得到整個變形後的物體並且保持完整的外形。
合理的影像變形的結果，對於虛擬實境的建立，可以產生如同身歷其境的感覺。我們以實驗結果來驗證本論文所提出方法的優越性。

Building the virtual reality world by the traditional computer graphics methods is a highly time-consuming task. The image-based rendering technology provides an elegant solution. Basically, the required image of arbitrary viewing position and direction is synthesized by morphing two or multiple pre-captured images at some determined camera positions. Applying the image morphing technology does not only reduce the expensive cost of world construction, but also overcome the discontinuity drawback of the pre-captured image sequence. However, if the morphing results fail to preserve the original shape of objects, it will cause a fake construction, especially when the target object is artifact.
In this paper, we propose a new shape-preserving image morphing method. First, the skeleton structures of the pre-captured pictures are extracted. The skeletonization is a process for reducing foreground regions in a digital image to a skeletal remnant that largely preserves the properties of the original region while discarding most of the original foreground pixels. Different skeletonization methods are applied to the artifact objects and non-artifact objects respectively. For artifact objects, the skeleton is determined from the interior lines of the object. For non-artifact objects, we use the Discrete Voronoi skeletons proposed by Robert L. Ogniewigz to build object’s skeleton. These skeleton structures then serve as the constrained Delaunay triangulation method. After the pre-captured images are analyzed, the skeletons and the Delaunay triangulation data structure of the required image are interpolated from the pre-calculated images. Finally, the reasonable result images are synthesized by texture mapping and blending the pictures.

中文摘要
Abstract
1 Introduction …………………………………………………… 1
2 Research Background……………………………………………4
2.1 Image Morphing vs. View Morphing ……………………………4
2.1.1 Image Morphing …………………………………………4
2.1.2 View Morphing ……………………………………………5
2.1.3 Comparing Result ………………………………………7
2.1.4 Common Problems…………………………………………8
2.2 Image Processing ………………………………………………8
2.2.1 Region Boundary …………………………………………8
2.2.2 Edge Detection …………………………………………8
2.3 Voronoi Skeletonization ……………………………………9
2.3.1 Technology of Skeletonization………………………9
2.3.2 The Skeletonization Properties …………………10
2.3.3 Discrete Voronoi Skeleton…………………………10
2.3.3.1 Potential Residual………………………12
2.3.3.2 Circularity Residual……………………12
2.3.3.3 Chord Residual……………………………13
2.3.3.4 The Skeleton Pyramid……………………13
2.4 Constrained Delaunay Triangulation ……………………14
2.4.1 Delaunay Triangulation Definition………………15
2.4.2 Constrained Delaunay Triangulation Definition15
2.4.3 CDT Algorithm…………………………………………17
2.4.4 Control of containing vertex regions …………17
2.4.5 Merge CDT………………………………………………18
3 Algorithm ………………………………………………………22
3.1 System Architecture ……………………………………………22
3.2 relation technology ………………………………………… 23
3.2.1 Interpolation …………………………………………… 23
3.2.2 Barycentric Coordinate………………………………23
3.3 Texture Mapping ……………………………………………… 24
4 System Implementation ……………………………………… 27
5 Conclusion …………………………………………………… 39

[1] Alan Watt, Fabio Policarpo, “The Computer Image”, Addison-Wesley
[2] L. Paul Chew, Constrained Delaunay Triangulation, ACM, 1987
[3] R.L. Ogniewicz, Discrete Voronoi Skeletons, Hartung-Gorre Verlag, Konstanz, Germany, (1993), Revised and extended version of Ph.D. thesis No. 9876, ETH-Zurich, Switzerland.
[4] R. L. Ogniewicz, and O.Kubler, Hierarchic Voronoi Skeletons, Pattern Recognition, Vol. 28, no. 3, pp. 343-359, 1995.
[5] H. Blum, A transformation for extracting new descriptors of shape, in W. Wathen-Dunn, editor, Models for the Perception of Speech and Visual Form, MIT Press, Cambridge MA, (1967)
[6] Williams L. and Chen S. E., View Interpolation for Image Synthesis, Proc. SIGGRAPH 1993, 279-88
[7] Seitz S. M. and Dyer C. R., View Morphing, Proc. SIGGRAPH 1996, 21-30
[8] T. Beier and S. Neely. Feature-based Image Metamorphosis. SIGGRAPH’92 Proceedings, pp. 33-42, 1992
[9] S. Y. Lee, K. Y. Chwa, S. Y. Shin, and G. Wolberg. Image Metamorphosis Using Snakes and Free-Form Deformations. SIGGRAPH’95, pp. 439-448, 1995
[10] G. Wolberg. Image Morphing Survey. The Visual Computer, 14, 8/9, 1998
[11] Hearn, Baker. Computer Graphics, Second edition. Prentice Hall International
[12] J. R. Parker, Algorithms for Image Processing and Computer Vision, Wiley Computer.
[13] I. Pitas, Digital Image Processing Algorithms and Application, Wiley-Interscience
[14] Rafael C. Gonzalez, Richard E. Woods, Digital Image Processing, Addison-Wesley
[15] Chen S. E. (1995). QuickTime VR-An Image based approach to virtual environment navigation. Proc. SIGGRAPH 1995, 29-38
[16] Mark A. Ruzon Carlo Tomasi. Edge, Junction, and Corner Detection Using Color Distributions, IEEE Transactions on pattern analysis and machine intelligence, vol. 23, no. 11, 2001.
[17] Paul S. Heckbert, Pixar, Survey of Texture Mapping, IEEE Computer Graphics and Application, 1986, 56-67
[18] Paul S. Heckbert, Fundamentals of Texture Mapping and Image Warping, thesis, Dept. of Electrical Engineering and Computer Sicence, University of California, Berkley, CA94720
[19] Mark De Berg (Editor), et al,Computational Geometry: Algorithms and Applications, Springer, (Hardcover - May 2000)
[20] R. C. T. Lee, Introduction to the Design and Analysis of Algorithms, second edition, FLAGE publishing company.
[21] Tal A, Elber G. Image Morphing with feature preserving texture. Computer Graphics Forum(Eurographics’99 proceedings) 1999;339-48.
[22] Alexa M, Cohen-Or D, Levin. As-rigid-as-Possible Shape Interpolation, Proceedings of the SIGGRAPH’2000, New Orleans, LA USA.
[23] Graig Gotsman, Vitaly Surazhsky. Shape Blending Guaranteed intersection-free polygon morphing, Computer & Graphics PERGAMON, 25(2001)67-75