Image coding with scalable context quantization

A scalable quantizer is generated from a plurality of context models for each of a plurality of bit rates used in coding a source. A context model for a lower bit rate quantizes conditioning states when there is no compression gain in coding the image using child conditioning states in the higher bit rate context model over a parent conditioning state to which they may be quantized. The scalable quantizer includes a basic context model for a lowest anticipated bit rate and enhancement bits indicating how to adapt the basic context model to derive context models for higher bit rates. For image data transformed with embedded wavelet coding, context events are selected from corresponding or neighboring pixels at different resolutions and in different bit planes, and the order of the context events is optimized to reduce conditional entropy between the context events and the current value.

BACKGROUND

Improving digital imaging technology allows for increasingly higher resolution and color variation in digital images. As image quality increases, however, resulting image data files increase geometrically in size. Image compression technologies strive to reduce the storage required to store image data and the bandwidth needed to transmit image data.

Image compression technologies seek to balance competing interests. On one hand, it is desirable to compress the size of a data file as much as possible so that the compressed file will consume the least amount of storage or bandwidth. On the other hand, the more a data file is compressed, the more computing resources and time are consumed in compressing the file.

FIG. 1shows a functional block diagram of a representative encoder100and decoder140pair used to compress and decompress source data102, respectively. For sake of example, the source data102includes image or video data. The encoder100receives the source data102. In one embodiment, the encoder100first presents the source data102to a preprocessor104. The preprocessor104separates the source data102into luminosity (grayscale) and chrominosity (color) components.

The output of the preprocessor104is presented to a transformer106that performs frequency transformation on the output of preprocessor104. The transformer106may perform discrete wavelet transformation (DWT), discrete cosine transformation (DCT), fast Fourier transformation (FFT), or another similar frequency domain transformation on the preprocessed data. Individual data values vary less from neighboring values in transformed, frequency domain data, as compared to the spatial domain data.

Taking advantage of the less variant data values in the frequency domain data, the quantizer108identifies and aggregates data values having identical values, replacing a repeating series of identical data values with one instance of the data value combined with an indication of how many times the identical data value repeats. Similarly, the quantizer may combine a series of similar but not identical values with a single identical value when data values representing them with data points of equal value when the data values fall within a particular tolerance. Aggregating similar but not identical data values is used in lossy compression where some degradation of the original image is acceptable.

The output of the quantizer108is presented to an entropy coder110that generates the compressed image data120. Generally, entropy coding compresses data by identifying or predicting the frequency with which data values occur in a data file. Then, instead of representing each data value with a fixed, equal-length value, entropy coding represents more frequently appearing data values with shorter binary representations. By replacing frequently appearing data values with shorter representations instead of fixed, equal-length representations, the resulting compressed data120is reduced in size.

The compressed data120generated by the entropy coder110is presented to a channel130. The channel130may include data storage and/or data transmission media. A decoder140receives or retrieves the compressed data120from the channel130and decompresses the compressed data120through a mirror image of the process applied by the encoder100. The compressed data120is translated by an entropy decoder142, a dequantizer144, an inverse transformer146, and a postprocessor148that ultimately presents output data150, such as image or video data suitable for presentation on a display or other device.

The entropy coder110uses a probabilistic context model to determine which values are assigned shorter and longer codes by predicting or determining which data values to appear more and less frequently, respectively. The context model includes a plurality of conditioning states used to code the data values. The context model used by the entropy encoder110may be a static model, developed off-line and stored both with the encoder100and the decoder140. However, because the frequency with which data values may vary substantially between different data files, using a universal context model may not result in effective compression for every data file. Alternatively, a context model may be developed for each data file. The context model used by the entropy coder is stored and transmitted as part of the compressed data120, so that the context model is available to the entropy decoder142to decode the compressed data120.

Compression may be increased by using a higher order context model. A high order context model includes a large number of conditioning states for coding the data values, thus allowing for the possibility of higher coding efficiency in coding data values with the fewer bits. However, a higher order context model not only includes a large number of predicted values, but the conditioning states themselves are of a higher order. Thus, the higher the order of the context model, the more storage or bandwidth the context model consumes.

Further, if the order of the model is too high, a higher order context model may actually reduce coding efficiency. If too high an order context model is used, the coded data values may not converge sufficiently to meaningfully differentiate between data values occurring more and less frequently in the input data. This problem commonly is known as “context dilution” or “model cost,” and reduces efficiency of the entropy coder.

One solution to address the content dilution problem is context quantization. Context quantization encodes values based on a selected subset of conditioning states representing data values from an area adjacent the data value being coded. Because of the complexity of finding good conditioning states and the significant overhead of representing the found conditioning states presented by the quantizer, conventional context quantizers are trained offline from a training set of data values. However, as previously described, the frequency with which data values appear in different sets of data will vary. Thus, quantizing a context model on training sets may not consistently provide effective compression.

Further complicating matters is that a context model generated or quantized for coding a source at one bit rate may not work as well for coding a source at a different bit rate. For example, a context model suitable for coding a source at a high bit rate, where more samples of the source are provided, may pose a pronounced context dilution concern when coding using a low bit rate. Different models may be created for different bit rates, but creation, storage, and/or transmission of different models for a number of different bit rates consumes processing, storage, and bandwidth resources, respectively.

SUMMARY

A scalable quantizer is generated from a plurality of context models for each of a plurality of bit rates used in coding a source. A context model for a lower bit rate quantizes conditioning states when there is no compression gain in coding the image using child conditioning states in the higher bit rate context model over a parent conditioning state to which they may be quantized. The scalable quantizer includes a basic context model for a lowest anticipated bit rate and enhancement bits indicating how to adapt the basic context model to derive context models for higher bit rates. For image data transformed with embedded wavelet coding, context events are selected from corresponding or neighboring pixels at different resolutions and in different bit planes, and the order of the context events is optimized to reduce conditional entropy between the context events and the current value.

