Method and apparatus for determining halftone line frequency estimates using MIN/MAX detection

• US 6,734,991 B1
• Filed: 09/24/1999
• Issued: 05/11/2004
• Est. Priority Date: 09/24/1999
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Schweid, Stuart A.
• Primary Examiner(s): Lee, Thomas D.
• Assistant Examiner(s): BRINICH, STEPHEN M
• Application Number:
  US09/405,928
• Time in Patent Office: 1,691 Days
• Field of Search: 358/1.9, 358/1.8, 358/3-7-, 358/3.14, 358/3.13, 358/3--, 358/448, 382/237
• US Class Current: 358/3.06
• CPC Class Codes: H04N 1/40062 Discrimination between different image types, e.g. two-tone, continuous tone
• CPC Class Codes: H04N 1/40075 Descreening, i.e. converting a halftone signal into a corresponding continuous-tone signal; Rescreening, i.e. combined descreening and halftoning

Abstract

A method and apparatus is provided for determining a halftone line screen frequency estimate f at a pixel of interest in an image formed of a plurality of pixels arranged in a regular array of rows and columns. A first single dimensional line screen frequency estimate f_H is determined based on video values of a first set of pixels in a row of pixels in the scanned image. Next, a second single dimensional line screen frequency estimate f_V is determined based on video values of a second set of pixels in a column of pixels in the scanned image. A two-dimensional halftone line screen frequency estimate f is calculated at each pixel of interest based on a norm of the first single dimensional line screen frequency estimate f_H and on the second single dimensional line screen frequency estimate f_V. A halftone line screen angle estimate a is calculated at each pixel of interest based on an arctangent of the ratio between the first and second single dimensional line screen frequency estimates. Maxima and minima (MIN/MAX) extrema peak detection is used in fastscan and slowscan directions to determine the first and second single dimensional frequency estimates. False peak detection is prevented in the MIN/MAX detection scheme.

Claims

1. A method of determining a halftone line frequency estimate f at each pixel V(i) of an image formed of a plurality of pixels arranged in a plurality of fastscan pixel rows and slowscan pixel columns, the method comprising the steps of:

for each fastscan pixel row of said image;

identifying a set of fastscan maxima extrema pixels having a video value greater than selected neighboring fastscan direction pixels; and

,

identifying a set of fastscan minima extrema pixels having a video value less than selected neighboring fastscan direction pixels;

for each slowscan pixel column of said image;

identifying a set of slowscan maxima extrema pixels having a video value greater than selected neighboring slowscan direction pixels; and

,

identifying a set of slowscan minima extrema pixels having a video value less than selected neighboring slowscan direction pixels;

for each pixel of said image;

generating a fastscan maxima extrema frequency value f_Hx based on a quantity of neighboring of fastscan maxima extrema pixels;

generating a fastscan minima extrema frequency value f_Hn based on a quantity of neighboring fastscan minima extrema pixels;

generating a slowscan maxima extrema frequency value f_Vx based on a quantity of neighboring slowscan maxima extrema pixels; and

,

generating a slowscan minima extrema frequency value f_VN based on a quantity of neighboring slowscan minima extrema pixels;

for each pixel of said image;

generating a halftone fastscan frequency estimate f_H by selecting the greater between the fastscan maxima extrema frequency value f_Hx at said each pixel and the fastscan minima extrema frequency value f_Hn at said each pixel; and

,

generating a halftone slowscan frequency estimate f_V by selecting the lesser between the slowscan maxima extrema frequency value f_Vx at said each pixel and the slowscan minima extrema frequency value f_Vn at said each pixel; and

,

for each pixel, determining a halftone line frequency estimate f based on a norm of said halftone fastscan frequency estimate f_H and said halftone slowscan frequency estimate f_V.

2. The method of determining a halftone line frequency estimate f according to claim 1 wherein:

the step of identifying the set of fastscan maxima extrema pixels includes identifying said set of fastscan maxima pixels having a video value greater than at least four neighboring fastscan direction pixels;

the step of identifying said set of fastscan minima extrema pixels includes identifying said set of fastscan minima extrema pixels having a video value less than at least four selected neighboring fastscan direction pixels;

the step of identifying said set of slowscan maxima extrema pixels includes identifying said set of slowscan maxima extrema pixels having a video value greater than at least four selected neighboring slowscan direction pixels; and

,

