PaperlayerView exact revision on arXiv

Source-linked AI summary

SweepLSD: A One-Pass, O(width)-Memory Line Segment Detector with an Integer-Only Streaming Core and a Real-Time FPGA Realization

Yoshiyasu Shimizu

arXiv:2608.22086v1eess.IVcs.ARcs.CV

TL;DR

Line segment detectors commonly require frame-sized memory and repeated pixel access, limiting their fit for streaming hardware and cache-sensitive pipelines. SweepLSD instead performs one-pass raster processing with O(width) state and an integer-only core, and demonstrates both fast CPU operation and frame-buffer-free FPGA detection. Its main trade-off is lower coverage or synthetic F-score on some difficult imagery, especially soft low-contrast structure and arbitrary-angle rotations.

  • Problem

    Existing dominant line detectors hold full images and full-resolution intermediates in memory and revisit pixels, creating a mismatch with hardware and latency-critical pipelines.

  • Method

    SweepLSD expresses smoothing, gradient processing, labeling, and line testing as a one-pass row stream with O(width) state, contact-driven labeling, and an integer-only per-pixel core.

  • Results

    SweepLSD runs live at 1080p30 without a frame buffer or external memory, while one CPU thread processes Full-HD frames in 11.3 ms, 4.6×, 5.2×, and 25× faster than ELSED, EDLines, and LSD.

  • Takeaways & Limitations

    The detector provides a low-memory streaming alternative for CPU and FPGA line-segment pipelines while retaining competitive downstream camera-attitude and vanishing-point performance.

  • Takeaways & Limitations

    ELSED leads synthetic-ground-truth F-score, while SweepLSD misses soft low-contrast structure and performs worst under arbitrary-angle rotation repeatability.

Abstract

from arXiv · show

We present SweepLSD, a line segment detector that reads the image exactly once and emits each segment within a few rows of its last pixel passing the scan line. Every stage, including connected-component labeling and the final line test, processes the image as a row stream: intermediate memory is O(width) rather than O(pixels), and the per-pixel core is integer-only. We give the first complete description of the algorithm, designed in the author's 2014 master's thesis but never published, together with an open-source C++17 implementation and an FPGA realization -- held bit-exact against the software in its hardware configuration -- detecting segments in live 1080p30 video on 2009-era silicon without frame buffer or external memory. On structure-rich public 4K photographs downscaled to Full-HD, one CPU thread detects segments in ~11 ms -- 4.6x/5.2x/25x faster than the original authors' implementations of ELSED, EDLines, and LSD -- with the tightest frame-time distribution and the best per-segment direction accuracy of the four detectors, and curve rejection by design, while trailing ELSED in F-score on synthetic ground truth. A Manhattan-frame vanishing-point study on York Urban and NYU-VP scores every detector under a selection/evaluation-separated best-estimator-per-detector protocol, under which SweepLSD leads on NYU-VP by ~0.3 degrees and trails by 0.1 degrees on York Urban, with the fastest end-to-end pipeline of the four detectors on both. A single-frame camera-attitude application, evaluated on synthetic scenes with exact ground truth and on EuRoC and TUM-VI, matches the baselines' accuracy at a fraction of their memory, and drives a 4K horizon lock to 0.06 degrees median attitude error at 32 ms median per frame.

1 Introduction

SweepLSD is introduced as a one-pass, row-streaming detector designed to reduce memory and repeated pixel access while supporting software and FPGA deployment. The paper publicly describes the previously unpublished method and evaluates its speed, hardware realization, and known accuracy trade-offs.

  • Design: SweepLSD processes every detector stage as a row stream, using O(width) intermediate memory and finalizing segments shortly after their last pixel.The labeling stage trails the sweep by 7 rows.
  • Contribution: The method was designed in a 2014 master’s thesis but had not previously received a complete public description or released implementation.The paper presents the method under the new name SweepLSD.
  • Evaluation: The paper evaluates SweepLSD against LSD, EDLines, and ELSED across timing, memory, accuracy, repeatability, camera attitude, and vanishing-point estimation.The vanishing-point protocol separates estimator selection from evaluation.
  • Limitations: ELSED leads SweepLSD in synthetic-ground-truth F-score, while SweepLSD’s contrast-gated edge model misses soft, low-contrast structure recovered by LSD and EDLines.These limitations define an accuracy and coverage trade-off despite the streaming design.
  • Hardware: A live FPGA realization runs at 1080p30 on a 2009-era Spartan-6 without a frame buffer or external memory, with lossless output on all but two densest corpus frames.The hardware is held bit-exact against the software in its hardware configuration.

