Cited By
View all- Kelly TFemiani JWonka PMitra N(2017)BigSURACM Transactions on Graphics10.1145/3130800.313082336:6(1-16)Online publication date: 20-Nov-2017
Discovering Structured Variations Via Template Matching
Authors: 
Duygu Ceylan, Minh Dang, 
Niloy J. Mitra, Boris Neubert, and 
Mark PaulyAuthors Info & Claims
Duygu Ceylan, Minh Dang, Niloy J. Mitra, Boris Neubert, and Mark PaulyAuthors Info & ClaimsAbstract
Understanding patterns of variation from raw measurement data remains a central goal of shape analysis. Such an understanding reveals which elements are repeated, or how elements can be derived as structured variations from a common base element. We investigate this problem in the context of 3D acquisitions of buildings. Utilizing a set of template models, we discover geometric similarities across a set of building elements. Each template is equipped with a deformation model that defines variations of a base geometry. Central to our algorithm is a simultaneous template matching and deformation analysis that detects patterns across building elements by extracting similarities in the deformation modes of their matching templates. We demonstrate that such an analysis can successfully detect structured variations even for noisy and incomplete data.
References
[1]
{BCLS13}¿ Bao S. Y., Chandraker M., Lin Y., Savarese S.: Dense object reconstruction with semantic priors. In IEEE CVPR Portland, OR, USA, 2013, IEEE Computer Society, Los Alamitos, CA, USA.
[2]
{CKX*08}¿ Chen X., Kang S. B., Xu Y.-Q., Dorsey J., Shum H.-Y.: Sketching reality: Realistic interpretation of architectural designs. ACM Transactions on Graphics Volume 27 2008, pp.11:1-11:15.
[3]
{CML*12}¿ Ceylan D., Mitra N. J., Li H., Weise T., Pauly M.: Factored facade acquisition using symmetric line arrangements. Computer Graphics Forum Eurographics Volume 31 May 2012, pp.671-680.
[4]
{CMZP14}¿ Ceylan D., Mitra N. J., Zheng Y., Pauly M.: Coupled structure-from-motion and 3d symmetry detection for urban facades. ACM Transactions on Graphics Volume 33, Issue 1 Feb. 2014, pp.2:1-2:15.
[5]
{DFVN14}¿ Dong X., Frossard P., Vandergheynst P., Nefedov N.: Clustering on multi-layer graphs via subspace analysis on Gassmann manifolds. IEEE Transactions on Signal Processing Volume 62 Feb. 2014, 905-918.
[6]
{DOIB10}¿ Delong A., Osokin A., Isack H., Boykov Y.: Fast approximate energy minimization with label costs. In IEEE CVPR San Francisco, CA, USA, June 2010, IEEE Computer Society, Los Alamitos, CA, USA, pp. pp.2173-2180.
[7]
{DSG*12}¿ Doersch C., Singh S., Gupta A., Sivic J., Efros A. A.: What makes paris look like paris ? ACM Transactions on Graphics SIGGRAPH Volume 31, Issue 4 2012, pp.103-110.
[8]
{DTRC01}¿ Dick A. R., Torr P. H. S., Ruffle S. J., Cipolla R.: Combining single view recognition and multiple view stereo for architectural scenes. In IEEE International Conference on Computer Vision Vancouver, British Columbia, Canada, 2001, IEEE, IEEE Computer Society, Los Alamitos, CA, USA.
[9]
{FI13}¿ Faktor A., Irani M.: Co-segmentation by composition. IEEE International Conference on Computer Vision Sydney, Australia, 2013, IEEE, IEEE Computer Society, Los Alamitos, CA, USA, pp. pp.1297-1304.
[10]
{FP09}¿ Furukawa Y., Ponce J., : Accurate, dense, and robust multiview stereopsis. IEEE Transactions on Pattern Analysis and Machine Intelligence 32 2009, pp.1362-1376.
[11]
{GSMCO09}¿ Gal R., Sorkine O., Mitra N. J., Cohen-Or D.: iWIRES: An analyze-and-edit approach to shape manipulation. ACM Transactions on Graphics SIGGRAPH Volume 28 2009, pp.33:1-33:10.
[12]
{JTC11}¿ Jiang N., Tan P., Cheong L.-F.: Multi-view repetitive structure detection. In IEEE International Conference on Computer Vision Barcelona, Spain, 2011, IEEE, IEEE Computer Society, Los Alamitos, CA, USA, pp. pp.535-542.
[13]
{KMYG12}¿ Kim Y. M., Mitra N. J., Yan D.-M., Guibas L.: Acquiring 3d indoor environments with variability and repetition. ACM Transactions on Graphics SIGGRAPH Asia Volume 31 Nov. 2012, pp.138:1-138:11.
[14]
{KWW*14}¿ Kurz C., Wu X., Wand M., Thormÿhlen T., Kohli P., Seidel H.-P.: Symmetry-aware template deformation and fitting. Computer Graphics Forum Volume 33 2014, pp.205-219.
[15]
{LCDF10}¿ Lipman Y., Chen X., Daubechies I., Funkhouser T.: Symmetry factored embedding and distance. ACM Transactions on Graphics SIGGRAPH Volume 29, Issue 4 July 2010, pp.103:1-103:12.
[16]
{LKBH13}¿ Lafarge F., Keriven R., Brédif M., Hiep V.: A hybrid multi-view stereo algorithm for modeling urban scenes. IEEE Transactions on Pattern Analysis and Machine Intelligence Volume 35, Issue 1 Jan. 2013, pp.5-17.
[17]
{LM06}¿ Learned-Miller E.: Data driven image models through continuous joint alignment. IEEE Transactions on Pattern Analysis and Machine Intelligence 28 Feb. 2006, pp.236-250.
[18]
{LMLR07}¿ Liu S., Martin R. R., Langbein F. C., Rosin P. L.: Segmenting periodic reliefs on triangle meshes. In Proceedings of the IMA International Conference on Mathematics of Surfaces 2007 R.Martin, M.Sabin, J.Winkler Eds., Springer-Verlag, Sheffield, UK, pp. pp.290-306.
[19]
{LT13}¿ Leifman G., Tal A.: Pattern-driven colorization of 3d surfaces. In IEEE CVPR Portland, OR, USA, June 2013, IEEE, IEEE Computer Society, Los Alamitos, CA, USA, pp. pp.241-248.
[20]
{LWC*11}¿ Li Y., Wu X., Chrysanthou Y., Sharf A., Cohen-Or D., Mitra N. J.: Globfit: Consistently fitting primitives by discovering global relations. ACM Transactions on Graphics SIGGRAPH Volume 30, Issue 4 2011, pp.52:1-52:12.
[21]
{LZS*11}¿ Li Y., Zheng Q., Sharf A., Cohen-Or D., Chen B., Mitra N. J.: 2d-3d fusion for layer decomposition of urban facades. In IEEE ICCV Barcelona, Spain, November 2011, IEEE, IEEE Computer Society, Los Alamitos, CA, USA.
[22]
{MGP06}¿ Mitra N. J., Guibas L. J., Pauly M.: Partial and approximate symmetry detection for 3d geometry. ACM Transactions on Graphics SIGGRAPH Volume 25 2006, pp.560-568.
[23]
{MPWC13}¿ Mitra N. J., Pauly M., Wand M., Ceylan D.: Symmetry in 3d geometry: Extraction and applications. Computer Graphics Forum Volume 32, Issue 6 2013, pp.1-23.
[24]
{MWA*13}¿ Musialski P., Wonka P., Aliaga D. G., Wimmer M., <familyNamePrefix>van</familyNamePrefix>Gool L., Purgathofer, W.: A survey of urban reconstruction. Computer Graphics Forum Volume 32, Issue 6 2013, pp.146-177.
[25]
{NXS12}¿ Nan L., Xie K., Sharf A.: A search-classify approach for cluttered indoor scene understanding. ACM Transactions on Graphics Volume 31 Nov. 2012, pp.137:1-137:10.
[26]
{PMG*05}¿ Pauly M., Mitra N. J., Giesen J., Gross M., Guibas L. J.: Example-based 3D scan completion. Computer Graphics Forum SGP 2005, pp.23-32.
[27]
{PMW*08}¿ Pauly M., Mitra N. J., Wallner J., Pottmann H., Guibas L., : Discovering structural regularity in 3D geometry. ACM Transactions on Graphics SIGGRAPH 43 2008, pp.1-11.
[28]
{Qua10}¿ Quan L.: Image-Based Modeling, 1st ed. Springer, New York, USA, 2010.
[29]
{Sch03}¿ Schindler K.: A model-based method for building reconstruction. In Proceedings of the International Conference on Computer Vision Working on Higher-Level Knowledge in 3D Modeling & Motion Nice, France, 2003, IEEE, IEEE Computer Society, Los Alamitos, CA, USA, pp. pp.74-82.
[30]
{SI07}¿ Shechtman E., Irani M.: Matching local self-similarities across images and videos. In IEEE CVPR Mineapolis, USA, June 2007, IEEE, IEEE Computer Society, Los Alamitos, CA, USA, pp. pp.1-8.
[31]
{ska}¿ Skanect 3d scanning software. "http://skanect.occipital.com/". Accessed: 2015-01-10.
[32]
{VAW*10}¿ Vanegas C. A., Aliaga D. G., Wonka P., Müller P., Waddell P., Watson B.: Modelling the appearance and behaviour of urban spaces. Computer Graphics Forum Volume 29, Issue 1 2010, pp.25-42.
[33]
{VEB09}¿ Vinh N. X., Epps J., Bailey J.: Information theoretic measures for clusterings comparison: Is a correction for chance necessary ? In ICML Montreal, Quebec, Canada, 2009, ACM, New York, USA, pp. pp.1073-1080.
[34]
{WFP11} Wu C., Frahm J.-M., Pollefeys M.: Repetition-based dense single-view reconstruction. In IEEE CVPR Providence, RI, USA, 2011, IEEE, IEEE Computer Society, Los Alamitos, CA, USA.
[35]
{WKM15}¿ Wang T. Y., Kohli P., Mitra N. J.: Dynamic SFM: Detecting scene changes from image pairs, Computer Graphics ForumVolume 34 2015, pp.177-189.
[36]
{Wu13}¿ Wu C.: Towards linear-time incremental structure from motion. In 3DV-Conference Seattle, WA, USA, 2013, IEEE, IEEE Computer Society, Los Alamitos, CA, USA, pp. pp.127-134.
[37]
{ZSW*10}¿ Zheng Q., Sharf A., Wan G., Li Y., Mitra N. J., Cohen-Or D., Chen B.: Non-local scan consolidation for 3D urban scenes. ACM Transactions on Graphics SIGGRAPH Volume 29 2010, pp.94:1-94:9.
Recommendations
Fixed time template matching
SMC'09: Proceedings of the 2009 IEEE international conference on Systems, Man and CyberneticsThe problem of finding a match for an image ('template') within a larger image is known as template matching. It is key to a variety of Computer Vision applications. Currently known template matching algorithms run in fixed time, or are guaranteed to ...
A Dual-Bound Algorithm for Very Fast and Exact Template Matching
Recently proposed fast template matching techniques employ rejection schemes derived from lower bounds on the match measure. This paper generalizes that idea and shows that in addition to lower bounds, upper bounds on the match measure can be used to ...
Fast Template Matching With Polynomials
Template matching is widely used for many applications in image and signal processing. This paper proposes a novel template matching algorithm, called algebraic template matching. Given a template and an input image, algebraic template matching ...
Comments
Information & Contributors
Information
Published In
Publisher
The Eurographs Association & John Wiley & Sons, Ltd.
Chichester, United Kingdom
Publication History
Published: 01 January 2017
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Other Metrics
Citations
Cited By
View all- Kelly TFemiani JWonka PMitra N(2017)BigSURACM Transactions on Graphics10.1145/3130800.313082336:6(1-16)Online publication date: 20-Nov-2017
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in