Efficient Privacy Preserving Viola-Jones Type Object Detection via Random Base Image Representation
Xin Jin Peng Yuan Xiaodong Li Chenggen Song Shiming Ge Geng Zhao Yingya Chen




𝐱
ŁL








Xin Jin^1, Peng Yuan^1,2, Xiaodong Li^1,*, Chenggen Song^1, Shiming Ge^3, Geng Zhao^1, Yingya Chen^1 This work is partially supported by the National Natural Science Foundation of China (Grant NO.61402021, 61402023, 61640216), the Science and Technology Project of the State Archives Administrator (Grant NO. 2015-B-10), the open funding project of State Key Laboratory of Virtual Reality Technology and Systems, Beihang University (Grant NO. BUAA-VR-16KF-09), and the Fundamental Research Funds for the Central Universities (NO. 2016LG03, 2016LG04).





^1Beijing Electronic Science and Technology Institute,
Beijing 100070, China

^2Xidian University, Xi'an 710071, China

^3Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100095, China
Corresponding Author: lxd@besti.edu.cn


















Efficient Privacy Preserving Viola-Jones Type Object Detection 
 via Random Base Image Representation
    Byung-Woo Hong    Ja-Keoung Koo

Chung-Ang University, Korea

{hong,jakeoung}@cau.ac.kr









Stefano Soatto

University of California Los Angeles, U.S.A.

soatto@cs.ucla.edu

    
======================================================================================================================================================================================






A cloud server spent a lot of time, energy and money to train a Viola-Jones type object detector <cit.> with high accuracy. Clients can upload their photos to the cloud server to find objects. However, the client does not want the leakage of the content of his/her photos. In the meanwhile, the cloud server is also reluctant to leak any parameters of the trained object detectors. 10 years ago, Avidan & Butman introduced Blind Vision, which is a method for securely evaluating a Viola-Jones type object detector. Blind Vision uses standard cryptographic tools and is painfully slow to compute, taking a couple of hours to scan a single image. The purpose of this work is to explore an efficient method that can speed up the process. We propose the Random Base Image (RBI) Representation. The original image is divided into random base images. Only the base images are submitted randomly to the cloud server. Thus, the content of the image can not be leaked. In the meanwhile, a random vector and the secure Millionaire protocol are leveraged to protect the parameters of the trained object detector. The RBI makes the integral-image enable again for the great acceleration. The experimental results reveal that our method can retain the detection accuracy of that of the plain vision algorithm and is significantly faster than the traditional blind vision, with only a very low probability of the information leakage theoretically.



Blind Vision, Random Base Image, Privacy Preserving, Object Detection









§ INTRODUCTION


Recently, widespread smart phones with cameras enable people to shot images and videos nearly anytime and anywhere. Millions of surveillance cameras including the driving recorders captures images and videos every second. All these conveniences devices are producing the large-scale visual media data, which is considered as the biggest big data.




Due to the limited storage space of these terminal devices, large-scale visual media data is being uploaded and stored in the cloud servers. Not only the storage, but also the processing of large-scale visual media data are being outsourced to the cloud servers. 

The cloud servers have some strong algorithms such as face/object detection, face/object recognition, intelligent video surveillance. Nowadays, people can easily find all the faces in their photos stored in the cloud servers using the powerful face detection algorithms maintained by the cloud servers. However, the cloud servers are always third party entities. Thus the privacy of the users' visual media data may be leaked to the public or unauthorized parties.

In the meanwhile, the powerful cloud services for visual media analysis and processing need a lot of money, data and time from the cloud server producers. The cloud servers are also reluctant to leak any parameters of the trained models or some protected details of their algorithms with copyrights.

Thus, the privacy of both the content of the visual media from the clients and the parameters of the vision algorithms from the cloud servers should be protected. 10 years ago, Avidan & Butman introduced Blind Vision <cit.>, which is a method for securely evaluating a Viola-Jones type face detector. Blind Vision uses standard cryptographic tools and is painfully slow to compute, taking a couple of hours to scan a single image. 

