臺灣博碩士論文加值系統

現今的資訊隱藏技術(information hiding techniques)已逐漸採用三維模型(three-dimensional models)來當作掩護媒體(cover media)，但相關的文獻與技術上方面皆有改進的空間。首先，在文獻部分，現今大多數的內容還是以探討浮水印演算法(watermarking algorithms)為主，只有若干篇的研究著重在秘密通訊(covert communication)的資訊偽裝演算法(steganographic algorithms)上。其次，在效率方面，目前的資訊偽裝演算法，在嵌入或擷取過程中，使用了一些複雜的運算或是資料結構，皆使得執行時間變長。另外，低資訊隱藏量仍是目前資訊偽裝演算法之瓶頸，亦是技術上有待突破的部分。
在本篇論文中，我們提出了兩個資訊偽裝演算法來解決上述的缺失。其一，為利用空間切割(spatial subdivision)的概念來達到資訊偽裝的目的。我們將它實作在三維模型與彩色影像上，此方法係利用二元空間分割樹(binary space partitioning tree)，先將掩護媒體細分成許多的小子空間，稱之為「立體像素」(voxels)。在嵌入過程中，先在樹狀結構中尋找葉結點(leaf nodes)，然後藉由改變節點中頂點的位置來藏入秘密訊息。此方法既簡單、有效率，又能在低失真程度(imperceptible distortion)下達到高隱藏量。
其二，我們利用秘密訊息以及私密金鑰來控制參數函數(parametric functions)中變數(variables)的分佈情況。我們將此方法稱為「機密取樣」(embedding sampling)。這個方法有四個優點：首先，以往演算法的隱藏容量，與掩護模型的複雜度有關，而此方法的隱藏容量，則主要跟使用者欲取樣的數目成正比關係，使用我們的方法，能讓隱藏容量大為提升。其次，承載資料的模型非常有彈性，可以是一條線、一片三角形，或是一個參數曲面(parametric surfaces)。再者，執行時間非常的快，若以一個三角片的參數函數為例，只需兩秒鐘即可產生出藏有兩百萬位元秘密資訊的偽裝模型。最後，我們的方法能夠產生出平滑表面的偽裝模型，優於以往演算法都會產生出帶有粗糙表面(rough surfaces)的模型。
總結本篇論文，根據實驗結果顯示，我們所提出的兩個演算法都有下列的優點：有效率、高容量以及低失真程度。這樣的結果，足以證實我們所提出的演算法，已符合一個好的資訊偽裝系統之要求。

Nowadays, the use of three-dimensional models in information hiding techniques is gradually attracting more and more attention. Watermarking algorithms, which mainly protect copyright ownership, are still in the majority. For steganographic algorithms, which are mainly techniques of covert communication, only a few papers have been presented, and there is still much room for development. In terms of efficiency, current steganographic algorithms use complicated operations or data structures during the embedding and extracting algorithms. This may greatly increase processing time. Besides, smaller capacity for 3D models remains bottlenecked.
In this thesis, we propose two steganographic algorithms to overcome the above drawbacks. The first algorithm employs the concept of spatial subdivision to achieve the purpose of steganography. This technique applied to both 3D models and color images. Specifically, we decompose the bounding volume of the cover media into voxels based on a Binary Space Partitioning (BSP) tree data structure. In the embedding process, the tree data structure is traversed in search of leaf nodes, where a payload can be embedded by changing the positions of points. This scheme is simple and efficient, and it can achieve high data capacity with imperceptible distortion.
For the second steganographic algorithm, we use a secret payload and secret keys to control the distribution of variables in the parametric functions. We call this technique “embedding sampling.” This scheme has four advantages. First, the data capacity is proportional to the number of sample points, while previous algorithms have been dependent on input model complexity. Secondly, the input model is flexible. Third, it is very fast. For a triangle, for example, it takes less than two seconds to embed a payload of two million bits. The final advantage is shape preservation; the generated sample points are located on the surface of the three-dimensional geometry.
Experimental results show that both of these schemes are efficient and have high capacity and imperceptible distortion. They also demonstrate that our proposed algorithms meet the requirements of a good steganographic system.