2 Related work

Prior line detectors generally operate on frame-sized data or revisit pixels across stages, whereas SweepLSD uses bounded-row raster streaming for both software and hardware-oriented processing.

  • Classical detectors: Classical detectors such as LSD grow orientation-consistent regions and validate candidates with an a-contrario test, while EDLines and ELSED use edge drawing, linking, and fitting.These approaches are accurate and reasonably fast but retain full-resolution intermediates and revisit pixels.
  • Learned detectors: Learned detectors improve robustness on difficult imagery but typically run inference over frame-sized feature maps on GPUs or NPUs.The related-work review includes wireframe parsers, transformers, and compact learned detectors.
  • Streaming connected components: Single-pass connected-components analysis is established in FPGA literature, but SweepLSD closes runs through endpoint contacts and judges them in-stream.Its accepted runs are emitted as line segments while scanning continues.
  • Hardware line detection: Hough-based FPGA line extraction maps voting onto on-chip RAM but produces infinite lines and requires accumulated frame votes before output.This differs from SweepLSD’s segment-oriented streaming design.
  • Positioning: SweepLSD shares the frame-buffer-free stance of prior streaming FPGA segment detectors but uses edge runs, union–find labeling, and contact-driven closure instead of stream-adapted region growing.On a Spartan-6 it sustains approximately 1080p30 or 720p60.
  • Evaluation methodology: The evaluation replaces reliance on incomplete, coarse hand-labeled annotations with strict synthetic matching and calibrated Manhattan-frame accuracy against rotation ground truth.The latter is evaluated on York Urban and NYU.

3 The SweepLSD algorithm

SweepLSD is a five-stage row-streaming detector whose implementation never revisits earlier rows, using O(width) state and integer-oriented processing to emit segments promptly. Its pipeline combines edge extraction, endpoint-candidate detection, streaming labeling, and in-stream line judgment.

  • Streaming design: O(width) intermediate memory follows from expressing every stage as a row stream with fixed vertical support and no earlier-row revisits.The detector uses only small rings of rows and a compact label table; the hardware realization reports approximately 70 KiB of detector state.
  • Pipeline: SweepLSD comprises five stages: integer Gaussian smoothing, gradient and direction-aware NMS, endpoint-candidate detection, streaming labeling, and in-stream line judgment.The pipeline produces thinned edges, identifies where runs must be cut, accumulates component statistics, and judges closed runs.
  • Edge extraction: The gradient uses a 2×2 integer operator, an L1 power approximation, and two-way direction quantization without square roots.Horizontal versus vertical direction is selected by comparing |dx| and |dy|, with exact ties classified as vertical.
  • Endpoint candidates: Endpoint candidates are identified by reducing supported outer-ring exits: straight crossings with n = 2 and d ≥7 are excluded, while ends, branches, and sharp turns are marked.Support pruning removes unrelated clipped structure, and thinning collapses doubled or connected exits before classification.
  • Streaming labeling: Streaming labels store constant-size moments, recency, connectivity, strong-pixel counts, extrema, and contact state rather than component pixels.Merging requires integer additions, and a finished run can be judged in O(1) time regardless of its length.
  • Emission: Closure-driven emission judges a run at its terminating contact and emits segments within the pipeline lag of the run’s last pixel.Measured latency is 6.5 rows median, 7.8 rows at the 99th percentile, and 11.4 rows worst case; at 1080p30, this is approximately 0.19 ms of algorithmic latency.

4 Evaluation: speed and detection quality

