v1.4.1 — Kill per-patch heap traffic in Patchwork++ (+14.8% Hz)

Highlights

Patch bump. pypatchworkpp.patchworkpp is now +14.8% Hz on KITTI seq 00 (97.5 → 111.9 Hz, median of 3 runs, i7-12700) thanks to killing short-lived heap allocations in R-VPF + R-GPF. Closes the alloc-driven part of #96.

Perf — pypatchworkpp.patchworkpp

KITTI seq 00, 2900 timed frames, median of 3 runs:

Stage	ms/frame	Hz	Δ Hz
v1.4.0 baseline (JacobiSVD + per-call allocs)	10.26	97.5	—
eigh only	9.94	100.6	+3.2%
v1.4.1 (eigh + alloc-free)	8.94	111.9	+14.8%

The win comes from three changes inside PatchWorkpp::extract_piecewiseground and PatchWorkpp::estimate_plane:

1. estimate_plane: drop Eigen::MatrixX3f eigen_ground, centered, and centered.adjoint() * centered heap allocations. Replace with a single-pass scalar accumulation of mean + 9 cross-products; build the 3×3 cov on the stack.
2. extract_piecewiseground: promote src_wo_verticals and src_tmp to reused instance scratch members. vector::clear() keeps capacity, so per-patch malloc pressure on the glibc heap drops away after the first few patches.
3. estimateGround main loop: auto& zone instead of auto zone for ConcentricZoneModel_[zone_idx]. Avoids a deep-copy of the full 3-level nested vector per outer iteration.

Plus a smaller cleanup: JacobiSVD<Matrix3f> → SelfAdjointEigenSolver::computeDirect on the 3×3 PSD covariance in both cpp/common/src/plane_fit.cpp and the in-place PatchWorkpp::estimate_plane. singular_values_ is repacked descending so every consumer (linearity_, planarity_, ground_flatness, line_variable, flatness_thr index (2)) keeps the same convention bit-for-bit.

Patchwork (classic)

Unchanged: 4.29 ms / 232.9 Hz (within run-to-run noise of the v1.4.0 baseline). TBB parallel_for already amortises allocations across cores and SVD is sub-µs/patch.

Numerical equivalence

KITTI seq 00 (4541 frames), v1.4.0 → v1.4.1:

Method (protocol)	Before	After	Δ F1
patchwork (pw)	P 92.34, R 94.64, F1 93.41	P 92.34, R 94.64, F1 93.41	0.00
patchworkpp (pp)	P 94.88, R 98.47, F1 96.62	P 94.89, R 98.48, F1 96.63	+0.01

Algebraic identity of JacobiSVD vs eigh verified on 500 real KITTI patch covariances: normal_ (up to sign), singular_values_, linearity_, planarity_, ground_flatness, line_variable all match to FP precision.

Refs

• #100 — PR (perf: alloc-free + eigh)
• #96 — Issue (R-VPF / R-GPF allocation profile)

v1.4.0 — Shared common library + optional TBB on classic Patchwork (+1.73× Hz)

Highlights

