AU747603B2 - A method and apparatus for discrete wavelet transforms for block entropy coding of subband image data - Google Patents

Description

S&F Ref: 527050

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 and Dominic Yip Spruson Ferguson St Martins Tower 31 Market Street Sydney NSW 2000 A Method and Apparatus for Discrete Wavelet Transforms for Block Entropy Coding of Subband Image Data ASSOCIATED PROVISIONAL APPLICATION DETAILS [33] Country [31] Applic. No(s) AU PQ4433 [32] Application Date 03 Dec 1999 The following statement is a full description of this invention, including the best method of performing it known to me/us:- Documents received on: f B- 27 NOV 230 Ci Batch No: 5815c A METHOD AND APPARATUS FOR DISCRETE WAVELET TRANSFORMS FOR BLOCK ENTROPY CODING OF SUBBAND IMAGE DATA FIELD OF INVENTION s The present invention relates to the field of digital image compression and in particular, to a method and apparatus for performing a wavelet decomposition of an image.

DESCRIPTION OF BACKGROUND ART The field of digital data compression and in particular digital image compression has attracted great interest for some time. Most recently, compression schemes based on a Discrete Wavelet Transform (DWT) have become increasingly popular because the DWT offers a non-redundant hierarchical decomposition of an image, and resultant compression of the image provides favourable rate-distortion statistics.

THE DISCRETE WAVELET TRANSFORM 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 20 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 ofN samples there are NDWT samples: N/2 lowpass samples and N/2 highpass samples.

A single level DWT of an image is typically performed by buffering the entire image in memory and performing the DWT on the buffered image. Unfortunately, this approach requires a large amount of memory, particularly for image of 2000 pixels x 2000 pixels or more. Thus a relatively large amount of (slower) external memory is required. The reference to external memory, should be construed, unless otherwise stated, throughout this document, as denoting off-chip memory, that is, memory external to the processor chip performing the DWT (or Inverse DWT denoted as iDWT). Further, several write and read accesses to and from this slower external memory are required to CFP 1909AU(TANDARD 08) [I:\ELEC\CISRA\Standard\Standard08]527050Spec.doc:SDB -2several write and read accesses to and from this slower external memory are required to perform the DWT. These accesses then restrict the speed at which the whole DWT can be performed.

SUMMARY OF THE INVENTION According to a first aspect of the invention, there is provided a method of decoding a compressed bit stream, the compressed bit stream being derived from a discrete wavelet transform image comprising a low-low frequency subband and a plurality of high frequency subbands, each subband being divided into plurality of blocks and each block substantially independently entropy encoded into the compressed bit stream, the method comprising the steps of: a) entropy decoding a current block for each high frequency subband at a current level; b) storing the entropy decoding blocks in to a first (fast) memory; c) if the current level is a highest level of the discrete wavelet transform image: ca) entropy decoding a corresponding block of the low-low frequency subband of the current level and storing the block into a first (fast) memory; otherwise cb) extracting a corresponding low-low frequency subband block, for the i 20 current level, from a second (slow) memory and storing the extracted block into the first (fast) memory; d) performing an inverse discrete wavelet transform upon each block of subband coefficients at the current level, stored in the first (fast) memory, to produce a block of coefficients of a low-low subband at one level below the current level; 25 e) storing the produced low-low block of coefficients in the first (fast) memory; f) entropy decoding high frequency subband blocks, at a level one below the current level, substantially spatially corresponding to the produced low-low block of coefficients, into the first (fast) memory; g) performing an inverse discrete wavelet transform upon each of the high frequency blocks at one level below the current level and the produced low-low block of coefficients at one level below the current level, to generate a block of coefficients of a low-low subband at two levels below the current level; and CFP1909AU(STANDARD 08) [:\ELEC\CISRA\Standard\Standard08]52705Spec.doc:SDB h) storing the generated block of low-low subband coefficients into the second (slow) memory.

According to a second aspect of the invention, there is provided a method of encoding an image, said method comprising the steps of: performing a discrete wavelet transform on a first block (portion) of said image to produce a (second) block of each of a LL, HL, LH and HH subband data at a current level and storing said produced blocks in a first (fast) memory; entropy coding the HL, LH and HH (second) blocks; performing a discrete wavelet transform on said second LL block to produce a (third) block of LL, HL, LH and HH coefficients at one level below the current level, and said third HL, LH, HH blocks being stored in said first (fast) memory; storing the third LL block in a second (slow) memory; and entropy coding said HL, LH and HH (third) blocks.

According to a third aspect of the invention, there is provided a method of encoding an image into a compressed bitstream, said image being divided into a plurality of blocks (portions), said method comprising the steps of: 20 performing a discrete wavelet transform on a first block (portion) of said image to produce a first Low-Low frequency subband and a first plurality of high frequency subband data, for said first block, at a current level and storing said produced blocks in a first (fast) memory; entropy coding the first plurality of high frequency subband data for said first 25 block at a current level into a bitstream; performing a discrete wavelet transform on said first Low-Low frequency subband data for said first block to produce a second Low-Low frequency subband and a second plurality of high frequency subband data, for said first block, at one level below the current level, said second plurality of high frequency subband data being stored in said first (fast) memory; storing the second Low-Low frequency subband in a second (slow) memory; and entropy coding said second plurality of high frequency subband data into the bitstream.

CFP I909AU(STANDARD 08) [:\ELEC\CISRA\Standard\Standard08]527050spec.doc:SDB According to a fourth aspect of the invention, there is provided an apparatus for implementing any one of the aforementioned methods.

According to a fifth aspect of the invention there is provided a computer program product including a computer readable medium having recorded thereon a computer program for implementing any one of the methods described above.

BRIEF DESCRIPTION OF THE DRAWINGS to Notwithstanding any other forms which may fall within the scope of the present invention, preferred forms of the invention are described hereinafter, by way of example only, with reference to the accompanying drawings in which: Fig. 1 is a block diagram illustrating a row of blocks in each subband of a DWT image; Fig. 2 is a schematic representation of a lifting lattice for inverse DWT of 9/7 filters; Fig. 3 is a flow chart ofa single level iDWT; Fig. 4 is a block diagram showing a single level DWT and iDWT of an image as a series of one-dimensional transforms; 20 Fig. 5 is a block diagram showing a correspondence between blocks in the LL and HL subbands and the Lc sub-image; Fig. 6 is a block diagram showing a correspondence between blocks in the Lc subimage and Hc sub-image and the original image; Fig. 7 is a flow chart of a two-level engine based iDWT; Fig. 8 is a flow chart of a two-level iDWT block engine; Fig. 9 is a schematic representation showing a 9/7 filter implementation using a lifting scheme; Fig. 10 is a block diagram showing how the original image is transformed into LL, HL, LH, HH subbands, and vice versa; Fig. 11 is a block diagram showing in detail how the original image is transformed into Lc and Hc sub-images row-block by row-block; Fig. 12 is a block diagram showing in detail how the Lc sub-image is transformed into LL and HL subbands block by block; UFP1909AU(STANDARD 08) [I:\ELEC\CISRA\Standard\StandardO8]527050spec.doc:SDB Fig. 13A is a flow diagram illustrating the two level engine based DWT of an image; Fig. 13B is a flow diagram illustrating the process of transforming the original image into the 4 subbands; Fig. 14 is a block diagram illustrating preferred embodiment of the present invention; Fig. 15 is a block diagram showing in detail how input samples are transformed by the preferred embodiment of the present invention; Fig. 16 is a block diagram showing the various subbands in a 2-level DWT transform; Fig. 17 is a flow diagram illustrating the overlap read-back method of the preferred embodiment; Fig. 18 is a flow diagram illustrating the initialisation of the first level intermediate results buffer, second level intermediate results buffer, and the subband buffer; Fig. 19 is a flow diagram illustrating the DWT step on a row-block of the original samples in the first level DWT unit; Fig. 20 is a flow diagram illustrating the Lc row-DWT step in the first level DWT unit in Fig. 19; 20 Fig. 21 is a flow diagram illustrating the He row-DWT step in the first level DWT unit in Fig. 19; Fig. 22 is a flow diagram illustrating the operation of the second level DWT unit; Fig. 23 is a flow diagram showing the Lc row-DWT steps in the second level DWT unit in Fig. 22; 25 Fig. 24 is a flow diagram showing the He row-DWT steps in the second level DWT unit in Fig. 22; Fig. 25 is a flow diagram illustrating the redundant source read method of the preferred embodiment; Fig. 26 is a flow diagram showing how the first row-block is processed; Fig. 27 is a flow diagram showing how the subsequent row-blocks are processed; Fig. 28 is a flow diagram showing the Lc row-DWT step in the first level DWT unit in Figs. 26 and 27; CFP 1909AU(STANDARD 08) [1:\ELEC\CISRA\Standard\Standard08]527050spec.doc:SDB -6- Fig. 29 is a flow diagram showing the He row-DWT step in the first level DWT unit in Figs. 26 and 27; Fig. 30 is a flow diagram showing the operation on the first row-block of the second level DWT unit in the redundant source read method; s Fig. 31 is a flow diagram showing the operation on the subsequent row-blocks of the second level DWT unit in the redundant source read method; Fig. 32 is a flow diagram showing the Lc row-DWT step in the second level DWT unit in Figs. 30 and 31; Fig. 33 is a flow diagram showing the He row-DWT step in the second level DWT unit in Figs. 30 and 31; Fig. 34 is a block diagram of a single level based iDWT; Fig. 35 is a block diagram of a two-level based iDWT; and Fig. 36 is a block diagram of a general purpose computer with which embodiments of the invention can be practiced.

DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION A method, an apparatus, and a computer program product are disclosed for decoding a compressed bitstream derived from a discrete wavelet transform image. The image comprises a low-low frequency subband and a number of high frequency subbands.

20 Each subband is divided into a number of blocks, which are each substantially independently entropy encoded into the compresed bitstream. Similarly, a corresponding method, apparatus, and computer program product for encoding such a compressed bitstream are disclosed. In the following description, numerous specific details are set forth. However, it will be apparent to those skilled in the art, in view of this disclosure, 25 that changes may be made without departing from the scope and spirit of the invention.

Throughout this specification a reference to any one of the italicised terms listed below is to be construed as stated below, unless contrary intentions appear.

The term "image" is to be construed 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 CFP1909AU(TANDARD 08) [1:\ELEC\CISRA\Standard\Standard08]527050spec.doc:SDB -7spatial 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.

The term "analysis" is to be construed as a forward DWT decomposition of an image, and the term "synthesis" as the inverse DWT of an image. Variations on theseterms such as "analysising", "analysed", "synthesising" and "synthesised" have corresponding meanings.

ARRANGEMENT OF DISCRETE WAVELET TRANSFORM DATA to Fig. 4 illustrates the process of performing a single level two-dimensional DWT of an input image 400. Each column of the image is analysed with a one-dimensional DWT resulting in output columns comprising low-pass and high-pass samples. The preferred arrangement, in accordance with the preferred embodiment, is that each of the resulting output columns comprises two parts, a first part has lowpass samples and second part has or consists ofhighpass samples. Thus, the analysis of each column of the input image, collectively, results in two sub-images labelled L and Hc. The columns of L has or consists of the lowpass filtered (and decimated) samples of the input image and the columns of HC has or consists of the highpass filtered (and decimated) columns of the input image. This column analysis of the input image 400 is denoted in Fig. 4 as "col 20 DWTs", and results in image 401 made up of two sub-images LC and Hc.

Similarly, rows of the resulting output image 401 are then analysed with a onedimensional DWT (denoted as "row DWT") as shown in Fig. 4. The row DWT analysis upon the image 401 results in four sub-images or subbands 402, which are each labelled S 25 by a two letter label LL, HL, LH and HH, where L and H refer to lowpass and highpass respectively. In the two letter label, the first letter represents row filtering and the second represents column filtering of an image. 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 often referred to as 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 of an image is referred to as a single level DWT (or even simply DWT) of an image.

CFP 1909AU(TANDARD 08) [I:\ELEC\CISRA\Standard\Standard08]527050_spec.doc:SDB -8- For the purpose of clarity, the description given herein assumes that the, columns are transformed first followed by the rows for the forward DWT on analysis), and that the rows are inverse transformed first, followed by the columns for the inverse DWT on synthesis). However, provided there is consistency the synthesis is performed in reverse order to the analysis), the order in which rows and columns are processed does not substantially affect the result of the DWT or iDWT of an image.

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 o0 these subband samples, of which there are N in total, can be synthesised with a onedimensional inverse DWT back into the original N samples of the one-dimensional signal.

Thus by synthesising rows and then columns of a single level DWT image the original image can be reconstructed. This is also illustrated in Fig. 4 by "row iDWTs" and "col iDWTs" representing the row then column synthesis of the DWT image 402. Thus a single level (two-dimensional) DWT is invertible.

