CN100566419C - Equipment and method with harmless mode encoding digital image data - Google Patents

Abstract

A method (900) of losslessly compressing and encoding a signal representing image information is presented. A lossy compressed data file (922) and a residual item compressed data file (960) are generated. When the lossy compressed data file and the residual compressed data file are combined, a lossless data file that is substantially identical to the source data file is created.

Description

Apparatus and method for encoding digital image data in a lossless manner

This application is a divisional application of an invention patent application with a filing date of July 2, 2002, an application number of 02817150.0, and an invention title of "equipment and method for encoding digital image data in a lossless manner".

technical field

The present invention relates to image processing and compression. More specifically, the invention relates to the lossless coding of video image and audio information in the frequency domain.

Background technique

In the principle of general digital signal processing, digital picture processing occupies a very important position. The importance of human visual perception has greatly stimulated interest and progress in this field and in the science of digital image processing. In the field of transmitting and receiving video signals, such as for projecting films and movies, various improvements have been made to image compression techniques. Many current or proposed video systems use digital encoding techniques. These aspects of the field include: image coding, image restoration, and image feature selection. Image coding represents an attempt to transmit pictures over a digital communication channel in an efficient manner, using as few bits as possible to minimize the required bandwidth, while maintaining distortion within certain limits. Image restoration refers to the work that strives to recover the real image of the target. The encoded image transmitted over the communication channel may be distorted due to various factors. When creating an image from a target, sources of distortion can arise. Feature selection refers to the selection of certain attributes of an image. These attributes may be required for identification, classification, and adjudication in general.

The digital encoding of video, such as that performed in digital cameras, is an area that would benefit from improved image compression techniques. Digital image compression can generally be divided into two categories: lossless methods and lossy methods. Lossless images can be recovered without losing any information. Lossy methods cause some information to be lost irretrievably, depending on the compression ratio, the quality of the compression algorithm, and the implementation of the algorithm. Typically, lossy compression methods are considered to achieve the compression ratios desired by economical digital cinema. To achieve digital cinema quality levels, the compression method needs to deliver a visually lossless level of performance. Thus, although the compression process still results in a mathematical loss of information, the image distortion caused by this loss will not be noticed by the viewer under normal viewing conditions.

Existing digital image compression techniques have been developed for other applications, namely television systems. These technologies have been designed with a balance of suitability for the desired application, but have not met the quality requirements required for cinema performance.

Digital cinema compression technology needs to deliver the visual quality moviegoers have experienced before. Ideally, the visual quality of digital cinema should try to surpass that of high-quality distribution photocopies. At the same time, compression techniques should have practically high coding efficiency. As defined herein, coding efficiency refers to the bit rate required for compressed image quality to meet a certain quality standard. Still further, the system and encoding technique needs to have enough flexibility built in to accommodate different formats, and should also be economical, ie, a small size and efficient decoder or encoder processing.

Many existing compression techniques can provide significant degrees of compression, but result in a degradation of video signal quality. In general, techniques for sending compressed information require that the compressed information be sent at a constant bit rate.

One compression technique that can provide a significant degree of compression while maintaining a desired level of video signal quality uses adaptively sized blocks and sub-blocks of encoded discrete cosine transform (DCT) coefficient data. This technique is hereinafter referred to as the Adaptive Block Size Discrete Cosine Transform (ABSDCT) method. This technique is disclosed in U.S. Patent No. 5,021,891, entitled "Adaptive Block Size Image Compression Method And System," assigned to the assignee of the present application and incorporated herein by reference. DCT techniques are also disclosed in U.S. Patent No. 5,107,345, entitled "Adaptive Block Size Image Compression Method And System," assigned to the assignee of the present application and incorporated by reference in this. In addition, the combination of using ABSDCT technology and differential quadtree transform technology is disclosed in U.S. Patent No. 5,452,104, entitled "Adaptive Block Size Image Compression Method and System" ("Adaptive Block Size Image Compression Method And System"), also assigned to The assignee of this application is hereby incorporated by reference. The systems disclosed in these patents use a method called "intra" coding in which each frame of image data is coded without regard to the content of any other frames. Using ABSDCT technology, the achieved data rate can be reduced from around 1.5 billion bits per second to about 50 million bits per second without discernible degradation in image quality.

ABSDCT technology can be used to compress black-and-white or color images, or signals representing images. The color input signal may be in YIQ format, where Y is luma, or luminance samples and I and Q are chrominance or color samples, for each 4:4:4 or other format. Other known formats such as YUV, YC _b C _r or RGB formats may also be used. Due to the low spatial sensitivity of the eye to color, most research results show that it is reasonable to sub-sample the color components by a factor of 4 in the vertical and horizontal directions. Thus, a video signal can be represented by 4 luma samples and two chrominance samples.

Using ABSDCT, a video signal will typically be divided into blocks of pixels for processing. For each block, the luma and chrominance components are sent to a size distribution element, or an interleaver. For example, a 16x16 (pixel) block is presented to the block interleaver, which arranges or organizes image samples within each 16x16 block to produce data blocks for discrete cosine transform (DCT) analysis and Synthetic subblocks. The DCT operation is a method of converting a temporally and spatially sampled signal into a frequency representation of the same signal. By converting to a frequency representation, the DCT technique appears to allow a high degree of compression because the quantizer can be designed to take advantage of the frequency distribution properties of the image. In a preferred embodiment, a 16×16 DCT is applied to the first sorting, 4 8×8 DCTs are applied to the second sorting, 16 4×4 DCTs are applied to the third sorting and 64 2×2 DCTs are applied to the Applied to the fourth sort.

The DCT operation reduces the spatial redundancy inherent in video sources. After performing DCT, most of the video signal energy will be concentrated on a few DCT parameters. An additional transform, the differential quadtree transform, can be used to reduce redundancy in the DCT parameters.

For a 16x16 block and each sub-block, the DCT parameter values and DQT values (if DQT is used) are analyzed to determine the number of bits required to encode the block or sub-block. Then, the block or combination of sub-blocks requiring the fewest number of bits to achieve encoding is chosen to represent the image segment. For example, 2 8x8 sub-blocks, 6 4x4 sub-blocks and 8 2x2 sub-blocks may be selected to represent image segments.

The selected block or combination of sub-blocks is then suitably arranged into a 16x16 block. DCT/DQT parameter values may be frequency weighted, quantized and coded (such as variable length coded) in preparation for transmission. Although the ABSDCT technique described above performs reasonably well, it is computationally intensive.

