Method and apparatus for compressing and decompressing images Number:6,801,665 from the United States Patent and Trademark Office (PTO) owispatent A method and apparatus for encoding (622) digital image data wherein a region of interest (606) can be specified either before the encoding process has begun or during the encoding process, such that the priority (616) of the encoder outputs are modified so as to place more emphasis on the region of interest, therefore increasing the speed and/or increasing the fidelity of the reconstructed region of interest. The system, therefore, enables more effective reconstruction of digital images over communication lines.<H decompressing, compressing, Method, and, appa, 6801665.html, Patent, pto, 6801665

Title: Method and apparatus for compressing and decompressing images

Abstract: A method and apparatus for encoding (622) digital image data wherein a region of interest (606) can be specified either before the encoding process has begun or during the encoding process, such that the priority (616) of the encoder outputs are modified so as to place more emphasis on the region of interest, therefore increasing the speed and/or increasing the fidelity of the reconstructed region of interest. The system, therefore, enables more effective reconstruction of digital images over communication lines.

Patent Number: 6,801,665 Issued on 10/05/2004 to Atsumi, et al.

Inventors: Atsumi; Eiji (Kamakura, JP), Farvardin; Nariman (Rockville, MD)
Assignee: University of Maryland (College Park, MD)
Mitsubishi Electric Corporation (Tokyo, JP)

Appl. No.: 09/623,473

Filed: November 17, 2000

PCT Filed: September 15, 1998

PCT No.: PCT/US98/19065

PCT Pub. No.: WO99/49412

PCT Pub. Date: September 30, 1999

Current U.S. Class: 382/239 ; 382/240

Current International Class: H04N 7/26 (20060101)

Field of Search: 382/232,239,240,242,243,282 358/539,537,538,1.15

References Cited [Referenced By]

U.S. Patent Documents


4811210	March 1989	McAulay
5412741	May 1995	Shapiro
5598216	January 1997	Lee
5729648	March 1998	Boyce et al.

Other References

Said et al. ("A new, Fast, and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees", IEEE, Transactions on Circuits and Systems for Video Technology, vol. 6, No. 3, Jun. 1996)..

Primary Examiner: Boudreau; Leo
Assistant Examiner: Dang; Duy M.
Attorney, Agent or Firm: Squire, Sanders & Dempsey L.L.P.

Claims

What is claimed is:

1. A method of image compression, said method comprising the steps of: providing digital image data including data on values and coordinates for a plurality of pixels; selecting a region of interest of an image represented by said digital image data; sorting and prioritizing said digital image data according to at least two priority categories, with digital image data corresponding to the region of interest having a higher priority than digital image data corresponding to areas outside of the region of interest; and transmitting said sorted and prioritized digital image data to a remote location, with the digital information data corresponding to the region of interest being transmitted with higher priority than the areas outside of the region of interest wherein said sorting and prioritizing of said digital image data further comprises the steps of: performing a wavelet transform of all the pixel values in the digital image data to obtain transform coefficients; identifying the transform coefficients corresponding to the region of interest; emphasizing the transform coefficients corresponding to the region of interest by scaling up the transform coefficients corresponding to the region of interest; ordering the transform coefficients including the scaled up transform coefficients; and entropy encoding the transform coefficients to form a bit stream.

2. A method of image compression, said method comprising the steps of: providing digital image data including data on values and coordinates for a plurality of pixels; selecting a region of interest of an image represented by said digital image data; sorting and prioritizing said digital image data according to at least two priority categories, with digital image data corresponding to the region of interest having a higher priority than digital image data corresponding to areas outside of the region of interest; and transmitting said sorted and prioritized digital image data to a remote location, with the digital information data corresponding to the region of interest being transmitted with higher priority than the areas outside of the region of interest, wherein said step of transmitting said sorted and prioritized digital image data to the remote location includes performing a wavelet transform of all the pixels values in the digital image data to obtain transform coefficients, transmitting the sorted and prioritized digital image data corresponding to the region of interest at a higher rate such image data corresponding to the region of interest at a higher rate such that the region of interest can be reconstructed at a higher fidelity than areas outside of the region of interest, said higher fidelity being provided by said sorting and prioritizing of said digital image data corresponding to the region of interest.

3. A method for encoding and decoding an image, said method comprising the steps of: providing digital image data in a computer-readable format, said digital image data including data on values and coordinates for a plurality of pixels; sorting said digital image data according to a sorting protocol for the entire image, said digital image data being sorted and prioritized according to a predetermined prioritization formula; transmitting said sorted data to a receiver, and repeating said sorting and transmitting until a partial reconstructed image appears on a display at the receiver; selecting a region of interest based upon said partial reconstructed image; transmitting data from said receiver to a computer transmitting data identifying the selected region of interest; modifying the sorting of the digital image data based upon the selected region of interest, wherein digital image data corresponding to the region of interest is sorted and prioritized to have a higher priority than digital image data corresponding to areas outside of the region of interest; and transmitting said modified sorted and prioritized data to the receiver, with said region of interest being transmitted with higher priority than the areas outside of the region of interest, wherein said step of transmitting said sorted data includes transmitting said sorted data onto a network, wherein said receiver is a receiving computer on said network, and wherein said step of selecting the region of interest is performed at said receiving computer.

