Gamut Mapping for Electronic Devices

Abstract

This paper starts with comparing a pervious known gamut mapping approaches. It tries to address the need of having applicable gamut mapping algorithms, meaning a method that requires a reasonable amount of data and is comparably fast. All the past methods ask for huge amount of data in order to detect an out of gamut color and correct the ones. There are works done to preserve spatial luminance variation of image. In this paper, a general survey of some of the most known approaches are given and then two methods are introduced to improve both point-wise and spatial gamut mapping algorithms. The given methods try to use the idea that gamuts of different devices, especially CRT and LCD monitors plus LCD and DLP projectors are similar to each other in terms of geometric shape.

 Introduction

The gamut is the range of color that a given device can produce. For an image, the color gamut is simply the set of all the colors found in it. Gamut mapping means re-defining the colors of a given device so that its gamut becomes (approximately) identical to that of a second device.[[i]] Gamut mapping is an important problem in color management, and has been one of the most active areas of research in the Color Imaging Conference series. The optimal gamut mapping approach for a given case

depends on input and output device gamuts, image content, user intent and preference. Most gamut mapping strategy based their work on the assumption that the design of the optimal technique involves combination of image attributes such as contrast, luminance detail, vividness, and smoothness and thus they avoid to come up with a general approach that suits most applications. Excellent overviews and references to work in this area can be found in [[ii]] and [[iii]].

Gamut mapping algorithms can be classified into three different methods based on how they use image content heuristics [[iv]]. The first category is solely device dependent, where gamut mapping is a function of input device and output gamut and is independent of image content. The majority of well-known gamut mapping algorithms fall in this category.

The second category consists of image dependent algorithms; where in the gamut mapping is a function of the input image statistics, and the output device gamut. These algorithms expected to perform better since they include image content [3 ].

In both these approaches the gamut mapping is a point-wise operation from an input point to an output point in an appropriate (usually perceptual) 3D color space. One of the fundamental problems with such point-wise operations is that they do not take important spatial neighbourhood effects into account. Imagine an image on a CRT monitor that has black text on a blue background. The text is easily distinguished against the background. However, if Clipping method [[v]] is applied to correct out of gamut colors, the gamut at darker color becomes narrower than it should be. This method results in CRT blue being mapped to a much darker blue in the output device. As a result, much of the luminance distinction is lost between text and background.

The third category of gamut mapping algorithms considers spatial characteristics in addition to color characteristics of the image. Using these algorithms, two pixels of the same color in an image can map to different colors in the output image, depending on the spatial characteristics in the neighbourhood of the pixels.

Most of the gamut mapping algorithms in any of the above categories, require large amount of information for the input and output device gamuts. They also can be slow, which can be a major barrier of them being used in commercialized applications.

In this paper gamuts of different monitors (LCD and CRT) and projectors are studied. In most of the analysis only the two monitors are used and I refer to them by LCD gamut and CRT gamut instead of LCD monitor gamut and CRT monitor gamut. I note here that my results may be biased since I only had access to two monitors to measure. Most of the figures are repeated in the appendix in a larger version. They also can be viewed electronically at: http://www.cs.sfu.ca/~bbastani/courses/820/project

Similar Gamut Shapes: Rotation/Scale/Translation

Speed: O(n)[1]

Memory: a 4x4 matrix

Below gamuts of a CRT and a LCD monitor in xyz space is shown below. The left gamut is for Samsung CRT monitor and the right one is for IBM LCD monitor.

They both have similar geometric shape.  Both are 8-sided 3D shape where gray axis defining the farthest two points in their space. So the first intuition was that maybe by a linear transformation most of the input device colours could fit inside output gamut.

The research has shown that aligning two gamuts’ grey axes are the most important factor in preserving color appearance of two models [2 ], [[vi]]. The first operation involves translating both gamuts so that their black points are at origin [0,0,0]. Since translation is an addition operation and scaling and rotation are multiplication operation, all the transformation operations are done in homogenous space so that they can be combined in on single matrix operation [[vii]].

The second step involves bringing both gamut measurements under same intensity environment. A spectrometer was used to measure the xyz values of colors inside gamuts. Since each monitor might have been under different setting (different contrast and brightness level) during the measurement, size of their gamuts may be different due to environment characteristics and not necessarily the of the device. There are two methods that I could of think of for bringing gamuts under unique illuminant environment.

First, measuring grey axis vector and dividing all the colors in xyz format by this vector, which is in xyz format as well. To be more precise:

