Matching instances when nothing tells you which is which

Semantic segmentation is easy to score: every point has exactly one label, and “did the prediction match the label” is a question with a yes-or-no answer per point. Instance segmentation is not, because an instance id carries no meaning on its own. My algorithm found 41 blobs in a room; the ground truth has 37. Nothing in either array says blob #12 is chair #4, that correspondence has to be discovered, and discovering it is an assignment problem, not a lookup. This post is about the matcher that decides that correspondence, the conflict rule that makes it deterministic, and the two extra things that fall out of getting it right: an honest precision–recall curve, and (because I went back to segtester/cutil/cutil.cpp for this one) a Rust port of the C++ I wrote to make the matching matrix fast enough to run at all.

The I×J matrix everything else depends on

Before any matching can happen, every predicted instance has to be scored against every ground-truth instance. That is an I×J matrix of Jaccard/IoU values, and Seg.get_instance_ious routes to whichever of three implementations the point count deserves:

# segtester/types/seg.py:32-40
def get_instance_ious(self, ground_truth):
    if torch.cuda.is_available() and len(self.classes) > 100000:
        try:
            return self.calc_iou_mtx_gpu(self.instance_masks, ground_truth.instance_masks)
        except Exception:
            print("I could not run on gpu reverting to cpu")
            pass

    return cutil.calc_iou_mtx(self.instance_masks, ground_truth.instance_masks)

calc_iou_mtx_gpu (segtester/types/seg.py:20-30) is a plain double Python loop over torch tensors on CUDA, readable, and only worth the transfer cost above 100,000 points. Below that, cutil.calc_iou_mtx is the interesting fork: the pure-numpy version broadcasts every prediction mask against every ground-truth mask in one shot, and falls back to a per-row loop the moment that broadcast is too big to allocate:

# segtester/cutil/cutil.py
def calc_iou_mtx(instance_masks_est, instance_masks_gt):
    masks_p = instance_masks_est[:, None]
    masks_gt = instance_masks_gt[None]
    try:
        intersection = np.count_nonzero(np.bitwise_and(masks_gt, masks_p), axis=2)
        union = np.count_nonzero(np.bitwise_or(masks_gt, masks_p), axis=2)
    except MemoryError:
        intersection = np.zeros((masks_p.shape[0], masks_gt.shape[1]), dtype=np.uint32)
        union = np.zeros((masks_p.shape[0], masks_gt.shape[1]), dtype=np.uint32)
        for i in range(len(intersection)):
            intersection[i] = np.count_nonzero(np.bitwise_and(masks_gt[0], masks_p[i]), axis=1)
            union[i] = np.count_nonzero(np.bitwise_or(masks_gt[0], masks_p[i]), axis=1)
    return intersection/union

masks_p[:, None] and masks_gt[None] broadcast an (I, N) and a (J, N) boolean array into an (I, J, N) array before numpy ever counts anything, for a scene with a few hundred thousand points and a few dozen instances a side, that intermediate array alone can be gigabytes. The except MemoryError isn’t defensive programming for a hypothetical; it is what actually happened on this scene, on this machine, and the fix is to give up the broadcast and pay for it one row at a time instead.

But the module is called cutil (C-util) for a reason. Next to that Python file sits a pybind11 extension that does the same job as a flat triple loop, one bool at a time:

// segtester/cutil/cutil.cpp:7-39
py::array_t<double> calc_iou_mtx(py::array_t<bool> input1, py::array_t<bool> input2) {
    auto r1 = input1.unchecked<2>(), r2 = input2.unchecked<2>();
    ...
    auto result = py::array_t<double>(std::vector<ptrdiff_t>{r1.shape(0), r2.shape(0)});
    auto res_mut = result.mutable_unchecked<2>();

    for (ssize_t i = 0; i < r1.shape(0); i++)
        for (ssize_t j = 0; j < r2.shape(0); j++) {
            long int_count = 0;
            long union_count = 0;
            for (ssize_t k = 0; k < r1.shape(1); k++) {
                int_count += r1(i,k) && r2(j,k);
                union_count += r1(i,k) || r2(j,k);
            }
        if (union_count == 0) {
            res_mut(i,j) = 0;
        } else {
            res_mut(i,j) = int_count/(double)union_count;
        }
    }
    return result;
}

