No abstract uploaded!

Computing centroidal Voronoi tessellations (CVT) has many applications in computer graphics. The existing methods, such as the Lloyd algorithm and the quasi-Newton solver, are efficient and easy to implement; however, they compute only the local optimal solutions due to the highly non-linear nature of the CVT energy. This paper presents a novel method, called manifold differential evolution (MDE), for computing globally optimal geodesic CVT energy on triangle meshes. Formulating the mutation operator using discrete geodesics, MDE naturally extends the powerful differential evolution framework from Euclidean spaces to manifold domains. Under mild assumptions, we show that MDE has a provable probabilistic convergence to the global optimum. Experiments on a wide range of 3D models show that MDE consistently outperforms the existing methods by producing results with lower energy. Thanks to its intrinsic and global nature, MDE is insensitive to initialization and mesh tessellation. Moreover, it is able to handle multiply-connected Voronoi cells, which are challenging to the existing geodesic CVT methods.

Intrinsic Delaunay triangulation (IDT) naturally generalizes Delaunay triangulation from R^2 to curved surfaces. Due to many favorable properties, the IDT whose vertex set includes all mesh vertices is of particular interest in polygonal mesh processing. To date, the only way for constructing such IDT is the edge-flipping algorithm, which iteratively flips non-Delaunay edges to become locally Delaunay. Although this algorithm is conceptually simple and guarantees to terminate in finite steps, it has no known time complexity and may also produce triangulations containing faces with only two edges. This article develops a new method to obtain proper IDTs on manifold triangle meshes.We first compute a geodesic Voronoi diagram (GVD) by taking all mesh vertices as generators and then find its dual graph. The sufficient condition for the dual graph to be a proper triangulation is that all Voronoi cells satisfy the so-called closed ball property. To guarantee the closed ball property everywhere, a certain sampling criterion is required. For Voronoi cells that violate the closed ball property, we fix them by computing topologically safe regions, inwhich auxiliary sites can be addedwithout changing the topology of theVoronoi diagram beyond them.Given a meshwith n vertices, we prove that by adding at most O(n) auxiliary sites, the computed GVD satisfies the closed ball property, and hence its dual graph is a proper IDT. Our method has a theoretical worst-case time complexity O(n^2 + tn log n), where t is the number of obtuse angles in the mesh. Computational results show that it empirically runs in linear time on real-world models.

Superpixels are perceptually meaningful atomic regions that can effectively capture image features. Among various methods for computing uniform superpixels, simple linear iterative clustering (SLIC) is popular due to its simplicity and high performance. In this paper, we extend SLIC to compute content-sensitive superpixels, i.e., small superpixels in content-dense regions with high intensity or colour variation and large superpixels in content-sparse regions. Rather than using the conventional SLIC method that clusters pixels in R^5, we map the input image I to a 2-dimensional manifoldMR5, whose area elements are a good measure of the content density in I. We propose a simple method, called intrinsic manifold SLIC (IMSLIC), for computing a geodesic centroidal Voronoi tessellation (GCVT)—a uniform tessellation—onM, which induces the content-sensitive superpixels in I. In contrast to the existing algorithms, IMSLIC characterizes the content sensitivity by measuring areas of Voronoi cells onM. Using a simple and fast approximation to a closed-form solution, the method can compute the GCVT at a very low cost and guarantees that all Voronoi cells are simply connected. We thoroughly evaluate IMSLIC and compare it with eleven representative methods on the BSDS500 dataset and seven representative methods on the NYUV2 dataset. Computational results show that IMSLIC outperforms existing methods in terms of commonly used quality measures pertaining to superpixels such as compactness, adherence to boundaries, and achievable segmentation accuracy. We also evaluate IMSLIC and seven representative methods in an image contour closure application, and the results on two datasets, WHD and WSD, show that IMSLIC achieves the best foreground segmentation performance.

We propose a simple fast spectral method for the Boltzmann collision operator with general collision kernels. In contrast to the direct spectral method [L. Pareschi and G. Russo, SIAM J. Numer. Anal., 37 (2000), pp. 1217–1245; I. M. Gamba and S. H. Tharkabhushanam, J. Comput. Phys., 228 (2009), pp. 2012–2036], which requires O(N6) memory to store precomputed weights and has O(N6) numerical complexity, the new method has complexity O(MN4 log N), where N is the number of discretization points in each of the three velocity dimensions and M is the total number of discretization points on the sphere and M ≪ N2. Furthermore, it requires no precomputation for the variable hard sphere model and only O(MN4) memory to store precomputed functions for more general collision kernels. Although a faster spectral method is available [C. Mouhot and L. Pareschi, Math. Comp., 75 (2006), pp. 1833–1852] (with complexity O(MN3 logN)), it works only for hard sphere molecules, thus limiting its use for practical problems. Our new method, on the other hand, can apply to arbitrary collision kernels. A series of numerical tests is performed to illustrate the efficiency and accuracy of the proposed method.