Image compression consists of making a new representation of the image data in digital form that takes up less storage space than the original. Many compression techniques are referred to as being lossy because they do not recover all the original data but instead make some approximation to this.

Often, the pixels that represent an image are stored in what is known as RGB format. This means they are built from three multi bit numbers which respectively represent the amount of red green and blue colours to be applied to a particular pixel. Another colour format is known as YUV. In this colour is encoded such that the brightness of the image is represented by the Y value and can be used to display black and white images whilst the colour is contained in the U and V values. These colour formats can be graphically represented using an orthognal coordinate system to define what is known as colour space.

In some cases translucency data is included with image data. This information is used when one image is shown against another image or a background and the translucency or alpha information is then used to combine one image with the other. This is particularly useful when blending the edge of one image into another. A special type of translucency known as punch-through can be used to switch on and off translucency whilst full variable translucency can be used for objects such as perspex which might have fractional or variable alpha values.

In most compression techniques blocks of pixels are operated on by the compression technique. In this patent

application we will usually be referring to a 4x4 pixel block although the invention may of course apply to any block s ze.

The S3 compression technology referred to above provides a technique of lossy image compression. It contains three different compression schemes known as DXT1, DXT2, and DXT3. The first of these is in principle an opaque method of compression in that its main role is to compress RGB pixels. It does cater for a particular type of translucency known as"punch through"which is used when translucency or alpha value is either on or off.

The other two compression schemes DXT2 and DXT3 are used only for translucency information where the alpha value is between 1 and 0.

DXT1 operates by first splitting the image into blocks of 4x4 pixels. Colours of each of the pixels in the block are analysed and the two points furthest apart in colour space are derived from this. Each of these end points is then represented bv a 16 bit colour value in format RGB565 (meaning 5,6, and 5 bits to each of the R, G and B channels respectively). An index of two bits per pixel is then used to assign a colour value along the line joining the two end points in colour space to each of the pixels in the 4x4 block. The possible values of the index for each pixel are and 11.00 represents one end point and 11 the other. The two other values represent intermediate points along the line which are derived by interpolation during decompression.

The choice of representative colours need not be the two furthest apart values. More complex schemes which iterate to reduce errors could be used, and weightings based on e. g. colour perception and other factors could be applied.

Index values are assigned to each pixel at the compressor by determining which of the four possible colour values corresponds most closely to the original colour value of that pixel. Thus, DXT1 provides a scheme

whereby a block of 4x4 pixels which each originally were represented by, for example, a 24 bit RGB colour value have their image data compressed to two 16 bit colour values and an index of two bits per pixel thereby comprising a total of 64 bits.

Punch through translucency is dealt with in DXT1 by having only one intermediate colour value in colour space and using the fourth index value to determine whether or not the translucency is on or off for a particular pixel.

Thus, there is a reduction in the number of available colours for the 4x4 pixel block and the quality of the representation of colour in the block is thereby reduced when punch-through is selected.

DXT2 is used purely for translucency. It operates merely by restoring the alpha information at a lower precision. Therefore, it does not work particularly well on alpha layers that are stored at high precision.

DXT3 is another compression scheme for storing the alpha data. It does this in a similar manner to the colour method described above. For each 4x4 block two 8 bit alpha values are stored along with a 3 bit per pixel index to select between the two 8 bit alpha values and six interpolated values between these two extremes.

Problems with image quality can arise in schemes such as DXT1 described above when an image block contains an edge between two different colours. As the colour data for the block is generated by only two representative colours it is only possible to represent graduations between the two colours and not graduations of the two colours. Hence the scheme does not compress the image so well and in some cases this can result in the decompressed image having a blocky appearance. This is generally not acceptable.

Preferred embodiments of the present invention seek to reduce the blockiness of schemes such as DXT1 and to improve the visual quality of the image after compression and decompression by reducing visual artefacts as well as

by reducing more easilv measured criteria such as the least squares error.

Embodiments of the invention can also be applied to the other DXT compressions schemes described above which are used for translucency information.

The invention is designed with more precision in the appended claims to which reference should now be made.

A preferred embodiment of the invention will now be described in detail by way of example with reference to the accompanying drawings in which: Figure 1 is block diagram of a compression unit embodying the invention; and d Figure 2 is a block diagram of a decompression unit embodying the invention.

The embodiment described comprises an improvement to the quality of the DXT1 image compression. The basic scheme as described above compresses RGB colour data for a 4x4 pixel block into two RGB565 representative colours totalling 32 bits and a 2 bit index per pixel indicating which interpolated colours to use. This makes another 32 bits giving 64 bits in all.

In Figure 1 which shows a block diagram of the compression stage it can be seen that the original pixels a enter the unit and are compressed according to the Dxtl scheme in the S3 compression unit 2 which outputs a compressed approximation layer f for each block.

