Characters string recognition on maps, a method for high level reconstruction

We present a complete method for character string extraction that is specifically adapted to a cartographic context (orientation,…). We emphasize a high level reconstruction process that: (1) resolves the ambiguities remaining from pattern analysis; (2) structures the characters into strings. The knowledge used by this process is the coherence of strings to be constructed (e.g. in orientation, scale, fonts…). We formalize the problem in the most general way and then admit two simplifying hypotheses that transform the problem into a graph optimization problem. The method implemented for solving this problem uses different techniques such as: graph theory, dynamic programming, heuristic, combinatorial exploration…. The results seem sufficiently good for an industrial application