Colour pictures appearing in connection with computers are available in different formats and types, and the maximum number of colours varies significantly. The following table shows some common values: Max. number of colours Bits per pixel Palette Designation 2 1 Yes Monochrome 16 4 Yes 4 bit colour 256 8 Yes 8 bit colour 65,536 16 No Hi Colour 16,777,216 24 No True Colour A True Colour picture in non-compressed state takes up a large space in the file system, which can be a reason for reducing the number of colours. However, methods are now available for compressing True Colour pictures without reducing the number of colours, for instance JPEG.

Today mainly two picture formats are available on the Internet, JPEG and GIF.

JPEG is a 24 bit True Colour format and GIF is a format with 2 to 256 colours. If a picture with thousands of colours is to be published on the Internet, it is in most cases convenient to select JPEG, and the present invention concerning a colour palette optimisation may seem superfluous. The GIF format, however, has certain advantages compared with JPEG, viz. the capability of transparence, interlace and animation. Moreover, GIF is very convenient for graphics with a small number of homogeneous colours.

It is sometimes desirable to reduce the number of colours in a GIF picture to a minimum so as to obtain a small file size. A small file size is advantageous on the Internet. Particularly in such cases, it is important to have a good algorithm.

In a GIF application, the present invention can convert a 24 bit colour to 8 bits or fewer with a minimum degradation of the picture quality. The invention need not,

however, be used with a GIF picture, but it may also reduce the number of colours in other applications and then yields an excellent result.

According to the invention, the problems above are solved by the invention being designed as is evident from the appended independent claim. Suitable embodi- ments of the invention appear from the remaining claims.

The invention will now be described in more detail with reference to the accompany- ing drawings, in which Fig. 1 shows an example of a histogram of red colours, Fig. 2 shows a colour cube, a three-dimensional histogram, Fig. 3 shows a colour cube with two colour blocks, Fig. 4 shows the trimming of a colour block, Fig. 5 shows the division of a colour block, Fig. 6 shows how unsuitable division may cause small neighbouring blocks, Fig. 7 shows the combination of small neighbouring blocks, and Fig. 8 shows how a combination may result in overlap.

First, various conceptions that are used in the invention must be defined. In the embodiment of the invention that will be described in more detail below, the input is a True Colour picture, i. e. a rectangle with pixels, each pixel consisting of 24 bits.

Other picture formats that are read can first be converted to such a picture. Alter- natively, the invention may act directly on other picture formats in a corresponding fashion. The palette optimisation according to the invention can be used as soon as the number of colours in the input exceeds the number of colours that are to be presented in the output picture.

In the Example, each pixel is RGB-coded. Other formats can be converted intemally to RGB. This means that the 24 bits are distributed among an 8 bit red level, an 8 bit green level and an 8 bit blue level. The level of an individual colour may then vary between 0 and 255.0 indicates blanked and 255 corresponds to full intensity.

In other applications of the invention it is possible to use other divisions into three colours.

The output is a picture with an indexed colour palette. The output picture has the same width and height as the input picture, and if everything functions as it should,

it looks approximately the same while at the same time the number of colours has decreased significantly.

In the input, the entire colour code for a pixel is stored in the pixel itself. Therefore there is no need for a palette. In the output there is a table with 2 to 256 colour codes (in the Example, with 24 bit RGB). An address, an index, to a code in this table consists of 1 to 8 bits. The colour code table is called a palette, and a pixel in the output picture consists of an index for the palette.

The present invention is essentially a program for optimising the palette, i. e. filling the palette with 24 bit RGB codes which are selected as well as possible. For exam- ple, for a picture of a forest, many different green hues are available in the palette.

Moreover, an output picture is to be produced, where the pixels are an index for the palette, but this is a simpler task.

The invention operates with a three-dimensional histogram of colours. The true his- togram is a three-dimensional colour cube with, in the Example, a red, green and blue level along an axis of its own. You may often see a histogram of one colour level at a time, for instance the red level, see Fig. 1. Showing histograms for the red, green and blue levels separately, however, is a simplification. Fig. 2 illustrates a colour cube-a true 3D histogram.

For each 24 bit colour there is a cell in the colour cube, and in that cell there is stored the number of pixels in the input picture that has precisely that colour. It is possible to imagine that the colour cube contains a"pixel cloud"with varying density.

