JPH11225330A - Digital image compressing method - Google Patents

Abstract

PROBLEM TO BE SOLVED: To efficiently compress/expand a synthetic digital image while integrating lossless and loss compression by optimizing subband decomposition, continuous approximation, encoding and a bit stream operation. SOLUTION: A compressor 110 compresses an uncompressed image 105, produces a bit stream 115 in a scalable way and produces an expanded image 135 from the bit stream that applies a prescribed number scaling operation 120 by an expander 130. The bit stream operation selects the number of quantization layers which should be included in each subband. Continuous approximation and an encoding element produce plural layers of quantized subband symbols which are encoded by using context adaptive arithmetic coding, decide an encoding context based on an adjacent sample of a sample within the range of the same subband together with a quantizer that should be used for an optional specific subband sample and design in such a manner that information is concentrated on the neighborhood of an area where activity is high. The subband and the quantization layer are encoded at the same time.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention relates to digital image processing, and more particularly to compression and decompression of digital images.

[0002]

2. Description of the Related Art The current standard for compressing natural images is JPE.
G. In practice, this standard covers various related compression schemes in which only the so-called baseline scheme is commonly implemented. Baseline JPEG has not achieved state-of-the-art compression performance, but provides significant flexibility in the design of quantization and Huffman coding tables. This Huffman coding can be used to obtain a high bit rate compression efficiency and medium with relatively low cost in terms of computation and memory resources. fact,
Given that natural image compression efficiency is the only consideration, it is unlikely to use any more advanced compression scheme as an alternative to standard baseline JPEG. However, recently there has been a need for a single compression scheme that can provide applications that require a wider range of functions. Examples of such functions include:

1) The ability to efficiently compress natural and artificial images without resorting to completely different compression schemes in each case. Artificial image sources include graphics and text. These image sources have become particularly important with the widespread use of scanners. Scanners require compression so that scanned data can be stored and transmitted efficiently, but are sometimes used to indiscriminately scan everything from photographic images to monotonous documents. Ideally, a single compression scheme can work well for composite images consisting of both natural and artificial image source regions.

2) The ability to naturally construct image materials into multiple resolution hierarchies. In this case, easily identifiable components will exhibit relatively low resolution characteristics in the compressed bitstream, while other components will exhibit relatively high resolution characteristics. Such a property is referred to herein as resolution scalability. This capability is particularly important for applications that require distributing a single compressed image to a variety of different clients, each with different resolution constraints. This capability is of particular interest if the original image is so large that many clients cannot represent it and can simply retrieve it over the network.

3) Ability to naturally compose a compressed bit stream into a plurality of components corresponding to sequentially high reproducibility.
This capability is referred to herein as bit rate scalability. As in the case of resolution scalability, this ability is important for applications where a single compressed bitstream must be used to meet the needs of different users with different bandwidth constraints. This capability is especially useful for progressive transmission of compressed image data (i.e., progressive transmission) where image reproducibility is progressively improved as more and more compressed bit streams are received over a limited bandwidth network connection. Useful.

4) Integration of lossy and lossless compression. There are numerous applications that require true lossless compression for each reason. One of such applications
One is a medical image. In this case, the motivation for lossless compression, apart from its medical significance, is primarily statutory suggestions against data loss. Obviously, such an application would benefit from the presence of a single compression scheme or a single scalable bit rate stream that implements both lossy and lossless compression.

[0007]

It is important that features such as those described above be supported within a single, unified compression scheme suitable for embedded embodiments, including software and ASICs. Otherwise, such features are unlikely to be extensively or fully exploited so that they can have a significant impact.
As a result, issues such as computational complexity, memory usage and memory bandwidth requirements are of significant interest.

[0008] Thus, the limitations of synthetic images, resolution and bit rate scalability and the inability to integrate lossy and lossless compression impose limitations on digital image compression and decompression devices and the use of these devices in many applications. Hinder. Thus, there remains an unmet need for integrated digital image compression and decompression techniques that provide resolution and bit rate scalability, and that can efficiently compress / decompress composite digital images while integrating lossless and lossy compression. Exists.

[0009]

SUMMARY OF THE INVENTION In order to solve the above problems, a method for providing resolution and bit rate scalability and efficiently compressing / expanding a composite digital image while integrating lossless and lossy compression. And an apparatus are provided. The compression method is subband decomposition,
Includes three main components: continuous approximation and coding, and bitstream manipulation. Bitstream operations involve selecting the number of quantization layers to be included for each subband to achieve a particular bit rate or quality goal. All three elements can operate simultaneously to minimize intermediate storage buffer requirements.

The continuous approximation as well as the coding element is C
The core of the ASAC processing procedure (CASAC is Context A
Shorthand for daptive Successive Approximation and Coding, meaning context-adaptive continuous approximation and coding). This includes a built-in dead zone quantizer set. Generate the layer (s) of quantized subband symbols to be encoded using context-adaptive arithmetic coding. With the quantizer to be used for any particular subband sample, the encoding context is determined based on the samples that are spatially immediately adjacent to that sample within the same subband. Adaptive schemes are simple and are designed to focus information near high activity areas. Arithmetic coding has a significant impact on the computational complexity otherwise, so use a variation of run-length coding to reduce the total number of symbols that need to be coded without sacrificing compression performance Can be done.

Although deemed particularly important for high performance ASIC implementations, to minimize buffer requirements and maximize opportunities for parallelism, all subbands and all quantization layers are simultaneously encoded. The algorithm is designed to be able to be encrypted or decoded.

All subband samples are quantized using a built-in scalar dead zone quantizer, where the dead zone is twice the quantization step size and zero. Concentrate around. The specimen is
A continuous approximation is made by adapting successively finer quantizers, where the step size is divided by two each time. Although the quantizer is scalar, it is possible to adapt the quantization strategy. This is because the choice of a particular quantizer within the embedded (or stratified) hierarchy depends on the neighboring samples (or context) in space of the sample being quantized.

The compression and decompression processes are fundamental because the subband integration and analysis are comparable in complexity and the context formation for the adaptive arithmetic encoder is the same for the encoder and the decoder. Is symmetrically.

The process is both hierarchical in terms of resolution and progressive with respect to reproducibility. Select desired resolution
The compressed bitstream is compressed and decompressed at any point in It can be filtered (this is a simple action of discarding certain elements according to, for example, an identifier embedded in the bitstream).

[0015]

DETAILED DESCRIPTION OF THE INVENTION 1. Architecture Overview FIG. 1 shows a conceptual system architecture. Conceptually, the image is progressively reduced to smaller components that carry different aspects of the image content,
Ultimately, all such components are encoded and packaged into a single compressed bitstream. FIG. 1 is a diagram showing CASAC (ie, context-adaptive continuous approximation and encoding).
1 is a block diagram illustrating an embodiment of an integrated scalable image compression / decompression system 100 based on (simplified notation of ation and Coding). In summary, the initially uncompressed image 105
Is compressed by a compressor 110 to generate a scalable compressed bitstream 115, which is then subjected to a required number of scaling operations 120. The decompressor 130 is then applied to the scaled bit stream to create a decompressed image 135.

A color image is usually composed of luminance and chromaticity components.
(C ₁ , C ₂ ,..., C _K ). In general, the color component is susceptible to several of a number, the present invention is C _k compared to C _{k + 1}
Is considered to be a more important color component.

Next, using the multi-resolution conversion, each color component is independently decomposed into resolution levels l = O, 1, 2,..., L. Where l = 0 represents the lowest resolution representation of the color component, while each of the subsequent levels l
Represents the additional detail needed to recover an image with twice the resolution that would be available based on -1. The parameter L is called the number of levels in the multi-resolution conversion. L = 0 corresponds to the case where the original image itself has the lowest available resolution.

In one embodiment of the present invention, the implementation is limited to only two types of multi-resolution transforms, allowing the compression system to switch between these different transforms in different regions of the image. The two types of transformation are as follows. (1) Overcomplete conversion. By interpolating the lower resolution image and then building up the difference between the interpolated image and the actual higher resolution image, the higher resolution image associated with level l becomes the lower resolution image (level 1-1). Obtained from in this case,
At each resolution level l there is a single band C _{k, l, 0} whose sample represents the difference image. This single band contains exactly the same number of specimens as the higher resolution image. (2) Non-overcomplete conversion. This will probably be limited to the standard linear subband / wavelet transform. In this case, there are three bands, C _{k, l, 1} , C _{k, l, 2} , and C _{k, l, 3} . They are usually LH bands (ie, vertically low-pass, horizontally high-pass bands), HL bands (ie, vertically high-pass, horizontally low-pass bands), and HH bands (ie, vertically high-pass, horizontally high-pass bands). Is interpreted as Each of these three bands contains the same number of samples as the lower resolution image, ie, one third of the number of samples in the high resolution image.
The lowest frequency image itself has levels l = 0 and b = 0
That is _{, it} is represented as a single base band having a band index of C _{k, 0,0} .

Next, the individual samples used to represent each band C _{k, l, b} are independently quantized using a set of built-in scalar quantizers, resulting in a quantum Q _{k, l, b, 1} , C _{k, l, b, 2} , ..., C _{k, l, b, Q} are generated for the Q symbols of the coded symbol. A continuous layer is interpreted as a component with high reproduction fidelity in a continuous approximation of the band.
Specifically, the quantization symbol C _{k, l, b, 1} carries the coarsest representation, after which each successive resolution C _{k, l, b, q} quantizes the sample values of the band Provides the additional information needed to represent with twice the precision represented by the layers. Details of the built-in quantizer will be described later.

The next conceptual step in the overall system architecture is to encode each quantization layer C _{k, l, b, q} into a string of bits and utilize the redundant information as efficiently as possible. is there. This document describes such a bit
String

[0021]

(Equation 1) And the length rounded to the nearest number of bytes

