Patent Description:
In 3D computer graphics, much of the information contained within a scene is encoded as surface properties of 3D geometry. Texture mapping, which is an efficient technique for encoding this information as bitmaps, is therefore an integral part of the process of rendering an image. Textures typically consume a large amount of bandwidth in the rendering pipeline and are therefore often compressed with one of a variety of available hardware-accelerated compression schemes.

It is not usually possible to read directly from textures as the projection of 3D geometry often requires some form of re-sampling. MIP maps, which comprise a sequence of textures, each of which is a progressively lower resolution representation of a given base texture, are used to increase the speed of rendering by allowing some of this re-sampling to be performed offline. This in turn reduces the bandwidth of texture reads by promoting locality of reference among neighbouring samples. A schematic diagram of a MIP map <NUM> is shown in <FIG>. Each successive texture in the sequence of textures <NUM>-<NUM> is half the width and height (i.e. half the resolution) of the previous 2D texture, and the result may be considered as a three-dimensional pyramidal structure with only <NUM>/<NUM> as many samples as the highest resolution texture. Each of these textures <NUM>-<NUM> may be referred to as a 'MIP map level' and each is a representation of the same base texture, but at a different resolution. Although the MIP map levels shown in <FIG> are square, a MIP map does not have to be square (e.g. MIP map levels may be rectangular), nor does it need to be two dimensional, though this is generally the case. These MIP map levels may then be individually compressed with one of a variety of available hardware-accelerated texture compression schemes (e.g. Adaptive Scalable Texture Compression, ASTC, or PowerVR Texture Compression, PVRTC).

When rendering an image using a MIP map, trilinear filtering may be used. Trilinear filtering comprises a combination of two bilinear filtering operations followed by a linear interpolation (or blend). To render an image at a particular resolution (or level of detail), bilinear filtering is used to reconstruct a continuous image from each of the two closest MIP map levels (i.e. the one at a slightly higher resolution than the required resolution and the one at a slightly lower resolution than the required resolution) and then linear interpolation (or blending) is used to produce an image at the intermediate, and required, resolution. Trilinear filtering is the best re-sampling solution supported on all modern graphics hardware. The terms "filtering" and "re-sampling" will be used interchangeably. Alternatively, each of the blending operations may be substituted with "nearest neighbour" sampling, which when applied inter MIP map level only requires a single MIP map level per sample. This form of MIP map sampling produces a poor approximation of the desired texture re-sampling and introduces discontinuities.

Referring back to the example shown in <FIG>, to render an image at a resolution which is higher than the resolution of texture <NUM> but lower than the resolution of texture <NUM>, bilinear filtering is used to reconstruct an image from each of the two textures (or MIP map levels) <NUM>, <NUM> and then a resultant texture is generated by linearly interpolating between the two reconstructed textures.

The embodiments described below are provided by way of example only and are not limiting of implementations which solve any or all of the disadvantages of known methods of encoding and/or decoding texture data. <NPL> describes that H. <NUM>/scalable video coding (SVC) has spatial scalability which can provide various resolution sequences for a single encoded bit-stream. The various resolutions are achievable by up-sampling a lower image resolution sequence. The up-sampling method employed in H. <NUM>/SVC is directly proportional to the video quality. To improve the video quality with an effective up-sampling method, a classified multifilter up-sampling algorithm for H. <NUM>/SVC in spatial scalability which classifies an image region as edges and non-edges was provided. An appropriate filter was applied to up-sample the image. In the scheme, Wiener filter was applied for edges and conventional filter for non-edges within the defined window size to preserve the edges in the up-sampled image sequence. <NPL> describes a scalable extension to the H. <NUM>/AVC video coding standard. The extension allows multiple resolutions of an image sequence to be contained in a single bit stream. In the paper, a spatially scalable extension within the resulting scalable video coding standard is introduced. <CIT> describes techniques for coding information in a scalable video coding (SVC) scheme that supports spatial scalability. In one example, a method for coding video data with spatial scalability comprises up-sampling base layer residual video data to a spatial resolution of enhancement layer residual video data, and coding the enhancement layer residual video data based on the up-sampled base layer residual video data. In accordance with this disclosure, up-sampling base layer residual video data includes interpolating values for one or more pixel locations of the up-sampled base layer residual video data that correspond to locations between different base layer residual video data blocks. <NPL>, discloses a method for rendering directly from compressed textures in hardware and software rendering systems where textures are compressed using a vector quantization (VQ) method , where textures can be decompressed quickly during rendering. An extension to the basic VQ technique for compressing mipmaps is also disclosed.

Embodiments of the invention will be described in detail with reference to the accompanying drawings in which:.

In the following, when the term "embodiment" relates to unclaimed combination of features, said term has to be understood as referring to examples of the present invention.

Existing texture compression formats do not address the common use of variable-rate sampling in texture mapping. MIP maps facilitate variable-rate sampling (as described above) but consist of independently compressed textures which do not exploit the inherent redundancy in information between adjacent MIP map levels. Indeed, it is precisely this redundancy which enables one to trade off computation against storage in the first place. However, in the case of trilinear filtering, this means that adjacent MIP map levels must be decoded separately from non-local regions of memory, with the performance and bandwidth implications that this entails. It has been appreciated by the inventor that it should, after accounting for the effects of texture compression, be possible to derive all of the data from a single map without incurring undue overhead. Image compression formats in general often leverage some form of scale-based representation to model image statistics so one should be able to efficiently combine decoding and re-sampling.

