Dense Stereo Matching with Max-Sum Belief Propagation on a Jetson TX2 (MASDA, Part 2)

This is the dense stereo matcher: a C++14 implementation of MASDA — max-sum loopy belief propagation for data association — applied to every pixel of an 848×480 infrared pair, on a Jetson TX2. Part 1 derives the message equations and measures the one-to-one constraint on sparse candidate matrices. This post is the algorithm at full frame rate. It covers four things:

• the representation it needs;
• the parameters that matter;
• the ones that turn out to do nothing;
• and a set of experiments that ended with a result I did not expect about the algorithm the series is named after.

Every term is defined in the series glossary, with links to the original papers. Terms link there on first use.

The matcher, in one paragraph. Each left pixel is a measurement; its candidate “objects” are the right pixels along the same rectified row within the disparity range. Four stages follow:

1. A Census descriptor plus a truncated absolute difference scores every (pixel, disparity) pair.
2. An edge-aware recursive filter aggregates those scores.
3. The two best-scoring disparities per pixel are kept, and everything else is discarded.
4. MASDA solves each row as an assignment problem, through its messages with clutter and misdetection.

It emits a disparity and a margin, the gap between the best and second-best candidate. That margin is the confidence a downstream gate consumes.

Where it stands, measured on the fifteen Middlebury v3 training scenes under the benchmark’s own scoring rules:

Ahead on the error rate over answered pixels, ten points behind on how many pixels it answers. Neither number settles it on its own, and the whole curve is the only fair way to read a matcher that declines to answer. Read that way, SGM is ahead.

1. The cost volume is never built

The textbook pipeline materialises a \(W \times H \times D\) cost volume, aggregates it, then reads it back to pick winners.

At \(D=64\) that volume is 43 MB per frame at 450×375, and 104 MB at 848×480, in float. Both halve once the scores are Q14 int16.

I built that first, then measured what the solver actually consumes.

1.1 The score, one pixel at a time

Before anything is aggregated there has to be a number to aggregate, and it comes from comparing two small patches. The Census transform describes a pixel by how its neighbours compare with it, and nothing else:

For a 7×7 window that is 48 neighbours, so 48 bits packed into a uint64. The centre pixel is not coded — it is the thing everything is compared against. What survives is the ordering of brightness in the window, not the brightness itself. So the descriptor does not care that the two cameras have different gain, or that one side of the scene is lit more strongly than the other.

Two descriptors are compared by Hamming distance — count the bits that disagree — which is one instruction:

Here it is on one pixel of Teddy, at its true disparity and 5 px away from it:

The left patch codes to 0xe1c3c71c3c7c. At the true disparity the right patch differs in 2 bits of 48; five pixels away it differs in 42, which is closer to inverted than to equal. That is the whole matching signal.

The figure is also a fair warning about what happens when a patch has no texture. Every neighbour then falls on one side of the centre, the code is all zeros, and there is no signal at all.

The distance becomes a score on a fixed scale, positive for agreement:

which is \(+0.92\) at the true disparity above and \(-0.75\) at the wrong one. In the code this is a 49-entry lookup table in Q14 — \(s \cdot 2^{14}\) — so the whole cost is integer arithmetic from here on.

One term is blended in beside it. The truncated absolute difference compares the raw grey values, saturating at \(T = 10\) levels:

Census carries the structure and is blind to a constant offset; the absolute difference notices an offset but is helpless on flat texture. What the parameters are worth measures what that blend is actually worth, and the answer is not what it was when the term was added.

1.2 What “aggregate” means here

Aggregation is the stage that does most of the work, so it is worth being precise about it.

The problem it solves. One pixel does not carry enough evidence to pick a disparity. A 7×7 Census descriptor compares 48 neighbours, so the score between two pixels is a Hamming distance between 0 and 48 — only 49 possible values. On a surface with little texture, many disparities produce the same score, and the best one is often not the correct one.

The effect is not marginal. On Teddy, taking each pixel’s best unaggregated score lands within 1 px of the truth for 62.0% of pixels; aggregating first takes that to 86.9%. Panel (b) below is one such pixel: the per-pixel score peaks at \(d = 10\) where the truth is 18.25, and after aggregation the peak sits at 18.

What the stage does. For each disparity \(d\), it replaces every score by a weighted average of the scores around it:

Read the indices carefully, because one detail decides the whole design. The sum runs over positions \((u,v)\). The disparity \(d\) is fixed. Aggregation averages a pixel with its spatial neighbours at the same disparity, and never across disparities. A disparity plane is the entire image scored at one fixed \(d\). The code needs a whole one of those in memory at once, and that single constraint is behind two of the negative results later in this post.

The weights are not a fixed window. Averaging across an object boundary is harmful: it pulls a foreground disparity onto the background behind it. So the weight between two neighbouring pixels shrinks when the image brightness changes between them. For a horizontal neighbour pair the coefficient is

where \(|\Delta I|\) is the brightness difference between the two pixels, in grey levels. The two parameters are separate: \(\sigma_s\) sets the reach on a flat surface, \(\sigma_r\) sets how large a brightness step has to be before support stops there.

How it is computed. Not with a window. The filter is a first-order recurrence — each pixel mixes its own score with the running value from the previous pixel:

This runs four times over the plane: left to right, right to left, top to bottom, bottom to top. Each pass costs one multiply and one add per pixel, and that cost does not depend on \(\sigma_s\). A wider support costs nothing. This is why the \(\sigma_s\) sweep later in this post changes accuracy at no cost in time, and why a value that was too large could sit unnoticed.

The reach is easy to read off the recurrence. On a flat surface \(a\) is constant, so a pixel \(k\) steps away contributes \(a^k = e^{-\sqrt{2}k/\sigma_s}\). The weight falls to \(1/e\) after \(k = \sigma_s/\sqrt{2}\) pixels. At the shipping \(\sigma_s = 8\) that is \(a = 0.838\) and a reach of 5.7 px, with half weight already at 3.9 px. At a 30-grey-level edge with \(\sigma_r = 0.2\) the coefficient drops to \(a = 0.36\), so support decays about four times faster — the numerical meaning of “the filter stops at edges”.

The whole stage is about fifteen lines. This is the shipping filter, written in NumPy instead of C++:

import numpy as np

def coefficients(img, sigma_s=8.0, sigma_r=0.2):
    """One coefficient per neighbour pair. Depends on the image only."""
    k, rs = -np.sqrt(2) / sigma_s, sigma_s / sigma_r
    img = img.astype(np.float32)
    dx = np.abs(np.diff(img, axis=1, prepend=img[:, :1]))   # left neighbour
    dy = np.abs(np.diff(img, axis=0, prepend=img[:1, :]))   # upper neighbour
    return (np.exp(k * (1 + rs * dx / 255)),
            np.exp(k * (1 + rs * dy / 255)))

def aggregate(C, ax, ay):
    """Filter ONE disparity plane in place. Four passes, O(1) per pixel."""
    for x in range(1, C.shape[1]):              # left to right
        C[:, x] += ax[:, x] * (C[:, x - 1] - C[:, x])
    for x in range(C.shape[1] - 2, -1, -1):     # right to left
        C[:, x] += ax[:, x + 1] * (C[:, x + 1] - C[:, x])
    for y in range(1, C.shape[0]):              # top to bottom
        C[y] += ay[y] * (C[y - 1] - C[y])
    for y in range(C.shape[0] - 2, -1, -1):     # bottom to top
        C[y] += ay[y + 1] * (C[y + 1] - C[y])
    return C

Ten pixels of one row, with real numbers — the same row and disparity as the Census example above, before any vertical pass:

Two things to read out of it. At \(x = 82\) and \(83\) the image steps by 20 and 26 grey levels, and the coefficient falls to 0.48 and 0.41. The running value is then pulled most of the way to the local cost. Support does not cross that edge. And at \(x = 89\) the raw cost collapses to 0.208 — one bad sample — while the filtered value only falls to 0.641, because it is still carrying eight neighbours’ worth of evidence. That is aggregation doing its job in one number.

Two notes on reading the code. The updates are in place and ordered: C[:, x - 1] has already been overwritten by this pass, so it is \(F_{x-1}\). And the backward pass uses ax[:, x + 1], because a coefficient belongs to the pair of pixels it sits between, not to one pixel.

Running this on the scored planes reproduces the C++ output to 0.001% of a plane’s range, which is the int16 rounding. The shipping version differs only in arithmetic: \(a\) is stored as a uint16 in Q15, and the recurrence multiplies into int32 and stores back to int16. Those details are not cosmetic — Part 3 reproduces them bit for bit on the GPU, which is what makes cmp a valid test there.

