Image representation method and apparatus

0001Colour can potentially provide useful information to a variety of computer vision tasks such as image segmentation, image retrieval, object recognition and tracking. However, for it to be helpful in practice, colour must relate directly to the intrinsic properties of the imaged objects and be independent of imaging conditions such as scene illumination and the imaging device. To this end many <i>invariant</i> colour representations have been proposed in the literature. Unfortunately, recent work [3] has shown that none of them provides good enough practical performance.

Summary of the Invention

0002The invention provides a method and an apparatus for representing, characterising, transforming or modifying a colour image as defined in the appended independent claims. Preferred or advantageous features of the invention are set out in dependent subclaims.

0003In this paper we propose a new colour invariant image representation based on an existing grey-scale image enhancement technique: histogram equalisation. We show that provided the rank ordering of sensor responses are preserved across a change in imaging conditions (lighting or device) a histogram equalisation of each channel of a colour image renders it invariant to these conditions. We set out theoretical conditions under which rank ordering of sensor responses is preserved and we present empirical evidence which demonstrates that rank ordering is maintained in practice for a wide range of illuminants and imaging devices. Finally we apply the method to an image indexing application and show that the method outperforms all previous invariant representations, giving close to perfect illumination invariance and very good performance across a change in device.

1 Introduction

0004It has long been argued that colour (or <i>RGB</i>) images provide useful information which can help in solving a wide range of computer vision problems. For example it has been demonstrated [14, 1] that characterising an image by the distribution of its colours (<i>RGBs</i>) is an effective way to locate images with similar content from amongst a diverse database of images. Or that a similar approach [19] can be used to locate objects in an image. Colour has also been found to be useful for tasks such as image segmentation [12, 13] and object tracking [7, 16]. Implicit in these applications of colour is the assumption that the colours recorded by devices are an inherent property of the imaged objects and thus a reliable cue to their identity. Unfortunately a careful examination of image formation reveals that this assumption is not valid. The <i>RGB</i> that a camera records is more properly a measure of the light reflected from the surface of an object and while this does depend in part on characteristics of the object, it depends in equal measure on the composition of the light which is incident on the object in the first place. So, an object that is lit by an illuminant which is itself reddish, will be recorded by a camera as more red than will the same object lit under a more bluish illuminant. That is, image <i>RGBs</i> are <i>illumination dependent.</i> In addition image colour also depends on the properties of the recording device. Importantly, different imaging devices have different sensors which implies that an object that produces a given <i>RGB</i> response in one camera might well produce a quite different response in a different device.

0005In recognition of this fact many researchers have sought modified image representations such that one or more of these dependencies are removed. Researchers have to-date, concentrated on accounting for illumination dependence and typically adopt one of two approaches: colour invariant [9, 5, 6, 10, 18] or colour constancy [11, 8] methods. Colour invariant approaches seek transformations of the image data such that the transformed data is illuminant independent whereas colour constancy approaches set out to determine an estimate of the light illuminating a scene and provide this estimate in some form to subsequent vision algorithms.

0006Colour constancy algorithms, in contrast to invariant approaches can deliver true object colours. Moreover, colour invariants can be calculated post-colour constancy processing but the converse is not true. This said, colour constancy has proven to be a harder problem to solve than colour invariants. Most importantly however, it has been demonstrated [8, 3] that the practical performance of neither approach is good enough to facilitate colour-based object recognition or image retrieval. Moreover, none of the methods even attempts to account for device dependence.

0007In this paper we seek to address the limitations of these existing approaches by defining a new image representation which we show is both illumination independent and (in many cases) also device independent. Our method is based on the observation that while a change in illumination or device leads in practice to significant changes in the recorded <i>RGBs</i>, the rank orderings of the responses of a given sensor are largely preserved. In fact, we show in this paper (§3) that under certain simplifying assumptions, invariance of rank ordering follows directly from the image formation equation. In addition we present an empirical study (§4) which reveals that the preservation of rank ordering holds in practice both across a wide range of illuminants and a variety of imaging devices. Thus, an image representation which is based on rank ordering of recorded <i>RGBs</i> rather than on the <i>RGBs</i> themselves offers the possibility of accounting for both illumination and device dependence at the same time.

0008To derive an image representation which depends only on rank orderings we borrow a tool which has long been used by the image processing community for a quite different purpose. The technique is histogram equalisation and is typically applied to grey-scale images to produce a new image which is enhanced in the sense that the image has more contrast and thus conveys more information. In some cases this results in a visually more pleasing image. But in a departure from traditional image processing practice, we apply the procedure not to a grey-scale image, but rather to each of the <i>R, G,</i> and <i>B</i> channels of a colour image independently of one another. We show that provided two images differ in such a way as to preserve the rank ordering of pixel values in each of the three channels then an application of histogram equalisation to each of the channels of the two images results in a pair of equivalent images. Thus provided a change in illuminant or device preserves rank ordering of pixel responses the application of histogram equalisation will provide us with an invariant representation of a scene which might subsequently be of use in a range of vision applications.

0009Of course the reader may be surprised that we propose something so simple: histogram equalisation is a common tool. Paradoxically however, histogram equalising <i>R, G,</i> and <i>B</i> channels of an image is generally discouraged because this results in unnatural pseudo-colours. For our purposes, however - recognition or tracking - pseudo-colours suffice. We demonstrate this (§5) by applying the method to the problem of colour indexing: we show that the method out performs all previous approaches and in the case of a change in illumination provides close to perfect indexing.

