Privacy-preserving inpainting for outsourced image

Abstract

In this article, a framework of privacy-preserving inpainting for outsourced image and an encrypted-image inpainting scheme are proposed. Different with conventional image inpainting in plaintext domain, there are two entities, that is, content owner and image restorer, in our framework. Content owner first encrypts his or her damaged image for privacy protection and outsources the encrypted, damaged image to image restorer, who may be a cloud server with powerful computation capability. Image restorer performs inpainting in encrypted domain and sends the inpainted and encrypted image back to content owner or authorized receiver, who can acquire final inpainted result in plaintext domain through decryption. In our encrypted-image inpainting scheme, with the assist of Johnson–Lindenstrauss transform that can preserve Euclidean distance between two vectors before and after encryption, the best-matching block with the smallest distance to current block can be found and utilized for patch filling in Paillier-encrypted image. To eliminate mosaic effect after decryption, weighted mean filtering in encrypted domain is conducted with Paillier homomorphic properties. Experimental results show that our privacy-preserving inpainting framework can be effectively applied in secure cloud computing, and the proposed encrypted-image inpainting scheme achieves comparable visual quality of inpainted results with some typical inpainting schemes in plaintext domain.

Introduction

Image inpainting is also known as image retouching, the idea of which is inherited from ancient technique of manually repairing valuable artworks in an indiscernible way. ¹ Inpainting of digital images has found applications in such fields as repairing of historical photographs, ² filling in or removing the selected region in images, ³ and wiping off visible watermarks. ⁴ In recent years, some studies have also been investigated to utilize image inpainting technique in deinterlacing, ⁵ image compression,^6,7 image self-recovery,^8,9 data hiding, ¹⁰ and repairing missing blocks of JPEG images due to poor channels. ¹¹ As for traditional image restoration, the regions for restoring generally include both noise and useful information. However, the damaged or missing regions to be inpainted often contain no useful information. Hence, the task of inpainting is to produce or create image regions that initially do not exist at all, according to the available information in close neighborhood and some mathematical models. Currently, there are four main categories of image inpainting methods, including interpolation-based methods,^12–15 partial differential equation (PDE)-based methods,^1,2,16–18 exemplar/patch-based methods,^3,19–21 and learning-based methods.^22–25 A brief review of these inpainting methods is given in section “Related works.”

Nowadays, with the prosperous development of Internet and mobile network, cloud storage and computing have become more and more prevalent. Due to the limit storage space and computation capability, the users can upload their multimedia data (such as texts, images, audios, and videos) through network, and various kinds of data computing required by users can be outsourced and implemented by cloud server. However, although cloud computing brings promising conveniences, the security issue is also raised at the same time because of the user privacy problem. ²⁶ In other words, users are afraid that their private data will be leaked, or cloud server and the third party may abuse their data. Therefore, a secure and reasonable solution is to encrypt the user data before outsourcing to the cloud for privacy protection, and the cloud server can perform data computing in the encrypted domain. Then, after conducting decryption for the received data from cloud server, the user can obtain the processed data with desirable effects in the plaintext domain. Based on this application scenario and requirements, in recent years, the studies of secure signal processing in encrypted domain have been widely investigated, such as transform, ²⁷ compression, ²⁸ denoising, ²⁹ feature extraction, ³⁰ and data hiding^31,32 for encrypted data.

In this article, we mainly focus on the problem of privacy-preserving inpainting for outsourced images. The aim of this problem is to realize the inpainting for encrypted, damaged images of users on the cloud server without sacrificing user privacy. Currently, although many image processing tools have modules to inpaint images, there are still a lot of manual operations that should be involved. In addition, these tools are often not free, and if we just have only a few images required to be inpainted, it is actually not a cost-effective choice to pay for these software. However, if we need to conduct inpainting for a large number of images, these professional tools often involve many manual operations and complex calculations during the implementation on the user client with limited computation capability and power. If we decide to outsource the inpainting work to the cloud, the privacy of image owner must be considered, which means the images to be inpainted should be encrypted at first. However, after the images are encrypted to prevent information leakage, there are also few related information that can be utilized in the encrypted domain for inpainting. Hence, the challenging and innovative task of outsourcing encrypted, damaged images to the cloud for automatic inpainting without leaking privacy deserves our in-depth investigations and has a lot of application scenarios. To the best of our knowledge, the reported works of inpainting all focused on the plaintext domain, and there have been no published literatures about image inpainting in the encrypted domain.

In this work, we propose a damaged image inpainting scheme based on a new privacy-preserving inpainting framework. The main contributions of the proposed scheme are summarized as follows: (1) The operation of image inpainting in our scheme is completely implemented in the encrypted domain, and image restorer cannot access any information of plaintext-image contents; (2) To calculate priority order and find similar blocks in encrypted image, with the assist of Johnson–Lindenstrauss (JL) transform that preserves Euclidean distance between two vectors before and after encryption, the best-matching, intact block can be found in the source region, and the intact patch is exploited to fill the damaged patch in homomorphic encrypted image; (3) To eliminate the undesirable mosaic effect after decryption, the weighted mean filtering in the encrypted domain is performed using the properties homomorphic cryptosystem; (4) Besides protecting the privacy of image owner, the proposed encrypted-image inpainting scheme can achieve comparable performance of inpainted-image quality with respect to some typical inpainting schemes for plaintext images.

The rest parts of the article are organized as follows. Section “Related works” presents brief reviews of image inpainting and homomorphic encryption. Section “Proposed scheme” describes the detailed procedures of the proposed privacy-preserving inpainting scheme for outsourced image, including image encryption, inpainting for encrypted image, and image decryption. Experimental results and analysis are presented in section “Experimental results and analysis.” Section “Conclusion” concludes the article.

Related works

Image inpainting

Generally speaking, current image inpainting methods can be categorized as non-learning-based methods and learning-based methods. Learning-based inpainting methods^22–25 often require a large-scale set of intact images for training with a specific deep neural network and then learn how to generate a reasonable repaired result for damaged region in a given image. Non-learning-based inpainting methods depend on the characteristic of autocorrelation within natural image, which usually exploit intact information only in current given image beyond its damaged region and use the exploited intact information to repair damaged region seamlessly in different ways, such as interpolation,^12–15 PDE propagation,^1,2,16–18 and patch synthesis.^3,19–21

Interpolation-based methods

Shih et al. ¹² proposed a multi-resolution method using pixel interpolation. In their method, the damaged image for inpainting was segmented into blocks, and the segmentation was conducted until the variances of sub-blocks were smaller than a pre-determined threshold. Damaged pixel was then repaired through the mean value of current sub-block or sub-block of previous level. Another image inpainting scheme with interpolation strategy was proposed in Shih et al., ¹³ which evaluated neighboring information of each pixel to be inpainted and decided the size of reference window that can be exploited to calculate an interpolated color. However, these methods may lead to blurring effects when damaged pixels were close to image edges.

PDE-based methods

This type of methods was motivated by intensive works on the use of variational and PDE methods in image processing. Bertalmio et al. ² established an inpainting mathematical model by borrowing ideas from classic fluid dynamics. By iteratively solving the numerical representation of a PDE, intact information of neighboring areas can be smoothly propagated into damaged region along isophote direction. Guided by the connectivity principle of human visual perception, Chan and Shen ¹⁶ proposed a non-texture image inpainting method with a third-order PDE, which essentially was an anisotropic diffusion process based on the total variation (TV) model. ¹⁷ To meet the requirements of human vision, diffusion intensity was related to the curvature. Even if the remaining objects were disconnected far apart by damaged region, this method can still output acceptable inpainted result. However, the PDE-based methods cannot deal with the large-area inpainting very well and often introduced heavy computation complexity due to high-order mathematic models.