1.3 How many candidates the solver needs

How many candidates per pixel does MASDA need? Sweeping \(k\), the number of top-scoring disparities kept per pixel, against the full volume:

Two — and \(k=2\) was measurably better than \(k=8\). The extra candidates are noise, and the solver has to weigh them against the real ones. This is Part 1’s precision-by-margin table speaking again: the second-best candidate carries real information, since it defines the margin. The eighth carries none.

With \(k=2\), the running top-2 per pixel is the reduced volume. So the pipeline computes one disparity plane at a time — score, filter, insert — and the array never exists:

The insert’s common case is a rejection that reads one cached plane, so the whole stage is a single streaming pass over the scored planes. Removing the volume measured 1.9× end to end, and made the accuracy work possible: every parameter in the sweep was measured on a pipeline fast enough to iterate on.

Three structural properties fall out of this design and matter later:

• Rows are independent, because correspondences live on a rectified row. Each row is a separate MASDA instance.
• Disparity planes are independent until the top-2 insert, which is a per-pixel reduction.
• The aggregation needs whole constant-disparity planes. The recursive filter runs across the image at one disparity. This constraint decides the outcome of two separate experiments in what did not work. It is the single most consequential property of the design.

2. Sub-pixel disparity: the largest accuracy result in the project

The solver picks a disparity from a discrete set, so its output is an integer. That forfeits up to half a pixel before any matching error, and fixing it is worth more than every other accuracy change in this post combined.

The fit is a parabola through the aggregated cost at the winning disparity and its two neighbours, with the vertex taken as the answer:

Panel (c) is the reason this matters and the reason it went unnoticed for a long time. A perfect integer disparity map scores 45.6% bad-1.0 on Middlebury v3 at quarter resolution. A perfect floating-point one scores 0.8%. The reason is the threshold. The benchmark allows one pixel of error at full resolution, and the matcher works at quarter resolution, so the allowance is a quarter of a pixel in the matcher’s own units. An integer answer can never land inside a quarter-pixel window, no matter how correct it is. The matcher’s own integer output measured 41.5%, which is close to that 45.6% ceiling: the matching was already good, and the output format was throwing it away.

With the fit: 41.5% → 24.5%, at coverage that does not move — 17 points. The fit changes values, never decisions.

The estimator matters as much as having one. Write \(c_0\) for the score at the winning disparity and \(c_{-1}, c_{+1}\) for its two neighbours. Fitting a parabola through the three and taking its vertex gives an offset

and the answer is \(d + \delta\), clamped to \(|\delta| \le \tfrac{1}{2}\). A parabola is the wrong shape for this cost. The graded score blends Census with a truncated absolute difference, which is piecewise linear, so the surface around the winner is locally a V rather than a bowl. Fitting two straight lines of equal and opposite slope instead — the equiangular estimator, the standard one for a V — changes only the denominator:

Same three samples, same one line of code, no extra memory:

0.71 points for one line. The third row says the absolute-difference term still costs 0.72 even with the right estimator, so this is not purely an estimator mismatch. Fitting on the Census term while selecting on the graded cost would collect the rest, at the price of a second filtered plane. Not built.

Two implementation details matter enough to describe.

Getting the neighbours back. The whole point of never building the volume is that the filtered cost volume does not exist, so the two costs the fit needs are gone by the time the winner is known. The cost stage now retains a three-wide window around each pixel’s running best. When a new best is set, the previous plane’s value becomes its left neighbour, and the next plane’s value becomes its right. That only works if the disparity planes arrive in order within a thread, which means the cost stage hands each worker a contiguous range of disparities instead of stealing single planes. Those ranges have to be sized by work rather than by plane count. A plane’s cost is proportional to its valid width \(W - 6 - d\), which shrinks as \(d\) grows. Equal plane counts would leave the low-\(d\) worker holding the most.

It costs 1.30× on the CPU. The three-wide window and the coarser work quantum both land on the cost stage. The first version cost 1.53×, and I fixed the wrong half of it before finding the right one. Double-buffering removed the extra store and barely changed the wall clock, because the store was never the constraint. The chunked scheduler was. 16-plane chunks at \(D=60\) is four chunks for six threads, so two threads got nothing and occupancy fell from 5.3 of 6 cores to 3.7. That is worth more than the arithmetic it saved.