0010The scientific article by Pietitkäinen et al. <i>"Accurate color discrimination with classification based on feature distributions",</i> ICPR'96, 1996, discloses a method for the retrieval of images based on the comparison of color image histograms. The illumination change invariance is achieved by a calibration procedure.

0011The scientific article by<nplcit id="ncit0001" npl-type="s"><text> Chen et al. "Rotation and gray scale transform invariant texture identification using wavelet decomposition and hidden Markov model" in Transactions on Pattern Analysis and Machine intelligence, Vol.16, February 1994</text></nplcit>, discloses a method for texture recognition where a gray scale transform invariance is achieved by an histogram equalization of the image intensity value.

2 Background

0012We base our work on a simple model of image formation in which the response of an imaging device to an object depends on three factors: the light by which the object is lit, the surface reflectance properties of the object, and the properties of the device's sensors. We assume that a scene is illuminated by a single light characterised by its spectral power distribution which we denote <i>E</i>(λ) and which specifies how much energy the source emits at each wavelength (λ) of the electromagnetic spectrum. The reflectance properties of a surface are characterised by a function <i>S</i>(λ) which defines what proportion of light incident upon it the surface reflects on a per-wavelength basis. Finally a sensor is characterised by <i>R_k</i>(λ), its spectral sensitivity function which specifies its sensitivity to light energy at each wavelength of the spectrum. The subscript <i>k</i> denotes that this is the <i>k</i>th sensor. Its response is defined as: <maths id="math0001" num="(1)"><math display="block"><msub><mi>p</mi><mi>k</mi></msub><mo>=</mo><mrow><msub><mo>∫</mo><mi>ω</mi></msub><mo>⁢</mo><mi>E</mi><mfenced><mi>λ</mi></mfenced><mo>⁢</mo><mi>S</mi><mfenced><mi>λ</mi></mfenced><mo>⁢</mo><msub><mi>R</mi><mi>k</mi></msub><mfenced><mi>λ</mi></mfenced><mo>⁢</mo><mi>d</mi><mo>⁢</mo><mi>λ</mi><mo>)</mo></mrow><mo>,</mo><mspace width="1em" /><mi>k</mi><mo>=</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>m</mi></math><img file="EP1520397B1_D0001.tif" /></maths> where the integral is taken over the range of wavelengths ω: the range for which the sensor has non-zero sensitivity. In what follows we assume that our devices (as most devices do) have three sensors (<i>m</i> = <i>3</i>) so that the response of a device to a point in a scene is represented by a triplet of values: (<i>p₁,p₂,p₃</i>). It is common to denote these triplets as <i>R, G,</i> and <i>B</i> or just <i>RGBs</i> and so we use the different notations interchangeably throughout. An image is thus a collection of <i>RGBs</i> representing the device's response to light from a range of positions in a scene.

0013Equation (1) makes clear the fact that a device response depends both on properties of the sensor (it depends on <i>R_k</i>(λ)) and also on the prevailing illumination on (<i>E</i>(λ)). That is, responses are both device and illumination dependent. It follows that if no account is taken of these dependencies, an <i>RGB</i> cannot correctly considered to be an intrinsic property of an object and employing it as such is quite likely to result in poor results.

0014An examination of the literature reveals many attempts to deal with the illumination dependence problem. One approach is to apply a correction to the responses recorded by a device to account for the colour of the prevailing scene illumination. Provided an accurate estimate of the scene illumination can be obtained, such a correction accounts well for the illumination dependence, rendering responses colour constant: that is stable across a change in illumination. The difficulty with this approach is the fact that estimating the scene illuminant is non-trivial. In 1998 Funt <i>et al</i> [8] demonstrated that existing colour constancy algorithms are not sufficiently accurate to make such an approach viable. More recent work [11] has shown that for simple imaging conditions and given good device calibration the colour constancy approach can work.

0015A different approach is to derive from the image data some new representation of the image which is invariant to illumination. Such approaches are classified as colour (or illuminant) invariant approaches and a wide variety of invariant features have been proposed in the literature. Accounting for a change in illumination colour is however difficult because, as is clear from Equation (1), the interaction between light, surface and sensor is complex. Researchers have attempted to reduce the complexity of the problem by adopting simple models of illumination change. One of the simplest models is the so called <i>diagonal</i> model in which it is proposed that sensor responses under a pair of illuminants are related by a diagonal matrix transform: <maths id="math0002" num="(2)"><math display="block"><mfenced><mtable><mtr><mtd><msup><mi>R</mi><mi>c</mi></msup></mtd></mtr><mtr><mtd><msup><mi>G</mi><mi>c</mi></msup></mtd></mtr><mtr><mtd><msup><mi>B</mi><mi>c</mi></msup></mtd></mtr></mtable></mfenced><mo>=</mo><mfenced><mtable><mtr><mtd><mi>α</mi></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mi>β</mi></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mi>γ</mi></mtd></mtr></mtable></mfenced><mo>⁢</mo><mfenced><mtable><mtr><mtd><msup><mi>R</mi><mi>o</mi></msup></mtd></mtr><mtr><mtd><msup><mi>G</mi><mi>o</mi></msup></mtd></mtr><mtr><mtd><msup><mi>B</mi><mi>o</mi></msup></mtd></mtr></mtable></mfenced></math><img file="EP1520397B1_D0002.tif" /></maths> where the superscripts o and c characterise the pair of illuminants. The model is widely used, and has been shown to be well justified under many conditions [7]. Adopting such a model one simple illuminant invariant representation of an image can be derived by applying the following transform: <maths id="math0003" num="(3)"><math display="block"><mi mathvariant="italic">Rʹ</mi><mo>=</mo><mfrac><mi>R</mi><msub><mi>R</mi><mi mathvariant="italic">ave</mi></msub></mfrac><mo>,</mo><mi mathvariant="italic">Gʹ</mi><mo>=</mo><mfrac><mi>G</mi><msub><mi>G</mi><mi mathvariant="italic">ave</mi></msub></mfrac><mo>,</mo><mi mathvariant="italic">Bʹ</mi><mo>=</mo><mfrac><mi>B</mi><msub><mi>B</mi><mi mathvariant="italic">ave</mi></msub></mfrac></math><img file="EP1520397B1_D0003.tif" /></maths> where the triplet <i>(R_ave G_ave, B</i>_a<i>ve</i>) denotes the mean of all <i>RGBs</i> in an image. It is easy to show that this so called <i>Greyworld</i> representation of an image is illumination invariant provided that Equation (2) holds.

