# Face Image Publication Based on Differential Privacy

Authors: Chao Liu; Jing Yang; Weinan Zhao; Yining Zhang; Jingyou Li; Chunmiao Mu
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

As an information carrier, face images contain abundant sensitive information. Due to its natural weak privacy, direct publishing may divulge privacy. Anonymization Technology and Data Encryption Technology are limited by the background knowledge and attack means of attackers, which cannot completely content the needs of face image privacy protection. Therefore, this paper proposes a face image publishing SWP (sliding window publication) algorithm, which satisfies the differential privacy. Firstly, the SWP translates the image gray matrix into a one-dimensional ordered data stream by using image segmentation technology. The purpose of this step is to transform the image privacy protection problem into the data stream privacy protection problem. Then, the sliding window model is used to model the data flow. By comparing the similarity of data in adjacent sliding windows, the privacy budget is dynamically allocated, and Laplace noise is added. In SWP, the data in the sliding window comes from the image. To present the image features contained in the data more comprehensively and use the privacy budget more reasonably, this paper proposes a fusion similarity measurement EM (exact mechanism) mechanism and a dynamic privacy budget allocation DA (dynamic allocation) mechanism. Also, for further improving the usability of human face images and reducing the impact of noise, a sort-SWP algorithm based on the SWP method is proposed in the paper. Through the analysis, it can be seen that ordered input can further improve the usability of the SWP algorithm, but direct sorting of data will destroy theε-differential privacy. Therefore, this paper proposes a sorting method-SAS method, which satisfies the ε-differential privacy; SAS obtain an initial sort by using an exponential mechanism firstly. And then an approximate correct sort is obtained by using the Annealing algorithm to optimize the initial sort. Compared with LAP algorithm and SWP algorithm, the average accuracy rate of sort-SWP algorithm in ORL, Yale is increased by 56.63% and 21.55%, the recall rate is increased by 6.85% and 3.32%, and F1-sroce is improved by 55.62% and 16.55%.


---

## Body

## 1. Introduction

With the rapid development of information technology and multimedia technology, it is easier to obtain and share face digital images. Users can publish photos of their mobile phones or digital cameras to social networking platforms (such as Twitter, LinkedIn, WeChat) or other channels. Relevant statistics show that the number of face photos shared by users on major social networking platforms worldwide exceeds 3.2 billion every day. Also, there are numerous face image data derived from video. However, these digital images usually contain a wealth of personally sensitive information. If this information was collected and analyzed by a third party with ulterior motives, it may cause personal privacy disclosure and other unexpected losses.Privacy is an emotional word, which implies different meanings to different people. According to the definition of International Organization Standardization (ISO), privacy refers to the characteristics that can distinguish individuals or groups from other individuals and groups. Different countries have different legal definitions of privacy, and different objects (individuals, enterprises, governments, etc.) define the scope of privacy differently. For digital images, sensitive information can be a specific person or object in an image, a face, or fingerprint; the embedded information (photo location information and creation time, etc.); or an area that the image owner is concerned about. How to publish and analyze without disclosing sensitive information is the main purpose of privacy protection.The early research uses Anonymization Technology or Data Encryption Technology to solve the privacy protection of face image. Anonymization Technology refers to cover up real data with methods of hidden or fuzzy. It generally adopts anonymous operations such as suppression [1], generalization [2], analysis [3], slicing [4], and separation [5]. Especially, k-anonymity [6] is a classic representative algorithm. K-anonymity proposed that the sensitive information covered by the data should at least be indistinguishable from other k−1 data. Because of its shortcomings and shortcomings, K-anonymity extends the l-diversity method which ensures that each equivalent class contains at least l different sensitive attribute values [7], the t-closeness method to improve the global distribution of sensitive attributes [8], the m-variance method for dynamic relational data [9], and the HD composition method [10]. References [11, 12] use an anonymization mechanism to propose the k-same method. This method anonymizes the published digital image so that the probability of the attacker to identify the user identity through the published digital image again is less than 1/K. However, the main drawback of the traditional anonymization mechanism is too many assumptions about the attacker’s background knowledge and attack model, but those assumptions are not completely successful in reality.Data Encryption Technology is another important research direction of image information security, and its representative methods include secure multiparty computing [13], homomorphism encryption [14], and classification algorithm [15]. References [16–19] prevent the invasion of the third party by controlling the user communication protocol. References [20–23] propose using pixel replacement or pixel value substitution to encrypt image content. References [24–28] encrypt the image by changing the transform coefficient of the image in the frequency domain. Similar to the problems of anonymization technology, data encryption technology will also make corresponding assumptions for attacks and then design the corresponding encryption algorithm based on these assumptions. But this kind of encryption method will fall into the cycle of “new encryption methods are constantly proposed but constantly broken.” Also, the encrypted image is not open.Dwork first proposed differential privacy [29] in 2006, which disturbs sensitive data by adding noise to the output. Differential privacy can hide the influence of a single record. That means whether the record is in or not in the dataset, the output probability of the same result will not change significantly. The attacker’s ability to further reasoning is limited. Therefore, differential privacy is better than other privacy protection technologies by not making any assumptions about the background knowledge of any potential attacker. Besides, differential privacy is further studied in a series of papers of Dwork [30–34], and its implementation mechanism is proposed in [35, 36]. McSherry pointed out that some differential privacy algorithms for complex privacy problems satisfy two combinatorial properties: sequence composability and juxtaposition and combination [37]. In recent years, differential privacy is mainly used in data publishing, including histogram publishing [38–43], graph data publishing [44–48], data mining [49–51], data stream publishing [52], and spatial data publishing [53]. Due to the complexity of image data, researchers are still in the exploratory stage to use differential privacy technology to protect sensitive information in images.The real field matrix is a common representation of the image. Any pixel in the image can be mapped to a numerical relative position in a 2D matrix. It is the most direct method to add Laplace noise to all the values in the matrix. Although this method can satisfyε-differential privacy, it will cause excessive distortion and low usability of the disturbing image. Fourier transform and Wavelet transform are commonly compression techniques in image processing. In reference [54], an image compression method based on a discrete Fourier transform is proposed. This method adds the corresponding Laplace noise to the compressed image. Although the noise error is reduced, the reconstruction error is introduced in the image compression process. To reduce the impact of noise on the original image and improve the usability of published images, this paper proposes a differential privacy protection method for image publishing. It is inspired by the noncorrelation of the values in the image matrix; this paper tries to use image segmentation technology to transform the image gray matrix into 1D ordered data stream and then use the sliding window model to model the data flow. By comparing the similarity of data in adjacent sliding windows, the privacy budget is dynamically allocated which is used to solve the problem of image privacy protection. This method not only satisfies the differential privacy but also has high usability of the published image.


## 2. Background

### 2.1. Differential Privacy

Dalenius raised a problem with statistical databases: by accessing the database, no one should be able to get any information about a person [55]. However, due to background knowledge, absolute privacy protection is not possible. Differential privacy sidesteps this issue and turns to relative privacy protection. Any potential privacy breach will be limited to a small multiplier. To be in attention is that serious leaks may occur, but it is not because of whether a particular piece of data exists in the database.As a carrier of information, a digital image is usually stored and transmitted by a 3D matrix (i.e., a color image can be expressed as R, G, and B, three 2D matrices). To facilitate the data processing, it tries to make normalization treatment to the 3D image matrix and then get the corresponding 2D image gray matrix. Imagex can be expressed as a 2D matrix Xmn, with m is the number of rows, and N is the number of columns of the matrix.Formula (1) gives the specific calculation method.
(1)Xmn=Rmn×0.299+Gmn×0.587+Bmn×0.114.Before giving the formal definition of differential privacy, the definition of the neighborhood is given first by combining withX.Definition 1.
Given an imageX, the image gray matrix Xmn is obtained after normalization, so
(2)X∣Xmn=x11,x12,⋯x1n⋮⋱⋮xm1,xm1,⋯xmn;xij
represents the gray value of the corresponding element in the matrixXmn. If there is an X′, and there is only one element difference between X and X′, that is, |X−X′=xij1≤i≤m,1≤j≤n, then X and X′ are said to be adjacent to each other.Definition 2.
A random algorithmM for image data publishing is supposed. Range (M) is the output range of M. if any output s of algorithm M on two two-dimensional matrices X and X′ which are adjacent to each other satisfies Equation (3), then algorithm M satisfies ε-differential privacy.
(3)PrMX∈S≤expε×PrMX′∈S.In Equation (3), ε is usually a small positive number, which is used to weigh the relationship between privacy and precision. Relatively, if the ε is small, the privacy is higher, and the accuracy is lower, and vice versa. In general, the users select ε by executing a certain privacy policy. Besides, if an algorithm satisfies the ε-differential privacy when the neighbor database differs by one record, it satisfies the kε-differential privacy when the neighbor database differs at most by K records.To achieve differential privacy, a certain amount of random noise needs to be added to the query results. Intuitively, its magnitude should cover the maximum impact of a single record on the output. Therefore, the noise level is closely related to the global sensitivity of the corresponding query function.Definition 3.
Q is supposed to any query function and Q:D⟶Rd, the sensitivity of Q is expressed as
(4)ΔQ=maxX,X′QX−QX′ρ.Laplace mechanism is the most common noise-adding mechanism. For achieving differential privacy, the noise generated by Laplace distribution (the noise distribution satisfies Laplace probability density functionpdfx∣λ=1/2λe−∣x∣/λ, λ=ΔQ/ε) is added to disturb the real output.Theorem 4.
Laplace mechanism: supposeQ is a query sequence of length D. random algorithm m, which takes database as input and outputs the following vectors. It will satisfy ε-differential privacy.
(5)MD=QD+<Lap1ΔQε,⋯,LapdΔQε>.What should be noted here is thatLapiΔQ/ε (1≤i≤d) is an independent Laplace noise. The magnitude of the noise is proportional to ΔQ and inversely proportional to ε.Theorem 5.
Exponential mechanism: for any sampling methodm under the exponential mechanism, M satisfies ε-differential privacy if it satisfies Equation (6).
(6)MH,Hi=Hi:∣PrHi∈H∝expεuH,Hi2Δu.The exponential mechanism mainly deals with the nonnumerical output of the sampling algorithm. In the mechanism,uH,Hi is the scoring function, Δu is the global sensitivity of scoring function uH,Hi, and H is the output domain of the algorithm. According to formula (6), the higher the scoring function of Hi, the greater probability of output is selected.


### 2.2. Data Flow and Sliding Window Model