No broadcast, no intermediate array: three nested loops and a running count, exactly the kind of thing you reach for in C++ when numpy’s vectorised path either runs out of memory or simply loses to a compiler that can keep everything in registers. It is not clever. It is the 2019 answer to “the Python was too slow”, and it is the piece of this repository the widget below gets to have a direct conversation with.

Turning the matrix into an assignment

The matrix says how good every possible pairing is. Deciding which pairings actually count is Seg.get_instance_map, and it is worth reading the whole thing once, because every line is a decision:

# segtester/types/seg.py:42-83
def get_instance_map(self, ground_truth, min_match_iou=0, allow_duplicates=False,
                     class_map=None, match_classes=False):

    if match_classes and class_map is None:
        class_map = np.arange(self.instance_classes.max()+1)

    iou = self.get_instance_ious(ground_truth)
    instance_map = np.repeat(-1, iou.shape[0])
    unassigned_indices = list(range(iou.shape[0]))
    assigned_labels = {}
    while len(unassigned_indices) > 0:
        i = unassigned_indices.pop()
        max_ind = np.argmax(iou[i])

        iou_val = iou[i, max_ind]
        if iou_val <= min_match_iou:
            continue

        if class_map is not None and ground_truth.instance_classes[max_ind] != class_map[self.instance_classes[i]]:
            unassigned_indices.append(i)
            iou[i, max_ind] = -1
            continue

        if allow_duplicates or max_ind not in assigned_labels:
            instance_map[i] = max_ind
            assigned_labels[max_ind] = i
            continue
        prev_i = assigned_labels[max_ind]
        prev_iou_val = iou[prev_i, max_ind]
        if prev_iou_val >= iou_val:
            unassigned_indices.append(i)
            iou[i, max_ind] = -1
        else:
            unassigned_indices.append(prev_i)
            iou[prev_i, max_ind] = -1
            instance_map[i] = max_ind
            instance_map[prev_i] = -1
            assigned_labels[max_ind] = i
    unassigned_instances = instance_map == -1
    instance_map[unassigned_instances] = \
        np.arange(iou.shape[1], iou.shape[1]+np.count_nonzero(unassigned_instances))
    return instance_map

Read it as a queue, not a loop: unassigned_indices is a stack of predictions still looking for a home. Pop one, take its argmax (its best available ground-truth column) and reject it outright if that best match doesn’t clear min_match_iou. If the column is free, it’s a match, done. If the column is already claimed, the two contenders compare their IoU at that one column and the higher bid keeps it; the loser goes back on the stack with that specific cell in iou set to -1, so its next argmax skips straight past the column it just lost. A prediction can only ever move forward through its own row, once a column is blocked for it, it’s blocked for good, which is what guarantees the whole thing terminates in at most I×J steps rather than looping forever.

What it does not do is look ahead. A prediction that wins its first-choice column stops there and never checks whether its second-best column was actually the better use of it globally. That is a genuine limitation, not a nitpick, and it’s exactly what the widget’s “greedy vs optimal” preset is built to show you happening.

The nice detail: nobody gets dropped

The last two lines are doing something easy to miss. instance_map still has -1 in it for every prediction that never found a home (rejected on IoU, rejected on class, or simply never chosen), and instead of leaving those as -1 (which would make them invisible to anything that counts predictions), they’re renumbered to ids beyond the ground-truth range: np.arange(J, J+count). A prediction that matches nothing doesn’t disappear from the output; it becomes its own, fictional, ground-truth-less instance. Every metric that counts “how many predicted instances are there” downstream counts it. It cannot ever be a true positive, there is no ground truth sharing its id, so it can only ever inflate the false-positive count. The bookkeeping that makes precision punish over-prediction isn’t a separate check bolted onto the matcher; it’s this one renumbering line.

