臺灣博碩士論文加值系統

隨著網際網路的爆炸性成長及各種數位內容處理技術的發展，許多有價值的數位化資料得以透過網際網路分發傳送。各種形式的數位化資訊可以使用數位浮水印或是資訊隱藏等資料嵌入技術防止被惡意盜用、修改或複製。目前資料嵌入技術的開發及研究大多以影像為主，其他形式的數位媒體則較少相關研究。然而近年來三維模型逐漸廣泛地被應用在各種場合，因此也需要發展三維模型相關的資料嵌入技術，本論文即提出針對三維模型資訊隱藏的技術。
大多數針對三維模型之高容量資訊隱藏技術會對原始模型外形造成無法回復的形變。然而對於藝術模型或科技用的精確模型而言，不改變原始模型往往非常重要。本論文提出兩個針對三維模型之可逆式資訊隱藏演算法，不但資訊隱藏量高，而且於隱藏資料取出後，可以完全恢復原始模型外觀。第一個演算法是在空間域 (spatial domain) 中藏入資訊，為可多層次隱藏資訊之可逆式三維模型高容量資訊隱藏技術；第二個演算法是在資料表示域中 (representation domain) 藏入秘密資訊，即利用改變原始模型檔案中點與面的排列順序來隱藏資訊。
第一個演算法首先由原始遮蔽模型(cover media)中任意找出一組不相依的點集合(independent set of vertices) 來隱藏資訊，根據此集合中點的鄰點座標計算出此點座標的預測誤差 (prediction residue)，接著將這些預測誤差及秘密資訊用算術編碼法 (arithmetic coding) 分別壓縮並紀錄。隱藏資訊的步驟是先將壓縮後的預測誤差取代原有點座標較不重要部分的數個位元，接著用相同的取代法藏入壓縮後的秘密資訊。因為資訊壓縮的關係，會有多餘的空間得以用來隱藏秘密資訊。在使用者由隱藏模型擷取出算術編碼法的壓縮資訊後，可依算術解碼法解出秘密資訊及預測誤差，再依預測誤差重建原始模型。實驗結果顯示我們所提的方法具有高隱藏容量且可以成功地完全重建原始模型。
第二個演算法是利用改變原始模型檔案中點與面的排列順序來隱藏資訊。點與面重排後的順序即表示被藏入的資料，由於點座標內容不變且模型的三角網格也未曾改變，因此嵌入秘密資訊後的模型與原始模型外表形狀完全相同，不會有任何形變。我們所提的方法能抵抗縮放、平移及旋轉等變換；演算法中並且加入了強化安全機制以防止惡意攻擊。實驗結果顯示我們所提的方法是一種高容量的資訊隱藏術，而且不會對原始模型造成任何形變。
我們所提出的兩個3D模型資訊隱藏方法是將秘密資訊分別隱藏在空間域及資料表示域中。由於在空間域中藏入資訊會使得模型產生形變，因此我們藉由控制模型之點座標的最大改變量來達到模型隱藏資訊的不可察覺性；此外為了重建原始模型，可逆式資訊隱藏演算法必須隱藏大量額外的資訊，本文所提出的第一個方法仍達到每個所選出的點可隱藏4~8位元的容量。爲了在隱藏量與形變之間取得良好的平衡，未來考慮使用可調整之最大形變控制機制，甚至使用更有效率的方式去計算被用來嵌入資料的預測座標。另外我們在資料表示域中隱藏資料是藉由將模型之點與面的順序重排，模型外觀不會有任何改變，對一個具有 n 個頂點的三維模型，我們所提出的方法可高達將近 3lgn 位元/頂點 (bits per vertex, bpv) 的資訊隱藏量，每一點所能隱藏的資訊容量將隨著模型之點與面的數量增加而增加。在目前3D模型偽裝術中，此方法之隱藏容量是最高的。
未來的研究工作包括研發嵌入資訊後不會引起惡意使用者注意而加以攻擊的演算法，以及開發適用於所有三維模型的資訊隱藏方法。此外，三維模型還有許多其他有趣的研究主題，我們也將擴大我們的研究領域至三維模型的紋理貼圖、壓縮、傳輸、視覺、骨架、形變、動畫等議題。