Differential privacy can ensure that the operation of inserting or deleting a record in a database will not affect the output of any query, thus ensuring that each record’s deletion or joining the database will not pose a threat to its privacy. To define differential privacy on a data stream, it is necessary to give the nearest neighbor relationship between two data streams.Definition 6.
For the data streamD and D′, if there is at most one record difference between them, then D and D′ are neighbors to each other.Definition 7.
For the data streamD and D′, they are adjacent to each other. A privacy algorithm A is assumed, if the result s of A on D and d∧ satisfies Equation (7), then algorithm A satisfies ε-differential privacy.
(7)PrAD∈S≤expε×PrAD′∈S.At any time, the sliding window model only needs to consider and process the most recently arrivedN data. It can better reflect the characteristics that the importance of data in the data stream gradually decreases with time. Therefore, the sliding window model is usually used in data stream processing. The sliding window model is used to model a data stream D with the length of N. All sliding windows use the fixed size of W. The value of ∣w∣ is equal to the number of data contained in the sliding window. The sliding amplitude s is the distance that the current sliding window moves forward compared with the previous one. Generally, the sliding amplitude is 1, which can be adjusted according to the actual demand. However, to ensure the continuity of the sliding window in the data stream, it is necessary to ensure 1≤r≤W. The data stream D=x1,x2,x3,⋯,xN and two adjacent sliding windows Wj and Wj+1. Assumed ∣W∣=∣W∣=4 且 r=1,2,4, Figure 1 shows the schematic diagram of adjacent sliding windows under different sliding amplitudes.Figure 1
Flow sliding window model.
(a)
r=1(b)
r=2(c)


## 2.1. Differential Privacy

Dalenius raised a problem with statistical databases: by accessing the database, no one should be able to get any information about a person [55]. However, due to background knowledge, absolute privacy protection is not possible. Differential privacy sidesteps this issue and turns to relative privacy protection. Any potential privacy breach will be limited to a small multiplier. To be in attention is that serious leaks may occur, but it is not because of whether a particular piece of data exists in the database.As a carrier of information, a digital image is usually stored and transmitted by a 3D matrix (i.e., a color image can be expressed as R, G, and B, three 2D matrices). To facilitate the data processing, it tries to make normalization treatment to the 3D image matrix and then get the corresponding 2D image gray matrix. Imagex can be expressed as a 2D matrix Xmn, with m is the number of rows, and N is the number of columns of the matrix.Formula (1) gives the specific calculation method.
(1)Xmn=Rmn×0.299+Gmn×0.587+Bmn×0.114.Before giving the formal definition of differential privacy, the definition of the neighborhood is given first by combining withX.Definition 1.
Given an imageX, the image gray matrix Xmn is obtained after normalization, so
(2)X∣Xmn=x11,x12,⋯x1n⋮⋱⋮xm1,xm1,⋯xmn;xij
represents the gray value of the corresponding element in the matrixXmn. If there is an X′, and there is only one element difference between X and X′, that is, |X−X′=xij1≤i≤m,1≤j≤n, then X and X′ are said to be adjacent to each other.Definition 2.
A random algorithmM for image data publishing is supposed. Range (M) is the output range of M. if any output s of algorithm M on two two-dimensional matrices X and X′ which are adjacent to each other satisfies Equation (3), then algorithm M satisfies ε-differential privacy.
(3)PrMX∈S≤expε×PrMX′∈S.In Equation (3), ε is usually a small positive number, which is used to weigh the relationship between privacy and precision. Relatively, if the ε is small, the privacy is higher, and the accuracy is lower, and vice versa. In general, the users select ε by executing a certain privacy policy. Besides, if an algorithm satisfies the ε-differential privacy when the neighbor database differs by one record, it satisfies the kε-differential privacy when the neighbor database differs at most by K records.To achieve differential privacy, a certain amount of random noise needs to be added to the query results. Intuitively, its magnitude should cover the maximum impact of a single record on the output. Therefore, the noise level is closely related to the global sensitivity of the corresponding query function.Definition 3.
Q is supposed to any query function and Q:D⟶Rd, the sensitivity of Q is expressed as
(4)ΔQ=maxX,X′QX−QX′ρ.Laplace mechanism is the most common noise-adding mechanism. For achieving differential privacy, the noise generated by Laplace distribution (the noise distribution satisfies Laplace probability density functionpdfx∣λ=1/2λe−∣x∣/λ, λ=ΔQ/ε) is added to disturb the real output.Theorem 4.
Laplace mechanism: supposeQ is a query sequence of length D. random algorithm m, which takes database as input and outputs the following vectors. It will satisfy ε-differential privacy.
(5)MD=QD+<Lap1ΔQε,⋯,LapdΔQε>.What should be noted here is thatLapiΔQ/ε (1≤i≤d) is an independent Laplace noise. The magnitude of the noise is proportional to ΔQ and inversely proportional to ε.Theorem 5.
Exponential mechanism: for any sampling methodm under the exponential mechanism, M satisfies ε-differential privacy if it satisfies Equation (6).
(6)MH,Hi=Hi:∣PrHi∈H∝expεuH,Hi2Δu.The exponential mechanism mainly deals with the nonnumerical output of the sampling algorithm. In the mechanism,uH,Hi is the scoring function, Δu is the global sensitivity of scoring function uH,Hi, and H is the output domain of the algorithm. According to formula (6), the higher the scoring function of Hi, the greater probability of output is selected.


## 2.2. Data Flow and Sliding Window Model

Differential privacy can ensure that the operation of inserting or deleting a record in a database will not affect the output of any query, thus ensuring that each record’s deletion or joining the database will not pose a threat to its privacy. To define differential privacy on a data stream, it is necessary to give the nearest neighbor relationship between two data streams.Definition 6.
For the data streamD and D′, if there is at most one record difference between them, then D and D′ are neighbors to each other.Definition 7.
For the data streamD and D′, they are adjacent to each other. A privacy algorithm A is assumed, if the result s of A on D and d∧ satisfies Equation (7), then algorithm A satisfies ε-differential privacy.
(7)PrAD∈S≤expε×PrAD′∈S.At any time, the sliding window model only needs to consider and process the most recently arrivedN data. It can better reflect the characteristics that the importance of data in the data stream gradually decreases with time. Therefore, the sliding window model is usually used in data stream processing. The sliding window model is used to model a data stream D with the length of N. All sliding windows use the fixed size of W. The value of ∣w∣ is equal to the number of data contained in the sliding window. The sliding amplitude s is the distance that the current sliding window moves forward compared with the previous one. Generally, the sliding amplitude is 1, which can be adjusted according to the actual demand. However, to ensure the continuity of the sliding window in the data stream, it is necessary to ensure 1≤r≤W. The data stream D=x1,x2,x3,⋯,xN and two adjacent sliding windows Wj and Wj+1. Assumed ∣W∣=∣W∣=4 且 r=1,2,4, Figure 1 shows the schematic diagram of adjacent sliding windows under different sliding amplitudes.Figure 1
Flow sliding window model.
(a)
r=1(b)
r=2(c)


## 3. Methods

Most of the existing differential privacy methods for image publishing use image compression technology to transferXmn; then, Laplace noise is added to the transformed data. After that, the disturbing data is restored to obtain Xmn′ which includes noise. However, there are two kinds of errors in the process of obtaining Xmn′. One is the noise error LEXmn′ which is caused by the Laplace mechanism. The other is the reconstruction error REXmn′ in the process of transformation. As a result, the total error ErrorXmn′ of “X” can be shown.
(8)ErrorXmn′=LEXmn′+REXmn′.The process of converting an image into an image gray matrix can be understood as storing the gray value in each position of the corresponding two-dimensional matrix. As shown in Figure2, Xmn is supposed to give each value a two-dimensional number to represent its position. This paper proposes to reconstruct the original two-dimensional number into a one-dimensional number, transform the image gray matrix into a data stream in the order of the one-dimensional number, and then, use the sliding window model to construct the data stream.Figure 2
Matrix transform data flow.Because the image gray matrix does not have the overall mathematical meaning, namely, the numerical ofXmn is no correlation. It can be seen that the transformation of the 2D matrix into a 1D data stream does not destroy the distribution of the original image. Be in attention, the whole conversion process is reversible and lossless, so REXm×n′ is avoided. In the research of this paper, the total error of Xmn′ is expressed as
(9)ErrorXmn′=LEXmn′.In this paper, the imaging differential privacy publishing method uses a sliding window model to construct the data stream. Assuming that there is a sliding windowWj+1 at the moment of j+1, and set r=∣W∣. Whether the data in the current sliding window is noisy and published, it needs to be judged according to the preset threshold value. If Wj+1 and the latest published Wj′ (Wj′ has been added noise by Laplace mechanism) is less similar than the default threshold, Wj′ replace Wj+1 to be released; otherwise, Wj+1 is released as Wj+1′ after it is allocated an appropriate privacy budget and adds noise. In the process of method implementation, the following three principles should be considered:
(1)
The data samples contained in any two adjacent sliding windows are all from the image gray matrix. Comparing the similarity between the two samples by numerical difference alone cannot show all the features of the image. Therefore, the measurement method of samples similarity needs to be considered and designed from the image features(2)
Using a sliding window model to construct data flow needs to consider the allocation of the privacy budget. For anyWj′, the smaller privacy budget is allocated, the greater noise value is added, and the higher degree of privacy protection has, but this practice also caused the lower availability of Wj′. Therefore, it is necessary to establish a reasonable privacy budget allocation mechanism on the premise of satisfying ε-differential privacy(3)
The method should satisfyε-differential privacy and improve the usability of the noisy image


### 3.1. LAP Algorithm

In this paper, the Laplace algorithm is proposed based on the Laplace mechanism. The method does not change the original data, but directly uses Laplace noise to disturbed the value ofXmn and then release Xmn′.Given the gray matrixXmn of an image, Laplace noise is added to each numerical matrix to obtain Xmn′=Xmn+∑i=1m×nlapΔQ/ε. According to Theorem 4, the LAP algorithm satisfies the ε-differential privacy, and ε=εsum/mn is the privacy budget that is allocated to each number of the image gray matrix. εsum is the total privacy budget, and ε is the privacy budget allocated to each numerical. To explain the problem more simply, the size of ε will not be specified under the same conditions.This paper will continue to describe the error size of the lap algorithm. Since there are only Laplace noises in the algorithm, the sum of squares of errors is obtained as:(10)ErrorXm×n′=E∑i=1m×nxi′−xi2=E∑i=1m×nxi−xi+lapΔQε2=2mnΔQε2.In formula (10), the sensitivity is ΔQ=xmax−xmin. Because the value of Xmn comes from the calculation result of the formula (1), so ΔQ≤255 exists. Besides, it can be seen from the above formula that the main factor determining the error size in the lap algorithm is the selected image size (m×n). When the selected image size is too large, using the lap algorithm will produce a large amount of noise, which will lead to the image with low usability after adding noise. To improve usability, this paper proposes an image privacy-preserving publishing method based on a sliding window.


### 3.2. The Measurement Method of Similarity