DETAILED DESCRIPTION

Scalable Context Quantizer for Coding a Source at Multiple Bit Rates

FIG. 2is a block diagram illustrating an embodiment of a mode of a scalable context quantizer200. In one mode, the scalable context quantizer200receives a plurality of potential conditioning states210and generates a scalable context model230that is scalable for coding sources at a plurality of bit rates.

In one exemplary mode described in detail herein, the scalable context quantizer200derives the scalable context model220from the 2Nconditioning states210, derived from N binary context events230, using a context quantizer240and a model scaler250. From the 2Npotential conditioning states210, the context quantizer240generates a plurality of context models260for each of a plurality of respective bit rates. As will be further described below, in one mode, the context quantizer240determines whether worthwhile compression gain is sacrificed by quantizing higher order conditioning states to a parent conditioning state.

The model scaler250recognizes a basic context model270that is used for coding a source at a low bit rate and how the basic context model270is adapted for higher bit rates by the context quantizer240. More specifically, in one mode, the model scaler250determines when conditioning states previously quantized to parent conditioning states have been replaced by one or more levels of child conditioning states to achieve a compression gain at a higher bit rate.

Instead of providing a plurality of complete context models for each of the respective bit rates, however, the scalable context quantizer200presents a single basic context model270and a set of enhancement bits280. As further described in connection withFIG. 6, the enhancement bits280are generated by the model scaler250as an indication of how the basic context model is adapted to the generate a context model adapted for a higher bit rate. By analogy, context models for each of a number of bit rates can be reconstituted from the basic context model270by applying one or more sets of enhancement bits280.

In one embodiment of the scalable context quantizer220, the basic context model270is a context model quantized for coding the source at a lowest anticipated bit rate. As is described below with regard toFIG. 3, in one mode of the scalable context quantizer220, the context models260, including the basic context model270, are be quantized to improve compression gain for each bit rate.

For each of the higher anticipated bit rates for which the source may be coded, there may be a set of enhancement bits to adapt a previously derived context model suites for coding at a lower bit rate. The context model for the next lower bit rate may include the basic context model270or a context model previously derived from the basic context model270using one or more sets of enhancement bits. The one or more sets of enhancements bits each are generated to adapt a context model for a next lower bit rate for coding at a current bit rate. By applying the enhancement bits to the conditioning states in a previously derived context model, as described in connection withFIG. 6, the previously derived context model for use in coding the current bit rate is derived.

In sum, a mode of the scalable context quantizer200quantizes available conditioning states in context models for each of a plurality of bit rates used to code the source to improve compression gain. However, instead of storing each of the context models for each of the bit rates, the context models are reduced to a basic context model and a series of enhancement bits from which each of the context models can be derived.

Process of Generating a Scalable Context Model and Enhancement Bits

FIG. 3is a flow diagram of a process300used in generating a scalable context model as introduced with regard toFIG. 2. In one mode, at302, N binary context events are identified to be used in coding samples from a source. At304, the 2Npossible conditioning states based on the N context events are identified. As is described further below, it may be desirable to order the context events to present conditioning states to reduce entropy and enhance compression.

At306, a context tree model is created including nodes representing the potential conditioning states, as illustrated inFIG. 4. The context tree model400represents all of the possible conditioning states for three binary context events. The context tree400includes N layers where, as in the example ofFIG. 4, N is equal to 3. The layers range from a topmost layer, layer1410to a bottom layer, layer3430. The bottom layer430of the context tree400includes all of the possible three-bit conditioning states. Each next higher layer, including layers420and410, includes one or more conditional states or nodes that may be quantized from conditional states or nodes in a lower layer. For example, layer2420includes parent conditioning state00422, to which potentially will be quantized child conditioning states000432and001434. Similarly, layer2420includes parent conditioning state01424, to which potentially will be quantized child conditioning states010436and011438. Layer1410includes parent conditioning state0412to which potentially will be quantized child conditioning states00422and01424. Using such a context tree model in general is described in “Tree Coding of Bi-Level Images,” B. Martins and S. Forschammer, IEEE Transactions on Image Processing, vol. 7, pp. 517–528 (April 1998).

Referring again toFIG. 3, at308, quantizing context models begins with an unquantized layer and processing for the highest bit rate. At310, the process300proceeds to a next pair of child conditioning states or nodes. At312, the child conditioning states are evaluated relative to its parent node to determine whether there is any compression gain of coding with the child conditioning states instead of the parent conditioning state at the current bit rate.

In one mode, compression gain achieved by using any particular conditioning states is determined according to Eq. (1):
G(C,C0,C1)=I(C)−[I(C0)+I(C1)]−Split Cost  (1)
In Eq. (1), G is the compression gain, which is determined as a function of three conditioning states: C represents the parent conditioning state, and C0and C1represent each of the child conditioning states. The Split Cost represents a pre-defined value limiting a number of quantized conditioning states. I is the entropy of a subject conditioning state X calculated according to Eq. (2):

I⁡(X)=f1⁡(log⁢⁢f1X+δf1X+f0X+δ)+f0⁡(log⁢⁢f0X+δf1X+f0X+δ)(2)
In Eq. (2), f1xis a number of encoded significant bits, f0xis a number of encoded insignificant bits, and δ is a constant. In one mode, the constant δ is set equal to 0.45. The constant δ is optimized using JBIG, as described in “JBIG: Progressive Bi-Level Image Compression,” ISO/IEC International Standard 11544 (1993).