With explosive growth of the Internet and the development of digital content processing techniques, many valuable digitized materials are distributed and transmitted via the Internet. Various digital media can be embedded data for protecting digital materials from being accessed, duplicated, and modified. Most data-embedding techniques are applied to images. Work on other media is lacking. Recently, 3D models have become more accessible to most end-users in various applications. Thus, 3D models are suitable to serve as host media for various data-embedding purposes.
Most high-capacity, 3D data-hiding schemes introduce irreversible changes into the host models. For artistic or technical models, not modifying the original mesh models is sometimes very important. This dissertation describes two data-hiding schemes to solve this problem for 3D mesh models. The first one is a multi-layer reversible data-hiding scheme in the spatial domain such that the original model can be recovered after the retrieving of the hidden data. The second scheme hides data in the representation domain of 3D models. The vertex and face rearrangement procedures will not cause any distortion on the host model; thus the stego model is identical to the original one.
The first scheme starts with finding an independent set of vertices for embedding data. The prediction residues of the vertices of the independent set and the secret bit string are then encoded using the arithmetic coding method. The embedding procedure is done by substituting part of the mantissa of these vertices with the coded arithmetic decimal numbers. A maximum distortion constraint is set for each embedding vertex, such that the distortion on the cover model is controlled to be imperceptible. Users can construct a multi-layer embedding scheme by repeatedly applying the single-layer embedding procedure until the secret bit string is completely embedded. Experimental results show that the proposed scheme can successfully reconstruct the original model while extracting the secret bit string.
The second scheme embeds messages in triangle meshes by rearranging the vertex and face representation information in the mesh file. The main advantage of embedding messages in the representation domain is that the visual effect of the embedded models is identical to that of the original ones. After rearrangement, the secret messages are embedded in the new indices of vertices and faces of the cover model. The face rearrangement embedding scheme is integrated with a face formation type rearrangement scheme to increase the embedding capacity. The proposed method is robust against transformations such as translation, rotation and uniform resizing. Finally, a security enhancement algorithm is proposed to prevent malicious attackers retrieving the embedded information using a brute force method. Experimental results show that the proposed method is a high-capacity data-hiding approach with no distortion.
In short, this dissertation presents two data-hiding schemes for 3D mesh models. In the spatial domain, the proposed method achieves 4~8 bits/vertex embedding capacity while reserving the ability of rebuilding the original model. Currently, we consider an adaptive maximum distortion control mechanism for a good balance between capacity and distortion. Moreover, we try to develop a more effective way to predict the coordinates of the embedded vertices. In the representation domain, the proposed method can yield an embedding capacity of approximately 3lgn bits/vertex, where n presents the number of vertices. The bit-per-vertex (bpv) embedding capacity increases with the size of the mesh. The embedding capacity is the highest compared to that of other up-to-date 3D embedding schemes.
Future work includes constructing an embedding method which does not attract the attention of malicious users and is applicable to all model types. Many other issues of 3D data processing are also interesting and worth studying. In the future, we will extend our study in the fields of 3D texture mapping, compression, transmission, visualization, skeleton, deformation, animation, etc.

