PaperlayerView exact revision on arXiv

Source-linked AI summary

Hierarchical Sparse Graph for Multi-dimensional Assignment in Event-based Tracking

Muxi Zha, Yang Shang, Wenlong Zhang, Qifeng Yu, Banglei Guan

arXiv:2610.37321v1cs.CV

TL;DR

Long-term occlusions and missed detections motivate association across a broader temporal window, while event-based detections create an underdetermined many-to-many matching problem. The paper combines fuzzy kinematic correlations in an HSG and partitions it adaptively; it reports over 2× OC-SORT across all metrics in many-to-many tracking.

  • Problem

    Online event-based tracking associates adjacent batches, while long-term occlusions and missed detections motivate association across a broader temporal window.

    Source: §I · p. 1

  • Method

    The method combines long-range kinematic metrics as fuzzy tracklet correlations, constructs an HSG, and uses heuristic adaptive graph partitioning for assignment.

    Source: §I · p. 2

  • Results

    Over 2× OC-SORT across all metrics in the many-to-many scenario, including tiny objects (6.8 × 5.4 pixels) under large spatio-temporal gaps.

    Source: §I · p. 2

  • Takeaways & Limitations

    The training-free method shows strong performance in both one-to-one and many-to-many matching scenarios across challenging conditions.

    Source: §VI · p. 15

    Voting-based graph partitioning can misassociate tracklets when evidence is sparse or ambiguous, including in extremely dense crowds with overlapping trajectories and similar motion.

    Source: G. Discussion · pp. 14–15

Abstract

from arXiv · show

Existing event-based tracking methods typically operate in an online manner, associating tracklets across adjacent batches. However, this limited temporal window often leads to failures in challenging scenarios, such as long-term occlusions or missed detections, where broader temporal context should be incorporated for high-precision tracking. To achieve robust and accurate tracking, this paper concentrates on the event-based multi-dimensional assignment that associates tracklets across multiple batches simultaneously. Unlike image-based detectors, event-based detectors can generate multiple correct yet spatially distinct tracklets for a single object per batch. This violates the one-to-one rule in classic data association, making event-based association an underdetermined many-to-many matching problem. To the best of our knowledge, this is the first work to tackle this NP-hard problem. To address its underdetermined nature, we formulate the assignment problem via fuzzy logic, where pairwise tracklet correlations are quantified through multiple long-range kinematic metrics. This fuzzy design eliminates the need for hard tracking thresholds and enables multiple heterogeneous metrics to be integrated into a unified correlation. By treating tracklets as nodes and their fuzzy correlations as edges, we construct a Hierarchical Sparse Graph (HSG). Building upon the HSG, we pose assignment as a graph partition task, and employ a heuristic solution that measures vertex affinity for partitioning adaptively. The entire pipeline is training-free. Comprehensive experiments on two challenging event datasets, eTram and Ev-UAV, show that our method outperforms existing event-based and most image-based association models. Particularly, it achieves over 2$\times$ the performance of OC-SORT across all metrics in the many-to-many association scenario.

I. INTRODUCTION

Event-based multi-dimensional assignment extends association across batches, addressing an underdetermined many-to-many problem created by multiple valid tracklets per object. The paper introduces fuzzy kinematic correlations and a Hierarchical Sparse Graph (HSG), then evaluates the training-free approach against existing methods.

I. INTRODUCTION

  • Multiple spatially distinct tracklets can all be valid for one event-based object, making association an underdetermined many-to-many problem whose difficulty grows with the association period.Unlike image detections, these event detections cannot simply be suppressed because they may represent different temporal segments of an event trajectory.Source: §I · pp. 1–2
  • Fuzzy modeling combines multiple kinematic metrics into unified tracklet correlations and constructs an HSG for assignment optimization.The proposed heuristic groups tracklets into cohesive partitions using vertex affinity and an adaptive threshold, avoiding a manually set merging threshold.Source: §I · p. 2
  • The paper introduces B´ezier-based position smoothness and direction-displacement-based variation consistency to capture long-range tracklet coherence in positional and directional domains.Source: §I · p. 2
  • Over 2× OC-SORT across all metrics for tiny objects (6.8 × 5.4 pixels) under large spatio-temporal gaps, while remaining competitive with leading image-based networks.The method is training-free and consistently outperforms existing event-based and motion-based methods.Source: §I · p. 2

II. RELATED WORKS

  • Prior event-based association work largely focuses on adjacent batches, while this paper studies multi-dimensional assignment across multiple batches.Source: §II · p. 2

A. Event-based association

The section motivates long-range event-tracklet association and formulates it as graph partitioning, with fuzzy correlations representing relationships among candidate tracklets. It introduces quadratic B´ezier position fitting to capture long-term trajectory smoothness without cubic-curve overfitting.

A. Event-based association

  • Existing event-based methods associate adjacent batches, limiting their ability to associate fragmented tracklets separated by large spatio-temporal gaps.Source: A. Event-based association · pp. 2–3

B. Image-based multi-dimensional assignment

  • Image-based multi-dimensional assignment relies on one-to-one matching, which does not fit event-based many-to-many association; appearance cues are also largely unavailable in events.The paper therefore uses kinematic features to model relationships between tracklet pairs.Source: B. Image-based multi-dimensional… · p. 3

III. FUZZY-BASED OPTIMIZATION FORMULATION

  • The section presents an optimization objective for event-based multi-dimensional assignment and details a fuzzy modeling pipeline that defines and computes two input metrics, uses hierarchical and sparse quantization, and produces the resulting HSG.Source: §III · p. 3

A. Event-based Multi-dimensional Assignment Optimization

B. B´ezier curve-based Position Smoothness

  • Quadratic B´ezier fitting is selected for position smoothness because cubic curves can fit incorrect matches well, risking overfitting at event cameras’ high temporal resolution.The quadratic curve uses three control points; its smoothness error is computed from the fitted points and tracklet samples.Source: B. B´ezier curve-based Position… · p. 4

C. Direction-displacement-based Variation Consistency

Position smoothness alone can admit spatially close tracklets with different velocities, so the method adds velocity consistency as a second cue. It uses direction and displacement variation to help distinguish correct long-range matches.

C. Direction-displacement-based Variation Consistency

  • Velocity consistency complements position smoothness, which can be small for spatially close tracklets with significantly different velocities.The method focuses on direction because speed is difficult to estimate accurately from asynchronous events.Source: C. Direction-displacement-based… · p. 4
  • Eθ quantifies the average cosine similarity between tracklet directions and their positional displacement.Fig. 5 places the two kinematic metrics in a fuzzy modeling pipeline that produces unified correlations for an HSG.Source: C. Direction-displacement-based… · p. 5, Figure 5 · p. 5
  • Higher Eθ values distinguish correct matches from incorrect ones in the illustrated association cases.The paper reports that Eθ disambiguates cases that Ep cannot distinguish.Source: C. Direction-displacement-based… · p. 5, Figure 6 · p. 5

D. The Computation of Metrics

Long temporal gaps can undermine both positional and directional metrics, motivating a temporal weight for positional error. The method adjusts that weight using temporal proximity, match history, and object size.

D. The Computation of Metrics

  • With large temporal gaps, Ep may be low even for incorrect pairs, while Eθ may remain large across candidates and fail to distinguish matches.The latter issue arises because the temporal component can dominate direction vectors, making spatial variation negligible.Source: D. The Computation of Metrics · p. 5
  • The temporal weight λ adjusts Ep according to association reliability over temporal intervals.It is introduced to address the positional-error issue that temporal scaling does not resolve.Source: D. The Computation of Metrics · p. 5

E. Temporal Weight Analysis λ

  • Ep computation proceeds from temporally proximal candidates to distant ones, with historical match count α affecting whether farther candidates remain reliable.Low α allows association to more distant candidates to help recover from fragmentation; high α calls for caution with remaining candidates.Source: E. Temporal Weight Analysis λ · pp. 5–6
  • Object size also adjusts λ, assigning higher weights to small objects and lower weights to large ones.The adjustment addresses positional-error ambiguity in dense or frequently overlapping scenarios.Source: E. Temporal Weight Analysis λ · p. 6

F. Hierarchical and Sparse Quantization

The method maps heterogeneous positional and directional metrics to unified correlations through hierarchical and sparse quantization. It first normalizes and filters candidate pairs, then assigns discrete correlation levels.

F. Hierarchical and Sparse Quantization

  • Ep is measured in pixels over [0, ∞), whereas Eθ is unitless over [−1, 1], complicating their direct integration into a unified correlation.Source: F. Hierarchical and Sparse Quantization · p. 6
  • The method normalizes Ep by object width and initially filters pairs with E′p > 1 or Eθ < 0.Remaining normalized positional errors and directional variations share the range [0, 1].Source: F. Hierarchical and Sparse Quantization · p. 6
  • Hierarchical modeling assigns N valid correlation levels plus level 0 for outliers, clustering metric values with K-means++ and ordering centroids by metric.Centroids are sorted descending for Ep and ascending for Eθ.Source: F. Hierarchical and Sparse Quantization · p. 6
  • The final correlation between tracklets i and j sums their directional correlation levels, with a bias distinguishing line-based and Bézier-based position fits.Sparse modeling prunes irrelevant edges to reduce computational burden.Source: F. Hierarchical and Sparse Quantization · p. 6

IV. CONNECTION SIMILARITY BASED GRAPH PARTITION

The underdetermined assignment is solved by heuristically partitioning the HSG through adaptive vertex merging. Connection similarity measures affinity using shared-neighbor edge weights.

IV. CONNECTION SIMILARITY BASED GRAPH PARTITION

  • An adaptive-threshold search-merge heuristic partitions the HSG because the underdetermined combinatorial assignment has no closed-form solution.The approach uses graph topology and edge weights to guide vertex merging.Source: §IV · p. 6

A. Connection Similarity

  • Connection similarity measures vertex affinity using the proportion of edge weight shared through common neighbors relative to each vertex’s total weight.The two scores are asymmetric, one for each merging direction.Source: A. Connection Similarity · p. 6
  • Shared neighbors can support merging vertices even when the vertices lack a direct link.Source: A. Connection Similarity · p. 6

B. Threshold for Connection Similarity under a Null Model

The null-model threshold estimates expected connection similarity under random connectivity and provides a lower bound for vertex merging. A size-adjustment factor mitigates the threshold’s sensitivity to vertices of substantially different sizes.

B. Threshold for Connection Similarity under a Null Model

  • The adaptive threshold τ approximates expected connection similarity in a randomly connected graph and serves as the lower bound for merging vertices.Vertices are merged when their connection similarity meets the threshold.Source: B. Threshold for Connection Similarity… · p. 7
  • The null model estimates the number of mergeable candidates from neighboring nodes and the sizes of the vertices being considered.It uses the number of neighboring nodes of ui and the nodes in uj to estimate m.Source: B. Threshold for Connection Similarity… · p. 7
  • Replacing m with m + 1 in the denominator avoids an overly strict merging condition when m is below 1 and graph density is high.The numerator retains m to preserve the expected edge connection; the experiments use this alternative formulation.Source: B. Threshold for Connection Similarity… · p. 7
  • The factor γ mitigates the effect of large size differences between vertices because the null model assumes comparable vertex sizes.The threshold’s numerator represents expected direct connections, which lower-bound a similarity measure that also captures indirect connections.Source: B. Threshold for Connection Similarity… · p. 7

C. Two-stage graph partition

The graph partition procedure repeatedly searches for mergeable neighboring vertices, merges vertices with shared labels, and rebuilds the graph until no further merges remain. It partitions disconnected subgraphs independently to reduce computation.

C. Two-stage graph partition

  • Partitioning each disconnected subgraph independently reduces computation compared with partitioning the full graph.HSG edge weights encode correlation strength, allowing disconnected subgraphs to serve as initial partitions.Source: C. Two-stage graph partition · p. 7
  • The search stage evaluates connection similarity for neighboring vertex pairs and assigns a common label when the merging criterion is met.The procedure examines all vertices before moving to the merge stage.Source: C. Two-stage graph partition · p. 8
  • In the merge stage, vertices with the same label are integrated and the graph is reconstructed with an updated vertex set.Search and merge repeat until no mergeable vertices remain, yielding the final partition.Source: C. Two-stage graph partition · p. 8

V. EXPERIMENTS

The experiments evaluate association on eTram and Ev-UAV, using dataset-specific tracking metrics and comparisons with event-based and image-based methods. They also include ablations and parameter sensitivity experiments.

V. EXPERIMENTS

  • Experiments use eTram, an event-based traffic MOT dataset, and Ev-UAV, an event-based tiny-object detection dataset with event-wise labels.The datasets include challenging lighting conditions; Ev-UAV covers high-brightness and low-light scenarios.Source: §V · p. 8
  • The experiments assess component contributions and robustness under different parameter configurations.The eTram event-based comparison table reports MOT performance for different association methods.Source: §V · p. 8, Table I · p. 9

A. Evaluation metrics and model configurations

  • Evaluation reports MT, ML, MOTA, and IDF1 on eTram, and IDF1, IoU, Acc, Track IoU, and Track Acc on Ev-UAV.Track IoU and Track Acc extend the original metrics by matching predicted identities with ground-truth identities.Source: A. Evaluation metrics and model… · p. 8

B. Comparison methods

  • Comparisons include event-based association and single-object tracking methods, plus image-based MOT association modules and the multi-dimensional assignment model LPT.OC-SORT is the primary Ev-UAV baseline; the comparison also substitutes the association modules in image-based trackers with the proposed method.Source: B. Comparison methods · p. 8

C. Tracking on eTram

On Ev-UAV, HSG outperforms OC-SORT by over 2× across all reported metrics on both the original and corrected data. On eTram, results vary by detector, with strong gains under RVT and trade-offs under YOLOX; qualitative cases show successful association across missed detections and occlusions.

C. Tracking on eTram

  • Under GT detections, our method achieves 98.5 MOTA and 95.7 IDF1 on the validation set, and 98.4 MOTA and 95.3 IDF1 on the test set.It surpasses the second-best method by 8% in MOTA and 50% in IDF1.Source: C. Tracking on eTram · p. 9
  • With YOLOX on eTram, HSG trails OC-SORT by 0.6% in MOTA and 0.5% in IDF1 but leads by >3% in the other three metrics.The authors attribute OC-SORT’s slight advantage to filtering fragmented tracklets, reducing false positives and identity switches.Source: C. Tracking on eTram · p. 9
  • In qualitative eTram cases, HSG associates fragmented tracklets across missed detections and partial occlusions where OC-SORT fails.HSG also fails where a detection box contains nearly zero events, making event-based association infeasible.Source: C. Tracking on eTram · pp. 9, 11, Figure 9 · p. 9, Figure 10 · p. 11
  • Under RVT on eTram, HSG surpasses OC-SORT by >5% in MT and ML and >11% in IDF1.Across three detectors, HSG consistently outperforms association baselines under Permatrack, UAVMOT, and RVT.Source: C. Tracking on eTram · p. 9, Table II · p. 10

D. Tracking on Ev-UAV

  • Ev-UAV’s corrected labels were manually refined on 20 of 48 test and validation sequences, and results are reported for both the 28 unmodified sequences and the full set.The refinements compared UAV motion patterns in 2D and 3D; the corrected annotations are intended for future public release.Source: D. Tracking on Ev-UAV · p. 11
  • Over 2× across all metrics, HSG outperforms OC-SORT on both original and corrected Ev-UAV sets.The results support robust association of long-range fragmented tracklets into complete trajectories.Source: Table III · p. 11, D. Tracking on Ev-UAV · p. 11
  • Ev-UAV evaluation targets many-to-many association of tiny objects without appearance cues, and HSG links isolated tracklets across challenging motion patterns.The dataset’s original tracking labels were corrected on test and validation sets.Source: D. Tracking on Ev-UAV · p. 11

E. Computational Efficiency

The method processes over 1M events per second without GPU resources, while its modeling stage is the main computational bottleneck. Ablations examine the motion metrics, temporal weighting, and adaptive merging threshold across eTram and Ev-UAV.

E. Computational Efficiency

  • O(N^2 + N·ζ^2·log2 N) is the overall time complexity, with O(N^2) modeling and O(N·ζ^2·log2 N) graph partitioning.N is the number of tracklets and ζ is the number of candidates per tracklet after sparsification.Source: E. Computational Efficiency · pp. 11–12

F. Ablation Studies

  • Nearly 2× improvement on corrected Ev-UAV results comes from adding B́ezier position smoothness compared with the variant without that term.On the original set, incorrect ground-truth labels split trajectories and penalize the metric; on eTram, the improvement is modest because motion is predominantly linear.Source: Table V · p. 12, F. Ablation Studies · p. 13, Table VI · p. 13
  • On eTram, quadratic B́ezier fitting outperforms linear and cubic fitting by 0.1%–0.3% in MOTA and IDF1, while quadratic fitting gives the best Ev-UAV trade-off.Source: F. Ablation Studies · p. 13, Table VII · p. 13, Table VIII · p. 13
  • On eTram, removing direction-displacement consistency raises IDF1 by 0.1% but can cause over-association; on Ev-UAV, the full model performs better most of the time.The illustrated eTram cases show HSG distinguishing nearby tracklets with different directions where the variant without this term associates them incorrectly.Source: Table V · p. 12, F. Ablation Studies · pp. 13–14, Figure 13 · p. 13
  • Omitting temporal weight λ drops IDF1 by over 15% under GT detections and 10% under YOLOX detections on eTram.The paper attributes the degradation to association unreliability over long time intervals.Source: F. Ablation Studies · p. 14, Table IX · p. 14
  • Adaptive τ is more robust and accurate than fixed thresholds on both datasets; on eTram, HSG significantly outperforms variants omitting γ or the m + 1 denominator (p < 0.05).On Ev-UAV, those variants are sometimes on par with or better than HSG, which the authors attribute to differing graph sparsity.Source: F. Ablation Studies · p. 14, Figure 14 · p. 14, Table X · p. 14

G. Discussion

The graph-partitioning approach can make erroneous associations when voting evidence is insufficient or ambiguous, especially in dense crowds. The conclusion presents the training-free, plug-and-play method as effective across one-to-one and many-to-many scenarios, including long-range and tiny-object tracking.

G. Discussion

  • Without enforcing global continuity within a partition, voting can misassign tracklets when evidence is insufficient or ambiguous.With sparse evidence, an isolated tracklet may be absorbed into a continuous trajectory based on spatial proximity and similar motion direction.Source: G. Discussion · p. 14
  • In extremely dense crowds, overlapping event trajectories and similar motion patterns make the voting evidence ambiguous.The authors suggest examining a sliding window of tracklets within each partition or developing incremental metrics for motion continuity across tracklets.Source: G. Discussion · p. 15

VI. CONCLUSION

  • The training-free, plug-and-play method shows strong performance across one-to-one and many-to-many scenarios, particularly for long-range and tiny-object tracking.Source: §VI · p. 15

Related papers

Loading 2610.37321v1…