Apparatus and Method for Increasing the Throughput of an Acoustic or Image Compression System

The present invention relates to an apparatus and corresponding method for compressing image data, and an apparatus and method for increasing throughput of a processor involving additions, subtractions, and shifts.

The present invention is related to the above identified cross-referenced applications which are commonly owned by the same assignee as the present invention. The details of these cross-referenced applications are hereby incorporated by reference.

However, the aspects of the present invention are not limited to such image compression systems. Rather, the present invention is directed toward an apparatus and corresponding method for improving the throughput of a general data signal processing system, such as an acoustic data compression system.

In signal processing it is often necessary to perform time-consuming arithmetic. Today's general-purpose processors (such as the Motorola 68020) usually have 32-bit arithmetic data paths, but this is far more precision than is needed for important applications such as acoustic or image processing, such as with the present invention. It would be preferable to have less precision and more speed in such an acoustic or image processing environment.

For instance, the Generalized Chen Transform (GCT) described in the cross-referenced patent and patent applications may be implemented to perform an approximation to the discrete cosine transform (DCT) using only additions, subtractions and shifts, with a final multiply. An accuracy of 32-bits is not required to provide acceptable image quality. Therefore, the throughput of the GCT can be dramatically increased by combining two 16-bit words of data into each 32-bit word, processing the two 16-bit words in parallel in a 32-bit processor, and extracting two 16-bit words of output data. This process allows a single-instruction single-data (SISD) machine to operate as a single-instruction multiple-data (SIMD) machine.

It is an object of the present invention to provide an apparatus and corresponding method for compressing data, particularly still image data.

It is a more particular object to provide an apparatus and corresponding method for compressing acoustic or still images while increasing the throughput.

It is another object of the present invention to provide a method for adapting a single-instruction single-data machine to operate as a single-instruction multiple-data machine, thereby increasing throughput.

Additional objects, advantages and novel features of the present invention will be set forth in part in the description which follows and in part become apparent to those skilled in the art upon examination of the following, or may be learned by practice of the invention. The objects and advantages of the present invention may be realized and attained by means of the instrumentalities and combinations which are pointed out in the appended claims.

The accompanying drawings which are incorporated in and form a part of this specification illustrate an embodiment of the invention and, together with the description, serve to explain the principles of the invention.

FIG. 1a shows a block diagram of the components of a standard compressor, and FIG. 1b shows a block diagram of the components of a compressor according to a preferred embodiment of the present invention.

FIG. 2 shows a block diagram of the components of a separable 2D transform unit.

FIG. 3 provides a comparison of the accuracy of addition operations according to two embodiments of the present invention.

FIG. 4 provides a comparison of the accuracy of left-shifts according to two embodiments of the present invention.

FIG. 5 schematically illustrates the circuitry of the present invention for implementation of additions and subtractions.

FIG. 6 shows an example of the right-shift operation utilizing the present invention.

Before going into a detailed description of the aspects of the present invention, a brief overview of the cross-referenced patent and applications will be provided. However, as pointed out above, the present invention is not limited to such a compression system. Rather, the invention provides a method and apparatus whereby a number of input data quantities are combined to provide a lesser number of "doublevectors," operations are performed by the processor on the input doublevectors to provide output doublevectors, and a number of output data quantities are extracted from the output doublevectors, the number of output doublevectors being less than the number of output data quantities.

Transform Image Compression compresses an image by transforming the values of sets of adjacent pixels into sets of transform coefficients. The advantage of this is that the values transform coefficients tend to be less correlated than that of the corresponding pixel values. Adjacent pixels in an image are usually of similar value, i.e. the "energy" distribution of pixels is relatively even. If the coefficients of a transform are very dissimilar or decorrelated, the transform provides good energy compaction. For the sam reconstructed signal quality, lossy quantization of transform coefficients results in much better compression than lossy quantization of the original data. (0r equivalently for the same amount of compression, lossy quantization of the transform coefficients results in better reconstructed signal quality than lossy quantization of the original data.)

An example of a typical Transform Image Compression system is shown in FIG. 1a. (Note that the JPEG Still Image Compression Standard baseline system is such a system). For a raw color image 8, the pixels are converted into an opponent color space, such as YC.sub.R C.sub.B, at the color conversion unit 10. Through the rest of the system, only one color component is processed at a time. Color converted image data 15 is then divided into N.times.N blocks, 8.times.8 blocks in the JPEG case, by the N.times.N segmentation unit 20. The N.times.N opponent color blocks 25 are then transformed at the two dimensional transform unit 30.

