EP0493101A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Image conversion
Assignee: Xerox Corp
•
Filing: 1991-12-23
•
Granted: —
•
Expires: 2011-12-23
Abstract
Abstract A method for optimal discrete rendering of images is disclosed. The present invention provides 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 trial 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.
Inventors
- 👤 Michael F. Plass
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-04 17:27
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/40; H04N1/405; H04N1/4051; G; G06; G06K; G06K15/00
Claims Analysis
Total Claims: 4
Claim 1
Independent Claim
551 words
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 the original image to form a sampled image (12); (e) constructing a plurality of parallel swaths (14) through the sampled image (12), each swath (14) being a linear path of adjacent bits, each path having width of n bits; (f) defining a linear array of columns of bits (16a, 16b, etc.) for each swath (14), each column (16) being n bits wide, with each column (16) for each swath (14) being numbered consecutively; (g) choosing a configuration of values of a first column of bits (16a) of an ith swath (14i) including a number (p) of columns of bits (16), and q columns of non-image bits having preset values (26); (h) determining a first set of look-ahead bits (22a) adjacent to the first column of bits (16a) and within the ith swath (14i), the first set of look-ahead bits (22a) including a set of k consecutive columns of bits of the ith swath (14i), the first set of look-ahead bits having a configuration of values; (i) applying the printer model (17a) to a first neighborhood (20a) around the first column of bits (16a) to provide a printed image of the first neighborhood (20a); (j) applying the perception model (17b) to a second neighborhood (18a) within the printed image of the first neighborhood (20a) around the first column of bits (16a) to provide a perceived image of the second neighborhood (18a); (k) applying the comparison model to compare the perceived image of the second neighborhood (18a) with the sampled image (12) of the second neighborhood (18a) to arrive at a difference value for each bit of a subset of columns of bits of the ith swath (14i) lying within the second neighborhood (18); (l) calculating a combined difference value from the difference values; (m) storing the combined difference value along with the configuration of values of the first column of bits (16); (n) altering the configuration of values of the first column of bits (16) of the ith swath (14i ); (o) repeating steps (i) through (n) 2n times until all of the configurations of values of the first column of bits (16) of tlhe ith swath (14i) have been used; (p) determining which of the configurations of values of the first column of bits (16) provides a least combined difference value for the configuration of values of the first set of look-ahead bits (22), by comparing the stored combined difference values; (q) altering the configuration of values of the first set of look-ahead bits (22) of the ith swath ( 14i); (r) repeating steps (i) through (q) up to 2n + k times until all of the configurations of values of the first set of look-ahead bits (22) of the ith swath (14i) have been used, and (s) storing a configuration of values of the first column of bits (16) for each of the configuration of values of the first set of look-ahead bits (22), the stored configuration of values of the first column of bits (16) providing a least combined difference value for a respective configuration of values of the first set of look-ahead bits (22).
Claim 2
Dependent Claim
565 words
The method as claimed in Claim 1, comprising the further steps of: (t) choosing a configuration of values of a jth column of bits (16b) of the ith swath (14i); (u) determining a jth set of look-ahead bits (22b) adjacent to the jth column of bits (16b) and within the ith swath (14i), the jth set of look-ahead bits (22b) including a set of k consecutive columns of bits of the ith swath (14i), the jth set of look-ahead bits (22b) having a configuration of values; (v) applying the printer model ( 17a) to a first neighborhood (20b) around the jth column of bits (16b) to provide a printed image of the first neighborhood (20b); (w) applying the perception model (17b) to a second neighborhood (18b) within the printed image of the first neighborhood (20b) around the jth column of bits (16b) to provide a perceived image of the second neighborhood (18b); (x) applying the comparison model to compare the perceived image of the second neighborhood (18b) with the sampled image (12) of the second neighborhood (18b) to arrive at a difference value for each bit of a subset of columns of bits of the ith swath (14i) lying within the second neighborhood (18b); (y) calculating a combined difference value from the difference values; (z) storing the combined difference value along with the configuration of values of the jth column of bits ( 16b); (aa) altering the configuration of values of the jth column of bits (16b) of the ith swath (14i); (ab) repeating steps (v) through (aa) 2n times until all of the configurations of values of the jth column of bits (16b) of the ith swath (14i) have been used; (ac) determining which of the configurations of values of te jth column of bits (16b) provides a least combined difference value for the values of the jth set of look-ahead bits (22b), by comparing the stored combined difference values; (ad) altering the configuration of the jth set of look-ahead bits (22b) of the ith swath (14i); (ae) repeating steps (v) through (ad) up to 2n + k times until all of the configurations of values of the jth set of look-ahead bits (22b) of the ith swath (14i) have been used; (af) storing a configuration of values of the jth column of bits (16b) for each of the configurations of values of the jth set of look-ahead bits (22b), the stored configuration of values of the jth column of bits (16b) providing a least combined difference value for a respective configuration of values of the jth set of look-ahead bits (22b) (ag) letting jequal 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 the pth column of bits of the ith swath, and (aj) assigning one of the stored configurations of values for a (p-1)th column of bits of the ith swath to the (p-1)th column of bits, the 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 the (p-1)th column of bits, the configuration of values of the (p-1)th set of look-ahead bits determined by the assigned configuration of values of the pth column of bits and the preset values of q-1 columns of the columns of non-image bits.
Claim 3
Independent Claim
113 words
The method as recited in Claim à further comprising: (ak) assigning one of the stored configurations of values of an rth column of bits of the ith swath to the rth column of bits, the assigned configuration of values minimizing a combined difference value for a configuration of values of an rth set of look-ahead bits of the rth column of bits, the configuration of values of the 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.
Claim 4
Dependent Claim
27 words
The method as recited in Claim 3 further comprising: (an) repeating steps (g) through (am) for a set of the swaths (14) of the sampled image (12).
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.