To create a two-level DWT, the LL subband of a single level DWT image is further analysed with a DWT into four subbands, just as the original image was analysed into four subbands to produce the single level DWT image. Thus, the steps to achieving 20 the four subbands from the original image 400 described above with reference to Fig. 4 are repeated upon the LL subband of image 402. For a three level DWT the resulting LL subband is again analysed as described above. Thus a multi-level DWT (or often simply referred to as 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 25 original image. A multi-level DWT can be inverted by simply inverting each single-level DWT and performing the synthesis in a reverse order to the analysis.

At each level of a multi-level DWT, there are three high frequency subbands, the HL, LH and HH subbands. To indicate what level in the decomposition of an image a subband is from, a level number is included with the labelling of the subbands. For example the notation (labelling) of the Highpass-Highpass subband at the third level of decomposition is HH3. Thus, the four subbands illustrated in Fig. 4 are more precisely denoted LL1, HL1, LH1 and HH1. Similarly, the three high frequency subbands at level CFP I909AU(STANDARD 08) F 0:\ELEC\CI5RA\Standard\Standard08]5 2 705 Ospec.doc: SDB -9- 2, resulting from the single level DWT of the LL1 subband, are denoted HL2, LH2 and HH2. Using this subband notation the original image can be labelled as the LLO subband.

IMAGE COMPRESSION PROCESSOR ARCHITECTURES The embodiment of the invention can be practiced using a general-purpose computer, such as the one shown in Fig. 36, wherein the processes of Figs. 2 to 13B may be implemented as software executing on the computer. In particular, the steps of the encoding, decoding methods are effected by instructions in the software that are carried out by the computer. The coding process for providing encoding digital images, decoding or signalling the structure of a code stream representing a digital image may also be implemented by instructions in software carried out by the computer. 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. A computer readable medium having such software or computer program recorded on it is a computer program product. The use of the computer program product in the computer preferably effects an advantageous apparatus for encoding digital images, decoding or signalling the structure of coded representations of digital images in accordance with the embodiment of the invention.

The computer system 100 consists of the computer 101, a video display 114, and input devices 102, 103. In addition, the computer system 100 can have any of a number of other output devices 115 including line printers, laser printers, plotters, and other reproduction devices connected to the computer 101. The computer system 100 can be connected to one or more other computers using an appropriate communication channel •oooo via a modem 116, a computer network 120, or the like. The computer network may include a local area network (LAN), a wide area network (WAN), an Intranet, and/or the Internet.

The computer 101 itself comprises a central processing unit(s) (simply referred to as a processor hereinafter) 105, a memory 106 which may include random access memory (RAM) and read-only memory (ROM), an input/output (IO) interface 108, a video interface 107, and one or more storage devices generally represented by a block 109 in Fig. 36. The storage device(s) 109 can consist of one or more of the following: a floppy CFP 1909AU(TANDARD 08) [1:\ELEC\CISRA\Standard\Standard08]527050spec.doc:SDB disc 111, a hard disc drive 110, a magneto-optical disc drive, CD-ROM, magnetic tape or any other of a number of non-volatile storage devices well known to those skilled in the art. Each of the components 105 to 113 is typically connected to one or more of the other devices via a bus 104 that in turn can consist of data, address, and control buses.

The video interface 107 is connected to the video display 114 and provides video signals from the computer 101 for display on the video display 114. User input to operate the computer 101 can be provided by one or more input devices. For example, an operator can use the keyboard 102 and/or a pointing device such as the mouse 103 to provide input to the computer 101.

The system 100 is simply provided for illustrative purposes and other configurations can be employed without departing from the scope and spirit of the invention. Exemplary computers on which the embodiment can be practiced include IBM-PC/ATs or compatibles, one of the Macintosh (TM) family of PCs, Sun Sparcstation or the like. The foregoing are merely exemplary of the types of computers with °which the embodiments of the invention may be practiced. Typically, the processes of ""the embodiments, described hereinafter, are resident as software or a program recorded on a hard disk drive (generally depicted as block 110 in Fig. 36) as the computer readable .ooo0i o20 medium, and read and controlled using the processor 105. Intermediate storage of the program and pixel data and any data fetched from the network may be accomplished using the semiconductor memory 106, possibly in concert with the hard disk drive 110.

In some instances, the program may be supplied to the user encoded on a CD- 25 ROM or a floppy disk (both generally depicted by block 109), or alternatively could be read by the user from the network via a modem device connected to the computer, for •example. Still further, the software can also be loaded into the computer system 100 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 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 are merely exemplary of relevant computer readable mediums. Other CFP1909AU(STANDARD 08) [1:\ELEC\CISRA\Standard\Standard0]527050spec.doc:SDB -11computer readable mediums may be practiced without departing from the scope and spirit of the invention.

The preferred embodiment of the coding method is preferrably in dedicated hardware such as one or more integrated circuits performing the functions or subfunctions of the encoding, decoding or signalling processes. An example of such hardware is described hereinafter with reference to Figs. 14 to 35. Such dedicated hardware may include ASICs and associated on-chip memories.

As described, image compression can be executed on general-purpose computers and also on application specific devices (ASIC). Both of these systems employ an architecture where the main processing unit has access to different memory units. Size and speed of access (and cost) typically differentiate these memories. For purpose of clarity and simplicity of description it will suffice to describe memory in two categories.

Namely, fast and slow memory. Fast memory includes: on-chip memory, where the memory is on the same chip that contains the processor utilising the memory. In a S°general-purpose computer, cache memory is also considered fast memory and usually relatively small in capacity. Slower memory is typically off-chip, that is, on another chip ""to the processor performing the computation and is relatively large in capacity. On a general-purpose computer, RAM (random access memory) or storage memory hard Disk, floppy disks, RW-CD) can be considered as slow memory. Hereinafter, a reference to local or internal memory is also a reference to fast memory and a reference to external memory is also a reference to slower (preferably) larger memory, unless contrary intentions appear.

SUBBAND IMAGE CODING tiled Referring to Fig. 1 there is shown an example of a DWT sub-image, or subbands, °i tiled into blocks, typically of block sizes being for instance K rows by K columns. The illustrated example of Fig. 1 shows two rows ofK x K blocks, where each row of each subband comprises four blocks. A row of blocks in a subband consists of K lines of the subband. Upon compression, each block is quantised and entropy coded substantially independently. Thus each block can be entropy decoded (and dequantised) substantially independently. Substantially independent coding and/or decoding of each block is CFP I909AU(STANDARD 08) [I:\ELEC\CISRA\Standard\Standard08]527050Spec.doc:SDB directed to include blocks which are coded and/or decoded independently but for some of the information which can be encoded and/or decoded together for a predetermined set of blocks. For example, 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 or alternately for predetermined sets of blocks in a subband. However, if the time or effort required to encode or decode such information for one block is trivial (not substantial) when compared to encoding or decoding a whole block, then the blocks can be considered as if the blocks are coded independently.

BLOCK BASED ENTROPY CODING OF DWT SUBBAND IMAGE DATA Typically, entropy coding is efficient and convenient when fully entropy coding a whole block of subband data. Similarly, when entropy decoding, it is convenient and efficient to entropy decode a whole block of data. That is, a whole block of data is held in local memory during encoding or decoding, so that the processor requires minimal interaction with external memory, while executing these processes.

CORRESPONDENCE BETWEEN THE SUBBAND AND IMAGE DOMAIN Fig. 1 illustrates a single level DWT of an image, and the tiling of each subband into K x K coefficient blocks 10 where K is a positive integer value. In Fig. 1 20 there are four blocks per row of blocks in each subband, which means that there are 4K coefficients per row in each subband. The image upon which the DWT is performed can s* in fact be any array of samples, such as some intermediate LL subband, and is not necessarily 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 (which typically consists of four subbands). Each row 11 of blocks of a subband in the DWT image, shown in Fig. 1, has or consists of K lines. Preferably, K is S. 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 input image. For example, in the case of Haar filters, 2K lines are 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 CFP 1909AU(TANDARD 08) [I:\ELEC\CISRA\Standard\Standard08]527050_spec.doc:SDB for other (longer) filters a number of extra image lines may be required to generate K subband lines at a next level of DWT decomposition. For example, in the case of 9/7 Daubechies filters, an additional 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 a previous level. 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. Nevertheless, for most filters used there is a correspondence between subband samples and input image samples. In the case of the Haar filters, this correspondence is 0o one-to-one.

The one-dimensional iDWT can be implemented using a lifting scheme.

The lifting scheme for an iDWT is described with reference to 9/7 Daubechies filters, however those skilled in the art will appreciate that other filters can be used without Is departing from the scope and spirit of the invention. For instance, other filters include 5/3 filters, D4 Daubechies filters, D6 Daubechies filters, Gabor filters and Haar filters.

Consider a signal x comprising samples xo, x, x2, and the one dimensional DWT of this signal generating a lowpass signal s comprising samples (coefficients) so, sl, s2, and a highpass signal d comprising samples (coefficients) do, dd, d 2 In this notation x 20 is referred to as the image signal, and the s and d signals are referred to as subband signals. Using this notation the iDWT, that is, a DWT signal can be inverted according to the following equations: d= -y(s 2n x2n+ 2 n x2+2 where a =-1.5861, 6= -0.052980, 0.88291, J 0.44351 (these values corresponding to the 9/7 Daubechies filters). In addition, some scaling of the subband or output coefficients may be required depending on the scaling used for the forward transform.

CFP1909AU(STANDARD 08) [I:\ELEC\CISRA\Standard\Standard08]527050spec.doc:SDB Fig. 2 illustrates a lifting lattice in accordance with the implementation of equations Each line 200 between samples 201 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 200. Thus, for example, since do, sl and d, are all connected to s' 1 by lines 200, and s' is at the bottom of each line 200, therefore according to Fig. 2 s' is a weighted sum of do, si and di. In particular, from lifting equation s'l sl 8(do dl) of equation it can be seen that lines 200 joining do and d, to s' are weighted by 8= 0.44351 and si by unity.

Still referring to Fig. 2 consider a first segment of subband samples so, s\, s2, S3, 54 and do, di, d 2 d 3 d 4 Corresponding to these 10 samples are the 10 first image samples xo, xl, x9. However, only a first seven samples xo, xi, x6 can be reconstructed from the first subband segment. The last three samples X 7 X8, and x9, cannot be reconstructed without obtaining further subband samples, namely subband samples ss, ds, S6, and d 6 Now consider that the first 7 (image) samples are reconstructed from the first segment of subband samples. In the reconstruction using the lifting equations several intermediate subband coefficients are calculated. Consider that in the reconstruction of 20 the four intermediate subband samples x6, d' 3 S'4, and d 4 are retained, in a memory buffer. These are the coefficients immediately to the left of the heavy diagonal line 202 in Fig. 2. If a second segment of subband samples ss, S6, S7, S8, S9 and ds, d 6 d 7 ds, d 9 is obtained, using the retained intermediate subband data the image samples X7, xs, and xg, and also all the image samples, bar the last three, corresponding to these new subband 25 samples can be reconstructed. That is samples X7, xg, x 9 xlo, xi, x 16 can be reconstructed. As before, in the description of the first segment the last three samples xl7, x8s, and x19 cannot be reconstructed without obtaining more subband samples. However, again if the 4 intermediate subband samples are retained and a third segment of subband samples is obtained another 10 subband samples can be reconstructed and so on.

Using this approach of buffering 4 intermediate subband samples, a signal can be reconstructed from sequential segments of subband samples. For each segment comprising n lowpass and n highpass samples 2n image samples can be reconstructed.

CFP 1909AU(STANDARD 08) [I:\ELEC\CISRA\Standard\Standard08]527050spec.doc:SDB These are the 2n image samples corresponding to the n subband samples, bar 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 2n image samples can be reconstructed. For the first segment 2n-3, while for the last segment 2n+3, samples are s reconstructed. Using the usual symmetric boundary extension the last three samples for last block are reconstructed from the last subband segment.

These properties of the lifting lattice are used to facilitate the implementation of the line-based inverse DWT in accordance with the present embodiment. Convolution techniques can also be used, however, a convolution implementation typically requires 7 samples retained (or re-obtained) between subband segments as opposed to 4 for the lifting scheme described above.

For filters other than the 9/7 the same approach to reconstructing the signal from subband segments can be used. However, more or less intermediate subband samples are needed to be buffered depending on the lattice configuration (or filters).

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 20 performed in segments. A special case of a two-dimensional segment of a twodimensional subband is simply a block of subband samples. Thus, a single level iDWT of 4 subbands can be performed by processing blocks of subband samples and buffering intermediate results between blocks.

25 A forward DWT can be performed in a similar manner, using segments of an input signal. Using a lifting implementation for the 9/7 filters, a minimum of 4 samples needs to be buffered between segments of the input signal. Alternatively, overlapping parts of the segments can be re-read, or buffered, between segments, and also convolution techniques can be used.

PERFORMING A SINGLE LEVEL TWO-DIMENSIONAL IDWT ON A BLOCK BY BLOCK BASIS USING LIFTING CFP 1909AU(TANDARD 08) [I:\ELEC\CI5RA\Standard\Standard08]527050Spec.doc:SDB -16- The observations made above with reference to Fig. 2 for performing a one-dimensional iDWT in segments can be used to perform a two-dimensional DWT on a block by block basis (a block being the two-dimensional equivalent of a one-dimensional segment).

Referring to Figs. 1 and 4, consider the single level inverse DWT of a DWT image. Suppose the LL, HL and HH subbands are of size N x N. First the rows of the LL and HL subbands are synthesised to form an N x 2N array of samples, which comprises the lowpass (and decimated by 2) filtered columns of the original image. This 0o array is labelled as Lc in Fig. 4. Similarly the rows of the LH and HH subbands are synthesised to form another N x 2N array of samples, which comprises the highpass (and decimated by 2) filtered columns of the original image, and is labelled Hc in Fig. 4.

This row operation, as a series of one-dimensional iDWTs can be performed in segments, where the segment's boundaries are given by the block boundaries.

Fig. 5 illustrates a row synthesis of the LL and HL subbands to form an LC sub-image. Corresponding to each block pair in the LL and HL subband is a block in the 20 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 the purposes of the inverse row transform, the 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.

Consider block 1 in the LL and HL subbands. Each block consists of K rows by K columns of data. Each row of these blocks is inverse transformed resulting in 2K-3 synthesised samples per row. The 2K-3 samples per row are the first 2K-3 samples per row of block 1 of the Lc sub-image. The last 3 row synthesised samples per row, 30 being the last three samples in each row in block 1 of the Lc sub-image, cannot be reconstructed until more subband data from block 2) is obtained. During the row synthesis, 4 intermediate subband samples are buffered per row, so that each inverse row CFP1909AU(STANDARD 08) [I:\ELEC\CISRA\Standard\Standard08]52705Spec.doc:SDB transform can be continued when block 2 (for the LL and HL subbands) rows are processed.

