量化SIFT和同态加密的隐私保护图像检索方法*

陈 帆

(合肥工业大学 计算机与信息学院，安徽 合肥 230000)

量化SIFT和同态加密的隐私保护图像检索方法*

陈 帆

(合肥工业大学 计算机与信息学院，安徽 合肥 230000)

提出了一种隐私语义保持的图像内容检索方法，将加密图像中隐私保持尺度不变特征变换(SIFT)的提取方法和二进制SIFT算法融合在一起，不仅保证了上传到服务器端的图像是加密的，同时又能在加密空间保持其隐私语义。对图像进行Paillier同态加密，保证了图像在服务器端和传输过程中的安全性，在加密域提取SIFT特征，并将其用二进制表示，减少存储空间和计算复杂度。实验证明：经原始图像特征提取后生成的二进制SIFT在稳健性测试中获得良好的效果，并且与加密图像特征提取后生成的二进制SIFT保持等距，在明文域和密文域中保持了图像搜索匹配的准确性，在匹配效率上得到提高。

图像检索； 尺度不变特征变换； 同态加密； 隐私保护

0 引 言

图像检索已经远远超越了最初基于文本标签的搜索模式, 而图像内容检索(content-based image retrieval，CBIR)[1]技术在20世纪90年代兴起。基于内容的图像检索主要是通过计算图像全局特征和局部特征来对图像进行表示。图像全局特征包括纹理[2～4]、颜色[5～7]、形状[8]等整幅图像的底层特征，显然这些底层特征与图像高层语义之间存在较大的语义鸿沟，需要更高精确的图像检索。局部特征则主要集中在图像比较显著的区域，其中Lowe教授[9]提出尺度不变特征变换(scale invariant feature transform,SIFT)特征，由于其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性，Wang Z等人提出将SIFT特征在图像内容检索中应用广泛[10]。

然而这种方法保证了图像检索的准确性，却忽视了图像的隐私性，网络环境复杂由此带来隐私泄露风险不容忽视，在图像明文域以及用户查询的图像都是明文，易受到攻击。人们对图像内容检索的安全性提出更高的要求。 因此Hsu[11]提出了一种隐私保持的SIFT提取方法，即图像首先进行Paillier同态加密[12]，由于同态加密的特性，加密域的加操作等价于明文域的乘操作，论证了加密图像中计算SIFT的过程与明文图像计算的SIFT特征点等价。主要是为了保证图像在云端是加密的，搜索的图像也是加密的，确保了图像的隐私安全。

在SIFT特征匹配实现图像检索的过程中，由于特征维数较高，计算较为复杂。为了更好地提高图像检索匹配效率, 针对SIFT的量化工作也进行了多种研究，如Peker K A.[13]指出可以用中位数作为量化阈值，另外文献[14]是通过主成分分析(PCA)筛选对SIFT特征进行降维。而这些工作主要是针对于提高图像的检索匹配效率，没有考虑图像在服务器端存储的安全性。

本文提出来一种结合二进制SIFT和同态加密的隐私保护图像检索算法，结合了加密域中SIFT特征提取办法以及SIFT量化，同时保证了图像隐私安全以及加密图像的检索效率，并验证了该方法的有效性和可行性。

1 相关工作

在图像内容检索特征中SIFT特征应用广泛。传统的图像检索方法中，由于“维数灾难”使特征存储空间大，检索效率低下，因此，对SIFT特征进行降维。在图像加密的各种算法中，为了使加密前和加密后的特征提取保持一致的效果，根据同态加密的特性选择了同态加密。本文同时结合了这两种方法。详细描述如下。

1.1 Paillier加密

在解密时，给定密文c，使用私钥λ得到明文m,使L(u)=u-1/N，则对于计算密文过程为m=D(c,λ)=(L(cλmodN2)/L(gλmodN2))modN，该加密系统满足加同态，因为

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

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

(1)

即给定密文c1和c2,可以推导出明文m1+m2。在加同态的基础上延伸出明文乘同态，如下

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

(2)

即明文的乘法等同于密文的取幂运算。

1.2 SIFT特征

SIFT特征主要应用于对象识别以及不同视角物体或场景的匹配等领域。SIFT特征的提取过程的主要步骤如下：

1.2.1 构造差分高斯尺度空间