4. A method of encoding digital data representing an image, the method comprising the steps of: providing digital image data in a computer-readable format, the digital image data including data on values and coordinates for at least one image; selecting at least one region of interest of an image represented by the digital image data; performing a wavelet transform selected from the group consisting of a mallet type wavelet transform, a spacl type wavelet transform, and a packet type wavelet transform on the digital image data to obtain subbands containing transform coefficients; identifying transform coefficients corresponding to the at least one selected region of interest; specifying a priority to each region of interest; classifying the transform coefficients in each subband into at least one sequence; allocating a bit-rate to each sequence of transform coefficients; quantizing the transform coefficients in each sequence by a quantization scheme selected based upon the allocated rate; scaling up bit significance levels of bit planes consisting of the quantized transform coefficients corresponding to each region of interest based upon the priority specified for each region of interest; modifying an encoding ordering of the bit planes consisting of quantized transform coefficients based upon the scaled up bit significance levels of the transform coefficients; and entropy encoding the bit planes of the quantized transform coefficients according to the modified encoding ordering to generate an encoded bit stream of digital image data.

5. The method of claim 4 further comprising the step of identifying the coefficients necessary and sufficient to encode the region of interest to be reconstructed up to a highest fidelity in a target spatial resolution image.

6. The method of claim 4 wherein the step of identifying the coefficients corresponding to the region of interest further comprises the steps of: identifying pixels on boundaries of the region of interest; identifying pixels one pixel inside the region of interest along one of a vertical and horizontal direction of the image if at least one of a low pass and a high pass filter which perform the wavelet transform and an inverse wavelet transform has an odd filter length; tracing an input-output relationship of one of the wavelet transform and the inverse wavelet transform from an image domain to each subband domain to identify the transform coefficients which correspond to the pixels identified in the previous steps; forming boundaries of a corresponding region of interest in each subband domain based upon the identified coefficients in the previous step; and identifying coefficients surrounded by the boundaries in each subband as coefficients corresponding to the region of interest.

7. The method of claim 4 wherein the step of identifying the coefficients corresponding to the region of interest further comprises the steps of: identifying a set of transform coefficients which correspond to each pixel in the region of interest by tracing an input-output relationship of one of a set of wavelet transforms performed on the pixel and a set of inverse wavelet transforms which reconstruct a pixel value; and forming a coefficient identification result such that a set of transform coefficients corresponding to each pixel can be identified.

8. The method of claim 4 wherein the step of entropy encoding the bit planes produces encoded information that is in the form of a number of bits, and the method further comprises the steps of: allocating the number of bits separately for use in representing the bit planes consisting only of the transform coefficients corresponding to the regions of interest in each sequence of transform coefficients, for use in representing the bit planes consisting of all the transform coefficients in the same sequence, and for use in representing the bit planes consisting of the transform coefficients corresponding to the regions outside of the region of interest in the same sequence such that the number of bits to reconstruct the region of interest and the number of bits to reconstruct the regions outside of the region of interest will be separately controlled; and aligning encoded bit portions of the bit planes such that a certain series of bit portions representing the region of interest will be transmitted at the earlier stage of transmission than bit portions representing regions outside of the region of interest.

9. The method according to claim 4 wherein the step of selecting a region of interest further comprises selecting a plurality of regions of interest in the image and assigning each region a priority and wherein the step of classifying the transform coefficients in each subband into at least one sequence further comprises the step of classifying the transform coefficients such that at least one sequence corresponds to each of the plurality of regions of interest.

10. The method of claim 4 wherein the step of performing a wavelet transform on a digital image further comprises dividing the image into rectangular blocks of pixels such that some blocks only contain pixels which are inside the region of interest, some block only contain pixels which are outside of the region of interest, and some blocks contain some pixels which are inside the region of interest and some pixels which are outside of the region of interest and performing a wavelet transform on each rectangular block of pixels, and the method further comprises the steps of defining the region of interest by selecting entire rectangular blocks of pixels to be included in the region of interest and by individually selecting pixels within rectangular blocks in which there exist boundaries between the region of interest and regions outside of the region of interest to be included in the region of interest; scaling up the bit significance level of all the transform coefficients corresponding to the rectangular blocks of pixels entirely within the region of interest and scaling up the bit significance level of the transform coefficients corresponding to pixels belonging to the region of interest in blocks that overlap the boundaries of the region of interest based upon the priority assigned to the region of interest; modifying a predetermined encoding ordering of the bit planes of the quantized transform coefficients in the blocks overlapping the boundaries of the region of interest based upon scaling up the bit significance level of the transform coefficients inside the region of interest; entropy encoding the bit planes of the quantized transform coefficients in the blocks which do not overlap the boundaries of the region of interest according to the predetermined encoding ordering, and encoding the bit plane of the quantized transform coefficients in the blocks which overlap the boundaries of the region of interest according to the modified encoding ordering; and adjusting the ordering of the encoded bit sequences of the bit planes of all the blocks such that the ordering of bit sequences of bit planes in the blocks inside the region of interest are given higher priority by a priority value assigned to the region of interest and the ordering of the bit sequences of the bit planes in the blocks outside of the region of interest and in the blocks overlapping the region of interest are the same as the encoding ordering of the corresponding blocks in order to generate the encoded bit stream of digital data.

11. The method of claim 4 wherein the step of entropy encoding further comprises performing data compression on the coefficients such that more information concerning regions outside of the region of interest is lost than is information concerning the region of interest.

12. A method of decoding information representing an image, the method comprising the steps of: receiving the information in a computer-readable format, the received information including digital data representing an image and digital data concerning at least one region of interest in the image; locating at least one region of interest in the image to be reconstructed from the encoded bit stream according to the information concerning the at least one region of interest; identifying digital data corresponding to specified regions of interest; modifying a decoding ordering of the encoded bit stream based upon a priority assigned to each region of interest; entropy decoding the encoded bit stream according to the modified decoding ordering in order to obtain bit planes corresponding to quantized transform coefficients having a same bit significance level; scaling down the bit significance level of the bit planes including quantized transform coefficients corresponding to each region of interest in order to obtain original bit significance levels of the quantized transform coefficients; de-quantizing the quantized transform coefficients according to a de-quantization scheme to obtain sequences of transform coefficients; declassifying the sequences of transform coefficients into a set of subbands; and performing an inverse wavelet transform selected from a mallet type transform, a spacl type transform, and a packet type transform on the subbands in order to reconstruct the digital image data.