Next the K rows of block 2 (from the LL and HL subband) are inverse transformed and, using the 4 buffered subband samples per row from block 1, the next 2K samples of each synthesised row is obtained. That is, the last 3 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 are obtained. At this stage the reconstruction of block 1 of the LC sub-image is complete and all but the last three columns of block 2 of the L' sub-image have been synthesized. Blocks 3 and 4 are similarly processed. For block 4 not only is the reconstruction of block 3 completed, but also the reconstruction of block 4 is completed. The last 3 synthesised samples of block 4 of the L' sub-image for each row can be reconstructed using the symmetric boundary extension conditions. Thus for the block 4 2K 3 samples per row are synthesized.

The LH and HH subbands are similarly processed in block row order to produce the Hc sub-image.

Corresponding to each pair of blocks in the L and Hc sub-images is a 2K x 20 2K block in the original image, as illustrated in Fig. 6. Just as the LL and HL subbands and the LH and HH subbands can be processed in block order as just described, so can the L and HC sub-images. In the preferred embodiment, this block order processing is interleaved so that in effect the corresponding blocks from the LL, LH, HL and HH subbands are directly synthesized to the corresponding image block, or part thereof. This 25 approach is now described with reference to Fig. 1.

Returning to block 1 for each of the subbands of Fig. 1. Having performed the row synthesis for the LL and HL subbands all but the last three columns of block 1 of the Lc sub-image are obtained. Similarly, processing block 1 for the LH and HH 30 subbands all but the last three columns of block 1 of the HC sub-image are obtained. Thus at this stage the first 2K-3 columns of block 1 of the Lc and HC sub-image are reconstructed. For each row processed, 4 intermediate subband samples are buffered so that the row inverse DWT can be performed for block 2. Next, column 1 of block 1 of Lc UP I 909AU(STANDARD 08) [I:\ELEC\CISRA\Standard\Standard08]527050spec.doc:SDB -18sub-image and column 1 of block 1 of the HC sub-image are processed to generate all but the last three samples of column 1 of block 1 of the original image. Columns 2, 3, 2K- 3 of these blocks are similarly processed. In this way the top left hand 2K-3 x 2K-3 samples of block 1 of the original image are reconstructed. Four intermediate subband samples for each column are also buffered, so that the column inverse DWT's can be performed when block 5 is processed.

Rows of block 2 of the LL and HL subbands and rows of block 2 of the LH and HH subbands are processed. Using the buffered intermediate row subband data from block 1, the last three columns of block 1 and the first 2K-3 columns of block 2 of the Lc and Hc sub-image are generated. The intermediate row subband data is buffered for when block 3 is processed. These new 2K columns are then processed 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 1 of the original image. As before, 4 intermediate subband samples for each of the 2K columns are again buffered. At this stage the first 4K-3 samples for the first 2K-3 rows of the original image have been reconstructed. Blocks 3 and 4 are similarly processed, giving all of the first 2K-3 rows of the original image.

Next, a second row 12 of blocks is processed in a similar fashion. At block 20 5 the rows are synthesized as described above. Then the columns are synthesized using the buffered column subband data from block 1. This reconstructs the last three rows of block 1 in the original image as well as the first 2K-3 rows of block 5 of the original image (baring the last three columns as usual). Similarly for blocks 6 and 7 the last 3 rows of blocks 2 and 3 for the original image are reconstructed as well as the first 2K-3 rows of block 6 and 7 of the original image. For block 8 all the row data can be reconstructed, and thus a 2K x (2K+3) block can be reconstructed. In the same manner, all the blocks in DWT subbands are processed to reconstruct the original image.

.eeeei The above described process is further described in a steady state operation 30 with reference to Fig. 3. For this purpose, it is assumed that corresponding blocks of LL, S"HL, LH and HH data are input. Also input is an intermediate row subband data and intermediate column subband data, which allow the row and column DWT's to be continued from previous blocks. The process output's intermediate row and column CFP1909AU(STANDARD 08) [1:\ELEC\CISRA\Standard\Standard08]527050Spec.doc:SDB -19subband data for use when processing subsequent blocks. For blocks on the edge of the image some of this input or output intermediate subband data may be empty.

At step 300 processing begins. Rows of the LL and HL blocks are synthesized using the input intermediate row subband data to form substantially the rows of the corresponding Lc block at Step 305 (including the last three samples per row from the Lc block immediately to the left of this corresponding LC block but excluding the last three samples per row of this corresponding L block). For each row, four (4) intermediate row subband samples are output to the intermediate row subband buffer.

Similarly at Step 310 the rows of the LH and HH blocks are synthesized to form substantially the rows of the corresponding HC block. For each row 4 intermediate row subband samples are output to the intermediate row subband buffer. At Step 315, the columns of the synthesized LC and Hc block are synthesized to substantially form the corresponding image block. For each column four intermediate column subband samples are output to the intermediate column subband buffer.

A forward DWT can similarly be performed on a block by block basis.

Block 1 of the original image can be used to generate most of block 1 in each of the four subbands. Assuming blocks in the original image have even dimensions and that the 20 filtering is aligned so that the filter waveform corresponding to the first lowpass sample is centred around the first image sample, all but the last 2 rows and 2 columns of block 1 are generated in each subband. Alternatively, three extra samples per row, and per column (data to the right and below block 1) can be retrieved along with block 1 from the input image, and the whole of block 1 in each subband can be generated. Block 2 can be similarly processed in either way. When processing block 2 either buffered intermediate subband data can be used, or simply some extra data re-read from the input image to generate block 2 in each subband.

DECODING AN IMAGE WITH A TWO-LEVEL ENGINE INVERSE DWT i: 30 A multi-level iDWT of an DWT image compressed using substantially independently coded blocks of subband data is now described. The method of the preferred embodiment is based upon a two-level iDWT engine. The engine processes K lines at some level, say level j, and produces 4K lines of the LL subband at level j-2.

UFP 1909AU(STANDARD 08) 0I:\ELEC\CISRA\Standard\StandardO8]527050Spec.doc:SDB Figure 35 illustrates how 2-level IDWT is implemented in hardware in accordance with the embodiment. An Entropy Decoder 3505 simultaneously entropy decodes a LH2 3530, HL2 3535, and HH2 3540 sub-band and feeds them to a first 1-level IDWT unit 3515 in the 2-level IDWT unit 3510. The Entropy Decoder 3505 decodes a first LL2 band 3516 too if external memory contains no LL2 band. A multiplexer 3570 selects between an LL2 subband 3515 from the entropy decoder 3505 or an LL2 subband from external memory 3585. The multiplexor's output 3525 is the LL2 subband used in the inverse transform. The 1-level IDWT unit 3515 generates an LL1 band 3560 and feeds to the LL1 band 3560 to a second IDWT Unit 3520 in the 2-level IDWT unit 3510. At the same time, the Entropy Decoder 3505 also decodes an LH1 3545, HL1 3550 and HH1 3555 band and feeds them to the second IDWT Unit 3520. The second 1-level IDWT unit 3520 generates samples or more LL bands 3580 data if the current band is not the last. The IDWT unit 3520 then writes the samples 3580 to external memory 3585.

The IDWT units 3515, 3520 can work in columns or rows. The second IDWT unit 3520 can accept input twice the width of the first IDWT unit, and the throughput of the second IDWT unit is 4 times that of the first IDWT unit to keep the pipeline running smoothly.

Buffering Requirements The buffering requirements of the preferred embodiment are now described before continuing with the description of the decoding process.

25 The preferred embodiment utilises an even number of DWT levels, J.

However an odd J, where J is greater than 1, can be used without departing from the spirit of the invention. The levels are processed in pairs of levels. Levels 2 and 1 are processed together, as are levels 4 and 3, up to levels J and J-1. When J is odd, the first level is processed by itself, and for the purpose of this description can be considered as a level 30 pair, of levels J+1 and J.

For each pair of levels, there is a number of associated memory buffers that are now described.

CFP I909AU(STANDARD 08) [I:\ELEC\CISRA\Standard\Standard08]527050spec.doc:5DB For each pair of levels there is an output LL subband line buffer. For the level pair comprising levels j and j-1, there is an external memory line buffer for subband LL(j-2), called the LL(j-2) subband (line) buffer. Thus, for example, there is a line buffer for the LLO subband, which is a buffer for the output decoded image lines, a line buffer for the LL2 subband, whose lines are substantially 1/4 the length of the output image lines, and so on.

For each pair of levels, there is a pair of four line buffers that are referred to as the external column overlap buffers. For the level pair representing level j and level j-1, there is one four line buffer for level j and one four line buffer for level j-1. The line length of these buffers is preferably the length of the LL subband lines at the next lower level. Thus the external column overlap buffer for level 1 has a line length the same as the line length of the output image. In the preferred embodiment the external column overlap buffers are preferably resident in external memory. However, these buffers can reside in internal memory (on-chip) without departing from the scope and spirit of the invention.

There is a three line row buffer for each of the HL, LH, and HH subbands 20 (or AC subbands) at level 2, J-2 which preferably reside in external memory. These buffers are referred to as external row AC subband buffers. The length of the three line row buffer is preferably determined by the length required to store the relevant subband data.

25 The buffers described above relate to particular level pairs. There is also a o set of buffers used by the two-level iDWT engine independently of which level pair in question being processed. These buffers are now described.

There are two buffers that are referred to as internal row overlap buffers.

30 The internal row overlap buffers are preferably of size 4 columns by 2K rows, and 4 columns by 4K rows. Further, in the preferred embodiment there are two internal column overlap buffers. One is preferably of size 4 rows by 2K+3 columns, while the other is of size 4 rows by 4K+9 columns. When the two-level iDWT engine is processing a level CFP I 909AU(STANDARD 08) [I:\ELEC\CI5RA\Standard\Standard08]527050spec.doc:5DB pair, say level j and j-1, the smaller of the row and column buffers are used for level j, while the larger row and column buffer are used for level j-1. Preferably these buffers reside in internal memory.

There are also four block buffers, each preferably of size K x K and preferably residing in internal memory, which are referred to as the LL, HL, LH and HH block buffers. There is also an internal block buffer, preferably of size 2Kx2K and residing in internal memory, which contains LL subband data for odd levels.

There are also three buffers of size 3 rows by 2K columns and three buffers of size 3 rows by 2K columns, which are for buffering rows of AC subband blocks and preferably reside in internal memory. These three buffers are referred to as the internal row AC subband buffers. There are also three 3 column by K row buffers and three 3 column by 2K row buffers that are for buffering columns of AC subband blocks, which preferably reside in internal memory. These buffers are referred to as internal column AC subband buffers.

Multi-level iDWT Referring to Fig. 7 the multi-level iDWT process of a DWT image 20 compressed using substantially independently coded blocks of subband data is now described. Processing begins at Step 700. At Step 705, the compressed image header is decoded to preferably extract such image parameters as image size, number of image components, number of DWT levels, and subband block sizes. In the preferred embodiment the subband block size is fixed at K x K coefficients. However, block sizes that vary between subbands, and even within a subband, can be used without departing from the spirit of the invention.

A loop is entered at Step 710 that terminates when all the lines of the image have been decoded. Image lines are decoded in sets of lines, where the sets are 30 decoded in (set) raster scan order. Typically 4K lines are decoded at each iteration.