At314, it is determined if using child conditioning states provide a compression gain over their parent conditioning state. If not, at316, the child conditioning states are quantized to the parent conditioning state, thereby pruning the child conditioning states or child nodes from the context tree. Two points should be noted. First, whether there is a compression gain realized by using the child conditioning states may be determined by whether using the child conditioning states provides any compression gain or a threshold compression gain such that the compression gain is worth increasing the size of the context model to include the child conditioning states. Second, the determination at312and comparison at314may be performed iteratively. It may be determined that, for a particular bit rate and source, that not only should the child conditioning states be quantized to their parent states, but that one the conditioning states on one or more additional layers also should be quantized.

FIG. 5illustrates a context tree500representing the context tree400(FIG. 4) for which a plurality of conditioning states have been quantized to parent conditioning states. For a bottom third layer530, it is determined that child conditioning state000532and child conditioning state001534provide a desirable compression gain over using parent conditioning state00522on the second layer520. Thus, child conditioning states000532and001534are not quantized to their parent conditioning state00522.

On the other hand, based on the determined compression gain, by comparison withFIG. 4, child conditioning states010436and011438have been quantized to parent conditioning state01524. In addition, every conditioning state that was a child or grandchild of conditioning state1514has been quantized to conditioning state1514. As previously described, the context tree400may have been quantized to the context tree500for a next highest anticipated bit rate, or the context tree500may be the result of the context tree400being successively quantized for each of a plurality of anticipated bit rates.

Referring back toFIG. 3, after it is determined that the potential compression gain dictates quantizing the conditioning states at316, or if it was determined at314there was no such compression gain, at318, it is determined if all the child conditioning states or nodes have been evaluated. If not, the process loops to310to identify the next two child conditioning states or nodes to determine whether they should be quantized. On the other hand, if it is determined at318that all the child conditioning states have been evaluated, at320, the quantized context model is presented for use at the current bit rate.

At322, it is determined if the context tree has been quantized for all anticipated bit rates. If not, at324, the context model for the next highest bit rate, which was just presented at320, is evaluated at the next lower bit rate, and the process loops to310to begin the process of quantizing the context model for the next lower bit rate. On the other hand, if it is determined at322that the context tree has been quantized for all bit rates, the process ends at326.

Generating Enhancement Bits to Extend a Lower Order Context Model

As previously described with regard toFIG. 2, a mode of a scalable context quantizer generates a scalable context model220including a basic context model270and one or more sets of enhancement bits280that allow the basic context model270to be extended to one or more higher order context models suitable for higher bit rates.FIG. 6is a flow diagram of a process600for comparing a context model generated for one bit rate to the context model for a next higher bit rate and generating the appropriate enhancement bits.FIGS. 7 and 8provide examples of how the enhancement bits derived to represent how to adapt a lower order context model (FIG. 7) for a lower bit rate to a higher order context model for a next higher bit rate (FIG. 8).

InFIG. 6, the process600begins at602with the context model that was generated for the lowest anticipated bit rate. As previously described with regard toFIG. 3, in one mode, a context tree model is generated included all the potential conditioning states. Then, for each of the anticipated bit rates, from the highest to the lowest, a context model is generated by quantizing child conditioning states to their parent conditioning states when using the child conditioning states does not result in a desired compression gain. Thus, the context tree is systematically quantized for each succeeding lower anticipated bit rate. The process600ofFIG. 6follows a reverse order, starting with the context model for the lowest anticipated bit rate and generating enhancement bits to scale the context model for each succeeding higher anticipated bit rate.

At604, a starting conditioning state in the current context model is identified. Starting with the context model for the lowest bit rate, the lowest bit rate context model thus is the current context model. In addition, in one mode, the process of generating enhancement bits begins with the highest order conditioning state at a low magnitude end of the context model. As is discussed further below, in the example ofFIGS. 7 and 8, the starting conditioning state is conditioning state00702, the highest order conditioning state on the left, low magnitude side of the context model.

At606, by comparing the current conditioning state in the current context model with the current conditioning state in the context model for the next lower bit rate, it is determined whether the current conditioning state is split into child conditioning states in the higher order model. In other words, it is determined whether, in the context model for the next higher bit rate, the child conditioning states were quantized to their parent conditioning state. If so, at608, a significant bit is inserted in the enhancement bits to represent the split of the conditioning state. On the other hand, if it is determined at606that the conditioning state is not split, a nonsignificant bit is inserted in the enhancement bits. It should be noted that using a significant bit to represent a conditioning state that is split into child conditioning states and using a nonsignificant bit to represent a child conditioning state that is not split is a convention, and an opposite designation of bits or some other form of indication could be used. However, the convention may be considered appropriate, because a nonsignificant bit, or zero, indicates there is no enhancement from the current conditioning state into child conditioning states, while a significant bit, or one, indicates there is enhancement from the current conditioning states into its child conditioning states.

After either a significant bit or a nonsignificant bit is inserted in the enhancement bits at608or610, respectively, at612it is determined if all the conditioning states have been checked to see if all the conditioning states in the current context have been checked to determine if each is split into child conditioning states in a context model for a next higher bit rate. As is described below with reference toFIG. 8, checking the conditioning states includes any child conditioning states into which conditioning states in the current context model have been split. If not, at614, the next highest order conditioning state in the current context model is selected, and the process600loops to606to evaluate whether this conditioning state is split into child conditioning states. On the other hand, if it is determined at612that all the conditioning states have been checked, at616, a set of enhancement bits is presented for use in scaling the context model for the current conditioning state to a context model for a next higher bit rate.

