Title of Invention

ALPHA IMAGE PROCESSING

Abstract

An alpha image encoding and decoding scheme is disclosed. In the encoding an alpha image, is decomposed into image blocks (600) comprising multiple image element (610). The blocks (600) are compressed into block representations (700). A block representation (700) comprises at least a color codeword (710), an alpha codeword (720), an alpha modifying codeword (730) and a sequence (740) of alpha modifier indices. The color (710) and alpha (720) codeword (710) are representations of the colors and alpha value of the image elements (610) of the block (600), respectively. The alpha modifying codeword (730) is a representation of a set of multiple alpha modifiers for modifying an alpha value represented by the alpha codeword (720). The index sequence (740) includes an alpha index for each image element (610) in the block (600), where an alpha index identifies one of alpha modifiers in the alpha modifier set.

Full Text

TECHNICAL FIELD The present invention generally refers to image processing, and in particular to methods aijid systems for encoding and decoding images. BACKGROUND Presentation and rendering of images and graphics on data processing systems and user terminals, such as computers, and in particular on mobile terminals have increased tremendously the last years. For example, three-dimensional ,(3D) graphics and images have a number of appealing applications on such terminals, including games, 3D maps and messaging, screen savers 'and man-machine interfaces. A 3D graphics rendering process typically comprises three siib-stages. Briefly, a first stage, the application stage, creates several triangles. The corners of thfese triangles are transformed, projected and lit in a second stage, the gedmetry stage. In a third stage, the rasterization stage, images, often denoted] textures, can be "glued" onto the triangles, increasing the realism of the (rendered image. The third stage typically also performs sorting i using a z-buffer. However, rendering of images and textures, and in particular 3D images and graphics, is a computationally expensive task in terms of memory bandwidth and processing power required for the graphic systems. For example, textures are costly both in terms of memory, the textures must be placed on or cached in fast on-chip memory, and in terms of memory bandwidth, a I texture can be! accessed several times to draw a single pixel. In order to reduce the bandwidth and processing power requirements, an image (texture) encoding method or system is typically employed. Such an encoding system should result in more efficient usage of expensive on-chip memory and lower memory bandwidth during rendering and, thus, in lower power consumption and/or faster rendering. In addition to efficiently and accurately compressing and Decompressing an image, there is a general desire that the texture compression and decompression systems should have the capability of i managing alpha components. Such alpha components can be used to represent transparent or semi-transparent pixels or texels in the textures, which ^re used in a wide range of applications. In a patent description US 5,956,431, lourcha et al. disclose a texture compression scheme called S3TC (S3 Texture Compression) or DXTC (DirectX Texture Compression). An image is decomposed into a number of image blocks of 4 pixels x 4 pixels. Each such image block! is encoded into a bit sequence of 64 bits, thus resulting in a compression irate of 4 bpp (bits per pixel). The 64-bit sequence comprises two basicj colors or color j codewords and a sequence of pixel indices, one index for each pixel in the image block. During decoding, a color palette of four colors! is generated. The first two RGB (red, green and blue) colors of the palette Correspond to the i two basic colors (codewords). The two additional colors, situated between the basic colors in the RGB space, are then interpolated therefrom. Each pixel index then identifies, for each pixel, one of the four colors of the palette to use for that pixel. During the interpolation of the two additional colors of jthe color palette, multiplication by 1/3 and 2/3 is performed, which is not ideal in hardware. In addition, the compression using S3TC is relatively time consuming. The S3TC scheme handles alpha textures as a special casei The bits are then interpreted differently in order to allow for a so-called punfch-through alpha. This simple version of alpha mechanism represents eadh pixel as either being completely opaque or transparent. The fact that S3TC cannot handle more accurate alpha is one of the major drawbacks of the system. SUMMARY The present invention overcomes these and other drawbacks of the prior art arrangements. I It is a general object of the present invention to provide an efficient image processing. It is another object of the invention to provide an efficient image encoding and image decoding. A further object of the invention is to provide image encoding and decoding adapted for alpha images comprising transparent and/or semi-transparent image elements. These and ojther objects are met by the invention as defined by the accompanying patent claims. Briefly, the present invention involves alpha image processing in the form of encoding (conjipressing) an alpha image and decoding (decompressing) an encoded (compressed) image. According to the invention, an alpha image to be encoded is decomposed into I a number of \ image blocks comprising multiple image elements {pixels, texture elemelnts, texels, or volume elements, voxels). An image block preferably comprises eight image elements and preferably has a size of 2mx2n image elements, where m=3-n and nO, 1, 2, 3, or a size of 2mx2nx2P, where m, n, p=0, 1, 2, 3 and preferably m+n+p=3. Each image element in a block is characterized by a color and an alpha or transparency value. The individual ] image blocks are then compressed. In this lossy tilock encoding, a color codeword is determined for the image block. The cojor codeword is a representation of the colors of the image elements of the image block. Furthermore, an alpha codeword is determined for the image block. This alpha codeword is a representation of the alpha values of the image elements in the block. A preferred representation is a quantized average alpha value of the image elements in block. Thereafter, an alpha modifying codeword is provided for the image block. This alpha modifying codeword is a representation of a set of multiple alpha modifiers that are used (during decoding) for modifying or modulating the alpha value represented by the alpha codeword. Once th? alpha modifying codeword is provided, alpha modifier indices are selected for the image elements in the image block. Each such modifier index is with an alpha modifier from the alpha modifier set. In a preferred embodiment of the invention, an image block can be compressed according one of multiple, preferably two, possible compression modes. The use of two different compression modes provides flexibility to the encoding method by being able to better adapt to the properties of the individual image blocks in the alpha image. As a consequence of having a choice, per block basis, between two different compression 'modes, the image quality of the processed image is improved compared to tbJe prior art alpha-adapted encoding schemes with a single-mode encoding. In the first compression mode, a color modifying codeword (is generated. This color modifying codeword is a representation of a set of multiple intensity or color modifiers that are used (during decoding) for modifying or modulating the colors of the image elements in the block. Once the color modifying codeword is provided, color modifier indices are selected for the image elements in the image block. Each such modifier inde Hated with an alpha modifier from the alpha modifier set. In the second compression mode, the color codeword comprises a first color subcodeword and a second color subcodeword. The first color subcodeword preferably represents the colors of the image elements in a first portion of the image block, whereas the second subcodeword represents the colors of the image elements in a second portion of the block. Furthermore, color indices associated with the first or second color subcodeword are preferably generated for a first subset of the image elements in the block. A remaining second subset of th$ image elements in the block preferably has a pre-defined association wjith one of the color subcodewords so that no color index is ; required for trie image element(s) of this remaining subset. Although image block representations compressed according to the two modes include different codewords and image element associated indices, the sizes of the compressed block representations in terms of the number of bits are i preferably equ|al for both modes. The selection of compression mode to use for an image block can be performed before determining the codewords and index sequence, preferably i based on an investigation of the properties of the image elements- in the block, e.g. b^ised on the distribution of the color values of the image elements in the color space. Alternatively, the mode selection is made during or after generation of the codewords and index sequence. In the latter case, two compressed representations of the image block will be produced, one according to the first compression mode and one according to the second mode. A first error value associated with compressing the image block according to jthe first mode is determined using the block representation compressed according to this first mode. Correspondingly, also a second error value associate with compressing the image block according to the second mode is determined using the block representation compressed according to the second mode. These two error values are then compared, and the compression pode resulting in highest quality (smallest error value) is selected. The block representation compressed according to this selected mode will be used as encoded representation for the current block. During decoding, the compressed image block(s) that should be decompressed: is identified and fetched from e.g. a memory location. Once the correct compressed image block is identified, a decoded representation of at least one image element in the identified compressed! image block is generated using the codewords and indices. The invention offers the following advantages: Gives high quality (peak signal/noise ratio) for alpha images due to the flexibility of allowing alpha values representing, in addition to fully transparency and opacity, semi-transparency; Hardware implementation of decoding is extremely simple; Encoding is very fast, which enables implementations1 also in terminals with low clock frequencies; Can be extended to operate according to two modes adapted for i different image blocks, which will further improve the peak signal/noise ratio; and Exhaustive encoding is possible at feasible speed on a computer. Other advantages offered by the present invention will be appreciated upon reading of the below description of the embodiments of the invention. SHORT DESCRIPTION OF THE DRAWINGS The invention together with further objects and advantages thereof, may best be understood by making reference to the following description taken together with the accompanying drawings, in which: Fig. 1 is a flow diagram illustrating an embodiment of aiji image encoding method according to the present invention; Figs. 2A and 2B illustrate embodiments of an image block according to the present invention; Figs. 3A to 3C illustrate embodiments of compressed representations of an image block; Fig. 4 is a flow diagram illustrating an embodiment of the color codeword determining step of the image encoding method of Pig. 1; Fig. 5 is a flovjr diagram illustrating another embodiment of the color codeword determining step of the image encoding method of Fig. 1; Fig. 6 is flow diagram illustrating the steps of determining alpha codeword, determining alpha modifying codeword and selecting alpha modifier index of Fig. 1 in more detail; Fig. 7 is a flojw diagram illustrating an image decoding method according to the present invention; Fig. 8 is a flow diagram illustrating an embodiment of the color representation generating step of Fig. 7 in more detail; Fig. 9 is a flow diagram illustrating another embodiment of the color i representation generating step of Fig. 7 in more detail; Fig. '10 is d flow diagram illustrating the steps of generating alpha representation, selecting alpha modifier and modifying alpha representation of Fig. 7 in morejdetail; Fig. 11 schematically illustrates an example of a user terminal with an image encoder and decoder according to the present invention; Fig. 12 is a block diagram schematically illustrating an embodiment of an image encoded according to the present invention; Fig. 13 is a b6ck diagram schematically illustrating an embodiment of a block encoder according to the present invention; Fig. 14 is a block diagram schematically illustrating another embodiment of a block encoder according to the present invention; Fig. 15 is a block diagram schematically illustrating the colbr quantizer of the block encoder of Figs. 14 or 15 in more detail; Fig. 16 is a block diagram schematically illustrating the alpha quantizer of the block encoder of Figs. 14 or 15 in more detail; Fig. 17 is a block diagram schematically illustrating the incjlex selector of the block encoder of Figs. 14 or 15 in more detail; Fig. 18 is a block diagram schematically illustrating an embodiment of an image decoder according to the present invention; Fig. 19 is a block diagram schematically illustrating an embodiment of a block decoder according to the present invention; Fig. 20 is a block diagram schematically illustrating another embodiment of a block decoder according to the present invention; Fig. 21 is a hardware block diagram schematically illustrating an embodiment of a block decoder according to the present invention; Fig. 22 is hardware block diagram illustrating an embodiment of the bit extenders of Fig. 21 in more detail; Fig. 23 is hardware block diagram illustrating an embodiment of the clampers of Fig. 21 in more detail; and Fig. 24 is hardware block diagram illustrating an embodiment of the table look-ups of Fig. 21 in more detail. DETAILED DESCRIPTION ! Throughout the drawings, the same reference characters will be used for corresponding or similar elements. The present invention relates to image and graphic processing, and in particular to encoding or compressing alpha images and decoding or decompressing encoded (compressed) alpha images. Generally, according to the invention, during image encoding, an alpha image is decdmposed or divided into a number of image blocks. Each such image block then comprises multiple, i.e. at least two, image elements having image elemenjt associated properties, among others, a certain color and an associated all or transparency value. The image blocks are then encoded or compressed to generate an encoded representation of the image. When an encoded image is to be displayed on a screen, or a geometric primitive associated with the encoded image is to be rendered, the relevant image elements of the encoded image blocks are identified and decoded. These decoded image elements can then be used to generate a decoded representatiorj of the original image for display, or they can be used for rendering the geometric primitive. The present invention is well adapted for usage with three-dimensional (3D) graphics and images, such as photos, text and "synthetic" images, all of which can .be used in applications, such as games, 3D maps and scenes, 3D messages, e.gj animated messages, screen savers, man-machine interfaces (MMIs), etc., fcut is not limited thereto. Thus, the invention could also be employed for encoding other types of images or graphics, e.g. one-dimensional (JlJD), two-dimensional (2D) or 3D images. In the present! invention the expression "image element" refers to an element in an image block or encoded (compressed) representation of an image block. This image block, in turn, corresponds to a portion of an image or texture. Thus, according to the invention, an image element could bje a texel of a (ID, 2D or 3D) texture or a pixel of a (ID, 2D or 3D) image. Correspondingly, an image element could be a voxel in a 3D texture or image. Generally, an image element is characterized by certain image-element-associated properties, such as a color value and an alpha or transparency value. Furthermore, in the following, the term "image" is used to denote any ID, 2D or 3D image or texture that can be encoded and decoded by means of the pjresent invention. As was briefly mentioned above, an image element is often characterized by, among others, a color. This color could be a single-component (one-dimensional) property, typically a grey level or value. In jsuch a case, the color of an image element can take a value from a minimum grey level, e.g. 0, typically representing black to a maximum grey level, e.g. 255, typically representing white. Alternatively, the color of an image element could be a multi-component (multi-dimensional) property, typically Icomprising three color components. In such a case, the color could be a kGB (Red, Green, Blue) color, a color in the YUV space, a color in the YCrCb space, or any other color space used in image and graphics processing. In the following, the present invention will mainly be described with reference to RGB color. This should, however, merely be seen as an illustrative, but non-limiting, example of a suitable color format. The corresponding description can, thus, also be applied to other multi-component color formats and single component color formats, e.g. grey level. In the art of alpha image processing, alpha values are used to represent the transparency property of an image element. Generally, an alpha value is typically defined as alpha_value= 1 - transparency, if 0 property of that image element depending on the employed alpha value-transparency relationship. It is anticipated by the present invention that the image elements of an "alpha imag4" in addition to their respective alpha values also have associated color values. Thus, an alpha image of the invention could be a so-called RGBA-image. Image encoding Fig. 1 is a flo-v| diagram of an embodiment of the (lossy) method of encoding an alpha image according to the present invention. In a first step SI, the image is decomposed dr divided into a number of image blocks. Each such image block then comprises multiple image elements. In a preferred embodiment of the invention, an image block comprises eight image elements (pixels or texels) and has a size of 2m x 2n image elements, where m=3-n and n=0, 1,2,3. More I preferably, 11 ijs 1 or 2. Figs. 2A and 2B schematically illustrate two examples of an image block 600 with eight image elements 610 according to the present invention. In Fig. 2A, the height is two image elements 610 and the width is four image elejments 610, i.e. m=l and n=2, whereas for the image block 600 i in Fig. 2B m-2 and n=l. Correspondingly, when compressing 3D images, a preferred image block size could be 2 x 2 x 2 image elements (voxels). However, the present invention is not limited to blocks with eight image elements but could alternatively be used in connection with image blocks having less, eig. 2x2, or more than eight image elements, e.g. 4x4 image elements. Returning to Fig. 1, the whole image block is preferably decomposed into (non-overlapping) irjiage blocks in step SI. However, in some applications, only a portion of an image is encoded and, thus, only this portion is decomposed into image blocks. In step S2, a color codeword is determined for the image block. This color codeword is a representation of the colors of the image elements in the image block. In a typical implementation, the color codeword is a! representation of an average color of the image elements of the block but ojould alternatively represent multiple color values. The color codeword is preferably in the same color format (space) as the original image. However, in some cases, it may be •useful to convert the image to a different color format, i.e having the color codeword in a first color space and the original image in a second different color space. In a next step S3, an alpha codeword is determined for the i current image block. This alpha codeword is a representation of the alpha values of the image elements in the image block. In a typicall implementation, the alpha codeword is a representation of an average alpha value of the image elements in the block. Thereafter, an alpha modifying codeword is provided in step S4. This alpha modifying codeword is a representation of a set of multiple alpha modifiers that are used (during decoding) for modifying the alpha representation of the image elements in the image block. In a preferred embodiment of the invention,, the alpha modifying codeword is an index or representation allowing identification of an alpha modifier set. This index could then identify or point to the set in an alpha! table or codebook comprising several different alpha modifier sets. Each set comprises two or more alpha modifier values, preferably at least four modifier jvalues. The alpha table preferably comprises sets including small alpha modifier values, which are adapted for allowing representation of smoothly changing i transparency properties. In addition, the table preferably also comprises sets that include large alpha modifier values, which are adapted for allowing representation of sharp transparency contrast. The actual alpha modifier values of the sets in the table can be found by starting with random values and then optimizing these valujes using a number of different optimization schemes and algorithms, such as versions of the LBG-algorithm (Linde, Buzo and Gray) [2], simulated annealing and coordinate search, which are known to a person skilled in the art. A handful of alpha images bf different types can be used as training data. In order to ma!ke a hardware implementation of the alpha table less expensive, the alpha modifiers of a set can be forced to be mathematically complementary I values, i.e. ea

Documents:

4120-delnp-2006-abstract.pdf

4120-delnp-2006-Claims-(02-04-2014).pdf

4120-DELNP-2006-Claims-(21-02-2012).pdf

4120-delnp-2006-claims.pdf

4120-DELNP-2006-Correspondence Others-(02-03-2012).pdf

4120-delnp-2006-Correspondence Others-(02-04-2014).pdf

4120-DELNP-2006-Correspondence Others-(21-02-2012).pdf

4120-delnp-2006-correspondence-others 1.pdf

4120-delnp-2006-Correspondence-Others-(05-11-2013).pdf

4120-delnp-2006-Correspondence-Others-(06-03-2014).pdf

4120-delnp-2006-Correspondence-Others-(29-05-2013).pdf

4120-delnp-2006-correspondence-others.pdf

4120-delnp-2006-description (complete).pdf

4120-delnp-2006-drawings.pdf

4120-delnp-2006-form-1.pdf

4120-delnp-2006-form-18.pdf

4120-delnp-2006-form-2.pdf

4120-delnp-2006-form-26.pdf

4120-DELNP-2006-Form-3-(02-03-2012).pdf

4120-delnp-2006-Form-3-(05-11-2013).pdf

4120-delnp-2006-Form-3-(06-03-2014).pdf

4120-DELNP-2006-Form-3-(21-02-2012).pdf

4120-delnp-2006-Form-3-(29-05-2013).pdf

4120-delnp-2006-form-3.pdf

4120-delnp-2006-form-5.pdf

4120-delnp-2006-GPA-(02-04-2014).pdf

4120-delnp-2006-pct-101.pdf

4120-delnp-2006-pct-210.pdf

4120-delnp-2006-pct-301.pdf

4120-delnp-2006-pct-304.pdf

4120-delnp-2006-pct-306.pdf

4120-delnp-2006-pct-371.pdf

abstract.jpg

Petition under rule 137.pdf