Counting targets when the sensors make mistakes

Counting targets by their holes showed something that looks too good to be true. A field of sensors, each reporting only how many hidden targets it can detect — not which targets, not how far away — can have its readings combined into the exact number of targets. Take the region where the count is at least one, the region where it is at least two, and so on; work out the Euler characteristic of each, the number of pieces minus the number of holes; add them up. If each target is detected inside a region with no holes, of any size and shape, overlapping the others in any way, the sum is the number of targets. Yuliy Baryshnikov and Robert Ghrist called this integration against the Euler characteristic, and proved it in 2009.

That essay ended with the obvious worry. The Euler characteristic depends only on how many pieces and holes a region has, and a single wrong reading can make a new piece or a new hole. Real sensors misread. This essay measures what that does to the count, why the damage grows the more sensors there are, and how the count can be repaired — by smoothing the readings and then counting each piece and hole not once but by how long it lasts. The repair works remarkably well, and it costs something specific: the one property that made the method surprising.

Eight targets, counted as a hundred and sixty #

The field in the figure has eight targets. Six are detected within discs that overlap their neighbours in a ring, enclosing a gap in the middle; two more sit apart in the corners. The region where at least one target is detected is a ring with a hole, plus two discs: three pieces, one hole, Euler characteristic two. The region where at least two are detected is the six lens-shaped overlaps: six pieces, no holes, characteristic six. Nowhere are three targets detected at once. Two plus six is eight, and the count is right, without any sensor knowing how large a detection disc is or where its target sits.

Now let each sensor misread with probability one in ten, reading one more or one fewer than the truth, never below nought. In this field that is 415 wrong readings out of 5,760, scattered at random. The middle panel looks like the left panel with a light speckle on it, and any method that averaged readings would barely notice. The Euler count notices completely: it comes out at 160.

The reason is visible in the speckle. For a region drawn in the plane, corners minus edges plus faces comes to pieces minus holes — the planar form of Euler’s count, which two trees through the corners and the faces proves — and the speckle adds to both. A sensor outside every disc that reads one instead of nought is a new piece of the region “at least one”: a tiny island, one sensor wide, which adds one to the characteristic exactly as a whole target would. A sensor inside a disc that reads two instead of one is a new island of the region “at least two”, and adds one. A sensor inside a disc that reads nought instead of one punches a hole in the region “at least one”, and subtracts one. The Euler characteristic has no notion of size, so the island one sensor wide counts as much as the disc forty sensors wide. That indifference to size is precisely what let the method count targets of unknown size, and it is precisely what makes it count every speck.

More sensors, more error #

For most measurements more data helps. An average of $n$ independent readings has an error that shrinks like $1/\sqrt n$, the law that the average settles and the wobble does not separates into its two halves. The Euler count is not an average, and it behaves the opposite way.

The overshoot follows a simple rule. Outside every disc, half of all mistakes are readings of one instead of nought, and each is a new piece: those add $p/2$ times the number of empty sensors. Inside the discs, a reading one too high makes a new piece one level up and a reading one too low makes a hole, and the two roughly cancel. Readings one too low outside the discs are clipped at nought and change nothing. So the expected overshoot is about $p/2$ times the number of sensors that see no target, and the dashed lines in the figure, which are exactly that, run through the measurements.

At $p = 0.01$ — one reading in a hundred wrong — the coarse grid overshoots by about four, the middle one by about eighteen, the fine one by about sixty-five. Quadrupling the number of sensors over the same ground roughly quadruples the error. A denser network sees the targets in more detail and counts them worse. The error is not a fluctuation that grows like a square root; it is a bias that grows in proportion to the number of readings, because each wrong reading is one wrong feature and no two cancel.

The same arithmetic applies to any estimate built from the Euler characteristic of thresholded data: counting cells in a microscope image, galaxies in a survey, blobs in a scan. Each spurious pixel is a spurious object. The first thing image analysis does with such data is to clean it, and the obvious cleaning is the median.

A median repairs isolated mistakes #

Replace every reading by the median of itself and its eight neighbours. An isolated wrong reading is outvoted by eight correct ones and disappears; a region more than a sensor or two wide is left unchanged, because most of the nine readings inside it agree. This is the same robustness that the median of many small averages exploits in estimation: a median ignores a minority of wild values entirely, where an average is dragged by every one.