0016Many other illuminant invariant representations have been derived, in some cases [10] by adopting different models of image formation. All derived invariants however share two common failings: first it has been demonstrated that when applied to the practical problem of image retrieval none of these invariants affords good enough performance across a change in illumination. Secondly, none of these approaches considers the issue of device invariance.

0017Device invariance occurs because different devices have different spectral sensitivity functions (different <i>R_k</i> in Equation (1)) but also because the colours recorded by a device are often not linearly related to scene radiance as Equation (1) suggests, but rather are some non-linear transform of this: <maths id="math0004" num="(4)"><math display="block"><msub><mi>p</mi><mi>k</mi></msub><mo>=</mo><mi>f</mi><mfenced><msub><mo>∫</mo><mi>ω</mi></msub><mo>⁢</mo><mi>E</mi><mfenced><mi>λ</mi></mfenced><mo>⁢</mo><mi>S</mi><mfenced><mi>λ</mi></mfenced><mo>⁢</mo><msub><mi>R</mi><mi>k</mi></msub><mfenced><mi>λ</mi></mfenced><mo>⁢</mo><mi>d</mi><mo>⁢</mo><mi>λ</mi></mfenced><mo>,</mo><mi>k</mi><mo>=</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>m</mi></math><img file="EP1520397B1_D0004.tif" /></maths>

0018The transform <i>f()</i> is deliberately applied to <i>RGB</i> values recorded by a device for a number of reasons. First, many captured images will eventually be displayed on a monitor. Importantly colours displayed on a screen are not a linear function of the RGBs sent to the monitor. Rather, there exists a power function relationship between the incoming voltage and the displayed intensity. This relationship is known as the gamma of the monitor, where gamma describes the exponent of the power function [15]. To compensate for this gamma function images are usually stored in a way that reverses the effect of this transformation: that is by applying a power function with exponent of 1/γ, where y describes the gamma of the monitor, to the image RGBs. Importantly monitor gammas are not unique but can vary from system to system and so images from two different devices will not necessarily have the same gamma correction applied. In addition to gamma correction other more general non-linear "tone curve" corrections are often applied to images so as to change image contrast with the intention of creating a visually more pleasing image. Such transformations are device, and quite often, image dependent and so lead, inevitably to device dependent colour. In the next section we address the limitations of existing invariant approaches by introducing a new invariant representation.

3 Histogram Equalisation for Colour Invariance

0019Let us begin by considering again the diagonal model of image formation defined by Equation (2). We observe that one implication of this model of illumination change is that the rank ordering of sensor responses is preserved under a change of illumination. To see this, consider the responses to a single sensor <i>R,</i> such that <i>R^o_i</i> represents the response to a surface i under an illuminant <i>o.</i> Under a second illuminant, which we denote c, the surface will have response <i>R^c_i</i> and the pair of sensor responses are related by: <maths id="math0005" num="(5)"><math display="block"><msubsup><mi>R</mi><mi>i</mi><mi>c</mi></msubsup><mo>=</mo><mi>α</mi><mo>⁢</mo><msubsup><mi>R</mi><mi>i</mi><mi>o</mi></msubsup></math><img file="EP1520397B1_D0005.tif" /></maths>

0020Equation (5) is true for all surfaces (that is, ∀ <i>i</i>). Now, consider a pair of surfaces, <i>i</i> and <i>j,</i> viewed under illuminant o and suppose that <i>R^o_i</i> > <i>R^o_j</i>, then it follows from Equation (5) that: <maths id="math0006" num="(6)"><math display="block"><msubsup><mi>R</mi><mi>i</mi><mi>o</mi></msubsup><mo>></mo><msubsup><mi>R</mi><mi>j</mi><mi>o</mi></msubsup><mo>⇒</mo><mi>α</mi><mo>⁢</mo><msubsup><mi>R</mi><mi>i</mi><mi>o</mi></msubsup><mo>></mo><mi>α</mi><mo>⁢</mo><msubsup><mi>R</mi><mi>j</mi><mi>o</mi></msubsup><mo>⇒</mo><msubsup><mi>R</mi><mi>i</mi><mi>c</mi></msubsup><mo>></mo><msubsup><mi>R</mi><mi>j</mi><mi>c</mi></msubsup><mo>∀</mo><mspace width="1em" /><mi>i</mi><mo>,</mo><mi>j</mi><mo>,</mo><mo>∀</mo><mi>α</mi></math><img file="EP1520397B1_D0006.tif" /></maths>

0021That is, the rank ordering of sensor responses within a given channel is invariant to a change in illumination.

