JF-cut: a parallel graph cut approach for large-scale image and video.

Area of Science:

• Computer Vision
• Computer Graphics
• Algorithm Design

Background:

• Graph cut is a powerful technique for image segmentation.
• Conventional graph-cut methods struggle with large datasets due to high computational complexity.
• Existing parallel solutions on CPUs and GPUs have limitations in parallelism and convergence speed.

Purpose of the Study:

• To develop a novel, efficient graph-cut algorithm for large-scale image and video segmentation.
• To enhance the performance and convergence of graph-cut on parallel processing units, specifically GPUs.
• To provide a user-friendly interface for handling occlusions in video segmentation.

Main Methods:

• A novel graph-cut algorithm utilizing a parallelized jump flooding technique.
• Implementation of an heuristic push-relabel scheme including back-and-forth relabel, convergence detection, and block-wise push-relabel.
• Full parallelization of the algorithm on Graphics Processing Units (GPUs).

Main Results:

• The proposed GPU-parallelizable algorithm outperforms existing GPU-based implementations in global convergence, information propagation, and performance.
• Achieved high-quality segmentation results on diverse datasets including large images, high-resolution videos, and volumetric data.
• Demonstrated significant speedups: up to 40-fold over conventional GPU-based approaches and 139-fold over CPU-based approaches.

Conclusions:

• The novel graph-cut algorithm offers a substantial improvement in efficiency and performance for large-scale segmentation tasks.
• The parallelized approach effectively addresses the computational limitations of traditional graph-cut methods.
• The algorithm provides a robust and fast solution for complex segmentation problems in computer vision and graphics.