One DAG to Rule Them All.

Area of Science:

• Computer Science
• Image Processing
• Algorithm Optimization

Background:

• Binary image processing algorithms are crucial in various computational fields.
• Existing optimization techniques often lack comprehensive integration and flexibility.
• Performance bottlenecks limit the real-time application of complex image processing tasks.

Purpose of the Study:

• To present novel strategies for optimizing binary image processing algorithms.
• To introduce the GRAPHGEN open-source framework for automated code generation.
• To demonstrate significant performance improvements over existing methods.

Main Methods:

• Development of the GRAPHGEN framework for automated C++ source code generation.
• Implementation of optimization strategies including decision trees with minimum average path-length, state prediction, and code compression using Directed Rooted Acyclic Graphs (DRAGs).
• Integration of multiple optimization techniques within a unified framework.

Main Results:

• GRAPHGEN successfully generates optimized C++ code for binary image processing algorithms.
• Optimized algorithms, particularly using DRAGs, show significant performance gains compared to state-of-the-art approaches.
• Performance improvements were validated on Connected Components Labeling, Thinning, and Contour Tracing algorithms in both 2D and 3D.
• Enhanced performance was observed on both Central Processing Units (CPUs) and Graphics Processing Units (GPUs).

Conclusions:

• The GRAPHGEN framework provides a powerful and flexible approach to optimizing binary image processing algorithms.
• The proposed strategies, especially DRAGs, offer substantial performance benefits for classical image processing tasks.
• Automated code generation using GRAPHGEN leads to state-of-the-art performance in both 2D and 3D image processing on modern hardware.