AU2006236081A1 - An image compression and decompression apparatus - Google Patents

Description

S&F Ref: 774780

AUSTRALIA

PATENTS ACT 1990 COMPLETE SPECIFICATION FOR A STANDARD PATENT Name and Address of Applicant Actual Inventor(s): Address for Service: Invention Title: Canon Kabushiki Kaisha, of 30-2, Shimomaruko 3-chome, Ohta-ku, Tokyo, 146, Japan David Robert James Monaghan Spruson Ferguson St Martins Tower Level 31 Market Street Sydney NSW 2000 (CCN 3710000177) An image compression and decompression apparatus The following statement is a full description of this invention, including the best method of performing it known to me/us:- 5845c(574635_1) SAN IMAGE COMPRESSION AND DECOMPRESSION APPARATUS

O

Z Field of the Invention The present invention relates generally to image compression and decompression and, in particular, to image compression in a tiled image processing system where memory 00 Sresources are limited.

,O 5 Background 4 In colour printing environments the total uncompressed size of a generated pixel images is often large. It is therefore advantageous to avoid storing the entire image without compressing the image as memory is a significant cost for raster devices such as printers, scanners and computer displays.. Such pixel images are typically generated in raster or band order. In particular, pixels, scanlines, groups of scanlines, or tiles, are emitted in a stream from a raster image processor (RIP) that has as input an object graphic description of the page to be printed. In recent years, image processing applications have typically included more and more functionality for the displaying or printing of images.

Some of these applications have included the capability of performing rotations and reflections of the image. For such applications tile-based storage is desirable as tiles can be rotated reflected repositioned in sequence without excessive memory requirements.

Many schemes have been proposed for image compression. One widely used method for colour images is the baseline method of the Joint Photographic Experts Group (JPEG) standard. Whilst this method is widely implemented, it suffers from a major drawback in that it is impossible to accurately predict the output size of a compressed image without knowing details of the input data ahead of time. Allocating large amounts of memory is typically wasteful and there is still no guarantee that the final compressed image will fit into the memory allocated. Memory requirements for compressed data are 774780 -2-

NO

Sfurther complicated by (and dependent on) the number of intensities (bit depth) of the pixel 0 z data and the addition of further colours (colour channels components). This makes JPEG compression unsuitable for use in a system that has limited memory resources.

Some schemes exist that limit total compressed size by maintaining a sufficiently high compression factor on local regions of the image, but in these schemes it is not

NO

CC possible to trade off one part of the image that compresses well against another that does

