# An Improved Reversible Image Transformation Using K-Means Clustering and Block Patching
## 3 The Proposed Method
### Algorithm Explaining of the Proposed Method  
According to Sections 3.1 and 3.2, the framework of image embedding in the proposed method is shown in Figure 2, and the detailed algorithm about stego-image creation is described as follows (Algorithm 1).  
Figure 5: The example of image blocks patching in the first class.  
```
1:A secret image, target image and secret key sk.
2:Decrypt and decompress the sequence to obtain \(SF_{1}\) and \(F_{2}\).
3:for each color channel of transformed images do
4:Divide each color channel of transformed image into non-overlapping \(4\times 4\) blocks.
5:for each block in the image do
6:Calculate the mean and SD of each block.
7:Cluster secret blocks into K classes by K-means clustering according to their SDs, and classify target blocks into K classes according to their SDs, the scanning order and the classes volumes of secret image. Assign a class index for each color channel of two images.
8:for each block in the last (K-T)-classes do
9:Match image blocks having same class index.
10:Shift pixel values with Equations (3)-(5) and (7), and rotate each block with the optimal angel.
11:Record the \(LM\), \(\Delta u^{\prime}=2|\Delta u|/\lambda\) and \(\vartheta\) as the parameters for restoring the image.
12:Replace the target image blocks with the corresponding transformed blocks in the last (K-T)-classes, and generate the composite image.
13:Compress the AI \(F_{1}\), which brings from the last (K-T)-classes transformation, and divide them into \(BF_{1}\) and \(SF_{1}\).
14:for each block in the first T-classes do
15:Distribute a class index \(\alpha_{\beta}\) to these blocks of secret and composite images by \(BF_{1}\), then patch the \(\alpha_{\beta}th\) secret image blocks into current position of composite image to hide \(BF_{1}\).
16:Shift pixel values with Equations (3)-(5) and (7), and rotate patched blocks with the optimal angel.
17:Compress new parameters including \(LM\), \(\Delta u^{\prime}=2|\Delta u|/\lambda\) and \(\vartheta\) as \(F_{2}\).
18:Replace the target image blocks with the corresponding transformed blocks.
19:Combine three color channels to generate the final transformed image.
20:Combine \(SF_{1}\) and \(F_{2}\) to obtain AI, and use secret key sk to encrypt the information, then embed the encrypted sequence into the transformed image by RDH method.
21:return The stego-image.
```  
**Algorithm 2 Secret image recovery**  
And then the processing of secret image recovery can be described as follows (Algorithm 2):  
```
1:A stego-image and secret key sk.
2:A secret image.
3:Extract the encrypted sequence and recover the transformed image by RDH method.
4:Decrypt and decompress the sequence to obtain \(SF_{1}\) and \(F_{2}\).
5:for each color channel of transformed images do
6:Divide each color channel of transformed image into non-overlapping \(4\times 4\) blocks.
7:for each block in the image do
8:Calculate the mean and SD of each block.
9:Obtain class index A according to \(F_{2}\), and classify the transformed blocks into K classes by their SDs and class index A, then generate \(BF_{1}\), class index SC and B.
10:for each block in the first T-classes do
11:Rotate the block in the reverse direction and shift pixel values according to \(F_{2}\).
12:Rearrange the transformed blocks in the first T-classes to generate the composite image by the mapping relation between class indexes A and SC.
13:Combine \(BF_{1}\) and \(SF_{1}\) to obtain \(F_{1}\).
14:for each block in the last (K-T)-classes do
15:Rotate the block in the reverse direction and shift pixel values according to \(F_{1}\).
16:Reassign the transformed blocks in the last (K-T)-classes by the mapping relation between class indexes A and B.
17:return The original secret image.
```  
**Algorithm 3** Secret image recovery