AU769886B2 - Segmenting an image - Google Patents

Description

S&FRef: 545168

AUSTRALIA

PATENTS ACT 1990 COMPLETE SPECIFICATION FOR A STANDARD PATENT

ORIGINAL

Name and Address of Applicant: Actual Inventor(s): Address for Service: Invention Title: Canon Kabushiki Kaisha 30-2, Shimomaruko 3-chome, Ohta-ku Tokyo 146 Japan Delphine Anh Dao Le, Julian Frank Andrew Magarey Spruson Ferguson St Martins Tower,Level 31 Market Street Sydney NSW 2000 Segmenting an Image ASSOCIATED PROVISIONAL APPLICATION DETAILS [33] Country [31] Applic. No(s) AU PQ5932 [32] Application Date 01 Mar 2000 The following statement is a full description of this invention, including the best method of performing it known to me/us:- 5815c SEGMENTING AN IMAGE Technical Field of the Invention The present invention relates to a method and apparatus for segmenting an image. The invention also relates to a computer readable medium comprising a computer program for segmenting an image.

Background Image segmentation is an initial step in many image processing tasks such as pattern recognition, image coding and image interpretation. For example, in scene understanding applications, the segmentation process generally provides a labelling process with regions to be classified.

Ideally, image segmentation is the process of partitioning the image into meaningful segments, ie. regions corresponding to different entities or objects.

Automatic segmentation methods try to find homogeneous regions, for example, regions which have a homogeneous colour distribution.

Most segmentation methods are composed of several steps. For example, region growing methods form a popular class of region-based segmentation methods, which can S"simultaneously take into account the colour distribution in colour space and its repartition S"in the spatial domain. The general procedure is to compare one pixel to its neighbour(s) and ifa homogeneity criterion is satisfied, the pixel is said to belong to the same region as oO0. 20 one or more of its neighbours. However, region growing methods often generate non So smooth boundaries, resulting in small or thin regions, thus it is necessary to go through additional steps like small region elimination, boundary smoothing, etc., each step depending on several parameters.

o.The publication entitled "A multiscale algorithm for image segmentation by variational method" (SIAM J. Numer. Anal., Vol. 31, pp. 282-299, 1994) by Koepfler et o..

al., discloses a multiscale segmentation method based on an energy minimisation process.

With a simple energy function, it is possible, in a unique region merging process, to 545168.doc -2obtain a hierarchy of segmentations with good topological properties, including compactness and smoothness of the solutions.

This unified segmentation method leads to a drastic reduction of the number of parameters to set. Only one scale parameter needs to be chosen at each level of the hierarchy. However, this segmentation method and other similar methods suffer from the disadvantage that the choice of the values of this parameter are arbitrary and are left to the user.

The reference to the publication by Koepfler et al. hereinbefore is not an admission that the contents of that publication in whole or in part constitute common general knowledge.

Summary of the Invention It is an object of the present invention to substantially overcome, or at least ameliorate, one or more disadvantages of existing arrangements.