13. The method of claim 12, further comprising the steps of: identifying a number of bits separately for use in entropy decoding a portion of the encoded bit stream in order to obtain bit planes consisting only of transform coefficients corresponding to the region of interest, for use in obtaining bit planes consisting of all transform coefficients in the same sequence, and for use in obtaining the rest of the bit planes consisting of transform coefficients outside the region of interest in the same sequence such that the number of bits used to reconstruct the region of interest and the number of bits to reconstruct the regions outside of the region of interest will be separately controlled; and aligning the portions of received encoded bit stream such that a certain series of the bit portions representing the region of interest will be decoded at an earlier stage in reconstruction of the region of interest.

14. The method of claim 12 wherein the step of receiving the information further comprises receiving the information such that information corresponding to the region of interest is received at a higher rate than information corresponding to regions of the image outside of the region of interest is received.

15. The method according to claim 12 wherein the step of identifying digital data corresponding to a region of interest further comprises the steps of: identifying digital data corresponding to a plurality of regions of interest in the image represented by the information; determining a priority corresponding to each of the plurality of regions of interest; and reconstructing the image by reconstructing the plurality of regions of interest in a manner that is dependent upon each of the region's determined priority.

16. The method of claim 12 wherein the encoded bit stream of the digital image data consists of sets of encoded bit planes representing rectangular blocks of pixels in the image, the method further comprising the steps of: modifying a decoding ordering of encoded bit planes for rectangular blocks overlapping the boundaries of the region of interest based upon the priority value assigned to the region of interest; entropy decoding encoded bit planes for the rectangular blocks which do not overlap boundaries of the region of interest according to one decoding ordering, and entropy decoding encoded bit planes for rectangular blocks which overlap the boundaries of the region of interest according to the modified decoding ordering in order to obtain bit planes consisting of a same bit significance level of the quantized transform coefficients in each sequence; scaling down the bit significance level of the bit planes consisting only of the quantized transform coefficients corresponding to the region of interest within the blocks overlapping the boundaries of the region of interest according to the priority value assigned to the region of interest in order to obtain an original bit significance level of the bit planes; and performing an inverse wavelet transform on each set of subbands containing quantized transform coefficients in order to reconstruct each rectangular block in the digital image.

17. An encoding device for encoding information representing an image, the device comprising: receiving means for receiving information including data on values and coordinates for a plurality of pixels; selecting means for selecting at least one region of interest in the image represented by the information; wavelet based bit plane coder means for performing a wavelet transform selected from the group consisting of a mallet type wavelet transform, a spacl type wavelet transforms and a packet type wavelet transform on the information to obtain subbands containing coefficients; identification means for identifying coefficients corresponding to the at least one region of interest; ordering means for ordering the coefficients according to a plurality of categories wherein at least one category corresponds to coefficients representing the region of interest and at least one category corresponds to coefficients representing regions outside of the region of interest; entropy encoding means for encoding the coefficients according to the category into which the coefficients were placed to obtain a number of bits representing the encoded coefficients; transmitting means for transmitting the bits in a bit stream to a remote location, such that the manner in which the bits are transmitted depends upon the category of coefficients to which the bits correspond; and bit allocation means for allocating a predetermined number of bits for use in representing each category of coefficients wherein the number of bits allocated to represent the categories of coefficients corresponding to the region of interest of the image is such that the region of interest of the image can be reconstructed with a higher fidelity than the regions of the image outside of the region of interest; and bit stream allocation means for allocating a fixed portion of bits of the bit stream transmitted per unit time for transmitting bits corresponding to categories of coefficients corresponding to the region of interest.

18. An encoding device for encoding information representing an image the device comprising: receiving means for receiving information including data on values and coordinates for a plurality of pixels; selecting means for selecting at least one region of interest in the image represented by the information; wavelet based bit plane coder means for performing a wavelet transform selected from the group consisting of a mallet type wavelet transform a spacl type wavelet transform, and a packet type wavelet transform on the information to obtain subbands containing coefficients; identification means for identifying coefficients corresponding to the at least one region of interest; ordering means for ordering the coefficients according to a plurality of categories wherein at least one category corresponds to coefficients representing the region of interest and at least one category corresponds to coefficients representing regions outside of the region of interest; entropy encoding means for encoding the coefficients according to the category into which the coefficients were placed to obtain a number of bits representing the encoded coefficients; and transmitting means for transmitting the bits in a bit stream to a remote location, such that the manner in which the bits are transmitted depends upon the category of coefficients to which the bits correspond, wherein the ordering means further comprise block ordering means for ordering the coefficients according to categories such that some categories of coefficients contain information that corresponds to rectangular blocks of pixels in the image wherein all the pixels in the corresponding block are either inside the region of interest or outside of the region of interest, and some categories of coefficients contain information that corresponds to rectangular blocks of pixels in the image wherein some of the pixels in the corresponding block are inside the region of interest and some of the pixels are outside of the region of interests.

19. A decoding device for receiving and decoding information representing an image, the device comprising: receiving means for receiving the information including data on values and coordinates for a plurality of pixels; identification means for receiving the information from the receiving means and identifying at least two categories of information corresponding to regions of the image such that at least one category corresponds to information representing a region of interest in the image and at least one category corresponds to information representing a region in the image outside of the region of interest; entropy decoding means for entropy decoding the information according to the information's category; and reconstructing means for reconstructing the image from the entropy decoded information such that the manner in which regions of the image are reconstructed depends upon the category of the information representing the region, wherein the received information is in the form of a bit stream and a fixed portion of bits in the bit stream received per unit time corresponds to the region of interest, and wherein the reconstructing means reconstruct the region of interest more quickly than regions of the image outside of the region of interest and with a higher fidelity than regions outside of the region of interest.