After that, rich literatures have been proposed in this field. The cryptographic tools such as secret sharing (SS) <cit.>, security multi-party computation (SMC) <cit.>, homomorphic encryption (HE) <cit.>, garbed circuit (GC) <cit.>, Chaotic System (CS) <cit.> are heavily used. Plenty of computer vision applications have been modified to the privacy preserving or secure versions such as private face detection <cit.>, face recognition <cit.>, content based image retrieval <cit.>, visual media search on public datasets <cit.>, intelligent video surveillance <cit.>.


However, most of these work rely heavily on cryptographic tools, which are painfully slow to compute or need bit by bit interaction between the clients and the cloud servers. In this paper, we revisit the Blind Vision <cit.> and attempt to make the blind vision towards cryptographic-free, without losing the security properties. We use  randomness and only a little cryptographic operations to protect the visual media data of the clients and the parameters of the trained models in the cloud servers. 


A novel image representation called Random Base Image(RBI) representation is proposed. In this work, we also investigate the object detection in the cloud. We apply our RBI to the famous Viola and Jones object detection method and propose a novel blind object detection method.  We separate an image into random base images. The weight of each base image is only known by the client. The base images are sent randomly to the cloud server. The cloud server cannot recover anything from the random base images. A random vector  and the secure Millionaire protocol <cit.> are leveraged to protect the parameters of the trained object detector. The RBI makes the integral-image enable again for the great acceleration. The experimental results reveal that our method is significantly faster than the traditional blind vision, with only a very low probability of the information leakage theoretically. 

  



































§ SECURE OBJECT DETECTION


In this section we develop a secure object detector with the random base image representation.




 §.§ Notations


Our scenario and the notations are the same as that of traditional Blind Vision <cit.>, as show in Figure <ref>. Denote some L dimensions finite field F that is large enough to represent all the intermediate results. Denote by X the image that Alice owns. A particular detection window within the image X will be denoted by x ∈ F^L and x will be treated in vector form. Bob owns a strong classifier of the form


    H(𝐱) = sign(∑_n=1^Nh_n(𝐱)),

where h_n(𝐱) is a threshold function of the form


    h_n(𝐱) = 
       α_n   𝐱^T𝐲_𝐧 > θ_n 
       β_n    otherwise,

and y_n ∈ F^L is the hyperplane of the threshold function h_n(𝐱). The parameters α_n ∈ F, β_n ∈ F and θ_n ∈ F of h_n(𝐱) are determined during training; N is the number of weak classifiers used.





 §.§ The Random Base Image Representation

The core idea of our RBI is to separate the original image into some random base images with fixed weights. The original image can be recovered by all the base images. The sparse representation can be considered as the one has such ability. However, they need another image dataset for learning the base images. Further more, there could be reconstruction error. Thus, we fix the weights and randomize the base images themselves.

The detection window 𝐱 can be represented as:


    𝐱 = ∑_i=0^M-1w_i𝐁_i,

where 𝐁_i is the base image with weight w_i. As is shown in Figure <ref>, each base image has a fixed weight. The base image itself is randomly determined. The number of the base image is set to M=256. Thus, each base image can be a binary image, which is easy for network transfer and fast to compute. In addition, there are 256! permutation of the base image which is not easy to guess. The process of the RBI generation is described in Algorithm <ref>.


 

 








 §.§ Secure Object Detection with RBI




  §.§.§ Secure Object Classifier Protocol

The core of our method is the secure object classifier protocol as is described in Algorithm <ref> and Figure <ref>. For secure object detection, Alice first divides the test image 𝐗 into Q detection windows {𝐱_1,𝐱_2,...𝐱_Q}. Then the detection windows are randomly sent to Bob as the inputs of the secure face classifier protocol one by one. Using the Algorithm <ref>, Alice and Bob know which detection windows are the target objects. Because the detection windows are randomly sent to Bob, only Alice learns the location of all the detected faces in the original image. Bob does not learn the contents including where the faces are in the image of Alice. Alice learns nothing about the parameters of the face detector of Bob.












 




