CN102033933B - 最大化平均查准率均值的距离测度优化方法 - Google Patents

Abstract

本发明公开了一种最大化平均查准率均值(MAP)的距离测度优化方法，包括以下步骤：(1)获取包含查询图像-待查询图像对集合的图像数据库；(2)采用平滑函数对MAP进行逼近，将其转换为目标函数并添加正则化项，使得目标函数是连续可微的；(3)使用图像数据库中的查询图像-待查询图像对，采用基于梯度下降的优化技术对目标函数进行优化，并重复优化过程，取使MAP最大的解作为最优的线性变换矩阵；(4)获得由最优线性变换矩阵定义的距离测度。本方法的具有优化过程和目标直接的特点，用本方法得到的距离测度可达到更好的图像检索性能。

Description

最大化平均查准率均值的距离测度优化方法

技术领域

本发明涉及一种用于提高图像检索性能的距离测度优化方法，具体来说涉及一种最大化平均查准率均值的距离测度优化方法。

背景技术

基于内容的图像检索(Content-Based Image Retrieval，CBIR)的基本思想是对图像的视觉特征进行提取，以视觉特征作为索引来实现较高层次的图像检索。CBIR技术可以为管理图像数据、临床诊断、医学教学等提供支持和帮助。特别地，医学图像中相似病灶的检索，可提高临床诊断的可靠性和相关信息的完整性。

一般地，CBIR系统为了能让查询结果按照相似度从大到小的顺序返回，需在图像特征空间中定义一个距离测度或相似性度量来衡量数据库中待查询图像与查询图像间的差别，返回结果时，待查询图像按照差别大小的排序。常用的距离测度有：欧氏距离、马氏距离、柯西距离等。CBIR系统的检索性能很大程度上取决于两方面：1.用于表达图像内容和语义概念的视觉特征；2.在特征空间中定义的距离测度或相似性度量。CBIR系统中通常采用低层视觉特征，如颜色、纹理、形状、边缘等描述图像内容。然而低层视觉特征的描述能力有限，表达图像时信息会有损失，因而低层视觉特征一般不能直接表达或反映图像的高层语义。这样，在低层特征空间中，我们难以用上述一般性的距离测度定义一个与语义概念紧密关联的相似性度量，即存在所谓的“语义鸿沟”，使得CBIR系统的检索性能与实际需求有一定距离。

关联反馈(Relevance Feedback)和距离测度学习(Distance Metric Learning)方法可以用于减小语义鸿沟，提高CBIR的检索性能。关联反馈中用于学习的数据难以获取，系统需要多次调整才能达到满意效果，用户使用不是非常方便。距离测度学习方法可依据事先标注的图像样本，建立低层图像特征和高层语义之间的映射，从而定义反映语义差别的距离测度，提高检索性能。现有的距离测度学习方法，多针对聚类或k近邻分类问题设计，其学习目标是为了提高聚类或k近邻分类的准确率。然而，CBIR系统的检索精度指标与分类准确率有很大的不同，如平均查准率均值(Mean Average Precision，MAP)、NDCG(Normalized DiscountedCumulative Gain)，都与数据库中待查询图像的排序有关系，使用优化针对聚类或分类问题设计的目标函数进行距离测度学习，不一定能得到检索性能最佳的距离测度。而且，由于检索精度指标不是连续可微的，对其进行优化存在一定困难。

发明内容

本发明的目的在于提供一种最大化平均查准率均值的距离测度优化方法，本方法具有优化过程和目标直接，优化得到的距离测度能反映图像的语义差别，用本方法得到的距离测度可达到更好的图像检索性能。

本发明的目的可通过以下的技术措施来实现：

一种最大化平均查准率均值的距离测度优化方法，包括以下步骤：

(1)获取包含查询图像-待查询图像对集合的图像数据库；

(2)采用平滑函数对MAP进行逼近，将其转换为目标函数并添加正则化项，使得目标函数是连续可微的；

(3)使用图像数据库中的查询图像-待查询图像对，对目标函数采用基于梯度下降的方法进行优化，并重复优化过程，取使MAP最大的解作为最优的线性变换矩阵；

(4)图像间距离测度的获取，包括两种方式：用步骤(3)中的最优线性变换矩阵对图像数据库中的图像特征先进行变换，再用变换特征的欧氏距离定义图像间的距离测度；或者是用步骤(3)中的最优线性变换矩阵定义马氏距离作为图像间的距离测度。

所述步骤(1)中的图像数据库由图像或图像区域特征、图像类别构成。