[0022]

(Equation 2) It expresses. Details of the encoding process will be described later.

Finally, the bit strings associated with each quantization layer of each band are aggregated into a single bit stream containing the appropriate symbols and header information, and the reproduction fidelity, resolution and number of the color components are Allows the bitstream to be reduced to the most appropriate subset for applications that decompress later. A bitstream that supports such an operation after compression is called a scalable bitstream. When packaging a bitstream, some scaling may be applied immediately to limit the overall size of the initial bitstream, usually to meet some target bit rate.

It should be noted that an actual compression system should not implement a linear sequence operation as shown in FIG. In particular, buffering the entire image representation at each intermediate stage of the conceptual architecture is impractical and unnecessary. This specification assumes that each color component comes from the image source one scan line at a time, starting at the top of the image and working towards the bottom. A memory efficient embodiment should generate scan lines for each band sequentially while generating all bands essentially simultaneously. Similarly, the quantization and encoding of each band must be a sequential process while simultaneously generating all quantization layers. To enable such a memory-efficient implementation, the quantization and coding scheme for a particular quantization layer may require information from another band or another quantum of the same band that appeared much earlier in the image. May not be based on information from the chemical layer. For this reason, in fact, the particular coding scheme described below treats every band of every color component completely independently. Further, the quantized symbols from layer q of any particular band can be encoded without reference to information from layer q-1 that has gone down one or more scan lines of that band.

2. Multi-Resolution Conversion FIG. 2 is a block diagram showing basic features of the multi-resolution image conversion subsystem when there are two conversion levels. Each level in the multi-resolution hierarchy uses an overcomplete transform or a non-overcomplete transform, or a mixture thereof. Mixed transformations are expected to be particularly useful in compressing composite documents. If only the overcomplete transform is used at some level, the compressed bitstream contains only a single band C _{k, l, 0} . Assuming that only non-overcomplete transforms are used, the compressed bitstream contains three bands.
C _{k, l, 1} , C _{k, l, 2} , C _{k, l, 3} are included. If a mixed transform is used, all four bands are included.

2.1. Band Resolution As described above, each level in the multi-resolution conversion produces a new image at half the resolution of the previous level. Here, before proceeding to the description of image generation, in order to answer the question of whether a case where the resolution cannot be divided by 2 or a case where color components have different resolutions may occur,
First, the relationship between various color component resolutions and conversion bands will be described. Let H (C _{k, l, b} ) represent the height of band C _{k, l, b} (that is, the total number of sample scanning rows). Similarly, let W (C _{k, l, b} ) represent the width of this band (ie, the number of samples per scan line). Also, H (C _{k, l} ) and W (C _{k, l} ) are changed to level l = 0,
Represent the height and width of the color components that can be reconstructed from 1, ..., l, let H (C _k ) and W (C _k ) represent the height and width of the color component k . Finally, let L _k denote the number of levels in the multi-resolution hierarchy associated with the kth color component. Therefore, H (C _k , L _k ) = H (C _k ) and W
(C _k , L _k ) = W (C _k ). The various resolutions available within a multi-resolution hierarchy for a given color component k are related by the following equations:

[0027]

(Equation 3)

[0028]

(Equation 4) In the above formula,

[0029]

(Equation 5)

Represents rounding to the nearest integer.
In one embodiment, the basis bands C _{k, 0,0} have the same resolution for all color components k, with the first color component having the highest resolution. This is because the lower resolution color component C _k

[0031]

(Equation 6) and

[0032]

(Equation 7) It means that a plurality of color components may have different resolutions only when.

In the case of an overcomplete transform, a single difference band C _{k, 1,0} has the same resolution as the resolution level used to reconstruct. That is, H (C _{k, l, 0} ) = H
(C _{k, l} ) and W (C _{k, l, 0} ) = W (C _{k, l} ). On the other hand, the non-overcomplete transform produces three detail bands, each with about one quarter the resolution of many samples. Specifically, the following three bands are obtained.

[0034]

(Equation 8)

It is easy to observe that the total number of specimens in these three bands always equals the difference between the number of specimens at the lower and higher resolution levels C _{k, l} and C _{k, l-1} . Is done.

2.2. Overcomplete Conversion In the unified image compression system described herein, the overcomplete conversion option is intended to compress image data with low amplitude levels. That is, the frequency graph of color component values must be composed of a small number of independent cuts. A special case of this is a double or near double layer of data obtained by scanning text and line art. For these types of sources, it is desirable to apply a multi-resolution transform to preserve the original number of amplitudes rather than scatter the amplitude levels continuously as in the case of a linear transform. More generally, the emphasis is on transforms that maintain a level set of pixels to be transformed. Such a transformation is known as a morphological transformation because the morphological operator is an operator that holds a level set.
To address these needs, the present invention proposes a very specific overcomplete morphological transformation, while considering the use of alternative related transformations.

Let C _{k, l} [m, n] denote the level and the sample values on row m and column n of the color component k, as shown at level 1 in FIG. C _{k, l-1} [m, n] = M (C _{k, l} [2m, 2n], C _{k, l}
[2m, 2n-1], C _{k, l} [2m, 2n + 1], C _{k, l} [2m-1,2n], C _{k, l} [2m + 1,2
n]), the next lower resolution level is formed. In the above equation, M (a, b, c, d, e) is the five arguments a,
Indicates the median of b, c, d, e.

As described above, the low-resolution image is extracted by the nonlinear median filtering operation. This method is more appropriate for text and graphics than linear filtering.

The samples of the difference band C _{k, l, 0} are C _{k, l} and C _{k, l−1}
From the morphologically interpolated version of the difference. In particular,

[0040]

(Equation 9) It is. In the above equation, P _{k, l-1} [m, n] {-1,1} is to be interpreted as a code prediction word,

[0041]

(Equation 10) Is obtained by the following morphological interpolation operation of Expression 11.

[0042]

[Equation 11]

Here, the morphological operator A (a, b, ...) (α,
..) returns the value of the argument in the first list a, b,... n closest to the average of the arguments in the second list α, β,. These sub-sampling and interpolation operations are illustrated in FIG.

The code predictor P _{k, l-1} [m, n] plays an important role in exploiting the important form of redundancy that exists in image samples with a small number of level sets. Specifically, the interpolation error

[0045]

(Equation 12) Whenever is large, the sign of this error is

[0046]

(Equation 13) Is likely to match the sign of However

[0047]

[Equation 14]

Is a measure of the local centroid of the available level set. This is the easiest way to understand if the image data is essentially two levels (the fluctuations around the level set may be small, but the frequency graph has two distinct cuts). In this case, the sign of the large interpolation error will carry the higher level set to the lower level set and the higher level error
It is completely predictable in that it carries a lower level set to the set. In this case, the above direction is always
Same as the direction of the center of gravity of the two level sets. For these reasons, the following predictive word (Equation 15) represents a rational embodiment of the idea of the present invention. However, it is also possible to adapt alternative predictors.

[0049]

(Equation 15) However,

[0050]

(Equation 16) Represents a run-time estimate of a set of locally adjacent minimum levels, while

[0051]

[Equation 17]

Represents the run-time estimate of the locally adjacent maximum level set. There are a number of efficient techniques for forming such estimates while minimizing memory and computational requirements. To give a simple example, the minimum value from the sample at the same position in several adjacent scan lines, that is,

[0053]

(Equation 18) And use this value to

[0054]

[Equation 19] , The following recursive update procedure can be derived.

[0055]

(Equation 20) Where α (0,1) is an exponential decay coefficient that controls the rate at which predicted words can adapt to changes in the level set.

It should be noted that the morphological transformation described above is essentially compatible with both lossy and lossless image compression. Furthermore, this transform is particularly suitable for compressing images having only one bit per sample. This is because, in this case, the code prediction word guarantees that no bits are consumed in the code bit coding step described in section 5.3 below. In this way, independent of the properties of the image material, exactly the same quantization and coding techniques as described in sections 4 and 5 below can be used.

