一种基于多视点及二部图匹配的3D目标检索方法

摘要

一种基于多视点及二部图匹配的3D目标检索方法，涉及3D目标检索。1)视点提取：从网络中查找相似的图像；2)特征提取：对查找的图像提取特征；3)视点特征聚类：对于网络中已经找到的图像提取代表性视点；4)二部图匹配：对于每一种特征，建立待查找模型与数据库中模型的二部图；5)多特征融合：通过建立的二部图，计算数据库中每个模型与待查找模型的相似度；6)初次排序：根据计算的相似度，对数据库中的模型进行排序；7)重排序：请用户对排序结果进行评价，根据用户的评价重新对数据库中的模型排序。可应对多特征情况，无需考虑3D模型与2D模型的转换问题，视点选择的自由度较大，可通过用户的反馈信息对检索结果进行合理调整。

说明书

技术领域

本发明涉及3D目标检索，尤其是涉及一种基于多视点及二部图匹配的3D目标检索方法。

背景技术

随着图形硬件、计算机技术以及3D技术的发展——3D重建、3D模型，在3D电影、3D图形学、CAD制图和3D结构设计的广泛应用，因而对于3D目标检索技术的高效的提出了更高的要求。一般来说,3D目标检索技术根据被检索的目标的数据组织形式可以分为两类，基于模型(model based)的3D目标检索技术和基于视点(view based)的3D目标检索技术。但是由于在实际应用中获得3D目标的模型(model)是十分困难的。当然可以利用视点信息重建出3D目标的模型，但是这样做不仅会有很大的时间开销，而且重建出的模型往往与物体的真实样貌有较大的偏差。这就使得基于模型的3D目标检索技术有很大的局限性。与之相对的，基于视点的3D目标检索技术，不仅获取信息更为便利，而且运算效率高。同时由于前人在2D图像技术已经积累了大量的经验，这就使得基于视点的3D目标检索技术要优于基于模型的3D目标检索技术。在基于视点的3D目标检索的基础上，基于二部图匹配和特征融合可大幅度提高目标检索的性能。另外，现有技术无法处理用户的反馈信息，无法处理多特征的情况，检索效率低，无法处理用户的反馈信息，并存在以下技术问题：

1、当3D物体的深度信息丢失，或者根本没有相应的3D模型(只有视点信息)时，如何对目标进行检索。

2、如何利用同一3D物体提取的多个特征。

3、当用户可以对部分检索的结果提供反馈信息时如何对检索的结果进行修正。

发明内容

本发明的目的在于提供一种基于多视点及二部图匹配的3D目标检索方法。

本发明包括以下步骤：

1)视点提取：从网络中查找相似的图像；

2)特征提取：对查找的图像提取特征；

3)视点特征聚类：对于网络中已经找到的图像提取代表性视点；

4)二部图匹配：对于每一种特征，建立待查找模型与数据库中模型的二部图；

5)多特征融合：通过建立的二部图，计算数据库中每个模型与待查找模型的相似度；

6)初次排序：根据计算的相似度，对数据库中的模型进行排序；

7)重排序：请用户对排序结果进行评价，根据用户的评价重新对数据库中的模型排序。

在步骤1)中，所述视点提取的具体方法可为：将3D目标投影到2D平面上，或给真实场景中的物体拍照。

在步骤2)中，所述特征提取的具体方法可为：对图像提取BoVW特征、椭圆傅里叶特征和Zernike矩特征。

在步骤3)中，所述视点特征聚类的具体方法可为：假设对某个物体共有n₀个视点，每个视点的特征分别为那么视点特征的聚类是把这些视点以“算法1”方式划分为多个类别，聚类的目的是用少数几个视点特征代表所有的视点特征；

所述算法2为凝聚层次聚类即HAC算法，表示如下：

(1)计算每两个视点之间的距离：若两个视点之间的距离小于给定的阈值，则将这两个视点合并成一个簇，则原有的n₀个视点经过合并，形成了n₁个簇；所述阈值是一个数字，可为0.75；所述簇是视点的集合，是将若干个视点看成是一个整体；

(2)计算每两个簇之间的距离：若两个簇之间的距离小于给定的阈值，则将这两个簇合并成一个簇，原有的n₁个视点经过合并，形成n₂个簇；所述两个簇之间的距离是两个簇中视点的平均值之间的距离；所述阈值可为0.75；所述合并是集合运算中的“并”运算；

