High performance gray-level watermarking system

[0001] The preset invention relates to the watermarking system for data protection. More particularly, the new invention system can provide gray level signal watermarking for images, video, music and speech applications.

[0002] In recent years, Internet system has become popular for transmitting and receiving digital data. Because the nature of Internet is an open system, transmitted data is easily copied, altered or even stolen. Hence communication security becomes a major concern. Moreover, digitized multi-media data such as image, video and music signals have been widely transmitted using this open system for its convenience. The problem of copyright protection becomes a most controversial subject. Unfortunately, at the present time, the protection technique is nowhere near perfect. Hence large amount of unauthorized duplication is found daily. In order to resolve this problem, watermarking techniques [1–4] have become a popular tool to protect the secrecy of the transmitted document. To achieve a high performance watermarking, the algorithm must possess properties of invisibility, security and robustness. In recent literatures, most authors [5–7] concentrated on using binary data watermarking, such as “logo” or “text”, the gray-level image watermarking for protecting multi-media data has rarely been discussed. In this invention, a gray-level data watermarking based on sub-band filtering and codebook principles is developed. In order to accomplish a high security watermarking, we avoid using the original data to extract watermark. Instead, we develop a private-key system for protecting watermark, which gives an additional security level.

[0003] Although many watermarking algorithms have been developed in recent years, most of them concentrated on using binary data such as logos or texts. In this invention, the sub-band filtering approach is successfully employed for a gray-level data watermarking. With signal processing in the frequency domain, the feature of progressive transformation is utilized to disperse the watermark into the entire data and to enhance the robustness. The watermark is randomly dispersed into the high frequency portion of the original data. We achieved good hiding quality, which makes the unfriendly attempt on either duplication or alternation extremely difficult. To extract the watermark, we develop a four-fold key system rather than using the original data. And the privacy key is further encrypted to increase the degree of security. Furthermore, the progressive feature of DCT is used to enhance the robustness of watermarking. Even if the composite data is under attacked, the watermark can be restored from the residual coefficients, where the resulting watermark only suffers different degree of blurring but no serious distortions. Our watermark algorithm possesses the nature of good vision quality, high security, and a strong robustness. The watermarking scheme can provide good protection on the secrecy of multi-media data transmission over the current internet system, and no double shall contribute substantially on resolving the copyright violation problems.

[0017] It is well known that the spectrum of a data can be divided into four sub-bands [8], the LL band, LH band, HL band and HH band to represent its frequency components of 2D-signal. Filters for different bands can be obtained from the following equations

[0018] $\begin{array}{cc}\mathrm{LL}\mathrm{band}:X_{\mathrm{LL}}=H_{\mathrm{LL}}\left(x_{\mathrm{ij}}\right)=\frac{1}{C}\sum _{n1=0}^{m1}\sum _{n2=0}^{m2}{x}_{\mathrm{ij}}{W}_1^{-\mathrm{kn}1}{W}_2^{-\mathrm{kn}2},& \left(1\right)\\ \mathrm{LH}\mathrm{band}:X_{\mathrm{LH}}=H_{\mathrm{LH}}\left(x_{\mathrm{ij}}\right)=\frac{1}{C}\sum _{n1=0}^{m1}\sum _{n2=0}^{m2}{x}_{\mathrm{ij}}{W}_1^{-\mathrm{kn}1}{W}_2^{-\left(k+\pi \right)n2},& \left(2\right)\\ \mathrm{HL}\mathrm{band}:X_{\mathrm{HL}}=H_{\mathrm{HL}}\left(x_{\mathrm{ij}}\right)=\frac{1}{C}\sum _{n1=0}^{m1}\sum _{n2=0}^{m2}{x}_{\mathrm{ij}}{W}_1^{-\left(k+\pi \right)n1}{W}_2^{-\mathrm{kn}2},& \left(3\right)\\ \mathrm{HH}\mathrm{band}:X_{\mathrm{HH}}=H_{\mathrm{HH}}\left(x_{\mathrm{ij}}\right)=\frac{1}{C}\sum _{n1=0}^{m1}\sum _{n2=0}^{m2}{x}_{\mathrm{ij}}{W}_1^{-\left(k+\pi \right)n1}{W}_2^{-\left(k+\pi \right)n2};& \left(4\right)\end{array}$
where C is a constant for transformation. Using different frequency factors W1 and W2, transformations such as the Discrete Fourier Transform (DFT), Discrete Cosine Transform (DCT), etc. can be selected at will. We adapt the DCT for it has been widely used in watermarking applications. In order to reconstruct the data without frequency aliasing, transformation should have the Quadrature Mirror Filter (QMF) feature [9]. To confirm QMF in 2D transforms, horizontal symmetry, vertical symmetry and cross symmetry properties must be achieved first. In discrete signal processing, a 2D spatial block {fjk} is transformed into a DCT block by

