US6122407A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for producing threshold arrays using variance minimization and sparse image calculations
Assignee: Electronics for Imaging Inc
•
Filing: 1997-12-19
•
Granted: 2000-09-19
•
Expires: 2017-12-19
Abstract
Abstract A method and apparatus for creating threshold arrays having a minimized gray scale variance without geometric artifacts. The invention comprises the steps of processing each candidate pixel in the threshold array using a variance minimization technique and applying a sparse image calculation on the same pixel. The preferred embodiment of the invention comprises the application of a variance minimization technique on a threshold array. The threshold array is analyzed on a pixel-by-pixel basis. Each candidate pixel that is to be turned on is examined in relation to the previous pixels that already exist. The candidate pixel is examined to determine its effect on the variance of the smoothed gray level determined by the convolution of the pixel pattern with a smoothing kernel. The candidate pixel is also examined in relation to the distribution of the angles it forms with the previously selected pixels. The preferred embodiment uses a variant of the combinatorial Hough transform. In the preferred embodiment, there is an accumulator array for each not yet selected pixel that has a location for each of a quantified set of angles. A sum is stored in this location based on those previously selected pixels which make an angle with the not yet selected pixel which is discretized to the angle corresponding to that location. The effect of the true angle may be distributed over more than one location of the accumulator array and may depend on distance and angle. It is desired that a pixel is selected which combines a low variance of the smoothed gray level with a favorable distribution of values in its angle accumulator array. This process is repeated until all the pixels in the threshold array have been selected.
Inventors
- 👤 Michael Alan Peters
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 13:33
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/40; H04N1/405; H04N1/4051
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
128 words
Method for producing a threshold array, comprising the steps of: means for selecting a candidate pixel to be turned on in the threshold array; selecting a function representing the perceived binary pattern for a desired gray level; applying said binary function to said candidate pixel and all existing pixels in said threshold array to determine a variance between the value of each perceived pixel minus the average of all existing pixels; applying a pixel angle function to said candidate pixels and all previously selected pixels in said threshold array to determine a measure of collinearity with any other existing pixels; and turning said candidate pixel on if the sum of the variance and λ times the collinearity measure for said pixel is minimized, where λ is a parameter.
Claim 2
Dependent Claim
128 words
Method for producing a threshold array, comprising the steps of: means for selecting a candidate pixel to be turned on in the threshold array; selecting a function representing the perceived binary pattern for a desired gray level; applying said binary function to said candidate pixel and all existing pixels in said threshold array to determine a variance between the value of each perceived pixel minus the average of all existing pixels; applying a pixel angle function to said candidate pixels and all previously selected pixels in said threshold array to determine a measure of collinearity with any other existing pixels; and turning said candidate pixel on if the sum of the variance and λ times the collinearity measure for said pixel is minimized, where λ is a parameter.
Claim 3
Independent Claim
134 words
An apparatus for producing a threshold array, comprising: means for selecting a candidate pixel to be turned on in the threshold array; means for selecting a function representing the perceived binary pattern for a desired gray level; means for applying said binary function to said candidate pixel and all existing pixels in said threshold array to determine a variance between the value of each perceived pixel minus the average of all existing pixels; means for applying a pixel angle function to said candidate pixels and all previously selected pixels in said threshold array to determine a measure of collinearity with any other existing pixels; and means for turning said candidate pixel on if the sum of the variance and λ times the collinearity measure for said pixel is minimized, where λ is a parameter.
Claim 4
Independent Claim
134 words
An apparatus for producing a threshold array, comprising: means for selecting a candidate pixel to be turned on in the threshold array; means for selecting a function representing the perceived binary pattern for a desired gray level; means for applying said binary function to said candidate pixel and all existing pixels in said threshold array to determine a variance between the value of each perceived pixel minus the average of all existing pixels; means for applying a pixel angle function to said candidate pixels and all previously selected pixels in said threshold array to determine a measure of collinearity with any other existing pixels; and means for turning said candidate pixel on if the sum of the variance and λ times the collinearity measure for said pixel is minimized, where λ is a parameter.
Claim 5
Independent Claim
74 words
A method for creating a threshold array having a minimized gray scale variance, comprising the steps of: processing each of a plurality of candidate pixels in said threshold array using a variance minimization technique; and applying a pixel angle calculation on said candidate pixel; wherein said candidate pixel is examined to determine its effect on the variance of a smooth gray level determined by the convolution of a pixel pattern with a smoothing kernel.
Claim 6
Independent Claim
74 words
A method for creating a threshold array having a minimized gray scale variance, comprising the steps of: processing each of a plurality of candidate pixels in said threshold array using a variance minimization technique; and applying a pixel angle calculation on said candidate pixel; wherein said candidate pixel is examined to determine its effect on the variance of a smooth gray level determined by the convolution of a pixel pattern with a smoothing kernel.
Claim 7
Dependent Claim
23 words
The method of claim 3 further comprising the step of: analyzing each pixel in said threshold array on a pixel by pixel basis.
Claim 8
Dependent Claim
24 words
The method of claim 3 wherein said candidate pixel is examined in relation to a distribution of angles it forms with previously processed pixels.
Claim 9
Dependent Claim
18 words
The method of claim 5 wherein said distribution of angles is determined using a variant combinational Hough transform.
Claim 10
Dependent Claim
30 words
The method of claim 3 further comprising the step of: providing an accumulator array for each not-yet-processed pixel that has a location for each of a quantized set of angles.
Claim 11
Dependent Claim
45 words
The method of claim 7 further comprising the step of storing a sum in said accumulator array location based on those previously processed pixels which make an angle with said not-yet-processed pixel, wherein said not-yet-processed pixel is discretized to an angle corresponding to that location.
Claim 12
Dependent Claim
30 words
The method claim 8 wherein an effect of a true angle may be distributed over more than one location of said accumulator array and may depend upon distance and angle.
Claim 13
Dependent Claim
31 words
The method of claim 3 wherein a pixel is selected which combines a low variance of a smooth gray level with a favorable distribution of values in an angle accumulator array.
Claim 14
Independent Claim
75 words
A apparatus for creating a threshold array having a minimized gray scale variance, comprising: a threshold array in which each of a plurality of candidate pixels is processed using a variance minimization technique; and means for applying a pixel angle calculation on said candidate pixel; wherein said candidate pixel is examined to determine its effect on the variance of a smooth gray level determined by the convolution of a pixel pattern with a smoothing kernel.
Claim 15
Independent Claim
75 words
A apparatus for creating a threshold array having a minimized gray scale variance, comprising: a threshold array in which each of a plurality of candidate pixels is processed using a variance minimization technique; and means for applying a pixel angle calculation on said candidate pixel; wherein said candidate pixel is examined to determine its effect on the variance of a smooth gray level determined by the convolution of a pixel pattern with a smoothing kernel.
Claim 16
Dependent Claim
22 words
The apparatus of claim 11, further comprising: mean for analyzing each pixel in said threshold array on a pixel by pixel basis.
Claim 17
Dependent Claim
24 words
The apparatus of claim 11 wherein said candidate pixel is examined in relation to a distribution of angles it forms with previously processed pixels.
Claim 18
Dependent Claim
18 words
The apparatus of claim 13 wherein said distribution of angles is determined using a variant combinational Hough transform.
Claim 19
Dependent Claim
27 words
The apparatus of claim 11 further comprising: providing an accumulator array for each not-yet-processed pixel that has a location for each of a quantized set of angles.
Claim 20
Dependent Claim
42 words
The apparatus of claim 15 wherein a sum is stored in said accumulator array location based on those previously processed pixels which make an angle with said not-yet-processed pixel, wherein said not-yet-processed pixel is discretized to an angle corresponding to that location.
Claim 21
Dependent Claim
30 words
The apparatus claim 16 wherein an effect of a true angle may be distributed over more than one location of said accumulator array and may depend upon distance and angle.
Claim 22
Dependent Claim
31 words
The apparatus of claim 11 wherein a pixel is selected which combines a low variance of a smooth gray level with a favorable distribution of values in an angle accumulator array.
References Cited (Backward Citations)
US5111310A
Cited
US5708518A
Cited
US5726772A
Cited
EP0560285A1
Cited
US5526438A
Cited
EP0762734A2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-09-19 | 2004-03-20 | 2004-09-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-09-19 | 2008-03-20 | 2008-09-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-09-19 | 2012-03-20 | 2012-09-19 | $7700.00 | Window Closed / Lapsed |