(3)重复步骤(2)，直至任意两个簇的距离都大于给定的阈值；所述阈值可为0.75；

(4)计算每个簇中视点的平均值，一个平均特征值代表一个簇，所有的簇代表当前的物体，即，经过凝聚层次聚类，将从前的n₀个视点数量减少。

在步骤4)中，所述二部图匹配的具体方法可为：

通常认为两个物体之间的视点应该是一一对应的，而不是一对多的关系，这就需要对二部图进行优化，即二部图匹配，其主要目的是二部图的匹配是把视点特征之间有用的关系保留，去除无用的关系；

所述二部图匹配可采用KM算法，采用贪婪的算法求解二部图匹配问题，具体方法如下：

输入：二部图的边的矩阵E^T(n_o*n_q维)

输出：二部图的关联矩阵X(n_o*n_q维)

X＝zeros(n_o,n_q)//关联矩阵X初始化为与E^T同样大小的全0矩阵，即X与E^T中元素的排列方式相同，且元素值全为0。

n_min＝min{n_q,n_o}//求矩阵的行数与列数中的最小值，若矩阵的行数大于列数，则n_min为矩阵的行数；否则为列数。

For i＝1:n_min//贪婪地求解关联矩阵X，这里的For代表循环，i为循环的元素，1:n_min为循环的范围(等价于1,2,3,4，…,n_min)

//找到边的矩阵E^T中的最大值的坐标(i_max,j_max)，其中E^T(i,j)即为矩阵第i行第j列的元素值，即为找到当前矩阵E^T中元素值最大的元素的位置，即为将找到的当前矩阵E^T中元素值最大的元素的位置赋值给(i_max,j_max)

X(i_max,j_max)＝1//将X矩阵中第i_max行第j_max列的元素值赋值为1

E^T(i_max,:)＝-INF//将E^T矩阵中的i_max行置为负无穷大，其中“：”符号代表所有元素，即E^T(i_max,:)表示第i_max行中的所有元素，-INF代表负无穷大

E^T(:,j_max)＝-INF//将E^T矩阵中的j_max列置为负无穷大，E^T(:,j_max)表示第j_max行中的所有元素

End。

在步骤5)中，所述多特征融合的具体方法可为：采用的融合手段为简单的线性加权，即将得到的三种特征的二部图以一定的比例相加，即E_mix＝λ₁E_BoVW/SIFT+λ₂E_Fourier+λ₃E_Zernike，其中λ₁＝0.014，λ₂为0.98，λ₃为0.006，E_BoVW/SIFT,E_Fourier,E_Zernike分别为通过BoVW特征、椭圆傅里叶特征和Zernike矩特征建立的优化过的二部图。

在步骤6)中，所述初次排序的具体方法可为：对于融合后的二部图矩阵，将其中的所有元素(所有数字)相加所得到的值(值越小说明越相似)作为判断查询目标与数据库目标相似程度的依据。并根据这个值对数据库中的目标进行由小到大的排序。

在步骤7)中，所述重排序的具体方法可为：通过获取用户相关反馈信息(userrelevant feedback)，让用户手动对得到的每组检索结果的前10个结果的做标记，标记出其中与查询目标同类和不同类的样本。将融合得到的特征对前100个查询得到的目标做重排序，重排序以当前目标到正例目标的最小距离，基于反馈调节的重排序算法如下所示：

输入：反馈信息矩阵RF(num_q*10维)，RF中元素为1代表相应的反馈结果是正例，为0代表结果是负例

已获得的检索结果矩阵Result(num_q*100维)

查询目标的个数num_q

输出：重排序的结果RResult

For i＝1:num_q

n_pos＝sum(RF(i,:))//统计正例个数，其中sum为求和符号，RF(i,:)表示矩阵RF中第i行的所有元素，sum(RF(i,:))表示将矩阵RF中第i行的所有元素的值加在一起；

计算第i个样本到任一正例样本的距离，取其中的最小值的倒数作为新的Score(正例到正例的距离为正无穷大)

用新的Score排序前100个样本

根据新的排序结果重排Result矩阵

结束。

