ALGORITHM OF PRETREATMENT ON AUTOMOBILE BODY POINT CLOUD.docVIP

chinese journal of mechanical engineering vol. 20, no. 4, 200771gao fengzhouyudu farongqu weiwei xiongyonghuadepartment of automobile engineering,beihang university,beijing 100083, chinaalgorithm of pretreatment on automobile body point cloud*abstract: as point cloud of one whole vehicle body has the traits of large geometric dimension, huge data and rigorous reverse precision, one pretreatment algorithm on automobile body point cloud is put forward. the basic idea of the registration algorithm based on the skeleton points is to construct the skeleton points of the whole vehicle model and the mark points of the separate point cloud, to search the mapped relationship between skeleton points and mark points using congruence triangle method and to match the whole vehicle point cloud using the improved iterative closed point (icp) algorithm. the data reduction algorithm, based on average square root of distance, condenses data by three steps, computing datasets average square root of distance in iw.pling: cube rd, sorting order according to the value computed from the first stop, choosing sampling percentage. tfe accuracy of the two algorithms above is proved by a registration and reduction exiuvple of whole vehicle point cloud of a certain light truck.key voros: reverst; engineering paint cloud registration skeleton point iterative closed point(icp) data reduction0introductionin reverse engineering system, the point cloud registration and the data reduction are two crucial cruxes of the point cloud pretreatment. the precision of registration and quality of reduction can affect the outcome of surface reconstruction significantly.the hypostasis of point cloud registration is to find proper mapping relation among several preparative registration point clouds and achieve iterative solution by coordinate transforming. the traditional registration algorithm is mainly divided into two categories: the geometry matching algorithm and the pinpoint registration algorithm. geometry matching algorithm, such as label matching algorithm11 and maximum likelihood registration algorithm21, constructs the mapping relation among point cloud by using the topology geometry character of point cloud or triangles. pinpoint registration algorithm mainly depends on numerical analysis such as interative closed point(icp) algorithm13 to realize. the precision of geometry matching algorithm is not very well while pinpoint registration algorithm has disadvantage in nailing down mapping relation of free-form point clouds. contraposing the advantage and disadvantage of the two algorithms above, this article proposes one algorithm for the whole vehicle body point cloud registration. this new algorithm searches mapping relation using congruence triangle principle to orient geometrically, and then completes precise registration by using improved accelerated iterative icp algorithm.in the aspect of the point cloud reduction, classical algorithms such as uniformity pane algorithm4 and delaminated sampling algorithm5 need to be improved. this article ameliorates the two algorithms above and puts forward point cloud reduction algorithm based on average square root of distance.1algorithm of point cloudregistrationmark pointthe mark points. after saving each mark points serial number and corresponding coordinate the whole vehicle mark point set is formed. we call it skeleton point cloud information g. we then scan the whole clay model by camega to get body partial point cloud wk including 4-5 mark points (i k 0(x00,z0).we can translate this problem into two-dimension issue by coordinate transform. now we assume the best-fit plane of the black circle is z on the z plane, let the center of the black circleis /(*, ji), radius is r, so we can get the circles equation(x-x;f+(y-ysf=s(1)the fitting point list is a ,(xy,)i = 1.2,- -,n. note eq. (i), which implies1.1 definition of mark point and skeleton pointat the very beginning, we should paste all the circular sign points showed in fig. 1 on the clay model uniformly (the centre of the circle of the sign points is called mark point). try best to avoid any three mark points forming into isosceles triangle. in the body reference frame, we can use coordinates measure machine(cmm) to measure each mark points coordinate exactly and number all this project is supported by provincial technology cooperation program of yunnan, china (no. 2003eaaaao0do43). received june 13, 2006; received in revised form march 9,2007; accepted may 28,2007f(x,y) = (x- v)2 + (y-yj)2 -r2 = 0(2)putting a,(x,), i = ,2,-,n, into eq. (2), we get/(w/) = (*/ - o2+(x - y*f r2 = r,(3)where /?,difference valueif making xh,#,2 minimum, we can get pxn,y0). then,piw-vo) should be translated into p0(x0,y0,z0) which is exact coordinate of mark point by coordinate reverse transform. 1994-2007 china academic journal electronic publishing house. all rights reserved, 72*gao feng, et al: algorithm of pretreatment on automobile body point cloud(4)1.3 projection of mark pointsit needs to ascertain the projection plane l in order to project the mark point from section 1.2 on the partial point cloud wk.the approach of fitting for plane l adopts point-normal mode as follows.ascertain the point: we take /0(x0,.)0,20) as sphere center and choose radius in order that 4-5 points are included in the sphere (the miscellaneous points and noise points are leached). we get_ 1 p=zpj j, which is nearest to p .ascertain the normal vector:(1)we need to construct triangle net71 of the data point hpf(2)after choosing ps and vicintl triangle ne*. we assumethere being , sides in the ft/angie net. then, we can calculateunit direction vector of each side as follows!/,/_ p,p.pipuuui /+iunit direction vector of one sidethe plane normal vector decided by the contiguous sides* = f,*fm kh(7)then we can get the normal vector of p,a = ltti kh|(8)h.(9)#=*,!/rgingruenxseiioi numberserial numberoftrianijbiggie slignof sideof acmei01,4,51,2,3201,2,101,2,51002,4,62,3,5we take five points as examples. as fig. 2 shows, five points could compose 10 triangles and 10 sides.fig. 2 triangle netthe approach of congruence triangle searching algorithm is as follows:(1) we should scan s* triangle table in order to judge whether this triangle is isosceles triangle. since isosceles triangle has two equal sides, it will bring indeterminacy in the searching process and it need to be excluded.(1) we need to scan the sides of triangles in g and 5* separately and calculate the side difference s. if s is less than the fixed limited sa (sa is usually 0.02 mm), two sides are consideredequivalent. here, we should record the serial number of the two sides in the g and sk and add one congruence triangles sign number on the triangle that contains this side in g. the triangle whose congruence triangle sign number is three is the triangle that equates one triangle in sk. by the recorded serial number, we can find this triangle 5*. by the above method, we can search all congruence triangles pairs in g and sk.(3) if searching out many pairs of triangles that are equivalent, the mean of s should be calculated. we should choose the pair of triangles whose average s is the least as the mapping triangle pair of g and s*.(3) reset the record, add one on the k and return (1). the cycle will continue until all pairs of triangles are searched out.l.s improved icp algorithm1cp algorithm generates iterative answer by transforming matrix to resolve multi-view matching problem. the basic idea of this algorithm is giving certain object point set p (the object required coordinated transformation) and reference point set q and making them aligned. we need first to find one point in q that is the nearest to the point in p and establish the mapping relation of the pair. through least square method, we can calculate one best coordinate transform (marked m) and make p=m (p). this process of iterative solution will continue until the precision is meeted. 1994-2007 china academic journal electronic publishing house. all rights reserved, chinese journal of mechanical engineering73*(10)the final coordinate transform is the composing of each transform.for two point clouds which have ten thousands or hundreds of thousands of points, each iterative needs to calculate each points corresponding point of reference point set in the aim point set. therefore, icp algorithm has the disadvantage of the low calculating speed. the calculating speed will be improved significantly if we choose the subset of the conjunct point set only and search all the points in the subset by icp algorithm.there are various ways to construct subsets, such as the character searching algorithm18 and the triangles impendent algorithm1. contraposing the particularity of body point cloud, this article establishes definite corresponding relation and improves icp algorithm by using the mapping triangle pairs in sk and g to construct subsets. the processing details are as follows.(1) construct aim subset. let the triangle formed by three points s,s2,si of the projected point set sk equate with the triangle constructed by three points gggi of skeleton point set g. we take up a points which are the nearest to si,s2,s t0 mt0 three planes. based on the three planes, vie can get three columnar districts according to the designed semiiiameter and height. the point set qa,qb,qc of the columnar districts is the aim subset corresponded with g1,g2,g, let the number of the three piont sets is a,b,c separately.(1) choose qt,qj,qk from point set qa,qh,qc separately (1ia,kjb,kksa, we should go back to (1) and transform qi,qj,qk (5)seek out the transform matrix t from point qqj,qk toggig) using least square method.(6)for each point set qu = (qt,qj,qk), there exits2 algorithm of point cloud reductionthe aim of the point cloud data reduction is not only to reduce the density of point cloud but also to guarantee the local uniformity of the point cloud reduction result. the higher the density of point cloud is, the smaller the average square root of the distance among points is. this algorithm firstly calculates the average square root of the distance between any points of finite space u and other points in u. secondly, arrange the average square root of each point by the order from small to large. finally, according to the defined sampling percent 8, the 8 percents points with the least average square root are deleted. consequently the point cloud reduction is accomplished. the algorithm is as following.(1) at the beginning we need to define sampling cube side length d and sampling percent ft then, the point cloud data is divided using the sampling cube with d length side as fig. 3 shows. make sure that there are an amount of data points in each sampling cube.i /i i i i i j-l_fig. 3 sampling cube(2) let pipjtpytp,) is one random point in cube, point set (?,(* .yz,x = 1,2,- -,n) is the point set except p in the cube. we can calculate the distance between p(px,py,pt) and any pointinfi(w,-z,)where rexp(u) = minfc - v-transform matrix(11)pq = /(j -x,)2 +(py-ytf+(pi-zf(14)lal=vw xj+(py -y2)2+(p,-y (is)v = (vv2,v3)vi - v2. v3coordinates of g, g2, g3(7) determine the convergence condition|exp( + l)-exp()|ne(12)pq=v - *)2+(py - yj+(1 -z-)2 d6)(3) then we can calculate the average square root djpqarts is about only one tenth of point cloud oneself acreage. atfe: checkout, the overlap error110 i* only 0.(135 mm and comsj. computer vision and image understanding volume, 2001,81(1): 117-142.2 chui haiti, rangarajan a. a new point matching algorithm for non-rigid registration. computer vision and image understanding volume, 2003,89(2-3): 114-141.3 timothee m. fast geometric matching for shape registrationp. swi-tzeland: university of neuchatel, 2002.4 lee k h, woo h, suk t. point data reduction using 3d gridj. international journal of advanced manufacturing technology, 2002, 18(3): 201-210.5 sun w, bradley c, zhang y f, et al. cloud data modeling employing a unified non-redundant triangular meshj. computer aided de