Method for image data processing utilizing multiple transform engines

• US 9,204,170 B2
• Filed: 08/11/2006
• Issued: 12/01/2015
• Est. Priority Date: 08/26/2005
• Status: Active Grant

• Current Assignee: RGB Systems Incorporated
• Original Assignee: RGB Systems Incorporated
• Inventors: Smith, Peter Lionel
• Primary Examiner(s): Vaughn, Jr., William C
• Assistant Examiner(s): Hess, Michael J
• Application Number:
  US11/991,027
• Publication Number:
  US 20100014590A1
• Time in Patent Office: 3,399 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04N 19/107 between spatial and temporal predictive coding, e.g. picture refresh
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/132 Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
• CPC Class Codes: H04N 19/17 the unit being an image region, e.g. an object
• CPC Class Codes: H04N 19/174 the region being a slice, e.g. a line of blocks or a group of blocks
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/182 the unit being a pixel
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/1883 the unit relating to sub-band structure, e.g. hierarchical level, directional tree, e.g. low-high [LH], high-low [HL], high-high [HH]
• CPC Class Codes: H04N 19/33 in the spatial domain
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/423 characterised by memory arrangements H04N19/433 takes precedence
• CPC Class Codes: H04N 19/507 using conditional replenishment
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/635 characterised by filter definition or implementation details
• CPC Class Codes: H04N 19/645 by grouping of coefficients into blocks after the transform
• CPC Class Codes: H04N 19/647 using significance based coding, e.g. Embedded Zerotrees of Wavelets [EZW] or Set Partitioning in Hierarchical Trees [SPIHT]
• CPC Class Codes: H04N 19/66 involving data partitioning, i.e. separation of data into packets or partitions according to importance
• CPC Class Codes: H04N 19/68 : involving the insertion of resynchronisation markers into the bitstream
• CPC Class Codes: H04N 19/70 : characterised by syntax aspects related to video coding, e.g. related to compression standards
• CPC Class Codes: H04N 19/86 : involving reduction of coding artifacts, e.g. of blockiness
• CPC Class Codes: H04N 19/89 : involving methods or arrangements for detection of transmission errors at the decoder
• CPC Class Codes: H04N 19/91 : Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
• CPC Class Codes: H04N 19/96 : Tree coding, e.g. quad-tree coding

Abstract

Methods of spatial compression of image data using trees formed with logic gates are described. Data encoding is achieved using a five-level wavelet transform, such as the Haar or 2/10 transforms. A dual transform engine is used, the first engine being used for the first transform, and the subsequent transforms being performed by the second engine. Each bit plane of the resulting coefficients is then encoded by forming a tree structure from the bits and logical OR combinations thereof. Redundant data are removed. Further data can be removed with a predetermined compression profile. The resulting blocks of compressed data are of variable length and are packaged with sync and index words for transmission so that the location and identity of the transformed data blocks can be determined.

Claims

1. A method of transforming a video stream comprising a sequence of images, each image comprising pixels arranged in a first two-dimensional array, said first two-dimensional array comprising a first dimension and a second dimension, said method transforming said sequence of images into a corresponding sequence of sets of multi-level transformed wavelet coefficients, each of said sets of multi-level transformed wavelet coefficients arranged in a second two-dimensional array comprising said first and second dimensions, said transforming performed using asymmetric parallel processing implemented by an encoding system comprising first and second transform engines, a shared memory, and a controller, each of said transform engines configured to receive pairs of input data values and transform each of said pairs of input data values into a pair of output data values, each of said pair of output data values comprising a smooth output data value obtained by applying a first filter to said pair of input data values and a detail output data value obtained by applying a second filter to said pair of input data values, said method comprising the steps of:

said first transform engine receiving as first pairs of input data values pairs of pixel values from a first image from said video stream each of said first pairs of input data values comprising a first pixel value of a first pixel and a second pixel value of a second pixel immediately adjacent to said first pixel along said first dimension of said first two-dimensional array;

said first transform engine applying said first and second filters to said first pairs of input data values, thereby transforming said first pairs of input data values into first pairs of output data values, said first pairs of output data values comprising first level one once transformed wavelet coefficients;

said controller storing said first level one once transformed wavelet coefficients as a third two-dimensional array comprising said first and second dimensions in a first memory storage area of said shared memory;

said controller providing said first level one once transformed wavelet coefficients from said first memory storage area to said second transform engine as second pairs of input data values, each of said second pairs of input data values comprising a first first level one once transformed wavelet coefficient from said third two-dimensional array and a second first level one once transformed wavelet coefficient immediately adjacent to said first first level one once transformed wavelet coefficient along said second dimension of said third two-dimensional array;

said second transform engine applying said first and second filters to said second pairs of input data values, thereby transforming said second pairs of input data values into second pairs of output data values, said second pairs of output data values comprising first level one twice transformed wavelet coefficients;