the step of identifying said set of slowscan minima extrema pixels includes the step of identifying said set of slowscan minima extrema pixels having a video value less than at least four selected neighboring slowscan direction pixels.

3. The method of determining a halftone line frequency estimate f according to claim 2 wherein:

the step of determining said set of fastscan maxima extrema pixels includes the step of, for each pixel V(i) of said each fastscan pixel row of said image, determining whether said each pixel is a one of said set of fastscan maxima extrema pixels according to;

4. A method of estimating a halftone line screen frequency f at a pixel of interest in an image formed of a plurality of pixels having video values, the method comprising the steps of:

determining a first single dimensional frequency estimate f_H based on video values of a first set of pixels forming a row of pixels in said image including said pixel of interest;

determining a second single dimensional frequency estimate f_V based on video values of a second set of pixels forming a column of pixels in said image including said pixel of interest; and

,

calculating said halftone line screen frequency estimate f at said pixel of interest based on a norm of said first single dimensional frequency estimate f_H and said second single dimensional frequency estimate f_V.

5. The method according to claim 4 wherein:

the step of determining said first single dimensional frequency estimate f_H includes determining a first maxima extrema frequency estimate f_HX and a first minima extrema frequency estimate f_HN based on peak video values among said first set of pixels in said row of pixels; and

,

the step of determining said second single dimensional frequency estimate f_V includes determining a second maxima extrema frequency estimate f_VX and a second minima extrema frequency estimate f_VN based on peak video values among said second set of pixels in said column of pixels.

6. The method according to claim 5 wherein:

the step of determining said first single dimensional frequency estimate f_H includes selecting the greater of said first maxima extrema frequency estimate f_HX and said first minima extrema frequency estimate f_HN as said first single dimensional frequency estimate f_H according to f_H=max(f_HX, f_HN); and

,

the step of determining said second single dimensional frequency estimate f_V includes selecting the greater of said second maxima extrema frequency estimate f_VX and said second minima extrema frequency estimate f_VN as said second single dimensional frequency estimate f_V according to f_V=max(f_VX, f_VN).

7. The method according to claim 6 wherein the step of calculating said halftone line screen frequency estimate f includes calculating said halftone line screen frequency estimate f at said pixel of interest based on said norm of said first single dimensional frequency estimate f_H and said second single dimensional frequency estimate f_V according to f={square root over (f_H²+f_V²)}.

8. The method according to claim 6 further including the step of determining a halftone line screen angle estimate α

at said pixel of interest based on a ratio between said first single dimensional frequency estimate f_H and said second single dimensional frequency estimate f_V.

9. The method according to claim 8 wherein the step of determining said halftone line screen angle estimate α

at includes calculating said halftone line screen angle estimate at based on said ratio between first single dimensional frequency estimate f_H and said second single dimensional frequency estimate f_V according to α

=arctan(f_V/f_H).

10. The method according to claim 5 wherein:

the step of determining said first maxima extrema frequency estimate includes determining said first maxima extrema frequency estimate based on a video value of said pixel of interest relative to said video values of said first set of pixels forming said row of pixels in said image and relative to a predetermined noise value to prevent false video peak detection due to noise in said image;

determining said first minima extrema frequency estimate includes determining said first minima extrema frequency estimate based on said video value of said pixel of interest relative to said video values of said first set of pixels forming said row of pixels in said image and relative to said predetermined noise value to prevent false video peak detection due to noise in said image;

the step of determining said second maxima extrema frequency estimate includes determining said second maxima extrema frequency estimate based on said video value of said pixel of interest relative to said video values of said second set of pixels forming said column of pixels in said image and relative to said predetermined noise value to prevent false video peak detection due to noise in said image; and

, the step of determining said second minima extrema frequency estimate includes determining said second minima extrema frequency estimate based on said video value of said pixel of interest relative to said video values of said second set of pixels forming said column of pixels in said image and relative to said predetermined noise value to prevent false video peak detection due to noise in said image.

11. The method according to claim 5 wherein:

the step of determining said first single dimensional frequency estimate includes calculating said first single dimensional frequency estimate to prevent false shallow peak detection due to a first peak video value proximate a second substantially larger peak video value in said image and,

the step of determining said second single dimensional frequency estimate includes calculating said second single dimensional frequency estimate to prevent said false shallow peak detection due to a third peak video value proximate a fourth substantially larger peak video value in said image.

12. The method according to claim 5 wherein:

the step of determining said first single dimensional frequency estimate includes calculating said first single dimensional frequency estimate to prevent false flat peak detection due to a first peak video value proximate one or more second substantially similar peak video values in said image; and

,

the step of determining said second single dimensional frequency estimate includes calculating said second single dimensional frequency estimate to prevent said false flat peak detection due to a third peak video value proximate one or more fourth substantially similar peak video values in said image.

13. The method according to claim 4 further including determining a halftone line frequency estimate f_V(i) for each pixel the V(i) in said image.

14. The method according to claim 13 wherein the step of determining said halftone line frequency estimate f_V(i) includes the steps of, for each pixel V(i):

determining an estimated first single dimensional frequency estimate f_HV(i) based on a video value of a first set of pixels v(i−

1)_H . . . v(i+2)_H.

15. An apparatus for estimating a halftone line screen frequency f at a pixel of interest in an image formed of a plurality of pixels having video values, the apparatus comprising:

a fastscan frequency estimator circuit for determining a first single frequency estimate f_H based on video values of a first set of pixels forming a row of pixels in said image including said pixel of interest;

a slowscan frequency estimator circuit for determining a second single dimensional frequency estimate f_V based on video values of a second set of pixels forming a column of pixels in said image including said pixel of interest; and

,

a halftone line frequency estimator circuit for calculating said halftone line screen frequency estimate f at said pixel of interest based on a norm of said first single dimensional frequency estimate f_H and said second single dimensional frequency estimate f_V.

16. The apparatus according to claim 15 further including:

a first fastscan localized frequency estimator circuit for determining a first maxima extrema frequency estimate f_HX based on peak video values among said first set of pixels in said row of pixels;

a second fastscan localized frequency estimator circuit for determining a first minima extrema frequency estimate f_HN based on peak video values among said first set of pixels in said row of pixels;

a first slowscan localized frequency estimator circuit for determining a second maxima extrema frequency estimate f_VX based on peak video values among said second set of pixels in said column of pixels, and

a second slowscan localized frequency estimator circuit for determining a second minima extrema frequency estimate f_VN based on peak video values among said second set of pixels in said column of pixels.

17. The apparatus according to claim 16 wherein:

said first fastscan localized frequency estimator circuit includes means for determining said first maxima extrema frequency estimate based on a video value of said pixel of interest relative to said video values of said first set of pixels forming said row of pixels in said image and relative to a predetermined noise value to prevent false video peak detection due to noise in said image;

said second fastscan localized frequency estimator circuit includes means for determining said first minima extrema frequency estimate based on said video value of said pixel of interest relative to said video values of said first set of pixels forming said row of pixels in said image and relative to said predetermined noise value to prevent false video peak detection due to noise in said image;

said first slowscan localized frequency estimator circuit includes means for determining said second maxima extrema frequency estimate based on said video value of said pixel of interest relative to said video values of said second set of pixels forming said column of pixels in said image and relative to said predetermined noise value to prevent false video peak detection due to noise in said image; and

,

said second slowscan localized frequency estimator circuit includes means for determining said second minima extrema frequency estimate based on said video value of said pixel of interest relative to said video value of said second set of pixels forming said column of pixels in said image and relative to said predetermined noise value to prevent false video peak detection due to noise in said image.

18. The apparatus according to claim 16 wherein:

said fastscan frequency estimator circuit includes means for calculating said first single dimensional frequency estimate to prevent false shallow peak detection due to a first peak video value proximate a second substantially larger peak video value in said image; and

,

said slowscan frequency estimator circuit includes means for calculating said second single dimensional frequency estimate to prevent said false shallow peak detection due to a third peak video value proximate a fourth substantially larger peak video value in said image.

19. The apparatus according to claim 16 wherein:

said fastscan frequency estimator circuit includes means for calculating said first single dimensional frequency estimate to prevent false flat peak detection due to a first peak video value proximate one or more second substantially similar peak video values in said image; and

,

said slowscan frequency estimator circuit includes means for calculating said second single dimensional frequency estimate to prevent said false flat peak detection due to a third peak video value proximate one or more fourth substantially similar peak video values in said image.

20. The apparatus according to claim 15 further including a halftone line angle estimator circuit for determining a halftone line screen angle estimate α

at said pixel of interest based on a ratio between said first single dimensional frequency estimate f_H and said single dimensional frequency estimate f_V.