臺灣博碩士論文加值系統

近年來，智慧財產的保護是一個極大的挑戰，也因此資訊隱藏相關的技術變得日益重要，取決於不同的需求及目的，本碩士論文針對資訊隱藏的相關主題提出三個不同的方法。在本論文中第一個方法提出以區塊為基礎的驗證浮水印機制，運用於確認二元影像的完整性。當取得一張要保護的二元影像時，首先將影像切割為個別不重複的區塊，接著利用雜湊函數對於區塊取得訊息摘要，並利用 XOR 運算結合浮水印與訊息摘要，最後再將得到的機密值藏入要保護的影像中。當保護後的二元影像遭到如隨機攻擊或偽造攻擊時，本論文所提出的方法可有效地偵測在影像中何處遭到竄改。在資訊隱藏的技術中，一般普遍運用於影像的資料隱藏方法為最低有效位元置換，但這個方法會造成原始影像的失真，以至於可能引起惡意人士的注意。隨後，最佳化的最低有效位元置換因而被提出改善這類的問題，但是這個方法必須花費大量的運算時間。因此，本論文的第二個方法提出一個高效能的演算法以解決這個問題，本方法將最佳化的最低有效位元位置的問題簡化為指派問題，結合匈牙利演算法的運算，進而可利用最少的記憶體及時間找出最佳解。
本論文的第三個方法提出一個高容量及高品質的可逆式資料隱藏技術。主要的概念為利用鄰近像素值相似性的特性將遮蔽的影像利用鄰近的像素分組為不重疊的群組。接著計算每各個群組之差值得到完整差值表，並加總每個誤差值的次數以建立一個差值長條圖，最後利用長條圖的位移來藏入資訊。由實驗的結果證明本論文所提出的方法之隱藏量及遮蔽影像的品質均明顯地優於傳統長條圖的位移方法。

Recently, protecting the intellectual property rights of digitized information is a serious challenge. For the reason above, related information hiding technologies are becoming more and more important. In accordance with different requests, there are three different schemes proposed in this thesis.
The first scheme presents a new block-based authentication watermarking for verifying the integrity of binary images. The original protected image is partitioned into individual blocks. Each block obtains the hashing message by a hashing function. An exclusive-or operation is performed on the hashing message and watermark values and thus the authentication information is embedded into the protected image. If a binary image is tampered with by random modification or counterfeiting attack, the proposed technique can detect which locations have been altered.
In many data hiding techniques, the simple least-significant-bit (LSB) substitution is a general scheme used to embed secret message in the cover image. This practice may injure the quality of the host image which increases the probability that malicious users will notice the existence of something within the stego-image. As a result, the optimal LSB substitution method was proposed to improve the quality of the image, but the optimal LSB substitution solution is not easy to find. Therefore, the second scheme proposed an efficient algorithm as an attempt to solve the above problem. In the second proposed scheme, the optimal LSB substitution problem is regarded as a general assignment problem, and then the Hungarian algorithm is used to find the actual optimal LSB substitution solution. Also the proposed scheme does not need a great deal of memory space.
The third scheme proposed an effective reversible steganographic technique. The main concept is to utilize a similar property of all neighboring pixels. In the proposed scheme, the cover image is divided into non-overlapping groups by the neighboring pixel. Then each group is counted with an error value and then a complete error table can be derived. Then, the frequency of each error value is summed up and allows for the construction of the error histogram. Finally, the histogram shift scheme is used to hide data. The experimental results prove that by using the proposed scheme, the payload size and covered image quality are both obviously better than the original histogram shift scheme.

