One edge is not an edge

An edge has no order of convergence measured the three resampling kernels across a discontinuity and found their orders collapsing from the first, second and third they reach on a smooth field to 0.78, 0.58 and 0.60 — within a factor of 1.33 of one another, with nearest-neighbour fastest. It then recorded what that measurement was:

The edge measurement is of one edge. A single straight discontinuity at 27° to the graticule, with no noise. Real imagery has curved edges, corners and edges at every angle including the aligned case, which is genuinely easier for every kernel.

Two of those three predictions are wrong, and the third is wrong in the most interesting way available.

The aligned case is the worst, not the easiest #

The note predicted that an edge aligned with the sampling lattice would be easier. It is the hardest case for every one of the three kernels, and for one of them it is not merely hard but unconverging.

The sequence for the aligned case is 2.3, 1.7, 21.7, 0.90, 30.1 — in units of a thousandth — as the raster goes from 48 cells across to 160. It does not fall. It depends on whether this particular grid happens to put the edge on a cell boundary, and the answer to that question changes erratically as the grid is refined.

A convergence order fitted through that sequence comes out at −1.49, and a negative order is the honest signal that there is no order to fit. The essay this rung extends was named for a claim about one edge; the aligned case is a stronger version of the same claim, and it is the case every rectangular field boundary, every building in a nadir image and every administrative border drawn on a graticule actually is — including the antimeridian, which is a cut in the numbers rather than a feature.

The reason the alignment hurts rather than helps is worth being precise about. An oblique edge crosses a mixture of cells — some almost entirely on one side, some split near the middle — so refining the grid improves the average steadily. An aligned edge crosses every cell in the same row in the same way, so refining the grid either fixes all of them at once or none of them, and which of the two happens is a property of the arithmetic rather than of the resolution.

The ranking reverses #

Across the family, cubic interpolation spans 0.19 to 0.87, bilinear 0.30 to 0.64, and nearest-neighbour −1.49 to 0.86. Those ranges overlap almost entirely, which means the question which kernel converges fastest across an edge has no answer independent of the edge.

It has a different answer at different orientations. At 15° nearest-neighbour reaches 0.676 against cubic’s 0.666, so the simplest kernel wins; at 63° it is 0.267 against 0.469 and the most elaborate one wins by nearly a factor of two. A table of convergence orders is used to choose a kernel, and the choice it supports depends on how the edges in the image happen to lie.

That is the finding this rung exists for, and it is a stronger statement than the one it extends. The published order was not merely a sample of a distribution; it was a sample of a distribution wide enough to contain the ordering as well as the values.

The curve and the corner #

The curved edge behaves like an average of orientations, which is what it is: 0.35, 0.30 and 0.33 for the three kernels, sitting inside the range the straight cases span and closer to their middle than to either end. Nothing about curvature is special, because a smooth curve is locally straight at the scale of a cell and the measurement averages over every angle it presents.

The corner is more interesting and less dramatic than expected. Adding a second discontinuity meeting the first at a right angle changes the orders by less than the orientation does — 0.86 against 0.78 for nearest-neighbour at 27°, 0.57 against 0.60 for cubic — because a corner is one point and an edge is a line, so the corner contributes a vanishing fraction of the error as the grid is refined.

A feature of lower dimension does not change a convergence order, which is a general fact that this family makes concrete. What a corner does change is the overshoot, and that is not a convergence question at all.

Across all three shapes the cubic kernel leaves the data’s own range by 11 to 12 per cent of the jump, and nearest-neighbour never does — not approximately, but exactly, because it invents nothing and only moves values that were already there. That contrast is unchanged by orientation, unchanged by curvature and unchanged by the corner, which makes it the one property of these kernels that a table can honestly report.

What was computed, and how #

Thirteen fields, three kernels, five grid sizes, one fit.

Each field is a signed distance function plus a jump across it, so the discontinuity is exact and has no width: a straight edge at a stated angle, a circular arc, and the intersection of two half-planes. A gentle gradient on each side keeps the two regions from being flat, so the smooth part of the field still exercises the kernel.