中文摘要 i
Abstract iv
誌謝 vii
List of Figures x
List of Tables xii
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Overview of this study 5
1.3 Organization of the dissertation 6
Chapter 2 The related works 7
2.1 Watermarking for 3D models 7
2.1.1 3D robust watermarking 7
2.1.2 3D fragile watermarking 9
2.2 Data hiding for 3D models 10
2.2.1 Hiding data in spatial domain 11
2.2.2 Hiding data in representation domain 11
Chapter 3 Multi-layer reversible data-hiding scheme 13
3.1 Overview of the proposed scheme 13
3.2 Determining an independent set of vertices for embedding 16
3.3 Prediction residue calculation 17
3.4 Arithmetic encoding and processing 19
3.5 Mantissa substitution 20
3.6 Decoding and reversibility 21
3.7 Multi-layer embedding 23
3.8 Experiments and discussions 24
Chapter 4 Data hiding in representation domain 39
4.1 Overview of the proposed scheme 39
4.2 Embedding messages by vertex rearrangement 41
4.3 Embedding messages by face rearrangement 47
4.4 Extracting hidden data 52
4.5 Enhancing security 56
4.6 Analyzing embedding capacity 57
4.7 Experiments and discussions 60
Chapter 5 Conclusions and future works 69
Bibliography 74

