A press makes the cheap route a search

A gamut charges a gradient nothing took the shortest path between two colours under ΔE₀₀ and held it inside sRGB. The held path was as short as the free one to within the relaxation’s own noise, on every gradient tried, including gradients whose free path was outside the display at fifteen of its twenty-one steps.

That essay credited the result to a property of the display. sRGB’s gamut is convex, so a path pushed back onto its boundary pays a cost that is second-order in how far it wanted to go: the boundary curves away from the path, and there is always a nearby way round. It ended by pointing at the solid where that is not true. A press’s gamut has dents — where one ink’s unwanted absorption pulls a hue inwards, and where the greens pinch between cyan and yellow — and a path pushed onto a concave boundary has to pick a side. The prediction was that the price would stop being nothing, and that the number to watch was the worst gradient, not the mean.

The price does not appear. Something else does.

Cheap at best, and hard to find #

On ten gradients whose straight line leaves a coated CMYK press, the best of six held routes costs a median of 0.12 per cent over the free shortest path, and at most 1.1 per cent. The same six starts on the display’s gradients find a median of 0.22 and at most 1.3. At best, the press charges what the display charges.

• The best route depends on the start. The relaxation started from the free path itself was the best of the six on one gradient of ten. Started from there it lands at a median of 3.6 per cent, and at worst at 220.
• On five of the ten crossing gradients some start is trapped at more than twice the free length or cannot be held inside. On the three display gradients and on six press gradients whose straight line stays inside, none is.
• The press’s straight-line exits cluster in the greens. 216 of the 630 lines between colours on its hue ring leave the gamut somewhere; the 26 that leave by more than one and a half CIELAB units nearly all run between colours containing yellow, and the worst leaves by 7.5.
• The free shortest path is not unique. On most crossing gradients a free path relaxed from the straight line runs outside the press, and another, relaxed from the best held route, runs inside at the same length to within about half a per cent.

A press as something a relaxation can be pushed by #

The display essay held a path inside sRGB with a penalty: the squared distance each point sits outside the unit cube in linear RGB, added to the path’s length and weighted heavily. A press has no cube. Neither gamut contains the other measured a press’s gamut, and it measured it the only honest way for a solid with dents: as the set of CIELAB cells the press can reach, here at one unit a cell, over every separation of cyan, magenta, yellow and black within an ink limit of 320 per cent. A convex hull would fill in the dents, and the dents are the point.

A voxel set says inside or outside, which gives a relaxation nothing to push against. So the set becomes a distance field: every cell outside the press gets its Euclidean distance to the nearest cell inside, computed exactly by three one-dimensional passes, and a colour’s distance outside is read from the field by trilinear interpolation. That distance, squared and weighted, is the penalty.

The gradients run between colours the press can print at its own boundary: two inks at full strength in steps of a quarter, around the hue ring, with and without half black. That is thirty-six colours and 630 straight lines between them.

The measurement differs from the display essay’s in one deliberate way. Every held path is relaxed from six starts rather than one: the straight line in CIELAB, the free shortest path, and the straight line bent eight units towards the neutral axis, away from it, up in lightness and down. A third space breaks the tie only once found a geodesic that two agreeing starts had both missed, and a single start cannot tell a price from a place where the relaxation got stuck.

Where the press is not convex #

216 of the 630 lines leave the press somewhere. In a convex solid none could: the straight segment between two points of a convex set lies inside it, by definition. Most of these leave by less than a CIELAB unit, which is the resolution of the gamut itself. That is not nothing, but it is not a concavity a gradient would notice either.

The 26 that leave by more than a unit and a half nearly all join colours with yellow in them, running through the greens, and the worst is the gradient from full yellow to full yellow plus full cyan, whose straight line is outside the press at 19 of its 21 points and by as much as 7.5 units. That is the pinch the display essay predicted, and it is a place most of this diagram cannot be shown would mark: greens a display shows and a page cannot. Cyan and yellow each reflect strongly across a wide band, and the green they make together has lost reflectance at both ends of the spectrum. The straight line in CIELAB between a yellow and a green cuts the corner of a boundary that bows inwards between them.

The ten gradients that leave by most are the census. Six gradients whose straight line never leaves, chosen across the ring, are the control.

Six starts, one gradient at a time #

