{ "cells": [ { "cell_type": "markdown", "id": "b4e16687", "metadata": {}, "source": [ "# SimpleTrack Deep Dive - 03: Data Association - 3D IoU / GIoU / L2 Affinity + the Hungarian Algorithm\n", "\n", "Given $M$ predicted track boxes and $N$ new detection boxes, **data association** decides the one-to-one matching between them. It has two parts: (a) an **affinity/cost metric** that scores how well a track box and a detection box agree, and (b) a **solver** that picks the best global matching. SimpleTrack's paper specifically studies the affinity choice and argues for **3D Generalized IoU (GIoU)**." ] }, { "cell_type": "code", "execution_count": 1, "id": "b5130af2", "metadata": { "execution": { "iopub.execute_input": "2026-08-02T03:39:28.321368Z", "iopub.status.busy": "2026-08-02T03:39:28.321015Z", "iopub.status.idle": "2026-08-02T03:39:28.860621Z", "shell.execute_reply": "2026-08-02T03:39:28.859930Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "IN_CONTAINER : True\n", "SIMPLETRACK_SRC : /workspace/perception/simpletrack exists= True\n", "NUSC_ROOT : /data/nuscenes exists= True\n", "RESULTS_DIR : /results exists= True\n" ] } ], "source": [ "# --- Common bootstrap (safe to run first in any SimpleTrack notebook) ---\n", "import os, sys, math, json, textwrap\n", "import numpy as np\n", "\n", "def _first_existing(paths, default):\n", " for p in paths:\n", " if p and os.path.isdir(p):\n", " return p\n", " return default\n", "\n", "IN_CONTAINER = os.path.isdir(\"/workspace/perception\")\n", "SIMPLETRACK_SRC = os.environ.get(\"SIMPLETRACK_SRC\") or _first_existing(\n", " [\"/workspace/perception/simpletrack\",\n", " \"/home/nadurthi/repos/deeplearning/perception/simpletrack\"],\n", " \"/home/nadurthi/repos/deeplearning/perception/simpletrack\")\n", "NUSC_ROOT = os.environ.get(\"NUSC_ROOT\") or _first_existing(\n", " [\"/data/nuscenes\", \"/mnt/mydata/nuscenes/mini_root\", \"/mnt/mydata/nuscenes\"],\n", " \"/mnt/mydata/nuscenes\")\n", "RESULTS_DIR = os.environ.get(\"BEVFUSION_RESULTS_DIR\") or _first_existing(\n", " [\"/results\", \"/mnt/mydata/nuscenes/results\"], \"/mnt/mydata/nuscenes/results\")\n", "\n", "if SIMPLETRACK_SRC and os.path.isdir(SIMPLETRACK_SRC) and SIMPLETRACK_SRC not in sys.path:\n", " sys.path.insert(0, SIMPLETRACK_SRC)\n", "\n", "import matplotlib\n", "if os.environ.get(\"MPLBACKEND\") is None:\n", " try: matplotlib.use(\"Agg\")\n", " except Exception: pass\n", "import matplotlib.pyplot as plt\n", "import matplotlib.patches as mpatches\n", "np.set_printoptions(precision=3, suppress=True)\n", "\n", "print(\"IN_CONTAINER :\", IN_CONTAINER)\n", "print(\"SIMPLETRACK_SRC :\", SIMPLETRACK_SRC, \"exists=\", os.path.isdir(SIMPLETRACK_SRC))\n", "print(\"NUSC_ROOT :\", NUSC_ROOT, \"exists=\", os.path.isdir(NUSC_ROOT))\n", "print(\"RESULTS_DIR :\", RESULTS_DIR, \"exists=\", os.path.isdir(RESULTS_DIR))\n" ] }, { "cell_type": "code", "execution_count": 2, "id": "1922a4f4", "metadata": { "execution": { "iopub.execute_input": "2026-08-02T03:39:28.862640Z", "iopub.status.busy": "2026-08-02T03:39:28.862334Z", "iopub.status.idle": "2026-08-02T03:39:28.870516Z", "shell.execute_reply": "2026-08-02T03:39:28.870037Z" } }, "outputs": [], "source": [ "# --- Reusable BEV geometry + drawing helpers (oriented boxes in the ground plane) ---\n", "def box_corners_2d(cx, cy, w, l, yaw):\n", " \"\"\"4 corners (l=along-heading, w=lateral) of a BEV box, CCW.\"\"\"\n", " c, s = np.cos(yaw), np.sin(yaw)\n", " R = np.array([[c, -s], [s, c]])\n", " local = np.array([[ l/2, w/2], [ l/2, -w/2], [-l/2, -w/2], [-l/2, w/2]])\n", " return (local @ R.T) + np.array([cx, cy])\n", "\n", "def draw_box(ax, cx, cy, w, l, yaw, color='C0', lw=2, label=None, alpha=1.0, ls='-'):\n", " cc = box_corners_2d(cx, cy, w, l, yaw)\n", " cc = np.vstack([cc, cc[0]])\n", " ax.plot(cc[:, 0], cc[:, 1], color=color, lw=lw, alpha=alpha, ls=ls)\n", " # heading tick\n", " hc, hs = np.cos(yaw), np.sin(yaw)\n", " ax.plot([cx, cx + hc*l*0.6], [cy, cy + hs*l*0.6], color=color, lw=lw, alpha=alpha)\n", " if label:\n", " ax.text(cx, cy, str(label), color=color, fontsize=9, ha='center', va='center')\n", "\n", "def new_bev_ax(title, lim=None, figsize=(6,6)):\n", " fig, ax = plt.subplots(figsize=figsize)\n", " ax.set_aspect('equal'); ax.grid(alpha=0.3)\n", " ax.set_xlabel('x (m)'); ax.set_ylabel('y (m)'); ax.set_title(title)\n", " if lim: ax.set_xlim(lim[0], lim[1]); ax.set_ylim(lim[2], lim[3])\n", " return fig, ax\n" ] }, { "cell_type": "markdown", "id": "ebf5d09d", "metadata": {}, "source": [ "## 1. Affinity metric #1 - Euclidean / L2 center distance\n", "The simplest affinity is the negative distance between box centers (this is what the nuScenes tracking baseline and the AB3DMOT 'dist' variant use):\n", "$$ \\text{cost}_{L2}(t, d) = \\lVert \\mathbf{c}_t - \\mathbf{c}_d \\rVert_2 . $$\n", "Cheap and robust to size errors, but **size/orientation-blind**: a big truck and a small car whose centers coincide look identical. It also needs a hand-tuned gating radius that varies by class." ] }, { "cell_type": "markdown", "id": "8d8f01c9", "metadata": {}, "source": [ "## 2. Affinity metric #2 - 3D IoU, and its blind spot\n", "**Intersection-over-Union** of the two oriented 3D boxes:\n", "$$ \\text{IoU}(t,d) = \\frac{|B_t \\cap B_d|}{|B_t \\cup B_d|} \\in [0,1]. $$\n", "IoU is size- and orientation-aware, which is why AB3DMOT used it. **But IoU = 0 for any pair that does not overlap** — and it gives *no gradient of closeness* between two disjoint boxes. When the detector misses a frame or the object moves fast, the predicted and detected boxes often don't overlap at all, so IoU cannot tell 'just barely missed' from 'across the street'. That is the exact failure SimpleTrack calls out." ] }, { "cell_type": "markdown", "id": "8871de42", "metadata": {}, "source": [ "## 3. Affinity metric #3 - Generalized IoU (GIoU): SimpleTrack's choice\n", "**GIoU** repairs IoU's disjoint-box blind spot by subtracting the 'wasted space' of the smallest **enclosing** box $C$ that contains both:\n", "$$ \\text{GIoU}(t,d) = \\text{IoU}(t,d) - \\frac{|C \\setminus (B_t \\cup B_d)|}{|C|} \\in (-1, 1]. $$\n", "* When the boxes overlap, GIoU $\\approx$ IoU.\n", "* When they are disjoint, IoU $=0$ but **GIoU keeps decreasing toward $-1$ as they move apart**, so it still provides a meaningful *ordering* of candidate matches. This monotone signal in the no-overlap regime is precisely why SimpleTrack adopts **3D GIoU** as its default association metric and reports it reduces ID-switches vs IoU (paper §4.3). We compute GIoU in the BEV plane and multiply by the height overlap term for the 3D version; the BEV term dominates for road scenes.\n", "\n", "The cell below implements axis-robust polygon IoU/GIoU via shapely if available, else a rasterized fallback so it always runs, and plots IoU vs GIoU as two boxes separate." ] }, { "cell_type": "code", "execution_count": 3, "id": "f6f6107f", "metadata": { "execution": { "iopub.execute_input": "2026-08-02T03:39:28.872456Z", "iopub.status.busy": "2026-08-02T03:39:28.872214Z", "iopub.status.idle": "2026-08-02T03:39:29.105258Z", "shell.execute_reply": "2026-08-02T03:39:29.104693Z" } }, "outputs": [], "source": [ "def _poly(cx,cy,w,l,yaw):\n", " return box_corners_2d(cx,cy,w,l,yaw)\n", "\n", "def _polys_iou_giou(A, B):\n", " \"\"\"Return (IoU, GIoU) of two BEV quadrilaterals A,B (4x2 arrays). shapely if present, else raster.\"\"\"\n", " try:\n", " from shapely.geometry import Polygon\n", " pa, pb = Polygon(A), Polygon(B)\n", " inter = pa.intersection(pb).area; uni = pa.union(pb).area\n", " iou = inter/uni if uni>0 else 0.0\n", " allpts = np.vstack([A,B])\n", " # smallest *axis-aligned* enclosing box as a cheap convex hull proxy for C\n", " from shapely.geometry import MultiPoint\n", " C = MultiPoint([tuple(p) for p in allpts]).convex_hull.area\n", " giou = iou - (C - uni)/C if C>0 else iou\n", " return iou, giou\n", " except Exception:\n", " # rasterized fallback on a fine grid\n", " allpts=np.vstack([A,B]); lo=allpts.min(0)-1; hi=allpts.max(0)+1\n", " gx,gy=np.meshgrid(np.linspace(lo[0],hi[0],200), np.linspace(lo[1],hi[1],200))\n", " P=np.stack([gx.ravel(),gy.ravel()],1)\n", " def inside(poly,P):\n", " n=len(poly); ins=np.zeros(len(P),bool); j=n-1\n", " for i in range(n):\n", " xi,yi=poly[i]; xj,yj=poly[j]\n", " cond=((yi>P[:,1])!=(yj>P[:,1])) & (P[:,0] < (xj-xi)*(P[:,1]-yi)/(yj-yi+1e-12)+xi)\n", " ins ^= cond; j=i\n", " return ins\n", " ia,ib=inside(A,P),inside(B,P); cell=((hi[0]-lo[0])/200)*((hi[1]-lo[1])/200)\n", " inter=(ia&ib).sum()*cell; uni=(ia|ib).sum()*cell\n", " iou=inter/uni if uni>0 else 0.0\n", " # enclosing = axis-aligned bbox area\n", " C=(hi[0]-lo[0]-2)*(hi[1]-lo[1]-2)\n", " giou=iou-(C-uni)/C if C>0 else iou\n", " return iou,giou\n", "\n", "# Sweep detection box away from a fixed track box; plot IoU vs GIoU\n", "trk = _poly(0,0,1.9,4.5,0.0)\n", "dx = np.linspace(0, 10, 40); ious=[]; gious=[]\n", "for d in dx:\n", " det=_poly(d,0,1.9,4.5,0.0); i,g=_polys_iou_giou(trk,det); ious.append(i); gious.append(g)\n", "fig, axes = plt.subplots(1,2, figsize=(13,5))\n", "axes[0].plot(dx, ious, 'C3.-', label='IoU'); axes[0].plot(dx, gious, 'C0.-', label='GIoU')\n", "axes[0].axhline(0, color='k', lw=0.5); axes[0].set_xlabel('center separation (m)')\n", "axes[0].set_ylabel('affinity'); axes[0].legend(); axes[0].grid(alpha=0.3)\n", "axes[0].set_title('IoU flatlines at 0 once boxes separate; GIoU keeps a usable gradient')\n", "fig2, ax = new_bev_ax('track (blue) vs detection at 3 m (red)', lim=(-4,9,-4,4)); \n", "draw_box(axes[1], 0,0,1.9,4.5,0.0, color='C0', label='trk')\n", "draw_box(axes[1], 3,0,1.9,4.5,0.0, color='C3', label='det')\n", "axes[1].set_aspect('equal'); axes[1].grid(alpha=0.3); axes[1].set_xlim(-4,9); axes[1].set_ylim(-5,5)\n", "axes[1].set_title('disjoint boxes: IoU=0 but GIoU<0 still ranks them'); plt.close(fig2)\n", "plt.tight_layout(); plt.savefig('nb03_iou_vs_giou.png', dpi=80); plt.show()\n" ] }, { "cell_type": "markdown", "id": "39d030c1", "metadata": {}, "source": [ "## 4. The Hungarian algorithm - optimal one-to-one matching\n", "With an $M\\times N$ **cost** matrix $\\mathrm{Cost}[i,j]$ (for GIoU we use $\\text{cost} = -\\text{GIoU}$, for L2 we use the distance), we want the assignment that **minimizes total cost** subject to each track matching at most one detection and vice-versa:\n", "$$ \\min_{X\\in\\{0,1\\}^{M\\times N}} \\sum_{i,j} \\mathrm{Cost}[i,j]\\,X_{ij} \\quad \\text{s.t.}\\ \\sum_j X_{ij}\\le 1,\\ \\sum_i X_{ij}\\le 1. $$\n", "This is the **linear assignment problem**, solved exactly in $O(n^3)$ by the **Hungarian (Kuhn-Munkres) algorithm** (`scipy.optimize.linear_sum_assignment`). A **gate** first sets impossible pairs to $+\\infty$ (e.g. GIoU below a threshold) so they are never matched. SimpleTrack also studies a **greedy** alternative (repeatedly take the globally best remaining pair); Hungarian is optimal, greedy is faster and often nearly as good." ] }, { "cell_type": "code", "execution_count": 4, "id": "c55c7c30", "metadata": { "execution": { "iopub.execute_input": "2026-08-02T03:39:29.108246Z", "iopub.status.busy": "2026-08-02T03:39:29.107783Z", "iopub.status.idle": "2026-08-02T03:39:29.394098Z", "shell.execute_reply": "2026-08-02T03:39:29.393463Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "cost matrix (-GIoU):\n", " [[-0.695 0.525 0.693]\n", " [ 0.494 -0.701 0.681]\n", " [ 0.523 0.712 0.81 ]]\n", "\n", "matches (trk->det): [(0, 0), (1, 1)]\n", "unmatched tracks: [2] unmatched dets: [2]\n" ] } ], "source": [ "def giou_cost_matrix(tracks, dets):\n", " \"\"\"tracks,dets: arrays of (cx,cy,w,l,yaw). Returns cost = -GIoU (MxN).\"\"\"\n", " M,N=len(tracks),len(dets); C=np.zeros((M,N))\n", " for i,t in enumerate(tracks):\n", " for j,d in enumerate(dets):\n", " _,g=_polys_iou_giou(_poly(*t), _poly(*d)); C[i,j]=-g\n", " return C\n", "\n", "def associate(cost, gate):\n", " \"\"\"Hungarian match with a gate; returns matches, unmatched_tracks, unmatched_dets.\"\"\"\n", " try:\n", " from scipy.optimize import linear_sum_assignment\n", " big=1e6; C=cost.copy(); C[C>gate]=big\n", " ri,ci=linear_sum_assignment(C)\n", " matches=[(i,j) for i,j in zip(ri,ci) if cost[i,j]<=gate]\n", " except Exception:\n", " # greedy fallback\n", " matches=[]; used_r=set(); used_c=set()\n", " order=np.dstack(np.unravel_index(np.argsort(cost,axis=None), cost.shape))[0]\n", " for i,j in order:\n", " if i in used_r or j in used_c or cost[i,j]>gate: continue\n", " matches.append((int(i),int(j))); used_r.add(i); used_c.add(j)\n", " um_t=[i for i in range(cost.shape[0]) if i not in {m[0] for m in matches}]\n", " um_d=[j for j in range(cost.shape[1]) if j not in {m[1] for m in matches}]\n", " return matches, um_t, um_d\n", "\n", "# Example: 3 predicted tracks, 3 detections (one is clutter, one track is missed)\n", "tracks=[(0,0,1.9,4.5,0.0),(10,2,2.0,4.8,np.pi),(-8,-3,1.8,4.2,0.2)]\n", "dets =[(0.6,0.1,1.9,4.5,0.02),(9.4,2.1,2.0,4.8,np.pi-0.05),(3,8,1.0,1.0,0.0)] # det2 = clutter\n", "C=giou_cost_matrix(tracks,dets)\n", "print('cost matrix (-GIoU):\\n', C)\n", "m,umt,umd=associate(C, gate=0.5) # gate: require GIoU >= -0.5\n", "print('\\nmatches (trk->det):', m); print('unmatched tracks:', umt, ' unmatched dets:', umd)\n", "\n", "fig, ax = new_bev_ax('Association result: green=matched, orange=missed track, red=clutter det', lim=(-12,14,-6,11), figsize=(10,7))\n", "for i,t in enumerate(tracks): draw_box(ax,*t,color='C0',label=f'T{i}')\n", "for j,d in enumerate(dets): draw_box(ax,*d,color='0.5',ls='--',label=f'D{j}')\n", "for i,j in m:\n", " ax.plot([tracks[i][0],dets[j][0]],[tracks[i][1],dets[j][1]],'g-',lw=2)\n", "for i in umt: draw_box(ax,*tracks[i],color='C1',lw=3)\n", "for j in umd: draw_box(ax,*dets[j],color='C3',lw=3)\n", "plt.tight_layout(); plt.savefig('nb03_association.png', dpi=80); plt.show()\n" ] }, { "cell_type": "markdown", "id": "99b20337", "metadata": {}, "source": [ "## 5. Mahalanobis gating (the covariance-aware alternative)\n", "Instead of a Euclidean gate, one can gate/score with the KF's own uncertainty using the innovation covariance $S$ from NB02 eq. (4):\n", "$$ D_M^2(t,d) = (\\mathbf{z}_d - H\\hat{\\mathbf{x}}_t)^\\top S^{-1} (\\mathbf{z}_d - H\\hat{\\mathbf{x}}_t) . $$\n", "This automatically widens the gate for uncertain (recently-missed) tracks and tightens it for confident ones — the nuScenes CenterPoint tracker uses exactly this. SimpleTrack found well-tuned GIoU competitive with Mahalanobis while being simpler and detector-agnostic.\n", "\n", "---\n", "**Next:** [`04_two_stage_association_and_lifecycle.ipynb`](04_two_stage_association_and_lifecycle.ipynb) - SimpleTrack's key contribution: a **two-stage** matching that rescues low-score detections, plus the birth/death **life-cycle** that assigns and preserves track ids (and re-identifies after gaps)." ] } ], "metadata": { "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.10" } }, "nbformat": 4, "nbformat_minor": 5 }