Halving a picture moves its centre by a quarter of a pixel

A pixel is not a point found that where the sample sits inside a pixel is a convention, and that getting it wrong moves every mark by half a pixel in each axis. The camera recovered from such a picture has a principal point 0.707 px off and its focal length is untouched, and nothing about the picture says so. That essay’s half pixel appears once and has a fixed size, and a program that gets its convention right gets it right everywhere.

The next place the convention bites is one where programs get it wrong as a matter of course, in writing a single line. A picture is calibrated at its full size. Then it is reduced, to feed a matcher or a network or to make a pyramid, and the camera has to go along with it. The obvious operation is to multiply. Scale the focal length by the factor and scale the principal point by the same factor. The first of those is right and the second is not, and the error is not half a pixel. It depends on the scale, and on a pyramid it comes back at each level as if nothing had been done about it.

Where an index goes #

An image’s pixels are areas. Under the convention that essay settled on, the pixel with index $i$ occupies the interval from $i$ to $i+1$ on a continuous axis, and its sample is at the middle, $i + \tfrac{1}{2}$. Scaling the picture by $s$ multiplies continuous coordinates by $s$, because the picture’s left edge stays at zero and its right edge moves. So a point at index $i$ on the old grid is at $i + \tfrac{1}{2}$ on the continuous axis, then at $s(i + \tfrac{1}{2})$, and then at index

$$i' = s\left(i + \tfrac{1}{2}\right) - \tfrac{1}{2}$$

on the new grid. The naive multiplication gives $si$. The difference is

$$s\,i - i' = \frac{1 - s}{2},$$

and it does not depend on $i$. Every point on the picture is off by the same amount: a quarter of a new pixel when halving, an eighth when reducing to three-quarters, in the same direction in both axes.

The drawing is the whole argument. Each block of two pixels becomes a new pixel whose middle stands halfway between them. Old index 0 is at the left of the first block and new index 0 is at its middle. The grid has an origin at the middle of its first pixel, and scaling the grid moves that middle away from where the old one was. Sampling conventions can be stated either way, with the first sample at zero or at half a pixel, but after a change of scale one of them has to be paid for, and this is where it is paid. Someone working with an edge-at-zero convention writes $s\,c$ and is right, in their convention. The trouble starts when the $c$ they multiply was reported in a centre-at-integer convention, which almost every calibration tool uses.

The picture knows the true map #

Nothing above has been measured yet, and the reader who suspects the convention argument of being a matter of definitions can ask the picture.

Take a camera with a stated principal point, photograph a box at some turn, and move the three vanishing points to the new grid with the true map. Recover the camera from those points. Recovering the camera gives the principal point as the orthocentre of the triangle. That recovery knows nothing of any convention.

Across scales of a half, a quarter, an eighth, three-quarters and double, the recovered centre agrees with the true map’s prediction to better than $10^{-8}$ of a pixel, the recovered focal length is exactly $s$ times the old one, and the naive principal point stands off by $0.250$, $0.375$, $0.438$, $0.125$ and $0.500$ px. So the answer is not arbitrary. If the marks are moved correctly, a recovery performed on them finds the true map’s centre. The multiplication is then not an alternative convention. It is an error, which the picture itself would report if it were ever asked.

It usually is not asked, because a recovery from three vanishing points read with half a pixel of error has a principal point uncertain by tens of pixels, and a quarter of a pixel is not going to show. The error lives entirely in the pipeline’s assumption about the camera, where nothing will catch it, and it costs precisely when that camera is trusted exactly, which a fitted camera usually is.

A pyramid does not forget #

Every level of an image pyramid halves the previous one. Reduce $k$ times, each correctly, and the true map from the original is the same formula with $s = 2^{-k}$. So the naive centre at level $k$ is out by

$$\frac{1}{2}\left(1 - 2^{-k}\right)$$

of that level’s pixels.