0022Thus, if what we seek is an image representation which is invariant to illumination we can obtain one by considering not the pixel values themselves but rather the relative ordering of these values. There are a number of ways we might employ this rank ordering information to derive an invariant representation, we set forth one such method here which we will demonstrate has a number of interesting properties. To understand our method consider a single channel of an <i>RGB</i> image recorded under an illuminant <i>o</i> where without loss of generality we restrict the range of <i>R^o</i> to be on some finite interval: <i>R^o</i> ∈ [0...<i>R</i>/<i>max</i>]. Now, consider further a value <i>R^o_i</i> ∈ [0...<i>R</i>/<i>max</i>] where <i>R^o_i</i> is not necessarily the value of any pixel in the image. Let us define by <i>P</i>(<i>R^o&lt; R^o_i</i>), the number of pixels in an image with a value less than or equal to <i>R^o_i</i>. Under a second illuminant, <i>c,</i> a pixel value <i>R^o</i> under illuminant o is mapped to a corresponding value <i>R_c</i>. We denote by <i>P</i>(<i>R_c</i> &lt; <i>R^c_i</i>) the number of pixel values in the second image whose value is less than <i>R^c_i.</i> Assuming that the illumination change preserves rank ordering of pixels we have the following relation: <maths id="math0007" num="(7)"><math display="block"><mi>P</mi><mfenced><msup><mi>R</mi><mi>c</mi></msup><mo>&lt;</mo><msubsup><mi>R</mi><mi>i</mi><mi>c</mi></msubsup></mfenced><mo>=</mo><mi>P</mi><mfenced><msup><mi>R</mi><mi>o</mi></msup><mo>&lt;</mo><msubsup><mi>R</mi><mi>i</mi><mi>o</mi></msubsup></mfenced></math><img file="EP1520397B1_D0007.tif" /></maths>

0023That is, the number of pixels in our image under illuminant o which have a value less than <i>R^o_i</i> is equal to the number of pixels in the image under illuminant c which have a value less than the transformed pixel value <i>R^c_i</i>: a change in illumination preserves cumulative proportions. Given this, we define one channel of the invariant image representation thus: <maths id="math0008" num="(8)"><math display="block"><msubsup><mi>R</mi><mi>i</mi><mi mathvariant="italic">inv</mi></msubsup><mo>=</mo><mfrac><msub><mi mathvariant="italic">R</mi><mi mathvariant="italic">max</mi></msub><msub><mi mathvariant="italic">N</mi><mi mathvariant="italic">mix</mi></msub></mfrac><mo>⁢</mo><mi>P</mi><mfenced><msup><mi>R</mi><mi>o</mi></msup><mo>≤</mo><msubsup><mi>R</mi><mi>i</mi><mi>o</mi></msubsup></mfenced><mo>=</mo><mi>P</mi><mfenced><msup><mi>R</mi><mi>c</mi></msup><mo>≤</mo><msubsup><mi>R</mi><mi>i</mi><mi>c</mi></msubsup></mfenced></math><img file="EP1520397B1_D0008.tif" /></maths> where <i>N_pix</i> is the number of pixels and the constant <i>R_max</i>/<i>N_pix</i> ensures that the invariant image has the same range of values as the input image. Repeating the procedure for each channel of a colour image results in the required invariant image.

0024The reader familiar with the image processing literature might recognise Equation (8). Indeed this transformation of image data is one of the simplest and most widely used methods for image enhancement and is commonly known as histogram equalisation. Histogram equalisation is an image enhancement technique originally developed for a single channel, or grey-scale, image. The aim is to increase the overall contrast in the image since doing so typical brightens dark areas of an image, increasing the detail in those regions which in turn can sometimes result in a more pleasing image. Histogram equalisation achieves this aim by transforming an image such that the histogram of the transformed image is as close as possible to a uniform histogram. The approach is justified on the grounds that amongst all possible histograms, a uniformly distributed histogram has maximum entropy. Maximising the entropy of a distribution maximises its information and thus histogram equalizing an image maximises the information content of the output image. Accepting the theory, to histogram equalise an image we must transform the image such that the resulting image histogram is uniform. Now, suppose that <i>x_i</i> represents a pixel value in the original image and <i>x'_i</i> its corresponding value in the transformed image. We would like to transform the original image such that the proportion of pixels less than <i>x'_i</i> in the transformed image is equal to the proportion of image pixels less than <i>x_i</i> in the original image, and that moreover the histogram of the output image is uniform. This implies: <maths id="math0009" num="(9)"><math display="block"><msubsup><mo>∫</mo><mn>0</mn><msub><mi>x</mi><mi>i</mi></msub></msubsup><mo>⁢</mo><mi>p</mi><mfenced><mi>x</mi></mfenced><mo>⁢</mo><mi mathvariant="italic">dx</mi><mo>=</mo><msubsup><mo>∫</mo><mn>0</mn><msubsup><mi>x</mi><mi>i</mi><mi>ʹ</mi></msubsup></msubsup><mo>⁢</mo><mi>q</mi><mfenced><mi>x</mi></mfenced><mo>⁢</mo><mi mathvariant="italic">dx</mi><mo>=</mo><mfrac><msub><mi mathvariant="italic">N</mi><mi mathvariant="italic">pix</mi></msub><msub><mi mathvariant="italic">x</mi><mi mathvariant="italic">max</mi></msub></mfrac><mo>⁢</mo><msubsup><mo>∫</mo><mn>0</mn><msubsup><mi>x</mi><mi>i</mi><mi>ʹ</mi></msubsup></msubsup><mo>⁢</mo><mi mathvariant="italic">dx</mi></math><img file="EP1520397B1_D0009.tif" /></maths> where <i>p(x)</i> and <i>q(x)</i> are the histograms of the original and transformed images respectively. Evaluating the right-hand integral we obtain: <maths id="math0010" num="(10)"><math display="block"><mfrac><msub><mi mathvariant="italic">x</mi><mi mathvariant="italic">max</mi></msub><msub><mi mathvariant="italic">N</mi><mi mathvariant="italic">piz</mi></msub></mfrac><mo>⁢</mo><msubsup><mo>∫</mo><mn>0</mn><msub><mi>x</mi><mi>i</mi></msub></msubsup><mo>⁢</mo><mi>p</mi><mfenced><mi>x</mi></mfenced><mo>ⅆ</mo><mi>x</mi><mo>=</mo><msubsup><mi>x</mi><mi>i</mi><mi>ʹ</mi></msubsup></math><img file="EP1520397B1_D0010.tif" /></maths>