The image privacy protection publishing method proposed in this paper needs to rely on an accurate similarity measurement method. Different from an ordinary matrix, an image gray matrix not only has mathematical meaning but also includes a color feature, texture feature, and spatial distribution feature of the image itself. The commonly used similarity measurement methods include Manhattan distance, Chebyshev distance, and cosine distance. Due to the existing methods cannot analyze and compare samples from the perspective of images, the results obtained are available, but it will affect the usability of privacy protected images. Therefore, an accurate image data similarity measurement method—EM (exact mechanism)—is proposed.SupposeWx and Wy are two adjacent samples obtained by using a sliding window model after the image gray matrix is transformed into a data stream, where Wx=X1,X2,X3,⋯,Xn,Wy=Y1,Y2,Y3,⋯,Yn. Euclidean distance is often used to compare the similarity of data. The formula is:
(11)dX,Y=∑i=1nXi−Yi22.Since the data in the sample comes from pixel values, the Euclidean distance is used to measure the similarity of image data, and the results can reflect the difference of color features between different samples. According to formula (11), the similarity formula of the two samples is
(12)θ=dWx,Wy.There is an example to illustrate the limitation ofθ obtained from Equation(12): there are three sample Wx, Wy, and Wz. Equation(12) is used to calculate θ1 of Wx and Wy and θ2 of Wx and Wz. If θ1<θ2, Wx and Wy can be determined more similar. But actually, it is not like this. Different color feature, texture feature, is not based on pixel feature. It needs statistical calculation in the region containing multiple pixels. In pattern matching, this regional feature has great advantages and will not fail to match due to local bias. Suppose Wx=0,0,0,0,0,0,0,0,0, Wy=80,80,80,80,80,80,80,80,80, and Wz=0,0,0,0,0,0,0,0,255, there is a large global deviation between Wx and Wy, and a minimum local deviation between Wx and Wz (only one data difference between different samples). Equation (12) does not consider the influence of texture features on image matching results.Jaccard similarity index is used to measure the similarity between two sets. It is defined as the number of elements in the intersection of two sets divided by the number of elements in the union, the formula is(13)ρX,Y=X∩YX∪Y.For considering the influence of texture features, the Jaccard similarity index of two samples is used as the optimal value to add to the calculation formula ofθ, the formula is
(14)θ=dWx,WyρWx,Wy+σ.In the formula,dWx,Wy is the Euclidean distance between two samples. ρWx,Wy is the Jaccard similarity index between the two samples. σ appears as a correction value to ensuring the denominator is not 0. Besides, to reduce the influence of ρWx,Wy to the calculation results of formula (14), the value range of σ should be controlled between 0.8 and 1.Besides, hamming distance is often used to reflect the difference between two spatial vectors with the same structure and size. Hamming distance is a judgment method by comparing the values of the corresponding positions of two space vectorsX and Y in turn. If the value of Xi and Yi is the same, the result is 0. If it is different, it is 1. The result is to compare the values of all positions of the two space vectors in turn and then accumulate the result 1. The value obtained is the Hamming distance of the two space vectors. The formula of hamming distance is
(15)μX,Y=∑i=1nXi⊕Yi.The hamming distance can effectively measure the difference of spatial distribution characteristics between two samples, but its calculation result is a positive integer accumulated by the number 1, which cannot be directly used in the calculation ofθ. Besides, the calculation results of Hamming distance are limited by the sample size, and the Hamming distance of different size samples is not comparable. To solve this problem, a method combining Hamming distance with a perceptual hash algorithm [55] is proposed to add a disturbance value φ to formula (14). It further enhances the accuracy of θ. The values of φ are as follows:
(16)θ′ρWx,Wy+σdWx,Wy,θ′ρWx,Wy+σdWx,Wy,μWx,Wy<0.078n,1,0.078n≤μWx,Wy≤0.156n,1lgn−μWx,Wy,μWx,Wy>0.156n.In the above formula,n is the size of the sample, and θ′ is the minimum value given in advance. If θ>θ′, the two samples are not similar. If θ≤θ′, the two samples are similar. To sum up, the EM mechanism can be expressed as
(17)θ=φdX,YρX,Y+σ.


### 3.3. SWP Algorithm

Different from the lap algorithm, SWP (sliding window publication) uses a sliding window model to construct data flow. Through continuous moving of sliding window, it calculatesθ2≤i≤k between Wi and Wi−1′ by EM mechanism. If θ≤θ′,Wi−1′ replaces Wi to release Wi−1′; if θ>θ′, the DA mechanism is used to allocate an appropriate privacy budget to get Wi′, then release Wi′. The implementation process of the SWP algorithm is as follows.Algorithm 1: SWP.
input : sliding windowW=W1,W2,W3,W4,⋯,Wk, privacy budget ε,θ′output : 1.s=0;2.W1′=W1+lapε/k;3.εleft=εk−1/k;4.fori=2+stok5. use EM mechanism to calculateθ between W1+s′ and W2+s;6. Ifθ<=θ′7.Wi=W1+s′;8.s=s+1;9. else10.s=s+1;11.Wi′=Wi+lapεleft/k−s;12.εleft=εleft−εleft/k−s;13.W1+s′=Wi′;14. end if15. end for16. returnW′=W1′,W2′,W3′,W4′,⋯,Wk′.Note that in the SWP algorithm, we use the iterative method to take a dynamic allocation privacy budget mechanism—DA (dynamic allocation) mechanism which can be used for a limited data stream. Different from the commonly used dichotomy privacy budget allocation mechanism, the DA mechanism solves the problem of too fast consumption of privacy budget in a data stream and reduces the impact of noise on the original data to a certain extent.


#### 3.3.1. Dynamic Allocation

In the DA mechanism, the privacy budget for each consumption is assumed to beεi=ε1,ε2,ε3,⋯,εm, and the number of sliding windows affected by each consumption of privacy budget is si=s1,s2,s3,⋯,sm, there is s1+s2+s3+⋯+sm=k, and s1=1, K is the total number of sliding windows. Besides, εileft is the remaining privacy budget after i status is completed, then there is
(18)ε1=εk,ε1left=ε−εk,ε2=ε1leftk−s1,ε2left=ε1left−ε2,ε3=ε2leftk−s1−s2,ε3left=ε2left−ε3,ε4=ε3leftk−s1−s2−s3,ε4left=ε3left−ε4,m−1.εm−1=εm−2leftk−s1−s2⋯−sm−1,εm−1left=εm−2left−εm−1,m.εm=εm−1leftk−s1−s2⋯−sm,εmleft=εm−1left−εm.We can see from the above formula of DA that under any state,εi, and εileft the general formula of εi and εileft is as follows
(19)εi=εi−1leftk−∑j=1i−1sj,(20)εileft=εi−1left−εi.As shown in Figure3, in the implementation process of the DA mechanism, W1 is added Laplace noise to generate W1′ and publish it; the privacy budget ε/k is consumed with W1′ and then publish it. Using EM mechanism to calculate the θ between W1′ and W2, if the condition (θ<=θ′) is satisfied, then W2 is replaced by W1′ and released. The above operation is repeated until finding all Wi that meet the conditions. When W2, W3, and W4 are the suitable conditions, all of them are replaced with W1′. Because the replacement operation does not consume the privacy budget, the total privacy budget consumed by the four sliding windows is ε/k. If θ between W1′ and W2 does not satisfy the condition (θ>θ′), W5 adds Laplace noise to generate W5′ and publish it; the privacy budget which cost by W5 is εk−1/kk−4..Theorem 8.
In SWP, the privacy budget consumed will not exceedε, that is ε1+ε2+ε3+⋯+εm≤ε.
Certificate: according to formula (17), when k−∑j=1m−1sj=1, εm−1left=εm, then εmleft=0. In this state, it is expressed as
(21)ε1+ε2+ε3+⋯+εm=ε,where k−∑j=1m−1sj>1, εm−1left/εm>1, then εmleft>0. In this state, the formula is
(22)ε1+ε2+ε3+⋯+εm<ε.
The proof is complete.
Property 1 sequence combination property:D is assumed as a privacy data set, A1,A2,A3,⋯,An is n random algorithms, and Ai1≤i≤n satisfies ε-differential privacy with ε=∑i=1nεi.Theorem 9.
SWP method satisfiesε-differential privacy
Certificate: It can be seen from Theorem4:
(23)ε1+ε2+ε3+⋯+εm≤ε.Figure 3
Private budget allocation.In the formula,εi1≤i≤m is the budget privacy which is consumed in each state. According to the sequence combination property of difference privacy (property 1), the SWP method satisfies ε-differential privacy. The proof is complete.Theorem 10.
The error of the SWP method is not greater than the lap algorithm, it is:(24)ErrorSWP≤ErrorLap.Certificate: the DA used in the SWP method consumes a privacy budget ofεi=ε1,ε2,ε3,⋯,εm. The number of sliding windows affected by each consumption of privacy budget is si=s1,s2,s3,⋯,sm, and there is s1+s2+s3+⋯+sm=k. The Laplace mechanism adopted by the lap algorithm consumes a privacy budgetε/kand ∑i=1ksi′=k (s1′=s2′=s3′=⋯=sk′=1)First of all, the maximum error caused by the DA mechanism is calculated. In this case, it knowss1=s2=s3=⋯sm=1, means m=k, so it is
(25)ErrorSWPmax=lapΔQε1+lapΔQε2+lapΔQε3+⋯lapΔQεmmax=∑i=1klapΔQεi=k×lapΔQε/k=ErrorLap.For other cases, it can be judged according to formula (20). After the completion of state i, the remaining privacy budget of DA is εileft, the remaining privacy budget of the Laplace mechanism is ε´ileft. The DA allows si>1 and assume the existence of s1=s2=s3=⋯si−1=11<i<m. From this, it can get
(26)εileft−ε´ileft=ε−ε×k−i−1+sik−ε−ε×k−ik=ε×k−ik−k−i−1+sik=ε×si−1k.Due tosi>1, so εileft−ε´ileft>0, then εi+1,εi+2,εi+3,⋯,εm>ε/k, it is shown that ErrorSWP<ErrorLap.The proof is complete.


### 3.4. Sort-SWP Algorithm