The median count is exact up to one reading in ten. At one in five it starts to fail, and by one in three it is off by ten. The failure has a definite cause. When mistakes are common, two or three of them often fall in one neighbourhood of nine, and five out of nine is a majority: a cluster of wrong readings survives the median as a speck of its own, and each speck is again a whole new piece. The median does not reduce the influence of a mistake; it removes isolated ones and leaves the rest at full strength. Its count is exact until the clusters appear and then degrades in the same all-or-nothing way as the raw count.

The third curve in the figure is flat at nought all the way to one reading in two. It needs two ideas: smoothing the readings so that they become a continuous surface, and counting each feature of that surface by how long it lasts.

Counting a feature by how long it lives #

Average each reading with its neighbours, weighting near ones more than far ones by a bell-shaped Gaussian of width $\sigma$ sensors — the shape a random walk spreads into, and the shape of a single hot spot after it has cooled for a while. That is the smoothing heat performs on a temperature profile, and the corners go first explains why it erases fine detail so much faster than coarse detail: the finer a feature, the faster it fades. A single wrong reading becomes a faint bump, about a fourteenth of a target’s height at $\sigma = 1.5$; a whole disc keeps nearly its full height.

The smoothed readings are no longer whole numbers, so the regions “at least one”, “at least two” no longer capture everything. Instead lower a threshold $s$ continuously from the highest reading to nought, and watch the region above it. Pieces appear at the peaks and grow; two pieces meet and merge, and the younger is said to die, absorbed into the older; holes appear where pieces join around a gap, and are filled in as the threshold falls further. Each piece and each hole has a lifetime: the height at which it was born minus the height at which it died. This is the bookkeeping of persistent homology, formalised by Herbert Edelsbrunner, David Letscher and Afra Zomorodian around 2000, and the rule that the younger of two meeting pieces dies is called the elder rule.

The lifetimes connect directly to the Euler count. Baryshnikov and Ghrist extended their integral to real-valued readings in 2010 by integrating the Euler characteristic of the region above the threshold over all thresholds, $\int_0^\infty \chi(h \ge s)\,ds$. A piece alive between heights $d$ and $b$ contributes $+1$ to $\chi$ for every threshold in between, a total of $b - d$, its lifetime; a hole contributes $-1$ for its lifetime. So the integral of the smoothed readings is the sum of the pieces’ lifetimes minus the sum of the holes’. For whole-number readings it is the original count. For smoothed readings it is a count in which every feature is weighed by how long it survives.

The lifetimes split cleanly into two groups. Nine live for most of a unit or more, between 0.80 and 2.03. Eight are pieces: the six overlaps are born at the top, and as the threshold falls below one they join up into the ring, so by the elder rule five of them die there, after lifetimes a little under one, and the sixth carries on as the ring itself down to nought, a lifetime of two; the two corner discs live for about one each. The ninth is the hole in the middle of the ring, born when the ring closes and filled only at nought. The other 117 all die within 0.19 of being born. They are the mistakes: specks too faint after smoothing to last.

Weighing every feature by its lifetime already helps. Each speck now contributes a few hundredths rather than one, and the 117 together contribute 1.30, so the integral of the smoothed readings is 8.66 rather than 160. Rounding each lifetime to the nearest whole number before adding removes the specks altogether, since every one of them rounds to nought, and leaves the long-lived features at one each — two for the ring’s piece. The rounded count is eight.

There is a theorem behind the gap. The stability theorem of persistent homology, proved by David Cohen-Steiner, Herbert Edelsbrunner and John Harer in 2007, says that if two functions differ by at most $\varepsilon$ everywhere, their lifetimes can be matched so that no lifetime moves by more than $\varepsilon$, and any unmatched feature lives at most $2\varepsilon$. Here the smoothed mistaken readings differ from the smoothed true readings by at most 0.24 anywhere. So no feature the mistakes create can live longer than 0.48, which rounds to nought, and each true feature’s birth and death move by at most 0.24. The guarantee is conservative: to be sure that every true feature still rounds to one, it would need them all to live longer than about one, and the overlaps here live only 0.8 or so. The measured specks are far shorter than the theorem allows — none above 0.19 — which is why the count survives in practice well beyond what the theorem promises, even at one reading in two.