20. A decoding device for receiving and decoding information representing an image, the device comprising: receiving means for receiving the information including data on values and coordinates for a plurality of pixels; identification means for receiving the information from the receiving means and identifying at least two categories of information corresponding to regions of the image such that at least one category corresponds to information representing a region of interest in the image and at least one category corresponds to information representing a region in the image outside of the region of interest; entropy decoding means for entropy decoding the information according to the information's category; and reconstructing means for reconstructing the image from the entropy decoded information such that the manner in which regions of the image are reconstructed depends upon the category of the information representing the region, wherein the identification means further comprise: multiple region of interest identification means for identifying a plurality of categories corresponding to a plurality of regions of interest in the image represented by the information; and priority determining means for determining a priority corresponding to each of the plurality of regions of interest; and wherein the reconstructing means reconstruct the plurality of regions of interest in a manner that is dependent upon each of the region's priority.

21. A decoding device for receiving and decoding information representing an image the device comprising: receiving means for receiving the information including data on values and coordinates for a plurality of pixels; identification means for receiving the information from the receiving means and identifying at least two categories of information corresponding to regions of the image such that at least one category corresponds to information representing a region of interest in the image and at least one category corresponds to information representing a region in the image outside of the region of interest, entropy decoding means for entropy decoding the information according to the information's category; and reconstructing means for reconstructing the image from the entropy decoded information such that the manner in which regions of the image are reconstructed depends upon the category of the information representing the region, wherein the identification means further comprise rectangular block identification means for identifying categories of information containing information that corresponds to rectangular blocks of pixels in the image wherein all the pixels in each corresponding block are either inside the region of interest or outside of the region of interest and categories of information containing information that corresponds to rectangular blocks of pixels in the image wherein some of the pixels in each corresponding block are inside the region of interest and some of the pixels are outside of the region of interests.

22. A method of encoding digital image data representing an image, said method comprising the steps of: selecting at least one region of interest in an image represented by said digital image data; performing a wavelet transform on the digital image data to obtain transform coefficients; identifying the transform coefficients corresponding to the region of interest; assigning a priority to the at least one region of interest; emphasizing the transform coefficients corresponding to the region of interest by scaling up the transform coefficients corresponding to the region of interest; ordering the transform coefficients including the scaled up transform coefficients; quantizing the transform coefficients including the scaled up transform coefficients; and entropy encoding the transform coefficients to form a bit stream.

23. A method of encoding digital image data representing an image, said method comprising the steps of: selecting at least one region of interest in an image represented by said digital image data; performing a wavelet transform on the digital image data to obtain transform coefficients; identifying the transform coefficients corresponding to the region of interest; and assigning a priority to the at least one region of interest, quantizing the transform coefficients to obtain quantization indices; emphasizing quantization indices corresponding to the region of interest by scaling up the quantization indices corresponding to the region of interest; ordering the quantization indices including the scaled up quantization indices; and entropy encoding the quantization indices to form a bit stream.

Description

BACKGROUND OF THE INVENTION:

1. Field of the Invention

Modern computers and modern computer networks enable the transfer of a significant amount of information between computers and between a computer and a storage device. When computers access local storage devices, such as a local hard drive or local floppy drive, significant amounts of information can be quickly accessed. However, when seeking to access data from a remote storage location such as over a wide area network (WAN), the internet, or a wireless communication channel (cellular phone network, etc), data transfer rates are significantly slower. Transferring large files, therefore, takes significant amounts of time. Additionally, storage of large files utilizes valuable and limited storage space. Photographic images and similar graphical images typically are considered to be large files, since an image conventionally requires information on each picture element or pixel in the image. Photographs and similar graphical images, therefore, typically require over one megabyte of storage space, and therefore require significant transmission times over slow network communications. In recent years, therefore, numerous protocols and standards have been developed for compressing photographic images to reduce the amount of storage space required to store photographic images, and to reduce transfer and rendering times. The compression methods essentially create mathematical or statistical approximations of the original image.

Compression methods can broadly be categorized into two separate categories: Lossy compression methods are methods wherein there is a certain amount of loss of fidelity of the image; in other words, close inspection of the reproduced image would show a loss of fidelity of the image. Lossless compression methods are ones where the original image is reproduced exactly after decoding. The present invention is directed to an efficient image compression method and apparatus wherein a part, or parts, of an image can be compressed with a higher level of fidelity in the reproduced image than other parts of the image, based on a selection of region-of-interests by the user or the system which is initially encoding or compressing the image, or the user or the system which receives and decodes the image data through interaction with the encoding side.

2. Description of the Related Art

A currently popular standard for compressing images is called the JPEG or "J-peg" standard. This standard was developed by a committee called The Joint Photographic Experts Group, and is popularly used to compress still images for storage or network transmission. Recent papers by Said and Pearlman discuss new image coding and decoding methods based upon set partitioning in hierarchical trees (SPIHT). See Said and Pearlman, Image Codec Based on Set Partitioning in Hierarchical Trees, IEEE Transactions on Circuits and Systems for Video Technology, vol. 6, no. 3, June 1996, and Said and Pearlman, Image Multi-Resolution Representation, IEEE Transactions on Image Processing, vol. 5, no. 9, September 1996. The contents of these papers are hereby incorporated by reference. These references disclose computer software which, when loaded and running on a general purpose computer, performs a method and creates an apparatus which utilizes integer wavelet transforms which provide lossy compression by bit accuracy and lossless compression within a same embedded bit stream, or an apparatus which utilizes non-integer wavelet transforms which provide lossy compression by bit accuracy within a single embedded bit stream. An image which is initially stored as a two dimensional array representing a plurality of individual pixels prioritizes bits according to a transform coefficient for progressive image transmission.

