量化SIFT和同態(tài)加密的隱私保護圖像檢索方法*

陳 帆

(合肥工業(yè)大學 計算機與信息學院，安徽 合肥 230000)

量化SIFT和同態(tài)加密的隱私保護圖像檢索方法*

陳 帆

(合肥工業(yè)大學 計算機與信息學院，安徽 合肥 230000)

提出了一種隱私語義保持的圖像內容檢索方法，將加密圖像中隱私保持尺度不變特征變換(SIFT)的提取方法和二進制SIFT算法融合在一起，不僅保證了上傳到服務器端的圖像是加密的，同時又能在加密空間保持其隱私語義。對圖像進行Paillier同態(tài)加密，保證了圖像在服務器端和傳輸過程中的安全性，在加密域提取SIFT特征，并將其用二進制表示，減少存儲空間和計算復雜度。實驗證明：經原始圖像特征提取后生成的二進制SIFT在穩(wěn)健性測試中獲得良好的效果，并且與加密圖像特征提取后生成的二進制SIFT保持等距，在明文域和密文域中保持了圖像搜索匹配的準確性，在匹配效率上得到提高。

圖像檢索； 尺度不變特征變換； 同態(tài)加密； 隱私保護

0 引 言

圖像檢索已經遠遠超越了最初基于文本標簽的搜索模式, 而圖像內容檢索(content-based image retrieval，CBIR)[1]技術在20世紀90年代興起?；趦热莸膱D像檢索主要是通過計算圖像全局特征和局部特征來對圖像進行表示。圖像全局特征包括紋理[2～4]、顏色[5～7]、形狀[8]等整幅圖像的底層特征，顯然這些底層特征與圖像高層語義之間存在較大的語義鴻溝，需要更高精確的圖像檢索。局部特征則主要集中在圖像比較顯著的區(qū)域，其中Lowe教授[9]提出尺度不變特征變換(scale invariant feature transform,SIFT)特征，由于其對旋轉、尺度縮放、亮度變化保持不變性，對視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性，Wang Z等人提出將SIFT特征在圖像內容檢索中應用廣泛[10]。

然而這種方法保證了圖像檢索的準確性，卻忽視了圖像的隱私性，網絡環(huán)境復雜由此帶來隱私泄露風險不容忽視，在圖像明文域以及用戶查詢的圖像都是明文，易受到攻擊。人們對圖像內容檢索的安全性提出更高的要求。 因此Hsu[11]提出了一種隱私保持的SIFT提取方法，即圖像首先進行Paillier同態(tài)加密[12]，由于同態(tài)加密的特性，加密域的加操作等價于明文域的乘操作，論證了加密圖像中計算SIFT的過程與明文圖像計算的SIFT特征點等價。主要是為了保證圖像在云端是加密的，搜索的圖像也是加密的，確保了圖像的隱私安全。

在SIFT特征匹配實現(xiàn)圖像檢索的過程中，由于特征維數(shù)較高，計算較為復雜。為了更好地提高圖像檢索匹配效率, 針對SIFT的量化工作也進行了多種研究，如Peker K A.[13]指出可以用中位數(shù)作為量化閾值，另外文獻[14]是通過主成分分析(PCA)篩選對SIFT特征進行降維。而這些工作主要是針對于提高圖像的檢索匹配效率，沒有考慮圖像在服務器端存儲的安全性。

本文提出來一種結合二進制SIFT和同態(tài)加密的隱私保護圖像檢索算法，結合了加密域中SIFT特征提取辦法以及SIFT量化，同時保證了圖像隱私安全以及加密圖像的檢索效率，并驗證了該方法的有效性和可行性。

1 相關工作

在圖像內容檢索特征中SIFT特征應用廣泛。傳統(tǒng)的圖像檢索方法中，由于“維數(shù)災難”使特征存儲空間大，檢索效率低下，因此，對SIFT特征進行降維。在圖像加密的各種算法中，為了使加密前和加密后的特征提取保持一致的效果，根據同態(tài)加密的特性選擇了同態(tài)加密。本文同時結合了這兩種方法。詳細描述如下。

1.1 Paillier加密

在解密時，給定密文c，使用私鑰λ得到明文m,使L(u)=u-1/N，則對于計算密文過程為m=D(c,λ)=(L(cλmodN2)/L(gλmodN2))modN，該加密系統(tǒng)滿足加同態(tài)，因為

c1×c2=E(m1,r1)×E(m2,r2)

=g(m1+m2)(r1r2)NmodN2=E(m1+m2)

(1)

即給定密文c1和c2,可以推導出明文m1+m2。在加同態(tài)的基礎上延伸出明文乘同態(tài)，如下

D([E(m1,r1)]m2modN2)=(m1×m2)modN

(2)

即明文的乘法等同于密文的取冪運算。

