Enhanced method and apparatus for image compression

Abstract

Described is a method of image compression and decompression involving a variable-to-variable coding scheme, for example as used or of similar nature to a HT Cleanup encoding algorithm, as described in ISO/IEC 15444-15:2019. The method involves a lookup table that the encoder addresses using a potentially modified version of the EMB pattern, a potentially modified version of the significance pattern, and any additional context information, in order to find the associated variable length codeword. The modified significance pattern and modified EMB pattern, each consisting of 1 bit per sample in a quad, implicitly identify the quad's original significance pattern and the quad's 1-bit unsigned residual offset value, together with some or all of the quad's original EMB pattern, both when the unsigned residual offset value is 1 and, for specific values of the significance pattern, when the unsigned residual offset value is 0.

Claims

1. A method of image compression involving a variable-to-variable coding scheme, whereby a variable number of bits are used to encode for each rectangular block of 4 samples, herein identified as a quad: i) a significance of each sample in the quad, herein identified as a significance pattern, comprising 4 bits with one bit for each sample in the quad indicating whether the sample in the quad is zero or non-zero; ii) a variable amount of information from a 4 bit EMB pattern for the quad, said EMB pattern consisting of the magnitude bits from each of the quad's samples that are found within a bounding magnitude bit-plane for the quad, said bounding magnitude bit-plane having the property that no samples of the quad have non-zero magnitude bits in any higher bit-plane; iii) a 1-bit unsigned residual offset value that indicates whether said bounding magnitude bit-plane is greater than a reference value or equal to the reference value, wherein the 1-bit unsigned residual value for the quad being 0 indicates the said bounding magnitude bit plane is equal to the reference value and the 1-bit unsigned residual value for the quad being 1 indicates the said bounding magnitude bit plane is greater than the reference value, said reference value depending on the sample values associated with previously encoded quads, the method involving a lookup table that an encoder addresses in order to find a suitable codeword from a context dependent variable length (CxVLC) code, wherein the CxtVLC code includes codewords that communicate EMB pattern information for specific values of a significance pattern for the quad when an unsigned residual offset value for the quad is 0, the method comprising the steps of: determining for the quad a modified significance pattern and a modified EMB pattern, each consisting of 1 bit per sample in the quad, based on the original significance pattern for the quad, the original EMB pattern for the quad, and the 1-bit unsigned residual offset value for the quad, the modified EMB pattern including some or all of the original EMB pattern for the quad both when the unsigned residual offset value is 1 and, for specific values of the significance pattern for the quad, when the unsigned residual offset value for the quad is 0, whereby the 8 bits of the modified significance and the modified EMB pattern infer the residual offset value for the quad, in addition to the original significance pattern for the quad, through transformations that exploit the property that whenever any EMB bit is 1, the corresponding significance bit must be 1.

2. The method of image compression of claim 1, wherein the CxtVLC code includes codewords that communicate EMB pattern information for specific values of a significance pattern for a quad when an unsigned residual offset value is 0.

3. The method of image compression of claim 1 wherein the modified significance and modified EMB pattern values identify the original EMB pattern when the unsigned residual offset value is 0 and all samples in the quad are significant.

4. The method of image compression of claim 2, where, for a quad, a modified EMB pattern and a modified significance pattern depend on whether or not the following three conditions hold: a) all samples in the quad are significant; b) the unsigned residual offset value for the quad is 0; and c) the original EMB pattern for the quad is non-zero; wherein (i) the modified EMB pattern is set to its original EMB pattern for the quad if the unsigned residual offset value for the quad is 1 or when all three conditions a), b), and c), hold, otherwise the modified EMB pattern is set to 0; and (ii) the modified significance pattern is set to 0 if all three conditions a), b), and c), hold, otherwise the modified significance pattern is the original significance pattern for the quad.

5. The method of image compression of claim 1, where the CxtVLC code includes multiple codewords for which the unsigned residual offset value is 0 and the bits of the significance pattern are all 1, indicating that all samples in the quad are significant, at least one such codeword serving to communicate EMB pattern information for the quad.

6. The method of image compression of claim 1 wherein, a modified EMB pattern for a quad is the same as an original EMB pattern for the quad, and a modified significance pattern for the quad is set to: a bit-wise exclusive OR of an original significance pattern for the quad and the original EMB pattern for the quad if the unsigned residual offset value for the quad is 0, or the original significance pattern for the quad otherwise.

7. The method of image compression as claimed in claim 1, wherein the method provides an extension of a HT Cleanup encoding algorithm in accordance with ISO/IEC 15444-15:2019.