The tempting mental model is that coarser levels are less sensitive, so errors there do not matter. That has it backwards twice over. A quarter pixel at the first level becomes 0.375 at the second, 0.4375 at the third and 0.469 at the fourth, approaching half a pixel of whatever that level’s size is. Expressed in the original picture’s pixels, that is $(2^k - 1)/2$, doubling at every step, which at the fifth level is 15.5 of the original’s. And the things a pyramid is used for are exactly the things it hurts: a level’s features are matched to a fraction of that level’s pixel, so half of one is a large fraction. Sub-pixel accuracy of a tenth at a level means an error five times larger than the reading itself.

What does that do to a result? A principal point error turns a pose by the angle it subtends at the eye. At a focal length of 854 px, the level’s own focal length falls as the picture does. The error stays near half a pixel while its focal length halves, so the angle doubles at every level.

0.034° at level one, 0.101° at level two, 0.235° at level three, 0.503° at level four and 1.040° at level five. A coarse-to-fine estimator starts at the top of that list and works down. It may well recover, because each finer level corrects what the coarser level’s error began. But a pipeline that keeps coarse poses, a thumbnail index for instance, or a network that returns a pose from a small picture, keeps the half degree or the degree. A pose regression trained on thumbnails with naively scaled intrinsics has this as a systematic error in its training labels, and it will duly learn it. A learned model is especially good at hiding the fault, since it reproduces the same bias on its test set and reports no error against labels made the same way, and it fails only when moved to pictures reduced by a different route.

Scales that are not halves #

A pyramid is the case that makes the formula memorable, but the rule is general.

The sign is worth noticing. Reducing gives a negative error and enlarging a positive one. A double-size picture has its naive centre half a pixel low, and a triple-size one a full pixel low. Enlargements of this kind are common in training pipelines and super-resolution, and they are not bounded by a half pixel. They are, however, smaller in the original’s units, so the same physical offset is being expressed: it comes to at most half of one old pixel when enlarging. Reduction puts a pixel of bounded size on a growing physical length, and enlargement a growing number of smaller pixels on a bounded length. The arithmetic is one formula, and which way it looks depends on what unit the reader has in mind.

Two companion rules are common and need the same care. The first is mapping onto $W - 1$ rather than onto $W$, the convention usually called aligned corners, in which the first and last pixels of the row are forced to coincide across the two grids. A pixel is not a point measured that as a scale error rather than a shift, and it is a separate choice in the same family. Under it, the two grids’ scales do not even equal $s$ exactly. The second concerns rounding sizes: a row of 691 pixels halved is 345 or 346, and the scale is then $345/691$ or $346/691$ rather than a half. That small difference in scale between the axes has consequences of its own, and it leads straight on to the question at the end of this essay.

Crop and scale do not commute on a grid #

Pipelines do not only scale. They also crop, and a crop is a change of origin: remove $m$ columns from the left and the principal point’s column falls by exactly $m$, with no half-pixel involved, because a crop is a whole-pixel move on the grid it is taken from.

So the order of operations matters. Crop first and scale second, and the error stays at a quarter of a new pixel. Scale first and then crop 101/2 columns from the new grid, and there is no such crop. Fifty or fifty-one columns can be removed, and that is a further half of a new pixel beyond the first quarter, which adds to 0.75 px, a larger error than the whole family above. An augmentation pipeline that crops and scales in a random order has an error that varies from picture to picture, which is much harder to notice than a fixed one, because a fixed one could be absorbed into a calibration and a varying one can only be absorbed as noise.

The rule, in a form that survives copying #

Written against a centred-integer convention, as most calibration tools report:

$$f' = s f,\qquad c' = s\left(c + \tfrac{1}{2}\right) - \tfrac{1}{2}.$$

That is one line longer than the naive version, and it has a further useful property: applied twice it composes correctly, so a pyramid gets the right result level by level with no special casing. The naive version composes to itself, and that is why it looks so natural in code. It is internally consistent. It is just not consistent with the picture.

A program may instead work in the continuous convention throughout, in which the rule really is simple multiplication; it must then hand back principal points in that convention, and whatever reads them has to expect it. Both are honest. What goes wrong is a mixture, which is what happens when a calibration from one tool meets a resize from another, and no documentation of either says which it uses. A tile is an off-centre frustum shows the same bookkeeping in a renderer, where a tile’s own frustum has to be written in the full frame’s coordinates for its edges to meet its neighbours’ with no seam.

