Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
1998-09-29
2001-07-24
Couso, Jose L. (Department: 2724)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S232000, C706S013000
Reexamination Certificate
active
06266450
ABSTRACT:
FIELD OF INVENTION
The present invention relates to the field of data compression and in particular, discloses an architecture for encoding coefficients that, have been constructed as a result of a compression process.
BACKGROUND OF THE INVENTION
The field of digital data compression and in particular digital image compression has attracted great interest for some time.
In the field of digital image compression, many different techniques have been utilised. In particular, one popular technique is the JPEG standard which utilises the discrete cosine transform to transform standard size blocks of an image into corresponding cosine components. In this respect, the higher frequency cosine components are heavily quantised so as to assist in obtaining substantial compression factors. The heavy quantisation is an example of a “lossy” technique of image compression. The JPEG standard also provides for the subsequent loss less compression of the transformed coefficients.
Recently, the field of wavelet transforms has gained great attention as an alternative form of data compression. The wavelet transform has been found to be highly suitable in representing data having discontinuities such as sharp edges. Such discontinuities are often present in image data or the like.
Although the preferred embodiments of the present invention will be described with reference to the compression of image data, it will be readily evident that the preferred embodiment is not limited thereto. For examples of the many different applications of Wavelet analysis to signals, reference is made to a survey article entitled “Wavelet Analysis” by Bruce et. al. appearing in IEEE Spectrum, October 1996 page 26-35. For a discussion of the different applications of wavelets in computer graphics, reference is made to “Wavelets for Computer Graphics”, I. Stollinitz et. al. published 1996 by Morgan Kaufmann Publishers, Inc.
It would be desirable to provide an hardware embodiment of an encoder and method so as to provide for efficient and effective encoding of a series of wavelet coefficients in order to substantially increase the speed of encoding.
SUMMARY OF INVENTION
It is an object of the present invention to ameliorate one or more disadvantages of the prior art.
According to one aspect of the invention there is provided an apparatus for encoding a series of coefficients of a predetermined size into a compact representation of said coefficients, said apparatus including:
tree building means for constructing a tree representation of said 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;
tree coding means for coding said constructed tree representation to produce a stream of data including said compact representation of said coefficients.
According to another aspect of the invention there is provided a method of encoding of a series of coefficients of a predetermined size into a compact representation of said coefficients, said method including:
constructing a tree representation of said 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;
coding said constructed tree representation to produce a stream of data including said compact representation of said coefficients.
According to still another aspect of the invention there is provided a computer program product including a computer readable medium having recorded thereon a computer program for encoding of a series of coefficients of a predetermined size into a compact representation of said coefficients, said computer program product including:
tree building means for constructing a tree representation of said 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;
tree coding means for coding said constructed tree representation to produce a stream of data including said compact representation of said coefficients.
According to another aspect of the invention there is provided an apparatus for the creation of an encoded bit stream from a series of coefficients including:
bit plane input means for inputting said series of coefficients;
a plurality of bit data validity units interconnected to said bit plane input means and to one another and adapted to filter said coefficient data into a predetermined number of groups and to further filter coefficients within each group into leading zero portions and non leading zero portions and to output said bit data in bit plane by bit plane portions and to further output signals indicative of said groupings;
packing logic means adapted to pack said encoded bit stream into a contiguous stream from said outputs of said bit data validity units.
According to still another aspect of the invention there is provided a method for the creation of an encoded bit stream from a series of coefficients, the method including the steps of:
inputting said series of coefficients;
grouping said coefficient data into a predetermined number of bitplanes;
grouping said coefficients within each group into leading zero portions and non leading portions;
outputting said series of coefficients in groups of bitplanes;
outputting data valid bits indicative of said groupings of said coefficents within each group; and
packing said series of coefficients using said data valid bits to produce said encoded bit stream.
According to another aspect of the invention there is provided 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 series of coefficients, the computer program product including:
input means for inputting said series of coefficients;
first group means for grouping said coefficient data into a predetermined number of bitplanes;
second group means for grouping said coefficients within each group into leading zero portions and non leading portions;
output means for outputting said series of coefficients in groups of bitplanes; output means for outputting data valid bits indicative of said groupings of said coefficents within each group; and
packing means for packing said series of coefficients using the output data valid bits to produce said encoded bit stream.
According to still another aspect of the invention there is provided a method for the creation of an encoded bit stream from a series of coefficients, the including a coefficient stream, each of said coefficients being represented by a predetermined number of bits, said method including the steps of:
inputting said coefficients, a bit plane at a time;
determining from said bit plane a most significant bit of each of said coefficients;
storing those portions of said coefficients which are less than the most significant bit;
utilizing said most significant bit determination and said portions of said coefficients to encode a decodable interleaved compact form of said coefficient stream. including an interleaved coefficient magnitude portion stream and a coefficient portion stream.
According to still another aspect of the invention there is provided an apparatus for encoding a series of coefficients including:
input means for simultaneously inputting said series of coefficients, one bit plane at a time;
bit plane magnitude determination means interconnected to said input means for determining and storing a most significant bit of each of said coefficients;
coefficient storage means interconnected to said input means for storing the lesser significant coefficients of said coefficients;
pixel packer means interconnected to said bit plane magnitude determination means and said coefficient storage means and adapted to read values and to produce a decodable interleaved compact form of said coefficient stream including an interleaved coefficient magnitude portion stream and a coefficient portion stream.
According to
Elbourne Trevor Robert
Patel Hiren
Yip Dominic
Canon Kabushiki Kaisha
Couso Jose L.
Do Anh Hong
Fitzpatrick ,Cella, Harper & Scinto
LandOfFree
Encoding method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Encoding method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Encoding method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2568026