Also, although using ABSDCT is visually lossless, it is sometimes desirable to recover data in exactly the same way as it was encoded. For example, applications for containment and archiving require that data be compressed in such a way that it can be restored exactly to its original domain.

Traditionally, lossless compression systems for images include a predictor that estimates the value of the current pixel to be encoded. The remaining term pixels are obtained as the variance between the true and predicted pixels. The remaining term pixels are then entropy encoded and stored or sent. Since the prediction removes the correlation between pixels, the remaining term pixels have a reduced dynamic range that is characteristically bilaterally exponential (Laplace) distributed. Hence the compression. The amount of compression for the remainder depends on both the prediction and the subsequent encoding method. The most commonly used prediction method is Differential Pulse Code Modulation (DPCM) and its variants such as Adaptive DPCM (ADPCM).

One problem with using pixel-based predictions is that the remaining terms still have high energy. This is due to the fact that only a very small number of adjacent pixels are used in the prediction process. Therefore, there is still much room for improving the coding efficiency of pixel-based prediction schemes.

Contents of the invention

Embodiments of the present invention describe a system for encoding digital image and video data in a lossless manner to achieve compression. The system is hybrid, meaning that the system has a part that compresses the data in a lossy manner and another part that compresses the remaining data in a lossless manner. For the lossy part, the system uses the Adaptive Block Size Discrete Cosine Transform (ABSDCT) algorithm. The ABSDCT system compresses the data and provides high visual quality and high compression ratio. The remainder image is obtained as the variance of the source image and the image decompressed from the ABSDCT system. The remainder is losslessly encoded using the Golomb-Rice encoding algorithm. Due to the vision-based adaptive block size and quantization to the DCT coefficients, the residual terms have very low energy, which provides a better overall lossless compression ratio.

The ABSDCT system achieves high compression ratios at cinema quality. Since it is block-based, it can de-correlate pixels better than any other pixel-based scheme. It is therefore used as a predictor in the lossless system to be described here. Combining the predictor with the addition of a lossless coding system forms a hybrid lossless compression system. It should be noted that the system is capable of compressing still images as well as moving images. In the case of a still image, only the ABSDCT compressed data and the entropy-coded residual item data are used as compressed output. For moving sequences, a decision is made as to whether to use intra or inter compression. For example, if f(t) represents the image frame at time t, F(t) and F(t+Δt) represent the DCT of the image frame at time t and t+Δt, respectively. Note that Δt represents the time interval between two consecutive frames.

The present invention is embodied in an apparatus and method for compressing data which allow data to be recovered in exactly the same manner as encoded data. Embodiments include a system that performs intra-coding, inter-coding, or a combination of both. The system is a quality based system using adaptively sized blocks and sub-blocks of discrete cosine transform coefficient data. A block of pixel data is input to an encoder. The encoder includes a block size allocation (BSA) element that segments an input pixel block for processing. The allocation of the block size is based on the variance of the input block and further divided sub-blocks. Typically, regions with larger variance are split into smaller blocks, while regions with smaller variance are not subdivided, assuming the mean values of the blocks and sub-blocks fall into different pre-determined ranges. In this way, first the variance threshold of the block is modified from its nominal value according to its mean value, then the variance value of the block is compared with the threshold value, if the variance value is greater than the threshold value, the block is subclassed. segmentation.

The block size allocation is provided to a transform element, which transforms the pixel data into frequency domain data. This transformation is only performed on blocks and subblocks selected by the block size allocation. For AC elements, the transformed data is then scaled by quantization and serialization. Quantization of transformed data is based on image quality metrics such as scaling factors for adjusting contrast, coefficient counts, rate-distortion, block size allocation density and/or previous scaling factors. Serialization, such as zigzag scanning, is based on establishing the longest possible run length for the same value. The data stream is then encoded by a variable length encoder in preparation for transmission. The coding can be Huffman coding, or coding based on exponential distribution, such as Golomb-Rice coding.

Use a hybrid compression system such as ABSDCT as a good predictor of pixel or DCT values. Therefore it can achieve higher lossless compression ratios than any using pixel-based prediction. The lossy part provides digital cinema quality results, ie the compression produces a file that is visually lossless. For the lossless part, unlike Huffman coding, Golomb-Rice coding does not require any prior coding to be generated. Therefore, it does not need to save a large codebook like Huffman coding. This enables a more efficient use of the chip's resources, so the size of the chip implemented in hardware can be reduced. In addition, Golomb-Rice coding is simpler to implement than Huffman coding. Moreover, Golomb-Rice coding achieves higher coding efficiency than Huffman coding due to the natural exponential distribution of DCT parameters or residuals. Furthermore, since the lossy part of the compression system uses visually important information in the sub-segmentation of the block, the content model is inherited in the encoding of the remaining items. This is important because then no additional storage registers are required to collect relevant content data for remaining item encodings. The system is also very simple to implement since it does not use any motion estimation.

An apparatus and method for losslessly compressing and encoding a signal representing image information is presented. Signals representing image information are compressed to create a compressed version of the image. A compressed version of the image is quantized and a lossy version of the image is created. The compressed version of the image is also serialized to create a serialized, quantized, compressed version of the image. This version of the image is next decompressed and the differences between the source image and the decompressed version are determined and a residual version of the image is created. The lossy version of the image and the remainder version of the image may be output separately or in combination, where the combination of the decompressed lossy version of the image and the remainder version of the image is substantially identical to the source image.

A method for losslessly compressing and encoding signals representing image information is presented. Produces a lossy data file and a residual item compressed data file. When the lossy data file and residual compressed data file are combined, a lossless data file is created that is substantially identical to the source data file.

Thus, an aspect of an embodiment provides an apparatus and method for efficiently providing lossless compression.

Another aspect of an embodiment provides lossless compression of digital image and audio information for purposes beneficial for control and archiving.

Yet another aspect of an embodiment provides an inter-based lossless compression system.

Another aspect of an embodiment provides an intra-based lossless compression system.

An embodiment of the invention describes an apparatus for encoding data comprising a source image, the apparatus comprising: means for compressing data representing said source image and thereby creating a compressed version of said source image, wherein said compression uses data previously generated by adaptive block resizing of a source image; means for quantizing a compressed version of said source image and thereby creating a lossy version of said source image; means for compressing a compressed version of said source image to create a decompressed image, wherein said decompression uses data previously generated by adaptive block resizing of said source image; for determining said source image and means for taking the difference between said decompressed images and thereby creating remnant data associated with said source image; and means for outputting a lossy version of said source image and said remnant data , wherein the lossy version of the source image and the residual item data can be used to create an image substantially identical to the source image.