致謝 i
中文摘要 ii
Abstract iv
List of Figures ix
List of Tables xii
Chapter 1 Introduction 1
1.1 Overview of Our Proposed Techniques 3
1.2 Thesis Organization 5
Chapter 2 Background Knowledge for Information Hiding Techniques 6
2.1 Watermarking and Steganographic Algorithms 6
2.2 Spatial Domain and Transform Domain 8
2.3 Blind, Semi-blind, and Non-blind Techniques 9
2.4 Three-dimensional Objects Representation 9
2.4.1 Constructive Solid Geometry (CSG) Representation 9
2.4.2 Polygonal Model Representation 10
2.4.3 Point-based Geometry Representation 11
2.4.4 Parametric Surface Representation 12
Chapter 3 Steganography on 3D Models Using a Spatial Subdivision Technique 14
3.1 Related Work 14
3.2 The BSP Tree Construction 16
3.2.1 An Overview of the BSP Tree Construction 17
3.2.2 The Bounding Volume Construction 19
3.2.3 Processes for the BSP Tree Construction 21
3.3 The Proposed Technique 22
3.3.1 The Embedding Data Process (EMDP) 23
3.3.2 The Extracting Data Process (EXDP) 25
3.4 Implementation Issues 26
3.5 Experimental Results 28
3.6 Summary 36
Chapter 4 Extending the Spatial Subdivision Technique to Color Images 37
4.1 Related Work 37
4.2 The Proposed Technique 38
4.2.1 The Bounding Volume Decision and BSP Tree Construction 40
4.2.2 The Embedding Data Process (EMDP) 40
4.2.3 The Extracting Data Process (EXDP) 42
4.3 Implementation Issues 43
4.4 Experimental Results and Robustness Assessment 45
4.4.1 Experimental Results 45
4.4.2 Robustness Assessment 52
4.5 Summary 55
Chapter 5 Steganography on Parametric Functions 57
5.1 Related Work 59
5.2 Algorithm Description 60
5.2.1 The Data Embedding Algorithm 61
5.2.2 The Data Extracting Algorithm 65
5.3 Experimental Results 67
5.4 Discussion 69
5.5 Summary 72
Chapter 6 Conclusions and Future Work 73
References 76
Index 85