However, for the first iteration, only a first 4K-9 lines of the image are decoded.

However, for the first iteration, only a first 4K-9 lines of the image are decoded.

CFP1909AU(STANDARD 08) [I:\ELEC\CISRA\Standard\Standard08]527050Spec.doc:SDB At Step 715 the highest DWT level requiring processing is determined and a "j_max" variable is set accordingly. The method of the preferred embodiment operates by running a two-level iDWT engine on each level pair. For the level pair consisting of levels j and j-1, K lines from the LLj subband, which are resident in the LLj subband line buffer, are input to said iDWT engine. The output is 4K LL(j-2) subband lines, which are written to the LL(j-2) subband buffer. To generate a (next) set of 4K output image lines requires at the least the K corresponding lines of the LL2 subband (as well as data from the other level 2 and the level 1 subbands). If the output LL2 subband line buffer contains the required K lines, then j_max is set to 2. However, if the required LL2 o0 subband lines are not in the output LL2 subband line buffer, then the iDWT engine needs to be run on LL4 subband lines, to generate the required lines. This in turn requires that sufficient space be available in the LL4 subband line buffer. IfK lines, of which some are the required corresponding lines at level 4, are available in the LL4 output subband, buffer j_max is set to 4. Otherwise the process continues, incrementing j_max by two until an output subband line buffer is found with the necessary lines or j_max J, where J denotes the highest level. Consequently, j_max is the smallest even integer less than or equal to J such that the LL2, LL4, LL(j_max-2) buffers each have less than K lines of data in those buffers, while LL(j_max) has at least K lines in the corresponding buffer. If all the LL buffers have less than K lines in those buffers, thenjmax is J, as is the case for 20 the first iteration.

o i. At step 720 a loop is entered that iterates fromj =j_max toj 2, •decrementingj by 2 at each iteration. At each iteration nominally K lines of each of the four subbands at level j and nominally 2K lines at level j-1, are processed to produce 25 nominally 4K lines of the LL(j-2) subband. The K lines processed at level j are the K 4 lines in the first unprocessed row of blocks in the levelj subbands. In other words, for a given levelj, subsequent iterations of this loop process subsequent rows of blocks.

Similarly the 2K lines processed at level j-2 are the 2K lines in the first unprocessed pair of row of blocks in the level j-2 subbands.

At step 725 a loop is entered that iterates over the number of blocks per row of blocks for the subbands at levelj, for the first row of unprocessed row of blocks.

At Step 730 (substantially) block k for each of the LL, HL, LH and HH subbands is CFP 1909AU(STANDARD 08) [1:\ELEC\CISRA\Standard\Standard08]527050_spec.doc:SDB processed along with substantially the corresponding blocks at level j-1. The processing at step 730 is described in more detail with reference to Fig. 8.

Referring to Fig. 8, processing initiates at step 800. Inputs for the process are a DWT level (even) number j and a subband block number, k. At step 805 block k in each of the HL, LH and HH subbands at level j is entropy decoded into the internal HL, LH and HH block buffers. At Step 810 either the corresponding LL subband block is entropy decoded or extracted from the external LLj subband line buffer and put into the internal LL block buffer. At Step 815 the internal column overlap buffer is loaded with o0 the relevant data from the relevant external column overlap buffer. The internal column overlap buffer then contains the necessary intermediate subband data required to continue the column iDWT into block k in the LC and Hc subbands at level j, from the block immediately above block k in said L and Hc subbands. If block k is in the first row of blocks in the subband, then this data is not used (the data does not exist). The internal row overlap buffer data already contains the necessary intermediate subband data required to continue the row iDWT into block k from the row iDWT of the block immediately to the left of block k. If the block is the first block in the row of blocks in a subband then this data is not used (it does not exist).

At Step 820, the single-level block iDWT engine is operated on the four LL, HL, LH and HH blocks and the row and column intermediate subband data. This engine produces typically a 2K x 2K block of LL(j-1) data, which is placed in the LL block buffer for odd levels, and the intermediate row and column subband data required to continue the row and column iDWT's for blocks to the right and below the current block. The intermediate row subband data is put in the internal row overlap buffer, while the intermediate column subband data is put in the relevant external column overlap buffer.

At step 825, a loop is entered that iterates over the four blocks at level j-1 that substantially correspond to block k at level j. The order is preferably top left, top right, bottom left, and bottom right for the 2x2 set of corresponding blocks. At Step 830 the current block in the set of 2x2 corresponding blocks is decoded for the HL, LH and HH subbands at level j-1 into the HL, LH and HH block buffers.

CFP1909AU(TANDARD 08) [I:\ELEC\CISRA\Standard\Standard08]527050Spec.doc:SDB In Step 835, the previous three rows for each of the AC blocks (LH, HL and HH blocks) are loaded from the row AC subband buffers into the AC blocks. If the current block is the bottom left or bottom right block in the current set of 2x2 blocks, this row AC subband data is copied from the internal AC subband row buffers. Otherwise the row AC subband data is copied from the external row AC subband buffers for level j-1.

If the current block is in the first row of blocks in the subband, then this data is not loaded (the data does not exist). The three columns prior to the current AC blocks are in the internal column AC subband buffers and are loaded into the internal AC block buffers. If the block is in the first column of blocks in a subband, then this data is not loaded (the data does not exist). The last three rows and columns of each AC block are put in the row and column AC subband buffers respectively. If the current block is the top left or top right block, then the internal row AC subband buffers are used. Otherwise the data is buffered in the external row AC subband buffers.

At Step 840 the internal column overlap buffer is loaded with the relevant data from the relevant external column overlap buffer. This contains the necessary intermediate subband data required to continue the column iDWT into the current block in the Lc and Hc subbands at level j-1, from the block immediately above the current block in said Lc and Hc subbands. If the current block is in the first row of blocks in the subband, then this data is not used (the data does not exist). The relevant internal row overlap buffer data already contains the necessary intermediate subband data required to continue the row iDWT into block k from the row iDWT of the block immediately to the left of block k. If the block is the first block in the row of blocks in a subband then this data is not used (it does not exist).

At Step 845 the single level block iDWT engine is operated on the four LL, HL, LH and HH blocks and the row and column intermediate subband data. This engine produces a 2K x 2K block of LL(j-2) data, which is placed in the output LL(j-2) subband line buffer, and the intermediate row and column subband data required to continue the row and column iDWT's for blocks to the right and below the current block.

The intermediate row subband data is put in the larger internal row overlap buffer, while CFP1909AU(STANDARD 08) [I:\ELEC\CISRA\Standard\Standard08]527050Spec.doc:SDB the intermediate column subband data is put in the relevant external column overlap buffer.

The method described with reference to Figs. 7 and 8 continues until processing terminates at Step 710 in Fig. 7, when all image lines have been decoded and output.

An Example OfSynthesising A 256x256 Pixel DWT Image In the following description an example of the two-level engine based iDWT is 0o given. In the example the entropy block size is 16x16, the 9/7 filter is used, and a single 2-level IDWT is used. The upper level of the iDWT unit is designed to accept 16 lines, and the second level 32 lines. All the data required by the iDWT unit arrives synchronised, so that the unit does not need input buffering. For an image of size 256x256 pixels, the LH1, HL1 and HH1 bands are 128x128, and LL2, HL2, LH2 and HH2 bands are of size 64x64 coefficients. Let LL1 [ij,k] denote the kth line in the jth block of the i t row of blocks in LL1 sub-band, LL1 [ij] as block j in row i of the rows of blocks, and LL1 be lines m to n in LL1 sub-band (regardless of what block they are in). Corresponding notation is used for subbands other than the LL1 subband.

In the first cycle, blocks LL2[1,1], HL2[1,1], LH2[1,1] and HH2[1,1] are fed into the first level IDWT unit 3515, which generates the first 29 columns ofLLl[1:29] and .o some intermediate results. These intermediate results are written into external memory 3585, while the LL1 data is fed 3560 into the second level DWT unit 3520. Meanwhile, the first 29 columns ofLL1[1:29] are combined with the first 29 columns ofHLI[1:29], LH [1:29] and HH1[1:29] in the second level IDWT unit 3520 to give the first columns of LLO[1:55]. The first 29 columns of HLl[30:32], LH1[30:32] and HH1[30:32] are stored in external memory 3585 to be used later. This continues until all blocks in row 1 of LL2 are processed.

In the next cycle, blocks LL2[2,1], HL2[2,1], LH2[2,1] and HH2[2,1] and partial data (intermediate results) from external memory 3585 are fed into the first level IDWT unit 3515, which generates the first 29 columns of LL1[30:61]. Meanwhile, these columns of LLO[30:61] are combined with the corresponding columns of HL1[30:61], UFP 1909AU(STANDARD 08) [I:\ELEC\CI SRA\Standard\Standard08j5 27050-spec.doc: SDB LH1 [30:61] and HH1[30:61] (lines 30-32 from external memory, the rest from entropy decoders) in the second level IDWT unit 3520 to give the first 55 columns of LLO[56:119]. The first 29 columns of HL [62:64], LH1[62:64] and HH1[62:64] are stored in external memory 3585 to be used later. This continues until all the blocks in row 2 of LL2 are processed.

In the next cycle, blocks LL2[3,1], HL2[3,1], LH2[3,1] and HH2[3,1] and intermediate results from external memory are fed into the first level IDWT unit 3515, which generates the first 29 columns of LL1 [62:93]. Generated intermediate results are o0 saved to external memory 3585. Meanwhile, these columns of LL1[62:93] are combined with the corresponding columns of HLl[62:93], LH1[62:93] and HH1[62:93] (lines 62-64 from external memory, the rest from entropy decoders) in the second level IDWT unit to give the first 55 columns of LLO[120:183]. The first 29 columns ofHLl[94:96], LH1 [94:96] and HH1 [94:96] are stored in external memory to be used later. This continues until all the blocks in row 3 of LL1 are processed.

In the next cycle, blocks LL2[4,1], HL2[4,1], LH2[4,1] and HH2[4,1] and intermediate results from external memory are fed into the first level IDWT unit 3515, which generates the first 29 columns ofLL1 [94:125]. Again, generated intermediate results are saved in external memory 3585. Meanwhile, these columns of LL1[94:125] are combined with the corresponding columns of HLl[94:125], LH1[94:125] and HH1 [94:125] (lines 94-96 from external memory, the rest from entropy decoders) in the second level IDWT unit 3520 to give the first 55 columns ofLLO[184:247]. The first 29 columns ofHLl[126:128], LH1[126:128] and HH1[126:128] are stored in external memory to be used later. This continues until all the blocks in row 4 of LL2 are processed. In the last set of cycles, the saved intermediate results are loaded into the first level IDWT unit to generate LL1 [126:128]. These lines are fed into the second level IDWT unit 3520 with HL1[126:128], LH1[126:128] and HH1[126:128] to produce LLO[248:256].

THE ONE DIMENSIONAL DWT BY LIFTING This section substantially parallels the description of the previous section entitled "The Inverse One Dimensional DWT by Lifting" excepting that now a forward DWT CFP 1909AU(STANDARD 08) [I:\ELEC\C5RA\Standard\Standard08]527050Spec.doe:5DB (analysis) is performed with reference to equation below. Because of symmetry between analysis and synthesis in the lifting scheme used, the description for analysis and synthesis appears similar, excepting for equation The one-dimensional DWT can be implemented using a lifting scheme. Consider a signal x comprising samples xo, x1, x 2 and the one dimensional DWT of this signal generating a low-pass signal s comprising samples (coefficients) so, si, S2, and a highpass signal d comprising samples (coefficients) do, dl, d 2 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 the DWT an image signal can be converted according to the following equations: x2+ 2 x 2n+ 2 x 2 (2) +s,l) s, d where a= -1.5861, fP= -0.052980, y= 0.88291, 6= 0.44351 (these values correspond to the 9/7 Daubechies filters). In addition, some scaling of the subband or output coefficients may be required depending on the scaling used for the inverse transform.

