One DAG to Rule Them All

Federico Bolelli, Stefano Allegretti, Costantino Grana

Abstract

In this paper, we present novel strategies for optimizing the performance of many binary image processing algorithms. These strategies are collected in an open-source framework, <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">graphgen</small> , that is able to automatically generate optimized C++ source code implementing the desired optimizations. Simply starting from a set of rules, the algorithms introduced with the <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">graphgen</small> framework can generate decision trees with minimum average path-length, possibly considering image pattern frequencies, apply state prediction and code compression by the use of directed rooted acyclic graphs (DRAGs). Moreover, the proposed algorithmic solutions allow to combine different optimization techniques and significantly improve performance. Our proposal is showcased on three classical and widely employed algorithms (namely Connected Components Labeling, Thinning, and Contour Tracing). When compared to existing approaches —in 2D and 3D—, implementations using the generated optimal DRAGs perform significantly better than previous state-of-the-art algorithms, both on CPU and GPU.
BibTeX
@article{bolelli2022one,
  author = {Federico Bolelli and Stefano Allegretti and Costantino Grana},
  title = {{One DAG to Rule Them All}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2022},
  url = {https://openreview.net/forum?id=9muoL8Z7uG},
}

Loading related content...

Figure