3. Measuring it: the benchmark had to change first

For most of this project the accuracy number came from eight Middlebury 2003/2005 scenes at 450×375, scored at native resolution. That benchmark is structurally incapable of seeing the sub-pixel result: at a one-pixel threshold on the native grid, integer output costs almost nothing. Sub-pixel disparity measured as slightly harmful there, was recorded as a negative, and sat disabled.

Middlebury v3 is where the field publishes, and its rules differ in a way that matters: the evaluation is always at full resolution, and it upsamples your result to get there. Disparity scales with resolution, so a quarter-resolution result has its disparities multiplied by four and its errors with them.

That trap is worth stating precisely, because the first evaluator I wrote fell into it. Scoring a quarter-resolution result against quarter-resolution ground truth at bad-1.0 gives 13.0% where the leaderboard says 37.3% for the same data. That is 2.9× too good, and it looks entirely plausible. What caught it was scoring Middlebury’s own published SGM output, which ships with the dataset and has a known row on the public table. An evaluator that cannot reproduce a known result is not evidence about anything. Mine now reproduces it to 37.33 against 37.3 and refuses to run if it stops.

The metric definitions are transcribed from the benchmark’s own evaldisp.cpp rather than reimplemented. Three details change the answer:

• the maximum disparity for clipping comes from the result’s calibration;
• the integer-rounding flag comes from the ground truth’s;
• bad counts wrong pixels over all masked pixels, including the ones the matcher left empty.

That last one means bad is not an error rate over answered pixels until you divide by coverage.

4. What the matcher produces

All fifteen v3 scenes run, including the two with disparity ranges of 160 and 190. These are the eight 2003/2005 scenes, at their native resolution, so the disparity maps are directly comparable with the ground truth beside them. Black is “no answer” — either no ground truth, or the margin gate declining to commit:

The error column is the interesting one. The residual error is at depth discontinuities and in repetitive texture, which is where Part 1’s ambiguity analysis predicted every matcher loses — including the exact assignment solver. The error budget measures exactly how much of the total error lives near discontinuities, because it turns out to decide whether a whole family of improvements is worth building.

5. The precision–coverage curve, and reading it against SGM

A matcher with a confidence gate does not have an accuracy. It has a curve, and the gate picks a point on it. Sweeping the margin gate across the fifteen v3 scenes:

This is the only fair way to compare against a matcher that answers a different number of pixels. Read at matched coverage, SGM is ahead. Read at the shipping gate, this matcher has the lower error rate but answers ten points fewer pixels. Both readings describe the same picture: SGM’s curve has a lower error rate than this one over the coverage range where they overlap.

That is a different conclusion from the one the older eight-scene benchmark supports, where dense MASDA measures 9.8% bad-1.0 against OpenCV SGM’s 10.9%. Both numbers are real. The 2003/2005 scenes at native resolution are an easier problem scored at a looser tolerance, and the two benchmarks disagree about the ordering. When they disagree I take the harder one, but the older number is not wrong — it is answering a different question.

Where the coverage goes is worth knowing, because it is not lost:

One property of the margin bounds how far it can be trusted, and no benchmark shows it. Best-minus-second is only defined over the candidates actually searched. Where the true disparity is outside the search range, or its match lies off the edge of the other image, the best candidate has no real competitor and the margin is therefore large. On the camera this is not hypothetical. One scene had its near floor outside the search range. Raising the gate to 0.05 there removed a fifth of the wrong points and four fifths of the right ones. A confidence that reads only the cost curve cannot see the case where the answer was never on the curve.

98% of the coverage cost is the gate, which is a chosen position on the curve. I built the fix for the other 0.2. When a pixel’s best candidate points at a right pixel some other pixel has already claimed, retry its second candidate rather than dropping the pixel. Measured, that moves coverage 80.1% → 80.3% for error 26.0% → 26.3%. The coverage it recovers costs the same in error. Reverted.

6. Where a pixel is actually lost

A single error rate says how often the matcher is wrong, not which component was wrong. Dumping the aggregated cost volume and asking where the true disparity ranks splits it. Over the 2.35 million far-field pixels — those nowhere near a depth discontinuity, which carry 71% of all error:

Half a pixel is the threshold that matters, because a candidate that close is the nearest integer to the truth and the sub-pixel fit can still reach the answer. A candidate a full pixel away cannot be refined into a correct one.