The colour cube described above has 256 * 256 * 256 = 16,777,216 cells and each cell can be a 32 bit integer. The colour cube then takes slightly more than a 67 megabyte RAM memory. For a theoretic mathematician and/or supercomputer owner this is no problem at all, but in practical use in picture processing it consti- tutes a problem. If, on the other hand, the 24 bit colour is reduced to 18 bits, a cube having 64 * 64 * 64 = 262,144 cells is obtained. Then slightly more than one megabyte is required if each cell has 32 bits, and slightly more than half a mega- byte for cells with 16 bits. This size is quite reasonable. An 18 bit colour is better than Hi Colour and is in fact unnecessarily good for the application in question.

With 16 bits per cell there is a small risk that parts of the colour cube are "saturated", i. e. that some cells hit the ceiling since 216-1 is not more than 65,535.

This does not imply any considerable inconvenience. As a suitable size of the colour cube, 64 * 64 * 64 cells and a sixteen bit integer without sign for each cell are suggested in the present case.

In other applications, it may be convenient to use alternative colour cubes of other sizes. If, for instance, the output picture should only contain colours from the standard Netscape palette, a suitable size of the cube will be 6 * 6 * 6 = 216 cells (and the cells may then have 32 bits since each cell contains more pixels when there are fewer cells).

It must be possible to zero the three-dimensional histogram. Therefore a function must be available, which sets all cells in the colour cube at zero. When a picture then is to be added to the histogram, broadly the following is carried out for all pixels in the picture (input).

* Find the red, green and blue level of the pixel in question.

* Convert the colour levels to suitable indices in the colour cube, for instance round off 8 bits to 6 bits.

The cell indicated by the three indices is incremented by one, unless it is satu- rated.

Continue with the next pixel.

By allowing several pictures to be added to the histogram, it may be possible to optimise a joint palette for them. When working with animations, this may be convenient.

Of course there must be a function for reading cells in the colour cube. The function takes three indices (not colour levels) as arguments and gives the number of pixels in the indicated cell.

The invention may further comprise a number of less important functions. The fol- lowing are Examples of such functions.

* Ignore almost empty Cells There may be a function for zeroing the cells in the colour cube that only contain just a few pixels, say 1 to 10. The function is to be selectable. If the input picture

contains just a few stray pixels with odd colours, it is possible to prevent them from taking up valable place in the completed palette, provided that the stray pixels are of no interest.

If a small picture with uniform colour distribution is optimised, it must be taken care so that one does not zero the entire colour cube or a large part thereof.

'sue) Selectable Saturation If the cells consist of 16 bits, an automatic saturation level of 65,535 pixels per cell is introduced. The user can be allowed to set a saturation level of his own, of say 1,000 to 65,535 pixels. It may then be possible to avoid that large surfaces of uniform colour become too dominating when assigning palette colours.

Colour Cube Statistics The colour cube can also answer some statistic questions, for instance how many pixels it contains in all, how many cells have any content etc. Comprehensive statis- tics, however, are not necessary in this case. Such things as minimum, maximum, average value and standard deviation for red, green and blue are handled by the colour blocks that will be described below.

A colour block is a rectangular subvolume of the colour cube. For each colour cube (there is only one) there are between 1 and 256 colour blocks, see Fig. 3. The maxi- mum size of one colour block is equal to the entire colour cube and the minimum size is a single cell in the colour cube. Each colour block corresponds exactly to a colour in the palette and vice versa. The list containing 1 to 256 colour blocks is the instrument in the palette optimising function according to the invention.

The volume of a colour block can be described as, for instance, six variables which are indices for the colour cube: red_min, redmax,greenmin,greenmax, b)uemin and blue-max.

The palette optimisation according to the invention can be started on the basis of a single colour block of the same size as the entire colour cube. Subsequently a number of steps conceming trimming, cutting and combining to optimise a palette are carried out.

Trimming starts from the fact that a colour block should not be allowed to contain any empty edges. A side containing merely zeroed cells is therefore peeled away,

see Fig. 4 regarding such trimming. Each block has six sides which can be peeled away if they are empty, when necessary in several steps. If a block is quite empty, it will shrink to zero in connection with trimming and be removed. (Quite empty blocks should in fact not be available.) Ignored pixels, see above, may get outside all blocks in connection with trimming.