1.2 SIFT特征

SIFT特征主要應用于對象識別以及不同視角物體或場景的匹配等領域。SIFT特征的提取過程的主要步驟如下：

1.2.1 構造差分高斯尺度空間

首先,計算圖像I(x,y)與高斯函數(shù)G的卷積,L(x,y,σ)=G(x,y,σ)*(I(x,y)，用來對圖像進行不同程度的高斯模糊處理,得到不同尺度層次的圖像，其中尺度可變高斯函數(shù)為

(3)

然后,計算相鄰高斯模糊圖像的差值得到差分高斯D，即構造差分高斯尺度空間。

D(x,y,σ)=(G(x,y,kσ)-G(x,y,σ))*I(x,y)

=L(x,y,kσ)-L(x,y,σ)

(4)

1.2.2 特征點檢測及定位

在差分高斯的金字塔中，將每個像素點與其所在的圖像鄰域的8個像素以及它所在的向量尺度空間上下2幅圖對應位置鄰域各9個點，總共26個點進行像素值比較，如果該點是最大或者最小點，則該點就暫時列為特征點。

繼續(xù)精確定位極值點，在已經檢測到的特征點中去掉低對比度的特征點和不穩(wěn)定邊緣相應點，其本質是剔除DoG局部曲率非常不對稱的像素。

1.2.3 方向分配生成SIFT算子

在已定位的特征點附近選取一個區(qū)域，并對該區(qū)域0°～360°分為36個單元統(tǒng)計像素的梯度方向直方圖，每10°為一個單元，將直方圖中大于峰80%的梯度方向作為主方向。以特征點為中心將鄰域像素相對主方向進行旋轉，選取一個方形的局部區(qū)域，分割成4×4的塊，統(tǒng)計每塊的梯度方向直方圖，最終得到4×4×8=128維的SIFT描述子。

1.3 二進制SIFT

1.3.1 原始SIFT特征提取

給定圖像I計算其SIFT特征點，記為F(I)={F1,…,Fi,…,Fn}(1≤i≤n)，其中F1,…,Fn為圖像I的特征點，n為特征點的個數(shù)，每個特征點Fi通常采用m維的向量表示，即Fi=(fi,1,…,fi,m)。

1.3.2 SIFT特征量化

(5)

1.3.3 二進制SIFT距離衡量

在將每個SIFT特征點轉化為比特串之后，B-SIFT距離度量通過計算不同比特位的數(shù)量，采用漢明距離來計算相似度, 即每個特征進行按位異或運算，計算過程表示如下

(6)

2 隱私保護圖像檢索算法

將以上3種處理過程融合在一起,提出了一種二進制隱私保持SIFT(binary privacy preserving SIFT,B-PPSIFT)。為了使密文域的操作得到與在明文域的操作一樣的結果，同態(tài)加密已經被廣泛研究。由于Paillier加密中密文的加操作等同于明文的乘操作，這里選取的是Paillier同態(tài)加密。如圖1所示,SIFT特征，對此時SIFT特征使用B-SIFT同樣的量化方法進行壓縮處理，最終為了保證原始SIFT以及B-PPSIFT相比有同樣的匹配效果。

圖1 B-PPSIFT的計算過程

計算過程如圖2所示。對給定圖像I,直接提取SIFT特征記為F(I)，對其進行量化得到B-SIFT，記為F′(I)。圖像I經同態(tài)加密運算后的圖像記為Ie，對加密的圖像進行SIFT特征提取記為F(Ie)，在此基礎上進行量化生成B-PPSIFT，記為F′(Ie)。

首先給定圖像I，在B-SIFT中，采用漢明距離進行圖像相似性度量，與原始SIFT中采用的歐氏距離相比保持幾乎一致的準確性，如式(7)所示

(7)

式中simO為用歐氏距離計算兩個特征點之間的相似性;simH為漢明距離計算兩個特征比特串之間的相似性;Ix和Iy分別表示圖像x和圖像y中的兩個特征點。

如圖2所示，其中①兩端所指的F(I)和F′(I)在分別使用歐氏距離和漢明距離衡量時具有等價一致性。那么將I替換為Ie，可由式(7)推導出式(8)

(8)

圖2 計算過程示意圖

此時在②兩端同樣具有距離保持等價性。

在圖像加密域中提取SIFT,首先要計算差分高斯。由Hsu等人已經證明在圖像經同態(tài)加密后提取差分高斯De與直接計算差分高斯D有De(x,y,ρ)=E(D(x,y,ρ),Rρ)關系。Rρ為組合一致選擇值，依賴于G()，而不是圖像大小。ρ表示相鄰高斯模糊圖像的差值ρ=ρi-ρj。即用戶將加密的圖像Ie上傳到服務器，在密文域計算的差分高斯與直接用Rρ加密在尺度ρ上的差分高斯保持相等。在極值點定位時，對于a1和a2，如果a1>a2，那么E(D(x1,y1,ρ1),Rρ1)

(9)

又因在同樣的向量空間進行距離衡量，歐氏距離對應L2范數(shù)，由于在有限維線性空間的所有范數(shù)都具有等價性，則有

(10)

由等價性的傳遞原則，在這里對原始圖像SIFT特征點的距離度量方法選用歐氏距離，對F′(Ie)采取漢明距離。綜上可以證明④，即在原始圖像使用歐氏距離與B-PPSIFT中計算漢明距離是等價的，如式(11)所示

(11)

圖像檢索場景適用于用戶上傳圖像的B-PPSIFT，此時服務器就無法得知用戶想要查詢的圖像。而在服務器端存儲的是加密的圖像以及對應的B-PPSIFT，這時在圖像搜索階段，是通過密文的二進制進行匹配。保證安全性的同時，也保護了圖像的隱私。

3 實驗與分析

3.1 穩(wěn)健性實驗

實驗采用 StirMark 4.0基準測試程序[15]來驗證程序針對惡意攻擊的穩(wěn)健性，實驗采用5種不同內容的彩色圖像如圖3所示，從左到右依次為，I1：Lena；I2：pens；I3：baboon；I4：pepper；I5：flower，每類圖像都進行12種不同類型的攻擊，變換實驗過程類似于復制圖像檢測。

圖3 5種不同的彩色圖像

在實驗過程中，將加密圖像的B-PPSIFT二進制串作為查詢圖像，在實驗數(shù)據庫中進行匹配，通過對比B-PPSIFT，衡量能正確檢測到圖像數(shù)量。結果如表1所示，每種攻擊對應的數(shù)字表示不同參數(shù)下攻擊產生的版本。通過本文作者的實驗結果可以知道，總共480幅圖像中，對每一類原始圖像有96個攻擊圖像，其中能正確檢測到圖像為427, 表明識別的正確率為88.95 %，而在檢測失敗的情況中包括加噪、裁剪，在原始SIFT中也同樣檢測失敗。實驗結果顯示這種方法保證了同樣有效的穩(wěn)定性并保證了圖像隱私。

表1 StirMark4下的穩(wěn)健性測試

3.2 圖像檢索實例

為了證明本文作者提出B-PPSIFT方法在圖像識別上的準確性，采用數(shù)據庫Caltech 256[16]包含多種對象類別，并在形狀上具有高度可變性，隨機選擇了10種常用類別的圖像作為實驗數(shù)據，每類圖像包含60張圖像，其中30張作為查詢圖像，其他的則一起存儲數(shù)據庫中作為被查詢圖像。這10類圖像分別記為(C1：forg；C2：goat；C3：ak47；C4：backpack；C5：Colculator；C6：bear；C7：bulldozer；C8：dolphin；C9：Eyeglasse；C10：grand-piano)，當給定查詢的圖像，先計算它的B-PPSIFT，然后同樣計算圖像庫中圖像的B-PPSIFT，進行匹配，之后根據匹配的特征點數(shù)進行排序，找出最接近的一幅或多幅圖像，實驗結果用最接近的k幅圖像來表示。這里設置k=1,2,3,5，10時，識別效果與原始SIFT接近，結果如表2所示。第一列表示10種不同的類型的圖像，Ⅰ表示原始SIFT特征，Ⅱ表示B-PPSIFT。表格中數(shù)字表示對應top-k正確識別的個數(shù)，比如top-3中C3對應的兩行，第一行表示原始SIFT在k=5時，正確搜索到的圖像為21；采用B-PPSIFT時，正確識別的圖像為26。

由實驗結果可以看出，B-PPSIFT的識別率與原始SIFT的識別率基本相當。需要指出，實驗結果顯示的識別率不是太好，是因為實驗僅僅采用了特征點的匹配，沒有采用分類器的設計方法。如果繼續(xù)用先進的特征表示和設計良好的分類方法，效果會得到進一步改善。實驗表明，B-PPSIFT與原始SIFT有幾乎相當?shù)牟樵冃Ч?/p>