Instance score, semantic score, and the gap between them

match_classes is the whole difference between two of the three column blocks in the project’s result tables. Run the matcher once with it on, once with it off, over the same IoU matrix:

Algorithm	Instance Acc. [%]	Instance FIoU	Instance MIoU	Semantic Acc. [%]	Semantic FIoU	Semantic MIoU
3DMV	48.034	0.392	0.044	40.815	0.340	0.032
ME (2cm)	54.407	0.448	0.214	50.831	0.419	0.175
ME (5cm)	38.349	0.276	0.085	31.551	0.219	0.044
SF.	26.036	0.208	0.010	20.942	0.160	0.007

assets/SCANNET/seg3d_all_c.tex, Instance and Semantic column blocks.

With match_classes=False (the “semantic” score), a predicted blob and a ground-truth blob can match purely on overlap; a chair-shaped prediction labelled “sofa” still counts as a hit on the chair. With it True (“instance”), the same pair is rejected unless the predicted class is also right. Every row above drops going from instance to semantic, because dropping the class check can only ever make matching easier. The size of that drop is not noise: it is exactly the additional cost of getting the class right on top of getting the extent right, isolated by toggling one boolean and re-running the identical matcher.

Where the ground-truth instances actually come from

None of 3DMV, MinkowskiEngine or SemanticFusion output instances: they are semantic segmentation networks; every point gets a class, never an instance id. So before any of the matching above can happen, Seg3D has to manufacture instances out of a class-only point cloud, for predictions and (where ScanNet’s own instance annotations aren’t used) ground truth alike:

# segtester/types/seg3d.py:60-95 (dist_thresh=0.12 default is commented out just above this line; 0.30 is what actually ran)
def get_instance_masks_from_classes(self, dist_thresh=0.30, classes_to_skip=[0], linkage="single"):
    pcd = o3d.geometry.PointCloud()
    pcd.points = o3d.utility.Vector3dVector(self.points)
    downpcd = pcd.voxel_down_sample(voxel_size=0.10)
    down_points = np.array(downpcd.points)
    class_inds = self.get_search_tree().query(down_points, k=1, return_distance=False)[:, 0]
    classes = self.classes[class_inds]

    seg_labels = np.zeros_like(self.classes)
    unique_classes = np.unique(classes)
    current_max_label = 0
    instance_classes = []
    for c in unique_classes:
        if c in classes_to_skip:
            continue
        mask = classes == c
        masked_pts = down_points[mask]
        if len(masked_pts) >= 2:
            clustering = AgglomerativeClustering(n_clusters=None,
                                                 distance_threshold=dist_thresh,
                                                 linkage=linkage).fit(masked_pts)
            labels = clustering.labels_ + (current_max_label + 1)
        else:
            labels = np.repeat(current_max_label + 1, len(masked_pts))
        next_max_label = labels.max()
        instance_classes += [c] * (next_max_label - current_max_label)
        current_max_label = next_max_label
        mask_reverse = self.classes == c
        reverse_mapped_inds = KDTree(masked_pts).query(self.points[mask_reverse], k=1, return_distance=False)[:, 0]
        seg_labels[mask_reverse] = labels[reverse_mapped_inds]
    instance_masks = np.unique(seg_labels)[1:, None] == seg_labels[None]

    return instance_masks, np.array(instance_classes)

Voxel-downsample the whole cloud to 10 cm (clustering the full-resolution point cloud would be far too slow); then, per class, single-linkage agglomerative clustering with a 30 cm distance threshold: any two downsampled points of the same class within 30 cm of a chain of same-class neighbours become one instance; then map every full-resolution point back to its nearest downsampled label with a second KDTree query. Two chairs pushed together closer than 30 cm become one instance. A single chair split by an occluding column into two point clusters more than 30 cm apart becomes two.