所述步骤(1)中依据是否包含相同解剖结构、相同类型病灶等确定图像对是否相关，对查询-待查询图像对进行标注。

所述步骤(2)中对MAP进行逼近的过程为：对给定的查询图像，任一待查询图像的排序序号使用Sigmoid型函数进行平滑逼近，进而得到MAP的平滑逼近。

所述待查询图像的排序序号由该待查询图像和其他所有待查询图像与查询图像之间的距离进行比较确定。

所述步骤(3)中变换矩阵的初始解可为一随机矩阵或由其他方法得到的变换矩阵。

所述步骤(3)中采用随机梯度下降算法来优化目标函数。

本发明方法相对于现有技术来说，具有以下的有益效果：

1、本方法涉及图像检索、统计学习和数值优化等技术，通过统计学习直接优化平均查准率均值(Mean Average Precision，MAP)，可用于图像检索、聚类分析、数据约减等。本方法主要对标注的图像数据进行统计学习，得到一个线性变换矩阵，将原始特征空间映射至一个新的更具鉴别力的特征空间，在新的特征空间中以欧氏距离作为图像相似性度量进行检索，达到较高的MAP。

2、本发明方法直接解线性变换矩阵，无需使用费时的半正定规划算法进行求解，并可通过直接调整变换矩阵的维数对原始特征进行维数约减，而不是对半正定矩阵的秩进行约束或间接地调节正则化参数实现维数约减。该方法以检索精度指标MAP的平滑逼近为目标函数，相对于其他一些距离测度学习方法，优化过程和目标更为直接，映射后的低层图像特征与高层语义特征联系更为紧密，检索性能更优。在基于内容的医学图像检索应用中，本发明比其他一些距离测度学习方法得到的距离测度可达到更好的检索性能。

3、由于对所有查询图像-待查询图像对计算目标函数及梯度的计算量非常大，因此，本方法中采用随机梯度下降算法进行优化，可减小对计算机内存的需求、加快算法收敛速度；此外，由于目标函数非凸，解空间中存在很多局部极值点，为避免解陷入局部极值点，通过其他较快速的距离测度学习方法估计一个较接近最优解的初始解，然后多次重复优化过程取最优解。

附图说明

图1是本发明的最大化平均查准率均值的距离测度优化方法的流程图；

图2是本发明优化检索精度指标MAP过程中MAP随优化算法迭代次数的收敛情况示意图；

图3是本发明与其他距离测度优化方法得到的距离测度用于检索的查全-查准率曲线；

图4是四种距离测度在返回图像为50幅时的查准率均值曲线图；

图5是使用本发明优化得到的距离测度用于脑部肿瘤T1加权增强MRI图像病检索的示例

具体实施方式

图1示出了本发明的最大化平均查准率均值的距离测度优化方法的具体流程，包括以下步骤：

(1)获取包含人工标注的查询图像-待查询图像对的集合的图像数据库；图像数据库由图像或图像区域特征、图像类别构成。

(2)采用平滑函数对MAP进行逼近，将其转换为目标函数并添加正则化项，使得目标函数是连续可微的；变换矩阵初始解可取一个随机矩阵或由其他较快速的距离测度学习方法估计的变换矩阵。对MAP进行逼近的过程为：对给定的查询图像，任一待查询图像的排序序号使用Sigmoid型函数进行平滑逼近，进而得到MAP的平滑逼近。

待查询图像的排序序号由该待查询图像和其他所有待查询图像与查询图像之间的距离进行比较确定。

(3)使用图像数据库中的查询图像-待查询图像并采用随机梯度下降算法来优化目标函数，重复优化过程，取使MAP最大的解作为最优的线性变换矩阵；

(4)图像间的距离测度用于对图像进行检索，步骤(3)中的最优线性变换矩阵的使用方式包括两种：一种是用线性变换矩阵对图像数据库中的图像特征先进行变换，再用变换特征的欧氏距离定义图像间的距离测度，从而进行图像查询；另一种是用线性变换矩阵定义马氏距离作为图像的距离测度进行图像查询。

下面结合脑部T1加权增强MRI图像检索问题，阐述本发明的工作原理和步骤。

步骤1，从图像数据库读取MRI图像、图中肿瘤的病理类型和医生手工勾画的病灶轮廓，提取病灶区域灰度、纹理、形状和边缘等特征，特征向量表示为x_i。定义包含相同类型肿瘤的图像为相关图像，否则为不相关图像。图像检索的任务是将数据库中与查询图像中病灶区域病理类型相同的图像返回给用户。