2.3. Non-over-Complete Transformation As mentioned above, the non-over-complete transform is simply
Perfect reconstruction (P for short)
R) or near-perfect reconstruction (NPR) linear subband transformation. In the embodiment of the present invention, a 9-tap NPR filter method by Adelson et al. Was used (see: Proc. SPIE (Cambridge, MA), Oc.
"Orthogonal pyramid transform" by EHAdelson, E. Simoncelli and R. Hingorami3, t. 1987, pp. 50-58.
s for image coding "), there is no reason why different filter sets or fully programmable filter coefficients are not supported. Using standard symmetric extension techniques, extra samples may be used to preserve the full reconstruction properties. It can be ensured that there is no need to pack into subbands.

An important problem with the transform filter coefficients is that
How they are normalized. This is because normalization affects the interpretation of the quantization applied to the samples in each band. In view of this, it is assumed below that all filters are normalized to ensure that the low-pass sub-band filter has unity DC gain, that is, its coefficients sum to one.
This means that the nominal range R for image sample values (eg, R = 255 for 8-bit data) is also the nominal range for sample values at all resolution levels. Such a normalization technique guarantees compatibility between the linear subband transform and the morphological transform described in section 2.2 above.

It should be noted that NPR filters and most PR subband filters are not suitable for lossless image compression. However, subband transforms that are compatible with both lossy and lossless compression are known. These are known as exact reconstruction systems. There is no reason such a transformation cannot be used within the exact same framework.

2.4. Memory and Bandwidth Requirements This section discusses the overall system memory requirements and the significance of multi-resolution conversion for memory bandwidth usage. In this analysis, only the linear subband transform is considered. This is because the kernel of the overcomplete morphological transformation supports very small areas, thus reducing memory requirements.

During compression, the method of image data arrival is such that one sample arrives at a time, one scan line at a time, in dictionary order, starting from the upper left corner of the image. This means that T represents the maximum number of taps in either the vertical low-pass or high-pass filter to generate scan rows for each of the three highest frequency subbands and the half resolution image (e.g.,
For the filter in section 2.3, T = 9), T-1 of each color component
This means that the scan line must be buffered. As each sample arrives, the previous T-1 samples are read from memory, filtered, and one sample written to the relevant subband. Thus, the first level of the bi-resolution conversion requires T sample transactions per original image sample. Subsequent levels l <L _k in the multi-resolution hierarchy for color component k-1 are the resolution levels C
_{At k, l} , T-1 scan rows are buffered, requiring that T sample transactions be performed for each sample at C _{k, l} . However, C _{k, l} is
It only has a quarter sample in number and half scan lines in length for _{k, l + 1} . Therefore, the memory requirement for compression is limited to 2 (T-
1) Will be image scan lines and (4/3) T specimen transactions.

However, many images are 8 per sample
It should be noted that the present embodiment desires to use up to 16 bits per sample for subband samples, while being represented in bits only. In that case, the buffer memory requirements are:

[0063]

(Equation 21) Would be represented as However, the memory bandwidth is

[0064]

(Equation 22) It is.

With respect to decompression, the analysis is somewhat less intuitive, but the situation is very similar. If you omit the details and show only the results, during compression

[0066]

(Equation 23)

Requires an intermediate storage sample and a (4/3) T sample transaction. However, all buffered samples are sub-band samples rather than image samples in this case. Assuming again that the image samples are only 8 bits deep but all subband samples are 16 bits deep, the buffer needed for decompression is
The memory requirements are

[0068]

(Equation 24) And the memory bandwidth is -1+ (8 /
3) T bytes.

3. Configuration of Compressed Bitstream Although the final compressed bitstream is configured after quantization and encoding, the details of the configuration are first described to clarify the operation of the overall compression system. FIG. 4 shows an example of the structure of the configuration information within the bitstream itself according to one particular embodiment of the invention. As shown in FIG. 4, the bitstream is divided into four main partitions.

3.1. First Header Section The first section consists of the following simple elements: 1.5-byte magic string "CASAC". 2. One null terminator byte equal to zero. This may be modified in the future to support the inclusion of additional information in the header. 3. A 16-bit unsigned integer representing the base bandwidth W (C _{k, 0,0} ) = W (C _{k, 0} ). This is the same for all color components k, as described in section 2.1. 4. A 16-bit unsigned integer representing the base band height H (C _{k, 0,0} ) = H (C _{k, 0} ). This is the same for all color components k. 5. Represents the size of the quantization step associated with the first (coarse) quantization layer of the basis band C _{k, 0} , where each color component k
16-bit unsigned integer for. The specific interpretation of this step size is described in section 4 below.

3.2. Band Header The second section of the bitstream identifies all the decomposition bands represented within the bitstream and the number of coded quantization layers available for each band. Contains additional header information describing the size. For the particular embodiment described herein, the header information for each band is written in a particular order according to the following rules. All bands for level l appear before any bands for level l + 1 as l = 0,1,2 .. According to the above conditions, all bands for color component k appear before all bands for color component k + 1 as k = 1,2,. According to the above conditions, band b always appears before band b + 1, as b = 0, 1, 2,. These rules not only give more important information priority to less important information, but also to uniquely identify the band, the information of the information that must be carried by a one-byte identifier where the header of each band begins. Reduce the amount.

The header for a particular band C _{k, l, b} consists of the following entries: 1. 1-byte identifier: the least significant 2 bits represent band index b, the next 4 bits represent up to 16 different color components k, and the next 1 bit has width W (C _{k, l, b} ). If the number is odd, 1 is held. If the height H (C _{k, l, b} ) is odd, the 1 most significant bit holds 1. It will be readily appreciated that this information is sufficient to reconstruct the multi-resolution hierarchy with the resolution and resolution level of all bands. 2. One byte that identifies the quantization layer available for the band. The lower 4 bits of this byte identify the number of the first quantization layer to be skipped, while the upper 4 bits identify the index of the finest quantization layer for which information is available. In this way, at most 15 quantization layers can be coded for all subbands. The reason for skipping the first quantization layer is that the quantization step size associated with the coarsest quantization layer (q = 1) is the base quantization step size Δ _{k, 0} recorded in the first part of the header. _{, 1} (this point is described in detail in section 4 below). However, such a coarse quantization step size band may not contain useful information. 3. One or more bytes for each of the available quantization layers q,

[0073]

(Equation 25)

Indicates the total number of bytes used to encode the The lower 7 bits of this first byte hold the lower 25 bits of Equation 25 above, and the most significant 1 bit is set to 1 if additional bytes are needed. If the most significant bit is set to 1, the next byte is
Represents the next 7 bits of 5, and a plurality of bytes are used in the same manner as necessary.

3.3. Level Specific Information The third section of the bitstream identifies the particular transform used at each level of the multi-resolution hierarchy. For each color component, information identifying the transform used to reduce C _{k, 1} to the relevant base band first appears, followed by information to reduce C _{k, 2,} and so on. Followed by The conversion information is common for all color components at the same level, but can vary from level to level. The information embedded in this part of the bitstream can be modified in other embodiments, but in this embodiment, the transformation is performed on the image so that it can only be changed in the vertical direction. It is kept aligned over the entire width.

The header information for each level consists of a sequence of one or more bytes identifying the particular transform and the number of successive scan lines for which the transform is to be used.
Least significant bit of each byte is overcomplete conversion
Identifies either a (zero bit) or a non-overcomplete conversion (one bit).

The remaining 7 bits are for bands C _{k, l, 0 for} overcomplete conversion or for bands C _{k, l, 1} , C _{k, l, 2} and C _{k, l, 1 for} non-overcomplete conversion.
Identify the number of consecutive scan rows of the resolution component C _{k, 1} to which this transform is applied to generate a sample for C _{k, l , 3} .
Subsequent bytes appear with the same interpretation until all H (C _{k, l} ) scan lines of the relevant resolution component have been processed. When the transformation switches between one vertical segment of the image and another, it considers them sub-images and applies the appropriate transformation independently within the relevant segment. To avoid creating noticeable defects in the reconstructed image, it is recommended that such switching be limited, if possible, to smooth, blank areas, for example, between text portions and natural images.

[0078] The header information is level l = 1, 2, ... but appear in the order with respect to L _1, b = 0 or b ≠ any band header partition band identifier of that level in the case of the 0 , Any particular level l is skipped. Otherwise, the particular transformation is fixed and b =
Omission of either 0 or b ≠ 0 implies a particular transformation.

3.4. Quantized Layer to be Encoded The last section of the bitstream contains all the bit strings representing the quantized layer encoded from each of the bands.
Each bit string is padded with an integer indicating the number of bytes already recorded in the individual band header, as described above, so that decompression and bitstream filtering applications can easily associate the relevant code bytes. An index to find is provided. In this embodiment, the code bytes for all bands in the quantization layer q = 1 first appear, followed by subsequent q = 2,3,.
The sign byte for appears. Furthermore, according to such an order, the code bytes for all bands containing information in the appropriate quantization layer q are stored in the second bitstream.
Appear in exactly the same order as the headers for the bands that appeared in the section. Such a simple ordering scheme suggests that the bitstream can be used as is in progressive transmission applications, since the code bytes appear from the most important one. This also allows an effective error prevention scheme to be implemented without having to analyze the bitstream precisely. This is because, when distributing the compressed image via a noisy path, the first part of the bitstream must obviously be protected more strongly than the rear part.

3.5. Bitstream Scaling Given a bitstream having the above representation, discarding components that are not important for a particular decompression application is not a major problem. For example, if black and white information is required, all information relating to color component k> 1 may simply be discarded. If there is a resolution limit, all band headers and associated code bytes beyond the appropriate resolution level l need only be discarded. The most important scaling task to consider is when restrictions are imposed on the total size of the bitstream to be passed to the decompression application. This is called bit rate scaling.
In this case, the number of bytes available for the sign byte, ie

[0081]

(Equation 26) And layer size information ie

[0082]

[Equation 27]

To reach the limit B _max for, the number of bytes associated with all the required header information is first reduced.
_Let B _{k, l, b, q} denote the sum of C _{k, l, b, q} and the number of header bytes needed to represent this size. Thus, B _{k, l, b, q} is the number of bytes needed to contain C _{k, l, b, q} in the filtered bitstream. Using such notation, the following bit rate scaling algorithm is recommended. Step 1: Find the maximum quantization layer index q ₀ as shown in the following Expression 28.

[0084]

[Equation 28]

[0085] and B = B _max -B _min. This is the number of available bytes that will be unused if all quantization layers beyond q ₀ are discarded. Step 2: with q = q _0. Step 3: Verify all bands C _{k, l, b} in exactly the same order as they appear in the bitstream. For each such band, let q _{k, l, b} denote the index of the finest quantization layer for which information is available. Case 1: If q _{k, l, b} <q, there is nothing to do. Case 2: If q _{k, l, b} > q but B _{k, l, b, q} > B, discard all quantization layers beyond layer q for this band. That is, q _{k, l, b} = q. Case 3: If q _{k, l, b} > q and B _{k, l, b, q} ≦ B, subtract B _{k, l, b, q} from B. Step 4: If q = 15, the process is completed. Otherwise, set q = q + 1 and return to step 2. It should be noted that this algorithm essentially assigns approximately equal numbers of quantization layers to all bands. The quantization strategy described in Section 4.2 is to set the base quantization step size to different bands so that the strategy of assigning an equal number of quantization layers to all bands is a good bit rate assignment strategy. Trying to assign to.

3.6. Buffer Storage of the Bitstream In this specification, the bitstream must generally be much smaller than the original image, so the memory usage and memory bandwidth requirements of the compressed bitstream itself are very small. Interest is not paid. When implementing the present system on a general-purpose CPU, the compressed bit string, ie, while the image is compressed,

[0087]

(Equation 29)

It is usually quite satisfactory to simply buffer the memory in memory and construct and write out the final bitstream only once after the image has been fully compressed. However,
At high bit rates or when processing very large images, this may not be satisfactory. A similar problem can occur in custom ASIC embodiments. If this is a problem, the following may prove useful in solving the problem.

First, it should be noted that there is no efficient means to generate the final bitstream until after the entire image has been compressed. Because, any memory efficient embodiment of the compression system needs to generate all quantization layers of all bands substantially in parallel, while the bit stream has one associated bit stream. And requires that header information be generated to reflect the number of code bytes used to compress each quantization layer.

The bitstream may also need to be filtered using the algorithm described in section 3.5 to meet certain size restrictions. Therefore, the bitstream must be initially buffered in a memory with some random access capability. Fortunately, however, the memory mechanism need not be particularly fast and need not have byte-by-byte addressing capabilities. One suitable approach is to create a linked list of storage blocks, each of 64 bytes, for example, and maintain one list for each quantization layer in each band. 8 quantization layers, 3 color components, and 7
Assuming a complete 4 bands for each of the resolution levels, the compressor would have 672 such blocks or 4
Only 3 Kbytes need to be accessed, and the blocks can be written to a relatively large storage in any order, as needed during image compression. Of course, once the image has been compressed, the blocks need to be fetched from its large memory facility and rearranged into a new bitstream. Of course, buffering of such intermediate storage blocks, rather than the actual bitstream, involves some overhead, and the storage mechanism is large enough to hold more data than is required for the final compressed bitstream. Must.

4. Built-in quantization As mentioned in the above section 1, each band C _{k, l, b} is a quantization layer C
_{k, l, b, 1} , C _{k, l, b, 2} , ... C _{k, l, b, q}
A continuously high fidelity representation of the band samples is provided. All bands except the base band C _{k, 0,0 of} each color component k are quantized using a built-in dead zone quantizer. Because all of these bands, the value zero represents high frequency information of special importance. Therefore, it is important that the center quantization interval (ie, the dead zone) be around zero. The base band, on the other hand, represents infrequent information where the value zero has no special meaning. These bands are uniformly quantized as described in Section 4.2.

4.1. Embedded Dead Zone Quantizer FIG. 5 shows the relationship between multiple embedded dead zone quantizers used to generate the quantization layer for bands other than the base band C _{k, 0,0.} Show. The whole set of quantizers is
It is characterized by a single parameter Δk _{, l, b} that identifies the coarsest quantization step size. Note that, taking advantage of the fact that the high frequency information represented by these bands tends to swarm around zero,
The dead zone around zero has a width of 2Δk _{, l, b} . As a practical matter, these built-in quantizers are implemented very efficiently by first converting the relevant sample values to a signed magnitude representation and then discarding the appropriate number of lower bits. Let S _{k, l, b} [m, n] be the scan row m and column of band C _{k, l, b}
Sign bit for sample C _{k, l, b} [m, n] on n (1 is negative, 0 is positive)
And M _{k, l, b} [m, n] indicates the magnitude of scaling (integer). That is,

[0093]

[Equation 30]

Is as follows. Where R is the nominal range of the original image sample values (R = 255 for an 8-bit image sample),
Q _{k, l, b} is the index of the finest quantization layer that is of interest in the present embodiment when generating the band C _{k, l, b} . Next, the quantization symbol for the quantization layer q <q _{k, l, b} becomes the code bit S _{k, l, b} [m, m for the non-zero value of M _{k, l, b, q} [m, n]. n] together with the shifted magnitude as in the following equation 31.

[0095]

(Equation 31)

[0096] In this _{manner, M k, l, b [} m, n] for _{acquiring, M k, l, b [} m, n] from _{Q k, l, b -q +} 1-σ k, _{l, b, q} [m, n] lower bits may be discarded. Here, σ _{k, l, b, q} [m, n] is a quantization application parameter, and its value is zero or one.
When σ _{k, l, b, q} [m, n] = 0, it is easy for the efficient quantization step size to be (R / 2 ¹⁵ ) (Δ _{k, l, b} / 2 ^q-1 ) I understand.
This increases the scaling sample values up to a nominal range is equal to 2 ^15, then delta _{k, l} as a step size for the first quantization _layer, the _b, step size for the second quantized layer as delta _{k, l,} the _b / 2, be construed as using the same values for the following layers. σ _{k, l, b, q} [m, n]
When = 1, the effective quantization step size is half, ie
(R / 2 ¹⁵ ) (Δ _{k, l, b} / 2 ^q ).

Next, the quantization application parameter σ _{k, l, b, q} [m,
n]. To understand how this parameter is formed, each quantization layer is generated in dictionary order, i.e., every scan row, decoded after being encoded, and when quantization q is available. It is important to understand that the quantization layer q-1 is always available. Further, the decoding process for the quantization layer q-1
It is always one scan line ahead of the decoding process for the quantization layer q, which is M _{k, l, b, q-1} [m, n + 1], M _{k, l, b, q-1} [m +
1, n-1], M _{k, l, b, q-1} [m + 1, n] and M _{k, 1, b, q-1} [m + 1, n + 1]
Is known by the time M _{k, l, b, q} [mn] is decoded. Of course, M _{k, l, b, q} [m, n], M _{k, l, b, q} [m
-1, n-1], M _{k, 1, b, q} [m-1, n] and M _{k, l, b, q} [m-1, n] are also known, and these eight quantized All of the adjacent sample sizes used are used to condition the quantization and coding of M _{k, l, b, q} [m, n]. This neighbor information is shown in FIG. Here, σ ′ _{k, l, b, q} [m, n] is assumed to be equal to zero if the size of these eight adjacent samples is equal to zero. Thus, if the four closest samples of the sample were found to be non-zero in layer q in the affected past, or if the remaining closest samples were found to be non-zero in layer q-1, σ ′ _{k, l, b, q} [m, n] = 1. Next, σ _{k, l, b, q} [m, n] is defined from the viewpoint of the proximity parameter σ ′ _{k, l, b, q} [m, n]. To be specific,

[0098]

(Equation 32)

Is as follows. The above definitions are easier to understand and implement from a procedural perspective than a functional one. Specifically, the following steps are performed when evaluating M _{k, l, b, q} [m, n]. 1. σ ' _{k, l, b, q} [m, n] depending on already encoded information
Check the value of. If σ ' _{k, l, b, q} [m, n] is 1, that is, if the adjacent value is non-zero, fine quantization related to σ _{k, l, b, q} [m, n] = 1 Calculate M _{k, l, b, q} [m, n] immediately based on the threshold. 2. If the magnitude has already been found to be non-zero in the previous quantization layer, that is, if M _{k, l, b, q-1} [m, n] ≠ 0, then σ
_{k, l, b, q} [m, n] must be equal to 1. In fact, σ
_{k, l, b, q} [m, n] is observed to be a non-decreasing function of q. 3. If σ ' _{k, l, b, q} [m, n] = 0 and M _{k, l, b, q-1} [m, n] = 0, 3 × 3 window around the current sample Turns out to have no non-zero magnitude in the range. In this case, σ
M based on the assumption that _{k, l, b, q} [m, n] is equal to zero
First _{, k, l, b, q} [m, n] are calculated. If this yields a quantized magnitude of zero, the assumption is correct. Otherwise, M _{k, l, b} [m, n]> 2X (where X = Q _{k, l, b} -q + 1), which is σ _{k, l, b, q [m, n ] = 1,} which means that M _{k, l, b, q} [m, n] must be recalculated based on this new information.

In a software implementation, these procedural steps can be performed using a simple set of mask, test, and shift operations, which are performed to implement the encoding scheme described in Section 5. Is the same as the operation required for

The above definition of σ _{k, l, b, q} [m, n] indicates that a specific sample has a coarse step size (R / 2 ¹⁵ ) (Δ _{k, l, b} / 2 ^q-1 ). As soon as it turns out to have a size that exceeds
Switching to the use of a finer quantizer with size (R / 2 ¹⁵ ) (Δ _{k, l, b} / 2 ^q ) implies quantizing and encoding the sample and all of its neighbors. As a result, the common sample encountered in non-adaptive quantization schemes, where the separated sample values exceed the threshold value while quantizing all adjacent samples to zero, creating particularly unpleasant defects The problem is avoided. This scheme also tends to naturally reduce the quantization step size near high contrast edges, thereby reducing "ring" defects in the reconstructed image.

4.2. Embedded Uniform Quantizer The K basis bands C _{k, 0,0} are all quantized using a simple set of embedded uniform quantizers, as shown in FIG. In one embodiment, these built-in uniform quantizers are implemented in exactly the same way as the built-in dead zone quantizer described in Section 4.1, but instead of using a signed magnitude representation of the sample values, Differs in that the quantization is started using the two's complement representation. Specifically, V _{k, 0,0} [m, n] is

[0103]

[Equation 33]

(2) where Q _{k, 0,0} is again the finest quantization that is of interest to generate with respect to the base band of color component k. The quantization symbol for layer q ≦ Q _{k, 0,0} is

[0105]

(Equation 34)

Signed two's complement integer defined by
There is a one-to-one correspondence with V _{k, 0,0} [m, n]. That is, V
_The lower Q _{k, 0,0} -q + 1 bits from _{k, 0,0} [m, n] are simply discarded. The effective quantization step size for layer q is (R / 2
¹⁵ ) (Δ _{k, 0,0} / 2 ^q-1 ). This raised the scaling sample values to their range is equal to 2 ^15, then Δ relative to the first quantization layer
_{k, 0,0} is interpreted as using 1 / 2Δk _{, 0,0} for the second quantization, using a similar size for subsequent layers. Unlike all other bands, no quantization adaptation policy is used for the base band. That is, the quantization step size is independent of the spatial context of the sample being quantized.

4.3. Relationship Between Different Bands So far, the quantization strategy has been dependent on the base quantization step size Δ _{k, l, b} associated with each band. It is a natural and important question how these quantization step sizes are related. In view of the fact that the bitstream syntax described in Section 3.1 gives a specification of only one basis for each color component,
The above question is particularly important. In one embodiment,
The answer to this question is very simple,

[0108]

(Equation 35)

Is defined as That is, the quantization step size associated with the corresponding quantization layer is the same for all bands in the multi-resolution hierarchy, and is doubled each time the hierarchy is moved to the next higher resolution level. For at least the linear subband / wavelet transform, this strategy is almost optimal in terms of minimizing the mean square error of the reconstructed image, assuming that all bands are always assigned the same number of quantization layers. Is assumed to be In fact, the scaling algorithm described in section 3.5 usually gives more weight to lower frequency bands. This is because those low frequency bands have high priority as candidates for the remaining bytes once all bands are initially assigned the same number of quantization layers. This is also very reasonable considering the fact that the human visual system is generally relatively sensitive to lower spatial frequencies. In fact, informal subjective experiments suggest that the above relationship of quantization step sizes for different bands is nearly optimal.

5. Quantization Layer Coding The technique used to encode the quantization layers C _{k, l, b, q} associated with each band C _{k, l, b, q} is described below. . For this embodiment, the encoding algorithm is designed to keep memory and computational resources at a minimum without sacrificing compression performance. The following key points have been determined primarily to keep the intermediate buffer memory within acceptable limits. -Encode each band separately. _Inclusion of information from the same band at the previous resolution in the conditioning context used to encode C _{k, l, b, q} [m, n] offers some advantages, but improves compression efficiency Is hardly more than about 5%. It is difficult to justify this improvement in terms of increased intermediate storage capacity due to the fact that there is a natural delay of several scan lines between successive levels in the multi-resolution hierarchy.
Also, independently encoding every band simplifies the implementation of compression schemes in hardware and reduces the memory bandwidth and on-chip memory demands associated with such implementations. Further, such encoding avoids imposing constraints on the bitstream scaling algorithm described in Section 3.5. For any particular band, appear above the coarser quantization layer q-1 or in the current quantization layer q when generating a conditioning context to encode quantization symbols from layer q of scan row m. The encoding method of the present embodiment does not depend on information appearing before the scanning line m-1. This means that Q
_{If k, l, b} + 1 is the index of the finest quantization layer to be generated during compression (or reconstructed during expansion), then at most Q _k from band C _{k, l, b , l, b} +1 scan lines must be placed in intermediate storage. To illustrate this point, FIG. 8 shows the relationship between a buffered scan row and a quantization layer encoded or decoded from the buffered data.

Before describing the details of the coding, it should be noted that the baseband quantization layer C _{k, 0,0, q} is completely _independent of the particular coding scheme. Each symbol V _{k, 0,0, q} [m, n] (however
q> 1), the initial quantization value V _{k, 0,0,1} is transmitted directly using the fixed-length codeword after a single bit is transmitted, and V
It is identified whether _{k, 0,0, q} [m, n] is equal to 2V _{k, 0,0, q-1} or 2V _{k, 0,0, q-1} +1. In the following description, the sample size M _{k, l, b, of} the band C _{k, l, b} subjected to the dead zone quantization for each quantization layer q = 1,2, ... Q _{k, l, b The} procedure required to effectively encode _q [m, n] and the code S _{k, l, b, q} [m, n] is considered. Although the encoding step will be divided into a number of categories as described below, this embodiment requires that the steps required to encode the quantized value of each sample for layer q be First, it is pointed out that two main groups can be determined based on whether or not the sample in the previous quantization layer is zero.
If M _{k, l, b, q-1} [mn] ≠ 0, the code S _{k, l, b} [m, n] has already been coded in the previous quantization layer, and in the layer q It is only necessary to improve the knowledge to derive a magnitude that matches the finer quantization size. This is called improved coding, and is described first for simplicity. But M
_{If k, l, b, q-1} [m, n] = 0, the main processing in layer q is M
It is to encode whether _{k, l, b, q-1} [m, n] is also zero. This is called zero encoding, and the corresponding steps are described in Section 5.2. If M _{k, l, b, q-1} [m, n] ≠ 0, then the actual size if not clear from the sign bit S _{k, l, b} [m, n] and the context Is obtained in order to encode. These points are described in Section 5.3 and 5.4
Section. Although the encodings outlined here may seem complicated, there are efficient mechanisms to implement them in software and hardware with relatively little effort. The flowchart shown in FIG. 9 will be particularly helpful in understanding the description in the following sections.

5.1. Improved Coding Improved coding is very easy to understand. In this case, we already know that M _{k, l, b, q-1} [m, n] is not zero, and the coded bits have already been coded in the previous layer, so

[0113]

[Equation 36] It is only necessary to send a binary value symbol that distinguishes the two cases.

The quantization application parameter is equal to 1 or σ for all layers whose quantized magnitude is found to be non-zero, as described in Section 4.1.
It should be noted that there are certainly only two such cases, since it is guaranteed that _{k, l, b, q-1} = σ _{k, l, b, q} = 1. Conditioning context R _{k, l, b, q} [m, n] (0,1,
2,3}, an appropriate symbol is encoded. It is divided into the following four states. State 0: M _{k, l, b, q-1} [m, n] has the smallest possible value, namely 1, and any of the nearest neighbors in the vertical, horizontal, and right directions is still zero, ie, M _{k, l, b, q} [m, n-1] = M _{k, l, b, q} [m-1, n] = M _{k, l, b, q-1}
If [m, n + 1] = M _{k, l, b, q-1} [m + 1, n] = O, the improved symbol is encoded according to this context. Under these conditions, there is a high probability that the improved symbol is also zero. State 1: M _{k, l, b, q-1} [m, n] has the smallest possible value, ie, 1, but at least one of the nearest neighbors (up, down, left, right) is non-zero, or If either of the two neighboring samples affected in a past two neighboring samples or layer q-1 is found to be non-zero, the refined symbol is encoded according to this context. State 2: If M _{k, l, b, q-1} [m, n] = 2, the improved symbol is encoded according to this context. In this case, M
_An improved symbol is used to identify whether _{k, l, b, q} [m, n] = 4 or M _{k, l, b, q} [m, n] = 5. State 3: If M _{k, l, b, q−1} [m, n] ≧ 3, the improved symbol is encoded according to this context. Here, as long as the samples generated by the morphological transformation are not coded, in the image region where the number of samples with distinct values is limited, the statistical distribution of the improved symbols is beginning to approach a uniform distribution. It must be. A precise conditional arithmetic coding algorithm that encodes binary-valued symbols according to these context states is described in Section 5.7.

5.2. Zero Coding Zero coding is required when the sample is not yet known to be non-zero, ie when M _{k, l, b, q-1} [m, n] = 0. In this case, two cases, ie, M _{k, l, b, q} [m, n] = 0
A single binary symbol must be encoded to distinguish between (symbol 0) and M _{k, l, b, q} [mn] ≠ 0 (symbol 1). In the latter case, the additional information must be encoded, including the sign of the sample that was found to have a non-zero magnitude. However, this is not part of the zero encoding step described here. It is of paramount importance to overall compression efficiency because zero coding accounts for most of the overall compression bit rate for all layers except the finest quantization layer. Since zero encoding also accounts for most of the encoded symbols, it has a significant effect on the overall computational complexity of the compression system. For this reason, in one embodiment, the zero-encoding task is divided into two cases based on the quantized magnitude of the eight nearest neighbors of the sample, as shown in FIG. . In practice, these two cases are distinguished using the binary context variables σ ′ _{k, l, b, q} [m, n] described in section 4.1.

Zero-coding with non-zero neighbors The first case is identified by σ ′ _{k, l, b, q} [m, n] = 1, which is the eight nearest neighbors of the sample. This corresponds to a condition in which at least one of the samples has been found to have a non-zero magnitude. The quantized magnitudes available for the affected past four neighbors are shown in FIG. 6, along with the remaining four neighbor samples. In this case, based on the size of these 8 adjacent samples, a 32-state conditioning context Z _{k, l, b, q} [m,
n] is constructed and, according to this context, a zero-coded symbol is coded using the adaptive arithmetic coder described in Section 5.7 (if M _{k, l, b, q} = 0 0, otherwise 1).
If σ _{k, l, b, q-1} [m, n] = 1, the first 16 states Z
_{k, l, b, q} [m, n] {0,1, ..., 15} are used. in this case,
The previous quantization layer has already been coded and M _{k, l, b} [m, n] <2X (where X
= Q _{k, l, b} -q + 1), while the zero-coded symbol is M _{k, l, b} [m, n] <2Y (where Y = Q _{k, l, b-} q) or not. If σ _{k, l, b, q-1} [m, n] = 0, the second 16 states Z _{k, l, b, q} [m, n] {16,17, ..., 31} is used. In this case, the size M _{k, l, b} [m, n] is not known.
In both cases, the lookup table is 256
The specific context state is indirectly determined by applying to a relatively large set of the indices σ ′ _{k, l, b, q} [m, n]. The formation of this index will now be described in terms of the size of the eight adjacent samples in FIG.

The 8-bit index Z ′ _{k, l, b, q} [m, n] is composed of the following four subwords. Bits 0-2: These are intended to roughly indicate the current point in time information about the average horizontal adjacent sample size of the sample. Specifically, these three bits

[0118]

(37)

The total is stored as follows. This apparently complex representation turns out to be particularly computationally efficient, even in software. It can be easily verified that Equation 37 can take eight different values. It has the following interpretation. 0: Both horizontal neighbors are zero. However, the adjacent sample on the left side can satisfy M _{k, l, b, q} [m, n−1] ≧ 2Y (where Y = Q _{k, l, b} −q). It is known that both horizontal neighbors are zero and 1: M _{k, l, b, q} [m, n-1] <2Y, where Y = Q _{k, l, b} -q. 2: M _{k, l, b, q} [m, n-1] = 1 and M _{k, l, b, q-1} [m, n + 1] = O. 3: M _{k, l, b, q} [m, n-1] ≧ 2 and M _{k, l, b, q-1} [m, n + 1] = O or M _{k, l, b, q} One of [m, n-1] = 0 and M _{k, l, b, q-1} [m, n + 1] = 1. 4: M _{k, l, b, q} [m, n-1] = 1 and M _{k, l, b, q-1} [m, n + 1] = 1. 5: M _{k, l, b, q} [m, n-1] = 0 and M _{k, l, b, q-1} [m, n + 1] ≧ 2 or M _{k, l, b, q} [m, n-1] ≧ 2 and M _{k, l, b, q-1} [m, n + 1] = 1
One of 6: M _{k, l, b, q} [m, n-1] = 1 and M _{k, l, b, q-1} [m, n + 1] ≧ 2. 7: M _{k, l, b, q} [m, n-1] = ≧ 2 and M _{k, l, b, q-1} [m, n + 1] ≧ 2. Bits 3-5: These are intended to roughly indicate the current point in time information about the average size of the vertical neighbors of the sample. These three bits

[0120]

(38) Is stored.

[0121]

[Equation 39] The eight different values assumed by

[0122]

(Equation 40) Has the same interpretation as the corresponding one for.

Bit 6: Any of the diagonally adjacent samples of the sample on the previous scan line is non-zero, ie, M _{k, l, b, q} [m
-1, n-1] ≠ 0 or M _{k, l, b, q} [m-1, n + 1] ≠ 0 only if this bit is known to be
Set to 1. Bit 7: Any of the diagonal adjacent samples of the sample on the next scan line is non-zero, ie, M _{k, l, b, q-1} [m + 1, n-1] ≠ 0
Or, this bit is set to 1 only if it is found that both of M _{k, l, b, q-1} [m + 1, n + 1] ≠ 0.

The final zero encoding state Z _{k, l, b, q} [m, n] is

[0125]

[Equation 41]

By applying one of the two 256-element look-up tables, each producing an integer in the range from 0 to 15, as in the intermediate index Z ′ _{k, l, b, q} Created from [m, n].

The purpose of the look-up table is to reduce the total number of context states, which has a significant effect on the memory requirements of the compression scheme and reduces the adaptation costs associated with adaptive arithmetic coding. The latter effect is particularly important when compressing relatively small images. It should be noted that in the embodiments described above, a separate look-up table is not maintained for every band or every quantization layer. In fact, only two different look-up tables are used for each of the different types of bands b = 0,1,2,3.

Since different values of b correspond to image features having different directional characteristics, the dependence on b is important and has a significant effect on optimal state reduction association. Although the content of these look-up tables is expected to be fixed for all images, this specification does not specify them by category. According to the inventor's experience, a single set of tables has been optimized for the statistics obtained from the set of training images. As far as that particular embodiment is concerned, the optimization algorithm is a pruned tree pruning and iterative L
A relatively simple combination of BG (Lind-Buzo-Gray) optimization techniques.

The zero-encoding procedure when none of the eight nearest neighbors of the zero-encoded sample is known to be non-zero when the adjacent samples are all zero is described below. Taking advantage of this relatively frequent event, by using one type of run-length coding scheme, the total number of symbols to be coded is reduced, thus reducing the complexity of the overall arithmetic coding. Can be. The idea is that given information that has already been encoded (i.e. the information currently available at the decoder), the first step is to make successive samples on the same scan row whose nearest neighbors can potentially remain zero. The purpose is to determine the maximum number of samples C _{k, l, b} [m, n ′] (where N ′ ≧ n). Specifically, each such sample has a σ "
_{k, l, b, q} [m, n '] = 0 must be satisfied. However,

[0130]

(Equation 42)

Is as follows. Let n ′ _max denote the maximum continuous sequence index for σ ″ _{k, l, b, q} [m, n ′] = 0. The run-length encoding scheme of this embodiment consists of the following approximately two steps: 1) Encode a binary value symbol subject to a maximum run length n ' _max -n and use M for any n' in this interval.
_{k, l, b, q} [m, n '] ≠ 0 is identified. 2) If such non-zero magnitude occurs within the maximum run length, send the index n'-n using a fixed length codeword.

As described above, this method has many pitfalls. First, some limit must be placed on the maximum run length considered for practical reasons. Second
In order to minimize the coding adaptation cost along with the memory resources, it is necessary to derive a relatively limited set of conditioning states from a large set of values that may be assumed by the maximum run length n ' _max -n. is there. Finally, because the samples whose neighbors are very close to non-zero samples are likely to have different statistics, the zero encoding strategy needs to be modified. The actual coding scheme designed to address the above problems will now be described.

First,

[0134]

[Equation 43]

According to the above equation, n ′ _max is defined as follows: n ′ _max = W (C _{k, l, b} ) indicates that all samples n ′ ≧ n are σ ″ _k, Note that it means that we have _{l, b, q} [m, n '] = 0. Basically, this definition means that the maximum run length is truncated to ensure that the maximum run length does not exceed 127 and that the right nearest neighbor sample ends with a sample known to be non-zero. I do.

Next, an 8-state run-length context U _{k, l, b, q} [m, n] having the following interpretation is defined. State 0: This state is used if n " _max <n + 1 or σ ' _{k, l, b, q} [m, n-1] ≠ 0. In this case, this sample is its neighbor Are considered very close to another sample that is not all zeros, and run-length encoding is not actually used. Instead, this context state is represented by M _{k, l, b, q}
Used to encode whether [m, n] is equal to zero. State 1: If n " _max = 1, use this state and n '{n, n + 1}
Encode whether M _{k, l, b, q} [m, n ′] is non-zero.
If so, send a single bit (not adaptive arithmetic coding) identifying whether the first such n 'is equal to n or n + 1. State 2: If n " _max {2,3}, use this state and n '
For {n, n + 1, n + 2, n + 3}, encode whether M _{k, l, b, q} [m, n ′] is non-zero. If so, first such n '
Send a 2-bit fixed-length codeword identifying ... State 7: If n " _max {64,65, .., 127}, use this state and n '{n, n + 1, n + 2, ..., n + 127} With respect to M
_Encode whether _{k, l, b, q} [m, n '] is non-zero. If so, send the first 7-bit fixed-length codeword identifying such n '.

5.3. Sign bit encoding The sample is non-zero in the quantization layer q, ie, M
_{When k, l, b, q-1} [m, n] = 0 but M _{k, l, b, q} [m, n] ≠ 0 is first found, the first task is the sign bit S _{k, l, b, q} [m, n]. There may be other information that needs to be encoded, but that will be described in 5.4. There is one special case where there is no need to encode the sign bit. It means that the original image has only two levels (ie one bit per sample)
Is known and the morphological transformation described in Section 2.2 is used. In this case, the sign prediction component of the morphological transformation ensures that the sign bit should always be zero. However, rather than specifically signaling the encoder to this fact, the adaptive arithmetic encoder discovers such extremely biased statistics and encodes deterministic information with as few bits as possible. It is enough to be able to. The particular arithmetic coding described in section 5.7 can achieve rates as low as 2-15 bits per symbol under such conditions.

The sign bit is encoded corresponding to the 16-state context G _{k, l, b, q} [m, n] in the following 4-bit representation form. Bit 0: If any of the horizontally adjacent samples are found to have non-zero magnitude and positive sign, this bit is set to 1 (sign bit equals zero). Bit 1: If any of the vertically adjacent samples are found to have a non-zero magnitude and positive sign, this bit is set to 1 (sign bit equals 1). Bit 2: If any of the vertically adjacent samples are found to have non-zero magnitude and positive sign, this bit is set to 1 (sign bit equals zero). Bit 3: If any of the horizontally adjacent samples are found to have non-zero magnitude and negative sign, this bit is set to 1 (sign bit equals 1).

5.4. Initial magnitude coding In the quantization layer q, it is first non-zero (ie, M
_{k, l, b, q-1} [m, n] = 0) actual sample size M
_The method of encoding _{k, l, b, q} [m, m] is described below. As a result of the adaptive quantization strategy of this embodiment, there are a surprising number of cases to consider. The following description refers in particular to the lower part of the flow chart of FIG.

Before going into the subject, some new notations are introduced.

[0141]

[Equation 44]

Let denote the first quantization layer that is actually included in the bitstream for bands C _{k, l, b, q} as received by the decoder. This value is recorded in the bitstream header described in section 3.2.
Furthermore,

[0143]

[Equation 45] Denote the first quantization layer that the encoder attempts to encode for this band.

[0144]

[Equation 46] Is independent of the image and is assumed to be known a priori to the encoder and decoder. In the simplest case, for all bands,

[0145]

[Equation 47]

Is set. More specifically, the computational processing and memory requirements of the encoder use the larger value of (45) for a larger resolution layer l where a coarser quantization layer is not expected to be useful anyway. Can be reduced. In this case, the assumption of this embodiment that both the encoder and the decoder know in advance the value of Equation 45 above is that this information
It must not be embedded in the bitstream (not covered by the bitstream syntax described in paragraph 3 above), or that, for example, a fixed relationship between layer index l and equation 45 above must be universally given. means.

In contrast to Equation 45 above, since the present embodiment assumes that the images are coded incrementally on arrival as the memory requirements are reduced, the encoder must encode the entire image. Until encoding,

[0148]

[Equation 48]

Cannot be known. Specifically, the quantizer knows the first layer (Equation 48 above) where the quantized magnitude M _{k, l, b, q} [m, n] was found to be non-zero. After that, an attempt is made to encode all quantization layers q = 1, 2,..., Q _{k, l, b} for each band C _{k, l, b} . The quantizer then discards all previous layers, so that the final bit stream received by the decoder

[0150]

[Equation 49]

Only the encoded bits are included. While the encoder is not aware of equation (48), while the encoder is encoding any particular band, the layer

[0152]

[Equation 50]

Each time a non-zero magnitude M _{k, l, b, q} [m, n] where M _{k, l, b, q-1} [m, n] = O is encountered, the layer q Regardless of whether -1 is actually available to the decoder, it is certain that the decoder will notice the fact that M _{k, l, b, q-1} [m, n] = 0. This helps reduce the amount of information that must be encoded when the sample is first found to be non-zero.

Accordingly, the size M _{k, l, b, q} [m, n] that is quantized in the early stage of the sample whose quantized size is non-zero in the layer q-1 is encoded. There are two main cases that need to be differentiated. These cases are distinguished by whether q is equal to Equation 45 above. If q> 45, there is no limit on the maximum value of the quantized magnitude M _{k, l, b, q} [m, n], so there is no need to encode additional information. This case is further addressed in Section 5.5. However, if q = Equation 45, the size M
_No upper bound can be assumed for _{k, l, b, q} [m, n].
In this case, one or more binary-valued symbols are first encoded to set an upper limit, and then the magnitude itself is represented within a suitable range using fixed-length codes. This case is further addressed in Section 5.6. Before that, the use of one of the encoding context states is described since they are used in both cases.

There are a total of four environmental conditions that are provided for the encoding limits for the initial magnitude of a new non-zero sample value. Their interpretation and usage are as follows. State 0: Using this state, M _{k, l, b, q} [m, n] = 1 (symbol
0) or M _{k, l, b, q} [m, n] ≧ 2 (symbol 1). State 1: M _{k, l, b, q} [m, n] {2,3} (symbol 0) or M _{k, l, b, q} [m, n] ≧ 4 (symbol 1 ) Or not. State 2: Using this state, M _{k, l, b, q} [m, n] {4,5,6,7}
(Symbol 0) or M _{k, l, b, q} [m, n] ≧ 8 (symbol 1) is encoded. State 3: This state has the size M described in section 5.6.
_{k, l, b, q} Used as necessary for upper limit identification for [m, n]. An independent set of four context states is rarely used in finer quantization layers, but is maintained for each quantization layer in each band.

5.5. Initial Size Encoding for q> Equation 45 In this case, both the encoder and the decoder
Knowing the fact that _{Mk, l, b, q} [m, n] = 0, there are only three possible cases: Case 1: At least one of the eight most recent samples of the samples in both the current quantization layer q and the previous quantization layer q-1 is nonzero, ie, σ ′ _{k, l, b, q} [m, n ] = σ '
It is known that _{k, l, b, q-1} [m, n] = 1. In this case, M
_{k, l, b} [m, n] <2X (where X = Q _{k, l, b} -q + 1), that is, M _{k, l, b, q} [m,
Since the previous quantization layer reveals that n] <2, the new non-zero magnitude must be 1 and does not need to be coded. Case 2: at least one of the last eight samples of the current quantization layer q is non-zero but the previous quantization layer
All of the samples at q-1 are zero, ie σ '
It is known that σ ′ _{k, l, b, q−1} [m, n] = 0 when _{k, l, b, q} [m, n] = 1. In this case, M _{k, l, b, q} [m, n] <2X (where X = Q
_{k, l, b} -q + 2), that is, M _{k, l, b, q} [m, n] {1,2,3} is found from the previous quantization layer. To encode the actual magnitude, use magnitude context state 0, which conditions the encoding of this symbol, with magnitude equal to 1 (symbol 0) or 1
Binary to identify larger (symbol 1)
Encode the symbol. If the value is greater than 1, proceed to the improved encoding process and encode M _{k, l, b, q} [m, n] using exactly the same procedure and context state as described in section 5.1 above. Case 3: None of the last eight samples are known to be non-zero, ie, σ ′ _{k, l, b, q} [m, n] = 0. In this case, M _{k, l, b, q} [m, n] {2,3}, again proceeding to the improved encoding process, using exactly the same procedure and context state as described in section 5.1 above. M _{k, l, b, q}
Encode the least significant bit of [m, n]. These steps are shown in the lower right part of the flowchart in FIG.

5.6. Encoding of Initial Size When q = Equation 45 If it is not yet known whether q is the first quantization layer received by the decoder, the additional information is encoded to identify the upper limit on the size. There must be. The encoding procedure involves two main steps: Step 1:

[0158]

(Equation 51)

Encode the values of all but the least significant bits of M _{k, l, b, q} [m, n], denoted as Step 2: Encode the least significant bits of M _{k, l, b, q} [m, n] using exactly the same procedure and context state as described in section 5.1 above.

There are two cases to consider before encoding M ′ _{k, l, b, q} [m, n]. Case 1: None of the eight most recent samples is known to be non-zero, ie, σ ′ _{k, l, b, q} [m, n] = 0. In this case, M _{k, l, b, q} [m, n] ≧ 2, and therefore
It has already been found that M ′ _{k, l, b, q} [m, n] ≠ 0. Case 2: One or more of the last eight samples of the sample are known to be non-zero, ie, σ ′ _{k, l, b, q} [m, n] = 0. In this case, M _{k, l, b, q} [m, n] = 1 (symbol
0) or M _{k, l, b, q} [m, n] ≧ 2 (symbol 1) must be encoded first. M _{k, l, b, q} [m, n] = 1
Then no further encoding is needed, otherwise
M ′ _{k, l, b, q} [m, n] ≠ 0.

[0161] _{M 'k, l, b,} q [m, n] if it is determined that ≠ is _{0, M' k, l,} b, q [m, n] < minimum exponent e as 2 ^e Is first encoded. The magnitude context state is used to encode a binary value symbol indicating that e = 1 (symbol = 0) or e ≧ 2 (symbol 1). If it turns out to be the latter case, using context state 2, e = 2 (symbol =
0) or a binary value symbol indicating that e ≧ 3. If the latter proves to be the case further, context state 3 is used to encode a binary-valued symbol indicating that e = 3 (symbol = 0) or that e ≧ 3. In this way, the encoding of e = 3, 4,... Is repeated until the value of e is completely encoded. Such a scheme is often called a comma code. If the value of e is coded, the value M _{'k, l, b,} sends the _{q [m, n] e-} 1 -bit fixed length code words to represent -2 ^e.

5.7. Adaptive Arithmetic Encoder Apart from the large number of fixed length codewords described above, most of the information from any given quantization layer is applied to the adaptive arithmetic coder to apply some Created by encoding a binary value symbol (0 or 1) corresponding to the context state. The distribution associated with each state is updated separately to reflect the statistics of all previously encoded symbols within the same context state. Let P (1) denote the probability that the symbol is equal to one. This is enough for the symbols to characterize a binary distribution. In practice, the actual probabilities are not known; rather, P (1) represents a probability estimate based entirely on previously coded symbols in the same context state. This document does not describe the basic arithmetic coding algorithm used to encode binary-valued symbols according to a given distribution. Because it is well known and relatively simple. It should be noted, however, that using the exact same fixed-point representation for the probabilities and the intermediate accumulators that form an integral part of the algorithm is important for both the encoder and the decoder. In this embodiment, the accumulator has 31-bit precision, and the probabilities are represented using 15-bit precision, which is perceived to be a particularly convenient quantity for software implementation. The remaining problem is
An algorithm that efficiently calculates an appropriate estimate for P (1).

Although extremely small values of P (1) may need to be accurately represented, the following is described to take advantage of the fact that P (1) is practically very close to 1. The algorithm is designed. Because all the above symbol definitions are biased towards the choice of zero as the most likely symbol, we support a few exceptional cases where any symbol is more likely than another symbol. There is no a priori reason that can be done. The algorithm is also designed to hold all state information in a single 16-bit word. This information is updated efficiently, using either a simple look-up table in software implementation or an efficient combination of a small look-up table and low precision multiplier for hardware implementation. An estimate of P (1) based on is derived. Note that JPEG and J
IB exposed to both BIG arithmetic coding options
M's famous Q encoder is used to store context state information.
Although only 8 bits are required, relying on this encoder generally sacrifice some compression efficiency.

The 16-bit status word is divided into three groups as follows. S: This holds the regular expression for the number of symbols mentioned above
7-bit quantity. N: This is a 6-bit quantity that holds the 1 regular expression described above. E: This is a very small value of P when the value of N is equal to zero.
A 3-bit power number used to estimate (1).

These three quantities are updated as follows. After encoding symbol 1: set E = 0, then increment S and N together. If this operation causes a quantity overflow, divide both quantities by two and truncate the remainder before incrementing them. After encoding symbol 0: increment S only. If this operation causes an overflow of S, divide both the N and S quantities by two and truncate the remainder of the division before incrementing S. If equal to zero before division, increment exponent E unless exponent E is already at maximum 7.

The following describes how P (1) is calculated from E, N and S to complete the description of the adaptive encoder. If N ≠ 0, the estimate is clearly P (1) = N / S. On the other hand, when N = 0, N must have been shifted down at least E + 1 times since N was finally equal to one. Therefore, the estimated value is P (1) = 1 / (S * ^{2E + 1} ). Of course, this probability expression is a 15-bit fixed point. Furthermore, importantly, this representation is easy to compute in hardware and software. The simplest approach in software is to use N and S together to create a 13-bit index into the look-up table and shift the result down E times. However, in hardware, such large look-up tables are expensive and cannot be justified. The preferred embodiment in hardware uses a very small look-up table to determine the appropriate precision and multiply this quantity by N. Since both embodiments must produce exactly the same result under all circumstances, the present invention specifies an algorithm that computes P (1) in a hardware embodiment, and then uses a compatible quantity. Leave a software embodiment that fills in a larger lookup table. The exact definition of P (1) as a 15-bit fixed-point quantity is as follows:

[0167]

(Equation 52)

It is a very simple matter to verify that this quantity is always in the range 1 ≦ 2 ¹⁵ P (1) ≦ 2 ¹⁵ −1, which means that the bitstream is correctly encoded. It is enough range to confirm that it is waxy.

5.8. Required Memory Intermediate Buffer Size It is straightforward to calculate the total amount of intermediate buffer storage required to implement the encoding scheme described above. As shown in FIG. 8, at most Q _{k, l, b} +1 scan rows must be maintained for each band. In this case, Q _{k, l, b} +1 is the finest quantization layer related to coding. To translate this into a simple expression, for all bands Q _{k, l, b} = 8
Suppose that In fact, it has been found that eight quantization layers are adequate enough for most purposes. Given that each scan row is halved in size each time the multi-resolution pyramid is moved down, for all difference bands generated using the overcomplete morphological transform,

[0170]

(Equation 53)

For high frequency subbands generated using a non-overcomplete subband transform, the total sample values

[0172]

(Equation 54)

The total sample value must be buffered. The storage capacity for morphological and sub-band transforms is not added, even if interested in switching between two transforms in different areas of the image. This is because each region is compressed as a separate image whenever a switch occurs, with the only exception that the context state used for adaptive coding is not reinitialized.

In addition, it must be possible to store context state information for all quantization layers of all bands. If calculated, exactly 64 different context states of 2 bytes each must be provided for each quantization layer in each band. Assuming 8 quantization layers and up to 7 levels for each color component in the bi-resolution decomposition, and all 4 bands are used at each level (i.e. it is desirable to support morphological and sub-band transforms simultaneously) ), The total K *
28.672k bytes of context state memory are required.

To consider the combination of the transform buffer and the encoding buffer, which affect the required capacity of the entire intermediate buffer, the results of Section 2.4 are combined with the above numbers, and the band sample values are represented with 16-bit precision, while the image samples are Assuming 8-bit precision, the total memory requirement is

[0176]

[Equation 55]

Is obtained. Assuming that the image is black and white (K = 1), has 6000 pixels per scan line, and uses T = 9 to support subband filters, the total memory requirement is 281 kbytes. This sum would be reduced to 247k bytes if no morphological transforms were used and only sub-band transforms were supported. It is worth noting that the memory requirements are actually governed by the transform, not the coding stage, despite the large number of embedded quantization layers. Alternatively, a somewhat smaller sub-band filter can be used. For example, the exact reconstruction filter developed by Ricoh (which is appropriate for lossy / lossless joint compression) has T = 6 and the intermediate buffer requirement for subbands alone is 19
Reduce to 3k bytes. By comparison, standard baseline JPEG compression requires about 48k bytes or more.

Memory Band for Hardware Implementation
Width and On-Chip RAM A simple hardware embodiment of the above-described encoding scheme sequentially processes a single scan row of each quantization layer in each band. In this case, the required capacity of the on-chip RAM is governed by the following items. Memory required for 64 context state words, each 16 bits wide for the appropriate layer of the band being processed.
A double buffer may be required, a total of 256
Requires bytes. • For the two lookup tables as described above,
An additional 256 bytes of on-chip memory is required. -Requires some additional on-chip memory required to implement the run-length encoding scheme described above. This would require internal buffer storage of up to 65 sample samples (16 bits wide each) from three scan lines used to obtain contextual information. This is an additional 39
Add 0 bytes to the required memory on chip. However, there are a number of techniques that can dramatically minimize this component. In particular, run-length encoding techniques can be included on the ASIC itself to provide it with negligible components of the overall on-chip memory.

6. Performance The compression system described herein achieves competitive compression performance for a wide variety of image types, including natural images, graphics, synthetic documents, and two-level image sources. Can be. Furthermore, for all of these image sources, the system produces a highly scalable compressed bit stream that can be scaled in parallel with respect to resolution and bit rate.

The adaptive quantization method described in section 4 and 5
The relevant encoders described in section include both the CASAC (ie, context-adaptive continuous approximation and coding) algorithm, but have been tested in conjunction with the multi-level subband transform described in section 2.3. With regard to natural image processing, it has been observed that the compression performance of the present embodiment requires much less memory and is competitive compared to other state-of-the-art compression schemes. It should be noted that the adaptive quantization characteristics can be retrieved with almost no modification, while incorporating the quantization strategies used in almost all existing scalable image compression schemes. Taking advantage of this advantage, it was possible to verify that the adaptive quantization strategy actually produced a more visually pleasing image. Images compressed with adaptive quantization are slightly poorer than those compressed with non-adaptive embedded quantizer
Despite the fact that it typically has a reconstructed MSE (approximately 0.1 to 0.2 dB), the above points have been observed to be true.

7. Notes Many features and advantages of the invention are apparent from the above description. In addition, many modifications and changes will occur to those skilled in the art, so it is not desired to limit the invention to the exact same construction and operation as illustrated and described.
Accordingly, all appropriate modifications should not be deemed to depart from the spirit of the invention.

The present invention includes the following embodiments as examples. (1) A method for compressing a digital image, wherein spatially adaptive embedded quantization is performed on the digital image, and a quantization symbol generated as a result of the step is encoded to form a compressed image. And a digital image compression method. (2) The digital image compression method according to the above (1), comprising a step of performing a digital image conversion prior to the embedded quantization step. (3) The digital image compression method according to (2), wherein the image conversion step includes morphological conversion. (4) The digital image compression method according to (3), wherein the morphological transformation includes a sign prediction operator. (5) The digital image compression method according to (2), wherein the image conversion step includes a conversion selected from a set of a subband and a wavelet transform. (6) The digital image compression method according to (1), wherein the embedded quantization step includes embedded dead zone quantization. (7) The digital image compression method according to (6), wherein the dead zone quantization is characterized by a single parameter identifying a coarsest quantization step size. (8) wherein the embedded dead zone quantization comprises: converting a sample of the image into a code value representation; and discarding an appropriate number of lower bits of the code value representation.
The digital image compression method according to the above (6).

(9) If the sample has a size greater than the coarse step size, the sample and its neighboring samples are quantized and encoded using a finer step size. 2. The digital image compression method according to 1. (10) The digital image compression method according to (2), wherein independent bands of the transform are independently quantized and decoded. (11) When generating a conditioning context to encode the quantization layer of scan row m for any particular band, any information appearing beyond scan row m + 1 in coarser quantization layer q-1 Is not used, nor is any information that precedes the scan line m-1 in the current quantization layer q used.
The digital image compression method according to the above (1). (12) performing the improved encoding if the sample is recognized as non-zero in the previous quantization layer, and encoding the embedded quantization symbol; Performing the zero-encoding if it is determined that the digital image compression is performed. (13) If the sample is found to be zero in the previous quantization layer, performing the zero encoding comprises performing a code encoding and performing an initial magnitude encoding. The digital image compression method according to the above (12). (14) given the continuous run length of the sample previously quantized to zero, the sample quantized to zero is continuously encoded using a run-length encoding scheme, as described in (12) above. 2. The digital image compression method according to 1.

(15) A method of decompressing the compressed image described in (1). (16) The digital image compression method according to (1), including a step of performing bit stream editing of the compressed image. (17) The bit stream editing of the compressed image includes the step of discarding unnecessary subbands from the compressed image to select a certain resolution.
The digital image compression method according to 6). (18) The step of (16), wherein the step of performing the bitstream editing of the compressed image includes a step of discarding unnecessary quantization layers in related subbands from the compressed image to select reproduction fidelity. Digital image compression method. (19) A processor for performing compression of a digital image, a means for performing spatial adaptive built-in quantization on the digital image, and encoding a compressed symbol generated as a result of the quantization into a compressed image. Means for forming a digital image compression processor. (20) A bitstream editor for selectively reducing the size of an image compressed by the processor according to (19). (21) An expander for expanding an image compressed by the processor according to (19).

[0185]

The present invention efficiently compresses / compresses composite digital images while providing resolution and bit rate scalability and integrating lossless and lossy compression.
It is possible to stretch.

[Brief description of the drawings]

FIG. 1 is a block diagram illustrating an embodiment of a CASAC integrated scalable image compression / decompression system according to the present invention.

FIG. 2 is a block diagram illustrating a two-level multi-resolution conversion according to an embodiment of the present invention.

FIG. 3 is a block diagram illustrating morphological sub-sampling and interpolation of a digital image according to an embodiment of the present invention.

FIG. 4 is a block diagram showing a configuration of a compressed bit stream according to an embodiment of the present invention.

FIG. 5 is a block diagram illustrating an example of a built-in dead zone quantizer according to an embodiment of the present invention.

FIG. 6 is a block diagram illustrating neighbor information used to quantize and encode bands in a quantization layer according to an embodiment of the present invention.

FIG. 7 is a block diagram illustrating an example of an embedded uniform quantizer according to an embodiment of the present invention.

FIG. 8 is a block diagram illustrating an embodiment of the present invention in which four scan rows are buffered to encode or decode all layers of a three-layer band.

FIG. 9 is a flowchart illustrating encoding of information associated with a band sample for quantization, according to an embodiment of the invention.

[Explanation of symbols]

 100 Integrated Scalable Image Compression / Decompression System 105 Uncompressed Image 110 Compressor 115, 125 Scalable Bitstream 130 Decompressor 135 Decompressed Image

Claims (1)

[Claims] 1. A method for compressing a digital image, comprising the steps of: performing spatial adaptive embedded quantization on the digital image; and encoding the quantized symbols generated as a result of the step to form a compressed image. And a digital image compression method.