Robust Digital Audio Watermarking Based on SVD and Modified Firefly Algorithm

Show more

1. Introduction

The term digital watermarking [1] , first came into existence in 1993 when Tirkel presented watermarking techniques to hide the watermark data in the image. Due to the rapid growth in computer and communication industry, cost effective and popular digital recording and storage devices made it possible to copy, and have unauthorised access of the original digital multimedia contents. Digital watermarking has evolved as a solution to these problems of copyright protection, authorization, illegal modifications and distributes the data in an effortless ways without having legal permission of the author. Digital watermarking provides a way to imperceptibly embed digital signal or information into the digital multimedia content. The watermarking is done by embedding a watermark signal into the host data for the purpose of copyright protection, access control. Broadcast monitoring etc. A watermark can be a signal, a tag or a label. The embedding process should be in such a way that the watermark image can be extracted from the watermarked audio without any perceptible loss of quality of the host audio. Watermarking techniques can be classified according to domain, visibility and transparency.

According to domain, watermarking is classified as spatial domain and transform domain [2] . In spatial domain, watermark is embedded directly into the original audio. In transform domain, the watermark is embedded by modulating the coefficients in a transform such as discrete cosine transforms (DCT), discrete Fourier transform (DFT), discrete wavelet transform (DWT). The transform domain provides more robust and secure watermarking which has attracted many researchers to work in this domain. The main advantage of working in the transform domain is that when the audio is inverse transformed the watermark is distributed irregularly over the host audio which makes the attacker hard to modify and copy the host audio.

The singular value decomposition (SVD) [3] is a kind of transform domain technique. SVD divides a N × N matrix into three matrices:

$A=US{V}^{\text{T}}$

where S is an N × N diagonal matrix. U and V^{T} are N × N orthogonal matrices, whose column vectors are u_{i}’s and v_{i}’s, respectively. The important property of the singular values is that any modifications done on these values do not show any change in the respective matrix. Based on this property, the singular values are modified with the singular values of the watermark image. An N × N image can have N singular values that reveal various tolerances to modifications [4] . As there is no idea of the sensitivity of the image to various scaling factors. Therefore, an optimization algorithm [5] is needed to obtain optimum scaling factors [6] that can give highest possible robustness and transparency. For this purpose, firefly algorithm [7] is used, which is a metaheuristic algorithm for optimization problems. The algorithm is based upon the flashing behaviour of fireflies [8] . Randomly generated solutions are treated as fireflies. It has two basic components-brightness and attractiveness. Attractiveness is directly proportional to the brightness but decreases with distance. Brightness is computed on the basis of an objective function. Thus the basic rule is that the brighter firefly will attract the more fireflies and if no such brighter firefly is present then the firefly will move in random direction [9] . This random movement may decrease the brightness depending on direction. As a consequence the overall performance of the algorithm is decreased in that particular iteration. Now if we change this property of random movement by moving in a particular direction in which its brightness increases which do not reduce the performance in that iteration. If such direction does not exist then the firefly will remain at its current position [10] . Hence the modified singular values (SV) by the watermark values will be more robust and secure. Also it will enhance the overall watermarking scheme and decrease the trade-off between robustness and transparency and less vulnerable to various attacks. The paper is organised in the following manner: Section II elaborates the description of Singular Value Decomposition (SVD); Section III is for Modified Firefly algorithm. The proposed model is being given in Section IV. Section V gives the conclusion of the paper and the proposed model.

2. Singular Value Decomposition (SVD)

Singular value decomposition (SVD) comes under the category of transform domain technique of digital audio watermarking, which is akin theory of diagonalizing of symmetric matrix in linear algebra. SVD decomposes a matrix into three sub-parts: U, S and V. U and V are the orthogonal matrices while S is the diagonal matrix. These diagonal elements are called the singular values of the corresponding matrix. This decomposition can be illustrated as:

$A=US{V}^{\text{T}}$ (1)

where A is a matrix of dimension m × n. U is made up of the eigen vectors of AA^{T} and is called left singular vector. V is formed by the orthogonal vectors of A^{T}A and is called right singular vector. S contains the square roots of either U or V in descending order in its diagonal being a diagonal matrix. Let the rank of the matrix A be r (r < n), then the diagonal elements of S will follow the following relation:

${\alpha}_{1}\ge {\alpha}_{2}\ge \cdots \ge {\alpha}_{r}\ge {\alpha}_{r+1}\ge {\alpha}_{r+2}\ge \cdots \ge {\alpha}_{n}$ (2)

Now A can be derived as:

$A={\displaystyle {\sum}_{i=1}^{r}{\alpha}_{i}{u}_{i}{v}_{i}}$ (3)

where
${\alpha}_{i}$ is the diagonal element of matrix S at i^{th} position.

The singular values give the luminance of the audio at each i^{th} position, whereas singular vectors give the geometrical property. The most important property of SVD is that if any changes are applied to the singular values then will be no significant changes seen on the given matrix. Using this property the watermark image is modified by applying change in its singular values and embedded into the singular values of the host audio without getting any distortions and any perpetual change.

Properties of SVD:

1) Singular values preserve the energy as well as prevent the image from attacks.

2) The matrix in SVD can be variable. It need not be always scalar.

3) The singular values α_{i} are unique in the matrix S.

4) The rank of the matrix is given by the non-zero elements in the diagonal matrix, S.

3. Modified Firefly Algorithm

Firefly algorithm [7] is a metaheuristic algorithm for optimization problems. The algorithm is based upon the flashing behaviour of fireflies. Randomly generated solutions are treated as fireflies. It has two basic components-brightness and attractiveness. Attractiveness is directly proportional to the brightness but decreases with distance. Brightness is computed on the basis of an objective function. Thus the basic rule is that the brighter firefly will attract the more fireflies and if no such brighter firefly is present then the firefly will move in random direction [9] .

In firefly algorithm, the brightest firefly is a firefly with current global best solution and it will move in random direction if no brighter firefly is found. This random movement may decrease the brightness depending on direction. As a consequence the overall performance of the algorithm is decreased in that particular iteration.

It is proved in elementary physics that intensity of light is inversely proportional to the square of the distance from the source to the object. Therefore we can formulate the light intensity, I in terms of distance, r as follows:

$I\left(r\right)={I}_{0}{\text{e}}^{-\lambda r}$ (4)

where λ is the light absorption coefficient and I_{0} is the light intensity at the source point.

For the sake of simplicity this can be written as:

$I\left(r\right)=\frac{{I}_{0}}{1+\lambda {r}^{2}}$ (5)

Likewise, attractiveness can also be derived:

$A\left(r\right)=\frac{{A}_{0}}{1+\lambda {r}^{2}}$ (6)

where A_{0} is the attractiveness at r = 0.

Steps of implementation of firefly are as follows:

1) Generate a solution set randomly.

2) Find the intensity for each of the generated firefly.

3) The movement of the firefly will be done in the direction of brighter firefly and if no such direction is found then the firefly will move in random direction.

4) Now, solution is updated.

5) End the process if termination condition holds true; else go back to step 2.

The main drawback of the FA is that if there is no such direction in which the brightness increases, it moves the firefly randomly, and this random movement may sometimes cause degradation in the performance of FA because brightness may reduce in some random direction. Now if we change this property of random movement by moving in a particular direction in which its brightness increases then it will not degrade the performance in that iteration. If such direction does not exist then the firefly will remain at its current position. This is the Modified Firefly algorithm.

The movement of the firefly will be according to the following relation:

$d:=d+\alpha \mu $ (7)

where, d is the location of the firefly, µ is the chosen direction in which movement is to be done and α is the step length selected randomly.

Attractiveness of a firefly can be calculated as:

${A}_{0}=\frac{{{I}^{\prime}}_{0}}{{I}_{0}}$ (8)

where A_{0} is the attractiveness of a firefly say, i at r = 0,
${{I}^{\prime}}_{0}$ is the intensity of firefly i and I_{0} is the intensity of firefly j.

4. Proposed Watermarking Model

This paper proposes a SVD [11] based watermarking technique which uses multiple scaling factors (MSF) to embed the watermark image into host audio. These MSFs are generated using the optimization algorithm, Modified Firefly Algorithm (MFA) [12] . The embedding and extraction process by applying block by block SVD and combining it with the MFA is described in the following sections in the form of flow charts and then the conclusion is derived with the help of experimental results.

1) Steps of embedding watermark:

The steps of embedding the watermark image into the host audio are shown in Figure 1.

Step1: Divide the host audio (H) and watermark image (W) into n non overlapping frames of size m × m.

Step 2: Apply SVD on these blocks of host audio (H_{i}) and watermark image (W_{i}) simultaneously.

$\left[{U}_{i}{S}_{i}{V}_{i}\right]=\text{SVD}\left({H}_{i}\right)$ (9)

$\left[{U}_{wi}{S}_{wi}{V}_{wi}\right]=\text{SVD}\left({W}_{i}\right)$ (10)

Step 3: Embed the singular values of the watermark image (S_{wi}) into the singular values of host audio (S_{i}) using the following formula:

${{S}^{\prime}}_{i}=\{\begin{array}{l}{S}_{i}+{\rho}^{*}{S}_{wi},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{if}\text{\hspace{0.17em}}{S}_{i}\left(x,y\right)<{S}_{wi}\left(x,y\right)\\ {S}_{i}-{\rho}^{*}{S}_{wi},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{otherwise}\end{array}$ (11)

Step 4: Do inverse SVD on the sub-blocks to regain the H_{i}:

${H}_{i}={U}_{i}{{S}^{\prime}}_{i}{V}_{i}$ (12)

Step 5: Recombination of the blocks is performed to get the watermarked image with size equal to the host image.

2) Extraction process of watermark

In the extraction process watermark image is being extracted from the watermarked audio (H_{w}), which is produced as a result of the embedding process. This extraction procedure is described below in Figure 2 with the help of flow chart.

Step 1: Divide the produced watermarked image (H_{w}) into n non overlapping blocks (H_{iw}) of equal size.

Figure 1. Flow chart of watermark embedding algorithm.

Figure 2. Extraction process.

Step 2: Perform SVD on each sub-block:

$\left[{U}_{fi}{S}_{fi}{V}_{fi}\right]=\text{SVD}\left(fi\right)$ (13)

Step 3: Singular Values of the watermark image is extracted using:

${{S}^{\prime}}_{wi}=\{\begin{array}{l}\frac{{S}_{i}-{S}_{fi}}{\rho},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{if}\text{\hspace{0.17em}}{S}_{i}\left(x,y\right)>{S}_{fi}\\ \frac{{S}_{fi}-{S}_{i}}{\rho},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{otherwise}\end{array}$ (14)

Step 4: Now watermark image is recovered from the watermarked image by:

${{W}^{\prime}}_{i}={U}_{wi}^{*}{S}_{wi}^{*}{V}_{wi}^{\text{T}}$ (15)

Step 5: To get the original size and dimension of the watermark image, the recovered blocks are recombined.

5. Proposed Algorithm

Let the host audio be H and watermark image be W of size N × N, then the following are the steps of the algorithm by which this model works:

Step 1: n no. of fireflies are generated randomly using MFA.

Where $n=\left[{\rho}_{1},{\rho}_{2},{\rho}_{3},\cdots ,{\rho}_{n}\right]$

Step 2: for each generated firefly, ρ, perform the following operations:

1) Apply embedding process discussed in the previous section on the host audio and watermark image.