0025Equation (10) tells us that to histogram equalise an image we transform pixel values such that a value x_i in the original image is replaced by the proportion of pixels in the original image which are less than or equal to x_i. A comparison of Equation (8) and Equation (10) reveals that, disregarding notation, the two are the same, so that our invariant image is obtained by simply histogram equalising each of the channels of our original image.

0026In the context of image enhancement it is argued [20] that applying an equalisation to the channels of a colour image separately is inappropriate since this can produce significant colour shifts in the transformed image. However our context we are interested not in the visual quality of the image but in obtaining a representation which is illuminant and/or device invariant. Histogram equalisation achieves just this provided that the rank ordering of sensor responses is itself invariant to such changes. In addition, by applying histogram equalisation to each of the colour channels we maximise the entropy in each of those channels. This in itself seems desirable since our intent in computer vision is to use the representation to extract information about the scene and thus maximising the information content of our scene representation ought to be helpful in itself.

4 Invariance of Rank Ordering

0027The analysis above shows that the illuminant invariance of histogram equalised images follows directly from the assumption of a diagonal model of illumination change (Equation (2)). But the method does not require Equation (2) to hold to provide invariance. Rather, we require only that rank orderings of sensor responses remain (approximately) invariant under a change in illumination. In fact, the method is not restricted to a change in lighting but to any transformation of the image which leaves rank orderings unchanged. Consider for example Equation (3) which allows the image formation process to include an arbitrary non-linear transform (denoted by <i>f()</i>) of sensor responses). Different transforms <i>f()</i>, lead of course to different images. But note that, the rank ordering of sensor responses will be preserved provided that <i>f()</i> is a monotonic increasing function. Thus, histogram equalised images are invariant to monotonic increasing functions. This fact is important because many of the transformations such as gamma or tone-curve corrections which are applied to images, satisfy the condition of monotonicity.

0028To investigate further the rank invariance of sensor responses we conducted a similar experiment to that of Dannemiller [2] who investigated to what extent the responses of cone cells in the human eye maintain their rank ordering under a change in illumination. He found that to a very good approximation rank orderings were maintained. Here, we extend the analysis to investigate a range of different devices in addition to a range of illuminants. To investigate the invariance of rank orderings of sensor responses for a single device under changing illumination we proceed as follows. Let <i>R_k</i> represent the spectral sensitivity of the <i>k</i>th sensor of the device we wish to investigate. Now suppose we calculate (according to Equation (1)) the responses of this sensor to a set of surface reflectance functions under a fixed illuminant <i>E¹</i>(λ). We denote those responses by the vector <i>P¹_k</i>. Similarly we denote by <i>P²_k</i> the responses of the same sensor to the same surfaces viewed under a second illuminant <i>E²</i>(λ). Next we define a function <i>rank()</i> which takes a vector argument and returns a vector whose elements contain the rank of the corresponding element in the argument.

0029Then, if sensor responses are invariant to the illuminants <i>E¹</i> and <i>E²,</i> the following relationship must hold: <maths id="math0011" num="(11)"><math display="block"><mi mathvariant="italic">rank</mi><mfenced><msubsup><mi>P</mi><mi>k</mi><mn>1</mn></msubsup></mfenced><mo>=</mo><mi mathvariant="italic">rank</mi><mfenced><msubsup><mi>P</mi><mi>k</mi><mn>2</mn></msubsup></mfenced></math><img file="EP1520397B1_D0011.tif" /></maths>

0030In practice the relationship in Equation (11) will hold only approximately and we can assess how well the relationship holds using Spearman's Rank Correlation coefficient which is given by: <maths id="math0012" num="(12)"><math display="block"><mi>ρ</mi><mo>=</mo><mn>1</mn><mo>-</mo><mn>6</mn><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mfrac><msubsup><mi>d</mi><mi>j</mi><mn>2</mn></msubsup><mrow><msub><mi>N</mi><mi>s</mi></msub><mo>⁢</mo><mfenced><msubsup><mi>N</mi><mi>s</mi><mn>2</mn></msubsup><mo>-</mo><mn>1</mn></mfenced></mrow></mfrac></math><img file="EP1520397B1_D0012.tif" /></maths> where <i>d_j</i> is the difference between the <i>j</i>th elements of <i>rank</i> (<i>P¹_k</i>) and <i>rank</i> (<i>P²_k</i>) and <i>N_s</i> is the number of surfaces. This coefficient takes a value between 0 and 1: a coefficient of zero implies that Equation (11) holds not at all, while a value of one will be obtained when the relationship is exact. Invariance of rank ordering across devices can be assessed in a similar way by defining two vectors: <i>P¹_k</i> defined as above and <i>Q_k</i> representing sensor responses of the <i>k</i>th class of sensor of a second device under the illuminant <i>E¹.</i> By substituting these vectors in Equation (12) we can measure the degree of rank correlation. Finally we can investigate rank order invariance across device and illumination together by comparing, for example, the vectors <i>P²_k</i> and <i>Q¹_k</i>.

