Resolution conversion for anti-aliased images using loose gray scale template matching

• US 6,757,431 B2
• Filed: 12/19/2000
• Issued: 06/29/2004
• Est. Priority Date: 12/19/2000
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Handley, John C., Loce, Robert P., Cuciurean-Zapan, Clara
• Primary Examiner(s): Ahmed, Samir
• Assistant Examiner(s): LE, BRIAN Q
• Application Number:
  US09/740,607
• Publication Number:
  US 20020076120A1
• Time in Patent Office: 1,288 Days
• Field of Search: 382/205, 382/209, 382/217, 382/218, 382/219, 382/220, 382/221, 382/270, 382/266, 382/269
• US Class Current: 382/209
• CPC Class Codes: G06T 3/4007 based on interpolation, e.g. bilinear interpolation image demosaicing G06T3/4015; edge-driven or edge-based scaling G06T3/403

Abstract

A method for resolution conversion for re-sampling anti-aliased images is disclosed which decreases bandwidth costs associated with anti-aliased line art and other costs associated with interpolating these images to a desired resolution. The present method first involving the receipt of an image which is comprised of bitmap data including at least a plurality of gray-scale pixel tiles that define the image. Then receiving the image data at a first resolution and extracting pixel tile information of the received image at a second resolution. The method has the step of next using loose gray scale template matching on each of the pixel tile information with at least one of a plurality of templates so as to generate pixel-wise looseness interval values there between. Then, outputting a portion of the enhanced pixel tile information wherein the enhanced pixel tile information is formed by a matching of a template with pixel-wise looseness values. Preferably, the input and output resolutions are at different integer values and the first and second resolutions have a non-integer ratio. The input image can also preferably be comprised of gray halftones and the output enhanced pixel tile can be formed of binary pixel data.

Claims

1. A method for resolution conversion for re-sampling anti-aliased images from an image source in order to decrease bandwidth costs associated with anti-aliased line art and associated with interpolating said images to a desired resolution, comprising:

(a) receiving an image comprised of bitmap of image data, the image data being at a first resolution;

(b) generating a first two-dimensional window, the first two-dimensional window having a plurality image data values, each image data value being associated with a pixel location in the first two-dimensional window;

(c) determining a representative gray scale value for the first two-dimensional window;

(d) determining, a plurality of looseness intervals, each looseness interval being a difference between the determined representative gray scale value of the first two-dimensional window and a target representative gray scale value, the target representative gray scale value being associated with one template of a plurality of templates;

(e) comparing the determined looseness intervals to a threshold looseness interval, the threshold looseness interval being a maximum allowable value for the determined looseness interval that indicates a loose match;

(f) determining, based upon the comparison between the determined looseness intervals and the threshold looseness interval, which template of the plurality of templates loosely matches the first two-dimensional window of image data values, the loosely matched template being a template wherein the determined looseness interval associated therewith is equal to a non-zero value and the threshold looseness interval is equal to a non-zero value, an exactly matched template being a template wherein the associated determined looseness interval is equal to a zero value and the threshold looseness interval is equal to a zero value; and

(g) generating, based on the template loosely matched the first two-dimensional window of image data values, a second two-dimensional window of image data values, the second two-dimensional window of image data values having a second resolution, the first resolution being different from the second resolution.

2. The method as claimed in claim 1, wherein the second resolution is less than the first resolution.

3. The method as claimed in claim 1, wherein the second resolution is greater than the first resolution.

4. A method for converting image data of a first resolution to image data of a second resolution, comprising:

(a) receiving an image comprised of bitmap of image data, the image data being at a first resolution;

(b) generating a first two-dimensional window, the first two-dimensional window having a plurality image data values, each image data value being associated with a pixel location in the first two-dimensional window;

(c) determining, a plurality of sets of looseness intervals for the first two-dimensional window, each set of looseness intervals being associated with one template of a plurality of templates, each looseness interval being a difference between an image data value associated with a pixel location in the first two-dimensional window and a target value from a set of target values, the target value being associated with a corresponding pixel location from a template, the set of target gray scale values being associated with one template of a plurality of templates;

(d) comparing the determined sets of looseness intervals to a threshold looseness interval, the threshold looseness interval being a maximum allowable value for the determined sets of looseness interval that indicates a loose match;

(e) determining, based upon the comparison between the determined sets of looseness intervals and the threshold looseness interval, which template of the plurality of templates loosely matches the first two-dimensional window of image data values, the loosely matched template being a template wherein a portion of the determined looseness intervals associated therewith are equal to a non-zero value and the threshold looseness interval is equal to a non-zero value, an exactly matched template being a template wherein all the associated determined looseness intervals are equal to a zero value and the threshold looseness interval is equal to a zero value; and

(f) generating, based on the template loosely matching the first two-dimensional window of image data values, a second two-dimensional window of image data values, the second two-dimensional window of image data values having a second resolution, the first resolution being different from the second resolution.

5. The method as claimed in claim 4, wherein the second resolution is less than the first resolution.

6. The method as claimed in claim 4, wherein the second resolution is greater than the first resolution.

7. A method as claimed in claim 4, wherein the template of the plurality of templates which matches the first two-dimensional window of image data values is determined by:

(c1) determining an average looseness interval value for each set of looseness intervals;

(d1) comparing each average looseness interval value with the threshold looseness interval; and

(e1) selecting the template of the plurality of templates having an associated average looseness interval value closest to the threshold looseness interval as the template that loosely matches the first two-dimensional window of image data values, the loosely matched template being a template wherein a difference between the associated average looseness interval value and the threshold looseness interval is equal to a non-zero value, an exactly matched template being a template wherein a difference between the associated average looseness interval value and the threshold looseness interval is equal to a zero value.

8. The method as claimed in claim 4, wherein the template of the plurality of templates which matches the first two-dimensional window of image data values is determined by:

(d1) comparing each looseness interval of a set of looseness intervals with a looseness interval threshold value to determine a looseness interval number, the looseness interval number being equal to how many looseness intervals within the set of looseness intervals are less than the looseness interval threshold value; and

(d2) selecting the template of the plurality of templates having a greatest associated looseness interval number as the template that loosely matches the first two-dimensional window of image data values.