In the SWP algorithm, the sliding window is set to move forward only in one-dimensional space, so the impact rangesi of Wi′ is completely determined by θ′. The verification method is not complicated. Assuming that there is an image x which use the SWP method to protect ε-privacy protection of X (assuming k=36), and θi between W1′ and every Wi2≤i≤36 is calculated. Figure 4 shows the distribution of specific data (abscissa is i, the ordinate is θ). When θ′=10, W2 and W3 will be replaced by W1′ to publish. From this, we can see that s1=2.Figure 4
Original sequence.However, by looking at allθi in Figure 3, it is found when θ′=10, it is not only W2 and W3 satisfy the condition θ≤θ′ but also including W34 and W35. According to the proof process of Theorem 10, under the same conditions, the larger the value of si is, the smaller the ErrorX′ is. If the SWP method is executed after sorting θ, assumed θ′=10, s1=4 can be obtained. The sorted result is shown in Figure 5.Figure 5
Sort sequence.However, the direct sorting of data will destroy theε-differential privacy [56]. Reference [57] proposed to add independent Laplace noise to each subdataset and then use the added noise value to sort. But this method will cause inaccurate sorting results. Reference [58] proposed to use the repeated index mechanism to sample the data and then to sort the data according to the order of sampling. However, the accuracy of the ranking results is too dependent on the allocation of the privacy budget. Therefore, an approximate sorting method—SAS (Simulated Annealing-Sort)—is proposed to satisfy ε-differential privacy. In the SAS algorithm, the sampling technique in exponential mechanism is used to get the initial sorting results, and then Simulated Annealing Algorithm is used to optimize the initial sorting results, so more accurate sorting results can be obtained.The Simulated Annealing Algorithm comes from the principle of solid annealing, and its core is the choice of solution. Simulated Annealing Algorithm is also a greedy algorithm. Random factors are introduced in its implementation process, which makes the algorithm accept a solution that is worse than the current solution with a certain probability. The annealing process in thermodynamics can be summarized as the state that the body with variable temperature drops slowly and reaches the lowest energy among molecules. Suppose there aren discrete states in the thermodynamic system S, and the energy of the current state is Eold, the energy of the next state is Enew. According to the Metropolis criterion, the probability P of state transition at temperature T (1≤old,new≤n) is expressed as follows:
(27)p=1Enew<Eold,exp−Enew−EoldγTEnew≥Eold.According to Equation (27), the receiving state is transferred when Enew<Eold. It will accept the state transition with probability P when Enew≥Eold. As a positive number which is less than 1, γ is used to control the change rate of temperature T by an iterative method, which also shows that the higher the temperature is, the greater the value of P is. Conversely, the lower the temperature is, the smaller the value of P will be.Because the Simulated Annealing Algorithm is probability-based, the solution obtained is not necessarily correct. It is not contrary to the core idea of differential privacy. Based on the above analysis, the implementation details of the SAS algorithm are given.Algorithm 2: SAS.
Input : sliding windowW=W1,W2,W3,W4,⋯,Wk, Privacy budget ε1 and ε2, initial temperature T, Cooling coefficient γ, Termination temperature TminOutput : Approximation ofW~1.W1′=W1+lapε2;2. UsingEM mechanism to calculate the similarity between W1′ and all other sliding windows, get θ=θ1,θ2,θ3,⋯,θk−1;3.z=0;4.whilek−z>15. The scoring function of exponential mechanismΔQ is 1/θ+σ;6. An unlabeledθjj=1 …k−1 is selected with probability P∝expε1ΔQ/2Δu by using the exponential mechanism7. markedθj which is currently selected8.z=z+1;9.θ~z=θj;10.Sz=j;11. while (T>Tmin)12. Random selectθ~ii=1⋯z−1;13.dE=θ~i−θ~i+1;14.if(dE>=0)15. Change the position ofθ~i and θ~i+1;16. Update sorting of data inθ~;17. Change the position ofSiandSi+1;18.else19.if(expdE/T>random0,1)20. Change the position ofθ~i and θ~i+1;21. Update sorting of data inθ~;22. Change the position ofSi and Si+1;23.end if24.T=T∗γ;25. Return the sliding windowW~ ={W1, WM, …} after sorting, initial position M=S1+1,⋯,Sz+1.In the SAS algorithm, the first line is to distributeW1 to get W1′. In line 2, using EM mechanism calculates the similarity of W1′ with all other sliding windows and stored in θ. Lines 4-7 use the exponential mechanism to rank θ from small to large. The fifth row is the scoring function of the index mechanism. In the SAS algorithm, we want those sliding window which is more similar to W1′ extracted with a higher probability. σ is a small positive number to ensure that the denominator of the scoring function is not 0. Besides, because deleting or adding a record only affects one count of θ, Δu=1. In line 9, the sorted results are stored in θ~. Line 10 is to store the sequence number of the position before sorting θ into S. In line 11-24, the annealing algorithm is used to optimize the sorting results. In line 12-17, θ~i is randomly selected in θ~, and the position of θ~i and θ~i+1 is changed. Assumed energy change from it is dE=θ~i−θ~i+1. If dE>=0, the changed θ~ and S are obtained after accepting the adjustment of this position, and the changed θ~ and S are regarded as the starting point of the next change. Lines 18-23, if de<0, it is accepted as the change with a certain probability and make the corresponding adjustment. Note that when dE<0,expdE/T ranges from 0 to 1. In line 24, the temperature T is adjusted by using γ (the value of γ is generally set as a positive number slightly less than 1). Since it is an annealing process, it can be seen from formula (12) that the value of T will decrease with the increase of iteration times, and this change will cause the acceptance probability to decrease.Based on the above contents, a sort-SWP method which is an optimization method based on sorting is proposed. The implementation process of the algorithm is shown as follows.Algorithm 3: Sort-SWP.
Input : sliding windowW=W1,W2,W3,W4,⋯,Wk, Privacy budgetε,θ′Output : Satisfying differential privacyW′1.ε=ε1+ε2+ε3;2.W~=SASW,ε1,ε2;3.W~′=SWPW~,ε3;4. fori=1 to k5. ifi=16.W1′=W~1′;7. Else8.m=Mi−1;9.Wm′=W~i′;10. endif11. end for12. returnW′=W1′,W2′,W3′,W4′,⋯,Wk′.The sort SWP method consists of three main steps: first, the SAS algorithm is used to sortW to get W~, where ε1 is used for exponential mechanism, and ε2 is used in the Laplace mechanism. To ensure the consistency of the sort SWP method, ε2=ε3/k is set. Secondly, the SWP algorithm is used to add noise to W,~ then gets W~′; the third (lines 5-11), because the distribution of data in W~′ destroys the structure of the original image, the position number stored in M is used to restore W~′ to W′.Theorem 11.
Sort SWP method satisfiesε-differential privacy
Certificate: in the sort SWP method, the total privacy budget is divided into three parts, and there existsε=ε1+ε2+ε3. Inside, ε1 used exponential machine to select the sliding window W and the probability is proportional to expε1ΔQ/2Δu, it shows as
(28)PrMX,ΔQ=W=expε1ΔQX,W/2Δu∑W′∈Oexpε1ΔQX,W′/2Δu.GivenX and its adjacent X′, for any value of WW∈O, it can be seen from formula (28)
(29)PrMX,ΔQ=WPrMX′,ΔQ=W=expε1ΔQX,W/2Δu/∑W′∈Oexpε1ΔQX,W′/2Δuexpε1ΔQX′,W/2Δu/∑W′∈Oexpε1ΔQX′,W′/2Δu=expε1ΔQX,W/2Δuexpε1ΔQX′,W/2Δu×∑W′∈Oexpε1ΔQX′,W′/2Δu∑W′∈Oexpε1ΔQX,W′/2Δu=expε1ε1ΔQX,W−ε1ΔQX′,W2Δu×∑W′∈Oexpε1ΔQX′,W′/2Δu∑W′∈Oexpε1ΔQX,W′/2Δu≤expε12×∑W′∈Oexpε1/2×expε1ΔQX,W′/2Δu∑W′∈Oexpε1ΔQX,W′/2Δu≤expε12×expε12×∑W′∈Oexpε1ΔQX,W′/2Δu∑W′∈Oexpε1ΔQX,W′/ε1ΔQX,W′=expε1.It can be seen that the process of selectingW by using the exponential mechanism satisfies ε1-differential privacy in Sort-SWP. Besides, according to Theorem 4, the Sort-SWP method satisfies ε2-differential privacy. According to the proof process of Theorem 9, it can be concluded that the Sort-SWP method satisfies ε3-differential privacy. Therefore, the whole process of the Sort-SWP method satisfies the ε-differential privacy. The proof is complete.


## 3.1. LAP Algorithm

In this paper, the Laplace algorithm is proposed based on the Laplace mechanism. The method does not change the original data, but directly uses Laplace noise to disturbed the value ofXmn and then release Xmn′.Given the gray matrixXmn of an image, Laplace noise is added to each numerical matrix to obtain Xmn′=Xmn+∑i=1m×nlapΔQ/ε. According to Theorem 4, the LAP algorithm satisfies the ε-differential privacy, and ε=εsum/mn is the privacy budget that is allocated to each number of the image gray matrix. εsum is the total privacy budget, and ε is the privacy budget allocated to each numerical. To explain the problem more simply, the size of ε will not be specified under the same conditions.This paper will continue to describe the error size of the lap algorithm. Since there are only Laplace noises in the algorithm, the sum of squares of errors is obtained as:(10)ErrorXm×n′=E∑i=1m×nxi′−xi2=E∑i=1m×nxi−xi+lapΔQε2=2mnΔQε2.In formula (10), the sensitivity is ΔQ=xmax−xmin. Because the value of Xmn comes from the calculation result of the formula (1), so ΔQ≤255 exists. Besides, it can be seen from the above formula that the main factor determining the error size in the lap algorithm is the selected image size (m×n). When the selected image size is too large, using the lap algorithm will produce a large amount of noise, which will lead to the image with low usability after adding noise. To improve usability, this paper proposes an image privacy-preserving publishing method based on a sliding window.


## 3.2. The Measurement Method of Similarity