0031We conducted such an analysis for a variety of imaging devices and illuminants, taking as our surfaces, a set of 462 Munsell chips [21] which represent a wide range of reflectances that might occur in the world. For illuminants we chose 16 different lights, including a range of daylight illuminants, Planckian blackbody radiators, and fluorescent lights, again representing a range of lights which we will meet in the world. Finally, we used the spectral sensitivities of the human colour matching functions [21] as well as those of four digital still cameras and a flatbed scanner. <tables id="tabl0001" num="0001"><table frame="all"><title>Table 1: Spearman's Rank Correlation Coefficient for each sensor of a range of devices. Results are averaged over all pairs of a set of 16 illuminants.</title><tgroup cols="4"><colspec colnum="1" colname="col1" colwidth="40mm" /><colspec colnum="2" colname="col2" colwidth="42mm" /><colspec colnum="3" colname="col3" colwidth="43mm" /><colspec colnum="4" colname="col4" colwidth="43mm" /><thead><row><entry align="center" valign="top" /><entry align="center" valign="top">1^st Sensor</entry><entry align="center" valign="top">2^nd Sensor</entry><entry align="center" valign="top">3^rd Sensor</entry></row><row><entry namest="col1" nameend="col4" align="center" valign="top">Across Illumination</entry></row></thead><tbody><row><entry>Colour Matching Functions</entry><entry align="char" char="." charoff="5">0.9957</entry><entry align="char" char="." charoff="5">0.9922</entry><entry align="char" char="." charoff="5">0.9992</entry></row><row><entry>Camera 1</entry><entry align="char" char="." charoff="5">0.9983</entry><entry align="char" char="." charoff="5">0.9984</entry><entry align="char" char="." charoff="5">0.9974</entry></row><row><entry>Camera 2</entry><entry align="char" char="." charoff="5">0.9978</entry><entry align="char" char="." charoff="5">0.9938</entry><entry align="char" char="." charoff="5">0.9933</entry></row><row><entry>Camera 3</entry><entry align="char" char="." charoff="5">0.9979</entry><entry align="char" char="." charoff="5">0.9984</entry><entry align="char" char="." charoff="5">0.9972</entry></row><row><entry>Camera 4</entry><entry align="char" char="." charoff="5">0.9981</entry><entry align="char" char="." charoff="5">0.9991</entry><entry align="char" char="." charoff="5">0.9994</entry></row><row><entry>Scanner</entry><entry align="char" char="." charoff="5">0.9975</entry><entry align="char" char="." charoff="5">0.9989</entry><entry align="char" char="." charoff="5">0.9995</entry></row></tbody></tgroup><tgroup cols="4"><colspec colnum="1" colname="col1" colwidth="40mm" /><colspec colnum="2" colname="col2" colwidth="42mm" /><colspec colnum="3" colname="col3" colwidth="43mm" /><colspec colnum="4" colname="col4" colwidth="43mm" /><thead><row><entry namest="col1" nameend="col4" align="center" valign="top">Across Devices</entry></row><row><entry valign="top">Illuminant</entry><entry align="center" valign="top">1^st Sensor</entry><entry align="center" valign="top">2^nd Sensor</entry><entry align="center" valign="top">3^rd Sensor</entry></row></thead><tbody><row><entry>Daylight (D65)</entry><entry align="char" char="." charoff="5">0.9877</entry><entry align="char" char="." charoff="5">0.9934</entry><entry align="char" char="." charoff="5">0.9831</entry></row><row><entry>Fluorescent (cwf)</entry><entry align="char" char="." charoff="5">0.9931</entry><entry align="char" char="." charoff="5">0.9900</entry><entry align="char" char="." charoff="5">0.9710</entry></row><row><entry>Tungsten (A)</entry><entry align="char" char="." charoff="5">0.9936</entry><entry align="char" char="." charoff="5">0.9814</entry><entry align="char" char="." charoff="5">0.9640</entry></row></tbody></tgroup><tgroup cols="4"><colspec colnum="1" colname="col1" colwidth="40mm" /><colspec colnum="2" colname="col2" colwidth="42mm" /><colspec colnum="3" colname="col3" colwidth="43mm" /><colspec colnum="4" colname="col4" colwidth="43mm" /><thead><row><entry namest="col1" nameend="col4" align="center" valign="top">Across Device and Illuminant</entry></row></thead><tbody><row><entry /><entry align="center">0.9901</entry><entry align="center">0.9886</entry><entry align="center">0.9774</entry></row></tbody></tgroup></table></tables>

0032Table 1 summarises the results for the case in which sensor is fixed and illumination is allowed to change, using the measure defined by Equation (12). Values are shown for each device averaged over all 16 illuminants in our illuminant set, for three illuminants (daylight, fluorescent, and tungsten) averaged over all devices, and for all devices and illuminants. In all cases, the results show a very high degree of correlation: average correlation never falls below 0.964 which represents a high degree of correlation. Minimum correlation over all devices and illuminants was 0.9303 for the 1^st sensor, 0.9206 for the 2^nd sensor and 0.8525 for the 3^rd. Thus on the basis of these results we conclude that rank orderings are preserved to a very good approximation across a change in either or both, device and illumination.

5 An Application to Colour Indexing