SweepLSD combines fast, predictable detection and low-memory scaling with strong direction accuracy and curve rejection, but its performance depends on image content and trails ELSED on synthetic F-score.

  • Speed: 11.3 ms is SweepLSD’s median Full-HD detection time, 4.6× faster than ELSED, 5.2× than EDLines, and 25× than LSD.The comparison uses one CPU thread and original authors’ implementations.
  • Speed: SweepLSD has the tightest frame-time dispersion, because front-end stages process every pixel once while labeler and finalization vary with content.The tail advantage separates above the 95th percentile, although interquartile bands largely overlap.
  • Memory and latency: SweepLSD’s peak working set grows 3.8× while pixels grow 36×, reflecting O(width) intermediate state rather than O(pixels).At 4K, its 22 MiB process peak includes an approximately 7.9 MiB input image.
  • Memory and latency: 6.5 rows is SweepLSD’s median emission latency after a segment’s endpoint row, corresponding to approximately 0.19 ms at 1080p30.The worst measured latency is 11.4 rows.
  • Detection quality: ELSED leads F-max at every synthetic noise level, while SweepLSD is second on clean and σ ≤5 images.A gap-tolerant linker raises SweepLSD’s F-max from 0.905 to 0.924 at σ = 20, but from 0.958 to 0.960 on clean scenes.
  • Detection quality: SweepLSD has the best matched-segment direction accuracy at every noise level, beating ELSED by 2.2–4.4× and ED Lib by 3.5–8.7×.Lateral error among SweepLSD, ELSED, and ED Lib differs by no more than 0.013 px without stable ordering.
  • Detection quality: SweepLSD’s direction advantage survives common-segment control, while ELSED leads the fixed pool-best F-max protocol and SweepLSD ranks third.On the identical 6,657-segment intersection, SweepLSD remains more accurate than LSD and ED Lib, and has a lower median direction error than ELSED.

5 Applications: do the architectural advantages reach the task?

SweepLSD’s streaming architecture reaches downstream attitude and vanishing-point tasks with accuracy comparable to the baselines while reducing memory and detection time. Its main practical boundaries are scene geometry, support quantity, and occasional frame-time or contrast limitations.

  • 5.1 Attitude from a single frame, from 540p to 4K: 0.06–0.09° median gravity error at 4K leaves all four detectors within 0.03° of one another.SweepLSD measures 0.09°, versus 0.07° for ELSED and EDLines and 0.06° for LSD outdoors.
  • 5.1 Attitude from a single frame, from 540p to 4K: ≈30 ms detection and ≈22 MiB peak resident memory at 4K outperform the three baselines while preserving comparable attitude accuracy.SweepLSD detects 2.7× faster than ELSED and uses 6.8× less memory than ELSED and EDLines.
  • 5.2 Generalization to real data: EuRoC and TUM-VI: Scene geometry can cap single-frame accuracy near 1° in mocap rooms because visual gravity recovers the scene’s pseudo-vertical rather than an ideally vertical world axis.The reported floor is intrinsic to monocular single-frame gravity, not to line localization.
  • 5.2 Generalization to real data: EuRoC and TUM-VI: 0.96° median attitude error on native 1024² TUM-VI frames leads the baselines under the detector-agnostic protocol, while detection is 2.5× faster than ELSED.At 139° field of view, however, the four detectors converge to 0.89–0.95°.
  • 5.3 Downstream vanishing-point evaluation: SweepLSD’s best per-line direction residual is 0.51° on York Urban, but its weaker-axis result reflects approximately 20% less supporting line length.Subsampling LSD to SweepLSD’s segment count reproduces nearly the same York Urban score, indicating a quantity rather than quality gap.
  • 5.3.2 Best estimator per detector, cross-validated: The cross-validated detector–estimator pair leads on indoor NYU-VP, while York Urban is a metric-dependent near-tie with SweepLSD 0.1° behind on median.Random half-split tests preserve these ordering conclusions, though York Urban baseline medians show build sensitivity.

6 Hardware realization

The hardware realization expresses SweepLSD as bit-exact streaming HLS and portable RTL designs, with one-pixel-per-clock front-end scheduling and live operation without frame memory. The RTL implementation reduces arithmetic resources enough to support real-time video on 2009-era FPGA hardware.

  • Verification: Bit-exactness is enforced across software, HLS, and RTL at emitted integer run records, covering 204,759 corpus segments.The shared host-side floating-point finalization makes record-level equality segment-level equality.
  • HLS realization: II=1 at 100 MHz schedules every HLS front-end stage for one pixel per clock, while the labeling back end remains event-driven behind an event FIFO.The HLS sources also compile as ordinary C++ and are parity-tested against the software reference.
  • RTL realization: 1080p30 and 720p60 run live on a Spartan-6 without a frame buffer or external memory, using ≈70 KiB of detector block RAM.Segments emerge a median 6.5 rows after their last pixel, approximately 0.19 ms at 1080p30.
  • Resource usage: ≈7 DSP blocks in RTL versus 79 in the HLS detector results from folding judge products onto one shared sequential multiplier.The complete RTL system uses ≈140 KiB of the device’s 261 KiB including video I/O and overlay.
  • Hardware configuration: 8.1 ms versus 11.3 ms at Full-HD makes the hardware configuration faster in software because sub-pixel NMS is omitted.The omission raises mean direction error to 0.05–0.08° from 0.02–0.04° while remaining comparable to the best baseline.
  • Overload limit: 0.48% of corpus segments are lost under the measured 1080p30 overload simulation, concentrated in two densest frames.The event FIFO sheds events when dense edge activity outruns the event-driven back end.