The image privacy protection publishing method proposed in this paper needs to rely on an accurate similarity measurement method. Different from an ordinary matrix, an image gray matrix not only has mathematical meaning but also includes a color feature, texture feature, and spatial distribution feature of the image itself. The commonly used similarity measurement methods include Manhattan distance, Chebyshev distance, and cosine distance. Due to the existing methods cannot analyze and compare samples from the perspective of images, the results obtained are available, but it will affect the usability of privacy protected images. Therefore, an accurate image data similarity measurement method—EM (exact mechanism)—is proposed.SupposeWx and Wy are two adjacent samples obtained by using a sliding window model after the image gray matrix is transformed into a data stream, where Wx=X1,X2,X3,⋯,Xn,Wy=Y1,Y2,Y3,⋯,Yn. Euclidean distance is often used to compare the similarity of data. The formula is:
(11)dX,Y=∑i=1nXi−Yi22.Since the data in the sample comes from pixel values, the Euclidean distance is used to measure the similarity of image data, and the results can reflect the difference of color features between different samples. According to formula (11), the similarity formula of the two samples is
(12)θ=dWx,Wy.There is an example to illustrate the limitation ofθ obtained from Equation(12): there are three sample Wx, Wy, and Wz. Equation(12) is used to calculate θ1 of Wx and Wy and θ2 of Wx and Wz. If θ1<θ2, Wx and Wy can be determined more similar. But actually, it is not like this. Different color feature, texture feature, is not based on pixel feature. It needs statistical calculation in the region containing multiple pixels. In pattern matching, this regional feature has great advantages and will not fail to match due to local bias. Suppose Wx=0,0,0,0,0,0,0,0,0, Wy=80,80,80,80,80,80,80,80,80, and Wz=0,0,0,0,0,0,0,0,255, there is a large global deviation between Wx and Wy, and a minimum local deviation between Wx and Wz (only one data difference between different samples). Equation (12) does not consider the influence of texture features on image matching results.Jaccard similarity index is used to measure the similarity between two sets. It is defined as the number of elements in the intersection of two sets divided by the number of elements in the union, the formula is(13)ρX,Y=X∩YX∪Y.For considering the influence of texture features, the Jaccard similarity index of two samples is used as the optimal value to add to the calculation formula ofθ, the formula is
(14)θ=dWx,WyρWx,Wy+σ.In the formula,dWx,Wy is the Euclidean distance between two samples. ρWx,Wy is the Jaccard similarity index between the two samples. σ appears as a correction value to ensuring the denominator is not 0. Besides, to reduce the influence of ρWx,Wy to the calculation results of formula (14), the value range of σ should be controlled between 0.8 and 1.Besides, hamming distance is often used to reflect the difference between two spatial vectors with the same structure and size. Hamming distance is a judgment method by comparing the values of the corresponding positions of two space vectorsX and Y in turn. If the value of Xi and Yi is the same, the result is 0. If it is different, it is 1. The result is to compare the values of all positions of the two space vectors in turn and then accumulate the result 1. The value obtained is the Hamming distance of the two space vectors. The formula of hamming distance is
(15)μX,Y=∑i=1nXi⊕Yi.The hamming distance can effectively measure the difference of spatial distribution characteristics between two samples, but its calculation result is a positive integer accumulated by the number 1, which cannot be directly used in the calculation ofθ. Besides, the calculation results of Hamming distance are limited by the sample size, and the Hamming distance of different size samples is not comparable. To solve this problem, a method combining Hamming distance with a perceptual hash algorithm [55] is proposed to add a disturbance value φ to formula (14). It further enhances the accuracy of θ. The values of φ are as follows:
(16)θ′ρWx,Wy+σdWx,Wy,θ′ρWx,Wy+σdWx,Wy,μWx,Wy<0.078n,1,0.078n≤μWx,Wy≤0.156n,1lgn−μWx,Wy,μWx,Wy>0.156n.In the above formula,n is the size of the sample, and θ′ is the minimum value given in advance. If θ>θ′, the two samples are not similar. If θ≤θ′, the two samples are similar. To sum up, the EM mechanism can be expressed as
(17)θ=φdX,YρX,Y+σ.


## 3.3. SWP Algorithm

Different from the lap algorithm, SWP (sliding window publication) uses a sliding window model to construct data flow. Through continuous moving of sliding window, it calculatesθ2≤i≤k between Wi and Wi−1′ by EM mechanism. If θ≤θ′,Wi−1′ replaces Wi to release Wi−1′; if θ>θ′, the DA mechanism is used to allocate an appropriate privacy budget to get Wi′, then release Wi′. The implementation process of the SWP algorithm is as follows.Algorithm 1: SWP.
input : sliding windowW=W1,W2,W3,W4,⋯,Wk, privacy budget ε,θ′output : 1.s=0;2.W1′=W1+lapε/k;3.εleft=εk−1/k;4.fori=2+stok5. use EM mechanism to calculateθ between W1+s′ and W2+s;6. Ifθ<=θ′7.Wi=W1+s′;8.s=s+1;9. else10.s=s+1;11.Wi′=Wi+lapεleft/k−s;12.εleft=εleft−εleft/k−s;13.W1+s′=Wi′;14. end if15. end for16. returnW′=W1′,W2′,W3′,W4′,⋯,Wk′.Note that in the SWP algorithm, we use the iterative method to take a dynamic allocation privacy budget mechanism—DA (dynamic allocation) mechanism which can be used for a limited data stream. Different from the commonly used dichotomy privacy budget allocation mechanism, the DA mechanism solves the problem of too fast consumption of privacy budget in a data stream and reduces the impact of noise on the original data to a certain extent.


### 3.3.1. Dynamic Allocation

In the DA mechanism, the privacy budget for each consumption is assumed to beεi=ε1,ε2,ε3,⋯,εm, and the number of sliding windows affected by each consumption of privacy budget is si=s1,s2,s3,⋯,sm, there is s1+s2+s3+⋯+sm=k, and s1=1, K is the total number of sliding windows. Besides, εileft is the remaining privacy budget after i status is completed, then there is
(18)ε1=εk,ε1left=ε−εk,ε2=ε1leftk−s1,ε2left=ε1left−ε2,ε3=ε2leftk−s1−s2,ε3left=ε2left−ε3,ε4=ε3leftk−s1−s2−s3,ε4left=ε3left−ε4,m−1.εm−1=εm−2leftk−s1−s2⋯−sm−1,εm−1left=εm−2left−εm−1,m.εm=εm−1leftk−s1−s2⋯−sm,εmleft=εm−1left−εm.We can see from the above formula of DA that under any state,εi, and εileft the general formula of εi and εileft is as follows
(19)εi=εi−1leftk−∑j=1i−1sj,(20)εileft=εi−1left−εi.As shown in Figure3, in the implementation process of the DA mechanism, W1 is added Laplace noise to generate W1′ and publish it; the privacy budget ε/k is consumed with W1′ and then publish it. Using EM mechanism to calculate the θ between W1′ and W2, if the condition (θ<=θ′) is satisfied, then W2 is replaced by W1′ and released. The above operation is repeated until finding all Wi that meet the conditions. When W2, W3, and W4 are the suitable conditions, all of them are replaced with W1′. Because the replacement operation does not consume the privacy budget, the total privacy budget consumed by the four sliding windows is ε/k. If θ between W1′ and W2 does not satisfy the condition (θ>θ′), W5 adds Laplace noise to generate W5′ and publish it; the privacy budget which cost by W5 is εk−1/kk−4..Theorem 8.
In SWP, the privacy budget consumed will not exceedε, that is ε1+ε2+ε3+⋯+εm≤ε.
Certificate: according to formula (17), when k−∑j=1m−1sj=1, εm−1left=εm, then εmleft=0. In this state, it is expressed as
(21)ε1+ε2+ε3+⋯+εm=ε,where k−∑j=1m−1sj>1, εm−1left/εm>1, then εmleft>0. In this state, the formula is
(22)ε1+ε2+ε3+⋯+εm<ε.
The proof is complete.
Property 1 sequence combination property:D is assumed as a privacy data set, A1,A2,A3,⋯,An is n random algorithms, and Ai1≤i≤n satisfies ε-differential privacy with ε=∑i=1nεi.Theorem 9.
SWP method satisfiesε-differential privacy
Certificate: It can be seen from Theorem4:
(23)ε1+ε2+ε3+⋯+εm≤ε.Figure 3
Private budget allocation.In the formula,εi1≤i≤m is the budget privacy which is consumed in each state. According to the sequence combination property of difference privacy (property 1), the SWP method satisfies ε-differential privacy. The proof is complete.Theorem 10.
The error of the SWP method is not greater than the lap algorithm, it is:(24)ErrorSWP≤ErrorLap.Certificate: the DA used in the SWP method consumes a privacy budget ofεi=ε1,ε2,ε3,⋯,εm. The number of sliding windows affected by each consumption of privacy budget is si=s1,s2,s3,⋯,sm, and there is s1+s2+s3+⋯+sm=k. The Laplace mechanism adopted by the lap algorithm consumes a privacy budgetε/kand ∑i=1ksi′=k (s1′=s2′=s3′=⋯=sk′=1)First of all, the maximum error caused by the DA mechanism is calculated. In this case, it knowss1=s2=s3=⋯sm=1, means m=k, so it is
(25)ErrorSWPmax=lapΔQε1+lapΔQε2+lapΔQε3+⋯lapΔQεmmax=∑i=1klapΔQεi=k×lapΔQε/k=ErrorLap.For other cases, it can be judged according to formula (20). After the completion of state i, the remaining privacy budget of DA is εileft, the remaining privacy budget of the Laplace mechanism is ε´ileft. The DA allows si>1 and assume the existence of s1=s2=s3=⋯si−1=11<i<m. From this, it can get
(26)εileft−ε´ileft=ε−ε×k−i−1+sik−ε−ε×k−ik=ε×k−ik−k−i−1+sik=ε×si−1k.Due tosi>1, so εileft−ε´ileft>0, then εi+1,εi+2,εi+3,⋯,εm>ε/k, it is shown that ErrorSWP<ErrorLap.The proof is complete.


## 3.3.1. Dynamic Allocation

In the DA mechanism, the privacy budget for each consumption is assumed to beεi=ε1,ε2,ε3,⋯,εm, and the number of sliding windows affected by each consumption of privacy budget is si=s1,s2,s3,⋯,sm, there is s1+s2+s3+⋯+sm=k, and s1=1, K is the total number of sliding windows. Besides, εileft is the remaining privacy budget after i status is completed, then there is
(18)ε1=εk,ε1left=ε−εk,ε2=ε1leftk−s1,ε2left=ε1left−ε2,ε3=ε2leftk−s1−s2,ε3left=ε2left−ε3,ε4=ε3leftk−s1−s2−s3,ε4left=ε3left−ε4,m−1.εm−1=εm−2leftk−s1−s2⋯−sm−1,εm−1left=εm−2left−εm−1,m.εm=εm−1leftk−s1−s2⋯−sm,εmleft=εm−1left−εm.We can see from the above formula of DA that under any state,εi, and εileft the general formula of εi and εileft is as follows
(19)εi=εi−1leftk−∑j=1i−1sj,(20)εileft=εi−1left−εi.As shown in Figure3, in the implementation process of the DA mechanism, W1 is added Laplace noise to generate W1′ and publish it; the privacy budget ε/k is consumed with W1′ and then publish it. Using EM mechanism to calculate the θ between W1′ and W2, if the condition (θ<=θ′) is satisfied, then W2 is replaced by W1′ and released. The above operation is repeated until finding all Wi that meet the conditions. When W2, W3, and W4 are the suitable conditions, all of them are replaced with W1′. Because the replacement operation does not consume the privacy budget, the total privacy budget consumed by the four sliding windows is ε/k. If θ between W1′ and W2 does not satisfy the condition (θ>θ′), W5 adds Laplace noise to generate W5′ and publish it; the privacy budget which cost by W5 is εk−1/kk−4..Theorem 8.
In SWP, the privacy budget consumed will not exceedε, that is ε1+ε2+ε3+⋯+εm≤ε.
Certificate: according to formula (17), when k−∑j=1m−1sj=1, εm−1left=εm, then εmleft=0. In this state, it is expressed as
(21)ε1+ε2+ε3+⋯+εm=ε,where k−∑j=1m−1sj>1, εm−1left/εm>1, then εmleft>0. In this state, the formula is
(22)ε1+ε2+ε3+⋯+εm<ε.
The proof is complete.
Property 1 sequence combination property:D is assumed as a privacy data set, A1,A2,A3,⋯,An is n random algorithms, and Ai1≤i≤n satisfies ε-differential privacy with ε=∑i=1nεi.Theorem 9.
SWP method satisfiesε-differential privacy
Certificate: It can be seen from Theorem4:
(23)ε1+ε2+ε3+⋯+εm≤ε.Figure 3
Private budget allocation.In the formula,εi1≤i≤m is the budget privacy which is consumed in each state. According to the sequence combination property of difference privacy (property 1), the SWP method satisfies ε-differential privacy. The proof is complete.Theorem 10.
The error of the SWP method is not greater than the lap algorithm, it is:(24)ErrorSWP≤ErrorLap.Certificate: the DA used in the SWP method consumes a privacy budget ofεi=ε1,ε2,ε3,⋯,εm. The number of sliding windows affected by each consumption of privacy budget is si=s1,s2,s3,⋯,sm, and there is s1+s2+s3+⋯+sm=k. The Laplace mechanism adopted by the lap algorithm consumes a privacy budgetε/kand ∑i=1ksi′=k (s1′=s2′=s3′=⋯=sk′=1)First of all, the maximum error caused by the DA mechanism is calculated. In this case, it knowss1=s2=s3=⋯sm=1, means m=k, so it is
(25)ErrorSWPmax=lapΔQε1+lapΔQε2+lapΔQε3+⋯lapΔQεmmax=∑i=1klapΔQεi=k×lapΔQε/k=ErrorLap.For other cases, it can be judged according to formula (20). After the completion of state i, the remaining privacy budget of DA is εileft, the remaining privacy budget of the Laplace mechanism is ε´ileft. The DA allows si>1 and assume the existence of s1=s2=s3=⋯si−1=11<i<m. From this, it can get
(26)εileft−ε´ileft=ε−ε×k−i−1+sik−ε−ε×k−ik=ε×k−ik−k−i−1+sik=ε×si−1k.Due tosi>1, so εileft−ε´ileft>0, then εi+1,εi+2,εi+3,⋯,εm>ε/k, it is shown that ErrorSWP<ErrorLap.The proof is complete.


