Encoding method and apparatus

• US 6,266,450 B1
• Filed: 09/29/1998
• Issued: 07/24/2001
• Est. Priority Date: 09/29/1997
• Status: Expired due to Term

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Patel, Hiren, Yip, Dominic, Elbourne, Trevor Robert
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Do, Anh Hong
• Application Number:
  US09/161,769
• Time in Patent Office: 1,029 Days
• Field of Search: 382/240, 382/238, 382/232, 709/225, 706/13
• US Class Current: 382/240
• 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/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/647 using significance based coding, e.g. Embedded Zerotrees of Wavelets [EZW] or Set Partitioning in Hierarchical Trees [SPIHT]

Abstract

An apparatus for the encoding of a series of wavelet coefficients of a predetermined size into a compact representation of the coefficients. The apparatus comprises a tree builder for constructing a tree form representation of the coefficients with leaf nodes representing coefficient values and internal nodes representing the number of bits needed to encode leaf nodes and child nodes of a current internal node. The tree builder stores the tree form representation in a tree buffer of the apparatus, and the tree buffer stores the tree form representation. A tree coder of the apparatus is interconnected to the tree buffer and adapted to read a current tree form representation and to output the encoding from the tree form representation. The tree buffer can include a component for storing at least two tree form representations and the tree builder can be adapted to form a first of the representations while the tree coder can be adapted to read a second of the tree form representations previously created by the tree builder.

Claims

1. An apparatus for encoding a block of coefficients to provide a coded representation of said coefficients, wherein said block of coefficients is partitioned into a plurality of groups of said coefficients, said apparatus comprising:

a tree building circuit for constructing a tree representation of said coefficients, wherein said tree representation comprises a plurality of internal nodes and a plurality of leaf nodes, the leaf nodes of a corresponding said internal node representing respective values of coefficients of a corresponding said group of coefficients, and each internal node having a number associated therewith representing the maximum number of a number indicating the number of digits required to represent the largest coefficient of the coefficients of any leaf nodes immediately descendant therefrom and said numbers associated with any internal nodes immediately descendant therefrom; and

a tree coding circuit for coding said constructed tree representation to produce a stream of data comprising said coded representation of said coefficients.

2. An apparatus as claimed in claim 1, wherein said apparatus further comprises:

a tree buffer interconnecting said tree building circuit and said tree coding circuit for storing said tree representation.

3. An apparatus as claimed in claim 2, wherein said tree buffer is adapted to store at least two tree representations and said tree building circuit is adapted to form a first of said two representations while said tree coding circuit is adapted to read a second of said two tree representations previously created by said tree building circuit.

4. An apparatus as claimed in claim 1, wherein said coefficients comprise wavelet coefficients.

5. A method of encoding a block of coefficients to provide a coded representation of said coefficients, wherein said block of coefficients is partitioned into a plurality of groups of said coefficients, said method comprising:

constructing a tree representation of said coefficients, wherein said tree representation comprises a plurality of internal nodes and a plurality of leaf nodes, the leaf nodes of a corresponding said internal node representing respective values of coefficients of a corresponding said group of coefficients, and each internal node having a number associated therewith representing the maximum number of a number indicating the number of digits required to represent the largest coefficient of the coefficients of any leaf nodes immediately descendant therefrom and said numbers associated with any internal nodes immediately descendant therefrom; and

coding said constructed tree representation to produce a stream of data comprising said coded representation of said coefficients.

6. A method as claimed in claim 5, wherein said construction step comprises constructing said tree in a depth first order from a deepest leaf node.

7. A method as claimed in claim 5, wherein said coding step comprises coding said tree representation in a breath first order to produce said data stream.

8. A method as claimed in claim 5, wherein said construction step comprises:

traversing in sequence said plurality of groups;

storing, for each group, the coefficient values of the group in respective said leaf nodes; and

determining, for each internal node, the maximum number of a number indicating the number of digits required to represent the largest coefficient of the coefficients of any leaf nodes immediately descendant therefrom and said numbers associated with any internal nodes immediately descendant therefrom and storing such maximum number in said internal node.

9. A computer program product including a computer readable medium having recorded thereon a computer program for encoding a block of coefficients to provide a coded representation of said coefficients, wherein said block of coefficients is partitioned into a plurality of groups of said coefficients, said computer program product comprising:

tree building means for constructing a tree representation of said coefficients, wherein said tree representation comprises a plurality of internal nodes and a plurality of leaf nodes, the leaf nodes of a corresponding said internal node representing respective values of coefficients of a corresponding said group of coefficients, and each internal node having a number associated therewith representing the maximum number of a number indicating the number of digits required to represent the largest coefficient of the coefficients of any leaf nodes immediately descendant therefrom and said numbers associated with any internal nodes immediately descendant therefrom; and

tree coding means for coding said constructed tree representation to produce a stream of data comprising said coded representation of said coefficients.

10. A computer program product as claimed in claim 9, wherein said tree building means comprises means for constructing said tree in a depth first order from a deepest leaf node.

11. A computer program product as claimed in claim 9, wherein said tree coding means comprises means for coding said tree representation in a breath first order to produce said data stream.