步骤2，由于MAP与待查询图像的排序有关，首先依据查询图像与待查询图像之间的距离确定和逼近每一待查询图像的排序序号。设L为一d×D(d≤D)实数矩阵，半正定矩阵W＝L^TL，则x_i与x_j之间的马氏距离(平方)为

d_ij＝||Lx_i-Lx_j||²＝(x_i-x_j)^TL^TL(x_i-x_j)＝(x_i-x_j)^TW(x_i-x_j)，

这里^T表示矩阵的转置操作。设查询特征向量为x_q，查询-待查询对为(x_q，{x_i，i＝1，2，...，N})，这里N为待查询图像总数，待查询特征向量x_i的排序序号可表达为

$\mathrm{\π}\left(x_i\right)=1+\underset{k,k\≠i}{\mathrm{\Σ}}1\{d_{\mathrm{qi}}>d_{\mathrm{qk}}\}=1+\underset{k,k\≠i}{\mathrm{\Σ}}1\{\mathrm{\Δ}{d}_{\mathrm{ik}}>0\},$

其中Δd_ik＝d_qi-d_qk，1{}为指示函数。由于指示函数不连续、不可微，排序序号π(x_i)作为距离d_qi或L的函数也是不连续、不可微的。指示函数可用连续可微的Sigmoid型函数，记为S(Z)。排序序号π(x_i)的平滑逼近为

检索精度指标平均查准率(Average Precision，AP)定义为

其中rel(x_i)∈{0，1}表示两级相关的标号，N⁺为与查询图像相关的图像总数，

MAP为平均查准率在所有查询对上的平均。AP可写成如下形式

$\mathrm{AP}=\frac{1}{N^{+}}\underset{i}{\mathrm{\Σ}}(\frac{\mathrm{rel}\left(x_i\right)}{\mathrm{\π}\left(x_i\right)}+\underset{i,i\≠j}{\mathrm{\Σ}}\mathrm{rel}\left(x_i\right)\mathrm{rel}\left(x_j\right)\frac{1\{\mathrm{\Δ}{d}_{\mathrm{ij}}>0\}}{\mathrm{\π}\left(x_i\right)}).$

用

替代π(x_i)，并再次用Sigmoid函数逼近指示函数，AP的平滑逼近为

$\hat{A}P=\frac{1}{N^{+}}\underset{i=1}{\overset{N}{\mathrm{\Σ}}}(\frac{\mathrm{rel}\left(x_i\right)}{\widehat{\mathrm{\π}}\left(x_i\right)}+\underset{k,k\≠i}{\mathrm{\Σ}}\frac{\mathrm{rel}\left(x_i\right)\mathrm{rel}\left(x_k\right)S\left(\mathrm{\Δ}{d}_{\mathrm{ik}}\right)}{\widehat{\mathrm{\π}}\left(x_i\right)}).$

变换矩阵L的正则化项表示为Reg(L)。Reg(L)可取trace(L^TL)，这里trace(M)表示矩阵M的迹；Reg(L)也可取L的其他范数形式。

最大化MAP，等价于最小化1-MAP。定义平均查准率损失函数：

${\mathrm{Loss}}_{\mathrm{AP}}\left(L\right)=1-\hat{A}P,$

本发明定义的目标函数具有如下形式：

R(L)＝Loss_AP(L)+γReg(L)，

其中γ为权重系数，用于控制损失函数和正则化项之间的平衡。R(L)是连续可微的。

本发明的距离测度优化问题表达为：

$L*=\underset{L\∈R^{d\×D}}{\arg \min }\frac{1}{M}\underset{m=1}{\overset{M}{\mathrm{\Σ}}}{R}_m\left(L\right),$

其中M为查询-待查询图像对总数，R_m(L)为在第m个查询-待查询图像对上的目标函数。

步骤3，首先估计初始解L₀，L₀可为一d×D随机矩阵或者取其他距离测度学习方法得到的解。第t次迭代时，随机从图像数据库中产生查询-待查询对(x_q，{x_i，i＝1，2，...，N_t})_t，计算R(L_t)在该查询对上关于L_t的梯度g_t，更新L_t＝L_t-1-η_tg_t，这里

t＝1，2，...，T为迭代次数，T为设定的最大迭代次数，η_t为第t次迭代的步长；重复迭代，直至达到最大迭代次数或解收敛条件。多次重复上述过程，选取使检索精度指标最大的解作为L^*。如取trace(L^TL)作为正则化项，则梯度g_t为：

