SweepLSD — how it works

One sweep, all segments. A one-pass, O(width)-memory line segment detector with an integer-only streaming core.

SweepLSD segments on a Full-HD photo

Full-HD photo, 2980 segments in ~11 ms (one detector sweep, single thread).

The idea. Most line segment detectors hold the whole image (and several full-size intermediates) in memory and revisit pixels many times. SweepLSD instead treats the image as a row stream: every stage — smoothing, gradient, edge thinning, endpoint detection, labelling, even the final line test — is expressed so that it only ever needs a few rows of state. The image flows through once, top to bottom, and segments fall out as their last pixel passes by. That is what makes the design FPGA-friendly (the algorithm was designed for hardware in a 2014 master's thesis, where it was called OPLSD), and it is also why it is fast on CPUs: the working set stays in cache.

1. The pipeline

Five stages, each a simple row kernel. The figures below are the actual intermediates (sweeplsd_dump_stages) on a 960×540 photo.

input (8-bit grayscale)
1. gaussian 5×5, integer, {16,64,96,64,16}
2. gradient power (2×2 operator)
3. threshold + NMS → 1-px edges
4. endpoint candidates (red) on edges
5. labelled + judged → segments
  1. Gaussian. Separable 5×5 blur with weights {16,64,96,64,16}, all integer, one final >>10 rescale. The vertical pass fits exactly in uint16, so the compiler auto-vectorizes it 16 lanes wide.
  2. Gradient. A 2×2 operator on the smoothed image; power = (|dx|+|dy|+1)/2 and a direction quantised to just horizontal or vertical — that is all the NMS needs.
  3. Edge. Threshold on the power plus non-maximum suppression along the dominant gradient axis, branch-free.
  4. Endpoint candidates. A 5×5 ring test marks edge pixels where a segment starts, ends, branches or corners. A candidate is confirmed only where two are consecutive and the inner one is kept — a deterministic rule that also lands the recovered tips ≈1 px inside the true endpoint (a correctable extent bias; see the quality page). These delimit the pixel runs that may become segments.
  5. Labelling + judgment. A row-streaming connected-component labeller carries, per label, running scatter moments (Σx, Σy, Σx², Σxy, Σy², count). When a run closes — its second endpoint-candidate contact — it is judged on the spot: a segment is emitted iff it has enough pixels and the PCA eigenvalue ratio of its scatter says "thin and straight". The moments also give sub-pixel endpoints and the line direction for free.

2. The one-pass architecture

The library ships two drivers over the same kernels, tested to produce identical output:

driverwhat it doesmemoryspeed (Full-HD)
detect()one full-image pass per stage — easiest to read and debugO(pixels)~12 ms
detectOnePass()single top-to-bottom sweep; each stage keeps only the rows the next stage needs; labelling trails the input by 7 rowsO(width)~11 ms

The per-pixel core is integer-only (the thesis targeted an FPGA datapath); floating point appears only in the once-per-segment finalization (PCA, endpoint projection). There are no SIMD intrinsics anywhere — the kernels are written so GCC/Clang auto-vectorize them, which keeps the code readable and portable.

The hardware-friendliness is not hypothetical: the detector runs live on a 2009-era FPGA — HDMI in → detect → overlay out at 1080p30, with no frame buffer.

How the labelling stays O(width). The connected-component labeller is a single-pass union–find (with path compression) that merges edge runs touching across adjacent rows. What keeps its memory bounded is label recycling: labels live in a fixed pool addressed through a ring free-list, split into a hot record (moment accumulation for active runs) and a cold record (dormant). The instant a component can no longer be touched — its last edge row has passed above the scan line — an end-of-row retire sweep frees its slot for reuse. The number of live labels is therefore bounded by the image width, not its pixel count: the working set is ~15 KB and stays in cache, where a grow-forever label table would reach tens of thousands of slots (megabytes) on a dense frame. The pool is sized to width/4 and grows to width/2 only on abnormal inputs; a correct image never exceeds it (in hardware, overflow drops labels rather than allocating). This is what turns "a few rows of pixels" into a genuine O(width) memory bound end to end.

3. Measured refinements (all on by default)

Params{} is SweepLSD as published: the refinements below are all enabled, and each was added only after measuring its effect on the three evaluation axes (synthetic-GT F-score, real-photo inspection, downstream vanishing points). The right-hand column states which way each one moved the needle; the measurements behind it are on the quality and vanishing-point pages. Each can be disabled individually, and Params::original2014() reproduces the 2014 thesis implementation's behaviour, so any row can be reproduced by turning it off:

improvementwhatmeasured effect
strict NMS tie-breakgradient plateaus thin to 1 px instead of 2cleaner edges, fewer duplicate labels
sub-pixel NMSparabolic peak interpolation accumulated into the momentslateral error ↓
streaming hysteresislow extraction threshold + per-label strong-pixel requirement; the low threshold adapts to the image noise floor (O(1) state)recall ↑ on clean images without flooding noisy ones
endpoints from projection extremesbounding-box corners projected on the fitted axisrobust when a label has >2 endpoint contacts
curve rejectionabsolute bound on the perpendicular RMS spreadcircles/arcs rejected by design (see the isotropy page)
half-pixel lattice shiftthe 2×2 gradient lives on pixel corners; output is shifted +0.5 px (canonical LSD applies the same correction)systematic −0.5 px bias → 0; lateral error 0.92→0.12 px

All refinements preserve the streaming / O(width) property. One optional feature is off by default: a gap-tolerant collinear linker (link_collinear) that re-assembles fragments across junction cuts and noise breaks — its measured effect is reported on the quality and vanishing-point pages, always explicitly labelled.

Known limitation, stated plainly. SweepLSD's edge model is contrast-gated: a pixel becomes an edge only if its gradient peak clears a threshold. Soft, wide luminance ramps (dim wall corners, defocused structure) never form a peak, so LSD / EDLines / ELSED — which link pixels by orientation coherence instead — recover some low-contrast structure SweepLSD misses. The quality and vanishing-point pages quantify exactly when this matters and when it does not.