Each is resampled into another projection and back — an operation whose geometry composes exactly even though its values do not — and the root-mean-square difference from the original is fitted against the grid spacing in logarithms, over rasters from 48 × 32 to 160 × 110 cells. That is the same fit, with the same five sizes, that produced the smooth-field orders of 1, 2 and 3 and the single-edge orders of 0.78, 0.58 and 0.60 — which is why the numbers are directly comparable, and it is the reason the family had to use five sizes rather than four.

That last point is not bookkeeping. The family was first measured with four grid sizes and the fitted orders moved by up to a third against the five-size fit. A fitted convergence order that depends on which grid sizes were used is itself evidence for this rung’s thesis, and it is not something two functions on one site should disagree about silently.

The smooth case, for contrast #

On an analytic field the orders are exactly what the textbooks say, and the fit recovers them to within 0.15. That is the case the published orders describe, and it is a real case: elevation models, gravity fields, interpolated climate surfaces and anything else that was smooth before it was sampled — including a geoid, whose own features are smoother than the gravity anomalies that produce them.

The distance between that figure and this essay’s first one is the whole subject. The orders are properties of the kernel and the field together, and quoting them without the field is quoting half of a measurement.

What a practitioner should take from it #

The three kernels are chosen from a menu in every piece of geospatial software, usually with a one-line description: nearest for categorical data, bilinear for continuous, cubic for smooth. This rung does not overturn that advice — it says what the advice is and is not based on.

For a categorical raster, nearest-neighbour remains right and the reason is not convergence. It is the overshoot: a smoothing kernel invents values that are in no class, and 11 per cent of the jump outside the data’s range is a class that does not exist. Reprojecting a raster invents values measures the same effect on a continuous field, where it is a rounding and not a category error.

For a continuous raster with edges in it, the choice is not decided by the orders, any more than a nearest-neighbour query is decided by the metric it is asked in. The three orders overlap across the family, so a table cannot rank them; what can be ranked is what each does at the edge, which is a matter of overshoot and of how far the influence of a discontinuity spreads.

And for anything where the answer matters, the orientation of the edges relative to the grid is a property of the data worth knowing. An aerial image of farmland with rectangular fields aligned to a survey grid is the aligned case; the same fields photographed from a satellite in a sun-synchronous orbit are not.

What the pixel’s own size does to this #

An edge is not the only thing in a raster that has no derivative. The pixel is a place with a size argues that a stored value is an average over an area rather than a sample at a point, and the two facts compound: a cell straddling a discontinuity holds a number that is neither of the two values, and no kernel can recover from that because the information was lost before the resampling started.

That sets a floor under everything in this essay. The measurements here use a field known exactly at every point — the discontinuity has no width and the cell values are point samples — so the errors reported are the resampling’s alone. A real raster arrives with the edge already smeared, and a kernel applied to it is smoothing something that has been smoothed.

Where the model stops #

The edges here have no noise and no point-spread function. A real raster has been through a sensor whose response is not a delta function and a compression that is not lossless, so its edges have a width. That width interacts with the cell size in a way none of this measures, and it is genuinely the next thing to measure rather than a caveat.

The test fields are synthetic, and deliberately. A measurement made on a real image would measure the sensor and the vendor’s processing as well as the kernel, which is the same argument that keeps coastlines out of this site’s area calculations.

Only three kernels appear. Lanczos, Mitchell–Netravali and the family of B-splines are all in use, they all smooth more or less than the cubic, and nothing here is claimed about them — except the one property that follows from the arithmetic: any kernel with negative lobes overshoots, and any kernel without them does not.

And the round trip is not what a pipeline does. A single reprojection has no reference to compare against, so the error is measured by going there and back — which counts the interpolation twice and is therefore an upper bound on a single warp’s error rather than an estimate of it.

What would change the answer #

Two extensions would move these numbers, and naming them separates what has been measured from what has been assumed.

