Synthetic image rendering systems can produce image descriptions that require the entire range of visible colors. Imaging hardware, however, can reproduce only a subset of these colors: the device gamut. An image can only be correctly displayed if all of its colors lie inside the gamut of the target device. The gamut varies from device to device. For example, most color CRTs can display cyans and yellows that cannot be printed, and many color printers can create blues and greens and that cannot be displayed on a CRT.

The solution to this problem is often to take the rendered picture and somehow distort it to fit the allowable colors for a given device. This approach has two drawbacks. First, typically an image is created on a CRT and tuned there, only to be printed when done. Such a process sacrifices all the colors that the printer makes available that the CRT lacks. Secondly, there is no way to adjust colors locally (say, pixel-by-pixel) and still preserve what we call the semantic integrity of the image. For example, if you change the color of pixels that look directly upon an object, you need to change the color of pixels that include a reflection of that object. But there's no way to identify or fix those pixels when all you have is colors and pixels.

Our insight was to realize that if you save the history of how each pixel was computed, then you have enough information to recalculate the image correctly using new colors for the lights and objects.

This was a joint project with Ken Fishkin, David Marimont, and Maureen Stone of Xerox PARC.

The heart of the method is to realize that when you compute an image, you have a lot of informaiton available that is not available when you have just a rectangular array of colors. When rendering, you know just how much each light source and each object is contributing to each pixel.

To start, we need to define color vectors. A color vector represents the spectral distribution of light at a variety of wavlengths. At a minimum, each color vector is a single value (for a grayscale image), but more typically they have 3 components (one each for red, green, and blue). More sophisticated renderers can support more detailed color descriptions. We will write such vectors in bold, e.g. V.

Consider a pixel which is looking at a slightly shiny ball. The ball is lit by a light source with color L. The ball itself is coated with paint that when illuminated with perfectly uniform white light, reflects a color C. Furthermore, at the particular angle which is seen by this pixel, the ball reflects a percentage a of the incident light specularly, and a percentage b diffusely. So the specular component is just the light source color scaled by the specular reflectivity, or aL. The diffuse component is the light source color modulated by the surface, and then scaled, giving bL C. The total color P at the pixel is then P = aL + bL C. This is the basic form of all pixel expressions; most have many more terms, but they're all just sums and products of colors and scalars.

We will assume that a and b are fixed, since changing them can drastically alter the image (imagine cranking up the specular component of a person's skin). However, we will be free to change the colors L and C. Our pixel expression above is a vector expression; if the colors are stored with three RGB components, then it's actually three scalar equations. For example, the red component would be Pr = a Lr + b Lr Cr, and similarly for green and blue. The heart of DDR is to realize that we can differentiate this expression with respect to Lr, which will then tell us how much Pr changes for each little change in Lr.

In DDR, we first render the image to get a vector expression for each pixel, which we then break down into scalar expressions. We differentiate each of these expressions for each of the pixel components, so that we can quickly plug in any desired change to the colors and immediately see the resulting change in the pixel values. Now we step back and look at the colors we have at the pixels, and check to see if everything is in (or close to) gamut. If the picture is in gamut, we're done. Otherwise, we create a target in-gamut picture by simply finding the nearest in-gamut color for each out-of-gamut pixel. This is just like local gamut mapping, except we don't actually use these colors for display. Instead, we pretend that this is the picture we want, and we find the difference between each current pixel component and the target component. That is, suppose pixel (3, 55) has color components (135, 265, -5), and we want to map to a color CRT that can display only in the range [0, 255] for each component; we would want to move that pixel by (0, -10, 5).

The goal is to find some change to the colors that will match the desired changes to the pixels. Of course, we can never get all the desired pixel changes, since the target picture has been mapped without regard to the underlying scene description. But it gives us a direction to move in order to get closer to the gamut. So we take all our differentiated pixel expressions and arrange them in a matrix: one row per pixel component, one column per color component. We can write this as a matrix formula dP=J dW, where dP is the column of changes to pixel components, W is the set of current color weights, and J is the matrix that tells us for each change to the weights, what change we get in the pixels. This matrix of partial differential equations is called the Jacobian. This equation is backwards; we know how much we want the pixels to move dP, and we want to find the changes in the scene colors dW to get those pixel changes. So we invert the matrix and write dW = J* dP, where J* is the pseudo-inverse of J (this is necessary because J is typically not square).

Given these changes dW, we alter the scene colors and try again, creating a new picture. If it's not in gamut, we project it to the gamut again, creating a new set of desired pixel changes dP, and compute a new set of scene-color changes.

In our experience, this process always converges, but frankly we don't have any ideas for how to prove it. The choice of target also influences the algorithm; one could argue that rather than computing a new target after each iteration, the target should be held fixed throughout the process. We address these issues in our TOG paper, referenced below under More Info.

This algorithm is discussed in detail in our paper "Device-Directed Rendering", which appears in ACM Transactions on Graphics. Here's the citation:

Glassner, Andrew S., Kenneth P. Fishkin, David H. Marimont, and Maureen C. Stone, "Device-Directed Rendering", ACM Transactions on Graphics, Vol. 14, No. 3, January 1995, pp. 58-76