Qi-Xing Huang, Radomir Mech, and Nathan Carr. Optimizing Structure Preserving Embedded Deformation for Resizing Images and Vector Art. Computer Graphics Forum, Volume 29, number 7, (Pacific Graphics 2009 Conference Proceedings), to appear.

Smart deformation and warping tools play an important part in modern day geometric modeling systems. They allow existing content to be stretched or scaled while preserving visually salient information. To date, these techniques have primarily focused on preserving local shape details, not taking into account important global structures such as symmetry and line features. In this work we present a novel framework that can be used to preserve the global structure in images and vector art. Such structures include symmetries and the spatial relations in shapes and line features in an image. Central to our method is a new formulation of preserving structure as an optimization problem. We use novel optimization strategies to achieve the interactive performance required by modern day modeling applications. We demonstrate the effectiveness of our framework by performing structure preservation deformation of images and complex vector art at interactive rates.

B. Thuswaldner, Simon Flöry, R. Kalasek, Michael Hofer, Qi-Xing Huang, and H. Thür. Digital Anastylosis of the Octagon in Ephesos. Journal on Computing and Cultural Heritage (JOCCH), 2009, Volume 2, Issue 1, 1-27.

Anastylosis is the archaeological and architectural reconstruction of a ruined monument at the historic site after careful study of the remaining original elements. We pose research challenges concerning 3D technologies that are needed to support the anastylosis of cultural heritage monuments. Based on current state-of-the-art research we define challenges to improve and simplifydata collection, digital artefact reconstruction, digital reassembly of existing fragments, and the digital completion of missing fragments. We demonstrate progress that is made in the outlined research directions at hand of the currently running anastylosis of the Octagon monument in Ephesos, Turkey. Our focus is on methods that belong to geometry processing .

Qi-Xing Huang, Martin Wiche, Bart Adams, and Leonias J. Guibas. Shape Decomposition Using Modal Analysis . Computer Graphics Forum 28 (2) (Proceedings of Eurographics), 2009

We introduce a novel algorithm that decomposes a deformable shape into meaningful parts requiring only a single input pose. Using modal analysis, we are able to identify parts of the shape that tend to move rigidly. We define a deformation energy on the shape, enabling modal analysis to find the typical deformations of the shape. We then find a decomposition of the shape such that the typical deformations can be well approximated with deformation fields that are rigid in each part of the decomposition. We optimize for the best decomposition, which captures how the shape deforms. A hierarchical refinement scheme makes it possible to compute more detailed decompositions for some parts of the shape. Although our algorithm does not require user intervention, it is possible to control the process by directly changing the deformation energy, or interactively refining the decomposition as necessary. Due to the construction of the energy function and the properties of modal analysis, the computed decompositions are robust to changes in pose as well as meshing, noise, and even imperfections such as small holes in the surface.

Helmut Pottmann, Johannes Wallner, Qi-Xing Huang, and Yong-Liang Yang. Integral invariants for robust geometry processing. Comput. Aided Geom. Design 26 (2009), 37-60.

Differential invariants of curves and surfaces such as curvatures and their derivatives play a central role in Geometry Processing. They are, however, sensitive to noise and minor perturbations and do not exhibit the desired multi-scale behaviour. Recently, the relationships between differential invariants and certain integrals over small neighborhoods have been used to define efficiently computable integral invariants which have both a geometric meaning and useful stability properties. This paper considers integral invariants defined via distance functions, and the stability analysis of integral invariants in general. Such invariants proved useful for many tasks where the computation of shape characteristics is important. A prominent and recent example is the automatic reassembling of broken objects based on correspondences between fracture surfaces.

We present a robust and efficient algorithm for the pairwise non-rigid registration of partially overlapped 3D surfaces. Our approach treats non-rigid registration as an optimization problem and solves it by alternating between correspondence and deformation optimization. Assuming approximately isometric deformations, robust correspondences are generated using a pruning mechanism based on geodesic consistency. We iteratively learn an appropriate deformation discretization from the current set of correspondences and use it to update the correspondences in the next iteration. Our algorithm is able to register partially similar point clouds that undergo large deformations, in just a few seconds. We demonstrate the potential of our algorithm in various applications suchas example based articulated segmentation, and shape interpolation.

