An edge has no order of convergence

Reprojecting a raster invents values measures three interpolation kernels by refining the grid and fitting the slope: nearest-neighbour converges at order 1, bilinear at 2, and Catmull–Rom at 3. Those are the theoretical orders and the measurement returns them to two decimal places, which is a satisfying result and was recorded at the time as a suspicious one:

kernelConvergence measures three kernels on an analytic field, and the orders come out at their theoretical values because there is nothing else in the signal. Real imagery has edges, which is where interpolation kernels differ most and where an order of convergence stops applying at all.

The note also said what would be needed: a test image with a known discontinuity, and a defensible definition of the error at it.

The test field, and why it is not a photograph #

The discontinuity has to be exact, or the measurement is partly about how the edge was made.

The field here is a step across a straight line tilted 27° to the graticule, with a gentle sinusoidal gradient on each side so that the two regions are not flat. It is known at every point, its jump has no width at all, and its position is a stated number rather than a property of a dataset.

That is the same reasoning that keeps coastlines out of computing an area needs a surface and photographs out of the smooth measurement. A real edge in a real raster has been through a sensor’s point-spread function and a compression, so a kernel measured on one is being measured against those as much as against the edge.

The tilt matters. An edge aligned with the grid is a special case that flatters every kernel, because the interpolation is then one-dimensional and the boundary passes through cell centres in a regular pattern. Twenty-seven degrees is a number with no small rational relationship to the grid.

What happens to the orders #

A convergence order is a statement about a Taylor expansion: a kernel reproduces polynomials up to some degree, so its error is governed by the first term it cannot reproduce, and refining the grid shrinks that term by a known power.

At a discontinuity there is no Taylor expansion. The error is concentrated in a band of cells straddling the edge; the band’s width shrinks as the grid refines, but the error inside it does not — a cell that straddles a step is wrong by a fixed fraction of the step however small the cell is. The result is a root-mean-square error that falls like the square root of the cell size, which is order 0.5, and every kernel is subject to it.

The measurement gives 0.78, 0.58 and 0.60 rather than a clean 0.5 for all three, and the departures are informative. Nearest-neighbour does better than the others because its error at the edge is a displacement of the step by up to half a cell rather than a smearing of it, and a displaced step has a smaller mean square error than a ramp of the same width.

So the ordering is not merely compressed. It is reversed at the top: the kernel that does no interpolating has the fastest convergence across an edge.

What each kernel does to a step, drawn #

The orders say the three kernels are nearly equal across an edge. What they do there is not equal at all.

The overshoot is a property of Catmull–Rom’s weights, two of which are negative. Those negative weights are what buy the third-order accuracy on a smooth field: a kernel with all-positive weights cannot reproduce a quadratic. The same weights, applied across a step, extrapolate — and extrapolation past a discontinuity produces values outside the data’s range.

That is a trade with no free side. Positive weights mean bounded output and low order; negative weights mean high order and unbounded output.

The case where the ranking is not merely weakened #

A land-cover raster’s values are class numbers: 3 is forest and 4 is water, and 3.5 is nothing. On such a raster the whole apparatus of convergence orders is beside the point, and the measurement makes that concrete.

The cubic kernel wins the error column and loses the question. That is the sharpest form of this site’s standing argument: a number that measures the wrong thing is worse than no number, because it comes with an ordering and the ordering is confident.

The practical rule every GIS manual states — use nearest-neighbour for categorical data — is usually given as a convention. It is a theorem: an averaging kernel returns values that were not in the input, and for categorical data every such value is an error whose magnitude is undefined.

Where the edge is, after the round trip #

There is a second failure at an edge that the error columns hide, and it belongs to the pixel rather than to the kernel.

A step that falls between two cell centres has to be assigned to one of them, and which one depends on where the target grid happens to sit. That is a quantisation, and it moves the boundary by up to half a cell in a direction that depends on position — so a reprojected class raster has a boundary that wanders by half a cell relative to the truth, with no kernel able to help.

