AU749350B2 - A method and apparatus for encoding and decoding compressed images - Google Patents

Description

-1 A Method and Apparatus for Encoding and Decoding Compressed Images Field of the Invention This invention relates to a method and apparatus for encoding and decoding compressed images, especially, although not exclusively, using a wavelet transform.

Background of the Invention Using a wavelet transform for compressing images leads to very efficient compression and introduces some new features, which can rarely be achieved by other means. However, most of the current implementations of wavelet transforms have at least one significant drawback. In order to perform the wavelet transform of an image in the traditional way, full image buffering is required.

This dramatically increases the minimum amount of memory needed. As a result, it is difficult to provide a cost effective solution for many products, based on embedded microcontrollers and Digital Signal Processors (DSPs). An example of such a known image compression method is described in US Patent No. 5,315,670 entitled "Digital Data Compression System Including Zerotree Coefficient 20 Coding", in which a sub-band decomposer is used, which requires full i image buffering.

A typical solution to the problem of excessive memory requirements by the wavelet transform is the use of nonoverlapping tiling of an input image and processing each tile independently. This solution solves the memory problem, however, the subsequent quantization of the wavelet coefficients usually *introduces undesirable distortions in the wavelet domain which appear on the boundaries of the tiles and become visible after -2decoding of the compressed bit stream, especially at low to medium bit rates.

An article entitled "A block wavelet transform for sub-image coding/decoding" by Eom Kim Kim J. published in Proc. SPIE Vol. 2669, pp. 169-178, Still-Image Compression II, edited by R.

Stevenson, A. Drukarev and T. Gardos describes a wavelet transform implementation which overcomes the need for full image buffering.

However, a detailed examination of the method described therein shows that it is designed to operate with a strict range of filters of equal lengths in the low-pass and high-pass channels. Another disadvantage of this method lies in its inverse procedure, which requires samples from adjacent blocks to perform reconstruction and as a result of this a large memory buffer and significant time to access the samples from each of three blocks is needed.

Brief Summary of the Invention The present invention therefore seeks to provide a method and apparatus for encoding and decoding compressed images which overcome, or at least reduce the above-mentioned problems of the prior art.

20 Accordingly, in a first aspect, the invention provides a method of image compression comprising the steps of receiving an input image; partitioning the input image into a plurality of overlapping S. tiles; decomposing at least some of the tiles into at least one sequence of transform coefficients per tile; and combining the 0 25 sequences of transform coefficients to provide compressed data 0 representing the input image; wherein each of the overlapping tiles :which are not at an edge of the input image has at least one overlap area which overlaps at least two oppositely adjacent tiles.

-3- In a second aspect, the invention provides a method of image decompression comprising the steps of receiving compressed data representing an image; separating the compressed data into a plurality of sequences of transform coefficients, at least one sequence representing one of a plurality of overlapping tiles making up the image; reconstructing each overlapping tile from the corresponding at least one sequence of transform coefficients; and combining the reconstructed tiles to form the image; wherein each tile which is not at an edge of the image has at least one overlap area which overlaps at least two oppositely adjacent tiles.

According to a third aspect, the invention provides apparatus for compressing image data comprising an input terminal for receiving image data; a partitioning module having one or more inputs for receiving at least some tile size and decomposition complexity information and an output providing at least one tile overlap area size which overlaps at least two oppositely adjacent tiles; an input buffer coupled to the input terminal and to the output of the partitioning module for receiving and storing image data corresponding to the size of a tile including its at least one overlap 20 area; and a transform module having an input coupled to the input buffer for decomposing the stored image data to produce compressed image data.

The invention also provides, in a fourth aspect, apparatus for decompressing image data comprising an input terminal for receiving image data; a separator coupled to the input terminal for separating the image data into a plurality of image data sequences; S. an inverse transform module having a plurality of inputs for receiving the plurality of image data sequences and an output providing a plurality of reconstructed tiles, each reconstructed tile -4 being formed by an inverse transformation of one or more of the sequences and forming part of an image and each tile having at least one overlap area which overlaps at least two oppositely adjacent tiles; and an accumulator having an input coupled to the output of the inverse transform module and having an output providing decompressed image data formed by combining at least a pair of adjacent reconstructed tiles.

In this specification, including the claims, the terms "comprises", "comprising" or similar terms are intended to mean a non-exclusive inclusion, such that a method or apparatus that comprises a list of elements does not include those elements solely, but may well include other elements not listed.

Brief Description of the Drawings One embodiment of the invention will now be more fully described, by way of example, with reference to the drawings, of which: FIG. 1 shows a typical transform-based image compression system; oO..

FIG. 2 shows a known method of tiling an image; 20 FIG. 3 schematically shows a typical 2D forward wavelet oeee transform; 4 shows a wavelet coefficient matrix for an image; FIG. 5 schematically shows a typical 2D inverse wavelet transform; FIG. 6 shows a method of tiling an image according to an embodiment of the present invention; FIG. 7 shows a wavelet coefficient matrix for a tiled image; o FIG. 8 schematically shows a 1-dimensional spatially segmented wavelet transform according to an embodiment of the present invention; FIG. 9 shows a 1-dimensional inverse spatially segmented wavelet transform similar to that of FIG. 8, but inverse; FIG. 10 shows a block diagram of an apparatus for carrying out a 2-dimensional spatially segmented wavelet transform according to an embodiment of the present invention; FIG. 11 schematically shows the layout of an overlapping tile used in the apparatus of FIG. FIG. 12 shows the input buffer used in the apparatus of FIG.