When a colour in the palette is to be assigned to these pixels later on, one will have to take the colour that happens to be closest.

After trimming, the following statistics variables are already known: red_min, redmax, green_min, green_max, blue_min and blue_max. These are the same variables as describe the size of the block.

Moreover, the following is to be calculated: pixels The total number of pixels in the block. This is one of the two measures of the size of the block. diagonal The length of the body diagonal of the block. This is the other measure of the size of the block and a measure of how disparate colours the block contains. (The volume of the block is not used as a measure since an elongate block can be very large along one axis and still have a small volume.) colour-centre The centre of each side of the block. recentre recentre = (red_min + red_max)/2 <BR> <BR> <BR> <BR> greencentre<BR> <BR> <BR> <BR> <BR> blue-centre colour size The length of each side of the block. redsizeredsize = (red_max + 1)-red_min <BR> <BR> <BR> greensize<BR> <BR> <BR> <BR> <BR> b)uesize colour_average"The average". redaverageco)ouraverage is the average of each colour level in the block. green average

blue_average colour-deviation Standard deviation of each colour level. red-deviation <BR> <BR> <BR> greendeviation<BR> <BR> <BR> <BR> <BR> blue-deviation When the local statistics have been collected for all blocks, some global statistics are to be calculated: pixels_average The average of the number of pixels in the blocks. (The total number of pixels in the cube divided by the number of blocks.) diagonal_average The average of the diagonals of the block.

It is now possible to calculate some further local statistics for each block: pixels-relative = pixels/pixels_average The pixel size of the block in relation to the other blocks. diagonal-relative = diagonal/diagonal_average The diagonal of the block, or"colour size", in relation to the other blocks.

The diagonal and pixel size of the block are two measures which cannot simply be compared with each other and besides they vary in different ways as the volume of the block changes. The purpose of preparing relative sizes is that it should be easier to compare the two measures with each other. Such a comparison is neces- sary since the invention comprises the operation of dividing colour blocks, i. e. that the largest colour block in a selected sense is chosen and divided into two smaller blocks.

As mentioned above, a block has two measures of its size in relation to the other blocks: pixels_relative and diagonal_relative.

It is the user of the program who decides which measure should apply, and it may be possible to choose a compromise. If one chooses, for example, 60% priority to

minimising the diagonals of the blocks and 40% to the pixels, the following is applicable for each block: weighedsize = 0.6 * diagonal-relative + 0.4 * pixels-relative If it is important to have a uniform distribution of the colours in the palette, one chooses a high priority for the diagonal size (colour measure). If it is more important to have a good colour resolution for areas which are large in the picture, one chooses a higher priority for the pixel measure.

The block having the largest weighed size is selected to be divided. A block consist- ing of one cell only is non-divisible and must not be selected to be divided. If there are only one-cell blocks, the palette optimisation must be interrupted prematurely.

When dividing a block, see Fig. 5, the total number of blocks increases by one. The block which is divided is cut into two equal parts with a plane which is perpendicular either to the red, green or blue axis. The largest axis is selected to be divided. Here the size can again be measured in two manners, the length of the side (in cells) or the standard deviation of the corresponding colour level. A weighed average can be calculated in the same way as for weighed-size above. redweighedsize = priority * (redsize/average size) + (1-priority) * (red_deviation/average deviation), where average size and average deviation apply locally to the block.

An easier and maybe more robust measure is red weighed size = priority * red size + (1-priority) * red_deviation.

Or even more robust: redweighedsize = redsize + (1-priority) * red_deviation.

When an axis, red, green or blue, has been selected to be divided, the position of the dividing is to be determined. This may be the centre of the axis or the average of the colour level or a combination thereof, for instance: Reddivide = priority * recentre + (1-priority) * redaverage It should be possible to use the same priority value for selecting the largest block, selecting a dividing axis and selecting a dividing coordinate. The dividing coordinate

is, of course, rounded off to a full number of cells before dividing is carried out. The two new blocks are trimmed and statistically processed. Subsequently a new largest block is selected to be divided.

If the priority for the pixel content of the blocks is zero, the algorithm takes only the cell size of the blocks into consideration. The program can then be speeded up, since it is not necessary to collect detailed pixel statistics.

