综述 | 明白 | 知识分享

技术背景

公共云存储服务兴起，为保护云端数据的安全，多媒体数据在上传之前会进行加密处理。
诸多的云存储应用服务带来了密文数据的管理和检索难题。
早期的加密域图像检索方案研究（类似基于逐词加密和精确匹配的加密域文本检索方案）通过添加图像标识将其转化为加密域文本检索。
真正意义上的加密域图像检索技术是支持特征保护的图像检索方案。

方案实体

图像所有者

提取待上传图像的特征向量，建立安全索引（提高检索效率），并将特征加密；
将密文特征和安全索引上传到云服务器；
向合法用户授权查询并发放图像的解密密钥。

云服务器

存储密文图像特征和安全索引；
处理来自图像查询者的检索请求，按照访问策略检索；
对受保护的多媒体数据进行搜索和计算。

图像查询者

获得图像所有者的授权；
提取查询图像的特征并加密；
将密文特征作为查询陷门提交给服务器；
接收到查询结果后，使用图像所有者共享的密钥对其解密。

关键技术

安全策略

图像上传到云服务器上之前常采用以下两种处理方式：

先提取图像特征再加密（FETC）——可采用传统的RSA或AES等标准加密算法

先加密再提取图像特征（FCTE）——服务器再密图上建立安全索引，需要特殊的加密操作，如同态加密、保序加密。

加密技术

同态加密

同态加密（Homomorphic Encryption）允许在加密状态下对数据进行计算，而无需解密即可得到计算结果。这使得数据隐私得到了保护，同时仍然可以进行有限的计算和分析。

如果一种同态加密算法支持对密文进行任意形式的计算，则称其为全同态加密（Fully Homomorphic Encryption, FHE）；如果支持对密文进行部分形式的计算，例如仅支持加法、仅支持乘法或支持有限次加法和乘法，则称其为半同态加密（Somewhat Homomorphic Encryption, SWHE）或部分同态加密（Partially Homomorphic Encryption, PHE）。一般而言，由于任意计算均可通过加法和乘法构造，若加密算法同时满足加法同态性和乘法同态性，则可称其满足全同态性。

保序加密

保序加密（Order-Preserving Encryption，简称OPE）在对数据进行加密的同时保持数据的顺序关系。换句话说，如果对明文数据进行了保序加密，那么对应的密文数据之间的大小关系仍然与明文数据之间的大小关系相同。这使得在加密数据的同时，仍然可以进行一些基于排序和比较的操作，如范围查询和排序，而无需解密数据。

置乱加密

图像特征提取技术

明文域的特征提取：用户在本地独立从原始图像上提取特征。过程简单，隐私性高，但是终端用户的资源有限，难以应对较大的计算量。
密文域的特征提取：用户将用于计算特征的数据进行加密，然后再外包给云服务器以完成特征的提取，从而避免泄露图像或特征的内容。

全局图像特征提取

从整体上描述一幅图像，包括颜色直方图、形状特征、纹理特征等信息。

局部图像特征提取

用带权重的局部特征向量集合表示一幅图像，常用的局部图像特征提取算法有尺度不变特征变换（SIFT，scale-invariant feature transform)、局部聚合向量(VLAD，vector of locally aggregated descriptors)、局部二值模式（LBP，local binary patterns）等。

安全索引技术

基于视觉单词的安全索引

基于视觉单词的安全索引是一种用于保护敏感数据的隐私保护技术，通常应用于图像、视频或其他多媒体数据。它的目标是在不暴露原始数据的情况下，允许用户对数据进行搜索和查询操作。

特征提取和编码： 首先，原始的图像或多媒体数据会被转换成一组特征向量，这些特征向量可以代表图像中的关键视觉信息。这些特征可能涉及图像的颜色、纹理、形状等方面。然后，这些特征向量会被进一步编码成视觉单词。
构建视觉词典： 为了实现索引和查询，系统会构建一个视觉词典，其中包含了大量的视觉单词。这些视觉单词是从训练数据中提取出来的，类似于一种视觉单词的“词汇表”。
安全索引构建： 在构建安全索引时，系统会将视觉单词与原始数据的特征向量关联起来，并应用隐私保护技术。一种常见的方法是使用陷门函数（Trapdoor Function）来对视觉单词进行加密，生成一个安全索引。陷门函数允许用户在不知道原始数据的情况下，生成一个能够与安全索引匹配的陷门。这使得用户可以在加密的情况下进行查询。
查询操作： 当用户想要查询数据时，他们会生成一个查询陷门，然后使用这个陷门对视觉单词进行加密。然后，加密后的查询陷门与安全索引进行匹配，找到相应的视觉单词。
解密和获取结果： 一旦找到匹配的视觉单词，用户可以使用解密密钥对其进行解密，获得原始数据的特征向量。然后，用户可以对这些特征向量进行分析、处理或其他操作。

基于局部敏感哈希的安全索引

