Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
1999-03-19
2004-10-12
Dastouri, Mehrdad (Department: 2623)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S250000
Reexamination Certificate
active
06804402
ABSTRACT:
FIELD OF INVENTION
The present invention relates to a method and apparatus for encoding and decoding digital images including transcoding to and from other compression formats. The present invention is not limited to still image technologies and may also be used in video image technologies.
BACKGROUND OF INVENTION
In the current baseline JPEG standard it is necessary to substantially decode all the transform coefficients of an 8×8 block before the next 8×8 block can be decoded. Thus the time required to decode any lower resolution version of the image is bound by the time to decode all the coefficients. This time actually significantly constrains the decoding time, especially for the smallest resolutions.
The JPEG standard also provides for redundant hierarchical encoding. The image is encoded at multiple resolutions so that lower resolution versions may be accessed without first having to decompress the image at its full resolution. However this results in large compression files which contain more information than is desirable.
The JPEG standard also provides for non redundant hierarchical encoding such as spectral selection. However these methods are inefficient in the coding of the image
SUMMARY OF INVENTION
It is an object of the invention to ameliorate one or more of the above mentioned disadvantages of the prior art.
According to a first aspect of the invention, there is provided an image encoding method comprising the steps of: (a) dividing an image into a plurality of blocks which are composed of (A×B) pixels, A and B being an integer two or more;(b) converting pixels into coefficients in plural frequency regions in the block basis; (c) combining the coefficients of the same frequency region in different blocks to obtain a group of coefficients; and (d) encoding the group of coefficients by the group.
According to a second aspect of the invention, there is provided a method of representing a digital image to provide a coded representation, said method comprising the steps of: (a) dividing said digital image into a plurality of blocks of pixels; (b) transforming each block of pixels into a block of transform coefficients, where each transform coefficient is represented by a predefined bit sequence; (c) rearranging the transform coefficients into a plurality of groups each having one or more subgroups of transform coefficients, wherein said transform coefficients of the same spatial frequency region are grouped together in the same group; (d) selecting in turn each subgroup as a region and setting a predetermined maximum bit plane as the current bit plane; (e) scanning the significance of each bitplane of said selected region from said current bitplane towards a predetermined minimum bitplane, and providing a first token for each insignificant bitplane and a second token for a significant bitplane in said coded representation until a significant bitplane is determined and setting said determined significant bitplane as the current bitplane; (f) partitioning said selected region into two or more subregions having a predetermined form, and setting each of said subregions as said selected region; and (g) repeating steps (e) and (f) for each selected region in turn, commencing from said current bit plane until the predetermined minimum bitplane has been reached, or said selected region has a predetermined size, and coding said transform coefficients of said selected region and providing said coded transform coefficients in said coded representation.
According to a third aspect of the invention, there is provided a method of encoding an image. The method includes the step of dividing the image into a plurality of blocks of pixels. The method also includes the step of transforming the blocks of pixels into respective blocks of transform coefficients, wherein each block of transform coefficients comprises a plurality of subgroups of transform coefficients. The subgroups of each block are associated with respective spatial frequency regions of the block and are capable of being hierarchically inverse transformed to reproduce a number of resolutions of a sub-image of the image. The method further includes the step of rearranging all the subgroups of transform coefficients from all the blocks into groups of transform coefficients, wherein each group comprises those subgroups associated with the same spatial frequency regions from all the blocks of transform coefficients. The method further includes the step of encoding the groups in turn beginning with a first group and continuing in sequence through to a last group, wherein each group is encoded such that a decoder is capable of decoding each group substantially independently of any other group.
According to a fourth aspect of the invention, there is provided a method for decoding a coded representation of a digital image, the coded representation comprising in turn a plurality of encoded groups of transform coefficients, commencing with a first group and continuing in sequence through to a last group. Each encoded group comprises subgroups of transform coefficients associated with the same spatial frequency regions from respective blocks of transform coefficients. The method includes the step of selecting a resolution mode. The method also includes the step of decoding the encoded groups in turn beginning with the first encoded group and continuing in sequence until a number of encoded groups have been decoded, wherein the number is an integer and is determined in response to the resolution mode. The method further includes the step of rearranging all of the transform coefficients of the decoded groups into a plurality of m×m complete blocks of the transform coefficients, where m is an integer and is dependent on the selected resolution mode. The method further includes the step of inverse transforming each of the m×m blocks of transform coefficients, if necessary, to derive a block of pixels. Also included is the step of combining the blocks of pixels to reconstitute the image at the selected resolution.
According to a fifth aspect of the invention, there is provided a method for decoding a coded representation of a digital image, said image comprises a plurality of blocks of pixels having associated therewith blocks of transform coefficients which have been rearranged into a plurality of groups each comprising one or more subgroups of transform coefficients, said method comprising the steps of: (a) selecting a resolution mode; (b) decoding the groups in turn beginning with a first group and continuing in sequence until a number of groups have been decoded, wherein said number is determined in response to said resolution mode; and wherein said decoding step comprises the following sub-steps (b)(i) selecting in turn each said subgroup of the groups to be decoded as a region; (b)(ii) scanning said coded representation associated with said selected region, said coded representation comprising a first token for each insignificant bitplane of said coefficients, a second token for each significant bitplane of said coefficients, and zero or more coded coefficients; (b)(iii) if a first token is determined, providing an insignificant bitplane in an output stream for a current bitplane of coefficients of said selected region; (b)(iv) if a second token is determined, providing a significant bitplane in said output stream for said current bitplane of said coefficients of said selected region and partitioning said selected region into two or more subregions having a predetermined form, and setting each of said subregions as said selected region; and (b)(v) repeating steps (b)(ii) to (b)(iv) commencing from a predetermined bitplane until a predetermined minimum bit plane has been reached, or until said selected region has a predetermined size wherein a coded transform coefficient of said selected region is decoded; and (b)(vi) providing said selected subgroups of decoded transform coefficients as an output; (c) rearranging all of the decoded transform coefficients of said selected subgroups into a plurality of
LandOfFree
Method and apparatus for hierarchically encoding and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for hierarchically encoding and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for hierarchically encoding and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3320145