said controller storing said first level one twice transformed wavelet coefficients in said third two-dimensional array by overwriting said first level one once transformed wavelet coefficients;

said controller providing a first portion of said first level one twice transformed wavelet coefficients from said third two-dimensional array to said second transform engine as third pairs of input data values, each of said third pairs of input data values comprising a first first level one twice transformed wavelet coefficient from said third two-dimensional array and a second first level one twice transformed wavelet coefficient immediately adjacent to said first first level one twice transformed wavelet coefficient along said first dimension of said third two-dimensional array;

said second transform engine applying said first and second filters to said third pairs of input data values, thereby transforming said third pairs of input data values into third pairs of output data values, said third pairs of output data values comprising first level one three-times transformed wavelet coefficients;

said controller storing said first level one three-times transformed wavelet coefficients in said third two-dimensional array by overwriting said first portion of said first level one twice transformed wavelet coefficients;

said first transform engine receiving as fourth pairs of input data values pairs of pixel values from a second image from said video stream, each of said fourth pairs of input values comprising a third pixel value of a third pixel and a fourth pixel value of a fourth pixel immediately adjacent to said third pixel along said first dimension of said first two-dimensional array;

said first transform engine applying said first and second filters to said fourth pairs of input data values, thereby transforming said fourth pairs of input data values into fourth pairs of output data values, said fourth pairs of output data values comprising second level one once transformed wavelet coefficients;

said controller providing first additional pairs of input data values to said second transform engine, said first additional pairs of input data values comprising pairs of immediately adjacent wavelet coefficients from portions of said third two dimensional array;

said second transform engine performing a plurality of higher level transformations on said first additional pairs of input data values by applying said first and second filters to said first additional pairs of input data values to generate a first of said sets of multi-level transformed wavelet coefficients stored in said first memory storage area;

said controller storing said second level one once transformed wavelet coefficients as a fourth two-dimensional array comprising said first and second dimensions in a second memory storage area of said shared memory.

2. A method as claimed in claim 1, wherein said first dimension is a horizontal dimension.

3. A method as claimed in claim 1, further comprising the steps of:

said controller providing said second level one once transformed wavelet coefficients from said second memory storage area to said second transform engine as fifth pairs of input data values, each of said fifth pairs of input data values comprising a first second level one once transformed wavelet coefficient from said fourth two-dimensional array and a second second level one once transformed wavelet coefficient immediately adjacent to said first second level one once transformed wavelet coefficient along said second dimension of said fourth two-dimensional array;

said second transform engine applying said first and second filters to said fifth pairs of input data values, thereby transforming said fifth pairs of input data values into fifth pairs of output data values, said fifth pairs of output data values comprising second level one twice transformed wavelet coefficients;

said controller storing said second level one twice transformed wavelet coefficients in said fourth two-dimensional array by overwriting said second level one once transformed wavelet coefficients;

said controller providing second additional pairs of input data values to said second transform engine, said second additional pairs of input data values comprising pairs of immediately adjacent wavelet coefficients from portions of said fourth two dimensional array;

said second transform engine performing a plurality of higher level transformations on said second additional pairs of input data values by applying said first and second filters to said second additional pairs of input data values to generate a second of said sets of multi-level transformed wavelet coefficients stored in said second memory storage area.

4. A method as claimed in claim 3, applied to a plurality of further images from said video stream, comprising said controller storing each set of multi-level transformed wavelet coefficients resulting from transforming each further odd-numbered image in said first memory storage area, and said controller storing each set of multi-level transformed wavelet coefficients resulting from transforming each further even-numbered image in said second memory storage area.

5. A method as claimed in claim 4, wherein said sets of multi-level transformed wavelet coefficients are stored by said controller in their respective memory storage area so as to overwrite at least some portion of the wavelet coefficients already stored therein.

6. A method as claimed in claim 1, wherein said step of said first transform engine applying said first and second filters to said fourth pairs of input data values commences before the completion of said step of said controller providing said first level one once-transformed wavelet coefficients from said first memory storage area to said second transform engine.

7. A method as claimed in claim 3, wherein said steps performed on said first and second images are performed on a plurality of subsequent images from said video stream, wherein said steps performed on said first image are applied to odd-numbered images and said steps performed on said second image are applied to even-numbered images.

8. A method as claimed in claim 1 wherein said first filter implements the function:

s(n)=└

(x(2n)+x(2n+1))/2┘

wherein x(2n) and x(2n+1) comprise said input data values and s(n) comprises said smooth output data value.

9. A method as claimed in claim 8 wherein said second filter implements the function:

d(i)=x(2n)−

x(2n+1)+p(n)

wherein x(2n) and x(2n+1) comprise said input data values, p(n) comprises a predictor data value, and d(n) comprises said detail output data value.

10. A method as claimed in claim 9 wherein said predictor data value is zero.