At618, it is determined if enhancement bits have been generated to describe how to adapt a context model from each lower bit rate to each higher bit rate. In other words, at618, it is determined if enhancement bits have been generated to describe how to create the highest order context model for the highest anticipated bit rate. If not, at620, the context model for the next higher bit rate is retrieved or accessed, and the process600loops to604to identify the starting conditioning state in the new current context model to begin the enhancement bit evaluation.

On the other hand, if it is determined at618that all enhancement bits used in generating all the context models for all of the anticipated bit rates have been generated, at622, each of the sets of enhancement bits is included in the scalable context model220(FIG. 2) with the basic context model for use in deriving each of the context models for each of the bit rates from a context model for a next lower bit rate. The scalable context model220is then stored with or transmitted with the compressed image data for use in reconstituting source data at a selected bit rates.

FIGS. 7 and 8illustrate context models700and800suitable for coding an image at a lower bit rate and a higher bit rate, respectively, to illustrate how a set of enhancement bits is derived to scale context model800from context model700. A previous context model700, for sake of example, may represent a context model for a lowest anticipated bit rate, and a next context model800may represent a context model for a second lowest anticipated bit rate. Alternatively, context models700and800may represent context models for any pair of bit rates, and the enhancement bits will indicate how to scale from the lower order context model700for a lower bit rate to the higher order context model800for a higher bit rate. The enhancement bits may be used to indicate how to scale between any two context models, and are not limited to only indicating how to adapt between adjacent bit rates.

InFIG. 8, child conditioning states into which a parent conditioning state has been split are presented in boldface type and shaded for purposes of highlighting the additional conditioning states. Enhancement bits are represented by dashed circles containing either a “0,” for a nonsignificant bit or a “1” for a significant bit.

According to a mode of the enhancement bit generation process ofFIG. 6, inFIG. 7, a starting conditioning state is identified as the highest order conditioning state on the lowest magnitude side of the context model tree700. Thus, the starting conditioning state is conditioning state70200. Starting with conditioning state00702, it is determined if each of the conditioning states in the previous context model700is split into child conditioning states in the next context model800for a higher bit rate. Comparing conditioning state00702in the context models700and800, conditioning state00702is not split into child conditioning states in next context model800. Because conditioning state00702is not split, according to the convention of the process600(FIG. 6), a nonsignificant bit or “0”852is inserted as an enhancement bit.

Because conditioning state00702is not scaled into child conditioning states, moving in order of magnitude from left to right across the context tree model as previously described, the next highest order conditioning state is conditioning state01704. Comparing context models700and800, conditioning state01704is split into child conditioning states010806and011808. Thus, a significant bit or one854is inserted as an enhancement bit for conditioning state01704. Moving to the next highest order conditioning states from conditioning state01704involves moving to the child conditioning states010806and011808. Neither of these child conditioning states is further split into child conditioning states. Thus, nonsignificant bits856and858are inserted as enhancement bits for conditioning states010806and011808, respectively.

Because there are no further child conditioning states of a higher order for conditioning states010806and011808, the next highest order conditioning state in terms of magnitude is1710. Conditioning state1710is split into child conditioning states10812and11814, thus, a significant bit860is inserted in the enhancement bits for conditioning state1710. The next higher order conditioning state is child conditioning state10812, the lower magnitude of the two child conditioning states10812and11814into which parent conditioning state1710has been split. Conditioning state10812is not further split into child conditioning states, thus a nonsignificant enhancement bit862is inserted for conditioning state10812. By contrast, conditioning state11814is further split into child conditioning states110816and111818. Thus, a significant enhancement bit864is inserted for conditioning state11814. The child conditioning states110816and111818are not further split into child conditioning states, so nonsignificant enhancement bits866and868, are inserted for conditioning states110816and111818, respectively.

Thus, according to a mode of context model scaling, a set of enhancement bits to scale previous context model700to next context model800begins with the starting conditioning state and continues through the higher order and higher magnitude conditioning states. This is the same order in which the enhancement bits were previously identified with reference toFIGS. 7 and 8. In order, the enhancement bits are presented in order in Table (1). The reference numerals fromFIG. 8are included (in parentheses) for clarity:

TABLE 1Conditioning StateEnhancement Bit00 (702)0 (852)01 (704)1 (854)010 (806)0 (856)011 (808)0 (858)1 (710)1 (860)10 (812)0 (862)11 (814)1 (864)110 (816)0 (866)111 (818)0 (868)
Thus collecting the enhancement bits from Table (1) in order, a set of enhancement bits to scale the previous context model to the next context model, the set of enhancement bits is 010010100. The next context model thus is representable by this series of nine bits, instead of by an entire additional context model.

If the next context model800included different conditioning states, the resulting sets of enhancement bits would be different. For sake of example, if conditioning state11814were not further split into child conditioning states110816and111818, the significant enhancement bit864would be replaced by a nonsignificant enhancement bit and there would be no higher order child conditioning states for which enhancement bits would be generated. Thus, replacing the significant enhancement bit864with a nonsignificant enhancement bit, and truncating the last two enhancement bits, the set of enhancement bits would be 0100100. For another example, if the starting conditioning states00702were split into child conditioning states, the nonsignificant enhancement bit0852would be replaced by a significant enhancement bit, and nonsignificant enhancement bits would be inserted after that significant enhancement bit for each of its child conditioning states. Thus, the set of enhancement bits would be 10010010100.

It should be noted that, the more conditioning states that are added between a previous conditioning state and a next conditioning state, the more enhancement bits there will be. Nonetheless, the additional enhancement bits consume less storage than including the additional conditioning states themselves. In addition, as previously described, the mode of generating enhancement bits described with reference toFIGS. 6,7and8is just one mode of generating enhancement bits, and different protocols, such as by using symbols for representing splits, proceeding in a different order, and other variations may be used.