The most important information is selected by determining significant or insignificant elements with respect to a given threshold utilizing subset partitioning. The progressive transmission scheme disclosed by Said and Pearlman selects the most important information to be transmitted first based upon the magnitude of each transform coefficient; if the transform is unitary, the larger the magnitude, the more information the coefficient conveys in the mean squared error (MSE, D.sub.mse ( )) sense; ##EQU1##

where (i,j) is the pixel coordinate, with p, therefore representing a pixel value. Two dimensional array c is coded according to c=.OMEGA. (p), with .OMEGA.(.) being used to represent a unitary hierarchical subband transformation. Said and Pearlman make the assumption that each pixel coordinate and value is represented according to a fixed-point binary format with a relatively small number of bits which enables the element to be treated as an integer for the purposes of coding. The reconstructed image p is performed by setting a reconstruction vector c to 0, and calculating the image as:

N is the number of image pixels, and the above calculation for mean squared-error distortion can therefore be made. Using mathematical assumptions, it is known that the mean squared-error distortion measure decreases by .parallel.c.sub.i,j .parallel..sup.2 /N. This fact enables pixel values to be ranked according to their binary representation, with the most significant bits (MSBs) being transmitted first, and also enables pixel coefficients with larger magnitude to be transmitted first because of a larger content of information. An algorithm is utilized by the encoder to send a value representing the maximum pixel value for a particular pixel coordinate, a sorting pixel coordinates by wavelet transform coefficient values, then outputting a most significant bit of the various coefficients, using a number of sorting passes and refinement passes, to provide high quality reconstructed images utilizing a small fraction of the transmitted pixel coordinates. A user can set a desired rate or distortion by setting the number of bits to be spent in sorting passes and refinement passes.

SUMMARY OF THE INVENTION

The invention is a method and apparatus for encoding images for transmission or storage where a region of interest (ROI) or certain regions of the image are to be emphasized and for decoding the encoded image after transmission or retrieval from storage. The encoding method includes selecting a region or regions of interest in digital image data, and specifying a priority to each region. A wavelet transform of the pixel values of the entire image is performed in order to obtain the transform coefficients of the wavelet, and the transform coefficients corresponding to each region of interest are identified. The transform coefficients for each region of interest are emphasized by scaling up these transform coefficients in such a way that more bits are allocated to these transform coefficients or encoding ordering of these coefficients are advanced. After the scaling up the transform coefficients for each region of interest, quantization is performed on the transform coefficients for the entire image in order to obtain the quantization indices. In the alternative, the quantization indices of the quantized transform coefficients corresponding to each region of interest are scaled up according to the priority assigned to each region of interest. After the quantization for the entire image, scaling up is performed for each region of interest. The quantization indices of the transform coefficients are entropy encoded based upon the encoding strategy such as encoding ordering or bit allocation determined by the scaling up for each region of interest in order to form a data bit stream. A bit stream header is formed, and the data bit stream is appended to the bit stream header. The entropy coding is performed on each bit field of the binary representation of the quantization indices of the transform coefficients. Either bit plane coding is used, such as a binary arithmetic coding technique, or a zero-tree coding technique, such as SPIHT coding, is used. The decoding method includes separating the bit stream header from the data bit stream, decoding the description such as coordinates of the region or regions of interest, priority to each region, size of the image, and the number of wavelet decomposition levels from the bit stream header. The wavelet transform coefficients corresponding to a region or regions of interest specified by the description of the region or the regions of interest are identified, and the data stream is entropy decoded by following the decoding ordering determined by the identified result of the transform coefficients corresponding to each region of interest and the priority assigned to each region of interest. This forms a set of subbands containing the quantization indices of the transform coefficients. Either the de-quantized transform coefficients or the quantization indices of the transform coefficients corresponding to each region of interest are scaled down. If scaling up and quantization are performed in this order at the encoder, de-quantization of the transform coefficients for the entire image and scaling down the quantized transform coefficients for each region of interest is performed in this order; if quantization and scaling up are performed in this order at the encoder, scaling down the quantization indices for each region of interest and de-quantization of the quantization indices for the entire image is performed in this order. In either case, de-quantization is performed on the quantization indices in order to obtain the quantized transform coefficients. The inverse wavelet transform is performed on the de-quantized transform coefficients in order to form the pixel values on the entire image. The digital image in this invention can be not only two dimensional digital data but also one dimensional digital data such as voice data, electrocardiogram data, seismic wave data. When the data is one dimensional, steps and means based on wavelet transform, subband, ROI coefficient identification or inverse wavelet transform which are applied along each dimension of the two dimensional data are applied only along the single dimension of the data.

BRIEF DESCRIPTION OF THE DRAWINGS

For a clear understanding of the embodiments of the invention, reference should be made to the accompanying drawings, wherein:

FIG. 1 illustrates a method for compressing an image with an emphasis on a selected region of interest in an image by allocating more bits to the region of interest;

FIG. 2 illustrates a method of decompressing an image which is encoded with an emphasis on a selected ROI;

FIGS. 3A-3F illustrate a method of ROI coefficient scaling;

FIGS. 4A and 4B illustrate an ROI coefficient scaling method wherein multiple regions of interest are to be emphasized with different priorities;

FIGS. 5A-5C illustrate an ROI coefficient scaling method that uses some of the bit elements in the quantization indices for a ROI in order to emphasize the ROI;