首先,计算图像I(x,y)与高斯函数G的卷积,L(x,y,σ)=G(x,y,σ)*(I(x,y)，用来对图像进行不同程度的高斯模糊处理,得到不同尺度层次的图像，其中尺度可变高斯函数为

(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个点进行像素值比较，如果该点是最大或者最小点，则该点就暂时列为特征点。

继续精确定位极值点，在已经检测到的特征点中去掉低对比度的特征点和不稳定边缘相应点，其本质是剔除DoG局部曲率非常不对称的像素。

1.2.3 方向分配生成SIFT算子

在已定位的特征点附近选取一个区域，并对该区域0°～360°分为36个单元统计像素的梯度方向直方图，每10°为一个单元，将直方图中大于峰80%的梯度方向作为主方向。以特征点为中心将邻域像素相对主方向进行旋转，选取一个方形的局部区域，分割成4×4的块，统计每块的梯度方向直方图，最终得到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为特征点的个数，每个特征点Fi通常采用m维的向量表示，即Fi=(fi,1,…,fi,m)。

1.3.2 SIFT特征量化

(5)

1.3.3 二进制SIFT距离衡量

在将每个SIFT特征点转化为比特串之后，B-SIFT距离度量通过计算不同比特位的数量，采用汉明距离来计算相似度, 即每个特征进行按位异或运算，计算过程表示如下

(6)

2 隐私保护图像检索算法

将以上3种处理过程融合在一起,提出了一种二进制隐私保持SIFT(binary privacy preserving SIFT,B-PPSIFT)。为了使密文域的操作得到与在明文域的操作一样的结果，同态加密已经被广泛研究。由于Paillier加密中密文的加操作等同于明文的乘操作，这里选取的是Paillier同态加密。如图1所示,SIFT特征，对此时SIFT特征使用B-SIFT同样的量化方法进行压缩处理，最终为了保证原始SIFT以及B-PPSIFT相比有同样的匹配效果。

图1 B-PPSIFT的计算过程

计算过程如图2所示。对给定图像I,直接提取SIFT特征记为F(I)，对其进行量化得到B-SIFT，记为F′(I)。图像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等人已经证明在图像经同态加密后提取差分高斯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范数，由于在有限维线性空间的所有范数都具有等价性，则有

(10)

由等价性的传递原则，在这里对原始图像SIFT特征点的距离度量方法选用欧氏距离，对F′(Ie)采取汉明距离。综上可以证明④，即在原始图像使用欧氏距离与B-PPSIFT中计算汉明距离是等价的，如式(11)所示

(11)

图像检索场景适用于用户上传图像的B-PPSIFT，此时服务器就无法得知用户想要查询的图像。而在服务器端存储的是加密的图像以及对应的B-PPSIFT，这时在图像搜索阶段，是通过密文的二进制进行匹配。保证安全性的同时，也保护了图像的隐私。

3 实验与分析

3.1 稳健性实验

实验采用 StirMark 4.0基准测试程序[15]来验证程序针对恶意攻击的稳健性，实验采用5种不同内容的彩色图像如图3所示，从左到右依次为，I1：Lena；I2：pens；I3：baboon；I4：pepper；I5：flower，每类图像都进行12种不同类型的攻击，变换实验过程类似于复制图像检测。

图3 5种不同的彩色图像

在实验过程中，将加密图像的B-PPSIFT二进制串作为查询图像，在实验数据库中进行匹配，通过对比B-PPSIFT，衡量能正确检测到图像数量。结果如表1所示，每种攻击对应的数字表示不同参数下攻击产生的版本。通过本文作者的实验结果可以知道，总共480幅图像中，对每一类原始图像有96个攻击图像，其中能正确检测到图像为427, 表明识别的正确率为88.95 %，而在检测失败的情况中包括加噪、裁剪，在原始SIFT中也同样检测失败。实验结果显示这种方法保证了同样有效的稳定性并保证了图像隐私。

表1 StirMark4下的稳健性测试

3.2 图像检索实例

为了证明本文作者提出B-PPSIFT方法在图像识别上的准确性，采用数据库Caltech 256[16]包含多种对象类别，并在形状上具有高度可变性，随机选择了10种常用类别的图像作为实验数据，每类图像包含60张图像，其中30张作为查询图像，其他的则一起存储数据库中作为被查询图像。这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，进行匹配，之后根据匹配的特征点数进行排序，找出最接近的一幅或多幅图像，实验结果用最接近的k幅图像来表示。这里设置k=1,2,3,5，10时，识别效果与原始SIFT接近，结果如表2所示。第一列表示10种不同的类型的图像，Ⅰ表示原始SIFT特征，Ⅱ表示B-PPSIFT。表格中数字表示对应top-k正确识别的个数，比如top-3中C3对应的两行，第一行表示原始SIFT在k=5时，正确搜索到的图像为21；采用B-PPSIFT时，正确识别的图像为26。

由实验结果可以看出，B-PPSIFT的识别率与原始SIFT的识别率基本相当。需要指出，实验结果显示的识别率不是太好，是因为实验仅仅采用了特征点的匹配，没有采用分类器的设计方法。如果继续用先进的特征表示和设计良好的分类方法，效果会得到进一步改善。实验表明，B-PPSIFT与原始SIFT有几乎相当的查询效果。

表2 SIFT和B-PPSIFT的识别结果对比

由表3可知，第三行表示当特征点数为5×106时，B-PPSIFT的检索时间为200 ms, 而SIFT的检索时间为20 000 ms。大大减少了搜索时间，提高了匹配效率。

表3 存储空间和匹配速度结果对比

4 结束语

本文提出了一种结合同态加密和SIFT特征提取以及 SIFT量化的一种图像隐私保护搜索方法，理论验证了这种方法在距离度量时具有的等价一致性，证明其结合的可行性，并用实验说明能达到鲁棒性和准确性较好的效果。在图像检索中适用于对隐私保护有需求的用户，比如在多媒体检索中保护用户隐私，当用户将加密数据作为查询内容发送至服务器端，服务器则可以在接收到加密的数据时，无需解密完成查询匹配过程，最终将对应的加密数据返回给用户。整个过程中，服务器端以及在传输过程中都是加密的图像，保护了数据隐私同时高效完成了查询任务。在未来图像安全会越来越成为大家的主要考虑因素。

下一步将针对搜索的算法进行研究，加密图像SIFT量化后是否还可以继续进行降维压缩，或者在搜索索引的建立上进一步提高方法的有效性。

[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-)，女，硕士，主要研究方向为图像隐私保护。