0033To test the invariance properties of histogram equalisation further we applied the method to an image retrieval task. Finlayson <i>et al</i> [3] recently investigated whether existing invariant approaches were able to facilitate good enough image indexing across a change in either, or both illumination and device. Their results suggested that the answer to this question was no. Here we repeat their experiment but using histogram equalised images as our basis for indexing to investigate what improvement, if any, the method brings. <tables id="tabl0002" num="0002"><table frame="all"><title>Table 2: Average Match Percentile results of the indexing experiment for four different cases: (1) Across Illumination, (2) Across cameras, (3) Across scanners, and (4) Across all devices.</title><tgroup cols="5"><colspec colnum="1" colname="col1" colwidth="32mm" /><colspec colnum="2" colname="col2" colwidth="34mm" /><colspec colnum="3" colname="col3" colwidth="34mm" /><colspec colnum="4" colname="col4" colwidth="34mm" /><colspec colnum="5" colname="col5" colwidth="34mm" /><thead><row><entry valign="top">Colour Model</entry><entry align="center" valign="top">Case (1)</entry><entry align="center" valign="top">Case (2)</entry><entry align="center" valign="top">Case (3)</entry><entry align="center" valign="top">Case (4)</entry></row></thead><tbody><row><entry>RGB</entry><entry align="char" char="." charoff="11">63.23</entry><entry align="char" char="." charoff="11">71.85</entry><entry align="char" char="." charoff="11">98.88</entry><entry align="char" char="." charoff="11">65.53</entry></row><row><entry>Greyworld</entry><entry align="char" char="." charoff="11">93.96</entry><entry align="char" char="." charoff="11">94.22</entry><entry align="char" char="." charoff="11">99.34</entry><entry align="char" char="." charoff="11">92.28</entry></row><row><entry>Hist Eq.</entry><entry align="char" char="." charoff="11">96.72</entry><entry align="char" char="." charoff="11">95.52</entry><entry align="char" char="." charoff="11">98.94</entry><entry align="char" char="." charoff="11">94.54</entry></row></tbody></tgroup></table></tables>

0034The experiment is based on a database of images of coloured textures captured under a range of illuminants and devices and described in [4]. In summary there are 28 different coloured textures each captured under six different devices (4 cameras and 2 scanners). In addition each camera was used to capture each of the textures under 3 different lights so that in total there are (3 x 4 + 2) x 28 = 392 images. In image indexing terms this is a relatively small database and it is chosen because it allows us to investigate performance across a change in illumination and device. In our experiments we tested indexing performance across three different conditions: <b>(1)</b> across illumination, <b>(2)</b> across homogenous devices, and <b>(3)</b> across heterogeneous devices <b>(4).</b> In each case the experimental procedure was as follows. First, we choose a set of 28 images all captured under the same conditions (same device and illuminant) to be our image database. Next we select from the remaining set of images a subset of appropriate query images. So, if we are testing performance across illumination, we select as our query images the 56 images captured by the device corresponding to the database images, under the two non-database illuminants. Then for all database and query images we derive an invariant image using either the histogram equalisation method set forth above, or one of a range of previously published [9, 5, 6, 10, 18] invariant methods. Finally we represent the invariant image by its colour distribution: that is, by a histogram of the pixel values in the invariant image. All results reported here are based on 3-dimensional histograms of dimension 16 x 16 x 16.

0035Indexing is performed for a query image by comparing its histogram to each of the histograms of the database images. The database image whose histogram is most similar to the query histogram is retrieved as a match to the query image. We compare histograms using the intersection method described by Swain <i>et al</i> [19] which we found to give the best results on average. Indexing performance is measured using average match percentile [19] which gives a value between 0 and 100%. A value of 99% implies that the correct image is ranked amongst the top 1% of images whilst a value of 50% corresponds to the performance we would achieve using random matching.

0036Table 2 summarises the average match percentile results for the four different conditions. In addition to results for histogram equalisation we also show results based on histograms of the original images (<i>RGB</i>), and on Greyworld normalised images, that is on images calculated according to Equation (3). Results for a variety of other invariant representations can be found in [3]: all perform significantly worse than Greyworld. Significantly histogram equalisation outperforms Greyworld for all conditions. Histogram equalisation results across a change in illumination are very good: an AMP of close to 97% as compared to 94% for the second best method. Results of matching across homogeneous devices (Cases 2 and 3 in Table 2) show that both Greyworld and histogram equalisation perform similarly with histogram equalisation performing slightly better on average. Finally across heterogeneous devices histogram equalisation performs best.

0037While the results are quite good: the histogram equalisation method clearly outperforms all other methods on average, the experiment does raise a number of issues. First, it is surprising that one of the simplest invariants -- Greyworld-performs as well as it does, whilst other more sophisticated invariants perform very poorly. This performance indicates that for this dataset a diagonal scaling of sensor responses accounts for most of the change that occurs when illuminant or device is changed. It also suggests that any non-linear transform applied to the device responses post-capture (the function <i>f()</i> in Equation (2)) must be very similar for all devices: most likely a simple power function is applied. Secondly, we might have expected that histogram equalisation would have performed somewhat better than it does. In particular, while illumination invariance is very good, device invariance is somewhat less than we might have hoped for given the analysis in Section 4. An investigation of images for which indexing performance was poor reveals a number of artefacts of the capture process which might account for the performance. First, a number of images captured under tungsten illumination have values of zero in the blue channel for many pixels. Second, a number of the textures have uniform backgrounds but the scanning process introduces significant non-uniformities in these regions. For both cases the resulting histogram equalised images are far from invariant. Excluding these images leads to a significant improvement in indexing performance. However, for an invariant image representation to be of practical use in an uncalibrated environment it must be robust to the limitations of the imaging process. Thus we have reported results including all images. And we stress again in summary, that the simple technique of histogram equalisation, posited only on the invariance of rank ordering across illumination and/or device outperforms all previous invariant methods and in particular gives excellent performance across changes in illumination.

