Differential Privacy Protection of Face Images Based on Region Growing

Since its nascency, facial recognition has attracted much attention for the intuitiveness, uniqueness, and privacy of face images. The public cautiously enjoy the convenience of facial recognition, while worrying about whether their privacy and rights will be violated someday. With the commercialization of facial recognition, consumers are calling for effective regulation of the technology. Many scholars and organizations have worked to promote relevant legislations. Against this backdrop, the United States Government Accountability Office (U.S. GAO) released two reports: Facial Recognition Technology: Federal Law Enforcement Agencies Should Better Assess Privacy and Other Risks, and Facial Recognition Technology: Privacy and Accuracy Issues Related to Commercial Uses. In China, the Public Research Report of Facial Recognition Applications shows that, more than 60% of the respondents feel that facial recognition has been misused, and over 30% expressed that they have suffered privacy leak or financial loss due to the misuse of facial recognition. Therefore, information technology is a mixed blessing. How to make good use of the technology is a worldwide concern. Owing to the rapid development of information technology and multimedia technology, it is increasingly easy to acquire and share digital face images. Users can upload the photos in their mobile phones or digital cameras to social network platforms like Twitter, Pinterest, LinkedIn, or WeChat. Statistics have shown that more than 3.2 billion face images are shared by users each day on the major social network platforms across the globe. Besides, countless face images are generated from videos. These digital images contain lots of sensitive personal information. If they are collected and analyzed by malicious third-parties, privacy leak and other losses will be beyond measure [1].

In related reports, some stakeholders express concerns about the privacy issues related to the commercial use of facial recognition. The technology may publicly identify and track people without being noticed by them, and may collect, use, and share their personal data. However, some working in the industry argue that facial recognition will not bring new or special privacy risks, and the risks of the technology are controllable.

The National Telecommunications and Information Administration (NTIA) once organized a test on multiple parties. Some participants worried that facial recognition may threaten personal privacy, because it reduces the anonymity of individuals in public or commercial locations (such as pavement or stores). The participants also expressed the concern that facial recognition may be used to individuals in public, and erode personal privacy. Industry insiders revealed that facial recognition has not been widely used to track consumers in business environments.

The Center for Democracy and Technology announces that most people are willing to be facially identified in public by some people or enterprises. But they do not want their faces to be linked with their names, not to mention associating their faces with other data, such as network behavior, and travel plan. If facial technology is widely adopted in public, and if the recognized faces are shared between enterprises, the consumer movement from one place to another will be tracked any time by a network of cameras. A representative of World Privacy Forum wore that, most consumers will find their privacy be violated, if their activities are tracked by security cameras for marketing. Similarly, the staff of the Federal Trade Commission reported that, consumers will face higher privacy risks, if enterprises start tracking consumers in stores, using collected digital images.

Another widely concerned issue is that consumers will find it impossible to opt out if facial technology is popularized, even if they are notified of the right to reject facial recognition. In many cases, facial recognition is applied to commercial identity recognition or verification, without the knowledge or consent from consumers. This issue has been noticed by some industry trade organizations, which remain cautious about using facial recognition without informed consent from consumers. Computer and Communications Industry Association suggested that, when an enterprise matches face images with names and curriculum vitae through facial recognition, the whole process should remain transparent, and the relevant parties must be given the right to opt out.

Market surveys, patent data, as well as the growing participation in the Facial Recognition Vendor Test (FRVT) organized by the National Institute of Standards and Technology (NIST), indicate that a rising number and types of enterprises are adopting facial recognition. Facial recognition often relies on the acquisition of massive face images (face image databases). Focusing on the massive personal data in such databases, privacy protection organizations, government agencies, the academia, and some industry representatives have expressed concerns over the collection, use, and sharing of personal data by commercial entities.

Face image databases can be sold or shared by all parties, but the selling range remains unknown. The data associated with facial recognition may be sold or shared, often without the knowledge or consent from the affected parties. In recent years, there is a surge in the total amount of personal data collected and shared by resellers and other enterprises, which exacerbates the public concern over this issue.

Privacy is a word with emotional color. Different people have different understandings of this word. According to the International Organization for Standardization (ISO), privacy refers to the features that distinguish individuals or groups from other individuals and groups. Different countries have different legal definitions of privacy. The definition of privacy also varies with objects (individuals, enterprises, governments, etc.). For digital images, sensitive information can be a specific person or object in the original image, a face or fingerprint, embedded information (the location and creation time of the image), or the region of interest (ROI) in the eyes of the image owner. How to publish and analyze images without disclosing sensitive information is the main purpose of privacy protection.

The above privacy issues can be solved through image data query under privacy protection. For the image data released on the social network, the privacy can be usually protected by k-anonymity, access control, and privacy encryption. Fung et al. [2] and Xiao and Tao [3] proposed the k-same method under the anonymization mechanism. Their method anonymizes the published grayscale image, reducing the probability that the attacker re-identifies the user with the published image to less than 1/k. However, the traditional anonymization mechanism has a prominent defect: Before data processing, researchers must set lots of prior conditions for the attacker’s background knowledge and attack models. But these conditions are not fully established in reality. For example, Li et al. [4] relied on access control to restrict user access to social network images, and to control the number of transfers and accesses of the images published on the social network. Despite realizing the goal of privacy protection, the access-oriented protection is merely a superficial privacy protection approach for images. If the attacker has a certain background knowledge, he/she will be able to acquire user images and the relevant privacy information. Terrovitis et al. [5] carried out same-state encryption of the grayscale image to prevent the re-identification of the communication process. Nevertheless, the data encryption algorithms are developed based on some assumptions of the attacks. The existing algorithms are quickly phased out, due to the continuously updating attack modes. Sweeney [6] revealed that attackers can identify sensitive personal information (diseases, and address) from anonymous images on Facebook by deriving the social security number (SSN) of the people in the anonymous images from the extra Friendster feature of Facebook. So, is there any technique that can protect personal privacy in spatial data without the background knowledge of an attacker? This is the focus of image data publication based on differential privacy.