[1]W.-L. Tai and C.-C. Chang, “Data hiding based on VQ compressed images using hamming codes and declustering,” International Journal of Innovative Computing, Information and Control, Vol.5, No.7, pp.2043-2052, 2009.
[2]C.-C. Chang, T.-D. Kieu, and Y.-C. Chou, “Reversible information hiding for VQ indices based on locally adaptive coding,” Journal of Visual Communication and Image Representation, Vol. 20, Issue 1, pp.57-64, 2009.
[3]Q. Gu and T. Gao, “A novel reversible watermarking algorithm based on wavelet lifting scheme,” ICIC Express Letters, Vol.3, No.3 (A), pp.397-402, 2009.
[4]C.-C. Chang, C.-C. Lin, and Y.-H. Chen, “Reversible data-embedding scheme using differences between original and predicted pixel values,” IET Information Security, Vol. 2, Issue 2, pp.35-46, 2008.
[5]C.-C. Chang, Y.-H. Chen, and D. Kieu, “A watermarking technique using synonym substitution for integrity protection of XML documents,” ICIC Express Letters, Vol.4, No.1, pp.89-94, 2010.
[6]M. Chow, “Optimized geometry compression for real-time rendering,” in Proc. IEEE Visualization, Phoenix, AZ, Oct. 19-24, pp.347-354, 1997.
[7]M. Deering, “Geometry compression,” in ACM SIGGRAPH, Los Angeles, CA, Aug. 6-11, pp.13-20, 1995.
[8]F. Evans, S. S. Skiena, and A. Varshney, “Optimizing triangle strips for fast rendering,” in Proc. IEEE Visualization, Hyatt Regency, San Francisco, CA, Oct. 28-29, pp.319-326, 1996.
[9]R. Ohbuchi, H. Masuda, and M. Aono, “Watermarking three-dimensional polygonal models through geometric and topological modifications,” IEEE Journal on Selected Areas in Communication, Vol. 16, No. 4, pp. 551-560, 1998.
[10]R. Ohbuchi, A. Mukaiyama, and S. Takahashi, “A frequency-domain approach to watermarking 3D shapes,” Computer Graphics Forum, Vol. 21, No. 3, pp. 373-382, 2002.
[11]O. Benedens, “Geometry-based watermarking of 3-D models,” IEEE Computer Graphics and Applications, Vol. 19, No. 1, pp.46-55, 1999.
[12]O. Benedens and C. Busch, “Towards blind detection of robust watermarks in polygonal models,” Computer Graphics Forum, Vol. 19, No. 3, pp. 199-208, 2000.
[13]E. Praun, H. Hoppe, and A. Finkelstein, “Robust mesh watermarking,” in Proc. ACM SIGGRAPH, Los Angeles, CA, Aug. 8-13, pp. 49-56, 1999.
[14]H. Hoppe, “Progressive meshes,” in Proc. ACM SIGGRAPH, New Orleans, LA, Aug. 4-9, pp. 99-108, 1996.
[15] S. Zafeiriou, A. Tefas, and I. Pitas, “Blind robust watermarking schemes for copyright protection of 3D mesh objects,” IEEE Trans. Visualization and Computer Graphics, Vol. 11, Issue 5, pp. 596-607, 2005.
[16]D. Chou, C.-Y. Jhou, and S.-C. Chu, “Reversible watermark for 3D vertices based on data hiding in mesh formation,” International Journal of Innovative Computing, Information and Control, Vol.5, No.7, pp.1893-1902, 2009.
[17]B.-L. Yeo and M.-M. Yeung, “Watermarking 3D objects for verification,” IEEE Computer Graphics and Applications, Vol. 19, No. 1, pp.36-45, 1999.
[18]H.-Y. Lin, H.-Y. Liao, C.-S. Lu, and J.-C. Lin, “Fragile watermarking for authenticating 3-D polygonal meshes,” IEEE Trans. Multimedia, Vol. 7, No. 6, pp. 997-1006, 2005.
[19]C.-M. Chou and D.-C. Tseng, “A public fragile watermarking scheme for 3D model authentication,” Computer-Aided Design, Vol. 38, No. 11, pp.1154-1165, 2006.
[20]C.-M. Chou and D.-C. Tseng, “Affine-transformation-invariant public fragile watermarking for 3D model authentication,” IEEE Computer Graphics and Applications, Vol. 29, Issue 2, pp.72-79, 2009.
[21]J. Dittmann and O. Benedens, “Invertible authentication for 3D meshes,” in Proce. SPIE - The International Society for Optical Engineering, Santa Clara, CA, USA, Jan. 21, Vol. 5020, pp.653-664, 2003.
[22]H.-T. Wu and Y.-M. Cheung, “A reversible data hiding approach to mesh authentication,” in Proceedings of IEEE/WIC/ACM International Conf. on Web Intelligence, Sep. 19-22, Compiegne, France, pp.774-777, 2005.
[23]Z.-M. Lu and Z. Li, “High capacity reversible data hiding for 3D meshes in the PVQ domain,” LNCS, Vol. 5041, pp.233-243, 2008.
[24]H.-T. Wu and J.-L. Dugelay, “Reversible watermarking of 3D mesh models by prediction-error expansion,” in IEEE 10th Workshop on Multimedia Signal Processing, Shangri-la Hotel, Cairns, Queensland, Australia, Oct. 8-10, pp.797-802, 2008.
[25]F. Cayre and B. Macq, “Data hiding on 3-D triangle meshes,” IEEE Trans. Signal Processing, Vol. 51, No. 4, pp. 939-949, 2003.
[26]C.-M. Wang and Y.-M. Cheng, “An efficient information hiding algorithm for polygon models,” Computer Graph. Forum, Vol. 24, No. 3, pp.591-600, 2005.
[27]Y.-M. Cheng and C.-M. Wang, “An adaptive steganographic algorithm for 3D polygonal meshes,” Visual Computer, Vol. 23, pp.721-732, 2007.
[28]M.-W. Chao, C.-H. Lin, C.-W. Yu, and T.-Y. Lee, “A high capacity 3D steganography algorithm,” IEEE Trans. Visualization and Computer Graphics, Vol. 15, No. 2, pp. 274-284, 2009.
[29]Y.-M. Cheng and C.-M. Wang, “A high-capacity steganographic approach for 3D polygonal meshes,” Visual Computer, Vol. 22, No. 9, pp. 845–855, 2006.
[30]C. I. Tan, C.-K. Lin, W.-K. Tai, and C.-C. Chang, “Hiding data: a high-capacity distortionless approach,” Multimedia Systems, Vol. 15, No 6, pp. 325-336, 2009.
[31]J. Peng, C.-S. Kim, and C.-C. J. Kuo, “Technologies for 3D mesh compression: a survey,” Journal of Visual Communication and Image Representation, Vol. 16, No.6, pp.688-733, 2005.