## 3.4. Sort-SWP Algorithm

In the SWP algorithm, the sliding window is set to move forward only in one-dimensional space, so the impact rangesi of Wi′ is completely determined by θ′. The verification method is not complicated. Assuming that there is an image x which use the SWP method to protect ε-privacy protection of X (assuming k=36), and θi between W1′ and every Wi2≤i≤36 is calculated. Figure 4 shows the distribution of specific data (abscissa is i, the ordinate is θ). When θ′=10, W2 and W3 will be replaced by W1′ to publish. From this, we can see that s1=2.Figure 4
Original sequence.However, by looking at allθi in Figure 3, it is found when θ′=10, it is not only W2 and W3 satisfy the condition θ≤θ′ but also including W34 and W35. According to the proof process of Theorem 10, under the same conditions, the larger the value of si is, the smaller the ErrorX′ is. If the SWP method is executed after sorting θ, assumed θ′=10, s1=4 can be obtained. The sorted result is shown in Figure 5.Figure 5
Sort sequence.However, the direct sorting of data will destroy theε-differential privacy [56]. Reference [57] proposed to add independent Laplace noise to each subdataset and then use the added noise value to sort. But this method will cause inaccurate sorting results. Reference [58] proposed to use the repeated index mechanism to sample the data and then to sort the data according to the order of sampling. However, the accuracy of the ranking results is too dependent on the allocation of the privacy budget. Therefore, an approximate sorting method—SAS (Simulated Annealing-Sort)—is proposed to satisfy ε-differential privacy. In the SAS algorithm, the sampling technique in exponential mechanism is used to get the initial sorting results, and then Simulated Annealing Algorithm is used to optimize the initial sorting results, so more accurate sorting results can be obtained.The Simulated Annealing Algorithm comes from the principle of solid annealing, and its core is the choice of solution. Simulated Annealing Algorithm is also a greedy algorithm. Random factors are introduced in its implementation process, which makes the algorithm accept a solution that is worse than the current solution with a certain probability. The annealing process in thermodynamics can be summarized as the state that the body with variable temperature drops slowly and reaches the lowest energy among molecules. Suppose there aren discrete states in the thermodynamic system S, and the energy of the current state is Eold, the energy of the next state is Enew. According to the Metropolis criterion, the probability P of state transition at temperature T (1≤old,new≤n) is expressed as follows:
(27)p=1Enew<Eold,exp−Enew−EoldγTEnew≥Eold.According to Equation (27), the receiving state is transferred when Enew<Eold. It will accept the state transition with probability P when Enew≥Eold. As a positive number which is less than 1, γ is used to control the change rate of temperature T by an iterative method, which also shows that the higher the temperature is, the greater the value of P is. Conversely, the lower the temperature is, the smaller the value of P will be.Because the Simulated Annealing Algorithm is probability-based, the solution obtained is not necessarily correct. It is not contrary to the core idea of differential privacy. Based on the above analysis, the implementation details of the SAS algorithm are given.Algorithm 2: SAS.
Input : sliding windowW=W1,W2,W3,W4,⋯,Wk, Privacy budget ε1 and ε2, initial temperature T, Cooling coefficient γ, Termination temperature TminOutput : Approximation ofW~1.W1′=W1+lapε2;2. UsingEM mechanism to calculate the similarity between W1′ and all other sliding windows, get θ=θ1,θ2,θ3,⋯,θk−1;3.z=0;4.whilek−z>15. The scoring function of exponential mechanismΔQ is 1/θ+σ;6. An unlabeledθjj=1 …k−1 is selected with probability P∝expε1ΔQ/2Δu by using the exponential mechanism7. markedθj which is currently selected8.z=z+1;9.θ~z=θj;10.Sz=j;11. while (T>Tmin)12. Random selectθ~ii=1⋯z−1;13.dE=θ~i−θ~i+1;14.if(dE>=0)15. Change the position ofθ~i and θ~i+1;16. Update sorting of data inθ~;17. Change the position ofSiandSi+1;18.else19.if(expdE/T>random0,1)20. Change the position ofθ~i and θ~i+1;21. Update sorting of data inθ~;22. Change the position ofSi and Si+1;23.end if24.T=T∗γ;25. Return the sliding windowW~ ={W1, WM, …} after sorting, initial position M=S1+1,⋯,Sz+1.In the SAS algorithm, the first line is to distributeW1 to get W1′. In line 2, using EM mechanism calculates the similarity of W1′ with all other sliding windows and stored in θ. Lines 4-7 use the exponential mechanism to rank θ from small to large. The fifth row is the scoring function of the index mechanism. In the SAS algorithm, we want those sliding window which is more similar to W1′ extracted with a higher probability. σ is a small positive number to ensure that the denominator of the scoring function is not 0. Besides, because deleting or adding a record only affects one count of θ, Δu=1. In line 9, the sorted results are stored in θ~. Line 10 is to store the sequence number of the position before sorting θ into S. In line 11-24, the annealing algorithm is used to optimize the sorting results. In line 12-17, θ~i is randomly selected in θ~, and the position of θ~i and θ~i+1 is changed. Assumed energy change from it is dE=θ~i−θ~i+1. If dE>=0, the changed θ~ and S are obtained after accepting the adjustment of this position, and the changed θ~ and S are regarded as the starting point of the next change. Lines 18-23, if de<0, it is accepted as the change with a certain probability and make the corresponding adjustment. Note that when dE<0,expdE/T ranges from 0 to 1. In line 24, the temperature T is adjusted by using γ (the value of γ is generally set as a positive number slightly less than 1). Since it is an annealing process, it can be seen from formula (12) that the value of T will decrease with the increase of iteration times, and this change will cause the acceptance probability to decrease.Based on the above contents, a sort-SWP method which is an optimization method based on sorting is proposed. The implementation process of the algorithm is shown as follows.Algorithm 3: Sort-SWP.
Input : sliding windowW=W1,W2,W3,W4,⋯,Wk, Privacy budgetε,θ′Output : Satisfying differential privacyW′1.ε=ε1+ε2+ε3;2.W~=SASW,ε1,ε2;3.W~′=SWPW~,ε3;4. fori=1 to k5. ifi=16.W1′=W~1′;7. Else8.m=Mi−1;9.Wm′=W~i′;10. endif11. end for12. returnW′=W1′,W2′,W3′,W4′,⋯,Wk′.The sort SWP method consists of three main steps: first, the SAS algorithm is used to sortW to get W~, where ε1 is used for exponential mechanism, and ε2 is used in the Laplace mechanism. To ensure the consistency of the sort SWP method, ε2=ε3/k is set. Secondly, the SWP algorithm is used to add noise to W,~ then gets W~′; the third (lines 5-11), because the distribution of data in W~′ destroys the structure of the original image, the position number stored in M is used to restore W~′ to W′.Theorem 11.
Sort SWP method satisfiesε-differential privacy
Certificate: in the sort SWP method, the total privacy budget is divided into three parts, and there existsε=ε1+ε2+ε3. Inside, ε1 used exponential machine to select the sliding window W and the probability is proportional to expε1ΔQ/2Δu, it shows as
(28)PrMX,ΔQ=W=expε1ΔQX,W/2Δu∑W′∈Oexpε1ΔQX,W′/2Δu.GivenX and its adjacent X′, for any value of WW∈O, it can be seen from formula (28)
(29)PrMX,ΔQ=WPrMX′,ΔQ=W=expε1ΔQX,W/2Δu/∑W′∈Oexpε1ΔQX,W′/2Δuexpε1ΔQX′,W/2Δu/∑W′∈Oexpε1ΔQX′,W′/2Δu=expε1ΔQX,W/2Δuexpε1ΔQX′,W/2Δu×∑W′∈Oexpε1ΔQX′,W′/2Δu∑W′∈Oexpε1ΔQX,W′/2Δu=expε1ε1ΔQX,W−ε1ΔQX′,W2Δu×∑W′∈Oexpε1ΔQX′,W′/2Δu∑W′∈Oexpε1ΔQX,W′/2Δu≤expε12×∑W′∈Oexpε1/2×expε1ΔQX,W′/2Δu∑W′∈Oexpε1ΔQX,W′/2Δu≤expε12×expε12×∑W′∈Oexpε1ΔQX,W′/2Δu∑W′∈Oexpε1ΔQX,W′/ε1ΔQX,W′=expε1.It can be seen that the process of selectingW by using the exponential mechanism satisfies ε1-differential privacy in Sort-SWP. Besides, according to Theorem 4, the Sort-SWP method satisfies ε2-differential privacy. According to the proof process of Theorem 9, it can be concluded that the Sort-SWP method satisfies ε3-differential privacy. Therefore, the whole process of the Sort-SWP method satisfies the ε-differential privacy. The proof is complete.


## 4. Experiment and Result Analysis

### 4.1. Sorting Method Experiment

