Method for optimal discrete rendering of images

• US 5,191,640 A
• Filed: 12/26/1990
• Issued: 03/02/1993
• Est. Priority Date: 12/26/1990
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Plass, Michael F.
• Primary Examiner(s): Shaw, Dale M.
• Assistant Examiner(s): Tung, Kee M.
• Application Number:
  US07/633,930
• Time in Patent Office: 797 Days
• Field of Search: 395/100, 395/107, 395/116, 395/108, 395/117, 395/112, 395/114, 395/325, 395/500, 358/448, 358/80, 358/455, 358/456, 358/457, 340/728, 340/731, 340/744
• US Class Current: 358/1.13
• CPC Class Codes: G06K 15/00 Arrangements for producing a permanent visual presentation of the output data , e.g. computer output printersprinting or plotting combined with another operation, e.g. with conveying, G06K17/00
• CPC Class Codes: H04N 1/4051 producing a dispersed dots halftone pattern, the dots having substantially the same size different sizes H04N1/4057

Abstract

A technique for efficiently converting an original sampled image into a bitmap suitable for a specific output device. The method includes explicit printer and perception effects, and employs local permutations of bits, to find optimal bit settings. A continuous-tone image is first sampled to form a sampled image (12), through which a series of swaths are defined. For each swath (14i) in turn, an iterative procedure examines a column of bits (16) at a time, determining which configuration of the column of bits yields a minimal local difference value between the trial bitmap and the sampled image. While holding the rest of the trail bitmap constant, the column of bits is permuted and the difference value calculated, for each configuration of the column'"'"'s look-ahead bits (22). To determine the difference values, local printer (17a) and perception (17b) models calculate effects between bits, while a local comparison model calculates the difference between the trial bitmap and the sampled image. The printable bitmap resulting from the methods of the present invention can be displayed by the output device to provide a faithful duplication of the original image.

Claims

1. A method for converting an original image to a printable bitmap comprising the steps of:

(a) defining a printer model (17a);

(b) defining a perception model (17b);

(c) defining a comparison model;

(d) sampling said original image to form a sampled image (12);

(e) constructing a plurality of parallel swaths (14) through said sampled image (12), each of said swaths (14) being a linear path of adjacent bits, each path having a width of n bits;

(f) defining a linear array of columns of bits (16a, 16b, etc.) for each of said swaths (14), each of said columns of bits (16) being n bits wide, each of said columns of bits (16) for each of said swaths (14) being numbered consecutively;

(g) choosing a configuration of values of a first column of bits (16a) of an ith swath (14i), said ith swath (14i) including a number p of said columns of bits (16) and q columns of non-image bits having preset bits (26);

(h) determinig a first set of look-ahead bits (22a) adjacent to said first column of bits (16a) and within said ith swath (14i), said first set of look-ahead bits (22a) including a set of k consecutive columns of bits of said ith swath (14i), said first set of look-ahead bits having a configuration of values;

(i) applying said printer model (17a) to a first neighborhood (20a) around said first column of bits (16a) to provide a printed image of said first neighborhood (20a);

(j) applying said perception model (17b) to a second neighborhood (18a) within said printed image of said first neighborhood (20a) around said first column of bits (16a) to provide a perceived image of said second neighborhood (18a);

(k) applying said comparison model to compare said perceived image of said second neighborhood (18a) with said sampled image (12) of said second neighborhood (18a) to arrive at a difference value for each bit of a subset of columns of bits of said ith swath (14i) lying within said second neighborhood (18);

(l) calculating a combined difference value from said difference values;

(m) storing said combined difference value along with said configuration of values of said first column of bits (16);

(n) altering said configuration of values of said first column of bits (16) of said ith swath (14i);

(o) repeating steps (i) through (n) 2ⁿ times until all of said configurations of values of said first column of bits (16) of said ith swath (14i) have been used;

(p) determining which of said configurations of values of said first column of bits (16) provides a least combined difference value for said configuration of values of said first set of look-ahead bits (22), by comparing said stored combined difference values;