Another embodiment of the present invention describes a method of encoding data comprising a plurality of source frames from a source image, the method comprising: compressing data representing a first source frame of the plurality of source frames, and thereby creating a compressed version of the first source frame, wherein the compression uses data previously generated by adaptive block resizing of the plurality of source frames; quantizing the compressed version of the first source frame and thereby creating a lossy version of the first source frame; decompressing the compressed version of the first source frame to create a decompressed frame, wherein the decompressing uses previously generated data from adaptive block resizing; determining a difference between a second source frame and said decompressed frame and thereby creating residual item data associated with said first source frame; and outputting A lossy version of the first source frame and the remnant data, wherein the lossy version of the first source frame and the remnant data may be used to create a frame substantially identical to the first source frame.

Yet another embodiment of the present invention describes an apparatus for encoding data comprising a plurality of source frames from a source image, the apparatus comprising: compressing data representing a first source frame of the plurality of source frames , and thereby create a compressed version of said first source frame, wherein said compression uses data previously generated by adaptive block resizing of said plurality of source frames; for quantizing said first source frame means for decompressing the compressed version of the first source frame to create a decompressed frame, wherein the decompressing The compression uses data previously generated by adaptive block resizing of the plurality of source frames; used to determine the difference between the second source frame and the decompressed frame and thereby create a means for remnant item data associated with said first source frame; and means for outputting a lossy version of said first source frame and said remnant item data, wherein said lossy version of said first source frame and said remnant item data The remaining item data may be used to create a frame substantially identical to the first source frame.

Description of drawings

Features and advantages of the present invention will be more apparent through the following detailed description made in conjunction with the accompanying drawings. In the accompanying drawings, the same reference numerals indicate the same features throughout, wherein:

Fig. 1 is a block diagram of an encoding part in an image compression and processing system;

Fig. 2 is a block diagram of the decoding part in an image compression and processing system;

Figure 3 illustrates a flowchart of the processing steps involved in variance-based block size allocation;

Figure 4a illustrates the exponential distribution of the run length of the Y component in the DCT coefficient matrix;

Figure 4b illustrates the exponential distribution of the run length of the C _b component in the DCT coefficient matrix;

Figure 4c illustrates the exponential distribution of the run length of the _Cr component in the DCT coefficient matrix;

Figure 5a illustrates the magnitude of the Y component magnitude or the exponential distribution of the magnitude of the Y component magnitude in the DCT coefficient matrix;

Figure 5b illustrates the C _b component amplitude magnitude or the exponential distribution of the C _b component amplitude magnitude in the DCT coefficient matrix;

Figure 5c illustrates the magnitude of the _Cr component magnitude or the exponential distribution of the magnitude of the _Cr component magnitude in the DCT coefficient matrix;

Figure 6 illustrates the Golomb-Rice encoding process;

Figure 7 illustrates an apparatus for Golomb-Rice encoding;

Figure 8 illustrates the process of encoding DC component values;

Figure 9 illustrates an apparatus for lossless compression; and

Figure 10 illustrates a method of hybrid lossless compression.

Detailed ways

In order to achieve digital transmission of digital signals and take advantage of them, it is often necessary to use some form of signal compression. When achieving high compression ratios in a resulting image, it is equally important to maintain the high quality of the image. Also, its computational efficiency is expected for tiny hardware implementations, which is important in many applications.

Before explaining one embodiment of the present invention in detail, it should be understood that the present invention is not limited to the detailed construction and arrangement of parts described in the following description or illustrated in the accompanying drawings. The invention is capable of other embodiments and of being carried out in various ways. Also, it is to be understood that the phraseology and terminology used herein are for the purpose of description and should not be regarded as limiting.

The image compression used in an aspect of one embodiment is based on discrete cosine transform (DCT) technology, such as the pending U.S. patent application "Contrast Sensitive Variance Based Adaptive Block Size DCT Image Compression" ("Contrast Sensitive Variance Based Adaptive Block Size DCT Image Compression"), Serial No. 09/436,085, filed November 8, 1999, assigned to the assignee of this application and incorporated herein by reference. An image compression and decompression system using DCT is described in co-pending U.S. Patent "Quality Based Image Compression," Serial No. 09/494,192, filed January 28, 2000, Assigned to the assignee of this application and incorporated herein by reference. Typically, an image processed in the digital domain consists of pixel data divided into a matrix of non-overlapping blocks, of size NxN. Two-dimensional DCT can be performed on each block. The two-dimensional DCT is defined by the following relationship:

$\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; \&alpha;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; \&beta;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span>}{\sqrt{\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; m</span>}}}\underset{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\underset{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; cos</span>}<span\; class="notranslate">\; [</span>\frac{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; \&pi;k</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; N</span>}}<span\; class="notranslate">\; ]</span>\mathrm{<span\; class="notranslate">\; cos</span>}<span\; class="notranslate">\; [</span>\frac{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; \&pi;l</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; N</span>}}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}$