Implication: Doing so makes white on each device equal to 1, meaning white is white on all the devices. Putting it in a different word using Colour Appearance Model (CAM), we can argue that user perceives a white patch as white whether he/she is viewing it on CRT or LCD monitor [[viii]]. However, there is one major problem with using this method and that is by applying this division the white point of each gamut will locate at [1,1,1]. Basically this division works as applying a non-uniform scale matrix. By having the white points sitting on [1,1,1] location, we loose the freedom of rotation.

So we need a method that we can both bring the grey axes together and also be able to remove environment illuminant factor. The second method is scaling the colour data by the size of its gamut grey axis. Basically applying a uniform scaling transformation. This method preserves location of white point and at the same time scales the gray axis to make it unit length.

After both gamuts are translated to origin and they are scaled so that their grey axes are of unit one, input gamut is rotated in 3D so that its grey axis falls on top of output gamut’s grey axis. After this rotation is applied, the input device gamut is scaled back, but this time by the size of output device grey axis. This way, the input gamut can be transferred to lighting environment of output device.

The last operation is translating the input gamut to where output gamut was originally. Below the operations are summarized:

[2] Inv(Trans_ouput) x Inv(Scale_ouput) x Rotation x

 Scale_input x Trans_input

Below are four input devices gamuts that are transformed to fit inside CRT gamut.

Left to right, top to bottom, black gamut is: CRT, monitor, LCD monitor, LCD Projector I, LCD projector II

In terms of speed, this method requires only applying a 4x4 matrix. The amount of information is needed to compute the transformation is only having the black and white point of the two input and output device.

However, it should be mentioned that this technique is not sufficient on its own since after transformation is applied, there might be colours that are still out of gamut. This method can be considered as a complement to other pixel-wise gamut mapping techniques.

One more degree of rotation, but which one?

Speed: O(n)

Memory: output device convex hull

When both device grey axes are aligned on top of each other, there is still one more degree of freedom to rotate the input gamut and that is a rotation around grey axis. This allows for further colour adjustment especially if after initial rotations some input colours are sticking out of output gamut.

However, one question remains and that is what colour should we pick as our point of adjustment. The choice of colour can be either inside output gamut or outside it. Analyzing the two gamuts after rotation shows that saturated colors, especially close to high end of x and y axis are more distant from their corresponding value in output gamut.

In my perceptual tests I found out that above analysis is true, meaning that trying to align colours such as yellow or blue makes the most visible change in other colours. The effects are a mixture of desirable and undesirable changes. But one thing to know is that there is no single answer. The effect of pivot colour is different based on output and input gamut characteristics.

Below is a test done on an image of human face[3]. The first set of images shows the final rotation around grey axes is done to align saturated blue colour. The next set had the rotation on saturated yellow. Colours that are still left out of gamut are clipped using Straight Clipping method II described later:

If the output images are inspected carefully on the monitors that the gamuts belong to, we can see that more facial parts of the face is preserved (not just clipped, but rather the relation between the colours are preserved) when yellow colour is aligned rather than blue.

Again these tests need to be done on the actual output devices that we measured their gamuts. Choosing cyan and magenta are better than choosing blue as pivot colour, but not as good as yellow.

The other problem that remains is still shape of the two gamuts. Consider figure below. The black gamut is rotated and scaled to fit inside output gamut. But naturally LCD gamut is thin and long versus CRT gamut, which is comparably thicker. So suppose when LCD gamut is fit inside CRT gamut, the saturated colours like yellow in LCD never match CRT saturated colours.

          LCD=black                         CRT=black

To be more precise, consider a person viewing an image with saturated yellow colour on CRT monitor. Even though the saturated yellow on LCD is not same as saturated yellow on CRT, but we perceive both yellows as saturated yellow, unless the two monitors are put right beside each other. Basically here we are dealing with colour appearance model. We might say that saturated yellow in LCD is inside CRT gamut so it is fine since the colour is not out of gamut. Consider the sun-rise image below:

When we are viewing this image, we expect (or our perception expects) that the sun-rise colour be close to bright yellow than non-saturated yellow.

What can be done?

To improve the gamut mapping, an interpolation was applied to input colours to blow them non-uniformly to fill in output gamut in the direction specified by some vectors. The interpolation uses weighted vectors between vectors between predefined saturated colours.

Unfortunately, I did not have the complete version of this part done due to lack of time. But some preliminary results showed that a better matching could be achieved. It should be mentioned that this method is good on natural scenes where we have a expectation of colours, and it is not desirable on an image of colour patches.

Why xyz space?

Speed: O(n)

Memory: a 4x4 matrix