7 Limitations

SweepLSD trades coverage and rotation robustness for contrast-gated, direction-focused streaming detection. Its default false-positive control and speed also depend on optional validation and compiler behavior.

  • Coverage: ~20% support deficit occurs on soft, wide, low-contrast luminance ramps that do not form gradient peaks.Lowering the threshold does not recover these misses because they are architectural.
  • Synthetic accuracy: ELSED leads SweepLSD at every noise level on the synthetic F-max protocol, while ED Lib is more noise-stable at σ ≥10.SweepLSD’s synthetic advantage is per-segment direction rather than raw F-max.
  • Orientation and false detections: SweepLSD is weakest on the dense Siemens-star orientation-isotropy probe because two-way direction quantization limits isotropy.The default configuration has no a-contrario false-detection control, although optional streaming NFA validation is available.
  • Orientation and false detections: Near-zero false positives occur on pure noise at defaults, versus 3.2 per image on smooth texture plus noise; optional NFA reduces this to 0.8.These measurements bound the practical consequence of the absent default NFA control.
  • Repeatability and endpoints: Arbitrary-angle rotation yields 39–48% median repeatability for SweepLSD versus LSD’s 62–64%, while viewpoint and illumination repeatability remains unevaluated.The same two-way quantization that stabilizes axis-preserving rotations disturbs arbitrary rotations.

8 Conclusion

SweepLSD is presented as a publicly described, true raster-stream line detector with a few rows of state and an integer-only core. Its implementation and hardware realization support strong speed, direction, and deployment results, with a measured coverage trade-off.

  • Conclusion: 4.6×/5.2×/25× faster than ELSED/EDLines/LSD on Full-HD CPU detection, SweepLSD also has the tightest frame-time distribution and best per-segment direction accuracy.Curve rejection is by design, while the quantified trade-off is reduced coverage on soft, low-contrast structure.
  • Conclusion: Bit-exact hardware configuration enables live 1080p30 detection on a 2009-era FPGA without a frame buffer or external memory.The hardware realization turns the earlier design claim into an implemented result.

Declarations

The paper reports no funding or competing interests, describes AI-assisted development with author verification, and makes implementation and evaluation resources openly available.

  • Declarations: The author received no financial support for the research, authorship, or publication of the article.
  • Declarations: The author declares no competing interests and reports AI assistance in implementation, evaluation-suite development, and manuscript drafting, with claims verified against measurements.
  • Data and code availability: Implementation, HLS and RTL sources, baseline glue, and evaluation harnesses are openly available under the MIT license, using named public datasets under their own terms.

A The outer-ring thinning reduction

The outer-ring thinning reduction prunes unsupported exits and thins connected arcs to representative candidates, then computes two-survivor arc distance branch-free with an 8-bit XOR-popcount operation shared across software and hardware.

  • Ring representation: The reduction indexes 16 outer-ring positions and 8 inner-ring positions, with each inner position facing outer position 2k.Outer positions are classified as midpoints, corners, or flanks.
  • Rule evaluation: Rules are applied in all four rotations before advancing, so each update reads values left by the preceding rule.
  • Support pruning and thinning: Flank support retains an outer flank only when an inner or adjacent supported midpoint connects it toward the center.The rule is O1 ← O1 ∧ (A0 ∨ A1 ∨ O0), with the corresponding rotated rule for O15.
  • Support pruning and thinning: Support pruning removes exits from structures that merely clip the window, while thinning leaves one representative per connected arc.Within a connected arc, midpoints yield to flanks and surviving corners absorb their flanks.
  • Arc-distance computation: For two survivors, popcount(Tp ⊕ Tq) gives their shorter 16-cycle arc distance without a lookup table.The branch-free 8-bit reduction is identical in the C++ row kernel, HLS model, and RTL.

B Per-stage timing and a two-term cost model