本发明具有以下优点：

1、多特征的提取及融合：分别提取了Zernike矩和BoVW/SIFT特征联合表达目标的区域形状特征，并且提取了基于边界的傅里叶特征建模目标的轮廓特性，通过二部图匹配和特征融合提高检索性能。

2、基于反馈的重排序算法：对于给定的排序结果，由用户手动标记目标的相关程度，计算待排序目标到相关目标的距离；取其中的最小值作为待排序目标到相关目标的距离；根据待排序目标到相关目标的距离对目标进行重排序。引入用户反馈信息后，性能得到了更高提升。

本发明旨在通过二部图匹配、融合多个特征，使各个特征彼此互补，从而探索基于视点的3D目标的本质特性，解决了以往方法无法处理多特征的情况，并大幅度提升了目标检索的性能。除此之外，本发明也加入了用户信息反馈模块，进一步提升了目标检索的效率以及性能。具体来说，本发明分别通过提取Zernike矩和BoVW/SIFT特征联合表达目标的区域形状特征，并且通过提取基于边界的傅里叶特征建模目标的轮廓特性。再经过贪婪检索(即贪婪的二部图匹配)和特征融合提高目标检索的性能。进一步地，当引入用户反馈信息后，性能得到了更高提升。

现有的3D目标检索技术根据被检索的目标的数据组织形式可以分为两类，基于模型(model based)的3D目标检索技术和基于视点(view based)的3D目标检索技术。但是由于在实际应用中获得3D目标的模型(model)是十分困难的。(当然可以利用视点信息重建出3D目标的模型，但是这样做不仅会有很大的时间开销，而且重建出的模型往往与物体的真实样貌有较大的偏差。)这就使得基于模型的3D目标检索技术有很大的局限性。与之相对的，基于视点的3D目标检索技术，不仅获取信息更为便利，而且运算效率也十分的高。同时由于前人在2D图像技术已经积累了大量的经验，这就使得基于视点的3D目标检索技术要优于基于模型的3D目标检索技术。在基于视点的3D目标检索的基础上，基于二部图匹配和特征融合可大幅度提高目标检索的性能。另外，现有技术无法处理用户的反馈信息，我们在其中加入基于用户反馈的重排序算法，大大提高了3D目标检索的效率以及性能。

与现有技术方案的技术角度对比有以下几点：

本发明可以应对多特征情况，且时间复杂度相同(即运算时间大体相等)，本发明无需考虑3D模型与2D模型的转换问题，即视点选择的自由度较大，本发明可以通过用户的反馈信息对检索结果进行合理调整(即调整后性能提升)。

具体实施方式

给定由3D模型组成的数据集，数据集中的每个3D模型都已经提取了足够多的视点以及对应的特征。对于某个想要查找的模型：

1)视点提取：从网络中查找相似的图像；

2)特征提取：对查找的图像提取特征；

3)视点特征聚类：对于网络中已经找到的图像提取代表性视点；

4)二部图匹配：对于每一种特征，建立待查找模型与数据库中模型的二部图；

5)多特征融合：通过建立的二部图，计算数据库中每个模型与待查找模型的相似度；

6)初次排序：根据计算的相似度，对数据库中的模型进行排序；

7)重排序：请用户对排序结果进行评价，根据用户的评价重新对数据库中的模型排序。

以下给出具体实施例。

本发明实施例包括以下步骤：

1)视点提取，具体方法为：将3D目标投影到2D平面上，或给真实场景中的物体拍照；

2)特征提取，具体方法为：对图像提取BoVW特征、椭圆傅里叶特征和Zernike矩特征

3)视点特征聚类，具体方法为：假设对某个物体共有n₀个视点，每个视点的特征分别为那么视点特征的聚类是把这些视点以“算法1”方式划分为多个类别。聚类的目的是用少数几个视点特征代表所有的视点特征；

所述算法3为凝聚层次聚类即HAC算法，表示如下：

(1)计算每两个视点之间的距离：若两个视点之间的距离小于给定的阈值，则将这两个视点合并成一个簇，则原有的n₀个视点经过合并，形成了n₁个簇；所述阈值是一个数字，可为0.75；所述簇是视点的集合，是将若干个视点看成是一个整体；

