Adaptive transform coding using variable block size

• US 5,241,395 A
• Filed: 03/23/1992
• Issued: 08/31/1993
• Est. Priority Date: 08/07/1989
• Status: Expired due to Term

• Current Assignee: TTI Inventions C LLC (Intellectual Ventures LLC)
• Original Assignee: Bell Communications Research, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Chen, Cheng-Tie
• Primary Examiner(s): Coles, Sr., Edward L.
• Assistant Examiner(s): LEE, TOMMY D
• Application Number:
  US07/859,614
• Time in Patent Office: 526 Days
• Field of Search: 358/426, 358/261.1, 358/261.2, 358/261.3, 358/261.4, 358/430, 358/432, 358/433, 358/464, 358/465, 358/466, 382/56
• US Class Current: 358/426.14
• CPC Class Codes: H04N 19/119 Adaptive subdivision aspects, e.g. subdivision of a picture into rectangular or non-rectangular coding blocks
• CPC Class Codes: H04N 19/154 Measured or subjectively estimated visual quality after decoding, e.g. measurement of distortion use of rate-distortion criteria H04N19/147
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/85 using pre-processing or post-processing specially adapted for video compression
• CPC Class Codes: H04N 19/96 Tree coding, e.g. quad-tree coding

Abstract

An adaptive transform coding algorithm for a still image utilizes a quadtree based variable block size discrete cosine transform to achieve a better tradeoff between bit rate and image quality. The choice of appropriate block size is made according to a mean based decision rule which can discriminate various image contents for better visual quality.

Claims

1. A method for processing a signal corresponding to a still image so that said still image can be transmitted to a remote location via a channel, said method comprising the steps of

providing a signal comprising a two-dimensional array of pixels which is representative of a still image,

dividing said signal into blocks of pixels of size M×

M, each of said M×

M blocks of pixels having a content,

splitting each of said M×

M blocks to produce a hierarchy of sub-blocks including the levels designated i-0,1,2, . . . ,K-1, so that at each level of the hierarchy, there are 4i sub-blocks of size M/2ⁱ ×

M/2ⁱ, i=0,1, . . . ,K-1, where K is an integer,

starting with the K-1 level in said hierarchy and proceeding to successive levels in said hierarchy, merging adjacent of said sub-blocks when the differences in the mean pixel value of said sub-blocks is below a predetermined threshold,

applying an orthogonal transform individually to each of said sub-blocks comprising said M×

M blocks of pixels to form transform coefficients for each of said sub-blocks,

utilizing an encoder to convert the transform coefficients for each sub-block into a signal in the form of a stream of bits, and

transmitting said signal in the form of a stream of bits for each of said sub-blocks via a channel to a receiver at a remote location.

2. The method of claim 1 wherein said orthogonal transform is a discrete cosine transform.

3. The method of claim 2 wherein sub-blocks of different sizes are coded using different codes.

4. The method of claim 1 wherein said method further comprises the steps of compressing the transform coefficients resulting from the application of an orthogonal transform to each sub-block of pixels and coding the compressed transform coefficients.

5. The method of claim 4 wherein said compressing step comprises thresholding said transform coefficients with a threshold value T and quantizing said transform coefficients with a quantization step size Q.

6. The method of claim 5 wherein said quantization step size Q is chosen individually for each different sub-block size.

7. The method of claim 5 wherein said threshold value T is chosen individually for each different sub-block size.

8. The method of claim 1 wherein said transmitting step comprises transmitting the stream of bits for each sub-block to a channel coder for transmission to said remote location.

9. A method for processing a signal corresponding to a still image so that said still image can be transmitted to a remote location via a channel, said method comprising the steps of

providing a signal comprising a two-dimensional array of pixels which is representative of a still image,

dividing said signal into blocks of pixels of size M×

M, each of said M×

M blocks of pixels having a content,

depending on the content of each of said M×

M blocks of pixels, selectively decomposing each of said M×

M blocks of pixels into one or more sub-blocks of pixels, each of said sub-blocks being of a size given by M/2ⁱ ×

M/2ⁱ, where i=0,1,2, . . . ,K-1 and where K is an integer,

said decomposing step comprising

splitting each of said M×

M blocks to produce a hierarchy of sub-blocks including the levels designated i=0,1, . . . K-1, so that at each level of the hierarchy, there are 4ⁱ sub-blocks of size M/2ⁱ ×