Qi-Xing Huang, Martin Wiche, Bart Adams, and Leonidas J. Guibas. Segmentation of Articulated Models from a Single Pose. Proc. 6th Eurographics Symposium on Geometry Processing, Copenhagen, Denmark, 2008, poster.

We introduce a novel shape segmentation algorithm that computes meaningful segmentations of articulated shapes from a single pose. Using an energy function that favors articulated motions, we use spectral analysis on the Hessian of the deformation energy to compute typical deformation modes of the shape. We then approximate the eigenmodes by piecewise rigid deformation fields. Nodes undergoing the same rigid transformation form the patches of our segmentation. The result is a segmentation that captures how an articulated shape deforms. A hierarchical refinement scheme makes it possible to compute more detailed segmentations for parts of the shape. We use this segmentation and the knowledge about typical deformations to extract a skeleton. The algorithm can be applied to meshes as well as point clouds, and we show that the segmentation is robust to noise, and even imperfections such as holes in the surface.

Qi-Xing Huang, Bart Adams, and Michael Wand. Bayesian Surface Reconstruction via Iterative Scan Alignment to an Optimized Prototype. In: Proc. 5th Eurographics Symposium on Geometry Processing, Barcelona, Spain, 2007.

This paper introduces a novel technique for joint surface reconstruction and registration. Given a set of roughly aligned noisy point clouds, it outputs a noise-free and watertight solid model. The basic idea of the new technique is to reconstruct a prototype surface at increasing resolution levels, according to the registration accuracy obtained so far, and to register all parts with this surface. We derive a non-linear optimization problem from a Bayesian formulation of the joint estimation problem.

The prototype surface is represented as a partition of unity implicit surface, which is constructed from piecewise quadratic functions defined on octree cells and blended together using B-spline basis functions, allowing the representation of objects with arbitrary topology with high accuracy. We apply the new technique to a set of standard data sets as well as especially challenging real-world cases. In practice, the novel prototype surface based joint reconstruction-registration algorithm avoids typical convergence problems in registering noisy range scans and substantially improves the accuracy of the final output.

Michael Wand, Phillp Jenke, Qi-Xing Huang, Martin Bokeloh, Leonidas J. Guibas, and A. Schilling. Reconstruction of Deforming Geometry from Time-Varying Point Clouds. In: Proc. 5th Eurographics Symposium on Geometry Processing, Barcelona, Spain, 2007.

In this paper, we describe a system for the reconstruction of deforming geometry from a time sequence of unstructured, noisy point clouds, as produced by recent real-time range scanning devices. Our technique reconstructs both the geometry and dense correspondences over time. Using the correspondences, holes due to occlusion are filled in from other frames. Our reconstruction technique is based on a statistical framework: The reconstruction should both match the measured data points and maximize prior probability densities that prefer smoothness, rigid deformation and smooth movements over time. The optimization procedure consists of an inner loop that optimizes the 4D shape using continuous numerical optimization and an outer loop that infers the discrete 4D topology of the data set using an iterative model assembly algorithm. We apply the technique to a variety of data sets, demonstrating that the new approach is capable of robustly retrieving animated models with correspondences from data sets suffering from significant noise, outliers and acquisition holes.

Simon Flöry, Michael Hofer, Barbara Thuswaldner and Qi-Xing Huang. Reassembling Ancient Monuments via Constrained Registration. SIGGRAPH 2007 poster, San Diego, August 2007.

As demonstrated in our work [Huang et al. 2006] fracture surfaces of broken solids contain rich geometric information that are sufficient for reassembly based on geometric matching. However, the task of reassembling an ancient monument from its building blocks differs significantly from that of reassembling a broken solid. These building blocks are fragments in a much looser sense as opposing faces of neighboring stones do not contain the rich geometric features of fracture surfaces. The contribution of the present work is an algorithm for automatic reassembly of ancient monuments guided by high-level features such as edges, clamp holes, or ornaments. The data we use to test our new method on comprises the remaining stones of the Octagon (Fig. 1, top, right) monument in Ephesos, Turkey, which fell apart a thousand years ago and whose reconstruction is currently undertaken.