A good deal of computation can be saved if the two-dimensional transform can be performed by two passes through a one-dimensional transform. In this case the two-dimensional transform is termed a separable transform. FIG. 2 illustrates the circuit component for calculation of this type of transform. First, a one-dimensional transform is performed by the 1D transform unit 32 on N rows of 1.times.N image components 25. The resulting transform coefficients 31 are then transposed at transpose unit 34, and the new N rows of 1.times.N coefficients 33 are transformed at 1D transform unit 36 to provide a set of two-dimensional transform coefficients 35 which have been subject to a two-dimensional transform.

As shown in FIG. 1a, the blocks of transform coefficients 35 are then quantized at quantization unit 40. Quantization is produced by dividing each coefficient 35 by a known number. This reduces the number of bits that are required to encode quantized coefficients 45. (During decompression, the quantization is reversed by multiplication of the coefficients by the same known numbers.) It should be noted that it is likely that the exact transform coefficient values will not be recovered after dequantizing because of the truncation error produced by division of integers, thus, the quantization is "lossy." The quantized coefficients 45 are losslessly encoded by some algorithm, such as Huffman Coding, at the lossless coder 50 to provide a set of coded transform coefficients 55.

When implemented in software with a general microprocessor, the slowest part of this system is the transform itself. To get good energy compaction requires complicated transforms, such as the Discrete Cosine Transform (DCT). The mathematical computation requires significant processor time. Since shifts and adds can be performed much faster than multiplications, the speed of the calculation may be increased by replacing the slow computations, specifically multiplications, with additions, subtractions and shifts.

The Generalized Chen Transform, disclosed in U.S. Pat. No. 5,129,015 and incorporated herein by reference, uses only adds and shifts in the transform. All required multiplications of the transform are combined with the multiplications of the quantization so that the speed of the quantization is not decreased while the speed of the transform is greatly increased.

The present invention takes advantage of transforms like that GCT that have a great number of adds and shifts by allowing two blocks of components to be transformed in parallel with a conventional general microprocessor.

An aspect of the present invention will now be described. In signal processing it is often necessary to perform time-consuming arithmetic. Today's general-purpose processors usually have 32-bit arithmetic data paths, but this is far more precision than is needed for important applications such as acoustic or image processing, such as with the present invention. It would be preferable to have less precision and more speed in such an acoustic or image processing environment.

The invention achieves this desirable object by packing a plurality of numbers into one 32-bit "doublevector." For example, four 8-bit data, or three 10-bit data (with two bits to spare), or two 16-bit data can be packed into a single 32-bit doublevector. Because left-shifts result in a reduction in precision, the transform process is preferably designed so that the significant bits of each component number is limited to, for instance, 14 bits the 32-bit doublevector is comprised of two 16-bit numbers.

A preferred embodiment of the present invention involving the use of the doublevector method to augment the speed of a two-dimensional transform in shown in FIG. 1b. The apparatus up to the N.times.N segmentation unit 20, and from the quantization unit 40 on, are the same as those of the standard compression apparatus of FIG. 1a. As shown in FIG. 1b, the output 25a and 25b of the N.times.N segmentation unit 20 consists of N.times.N pixel blocks. Adjacent pairs of pixel blocks 25a and 25b are combined at the doublevector production unit 27 to generate doublevectors 29. The doublevectors 29 are transformed at the two-dimensional transform unit 30 using additions, subtractions, and shifts to perform a GCT transform, as described in the above-referenced patent. The output doublevectors 31 are then decomposed to standard numerical form at the number extraction unit 33 to produce transform coefficients 35. The transform coefficients 35 are quantized and coded as described above.

One object of the present invention is to perform a linear transform, such as the 8 component GCT transforms 32 and 36 of FIG. 2, at high speed on a 32-bit processor, such as the MC68020 manufactured by Motorola. In a preferred embodiment two standard numbers will be combined in 32-bit registers. Thus the SISD (single-instruction single-data) processor is effectively treated as a SIMD (single-instruction multiple-data) machine. A linear transform consists of additions, subtractions and multiplications by constants. The multiplies will be replaced with some combination of adds, subtracts, left-shifts, and right-shifts. Table lookups and multiplications are avoided.