Described herein is a lossy texture compression format, referred to as Differential Texture Compression (DTC), along with a new filtering algorithm, referred to as the Differential Texture Filter (DTF). Differential Texture Compression encodes two distinct 2D textures into a single, combined, compressed format (henceforth referred to as a differential texture or DTC texture). The second encoded texture is required to be twice the width and height of the first, and they are referred to as the "high" and "low" resolution texture respectively, but they are otherwise independent. In addition to the normal spatial coordinates used to parameterize a texture, a differential texture also has, In an analogous fashion to MIP maps, a "level of detail" (dLOD) parameter (bounded by the interval [<NUM>,<NUM>], with '<NUM>' and '<NUM>' representing the high and low resolution textures respectively). The Differential Texture Filter provides an efficient way to accelerate trilinear filtering of pairs of DTC textures using this extra dLOD parameter as input. By choosing appropriate pairs of levels of detail to be compressed together, a MIP map can be constructed from a plurality of DTC textures. A DTC encoded MIP map then provides the flexibility to combine conventional MIP map sampling with DTF sampling, which allows trilinear filtering to be performed over a range of level of detail without the need to read from more than one MIP map level. The methods of generating a DTC texture and corresponding hardware to perform the methods are also described.

There are many effects of using DTC: it can increase the effective number of textures in a MIP map without additional storage cost, it allows for the design of potentially higher quality reconstruction filters through the manipulation of the additional detail (dLOD) parameter, and it reduces or entirely eliminates the need for conventional trilinear filtering. By reducing or eliminating conventional trilinear filtering, use of DTC reduces bandwidth throughout the graphics engine (including to/from main memory) and increases sample throughput (as the overall number of Independent filtering operations is reduced).

<FIG> is a schematic diagram showing an example method of generating a single DTC texture. As shown in <FIG>, a low resolution texture <NUM> (i.e. a low resolution bitmap image) is encoded directly (block <NUM>) using an encoding scheme such as ASTC or ETC (Ericsson Texture Compression). The high resolution texture <NUM> is not encoded directly but instead the low resolution texture <NUM> is used as a predictor and a difference texture is generated (block <NUM>) which comprises, for each texel of the high resolution texture, the difference between this prediction and its true value. In more concrete terms, a prediction stage of the method takes the low resolution texture and generates a prediction texture (block <NUM>), which is twice the width and height of the low resolution texture (thereby matching the high resolution texture). The prediction texture (which may also be referred to as a prediction image) is formed from the low resolution texture using an adaptive interpolator. The difference texture (which may also be referred to as a difference image), which has been generated from the prediction texture and the high resolution texture (in block <NUM>), is then encoded (block <NUM>) alongside data to determine the adaptive interpolator. In the examples described herein a block-based vector quantization scheme is used to encode the difference texture (in block <NUM>); however, an alternative compression scheme may be used. The two encoded textures may then be interleaved (block <NUM>) to ensure locality of reference or they may be stored separately.

The block-based vector quantization scheme which may be used to encode the difference texture (in block <NUM>) discards colour information (effectively applying chroma subsampling to the high resolution image) and uses one, two or more distinct hard-coded vector lookup tables (or dictionaries) to encode groups of 4x2 texels in single entries. It is also responsible for encoding the adaptive interpolation used to generate the prediction texture. Where two or more tables are used, each table may be identified with a prediction mode that determines the form of the adaptive interpolation over a local region and which may be chosen on a per-block basis (i.e. per block of data which is interleaved in block <NUM>) to improve the quality of the results. Where more than two vector lookup tables are available, the lookup tables may be grouped, with different groups (e.g. pairs) of lookup tables being used for different types of difference textures and a particular group may be selected for use based on texture header information.

In various examples, the block-based vector quantization scheme (in block <NUM>) operates on a 4Nx4M difference block (i.e. it comprises 4Nx4M texels at the high resolution), where N and M are integers. Where interleaving is used (in block <NUM>), the values of N and M may be selected such that the size of the difference block matches the size of the blocks used in the encoding of the low resolution texture <NUM> (in block <NUM>), i.e. such that the blocks used in the encoding of the low resolution texture <NUM> comprise 2Nx2M texels. For example, as shown in <FIG>, if ASTC is used to encode the low resolution texture <NUM> (in block <NUM>), the size of the ASTC block <NUM> is 6x6 texels at the lower resolution, so that the matching difference block <NUM> will comprise 12x12 texels, i.e. N=M=<NUM>. If, however, ETC is used to encode the low resolution texture <NUM> (in block <NUM>), the size of the ETC block is 4x4 texels at the lower resolution, so that the matching difference block will comprise 8x8 texels, i.e. N=M=<NUM>. For the purposes of the following explanation, it is assumed that N=M=<NUM>; however it will be appreciated that in an implementation of DTC these parameters may have other values and in some implementations N≠M.

The difference block <NUM> may be subdivided into a plurality of sub-blocks <NUM> each comprising 4x4 texels at the high resolution. These sub-blocks form the basic units of compression and each one is encoded by indexing two vectors from a hard-coded lookup table. A lookup table defines a plurality of 4x2 vectors (e.g. <NUM>4x2 vectors) and so a sub-block can be compressed by splitting the sub-block in half (each half comprising 4x2 texels) and then referencing two vectors from the lookup table. In this way, a sub-block can be compressed to a series of bits which identify the two vectors in the lookup table. To perform the encoding, the encoder may evaluate every possible sub-block encoding in turn, until the best match is found.