表2 SIFT和B-PPSIFT的識別結果對比

由表3可知，第三行表示當特征點數(shù)為5×106時，B-PPSIFT的檢索時間為200 ms, 而SIFT的檢索時間為20 000 ms。大大減少了搜索時間，提高了匹配效率。

表3 存儲空間和匹配速度結果對比

4 結束語

本文提出了一種結合同態(tài)加密和SIFT特征提取以及 SIFT量化的一種圖像隱私保護搜索方法，理論驗證了這種方法在距離度量時具有的等價一致性，證明其結合的可行性，并用實驗說明能達到魯棒性和準確性較好的效果。在圖像檢索中適用于對隱私保護有需求的用戶，比如在多媒體檢索中保護用戶隱私，當用戶將加密數(shù)據作為查詢內容發(fā)送至服務器端，服務器則可以在接收到加密的數(shù)據時，無需解密完成查詢匹配過程，最終將對應的加密數(shù)據返回給用戶。整個過程中，服務器端以及在傳輸過程中都是加密的圖像，保護了數(shù)據隱私同時高效完成了查詢任務。在未來圖像安全會越來越成為大家的主要考慮因素。

下一步將針對搜索的算法進行研究，加密圖像SIFT量化后是否還可以繼續(xù)進行降維壓縮，或者在搜索索引的建立上進一步提高方法的有效性。