FIGS. 6A-6C illustrate an ROI coefficient scaling method where multiple regions of interest are emphasized from different stages of encoding with different priority is disclosed;

FIGS. 7A-7D illustrate entropy coding of the quantization indices with a bit plane based coder under the encoding strategy determined by the ROI coefficient scaling.

FIGS. 8A-8C illustrate the case where bit plane coding is performed in each subband where ROI coefficient scaling is used only on the bit fields at some bit significance levels;

FIG. 9 illustrates an identification process performed only on the pixels on the boundaries of the region of interest and on the pixels which locate one pixel inside the boundaries of the region of interest;

FIGS. 10A and 10B illustrate a wavelet transform accomplished by a low pass filter whose filter coefficients are g.sub.A (k) and a high pass filter whose filter coefficients are f.sub.A (k) and a down sampler which discards every other pixel or transform coefficient;

FIG. 11 illustrates an encoding method for representing the input image with a set of subbands consisting of the transform coefficients;

FIG. 12 illustrates a method of decompressing an image which is encoded by the encoding method of FIG. 11 with an emphasis on a selected region of interest;

FIG. 13 illustrates ROI coding when encoding and decoding are done on a block by block basis;

FIG. 14 is a flow chart of another method of encoding data in accordance with the present invention;

FIG. 15 illustrates an approach whereby a total number of bits to be used to encode the digital data representing the image is determined;

FIG. 16 shows a block diagram of an embodiment of an encoding device of the present invention;

FIG. 17 depicts a block diagram of an embodiment of a decoding device of the present invention; and

FIG. 18 depicts an embodiment wherein the device includes a transmitting side that encodes the image and transmits the encoded data to a receiving side which receives and displays the image.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

The present invention is directed to a method and apparatus of performing image compression wherein a region of interest specified by the user is emphasized so that it is encoded with higher fidelity than the rest of the image. The emphasis can occur either during the beginning or from the middle of the encoding process. If it occurs during the middle of encoding, the emphasis can be driven by the use at the receiving side which receives portions of the encoded bit stream while the encoding is underway. The emphasis to the region of interest is done in the transform coefficient domain in order not to cause artificial boundaries around the region of interest on the reconstructed image. In an embodiment where the emphasis is done on the transform coefficients after the quantization, information ordering of the quantization indices corresponding to the region of interest is modified so that the region of interest can be reconstructed at the earlier stages of progressive reconstruction; therefore, the region of interest is reconstructed with a higher fidelity at the low bit rate. Since the emphasis on the region of interest merely modifies the ordering with which the bit fields of the quantization indices are encoded, the emphasis does not cause any information loss. Also the modification of the information ordering is applicable not only by each coefficient level but also by each bit field level of the coefficient, which not only improves the quality of the specific parts of the image but also flexibly modifies the encoding ordering with which each part of the image is reconstructed. Another embodiment of this invention is to emphasize the transform coefficients before quantization. This embodiment does not provide such a flexible functionality as the other mode, but makes it possible to reconstruct the region of interest with higher fidelity than the rest of the image at any bit rate at a minimal increase of computational complexity.

FIG. 1 illustrates a method for compressing an image with an emphasis on a selected region of interest in an image by allocating more bits to the region of interest or encoding the region of interest at the earlier stages of the encoding process than to the regions outside of the region of interest. Encoding method 100 comprises step 101 for performing a wavelet transform on the pixel values of the input digital image in order to represent the input image by a set of subbands consisting of the transform coefficients. Step 101 is followed by bit allocation step 102 and a quantization step 103. At step 102, a bit per coefficient (i.e., representation accuracy of the coefficient) is assigned to the transform coefficients in each subband in order to represent the transform coefficients with digitized values is determined in such a way that the subband which has higher variance or higher energy of the transform coefficients will be allocated a larger number of bits per coefficient, which is equivalent to being allocated a smaller quantization step size. However, in the case where the bit per coefficient for each subband or for all the subbands is predetermined, step 102 is not performed. The allocated bits per coefficient are used in step 103. At step 103, quantization is performed on the transform coefficients in each subband in order to represent the transform coefficients of each subband with quantization indices whose representation accuracy is specified by the allocated bits per coefficient or by the quantization step size for each subband. Through step 103, quantization indices representing transform coefficients with a reduced or the same representation accuracy of the transform coefficient values is obtained. The obtained quantization indices are input to ROI coefficient scaling step 107.

Before, after, or together with steps 101, 102 and 103, region of interest selection step 104, ROI coefficient identification step 105, and ROI coordinate description step 106 are performed. At step 104, the region of interest is selected on the input image and the coordinates of the selected region of interest are input to steps 105 and 106. At step 105, wavelet transform coefficients corresponding to the selected region of interest, i.e., ROI coefficients, in each subband are identified in order to emphasize the selected region of interest in the image by emphasizing the ROI coefficients in each subband containing the wavelet transform coefficients. The identification result of the ROI coefficients (i.e., categories of the coefficients), which depicts whether the transform coefficients correspond to each region of interest or regions outside of the region of interest, is input to step 107. At ROI coordinate description step 106, coordinates of the selected region of interest are encoded in order to effectively transmit or store the ROI coordinate information, from which decoder can tell what region of interest is selected to be emphasized in the reconstructed image.

The ROI description information is added to the header bits in the bit stream in transmission step 109.

At ROI coefficient scaling step 107, among the quantization indices input from 103, only the quantization indices for the transform coefficients corresponding to the region of interest are emphasized in such a way that the quantization indices for the ROI coefficients are scaled up by a left bit shift value (S) specified by a priority assigned to the region of interest so that the indices for the ROI coefficients are to be encoded as if the indices had larger values than their actual values. Therefore, they are encoded with a larger number of bits at a given bit rate or encoded at the earlier stages of the encoding process, at the following step 108 entropy encoding. The quantization indices, some of which are scaled up, are input to step 108 together with the category of the coefficients, the identification result of ROI coefficients, formed at step 105 and the priority (the left bit shift value, S) used for the scaling up.

