S&FRef: 602062
AUSTRALIA
PATENTS ACT 1990 COMPLETE SPECIFICATION FOR A STANDARD PATENT
ORIGINAL
Name and Address of Applicant: Actual Inventor(s): Address for Service: Invention Title: Canon Kabushiki Kaisha 30-2, Shimomaruko 3-chome, Ohta-ku Tokyo 146 Japan James Philip Andrew Spruson Ferguson St Martins Tower,Level 31 Market Street Sydney NSW 2000 (CCN 3710000177) Inverse Discrete Wavelet Transforms for Data Decompression ASSOCIATED PROVISIONAL APPLICATION DETAILS [33] Country [31] Applic. No(s) AU PR6626 [32] Application Date 26 Jul 2001 The following statement is a full description of this invention, including the best method of performing it known to me/us:- SIP Australia Documents received on: (0 -I.S 22 JUL 2002 o 581 5c Batch No: INVERSE DISCRETE WAVELET TRANSFORMS FOR DATA
DECOMPRESSION
Copyright Notice This patent specification contains material that is subject to copyright protection.
The copyright owner has no objection to the reproduction of this patent specification or related materials from associated patent office files for the purposes of review, but otherwise reserves all copyright whatsoever.
Technical Field of the Invention The present invention relates generally to data compression and, in particular, to image decompression. The present invention relates to a method and apparatus for the inverse discrete wavelet transforming of compressed image data. The invention also relates to a computer program for inverse discrete wavelet transformnning of an image.
Background The field of digital data compression and in particular digital image compression has attracted a great interest for some time. Recently, compression schemes based on a Discrete Wavelet Transform (DWT) have become increasingly popular because the DWT ofl'ers a non-redundant hierarchical decomposition of an image and resultant compression of the image provides favourable rate -distortion statistics.
Typically, the discrete wavelet transform (DWT) of an image is performed using a series of one-dimensional DWTs. A one-dimensional DWT of a signal (ie. an image row) is performed by lowpass and highpass filtering the signal, and decimating each filtered signal by 2. Decimation by 2 means that only every second sample of the filtering processes is calculated and retained. When performing a convolution (filtering) the filter is moved along by two samples at a time, instead of the usual one sample, to effect the decimation by 2. In this way, for a signal of N samples, there are N DWT samples, N/2 lowpass samples, and N/2 highpass samples. Strictly speaking this is a single level one dimensional DWT. However, since only single level one-dimensional DWTs are used in this description, they are referred to simply as a one-dimensional DWT (ID DWT).
602062.doc 14. FEB. 2005 18:33 SPRUSON FERGUSON NO, 7059 P, 5/43 -2.
o Fig. illustrates a typical process for perfonning a single level two-dimensional DWT of an input image 100. Each column of the image 100 is analysed with a one- Sdimensional DWT giving output columns whose first half comprise lowpass samples and whose second half comprise highpass samples. A single level one-dimensional DWT of a column is referred to as a column DWT. Such analysis of each column of the input image o 100 results in a coded representation 101 having two sub-images labelled L' and HF. The o columns of L" are formed of the lowpass filtered (and decimated) columns of the input en image 100 and the columns of H' are formed of the highpass filtered (and decimated) o columns of the input image 100. The coded representation 101 may then be considered as Ci 10 an output image, the rows of which are then analysed with a one-dimensional DWT, or row DWT, as also illustrated in Fig. 1. This results in a further coded representation 102 having four sub-images or subbands, labelled LL, HL, LH and HH, where L and H refer to lowpass and highpass respectively, and in the two letter label, the first letter corresponds to the row filter, while the second to the column filter. That is, the HL subband is the result of lowpass filtering the columns (and decimating by 2) and highpass filtering the resulting rows (and decimating by The LL subband is also called the DC or low frequency subband while the HL, LH and HH are called AC or high frequency subbands. Depending on the context, a single level two-dimensional DWT 102 of an image 100 can be referred to as a single level DWT (or even simply DWT) of the image 100.
Each one-dimensional DWT can be inverted, That is, having analysed a onedimensional signal of N samples into N/2 lowpass and N/2 highpass subband samples, these subband samples, of which there are N in total, can be synthesized with a onedimensional inverse DWT, into the N samples of the original onc-dimensional signal.
Thus, the original image can be reconstructed by synthesising the rows then the columns of a single level DWT of an image. This is also illustrated in Fig. 1. Thus a single level (two-dimensional) DWT is invertible. The process ofa inverting a DWT is often referred to as synthesis or applying an inverse DWT, or simply iDWT.
602062a COMS ID No: SBMI-01119664 Received by IP Australia: Time 18:51 Date 2005-02-14 To obtain a two level DWT the LL subband is further analysed with a single level DWT into four subbands, just as the original image was analysed into four subbands. To obtain a three level DWT, the LL subband resulting from the two level DWT is again analysed. Such a process can be perfomed in similar fashion for an arbitrary number of levels. Thus a multi-level DWT or simply DWT of an image can be performed by iterating a single level DWT some finite number of times on subsequent LL subbands, where the first LL subband is the original image 100). A multi-level DWT can be inverted by simply inverting each single level DWT.
At each level of a multi-level DWT there are three high frequency subbands, the I-lL, LH and HH subbands. Therefore, for a more precise notation a level number is included in the labelling of the subbands. Thus the four subbands illustrated in the coded representation 102 of Fig. 1 are more precisely denoted LL1, HL1, LH1 and HH1.
Similarly the three high frequency subbands at level 2, resulting from the single level DWT of the LLI subband, are denoted HL2, LH2 and HH2. Using this subband notation the original image 100 can be labelled as the LLO subband.
In some image compression methods the subbands resulting from a DWT are tiled into blocks of samples, called code-blocks. For example, each block consists of, say, H rows by H columns. A row of blocks in a subband is formed of H lines of the subband.
Typically, each block (code-block) is quantised and entropy coded substantially independently. Thus each block can be entropy decoded (and dequantized) independently. A block essentially becomes a minimum coded unit. The blocks are not necessarily strictly independently encoded. Some small amount of information, such as the most significant bit plane in each block, may be coded together for all blocks in a subband. However, if the time or effort required to encode or decode such information for one block is trivial when compared to encoding or decoding a whole block, then for present purposes it may be considered that the blocks are coded independently. Such image compression methods are referred to herein as block-based DWT image compression methods.
602062.doc 14FEB-2005 18:36 SPRUSON FERGUSON NO. 7059 P. 110/43 -4- 0 0 Other compression methods such as JPEG employ a block discrete cosine .C transform (DCT) to map data into a frequency domain. Typically an image is tiled in the
CD)
F spatial domain into 8x8 blocks of pixels. Each 8x8 block is transformed into a block of 8x8 coefficients, including 1 DC coefficient, and 63 AC coefficients. For baseline JPEG, the coefficients are quantized and coded into one entropy coded segment in the c0 compressed image bit-stream. This segment then represents the original 8x8 block of o pixels. Apart from a small coupling of the DC coefficients, there is a 1-1 relationship Sbetween the 8x8 blocks in the image domain and entropy coded segments.
SFor typical compression rates, many of the coefficients are quantized to zero and C 10 hence dequantized to zero. At the decoder, each block of 8x8 pixels is reconstructed substantially independently. Firstly the quantized DCT coefficients are decoded from the compressed bit-stream. The DC value is reconstructed from the current difference and the previous blocks DC value. The coefficients are then dequantized and inverse transformed with an inverse DCT. Many inverse (and forward) DCT techniques employ a series of one dimensional DCT's. Firstly all the columns are inverse transformed, and then all the rows. For each column a test may be made if each of the AC coefficients are zero. If so, a faster version of the inverse column DCT can be employed, providing a speed-up for the overall two-dimensional DCT. This technique is employed by the Independent JPEG Group (IJG) code which is widely used in JPEG compression and decompression software. A similar test can also be employed when performing the inverse row DCT's. However, if the row inverse DCT's are employed after the column inverse DCT's the likelihood of all the AC coefficients being zero is significantly less than that for the column inverse DCT's. In some cases the overhead required to test each row can result in a slower overall inverse two-dimension DCT, which is contrary to the zs intended purpose.
The 1-1 mapping between 8x8 blocks of coefficients and 8x8 blocks of pixels facilitate using knowledge of the zero-valued coefficients to accelerate the inverse DCT.
If a set of AC coefficients (ie a column) is zero, then it is known that all relevant AC coefficients that can affect this block are zero. That is there is no overlap from adjacent 602062a COMS ID No: SBMI-01119664 Received by IP Australia: Time 18:51 Date 2005-02-14 14 FEB, 2005 18:37 SPRUSON FERGUSON NO.7.059 P. 14/43 o blocks, and AC coefficients in adjacent (or other) blocks have no effect on the pixels resulting from the inverse transform of the current block.
For block-based DWT image compression methods, decompression involves entropy decoding compressed blocks of subband samples, and then an inverse DWT is performed on the resulting subbands. As with the DCT, at typical compression rates (for oc example I bit per pixel), many of the high frequency subband coefficients are quantized Sto 0. A rough correspondence can be derived between a set of DWT coefficients and a set M of the same size of image domain pixels. However, for overlapping filters, such as those employed by the JPEG2000 standard (ISO/IEC 15444-1:2000), the image domain pixels N 10 actually depend on a greater number of DWT coefficients: namely some of those adjacent to the given set of DWT coefficients. This non 1:1 relationship between subband and image domain blocks means that identifying all corresponding AC subband blocks are zero is not sufficient to determine that the corresponding output block can be generated assuming zero AC subband values.
Further, the inverse DWT is usually performed one-level at a time. There are thus 3 AC coefficients for every DC coefficient, for each level of the inverse DWT. The smaller number of AC coefficients relative to the DC coefficients, and the greater amount of overlapping state means that the IJG approach referred to above to reduce computation (based on zero valued AC coefficients) cannot be simply adopted in an efficient manner to the case of an inverse DWT.
Summary of the Invention In accordance with one aspect of the present invention, there is provided a method of inverse discrete wavelet transforming subband data in segments, wherein a plurality of different computational procedures for performing the inverse DWT may be used, and wherein a current state is maintained between a current and previous segments of subband data, the method comprising the steps of testing the current state and a subset of the current segment of subband data for zero valued coefficients to determine if the current segment can be inverse transformed with a reduced computational procedure; if the test is positive performing the inverse DWT using the reduced computational procedure based 602062a COMS ID No: SBMI-011 19664 Received by IP Australia: Time 18:51 Date 2005-02-14 14. FEB. 2005 18:37 SPRUSON FERGUSON NO. 7059 P. 15/43 -6o on a lifting implementation of an inverse DWT; otherwise performing the inverse DWT .Q of the segment using another computational procedure based on a lifting implementation
C)
.L of an inverse DWT.
In accordance with another aspect of the present invention, there is provided a method of performing a two-dimensional inverse discrete wavelet transform on blocks of f LL, LH, HIL and HH subband coefficients, utilising a non-AC and AC lifting state o between adjacent vertical and horizontal blocks, the method comprising the step of n generating a current output block of pixels corresponding to a current set of LL, HL, LH, o and HH blocks, wherein if the HIL, LH and HH blocks contain all zero valued Cl 10 coefficients, and the AC lifting state corresponding to the current block of pixels is zero, perfoming an inverse block-based DWT using the LL block and non-AC lifting state to generate the current block of pixels.
In accordance with another aspect of the present invention, there is provided a method of two-dimensional inverse discrete wavelet transforming subband data, wherein the subband data comprises a plurality of blocks of subband data and the blocks each comprising at least one quadruplet of LL, IHL, LH and HH subband coefficients, and wherein the method utilises a non-AC and AC lifting state between adjacent vertical and horizontal blocks, the method comprising the step of generating a current output block of pixels corresponding to a current set ofLL, HL, LH, and HH blocks, wherein if the HL, LH and HH blocks contain all zero valued coefficients, and the AC lifting state corresponding to the current block of pixels is zero, performing an inverse block-based DWT using the LL block and a non-AC lifting state to generate the current block of pixels.
In accordance with another aspect of the present invention, there is provided an apparatus for inverse discrete wavelet transforming subband data in segments, wherein a plurality of different computational procedures for performing the inverse DWT may be used, and wherein a current state is maintained between a current and previous segments of subband data, the apparatus comprising means for testing the curent state and a subset of the current segment of subband data for zero valued coefficients to determine if the 602062a COMS ID No: SBMI-01119664 Received by IP Australia: Time 18:51 Date 2005-02-14 14. FEB.2005 18:37 SPRUSON FERGUSON NO. 7059 P. 16/43 .7.
0 o current segment can be inverse transformed with a reduced computational procedure; means for performing, if the test is positive, the inverse DWT using the reduced Scomputational procedure based on a lifting implementation of an inverse DWT and means for performing, if the test is negative, the inverse DWT of the segment using another computational procedure based on a lifting implementation of an inverse DWT.
In accordance with another aspect of the present invention, there is provided an Sapparatus for performing a two-dimensional inverse discrete wavelet transform on blocks r of LL, LH, HL and HH subband coefficients, utilising a non-AC and AC lifting state o between adjacent vertical and horizontal blocks, the apparatus comprising means for C- 10 generating a current output block of pixels corresponding to a current set of LL, HL, LH, and HH blocks, wherein if the HL, LH and HH blocks contain all zero valued coefficients, and the AC lifting state corresponding to the current block of pixels is zero, performing an inverse block-based DWT using the LL block and non-AC lifting state to generate the current block of pixels.
In accordance with another aspect of the present inverition, there is provided an apparatus for two-dimensional inverse discrete wavelet transforming subband data, wherein the subband data comprises a plurality of blocks of subband data and the blocks each comprising at least one quadruplet of LL, HL, LH and HH subband coefficients, the apparatus utilising a non-AC and AC lifting state between adjacent vertical and horizontal blocks, the apparatus comprising means for generating a current output block of pixels corresponding to a current set of LL, HL, LH, and HH blocks, wherein if the HL, LH and HH blocks contain all zero valued coefficients, and the AC lifting state corresponding to the current block of pixels is zero, performing an inverse block-based DWT using the LL block and a non-AC lifting state to generate the current block of pixels.
In accordance with another aspect of the present invention, there is provided a computer program for inverse discrete wavelet transforming subband data in segments, wherein a plurality of different computational procedures for performing the inverse DWT may be used, and wherein a current state is maintained between a current and previous segments of subband data, the computer program comprising means for testing 602062a COMS ID No: SBMI-01119664 Received by IP Australia: Time 18:51 Date 2005-02-14 14. FEB. 2005 13:38 SPRUSON FERGJSON ,10. 7059 P. 17/43 -8- 0 o the current state and a subset of the current segment ofsubband data for zero valued coefficients to determine if the current segment can be inverse transformed with a reduced
C)
Lcomputational procedure; memans for performing, if the test is positive, the inverse DWT using the reduced computational procedure based on a lifting implementation of an inverse DWT and means for performing, if the test is negative, the inverse DWT of the oc
J
segment using another computational procedure based on a lifting implenmentation of an 0 ~inverse DWT.
cn In accordance with another aspect of the present invention, there is provided a 0 computer program for performing a two-dimensional inverse discrete wavelet transform Ci 10 on blocks ofLL, LH, HL and HH subband coefficients, utilising a non-AC and AC lifting state between adjacent vertical and horizontal blocks, the computer program comprising means for generating a current output block of pixels corresponding to a current set of LL, HL, LH, and HH blocks, wherein if the HL, LH and HH blocks contain all zero valued coefficients and the AC lifting state corresponding to the current block of pixels is zero, performing an inverse block-based DWT using the LL block and non-AC lifting state to generate the current block of pixels.
In accordance with another aspect of the present invention, there is provided a computer program for two-dimensional inverse discrete wavelet transforming subband data, wherein the subband data. comprises a plurality of blocks of subband data and the blocks each comprising at least one quadruplet of LL, HL, LH and HH subband coefficients, the apparatus utilising a non-AC and AC lifting state between adjacent vertical and horizontal blocks, the computer program comprising means for generating a current output block of pixels corresponding to a current set of LL, HL, LIHI, and HH blocks, wherein if the HL, LH and HH blocks contain all zero valued coefficients and the AC lifting state corresponding to the current block of pixels is zero, performing an inverse block-based DWT using the LL block and a non-AC lifting state to generate the current block of pixels.
602062a COMS ID No: SBMI-01119664 Received by IP Australia: Time 18:51 Date 2005-02-14 14, FEB, 2005 IB:38 SPRUSON FERGJSON 10. 7059 P. 18/43 .9- 0 oBrief Description of the Drawings A prefered implementation of the present invention will now be described with reference to the drawings and appendix, in which: Fig. I illustrates a prior art process of perforning a single level two-dimensional discrete wavelet transform of an image; Fig. 2 illustrates the division of eacb subband of a DWT image into row of blocks in o accordance with the preferred decoding method; nFig. 3 is a lifting lattice of an inverse DWT 9/7 filter for use in the preferred decoding method; Ci 10 Fig. 4 shows a correspondence between blocks in the LL and HL subbands and the 0 sub-image in accordance with the preferred decoding method; Fig. 5 shows a correspondence between blocks in the L sub-image and 1WY subimage and the original image in accordance with the preferred decoding method; Fig. 6 is a lifting lattice of an inverse DWT 5/3 filter for use in the preferred is decoding method; Fig. 7 is a flow-chart of a method of decoding a coded representation of an image in accordance with the preferred implementation; Fig. 8 is a flow chart of step 765 of the preferred decoding method shown in Fig. 7; Fig. 9 is a flow chart of sub-step 860 of step 765 of the preferred decoding method shown in Fig- 7; Fig. 10 is a schematic representation of a general-purpose computer for use in implementing the decoding method of Fig, 7; and Appendix A is a C code implementation of a 5/3 iDWT block engine Detailed Description Where reference is made in any one or more of the accompanying drawings to steps and/or features, which have the same reference numerals, those steps and/or featares 602062a COMS ID No: SBMI-01119664 Received by IP Australia: Time 18:51 Date 2005-02-14 14. FEB, 2005 18:3B SPRUSON FERGUSON NO. 7059 P. 19/43 0 ohave for the purposes of this description the same function(s) or operation(s), unless the contrary intention appears.
The principles of the preferred method, apparatus and computer program _described herein have general applicability to data compression. However, for ease of explanation, the preferred method, apparatus and computer program are described with 00 reference to digital stiU image compression. However, it is not intended that the present 00 invention be limited to the descnbed apparatus and method. For example, the invention CC) may have application to digital video decompression.
u Throughout the specification a reference to the term image is to be construed, Ci 10 unless otherwise stated, as an image in the spatial domain or its equivalent in the frequency domain depending upon the context in which the term image is used, Where an ambiguity may arise the terms "original image" shall be used as the spatial domain image and "DWT image" as the corresponding frequency domain image. Similarly, a reference to "sub-image" shall be taken to mean a portion or part of an image.
Apart from precision effects, the order in which the rows and columns of pixels are transformed or inverse transformed does not usually affect the result of the DWT or iDWT of an image. The description given herein describes for the purposes of clarity that the columns are transformed first and then the rows for the forward DWT, and that the rows are inverse transformed first, followed by the columns for the inverse DWT.
However, the invention is not limited as such and can include that the rows are transformed first and then the columns for the forward DWT, and that the columns are inverse transformed first, followed by the rows for the inverse DWT. Accordingly throughout the present description and appended claims, a reference to a "row" and a "column" can alternatively be taken to include a reference to a "column" and a "row" respectively.
Block Based Entropy Coding of DWT Subband Image Data When entropy coding. it is typically most efficient and convenient to fully entropy code a whole block of subband data. Similarly, when entropy decoding it is convenient 6dOZ62a COMS ID No: SBMI-01119664 Received by IP Australia: Time 18:51 Date 2005-02-14 -11and efficient to entropy decode a whole block of data. Generally, a whole block of data is held in a local memory during encoding or decoding, so that a processor performing the decoding requires minimal interaction with external memory, while executing these processes. The decoding method according to the preferred implementation perfonns the iDWT at a block level.
Correspondence between the Subband and Image Domain Fig. 2 illustrates a single level DWT 200 ofan image, and the tiling of each subband LL, I-IL, LH, HH into blocks 210 each comprising K x K coefficients In each subband LL, HL, LH, HH there are four blocks per row of blocks. Hence, there are 4K coefficients per row in each subband. The image upon which the DWT is performed can in fact be any array of samples, such as some intermediate LL subband, and need not necessarily be an original (spatial domain) image. However, in order to differentiate the input and output of the single level DWT, the array of samples input to the single level DWT is referred to as the (input) image, while the output is referred to as a (single level) DWT image 200) (which typically consists of four subbands). Each row 211 of blocks of a subband in the DWT image, shown in Fig. 2, consists ofK lines, where K is a positive integer value. Preferably, K is an integer value determining a preferred (or desired) block size for entropy coding. Corresponding to such a set of K lines are 2K lines of the original image. For example, in the case of Haar filters, 2K lines can be used to generate the K subband lines, for each of the four subbands, and visa-versa, so that there is a one-to-one correspondence between one level and a next level. However, those skilled in the art will appreciate that for other (longer) filters, a number of extra image lines may be required to generate the K subband lines at a next level of DWT decomposition. For example, in the case of 9/7 Daubechies filters, another seven lines of the input image, giving 2K+7 in total are required to produce K lines at a next level. In addition at synthesis extra subband lines, in addition to the K lines from each of the four subbands, are required to produce the 2K corresponding image lines of the previous level.
602062.doc 12 For the 9/7 Daubechies filters the LL and HL subband require 3 extra subband lines, while the LH and HH require 4 extra subband lines.
The Inverse One Dimensional DWT by Lifting The one-dimensional DWT and iDWT can be implemented using a lifting scheme.
An implementation of the invention preferably uses the reversible 5/3 or a 9/7 wavelet filler of type described in the JPEG2000 standard. However other filters can be used.
The single level 5/3 filter reversible iDWT of a one-dimensional signal x, as used in the JPEG 2000 standard, is defined by the lifting equations, x2n Sn 2)/4j S2n+1 d n +L(x2n+ x 2n+ 2 )/2J Eqns(l) where is sample n of the input signal, dn is sample n of the output onedimensional (1D) subband highpass signal, and s, is sample n of the output ID lowpass subband signal. Unless otherwise indicated all indices are zero based. That is the first sample of each signal is sample 0. These eqns referred to as lifting equations, can be represented by a lifting lattice as illustrated in Fig. 6.
The 9/7 filter iDWT of a one-dimensional signal x, as used in the JPEG 2000 standard, is defined by the lifting equations, d,, d, x. s' Eqn(2) x2l,, x 2 where c -1.5861, P -0.052980, y 0.88291, 6 0.44351, Sn and dn are coefficient n in the lowpass and highpass subband respectively, and s'n and d'n are intermediate values. These eqns can be represented by a lifting lattice as illustrated in Fig. 3.
602062.doc 13 For the purposes of this description, the correspondence between subband samples LL, HL, LH, and HH and input image samples is defined via the process of lifting, ie the updating of the coefficient. Thus, subband coefficient n+l) in the LL subband corresponds to input image sample (2m+2, 2n+2). Subband coefficient n+1) in the HL subband corresponds to input image sample (2m+2, 2n+3). Subband coefficient n+l) in the LH subband corresponds to input image sample (2m+3, 2n+2).
Subband coefficient n+l) in the HH subband corresponds to input image sample (2m+3, 2n+3).
Turning now to Fig. 3, the lifting scheme for an iDWT can now be described with reference to 9/7 Daubechies filters.
Consider a signal x comprising samples x 0 xi, The one dimensional DWT of this signal generates a lowpass signal s comprising samples (coefficients) so, s, s2, and a highpass signal d comprising samples (coefficients) do, In this notation x is referred to as the image signal, and the s and d signals are referred to as subband signals. Using this notation, an iDWT signal can be inverted according to above mentioned equations In addition, some scaling of the subband or output coefficients may be required depending on the scaling used for the forward transform.
Returning to Fig. 3, each line 300 between samples 301 on the lattice represents a contribution of a sample at the top end of the line to a weighted sum forming a number at the bottom end of the line 300. Thus, for example, since do, s, and dl are all connected to s'i by lines 300, and is at the bottom of each line 300 we have that s'i is a weighted sum of do, s/ and ds. In particular, according to the lifting equation s'i s, 3(do dj), and therefore lines 300 joining do and d, to s'i are weighted by 6= 0.44351 and s, by unity.
A brief explanation of the inverse DWT method is made with reference to Fig. 3.
The inverse DWT method accesses a first segment of subband samples say so, sl, s2, s3, s4 and do, dt, d2, d 3 d 4 Corresponding to these 10 samples are the 10 first image samples x o XN However the inverse DWT method can only reconstruct the first seven samples 602062.doc 14 xo, x 1 .x 6 It cannot reconstruct the last three samples x 7 xs, and xg, without obtaining further subband samples.
At the same time as the inverse DWT method obtains this first segment of subband samples and reconstructs the first 7 image samples, it also buffers the four intermediate coefficients xe, d'3, s'4, and These are the coefficients immediately to the left of the heavy diagonal line 302 in Fig. 3, and are referred to as the lifting state. The number and type of these intermediate coefficients of the lifting state eg. image coefficients n intermediate coefficients and subband coefficients will be dependent on the type of the lifting lattice in use. Also, the AC subband coefficients and AC intermediate coefficients of the lifting state (eg. d 4 and d'3) are referred to as the AC lifting state, and the remaining coefficients (eg. x 6 and s'4) of the lifting state are referred to as the non- AC lifting state. Next, the inverse DWT method retrieves a second segment of subband samples, say ss, s6, S7, ss, so and d 5 do, ls, d9, (some of which are not illustrated) and using the buffered lifting state data, the inverse DWT method can reconstruct the image samples x 7 vs, and x 9 and also all the image samples, bar the last three, corresponding to these new subband samples. That is samples xio, x.t, x1,. As before last three samples .V7, -is. and x i cannot be reconstructed without obtaining more subband samples. If the inverse DWT method again buffers four intermediate lifting state samples and obtains a third segment of subband samples it can reconstruct another ten subband samples, and so on. Using this approach of buffering four intermediate lifting state samples, the inverse DWT method can reconstruct a signal from sequential segments of subband samples. For each segment comprising n lowpass and n highpass samples, the inverse DWT method can reconstruct 2n image samples. These are the 2n image samples corresponding to the n subband samples, excepting the last three but also including the three samples prior to these 2n samples. For finite length signals, for all but the first and last segment of n subband samples the inverse DWT method is able reconstruct 2n image samples. For the first segment the inverse DWT method reconstructs 2n-3, while for the last segment 2n+3, 602062.doc images samples. Using the usual symmetric boundary extension, the inverse DWT method obtains the extra last three samples for last block.
These properties of the lifting lattice are used to facilitate the implementation of the line based inverse DWT in accordance with the preferred implmentation. Convolution techniques can also be used, however, a convolution implementation will typically require seven subband samples buffered between subband segments, as opposed to four, for a ti ting scheme as described above.
For filters other than the 9/7 Daubechies filter the same approach to reconstructing the signal from subband segments can be used. However more or less intermediate subband samples will need to be buffered depending on the lattice configuration (or filters). For example, for the 5/3 filters two lifting state variables are required.
Since a two-dimensional (single level) iDWT can be performed using a series of one dimensional inverse DWTs, the two-dimensional iDWT can also be performed in segments. A special case of a two-dimensional segment of a two-dimensional subband is simply a block of subband samples. Thus, the inverse DWT method can perform a single level iDWT of four subbands by processing blocks of subband samples and buffering intermediate results between blocks.
Performing a Single Level Two-Dimensional iDWT on a Block by Block Basis using Lifting The techniques described above with reference to Fig. 3 for performing a onedimensional iDWT in segments can be used to perform a two-dimensional iDWT on a block by block basis (a block being the two-dimensional segment).
Returning to Figs. 1 and 2 consider the single level inverse DWT of a DWT image.
Suppose the LL, HL and HH subbands are of size Nx N. First the rows of the LL and HL subbands are synthesised to form an N x 2N array of samples which comprise the lowpass (and decimated by 2) filtered columns of the original image. This array is labelled as L in Fig. 1. Similarly the rows of the LH and HH subbands are synthesised to form another 602062.doc 16- N x 2N array of samples, which comprise the highpass (and decimated by 2) filtered columns of the original image, and is labelled H' in Fig. 1.
This row operation, as. a series of one-dimensional iDWTs can be performed in segments, where the segments are say given by the block boundaries.
Consider the row synthesis of the LL and HL subband to form the L c sub-image, as illustrated in Fig. 4. Corresponding to each block pair in the LL and HL subband is a block in the L sub-image, which has the same number of rows as the corresponding LL (or HL) block, but has twice the number of columns. For example, the block 1 in the subband L' sub-image corresponds to the pair of blocks 1 in the LL and HL subbands.
For the purposes of the inverse row transform LL subband contains the lowpass row data, while HL subband contains the highpass row data. Corresponding blocks in each of these subbands contain the corresponding lowpass and highpass data.
First consider block 1 in the LL and HL subbands. Each block consists of K rows by K columns of data. The decoding method inverse transform each row these blocks outputting 2K-3 synthesised samples per row, and buffering four intermediate subband samples, per row. These 2K-3 samples per row are the first 2K-3 samples per row of block 1 of the L sub-image. The last 3 row synthesised samples per row, being the last three samples in each row in block 1 of the L' sub-image, cannot be reconstructed until more subband data (ie from block 2) is obtained. Thus the decoding method has reconstructed all but the last three columns of block 1 of the L' sub-image. Then the decoding method can inverse transform the K rows of block 2 (from the LL and HL subband) and, using the four buffered subband samples per row from block 1, generate the next 2K samples of each synthesised row data. That is, the last three synthesised samples of each row of block 1 of the Lc sub-image and the first 2K-3 samples of each row of block 2 of the LC sub-image. Hence the decoding method has now completed the reconstruction of block I of the L' sub-image and reconstructed all but the last three columns of block 2 of the LC sub-image. The decoding method can similarly process block 3. Finally the decoding method can process block 4. For this block the decoding 602062.doc 17method cannot only complete the reconstruction of block 3 of the LC sub-image but also of block 4 of the L e sub-image. The last three synthesised samples of block 4 of the LC sub-image for each row can be reconstructed using the symmetric boundary extension conditions. Thus for the block 4 we synthesise 2K 3 samples per row.
The decoding method can similarly process the LH and HH subbands in block row order to produce the He sub-image.
Corresponding to each pair of blocks in the L' and He sub-images is a 2K x 2K block in the original image, as illustrated in Fig. 5. For example, block I in the original image corresponds to the pair of blocks 1 in the Lc and He sub-images.
Turning now to Fig. 2, and 5, it can be seen that each quadruplet of blocks in the LL, HL, LH, and HH subbands, for example the quadruplet comprising blocks 1 in LL, -IL, LH, and HH (Fig. correspond to one block, for example block 1, in the original image (Fig. The decoding method having performed the row synthesis for the LL and HL subbands of block 1 results in all but the last three columns of block 1 of the L' subimage. Similarly processing block 1 for the LH and HH subbands gives all but the last three columns of block 1 of the H C sub-image. Thus, the decoding method at this stage results in the first 2K-3 columns of block 1 of the LC and He sub-image. During the next stage, the decoding method can process column 1 of block I of LE sub-image and of block 1 of the He sub-image to generate all but the last three samples of column 1 of block 1 of the original image. The decoding method can similarly process columns 2, 3, 2K-3 of these blocks. Thus during this stage, the decoding method can generate the top left hand 2K-3 x 2K-3 samples of block 1 of the original image. The decoding method also buffers the four intermediate subband samples for each column for use when the decoding method processes block The decoding method then processes the rows of block 2 of the LL and HL subbands and the rows of block 2 of the LH and HH subbands, and using the buffered intermediate subband data from block 1, reconstruct the last three columns of block 1 and 602062.doc the first 2K-3 columns of block 2 of the of LC and H C sub-image. The decoding method can then process these 2K columns to generate the top left hand 2K-3 x 2K-3 samples of block 2 of the original image, and also the right hand 2K-3 x 3 sub-block of block I of the original image. The decoding method also buffers the 4 intermediate subband samples for each of the 2K columns. At this stage, the decoding method has then reconstructed the first 4K-3 samples for the first 2K-3 rows of the original image. The decoding method can similarly process blocks 3 and 4, giving all of the first 2K-3 rows of the original image.
Next the decoding method processes the second row of blocks in a similar fashion.
For block 5, the decoding method synthesises the rows as above. When the decoding method synthesises the columns it uses the buffered column overlap data to reconstruct the last three rows of block 1 in the original image as well as the first 2K-3 rows of block 2 of the original image (excepting the last three columns, as before). Similarly for blocks 6 and 7 it also reconstructs the last three rows of blocks 2 and 3 for the original image as well as the first 2K-3 of block 6 and 7 of the original image. For block 8, the decoding method can reconstruct all the row data, and thus reconstruct a 2K x (2K+3) block. The decoding method similarly processes all the blocks in DWT subbands.
The block based inverse DWT can be performed at a very local level, right down to Ix subband blocks (or lx 1 subband block quadruples), where the blocks are processed in turn in raster order from left to right, top to bottom. In this case the output will be a block of 2x2 pixels, suitably delayed due to the filter overlap required. For example for the 5/3 reversible DWT, as used in JPEG2000, a 2x2 output block of image samples x[2m 1, 2*n x[2m 2, 2*n x[2m 1, 2*n 2] and x[2m+2, 2*n can be formed from subband samples LL[m n HL[m l,n LH[m l,n 1] and HH[m 1, n and a lifting state for each scanned subband block in raster order, which will be described in more detail below.
Turning now to Fig. 6, there is shown a lifting lattice for inverse DWT of 5/3 filters for illustrating the performance of 2x2 block based inverse DWT. Fig. 6 represents the 602062.doc -19- 5/3 lifting lattice in a similar fashion as the 9/7 lattice that shown in Fig. 3. Namely, each line 600 between samples 601 on the lattice represents a contribution of a sample at the top end of the line to a weighted sum forming a number at the bottom end of the line 600.
Thus, for example since dl, S2 and d 2 are all connected to x 4 by lines 600 and x 4 is the bottom of those lines x 4 is a weighted sum of d 1 s2 and d 2 It is also assumed that all samples x, to the left of the bold line 602 have been calculated during previous processing. A brief explanation of the 2x2 block based inverse DWT is now made with reference to Fig. 6 and Eqns Firstly consider a single level ID synthesis of the first column of a ID DWT image. For example, in Fig. 6 sn and dn refer to the lowpass and highpass samples at row n in the first column of the LC and H' sub-image respectively of the ID DWT image. For example, the image sample xio can be first determined from the subband samples d 4 ss, and ds as indicated by lines 600. The image sample x9 can then be determined fiomi the previously determined sample xs, the highpass sample d 4 and the previously determined sample x 1 o. That is, xio s 5 L(d4 +d 5 +2)/4J x 9 =d 4 +L(x8 +xo)/2J Eqns(3) More generally image samples X 2 n+ 2 and x2n+I can be calculated in accordance with Eqns given subband data s,n+ dn+, and image sample x2n.
In order to obtain the image samples of the original image from a single level 2D DWT image, the computations of Eqns may be applied to the rows and then the columns of a 2x2 block of the single level 2D DWT.
Pseudo-code *1 describing this 2x2 block based inverse DWT operation follows. In Pseudo code xl refers to row m I of the image x, x2 refers to row 2m 2 of the image, and the LL, HL, LH and HH variables refer to row 2m 1 of the corresponding subband, and XL2, XL1, XH2, XHI are temporary variables, and the constant ROUND LP 2.
602062.doc Pseudo-Code *1: Horizontal synthesis of LL and HL XL2 LL[n+l] ((HLcur HL[n+l ROUND_LP) 2); XL-= HLcur ((XLO+XL2)>> 1); HLcur HL[n+1]; Updates for next iteration across row (on n) XLO XL2; Horizontal synthesis of LH and HH XH2 LH[n+l] ((HHcur HH[n+l] ROUND_LP) 2); XH1 HHcur ((XHO XH2) 1); HHcur HH[n+l]; Updates for next iteration across row (on n) XHO XH2; Vertical synthesis of XL and XH, column2n+1 x2[2*n+l] XLI ((XHprcv[2*n+l] XH1 ROUND_LP) 2); xl[2*n+l] XHprev[2*n+l] ((XLprev[2*n+l] x2[2*n+l]) 1); XHprev[2*n+l XH 1; Update for next iteration down column (on m) XLprev[2*n+l] x2[2*n+l]; Vertical synthesis of XL and XH, column2n+2 x2[2*n+2] XL2 ((XHprev[2*n+2] XH2 ROUND_LP) 2); x t[2*n+2] XHprev[2*n-2] ((XLprev[2*n+2] x2[2*n+2) 1); XHprev[2*n+2] XH2; Update for next iteration down column (on m) XLprev[2*n+2] x2[2*n+2]; If AC subband coefficients HL[n+l], LH[n+l] and HH[n+1] are known to be zero, and the AC lifting state variables HLcur, HHcur, XHO, XHI, XHprev[2*n+1] and XHprev[2*n+l] are known to be zero then the operations can be simplified to the 602062.doc bfllowing Pseudo-code The AC lifting state variables are those lifting state variables that are zero in steady-state when AC subband data is zero.
Pseudo-code *2 Horizontal synthesis of LL and HL XL2 LL[n+1]; XL1 O+XL2) 1); XLO XL2; Horizontal synthesis of LH and HH Nothing to do Vertical synthesis of XL and XH, column2n+l x2[2*n+l]= XLl; xl ((XLprev[2*n+l1] x2[2*n+l 1); XLprev[2*n+l] x2[2*n+l]; Vertical synthesis of XL and XH, column2n+2 x2(2*n+2] XL2; x ((XLprev[2*n+2] x2[2*n+2) 1); XLprev[2*n+2] x2[2*n+2]; Also note that the lifting state variables HLcur, HHcur, XHO, XHI, XHprev[2*n+l] and XHprev[2*n+lJ do not need to be updated as they remain at zero. This simplified pseudo-code (Pseudo-code is referred to as the zero speed-up pseudo-code. The previous Pseudo-code I can be used as the default pseudo-code. If the relevant variables are known to be zero there is a substantial saving in computation using the zero speed-up pseudo-code. For the 5/3 filters illustrated here, the speed up is something in the order of four times less adds and shifts.
To know that the AC subband coefficients and the AC lifting state variables are zero requires testing of this data. It is important that the test itself does not substantially 602062.doc slow the operation of the inverse DWT procedure, otherwise the purpose of speeding up the inverse DWT is defeated.
The above pseudo-code procedures synthesize a lxl block of subband quadruples (a Ixl block from each of the LL, HL, LH and HH subbands) to form a 2x2 output block.
Larger blocks of subband quadruples can be synthesized with the above pseudo-code procedures. For example a 32x32 block of subband quadruples can be synthesized to form a 64x64 output image block. For larger subband block quadruples, the above pseudo-code procedures become the code in an inner loop of a two-dimensional loop iterating over preferably the rows first (outer loop) and then columns (inner loop) of the larger subband block quadruple. The inner loop moves across a row (looping over columns) of lxl subband block quadruples. The horizontal lifting state is required for the next inner loop iteration only, and hence can be stored in the scalar variables HLcur, HHcur, XLO, and XHO. The vertical lifting state needs to be remembered for a whole row of subband block quadruples and hence is stored in the vector (pointer) variables XLprev and XHprev. The horizontal lifting state, HLcur, HHcur, XLO, and XHO does need to be buffered for each row of the larger subband block quadruple, between synthesis of horizontally adjacent larger subband block quadruples. Further the vertical lifting state (the XHprev and HLprev vectors) needs to be buffered between synthesis of vertically adjacent subband block quadruples. This buffering is achieved with the same vectors (or a super-set thereof) for XHprev and XLprev.
If it is known that all relevant AC subband coefficients and lifting state variables are zero then a larger subband block quadruple can be synthesized using the zero speed-up pseudo-code as the code in the inner loop. Whether or not a code-block (ie. one out of four blocks in a subband block quadruple) of subband data is zero is easily (and with no computational cost) determined from the entropy decoder, for a block-based DWT image compression. It remains to test if the AC lifting state for a given subband block is zero.
602062.doc 14.FEB-2005 18:39 SPRUSON FERGUSON NO. 7059 P. 21/43 23- After the pseudo-code procedures given above have been iterated across a column, Sa simple operation can determine if any horizontal AC lifting state in any preceding row C is non-zero by using an or operation (D as follows: is_his_nonzero I- (XHO I HLcur r HHcur).
s If any of XHO, HLcur, and HHcur are non-zero then is_h s_nonzero will become nonzero. Once is his_nonzero is non-zero, it will remain so regardless of future such or operations. After the pseudo-code procedures given above have been iterated across all o the rows of a subband block quadruple, the ishlsnonzero variable can be buffered for when synthesizing the next horizontal larger subband block quadruple. If is_hls nonzero C 10 is zero, then all the horizontal AC lifting state for the next larger subband block quadruple is zero.
The vertical lifting state gets updated in the inner loop (ie. within the above pseudocode procedures). It is not desirable to test this lifting state in the inner loop, since it may substantially affect the speed of the loop. Before synthesizing a larger subband block quadruple, if the corresponding ishls nonzero state flag is zero, then the relevant vertical lifting state can be tested to see if it is all zero. It is necessary to test XHprev[n] where n is relevant to the subband block quadruple. If the vertical lifting state is also zero then the subband block quadruple can be synthesized with the zero speed-up pseudo-code method.
Otherwise the default method is used. In this way the testing overhead is substantially insignificant, for reasonable sized blocks.
C code implementing the above described 5/3 block engine is given in Appendix
A.
The 2x2 block based inverse DWT can also be implemented using a 9/7 reversible DWT in similar fashion to the 2x2 block based DWT described above.
Decoding an image with a block based zero speed-up inverse DWT Preferably, the blocks of each subband of a DWT image have been entropy coded, where the block size is fixed across all subbands and each block consists of has K rows of data. For situations where variable block sizes are used, preferably K is the number of rows of the block with the most number of rows (or possibly the least common multiple 602062a COMS ID No: SBMI-01119664 Received by IP Australia: Time 18:51 Date 2005-02-14 of tell number of rows in each block). Preferably, also square blocks are used so that the block dimensions are K x K. However, rectangular blocks can also be used.
Preferably, the decoding method uses an external memory buffer of 3K lines for each intermediate LL subband. That is, for a J level DWT, the decoding method uses LL1. LL2, and LL(J-I) buffers, each having 3K lines, where the line length is the length of the LLj subband. Further for each level, the decoding method uses a 2 line buffer which is referred to herein as a col_overlap buffer, and which contains the vertical lifting state between subband block quadruples. The line length for this buffer is the length the LL subband lines at the next lower level. Thus the col_overlap buffer for level 1 has a line length the same as the line length of the output image.
Preferably, the decoding method uses four internal memory buffers each of size K x K which are referred to herein to as LL, HL, LH and HH block buffers. There are two additional internal memory buffers. One comprising 2 columns by 2K rows, which is referred to herein as row_overlap buffer (which contains the horizontal lifting state between subband block quadruples), and one comprising 2 rows by 2K 3 columns which is referred to herein as the col_overlap (internal) buffer.
For some applications, depending on the image line length, it may be possible that the external col_overlap buffer is a local memory buffer. In this case the internal col_overlap buffer is not needed. Further, for a general purpose computer these buffers may not explicitly be designated as external or internal. The idea is that data held in internal buffers is held in the processor cache, and hence is accessible more quickly than data in external memory. In this way some buffers may operate as external and internal buffers at different times.
The decoding method in accordance with the preferred implementation is based around a single level two-dimensional iDWT engine that processes nominally K subband lines, for each of the four subbands at levelj, and produces nominally 2K lines of LL(j-1) data. As explained above the correspondence between these input K subband lines and output 2K lines is not exact. However, by maintaining some overlapping data we can 602062.doc usually produce 2K subband lines for K lines input for each of the level j subbands.
Turning now to Fig. 7, the decoding method can be described with reference to a flow chart which begins at Step 710 by decoding the compressed image header. From the header, image information such as size, number of DWT levels employed, and entropy coding block size are determined.
At step 720 a loop is entered that terminates when there are no more image lines to decode. Normally 2K image lines are decoded and output per iteration. For the first iteration only 2K-3 lines are decoded and for the last iteration up to 2K+3 lines are decoded. To obtain 2K image lines, (at least) K lines for each of the level one subbands are required. The K lines for the AC subbands can be obtained by decoding the appropriate row of blocks in each AC subband. But the decoding method still need K lines from the LL1 subband. If the LL1 buffer has less than K lines in it the decoding method needs to process the level two subbands, with the single level iDWT engine, to fill the LLI buffer with more lines, which in turn requires that the LL2 buffer has at least K lines in it. If this is not the case, the decoding method needs to process K lines of the level 3 with the single level iDWT engine subbands and so on. Step 730 then determines the highest such DWT level needed to be processed. Given a J level DWT,j_max is the smallest integer less than or equal to J such that the LL1, LL2, LL(j_max-1) buffers each have less than K lines of data in them, while LL(/_max) has at least K lines in it. If all the LL buffers have less than K lines in them thenj_max is J, as is the case for the first iteration.
At step 740 a loop is entered that iterates fromj =j_max toj 1, decrementingj by one at each iteration. At each iteration the decoding method processes, with the single level iDWT engine, substantially K lines of each of the four subbands at levelj producing nominally 2K lines of the LL(j-1) subband. The K lines the decoding method processes are the K lines in the first unprocessed row of blocks in the level j subbands. In other 602062.doc -26words, for a given levelj each time this loop is entered the decoding method processes the niext row ofblocks.
At step 745 a loop is entered that iterates over the number of blocks per row of blocks for the subbands at level j. At step 750, block k in the current row of blocks is decoded for each of the HL, LH and HH subbands and the data placed in the (K x K) HL, LH and HH local memory buffers. At step 755, the corresponding (K x K) block of LL data is put into the LL local memory buffer either by decoding block k in the current row of blocks in the LL/subband (in the case thatj or by reading the data from the LLj external memory buffer. At Step 760, the next 2K columns are read from the external col_overlap buffer into the internal col_overlap buffer. At Step 765, the four block buffers, LL, HL, LH and HH, and the row and col overlap internal buffers are then inverse transfornned with a single level iDWT to produce nominally a 2K x 2K output block of coefficients at level j-1. Figs. 8 and 9 illustrate the operation of Step 765 in more detail.
At Step 770, the intermediate row subband data needed for the next block in the current row of blocks is buffered in the internal row_overlap buffer. Similarly the intermediate column data that is needed for inverse transforming the block immediately below the current block in each subband is buffered in the col_overlap external buffer. At Step 775, the nominally 2K x 2K output data block is written to the buffer.
The synthesis of a subband block quadruple in Step 765 is explained further with reference to Fig. 8. In Step 801 the process of Fig. 8 commences. In decision block 810 a test is made to deternine if the AC horizontal lifting state for the current subband block quadruple is zero, ie H-Lcur, Hhcur, XLO, XHO are all zero. If decision block 810 returns true processing continues at Step 820. If decision block 810 returns false processing continues at Step 850.
In Step 820 a test is made to determine if the AC vertical lifting state for the current subband block quadruple is zero, ie Xlprev and Xhprev are all zero. This test preferably involves testing the AC lifting state for each column in the subband block quadruple. If 602062.doc decision block 830 returns true processing continues at Step 840. Otherwise processing continues at Step 850.
In Step 840 a zero speed-up inverse DWT procedure is selected as the procedure for performing the inverse DWT of the subband block quadruple. In Step 850 the default inverse DWT procedure is selected as the procedure for performing the inverse DWT of the subband block quadruple. In Step 860 the inverse DWT of the subband block quadruple is performed using the selected procedure.
The inverse DWT of the subband block quadruple of step 860 is now described with reference to Fig.9. This procedure describes both the default and zero speed-up inverse DWT procedures. Processing commences in Step 901.
In Step 910, a loop is entered that loops over the rows of the subband block quadruple. For K x K blocks there are K row iterations. In Step 920, a loop is entered that loops over the columns of the subband block quadruple. In Step 930, a 2x2 output image block is synthesized by performing the inverse DWT procedure of the current subband coefficient location that is of the current Ixl subband block quadruple. For the zero speed-up method this is preferably implemented as described by the zero speed-up pseudo-code described above. For the default method this is preferably implemented as described by the default pseudo-code described above.
After the column iterations have finished, (at the end of each row iteration) the horizontal lifting state is updated in Step 940, for the next horizontally adjacent subband block quadruple. In Step 950 a zero horizontal AC lifting state flag, for the next horizontally adjacent subband block quadruple is updated to reflect if any relevant lifting state is non-zero. This flag is tested in Step 710 of Fig. 7 to determine if the relevant horizontal lifting state is zero.
The aforementioned decoding method described with reference to Figs. 7 to 9 is preferably based on the reversible 5/3 or on the 9/7 wavelet filter of the type described in the JPEG2000. In the case where the 5/3 wavelet filter is used, Figs. 8 and 9 are preferably implemented as described by the C code in Appendix A.
602062.doc -28 Preferred Implementations of Apparatus and Computer Program The method of performing a two-dimensional inverse discrete wavelet transform on a digital image in accordance with the preferred implementation are preferably practiced using a conventional general-purpose computer system 1000, such as that shown in Fig. 10 wherein the method are implemented as software, such as an application progranm executing within the computer system 1000. In particular, the steps of the method are effected by instructions in the software that are carried out by the computer Appendix The software may be divided into two separate parts; one part for carrying out the discrete wavelet transform method; and another part to manage the user interface between the latter and the user. The software may be stored in a computer readable medium, including the storage devices described below, for example. The software is loaded into the computer from the computer readable medium, and then executed by the computer. The use of the computer readable medium in the computer preferably effects an advantageous apparatus for performing the preferred method in accordance with the implementations of the invention.
The computer system 1000 comprises a computer module 1001, input devices such as a keyboard 1002 and mouse 1003, output devices including a printer 1015 and a display device 1014. A Modulator-Demodulator (Modem) transceiver device 1016 is used by the computer module 1001 for communicating to and from a communications network 1020, for example connectable via a telephone line 1021 or other functional medium. The modem 1016 can be used to obtain access to the Internet, and other network systems, such as a Local Area Network (LAN) or a Wide Area Network (WAN).
The computer module 1001 typically includes at least one processor unit 1005, a memory unit 1006, for example formed from semiconductor random access memory (RAM) and read only memory (ROM), input/output interfaces including a video interface 1007, and an I/O interface 1013 for the keyboard 1002 and mouse 1003 and optionally a joystick (not illustrated), and an interface 1008 for the modem 1016. A storage device 1009 is provided and typically includes a hard disk drive 1010 and a 602062.doc -29floppy disk drive 1011. A magnetic tape drive (not illustrated) may also be used. A CD- ROM drive 1012 is typically provided as a non-volatile source of data. The components 1005 to 1013 of the computer module 1001, typically communicate via an interconnected bus 1004 and in a manner, which results in a conventional mode of operation of the computer system 1000 known to those in the relevant art. Examples of computers on which the implementations can be practised include IBM-PC's and compatibles, Sun Sparcstations or alike computer systems evolved therefrom.
Typically, the application program of the preferred implementation is resident on Ihe hard disk drive 1010 and read and controlled in its execution by the processor 1005.
Intermediate storage of the program and any data fetched from the network 1020 may be accomplished using the semiconductor memory 1006, possibly in concert with the hard disk drive 1010. In some instances, the application program(s) may be supplied to the user encoded on a CD-ROM or floppy disk and read via the corresponding drive 1012 or 1011, or alternatively may be read by the user from the network 1020 via the modem device 1016. Still further, the software can also be loaded into the computer system 1000 from other computer readable medium including magnetic tape, a ROM or integrated circuit, a magneto-optical disk, a radio or infra-red transmission channel between the computer module 1001 and another device, a computer readable card such as a PCMCIA card. and the Internet and Intranets including email transmissions and information recorded on websites and the like. The foregoing is merely exemplary of relevant computer readable mediums. Other computer readable mediums may be practiced without departing from the scope and spirit of the invention.
The preferred method in accordance with the implementations may alternatively he implemented in dedicated hardware such as one or more integrated circuits performing the functions or sub functions of the method. Such dedicated hardware may include graphic processors, digital signal processors, or one or more microprocessors and associated memories.
Industrial Applicability 602062.doc It is apparent from the above that the implementation of the invention is applicable to computer graphics, digital communication and related industries.
The foregoing describes some implementations of the present invention, and modifications and/or changes can be made thereto without departing from the scope and spirit of the invention, the implementations being illustrative and not restrictive.
In the context of this specification, the word "comprising" means "including principally but not necessarily solely" or "having" or "including" and not "consisting only of'. Variations of the word comprising, such as "comprise" and "comprises" have coTresponding meanings.
602062.doc AP3PENDIX A C code implementation ofthe 5/3 irreversible DWT block engine usinlg the standard method, or if possible calling the zero speed-tip method.
define ROUND LP 2 METI-IODDE FEXTERN(void) L53_BLOCKENGINEFN theccj2(_tile_decoder pt r ci 1 fo, j2k_ idw\tblock enlgiinept self, JVOIDARRAY oUtput_data, J1DIMIENSION start row, IDIMENSION start col, JDIMENSION blockheight, JDIMENSION block-width, JVOIDARRAY vert liftmem, booleai is first block row, boolean is First blockcol, J VOIDARRAY horiz liftmerm, .IVOIDARRAY ipLLbuf, JDIMENSION ipLLli ne_offset, JCOEFARRAY EC HLblock, JCOEFARRAY EC LHblock, ICOEFARRAYEC -IHblock, OPLLDATATYPE op_LL_datatype, boolean isAC blocks-zero, JUI3YTE *is lp_ horiz_liftstate-zero, JUBYTE *ishpvert_lift_statezero, JF17 LOAT *qstep) IDIMENSION opdelay 1; OUTPUTARRAYTYPE opLL-array (OUTPUT_ARRAY_TYPE) OLIputdata startrow op delay; OUTPUTROWTYPE xl; OUTPUTROWTYPE x2; i1NT32 is hIs nonzero 0; ildf USERANGELIMIT myidwtblock_engineptr idwtbe (my idwiblockengineptr) self, ISAMPLE *rangejlimit idwtbe->j sample range lmt table; lenclif NOTE: Onl a pentium mlt arithmetic is much faster than short iril arithmetic 602062.doc Ihus \We want to do the arithmietic with int's and not short ints. Thuls the following variables are JINTJ2 (ii on a pentium) to force Hit arithmetic regardless of whether JCOEF_ SC is of type int or short int.
*1
S
II XLI is coef XL(nm-1,2n+i), and similarly XH i 's coef XH(m+1,2n+i).
JINT32 XHO 0, XH1 0, X2 0; JINT3~2 XH-O 0, XH 1 0= XH2 0; J1NT32 ULcur, lHcur; HLcur HL[n+I I-I-cur HH[rn+l,n].
.IINT32 fl1Lnext, LI-Inext, lInext; INPUT LLBUF ROW TYPE LL- JCOEFRO\EC IL; JCOEFROW EC LH; JCOEFROW EC IIH; SXHPi-rev points at row ii of XH, and similarly XLprev points at row m of XL JCOEFROWEC XHprev (J COEFROW_EC)vertlift rnen[o] startcol; .ICOEFROWSC XLprev (JCOEFROW_EC)vertliftrnem[l]I start coP, .ICOEFRO\VEC horizitxLprev (JCOEFROW EC)horizlift_memO]; JCOEFRO\_SC horizitx Hcur (ICOEFROW EC)horizlift_mem[1];
I,
We can do a faster idwt if the AC coefficients are zero. We check for this case, and if possible we do it *1 if(is-ACblockszero *ishphriz_li ftstate zero) .11NT32 is-vls-nonzero=0, //Check vertical lifting state for (n n (inl) block_width-I1 is vlsrnonzero 1= (XHprev(2*nl] I XHprev[2*n+2]); if(isvlsv nonzero 0) if(opLLdara_type ENUMJSAMPLE) //printf("Doing fast zero AC idwt\n"); L53_coefsanpzerohf iblock engine (cinfo, self, output_data, startrow, startcol, block heighr,block_width, venliftene, isfirstblockrow, isfirstblockcol, horiz_lift_mern, ip_LLbuf, ip_LL_line_offset, FILblock, LHblock, HHblock, op_LL_data_type, isACblockszero, is hphonizliftstatezero, ishpvcrtlft state zero, qslep); return; else L-53_coefcoefzerohfi block_ engine (cinfo, self, output_data, startrow, startcol, block heght,block_width, vertliftiern, isfirstblock_row, isfrjstblockcol, horizliftmem, ip_LLbuf, ip_LL_line_offset, HLblock, LHblock, HHblock, opLLdatatype, isACblocks_zero, is hp hoizliftstatezero, 602062.doc is hp vert_ liftstate_zero, qstep); retRu'll; Initiliase the vertical lifting state (X-Iprev only) for the first iteration on m We need to generate XHprev[2n+1], XHprev[2n+2] for n -1,0,..block_width- I1, for the verical synthesis of row m+ I 0 below.
We do not need to generate XLprev, as this does not effect the first row (XHprev here is row -1).As XHprev contains pre-update values we only need do the inverse row transformion (as in producing XH I and XH2, for n -1,0,..blockwidthi-1.) if(is first_block row) I First update the inverse row transformn values LH LHblock[0]; HH HI-block[0]; Generate horizontal lifting state to effect a symmni. extension if(isfiri-stblock col) XHO- 0; we don't care here SIGN MAG_ TWOS_COM P LIMENT_CONVERSION(HHcur, HH[0],
JCOEF_EC_MIN);
i else 1/ Get horizontal lifting state from buffer XHO horiz_itx_Lprev[ //Highpass row is in row 2nm+ HHcur horiz_itx_Hcur[l]; for (n n (int)block_width-1; 4 SIGN_MAG_TWOS_COM P LIMENT_CONVERSION(LHnext, LH[n+I],
JCOEFEC_MIN);
SIGN_MAG_TWOS_COMPLIMENT_CONVERSION(HHnext, HH[n+1], JCOEFEC_ MIN); XI-prev[2*n+2] (JCOEFEC) (LHnext ((HHcur HHnext ROUND_LP) XH2 value XHprev[2*n+1] (JCOEF_EC) (HHcur ((XHO XHprev[2*n+2]) XHl value XHO XHprev[2*n+2]; Update for next interation (on n) HHcur HHnext; else //Li fting state was intialised when block above was synthesized We set x I, an output row pointer, so that for m -1 (overlap 1) it points at the first available output row. Lines pointed at by x2 and for 602062.doc x I follow in order from there. We also offset xl and x2 by start_col (which equals 21W see the calling function extractlines method of a single level iDWT object) so that as we are really generating ouLtpult data points (2kH+2n+1, 21W+2n+) etc.
for (m min (int) block_height- ii// Set input and output row pointers x I op_LL_array[2*m+ I] start_col; x2 op_LL_array[2*m+2] startcol; Point LL, HIL, LH and HH so that we access row kH+m+l in each subbands, and then samples lW+n+1(2) in this row.
LL (INPUT LLBUF_ROW_TYPE)ip_LLbuf[m+1]; LL ip_LL_line_offset; IHL HLblock[ni+ Offset pointers by the scan row LH LHblock[m+1]; HH =HHblock[m+]; //Initialise the horizontal lifting state for the first iteration if(is_first_block_col) don't need XLO and XHO, because we don't care about op satnp -1 here X LO 0; XHO 0; SIGNMAG TWOS_COM P LIMENTCONVERSION(HLcur, HL[0],
.JCOEF_EC_MIN);
SIGN_MAG_TWOS_COMPLIMENT_CONVERSION(HHcur, HH[O0,
JCOEF_EC_MIN);
else "Current" row being synthesized is row m+I, hence get state from rows 2(m+1)=2mr+2 and 2m+3 XLO horiz_i tx_Lprev[2*m+2]; XHO horiz_itxLprev[2*mn+3]; HLcur horiz_itx_Hcur[2*m+2]; HHcur horiz_itx_Hcur[2*m+31; for (n n (int) blockwidth 1; SIGNMAG _TWOSCOMPLIMENTCONVERSION(HLnext, HL[n+l], JCOEFEC MIN); XL2 LL[n+ I] Lcur HLnext ROUND_LP) 2); XL1 HLcur ((XLO+ XL2) 1); HLcur H[Lnext; Updates for next iteration across row (on n) XLO XL2; Horizontal sythesis of LH and HH SIGNMAGTWOSCOMPLIMENTCONVERSION(LHnext, LH[n+1], J.ICOEF EC MIN); 602062.doc 35 SIG NMAGTWOSCOM PLIM ENTCONV ERS ION(H Hnext, HHj[n-4-],
.ICOIT--_EC_MIN);
XI-12 LI-nexr ((H-HCUr U~nexi ROUND_LP) 2); XII I HHcur ((XHO XI-2) l-l-cur1 HHnext; Updates for next iteration across row (onl n) XI-1 XH-2; Vertical synthesis of XL and XH, colunn2ntx2[2*i+ I]J= RANGE-LIM IT XLI ((XHprevt2*n±]J XH1 ROUNDLP) >2) x 1r2*n+ I] RANGE-LIM IT XI~prev[2*ni+I ((XLprev[2*ii+lI1 x2[2*nrl]) 1) /Update for next iteration down COIL11mO1 (Onl 11) XHpr-ev[2*n+t] (JCOEF_EC) XHl1; XLpIrevL2*a+ 1] x2[2*nif+]]; Vertical synthesis of XL and XH, column2n42 x2t2*ii±2] RANGE-LIM IT XL2 ((XHprev[2*ni+21 XH2 +1 ROUNDLP) 2) xl1[2 RANGE-LIM IT XI~pr-ev[2*n±+2] ((XLprev[2*ni+2] x2[2*n+2]) 1) il Update for next iteration down coIlumrn (on mn) XHpr-ev[2*n+2] (JCOEF_[C) XH2; XLp~rev[2*n+2] x2[2*ni+2J; 1 *Update the horizontal lifting memory for the next block *(noting LI1 XLI etc have been updated at the end of the above l oop across row elements) horizijtxLprev[2*ni±2] =(JCOEF -EC) XLO; horizicxLprev[2*ni±3] (ICOEF E) XHO; horiz itx HCr[2*mi+2] =(JCOEF -EC) H Leur; horiz itx Hcur[2 =(JCOBF EC) H Heur; isIds nonzero H= (XHO IHLcur I HHcur);- *ishlp horix lift-state-zero (J1UBYTE)(is h~s-nonzero 0); 602062.doc C code implementation olthe 5/3 irreversible DWT block engine using zero speed-ip method (implements L53coefsampzeroh-ifiblockengilne anid L53_coef'sampzerolif block_engine.
c, kdefine ROUNDLP 2 iMETHODDEFEXTERN(void) L53_BLOCKENGINEFN thj2kIiledecoder pir cinfo, j2kidwtblock engine ptr self, .IVOIDARRAY output _cat, JDIMENSION start row, JDIMENSION start col, JDIMENSION blockheight, JDIMENSION block %width, JVOJDARRAY vert liftmem, boolean is first block row, boolean isFirst block col, iVOIDARRAY horizifimem, IVOIDARRAY ipLLbuf, J.D IMENSION ipLL l_1ine_offset, JICOEF-ARRAY lEG -ILbock, JCOEFARRAY EC LHblock, JCOEFARRAY EC HHblock, OPLDATA TYPE opLLdata type, boolean isPACblokszero JUBTE *s ip Iiizlo i ftstat ezero JUBYTE *islhpveriot_ ift state zero, JFLOAT *qstep nyidt_block_engine pir idwtbe (my idwiblock engineptr) self; int int n .IDIMENSION op delay 1; OUTPUTARRAYTYPE opLL -array (OUTPUTARRAY TYPE) output data start row op dely; OUTPUTROWTYPE xl; OUTPUTROWTYPE x2; ifdef USE-RANGELIMIT JSAMPLE *range limit idwtbe->jsample range limit_table; fiendif 1* 602062.doc 37 NOTE: On a pentium int arithmetic is much faster than short int aritlmetic. Thus we want to do the arithmetic with int's and not short inlts. Thus the following variables are JINT32 (int on a pentium) to force int arithmetic regardless of whether JCOEF_EC is of type int or short int.
1* XLi is coefficient XL(mi1,2n+i), and similarly XHi is coefficient XH(n+1,2n+i).
*1 JINT32 XLO= O, XL1= XL2= 0; JINT32 XHO= 0; JINT32 H-ILcur, HHcur; HLcur= HL[mi+-l,n], HHcur= HH[m+l,n].
INPUT LLBUFROWTYPE LL; XHprev points at row m of XH, and similarly XLprev points at row m of XL JICOEFROW_EC XHprev (JCOEFROW_EC)vert_lift rnmem[O] startcol; JCOEFROW_EC XLprev (JCOEFROW_EC)vert_lift_men[1] startcol; JCOEFROW_EC horiz_itx_Lprev (JCOEFROWEC)horiz_lift_mem[0]; JCOEFROW_EC horiz_itx_Hcur (JCOEFROWEC)horiz_liftmemlr i]; Initiliase the vertical lifting state (XHprev only) for the first iteration oil m We need to generate XHprev[2n+], XHprev[2n+2] for n -1,0,..block_width- I1, for the vertical synthesis of row m+ I 0 below. We do not need to generate XLprev, as this does not effect the frst row (XHlprev here is row -1).As XHprev contains pre-update values we only need do the inverse row transformion (as in producing XHI and XH2, for n -l,0,..block_width-1.) if(is_first_block row) First update the inverse row transform values if(is_first_block col) Generate horizontal lifting state to effect a symm. extension XHO 0; we don't care here HHcur 0; else Get horizontal lifting state from buffer XHO= horiz itx_Lprev[]; //Hl-Iighpass row is in row 2rn+1 HHcur horiz_itx_Hcur[ I]; for (n n (int)block_width 1; XH2 value XHprev[2*n+2] (JCOEFEC)((HHcur 0 ROUND_LP) 2); 602062.doc XH I value Xi1prev[2*n+I] (JCOEFEC)(HHcur ((XHO XHprev[2*n+2]) Update for next interation (on n) XHO XHprev[2*n+2]; lHHcur 0; else Lifting state was intialised when the block above the current 1/ block was synthesized We set x 1, an output row pointer, so that for in -1 (overlap I) it points at the first available output row. Lines pointed at by x2 and for xl I follow in order from there. We also offset xl I and x2 by start_col (which equals 21W see the calling function extractlines method of a single level iDWT object) so that as we are really generating output data points (2kH+2m+l, 21W+2n+1) etc.
for (mi mi (int) block_height-; Set input and output row pointers NI op_LL_arrayf2*i+ I start_col; x2 opLL_array[2*m+2] startcol; Point LL, H-L, LH and HHl so that we access row kH+m+1 in each subbands, and then samples lW+n+1(2) in this row.
LL (INPUT LLBUF_ ROW_TYPE)ip_LLbuf[mn+l]; LL ipLL line_offset; f/Initialise the horizontal lifting state for the first iteration across the rows if(is_first_block_col) I //We don't need XLO and XHO, because we don't care about output sample -1 in this case XLO 0; XH 0 0; I-IHLcur 0; HL[0] (Symmetric extension condition) I-IHcur 0; -IH[0]; else "Current" row being synthesized is row mn+l, hence get state from rows 2(rm+l )=2m+2 and 2m+3 XLO horizitx_Lprev[2*m+2]; XHO= horiz itx_Lprev[2*m+3]; HLcur horizitx_Hcur[2*m+2]; H Hcur horizitxHcur[2*m+3]; 602062.doc 39 F'or (ni n tit) blIock_width-] I; X L2 L L~n+l11; XL1 +XL2) XLO XL2; IHorizontal sythesis of LU and HH Nothing to do here IVertical synthesis of XL and XH, columin2n+1 x2[2*ii~l1] RANGELIMIT(XL1); xl1[2*tn±1] RANG ELIM IT(((X Lprev[2* n+1] x2[2*n~l) XLprev[2*nil] x2[2 4 n-T-l]; Vertical synthesis of XL and XI-, colLlmn1n+2 x2F2*ni+2] RANGELIMIT(XL2); x I RANGELIMIT(((XLprev[2*ni+21 x2[2*nii+2) XLprev[2*in+2J x2[2*n+21; *Update the horizontal lifting memory for- the next block (noting Li= XLI etc have bee n u tpdated at the end of the above loop across row elements) horizitxLprev[2*vt2] (JCOEFEC) XLO; hiotizitxLprev[2rni+3] 0; hoiz itxHcur[2*rn±2] 0; horiz_itx_Hcur[2 4 mn+3] 0; /1Zero vertical (highpass) lifting state i f(blockj height 0) for (n 1; n (int) block -width- 1; XHprev[2*tn+l] 0, Xflprev[2*ii+2] 0; 602062.doc