Detecting Recurring Deformable Objects: An Approximate Graph Matching Method for Detecting Characters in Comics Books

摘要

Graphs are popular data structures used to model pair wise relations between elements from a given collection. In image processing, adjacency graphs are often used to represent the relations between segmented regions. The comparison of such graphs has been largely studied but graph matching strategies are essential to find, efficiently, similar patterns. In this paper, we propose a method to detect the recurring characters in comics books. We would like to draw attention of the reader. In this paper, the term "character" means the protagonists of the story. In our approach, each panel is represented with an attributed adjacency graph. Then, an inexact graph matching strategy is applied to find recurring structures among this set of graphs. The main idea is that the same character will be represented by similar subgraphs in the different panels where it appears. The two-step matching process consists in a node matching step and an edge validation step. Experiments show that our approach is able to detect recurring structures in the graph and consequently the recurrent characters in a comics book. The originality of our approach is that no prior object model is required the characters. The algorithm detects, automatically, all recurring structures corresponding to the main characters of the story.