For the previous methods, the rotations and scaling was done in xyz space. Cones space on the other hand, is meant to model illumination. The only reason that most the gamut mapping methods are done in xyz space is due to convention rather than anything else.

Cones space is considered to represent our eye cones. Beside sensor response, which is our eye observation is captured by:

Where lambda is the wavelength range. S is sensor sensitivity, R is illumination and E is the reflection factor.

Adjusting the grey axis by normalizing in lms space is more intuitive than doing it in xyz space. We also know that a linear transformation takes colours from xyz space to lms space.

Applying grey axis adjustment in lms is shown to have a relatively small improvement over previous method of rotation. The result for CRT and LCD monitor is shown below:

Finding out of gamut colours

Speed: O(n)

Memory: a 4x4 matrix

The linear transformation methods discussed before still leave some colours out of gamut. It is essential to find out if any colour is out of gamut so that otherwise we could stop applying further gamut mapping algorithm. The fastest algorithm that I knew about was using voronoi diagram and applying nearest neighbour search. Let us have a short discussion on voronoi diagram and nearest search algorithm.

Voronoi Diagram & Nearest Neighbour Search [[ix]][[x]]

Problem: Given a set of N points P = {P₁, P₂, …, P_n}, create a data-structure D_NN. Then, given a query point q, use D_NN to find the closest point p* in P to q, so that Distance (q, p*) ≤ Distance(q, pi) for all p_i in P.

To find the out of gamut colours, we need an algorithm that requires short time to reply to a query, which is influenced by the design of D_NN and as well as the algorithm used to locate the nearest neighbour. Size of the data structure D_NN, which is determined in pre-processing time is also important.

What is Voronoi Diagram?

Voronoi Diagrams transform a subdivision of the space into convex regions. The

boundaries of these regions are line segments, which become hyper planes[[xi]] in higher dimensions. A point has an unbounded region if and only if it lies on the hull of the convex. The space complexity of the Voronoi Diagram data-structure is O(N^ceil(d/2) ), which means it is quadratic for three dimensions. Basically, given the below data points as input:

Its voronoi diagram looks like [[xii]]:

The nearest neighbour search is based on voronoi diagram.

Algorithm:

To use this algorithm for finding outside gamut colours, the first step is to find convex hull of the output gamut. It usually contains 200+ points. Next, an arbitrary point inside gamut is chosen and its perpendicular bisector against every single plane in convex hull is found. After that, a voronoi diagram of these constructed points is created. These are done in pre-processing section.

For query, given a data point, the closest neighbour among the constructed points to this data point is found. If data point is closer to the nearest neighbour than the original arbitrary point inside, the data point is outside of gamut, otherwise it is inside.

Detail of Perpendicular Bisector[4]:

Perpendicular bisector of a point P to a plane L is found by first finding a perpendicular line to L and find projection of P on L. Suppose plane equation is (X – m) v[5], where v is the normal of L and the line equation is:

Q(t) = Q + tw. In this case, w is same as v. Then the equation to find projection of P on L is:

P_j

Then adding a vector PP_j to P_j gives the perpendicular bisector the plane L.

Analysis of the Algorithm:

Nearest search algorithm has complexity of n log(m) where m is the number of neighbours and n is the number of available data point. Normally for output gamut there are fewer than 300 data sets representing the convex hull. Thus log(300) 5.7, so the complexity of algorithm is less than 6n, which is quite fast.

Clipping Out of Gamut Colours

Clipping is one the most used methods for pixel-wise gamut mapping. There are a number of variations to this method such as[[xiii]][[xiv]]:

Straight Clipping:
A Gamut clipping algorithm that only affects colors which are outside the output gamut. For colours outside the output gamut, this algorithm specifies a mapping criterion, which is used for finding the point on the output gamut to which a given colour is mapped. All the colours inside output gamut remain unchanged. There are a number ways for projecting outside gamut colours onto output gamut convex hull and choosing the plane to project onto it.

Rescaling:

Opposite to Straight Clipping method that affects only out of gamut colours, this method scales down all the colours geometrically towards the white point. The scale factor is determined independently on each sector of gamut. The value of the factor is given by the ratio of the distance of the furthest point and the distance of the white point to its projection on the gamut.

Knee-Rescaling:

This method aims towards preserving the chromatic signal through the central portion of the gamut while compressing the chromatic signal near the edges of the gamut. This method tries to preserve the low chromatic signal characteristics, where the changes are more noticeable, while applying most the chromatic compression where the differences are less noticeable.

ResClipping:
This method is a mix between Straight Clipping and Rescaling. For colours outside the output gamut, ResClipping finds a mapping to project the point on the convex hull of the output gamut. For the colours inside the gamut they are geometrically scaled down, towards the white point using method described used in Rescaling.