Note that significant bits migrate to the left under additions and subtractions. For example, two numbers with six significant bits can be added to provide a number with seven significant bits, e.g. ##EQU1## The maximum magnitudes are known for any computational point in a transform, so therefore by design the magnitudes of numbers are restricted to prevent magnitude overflow. However, sign bits of negative numbers can migrate to the lower bits of the upper number of a doublevector. Depending on the size of the transform and the desired accuracy, a right-shift may be required to "re-center" the data. Instead of multiplying by 5, it may therefore be preferable to multiply a first quantity by 2.5, and a "partner" quantity by 2.0, with the knowledge that these two quantities will eventually be multiplied together after some divisions have also been performed on these quantities.

According to the present invention, an N-bit number A and an M-bit number B are combined to produce an (N+M)-bit "doublevector" number C. The relation between the doublevector C and its component numbers, A and B, is represented by the notation C=[A, B]. Once the doublevector numbers are constructed, they are subject to a series of operations (most of which are simply normal arithmetic operations) to produce a doublevector output, and the doublevector output is then decomposed to provide component numbers. For instance, the additions

and

may be performed simultaneously by generating the doublevectors

and

performing an addition of the two doublevectors

and extracting the results X and Y from the doublevector Z. Subtraction is performed in an analogous way.

Similarly, a left shift by n bits of two (monovector) numbers A and B may be performed simultaneously by defining the doublevector

performing the left shift on C to provide an output doublevector C',

where "<<n" represents a left shift by n bits, and packing with zeros on the right, and decomposing the doublevector C' to provide

and

A first method for generating doublevectors is termed the linear method. According to the linear method the doublevector C generated from the m-bit number A and the n-bit number B is defined by

The extraction of A and B from C is given by

and

where ">>n" indicates a right-shift by n bits and extending the sign bit on the left. In the preferred embodiment A and B are 16-bit two's-complement signed integer numbers, C is a 32-bit doublevector, and

The extraction is then given by

and

(or equivalently A=C>>16, or any other equivalent combination of arithmetic and Boolean operations).

For instance if

then ##EQU2## where numbers with a "0x" prefix are written in hexadecimal notation.

Using the linear method the addition of the two 16-bit numbers 0.times.0041 and 0.times.0041 can be combined with the addition of the two 16-bit numbers 0.times.FFF7 and 0.times.FFF7, by performing the addition of the two 32-bit doublevectors, i.e. ##EQU3## The resulting sum is then decomposed according to the above method to provide the sums 0.times.0081=129, and 0.times.FFEE=-18.

Another method of generating doublevectors is termed the packing method. The (m+n)-bit doublevector C is generated from the m-bit number A and the n-bit number B according to the packing method by

where as in the C programming language, ".vertline." represents the bitwise OR operation. Therefore A is placed directly in the high-order portion of C, and B is placed in the n least significant bits of C. The inverse operation is simply

and

where as in the C programming language, "&" represents the bitwise AND operation. In particular, in the preferred embodiment where A and B are 16-bit numbers

and the inverse operation is

and

For instance, if A=0.times.0041 and B=0.times.FFF7, then C=0.times.0041 FFF7. It should be noted that although the quantities A, B and C above have been considered to be numbers, the linear and packing methods may also be applied to arrays or matrices.

With the packing method the addition of the two 16-bit numbers 0.times.0041 and 0.times.0041, and the addition of the two 16-bit numbers 0.times.FFF7 and 0.times.FFF7 is transformed into the addition of the two 32-bit doublevectors 0.times.0041 FFF7 and 0.times.0041 FFF7 to provide 0.times.0083 FFEE, which can be decomposed to provide the sums 0.times.0083=131 and 0.times.FFEE=-18. This example illustrates that the packing method sometimes produces errors in the least significant bit of the number placed in the high-order portion of the doublevector. The linear method does not suffer from this problem. However, the packing method is more rapid than the linear method since shifts, OR's, and AND's are quicker than multiplications and additions.

FIG. 3 provides a comparison of the results of additions for pairs of 4-bit numbers in 8-bit doublevectors using the linear method and the packing method. Whereas the first two sets of additions [(3+2) and (1+1), and (-3+2) and (1+1)] produce correct results with both the linear method and the packing method, the last two sets of additions [(3+2) and (1+{-1}), and (3+2) and (-1+{-1})] produce correct results with the linear method and incorrect results with the packing method. In general, a negative number in the low-order portion of a doublevector will introduce an error in the least significant bit of the number in the high-order portion of the doublevector. Usually the numbers stored in the doublevectors are large and such errors do not significantly affect the computation. Another method is to adjust the numbers so there are extra digits on the right side (to the right of the binary point).