Exemplar/patch-based methods

This type of methods employed the strategy of texture synthesis ³³ to repair larger damaged region. Criminisi et al. ²⁰ presented an exemplar-based image inpainting method, which can be used for both region filling and object removal. This method implemented the task of patch synthesis through a best-first filling mechanism, and the value of priority for each patch depended on the percentage of intact pixels and the angle between the isophote and contour normal on the center pixel. After locating the patch with the maximum priority in damaged region, the most similar patch was selected for substitution from the intact region in the image, and then the priority values should be updated to continue above process repeatedly. Inpainting procedure was terminated till all damaged patches were repaired. This method can achieve better inpainted results for larger damaged region than the PDE-based methods, although it may leave some artificial seams between the patches.

Learning-based methods

In recent years, a lot of works have applied the convolutional neural network (CNN) to image inpainting, such as Iizuka et al. ²² and Pathak et al. ²⁵ In these tasks, training samples were utilized to train the deep CNN so that they can estimate the pixel strength of the damaged region in the input image. ²⁴ Benefiting from large-scale training data, these learning-based methods can produce semantic specious inpainting results. However, the existing CNN-based inpainting methods usually completed damaged region by propagating convolution feature to the fully connected layer, which sometimes made the inpainted results lack fine texture details with blurring. Another powerful family of learning-based inpainting methods with deep generative model ²³ has also been proposed through introducing the adversarial loss to improve the visual quality of the inpainted results. Generally speaking, learning-based methods can achieve superior global semantic structures of inpainted results compared with non-learning-based methods, while non-learning-based methods can obtain fine local textures of inpainted results with much less computational complexity.

In this work, we mainly focus on the non-learning-based image inpainting methods, which have efficient and clear algorithms to follow and are more possible to be implemented in the encrypted domain with privacy-preserving capability than the learning-based methods.

Homomorphic encryption

To achieve computing in the encrypted domain, appropriate encryption methods should be first addressed. Homomorphic encryption generally includes partially homomorphic encryption (PHE), fully homomorphic encryption (FHE), and somewhat homomorphic encryption (SHE). PHE allows either addition or multiplication operations. Rivest et al. ³⁴ proposed a homomorphic encryption algorithm, which can maintain some algebraic relationships between the plaintext and the ciphertext. These relationships can be exploited to realize the computation for encrypted data effectively. Afterward, several probabilistic public-key cryptosystems were presented, such as ElGamal ³⁵ cryptosystem, Paillier ³⁶ cryptosystem, and Damgård and Jurik ³⁷ cryptosystem, and these cryptographic algorithms only had one homomorphic property, that is, addition or multiplication. For example, Paillier cryptosystem only had the addition homomorphism, which means that the addition of two plaintexts can be achieved through performing some operations on the two corresponding ciphertexts. FHE allows arbitrary number of addition and multiplication operations. ³⁸ In other words, FHE can realize the homomorphisms of addition and multiplication simultaneously, and theoretically speaking, it can solve any privacy-preserving computation problems. SHE allows addition and multiplication operations, but the number of operations is limited. ³⁹

Proposed scheme

In this section, we first present a new privacy-preserving inpainting framework for outsourced image, which can be effectively applied in the environment of cloud computing. Generally speaking, there are two entities in our framework, that is, content owner and image restorer, see Figure 1. Content owner, who has no professional inpainting capability, wants to have his or her damaged image repaired without disclosing image contents for privacy preserving. Hence, the ideal framework for this application scenario is that the content owner first encrypts the damaged image for inpainting and outsources the encrypted image to the image restorer, who may be a cloud server with powerful computation capability. Then, the restorer can conduct the inpainting operation for the damaged image effectively in the encrypted domain and sends the inpainted, encrypted image back to the content owner or the legal receiver, who can directly obtain the inpainted result in plaintext domain through image decryption.

Figure 1.

Framework of privacy-preserving inpainting for outsourced image.

To achieve the above described functions in the framework, a specific encrypted-image inpainting scheme is also proposed. Content owner first chooses a target region Ω to be removed or filled in the damaged image I_d and labels the position of the target region through a binary mask image Θ, in which the pixels with the values of 0 and 1 denote intact area and damaged area at the corresponding coordinates in the damaged image I_d, respectively. Then, the damaged image I_d is encrypted by Paillier homomorphic cryptosystem and JL transform to produce two encrypted results, that is, E_P and E_J. The content owner sends E_P, E_J, and Θ to image restorer for inpainting through the public channel. After receiving E_P, E_J, and Θ, the image restorer can perform image inpainting in the encrypted domain by utilizing these three components. In detail, the priority is first calculated for each pixel belonging to the target region according to the mask image Θ. With the assist of E_J, the encrypted, damaged image E_P can be inpainted as E_P′ through the mechanism of sample patch filling in the priority order. Then, the target region of E_P′ is further smoothed with the weighted mean filtering to produce the final inpainted result E_P″ in the encrypted domain. The content owner can decrypt E_P″ to obtain the inpainted image I_r in the plaintext domain. The flowchart of our scheme is illustrated in Figure 2. Details are described in the following subsections.

Figure 2.

Flowchart of the proposed encrypted-image inpainting scheme.

Image encryption

To protect the privacy of content owner, the damaged image I_d to be outsourced for inpainting is first encrypted as two results through the cryptographic techniques, that is, Paillier homomorphic cryptosystem and JL transform. In detail, one encrypted result E_P is obtained by Paillier homomorphic cryptosystem, which enables the filling or removing for the target region Ω with sample patches and the performing of the weighted mean filtering; the other encrypted result E_J is obtained by JL transform, which enables the operation of block matching. In addition, a mask image Θ is also generated and used to label the position of target region Ω for inpainting.

Encryption with Paillier homomorphic cryptosystem

The content owner first encrypts each pixel of the damaged image I_d sized H × W in the plaintext domain through homomorphic cryptosystem and obtains the encrypted result of each pixel by equation (1)

$$\rho (i,j)=\varphi [m(i,j),{\kappa }_{\mathrm{p}}]$$

(1)

where φ denotes the encryption function based on homomorphic cryptosystem, m(i, j) denotes the value of the pixel in I_d at the coordinate (i, j), κ_p is the public key of content owner, and ρ(i, j) denotes the encrypted result for the pixel m(i, j). Details of the calculation in equation (1) are given as follows.

In our scheme, Paillier ³⁶ homomorphic encryption belonging to the RSA-based probabilistic public-key cryptosystem is utilized. In Paillier homomorphic encryption, the content owner first chooses two large primes p and q randomly and calculates n = p·q and λ = lcm(p − 1, q − 1), where lcm(·) denotes the function of the least common multiple. Then, an integer g∈Z_n2^* is selected, which should satisfy gcd{[(g^λ mod n²) − 1]/n, n} = 1. The function gcd(·) is used to return the greatest common divisor. Thus, the public key κ_p and the private key κ_s of content owner can be acquired

$${\kappa }_{\mathrm{p}}=(n,g)$$

(2)

$${\kappa }_{\mathrm{s}}=(p,q,\lambda )$$

(3)

After generating the public key and the private key, the encryption for each pixel in I_d can be conducted with the public key κ_p, see equation (4)

$$\rho (i,j)=g^{m(i,j)}·r^n(i,j)mod{n}^2$$

