Source Code Documentation

Some general comments about how different software works.

TARGET

 Nearly all current Color correction systems generate test charts (or device characterization target charts) by laying out a regular rectangular grid of test points in device space (Targen will do this if you feed it a non-zero -m option). On some consideration, this approach is far from optimal. Not only is a regular grid inefficient in packing the multidimensional device space but if the points are spaced evenly in device space, they will probably not be optimal in determining the underlying device characteristic, sampling too finely where the device behavior is smooth, and too coarsely where the device behavior changes rapidly. Some commercial color systems tackle the latter problem by "pre-linearizing" the device, which amounts to distorting the regular device space grid points with a perceptual inverse per device channel lookup curve.

The approach I have taken with Argyll, is a little different. Both a device independent and device dependent approach are available. In the device independent mode, test points are distributed so as to minimize the distance from any point in the device space to the nearest test chart value. When the device dependent approach is used, test points are chosen so as to minimize the expected error between the resulting profile and the underlying device response.

For higher dimensional spaces, where the aim is to create a more approximate device profile, I've used an "incremental far point" point generator, that starting with a previous test point as a seed, use a minimization algorithm to locate another point that is as far as possible from the nearest existing test point in perceptual space, while remaining in gamut at all tines. This means that ideally each point "fills in" the gaps in the existing distribution.

Another issue with laying test points out in regular grids, is that this means that the device response is poorly sampled (since the grids are usually coarse), and this can make it impossible to create detailed device linearisation "shaper" curves from the resulting data ! Ideally, in any colorspace (input or output), when viewed from any possible angle, none of the test data points should appear  to line up. The Argyll target generator seems to achieve this goal.


target/printtarg.c:

printtarg simply generates a PostScript file containing the patches laid out for an Xrite DTP51/DTP41/SpectroScan. It allows them to be laid out on a choice of paper sizes, with the appropriate contrasting color spacers between each patch for the strip reading instruments. Unlike other charts, Argyll charts are generated as required, rather that being fixed. Also unlike most other strip reading charts, the spacers may colored, so that the density contrast ratio is guaranteed, even when two patches are about 50% density.

Another feature is the pseudo random patch layout. This has three purposes. One is to try and average out any variation in the device response in relationship to the location of the patch on the paper. Color copiers and printing presses (for instance), are notorious in having side to side density variations.

Another purpose of the random patch layout, is that it gives the reading program a good mechanism for detecting user error. It can guess the expected values, compare them to the readings, and complain if it seems that the strip is probably the wrong one.

The final purpose of the random patch layout is to optimize the contrast between patches in a strip, to improve the robustness of the strip reading. Using this, small charts may be even be generated without any gaps between the test patches.

RSPL

A lot of core Argyll algorithms are bound up in the RSPL (Regular Spline) class. The RSPL class is closely related to the CLUT table structure used in the ICC profile format, and is a general purpose way of mapping one multi-dimensional value to another, using interpolation to reduce the mapping function to a manageable size.
Regular splines are not directly related to other types of splines, and do not generally suffer from the sort of "wiggles" and "overshoot" characteristic of other spline systems.

The RSPL class adds three basic methods to the underlying data structure:

1) Interpolation

2) Creation from scattered data

The regular spline implementation was inspired by the following technical reports:

D.J. Bone, "Adaptive Multi-Dimensional Interpolation Using Regularized Linear Splines," Proc. SPIE Vol. 1902, p.243-253, Nonlinear Image Processing IV, Edward R. Dougherty; Jaakko T. Astola; Harold G. Longbotham;(Eds)(1993).

D.J. Bone, "Adaptive Colour Printer Modeling using regularized linear splines," Proc. SPIE Vol. 1909, p. 104-115, Device-Independent Color Imaging and Imaging Systems Integration, Ricardo J. Motta; Hapet A. Berberian; Eds.(1993)

Don Bone and Duncan Stevenson, "Modelling of Colour Hard Copy Devices Using Regularised Linear Splines," Proceedings of the APRS workshop on Colour Imaging and Applications, Canberra (1994)

see <http://www.cmis.csiro.au/Don.Bone/>

Also of interest was:

"Discrete Smooth Interpolation", Jean-Laurent Mallet, ACM Transactions on Graphics, Volume 8, Number 2, April 1989, Pages 121-144.

3) Inversion

Simplex interpolation is normally done in Baricentric space, where there is one more baricentric coordinate than dimensions, and the sum of all the baricentric coordinates must be 1.
To simplify things, we work in a "Simplex parameter" space, in which there are only <dimension> parameters, and each directly corresponds with a cartesian coordinate, but the parameter order corresponds with the baricentric order.
For example, given cartesian coordinates D0, D1, D2 these should be sorted from smallest to largest, thereby choosing a particular simplex within a cube, and allowing a correspondence to the parameter coordinates, ie:

D1 D0 D2     Smallest -> Largest cartesian sort
P2 P1 P0     Corresponding Parameter coordinates (note reverse order!)

B0 = P0      Conversion to Baricentric coordinates
B1 = P1 - P0
B2 = P2 - P1
B3 = 1  - P2

The vertex values directly correspond to Baricentric coordinates,
giving the usual interpolation equation of:

  VV0 * B0
+ VV1 * B1
+ VV2 * B2
+ VV3 * B3

where VVn is the vertex value for each of the 4 vertices of the simplex.

Reversing the Parameter -> Baricentric equations gives the
following interpolation equation using Parameter coordinates:

  VV0 - VV1 * P0
+ VV1 - VV2 * P1
+ VV2 - VV3 * P2
+ VV3

It is this which is used in rev.c for solving the reverse interpolation problem. Within a simplex, only linear algebra is needed to compute inverses. To deal with the 4D->3D nature of a CMYK profile, the SVD (Singular Value Decomposition) approach is used to solving a CMYK for a given CIE value, the result being the equation of the line of solutions. The lines from adjacent simplexes form a solution locus, that can be resolved into a single point solution once a black generation rule is applied.

Outline of inversion processing:

     Basic function requirements:  exact, auxil, locus, clip inversion.
     Fwd cell - reverse cell list lookup
     Basic layout di -> fdi + auxils + ink limit
     Basic search strategy
     Sub Simplex decomposition & properties
     How each type of function finds solutions
       Sub-simplex dimensionality & dof + target dim & dof
       Linear algebra choices.
     How final solutions are chosen

XICC

    Profiling using concatenated shapers to augment thin plate splines for per channel curves.

IMDI

This module generates C code routines which implement an integer multi-channel transform. The input values are read, passed through per channel lookup tables, a multi-dimensional interpolation table, and then a per channel output lookup table, before being written.

MPP
Outline model parameter optimization using slope accelerated error metric, and initial parameter speedup for adjacent spectral bands etc.