in $\mathrm{\&alpha;}\left(k\right),\mathrm{\&beta;}\left(k\right)=\left\{\begin{array}{cc}1,\mathrm{if}& k=0\\ \sqrt{2},\mathrm{if}& k\&NotEqual;0\end{array}\right.,$ as well as

x(m,n) is the pixel at position (m,n) in an NxM block, and

X(k,l) is the corresponding DCT coefficient.

Since pixel values are non-negative, the DCT score X(0,0) is always positive and generally has most of the energy. In fact, for a typical image, most of the transformation energy is concentrated around the component X(0,0). This energy-compressing property makes the DCT technique an attractive compression method.

This image compression technique uses contrast adaptive coding to achieve further bit rate reduction. It is observed that most natural images consist of relatively slowly changing smooth regions and volatile regions such as object boundaries and high-contrast textures. Contrast adaptive coding schemes take advantage of this by allocating more bits to busy areas and fewer bits to less busy areas.

Contrast adaptive methods use intra-coding (spatial processing) instead of inter-coding (spatial-temporal processing). Inter-coding inherently requires more complex processing circuitry and also requires multiple frame buffers. In many applications, complexity reduction is required in practical implementations. Intra coding can also be used in environments where spatio-temporal coding schemes fail and perform poorly. For example, a film at 24 frames per second would fall into this category due to the relatively short integration time provided by the mechanical shutter. Shorter integration times allow for a higher degree of time domain aliasing. For fast motion, since it becomes jerky, the assumption of frame-to-frame correlation is broken. Intra coding is also easy to standardize when using both 50Hz and 60Hz power line frequencies. TV is now sent at 50Hz or 60Hz. Using intra-frame coding, it is possible to accommodate 50 Hz as well as 60 Hz operation as a digital solution, or even 24 frames per second film by compromising the frame rate with respect to the spatial resolution.

For image processing, DCT operations are performed on pixel data partitioned into non-overlapping blocks in a matrix. Note that although the block size discussed here is NxN, it is envisioned that a variety of block sizes could be used. For example, a block size of NxM may be used, where N and M are integers and M may be larger or smaller than N. Another important aspect is that the block can be divided into at least one level of sub-blocks, eg N/ixN/i, N/ixN/j, N/ixM/j, etc., where i and j are integers. Additionally, the exemplary block size discussed here is a 16x16 pixel block with corresponding DCT blocks and sub-blocks. It is also envisioned that various other integers may be used such as two even numbers or two odd numbers, such as 9x9.

1 and 2 illustrate an image processing system 100 incorporating the concept of a configurable serializer. The image processing system 100 includes an encoder 104 that compresses a received video signal. The compressed signal is sent using a transmission channel or physical medium 108 and received by a decoder 112 . The decoder 112 decodes the received encoded data into image samples, which may then be displayed.

Typically, an image is divided into blocks of pixels for processing. A color signal can be converted from RGB space to YC ₁ C ₂ space using RGB to YC ₁ C ₂ converter 116, where Y is the luminance or luminance component and C ₁ and C ₂ are chrominance, or color components. Because of the eye's low spatial sensitivity to color, many systems subsample the _C1 and _C2 components by a factor of 4 in the horizontal and vertical directions. However, subsampling is not required. A full resolution image, known as 4:4:4 format, may be very useful or necessary in some applications such as so-called "digital cinema". Two possible YC ₁ C ₂ representations are, the YIQ representation and the YUV representation, both of which are well known in the art. A variation of the YVU representation known as YC _b C _r can also be used. This can be further divided into parity and even components. Thus, Y-even, Y-odd, _Cb -even, _Cb -odd, _Cr -even, _Cr -odd are used in one embodiment to represent.

In a preferred embodiment, each of the odd and even Y, _Cb and _Cr components are processed without subsampling. Thus, an input for each of the six components of a 16x16 pixel block is provided to the encoder 104 . For illustration, the encoder 104 is shown for the Y-even component. Similar encoders are used for the Y-odd component, and the odd-even _Cb and _Cr components. Encoder 104 includes block size allocator 120, which performs allocation of block sizes in preparation for video compression. The block size allocator 120 determines the decomposition of a 16x16 block based on the perceptible characteristics of the images in the block. The block size allocation subdivides each 16x16 block into smaller blocks, such as 8x8, 4x4, and 2x2, in a quadtree based on the activity in the 16x16 block form. The block size allocator 120 generates quadtree data, called PQR data, which can be between 1 and 21 bits in length. Thus, if the block size allocation determines that a 16x16 block needs to be split, R bits of PQR data are set followed by 4 bits of additional Q data corresponding to the division into four 8x8 blocks. If the block size allocation determines that any 8x8 block needs to be subdivided, an additional 4 bits of P data are added for each subdivided 8x8 block.

Referring now to FIG. 3, a flowchart detailing the operation of block size allocation element 120 is provided. The variance of a block is considered as a metric when deciding whether to sub-split a block. Starting from step 202, a 16×16 pixel block is read. In step 204, the variance v16 of the 16×16 block is calculated, and its variance is calculated by the following formula:

$\mathrm{<span\; class="notranslate">\; var</span>}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="2"\; label="N"\; filenames="C2006101464760026H1.png,C2006101464760027H1.png"\; state="\{\{state\}\}">N</figure-callout></span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; -</span>{<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="2"\; label="N"\; filenames="C2006101464760026H1.png,C2006101464760027H1.png"\; state="\{\{state\}\}">N</figure-callout></span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}$

Where N=16, and xi _,j is the pixel located in the i ^th row j ^th column in the NxN block. In step 206, first if the mean value of the block is between two predetermined values, the variance threshold T16 is modified to provide a new variance threshold T'16. Next the block variance is compared with the new threshold T'16.

If the variance v16 is not greater than the threshold T16, then at step 208, the start address of the 16*16 block is written into temporary storage, and the R-bit PQR data is set to 0 to indicate that the 16*16 block is not subdivided. The algorithm next reads the next 16x16 block of pixels. If the variance v16 is greater than the threshold T16, then at step 210, the R bit of PQR data is set to 1 to indicate that the 16×16 block is subdivided into four 8×8 blocks.

These four 8×8 blocks, i=1:4, may be further sub-divided, as shown in step 212 . For each 8×8 block, the variance v8 _i is calculated in step 214 . In step 216, the variance threshold T8 is first modified to provide a new threshold T'8 if the average value of the block is between two predetermined values, and then the block variance is compared with the new threshold.

If the variance v8 _i is not greater than the threshold T8, then in step 218, the start address of the 8×8 block is written into the temporary memory, and the corresponding Q bit, Q _i is set to 0. Then process the next 8×8 block. If the variance v8 _i is greater than the threshold T8, then in step 220, the corresponding Q bit, Qi is set to 1 to indicate that the 8×8 block will be subdivided into four 4×4 blocks.

For the four 4×4 blocks, j _i =1:4, further sub-division may be considered, as shown in step 222 . For each 4×4 block, the variance v8 _ij is calculated in step 224 . In step 226, the variance threshold T4 is first modified to provide a new threshold T'4 if the mean value of the block is between two predetermined values, and then the block variance is compared to the new threshold.

If the variance v4 _ij is not greater than the threshold T4, then in step 228, the first address of the 4×4 block is written, and the corresponding P bit, P _ij is set to 0. Then process the next 4×4 block. If the variance v4 _ij is greater than the threshold T4, then in step 230, the corresponding P bit, _Pij is set to 1 to indicate that the 4×4 block will be further subdivided into four 2×2 blocks. Additionally, these 4 2x2 blocks are written into temporary memory.

Thresholds T16, T8 and T4 may be predetermined constants. This is called a hard judgment. Alternatively, adaptive or soft decisions can also be used. For example, a soft decision changes the threshold for variance according to the average pixel value of a 2Nx2N block, where N can be 8, 4 or 2. In this way, a function of the average pixel value can be used as a threshold.

To illustrate, consider the following example. The predetermined variance thresholds for the Y component are set to 50, 1100 and 880 for 16x16, 8x8 and 4x4 blocks, respectively. In other words, T16=50, T8=1100 and T4=880. Set the range of Average to 80 to 100. Suppose a variance of 60 is calculated for a 16×16 block. Since 60 is greater than T16 and the average value of 90 is between 80 and 100, the 16×16 block is subdivided into four 8×8 subblocks. Assume that the variances of the calculated 8×8 blocks are 1180, 935, 980 and 1210. Since the variance of two 8×8 blocks exceeds T8, these two blocks will be further subdivided to generate a total of 8 4×4 sub-blocks. Finally, assume that the variances of the eight 4×4 blocks are 620, 630, 670, 610, 590, 525, 930, and 690, and the corresponding average values are 90, 120, 110, and 115. Since the average value of the first 4*4 sub-block falls within the range (80,100), its threshold value will be reduced to T'4=200, which is smaller than 880. Therefore, this 4x4 sub-block will be sub-divided as well as the seventh 4x4 sub-block.

Note that a similar process would be used to assign block sizes for the luma component Y-odd and the color components _Cb and _Cr . Color components can be decimated horizontally, vertically, or both.

Also, note that although block size allocation is described as a top-down approach, ie the largest block (16x16 in this example) is estimated first, it is also possible to use a bottom-up approach. A bottom-up approach will estimate the smallest block first (2×2 in this example).

Returning to FIG. 1 , the PQR data is provided to DCT element 124 along with the address of the selected block. The DCT element 124 uses the PQR data to perform an appropriately sized discrete cosine transform on selected blocks. Only selected blocks require DCT processing.

The image processing system 100 also includes a DQT element 128 for reducing redundancy in the DC coefficients of the DCT. The DC coefficients are located in the upper left corner of each DCT block. Generally, the DC coefficient is larger than the AC coefficient. The variance in size makes it difficult to design an efficient variable-length encoder. Therefore, reducing redundancy in the DC coefficients is beneficial.

The DQT element 128 performs a 2-D DCT on the DC coefficients, 2×2 at a time. Starting from a 2x2 block in a 4x4 block, a 2-D DCT is performed on the 4 DC coefficients. This 2-D DCT is called the differential quadtree transform of 4 DC coefficients, or DQT. Next, the DC coefficient of this DQT and the three adjacent DC coefficients in the 8x8 block are used to calculate the DQT of the next level. Finally, the DC coefficients of the four 8x8 blocks in the 16x16 block are used to calculate the DQT. Thus, in a 16×16 block, there is only one real DC and the others are AC coefficients corresponding to DCT and DQT.

The transform coefficients (DCT and DQT) are supplied to a quantizer for quantization. In a preferred embodiment, the DCT coefficients are quantized using frequency weighting masks (FWMs) and a quantization scale factor. FWM is a table of frequency weights on the same dimension of the input DCT coefficient block. Frequency weighting applies different weights to different DCT coefficients. The weights are designed to emphasize input samples that have frequency content to which human vision or the optical system is sensitive, while attenuating input samples that have frequency content to which human vision or the optical system is not sensitive. Weights can also be designed based on factors such as viewing distance and the like.

The choice of weights is based on empirical data. A method for designing weight masks for 8×8 DCT coefficients in ISO/IEC JTC1 CD 10918, "Digital compression and encoding of continuous-tone still images Part 1: Requirements and guidelines" ("Digital compression and encoding of continuous-tone still images-part 1: Requirements and guidelines"), International Standards Organization, 1994, incorporated herein by reference. Typically, two FWMs are designed, one for the luma component and the other for the chrominance component. The FWM tables for block sizes 2x2 and 4x4 are obtained by decimation for the 8x8 block table and the 16x16 table is obtained by interpolation of the 8x8 block table. The scale factor controls the quality and bit rate of the quantized coefficients.

Thus, each DCT coefficient is quantized according to the following relationship:

where DCT(i,j) is the input DCT coefficient, fwm(i,j) is the frequency weighting mask, q is the scaling factor, and DCTq(i,j) is the quantized coefficient. Note that the first term in parentheses rounds up or down, depending on the sign of the DCT coefficients. The DCT coefficients are also quantized using a suitable weight mask. However, multiple tables or masks can be used and applied to the Y, C _b and _Cr components.

At block 130, the AC values are next separated from the DC values and processed separately. For the DC element, the first DC component value for each segment is coded. Each subsequent DC component value for each segment is then represented as the variance between it and its preceding DC component, and encoded, as in block 134 . For lossless coding, the initial DC component value and the difference value of each segment are coded using Golomb-Rice shown in conjunction with FIGS. 6 and 8 , as in block 138 . Using Golomb-Rice to encode the difference between successive DC component values is advantageous in that the differential of the DC component values tends to have a bilateral exponential distribution. The data is then temporarily stored using buffer 142 and then transmitted or sent to decoder 112 via transmission channel 108 .

Figure 8 illustrates the process of encoding DC component values. This processing is equally applicable to still images, video images (such as, but not limited to, motion images or high-definition television), and audio. Given a segment of the data, as in step 804 , the first DC component value for the segment is retrieved as in step 808 . The first DC component value is then encoded, as in step 812 . Unlike AC component values, DC component values do not need to be quantized. In one embodiment, a single value is used for a 16x16 block regardless of block size allocation failures. It is envisioned that any fixed size block, such as 8x8 or 4x4, or any variable block size defined by the block size allocation can be used. Second, or then, the DC component value for a given segment is retrieved (step 816). The second DC component value is compared to the first DC component value and the difference, or remainder, is encoded (step 820 ). Thus, the second DC component value needs to be expressed as the difference between it and the first value. This process is repeated for each segment's DC component value. Thus, a query is made, step 824 to determine if the end of the segment (last block and last DC value) has been reached. If not, go to step 828, retrieve the DC value of the next segment, go to step 816 and repeat the above process. If so, go to step 832 to retrieve the next segment, as in step 804 and repeat the process until all frames in the file and all segments in all frames have been processed.

The purpose of lossless coding for the DC component values is to generate residual term values with low variance. With DCT, the DC coefficient component value contributes the most pixel energy. Therefore, the variance of the remaining term is reduced by not quantizing the DC component value.

For the AC component, the data block and frequency weighting mask are then scaled by the quantizer 146 or scale factor element. The quantization of DCT coefficients reduces most of them to 0 to achieve the effect of compression. In a preferred embodiment, there are 32 scaling factors corresponding to the average bit rate. Unlike other compression methods such as MPEG2, the control of the average bit rate is based on the quality of the processed image rather than the target bit rate and the state of the cache.

To further increase compression, the quantized coefficients are provided to a scan serializer 150 . The scan serializer 150 scans the quantized coefficient block to generate a serial stream of quantized coefficients. Zigzag scanning, column scanning or row scanning can be used. A variety of different zigzag scanning methods and non-zigzag scanning methods can be selected. A preferred technique uses 8x8 blocks for zigzag scanning. Zigzag scanning for quantized coefficients increases the likelihood of encountering large runs of zeros. Such zero-runs inherently have decreasing probability and can be efficiently coded with Huffman coding.

A serial, quantized stream of AC coefficients is provided to a variable length encoder 154 . The AC component values can be encoded using Huffman coding or Golomb-Rice coding. For DC component values, Golomb-Rice encoding is used. The run-length encoder separates zero coefficients from non-zero coefficients and is described in detail in FIG. 6 . In one embodiment, Golomb-Rice encoding is used. Golomb-Rice coding can efficiently encode non-negative integers with exponential distribution. Compression using Golomb codes better provides shorter length codes for exponentially distributed variables.

则其长度为

位，否则长度为

Golomb-Rice编码是Golomb编码的一种特殊形式，其中系数m表示为m＝2^k。在这种情况下，商n/m通过将二进制表示的整数n向右移k位而获得。这样，Golomb-Rice码是两者的串接。Golomb-Rice编码能用于编码具有双边几何(指数)分布的正的或者是负的整数，该分布表示为In Golomb coded run lengths, the Golomb code is coefficiented by a non-negative integer m. For example, given a coefficient m, the Golomb code for a positive integer n is represented by the quotient n/m in unary code plus the remainder of the modified binary code if the remainder is less than or equal to

Then its length is

bits, otherwise the length is

Golomb-Rice coding is a special form of Golomb coding, where the coefficient m is expressed as m=2 ^k . In this case, the quotient n/m is obtained by shifting the integer n in binary representation to the right by k bits. Thus, the Golomb-Rice code is the concatenation of the two. Golomb-Rice coding can be used to encode positive or negative integers with a bilateral geometric (exponential) distribution, expressed as

p _α (x)=cα ^|x| (1)

In (1), α is a characteristic coefficient representing the decay of probability x, and c is a normalization constant. Since P _α (x) is monotonic, it can be seen that a series of integer values should satisfy

p _α ( _xi ＝0)≥p _α ( _xi ＝-1)≥p _α ( _xi ＝±1)≥p _α ( _xi ＝-2)≥... (2)

As shown in Figures 4a, 4b, 4c and 5a, 5b, 5c, both the runs of zeros and magnitudes in the quantized DCT coefficient matrix have an exponential distribution. The distributions shown in these figures are based on data from real images. Figure 4a illustrates a Y-component distribution 400 of zero runlength versus frequency of interest. Similarly, Figures 4b and 4c illustrate _Cb and _Cr component distributions 410 and 420, respectively, of zero runlength versus frequency of interest. Figure 5a illustrates a Y-component distribution 500 of amplitude magnitude versus frequency of interest. Similarly, Figures 5b and 5c illustrate _Cb and _Cr component distributions 510 and 520, respectively, of amplitude magnitude versus frequency of interest. Note that the curves in Figures 5a, 5b and 5c represent the distribution of DCT coefficient magnitudes. Each size represents a range of coefficient values. For example, a size value of 4 has a range of {-15, -14, ... -8, 8..., 14, 15} for a total of 16 values. Similarly, a size value of 10 has a range of {-1023, -1022, ..., -512, 512, ..., 1022, 1023}, a total of 1024 values. From Figures 4a, 4b, 4c, 5a, 5b and 5c it can be seen that both the run length and the amplitude magnitude have an exponential distribution. The actual distribution of the magnitudes shown can be fitted by the following equation:

$\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\sqrt{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}}{\mathrm{<span\; class="notranslate">\; 2</span>}}\mathrm{<span\; class="notranslate">\; exp</span>}<span\; class="notranslate">\; \{</span><span\; class="notranslate">\; -</span>\sqrt{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}<span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; \}</span><span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; \&NotEqual;</span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; )</span>$

