一种基于有监督超图离散化图像二值编码方法转让专利
申请号 : CN201810402753.3
文献号 : CN109284411B
文献日 : 2022-03-18
发明人 : 王轩 , 张喜 , 漆舒汉 , 蒋琳 , 廖清 , 姚霖 , 李晔 , 关键 , 刘泽超 , 吴宇琳
申请人 : 哈尔滨工业大学深圳研究生院
摘要 :
权利要求 :
1.一种基于有监督超图离散化图像二值编码方法,其特征在于,包括以下步骤:S1.假设一个由n幅图像组成训练集,将训练集所有样本通过学习哈希函数映射到汉明空间的二值化哈希码;
S2.定义一个线性多分类模型,采用优化函数对离散化变量进行优化,得出第一目标函数;
S3.采用超图对数据哈希码之间的距离度量一致性进行约束,得出第二目标函数;
S4.整合第一目标函数和第二目标函数,得到完整的目标函数,采用“位循环坐标下降方法”学习哈希码矩阵,并通过迭代运算优化目标函数;
所述步骤S1具体包括:
1×d
假设训练集{(xi∈R ),i=1,2,...,n}由n幅图像组成,其中xi表示第i幅图像的d维特d×n 1×r
征向量,用X=[x1,...,xn]∈R 表示训练集,{(bi∈{‑1,+1} ),i=1,2,...,n}是训练集所有样本通过学习哈希函数映射到汉明空间的二值化哈希码,每个样本的哈希码长度为r,r取值范围为数十位到数百位之间,哈希码码位取值为‑1或者+1,用B=[b1,...,bn]∈{‑1,+r×n
1} 表示训练集对应的哈希编码结果;
学习得到一系列哈希函数:
H(x)={h1(x),…,hC(x)} (2‑1)将哈希函数值进行量化成二值化的哈希码,过程如下:bi=sgn(H(xi)),i=1,...,n (2‑2)sgn(·)是符号函数;
哈希函数采用如下非线性形式:T
H(x)=PΦ(x) (2‑3)d×r
其中P=[p1,p2,…,pr]∈R 是哈希函数的线性变换矩阵,Φ(x)是关于原始图像的非线性映射函数:
2 2 2 T
Φ(x)=[exp(||x‑a1||/σ),exp(||x‑a2||/σ),...,exp(||x‑am||/σ)],是一组从训练集中随机选取的锚点,σ是一个常数;
所述步骤S2具体包括:
现定义一个线性多分类模型如下所示:T T T T
y=F(b)=Wb=[w1b,....,wrb] (2‑4)r×1 r
其中{wk∈R ,k=1,...,C}是数据样本所属类别k的参数向量,总共有C个类别,y∈R×1 T
是各个类别的激活值,与标签对应;根据Wb的最大值yk对应的类标,将样本数据点x分类到第k个类别;采用下面的优化函数:上式中 是分类损失函数,表示训练集的分类误差,度量学习到哈希码的C×n
分类质量;λ是正则化参数,Y=[y1,...,yn]∈R 是训练集的真实标签矩阵,满足下面的约束条件;||·||是L2范数;α是哈希函数H(xi)拟合哈希码bi错误率的惩罚参数;理论上,bi与H(xi)之间距离尽量小,所以参数α的值尽量大;
用矩阵表示进行化简:
所述步骤S3包括:
S31.超图构建:
构建超图表示为G=(V,E,W),V表示顶点集合,E表示超边集合,W表示超边对应的权重集合,其中,训练集中的每一个数据点可以表示为一个顶点,而每个顶点与他的k‑近邻的数据点表示为一条超边;
所述步骤S31具体为:
超图G用|V|×|E|规模的关联矩阵,|·|表示求基数操作,G中的顶点vi与超边ej的关联度可以表示为:
其中dist(xi,xj)表示顶点vi与vj之间的距离,dist(xi,xj)=||xi‑xj||2,kdist(vj)表示顶点vj与他的k‑近邻顶点集合;对于每条超边的度δ(ej)被定义为相似度一致性通过超边包含的顶点之间的特征的相似度来计算:其中,a和b表示任意两个顶点,σej是规范化因子,采用该超边所包含的顶点之间距离的平均值作为规范化因子:
所述步骤S3包括:
S32.构建损失项如式:
其中Aij=∑e∈E∑(i,j)∈e(w(e)/δ(e))是超图中两个顶点之间的权重,其中Lhyper是超图的归一化拉普拉斯矩阵,根据Lhyperm=I‑M计算: 其中Dv,De,Dw是图像特征所构建超图对应的顶点的度、超边的度和超边权重的对角矩阵,构造如下:所述步骤S4包括:
整合第一目标函数和第二目标函数,得到完整的目标函数:
2.根据权利要求1所述的基于有监督超图离散化图像二值编码方法,其特征在于,所述在优化目标函数式2‑13时需要优化的参数是B,W,H,分步优化该三个参数;包括:H‑Step在求解H时,应固定B和W,将其视为常数:
2 T 2
minα||B‑H(X)||=||B‑PΦ(X)|| (2‑14)T ‑1 T
2‑14式对P求偏导为0,求得解析解为:P=(Φ(X)Φ(X)) Φ(X)BW‑Step在求解W时,应固定H和B,将其视为常数:T 2 2
min||Y‑WB||+λ||W|| (2‑15)T ‑1 T
2‑15式对W求偏导为0,求得解析解为W=(BB+λI) BYB‑step在求解B时,按照求解W和H一样的方法,应固定W和H,将其转化成如下形式:对2‑16进行化简成如下的形式:其中M采用归一化拉普拉斯矩阵 L=I‑M,引入辅助变量Q=WY+αH(X),2‑17式等价于2‑18:
3.根据权利要求2所述的基于有监督超图离散化图像二值编码方法,其特征在于,所述采用“位循环坐标下降方法”学习哈希码B矩阵的过程为:T T
先令b 是B的第l行向量,B′是B去掉b剩余的部分;相似的,q 是Q的第l行向量,Q′是Q去T
掉q剩余的部分,v是Q的第l行向量,W′是W去掉v剩余的部分,将2‑18进行化简:T 2 T T T
式中||bv||=Tr(vbbv)=nvv=const,同理,T T
Tr(BQ)=const+qb (2‑20)T
对于tr(BMB)按照逐位下降法思想,化简为:T T
Tr(BMB)=const+bMb (2‑21)那么式子2‑15等价形式如下式(2‑22)所示:n
s.t.b∈{‑1,+1} (2‑22)。
4.根据权利要求3所述的基于有监督超图离散化图像二值编码方法,其特征在于,2‑22式使用“符号梯度”方法进行求解,定义一个局部函数 来线性替代f(b)在点bj+1处的取值,使用 作为f(b)的近似函数对b作离散优化;
给定bj,在推导bj+1时,有对于bj+1要保证它的存在,引入一个指示函数 并更新bj:当所有元素不再更新时,终止迭代。
说明书 :
一种基于有监督超图离散化图像二值编码方法
技术领域
背景技术
文本的传统图像检索方法是采用人工的手段对图像标注,利用文字标签信息进行检索。但
是,随着图像数据的快速增加,人工标注图片太过费力,耗时较长,并带有主观偏差,而且有
些图片根本无法用文本信息来进行描述。因此基于内容的图像检索(CBIR)便应运而生。
一个基本问题是当特征维度高且数据量非常庞大时,数据存储空间将随着特征维度的增
加,迅速增加,检索效率会随之降低,这种现象称为“维度灾难”。
据检索中,用户更注重的是检索效率,而对检索的准确性不做过高的要求。对于大规模数据
的检索,近似的检索结果就能满足用户的检索需求。从而在解决实际大规模数据检索问题
时,可以合理的牺牲检索精度,来提高检索的效率。
明距离代替原始空间的欧氏距离行快速检索,同时还能保持较高的准确性。通过线下学习
原始数据的哈希码,对于新查询的数据,可以大幅提高其在数据中的检索速度,满足实际的
检索需求。
发明内容
d维特征向量,用X=[x1,...,xn]∈R 表示训练集,{(bi∈{‑1,+1} ),i=1,2,...,n}是
训练集所有样本通过学习哈希函数映射到汉明空间的二值化哈希码,每个样本的哈希码长
度为r,r取值一般较小数十位到数百位不等,哈希码码位取值为‑1或者+1,用B=[b1,...,
r×n
bn]∈{‑1,+1} 表示训练集对应的哈希编码结果;
∈R 是各个类别的激活值,与标签对应。根据W b的最大值yk对应的类标,将样本数据点x
分类到第k个类别。采用下面的优化函数:
码的分类质量。λ是正则化参数,Y=[y1,...,yn]∈R 是训练集的真实标签矩阵,满足下面
的约束条件。||·||是L2范数。α是哈希函数H(xi)拟合哈希码bi错误率的惩罚参数。理论上,
bi与H(xi)之间距离尽量小,所以参数α的值尽量大。b
的数据点表示为一条超边。
Dw是图像特征所构建超图对应的顶点的度、超边的度和超边权重的对角矩阵,构造如下:
Q去掉q剩余的部分,v是Q的第l行向量,W′是W去掉v剩余的部分,将上式进行化简:
化;给定bj,在推导bj+1时,有 对于bj+1要保证它
的存在,引入一个指示函数 并更新bj:
哈希函数时,利用数据的标签信息对图像语义信息的表示作用,同时引入超图方法,通过超
图构建数据内部高阶语义相关性,保证数据在原始空间和在汉明空间距离一致性。在学习
哈希函数时放弃“松弛”的策略,直接对离散变量约束优化问题进行求解。采用“离散循环坐
标下降”算法,引入一个辅助变量,逐位学习所有样本数据的哈希码。在逐位学习哈希码过
程中,构造非线性哈希函数,因为非线性函数与线性函数相比对特征具有更好的表达能力。
同时,利用标签信息,学习二值化哈希码可以认为是对二值化特征向量进行分类,采用线性
分类器对哈希码进行二值分类,生成二值化哈希码的区分性更强。本方法充分考虑近似样
本点对在汉明空间与原始语义一致的原则,原始空间近似样本点对映射到汉明空间之后,
哈希码尽量一致,而且产生紧致的哈希码。既可以保持数据在原始空间相似性,又能提高检
索的准确率。
附图说明
具体实施方式
d维特征向量,用X=[x1,...,xn]∈R 表示训练集,{(bi∈{‑1,+1} ),i=1,2,...,n}是
训练集所有样本通过学习哈希函数映射到汉明空间的二值化哈希码,每个样本的哈希码长
度为r,r取值一般较小数十位到数百位不等,哈希码码位取值为‑1或者+1。用B=[b1,...,
r×n
bn]∈{‑1,+1} 表示训练集对应的哈希编码结果。哈希学习的目的是学习训练集X的二值
化的哈希码B,并尽量保持语义相似性。
原始数据的近邻性。哈希函数采用如下非线性形式:
矩阵相比原始数据具有可区分性,生成对应的二值化的哈希码能够近似表示原始数据。
希码,对线性分类器的分类是最优的。现定义一个线性多分类模型如下所示:
∈R 是各个类别的激活值,与标签对应。根据W b的最大值yk对应的类标,将样本数据点x
分类到第k个类别。采用下面的优化函数:
码的分类质量。λ是正则化参数,Y=[y1,...,yn]∈R 是训练集的真实标签矩阵,满足下面
的约束条件。||·||是L2范数。α是哈希函数H(xi)拟合哈希码bi错误率的惩罚参数。理论上,
bi与H(xi)之间距离尽量小,所以参数α的值尽量大。b
令bi=sgn(H(xi)),放弃bi的离散约束限制,获得bi的近似解,再采用量化措施,获得二值化
哈希码,会产生量化误差,大部分现存算法都采用这种措施,很显然这类方法获得的解是次
最优解。
直接约束。本方法根据谱图分析理论,引入超图(Hypergraph)的概念,对数据哈希码之间的
距离度量一致性进行约束。
图中,一条边通常只连接两个顶点,而在超图中,每一条超边可能同时连接三个以上顶点。
同时,谱图中,边与边之间最多只能共享一个顶点,而在超图中超边之间可能同时共享多个
顶点。从以上几点区别可以看出,谱图只能描述数据点之间的简单关系,而超图则可以表示
数据之间的某些高阶关系。
点,而每个顶点与他的k‑近邻的数据点表示为一条超边。在超图中,通常超边的数量与顶点
的数量是相等的,而每条超边包含k+1个顶点。顶点之间的相似性通过原始特征之间的距离
来度量。具体来讲,超图G可以用|V|×|E|规模的关联矩阵(|·|表示求基数操作),G中的顶
点vi与超边ej的关联度可以表示为:
过超边包含的顶点之间的特征的相似度来计算:
间内,在局部空间内呈线性关系的数据点之间都是相似的,在映射至汉明空间后,数据点之
间的汉明距离仍然要求较小,反之,在原流形空间中距离较远的数据点,在映射至汉明空间
后,数据点之间的汉明距离则要求较远。由于超图可以保留数据流形空间内部的高阶关系,
所以采用超图对映射特征进行约束可以有效改善映射后特征的平滑度,构建损失项如式:
De,Dw是图像特征所构建超图对应的顶点的度、超边的度和超边权重的对角矩阵,构造如下:
n
元素bi∈{‑1,+1}放松为{‑1≤bij≤+1,j=1,…n},再通过普通数值解求解方法,求解出最
优值B。但是这类方法基本上都忽视了由于“松弛”导致的误差问题,误差积累会影响哈希码
的质量。本文对约束变量B仍要求取离散值,采用“位循环坐标下降”方法,进行r次迭代运
算,在迭代到第k次时,计算所有样本n的第k位哈希码,效率非常高效。
学习第2位哈希码,如此迭代r次,即可完成n个样本的所有r位哈希码矩阵B的学习。
行向量,Q′是Q去掉q剩余的部分,v是Q的第l行向量,W′是W去掉v剩余的部分,将上式进行
化简:
代f(b)在点bj+1处的取值,使用 作为f(b)的近似函数对b作离散优化。给定bj,在推导
bj+1时,有 此处有这么一种情形,导数 的
值全为0的情况,对于bj+1要保证它的存在,引入一个指示函数 采用下面
的策略更新bj:
由于f(bj)是收敛的,那么bj也是收敛的。
的背景且类内各个物体之间变化很大,该数据集并没有提供特征数据,实验分别提取gist
和cnn特征。实验时随机选取1000图片数据作为查询数据集,余下的数据作为训练集。
数对图像进行哈希编码,然后将得到的哈希码与数据库中保存的哈希码进行对比,计算相
似度。这个过程是通过计算机硬件“异或”操作完成,速度较快。
(ITQ、SH、AGH、SDH)有相对较高的MAP。当编码码长增加时,基于机器学习的方法的性能提升
效果明显。当编码码长小于64位时,采用”离散“的优化方法如SDH以及本方法,效果要明显
好于采用”松弛“的优化方法,表明离散地优化方式学习到的哈希码更紧致。同时本文提出
的离散图哈希方法主要对相似样本进行约束,同时结合“离散”优化策略,即使码长较短性
能指标均优于其他哈希方法。
实验结果可以明显看出,本方法的检索性能要好于其他对比算法。
不脱离本发明构思的前提下,还可以做出若干简单推演或替换,都应当视为属于本发明的
保护范围。