The body of Algorithm <ref> is described as follows:




  * (1): Alice factorizes the detection window x into M random base images 𝐁={𝐁_0, 𝐁_1,..., 𝐁_M-1} with weight w={w_0,w_1,...,w_M-1}={0,1,...,M-1} through Algorithm <ref>.


  * (2): Alice randomly shuffles the weight w to w'. The random base images 𝐁 are permuted with the same order of that of w'={w'_0,w'_1,...,w'_M-1} to 𝐁'={𝐁'_0, 𝐁'_1,..., 𝐁'_M-1}, which is sent to Bob.



  * (3): In one cascade, Bob has N weak classifiers with parameter vectors 𝐲={𝐲_0,𝐲_1,...𝐲_N-1}. Bob randomly add K fake weak classifiers and set their parameters α and β to zero. Bob randomly shuffles the N+K true and fake weak classifiers to form 𝐲'={𝐲'_0,𝐲'_1,...𝐲'_N+K-1}. Then, Bob generates N+K random positive numbers s={s_0,s_2,...,s_N+K-1}. For each parameter vector 𝐲'_n ∈𝐲'. Bob and Alice repeat the following 3 steps.





  * (3.1): Bob computes the feature responses for all the base image 𝐁'_m in 𝐁' by F_m(n)=𝐁_m^'T𝐲'_n, m=0,1,...,M-1. All the M responses of base images 𝐁' on each parameter vector 𝐲'_n are sent back to Alice.



  * (3.2): Alice computes the feature responses of the detection window 𝐱 by F(n) = ∑_m=0^M-1F_m(n)w'_m. 



  * (3.3): Alice and Bob use the secure Millionaire protocol <cit.> to determine which number is larger: F(n) or θ_n. Bob send α_n+s_n or β_n+s_n to Alice. Alice store it as c_n.







  * (4): Alice and Bob use the secure Millionaire protocol <cit.> to determine which number is larger: ∑_n=1^N+Kc_n or ∑_n=1^N+Ks_n. If Alice has a larger number then x is positively classified, otherwise x is negatively classified.












  §.§.§ Security
 The protocol protects the security of both parties. The protocol protects the contents of the image from Alice and the parameters of the face detector from Bob. We analyse the security of Algorithm <ref> in the following paragraph.


 
  * From Alice to Bob
 
 	
 	
  * In step 2, Alice send randomly shuffled base images to Bob. Bob only knows the randomly generated base images and do not know the weight of each base image. The probability of guessing out the right permutation is 1/M!. Even Bob guesses out the right permutation, he does not know the weight of each base image. Thus, it is almost impossible for Bob to recover the detection window of Alice.
 	
  * In the 3th sub-step of step 3 and the step 4. Alice and Bob engage in secure Millionaire protocol <cit.>. so Bob can learn nothing about Alice’s data.
 	
 	
 	
 
  * From Bob to Alice
 
 	
	
  * In the 1st sub-step of step 3, Alice can not learn the number of the weak classifiers N or the true filters from the received feature responses. The true filters are obfuscated by the fake filters. 
 	
  * In the 3rd sub-step of step 3, Alice and Bob engage in a secure Millionaire protocol so Alice only learns if F(n)>θ_n. She can not learn anything about the parameter θ_n. Moreover, at the end of the Millionaire protocol Alice learns either α_n+s_n or β_n+s_n. In both cases, the real parameter (α_n or β_n) is obfuscated by the random number s_n.
	
  * In step 4, Alice and Bob use the secure Millionaire protocol to determine which number is larger: ∑_n=1^Nc_n or ∑_n=1^Ns_n. If Alice has a larger number then x is positively classified, otherwise x is negatively classified.
 	
 	 
 
  * Multiple Cloud Servers
 	
 	
  * The M random base images can be also sent to multiple cloud server with the same object detector to increase security.
 	 
 	 







  §.§.§ Complexity and Efficiency
 The complexity of the protocol is O(M(N+K)L), where M is the number of the base images. N and K are the numbers of the true and fake weak classifiers, respectively. L is the dimensionality of the detection window x.

Unlike the traditional Blind Vision <cit.>, in which the OT operation is used extensively, the proposed method only use OT operation to compare 2 numbers. In the secure dot-product protocol, each pixel of each detection window uses a OT_1^256 operation, which needs 1 RSA encryption and 256 RSA decryption with 128-bit long encryption keys. We leverage our M random images, whose computation is much faster than the RSA encryption and decryption operations.

In addition, in the traditional Blind Vision <cit.>, they convert the integral-image representation to regular dot-product operation, a step that clearly slows down their implementation as they no longer take advantage of the integral-image representation. In our RBI based protocol, the integral-image representation is enabled again, which accelerates the computation obviously.






§ EXPERIMENTS

We convert the Viola-Jones type object detector <cit.> to our secure object detector. We implement our RBI based object detector using Microsoft Visual Studio 2012 and OpenCV 2.4.3/10. [http://opencv.org/] package for computer vision in a 64 bits Windows 7 operating system. The hardware configuration is 3.5GHz AMD A10 Pro-7800 R7 CPU with 12 compute Cores and 8GB Memory. 

The face detector is from the OpenCV 2.4.3 package and consists of a cascade of 22 rejectors, where each rejector is of the form presented in Eq. <ref>. The first rejector consists of 3 weak classifiers. The most complicated rejector consists of 213 weak classifiers. There is a total of 2135 weak classifiers. We also test the nose detector, the eye detector and the full body detector from OpenCV 2.4.10.










 §.§ The Detection Accuracy










We test our secure face detector in 3 face detection datasets: The Face Detection Dataset (FDDB) <cit.>, The Face96 Dataset <cit.>, and The FEI Face Database <cit.>.









We randomly select 100 face images from each of the 3 datasets. The detection accuracy (88.46%) of our secure face detector is the same as that of the OpenCV 2.4.3 face detector (88.46%). 

The nose and the eye detectors are tested on the FDDB dataset <cit.>. The full body detector is tested on the INRIA Person dataset <cit.>. We randomly select 100 images from each of the 2 datasets. The detection accuracy of our secure object detectors is the same as that of the OpenCV 2.4.10 nose, eye and full body detectors.
































 §.§ Comparison with Other Methods
 
We compare our method with the  Viola-Jones method implemented by the OpenCV package and the method of the traditional Blind Vision <cit.>. 50 test images with size of 100 × 100 are randomly selected from each of the 3 datasets. The average running time is shown in Table <ref>. All the methods are running in client and server mode. For the Viola-Jones, Alice send the original image to Bob. Then, Bob runs the Viola-Jones method and return the detected windows to Alice. Our method is slower than the Viola-Jones method, which is running on plain images without protecting any privacy. According to the traditional Blind Vision method <cit.>, the time-consuming OT operation is heavily used and the integral-image representation is disabled. Thus, they have to take a couple of hours to scan a single image, which is painfully slow. Although in our method, the only information that Bob learns is that how many faces are in the image of Alice, our cryptographic-free method is significantly faster than the previous work towards practical usage of blind vision applications.


In addition, we compare our method with the Viola-Jones method implemented by the OpenCV package and the method of the traditional Blind Vision <cit.>. 50 test images with size of 100 × 100 are randomly selected from each of the FDDB and the INRIA Person datasets. The average running times are shown in the last 3 rows of Table <ref>. All the methods are running in client and server mode.





































































§ CONCLUSIONS AND DISCUSSIONS

We propose a novel random base image representation (RBI) for efficient object detection applications. The traditional blind vision method applies secure multi-party techniques to vision algorithm. Their method reveals no information to either party at the expanse of heavy computation load. Our method is an attempt towards cryptographic-free. Alice learns nothing about the parameters of the face detector of Bob. Bob does not know the contents of the image of Alice. The only information may be leaked is that Bob have a probability 1/M! to guess out the right permutation of the base images. This is just a theoretical event. Even Bob guesses out the right permutation, he does not know the weight of each base image.  Thus it is almost impossible for Bob to learn the information of the detection window of Alice. Because the heaviest cost of OT operation in the secure dot-production of <cit.> is avoided by our RBI based dot-production, the Millionaire version protocol of ours need much less time than the traditional blind vision protocol does.


There are several extensions to this work. First is the need to accelerate the secure blind vision to practical use, i.e. to reduce the time cost to near that of the vision algorithm without security consideration. Second is to make both the training and the test blind. This will make the client users to upload more visual data to the cloud without worrying about the privacy leakage. 




































































































































IEEEbib