• Shared cpp/common/ library for PointXYZ, PCAFeature, PatchStatus, estimate_plane, xy2theta, xy2radius, point_z_cmp. Three previously-drifted copies of the plane-fit math (which had caused real bugs — see Fix 2 in #90) collapse to one canonical implementation.
• pypatchworkpp.patchwork gains tbb::parallel_for. Measured 1.73× speedup on KITTI seq 00 (i7-12700, 24 logical cores): 8.31 ms → 4.81 ms median per frame, 120 → 208 Hz.
• TBB is optional at build time. If libtbb-dev / brew install tbb / vcpkg install tbb is present, you get the speedup; otherwise the build falls back to a sequential loop with a CMake STATUS message. CI / wheels keep working without TBB installed.
• pypatchworkpp.patchworkpp stays sequential — same TBB pattern was applied and benchmarked at 1 / 2 / 4 / 8 / 16 / 24 threads, every configuration was slower than single-thread (111 Hz → 93 Hz at 2 threads, → 69 Hz at 24 threads). Per-patch work is small (~14 µs avg) and dominated by short-lived allocations inside R-VPF + R-GPF; concurrent malloc serialises on the heap. See #96 for the full measurement and the conditions under which we'd revisit.
• python/examples/bench_hz.py — per-frame timing harness reporting median / mean / p95 / p99 ms and Hz.

Numerical equivalence

KITTI 00–10 full sweep (23,201 frames), Patchwork++ paper protocol, v1.3.1 → v1.4.0:

Method	F1 v1.3.1	F1 v1.4.0	Δ
--method patchwork	96.0172	96.0172	0 (byte-identical)
--method patchworkpp	96.2918	96.2919	+0.0001 (float noise)

Both within the ±0.05 F1 budget set in the refactor plan.

References

• #94 — PR: extract cpp/common/ library
• #95 — PR: TBB on classic Patchwork
• #96 — Issue: why Patchwork++ has no TBB
• #97 — PR: this release

See CHANGELOG.md for the full v1.4.0 entry.

v1.3.1 — Fix ringwise_flatness leakage in TGR (#69)

Bug fix

• #69 → #91: ringwise_flatness is now cleared at the end of every ring iteration in cpp/patchworkpp/src/patchworkpp.cpp, not only when the ring produced revert candidates. The previous placement leaked flatnesses from no-candidate rings into the next ring's temporal_ground_revert call, biasing the mean ± stdev decision threshold. Reported by @KennethBlomqvist.

Numerical impact

KITTI 00–10 full sweep (23,201 frames) under the Patchwork++ paper evaluation protocol:

Build	P	R	F1
v1.3.0	95.5494	97.1649	96.2886
v1.3.1	95.5496	97.1710	96.2918

ΔF1 = +0.003 (within run-to-run noise). The bug only triggers when a ring finishes with no revert candidates, which is uncommon on KITTI; macro-average impact is negligible but the fix is correctness.

See CHANGELOG.md.

v1.3.0 — Performance enhancement for pypatchworkpp.patchwork

Highlights

• +2.29 F1 on KITTI 00–10 for pypatchworkpp.patchwork (classic Patchwork). Three deviations from the original url-kaist/patchwork were identified and fixed; numbers now match the Patchwork++ paper Table I within run-to-run variance (96.02 vs. 95.88 F1).
• pypatchworkpp.patchworkpp (the real Patchwork++) is unaffected — all three fixes were in cpp/patchwork/, not cpp/patchworkpp/. Patchwork++ continues to match the paper.
• New USAGE.md explains the two SemanticKITTI evaluation protocols (Patchwork vs Patchwork++ paper), the parameter-tuning order, and a copy-pasteable command to reproduce paper Table I.
• New python/examples/evaluate_semantickitti.py — paper-faithful KITTI evaluation driver with --method {patchwork, patchworkpp} and --eval_protocol {patchwork, patchworkpp}.

Results — SemanticKITTI 00–10, 23,201 frames, paper-matched params

Configuration	Eval protocol	P	R	F1
pypatchworkpp.patchwork, v1.2.0	Patchwork-paper	86.94	96.75	91.37
pypatchworkpp.patchwork, v1.2.0	Patchwork++ paper	89.70	98.49	93.73
pypatchworkpp.patchwork, v1.3.0	Patchwork-paper	92.77	93.66	93.08
pypatchworkpp.patchwork, v1.3.0	Patchwork++ paper	94.64	97.58	96.02
url-kaist/patchwork original ROS 2 (reference)	Patchwork++ paper	94.38	97.90	96.05
Patchwork++ paper Table I, Patchwork [1]	Patchwork++ paper	94.23	97.62	95.88

The three fixes

1. elevation_thr is converted to the sensor frame by subtracting sensor_height. The YAML thresholds in the original repo are documented as ground-frame; the reimpl was using the raw value, so the elevation gate effectively never fired for normal ground.
2. Plane-distance comparison uses uncentred normal · p against th_dist_d_ = th_dist − d_. The previous centred form shifted the cutoff by an extra −d_ (~ 1.6 m on KITTI), absorbing far-from-plane points into ground.
3. Tier index is the GLOBAL ring index across all zones, so each of the first elevation_thr.size() rings gets its own threshold. The previous (zone==0) ? ring : zone collapse destroyed the per-ring tuning.

References

• #87 — How to reproduce the performance on the paper?
• #88 — Explanation about the evaluation protocol
• #89 — Performance enhancement step-by-step ablation report (with subset and full-sweep tables)
• #90 — PR landing the fixes

See CHANGELOG.md for the full changelog.

v1.2.0 — Crash fix for partial (non-360°) point clouds

What's new

Bug-fix release. Fixes a startup crash reported in #62 when processing partial (non-360°) point clouds — for example OS1 128 Ouster scans that don't begin at azimuth 0.

Changes since 1.1.0

• #81 (#62, supersedes #66 #72) — Switch `normal_`, `singular_values_`, and `pc_mean_` from `Eigen::VectorXf` (dynamic) to `Eigen::Vector3f` (fixed-size). The dynamic vectors were being indexed before being sized, which was safe with full 360° clouds but crashed on partial inputs. Thanks @MatteGombia for the original fix; @enricocovili for diagnosing the root cause in #62.

Compatibility

• API unchanged. No migration needed.
• Wheels for CPython 3.8 – 3.13 on Linux x86_64 (manylinux2014, musllinux), Windows 32/64-bit, macOS 14 (arm64).

v1.1.0 — Patchwork (classic) algorithm added

What's new

This release ships the original Patchwork ground segmentation algorithm alongside the existing Patchwork++, behind the same Python module and ROS2 node. Both algorithms are runtime-selectable; existing Patchwork++ users get the new option without any change in behavior.

New API

Python:

import pypatchworkpp as p

pp_default = p.patchworkpp(p.Parameters())          # Patchwork++ (unchanged)
pp_classic = p.patchwork(p.PatchworkParams())       # Patchwork (classic, NEW)

pp_classic.estimateGround(scan)
ground = pp_classic.getGround()
nonground = pp_classic.getNonground()

ROS2:

ros2 launch patchworkpp patchworkpp.launch.py algorithm:=patchwork

When to pick which

• Patchwork++ (default): adaptive elevation/flatness thresholds, RNR (intensity-based reflected noise removal), RVPF (vertical structure suppression), TGR (probability-based ground revert). Best for most LiDAR data and self-tuning thresholds.
• Patchwork (classic): fixed thresholds with explicit z < -sensor_height - 2.0m cutoff, few-points reject, and optional ATAT (auto sensor-height tuning). Often more aggressive on ground-plane noise in heavily cluttered scenes.

Compatibility

• The existing pypatchworkpp.patchworkpp API is bit-for-bit unchanged. No migration needed.
• Adding the new class is purely additive.
• Wheels built for: Linux x86_64 (manylinux2014), Windows 2022, macOS 14 (arm64). CPython 3.8 – 3.13.

Implementation notes

The classic algorithm was ported from the original Patchwork repo with PCL/TBB/ROS dependencies stripped. The Concentric Zone Model uses the parametric form (mirroring Patchwork++) instead of upstream's sensor-string-driven CZM. Per-patch processing is sequential; performance is fine for typical 100k-point scans.

See PR #79 for the full breakdown.

v1.0.4

Full Changelog: v.1.0.2...v1.0.4

v1.0.2

What's Changed

• Feature/eigen free by @LimHyungTae in #64

Full Changelog: v1.0.1...v.1.0.2

v1.0.0

Put const in the header file as well