Images and Geometry

Leader of the group: Dr. Renjie Chen

 

Vision and Research Strategy

As its core mission, computer graphics endeavors to deliver natural-looking and convincing graphic contents, such as images, videos and 3D models for various applications, including design, entertainment, education, simulation, etc. In many cases,  "natural-looking" can be interpreted as low distortion with respect to some reference. Depending on the application, the distortion can be measured as the amount of feature stretching, non-feature noise, change of scale, self-overlapping, and so on. As distortions can largely affect human perception of the contents, we want to generate images and shapes with no distortion or controlled amount of distortions, while satisfying the user-defined constraints for various applications. My research has been mainly focusing on designing theoretically sound and computationally efficient algorithms for geometry processing and its applications in image editing.

 

Research Areas and Achievements

Shape Modeling

Harmonic maps are extensively used in geometry processing applications, as they possess various nice properties such as smoothness. We established a sufficient and necessary condition for a harmonic mapping of any (possibly multiply-connected) domain to have bounded conformal and isometric distortions, solely based on the boundary behavior of the mapping. We construct a harmonic linear subspace which allows us to cast the locally injective mapping problem as a boundary value problem. Within this low dimensional subspace, the induced map and its differentials can be expressed in closed-form leading to simple, efficient and accurate evaluation. Moreover, we provide a closed-form recipe for a positive projection of the Hessian of the isometric energies, and this leads to effective-and-efficient Newton iterations. Our algorithm is specifically designed for modern parallel graphics hardware architectures, making it the first GPU-based locally injective deformation method.

 

Divergence-Based Distance Functions

Distance functions can be used to automatically plan a gradient-descent path towards a given target point in the domain, avoiding obstacles that may be present. A key requirement from such distance functions is the absence of spurious local minima, and this has led to the common use of harmonic potential functions. This choice guarantees the absence of spurious minima, but is slow to compute. To alleviate this problem, we propose a family of novel divergence distances based on f-divergence of the Poisson kernel. We show that divergence distances generate paths identical to those generated by the potential function. However using divergence distances has a significant computational advantage, as, following a pre-processing stage, they may be computed online up to an order of magnitude faster than the others. Additionally, the computation is "embarrassingly parallel", so may be implemented on a GPU with up to three orders of magnitude speedup.

We prove that the discrete version of the f-divergence distance also delivers, based on reduced coordinate vectors, which are the harmonic measures of a partition of the boundary into segments. Since in practice, the path is often restricted to follow the edges of a discrete network defined on a finite set of sites, any method that works well in the continuous setting must be discretized appropriately to preserve the important properties of the continuous case. We show how to define a network connecting a finite set of sites, such that a greedy routing algorithm based on our reduced coordinates is guaranteed to generate a path in the network between any two sites.

 

Fastest-Path Computations

In the age of real-time online traffic information and GPS-enabled devices, fastest-path computations in a road network graph, where each edge is weighted by a  "travel time" value, are becoming a standard feature of many navigation-related applications. To support this, efficient computation of these paths in very large road networks is critical. Fastest paths may be computed as minimal-cost paths in a weighted graph, but traditional minimal-cost path algorithms based on variants of the classic Dijkstra algorithm do not scale well, as in the worst case they may traverse the entire graph. A common improvement, which can dramatically reduce the number of traversed graph vertices, is the A* algorithm, which requires a good heuristic lower bound on the minimal cost. We introduce a simple, but very effective and highly scalable, heuristic function based on a small number of values assigned to each graph vertex. The values are based on graph separators and computed efficiently in a preprocessing stage. Experimental results show that our heuristic provides estimates of the minimal cost which are superior to those of other heuristics, and when used in the A* algorithm, this heuristic can reduce the number of vertices traversed by an order of magnitude compared to other heuristics.