Straight Clipping Method I:

Speed: O(log(n))

Memory: O(1)

Unfortunately I cannot explain this method in detail since it is highly dependent on the technology used in CVL lab at Simon Fraser University for mapping colour between devices.

To summarize, it breaks down the 3D gamut vale of an image into 3 parts. Then a clipping is applied in each 1D and a linear transformation moves the colour from the one dimension chosen back to the three-dimension space.

Analysis:

The result is not as good as the next clipping method. It preserves relation between colours inside gamut but for outside gamut colours plane chosen for projection is not as precise. This method is much faster than other clipping algorithms and uses less memory. Below is the output of this method:

Straight Clipping Method II:

Speed: O(n)

Memory: O(1)

Using Nearest Search algorithm, discussed earlier, we can find the closest outer point to a colour that is outside of output gamut. Every single outer point belongs to a plain in convex hull of output gamut. So using this information, we can find the plane that this colour is closest to. Projecting the colour on to the gamut should bring the point closer to the gamut surface. However, this heuristic does not guarantee a projection of colour on gamut surface in one iteration. Consider the following example:

The blue point is an outside gamut colour. The black point is the closest neighbour to this colour[6].

Data point is projected on to the plane corresponding to the closest neighbour point.

This point is still out of gamut so we need to apply projection one more time (iterate through the algorithm).

Analysis:

The images below are clipped using straight clipping method described in this section:

You can see that when output gamut is CRT and input is LCD (bottom left picture), colours look not saturated especially about the bright window. The reason is due to small shape of LCD gamut compare to CRT monitor gamut. This problem is discussed previously. On the other hand, when CRT gamut is fit into LCD gamut (top right picture), the colour contrast is not minimized. For instance it is hard to see the shadow on the face, there is a bright V shape on the face that was supposed to be bright face colour.

This method is more desirable than the previous clipping method and is used widely among industries. In terms of speed, the algorithm has to go through every single colour and find out whether the colour is outside or inside gamut. If it is outside of gamut then the colour has to be projected to the gamut surface as described before. Therefore this algorithm is of complexity  O(n) in speed, where n is the number unique colours in the image. In terms of memory use, for each plain in the convex hull, three points are stored and the gamuts normally have fewer than 300 plains describing their surface.

Non-Uniform Transformation[7]:

Speed: O(n2)

Memory: O(1)

Studying the gamut of monitors, we can see that they are not exactly 6-sided shape. Some of their sides are curved and this curvature is different between devices. This was shown earlier when a linear transformation could not fit one gamut to another one. In this section another method was applied that non-uniformly tries to fit the input gamut into output gamut.

In this method a set of colours that we have their perceived values (in this case xyz values) for both gamuts are chosen. Let us call these candidate colours as pivots. Since we have values for these pivots on both input and output gamut, they can be directly mapped to each other. For other colours not in this set we use an interpolation to find mapping between input gamut colours to output gamut.

Analysis:

Choice of interpolation is essential for this method. The other thing to know is that if the pivots are only saturated colours close to gamut surface, then the interpolation does not guarantee a straight grey axes. More specifically, we need data points inside gamuts as well to hold a good ratio between interpolated values. Advantage of using this method is that, it solves the problem of fitting thin shape LCD gamut into CRT gamut. We can force the interpolation to map saturated yellow in LCD to saturated yellow in CRT gamut. The result is shown below, but note that still some clipping needed since interpolation does not guarantee to hold all the colours inside output gamut.

One major problem with this method is that it reduces image quality. It is because the pivot colours are mapped directly and non-pivot colours are found using interpolation, so the image looks a bit rigid. Perhaps we could apply some smoothing, but applying that reduces the spatial factor of the image. There is more detail about this part later in this report.

Spatial Effect, Introduction

Most of the gamut mapping methods involve a pixel-wise mapping and ignore the spatial color configuration in the image. A spatial gamut mapping technique is proposed to overcome the weakness of standard pixel-wise gamut mapping algorithms by normally preserving spatially local luminance variations in the original image. These approaches are only used recently and there are not much research done in this area. The two approaches that are implemented in this section are based on the two famous and recent papers in this area [4 ] and [[xv]]. The detail math behind these two methods is not repeated here and the reader is encouraged to read these papers first.

Preserve Spatial Luminance Variations[4 ]

Speed: O(n)

Memory: O(n)