The list of available vectors may be increased by having more than one lookup table, for example by having two lookup tables and including an extra bit (or bits, where there are more than two lookup tables) to identify which lookup table was used to encode the block (the same table is used for all the sub-blocks in a difference block). The extra bit may be referred as identifying a 'prediction mode' (because the different sets of vectors are constructed to suit the characteristic statistics of the high resolution differences which will be different depending upon which interpolation mode is used for the low resolution texture) and <FIG> illustrates an example set of available vectors <NUM> where two lookup tables <NUM>, <NUM> are used. In the implementation shown in <FIG>, if the prediction mode bit is set, each high resolution texel will be predicted with a <NUM>/<NUM> blend of nearest neighbour and bilinear interpolation of the low resolution texture and the right set of vectors <NUM> is used. If the prediction mode is not set, pure nearest neighbour sampling is used and the left set of vectors <NUM> is used. In this way, the prediction mode is used to control the adaptive interpolation and to determine which lookup table to use.

Whilst the lookup tables <NUM>, <NUM> shown in <FIG> use different shadings to graphically represent the differences, each entry in a lookup table may comprise <NUM><NUM>-bit two's complement values. In this case, upon retrieval these values must be first sign-extended to <NUM>-bit signed integers, and then rescaled by a factor of <NUM>, for the first half of the table entries (V=<NUM> to V=<NUM>), or by a factor of <NUM>, for the second half (V=<NUM> to V=<NUM>). Two example tables A and B, corresponding to prediction modes <NUM> and <NUM> respectively, are shown below, with each 4x2 entry divided into left (L) and right (R) (2x2) halves and given in hexadecimal notation,.

The list of available vectors may be doubled through the inclusion of an extra flip bit for each vector (i.e. two for each sub-block) which flips each vector <NUM> along its long axis. The sub-block (formed from the two 4x2 vectors) may also be rotated into one of four orientations using rotation bits specified for each sub-block. Furthermore, in some implementations a further bit may be used to indicate that for the entire difference block, the size of the differences are doubied and in other implementations (e.g. where PVRTC or ETC is used) it may be possible to specify whether the differences are doubled or not per 4x2 vector. This may be used to better encode regions of high contrast. By expanding the list of available vectors in this way, it increases the number of possible sub-block encodings (including cycling through each possible orientation) which can be evaluated to find the best match without increasing the size of the look-up tables.

The DTC textures may be generated using the method of <FIG> by an encoder <NUM> as shown in <FIG>. The encoder <NUM> may encode the difference textures offline (in software) or online (in hardware) and if the encoder <NUM> is used to generate a MIP map, its precise structure of will also depend on the properties of the MIP map. The encoder <NUM> comprises an input <NUM> for receiving both the low resolution and the high resolution textures <NUM>, <NUM> or, as described below, one or both of these may be generated within the encoder <NUM>. The encoder <NUM> further comprises a prediction texture generator <NUM> which generates the prediction texture (as in block <NUM>) and difference texture generator <NUM> which generates the difference texture using the prediction texture and the high resolution input texture <NUM> (as in block <NUM>). The encoder <NUM> may comprise two encoder units <NUM>, <NUM>: a first encoder unit <NUM> encodes the low resolution texture <NUM> (as in block <NUM>, e.g. using ASTC, PVRTC or ETC) and a second encoder unit <NUM> encodes the difference texture (as in block <NUM>) using the vector lookup tables which may be stored in a data store <NUM>. If the input low resolution texture is already encoded, then the first encoder <NUM> Is not required and instead the encoder <NUM> comprises a decoder unit which decodes the input encoded low resolution texture so that the prediction texture can be generated (in block <NUM>). An interleaver unit <NUM> within the encoder <NUM> interleaves the blocks of data (as in block <NUM>) i.e. it interleaves an encoded block of the low resolution texture and an encoded difference block and then the encoded data which forms the DTC texture is output via an output <NUM> (e.g. to memory).

In an example, the encoder <NUM> may take a previously ASTC/PVRTC/ETC-compressed MIP map (at the appropriate <NUM>/<NUM> bits per pixel compression rate) as input and use adjacent MIP map levels to generate the difference textures. There is no need to encode the low resolution texture as this has already been done, but interleaving is performed after difference textures are generated (e.g. after all the difference textures have been generated). In an online hardware-based approach, the difference textures may make use of the hardware decoder of both ASTC/PVRTC and DTC to evaluate different encodings. As difference textures can only be generated when adjacent MIP map levels are related by a scale factor of <NUM>, a "full" set of difference textures will only be generated for a "power of two" texture. Once the procedure is complete, the top level texture may be optionally discarded, where retaining it implies the use of bilinear magnification of the top level in place of DTC when the LOD is below zero.

In another example, the encoder <NUM> may take a single texture (or MIP map) and generate the low and high resolution texture pairs in tandem with the encoding (e.g. the input textures <NUM>, <NUM> may be generated in parallel with encoding the low resolution texture in block <NUM>). A number of options will exist for how to produce these textures, including choice of filtering kernel and how to handle odd dimensions. After these textures are produced, the high and low resolution versions of the texture can be input to the difference texture generator and the encoder <NUM> can proceed as described above with reference to <FIG>.

