Abstract
Polygonal objects are prevalent in man-made scenes. Early approaches to detecting them relied mainly on geometry while subsequent ones also incorporated appearance-based cues. It has recently been shown that this could be done fast by searching for cycles in graphs of line-fragments, provided that the cycle scoring function can be expressed as additive terms attached to individual fragments. In this paper, we propose an approach that eliminates this restriction. Given a weighted line-fragment graph, we use its cyclomatic number to partition the graph into managebly-sized sub-graphs that preserve nodes and edges with a high weight and are most likely to contain object contours. Object contours are then detected as maximally scoring elementary circuits enumerated in each sub-graph. Our approach can be used with any cycle scoring function and multiple candidates that share line fragments can be found. This is unlike in other approaches that rely on a greedy approach to finding candidates. We demonstrate that our approach significantly outperforms the state-of-the-art for the detection of building rooftops in aerial images and polygonal object categories from ImageNet.
This work was funded in part by the EU MyCopter project.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Arbelaez, P., Maire, M., Fowlkes, C., Malik, J.: Contour Detection and Hierarchical Image Segmentation. PAMI 33(5), 898–916 (2011)
Ballard, D.H.: Generalizing the Hough Transform to Detect Arbitrary Shapes. PR 13(2), 111–122 (1981)
Barnes, N., Loy, G., Shaw, D.: The Regular Polygon Detector. PR 43(3), 592–602 (2010)
Belongie, S., Malik, J., Puzicha, J.: Shape Matching and Object Recognition Using Shape Contexts. PAMI 24(24), 509–522 (2002)
Bignone, F., Henricsson, O., Fua, P., Stricker, M.: Automatic Extraction of Generic House Roofs from High Resolution Aerial Imagery. In: Buxton, B.F., Cipolla, R. (eds.) ECCV 1996. LNCS, vol. 1064, Springer, Heidelberg (1996)
Carreira, J., Sminchisescu, C.: Constrained Parametric Min-Cuts for Automatic Object Segmentation. In: CVPR 2010 (2010)
Chui, H., Rangarajan, A.: A New Point Matching Algorithm for Non-Rigid Registration. CVIU 89(2-3), 114–141 (2003)
Cootes, T., Taylor, C., Cooper, D., Graham, J.: Active Shape Models: Their Training and Application. CVIU 61(1), 38–59 (2005)
Cox, I.J., Rehg, J.M., Hingorani, S.L.: A Bayesian Multiple Hypothesis Approach to Contour Segmentation. IJCV 11, 5–24 (1993)
Crevier, D.: A Probabilistic Method for Extracting Chains of Collinear Segments. Image and Vision Computing (1999)
Dalal, N., Triggs, B.: Histograms of Oriented Gradients for Human Detection. In: CVPR 2005 (2005)
Deng, J., Dong, W., Socher, R., Li, L.J., Li, K., Fei-Fei, L.: Imagenet: A Large-Scale Hierarchical Image Database. In: CVPR 2009 (2009)
Dickson, W.: Feature Grouping in a Hierarchical Probabilistic Network. Image and Vision Computing (1991)
Diestel, R.: Graph Theory. Springer (2005)
Elder, J., Zucker, S.: Computing Contour Closure. In: Buxton, B.F., Cipolla, R. (eds.) ECCV 1996. LNCS, vol. 1064, Springer, Heidelberg (1996)
Elder, J.H., Krupnik, A., Johnston, L.A.: Contour Grouping with Prior Models. PAMI 25(25), 661–674 (2003)
Endres, I., Hoiem, D.: Category Independent Object Proposals. In: Daniilidis, K., Maragos, P., Paragios, N. (eds.) ECCV 2010, Part V. LNCS, vol. 6315, pp. 575–588. Springer, Heidelberg (2010)
Felzenszwalb, P., Mcallester, D., Ramanan, D.: A Discriminatively Trained, Multiscale, Deformable Part Model. In: CVPR 2008 (2008)
Ferrari, V., Jurie, F., Schmid, C.: From Images to Shape Models for Object Detection. IJCV 87, 284–303 (2010)
Guy, G., Medioni, G.: Inferring Global Perceptual Contours from Local Features. IJCV 20(1/2), 113–133 (1996)
Huertas, A., Cole, W., Nevatia, R.: Detecting Runways in Complex Airport Scenes. CVGIP 51(2) (1990)
Izadi, M., Saeedi, P.: Three-Dimensional Polygonal Building Model Estimation from Single Satellite Images. IEEE Trans. Geosci. Remote Sens. (2012)
Johnson, D.B.: Finding All the Elementary Circuits of a Directed Graph. SIAM 4(1) (1975)
Jung, C.R., Schramm, R.: Rectangle Detection Based on a Windowed Hough Transform. In: CGIP 2004 (2004)
Jurie, F., Schmid, C.: Scale-Invariant Shape Features for Recognition of Object Categories. In: CVPR 2004 (2004)
Kumar, M.P., Koller, D.: Efficiently Selecting Regions for Scene Understanding. In: CVPR 2010 (2010)
Lampert, C., Blaschko, M., Hofmann, T.: Beyond Sliding Windows: Object Localization by Efficient Subwindow Search. In: CVPR 2008 (2008)
Loy, G., Zelinsky, A.: Fast Radial Symmetry for Detecting Points of Interest. PAMI 25(8), 959–973 (2003)
Mahamud, S., Williams, L.R., Thornber, K.K., Xu, K.: Segmentation of Multiple Salient Closed Contours from Real Images. PAMI (2003)
Matas, J., Chum, O., Urban, M., Pajdla, T.: Robust Wide-Baseline Stereo from Maximally Stable Extremal Regions. IVC 22(10), 761–767 (2004)
Mayer, H.: Automatic Object Extraction from Aerial Imagery, a Survey Focusing on Buildings. CVIU 74(2), 138–149 (1999)
Opelt, A., Pinz, A., Zisserman, A.: A Boundary-Fragment-Model for Object Detection. In: Leonardis, A., Bischof, H., Pinz, A. (eds.) ECCV 2006. LNCS, vol. 3952, pp. 575–588. Springer, Heidelberg (2006)
Parent, P., Zucker, S.W.: Trace Inference, Curvature Consistency, and Curve Detection. PAMI 11(8) (1989)
Perona, P., Freeman, W.T.: A Factorization Approach to Grouping. In: Burkhardt, H.-J., Neumann, B. (eds.) ECCV 1998. LNCS, vol. 1406, pp. 655–670. Springer, Heidelberg (1998)
Roberts, L.: Machine Perception of Three-Dimensional Solids. Ph.D. thesis (1965)
Robles-Kelly, A., Hancock, E.R.: A Probabilistic Spectral Framework for Grouping and Segmentation. PR 37(7), 1387–1405 (2004)
Russakovsky, O., Ng, A.Y.: A Steiner Tree Approach to Object Detection. In: CVPR 2010 (2010)
Sarkar, S., Boyer, K.L.: Quantitative Measures of Change Based on Feature Organisation: Eigenvalues and Eigenvectors. CVIU 71(1), 110–136 (1998)
Shashua, A., Ullman, S.: Structural Saliency: the Detection of Globally Salient Structures Using a Locally Connected Network. In: ICCV 1988 (1988)
Shotton, J., Blake, A., Cipolla, R.: Contour-Based Learning for Object Detection. In: ICCV 2005 (2005)
Sivic, J., Russell, B., Efros, A., Zisserman, A., Freeman, W.: Discovering Objects and Their Location in Images. In: ICCV 2005 (2005)
Sun, X., Christoudias, M., Lepetit, V., Fua, P.: Real-Time Landing Place Assessment in Man-Made Environments. MVA (2013)
Uijlings, J.R.R., van de Sande, K.E.A., Gevers, T., Smeulders, A.W.M.: Selective Search for Object Recognition. IJCV 104(2), 154–171 (2013)
Vijayanarasimhan, S., Grauman, K.: Efficient Region Search for Object Detection. In: CVPR 2011 (2011)
Wang, S., Kubota, T., Siskind, J.M., Wang, J.: Salient Closed Boundary Extraction with Ratio Contour. PAMI 27(4) (2005)
Yeh, T., Lee, J., Darrell, T.: Fast Concurrent Object Localization and Recognition. In: CVPR 2009 (2009)
Zhang, Z., Cao, Y., Salvi, D., Oliver, K., Waggoner, J., Wang, S.: Free-Shape Subwindow Search for Object Localization. In: CVPR 2010 (2010)
Zhang, Z., Fidler, S., Waggoner, J., Dickinson, S., Siskind, J.M., Wang, S.: Supderedge Grouping for Object Localization by Combining Appearance and Shape Information. In: CVPR 2012 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Sun, X., Christoudias, C.M., Fua, P. (2014). Free-Shape Polygonal Object Localization. In: Fleet, D., Pajdla, T., Schiele, B., Tuytelaars, T. (eds) Computer Vision – ECCV 2014. ECCV 2014. Lecture Notes in Computer Science, vol 8694. Springer, Cham. https://doi.org/10.1007/978-3-319-10599-4_21
Download citation
DOI: https://doi.org/10.1007/978-3-319-10599-4_21
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-10598-7
Online ISBN: 978-3-319-10599-4
eBook Packages: Computer ScienceComputer Science (R0)