In this letter, we present a hierarchical connection graph (HCG) algorithm based on a self-avoiding polygon (SAP) model for detecting and extracting gable roofs from aerial imagery. The SAP model is a deformable shape model that is capable of representing gable roofs of various shapes and appearances. The model is composed of a sequence of roof-corner templates that are connected into a SAP, which serves as a flexible shape prior. An energy function that combines features from three channels (corner, boundary, and interior area) is defined over the sequence to quantify the variability in appearances of gable roofs. To infer the most probable state of the corner sequence for an input image, we use an efficient algorithm-called HCG algorithm. The algorithm converts the solution space of a SAP model into a directed graph (which we call “HCG”) and searches for the best path using dynamic programming (DP). It is efficient for two reasons: 1) By constructing an HCG, the algorithm can quickly prune out a large amount of invalid solutions using only geometric constraints, which are inexpensive to compute, and 2) by employing DP, the algorithm decomposes the searching problem into smaller overlapping subproblems and reuses energy scores, which are expensive to compute. Experimental results on a set of challenging gable roofs show that our algorithm has good performance and is computationally effective.

In this paper we present a hierarchical and contextual model for aerial image understanding. Our model organizes objects (cars, roofs, roads, trees, parking lots) in aerial scenes into hierarchical groups whose appearances and configurations are determined by statistical constraints (e.g. relative position, relative scale, etc.). Our hierarchy is a non-recursive grammar for objects in aerial images comprised of layers of nodes that can each decompose into a number of different configurations. This allows us to generate and recognize a vast number of scenes with relatively few rules. We present a minimax entropy framework for learning the statistical constraints between objects and show that this learned context allows us to rule out unlikely scene configurations and hallucinate undetected objects during inference. A similar algorithm was proposed for texture synthesis (Zhu et al. in Int. J. Comput. Vis. 2:107–126, 1998 ) but didn’t incorporate hierarchical information. We use a range of different bottom-up detectors (AdaBoost, TextonBoost, Compositional Boosting (Freund and Schapire in J. Comput. Syst. Sci. 55, 1997 ; Shotton et al. in Proceedings of the European Conference on Computer Vision, pp. 1–15, 2006 ; Wu et al. in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1–8, 2007 )) to propose locations of objects in new aerial images and employ a cluster sampling algorithm (C4 (Porway and Zhu, 2009 )) to choose the subset of detections that best explains the image according to our learned prior model. The C4 algorithm can quickly and efficiently switch between alternate competing sub-solutions, for example whether an image patch is better explained by a parking lot with cars or by a building with vents. We also show that our model can predict the locations of objects our detectors missed. We conclude by presenting parsed aerial images and experimental results showing that our cluster sampling and top-down prediction algorithms use the learned contextual cues from our model to improve detection results over traditional bottom-up detectors alone.

Roof detection has been studied for several decades, one of the big challenge is its structure and appearance diversity. In this paper, we present a grammatical framework to account for these diversities and a multiple way compositional algorithm to extract rooftops from aerial images. We represent rooftops by a context sensitive graph grammar consisting of 5 production rules and 3 types of commonly shared quadrilateral primitives. Each production rule includes a number of equations that constrain the attributes of a parent node and those of its children. In addition, a set of horizontal links are defined between peer nodes at the same level that account for spatial/appearance constraints. The graph grammar produces a large number of valid configurations and can be used to represent the wide structural variability of rooftops. Our rooftop extraction algorithm starts with a lower level bottom-up step that generates hypothesis of quadrilateral primitives by grouping edgelets hierarchically into bigger structures (straight lines, parallel lines and junctions). The grouping process repeats multiple times following alternative paths to reduce missing detections caused by partial occlusion and/or background clutter. Then the higher level relations served as context for lower level elements evaluates each hypothesis according to the graph grammar model and prunes incompatible ones to arrive at an optimal solution.