基于超图的三维对象检索方法和装置转让专利
申请号 : CN201010571681.9
文献号 : CN102024036B
文献日 : 2012-09-05
发明人 : 戴琼海 , 高跃 , 张乃尧
申请人 : 清华大学
摘要 :
本发明提出一种基于超图的三维对象检索方法和装置，其中，所述方法包括以下步骤：计算数据库中三维对象的所有视图之间的距离矩阵；根据所述距离矩阵对所述所有视图进行聚类以得到多个聚类结果，并根据所述多个聚类结果构建所述三维对象对应的多个超图；对所述多个超图进行融合以形成一个融合后的超图，并对所述融合后的超图进行分析，且根据分析结果建立所述三维对象之间的关联性；根据所述关联性检索所述三维对象。通过本发明的方法，很好的解决了三维对象信息的复杂所带来的检索准确度低的问题，该方法通过超图进行建模，能够有效地进行三维对象的关联性分析，从而能够获得更加准确，更为有效的检索效果。
权利要求 :
1.一种基于超图的三维对象检索方法，其特征在于，包括以下步骤：
计算数据库中三维对象的所有视图之间的距离矩阵；
根据所述距离矩阵对所述所有视图进行聚类以得到多个聚类结果，其中，采用K均值聚类方法对所述所有视图进行聚类，其中，聚类结果根据K值的不同而变化，并根据所述多个聚类结果构建所述三维对象对应的多个超图，其中，以所述三维对象的相应视图集合为所述超图的超边，将每个三维对象作为超图的一个顶点，而获得的每个视图集合作为该超图的一个超边，用来连接超图的顶点，以形成多个超图；
对所述多个超图进行平均融合以形成一个融合后的超图且所述多个超图中的每一个具有相同的权重，并对所述融合后的超图进行分析，且根据分析结果建立所述三维对象之间的关联性，包括根据预设的目标函数对所述融合后的超图的顶点之间的标签进行分析，以获得数据库中任意三维对象之间的关联性，其中，满足关联性要求的所述顶点具有相似的标签；和根据所述关联性检索所述三维对象。
2.如权利要求1所述的基于超图的三维对象检索方法，其特征在于，所述计算数据库中三维对象的所有视图之间的距离矩阵，进一步包括：以Zernike Moments为图像特征对所述所有视图进行特征提取以得到特征提取结果；
根据特征提取结果应用欧式距离计算任意两个视图之间的距离，直到所述所有视图之间的距离计算完毕，得到所述所有视图之间的距离矩阵。
3.一种基于超图的三维对象检索装置，其特征在于，包括：
距离矩阵计算模块，所述距离矩阵计算模块用于计算数据库中三维对象的所有视图之间的距离矩阵；
超图构建模块，所述超图构建模块用于根据所述距离矩阵对所述所有视图进行聚类以得到多个聚类结果，其中，采用K均值聚类方法对所述所有视图进行聚类，其中，聚类结果根据K值的不同而变化，并根据所述多个聚类结果构建所述三维对象对应的多个超图，其中，以所述三维对象的相应视图集合为所述超图的超边，将每个三维对象作为超图的一个顶点，而获得的每个视图集合作为该超图的一个超边，用来连接超图的顶点，以形成多个超图；
关联模块，所述关联模块用于对所述多个超图进行融合以形成一个融合后的超图，并对所述融合后的超图进行分析，且根据分析结果建立所述三维对象之间的关联性，其中，所述关联模块包括融合模块和关联建立模块，其中，所述融合模块用于对所述多个超图进行平均融合以形成一个融合后的超图且所述多个超图中的每一个具有相同的权重，所述关联建立模块用于根据预设的目标函数对所述融合后的超图的顶点之间的标签进行分析，以获得数据库中任意三维对象之间的关联性，其中，满足关联性要求的所述顶点具有相似的标签；和检索模块，所述检索模块用于根据所述关联性检索所述三维对象。
4.如权利要求3所述的基于超图的三维对象检索装置，其特征在于，所述计算数据库中三维对象的所有视图之间的距离矩阵，进一步包括：以Zernike Moments为图像特征对所述所有视图进行特征提取以得到特征提取结果；
根据特征提取结果和欧式距离计算任意两个视图之间的距离。
说明书 :
基于超图的三维对象检索方法和装置
技术领域
[0001] 本发明涉及三维对象处理，三维对象分析技术领域，特别涉及一种基于超图的三维对象检索方法。
背景技术
[0002] 计算机和多媒体技术的进步加快了三维立体对象数据的快速增长。近些年来，三维对象在计算机辅助制造、虚拟现实、医学及娱乐等多种领域的应用日益广泛，因此，快速有效的三维对象检索方法变得越发的重要。
[0003] 传统的三维对象的描述方法主要是基于虚拟模型的，但是应用传统的三维对象描述方法进行对真实三维对象进行表示时通常需要三维重建的过程。由于三维重建的计算量较大，这使得传统的三维对象描述方法并不能很好的应用到真实三维对象的分析与处理上。
[0004] 随着照相机技术的快速发展，更多的方法关注与基于多视图的三维对象分析。这种基于多视图的方法通过一组多视图来描述三维对象的信息，进而完成三维立体对象的检索等进一步的工作。
[0005] 由于一个三维对象包含着大量的多视图，因此如何应用多视图进行三维对象的关联性描述是一个较困难的课题。2003年在欧洲图形学会议上提出的方法中(D.Y.Chen，X.P.Tian，Y.T.Shen，and M.Ouhyoung.On visual similarity based 3d model retrieval.Computer Graphics Forum)提出了光场描述符(Lighting Filed Descriptor)，通过在正十二面体的20个顶点位置设置的照相机阵列进行数据采集，获得多组视图来描述原始三维对象，这些视图从不同的角度来描述三维对象的空间结构信息，另一方面，该方法针对这样的多视图阵列进行匹配来对三维立体对象之间的匹配。以二值的视图的Zernike矩和傅里叶描述符特征被用来作为视图的特征，然而，这种方法中对照相机阵列有固定的设置要求。2007在国际电子电气工程师协会多媒体汇刊上(T.F.Ansary，M.Daoudi，and J.P.Vandeborre，“A bayesian 3-d search engine using adaptive views clustering，”IEEETransactions on Multimedia，vol.9，no.1，pp.78-88，
2007.)提出一种基于贝叶斯分析的三维立体对象检索方法，其中视图获取也是使用固定的
320照相机阵列。该方法首先获得320张原始图片，这里针对原始视图，49维的Zernike矩被选用图像特征，该方法首先从原始视图中进行代表性视图选择，通过对视图之间的整体相似度的计算，进行K均值迭代聚类，其中每一步都尝试将已有的分类结果进行重新聚类，其中K选取为2。这里，贝叶斯信息准备被用来判定聚类的效果及停止条件，在接下来的处理中，只有代表性的视图才应用到具体的检索分析中，通过对视图之间的贝叶斯概率分析来获得整体三维对象之间的相关程度，从而完成三维立体对象的基于视图的检索工作。
2007.)提出一种基于贝叶斯分析的三维立体对象检索方法，其中视图获取也是使用固定的
320照相机阵列。该方法首先获得320张原始图片，这里针对原始视图，49维的Zernike矩被选用图像特征，该方法首先从原始视图中进行代表性视图选择，通过对视图之间的整体相似度的计算，进行K均值迭代聚类，其中每一步都尝试将已有的分类结果进行重新聚类，其中K选取为2。这里，贝叶斯信息准备被用来判定聚类的效果及停止条件，在接下来的处理中，只有代表性的视图才应用到具体的检索分析中，通过对视图之间的贝叶斯概率分析来获得整体三维对象之间的相关程度，从而完成三维立体对象的基于视图的检索工作。
[0006] 这些传统的基于视图的三维对象分析方法主要通过对三维对象的多视图进行直接或间接的匹配等方法进行三维对象之间的比较。但是由于三维对象信息的复杂性，这使得直接应用三维对象的视图匹配的方法并不能很有效的进行三维对象相关性的分析。
发明内容
[0007] 本发明的目的旨在至少解决上述技术缺陷之一。
[0008] 为达到上述目的，本发明一方面提出了一种基于超图的三维对象检索方法，该方法通过应用超图对三维图像进行建模，从而对三维对象之间进行相关性分析。
[0009] 为此，本发明提出了一种基于超图的三维对象检索方法，包括以下步骤：计算数据库中三维对象的所有视图之间的距离矩阵；根据所述距离矩阵对所述所有视图进行聚类以得到多个聚类结果，并根据所述多个聚类结果构建所述三维对象对应的多个超图；对所述多个超图进行融合以形成一个融合后的超图，并对所述融合后的超图进行分析，且根据分析结果建立所述三维对象之间的关联性；和根据所述关联性检索所述三维对象。
[0010] 在本发明的一个实施例中，所述计算数据库中三维对象的所有视图之间的距离矩阵，进一步包括：以Zernike Moments为图像特征对所述所有视图进行特征提取以得到所述特征提取结果；根据所述特征提取结果应用欧式距离计算任意两个视图之间的距离，直到所述所有视图之间的距离计算完毕，得到所述所有视图之间的距离矩阵。
[0011] 在本发明的一个实施例中，所述根据距离矩阵对所述所有视图进行聚类以得到多个聚类结果，进一步包括：采用K均值聚类方法对所述所有视图进行聚类，其中，所述聚类结果根据所述K值的不同而变化。
[0012] 在本发明的一个实施例中，所述根据多个聚类结果构建所述三维对象对应的多个超图，进一步包括：以所述三维对象的相应视图集合为所述超图的超边，连接以每个所述三维对象为相应超图的顶点，以形成多个超图。
[0013] 在本发明的一个实施例中，所述对多个超图进行融合以形成一个融合后的超图，并对所述融合后的超图进行分析，且根据分析结果建立所述三维对象之间的关联性，进一步包括：对所述多个超图进行平均融合，以形成一个融合后的超图；根据预设的目标函数对所述融合后的超图的顶点之间的标签进行分析，以获得数据库中任意三维对象之间的关联性，其中，满足关联性要求的所述顶点具有相似的标签。
[0014] 本发明的另一方面还提出了一种基于三维对象检索的装置，包括：距离矩阵计算模块，所述距离矩阵计算模块用于计算数据库中三维对象的所有视图之间的距离矩阵；超图构建模块，所述超图构建模块用于根据所述距离矩阵对所述所有视图进行聚类以得到多个聚类结果，并根据所述多个聚类结果构建所述三维对象对应的多个超图；关联模块，所述关联模块用于对所述多个超图进行融合以形成一个融合后的超图，并对所述融合后的超图进行分析，且根据分析结果建立所述三维对象之间的关联性；和检索模块，所述检索模块用于根据所述关联性检索所述三维对象。
[0015] 在本发明的一个实施例中，所述计算数据库中三维对象的所有视图之间的距离矩阵，进一步包括：以Zernike Moments为图像特征对所述所有视图进行特征提取以得到所述特征提取结果；根据所述特征提取结果应用欧式距离计算任意两个视图之间的距离。
[0016] 在本发明的一个实施例中，所述超图构建模块包括聚类模块和构建模块，其中，所述聚类模块用于采用K均值聚类方法对所述所有视图进行聚类，其中，所述聚类结果根据所述K值的不同而变化；所述构建模块用于以所述三维对象的相应视图集合为所述超图的超边，连接以每个所述三维对象为相应超图的顶点，以形成多个超图。
[0017] 在本发明的一个实施例中，所述关联模块包括融合模块和关联建立模块，其中，所述融合模块用于对所述多个超图进行平均融合，以形成一个融合后的超图；所述关联建立模块用于根据预设的目标函数对所述融合后的超图的顶点之间的标签进行分析，以获得数据库中任意三维对象之间的关联性，其中，满足关联性要求的所述顶点具有相似的标签。
[0018] 通过本发明的方法，能够有效的解决三维对象信息的复杂所带来的检索准确度低，计算复杂度高等缺点。该方法通过超图进行建模，能够有效地进行三维对象的关联性分析，从而能够获得更加准确，更为有效的三维对象检索效果。
[0019] 本发明附加的方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。
附图说明
[0020] 本发明上述的和/或附加的方面和优点从下面结合附图对实施例的描述中将变得明显和容易理解，其中：
[0021] 图1为本发明实施例的基于超图的三维对象检索方法的流程图；
[0022] 图2为应用本发明实施例的方法检索结果与其他三种检索方法的检索结果的对比图，和
[0023] 图3为本发明实施例的基于超图的三维对象检索装置结构图。
具体实施方式
[0024] 下面详细描述本发明的全部实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，仅用于解释本发明，而不能解释为对本发明的限制。
[0025] 本发明是针对现有三维对象检索的准确度差，难于分析的不足而提出的一种基于超图的三维对象检索方法，该方法通过应用超图对三维对象进行建模，从根据三维对象之间相关性分析结果对三维对象进行检索。
[0026] 以下结合附图对本发明实施例提出的基于超图的三维对象检索方法进行详细描述。
[0027] 如图1所示，为本发明实施例的基于超图的三维对象检索方法的流程图，在本发明的实施例中，该方法包括以下步骤：
[0028] 步骤S101，计算数据库中三维对象的所有视图之间的距离矩阵。
[0029] 具体地，采用Zernike Moments作为数据库中三维对象视图的图像特征，根据特征提取算法对视图进行Zernike Moments特征提取，从而得到所有视图的特征提取结果，接着，使用获得的Zernike Moments特征提取结果，并且采用欧式距离作为计算距离，对视图应用距离计算方法计算任意两个视图之间的距离，从而计算得到任意两个视图之间的距离值。同样地，对于所有视图，采用此距离计算方法对所有视图之间的距离计算完毕，从而获得所有视图之间的距离矩阵。
[0030] 步骤S102，根据所述距离矩阵对所述所有视图进行聚类以得到多个聚类结果，并根据所述多个聚类结果构建所述三维对象对应的多个超图。
[0031] 具体地，使用K均值聚类方法对所有视图进行聚类，其中通过设定不同的K值，生成不同的聚类结果，并且在每组聚类结果的基础上，将每个三维对象作为超图的一个顶点，而获得的每个视图集合作为该超图的一个超边，用来连接超图的顶点，从而形成多个超图。
[0032] 在本发明的具体实施例中，如：G1＝(V1，E1，w1)，G2＝(V2，E2，w2)，...Gκ＝(Vκ，Eκ，wκ)用来表示获得的K个超图，其中，在具体实施例中，K值可以取大于1的正整数。根据本发明的具体实例，针对超图的定义，H1，H2，L Hκ，用来表示G1＝(V1，E1，w1)，G2＝(V2，E2，w2)，...Gκ＝(Vκ，Eκ，wκ)超图的相关性矩阵，Dv1，Dv2，L Dvκ用来表示上述超图的顶点度矩阵，而De1，De2，L Deκ用来表示上述超图的边度矩阵。
[0033] 其中，H矩阵(以Hi为例)的建立方法如下：
[0034]
[0035] 其中，根据上述公式可知，当一个顶点属于一个超边时，H矩阵对应位置为1，否则对应位置为0。
[0036] 根据本发明的实施例，另外两个矩阵的建立方法如下：
[0037] d(vi)＝∑e∈Eh(vi，e)；
[0038]
[0039] 步骤S103，对所述多个超图进行融合以形成一个融合后的超图，并对所述融合后的超图进行分析，且根据分析结果建立所述三维对象之间的关联性。
[0040] 具体地，首先对获得的所有超图进行融合，形成一个融合后的超图。进一步说，首先将所有的超图进行平均融合，也就是说每个超图都有相同的权重，然后应用设置的目标函数对超图上的各节点之间的标签进行分析，从而获得数据库中任意三维对象之间的关联性。在本发明的实施例中，该三维对象检索方法要求有更多相关性的顶点具有相似的标签。
[0041] 在本发明的具体实施例中，令标签的向量为f，定义融合后的超图上的目标函数为： 其中
[0042]
[0043]
[0044]
[0045]
[0046]
[0047] 其中， 令 其中T
由此。可以获得Ω(f)＝fΔf。
由此。可以获得Ω(f)＝fΔf。
[0048] Remp(f)为经验风险，对其做如下定义：
[0049]
[0050] 其中，y为已有的标签向量，而f为优化的标签向量。
[0051] 因此，该超图上分析为优化以下的式子：
[0052] Φ(f)＝fTΔf+λ||f-y||2，其中λ＞0。
[0053] 通过运算，可以得到以下的结果：
[0054]
[0055] 从结果可以看出，在给定一个用于检索的三维对象，将y中对应元素设置为1，其他元素设置为0。最终获得f作为数据库中其他三维对象与该检索对象的相关性，用于检索。
[0056] 步骤S104，根据所述关联性检索所述三维对象。
[0057] 为了对本发明的方法有更加清楚的理解，以下就结合具体实例对本发明的检索方法进行详细描述。
[0058] 【实施例】
[0059] 本实施例为选择National Taiwan University的基于图像集合的3D对象数据库，每个对象由20张图像表示，一共选取了500个对象作为实验数据库。在试验中，分别将每个对象作为待检索对象，进行检索，并分析最后的综合检索效果。
[0060] 首先，采用Zernike Moments作为3D对象数据库中三维对象视图的图像特征，根据特征提取算法对视图进行Zernike Moments特征提取，从而得到所有视图的特征提取结果，接着，使用获得的Zernike Moments特征提取结果，并且采用欧式距离作为计算距离，对视图应用距离计算方法计算任意两个视图之间的距离，从而计算得到任意两个视图之间的距离值。同样地，对于所有视图，采用此距离计算方法对所有视图之间的距离计算完毕，从而获得所有视图之间的距离矩阵。
[0061] 然后，使用K均值聚类方法对所有试图进行聚类，其中通过设定不同的K值，生成不同的聚类结果。在本实例中，K分别取值为50、100、200、400、600、1000、1500、2000和3000。并且在每组聚类结果的基础上，将每个对象作为超图的一个顶点，而获得的每个视图集合作为该超图的一个超边，用来连接超图的顶点，从而形成多个超图。这里G1＝(V1，E1，w1)，G2＝(V2，E2，w2)，...Gκ＝(Vκ，Eκ，wκ)用来表示获得的κ个超图。针对超图的定义，H1，H2，L Hκ，Dv1，Dv2，L Dvκ，...De1，De2，L Deκ用来表示这些超图的相关性矩阵、顶点度矩阵和边度矩阵。
[0062] 其中，H矩阵(以Hi为例)的建立方法如下：
[0063] 其中，e∈Ei。
[0064] 其中，根据上述公式可知，当一个顶点属于一个超边时，H矩阵对应位置为1，否则对应位置为0。
[0065] 根据本发明的实施例，另外两个矩阵的建立方法如下：
[0066] d(vi)＝∑e∈Eh(vi，e)；
[0067]
[0068] 最后，对获得的所有超图进行融合，形成一个融合后的超图。进一步说，首先将所有的超图进行平均融合，也就是说每个超图都有相同的权重，然后应用设置的目标函数对超图上的各节点之间的标签进行分析，从而获得数据库中任意三维对象之间的关联性。在本发明的实施例中，该三维对象检索方法要求有更多相关性的顶点具有相似的标签。
[0069] 具体的步骤结合公式进行说明：
[0070] 令 标 签 的 向 量 为f，定 义 融 合 后 的 超 图 上 的 目 标 函 数 为：其中
[0071]
[0072]
[0073]
[0074]
[0075]
[0076] 其中， 令 其中T
由此。我们可以获得Ω(f)＝fΔf。
由此。我们可以获得Ω(f)＝fΔf。
[0077] Remp(f)为经验风险，对其做如下定义：
[0078]
[0079] 其中，y为已有的标签向量，而f为优化的标签向量。
[0080] 因此，该超图上分析为优化以下的式子：
[0081] Φ(f)＝fTΔf+λ||f-y||2，其中λ＞0。
[0082] 通过运算，可以得到以下的结果：
[0083]
[0084] 从结果可以看出，在给定一个用于检索的三维对象，将y中对应元素设置为1，其他元素设置为0。最终获得f作为数据库中其他三维对象与该检索对象的相关性，用于检索。
[0085] 本实施例的三维对象检索结果如图2所示，为应用本发明实施例的方法检索结果与其他三种检索方法的检索结果的对比图。图2中给出了查全率-查准率曲线，第一种方法203计算两组三维对象视图中的Hausdorff距离(HAUS)，第二种方法204计算两组视图中所有图像距离和的均值(MEAN)，第三种方法202首先计算检索对象的每个视图与另一个对象的各个视图中的最小距离，再对所有距离求和(SumMin)。而本发明实施例的检索方法201(Hypergraph)在三维对象的检索效果上，与传统方法相比能取得更好的效果。
[0086] 在本发明的实施例中，还提出了一种基于超图的三维对象检索装置，如图3所示，为本发明实施例的基于超图的三维对象检索装置的结构图。该基于超图的三维对象检索装置300包括距离矩阵计算模块310、超图构建模块320、关联模块330和检索模块340。其中，距离矩阵计算模块310用于计算数据库中三维对象的所有视图之间的距离矩阵；超图构建模块320用于根据所述距离矩阵对所述所有视图进行聚类以得到多个聚类结果，并根据所述多个聚类结果构建所述三维对象对应的多个超图；关联模块330，用于对所述多个超图进行融合以形成一个融合后的超图，并对所述融合后的超图进行分析，且根据分析结果建立所述三维对象之间的关联性；检索模块340用于根据所述关联性检索所述三维对象。
[0087] 进一步，超图构建模块320包括聚类模块321和构建模块322。其中，聚类模块321用于采用K均值聚类方法对所述所有视图进行聚类，其中，所述聚类结果根据所述K值的不同而变化；构建模块322用于以所述三维对象的相应视图集合为所述超图的超边，连接以每个所述三维对象为相应超图的顶点，以形成多个超图。
[0088] 关联模块330包括融合模块331和关联建立模块332。其中，融合模块331用于对所述多个超图进行平均融合，以形成一个融合后的超图；关联建立模块332用于根据预设的目标函数对所述融合后的超图的顶点之间的标签进行分析，以获得数据库中任意三维对象之间的关联性，其中，满足关联性要求的所述顶点具有相似的标签。
[0089] 通过本发明提出的基于超图的三维对象检索方法和装置，能够改变传统的直接基于视图匹配的三维对象相关性方法，通过底层视图的相关性，应用超图进行建模，并进一步应用超图上的学习获得三维对象的较高层次的相关性。并且该方法能够有效的避免以下两种问题，第一类问题是当同类三维对象之间只有少数视图相似时，应用基于视图的直接匹配的方法会产生错误的结果，第二类问题是当两个非同类对象之间有个别图像非常相似时会产生错误的结果。当然，该方法可以更有效的进行三维对象的关联性分析，从而获得更好的检索结果。另外，本发明提出的方法设计简单，易于实现。
[0090] 尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由所附权利要求及其等同限定。