2) Induce r number of attacks on the watermarked audio (Hw); hence attacked audio (Hw') are generated.

3) Extract the watermark from the host audio and attacked images using extraction algorithm described above.

4) Compute the PSNR values of the host audio (H), watermarked audio (Hw) and attacked audio (Hw').

5) Compute the objective function (O) of the firefly (ρ) using the objective function below:

$O=\text{PSNR}\left(H,Hw\right)+\text{PSNR}\left(W,H{w}^{\prime}\right)+{\displaystyle {\sum}_{i=1}^{r}\text{PSNR}\left(W,{{H}^{\prime}}_{Wi}\right)}$ (16)

where $\text{PSNR}\left(W,H{w}^{\prime}\right)$ is the peak signal to noise ratio between watermark audio and the watermark extracted from the attacked audio.

Step 3: Now take the maximum value of the objective function to choose the multiple scaling factor which in turn optimizes the trade-off between the imperceptibility and robustness of the watermarking procedure.

6. Implementation Results

To verify the results of above-mentioned technique, we implemented the algorithm in the MATLAB 7.0. The audio file named “in” (Figure 3(a)) used in the experiment is audio signal in the wave format sampled at a rate of 44,100 Hz. Plots of in (host signal) audio signal and its watermarked version are shown in Figure 3(b). The original and extracted watermark without any attack has been shown in Figure 4(a) and Figure 4(b). This value provides good tradeoffs between imperceptibility of watermark and robustness against different attacks [13] .

7. Robustness Test

The following attacks [14] are performed on the watermarked audio signal to test the robustness of our scheme. The audio editing and attacking tools used in the experiment are MATLAB 7.0 and Gold Wave 5.18. The effects of different attacks are shown in Table 1.

(a)(b)

Figure 3. (a) Host audio signal; (b) Watermarked audio signal.

(a) (b)

Figure 4. (a) Binary watermark; (b) Recovered watermark.

Table 1. Effect of different attacks.

1) Additive white Gaussian noise (AWGN):

White Gaussian noise [7] is added to the watermarked audio signal so that the resulting signal has a SNR of above40db.

2) Re-sampling:

The Watermarked signal originally sampled at 44.1 kHz is re-sampled at 22.05 kHz, and then restored by sampling again at 44.1 kHz. Correlation [15] is a measure of similarity of two signals as it depicts the amount by which the signal is deviated from the other signal. Normalized correlation is defined as follows:

$NC\left(wm,w{m}^{\prime}\right)=\frac{{{\displaystyle \sum}}_{i=1}^{M}{{\displaystyle \sum}}_{j=1}^{M}\text{\hspace{0.05em}}W\left(i,j\right)\stackrel{\xaf}{wm\left(i,j\right)}}{\sqrt{{{\displaystyle \sum}}_{i=1}^{M}{{\displaystyle \sum}}_{j=1}^{M}\text{\hspace{0.05em}}\text{\hspace{0.05em}}w{m}^{2}\left(i,j\right)}\sqrt{{{\displaystyle \sum}}_{i=1}^{M}{{\displaystyle \sum}}_{j=1}^{M}\text{\hspace{0.05em}}\stackrel{\xaf}{w{m}^{2}\left(i,j\right)}}}$

The bit error rate (BER) is used to measure the robustness of our scheme:

$\text{BER}\left(wm,\stackrel{\xaf}{wm}\right)=\frac{\text{Errorbits}}{\text{TotalBits}}$

3) Low-pass Filtering:

The low-pass filter [7] [8] used is a second-order Butterworth filter with cut-off frequency 11,025 Hz.

8. Conclusion

