TubeletGraph

TubeletGraph is a zero-shot framework for tracking and understanding object transformations in video. Its goal is to recover objects that temporarily go missing and attach semantic meaning to each state transition.

If we can detect when false negatives occur, we can try to recover the missed object while also understanding the transformation that caused the tracking failure in the first place.

The key representation is a “soup of tubelets,” which reduces the search space. Every entity is tracked from the first frame, and new tracks are started in later frames wherever pixels are not already covered by an existing track.

Finding a missing object becomes the problem of finding its missing tubelet. The appearance of new tubelets also becomes a signal that a state transformation may have occurred. The method then uses multimodal vision-language and language models, including CLIP and FC-CLIP, to help reason about those changes.

pred_masks = predictions["instances"].pred_masks
pred_scores = predictions["instances"].scores

selected_indexes = pred_scores >= confidence_threshold
selected_scores = pred_scores[selected_indexes]
selected_masks = pred_masks[selected_indexes]

mask_id = np.zeros((m_H, m_W), dtype=np.uint8)

selected_scores, ranks = torch.sort(selected_scores)
ranks = ranks + 1
for index in ranks:
    mask_id[(selected_masks[index - 1] == 1).cpu().numpy()] = int(index)

out[len(out)] = {
    ii: bmask_to_rle(mask_id == mid)
    for ii, mid in enumerate(np.unique(mask_id)[1:])
}

Start with a video and a binary mask in the first frame as the initial object prompt. At any time, an object can be represented by a collection of tracks because a state change may split one track into several new ones. For example, one object might break into two pieces.

Each track is a temporally linked sequence of object segmentation masks. Across space and time, that sequence forms the tube-like structure behind the name TubeletGraph.

def add_mask(sam2, obj_id, mask, all_tracks, tracked_objs, frame_idx):
    sam2.predictor.add_new_mask(
        inference_state=sam2.inference_state,
        frame_idx=frame_idx,
        obj_id=obj_id,
        mask=mask,
    )
    all_tracks[frame_idx][obj_id] = bmask_to_rle(mask)
    tracked_objs[obj_id] = {
        "mask": mask,
        "init_frame_idx": frame_idx,
    }

for out_frame_idx, out_obj_ids, out_mask_logits in \
        sam2.predictor.propagate_in_video(sam2.inference_state):

    for i, obj_idx in enumerate(out_obj_ids):
        all_tracks[out_frame_idx][obj_idx] = bmask_to_rle(
            (out_mask_logits[i, 0] > 0.0).cpu().numpy()
        )

At a transition time, the graph collects the tracks immediately before and after the change. A language model then describes the transformation that connects those two sets of tracks.

obj_info[obj_idx] = {
    "desc": parsed_rsp[1],
    "action": parsed_rsp[2],
    "prior_desc": parsed_rsp[0],
    "analysis_frame_idx": obj_start_frame,
    "object_start_frame_idx": int(first_obj_frame),
}

The video is first partitioned into partial tracks using SAM 2. A partition stays continuous while the object remains visually recognizable and ends when an appearance change occurs.

CropFormer creates a spatial partition of the initial frame, and each entity is tracked forward. When CropFormer runs again later, a new tubelet is spawned for a region that is not sufficiently covered by an existing tubelet. Spatial and semantic proximity are then used to connect likely tracks across the change, after which a language model names the transformation.

pred_cover_rle = MaskUtils.merge(all_pred_masks, intersect=0)

coverages = np.array([
    coverage(
        den_mask=entity_mask,
        mask2intersect=pred_cover_rle,
    )
    for entity_mask in entity_masks_rle.values()
])

pix_perc = np.array([
    MaskUtils.area(entity_mask)
    for entity_mask in entity_masks_rle.values()
]) / img_h / img_w

entity_to_add = np.where(
    (coverages < fill_coverage_thrd)
    & (pix_perc > pix_perc_thrd)
)[0]

1. Every region in the video is associated with a partition or tubelet.
2. The search problem is reduced to identifying which partition contains the missing object.
3. Candidate tubelets can be narrowed to the tracks that appeared after the state change.

Here is how I think about the selection step. Let C be a candidate tubelet that first appears at frame s, and let P be the original prompted track. The new track has to look right in two ways. It should appear near the original object and still represent the same thing.

tracked_objs[obj_id]["mm_iou"] = float(np.max(
    MaskUtils.iou(
        [multi_masks[start_frame][1],
         multi_masks[start_frame][2]],
        [obj_mask_rle],
        [False],
    )
))

tracked_objs[obj_id]["mm_cover"] = float(np.max([
    coverage(
        obj_mask_rle,
        mask2intersect=multi_masks[start_frame][i],
    )
    for i in [1, 2]
]))

later_clip_feats = F.normalize(
    torch.cat(later_clip_feat_list), dim=-1
)

cos_sim_all = later_clip_feats @ query_clip_feat[:, query_valid]
cos_sim_prior = cos_sim_all[:, :num_valid_prior]

tracked_objs[obj_idx]["clip_sim_max"] = \
    torch.max(cos_sim_prior).item()

keep = set(self.tracked_objs.keys())

for metric_name, threshold in self.thrds.items():
    keep &= {
        obj_idx
        for obj_idx, metric in self.metrics[metric_name].items()
        if metric > threshold
    }

return [self.prompt_obj] + list(keep)

mask_subset = {
    obj_idx: self.all_tracks[str(frame_idx)][str(obj_idx)]
    for obj_idx in best_subset_indices
    if str(obj_idx) in self.all_tracks[str(frame_idx)]
}

output["prediction"][frame_idx] = {
    0: MaskUtils.merge(list(mask_subset.values()), intersect=0)
}