Thesis of Kamel Madi

A graph based approach to kite recognition

Defense date: 13/12/2016

Advisor: Hamamache Kheddouci
Coadvisor: Hamida Seba


This thesis focuses on object recognition and namely Kite recognition on satellite images using graph based tools. Kites are remnants of long stone walls that outline the shape of a child’s kite. But the kites are huge: The “body” is a wall enclosing a corral-like space often 100 or more meters across. The “tails,” two or more walls running out from the head, are typically each a few hundred meters long, but they can be as long as two or three kilometers.
A large scale recognition of kites will help archeologists of various fields to understand these enigmatic constructions.
In the problem of pattern recognition, the representation of objects is a fundamental issue There are two main methods of representation: statistical and structural. In the statistical approach, objects are represented by feature vectors which allows benefiting from the mathematical operations available in a vector space i.e., sum, product, mean, distance, etc. However, this representation can not describe the relationships between different parts of the same object or between two different objects.
In the structural representation, objects are represented by graphs that are capable of taking into account the properties of the objects and the relationships between them. The main problem of the graph representation is certainly the complexity of the matching algorithms used in pattern recognition. However, during the last decade, we saw the birth of new perspectives in this field. In particular, the use of tools such as embeddings and graph kernels to simplify matching algorithms.
Kites Recognition, require a hybrid solution that combines the two approaches. In fact:
1. Because of their structures, kites are graphs. Moreover, according to their state of preservation, Kites can be modeled by subgraphs of a reference graph. Matching solution based on graph edit distance can then return results corresponding to kites in various states of preservation.

2. There are several information that must be considered at the level of a kite and at the level of the region containing it. This information must be taken into account in the recognition process.
The thesis will focus on these two complementary aspects of the problem with the following objectives:
1. Modeling kites by graphs while taking into account all the information describing them.
2. Proposing recognition solutions adapted to this representation. The proposed algorithms must be polynomial and adapted to the amount of images that will be processed. The returned results will be classified according to the state of preservation of the kites. This is will be achieved by the graph matching algorithms.
3. Indexing of images based on this modeling to ensure the deployment of the solution at large scales.