| As a newly developed subject and technology, reverse engineering has gained widespread use in many areas such as industrial design and fabrication, simulation and virtual reality, medicine and entertainment, etc. Thus, reverse engineering has become the focus of scientific research, and has attracted increasing attentions at home and abroad. In this dissertation, we study several key techniques in reverse engineering, and the main results are as follows:1. We study the technology of registration of point clouds, which is one of the key techniques in the data pre-processing of reverse engineering. Based on the works of Zhu et al. [27] and Luo et al. [57], we propose an automatic registration method of scanning point clouds by introducing new metrics for matching corre-sponding points and modifying ICP algorithm. The whole registration consists of two steps:the initial registration and fine registration.In the first step, the proposed method firstly aims at constructing high-quality corresponding points. Assume S1={pi1|pi1∈R3, i=1,…, N1} and S2= {pi2|Pi2∈R3, i=1,…,N2} are two point clouds to be aligned. For any two points pi1∈S1 and pj2∈S2, the neighboring surfaces around them are required to be of the same type, i.e., the Gaussian and mean curvatures of pi1, pj2 must satisfy where sign(·) is the sign function. Then we omit the points in planar areas by requiring pi1, pj2 to satisfy Here,δ1,δ2>0 are two sufficiently small preset thresholds. Furthermore, we introduce the similarity metric of principle curvatures of pi1, pj2, as that in the work of Zhu et al.:Based on these restrictions, we further develop a new metric for the curva-ture similarity between the neighborhoods of two points, i.e., ZNCC (Zero-Mean Normalized Cross-Correlation Coefficient). As a matching metric for 2D images, ZNCC is often used for measuring the similarity of grey values between the local neighborhoods of two pixels, and a larger ZNCC value implies a higher similarity. We incorporate ZNCC into the registration of point clouds by taking points in 3D spaces as pixels and point curvatures as the pixel grey values. For any point couple (Pi1, Pj2), let Zncc1(pi1,pj2) and Zncc2(pi1, pj2) denote the neighborhood similarity of principle curvatures k1 and k2, which are of the following forms: whereΣk denote the summation operator all over the given local neighborhoods of pi1 and pj2, and k1,1 k21 and k12, k22denote the mean values of maximal and minimal curvatures in the neighborhoods of pi1 and pi2, respectively.The matching strategy using ZNCC is as follows. For any non-planar points pi1 in the first point cloud, suppose M denotes the set of all the points in the second point cloud satisfying Eqs. (1), (2), and (3), then we take point p*2 satisfying Eq. (4) as as the only corresponding point of p1i where Zncc(pi1, pj2)=Zncc1(pi1, Pj2)+Zncc2(pi1,pj2), andε3 is a preset threshold.Applying the above methods, we can obtain an initial array of one to one cor-responding points. Furthermore, by using the invariants of the rigid transformation, two more restrictions based on the Euclid distance and super segments are applied to pick out some corresponding points of higher precision from the initial array. The proposed algorithm directly computes the initial registration parameters according to the normal vector and principle vectors of the corresponding points.In the second registration step, we filter the initial point clouds using the cor-responding points obtained previously, and construct two effective initial point sets P and X for ICP iteration. During the iteration, for any point p∈P, Luo et al. search three most closest points x0, x1, x2 in X, and take the foot of perpendicular of p in the plane fixed by x0, x1, x2 as the corresponding point of p. However, this handling is not appropriate in the case when the foot of perpendicular of p locates outside of the triangular face F composed by x0,x1, x2. In contrast, we search the closet point on the triangular face F to avoid such situations.The algorithm needs neither additional information about the position or ori-entation of the laser scanner, nor any artificially introduced label or feature points. Besides, the algorithm directly computes the first registration parameters according to the geometric information of the corresponding points. Hence, there is no need to compute the possible transforms of all the point pairs or to construct the hash table for finding the first registration parameters. Experiments have demonstrated the efficiency and good performance of the method.2. By studying and analyzing the subdivision surface reconstruction technol-ogy in reverse engineering, we propose a method for fitting point cloud using Loop subdivision surface.Let P denote the point cloud data, T denote the triangle mesh constructed from P, and M denote the control mesh. Suppose xi∈M is the i-th control vertex; vi∈T is the i-th vertex of T, then the Loop's subdivision surface interpolation problem can be formulated as follows:for the given points{vi}1μ, find the control vertices{xi}1μsuch that Define X=[x1,…, xμ]T, V=[v1,…, vμ]T, Eq. (5) can be expressed in a matrix form: where A={ai,j}μ×μ, and For Eq. (6), classical Jacobi or Gauss-Siedel iterative algorithm does not necessarily converge. Xu put forward the following Jacobi-like iterative algorithm However, he did not prove the convergence of the algorithm.We firstly transform Eq. (6) into an equivalent expression by multiplying both sides of Eq. (6) by matrix D DAX=DV, where D={di,j} is a diagonal matrix with diagonal elements di,i= 1/li, i= 1,…,μ. Define P=DA, B=DV, then we can obtain PX=B. (7) Here, P={Pi,j}μμandWe prove that matrix P is positive definite, and further give the following upper and lower bounds estimations for its eigenvalues:Theorem 1 All the eigenvalues of P are greater than 1/8.Theorem 2 All the eigenvalues of P are less than 1/lN, where N is the maxi-mal valence of all the vertices of T.We put forward two kinds of iterative methods based on Richardson relaxation algorithm and SOR algorithm, and also give the corresponding profit-loss modifi-cation formulas. It is clear that for the linear system of equations Eq. (7), both the two iterative algorithms are convergence.For any xi∈M, let ri denote the correction term, x'i denote the new position of xi, and i* denote the index set for the 1-ring neighbors of xi.(1) Richardson relaxation iterative algorithm(2) SOR iterative algorithmThe interpolation of a given point cloud using the Loop subdivision surface includes the following steps: Stepl For the input point cloud Q, we firstly simplify it if Q is too dense or contain redundancies. Assume P is the resulting point cloud, and T is the triangle mesh constructed from P.Step2 Take vertices{vi} of T as the initial positions for the vertices{xi(0)} of the initial control mesh M(0), and let k:=0.Step3 Compute error E(k)= maxi|(xi(k))∞-vi|·If E(k) is less than the given thresholdε> 0, go to Step5; otherwise, go to Step4;Step4 Correct the position of each vertex of M(k) according to Eq. (8) or Eq. (9). Denote the resulting mesh by M(k+1), k:=k+1, then go to Step3.Step5 Output the control mesh M:=M(k) with the vertices{xi(k)} for the subdivision interpolation surface.Through numerical experiments, we demonstrate the efficiency and high pre-cision of the proposed two iterative algorithms.3. With the advent of laser scanning systems, the multiresolution analysis technique has received increasing attention due to its ability to process large-scale meshes. This technique has been widely used in various fields of 3D graphics pro-cessing, such as geometry compression, progressive transmission, denoising, con-tinuous level-of-detail control and multiresolution editing and so on. The ground-breaking work of the multiresolution analysis theory based on subdivision wavelets was done by Lounsbery et al. in 1997 [158], who extended classical wavelet anal-ysis to subdivision surfaces and constructed a new class of subdivision wavelets that could be defined on surface of arbitrary topological type. From then on, the multiresolution analysis technique based on subdivision wavelets has increasingly become an important method in the processing of 3D graphics.In recent years, the ternary subdivision has received a lot of research interests because of its ability to produce limit surface with bounded curvature at extraordi-nary vertices. Thus, in this dissertation we construct a biorthogonal wavelet trans-form for the ternary Loop subdivision based on the lifting scheme, and present in detail the wavelet decomposition and reconstruction formulas. In this paper, we use the following ternary subdivision scheme proposed by Loop [179] we can easily obtain an equivalent expression of Eq. (10)The starting point for the construction of our subdivision wavelets by lifting scheme is to establish a reversible subdivision scheme. To make the ternary Loop subdivision scheme (11) reversible, we introduce a vector e for each newly gener-ated edge-vertex and a vector f for each face-vertex at each level. Hence, we can obtain the following extended ternary Loop subdivision: It is obvious that Eq. (12) is equivalent to Eq. (11) if all the vectors e, f are initialized to be zeros. In general, e or f may have nonzero values which contribute to the final shape of the subdivision surfaces through recursive subdivision operations. By reversing each mask of Eq. (12) starting from the third mask, we can obtain the reverse of Eq. (12)In terms of the theory of second generation wavelets, Eq. (12) and Eq. (13) have already defined a lazy wavelet synthesis and a lazy wavelet analysis, respec-tively. The basis functions corresponding to the vertex-vertex (i.e., scaling func-tion), the edge-vertex (lazy wavelet) and the face-vertex (i.e., lazy wavelet) are al-ready defined by Eq. (12), while vectors e and f correspond to the coefficients of lazy wavelets.Unfortunately, the lazy wavelets derived above usually result in instable com-putation, which means that the coarse signals obtained from wavelet decomposition fit poorly to the detailed signals. In order to overcome this restriction, some im-provements can be made by using the lifting scheme. The lifted lazy wavelets are orthogonal with the scaling functions and thus exhibit a better stability. In order to save the computational cost, a local orthogonalization with a discrete inner operator is employed.For any edge-vertex e, we orthogonalize the corresponding lazy waveletψe with the scaling functions at all the parent vertices vi, i= 0,…, n0, i.e., we con-struct a new wavelet function satisfying where n0 is the valence of the central parent vertex v0, and (?)i is the corresponding scaling function of vi, i= 0,…, n0. Combining Eq. (14) and Eq. (15), we can obtain the following linear system of equations of order n0+1 Aw=b, where A={<(?)i,(?)j>}, b={-(<(?)i,ψe>}, w={ωi}. By solving the system, the weightsωi,i=0,…, n0, can be obtained. The orthogonalization of the lazy wavelet corresponding to any face-vertex f follows the same way.Based on the above works, we can give the synthesis formulas of the new biorthogonal ternary Loop subdivision wavelet transform which consists of the fol-lowing six assignment statements to be executed in sequence: By inverting the six individual lifting operations of Eq. (16) in reverse order, we can obtain the wavelet analysis which is composed of another six assignment statements executed in sequence:Furthermore, we apply the proposed algorithm to the progressive transmission and the denoising of 3D graphics, and show its sufficient stability and good performance by some numerical experiments.4. As one of the methods of 3D graphics processing, multiresolution anal-ysis based on subdivision wavelets has been investigated and applied in the past decade. Nevertheless, as far as we know, multiresolution analysis based on subdivi-sion wavelet tight frames has few applications to the processing of 3D graphics. It is evident that the application of wavelet tight frames will bring in some advantages. First of all, a tight frame is its own dual and, therefore, the masks for decomposition and reconstruction are the same. Hence, there is no need to solve any linear sys-tem of equations. Secondly, the discrete frame transform is an isometry on l2 if the given fine-scale coefficients are properly normalized. So the decomposition over an arbitrary number of resolution levels has condition number 1.Based on the works of Charina and Stockler, we present in detail the wavelet tight frame decomposition and reconstruction formulas for Loop subdivision scheme. The subdivision scheme used by Charina and Stockler is a variant of the standard Loop subdivision scheme proposed by Warren et al., and the subdivision rules are as follows where n is the valence of vertex v.For any j≥0, let T(j) denote the subdivision mesh at level j, and a,=[aj,k: k∈Mj]T denote all the vertices of T(j),where Mj is the index set. For some J>0, suppose that we are given the vertices sequence aj=[a,j,k∈MJ]T. For any 0≤j |
PDF Full Text Request