[0019] $\begin{array}{cc}{F}_{\mathrm{uv}}=C_{\mathrm{uv}}\sum _{j=0}^{N-1}\sum _{k=0}^{N-1}{f}_{\mathrm{jk}}{W}_{\mathrm{jk}}^{\mathrm{uv}}=\mathrm{FDCT}\left(f_{\mathrm{jk}}\right),W_{\mathrm{jk}}^{\mathrm{uv}}=\cos \left(\frac{\left(2j+1\right)u\pi }{2N}\right)\cos \left(\frac{\left(2k+1\right)v\pi }{2N}\right).& \left(5\right)\end{array}$
DCT transformation can easily achieve horizontal symmetry, vertical symmetry and cross symmetry by observing

[0020] $\begin{array}{c}{W}_{\left(N-k-1\right)}^{\mathrm{uv}}={\left(-1\right)}^v{W}_{\mathrm{jk}}^{\mathrm{uv}},\\ W_{\left(N-j-1\right)k}^{\mathrm{uv}}={\left(-1\right)}^u{W}_{\mathrm{jk}}^{\mathrm{uv}}\\ \mathrm{and}\\ W_{\left(N-j-1\right)\left(N-k-1\right)}^{\mathrm{uv}}={\left(-1\right)}^{u+v}{W}_{\mathrm{jk}}^{\mathrm{uv}}\end{array}$
respectively. For 2D sub-bands, we can define each band according to equations (1)–(4) as: (a) LL band F_LL=F_u1,v1, |u1|<N/2 and |v1|<N/2; (b) LH band F_LH=F_u2,v2, N/2>|u2| and N>|v2|≧N/2; (c) HL band F_HL=F_u3,v3, N>|u3|≧N/2 and |v3|<N/2; (d) HH band F_HH=F_u4,v4, N>|u4|≧N/2 and N>|v4|≧N/2.

[0021] In order not to confuse the “watermark data” and “watermarked data”, we shall name the former as the “watermark” and the latter as the “composite data” hereafter. Let {tilde over (f)}_jk denote a composite data where a watermark w_jk has been embedded onto an original data f_jk. Clearly, the nature of a watermark is that it must be perceptually invisible in order to prevent any attempt on the composite data by unfriendly sources. Intuitively, the high frequency portion of the original data is an ideal place to insert a watermark since the great variation in high frequency makes the watermark much more difficult to detect. As the original data is divided into 8×8 blocks, its sub-bands can be obtained from

[0022] $\begin{array}{cc}{F}_{\mathrm{uv}}={\mathrm{FDCT}\left(f_{\mathrm{jk}}\right)}_{8\times 8}={\left(\begin{array}{cc}{F}_{\mathrm{LL}}& F_{\mathrm{LH}}\\ F_{\mathrm{HL}}& F_{\mathrm{HH}}\end{array}\right)}_{8\times 8}={\left(\begin{array}{cc}{F}_{u1v1}& F_{u2v2}\\ F_{u3v3}& F_{u4v4}\end{array}\right)}_{8\times 8}.& \left(6\right)\end{array}$
The HH band components F_HH can be viewed as a measuring parameter to search for high frequency blocks. Let us define P_HH as

