Binary Morphology and Related Operations on Run-Length Representations

Thomas Breuel

In: Proceedings VISAPP 2008. International Conference on Computer Vision Theory and Applications (VISAPP-08), 3rd, located at VISIGRAPP - The International Joint Conference on Computer Vision and Computer Graphics Theory and Applications, January 22-25, Funchal, Madeira, Portugal, 2008.


Binary morphology on large images is compute intensive, in particular for large structuring elements. Run-length encoding is a compact and space-saving technique for representing images. This paper describes how to implement binary morphology directly on run-length encoded binary images for rectangular structuring elements. In addition, it describes efficient algorithm for transposing and rotating run-length encoded images. The paper evaluates and compares run length morphologial processing on page images from the UW3 database with an efficient and mature bit blit-based implementation and shows that the run length approach is several times faster than bit blit-based implementations for large images and masks. The experiments also show that complexity decreases for larger mask sizes. The paper also demonstrates running times on a simple morphology-based layout analysis algorithm on the UW3 database and shows that replacing bit blit morphology with run length based morphology speeds up performance approximately two-fold.

Weitere Links

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