The first is the width of a real edge. Every field here is exact and discontinuous, so the only smoothing is the resampling’s own. A sensor’s point-spread function gives a real edge a width of one or two cells before anything is resampled, and once an edge is wider than the kernel’s support the discontinuity stops being one: the field is locally smooth, and the orders should climb back towards 1, 2 and 3. Where the crossover sits — how many cells of blur it takes for a cubic kernel to recover its third order — is a measurement this collection has not made and could.

The second is the direction the resampling runs. Everything here reprojects into another projection and back, so each cell is sampled twice and the two samplings are inverses. A single warp, or a chain of several, would weight the errors differently, and a chain would compound the aligned case’s resonance in a way that a round trip cancels by construction.

The generalisation #

The result is an instance of something worth stating in general, because published tables of convergence orders exist in every numerical subject. A convergence order is an asymptotic statement about a family of problems, and it is meaningful only where the family is stated. The order of a quadrature depends on the smoothness of the integrand; the order of a finite-difference scheme depends on the solution’s regularity; the order of a resampling kernel depends on the field.

Where this case is unusually clean is the aligned edge, which produces a negative fitted order. That is not slow convergence and it is not noise. It is a resonance between the feature and the sampling lattice, and it is the same phenomenon that makes a picket fence photograph badly at some distances and well at others — the error depends on a relative phase that the refinement parameter changes unpredictably.

Who found it, and when #

The convergence orders of interpolation kernels on smooth data are nineteenth-century numerical analysis and are not in dispute. The behaviour across discontinuities is a standing topic in image processing — the overshoot of a kernel with negative lobes is Gibbs’ phenomenon under another name, and it has been known since 1898 — and the specific business of measuring an order across an edge is unusual, because there is no order there to measure and the literature mostly says so by not doing it.

What this collection contributes is the family: not that an order across an edge is ill-defined, which is expected, but by how much and in which direction it varies, and the fact that the ranking of the three kernels is not stable across orientations.

What a negative order does to an acceptance test #

The fitted orders are a finding about the kernels, and they are also a finding about how the kernels can be tested — which is the part a practitioner can act on today.

The obvious test is a convergence test, and it is the wrong one here. Halve the sampling interval, confirm the error fell is the standard acceptance check for a resampling path, it is correct on smooth data, and on an aligned edge it can fail on a correct implementation. A negative fitted order means refinement sometimes makes the error larger, so a test written that way will produce failures that no code change can fix and passes that no code change earned.

Worse, the outcome is not even stable under repetition. The error across an aligned edge depends on where the edge falls within a sampling cell, and refining the interval moves it within the cell in a way nothing about the refinement controls. Two resolutions that differ by nothing a reviewer would call meaningful can give errors differing by a factor of several, in either direction. A test suite built on this will be flaky, the flakiness will be blamed on the machine, and it will be quietly given a tolerance wide enough to catch nothing.

The test that does work is a bound over the sub-cell offset. Sweep the sub-pixel offset of the edge across one full lattice period — a few dozen offsets is enough — and take the worst error over the sweep. That number is stable, it is reproducible, it is the quantity a user actually experiences when a raster happens to land badly, and it is comparable between kernels in a way a fitted order across an edge is not.

The sweep also recovers something the order threw away. A kernel’s worst case and its typical case are different numbers, and on an aligned edge they are far apart; a single measurement at one arbitrary sub-cell offset reports one of them and cannot say which. That is the same distinction this collection draws whenever it reports a worst case rather than a mean, and the reason is the same each time: an extreme is a property of the method and an average is a property of the sample.

Where the ladder goes next #

This rung measures what resampling costs when the geometry is fixed. What it has not measured is the case a tilted screen produces, where the footprint of a screen pixel on the source raster is not a square but a long thin parallelogram whose orientation changes across the frame — a tilted view has no zoom level measures the anisotropy that creates, and the resampling that has to happen inside it is this essay’s family with a footprint that is itself the variable.