FIG. 13 shows the multiplexer used in the apparatus of FIG. FIG. 14 shows a flow chart of the operation of the multiplexer of FIG. 13; FIG. 15 shows a transform module used in the apparatus of FIG. FIG. 16 shows an operating table of the transform module of oooQ FIG. 20 FIG. 17 shows the demultiplexer used in the apparatus of FIG.

FIG. 18 shows a flow chart of the operation of the demultiplexer of FIG. 17; FIG. 19 shows the partitioning and level control module used 25 in the apparatus of FIG. FIG. 20 shows a flow chart of the operation of the partitioning S" and level control module of FIG. 19; FIG. 21 shows a timing diagram of a pair of outputs of the partitioning and level control module of FIG. 19; -6- FIG. 22 shows a block diagram of an apparatus for carrying out a 2-dimensional inverse spatially segmented wavelet transform similar to that of FIG. 10, but inversely; FIG. 23 shows an inverse transform module used in the apparatus of FIG. 22; FIG. 24 shows an operating table of the inverse transform module of FIG. 23; FIG. 25 schematically shows the layout of an overlapping tile used in the apparatus of FIG. 22; FIG. 26 shows the accumulator used in the apparatus of FIG.

22; FIG. 27 shows the inverse partitioning and level control module used in the apparatus of FIG. 22; and FIG. 28 shows a timing diagram of a pair of outputs of the partitioning and level control module of FIG. 27.

Detailed Description of the Drawings Thus, a typical transform-based image compression system is depicted in FIG. 1. An input image is first decomposed by a transform 1 to provide transform coefficients, which are then 20 quantised 2 and then coded 3 for onward transmission. One of the a*.o most popular transforms used in such a system is the wavelet transform.

As mentioned above, in order to perform the wavelet transform of an image in a conventional way a full image buffering 0* ooo25 is required. This increases the minimum amount of memory needed for the wavelet based image processing. As further described above, one known solution to the problem of excessive memory ~requirement by the wavelet transform is th.e use of non-overlapping tiling of an input image and processing each tile independently as -7shown in FIG. 2. In this solution, the input image 4 is partitioned into a number of non-overlapping tiles 5, each of which is then passed to the image compression system separately 6.

A conventional separable forward wavelet transform of twodimensional (2D) signals, such as images at an input 7, is performed with pairs of filters 8 and 9, 10 and 11, 12 and 13, as shown in FIG.

3. Each pair of filters which is used in the conventional wavelet transform is denoted by: H(z) and O(z) where H(z) H(z-) and G(z) G(z Each of the filtering operations is followed by a sub-sampling by the factor of 2 denoted by sub samplers 14, 15, 16, 17, 18 and 19 indicated as 2->1 in FIG. 3. Thus, the first pair of filters 8 and 9 lowpass and high-pass filter the image in lines across the image and the resulting coefficients are sampled by sub-samplers 14 and respectively, so that the results are a set of low-pass coefficients and 20 a set of high-pass coefficients, the two sets adding up to the size of the original image. The set of low-pass coefficients is then filtered by the second pair of filters 10 and 11 to low-pass and high-pass filter the set of low-pass coefficients in columns across the image and the resulting coefficients are sampled by sub-samplers 16 and 17, respectively, so that the results are a set of low-low pass coefficients and a set of low-high pass coefficients. Similarly, the set of high-pass coefficients is filtered by the third pair of filters 12 and 13 to low-pass and high-pass filter the set of high-pass coefficients in columns across the image and the resulting coefficients are sampled by sub-samplers 18 and 19, respectively, so that the -8results are a set of high-low pass coefficients and a set of high-high pass coefficients. The four sets of coefficients from the subsamplers 16, 17, 18 and 19 can thus be represented as four quadrants 21, 22, 23 and 24 of a wavelet coefficient matrix shown in FIG. 4.

Considering the structure depicted in FIG. 3 as a one level 2D forward wavelet transform, then a multilevel 2D wavelet transformation can be achieved by recursively expanding any of the four sets of coefficients obtained from the previous level until the desired level of transformation is reached. Assuming that the filter H(z) is a low-pass filter and the filter G(z) is a high-pass filter, the most typical multilevel decomposition involves the transformation of the coefficients obtained in the band which is processed only with low-pass filters, or the line provided by filter 8, sub-sampler 14, filter 10 and sub-sampler 16. The layout of the wavelet coefficient matrix 20 after a 3-level wavelet decomposition of this type is shown in FIG. 4, where the low-low pass set of coefficients represented by quadrant 21 has been decomposed into four quadrants 25, 26, 27 and 28 and the low-low pass set of coefficients 20 from this second level of decomposition is decomposed a third time to produce the four quadrants 29, 30, 31 and 32.

The 2D inverse wavelet transform procedure is the reverse of the forward procedure and is shown in FIG. 5. In the inverse transformation the four sets of transform coefficients provided at four inputs to each of four up-samplers 33, 34, 35 and 36 are upsampled by a factor of 2, denoted by and are then filtered by inverse filters 37, 38, 39 and 40 to produce inverse low-pass filtered outputs 41 and 43 and inverse high-pass filtered outputs 42 and 44. The inverse low-pass filtered output 41 and inverse high- -9pass filtered output 42 are then summed by adder 45 and then upsampled by up-sampler 47 and inverse low-pass filtered by inverse low-pass filter 48. Similarly, the inverse low-pass filtered output 43 and inverse high-pass filtered output 44 are then summed by adder 46 and then up-sampled by up-sampler 49 and inverse low-pass filtered by inverse high-pass filter 50. The outputs of inverse lowpass filter 48 and inverse high-pass filter 50 are then summed by adder 51.

Typically, as discussed above, if there are no memory restrictions, the wavelet transform is performed on a whole image.

In this case, the layout of the wavelet coefficient matrix is as depicted in FIG. 4. In the case when the amount of memory available for the transformation is limited, the input image is partitioned into non-overlapping tiles and, then, each tile is processed independently. Such tiling allows the amount of memory required to be reduced to a minimum. The size of the tiles used depends on the memory resources available. The layout of a 3-level wavelet coefficient matrix after tiling and transformation is shown in FIG. 7, where it will be seen that each of the tiles 5 from FIG. 2 is 20 represented by a separate matrix 52 of the type shown in FIG. 4.

If the input image is denoted by I, the conventional wavelet transform byW, and non-overlap tiling and the wavelet transformation by WTnonoverlap and with a transformation Map[] that maps the layout of FIG. 7 onto the layout of FIG. 4, then it can be 25 seen that: Map WTnonoverlap(I)] (1) This inequality is due to the discontinuity which is introduced by partitioning the input image into non-overlapping tiles. The main disadvantage of this discontinuity becomes evident when such a 10 transformation is incorporated into an image compression system. In such a case, the quantization that typically follows the transformation procedure in a compression system, inevitably introduces distortions, which become especially pronounced along the boundaries of the tiles due to this discontinuity.

