一种加密域SURF图像特征提取方法

摘要

本发明涉及一种加密域的SURF特征提取方法，包括：构建Paillier加密系统和DGK加密系统，生成相应的公匙与私匙；用户端利用Paillier加密系统，以生成的公匙对图像进行加密，然后将加密后的图像发送给服务器端；服务器端对加密后的图像提取SURF特征点；服务器端对提取的SURF特征点进行校正；服务器端提取SURF特征描述子。本发明利用Pallier同态加密方法的同态特性，提出一种加密域的SURF特征提取方法。该方法无需解密即可对加密后的图像直接提取SURF特征，避免了图像信息的泄漏；而且取出的SURF特征点数和位置与明文域算法完全一致，描述子与明文域的误差也仅为0.0002932%。

说明书

技术领域

本发明涉及一种加密域的SURF（Speeded Up Robust Features，加速健壮特征）特征提取方法，属于多媒体信息安全处理领域。 

背景技术

近年来，随着云计算和物联网等应用对安全需求的不断增加，人们开始研究在加密域内进行信号处理的可能性，即对加密后的信号直接进行处理，可以在保证用户信息安全的同时又不牺牲信号处理的功能。近年来，随着云计算应用的不断推广，加密域信号处理已经成为信号处理领域的一个研究热点。 

SURF特征是一种局部特征提取算法。该算法提取的特征具有尺度不变、旋转不变的性能，对光照变化、仿射变化、透视变换具有部分不变性。而且SURF算法在重复度、区分性、鲁棒性三个方面均超越或接近于以往提出的算法。相比于SIFT（Scale Invariant Feature Transform，尺度不变特征变换）算法，其特征提取速度具有明显优势，也因此常被人们看作是SIFT的快速算法，目前已被广泛应用于图像检索、图像配准、人脸识别等各种应用中。 

同态加密允许人们对加密后的数据进行特定的代数运算，其得到的处理结果与对明文进行同样的运算再将结果加密一样。Paillier加密算法不仅具有加法同态特性，还可以实现数乘运算，是目前最常用的同态加密算法。相比于RSA加密算法，Paillier加密算法具有更高的运算效率。 

申请号为200680019169.5的专利公开了一种用于在媒体信号中嵌入水印的方法和系统。当接收媒体信号的设备不被信任时，该方法和系统可以在媒体信号中嵌入水印，作为媒体信号的身份验证，但是随着媒体信号的近拷贝版本的变化，认证精度无法保证。不如直接检验媒体信号的内容，把媒体信号的内容当做其唯一身份验证信息。 

发明内容

本发明基于Pallier同态加密算法，提出了一种加密域的SURF特征提取方法，该方法无需解密，可针对加密后的图像直接提取图像的SURF特征，避免了图像信息的泄漏。 

一种加密域的SURF特征提取方法，包括以下步骤： 

步骤1：构建Paillier加密系统和DGK加密系统，生成相应的公匙与私匙，用于图像的加密和解密。 

步骤2：用户端利用Paillier加密系统，以步骤1生成的公匙对图像进行加密，然后将加 密后的图像发送给服务器端。 

步骤3：服务器端对加密后的图像提取SURF特征点。 

步骤3.1：计算图像每个点的海森矩阵。 

步骤3.2：计算每个海森矩阵对应的行列式值。 

（1）将图像的像素值放大到100倍。 

（2）计算每个海森矩阵对应的行列式值。 

利用方格滤波器与图像的卷积来代替高斯二阶导数与图像的卷积近似计算海森矩阵对应的行列式值。假设x、y和xy方向的滤波器与图像的卷积结果分别为D_xx、D_yy和D_xy，海森矩阵H_approx的行列式值的计算公式为： 

det[H_approx]＝D_xxD_yy-(0.9D_xy)²      (1) 

步骤3.3：在所有行列式值中寻找局部极值，该局部极值对应的点即为特征点。 

步骤4：服务器端对提取的SURF特征点进行校正，即曲线拟合。 

