PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2610.37297v1cs.CV

TL;DR

High-resolution contour extraction is hindered by sequential processing and the overhead of building topological hierarchies, while practical parallel alternatives can involve stitching or synchronization. TRUCO uses lock-free tracing with start-point ownership and speculative traversal. It reaches a 19.97× speedup for 1MP images and is reported to scale across resolutions and hardware.

  • Problem

    High-resolution contour extraction is constrained by sequential algorithms and topological-hierarchy overhead, while existing parallel alternatives can be complex or unavailable in practical libraries.

    Source: §1 · p. 1

  • Method

    TRUCO assigns contours by raster-scan start-point ownership and uses speculative tracing with upward termination, relying on idempotent pixel marking rather than mutexes or atomics.

    Source: §1 · pp. 1–2, §4.4 · p. 7

  • Results

    TRUCO reaches a 19.97× speedup for 1MP images and is reported to outperform standard Suzuki-Abe even in single-threaded execution while scaling across hardware configurations.

    Source: §5.1 · p. 8, §6 · p. 11

  • Takeaways & Limitations

    TRUCO offers an architecture-agnostic option for real-time robotics and high-speed inspection applications requiring rapid geometric boundary data.

    Source: §6 · p. 11

    Speculative writes to shared cache lines can cause false sharing and implicit hardware synchronization when a contour spans multiple thread domains.

    Source: §4.4 · p. 7

Abstract

from arXiv · show

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.

1. Introduction

High-resolution contour extraction is constrained by sequential processing and the cost of constructing topological hierarchies, even when applications need only geometric boundaries. TRUCO introduces lock-free parallel tracing based on start-point ownership and speculative traversal.

1. Introduction

  • High-resolution, real-time imaging strains sequential contour extraction, while constructing parent-child relationships adds overhead when only geometric boundaries are needed.The introduction identifies 4K-and-beyond images as a growing demand.Source: §1 · p. 1
  • Existing parallel alternatives are often computationally complex or lack public implementations, and OpenCV has no native parallel contour-extraction implementation.The paper positions TRUCO as a lightweight, deterministic tracer for multi-core CPUs.Source: §1 · pp. 1–2
  • TRUCO assigns each contour to the thread containing its raster-scan entry point, using downward speculative tracing and upward termination to prevent duplicate extraction.Threads may write the same pixel because marking is idempotent, avoiding mutexes and atomic instructions.Source: §1 · pp. 1–2
  • TRUCO uses 8-bit operations rather than Suzuki-Abe’s 32-bit integer labeling, reducing memory-bandwidth pressure and improving SIMD throughput independently of thread count.The source code and materials to reproduce the results are publicly available.Source: §1 · p. 2

2. Related Work

Contour extraction research ranges from local boundary tracing and topological analysis to run-based and parallel methods. The section also discusses deep-learning edge maps, which still require vectorization into geometric contours.

2. Related Work

  • Contour-extraction research has progressed from local boundary followers to global topological analyzers and data-driven models.Source: §2 · p. 2

2.1. Classical Sequential Tracing Paradigms

  • Square Tracing is simple but vulnerable to stopping and 8-connectivity problems, while Moore-Neighbor Tracing is more robust but serial, with O(L) complexity.Pixel-type classification refinements reduce the search space without changing the stated complexity.Source: §2.1 · p. 2

2.2. Topological connectivity

  • Suzuki-Abe [8] builds a contour hierarchy with O(N×M) complexity; linear-time and block-based optimizations reduce scanning or memory access but retain topological overhead.Source: §2.2 · p. 2

2.3. Run-Length Encoding Approaches

  • Run-Length Encoding processes foreground runs and can improve throughput on simple geometries, but linking adjacent rows remains sequential and limits parallel scaling.The paper includes run-based tracing as an experimental baseline.Source: §2.3 · p. 2

2.4. Parallel Contour Extraction

  • Parallel contour methods include PRAM ranking, systolic-array chain coding, tiled Suzuki-Abe variants, and Union-Find extraction; tile stitching and object-density sensitivity remain concerns.Figure 1 depicts Suzuki-Abe scanning and labeling, including an outer contour and inner contours.Source: §2.4 · pp. 2–3, Figure 1 · p. 3

2.5. Deep Learning edge detection

  • HED and SAM [29] produce dense probability maps that require vectorization, while TRUCO targets geometric tracing without synchronization or complex stitching.The section also describes TRUCO’s start-point-invariant geometric hashing for deduplication.Source: §2.5 · p. 3

3. The Suzuki-Abe Algorithm

The Suzuki-Abe algorithm raster-scans a binary image and labels contour pixels while constructing topological information. Its start tests distinguish outer and hole contours, and its tracing routine uses signed labels to track visited pixels.

3. The Suzuki-Abe Algorithm

  • The algorithm assumes a one-pixel background border, scans the image in row-major order, and modifies the integer image in place with contour labels.The label magnitude corresponds to the current contour counter, NBD.Source: §3 · pp. 3–4
  • A foreground pixel preceded by background starts an outer contour, while a labeled pixel followed by background can start a hole contour unless its label is negative.Source: §3 · p. 4
  • Counter-clockwise Moore-Neighbor tracing labels pixels −NBD when the east-neighbor condition is met and NBD otherwise, preventing right-edge pixels from being mistaken for new hole starts.Figure 1 illustrates the outer contour and hole contours detected by the scan.Source: §3 · pp. 3–4

4. Threaded Raster Unrestricted Contour Ownership