To overcome this disadvantage, a preferred embodiment of the present invention provides a Spatially Segmented Wavelet Transform (SSWT) method, which is based on partitioning of the input image into overlapping tiles, as shown schematically in FIG. 6.

By comparing FIGS. 2 and 6 it can be seen that in the present embodiment, the input image 60 is partitioned into a number of overlapping tiles 61. Each tile 61 is arranged to include the same area as that of the non-overlapping tiles, but to be a bit larger so as to include am overlap area 62 around each edge of the tile 61. Each such "overlapped" tile 61 is then separately passed to the image compression system.

Using the same notation as above, the SSWT method provides: Map[WToverap(I)] (2) whereWToverlap denotes overlapping tiling and, therefore, overcomes the discontinuity introduced by non-overlapping tiling.

For the further description of the SSWT method, the following parameters will be defined: N (3) 25 and LT=M-N-1 (4) for a given Finite Impulse Response (FIR) filter qo...qM-N- I having M taps, which are at q, for i< M-N-1, the parameter L being the number of taps, of the filter on either side of qO of a filter Q(z) for a one-dimensional (1D) signal partitioned into a number of tiles each of which is has a non-overlap portion ofW samples. Thus, -11 for a pair of filters formed by a low-pass filter (LPF) H(z) and a high-pass filter (HPF) the lD SSWT is represented in FIG. 8.

In order to perform the SSWT on a tile, a number of samples from the adjacent tiles are required. The number of samples C depends on the parameters of the filters used and the number of levels of decomposition and can be calculated as follows:

CH

e a d ax{L ,LT} and Cr= '-1/ax{jd,LH 1 (6) where 1>0 and is the number of levels in a multilevel decomposition and the function Max[] is defined as ifa>b Max{a,b}= b, ofeise (7) b, otherwise The extensions CHead and C r ail on each level of decomposition can be calculated using the above equation with I being set to the particular level.

FIG. 8 shows a full tree transformation, in which, on level 0, an input signal 62 is formed ofW samples plus extensions CHead and Cai.

The input signal 62 is processed in parallel using the low-pass and 20 high-pass filters followed by down-sampling operations. As a result the input signal 62 is split into an LPF part 63 and an HPF part 64 at level one, each of which are in turn processed in the recursive manner to form LPF parts 65 and 66 and HPF parts 67 and 68 at level two, the recursive processing continuing until the desired level 25 of decomposition is reached. In such a way, a full decomposition tree is obtained. However, one does not have to follow the full tree and decomposition can be stoped at any level in any branch of the tree.

12 As mentioned above, the most popular decomposition is the one which has only LPF branches further expanded while the HPF ones are left without change. Since this decomposition is used in a majority of applications, the description below will be primarily focused on such a decomposition. However, it should be understood that the embodiment of the invention described below is equally applicable to the full-tree decomposition procedure.

Thus, for the decomposition of the LPF branches only, equations and become: C -Head Tail TTail 1 _Tail 8) CHead Max{L) La -l iz) (8) and CTai =21-1 {L Head LHad 1-1 _I -Ll) (9) T(z) 0"zlz) Similarly, the 1D inverse SSWT procedure is the reverse of that described above and is depicted in FIG. 9, where input vectors of wavelet coefficients 70 are initially up-sampled and then convolved with a pair of inverse filters, with the results being appropriately aligned and summed by adders 71. The level 2 wavelet coefficients 72, being the outputs from adders 71 from level 20 3 are similarly up-sampled, convolved and then aligned and summed by adders 73 to produce the level 1 wavelet coefficients 74. These are themselves up-sampled, convolved, aligned and summed by adders 75 to produce the level 0 final wavelet coefficient sequence 76.