Reading the bill:

• The descriptor is the largest single item. 10.8% of far-field pixels have no candidate within half a pixel anywhere in the top eight — unreachable by any solver on this cost volume — and 19.0% are unreachable without keeping more than two candidates.
• 13.1% is the selector’s. The truth is in the top-2 and the top-1 was taken. That is the one component with a clear mandate and no mechanism currently collecting it: the ablation shows that neither winner-take-all nor message passing gets it.
• 8.5% is the fit, on pixels whose integer was already right.

One methodological note, because it changed the answer. Run on Teddy alone, this table says the fit is dominant and the descriptor costs almost nothing. Teddy’s cost is much better than average: 92.8% top-1 in the far field, against 67.9% pooled. The fifteen-scene number inverts the ordering. One scene is not a benchmark. This is the cleanest demonstration of that in the project.

7. What the parameters are worth

Every parameter in the matcher, swept on the fifteen v3 scenes at the shipping configuration. Some of these had never been measured, and one of them had never been measured at all despite carrying a comment that implied it had.

Aggregation reach \(\sigma_s\) — was set past its optimum. The comment beside it recorded a sweep of the range parameter \(\sigma_r\), and \(\sigma_s\) had simply inherited a value:

(This sweep and the two below predate the equiangular estimator, so their absolute values sit 0.7 above the current operating point. They are read for the shape of the curve, not for its level.)

Better on both axes at 6–8 than at 12, and it costs nothing: the filter is an IIR whose cost does not depend on \(\sigma\). The shipping value is 8. Those 0.9 points cost zero runtime, and they went uncollected only because a comment about a neighbouring parameter made 12 look considered.

The graded cost interacts with the sub-pixel fit, and the benchmarks disagree. The truncated absolute difference blended into the Census score was measured at 10.3% → 9.7% when it was added:

On v3 it now measures the other way — and the entire effect is the fit. With sub-pixel disabled, ad 0 gives 42.00 and ad 0.15 gives 42.04, which is nothing. The truncated difference saturates and is piecewise linear, so blending it into the cost changes the shape near the minimum. An argmax does not care about shape; a parabola through three samples cares about very little else. On the older eight-scene benchmark, scored at native resolution where the fit’s quality is invisible, the graded cost still helps — 9.8% against 10.3%, and better coverage. It stays on, because that is the resolution and tolerance the camera actually operates at, and the interaction is recorded rather than tuned away. The change that would improve both is to fit on the Census term alone while still selecting on the graded cost, which costs a second filtered plane.

\(\lambda\) and \(\gamma\) do nothing where they are set. These are MASDA’s clutter and misdetection costs — the price of leaving a left pixel unmatched and a right pixel unclaimed:

Below zero they are not merely flat — a factor of four in magnitude produces a byte-identical disparity map. Both values are lower than almost every candidate score in the volume, so the rejection they implement rarely fires. Above zero they work. What they do is trade coverage for precision, at roughly the same exchange rate as the margin gate — which makes them a second gate rather than a second mechanism.

Descriptor size trades, it does not improve. The obvious response to a 10.8% descriptor bill is a bigger descriptor — the Census window is a template and 9×7 is 62 bits, which still fits a uint64. Before touching fifteen border literals in the cost loops and the CUDA census kernel, the direction was priced on the axis already wired. --csct is the same Census at 24 bits instead of 48:

Halving the descriptor lowers the error rate by 0.5 and costs 3.7 points of coverage. That is the same precision–coverage trade every other parameter offers — not a better or worse descriptor, a differently-gated one. If 24 fewer bits only slides along the curve, 14 more will too, so 9×7 is not worth building.

Which sharpens what that 10.8% is: not a bits problem. More of the same descriptor will not collect it. It is a limit of Census-plus-truncated-difference as a similarity measure on weakly textured and repetitive surfaces. Moving it means replacing that measure.

And one flag does nothing at all. --agg, the aggregation radius, produces identical output at 3, 7 and its default, because the recursive filter ignores it. It still exists as a flag because an older box-filter path used it. Stated here so that nobody sweeps it and wonders why nothing changes.

8. The ablation: message passing is not worth its 12 ms in the dense path