The cost of smoothing #

Smoothing cannot be free, and on true readings its cost is easy to see.

As the smoothing widens, the overlaps between discs, which are narrow lens-shaped regions, are flattened. Their peaks are lowered and their lifetimes shrink, and the unrounded integral falls steadily: 8.01 at width one, 6.67 at width two. The rounded count does not move while every overlap still lives longer than a half. Past a width of about three sensors the overlaps fall below a half, round to nought, and the count collapses to three.

So the width must be chosen between two limits. It must be wide enough to turn each mistake into a bump too short-lived to round up, and narrow enough to leave each real overlap long-lived enough to round to one. The second limit depends on how thin the thinnest real feature is.

The lower limit is the same in every row: about one sensor’s width of smoothing is needed before isolated mistakes stop counting. The upper limit grows with the depth of the overlaps, roughly in proportion to it — a third to a half of the depth. With overlaps eight sensors deep, every width from one to nearly three works. With overlaps two sensors deep, exactly one width works. Thinner still, and none would: a real feature thinner than the smoothing needed to swallow a mistake cannot be told apart from a mistake.

That is the price. The original theorem needed nothing about sizes: targets of any size, overlapping by any amount, were counted exactly. The robust count needs a scale — the smallest overlap, gap or region that is real — because it has to declare everything smaller than that scale to be noise. The two cannot both be had. A single misread sensor and a genuine overlap one sensor wide produce the same readings, so no method that ignores size can tell them apart, and any method that tells them apart has assumed a size.

Why topology is fragile and what persistence adds #

The Euler characteristic is an extreme case of a general difficulty with topological measurements. A count of pieces and holes is a whole number, and a whole number cannot change a little: any perturbation either leaves it alone or changes it by at least one. The solid where the answer is not two showed how a single tunnel changes $V - E + F$ from two to nought; a single sensor can make or fill that tunnel. Measurements of length or area move continuously with their data, and errors in them can average; topological measurements jump.

Persistence turns that jump into something continuous. Instead of asking whether a feature exists at one threshold, it asks over what range of thresholds it exists, and a range can be long or short. A real feature exists over a long range; a feature made by noise exists over a short one. The stability theorem is exactly the statement that this range moves continuously with the data. That is why persistence has become the standard way of applying topology to measured data — point clouds sampled from shapes, images, sensor fields, the shapes of molecules — and why its outputs are pictures of lifetimes rather than single numbers.

The Euler integral is unusual among topological tools in that it adds: the alternating count of corners, edges and faces obeys inclusion and exclusion just as area does, and that additivity is what lets it count overlapping targets. Persistence keeps the additivity, because the integral of the smoothed readings is the signed sum of lifetimes, and adds the robustness. Rounding sacrifices exact additivity for an integer answer; leaving the lifetimes unrounded keeps it, with a bias that the drift figure shows.

Still open: robustness with fewer assumptions, and moving targets #

The window in the last figure is a measurement on one field. How wide the window is in general — how the minimum feature size, the error rate and the density of sensors trade against one another — is known only through bounds like the stability theorem, which guarantee a count when the noise is small enough in the worst case and are pessimistic in the ordinary one. Mistakes that are not independent, such as a whole row of sensors failing, or a sensor that counts one target twice whenever two targets are near, defeat the smoothing argument, and robust counts under such models are not worked out.

The integral of real-valued readings has a further subtlety that Baryshnikov and Ghrist pointed out: there are two natural ways to define it, by thresholding from above or from below, and for functions that are not whole-number valued they give different answers. The rounded count chooses one. Which version, if either, is the right one for noisy sensor data, and whether a version exists that is both additive and stable, is open.

And targets move. When the readings are a field changing in time, a count can be made at each moment, but the counts at successive moments should be consistent — a target does not appear and vanish — and persistence over time as well as over threshold is the natural tool. How to combine the two, so that a target briefly hidden by an error is carried through rather than lost and found again, is an active question in sensor networks, and so is the reverse problem the original theorem left open: which sensor readings beyond a single count allow more than the number of targets to be recovered.