<FIG> also shows a schematic diagram of a decoder/filter unit <NUM> which is used to sample a DTC texture as described above. The decoder/filter unit <NUM> comprises a fetch unit <NUM> which fetches the encoded blocks of data from the DTC texture, a first decoder <NUM> which decodes the encoded blocks of data from the low resolution texture (which may be encoded using ASTC, PVRTC or ETC), a difference decoder <NUM> which recreates the difference texture using hard-coded lookup tables <NUM> and these four elements may be considered to be part of a decoder sub-unit <NUM>. The decoder/filter unit <NUM> further comprises two filtering elements: a pre-filter <NUM> and a bilinear filtering unit <NUM> which may be considered to be part of a filter sub-unit <NUM> (this constitutes the logic of the Differential Texture Filter). Whilst the decoding and filtering techniques described herein may be used together, it will be appreciated that they may also be used independently of each other (e.g. where a different decoding technique or a different filtering technique is used).

The operation of the decoder sub-unit <NUM> can be described with reference to <FIG>. As shown in <FIG>, the decoder sub-unit <NUM> fetches encoded blocks of data (block <NUM>, in the fetch unit <NUM>), where, as described above and shown in <FIG>, encoded blocks of the low resolution texture (e.g. block <NUM>) are interleaved with encoded blocks of the difference texture (e.g. block <NUM>). The decoder sub-unit <NUM> then decodes the encoded blocks of the low resolution texture which have been fetched (block <NUM>, in the first decoder <NUM>) where as described above, the blocks of the low resolution texture may be encoded using ASTC, PVRTC or ETC.

The decoder sub-unit <NUM> also fetches encoded sub-blocks of data from the corresponding encoded difference blocks (block <NUM>, in the fetch unit <NUM>) and although this is shown separately from the fetching of the encoded blocks of the low resolution data (in block <NUM>), the two fetch operations (blocks <NUM> and <NUM>) may be performed at the same time.

The fetch unit <NUM> uses a modified texture lookup function (compared to conventional texture lookups) because although texel coordinates are calculated using the (low resolution) texture dimensions, the fractional coordinates (e.g. two bits) of a sample of interest at position (u,v) cannot be discarded, or simply provided to the bilinear filtering unit <NUM> (as in conventional trilinear filtering) as they are used by the pre-filter <NUM> as described below.

In particular, a conventional bilinear texture lookup maps (u,v) to (u * w - <NUM>, v * h - <NUM>) where w and h are the width and height of the texture respectively. The integral part of these coordinates is used to index four neighbouring texels, applying boundary conditions as necessary. The fractional part is converted to a fixed point value and used for bilinear interpolation.

The modified lookup which is performed by the fetch unit <NUM>, uses the same mapping, with the width and height of the lower resolution texture as the supplied dimensions. Four neighbouring low resolution texels are indexed from the integral parts of the coordinates, as before. The same values are also used to index four neighbouring groups of four differences with their associated prediction modes. The fractional parts of the coordinates are multiplied by <NUM>; the integral parts of the result of the multiplication by <NUM> are sent to the pre-filter <NUM> as two <NUM> bit values and the remaining fractional part (of the result of the multiplication by <NUM>) is sent to the bilinear filtering unit <NUM>.

As a result of each high resolution texture always being twice the width and height of the low resolution texture, each low resolution texel corresponds to four high resolution texels. Each texture fetch (using the method of <FIG>) therefore fetches:.

Using the method of <FIG>, the fetch unit <NUM> can fetch all the required data to perform trilinear filtering with just four addresses, which is the same as for conventional bilinear filtering and this is shown graphically in <FIG> shows, for each of the four texels <NUM> (labelled A-D), one low resolution texel, <NUM> (labelled L, comprising R, G, B and alpha channels, where the alpha channel is shown by the sub-script A), four differences <NUM> and one prediction mode <NUM>. Of the fetched data <NUM>-<NUM>, all the parameters are considered low resolution parameters except for the four difference quads <NUM> and the low resolution parameters can be considered as five 2x2 quads <NUM>-<NUM> - one each for the R, G, B and alpha channels <NUM>-<NUM> and one for the prediction modes <NUM>.

The interleaving of the block data together with the correspondence in texture dimensions means that the encoded blocks cover the same area of a texture (in terms of the (u,v) coordinate system). The filter is trying to mimic trilinear filtering so it needs to fetch the data from each map that would be required to perform this operation. That means that two bilinear patches i.e. a set of four texels are fetched from each map. The nature of trilinear filtering is such that the bilinear texel footprint of the higher resolution map is always a subset of the footprint of the lower resolution map whenever the samples are aligned in a <NUM>:<NUM> ratio. If blocks are fetched such that their union covers the low resolution bilinear texel footprint, then these also cover the high resolution bilinear footprint and all the data needed for trilinear filtering has been fetched.

Referring back to <FIG>, a single sub-block <NUM> is fetched from the encoded difference block <NUM> per texture fetch. The sub-block fetch (in block <NUM>) may operate slightly differently depending upon the precise structure of the difference block (e.g. block <NUM> in <FIG>) and two example difference block layouts are shown in <FIG> and <FIG>. <FIG> shows a first example block data layout <NUM> for a <NUM>-bit difference block and <FIG> shows a second example block data layout <NUM> for a <NUM>-bit difference block. Each layout <NUM>, <NUM> comprises a plurality of encoded sub-blocks <NUM> (denoted SBi and comprising <NUM> bits in the case of DTC <NUM> and <NUM> bits in the case of DTC <NUM>). The <NUM>-bit block <NUM> also comprises a prediction mode bit <NUM> (denoted M) which identifies the lookup table from which the vectors are selected and an optional scaling factor bit <NUM> (denoted A) which indicates whether the differences should be doubled or not (as described above). The <NUM>-bit block <NUM> does not comprise a prediction mode bit and so where multiple lookup tables are available, a default table (and hence a default value for M e.g. M=<NUM>) may be used. The size of the difference block <NUM>, <NUM>, <NUM> may be selected to match the size of the encoded low resolution block <NUM> so that the blocks can be interleaved and this ensures locality of reference.