The matcher is named after an inference algorithm, so the obvious question is what that inference contributes. Disabling the message passing leaves everything else in place: the candidate set, the one-to-one decode, the margin and the gate. The decision is then made by score alone. That is winner-take-all with a uniqueness constraint on top:

The message passing gains coverage and costs precision, at about the same rate as the gate and \(\lambda/\gamma\). It is a third parameter along the same curve. And it costs time: on the TX2 the solve is 13.0 ms without it against 25.5 ms with it, so roughly twelve milliseconds of CPU at the camera’s resolution.

Getting this measurement right required fixing the ablation first. With no messages the max-sum belief \(\beta + \rho - s\) degenerates to minus the score, so the solver picked the worst candidate. The configuration read 67.3%, which looks exactly like proof that message passing is worth forty points. It is not an ablation, it is an inverted objective, and it would have been an easy number to publish.

What this does not say is that MASDA is doing nothing. Two parts survive the ablation, and they are the parts that distinguish this from a block matcher:

• the one-to-one constraint, which SGM does not have at all and approximates with a left-right consistency check added afterwards;
• the margin, which a downstream consumer gates on.

Both are present in every row of that table. What is in question is the loopy belief propagation on top of a two-candidate set, which is the case where it has least to decide.

On the sparse keypoint matcher, where each point has many candidates on deliberately ambiguous projected-dot texture, message passing finds 46% more matches than nearest-neighbour. Temporal association, where the candidate set is genuinely large and two-dimensional, has not been tested. Message passing is off by default in the dense path and one flag away.

The camera adds a detail the benchmark cannot show. Take a live scene where part of the floor falls outside the search range, so those pixels have no correct answer available at all. Raising the iteration count moves coverage from 88.3% to 90.0%. It also moves the number of points sitting on a demonstrably false surface from 242 to 473. The extra ones are concentrated in the strip where the correct match lies off the edge of the right image.

So the extra coverage is partly coverage of pixels that cannot be answered. Message passing propagates support along the row. Where no correct answer exists, it propagates the wrong one and raises its confidence. A one-to-one constraint does not reject an occluded pixel when the true partner is outside the image, because there is no competitor for it to lose to.

9. What did not work, and why

Four families of improvement were measured and declined. Each was priced before it was built, which is the only reason the list is short.

Restricting the disparity range — 5.2× on paper, 1.9× in practice. Every fast published CPU matcher avoids the exhaustive sweep: ELAS triangulates support points, PatchMatch propagates hypotheses, rSGM subsamples. The ceiling is real — if each 16×16 tile knew which disparities its pixels needed, it would compute 19.2% of the sweep. Three things consume that saving:

1. Per-pixel restriction is illegal here. The filter aggregates over a plane, so a plane must hold one constant disparity. Restriction has to be per-tile, so that every pixel in a tile sweeps the same set.
2. The best available predictor is not accurate enough. A half-resolution pass predicts tile ranges at 20.9% of the sweep — essentially at the oracle’s cost — but with 90.7% recall, meaning one true disparity in eleven falls outside its tile’s band. Reaching a usable recall costs most of the saving.
3. The aggregation needs its input. A tile can only skip a plane if it also skips it for the pixels the filter reads, and the filter reaches ~16 px. A 16×16 tile wanting one plane costs a 48×48 patch of it. That takes 26.3% to 53.8%.

Intrinsic curves deserve a separate mention because they reproduce their paper exactly and still do not help. The construction admits 13.9% of the disparity range per pixel — an 86% reduction, right at the published claim. But the admitted disparities of neighbouring pixels do not agree: the union over even a 4×4 tile is 43.6% of the range. A reduction that is per-pixel and spatially incoherent is unusable by a matcher that aggregates over planes. It is usable by one that scores candidates individually, which that paper’s own SGM does.

Better edge-aware support — the target is real, the mechanism is not. Pixels within 8 px of a depth discontinuity are 18.3% of the image and carry 28.6% of all error, at 57.1% against a 32.0% far-field rate. That is a 4.6-point target. But two independent parameters that should move it do not:

• a fourfold range of the filter’s edge sensitivity leaves near-edge error at 57.1–57.8%;
• handing the solver the entire disparity range, instead of two candidates, leaves it at 56.4%.

What remains is half-occlusion. Beside a foreground edge, part of the support has no correspondence in the other image at all, and no weighting scheme fixes neighbours that are not visible. The aggregation here is already edge-aware, and making it more or less so does not touch the pixels it was supposed to help.