设特征点坐标为X＝(σ,y,x)^T，校正后特征点的坐标X′＝(σ′,y′,x′)^T，则： 

${\sigma }^{\prime }=\frac{\left|A_1\right|}{\left|A\right|},y^{\prime }=\frac{\left|A_2\right|}{\left|A\right|},x^{\prime }=\frac{\left|A_3\right|}{\left|A\right|}---\left(2\right)$

其中， 

$A_1=\left(\begin{array}{c}\frac{\partial F}{\partial \sigma }\frac{{\partial }^{2}F}{\partial \mathrm{\sigma y}}\frac{{\partial }^{2}F}{\partial \mathrm{\sigma x}}\\ \frac{\partial F}{\partial y}\frac{{\partial }^{2}F}{\partial y^2}\frac{{\partial }^{2}F}{\partial \mathrm{yx}}\\ \frac{\partial F}{\partial x}\frac{{\partial }^{2}F}{\partial \mathrm{yx}}\frac{{\partial }^{2}F}{\partial x^2}\end{array}\right),A_2=\left(\begin{array}{c}\frac{{\partial }^{2}F}{\partial {\sigma }^2}\frac{\partial F}{\partial \sigma }\frac{{\partial }^{2}F}{\partial \mathrm{\sigma x}}\\ \frac{{\sigma }^{2}F}{\partial \mathrm{\sigma y}}\frac{\partial F}{\partial y}\frac{{\partial }^{2}F}{\partial \mathrm{yx}}\\ \frac{{\partial }^{2}F}{\partial \mathrm{\sigma x}}\frac{\partial F}{\partial x}\frac{{\partial }^{2}F}{\partial x^2}\end{array}\right),A_3=\left(\begin{array}{c}\frac{{\partial }^{2}F}{\partial {\sigma }^2}\frac{{\partial }^{2}F}{\partial \mathrm{\sigma y}}\frac{\partial F}{\partial \sigma }\\ \frac{{\partial }^{2}F}{\partial \mathrm{\sigma y}}\frac{{\partial }^{2}F}{\partial y^2}\frac{\partial F}{\partial y}\\ \frac{{\partial }^{2}F}{\partial \mathrm{\sigma x}}\frac{{\partial }^{2}F}{\partial \mathrm{yx}}\frac{\partial F}{\partial x}\end{array}\right),A=\left(\begin{array}{c}\frac{{\partial }^{2}F}{\partial {\sigma }^2}\frac{{\partial }^{2}F}{\partial \mathrm{\sigma y}}\frac{{\partial }^{2}F}{\partial \mathrm{\sigma x}}\\ \frac{{\partial }^{2}F}{\partial \mathrm{\sigma y}}\frac{{\partial }^{2}F}{\partial y^2}\frac{{\partial }^{2}F}{\partial \mathrm{yx}}\\ \frac{{\partial }^{2}F}{\partial \mathrm{\sigma x}}\frac{{\partial }^{2}F}{\partial \mathrm{yx}}\frac{{\partial }^{2}F}{\partial x^2}\end{array}\right)$

式中，σ为该点所在的尺度，y为该点的纵坐标，x为该点的横坐标，F表示该点对应的海森矩阵的行列式值。 

步骤5：服务器端提取SURF特征描述子。 

步骤5.1：以特征点为圆心，计算半径为6σ圆内x和y方向上的Haar小波响应系数HaarX和HaarY，公式如下： 

HaarX＝(E(x+σ,y+σ)+E(x,y-σ)-E(x,y+σ)-E(x+σ,y-σ))- 

                                   (3) 

(E(x,y+σ)+E(x-σ,y-σ)-E(x-σ,y+σ)-E(x,y-σ)) 

HaarY＝(E(x-σ,y)+E(x+σ,y+σ)-E(x+σ,y)-E(x-σ,y+σ))- 

                               (4) 

(E(x+σ,y)+E(x-σ,y-σ)-E(x-σ,y)-E(x+σ,y-σ)) 

式中，E(x,y)为积分图像中点(x,y)处的加密值。 

