Image quality improvement by hierarchical pattern matching with variable size templates

• US 5,365,251 A
• Filed: 08/28/1992
• Issued: 11/15/1994
• Est. Priority Date: 08/28/1992
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Denber, Michel J.
• Primary Examiner(s): Oberley, Alvin E.
• Assistant Examiner(s): Saras, Steven J.
• Application Number:
  US07/936,456
• Time in Patent Office: 809 Days
• Field of Search: 340/154, 340/726, 340/728, 382/54, 358/456-458, 345/130, 345/137, 345/138, 345/203
• US Class Current: 345/611
• CPC Class Codes: G06K 15/02 using printers
• CPC Class Codes: G06K 2215/006 Anti-aliasing raster data
• CPC Class Codes: G09G 5/28 for enhancement of character form, e.g. smoothing

Abstract

Image quality is improved by the prevention of aliasing using a hierarchial pattern matching operation incorporating variable-sized templates. A template which is passed over an image is partitioned into a plurality of sub-templates. The corner sub-templates of the template are eliminated from consideration. It is determined whether the remaining sub-templates contain anything other than all-white or all-black. If a sub-template reports something other than all-white or all-black, the sub-template is checked with a matching region. The matching region defines the action to be taken on the central pixel beneath the template. The pattern matching operation prevents the necessity for an increased memory capacity while providing increased levels of gray for each pixel.

Claims

1. A pattern matching method in a signal processing device for improving image quality, comprising:

partitioning a template into a plurality of sub-templates;

passing the template over an image on a pixel-by-pixel basis such that the template is centered about a central pixel;

determining whether the sub-templates contain image information other than either of all white and all black;

if any of the sub-templates are determined to contain image information other than either of all white and all black, checking the sub-template containing such image information by using a matching region, said matching region including at least a portion of the sub-template containing such image information but less than the entire template, said matching region extending beyond the sub-template containing such image information at least to the central pixel;

matching a pattern in the matching region to a corresponding pattern to specify an action to be taken on the central pixel; and

generating an output image based on the step of matching the pattern in the matching region to a corresponding pattern.

2. The method according to claim 1, including removing corner sub-templates of said template prior to passing the template over the image.

3. The method according to claim 2, wherein if more than one of said sub-templates are determined to contain image information other than either of all white and all black, resulting in the use of more than one matching region and resulting in the specification of different actions to be taken on the central pixel, said method includes averaging the Specified actions to be taken on the central pixel.

4. The method according to claim 2, wherein if more than one of said sub-templates are determined to contain image information other than either of all white and all black, resulting in the use of more than one matching region and resulting in the specification of different actions to be taken on the central pixel, said method includes taking a vote among the specified actions to be taken on the central pixel.

5. The method according to claim 4, wherein if said vote results in a tie, said method includes matching a pattern in a central one of said sub-templates to a corresponding pattern to specify an action to be taken on the central pixel.

6. The method according to claim 5, wherein said step of matching a pattern in a central one of said sub-templates comprises a 3×

3 pattern matching operation.

7. The method according to claim 2, wherein if none of the sub-templates is determined to contain image information other than either of all white and all black, said method includes performing a pattern matching operation on a central one of said sub-templates.

8. The method according to claim 7, wherein said pattern matching operation comprises a 3×

3 pattern matching operation.

9. The method according to claim 1, wherein said template comprises a 9×

9 template.

10. The method according to claim 1, wherein said sub-templates comprise nine 3×

3 sub-templates.

11. The method according to claim 1, wherein:

the partitioning step includes partitioning the template into a central sub-template and at least one edge sub-template that borders the central sub-template;

the determining step includes determining whether the least one edge sub-template contains image information other than either of all white and all black;

the checking step occurs if any edge sub-template is determined to contain image information other than either of all white and all black; and

the matching region used in the checking step includes at least a portion of the edge sub-template containing such information and extends beyond the edge sub-template containing such image information into the central sub-template at least to the central pixel.