References

0038<ol id="ol0001"><li>[1] <nplcit id="ncit0002" npl-type="s"><text>J. Bach, C. Fuller, A. Gupta, A. Hampapur, B. Horowitz, R. Humphrey, and R. Jain. The virage image search engine: An open framework for image management. In SPIE Conf. on Storage and Retrieval for Image and Video Databases, volume 2670, pages 76-87, 1996</text></nplcit>.</li><li>[2] <nplcit id="ncit0003" npl-type="s"><text>James L. Dannemiller. Rank orderings of photoreceptor photon catches from natural objects are nearly illuminant-invariant. Vision Research, 33(1):131-140, 1993</text></nplcit>.</li><li>[3] <nplcit id="ncit0004" npl-type="s"><text>G. Finlayson and G. Schaefer. Colour indexing across devices and viewing conditions. In 2nd International Workshop on Content-Based Multimedia Indexing, 2001</text></nplcit>.</li><li>[4] <nplcit id="ncit0005" npl-type="s"><text>G. Finlayson, G. Schaefer, and G. Y. Tian. The UEA uncalibrated colour image database. Technical Report SYS-COO-07, School of Information Systems, University of East Anglia, Norwich, United Kingdom, 2000</text></nplcit>.</li><li>[5] <nplcit id="ncit0006" npl-type="b"><text>G.D. Finlayson, S.S. Chatterjee, and B.V. Funt. Color angular indexing. In The Fourth European Conference on Computer Vision (Vol II), pages 16-27. European Vision Society, 1996</text></nplcit>.</li><li>[6] <nplcit id="ncit0007" npl-type="s"><text>G.D. Finlayson, B. Schiele, and J. Crowley. Comprehensive colour image normalization. In eccv98, pages 475-490, 1998</text></nplcit>.</li><li>[7] <nplcit id="ncit0008" npl-type="b"><text>Graham Finlayson. Coefficient Colour Constancy. PhD thesis, Simon Fraser University, 1995</text></nplcit>.</li><li>[8] <nplcit id="ncit0009" npl-type="b"><text>Brian Funt, Kobus Baxnard, and Lindsay Martin. Is machine colour constancy good enough? In 5th European Conference on Computer Vision, pages 455-459. Springer, June 1998</text></nplcit>.</li><li>[9]<nplcit id="ncit0010" npl-type="s"><text> Brian V. Funt and Graham D. Finlayson. Color Constant Color Indexing. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17(5):522-529, 1995</text></nplcit>.</li><li>[10] <nplcit id="ncit0011" npl-type="s"><text>T. Gevers and A.W.M. Smeulders. Color based object recognition. Pattern Recognition, 32:453-464, 1999</text></nplcit>.</li><li>[11] <nplcit id="ncit0012" npl-type="s"><text>Graham. D. Finlayson, Steven Hordley, and Paul Hubel. Illuminant estimation for object recognition. COLOR research and application, 2002</text></nplcit>. to appear.</li><li>[12] <nplcit id="ncit0013" npl-type="s"><text>G. Healey. Using color for geometry-insensitive segmentation. Journal of the Optical Society of America, A., 6:920-937, 1989</text></nplcit>.</li><li>[13] <nplcit id="ncit0014" npl-type="s"><text>B.A. Maxwell and S.A. Shafer. A framework for segmentation using physical models of image formation. In Computer vision and Pattern recognition, pages 361-368. IEEE, 1994</text></nplcit>.</li><li>[14] <nplcit id="ncit0015" npl-type="s"><text>W. Niblack and R. Barber. The QBIC project: Querying images by content using color, texture and shape. In Storage and Retrieval for Image and Video Databases I, volume 1908 of SPIE Proceedings Series. 1993</text></nplcit>.</li><li>[15] <nplcit id="ncit0016" npl-type="s"><text>C. Poynton. The rehabilitation of gamma. In SPIE Conf. Human Vision and Electronic Imaging III, volume 3299, pages 232-249, 1998</text></nplcit>.</li><li>[16]<nplcit id="ncit0017" npl-type="b"><text> Yogesh Raja, Stephen J. McKenna, and Shaogang Gong. Colour model selection and adaptation in dynamic scenes. In 5th European Conference on Computer Vision, pages 460-474. Springer, June 1998</text></nplcit>.</li><li>[17]<nplcit id="ncit0018" npl-type="s"><text> B. Schiele and A. Waibel. Gaze tracking based on face-color. In International Workshop on Automatic Face- and Gesture-Recognition, June 1995</text></nplcit>.</li><li>[18] <nplcit id="ncit0019" npl-type="s"><text>M. Sticker and M. Orengo. Similarity of color images. In SPIE Conf. on Storage and Retrieval for Image and Video Databases III, volume 2420, pages 381-392,1995</text></nplcit>.</li><li>[19] <nplcit id="ncit0020" npl-type="s"><text>Michael J. Swain and Dana H. Ballard. Color Indexing. International Journal of Computer Vision, 7(1):11-32, 1991</text></nplcit>.</li><li>[20] <nplcit id="ncit0021" npl-type="b"><text>Alan Watt and Fabio Policarpo. The Computer Image. Addison-Wesley, 1997</text></nplcit>.</li><li>[21] <nplcit id="ncit0022" npl-type="b"><text>G. Wyszecki and W.S. Stiles. Color Science: Concepts and Methods, Quantitative Data and Formulas. New York:Wiley, 2nd edition, 1982</text></nplcit>.</li></ol>