[Asho2004]M. Ashourian, R. Enteshari, and J. Jeon, “Digital Watermarking of Three-Dimensional Polygonal Models in the Spherical Coordinate System,” Proceedings of Computer Graphics International, pp. 590-593, 2004.
[Aspe2002]N. Aspert, E. Drelie, Y. Maret, and T. Ebrahimi, “Steganography for Three-Dimensional Polygonal Meshes,” Proceedings of SPIE 47th Annual Meeting, pp. 705-708, 2002.
[Bend1996]W. Bender, D. Gruhl, N. Morimoto, and A. Lu, “Techniques for Data Hiding,” IBM System Journal, Vol. 35, No. 3&4, pp. 313-336, 1996.
[Bene1999a]O. Benedens, “Geometry-Based Watermarking of 3D Models,” IEEE Computer Graphics and Applications, Vol. 19, No. 1, pp. 46-55, 1999.
[Bene1999b]O. Benedens, “Watermarking of 3D Polygon Based Models with Robustness against Mesh Simplification,” Proceedings of SPIE: Security and Watermarking of Multimedia Contents, pp. 329-340, 1999.
[Bene2000]O. Benedens and C. Busch, “Towards Blind Detection of Robust Watermarks in Polygonal Models,” Computer Graphics Forum (Proceedings of Eurographics 2000), Vol. 19, No. 3, pp. 199-208, 2000.
[Bors2004]A. G. Bors, “Blind Watermarking of 3D Shapes Using Localized Constraints,” Proceedings of the International Symposium on 3D Data Processing, Visualization, and Transmission, pp. 242-249, 2004.
[Bors2006]A. G. Bors, “Watermarking Mesh-Based Representations of 3-D Objects Using Local Moments,” IEEE Transactions on Image Processing, Vol. 15, No. 3, pp. 687-701, 2006.
[Cayr2003]F. Cayre and B. Macq, “Data Hiding on 3-D Triangle Meshes,” IEEE Transactions on Signal Processing, Vol. 51, No. 4, pp. 939-949, 2003.
[Chan2004]C.-K. Chan and L.-M. Cheng, “Hiding Data in Images by Simple LSB Substitution,” Pattern Recognition, Vol. 37, No. 3, pp. 469-474, 2004.
[Chang2004a]C.-C. Chang, J.-C. Chuang, and Y.-P. Lai, “Hiding Data in Multitone Images for Data Communications,” IEE Proceedings-Vision, Images, and Signal Processing, Vol. 151, No. 2, pp. 137-145, 2004.
[Chang2004b]C.-C. Chang and H.-W. Tseng, “A Steganographic Method for Digital Images Using Side Match,” Pattern Recognition Letters, Vol. 25, No. 12, pp. 1431-1437, 2004.
[Cign1998]P. Cignoni, C. Rocchini, and R. Scopigno, “Metro: Measuring Error on Simplified Surfaces,” Computer Graphics Forum, Vol. 17, No. 2, pp. 167-174, 1998.
[Cott2004]D. Cotting, T. Weyrich, M. Pauly, and M. Gross, “Robust Watermarking of Point-Sampled Geometry,” Proceedings of International Conference on Shape Modeling and Applications, pp. 233-242, 2004.
[Cox1997]J. Cox, J. Kilian, F. T. Leighton, and T. Shamoon, “Secure Spread Spectrum Watermarking for Multimedia,” IEEE Transactions on Image Processing, Vol. 6, No. 12, pp. 1673-1687, 1997.
[Duga1998]R. Dugad, K. Ratakonda, and N. Ahuja, “A New Wavelet-based Scheme for Watermarking Images,” Proceedings of IEEE International Conference on Image Processing, pp. 419-423, 1998.
[Duge2002]J. L. Dugelay, E. Carcia, and C. Mallauran, “Protection of 3-D Object Usage through Texture Watermarking,” Proceedings of 11th European Signal Processing Conference, pp. 35-38, 2002.
[Jin2004]J. Q. Jin, M. Y. Dai, H. J. Bao, and Q. S. Peng, “Watermarking on 3D Mesh Based on Spherical Wavelet Transform,” Journal of Zhejiang University SCIENCE, Vol. 5, No. 3, pp. 251-258, 2004.
[Kali2003]A. Kalivas, A. Tefas, and I. Pitas, “Watermarking of 3D Models Using Principal Component Analysis,” Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 676-679, 2003.
[Kana1998]S. Kanai, H. Date, and T. Kishinami, “Digital Watermarking for 3D Polygons Using Multiresolution Wavelet Decomposition,” Proceedings of the Sixth IFIP WG 5.2 International Workshop on Geometric Modeling: Fundamentals and Applications (GEO-6), pp. 296-307, 1998.
[Karn2000]Z. Karni and C. Gotsman, “Spectral Compression of Mesh Geometry,” Proceedings of SIGGRAPH, pp. 279-286, 2000.
[Katz2000]S. Katzenbeisser and F. A. P. Petitcolas, Information Hiding Techniques for Steganography and Digital Watermarking, Artech House, London, 2000.
[Kim2000]T. H. Kim, J. Lee, and S. Y. Shin, “Robust Motion Watermarking Based on Multiresolution Analysis,” Computer Graphics Forum (Proceedings of Eurographics 2000), Vol. 19, No. 3, pp. 189-198, 2000.
[Kobb2004]L. Kobbelt and M. Botsch, “A Survey of Point-Based Techniques in Computer Graphics,” Computers & Graphics, Vol. 28, No. 6, pp. 801-814, 2004.
[Lee2005]J. W. Lee, S. H. Lee, K. R. Kwon, and K. I. Lee, “Complex EGI Based 3D-Mesh Watermarking,” IEICE Transactions on Fundamentals, Vol. E88-A, No. 6, pp. 1512-1519, 2005.
[Lee2003]S. H. Lee, T. S. Kim, B. J. Kim, S. G. Kwon, K. R. Kwon, and K. I. Lee, “3D Polygonal Meshes Watermarking Using Normal Vector Distributions,” Proceedings of IEEE International Conference on Multimedia and Expo, pp. 105-108, 2003.
[Lee2004]S. K. Lee and Y. S. Ho, “A Fragile Watermarking Scheme for Three-Dimensional Polygonal Models Using Triangle Strips,” IEICE Transactions on Communications, Vol. E87-B, No. 9, pp. 2811-2815, 2004.
[Li2000]X. Li and H. H. Yu, “Transparent and Robust Audio Data Hiding in Subband Domain,” Proceedings of International Conference on Information Technology: Coding and Computing, pp. 74-79, 2000.
[Lie1999]W.-N. Lie and L.-C. Chang, “Data Hiding in Images with Adaptive Number of Least Significant Bits based on the Human Visual System,” Proceedings of IEEE International Conference on Image Processing, Vol. 1, pp. 286-290, 1999.
[Lin2005]H.-Y. S. Lin, H.-Y. M. Liao, C.-S. Lu, and J.-C. Lin, “Fragile Watermarking for Authenticating 3-D Polygonal Meshes,” IEEE Transactions on Multimedia, Vol. 7, No. 6, pp. 997-1006, 2005.
[Mare2004]Y. Maret and T. Ebrahimi, “Data Hiding on 3D Polygonal Meshes,” Proceedings of the 2004 Workshop on Multimedia and Security, pp. 68-74, 2004.
[Muro2003]K. Murotani and K. Sugihara, “Watermarking 3D Polygonal Meshes Using the Singular Spectrum Analysis,” Proceedings of the 10th IMA International Conference on the Mathematics of Surfaces, pp. 85-98, 2003.
[Neha2004]D. Nehab and P. Shilane, “Stratified Point Sampling of 3D Models,” Proceedings of Eurographics Symposium on Point-Based Graphics, pp. 49-56, 2004.
[Ohbu1997]R. Ohbuchi, H. Masuda, and M. Aono, “Watermarking Three-Dimensional Polygonal Models,” Proceedings of ACM Multimedia, pp. 261-272, 1997.
[Ohbu1998a]R. Ohbuchi, H. Masuda, and M. Aono, “Watermarking Three-Dimensional Polygonal Models Through Geometric and Topological Modifications,” IEEE Journal on Selected Areas of Communications, Vol. 16, No. 4, pp. 551-560, 1998.
[Ohbu1998b]R. Ohbuchi, H. Masuda, and M. Aono, “Geometrical and Non-Geometrical Targets for Data Embedding in Three-Dimensional Polygonal Models,” Computer Communications, Vol. 21, No. 15, pp. 1344-1354, 1998.
[Ohbu2001]R. Ohbuchi, S. Takahashi, T. Miyazawa, and A. Mukaiyama, “Watermarking 3D Polygonal Meshes in the Mesh Spectral Domain,” Proceedings of Graphics Interface, pp. 9-17, 2001.
[Ohbu2002]R. Ohbuchi, A. Mukaiyama, and S. Takahashi, “A Frequency-Domain Approach to Watermarking 3D Shapes,” Computer Graphics Forum (Proceedings of Eurographics 2002), Vol. 21, No. 3, pp. 373-382, 2002.
[Ohbu2004]R. Ohbuchi, A. Mukaiyama, and S. Takahashi, “Watermarking a 3D Shape Model Defined as a Point Set,” Proceedings of International Conference on Cyberworlds, pp. 392-399, 2004.
[Peti1999]F. A. P. Petitcolas, R. J. Anderson, and M. G. Kuhn, “Information Hiding - A Survey,” Proceedings of IEEE, Special Issue on Protection of Multimedia Content, Vol. 87, No. 7, pp. 1062-1078, 1999
[Pfit1996]B. Pfitzmann, “Information Hiding Terminology,” Proceedings of First International Workshop on Information Hiding, pp. 347-350, 1996.
[Prau1999]E. Praun, H. Hoppe, and A. Finkelstein, “Robust Mesh Watermarking,” Proceedings of SIGGRAPH, pp. 49-56, 1999.
[Renc2002]A. C. Rencher, Methods of Multivariate Analysis, Second Edition, Wiley, New York, 2002.
[Rubi1981]R. Y. Rubinstein, Simulation and the Monte Carlo Method, John Wiley & Sons, New York, 1981.
[Shir1996]P. Shirley, C. Wang, K. Zimmerman, “Monte Carlo Techniques for Direct Lighting Calculation,” ACM Transactions on Graphics, Vol. 15, No. 1, pp. 1-36, 1996.
[Shre1966]Y. A. Shreider, The Monte Carlo Method, Pergamon Press, New York, 1966.
[Sola2004]V. Solachidis and I. Pitas, “Watermarking Polygonal Lines Using Fourier Descriptors,” IEEE Computer Graphics and Applications, Vol. 24, No. 3, pp. 44-51, 2004.
[Song2002]H. S. Song, N. I. Cho, and J. W. Kim, “Robust Watermarking of 3D Mesh Models,” Proceedings of IEEE International Workshop on Multimedia Signal Processing, pp. 332-335, 2002.
[Sonn2003]H. Sonnet, T. Isenberg, J. Dittmann, and T. Strothotte, “Illustration Watermarks for Vector Graphics,” Proceedings of the 11th Pacific Conference on Computer Graphics and Applications, pp. 73-82, 2003.
[Swan1997]M. D. Swanson, B. Zhu, and A. H. Tewfik, “Data Hiding for Video-in-Video”, Proceedings of International Conference on Image Processing, Vol. 2, pp. 676-679, 1997.
[Turk1990]G. Turk, “Generating Random Points in Triangles,” Graphics Gems, Academic Press, New York, pp. 24-28, 1990.
[Ucch2004]F. Uccheddu, M. Corsini, and M. Barni, “Wavelet-Based Blind Watermarking of 3D Models,” Proceedings of the 2004 Workshop on Multimedia and Security, pp. 143-154, 2004.
[Wagn2000]M. G. Wagner, “Robust Watermarking of Polygonal Meshes,” Proceedings of Geometric Modeling & Processing, pp. 201-208, 2000.
[Wang1993]C. Wang, The Direct Lighting Computation in Global Illumination Methods, Ph.D. Thesis, University of Indiana, USA, 1993.
[Wang2004a]C.-M. Wang, N.-C. Hwang, Y.-Y. Tsai and C.-H. Chang, “Ellipse Sampling for Monte Carlo Applications,” Electronics Letters, Vol. 40, No. 1, pp. 21-22, 2004.
[Wang2004b]C.-M. Wang and P.-C. Wang, “A Novel Approach to Sampling the Coiled Tubing Surface with an Application for Monte Carlo Direct Lighting,” IEICE Transactions on Information and Systems, Vol. E87-D, No. 6, pp. 1545-1553, 2004.
[Wang2005a]C.-M. Wang and P.-C. Wang, “Data Hiding Approach for Point-Sampled Geometry,” IEICE Transactions on Communications, Vol. E88-B, No. 1, pp. 190-194, 2005.
[Wang2005b]C.-M. Wang and Y.-M. Cheng, “An Efficient Information Hiding Algorithm for Polygon Models,” Computer Graphics Forum (Proceedings of Eurographics 2005), Vol. 24, No. 3, pp. 591-600, 2005.
[Wang2006]C.-M. Wang and P.-C. Wang, “Steganography on Point-sampled Geometry,” Computers & Graphics, Vol. 30, No. 2, pp. 244-254, 2006.
[Wang2001]R.-Z. Wang, C.-F. Lin, and J.-C. Lin, “Image Hiding by Optimal LSB Substitution and Genetic Algorithm,” Pattern Recognition, Vol. 34, pp. 671-683, 2001.
[Wu2003]D.-C. Wu and W.-H. Tsai, “A Steganographic Method for Images by Pixel-values Differencing,” Pattern Recognition Letters, Vol. 24, pp. 1613-1626, 2003.
[WuH2005]H. T. Wu and Y. M. Cheung, “A Fragile Watermarking Scheme for 3D Meshes,” Proceedings of the 7th ACM Workshop on Multimedia and Security, pp. 117-123, 2005.
[WuJ2005]J. Wu and L. Kobbelt, “Efficient Spectral Watermarking of Large Meshes with Orthogonal Basis Functions,” Proceedings of the 13th Pacific Conference on Computer Graphics and Applications, pp. 848-857, 2005.
[Yin2001]K. Yin, Z. Pan, J. Shi, and D. Zhang, “Robust Mesh Watermarking Based on Multiresolution Processing,” Computers & Graphics, Vol. 25, No. 3, pp. 409-420, 2001.
[Yu2003]Z. Yu, H. S. Horace, and L. F. Kowk, “Robust Watermarking of 3D Polygonal Models Based on Vertice Scrambling,” Proceedings of Computer Graphics International, pp. 254-257, 2003.
[Zafe2005]S. Zafeiriou, A. Tefas, and I. Pitas, “Blind Robust Watermarking Schemes for Copyright Protection of 3D Mesh Objects,” IEEE Transactions on Visualization and Computer Graphics, Vol. 11, No. 5, pp. 596-607, 2005.
[Zhan2002]L. Zhang, R. Tong, F. Su, and J. Dong, “A Mesh Watermarking Approach for Appearance Attributes,” Proceedings of the 10th Pacific Conference on Computer Graphics and Applications, pp. 450-451, 2002.