8. A method of image decompression involving decoding compressed image data encoded using a variable-to-variable coding scheme, wherein a variable number of bits encode for each rectangular block of 4 samples herein identified as a quad: i) a significance of each sample in the quad, herein identified as a significance pattern; ii) a variable amount of information from a 4-bit EMB pattern for the quad, said EMB pattern consisting of the magnitude bits from each of the quad's samples that are found within a bounding magnitude bit-plane for the quad, said bounding magnitude bit-plane having the property that no samples of the quad have non-zero magnitude bits in any higher bit-plane; iii) a 1-bit unsigned residual offset value that indicates whether said bounding magnitude bit-plane is greater than a reference value or equal to the reference value, wherein the 1-bit unsigned residual value being 0 indicates the said bounding magnitude bit plane is equal to the reference value and the 1-bit unsigned residual value being 1 indicates the said bounding magnitude bit plane is greater than the reference value, said reference value depending on the sample values associated with previously encoded quads, the method involving a decoder addressing a lookup table that identifies the encoded codeword from a context-adaptive variable length code, herein known as the CxtVLC code, along with the significance pattern, unsigned residual offset value, and partial any EMB pattern information associated with that codeword, wherein at least one codeword in the CxVLC code serves to communicate magnitude exponent (EMB) pattern information for the quad, when the unsigned residual offset value is 0.

9. The method of image decompression as claimed in claim 8, wherein the method provides an extension of a HT Cleanup encoding and decoding algorithm in accordance with ISO/IEC 15444-15:2019.

Description

DETAILS OF THE PREFERRED EMBODIMENT

(1) Embodiments of the present invention relate to a modified coder implementation providing an extension for the High Throughput JPEG 2000 standard block coding algorithm described in the background section (the HTJ2K standard). Embodiments also provide an enhanced decoding method by virtue of the enhanced encoding.

(2) In the method of embodiments of this invention, an enhanced block encoder addresses the CxtVLC table using context c.sub.q, a modified significance pattern .sub.q, and a modified 4-bit pattern .sub.q, which are determined in such a way that the value of u.sub.q.sup.off is implied by .sub.q and .sub.q, while preserving all information in .sub.q and some or all of the information in .sub.q, both when u.sub.q.sup.off=1 and also when u.sub.q.sup.off=0 and .sub.q=15.

(3) Importantly, in this invention the encoder uses the same number of index bits to address the CxtVLC table as it did in the original HT block coding algorithm4 bits from .sub.q, 4 bits from .sub.q, plus the bits associated with the context c.sub.q. In this way, the enhancement of this invention can be obtained with almost no increase in implementation complexity.

(4) The decoding procedure is not actually changed at all by the method of this invention. CxtVLC decoding still produces values for .sub.q, u.sub.q.sup.off and the k.sub.n and i.sub.n values, from which the decoder knows the number of bits m.sub.n=.sub.n.Math.(U.sub.qk.sub.n) to unpack from the MagSgn bit-stream, combining them with .sub.n and i.sub.n to recover v.sub.n and thence .sub.n and s.sub.n. However, the CxtVLC table itself will be different, since it can now include codewords corresponding to u.sub.q.sup.off=0, in which one or more of the k.sub.n are non-zero.

(5) In a preferred embodiment, the encoder constructs .sub.q and .sub.q as follows:

(6) $\stackrel{=}{{}_q}=\{\begin{array}{cc}{}_q& \mathrm{if}{}_q=15\mathrm{and}{u}_q^{\mathrm{off}}=0\mathrm{and}{}_{q}0\\ u_q^{\mathrm{off}}.Math.{}_q& \mathrm{otherwise}\end{array}$$\stackrel{=}{{}_q}=\{\begin{array}{cc}0& \mathrm{if}{}_q=15\mathrm{and}{u}_q^{\mathrm{off}}=0\mathrm{and}{}_{q}0\\ {}_q& \mathrm{otherwise}\end{array}$

(7) This works because in the case where .sub.q#0, the significance pattern .sub.q cannot possibly be 0. It can be deduced, therefore, that when .sub.q0 and .sub.q=0 the value of .sub.q must be 15. Moreover, u.sub.q.sup.off=1 if and only if .sub.q0 and .sub.q0, so long as the encoder makes the sensible choice U.sub.q=E.sub.q.sup.max whenever .sub.qE.sub.q.sup.max so that .sub.q0 whenever u.sub.q.sup.off=1. In this way, non-zero EMB patterns .sub.q can be made available for CxtVLC coding even when u.sub.q.sup.off=0, at least in the important case where .sub.q=15.

(8) More generally, embodiments of the invention can exploit the fact that whenever any EMB bit e.sub.n=1, the corresponding significance bit must be a .sub.n=1, so that the corresponding bit within .sub.q a can be used to implicitly communicate u.sub.q.sup.off.

(9) In one general embodiment of the invention, that exploits this principle, the encoder constructs .sub.q and .sub.q as follows:

(10) $\stackrel{=}{}={}_q$${\stackrel{=}{}}_q=\{\begin{array}{cc}{}_q{}_q& \mathrm{if}{u}_q^{\mathrm{off}}=0\\ {}_q& \mathrm{otherwise}\end{array}$

(11) Here denotes bit-wise exclusive OR. In this embodiment, u.sub.q.sup.off is implicitly identified as 0 if .sub.q==0 or if any bit position within .sub.q is 1, while the corresponding bit position within .sub.q is 0; otherwise u.sub.q.sup.off must be 1. As before, this relies on the assumption that the encoder makes the sensible choice U.sub.q=E.sub.q.sup.max whenever .sub.q.sub.q.sup.max so that .sub.q0 whenever u.sub.q.sup.off=1. Also, .sub.q is easily recovered from the modified EMB and significance bit patterns by taking their bit-wise inclusive ORi.e., .sub.q=.sub.q.sub.q.

(12) To summarise key points described above: The CxtVLC coding procedure in the HTJ2K standard allows a decoder to decode 3 quantities (significance pattern .sub.q, partial EMB pattern information, and unsigned residual offset u.sub.q.sup.off), all from a variable length codeword with 0-7 bits. Importantly, the amount of EMB pattern information contained in a CxtVLC codeword is variableanywhere from no EMB information to all 4 bits of EMB pattern information are communicated, depending on the codewordit is a variable-to-variable coding scheme, coding a variable amount of information, using a variable number of bits. The HTJ2K encoding procedure only uses a 3-bit context value, a 4-bit significance pattern .sub.q and a 4-bit EMB pattern .sub.q, multiplied by the binary u.sub.q.sup.off value. These 11 bits address a lookup table that generates the CxtVLC codewords, relying upon the fact that these implicitly identify u.sub.q.sup.off=0, but at the expense of discarding all EMB pattern information .sub.q when u.sub.q.sup.off=0. The present invention is based on the insight that there are ways to communicate some EMB pattern information even when u.sub.q.sup.off=0 without using additional bits to address the CxtVLC table in the encoder.

(13) The key to this is to address the lookup table using a modified EMB pattern and a modified significance pattern, having the same number of bits as the original EMB and significance patterns.

(14) The terminology of relevance to the description above is summarised as follows: 1. EMB patternthe bit pattern .sub.q consisting of all e.sub.n bits for a given quad q.

(15) EMB pattern is a term in the HTJ2K standard, where it is a 4-bit word for each 22 quad being coded, that consists of the bits e.sub.n. This is the most significant bit-position that can contain non-zero bits. The EMB pattern is statistically skewed and in the context of the present invention presents an opportunity for coding efficiency gains through variable length coding methods, which is why it is desirable to include EMB pattern information in the variable length CxtVLC codewords whenever possible, subject to the constraint that CxtVLC codewords should exceed a given maximum length. 2. Modified EMB patterna bit pattern .sub.q, derived from and having the same number of bits as the original EMB pattern .sub.q, that is used to address the encoder's CxtVLC lookup table. 3. Partial EMB pattern informationpartial information about the original EMB pattern (0 or more of the original EMB bits) that the decoder discovers when it encounters a particular CxtVLC codeword. 4. Significance patternthe bit pattern .sub.q consisting of all .sub.n bits for a given quad q, identifying whether or not each sample in the quad is non-zero. 5. Modified significance patterna bit pattern .sub.q, derived from and having the same number of bits as the original significance pattern, that is used to address the encoder's CxtVLC lookup table.

(16) It will be understood to persons skilled in the art of the invention that many modifications may be made without departing from the spirit and scope of the invention.

(17) In the claims which follow and in the preceding description of the invention, except where the context requires otherwise due to express language or necessary implication, the word comprise or variations such as comprises or comprising is used in an inclusive sense, i.e. to specify the presence of the stated features but not to preclude the presence or addition of further features in various embodiments of the invention.

(18) It is to be understood that, if any prior art publication is referred to herein, such reference does not constitute an admission that the publication forms a part of the common general knowledge in the art, in Australia or any other country.