Bilkent University
Department of Computer Engineering


Structural Scene Analysis of Remotely Sensed Images Using Graph Mining


Bahadir Ozdemir
MSc. Student
Computer Engineering Department
Bilkent University

The need for intelligent systems capable of automatic content extraction and classification in remote sensing image datasets, has been constantly increasing due to the advances in the satellite technology and the availability of detailed images with a wide coverage of the Earth. Increasing details in very high spatial resolution images obtained from new generation sensors have enabled new applications but also introduced new challenges for object recognition. Contextual information about the image structures has the potential of improving individual object detection. Therefore, identifying the image regions which are intrinsically heterogeneous is an alternative way for high-level understanding of the image content. These regions, also known as compound structures, are comprised of primitive objects of many diverse types. Popular representation such as the bag-of-words model uses primitive object parts extracted using local operators but cannot capture their structure because of the lack of spatial information. Hence, the detection of compound structures necessitates new image representations that involve joint modeling of spectral, spatial and structural information.

We propose an image representation that combines the representational power of graphs with the efficiency of the bag-of-words representation. The proposed method has three parts. In the first part, every image in the dataset is transformed into a graph structure using the local image features and their spatial relationships. The transformation method first detects the local patches of interest using maximally stable extremal regions obtained by gray level thresholding. Next, these patches are quantized to form a codebook of local information and a graph is constructed for each image by representing the patches as the graph nodes and connecting them with edges obtained using Voronoi tessellations. Transforming images to graphs provides an abstraction level and the remaining operations for the classification are made on graphs. The second part of the proposed method is a graph mining algorithm which finds a set of most important subgraphs for the classification of image graphs. The graph mining algorithm we propose first finds the frequent subgraphs for each class, then selects the most discriminative ones by quantifying the correlations between the subgraphs and the classes in terms of the within-class occurrence distributions of the subgraphs; and finally reduces the set size by selecting the most representative ones by considering the redundancy between the subgraphs. After mining the set of subgraphs, each image graph is represented by a histogram vector of this set where each component in the histogram stores the number of occurrences of a particular subgraph in the image. The subgraph histogram representation enables classifying the image graphs using statistical classifiers. The last part of the method involves model learning from labeled data. We use support vector machines (SVM) for classifying images into semantic scene types. In addition, the themes distributed among the images are discovered using the latent Dirichlet allocation (LDA) model trained on the same data. By this way, the images which have heterogeneous content from different scene types can be represented in terms of a theme distribution vector. This representation enables further classification of images by theme analysis.

The experiments using an Ikonos image of Antalya show the effectiveness of the proposed representation in classification of complex scene types. The SVM model achieved a promising classification accuracy on the images cut from the Antalya image for the eight high-level semantic classes. Furthermore, the LDA model discovered interesting themes in the whole satellite image.


DATE: 20 July, 2010, Tuesday @ 14:30