When the number of blocks has reached a predetermined number, between 2 and 256, the first step of the palette optimisation is terminated. After that, it is possible to proceed to create the palette, cf. further down in the description.

In many cases, however, it is suitable to perform also a second step regarding the combining of small blocks before creating the palette. The fact is that if you are unlucky in the dividing of a block, two small blocks can by mere chance be posi- tioned close to each other when the desired number of blocks has been reached, see Fig. 6. This is not optimal.

By combining the small blocks to one block which still is fairly small, the dividing process may continue one more step, and the available space in the palette can be better used. This procedure can be repeated as long as there are two blocks that can be combined without the combined block being the largest, see Fig. 7. The function is somewhat difficult in terms of combination, but it is not impossible to perform the function. The ambitious user chooses on each occasion the pair of blocks which after the combination yields the absolutely smallest size. When combining blocks there is a certain risk of overlapping blocks, see Fig. 8. Such an overlap can either be permitted or forbidden.

The pixel density for the colour cube is defined as the total number of pixels divided by the volume of the entire colour cube. This density measure can be calcu- lated once and for all and is then constant as the palette optimisation proceeds. In a similar way it is possible to define the pixel density for a colour block but that measure may change somewhat as the block is trimmed, divided or combined.

The pixel density of a block can be standardised by being divided by the pixel density of the entire colour cube. The standardised or relative pixel density, pixel density_relative, is greater than one (>1) if the block is denser than the colour

cube on average, and smaller than one (<1) if the block is thinner than that. The measure does not change when other blocks change their shape.

Using the relative diagonal and pixel content of the blocks involves certain draw- backs. As soon as something happens to a single block, these relative sizes can change for all blocks.

In a possible combination of blocks, a fairly large number of combinatory possibili- ties are to be investigated to find out whether there is a pair of blocks which together have a size that is smaller than the largest individual block. The algorithm is difficult if all blocks have different sizes before and after each possible combina- tion.

It would then be convenient if it would instead be possible to use a size measure which is constant for a certain block as long as the block itself does not change.

The absolute diagonal and the absolute number of pixels are such constant measures but it is difficult to compare them with each other. The diagonal increases linearly with the size of the block while the number of pixels increases approxi- mately with the cube.

The pixel density (relative or absolute) is not immediately dependent on the size of the block. By multiplying the density by the diagonal, a pixel measure is obtained, which has the same dimension as the diagonal. weighedsize = priority * diagonal + (1-priority) * diagonal * pixel density_relative Instead it is possible to use somewhat more cautiously weighedsize = diagonal + (1-priority) * diagonal * pixel density_relative It may be a precautionary measure never to let the size of a block be smaller than its diagonal.

After trimming, dividing and combining, there remains the creating of the palette. On a conceptual plane, there is aiways a one-to-one relationship between the colour blocks and the colours in the palette. The colour for a certain block may be, for instance, reddivide,greendivide and blue_divide as described above. Before these levels are inserted into the palette table, they must be converted to 8 bits for each level. A slightly better colour accuracy can sometimes be achieved if, for

instance, reddivide is not rounded off to an entire cell before it is converted to 8 bits.

Finally, an output picture is constructed, where the pixels consist of indices for the palette. For each pixel, its original RGB value is collected in the input picture. The RGB value is converted to an index for a cell in the colour cube. A colour block is selected, either a block containing the cell, or otherwise the closest block. The index for the palette which corresponds to the selected block is the correct output for the pixel in question.

Additionally, the user can use a dither function when constructing the output picture.

The purpose is to produce apparently more colours by screening. How this is done is known to a person skilled in the art and will not be described here.

If the input consists of several pictures, the output can do so as well. The principes are the same as for a single picture, except that the pixels are read from and written to a plurality of picture rectangles instead of one. When working with GIF anima- tions, one often wants to optimise a joint palette for a series of pictures.

A slightly simpler variant of the algorithm described above has been implemented in Common Lisp on a Texas Explorer II Lisp machine. Pictures from a Teragon picture processing system in a 24 bit colour were shown on the Texas machine, which could show an 8 bit colour. The experiment was successful. The optimisation of the palette functioned well. New versions of the algorithm can be expected to be executed as Windows 95/NT applications or possibly an application in Java.