A schematic of the circuitry for performing doublevector addition or subtraction operations is shown in FIG. 5. The storage register array 80 stores 32-bit doublevectors which have been generated using the linear method or the packing method. Pairs of 32-bit doublevectors chosen from the registers 80 according to the specifics of the calculation are directed over 32-bit lines 84 and 86 to an arithmetic logic unit (ALU) 82. The ALU 82 may be a Motorola MC68020, or any other 32-bit processor such as the Intel 80386 or 80486, the MIPS R3000, or a processor from the Sun SPARC family. The output of the ALU 82 is a 64-bit number which is directed over a 64-bit line 88 to a chosen register in the array 80. The number stored in the register is trimmed to a 32-bit number (which in this case is a doublevector) by discarding the upper 32 bits.

A comparison of the results of left shifting using the linear method and the packing method is provided in FIG. 4. When the number in the low-order portion of the doublevector is positive, as in the first example [(3<<1) and (1<<1)], then both the linear method and the packing method produce correct results. However, when the number in the low-order portion of the doublevector is negative, as in the second example [(3<<1) and (1<<1)], an error is introduced in the least significant bit of the number in the high-order portion of the doublevector using both the linear method and the packing method. It should be noted that left-shifts may cause the sign reversal of components of a doublevector just as left-shifts may cause the sign reversal of conventional two's-complement binary numbers. Generally, numbers stored in m-bit registers are (m-k) bit numbers and are shifted left by no more than k bits to prevent overflow.

The performance of a right-shift on doublevectors is different than a left-shift because when a right-shift is performed, the sign bit of the number in the low-order portion of the doublevector must be preserved. Suppose we want to right-shift by two bits the doublevector C=0.times.0040 FFF7 formed by the packing method from the two 16-bit numbers

and

A conventional 32-bit right-shift yields

and the component numbers by the packing method are 16 and +16,381, whereas a 2-bit right-shift performed directly on the component numbers yields 16 and -3. This discrepancy in sign is unacceptable.

As shown in FIG. 6, a proper right shift of a doublevector maintains the sign bits of each number component of the doublevector by replicating the sign bit of each number component. In this instance the high-order bits (including the sign bit) of the number in the low-order portion of the doublevector must remain as 1's, and the proper result is 0.times.0010 FFFD.

Using the 1MC68000 instruction set, for example, a proper right-shift of a doublevector requires the sequence of commands

where the swap C command swaps the upper and lower 16 bits of the 32-bit doublevector C, and the (asrw 2, C) command is an arithmetic right-shift by 2 bits on the lower 16 bits of C. This sequence of operations maintains the sign of the number in the lower 16 bits of the doublevector. It should be noted that if multiple right-shifts are to be performed on a doublevector, only the first swap in each asrw/swap/asrw/swap sequence need be performed; then a final swap may be necessary if an odd number of right-shifts were performed.

Using the doublevector method of the present invention, the linear transform ##EQU4## may be combined with the transform ##EQU5## by defining the doublevectors p=[x.sub.1, x.sub.2 ] and q=[Y.sub.1, Y.sub.2 ], performing the computation ##EQU6## and extracting the solutions x.sub.1 ', x.sub.2 ', y.sub.1 ' and y.sub.2 ' by the relations p'=[x.sub.1, x.sub.2 '] and q'=[Y.sub.1 ', Y.sub.2 '].

For instance, consider the linear transformation matrix ##EQU7## Because the entries of M are simple rational numbers the matrix operation M on (x.sub.1, y.sub.1)T can be performed by a combination of additions, subtractions, left-shifts, and right-shift, i.e. ##EQU8## If the transform M is to be performed on the pair of 1.times.2 matrices (x.sub.1, y.sub.1)T and (x.sub.2, y.sub.2).sup.T, then the calculation time may be reduced by calculating ##EQU9## and extracting the number components of p' and q'. Note that there is no need for addressing of the components of a doublevector during a doublevector calculation until the final stage when the component numbers are extracted. (Because the calculation of the two entries of (p',q').sup.T each include one right-shift but the right-shifted quantities are added to quantities which are not right-shifted, no swaps may be omitted.)

