基于哈希的图像检索

一、图像检索中哈希算法的使用过程：

在我们的成绩管理系统中了解了某位同学的姓名以及其在数学和语文科目的具体得分情况之后通过数据分析系统来查找这个记录从而识别出该学生每一次的数据匹配都需要对姓名以及这两门功课的成绩进行详细比对由于这些数据量较为有限因此采用线性匹配方式就能有效解决问题

在小型图片数据库中, 为每张图片增添标签, 比如给一张风景照片标注山、水、湖泊和房屋等标签, 当我们要搜索与房屋相关的图片时, 可以通过搜索‘房屋’关键字来让数据库匹配并获取用户所需的照片。

3.但在当今大数据时代背景下,每天所产生的海量图片数据呈现出指数级增长态势,而针对这种高维空间的数据,单纯依靠传统检索方法往往难以达到理想的效果。在此类大规模数据处理中,近似近邻搜索算法作为一种有效的解决方案,能够在保证检索效率的同时实现较高程度的检索精度。其核心理念在于将复杂的数据对象转化为相对简洁的二进制表示形式（如64位或128位二进制编码）,这种表示方式既能够有效保留原始数据的空间特征信息,又能在一定程度上降低数据存储和计算的需求。当用户上传新的图片时,系统会通过哈希函数将该图片转换为相应的二进制编码表示形式,随后通过计算该编码与数据库中所有记录对应编码之间的汉明距离（即进行异或运算后统计差异位的数量）来确定相似度。最终会将具有最小汉明距离的前100条记录作为候选结果返回给用户,并通过预先建立的数据索引快速定位出原始图片的具体信息进行展示

4.主要过程：

在基于哈希的方法中进行图像检索时

二、DSH哈希算法

密度 sensitive hashing 可以被看作是 local sensitive hashing 的一种扩展形式，在处理过程中它是通过使用超平面将整个数据集划分为若干个区域并生成相应的 hash 码。其主要区别在于它通过对数据分析分布进行深入研究并采取最优策略来进行区域划分，在保证高效查询的同时最大限度地保留了原始数据间的相似度信息。

1.基于超平面的哈希算法对比，第三张图为密度敏感哈希

2.使用k-means方法划分聚类

将原始数据划分为K个簇，并作为属于十大经典的数据挖掘算法之一使用。其核心思路在于随机选取k个中心点，并通过迭代优化这些中心点位置直至收敛至最小化误差的目标状态。具体而言，在每一次迭代中我们都会将所有样本分配至这k个簇中并不断调整各簇中心以降低整体误差水平。

聚类步骤：

（1）适当选择k个类的初始中心；

（2）对于任意一个样本x，在计算其至k个中心点的距离后，将其归入离它最近的那个中心所属的类别中。

（3）求出每个类心的平均值，即每个类心向量之和再除以每个类心点的个数；

（4）找到这个类心里与该平均值最近的点作为新的类心

所有c个聚类中心中，在应用（2）、（3）、（4）所描述的迭代方法进行更新后计算得到的值不再变化，则算法终止；否则将转而进行下一次迭代。

该算法的核心优势体现在高效性和迅速性上。从核心角度来看，该算法的关键在于确定初始中心的位置以及采用合适的计算距离的标准。

首先从n个数据对象中任意选取k个作为初始聚类中心,要求这些初始质心尽量分散;剩余的对象则依据其与各质心之间的相似度(用距离衡量)进行分配,即将其归入与其最接近质心所属类别.随后重新计算每个新形成的类别中的均值;反复执行上述步骤直至某个标准指标开始收敛.通常采用均方差作为收敛的标准.这些划分出的k个类别具有以下特点:各个类别内部应尽可能紧密地聚集在一起;而不同类别之间则应尽量保持分离.

3.近邻组对的形成

令近邻集合大小设定为r。首先计算该类别与其他所有k−1个类别之间的距离。随后将这些类别按照距离进行排序。接着选取与之最近的r个类别作为其近邻集合。最后遍历所有类别并确定每个类别对应的最优近邻集合。最终得到一个维度大小为(k×r)的距离矩阵。

中垂面的定义如下：

哈希函数定义如下：

其中：

每个近邻组对会生成一个超平面的所有这些超平面总数是k \times r。当k设置为64时（即进行64聚类），r设为3，则总共会产生192个超平面。选择将这些哈希编码转换为64位时，则只需从这192个候选选项中选出最优的k=64作为最终构建哈希函数的基础。
因此，在这192个候选选项中，我们需要选出其中最优的k=64作为最终构建哈希函数的基础。

4.基于熵值的超平面的选择

在信息论中, 熵是接收每个事件所携带的信息数量的平均值, 通常被称为信息熵或信源熵. 每个事件在这里用来表示来自分布或数据流中的样本或特征. 在信息领域, 熵越高则系统的不确定性越大, 能够处理的信息也就越多; 相反地, 熵越低则系统的不确定性就越小, 能够处理的信息就越有限. 信息: 信息量可以用'出乎意料的程度'来衡量. 如果有人告诉我们一个罕见事件发生了, 我们会收到比得知一个常见事件发生的更多'惊讶程度'; 如果我们被告知某个必然会发生的事情发生了, 那么我们就不会感受到任何'惊讶程度', 因为这本来就是肯定会发生的事情.

熵值公式表示为：

在熵值最大化理论的指导下，通过计算各超平面对应的条件熵值并最终选取条件熵最大的那一个超平面作为构建哈希函数的基础。具体而言，在这一过程中需要完成两个主要步骤：首先计算各维特征之间的互信息量；其次将这些互信息量按照从大到小进行排序，并选择互信息量最高的那几个特征组合起来形成决策边界线。

Wi熵值的计算：

其中符号S_i代表第i个聚类中元素的数量，并且C_{i,0}代表平面W_i左侧的聚类中心而C_{i,1}则代表右侧的聚类中心。

找到L个熵值最大超平面形成哈希编码。