As shown in <FIG>, the <NUM>-bit difference block <NUM> comprises <NUM> sub-blocks and as shown in <FIG>, the <NUM>-bit difference block <NUM> comprises <NUM> sub-blocks. The sub-block fetch operation (block <NUM>) selects a single sub-block <NUM> from the difference block <NUM>, <NUM> using u,v parameters. The u,v parameters here are the texel offset within each block. The sub-block data layouts <NUM>, <NUM> are also shown in <FIG> and <FIG>. It can be seen that whilst there is a single scaling factor bit (A) for the entire block in the <NUM>-bit example <NUM>, in the <NUM>-bit example <NUM>, the scaling factor <NUM> (denoted Aj where j={<NUM>,<NUM>}) can be set per vector <NUM> (denoted Vj where j={<NUM>,<NUM>}) within a sub-block, where a vector corresponds to half a sub-block. As shown in <FIG> and <FIG>, each sub-block <NUM>, <NUM> comprises two rotation bits <NUM> (denoted R) and a flip bit <NUM> for each vector (denoted Fj where j={<NUM>,<NUM>}).

The sub-block decode operation (block <NUM>, in the difference decoder <NUM>) can be described with reference to <FIG> and once at the sub-block stage, operates in the same way irrespective of the size of the difference block. <FIG> shows a first stage in the sub-block decode operation which uses the lookup tables <NUM>. Based on the value of M (which as described above may be specified on a difference block level or have a default value), the two vectors V<NUM> and V<NUM> are identified (operation <NUM>). The identified vectors are then flipped or not based on the values of F<NUM> and F<NUM> <NUM> (operation <NUM>) and scaled, where required based on the value of the scaling bit(s) (operation <NUM>). If there is only a single scaling bit <NUM> then instead of using A<NUM> and A<NUM> <NUM> (as shown in <FIG>), the single value A <NUM> is used for both vectors V<NUM> and V<NUM>.

<FIG> shows a second stage in the sub-block decode operation in which the two vectors are combined to form the sub-block and the sub-block is rotated based on the two rotation bits R <NUM> (operation <NUM>). A single difference quad <NUM> is then selected from the rotated sub-block using the least significant bits of the u,v coordinates (operation <NUM>).

Although <FIG> and <FIG> show the assembly of a complete sub-block; in various examples it may not be necessary to assemble the whole sub-block.

<FIG> shows a third stage in the sub-block decode operation which identifies a prediction mode for each of the two vectors V<NUM> and V<NUM>. A single value is selected (operation <NUM>) based on the value of M (which as described above may be specified on a difference block level or have a default value). Then two values P<NUM> and P<NUM> (one for each vector) are determined based on the single value (from operation <NUM>) and the values of Vj and Fj (operation <NUM>). This operation ensures that for smooth areas, the prediction mode defaults to bilinear prediction.

The two values P<NUM> and P<NUM> from the third stage are fed into the fourth stage in the sub-block decode operation. As shown in <FIG>, the two values are arranged into a quad based on the two rotation bits R <NUM> (operation. <NUM>), with P<NUM> associated with block A and P<NUM> associated with block B. A single prediction value <NUM> is then selected from the prediction quad (formed in operation <NUM>) using the least significant bits of the u,v coordinates (operation <NUM>).

The operation of the filter sub-unit <NUM> can be described with reference to <FIG>. As shown in <FIG>, the filter sub-unit <NUM> receives the fetched and decoded texel data <NUM> (e.g. as shown graphically in <FIG>) and the first operation applies boundary conditions (block <NUM>) which is shown graphically in <FIG>. The boundary conditions which are applied determine how to stitch the 2x2 difference quads into a 4x4 quad and <FIG> shows <NUM> different ways that the 2x2 difference quads <NUM> (from <FIG>) can be stitched together (as indicated by bracket <NUM>) and depending upon where the texture is sampled, only one of these is used. For the description of subsequent stages of the method herein, the notation shown in quad <NUM> is used irrespective of which of the quads is actually assembled (in block <NUM>).

When sampling along the edge of a texture (e.g. at the top left/right corners, bottom left/right corners or top/bottom/left/right edge), the sampling depends upon which boundary mode is set. Where the boundary mode is set to wrap, the opposite edges of the texture are considered to be connected to each other, e.g. if you are sampling along the right edge of a texture, a bilinear sample from each of the low and high resolution maps may require two texels from the right edge of the texture and a further two texels from the left edge of the texture. The arrangement of the 2x2 difference quads in the case of the boundary mode being set to wrap is shown in <FIG> (example <NUM>) and the same arrangement is used where the interior of the texture is sampled.

If the boundary mode is set to mirror or clamp instead of wrap, the texels on the edge being sampled are duplicated instead of using texels from the opposite edge (e.g. referring back to the earlier example, samples from the right edge may be duplicated instead of using texels from the left edge) as shown in examples <NUM>-<NUM>. Although the mirror and clamp modes are two distinct texture modes, where the former reflects the texture along its boundaries, and the latter restricts the texture to its border outside the [<NUM>, <NUM>] coordinate interval, both modes involve duplication of colours along the texture edges, so they can be handled by the same logic. In particular, if the boundary mode is set to clamp, the outer columns/rows of the patch are never used and so clamping can be thought of as mirroring the texture to handle interpolation across the boundary, but then restricting the texture coordinates so that they cannot exceed one or be less than zero.