That essay found a seam would have been visible at once. Here nothing is visible. A resized picture looks fine, and so does its naively scaled camera, and they disagree by a quarter of a pixel in a direction that makes no visible pattern. It is an error of the kind the pixel that is not square measured from the other side, where an unmodelled camera is absorbed into a confident wrong answer and the residuals say nothing. And a rounded viewport is the same bookkeeping one step later, when the size itself has to be a whole number.

The test that finds it, on any pipeline #

Whichever convention a piece of software uses, nothing needs to be taken from its documentation. The answer is a measurement, and it is short.

Draw a single bright pixel on a dark picture at a known index, somewhere away from the edge. Reduce the picture by a half with the function in question. Read the bright patch’s position in the small picture as a centroid: sum of index times brightness, over the sum of brightness. A patch from a true area-preserving reduction lands at $\tfrac12(i + \tfrac12) - \tfrac12$, so an old index of 100 lands at 49.75, and the centroid says 49.75 to several decimal places. A keep-every-other reduction puts it at 50 or drops it altogether. An aligned-corners resize puts it at $100\,(w' - 1)/(w - 1)$, which on a 690-pixel row is 49.93. Those three answers are far enough apart to distinguish with a single dot and a line of arithmetic, whatever the row’s length.

Then the pipeline’s own camera can be checked against the answer: scale the principal point the way the program scales it, project the dot’s known direction with the scaled camera, and compare with the centroid. A disagreement of a quarter of a pixel is the error named here, and it can be found on a system whose source nobody has. This is the same idea recovering the camera rests on, with the picture as the authority and the arithmetic as what is being tested, and a test of this kind costs far less than the bias it finds.

It is worth running at more than one size, because a resize often changes behaviour with its scale. Some libraries use an area filter when reducing by large factors and a different filter close to one. Those have the same centre, if they are built correctly, but only a measurement says they are.

Keeping every second pixel changes the rule #

Everything here treats the resize as geometrically ideal: an area average or a filter centred on the true map, which is what a careful library does when it halves a picture. Some fast reductions simply keep every second pixel. That method picks up a shift of its own, because the sample it keeps is the old index $2j$, not the midpoint of the two. Its map is $i' = i/2$, and for that method the naive multiplication is right, and the picture really is displaced from the area-averaged one by a quarter of a new pixel. So the rule depends on the reducing filter. This is why it matters to know what is being used and why a small test on a known target can decide the question empirically: a pair of dots at known positions, reduced by the pipeline’s own function, read back with a centroid.

Rendering a resampled image carries a similar choice, and a texture does not interpolate on the page has more on what those filters do to a value. Nothing here touches the values; these numbers concern where each index stands.

No lens distortion is modelled, and for a distorted image the principal point is not the only thing that moves: a coefficient defined in pixels changes with the scale, though one defined in normalised coordinates does not. And the same half-pixel subtleties apply in depth maps and in any buffer whose values are read as positions, where the term is usually smaller only because reading precision is poorer.

Still open: what rounding the size does #

A picture of 1,000 by 562 reduced by a nominal 0.5 goes to 500 by 281, so the row scale and the column scale are 0.5 and 0.5, but a reduction by a nominal 0.75 goes to 750 by 422 (rounded from 421.5), a column scale of 0.75 and a row scale of 0.7509. That is two different focal lengths from a camera that had one, and the same thing happens in every renderer whose buffer has a whole number of pixels on each side. The difference is a tenth of a per cent at this size and more for a small picture.

The measurement that settles what it is worth takes every window size a renderer might be given at the usual display scales, with the aspect ratio computed from the requested size and the pixels from the rounded one, and reports how far the two focal lengths differ. Then it asks whether that falls with the picture’s size in a way that matters; how far it moves a mark at the frame’s edge, in pixels; and whether any single picture, read as well as a picture can be read, could see it.

A multiplication that composes with itself looks correct because it agrees with itself. The picture has a centre of its own, and it is at the point the true map says.