In (3), X _{k, l} represents the DCT coefficient corresponding to frequency k in the vertical direction and frequency l in the horizontal direction, and the mean ${\mathrm{\&mu;}}_x=\frac{1}{\sqrt{2\mathrm{\&lambda;}}},$ variance ${\mathrm{\&sigma;}}^2=\frac{1}{2\mathrm{\&lambda;}}.$ Thus, it is more desirable to use Golomb-Rice coding in the form described for data processing in DCT.

Although the following description is in connection with the compression of image data, the embodiments are equally applicable to embodiments that compress audio data. In the compression of image data, the image or video data may be, for example, RGB or YIQ or YUV or YC _b C _r with linearly or logarithmically encoded pixel value components.

FIG. 6 illustrates a process 600 of encoding 0 and non-zero coefficients. When the DCT matrix is scanned, zero and non-zero coefficients are processed separately and separated, as in step 604 . For 0 data, determine the length of the 0 run, as in step 608 . Note that run lengths are positive integers. For example, if the run length is n, then the Golomb coefficient m is determined, as in step 612 . In one embodiment, the Golomb coefficient is determined as a function of run length. In another embodiment, the Golomb coefficient (m) is determined by the following formula (4)

Optionally, the length of the run length and the associated Golomb coefficient are counted by a counter or register, as in step 616 . To encode the run length n of 0, the quotient is encoded, as in step 620 . In one embodiment, the quotient is determined as a function of the run length of zero and the Golomb coefficient. In another embodiment, the quotient (Q) is determined by the following equation (5):