The figure above is the whole census in one picture: a row per gradient, a dot per start, each dot at how much longer that start’s held route is than the free shortest path.

On the six control rows the dots sit at the left: five of the six starts on every row land within two per cent of the free length, and the worst single start on any of them, a bend away from the neutral axis, lands at 5.2. The three display rows spread to 4.2 per cent between their best and worst starts. No start on any of those nine rows is trapped, and the best on each display row costs at most 1.3 per cent.

The ten crossing rows are different in kind. On each, the best start costs little: a median of 0.12 per cent, at most 1.1. But on five of them one or more starts land to the far right, at more than twice the free length, or end still outside the press. On those five the starts run from a tenth of a per cent to more than a hundred. And which start wins changes: the bend towards the neutral axis on seven, and darker, lighter and the free path itself on one each.

The start that looks natural wins least. A program holding a gradient inside a gamut would start from the free shortest path, because that is the answer it is trying to preserve. Started there, the held route costs a median of 3.6 per cent and at worst 220 — on the one gradient of ten where the free path was the best start, it cost 0.11.

What a trapped start looks like #

The clearest single case is the gradient the ring figure picked out as the worst exit.

The free shortest path from yellow to green is outside the press at 18 of its 21 points, by as much as 4.7 units. Held inside from that path, the relaxation finds a route 3.6 per cent longer. Held inside from the straight line bent downwards in lightness, it finds one 1.1 per cent longer.

The two held routes are both inside and both local minima: no small change to either shortens it without leaving the press. They pass through different colours, and a start that begins on one side of the pinch settles on that side. A start already sitting in the cheaper valley stays there.

The display cannot produce this. A convex boundary is always curving away from a path pushed against it, so the path slides along it towards wherever it was going. A concave boundary curves towards the path, the nearest inside point can be in the wrong direction, and a path pushed there has committed to a side.

A start trapped at three times the length #

This gradient’s free path, relaxed from the straight line, is outside at 18 points but never by more than 2.0 units. Held from that path, the relaxation ends 220 per cent longer, at more than three times the length. From the bend towards the neutral axis it ends a hundredth of a per cent longer — indistinguishable from free.

The trap belongs to the penalty, and the press’s shape is what springs it. Every point of the starting path is a little outside and pays for it. On a convex solid each point can stop paying by moving a little inwards, and its neighbours move the same way. Round a pinch, the likely reason is that neighbouring points’ nearest inside colours lie in different directions, so moving them in pulls the path apart, and the relaxation stops paying only by taking a detour 64 units away from the free path, through darker colours that are inside everywhere. Every step lowered the total cost, and the cost it settled at is a path three times as long as it needed to be.

A gradient-drawing tool holding colours inside a press by this method, started from the natural place, would draw that detour — a worse result than either answer no mapping preserves everything offers, since both of those keep the colours that were already printable where they were. Nothing about the free path warned of it: its worst excursion was two units, less than several gradients whose held routes cost under one per cent.

The dark side of the ring #

The pattern is not confined to full-strength colours. From full green to a yellow darkened with half black, the free path is outside at 18 points by up to 2.8 units; held from it, the route costs 4.1 per cent, and from the bend towards the neutral axis 0.69. Half black moves one end down the lightness axis, where the ink limit starts to bind, so the same pinch is met at a different lightness and the gradient still crosses it. Black adds no chroma boundary at these lightnesses — the fourth ink is not for colour found that — so it cannot widen the pinch, only move where the gradient meets it.

What the press charges, set beside the display #

At best the press charges a median of 0.12 per cent and at most 1.1; sRGB a median of 0.22 and at most 1.3. On the display essay’s own terms the prediction fails: a non-convex gamut does not make the cheapest in-gamut route expensive.

What it changes is the search. Five of ten crossing press gradients trapped a start, against none of three display gradients and none of six press gradients that stay inside. On the display, any reasonable start finds a route within a few per cent of the best. On the press, the start decides whether the route costs a tenth of a per cent or three times the length.

The display essay’s closing test — whether a gamut that charges nothing for most gradients and a great deal for the ones crossing its concavity justifies routing without a check — has an answer, but not the one it expected. The press charges nothing at best on every gradient here. It justifies routing only with a search: several starts, the shortest held result kept, and a warning when the starts disagree. A single relaxation from the free path is the one arrangement that fails.

