Image coding and decoding methods, image coder, and image decoder

• US 6,243,416 B1
• Filed: 02/04/2000
• Issued: 06/05/2001
• Est. Priority Date: 03/12/1997
• Status: Expired due to Term

• Current Assignee: Oki Data Corporation (OKI Electric Industry Company Limited)
• Original Assignee: Oki Data Corporation (OKI Electric Industry Company Limited)
• Inventors: Yoshida, Yoshihiko, Matsushiro, Nobuhito
• Primary Examiner(s): Rao, Andy
• Assistant Examiner(s): AN, SHAWN S
• Application Number:
  US09/499,334
• Time in Patent Office: 487 Days
• Field of Search: 375/240, 348/396, 348/392, 348/395, 382/251, 382/283, 382/176
• US Class Current: 375/240
• CPC Class Codes: H04N 19/59 involving spatial sub-sampling or interpolation, e.g. alteration of picture size or resolution
• CPC Class Codes: H04N 19/94 Vector quantisation

Abstract

An image is divided into blocks and coded by matching each block with a pattern having either a single region, or two or more regions defined by internal edges. The coded value of the block includes a pattern identifier, and a single pixel value for each region in the matching pattern. The coded image is decoded by constructing blocks divided into regions according to the pattern identifiers, and filling each region with the given single pixel value. The decoded blocks may be the same size as the blocks in the original image, or smaller, in which case the decoded image is reduced, or larger, in which case the decoded image is enlarged.

Claims

1. A method of coding an image made up of pixels having pixel values by dividing the image into blocks, comprising the steps of:

providing a table of predetermined patterns identical in size and shape to said blocks, said patterns including a plurality of patterns each having at least two regions defined by at least one internal edge, said patterns being identified by pattern identifiers;

detecting internal edges in said blocks, thereby matching each block among said blocks with one of the patterns in said table;

calculating, for each block among said blocks, one representative pixel value for each region in the pattern matching said block, said one representative pixel value being calculated from the pixel values of the pixels in said block in positions corresponding to said region; and

coding each said block by a pattern identifier identifying the pattern matching the block, accompanied by the representative pixel value calculated for each region in the pattern thus identified.

2. The method of claim 1, wherein said step of calculating comprises calculating, for each block among said blocks, for each region in the pattern matching said block, an average pixel value of the pixels in corresponding positions in said block.

3. The method of claim 1, wherein the patterns in said table have at most two regions each.

4. The method of claim 3, wherein the two regions in each pattern having two regions are defined by a straight internal edge.

5. The method of claim 4, wherein said step of detecting internal edges further comprises, for each said block, the steps of:

comparing differences between the pixel values of adjacent corner pixels in said block with a threshold value, to determine whether an internal edge is present;

if an internal edge is present, comparing said differences with each other to select two sides of said block intercepted by said internal edge; and

if an internal edge is present, comparing the pixel values of adjacent pixels on said two sides, to determine where said internal edge intercepts each of said two sides.

6. The coding method of claim 1, wherein said step of coding each said block codes the pattern identifier of said pattern having only one region as a single bit.

7. A method of decoding coded image information coded by the method of claim 1, comprising the steps of:

providing at least two tables of predetermined patterns, each table among said tables storing patterns of a different size, each said table including a plurality of patterns each having at least two regions defined by at least one internal edge, said patterns being identified by the pattern identifiers used in the method of claim 1;

selecting one table among said tables, according to mode information;

for each pattern identifier in said coded image information, reading the pattern identified by said pattern identifier from the selected table; and

for each pattern identifier in said coded image information, constructing a block made up of regions matching the regions in the pattern thus read, by filling each region in said block with the representative pixel value given for said region in said coded image information.

8. The method of claim 7, wherein said tables comprise:

a first table identical to the table employed in the coding method of claim 1;

a second table having patterns smaller than the patterns in said first table; and

a third table having patterns larger than the patterns in said first table.

9. The method of claim 7, wherein each said table also includes a pattern having only one region.

10. The method of claim 1, wherein said table also includes a pattern having only one region.

11. A method of decoding coded image information coded by the method of claim 1, comprising the steps of:

providing a table identical to the table employed in the method of claim 1;

for each pattern identifier in said coded image information, reading the pattern identified by said pattern identifier from said table; and

