# Robust Image Embedded Watermarking Using DCT and Listless SPIHT
## 3 Proposed Scheme
### Embedding Procedure
#### 3.1.1 Partition of blocks  
The host image is taken as a grayscale image and watermark is a binary image. Initially, the host image is divided into blocks of \(8\times 8\) pixels. The single watermark bit is then embedded in a single block selected. Then the blocks are chosen as random. Figure 1: Watermark embedding process; DCT: discrete cosine transform; CRT: Chinese remainder theorem; SPIHT: set partitioning in hierarchical trees. Step-2 Selection of DCT coefficients  
In order to improve robustness, the preferred choice is to embed the watermark into the most significant coefficients. However, it will degrade the quality of the watermark. If insignificant coefficients are used for embedding, the watermark may be lost during lossy compression. Since proposed scheme use block size \(8\times 8\) pixels, the resulting DCT block is also of the same size. This gives a total of 64 DCT coefficients. We have included both DC and low-frequency AC coefficients for embedding in order to achieve trade-off between quality and robustness. The DC component and the remaining 63 low-frequency AC components are selected as the possible locations for embedding the watermark bits in the DCT domain. Step-3 Zigzag scanning of the DCT coefficients  
After zigzagging the DCT coefficients, one value must be selected. During that selection, randomizing the coefficients is done using a pseudo random generator. Using randomization technique, security and authentication aspects will increase as the value is changing for every execution. During randomization, one of the selected coefficients is chosen and its index is stored as a secret key whenever we execute the code. This feature adds more security to the data while embedding the procedure. Step-4 Arnold transform  
This is a digital scrambling algorithm to randomize the bits of the watermark. It improves the robustness of the digital watermark. In order to increase the security and robustness of watermark, we use Torus automorphism (TA), which could disperse a watermark equally and randomly [41]. Applying TA for scrambling the binary watermark before embedding offers cryptographic protection against intentional reconstruction of watermark [39]. Further, the key utilized in the TA permutation procedure for scrambling the watermark is also required during the inverse TA permutation (descrambling) procedure. The TA permutation procedure is based on the following equation [39]. \[\left( \begin{array}{c}i*\\ j*\end{array} \right)=\left( \begin{array}{cc}1&1\\ k&k+1\end{array} \right)\times\left( \begin{array}{c}i\\ j\end{array} \right)\text{mod}m, \tag{1}\]  
Equation (1) indicates that each pixel of the watermark pattern at coordinate \((i,j)\) will move to \((i*,j*)\). The \(k\) and \(m\) are the key parameters given by the user. Step-5 Embedding the watermark bits  
After dividing \(8\times 8\) blocks, one watermark bit gets embedded in each of the block. Considering one block at a time, the procedure for embedding the watermark bits is listed as follows:  
* Randomly select an \(8\times 8\) block from host image and apply DCT to the block. * Randomly select a watermark bit from the watermark image in order to embed into the block. * Randomly select a DCT coefficient (DC or one of the AC components) to embed the watermark bit. Let its value be denoted as \(\vartheta\). * Let \(P_{1}\) and \(P_{2}\) be the pair-wise co-prime numbers used in CRT (say, \(P_{1}=38\) and \(P_{2}=107\)) for the DC coefficient. For an AC coefficient, let the values of \(P_{1}=38\) and \(P_{2}=55\). * Find \(E_{1}\) and \(E_{2}\) by applying the inverse CRT to \(\vartheta\). Let the absolute difference between \(E_{1}\) and \(E_{2}\) value be 'z'. * Determine the value \(D=\max(P_{1},P_{2})-1\). * The required condition for embedding watermark bit '1', is \[z\geq D/u,\] (2) where \(u=2\) if \(\vartheta\) is DC coefficient, otherwise, \(u=3\). Apply CRT to modify \(\vartheta\). If the condition is not satisfied, then \(\vartheta\) is modified in step of 8 until the required condition in Equation (2) is satisfied.