The IoU that made a metric well-defined: precision, recall, and the interpolated staircase

A single precision/recall number depends on a confidence threshold you haven’t chosen yet. precision_recall sweeps every threshold a real prediction’s own confidence could plausibly sit at, and at each one asks the same question: given only the predictions confident enough to survive, how many ground-truth instances got a true positive?

# segtester/metrics/seg.py:46-78
def precision_recall(est_labels, gt_labels, est_probs, test_probs=None, iou_threshs=None):
    if iou_threshs is None:
        iou_threshs = [0.5]
    iou_threshs = np.array(iou_threshs)[None]
    if test_probs is None:
        test_probs = list(sorted(np.append(-1e-6, est_probs)))
    all_labels = np.unique([est_labels, gt_labels])
    all_labels = all_labels[all_labels != 0]

    precision = np.empty((len(test_probs), iou_threshs.shape[1]), dtype=np.float)
    recall = np.empty((len(test_probs), iou_threshs.shape[1]), dtype=np.float)

    total_pos_gt = np.count_nonzero(np.unique(gt_labels))
    for prob_ind, prob_thresh in enumerate(test_probs):
        lt_mask = est_probs <= prob_thresh
        est_labels[lt_mask] = 0

        if np.count_nonzero(est_labels) == 0:
            precision[prob_ind:] = 1
            recall[prob_ind:] = 0
            break

        total_pos_est = np.count_nonzero(np.unique(est_labels))
        iou_val = np.nan_to_num(iou(est_labels, gt_labels, all_labels=all_labels))
        tps = np.count_nonzero(iou_val[:, None] >= iou_threshs, axis=0)
        fns = total_pos_gt - tps
        fps = total_pos_est - tps

        precision[prob_ind] = tps / (tps + fps)
        recall[prob_ind] = tps / (tps + fns)

    return precision, recall, test_probs, iou_threshs

The threshold list is just every prediction’s own confidence, sorted, with one sentinel below all of them (-1e-6, so the first row keeps every prediction). At each threshold, the points belonging to low-confidence predictions get zeroed out of est_labels, that’s get_instance_map’s output being reused as a per-point labelling, not re-matched, and iou() recomputes overlap per label id. A true positive is a label whose IoU still clears 0.5 after the zeroing; false positives and false negatives fall straight out of the id counts. And this is where the fresh-id trick from earlier pays for itself a second time: an unmatched prediction’s label never appears among the ground-truth ids, so its IoU is always 0, it can never become a true positive at any threshold, and it correctly inflates total_pos_est, a false positive at every confidence below its own, with no extra code to make that happen.

Once you have one precision value per threshold, plotting precision against recall directly gives a jagged, non-monotonic line: precision can wobble as the threshold sweeps. The fix used almost everywhere instance/object detection is reported (PASCAL VOC’s average precision, most since) is to interpolate: at every recall level, report the best precision achieved at that recall or higher.

# segtester/metrics/seg.py:113-124
def interpolated_precision(precision):
    """
    Assumes precision is already in reverce order
    :param precision:
    :return:
    """
    result = np.empty(precision.shape, dtype=precision.dtype)
    max_val = -1
    for i, val in enumerate(precision):
        max_val = max(max_val, val)
        result[i] = max_val
    return result

A fifteen-line running max, on an array already sorted by ascending confidence threshold, which is descending recall. Walking it forward and keeping the running maximum is exactly “the best precision seen at this recall or any higher recall”, the standard interpolated staircase, and it is monotone non-increasing by construction: a running maximum can never go down as you add more candidates to max over.

Verifying the 1.4% instance-accuracy number

