Optimized block-based connected components labeling with decision trees.

Area of Science:

• Computer Vision
• Image Processing
• Algorithms

Background:

• Eight-connection labeling is crucial for image analysis tasks.
• Existing methods often involve extensive memory access and suboptimal neighborhood exploration.
• Efficiency in image labeling is critical for real-time applications.

Purpose of the Study:

• To introduce a novel paradigm for eight-connection labeling.
• To enhance neighborhood exploration and minimize memory accesses.
• To develop a faster and more efficient image labeling algorithm.

Main Methods:

• Extended decision table formalism with OR-decision tables for managing multiple actions.
• Automatic synthesis of optimal decision trees from decision tables to determine efficient condition evaluation order.
• A new 2x2 pixel grid scanning technique optimized by the generated decision tree.

Main Results:

• The proposed algorithm demonstrates a significant speedup compared to state-of-the-art methods.
• Extensive comparisons on synthetic and real-world datasets (artistic images, document analysis, standard resolution images) validate the performance.
• The method effectively improves neighborhood exploration and reduces memory accesses.

Conclusions:

• The new paradigm offers a substantial improvement in the speed and efficiency of eight-connection labeling.
• The integration of OR-decision tables and optimized scanning provides a robust solution for various image analysis tasks.
• This approach sets a new benchmark for performance in image segmentation and labeling.