TRUCO: A Scalable Lock-Free Algorithm for Parallel Contour Extraction
Authors: Rafael Munoz-Salinas, Francisco J. Romero-Ramirez, Manuel J. Marin-Jimenez
Organizations: Department of Computing and Numerical Analysis, Córdoba University, Spain · Department of Electronics and Computer Engineering, Córdoba University, Spain
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.
Figures & tables
Figure 1: The Suzuki-Abe scanning and labeling logic. (1) Input image. (2) First contour, which is an outer contour. (3,4) Inner contours. (See text for details)
Figure 2: The proposed scanning and labeling logic using two threads ( T0 and T1 ). (a) A possible scenario where thread T0 runs before T1 . (b) A possible scenario where T1 runs before T0 (See text for details)
Figure 3: Synthetic image dataset results
Figure 4: Examples from the Liu4K dataset showing the original RGB images and their corresponding binary input masks generated via adaptive thresholding. The left images show a complex scene with 1.4 million contours, where our method achieves the maximum speedup (23.64 × ). The right image shows one of the simplest cases, with approximately 2500 contours, where our method achieves its minimum speedup (2.09 × ).
TRUCO(1T)
TRUCO(20T)
Res.
Mean
Std
Min
Max
Mean
Std
Min
Max
16MP
1.79
0.19
1.15
2.74
10.50
3.94
2.09
23.64
8MP
1.79
0.15
1.46
2.97
10.10
3.42
2.14
20.72
4MP
1.80
0.13
1.54
2.77
9.80
3.16
2.20
22.66
2MP
1.80
0.11
1.21
2.49
10.10
3.18
1.66
20.54
1MP
1.79
0.10
1.16
2.48
9.40
2.92
1.59
20.23
Table 3: Statistical analysis of the speedup factor for the proposed method on the Liu4K dataset (i7-13700H). ’1T’ denotes the single-threaded performance, and ’20T’ denotes the peak performance achieved 20 threads.
Figure 5: Scalability analysis on the Liu4K dataset.
Figure 6: Performance analysis under worst-case geometric conditions. (a) Vertical Stripes image. (b) Computing times of TRUCO and Suzuki-Abe in the previous image. TRUCO obtains up to 2.06× speedup before abort overhead dominates. (c) Infinite Spiral image. (d) Computing times of the tested methods in the previous image. TRUCO achieves an almost constant 1.2× speedup.
College of Oceanography and Space Informatics, China University of Petroleum (East China), Qingdao 266580, China · South Surveying&Mapping Instrument Co.,Ltd. · China Railway Design Corporation, Tianjin, China
Division of Robotics and Perception and Learning, KTH Royal Institute of Technology, Stockholm, Sweden · Department of Mechanical Engineering, the University of Hong Kong · School of Computing and Data Science, the University of Hong Kong