Direct sorting will destroy theε-differential privacy. Therefore, this paper adopts an approximate sorting method—SAS algorithm—which satisfies theε-differential privacy. During the test, a one-dimensional array which is containing 57 random numbers is used as the experimental data set, and three sorting methods, namely, simulated annealing algorithm, exponential mechanism, and SAS algorithm, are selected for comparison. Besides, to verify the impact of the privacy budget on different ranking results, ε is taken as 0.4, 0.5, ln2, and 1, respectively. The results are shown in Figure 6.Figure 6
Noise statistics.In Figure7, the abscissa represents the number of times the algorithm is executed, and the ordinate represents the accuracy of the sorting. The following three conclusions can be drawn from the experimental results: (1) the sorting results of the simulated annealing algorithm are only related to the execution times of the algorithm and not relevant to the value of ε; (2) the ranking results of the exponential mechanism are only related to the value of ε, and the higher the value of ε is, the higher the sorting accuracy is. It is independent of the execution times of the algorithm; (3) the sorting results of the SAS algorithm are related to the value of ε and also related to the execution times of the algorithm, and they are proportional.Figure 7
Sorting result test.
(a)
ε=0.4(b)
ε=0.5(c)
ε=ln2(d)
ε=1


### 4.2. Simulation Experiment

In different kinds of images, the sensitive information of face photos is the most representative. Therefore, to verify the usability of the algorithm, it selects a front face photo (190∗160) to complete the corresponding experiment in this paper. The experimental results of different algorithms under the same conditions are shown in Figure 8. Figure 8(a) is the original image; Figure 8(b) is the resulting graph obtained by directly adding Laplace noise to the original image; Figure 8(c) is the resulting graph obtained by using the SWP algorithm; Figure 8(d) is the resulting graph obtained by using sort SWP algorithm. Compared with the LAP algorithm, the SWP algorithm and sort SWP algorithm have better display effect.Figure 8
Experimental results.
(a)
Original image(b)
LAP(c)
SWP(d)
Sort-SWPThe core of this paper is to use the Laplace mechanism in differential privacy protection to add noise to the image and to protect the sensitive information in the image. Therefore, to destroy the effect of privacy protection, it is a common method to eliminate or reduce the impact of image noise. For the methods of eliminating image noise, the representative methods are average filtering or median filtering. In Figures9 and 10, the mean filter and median filter are used to interfere with the experimental results in Figure 8. The purpose of this is to evaluate the degree of privacy protection and the usability of the protected images after noise elimination.Figure 9
Experimental results graph and mean filtering.
(a)
Original image and AF(b)
LAP and AF(c)
SWP and AF(d)
Sort-SWP and AFFigure 10
Experimental result graph and median filter.
(a)
Original image and MF(b)
LAP and MF(c)
SWP and MF(d)
Sort-SWP and MFNow, we have given a preliminary conclusion that the SWP algorithm and sort SWP algorithm are better than the LAF method. However, this conclusion is only obtained by observing the experimental results, so it may be one-sided or inaccurate. To further verify whether the conclusion is correct, the previous 12 images are transformed into a gray histogram for further comparison. Gray histogram reflects the relationship between the frequency of gray level pixels and gray level in an image, although the gray histogram cannot reflect the specific distribution of image pixels but reflect the impact of Laplace noise on the image as a statistical result.It can be seen from Figures11–13, under the same conditions, the histogram distribution of the SWP algorithm and lap algorithm is closer, but it is quite different from the distribution of pixels in the original image. The distribution of pixels in the histogram of the result of the sort SWP algorithm is consistent with the original image. Therefore, it can be considered that the noise interference caused by the sort SWP algorithm is the least.Figure 11
Gray histogram of experimental image.
(a)
Original image and GH(b)
LAP and GH(c)
SWP and GH(d)
Sort-SWP and GHFigure 12
Experimental image gray histogram and average filtering.
(a)
Original image and AF and GH(b)
LAP and AF and GH(c)
SWP and AF and GH(d)
Sort-SWP and AF and GHFigure 13
Experimental image gray histogram and median filter.
(a)
Original image and MF and GH(b)
LAP and MF and GH(c)
SWP and MF and GH(d)
Sort-SWP and MF and GHIn the papers related to differential privacy protection, the noise size is an important evaluation index to measure the advantages and disadvantages of the algorithm. Under the same conditions, less noise represents higher availability. Of course, as a special information carrier, image noise is only one of the evaluation indicators.If the pixel value of the gray-scale image is regarded as a value, the value after adding Laplace noise will change with the change ofε. The smaller the ε is, the greater the noise is, the higher the degree of privacy protection is, and there is no limit to the value. However, in the experiment, the range of the pixel value of the gray image is limited between 0 and 255, so even if the obtained value is beyond this range under the influence of noise, it will be normalized. That means all values greater than 255 will be changed to 255, and all values less than 0 will be changed to 0. Therefore, the error of the image after privacy protection is divided into absolute error and relative error. For example, in an image x, there is a pixel xmn=200. If xmn′=280 after adding noise, the absolute error value is 80, and the relative error value is 55.In Figure6, the absolute error and relative error value of the experimental result graph under the influence of different algorithms are given. The conclusion is that the error caused by the three algorithms is in line with the previous expectations, and compared with the LAP algorithm and SWP algorithm, the sort-SWP algorithm will cause the smallest error. Also, the median filter is slightly better than the average filter for Laplace noise.


### 4.3. Result Analysis

To verify the feasibility of the algorithm, the ORL face database, and YALE face database are used as experimental data sets, and the experimental environment is Intel® Corei9-9900K CPU@ 3.60 GHz,32 G memories, GTX 21080TI GPU, Windows 10 operating system. A face recognition method based on an improved AlexNet convolution neural network is adopted in the experiment. Compared with the AlexNet model, this method has a simpler network structure and fewer parameters, which can save a lot of model training time and then make a fast prediction. When using the ORL face database for the experiment, 5 images of each person are used as a training set, and other images are used as a test set. The sliding window length is 56,k=184. When using the YALE face database for experiments, random 5 images of each person are also used as the training set and the rest as the test set. The sliding window length is 160, k=486. Privacy budget ε is 1, 2, 3, 4, and 5. The test items are accuracy rate, recall rate, and F1 score. The experimental results are shown in Tables 1–6.Table 1
ORL and precision.
PrecisionLAPSWPSort-SWPLAP and AFSWP and AFSort-SWP and AFLAP and MFSWP and MFSort-SWP and MFε=16.52%39.29%53.86%9.27%47.09%60.55%14.95%49.01%65.39%ε=28.83%43.45%69.26%15.86%56.39%72.06%25.37%57.61%75.41%ε=311.37%48.29%71.66%22.00%63.39%79.27%36.61%72.18%83.68%ε=413.96%55.18%75.19%27.71%70.43%82.51%44.36%80.97%87.55%ε=516.67%62.72%82.83%33.08%76.36%86.19%51.98%88.70%91.33%Table 2
ORL and recall.
RecallLAPSWPSort-SWPLAP and AFSWP and AFSort-SWP and AFLAP and MFSWP and MFSort-SWP and MFε=171.32%77.96%83.58%72.35%81.63%84.57%80.12%83.47%88.14%ε=273.56%75.68%81.83%75.52%81.26%83.67%78.68%79.85%80.33%ε=375.79%83.81%85.25%77.53%84.36%85.23%81.18%86.63%84.54%ε=472.32%74.22%78.58%73.52%78.59%82.18%75.36%81.23%87.10%ε=577.91%76.23%80.12%78.07%80.11%82.51%80.12%81.15%83.94%Table 3
ORL and F1-score.
F1-sroceLAPSWPSort-SWPLAP and AFSWP and AFSort-SWP and AFLAP and MFSWP and MFSort-SWP and MFε=111.95%52.25%65.51%16.43%59.73%70.57%25.20%61.76%75.08%ε=215.77%55.21%75.02%26.21%66.58%77.43%38.37%66.93%77.79%ε=319.77%61.27%77.87%34.27%72.39%82.14%50.46%78.75%84.11%ε=423.40%63.30%76.85%40.25%74.29%82.34%55.85%81.10%87.32%ε=527.46%68.82%81.45%46.47%78.19%84.31%63.05%84.76%87.48%Table 4
YALE and precision.
PrecisionLAPSWPSort-SWPLAP and AFSWP and AFSort-SWP and AFLAP and MFSWP and MFSort-SWP and MFε=14.12%27.33%44.52%7.89%41.25%53.91%10.18%44.74%56.10%ε=26.77%31.56%57.38%12.51%48.98%60.47%18.23%53.82%64.58%ε=39.85%39.41%64.57%18.01%57.24%69.13%29.76%59.71%71.35%ε=411.26%46.55%72.31%23.80%65.50%75.25%37.61%66.07%78.69%ε=513.01%59.32%77.01%27.12%72.05%83.27%46.07%75.15%86.38%Table 5
YALE and recall.
RecallLAPSWPSort-SWPLAP and AFSWP and AFSort-SWP and AFLAP and MFSWP and MFSort-SWP and MFε=177.34%82.51%84.18%79.58%84.83%83.05%73.62%82.49%85.26%ε=278.12%78.74%82.47%77.41%80.24%84.18%76.14%80.14%86.14%ε=380.34%83.56%87.51%78.87%81.07%86.91%79.35%81.61%85.36%ε=479.24%81.54%80.63%76.15%77.69%85.43%80.45%78.34%84.81%ε=575.39%82.37%85.66%78.56%82.48%88.75%79.51%81.95%87.57%Table 6
YALE and F1-score.
F1-sroceLAPSWPSort-SWPLAP and AFSWP and AFSort-SWP and AFLAP and MFSWP and MFSort-SWP and MFε=17.82%41.06%58.24%14.36%55.51%65.38%17.89%58.01%67.67%ε=212.46%45.06%67.67%21.54%60.83%70.38%29.42%64.39%73.82%ε = 317.55%53.56%74.31%29.32%67.10%77.01%43.29%68.96%77.73%ε=419.72%59.27%76.24%36.27%71.08%80.02%51.26%71.68%81.64%ε=522.19%68.97%81.11%40.32%76.91%85.92%58.34%78.40%86.97%


## 4.1. Sorting Method Experiment

Direct sorting will destroy theε-differential privacy. Therefore, this paper adopts an approximate sorting method—SAS algorithm—which satisfies theε-differential privacy. During the test, a one-dimensional array which is containing 57 random numbers is used as the experimental data set, and three sorting methods, namely, simulated annealing algorithm, exponential mechanism, and SAS algorithm, are selected for comparison. Besides, to verify the impact of the privacy budget on different ranking results, ε is taken as 0.4, 0.5, ln2, and 1, respectively. The results are shown in Figure 6.Figure 6
Noise statistics.In Figure7, the abscissa represents the number of times the algorithm is executed, and the ordinate represents the accuracy of the sorting. The following three conclusions can be drawn from the experimental results: (1) the sorting results of the simulated annealing algorithm are only related to the execution times of the algorithm and not relevant to the value of ε; (2) the ranking results of the exponential mechanism are only related to the value of ε, and the higher the value of ε is, the higher the sorting accuracy is. It is independent of the execution times of the algorithm; (3) the sorting results of the SAS algorithm are related to the value of ε and also related to the execution times of the algorithm, and they are proportional.Figure 7
Sorting result test.
(a)
ε=0.4(b)
ε=0.5(c)
ε=ln2(d)
ε=1