摘 要 I
ABSTRACT III
致 謝 V
Contents VI
List of Figures VIII
List of Tables X
Chapter 1 Introduction 1
1.1 Background 1
1.2 Watermarking Technology 2
1.3 Steganographic Technology 4
1.4 Thesis Organization 7
Chapter 2 Preliminaries 9
2.1 Simple Least-Significant-Bit(LSB) Substitution 9
2.2. Authentication Watermarking Technique 10
2.3. Optimal Least-Significant-Bit Substitution 11
2.4 Optimal Least-Significant-Bit Substitution with Dynamic Programming Strategy 13
2.5 Assignment Problem 14
2.6 Ni et al.’s Reversible Data Hiding Algorithm 16
Chapter 3 A Block-based Authentication Watermarking Technique for Binary Images 18
3.1 The Proposed Scheme 18
3.1.1 Key-Image Generation Scheme 18
3.1.2 Data Embedding for Binary/Halftone Images 19
3.1.3 The Block-Based Authentication Watermarking Scheme 22
3.2 Experimental Results and Analyses 26
3.2.1 Tamper Detection in the Halftone Image 26
3.2.2 Attack by Randomly Modifying Three Pixels in Halftone Image 27
3.2.3 Counterfeiting Attack in Halftone Images by Copying Block A to Block B 28
3.2.4 Tamper Detection for Binary Images 29
Chapter 4 Finding Optimal LSB Substitution Using Efficient Assignment Problem Solver 31
4.1 The Proposed Scheme 31
4.1.1 Construct the Distortion Matrix 31
4.1.2 Finding the Optimal Substitution Solution by Using Hungarian Algorithm 33
4.2 Experimental Results 37
4.2.1 The Space Complexity Analysis 39
4.2.2 Factor Analysis of Image Quality 41
Chapter 5 Effective Reversible Steganographic Technique by Using Error Histogram 45
5.1 The Proposed Scheme 45
5.1.1 The Algorithm of Constructing the Error Histogram 45
5.1.2 The Algorithm of Hiding Data 47
5.1.3 The Algorithm of Data Extraction and Covered Image Restoration 54
5.2 Experimental Results 55
Chapter 6 Conclusions 61

