Premium
Microtiles: Extracting Building Blocks from Correspondences
Author(s) -
Kalojanov Javor,
Bokeloh Martin,
Wand Michael,
Guibas Leonidas,
Seidel HansPeter,
Slusallek Philipp
Publication year - 2012
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/j.1467-8659.2012.03165.x
Subject(s) - homogeneous space , equivalence class (music) , set (abstract data type) , computer science , mathematics , class (philosophy) , theoretical computer science , point (geometry) , object (grammar) , similarity (geometry) , pairwise comparison , matching (statistics) , equivalence (formal languages) , representation (politics) , artificial intelligence , image (mathematics) , pure mathematics , geometry , programming language , statistics , politics , political science , law
In this paper, we develop a theoretical framework for characterizing shapes by building blocks. We address two questions: First, how do shape correspondences induce building blocks? For this, we introduce a new representation for structuring partial symmetries (partial self‐correspondences), which we call “microtiles”. Starting from input correspondences that form point‐wise equivalence relations, microtiles are obtained by grouping connected components of points that share the same set of symmetry transformations. The decomposition is unique, requires no parameters beyond the input correspondences, and encodes the partial symmetries of all subsets of the input. The second question is: What is the class of shapes that can be assembled from these building blocks? Here, we specifically consider r‐similarity as correspondence model, i.e., matching of local r‐neighborhoods. Our main result is that the microtiles of the partial r‐symmetries of an object S can build all objects that are ( r +ε)‐similar to S for any ε >0. Again, the construction is unique. Furthermore, we give necessary conditions for a set of assembly rules for the pairwise connection of tiles. We describe a practical algorithm for computing microtile decompositions under rigid motions, a corresponding prototype implementation, and conduct a number of experiments to visualize the structural properties in practice.