基于局部敏感哈希（Locality-Sensitive Hashing，LSH）的安全索引是一种隐私保护技术，用于在保护数据隐私的同时，允许用户对数据进行相似性搜索和查询。LSH 是一种哈希技术，可以将相似的数据映射到相近的哈希桶中，从而实现相似性搜索。

数据哈希：首先，原始数据会被转换成特征向量，然后使用局部敏感哈希函数对这些特征向量进行哈希操作。局部敏感哈希函数的特点是，相似的数据在哈希空间中有较大的概率被映射到相近的哈希桶中，从而实现相似性的保持。
构建哈希索引：使用哈希函数生成的哈希值，构建一个哈希索引结构。这个索引结构允许根据哈希值来查找相似的数据项。
安全索引构建：在构建安全索引时，会引入隐私保护机制，例如差分隐私或同态加密。这些机制可以在保护数据的同时，允许在哈希索引上执行查询操作。
查询操作：当用户想要查询相似数据时，他们会提供一个查询特征向量。然后，查询特征向量会被使用局部敏感哈希函数映射到哈希空间中的一个或多个哈希桶中。
相似性搜索：根据查询特征向量映射到的哈希桶，可以找到与查询特征向量相似的数据项。由于局部敏感哈希的性质，这些数据项很可能是与查询相似的数据。
解密和获取结果：找到相似的数据项后，用户可以使用解密密钥对这些数据项进行解密，获得原始数据的特征向量。然后，用户可以对这些特征向量进行分析、处理或其他操作。

相似性度量

汉明距离

汉明距离（Hamming Distance）是用于比较两个等长字符串之间的差异度量，通常用于比较二进制编码。在给定向量空间，两个向量 $X=x_1,x_2,\cdots,x_i$ 和 $Y=y_1,y_2,\cdots,y_i$ 的汉明距离是表示向量 $X$ 和 $Y$ 之间相同位置字符不同的个数，若字符不同则距离加 1，否则不变。因此，汉明距离越小，图像差异越小，否则图像有明显差异。

欧式距离

欧式距离（Euclidean Distance）表示两个向量之间的几何距离，即直线距离。

三维空间：

$D=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2}$

$n$维空间：

$D=\sqrt{\sum_{i=1}^n (x_i-y_i)^2}$

$x_i$ 表示第一个点在第 $i$ 维坐标数据，$y_i$ 表示第二个点在第 $i$ 维坐标数据，其中 $i=1,2,3,\cdots,n$。图像检索中我们可以把图像看作一个 $n$ 维的图像特征向量，通过计算两个图像特征向量的欧式距离 $D$，得到图像之间的相似度距离，如果欧式距离 $D$ 越小表示图像差异越小，反之图像差异较大。

余弦距离

余弦距离（Cosine Distance）是用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小的度量。向量 $X=x_1, x_2, …, x_i$ 和 $Y=y_1, y_2, …, y_i$ 之间的余弦距离 $D$ 可以用它们之间夹角的余弦值来表示：

$D=\dfrac{x_1y_1+x_2y_2+\cdots+x_iy_i}{\sqrt{x_1^2+x_2^2+\cdots+x_i^2} \cdot {\sqrt{y_1^2+y_2^2+\cdots+y_i^2}}}$

余弦距离范围在[-1, 1]之间，值越接近1表示夹角越接近，表示相似性越高。

哈曼顿距离

曼哈顿距离也称为城市街区距离，用于计算两个向量之间的标准距离，而不是直线距离。对于具有 $n$ 个维度的向量 $X=x_1, x_2, …, x_i$ 和 $Y=y_1, y_2, …, y_i$ ，曼哈顿距离可以通过以下公式计算：

$D=\sum_{i=1}^n \mid x_i-y_i \mid$

性能评价

召回率R 精确率P

在图像检索中，召回率（Recall）和精确率（Precision）是用来评估检索系统性能的重要指标。一般而言，这两个评价指标是相互影响制衡的，在理想的情况下两者是都高的，但是通常情况下其中一个高另一个就低。

TP（True Positives）：系统正确检索到的相关图像数量。
FP（False Positives）：系统错误将非相关图像检索为相关图像的数量。
FN（False Negatives）：系统未能检索到的相关图像数量。

$R = \dfrac {TP}{TP + FN}$

召回率R的范围在0到1之间，越接近1表示算法检索到的相关图像越多，说明算法能够较好地覆盖相关图像的范围，召回率越高，算法的检索能力越强。

$P = \dfrac {TP}{TP + FP}$

准确率P的范围在0到1之间，越接近1表示检索到的图像中有更多是真正相关的图像，说明算法的检索结果更可信，准确率越高，算法的精确性越好。

F分数

F分数（F-score），也称为F1分数，是一种综合评估分类模型性能的指标，它结合了精确率P和召回率R两个指标，用于在不平衡数据集或需要平衡召回率和精确率时进行评估。

$F=2 \dfrac {PR}{P+R}$

为了适应更多应用领域，允许P和R权重不同，以下给出F分数的一般式:

$F=(1+a^2) \dfrac {PR}{a^2 P+R}$

式中，$a$ 表示P与R间的权重比。