Facsimile and static presentation processing – Static presentation processing – Attribute control
Reexamination Certificate
1999-09-24
2004-05-11
Lee, Thomas D. (Department: 2624)
Facsimile and static presentation processing
Static presentation processing
Attribute control
C358S448000
Reexamination Certificate
active
06734991
ABSTRACT:
BSCKGROUND OF THE INVENTION
The present invention is directed to the art of digital image processing and, more particularly, to a method and apparatus for determining a halftone line screen frequency estimate and a halftone line screen angle estimate at each pixel of an image scan formed of a plurality of pixels arranged in a regular array of fastscan pixel rows and slowscan pixel columns and will be described with particular reference thereto. However, it is to be understood that the present invention has broader application in many fields such as in calculating halftone line and screen frequency and angle estimates of a wide variety of digital images and other digital information or data.
Segmentation plays an important role in electronic image processing. In systems that rely on image segmentation, the detection of halftones in compound documents is very useful for image storage and processing. The accuracy of most halftone detection algorithms rests primarily on the ability of the system to determine an accurate estimate of halftone frequency. Accordingly, the art of estimating halftone frequencies has developed over the years.
Many halftone frequency estimate algorithms are available for detecting the halftone frequency of dot screens. One such algorithm commonly known as two dimensional peak detection finds isolated peak video values in a scanned image. The isolated peaks are detected as minimums and maximums (MIN/MAX) using a local criteria or other scheme. Essentially, in two-dimensional peak detection, the isolated peak count in a local area provides a measure of the halftone frequency for dot screen halftones.
Two-dimensional peak detection cannot be used, however, to determine the halftone frequency of line screens. Since line screens do not have isolated peaks as such, but rather, are formed of pulse-width modulated lines, two-dimensional peaks cannot be directly detected.
As a solution to the deficiencies of the above-described peak detection scheme, the auto-correlation function has been developed. In auto-correlation, a copy of the scanned image pattern is shifted along a first direction and compared with the unshifted scanned image itself acting as a “template” until a good match or correspondence is found. The shift distance along the first direction required to establish good correspondence between the unshifted image (template) and shifted image copy gives an indication of halftone line screen frequency in the first shift direction. Mathematically, the basic line frequency is determined by finding maxima of an inner product calculation taken between the unshifted image used as a template and the shifted image shifted in the first direction.
The use of the auto-correlation function to provide a line frequency estimate is somewhat expensive and difficult to implement. In addition, the auto-correlation function becomes very burdensome when the halftone pattern in the original document is either scanned at an angle or occurs naturally at an angle relative to the regular array of sensor rows and columns. The processing for determining the basic line frequency becomes much more difficult when the line frequency pattern in the scanned image is offset at an angle. In that case, the basic line frequency is determined using inner product calculations taken between the image and the image shifted in a first direction and also between the image and the image shifted in a second direction. The shifts in the first and second directions are necessary to provide a frequency estimate of halftone lines that occur at an angle relative to the array of pixel rows and columns in the scanned image. Accordingly, the processing required by the auto-correlation function is time consuming and expensive.
Further to the above, when the basic line frequency is not an integer multiple of the scan sampling frequency, an additional algorithm or layer of processing becomes necessary to detect the maxima of the inner product calculation taken between the image (template) and the one or more shifted image copies. Essentially, the additional layer of processing must be able to detect “flat” peak areas in the interference pattern between the shifted and the unshifted image as peaks in the original image.
Accordingly, it would be desirable to provide a relatively simple method and apparatus for determining frequency estimates of halftone line patterns that overcomes the problems and processing complexities that are present in the prior art schemes.
It would further be desirable to extend some basic concepts used in the scheme for determining halftone dot frequency estimates for novel use in determining halftone line frequency estimates.
It would still further be desirable to extend portions of the basic scheme used to determine halftone dot frequency estimates for use in a novel way for determining an estimate of an angle of halftone lines in a scanned image.
The present invention contemplates a new and improved method and apparatus for determining halftone line frequency estimates using MIN/MAX detection which overcomes the above-referenced problems and others.
SUMMARY OF THE INVENTION
In accordance with one aspect of the present invention, one-dimensional peak detection algorithms are used in first and second directions of interest to locate local maximas (MAXs) and local minimas (MINs). For each pixel in the scanned image, an overall line screen frequency estimate is determined from the sum of the squares of the line frequencies taken in the first and second directions.
In accordance with a more limited aspect of the present invention, for each pixel in the scanned image an overall line screen angle estimate is determined from the arctangent of the ratio of a first direction frequency estimate to a second direction frequency estimate.
In accordance with a still more limited aspect of the invention, one-dimensional peak detection algorithms are used in vertical and horizontal scanned image directions to locate the local maximas (MAXs) and the local minimas (MINs). The overall line screen frequency estimate for each scanned image pixel is determined from the sum of the squares of the line frequencies taken in the vertical and horizontal scanned image directions. The overall line screen angle estimate is determined at each scanned image pixel from the arctangent of the ratio between the vertical and horizontal scanned image direction frequencies.
In accordance with yet a still more limited aspect of the invention, one-dimensional peak detection algorithms are used in the fastscan and slowscan directions to locate local maximas and local minimas. The overall line screen frequency estimate is determined at each scanned image pixel from the sum of the squares of the line frequencies of the fastscan and slowscan directions. The overall line screen frequency angle estimate is determined at each scanned image pixel from the arctangent of the ratio between the fastscan and slowscan direction frequency estimates.
One advantage of the present invention is that halftone line frequency estimates are determined using relatively simple and inexpensive one-dimensional MIN/MAX peak detection algorithms. This reduces the cost of estimate processing overhead and enables a simple implementation.
Another advantage of the present invention is that the halftone line frequency angle estimates are determined using the same relatively simple and inexpensive one-dimensional MIN/MAX peak detection algorithms that are used to provide the halftone line frequency estimates. Again, the processing overhead costs are reduced and simple implementation is enabled.
REFERENCES:
patent: 5200821 (1993-04-01), Haghiri et al.
patent: 5293430 (1994-03-01), Shiau et al.
patent: 5621519 (1997-04-01), Frost et al.
patent: 5822470 (1998-10-01), Vehvilainen
Brinich Stephen
Lee Thomas D.
Xerox Corporation
LandOfFree
Method and apparatus for determining halftone line frequency... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for determining halftone line frequency..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determining halftone line frequency... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3230515