步骤5.2：根据Haar小波响应系数计算主方向。 

（1）旋转顶点在圆心、夹角为60°的扇形区域，旋转扇形区域的步长为0.15弧度，将整个区域分成42个部分。 

（2）判断点（HaarX,HaarY）所属的扇形区域。 

假设点（HaarX,HaarY）与原点的连线和横轴的夹角为β，某个扇形区域的两条边与横轴的夹角分别为α,α+60°。如果α＜β＜α+60°，则点（HaarX,HaarY）属于该扇形区域；否则，继续判断该点与该扇形区域相邻的扇形区域的关系，直到找出该点所属的扇形区域。 

在加密域比较角度β与α大小的方法如下： 

当与X_α异号时，如果则β＞α，反之亦然。 

当与X_α同号时，如果$\frac{\mathrm{\Sigma HaarY}}{\mathrm{\Sigma HaarX}}>\frac{Y\_\alpha }{X\_\alpha },$则β＞α，如果$\frac{\mathrm{\Sigma HaarY}}{\mathrm{\Sigma HaarX}}<\frac{Y\_\alpha }{X\_\alpha },$则β＜α。 

（3）求扇形区域内的最大值，最大值对应的方向即为特征点的主方向。 

步骤5.3：将Haar响应旋转到主方向，即计算Haar响应值在主方向上的投影； 

（1）计算E(sinθ)与E(cosθ)，θ为主方向的角度。 

以代替sinθ值。若主方向为$(E\left(\mathrm{\Sigma HaarX}\right),E\left(\mathrm{\Sigma HaarY}\right)),$则： 

（2）计算d_x和d_y在主方向上的投影d′_x和d′_y，具体公式如下： 

$\left(\begin{array}{c}{d}_x^{\prime }=-d_x\times \sin \theta +d_y\times \cos \theta \\ d_y^{\prime }=d_x\times \cos \theta +d_y\times \sin \theta \end{array}\right)---\left(6\right)$

式中，θ为主方向的角度。 

步骤5.4：计算每个子窗口与的值，并生成描述子。 

所述公式（1）进行加密域乘法的实现方法如下： 

若已知加密值c₁和c₂，其中c₁＝E(m₁)，c₂＝E(m₂)，c_i＝E(m_i)代表明文m_i加密后的值为c_i，i=1,2，则加密域的乘法运算就是计算加密值c₃，使得D(c₃)＝m₁×m₂；E代表加密过程，D代表解密过程。 

（1）服务器端生成随机数r₁和r₂并加密，得到c₄＝E(r₁)、c₅＝E(r₂)和c₆＝E(-r₁r₂)。 

（2）计算c₄×c₁modN²，c₅×c₂modN，并将结果发送给用户端；N为加密系统的参数。 

（3）用户端将步骤（2）中的两个结果解密后，进行两个解密值的乘法运算，然后将相乘结果c₇加密后发送回服务器端。 

（4）服务器端计算$c_3=c_7\times {c_1}^{-r_1}\times {c_2}^{-r_2}\times c_6\mathrm{mod}{N}^2$，其中D(c₃)＝m₁×m₂。 

所述公式（2）在加密域实现除法运算的方法如下： 

假设加密值c₁和c₂，其中c₁＝E(m₁)，c₂＝E(m₂)，加密域除法计算就是得到加密值c₃，使得$D\left(c_3\right)=s\times \frac{m_1}{m_2},$s＝10⁷。 

（1）服务器端生成随机数r，然后对r加密，得到c₅＝E(r)。 

（2）计算c₅×c₂＝E(m₂+r)＝c₆。 

（3）服务器将c₆发送给用户端，由于用户端不知道随机数r的大小，所以无法通过解密c₆来获取m₂的值；用户端解密c₆，D(c₆)＝m₃；然后计算并加密得到

（4）用户端将c₄的值返回给服务器端。 

所述公式（5）在加密域实现开方运算的方法如下： 

若已知c₁＝E(m)，加密域开方运算是为了获得c₂，使得其中s＝10¹²。具体的实现步骤如下： 