According to a first aspect of the invention, there is provided a method of segmenting an image, wherein said image is a function g defined over an image domain having a plurality of pixels, the method comprising the steps of: providing the image in a L*a*b colour space; and merging said pixels in accordance with an energy merging criterion 0 oD AE uu uj 2 Ri Rj wherein Ri is the area of a region R; of one or more said pixels, Rj is the area of a region Rj of one or more said pixels, u i is the mean of said function g on said region R,, u. is the mean of said function g on said region Rj, is the length of the common boundary between said region R, and said region Rj, and kk is a multi-scale parameter where k such that X1 (X 2 and wherein a first value X of said S. 25 multi-scale parameter k is chosen so that those adjacent pixels of less than a perceptible colour change are merged.

545168.doc -3- According to a second aspect of the invention, there is provided an apparatus for segmenting an image, wherein said image is a function g defined over an image domain having a plurality of pixels, the apparatus comprising: means for providing the image in a L*a*b colour space; and s means for merging said pixels in accordance with an energy merging criterion AE Ri+ U j ki((Rl, Rj)), Rj wherein Ri, is the area of a region R i of one or more said pixels, Rj is the area of a region Rj of one or more said pixels, ui is the mean of said function g on said region Ri, uj is the mean of said function g on said region Rj, e(a(Ri,R j is the length of the common boundary between said region R i and said region Rj, and Xk is a multi-scale parameter where k such that k 1 (k 2 and wherein a first value X1 of said multi-scale parameter Xk is chosen so that those adjacent pixels of less than a perceptible colour change are merged.

According to a third aspect of the invention, there is provided a computer readable medium comprising a computer program for segmenting an image, wherein said image is a function g defined over an image domain having a plurality of pixels, the computer program comprising: code for providing the image in a L*a*b colour space; and code for merging said pixels in accordance with an energy merging criterion RII R I 20 E= +R ui -U u 1 Ri)), R wherein IR i is the area of a region R, of one or more said pixels, Rjl is the area of a S'.i region Rj of one or more said pixels, u i is the mean of said function g on said region R,, uj is the mean of said function g on said region Rj, is the length of the common boundary between said region R, and said region Rj, and Xk is a multi-scale parameter where k such that k 1 2 and wherein a first value X 1 of said 545168.doc -4multi-scale parameter Xk is chosen so that those adjacent pixels of less than a perceptible colour change are merged.

According to a fourth aspect of the invention, there is provided a method of segmenting an image, wherein said image is a function g defined over an image domain having a plurality of pixels, the method comprising the steps of: providing the image in a L*a*b colour space; and merging said pixels in accordance with an energy function comprising a component favouring autosimilarity, a second component favouring smooth boundaries, and a multiscale parameter Xk, where k 1, 2, such that X\ (X 2 and wherein a first value X, of said multi-scale parameter Xk is chosen so that those adjacent pixels of less than a perceptible colour change are merged.

According to a fifth aspect of the invention, there is provided an apparatus for segmenting an image, wherein said image is a function g defined over an image domain having a plurality of pixels, the apparatus comprising: means for providing the image in a L*a*b colour space; and means for merging said pixels in accordance with an energy function comprising a component favouring autosimilarity, a second component favouring smooth boundaries, ooo. and a multiscale parameter Xk, where k 1, such that Xi (X 2 and wherein a first value Xi of said multi-scale parameter Xk is chosen so that those adjacent pixels of less than a perceptible colour change are merged.

According to a sixth aspect of the invention, there is provided a computer readable medium comprising a computer program for segmenting an image, wherein said image is a function g defined over an image domain having a plurality of pixels, the computer program comprising: code for providing the image in a L*a*b colour space; and code for merging said pixels in accordance with an energy function comprising a component favouring autosimilarity, a second component favouring smooth boundaries, and a multiscale parameter Xk, where k 1, 2, such that Xi 2 (L and wherein a 545168.doc first value X, of said multi-scale parameter Xk is chosen so that those adjacent pixels of less than a perceptible colour change are merged.

Brief Description of the Drawings A number of preferred embodiments of the present invention will now be described with reference to the drawings, in which: Figs 1A and 1B are a flow chart of a method of segmenting an image; and Fig. 2 is a schematic block diagram of a general-purpose computer upon which the preferred embodiment of the present invention can be practiced.

Detailed Description including Best Mode The present invention relates to a segmentation method and apparatus. The input data to this segmentation technique is a pixel-map representation of the image. The pixelmap comprises a numerical representation of a particular colour for each pixel location in a rectangular array. Any numerical representation of colour may be used as long as it is expressed as a sequence of one or more numbers. Preferably, the data information is supplied on a pixel by pixel basis in raster image order, ie. from left to right across a display device and from top to bottom of the display device in a non-interlaced fashion.

Pixel locations at the pixel grid are represented by an array of row and column (x) specifications.

In the Koepfler et al. publication (herein incorporated by reference), the o 20 segmentation problem is formulated as an energy minimisation problem. The energy •function allows the ordering of all possible segmentations. The energy is a real function :oo.

E such that if E(Ki) E(K 2 then the segmentation K 1 is considered better than the segmentation K 2 A segmentation K is defined by a set of boundaries or a set of regions which form a partition of the image.

25 The energy function contains terms that control: 4E The autosimilarity of each region with respect to chosen channels, ie colour; the chosen channels should be constant on each region.

4. The size and regularity of the boundaries.

545168.doc Let the image g be a function defined on the image domain 0; g may be a scalar function (eg. grey level) or a vectorial function, in the case where it has several channels for characterising colours, textures, histograms, etc. Let K be a segmentation of g. The energy function chosen by Koepfler et al. is one of the simplest model, composed of two terms: a two-dimensional term measuring the variance ofg on each connected component Sof V\K and a one-dimensional term for controlling the length of the boundaries: E(u,K) g) 2 dx dy (1) where u is a piecewise constant image on O\K and u is equal to the mean of g on each connected component of Q\K, e(K) is the length of the union of all boundaries in K and X to is a scale parameter. This energy function can be generalised for example by imposing that u is linear or quadratic.

The segmentations provided by Koepfler's region merging algorithm have some good properties like compactness of the set of solutions, elimination of small and thin regions, and smoothness of the boundaries. The algorithm is based on a sequence of scale parameters k 2 XL with Xi X 2 XL and comprises the following steps: Initialise the segmentation with the trivial segmentation where each pixel is a region and X= X 1 (ii) Scan the list of regions and for every candidate region Ri, look for the adjacent region Rj that yields the maximum energy decrease. If such a region exists (ie. for S 20 at least one Rj, there is a decrease in energy), proceed to merge Ri and Rj and update the data structure. The next region in the list becomes a candidate for merging.

For X ki fixed, repeat scanning the image until no merging is possible, ie. there is no pair (Ri, Rj) such that their merging yields a decrease in E.

(iii) For every ki, i iterate step The algorithm stops when only one region 25 remains or after computing a segmentation for the last scale parameter XL.

The merging criterion is a maximum decrease in energy, the energy function being defined as in It can be written as: e* 545168.doc R i R j 2 AE= R I u i UIj ke(a(R,, (2) Ri R wherein JR, is the area of a region Ri of one or more said pixels, IR is the area of a region Rj of one or more said pixels, u is the mean of the function g on said region Ri, uj is the mean of said function g on the region R 1 (a(Ri,R j is the length of the common boundary between the region R, and the region Rj, and Xk is the multi-scale parameter where k The issue of how to choose L and the L values for Xi,i is not in the scope of Koepfler et al. 's publication. However, it is critical for automatic segmentation.

The inventors have recognised that the RGB colour space, which is most frequently used to represent colour images, is far from optimal for measuring the colour differences jUi, uj because it isn't perceptually linear.

The L*a*b* colour space standardised by the CIE (Commission Internationale de l'Eclairage) is defined in such a way that Euclidean distance between two colours is proportional to their visual difference. Moreover, a Euclidean distance equal to one in L*a*b* space is supposed to correspond to a just perceptible colour change.

In the present embodiment, the image segmentation of Koepfler is applied to an image in a L*a*b* colour space format. If the image is initially in a RGB colour space format, then the present embodiment first converts the image to the L*a*b* colour space format prior to applying Koepfler's process.

20 To convert RGB images to L*a*b* format, it is necessary to convert them to XYZ colour space first (the three primaries defined by the CIE), using the following equations (with D65 white point): Z 0.412453 0.357580 0.189423 R Y 0.212671 0.715160 0.072169 G (3) 0.019334 0.119193 0.950227 B Then RGB colour coordinates can be transformed into L*a*b* colour coordinates using .oSee: the following formulae: 545168.doc -8- 1 L*=116 J -16, if 0.008856, (4a) L* 903.3 Y, otherwise; 500f (4b) b= 200 f f (4c) f(t) t 3 if t 0.008856; where 16 f(t) 7.787t+ otherwise.

116 Y, and Z, are the coordinates of the CIELAB reference white, which are usually chosen to be 0.9642, 1.0 and 0.8249 respectively.

At level k of the Koepfler's image segmentation process, two regions R, and Rj will be merged if the criterion AE (see equation is negative; this condition can be written: IUi U 2 k R R Rj) "IRi Rj At the first level, when each region consists of a unique pixel: u i 11-uj <2 1 (6) As the segmentation process is done in a unique merging process (without resplitting), it is preferable to choose the first scale parameter k, so that only pixels of very similar colours are merged 1 =0.252). Namely, pixels in the L*a*b* colour space 20 of less than a perceptible colour change are merged. For the same reason, it is also preferable not to increase Xk too quickly. Preferably, X is also chosen so that a quadratic rate of increase for X, corresponds to a linear rate of increase for ui u 545168.doc -9- ,Xk withr=1.

In this way, there is provided an automatic robust method of segmentation. The method stops when only one region remains or after computing a segmentation for the last scale parameter X, (eg L The preferred embodiment can be generalised to energy functions which are composed of two terms C 1 ?kC2, the first one C 1 favouring the autosimilarlity of a function g (eg. colour) for each region and the second one C 2 favouring smooth boundaries. It is then possible to set the first scale parameter i just below a level of perceptible variation for g in the L*a*b* colour space parameter, and then increase the scale parameter so that the allowed variation for g within a region increases linearly.

Turning now to Figs. 1A and 1B, there is shown a flow chart of a method 100 of segmenting an image. The image comprises a pixel-map representation of an original image. The pixel-map can include a numerical representation of the particular colour for each pixel location in a rectangular array. Any numerical representation of colour can be used and can be expressed as a sequence of one or more numbers (sometimes called the pixel coefficient). Pixel locations at the pixel grid are represented by an array of row (y) and column specifications.

"The method 100 commences at step 102, where any necessary parameters are initialised. The method 100 then proceeds to step 104, where the image is input for 20 processing. If the image is in a format other than L*a*b* colour space format, then the image is converted to the L*a*b* format during this step 104 in the manner described above.

After the method 100 inputs and converts the image if necessary, the method 100 proceeds to step 106, where the method determines a list of initial regions Re of the image S 25 as the region list. Preferably, the initial segmentation of the image is a trivial S•segmentation where each pixel is an initial region and the region list comprises a list of all these initial regions. Each initial region of the list is identified by the co-ordinates of the pixel, the colour components of the pixel, and a flag which indicates whether the 545168.doc associated region Ri has been previously scanned by the method 100. During step 106, all the regions of the list have their associated flags tagged as having not been scanned.

The method then sets 108 a counter variable k to one and sets 109 the scale parameter A to 2 k. The method comprises a loop 110-122-124-123-110 for processing the image for each scale parameter k, Initially, the method sets 109 the scale 2 parameter to A, 0.25 2 In this manner only pixels in the L*a*b* colour space of less than a perceptible colour change are merged. During the passes of the loop 110-122-124- 123-110, the counter k is incremented 122 and Ak is chosen 123 in accordance with the following formula: ,Xk withr=l.

After step 109, the method 100 then proceeds to step 110, where the method 100 gets the first region Ri in the region list having a flag indicating that the region has not been previously scanned. The method 100 then proceeds to step 112, where the method 100 determines that region Rj amongst all the regions adjacent to the current region Ri, which has the lowest value of AE. The value AE for each adjacent region Rj to the current region Ri is determined during this step 112 in accordance with Eqn(2).

The method 100 then proceeds to decision block 114, where the method 100 :determines if the current region Ri and its adjacent region Rj which has the lowest value of S.:i2 AE are candidates for merging. Specifically, the method 100 determines if the current o• lowest value of AE is less than zero. If the decision block 114 returns TRUE (yes), then the method proceeds to step 116, where the method 100 merges the current region Ri and its adjacent region Rj. In this way the current region and its adjacent region which has the lowest value of AE less than zero are merged.

After step 116, the method 100 proceeds to step 118, where the two regions R and S 25 Rj in the region list which have been merged are replaced with the newly merged region.

S"During this step 118, the flag of the newly merged region in the region list is set as having not been previously scanned. The method 100 then proceeds to decision block 117, where a check is made whether there is only one region remaining in the list. If the 545168.doc -11decision block 117 returns TRUE (yes), namely there is only one region remaining in the list, the method 100 proceeds to step 126 where the method 100 terminates. On the other hand, if the decision block 117 returns FALSE the method 100 proceeds to decision block 120.

On the other hand, if the decision block 114 returns FALSE the current region Ri and its adjacent region Rj are not merged, and the method 100 proceeds to step 119, where the flag of the region R, in the region list is tagged as having been scanned. After step 119, the method 100 proceeds to decision block 120.

The decision block 120 determines whether there are any more unscanned regions in the region list. Specifically, the decision block 120 determines whether there are any regions in the region list having flags indicating they have not been scanned. If the decision block 120 returns TRUE (yes), namely there are remaining unscanned regions in the list, then the method 100 returns to step 110, where the method 100 selects the first region in the list that has a flag indicating it has not been scanned. The method 100 then processes this new region in a similar fashion as previously described.

On the other hand, if the decision block 120 returns FALSE namely there are no more unscanned regions in the list, the method 100 proceeds to step 122, where the counter k is incremented by one.

S.:i After step 122, the method 100 proceeds to decision block 124 where a check is 20 made whether k is greater than L. If the decision block 124 returns FALSE the :method 100 then proceeds to step 123 where the scale parameter is set to A 2 k in the manner described above. After step 123, the method 100 then proceeds to step 128, where the flags of all the regions in the region list are cleared, thus indicating all the current regions in the list have not been scanned. After step 128, the method 100 then 25 returns to step 110 for processing of the regions in the list for the new scale parameter.

S"On the other hand, if the decision block 124 returns TRUE(yes), the method 100 then terminates 126.

545168.doc 12- The aforementioned preferred method comprises a particular control flow.

There are many other variants of the preferred method, which uses different control flows without departing the spirit or scope of the invention. Furthermore one or more of the steps of the preferred method may be performed in parallel rather sequential.

The preferred image segmentation method is preferably practiced using a conventional general-purpose computer system 200, such as that shown in Fig. 2 wherein the image segmentation method may be implemented as software, such as an application program executing within the computer system 200. In particular, the steps of the image segmentation method are effected by coded instructions in the software that are carried 1o out by the computer. The software may be stored in a computer readable medium, including the storage devices described below, for example. The software is loaded into the computer from the computer readable medium, and then executed by the computer.

The computer system 200 comprises a computer module 201, input devices such as a keyboard 202 and mouse 203, output devices including a printer 215 and a display device 214. A Modulator-Demodulator (Modem) transceiver device 216 is used by the computer module 201 for communicating to and from a communications network 220, for example connectable via a telephone line 221 or other functional medium. The modem 216 can be used to obtain access to the Internet, and other network systems, such as a Local Area Network (LAN) or a Wide Area Network (WAN).

The computer module 201 typically includes at least one processor unit 205, a memory unit 206, for example formed from semiconductor random access memory (RAM) and read only memory (ROM), input/output interfaces including a video 0interface 207, and an 1/O interface 213 for the keyboard 202 and mouse 203 and optionally a joystick (not illustrated), and an interface 208 for the modem 216. A storage 25 device 209 is provided and typically includes a hard disk drive 210 and a floppy disk drive 211. A magnetic tape drive (not illustrated) may also be used. A CD-ROM drive 212 is typically provided as a non-volatile source of data. The components 205 to 213 of the computer module 201, typically communicate via an interconnected bus 204 and in a 545168.doc 13 manner, which results in a conventional mode of operation of the computer system 200 known to those in the relevant art. Examples of computers on which the embodiments can be practised include IBM-PC's and compatibles, Sun Sparcstations or alike computer systems evolved therefrom.

Typically, the application program of the preferred embodiment is resident on the hard disk drive 210 and read and controlled in its execution by the processor 205.

Intermediate storage of the program and any data fetched from the network 220 may be accomplished using the semiconductor memory 206, possibly in concert with the hard disk drive 210. In some instances, the application program may be supplied to the user encoded on a CD-ROM or floppy disk and read via the corresponding drive 212 or 211, or alternatively may be read by the user from the network 220 via the modem device 216.

Still further, the software can also be loaded into the computer system 200 from other computer readable medium including magnetic tape, a ROM or integrated circuit, a magneto-optical disk, a radio or infra-red transmission channel between the computer module 201 and another device, a computer readable card such as a PCMCIA card, and the Internet and Intranets including email transmissions and information recorded on websites and the like. The foregoing is merely exemplary of relevant computer readable mediums. Other computer readable mediums may be practiced without departing from the scope and spirit of the invention.

S 20 The image segmentation method may alternatively be implemented in dedicated hardware such as one or more integrated circuits performing the functions or sub functions of the method. Such dedicated hardware may include graphic processors, digital signal processors, or one or more microprocessors and associated memories.

Industrial Applicability It is apparent from the above that the embodiment(s) of the invention are applicable to the video and image processing industries.

o 545168.doc 14- The foregoing describes only some embodiments of the present invention, and modifications and/or changes can be made thereto without departing from the scope and spirit of the invention, the embodiment(s) being illustrative and not restrictive.

In the context of this specification, the word "comprising" means "including principally but not necessarily solely" or "having" or "including" and not "consisting only of'. Variations of the word comprising, such as "comprise" and "comprises" have corresponding meanings.

545168.doc

Claims (5)

1. A method of segmenting an image, wherein said image is a function g defined over an image domain having a plurality of pixels, the method comprising the steps of: providing the image in a L*a*b colour space; and merging said pixels in accordance with an energy merging criterion lR y I ,2 AE =R i R Rj)), Ri, IRi wherein JR,/ is the area of a region R i of one or more said pixels, Rj is the area of a region Rj of one or more said pixels, u, is the mean of said function g on said region R i uj is the mean of said function g on said region Rj, R 1 is the length of the common boundary between said region Ri and said region Rj, and Xk is a multi-scale parameter where k 1,2, such that Xi (X 2 and wherein a first value X of said multi-scale parameter Xk is chosen so that those adjacent pixels of less than a perceptible colour change are merged.

2. A method according to claim 1, wherein said first value 1 is equal to 0.252 A method according to claim 1 or 2, wherein said multi-scale parameter 2k Sincreases quadratically. e

4. A method according to claim 3, wherein said multi-scale parameter equals Xk withr=1.

5. A method according to claim 1, wherein said providing step comprises: 25 converting said image from a RGB colour space to said L*a*b colour space.

545168.doc -16- 6. Apparatus for segmenting an image, wherein said image is a function g defined over an image domain having a plurality of pixels, the apparatus comprising: means for providing the image in a L*a*b colour space; and means for merging said pixels in accordance with an energy merging criterion R, IRj 2 AE uR Rj uj 2 Ak(ac(Ri, IR, I+ Rj wherein IR, is the area of a region R i of one or more said pixels, Rj is the area of a region Rj of one or more said pixels, u, is the mean of said function g on said region R,, u. is the mean of said function g on said region Rj, is the length of the common boundary between said region R, and said region Rj, and ?k is a multi-scale 0o parameter where k such that X (X 2 and wherein a first value )1 of said multi-scale parameter Xk is chosen so that those adjacent pixels of less than a perceptible colour change are merged. 7. Apparatus according to claim 6, wherein said first value Xi is equal to 0.252 8. Apparatus according to claim 6 or 7, wherein said multi-scale parameter Xk increases quadratically. 9. Apparatus according to claim 8, wherein said multi-scale parameter equals 20 k withr=l. Apparatus according to claim 6, wherein said providing means comprises: means for converting said image from a RGB colour space to said L*a*b colour space. oooo 545168.doc -17- 1 1. A computer readable medium comprising a computer program for segmenting an image, wherein said image is a function g defined over an image domain having a plurality of pixels, the computer program comprising: code for providing the image in a L*a*b colour space; and code for merging said pixels in accordance with an energy merging criterion AE- =Ril IRj I U i -Ujll 2 VJ(a(Ri, R wherein IR i l is the area of a region R i of one or more said pixels, IRi I is the area of a region Rj of one or more said pixels, u, is the mean of said function g on said region R i Uiis the mean of said function g on said region Rj, I (a(Ri, R j is the length of the common boundary between said region and said region Rj, and Xk is a multi-scale parameter where k such that X, (X2 (XL and wherein a first value X, of said multi-scale parameter X.k is chosen so that those adjacent pixels of less than a perceptible colour change are merged. 12. A computer readable medium according to claim 1 1, wherein said first value X,1 is equal to 0.25 2 13. A computer readable medium according to claim 1 1 or 12, wherein said multi- scale parameter increases quadratically. .o 14. A computer readable medium according to claim 13, wherein said multi-scale parameter equals kk (k -1)r) 2 with r 1. :15. A computer readable medium according to claim 11, wherein said providing 25 code comprises: 01"'"'-code for converting said image from a RGB colour space to said L*a*b colour space. 545168.doc 18- 16. A method of segmenting an image, wherein said image is a function g defined over an image domain having a plurality of pixels, the method comprising the steps of: providing the image in a L*a*b colour space; and merging said pixels in accordance with an energy function comprising a component favouring autosimilarity, a second component favouring smooth boundaries, and a multiscale parameter k, where k 1, such that X, (X (XL and wherein a first value ,1 of said multi-scale parameter Xk is chosen so that those adjacent pixels of less than a perceptible colour change are merged. 17. Apparatus for segmenting an image, wherein said image is a function g defined over an image domain having a plurality of pixels, the apparatus comprising: means for providing the image in a L*a*b colour space; and means for merging said pixels in accordance with an energy function comprising a component favouring autosimilarity, a second component favouring smooth boundaries, and a multiscale parameter Xk, where k 1, such that X1 (k 2 and wherein a first value k, of said multi-scale parameter Xk is chosen so that those adjacent pixels of less than a perceptible colour change are merged. 18. A computer readable medium comprising a computer program for segmenting an image, wherein said image is a function g defined over an image domain having a plurality of pixels, the computer program comprising: code for providing the image in a L*a*b colour space; and code for merging said pixels in accordance with an energy function comprising a 25 component favouring autosimilarity, a second component favouring smooth boundaries, and a multiscale parameter Xk, where k 1, such that X, (k 2 and wherein a first value k, of said multi-scale parameter Xk is chosen so that those adjacent pixels of less than a perceptible colour change are merged. 545168.doc -19- 19. A method of segmenting an image, the method substantially as described herein with reference to the accompanying drawings. 20. Apparatus for segmenting an image, the apparatus substantially as described herein with reference to the accompanying drawings. 21. A computer readable medium comprising a computer program for segmenting an image, the computer program substantially as described herein with reference to the accompanying drawings. DATED this TWENTY-SEVENTH Day of FEBRUARY 2001 CANON KABUSHIKI KAISHA Patent Attorneys for the Applicant SPRUSON FERGUSON 0*S oo** o• 545168.doc