In 2006, Dwork [7] invented differential privacy, which disturbs sensitive data by adding noise to the output. Differential privacy can limit the further reasoning ability of the attacker by hiding the impact of a single record, i.e., the output probability of the same result does not change significantly, whether the record is in the dataset. Therefore, differential privacy does not make any assumption for any potential attacker’s background knowledge. This is better than other privacy protection technologies. Dwork further investigated differential privacy in a series of theses [8-12], and proposed its implementation mechanism [13, 14]. McSherry [15] pointed out that the differential privacy algorithm for complex privacy issues need to satisfy two combined features: sequence combination and concurrent combination. In recent years, differential privacy is mainly applied in data publication. To protect data publication with differential privacy, the main issues is to ensure the accuracy of the released data or query results, while fulfilling the conditions of differential privacy. The relevant research mainly focuses on the publication mechanism and algorithm complexity. The main research approach is quantification based on calculation theory and learning theory. Based on the realization environment, data publication protected by differential privacy can be divided into interactive data publication and non-interactive data publication [13]. The representative interactive data publication (query) methods are as follows: Roth and Roughgarden [16] presented a Median algorithm that can respond to multiple queries. Hardt and Rothblum [17] developed a private multiplicative weights (PMW) mechanism that increases the number of queries. Gupta et al. [18] put forward a universal iterative dataset creation (IDC) framework. Fan and Xiong [19] designed a FAST algorithm based on filtering and adaptive sampling. Kellaris et al. [20] designed a flow data publication algorithm with an unlimited number of queries. When it comes to non-interactive data publication, histogram publication is the most widely adopted technique. The representative strategies include Xiao et al.’s [21] Privelet algorithm, Xu et al.’s [22] Noise First and Structure First algorithms, Li et al.’s [23] matrix mechanism, and Yuan et al.’s data- and workload-aware (DAWA) algorithm [24]. Due to the complexity of image data, the research of sensitive information in the images protected by differential privacy is still in the exploratory stage.

The real domain matrix is a common representation of images. Any pixel in the image can be mapped to a value at the corresponding position of the two-dimensional (2D) matrix. The most direct approach is to add a Laplace noise to all values in the matrix. Although this approach can satisfy ε-differential privacy, the disturbed image will be excessively distorted and weakly available. Fourier transform and wavelet transform are often adopted to compress images. Zhang et al. [25] proposed an image compression method based on discrete Fourier transform, which adds corresponding Laplace noise to the compressed image. Despite reducing the noise error, their method introduces reconstruction error to image compression. Considering the noncorrelation between data in image matrix, Nissim et al. [26] converted the grayscale matrix into a one-dimensional (1D) sequential data flow through image segmentation, modeled the data flow with sliding window model, and dynamically distribute privacy budget based on the data similarity between adjacent sliding windows. In this way, the privacy protection of images is achieved. However, this highly feasible approach faces two problems: the overall operation is confined in the 1D space, and Laplace noise covers the entire image.

Today’s differential privacy methods for face image publication mostly change the data in the original matrix $X_{m \times n}$ through reconstruction (e.g., Fourier transform or wavelet transform), disturb the changed data by adding Laplace noise, and restore the disturbed data to obtain a noisy matrix $\mathrm{X}_{\mathrm{m} \times \mathrm{n}}{ }^{\prime}$. However, two errors may occur during the derivation of $\mathrm{X}_{\mathrm{m} \times \mathrm{n}}{ }^{\prime}$: the noise error LE($\mathrm{X}_{\mathrm{m} \times \mathrm{n}}{ }^{\prime}$) brought by the Laplace mechanism, and the reconstruction error RE($\mathrm{X}_{\mathrm{m} \times \mathrm{n}}{ }^{\prime}$) produced in the reconstruction of the original data. Hence, the overall error Error($\mathrm{X}_{\mathrm{m} \times \mathrm{n}}{ }^{\prime}$) of the released face image $\mathrm{X}_{\mathrm{m} \times \mathrm{n}}{ }^{\prime}$ can be expressed as:

$\operatorname{Error}\left(X_{m \times n}{ }^{\prime}\right)=L E\left(X_{m \times n}{ }^{\prime}\right)+R E\left(X_{m \times n}{ }^{\prime}\right)$           (12)

To reduce noise, the above-mentioned reconstruction methods (Fourier transform and wavelet transform) essentially modify the 2D data extracted from the face image, and add noise to the modified data. None of these methods can avoid the reconstruction error RE($\mathrm{X}_{\mathrm{m} \times \mathrm{n}}{ }^{\prime}$).

Therefore, this paper inherits the approach of Liu et al. [1]: rather than change the data in the 2D matrix, implement the reconstruction from the perspective of structure. Without changing the original data, this approach effectively avoids RE($\mathrm{X}_{\mathrm{m} \times \mathrm{n}}{ }^{\prime}$). Hence, the following conclusion can be drawn:

$\operatorname{Error}\left(X_{m \times n}^{\prime}\right)=L E\left(X_{m \times n}^{\prime}\right)$            (13)

On differential privacy of data publication, the main research focus lies in the publication method of non-interactive data. In this method, the ε effect range covers the entire image, such that the noise level is the same across the image. In reality, however, the sensitive information of a face image clusters in specific regions. For an image, different regions need different degrees of privacy protection. Therefore, this paper tries to protect the privacy of face images by combining the differential privacy of interactive data publication with the image segmentation technology. Under the premise of meeting $\varepsilon$-differential privacy, the integrated method reduces the influence of Laplace noise on the privacy protection image, and strikes a balance between image availability and degree of privacy protection.

3.1 LAP algorithm

This paper designs the LAP algorithm based on Laplace mechanism. Without changing the original data, the LAP algorithm directly disturbs the values in the 2D matrix of the original image with Laplace noise, and publishes the disturbed image straightforwardly.

Drawing on image segmentation theory, each pixel x_ij in the grayscale matrix $X_{m \times n}$ of the original image is treated as an independent entity. The pixels do not interfere with each other, and the privacy budget is distributed evenly. Then, each $\mathrm{x}_{\mathrm{ij}}(1 \leq \mathrm{i} \leq \mathrm{m}, 1 \leq \mathrm{j} \leq \mathrm{n})$ consumes the privacy budge of the size $\varepsilon /(m \times n)$. In the LAP algorithm, the overall error induced by Laplace noise can be expressed as:

$\begin{aligned} \operatorname{Error}\left(X_{m \times n}^{\prime}\right)=& E \sum_{i=1}^{i=m}\left(\sum_{j=1}^{j=n}\left(x_{i j}^{\prime}-x_{i j}\right)^{2}\right) \\ &=E \sum_{i=1}^{i=m}\left(\sum_{j=1}^{j=n}\left(x_{i j}-x_{i j}+\operatorname{lap}\left(\Delta Q \times m \times \frac{n}{\varepsilon}\right)\right)^{2}\right) \\ &=2 m n(\Delta Q \times m \times n / \varepsilon)^{2} \end{aligned}$              (14)

Although the LAP algorithm satisfies ε-differential privacy, a huge noise error will occur when the algorithm is adopted to protect image privacy, if the image is too large. In this case, the noisy image will be weakly available.

3.2 Publication method based on region growing

To control the effect of noise error on the privacy protection of image publication, this paper proposes an image publication algorithm called region growing publication (RGP), which combines region growing with differential privacy technique. In traditional region growing rule, the mean intensity difference between the seed point and a surrounding pixel is compared with the given threshold to judge if the pixel should be merged into the seed point. That is, the growth rule can be expressed as: 

$\left|x_{i \pm 1, j \pm 1}-x_{i j}^{R}\right|<T h$               (15)

