基于统计学的三维模型检索算法
|
摘要
三维模型在虚拟手术、分子生物、文物保护、计算机辅助设计等众多领域都扮演着非常重要的角色。上个世纪90年代以来,随着这些领域的快速发展以及网络三维模型海量数据库的扩充和三维物体扫描技术的成熟,导致了三维模型数量的急剧增加,人们迫切需要从众多的三维模型中准确地找到自己所需要的模型,因此三维模型检索越来越受到研究人员的重视。本文在对前人关于三维模型检索的工作进行系统研究的基础之上,提出了两种新的基于统计学的三维模型检索算法。本文所做的工作如下:
(1)总结与分析了三维模型检索的研究现状、相关技术。
(2)实现了两个前人的基于统计学的三维模型检索算法:Osada提出的形状分布的检索算法和Ankerst提出的对模型切分后生成直方图的检索算法。
(3)提出了一种新的基于统计学的三维模型检索算法:基于相对角度直方图匹配的检索算法。该算法仅仅通过统计模型表面点上每一个点与其他所有点之间的角度关系作为模型的特征量用于模型的检索,不需要考虑模型三角面片的相关信息。
(4)由于相对角度直方图需要考虑模型上每一个点与其他所有点之间的角度关系,导致了每一个模型所形成的直方图的维数较大,所以基于降维的考虑又提出了一种基于聚类分析的检索算法。该算法大大的降低了模型的特征量维数,从而降低了算法的时间复杂度,加快了模型检索的速度。
(5)总结了算法性能评价的相关标准,并且从实验结果与算法性能来看,本文提出的两种三维模型的检索算法对于大多数模型来说在检索效果与算法性能上都比Osada提出的形状分布的检索算法和Ankerst提出的对模型切分后生成直方图的检索算法要好。
3D model retrieval plays a very important role in so many fields such as virtual surgery, molecular biology, heritage protection, computer aided design. Since the 90's, with the rapid development of these fields as well as the expansion of massive database of web 3D model and the scanning technology maturity of three-dimensional objects, the quantities of 3D models are sharply increased, it's urgent need for people to accurately find their own required model from a large number of 3D models. So 3D model retrieval becomes more and more importance to researchers. Based on the systematic study about the previous work of 3D model retrieval, this paper presents two new kinds of 3D model retrieval algorithm based on statistics. The work done of this paper is as follows:
(1) The 3D model retrieval's research status and related technologies are summarized and analyzed.
(2) Two previous 3D model retrieval algorithms based on statistics are realized: the algorithm of shape distribution which was presented by Osada and the algorithm of the model cutting generated histogram which was presented by Ankerst.
(3) A new 3D model retrieval algorithm based on statistics is presented: the retrieval algorithm based on the relative angle histogram matching. The algorithm simply need to statistic the angle's relationship of each model point of model's surface point with all other points as model's features for the model retrieval, it needs not to consider the model's related information of triangle.
(4) A new retrieval algorithm of cluster analysis based on dimension reduction in this paper is presented as the histogram of relative angle needs to considerate angle's relation of all points, which has lead to large dimension of histogram generated for each model. This algorithm greatly reduces the characteristic index dimension of model, thus reducing algorithm time complexity and accelerating the speed of model retrieval.
(5) The relevant standards of the algorithm performance evaluation are concluded, and from the experimental results and the algorithm performance, two kinds of 3D model retrieval algorithm which are presented by this paper have better than the algorithm of shape distribution which was presented by Osada and the algorithm of the model cutting generated histogram which was presented by Ankerstfor the most models.
(1)总结与分析了三维模型检索的研究现状、相关技术。
(2)实现了两个前人的基于统计学的三维模型检索算法:Osada提出的形状分布的检索算法和Ankerst提出的对模型切分后生成直方图的检索算法。
(3)提出了一种新的基于统计学的三维模型检索算法:基于相对角度直方图匹配的检索算法。该算法仅仅通过统计模型表面点上每一个点与其他所有点之间的角度关系作为模型的特征量用于模型的检索,不需要考虑模型三角面片的相关信息。
(4)由于相对角度直方图需要考虑模型上每一个点与其他所有点之间的角度关系,导致了每一个模型所形成的直方图的维数较大,所以基于降维的考虑又提出了一种基于聚类分析的检索算法。该算法大大的降低了模型的特征量维数,从而降低了算法的时间复杂度,加快了模型检索的速度。
(5)总结了算法性能评价的相关标准,并且从实验结果与算法性能来看,本文提出的两种三维模型的检索算法对于大多数模型来说在检索效果与算法性能上都比Osada提出的形状分布的检索算法和Ankerst提出的对模型切分后生成直方图的检索算法要好。
3D model retrieval plays a very important role in so many fields such as virtual surgery, molecular biology, heritage protection, computer aided design. Since the 90's, with the rapid development of these fields as well as the expansion of massive database of web 3D model and the scanning technology maturity of three-dimensional objects, the quantities of 3D models are sharply increased, it's urgent need for people to accurately find their own required model from a large number of 3D models. So 3D model retrieval becomes more and more importance to researchers. Based on the systematic study about the previous work of 3D model retrieval, this paper presents two new kinds of 3D model retrieval algorithm based on statistics. The work done of this paper is as follows:
(1) The 3D model retrieval's research status and related technologies are summarized and analyzed.
(2) Two previous 3D model retrieval algorithms based on statistics are realized: the algorithm of shape distribution which was presented by Osada and the algorithm of the model cutting generated histogram which was presented by Ankerst.
(3) A new 3D model retrieval algorithm based on statistics is presented: the retrieval algorithm based on the relative angle histogram matching. The algorithm simply need to statistic the angle's relationship of each model point of model's surface point with all other points as model's features for the model retrieval, it needs not to consider the model's related information of triangle.
(4) A new retrieval algorithm of cluster analysis based on dimension reduction in this paper is presented as the histogram of relative angle needs to considerate angle's relation of all points, which has lead to large dimension of histogram generated for each model. This algorithm greatly reduces the characteristic index dimension of model, thus reducing algorithm time complexity and accelerating the speed of model retrieval.
(5) The relevant standards of the algorithm performance evaluation are concluded, and from the experimental results and the algorithm performance, two kinds of 3D model retrieval algorithm which are presented by this paper have better than the algorithm of shape distribution which was presented by Osada and the algorithm of the model cutting generated histogram which was presented by Ankerstfor the most models.
引文
[1]Paquet Eric,Rioux Marc.A query by content software for three-dimensional databases management[A].Proceedings of International Conference on Recent Advances in 3D Digital Imaging and Modeling[C].Ottawa,Canada,1997:345-352
[2]Paquet.Eric,Rioux Marc.A content based search engine for VRML databases[A].Proceedings of the 1998 computer Society Conference on Computer Vision and Pattern Recognition(CVPR)[C].Santa Barbara,CA,1998:541-646
[3]杨育彬,林珲,朱庆.基于内容的三维模型检索综述[J].计算机学报,2004,27(10):1297-1310
[4]Min P.,Halderman A.,Kazhdan M.,et al.Early experiences with a 3d model search engine[A].Proceedings of Web 3D Symposium[C].Saint Malo,France,2003:7-18
[5]Thomas Funkhouser,Patrick Min,Michael Kazhdan,et al.A search engine for 3D models[J].ACM Transactions on Graphics,2003,V22(1):83-105
[6]Thomas Funkhouser,Patrick Min,Michael Kazhdan,et al.Shape-based retrieval analysis of 3d model[J].Communications of the ACM,2005,V48(6):60-63
[7]Osada R.,Funkhouser T.,Chazelle B.,et al.Matching 3D models with shape distributions[A].International Conference on Shape Modeling and Applications[C].Genova,Italy,2001:154-166
[8]Osada R.,Funkhouder T.,Chazelle B.,et al.Shape distributions[J].ACM Transactions on Graphics,2002,V21(4)(Oct.):807-832
[9]Chen D.Y.,Tian X.P.,Shen Y.T.,et al.On visual similarity based 3D model retrieval[J].Comput Graph Forum(EG 2003 Proceedings),2003,V22(3):223-232
[10]Kolonias I.,Tzovaras D.,Malassiotis S.,et al.Content-based similarity search of VRML models using shape descriptors[A].Proceedings of the International Workshop on Content-Based Multimedia Indexing(Sept.)[C].Brescia,Italy,2001:19-21
[11]Ohbuchi R.,Minamitani T.,Takei T..Shape similarity search of 3D models by using enhanced shape functions[A]. Proceedings of the Theory and Practice of Computer Graphics 2003[C]. Washington, USA, 2003: 97-104
[12] Ohbuchi R., Nakazawa M., Takei T.. Retrieving 3D shapes based on their appearance [A].Proceedings of MIR'03 (Nov.)[C]. Berkeley, CA, 2003: 39-46
[13] Mihael Ankerst, Gabi Kastenmüller, Hans-Peter Kriegel, et al. 3D Shape Histograms for Similarity Search and Classification in Spatial Databases[A]. Proceedings of the 6th International Symposium on Advances in Spatial Databases[C]. Hong Kong, China, 1999:207-226
[14] Laga H., Nakajima M.. A Boosting Approach to Content-based 3D Model Retrieval[A].Graphite(2007)[C]. Perth, Western Australia, 2007: 227-234
[15] Paquest E., Rioux M., Nefertiti. A query by content system for three-dimensional and image databases management[J]. Image Vision Computing, 1999, V17(2): 157-166
[16] Feng Jun , Horace H S Ip. Robust Point Correspondence Matching and Similarity Measuring for 3D Models by Relative Angle-Context Distributions[J]. Image and Vision Computing, 2007, V26(6): 761-775
[17] Ohbuchi R., Otagiri T., Ibato M., et al. Shape-similarity search of three-dimensional models using parameterized statistics [A]. Proceedings of Pacific Conference on Computer Graphics and Applications[C]. Beijing, China, 2002: 265-275
[18] Zhang C., Chen T.. An active learning framework for content based information retrieval [J]. IEEE Transactions on Multimedia Special Issue on Multimedia Database, 2002, V4(2):260-280
[19] Vranic D., Saupe D.. 3d model retrieval [A]. Proceedings of Spring Conference on Computer Graphics[C]. Budmerice, Slovakia, 2000: 89-93
[20] Vranic D., Saupe D., Richter J.. Tools for 3d -object retrieval: Karhunen-Loeve transform and spherical harmonics[A]. Proceedings of IEEE Workshop on Multimedia Signal Processing[C]. Cannes, France, 2001: 293-298
[21]Regli W.,Cicirello V..Managing digital libraries for computeraided design[J].Computer Aided Design,2000,V32(2):110-132
[22]Ankerst M.,Kastenmuller G.,Kriegel H.,et al.Nearest neighbour classification in 3d protein databases[A].Proceedings of International Conference on Intelligent Systems for Molecular Biology[C].Heidelberg,Germany,1999:34-43
[23]Amenta N.,Choi S.,Kolluri R.K..The power crust,union of balls,and the medial axis.transform[J].Computational Geometry:Theory and Applications,2002,V19:127-153
[24]Amenta N.,Choi S.,Kolluri R.K..The power crust[A].Proceedings of the 6~(th) ACM Symposium on Solid Modeling[C].Ann Arbor,Michigan,2001:249-260
[25]Sundar H.,Silver D.,Gagvani N.,et al.Skeleton based shape matching and retrieval[A].Proceedings of SMI 2003:International Conference on Shape Modeling and Applications[C].Seoul,South Korea,2003:130-139
[26]Gagvani N.Parameter controlled volume thinning[J].Graphical Models and Image Processing,1999,V61(3):149-164
[27]Novotni M.,Klein R..A geometric approach to 3D object comparison[A].Proceedings of the 1st International Conference on Shape Modeling and Applications[C].Genova,2001:167-175
[28]Novotni M.,Klein R.1..Geometric 3D comparisonan application[A].Proceedings of ECDL WS Generalized Documents 2001[C].Bonn,2001:39-44
[29]Endo S.,Baba T.,Shiitani S.,et al.Shape based 3D model retrieval without query[A].Conference On Image And Video Retrieval[C].Amsterdam,The Netherlands,2007:218-225
[30]郑伯川,彭维,张引,等.3D模型检索技术综述[J].计算机辅助设计与图形学学报,2004,16(7):873-881
[31]李庆,周曼丽,柳建.三维物体识别研究进展[J].中国图像图形学报,2000,5A(12):985-993
[32]崔晨旸,石教英.三维模型检索中的特征提取技术综述[J].计算机辅助设计与图形 学学报,2004,16(7):882-889
[33]韦娜,耿国华,周明全.基于内容的图像检索系统性能评价[J].中国图像图形学报,2004,9(11):1271-1276
[34]耿国华.数据结构——C语言描述[M].北京:高等教育出版社,2005:1-28
[35]周继来.三维模型检索技术研究及系统实现[D].西安:西北大学,2005
[36]郭竞.三维地形模型检索系统设计与实现[D].西安:西北大学,2007
[37]门秀萍.基于内容的三维模型检索[D].北京:中国石油大学,2007
[38]刘晓静.基于内容的三维模型检索方法研究与实现[D].西安:西北大学,2008
[39]崔妍.基于聚类技术的三维模型库索引的研究[D].吉林:吉林大学,2007
[40]程毛林.Matlab软件在多元统计分析中的应用[J].数理统计与管理,2008,27(2):279-284
[41]陈仲生.基于Matlab7.0的统计信息处理[M].湖南:湖南科学技术出版社,2005:159-167
[42]刘全.统计数据处理概论[M].北京:中国统计出版社,2008:144-152
[43]余锦华,杨维权.多元统计分析与应用[M].广州:中山大学出版社,2005:162-187
[44]张尧庭,方开泰.多元统计分析引论[M].北京:科学出版社,1999:393-457
[45]高惠璇.应用多元统计分析[M].北京:北京大学出版社,2005:216-262
[46]范金城,梅长林.数据分析[M].北京:科学出版社,2002:205-241
[2]Paquet.Eric,Rioux Marc.A content based search engine for VRML databases[A].Proceedings of the 1998 computer Society Conference on Computer Vision and Pattern Recognition(CVPR)[C].Santa Barbara,CA,1998:541-646
[3]杨育彬,林珲,朱庆.基于内容的三维模型检索综述[J].计算机学报,2004,27(10):1297-1310
[4]Min P.,Halderman A.,Kazhdan M.,et al.Early experiences with a 3d model search engine[A].Proceedings of Web 3D Symposium[C].Saint Malo,France,2003:7-18
[5]Thomas Funkhouser,Patrick Min,Michael Kazhdan,et al.A search engine for 3D models[J].ACM Transactions on Graphics,2003,V22(1):83-105
[6]Thomas Funkhouser,Patrick Min,Michael Kazhdan,et al.Shape-based retrieval analysis of 3d model[J].Communications of the ACM,2005,V48(6):60-63
[7]Osada R.,Funkhouser T.,Chazelle B.,et al.Matching 3D models with shape distributions[A].International Conference on Shape Modeling and Applications[C].Genova,Italy,2001:154-166
[8]Osada R.,Funkhouder T.,Chazelle B.,et al.Shape distributions[J].ACM Transactions on Graphics,2002,V21(4)(Oct.):807-832
[9]Chen D.Y.,Tian X.P.,Shen Y.T.,et al.On visual similarity based 3D model retrieval[J].Comput Graph Forum(EG 2003 Proceedings),2003,V22(3):223-232
[10]Kolonias I.,Tzovaras D.,Malassiotis S.,et al.Content-based similarity search of VRML models using shape descriptors[A].Proceedings of the International Workshop on Content-Based Multimedia Indexing(Sept.)[C].Brescia,Italy,2001:19-21
[11]Ohbuchi R.,Minamitani T.,Takei T..Shape similarity search of 3D models by using enhanced shape functions[A]. Proceedings of the Theory and Practice of Computer Graphics 2003[C]. Washington, USA, 2003: 97-104
[12] Ohbuchi R., Nakazawa M., Takei T.. Retrieving 3D shapes based on their appearance [A].Proceedings of MIR'03 (Nov.)[C]. Berkeley, CA, 2003: 39-46
[13] Mihael Ankerst, Gabi Kastenmüller, Hans-Peter Kriegel, et al. 3D Shape Histograms for Similarity Search and Classification in Spatial Databases[A]. Proceedings of the 6th International Symposium on Advances in Spatial Databases[C]. Hong Kong, China, 1999:207-226
[14] Laga H., Nakajima M.. A Boosting Approach to Content-based 3D Model Retrieval[A].Graphite(2007)[C]. Perth, Western Australia, 2007: 227-234
[15] Paquest E., Rioux M., Nefertiti. A query by content system for three-dimensional and image databases management[J]. Image Vision Computing, 1999, V17(2): 157-166
[16] Feng Jun , Horace H S Ip. Robust Point Correspondence Matching and Similarity Measuring for 3D Models by Relative Angle-Context Distributions[J]. Image and Vision Computing, 2007, V26(6): 761-775
[17] Ohbuchi R., Otagiri T., Ibato M., et al. Shape-similarity search of three-dimensional models using parameterized statistics [A]. Proceedings of Pacific Conference on Computer Graphics and Applications[C]. Beijing, China, 2002: 265-275
[18] Zhang C., Chen T.. An active learning framework for content based information retrieval [J]. IEEE Transactions on Multimedia Special Issue on Multimedia Database, 2002, V4(2):260-280
[19] Vranic D., Saupe D.. 3d model retrieval [A]. Proceedings of Spring Conference on Computer Graphics[C]. Budmerice, Slovakia, 2000: 89-93
[20] Vranic D., Saupe D., Richter J.. Tools for 3d -object retrieval: Karhunen-Loeve transform and spherical harmonics[A]. Proceedings of IEEE Workshop on Multimedia Signal Processing[C]. Cannes, France, 2001: 293-298
[21]Regli W.,Cicirello V..Managing digital libraries for computeraided design[J].Computer Aided Design,2000,V32(2):110-132
[22]Ankerst M.,Kastenmuller G.,Kriegel H.,et al.Nearest neighbour classification in 3d protein databases[A].Proceedings of International Conference on Intelligent Systems for Molecular Biology[C].Heidelberg,Germany,1999:34-43
[23]Amenta N.,Choi S.,Kolluri R.K..The power crust,union of balls,and the medial axis.transform[J].Computational Geometry:Theory and Applications,2002,V19:127-153
[24]Amenta N.,Choi S.,Kolluri R.K..The power crust[A].Proceedings of the 6~(th) ACM Symposium on Solid Modeling[C].Ann Arbor,Michigan,2001:249-260
[25]Sundar H.,Silver D.,Gagvani N.,et al.Skeleton based shape matching and retrieval[A].Proceedings of SMI 2003:International Conference on Shape Modeling and Applications[C].Seoul,South Korea,2003:130-139
[26]Gagvani N.Parameter controlled volume thinning[J].Graphical Models and Image Processing,1999,V61(3):149-164
[27]Novotni M.,Klein R..A geometric approach to 3D object comparison[A].Proceedings of the 1st International Conference on Shape Modeling and Applications[C].Genova,2001:167-175
[28]Novotni M.,Klein R.1..Geometric 3D comparisonan application[A].Proceedings of ECDL WS Generalized Documents 2001[C].Bonn,2001:39-44
[29]Endo S.,Baba T.,Shiitani S.,et al.Shape based 3D model retrieval without query[A].Conference On Image And Video Retrieval[C].Amsterdam,The Netherlands,2007:218-225
[30]郑伯川,彭维,张引,等.3D模型检索技术综述[J].计算机辅助设计与图形学学报,2004,16(7):873-881
[31]李庆,周曼丽,柳建.三维物体识别研究进展[J].中国图像图形学报,2000,5A(12):985-993
[32]崔晨旸,石教英.三维模型检索中的特征提取技术综述[J].计算机辅助设计与图形 学学报,2004,16(7):882-889
[33]韦娜,耿国华,周明全.基于内容的图像检索系统性能评价[J].中国图像图形学报,2004,9(11):1271-1276
[34]耿国华.数据结构——C语言描述[M].北京:高等教育出版社,2005:1-28
[35]周继来.三维模型检索技术研究及系统实现[D].西安:西北大学,2005
[36]郭竞.三维地形模型检索系统设计与实现[D].西安:西北大学,2007
[37]门秀萍.基于内容的三维模型检索[D].北京:中国石油大学,2007
[38]刘晓静.基于内容的三维模型检索方法研究与实现[D].西安:西北大学,2008
[39]崔妍.基于聚类技术的三维模型库索引的研究[D].吉林:吉林大学,2007
[40]程毛林.Matlab软件在多元统计分析中的应用[J].数理统计与管理,2008,27(2):279-284
[41]陈仲生.基于Matlab7.0的统计信息处理[M].湖南:湖南科学技术出版社,2005:159-167
[42]刘全.统计数据处理概论[M].北京:中国统计出版社,2008:144-152
[43]余锦华,杨维权.多元统计分析与应用[M].广州:中山大学出版社,2005:162-187
[44]张尧庭,方开泰.多元统计分析引论[M].北京:科学出版社,1999:393-457
[45]高惠璇.应用多元统计分析[M].北京:北京大学出版社,2005:216-262
[46]范金城,梅长林.数据分析[M].北京:科学出版社,2002:205-241