(4)

where each pixel value for encryption, that is, the plaintext m(i, j) ∈Z _n , and r(i, j) ∈Z _n ^* that is an n coprime, random number (blinding factor). It should be noted that due to the randomness of r(i, j), the pixels with the same value and different coordinates may have different encrypted results. After all H × W pixels m(i, j) in the damaged image I_d are encrypted with equation (4), the content owner collects all corresponding encrypted pixels ρ(i, j) to form the encrypted image E_P.

Actually, besides Paillier homomorphic encryption, the encryption method to generate E_P in our scheme can also be compatible and replaced with some other additive homomorphic cryptosystems effectively. In addition, the Ring learning with errors (RLWE)-based SHE cryptosystem may also be utilized to further improve the computational efficiency.

Encryption with JL transform

To achieve the operation of block matching in our encrypted-image inpainting, the JL transform, which can not only reduce dimension but also retain Euclidean distance, ⁴⁰ is also utilized for image encryption. The property of JL transform is based on the following lemma.

Lemma 1

For an arbitrary set V with N vectors belonging to R^d, given 0 < ε < 1 and k ≥ log₂ N/ε², there exists a linear mapping Γ that can transform each vector of V from R^d into R^k, and all pairwise distances after and before mapping are within 1 ± ε factor. That is to say, for any two vectors α and β in V, the following relationship of the inequality satisfies

$$\begin{array}{c}(1-\epsilon )·\Vert \mathbf{\alpha }-\mathbf{\beta }{\Vert }_2^2\hfill \\ \le \Vert \mathrm{\Gamma }(\mathbf{\alpha })-\mathrm{\Gamma }(\mathbf{\beta }){\Vert }_2^2\le (1+\epsilon )·\Vert \mathbf{\alpha }-\mathbf{\beta }{\Vert }_2^2\hfill \end{array}$$

(5)

where α, β∈R^d, and Γ(α), Γ(β)∈R^k.

Through JL transform, a d-dimension vector can be converted to a k-dimension vector, and the Euclidean distance of two d-dimension vectors is approximate to that of the corresponding two k-dimension vectors after the transform. In Kenthapadi et al., ⁴¹ they analyzed the security of JL transform and proved that JL transform can be utilized for data encryption effectively. In our scheme, a random matrix ℜ sized k × d (ℜ∈R^k × d), associated with the secret key κ_J, is used as the linear mapping Γ in equation (5), that is, Γ(α) = ℜ·α. Note that, the transform from α to Γ(α) by ℜ is an irreversible process when k < d.

When encrypting the damaged image I_d by JL transform, for each pixel m(i, j) in I_d, its neighboring s − 1 pixels are collected to form an s-pixels local pattern with the pixel m(i, j) at the center. For the pixels on the image border, incomplete pixels in the local pattern can be created with surrounding pixels. Reshape the s-pixels in the local pattern with the center of m(i, j) into an s-dimension vector, which is denoted as N _{i, j} . Then, according to the secret key κ_J of JL transform, a random matrix ℜ sized k × s and a random k-dimension Gaussian noise vector σ with zero mean are generated and utilized for encryption

$${\mathbf{L}}_{i,j}=\Re \times {\mathbf{N}}_{i,j}+\mathbf{\sigma }$$

(6)

where L _{i, j} is a k-dimension vector and denotes the encrypted result for the pixel m(i, j). Note that, different with the Paillier encryption in section “Encryption with Paillier homomorphic cryptosystem,” the encrypted result of each pixel by JL transform is a vector instead of a single value. After all H × W pixels m(i, j) in I_d are encrypted through equation (6), the content owner collects all corresponding encrypted results L _{i, j} to form the encrypted image E_J.

Generation of mask image

Similar with the conventional image inpainting in the plaintext domain, the location of the image region to be inpainted should be provided to the restorer, who does not compromise the security of the scheme. Therefore, a binary mask image Θ for locating the target region Ω in the damaged image I_d (E_P) is produced by the content owner