That is real, and it is not a typo: SemanticFusion’s 2D-reprojected instance accuracy on NYUv2 is 1.433%. Compare it to the same algorithm’s 3D instance accuracy on ScanNet, 26.036% in the table above, an order of magnitude higher. This is the harness telling you, correctly, that reprojecting a 3D semantic map back through a 2D camera and re-clustering it into instances is a much harder path than staying in 3D, and it’s Post 28’s story, not this one: a surfel map, however good, is never dense enough to fill every camera ray it’s reprojected through, and instance clustering on the resulting sparse, speckled label image falls apart in a way point accuracy alone doesn’t fully capture (37.166% classification accuracy on the same run, in seg2d_all_c.tex, nowhere near as bad).

The performance story, and the Rust that answers it

Three implementations of one matrix, in one repository, is the tell that this matrix is a bottleneck: pure numpy with a MemoryError escape hatch, a pybind11 C++ triple loop, and a CUDA path gated behind a 100,000-point threshold. That’s the shape of a problem worth solving properly in the browser too, and it’s the reason this post gets a crate rather than plain JavaScript.

wasm/crates/instance-wasm/ ports the C++ triple loop, not the numpy broadcast: the same nested-loop structure as cutil.cpp:21-28, but with masks packed 64 pixels to a u64 word instead of one bool per point. iou::iou_of_words (wasm/crates/instance-wasm/src/iou.rs:28-42) is the entire kernel:

// wasm/crates/instance-wasm/src/iou.rs:28-42
pub fn iou_of_words(a: &[u64], b: &[u64]) -> f64 {
    let mut inter: u64 = 0;
    let mut union_: u64 = 0;
    let n = a.len().min(b.len());
    for k in 0..n {
        let (aw, bw) = (a[k], b[k]);
        inter += (aw & bw).count_ones() as u64;
        union_ += (aw | bw).count_ones() as u64;
    }
    if union_ == 0 { 0.0 } else { inter as f64 / union_ as f64 }
}

Where cutil.cpp does int_count += r1(i,k) && r2(j,k) sixty-four times to cross sixty-four points, this does it once: AND/OR two 64-bit words and count_ones() (a single hardware popcnt instruction) for the same sixty-four points in one loop iteration. Same triple loop, same asymptotic cost, roughly two orders of magnitude fewer instructions executed for the same matrix. It’s still exactly the “read every point, count matches” idea cutil.cpp had; it’s just reading 64 of them at a time instead of 1.

The rest of the crate is the same set of decisions the Python makes, ported deliberately rather than transliterated:

• matching::greedy_match_impl is get_instance_map line for line: the stack, the argmax-with-rejection, the higher-bid-wins conflict rule, the fresh ids for the unmatched. min_match_iou and match_classes are both exposed as widget sliders/toggles.
• matching::optimal_match_impl does not exist in the Python at all, I added it so the post has something to compare greedy against. It pads the I×J matrix to an (I+J)×(I+J) cost matrix (a genuine “stay unmatched” row for every prediction, a genuine “stay unmatched” column for every ground-truth instance, both at value zero) and hands it to a from-scratch O(n³) Hungarian solver (hungarian.rs), nothing in the repo needed optimal assignment, so nothing in the repo had one.
• pr::precision_recall_curve_impl / interpolated_precision_impl port metrics/seg.py:46-124, adapted from a per-point confidence sweep to a per-blob one: the widget’s blobs carry one confidence each, which is the special case of the Python algorithm where every point of an instance shares a confidence, thresholding then keeps or drops a whole blob rather than eroding it a few points at a time, but the counting rule (a match is a true positive only while its IoU still clears 0.5 and it’s still “on”) is unchanged.

Four cargo test -p instance-wasm cases hold the port to its sources, alongside eleven more covering the individual pieces (16 tests total): the IoU of two hand-built masks against a value computed by hand; greedy and optimal agreeing on an unambiguous case and disagreeing on a constructed one, a hand-picked IoU matrix built to have exactly the same shape of failure as the widget’s “greedy fails” preset (a prediction outbids a rival for its shared column and stops, instead of taking a better, uncontested second choice): greedy achieves 0.50 total matched IoU and leaves a prediction unmatched, optimal achieves 0.85 and matches both; an unmatched prediction coming out with an id >= J rather than vanishing; and the interpolated-precision staircase being monotone non-increasing along a curve with a deliberate dip in it. The widget’s own circles were tuned separately, against the exact circle-circle intersection formula, to reproduce the same failure at full mask resolution, see the preset’s own numbers in the section below.