12. A computer program product as claimed in claim 9, wherein said tree building means comprises:

traversal means for traversing in sequence said plurality of groups;

means for storing, for each group, the coefficient values of the group in respective said leaf nodes; and

means for determining, for each internal node, the maximum number of a number indicating the number of digits required to represent the largest coefficient of the coefficients of any leaf nodes immediately descendant therefrom and said numbers associated with any internal nodes immediately descendant therefrom and storing such maximum number in said internal node.

13. An apparatus for the creation of an encoded bit stream from a block of coefficients, wherein said block of coefficients is partitioned into a plurality of groups of said coefficients, the apparatus comprising:

bit plane splitting means for splitting said block of coefficients as a plurality of bitplanes;

a plurality of bit data validity units connected to one another and connected to said bit plane splitting means for receiving and processing respective said bitplanes, wherein each said bit data validity unit outputs signals indicating whether or not respective portions of its received bitplane corresponding to respective said groups of coefficients comprise coefficients having a significant bit greater than or equal to its received bitplane; and

a packing logic circuit adapted to pack said coefficients into a contiguous bit stream utilizing said outputs of said bit data validity units.

14. An apparatus as claimed in claim 13, wherein said coefficients comprise a wavelet decomposition of data and said groups include sub-bands of said wavelet decomposition.

15. An apparatus as claimed in claim 13, wherein said packing logic circuit further comprises:

packing circuits for packing respective said groups of coefficients into packed groups;

a start address extraction circuit for extracting a start address within each of said groups; and

a combiner circuit interconnected to said packing circuits and said start address extraction circuit and adapted to pack said packed groups into said continuous bit stream.

16. A method for the creation of an encoded bit stream from a block of coefficients, wherein said block of coefficients comprises a plurality of groups of said coefficients, the method comprising the steps of:

inputting said block of coefficients;

splitting said block of coefficients into a predetermined number of bitplanes;

outputting signals, for each said bitplane, indicating whether or not respective portions of the bitplane corresponding to respective said groups of coefficients comprise coefficients having a significant bit greater than or equal to the bitplane; and

packing said block of coefficients into an encoded bit stream using said bitplanes and said output signals.

17. A method as claimed in claim 16, wherein said coefficients comprise a wavelet decomposition of data and said groups include sub-bands of said wavelet decomposition.

18. A method as claimed in claim 16, wherein said packing step further comprises:

packing said groups into packed groups;

extracting a start address within each of said groups; and

combining said packed groups to produce said encoded bit stream.

19. A computer program product including a computer readable medium having recorded thereon a computer program for the creation of an encoded bit stream from a block of coefficients, wherein said block of coefficients comprises a plurality of groups of said coefficients, the computer program product comprising:

input means for inputting said block of coefficients;

splitting means for splitting said block of coefficients into a predetermined number of bitplanes;

output means for outputting signals, for each said bitplane, indicating whether or not respective portions of the bitplane corresponding to respective said groups of coefficients comprise coefficients having a significant bit greater than or equal to the bitplane; and

packing means for packing said block of coefficients into an encoded bit stream using said bitplanes and said output signals.

20. A computer program product as claimed in claim 19, wherein said coefficients comprise a wavelet decomposition of data and said groups include sub-bands of said wavelet decomposition.

21. A computer program product as claimed in claim 19, wherein said packing means comprises:

packing means for packing said groups into packed groups;

extraction means for extracting a start address within each of said groups; and

combination means for combining said packed groups to produce said encoded bit stream.

22. A method for the creation of an encoded bit stream from a block of coefficients, each of said coefficients being represented by a predetermined number of bits, said method comprising the steps of:

inputting said coefficients, a bit plane at a time;

determining from said bit planes a most significant bit of each of said coefficients;

storing those portions of said coefficients which are less than the most significant bit; and

utilizing said most significant bit determination and said portions of said coefficients to encode a decodable interleaved compact form of said coefficient stream comprising an interleaved coefficient magnitude portion stream and a coefficient portion stream.

23. An apparatus for encoding a block of coefficients, the apparatus comprising:

input means for simultaneously inputting said block of coefficients, one bit plane at a time;

a bit plane magnitude determination circuit connected to said input means for determining and storing a most significant bit of each of said coefficients;

a coefficient storage connected to said input means for storing the lesser significant coefficients of said coefficients; and

a pixel packer circuit connected to said bit plane magnitude determination circuit and said coefficient storage and adapted to read values and to produce a decodable interleaved compact form of said coefficient stream comprising an interleaved coefficient magnitude portion stream and a coefficient portion stream.

24. A computer program product including a computer readable medium having recorded thereon a computer program for encoding a block of coefficients, each of said coefficients being represented by a predetermined number of bits, said computer program product comprising:

input means for inputting said coefficients, a bit plane at a time;

determination means for determining from said bit planes a most significant bit of each of said coefficients;

storage means for storing those portions of said coefficients which are less than the most significant bit; and

encoding means utilizing said most significant bit determination and said portions of said coefficients to encode a decodable interleaved compact form of said coefficient stream comprising an interleaved coefficient magnitude portion stream and a coefficient portion stream.