# An Improved Reversible Image Transformation Using K-Means Clustering and Block Patching
## 3 The Proposed Method
### Image Blocks Patching of the First T-Classes  
To embed the AI from the last (K-T)-classes transformation, the AI should be represented as a secret segment, and the image blocks in the first T-classes can be patched according to the secret segment. Before that, the AI can be compressed by the Huffman code method, and is denoted as \(F_{1}\). However, the number of image blocks in the first T-classes is not sufficient to hide \(F_{1}\) through patching image blocks because the length of \(F_{1}\) is very large. Therefore, \(F_{1}\) will be divided into two parts called \(BF_{1}\) and \(SF_{1}\), in which \(BF_{1}\) can be hidden by patching blocks, and \(SF_{1}\) can be embeded by final RDH. But determining the length of \(BF_{1}\) remains a challenge. Suppose the length of secret segment is \(l\), and each block in the first T-classes can be divided into \(M\) categories (\(M=2^{l}\)). We use each block to represent different secret segments. For example, if \(M=4\), the block may be represented secret segments \"00\", \"01\", \"10\" or \"11\". The total number of image blocks in the first T-classes is \(TN=n_{1}+\ldots+n_{T}\), where \(n_{1},\ldots,n_{T}\) is the number of each classes' blocks, respectively. Thus, the length of \(BF_{1}\) is \(l*TN\), and \(\text{BF}_{1}\) should be divided into \(TN\) secret segments and each segment contains \(l\) bits. We calculate the decimal values \(E_{i}(1<i<TN)\) for all segments, and count the frequency \(n_{1},\ldots,n_{M}\) of each \(E_{i}\). Then, we divide the secret blocks in the first T-classes into new \(M\) categories by the frequency \(n_{1},\ldots,n_{M}\), and the secret blocks in each class have the same volume as the corresponding frequency. Suppose the \(\alpha\)_th_ image class contains \(n_{\alpha}\) blocks, where \(1\leq\alpha\leq M\). The first \(n_{1}\) secret blocks with the smallest SDs, the second \(n_{2}\) secret blocks with second-smallest SDs, and so on, until the unmatched secret blocks are divided. Next, distribute a compound index \(\alpha_{\beta}\) to each secret block, where \(\alpha_{\beta}\) is the \(\beta\)_th_ block of the \(\alpha\)_th_ class and \(1\leq\beta\leq n_{\alpha}\). Then, the blank blocks of composite image can be divided into new \(M\) categories by the scanning order of \(BF_{1}\), in which the blocks will be distributed a class index \(\alpha_{\beta}\) according to the decimal values \(E_{i}\) of each secret segment. Finally, the unmatched secret blocks can be patched into composite image, in which the \(\alpha_{\beta}\)_th_ secret block should be replaced to the \(\alpha_{\beta}\)_th_ blank block, and the final transformed image is generated. To explain the process of image blocks patching in the first T-classes, based on the example of Figure 4, block patching in the first class are shown in Figure 5. Assuming \(M=2\) and \(BF_{1}=(0110110)_{2}\), the secret image blocks should be patched to composite image blocks in the first class, which are labeled as \"white\". Firstly, \(BF_{1}\) can be divided into the secret segment \"0\" and \"1\", and we can count that the number of \"0\" is three, and the number of \"1\" is five. Then, according to the number of \"0\" and \"1\", the secret blocks of the first T-classes can be sorted by SDs, and divided into two new categories:  
1. The first-3 image blocks of the ascending sequence belong to class 1; they are labeled as \"red\";
2. The last-5 image blocks of the ascending sequence belong to class 2; they are labeled as \"yellow\". Next, the blank blocks in the composite image can be divided by the scanning order of \(BF_{1}\). For example, the first bit in the \(BF\) is 0. Thus, the first position of unmatched blocks in the composite image belongs to class 1; they are labeled as \"red\". The second bit is 1. Thus the second position of unmatched blocks belongs to class 2; they are labeled as \"yellow\". Then, the new class index \(\alpha_{\beta}\) for the unmatched block can be defined.