Half a cell sounds negligible and is not, because it is systematic within a region: every cell along a stretch of boundary is displaced the same way, so an area computed from the resampled raster is biased rather than noisy. The bias is proportional to the boundary’s length times half a cell, which is the perimeter term the cells ladder’s query cost has in a different guise.

What was computed, and how #

The same machinery as the smooth measurement, with the field swapped. The warp goes into Lambert azimuthal equal-area and back to equirectangular, coordinates through the exact forward and inverse maps, and the error is measured on the grid the raster started on. Only the field differs, which is what makes the two tables comparable.

The error is split by distance from the edge. Within a band of 2° the RMS is the near-edge error; outside it the field is smooth and the theory applies. That split is the defensible definition the shortfall asked for, and it is a choice: a wider band includes more smooth ground and flatters the kernels, a narrower one is dominated by fewer cells.

Away from the edge the error falls through the arithmetic’s floor. At the finer grids the smooth part of the field is reproduced to the last bit, so the fitted order there is a slope through zeros and is not reported. An earlier version of the figure reported it, and gave the cubic kernel an order of eleven.

The class measurement uses a step with no gradient, so the field holds exactly two values and any third value is invented. With the gradient left in, every kernel returns thousands of distinct values and the test measures the gradient rather than the edge.

Why the band, and what it is sensitive to #

The split between near the edge and away from it is the one judgement call in the whole measurement, and it deserves to be exposed rather than buried in a parameter.

A band of 2° at these grid sizes is between three and seven cells wide, so it contains the cells the discontinuity touches plus a margin. Widening it to 5° pulls in smooth ground and pushes the near-edge orders up towards the smooth ones; narrowing it to half a degree leaves too few cells at the coarse grids for the fit to be stable.

None of the essay’s claims rest on the band, though, and that is the important part. The global orders — 0.78, 0.58 and 0.60 — are computed over the whole raster with no band at all, and they carry the collapse on their own. The band exists to show where the error lives, not to produce the headline.

The three refusals #

The smooth orders must still come out right. If the machinery returned 1.00, 1.98 and 2.93 on the smooth field and something else on the same field a week later, the comparison would be between two broken numbers. They are re-measured in the same run.

The edge orders must all fall below one. A kernel that kept its order across a discontinuity would mean the discontinuity was not one — a smoothed step, or an edge aligned with the grid.

The collapse must be a collapse. The three rates are required to lie within a factor of 1.5 of one another and the fastest is required to be nearest-neighbour. Either of those failing would mean the ranking had survived in some form, and the essay’s claim is that it does not.

What this changes about a reprojection #

Less than it sounds, and in a specific direction.

For continuous data — elevation, temperature, reflectance away from a coastline — the smooth measurement is the relevant one, the orders are real, and a higher-order kernel is worth having. Most of a satellite image is like this.

For data with edges, and for any decision made near an edge, the choice of kernel is close to irrelevant on accuracy and entirely relevant on what kind of wrong the answer is. Nearest-neighbour is wrong by displacing the boundary; bilinear is wrong by blurring it; the cubic kernel is wrong by inventing values on both sides of it.

And for categorical data the question does not arise: nearest-neighbour, always, and the reason is not accuracy.

The choice stops improving with resolution #

The collapse of the orders is stated as a fact about the ranking, and its sharper consequence is about refinement, which is the lever a practitioner actually has.

Where the three orders are 1, 2 and 3, refining the grid by ten multiplies the advantage of the cubic kernel over nearest-neighbour by 10² = 100. The choice of kernel gets more important the finer the raster, which is why a high-order kernel is worth implementing at all.

Across an edge the orders are 0.78, 0.58 and 0.60, so refining by ten changes the ratio between the best and the worst by 10^0.18 = 1.51. Refining by a hundred changes it by 2.3.

