@prefix vivo: . @prefix edm: . @prefix ns0: . @prefix dcterms: . @prefix dc: . @prefix skos: . vivo:departmentOrSchool "Applied Science, Faculty of"@en, "Electrical and Computer Engineering, Department of"@en ; edm:dataProvider "DSpace"@en ; ns0:degreeCampus "UBCV"@en ; dcterms:creator "Paquet, Alexandre"@en ; dcterms:issued "2009-09-29T23:19:19Z"@en, "2002"@en ; vivo:relatedDegree "Master of Applied Science - MASc"@en ; ns0:degreeGrantor "University of British Columbia"@en ; dcterms:description """The rapid expansion of the Internet and the overall development of digital technologies in the past years have sharply increased the availability of digital media. Digital contents can be reproduced without loss of quality, but they may also be easily modified, and sometimes, imperceptibly. In many contexts, any alteration of image, video or audio data must be detected. Therefore, some work needs to be done to develop security systems to protect the content of digital data. Watermarking is accepted as a plausible candidate for such an application as it allows for the invisible insertion of information in a host by its imperceptible modification. This thesis is concerned with the protection of information contained in digital images. A novel, semi-fragile watermarking technique for the authentication of images is developed. Image protection is achieved by the insertion of a secret author's identification key in an image's wavelet packet (WP) decomposition. Rounding the mean of selected regions of WP coefficients embeds the binary key. To take maximum advantage of the host image's characteristics in the embedding process, an optimal quantization protocol is formulated. The image's verification is done without the use of the original unmarked image. The detection of unauthorized frequency or spatial tampering with the image is performed by a combined interband/intraband verification protocol. This new technique can detect malicious tampering with images, but stays unaffected by high quality JPEG compression."""@en ; edm:aggregatedCHO "https://circle.library.ubc.ca/rest/handle/2429/13336?expand=metadata"@en ; dcterms:extent "6325205 bytes"@en ; dc:format "application/pdf"@en ; skos:note "Wavelet Packets-based Digital Watermarking for Image Authentication by Alexandre Paquet B.Eng, Universite Laval, 2000 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of Applied Science in THE FACULTY OF GRADUATE STUDIES (Department of Electrical & Computer Engineering) We accept this thesis as conforming to the required standard The University of British Columbia July 2002 © Alexandre Paquet, 2002 In p resen t ing this thesis in partial fulfi lment of the requ i rements for an a d v a n c e d deg ree at the Univers i ty o f Brit ish C o l u m b i a , I agree that the Library shall make it freely available for reference a n d s tudy. I further agree that p e r m i s s i o n for ex tens ive c o p y i n g o f this thesis for scholar ly p u r p o s e s m a y b e g ran ted b y the h e a d of my depa r tmen t o r by his o r her representat ives . It is u n d e r s t o o d that c o p y i n g o r p u b l i c a t i o n of this thesis for financial gain shall no t be a l l o w e d w i t h o u t my wr i t t en p e r m i s s i o n . D e p a r t m e n t of ZJ^j^rJ 8 (cM«f feny W The Univers i ty o f Brit ish C o l u m b i a V a n c o u v e r , C a n a d a D a t e A ^ , ^ f _ ? n r o D E - 6 (2/88) Abstract The rapid expansion of the Internet and the overall development of digital technologies in the past years have sharply increased the availability of digital media. Digital contents can be reproduced without loss of quality, but they may also be easily modified, and sometimes, imperceptibly. In many contexts, any alteration of image, video or audio data must be detected. Therefore, some work needs to be done to develop security systems to protect the content of digital data. Watermarking is accepted as a plausible candidate for such an application as it allows for the invisible insertion of information in a host by its imperceptible modification. This thesis is concerned with the protection of information contained in dig-ital images. A novel, semi-fragile watermarking technique for the authentication of images is developed. Image protection is achieved by the insertion of a secret au-thor's identification key in an image's wavelet packet (WP) decomposition. Round-ing the mean of selected regions of WP coefficients embeds the binary key. To take maximum advantage of the host image's characteristics in the embedding pro-cess, an optimal quantization protocol is formulated. The image's verification is done without the use of the original unmarked image. The detection of unautho-rized frequency or spatial tampering with the image is performed by a combined interband/intraband verification protocol. This new technique can detect malicious tampering with images, but stays unaffected by high quality JPEG compression. ii Contents Abstract ii Contents iii List of Tables vii List of Figures viii List of Abbreviations xiii Glossary xiv Acknowledgements xv 1 Introduction 1 1.1 Digital Watermarking 1 1.2 Problem Definition 3 1.3 Organization of the Thesis 4 2 Wavelet Analysis 7 iii 2.1 Introduction 7 2.2 Historical Perspective 8 2.3 Wavelets and Multiresolution Analysis 14 2.3.1 Series Expansion 14 2.3.2 Filter Banks 16 2.3.3 Multiresolution and Wavelet Theory 23 2.4 Wavelet Packet Analysis 28 2.5 Multidimensional Signals 32 2.6 Summary 33 3 Digital Watermarking 34 3.1 Introduction 34 3.1.1 Definition of Watermarking 35 3.2 Historical Perspective 36 3.3 Background on Watermarking 38 3.3.1 Host Media for Watermarking 40 3.3.2 Applications of Watermarking 41 3.3.3 Requirements of Watermarking Systems 42 3.3.4 Embedding Domains and Decoding Procedures . . . . 43 3.4 Watermarking for Copyright Protection 45 3.5 Summary 50 4 Image Authentication 52 4.1 Introduction 52 4.2 Approaches to authentication 54 iv 4.3 Requirements of Authentication Schemes 56 4.4 Previous Work 58 4.4.1 Fragile Watermarking in the Spatial Domain 58 4.4.2 Fragile Watermarking in Transform Domains 61 4.5 Our WP-Based Image Authentication 69 4.5.1 Embedding Process 70 4.5.2 Optimal Quantization Step 81 4.5.3 Watermark Decoding Process 84 4.6 Summary 89 5 Experimental Results 91 5.1 Introduction 91 5.2 Embedding, Decoding and Visibility 95 5.3 Tampering Detection 107 5.4 _ Comparison with Ei'konamark 112 5.4.1 Image Quality and Tampering Detection 113 5.4.2 Resistance to Collage Attacks . 119 5.4.3 Summary of Comparisons 122 5.5 Robustness to J P E G Compression 123 5.5.1 Predistortion in the Spatial and Wavelet Domains . . . 125 5.6 Summary 130 6 Conclusions and Future Research 132 6.1 Overview 132 v 6.2 Digital Watermarking and Content Authentication 133 6.2.1 Our Wavelet Packets-Based Authentication Scheme 135 6.2.2 Review of Results 136 6.3 Future Research 138 6.4 Closing Remarks 140 Bibliography 141 Appendix A 150 A . l Fourier Analysis 150 A.2 Orthonormality of Haar Basis 151 A.3 Conditions of Filters Ht(z) and Fi(z) 152 A.4 Definition of Multiresolution 153 A.5 Steps towards Multiresolution 154 A.6 Erasable Watermarking 154 Appendix B 156 vi List of Tables 4.1 Optimum Step Sizes for Laplacian Distribution with a2 = 1 (from [65]) 84 5.1 Average PSNR for Different Wavelet Functions 103 5.2 Average Detection Rate for Different Wavelet Functions . . . . 107 vii List of Figures 2.1 Haar Scaling () and Wavelet (ip) Functions 9 2.2 Meyer Scaling () and Wavelet (ip) Functions 9 sines and cosines, which are both infinite in time, the standard Fourier de-composition lacks the time1 localization necessary for the accurate analysis of several real signals. The idea of WFA is to study the frequencies of a signal for time-limited windows. This allows for some time localization of the frequency characteristics of a given signal. WFA concept finally allowed the examination of things in terms of both time and frequency. Nonetheless, Haar remained the only example of a wavelet, and the next major advancements did not come until later in the 1980s. Jean Morlet and Alex Grossman teamed up in 1981. Together, they discovered that a signal could be transformed into wavelet form, and then synthesized back into the original signal without any loss of information. Then, in 1984, they were the first to use the term wavelet to describe their functions [30]. More specifically, they were called Wavelets of Constant Slope. Other researchers had used the term wavelets for different signal processing applications (see [61] for example) but Morlet and Grossman were the first to use it as it is now currently referred to, which is as follows: a wavelet is a unique function, limited in time and frequency, that can be translated and dilated to form multiresolution basis used to decompose a signal at different levels. In addition, their major contribution was the finding of a simple signal recomposition method from its wavelet coefficients. They also discovered an-1Time and space will be used alternatively throughout this thesis as time is, in fact, but only one possible space representation. However, since a lot of concepts used have first been developed for time-dependant signals, we find it helpful to use the same notation. 10 other interesting thing that is now commonly used in wavelet-based coding: a small modification in the wavelet coefficients only causes a small change in the original signal. This might not have appeared to be especially meaning-ful at the time, but when considering that modern wavelet-based compression schemes quantize wavelet coefficients, if it had been otherwise, data compres-sion would be a much more difficult task today. The real breakthrough in wavelets analysis, however, happened in the late 1980's when a lot of papers now considered classic were published. Yves Meyer and Stephane Mallat were two important contributors to this newborn field. Investigating the use of wavelets in many different applied fields, they were amongst the first to develop the concept of multiresolution analysis for wavelets [49]. This was an important step for the advancement of research on wavelets. As a result, multiresolution is now an extensively used signal decomposition approach. Mallat and Meyer were the first to mention scaling functions of wavelets, which allow researchers and mathematicians to construct their own wavelets using established criteria [80]. Around the same time, a Belgian physicist named Ingrid Daubechies employed multiresolution analysis to create her own family of wavelets. Using construction methods related to filter banks, she introduced in [23] a family of compactly supported orthogonal wavelet systems with arbitrarily high, but fixed regularity. These wavelets offer a number of desirable properties (such as compact support, orthogonality, regularity, and continuity) that make them trully attractive2. This is why the Daubechies Wavelets are now some of the 2 More on this in the next section. 11 -5 0 5 -5 0 5 Figure 2.2: Meyer Scaling () and Wavelet (ip) Functions 12 most common ones today. ft Db4: \\|/ i i 1 \"\"0 2 4 6 0 2 4 6 Figure 2.3: Daubechies-4 Scaling () and Wavelet (ip) Functions Daubechies' work was probably the starting point of much focused re-search on wavelets that has lead to their acceptance as a modern mathematical tool and their wide use in sciences and engineering. Of course, many other researchers have contributed to the advancement of the field in the last decade, and several applications have been found. In particular, wavelet transforms prove to be extremely effective for image coding, and upcoming image com-pression standards-such as JPEG-2000-make use of them. From this, it is clear that wavelets are definitely a tool for the future, and this is why the knowledge 13 of their historical and theoretical bases is of great interest. 2.3 Wavelets and Multiresolution Analysis In her now classic book [24], Ingrid Daubechies defines the wavelet transform as the following: a tool that cuts up data or functions or operators into different frequency components and then studies each component with a resolution matched to its scale. The wavelet transform of a signal evolving in time depends on two variables: frequency and time. Therefore, these transforms provide an accurate tool for time-frequency localization. This is the most important factor that explains why wavelet transforms have already attracted so much attention. Extensive publications on the general theory of wavelets are found in [24, 69, 80], while [68] details their specific applications to image processing. We now briefly examine the concepts linked with series expansion, and subse-quently, the theory behind filter bank analysis. Finally, we introduce the idea of multiresolution and its application to wavelet decomposition. 2.3.1 Series Expansion The goal of series expansion is to represent a signal or function as a combina-tion of bases. Essentially, it means that we want to find a set of elementary signals {(pi}iez so that we can write an original signal x, as a linear combination 14 of the following basis: i where the expansion coefficients OJJ'S can be obtained by the computation of the inner product of the basis dual set {&} with the signal x as follows: <*i = '52 i [ 2 f t - J ] x m = -^=x[2k]—]=x[2k+l] (2.9) uz v 2 v 2 and so, the analysis filter bank is defined with the impulse response of the following associated filters: r T2 forn = - l , 0 0 otherwise h0[n] = { (2.10) 5First, the n = 2k results from the downsampling operation. Second, the filters are iden-tified Ho(z) and Hi(z) in the figure. Z-domain representation is used simply by convention. 19 hi[n] = { T2 f o r n = ° forn=-l (2-11) 0 otherwise It is clear that the impulse responses found are time-reversed versions of the basis functions (which correspond to the (Haar) scaling ((f)) and wavelet (ip) functions of Figure 2.1). This comes from the fact that convolution is an inner product with time reversal, giving the following: h0[n] = ip0[-n] and hi[n] = 2fc+i[n] (2.14) keZ kcZ Keeping in mind that the reconstruction operation includes upsampling and convolution, the previous equation (2.14) allows the extraction of the 20 following: (£)) and wavelet (ip(t)) functions. As the number of decomposition levels used increases, the subspace number j increases as well8. The wavelet space Wj corresponds to the difference between the present scaling space Vj and previous one Vj_i. It means that Vj © Wj = Vj-\\. This is shown in Figures 2.6 and 2.7, and graphically generalized in the frequency domain by Figure 2.8. 7l/(2J) 51/(2)') 7l/4 7C/2 71 Figure 2.8: Ideal Spectrum Division from Wavelet Decomposition Up to now, we have seen that the analysis side of the octave band filter 8We use the same notation as [24] and [69] but several others have been used; for example [80] employs exactly the opposite convention. 25 bank calculates the forward wavelet transform, while the synthesis side calcu-lates the inverse wavelet transform. Therefore, a two-channel QMF bank can be directly used to form wavelet decomposition. This is probably the most fre-quently employed method of designing and implementing wavelet transforms. It is nonetheless important to summarize the more theoretical approach to wavelet decomposition, which is more related to series expansion than filter banks. In order to account for the fact that the signal has to be decomposed into two bands at each level, two basis functions have to be defined. At each scale, a scaling function (f>(t) is defined in addition to the wavelet function ift(t). The first one acting like the low pass filter H0, while the second one is linked to the high pass filter Hi. Furthermore, in order to keep the total length of the decomposed signals equal to the length of the original signal-a fact that is taken care of by the downsampling operation in the filter bank representation-and to increase the definition at each level, a dilation operation needs to be performed (see Equation A. 13) on the original basis. Finally, given the original basis (j>, the scaling and wavelet functions at level j are as follows: oo {2H - k) (2.23) k=—oo oo (2H — k) (2.24) k=—oo Consequently, the appropriate initial filter ho and scaling function make possible the definition of different scaling ((f>(t)) and wavelet (ip(t)) func-tions by iteration of the dilation equations. Of course, the choice of the original 26 basis is of primordial importance, but as stated earlier, this is not the concern of the present thesis. In addition, a lot of work already exists in the field and that gives us enough material to work with. We introduce, in A.5, the six steps towards multiresolution, as proposed in [69]. Here, we present the Haar scaling and wavelet functions for V0 and Wq as they are shown in Figure 2.1: 1 0 < t < 1, (2.25) 0 otherwise 1 0 < t < \\, m = \\ -1 § < * < 1 , ( 2- 2 6) 0 otherwise One final point needs to be made in order to complete our discus-sion about multiresolution wavelet transform. What is the advantage of this specific form of signal decomposition over others? Figure 2.9 clearly shows that wavelet decomposition allows both frequency and time localization, while Fourier Transform does not. For FT, A / and At are fixed, even if the signal is first windowed in time. On the other hand, wavelet transform gives scalable time/frequency resolution as Aw oc 2J and A i oc 2~J, thus allowing the choice of more or less levels of decomposition in accordance with the importance of each resolution. Finally, as different bases exist, it is also possible to choose and/or adapt a particular basis according to the application considered. This section reviewed the fundamentals of multiresolution analysis and its application to wavelet theory. We explained how multiresolution concepts are applied to octave band filter bank systems for the implementation of 27 *o T ^ T Figure 2.9: Frequency Tilling for Fourier and Wavelet Transforms wavelet transforms. In addition, we highlighted the main steps leading to the computation of scaling and wavelet functions from a given basis by dila-tion operations. Finally, we showed the time-frequency localization allowed by wavelet transform, and the degree of freedom granted by the existence of a wide range of basis. As a result, the advantages provided by the relatively new wavelet transform over the more traditional Fourier analysis should be very clear. 2.4 Wavelet Packet Analysis We just showed that the wavelet transforms offer several advantages in terms of localization, resolution and flexibility compared to the Fourier transform. In addition, we demonstrated that wavelet transforms can be easily implemented by the use of octave band Q M F banks. This means that, by recursive filtering on the signal's coarse approximation, it is possible to achieve efficient and 28 simple standard wavelet analysis. This is of great importance as it allows for both efficient and accurate signal decomposition based on solid mathematical definitions. Here, we are interested in seeing what would happen if we generalized the discussion of Subsection 2.3.3 to other, more arbitrary, tree structures. We are particularly interested in the full-tree decomposition scheme where all the outputs of the first stage, that is the high passed as well as the low passed ones, are further decomposed. This means that, starting from a single two-channel filter bank, we decompose a one-dimensional signal in 2J bands at each j resolution level. Of course, this full tree decomposition, first proposed in [14] and known as wavelet packets (WP), can be implemented using the same filter bank-related approach [12, 13]. The wavelet packet library is produced by cascading filtering and downsampling operations in a tree-structure. Figures 2.6 and 2.7 thus become Figures 2.10 and 2.11. x[n] Hd(z) 4-2 l H0(z) 4- 2 Hx(z) 4-2 H*z) 4- 2 w, 02 H0(z) 4-2 Hi(z) 4-2 w, w, Figure 2.10: Two Levels of Wavelet Packet Decomposition using Filter Bank Representation 29 wv t 2 F y)) wAx, v) (2-27) i k where the 2D basis functions are defined from the ID ones as follows: &,k{x,y) =