Scaling a Previous Context Model Using Enhancement Bits

FIG. 9illustrates a process900for scaling a context model using enhancement bits provided in a scalable context model. The process900is an iterative process usable to scale each of a plurality of context models to a next higher order model, such as for a next higher bit rate.FIGS. 10 and 11provide an example of an iteration of scaling a lower order context model1000to a higher order context model1100using a set of enhancement bits. For sake of further illustration, the examples of the lower order context model1000and higher order context model1100are different than those used in the example illustrated inFIGS. 7 and 8.

Referring toFIG. 9, at902, a scalable context model, including a basic context model and one or more sets of enhancements bits, is received for possible use in decoding a data file. At904, the process900begins with the basic context model which, as previously described, is the context model generated for coding and decoding a source at the lowest anticipated bit rate.

At906, it is determined if the current context model is adapted for decoding the data at the appropriate bit rate. If so, the process900advances to922to decode the data using the current context model. On the other hand, if the current context model is not scaled for the appropriate bit rate, at908, the next set of enhancement bits is accessed. At910, scaling according to the enhancement bits begins with the first enhancement bit in the set of enhancement bits and the starting conditioning state, as previously described in connection withFIG. 6.

At912, it is determined if the current enhancement bit is significant or nonsignificant as previously described. If the bit is significant, at914, the current conditioning state is split into its child conditioning states. In one mode, the child conditioning states are arrayed from lower magnitude to higher magnitude values.

Once the conditioning state is split at914, or if it was determined at912that the enhancement bit was nonsignificant, at916, it is determined if all the enhancement bits in the current set have been processed, which indicates that all the conditioning states in the current context model have been scaled for the next bit rate. If not, at918, the next conditioning state and enhancement bit are selected and the process loops to912to evaluate the current enhancement bit. As previously described, in one mode, a next conditioning state is a next higher order conditioning state or a next higher magnitude conditioning state. However, also as previously described, as long as the encoder and decoder observe the same protocol, a different processing order may be selected.

On the other hand, if it is determined at916that all the enhancement bits in the set have been processed, the context model has been fully scaled to a next context model for a next higher bit rate. Thus, at920, the next, scaled content model becomes the current context model. At906, it is determined if the current context model is adapted for the appropriate bit rate. If so, the process advances to922to decode the data using the current context model. On the other hand, if the current context model still is not scaled to the appropriate bit rate, at908, the next set of enhancement bits is accessed to further scale the context model. The process900thus repeats until the appropriate context model is generated.

To illustrate the scaling process,FIG. 10presents an exemplary scalable context model1000. The scalable context model1000, as previously described with reference toFIG. 2, includes a basic context model1010for a lowest anticipated bit rate and one or more sets of enhancement bits1020to scale the basic context model to a context model for an appropriate bit rate. The exemplary basic context model1010includes two conditioning states, conditioning state01012and11014. The enhancement bits1020includes a single set of enhancement bits, 11000100. For clarity, the enhancement bits are delineated into a sequence in Table (2) with reference numbers used inFIG. 11to clarify the application of each of the bits:

In scaling the basic context model1010to the next context model1100, the starting conditioning state again is the highest order, lowest magnitude conditioning state which, in this example, is conditioning state01012. The first enhancement bit is a significant bit11102, indicating that conditioning state01012is split into child conditioning states001152and011160. The enhancement bit set has not been exhausted, thus a next conditioning state and a next enhancement bit are evaluated. The next conditioning state is conditioning state001152, the lower magnitude conditioning state of the two higher order child conditioning states of conditioning state01012, according to the protocol used in generating the enhancement bits. The second enhancement bit, enhancement bit11104, is a significant bit. Thus, conditioning state001152also is split into its two child conditioning states, conditioning states0001156and0011158.

The set of enhancement bits is not exhausted. Thus, the next conditioning state, child conditioning state0001156, is the next lowest magnitude, highest order conditioning state. The third enhancement bit, enhancement bit01106is nonsignificant. Thus, conditioning state0001156is not further split. The next conditioning state is conditioning state0011158, the higher magnitude child conditioning state of conditioning state001152. The fourth enhancement bit01108also is nonsignificant, thus, conditioning state0011158is not further split.

Additional enhancement bits remain to be processed. Thus, the next conditioning state is identified as conditioning state011160, next conditioning state of lowest magnitude and highest order, and which was added by the split of conditioning state01012based on the first enhancement bit11102. The fifth enhancement bit is enhancement bit01110. Because the bit is not significant, conditioning state011160is not split.

The next conditioning state, moving from left to right with reference toFIG. 11, is conditioning state11014. The sixth enhancement bit is enhancement bit11114, a significant bit indicating that conditioning state11014is split into child conditioning states101166and111168. The next conditioning state is the lower magnitude child conditioning state101166. The seventh enhancement bit is enhancement bit01116, a nonsignificant bit indicating no further split of the conditioning states. The next and final conditioning state is conditioning state111168, and the next and final enhancement bit is enhancement01118. Because the bit is nonsignificant, conditioning state111168is not split. The set of enhancement bits1020has now been exhausted, thus the context model1100is fully scaled to the next higher bit rate, and may be used to decode data encoded at that bit rate.

As described with reference toFIG. 9, if the scaled context model1100is not the appropriate context model for the bit rate, another set of enhancement bits would be accessed to further scale the context model. This process would repeat until the context model for the appropriate bit rate is scaled.

Scalable Context Quantization for Embedded Wavelet Coding