[0023] $\begin{array}{cc}{P}_{\mathrm{HH}}=\sum F_{\mathrm{HH}}=\sum _{u4=4}^7\sum _{v4=4}^7F_{u4,v4},& \left(7\right)\end{array}$
which denotes a high frequency factor of the HH sub-band. As the P_HH value is larger, the block frequency variance becomes higher. We search and record the P_HH value of each block in accordance with its relative block coordinate (m,n), and use the P_HH (m,n) to denote the high frequency variance for (m,n)^th block. If the P_HH (m,n)>Variance-Threshold, which means this block is capable to embed a watermark without visible distortion. Then this high frequency block should be marked, for next discussions, let M(m,n) denote a coordinate of one marked block.

[0024] In order to disperse the spatial correlation of the watermark, the entire watermark w_jk is transformed by DCT. Then the DCT coefficients can be split into sub-bands as

[0025] $\begin{array}{cc}{W}_{\mathrm{uv}}={\mathrm{FDCT}\left(w_{\mathrm{jk}}\right)}_{m1\times m2}={\left(\begin{array}{cc}{W}_{\mathrm{LL}}& W_{\mathrm{LH}}\\ W_{\mathrm{HL}}& W_{\mathrm{HH}}\end{array}\right)}_{m1\times m2},& \left(8\right)\end{array}$
where the watermark size is m1×m2. Since the W_LL band contains more information about the watermark, only their DCT coefficients are embedded into the marked blocks. The value of the LL band coefficient is usually large due to the full picture transformation. To reduce visible distortion, we need to quantize these coefficients before the embedding operation. Then equation (8) is simplified to

[0026] $\begin{array}{cc}{\tilde{W}}_{\mathrm{uv}}=\frac{1}{Q_{m1m2}}{\left(\begin{array}{cc}{W}_{\mathrm{LL}}& 0\\ 0& 0\end{array}\right)}_{m1\times m2}={\left(\begin{array}{cc}{\tilde{W}}_{\mathrm{LL}}& 0\\ 0& 0\end{array}\right)}_{m1\times m2},& \left(9\right)\end{array}$
where Q_m1m2 are parameters from a quantization table. Note that the rank of {tilde over (W)}_LL is one quarter of that of {tilde over (W)}_uv. In order to reduce the bit-rate of the watermark further, we repeat the above procedure to produce a second layer LL band _LL from the first layer {tilde over (W)}_LL. Thus total bit-rate of the watermark is now reduced to 1/16 of the original one.

[0027] As coefficients of _LL are embedded into the marked blocks, we aim to achieve good hiding quality, high security and strong robustness. This can be easily done since only one coefficient of _LL is inserted into the high frequency portion of each marked block. Thus the watermarked block becomes

[0028] $\begin{array}{cc}{\tilde{F}}_{\mathrm{uv}}={\left(\begin{array}{cc}{F}_{\mathrm{LL}}& F_{\mathrm{LH}}\\ F_{\mathrm{HL}}& {\stackrel{\_}{F}}_{\mathrm{HH}}\end{array}\right)}_{8\times 8}& \left(10\right)\end{array}$
where {overscore (F)}_HH contains one watermark coefficient. Note that the marked blocks are randomly distributed, hence the watermark information is dispersed on the original picture everywhere. Finally, DCT coefficients are converted into spatial domain by using the inverse DCT transformation, hence the composite data is obtained by {tilde over (f)}_jk=IDCT({tilde over (F)}_uv) of each sub-block.