TRUCO parallelizes contour extraction by assigning row slices to threads and using a compact shared labeling state. Start-point ownership and speculative tracing coordinate work across slices, with correctness supported by an exactly-once ownership rule and logically benign writes.

4.1. Domain Decomposition and State Space

  • The method uses four labels—BACKGROUND, FOREGROUND, VISITED, and EAST VISITED—and 8-bit data instead of Suzuki-Abe’s 32-bit contour-ID image.Moore tracing treats every non-background state as foreground, so pixels marked visited by one thread remain geometrically valid to another.Source: §4.1 · p. 4

4.2. Speculative Tracing Logic

  • Each contour belongs to the thread whose row slice contains its raster-scan start point; downward tracing is allowed, while upward entry into a preceding slice aborts the trace.A hole contour starting on the slice’s first row may make a one-row upward excursion without aborting, provided it does not extend farther upward.Source: §4.2 · p. 5

4.3. Formal Correctness Proof

  • Every contour is emitted exactly once by the thread owning its raster-scan start point, including hole contours that begin on a slice boundary.The proof relies on a one-row boundary exception for such holes; traces from lower slices that reach the actual start point abort.Source: §4.3 · pp. 6–7

4.4. Synchronization and Memory Model

  • Overlapping writes are logically benign because marking pixels VISITED or EAST VISITED is idempotent, eliminating explicit barriers, locks, and atomic operations.Hardware cache coherence remains active, and false sharing can add latency when a contour spans multiple thread domains.Source: §4.4 · p. 7

5. Experimental Section

TRUCO is evaluated against OpenCV’s Suzuki-Abe and RLE methods and Garcia et al.’s parallel tiling method, using synthetic, real-world, and pathological images. It scales strongly on synthetic and Liu4K data, while vertical-stripe and spiral tests expose reduced parallel gains in worst-case geometries.

5. Experimental Section

  • The synthetic dataset comprised 40 images at 4000×4000 pixels, designed to simulate varying geometric complexity and computational load for benchmarking contour-tracing algorithms.Comparisons included Suzuki-Abe and RLE in OpenCV 4.12, Garcia et al.’s parallel tiling method, and the proposed approach; contour-hierarchy calculations were disabled.Source: §5.1 · p. 7, §5 · p. 7

5.1. Synthetic Dataset

  • On synthetic images, TRUCO peaks at 19.97× speedup for 1 MP and 13.97× for 16 MP, while higher thread counts reduce sensitivity to contour density.TRUCO(1T) is approximately 2× faster than the baseline; at higher parallelism, execution time remains stable across image complexities.Source: §5.1 · p. 8, Table 1 · p. 8

5.2. Liu4K dataset

  • 10.50× speedup over the Suzuki-Abe baseline on 16 MP Liu4K images with 20 threads; the Xeon server reaches 9.95×.The Liu4K results are compared across consumer and server architectures.Source: §5.2 · p. 9, Table 2 · p. 9
  • Liu4K speedup varies with scene complexity: 1.4 million contours correspond to 23.64×, while approximately 2500 contours correspond to 2.09×.TRUCO(1T) averages approximately 1.80× speedup with σ ≈0.15; TRUCO(20T) has σ ∈[2.92, 3.94].Source: Figure 4 · p. 9, §5.2 · p. 10, Table 3 · p. 10

5.3.1. Vertical Stripes

  • On vertical stripes, TRUCO reaches 2.06× speedup with five threads before abort overhead dominates; its single-thread version reaches 1.50×.As more threads are added, each stripe traverses every thread’s domain, increasing the ratio of aborted to valid work; performance remains comparable to the baseline rather than failing catastrophically.Source: §5.3.1 · pp. 10–11, Figure 6 · p. 10

5.3.2. The Spiral

  • On a single continuous spiral, TRUCO peaks at 1.28× speedup with six threads and stays around 1.20× across 20 threads, never falling below the baseline.The single-thread version reaches 1.14×; overlapping speculative traces likely trigger cache-coherency traffic that stalls the owner thread.Source: Figure 6 · p. 10, §5.3.2 · p. 11

6. Conclusions

TRUCO is presented as a lock-free contour-extraction framework that avoids synchronization and boundary merging while scaling across hardware configurations.

6. Conclusions

  • TRUCO is significantly faster than the standard Suzuki-Abe implementation even in single-threaded execution.The method avoids mutexes, atomic operations, and complex boundary-merging logic.Source: §6 · p. 11
  • Start-point ownership and speculative tracing distribute workloads across thread counts and image resolutions without synchronization primitives.The algorithm is described as scaling robustly across varying thread counts and image resolutions.Source: §6 · p. 11
  • TRUCO handles complex contours naturally and degrades gracefully on pathological geometries such as infinite spirals or dense vertical stripes.Source: §6 · p. 11
  • Consistent performance across hybrid and homogeneous core topologies and consumer and server architectures supports TRUCO’s portability.The paper describes an Intel i7 consumer CPU and Intel Xeon server CPU evaluation.Source: §6 · p. 11

Declaration of generative AI and AI-assisted technologies in the manuscript preparation process.

The authors disclose using Gemini 3.0 Pro to assist with algorithm coding and manuscript writing, and state that they reviewed and edited the content and take full responsibility.

Declaration of generative AI and AI-assisted technologies in the manuscript preparation process.

Data Availability Statement

The authors provide TRUCO’s source code and reproduction materials, and identify Liu4K as the source of real-world images.

Data Availability Statement

Loading 2610.37297v1…