The free path was never unique #

One more finding came out of the six starts, and it makes the others less surprising.

The free shortest path was found twice for every gradient: relaxed from the straight line, and relaxed again from the best held route. On most crossing gradients the first runs outside the press and the second runs inside, and the two differ in length by about half a per cent or less. On five of the ten the second is inside at every point.

So the free shortest path under ΔE₀₀ on these gradients is not a single curve. A family of paths runs through quite different colours at almost the same length, and some members are printable and some are not. The display essay’s result, that holding a path inside costs nothing, is partly this: in a direction where the metric is flat, a path can move a long way for nothing. The straight line is not the shortest gradient found how little the shortest path saved over the straight line on some gradients, which is the same flatness seen from the other side.

It also explains why the start matters so much. A relaxation settles in whichever member of the family it reaches first, and on a press some members are reached by crossing a concavity and some are not.

How the census was run #

The press is the collection’s coated CMYK model — ink transmittances over a coated paper, combined by the Demichel equations with dot gain and read under D50 — sampled at thirteen steps per chromatic ink and nine of black, with an ink limit of 320 per cent and at most three chromatic inks at once, and marked into one-unit CIELAB cells with the segments between lattice neighbours filled. The distance field is the exact Euclidean distance transform of that cell set; a colour’s distance outside is the trilinear interpolation of cell-centre distances less half a cell, floored at zero.

Paths are twenty segments, and lengths are ΔE₀₀’s local metric as in the display essay. A held path minimises its length plus 400 times the sum of its points’ squared distances outside, by the same backtracking gradient descent, from each of the six starts. The free path is relaxed from the straight line and again from the best held route, and the shorter is the reference every excess is measured against. A start counts as trapped when its held route is more than twice the free length or still more than a quarter of a unit outside.

The display control uses the display essay’s red to green, red to blue and blue to yellow, with its own penalty in linear RGB and the same six starts. The press control is six ring pairs whose straight line is inside at every point, spread around the ring.

What this leaves out #

The penalty method is one way to hold a path inside a gamut. A projection method — move each point to the nearest inside colour after every step — or a barrier that never lets a point leave would have different traps, and possibly none. The finding is about the search the obvious method needs, and it is the obvious method.

Ten gradients from one hue ring are a census of the worst exits, not of gradients in general. They were chosen because they leave the press; a random pair of press colours usually does not. The control shows that pairs which stay inside behave like the display.

The press is a model, and a real press’s concavities come from its own inks and its own dot gain. A measured profile would place the pinch differently and would have its own. What would not change is that a profile’s gamut is not convex, which what a gamut costs is the collection’s other measurement of.

And the voxel cell is one unit, so boundary excursions of under a unit are at the resolution of the gamut. Most of the 216 exits are at that resolution; the 26 the census is drawn from are not.

Still open: whether a cheaper search suffices #

Six relaxations per gradient cost six times as much as one, and a drawing program adjusting a gradient interactively cannot spend that on every stop.

The obvious cheap test does not work. Trapped routes on the census end between 20 and 64 CIELAB units from the free path, and good ones up to 33, so no single distance from the free path separates them. A check on the result’s length would work, since every trapped route is more than twice the free length, but only after the relaxation has already run.

The better candidate is a different method rather than a check. A projection — take a free step, then move each point to its nearest inside colour — never lets the path pay for being outside, so the incentive that drives the detours does not exist. Whether it has traps of its own round a pinch, where the nearest inside colours for neighbouring points diverge, is the census here run with projection in place of the penalty. The prediction is fewer traps and a best route no cheaper, since the best routes here are already within a tenth of a per cent of free.

A cheap answer can be hard to find #

The habit is about what a measured price means when the measurement is an optimisation.

A minimum found by a search is a claim about the search as much as about the problem. When the search always finds the same minimum from any reasonable start, reporting its value reports the problem. When it does not, the value depends on where the search began.

The move is to report the spread of starts beside the best result. Here the best result alone said the press behaves like the display, and the spread said it does not. A tool that runs one relaxation gets one draw from that spread.

The failure mode is to start from the answer being preserved. The free path is where a held route would naturally start, and it was the best start on one gradient of ten.