In one embodiment, the quotient Q is encoded as a unary code requiring Q+1 bits. Next, the remainder is encoded, as in step 624 . In one embodiment, the remainder is encoded as a function of the run function and the quotient. In another embodiment, the remainder (R) is determined using equation (6) below:

R=n-2 ^m Q (6)

In one embodiment, the remainder R is coded as an m-bit binary code. Then, the quotient Q and remainder R are determined, and the codes of Q and R are concatenated, as in step 628, to represent the overall code for a runlength n of zero.

Non-zero coefficients are also encoded using Golomb-Rice. Since the coefficient magnitude can be positive or negative, it is necessary to use a sign bit and encode the absolute value of the given magnitude. The magnitude of the given non-zero coefficient is x, and its magnitude can be expressed as a function of this absolute value and this sign. Thus, the magnitude can be expressed as y using equation (7) below:

Therefore, the value of the non-zero coefficient can optionally also be counted by a counter or a register, as in step 632 . Next in step 636 it is determined whether the magnitude is greater than or equal to zero. If so, its value is encoded at step 640 as twice the given value. If not, at step 644 the value is encoded as a value that is twice its absolute value minus one. It is envisioned that other mapping schemes may also be used. The point is that no extra sign bit is needed to differentiate the value.

Amplitude encoding using equation (7) results in positive x values becoming even integers and negative x values becoming odd integers. Further, the mapping preserves the probability distribution of x in formula (2). The advantage of using the encoding described in (7) is that it avoids using the sign bit to represent positive and negative numbers. After mapping, y is encoded in the same form as for the run of 0. Processing continues until all coefficients in the current block have been scanned.

