Kite Recognition by Means of Graph Matching

Kamel Madi, Hamida Seba, Hamamache Kheddouci, Charles-Edmont Bichot, Olivier Barge, Christine Chataigner, Rémy Crassard, Emmanuelle Reganon, Emmanuelle Vila, Marie‐Laure Chambrade, Brochier, jacquesLecture Notes in Computer Science 2015 · DOI · OpenAlex

TL;DR

This paper introduces a novel graph-based approach for recognizing "kites," ancient archaeological structures found in satellite imagery. By representing kites as graphs and employing a multi-level similarity measure that incorporates geometric features, they achieve robust identification and classification, even for partially preserved structures.

What Problem Does This Paper Address?

Archaeologists have long been interested in "kites," large ancient structures made of stone walls, often visible in high-resolution satellite images. Understanding their distribution, function, and the populations that built them requires an accurate and comprehensive inventory. However, identifying these structures from satellite imagery is challenging due to variations in preservation states, leading to fragmented or incomplete visual representations. Existing methods for object recognition in images often struggle with such incomplete data. This paper aims to bridge this gap by developing a robust method for recognizing kites from satellite images, even when they are partially destroyed or disconnected.

Methods

The authors propose a three-level graph-based approach for kite recognition:

  1. Graph Representation: Kites are converted into attributed graphs. Vertices represent endpoints of wall segments, and edges represent the wall segments themselves. Crucially, vertices are labeled with their 2D position and an n-dimensional attribute capturing the angles between consecutive incident edges, thus encoding the geometric form.
  2. Global Similarity Measure: This initial filter uses graph invariants (like vertex and edge counts, and angle distributions) to quickly discard images that are unlikely to be kites. This is a fast, computationally inexpensive step designed to handle a large number of images efficiently.
  3. Local Similarity Measure (GeoL_Sim): This more detailed comparison uses a graph edit distance-like approach. It extends traditional methods by incorporating vertex degrees, edge labels (distances), and, importantly, the angles between edges. Each vertex is represented by a "signature" vector containing these attributes. The similarity between two graphs is then computed based on the minimum cost of transforming one set of vertex signatures to another, using a bijection (mapping) between vertices. This level is designed to handle the state of preservation of kites.
  4. Reconstruction Step: For images that pass the similarity measures, a reconstruction step uses vertex coordinates to determine if detected kite parts belong to the same kite or different ones, aiming to reconstruct the complete structure.

Datasets

The authors introduce a new benchmark dataset of kite graphs constructed from real satellite images. This dataset consists of approximately 200 graphs in each of three preservation states:

  • State I: Entire and well-preserved kites.
  • State II: Very disconnected kites, with missing parts.
  • State III: Non-kite graphs, used as negative examples.

This dataset is intended to be used for evaluating graph matching and similarity measures.

Key Insights and Ideas

  • Geometric Form is Crucial: The paper highlights that traditional graph matching methods, which often focus solely on graph structure (vertices and edges) and labels, are insufficient for recognizing objects with distinct geometric shapes like kites. Incorporating angles between edges is key to capturing this geometric information.
  • Multi-level Approach for Efficiency: Using a fast global similarity measure first is essential for handling the large volume of satellite imagery in near real-time. This avoids computationally expensive local comparisons on irrelevant images.
  • Handling Disconnection: The proposed method is designed to cope with kites that are partially destroyed or disconnected, a common issue in archaeological contexts. The graph representation and the local similarity measure are adapted to handle these fragmented structures.
  • Benchmark for Future Research: The creation of a dedicated kite graph dataset provides a valuable resource for other researchers to test and compare their own kite recognition or graph matching algorithms.

Key Results

  • The proposed GeoL_Sim approach, which incorporates geometric features (angles), demonstrates higher accuracy in classifying kite graphs compared to a baseline method (L_Sim) that only considers local structures without angles.
  • In classification tasks, GeoL_Sim achieved accuracies of 94% (State I), 80% (State II), and 90% (State III).
  • The global similarity measure (G-Sim) is significantly faster than the local similarity measures, making the overall approach scalable.
  • A combination of G-Sim (for initial filtering) and GeoL_Sim (for detailed analysis) yields good performance across both positive (kites) and negative (non-kites) datasets.

Limitations and Future Work

  • Computational Cost: While the global similarity measure is fast, the local similarity measure, though polynomial, can still be computationally intensive for very large graphs.
  • Future Work: The authors express interest in comparing their approach with other graph similarity measures, particularly those based on kernels. They also plan to explore feature and classifier-based recognition solutions as an alternative or complementary approach.

Summary updated

BibTeX
@inproceedings{madi2015kite,
  author = {Kamel Madi and Hamida Seba and Hamamache Kheddouci and Charles-Edmont Bichot and Olivier Barge and Christine Chataigner and Rémy Crassard and Emmanuelle Reganon and Emmanuelle Vila and Marie‐Laure Chambrade and Brochier, jacques},
  title = {{Kite Recognition by Means of Graph Matching}},
  booktitle = {Lecture Notes in Computer Science},
  year = {2015},
  doi = {10.1007/978-3-319-18224-7\_12},
}

Loading related content...

Figure