Method of and system for encoding digital images

• US 5,960,119 A
• Filed: 08/28/1996
• Issued: 09/28/1999
• Est. Priority Date: 09/01/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Maeda, Junji, Echigo, Tomio, Ioka, Mikihiro, Hong, Jung-Kook
• Primary Examiner(s): Coles, Edward L.
• Assistant Examiner(s): WALLERSON, MARK E
• Application Number:
  US08/697,657
• Time in Patent Office: 1,126 Days
• Field of Search: 385/426, 385/261.1, 385/261.2, 385/261.3, 385/427, 385/433, 385/432, 385/448, 385/453, 385/538, 382/232, 382/240, 382/248, 382/250, 382/170, 382/171, 348/405, 348/415, 348/416, 348/408
• US Class Current: 382/248
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques
• CPC Class Codes: H04N 19/94 Vector quantisation
• CPC Class Codes: H04N 19/96 Tree coding, e.g. quad-tree coding

Abstract

Edge information sensitive to a visual characteristic is efficiently stored, block artifacts are reduced, and highly efficient compression is accomplished by an image compressing method. The system encodes a digital image and includes: an image input for inputting the digital image; a segmenter for segmenting the digital image into a plurality of primitive regions and computing parameters about the luminance and chrominances of the primitive region for each the primitive region; a first merger for merging the plurality of primitive regions to generate first-order block candidates and classifying each of the first-order block candidates into any of a plurality of predetermined patterns; a first clusterer for clustering, among the first-order block candidates belonging to the same classification, the first-order block candidates, where the parameters about the luminance and chrominances of the primitive regions thereof can be approximated with linear transformation, as a first-order block, and representing a transformation coefficient of the linear transformation with a parameter; a second merger for merging a plurality of the first-order blocks to generate second-order block candidates and classifying the second-order block candidate in accordance with the pattern of each the first-order blocks of the second-order block candidate; a second clusterer for clustering, among the second-order block candidates belonging to the same classification, the second-order block candidates, where the transformation coefficients of the first-order blocks thereof can be approximated with linear transformation, as a second-order block, and representing a transformation coefficient of the linear transformation with a parameter; a controller for recursively executing the clustering of the block candidates while raising the order of the block in sequence until the clustering of the blocks becomes impossible; and an encoder for encoding the parameters of the coexisting multi-order blocks.

Claims

1. A method of encoding a digital image, comprising the steps of:

(a) segmenting said digital image into a plurality of primitive regions and computing for each said primitive region, parameters about the luminance and chrominances of the primitive region thereof;

(b) merging said plurality of primitive regions to generate first-order block candidates;

(c) classifying said first-order block candidate into corresponding one of predetermined patterns;

(d) clustering, as a first-order block, the first-order block candidates which belong to the same classification, and parameters about the luminance and chrominances of said primitive regions in which can be approximated by linear transformation, and representing transformation coefficients of said linear transformation as parameters;

(e) merging said plurality of first-order blocks to generate second-order block candidates;

(f) classifying said second-order block candidate by a pattern of each said first-order block constituting said second-order block candidate;

(g) clustering, as a second-order block, said second-order block candidates which belong to the same classification, and transformation coefficients of said first-order blocks in which can be approximated with linear transformation, and representing the transformation coefficient of said linear transformation as parameters;

(h) recursively executing steps (e) through (g) while raising the order of the block in sequence until the clustering of the blocks becomes impossible; and

(i) encoding the parameters of the coexisting multi-order blocks.

2. The method as set forth in claim 1, wherein said step (a) further includes classifying each of said plurality of primitive regions into any one of a plurality of primitive region patterns.

3. The method as set forth in claim 2, wherein said plurality of primitive region patterns are defined in accordance with existence of a change of a plurality of pixels constituting said primitive regions.

4. The method as set forth in claim 2, wherein said step (c) classifies said first-order block candidate into any one of predetermined patterns, based on said primitive region pattern of each said primitive region constituting said first-order block candidate and on rotational angle corresponding to said primitive region pattern.

5. The method as set forth in claim 1, wherein in said step (b), said first-order blocks adjacent to one another are disposed so as to overlap one another.

6. The method as set forth in claim 1, wherein, in said step (d), the meaning that "the transformation coefficients of said first-order blocks thereof can be approximated with linear transformation" means a case where the error is less than a predetermined threshold value, when the parameters about the luminance and the chrominances of one of said first-order block candidates are approximated with those of another first-order block candidate, shifted and multiplied by fixed quantities.

7. The method as set forth in claim 1, wherein the clustering in said step (d) is performed in order of classification where the number of the classified first-order block candidates is greater.

