Patent Publication Number: US-2003223633-A1

Title: Method and system for compressing digital images

Description:
FIELD OF THE INVENTION  
       [0001] This invention relates to techniques for compressing images, and more particularly to techniques for compressing color images.  
       BACKGROUND OF THE INVENTION  
       [0002] A digital color image consists of M×N pixels with each pixel further represented by a number of bits in some of the standard color representations such as RGB (Red Green and Blue) (depicted generally in FIG. 1). For clarity these specifications will use a color depth (i.e. number of bits per pixel) of 24 bits, by way of non-limiting example only. The storage or transmission of the image information increases to M×N×24 bits. If the image is a frame in a digital video with 25 frames per second, the transmission requires the bandwidth M×N×24×25 bits per second (bps). Even a small frame size of 160×120 pixels yields 11,5 Mbps and is beyond the bandwidth of most fixed, and in particular, all wireless Internet connections. However, video sequences contain a lot of redundancy and may therefore be compressed.  
       [0003] All image and video compression techniques utilize the existing correlations within a frame and between frames, on one hand, and an understanding of the limitations of the human visual system, on the other hand. The correlations, such as static objects and areas with constant coloring, may be compressed without loss, while the omission of imperceptible details is by definition lossy. Further compression requires compromises to be made in the accuracy of the details and colors in the reproduced images.  
       [0004] The correlations within an image are typically accounted for by dividing the images into blocks and/or by some functional transform such as the Discrete Cosine Transform (DCT) or the Discrete Wavelet Transform (DWT). The image blocks can also be compressed with vector quantization (VQ), or with any other known means.  
       [0005] A skillful choice of the color representation in color images and videos may reduce the visually relevant information to one half. This is achieved by finding a color representation where the actual color information is separated from the brightness, i.e. luminance, of the colors. An example of this is the standard transition from the RGB color map to the YCrCb color map representation, where Y represents the luminance, and Cb and Cr jointly define the color, i.e. the chrominance. The conversion from RGB to YCrCb is made using the following equations:  
         Cr= 0,877*( R−Y )  EQ.1  
       [0006] and  
         Cb= 0,493*( B−Y ).  EQ.2  
       [0007]FIG. 2 illustrates a YCrCb color map. The compression is achieved by deluding the eye: the human visual system is less sensitive to detail in the colors than in the luminance and the color information may be expressed on a coarser scale than the luminance. If the color resolution is reduced to one half in both directions (Cr and Cb), this reduces the data from M×N×24 bits to  
         M×N× 8+( M/ 2)×( N/ 2)×8+( M/ 2)×( N/ 2)×8= M×N× 12 bits.  EQ.3  
       [0008] Most known image compression techniques treat the components Y, Cr, and Cb separately.  
       [0009] Retaining good visual quality of compressed videos is just one of the many requirements facing any practical video compression technology. For commercial purposes, the encoding process should be reasonably fast in order to facilitate the encoding of large amounts of video content. Apart from a possible initial buffering of frames in the computer&#39;s memory, the viewing of a video typically occurs in real time demanding real time decoding and playback of the video. The range of intended platforms from PC&#39;s to PDA&#39;s and, even to third generation mobile phones, sets further constraints on the memory usage and processing power needs of the codecs (CODer-DECoder).  
       [0010] Fast decoding is even more important for so-called streaming videos, which are transmitted to the receiver in real time as they are being viewed. A limited data transmission capacity determines a minimum compression ratio for streaming videos over the full length of the video, as the bit rate for transmitting the video must remain within the available bandwidth at all times.  
       [0011] Most video compression technologies comprise two components: an encoder used in compressing the videos and a decoder or player to be preinstalled, or downloaded and installed in the receiving end. Although this downloading needs to be done only once for each player version, there is a growing interest towards player-free streaming video solutions, which can reach all internet users. In such solutions, a small player application is transmitted to the receiving end together with the video stream. In order to minimize the waiting time due to this overhead information, the application, i.e., the decoder, should be made extremely small.  
       [0012] A DCT codec, as other functional transform codecs, requires prohibitively heavy decoding processing to be suitable for many PDA&#39;s and mobile phones, and in general is not fit for player-free streaming video solutions.  
       [0013] A VQ codec is a relatively light solution, which has a light processing on the decoding side as well. However, codebooks of VQ must be trained, and the efficiency of VQ depends on a compression ratio with a certain quality of images. Usually, the compression ratio (for a required image quality level) depends on the size of the codebooks: the larger the codebook—the greater the compression ratio. In other words, the larger codebook size provides better image quality, at any fixed compression ratio. The large codebooks require a relatively large memory space and a longer encoding time—due to prolonged vector search—and a longer transmission time. In any particular application, these disadvantages have to be weighed against the image quality and compression ratio benefits gained by using larger codebooks.  
       [0014] As can be seen, the present compression solutions require improvements, especially for streaming video and light platform receiving solutions.  
       SUMMARY OF THE INVENTION  
       [0015] The invention teaches an easily decodable compression technique for the color information in digital color images and video. An aspect of the invention is defining an active color area in a color map. The active color area comprises substantially all the colors present in the image under compression. Further a coordinate system is formed for the active area. The colors in the active area can be quantized, for example, by using a grid where each node of the grid represents all the colors in the quantization area of the node. Since the active area is smaller than the total color map area, fewer bits are needed to index the active colors in the active area. Saving the bits increases the compression of colors when compressing the image. The color (chrominance) values of the image are mapped using the indices of the active color area.  
       [0016] In a preferred embodiment of the invention the vector quantization (VQ) procedure is adapted to work more readily with the active color area. The chrominance codebook(s) are trained using image blocks in the active color map format. The VQ procedure may be performed on each chrominance component separately or jointly on the two of them.  
       [0017] The invention satisfies the need of improving the compression of the color information at any compression ratio while retaining good perceptual color quality, while maintaining a minimal processing power requirements in the decoding side.  
       [0018] So, an aspect of the invention comprises the steps of defining an active color area in a color map, the active area encompasses all colors used in the image; forming a coordinate system for the active color area; and mapping the colors of the encoded image to indices of the coordinate system.  
       [0019] A system according to the invention comprises at least a defining module, acting as an active area locator, for defining an active color area wherein all colors of the image are, a forming module acting as a coordinate system generator for forming a coordinate system for the active color area, and a mapping module, also known as a mapper, for mapping the colors of the images to indices of the coordinate system. The preferable embodiment for all the modules is in software. 
     
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
     [0020] Different aspects of the invention may be better understood by referring to the following description and the accompanying figures, in which:  
     [0021]FIG. 1 illustrates an example of the RGB color map.  
     [0022]FIG. 2 illustrates an example of the YCrCb color map.  
     [0023]FIG. 3 illustrates an example of coding colors according to a VQ based method.  
     [0024]FIG. 4 illustrates an example of coding colors according to a lattice VQ based method.  
     [0025]FIG. 5 illustrates the quantized color values of the example of FIG. 4 after the lattice quantization.  
     [0026]FIG. 6 illustrates the lattice VQ quantized pixels of the example of FIG. 4.  
     [0027]FIG. 7 illustrates an example of restricting the color map area within the area containing all colors that exist in an image.  
     [0028]FIG. 8 illustrates an example of the lattice quantization in the active color area.  
     [0029]FIG. 9 illustrates an example of possibilities to make new active areas utilizing an original active area.  
     [0030]FIG. 10 illustrates an example of an axis used as the basis for reflecting an active color area.  
     [0031]FIG. 11 illustrates a simplified flowchart of an embodiment in accordance with the inventive method.  
     [0032]FIG. 12 illustrates an example of an inventive apparatus. 
    
    
     DESCRIPTION OF THE INVENTION  
     [0033]FIG. 3 illustrates an example of coding colors according to VQ in the YCrCb color map. Dots P 1  to P 16  represent the real color values of one block (4*4 pixels) of the image. The X shapes C represent vector quantized color values, i.e. the codevector of 16 values. The codevector is a trained presentation of a number of similar blocks, i.e. the codevector quantizes several similar blocks.  
     [0034]FIG. 4 illustrates an example of coding colors according to the lattice VQ. Before the real chrominance values are vector quantized, the color map is divided into a grid. Each node CL of the grid is illustrated by an X. The single node represents the chrominance values which are nearest to the node. In this way the colors are quantized before the vector quantization. FIG. 5 shows the quantized color values CL 1  of the example of FIG. 4 after the lattice quantization. The lattice quantized values are initial values for the vector quantization. FIG. 6 represents the VQ quantized pixels of the example of FIG. 4, i.e. the lattice VQ quantized pixels P. Since the block size is 4*4 pixels, the size of the codevector is 16 chrominance values, but it can comprise the same colors more than once. Thus a number of squares P correspond to a number of squares with the same chrominance values in the codevector.  
     [0035] As mentioned before, most known image compression techniques treat the three color components (e.g. Red Green and Blue) separately. (Naturally color components may be based on other components than the basic three color components.). This is not optimal, since all objects in an image give rise to similar correlations in each of the three color components.  
     [0036] Most often this fact is either deliberately overlooked or the colors are expressed in terms of a color map where a limited number of colors (defined as RGB triples) is used and they are referred to via a set of indices. The color map scheme is most often used in the full three-dimensional color space but it may also be restricted to e.g. the chrominance plane, while the luminance is expressed separately, as showed in FIGS.  2  to  6 .  
     [0037] If the color components are compressed independently of each other, these two redundancies are not accounted for and the compression is likely to be only sub-optimal.  
     [0038] On the other hand and in general, if the values of a vector quantity, such as the color of a pixel, are limited to a small volume in space, the vector quantity values may be expressed with a smaller number of bits. If this volume is not fixed for all references to it, some overhead information is needed in determining the boundaries of the volume. The compression requirements may further necessitate the quantization of this volume. The simplest way to do this is to divide it evenly in each coordinate direction. More elaborate ways include rotations of the axis and an uneven grid used in dividing the volume. All these methods, commonly known as lattice VQ, (See FIGS.  4  to  6 ) can be used.  
     [0039] Due to the above-mentioned matters, the problems of the correlations between the color components in real images and the active color area (the restriction of the color space to the colors that actually occur in the images) must be taken into account when realizing this invention.  
     [0040] If the correlations are taken into account first, the most common approach is to use color maps. Each image is first converted to a set of indices according to the colors present in the image, and the indices are then compressed. The particular way of indexing the colors is a subtle problem in that the errors introduced into the indices in the encoding stage should optimally induce only small errors in the resulting colors. In other words, the colors should be indexed in such a way that the indices of all close-by colors should be close to each other.  
     [0041] In DCT based techniques such as the JPEG (Joint Photographic Expert Group) standard, all other frequencies but the lowest, or the dc component, automatically adapt to the active color space in that they only acquire coefficient values that fit into the “active colors”. The dc components are typically difference encoded so that for neighboring blocks only the difference from the previous block&#39;s respective value is transmitted. Therefore there is no real need to define the chrominance space for each frame. As to the correlation between the color components, the relationships between the DCT coefficients of the different color components are unlikely to be easily parameterized and would require excessive overhead information to be sent with the coefficients.  
     [0042] In VQ based techniques, the main advantages are the compact way of expressing several pixel values or DCT coefficients with just one index and the light decoding via table lookups. Hence, the need to exchange information such as the range of the colors directly decreases the efficiency of the VQ.  
     [0043] While VQ encoding color images/video, one can use one codebook for each color component or, in order to save memory and bandwidth requirements, use a common codebook for several components. If the VQ codebooks are predefined and trained with general image data, their entries cover practically the full range of the luminance and chrominance values. This is inefficient in that not all combinations of the color components are even within the RGB space that can be displayed on a computer screen, let alone actually present in a given image/video frame.  
     [0044] In order to account for the correlations between just the two chrominance components, these may be combined to represent colors i, (Cb i , Cr i ), and a codebook may be trained to represent blocks of such colors. This simple scheme has two immediate shortcomings: a big portion of the code vectors may fall outside the colors present in a given image/video frame; and the colors of real image blocks (and also frames) possess some degree of angular redundancy if expressed in polar coordinates.  
     [0045] The present invention may be considered as a lightly decodable compression technique for the color information in digital color images and video. It takes into account both correlations in image information and the existing color information of the image. FIG. 7 illustrates an example of restricting the color map area to the area containing all colors P 7  that exist in an image. Most images contain only a part of all the possible colors. In FIG. 7 the color map is the YCrCb map, wherein the color information is expressed in one plane, wherein one axis represents the values of the Cr color component and the other axis the values of the Cb color component. For simplicity, the luminance axis is not shown in FIG. 7. It should be noted that other coordinate systems can be used as well, but the YCrCb map is considered to be preferable.  
     [0046] The easiest way to define the area wherein the colors of the image are, i.e. the active color area, is to define a rectangle. The smallest and largest Cb and Cr values are found in the image. These values define a rectangular region, which comprises all the colors in the frame, and also the range of each chrominance component C 1 , C 2 . Although, the rectangle is easy to form and in many case reasonable to use, it may be possible to decrease it, especially at the corners as illustrated in FIG. 7. The decreasing of the rectangle can be obtained, for example, by using an auxiliary axis  71 . The auxiliary axis is at a certain angle to the other of the axes of the color map, and it forms a basis for an auxiliary color map index. The auxiliary index scale should preferably be the same as that of the original axes. The smallest and largest Cb and Cr values of the image at the auxiliary axis restrict the rectangle along lines extending perpendicularly from the auxiliary axis, and having the corresponding values at the auxiliary axis. It is possible to use any number of auxiliary axes, but mostly it is preferable to use only one or two axes and possibly at fixed angles, forming a hexagon or an octagon. The polygon bounded by those lines defines an active area that includes all colors contained within the image. The preferable angle to one of the original axes is 45 degrees. In most real images, it is possible to decrease the area contained within the polygon by 10%-70% as compared to the rectangle area. Although the restriction of the area of color space used with the basic VQ technique saves bits needed to identify the colors is useable by itself, further advantage may be gained by quantizing the active color area. A preferable way to quantize is to use lattice quantization, i.e. dividing the active area into a grid. FIG. 8 shows an example of the lattice quantization in the active color area. The quantized pixel value of a real pixel value P 7  of the image is the chrominance value of the nearest node of the grid. The lattice guantized chrominance values form an index vector or matrix, which is then vector quantized. The indices of the grid map represent the chrominance values of the image projected onto the active color area in the color map, and encode the colors as well.  
     [0047] This active color area can be divided into an even grid with either the same or some different number of quantization steps in each Axis. In order to facilitate a simple search algorithm for matching colors in the color map, the range of one of the chrominance components is uniformly quantized at one axis of the color map. It is advantageous to apply the uniform quantization to that chrominance component which has the smaller range. This procedure is easily reversible for the search process: find the component with the smaller range, say Cb; divide the Cb range into n even intervals; and find the closest match to the actual Cb value in the image. The range of the other chrominance component, Cr in the example, is divided into m values separately for each Cb value at the other axis. Only the actual range available for this particular Cb value is divided in order to fully benefit from the color space constraints.  
     [0048] In the above the numeric range of each chrominance component has been reduced by the constrained colormap constituting the active area. This has the immediate consequence that fewer bits are needed for each component. Furthermore, the quantization made in forming the colormap reduces the number of accessible values for each component. The human eye is less sensitive to quantization in the chrominance values than in the luminance; the quantization can also be dependent on the desired compression ratio.  
     [0049] The information regarding the color map area can, for example, be expressed by four or eight eight-bit numbers, depending on the chosen number of boundary lines used to define the active area. These are transmitted to the receiving end as often as necessary, i.e., they can be sent separately for each frame or even parts of a frame, or they may be sent once for longer sequences of a video. In the receiving end, the decoder reverses the steps performed during encoding for constructing the color map lattice.  
     [0050] Since each image is basically independent from other images, the active color area of a single image must be determined individually for each image. However, consecutive images in a video for example, tend to be similar. Due to this fact, it is possible to form other active areas utilizing an original active area made for a certain image. Often, this means that the boundaries of the existing active area may be adjusted for the new image. FIG. 9 illustrates an example of possibilities to make new areas. If the original area ORG is on one of the quadrants of the color map, it is possible to reflect it in relation to one axis of the chrominance plane or the origin in such a way that new active areas A, B, and C can be formed, each of them on a certain quadrant of the color map. As can be seen, the reflections are preferably done if the place of the origin remains fixed. Naturally, the active area can be reflected if it is, for example on the area of two or more quadrants, but then an overlapping area usually exists, which reduces encoding efficiency. Normally, active color areas cover the area nearby the origin, but FIG. 9 illustrates a borderline situation. Actually, the axis used for the basis of reflection can be any line on the color map, as described in FIG. 10, wherein area El is reflected in relation to line L 10  forming a new area E 2 .  
     [0051] The same effect can be achieved by reflecting the color map of a given frame in relation to the chrominance axis by translating the origin, (Cb,Cr)=(0,0), to appear in the lower left quadrant of the original color space.  
     [0052] In general, the color map could be rotated around the origin of the chrominance plane but performing a translation that places the origin in the lower left quadrant provides a simple way of doing this without unnecessary computations.  
     [0053] Such a simple reflection scheme maps the Cb-Cr distributions of frames quite well onto one single distribution, facilitating the usage of common codebooks for all frames. This means that when a reflection of an active color area is made the color distribution of the area is reflected as well.  
     [0054] In a preferable embodiment of the invention the VQ procedure is used for encoding images. Due to this, it is preferable to adapt the codevectors (chrominance codebooks) used, to an active color area of each image. The chrominance codebooks are trained using training image blocks in the active color map format, or alternatively, a combined codebook (containing, for example, Cr and Cb values) is trained in the active color map format.  
     [0055] The color map is best used if, e.g., VQ code vectors used to encode the colors can be scaled into the active chrominance area. However, as the active color map varies from frame to frame the scales and statistics of the components change. The scales can, to some extent, be accounted for in the training stage but the fact that the colors may be centered into different regions of the color map is more of a problem. If there exists correlation between images, the above mentioned reflection scheme can be beneficially used.  
     [0056] Preferably, the training material for forming the codebooks is to be first run through the above color map conversion procedure. The resulting blocks or vectors can be used in different ways: to train separate codebooks for Cb and Cr; to train one common codebook for the two components; or to train one joint codebook, whose entries contain both chrominance components. The color map does not need to be changed for each frame and it can be defined and kept constant for whole video shots or scenes showing similarly colored images.  
     [0057] The perceived usage of the color map is robust against quantization of the active color map boundaries. Therefore, the active color area can be held constant as long as the boundaries stay close to the same quantization level and then changed. In this way, not all the boundary parameters need to be transmitted with each frame while at the same time retaining the flexibility of varying the color map frame by frame.  
     [0058]FIG. 11 shows an example of a simplified flow chart of a method according to the invention. First, an active color area wherein all colors of the image are is defined  111 . A coordinate system for the active color area is formed  112 , and the colors of the images are mapped  113  to indices of the coordinate system. Furthermore, the defining step can comprise sub phases: determining a smallest and a largest color map index, at an axis of the color map, these indices reflect colors contained within images; determining a smallest and a largest color map index at another axis of the color map, these indices reflect colors contained within the images; and forming a rectangle area in the color map, using said indices at both axes for bordering the active rectangle.  
     [0059] Further, one or more auxiliary axis can be used for determining a smallest and a largest auxiliary color map index, in an auxiliary axis of the color map, the auxiliary axis being angled to the other axis of the color map. These indices of the auxiliary axis reflect colors contained within the images. The determined indices of the auxiliary axis or axes can be used for decreasing the active rectangle, using lines which extend perpendicularly to the auxiliary axis, one having said smallest index value at the auxiliary axis, and the other having said largest index value at the auxiliary axis. These lines border the active color area with the lines of the rectangle. As mentioned, the restriction of the active color area can be repeated (using additional auxiliary axes or lines) as many times as desired, for decreasing the active color area.  
     [0060] The step of forming the coordinate system can comprise a sub phase for forming a grid for the active color area for quantizating the colors in the active color area. The grid is preferably uniform across the active color area. Furthermore, the phase of forming the grid may comprise the steps of dividing the active color area uniformly at the color map axis, which has the smaller range of active color indices, and dividing the active color area at the other color map axis separately for each resulting index of division. In this way a best amount of quantization values will be achieved.  
     [0061] Optionally, the invention also comprises a preliminary step of training  114  codebooks in a format that represents the active color area. The preliminary step means that before compressing the real image in question, the codevectors used should be trained for the active color area using training image or images. It should be noted that these training images are preferably processed in a similar way as the actual image.  
     [0062] Furthermore, the active color area can be reflected in relation to a certain line on the color map for forming a new active color area.  
     [0063] The method of color compression contemplated herein is suitable to be used in conjunction with any compression technology used for the luminance information.  
     [0064]FIG. 12 shows an example of an inventive system. The system for compressing a color image according to an aspect of the invention comprises: an Active Area Locator  121  for defining an active color area wherein lie all colors of the image, a coordinate system generator  122  for forming a coordinate system for the active color area, and a mapper  123  for mapping the colors of the images to indices of the coordinate system.  
     [0065] The active area locator  121  may further comprise: a search module for determining a smallest and a largest color map index, at axes of the color map, these indices belonging to certain colors of the images; and a rectangle area forming module in the color map, using said indices at both axes for bordering the rectangle. Furthermore, the active area locator  121  may comprise means for determining at least one auxiliary axis that is at a certain angle to the other axis, that is functionally connected to the means for determining a smallest and a largest color map index; and means for decreasing the active color area using the indices of any of said axes to border the active color area.  
     [0066] The coordinate system generator  122  preferably further comprises means for forming a grid for defining the active color area for quantizating the colors in the active color area.  
     [0067] The inventive system may preferably further comprise a codebook trainer  124  for training codebooks using a training material that is processed in the area locator  121 , in the coordinate system generator  122 , and in the mapper  123 , separately or in combination. Preferably the codebook trainer  124  handles vector quantization codebooks.  
     [0068] Yet further, in the inventive system the area locator may optionally comprise means for reflecting a defined active color area in relation to a certain line on the color map for forming a new active color area. And further, optionally the reflection means may be capable to scale, rotate, and/or skew the defined active color area.  
     [0069] In practical usage, it is possible to embed any inventive arrangement as a part of a complete video compression/decompression software. The software consists of a user interface; media readers for reading in the video and audio information; software implementing algorithms for defining the active color region and for dividing it into a grid as proposed in this invention; a form of basic encoding; a solution for sending the stream; and a small decoding software package to be transmitted in the beginning of the video stream (or alternatively use codebooks and a player already stored in the receiving terminal) and capable of recreating the colors map for each frame, if necessary, from the information transmitted in the stream and using the color map to display the colors.  
     [0070] As can be seen, the invention can be modified to be suitable for a plurality of different solutions. Thus it is evident that the invention is not restricted to the above-mentioned examples but it can be used in other solutions as well, in the scope of the inventive idea.