Optimal Line and Arc Detection on Run-Length Representations

Daniel Keysers, Thomas Breuel

In: GREC 2005 - Sixth IAPR International Workshop on Graphics Recognition. IAPR International Workshop on Graphics Recognition (GREC) Hong Kong Seiten 17-23 Conference Proceedings 8/2005.


The robust detection of lines and arcs in scanned documents or technical drawings is an important problem in document image understanding. We present a new solution to this problem that works directly on run-length encoded data. The method finds globally optimal solutions to parameterized thick line and arc models. Line thickness is part of the model and used during the matching process. Unlike previous approaches, it does not require any thinning or other preprocessing steps, no computation of the line adjacency graphs, and no heuristics. Furthermore, the only search-related parameter that needs to be specified is the desired numerical accuracy of the solution. The method is based on a branch-and-bound approach for the globally optimal detection of these geometric primitives using runs of black pixels in a bi-level image. We present qualitative results of the algorithm on images used in the 2003 GREC arc segmentation contest.

KeysersBreuelOptLineArcDetec.pdf (pdf, 229 KB )

Deutsches Forschungszentrum für Künstliche Intelligenz
German Research Center for Artificial Intelligence