FIG. 12is a flow diagram of a process1200for performing scalable quantization for embedded wavelet coding. Embedded wavelet coding, to name one application, is used in scalable codestreams such as Joint Photographic Experts Group 2000 (“JPEG2000”) that allow for selectable access to content of the codestream at a range of access levels. In codestreams such as JPEG2000, bit plane coding is used. In bit plane coding, coefficients including a series of bits representing a multi-bit value are partitioned into bit planes according to the relative magnitude of each of the bits. A mode of scalable context quantization is well suited for use with codestreams employing embedded wavelet coding.

As is further explained below, in one mode, a set of context events includes bits in the same bit plane and for values for the same resolution, as well as bits in a next higher bit plane and for a value corresponding to a lower resolution of the data values. Selection of such a set of context events for discrete wavelet transformed image data facilitates coding efficiency because of the manner in which discrete wavelet transformed data is aligned.

At1202, data transformed using discrete wavelet transformation (DWT) and separated into a series of bit planes is received. At1204, a set of context events to be used in coding the data is selected. In a mode of coding, the set of context events includes context events representing values related to different image resolutions and different bit planes, as is further described below. At1206, according to one mode as also further described below, the selected context events are ordered to enhance coding efficiency.

At1208, coding begins with a most significant bit plane. At1210, a generalized context model is developed for the bit plane. As previously described, a generalized model may include all the potential conditioning states available for the set of context events selected using a context model tree as previously described. At1212, the conditioning states in the context model are quantized. As also previously described, the conditioning states may be quantized to reduce a higher order model to a lower order model when higher order conditioning states do not provide a desired compression gain over their parent conditioning states.

At1214, it is determined if the coefficient has first become significant in a previous bit plane. If so, the process1200advances to1228for a magnitude refinement pass, which is described further below. On the other hand, if it is determined at1214that the coefficient has not first become significant in a previous bit plane, at1216, it is determined if the coefficient has become significant in the current bit plane in what is termed a zero coding pass. If not, at1218, the coefficient is coded with a nonsignificant bit, and the process1200advances to1234to determine if all the bit planes have been encoded. This is termed a zero coding pass because a nonsignificant bit or 0 is encoded for each bit plane until a coefficient becomes significant in the current bit plane.

On the other hand, if it is determined at1216that the coefficient has become significant in the current bit plane, at1220, the coefficient is coded with a significant bit. Then, at1222, it is determined if the coefficient is positive in what is termed a sign coding pass. The sign coding pass is used to code the sign of the coefficient in association with a significant bit coded when a coefficient first becomes significant in the current bit plane. If the coefficient is not positive, at1224, the coefficient is further coded with a nonsignificant bit. On the other hand, if it is determined at1222that the coefficient is positive, at1226, the coefficient is further coded with a significant bit. Whether the coefficient is further coded with a nonsignificant bit at1224or a significant bit at1226, the process1200advances to1234to determine if all the bit planes have been encoded.

At1228, when it has been determined that the coefficient has become significant in a previous bit plane, it is determined if the coefficient is significant in the current bit plane in what is termed a magnitude refinement pass. As the name implies, the magnitude refinement pass further specifies the magnitude of the coefficient in the remaining, successively lower magnitude bit planes. If it is determined at1228that the coefficient is not significant in the current bit plane, at1230, the coefficient is coded with a nonsignificant bit using the quantized context model. On the other hand, if it determined at1228that the coefficient is significant in the current bit plane, at1232, the coefficient is coded with a significant bit using the quantized context model.

Once the coefficient has been coded with one or two bits based on whether the coefficient has become significant in a previous bit plane or in the current bit plane and whether the coefficient is positive or negative, at1234, it is determined if all bit planes have been encoded. If not, at1236, the process1200advances to the next lower magnitude bit plane and the process1200loops to1210to develop a context model for the next bit plane, and to repeat the coding process using the zero coding, sign coding, and magnitude refinement passes previously described. On the other hand, if it is determined at1234that all the bit planes have been encoded, the coding is complete and, at1238, the coded data is presented for storage or transmission.

Using the process1200, a single bit is coded for the coefficient in each bit plane except where the coefficient has first become significant in the current bit plane. When the coefficient first becomes significant in the current bit plane, the sign of the coefficient is also represented as positive or negative with an additional significant or nonsignificant bit, respectively. For all succeeding planes, the value of the coefficient is represented with a single bit using the respective quantized context model.

For example, a positive, eight-bit coefficient, 01100100, is considered. Beginning with the first, highest magnitude bit plane, at1214, it is determined that the coefficient has not become significant in a previous bit plane. Thus, at1216, it is determined that the coefficient is not significant in the current bit plane, and at1218, the coefficient is coded with a nonsignificant bit, “0.”

Advancing to the second bit plane, again at1214, it is determined that the coefficient has not become significant in a previous bit plane. However, at1216, it is determined that the coefficient has become significant in the current bit plane. Thus, at1220, the coefficient is coded with a significant bit and, once it is determined at1222that the coefficient is positive, at1226, the coefficient is further coded with a significant bit. Thus, the coefficient in the second bit plane is coded with a pair of bits, “11.”

Further advancing to the third bit plane, at1214, it is determined that the coefficient has become significant in a more significant bit plane. Thus, the process advances to1228to determine, in a magnitude refinement pass, that the coefficient is significant in the current bit plane. Thus, at1232, the coefficient is coded with a significant bit using the quantized context model, “1.” Once a coefficient has become significant in a previous bit plane, the process1200yields similar results for the remaining bit planes. Thus, for the remaining five bit planes, the coefficient is coded with a “0,” a “0,” a “1,” a “0,” and another “0.”

Context Event Selection and Ordering to Improve Compression

As referenced in the process1200(FIG. 12), the context events may be selected and ordered in order to improve coding efficiency.FIGS. 13 and 14illustrate a set of context events selected for use with embedded wavelet coding sequenced in order to optimize coding efficiency.