At step 109 entropy coding, an entropy coding is performed on each bit element of the binary representation of the quantization indices in order to form an encoded data stream within which encoded bits generated from the bit fields at the higher bit significance level of the quantization indices are placed in the earlier portion of the bit stream than other encoding bits generated from the bit fields at the lower bit significance level. In other words, an entropy coding is performed on each bit field of the binary representation of the quantization indices in such an order that the bit field at the highest bit significance level (Most Significant Bit) is encoded first and bit fields at the decreasing order of bit significance levels are encoded in a decreasing order of bit significance levels. The entropy coding step can be terminated or suspended at any bit rate: when the bit budget for the encoded bit stream is used up, when the receiving side or storing side of the encoded bit stream does not need any further bits, when user or a system at the encoding side wants to terminate or suspend the step or when user or a system at the receiving side wants to terminate or suspend the step.

The encoder avoids encoding bit fields of the bottom S least bit significance levels in the quantization indices for the ROI coefficients, because these bit fields, which do not exist before the scaling up of the ROI coefficients by S left bit shift, do not convey any information. Alternatively, in order to reduce the computational cost to avoid encoding these bottom S bit fields, these fields whose values are uniformly filled with 0 may be encoded together with the bottom S bit fields of the quantization indices for the regions out of the region of interest at the expense of increasing encoded bit rate. Top S bit fields of the quantization indices for the ROI coefficients are exclusively encoded without encoding any bit fields of the quantization indices for the regions outside of the region of interest in the same subband. Alternatively, in order to reduce computational cost to selectively encode the top S bit fields for the region of interest, these bit fields may be encoded together with the bit fields for the regions outside of the region of interest whose values are filled uniformly with 0 at the expense of increasing encoded bit rate.

The preferable encoding technique in step 108 is either a bit plane coding such as a binary arithmetic coding technique or a zero tree coding such as the SPIHT coding technique. With a bit plane coding technique, all the bit fields at a certain bit significance level in each subband are encoded at the same encoding stage. After these bit fields are encoded, other bit fields in another bit significance level are encoded. In many cases, bit fields of the higher bit significance levels are encoded earlier than the bit fields of the lower bit significance levels in the same subband. In such cases, encoding results of the bit fields in the higher bit significance levels may be used for encoding the bit fields in the lower bit significance levels. With a zero tree coding technique, bit fields at the higher bit significance level in each quantization index are always encoded earlier than the bit fields at the lower bit significance level in each quantization index, but some of the bit fields at the lower bit significance level in the same quantization indices are encoded earlier than the bit fields at the higher bit significance level in other quantization indices. Encoded data formed at step 108 is sent to transmission step 109 where data bits and header bits are appended into a bit stream to be transmitted or stored.

In a subband where the allocated bits per coefficient is smaller than the representation accuracy of the transform coefficients, each transform coefficient is represented by a quantization index whose representation accuracy is smaller than the accuracy with which the value of the quantized transform coefficients are represented. In a subband where the allocated bits per coefficient is the same as the representation accuracy of the value of the transform coefficients, each transform coefficient may not be quantized and each coefficient value itself may be regarded as a quantization index to be given to ROI coefficient scaling step 107. This invention goes with any kind of quantization schemes where the larger transform coefficient is to be represented with the larger quantization index. Preferred quantization in this invention is either a scalar quantization or a trellis coded quantization. With a scalar quantization, transform coefficients are quantized into indices based on the magnitudes of the coefficients with respect to a set of threshold values. With a trellis coded quantization, transform coefficients are quantized into indices not only based on the magnitude of themselves but also the states of the quantizer.

In FIGS. 3A-3F, ROI coefficient scaling step 107 is illustrated. ROI coefficient scaling is performed on the quantization indices of the transform coefficients either in each subband, in all the subbands or in several groups of subbands at a time. In a situation where the scaling is performed in each subband, each subband can be assigned a different priority including no priority (left bit shift value, S) to the quantization indices for the region of interest. In a situation where a selected region of interest needs to be emphasized in an image reconstructed only from some of the subbands, the ROI coefficient scaling needs to be performed only in the selected subbands (e.g., when a lower spatial resolution version of the image is reconstructed, ROI coefficients in the subbands which are not necessary for reconstructing the target spatial resolution are not scaled up). Hereafter, ROI coefficient scaling in each subband is disclosed, which can be generalized to be an ROI coefficient scaling to be performed in all the subbands or in several groups of subbands at a time, e.g., by assigning the same priority value to the quantization indices for the region of interest in all the subbands or in several groups of subbands.

To illustrate this concept, let us denote transform coefficients in one subband (subband[k]) as Y(j) where j (0=j<J) represents a coordinate of the transform coefficients and corresponding quantization indices in the subband[k], quantization index of the Y(j) as Z(j), allocated bits per coefficient at the step 102 as N, bit fields of the binary representation of the quantization index Z(j) are b.sub.N-1 (j), b.sub.N-2 (j), . . . , and b.sub.o (j), (b.sub.k (j), 0<=k<N, is either 0 or 1; b.sub.N-1 (j) is the bit field in the highest bit significance level of the Z(j)). Binary representation of the quantization index Z(j) is the following:

(Before the ROI coefficient scaling is performed, b.sub.n (j) represents a bit value in the bit significance of 2.sup.n.)