Robust watermarking scheme can provide better authentication and security of the digital audio. In this rapid growing era of technology there are many tools available which can easily modify or extract the watermark from an audio, hence it is a necessary thing to have more robust watermarking scheme which can withheld these attacks and forgeries. This is a new method of robust audio watermarking based on SVD using Modified Firefly Algorithm. Modified Firefly Algorithm is used to employ optimise function that was defined by two conflicting requirements of watermarking i.e. transparency and robustness. The watermark image is embedded into the host audio by modifying the singular values of the host audio. To achieve maximum robustness without losing transparency, modifications are to be done using multiple scaling factors obtained by Modified Firefly Algorithm.

References

[1] Hartung, F. and Kutter, M. (1999) Multimedia Watermarking Techniques. Proceeding of IEEE, 87, 1079-1107.

[2] Liu, F. and Liu, Y. (2008) A Watermarking Algorithm for Digital Image Based on DCT and SVD. In IEEE Congress on Image and Signal Processing, Sanya, Hainan, China, Vol. 1, 380-383.

[3] Lai, C.-C. (2011) A Digital Watermarking Scheme Based on Singular Value Decomposition and Tiny Genetic Algorithm. Digital Signal Processing, 21, 522-527.

https://doi.org/10.1016/j.dsp.2011.01.017

[4] Ghazy, R., El-Fishawy, N., Hadhoud, M., Dessouky, M.M and El-Samie, F. (2007) An Efficient Block by Block SVD Based Image Watermarking Scheme. In Proceedings of the 24th National Radio Science Conference, Cairo, Egypt, 13-15 March 2007, 1-9.

https://doi.org/10.1109/NRSC.2007.371376

[5] Vijaya Durga, K., Mamatha, G. and Hima Bindu, Ch. (2015) SVD Based Image Watermarking with Firefly Algorithm. In International Conference on Computer Communication and Informatics, Coimbatore, India, 8-10 Jan. 2015.

[6] Aslantas, V. (2009) An Optimal Robust Image Watermarking Based on SVD Using Differential Evolution Algorithm. In Optics Communications, 282, 769-777.

[7] Jain, C., Arora, S. and Panigrahi, P.K. (2008) A Reliable SVD Based Watermarking Scheme. adsabs.harvad.edu/abs/2008arXiv 0808.0309J.

[8] Yang, X.-S. and He, X. (2013) Firefly Algorithm: Recent Advances and Applications. International Journal of Swarm Intelligence, 1, 36-50.

https://doi.org/10.1504/IJSI.2013.055801

[9] Chandra, D. (2002) Digital Image Watermarking Using Singular Value Decomposition. In Proceedings of the IEEE 45th Midwest Symposium on Circuits and Systems, Oklahoma State University, USA, Vol. 3, 264-267.

[10] Agarwal C., Mishra A., Sharma A. and Chetty, G. (2014) A Novel Image Watermarking Scheme Using Firefly Algorithm. International Conference on Artificial Intelligence and software Engineering, 430-436.

[11] Lee S., Jang, D. and Yoo, C.D. (2005) AN SVD-Based Watermarking Method for Image Content Authentication with Improved Security. In: Proc. ICASSP05, 525-528.

[12] SurafelLulesegedTilahun and Hong ChoonOng.,(2012) Modified Firefly Algorithm. In Hindawi Publishing Corporation. Journal of Applied Mathematics, 2012, Article ID 467631.

[13] Surekha, P. and Sumathi (2011) Implementation of Genetic Algorithm for a DWT Based Image Watermarking Scheme. ICTACT Journal on Soft Computing: Special Issue on Fuzzy in Industry and Process Automation, 2.

[14] Yuan, Q., Li, C. and Zhong, Y. (2007) Adaptive DWT-SVD Domain Image Watermarking Using a Human Visual Model. Proceedings of the 9th Advanced Communication Technology Conference, 3, 1947-1951.

[15] Kim, B., Choi, J.G. and Min, D. (2003) Robust Digital Water-Marking Method against Geometric Attacks. Real Time Imaging Processing, 9, 139-149.

https://doi.org/10.1016/S1077-2014(03)00020-2