8. The method as set forth in claim 1, wherein, in said step (d), any of said first-order blocks clustered to the same pattern is selected as a representative region, parameters about the address, luminance, and chrominances of said representative region are stored, and the remaining first-order blocks are coded with transformation coefficients of a rotational angle, a luminance, and chrominances based on said representative region.

9. The method as set forth in claim 8, wherein, in the classification of the second-order block candidates in said step (f), said second-order block candidate is classified into any one of predetermined patterns, based on said representative region of said first-order blocks constituting each said second-order block candidates and on said transformation coefficients.

10. The method as set forth in claim 1, wherein, in said step (g), said transformation coefficients of said first-order blocks constituting one of said second-order block candidates can be approximated by linear transformation in a case where the error with the transformation coefficient in another said second-order block candidate is less than a predetermined threshold value, when said transformation coefficients are approximated with shifted and multiplied by fixed quantities.

11. A method of encoding a digital image, comprising the steps of:

(a) segmenting said digital image into a plurality of primitive regions;

(b) classifying said primitive region into corresponding one of predetermined patterns, and computing for each said primitive region, a parameter about the classified pattern and parameters about the luminance and the chrominances of the primitive region;

(c) merging said plurality of primitive regions to generate first-order block candidates;

(d) classifying each of said first-order block candidate by the parameters about the classified pattern of said primitive region constituting the first-order block candidate; and

(e) clustering, as a first-order block, said first-order block candidates which belong to the same classification, the parameters about the luminance and chrominances of said primitive regions in which can be approximated by linear transformation, and representing transformation coefficients of said linear transformation as parameters.

12. The method as set forth in claim 11, wherein said patterns are defined in accordance with existence of a change of a plurality of pixels constituting said primitive regions.

13. The method as set forth in claim 11, wherein said step (d) classifies said first-order block candidate, based on said primitive region patterns of said primitive regions constituting said first-order block candidate and on rotational angle corresponding to said pattern.

14. The method as set forth in claim 11, wherein in said step (e) said first-order blocks adjacent to one another are disposed so as to overlap one another.

15. The method as set forth in claim 11, wherein, in said step (e), the meaning that "the transformation coefficients of said first-order blocks thereof can be approximated by linear transformation" means a case where the error is less than a predetermined threshold value, when the parameters about the luminance and the chrominances of one of said first-order block candidates are approximated with those of another first-order block candidate, shifted and multiplied by fixed quantities.

16. The method as set forth in claim 11, wherein the clustering in said step (e) is performed in order of classification where the number of the classified first-order block candidates is greater.

17. A system for encoding a digital image, comprising:

image input means for inputting said digital image;

means for segmenting said digital image into a plurality of primitive regions and computing for each said primitive region, parameters about the luminance and chrominances of the primitive region;

means for merging said plurality of primitive regions to generate first-order block candidates and classifying each of said first-order block candidates into any one of a plurality of predetermined patterns;

means for clustering, as a first order block, the first-order block candidates which belong to the same classification, and the parameters about the luminance and chrominances of said primitive region in which can be approximated by linear transformation, and representing transformation coefficients of said linear transformation as parameters;

means for merging a plurality of the first-order blocks to generate second-order block candidates and classifying the second-order block candidate in accordance with a pattern of each said first-order blocks constituting said second-order block candidate;

means for clustering, as a second-order block, the second-order block candidates which belong and to the same classification, and the transformation coefficients of said first-order blocks in which can be approximated by linear transformation, and representing a transformation coefficient of said linear transformation as parameters;

control means for recursively executing steps (e) and (g) while raising the order of the block in sequence until the clustering of the blocks becomes impossible; and

means for encoding the parameters of the coexisting multi-order blocks.

18. A system for encoding a digital image, comprising:

image input means for inputting said digital image;

means for segmenting said digital image into a plurality of primitive regions and computing for each said primitive region, parameters about the luminance and the chrominances of the primitive region;

means for merging said plurality of primitive regions to generate first-order block candidates and classifying said first-order block candidate into corresponding one of predetermined patterns; and

means for clustering, as a first-order block the first-order block candidates which belong to the same classification, and the parameters about the luminance and chrominances of said primitive region in which can be approximated by linear transformation, and representing transformation coefficients of said linear transformation as parameters.

19. A method of decoding a digital image, comprising the steps of:

(a) computing parameters about the luminance and chrominances of a primitive region in a representative region of clustered first-order blocks;

(b) computing the parameters about the luminance and chrominances of the remaining first-order blocks, based on said parameters about an address of said representative region, an rotational angle against said representative region, and a transformation coefficient of linear transformation for the luminance and chrominances of said primitive region; and

(c) secursively executing steps (a) through (b) while raising the order of the block in sequence.