Systems and methods for reducing boundary artifacts in hybrid compression

• US 6,192,155 B1
• Filed: 09/16/1998
• Issued: 02/20/2001
• Est. Priority Date: 09/16/1998
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Fan, Zhigang
• Primary Examiner(s): Tadayon, Bijan
• Assistant Examiner(s): Bayat, Ali
• Application Number:
  US09/154,312
• Time in Patent Office: 888 Days
• Field of Search: 382/232, 382/266, 382/268, 382/269, 382/275, 382/173, 382/177, 382/179, 382/180, 382/181, 382/233, 382/235, 382/236, 382/238, 382/239, 382/240, 382/241, 382/242, 382/243, 382/245, 382/251, 358/433
• US Class Current: 382/232
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00

Abstract

A recursive dilation method and apparatus reduces the boundary artifacts occurring in hybrid compression. Documents containing both pictures and text are most efficiently compressed using a first compression standard for the picture region and a second compression standard for the text region, and thus inherently produce boundary blocks of both types, but such boundary blocks are most efficiently compressed when they contain only picture data and completely contain picture data, or only text data and completely contain text data. The non-picture data or non-text data in such boundary blocks can be considered “missing” data. The recursive dilation method and apparatus assigns the values of the boundary pixels to the neighboring pixels which have missing data.

Claims

1. A method for compressing an image, comprising:

dividing the image into image segments, the image segments including at least one segment of a first type and at least one segment of a second type, wherein at least each at least one segment of the first type is divided into image blocks and compressed on a block-by-block basis, and at least one of the image blocks of the at least one segment of the first type contains a boundary between data of the first type and missing data, each image block comprising a plurality of pixels, and each pixel having a value;

identifying each image block containing a boundary with missing data;

recursively replacing the missing data of each first type boundary block with first type data by assigning the value of a closest boundary pixel;

compressing each first type image block and each first type boundary block using a first compression technique; and

compressing each at least one segment of the second type using a second compression technique.

2. The method of claim 1, wherein the step of recursively replacing comprises determining, for each pixel of the missing data of the first type boundary block, whether that pixel is adjacent to a boundary pixel of the first type.

3. The method of claim 2, wherein assigning the value of the closest boundary pixel comprises assigning the value of the boundary pixel to the pixels of the missing data of the first type boundary block determined to be adjacent to the boundary pixel.

4. The method of claim 2, wherein assigning the value of the closest boundary pixel comprises assigning the value of an adjacent pixel to the pixels of the missing data of the first type boundary block determined not to be adjacent to the boundary pixel.

5. The method of claim 4, wherein the value of the adjacent pixel assigned is the value of the closest boundary pixel.

6. The method of claim 1, wherein the first compression technique is JPEG.

7. The method of claim 1, wherein the second compression technique is LZW.

8. The method of claim 1, wherein:

dividing the image into image segments further comprises dividing the image into at least one segment of a third type; and

the method further comprises compressing each third type segment using a third compression technique.

9. The method of claim 1, wherein dividing the image into image segments and dividing the segments into image blocks are performed concurrently.

10. The method of claim 1, where at least each at least one segment of the second type is divided into image blocks and compressed on a block-by-block basis, and at least one of the image blocks of the at least one segment of the second type contains a boundary between data of the second type and missing data, each second type image block comprising a plurality of pixels, and each pixel of the second type having a value, the method further comprising:

identifying each second type image block containing a boundary with missing data;

recursively replacing the missing data of each second type boundary block with second type data; and

compressing each second type image block and each second type boundary block using the second compression technique.

11. An apparatus for compressing an image, comprising:

an image segmenting portion that divides the image into image segments, the image segments including at least one segment of a first type and at least one segment of a second type;

a segment blocking portion that divides each at least one segment of the first type into image blocks, on a block-by-block basis, at least one of the image blocks of the at least one segment of the first type containing a boundary between data of the first type and missing data, each image block comprising a plurality of pixels, and each pixel having a value;

a block analyzer that identifies each image block containing a boundary with missing data;

a recursive dilation data generator that recursively replaces the missing data of each first type boundary block with first type data by assigning the value of a closest boundary pixel;

a first compressor that compresses each first type image block and each first type boundary block on a block-by-block basis, using a first compression technique; and

a second compressor that compresses each at least one segment of the second type using a second compression technique.

12. The apparatus of claim 11, wherein the recursive dilation data generator determines, for each pixel of the missing data of the first type boundary block, whether that pixel is adjacent to a boundary pixel of the first type.

13. The apparatus of claim 12, wherein the recursive dilation data generator assigns the value of the boundary pixel to the pixels of the missing data of the first type boundary block determined to be adjacent to the boundary pixel.

14. The apparatus of claim 12, wherein the recursive dilation data generator assigns the value of an adjacent pixel to the pixels of the missing data of the first type boundary block determined not to be adjacent to the boundary pixel.

15. The apparatus of claim 14, wherein the value of the adjacent pixel assigned is the value of the closest boundary pixel.

16. The apparatus of claim 11, wherein the first compression technique is JPEG.

17. The apparatus of claim 11, wherein the second compression technique is LZW.

18. The apparatus of claim 11, wherein:

the image segmenting portion further divides the image into at least one segment of a third type; and

the apparatus further comprises a third compressor that compresses each third type segment using a third compression technique.

19. The apparatus of claim 11, wherein the image segmenting portion includes the image blocking portion and concurrently divides the image into image segments and divides the segments into image blocks.

20. The apparatus of claim 11, wherein:

the image blocking portion divides each at least one segment of the second type into image blocks, at least one of the image blocks of the at least one segment of the second type containing a boundary between data of the second type and missing data, each second type image block comprising a plurality of pixels, and each pixel of the second type having a value;

the block analyzer identifies each second type image block containing a boundary with missing data;

the recursive dilation data generator recursively replaces the missing data of each second type boundary block with second type data; and

the second compressor compresses each second type image block and each second type boundary block on a block-by-block basis, using the second compression technique.