Fig. 9 illustrates a lifting lattice in accordance with the implementation of equations Each line 900 between samples 901 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 900. Thus, for example, since d'o, x2 and d'i are all connected to s' by lines 900, and is at the bottom of each line 900, s'i is a weighted sum of d'o, x2 and d'I. In particular, according to the lifting equation s x2 P(d'o and therefore 25 lines 900 joining d'o and to s'j are weighted by -0.052980 and x2 by unity.

Still referring to Fig. 9 consider a first segment of subband samples xo, X2, X3, xs. Corresponding to these 9 samples are the 5 low-pass samples so, sl, S2, S3, 54, and 4 high-pass samples do, di, d 2 d 3 However, only the first 3 low-pass samples so, sl, S2 and the first 3 high-pass samples do, di, d 2 can be generated from the first subband segment.

CFP1909AU(STANDAP-D 08 [I:\ELEC\CISRA\Standard\Standard08]527050Spec.doc:SDB -29- The remaining low-pass and high-pass samples cannot be generated without obtaining further image samples, namely image samples x9, xlo, xll and xl2.

In the transform using lifting equation several intermediate subband coefficients are calculated. Consider that in this transform the three intermediate subband samples d' 3 s' 3 and d 2 are retained, say in a memory buffer. These, as well as X8, are the coefficients immediately to the left of the heavy diagonal line 902 in Fig. 9. If a second segment of image samples x 8 x9, x 1 o, xI, X16 is obtained (note that x 8 is fetched again), using the retained intermediate-subband data the image samples s3, d 3 and s4, and also all 0o the subband samples, bar the last one, corresponding to these new subband samples can be generated. As for the first segment the last three samples S7, d 7 and ss cannot be reconstructed without obtaining more subband samples. However, again if the 3 intermediate subband samples are retained and a third segment of subband samples is obtained another 4 low-pass samples and 4 high-pass samples can be generated and so on.

Using this approach of buffering 3 intermediate subband samples, a signal can be converted to sequential segments of subband samples. For each segment comprising 2n image samples n low-pass and n high-pass samples can be generated. These are the 2n image samples corresponding to the 2n subband samples, bar 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 2n image samples n subband samples can be generated in the low-pass band and high-pass band. For the first segment n-1, while for the last segment n+1 samples are generated. Using the usual symmetric boundary extension the last samples for last blocks are generated from the last image segment.

These properties of the lifting lattice are used to facilitate the implementation of the line based DWT in accordance with the present embodiment. Convolution techniques can also be used, however, a convolution implementation typically requires 7 samples retained (or re-obtained) between subband segments as opposed to 4 for the lifting scheme described above.

For filters other than the 9/7 the same approach to generate subband segments can be used. However, more or less intermediate samples will need to be buffered depending on the lattice configuration (or filters).

CFP 1909AU(STANDA-D 08) [I:\ELEC\CISRA\Standard\Standard8]527050spec.doc:SDB PERFORMING A SINGLE LEVEL TWO-DIMENSIONAL DWT USING

LIFTING

The observations made above with reference to Fig. 9 for performing a onedimensional DWT in segments can be used to perform a two-dimensional DWT on a block by block basis (a block being the two-dimensional equivalent of a one-dimensional segment).

Turning to Figs. 10 and 12, consider the single level DWT of an image. Suppose lo the image is of size 2N x 2N. First the columns are converted to form two N x 2N arrays of samples which comprise the low-pass (and decimated by 2) filtered columns and the high-pass (and decimated by 2) filtered columns of the original image. These low-pass columns are labelled as Lc, and the high-pass Hc, in Fig. Is This column operation, as a series of one-dimensional DWTs, can be performed in segments, where the segments are given by the block boundaries.

Consider the column analysis of the image to form the Lc and Hc sub-images, as illustrated in Fig. 11. Corresponding to each block in the image there is a block pair in the L and Hc sub-images, which has the same number of columns as the corresponding image block, but has half the number of rows. For the purposes of the column transform, the Lc subband contains the low-pass row data, while Hc subband contains the high-pass row data. Corresponding blocks in each of these sub-bands contain the corresponding low-pass and high-pass data.

Consider row-block 1 in the image. A row-block is a row of blocks. Each rowblock consists of 2K+ 1 rows of data, and row-blocks overlap each other by one row.

Therefore, the 1 st row-block is from row I to 2K+l, the second row-block is from row S 2K+1 to 4K+ 1. Each column of these row-blocks is transformed resulting in K rows in the Lc and Hc sub-bands, except for the first row-block, which generates only K-I rows.

The K- I rows are the first K- I rows of the corresponding row-blocks 1 in the L and Hc .o S"sub-images. The last row of samples in the Lc and Hc sub-images cannot be generated until more image data from row-block 2) is obtained. During the column analysis, 3 CFP1909AU(STANDARD 08) [I:\ELEC\CISRA\Standard\StandardO8]527050Spec.doc:SDB intermediate subband samples are buffered per column, so that the column transform can be continued when we process the 2K+1 rows in row-block 2. Next the 2K+1 rows in row-block 2 are transformed and, using the 3 rows of buffered subband samples from row-block 1, the next K rows in the LC and H' sub-images are obtained. That is the last row of row-block 1, and the first K-l rows of row-block 2 of the Lc and Hc sub-images are obtained. At this stage the generation of row-block 1 of the Lc sub-image is complete and all but the last row of block 2 of the L sub-image have been generated. Row-blocks 3 and 4 are similarly processed. For row-block 4 not only is the generation of row-block 3 completed, but also the generation of row-block 4 is completed. In this example there to are 4 row blocks, so that row-block 4 is the last block row. The last row of row-block 4 of the Lc and Hc sub-images can be generated using the symmetric boundary extension conditions. Thus for the row-block 4, K 1 rows are generated.

Corresponding to each block in the Lc sub-image is one K x K block in each of the LL and HL subbands, as illustrated in Fig. 12. Correspondingly each block in the Hc subimage corresponds to one K x K block in each of the LH and HH subbands. In the preferred embodiment these blocks are processed in parallel, so all the 4 blocks in LL, HL, LH and HH subbands are generated simultaneously. This approach is now described with reference to Fig. 12.

Returning to Fig. 12, consider block 1 of the L e sub-image. Having performed the column analysis for the image all but the last row of row-block 1 of the Lc and Hc subimages are obtained. For each column processed the 3 intermediate subband samples are buffered so that the column DWT can be continued for row-block 2. Next row 1 of block 1 of L sub-image is processed to generate all but the last sample of row 1 of block 1 of the LL and HL subbands. Rows 2, 3, K-1 of block 1 are similarly processed. In this way the top left hand K- x K-1 samples of block 1 of the LL and HL subbands are generated. The 3 intermediate subband samples for each row are also buffered, so that the row DWT's can continue when block 2 is processed. At the same time, rows of block 1 in the Hc sub-image are processed to form the top left hand K-l x K-l samples of block 1 of the LH subband and the HH subband.

UP I 909AU(STANDARD 08) [I:\ELEC\CISRA\Standard\Standard08]527050Spec.doc:SDB Then rows of block 2 of the L subband HC subband are processed. Using the buffered intermediate row subband data from block 1, the last column of block 1 and the first K-1 columns of block 2 of the of LL, HL, LH and HH subbands are generated. The intermediate row subband data is buffered for block 3. At this stage the first 2K-1 samples for the first K- rows of the LL, HL, LH and HH subbands have been generated.

Blocks 3 and 4 are similarly processed, giving all of the first K-1 rows of all the subbands. When processing block 4 the boundary needs to be symmetrically extended to get the extra sample.

Next the second row of blocks is processed in a similar fashion. Rows of block are analysed generating the last row of block 1 in the LL, HL, LH, and HH subbands as well as the first K-1 rows of block 5 of all the subbands (baring the last column as usual).

Similarly for blocks 6 and 7 the last row of blocks 2 and 3 for the all the subbands are generated as well as the first K- rows of block 6 and 7 of all the subbands. For block 8 all the row data is generated, and thus a K x block is generated. All the other blocks in the original image are processed similarly.

The complete DWT process is described in the steady state operation with reference to Figs. 13A and 13B. It is assumed the original image blocks and the intermediate row subband and column subband data are inputs. The process outputs intermediate row and column subband data for use when processing subsequent blocks, and transformed blocks in LL, HL, LH and LL subbands. For blocks on the edge of the image some of this input or output intermediate subband data may be empty.

Turning to Fig. 13A at step 1305 the image header is coded with information such as image size, number of DWT levels, block size, number of components, etc. At step 1310 the process loops through all the DWT levels in step of 2. At step 1315, the process performs DWT on the LL subband at current level, and generates LL, HL, LH and HH subbands of the two levels above. The process sends all the HL, LH and HH subbands to the entropy coder. At step 1320 the process determines whether the final level is readied.

SIf so, then processing continues at step 1325, where the final LL subband is sent to the entropy coder. If not, then processing continues at step 1330 from step 1320, where the LL subband is sent to external memory. The process then goes back to step 1310.

CFP I909AU(STANDARD 08) [1:\ELEC\CISRA\Standard\Standard08]527050spec.doc:SDB Turning to Fig. 13B, the DWT process at each level is further described. At step 1340 processing begins. The row-blocks of the original data are analysed using the input intermediate column subband data to form substantially the rows of the corresponding Lc and Hc row-blocks at Step 1345 (including the last row from the Lc and Hc blocks immediately above the corresponding L and Hc row-blocks but excluding the last row of this corresponding Lc and Hc row-blocks). For each column 3 intermediate column subband samples are output to the intermediate column subband buffer. At Step 1350, the rows of the Lc block are transformed to substantially form the corresponding LL and HL to subband blocks. For each row 3 intermediate row subband samples are output to the intermediate row subband buffer. Similarly, at Step 1355, the rows of the HC block are transformed to substantially form the corresponding LH and HH subband blocks. For each row 3 intermediate row subband samples are output to the intermediate row subband buffer.

TWO-LEVEL DWT The preferred embodiment of the forward DWT is explained with reference to Fig.

14. When the original image 1405 goes into the 2-level DWT unit 1410, the first level DWT unit 1415 determines the LL1 subband 1435, LH1 subband 1420, HL1 subband 1425, and HH1 subband 1430. The second level DWT unit 1440 determines from the LL1 subband 1435 the LL2 subband 1460, LH2 subband 1445, HL2 subband 1450, and HH2 subband 1455. The LH1 1420, HL1 1425, HH1 1430, LH2 1445, HL2 1450, and HH2 1455 subbands are fed into the entropy coder 1480 to be coded, while the LL2 subband 1460 is written into external memory 1470 so that the subband 1460 can be read later for further processing.

When the original image is processed 2 levels together, the amount of data that needs to be written into external memory is decreased by 75%. However, the amount of internal memory required is increased, since some of the LL1 subband 1435 needs to be stored so there is enough to be transformed by the second DWT unit 1440. The problem may be partly solved by designing the second DWT unit 1440 in such a way so that the second DWT unit 1440 can accept coefficients in the order as supplied by the first DWT unit. This is further explained later.

CFP1909AU(STANDARD 08) [I:\ELEC\CISRA\Standard\StandardO8]527050spec.doc:SDB Operation of the 2-level DWT is described in more detail with reference to Fig. 15. This example is for illustration only and any part of the example can be modified according to the need of the user. In the following, the following conditions are assumed: The coefficients are coming in 2 rows of 4, and in the next cycle the next 2 rows come.

The DWT units 1415 and 1440 firstly apply a horizontal filter to the input, and then applies a vertical filter to the filtered coefficients. This may be swapped to suit the pattern of image data coming in.

The horizontal filter accepts two inputs and generates one high pass coefficient and one low pass coefficient. This may not be true for pixels near boundaries.

As the coefficients arrive, the first DWT unit 1415 firstly horizontally filters the samples in the original image 1500 using 2 4-input filter. This should produce 2 blocks of 2x2 coefficients in bands 1510 and 1520. Four 2-input filters then vertically filter the horizontally filtered coefficients to produce 2 coefficients in the LL1 subband 1530, HL1 subband 1535, LH1 subband 1540 and HH1 subband 1545. The coefficients in HL1 subband 1535, LH1 subband 1540 and HH1 band 1545 can go to their respective entropy coder 1480 or external memory. A second DWT unit 1440 then horizontally filters the 2 coefficients in LL1 band 1530 with a 2-input filter, and produces 1 coefficient in the high band 1555 and the low band 1550 respectively. In the next cycle cycle one more coefficient is produced in the next row of the high band 1555 and the low band 1550.

Then these 2 pairs of coefficients can be fed to 2 2-input vertical filter to generate 1 coefficient in LL2 subband 1560, LH2 subband 1565, HL2 subband 1575 and HH2 Toe* subband 1570. The coefficient in LL2 band 1560 goes back to external memory 1470, while the coefficients in the other bands can go to the entropy coder 1480 or internal memory (not shown in diagram).

The following is the hardware requirement and throughput to process various numbers of coefficients in one cycle according to the hardware arrangement of the preferred embodiment.

CFP 1909AU(STANDARD 08) [1:\ELEG\CISRA\Standard\Standard8]527050spec.doc:SDB TABLE 1 Hardware Requirement and Throughput of 2-level DWT Hardware Requirement Throughput Inp 1 st Ist 2 nd 2 nd HL LL ut Size Hfilter Vfilter Hfilter Vfilter 1, LH1, 2, LH2, HH1 HL2, HH2 lxi Ilx lx lx Ix 1 1 *2-input 2-input 2-input 2-input per 4 per 16 cycles cycles 1x2 lx 2m Ix M x lx lx mo2m-input x 2-input rn-input 2-input mn per 2 m/2 per 4 cycles cycles 2nx 2n 2 x nx 2 x nxl n/2 x 2-input 2n-input 2-input n-input per 2 xl per 4 cycles cycles 2nx 2n 2 x nx 2 x nxl n/2 2 x 2-input 2n-input 2-input n-input per cycle x 1 per 2 cycles 2x2 2 x 2m lx M x Ix lx m 2m-input x 2-input rn-input 2-input m per m/2 per 2 cycle cycles 2nx 2n 2m nx m x nx n/2 2m x 2rn-input x 2n-input rn-input n-input m per xmI2 per cycle cycle Input order must be top left, top right, bottom left, and bottom right of 2x2 block Odd row must be followed by even row Odd column must be followed by even column Method Of Handling Data Offset In 2-Level DWT CFP I 909AU(STANDARD 08) CFP 90AU(TANARD08)[:\ELEC\CISPRA\Standard\Standard08]527050-Spec.doc:SDB -36- As an output coefficient from the DWT depends on surrounding pixels (3 or 5 if a 5/3 filter is used, 7 or 9 if a 9/7 filter is used), when the first n inputs pixels are fed to the DWT unit fewer than n coefficients are generated. After the initial n pixels are finished, the n pixels in the next cycle generates n output coefficients. This continues until the last lot ofn pixels is fed in. In the last cycle, the DWT unit produces more than n coefficients to make up the shortfall in the first cycle.

Because of this, when 16 lines are fed into the DWT unit, less than 16 lines are obtained back. This causes some problems in 2-level DWT, especially if the second level to DWT depends on some alignment of coefficients from the first level DWT. In the preferred embodiment of the invention for the forward DWT there are presented 2 methods in which this data misalignment problem can be handled. The following examples illustrate the problem and how the problem can be solved.

With reference to Fig. 16, a typical 2-level DWT of an image is considered. The first level DWT can process at least 4K samples simultaneously, and the second level DWT can process 2K samples, where K is the height of the blocks encoded by the entropy coder. The filter is a 9/7 filter, which generates the DWT coefficients in 1690.

The original image 1600 is where N is the height of the input image. The subbands LH1[l:n/2] 1620, HL1[1:n/2] 1640 and HHI[1:n/2] 1630 are the output of the first-level DWT unit. The subbands LL2[1:n/4] 1670, LH2[1:n/4] 1680, HL2[1:n/4] 1650 and HH2[1:n/4] 1660 are the output of the second-level DWT.

There are two methods for handling data offset: overlap read-back and redundant source read.

OVERLAP READ-BACK The overlap read-back method is described with reference to Figs. 17 to 24.

Turning to Fig. 17 the process starts with step 1705, in which the first 9 lines of the image are fetched. These 9 lines are transformed by the first level DWT unit 1415 to produce LL1[1:3], HL1[1:3], LH1[1:3] and HH1[1:3], and some intermediate subband data. The first level subband data is written into the first level intermediate results buffer 1740, which resides in external memory 1470 through connection 1701. The subbands UFP I 909AU(STANDARD 08) [I:\ELEC\CISRA\Standard\Standard08]527050 spec.doc:SDB -37- HL1[1:3], LH1[1:3] and HH1[1:3] are written into the subband buffer 1750 via 1703.

The LL1 subband is sent to the second level DWT unit 1430, which generates some more intermediate data. These data are written into the second level intermediate results buffer 1745 via connection 1702.

Next in step 1710 a check is made to determine if there are any more input lines.

If there is none the process is complete and processing terminates. If there are more input lines (YES), then the process checks whether there are 4K lines in step 1715.

If there are not enough lines then the lines are symmetrically reflected at the to boundary in step 1720. (The symmetrical extension is actually only needed for 3 samples beyond the boundary. Any sample after that has no effect on the outcome. This applies to all symmetrical extension in all the following figures). Otherwise if step 1715 returns true (YES), processing continues at step 1725.

After step 1720, the process proceeds to step 1725, where rows 9+4nK to 9+4K(n+1) are transformed into various subbands in first and second level DWT. During the transform, step 1725 reads the intermediate subband data from the previous block of rows in first level intermediate results buffer 1740 and second level intermediate results buffer 1745, and generates new intermediate subband data for them. Step 1725 also reads rows 1+2nK to 3+2nK of the HL1 1640, LHI 1620 and HH1 1630 subbands from the subband buffer 1750 to complete some blocks, and then write rows of 1+2K(n+l) to 3+2K(n+l) back to the subband buffer 1750. Step 1725 sends HL1 1640, LH1 1620 and HH1 1630 blocks in rows 1+2nK to 2K(n+l) to first level entropy coder 1755 and sends HL2 1650, LH2 1680 and HH2 1660 blocks in rows l+nK to K(n+l) to the second level entropy coder 1760. Step 1725 writes the LL1 blocks 1670 to external memory 1470 for further processing. Processing then continues at decision step 1710.

Step 1705 in Fig. 17 is now further explained with reference to Figs. 18 and The first 9 rows of the image are fetched in step 1805. In step 1810, the 9 samples in each column are analysed to form the first 3 samples per column in the Lc and H' S. subbands. The subband intermediate results are stored through connection 1812. In step 1815 each row of the L' subband is analysed to produce the LL1 and HL1 subbands. In step 1820 each row of the H subband is analysed to produce the LH1 and HH1 subbands.

CFP I 909AU(TANDARD 08) [I:\ELEC\CISRA\Standard\Standard08]527050spec.doc:SDB -38- The first 3 rows of the HL1, LH1 and HH1 subbands are written to the subband buffer 1750 in step 1825 through connection 1827. Also in step 1825 rows 1-3 of the LL1 subband are sent to the second level DWT unit. In step 1830 in the second level DWT unit, the first 3 rows of the LL1 subband are further analysed to produce intermediate subband data. These data are written to the second level intermediate results buffer 1745 via connection 1832.

Step 1725 in Fig. 17 is now further explained with reference to Fig. 19. In step 1905 the process fetches rows 9+4nK to 9+2K(n+l) of the original image. In step 1910 the first level DWT unit 1415 reads intermediate subband data from first level intermediate results buffer 1740 via 1915, column-analyses the rows of the original image to rows 4+2nK to 3+2K(n+l) in the L and H' subbands, and writes back new intermediate subband data. In step 1920 all rows in Lc subband are analysed. In step 1925, all rows in HC subband are analysed. In steps 1920 and 1925, processing of the rows starts when enough outputs have been generated by step 1915, so that a minimum amount of intermediate results require buffering between these steps. This applies to all row-DWT steps in all the subsequent figures.

Steps 1815 in Fig. 18 and 1920 in Fig. 19 are now further described with reference 20 to Fig. 20. In step 2005 the first level DWT unit 1415 row-analyses the first 3 samples in each row and generates some intermediate subband row data. These intermediate data are written into the first-level row-intermediate result buffer 2010 internally. After that, in step 2015 the process checks whether there are any more samples in the row. If there is not, the process finishes. If there is, then in step 2020 the process checks whether there are 4K samples left in the row. If there is not, then in step 2025 the process symmetrically extends the samples before proceeding to step 2030. If decision step 2020 determines there are 4K columns (YES), processing continues at step 2030.

•In step 2030 the process performs a DWT on the next 4K (or remaining) samples on each row of the block. In step 2035 the process reads the 3 rows above the transformed samples to complete the LL and HL subband blocks. These overlap rows are read from the subband buffer 1750 via connection 2040. In step 2045 the process writes back the overlap rows 1+2K(n+l) to 3+2K(n+l) back to the subband buffer 1750 through CFP1909AU(STANDARD 08) [1:\ELEC\CISRA\Standard\Standard08]527050spec.doc:SDB connection 2050. In step 2060 the process sends the LL block to the second level DWT unit 1440 in Fig. 14. In step 2070 the process sends the generated HL block (from rows 1+2nK to 2K(n+l)) to the first level entropy coder 1755 through connection 2075. After that the process goes back to step 2015 to check whether there are any more columns to process.

Steps 1820 in Fig. 18 and 1925 in Fig. 19 are now further described with reference to Fig. 21. In step 2105 the first level DWT unit 1415 row-analyses the first 3 samples in each row and generates some intermediate subband row data. These intermediate data are 0o written into the first-level row-intermediate result buffer 2110 internally. After that, in step 2115 the process checks whether there are any more samples in the row. If there is not, the process finishes. If there is, then in step 2120 the process checks whether there are 4K samples left in the row. If there is, processing continues at step 2130. If there is not, then in step 2125 the process symmetrically extends the samples to 4K samples. In step 2130 the process performs a DWT on the next 4K samples on each row of the block.

In step 2135 the process reads the 3 rows above the transformed samples to complete the LL and HL subband blocks. These overlap rows are read from the subband buffer 1750 via connection 2140. In step 2145 the process writes back the overlap rows 20 1+2K(n+1) to 3+2K(n+1) back to the subband buffer 1750 through connection 2150. In step 2160 the process sends the generated HL block (from rows 1+2nK to 2K(n+1)) to the first level entropy coder 1755 through connection 2165. After that the process returns to step 2115 to check whether there are any more columns to process.

25 Step 2060 in Fig. 20 is now further described with reference to Fig. 22. In step 2205 rows 4+2nK to 3+2K(n+l) of the LL1 band from the first level DWT unit are fetched. In step 2210, the process performs column-DWT to generate rows 1+nK to K(n+l) of the LC and HC sub-images. To achieve that, step 2210 needs to read the intermediate subband data from the second level intermediate results buffer 1745 through 30 connection 2215, and after computation the process writes the new intermediate subband S. data back to the second level intermediate results buffer 1745. In step 2220 the process performs a DWT on each row in the L sub-image. In step 2225, the process performs DWT on each row in the HC sub-image.

CFP 1909AU(STAN DARD 08) [I:\ELEC\CISRA\Standard\Standard08]527050Spec.doc:SDB Step 2220 in Fig. 22 is now further described with reference to Fig. 23. In step 2305 the second level DWT unit 1440 row-analyses the first 3 samples in each row and generates some intermediate subband row data. These intermediate data are written into the second-level row-intermediate result buffer 2310 internally. After that, in step 2315 the process checks whether there are any more samples in the row. If there is not, the process finishes. If there is, then in step 2320 the process checks whether there are 2K samples left in the row. If there is, processing continues at step 2330. If there is not, then in step 2325 the process symmetrically extends the samples to 4K samples. In step 2330 the process performs a DWT on the next 2K samples on each row of the block. In step 2335 the process sends the LL block from row l+nK to K(n+l) to external memory 1470 in Fig. 14. In step 2340 the process sends the generated HL block (from rows l+nK to to the second level entropy coder 1760 through connection 2345. After that the process returns to step 2315 to check whether there are any more columns to process.

Step 2225 in Fig. 22 is now further described with reference to Fig. 24. In step 2405 the second level DWT unit 1440 row-analyses the first 3 samples in each row and generates some intermediate subband row data. These intermediate data are written into the second-level row-intermediate result buffer 2410 internally. After that, in step 2415 S 20 the process checks whether there are any more samples in the row. If there is not, then the process finishes. If there is, then in step 2420 the process checks whether there are 2K samples left in the row. If there is, the process continues at step 2430. If there is not, then in step 2425 the process symmetrically extends the samples to 4K samples. In step .4 2430, a ROW DWT is applied to columns 4+2pK to 3+2K(p+l) and then p is 25 incremented. In step 2435 the process sends the generated LH and HH blocks (from rows *99* l+nK to to the second level entropy coder 1760 through connection 2440. After that the process returns to step 2415 to check whether there are any more columns to process.

9 To further expand on the above process, a worked example is described below. In the example K equals 16, so that the first level DWT unit can accept up to 64 samples, while the second level DWT unit can accept up to 32 samples.

CFP1909AU(STANDARD 08) [1:\ELEC\CISRA\Standard\Standard08]527050Spec.doc:SDB -41- In the first pass P[1:9] are fed into the first DWT unit, which produces 3 first level intermediate results, LLI[1:3], HL1[1:3], LH1[1:3] and HH1[1:3]. HL1[1:3], LH1[1:3], HH1 LL1[1:3] and the intermediate results are written into external memory.

In the next pass, P[9:73] and the 3 lines of first level intermediate results are fed into the first level DWT unit, and LL1[4:35], HL1[4:35], LH1[4:35], HH1[4:35] and 3 first level intermediate results are generated. At the same time, LL1[1:3], HL1[1:3], LH1[1:3] and HHI[1:3] are read back. While HL1[1:32], LH1[1:32] and HH1[1:32] are passed to the entropy coder, LL1[1:35] is fed to the second level DWT unit, which to generates LL2[1:16], HL2[1:16], LH2[1:16], HH2[1:16] and 3 second level intermediate results. LL1[35], HL1[33:35], LH1[33:35], HH1[33:35] and the second level intermediate results are written into external memory, while LL2[1:16], HL2[1:16], LH2[1:16] and HH2[1:16] are sent to the entropy coder immediately.

In the third pass, P[73:137] and the 3 lines of first level intermediate results are fed into the first level DWT unit, and LL1[36:67], HL1[36:67], LH1[36:67], HH1[36:67] and another 3 lines of first level intermediate results are generated. LL1[35], HL1[33:35], LH1[33:35] and HH1[33:35] are read back, and HL1 [33:64], LH1[33:64], and HH1[33:64] are fed into the entropy coder. LL1[36:67] is combined with LL1[35] from 20 external memory, and LL1[36:67] and LLl[35] are fed into the second-level DWT unit.

The second-level DWT unit generates LL2[17:32], HL2[17:32], LH2[17:32], HH2[17:32] and 3 lines of second level intermediate results, each of which are half the width of the image. All outputs are fed into the entropy coder, while LL1[67], HL1[65:67], LH1 [65:67], HH1 [65:67] and the second level intermediate results are stored in external 25 memory.

Suppose that there are 256 lines in total. In the last pass, P[201:256] and the 3 lines of intermediate values are fed into the first level DWT unit. The remaining inputs are fed with symmetric extension of the image. The first level DWT unit generates LLl[100:128], HLl[100:128], LHl[100:128] and HHl[100:128]. LL1[99], HL1[97:99], LH1[97:99] and HH1[97:99] are read back, and HL1[97:128], LH1[97:128], and HH1[97:128] are fed into the entropy coder. The LL1[100:128] and LL1[99] from external memory (with the missing inputs filled with symmetric extension) are fed into CFP1909AU(STANDARD 08) [I:\ELEC\CISRA\Standard\StandardO8]527050spec.doc:SDB the second level DWT unit, which generates LL2[49:64], HL2[49:64], LH2[49:64] and HH2[49:64] that are all going to the entropy coder.

REDUNDANT SOURCE READ The second method for handling data offset is the redundant source read method.

This method is now described in detail with reference to Figs. 25 to 33. Turning to Fig. 25 the overall process is described in detail. The process starts at 2505, where the process checks whether there are any more rows to be processed. If there is no more rows to be processed, then the whole process finishes. If there are more rows, then in step 2510 the process checks whether the first block of rows is being processed. If so (YES), then the process continues onto step 2530, where a check is made to determine whether there are 4K+9 rows in the image. If there is (YES), processing continues at step 2540. If there is not, then in step 2535 the bottom of the image is symmetrically extended to 4K+9 lines. In step 2540 the process transforms rows 1 to 4K+9 of the original image. In doing that some intermediate data may be written through connections 2541 and 2542 to the first level intermediate results buffer 2550, the second level intermediate results buffer 2560, and complete blocks sent through connections 2543 and 2544 to first level entropy coder 2570 and second level entropy coder 2580. After that the process goes back to step 2505 to check whether there are more rows in step 2505.

If in step 2510 the process finds that it is not processing the first row of the image, *the process goes onto step 2515, a check is made whether there are 4K+5 lines to be processed. If there is (YES), processing continues at step 2520. If there is not, then in step 2517 the process symmetrically extends the original samples to 4K+5 rows. In step 25 2520 the process transforms rows 3+4nK to 9+4K(n+l) of the original samples. In doing that, some intermediate data may be read and written through connections 2521 and 2522 to the first-level intermediate-results buffer 2550, the second-level intermediate-results buffer 2560, and complete blocks sent through connections 2523 and 2524 to first level entropy coder 2570 and second level entropy coder 2580. After that the process goes 30 back to step 2505 to check whether there are more rows.

Step 2540 in Fig. 25 is now described in further detail with reference to Fig. 26.

The process begins at step 2605, where rows 1 to 4K+9 of the original samples are CFP 1909AU(STANDARD 08) [I:\ELEC\CISRA\Standard\Standard08]527050Spec.doc:SDB -43fetched. In step 2610 the process performs a DWT on each column of the original samples and generates rows 1 to 3+2K of the LC and HC sub-images. During the process some intermediate subband data are written into the first level intermediate results buffer 2550 through connection 2615. In step 2620 the process performs DWT on every row in the Lc sub-image to generate the LL1 and HL1 subbands. In step 2625 the process only performs DWT on rows 1 to 2K in the Hc sub-image to generate LH1 and HH1 subbands.

Step 2520 in Fig. 25 is now described in further detail with reference to Fig. 27.

The process begins at step 2705, where rows 3+4nK to 9+4K(n+l) of the original samples are fetched. In step 2710 the process performs DWT on each column of the original samples and generates rows 1+2nK to 3+2K(n+1) of the Lc and Hc sub-images. During the process some intermediate subband data are read and written into the first level intermediate results buffer 2550 through connection 2715. In step 2720 the process performs DWT on every row in the Lc sub-image to generate the LL1 and HL1 subbands.

In step 2725 the process performs DWT only on rows 1+2nK to 2K(n+l) in the Hc subimage to generate LH1 and HH1 subbands.

Steps 2620 in Fig. 26 and 2720 in Fig. 27 are now described in more detail with reference to Fig. 28. In step 2805 the first level DWT unit 1415 row-analyses the first 3 samples in each row and generates some intermediate subband row data. These intermediate data are written into the first-level row-intermediate result buffer 2810 internally. After that, in step 2815 the process checks whether there are any more samples in the row. If there is not, the process finishes. If there is, then in step 2820 the process checks whether there are 4K samples left in the row. If there is (YES), processing continues at step 2830. If there is not, then in step 2825 the process symmetrically extends the samples to 4K samples. In step 2830 the process performs DWT on the next 4K samples on each row of the block.

In step 2835 the process checks whether the first block of rows in the image or not is being processed. If it is (YES), then processing moves to step 2840, where rows 1 to 2K+3 of the LL1 band are sent to the second level DWT unit 1440 in Fig. 14 before proceeding to step 2850. If it is not then processing moves to step 2845, where rows 3+2nK to 2K(n+1)+3 of the LL1 band are sent to the second level DWT unit 1440 CFP I909AU(STANDARD 08) [I :\ELEC\CISRA\Standard\StandardO8527050 spc.doc:SDB -44in Fig. 14 before proceeding to step 2850. In step 2850 the process sends the generated HL block (from rows 1+2nK to 2K(n+l)) to the first level entropy coder 2570 through connection 2855. After that the process returns to step 2815 to check whether there are any more columns to process.

Steps 2625 in Fig. 26 and 2725 in Fig. 27 is now described in more detail with reference to Fig. 29. In step 2905 the first level DWT unit 1415 row-analyses the first 3 samples in each row and generates some intermediate subband row data. These intermediate data are written into the first-level row-intermediate result buffer 2910 to internally. After that, in step 2915, the process checks whether there are any more samples in the row. If there is not, then the process finishes. If there is, then in step 2920 the process checks whether there are 4K samples left in the row. If there is (YES), processing continues at step 2930. If there is not, then in step 2925 the process symmetrically extends the samples to 4K samples. In step 2930 the process performs is DWT on the next 4K samples on each row of the block. In step 2935 the process sends S*the generated LH and HH blocks (from rows l+2nK to 2K(n+l)) to the first level entropy coder 2570 through connection 2940. After that the process returns to step 2915 to check whether there are any more columns to process.

Step 2840 in Fig. 28 is now described in further detail with reference to Fig. The process begins at step 3005, where rows 1 to 2K+3 of the LL1 subband are fetched.

In step 3010 the process performs a DWT on each column of the LL1 subband and generates rows 1 to K of the LC and Hc sub-images. During the process some intermediate subband data are written into the second level intermediate results buffer 2560 through connection 3015. In step 3020 the process performs DWT on every row in the Lc subimage to generate the LL2 and HL2 subbands. In step 3025 the process only performs DWT on every row in the Hc sub-image to generate LH2 and HH2 subbands.

Step 2845 in Fig. 28 is now described in further detail with reference to Fig. 31.

The process begins at step 3105, when rows 3+2nK to 3+2K(n+1) of the LL1 subband are fetched. In step 3110 the process performs DWT on each column of the LL1 subband and generates rows 1+nK to K(n+l) of the L' and HC sub-images. During the process some intermediate subband data are written into the second level intermediate results buffer CFP I909AU(STANDARD 08) [I:\ELEC\CISA\Standard\Standard8]527050spec.doc:SDB 2560 through connection 3115. In step 3120 the process performs DWT on every row in the Lc sub-image to generate the LL2 and HL2 subbands. In step 3125 the process only performs DWT on every row in the Hc sub-image to generate LH2 and HH2 subbands.

Steps 3020 in Fig. 30 and 3120 in Fig. 31 are now described in more detail with reference to Fig. 32. In step 3205 the first level DWT unit 1415 row-analyses the first 3 samples in each row and generates some intermediate subband row data. These intermediate data are written into the second-level row-intermediate result buffer 3210 internally. After that, in step 3215 the process checks whether there are any more samples in the row. If there is not, then the process finishes. If there is, then in step 3220 the process checks whether there are 2K samples left in the row. If there is (YES), processing continues at step 3230. If there is. not, then in step 3225 the process symmetrically extends the samples to 2K samples. In step 3230 the process performs a DWT on the next 2K samples on each row of the block. In step 3235, the process sends rows 1 to K of the LL2 band to external memory 1470 in Fig. 14. In step 3240 the process sends the generated HL block (from rows 1+nK to to the second level entropy coder 2580 through connection 3245. After that the process returns to step 3215 to check whether there are any more columns to process.

Steps 3025 in Fig. 30 and 3125 in Fig. 31 are now described in more detail with reference to Fig. 33. In step 3305 the first level DWT unit 1415 row-analyses the first 3 samples in each row and generates some intermediate subband row data. These intermediate data are written into the second-level row-intermediate result buffer 3310 internally. After that, in step 3315 the process checks whether there are any more samples in the row. If there is not, then the process finishes. If there is, then in step 3320 *the process checks whether there are 2K samples left in the row. If there is (YES), processing continues at step 3330. If there is not, then in step 3325 the process symmetrically extends the samples to 2K samples (columns).

In step 3330 the process performs DWT on the next 2K samples on each row of the block. In step 3335, the process sends the generated LH and HH blocks (from rows l+nK to to the second level entropy coder 2580 through connection 3340. After CFP 1909AU(TANDARD 08) [I:\ELEC\CISRA\Standard\Standard08]527050Spec.doc:SDB -46that the process returns to step 3315 to check whether there are any more columns to process.

To further expand upon the above process a worked example is provided below.

In this example K equals 16, so that the first level DWT unit can accept up to 69 samples, while the second level DWT unit can accept up to 39 samples.

In the first pass P[1:73] are fed into the first DWT unit, which produces LL1[1:35], HL1[1:35], LH1[1:35], HH1[1:35]. HL1[1:32], LH1[1:32] and HH1[1:32] are to sent to the entropy coder, while the rest of those sub-bands are discarded. LL1[1:35] is fed to the second level DWT unit, which generates LL2[1:16], HL2[1:16], LH2[1:16], HH2[1:16] and 3 second level intermediate results. The second level inter-mediate results are written into external memory, while LL2, HL2, LH2 and HH2 are sent to the entropy coder immediately.

In the second pass, P[67:137] and the 3 lines of first level intermediate results are S• fed into the first level DWT unit, and LL1 [33:67], HL1[33:67], LH1[33:67], HH1[33:67] and another 3 lines of first level intermediate results are generated. HL1 [33:64], LH1[33:64], and HH11[33:64] are fed into the entropy coder. LL1[35:67] is fed into the second-level DWT unit. The second-level DWT unit generates LL2[17:32], HL2[17:32], LH2[17:32], HH2[17:32] and 3 lines of second level intermediate results, each of them half the width of the image. All outputs are fed into the entropy coder.

Suppose that there are 256 lines in total. In the last pass, P[195:256] and the 3 lines of intermediate values are fed into the first level DWT unit. The remaining inputs are fed with symmetric extension of the image. The first level DWT unit generates LL [97:128], HL1[97:128], LH1[97:128] and HHl[97:128]. HL1[97:128], LHO[97:128], and HHO[97:128] are fed into the entropy coder. The LL1 [99:128] (with the missing inputs filled with symmetric extension) are fed into the second level DWT unit, which generates LL2[49:64], HL2[49:64], LH2[49:64] and HH2[49:64] that are all going to the entropy coder.

CFP I 909AU(STANDA-D 08) [I:\ELEC\CISRA\Standard\Standard08]527050_spec.doc:SDB -47- In accordance with further embodiments of the invention, corresponding methods, apparatuses, and computer program products for encoding a compressed bitstream can readily be implemented based on the noted decoding techniques.

The foregoing only describes a small number of embodiments of the present invention. However, modifications and/or changes can be made thereto by a person skilled in the art without departing from the scope and spirit of the invention in the light of this disclosure. The present embodiments are, therefore, to be considered in all respects illustrative and 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 corresponding meanings.

CFP I909AU(STANDARD 08) [I:\ELEC\CSRA\Standard\Standard08]527050spec.doc:SDB

Claims (32)

1. A method of decoding a compressed bit stream, said compressed bit stream being derived from a discrete wavelet transform image comprising a low-low frequency subband and a plurality of high frequency subbands, each subband being divided into plurality of blocks and each block substantially independently entropy encoded into said compressed bit stream, said method comprising the steps of: a) entropy decoding a current block for each high frequency subband at a current level; b) storing said entropy decoding blocks into a first (fast) memory; c) if said current level is a highest level of the discrete wavelet transform image: ca) entropy decoding a corresponding block of the low-low frequency subband of said current level and storing said block into a first (fast) memory; otherwise cb) extracting a corresponding low-low frequency subband block, for said current level, from a second (slow) memory and storing said extracted block into said first (fast) memory; d) performing an inverse discrete wavelet transform upon each block of subband i coefficients at said current level, stored in said first (fast) memory, to produce a block of coefficients of a low-low subband at one level below said current level; e) storing said produced low-low block of coefficients in said first (fast) memory; f) entropy decoding high frequency subband blocks, at a level one below said current level, substantially spatially corresponding to said produced low-low block of coefficients, into said first (fast) memory; g) performing an inverse discrete wavelet transform upon each of said high Sfrequency blocks at one level below said current level and said produced low-low block of coefficients at one level below said current level, to generate a block of coefficients of a low-low subband at two levels below said current level; and h) storing said generated block of low-low subband coefficients into said second (slow) memory.

