Methods and apparatus for progressive transmission of subband images

[0001] This application claims priority to U.S. Provisional Application No. 60/126,259; filed Mar. 25, 1999.

[0002] The invention relates to image compression techniques, being exploited for transmission (or storage) of images.

General

[0003] MPEG-4 and JPEG2000 prerequisites hold concepts like graceful degradation and scalability, implemented in progressive transmission schemes. When transmitting image information over a communication channel, the sender is often not aware of the properties of the output devices such as display size and resolution, and the present requirements of the user—for example when he is browsing through a large image database. To support the large spectrum of image and display sizes and resolutions, the coded bit stream must be formatted in such a way that whenever the user or the receiving device interrupts the bit stream, a maximal display quality is achieved for the given bit rate. The progressive transmission paradigm incorporates that the data stream should be interruptible at any stage and still deliver at each breakpoint a good trade-off between reconstruction quality and compression ratio.

[0004] The classic block-based compression techniques (JPEG, MPEG-1, MPEG-2, H.263 . . . ), based on the decorrelating discrete cosine transform, hardly meet these requirements, since information is transmitted on a block basis. Interrupting the bit stream results in a partially reconstructed image, leaving the non-transmitted image part undefined. Additionally, since they are strictly block-based, disturbing block artifacts reduce the visual perception quality.

[0005] Wavelet transform based compression schemes avoid the above-mentioned problems since their data path is such that several image resolutions are obtained throughout the coding process (FIG. 1). Transmitting successively all the subbands (also denoted subband images or sub-images), starting with the average sub-image in the top left corner, already fulfils the graceful degradation requirement (FIG. 2). Of course, the relation between the compression ratio and the image reconstruction quality in this subband-by-subband image scanning approach can hardly be called optimal, there all subbands—each with their own weight—contribute to the final quality of the decoded image. For example, the least significant bit-plane of the average subband might for this criterion be less important then for instance the third bit-plane of the first LH-subband.

[0006] Note that although the wavelet transform is a particular method, which can be exploited for subband image encoding, and that the invention is illustrated for wavelet-transformed images, the invention is not limited hereto.

