# An Improved Reversible Image Transformation Using K-Means Clustering and Block Patching
## 2 Related Work
### Reversible Shift and Rotate Transformation  
After block matching, the transformed image blocks will be shifted to make it as similar as possible to the target image. Let the shifted block \(C\) be a set of pixels \(C=\left\{p_{i}^{\prime\prime},p_{2}^{\prime\prime},\ldots,p_{n}^{\prime\prime}\right\}\); the pixels can be calculated as:  
\[\Delta u=round(u_{B}-u_{A}),\ p_{i}^{\prime\prime}=p_{i}+\Delta u. \tag{3}\]  
To solve the overflow/underflow problem, \(\Delta u\) should be modified as follows. The maximum overflow and the minimum underflow pixel values are denoted as \(OV_{max}\) and \(UN_{min}\) for \(\Delta u\geq 0\) and \(\Delta u<0\), respectively.  
When \(\Delta u\geq 0\):  
\[\Delta u=\left\{\begin{array}{ll}\Delta u+255-OV_{max},&if\ 255-OV_{max}<0\\ \Delta u-U,&if\ 255-OV_{max}\geq 0\end{array}\right.. \tag{4}\]  
or when \(\Delta u<0\):  
\[\Delta u=\left\{\begin{array}{ll}\Delta u-UN_{min},&if\ UN_{min}<0\\ \Delta u+U,&if\ UN_{min}\geq 0\end{array}\right.. \tag{5}\]  
where \(U\) is an adjustable parameter for the balance between the number of overflow and underflow and the distance from the mean value of target image. To reduce the amount of auxiliary information, \(\Delta u\) should be quantized to a little integer.  
\[\Delta u=\left\{\begin{array}{ll}\lambda\times round\Big{(}\frac{\Delta u }{\lambda}\Big{)},&if\ u\geq 0\\ \lambda\times floor\Big{(}\frac{\Delta u}{\lambda}\Big{)}+\frac{\lambda}{2},& if\ u<0\end{array}\right.. \tag{6}\]  
where the quantization step \(\lambda\) must be an even parameter, \(round(\cdot)\) and \(floor(\cdot)\) are integral functions. Then, \(\Delta u^{\prime}=2|\Delta u|/\lambda\) should be recorded as the final auxiliary information, which is embedded into the transformed image, and \(\lambda\) is a parameter to make a trade-off between the amount of auxiliary information and the distance from the mean value of target image.  
Even when modifying the amplitude \(u_{B}-u_{C}\) to the final \(\Delta u\), the overflow/underflow problem may still occur. To solve this problem, the overflow pixels will be truncated back to the range of \([0,255]\), then \(LM=(lm_{1},lm_{2},\ldots,lm_{n})\) can be generated to record the position of overflow/underflow pixels.  
\[lm_{i}=\left\{\begin{array}{ll}-p_{i}^{\prime\prime},&if\ p_{i}^{\prime \prime}<0\\ p_{i}^{\prime\prime}-255,&if\ p_{i}^{\prime\prime}>255\end{array}\right.. \tag{7}\]  
Note that \(LM\) is very small and can be compressed well.  
To further maintain the similarity between the transformed and target images as much as possible, the shifted block \(C\) can be rotated into one of the four angles \(0^{\lx@math@degree}\), \(90^{\lx@math@degree}\), \(180^{\lx@math@degree}\) or \(270^{\lx@math@degree}\). The best angle \(\theta\in\left\{0^{\lx@math@degree},90^{\lx@math@degree},180^{\lx@math@degree },270^{\lx@math@degree}\right\}\) is selected for minimizing the root of mean square error (RMSE) between the rotated block and the target block.  
Thus, the transformed image is generated, and the auxiliary information containing the class index of secret image, quantified difference \(\Delta u^{\prime}\), small overflow/underflow information \(LM\) and rotation angle \(\theta\), which can also be embedded into transformed image by the arbitrary traditional RDHmethods. Before embedding, the auxiliary information should be compressed by a classic method, such as the Huffman code method, and should be encrypted by a traditional method, such as by AES encryption, for security.