Helmut Pottmann, Qi-Xing Huang, Yong-Liang Yang, Shi-Min Hu. Geometry and Convergence Analysis of Algorithms for Registration of 3D Shapes. International Journal of Computer Vision 67(3): 277-296 (2006).

The computation of a rigid body transformation which optimally aligns a set of measurement points with a surface and related registration problems are studied from the viewpoint of geometry and optimization.We provide a convergence analysis for widely used registration algorithms such as ICP, using either closest points (Besl and McKay [2]) or tangent planes at closest points (Chen and Medioni [4]), and for a recently developed approach based on quadratic approximants of the squared distance function [24]. ICP based on closest points exhibits local linear convergence only. Its counterpart which minimizes squared distances to the tangent planes at closest points is a Gauss-Newton iteration; it achieves local quadratic convergence for a zero residual problem and { if enhanced by regularization and step size control{ comes close to quadratic convergence in many realistic scenarios. Quadratically convergent algorithms are based on the approach in [24]. The theoretical results are supported by a number of experiments; there, we also compare the algorithms with respect to global convergence behavior, stability and running time.

Qi-Xing Huang. Simon Flöry, Nathsha Gelfand, Michael Hofer and Helmut Pottmann. Reassembling Fractured Objects by Geometric Matching. ACM Trans. Graphics 25(3), 569-578, (2006), Proc. SIGGRAPH 2006.

We present a system for automatic reassembly of broken 3D solids. Given as input digital models of the broken fragments, we analyze the geometry of the fracture surfaces to find a globally consistent reconstruction of the original object. Our reconstruction pipeline consists of a graph-cuts based segmentation algorithm for identifying potential fracture surfaces, feature-based robust global registration for pairwise matching of fragments, and simultaneous constrained local registration of multiple fragments. We develop several new techniques in the area of geometry processing, including the novel integral invariants for computing multi-scale surface characteristics, registration based on forward search techniques and surface consistency, and a non-penetrating iterated closest point algorithm. We illustrate the performance of our algorithms on a number of real-world examples.

Helmut Pottmann, Qi-Xing Huang, Yong-Liang Yang and Stephan Kölpl. Integral invariants for robust geometry processing. Geometry Preprint 146, Vienna University of Technology, December 2005.

Differential invariants of curves and surfaces such as curvatures and their derivatives play a central role in Geometry Processing. They are, however, sensitive to noise and minor perturbations and do not exhibit the desired multi-scale behaviour. Recently, the relationships between differential invariants and certain integrals over small neighbourhoods have been used to de[1]ne ef[1]ciently computable integral invariants which have both a geometric meaning and useful stability properties. This paper considers integral invariants de[1]ned via distance functions, and the stability analysis of integral invariants in general. Such invariants proved useful for many tasks where the computation of shape characteristics is important. A prominent and recent example is the automatic reassembling of broken objects based on correspondences between fracture surfaces.

Qi-Xing Huang . Helmut Pottmann. Automatic and Robust Multi-view Registration. Geometry Preprint 152, Vienna University of Technology, December 2005.

In this paper, we present a new approach to robust global and local registration of multiple 3D scans. We begin with the computation of a series of integral invariants. These are used for extracting from each scan a few important clusters. Based on cluster–cluster correspondences, we introduce a reliable and efficient pairwise surface matching algorithm. Global multiple view registration is then done by recursive application of pairwise surface matching. In particular, we focus on the situation in which one scan can only be correctly matched if several scans are already aligned as a prior. Once all scans are coarsely aligned, we devise a numerical optimization algorithm for local registration, which simultaneously improves the positions of the individual scans with help of a dynamic reference surface.

Helmut Pottmann, Qi-Xing Huang, Yong-Liang Yang and Shi-Min Hu. Geometry and convergence analysis of algorithms for registration of 3D shapes. Geometry Preprint 117, Vienna University of Technology, August 2004.

The computation of a rigid body transformation which optimally aligns a set of measurement points with a surface and related registrations problems are studied fromt the viewpoint of geometry and optimization. We provide a convergence analysis for known registration algorithms such as ICP and introduce new algorithms with an improved local and global convergence behavior. Most of our work deals with the fundamental problem of registering two views (scans, surfaces) with unknown correspondences. It is then shown how to extend the concepts to the simultaneous registration of an arbitrary number of views.