The polygonal approximation problem is a primary problem in computer graphics, pattern recognition, CAD/CAM, etc. In $R^2$, the cone intersection method (CIM) is one of the most eÆcient algorithms for approximating polygonal curves. With CIM Eu and Toussaint, by imposing an additional constraint and changing the given error criteria, resolve the three-dimensional weighted minimum number polygonal approximation problem with the parallel-strip error criterion (PS-WMN) under $L_2$ norm. In this paper, without any additional constraint and change of the error criteria, a CIM solution to the same problem with the line segment error criterion (LS-WMN) is presented, which is more frequently encountered than the PS-WMN is. Its time complexity is $O(n^3)$, and the space complexity is $O(n^2)$. An approximation algorithm is also presented, which takes $O(n^2)$ time and $O(n)$ space. Results of some examples are given to illustrate the eÆciency of these algorithms.

In this paper, we introduce a surface reconstruction method that can perform gracefully with non-uniformly-distributed, noisy, and even sparse data. We reconstruct the surface by estimating an implicit function and then obtain a triangle mesh by extracting an iso-surface from it. Our implicit function takes advantage of both the indicator function and the signed distance function. It is dominated by the indicator function at the regions away from the surface and approximates (up to scaling) the signed distance function near the surface. On one hand, it is well defined over the entire space so that the extracted iso-surface must lie near the underlying true surface and is free of spurious sheets. On the other hand, thanks to the nice properties of the signed distance function, a smooth iso-surface can be extracted using the approach of marching cubes with simple linear interpolations. More importantly, our implicit function can be estimated directly from an explicit integral formula without solving any linear system. This direct approach leads to a simple, accurate and robust reconstruction method, which can be paralleled with little overhead. We call our reconstruction method Gauss surface reconstruction. We apply our method to both synthetic and real-world scanned data and demonstrate the accuracy, robustness and efficiency of our method. The performance of Gauss surface reconstruction is also compared with that of several state-of-the-art methods.

We propose a framework for global registration of building scans. The first contribution of our work is to detect and use portals (e.g. doors and windows) to improve the local registration between two scans. Our second contribution is an optimization based on a linear integer programming formulation. We abstract each scan as a block and model the block registration as an optimization problem that aims at maximizing the overall matching score of the entire scene. We propose an efficient solution to this optimization problem by iteratively detecting and adding local constraints. We demonstrate the effectiveness of the proposed method on buildings of various styles and we show that our approach is superior to the current state of the art.

Manhattan-world urban scenes are common in the real world. We propose a fully automatic approach for reconstructing such scenes from 3D point samples. Our key idea is to represent the geometry of the buildings in the scene using a set of well-aligned boxes. We first extract plane hypothesis from the points followed by an iterative refinement step. Then, candidate boxes are obtained by partitioning the space of the point cloud into a non-uniform grid. After that, we choose an optimal subset of the candidate boxes to approximate the geometry of the buildings. The contribution of our work is that we transform scene reconstruction into a labeling problem that is solved based on a novel Markov Random Field formulation. Unlike previous methods designed for particular types of input point clouds, our method can obtain faithful reconstructions from a variety of data sources. Experiments demonstrate that our method is superior to state-of-the-art methods.

Object proposals are currently used for increasing the computational efficiency of object detection. We propose a novel adaptive pipeline for interleaving object proposals with object classification and use it as a formulation for asset detection. We first preprocess the images using a novel and efficient rectification technique. We then employ a particle filter approach to keep track of three priors, which guide proposed samples and get updated using classifier output. Tests performed on over 1000 urban images demonstrate that our rectification method is faster than existing methods without loss in quality, and that our interleaved proposal method outperforms current state-of-the-art. We further demonstrate that other methods can be improved by incorporating our interleaved proposals.