FIG. 13illustrates a set of context events1300selected to optimize coding efficiency for bit plane coding of image data transformed by an embedded wavelet coder may be changed to improve coding efficiency.FIG. 13shows a set of 14 context events. The context events are drawn from different resolution levels and different bit planes. As is understood in the art, embedded wavelet coding applies coefficients to a varying series of wavelets that vary around a zero value to represent a time domain signal in a frequency domain. As a consequence, selecting context events from different bit planes and from different resolution levels results in conditioning states that provide good convergence and, thus, effective compression.

More specifically, the set of context events1300includes two context events from the next lower resolution level, eight context events from the same resolution level and the next more significant bit plane, and four context events from the same resolution level and the same bit plane. Context event c11312, is the value of the corresponding pixel from a next lower resolution level in the next more significant bit plane1310. Context event c2 1322is the value of the corresponding pixel from the next lower resolution level and the current bit plane1320. Context events c31332, c41334, c51336, c61338, c71340, c81342, c91344, and c101346are the values of the eight surrounding pixels at the same resolution level in the next more significant bit plane1330. Context events c111352, c121354, c131356, and c141358are the values from four neighboring pixels to the current value c1360at the same resolution level in the same bit plane1350. The set of fourteen context events1300over these resolution levels in these bit planes presents a set of effective conditioning states.

Conventionally, context events may be sequenced according to distance between the context pixel and the pixel being encoded. For example, distance-based sequencing is suitable for bi-level image coding, where the context events are of the same resolution and in the same bit plane as the value being encoded. However, in other forms of coding, such as continuous-tone image coding, context events may be selected from other resolution levels and other bit planes. When context events are selected from different resolution levels and bit planes, distance to the value being coded is not a meaningful measure to use in sequencing the context events.

According to one mode, the context events are sequenced to minimize the resulting entropy. To minimize entropy, a greedy algorithm may be used. The following is one suitable, exemplary algorithm, where i is an order index, H(A|B) is the conditional entropy, C is the selected context, and IĈis a remaining set of events once one or more of the context events have been removed from the full set of events. Initially, i is equal to 1, C=φ, and IĈcontains all N context events in the algorithm:

While IĈ≠φ{find cxfrom IĈthat minimizes H(Y|Ccx);set order i to cx;C=Ccx;remove cxfrom IĈ;i++;}
The greedy algorithm determines how to order the selected context event to reduce conditional entropy.

Reducing the conditional entropy by using a process such as the foregoing greedy algorithm, the fourteen context events in the set of context events1300(FIG. 13) is resequenced to present the set of context events1400shown inFIG. 14. As a result of the resequencing, context event c11412again is the value of the corresponding pixel from a next lower resolution level in the next more significant bit plane1410. However, context event c21452is a value of a neighboring pixel, at the same resolution level and in the same bit plane as the current value c1460, in the preceding row and same column. Context event c3is the value of the corresponding pixel in next lower resolution level and the current bit plane1420. Context event c41432is the value of a pixel from the preceding row and the same column at the same resolution level in the next more significant bit plane1430, while context event c51434is the value of a pixel in the following row and the same column at the same resolution level in the next more significant bit plane1430.

Context event c61454is a neighboring pixel in the same row and a preceding column at the same resolution level and in the same bit plane. Context event c7, however, is the neighboring pixel in the same row and a preceding column of the same resolution level in a next more significant bit plane. Moving back to the same resolution level and the same bit plane, context event c81456is a value of a neighboring pixel in a preceding row and a next column, and context event c91456is the value of a neighboring pixel in a preceding row and a preceding column.

Changing bit planes again, however, context event c10is the value of a neighboring pixel in the same row and a following column for the same resolution level in a next more significant bit plane1430. Staying at the same resolution level and in the next more significant bit plane, context event c111440is the value of a neighboring pixel in a next row and a next column, and context event c12is a value of a neighboring pixel in a next row and a preceding column. Context event c131444is a value of a neighboring pixel in a preceding row and a next column, and, finally, context event c141446is a value of a neighboring pixel in a preceding row and a preceding column. Ordering the conditioning states from c1through c14yields conditioning states that minimize the conditional entropy to improve coding efficiency.

Computing System for Implementing Exemplary Embodiments

FIG. 15illustrates an exemplary computing system1500for implementing embodiments of scalable context quantization. The computing system1500is only one example of a suitable operating environment and is not intended to suggest any limitation as to the scope of use or functionality of exemplary embodiments of the scalable context quantization process previously described or other embodiments. Neither should the computing system1500be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary computing system1500.

The scalable context quantization process may be described in the general context of computer-executable instructions, such as program modules, being executed on computing system1500. Generally, program modules include routines, programs, objects, components, data structures, etc., that perform particular tasks or implement particular abstract data types. Moreover, those skilled in the art will appreciate that the scalable context quantization process may be practiced with a variety of computer-system configurations, including hand-held devices, multiprocessor systems, microprocessor-based or programmable-consumer electronics, minicomputers, mainframe computers, and the like. The scalable context quantization process may also be practiced in distributed-computing environments where tasks are performed by remote-processing devices that are linked through a communications network. In a distributed-computing environment, program modules may be located in both local and remote computer-storage media including memory-storage devices.

With reference toFIG. 15, an exemplary computing system1500for implementing the scalable context quantization process includes a computer1510including a processing unit1520, a system memory1530, and a system bus1521that couples various system components including the system memory1530to the processing unit1520.