[1] Venkat N，Gudivada,Vijay V，Raghavan.Content-based image retrieval systems-guest editors' introduction[J].IEEE Computer,1995,28(9):18-22.

[2] Tamura H,Mori S,Yamawaki T.Textural features corresponding to visual perception[J].IEEE Transactions on Systems,Man and Cybernetics,1987,8(6):460-473.

[3] Liu G H,Yang J Y,Manjunath B S,et al.Texture features for browsing and retrieval of image data[J].IEEE Transactionson on Pattern Analysis and Machine Intelligence,1996,18(8):837-842.

[4] Liu G H,Zhang L,Hou Y K,el al.Image retrieval based on multi-texton histogram[J].Pattern Recognition,2010,43(7):2380-2389.

[5] Liu G H,Yang J Y.Content-based image retrieval using color difference histogram[J].Pattern Recognition,2013,46(1):188-198.

[6] Chen B J,Shu H J,Zhang H,et al.Quaternion Zernike moments and their invariant for color image analysis and object recogni-tion[J].Signal Processing,2012,92(2):308-318.

[7] Mehtar-Tani Y,Salgado C A,Tywoniuk.Jets in QCD media:From color coherence to decoherence[J].Physics Letters B,2012,707(1):156-159.

[8] Wang F,Lin L,Tang M.A new sketch-based 3D model retrieval approach by using global and local features[J].Graphical Models,2013,76(3):128-139.

[9] Lowe D G.Distinctive image features from scale-invariant key points[J].International Journal of Computer Vision,2004,60(2):91-110.

[10] Wang Z,Jia K,Liu P.An effective web content-based image retrieval algorithm by using SIFT feature[C]∥The Third World Congress on Software Engineering,2009:291-295.

[11] Chao-Yung H,Chun-Shien L,Soo-Chang P.Image feature extraction in encrypted domain with privacy-preserving SIFT[J].IEEE Transactions on Image Processing:A Publication of the IEEE Signal Processing Society,2012,21(11):4593-4607.

[12] Paillier P.Public-key cryptosystems based on composite degree residuosity classes[J].Proc Eurocrypt,1999,547(1):223-238.

[13] Peker K A.Binary SIFT:Fast image retrieval using binary quantized SIFT features[C]∥International Workshop on Content-based Multimedia Indexing,2011:217-222.

[14] Fotouhi M,Kasaei S,Mirsadeghi S E,et al.BSIFT:Boosting SIFT using principal component analysis[C]∥Conference on Electrical Engineering,2014:1130-1135.

[15] Fabien A P Petitcolas.Watermarking schemes evaluation[J].IEEE Signal Processing,2000,17(5):58-64.

[16] Griffin G,Holub A,Perona P.Caltech-256 object category data-set[R].Pasadena:California Institute Technology,2007.

Privacy preserving image retrieval method based on binary SIFT and homomorphic encryption*

CHEN Fan

(College of Computer Science and Information Engineering,Hefei University of Technology,Hefei 230000,China)

A privacy preserving image content retrieval method,which combines privacy preserving SIFT extraction method in encrypted image with binary SIFT algorithm is proposed.In this way,it can not only guarantee the image uploaded to the server is encrypted,but also keep its semantic privacy in encrypted domain.Image is encrypted by using Paillier homomorphic encryption,this can ensure security of image on server end.And SIFT features are extracted in the encrypted domain,after that the features are converted to a binary representation,reduce storage space and computational complexity.Experimental results show that the binary SIFT extracted from encrypted domain performs well in robustness evaluation,and the similarity distances between binary SIFT generated from the original image and the binary SIFT generated from the encrypted image keep the same, and ensure accuracy of image searching and matching in plaintext and ciphertext domain，and the matching efficiency is improved.

image retrieval; SIFT; homomorphic encryption; privacy preserving

10.13873/J.1000—9787(2017)05—0083—05

2016—05—21

國家自然科學基金資助項目(61272540)； 安徽省自然科學基金資助項目(11040606M138)

TP 391.4; TP 309.7

A

1000—9787(2017)05—0083—05

陳 帆(1992-)，女，碩士，主要研究方向為圖像隱私保護。