So the choice of kernel is very nearly resolution-independent at an edge, and the practical form of that is uncomfortable: buying a finer source raster does not make the kernel choice matter more, and it does not make a poor kernel choice cost less either. The two hundredths of an error that separate bilinear from the cubic at these grids are still there, in nearly the same proportion, on a raster ten times finer.

The absolute numbers say the same thing from the other side. On the two-class raster the errors are 0.0334, 0.0339 and 0.0251 — a spread of a third, on quantities that would differ by orders of magnitude on smooth data. Extrapolating the fitted rates, nearest-neighbour’s error and the cubic kernel’s would cross at a grid about five times coarser than the coarsest one measured, and would never cross again going finer.

That closes the argument the ranking opens. On smooth data the kernels are three genuinely different instruments and refinement separates them. Across an edge they are three instruments differing by a third, refinement barely separates them, and the reason to prefer one is entirely about what kind of wrong the answer is — a displaced step, a blurred one, or a step with values on either side of it that the data never held. None of those three descriptions has an error bar in it, and the error bar is the only thing refinement improves.

Where the model stops #

One edge, one orientation, one shape. A single straight discontinuity at 27°. Real imagery has curved edges, corners, and edges at every angle including the ones aligned with the grid, and the aligned case is genuinely better for every kernel. The measurement here is of a generic edge, and no distribution over orientations is attempted.

No noise. A real raster has sensor noise, and a high-order kernel amplifies it while a low-order one does not — which is a second argument against Catmull–Rom that this field cannot see, because the test field is exact.

The step is a full unit and the errors scale with it. An edge between two classes that differ slightly produces proportionally smaller errors, so the numbers here are for the worst case: a step of one against a field whose smooth part varies by a tenth.

Nothing here is about resampling along an edge. The kernels that address this problem properly — edge-directed interpolation, or simply resampling a vector boundary rather than a raster of it — are a different technique, and the honest statement is that the fix for an edge is usually not to have rasterised it yet.

Two kinds of resolution, and which one is binding #

An edge in a reprojected raster is limited by two things at once: how finely the source raster samples the world, and how finely the target grid can represent a position. Those are different quantities and either can be the binding one.

The practical form is that refining a target grid past the source’s resolution buys nothing but storage, and refining it not quite to the source’s resolution throws away detail that was paid for. Both are common, and the reason they are common is that the two resolutions are quoted in different units — one in degrees, one in metres — and comparing them requires the projection’s own scale factor at the latitude in question.

The same arithmetic says what would separate them, and it is not a better kernel. The three orders are all governed by the same square-root law — a band of cells whose width shrinks and whose error does not — so any kernel that operates on the raster after the edge has been sampled is inside it. Escaping requires the edge to have a width before the kernel sees it, which is what a sensor’s own point-spread function supplies and what a synthetic step deliberately removes. The order is a property of the field, so the only way to improve it is to change the field, and the two ways of doing that are to blur it or not to have rasterised it.

Who found it, and when #

The convergence orders are classical approximation theory: Catmull and Rom published their spline in 1974, and its third-order accuracy on smooth data with its overshoot at discontinuities was understood immediately, because it is the same Gibbs-like behaviour every interpolant with negative weights has.

The imaging literature has been arguing about it since: Keys’ 1981 analysis of cubic convolution gives the parameter family Catmull–Rom sits in and discusses the trade against ringing directly. The categorical rule reaches remote sensing textbooks by the mid-1980s, and it is generally stated as advice rather than derived.

What is unusual here is only that both measurements are made with the same code on the same rasters, so the collapse of the ranking is a single table rather than two literatures.

Where the ladder goes next #

This closes the last of the applied field’s recorded gaps: the resampling measurement now covers the case it was written to exclude.

What remains open is a different kind of question, and it belongs to the field that measures projections rather than data. The site has spent nine essays on the first derivative of a projection and three on the second, and both have been measured at points and over the whole sphere. Neither has been measured over a region, which is the only unit anybody chooses a projection for.