Computer1510typically includes a variety of computer-readable media. By way of example, and not limitation, computer-readable media may comprise computer-storage media and communication media. Examples of computer-storage media include, but are not limited to, Random Access Memory (RAM); Read Only Memory (ROM); Electronically Erasable Programmable Read Only Memory (EEPROM); flash memory or other memory technology; CD ROM, digital versatile discs (DVD) or other optical or holographic disc storage; magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices; or any other medium that can be used to store desired information and be accessed by computer1510. The system memory1530includes computer-storage media in the form of volatile and/or nonvolatile memory such as ROM1531and RAM1532. A Basic Input/Output System1533(BIOS), containing the basic routines that help to transfer information between elements within computer1510(such as during start-up) is typically stored in ROM1531. RAM1532typically contains data and/or program modules that are immediately accessible to and/or presently being operated on by processing unit1520. By way of example, and not limitation,FIG. 15illustrates operating system1534, application programs1535, other program modules1536, and program data1537.

The computer1510may also include other removable/nonremovable, volatile/nonvolatile computer-storage media. By way of example only,FIG. 15illustrates a hard disk drive1541that reads from or writes to nonremovable, nonvolatile magnetic media, a magnetic disk drive1551that reads from or writes to a removable, nonvolatile magnetic disk1552, and an optical-disc drive1555that reads from or writes to a removable, nonvolatile optical disc1556such as a CD-ROM or other optical media. Other removable/nonremovable, volatile/nonvolatile computer-storage media that can be used in the exemplary operating environment include, but are not limited to, magnetic tape cassettes, flash memory units, digital versatile discs, digital video tape, solid state RAM, solid state ROM, and the like. The hard disk drive1541is typically connected to the system bus1521through a nonremovable memory interface such as interface1540. Magnetic disk drive1551and optical dick drive1555are typically connected to the system bus1521by a removable memory interface, such as interface1550.

The drives and their associated computer-storage media discussed above and illustrated inFIG. 15provide storage of computer-readable instructions, data structures, program modules and other data for computer1510. For example, hard disk drive1541is illustrated as storing operating system1544, application programs1545, other program modules1546, and program data1547. Note that these components can either be the same as or different from operating system1534, application programs1535, other program modules1536, and program data1537. Typically, the operating system, application programs, and the like that are stored in RAM are portions of the corresponding systems, programs, or data read from hard disk drive1541, the portions varying in size and scope depending on the functions desired. Operating system1544, application programs1545, other program modules1546, and program data1547are given different numbers here to illustrate that, at a minimum, they can be different copies. A user may enter commands and information into the computer1510through input devices such as a keyboard1562; pointing device1561, commonly referred to as a mouse, trackball or touch pad; a wireless-input-reception component1563; or a wireless source such as a remote control. Other input devices (not shown) may include a microphone, joystick, game pad, satellite dish, scanner, or the like. These and other input devices are often connected to the processing unit1520through a user-input interface1560that is coupled to the system bus1521but may be connected by other interface and bus structures, such as a parallel port, game port, IEEE 1394 port, or a universal serial bus (USB)1598, or infrared (IR) bus1599. As previously mentioned, input/output functions can be facilitated in a distributed manner via a communications network.

A display device1591is also connected to the system bus1521via an interface, such as a video interface1590. Display device1591can be any device to display the output of computer1510not limited to a monitor, an LCD screen, a TFT screen, a flat-panel display, a conventional television, or screen projector. In addition to the display device1591, computers may also include other peripheral output devices such as speakers1597and printer1596, which may be connected through an output peripheral interface1595.

The computer1510will operate in a networked environment using logical connections to one or more remote computers, such as a remote computer1580. The remote computer1580may be a personal computer, and typically includes many or all of the elements described above relative to the computer1510, although only a memory storage device1581has been illustrated inFIG. 15. The logical connections depicted inFIG. 15include a local-area network (LAN)1571and a wide-area network (WAN)1573but may also include other networks, such as connections to a metropolitan-area network (MAN), intranet, or the Internet.

When used in a LAN networking environment, the computer1510is connected to the LAN1571through a network interface or adapter1570. When used in a WAN networking environment, the computer1510typically includes a modem1572or other means for establishing communications over the WAN1573, such as the Internet. The modem1572, which may be internal or external, may be connected to the system bus1521via the network interface1570, or other appropriate mechanism. Modem1572could be a cable modem, DSL modem, or other broadband device. In a networked environment, program modules depicted relative to the computer1510, or portions thereof, may be stored in the remote memory storage device. By way of example, and not limitation,FIG. 15illustrates remote application programs1585as residing on memory device1581. It will be appreciated that the network connections shown are exemplary, and other means of establishing a communications link between the computers may be used.

Although many other internal components of the computer1510are not shown, those of ordinary skill in the art will appreciate that such components and the interconnections are well-known. For example, including various expansion cards such as television-tuner cards and network-interface cards within a computer1510is conventional. Accordingly, additional details concerning the internal construction of the computer1510need not be disclosed in describing exemplary embodiments of the scalable context quantization process.

When the computer1510is turned on or reset, the BIOS1533, which is stored in ROM1531, instructs the processing unit1520to load the operating system, or necessary portion thereof, from the hard disk drive1541into the RAM1532. Once the copied portion of the operating system, designated as operating system1544, is loaded into RAM1532, the processing unit1520executes the operating system code and causes the visual elements associated with the user interface of the operating system1534to be displayed on the display device1591. Typically, when an application program1545is opened by a user, the program code and relevant data are read from the hard disk drive1541and the necessary portions are copied into RAM1532, the copied portion represented herein by reference numeral1535.

CONCLUSION

Although exemplary embodiments have been described in language specific to structural features and/or methodological acts, it is to be understood that the appended claims are not necessarily limited to the specific features or acts previously described. Rather, the specific features and acts are disclosed as exemplary embodiments.