It is important to point out that although embodiments of the present invention determine the values of coefficients and runlengths as functions of equations (1)-(7), the exact equations (1)-(7) need not be used. This uses the exponential distribution of Golomb-Rice coding and DCT coefficients to achieve more effective compression of image and audio data.

Since zero-runs cannot be distinguished from non-zero amplitudes after encoding, a special fixed-length prefix encoding is required to mark the first occurrence of zero-runs. Usually all zeros are calculated after calculating the magnitude of non-zeros in a block. In some cases, it may be more efficient to use so-called end-of-block (EOB) codes than Golomb-Rice codes. The EOB code can also be a special fixed-length code.

According to equation (1) or (3), the probability distribution of the magnitude or run length of the DCT coefficient matrix is coefficientized by α or λ. It shows that the efficiency of encoding for content occurring under a certain block of DCT coefficients can be improved. The quantity of interest can then be encoded using appropriate Golomb-Rice coefficients. In one embodiment, counters and registers are used for each runlength and magnitude value to calculate the respective cumulative value and the corresponding number of occurrences of that value. For example, if registers are used to hold accumulated values and the number of accumulated elements are R _r1 and N _r1 respectively, the following equation (6) can be used as the Rice-Golomb coefficient to encode the run length:

Similar treatment can be used for magnitude.

Remainder pixels are generated by first decompressing the compressed data using an ABSDCT decoder, and then subtracting it from the source data. The smaller the dynamic range of the remaining items, the higher the compression ratio. Since compression is block-based, the remaining items are also block-based. It is a well-known fact that residual term pixels have a bilateral exponential distribution, usually centered at 0. Since Golomb-Rice codes are better for such data, a Golomb-Rice encoding process is used to compress the remaining item data. However, since there is no run length to encode, no special code is required. Further, no EOB encoding is required. Thus, compressed data includes two components. One component is from the lossy compressor and the other is from the lossless compressor.

Temporal correlation can also be exploited when encoding motion sequences. To fully exploit temporal correlation, the pixel shift due to motion is first estimated, and then motion compensated prediction is performed to obtain the remaining term pixels. Since ABSDCT performs adaptive block size coding, the block size information can alternatively be used as a measure of the shift due to motion. For further simplification, scene change detection is not used. Instead, the intra-frame compressed data is first obtained for each frame in the sequence. The difference between the current frame DCT and the previous frame DCT is then generated on a frame-to-frame basis. This is further described in US Patent Application Serial No. 09/877,578, filed June 7, 2001, incorporated herein by reference. The remaining terms in these DCT domains are encoded using the Huffman and Golomb-Rice encoding process. The final compressed output corresponds to the one that uses the smallest number of bits per frame.

The lossless compression algorithm is a hybrid scheme that can be adapted for reuse or transcoding by removing the lossless parts of it. Thus, maximizing the correlation of pixels in the spatial domain using ABSDCT enables residual term pixels to have lower variance compared to those using the prediction scheme. The lossy part of the overall system allows the user to achieve the desired quality and data rate for distribution without resorting to inter-frame processing, thereby eliminating motion-related artifacts and significantly reducing implementation complexity. This is especially important in distributing programs for digital cinema applications, since distribution of lossy portions of compressed material requires a higher level of quality.

FIG. 9 illustrates a hybrid lossless encoding device 900 . Figure 10 illustrates processes that may run on the device. Source digital information 904 is stored in a storage device, or is transmitted. Many of the elements in Figure 9 are described in detail in Figures 1 and 2 . The data frames are sent to a compressor 908 which includes a block size allocation element 912 , a DCT/DQT transform element 916 and a quantizer 920 . After DCT/DQT is performed on the data, the data is transformed into the frequency domain. At one output 922, the data is quantized by a quantizer 920 and passed to an output 924, which includes memory and/or switches. All processing described above is on an intra-frame basis.

The output of the quantizer is also sent to the decompressor 928 . The decompressor 928 performs the undo operation of the compressor process, through the inverse quantizer 932, and the IDQT/IDCT 936, along with knowledge of the PQR data as defined by the BSA. The result of the decompressor 940 is provided to a subtractor 944 for comparison with the source data. Subtractor 944 may be a variety of elements, such as a differentiator, that computes the residual pixel as the difference between the uncompressed and compressed decompressed pixels for each block. Additionally, the differentiator can obtain the remaining terms in the DCT domain for conditional inter-coding of each block. The result 948 of the comparison between the decompressed data and the source data is the pixel remainder file. That is, result 948 represents the loss of compressed and decompressed data. Thus, the source data is equal to the combination of output 922 and result 948 . The result 948 is then serialized 952 and encoded 956 by Huffman and/or Golomb Rice and provided as a second output 960. The Huffman and/or Golomb Rice encoder 956 is a form of entropy encoder that encodes residual term pixels using Golomb Rice encoding. The decision to use intra or inter coding is based on the fewest bits used for each frame. Using Golomb Rice to encode the remainder can improve the compression ratio of the overall system.

Thus, the lossless, inter-frame output is a combination or blend of two sets of data, the lossy, high-quality image file (922, or A) and the remainder file (960, or C).