25 By definition, given the length S of a signal and the length F of a filter the result of a convolution has the length of S+F-1. Due to up-sampling which follows the convolution in the process, the valid result of each convolution is given by 2*S+F-2. Therefore, an 13 alignment of the convolved signals before addition should be carried out according to their spatial positions.

Analogously to the forward SSWT, the equations for overlaps, or extensions, of the inverse SSWT can be determined. The full-tree reconstruction generates the following extensions: Head -1)Max({L ad,Lad} and 6Tail= i- _fax( LTail LTail -l 1ax{L(z) (1) where the above notations for 1 and Max[{ are used. If only a partial reconstruction tree given by the LPF part only is required, the extensions are as follows: Head IMa{L Head LeHad 1- 1 yHead (12) -2 Max{L(z),c(z) -H(Iz) and Tai ax{La,L) -1 (13) Each reconstructed tile is placed in an output stream according to its initial position in an input stream. The extensions CHead and CTa", generated on both sides of the tile during the process of upsampling, convolution and addition are summed with the corresponding samples of the adjacent tiles.

20 Although the above description has related to a 1D SSWT, it can be extended to two-dimensional (2D) signals, as will be described below.

A block diagram of a preferred embodiment of an apparatus for carrying out the 2D forward SSWT procedure is shown in FIG.

10. This apparatus 80 includes a partitioning and level control module 81, which receives input information relating to the length of the filters H(z) and the required number of levels I of iteration of decomposition that are required, and the horizontal extent W and vertical extent H of each tile, not including the overlap -14areas. As will be more fully described below, the partitioning and level control module 81 controls a wavelet transform module 82 to control the partitioning and decomposition of an input image provided at input 83 into a number of sequences of transform (wavelet) coefficients at outputs 84. The wavelet transform module 82 is formed by an input buffer 85 which is configured by the partitioning and level control module 81 to store the amount of the input image at input 83 corresponding to one tile, including its overlap area. The output of the input buffer 85 is passed through a multiplexer 86 to an input of a horizontal transform module 87.

As will be described further below, the horizontal transform module decomposes the tile bitstream at its input into two sequences of transform coefficients, each of which is passed to a respective vertical transform module 88 and 89, where the respective two sequences are further decomposed into a total of four sequences forming the outputs 84. This horizontal and vertical twostage decomposition constitutes one level of decomposition. If "-"further levels of decomposition are required, as described above, one or more of the outputs 84 is coupled via a demultiplexer 20 back to the multiplexer 86. In this way, the LPF branch, for ego• example, can be returned to the input of the horizontal transform module 87 for further decomposition instead of being passed to the output, via demultiplexer 90 and multiplexer 86. To support a fulldecomposition tree, demultiplexers would, of course, need to be 25 included in each of the output channels. The multiplexer 86, demultiplexer 90 and the transform modules 87, 88 and 89 are also controlled by the partitioning and level control module 81 to control levels of decomposition as well as the decomposition itself, as will also be further described below.

15 The layout of a tile 61, which the input buffer 85 is configured to receive, is depicted in FIG. 11. Although the vertical extent H and horizontal extent W of the tiles in the 2D SSWT method depends on the amount of memory available in the system, the size of the overlap C is analogous to the 1D SSWT and a function of the parameters of the particular filters used and the number of levels in a multilevel decomposition.

Thus, the overlaps in the horizontal direction are calculated as follows: cHead Ax "Tail r Tail 1 -1 __)Tail 1 C 1 (14) l Horz z t^ z) P (z) and C Tail 2 LrHead LHeadl 1_(2I1-1 lrHad-1) -Horz2 z ax(L LM The overlaps in the vertical direction are equal to the corresponding overlaps in the horizontal direction, that is: c' Head c Head Ver CHo (16) and Cl cTai (17) Vert Horx provided the same filters are used in both horizontal and vertical directions. In the case where different filters are used in the horizontal and vertical directions, the values of the overlaps are calculated based on the parameters of the filters used.

After partitioning, each tile, including the required amount of overlap, is placed into the input buffer 85, as shown in FIG. 10. The input buffer 85, which is shown in more detail in FIG. 12, has a first 25 input 91 and a second input 92 and an output 93. The first input 91 is coupled to receive the input image data. Second input 92 is coupled to the partitioning and level control module 81 and is used to configure the input buffer 85 to the amount of memory needed to hold one tile at a time. The size of the tiles, including the amount of -16overlap required, are set by the partitioning and level control module 81 after it has calculated the overlap required.

From the input buffer 85 each tile is sent through the multiplexer 86 to the horizontal transform module 87. A more detailed diagram of the multiplexer 86 is shown in FIG. 13 and a flow chart of its functionality is shown in FIG. 14. The multiplexer 86 has two first and second data inputs 94 and 95, a third input 96 and an output 97. The first and second data inputs 94 and 95 are coupled, respectively to the output of the demultiplexer and to the output 93 of the input buffer 85. The third input 96 of the multiplexer 86 is driven by the partitioning and level control module 81 and is set to 0 when further levels of decomposition are required for an already decomposed signal. Otherwise, the third input 96 is set to 1 by the partitioning and level control module 81.

As can be seen by reference to FIG. 14, the multiplexer 86 operates by firstly checking 98 whether the third input 96 is set to 0 or 1. If it is 0, the multiplexer sets 99 the output 97 to be the first input 94, and if the third input 96 is 1, then the multiplexer sets 100 the :00% output 97 to be the second input 40090 •o°•e 20 The transform modules 87, 88 and 89 are shown in more detail in FIG. 15 with their operating table being shown in FIG. 16.

Each transform module includes a first input 101 for receiving data and a second input 102 for receiving control signals from the O• O partitioning and level control module 81. The first input 101 is split 25 into two filtering channels. A first channel leads to a low pass filter *see 103 and thence to a first down sampler 104 from which exits a first o: output 105. The second channel leads to a high pass filter 106 and thence to a second down sampler 107 from which exits a second output 107. The second input 102 is a two channel input, one -17 channel being coupled to control the low pass filter 103 and the second channel being coupled to control the high pass filter 106.

Depending on the control signals on these two channels of the second input 102, the filters will or will not be active. The operation of the filters in accordance with the control signals is shown in the table of FIG. 16. The filters 103 and 106 are followed by the down samplers 104 and 107, which disregard every second sample appearing on their input lines to provide the first and second outputs 105 and 108.

Referring back to FIG. 10, it will be seen that the first output of the horizontal transform module 87 is coupled to the first input of first vertical transform module 88 and the second output of the horizontal transform module 87 is coupled to the first input of second vertical transform module 89. The second output of the first vertical transform module 88 and the first and second outputs of the second vertical transform module 89 directly provide the output stream 84 of the forward SSWT. The first output of the first vertical transform module 88, which, of course, passed through the LPF channels of both the horizontal transform module 87 and the first vertical transform module 88 is coupled to a first input of the demultiplexer 90, which is shown in more detail in FIG. 17.

flow chart of the function of the demultiplexer 90 is shown in FIG 18. As shown in FIG. 17, the demultiplexer 90 has a second input 111 and first and second outputs 112 and 113. The second input 111 is coupled to the partitioning and level control module 81 and is set to 0 if further levels of decomposition are required for an o already decomposed signa. Otherwise, the second input 111 is set to 1 by the partitioning and level control module 81. As can be seen by reference to FIG. 18, the demultiplexer 90 operates by firstly -18 checking 114 whether the second input 111 is set to 0 or 1. If it is 0, the demultiplexer sets 115 the first output 112 to be the input 110, and if the second input 111 is 1, then the demultiplexer sets 116 the second output 113 to be the input 110. Thus, if the third input 96 of multiplexer 86 and second input 111 of demultiplexer are set to 0, the LPF channel of the first vertical transform module 88 is looped back through the demultiplexer 90 and multiplexer 86 to the input of horizontal transform module 87 for a further level of decomposition, otherwise, if the third input 96 of multiplexer 86 and second input 111 of demultiplexer 90 are set to 1, the LPF channel of the first vertical transform module 88 is passed to output 84.

As will be appreciated, the partitioning and level control module 81, which is shown in more detail in FIG. 19, monitors and controls the flow of data through the entire system. The partitioning and level control module 81 is fed with the set of parameters needed to perform the 2D forward SSWT. A first input 120 provides the horizontal extent W and vertical extent H of the tiles, not •including the overlap areas. The number of levels 1 in a multi-level decomposition is fed through a second input 121. Finally, the decomposition filters O(z) and H(z) are provided via a third input 122.

Using equations (14) the partitioning and level control module 81 calculates the horizontal and vertical overlaps and S2.' 25 together with W and H passes them to the second input 92 of input buffer 85 via a third output 123. These data are used in the input ***buffer 85 to set up a memory array of the size of a tile, including the overlaps.

-19- Another function of the partitioning and level control module 81 is monitoring the level of decomposition, as shown in the flow chart of FIG. 19. From the number of samples in the input tile, the partitioning and level control module 81 calculates the number of samples at every step of transformation and initialises 126 its second output 124, which is coupled to the third input 96 of multiplexer 86, to 1. A level check 127 is then carried out and, if the final required level of decomposition has been carried out, then the second output 124 is maintained 132 at 1 so that the third input 96 of multiplexer 86 and second input 111 of demultiplexer 90 are thus set to 1 so that the LPF channel of the first vertical transform module 88 is passed to output 84. If, however the level check 127 indicates that the final required level of decomposition has not yet been reached, then the level indicator is decremented 128 by 1 and processing of the input data in the horizontal transform module 87 takes place 129. As soon as data has passed through the horizontal transform module 87, the second output 124 is set 130 to 0 so that the third input 96 of multiplexer 86 and second input 111 of demultiplexer 90 are set to 0. Thus, as the data processed 131 is processed in the vertical transform modules 88 and 89, the data in the LPF channel of the first vertical transform module 88 is passed back to the first input 94 of the horizontal transform module 87.

The level check 127 is then carried out again after the processing 131 in the vertical transform modules 88 and 89 has finished.

A six channel first output 125 of the partitioning and level control module 81 is used to control the transform modules 87, 88 and 89. The three pairs of channels are connected respectively to the two channel second inputs 102 of the transform modules 87, 88 and 89. A timing diagram showing the timing for the two channels 20 making up the first pair of the first output 125 of the partitioning and level control module 81 which are coupled the second input 102 of the horizontal transform module 87 is shown in FIG. 21. As can be seen, the first pair of channels of output 125 is set to 1 for a period of A C 1

C

2 for channel 1:0 and for a period of A B, B 2 for channel 1:1, where the values of A, B 1

B

2 C, and C 2 are calculated as follows: A 2l W (18) B L)l (19)

B

2 =LHead -1 C 1) CHo as in equation if 1 1 rHead, ,f 1

C

2 (22) SCT" as in equation (4),if I >1 where I is the current level of decomposition.

The remainder of the channels of the first output 125 of the partitioning and level control module 81 used to control the vertical •transform modules 88 and 89 are set in the same manner, but W is substituted by H.

A block diagram of a preferred embodiment of an apparatus 140 for carrying out the inverse SSWT procedure is shown in FIG.

22. Apart from P and Q, which denote the numbers of tiles in the horizontal and vertical directions, respectively, the notation used in FIG. 22 is the same as that used with respect to FIG. 10 above. Thus, the apparatus 140 includes an inverse partitioning and control module 141, which receives input information relating to the length of the inverse filters and the number of levels I of iteration of convolution that are required, and the horizontal extent W and -21 vertical extent H of each tile, not including the overlap areas, as well as P and Q mentioned above.

As will be more fully described below, the inverse partitioning and level control module 141 controls an inverse wavelet transform module 142 to control the reconstruction of the tiles and their combination into a complete image provided at output 144 from a number of sequences of transform (wavelet) coefficients provided at inputs 143. The input 143 to the inverse SSWT is the same format as the output streams 84 of the forward SSWT (FIG.

The coefficients generated by the LPF operations in the forward SSWT pass through a multiplexer 145 in the inverse wavelet transform module 142. The multiplexer 145 is similar to multiplexer 86 described above with reference to FIGS. 13 and 14.

Analogously to the forward procedure, the multiplexer 145 is controlled by the inverse partitioning and level control module 141.

All the other coefficients are sent directly to first and second oooo vertical inverse transform modules 146 and 147.

The outputs of the vertical inverse transform modules 146 and :.7 20 147 are passed to a horizontal inverse transform module 148, whose output is passed to an input of a demultiplexer 149. The demultiplexer either passes its input to an accumulator 150, where the tiles reconstructed by the inverse wavelet transform module 142 are combined into the complete image, or back to the multiplexer 145 for further reconstruction, depending on the number of levels of reconstruction required.

The inverse transform modules 146, 147 and 148 are shown in more detail in FIG. 23 with their operating table being shown in FIG. 24. Each inverse transform module includes first and second 22 data inputs 151 and 152 for receiving two data streams and a third input 153 for receiving control signals from the inverse partitioning and level control module 141. The first input 151 leads to a first up sampler 154 and thence to a low pass filter 155. The second input 152 leads to a second up sampler 156 and thence to a high pass filter 157. The third input 153 is a two channel input, one channel being coupled to control the low pass filter 155 and the second channel being coupled to control the high pass filter 157. Depending on the control signals on these two channels of the third input 153, the filters will or will not be active. The operation of the filters in accordance with the control signals is shown in the table of FIG. 24.

The filters 155 and 157 are followed by an adder 158, which combines the results of the two filters 155 and 157 to provide an output 159.

The outputs 159 of the vertical inverse transform modules 146 and 147 are connected to the first and second inputs 151 and 152 of the horizontal inverse transform module 148. Whereas the vertical inverse transformation modules 151 and 152 operate on columns of the 2D input stream, the horizontal inverse transformation module 148 operates on rows. Therefore, a 2D separable convolution is achieved.

The layout of the tile 160 at the output of the horizontal inverse transform module 148 is depicted in FIG. 25. The extensions C are calculated are follows: ^Hed 'Max{ PI ,a ead 1-1 lHd Co MaxzL) L(2 H( (23) and 6 Til- (24)jrTail Horz IVH(-z) (24) -23- If the same filters are used in both horizontal and vertical directions, the extensions in the vertical direction are the same as the corresponding extensions in the horizontal direction, that is: rt Horz and Tail jTail Vrt CHorz (26) In the case where the filters used in the horizontal and vertical directions are different, the extensions are calculated based on the parameters of the filters used.

The output of the horizontal inverse transform module 148 is sent to the accumulator 150 through the demultiplexer 149 depicted in Figure 9, which is similar to the demultiplexer 90 described above with reference to FIGS. 17 and 18. If a multi-level reconstruction is performed, the first output of the demultiplexer 149 is connected to the first input of the multiplexer 145 to form an internal loop.

Otherwise, the demultiplexer 149 passes its input to its second output, which is connected to a first input 161 of the accumulator, which is shown in more detail in FIG. 27. Each tile, received by the S"accumulator 150 at its first input 161, is spatially aligned and then 20 positioned according to the tile's initial position in the input image.

The initial position of the current tile is set through second input 162 by the inverse partitioning and level control module 141. The extensions C generated during the reconstruction phase, as shown in FIG. 25, are summed with the corresponding values of the adjacent tiles. In such a way, an update of the adjacent tiles is performed an provided on the output 144.

S"Analogously to the partitioning and level control module 81 in the forward SSWT, the inverse partitioning and level control module 141 in the inverse SSWT, which is shown in more detail in FIG. 27, 24 carries out full control of data flow in the system. Since the SSWT operates on tiles, the number of tiles in the horizontal and vertical directions P and Q, which are used to cover the entire input image, is known in advance and sent to the inverse partitioning and level control module 141 through a first input 163. These numbers are utilized to compute the position of each tile in the output stream.

The position together with the extensions 6 are provided to the accumulator via the first output 167, as described above. Second third and fourth inputs 164, 165 and 166 of the inverse partitioning and level control module 141 are used to provide information relating to the horizontal extent W and vertical extent H of each tile, the number of levels 1 of iteration of convolution that are required, and the length of the inverse filters H(z) and respectively.

A second output 168 of the inverse partitioning and level control module 141 provides control signals to the multiplexer 145 and the demultiplexer 149, as described above with reference to FIG. 20. A six channel third output 169 of the inverse partitioning oooo """and level control module 141 is used to control the inverse transform modules 146, 147 and 148 via their third inputs 153.

Analogously to the partitioning and level control module 81, the third output 169 of the inverse partitioning and level control module 141 is also split into pairs. A timing diagram for a first pair (Output 1:0 to Output 1:1) connected to the third input of the first vertical inverse transform module 146 is shown in FIG. 28.

In FIG. 28, Inputs 1 and 2 denote corresponding first and second inputs 151 and 152 of the vertical inverse transform module 146. Assuming that the current level of reconstruction is I and the top level is /max, the values of A, B 1

B

2 C, D, and D 2 are calculated as follows: 25 A= 2-'H (27) B LHead BI z) (28)

B

2 L -1 (29) A, if I= m.

x A otherwise

D

I eead D= L) (31) D2 1 (32) (2 where Max{L ead LHead+ 1-1- 'n1 fHead L"l (33 The timing diagram for the inverse transform modules 147 is similar, with all the parameters being calculated as above. Thr timing diagram for inverse transform modules 148 is also similar, with all the parameters being calculated as above, with the exception ofC', which is set to 0.

It will thus be appreciated that the embodiment of the invention described above does not require full image buffering and, therefore, relaxes memory constrains. At the same time, the 20 method is flexible and the amount of memory required can be adjusted depending on the implementation platform. If for some applications the memory size is not critical, this method can operate with full image buffering as well. A useful feature of this method is that it does not require that the encoder and decoder have the same 25 buffer size. For example, if the encoder is in a portable device with a small memory buffer, such as a digital camera, and one of the decoders is in a dissimilar device, such as in a PC, and implemented with full image buffering, this method can cope with this situation without introducing any distortions.

L 26 Furthermore, in contrast to the typical non-overlapping tile method, the above described method does not introduce distortions in the wavelet domain. This feature, namely that no distortions are introduced in the wavelet domain, allows the receiver to decode a bit stream compressed as described above with either the conventional wavelet transform procedure or the one described above.

It will further be appreciated that although only one particular embodiment of the invention has been described in detail, various modifications and improvements can be made by a person skilled in the art without departing from the scope of the present invention.

o oo oooo *e

Claims (15)

1. A method of image compression comprising the steps of: receiving an input image; partitioning the input image into a plurality of overlapping tiles; decomposing at least some of the tiles into at least one sequence of transform coefficients per tile; and combining the sequences of transform coefficients to provide compressed data representing the input image; wherein each of the overlapping tiles which are not at an edge of the input image has at least one overlap area which overlaps at least two oppositely adjacent tiles.

2. A method of image compression according to claim 1, wherein the step of partitioning the input image includes the steps of: providing at least some information as to the non-overlapping size of the tiles; providing information as to the complexity of the decomposition to be undertaken; determining a required size of the at least one overlap area for each tile based on the non-overlapping size of the tiles and the complexity of the decomposition to be undertaken; and configuring a memory to accomodate a part of the input image 25 which has the size of the tile including the at least one overlap area.

3. A method of image compression according to claim 2, wherein the step of receiving information as to the complexity of the decomposition to be undertaken includes the steps of: S S S 28 providing information as to a size of a filter to be used for the decomposition; and providing information as to a number of iterations to be performed in the decomposition.

4. A method of image compression according to any one of claims 1 to 3, wherein the step of decomposing each tile includes carrying out a wavelet transformation on the tile.

5. A method of image compression according to any preceding claim, wherein the step of decomposing each tile includes carrying out a two dimensional decomposition of the tile.

6. A method of image compression according to claim 5, wherein the step of decomposing each tile includes at least one level of decomposition, each level including the steps of: decomposing each tile using high pass and low pass filtering to produce a set of high pass coefficients and a set of low pass transform coefficients; 20 deccomposing each set of coefficients using high pass and low pass filtering to produce a set of high-high pass transform 'coefficients, a set of high-low pass transform coefficients, a set of low-high pass transform coefficients and a set of low-low pass transform coefficients. A method of image decompression comprising the steps of: receiving compressed data representing an image; -29- separating the compressed data into a plurality of sequences of transform coefficients, at least one sequence representing one of a plurality of overlapping tiles making up the image; reconstructing each overlapping tile from the corresponding at least one sequence of transform coefficients; and combining the reconstructed tiles to form the image; wherein each tile which is not at an edge of the image has at least one overlap area which overlaps at least two oppositely adjacent tiles.

8. A method of image decompression according to claim 7, wherein the step of reconstructing each overlapping tile includes carrying out an inverse wavelet transformation on the at least one sequence of transform coefficients.

9. A method of image decompression according to either claim 7 or claim 8, wherein the step of reconstructing each tile includes carrying out a two dimensional reconstruction of the tile. oooeo 20 10. A method of image decompression according to any one of claims 7 to 9, wherein the step of separating the compressed data ~includes the step of separating the compressed data into at least four sequences of transform coefficients and the step of reconstructing each tile includes: a first reconstruction step including: inverse high pass filtering a first sequence of transform coefficients to produce a first high pass filtered sequence; inverse low pass filtering a second sequence of transform coefficients to produce a first low pass filtered sequence; combining the first high pass filtered sequence and the first low pass filtered sequence to produce a first filtered sequence; inverse high pass filtering a third sequence of transform coefficients to produce a second high pass filtered sequence; inverse low pass filtering a fourth sequence of transform coefficients to produce a second low pass filtered sequence; and combining the second high pass filtered sequence and the second low pass filtered sequence to produce a second filtered sequence; and a second reconstruction step including: inverse high pass filtering the first filtered sequence to produce a third high pass filtered sequence; inverse low pass filtering the first filtered sequence to produce a third low pass filtered sequence; combining the third high pass filtered sequence and the third low pass filtered sequence to reconstruct the tile. 0:00 o o

11. A method of image decompression according to any one of 0 S.O.S. claims 7 to 10, wherein the step of combining the reconstructed tiles to form the image includes: storing adjacent tiles including their overlap areas; spatially aligning the adjacent tiles and their overlap areas; adding the at least one overlap area of one tile to a corresponding portion of an adjacent tile; and see& 69 25 repeating the steps of storing, spatially aligning and adding until the complete image has been reconstructed. 0 so

12. Apparatus for compressing image data comprising: an input terminal for receiving image data; -31 a partitioning module having one or more inputs for receiving at least some tile size and decomposition complexity information and an output providing at least one tile overlap area size which overlaps at least two oppositely adjacent tiles; an input buffer coupled to the input terminal and to the output of the partitioning module for receiving and storing image data corresponding to the size of a tile including its at least one overlap area; and a transform module having an input coupled to the input buffer for decomposing the stored image data to produce compressed image data.

13. Apparatus for compressing image data according to claim 12, wherein the transform module comprises: a first transform circuit having a high pass filter with a high pass output and a low pass filter with a low pass output; a second transform circuit coupled to the high pass output of ooooo the first transform circuit and having a high pass filter with a high pass output and a low pass filter with a low pass output; a third transform circuit coupled to the low pass output of the ~first transform circuit and having a high pass filter with a high pass output and a low pass filter with a low pass output, ~the low and high pass outputs of the second and third transform circuits being coupled to outputs of the apparatus.

14. Apparatus for compressing image data according to claim 13, wherein the low pass output of the third transform circuit is selectively switchable to an input of the first transform circuit. 4 32 Apparatus for compressing image data according to either claim 13 or claim 14, wherein the partitioning module comprises: a plurality of control outputs, each coupled to one of the high and low pass filters of the transform module to control the filters to be active for a period corresponding to the tile size and the at least one overlap area required for that filter.

16. Apparatus for decompressing image data comprising: an input terminal for receiving image data; a separator coupled to the input terminal for separating the image data into a plurality of image data sequences; an inverse transform module having a plurality of inputs for receiving the plurality of image data sequences and an output providing a plurality of reconstructed tiles, each reconstructed tile being formed by an inverse transformation of one or more of the sequences and forming part of an image and each tile having at least oo** one overlap area which overlaps at least two oppositely adjacent S• tiles; and an accumulator having an input coupled to the output of the inverse transform module and having an output providing decompressed image data formed by combining at least a pair of adjacent reconstructed tiles.

17. Apparatus for decompressing image data according to claim 25 16, wherein the inverse transform module comprises: S. a first inverse transform circuit having: a first input coupled to a high pass filter; a second input coupled to a low pass filter; and

33- a combiner having a first input coupled to an output of the high pass filter and a second input coupled to an output of the low pass filter and an output; a second inverse transform circuit having: a third input coupled to a high pass filter; a fourth input coupled to a low pass filter; and a combiner having a first input coupled to an output of the high pass filter and a second input coupled to an output of the low pass filter and an output; a third inverse transform circuit having a first input coupled to the output of the combiner of the first inverse transform circuit and a second input coupled to the output of the combiner of the second inverse transform circuit and an output providing the reconstructed tiles. 18. Apparatus for decompressing image data according to claim 17, wherein the output of the third inverse transform circuit is selectively switchable to an input of the first inverse transform circuit. 19. Apparatus for decompressing image data according to any one of claims 16 to 18, wherein the accumulator comprises: a buffer for storing adjacent tiles including their overlap areas; a controller for spatially aligning the adjacent tiles and their overlap areas; and an adder for adding the at least one overlap area of one tile to at least one corresponding portion of the adjacent tiles. 34 A method of image compression substantially as hereinbefore described with reference to FIGS. 6 to 28 of the drawings. 21. A method of image decompression substantially as hereinbefore described with reference to FIGS. 6 to 28 of the drawings. 22. Apparatus for compressing image data substantially as hereinbefore described with reference to FIGS. 6 to 8 and 10 to 21 of the drawings. 23. Apparatus for decompressing image data substantially as hereinbefore described with reference to FIGS. 6, 7 and 9 and 22 to 28 of the drawings. DATED this 30th day of JUNE 1998 Motorola Australia Pty Ltd *oo *o