Implementation Note 2: Approximating a Smooth Three-Dimensional Function on a Coarse Lattice

• For RGB-to-CMYK conversion, each inverse lookup can require iterative searches through a forward printer model, making per-pixel evaluation too slow for large images.Source: §2 · p. 1
• A full-resolution 8-bit RGB-to-CMYK table requires 64 MiB, which is impractical for typical flash memory sizes described in the paper.Source: §2 · p. 1
• The objective is to store a smooth three-input function at few points and cheaply reconstruct other values with low error.Source: §2 · p. 1

3 The lattice

• The lattice has n+1 nodes per axis, including the boundary, and each node stores Θ(k) outputs, such as four values for CMYK.Source: §3 · p. 2
• The table is computed once offline and contains (n + 1)^3 · k values, so its memory requirement grows cubically with n.Source: §3 · p. 2
• 16-bit node values limit inherited rounding error to at most 0.00076 % ink, versus up to 0.2 % ink for 8-bit values.Source: §3 · p. 2
• Sixteen-bit values are common in ICC profiles, while the integer method requires values below 2^16 so its weighted sum fits in 32 bits.Source: §3 · p. 2
• ICC profiles typically use 17 or 33 nodes per axis, corresponding to n = 16 or n = 32; a full 8-bit table stores every input and needs no interpolation.Source: §3 · p. 2

4 Tetrahedral interpolation

• Each cube is split into six tetrahedra sharing the diagonal from corner 000 to corner 111.Source: §4 · p. 2, Figure 1 · p. 3

4.1 Step 1: cube index and fractions

• The three input coordinates are scaled to grid units; their integer parts identify the cell and their remainders give the within-cell fractions.Source: §4.1 · pp. 2–3

4.2 Step 2: tetrahedron selection

• Sorting the three fractions in descending order selects the tetrahedron, with successive path steps along the axes of largest, middle, and smallest fractions.Source: §4.2 · p. 3

4.3 Step 3: weighted sum of the 4 corners

• The four path corners are combined using weights (1−t1), (t1−t2), (t2−t3), and t3, which are non-negative and sum to one.Source: §4.3 · pp. 3–4

4.4 Properties

• Tetrahedral interpolation uses 4 table reads and 3 multiplications per output channel, compared with 8 reads and 7 multiplications for trilinear interpolation.Source: §4.4 · p. 4
• Adjacent tetrahedra share faces, so the interpolation remains continuous across tetrahedron and cell boundaries.Source: §4.4 · p. 4
• If the function is linear inside a tetrahedron, interpolation is exact; for neutral colors, only the two diagonal corners have non-zero weights.Source: §4.4 · p. 4

5 Worked example: RGB to CMYK Color Conversion

• For the illustrative RGB input (200, 120, 60), using n = 16 (17 nodes per axis), the resulting CMYK value is (0, 40.06, 70.04, 21.57) %, compared with the exact value (0, 40.00, 70.00, 21.57) %.Source: §5 · p. 4

5.1 Excursion: why closed color conversion formulae don't exist in practice

• Real printer RGB-to-CMYK conversion lacks a closed formula because printer behavior and production settings shape the mapping and its inverse.Source: §5.1 · p. 4

5.2 Test function

• The test uses an ideal-printer textbook formula because its exact values are known; the method for real profiles is identical, with different table values.Source: §5.2 · p. 5

5.3 Step 1: fractions

• The example input is normalized to [0, 1] and multiplied by n = 16 before locating its cell and fractions.Source: §5.3 · p. 5

5.4 Step 2: tetrahedron

• Because tb > tr ≥ tg, the example’s tetrahedron path is 000 → 001 → 101 → 111, stepping first along B, then R, then G.Source: §5.4 · p. 5

5.5 Step 3: corners and weights

• The four corner values are combined with weights summing to 1; the example’s magenta output is 40.06 %.Source: §5.5 · p. 5

5.6 Result

• The tetrahedral result deviates from the exact value by at most 0.06 % ink; trilinear interpolation is slightly less accurate and requires twice as many table reads.Source: §5.6 · p. 5

6 Integer arithmetic for 8-bit input

• The lookup uses integer arithmetic without division, reusing cell indices, tetrahedron choice, and weights across all output channels.All intermediate values fit in unsigned 32-bit integers on the stated assumptions.Source: §6 · p. 6, §6.2 · p. 6

6.1 Step 1: cell index and fraction

• Each input channel yields a cell index and a fraction rounded to 16-bit units; n must be a power of two no greater than 128.For R = 200 and n = 16, the rounded fraction is 0.54903 versus the exact 0.54902.Source: §6.1 · p. 6

6.2 Steps 2 and 3: tetrahedron and weights

• Sorted fractions select a tetrahedral path through four nodes, whose values are combined with integer weights summing to 65536.The same indices, tetrahedron, and weights serve every output channel; only four table reads and the weighted sum repeat.Source: §6.2 · p. 6

6.3 Correctness

• For power-of-two n ≤ 128, the position formula is exactly rounded; endpoint inputs map to stored nodes, reproducing white and black exactly.The exact-position claim is also confirmed exhaustively for all 256 channel values and supported table sizes.Source: §6.3 · p. 7
• At n = 16, integer lookup differs from exact-fraction tetrahedral interpolation by at most 1 LSB (0.0015% ink), with a mean difference of 0.36 LSB.The bound applies over all 2^24 inputs; the mean interpolation error is much larger.Source: §6.3 · p. 7

6.4 Fraction width and position error

