# Computationally Efficient Robust Color Image Watermarking Using Fast Walsh Hadamard Transform
## 2 Walsh Hadamard Transform and Related Works  
Walsh Hadamard Transforms (WHT) are generalized version of Fourier transforms. The transformation matrix of the WHT consists of only value of \(1\) and \(-1\) which directly implies that the calculation of Walsh Hadamard Transform of an image consists of only real additions and subtractions [10]. The elementary matrix of Walsh Hadamard Transform is \(\left[ \begin{array}{cc}1&1\\ 1&-1\end{array} \right]\). Higher order matrices (\(H_{N}\)) are calculated as the kronecker product (\(\times\)) of lower order matrices as given below [15]. \[H_{N}=H_{N-1}\times H_{1} \tag{1}\]  
\[H_{N}=\left[ \begin{array}{cc}H_{N-1}&H_{N-1}\\ H_{N-1}&-H_{N-1}\end{array} \right] \tag{2}\]where \(H_{1}=\left[ \begin{array}{cc}1&1\\ 1&-1\end{array} \right]\). The rows of the Hadamard matrix are orthogonal and the transpose (\(H_{N^{T}}\)), conjugate (\(H_{N^{*}}\)) and inverse of the matrix (\(H_{N^{-1}}\)) are the same. \[H_{N}=H_{N^{*}}=H_{N^{-1}}=H_{N^{T}} \tag{3}\]  
Complexity of calculating the Walsh Hadamard Transform is O(Nlog\({}_{2}\)N) real additions and subtractions. Equations of forward Walsh Hadamard Transform of a one dimensional matrix \(u(m)\) is  
\[U(k)=1/\sqrt{N\sum_{m=0}^{N-1}u(m)\ (-1)^{b(k,m)}}0\leq k\leq N-1 \tag{4}\]  
\(k=k_{0}+2k_{1}+\cdots\cdots+2^{n-1}k_{n-1},\ k_{0},\ k_{1},\cdots,\ k_{n-1}\) are binary values  
\(m=m_{0}+2m_{1}+\cdots\cdots+2^{n-1}m_{n-1},\ m_{0},\ m_{1},\cdots,m_{n-1}\) are binary values  
\[b(k,m)=\sum_{i=0}^{n-1}k_{i}m_{i}\]  
The two dimensional transform is found out by calculating the one dimensional WHT of the rows first followed by WHT of the columns. The transformation matrix can be Walsh ordered or Hadamard ordered. Walsh ordered matrix has elements arranged in increasing order of frequency (sequency). Sequency is the more generalized 24 term for frequency which is the number of sign changes among the elements of a row in the matrix. But Hadamard matrix has elements arranged in hadamard order (0, 4, 6, 2, 3, 7, 5, 1). The inverse and forward transformations are identical except for a scalar multiplication factor. WHTs are computationally very efficient and hardware implementations are cost effective as both forward and inverse transformations can be done through the same block which reduces the space, complexity and cost considerably [11; 14]. Most of the energy is contained in less than 50% of the coefficients yielding good energy compaction properties and high resiliency towards low quality compression. So WHT turns out to be the best choice for robust, low cost implementations [2; 11]. Only few numbers of researchers worked on FWHT based algorithms. [PERSON] et al. combined the image decomposition method, Singular Value Decomposition (SVD) and FWHT and used the entropy (measure of randomness of the pixel values) of the blocks to decide the block to embed the watermark [14]. In [16], [PERSON] et al. developed a robust watermarking algorithm, but computationally, it takes more time as both watermark and original image are to be frequency transformed. The watermark is embedded in the coefficients selected by the security key. Moreover the DC coefficients of each block should be stored in a separate file. Some of the researchers used complex Hadamard transform. [PERSON] et.al. have applied FWHT on the watermark and has added to the DC coefficients of the host image and they could achieve good visual perception [17]. In [18], the authors tried to add the watermark in the Hadamard coefficients. But no attack analysis is performed instead they studied the effect of scaling factor on the embedding process. In [19], [PERSON] et.al. proposed an illumination based watermarking technique which used a combination of FWHT and DCT. With this technique they were able to attain 100% accuracy and robustness against compression. In [9] complex Hadamard transform is used and the watermark is embedded in the phase of the transform coefficients. [PERSON] et al. used spread spectrum based watermarking using FWHT.