2. The method according to claim 1, wherein steps f) and g) are performed incrementally upon said independently entropy encoded blocks. CFP1909AU(STANDARD 08) [I:\ELEC\CISRA\Standard\Standard08]527050spec.doc:SDB

3. The method according to claim 1, wherein said steps a) to h) are repeated until the entire bit stream is decoded.

4. The method of according to claim 1, wherein said steps a) to f) are repeated until the entire bit stream is decoded.

A method of encoding an image, said method comprising the steps of: performing a discrete wavelet transform on a first block (portion) of said image to produce a (second) block of each of a LL, HL, LH and HH subband data at a current level and storing said produced blocks in a first (fast) memory; entropy coding the HL, LH and HH (second) blocks; performing a discrete wavelet transform on said second LL block to produce a (third) block of LL, HL, LH and HH coefficients at one level below the current level, and said third HL, LH, HH blocks being stored in said first (fast) memory; storing the third LL block in a second (slow) memory; and entropy coding said HL, LH and HH (third) blocks.

6. A method of encoding an image into a compressed bitstream, said image being divided into a plurality of blocks (portions), said method comprising the steps of: performing a discrete wavelet transform on a first block (portion) of said image to produce a first Low-Low frequency subband and a first plurality of high frequency subband data, for said first block, at a current level and storing said produced blocks in a first (fast) memory; entropy coding the first plurality of high frequency subband data for said first block at a current level into a bitstream; performing a discrete wavelet transform on said first Low-Low frequency subband data for said first block to produce a second Low-Low frequency subband and a second plurality of high frequency subband data, for said first block, at one level below the current level, said second plurality of high frequency subband data being stored in said first (fast) memory; storing the second Low-Low frequency subband in a second (slow) memory; and CFP1909AU(STANDARD 08) [I:\ELEC\CISRA\Standard\Standard08]527050_spec.doc:SDB entropy coding said second plurality of high frequency subband data into the bitstream.