• The 16-bit fraction position is within 1/131072 of a cell; using 8 fraction bits increases this bound to 1/512, a factor of 256.The position error propagates through interpolation along each axis, with the overall 16-bit lookup error bounded separately above.Source: §6.4 · p. 7
• With 8 fraction bits, measured change reaches 104 LSB and averages 9.4 LSB for n = 16 inputs with a maximum channel value of at least 10%; 16 bits are used instead.The measured changes are 0.16% and 0.014% ink, versus mean interpolation error of 0.08%; 16-bit fractions cost one multiplication by 257, or a shift and addition, per input channel.Source: §6.4 · p. 7
• For n = 16, the high-nibble shortcut misplaces R = 200 at fraction 0.5 instead of 0.549 and can give white a visible 0.39% K tint.Adding the rounded correction reaches node 16 at R = 255, at higher operation cost than the shortcut.Source: §6.4 · pp. 7–8

7 Implementation

• The code provides floating-point lookup and integer lookup for 8-bit input, with the latter requiring power-of-two n ≤ 128.For RGB-to-CMYK, K = 4; the generic output-channel parameter supports other 3D functions, and the table is built offline for subsequent device lookups.Source: §7 · pp. 8–9
• The generic implementation builds a 3D table by sampling the function at lattice nodes and quantizing each output to 16-bit values.The table includes nodes at 1.0 so edge inputs have stored values.Source: §7 · p. 8
• The worked n = 16 example uses 17^3 nodes and reports lookup output of [0, 26252, 45897, 14135] for RGB [200, 120, 60].The values correspond to approximately 40.06%, 70.03%, and 21.57% for the nonzero CMYK channels.Source: §7 · pp. 10–11
• The integer lookup’s largest deviation is 1 LSB when checked over all 2^24 inputs against exact-fraction double-precision interpolation on the same table.The implementation notes recommend integer arithmetic per pixel, with floating point needed only to build the table.Source: §7 · p. 11

8 Error analysis

• The interpolation error inside a tetrahedron is bounded by 3 8Mh2, where M is the largest curvature of f in the cell.Other error sources are negligible or limited to the region near black.Source: §8 · p. 11

8.1 Error sources

• With 16-bit node values, table quantization adds at most 0.00076 % ink, below 1 % of the mean interpolation error at n = 16.Fraction rounding adds at most 0.5 LSB per axis, and final output rounding adds at most 0.5 LSB.Source: §8.1 · p. 11
• At n = 16, the mean interpolation error is 0.08 % ink, over 50 times the largest integer deviation; the two integer sources add at most 1 LSB.Their average combined deviation is 0.36 LSB.Source: §8.1 · p. 11

8.2 Theoretical bound

• If f is linear in a cell, tetrahedral interpolation reproduces it exactly, so the approximation error is caused by curvature.Constant functions are also reproduced exactly because the weights sum to 1.Source: §8.2 · p. 12
• The bound is zero at lattice nodes, and interpolation is also exact along a cube’s main diagonal when f is linear along it.For RGB to CMYK, this diagonal is the neutral axis.Source: §8.2 · p. 12
• The error bound scales with h2 = 1/n2: halving cell width reduces error by a factor of 4 while increasing memory by a factor of 8.The measured slope of −2.01 confirms this scaling.Source: §8.2 · p. 12
• For the test function, error concentrates near black because its C, M, and Y channels are discontinuous there.The bound depends on the cell’s largest curvature, not the size of f itself.Source: §8.1 · p. 11, §8.2 · p. 12

9 Experimental analysis

• At n = 16, mean error is 0.08 % ink and 99th-percentile error is 0.75 % ink; tetrahedral interpolation has less than half trilinear interpolation’s mean error.The measurements use inputs with a maximum channel value of at least 10 %.Source: §9 · p. 12

9.1 Setup

• The experiment uses 20,000 uniformly random RGB points, compares against trilinear interpolation on the same table, and reports mean and 99th-percentile worst-channel error.It tests grid sizes n = 2, 4, 8, 16, 32, and 64; points below 10% maximum channel are excluded except in Section 9.4.Source: §9.1 · pp. 12–13

9.2 Convergence

• For n = 8 to 64, fitted slopes are −2.01 and −2.07 for tetrahedral mean and 99th-percentile error, versus −1.88 and −1.50 for trilinear error.The slower decrease in trilinear 99th-percentile error is consistent with its cells combining values across nondifferentiable kink planes.Source: §9.2 · p. 13

9.3 Error inside the cells

• Both methods are exact on node planes; between them, tetrahedral error changes sign and stays below 0.08 % ink, while trilinear error reaches 0.31 % ink.The reported tetrahedral maximum is four times lower than the trilinear maximum.Source: §9.3 · p. 13
• In the B = 0.25 plane, error reaches 0.33 % ink at (R, G) = (0.500, 0.531) and, by symmetry, at (0.531, 0.500).Error is zero along lines where the largest channel is at a node value, and increases toward lower R and G between those lines.Source: §9.3 · p. 13, Figure 4 · p. 14

9.4 Error by brightness

• The mean error in the darkest brightness bin is about 200 times the mean in the brightest bin.The test formula is discontinuous at black, while real profiles are continuous but have highest curvature in shadows.Source: §9.4 · p. 13, Figure 5 · p. 14

9.5 Choice of n

• n = 16 is a suitable default; n = 32 is used when 99th-percentile error matters, while above n = 32 accuracy gains are small relative to memory cost.Each doubling of n reduces error by a factor of 4 and increases memory by a factor of 8.Source: §9.5 · p. 15