Software

 

Surface Approximation via Asymptotic Optimal Geometric Partition

Yiqi Cai, Xiaohu Guo, Yang Liu, Wenping Wang, Weihua Mao, Zichun Zhong

Abstract - In this paper, we present a novel method on surface partition from the perspective of approximation theory. Different from previous shape proxies, the ellipsoidal variance proxy is proposed to penalize the partition results falling into disconnected parts. On its support, the Principle Component Analysis (PCA) based energy is developed for asymptotic cluster aspect ratio and size control. We provide the theoretical explanation on how the minimization of the PCA-based energy leads to the optimal asymptotic behavior for approximation. Moreover, we show the partitions on densely sampled triangular meshes converge to the theoretic expectations. To evaluate the effectiveness of surface approximation, polygonal/triangular surface remeshing results are generated. The experimental results demonstrate the high approximation quality of our method.

[Citation] Yiqi Cai, Xiaohu Guo, Yang Liu, WenpingWang, Weihua Mao, Zichun Zhong, "Surface Approximation via Asymptotic Optimal Geometric Partition", to appear in IEEE Transactions on Visualization and Computer Graphics, 2016.

Paper Download | Code


Anisotropic Superpixel Generation Based on Mahalanobis Distance

Yiqi Cai, Xiaohu Guo

Abstract - Superpixels have been widely used as a preprocessing step in various computer vision tasks. Spatial compactness and color homogeneity are the two key factors determining the quality of the superpixel representation. In this paper, these two objectives are considered separately and anisotropic superpixels are generated to better adapt to local image content. We develop a unimodular Gaussian generative model to guide the color homogeneity within a superpixel by learning local pixel color variations. It turns out maximizing the log-likelihood of our generative model is equivalent to solving a Centroidal Voronoi Tessellation (CVT) problem. Moreover, we provide the theoretical guarantee that the CVT result is invariant to affine illumination change, which makes our anisotropic superpixel generation algorithm well suited for image/video analysis in varying illumination environment. The effectiveness of our method in image/video superpixel generation is demonstrated through the comparison with other state-of-the-art methods.

[Citation] Yiqi Cai, Xiaohu Guo, "Anisotropic Superpixel Generation Based on Mahalanobis Distance", to appear in Computer Graphics Forum (Proceedings of PG 2016), 2016.

Paper Download | Code


Point-Based Manifold Harmonics

Yang Liu, Balakrishnan Prabhakaran, Xiaohu Guo

Abstract - This paper proposes an algorithm to build a set of orthogonal Point-Based Manifold Harmonic Bases (PB-MHB) for spectral analysis over point-sampled manifold surfaces. To ensure that PB-MHB are orthogonal to each other, it is necessary to have symmetrizable discrete Laplace-Beltrami Operator (LBO) over the surfaces. Existing converging discrete LBO for point clouds, as proposed by Belkin et al [1], is not guaranteed to be symmetrizable. We build a new point-wisely discrete LBO over the point-sampled surface that is guaranteed to be symmetrizable, and prove its convergence. By solving the eigen problem related to the new operator, we define a set of orthogonal bases over the point cloud. Experiments show that the new operator is converging better than other symmetrizable discrete Laplacian operators (such as graph Laplacian) defined on point-sampled surfaces, and can provide orthogonal bases for further spectral geometric analysis and processing tasks.

[Citation] Yang Liu, Balakrishnan Prabhakaran, Xiaohu Guo, "Point-Based Manifold Harmonics," to appear in IEEE Transactions on Visualization and Computer Graphics, 2011.

Paper Download | Code


GPU-Assisted Computation of Centroidal Voronoi Tessellation

Guodong Rong, Yang Liu, Wenping Wang, Xiaotian Yin, Xianfeng David Gu, Xiaohu Guo

gpucvt.png

Abstract - Centroidal Voronoi tessellations (CVT) are widely used in computational science and engineering. The most commonly used method is Lloyd’s method, and recently the L-BFGS method is shown to be faster than Lloyd’s method for computing the CVT. However, these methods run on the CPU and are still too slow for many practical applications. We present techniques to implement these methods on the GPU for computing the CVT on 2D planes and on surfaces, and demonstrate significant speedup of these GPU-based methods over their CPU counterparts. For CVT computation on a surface, we use a geometry image stored in the GPU to represent the surface for computing the Voronoi diagram on it. In our implementation a new technique is proposed for parallel regional reduction on the GPU for evaluating integrals over Voronoi cells.

[APA Style Citation] Rong, G., Liu, Y., Wang, W., Yin, X., Gu, X., & Guo, X. (2010). GPU-Assisted Computation of Centroidal Voronoi Tessellation. Visualization and Computer Graphics, IEEE Transactions on, 17(3), 345-356. doi: 10.1109/TVCG.2010.53

[MLA Style Citation] Rong, Guodong, Yang Liu, Wenping Wang, Xiaotian Yin, Xianfeng David Gu and Xiaohu Guo. "GPU-Assisted Computation of Centroidal Voronoi Tessellation." Visualization and Computer Graphics, IEEE Transactions on 17.3 (2010): 345-356. doi: 10.1109/TVCG.2010.53

Paper Download | Code for 2D CVT | Code for Surface CVT