QAP Optimisation with Reinforcement Learning for Faster Graph Matching in Sequential Semantic Image Analysis

International audienceThe paper addresses the fundamental task of semantic image analysis by exploiting structural information (spatial relationshipsbetween image regions). We propose to combine a deep neural network(CNN) with graph matching where graphs encode efficiently structuralinformation related to regions segmented by the CNN. Our novel approach solves the quadratic assignment problem (QAP) sequentially formatching graphs. The optimal sequence for graph matching is conveniently defined using reinforcement-learning (RL) based on the regionmembership probabilities produced by the CNN and their structural relationships. Our RL-based strategy for solving QAP sequentially allowsus to significantly reduce the combinatorial complexity for graph matching. Preliminary experiments are performed on both a synthetic datasetand a public dataset dedicated to the semantic segmentation of face images. Results show that the proposed RL-based ordering significantlyoutperforms random ordering and that our strategy is about 386 timesfaster than a global QAP-based approach while preserving similar segmentation accuracy