pnpm build:wasm instance-wasm produces public/blog/wasm/instance-wasm.wasm at 24.5 kB with no dependencies, nothing to link against but Rust’s own allocator. Run against the widget’s default two-prediction, two-ground-truth scene at the full 640×480 mask resolution (4,800 u64 words per mask), the IoU matrix computes in a fraction of a millisecond; the readout under the matrix below shows the number for whatever scene you’ve actually built, live.

An instance matcher you draw yourself

Two panels of coloured circles: ground truth on the left, predictions on the right. Drag a blob to move it, its small square handle to resize it, select it and press Delete (or use the button) to remove it, or do all three with the keyboard once something’s selected. Every change re-rasterises that one blob onto the 640×480 grid and re-runs the whole pipeline: the I×J IoU matrix below shows every pairing, with the chosen assignment’s cell outlined in bold and any cell excluded by a class mismatch (when match_classes is on) greyed out. Precision, recall and F1 update from the same assignment. A per-blob confidence slider on the selected prediction drives the precision–recall curve at the bottom, with the interpolated staircase drawn over the raw points.

Four presets walk through the failure modes this post covers:

• Clean case: three well-separated instances, one good prediction each. Unambiguous; greedy and optimal always agree here.
• Split object (over-segmentation): two predicted blobs on one ground-truth instance, plus one clean pair alongside for contrast. The matcher keeps the better-overlapping one as a true positive and the other becomes a false positive with a fresh id, exactly as get_instance_map’s last two lines intend: 2 true positives, 1 false positive, 0 false negatives: 66.7% precision, 100% recall. Over-segmentation costs precision, not recall.
• Merged objects (under-segmentation): one predicted blob spanning two ground-truth instances, plus one clean pair alongside. Whichever it overlaps more wins; the other is a false negative that was never in contention: 2 true positives, 0 false positives, 1 false negative: 100% precision, 66.7% recall. The mirror image of the split case.
• Greedy fails: the constructed case: one prediction outbids another for its shared favourite column, wins, and stops, never trying its own decent second choice, which was the actually-better use of it. Under Greedy this scene is one true positive, one false positive, one false negative: 50% precision, 50% recall. Flip the assignment switch to Optimal and, with the same two ground-truth blobs and the same two predictions, it’s two true positives, zero false positives, zero false negatives: 100% and 100%. Nothing about the scene changed; only which pairing the matcher was willing to consider.

Export button included: Export scene + scores (JSON) writes out every blob’s position, class and confidence, the current assignment, the metrics, and the full precision–recall curve, the same numbers the readouts show, in case you want to check a preset’s arithmetic yourself rather than trust the canvas.

With JavaScript enabled, this becomes two panels of draggable, resizable, deletable blobs backed by the instance-wasm crate: a live I×J IoU heat-map, greedy vs. Hungarian-optimal assignment, precision/recall/F1, four presets, and a live precision–recall curve with the interpolated staircase.

What I’d tell past me

The matcher is not the hard part, once you see it as an assignment problem with a tie-break rule instead of a lookup. The hard part is everything that has to be true around it for a single accuracy number to mean what it claims: that unmatched predictions still count against you instead of quietly vanishing; that “instance” and “semantic” scoring are the same matcher with one boolean flipped, not two different pieces of code that could drift apart; that ground truth itself, when it has to be manufactured from a class map by clustering, is scoring the clustering rule as much as the network. None of that shows up in a single reported percentage. It only shows up if you go looking for the assignment problem hiding inside the metric, and, this time, for the C++ from 2019 that made it fast enough to run, doing the same job in your browser today.