# An Improved Reversible Image Transformation Using K-Means Clustering and Block Patching
## 3 The Proposed Method
### Image Blocks Matching of the Last (K-T)-Classes  
The image blocks matching for the last (K-T)-classes is described as follows:  
Firstly, cluster all SDs of secret blocks into K classes by a traditional clustering method such as K-means, and sort the last (K-T)-classes in ascending order for \(K-T+1<i<j\leq K\).  
Secondly, classify the target blocks with the classes' volumes of secret image, so that each target class has a same volume with the corresponding secret class. Suppose the \(\alpha\)th secret class contains \(n_{\alpha}\) image blocks, where \(K-T+1\leq\alpha\leq K\). Then, the first \(n_{K-T+1}\) target blocks are divided into the first class, the subsequent \(n_{K-T+2}\) target blocks are divided into the second class, and so on, until the \(Kth\) class.  
Finally, distribute a class index \(\alpha_{\beta}\) to each block, where \(\alpha_{\beta}\) is the \(\beta th\) block of the \(\alpha th\) class and \(1\leq\beta\leq n_{\alpha}\). And the \(\alpha_{\beta}th\) secret blocks should be replaced to \(\alpha_{\beta}th\) target blocks, and the initial composite image is generated.  
In order to explain the process of the last (K-T)-classes, suppose \(K=3\) and \(T=1\), a simple example of block matching in last 2-classes are shown in Figure 4.  
The secret tiles are divided into three classes here:  
(1) \(SDs\{0,1,2,3\}\) belong to the class 1, they are labeled as \"white\";  
(2) \(SDs\{4,5,6\}\) belong to the class 2, they are labeled as \"gray\";  
Figure 4: An example of image blocks matching in last 2-classes.  
Figure 3: The numbers distribution of image classes when \(K=10\).  
(3) \(SDs\{7,8,9\}\) belong to class 3, they are labeled as \"black\".  
Next, cluster target blocks based on the classes' volumes of secret images, then the class index of block can be obtained by scanning SDs classes in the raster order.  
For example, in secret image A, the second secret block is the first of class 1 that is assigned as \(1_{1}\), the seven block is the second of class 1 that is assigned as \(1_{2}\),..., and so on, a one-to-one map between secret and target blocks will be created. The \(\alpha_{\beta}\)th secret blocks in last 2-classes can be transformed to \(\alpha_{\beta}\)_th_ target blocks and replace them, while the pixel values of the class 1 are changed to 0, and they will be patched in Section 3.2. Finally, the composite image SC is generated.  
The SC has a similar texture pattern with the target image because it has pretty big SDs with the secret image, which results in the SC having a similar appearance to the target image while hiding the secret image. Moreover, the secret image can be recovered using the SC.  
To recover the secret image from the composite image, the receiver only needs to know the class index A. According to the table in Figure 4, the receiver will know how to rearrange the composite blocks to restore the secret blocks. For example, the first block of the composite image should be put back to position 4, and the fifth block should be put back to position 1, as indicated in the table.