Checklist OAI 2024 Stage I · Task 5
SOTA-AI Editorial
Object Tracking
Determine the final permutation of cups in rendered "three cups" shell-game videos, first from bounding boxes, then from noisy boxes, and finally from raw frames.
Hints
Hint 1
Start with the supplied bounding boxes in subtasks 1 and 2; the box list order does not preserve object identity.
Hint 2
Assign stable IDs from the initial left-to-right order and predict each track using recent motion.
Hint 3
Across short occlusions, enumerate the few possible assignments and use a robust median velocity.
Hint 4
For subtask 3, segment the red cups from raw frames; large merged components indicate ambiguous occlusion.
The solution in one line
Track the three cups with motion-guided box assignment, then use red-component detections for the raw-video subtask; sample accuracy is 2/2, 2/2, and 1/2, with released validation unavailable.
The editorial
Object Tracking — Poland 2024 Stage I
The official selection lists one task with three progressively harder subtasks. This write-up groups the three local subtask analyses and keeps the sample-only score evidence separate from the missing released validation results.
Subtask 1 — Three Cups
Task and metric
- Domain: computer vision, object tracking from detections.
- Metric: exact permutation accuracy; this subtask is worth up to 0.5 points.
- Abridged statement: given bounding boxes for three cups in each frame of a shuffle animation, return the initial cup IDs in final left-to-right order. The task explicitly forbids using the images in this subtask; only box coordinates may be used.
EDA
The official helper loads frames in JSON insertion order. Each example has 50 frames and exactly three boxes per frame. Box-list order changes between frames, so list indices are not object identities. Box centers are sufficient for tracking; image appearance is outside the permitted input.
Experiments and result
I tested the official example_data videos (two labeled videos, not the hidden validation set). A nearest-assignment tracker with constant-velocity prediction returned both expected final permutations correctly: 2/2 example videos. Using the median of recent observed per-frame velocities also returned 2/2. The returned permutation is sorted by each track's final x-coordinate, which matches the notebook's stated convention.
The official validation script expects valid_data/level_1/..., but the available repository clone contains only two examples per level. Therefore a full released-validation accuracy is unmeasured; 2/2 is sample performance, not a validation score.
Method and runtime
Initialize IDs by sorting the first complete frame by x. For each later frame, enumerate the six possible box-to-track assignments and select the assignment minimizing squared distance to recent constant-velocity predictions. Sort the final track centers by x to form the answer. This is deterministic and needs no training. Measured inference on the two loaded examples took 0.050 seconds total on the local CPU (0.038 and 0.012 seconds per clip); JSON loading is excluded.
Alternatives considered
Using image pixels is disallowed here. A fixed box-list index is invalid because detections are reordered. Appearance embeddings and learned detectors add cost without helping this coordinate-only toy task.
Subtask 2 — Occlusion and Blur
Task and metric
- Domain: computer vision, robust object tracking from noisy detections.
- Metric: exact permutation accuracy; this subtask awards up to 0.5 points and expects strong performance.
- Abridged statement: infer the final left-to-right order of the three cups from box coordinates when boxes can be imprecise, objects occlude each other, and detections disappear in some frames. Images remain for visualization only; the algorithm must consume coordinates.
EDA
The two official example videos contain 150 frames each. One has 84/150 frames with three detections and the other 67/150; the rest have one or two boxes, with some fully missing frames. Box positions vary in both x and y, and the list order is arbitrary. Occlusion gaps make one-step nearest-neighbor assignment ambiguous.
Experiments and result
On the two labeled examples, nearest assignment with only the latest displacement as velocity got 0/2. Replacing that slope with the coordinate-wise median of recent observed velocities, while enumerating assignments to any subset of the three tracks, got 2/2. This damps box jitter while preserving sustained motion through short gaps.
The official validator uses valid_data/level_2/...; that released validation directory is not present in the available clone. Full validation accuracy is unmeasured; the reported 2/2 is only on labeled examples.
Method and runtime
Initialize IDs from the first complete frame. At each frame, compute a prediction for each track from the median of recent observed displacement-per-frame vectors. Enumerate injective mappings from the available boxes to tracks (there are at most six) and minimize the squared center-to-prediction distance. Missing tracks remain unmodified until observed again. The function uses coordinates only and took 0.052 seconds total on the local CPU for the two 150-frame examples (0.027 and 0.024 seconds per clip); JSON loading is excluded.
Alternatives considered
Images are explicitly excluded for this level. Raw last-step velocity is too sensitive to jitter and missing detections. A full learned tracker is unnecessary with only three trajectories; a larger motion model can be considered if full validation later reveals harder gaps.
Subtask 3 — Build from Scratch
Task and metric
- Domain: computer vision, color segmentation and multi-object tracking.
- Metric: exact permutation accuracy; this subtask awards up to 0.5 points.
- Abridged statement: from raw frames, detect and track the three cups without supplied boxes, then return their final left-to-right order. Inference must complete within five minutes on CPU.
EDA
The two local examples use 640×480 RGB frames (150 and 120 frames). The cups are saturated red against a pale blue/white checkerboard, making a simple red-pixel mask a useful detector. Connected components produce three detections in many frames, but occlusion merges multiple cups into a single component. There are no training annotations beyond the one example track file, and no official valid_data directory is present.
Experiments and result
- Red thresholding plus connected-component centroids and one-step velocity tracking did not recover the full permutation.
- Using a median recent-velocity estimate improved coordinate-level tracking but still confused identities at long merged-component intervals.
- Filtering oversized merged components using a per-video component-size reference and then tracking with median velocity gets 1/2 labeled examples (the second example is correct; the first remains ambiguous). This is sample-only performance; official validation accuracy is unmeasured because the validation videos and targets are absent.
- A 100-state beam search over recent identity assignments produced the same two predictions and still scored 1/2; it took about 16 seconds across the two samples, compared with 5.2 seconds for the simpler framewise method. It did not justify the extra cost.
Component extraction and tracking took 3.07 seconds total for the two examples on the local CPU (1.84 seconds for 150 frames and 1.23 seconds for 120 frames), excluding image loading. The earlier end-to-end sample harness, including image loading, took 5.24 seconds.
Method and alternatives
Threshold red pixels, remove tiny regions, and use connected-component centroids and extents as detections. Estimate typical component size from frames with three separate components; discard a component that is clearly a union during partial-visibility frames. Track the remaining centers with the robust assignment method from Task 2. The approach is transparent and has no pretrained weights, but long intervals where cups merge remain an information bottleneck. Beam search did not resolve the difficult sample; watershed splitting or a temporal image model are plausible next steps, though neither can be measured without more labeled clips.
Code
Solution code
"""Coordinate-only tracking and color-based tracking for the 2024 Polish AI Olympiad."""
from __future__ import annotations
from itertools import permutations
import re
import numpy as np
def _center_detections(coordinates):
"""Return a chronological list of (center, box_size) detections per frame."""
if not coordinates:
return []
def frame_number(item):
match = re.search(r"(\d+)", str(item[0]))
return int(match.group(1)) if match else 0
frames = []
for _, boxes in sorted(coordinates.items(), key=frame_number):
detections = []
for box in boxes or []:
if box is None or len(box) < 4:
continue
x1, y1, x2, y2 = map(float, box[:4])
if x2 <= x1 or y2 <= y1:
continue
detections.append((np.array([(x1 + x2) / 2, (y1 + y2) / 2]),
np.array([x2 - x1, y2 - y1])))
frames.append(detections)
return frames
def _robust_velocity(history, window=4):
"""Coordinate-wise median of recent observed velocity vectors."""
recent = history[-(window + 1):]
velocities = []
for (t0, p0, _), (t1, p1, _) in zip(recent[:-1], recent[1:]):
if t1 > t0:
velocities.append((p1 - p0) / (t1 - t0))
if not velocities:
return np.zeros(2, dtype=float)
velocity = np.median(np.stack(velocities), axis=0)
# Suppress detector jitter when a cup is stationary.
if np.linalg.norm(velocity) < 2.0:
return np.zeros(2, dtype=float)
speed = np.linalg.norm(velocity)
if speed > 40.0:
velocity = velocity * (40.0 / speed)
return velocity
def _track_centers(frames):
"""Track up to three centers using a global assignment at each frame."""
start = next((i for i, detections in enumerate(frames) if len(detections) >= 3), None)
if start is None:
return [0, 1, 2]
initial = sorted(frames[start], key=lambda detection: detection[0][0])[:3]
tracks = [[(start, center.copy(), size.copy())] for center, size in initial]
for t in range(start + 1, len(frames)):
detections = frames[t]
# The task contains at most three objects. Ignore extra components/boxes
# by retaining the three largest, if a detector ever returns more.
if len(detections) > 3:
detections = sorted(detections,
key=lambda detection: detection[1][0] * detection[1][1],
reverse=True)[:3]
m = len(detections)
if m == 0:
continue
predictions = []
for history in tracks:
last_t, last_center, _ = history[-1]
velocity = _robust_velocity(history)
gap = min(t - last_t, 8)
predictions.append(last_center + velocity * gap)
best_mapping = None
best_cost = float("inf")
# The tuple maps detections (in input order) to distinct track IDs.
for mapping in permutations(range(3), m):
cost = sum(float(np.sum((detections[j][0] - predictions[track_id]) ** 2))
for j, track_id in enumerate(mapping))
if cost < best_cost:
best_cost = cost
best_mapping = mapping
for j, track_id in enumerate(best_mapping):
center, size = detections[j]
tracks[track_id].append((t, center.copy(), size.copy()))
final_x = [history[-1][1][0] for history in tracks]
# The problem's answer lists the original cup IDs occupying final slots
# from left to right.
return [int(i) for i in np.argsort(final_x)]
def your_algorithm_task_1(coordinates):
"""Return final cup order from complete level-1 bounding-box detections."""
return _track_centers(_center_detections(coordinates))
def your_algorithm_task_2(coordinates):
"""Return final cup order, bridging level-2 missing detections robustly."""
return _track_centers(_center_detections(coordinates))
def _image_components(images):
"""Extract red-cup connected components and filter merged regions."""
from scipy.ndimage import label
raw_frames = []
for image in images:
array = np.asarray(image.convert("RGB") if hasattr(image, "convert") else image)
if array.ndim != 3 or array.shape[-1] < 3:
raw_frames.append([])
continue
red, green, blue = array[..., 0], array[..., 1], array[..., 2]
mask = ((red > 90) & (red > 1.35 * green) & (red > 1.35 * blue)
& (green < 100) & (blue < 100))
labels, count = label(mask)
sizes = np.bincount(labels.ravel())
detections = []
for label_id in range(1, count + 1):
area = int(sizes[label_id])
if area < 1000:
continue
ys, xs = np.where(labels == label_id)
center = np.array([xs.mean(), ys.mean()], dtype=float)
box_size = np.array([xs.max() - xs.min() + 1,
ys.max() - ys.min() + 1], dtype=float)
detections.append((center, box_size, area))
raw_frames.append(detections)
complete_areas = [d[2] for frame in raw_frames if len(frame) == 3 for d in frame]
complete_y = [d[0][1] for frame in raw_frames if len(frame) == 3 for d in frame]
if len(complete_areas) >= 3:
y_mean = float(np.mean(complete_y))
y_scale = float(np.std(complete_y)) or 1.0
coefficients = np.polyfit((np.asarray(complete_y) - y_mean) / y_scale,
np.log(np.asarray(complete_areas)), 2)
def expected_area(y):
z = (y - y_mean) / y_scale
return float(np.exp(np.polyval(coefficients, z)))
else:
reference = float(np.median(complete_areas)) if complete_areas else 0.0
def expected_area(_y):
return reference
frames = []
for frame in raw_frames:
detections = []
for center, box_size, area in frame:
if len(frame) < 3:
expected = expected_area(center[1])
# An oversized connected region is likely two or more cups
# joined by occlusion; leave it out rather than relabeling it.
if expected > 0 and area / expected > 1.3:
continue
detections.append((center, box_size))
frames.append(detections)
return frames
def your_algorithm_task_3(images):
"""Detect red cup components, track their centers, and return final order."""
return _track_centers(_image_components(images))Editorials are written by members of the SOTA community, not by the olympiad. The official statement and scoring win wherever an editorial differs.