A Graph-based approach for Kite recognition

The oldest plans to scale of humanmade mega-structures

Data on how Stone Age communities conceived domestic and utilitarian structures are limited to a few examples of schematic and non-accurate representations of various-sized built spaces. Here, we report the exceptional discovery of the up-to-now oldest realistic plans that have been engraved on stones. These engravings from Jordan and Saudi Arabia depict 'desert kites', humanmade archaeological mega-traps that are dated to at least 9,000 years ago for the oldest. The extreme precision of these engravings is remarkable, representing gigantic neighboring Neolithic stone structures, the whole design of which is impossible to grasp without seeing it from the air or without being their architect (or user, or builder). They reveal a widely underestimated mental mastery of space perception, hitherto never observed at this level of accuracy in such an early context. These representations shed new light on the evolution of human discernment of space, communication, and communal activities in ancient times.

A Graph Based Image Interpretation Method Using A Priori Qualitative Inclusion and Photometric Relationships

This paper presents a method for recovering and identifying image regions from an initial oversegmentation using qualitative knowledge of its content. Compared to recent works favoring spatial information and quantitative techniques, our approach focuses on simple a priori qualitative inclusion and photometric relationships such as "region A is included in region B", "the intensity of region A is lower than the one of region B" or "regions A and B depict similar intensities" (photometric uncertainty). The proposed method is based on a two steps' inexact graph matching approach. The first step searches for the best subgraph isomorphism candidate between expected regions and a subset of regions resulting from the initial oversegmentation. Then, remaining segmented regions are progressively merged with appropriate already matched regions, while preserving the coherence with a priori declared relationships. Strengths and weaknesses of the method are studied on various images (grayscale and color), with various intial oversegmentation algorithms (k-means, meanshift, quickshift). Results show the potential of the method to recover, in a reasonable runtime, expected regions, a priori described in a qualitative manner. For further evaluation and comparison purposes, a Python opensource package implementing the method is provided, together with the specifically built experimental database.

Approach for sequential image interpretation using a priori binary perceptual topological and photometric knowledge and k-means-based segmentation

The proposed approach exploits a priori known qualitative inclusion and photometric relationships between image regions, represented by oriented graphs. Our work assumes a sequential image segmentation procedure where regions are progressively segmented and recognized by associating them with corresponding nodes in graphs related to the prior knowledge. The main contribution concerns the parameterization of the k-means clustering algorithm, to be used during the segmentation procedure, and the graph-matching-based identification of resulting clusters, corresponding to regions declared in graphs. The parameterization of k-means is based on known relationships as well as on regions that have been segmented and recognized at previous steps. Parameters are the region of interest within which k-means clustering is constrained, the number of clusters, and seeding constraints. Photometric relationships built from resulting clusters are matched with a priori known relationships to identify each cluster, this being formulated as an exact graph-matching problem. The potential of this approach is studied in four use cases involving real gray-scale and color images with dedicated sequential analysis procedures. Processing results are compared with those obtained without the proposed parameterization of k-means, as well as with some other clustering approaches. Results show the relevance of our approach, in particular in terms of segmentation accuracy, computation time, and seeding reliability.