In this embodiment the unit 2 also outputs the compression approximation layer at output b to be supplied to a decompression unit 4. This decompresses the compressed approximation layer in the same manner as it would be decompressed normally. The output of this c is the data which would be used to display the original image in decompressed form. This data and the original pixel data a is fed to a subtraction unit 6. This is used to

derive a difference between the original pixels and the decompressed pixels.

Thus, for each pixel there will be a difference for <BR> <BR> <BR> each o the RGB values and. this is provided a an output d. This difference value then passes to a transformation unit 8. This is optional but it will be used in a preferred embodiment The purpose of this transformation unit is to determine the range cf error values for each 4x4 block and to apply a scaling factor to them to ensure that they can subsequently be compressed and transmitted with the compressed image data in a form which will give reasonable accuracy on decompression. The scaling factor applied to the block 1S provided at an output g.

The other output of the transformation unit is the scale values themselves. These are passed to another DXT1 compression unit which compresses the difference pixel data in a manner similar to that of the approximation layer. Two representative difference colours are selected to represent the extremes in colour space of all the difference pixels in the block and are stored in RGB565 format. A 2 bit per pixel index is then used to indicate which out of these two end points and two intermediate points on the line joining these end points should be assigned to each pixel in the block.

Thus, a compressed error layer h is output by unit 10 comprising a further 64 bits in addition to the 64 bits of the compressed approximation layer. The compressed approximation layer, the compressed error layer, and the scaling factor for each block can then be stored or transmitted as required for subsequent decompression.

The system may be simplified by omitting the transformation unit and sending unscaled data.

The number of bits used for the error layer could be greater or fewer than that used for the compressed approximation layer. The bits used to represent the scaling factor are included in the approximation and error layers. The first bit comes from the ordering of

representatives in the approximation layer, e. g. ascending order denotes 1 and descending denotes 0. Similarly the second bit comes from the ordering of representatives in the error layer.

The image data is decompressed in the unit of Figure 2. This operates in the reverse manner to the compression unit.

The approximation layer f passes to a DXT1 decompression unit 12 That provides a decompressed output k. At the same time, the error layer for the equivalent block passes to a DXT1 decompression unit 14 which provides decompressed errors i for each pixel in the block. The scaling factor g passes to the transformation unit 16 which performs the reverse scaling of the transformation unit 8 on the scaled decompressed pixels to provide the unscaled decompressed errors j (this is omitted if unscaled data is sent). The decompressed pixel data k and decompressed error data j is then combined for each pixel in an addition unit 18 to give decompressed and error adjusted pixels at output 1.

The scaling factor stored can scale the error values by a fixed amount per block. This enables the method to dynamically change the range of errors stored in the different block h therebv enabling maximum resolution to be given to each error. The system could be modifie to provide a different scaling factor for each of the RG and B values.

In this particular-mplementation, two bits per block are used to specify which scaling is used out of a set of eg. 16,32,64 and 128, which we refer to as the scaling set. The source of these bits is discussed below.

For example, if the original RGB values in the pixel are (76,87,129) and the approximation layer produces a pixel with value after decompression, then the difference pixel has a value of (6,5,-13). As the maximum absolute difference for each colour component is less than 16, it is applicable to choose the range 16 from

the scaling set to represent all of the errors. The range represented by the number 16 can represent any value between and 15, and hence the value 15, or in the general case the value (range-1) is added to the difference values to give a scaled difference pixel with values (21,20,2) thus, each component is in the range 0- 31 or 0-'range-1 . The number is then scaled so that it occupies the highest possible range of, in this case, 8 bits. In this case, each component will be multiplie by 8 for scaling purposes. Thus, the scaled and translated difference pixel is (168,160,16). With all 16 of the transformed difference pixels in the block being found they are then compressed using the DXT1 method.

Other scaling sets and methods for selecting scaling functions can be used, e. g. maximums, average, or some other measure.

The reverse process follows in the decompression unit. If the decompressed difference pixel of the same pixel as above is (175,155,20), then the scaled back pixel is given by (21,19,3). This then gives the decompressed difference pixel as (6,4,-12). This can then be subtracted from the decompressed values of the original pixel, namely (62,92,116) to give (56,88, 128). Which is much closer to the original pixel value of (56,87,129) than the pixel value in the approximation layer.

It is possible that some values may exceed the largest possible difference value which here is 127. In such a case the errors would be clamped to be within this range.

The two bits that are used to choose the scaling factor from the scaling set are chosen in the same way as the S3 DXT1 compression scheme chooses between regular and punch through blocks. This involves placing the two representative values in either ascending or descending order to indicate whether or not a scaling factor is present, as explained above.