where, $\mathrm{x}_{\mathrm{i} \pm 1, \mathrm{j} \pm 1}$ is the grayscale of the surrounding pixel; $x_{i j}^{R}$ is the mean intensity of region R with x_ij as the seed point; Th is the given threshold. Formula (15) reveals two deficiencies with the traditional region growing method. Firstly, the object to be merged is merely a pixel, which carries very limited information, as the most basic unit of the image. The lack of information will bias the final result of region merging. To solve the problem, this paper divides the face image $X_{m \times n}$ into multiple non-intersecting sub-images:

$X_{m \times n}=\left[\begin{array}{cccc}x_{11}, x_{12}, & \cdots & x_{1 n} \\ \vdots & \ddots & \vdots \\ x_{m 1}, x_{m 1}, & \cdots & x_{m n}\end{array}\right]=\left[\begin{array}{cccc}T_{11}, T_{12}, & \cdots & T_{1 J} \\ \vdots & \ddots & \vdots \\ T_{I 1}, T_{I 1}, & \cdots & T_{I J}\end{array}\right]$        (16)

Any sub-image $\mathrm{T}_{\mathrm{ij}}(1 \leq \mathrm{i} \leq \mathrm{I}, 1 \leq \mathrm{j} \leq \mathrm{J})$ contains multiple pixels. Hence, the non-intersecting sub-images T_ij could carry lots of information of the original image. The division is nondestructive and reversible (Figure 3).

3.png

Figure 3. Dividing the original image into multiple sub-images

Secondly, the key of region growing is the definition of growth rule. Due to the natural complexity of face images, the growth rule should be configured in the light of the various attributes of the original image. The traditional growth rule mainly relies on the grayscale difference. However, the grayscale of a single pixel cannot reflect the rich information of the original image. To solve the problem, this paper takes sub-images as the basic unit of region growing. The sub-images retain most of the features of the original image, namely, brightness, contrast, structure, color, texture, and spatial distribution. To further improve the accuracy of region merging with sub-images as the basic unit, this paper puts forward a brand-new growth rule called fusion similarity measurement mechanism (FSMM).

After being converted into a grayscale matrix, the original image becomes meaningful in mathematical calculation. Let X and Y be the grayscale matrices of two adjacent sub-images, respectively (During region growing, sub-image Y can be any of the eight adjacent sub-images of sub-image X), $\mathrm{X}=\left[\begin{array}{ccc}\mathrm{X}_{1} & \cdots & \cdots \\ \cdots & \ddots & \cdots \\ \cdots & \cdots & \mathrm{X}_{\mathrm{c}}\end{array}\right], \mathrm{Y}=\left[\begin{array}{ccc}\mathrm{Y}_{1} & \cdots & \cdots \\ \cdots & \ddots & \cdots \\ \cdots & \cdots & \mathrm{Y}_{\mathrm{c}}\end{array}\right]$. Then, the similarity between X and Y can be measured by Euclidean distance:

$d(X, Y)=\sqrt[2]{\sum_{i=1}^{n}\left(X_{i}-Y_{i}\right)^{2}}$    (17)

Many scholars have adopted Euclidean distance to measure the similarity between two matrices, and to regulate region growing. The measurement can accurately characterize the difference between two sub-images in mathematical properties. This difference is directly exhibited in terms of image colors. However, the similarity rule, which solely considers the mathematical difference between grayscale matrices, cannot fully demonstrate the other properties of the image.

Below is an example illustrating the limitation of Euclidean distance as region growing rule: Suppose there are three grayscale matrices $\mathrm{T}_{1}=\left[\begin{array}{lll}0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{array}\right], \mathrm{T}_{2}=\left[\begin{array}{ccc}7 & 6 & 3 \\ 15 & 20 & 11 \\ 6 & 3 & 5\end{array}\right]$, and $\mathrm{T}_{3}=\left[\begin{array}{ccc}0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 255\end{array}\right]$. The Euclidean distances between T₁ and T₂, and T₁ and T₃ are denoted as θ₁ and θ₂, respectively. Since θ₁<θ₂, T₁ is more similar to T₂. However, after the matrices are converted to grayscale images, T₁ is more similar to T₃ even in naked eyes. In this example, images T₁ and T₃ have very similar colors. However, their Euclidean distance (color eigenvalue) is exaggerated by a salient eigenvalue. The mis-judgement is attributed to the fact that Euclidean distance (color eigenvalue) is solely considered to compute the grayscale matrices of the two images. The salient value of T₃ could be the result of texture or shape features of the image.

To solve the above problem, the Jaccard similarity index is introduced to compute the similarity θ between the grayscale matrices of the two images. The Jaccard similarity index, a metric of the similarity between two sets, is defined as the number of pixels in the interaction between two sets, divided by the number of pixels in the union of two sets: 

$\rho(X, Y)=|X \cap Y| /|X \cup Y|$         (18)

In this paper, the Jaccard similarity index is taken as the optimization value in the result of formula (17):

$\theta=d(X, Y) / \rho(X, Y)+\sigma$              (19)

where, d(X,Y) is the Euclidean distance between the grayscale matrices of two images; ρ(X,Y) is the Jaccard similarity index between the grayscale matrices of two images; σ is a small positive number that prevents the denominator from being zero.

The above-mentioned example can prove that the θ value derived from both Euclidean distance and Jaccard similarity index can largely reflect the similarity between the grayscale matrices of two images, and serve as the growth rule. However, some special cases are found during the experiments, in which the above formula is not applicable. Another example was given to explain the influence of the special cases.

Suppose two local grayscale matrices $\mathrm{T}_{1}=\left[\begin{array}{lll}7 & 9 & 8 \\ 4 & 3 & 7 \\ 1 & 5 & 6\end{array}\right]$, and $\mathrm{T}_{2}=\left[\begin{array}{lll}8 & 7 & 9 \\ 3 & 4 & 7 \\ 6 & 5 & 1\end{array}\right]$ are obtained from the same image. The similarity θ between them, which is calculated by formula (19), is far smaller than the expectation θ' given during the explements. θ^' is a preset threshold. If θ>θ', the grayscale matrices are not similar; otherwise, the grayscale matrices are similar. It can be observed from the experimental values in matrices T₁ and T₂ that formula (19) cannot calculate the correct θ value, due to its neglection of spatial distribution features of the images. Hamming distance is often employed to measure the difference between two spatial vectors of the same structure and size. This criterion sequentially compares the values in the corresponding positions of two spatial vectors X and Y. If X_i=Y_i, value is 0; otherwise, the value is 0. After all the corresponding positions of two spatial vectors have been compared, all the ones will be cumulated to obtain the Hamming distance between the two spatial vectors: 

$\mu(X, Y)=\sum_{i=1}^{n} X_{i} \bigoplus Y_{i}$          (20)

