Near-regular structure discovery using linear programming

Near-regular structures are common in manmade and natural objects. Al-gorithmic detection of such regularity greatly facilitates our understanding of shape structures, leads to compact encoding of input geometries, and en-ables efficient generation and manipulation of complex patterns on both ac-quired and synthesized objects. Such regularity manifests itself both in the repetition of certain geometric elements, as well as in the structured arrange-ment of the elements. We cast the regularity detection problem as an opti-mization and efficiently solve it using linear programming techniques. Our optimization has a discrete aspect, i.e., the connectivity relationships among the elements; as well as a continuous aspect, i.e., the locations of the ele-ments of interest. Both these aspects are captured by our near-regular struc-ture extraction framework, which alternates between discrete and continu-ous optimizations. We demonstrate the effectiveness of our framework on a variety of problems including near-regular structure extraction, structure-preserving pattern manipulation, and markerless correspondence detection. Robustness results with respect to geometric and topological noise are pre-sented on synthesized, realworld, and also benchmark datasets