[0029] The marked coordinate is an important information for restoring the watermark, M(m,n) can be treated as a key to restore the watermark. Let us define a privacy key PK as
PK={M1,M2, . . . , Mn}, Mx⊂M(m,n), x=1 to n,  (11)
which is a set of coordinates of the marked blocks. In order to attain high security, the privacy key can be further re-permuted by using conventional coding techniques, such as data encryption, etc. [10]. However, no algorithm is capable to remain undecoded forever, but we can create multiple privacy keys for our watermark with time-dependent codes to increase the difficulty of decoding and hence to prolong the duration of secrecy. Therefore users have a Key Bank, KB={PK0, PK1, . . . , Y}, where KB contains Y privacy keys to be used at various appropriate times. The complete embedding procedure of our algorithm is illustrated in FIG. 1.

[0030] In our watermarking system, we employ the designated keys rather than the original data to extract watermark. These keys are computed according to the frequency variance of original datas, and are independent of the watermark. So they can be pre-stored on disks in the decoder of the authorized user. To extract watermark, we only need to send the composite data to users without the keys. The key in our algorithm has four folds. They are (a) Privacy Key: provides the position of the marked blocks. (b) Permutation Function key: decrypts random values into normal ones. (c) Quantization Table of {tilde over ({tilde over (W)}_LL: provides the de-quantization for DCT coefficients of the watermark. (d) Embedding Coefficient Location: extracts the watermark coefficient from HH band of the marked blocks. In general, the procedure of extraction is just the opposite of the embedding operation. The keys that are pre-stored in the Key Bank use the same parameter for both encoder and decoder, where each user key is corresponding to one original data. Since the composite data is very similar as the original data, we can select one user key from Key Bank according to the composite data without any additional information required.

[0031] FIG. 2 shows the steps for watermark extraction. When users receive a composite data, it is first partitioned into 8×8 blocks. Since the watermark is hidden on DCT domain, these blocks should be transformed by DCT first, i.e. {tilde over (F)}_uv (Extract)=DCT({tilde over (f)}_jk)_8×8. As previously mentioned, watermark coefficients are embedded in the high frequency blocks, and the position of these marked block is recorded in the privacy key. By referring the different composite data, one can choose the appropriate privacy key from the Key Bank where the key order is re-permuted by decryption procedures. Hence the watermark coefficients are sequentially extracted from the HH band of {tilde over (F)}_uv (Extract) in the marked blocks. Finally, the LL band matrix of the watermark can be reconstructed. To restore the watermark, we need to combine the LH band, HL band and HH band of the watermark for a complete 2D sub-band processing. However, data in these bands are not used in our approach, so we must insert zeros to LH, HL and HH bands to achieve a complete matrix. After a de-quantization procedure, we can reconstruct the coefficient matrix Ŵ_uv of the watermark, and finally the watermark can be extracted from the inverse DCT of Ŵ_uv.

[0032] The other watermarking invention uses the codebook concept. In the first stage, the original data and watermark data all need be transformed to DCT domain. When the frame size of original picture f_jk is M1×N1, we take a full-frame transformation. Thus the DCT coefficients are attained form

[0033] $\begin{array}{cc}{F}_{u1v1}={\mathrm{FDCT}\left(f_{\mathrm{jk}}\right)}_{M1\times \mathrm{N1}}={(\begin{array}{c}\begin{array}{cccc}{F}_{00}& F_{01}& F_{{02}_{...}}& F_{0\left(M-1\right)}\\ F_{10}& F_{11}& & F_{1\left(M-1\right)}\\ \cdots & \cdots & \cdots & \cdots \end{array}\\ \begin{array}{ccc}{F}_{\left(N-1\right)0}& \cdots & F_{\left(N-1\right)\left(M-1\right)}\end{array}\end{array})}_{M1\times N1},& \left(12\right)\end{array}$
where u1 and v1 are frequency indexes for coefficient F_u1v1. By the same way, we attain the watermark coefficients from

[0034] $\begin{array}{cc}{W}_{u2v2}={\mathrm{FDCT}\left(w_{\mathrm{xy}}\right)}_{M2\times N2}={(\begin{array}{c}\begin{array}{cccc}{W}_{00}& W_{01}& W_{{02}_{...}}& W_{0\left(M2-1\right)}\\ W_{10}& W_{11}& {}_{\dots \dots \dots }& W_{1\left(M2-1\right)}\\ \cdots & \cdots & \cdots & \cdots \end{array}\\ \begin{array}{ccc}{W}_{\left(\mathrm{N2}-1\right)0}& \cdots & W_{\left(N2-1\right)\left(M2-1\right)}\end{array}\end{array})}_{M2\times N2},& \left(13\right)\end{array}$
where the watermark data size is M2×N2, and its frequency indexes use u2 and v2. To avoid the visible distortion after embedding process, the high frequency part of F_u1v1 is good choice to insert watermarking information since human eyes are difficult to detect high frequency component. However, when the watermark coefficient is embedded to the high frequency part, the watermark coefficient should be lost after data compression because high frequency component is spatial redundancy.

[0035] Based on frequency codebook concept, we propose a new approach to realize the watermarking system. As a watermarking coefficient W_a is to be embedded, its vector can be found from codebook. The coefficient matrix in (1) is treated as a codebook content. So the codebook is a set of picture coefficients. With coefficient-by-coefficient searching, we can find the minimum differential value between watermarking coefficient and codebook coefficient after n1×m1 points compared, which is given by
(Diff)_min=Min(W_a−F_b), F_bεF_u1v1.  (14)
where Min is minimum value search function. The watermarking coefficient is matched the codebook coefficient by minimum difference. The relative coordinate in matrix (1) can be recorded as a vector. To embed the watermarking information, the watermarking coefficient is rather than the original picture coefficient with
[F_b]_εDiff(min)=W_a,  (15)
where [F_b]_εDiff(min) is corresponding to the vector location of minimum difference. By the same way, the next watermarking coefficient is processed. The relative coordinate also requires to be recorded for each coefficient. Anyway, when the codebook coefficient has replaced by one watermarking coefficient in the previous search, the coefficient is not changed again for the next watermark coefficient processing. Totally, there are n2×m2 watermarking coefficients to be embedded. Finally, we can attain the relative vector according to the coordinate location from each watermark coefficient. Hereafter, the vector is named as W_a(m,n) to denote the coefficient W_a located on (m,n) coordinate. The W_a(m,n) is an import-nt information to restore watermark. So W_a(m,n) can be treated as a privacy key (PK) [22] that is defined by
PK={M1,M2 . . . Mn}, Mx⊂W_a(m,n), x=1 to n2×m2,  (16)
PK is a set of vector for watermarking information.

[0036] After the embedding process, the transform coefficient of original picture involves the watermarking coefficient. We get the new coefficient matrix with

[0037] $\begin{array}{cc}{\tilde{F}}_{\mathrm{u1v1}}={\left(\begin{array}{c}{F}_{00}{W}_{31}{F}_{02}{F}_{03}{W}_{12}{F}_{05}\cdots \\ W_{21}{W}_{35}{F}_{12}{F}_{13}{W}_{14}{F}_{15}\cdots \\ F_{20}{W}_{05}{W}_{62}{W}_{33}{F}_{24}{W}_{02}\cdots \\ \cdots \end{array}\right)}_{\mathrm{u1}\times \mathrm{v1}},& \left(17\right)\end{array}$
where some coefficients have been replaced by watermarking coefficients. Finally, the frequency coefficients are converted into spatial domain using inverse transform with

[0038] $\begin{array}{cc}{\tilde{f}}_{\mathrm{jk}}^1=\mathrm{IDCT}\left({\tilde{F}}_{\mathrm{u1v1}}\right),& \left(18\right)\end{array}$
{tilde over (f)}_jk¹ denotes the composite data in the first layer output. The embedding procedure of the proposed algorithm is illustrated in FIG. 3.

[0039] The procedure of extracting operation is an inverse operation of the embedding one. As receiving the composite data, we only need the key parameter rather than original data to extract watermark. Since the key is a secret data, we need use the same key both of the transmitter and receiver, as shown in FIG. 4. FIG. 5 indicates the processing step for watermark restoration. When the composite data is received, the data should be transformed by DCT since the watermarking information is hidden on the frequency domain. So we have

[0040] $\begin{array}{cc}{\tilde{F}}_{uv}=\mathrm{DCT}\left({\tilde{f}}_{\mathrm{jk}}^1\right)n1\times m1.& \left(19\right)\end{array}$
Using the privacy key, we could find the watermark coefficient from codebook. Then each coefficient is sequentially extracted according to the privacy key and the codebook content. Then the watermark coefficient matrix Ŵ_uv can be reconstructed. The reconstructed watermark data could be attain from inverse transform of Ŵ_uv with
ŵ_xy=IDCT(Ŵ_uv)_n2×m2  (20)

[0041] The watermarking information is hidden into the composite data and its privacy key. In order to increase security, we propose the second layer processing to hide the privacy key to enhance the communication security. Since we have used the frequency domain processing in the first layer, in order to avoid the frequency spectrum aliasing, we employ spatial domain processing consisting of the encryption approach in the second layer.

[0042] The encryption approaches had been used in the past twenty years. As the secret data is encrypted, the output becomes a scrambled data by predetermined key. The attacker can easily detect the data whether or not is encrypted. Since the computing power increases very fast today, the complex encryption system also can be de-encrypted by using statistical analysis. Although the watermarking system can efficiently avoid the attackers' detection, the security level is low. Once the watermark is detected, the attacker can be easy to extract the secret data. Therefore, we develop a mixing system with the encryption consisting of watermark system. The basic structure is shown in FIG. 6. The encryption can increase the security level for watermark. And watermarking can protect the encryption to be detected.

[0043] In our watermarking system, the privacy key is treated as a secret information. In order to increase the security level, the privacy key can be re-permuted by using conventional encryption methods, such as DES. As the key is encrypted by the encryption method, we have the new PK (NPK) from
NPK=Encryp (PK).  (21)
The encryption approach can provide high security to protect the privacy key. In order to avoid the encryption operation to be detected, the second layer hidden is employed.

[0044] To enhance security, the new PK can be further hidden into the composite data using spatial domain processing to avoid attackers' detection. One has simple and efficient method, the key is considered to embed the LSB bit of pixel in composite data, then we have

[0045] $\begin{array}{cc}{\mathrm{jk}}_2^{}={\left({\tilde{f}}_{\mathrm{jk}}^1\right)}_{\mathrm{LSB}}\leftarrow {\left(\mathrm{NPK}\right)}_{\mathrm{Bit}},& \left(22\right)\end{array}$
where

[0046] ${\tilde{f}}_{\mathrm{jk}}^2$
is the second layer composite data. The NPK data use bit-by-bit to insert the LSB of

[0047] ${\tilde{f}}_{\mathrm{jk}}^1$
from left-to-right and top-to-bottom sequentially. The first layer consists of the second layer with encryption and spatial domain processing is shown in FIG. 7. The decoding system block is illustrated in FIG. 8. As we receive

[0048] ${\tilde{f}}_{\mathrm{jk}}^2,$
the LSB is extracted to attain the key information. After de-encryption, the privacy key can be re-restored. According to the privacy key and

[0049] ${\tilde{f}}_{\mathrm{jk}}^2,$
we can reconstruct the watermark data.

[0050] As the composite data size is m1×n1, we have m1×n1 bits space to embed the key information. The coordinate resolution (m,n) presents each watermark coefficient vector, then the watermarking data size m2×n2 can be determined by

[0051] $\begin{array}{cc}\frac{m1\times n1}{m+n}\ge \mathrm{m2}\times \mathrm{n2}.& \left(23\right)\end{array}$
As the key information is embedded into LSB bits of each pixel, the data quality degrades very small. Moreover, the privacy key has been encrypted, to detect the watermarking information becomes very difficult. Thus the security level becomes higher as double hidden procedure is used. In fact, this watermarking system is the mixing process of the frequency and spatial domain hidden. In first layer, the frequency codebook watermark is employed using the DCT domain. And the privacy key is scrambled using the encryption approach consisting of spatial processing in the second layer.

[0052] Currently, JPEG compressor has been widely used to reduce the data size. However, most of the watermark data is discarded after JPEG processing as well. In order to overcome this drawback, a high robustness algorithm for JPEG processing is invented. In the JPEG compressor [12], the data is partitioned into 8×8, and then is transformed by DCT processing. These DCT coefficients are quantized using a particular quantization table, which can be expressed as

[0053] $\begin{array}{cc}{\hat{F}}_{uv}=\frac{{\mathrm{DCT}\left({\tilde{f}}_{\mathrm{jk}}\right)}_{8\times 8}}{Q_{\mathrm{uv}}},& \left(24\right)\end{array}$
where Q_uv is the quantization level that is dependent on the u and v component, {tilde over (f)}_jk is a composite data that is attained from (8), and {circumflex over (F)}_uv is the final quantized coefficient. For RLC/VLC package, the coefficient {circumflex over (F)}_uv should be truncated into an integer. In fact, the LSB bit of each coefficient is not exact after the truncation processing. Thus the compression performance is not changed too much as the privacy key information is embedded into LSBs of non-zero coefficients. With this concept, we first search all non-zero coefficients. Then the LSB of non-zero coefficient is modified by one-bit of the privacy key, which is given by

[0054] $\hspace{1em}\begin{array}{cc}\{\begin{array}{cc}\mathrm{If}& \left({\hat{F}}_{\mathrm{uv}}\right)\mathrm{is}\mathrm{odd},{\mathrm{then}\left({\hat{F}}_{\mathrm{uv}}\right)}_{\mathrm{LSB}}=0,{\mathrm{as}\left(\mathrm{Key}\right)}_{\mathrm{bit}}=0\\ \mathrm{If}& \left({\hat{F}}_{\mathrm{uv}}\right)\mathrm{is}\mathrm{even},{\mathrm{then}\left({\hat{F}}_{\mathrm{uv}}\right)}_{\mathrm{LSB}}=1,{\mathrm{as}\left(\mathrm{Key}\right)}_{\mathrm{one}\mathrm{bit}}=1,\mathrm{as}{\hat{F}}_{\mathrm{uv}}\ne 0\\ \mathrm{Else}& {\left({\hat{F}}_{\mathrm{uv}}\right)}_{\mathrm{LSB}}\mathrm{No}\mathrm{Change}\end{array}& \left(25\right)\end{array}$
The information of the privacy key is sequentially inserted into the LSB location of each non-zero coefficient with bit-by-bit approach. Since only LSBs of non-zero DCT coefficients are modified, the compression ratio is not affected.

[0055] FIG. 9 illustrates the privacy key embedded into non-zero coefficients on the JPEG encoder. FIG. 10 illustrates the JPEG decoder system block for the watermark data extracting. From the JPEG file, the composite data is reconstructed after JPEG decoder. Simultaneously, the privacy key is extracted from each non-zero coefficient. Then the composite data is transformed into DCT domain. According to the privacy key, the coefficients of the watermark data can be extracted. Finally, the watermark data can be restored from inverse DCT processing.

[0056] From the above mentions, how much the key information embedded has to be counted. The total bit of the key information is n2×m2×log₂(n1×m1) since there are n2×m2 keys and each key with log₂(n1×m1) bits. After JPEG processing, the number of non-zero coefficients (NNZC) in the full frame is computed by

If

[0057] ${\hat{F}}_{\mathrm{uv}}^i\ne 0,$
then NNZC=NNZC+1, where i=1 to (n1/8)×(m1/8), u,v=0 to 7 (26), where

[0058] ${\hat{F}}_{\mathrm{uv}}^i$
denote the quantized coefficient at the (u,v) location for the i^th block, and the composite data is split into (n1/8)×(m1/8) blocks as a block size is 8×8. To embed the key information completely, the following equation
NNZC≧n2×m2×log₂(n1×m1),  (27)
need be satisfied. Otherwise, some key information would be discarded, and the extracting quality will degrade accordingly. In fact the NNZC becomes smaller after quantization. Eq. (27) is seldom satisfied in practical case, except the watermark data size is further reduced or the source data size is further enlarged, but the hiding system shall become no efficiency. For practical applications, we present three scanning approaches as below.

[0059] Since DCT transformation has a progressive feature, each coefficient implies one spatial resolution. The watermark data can be restored using only a few DCT coefficients. The sequential procedure is shown in FIG. 11, where the key information is scanned to insert JPEG bit-stream with block-by-block processing. Until all non-zero coefficients are completely processed, the inserting procedure is stopped. Because the amount of the key information is much larger than that of non-zero coefficients, the extracting quality is not good generally. Intuitively, we can increase the number of non-zero coefficients to improve the data quality, but this scheme will reduce the compression ratio. Instead, the high-efficiency scanning styles are presented.

[0060] Because most of the data energy is compacted into the low frequency band in the DCT domain, the key information located at the low frequency area is first considered to embed. Based on a sub-band concept the coefficients can be split into LL, LH, HL and HH bands. In order to keep a regular processing flow, only LL band information is imbedded by using the zigzag scan as shown in FIG. 12. The zigzag scan likes as the run length coding within JPEG compressor, the scanning direction is from left-top corner to right-bottom for the LL band only.

[0061] Since the DCT coefficients are independent, the data can be approximately reconstructed from inverse transformation with coefficient-by-coefficient approach. As the coefficient value is larger, its weight is larger to affect the reconstructed result. To improve the data quality, the key position corresponding to a larger coefficient is first inserted. Because the coefficients are random distribution on the codebook, one-bit flag is required to record the current coefficient whether or not to be selected. For LL band processing, there are n2/2×m2/2 bits used to mark the available coordinate. The number of maximum weight coefficient (NMWC) recorded for the key processing can be computed as

[0062] $\begin{array}{cc}\mathrm{NMWC}=\frac{\mathrm{NNZC}-\left(\mathrm{n2}/2\times \mathrm{m2}/2\right)}{{\log }_2\left(\mathrm{n1}+\mathrm{m1}\right)},& \left(28\right)\end{array}$
The processing procedures using the maximum weight scan are:

• • [0063] (a). Pre-computing NNZC and NMWC.
  • [0064] (b). Find the maximum coefficient and record its corresponding key position.
  • [0065] (c) The one-bit flag is set to high, and counter=counter+1.
  • [0066] (d) The next maximum coefficient is processed with repeating (b)–(c), until the counter=NMWC.
    Although we sacrifice one bit space to record the location of maximum weight coefficients, the larger weight coefficients used can improve the inverse transformation result.

[0067] As previously mentioned, we had used two-layer DCT domain hidden. First the DCT coefficients are hidden on the frequency codebook. The codebook vector is treated as a privacy key. Then the privacy key is further hidden into DCT coefficients in the bit stream of JPEG domain. This approach can meet three requirements for the data hiding systems: invisible, robustness and security. The watermark data becomes invisible since its coefficients are embedded with the best match from the codebook content. Our approach can provide a high robustness for JPEG compressing because of the random coefficient distribution over the entire data. With double DCT layer hidden, a high security for the watermark data protection is achieved.