7. The method as claimed in claim 5 or 6, wherein each block (portion) includes a corresponding overlap portion.

8. An apparatus for decoding a compressed bit stream, said compressed bit stream being derived from a discrete wavelet transform image comprising a low-low frequency subband and a plurality of high frequency subbands, each subband being divided into plurality of blocks and each block substantially independently entropy encoded into said compressed bit stream, said apparatus comprising: a) means for entropy decoding a current block for each high frequency subband at a current level; b) means for storing said entropy decoding blocks into a first (fast) memory; c) means for, if said current level is a highest level of the discrete wavelet transform image: *o ca) entropy decoding a corresponding block of the low-low frequency subband of said current level and storing said block into a first (fast) memory; •otherwise cb) extracting a corresponding low-low frequency subband block, for said current level, from a second (slow) memory and storing said extracted block into said first (fast) memory; d) means for performing an inverse discrete wavelet transform upon each block of subband coefficients at said current level, stored in said first (fast) memory, to produce a block of coefficients of a low-low subband at one level below said current level; means for storing said produced low-low block of coefficients in said first (fast) memory; f) means for entropy decoding high frequency subband blocks, at a level one below said current level, substantially spatially corresponding to said produced low-low block of coefficients, into said first (fast) memory; g) means for performing an inverse discrete wavelet transform upon each of said high frequency blocks at one level below said current level and said produced low-low CFP1909AU(STANDARD 08) [1:\ELEC\CISRA\Standard\Standard08]527050Spec.doc:SDB -51 block of coefficients at one level below said current level, to generate a block of coefficients of a low-low subband at two levels below said current level; and h) means for storing said generated block of low-low subband coefficients into said second (slow) memory.