In this paper, the values are extracted from each grayscale matrix by formula (1). Thus, the values in the grayscale matrices are approximate. The color information of the images cannot be truthfully reflected, with Hamming distance as the only criterion. What is worse, the Hamming distance cannot be directly applied to formula (19).

To solve these problems, Hamming distance is combined with the result of perceptual hash algorithm into a disturbance φ for formula (19), further improving the correctness of the similarity θ between grayscale matrices. Combining formulas (19) and (20), the similarity θ between the grayscale matrices of two images can be expressed as: 

$\theta=\varphi(d(X, Y) / \rho(X, Y)+\sigma)$         (21)

Suppose the two contrastive spatial vectors are grayscale matrices X and Y of face images. Each matrix contains c pixels. Then, the disturbance φ can be calculated by: 

$\varphi=\left\{\begin{array}{cc}\theta^{\prime} \times(\rho(X, Y)+\sigma) / d(X, Y), & \mu(X, Y)<0.078 \times c \\ 1, & 0.078 \times c \leq \mu(X, Y) \leq 0.156 \times c \\ 1 / \lg \times(m \times n-\mu(X, Y)), & \mu(X, Y)>0.156 \times c\end{array}\right.$                 (22)

where, c is sample size; θ' is a preset threshold.

Structural similarity (SSIM) is a full reference image quality evaluation index. The traditional image quality metrics, such as mean squared error (MSE) and peak signal-to-noise ratio (PSNR), deviate from the actual visual perception of human eyes. By contrast, SSIM considers the visual features of human eyes, and adapts to the visual perception of humans. MSE and PSNR evaluates absolute errors, while SSIM, a perception-based metric, takes account of the fuzzy perceptual changes of image structure. The SSIM includes some phenomena related to perceptual changes, including brightness and contrast. The structural information refers to the internal dependence between pixels, especially the spatially close ones. The dependence carries important information about the visual perception of objects.

The SSIM ranges from 0 to 1. The greater the SSIM, the higher the similarity between two images. Based on the SSIM theory, the structural information is defined from the angle of image composition as an attribute reflecting the object structure in the scene, and independent of brightness and contrast, while distortion is modeled as the combination of brightness, contrast, and structure. Let X and Y be the reference image and the distorted image. Then, the following definitions can be established:

$l\left(T_{i \times j}, T_{(i \pm 1) \times(j \pm 1)} \quad \right)=\left(2 u_{X} u_{Y}+C_{1}\right) /\left(u_{X}^{2}+u_{Y}^{2}+C_{1}\right)$            (23)

$c(X, Y)=\left(2 \sigma_{X} \sigma_{Y}+C_{2}\right) /\left(\sigma_{X}^{2}+\sigma_{Y}^{2}+C_{2}\right)$                (24)

$s(X, Y)=\left(\sigma_{X Y}+C_{3}\right) /\left(\sigma_{X} \sigma_{Y}+C_{3}\right)$                (25)

where, u_X  and u_Y are the mean of images X and Y, respectively, reflecting the brightness of each image; σ_X  and σ_Y are the variances of images X and Y, respectively, reflecting the contrast of each image; C₁, C₂, and C₃ are very small positive integers that prevent the denominator from being zero. Based on the above three information, the SSIM can be calculated by:

$\operatorname{SSIM}(X, Y)=[l(X, Y)]^{\alpha} \cdot[c(X, Y)]^{\beta} \cdot[s(X, Y)]^{\gamma}$            (26)

where, $\alpha,  \beta$, and $\gamma$ are the weights of different eigenvalues. If $\alpha=\beta=\gamma=1, \mathrm{C}_{1}=\left(\mathrm{K}_{1} \mathrm{~L}\right)^{2}, \mathrm{C}_{2}=\left(\mathrm{K}_{2} \mathrm{~L}\right)^{2}, \mathrm{C}_{3}=\mathrm{C}_{2} / 2$, and $\mathrm{K}_{1} \ll 1, \mathrm{~K}_{2} \ll 1$, with L being the dynamic range of the image, formula (26) can be simplified as: 

$\operatorname{SSIM}(X, Y)=\left(2 u_{X} u_{Y}+C_{1}\right)\left(2 \sigma_{X} \sigma_{Y}+C_{2}\right) /\left(u_{X}^{2}+u_{Y}^{2}+C_{1}\right)\left(\sigma_{X}^{2}+\sigma_{Y}^{2}+C_{2}\right)$                 (27)

To sum up, the FSMM mechanism can be expressed as: 

$\operatorname{FSMM}(X, Y)=\frac{\varphi \times(d(X, Y) / \rho(X, Y)+\sigma) \times\left(2 u_{X} u_{Y}+C_{1}\right) \times\left(2 \sigma_{X} \sigma_{Y}+C_{2}\right)}{\left(u_{X}^{2}+u_{Y}^{2}+C_{1}\right) \times\left(\sigma_{X}^{2}+\sigma_{Y}^{2}+C_{2}\right)}$                (28)

The innovation of RGP algorithm lies in merging similar sub-images into one region via region growing. When RGP and LAP have the same privacy budget, RGP can produce a smaller noise error during privacy protection of images. During image growing, the face image $X_{m \times n}$ is segmented into k sub-images of the same structure. Then, a sub-image T_ij is selected randomly as the seed point, and assigned a privacy budget of $\varepsilon / \mathrm{k}$. Then, LAP is called to add a Laplace noise to the produce $\mathrm{T}_{\mathrm{ij}}^{\prime}$. Whether an adjacent $\mathrm{T}_{(\mathrm{i} \pm 1)(\mathrm{j} \pm 1)}$ needs to be merged into the growing region of the current seed point depends on whether the gap between $\mathrm{T}_{\mathrm{ij}}^{\prime}$ and $\mathrm{T}_{(\mathrm{i} \pm 1)(\mathrm{j} \pm 1)}$ satisfies the preset threshold. If $\operatorname{FSMM}\left(\mathrm{T}_{\mathrm{ij}^{\prime}}^{\prime} \mathrm{T}_{(\mathrm{i} \pm 1)(\mathrm{i} \pm 1)}\right) \leq \mathrm{Th}$ (Th is the preset threshold), $\mathrm{T}_{(\mathrm{i} \pm 1)(\mathrm{j} \pm 1)}\quad$ will be replaced with $\mathrm{T}_{\mathrm{ij}}^{\prime}$ before publication. Once no more qualified sub-image can be merged with T_ij being the seed point, a new seed point will be selected randomly from the remaining sub-images, and the above process will be repeated until the entire image is fully grown.

Note that no privacy budget is consumed as $\mathrm{T}_{(\mathrm{i} \pm 1)(\mathrm{j} \pm 1)}$ is replaced with $\mathrm{T}_{\mathrm{ij}}^{\prime}$. Hence, the privacy budget assigned to $\mathrm{T}_{(\mathrm{i} \pm 1)(\mathrm{j} \pm 1)}\quad$ will be retained for use in subsequent operations. 

To facilitate understanding, an example was provided to explain the implementation of RGP. The sub-image division is displayed in Figure 4: $\mathrm{X}_{\mathrm{m} \times \mathrm{n}}=\left(\mathrm{T}_{11}, \mathrm{~T}_{12}, \mathrm{~T}_{13}, \ldots, \mathrm{T}_{55}\right)$. Out of the sub-images, a random sub-image is selected as the seed point, and assigned a privacy budget of the size $\varepsilon / 25$. As shown in Figure 5, $\mathrm{T}_{22}^{\prime}$ serves as the seed point, i.e., the disturbance obtained by adding Laplace noise to T₂₂. In this case, the state of T₂₂ is labeled. After the seed point is selected, a chain will be created to temporarily store the seed points and candidate seed points.

Next, the seed point will be compared with each of the eight adjacent sub-images via region growing (Figure 6). If a sub-image is sufficiently similar and in line with the merging condition, replacement will be carried out, and the sub-image will be added to the temporary chain list as a candidate seed point. As shown in Figure 7, T₂₃ is the only sub-image whose similarity with the seed point satisfies the preset threshold. Hence, T₂₃ is replaced with $\mathrm{T}_{22}^{\prime}$, the current seed point is removed from the chain list, and the candidate seed point is selected as the new seed point. The above process is repeated until the temporary chain list is empty.

4.png

Figure 4. Image division

5.png

Figure 5. Seed point selection

6.png

Figure 6. Traversing adjacent regions

7.png

Figure 7. Replacement

8.png

Figure 8. Result of local region growing

9.png

Figure 9. Result of global region growing

Figure 8 shows the labeled region after one region growing. A seed is selected from the unlabeled region, and the above steps are repeated, until all sub-images are labeled. Figure 9 shows the noisy grayscale matrix after four region growing operations.

The specific implementation of RGP is summarized as follows:

Algorithm 1: RGP

Inputs: Original image X, privacy budget $\varepsilon$, preset parameters a and b, and expectation for sub-image similarity Th

Output: Image X' satisfying differential privacy

1.     Read original image X, and convert the image into a grayscale matrix $X_{m \times n}$ by formula (1).
2.     Segment the grayscale matrix $X_{m \times n}$ into a set T₁[a][b] of sub-images with the same structure, according to preset parameters a and b.
3.     Create T₂[a][b]={0} to record whether the state of a submatrix is labeled during region growing. 
4.     Create a chain list list to temporarily store the current seed point and candidate seed points. 
5.     s=0; 
6.     ε_left= ε; 
7.     While(z<a*b)
8.       if list_head==NULL
9.          Randomly select T₁[i][j] as the seed point
10.             if T₂[i][j]=1 then
11.             break;
12.             else
13.           i=head->x; 
14.               j=head->y; 
15.               p=head; 
16.               head=p->next; 
17.               free(p); 
18.        T₂[i][j]=1; 
19.  $\mathrm{T}_{1}^{\prime}[\mathrm{i}][\mathrm{j}]=\mathrm{T}_{1}[\mathrm{i}][\mathrm{j}]+\operatorname{lap}\left(\Delta \mathrm{Q} \times(\mathrm{a} * \mathrm{~b}-\mathrm{s}) / \varepsilon_{\text {left }}\right)$
20.      $\varepsilon_{\text {left }}=\varepsilon_{\text {left }}-\varepsilon_{\text {left }} /(a * b-s)$
21.       s=s+1; 
22.       p=list_head; 
23.       for m=i-1 to i+1 do
24.         for n=j-1 to j+1 do
25.                 If(m>=1&&m<=a&&n>=1 &&n<=b&&T₂[i][j]!=1)
26.         Use FSMM to compute the similarity θ between the current noisy seed point $\mathrm{T}_{1}^{\prime}[\mathrm{i}][\mathrm{j}]$ and $\mathrm{T}_{1}[\mathrm{~m}][\mathrm{n}]$.
27.                  If θ<=Th
28.                  $\mathrm{T}_{1}[\mathrm{~m}][\mathrm{n}]=\mathrm{T}_{1}^{\prime}[\mathrm{i}][\mathrm{j}]$; 
29.                  while(p->next!=NULL)
30.                      if(p->x==m&&p->y==n)
31.                          break; 
32.                      p=p->next; 
33.                      If p==NULL
34.                          Add T₁[m][n] to the chain list.
35.     Merge all the labeled submatrices into a noisy grayscale matrix $X_{m \times n}^{\prime}$.
36.     Convert $X_{m \times n}^{\prime}$ into the privacy protected image X'.

RGP provides a way to protect the privacy of face images based on region growing and differential privacy. Lines 5-7 define two variables and set the termination condition (while circulation). The two variables are z and ε_left. The former ensures that, after the algorithm completes, each sub-image T₁[i][j] will be converted into a noisy sub-image $\mathrm{T}_{1}^{\prime}[\mathrm{i}][\mathrm{j}]$, while ε_left defines the initial value for the allocation of privacy budget ε. Lines 8-18 specifies the seed point selection of region growing. Specifically, Lines 8-11 judge whether T₁[i][j] has been merged to a region. If it has been labeled, it is necessary to choose a new seed point. Lines 12-17 release the labeled seed point from the chain list, and select the next seed point from the candidates. Line 18 changes the state of the current seed point from unlabeled to labeled. Lines 19-21 assign a proper privacy budget and add a noise to the current seed point. Line 22 saves the current seed point to the chain list. Lines 23-25 demand that the adjacent region T₁[m][n] of the seed point should not surpass the image boundary and the labeled state. Lines 26-28 use the FSMM mechanism to compute the similarity between an adjacent region and the seed point, and judge if the former meets the growth rule. If yes, T₁[m][n] will be replaced with $\mathrm{T}_{1}^{\prime}[\mathrm{i}][\mathrm{j}]$. Lines 29-34 judge whether T₁[m][n] that satisfies growth rule exists in the chain list. If not, this region will be added to the chain list, and become a candidate seed point.

Note that Lines 19-21 of RGP provide a dynamic allocation (DA) mechanism for privacy budget. Unlike the common binary allocation mechanism, DA offers a more reasonable solution to the privacy budget allocation during region growing, and reduces the influence of noise on the original data. The DA mechanism can be described as follows:

Suppose each region growing consumes a privacy budget of ε_i={ε₁,ε₂,ε₃,…,ε_m }, each merged region contains s_i={s₁,s₂,s₃,…,s_m} sub-images, and s₁+s₂+s₃+⋯+s_m=k,with  k=a×b being the total number of sub-images. Let $\varepsilon_{\mathrm{i}}^{\mathrm{left}}$ be the residual privacy budget after the completion of state i. Then, the $\varepsilon_{\mathrm{i}}$ and $\varepsilon_{\mathrm{ileft}}$ in any state under the DA mechanism can be expressed as: 

$\varepsilon_{i}=\varepsilon_{i-1}^{l e f t} /\left(k-\sum_{j=1}^{i-1} s_{j}\right)$          (29)

$\varepsilon_{i}^{l e f t}=\varepsilon_{i-1}^{l e f t}-\varepsilon_{i}$           (30)

Theorem 3. In RGP, the consumption of privacy budget will not surpass  ε, i.e., $\varepsilon_{1}+\varepsilon_{2}+\varepsilon_{3}+\cdots+\varepsilon_{\mathrm{m}} \leq \varepsilon$.

Proof: Formula (29) shows that, when $\mathrm{k}-\sum_{\mathrm{j}=1}^{\mathrm{m}-1} \mathrm{~s}_{\mathrm{j}}=1, \varepsilon_{\mathrm{m}-1 \mathrm{left}}=\varepsilon_{\mathrm{m}} .$ Then, $\varepsilon_{\mathrm{mleft}}=0$. In this case, we have:

$\varepsilon_{1}+\varepsilon_{2}+\varepsilon_{3}+\cdots+\varepsilon_{m}=\varepsilon$

When $\mathrm{k}-\sum_{\mathrm{j}=1}^{\mathrm{m}-1} \mathrm{~s}_{\mathrm{j}}>1, \quad \varepsilon_{\mathrm{m}-\mathrm{1left}} / \varepsilon_{\mathrm{m}}>1$. Then, $\varepsilon_{\mathrm{mleft}}>0$, In this case, we have:

$\varepsilon_{1}+\varepsilon_{2}+\varepsilon_{3}+\cdots+\varepsilon_{m}<\varepsilon$

Q.E.D.

Theorem 4. RGP satisfies ε- differential privacy.

Proof: According to Theorem 3:

$\varepsilon_{1}+\varepsilon_{2}+\varepsilon_{3}+\cdots+\varepsilon_{m} \leq \varepsilon$

where, $\varepsilon_{\mathrm{i}}(1 \leq \mathrm{i} \leq \mathrm{m})$ is the privacy budget consumed under each state. According to the differential privacy-parallel combination property (Property 2), RGP satisfies $\varepsilon$- differential privacy.

Q.E.D.

Theorem 5. The error generated by RGP is no greater than that generated by LAP, i.e.:

Error $(R G P) \leq$ Error $(L A P)$

Proof: The DA mechanism of RGP consumes a privacy budget of $\varepsilon_{\mathrm{i}}=\left\{\varepsilon_{1}, \varepsilon_{2}, \varepsilon_{3}, \ldots, \varepsilon_{\mathrm{m}}\right\}$ each time. The number of submatrices affected by $\varepsilon_{\mathrm{i}}=\left\{\varepsilon_{1}, \varepsilon_{2}, \varepsilon_{3}, \ldots, \varepsilon_{\mathrm{m}}\right\}$ can be described by $\mathrm{s}_{\mathrm{i}}=\left\{\mathrm{s}_{1}, \mathrm{~s}_{2}, \mathrm{~s}_{3}, \ldots, \mathrm{s}_{\mathrm{m}}\right\}, \mathrm{s}_{1}+\mathrm{s}_{2}+\mathrm{s}_{3}+\cdots+\mathrm{s}_{\mathrm{m}}=\mathrm{k}$. The Laplace mechanism of LAP consumes a privacy budget of $\varepsilon / \mathrm{k}, \sum_{\mathrm{i}=1}^{\mathrm{k}} \mathrm{s}_{\mathrm{i}}^{\prime}=\mathrm{k}\left(\mathrm{s}_{1}^{\prime}=\mathrm{s}_{2}^{\prime}=\mathrm{s}_{3}^{\prime}=\cdots=\mathrm{s}_{\mathrm{k}}^{\prime}=1\right)$ each time.

Firstly, the maximum possible error of DA mechanism is calculated, revealing that $\mathrm{s}_{1}=\mathrm{s}_{2}=\mathrm{s}_{3}=\cdots \mathrm{s}_{\mathrm{m}}=1$, i.e., m=k. Thus, we have:

$\operatorname{Error}(R G P)_{\max }=\left(\operatorname{lap}\left(\Delta Q / \varepsilon_{1}\right)+\operatorname{lap}\left(\Delta Q / \varepsilon_{2}\right)+\operatorname{lap}\left(\Delta Q / \varepsilon_{3}\right)+\right.$

$\left.\cdots \operatorname{lap}\left(\Delta Q / \varepsilon_{m}\right)\right)_{\max }=\sum_{i=1}^{k} \operatorname{lap}\left(\Delta Q / \varepsilon_{i}\right)=k \times \operatorname{lap}(\Delta Q /$

$(\varepsilon / k))=\operatorname{Error}(L A P)$

The other situations can be judged by formula (30). After the completion of state i, the residual privacy budget of DA mechanism is ε_ileft, while that of Laplace mechanism is $\varepsilon_{\text {ileft }}^{\prime}$. Since DA mechanism allows an s_i>1, and $\mathrm{s}_{1}=\mathrm{s}_{2}=\mathrm{s}_{3}=\cdots \mathrm{s}_{\mathrm{i}-1}=1(1<\mathrm{i}<\mathrm{m})$, we have:

$\varepsilon_{\text {ileft }}-\varepsilon_{\text {ileft }}^{\prime}=\left(\varepsilon-\varepsilon \times \frac{k-\left(i-1+s_{i}\right)}{k}\right)-\left(\varepsilon-\varepsilon \times \frac{k-i}{k}\right)=\varepsilon \times$

$\left(\frac{k-i}{k}-\frac{k-\left(i-1+s_{i}\right)}{k}\right)=\varepsilon \times \frac{s_{i}-1}{k}$

Since $s_{i}>1 \quad, \quad \varepsilon_{\text {ileft }}-\varepsilon_{\text {ileft }}^{\prime}>0$. Thus, $\left(\varepsilon_{i+1}, \varepsilon_{i+2}, \varepsilon_{i+3}, \ldots, \varepsilon_{m}\right)>\varepsilon / k$. It can be seen that Error(RGP)<Error(LAP).

Q.E.D.

3.3 Atypical region growing publication (ARGP)

If the RGP is applied to an image, the merged region through one region growing with T₁₁ as the seed point can be illustrated in Figure 10 (the dark region). From the perspective of the entire image, i.e., removing the limitation on region growing direction, the similarity θ between $\mathrm{T}_{11}^{\prime}$ and each unlabeled sub-image is calculated, and all the qualified sub-images are merged together. But the merged region may not be as expected (Figure 11). Obviously, the current merged region is not continuous in 2D space (RGP cannot yield such a merged region), but every sub-image of the merged region satisfies θ<=Th.

10.png

Figure 10. Region growing direction estimated by RGP

To find more qualified sub-images for the seed point without damaging ε-differential privacy, this paper integrates atypical region growing with differential privacy into a novel privacy protection approach for image publication, denoted as ARGP. Different from traditional region growth strategy, the ARGP does not restrict the growing direction within adjacent sub-images, but searches for qualified sub-images among all unlabeled sub-images, using the exponential mechanism. The specific steps of the ARGP are as follows: 

Algorithm 2. ARGP

Inputs: Original image X, privacy budget ε, preset parameters a and b, and expectation for sub-image similarity Th

Output: Image X' satisfying differential privacy

1.     Read original image X, and convert the image into a grayscale matrix X_m×n by formula (1).
2.     Segment the grayscale matrix X_m×n into a set T₁[a][b] of sub-images with the same structure, according to preset parameters a and b.
3.     Create T₂[a][b]={0} to record whether the state of a submatrix is labeled during region growing. 
4.     ε=ε₁+ε₂; 
5.     s=0; 
6.     ε_left= ε₂; 
7.     While(w<a*b)
8.       If i==0&&j==0
9.           Randomly select T₁[i][j] as the seed point
10.       endif
11.       T₂[i][j]=1; 
12.    $\mathrm{T}_{1}^{\prime}[\mathrm{i}][\mathrm{j}]=\mathrm{T}_{1}[\mathrm{i}][\mathrm{j}]+\operatorname{lap}\left(\Delta \mathrm{Q} \times(\mathrm{a} * \mathrm{~b}-\mathrm{s}) / \varepsilon_{\text {left }}\right)$; 
13.       ε_left=ε_left-ε_left⁄((a*b-s) )
14.       s=s+1; 
15.       Find all unlabeled sub-images T₁[a][b].
16.       Realize the region merging in the traditional direction of region growing of RGP.
17.           Find all unlabeled sub-images T₁[a][b] again.
18.           Use FSMM to compute the similarity θ between $\mathrm{T}_{1}^{\prime}[\mathrm{i}][\mathrm{j}]$ and each T₁[a][b].
19.           $\Delta \mathrm{Q}=\frac{1}{\theta+\sigma}$; 
20.           Select one T₁[a][b] at the probability $\mathrm{P} \propto \exp \left(\frac{\varepsilon_{1} \Delta \mathrm{Q}}{2 \Delta \mathrm{u}}\right)$, using the exponential mechanism.
21.           Use FSMM to recalculate the similarity θ between the noisy current seed point $\mathrm{T}_{1}^{\prime}[\mathrm{i}][\mathrm{j}]$ and the selected T₁[a][b].
22.           If θ<=Th
23.               $\mathrm{T}_{1}[\mathrm{a}][\mathrm{b}]=\mathrm{T}_{1}^{\prime}[\mathrm{i}][\mathrm{j}]$; 
24.               i=m; 
25.               j=n;        
26.           else
27.               i=0; 
28.               j=0;   
29.     Merge all the labeled submatrices into a noisy grayscale matrix $X_{m \times n}{ }^{\prime}$.
30.     Convert $X_{m \times n}{ }^{\prime}$ into the privacy protected image X'.

In ARGP, Line 4 divides the privacy budget ε into two parts: a part ε₁ for exponential mechanism, and a part ε₂ for noise addition. Lines 5-7 define two variables and set the termination condition (while circulation). The two variables are w and ε_left. The former ensures that, after the algorithm completes, each sub-image T₁[i][j] will be converted into a noisy sub-image $\mathrm{T}_{1}^{\prime}[\mathrm{i}][\mathrm{j}]$, while ε_left defines the initial value for the allocation of privacy budget ε. Lines 8-14 specifies that, if there is no seed point, an unlabeled sub-image will be selected randomly as the seed point; then, the seed point will be labeled, and added a noise by DA mechanism. Lines 15-16 realize the RGP. Lines 17-20 select a sub-image by the exponential mechanism. Specifically, Line 17 defines the scoring function of exponential mechanism. ARGP intends to select the sub-image more similar to the seed point at a larger probability. Σ is a very small positive number that prevents the denominator from being zero. In Line 18, Δu is the sensitivity of the scoring function. Since adding/removing one record only affects one count of θ, Δu=1. Lines 21-28 use the FSMM mechanism to compute the similarity between the seed point and the selected T₁[m][n]. If the result satisfies the preset threshold, assign the value of $\mathrm{T}_{1}^{\prime}[\mathrm{i}][\mathrm{j}]$ to T₁[m][n], and set it as the new seed point. Otherwise, select a new seed point, and repeat the above process until all sub-images become noisy.

For ARGP, the exponential mechanism does not necessarily lead to the needed optimal solution, but capable of obtaining the optimal or near optimal solution at a high probability. Table 1 shows the test results on the selection probability of the exponential mechanism in ARGP. The test aims to select the minimum of a set of random numbers. Column 1 reports the similarity θ between the seed point and sub-regions. Column 2 reports the scoring function (σ=0.02). The other four columns report the section probabilities of each sub-region at different ε values, and the sum of each column equals or approximates 1 (the error induced by indivisibility). If ε=0, the level of privacy protection is maximized, and all sub-regions are selected at the same probability. With the growth of ε, the selection probability increases with the value of the scoring function ΔQ; the inverse is also true.

11.png

Figure 11. Region growing direction estimated by ARGP

Table 1. Exponential mechanism- minimum selection probability test

Theorem 6. ARGP satisfies ε-differential privacy.

Proof: ARGP divides the privacy budget ε into two parts: ε=ε₁+ε₂, where ε₁ is used to select unlabeled sub-region T by the exponential mechanism; the selection probability is positively correlated with exp $\left(\frac{\varepsilon_{1} \Delta Q}{2 \Delta u}\right)$:

$\operatorname{Pr}[\mathrm{M}(\mathrm{X}, \Delta \mathrm{Q})=\mathrm{T}]=\frac{\exp \left(\frac{\varepsilon_{1} \Delta \mathrm{Q}(\mathrm{X}, \mathrm{T})}{2 \Delta \mathrm{u}}\right)}{\sum_{\mathrm{T}^{\prime} \in O} \exp \left(\frac{\varepsilon_{1} \Delta \mathrm{Q}\left(\mathrm{X}, \mathrm{T}^{\prime}\right)}{2 \Delta \mathrm{u}}\right)}$               (31)

For the given X and its adjacent region X', the following can be derived from formula (31) for any $\mathrm{T} \in \mathrm{O}$:

$\frac{\operatorname{Pr}[M(X, \Delta Q)=T]}{\operatorname{Pr}\left[M\left(X^{\prime}, \Delta Q\right)=T\right]}=\frac{\frac{\exp \left(\frac{\varepsilon_{1} \Delta Q(X, T)}{2 \Delta u}\right)}{\sum_{T^{\prime} \in O} \exp \left(\frac{\varepsilon_{1} \Delta Q\left(X, T^{\prime}\right)}{2 \Delta u}\right)}}{\frac{\exp \left(\frac{\varepsilon_{1} \Delta Q\left(X^{\prime}, T\right)}{2 \Delta u}\right)}{\sum_{T^{\prime} \in O} \exp \left(\frac{\varepsilon_{1} \Delta Q\left(X^{\prime}, T^{\prime}\right)}{2 \Delta u}\right)}}$

$=\left(\frac{\exp \left(\frac{\varepsilon_{1} \Delta Q(X, T)}{2 \Delta u}\right)}{\exp \left(\frac{\varepsilon_{1} \Delta Q\left(X^{\prime}, T\right)}{2 \Delta u}\right)}\right) \times\left(\frac{\sum_{T^{\prime} \in O} \exp \left(\frac{\varepsilon_{1} \Delta Q\left(X^{\prime}, T^{\prime}\right)}{2 \Delta u}\right)}{\sum_{T^{\prime} \in O} \exp \left(\frac{\varepsilon_{1} \Delta Q\left(X, T^{\prime}\right)}{2 \Delta u}\right)}\right)$

$=\exp \left(\frac{\varepsilon_{1}\left(\varepsilon_{1} \Delta Q(X, T)-\varepsilon_{1} \Delta Q\left(X^{\prime}, T\right)\right)}{2 \Delta u}\right) \times\left(\frac{\sum_{T^{\prime} \in o} \exp \left(\frac{\varepsilon_{1} \Delta Q\left(X^{\prime}, T^{\prime}\right)}{2 \Delta u}\right)}{\sum_{T^{\prime} \in o} \exp \left(\frac{\varepsilon_{1} \Delta Q\left(X, T^{\prime}\right)}{2 \Delta u}\right)}\right)$

$\leq \exp \left(\frac{\varepsilon_{1}}{2}\right) \times\left(\frac{\sum_{T^{\prime} \in O} \exp \left(\frac{\varepsilon_{1}}{2}\right) \times \exp \left(\frac{\varepsilon_{1} \Delta Q\left(X, T^{\prime}\right)}{2 \Delta u}\right)}{\sum_{T^{\prime} \in O} \exp \left(\frac{\varepsilon_{1} \Delta Q\left(X, T^{\prime}\right)}{2 \Delta u}\right)}\right)$

$\leq \exp \left(\frac{\varepsilon_{1}}{2}\right) \times \exp \left(\frac{\varepsilon_{1}}{2}\right) \times\left(\frac{\sum_{T^{\prime} \in O} \exp \left(\frac{\varepsilon_{1} \Delta Q\left(X, T^{\prime}\right)}{2 \Delta u}\right)}{\sum_{T^{\prime} \in O} \exp \left(\frac{\varepsilon_{1} \Delta Q\left(X, T^{\prime}\right)}{2 \Delta u}\right)}\right)=\exp \left(\varepsilon_{1}\right)$

Hence, the exponential-based selection of unlabeled sub-region of ARGP satisfies ε₁-differential privacy. From the proof of Theorem 4, it can be learned that the noise addition of ARGP satisfies ε₂-differential privacy. Overall, ARGP satisfies ε-differential privacy in the whole process.

Q.E.D.

Theorem 7. When an image is divided on equal conditions, the number z_j of sub-images to be merged to a seed point in ARGP must be greater than or equal to the number s_i of sub-images to be merged to the same seed point in RGP, under ideal conditions, that is, Error(ARGP)≤Error(RGP).

Proof: Theorem 7 can be proved by contradiction. It is assumed that z_j<s_i.

In ARGP, there exists a sub-image T₀, whose merged region is set A, i.e., $\mathrm{T}_{0} \in \mathrm{A}$, with z_j being the number of elements in set A. In RGP, the merged region of the same sub-image T₀ is set B, i.e., $\mathrm{T}_{0} \in \mathrm{B}$, with s_i being the number of elements in set B. If z_j<s_i holds, then there must exist a sub-image T_x satisfying T_x∉A in ARGP and T_x∈B in RGP.

From the growing direction and seed point selection of the two algorithms, if T_x∈B, then there must exist T_x∈A. Thus, z_j<s_i is invalid.

Q.E.D.

12.png

Figure 12. z_j=s_i

The conclusion of Theorem 7 can be further analyzed by dividing z_j≥s_i into z_j=s_i and z_j>s_i. Suppose there is an image will produce δ merged regions by RGP or ARGP (Figure 12; the merged regions are in dark color). If the exponential mechanism cannot obtain the qualified sub-images for merging, then any z_j=s_i. From the proof of Theorem 5, we have:

$\left\{\begin{array}{rlc}\text { Error }(A R G P)\max=\operatorname{Error}(R G P)_{\max }=\operatorname{Error}(\mathrm{Lap}), & \delta=0 \\ \operatorname{Error}(A R G P)=\operatorname{Error}(R G P)<\operatorname{Error}(\operatorname{Lap}), & 1 \leq \delta \leq k / 2 \text { or }-1 \leq \delta \leq\left(a^{*} b\right) / 2\end{array}\right.$

As shown in Figure 13, if the exponential mechanism can obtain any qualified sub-images, which are not connected with the current merged region, then z_j>s_i. It can be derived from formula (30) that:

$\varepsilon_{R G P l e f t}-\varepsilon_{A R G P l e f t}=\left(\varepsilon-\varepsilon \times \frac{k-\left(\gamma-1+s_{i}\right)}{k}\right)-\left(\varepsilon-\varepsilon \times \frac{a * b-\left(\gamma-1+z_{j}\right)}{a * b}\right)==\varepsilon *$

$\left(\frac{a * b-\left(\gamma-1+z_{j}\right)}{a * b}-\frac{k-\left(\gamma-1+s_{i}\right)}{k}\right)=\varepsilon \times \frac{s_{i}-z_{j}}{k}$

Since z_j>s_i, ε_RGPleft-ε_ARGPleft<0. Thus, Error(ARGP)<Error(RGP).

Q.E.D.

13.png

Figure 13. z_j>s_i

To solve the privacy protection of face image publication, this paper combines regional growing technique with the Laplace mechanism of differential privacy to add noise to the original image, thereby protecting the sensitive information in face images. Compared with the LAP algorithm, which directly adds Laplace noise to the image, RGP and ARGP can effectively reduce the influence of noise on the protected image, and improve the feasibility of privacy protection on images. Moreover, this paper presents a novel region growing rule: FSMM, and discusses the influence of sub-image size on algorithm results. These conclusions provide an effective reference for other researchers.

It is worth noting that our differential privacy protection approach for face image publication is realized by global noise addition. However, the sensitive information of a face image mostly exists in specific regions (e.g., facial contours, eyes, eyebrows, mouth, and noise). The future work will try to pinpoint the locations of sensitive information, and add noise to these places, aiming to further reduce the noise influence, and enhance the availability of face images after privacy protection.