M/2ⁱ, i=0,1, . . . K-1, and

starting at the level of K-1 in said hierarchy and proceeding to successive levels in said hierarchy, testing each set of four childless brother/sister sub-blocks and merging each set of four childless brother/sister sub-blocks in which the difference of mean pixel value of any two sub-blocks is smaller than a predetermined value until a level in the hierarchy is reached wherein there are no sets of childless brother/sister sub-blocks to be tested,

applying an orthogonal transform individually to each of said sub-blocks comprising said M×

M blocks of pixels to form transform coefficients for each of said sub-blocks,

utilizing an encoder to convert the transform coefficients for each sub-block into a signal in the form of a stream of bits, and

transmitting said signal in the form of a stream of bits for each of said sub-blocks via a channel to a receiver at a remote location.

10. A method for processing a signal corresponding to a still image so that said still image can be transmitted to a remote location via a channel, said method comprising the steps of

providing a signal comprising a two-dimensional array of pixels which is representative of a still image,

dividing said signal into blocks of pixels of size M×

M, each of said M×

M blocks of pixels having a content,

depending on the content of each of said M×

M blocks of pixels, selectively decomposing each of said M×

M blocks of pixels into one or more sub-blocks of pixels, each of said sub-blocks being of a size given by M/2ⁱ ×

M/2ⁱ, where i=0,1,2, . . . , K-1 and where K is an integer,

said decomposing step comprising

splitting each of said M×

M blocks to produce a hierarchy of sub-blocks including the levels designated i=0,1, . . . K-1, so that at each level of the hierarchy, there are 4ⁱ sub-blocks of size M/2ⁱ ×

M/2ⁱ, i=0,1, . . . K-1, and

starting at the level of K-1 in said hierarchy and proceeding to successive levels in said hierarchy, testing each set of four childless brother/sister sub-blocks and merging each set of four childless brother/sister sub-blocks in which the difference of mean pixel value of any two sub-blocks is smaller than a predetermined value, chosen individually for each level in said hierarchy, until a level in the hierarchy is reached wherein there are no sets of childless brother/sister sub-blocks to be tested,

applying an orthogonal transform individually to each of said sub-blocks comprising said M×

M blocks of pixels to form transform coefficients for each of said sub-blocks,

utilizing an encoder to convert the transform coefficients for each sub-block into a signal in the form of a stream of bits, and

transmitting said signal in the form of a stream of bits for each of said sub-blocks via a channel to a receiver at a remote location.

11. A method for processing a signal corresponding to a still image comprising the steps of

providing a signal comprising a two dimensional array of pixels which is representative of a still image,

dividing said signal comprising said two-dimensional array of pixels into blocks of pixels of varying sizes such that smooth areas of said image are smaller sized blocks and busy areas of said image are larger sized blocks, said dividing step comprises

dividing said image into M×

M blocks of pixels,

splitting said M×

M blocks to produce a hierarchy of sub-blocks including the levels designated 1=0,1, . . . K-1, where K is an integer, so that at each level of the hierarchy there are 4ⁱ sub-blocks of size M/2ⁱ ×

M/2ⁱ, and

starting with the K-1 in the hierarchy and proceeding to successive levels in the hierarchy, testing each set of four childless brother/sister sub-blocks and merging each set of four childless brother/sister sub-blocks and merging each set of four childless brother/sister sub-blocks in which the difference of mean pixel value of any two sub-blocks is smaller than a predetermined value until a level in the hierarchy is reached in which there are no sets of four childless brother/sister sub-blocks to be tested,

applying the orthogonal transform to each of said blocks of pixels to form a two-dimensional array of transform coefficients for each of said blocks of pixels,

compressing the transform coefficients obtained for each block of pixels to form a two-dimensional array of compressed transform coefficients for each of said blocks of pixels,

scanning the two-dimensional array of compressed transform coefficients to form a signal comprising a one-dimensional sequence of transform coefficients for each block of pixels,

utilizing an encoder to encode the signal comprising a one-dimensional sequence of transform coefficients for each block to form a bit stream representative of a still image, and

transmitting said bit stream via a channel to a receiver at a remote location.

12. A method for processing a signal corresponding to a still image comprising the steps of

providing a signal comprising a two dimensional array of pixels which is representative of a still image,

dividing said signal comprising said two-dimensional array of pixels into blocks of pixels of varying sizes such that smooth areas of said image are smaller sized blocks and busy areas of said image are larger sized blocks, said dividing step comprising

dividing said image into M×

M blocks of pixels,

splitting said M×

M blocks to produce a hierarchy of sub-blocks including the levels designated 1=0,1, . . . K-1, where K is an integer, so that at each level of the hierarchy there are 4ⁱ sub-blocks of size M/2ⁱ ×

M/2ⁱ, and

starting with the K-1 in the hierarchy and proceeding to successive levels in the hierarchy, testing each set of four childless brother/sister sub-blocks and merging each set of four childless brother/sister sub-blocks and merging each set of four childless brother/sister sub-blocks in which the difference of mean pixel value of any two sub-blocks is smaller than a predetermined value, determined individually for each level in the hierarchy, until a level in the hierarchy is reached in which there are no sets of four childless brother/sister sub-blocks to be tested,

applying the orthogonal transform to each of said blocks of pixels to form a two-dimensional array of transform coefficients for each of said blocks of pixels,

compressing the transform coefficients obtained for each block of pixels to form a two-dimensional array of compressed transform coefficients for each of said blocks of pixels,

scanning the two-dimensional array of compressed transform coefficients to form a signal comprising a one-dimensional sequence of transform coefficients for each block of pixels,

utilizing an encoder to encode the signal comprising a one-dimensional sequence of transform coefficients for each block to form a bit stream representative of a still image, and

transmitting said bit stream via a channel to a receiver at a remote location.

13. A method for processing a signal corresponding to a still image comprising the steps of

providing a signal comprising of two dimensional array of pixels which is representative of a still image,

dividing said signal comprising said two-dimensional array of pixels into blocks of pixels of varying sizes such that the size of said blocks is determined by finding boundaries where the abutting edges of said varying sized blocks are high contrast edges,

applying the orthogonal transform to each of said blocks of pixels to form a two-dimensional array of transform coefficients for each of said blocks of pixels,

compressing the transform coefficients obtained for each block of pixels to form a two-dimensional array of compressed transform coefficients for each block of pixels,

scanning the two-dimensional array of compressed transform coefficients to form a signal comprising one-dimensional sequence of transform coefficients for each block of pixels,

utilizing an encoder to encode the signal comprising a one-dimensional sequence of transform coefficients for each block to form a bit stream representative of a still image, and

transmitting said bit stream via a channel to a receiver at a remote location.

14. A method for processing a signal comprising the steps of

providing a signal comprising a two-dimensional array of pixels which is representative of a still image,

dividing said signal comprising a two-dimensional array of pixels into blocks of pixels of size M×

M, each of said M×

M blocks of pixels having a content,

selectively decomposing each of said M×

M blocks into one or more sub-blocks,

comparing adjacent sub-blocks and merging said adjacent sub-blocks when the edges of said adjacent sub-blocks are not in high-contrast,

applying the discrete cosine transform to each of said sub-blocks to form transform coefficients,

compressing the transform coefficients formed for each of said sub-blocks to form compressed transform coefficients,

utilizing an encoder to form a bit stream corresponding to the compressed transform coefficients, and

passing the bit stream to a channel coder for transmission via a channel to a receiver at a remote location.

15. The method of claim 14 wherein said selective decomposing step comprises the steps of successively splitting each M×

M block to form a hierarchy of sub-blocks and selectively merging sets of childless brother/sister sub-blocks at one or more levels in said hierarchy.

16. A method for processing a signal comprising the steps of

providing a signal comprising a two-dimensional array of pixels which is representative of a still image,

dividing said signal comprising a two-dimensional array of pixels into blocks of pixels of size M×

M, each of said M×

M blocks of pixels having a content,

decomposing each of said M×

M blocks into one or more sub-blocks,

comparing adjacent sub-blocks and merging said adjacent sub-blocks when the edges of said adjacent sub-blocks are not in high contrast,

applying an orthogonal transform to each of said sub-blocks to form transform coefficients,

compressing the transform coefficients formed for each of said sub-blocks to form compressed transform coefficients,

utilizing an encoder to form a bit stream corresponding to the compressed transform coefficients, and

storing the bit stream in a memory.