为了正常的体验网站,请在浏览器设置里面开启Javascript功能!

基于小波理论的多重分辨率的曲面构造_英文_

2017-11-23 24页 doc 202KB 12阅读

用户头像

is_036899

暂无简介

举报
基于小波理论的多重分辨率的曲面构造_英文_基于小波理论的多重分辨率的曲面构造_英文_ () 文章编号 10042924X20010320203209 Multiresolution Surface Construction 1 1 2Guo Yun, Yasushi Yamaguchi, Zhong Xian - xin ( 1. Department of Graphics and Computer Sciences , The University of Tokyo , J apan ; )2 . Department of Optical Mechan...
基于小波理论的多重分辨率的曲面构造_英文_
基于小波理论的多重分辨率的曲面构造_英文_ () 文章编号 10042924X20010320203209 Multiresolution Surface Construction 1 1 2Guo Yun, Yasushi Yamaguchi, Zhong Xian - xin ( 1. Department of Graphics and Computer Sciences , The University of Tokyo , J apan ; )2 . Department of Optical Mechanics , Chongqing University , China Abstract :Unstructured and highly detailed meshes need to be effectively represented in many applications. Accom2 panied with wavelets , hierarchical multiresolution meshes can be in charge of this effective representation. To per2 form this multiresolution representation with wavelets , an available function space needs to be constructed and de2 fined over the general triangulated surface meshes. To employ an effective method to accomplish the construction of a continuous parameterization of arbitrary meshes over a simple domain is a key problem. The paper proposes a fast parameterization method based on geodesic polar map that can be effectively served in multiresolution surface con2 struction. Compared with previous methods , the construction process given in the paper can save a lot of computa2 tion time and maintain fine visual result . Key words :multiresolution surface representation ; parameterization ; geodesic polar map ; wavelets CR Categories and Subject Descriptors :I. 3 . 5 Computer Graphics :Computational Geometry and Object Model 2 ing. - Surfaces and Object Representations. 1 ,6 ,10 fold mesh. To implement this transformation to function space , an important element is concerned with 1 Introduction parameterization , which sets up the complexity domains to support triangulated surface parameterization. There are many representations for surfaces used 1 ,6in computer graphics such as parametric surfaces and Founded on this fact , two methods , harmonic map 3 constructive solid geometry etc . Triangle meshes , sup2 and its variant PL harmonic embeddinghave been employed in the triangulated surface multiresolution ported by the graphics hardware and obtained conve2 analysis. niently from laser scanning system , are capable of de2 In this paper , we draw on the parameterization scribing surfaces of arbitrary shape and topology. With 14 the advent of laser scanning system , arbitrary objects methodbased on geodesic polar map , and apply it can be made up of dense triangular meshes , which pos2 to our multiresolution surface construction practice . 17 From the differential character of geodesic polar map , sibly consist of large amount of triangles. To apply we named this parameterization shape2preserving pa2 these triangular objects to various fields , such as CAD , rameterization. The computation time and sampling re2 reverse engineering , arts etc . , one need to find more sults derived from the harmonic map method and shape2 effective technologies to process these objects. The first preserved method show that the latter method is more problem to be considered is to reconstruct the objects to effective when used in multiresolution surface construc2 be suitable for application in current computer capabili2 tion for the triangulated surface . Besides , we simulta2 ties . Multiresolution representation has been used as an ( neously combine smaller patches compared with the empirical technology to produce applicable surfaces. 6 ) Classical multiresolution technology based on wavelets strategy used in, figure 3to do parameterization , when applied to geometric problems needs to seek a which also contributed to less computation time . functional space over the original triangulated 22mani2 收稿日期 : 2001202214 ; 修订日期 : 2001204226 ing wavelets can go with this remesh. 2 Related Work From the point of view of graph with the consider2 1 The classical theory for multiresolution signal de2 ation of global geometric features , P. Gioiaproposed another measure to implement the multiresolution anal2 composition with the help of wavelet representation in2 ysis , which reduced the number of wavelet coefficients dicates that a signal can be approximated by a given 6 resolution. A family of wavelet basis functions can for equal detail representation. Resembling as, some withdraw the difference of information between two ad2 approximate harmonic map s have been used to build a 5 parameterization of original surface meshes over trian2 jacent given resolutions. This enables us to have a gular regions with good geometric approximation. hierarchical representation for the original signal with 10 j Lee provided an algorithm to consider the local( ) gradually increasing resolution such as 2j ?Z. sharp features to construct a hierarchical parameteriza2 These wavelets have been introduced as some functions tion over the base domain space . The parameterization with the characters of translations and dilations in many is implemented by using the PL harmonic embedding areas including image compression , numerical analysis operation. and physical simulation. Michael Lounsbery and his 7 The above2mentioned schemes heavily made use of coworkershave developed a class of wavelets , based harmonic map s to implement the parameterization. Dif2 on the subdivision surface , applied to functions defined on compact surfaces of arbitrary topological type . ferent from those work , we present an alternative ap2 6 proach to the parameterization in multiresolution surface Eck. etc . firstly provided an appealing frame2 work for the multiresolution geometric surface construc2 construction using the shape2preserving method. It re2 tion which originated from the view of a mathematical sults in less computing time and better sampling effect formalism of wavelet multiresolution analysis. than those with harmonic map method at the time when 6 triangulated surface reconstruction is conducted. In The key component of is to set up the smooth next section we will discuss the two main parameteriza2 parameterization of triangulated surfaces over simply tion methods and make some comparisons. In section 4 complex base domains , which include some Delaunary2 we will outline the results of our multiresolution surface like triangular regions generated first by constructing a construction practice . In the final section , conclusions Voronoi graph. In order to reach the goal , a series of approximate harmonic map s are employed to accomplish are discussed and further work are presented. 6 parameterization. In, harmonic map s have been re2 peatedly used in three main stages. These stages can 3 Para meterization be generalized as the following : from Voronoi tiling to Delaunary triangular , combining some subpatch of 3 . 1 Harmonic Ma ps Voronoi tiles to straight the edge of Delaunary triangular In triangulated surface parameterization , harmonic regions and the initial domains construction. The initial has already been widely used in different areas map 16 15 domains and the parameterization over it build the such as surface matchand graphics morphing, function description of the original triangulated surface . especially in the region of multiresolution surface con2 This description makes it practicable to hierarchically struction. Its elementary thought is as below : represent the surfaces by subdivision schemes like Ω We suppose f :< N ?M is a smooth map be2 8 Loop . The sampled vertices with subdivision connec2 () () tween Riemannian manifolds N , hand M , gwith tivity from the original triangulated surface can be used metrics h and g , respectively. This is a parameteriza2 to construct the wavelet representation. The original Ω) (tion of surface f < M over a two dimensional sub2 Ω triangulated surface can be further reconstructed from a manifold < N. The Dirichlet energy of the map f is wavelet representation. The multiresolution analysis us2 defined as Ω vertices of . A general conjugate gradient algorithm is2 ( ) ΔEf = 1/ 2| f | d g ?Ω ( )preferable to solve the linear equations. Figure 1 c 2 Δ( ) where | f | = trace g 5 f , 5 f , 5 f , , , ,. g is g displays an approximate harmonic map result . served as metric . The critical points of this energy 3 . 2 Sha pe2preserving Method ba sed on Geodesic function are called harmonic map s. This is a general Polar Ma p definition of harmonic map s. Now , we consider the Unlike previous work , we use shape2preserving special case . The two manifolds are in the 3D Euclide 2 method based on geodesic polar map in our multiresoluspace . The M is a surface of disc topology and N is a tion surface construction. This method originated from planar region. The harmonic map theory leads to a u2 14 Michael S. Floater ’s parameterization. He pro2 φ nique solution when we give a homeomorphism be2 posed this fast parameterization method and used it in 2 tween the two boundaries of M and N for this map. his surface fitting. The foundation of this approach is a Ω Furthermore if we let be a domain with triangulation geodesic polar map preserving the radial directional dif2 ωГand be the set of continuous and piecewise linear h h ferential similarity. The basic idear behind this param2 functions on Г. Then we can define the discrete h eterization is to set each vertex in image space to be a Dirichlet energy of any function f < Г: h h convex combination of its neighbors. And this combina2 2( ) ( ) ( ) Σ( αβ) f x- f x| Ef = 1/ 4cot+ cot| h i h jd hij ijtion is unique . The details are as follows : ) ( Firstly , let S G , Xbe disc topology surface tri2 edge{ i , j} 1 , 6 took an approximate approach to the harmonic ( ) angulation with graph G V , E , Fand node set X = 3 { x? R, i = 0 ,1 ,2 , , , , , n - 1 , n , n + 1 , , , , i Φ map . Given firstly a homeomorphism between the (Ω) Ω boundary of f and the boundary of , the map can ,N - 1} . We set the vertex set V = { i ; i = 0 ,1 ,2 , be imaged as the deformation of a network of springs. , , , ,n - 1 , n , n + 1 , , , , ,N - 1} . The range in2 Ω dexes 0 , n - 1 are pointed to interior vertices and Then the boundary of can be chosen according to the n , N - 1 boundary vertices index. The parameteriza 2 concrete application. The energy function can be com2 ( ) tion domain corresponding to S G , Xis a triangulated puted as follows : 22 Σ ( ) ( ) ( ) Ef = 1/ 2K| | f i - f j| | d ij ( ) planar region R G , Pwith node set P = { p ? R,i (Ω)() 1 { i , j } ?edges i = 0 ,1 ,2 , , , , ,n - 1 , n , n + 1 , , , , ,N - 1} . ( ) ( ) f iand f jare the images of the vertices i and j of Secondly , we ensure the unique convex combina2 Ω) Ω(f on . The K, serving as the spring constants , ij tion for each node i ?0 ,n - 1 to be built . Put the is related with the two triangles adjacent to the edge boundary of S onto the boundary of R by a piecewise ( ) { i , j} . The energy Ef can be regarded as the re2 d linear function. For our experiments , the boundary of sult from the deformation of triangulated spring meshes. 2 R is a convex polygon D < Rwith r corners. The fol2 In approximate harmonic map s , the spring coefficient lowing is the definition for the convex combination in Kis destined to preserve the ratios of edge length as ij the image space . small as possible in image space . For the two defined N - 1 λ( ) p=with pi ?[ 0 , n - 1 ]3 ijji ?vertices of one edge { i , j} , the Kis always equal . ij j = 0 ( ) Minimizing the energy function Ef is actually to λwhere the chosen by the geodesic polar map in addi2 d ij solve the symmetric sparse linear system : tion to the constrains : λλ > 0 { i , j} ? E otherwi se= 0 ,ij ij Δ( ( )) Ef = 5 Ef / 5 V = d id N - 1 ( )2 HV + 2 HV = 0 2 Σλiiii ibb = 1 ij j = 0 V is a vector of images corresponding to all inte2where The proof of this the unique of convex combination can i Ωrior vertices in . V is a vector of images of boundary b be found in 14 . Thirdly , a geodesic polar map needs to be built holds attractive speed of converging. We have already for each interior vertex i ?0 , n - 1 . In differential performed hundreds of the parameterization founded on geometry , the geodesic polar map originates from the geodesic polar map s using the Bi2CGSTAB solver . It 4 exponential map . The exponential map carries radial ( )works well for such linear equations. Fig. 1 b is the lines from vertex i in tangent plane of i to geodesics result from shape2preserving parameterization. starting at vertex i in S. And the exponential map holds 3 . 3 Comparison of the Experiments the diffeomorphical character for the neighborhood of i between image and source space . Let Gbe any one subgraph with vertex i and its i neighborhood , then a relative local coordinate system with the origination pis set as follows. For the neigh2 i ( borhood pj ?[ 0 , d- 1 ] , degree dis the number ij i i ) of neighborhood , the following conditions are satis2 fied. . | | x- x| | = | | p- p| | . i ij i ij . These angles between xaround xare scale to ij i () aOriginal surface patch the related angles between p. ij At the end of setting this local map , for each Δneighborhood of i , a triangle pppincluding ( ) ( ) ijir jir j+1 pcan be generated. However , pis completely inside i i the triangle or on the boundary of the triangle , the barycentric coordinates should exist for pwith respect i to this triangle . d- 1 i Σ = pb, b= 0 when p ijjk jk ik = 0 ( ) k ? r j+ 1. ( ) ()k ? r jand 4 λFinally , the coefficientscan be computed as the fol2 ij ( ) bShape2preserving embedding lowing : d- 1 i λΣ= 1/ d b ij i jkk = 0 () The formula 3can be written into the following ma2 trix linear equations : )(B P= 5 C τ Known from the above discussion , B is a sparse un2 symmetrical matrix. Generally speaking , the biconju2 gate gradient iterative method or generalized minimum resident method can solve the unsymmetrical linear e2 quation questions. In all our parameterization and sam2 9pling experiments , the approach named Bi2CGSTAB () cHarmonic embedding ( ) is adopted to be the solver of the formula 5, which leads to the fast smoothly converging result . Compared with the conjugate gradient algorithm , this solver also geodesic polar map have been carried out respectively. As we expected , the latter can preserve the similar lo2 cal shape in the polygon of R2 to relative surface patch ( ) ( )1 d 2f excluding the boundary triangles. Figure show us the tiny shape differences. ( ) ()dA subpatch of a () aShape2preserving method () ( )eShape2preserving map for d ( ) bHarmonic map Fig. 2 Computation time for different parameterizations. We carry out the partitioning work through ( ) Voronoi graph for Stanford bunny see section 4. Fig2 ure 2 shows the computing time comparison , which has been finished according to the parameterization of 92 2 Voronoi surface patches over the domains of R. The start point of this computation time is from fixing the boundary vertex for each patch. Studying the trends () ( )fHarmonic map for d from these charts , it is not difficult to find the shape2 ( ) Fig. 1 One surface patch cut from Stanford bunny. dindi2 preserving method with the faster convergence than the cates a vertex and its neighborhood. The shape varia2 scheme based on the harmonic map s. Also , we can () () tion can be observed from eand f. () feel , for figure 2 a, the computation time increment is not so much with the increasing of vertex amount . Surface curves sampled from the parameterization of In the process of our practice for multiresolution shape2preserving method can be observed from Fig. 3 surface construction , the parameterization based on () c. By the way , these experiments we have done are harmonic map and the parameterization based on under the platform of Windows NT 4 . 0 and Visual + + C 5 . 0 . 4 Multiresol ution Surface Construc2 tion From the signal analysis , we know a signal can be considered in the frequency domain. Therefore , can consider the surfaces as some kind of function about the distributor of a geometric measure such as curvature . Sampling theory tells us that a better2reconstructed sig2 ( ) bCombined smaller region nal should be made up of much different frequency component of itself . The surface reconstruction will obey the principle as soon as possible . Our main frameworks of multiresolution surface construction come from 6 . At first , a partition was carried out over the densely triangulated surface . Grow2 ing a Voronoi diagram using a multi2seed Dijkstra’s al2 gorithm can generate the patches. This diagram is then triangulated by the dual of the Voronoi graph and De2 launary2like triangular . Here , in order to straighten the () cDelaunary triangular curve edge of Delaunary2like triangular , we combined 6 ( ( ) ( ) ) two patches smaller thanFigure 3 a , c as a combined domain to perform a parameterization over it . This combined domain apparently encloses fewer ver2 tices so as to reduce the dimension of sparse matrix to ( ( ) () ) be solved Figure 3 b, e. To reach the approved goal , we strictly limited the conditions of producing the Voronoi diagram. We let each Voronoi site closer to the geometric center corresponding to Voronoi patch. These ( ) dCombined patch limitations enable us to produce a good look Delaunary ( ( ) ) triangular surface patches Figure 3 c. The results are shown in figure 3 . () eCombined smaller patch ( ) ( ) 2 ReFig. 3 Different combined domains for aand b. ( )sulting Delaunary triangular surface patches c ( ) come from busing the shape2preserving parame2 terization () aCombined region Next is to complete a parameterization of original surface over the Delaunary2like triangular regions. In our experiments , we used the method based on geodesic polar map narrated as before to implement the ( ) parameterization. In figure 3 c, we set up the con2 tinuous parameterization over the domains of 252 De2 launary triangular planar regions. Finally , as the original triangulated surface com2 ing from the real object in the form of uniform2sized tri2 angle meshes , the uniform triangular sampling out of ( )d such surfaces is an important element to preserve the smooth visual effect for the resulting triangulated sur2 face . We reached the target by adopting 6 ’s method named geometrically uniform sampling. The sampling order is to obey the general subdivision scheme , such 8as Loop scheme in figure 4 . ()e ()a ()f Multiresolution representation of Stanford Universi2 Fig. 4 ( ) ty’s bunny. a Object from laser scanner with ( ) 362272 points bObject from space2time analysis ( ) with 69451 faces. c Domains built by shape2 ( ) preserving parameterization. d Geometrically () ( )sampling for 2 levels. eFirstly 3 levels geomet2 b rical sampling followed by 1 level parametrical () sampling. fFirstly 3 levels geometrical sampling followed by 2 levels parametrical sampling. 5 Conclusion and Future Work We have described the multiresolution surface construction method based on the parameterization ()c named shape2preserving. During our parameterization , tion on such triangulated surface will be a fundamental 13 the fast Bi2CGSTAB is adopted as the solver for the lin2 problem. Recent workhas concerned with this prob2 ear equation system. Compared with the parameteriza2 lem. Combined with the dual local characters in time2 frequency domain of wavelets , how to effectively use tion based on harmonic map , this parameterization ef2 fectiveness has been showed in the computing time and the wavelet coefficients to represent the geometric fea2 the sampling result from this parameter . tures will be an interesting context for our further work. And yet , geometric features extraction and evalua2 References : 1 Gioia P. Reducing the number of wavelet coefficients by geometric partitioningJ . Computational Geometry Theory and Applica 2 tions ,1999 ,14 :25 - 48. Eells J ,Sampson L H. Harmonic mappings of Riemannian manifordsJ . Amer. J . Math , 1964 ,86 :109 - 160. 2 3 Duchamp T ,Certain A , Derose T , Stuetzle W. Hierarchical computation of PL harmonic embeddingsC . Tech. Rep , University of Washton , 1997. 4 Barret O’Neill . Elementary differential geometryC . San Diego , USA :2nd Academic Press , 1997. 5 Stephane G. Mallat . A theory for multiresolution signal decomposition : The wavelet representationJ . IEEE Transactions on Pat 2 () tern Analysis and Machine Intelligence . 1989 ,117:674 - 693. Eck M , DeRose T , DUCHAMP T. Multi - resolution analysis of arbitrary meshes. ACM Computer GraphicsC . SIGGRAPH ’95 6 Proceedings , Los Angeles , California , 1995 ,173 - 182. Michael Lounsbery , Tony D. DeRose , Joe Warren. Multiresolution analysis for surfaces of arbitrary topological type J . ACM 7 () Transactions on Graphics ,1997 ,161:34 - 73. 8 Loop , C T. Smooth subdivision surfaces based on triangles. Master’s thesisA . Dept . of MathematicsC , Univ. of Utah. Au2 gust ,1987. van H A DER VORS. BI2CGSTAB : A fast and smoothly converging variant of BI2CGfor the solution of nonsymmetrical linear sys2 9 () temsJ . SIAM J . Sci . Stat . Comput ,1992 ,13 2:631 - 644. 10 Aaron W. F. Lee . Peter Schroder , Lawrence Cowsar , David Dobkin. MAPS : multiresolution adaptive parameterization of surfaces A . In ACM Computer GraphicsC . SIGGRAPH ’98 Proceedings , 1998 ,19 - 24. Kai Hormann , Gunther Greiner. An efficient global parametrization MethodA . Curves & Surfaces Fourth International Confer 2 11 ence C , France , 1999 ,1 - 7. Allen Van Gelden. Approximate simulation of elastic memberances by triangulated spring meshesJ . Journal of Graphics Tools , 12 () 1998 ,3 2:21 - 42. Christian Rossl , Leif Kobbelt , Hans2Peter Seidel , Extraction of feature lines on triangulated surfaces using morphological opera2 13 torsA . AAAI Spring Symposium , Smart GraphicsC . Stanford University ,2000. Michael S. Floater. Parameterization and smooth approximation of surface triangulationJ . Computer Aided Geometric Design , 14 1997 ,14 :231 - 250. Kanai T , Suzuki H , Kimura F. Three2dimensional geometric metamorphosis based on harmonic mapsJ . The Visual Computer , 15 () 1998 ,14 4:166 - 176. Zhang D , Hebert M. Harmonic maps and their applications in surface matchingA . IEEE Conference on Computer Vision and 16 ( ) Pattern RecognitionC . CVPR ’99,1999. Marc Levoy , Kari Pulli , et al . The digital michelangelo project : 3D scanning of large statusA . ACM Computer GraphicsC . 17 SIGGRAPH 2000 proceedings , 2000. 基于小波理论的多重分辨率的曲面构造 1 1 2 郭云,山口泰,钟先信 ( 1. 日本东京大学图形和计算机科学系 , 日本 东京 ; )2. 中国重庆大学光电精密仪器系 ,重庆 400044 摘要 :高精度 、非接触式的激光数字扫描仪的诞生 ,使得人们能非常方便地获得高细节的物体形状 。这种物体是以非结构化和浓密的网格存储在计算机中的 。为了在科学 、工程 、艺术等领域有效地应用这种 物体 ,需要建立物体在计算机中有效表达形式 。基于小波分析的多重分辨率的曲面构造能担任这种任 ( ) 务 。细分连接 subdivision2connection的小波函数的构造需要我们把曲面参数化到一个简单的复合形域 中 。在这篇文章中 ,我们从微分几何的测地极映射观点出发 ,提出用快速的形状保持的参数化方法有效 地建立具有多重分辨率的物体曲面形状 。同前面的方法相比 ,我们的构造过程可以节约大量的计算时 间且维持良好的物体曲面形状 。 关 键 词 :多重分辨率曲面表达 ; 参数化 ; 测地极映射 ; 小波 中图分类号 : TP391文献标识码 :A Resume :Guo Yun was born in Jiangxi province , China in 1967. He is currently a PhD student , sponsored by J apanese Government Monbusho Scholarship and Sane Yoshi Scholarship , in the Department of Graphics and Computer Sciences , the University of Yokyo . He received his BE and ME from Chongqing University of China in 1989 and 1992 , respectively. In 1995 , he entered the Doctor’s course in the Department of Optical Precision Machine of Chongqing University. His research interests include the areas of computer graphics , computational geometry , wavelet analysis , and surface recognition. He has published several papers in the areas of computer graphics and modeling. He can be reached by e2mail :guo @graco . c . u2tokyo . ac . jp , or through postal address : Room D224 , The University of Tokyo , Mitaka International Hall of Residerce 6222220 Shinkawa , Mitaka2Shi , Tokyo 18120004 ,J apan. Yasushi Yamaguchi was born in J apan in 1961. He is currently an associated professor in the Deparmtent of Graphics and Computer Sciences , the University of Tokyo . His research interests lie in computer2aided design and geometric modeling , including parametric modeling , topology models for B2reps surface intersection and surface inter2 rogation. He is a member of ACM SIGGRAPH , IEEE Computer Society , and SIAM. He received BE in precision ma2 chinery engineering and Dr. Eng. in information engineering from the University of Tokyo in 1983 and 1988 , respec2 tively. He was an assistant professor of Tokyo Denki University from 1989 to 1993. He has cooperated with Tokyo Re2 search Lab , IBM , Stanford University in the areas of computer graphics and CAD geometric modeling. He has pub2 lished many papers in the international professional journals such as Computer Ai ded Geomet ric Desi gn , I EEE Computer S ociety , A CM etc . He can be reached through postal address : Department of Graphics and Computer Sci2 ences/ The University of Tokyo/ 32821 , Komaba , Meguro2ku/ Tokyo 15328902/ J apan.
/
本文档为【基于小波理论的多重分辨率的曲面构造_英文_】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索