Method and apparatus for compressing image data using a tree structure

• US 10,051,288 B2
• Filed: 10/06/2015
• Issued: 08/14/2018
• 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): Noh, Jae N
• Application Number:
  US14/876,067
• Publication Number:
  US 20160100195A1
• Time in Patent Office: 1,043 Days
• Field of Search: 37524019
• 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 data encoding using trees formed with logic gates are described which lead to spatial compression of image data. Data encoding is achieved using a five-level wavelet transform, such as the Haar or the 2/10 transform. A dual transform engine is used, the first and engine being used for the first part of the first-level transform, the second part of the first-level transform and the subsequent-level transforms being performed by the second transform engine within a time interval which is less than or equal to the time taken by the first transform engine to effect the part-transform. Each bit plane of the resulting coefficients is then encoded by forming a tree structure from the bits and OR logical combinations thereof. Redundant data are removed from the resulting tree structure, and further data can be removed by using a predetermined compression profile. The resulting blocks of compressed data are of variable length and are packaged with sync words and index words for transmission so that the location and identity of the transformed data blocks can be determined from the received signal.

Claims

1. A method of encoding an input set of data bits by a codec comprising hardware, the method comprising:

arranging said input set of data bits into a plurality of first groups of data bits, wherein said input set of data bits comprises a two-dimensional array of data bits;

dividing each of said first groups of data bits into a plurality of first subgroups of data bits;

logically combining said data bits within each of said first subgroups of data bits using a first logical operation to generate a first output data bit for each said first subgroup of data bits;

logically combining said first output data bits for said first subgroups of data bits of each of said first groups of data bits using a second logical operation to generate a second output data bit for each of said first groups of data bits, by forming a plurality of second subgroups of said second output data bits and logically combining said second subgroups of said second output data bits;

logically combining said second output data bits for said first groups of data bits to generate a final output data bit for said input set of data bits;

generating an encoded output set of data bits for said input set of data bits, said encoded output set of data bits comprising said final output data bit and, if said final output data bit is not equal to a first predetermined value, said encoded output set of data bits further comprising one or more of said output data bits and one or more of said data bits of said input set of data bits, in dependence on at least a first exclusion condition that if a given output data bit is equal to a second predetermined value, then said data bits and said output data bits used to generate said given output data bit are excluded from said encoded output set of data bits,

wherein said two-dimensional array of data bits comprises a bit plane of a block of image data that has been transformed using a multi-level wavelet transform and said second output data bits are grouped to form said second subgroups of said second output bits according to levels of said multi-level transform to which they relate.

2. The method of claim 1 wherein each of said first groups of data bits comprises a one-dimensional set of data bits.

3. The method of claim 1 wherein said first logical operation comprises a logical “

OR”

operation.

4. The method of claim 1 wherein said first logical operation comprises a logical “

AND”

operation.

5. The method of claim 3 wherein said second logical operation comprises a logical “

OR”

operation.

6. The method of claim 1 wherein said first predetermined value is zero.

7. The method of claim 1 wherein said second predetermined value is the same as said first predetermined value.

8. The method of claim 2 wherein each of said first groups of data bits comprises data bits from a plurality of rows of said two-dimensional array of data bits.

9. The method of claim 1 wherein said second subgroups of said second output data bits comprise second subgroups each comprising five of said second output data bits.

10. The method of claim 1 wherein said second output data bits comprise first ungrouped second output data bits that are not grouped into any of said second subgroups of said second output data bits.

11. The method of claim 10 wherein logically combining said second output data bits comprises logically combining each of said second subgroups of said second output data bits using a third logical operation to generate a third output data bit for each of said second subgroups of said second output data bits.

12. The method of claim 11 wherein logically combining said second output data bits comprises forming a plurality of third subgroups from said third output data bits and said first ungrouped second output data bits.

13. The method of claim 12 wherein said second output data bits comprise second ungrouped second output data bits that are not grouped into any of said second or third subgroups of said second output data bits.

14. The method of claim 13 wherein logically combining said second output data bits comprises logically combining each of said third subgroups of said second output data bits using a fourth logical operation to generate a fourth output data bit for each of said third subgroups of said second output data bits.

15. The method of claim 11 wherein said third logical operation is a logical “

OR”

operation.

16. The method of claim 14 wherein said fourth logical operation is a logical “

OR”

operation.