Intercoding can also be used. The output of the quantizer is sent to memory 964, along with the knowledge of the BSA. After obtaining valid data for one frame, the subtractor 966 compares the saved frame 964 with the next frame 968 . The difference thereof generates a DCT residual 970 which is then serialized and/or Golomb-Rice encoded 974 to provide a third output data set 976 to output 924 . In this way, inter lossless files B and C are compiled. In this way, the combination (A+C or B+C) can be chosen based on size considerations. Further, for editing purposes, a pure interframe output may be desired.

Returning to FIG. 1 , the compressed image signal generated by the encoder 104 can be temporarily stored using the buffer 142 and then sent to the decoder 112 using the transmission channel 108 . The transmission channel 108 may be a physical medium, such as a magnetic or optical storage device, or a wired or wireless transmission process or device. PQR data including block size allocation information is also provided to decoder 112 (FIG. 2). The decoder 112 includes a buffer 164 and a variable length decoder 168, and the encoder 168 decodes run lengths and non-zero values. The variable length decoder 168 operates in a similar but inverse manner to that described in FIG. 6 .

The output of variable length decoder 168 is provided to deserializer 172, which arranges the coefficients according to the scanning scheme used. For example, if a mix of zigzag scans, vertical scans, and horizontal scans is used, the deserializer 172 will use what it knows about the type of scan used to rearrange the coefficients appropriately. The deserializer 173 receives the PQR data to help arrange the coefficients correctly into the synthesized coefficient block.

The resulting block is provided to an inverse quantizer 174 for undoing the processing using the quantizer scale factor and frequency weighting mask.

If a differential quadtree transform is applied, the block of coefficients is provided next to an IDQT element 186 followed by an IDCT element 190 . Otherwise, the coefficient block is provided directly to the IDCT element 190 . IDQT element 186 and IDCT element 190 inverse transform the coefficients to generate a block of pixel data. The pixel data must then be interpolated, converted to RGB form, and saved for later display.

Fig. 7 illustrates an apparatus 700 for Golomb-Rice encoding. The apparatus of FIG. 7 preferably implements the process described in FIG. 6 . The determiner 704 determines the run length (n) and the Golomb coefficient (m). Alternatively, a counter or register 708 is used for each runlength and amplitude magnitude value to calculate the cumulative value and the corresponding number of occurrences of that value, respectively. Encoder 712 encodes the quotient (Q) as a function of the run length and the Golomb coefficient. The encoder 712 also encodes the remainder (R) as a function of run length, Golomb coefficient and quotient. In other embodiments, encoder 712 also encodes non-zero data as a function of the non-zero data value and the sign of the non-zero data value. The concatenator 716 is used to concatenate the Q value and the R value.

By way of example, the various illustrated logical block diagrams, flowcharts, and steps related to the embodiments disclosed herein may be implemented or executed in hardware or software, using application-specific integrated circuits (ASICs), programmable logic devices, discrete gates, or transistor logic , discrete hardware components such as registers and FIFOs, a processor executing a set of firmware instructions, any conventional programmable software and processor, or a combination thereof. The processor is preferably a microprocessor, but can be any conventional processor, controller, microcontroller or state machine. The software can be stored in RAM memory, flash memory, ROM memory, registers, hard disk, removable disk, CDROM, DVD-ROM or any other form of storage medium known in the art.

The foregoing description of preferred embodiments is provided to those skilled in the art to make or use the invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the general principles defined herein can be applied to other embodiments without inventive effort. Therefore, the invention should not be limited by the embodiments shown herein, but should be accorded the widest scope consistent with the principles and inventive features disclosed herein.

Other features and advantages of the invention are set forth in the claims.

Claims (9)

1. An apparatus for encoding data comprising a source image, the apparatus comprising: means for compressing data representing said source image and thereby creating a compressed version of said source image, wherein said compression uses data previously generated by adaptive block resizing of the source image; means for quantizing a compressed version of said source image and thereby creating a lossy version of said source image; means for decompressing a compressed version of the source image to create a decompressed image, wherein the decompression uses data previously generated by adaptive block resizing of the source image; means for determining a difference between said source image and said decompressed image and thereby creating residual item data associated with said source image; and means for outputting a lossy version of the source image and the remnant data, wherein the lossy version of the source image and the remnant data are operable to create an image substantially identical to the source image. 2. The apparatus of claim 1, wherein the means for compressing is on an intraframe or interframe basis. 3. The apparatus of claim 1, wherein the means for compressing uses a combination of discrete cosine transform and discrete quadtree transform techniques. 4. A method of encoding data comprising a plurality of source frames from a source image, the method comprising: compressing data representing a first source frame of said plurality of source frames, and thereby creating a compressed version of said first source frame, wherein said compression uses adaptive block resizing of said plurality of source frames and the data previously generated; quantizing the compressed version of the first source frame and thereby creating a lossy version of the first source frame; decompressing a compressed version of the first source frame to create a decompressed frame, wherein the decompressing uses data previously generated by adaptive block resizing of the plurality of source frames; determining a difference between a second source frame and said decompressed frame and thereby creating residual item data associated with said first source frame; and outputting a lossy version of the first source frame and the remnant data, wherein the lossy version of the first source frame and the remnant data may be used to create a frame substantially identical to the first source frame . 5. The method of claim 4, wherein the compressing is performed on an interframe basis. 6. The method of claim 4, wherein said compressing uses a combination of discrete cosine transform and discrete quadtree transform techniques. 7. An apparatus for encoding data comprising a plurality of source frames from a source image, the apparatus comprising: means for compressing data representing a first source frame of said plurality of source frames, and thereby creating a compressed version of said first source frame, wherein said compression uses Data generated prior to adapting to block size adjustments; means for quantizing a compressed version of said first source frame and thereby creating a lossy version of said first source frame; means for decompressing a compressed version of the first source frame to create a decompressed frame, wherein the decompression uses data previously generated by adaptive block resizing of the plurality of source frames ; means for determining a difference between a second source frame and said decompressed frame and thereby creating residual data associated with said first source frame; and means for outputting a lossy version of said first source frame and said remnant data, wherein said lossy version of said first source frame and said remnant data can be used to create consistent frame. 8. The apparatus of claim 7, wherein the means for compressing is on an interframe basis. 9. The apparatus of claim 7, wherein the means for compressing uses a combination of discrete cosine transform and discrete quadtree transform techniques.

Images