When the transform coefficients identified as corresponding to the region of interest (i.e., ROI coefficients), Y(j) where j=js, js+1, . . . and je, quantization indices Z(j) where j=js, . . . , and je are the ROI coefficients in the subband[k], which are to be scaled up in step 107. When a priority assigned to the selected region of interest is a left bit shift value, S, quantization indices Z(js), . . . , and Z(je) are scaled up to be Z(js), . . . , and Z(je):

As a result of the scaling by left bit shift of S, a1) magnitude of the corresponding indices has become 2S times bigger. In other words, a2) bit significance level (s_level) of each bit field has become bigger by S (s_level=N-1.fwdarw.s_level=N+S-1, s_level=N-2.fwdarw.s_level=N+S-2, . . . , s_level=0.fwdarw.s_level=S). If each bit field is encoded in the order of decreasing order of bit significance level, each top S bit field of the scaled up indices are to be encoded earlier than any other bit fields in the same subband. In other words, larger number of bit fields in the scaled up indices are to be encoded at the earlier stages of the encoding process. a3) In a situation where bit plane coding is used, encoding is done on each bit plane consisting of the bit fields of the same bit significance level. In each subband, each bit plane is encoded preferably in the decreasing order of bit significance level or any other order. Encoding ordering of each bit plane across subbands can be arbitrarily specified by following the encoding ordering within each subband. The following is an example of encoding ordering of each bit plane in the same subband: No 0. plane {b.sub.N-1 (js), b.sub.N-1 (js+1), . . . ,b.sub.N-1 (je)}, No 1. plane {b.sub.N-2 (js), b.sub.N-2 (js+1), . . . ,b.sub.N-2 (je)}, No S-1. plane {b.sub.N-S (js), b.sub.N-S(js+ 1), . . . ,b.sub.N-1 (je)}, No S. plane {b.sub.N-1 (0), . . . ,b.sub.N-1 (js-1), b.sub.N-S-1 (js), . . . ,b.sub.N-S-1 (je), b.sub.N-1 (je+1), . . . ,b.sub.N-1 (J-10}, No S+1. plane {b.sub.N-2 (0), . . . ,b.sub.N-2 (js-1), b.sub.N-S-2 (js), . . . ,b.sub.N-2 (je), b.sub.N-2 (je+1), . . . ,b.sub.N-2 (J-1)}, No N-1. plane {b.sub.S (0), . . . ,b.sub.S (js-1), b.sub.0 (js), . . . ,b.sub.0(je),b.sub.S (je+1), . . . ,b.sub.S (J-1)}, No N. plane {b.sub.S (0), . . . ,b.sub.S-1 (js-1), b.sub.S-1 (je+1), . . . ,b.sub.S-1 (J-1)}, No N+S-1.plane {N.sub.0 (0), . . . ,b.sub.0 (js-1), b.sub.0 (je+1), . . . ,b.sub.0 (J-1)}.

The maximum left bit shift value, S.sub.max, is determined by the bit per coefficient assigned to the subband, by the maximum bit per coefficient among the ones assigned to all the subbands, by the maximum level of the significant bit in the subband, or by the maximum level of the significant bit in all the subbands. If a left bit shift value bigger than S.sub.max is specified, it can be adjusted to S.sub.max. In this case, the left bit shift value, S, is always in the following range: 0<=S<=S.sub.max (S.sub.max =N, 0: no priority to the region of interest). Even if S.sub.max is not upper-bounded, the invention works at a small increase of the encoded bit rate or a small increase of computational cost.

If the maximum left bit shift or the value larger than the maximum left bit shift is chosen, all the bit fields of the quantization indices corresponding to the region of interest are to have a different bit significance level from all the bit fields of the quantization indices corresponding to the regions outside of the region of interest in the same subband. Thus, all the bit fields for the region of interest and all the bit fields for the regions outside of the region of interest are to be encoded separately. In other words, the quantization indices for the region of interest and the quantization indices for the regions outside of the region of interest are to be separately encoded at the entropy coder.

If the left bit shift value is less than the maximum value and larger than 0, the top S bit fields of the quantization indices corresponding to the region of interest are to be encoded separately from any bit fields of the quantization indices for the regions outside of the region of interest in the same subband, the rest of the N-S bit fields of the quantization indices corresponding to the region of interest are to be encoded at the same encoding stage with the top N-S bit fields of the rest of the indices in the same subband, and the rest of the S bit fields in the indices which correspond to the regions outside of the region of interest are to be encoded separately from any bit fields for the region of interest. In other words, the quantization indices for the region of interest and the quantization indices for the regions outside of the region of interest are partially separated to be encoded at the entropy coder, when the left bit shift is less than the maximum value and larger than 0.

Preferable methods of ROI coefficient scaling are e1) scaling up the value of the quantization indices corresponding to the region of interest, e2) scaling up the bit significance levels of the bit fields associated with the region of interest e3) reassigning encoding ordering. e1), e2) and e3) are corresponding to the previously discussed a1), a2) and a3), respectively. Either the result of the ROI coefficient scaling up with e1), e2) or e3) at the step 107 is used together with the priority to the selected region of interest and identification result of the coefficients corresponding to the region of interest at the step 108 in order to manage the entropy coding to be performed at the step 108 entropy coding.

In FIGS. 4A and 4B, ROI coefficients where multiple regions of interest are to be emphasized with different priorities are illustrated. When each selected region is emphasized with the same level of emphasis, quantization indices corresponding to every region of interest are to be scaled up with the same left bit shift value. In this case, the same ROI coefficient scaling is performed on the quantization indices corresponding to any regions of interest by the same way as illustrated in FIGS. 3A-3F. When each selected region is emphasized with its own priority, scaling up illustrated in FIGS. 3A-3F needs to be performed for each region of interest. In this case, transform coefficient