Land cover classification uses multispectral pixel information to separate image regions into categories. Image segmentation seeks to separate image regions into objects and features based on spectral and spatial image properties. However, making sense of complex imagery typically requires identifying image regions that are often a heterogeneous mixture of categories and features that constitute functional semantic units such as industrial, residential, or commercial areas. This requires leveraging both spectral classification and spatial feature extraction synergistically to synthesize such complex but meaningful image units. We present an efficient graphical model for extracting such semantically cohesive regions. We employ an initial hierarchical segmentation of images into features represented as nodes of an attributed graph that represents feature properties as well as their adjacency relations with other features. This provides a framework to group spectrally and structurally diverse features, which are nevertheless semantically cohesive, based on user-driven identifications of features and their contextual relationships in the graph. We propose an efficient method to construct, store, and search an augmented graph that captures nonadjacent vicinity relationships of features. This graph can be used to query for semantic notional units consisting of ontologically diverse features by constraining it to specific query node types and their indicated/desired spatial interaction characteristics. User interaction with, and labeling of, initially segmented and categorized image feature graph can then be used to learn feature (node) and regional (subgraph) ontologies as constraints, and to identify other similar semantic units as connected components of the constraint-pruned augmented graph of a query image.