二维碎片拼合技术研究
|
摘要
碎片拼合就是要把大量的不规则的碎片重新拼接成初始的完整模型。这一问题在飞行器的失事分析、考古、古生物学以及壁画保存等方面具有广泛的应用。要从成千上万的碎片中找到相互邻接的碎片，并最终拼接成完整的模型，没有计算机的辅助是很难实现的。本文研究二维碎片的BMP图片轮廓特征提取技术，并对这些特征进行简化、分析，然后设计了碎片拼合算法，主要的研究工作如下：
● 研究了碎片的数据采样。在分析碎片BMP图像的基础上，给出“栅格逆时针运动”算法获取碎片轮廓采样点。
● 研究了采样点的几何滤波(均值滤波、中值滤波和高斯滤波)和重新采样方法，得到了方便拼合的碎片数字化模型。
● 基于ACIS平台，对采样点进行B样条曲线拟合，并获得各采样点的匹配特征—曲率。
● 用动态规划(Dynamic Programming)算法找出两轮廓的匹配点序列，实现两碎片的拼合。
Reassembling unknowing broken objects from a large collection of irregular fragments arises in several contexts such as archaeology, failure analysis, paleontology, conservation(mural painting), and so on. It is impossible if there are no computers to assist in reassembling these tens of thousands of randomly shaped and featureless fragments. In this thesis, the extraction of contour feature is researched from the BMP images of 2D fragments. These features are analyzed and predigested. And the reassembling algorithm of fragments is designed. In brief, the primary contents are as follows:
Sample point data are obtained from fragment images with grid in counterclockwise sense algorithm given in this thesis.
Sample point data are filtered with geometric filtering(median filtering, mean filtering and Gaussian filtering) and predigested.
B-Spline curve fitting and curvature analysis are discussed in detail and are implemented with ACIS.
Matching point sequences are obtained on the basis of curvature analysis by applying the dynamic programming algorithm.
● 研究了碎片的数据采样。在分析碎片BMP图像的基础上，给出“栅格逆时针运动”算法获取碎片轮廓采样点。
● 研究了采样点的几何滤波(均值滤波、中值滤波和高斯滤波)和重新采样方法，得到了方便拼合的碎片数字化模型。
● 基于ACIS平台，对采样点进行B样条曲线拟合，并获得各采样点的匹配特征—曲率。
● 用动态规划(Dynamic Programming)算法找出两轮廓的匹配点序列，实现两碎片的拼合。
Reassembling unknowing broken objects from a large collection of irregular fragments arises in several contexts such as archaeology, failure analysis, paleontology, conservation(mural painting), and so on. It is impossible if there are no computers to assist in reassembling these tens of thousands of randomly shaped and featureless fragments. In this thesis, the extraction of contour feature is researched from the BMP images of 2D fragments. These features are analyzed and predigested. And the reassembling algorithm of fragments is designed. In brief, the primary contents are as follows:
Sample point data are obtained from fragment images with grid in counterclockwise sense algorithm given in this thesis.
Sample point data are filtered with geometric filtering(median filtering, mean filtering and Gaussian filtering) and predigested.
B-Spline curve fitting and curvature analysis are discussed in detail and are implemented with ACIS.
Matching point sequences are obtained on the basis of curvature analysis by applying the dynamic programming algorithm.
引文
[1] Weixin Kong. Benjamin. B. Kimia On Solving 2D and 3D Puzzles Using Curve Matching. IEEE Computer Vision and Pattern Recognition, 2001.
[2] Lai, J.Y., et al. Registration and data merging for multiple sets of scan data.Advanced Manufacturing Technology, 1999
[3] Pulli K. Multiview registration for large data sets. In:Proc. 2nd Int. Conf on 3D Digital Imaging and Modeling, 1999.
[4] Levoy M. Digitizing the Forrna Urbis Romae. Siggraph Digital Campfire on Computers and ArcheoIogy, 2001.
[5] Bonet J. S. et al. Structure-driven SAR image registration. Proceedings of SPIE 1998.
[6] Bonet J. S. et aL Structure driven image database retrieval. Advances in Neural Information Processing, Vol.10, 1997
[7] Yang C. et al. Image Database retrieval with multiple-instance learning techniques. Proceedings of the 16th International Conference on Data Engineering.2001
[8] Rowe,J. et al. A 3D digital library system: capture, analysis, query, anddisplay.http://3dk.asu.edu/DOCUMENT/archives/publication/g3dk,/3d_digLib.pdf
[9] Napoli L.D. et al. A semi-automatic procedure for the recognition and classification of pieces of archaeological artifacts. XII ADM international conference, Rimini, Italy, Sept. 2001
[10] Ankerst M, et al. 3D Shape Histograms for Similarity Search and Classification in Spatial Databases. Proc. 6th International Symposium on Spatial Databases,Hong Kong, 1999
[11] Kriegel H.-P, et al. Approximation-based Similarity Search for 3D Surface Segments, in: GeoInformatica Joumal, Vol. 2, No. 2, 1998.
[12] Osada, R. et al., Matching 3D Models with Shape Distributions. International Conference on Shape Modeling and Applications,2001.
[13] Tamas Varady, Ralph Martin,Jordan Cox. Reverse engineering of geometric models—an introduction. Computer Aided Design, 1997,29(4):253-268
[14] Huang MC, Tai CC. The Pre-processing of data points for curve fitting in
reverse engineering.International Journal of Advanced Manufacturing Technology.2000,16(9):635-642
[15] AC, Chan CF. Point-data processing and error analysis in reverse engineering.International Journal of Advanced Manufacturing Technology,1998,14(11):824-834
[16] Helena Cristina da, Gama Leitao. A Multi-Scale Method for the Re-Assembly of Fragmented Objects.2000.
[17] Farzin Mokhtarian and Alan K. Mackworth. A Theory of Multiscale,Curvature-Based Shape Representation for Planar Curves. on Pattern Analysis and Mach. Intel 1. 14 (8), 789--805(1992).
[18] 求是科技 张宏林编著．Visual C++数字图像模式识别技术及工程实践．人民邮电出版社2003．2 233-255
[19] 刘炉山．基于数字化样条的虚拟测量及数据技术．南京航空航天大学硕士学位论文．2002
[20] 施法中 计算机辅助几何设计与非均匀有理B样条(CAD&NURBS) 北京航空航空大学出版社1994
[21] 蔡炜斌，逆向工程中基于轮廓数据的曲面重构[学位论文]，南京，南京航空航天大学硕士学位论文，2001
[22] 孙家广，杨长贵，计算机图形学，北京：清华大学出版社，1994
[23] W. Schroeder, K. Marin and B. Lorensen, The Visualization Toolkit: An Object-Oriented Approach to 3D Graphics, Prentice Hall,1997.
[24] M. Sonka, V. Hlavac and R. Boyle, Image Processing, Analysis and Machine Vision, PWS,1999.
[25] Haim J.Wolfson. On curve matching. IEEE Transactions on Pattern Analysis and Machine Intelligence. 12(5):483-488,1990
[26] Paul Rosin and Svetha Venkatesh. Extracting natural scales using the Fourier description. Pattern Recognition ,26(9):1383-1393,1993.
[27] F.Boussofiane and G.Bertrand. Anew method for recognizing and locating objects by searching longest paths.IEEE Transactions on Patern Analysis and Machine Intellignce.,26(12):445-448,1993.
[28] H. Freeman and L. Garder. Apictorial jigsaw puzzles: the computer solution of a problem in pattern recognition.IEEE Trans. Elec. Comp.,13:118-127, 1964.
[29] G. M. Radack and N. I. Badler. Jigsaw puzzle matching using a boundary-centered polar encoding. CGIP, 19:1-17, 1982.
[30] H.Wolfson, A. Kalvin, E. Schonberg and Y. Lambdan. Solving jigsaw puzzles by computer. Annales of Operations Research,12:51-64, 1988.
[31] Farzin Moldhtarian and Alan K.Mackworth A theory of multiscale curvature-based shape representation for planar curves. IEEE Trans. PAMI, 14:789-805, 1992.
[32] 《运筹学》教材编写组．运筹学(第2版)[M]．北京：清华大学出版社，1990．194-253．
[33] 戴华 矩阵论(第一版)[M]．北京科学出版社，2001．169-175
[34] Helena Cristina da Gama Leito, Jorge Stolfi A Multi-Scale Method for the Re-Assembly of Fragmented Objects. IEEE Transactions on Pattern Analysis and Machine Intelligence(TPAMI), vol. 24, no. 9, 1239-1251. September 2002.
[35] http ://jwc.seu.edu.cn/xuyue/w104/s6.6/importent/zhangl/pinpu/pinpu.htm
[36] Helena Cristina da Gama Leitao and Jorge Stolfi. Geometric Curve filtering.Technical report. 1998
[37] Ronald N.Brancewell. The Fourier Transform and its Application.McGraw-Hill, 1986.
[38] (英)C．查特非尔德．时间序列分析导论．宇航出版社．1986．
[2] Lai, J.Y., et al. Registration and data merging for multiple sets of scan data.Advanced Manufacturing Technology, 1999
[3] Pulli K. Multiview registration for large data sets. In:Proc. 2nd Int. Conf on 3D Digital Imaging and Modeling, 1999.
[4] Levoy M. Digitizing the Forrna Urbis Romae. Siggraph Digital Campfire on Computers and ArcheoIogy, 2001.
[5] Bonet J. S. et al. Structure-driven SAR image registration. Proceedings of SPIE 1998.
[6] Bonet J. S. et aL Structure driven image database retrieval. Advances in Neural Information Processing, Vol.10, 1997
[7] Yang C. et al. Image Database retrieval with multiple-instance learning techniques. Proceedings of the 16th International Conference on Data Engineering.2001
[8] Rowe,J. et al. A 3D digital library system: capture, analysis, query, anddisplay.http://3dk.asu.edu/DOCUMENT/archives/publication/g3dk,/3d_digLib.pdf
[9] Napoli L.D. et al. A semi-automatic procedure for the recognition and classification of pieces of archaeological artifacts. XII ADM international conference, Rimini, Italy, Sept. 2001
[10] Ankerst M, et al. 3D Shape Histograms for Similarity Search and Classification in Spatial Databases. Proc. 6th International Symposium on Spatial Databases,Hong Kong, 1999
[11] Kriegel H.-P, et al. Approximation-based Similarity Search for 3D Surface Segments, in: GeoInformatica Joumal, Vol. 2, No. 2, 1998.
[12] Osada, R. et al., Matching 3D Models with Shape Distributions. International Conference on Shape Modeling and Applications,2001.
[13] Tamas Varady, Ralph Martin,Jordan Cox. Reverse engineering of geometric models—an introduction. Computer Aided Design, 1997,29(4):253-268
[14] Huang MC, Tai CC. The Pre-processing of data points for curve fitting in
reverse engineering.International Journal of Advanced Manufacturing Technology.2000,16(9):635-642
[15] AC, Chan CF. Point-data processing and error analysis in reverse engineering.International Journal of Advanced Manufacturing Technology,1998,14(11):824-834
[16] Helena Cristina da, Gama Leitao. A Multi-Scale Method for the Re-Assembly of Fragmented Objects.2000.
[17] Farzin Mokhtarian and Alan K. Mackworth. A Theory of Multiscale,Curvature-Based Shape Representation for Planar Curves. on Pattern Analysis and Mach. Intel 1. 14 (8), 789--805(1992).
[18] 求是科技 张宏林编著．Visual C++数字图像模式识别技术及工程实践．人民邮电出版社2003．2 233-255
[19] 刘炉山．基于数字化样条的虚拟测量及数据技术．南京航空航天大学硕士学位论文．2002
[20] 施法中 计算机辅助几何设计与非均匀有理B样条(CAD&NURBS) 北京航空航空大学出版社1994
[21] 蔡炜斌，逆向工程中基于轮廓数据的曲面重构[学位论文]，南京，南京航空航天大学硕士学位论文，2001
[22] 孙家广，杨长贵，计算机图形学，北京：清华大学出版社，1994
[23] W. Schroeder, K. Marin and B. Lorensen, The Visualization Toolkit: An Object-Oriented Approach to 3D Graphics, Prentice Hall,1997.
[24] M. Sonka, V. Hlavac and R. Boyle, Image Processing, Analysis and Machine Vision, PWS,1999.
[25] Haim J.Wolfson. On curve matching. IEEE Transactions on Pattern Analysis and Machine Intelligence. 12(5):483-488,1990
[26] Paul Rosin and Svetha Venkatesh. Extracting natural scales using the Fourier description. Pattern Recognition ,26(9):1383-1393,1993.
[27] F.Boussofiane and G.Bertrand. Anew method for recognizing and locating objects by searching longest paths.IEEE Transactions on Patern Analysis and Machine Intellignce.,26(12):445-448,1993.
[28] H. Freeman and L. Garder. Apictorial jigsaw puzzles: the computer solution of a problem in pattern recognition.IEEE Trans. Elec. Comp.,13:118-127, 1964.
[29] G. M. Radack and N. I. Badler. Jigsaw puzzle matching using a boundary-centered polar encoding. CGIP, 19:1-17, 1982.
[30] H.Wolfson, A. Kalvin, E. Schonberg and Y. Lambdan. Solving jigsaw puzzles by computer. Annales of Operations Research,12:51-64, 1988.
[31] Farzin Moldhtarian and Alan K.Mackworth A theory of multiscale curvature-based shape representation for planar curves. IEEE Trans. PAMI, 14:789-805, 1992.
[32] 《运筹学》教材编写组．运筹学(第2版)[M]．北京：清华大学出版社，1990．194-253．
[33] 戴华 矩阵论(第一版)[M]．北京科学出版社，2001．169-175
[34] Helena Cristina da Gama Leito, Jorge Stolfi A Multi-Scale Method for the Re-Assembly of Fragmented Objects. IEEE Transactions on Pattern Analysis and Machine Intelligence(TPAMI), vol. 24, no. 9, 1239-1251. September 2002.
[35] http ://jwc.seu.edu.cn/xuyue/w104/s6.6/importent/zhangl/pinpu/pinpu.htm
[36] Helena Cristina da Gama Leitao and Jorge Stolfi. Geometric Curve filtering.Technical report. 1998
[37] Ronald N.Brancewell. The Fourier Transform and its Application.McGraw-Hill, 1986.
[38] (英)C．查特非尔德．时间序列分析导论．宇航出版社．1986．
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |