Multi-Target Tracking

This example demonstrates GNN-based multi-target tracking with track management.

Overview

Multi-target tracking (MTT) addresses:

  • Data association: Matching measurements to tracks

  • Track initiation: Detecting new targets

  • Track maintenance: Updating confirmed tracks

  • Track termination: Removing lost targets

Key Concepts

  • Global Nearest Neighbor (GNN): Optimal measurement-to-track assignment

  • Gating: Reducing assignment candidates using statistical tests

  • Track scoring: M/N logic and likelihood-based confirmation

  • Clutter modeling: False alarm rate estimation

Data Association: The Hungarian algorithm finds the optimal measurement-to-track assignment by minimizing total cost.

Performance Metrics: OSPA (Optimal Sub-Pattern Assignment) measures tracking accuracy including localization error, cardinality error, and labeling error.

Code Highlights

The example demonstrates:

  • Track initialization from unassigned measurements

  • GNN assignment using Hungarian algorithm

  • Kalman filter updates for each track

  • Track state machine (tentative, confirmed, deleted)

  • OSPA metric computation for performance evaluation

Source Code

  1"""
  2Multi-target tracking example.
  3
  4This example demonstrates:
  51. Simulating multiple crossing targets
  62. Using the MultiTargetTracker for GNN-based tracking
  73. Track initiation, confirmation, and deletion
  8
  9Run with: python examples/multi_target_tracking.py
 10"""
 11
 12# Add parent directory to path for development
 13import sys
 14from pathlib import Path
 15
 16sys.path.insert(0, str(Path(__file__).parent.parent))
 17
 18# Output directory for generated plots
 19OUTPUT_DIR = Path(__file__).parent.parent / "docs" / "_static" / "images" / "examples"
 20OUTPUT_DIR.mkdir(parents=True, exist_ok=True)
 21
 22import os
 23from typing import List, Tuple  # noqa: E402
 24
 25import numpy as np  # noqa: E402
 26import plotly.graph_objects as go  # noqa: E402
 27
 28from pytcl.trackers import (  # noqa: E402
 29    MultiTargetTracker,
 30    TrackStatus,
 31)
 32
 33SHOW_PLOTS = os.environ.get("PYTCL_SHOW_PLOTS", "1") != "0"
 34
 35
 36def simulate_targets(
 37    n_steps: int = 50,
 38    dt: float = 1.0,
 39) -> Tuple[List[np.ndarray], List[List[np.ndarray]]]:
 40    """
 41    Simulate two crossing targets with position measurements.
 42
 43    Returns
 44    -------
 45    true_states : list of ndarray
 46        Ground truth states [x1, y1, x2, y2] at each step.
 47    measurements : list of list of ndarray
 48        Noisy position measurements at each step.
 49    """
 50    # Target 1: Moving right and up
 51    x1_0, y1_0 = 0.0, 0.0
 52    vx1, vy1 = 2.0, 1.0
 53
 54    # Target 2: Moving left and up
 55    x2_0, y2_0 = 100.0, 0.0
 56    vx2, vy2 = -2.0, 1.5
 57
 58    true_states = []
 59    measurements = []
 60    R = np.eye(2) * 2.0  # Measurement noise covariance
 61
 62    for k in range(n_steps):
 63        t = k * dt
 64
 65        # True positions
 66        x1 = x1_0 + vx1 * t
 67        y1 = y1_0 + vy1 * t
 68        x2 = x2_0 + vx2 * t
 69        y2 = y2_0 + vy2 * t
 70
 71        true_states.append(np.array([x1, y1, x2, y2]))
 72
 73        # Generate noisy measurements
 74        meas = []
 75
 76        # Detection probability
 77        pd = 0.95
 78
 79        if np.random.rand() < pd:
 80            z1 = np.array([x1, y1]) + np.random.multivariate_normal([0, 0], R)
 81            meas.append(z1)
 82
 83        if np.random.rand() < pd:
 84            z2 = np.array([x2, y2]) + np.random.multivariate_normal([0, 0], R)
 85            meas.append(z2)
 86
 87        # Add occasional false alarms
 88        if np.random.rand() < 0.1:
 89            # Random false alarm in scene
 90            fa = np.array([np.random.uniform(-10, 110), np.random.uniform(-10, 60)])
 91            meas.append(fa)
 92
 93        measurements.append(meas)
 94
 95    return true_states, measurements
 96
 97
 98def run_tracker(
 99    measurements: List[List[np.ndarray]],
100    dt: float = 1.0,
101) -> List[List]:
102    """
103    Run multi-target tracker on measurements.
104
105    Returns list of track histories at each step.
106    """
107
108    # Constant velocity model: state = [x, vx, y, vy]
109    def F(dt):
110        return np.array(
111            [[1, dt, 0, 0], [0, 1, 0, 0], [0, 0, 1, dt], [0, 0, 0, 1]], dtype=np.float64
112        )
113
114    # Measurement model: measure x and y
115    H = np.array([[1, 0, 0, 0], [0, 0, 1, 0]], dtype=np.float64)
116
117    # Process noise (acceleration noise)
118    def Q(dt):
119        q = 0.5  # Acceleration noise std
120        return (
121            np.array(
122                [
123                    [dt**4 / 4, dt**3 / 2, 0, 0],
124                    [dt**3 / 2, dt**2, 0, 0],
125                    [0, 0, dt**4 / 4, dt**3 / 2],
126                    [0, 0, dt**3 / 2, dt**2],
127                ]
128            )
129            * q**2
130        )
131
132    # Measurement noise
133    R = np.eye(2) * 2.0
134
135    # Initial covariance for new tracks
136    P0 = np.diag([10.0, 5.0, 10.0, 5.0])
137
138    # Create tracker
139    tracker = MultiTargetTracker(
140        state_dim=4,
141        meas_dim=2,
142        F=F,
143        H=H,
144        Q=Q,
145        R=R,
146        gate_probability=0.99,
147        confirm_hits=3,
148        max_misses=5,
149        init_covariance=P0,
150    )
151
152    # Process all measurements
153    track_history = []
154
155    for meas in measurements:
156        tracks = tracker.process(meas, dt)
157        track_history.append(tracks)
158
159    return track_history
160
161
162def plot_results(
163    true_states: List[np.ndarray],
164    measurements: List[List[np.ndarray]],
165    track_history: List[List],
166) -> None:
167    """Plot tracking results."""
168    fig = go.Figure()
169
170    # Plot true trajectories
171    true_arr = np.array(true_states)
172    fig.add_trace(
173        go.Scatter(
174            x=true_arr[:, 0],
175            y=true_arr[:, 1],
176            mode="lines",
177            line=dict(color="green", width=2),
178            name="Target 1 (truth)",
179        )
180    )
181    fig.add_trace(
182        go.Scatter(
183            x=true_arr[:, 2],
184            y=true_arr[:, 3],
185            mode="lines",
186            line=dict(color="blue", width=2),
187            name="Target 2 (truth)",
188        )
189    )
190
191    # Collect all measurements for a single trace
192    meas_x = []
193    meas_y = []
194    for meas in measurements:
195        for z in meas:
196            meas_x.append(z[0])
197            meas_y.append(z[1])
198
199    fig.add_trace(
200        go.Scatter(
201            x=meas_x,
202            y=meas_y,
203            mode="markers",
204            marker=dict(color="black", size=3, opacity=0.5),
205            name="Measurements",
206        )
207    )
208
209    # Plot tracks
210    # Collect track positions by track ID
211    track_positions: dict[int, list] = {}
212    for tracks in track_history:
213        for track in tracks:
214            if track.status == TrackStatus.CONFIRMED:
215                if track.id not in track_positions:
216                    track_positions[track.id] = []
217                track_positions[track.id].append(
218                    (track.state[0], track.state[2])
219                )  # x, y
220
221    # Plotly color palette (similar to tab10)
222    colors = [
223        "#1f77b4",
224        "#ff7f0e",
225        "#2ca02c",
226        "#d62728",
227        "#9467bd",
228        "#8c564b",
229        "#e377c2",
230        "#7f7f7f",
231        "#bcbd22",
232        "#17becf",
233    ]
234
235    # Plot each track
236    for i, (track_id, positions) in enumerate(track_positions.items()):
237        if len(positions) > 1:
238            pos_arr = np.array(positions)
239            fig.add_trace(
240                go.Scatter(
241                    x=pos_arr[:, 0],
242                    y=pos_arr[:, 1],
243                    mode="lines+markers",
244                    line=dict(color=colors[i % 10], width=1.5),
245                    marker=dict(color=colors[i % 10], size=4),
246                    name=f"Track {track_id}",
247                )
248            )
249
250    fig.update_layout(
251        title="Multi-Target Tracking with GNN Data Association",
252        xaxis_title="X Position",
253        yaxis_title="Y Position",
254        xaxis=dict(scaleanchor="y", scaleratio=1),
255        width=1200,
256        height=800,
257        showlegend=True,
258    )
259
260    # Save as HTML (interactive) and PNG (static)
261    output_path = OUTPUT_DIR / "multi_target_tracking_result.html"
262    fig.write_html(
263        str(output_path), include_plotlyjs="cdn", div_id=Path(output_path).stem
264    )
265    print(f"Interactive plot saved to {output_path}")
266    if SHOW_PLOTS:
267        fig.show()
268    else:
269        OUTPUT_DIR.mkdir(parents=True, exist_ok=True)
270        fig.write_html(
271            str(OUTPUT_DIR / "multi_target_tracking.html"),
272            include_plotlyjs="cdn",
273            div_id="multi_target_tracking",
274        )
275
276
277def main():
278    """Run multi-target tracking example."""
279    print("Multi-Target Tracking Example")
280    print("=" * 50)
281
282    # Set random seed for reproducibility
283    np.random.seed(42)
284
285    # Simulate targets
286    print("Simulating two crossing targets...")
287    true_states, measurements = simulate_targets(n_steps=50, dt=1.0)
288    print(f"  Generated {len(true_states)} time steps")
289    print(f"  Total measurements: {sum(len(m) for m in measurements)}")
290
291    # Run tracker
292    print("\nRunning multi-target tracker...")
293    track_history = run_tracker(measurements, dt=1.0)
294
295    # Count tracks
296    all_tracks = set()
297    confirmed_tracks = set()
298    for tracks in track_history:
299        for track in tracks:
300            all_tracks.add(track.id)
301            if track.status == TrackStatus.CONFIRMED:
302                confirmed_tracks.add(track.id)
303
304    print(f"  Total tracks initiated: {len(all_tracks)}")
305    print(f"  Confirmed tracks: {len(confirmed_tracks)}")
306
307    # Final track summary
308    final_tracks = track_history[-1]
309    print(f"\nFinal active tracks: {len(final_tracks)}")
310    for track in final_tracks:
311        pos = (track.state[0], track.state[2])
312        vel = (track.state[1], track.state[3])
313        print(
314            f"  Track {track.id}: pos=({pos[0]:.1f}, {pos[1]:.1f}), "
315            f"vel=({vel[0]:.1f}, {vel[1]:.1f}), status={track.status.value}"
316        )
317
318    plot_results(true_states, measurements, track_history)
319
320    print("\nDone!")
321
322
323if __name__ == "__main__":
324    main()

Running the Example

python examples/multi_target_tracking.py

See Also