## 4.2. Simulation Experiment

In different kinds of images, the sensitive information of face photos is the most representative. Therefore, to verify the usability of the algorithm, it selects a front face photo (190∗160) to complete the corresponding experiment in this paper. The experimental results of different algorithms under the same conditions are shown in Figure 8. Figure 8(a) is the original image; Figure 8(b) is the resulting graph obtained by directly adding Laplace noise to the original image; Figure 8(c) is the resulting graph obtained by using the SWP algorithm; Figure 8(d) is the resulting graph obtained by using sort SWP algorithm. Compared with the LAP algorithm, the SWP algorithm and sort SWP algorithm have better display effect.Figure 8
Experimental results.
(a)
Original image(b)
LAP(c)
SWP(d)
Sort-SWPThe core of this paper is to use the Laplace mechanism in differential privacy protection to add noise to the image and to protect the sensitive information in the image. Therefore, to destroy the effect of privacy protection, it is a common method to eliminate or reduce the impact of image noise. For the methods of eliminating image noise, the representative methods are average filtering or median filtering. In Figures9 and 10, the mean filter and median filter are used to interfere with the experimental results in Figure 8. The purpose of this is to evaluate the degree of privacy protection and the usability of the protected images after noise elimination.Figure 9
Experimental results graph and mean filtering.
(a)
Original image and AF(b)
LAP and AF(c)
SWP and AF(d)
Sort-SWP and AFFigure 10
Experimental result graph and median filter.
(a)
Original image and MF(b)
LAP and MF(c)
SWP and MF(d)
Sort-SWP and MFNow, we have given a preliminary conclusion that the SWP algorithm and sort SWP algorithm are better than the LAF method. However, this conclusion is only obtained by observing the experimental results, so it may be one-sided or inaccurate. To further verify whether the conclusion is correct, the previous 12 images are transformed into a gray histogram for further comparison. Gray histogram reflects the relationship between the frequency of gray level pixels and gray level in an image, although the gray histogram cannot reflect the specific distribution of image pixels but reflect the impact of Laplace noise on the image as a statistical result.It can be seen from Figures11–13, under the same conditions, the histogram distribution of the SWP algorithm and lap algorithm is closer, but it is quite different from the distribution of pixels in the original image. The distribution of pixels in the histogram of the result of the sort SWP algorithm is consistent with the original image. Therefore, it can be considered that the noise interference caused by the sort SWP algorithm is the least.Figure 11
Gray histogram of experimental image.
(a)
Original image and GH(b)
LAP and GH(c)
SWP and GH(d)
Sort-SWP and GHFigure 12
Experimental image gray histogram and average filtering.
(a)
Original image and AF and GH(b)
LAP and AF and GH(c)
SWP and AF and GH(d)
Sort-SWP and AF and GHFigure 13
Experimental image gray histogram and median filter.
(a)
Original image and MF and GH(b)
LAP and MF and GH(c)
SWP and MF and GH(d)
Sort-SWP and MF and GHIn the papers related to differential privacy protection, the noise size is an important evaluation index to measure the advantages and disadvantages of the algorithm. Under the same conditions, less noise represents higher availability. Of course, as a special information carrier, image noise is only one of the evaluation indicators.If the pixel value of the gray-scale image is regarded as a value, the value after adding Laplace noise will change with the change ofε. The smaller the ε is, the greater the noise is, the higher the degree of privacy protection is, and there is no limit to the value. However, in the experiment, the range of the pixel value of the gray image is limited between 0 and 255, so even if the obtained value is beyond this range under the influence of noise, it will be normalized. That means all values greater than 255 will be changed to 255, and all values less than 0 will be changed to 0. Therefore, the error of the image after privacy protection is divided into absolute error and relative error. For example, in an image x, there is a pixel xmn=200. If xmn′=280 after adding noise, the absolute error value is 80, and the relative error value is 55.In Figure6, the absolute error and relative error value of the experimental result graph under the influence of different algorithms are given. The conclusion is that the error caused by the three algorithms is in line with the previous expectations, and compared with the LAP algorithm and SWP algorithm, the sort-SWP algorithm will cause the smallest error. Also, the median filter is slightly better than the average filter for Laplace noise.


## 4.3. Result Analysis

To verify the feasibility of the algorithm, the ORL face database, and YALE face database are used as experimental data sets, and the experimental environment is Intel® Corei9-9900K CPU@ 3.60 GHz,32 G memories, GTX 21080TI GPU, Windows 10 operating system. A face recognition method based on an improved AlexNet convolution neural network is adopted in the experiment. Compared with the AlexNet model, this method has a simpler network structure and fewer parameters, which can save a lot of model training time and then make a fast prediction. When using the ORL face database for the experiment, 5 images of each person are used as a training set, and other images are used as a test set. The sliding window length is 56,k=184. When using the YALE face database for experiments, random 5 images of each person are also used as the training set and the rest as the test set. The sliding window length is 160, k=486. Privacy budget ε is 1, 2, 3, 4, and 5. The test items are accuracy rate, recall rate, and F1 score. The experimental results are shown in Tables 1–6.Table 1
ORL and precision.
PrecisionLAPSWPSort-SWPLAP and AFSWP and AFSort-SWP and AFLAP and MFSWP and MFSort-SWP and MFε=16.52%39.29%53.86%9.27%47.09%60.55%14.95%49.01%65.39%ε=28.83%43.45%69.26%15.86%56.39%72.06%25.37%57.61%75.41%ε=311.37%48.29%71.66%22.00%63.39%79.27%36.61%72.18%83.68%ε=413.96%55.18%75.19%27.71%70.43%82.51%44.36%80.97%87.55%ε=516.67%62.72%82.83%33.08%76.36%86.19%51.98%88.70%91.33%Table 2
ORL and recall.
RecallLAPSWPSort-SWPLAP and AFSWP and AFSort-SWP and AFLAP and MFSWP and MFSort-SWP and MFε=171.32%77.96%83.58%72.35%81.63%84.57%80.12%83.47%88.14%ε=273.56%75.68%81.83%75.52%81.26%83.67%78.68%79.85%80.33%ε=375.79%83.81%85.25%77.53%84.36%85.23%81.18%86.63%84.54%ε=472.32%74.22%78.58%73.52%78.59%82.18%75.36%81.23%87.10%ε=577.91%76.23%80.12%78.07%80.11%82.51%80.12%81.15%83.94%Table 3
ORL and F1-score.
F1-sroceLAPSWPSort-SWPLAP and AFSWP and AFSort-SWP and AFLAP and MFSWP and MFSort-SWP and MFε=111.95%52.25%65.51%16.43%59.73%70.57%25.20%61.76%75.08%ε=215.77%55.21%75.02%26.21%66.58%77.43%38.37%66.93%77.79%ε=319.77%61.27%77.87%34.27%72.39%82.14%50.46%78.75%84.11%ε=423.40%63.30%76.85%40.25%74.29%82.34%55.85%81.10%87.32%ε=527.46%68.82%81.45%46.47%78.19%84.31%63.05%84.76%87.48%Table 4
YALE and precision.
PrecisionLAPSWPSort-SWPLAP and AFSWP and AFSort-SWP and AFLAP and MFSWP and MFSort-SWP and MFε=14.12%27.33%44.52%7.89%41.25%53.91%10.18%44.74%56.10%ε=26.77%31.56%57.38%12.51%48.98%60.47%18.23%53.82%64.58%ε=39.85%39.41%64.57%18.01%57.24%69.13%29.76%59.71%71.35%ε=411.26%46.55%72.31%23.80%65.50%75.25%37.61%66.07%78.69%ε=513.01%59.32%77.01%27.12%72.05%83.27%46.07%75.15%86.38%Table 5
YALE and recall.
RecallLAPSWPSort-SWPLAP and AFSWP and AFSort-SWP and AFLAP and MFSWP and MFSort-SWP and MFε=177.34%82.51%84.18%79.58%84.83%83.05%73.62%82.49%85.26%ε=278.12%78.74%82.47%77.41%80.24%84.18%76.14%80.14%86.14%ε=380.34%83.56%87.51%78.87%81.07%86.91%79.35%81.61%85.36%ε=479.24%81.54%80.63%76.15%77.69%85.43%80.45%78.34%84.81%ε=575.39%82.37%85.66%78.56%82.48%88.75%79.51%81.95%87.57%Table 6
YALE and F1-score.
F1-sroceLAPSWPSort-SWPLAP and AFSWP and AFSort-SWP and AFLAP and MFSWP and MFSort-SWP and MFε=17.82%41.06%58.24%14.36%55.51%65.38%17.89%58.01%67.67%ε=212.46%45.06%67.67%21.54%60.83%70.38%29.42%64.39%73.82%ε = 317.55%53.56%74.31%29.32%67.10%77.01%43.29%68.96%77.73%ε=419.72%59.27%76.24%36.27%71.08%80.02%51.26%71.68%81.64%ε=522.19%68.97%81.11%40.32%76.91%85.92%58.34%78.40%86.97%


## 5. Conclusions

To solve the privacy protection problem of face image publishing, this paper proposes to use the Laplace mechanism of differential privacy to add noise in the image, so that this should protect the sensitive information in the face image. Compared with directly adding Laplace noise to the image, the SWP algorithm and sort SWP algorithm can effectively reduce the impact of noise on the protected image. Especially sort SWP algorithm, which uses the SAS algorithm to sort and then execute the SWP algorithm, is proposed to further improve the usability of the protected face image. From the results of several test experiments, compared with the lap algorithm (ORL, Yale), the absolute error of SWP algorithm decreased by 40.81%, relative error decreased by 38.26%, accuracy increased by 35.01%, recall rate increased by 3.53%, and F1-sroce increased by 39.07%; absolute error of sort-SWP algorithm decreased by 64.12%, relative error decreased by 51.70%, accuracy increased by 56.63%, recall rate increased by 6.85%, and F1-sroce increased by 55.62%. Besides, in the test of SAS algorithm, compared with the exponential mechanism ranking method (the accuracy of simulated annealing algorithm is only related to the number of iterations), the average ranking accuracy of SAS algorithm is improved by 17.63%.The differential privacy protection method proposed in this paper is implemented by global noise adding. However, most of the sensitive information contained in a face image exists in some specific areas (such as eyes, mouth, nose, and other organs or feature points). The next research direction will be devoted to accurately finding the region of sensitive information and adding noise for those local regions. At the same time, the research will try to further reduce the impact of noise and improve the usability of face image after privacy protection.



---

*Source: 6680701-2021-01-07.xml*