US5500744A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and appparatus for image scaling using parallel incremental interpolation
Assignee: Bayer Corp
•
Filing: 1994-08-05
•
Granted: 1996-03-19
•
Expires: 2014-08-05
Abstract
Abstract A method and apparatus for image scaling of continuous tone images to be rasterized and output to a recording or imaging device using incremental interpolation. The method employs multiple parallel interpolators, each of which contains an accumulation sum to which an accumulation constant is added. When each accumulation sum exceeds a reference value, a transition event is signaled, to be used for selection of contone image data value for processing. By initially loading the accumulation sums with shifted data and employing interpolation logic, multiple transition events can be calculated within one output resolution processing cycle.
Inventors
- 👤 Jerrold Sabath
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 16:25
CPC Classifications
G; G06; G06T; G06T3/00; G06T3/40; G06T3/4007; H; H04; H04N; H04N1/00; H04N1/40; H04N1/405; H04N1/4055
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
215 words
A method for IMAGE SCALING and HALFTONE PROCESSING of HALFTONE PIXELS corresponding to a CONTONE IMAGE having a CONTONE RESOLUTION, said method comprising the following steps: (A) Using the CONTONE RESOLUTION of said CONTONE IMAGE together with an OUTPUT RESOLUTION to obtain an ACCUMULATION CONSTANT and a TRANSITION VALUE; (B) Determining an initial value for each of a plurality of ACCUMULATION SUMS; (C) Selecting a CONTONE DATA VALUE for each of said plurality of ACCUMULATION SUMS; (D) Identifying a HALFTONE PIXEL corresponding to each of said plurality of ACCUMULATION SUMS; (E) Performing HALFTONE PROCESSING for each of said identified HALFTONE PIXELS using said selected CONTONE DATA VALUES; (F) Adding said ACCUMULATION CONSTANT to each of said plurality of ACCUMULATION SUMS thereby generating new values for each of said plurality of ACCUMULATION SUMS; (G) Determining a TRANSITION EVENT for each of said new values for each of said plurality of ACCUMULATION SUMS; (H) Using said TRANSITION EVENTS together with said TRANSITION VALUE to determine an adjusted value for each of said plurality of ACCUMULATION SUMS; (I) Using said TRANSITION EVENTS to select one or more CONTONE DATA VALUES of said CONTONE IMAGE for processing; and, (J) Repeating steps (D) through (I) until HALFTONE PROCESSING has been completed for all HALFTONE PIXELS corresponding to said CONTONE IMAGE.
Claim 2
Independent Claim
215 words
A method for IMAGE SCALING and HALFTONE PROCESSING of HALFTONE PIXELS corresponding to a CONTONE IMAGE having a CONTONE RESOLUTION, said method comprising the following steps: (A) Using the CONTONE RESOLUTION of said CONTONE IMAGE together with an OUTPUT RESOLUTION to obtain an ACCUMULATION CONSTANT and a TRANSITION VALUE; (B) Determining an initial value for each of a plurality of ACCUMULATION SUMS; (C) Selecting a CONTONE DATA VALUE for each of said plurality of ACCUMULATION SUMS; (D) Identifying a HALFTONE PIXEL corresponding to each of said plurality of ACCUMULATION SUMS; (E) Performing HALFTONE PROCESSING for each of said identified HALFTONE PIXELS using said selected CONTONE DATA VALUES; (F) Adding said ACCUMULATION CONSTANT to each of said plurality of ACCUMULATION SUMS thereby generating new values for each of said plurality of ACCUMULATION SUMS; (G) Determining a TRANSITION EVENT for each of said new values for each of said plurality of ACCUMULATION SUMS; (H) Using said TRANSITION EVENTS together with said TRANSITION VALUE to determine an adjusted value for each of said plurality of ACCUMULATION SUMS; (I) Using said TRANSITION EVENTS to select one or more CONTONE DATA VALUES of said CONTONE IMAGE for processing; and, (J) Repeating steps (D) through (I) until HALFTONE PROCESSING has been completed for all HALFTONE PIXELS corresponding to said CONTONE IMAGE.
Claim 3
Dependent Claim
42 words
The method of claim 1 wherein the TRANSITION VALUE is unity and the ACCUMULATION CONSTANT is a factor M times a SCALE FACTOR relating said CONTONE RESOLUTION to said OUTPUT RESOLUTION, said factor M being equal to the number of ACCUMULATION SUMS.
Claim 4
Dependent Claim
13 words
The method of claim 2 wherein said SCALE FACTOR is less than one.
Claim 5
Dependent Claim
26 words
The method of claim 1 wherein the number of ACCUMULATION SUMS can be expressed as an integer power of two, said integer being one or greater.
Claim 6
Dependent Claim
13 words
The method of claim 4 wherein the number of ACCUMULATION SUMS is two.
Claim 7
Dependent Claim
28 words
The method of claim 5 wherein the TRANSITION VALUE is unity and the ACCUMULATION CONSTANT is twice a SCALE FACTOR relating said CONTONE RESOLUTION to said OUTPUT RESOLUTION.
Claim 8
Independent Claim
202 words
A method for INCREMENTAL INTERPOLATION to generate a sequence of events occurring at a first frequency from a sequence of events occurring at a second frequency, said method comprising the following steps: (A) Using said first frequency together with said second frequency to obtain an ACCUMULATION CONSTANT and a TRANSITION VALUE; (B) Determining initial values for each of a plurality of ACCUMULATION SUMS; (C) Selecting an event of said first sequence of events for each of said plurality of ACCUMULATION SUMS; (D) Selecting an event of said second sequence of events corresponding to each of said ACCUMULATION SUMS; (E) Adding said ACCUMULATION CONSTANT to each of said plurality of ACCUMULATION SUMS thereby generating new values for each of said plurality of ACCUMULATION SUMS; (F) Determining a TRANSITION EVENT for each of said new values for each of said plurality of ACCUMULATION SUMS; (G) Using said TRANSITION EVENTS together with said TRANSITION VALUE to determine an adjusted value for each of said plurality of ACCUMULATION SUMS; (H) Using said TRANSITION EVENTS to select one or more events of said first frequency sequence of events, and, (I) Repeating steps (D) through (H) until all events of said first frequency sequence of events have occurred.
Claim 9
Independent Claim
202 words
A method for INCREMENTAL INTERPOLATION to generate a sequence of events occurring at a first frequency from a sequence of events occurring at a second frequency, said method comprising the following steps: (A) Using said first frequency together with said second frequency to obtain an ACCUMULATION CONSTANT and a TRANSITION VALUE; (B) Determining initial values for each of a plurality of ACCUMULATION SUMS; (C) Selecting an event of said first sequence of events for each of said plurality of ACCUMULATION SUMS; (D) Selecting an event of said second sequence of events corresponding to each of said ACCUMULATION SUMS; (E) Adding said ACCUMULATION CONSTANT to each of said plurality of ACCUMULATION SUMS thereby generating new values for each of said plurality of ACCUMULATION SUMS; (F) Determining a TRANSITION EVENT for each of said new values for each of said plurality of ACCUMULATION SUMS; (G) Using said TRANSITION EVENTS together with said TRANSITION VALUE to determine an adjusted value for each of said plurality of ACCUMULATION SUMS; (H) Using said TRANSITION EVENTS to select one or more events of said first frequency sequence of events, and, (I) Repeating steps (D) through (H) until all events of said first frequency sequence of events have occurred.
Claim 10
Dependent Claim
42 words
The method of claim 7 wherein the TRANSITION VALUE is unity and the ACCUMULATION CONSTANT is a factor M times a SCALE FACTOR relating said CONTONE RESOLUTION to said OUTPUT RESOLUTION, said factor M being equal to the number of ACCUMULATION SUMS.
Claim 11
Dependent Claim
13 words
The method of claim 8 wherein said SCALE FACTOR is less than one.
Claim 12
Dependent Claim
26 words
The method of claim 7 wherein the number of ACCUMULATION SUMS can be expressed as an integer power of two, said integer being one or greater.
Claim 13
Dependent Claim
13 words
The method of claim 10 wherein the number of ACCUMULATION SUMS is two.
Claim 14
Dependent Claim
28 words
The method of claim 11 wherein the TRANSITION VALUE is unity and the ACCUMULATION CONSTANT is twice a SCALE FACTOR relating said first frequency to said second frequency.
Claim 15
Independent Claim
65 words
The method of claims 1 or 7 wherein the TRANSITION VALUE is 2 n where n<N and N is the number of bits of precision of a data word representing said TRANSITION VALUE, said TRANSITION EVENT is generated by setting the nth bit of said data word, and said adjustment of said ACCUMULATION SUM is accomplished by resetting said nth bit of said data word.
Claim 16
Independent Claim
82 words
The method of claims 1 or 7 wherein the TRANSITION VALUE is 2 N where N is the number of bits of precision of a data word representing said TRANSITION VALUE, said TRANSITION EVENT is generated by setting a carry bit indicating overflow of said data word, said adjustment of said ACCUMULATION SUMS is performed by resetting said carry bit of said data word, the remaining N bits of said data word representing said new initial value for the corresponding ACCUMULATION SUM.
Claim 17
Dependent Claim
49 words
The method of claim 1 wherein said TRANSITION EVENT is generated for each of said plurality of ACCUMULATION SUMS by comparison of a first designated bit of each of said plurality of ACCUMULATION SUMS with that of a second designated bit of one of said plurality of ACCUMULATION SUMS.
Claim 18
Dependent Claim
48 words
The method of claim 15 wherein said TRANSITION EVENT is generated for each of said plurality of ACCUMULATION SUMS by forming an EXCLUSIVE OR of a designated bit of each of said plurality of ACCUMULATION SUMS with the same bit of another of said plurality of ACCUMULATION SUMS.
Claim 19
Dependent Claim
47 words
The method of claim 15 wherein said comparison occurs between a first designated bit of at least one of said plurality of ACCUMULATION SUMS and that of a second designated bit of at least one of said plurality of ACCUMULATION SUMS occurring in a previous processing iteration.
Claim 20
Independent Claim
203 words
An apparatus for IMAGE SCALING and HALFTONE PROCESSING of HALFTONE PIXELS corresponding to a CONTONE IMAGE having a CONTONE RESOLUTION, said apparatus comprising: (A) Means for obtaining an ACCUMULATION CONSTANT and a TRANSITION VALUE using the CONTONE RESOLUTION of said CONTONE IMAGE together with the OUTPUT RESOLUTION of an OUTPUT DEVICE; (B) Means for determining initial values for each of a plurality of ACCUMULATION SUMS; (C) Means for selecting a CONTONE DATA VALUE for each of said plurality of ACCUMULATION SUMS; (D) Means for identifying a HALFTONE PIXEL corresponding to each of said plurality of ACCUMULATION SUMS; (E) Means for HALFTONE PROCESSING for each of said identified HALFTONE PIXELS using said selected CONTONE DATA VALUES; (F) Means for adding said ACCUMULATION CONSTANT to each of said plurality of ACCUMULATION SUMS thereby generating new values for each of said plurality of ACCUMULATION SUMS; (G) Means for determining a TRANSITION EVENT for each of said new values for each of said plurality of ACCUMULATION SUMS; (H) Means for determining an adjusted value for each of said plurality of ACCUMULATION SUMS using said TRANSITION EVENTS with said TRANSITION VALUE; and, (I) Means for selecting one or more CONTONE DATA VALUES of said CONTONE IMAGE for processing.
Claim 21
Independent Claim
203 words
An apparatus for IMAGE SCALING and HALFTONE PROCESSING of HALFTONE PIXELS corresponding to a CONTONE IMAGE having a CONTONE RESOLUTION, said apparatus comprising: (A) Means for obtaining an ACCUMULATION CONSTANT and a TRANSITION VALUE using the CONTONE RESOLUTION of said CONTONE IMAGE together with the OUTPUT RESOLUTION of an OUTPUT DEVICE; (B) Means for determining initial values for each of a plurality of ACCUMULATION SUMS; (C) Means for selecting a CONTONE DATA VALUE for each of said plurality of ACCUMULATION SUMS; (D) Means for identifying a HALFTONE PIXEL corresponding to each of said plurality of ACCUMULATION SUMS; (E) Means for HALFTONE PROCESSING for each of said identified HALFTONE PIXELS using said selected CONTONE DATA VALUES; (F) Means for adding said ACCUMULATION CONSTANT to each of said plurality of ACCUMULATION SUMS thereby generating new values for each of said plurality of ACCUMULATION SUMS; (G) Means for determining a TRANSITION EVENT for each of said new values for each of said plurality of ACCUMULATION SUMS; (H) Means for determining an adjusted value for each of said plurality of ACCUMULATION SUMS using said TRANSITION EVENTS with said TRANSITION VALUE; and, (I) Means for selecting one or more CONTONE DATA VALUES of said CONTONE IMAGE for processing.
Claim 22
Dependent Claim
16 words
The apparatus of claim 18 wherein said accumulation means is a plurality of SERIAL PIPELINED INTERPOLATORS.
Claim 23
Dependent Claim
15 words
The apparatus of claim 18 wherein said OUTPUT RESOLUTION is greater than said CONTONE RESOLUTION.
Claim 24
Dependent Claim
26 words
The apparatus of claim 18 wherein the number of ACCUMULATION SUMS can be expressed as an integer power of two, said integer being one or greater.
Claim 25
Dependent Claim
13 words
The apparatus of claim 21 wherein the number of ACCUMULATION SUMS is two.
Claim 26
Independent Claim
188 words
An apparatus for INCREMENTAL INTERPOLATION for generating a sequence of events at a first frequency from a sequence of events occurring at a second frequency, said apparatus comprising: (A) Means for obtaining an ACCUMULATION CONSTANT and a TRANSITION VALUE using said first frequency together with said second frequency; (B) Means for determining initial values for each of a plurality of ACCUMULATION SUMS; (C) Means for selecting an event of said first sequence of events for each of said plurality of ACCUMULATION SUMS; (D) Means for selecting an event of said second sequence of events corresponding to each of said ACCUMULATION SUMS; (E) Means for adding said ACCUMULATION CONSTANT to each of said plurality of ACCUMULATION SUMS thereby generating new values for each of said plurality of ACCUMULATION SUMS; (F) Means for determining a TRANSITION EVENT for each of said new values for each of said plurality of ACCUMULATION SUMS; (G) Means for determining an adjusted value for each of said plurality of ACCUMULATION SUMS using said TRANSITION EVENTS with said TRANSITION VALUE; and, (H) Means for selecting one or more events of said first frequency sequence of events.
Claim 27
Independent Claim
188 words
An apparatus for INCREMENTAL INTERPOLATION for generating a sequence of events at a first frequency from a sequence of events occurring at a second frequency, said apparatus comprising: (A) Means for obtaining an ACCUMULATION CONSTANT and a TRANSITION VALUE using said first frequency together with said second frequency; (B) Means for determining initial values for each of a plurality of ACCUMULATION SUMS; (C) Means for selecting an event of said first sequence of events for each of said plurality of ACCUMULATION SUMS; (D) Means for selecting an event of said second sequence of events corresponding to each of said ACCUMULATION SUMS; (E) Means for adding said ACCUMULATION CONSTANT to each of said plurality of ACCUMULATION SUMS thereby generating new values for each of said plurality of ACCUMULATION SUMS; (F) Means for determining a TRANSITION EVENT for each of said new values for each of said plurality of ACCUMULATION SUMS; (G) Means for determining an adjusted value for each of said plurality of ACCUMULATION SUMS using said TRANSITION EVENTS with said TRANSITION VALUE; and, (H) Means for selecting one or more events of said first frequency sequence of events.
Claim 28
Dependent Claim
28 words
The apparatus of claim 23 wherein said means for adding said ACCUMULATION CONSTANT to each of said plurality of ACCUMULATION SUMS comprises a plurality of SERIAL PIPELINED INTERPOLATORS.
Claim 29
Dependent Claim
15 words
The apparatus of claim 23 wherein said second frequency is greater than said first frequency.
Claim 30
Dependent Claim
26 words
The apparatus of claim 23 wherein the number of ACCUMULATION SUMS can be expressed as an integer power of two, said integer being one or greater.
Claim 31
Dependent Claim
13 words
The apparatus of claim 26 wherein the number of ACCUMULATION SUMS is two.
Claim 32
Dependent Claim
77 words
The apparatus of claim 22 wherein said means for determining a TRANSITION EVENT produces even and odd TRANSITION EVENTS and wherein said means for selecting a CONTONE DATA VALUE comprises: (A) A pixel select state machine means responsive to said even and odd TRANSITION EVENTS for producing a plurality of control signals; and, (B) Pixel select logic means responsive to said plurality of control signals and to CONTONE DATA VALUES for producing even and odd CONTONE PIXELS.
Claim 33
Dependent Claim
53 words
The apparatus of claim 28 Wherein said pixel select state machine means uses the current state of said pixel select state machine means together with said even and odd TRANSITION EVENTS to produce the next state of said pixel select state machine means and control signals for controlling said pixel select logic means.
References Cited (Backward Citations)
US5187594A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-03-19 | 1999-09-18 | 2000-03-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-03-19 | 2003-09-18 | 2004-03-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-03-19 | 2007-09-18 | 2008-03-19 | $7700.00 | Window Closed / Lapsed |