The pre-filter <NUM> in the filter sub-unit <NUM> generates both a low resolution patch and a high resolution patch and provides automatic trilinear filtering at low additional complexity as is also described in detail below. The generation of these patches entails sub-division of both low resolution data (two sub-divisions, block <NUM>, as shown in <FIG>), from which the low resolution patch is directly derived, and high resolution data (one sub-division, block <NUM>, as shown in <FIG>), which are combined with the low resolution data to construct the high resolution patch (block <NUM>, as shown in <FIG>). This sub-division is performed so that linear interpolation can be performed on the high and low resolution patches (in block <NUM>, in the pre-filter <NUM>, as shown in <FIG>) before bilinear interpolation.

Low resolution parameter sub-division (block <NUM>) can be described with reference to <FIG>. As described above, the low resolution parameters comprise five 2x2 quads <NUM>-<NUM> and each is treated in the manner shown in <FIG> and consequently, the method of <FIG> is shown for a generic 2x2 quad with the elements labelled A-D and where this may be any of the quads of low resolution parameters <NUM>-<NUM>; however, as noted below, dependent upon which quad is being sub-divided, the second sub-division <NUM> may follow one or both of two parallel paths.

The low resolution parameter sub-division (in block <NUM>) comprises performing two sub-division steps <NUM>, <NUM> on a low resolution 2x2 quad <NUM>. The first sub-division <NUM> uses bilinear sub-division and generates a 3x3 quad <NUM> from the input 2x2 quad <NUM>, where the four corner blocks (NW, NE, SE, SW) have the same values as the four values in the input 2x2 quad <NUM> (A, B, D, C respectively), the centre block (X) is a ¼ blend of each of the four values A-D and the other four blocks (N, E, S, W) are a half-blend of their two immediate neighbours (e.g. N is a ½ blend of A and B, E is a ½ blend of B and D, etc.).

The resultant 3x3 quad <NUM> is then sub-divided in a second sub-division step <NUM> and depending upon which quad of low resolution parameters <NUM>-<NUM> parameters, this may involve one or both of the two separate operations shown (and which use different sub-division techniques) to generate one or two 5x5 quads <NUM>, <NUM>. One 5x5 quad <NUM> is formed using bilinear sub-division in a similar manner to the generation of the 3x3 quad <NUM> (e.g. such that the block between blocks NW and N is a ½ blend of NW and N). The other 5x5 quad <NUM> is formed using nearest neighbour sub-division and so the newly created sub-divided blocks are clamped to their nearest corner. A 2x2 quad <NUM> selected from each generated 5x5 quad based on coordinates which are labelled u, u+<NUM>, v and v+<NUM> in <FIG> and which are the top two bits of the fractional u,v, coordinates generated in the texture lookup described above.

As noted above, the low resolution parameter sub-division, as shown in <FIG>, is repeated for each of the low resolution 2x2 quads <NUM>-<NUM> and different quads follow different paths in the second sub-division step <NUM>. Parameters LR, LG and LB (quads <NUM>, <NUM>, <NUM>) take both the 'nearest neighbour' path and the 'bilinear' path and so generate two 5x5 quads <NUM>, <NUM>. A 2x2 quad <NUM> is then selected from each of these generated 5x5 quads <NUM>, <NUM>. Of these, the LR, LG and LB quads that followed the nearest neighbour path are henceforth relabelled as BR, BG and BB to disambiguate them from those that followed the bilinear path, which remain LR, LG and LB. Parameters P (quad <NUM>) only take the 'nearest neighbour' path and so generate a single 5x5 quad <NUM> from which a 2x2 quad <NUM> is then selected. Parameters LA (quad <NUM>) only take the 'bilinear' path and so generate a single 5x5 quad <NUM> from which a 2x2 quad <NUM> is then selected. No further processing is required for the LA parameter quad (block <NUM>) before the final bilinear interpolation (block <NUM>) and so it bypasses all further stages and is consequently relabelled as XA, to match the other bilinear channels output in in <FIG>.

The differential generation (in block <NUM>) involves a single sub-division as can be described with reference to <FIG>. The input is the 4x4 difference quad <NUM> as generated by applying the boundary conditions (in block <NUM>). Bilinear sub-division is used and this results in a 5x5 quad from which a 2x2 quad <NUM> is selected using the same coordinates as used in the low resolution parameter sub-division (in block <NUM>).

The high resolution patch generation (in block <NUM>) can be described with reference <FIG>. It involves, for each of the RGB channels, linear interpolation (indicated by bracket <NUM>) of the 2x2 quads <NUM> generated by low resolution parameter sub-division (in block <NUM>) followed by the addition (indicated by bracket <NUM>) of the difference 2x2 quad <NUM> generated in the differential generation (in block <NUM>) and the output is one 2x2 quad <NUM>-<NUM> for each of the RGB channels. The resultant 2x2 quads <NUM>-<NUM> are at the high resolution. These values may then be clamped to ensure they remain within the range of possible values (<NUM> to <NUM> for LDR textures).