(2)计算每两个簇之间的距离：若两个簇之间的距离小于给定的阈值，则将这两个簇合并成一个簇，原有的n₁个视点经过合并，形成n₂个簇；所述两个簇之间的距离是两个簇中视点的平均值之间的距离；所述阈值可为0.75；所述合并是集合运算中的“并”运算；

(3)重复步骤(2)，直至任意两个簇的距离都大于给定的阈值；所述阈值可为0.75；

(4)计算每个簇中视点的平均值，一个平均特征值代表一个簇，所有的簇代表当前的物体，即，经过凝聚层次聚类，将从前的n₀个视点数量减少；

4)二部图匹配：通常认为两个物体之间的视点应该是一一对应的，而不是一对多的关系，这就需要对二部图进行优化，即二部图匹配，其主要目的是二部图的匹配是把视点特征之间有用的关系保留，去除无用的关系；

所述二部图匹配可采用KM算法，采用贪婪的算法求解二部图匹配问题，具体方法如下：

输入：二部图的边的矩阵E^T(n_o*n_q维)

输出：二部图的关联矩阵X(n_o*n_q维)

X＝zeros(n_o,n_q)//关联矩阵X初始化为与E^T同样大小的全0矩阵，即X与E^T中元素的排列方式相同，且元素值全为0。

n_min＝min{n_q,n_o}//求矩阵的行数与列数中的最小值，若矩阵的行数大于列数，则n_min为矩阵的行数；否则为列数。

For i＝1:n_min//贪婪地求解关联矩阵X，这里的For代表循环，i为循环的元素，1:n_min为循环的范围(等价于1,2,3,4，…,n_min)

//找到边的矩阵E^T中的最大值的坐标(i_max,j_max)，其中E^T(i,j)即为矩阵第i行第j列的元素值，即为找到当前矩阵E^T中元素值最大的元素的位置，即为将找到的当前矩阵E^T中元素值最大的元素的位置赋值给(i_max,j_max)

X(i_max,j_max)＝1//将X矩阵中第i_max行第j_max列的元素值赋值为1

E^T(i_max,:)＝-INF//将E^T矩阵中的i_max行置为负无穷大，其中“：”符号代表所有元素，即E^T(i_max,:)表示第i_max行中的所有元素，-INF代表负无穷大

E^T(:,j_max)＝-INF//将E^T矩阵中的j_max列置为负无穷大，E^T(:,j_max)表示第j_max行中的所有元素

End；

5)多特征融合：采用的融合手段为简单的线性加权，即将得到的三种特征的二部图以一定的比例相加，即E_mix＝λ₁E_BoVW/SIFT+λ₂E_Fourier+λ₃E_Zernike，其中λ₁＝0.014，λ₂为0.98，λ₃为0.006，E_BoVW/SIFT,E_Fourier,E_Zernike分别为通过BoVW特征、椭圆傅里叶特征和Zernike矩特征建立的优化过的二部图；

6)初次排序。具体方法如下：对于融合后的二部图矩阵，将其中的所有元素(所有数字)相加所得到的值(值越小说明越相似)作为判断查询目标与数据库目标相似程度的依据。并根据这个值对数据库中的目标进行由小到大的排序；

7)重排序。具体方法如下：通过获取用户相关反馈信息(user relevantfeedback)，让用户手动对得到的每组检索结果的前10个结果的做标记，标记出其中与查询目标同类和不同类的样本。将融合得到的特征对前100个查询得到的目标做重排序，重排序以当前目标到正例目标的最小距离，基于反馈调节的重排序算法如下所示：

输入：反馈信息矩阵RF(num_q*10维)，RF中元素为1代表相应的反馈结果是正例，为0代表结果是负例

已获得的检索结果矩阵Result(num_q*100维)

查询目标的个数num_q

输出：重排序的结果RResult

For i＝1:num_q

n_pos＝sum(RF(i,:))//统计正例个数，其中sum为求和符号，RF(i,:)表示矩阵RF中第i行的所有元素，sum(RF(i,:))表示将矩阵RF中第i行的所有元素的值加在一起；

计算第i个样本到任一正例样本的距离，取其中的最小值的倒数作为新的Score(正例到正例的距离为正无穷大)

用新的Score排序前100个样本

根据新的排序结果重排Result矩阵

结束。