This paper aimed to take into account the spatial neighbourhood effects into account. One of their examples was about the case that black text on blue background. CRT monitor can show the image with text easily distinguished from the background. However, when this image is taken to printer, the blue is mapped to a darker blue and the text is not as obvious as it was on the monitor.

In this paper, the term ‘luminance’ refers to ‘Y component in XYZ space and ‘lightness’ refers to ‘L’ component in LAB space. A diagram showing the algorithm used in this paper is provided in Appendix B.

G₁ is any pixel-wise gamut mapping that brings all the colours inside output gamut. Similarly for the G₂ gamut mapping. First G₁ is applied to input colour and a ∆Y is computed between the luminance of the input and mapped colours. Then a high-pass filter F is applied to the ∆Y to get ∆Y^’. This result is then added back to gamut mapped signal Y^’. After that a second gamut mapping needs to be applied to ensure that if any of the colours went out of gamut because of ∆Y^’ addition are back inside output gamut. The whole purpose of this algorithm is to preserve the characteristics of high frequency luminance variations in the original image that might have been lost after applying G₁ mapping.

A simple linear filter was chosen for F as:

Where S is an NxN neighbourhood around pixel i.

The experiment shows that images with soft edges, e.g. the face picture used above, requires large filter size, while images with share edge requires small filter size. Below are the result of applying high filter size to the face and low filter size to the patches:

Analysis:

The result shows that even though the algorithm was able to restore some of high frequency variations, but it reduces the image quality. The other limitation with this algorithm was the fact that it works with gamut mapping methods such as Straight Clipping. Applying the filter to the methods that rotates the gamut reduces image quality by a large factor. This is because rotation changes the luminance by a larger factor than normal clipping and applying the filter tries to restore it back to the original one.

In the paper they mention that they tested the algorithm with clipping methods and for future work this method should be tested using other gamut mappings.

Space Dependent Colour Gamut Mapping

Speed: O(n)

Memory: O(n)

There is a heavy math behind this method and it is known to be the latest method in this area of gamut mapping. The motivation was to offer a new method in spatial dependent gamut mapping which does not use heuristic assumptions and does not have a high computational cost.

This method was the first method that tried to take advantage of gamut shape. They claim since the gamut of printers and monitors are convex, it is guaranteed using quadratic programming formulation that the gamut-mapping problem has a unique solution. 

Let us call our original input image u₀ and mapped image inside output gamut u_n. is the output gamut. We start with an image that is mapped to the output gamut using some pixel-wise method, so basically:

 u_n

This method iteratively applies to the previous adjustment until the solution converges. Thus another dimension beside position of pixel in the image is defined to represent time.  is introduced to represent this dimension and it is equal to dt.

Therefore,

u^n+r(x,y) = uⁿ(x,y,rT)

Let us define D₂= g_x*g_x + g_y + g_y where g_x is normalized Gaussian kernel with zero mean and small variance .

D=g*(u – u₀) is used as a model to capture perceptual differences between the initial, u₀, and final, u, images. Now the approximation for next iteration of gamut mapping follows:

Note that u_n .

The proof for convergence and how to optimize it are left to the reader.

Analysis:

The  factor in the above equation specifies a measure for our perceptual measures.

This method seems to work better than previous spatial gamut mapping It is smoother but takes considerably much longer time to give a good result. However, I should mention that pixel-wise gamut mapping between monitors preserve spatial information of an image enough that our eye will not catch the loose of information. All these gamut mapping proven to work well with previously known pixel-wise gamut mappings, especially clipping methods. However, it adds some noise to the image which might not be considered a problem since printers are in lower quality than monitor, but for gamut mapping between monitors this algorithm may not have much to offer.

Conclusion

Electronic technology is replacing our old way of communicating faster than ever. People tend to read more on their personal laptop than printing papers. Digital movies and DVD watched over monitors are replacing the old way of watching movies on TV. However, monitors and projectors each use a different technology and it is essential to find a mapping between their gamuts that brings similar perceived images to the viewer.

In this report there were some new method introduced that tried to take advantage of the fact that all these electronic devices have similar gamut shape. Also there was a survey of some of the most well-known gamut mapping method available. All the methods are analyzed by their speed, memory usage and the result they can offer.

Amongst discussed method, it was found that a combination of rotation and clipping gives the best result. It reduces the number of colours to be clipped and also keeps the hue of the gamuts constant. Applying non-uniform transformation to the linear transformed input gamut can result in a better mapping if we were able to choose larger number of pivots. This is needed to reduce the error caused by the interpolation.

Applying spatial gamut mappings restores some of the lost information in higher frequency, but they add some noise to the image.

Gamut of four devices

Use zoom option