A second search band around the coarse level’s runner-up. MASDA exports its second-best candidate, and at thin structures the runner-up is often the surface the best candidate missed. Measured: worse everywhere. Where the coarse level is ambiguous, its runner-up is the wrong period of a repetitive texture. A band around that hands the fine solver a wrong surface, which it then aggregates into a confident answer.

A strict per-pixel band-membership test at insert time — the principled version of a masked search. Measured a full point worse. The row-interval slack admits candidates a pixel’s own band would exclude, and they help.

The last two point the same way as Part 1’s central result. Exact per-row assignment is no more precise than MASDA on identical candidates. The inference is therefore not what bounds the outcome. The candidate set is. What you offer the solver matters more than how cleverly you restrict it. Both of these experiments restricted it, and both restricted it well.

10. Where this leaves the CPU implementation

At the camera’s 848×480 the CPU matcher is a 5 Hz matcher, and the solve — the part that is MASDA — is memory-bound rather than arithmetic-bound. Two structural properties say where it goes next, and neither is a CPU optimisation. Disparity planes are independent, rows are independent, and the solver is two strided reductions.

That is a description of a CUDA kernel, and the TX2’s GPU sits at load zero through everything above.

Part 3 is that port. The image plane moves to the GPU and the CPU keeps the graph. The matcher then runs at 31.7 ms per frame at 848×480, bit-identical to this implementation on all eight ground-truth scenes.

The methodological part is worth keeping even if the matcher were thrown away. Three rules, each produced by a failure:

1. The desktop is not a proxy for the target, in either direction.

   change	on the desktop	on the Jetson
   int16 arithmetic	neutral	worth 20%
   a 24-bit descriptor	worthless	worth 10%
   a coarse-to-fine mask	worth 1.24×	flat

2. The benchmark decides what you can see. Sub-pixel disparity was a recorded negative for months because the benchmark in use could not resolve it.

3. Check that a default change is live before measuring it — twice over.

   A header was listed as a prerequisite in one build rule and not the other. A header-only change therefore relinked nothing, make printed success, and a fifteen-scene benchmark measured the old value and reported it as the new one.

   Then both benchmark harnesses turned out to pass --iters with values of their own, silently overriding the binary’s default. “The default configuration” had for weeks meant the harness’s opinion, so a default change read as no change whatsoever.

   Both were caught by a number coming back exactly equal to a figure that should have moved. An unchanged measurement is a weaker signal than an error, and a slightly different one would have been believed.

The matcher is de_dense.cpp, plain C++14 with no dependencies. Every figure in this post is regenerated from the shipping binary by one script, and every number by one benchmark command against Middlebury ground truth.

References

Full citations with DOIs, and every term this post uses, are in the series glossary.

• Geiger, A., Roser, M., & Urtasun, R. (2011). Efficient large-scale stereo matching. ACCV 2010, LNCS 6492, 25–38 — support points and a triangulated prior; the canonical “don’t sweep” CPU matcher (ELAS).
• Bleyer, M., Rhemann, C., & Rother, C. (2011). PatchMatch Stereo — Stereo matching with slanted support windows. BMVC — hypothesis propagation instead of a sweep, and slanted support windows.
• Spangenberg, M., Langner, T., Adfeldt, S., & Rojas, R. (2014). Large scale semi-global matching on the CPU. IEEE Intelligent Vehicles Symposium, 1118–1124 (rSGM).
• Ruf, B., Mohrs, J., Weinmann, M., Hinz, S., & Beyerer, J. (2021). ReS2tAC — UAV-borne real-time SGM stereo optimized for embedded ARM and CUDA devices. Sensors, 21(11), 3938 — the disparity-in-the-lanes formulation, and the embedded CUDA baseline Part 3 measures against.
• Nover, H., Achar, S., & Goldman, D. B. (2018). ESPReSSo: Efficient slanted PatchMatch for real-time spacetime stereo. 3DV, 578–586 — edge-aware aggregation under shared plane hypotheses; the one remaining candidate for range restriction that produces tile-constant hypotheses by construction.
• Shahbazi, M., Sohn, G., Théau, J., & Menard, P. (2016). Revisiting intrinsic curves for efficient dense stereo matching. ISPRS Annals, III-3, 123–130 — the per-pixel range reduction measured in what did not work.