A patch at a required intermediate resolution can then be generated (in block <NUM>) by blending between the high resolution 2x2 quads <NUM>-<NUM> and the sub-divided low resolution quads generated by the low resolution parameter sub-division (in block <NUM>), based on the required intermediate level of detail (dLOD), as shown in <FIG>. The operations shown in <FIG> are performed sequentially: first performing the subtraction (L-H), then multiplication by the intermediate level of detail (x dLOD) before addition of the high resolution values (+H). The same sequence of operations is performed in <FIG> (in bracket <NUM>); it is equivalent to the expression (<NUM>-f)*A + f*B.

The pre-filter <NUM> outputs a single bilinear patch for each of the RGBA channels which is a linear interpolation of the low and high resolution patches generated within the pre-filter (as shown in <FIG>), with the exception of the alpha channel which is generated during the low resolution parameter subdivision <NUM>. This output patch is closer to the target sample location (i.e. for the target level of detail); however, it may not exactly match the target sample position because only the integral parts of the result of the <NUM> times multiplication of the fractional parts of texel address calculation are used (as described above). Consequently any fractional parts of the result of the <NUM> times multiplication are subsequently used by the bilinear filtering unit <NUM> to perform bilinear filtering (block <NUM>) on the output from the pre-filter <NUM> to generate an output patch at the target level of detail (and hence at the target sample locations). If there are no fractional parts then the output from the pre-filter <NUM> (and block <NUM>) is already at the target sample position and no bilinear filtering is required.

As described above, the bilinear filtering unit <NUM> performs bilinear filtering on the output from the pre-filter <NUM>.

Although it is not shown in <FIG>, in various examples, gamma correction may be performed between the output of the pre-filter <NUM> and the input to the bilinear filtering unit. Alternatively, gamma correction can be performed on the down-sampled images (i.e. after the bilinear filtering unit).

Although the methods and apparatus are described above in terms of textures (where a texture is defined as any bitmapped image used in 3D rendering), the methods and apparatus described herein may be more broadly applied to bitmapped images in general.

The encoder and decoder of <FIG> are shown as comprising a number of functional blocks. This is schematic only and is not intended to define a strict division between different logic elements of such entities. Each functional block may be provided in any suitable manner. It is to be understood that intermediate values described herein as being formed by a functional block need not be physically generated by the functional block at any point and may merely represent logical values which conveniently describe the processing performed by the functional block between its input and output.

The encoder and decoder described herein may be embodied in hardware on an integrated circuit. The encoder and decoder described herein may be configured to perform any of the methods described herein. Generally, any of the functions, methods, techniques or components described above can be implemented in software, firmware, hardware (e.g., fixed logic circuitry), or any combination thereof. The terms "module," "functionality," "component", "element", "unit", "block" and "logic" may be used herein to generally represent software, firmware, hardware, or any combination thereof. In the case of a software implementation, the module, functionality, component, element, unit, block or logic represents program code that performs the specified tasks when executed on a processor. The algorithms and methods described herein could be performed by one or more processors executing code that causes the processor(s) to perform the algorithms/methods. Examples of a computer-readable storage medium include a random-access memory (RAM), read-only memory (ROM), an optical disc, flash memory, hard disk memory, and other memory devices that may use magnetic, optical, and other techniques to store instructions or other data and that can be accessed by a machine.

A processor may be any kind of general purpose or dedicated processor, such as a CPU, GPU, System-on-chip, state machine, media processor, an application-specific integrated circuit (ASIC), a programmable logic array, a field-programmable gate array (FPGA), physics processing units (PPUs), radio processing units (RPUs), digital signal processors (DSPs), general purpose processors (e.g. a general purpose GPU), microprocessors, any processing unit which is designed to accelerate tasks outside of a CPU, etc. A computer or computer system may comprise one or more processors. Those skilled in the art will realize that such processing capabilities are incorporated into many different devices and therefore the term 'computer' includes set top boxes, media players, digital radios, PCs, servers, mobile telephones, personal digital assistants and many other devices.

It is also intended to encompass software which defines a configuration of hardware as described herein, such as HDL (hardware description language) software, as is used for designing integrated circuits, or for configuring programmable chips, to carry out desired functions. That is, there may be provided a computer readable storage medium having encoded thereon computer readable program code in the form of an integrated circuit definition dataset that when processed in an integrated circuit manufacturing system configures the system to manufacture an encoder and/or decoder configured to perform any of the methods described herein, or to manufacture an encoder and/or decoder comprising any apparatus described herein. An integrated circuit definition dataset may be, for example, an integrated circuit description.

An integrated circuit definition dataset may be in the form of computer code, for example as a netlist, code for configuring a programmable chip, as a hardware description language defining an integrated circuit at any level, including as register transfer level (RTL) code, as high-level circuit representations such as Verilog or VHDL, and as low-level circuit representations such as OASIS (RTM) and GDSII. Higher level representations which logically define an integrated circuit (such as RTL) may be processed at a computer system configured for generating a manufacturing definition of an integrated circuit in the context of a software environment comprising definitions of circuit elements and rules for combining those elements in order to generate the manufacturing definition of an integrated circuit so defined by the representation.

An example of processing an integrated circuit definition dataset at an integrated circuit manufacturing system so as to configure the system to manufacture an encoder and/or decoder as described herein will now be described with respect to <FIG>.