[0007] State of the art image compression techniques based on subband coding, typically exploit in their quantization and entropy coding steps the preservation of frequency and spatial information. They (e.g. wavelet transform) deliver in the transform domain information concerning the frequencies present at a specific spatial location. Hence, the quantization and entropy coding parts can exploit both the dependency between spatially neighboring pixels in one subband and the dependency between pixels in different subbands at corresponding spatial locations in a rate-distortion sense. Typically the first approach is addressed as intra-subband coding (e.g. quad-tree-based [J. Cornelis, A. Munteanu, A. Salomie, P. Schelkens, R. Deklerck, Y. Christophe and V. Enescu, “Medical Image Compression: Options for the Future”, Proceedings of Biosignal '98, pp. 1-12, 1998]], the latter as inter-subband coding (embedded zero-tree coding [J. M. Shapiro, “Embedded Image Coding Using Zero-trees of Wavelet Coefficients”, IEEE Transactions on Signal Processing, Vol. 41, no.12, pp.3445-3462, 1993] and SPIHT[A. Said and W. Pearlman, “A new fast and efficient image codec based on set partitioning in hierarchical trees”, IEEE Trans. on Circuits and Systems Video Technology 6 (1996) 243-250.]). Both intra-subband and inter-subband approaches successively approximate the subband coefficients by starting with the coarsest refinement level (i.e. most significant bit-plane) and ending at a refinement level needed to obtain the requested compression ratio (or required image quality). Refinement levels are also denoted quantization levels and the quantization approach is referred to as successive approximation quantization (SAQ). Remark that each bit-plane is completely scanned before the processing of another one is started. These methods thus exploit a quantization level-by-quantization level scanning method as opposed to a subband-by-subband scanning approach. With the quantization level-by-quantization level scanning method one is capable of coarsely approximating the optimal rate-distortion behavior when all required bits are transmitted while performing an appropriate thresholding to obtain the required compression quality. However, if the bit-stream is interrupted at an earlier stage in the transmission the obtained rate-distortion is far from satisfactory due to the bad weighting of the information in the different subbands: relatively seen we have transmitted too much information of one subband compared to another subband. Thus, a correct thresholding was not obtained.

Embedded Zero-tree Coding

[0008] Since, the invention is further illustrated for embedded zero-tree encoding, we will first discuss this coding approach. However, we have to stress that the invention is not limited hereto, and is applicable to all SAQ-based compression schemes.

[0009] By carefully studying the redundancy between spatially corresponding pixels of the different subbands, a remarkable coherence was revealed. J. Shapiro figured out that exploiting this property enhances the compression performance [J. M. Shapiro, “Embedded Image Coding Using Zero-trees of Wavelet Coefficients”, IEEE Transactions on Signal Processing, Vol. 41, no.12, pp.3445-3462, 1993.]. He considered the relation between spatially related pixels of different subbands as parent-children links. In the context of a N-level discrete wavelet transform, this means that a pixel in a level l sub-image (either LH, HL or HH) corresponds spatially to four pixels in the level l−1 sub-image with the same type of frequency constellation, i.e. LH, HL or HH. The inter subband correlation is exploited using the fact that the probability is rather high that magnitudes of the child pixel values are smaller than a certain threshold, whenever the parent's magnitude value is smaller than that threshold. This means that all the pixels of the same spatial locality can be coded in one step i.e. zero-tree coding. Within this scalar quantization method the comparison is performed with a threshold corresponding to the bit-planes (also denoted quantization levels). Thus, progressive transmission capabilities are an inherent property of the coding scheme, i.e. gradually refining the threshold levels (e.g. coding from the most significant bit-plane towards the least significant bit-plane) and respecting the order of importance of the subbands (FIG. 3). This way of image scanning rules out the objections against classic schemes (FIG. 2).

[0010] Since the embedded zero-tree wavelet encoding technique proposed by J. Shapiro utilizes scalar quantization, it partially fails to recognize spatial structures within the subbands, i.e. spatial redundancy. To overcome this shortcoming a progressive vector quantization based embedded zero-tree coding was introduced by E. da Silva [E. A. B. da Silva, “Wavelet Transforms for Image Coding”, PhD Dissertation, University of Essex, England, 1995.]. The significance of an image vector—composed out of a set of neighboring pixels—is evaluated by comparing the magnitude of that vector with a yardstick value, i.e. a vector threshold. This value allows layering the subbands similarly to the bit-plane concept in the scalar case (FIG. 3). As such this vector quantization also defines quantization levels. The vector codebook consists out of a set of normalized lattice-based directional code vectors.

[0011] As said in the introduction, a straightforward implementation of the above mentioned quantization level-by-quantization level scanning methods ([J. M. Shapiro, “Embedded Image Coding Using Zero-trees of Wavelet Coefficients”, IEEE Transactions on Signal Processing, Vol. 41, no.12, pp.3445-3462, 1993.], [E. A. B. da Silva, “Wavelet Transforms for Image Coding”, PhD Dissertation, University of Essex, England, 1995.]) does not lead to maximal coding performance, since both methods give the same weight to the information present in the different subbands. Thus, thresholding has to be introduced.

[0012] Practice indicates that the subbands do have a different energy and bit-range. The energy differences suggest that the information content of the different subbands is heterogeneous. It is therefore advisable to privilege the subbands with the highest energy. Applying subband dependent hard thresholding in a lossy compression scheme allows privileging the subband with the highest energy (FIG. 4). To find suitable threshold levels for each subband, we have to minimize the quantization error D(b) subject to the total bit-rate R_q(b), where the vector b represents the bit-rates allocated to the different subbands [G. Strang, T. Nguyen, “Wavelets and Filter Banks”, Wellesley-Cambridge Press, Wellesley, USA, 1996]. The bit-rate is an indication of the number of bits that is being considered for compression, it does not reflect the effective rate obtained after arithmetic encoding, being part of further coding steps. $\begin{array}{cc}D\left(b\right)=\sum _{k=1}^M{\alpha }_k{\omega }_k{2}^{-2b_k}{\sigma }_k^2& \left(1\right)\\ R_q\left(b\right)=\sum _{k=1}^M{\alpha }_k{b}_k& \left(2\right)\end{array}$

[0013] M represents the total number of subbands, α_k is the relative subband size, ω_k is the perceptual weighting factor, and σ_k² the subband variance. The latter is a good representative of the subband energy. Remark that while the low pass image at the highest wavelet level has a Gaussian distribution, the high pass images do have a Laplacian distribution. Assuming we want to obtain a certain fixed bit-rate R_q,c, minimizing D(b) can be solved by applying a method based on Lagrange multipliers: $\begin{array}{cc}\sum _{k=1}^M\frac{\partial }{\partial b_k}\left[D\left(b\right)+\lambda \left(R_q\left(b\right)-R_{q,c}\right)\right]=\sum _{k=1}^M\frac{\partial }{\partial b_k}\left[{\alpha }_k\left({\omega }_k{2}^{-2b_k}{\sigma }_k^2+\lambda b_k\right)\right]=0& \left(3\right)\end{array}$

[0014] The differentiation with respect to b_k delivers then: $\begin{array}{cc}{b}_k=\frac{1}{2}{\log }_2\frac{\left(2\ln 2\right){\omega }_k{\sigma }_k^2}{\lambda }& \left(4\right)\end{array}$

[0015] The fixed bit-rate constraint R_q,c poses: $\begin{array}{cc}\sum _{k=1}^M{\alpha }_k{b}_k=\frac{1}{2}\sum _{k=1}^M{\alpha }_k{\log }_2\frac{\left(2\ln 2\right){\omega }_k{\sigma }_k^2}{\lambda }=R_{q,c}& \left(5\right)\end{array}$

[0016] This yields then the Lagrange multiplier λ: $\begin{array}{cc}\lambda =2^{\sum _{k=1}^M{\alpha }_k{\log }_2\left[\left(2\ln 2\right){\omega }_k{\sigma }_k^2\right]-2R_{q,c}}& \left(6\right)\end{array}$

[0017] Equations (4) and (6) provide the bit lengths b_k. For small variances the results can be negative, and therefore they should be truncated to zero. The calculations have then to be repeated for a reduced number of subbands—ignoring the insignificant ones—until all b_k are bigger or equal to zero, and adjusting the fixed bit-rate to: $\begin{array}{cc}{R}_{q,c}=\sum _{k=1}^M{\alpha }_k{b}_k& \left(7\right)\end{array}$

[0018] The perceptual weighting factors ω_k are weighing the different subbands in such a way that the visual perception of the image is optimized.

[0019] Although the described subband dependent hard thresholding (FIG. 4) allows privileging the subband with the highest energy, it still works in a quantization level-by-quantization level scanning manner.

[0020] The invention aims at presenting a new scanning method through a subband encoded image (e.g. wavelet transformed image) which should retain the intrinsic capacity to continue coding When the transmission channel is not saturated or when devices with different resolutions are mounted to the communication channel. The transmission scheme should have inherent graceful degradation capabilities and should ensure an optimal trade-off between the image reconstruction quality and the compression ratio.

[0021] In the invention a method for progressive transmission of encoded images is presented.

[0022] Said image can be an individual image or being part of a sequence of images. An image is represented in a digital system as an array of pixels. Said image is stored in a memory of said digital system. From a programming point of view an image can be considered as a two-dimensional data type, although said image is not necessarily rectangular.

[0023] An image can be considered as a digital representation of a natural and/or synthetic scene (e.g. a photo) or a still image from a video recorded scene. Such an image can however have been transformed into another digital representation, from which the related reality cannot be retrieved by the human means only.

[0024] The invented progressive transmission method exploits subband transformed images. A subband-transformed image comprises a set of subband images.

[0025] As in digital processing finite word length is exploited, quantization is necessary. Such a quantization can be performed on the pixel level, meaning that for each of the pixels a set of bits is assigned and based on the value of a pixel said bits are being set to one or zero. Such a quantization can be performed on a group of pixels also. Due to quantization, quantization levels (yardsticks, bit-planes) are defined.

[0026] When one wants to transmit an entropy encoded subband transformed image from a first digital system to a second digital system, one has to select a scanning method being the ordering in which bits, representing said image in said first digital system, are grouped, encoded and transmitted, possibly after some further coding.

[0027] In the prior art a first scanning curve, scanning the subband transformed image, in a subband-by-subband manner, meaning processing all bits (all quantization levels) of a subband before processing another subband's bits, is disclosed. The ordering of the subbands is predetermined. The ordering of the quantization levels is typically from the most significant quantization level to the lowest significant quantization level. After processing, the produced data can be reordered. However, bits in different subbands are independently encoded. This scheme is only applicable for intra-subband encoding techniques.

[0028] In the prior art a second scanning curve, scanning the subband transformed image, in a specific quantization level-by-quantization level manner, meaning processing all bits of all subbands of the same quantization level before processing another quantization level bits, is disclosed. The ordering of the subbands is predetermined. The ordering of the quantization levels is typically from the most significant quantization level to the lowest significant quantization level.

[0029] In the invention a scanning curve, is disclosed for scanning the subband transformed image in another quantization level-by-quantization level like manner, such that at least bits of a first subband in a quantization level, said level being specified for said first subband, and bits of a second subband in a quantization level, said level specified for said second subband, are together processed, meaning together encoded. The choice of the specific quantization level of each subband, of which the bits are encoded together, is such that at least two of said subbands have a different quantization level. The ordering of the subbands and the associated quantization level is predetermined by the scanning curve. The ordering of quantization levels for each subband with the scanning curve is typically from the most significant quantization level to the lowest significant quantization level. This approach includes that inter-pixel dependencies can be exploited across different quantization levels and subbands.

[0030] The invented image scanning method can be exploited for subband transformed images based on wavelet transforms, but is not limited hereto.

[0031] It can be stated that the invention presents a new scanning curve through the data (pixels, bits) representing a subband-transformed image. The scanning curve results in a specific scanning pattern over the different subbands and the different quantization levels.

[0032] The transmission scheme, exploiting the invented image scanning method has inherent graceful degradation capabilities and ensures an optimized trade-off between the image reconstruction quality and the compression ratio. The latter is not evident since hard thresholding is required to meet this requirement for a specific PSNR requirement. This scanning method is applicable on both scalar (pixel based) and vector (grouping of pixels) quantization based schemes but is not limited hereto. Additionally, it is applicable on all mentioned SAQ techniques, thus both intra-subband and inter-subband entropy encoding techniques.

[0033] In all the scanning methods found in the prior art, further coding (entropy coding) is performed by evaluating the bit characteristics over all subbands, either by comparing at an identical quantization level neighboring pixels in the subband transformed image (the pixels can be positioned in different subbands with e.g. the Mallat organization [S. Mallat, “A Theory for Multiresolution Signal Decomposition: The Wavelet Representation”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.11, No.7, pp. 674-693, 1989.]), either by exploiting the dependency between spatially related pixels in different subbands (e.g. zero-trees) at identical quantization levels.

[0034] It is an aspect of the invention to recognize that a particular scanning curve is needed to have a more optimal relation between the quality of the reconstructed image and the compression ratio.

[0035] In the invented scanning method the encoding is performed over different quantization levels, i.e. dependencies are exploited by comparing the bit values in the different subbands at different quantization levels. The approximation error tolerated in each subband is determined by a bit allocation process, using image (or subband) parameters (e.g. variance) as indicating parameters, possibly combined with perceptual weighting factors (indicating the visual importance of the subband, i.e. a subjective parameter). Further coding (e.g. zero-tree coding) can be performed simultaneously with scanning. It must be emphasized that the invention performs an optimization of the quality of the reconstructed image and the compression ratio, which is embedded with the encoding. No preprocessing of the image is needed. This is in contrast with visual frequency weighting, wherein wavelet coefficients are rescaled with visual weighting factors before being quantized and encoded.

[0036] The invention thus results in a progressive, graceful enhancement of the decoded image due to the optimal embedded bit-stream characteristics.

[0048] The invention deals with images. Said images are subband transformed and thus within said images a plurality of subband images can be distinguished. An image, thus also each subband, comprises of a plurality of pixels. Pixels are represented by a plurality of bits; each of said bits is associated to a certain quantization level.

[0049] The invention presents methods and an apparatus implementing these methods for encoding an image. Encoding of an image requires scanning essentially all bits of essentially all pixels of said image and while scanning in a particular scanning order one exploits dependencies within groups of bits consecutively scanned for encoding them. Thus said bits of said groups are encoded together.

[0050] In a subband transformed image, the scanning order or scanning curve is defined by indicating in which order one traverse the several subbands and the several quantization levels.

[0051] The invented encoding method is characterized in that in the set of scanned bits, which will be encoded together, and which form thus a group, bits of at least two different sub-images and at least two different quantization levels are recognized.

[0052] It must be emphasized that in the prior-art disclosed subband by subband scanning is presented. Bits within one subband are encoded together in such an approach. No encoding, such that dependencies of bits of different subband images are exploited, is shown. In the prior-art also a quantization level by quantization level scanning is presented. Bits within one quantization level are encoded together in such an approach. No encoding such that dependencies of bits of different quantization levels are exploited, is disclosed.

[0053] The invented encoding method is part of a progressive transmission approach. While transmitting from the transmitting peer to a receiving peer (or a plurality of receiving peer) the decoding resources at the receiving peer are not always known. A progressive transmission approach guarantees that the decoding of the encoded bit-stream results in a continuously improving quality of the decoded image as the transmission and decoding continues. Such a progressive transmission approach relies on the encoding method used in the transmitting peer. More in particular the encoding method must select the grouping of bits to be encoded together in a particular way.

[0054] The invented method exploits the fact that quality of the decoded image relies on bits of different sub-images and bits of different quantization levels. One can state that the invented method selects its scanning curve such that a progressive transmission method is enabled. One can define for the decoded image the quality levels to be obtained after transmitting an amount of bits. For each discrete value of the quality level, a particular group of bits, to be encoded together, is uniquely assigned. One can state that the invented method groups bits of at least two different subbands and at least two different quantization in each group and further performs an ordering of said groups according to the quality level that will be obtained when the groups being transmitted are received at the decoding receiving peer. The invented method encodes (and also transmits) said encoded bits according to the quality ordering, meaning that the group of bits contributing the most to the quality of the decoded image are encoded and transmitted first.

[0055] Note that while encoding said groups of bits intra-subband coding or known inter-subband coding techniques can be used.

[0056] The flowchart of the described invention is depicted in FIG. 5. FIG. 6 illustrates such a process. The bits of the different quantization levels are grouped to support six reconstruction quality levels. Each group is separately encoded and depending on the selected technique inter- and/or intra-subband dependencies are exploited within the group. Remark that these dependencies are exploited across different quantization levels. Additionally, we have to remark too that in the illustration encoding ended at quality level six. However, the technique does not prohibit to finally encode a quality level that gives support for lossless reconstruction.

[0057] In principle the invented encoding method will be privileging subbands with higher energy as hard thresholding techniques do, but it recognizes also the different importance of the quantization levels, which is not taken into account in the quantization level-by-quantization level scanning techniques. The invention is compatible with methods that apply perceptual weighting factors to different subbands. The invention can be characterized as a method wherein the visual perception of the decoded image is optimized by weighting both the different subbands and the different quantization levels. In the prior-art this optimization process is set-up in a context of a fixed bit-rate and in a quantization-by-quantization level approach. In the invention instead the optimization process works as follows: one starts with a minimal bit-rate and selects the optimal grouping of bits (across different subbands and across different quantization levels), to be encoded (while exploiting dependencies across said grouped bits) and transmitted such that a still optimal reconstruction at the receiving peer can be obtained, next one increases said bit-rate, and determines the next group of bits to be encoded and transmitted, and one continues this process until essentially all bits are considered. In an embodiment of the invention encoding of a set of bits is also considered.

[0058] The invented scanning method is valid for both scalar and vector quantization. The invention is illustrated for wavelet transformed images and embedded zero-tree coding but is not limited hereto, and addresses generally all subband transformed images.

[0059] The proposed method considers the coding boundaries between which the respective yardsticks (also denoted quantization levels) have to progress. A specific yardstick is defined for each sub-image (also denoted subband image). The lower boundaries of the yardstick variables are determined by the maximum required image quality and registered into the lower bound vector (FIG. 7). The initial values of the yardstick vector are defined by the initial bound. This initial yardstick vector should be parallel with the lower bound vector, which ensures that the coding process respects the subband hierarchy determined by the energies of the different subbands. Coding of a specific subband ends when the yardstick vector element equals the lower bound vector element. Pixel values or vector magnitudes are then treated as non-significant. It is important to remark that the parent-children relations are evaluated in the scanning process corresponding to the yardstick vector, containing for each subband the yardstick value for the current approximation step (FIG. 7). This means that the correlation is exploited between a parent at a certain yardstick value and a set of children at another yardstick value. Practice indicates that this does not lower the compression quality. Theoretically, this is easily explained considering the probabilities of zero-tree occurrence in the different sub-images and planes. These probabilities do increase when the considered yardstick level increases for the child's sub-image, which is usually the case (as shown in the example of FIG. 7). The original hard thresholding technique obtains an optimal coding performance when reaching the desired prefixed bit rate. However, when the bit stream is interrupted earlier, this requirement is not met, while the improved invented scanning curve will still satisfy this prerequisite. This is illustrated in FIG. 8, where three different hard thresholding levels (indexed 1, 2 and 3), each optimized for a certain bit-rate, are compared to the improved technique. Additionally, an upper coding bound is introduced by considering the dynamic ranges of the sub-images (FIG. 9).

[0060] This allows reducing the computational load. A subband is encoded if the yardstick vector element for the specified subband is smaller than or equal to the upper bound vector. If this is not the case, the vector magnitudes of the considered subband are treated as non-significant. Remark that it would be a bad strategy to equalize the initial subband yardsticks to the upper bounds, since the coding process would then neglect the energy hierarchy of the different sub-images. This would result in a lower probability of zero-tree occurrence.

[0061] Looking carefully to the previous proposed methods, one should notice a remarkable resemblance with the soft thresholding technique. This technique applies the following function as preprocessing step to the image:
p_k(i, j)=p_k(i, j)−sign [p_k(i, j)].T_k  (9)
with p_k(i,j) the pixel value on position (i,j) in subband k and T_k the respective threshold level. The principle is illustrated by FIGS. 10 and 11, the first representing the hard thresholding principle, the latter the corresponding soft thresholding output.

[0062] If one compares the soft thresholding scanning curve (FIG. 11) with the improved scanning curve (FIG. 7), which is obtained for the same compression situation, it is clear that both curves treat the subband data with identical priority: the coding order of the subband data is identical. Nevertheless, the improved progressive transmission is an embedded technique, while soft thresholding requires a preprocessing stage. Additionally, due to the removal of non-significant data in the preprocessing step, coding ends for the soft thresholding technique when meeting the lower coding bounds. For the improved technique coding can still go on. This is important, since it is not possible to predict the exact required threshold levels for a certain bit-rate. The quantization entropy-encoding step (e.g. zero-tree coding and arithmetic encoding) exploits dependencies between pixels, which are not predictable during the bit allocation process defining the threshold levels.

[0063] Additionally, the proposed method is also related to the scaling approach used in visual frequency weighing. Typically this technique is used to obtain an optimal visual reconstruction of the image for the targeted bit-rate and displaying circumstances, by taking into account the contrast sensitivity properties of the human visual system. When applying the derived visual weighing factors to the respective subbands the wavelet coefficients are altered. If an SAQ approach is then used to encode data a similar effect is obtained as with the proposed new scanning method. However, if visual progressive coding is desired (i.e. multiple sets of weighing factors are successively applied to have for example support for an heterogeneous set of displaying devices), it becomes very difficult—if not impossible—to use a system purely based on successively multiplying wavelet coefficients with the required visual weighting factors. This approach would result in multiple encoding of the same bits. Hence, the invention claimed in this document takes care of this problem in an elegant way. Preferably the scaling factors used in the invention are powers of two.

[0064] Remark that, in the presented embodiment of the invention, the low pass subband is not scanned. In contradiction to Shapiro's original implementation, in this embodiment a non-wavelet based lossless coding applies on the average subband. However, this is not relevant for the proposed invention.

[0065] It can be concluded that the proposed scheme improves the classic progressive SAQ schemes, since it combines both the progressive and the thresholding concepts without paying off on the reconstruction quality and compression ratio parameters (FIG. 2).

[0066] This general scheme is applicable in both scalar and vector embedded zero-tree wavelet coding schemes but not limited hereto. For example, the squares delineating the subband areas to be encoded with the quad-tree encoding technique can cover several subbands, and thus require the introduction of the above mentioned improvement to have a correctly weighted SAQ encoding, and consequently a fully embedded bit-stream.