$$\theta (i,j)=\{\begin{array}{c}1,(i,j)\in \mathbf{\Omega },\hfill \\ \multicolumn{1}{c}{0,(i,j)\notin \mathbf{\Omega },}\end{array}$$

(7)

where θ(i, j) is the value of the pixel at the coordinate (i, j) in the mask image Θ, and Θ is also with the size of H × W, which is the same as I_d and E_P.

After the above operations, including Paillier encryption, JL transform, and mask generation, the content owner sends the obtained results E_P, E_J, and Θ to the image restorer for inpainting in the encrypted domain.

Inpainting for encrypted image

After receiving the two encrypted images E_P, E_J, and the mask image Θ, image restorer conducts patch filling for image inpainting through the exemplar-based texture synthesis in the encrypted domain, see Figure 3. The target region Ω in E_P is first located according to the positions of non-zeros in Θ. To determine the order of inpainting, for each pixel c in Ω, a block B _c sized l × l with c at the center is exploited to calculate the priority. Among all pixels in Ω, the block B_c* with the highest priority is chosen as the first for repairing.

Figure 3.

Illustration of patch filling by exemplar-based texture synthesis in encrypted domain.

A source region Φ that contains sufficient, intact pixels is defined for the candidate block searching. Since JL transform preserves Euclidean distance, thus, with the assist of E_J, the best-matching block B_s* with respect to B_c* can be found in Φ, and then, in the encrypted image E_P, the damaged patch of B_c* can be filled with the corresponding patch of B_s*. After that, the values in the mask image Θ corresponding to the pixels in the filled patch are marked as zeros, and the target region Ω, the source region Φ, and the encrypted image E_J are updated. The block priorities for the updated Ω are recalculated, and the above procedure is iterated until the target region Ω becomes empty. To further smooth the inpainted region, the intermediate result E_P′ after patch filling is performed with the weighted mean filtering in encrypted domain based on Paillier homomorphic properties to produce the final inpainted result E_P″. Details are described as follows.

Block priority calculation

To inpaint the target region Ω of the encrypted image E_P, the order of inpainting for all the pixels in Ω should be first determined, which is based on the priority of the block with each pixel of Ω at the center. Since image restorer does not know the image contents and pixel values from E_P and E_J in our encrypted-image inpainting scheme, hence, only the location information of intact and damaged pixels from Θ can be utilized for block priority calculation. Obviously, the original intact pixels can be used as references during block matching. Therefore, rather than inpainting from inner to outer, it is more appropriate to perform inpainting for Ω from the outer region to the inner region because the blocks on the boundary of Ω, that is, ∂Ω, include some intact pixels. Thus, the useful information of intact pixels can be effectively used and propagated into target region Ω, which can lead to a more reasonable inpainted result.

Based on the above analysis, in our scheme, two conditions are considered during the calculation of the block priority: (1) the center pixels of the blocks with higher priorities should be on the boundary of Ω, that is, ∂Ω; and (2) the blocks with higher priorities should have more intact or inpainted pixels. These two conditions can guarantee a best-first filling mechanism during inpainting and are biased toward those blocks that are on the continuous, strong edges and surrounded by high-confidence pixels. In the target region Ω of E_P, the block priority O_c corresponding to the block B _c with the pixel c at the center can be calculated by

$$O_c=\{\begin{array}{c}\frac{\Im ({\mathbf{B}}_c)}{l^2},c\in \partial \mathrm{\Omega },\hfill \\ \multicolumn{1}{c}{0,c\notin \partial \mathrm{\Omega },}\end{array}$$

(8)

where the function $\mathfrak{J}$ (B _c ) returns the number of intact pixels in the l × l block B _c with the pixel c at the center, and the value of the block priority O_c belongs to [0, 1]. Actually, the number of intact pixels in the block B _c of the encrypted image E_P can be counted by the number of zeros in the corresponding block of the mask image Θ. After the block priorities O_c for all pixels c on ∂Ω are obtained, the block B_c* with the highest priority is chosen for candidate block matching, where

$$c^{*}=\underset{c}{\arg max}(O_c)$$

(9)

It should be noted that, the size l × l of the blocks for priority calculation and further block matching may have influence on the performance of inpainting. Too small size of the blocks will weaken texture features in the inpainted results. However, if the block size is too large, inpainted results will appear the serious mosaic effect. In addition, the size r × r of the source region Φ is related to inpainting quality and computation complexity. Therefore, the selection of appropriate sizes of block and source region is important, which is discussed in section “Experimental results and analysis.”

Block matching and patch filling

After obtaining the block B_c* with the highest priority in current target region Ω of E_P, the block matching between B_c* and all candidate blocks in source region Φ is conducted with the assist of E_J, and then the corresponding patch Ψ_s* in the best-matching candidate block B_s* is utilized to fill the damaged patch Ψ_c* in B_c*.

The operation of block matching is based on the property of Euclidean distance preserving for JL transform. To conduct block matching and patch filling, the distance between the block B_c* and each candidate block B _s from Φ is calculated according to E_J

$$\begin{array}{c}\mathrm{dist}({\mathbf{B}}_{c*},{\mathbf{B}}_s)=\frac{\sum _{(i,j)\in {\mathbf{B}}_{c*}}D[{\mathbf{E}}_{\mathrm{J}}(i,j),{\mathbf{E}}_{\mathrm{J}}(i+x,j+y)]}{l^2}\hfill \\ \mathrm{subject}\mathrm{to}{\mathbf{B}}_s\in \mathbf{\Phi },\hfill \end{array}$$

(10)

where (x, y) is the coordinate displacement of B _s with respect to B_c*, s can be considered as the center pixel in B _s , and the function D for the calculation of the distance between the two points of k-dimension vectors in E_J can be found in equation (11)

$$D[{\mathbf{E}}_{\mathrm{J}}(i_1,j_1),{\mathbf{E}}_{\mathrm{J}}(i_2,j_2)]=\sqrt{\Vert {\mathbf{L}}_{i_1,j_1}-{\mathbf{L}}_{i_2,j_2}{\Vert }_2^2-2k·\Vert \mathbf{\sigma }{\Vert }_2^2}$$

(11)

where L_{i1, j1} and L_{i2, j2} denote two points of k-dimension vectors in E_J, that is, E_J(i₁, j₁) and E_J(i₂, j₂), which are also the two encrypted results based on JL transform for the plaintext pixels m(i₁, j₁) and m(i₂, j₂), respectively (refer to section “Encryption with JL transform”). Because the Euclidean distance between two vectors in JL-encrypted domain is approximate to that in the plaintext domain, thus, the candidate block B _s from Φ with the smallest distance to the block B_c* is selected as the best-matching block B_s*, where

$$s^{*}=\underset{s}{\arg min}[\mathrm{dist}({\mathbf{B}}_{c*},{\mathbf{B}}_s)]$$

(12)

Through obtaining the best-matching block B_s* in the encrypted image E_P, the damaged patch Ψ_c* of B_c* can be filled with the corresponding patch Ψ_s* of B_s*. In other words, all the encrypted, damaged pixels in B_c* are replaced by the encrypted, intact pixels at the same locations in B_s*, see equation (13)

$$\begin{array}{c}{\mathbf{E}}_{\mathrm{P}}\prime (i,j)={\mathbf{E}}_{\mathrm{P}}(i+x^{*},j+y^{*}),\hfill \\ \mathrm{for}\forall (i,j)\in {\mathbf{B}}_{c*}\mathrm{and}\theta (i,j)=1\hfill \end{array}$$

(13)

where (x^*, y^*) is the coordinate displacement of B_s* with respect to B_c*, and E_P′(i, j) is the filled result for the encrypted, damaged pixel E_P(i, j). Besides the patch filling for the block B_c* in E_P, the encrypted image E_J should also be repaired through the similar process

$$\mathbf{L}{\prime }_{i,j}={\mathbf{L}}_{i+x^{*},j+y^{*}},\mathrm{for}\forall (i,j)\in {\mathbf{B}}_{c*}\mathrm{and}\theta (i,j)=1$$

(14)

where L′ _{i, j} denotes the filled result for the encrypted, damaged vector L _{i, j} , that is, E_J(i, j), in E_J. After the patch filling in E_P and E_J, the mask image Θ is required for updating

$$\theta \prime (i,j)=\{\begin{array}{c}1,(i,j)\in \mathbf{\Omega }-{\mathbf{B}}_{c*},\hfill \\ \multicolumn{1}{c}{0,(i,j)\notin \mathbf{\Omega }-{\mathbf{B}}_{c*},}\end{array}$$

(15)

where θ′(i, j) is the updated value of the pixel at the coordinate (i, j) in the new mask image Θ′. Equation (15) means that the damaged patch in B_c* is repaired and can be marked as intact. Note that, the target region Ω and the source region Φ should also be updated at the same time with Θ, that is, the new Ω′ is updated with Ω − B_c* and the new Φ′ is updated with Φ + B_c*.

According to the above described steps, the operations of block priority calculation, block matching, and patch filling are iteratively implemented for the updated target region Ω′. Until the target region becomes empty, the iteration procedure is terminated and generates an inpainted result for the encrypted image E_P, that is, E_P′.

Region smoothing with weighted mean filtering

Because the process of patch filling in section “Block matching and patch filling” is performed in a blockwise manner, thus, undesirable mosaic effect may appear in the target region Ω if the inpainted result E_P′ is directly decrypted. To eliminate the mosaic effect, the post-processing should be conducted for E_P′ in the encrypted domain. Thereby, after image decryption by content owner or legal receiver, an inpainted image in the plaintext domain with satisfactory quality can be produced.

In our scheme, after patch filling, image restorer conducts region smoothing for the target region Ω in the intermediate result E_P′ to achieve the equivalent function of weighted mean filtering in the plaintext domain. The operation of region smoothing in the encrypted domain is realized based on homomorphic properties of Paillier cryptosystem. The utilized homomorphic properties of addition are described as follows.

Assume m(i₁, j₁) and m(i₂, j₂) as the values of two pixels at the coordinates (i₁, j₁) and (i₂, j₂) in plaintext domain, respectively. Denote ρ(i₁, j₁) and ρ(i₂, j₂) as the encrypted results of m(i₁, j₁) and m(i₂, j₂) based on Paillier homomorphic encryption (refer to section “Encryption with Paillier homomorphic cryptosystem”), see equation (16)

$$\rho (i_{\nu },j_{\nu })=g^{m(i_{\nu },j_{\nu })}·r^n(i_{\nu },j_{\nu })mod{n}^2,\nu =1,2$$

(16)

Then, the following three equations (17)–(19) can be acquired, where k is an integer

$$\begin{array}{c}\multicolumn{1}{c}{\rho (i_1,j_1)·g^{k}mod{n}^2=g^{m(i_1,j_1)}·r^n(i_1,j_1)·g^{k}mod{n}^2}\\ \multicolumn{1}{c}{=g^{m(i_1,j_1)+k}·r^n(i_1,j_1)mod{n}^2}\end{array}$$

(17)

$$\begin{array}{c}\rho (i_1,j_1)·\rho (i_2,j_2)mod{n}^2\hfill \\ =g^{m(i_1,j_1)}·r^n(i_1,j_1)·g^{m(i_2,j_2)}·r^n(i_2,j_2)mod{n}^2\hfill \\ =g^{m(i_1,j_1)+m(i_2,j_2)}[r(i_1,j_1)r(i_2,j_2){]}^{n}mod{n}^2\hfill \end{array}$$

(18)

$$\begin{array}{c}\multicolumn{1}{c}{{\rho }^k(i_1,j_1)mod{n}^2=[g^{m(i_1,j_1)}·r^n(i_1,j_1){]}^{k}mod{n}^2}\\ =g^{k·m(i_1,j_1)}{r}^{k·n}(i_1,j_1)mod{n}^2\hfill \end{array}$$

(19)

It can be observed from equations (17)–(19) that, under Paillier cryptosystem, ρ(i₁, j₁)·g^k mod n² is a valid encrypted result for m(i₁, j₁) + k, ρ(i₁, j₁) ·ρ(i₂, j₂) mod n² is a valid encrypted result for m(i₁, j₁) + m(i₂, j₂), and ρ^k(i₁, j₁) mod n² is a valid encrypted result for k·m(i₁, j₁), respectively.

As for the weighted mean filtering in the plaintext domain, the current pixel m(i, j) in target region Ω for processing should be substituted with the weighted mean value of m(i, j) itself and its neighboring pixels

$$\begin{array}{c}m\prime (i,j)={\mathbf{W}}_{i,j}·{\mathbf{M}}_{i,j}^{\mathrm{T}}\hfill \\ =[w_{i-1,j},w_{i+1,j},w_{i,j},w_{i,j-1},w_{i,j+1}]·\hfill \\ [m(i-1,j),m(i+1,j),m(i,j),m(i,j-1),m(i,j+1){]}^{\mathrm{T}}\hfill \\ =w_{i-1,j}·m(i-1,j)+w_{i+1,j}·m(i+1,j)+w_{i,j}·m(i,j)+\hfill \\ w_{i,j-1}·m(i,j-1)+w_{i,j+1}·m(i,j+1),\hfill \end{array}$$

(20)

where M _{i, j} denotes the pixel vector consisting of current pixel m(i, j) and its four neighborhood, W _{i, j} is the weight vector for M _{i, j} , and m′(i, j) is the result of weighted mean filtering for m(i, j). In our scheme, the components of the weight vector W _{i, j} can be set as: w_{i − 1,j} = w_i + 1,j = w_{i, j − 1} = w_{i, j + 1} = 1/(4 + ω) and w_{i, j} = ω/(4 + ω), where ω is a small positive integer. To realize weighted mean filtering in encrypted domain based on Paillier homomorphic properties of equations (17) and (19), the components of the weight vector W _{i, j} should be modified as integers

$$\mathbf{W}{\prime }_{i,j}=(4+\omega )·{\mathbf{W}}_{i,j}$$

(21)

where W′ _{i, j}  = [w′_{i − 1,j}, w′_i + 1,j, w′ _{i, j} , w′_{i, j − 1}, w′_{i, j + 1}] = [1, 1, ω, 1, 1]. Thus, for the intermediate result E_P′ after patch filling, according to the homomorphic properties of addition in equations (17)–(19), image restorer can perform the following operation to realize weighted mean filtering in the encrypted domain

$$\begin{array}{c}\multicolumn{1}{c}{\rho ″(i,j)=\rho \prime (i-1,j{)}^{w{\prime }_{i-1,j}}·\rho \prime (i+1,j{)}^{w{\prime }_{i+1,j}}·}\\ \multicolumn{1}{c}{\rho \prime (i,j{)}^{w{\prime }_{i,j}}·\rho \prime (i,j-1{)}^{w{\prime }_{i,j-1}}·\rho \prime (i,j+1{)}^{w{\prime }_{i,j+1}}}\\ =\rho \prime (i-1,j)·\rho \prime (i+1,j)·\rho \prime (i,j{)}^{\omega }·\hfill \\ \multicolumn{1}{c}{\rho \prime (i,j-1)·\rho \prime (i,j+1),}\\ \multicolumn{1}{c}{\mathrm{for}\forall (i,j)\in \mathbf{\Omega },}\end{array}$$

(22)

where ρ′(i, j) denotes the value of the encrypted pixel at coordinate (i, j) in E_P′, and ρ″(i, j) is the result of weighted mean filtering for ρ′(i, j) in Paillier-encrypted domain.

After all pixels ρ′(i, j) in E_P′ belonging to the original target region Ω finish the above processing in equation (22) as ρ″(i, j), the final inpainted, encrypted image E_P″ with patch filling and region smoothing can be obtained, which can be then transmitted to the content owner or authorized receiver for decryption, and the privacy-preserving inpainting for the outsourced image is completed.

Image decryption

After receiving the final inpainted, encrypted image E_P″ from image restorer, the content owner or the authorized receiver conducts image decryption through the private key κ_s = (p, q, λ) of Paillier encryption in equation (3)

$$\begin{array}{c}\multicolumn{1}{c}{m\prime (i,j)=\frac{[\rho ″{(i,j)}^{\lambda }mod{n}^2]-1}{[g^{\lambda }mod{n}^2]-1}modn,}\\ \mathrm{for}\forall (i,j)\in {\mathbf{E}}_{\mathrm{P}}″\hfill \end{array}$$

(23)

where m′(i, j) denotes the decrypted result of ρ″(i, j) based on Paillier ³⁶ cryptosystem. Then, since the weight vector W′ _{i, j} is multiplied by (4 + ω) during the weighted mean filtering (refer to section “Region smoothing with weighted mean filtering”), hence, all decrypted results m′(i, j) should be further processed to produce the final inpainted image I_r

$$m″(i,j)=\{\begin{array}{c}\frac{m\prime (i,j)}{4+\omega },\mathrm{for}\forall (i,j)\in \mathbf{\Omega },\hfill \\ \multicolumn{1}{c}{m\prime (i,j),\mathrm{for}\forall (i,j)\notin \mathbf{\Omega },}\end{array}$$

(24)

where m″(i, j) denotes the value of the pixel at coordinate (i, j) of the final inpainted image I_r in the plaintext domain.

Experimental results and analysis

To demonstrate the effectiveness and superiority of the proposed scheme, a large number of test images were applied to conduct privacy-preserving image inpainting in the encrypted domain. In addition, we also compared the performance of inpainted quality between our scheme and some typical image inpainting schemes in the plaintext domain. Note that, in real applications, we often do not have original intact images. In the experiments, original intact images were just used to generate corresponding damaged images and to evaluate the visual quality of inpainted results as the references. Some of the images used in experiments and analysis, including Lena, Baboon Portofino, Zelda, Lake, House, Peppers, and Elaine, are illustrated in Figure 4.

Figure 4.

Some of the test images. (a) Lena. (b) Baboon. (c) Portofino. (d) Zelda. (e) Lake. (f) House. (g) Peppers. (h) Elaine.

Examples of the proposed scheme

In the proposed scheme, the inpainting operation is performed on the encrypted, damaged image E_P of Paillier homomorphic encryption. Figures 5 and 6 illustrate the encrypted results for the two standard test images Lena and Baboon both with the sizes of 512 × 512, in which subfigures (a) and (b) are the original images and their corresponding mask images Θ for locating the damaged areas (target regions Ω were marked as black), and subfigures (c) and (d) are the damaged images in the plaintext domain and the Paillier-encrypted domain, respectively. The damaged rates τ, which are defined as the ratios between the numbers of black pixels and all pixels in the mask images Θ, for Lena and Baboon are 4.93% and 5.20%, respectively. Note that, pixel values of the encrypted images in Figures 5 and 6(d) are the results after modulo 256 for displaying. It can be clearly observed from Figures 5 and 6 that, the contents of original images are concealed after encryption, which can protect the privacy of the content owner effectively.

Figure 5.

Encrypted results based on Paillier homomorphic encryption for Lena. (a) Original image. (b) Mask image Θ. (c) Damaged image I_d (τ = 4.93%). (d) Encrypted, damaged image E_P.

Figure 6.

Encrypted results based on Paillier homomorphic encryption for Baboon. (a) Original image. (b) Mask image Θ. (c) Damaged image I_d (τ = 5.20%). (d) Encrypted, damaged image E_P.

After image encryption, the encrypted, damaged images were outsourced to image restorer for inpainting in the encrypted domain through the method described in section “Inpainting for encrypted image” (including patch filling and region smoothing). Then, the inpainted results in encrypted domain were sent back to the content owner or authorized receiver. Finally, after image decryption, the inpainted images in the plaintext domain were acquired. Figures 7 and 8(a) show the inpainted images in the encrypted domain for the two encrypted, damaged images Lena and Baboon in Figures 5 and 6(d), respectively, and their corresponding inpainted results in the plaintext domain (i.e. after image decryption) are presented in Figures 7 and 8(b). In our experiments, the two typical indices, peak signal-to-noise ratio (PSNR) and structural similarity (SSIM), ⁴² were utilized to evaluate visual quality of inpainted images in plaintext domain. Obviously, the greater the values of PSNR and SSIM are, the better visual quality of the inpainted image I_r with respect to the original intact image I_o is. PSNR values of the inpainted images Lena and Baboon in Figures 7 and 8(b) were calculated as 44.65 and 42.56 dB, and their SSIM values were 0.9826 and 0.9615, respectively. It can be found from Figures 7 and 8(b) and the values of PSNR and SSIM that, the visual quality of inpainted results for our scheme is satisfactory.

Figure 7.

Inpainted results for Lena. (a) Inpainted image E_P″ in encrypted domain. (b) Inpainted image I_r after decryption (PSNR = 44.65 dB, SSIM = 0.9826).

Figure 8.

Inpainted results for Baboon. (a) Inpainted image E_P″ in encrypted domain. (b) Inpainted image I_r after decryption (PSNR = 42.56 dB, SSIM = 0.9615).

Parameter analysis

In our encrypted-image inpainting scheme, there are four main parameters: s and k in JL transform (section “Encryption with JL transform”), the size l × l of the block for priority calculation and matching (section “Block priority calculation”), and the size r × r of source region for conducting block matching (section “Block matching and patch filling”). The influence of inpainting performance with respect to these parameters is analyzed detailedly in the following. The experiments for parameter analysis in this subsection were conducted on the standard images sized 512 × 512. Besides Lena (τ = 4.93%) and Baboon (τ = 5.20%) in Figures 5 and 6(c), the other two standard images Portofino and Zelda were also used and their damaged rates τ are 3.98% and 3.95% with random forms, respectively.

Parameters s and k in JL transform

During the image encryption of JL transform, a random matrix ℜ sized k × s is utilized, see equation (6), which can securely transform a s-pixels local pattern into a k-dimension vector for each center pixel m(i, j) and also retain the Euclidean distance. Based on a large number of experiments, we find that, the parameter s has obvious influence on the visual quality of inpainted results because the distance for block matching is significantly changed with different values of s, while the influence of parameter k is not obvious. In Table 1, with the values of s equaling to 5, 9, and 25, the indices of PSNR and SSIM for the inpainted images, including Lena, Baboon, Portofino, and Zelda, are given, and the three local patterns in Figure 9(a)–(c) correspond to s = 5, s = 9, and s = 25, respectively. It can be concluded from the results that, generally speaking, the smaller the value of s is, the better quality of inpainted results can be obtained. In the process of image encryption with JL transform, each ciphertext is determined by all the s-pixels in the local pattern, thus, smaller patterns can reflect local information of plaintext pixels more accurately. In addition, we can observe from the results that, for most images, the visual quality of inpainted results were satisfactory when s was set as 5. However, when s was set as a larger value, such as 9 or 25, the Euclidean distance between two JL-encrypted pixels covered more unnecessary information of adjacent pixels, which led to inaccurate results in searching the best-matching block, and degraded the inpainted quality.

Table 1.

Visual quality of inpainted results under different s and k of JL transform (l = 11, r = 33).

Parameters		Lena		Baboon		Portofino		Zelda
s	k	PSNR	SSIM	PSNR	SSIM	PSNR	SSIM	PSNR	SSIM
25	9	43.36	0.9775	40.70	0.9495	43.42	0.9784	42.79	0.9755
25	7	43.51	0.9778	40.51	0.9522	43.43	0.9780	42.95	0.9746
25	5	43.39	0.9781	40.48	0.9483	43.34	0.9779	42.92	0.9750
25	3	43.39	0.9789	40.47	0.9469	43.40	0.9783	42.49	0.9750
25	1	43.31	0.9799	40.55	0.9511	43.34	0.9773	42.89	0.9744
9	9	44.09	0.9819	41.06	0.9527	45.40	0.9825	44.22	0.9764
9	7	44.12	0.9816	41.32	0.9479	45.74	0.9830	44.23	0.9764
9	5	44.10	0.9813	41.06	0.9509	45.53	0.9826	44.04	0.9736
9	3	44.26	0.9814	41.08	0.9492	45.73	0.9833	43.98	0.9745
9	1	44.23	0.9814	41.27	0.9553	45.65	0.9823	44.17	0.9751
5	9	44.51	0.9831	41.65	0.9616	45.49	0.9841	44.54	0.9778
5	7	44.65	0.9826	41.64	0.9589	45.45	0.9840	44.40	0.9803
5	5	44.57	0.9831	41.70	0.9615	45.70	0.9837	44.37	0.9769
5	3	44.46	0.9831	41.62	0.9665	45.74	0.9841	44.09	0.9788
5	1	44.55	0.9828	41.42	0.9641	45.78	0.9837	44.04	0.9774

PSNR: peak signal-to-noise ratio; SSIM: structural similarity.

Figure 9.

Three local patterns used in image encryption based on JL transform. (a) s = 5. (b) s = 9. (c) s = 25.

Parameter of size l × l for block priority calculation and block matching

The procedure of encrypted-image inpainting described in sections “Block priority calculation” and “Block matching and patch filling” is performed in the blockwise manner. For each pixel c in the target region Ω, a block B _c sized l × l with c at the center is exploited for priority calculation and block matching. Therefore, the block size l × l is also a key factor that has influence on the inpainting performance. Detailedly, too smaller size of block B _c may cause the loss of texture features in the inpainted result, while too larger size leads to the serious mosaic effect probably. It can be observed from Figure 10 that, for most images sized 512 × 512, the visual quality of inpainted results decreases rapidly when l is smaller than 11, the inpainted quality has a downward trend when l is greater than 17, and the inpainted quality tends to be relatively stable when l is in the range between 11 and 17.

Figure 10.

Visual quality of inpainted results under different sizes l × l of block B _c (s = 5, k = 5, r = 33). (a) PSNR of inpainted results. (b) SSIM of inpainted results.

Parameter of size r × r for source region Φ

In our scheme, the source region Φ for searching the best-matching block can be defined as the entire image excluding the target region Ω. However, for the trade-off of acceptable inpainted quality and feasible computation complexity, rather than the entire image, we only set a dilated window centered at the current pixel c and sized r × r as the source region Φ. The correlation between the block B_c* and all candidate blocks in source region Φ for matching is inversely proportional to their distances; hence, too larger size of source region Φ cannot guarantee the satisfactory repaired results and may make the inpainted region significantly different with its close neighborhood. However, too smaller size of source region Φ may lead to the failure of finding the appropriate matching block and also make repaired results unsatisfactory. Therefore, a suitable size of source region Φ should be chosen for searching the best-matching block. However, from the results in Figure 11, we can find that the most appropriate sizes of source region Φ leading to the best inpainted quality fluctuate irregularly in a wide range for different images. Therefore, the size of source region Φ is better to be manually chosen through trial and error.

Figure 11.

Visual quality of inpainted results under different sizes r × r for source region Φ (s = 5, k = 5, l = 11). (a) PSNR of inpainted results. (b) SSIM of inpainted results.

Comparisons with plaintext-domain inpainting schemes

To demonstrate the effectiveness of our scheme, we compared the decrypted, inpainted results of our proposed ciphertext-domain inpainting scheme with those of the three famous plaintext-domain inpainting schemes, that is, TV-based scheme by Shen and Chan, ¹⁷ Navier–Stokes PDE-based scheme by Bertalmio et al., ² and exemplar-based scheme by Criminisi et al. ²⁰

Figure 12 shows the inpainted results for Lena, Baboon, Lake, and House, in which the first column to the fifth column denote the damaged images, the results of the proposed scheme after image decryption, scheme by Shen and Chan, ¹⁷ scheme by Bertalmio et al., ² and scheme by Criminisi et al., ²⁰ respectively. The damaged images Lena in Figure 12(a1) and Baboon in Figure 12(a2) are the same as those in Figures 5(c) and 6(c) with damaged rates τ = 4.93% and τ = 5.20%, respectively. Besides the conventional damage forms (such as lines and scratches in Lena and Baboon) for inpainting that can be considered as region filling, the other two typical examples of object removal for damaged images are presented in Figure 12(a3) and (a4). Detailedly, Figure 12(a3) shows the damaged image Lake imposed with a number of texts (τ = 4.86%). Figure 12(a4) shows the image House with a man as an undesirable foreground object, and to seamlessly remove the man from the image, this object was marked as the black region (τ = 0.96%). Note that, inpainting procedure of the schemes^2,17,20 was just performed on the plaintext-domain, damaged images in Figure 12(a1)–(a4), while the inpainting procedure of the proposed scheme was performed on their Paillier-encrypted, damaged versions.

Figure 12.

Comparison results for our encrypted-image inpainting and plaintext-image inpainting.^2,17,20 (a1)–(a4) Damaged images Lena, Baboon, Lake and House. (b1)–(b4) Results of our scheme after decryption. (c1)–(c4) Results of total variation-based scheme. ¹⁷ (d1)–(d4) Results of Navier–Stokes PDE-based scheme. ² (e1)–(e4) Results of exemplar-based scheme. ²⁰

We can observe from Figure 12 that the structural and textural information in the target region, such as lines and edges in Lena and fur and whiskers in Baboon, are successfully repaired by our scheme and there are not obvious blurring effects. Compared with the three plaintext-domain schemes,^2,17,20 our scheme can generally obtain better visual quality of inpainted results than the PDE-based schemes^2,17 and achieve the comparable performance with the texture synthesis-based scheme. ²⁰ It can also be found that our scheme can seamlessly remove the imposed texts for Lake and effectively inpaint the occluded window, bushes, and lawn for House without a priori model. The values of PSNR and SSIM for the inpainted results for Lena, Baboon, and Lake under the four schemes are listed in the first three rows of Table 2 (PSNR and SSIM for House are not available due to the absence of original reference image).

Table 2.

Comparisons of {PSNR, SSIM} for the inpainted results between the proposed scheme and the schemes in Shen and Chan, ¹⁷ Bertalmio et al., ² and Criminisi et al. ²⁰

Images	Damaged rate (%)	Scheme in Shen and Chan 17	Scheme in Bertalmio et al. 2	Scheme in Criminisi et al. 20	Proposed scheme
Lena	4.93	{34.25, 0.9831}	{43.17, 0.9811}	{44.99, 0.9805}	{44.65, 0.9826}
Baboon	5.20	{32.32, 0.9706}	{39.45, 0.9555}	{42.20, 0.9676}	{42.56, 0.9615}
Lake	4.86	{30.79, 0.9779}	{45.83, 0.9877}	{43.41, 0.9752}	{43.58, 0.9822}
Portofino	3.98	{37.98, 0.9873}	{42.10, 0.9771}	{45.57, 0.9780}	{46.06, 0.9832}
Zelda	3.95	{38.49, 0.9878}	{43.14, 0.9841}	{44.52, 0.9841}	{44.54, 0.9778}
Peppers	3.01	{39.77, 0.9943}	{43.04, 0.9850}	{47.52, 0.9884}	{46.74, 0.9864}
Elaine	4.19	{38.28, 0.9896}	{39.87, 0.9701}	{44.10, 0.9822}	{45.63, 0.9711}
Average	4.30	{35.98, 0.9844}	{42.37, 0.9772}	{44.61, 0.9794}	{44.82, 0.9778}

In addition to the above inpainting results in Figure 12 for the four images (Lena, Baboon, Lake, and House), four other standard test images, including Portofino, Zelda, Peppers, and Elaine, were also involved in the experiments. The damaged forms for these four images were random, and the corresponding damaged rates τ were 3.98%, 3.95%, 3.01%, and 4.19%, respectively. Table 2 gives a summary of PSNR and SSIM for the seven inpainted images with respect to their corresponding original images under the three plaintext-domain inpainting schemes^2,17,20 and the proposed ciphertext-domain inpainting scheme. It can be found that our scheme is more suitable for repairing the images with richer textures and larger damaged area. In a word, although the inpainting procedure of our scheme is implemented in ciphertext domain, it can achieve comparable inpainting performance with plaintext-domain schemes and can also realize privacy preserving for the content owner effectively.

Applications in color images and comparison with PatchMatch

Besides gray-level images, we also applied our scheme in color images for privacy-preserving inpainting. Test images were randomly selected from the ImageNet database, which is a famous large-scale image database in the fields of image recognition and computer vision, and a representative inpainting scheme for color images in plaintext domain, called PatchMatch, ²¹ was utilized for comparison, see Figure 13. The first column of Figure 13 denotes the original images randomly chosen from ImageNet, and the second column is their damaged versions with various damaged rates. The third column and the fourth column are the inpainted results of our scheme (after image decryption) and PatchMatch, ²¹ respectively. Note that, PatchMatch ²¹ was just performed on the damaged images in plaintext domain, that is, Figure 13(b1)–(b4), while our scheme was performed on the Paillier-encrypted, damaged versions of Figure 13(b1)–(b4). It can be observed from Figure 13 that the structural and textural information in the target region, such as lines and textures, was basically repaired by our scheme, and there were not obvious blurring effects. Therefore, our scheme can not only achieve comparable visual quality of inpainted results with the plaintext-domain scheme for color images, that is, PatchMatch, ²¹ but also can realize privacy protection for image contents from content owner since our inpainting operation of image restorer is processed on encrypted versions of damaged images.

Figure 13.

Inpainting application for color images and comparison between our encrypted-image inpainting with the plaintext-image PatchMatch inpainting. ²¹ (a1)–(a4) Original images from ImageNet. (b1)–(b4) Damaged versions of (a1)–(a4). (c1)–(c4) Results of our scheme after decryption. (d1)–(d4) Results of PatchMatch. ²¹

Discussions of security and computational complexity

Security discussions

Since Paillier ³⁶ proved that Paillier encryption provides semantic security and the attacker cannot learn any information of the plaintext except for the length of the plaintext, hence, we mainly discuss the security of JL transform used in the scheme. In our scheme, the encrypted result of each pixel by JL transform is a vector instead of a single value. After all H × W pixels m(i, j) in I_d are encrypted through equation (6), the content owner collects all corresponding encrypted results L _{i, j} to form the encrypted image E_J. Binarization attack mentioned in Hu et al. ²⁹ means that for each JL-encrypted result L _{i, j} with respect to the plaintext pixel m(i, j), which is a k-dimension vector, calculate the mean value of the k components in L _{i, j} , thus, corresponding to H × W plaintext pixels, H × W mean values can be obtained, which preserve the relative positions and intensities of pixels in the plaintext image I_d. Then, the attacker can easily quantize these H × W mean values into binary values through setting a threshold and reshape these H × W binary values to produce a binary image sized H × W, which is visually approximate to I_d and leaks the privacy of image owner.

To defeat the potential binarization attack, we should eliminate the correlation between neighboring pixels. Hence, after Paillier encryption and JL transform, random permutation should be further performed on the two encrypted images E_P, E_J, and their corresponding mask image Θ. It should be noted that our inpainting scheme is based on patch filling, and damaged region is repaired patch by patch rather than pixel by pixel. Hence, in our scheme, the random permutation is conducted on E_P, E_J, and Θ in a blockwise manner. In addition, to keep the corresponding relationships for the encrypted results of E_P, E_J, and Θ, the same pseudo-random permutation sequence derived by secret key κ_r should be utilized for them. Thus, without knowing the secret key κ_r, the attacker may try all possible permutations and the number of all possible permutations is (H × W / l²)! For an image sized 512 × 512 (H = W = 512) and the block size equaling 9 × 9 (l = 9), the possibility for the attacker to crack the correct permutation is lower than 1/3236! Therefore, without the secret key κ_r, even if the attacker implements the binarization attack on the ciphertext encrypted by JL transform, it is difficult to recover approximate content of original image I_d because the locations of image blocks are completely permuted.

However, since local correlation in the permuted image is removed after random permutation, the source region Φ sized r × r for candidate block searching will no longer work. An effective way to solve this problem is directly extending the source region Φ sized r × r to the whole image sized H × W. In other words, block matching will be conducted within the whole image instead of the source region, which may increase computational complexity significantly. Hence, we can adopt the random sampling strategy in Chan et al. ⁴³ to reduce computational complexity, which only randomly calculates a small number of image block distances according to sampling patterns.

Computational complexity

In our scheme, both JL Transform and Paillier encryption cause the ciphertext expansion. To reduce the storage on the client side, the image pixels can be encrypted one by one, and each encrypted pixel is directly transmitted to the cloud immediately. Thus, the client side does not need to store the whole encrypted images. As for Paillier encryption indicated in equation (4), the total data volume transmitted from the client side to the cloud is about 2| n| × H × W bits, where| n| denotes the bit length of n, and H × W is the number of image pixels. Thus, for a 1024-bit integer n, the ciphertext expansion ratio of Paillier encryption in our scheme is about 2 × 1024 / 8 = 256 for one 8-bit pixel. Since the encrypted result of each pixel m(i, j) for JL transform is a k-dimension vector instead of a single value, hence, the ciphertext expansion ratio of JL transform is approximately equal to the parameter k in our scheme. After the cloud completes the operation of image inpainting in encrypted domain, the final inpainted, Paillier-encrypted image E_P″ should be transmitted from the cloud to the client for decryption, while the ciphertext E_J encrypted by JL transform does not need to be sent back to the client.

As for execution time, the most complicated computation on the client side is Paillier encryption and decryption. To increase the efficiency, we adopted the fast algorithm proposed by Jost et al., ⁴⁴ which is a variant of Paillier cryptosystem based on pre-computing and look-up table. The execution time for the different operations on the sender side and the receiver side is listed in Table 3, which includes Paillier encryption, JL transform, random permutation for image owner/sender, and Paillier decryption and inverse permutation for legal receiver. The pre-computing before encryption consumes 9.56 s. Note that, JL transform is only required on the sender side, and random permutation is conducted for E_P, E_J, and Θ on the sender side and only for E_P″ on the receiver side. All experiments were implemented on a personal computer with a 3.20 GHz Intel i5 processor, 4 GB memory, and Windows 7 operating system.

Table 3.

Execution time of different operations (seconds).

Image owner/sender	Image size	Paillier encryption	JL transform	Random permutation
	256 × 256	1.936	0.185	1.172
	512 × 512	7.752	0.743	4.604
Image owner/receiver	Image size	Inverse permutation		Paillier decryption
	256 × 256	0.483		6.325
	512 × 512	1.956		25.169

JL: Johnson–Lindenstrauss.

Conclusion

In this work, we propose a new privacy-preserving inpainting framework for outsource image and a specific encrypted-image inpainting scheme, which can not only repair scratches and remove undesirable objects in images seamlessly but also can protect the user privacy through encrypting image contents toward image restorer. Paillier encryption and JL transform are both applied by content owner to generate encrypted results for the damaged image. The inpainting mechanism of our scheme is based on block matching and patch filling for the marked target region according to priority order. Since JL transform can preserve Euclidean distance between two vectors before and after encryption, the best-matching block with the smallest distance to current block can be found in source region and utilized for patch filling in the Paillier-encrypted image by image restorer. To further eliminate the possible mosaic effect after decryption, weighted mean filtering for the intermediate, inpainted image in encrypted domain is conducted based on homomorphic properties of addition in Paillier cryptosystem. After image decryption with correct secret key, content owner or authorized receiver can obtain the final inpainted image in plaintext domain. Experimental results demonstrate that the proposed encrypted-image inpainting scheme not only achieves comparable performance of inpainted-image quality with those typical inpainting schemes for plaintext images but also realizes privacy preserving for image content owner effectively due to the complete encrypted-domain operation.

Our current work belongs to non-learning-based inpainting method with privacy-preserving capability. However, learning-based methods can achieve superior global semantic structures of inpainted results, especially with rapid development of deep learning technique. Therefore, in the future, how to effectively and efficiently achieve the learning-based, privacy-preserving image inpainting deserves in-depth investigations. Some works studied privacy-preserving deep learning with homomorphic cryptosystem^45,46 and utilized asynchronous stochastic gradient descent as applied to neural networks, combining with the additively homomorphic encryption, which are helpful to our future work. In addition, functional encryption supports the restricted secret keys that enable a key holder to learn a specific function of encrypted data, but learn nothing else about the data, ⁴⁷ which may be suitable well to solve the problem of block matching (i.e. a specific function) in encrypted domain. Hence, further works also include realizing encrypted block matching through functional encryption and achieving the noise-resisting robustness of privacy-preserving inpainting.