Symmetry-Based Structure Analysis And Processing Of Man-Made Objects

An ever growing number of digital 3D models with complex shapes and representations have been stored today in many shape repositories. The analysis, understanding, and ultimately effective utilization, of these model collections have become a major effort in computer graphics research. Specifically, the study of man-made objects has drawn a great deal of interest recently, due in part to their rich varieties and large degrees of intra-class variations. Man-made objects usually comprise numerous parts and sub-parts. Relations among the parts such as adjacency, inclusion, repetition, parallelism, and symmetry collectively contribute to a description of the part structure of an object.The efficiency and effectiveness of a large number of shape analysis and processing methods are based on the structural information of the shape being analyzed or processed. For example, the symmetry information of an object may be used for mesh compression, segmentation, shape matching or mesh optimization; mesh editing algorithm for man-made objects should respect more general structural information. Furthermore, structural information also bridges the gap between geometry of a given 3D model and its semantics and functions. Thus, structural information is the key to analysis and processing of man-made objects. However, due to some specific modeling techniques, such as reconstruction from 3D scan data, or some shape processing operations applied on the models, structural information is not always available in the input models. Therefore, we attempt to solve a very challenging problem in our study, which is extracting the structure information from the input models of man-made shapes using only their geometric information. The main contributions of our study include:1. We propose a new structural representation for single man-made objects– symmetry hierarchy. Man-made objects typically have two characteristics. First, man-made objects are characterized by high levels of regularity and repetition as reflected by their different forms of symmetry. Second, they are often assembled from parts and sub-parts recursively. We conbine these two defining characteristics of man-made shapes: symmetry and hierarchical structures, to define a novel high-level representation of shapes called symmetry hierarchy. Specifically, we model a 3D man-made object as a symmetry-induced, hierarchical organization of its constituent parts. This representation utilizes the symmetry grouping rules in human perception and shape semantics, so it is able to reflect the perceptual and functional organization of model parts.2. We propose an iterative graph contraction algorithm base on a set of precedence rules to extract the symmetry hierarchy. Inferring a natural and meaningful hierarchical organization of a shape's parts is challenging even with a perfect shape segmentation and all the low-level symmetries detected. Computationally, a modest number of parts already lead to a large search space. Moreover, it's difficult to define a rigorous objective function for the optimal hierarchical organization of the input model, since it involves proper modeling of a cognitive process of human. To address these difficulties, we propose a recursive graph contraction algorithm to extract the symmetry hierarchy from the input model. The order of graph contraction is dictated by a set of precedence rules designed primarily to respect the law of symmetry in perceptual grouping and the principle of compactness of representation.3. We use symmetry hierarchy in performing several structural shape analysis and processing tasks. We apply symmetry hierarchy of man-made shapes in several structural analysis and processing tasks for man-made objects. First, we show that symmetry hierarchy naturally implies a hierarchical segmentation that is more meaningful than those produced by local geometric considerations. Then, we develop applications of symmetry hierarchies for structural shape editing and detection of upright orientations for man-made objects. We also demonstrate that the hierarchiecal segmentation and upright orientation obtained facilitates intro-class semantic labeling of shapes. The experimental results of these applications show that our emphasis on structure rather than geometric measures such as size and angle is particularly suited to man-made objects.4. We propose consistent structural hierarchies for man-made object sets. We define consistent structural hierarchies for a set of man-made objects that possess similar functionalities (i.e., belonging to the same family). This work is based on the key observation that objects that are designed to serve similar functions often possess a great deal of structural similarity. The key idea is that by analyzing such a set collectively, we gain knowledge about the commonality among the set of shape structures.5. We proposed an evolutionary algorithm framework for consistent structural hierarchy computation. In order to combine the per-shape structural information and the inter-shape part structure correspondence, we first generate multiple candidate structural hierarchies for each object in the input set. Then, we propose an evolutionary algorithm to extract a consistent structural hierarchy for the entire set. The algorithm iteratively evolves the individuals in the population composed of all the candidate structural hierarchies in a way that the individuals in the resulting population possess maximal similarity to each other. The experimental results show that the proposed algorithm successfully extracts consistent structural hierarchies for input sets of several different families of man-made objects, despite of the extremely large intra-class geometrical and topological variations.