The skeleton of a 2D shape is an important geometric structure in pattern analysis and computer vision. In this paper we study the skeleton of a 2D shape in a two-manifold M, based on a geodesic metric. We present a formal definition of the skeleton S(\Omega) for a shape V in M and show several properties that make S(\Omega) distinct from its Euclidean counterpart in R^2. We further prove that for a shape sequence {\Omega_i} that converge to a shape V in M, the mapping \Omega\rightarrow S(\Omega_i) is lower semi-continuous. A direct application of this result is that we can use a set P of sample points to approximate the boundary of a 2D shape V in M, and the Voronoi diagram of P inside \Omega\subset M gives a good approximation to the skeleton S(\Omega). Examples of skeleton computation in topography and brain morphometry are illustrated.

In this paper, we consider the problem of approximating the longest path in a grid graph that possesses a square-free 2-factor. By (1) analyzing several characteristics of four types of cross cells and (2) presenting three cycle-merging operations and one extension operation, we propose an algorithm that finds in an n-vertex grid graph G, a long path of length at least 5/6 n + 2. Our approximation algorithm runs in quadratic time. In addition to its theoretical value, our work has also an interesting application in image-guided maze generation.

Point cloud is the most fundamental representation of 3D geometric objects as it provides the most exact information of them. Analyzing and processing point cloud surfaces is important in computer graphics and computer vision. However, most of the existing algorithms for surface analysis require connectivity information. Therefore, it is desirable to develop a mesh structure on point clouds. This task can be simplified with the aid of a parameterization. In particular, conformal parameterizations are advantageous in preserving the geometric information of the point cloud data. In this paper, we extend a state-of-the-art spherical conformal parameterization algorithm for genus-0 closed meshes to the case of point clouds, using an improved approximation of the Laplace-Beltrami operator on data points. Then, we propose an iterative scheme called the North-South reiteration for achieving a spherical conformal parameterization. A balancing scheme is introduced to enhance the distribution of the spherical parameterization. High quality triangulations and quadrangulations can then be built on the point clouds with the aid of the parameterizations. Also, the meshes generated are guaranteed to be genus-0 closed meshes. Moreover, using our proposed spherical conformal parameterization, multilevel representations of point clouds can be easily constructed. Experimental results demonstrate the effectiveness of our proposed framework.

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.

There is an unmet medical need to identify neuroimaging biomarkers that allow us to accurately diagnose and monitor Alzheimer's disease (AD) at its very early stages and to assess the response to AD-modifying therapies. To a certain extent, volumetric and functional magnetic resonance imaging (fMRI) studies can detect changes in structure, cerebral blood flow, and blood oxygenation that distinguish AD and mild cognitive impairment (MCI) subjects from healthy control (HC) subjects. However, it has been challenging to use fully automated MRI analytic methods to identify potential AD neuroimaging biomarkers. We have thus proposed a method based on independent component analysis (ICA) for studying potential AD-related MR image features that can be coupled with the use of support vector machine (SVM) for classifying scans into categories of AD, MCI, and HC subjects. The MRI data were selected from