Per-stage measurements identify labeling and judgment as the largest software-time component, while a two-term model separates fixed pixel work from edge-content work across resolutions.

  • Per-stage timing: ≈45% of the 13.3 ms multi-pass stage sum belongs to labeling and judgment, whose share falls toward 30% on sparser imagery.The stage accumulates moment fits per edge run and judges each closed run, so its cost scales with segment density.
  • Per-stage timing: 1.4–2.3 ms is the near-constant cost of each of the four front-end row kernels, which touch every pixel regardless of scene content.Gaussian, gradient, thresholding, and endpoint kernels are integer sweeps and none exceeds a fifth of the stage sum.
  • Two-term cost model: 615 measurements across five resolution rungs fit one-pass time against pixel count and edge-pixel count.The corpus spans 640 × 360 to 3840 × 2160, with 123 photographs per rung and nine runs per image.
  • Two-term cost model: The two-term model assigns pixel-proportional work to four front-end kernels and content-proportional work to labeling and judgment.The content term is based on externally observable edge pixels; label-lifetime events fit marginally better at R2 = 0.967.
  • Two-term cost model: ≈1.5× the Full-HD median is the predicted spread, showing that content variation—not timing noise—drives the measured 24.4% and 1.66× variation.The model attributes frame-time dispersion to the content term.

C Compiler sensitivity of the raster sweep

Compiler choice strongly affects the raster-sweep detector because endpoint-candidate vectorization is toolchain-sensitive, although all tested toolchains preserve identical detections.

  • Compiler sensitivity: Only MSVC’s cl fails to vectorize the endpoint-candidate kernel among five toolchains built from identical sources at the same ISA target.The binaries were run interleaved image-by-image in one measurement window.
  • Compiler sensitivity: A single force-inline annotation recovers full speed with bit-identical output when an inliner leaves the ring test as a per-pixel call.The evidence points to the vectorizer rather than the algorithmic formulation.
  • Compiler sensitivity: The compiler sensitivity is specific to the raster-sweep design, while the baselines are comparatively insensitive because their anchor-chaining loops are branch-bound.This contrast concerns measured runtime behavior, not detection quality.
  • Detection consistency: 410,346 segment records are bit-identical across all five toolchains, verified in exact hexadecimal form.The records comprise 205,173 segments from each of the two drivers over 123 photographs.

D The refinements, ablated

Ablation shows that the refinements contribute unevenly: curve rejection and sub-pixel NMS matter most for downstream behavior, while endpoint projection mainly serves as a robustness guard.

  • Measured effects: Curve rejection is the only standard-bar F-max mover, adding 0.007 clean and improving downstream error by 0.10° at zero cost.It also supplies the mechanism yielding 0 segments on circles.
  • Measured effects: Sub-pixel NMS leaves F-max unchanged but reduces direction error from 0.05–0.08° to 0.02–0.04°.It is the costliest refinement at +3.2 ms, and the hardware configuration omits it.
  • Robustness guard: 0.2 ms is the cost of projection-extreme endpoints, whose endpoint extent error matches the simpler rule on all but one junction-probe case.The refinement is retained for components whose contact pair does not bracket the extent, including merge-path emissions and jagged junction runs.
  • Composition: 1.25 →1.02° is the joint downstream improvement from composing the refinements after curve rejection removes misleading arc fragments.The comparison shows sub-pixel precision becomes load-bearing once curve fragments no longer dominate the estimator.

E The gap-tolerant collinear linker

The optional linker reassembles accepted collinear fragments without touching pixels or rows, using deterministic geometric tests and span-based admission.

  • Design: The optional linker operates at finalization, consuming only judge-accepted segments in emission order and preserving the streaming property.It never accesses pixels or rows.
  • Link test: A new segment links to an active chain only when directions differ by at most 4°, lateral consistency is within 1 px, endpoint distance is at most 9 px, and the merged span stays within 4°.The lateral test prevents fusing parallel flanks of a thin bar across a large gap.
  • Merge behavior: k collinear fragments assemble in k −1 absorptions because each merged span rescans the active-chain list.Conflicts resolve greedily and deterministically in emission order.
  • Admission: 5 pixels is the linker-on admission threshold, lowered from Nth = 15 so broken fragments can reassemble before final length testing.Chains are retained at flush only when their Chebyshev span clears Nth; accepted full-threshold segments are never dropped.
  • Measured effect: ≈0.6 ms is the reported detection cost of the linker, with a downstream gain of 5.23° on NYU.Its F-max recovery is reported separately in Section 4.3.

F Default configuration

Table 18 consolidates the default parameters for SweepLSD’s shipped configuration on 8-bit grayscale input.

  • Table 18 collects the algorithmic defaults of the shipped detector in one place.
  • The shipped detector uses a single configuration throughout the paper.
  • The table’s parameters apply to 8-bit grayscale input.
Loading 2608.22086v1…