Piecewise Approximation Method And Its Applications On Point Cloud Processing

Piecewise approximation method divides an approximation problem to a given function into multiple ones with smaller regions,and then transforms to how to obtain the optimal partitions and the approximating functions over subregions.This dissertation firstly presents a piecewise optimal linear approximation method combined with power diagrams in continuous domains,from the view of generating anisotropic convex cell complexes.Specifically,the domain of given function is tessellated by a power diagram,from which an optimal linear polynomial is built to approximate the given function over each sub-region,and the error between them is treated as the objective function.Its minimization corresponds to the optimal power diagram and the polynomials,which is achieved by using an improved global optimization framework that iteratively adopts local search and perturbation to detect a lower minima of the objective function.Compared to existing methods,the proposed method is more general since it extends the given functions from convex type to arbitrary type,including non-convex functions.And it generates cell complexes with higher quality,lower approximation error and better cell anisotropy conforming to the Hessian matrix of given function;In addition,it produces a uniform point sets when the given function is a paraboloid.For the applications,because of the strong ability of the proposed method to generate high quality partitions and uniform point sets,this dissertation applies it to provide new solutions for supervoxels generation and resampling of three dimensional point clouds.In the former case,piecewise plane approximations are developed.Each supervoxel is firstly evaluated by planar degree,normal similarity and compactness of member points,based on which the objective function is formulated as the accumulation of all supervoxels’ quality metric.Therefore,a heuristic global searching algorithm is developed to minimize the objective function and the corresponding supervoxels results with feature preserving and regular boundaries.In the latter case,each resampling point is viewed as the approximation of local surface of original point cloud,which actually forms the objective function of piecewise position approximations,which can be minimized by using Lloyd’s method and Anderson acceleration to obtain high quality results as uniform as possible.Through the two applications,this dissertation demonstrates the robustness and efficacy of the proposed method.