The compression unit shown in Figure 1 could be modified so that only one DXT1 compression unit is required. This would involve the use or a feedback mechanis-to provide. he c mpressed error layer from compression unit 2 as well as the compressed approximation layer. Similarly, in decompression it is possible to use only one decompression unit by providing suitable multiplexing between the error approximation layers and a decompression unit and the transformation unit 16.

The compression scheme can in an alternative embodiment be used with punch through translucency. In this, one value of the index represents a punch through value. The fact that this value exists in the index is represented by the order of the two representative colours or the two error values. the first representative colour or error value stored is a larger value than the second then one of the index values represents punch through. If the representative colours or error values are in the opposite order then all the index values are used to represent points on the line in colour space.

When this is used then the reduction in quality is much less than in the basic DXT1 compression scheme because of the error correction process provided in the embodiment of the invention. In such an arrangement, the two bits used for the scaling function are then provided by using RGB 555 instead of RGB 565 for the approximation error layer representatives. This frees up an additional 2 bits for use as the scaling function. Clearly, the punch through bit could be one of the bits released by RGB 555, as desired in a particular application.

In another embodiment of the invention two layers are again used for transmission. The first of these consists of four pixels which are stored in colour format RGB 444 which takes up total storage of 48 bits. These pixels each represent the average colour in each of the four 2x2 blocks in the 4x4 block. These average pixels are stored explicitly after truncation to RGB 444 format. The second

layer then consist of an error or difference layer which is added to each of the average pixels for correction to a closer approximation to each of the original pixel values.

A scaling 1S applied to each 2x2 sub block to bring all the errors in each sub block into the same range in a manner similar to that described above.

In another embodiment, an error layer is added to the DXT2 or DXT3 schemes for compressing the alpha or translucency value. The method by which this s done is analogous to the method described above. In this, an error layer is added to each DXT3 compression scheme. As described above this scheme produces two 8 bit alpha values for each sub block with an index of 3 bits to a pixel ~o represent intermediate alpha values which are generated from the representative values. This is modified such that the approximation layer consists of two 8 bit alpha values followed by an index of 2 bits per pixel instead of three. The error layer then consists of two 8 bit difference representatives and an index of 2 bits per pixel to point to a total of 4 interpolated difference values generated from the two representative alpha values. The error per block can then be scaled based cn the average or maximum error per block and truncated before compression to give better resolution in blocks with small errors. As in the opaque case, 2 bits result ng from ordering of the representatives can be used to specify a scaling value from a scaling set of size 4.

The invention can be used on pixels which are stored in other colour formats such as YUV. When this is done it can be helpful to split the pixels up into different groups as motivated by the sections of colour components.

Pixels stored in YUV format can be represented using three schemes. Firstly, an approximation of the Y channe is provided using two representatives in a manner similar to the alpha only compression method above and a 2 bit index per pixel. Then a second approximation layer for the U and V channes is provided again using two UV

representatives and a 2 bit index per pixel. Finally, the Y approximation layer-=, corrected with the layer consisting of an error in Y. In this example the UV layers not corrected an t is deemed less important although this could be provided in another embodiment of the invention.

Finding the best two representatives or end points for the pixel error and approximation layers need not necessarily be done by choosing two furthest apart points in colour space. Some form of training and iteration can be used as follows.

Firstly, the best two representatives or end points for the pixels are found without considering the interpolated points between them. This is done by taking the two furthest apart pixels in colour space and then performing a small number of generalised Lloyd algorithm iterations to find a better pair of representatives.

These are the initial configuration or end point values.

Alternatively, we could simply start with the furthest of pixels.

Another way to find the end point codes is to do some multivariate analysis on the pixels, and find the mean and principal direction of the data by taking the eiganvalues of the covariates matrix of the points. At this point, the codes can be accepted and the next stage begins.

Alternatively, a second stage of iteration can be performed by doing a number of iterations where the best fit two end point codes are improved upon. This is done to satisfy a least squares condition with respect to the nearest interpretted codes to the pixels at that given iteration. Finally, the iteration could include some simulated annealing to try and escape the local minima instead of just accepting smaller errors.

Other arrangements could be implemented such as providing an approximation of YUV representatives corrected only with a layer consisting of errors or differences in Y.

This type of image compression and decompression is typicaily used in video graphics such as eg computer games for use in the home and supplied on some form of machine readable data carrier along with software relating to the game. It can be also be used in larger purpose built arcade type video games. It could also be used in realtime video transmissions.

In the games type applications the compression of data is performed before the software is sold. Thus, the compression unit such as the S3 unit would be modified in accordance with an embodiment of the invention either in hardware to provide a unit as shown in figure 1 above or, if all compression is provided in software this would be done by modifying the software used to compress images using S3 technology.