Visible colours as linear combinations of the primary RGB components
Colour is one of the most widely used visual features in multimedia context. To support communication over the Internet, the data should compress well and be suitable for heterogeneous environment with a variety of the user platforms and viewing devices, large scatter of the user's machine power, and changing viewing conditions. The CBVIR systems are not aware usually of the difference in original, encoded, and perceived colours, e.g., differences between the colorimetric and device colour data (Shi & Sun, 2000).
Colour is a subjective human sensation of visible light depending on an intensity and a set of wavelengths associated with the electromagnetic spectrum. The composition of wavelengths specifies chrominance of visible light for human visual system. The chrominance has two attributes: hue and saturation. The hue is characterised by the dominant wavelength(s) in the composition, and the saturation measures the purity of a colour. A pure colour has 100% of saturation, whereas all shades of colourless (grey) light, e.g. white light, have 0% of saturation.
The sensed colour varies considerably with 3D surface orientation, camera viewpoint, and illumination of the scene, e.g., positions and spectra of illuminating sources. Also, human colour perception is quite subjective as regarding perceptual similarity. To design formal colour descriptors, one should specify a colour space, its partitioning, and how to measure similarity between colours.
Colour is a subjective visual characteristic describing how perceived electromagnetic radiation F(l) is distributed in the range of wavelengths l of visible light [380 nm ... 780 nm]. A colour space is a multidimensional space of colour components. Human colour perception combines the three primary colours: red (R) with the wavelength l=700 nm, green (G) with the wavelength l=546.1 nm, and blue (B) with the wavelength l=435.8 nm. Any visible wavelength L is sensed as a colour obtained by a linear combination of the three primary colours (R, G, B) with the particular weights cR( l ), cG( l) , cB( l):
Visible colours as linear combinations of the primary RGB components
The XYZ chromaticity diagrams defined by the CIE (Commission Internationale de l'Eclairage) for 1931 2o and 1964 10o Standard Observers form the basis of all today's colorimetry. Most of applications refer to 2o Observer. The unreal primary colours XYZ are obtained as linear combinations of the real colours RGB. This representation pursues the goal of obtaining only non-negative weights cX( l ), cY( l) , cZ( l):
Visible colours as linear combinations of the primary XYZ components
|
|
| CIE 1931 XYZ colour diagram | Chromaticity in the CIE diagram |
The RGB (Red - Green - Blue) tristimuli representation is most popular because it closely relates to human colour perception. A majority of modern imaging devices (cameras, videocameras, scanners) produce images represented in the RGB colour coordinates. A non-linear (power-function) relationship S = Lg between the signal S and light intensity L in such devices is usually corrected before storing, transmitting, or processing the images. This is referred to as gamma correction.
There are a variety of standard and non-standard RGB spaces for different application domains, e.g. linearly related to XYZ but not CIE-based RGB spaces for digital image scanners and cameras or non-linear CIE-based RGB spaces for computer displays and digital television. To represent colour on the Internet, a colorimetric sRGB standard based on common monitors has been recently proposed. However, the RGB colour space is not perceptually uniform, and equal distances in different areas do not reflect equal perceptual dissimilarity of colours. Because of the lack of a single perceptually uniform colour space, a large number of spaces derived from the RGB space have been used in practice for a query-by-colour (Castelli & Bergman, 2002).
RGB colour space and relative rgb colour coordinates q = Q / (R + G + B) where Q, q stand for R, r; G, g, and B, b, respectively.
| 
|
| RGB colour image | Red (R) component |
| 
|
| Green (G) component | Blue (B) component |
The recorded initial RGB colour representation of an image is of retrieval value only if recording was performed in stable conditions, e.g., for art paintings. Generally, the RGB colour coordinates are strongly interdependent and describe not only inherent colour properties of objects but also variations of illumination and other external factors. To form more independent colour representation, at least for image retrieval, independent (or opponent) colour axes (R + G + B, R - G, - R - G + 2B), or relative colour coordinates shown above, or other "luminance - chrominance" representations are used. They separate luminance, or lightness of the optical colour signal (e.g., R + B + G) from two chrominance components in the co-ordinate plane orthogonal to the luminance axis. The luminance axis can be down-sampled as human vision is more sensitive to chroma than to brightness. The chrominance components are invariant to changes in illumination intensity and shadows (Smeulders e.a., 2000). But although these linear colour transforms are computationally simple, the resulting colour spaces are neither uniform, nor natural.
The HSI hue - saturation - intensity or, what is the same, HSV hue - saturation - value space is obtained by non-linear transformation of the RGB space. The HSI representation uses the brightness value( or intensity) I = (R + G + B)/3 as the main axis orthogonal to the chrominance plane. The saturation S and the hue H are the radius and the angle, respectively, of the polar coordinates in the chrominance plane with the origin in the trace of the value axis. This representation is approximately perceptually uniform and is closely related to the way the human vision perceives colour images. Because of invariance to the object orientation with respect to illumination and camera viewing direction, the hue is more suitable for object retrieval. But the conversion between the RGB and HSI colour coordinates is a bit complicated:
Colour television and image coding standards utilise less computationally complex opponent colour representations such as YUV, YIQ, YDbDr, and YCbCr. The chrominance component pairs are either differences (U, V) between the primary colours B or R and the luminance Y or linear transformations of these differences (I, Q or Db, Dr).
The YUV colour space used in PAL (Phase Alternating Line) TV systems adopted by most European countries, some Asian countries, Australia, and New Zealand, uses the following luminance (Y) and chrominance (U,V) components:
| Y = 0.299R + 0.587G + 0.114B |
| U = 0.492(B-Y) |
| V = 0.877(R-Y) |
| Y = 0.299R + 0.587G + 0.114B |
| U = -0.147R - 0.289G + 0.436B |
| V = 0.615R - 0.515G - 0.100B |
The YIQ colour space utilised in NTSC (National Television Systems Committee) TV systems in the USA, Canada, and Japan, has the same luminance component Y, but the two chrominance components are the linear transformation of the U and V components defined in the YUV model (the IQ co-ordinates are the UV ones rotated by 33o):
| I = -0.545U + 0.839V |
| Q = 0.839U + 0.545V |
| Y = 0.299R + 0.587G + 0.114B |
| I = 0.596R - 0.275G - 0.321B |
| Q = 0.212R - 0.523G + 0.311B |
The YDbDr model used in SECAM (Sequential Couleur a Memoire) TV system in France, Russia and some Eastern European countries differs from the YUV model by only scaling: Db = 3.059U and Dr = -2.169V, that is,
| Y = 0.299R + 0.587G + 0.114B |
| Db = -0.450R - 0.883G + 1.333B |
| Dr = -1.333R + 1.116G - 0.217B |
The YCbCr colur space is used in the JPEG and MPEG international coding standards. In order to make chrominance components non-negative, it is formed by scaling and shifting the Y,U,V co-ordinates:
| Y = 0.257R + 0.504G + 0.098B + 16 |
| Cb= -0.148R - 0.291G + 0.439B + 128 |
| Cr= 0.439R - 0.368G - 0.071B + 128 |
CIE introduced also two uniform luminance - chrominance colour spaces, namely, Lab (used in colour facsimile transmission) and Luv. CIE Lab and Luv colour spaces compress well in the case of pictorial images.
|
| 
|
| RGB colour image | Lab lightness (L) component |
| 
|
| Lab chrominance (a) component | Lab chrominance (b) component |
| 
|
| CMYK blacK component | CMYK Cyan component |
| 
|
| CMYK Magenta component | CMYK Yellow component |
To compress the colour information, most of graphics file formats use special colour maps or lookup tables, called palettes. A table of colours is of the fixed and relatively small size N, and the colour in a pixel is represented by an index into the table. The palletising is performed by vector quantisation of a given colour space.
The International Color Consortium (ICC) proposed more flexible approach to communicate colour in open systems by attaching an ICC profile of the input colour space to any image at hand. The profile defines the image colours explicitly in terms of a transform between a given colour space and a particular Profile Connection Space (PCS) such as XYZ or CIE Lab. The ICC has defined standard formats for profiles and classes of profiles for image input devices, monitors, printers, and device-to-device links. But a broad range of users do not require such flexibility and control. Also, most existing graphics file formats do not, and may never support colour profile embedding, as well as a broad range of uses actually discourage people from appending any extra data to their files (Stokes e.a., 1996).
Colour invariants for object retrieval can be derived by analysing existing photometric models of surface reflections (Smeulders e.a., 2000):
These representations depend only on sensor and surface albedo and are robust against major viewpoint distortions.
A standard default colour space for the Internet was proposed in 1996 by Hewlett-Packard and Microsoft. The aim of this colour space is to utilise a simple and robust device independent colour definition for handling colour in operating systems, device drivers, and the Internet. Although it is not a general standard yet, the attempt of merging the plethora of existing standard and non-standard RGB monitor colour spaces into a single standard RGB colour space is worthy to be discussed due to importance of the colour for visual information publishing and retrieval.
The standard describes the viewing environment relating to the human visual perception and the device space colorimetry. The viewing environment parameters, combvined with most colour appearance modelsa, provide conversions between the standard and target viewing environment. The colorimetric definitions specify necessary conversions between the sRGB colour space and device independent CIE XYZ two degree observer colour space. The CIE chromaticities for the reference primary RGB colours and for CIE Standard Illuminant D65 are as follows:
| Red | Green | Blue | D65 | |
|---|---|---|---|---|
| X | 0.6400 | 0.3000 | 0.1500 | 0.3127 |
| Y | 0.3300 | 0.6000 | 0.0600 | 0.3290 |
| Z | 0.0300 | 0.1000 | 0.7900 | 0.3583 |
sRGB tristimulus values for the illuminated objects of the scene are simply linear combinations of the 1931 CIE XYZ values:
| RsRGB = 3.2410 X - 1.5374 Y - 0.4986 Z |
| GsRGB = -0.9692 X + 1.8760 Y + 0.0416 Z |
| RsRGB = 0.0556 X - 0.2040 Y + 1.0570 Z |
The sRGB colour space meets the needs of most Internet users without the overhead of carrying an ICC profile with the image. The proposed standard assumes that all web page elements are in the sRGB colour space unless embedded ICC profiles indicate otherwise.
Generally, the colour space is much more detailed than human vision requires for representing natural objects, and every image or video clip does not use simultaneously all the perceivable colours . With 256 signal levels for each RGB colour component, the RGB cube splits into 224=16,277,216 individual colours whereas most of scenes involve only hundreds and rarely thousands of different colours. Thus the discrete colour space can be considerably compressed by proper colour quantisation.
With respect to accuracy of representing colours of each individual image, scalar quantisation of colour spaces, that is, separate quantisation of each colour dimension, ranks below adaptive vector quantisation. Generally, the vector quantisation maps a whole d-dimensional vector space into a finite set C = {c1, c2, ..., cK}of d-dimensional vectors. The set C is usually called a codebook, and its elements are called code words. In the colour quantisation, d=3, and each code word ck is a representative colour. The codebook C representing a collection of K colours is usually called a colour gamut, or a palette. The vector quantisation partitions the whole 3D colour space into K disjoint subsets, one per code word. All the colours belonging to the same subset are represented by, or quantised to the same code word ck. A perceptually good palette contains code words that closely approximate colours in the corresponding subsets so that each subset contains the visually similar colours.
Many digital graphics formats use one or another form of vector quantisation to compress the colour images. The palette for an image or an ensemble of images is usually built by statistical averaging and clustering of the colours at hand. Any conventional multidimensional clustering method, such as K-means, fuzzy K-means, or EM (Expectation - Maximisation) clustering, can be used in principle for the colour quantisation.
A popular vector quantisation algorithm iteratively doubles the number of codewords until a prescribed number of them, say, 64, 128, or 256, is formed. Each iteration t creates Kt =2t cluster centres (codewords) Ct = {Ck,t: k = 1, ..., Kt}. When t = 0, the process starts with a single centre c1,0 that averages colour vectors over an image. At each next iteration, t, every previous cluster centre ck,t-1; k = 1, ..., Kt-1, splits into the two new centres as follows:
Strategies of how to split one code word differ in different implementations, e.g. a multiplication to the two constant factors: (1+w)c and (1-w)c where w; 0 < w < 1, is a fixed constant, or a shift of each current centre to and from the most distant signal vectorg in the cluster: C + w(g - c) and c - w(g - c), or so forth.
Colour descriptors of images and video can be global and local. Global descriptors specify the overall colour content of the image but with no information about the spatial distribution of these colours. Local descriptors relate to particular image regions and, in conjunction with geometric properties of these latter, describe also the spatial arrangement of the colours (Castelli & Bergman).
A colour histogram describes the distribution of colours within a whole image or video scene or within a specified region. As a pixel-wise characteristic, the histogram is invariant to rotation, translation, and scaling of an object. At the same time, the histogram does not capture semantic information, and two images with similar colour histograms can possess totally different contents. A quantised HSI (or HSV) colour space is typically used to represent the colour in order to make the search partially invariant to irrelevant constraints such as illumination and object viewpoints (Chang e.a., 2001, Rahman, 2002). In such a colour space, an Euclidean or similar component-wise distance between the colours specifies colour similarity quite well. The YUV colour space is also often used since it is standard for the MPEG video compression.
A colour histogram h(image)=(hk(image): k=1,...,K) is a K-dimensional vector such that each component hk( image) represents the relative number of pixels of colour Ck in the image, that is, the fraction of pixels that are most similar to the corresponding representative colour. To built the colour histogram, the image colours should be transformed to an appropriate colour space and quantised according to a particular codebook of the size K. By extracting the colour histograms for image regions such as shown below, the spatial distribution of colours can be taken into account at least roughly because the dissimilarity of image colours is now measured by the weighted sum of the individual colour dissimilarities between the corresponding regions.
|
|
In the QBE case, the database images compared to the query have to be requantised by finding for every pixel the closest colour in the query codebook. Then the colour histogram of the image in question can be matched to the query histogram.
The (dis)similarity of two images described by normalised colour histograms, h and h', is measured by computing a distance between the histograms in the colour space. The chosen metric effects both effectiveness and computational complexity of retrieval. The effectiveness indicates to which extent the quantitative similarity match the perceptual, subjective one.
In the simplest case, the distance is based on the Minkowski metrics, such as the city-block or Euclidean distance between the relative frequencies of the corresponding colours, or on the histogram intersection proposed by Swain and Ballard:
The above metrics comparing only the corresponding colour components between the histograms take no account of cross-relations of the different colour clusters. Thus the images with similar but not identical representative colours can be considered as dissimilar on the basis of the distance between the colour histograms. Quadratic-form metrics avoid this drawback by pairwise comparisons of all the component pairs:
where A = [aij] is the positive definite symmetric matrix K × K with components aij = aji specifying the dissimilarity between the code words ci and cj for the histogram components with indices i and j. To decrease the computational complexity of the quadratic-form metrics, only most significant components may be taken into account.
A special case of the quadratic-form metric is the Mahalanobis distance in which the dissimilarity matrix A is obtained by inverting the covariance matrix for a training set of colour histograms. Alternatively, the Mahalanobis distance can account for the covariance matrix of colours in a set of training images (then the colours that are dominant across all images and do not discriminate among different images will not effect the distance, as it should be). In the special case of uncorrelated histogram components when the covariance matrix is diagonal, the Mahalanobis distance reduces to a weighted Euclidean one. The weight of each squared difference of the histograms' components is inversely proportional to the variance of these components treated as random variables.
The colour information for CBVIR is represented also using colour moments, colour sets, colour coherence vectors, or colour correlograms.
Here, q denotes the colour component (e.g., R, G, B or H, S, V) and S =2, 3, ..., is the order of the moment. The similarity between the moments is measured usually by the Euclidean distance.
However, if two images have only a similar subregion, their corresponding moments, as well as colour histograms, will be different, and the overall similarity measure will be low. This is why in many experimental QBE-oriented CBVIR systems the images are split onto a fixed or adaptive set of regions, and the colour features of one query region are compared to all the regions of every image in question.
Because the features for one query region can be similar to those for other regions, the same vector quantisation that had been efficient for building the colour codebooks can also be applied for selecting the most informative vectors of the colour features. Typically, the centres of the clusters of the feature vectors serve as such colour primitives describing the query image.
In the WebSEEk, the colour HSI space is divided into 166 colours as follows. The space is considered as a cylinder with the axis representing the value (intensity) that ranges from pure black to pure white. The distance (radius) to the axis gives the saturation, or relative amount of presense of a colour, and the angle around the axis is the hue giving the chroma (tint, ot tone). The hue is represented with the finest resolution by a circular quantisation of the hue circle into 18 sectors (6 per each primary colour). Other colour components are represented with the coarser resolution by quantising each into three levels. In addition, the colourless greyscale signals are quantised into four levels. This gives in total 18 (H) × 3 (S) × 3 (I) + 4 (grey levels) = 166 disctinct colours.