$g_t=\frac{\∂R\left(L_t\right)}{\∂L_t}=-\frac{\∂{\mathrm{Loss}}_{\mathrm{AP}}\left(L_t\right)}{\∂L_t}+2\mathrm{\γ}{L}_t$

损失函数关于L_t的偏导

通过链式法则得到。

算法参数α、γ可通过交叉检验方法进行调整，经验地α取1～10，γ取0.0001～0.01可达到满意效果。梯度下降的步长可取η_t＝η₀exp(-2t/T)，t为当前迭代次数，也可采用其他方式调整步长。图2示出了本发明优化检索精度指标MAP过程中MAP随优化算法迭代次数的收敛情况。

步骤4，对于步骤3得到的线性变换L^*，有两种等价的方式应用于图像检索。一是用L^*将原始特征向量映射至新的特征空间，然后用标准的欧氏距离作为图像的相似性度量；一是直接用L^*定义马氏距离作为图像的相似性度量进行检索，前者可减小特征所需的存储空间、加快图像检索速度。

图3为本发明与其他距离测度学习方法得到的距离测度用于检索的查全-查准率曲线，其中的实验数据为脑部T1加权增强MRI图像，包含相同类型肿瘤的图像为相关图像，反之为不相关图像。比较用的距离测度包括标准的欧氏距离、由大间隔近邻分类(LMNN)和局部Fisher判别分析(LFDA)方法学习得到的马氏距离。可见本发明方法可达到更高的MAP，优于欧氏距离和其他两种距离测度学习方法。

图4为四种距离测度在返回图像为50幅时的查准率均值曲线，所用图像数据与图3相同。本发明中的距离测度优化方法，在返回前5-50图像时，查准率均值高于其他三种距离测度。

图5为使用本发明得到的距离测度用于脑部肿瘤T1加权增强MRI图像病检索的示例，图中左上角的图像为查询图像，加实线框(白色线框)的表示检索到的相关图像(表示肿瘤类型相同)，加虚线框(白色虚线框)的表示检索到的不相关图像(表示肿瘤类型不相同)，图中肿瘤区域轮廓已人工勾出。上述实验数据表明本发明比其他一些距离测度学习方法得到的距离测度可达到更好的检索性能。

在本发明的实施方式不限于此，其他类似MAP由待查询图像排序序号定义的检索精度指标，如Preck和NDCG等，也可以使用类似上述的公式和方法进行逼近，然后用本发明的优化方法进行求解，在此不一一列举；其他一些基于梯度下降的优化技术和步长调整方式，如共轭梯度下降算法也可用于实现本发明目的；根据本发明的上述内容，按照本领域的普通技术知识和惯用手段，在不脱离本发明上述基本技术思想前提下，本发明还可以做出其它多种形式的等效修改、替换或变更，均落在本发明权利保护范围之内。

Claims (4)

1.一种最大化平均查准率均值的距离测度优化方法，包括以下步骤：

(1)获取包含查询图像-待查询图像对集合的图像数据库；

(2)采用平滑函数对平均查准率均值进行逼近，将其转换为目标函数并添加正则化项，使得目标函数是连续可微的；对平均查准率均值进行逼近的过程为：对给定的查询图像，任一待查询图像的排序序号使用Sigmoid型函数进行平滑逼近，进而得到平均查准率均值的平滑逼近；

(3)使用图像数据库中的查询图像-待查询图像对，对目标函数采用基于梯度下降的方法进行优化，并重复优化过程，取使平均查准率均值最大的解作为最优的线性变换矩阵；

(4)图像间距离测度的获取，包括两种方式：用步骤(3)中的最优线性变换矩阵对图像数据库中的图像特征先进行变换，再用变换特征的欧氏距离定义图像间的距离测度；或者用步骤(3)中的最优线性变换矩阵定义马氏距离作为图像间的距离测度。

2.根据权利要求1所述的最大化平均查准率均值的距离测度优化方法，其特征在于：所述步骤(1)中的图像数据库由图像或图像区域特征、图像类别构成。

3.根据权利要求1所述的最大化平均查准率均值的距离测度优化方法，其特征在于：所述步骤(1)中的查询图像-待查询图像对的集合是依据是否包含相同解剖结构、相同类型病灶确定图像对是否相似，进行标注的。

4.根据权利要求1所述的最大化平均查准率均值的距离测度优化方法，其特征在于：所述步骤(3)中采用随机梯度下降算法来优化目标函数。

Images