(q) altering said configuration of values of said first set of look-ahead bits (22) of said ith swath (14i);

(r) repeating steps (i) through (q) up to 2^n+k times until all of said configurations of values of said first set of look-ahead bits (22) of said ith swath (14i) have been used; and

(s) storing a configuration of values of said first column of bits (16) for each of said configuration of values of said first set of look-ahead bits (22), said stored configuration of values of said first column of bits (16) providing a least combined difference value for a respective configuration of values of said first set of look-ahead bits (22).

2. The method as recited in claim 1 further comprising the steps of:

(t) choosing a configuration of values of a jth column of bits (16b) of said ith swath (14i);

(u) determining a jth set of look-ahead bits (22b) adjacent to said jth column of bits (16b) and within said ith swath (14i), said jth set of look-ahead bits (22b) including a set of k consecutive columns of bits of said ith swath (14i), said jth set of look-ahead bits (22b) having a configuration of values;

(v) applying said printer model (17a) to a first neighborhood (20b) around said jth column of bits (16b) to provide a printed image of said first neighborhood (20b);

(w) applying said perception model (17b) to a second neighborhood (18b) within said printed image of said first neighborhood (20b) around said jth column of bits (16b) to provide a perceived image of said second neighborhood (18b);

(x) applying said comparison model to compare said perceived image of said second neighborhood (18b) with said sampled image (12) of said second neighborhood (18b) to arrive at a difference value for each bit of a subset of columns of bits of said ith swath (14i) lying within said second neighborhood (18b);

(y) calculating a combined difference value from said difference values;

(z) storing said combined difference value along with said configuration of values of said jth column of bits (16b);

(aa) altering said configuration of values of said jth column of bits (16b) of said ith swath (14i);

(ab) repeating steps (v) through (aa) 2ⁿ times until all of said configurations of values of said jth column of bits (16b) of said ith swath (14i) have been used;

(ac) determining which of said configurations of values of said jth column of bits (16b) provides a least combined difference value for said values of said jth set of look-ahead bits (22b), by comparing said stored combined difference values;

(ad) altering said configuration of said jth set of look-ahead bits (22b) of said ith swath (14i);

(ae) repeating steps (v) through (ad) up to 2^n+k times until all of said configurations of values of said jth set of look-ahead bits (22b) of said ith swath (14i) have been used;

(af) storing a configuration of values of said jth column of bits (16b) for each of said configurations of values of said jth set of look-ahead bits (22b), said stored configuration of values of said jth column of bits (16b) providing a least combined difference value for a respective configuration of values of said jth set of look-ahead bits (22b);

(ag) letting j equal j+1;

(ah) repeating steps (t) through (ag) until j equals p+1;

(ai) assigning a stored configuration of values of a pth column of bits to said pth column of bits of said ith swath; and

(aj) assigning one of said stored configurations of values for a (p-1)th column of bits of said ith swath to said (p-1)th column of bits, said assigned configuration of values minimizing a combined difference value for a configuration of values of a (p-1)th set of look-ahead bits of said (p-1)th column of bits, said configuration of values of said (p-1)th set of look-ahead bits determined by said assigned configuration of values of said pth column of bits and said preset values of q-1 columns of said columns of non-image bits.

3. The method as recited in claim 2 further comprising:

(ak) assigning one of said stored configurations of values of an rth column of bits of said ith swath to said rth column of bits, said assigned configuration of values minimizing a combined difference value for a configuration of values of an rth set of look-ahead bits of said rth column of bits, said configuration of values of said rth set of look-ahead bits determined by a set of previously assigned values of an (r+1)th through an (r+k)th column of bits;

(al) assigning r equal to r-1; and

(am) repeating steps (ak) through (al) until r equals 0.

4. The method as recited in claim 3 further comprising:

(an) repeating steps (g) through (am) for a set of said swaths (14) of said sampled image (12).