(N,

not.

For lossy compression schemes (such as baseline JPEG) the degree of loss must be selected ahead of time. Control of the degree of perceptual degradation (in short, loss) is a common method of controlling the output compression size. But this must generally be selected consistently across a whole image to achieve consistent visual quality, and must be selected at the start of the compression operation. The image may become unnecessarily compressed. Where a high-loss setting is used for a compression operation, it may transpire that the image data compressed well and a less-lossy setting could have been used in comparison with the system's available memory. A less-lossy setting would have resulted in higher final image quality, which is advantageous.

United States Patent No. 6664902 to Andrew et al., which issued 16 December 2003, discloses an image processing apparatus for one-pass compression into a fixed size buffer. This system comprises a Discrete Cosine Transform (DCT) unit for transforming blocks of pixels into respective blocks of transform coefficients, and a plurality of entropy encoders for encoding respective scan partitions of the DCT blocks where at least one scan partition comprises bit-plane data from each of the blocks of transform coefficients. The apparatus also comprises a scan output manager for storing the entropy encoded scan partitions in a buffer of fixed memory size. The manager manages the storing of the coded 774780

NO

scan partitions in the buffer whereby, during the storing of the coded scan partitions, if it is 0 determined the buffer is full, a coded least perceptually significant scan partition currently stored in the buffer is overwritten by data from a coded more perceptually significant scan partition. This method is able to store the compressed image in one pass within a buffer of Fixed size while maintaining uniform quality over the whole page. However, it suffers

NO

Cc from needing a separate Huffman encoding/decoding unit for each scan partition. Lower

(NI

bit-plane data is often noisy and statistical based methods of encoding are often inefficient, particularly when the images are tiled. In some circumstances the compressed data exceeds the uncompressed image in size. Huffman encoders are also complex to implement and overall performance can suffer when multiple encoders are utilised.

A need therefore exists for an algorithm capable of compressing bitplane data that is fast and simple, and takes advantage of tile based storage.

Summary It is an object of the present invention to substantially overcome, or at least ameliorate, one or more disadvantages of existing arrangements.

Disclosed are arrangements which seek to address the above problems by providing tile based storage of compressed image data. An optimum compression quality is achieved for a given fixed memory size, with the compression quality being uniform over the entire image. Certain bitplane scan partitions use fast, simple non Huffman based encoding.

According to a first aspect of the present invention, there is provided a method of compressing an image, wherein the image comprises a plurality of pixels, said method comprising the steps of: partitioning the image into a plurality of blocks of pixels; 774780

\O

transforming the blocks of pixels to produce respective blocks of transform 0 z coefficients; partitioning the blocks of transform coefficients into a plurality of partitions, said partitions having varying perceptual significance; 00 encoding said partitions, wherein at least one high frequency partition is

NO

e¢ encoded using a fixed length encoder; and storing of the encoded partitions in memory, wherein during the storing of the encoded partitions, if it is determined that the memory is full, the encoded partition having least perceptual significance currently stored in the memory is discarded to release memory and the released memory is allocated to an encoded partition having more perceptual significance than said encoded partition having least perceptual significance.

According to a second aspect of the present invention, there is provided a method of encoding an integer, said method comprising the steps of: determining a range within which said integer lies; encoding said range using a predetermined number of bits; and encoding said integer using a number of bits dependent on said range.

According to another aspect of the present invention, there is provided an apparatus for implementing any one of the aforementioned methods.

According to another aspect of the present 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.

Other aspects of the invention are also disclosed.

774780

ID

\O

O

Brief Description of the Drawings z One or more embodiments of the present invention will now be described with reference to the drawings, in which: Fig. la shows a page of tiles; 00 05 Fig. lb shows a single tile;

NO

e¢ Fig. 2 shows a schematic block diagram for an image compressor according to the

IND

present invention; Fig. 3 shows a schematic block diagram for an image decompressor complementing the image compressor of Fig. 2; Fig. 4 shows a schematic flow diagram for a method of encoding refinement bitplanes of AC coefficients as used by the image compressor of Fig. 2; Fig. 5 shows a schematic flow diagram for encoding End of Band Runs as used in the method of Fig. 4; Fig. 6 shows a schematic flow diagram of a method of writing compressed data bitstreams for the refinement bitplanes of AC coefficients, as used in the method of Fig. 4; Fig. 7 shows a schematic flow diagram for reading compressed data bitstreams for the refinement bitplanes of AC coefficients as used by the image decompressor of Fig. 3; Fig. 8 shows a schematic flow diagram for decoding the refinement bitplanes of AC coefficients as used in the method of Fig. 7; and Fig. 9 shows a schematic block diagram of a general purpose computer in which the image compressor and image decompressor of Figs. 2 and 3 may be implemented.

Detailed Description Where reference is made in any one or more of the accompanying drawings to steps and/or features, which have the same reference numerals, those steps and/or features 774780

\O

Shave for the purposes of this description the same function(s) or operation(s), unless the z contrary intention appears.

The principles of the arrangements described herein have general applicability to image compression and decompression. For ease of explanation the arrangements are 00 5 described with reference to image compression used in a colour raster image processing

NO

Ssystem. However, it is not intended that the present invention be limited to the described

IND

arrangements. For example, the present invention may have application to any arrangement utilising compression where memory resources are limited.

The preferred arrangement of the invention compresses rendered data as tiles.

Fig. la shows a page. For the purposes of the present description a page consists of tiles 100 of pixels, there being multiple tiles across the width of the page and multiple tiles down the length of the page. Each tile 100 consists of N by M pixels. Tiles 100 are preferably disjoint and jointly cover the page. Fig. lb shows a single tile 100. The tile 100 preferably consists of an integer number of blocks 102 of 8 x 8 pixels. For an A4 page at a printer resolution of 600 dpi a suitable choice for tile dimensions is for example M N 64.

The position of a pixel within the tile 100, where X and Y are integers, is relative to the upper left hand corner 101 of the tile 100. Integer Y indexes the tile rows whereas integer X indexes the offset of a pixel along a tile row. A tile row consists of the set of pixels that span the width of the tile 100. For example the first pixel 101 in the first tile row occupies pixel position whereas the last pixel 103 in first tile row occupies pixel position Similarly, the last pixel 104 in the last tile row occupies position (63,63). Raster tile order refers to processing a tile pixel by pixel, tile row by tile row, in 774780 -7-

NO

sequential order, starting with the first tile row and ending with the last row, as illustrated

O

z within tile 100 in Fig. la.

Pixel values are preferably represented by three channels representing a red component a green component and a blue component (referred to as RGB), 00 05 with 8 bits of precision per channel (referred to as bit depth). Other colour representations

INO

Cc such as one cyan, one magenta, one yellow and one black channel (referred to as CMYK) could also be utilised, along with other bit depths.

Where the dimensions of a page do not contain an integer number of tiles the page is preferably padded to the requisite size. Typically tiles 100 are processed one by one, but tiles 100 may also be processed in parallel.

The preferred arrangement of an image compression system described herein is specific to image data arranged in tile format. The preferred arrangement follows a particular mode of progressive JPEG. It is however noted that a number of the processes employed in the arrangement are not conformant to the progressive JPEG standard.

Compression Fig. 2 shows a schematic block diagram of an Image Compressor 200. The Image Compressor 200 may be implemented using a computer system 900, such as that shown in Fig. 9 wherein the components of the Image Compressor 200 are implemented as software executed within the computer system 900. The Image Compressor 200 consists of a Minimum Coding Unit (MCU) select module 208, a Colour Deinterleave module 207, a Discrete Cosine Transform (DCT) Encoder 206, a Scan Output Manager 205, a Huffman Encoder 202, a Bit Packing Module 203, a Fixed Length Encoder 204, and a Compressed Data Manager 201.

774780

\O

c The MCU Select module 208 receives as input image pixels 209 and partitions z each tile into blocks (minimum coding units or MCUs) of preferably 8 by 8 pixels suitable for the DCT Encoder 206. The Colour Deinterleave module 207 separates the 8 by 8 blocks of colour data into component colour channels to be passed to the DCT Encoder 0 206.

C

c The DCT Encoder 206 consists of a Forward Discrete Cosine Transform (FDCT) \,l Smodule 206a, a Quantiser 206b, and a Differential Pulse Code Modulation (DPCM)

O

Predictive Coder 206c. The FDCT module 206a may be any known DCT unit, but preferably the FDCT module 206a is lossless. A lossless DCT module transforms integer pixels to integer transform coefficients. The FDCT module 206a performs a discrete cosine transform on each component colour channel of each 8 by 8 block of colour data.

The Quantiser 206b quantises the resultant transformed data by a pre-determined set of tables. The DC coefficients output from Quantiser 206b are DPCM encoded using a ID predictor. The predictor is the DC value of the previous 8 by 8 block coded from the same colour channel.

The Scan Output Manager module 205 carries out a point transform on coefficients generated by the FDCT module 206a partitioning those coefficients into bitplanes according to scan partitions as described in the scan partiton table shown in Table 1 below.

The Huffman Encoder 202 consists of a DC Huffman encoder unit 202a and AC Huffman Encoder unit 202b. The DC Huffinan encoder unit 202a and the AC Huffman Encoder unit 202b are statistical encoders that utilise variable length symbols to losslessly encode transformed data. The Bit Packing Module 203 codes bits directly without making any attempt to predict the bits. The Fixed Length Encoder 204 uses fixed length symbols 774780 -9-

NO

to losslessly encode literal strings of transformed data. The arrangement of scan partitions 0 z is such that the encoders 202 to 204 used are considering separated streams of data that differ in their perceptual contribution to the resultant image. In the preferred arrangement varying perceptual significance of scan partitions is achieved by encoding bit planes 00 5 separately and using different encoders 202 to 204.

SThe Compressed Data Manager 201 is used to manage the output data bitstreams

(NO

from the Huffman Encoder 202, the Bit Packing Module 203 and the Fixed Length Encoder 204, and input scan data bitstreams to the decoders. The function of the Compressed Data Manager 201 is threefold: memory allocation, tile data location, and releasing memory when resources become exhausted. The Compressed Data Manager 201 has access to a fixed amount of free memory for allocation to the output scan data bitstreams. Memory is allocated from this free memory in fixed sized chunks. As data is passed from each of the processors the Compressed Data Manager 201 allocates fixed sized chunks of memory to each of the output data bitstreams as required, and the data is stored at those memory locations. Pointers to the memory locations within the output scan data bitstreams are maintained such that compressed data associated with each tile 100 can be retrieved. If the free memory is exhausted (or full) before compression is completed the Compressed Data Manager 201 discards the least perceptually significant scan data bitstream. The released memory is returned to free memory for allocation to more perceptually significant scan data bitstreams.

The FDCT module 206a performs a discrete cosine transform on each channel of each MCU of image data as used in the JPEG standard. Preferably the quantization table for each component is a "flat" table where each entry consists of the value 8. However, other quantization tables are possible. For example, a quantization table where the value is 774780

\O

4 for the DC value of each component, and 8 for the AC values for each component may 0 z be used. If a lossless DCT is employed the quantization step is optional, as the DCT coefficients are already integer values.

The coefficients output from the DCT Encoder 206 are then broken into scans by the Scan Output Manager 205 as described in the Scan Partition Table (Table 1) shown

NO

Sbelow. Each row in the table specifies one (encoding) partition. All transformed colour components for a given scan are encoded in a single partition, unlike JPEG which requires separate scans for each colour component for AC coefficients. The DCT coefficients from each of the components are coded sequentially. The Ss Se column specifies the start (Ss) l0 and end (Se) indices, following a JPEG-style zig-zag sequence of DCT coefficients, of a contiguous sub-sequence of DCT coefficients that are encoded in the partition. Therefore, for example, the second row of the table specifies that in the second partition DCT coefficients 1 to 16 are encoded. The bitplanes are numbered consecutively from the least significant bitplane (zero bitplane) to the most significant bitplane. The Ah Al column specifies the bit precision high and bit precision low parameters respectively used in the successive approximation mode of progressive JPEG. Ah set to zero indicates that all bitplanes above and including that indicated by Al are included in the scan partition.

The first scan partition consists of data from bitplanes 1 and above. Scan partitions 2-4 inclusive consist of the data from bit-planes 2 and above, as specified by the Ah:AI 0:2 pair. Scan partition 1 consists of the upper bitplanes 7 to 1 for the DC coefficient (zig-zag index 0) for each colour component. Scan Partition 2 consists of the bit-plane data for all bit-planes above and including bitplane 2 for AC refinement coefficients 1-16 for each colour component. Similarly, scan partition 3 comprises the same bitplanes for AC refinement coefficients 17-32. Also, scan partition 4 comprises the 774780 -11same bitplanes for AC refinement coefficients 33-63. In Partition 5 a new Ah:AI 2:1 pair is used. This pair specifies that bit-plane Al=1 is transmitted in this scan partition. Thus, scan partition 5 consists of the bit-plane 1 of the AC refinement coefficients 1-16 for each component. Scan partition 8 consists of bit-plane 0 for the DC coefficient for each colour components. Finally, scan partitions 9 to 11 consist of bit-plane 0 for the AC refinement coefficient for each components for the same frequency bands as scan partitions 5 to 7 respectively. AC refinement coefficients 1 32 may be termed low frequency type partitions, whereas AC refinement coefficients 33 63 may be termed high frequency type partitions.

Partition Encoder/Decoder Ss Se Ah: Al 1 Huffman (DC) 0-0 0:1 2 Huffman (AC) 1 16 0:2 3 Huffinan (AC) 17 32 0:2 4 Huffman (AC) 33-63 0:2 Fixed Length 1 16 2:1 6 Fixed Length 17 32 2:1 7 Fixed Length 33 63 2:1 8 Bit Packing 0-0 9 Fixed Length 1 16 Fixed Length 17 32 11 Fixed Length 33 -63 Table 1: Scan partition table The arrangement of scan partitions is such that the encoders 202 to 204 consider separated streams of data that differ in their perceptual contribution to the resultant image.

For the scan partitions 1 to 4 (stream multiple bit-planes of each coefficient are 774780 -12-

\O

O

C1 effectively coded together. For the remaining scan partitions, each bit plane is separately z encoded. Stream 2 consists of scan partitions 5 to 7 and 9 to 11, and stream 3 consists of scan partition 8.

In the baseline model of JPEG compression the end-of-block (EOB) symbol is used to indicate the end of an encoded block; that is all remaining AC coefficents,

NO

Sincluding the 63rd, for the MCU are zero. In this respect the EOB symbol acts as an

IND

escape symbol which terminates the MCU. In the progressive model of JPEG used by the preferred arrangement, cases often arise where all values for AC coefficient bitplanes within a given scan partition of a given MCU are zero. For instance, scan partition 4 (0:2) only has non-zero values on occasions where AC coefficients 32 63 greater than 3 exist, which is rare even for noisy image data. Zero values for all AC coefficients within an MCU can happen for other scan partitions as well. Consequently, cases arise where many consecutive MCU's within a tile have all zero values for a given colour channel of a given scan partition. For this reason it is preferable to define a symbol set to indicate consecutive runs of MCU's that have all zero values within a scan partition rather than coding a separate EOB for each zero valued MCU scan partition. In the progressive JPEG model these symbols are known as End of Band runs (EOBn's). For this reason a set of EOBn symbols are preferably incorporated into the Huffman Encoder 202 and Fixed Length Encoder 204.

There are several types of encoding utilised within the preferred arrangement.

The appropriate method is chosen according to which scan partition data stream is being encoded. The encoding methods used by the Image Compressor 200 are statistical encoding methods, bitpacking and fixed length, and each stream is encoded by one of these 774780 -13-

\O

methods, as shown in column 2 of Table 1. Each of the encoding methods will now be 0 z described in detail.

The top 7 bits of the DC coefficient (Scan Partition 1) as encoded by the DPCM representing the difference between the current value and the value for the preceding MCU. The differences are built into a symbol consisting of a Huffman coded SIZE value, Swhich determines the exact number of bits required to specify the difference, and the bits

IND

required to fill out the value, separately Huffman coded by the DC Huffman encoder 202a.

Runs of zeroes are built into a distinct symbol containing a code and a runlength value, and Huffman coded. The remaining bit plane of the DC coefficient (Scan Partition 8) is emitted io0 as-is and bit packed by the Bit Packing module 203.

Prior to encoding the AC coefficients of a MCU, an array that indicates the signs of the AC coefficients is initialised to zero. This 'signs array' is shared between the AC Huffman Encoder 202b and Fixed Length Encoder 204. The purpose of the signs array is as follows: After a scan partition is processed, the corresponding values in the signs array are either set to 1 or depending on the sign of the corresponding coefficient, or remain at 0 if a non-zero bit has not yet been encountered for that coefficient. When a given signs array value is first set to 1 or a sign bit need to be appended to the current scan partition data bitstream.

In the AC Huffman encoder 202b, the top 6 bits of the AC coefficients (Scan Partitions 2, 3, and 4) are encoded using the standard encoding for JPEG AC coefficients.

Each non-zero AC coefficient is encoded as (Run, Size, Value) where Run is the length of the run of zero coefficients prior to the encoded coefficient, and Size is the number of bits required to fully specify Value. Run and Size are Huffman encoded, while Value is represented by the low order Size bits in the encoded coefficient. If Value is positive, it is 774780 -14-

\O

O

emitted as is, otherwise if Value is negative, 1 Value is emitted. Note that the most 0 z significant bit of the emitted bit sequence is therefore 1 for negative values, and 0 for positive values.

The remaining 'refinement' bit planes (1 and 0) of the AC coefficients (Scan Partitions 5, 6, 7, 9, 10 and 11) are coded using a fixed length coding method that literally

NO

encodes the bitplanes. This method is not JPEG compliant and is not part of the JPEG standard.

Fig. 4 shows a schematic flow diagram of a method 400 for encoding AC refinement bitplanes. Method 400 is performed by the Fixed Length Encoder 204 (Fig. 2) and is carried out for each colour channel of each scan partition for each MCU within each tile 100. The Fixed Length Encoder 204 undertakes an initialisation step 401 where bitplane value, val, the bit counter that indicates the size of val, bitpos, and a counter vallength that indicates the last non-zero bit added to val, are initialised with zero values.

A zig-zag index counter, k, is then initialised in step 402 to the start index for the scan being processed. The AC coefficient corresponding to the kth zig-zag index zz[k] is stored in step 403 as a temporary variable temp.

If it is determined in step 404 that the variable temp is less than zero the Fixed Length Encoder 204 proceeds to step 405 where the variable temp is negated and a variable sign is set to The Fixed Length Encoder 204 then proceeds to step 407.

Alternatively, if it is determined in step 404 that the variable temp is greater than or equal to zero then the variable sign is set to 1 in step 406. from step 406 or 405 the Fixed Length Encoder 204 then proceeds to step 407 where variable temp is point transformed according to the value of Al for the scan being processed. The effect of the 774780

IO

C

point transform is that the least significant bit of temp equals the Al-th bit of AC[zz[k]]

O

z with all other bits zero.

After the point transform has been effected the Fixed Length Encoder 204 determines in step 409 whether the variable temp equals 1. If it is determined that the variable temp does not equal 1 then the Fixed Length Encoder 204 proceeds to step 417 C where the counter bitpos is incremented before the counter index is incremented in step

ID

0 408. The method then returns to step 403.

If it is determined that the variable temp does equal 1 then, in step 410, the variable temp is bitshifted to the left by bitpos, the resulting value of temp is masked into val using a bitwise OR operation, the counter bitpos is incremented, and val_length is set to the new value of counter bitpos.

Following step 410 the method 400 determines in step 411 whether the element in the signs array corresponding to the kth zig-zag index is nonzero. If it is determined that the element in the signs array corresponding to the kth zig-zag index is nonzero then the Fixed Length Encoder 204 proceeds to the step 414. Alternatively, if the element in the signs array corresponding to the kth zig-zag index is zero this indicates the first nonzero bit of the AC coefficient has been reached. As a result the sign bit needs to be appended to val.

The sign bit appended to val is either zero if the value of sign is positive or 1 if the value of sign is negative. The value of sign is stored in step 412 as an element in the signs array at the appropriate index.

In step 413 it is determined whether the value of sign is equal to If it is determined that the value of sign is equal to 1 (the only other possibility)then the Fixed Length Encoder 204 proceeds to step 416. Alternatively, if it is determined in step 413 that the value of sign is equal to -1 then a signed bit of 1 is appended to val in step 415, in 774780 -16-

NO

,I similar fashion to step 410. Following step 415 or 413 the bitpos and val_length counters 0 z are incremented in step 416.

Following step 416 or 411 the method 400 continues to step 414 where it is determined whether the index counter k has reached the end index for the scan. If the index counter k is not equal to Se then the Fixed Length Encoder 204 proceeds to step 408.

NO

Otherwise the Fixed Length Encoder 204 awaits the next input scan partition.

INO

The value val for each scan is written into the relevant scan data bitstream by the Compressed Data Manager 201. Fig. 6 shows a schematic flow diagram of a method 600 of writing the scan data bitstream generated by the Fixed Length Encoder 204 into the relevant scan data bitstream. The Compressed Data Manager 201 remains idle until it is signalled by the Fixed Length Encoder 204 that the encoding of a scan partition is completed. The Compressed Data Manager 201 considers the value of val_length, passed from the Fixed Length Encoder 204 for the relevant scan, and determines in step 601 whether value of val_length is greater than zero.. A value of val_length equal to zero indicates there were no non-zero, point transformed, AC coefficients for the given scan partition. In such a case the Compressed Data Manager 201 proceeds to step 607 where the EOBn counter for the scan is incremented.

Alternatively, if it is determined in step 601 that the value of vallength is greater than zero the current EOBn value for the scan is encoded to the scan data bitstream in step 602. The method for encoding EOBn values to the scan partition data bitstream will be described below with reference to Fig. 5. An appropriate length_code and the number of bits required to write the length_code, code_bits, are then determined in step 603 from the Fixed Length Code Table (FLCT) shown below as Table 2. Depending on the scan partition being considered, different code values are used. The first row of the FLCT 774780 17- C indicates which scan partitions the subsequent codes listed below are valid for. The 0 number of bits, code-bits, required to code length_code is determined by the scan partition number; these values are listed in the 2 nd row of the FLCT. Firstly, the Compressed Data Manager 201 bins the val_length value based on the val_length range values in the FLCT.

o0O 5 The corresponding length_code is then determined. The Compressed Data Manager 201 Sthen proceeds to write length_code to the scan data bitstream in step 604. The number of

(N

Sbits required to write val, code_length, is then determined in step 605 using the FLCT based on the code written in step 604. Finally, the Compressed Data Manager 201 proceeds in step 606 to write the lowest order val_length bits of val, that is, without any leading zeros, to the scan data bitstream using codelength bits. The Compressed Data Manager 201 then returns to idle and awaits the next signal from an encoder module.

774780 18- Scan Partitions: 7,11 Scan Partitions: 5,6,9,10 code bits 4 code bits 3 val_length length val_length range _code code_length range code length 0-4 Ox0 4 0-4 Ox0 4 5-6 OxI 6 5 -6 Oxl 6 7-8 0x2 8 7-8 0x2 8 9-10 0x3 10 9- 10 0x3 11 12 0x4 12 11 -13 0x4 13 13- 16 0x5 16 14- 16 0x5 16 17- 18 0x6 18 16 0x6 Read next 3 bits 19-20 0x7 20 0x7 Read EOBn 21 -22 0x8 22 23-24 0x9 24 25-26 Oxa 26 27-28 Oxb 28 29-30 Oxc 31 -32 Oxd 32 32 Oxe read next 4 bits Oxf Read EOBn Table 2: Fixed Length Codes Table (FLCT) The entries Oxe for scan partitions 7 and 11 and 0x6 for scan partitions 5, 6, 9, and as used as 'continuation' codes in case val_length is greater than 32 and 16 respectively and the word size of the system is limited by those respective amounts.

EOBn's are specially coded to take advantage of tiled data. EOBn's are contained wholly within a tile 100. There is a separate EOBn count for each scan partition and EOBn counts span across colour component channels. For example, the EOBn codes in the End of Band Run Table (EBRT) (Table 3 below) are based on tile sizes of 64 by 64 pixels, 774780 -19-

NO

O

c consisting of 3 colour channels. In a 64 by 64 tile there are preferably 64 MCU's per tile

O

z and therefore (3 x 64 192 is the maximum EOBn count possible. EOBn runs are written to the bitstream in step 602 of method 600 (Fig. 6) prior to non-zero scan bitplanes being written to the bitstream.

00

NO

Scan Partitions: 5,6,7,9,10,11 EOBn bits 2 EOBn max 104 EOBn range EOBnmin EOBnsize EOBn_code 1-8 0 3 Ox0 9-40 8 5 Ox1 41-104 40 6 0x2 EOBn follow on x3 Table 3: End of Band Run Table (EBRT) Fig. 5 shows a schematic flow diagram of a method 500 for encoding an EOBn.

The method 500 starts in step 502 where the Compressed Data Manager 201 determines whether the value of EOBn is equal to zero. If it is determined that EOBn is equal to zero no code is written to the scan data bitstream and the method 500 ends.

Alternatively, if it is determined in step 502 that the value of EOBn is nonzero then the appropriate Read_EOBn code (Oxf or 0x7), based on the scan partition number, from the FLCT is written in step 503 to the scan data bitstream using code_bits bits. This code indicates that, until otherwise indicated, the next encoded data in the scan data bitstream pertains to EOBn data. The Compressed Data Manager 201 then determines in 774780

O

c step 504 whether, based on the value of EOBn, a "follow on" code, EOBn_follow_on is 0 required to be written to the scan data bitstream. This is determined by determining whether EOBn is greater than EOBn_max. In the case where EOBn is greater than EOBn_max a code, EOBn_follow_on, is written to the scan data bitstream in step 507.

00 S5 The purpose of this follow-on code is twofold. Firstly it indicates an EOBn count of n EOBnmax. Secondly it indicates a further EOBn code follows in the bitstream.

(N

STherefore if the EOBn is greater than or equal to the predetermined maximum amount, EOBn_max (preferably 104), then an EOBn_follow_on code is written in step 507 to the bitstream using EOBn_bits bits and the value of EOBn is decremented by EOBn_max in step 508. The Compressed Data Manager 201 then returns execution to step 504 from where EOBn is further decremented by EOBn_max and an EOBn_follow_on code is written until EOBn is less than EOBn max.

If it is determined in step 504 that EOBn is not greater than EOBn_max then, in step 505, the EOBn is binned depending on the EOBn_range given in the EBRT. The appropriate code EOBn_symbol based on the binned (remaining) value of EOBn is then selected from column 4 of the EBRT and written in step 506 to the scan data bitstream.

The purpose of this code is also twofold. Firstly it indicates the number of bits (EOBn_size, column 3 of the EBRT) required to code the EOBn and secondly it indicates the range the EOBn falls into, and therefore the amount by which the coded EOBn has been reduced. The EOBn is then reduced in step 507 by EOBn_min (column 2 in the EBRT) so that the coded value of EOBn requires fewer bits than the raw value of EOBn.

For example, if EOBn 38 then the code Oxl is written to the bitstream. This code indicates the range which the EOBn falls into (9 40) and the number of bits required to code the reduced EOBn. Since 38 8 30, only 5 bits are required to code the EOBn.

774780 -21

\O

Finally, EOBn is written in step 508 to the scan data bitstream using EOBn_size bits. Note z that the actual written value is the binary representation of (EOBn to ensure EOBnsize bits are sufficient. The coded bitstream for the above example is therefore OxI OxID (01 1110O1).

Corresponding to each scan partition is a compressed image. For a given scan C' partition the corresponding compressed image is the image represented by the given scan partition and all previous scan partitions. Thus, corresponding to the sequence of scan partitions is a sequence of compressed images. For increasing sequence number the compressed image quality increases, while the compressed image size increases. The compression method in effect selects the largest compressed image (or highest quality compressed image) that fits into an available memory buffer. That is the next larger compressed image in the sequence after the selected compressed image does not fit in the buffer. There is some redundancy in the sense that the final compressed image will not, in general, totally fill the buffer. In order to minimise this redundancy it is desirable to have a sequence with fine granularity. That is the increase in size from one scan partition to the next is small. This suggests a lot of scan partitions. However the more scan partitions that are used the more complicated the encoding process, so there is a trade off.

There is another consideration in the design of the scan partition table that can be phrased in several different ways. One way is that each scan partition should maximise the increase in the compressed image quality for a given size increase (of compressed image).

A related way is that each scan partition should minimise the size increase for a given increase in compressed image quality. There are other ways that fall between the above mentioned two ways. The first way is used here for the purposes of discussion, but other ways are equally applicable.

774780 22-

\O

The aim of the scan partitions is therefore two-fold. One is that each should 0 C maximise the increase in quality for a given size increase. The other is that the size increase is not too large.

In order to achieve this aim in an efficient manner it is desirable to scan partition oO 05 the coefficients by magnitude (instead of by frequency alone) when designing the scan

NO

partition table. A magnitude scan partition is achieved in the preferred arrangement by

IND

coding different bit-planes in different scan partitions according to Table 1, but other magnitude scan partitions are possible. For example, in a scan partition the bits in bitplanes 2 and above are encoded for a set of coefficients. In a later scan partition (or scan partitions) the bits in bit-plane 1 are encoded for the same set of coefficients, and in a later scan partition (or scan partitions) the bits in bit-plane 0 are encoded for the same set of coefficients. Scan partitioning by frequency alone means the quality increase for a given scan partition is not always as large as it could be relative to the size increase. Further, when partitioning by frequency alone, it is difficult to achieve a sufficient number of scan partitions to reduce the redundancy referred to above, without compromising the compression efficiency, due to the nature of the JPEG coding method. In the preferred arrangement, the scan partitions as shown in the above mentioned Scan Partition Table are used.

Other perceptual scan partition separations are possible than those described above. For example, a different scan partition ordering whereby the scan partition 4 consisting of AC coefficients is placed after scan partition 11. For a more general example of different scan partitions, different selections of the Ss and Se boundaries, or a different interleaving of Ah and Al values for the different components and spectral segments could be used.

774780 N-23-

O

O

z Decompression Fig. 3 shows a schematic block diagram of an Image Decompressor 300, which complements the Image Compressor 200 shown in Fig. 2. The Image Decompressor 300 00 05 may also be implemented using the computer system 900 shown in Fig. 9. The Image Decompressor 300 consists of a Colour Interleave module 301, an DCT Decoder 303, a Scan INtput Manager 304, a Huffman Decoder 305, a Bit Unpacking module 306 and a Fixed Length Decoder 307.

The decompressor 300 takes the compressed image from the Compressed Data Manager 201 and reconstructs the image. The Compressed Data Manager 201 retrieves each compressed scan and provides scan data to the relevant decoder 305-307 according to the Scan Partition Table. The decoders 305-307 decode the scan data and pass the decoded data to the Scan Input Manager 304 which combines the scan data into 8 by 8 blocks of transform coefficients suitable for the DCT Decoder 303. When the bitstream decoding of a 8 by 8 block of data is complete the DCT Decoder 303 first reconstructs the DC coefficient using the DPCM and the previous DC coefficient, dequantises the block of transform coefficients and performs an inverse discrete cosine transform (IDCT) on the decoded block. Each DCT block is decoded from the compressed scans in tile raster order.

The Colour Interleave module 301 takes the output colour channel pixel values from the DCT Decoder 303 and interleaves each channel to the final image buffer to form pixel data 308. In the event where scans have been discarded by the Compressed Memory Manager 201 due to memory constraints the Compressed Memory Manager 201 instructs the decoders 305 307 to pad these scans with zeros.

774780 -24-

\O

In a DC Huffman decoder 305b of the Huffman decoder 305 the most significant 0 z bits of the DC coefficient difference (Scan Partition 1) are decoded using the standard decoding for JPEG DC coefficients. The DC coefficient is reconstructed by DPCM based on the DC coefficient of the previous decoded 8 by 8 block. In an AC Huffman decoder 00 05 305b of the Huffman decoder 305 the most significant bits of the AC coefficients (Scan Cc Partitions 2, 3, and 4) are decoded using the standard decoding for JPEG AC coefficients.

Prior to decoding the AC coefficients of a MCU an array that indicates the signs of the AC coefficients is initialised to zero. This 'signs array' is shared between the AC Huffman Decoder 305b and Fixed Length decoder 307. The purpose of the signs array is as follows. After a scan partition is processed, the corresponding values in the signs array are either set to 1 or depending on the sign of the corresponding coefficient, or remain at 0 if a non-zero bit has not yet been encountered for that coefficient. When a given signs array value is first set to 1 or a sign bit needs to be read from the current scan partition data bitstream.

The Compressed Data Manager 201 retrieves compressed scan data and provides encoded bitplane data to the decoders 305-307. Fig. 7 shows a schematic flow diagram of a method 700 used for reading encoded bitplane data by the Fixed Length Decoder 307.

Method 700 is carried out for each colour component of each scan partition for each MCU within each tile 100.

The value of EOBn has been initialised to zero for the tile 100. The Compressed Data Manager 201 determines in step 701 whether the value of EOBn is equal to zero. If the value of EOBn is not equal to zero then EOBn is decremented in step 705 by one and variable val is set to zero, before the Compressed Data Manager 201 proceeds to the next compressed scan data bitstream. A non-zero EOBn indicates to the Compressed Data 774780

O

C Manager 201 that the point transform values for that MCU within the scan partition are all zero.

If it is determined in step 701 that the value of EOBn is equal to zero the Compressed Data Manager 201 proceeds to read the fixed length code in step 702. The 0 0 5 size (code_bits) of this fixed length code is determined by the scan partition number and is determined using the FLCT above. The Compressed Data Manager 201 then, in step 703, Sdetermines whether the code read in step 702 equals Read_EOBn, which indicates the next value to be read is EOBn data, then the Compressed Data Manager 201 proceeds to step 704 where the EOBn specific code is read from the bitstream using EOBn_bits. Following step 704 the Compressed Data Manager 201 determines in step 707 whether the code is an EOBn follow on code. If it is determined that the code is EOBn follow on code then EOBn is incremented by EOBn_max in step 706 before processing returns to step 704.

The loop formed by steps 704, 706 and 707 continues until the EOBn code read indicates a range code (EOBn_symbol) rather than a follow on code.

When the code is no longer a follow on code processing continues to step 708.

Depending on the EOBn code read at step 704 the Compressed Data Manager 201 reads the required number of bits (EOBn_size) to obtain the reduced value of EOBn. This value, plus one, plus the appropriate value of EOBn_min from the EBRT is added to the intermediate total of EOBn to determine the final value for EOBn in step 708 before method 700 ends.

If it is determined in step 703 that the next value to be read is encoded bitplane data the Compressed Data Manager 201 proceeds to step 709 where the size of the encoded bitplane data is detennined. The size of the encoded bitplane data is then read and assigned to the variable val in step 710 before method 700 ends. The value of size is 774780 -26-

O

C dependent on both the scan number and the code that was read at step 702 and is z determined from the appropriate length code from the FLCT above.

The Fixed Length Decoder 307 (Fig. 3) decodes refinement bitplane data. Fig. 8 shows a schematic flow diagram of a method 800, used by the the Fixed Length Decoder 0 0 5 307, for decoding bitplane data. Method 800 is carried out for each MCU within each tile

NO

C for each colour channel of each scan partition where variable val, passed by the

(\N

0Compressed Data Manager 201, is nonzero.

The method 800 starts with an initialisation step 801 where: The index counter, k, is initialised to the start index for the scan being processed, the bit counter indicating the size of val, bitpos, is zeroed, a bitplane mask, p, is pre-calculated based on the Al value of the scan, and a mask, val_mask, is set to 0x01. The scan bitplane value, val, provided by the Compressed Data Manager 201 is then compared in step 802 with val_mask and the result stored in a boolean variable, t. The bitpos counter is then incremented and val_mask recalculated in step 803 to reflect the new bit position to next be considered in the scan bitplane value val.

Processing continues to step 805 where it is determined whether boolean variable t equals zero. If it is determined that boolean variable t is equal to zero 805 then the Fixed Length Decoder 307 proceeds to step 813. If it is determined that boolean variable t is equal to one (the only other alternative) then Fixed Length Decoder 307 proceeds to step 806 where the pre-calculated bitmask p is masked into the AC coefficient corresponding to the kth zig-zag index. It is in this fashion that the AC coefficients are reconstructed from data stored in each scan partition. The Fixed Length Decoder 307 then in step 808 considers the signs array. If the signs array corresponding to the kth zig-zag index is not equal to zero then the Fixed Length Decoder 307 proceeds to step 813. Alternatively if the 774780 -27-

NO

Ssigns array corresponding to the kth zig-zag index is equal to zero then this indicates the 0 z first nonzero bit of this AC coefficient has been reached; therefore the sign bit needs to be decoded from the scan bitplane value val. In step 807 the scan bitplane value val is compared with val_mask and the result stored in Boolean variable t. The bitpos counter is 00 then incremented and valmask recalculated in step 809.

NO

SFollowing step 809 the Fixed Length Decoder 307 then considers in step 811

(NO

whether the value of the boolean variable t equals zero. If the value of Boolean varaiable t is equal to zero then the sign of the AC coefficient is positive and the corresponding element in the signs array is set to 1 before processing continues to step 813.

Alternatively, if the value of Boolean variable t is equal to 1 (the only other alternative) then the sign of the AC coefficient is negative and the corresponding element in the signs array is set to -1 in step 810 before processing continues to step 813.

Step 813 determines if the index counter k has reached the end index for the scan.

If the index counter k is not equal to Se then the Fixed Length Decoder 307 proceeds to step 804 where the index counter k is incremented. The method 800 then returns to step 802. If it is determined in step 813 that the index counter k has reached the end index for the scan then the Fixed Length Encoder 204 returns to idle and awaits the next input scan.

The DCT Decoder 303 is responsible for performing an inverse discrete cosine transform on 8 by 8 blocks of transform coefficients to reconstruct image pixels. In this preferred arrangement both the reconstructed transform coefficients and the signs array generated by the decoder modules 305 307 are passed from the Scan Input Manager 304 to the DCT Decoder 303 where they are combined and transformed into colour channel pixel values.

Computer system 774780 28

\O

N, The Image Compressor 200 and the Image Decompressor 300 may be z implemented using the computer system 900 shown in Fig. 9. The computer system 900 is formed by a computer module 901, input devices such as a keyboard 902 and a pointer device 903, and output devices including a printer 915, and a display device 914.

O 5 The computer module 901 typically includes at least one processor unit 905, a

NO

Smemory unit 906 and a storage device 909. The module 901 also includes an number of input/output interfaces including a video interface 907 that couples to the video display 914, an 1O interface 913 for the keyboard 902 and pointing device 903, and an interface 908 for the printer 915.

The components 905, to 913 of the computer module 901 typically communicate via an interconnected bus 904 and in a manner which results in a conventional mode of operation of the computer system 900 known to those in the relevant art.

The Image Compressor 200 and Image Decompressor 300 are implemented as software executed within the computer system 900. The software is read and executed by the processor 905. The software may be recorded on a computer readable medium from where the software may be loaded into the computer system 900.

The Image Compressor 200 and Image Decompressor 300 may alternatively be implemented in dedicated hardware such as one or more integrated circuits.

The foregoing describes only some embodiments of the present invention, and modifications and/or changes can be made thereto without departing from the scope and spirit of the invention, the embodiments being illustrative and not restrictive.

In the context of this specification, the word "comprising" means "including principally but not necessarily solely" or "having" or "including", and not "consisting only 774780 29-

\O

of'. Variations of the word "comprising", such as "comprise" and "comprises" have 0 z correspondingly varied meanings.

0

IN

IND

774780

Claims (17)

1. A method of compressing an image, wherein the image comprises a plurality of pixels, said method comprising the steps of: O partitioning the image into a plurality of blocks of pixels; NO CC) transforming the blocks of pixels to produce respective blocks of transform IND coefficients; partitioning the blocks of transform coefficients into a plurality of partitions, said partitions having varying perceptual significance; encoding said partitions, wherein at least one high frequency partition is encoded using a fixed length encoder; and storing of the encoded partitions in memory, wherein during the storing of the encoded partitions, if it is determined that the memory is full, the encoded partition having least perceptual significance currently stored in the memory is discarded to release memory and the released memory is allocated to an encoded partition having more perceptual significance than said encoded partition having least perceptual significance.

2. A method as claimed in claim 1, wherein encoding using a fixed length encoder comprises the following sub-steps: determining a length code dependent on the length of said partition; encoding said length code using a number of bits dependent on a type of said partition; and encoding said partition using a number of bits dependent on said length code. 774780 -31 \O z

3. A method as claimed in claim 2, wherein said type of said partition is low frequency or high frequency. 00 5

4. A method as claimed in claim 2, wherein said length code is dependent on a range NO within which said length lies.

IND A method as claimed in claim 2, further comprising the sub-step, before said determining sub-step, of encoding an end of band run length, said end of band run length being equal to the number of all-zero-valued high frequency partitions encountered since the last said high frequency partition was encoded.

6. A method as claimed in claim 5, wherein said end of band run length is encoded by: determining a range within which said end of band run length lies; encoding said range using a predetermined number of bits; and encoding said end of band run length using a number of bits dependent on said range.

7. A method according to claim 6, wherein said end of band run length is encoded as a binary representation of said end of band run length minus a minimum value for said range.

8. A method according to claim 5, further comprising the steps, if said end of band run length is greater than a predetermined maximum value, of: 774780 -32- IO C outputting a predetermined symbol; and z subtracting said predetermined maximum value from said end of band run Slength. 0 0 5

9. A method according to claim 1, wherein said image is a colour image comprising a ¢Cc plurality of colour components and each said partition comprises data from all colour IND components of said block.

A method of encoding an integer, said method comprising the steps of: determining a range within which said integer lies; encoding said range using a predetermined number of bits; and encoding said integer using a number of bits dependent on said range.

11. A method according to claim 10, wherein said integer is encoded as a binary representation of said integer minus a minimum value for said range.

12. A method according to claim 10, further comprising the steps, if said integer is greater than a predetermined maximum value, of outputting a predetermined symbol; and subtracting said predetermined maximum value from said integer.

13. An image compressor for compressing an image, wherein the image comprises a plurality of pixels, said compressor comprising: means for partitioning the image into a plurality of blocks of pixels; 774780 33 \O Smeans for transforming the blocks of pixels to produce respective blocks of z transform coefficients; _means for partitioning the blocks of transform coefficients into a plurality of partitions, said partitions having varying perceptual significance; 00 5 means for encoding said partitions, wherein at least one high frequency NO Spartition is encoded using a fixed length encoder; and IND means for storing of the encoded partitions in memory, wherein during the storing of the encoded partitions, if it is determined that the memory is full, the encoded partition having least perceptual significance currently stored in the memory is discarded to release memory and the released memory is allocated to an encoded partition having more perceptual significance than said encoded partition having least perceptual significance.

14. Apparatus for encoding an integer, said method comprising the steps of: means for determining a range within which said integer lies; means for encoding said range using a predetermined number of bits; and means for encoding said integer using a number of bits dependent on said range.

A computer program product including a computer readable medium having recorded thereon a computer program for implementing any one of the methods according to claims 1 to 12.

16. A method substantially as described herein with reference to the accompanying drawings. 774780 -34- z

17. A method substantially as described herein with reference to the accompanying drawings. 0 5 DATED this 16th Day of November 2006 NO CANON KABUSHIKI KAISHA IND SPatent Attorneys for the Applicant SPRUSON&FERGUSON 774780