Parallel algorithm speeds up contour extraction on multicore CPUs

TRUCO: A Scalable Lock-Free Algorithm for Parallel Contour Extraction

Computer Vision and Pattern Recognition

Summary

Extracting outlines from images is an important step in understanding their content, but common methods work slowly because they process the image one step at a time. The authors created TRUCO, a new way to trace these outlines that lets many processors work together without getting in each other's way. This makes contour extraction much faster on modern computers with multiple cores, especially for very large images. The method ensures each outline is found exactly once by using a special ownership rule and smart thread coordination.

What this means in practice

  • For computer vision engineers: Process high-resolution segmentation results faster by extracting contours efficiently on multi-core CPUs without complex tile stitching.
  • For medical image analysts: Accelerate outline detection in large medical scans to improve throughput in diagnostic workflows using parallel contour tracing methods.

Authors

Rafael Munoz-Salinas, Francisco J. Romero-Ramirez, Manuel J. Marin-Jimenez

Abstract

Transforming binary masks into geometric contours remains a critical step in many computer vision pipelines, particularly for post-processing high-resolution segmentation outputs. Yet, standard algorithms such as the Suzuki-Abe method are limited by their sequential nature and the overhead of building topological hierarchies. As modern applications transition to high-resolution imaging, there is a critical need for contour extraction that leverages multi-core CPU architectures without the complexity of tile stitching or heavy synchronization. This paper presents TRUCO (Threaded Raster Unrestricted Contour Ownership), a lock-free parallel algorithm designed for high-performance geometric boundary extraction. TRUCO introduces a start-point ownership rule, combined with a speculative tracing model, in which threads trace contours downward into adjacent regions and use an upward-termination logic to ensure each contour is processed exactly once. Experimental results on synthetic and real-world datasets, conducted on both consumer and server-grade CPUs, demonstrate that TRUCO significantly outperforms existing baselines. The method achieves speedups of over an order of magnitude compared to the industry standard while maintaining robust scalability on high-resolution scenes across diverse hardware architectures.