[1]A.M. Alattar, "Reversible watermark using the difference expansion of a generalized integer transform," IEEE Transactions on Image Processing, Vol. 13, 2004, pp. 1147-1156.
[2]R.J. Anderson, F.A.P. Petitcolas, “On the limits of steganography,” IEEE Journal of Selected Areas in Communications, Vol. 16, 1998, pp. 474-481.
[3]P. Bao and X. Ma, “Image adaptive watermarking using wavelet domain singular value decomposition,” IEEE Transactions on Circuits and Systems for Video Technology, Vol. 15, 2005, pp. 96-102.
[4]P. Barreto, H.Y. Kim, and V. Rijmen, “Toward a secure public-key blockwise fragile authentication watermarking,” Proceedings of IEEE International Conference on Image Processing, Vol. 2, 2001, pp. 494-497.
[5]W. Bender, N. Morimoto, and A. Lu, "Techniques for data hiding," IBM Systems Journal, Vol. 35, 1996, pp. 313-336.
[6]R.E Burkard, “Selected topics on assignment problems,” Discrete Applied Mathematics, Vol. 36, 2002, pp. 257-302.
[7]C.C. Chang, J.Y. Hsiao, C.S. Chan, “Finding optimal least-significant-bit substitution in image hiding by dynamic programming strategy,” Pattern Recognition, Vol. 36, 2003, pp. 1583-1595.
[8]C.K Chan, L.M. Cheng, “Hiding data in images by simple LSB substitution,” Pattern Recognition, Vol. 37, 2004, pp. 469-474.
[9]L. H. Chen and J. J. Lin, “Mean quantization based image watermarking,” Image and Vision Computing, Vol. 21, 2003, pp. 717-727.
[10]R.M. Davis, The data encryption standard in perspective. Computer Security and the Data Encryption Standard, National Bureau of Standards Special Publication, Feb. 1978.
[11]M.S. Fu and O.C. Au, “Data hiding by smart pair toggling for halftone images,” Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing, Vol. 4, 2000, pp. 2318-2321.
[12]M.S. Fu and O.C. Au, “Data hiding in halftone images by stochastic error diffusion,” Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing, Vol. 3, 2001, pp. 1965–1968.
[13]M.S. Fu and O.C. Au, “Data hiding for halftone images,” Proceedings of SPIE, Vol. 3971, San Diego, California, USA, 2000, pp. 228-236.
[14]J. Fridrich, M. Goljan, and R. Du, "Invertible authentication," in SPIE Photonics West, Security and Watermarking of Multimedia Contents III, Vol. 3971. San Jose, CA, 2001, pp. 197-208.
[15]J. Fridrich, M. Goljan, and R. Du, "Lossless data embedding-New paradigm in digital watermarking," EURASIP Journal on Applied Signal Processing, Vol. 2002, pp. 185-196.
[16]M. Holliman and N. Memon, “Counterfeiting attacks on oblivious block-wise independent invisible watermarking schemes,” IEEE Transactions on Image Processing, Vol. 9, No. 3, March 2000, pp. 432-441.
[17]K.C. Ho, “Non-causal error diffusion for image halftoning,” Proceedings of IEEE International Symposium on Circuits and Systems, Vol. 5, Arizona, USA, 2002, pp. 257-260.
[18]S.Y. Ho, H.M. Chen, L.S. Shu, “Solving large knowledge base partitioning problems using the intelligent genetic algorithm,” Proceedings of the Genetic and Evolutionary Computation Conference, 1999, pp. 1567-1572.
[19]N.F. Johnson, S. Jajodia, “Exploring steganography: seeing the unseen,” IEEE Computer Magazine, Vol. 31, No. 2, 1998, pp. 26-34.
[20]H.Y. Kim and A. Afif, “A secure authentication watermarking for halftone and binary images,” International Journal of Imaging Systems and Technology, 2004, pp. 147-152.
[21]H.W. Kuhn, ”The Hungarian method for the assignment problem,” Naval research logistics quarterly, Vol. 2, 1955, pp. 83-98.
[22]S. J. Lee and S. H. Jung, “A survey of watermarking techniques applied to multimedia,” IEEE International Symposium on Industrial Electronics, Vol. 1, Pusan, South Korea, 2001, pp. 272-277.
[23]M. Mese and P. P. Vaidyanathan, “Optimized halftoning using dot diffusion and methods for inverse halftoning,” IEEE Transactions on Image Processing, Vol. 9, No. 4, 2000, pp. 691-709.
[24]Z. Ni, Y. Q. Shi, N. Ansari, and W. Su, "Reversible data hiding," IEEE Transactions on Circuits and Systems for Video Technology, Vol. 16, 2006, pp. 354-362.
[25]F. Petitcolas, RJ Anderson, and MG Kuhn, “Information hiding - a survey,” Proceedings of the IEEE: special issue on Protection of Multimedia Content, Vol. 87, No. 7, 1999, pp. 1062-1078.
[26]R. Rivest, A. Shamir, L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Communications of the ACM, Vol. 21, No. 2, 1978, pp. 120-126.
[27]R. L. Rivest, “The MD5 message digest algorithm,” IETF RFC 1321, April 1992.
[28]B. Schneier, Applied Cryptography, second ed., Wiley, New York, 1996.
[29]S. Suthaharan, “Fragile image watermarking using a gradient image for improved localization and security,” Pattern Recognition Letters, Vol. 25, 2004, pp. 1893-1903.
[30]J. Tian, "Reversible data embedding using a difference expansion," IEEE Transactions on Circuits and Systems for Video Technology, Vol. 13, 2003, pp. 890-896.
[31]C.L. Tsai, H.F. Chiang, K.C. Fan and C.D. Chung, “Reversible data hiding and lossless reconstruction of binary images using pair-wise logical computation mechanism,” Pattern Recognition, Vol. 38, 2005, pp. 1993-2006.
[32]R.G.. Van Schyndel, A.Z. Tirkel, and C.F. Osborne, “A digital watermark,” Proceedings of IEEE International Conference on Image Processing, Vol. 2, 1994, pp. 86-90.
[33]R.Z. Wang, C.F. Lin, J.C. Lin, “Image hiding by optimal LSB substitution and genetic algorithm,” Pattern Recognition, Vol. 34, 2001, pp. 671-683.
[34]P.W. Wong, “A watermark for image integrity and ownership verification,” Proceedings of the IS&T PIC Conference, Oregon, Portland, 1998, pp. 374-379.
[35]P.W. Wong, “A public key watermark for image verification and authentication,” Proceedings of IEEE International Conference on Image Processing, Vol. 1, 1998, pp. 455-459.
[36]P.W. Wong and N. Memon, “Secret and public key image watermarking schemes for image authentication and ownership verification,” IEEE Transactions on Image Processing, Vol. 10, No. 10, 2001, pp. 1593-1601.
[37]G. Voyatzis, I. Pitas, "Chaotic mixing of digital images and applications to watermarking," European Conference on Multimedia Applications, Vol. 2, 1996, pp. 687-695.
[38]X. Zhang and S. Wang, "Steganography using multiple-base notational system and human vision sensitivity," IEEE Signal Processing Letters, Vol. 12, 2005, pp. 67-70.