9. The apparatus according to claim 8, wherein said means for entropy decoding f) and said means for performing an inverse discrete wavelet transform g) are performed incrementally upon said independently entropy encoded blocks.

10. The apparatus according to claim 8, wherein operation of said means a) to h) is repeated until the entire bit stream is decoded.

11. The apparatus of according to claim 8, wherein operation of said means a) to f) is repeated until the entire bit stream is decoded.

S12. The apparatus according to claim 8, further comprising said first (fast) memory and said second (slow) memory. 0

13. An apparatus for encoding an image, said apparatus comprising: 20 means for performing a discrete wavelet transform on a first block (portion) of said image to produce a (second) block of each of a LL, HL, LH and HH subband data at a current level and storing said produced blocks in a first (fast) memory; means for entropy coding the HL, LH and HH (second) blocks; means for performing a discrete wavelet transform on said second LL block to produce a (third) block of LL, HL, LH and HH coefficients at one level below the current level, and said third HL, LH, HH blocks being stored in said first (fast) memory; means for storing the third LL block in a second (slow) memory; and means for entropy coding said HL, LH and HH (third) blocks.

,14. An apparatus encoding an image into a compressed bit stream, said image being divided into a plurality of blocks (portions), said apparatus comprising: CFP1909AU(STANDARD 08) [R:\LIBCC]46075.doc:wxb -52- means for performing a discrete wavelet transform on a first block (portion) of said image to produce a first Low-Low frequency subband and a first plurality of high frequency subband data, for said first block, at a current level and storing said produced blocks in a first (fast) memory; means for entropy coding the first plurality of high frequency subband data for said first block at a current level into a bit stream; means for performing a discrete wavelet transform on said first Low-Low frequency subband data for said first block to produce a second Low-Low frequency subband and a second plurality of high frequency subband data, for said first block, at one level below the current level, said second plurality of high frequency subband data being stored in said first (fast) memory; means for storing the second Low-Low frequency subband in a second (slow) memory; and means for entropy coding said second plurality of high frequency subband data S 15 into the bit stream. S

-15. The apparatus as claimed in claim 13 or 14, wherein each block (portion) includes a corresponding overlap portion.

16. A computer program product including a computer readable medium having recorded thereon a computer program for decoding a compressed bit stream, said compressed bit stream being derived from a discrete wavelet transform image comprising a low-low frequency subband and a plurality of high frequency subbands, each subband being divided into plurality of blocks and each block substantially independently entropy 25 encoded into said compressed bit stream, said computer program product comprising: ooo a) computer program code means for entropy decoding a current block for each high frequency subband at a current level; b) computer program code means for storing said entropy decoding blocks into a first (fast) memory; c) computer program code means for, if said current level is a highest level of the discrete wavelet transform image: ca) entropy decoding a corresponding block of the low-low frequency A 1 subband of said current level and storing said block into a first (fast) memory; Sotherwise CFP 1909AU(STAN DARD 08) [R:\LIBCC]46075.doc:wxb cb) extracting a corresponding low-low frequency subband block, for said current level, from a second (slow) memory and storing said extracted block into said first (fast) memory; d) computer program code means for performing an inverse discrete wavelet transform upon each block of subband coefficients at said current level, stored in said first (fast) memory, to produce a block of coefficients of a low-low subband at one level below said current level; e) computer program code means for storing said produced low-low block of coefficients in said first (fast) memory; f) computer program code means for entropy decoding high frequency subband blocks, at a level one below said current level, substantially spatially corresponding to said produced low-low block of coefficients, into said first (fast) memory; g) computer program code means for performing an inverse discrete wavelet transform upon each of said high frequency blocks at one level below said current level and said produced low-low block of coefficients at one level below said current level, to generate a block of coefficients of a low-low subband at two levels below said current level; and computer program code means for storing said generated block of low-low 9. S" subband coefficients into said second (slow) memory.

17. The computer program product according to claim 16, wherein said computer program code means for entropy decoding f) and said computer program code means for performing an inverse discrete wavelet transform g) are performed •incrementally upon said independently entropy encoded blocks.

18. The computer program product according to claim 16, wherein operation of said computer program code means a) to h) is repeated until the entire bit stream is decoded.

19. The computer program product of according to claim 16, wherein operation of said computer program code means a) to f) is repeated until the entire bit stream is decoded.

CFP I909AU(STANDA RD 08) [I:\ELEC\CISRA\Standard\Standard08]527050 spec.doc:SDB -54- The computer program product according to claim 16, further comprising said first (fast) memory and said second (slow) memory.

21. A computer program product including a computer readable medium having recorded thereon a computer program for encoding an image, said computer program product comprising: performing a discrete wavelet transform on a first block (portion) of said image to computer program code means for producing a (second) block of each of a LL, HL, LH and HH subband data at a current level and storing said produced blocks in a first (fast) memory; computer program code means for entropy coding the HL, LH and HH (second) blocks; computer program code means for performing a discrete wavelet transform on said second LL block to produce a (third) block of LL, HL, LH and HH 15 coefficients at one level below the current level, and said third HL, LH, HH blocks being stored in said first (fast) memory; computer program code means for storing the third LL block in a second (slow) memory; and computer program code means for entropy coding said HL, LH and HH (third) S• 20 blocks.

22. A computer program product including a computer readable medium having recorded thereon a computer program for encoding an image into a compressed bit stream, said image being divided into a plurality of blocks (portions), said computer 25 program product comprising: computer program code means for performing a discrete wavelet transform on a first block (portion) of said image to produce a first Low-Low frequency subband and a first plurality of high frequency subband data, for said first block, at a current level and storing said produced blocks in a first (fast) memory; computer program code means for entropy coding the first plurality of high RA4 frequency subband data for said first block at a current level into a bit stream; CFP I 909AU(STANDARD 08) [R:\LIBCC]46075.doc:wxb computer program code means for performing a discrete wavelet transform on said first Low-Low frequency subband data for said first block to produce a second Low-Low frequency subband and a second plurality of high frequency subband data, for said first block, at one level below the current level, said second plurality of high frequency subband data being stored in said first (fast) memory; computer program code means for storing the second Low-Low frequency subband in a second (slow) memory; and computer program code means for entropy coding said second plurality of high frequency subband data into the bit stream.

23. The computer program product as claimed in claim 21 or 22, wherein each block (portion) includes a corresponding overlap portion. is

24. A method of decoding a compressed bit stream, said compressed bit stream *being derived from a discrete wavelet transform image comprising a low-low frequency subband and a plurality of high frequency subbands, each subband being divided into plurality of blocks and each block substantially independently entropy encoded into said compressed bit stream, said method substantially as hereinbefore disclosed with reference 20 to any one or more of Figs. 1 to 36 of the accompanying drawings.

A method of encoding an image, said method substantially as hereinbefore disclosed with reference to any one or more of Figs. 1 to 36 of the accompanying drawings.

26. A method of encoding an image into a compressed bit stream, said method substantially as hereinbefore disclosed with reference to any one or more of Figs. 1 to 36 of the accompanying drawings.

27. An apparatus for decoding a compressed bit stream, said apparatus substantially as hereinbefore disclosed with reference to any one or more of Figs. 1 to 36 of the accompanying drawings. CFP 1909AU(STANDARD 08) [R:\LICC]46075.doc:wxb -56-

28. An apparatus for encoding an image, said apparatus substantially as hereinbefore disclosed with reference to any one or more of Figs. 1 to 36 of the accompanying drawings.

29. An apparatus encoding an image into a compressed bit stream, said apparatus substantially as hereinbefore disclosed with reference to any one or more of Figs. 1 to 36 of the accompanying drawings.

A computer program product including a computer readable medium having o0 recorded thereon a computer program for decoding a compressed bit stream, said computer program product substantially as hereinbefore disclosed with reference to any one or more of Figs. 1 to 36 of the accompanying drawings.

31. A computer program product including a computer readable medium having 15 recorded thereon a computer program for encoding an image, said computer program product substantially as hereinbefore disclosed with reference to any one or more of Figs. 1 to 36 of the accompanying drawings.

32. A computer program product including a computer readable medium having 20 recorded thereon a computer program for encoding an image into a compressed bit 90 stream, said image being divided into a plurality of blocks (portions), said computer program product substantially as hereinbefore disclosed with reference to any one or more of Figs. 1 to 36 of the accompanying drawings. 25 DATED this Twelfth Day of March, 2002 Canon Kabushiki Kaisha Patent Attorneys for the Applicant SPRUSON FERGUSON CFP I 909AU(STANDARD 08) [R:\LBCC]46075.doc:wxb