Microtiles: Extracting Building Blocks from Correspondences

dc.contributor.authorKalojanov, Javoren_US
dc.contributor.authorBokeloh, Martinen_US
dc.contributor.authorWand, Michaelen_US
dc.contributor.authorGuibas, Leonidasen_US
dc.contributor.authorSeidel, Hans-Peteren_US
dc.contributor.authorSlusallek, Philippen_US
dc.contributor.editorEitan Grinspun and Niloy Mitraen_US
dc.date.accessioned2015-02-28T07:44:06Z
dc.date.available2015-02-28T07:44:06Z
dc.date.issued2012en_US
dc.description.abstractIn 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+e)-similar to S for any e>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.en_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume31
dc.identifier.doi10.1111/j.1467-8659.2012.03165.x
dc.identifier.issn1467-8659en_US
dc.identifier.urihttps://doi.org/10.1111/j.1467-8659.2012.03165.xen_US
dc.publisherThe Eurographics Association and Blackwell Publishing Ltd.en_US
dc.titleMicrotiles: Extracting Building Blocks from Correspondencesen_US
Files