## 3 Proposed Scheme
### The First Layer of Data Embedding Process  
The first layer of data embedding in the proposed scheme is based on the side-match evaluation. Since the mapping codeword pair defined between two clusters are dissimilar enough, de-clustering by switching between a mapping codeword pair leads to an abnormal side-match value. The embedding rules are quite simple. The cluster labels '1' and '0' are exploited to indicate the embedded binary bit. When the label of current processing index is matched with the binary bit to be embedded, it is kept unchanged; when they are not matched, the index is switched to its counter codeword according to the predefined mapping. In this way, the secret data can be embedded without lengthening the index code. To execute the side-match evaluation, the indices in the first row and the first column of the index table are treated as the seed indices and kept unchanged. The first layer of data embedding is applied to the residual indices. Note that the formal (real) VQ image blocks are not always 'normal' under side-match evaluation. In such abnormal circumstance, the reserved codewords, i.e., the head and rear codewords, take over. When '0' is to be embedded, the head codeword is inserted; when '1' is to be embedded, the rear codeword is inserted. The insertion of a reserved codeword indicates two things: (1) the secret bit is as it represents for, and (2) the current image block is abnormal, and its index is pushed behind. Knowing the information of an abnormal situation, the actual index of the current image block still can be embedded with a secret bit according to the same rule. Thus, an abnormal image block leads to a double code length; however the embedded data is also doubled. In addition, the binary secret data is stream encrypted before embedding. The algorithm for the proposed secret data embedding scheme is summarized as Algorithm 1. Figure 7: Illustration of the side-match evaluation. ```
Input: cover image \(I\), specialized codebook \(B=\{CW_{i}|i=1,2,\ldots,n-2\}\), codeword mapping function \(M\), secret data \(S\). Output: 1-st stego index table \(\hat{T}\). 1: Divide the cover image into mutually exclusive blocks sized \(w\times h\). 2: Compress the cover image \(I\) into index table \(T\) according to codebook \(B\). 3: Encrypt the secret data \(S\) by a stream cipher. 4: For each residual index \(v_{j}\in T\),
5: Find the cluster label \(L(v_{j})\). 6: If \(d_{t}<d_{f}\),
7: Retrieve a secret bit \(b\) from \(S\). 8: If \(L(v_{j})=b\), record \(v_{j}\) to \(\hat{T}\); else, record \(v^{\prime}_{j}=M\Big{(}v_{j}\Big{)}\) to \(\hat{T}\). End
9: Else
10: Retrieve a secret bit \(b_{1}\) from \(S\). 11: If \(b_{1}=0\), record \(CW_{0}\) to \(\hat{T}\); else record \(CW_{n-1}\) to \(\hat{T}\). End
12: Retrieve a secret bit \(b_{2}\) from \(S\). 13: If \(L(v_{j})=b_{2}\), record \(v_{j}\) to \(\hat{T}\); else, record \(v^{\prime}_{j}=M\Big{(}v_{j}\Big{)}\) to \(\hat{T}\). End
14: End
15: End
```  
**Algorithm 1** The first-layer of data embedding for VQ index table. We use three typical examples to demonstrate the embedding process of the proposed data hiding scheme. The first example is shown in Figure 8. The index value is 'CW5' and the secret bit to be embedded is '1'. Since \(d_{t}=d(cw5)<d(cw12)=d_{f}\) and the cluster label matches with the secret bit, i.e., \(L(cw5)=1=b\), the secret bit is embedded without any modification. The second example is shown in Figure 9. The index value is 'CW7' and the secret bit to be embedded is '0'. Again, this is a normal image block according to the side-match evaluation. Since the cluster label mismatches the secret bit, i.e., \(L(cw7)=1\
eq 0=b\), the secret bit is embedded by recording its counterpart 'CW14' obtained through the pre-defined mapping between clusters. The third example is shown in Figure 10. In this case, the side-match evaluation, \(d_{t}=d(cw11)>d(cw4)=d_{f}\), indicates the occurrence of an abnormal block. Since the secret bit to be embedded is '1', the rear codeword 'CW15' is recorded.