<FIG> shows an example of an integrated circuit (IC) manufacturing system <NUM> which is configured to manufacture an encoder and/or decoder as described in any of the examples herein. In particular, the IC manufacturing system <NUM> comprises a layout processing system <NUM> and an integrated circuit generation system <NUM>. The IC manufacturing system <NUM> is configured to receive an IC definition dataset (e.g. defining an encoder and/or decoder as described in any of the examples herein), process the IC definition dataset, and generate an IC according to the IC definition dataset (e.g. which embodies an encoder and/or decoder as described in any of the examples herein). The processing of the IC definition dataset configures the IC manufacturing system <NUM> to manufacture an integrated circuit embodying an encoder and/or decoder as described in any of the examples herein.

In other examples, processing of the integrated circuit definition dataset at an integrated circuit manufacturing system may configure the system to manufacture an encoder and/or decoder without the iC definition dataset being processed so as to determine a circuit layout. For instance, an integrated circuit definition dataset may define the configuration of a reconfigurable processor, such as an FPGA, and the processing of that dataset may configure an IC manufacturing system to generate a reconfigurable processor having that defined configuration (e.g. by loading configuration data to the FPGA).

Those skilled in the art will realize that storage devices utilized to store program instructions can be distributed across a network. For example, a remote computer may store an example of the process described as software. A local or terminal computer may access the remote computer and download a part or all of the software to run the program. Those skilled in the art will also realize that by utilizing conventional techniques known to those skilled in the art that all, or a portion of the software instructions may be carried out by a dedicated circuit, such as a DSP, programmable logic array, or the like.

The methods described herein may be performed by a computer configured with software in machine readable form stored on a tangible storage medium e.g. in the form of a computer program comprising computer readable program code for configuring a computer to perform the constituent portions of described methods or in the form of a computer program comprising computer program code means adapted to perform all the steps of any of the methods described herein when the program is run on a computer and where the computer program may be embodied on a computer readable storage medium. Examples of tangible (or non-transitory) storage media include disks, thumb drives, memory cards etc. and do not include propagated signals. The software can be suitable for execution on a parallel processor or a serial processor such that the method steps may be carried out in any suitable order, or simultaneously.

The hardware components described herein may be generated by a non-transitory computer readable storage medium having encoded thereon computer readable program code.

Memories storing machine executable data for use in implementing disclosed aspects can be non-transitory media. Non-transitory media can be volatile or non-volatile. Examples of volatile non-transitory media include semiconductor-based memory, such as SRAM or DRAM. Examples of technologies that can be used to implement non-volatile memory include optical and magnetic memory technologies, flash memory, phase change memory, resistive RAM.

A particular reference to "logic" refers to structure that performs a function or functions. An example of logic includes circuitry that is arranged to perform those function(s). For example, such circuitry may include transistors and/or other hardware elements available in a manufacturing process. Such transistors and/or other elements may be used to form circuitry or structures that implement and/or contain memory, such as registers, flip flops, or latches, logical operators, such as Boolean operations, mathematical operators, such as adders, multipliers, or shifters, and interconnect, by way of example. Such elements may be provided as custom circuits or standard cell libraries, macros, or at other levels of abstraction. Such elements may be interconnected in a specific arrangement. Logic may include circuitry that is fixed function and circuitry can be programmed to perform a function or functions; such programming may be provided from a firmware or software update or control mechanism. Logic identified to perform one function may also include logic that implements a constituent function or sub-process. In an example, hardware logic has circuitry that implements a fixed function operation, or operations, state machine or process.

Any reference to 'an' item refers to one or more of those items. The term 'comprising' is used herein to mean including the method blocks or elements identified, but that such blocks or elements do not comprise an exclusive list and an apparatus may contain additional blocks or elements and a method may contain additional operations or elements. Furthermore, the blocks, elements and operations are themselves not impliedly closed.

The steps of the methods described herein may be carried out in any suitable order, or simultaneously where appropriate. The arrows between boxes in the figures show one example sequence of method steps but are not intended to exclude other sequences or the performance of multiple steps in parallel. Additionally, individual blocks may be deleted from any of the methods. Where elements of the figures are shown connected by arrows, it will be appreciated that these arrows show just one example flow of communications (including data and control messages) between elements. The flow between elements may be in either direction or in both directions.

Claim 1:
A method of encoding image data comprising:
receiving, at an input, a first image and a second image (<NUM>, <NUM>), wherein the second image is twice the width and height of the first image, wherein the first and second images are textures whose pixels are referred to as texels;
generating, in a prediction generator, a prediction image from the first image using adaptive interpolation (<NUM>);
generating, in a difference texture generator, a difference image from the prediction image and the second image (<NUM>);
encoding, in an encoder unit, the difference image (<NUM>), wherein encoding the difference image comprises subdividing a block of the difference image into a plurality of sub-blocks, each sub-block comprising 4x4 texels, and using a block-based vector quantization scheme to encode each sub-block by splitting the sub-block in half, each half comprising 4x2 texels, and indexing a vector from a vector lookup table for each half, wherein an encoded block of data from the difference image either comprises a prediction mode bit which identifies the vector lookup table from which the vector is selected or does not comprise a prediction mode bit in which case a default value of a prediction mode bit is used and a default vector lookup table is used, wherein the prediction mode bit also identifies the adaptive interpolation used to generate the prediction image, wherein the encoded sub-block further comprises additional bits, the additional bits comprising a flip bit for each vector and rotation bits, wherein a flip bit determines whether a vector is flipped along its long axis and rotation bits determine whether the sub-block is rotated into one of four orientations;
encoding the first image (<NUM>); and
interleaving blocks of data from the encoded version of the first image and blocks of data from the encoded difference image to generate compressed image data (<NUM>).