Many useful transforms require multiplications by irrational numbers and cannot be reduced to adds, subtracts, and shifts. However, since the GCT transform performed at transform units 32 and 36 of FIG. 2 will permit factoring such that these irrational multiplications may be combined with the quantization operation at quantization unit 40. The multiplications involve no additional computation. Note that for an N-dimensional transform, these multiplications can be coalesced such that their total cost is one-per-point instead of N-per-point. The remaining entries in the transform matrix may be replaced with rational numbers without losing the orthogonality of the transform. Useful transforms with this property include the Fast Hartley, Discrete Sine, and Discrete Cosine Transforms.

For the important image compression standard known as "JPEG" (Joint Photographic Experts Group) an approximation of the discrete cosine transform, adequate even for medical use, is given by the GCT transform, as described in the above-cited patent, using the substitutions for entries in the transform matrix listed in Table 1.

Hence useful transforms can be performed using simple rational numbers. The multiplies can be implemented as additions and shifts thereby allowing the application of the present invention. For instance, a multiplication by 1/.sqroot.2 (.apprxeq.0.70711) required by the GCT can be done with table-lookups, but using shifts and adds the multiplication can be implemented by

Set forth in Table 2 is a list of arithmetic primitives with their costs using both the standard approach and the approach of the present invention.

With the preferred embodiment of the present invention, additions, subtractions and left shifts of numbers of 16-bits or less are performed with twice the usual throughput by standard addition, subtraction and left-shift operations, respectively, on 32-bit doublevectors. Right-shifts on a doublevector requires one or two more operations than on normal numbers.

Lookups and multiplications of doublevectors are not used in the preferred embodiment of the present invention. If multiplications and table lookups were to be performed on doublevectors the number components of the doublevectors are extracted, then the operation performed on the number components, and finally, the numbers are recombined into doublevectors for further processing. (Note that table lookups of 32-bit doublevectors would require a prohibitively large table (2.sup.32 entries), and the multiplication of two 16-bit numbers generally produces a result with 32 significant bits, so the direct multiplication of doublevectors corrupts the data.)

As shown in Table 3, the method of the present invention reduces the number of additions, subtractions and left-shifts by a factor of two for a GCT transform on two 8.times.8 pixel blocks.

In the preferred embodiment for the MC68020, the packing method is used on the forward side of the transform process, and the linear method is used on the inverse side of the transform process. In the forward transform operation 8-bit pixel components are transformed to 11-bit coefficients, so errors in the least significant digit have a magnitude of only (1/2048). However, in the inverse transform operation 11-bit pixel components are transformed to 8-bit coefficients, so errors in the least significant digit have a magnitude of (1/256). Therefore the accuracy of the forward transform may be sacrificed for the sake of speed.

The error induced in the application of a forward and inverse transform may be decomposed into systematic error induced by precision constraints of integer arithmetic, quantization error, and the above-described errors related to the packing operation. For typical quantization the magnitude of the quantization error is much greater than the other to forms of error. Therefore, in practice the above-described method and apparatus prove useful.

After the transform of the doublevector pixel data by the transformunits 32 and 36 the data is transformed back to standard numbers for processing through the remainder of the compression system.

The foregoing description of the preferred embodiment of the invention has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed, and many modifications and variations are possible in light of the above example. Also, the present invention is compatible with existing standards, such as JPEG (Joint Photographic Experts Group). The present invention may also be adapted for sign-magnitude binary numbers. The preferred embodiment was chosen and described in order to best explain the principles of the invention and its practical applications to thereby enable others skilled in the art to best utilize the invention and various embodiments and with various modifications as are suited to the particular use contemplated. Many other variations are possible. For instance, although the majority of the present disclosure has addressed computations involving doublevectors, vectors with more than two numbers may be composed. (The term "doublevector" has only been used for convenience.) For example, the DEC Alpha series has 64-bit mathematics and so vectors containing four numbers may be used according to the present invention. Although the present invention has been presented in the context of transforms for data compression, the present invention is useful for other types of transforms, such as spectral analysis. Although the present invention has been discussed in the context of transforms, it may be used for other types of mathematical operations. Although particular combinations of arithmetic and Boolean operations have been provided for the linear and packing methods, any other equivalent combination of operations may be substituted. Although two doublevector methods have been detailed, other related methods may also be used. It is intended that the scope of the invention be defined only by the claims appended hereto.