Solving problems by taking pictures : study of general graph matching approaches

In a world where new technologies emerge every year, the field of computer vision becomes more and more important. Robots, autonomous cars, video surveillances with face recognition, licence plate recognitions are all examples where computer vision techniques apply to detect and understand real life objects. This understanding aims at extracting useful information and possibly make computations with it. Most of the time it is to ease, accelerate or automate the work of humans in different tasks. Due to the diversity of the application fields, most existing techniques are specific to a given problem. In this thesis, different approaches from specific to general have been considered. The main part of the study focuses on relatively general approaches making use of graph matching techniques. The first step consists in detecting, from the input image, a graph composed of nodes and edges, called the sGraph. Then, given a graph description of the problem to identify (called the mGraph), the aim is to find the largest subgraph of sGraph that matches, according a matching measure, a subgraph of mGraph. Unfortunately, this problem is NP-complete and requires an exponential computation time to solve it completely. It is then important to make decent assumptions and to rely on good heuristics to find a good (but not necessary the best) solution of the problem within a reasonable time. In this work, different graph matching approaches are presented and two of them give satisfactory results on relatively large graphs. The first one is coordinates dependant and rely on the sGraph nodes coordinates and edges attributes to perform the search. The second approach is coordinates independent and only uses the traditional graph structure (nodes and edges) to perform the search and find the best matching. Each of these two techniques has its advantages and disadvantages according the topology of researched problem.