（1）服务器端生成随机数r，然后对r²加密，得到c₃＝E(r²)。 

（2）计算$c_3\times {\left(c_1\right)}^{r^2}=E(m\times r^2+r^2)=c_4.$

（3）服务器将c₄发送给用户端，由于用户端不知道随机数r的大小，所以无法通过解密c₄来获取m的值；这时，需要用户端对c₄解密，得到D(c₄)＝m₂；然后计算并加密得到$D\left(\frac{s}{\sqrt{m_2}}\right)=c_5.$

（4）用户端将c₅的值发送给服务器端。 

（5）服务器计算r²的乘法逆元，其值为m₃，然后计算$c_2={\left(c_5\right)}^{m_3}=E(s\times \sqrt{m+1}),$则 $D\left(c_2\right)=s\times \sqrt{m+1}\approx s\times \sqrt{m}.$

与现有技术相比，本发明具有以下优点： 

本发明利用Pallier同态加密方法的同态特性，提出了一种加密域的SURF特征提取方法。 该方法无需解密，可针对加密后的图像直接提取图像的SURF特征，避免了图像信息的泄漏；而且取出的SURF特征点数量和位置与明文域算法提取的完全一致，描述子与明文域的误差也仅为0.0002932%。本发明为各种加密域图像处理应用提供了一种有用的工具。 

附图说明：

图1为本发明提出的加密域SURF特征提取方法流程图； 

图2为本发明提出的角度比较方法示意图； 

图3为SURF特征描述子示意图； 

图4为加密域SURF和明文域SURF特征点个数及位置的对比图。 

具体实施方式

本发明的流程图如图1所示，具体包括以下步骤： 

步骤1：构建Paillier加密系统和DGK加密系统，生成相应的公匙与私匙，用于图像的加密和解密。 

步骤2：用户端利用Paillier加密系统，以步骤1生成的公匙对图像进行加密，然后将加密后的图像发送给服务器端。 

步骤3：服务器端对加密后的图像提取SURF特征点，具体步骤包括： 

步骤3.1：对图像的像素值进行100倍的放大。 

步骤3.2：计算每个海森矩阵对应的行列式值。 

步骤3.3：在所有行列式值中寻找局部极值作为特征点。 

步骤4：服务器端对提取的SURF特征点进行校正，利用加密域乘法和加密域除法计算公式(2)，获得特征点校正后的值。 

步骤5：服务器端提取SURF特征描述子。SURF特征描述子示意图如图3所示。 

步骤5.1：以特征点为圆心，计算半径为6σ圆内x和y方向上的Haar小波响应系数。 

步骤5.2：根据Haar小波响应系数，计算主方向。 

步骤5.3：将Haar响应旋转到主方向，即计算Haar响应值在主方向上的投影。 

步骤5.4：计算与的值来生成描述子。 

图4为加密域SURF特征与明文域SURF特征对比图。左边第一列为原始图像，第二列为明文域SURF特征提取结果，第三列为加密域SURF特征提取结果，其中方块代表特征点的位置。图4表明加密域SURF的特征点数量和位置与明文域完全一致。 

表1是加密域与明文域提取出的SURF特征描述子的对比。从表1中可以看出，加密域描述子大小约是明文域的10²¹倍，10²¹是计算加密域除法和加密域开方运算时乘上的系数。如果将加密域描述子检测结果除以10²¹，可求得加密域和明文域检测结果的平均误差为 0.0002932%。这个误差来源于加密域近似开方运算和高斯加权值的近似。这一误差对后续的检索、匹配等应用不会造成太多的影响，是可以接受的。 

表1加密域与明文域描述子对比 

向量 明文域 加密域 第4维向量 0.0254506 25447978340820304956 第14维向量 -0.144928 144913278128088816342 第26维向量 -15.9526 -15952583853243776628096 第32维向量 1.03341 1033403209007703418500 第54维向量 -0.00993253 -993051543396542800 64维向量总和 -66.1773 -66177105905710516176452 平均差值百分比   0.0002932%