for each pattern identifier in said coded image information, constructing a block made up of regions matching the regions in said pattern, by filling each region in said block with the representative pixel value given for said region in said coded image information.

16. The image coder of claim 11, wherein said pixel value calculator comprises a plurality of averagers, each said averager among said averagers calculating an average value for just one region per block.

12. An image coder for coding an image made up of pixels having values by dividing the image into blocks, comprising:

a coding parameter memory storing patterns identical in size and shape to said blocks, said patterns including a plurality of patterns each having at least two regions defined by at least one internal edge, said patterns being identified by pattern identifiers;

an edge detector coupled to said coding parameter memory, for detecting internal edges in said blocks, thereby matching each block among said blocks with one of the patterns in said coding parameter memory;

a partitioner coupled to said coding parameter memory for dividing the pixels in each said block into regions corresponding to the regions in the pattern matching said block;

a pixel value calculator coupled to said partitioner for calculating a representative pixel value for each region in each said block said representative pixel value being calculated from the pixel values of the pixels in said region in said block; and

a code assembler coupled to said pixel value calculator, for coding each said block by a pattern identifier identifying the pattern matching the block, accompanied by the representative pixel value calculated for each said region in said block.

13. The image coder of claim 12, wherein said edge detector further comprises:

an edge presence detector for comparing differences between the pixel values of adjacent corner pixels in one said block with a threshold value, thereby determining whether an internal edge is present, and if an internal edge is present, comparing said differences with each other, thereby selecting two sides of said block intercepted by said internal edge; and

an intercept locator for comparing the pixel values of adjacent pixels on said two sides, thereby determining where said internal edge intercepts each of said two sides, and outputting corresponding intercept information.

14. The image coder of claim 13, wherein said coding parameter memory further comprises:

a conversion table for converting said intercept information to said pattern identifier;

a pattern table storing said patterns at addresses corresponding to said pattern identifiers; and

a region size table storing information indicating how many pixels are contained in each said region in each said pattern.

15. The image coder of claim 12, wherein said pixel value calculator comprises at least one averager for calculating an average value of the pixel values of the pixels in a region as the representative pixel value of said region.

17. The image coder of claim 12, further comprising a selector coupled to said edge detector, for providing the pixel values of the pixels constituting one block to said partitioner when said edge detector detects an internal edge in said block, and providing said pixel values directly to said pixel value calculator when said edge detector does not detect an internal edge in said block.

18. An image decoder for decoding coded image information coded by the image coder of claim 12, comprising:

a decoding parameter memory storing patterns at addresses corresponding to the pattern identifiers employed in said claim 12, said patterns including a plurality of patterns each having at least two regions defined by at least one internal edge; and

a fill processor coupled to said decoding parameter memory, for reading a pattern from said decoding parameter memory, according to a pattern identifier in said coded image information, and constructing a block made up of regions matching the regions in said pattern, by filling each region in said block with the representative pixel value given for said region in said coded image information.

19. The image decoder of claim 18, wherein said patterns also include a pattern having only one region.

20. The image decoder of claim 18, wherein said fill processor has a counter for counting pixels filled in by said fill processor, and said fill processor stops filling when said counter indicates that said block has been completely filled in.

21. The image decoder of claim 18, wherein said decoding parameter memory comprises a plurality of tables, each table among said tables storing patterns of a different size, each said table including a plurality of patterns each having at least two regions defined by internal edges, and said image coder further comprises a mode selector coupled to said decoding parameter memory, for receiving mode information and selecting one of said tables according to said mode information.

22. The image decoder of claim 21, wherein each said table also includes a pattern having only one region.

23. The image decoder of claim 21, wherein said decoding parameter memory comprises:

a first table identical to the table employed in the image coder of claim 12;

a second table having patterns smaller than the patterns in said first table; and

a third table having patterns larger than the patterns in said first table.

24. The image decoder of claim 21, wherein said fill processor comprises:

a block size selector for selecting a size equal to the size of the patterns in the table selected by said mode selector, thereby causing said fill processor to fill in a block of the selected size; and

a counter for counting pixels filled in by said fill processor, causing said fill processor to stop filling when said fill processor has filled in a number of pixels matching the size selected by said block size selector.

25. The image coder of claim 12, wherein said patterns also include a pattern having only one region.

26. The image coder of claim 25, wherein said code assembler codes the pattern identifier of said pattern having only one region as a single bit.