# An Improved Reversible Image Transformation Using K-Means Clustering and Block Patching
## 1 Introduction  
With the development of cloud computing, more and more images are outsourced to cloud servers for storage or processing. However, some important private information, such as design drawings and internet sales data, may be leaked, and eavesdroppers are easily able to steal these contents. Nowadays, there are two common ways to protect from leakages: data hiding [1; 2; 3; 4] and encryption [5]. Encryption technology is more easy to cause the eavesdropper's suspicious because of the messy codes of cipher texts with the special form. Therefore, data hiding has been attracting more and more attention from researchers in recent years, and many related algorithms have been proposed. For example, [PERSON] et al. [1] applied an optimal pixel adjustment process to the stego-image obtained by the simple LSB substitution method, and the stego-image quality can be greatly improved with low extra computational complexity. [PERSON] et al. [4] designed a novel steganography approach using a reversible texture synthesis, which weaves in the texture synthesis process to conceal secret messages. However, this is a problem for sensitive applications such as military images and medical images. Reversible data hiding (RDH) [6; 7; 8; 9] is an effective method for these special scenarios, which aims to recover both embedded data and the original image. In the past two decades, many classic RDH algorithms have been proposed, such as lossless image compression methods [6], difference expansion-based methods [7] and histogram shifting based methods [8]. [PERSON] et al. [9] proposed a new reversible watermarking scheme based on error prediction in Hadamard domain, in which an adaline neural network is used to determine the coefficients of the predictor function to reduce error values. With the popularity of cloud storage services, the traditional RDH methods are not suitable in these scenarios, especially with regard to the requirement of high security. Therefore, the research of privacy protection in cloud computing has attracted considerable attention in recent years. Reversible data hiding in encrypted images (RDH-EI) provides the possibility that the image owner can encrypt the image before uploading it to the cloud, and then the cloud manager can embed some additional message into the comprehensible encrypted image for steganography or authentication. The receiver or authorized user can recover both the additional message and the original image. For these reasons, [PERSON] [10] designed a framework for a vacating room after encryption (VRAE), in which some additional information will be embedded after encrypting the original image; then, the encrypted image blocks will be divided into two sets by the cloud manager, and the manager can embed additional information by flipping three LSBs of a set. However, this process is irreversible, and has a low embedded capacity. In order to reduce the extracted-bits error rate, [PERSON] et al. [11] evaluated the complexity of image blocks. [PERSON] et al. [12] utilized a two-class support vector machine classifier to distinguish the encrypted and non-encrypted image patches to recover original images and secret data. [PERSON] et al. [13] designed an RDH-EI method for AMBTC images in which the redundant space of the encrypted AMBTC-compressed image can be exploited utilizing the histogram of prediction error in the data embedding phase. Despite all of this, it is hard to use the traditional RDH method for the cloud manager in this framework since the correlation between neighbor pixels in the encrypted image is destroyed. To solve this problem, [PERSON] et al. [14] proposed the framework of a reserving room before encryption (RRBE), in which the image owner can reverse the room of LSBs by using an RDH method, and encrypt the self-embedded image; then, the cloud manager embeds secret data into the reversed LSBs of the encrypted image. [PERSON] et al. [15] compressed pixels in the local patch by sparse representation, and achieved a higher reversed room than other previous methods.