Image analysis – Image transformation or preprocessing – Changing the image coordinates
Reexamination Certificate
1999-04-29
2001-11-13
Boudreau, Leo (Department: 2621)
Image analysis
Image transformation or preprocessing
Changing the image coordinates
C345S440000, C358S451000
Reexamination Certificate
active
06317524
ABSTRACT:
BACKGROUND OF THE INVENTION
A process and circuit for resampling and resizing a digital image where each iteration converts each n pixels on a scan line to an average pixel to resample to 1
in the horizontal direction, and outputs one scan line for every n, plus or minus a small percentage, input scan lines to resample and resize the image in the vertical direction.
It is frequently necessary to change the size of an image slightly. For example, deleting alternate pixels will reduce an image to one half, and duplicating pixels will double the image size. To change image size by less than a multiple of two, an algorithm such as the nearest neighbor algorithm can be used to produce the necessary number of pixels.
It may also be necessary to resample image pixels. For example, if an image is scanned in on a scanner of higher pixel density and is to be processed or printed at a lower pixel density, conversion to a lower number of pixels per inch is required.
However, if image pixels are deleted in either of these processes, data will be lost. To minimize this, the pixels can be averaged first. That is, a number of pixels can be replaced by one average pixel.
The result of these operations is an image that is resampled and changed slightly in size while losing a minimum of image quality.
This process can be used in color copiers, as a first step in the prevention of counterfeiting. In its simplest form, paper currency can be counterfeited by placing it on the platen and copying it. To prevent this, currency has marks of various sizes, shapes and colors. The image output of the scanner can be analyzed, and the copying discontinued if a currency mark of a particular size is found by a currency detection circuit in the copier. To defeat this detection, a counterfeiter may set the scanner to magnify the image size enough so that the marks will not be recognized by the currency detector, and then reduce the image by the same amount when printing.
To prevent this, the detection circuit must be supplied with a number corresponding to the amount of magnification (or reduction) that the scanner was set to, and must reduce (increase) the image size by the same amount before testing for currency marks.
Additionally, the pixel density of the image is greater than that needed by the detection circuit, so the data is resampled first. With the addition of the averaging of the image pixels, the total process becomes averaging, sizing and resampling.
The final problem is that of circuit speed. When an original of any kind is placed on the platen, the copier can not start to print until the test for currency is complete, and since this test must be done for every original, the elapsed time must be as short as possible. There is therefore a need for an algorithm that can implemented in a pipe-lined circuit so that the elapsed time is minimized.
In this discussion, as an aid in understanding a numerical example will be used where the resampling will be assumed to be 4 to 1, and the resizing will be assumed to be between plus or minus 20%.
A typical color copier makes small changes in image size by slowing down the speed of the paper in the vertical, or slow scan direction, but in the fast scan direction the clock remains unchanged, and therefore the copier can only change the image size slightly by using a nearest neighbor algorithm to change the density of pixels in the horizontal, or fast scan, direction.
Therefore, in the horizontal direction, all that is required is resampling the pixels before the image is resized, and that is accomplished by averaging four pixels at a time, and using the result as the sampled pixel.
However, in the vertical direction, an image change of up to plus or minus 20% will also have to be made by using a reduction factor of between 3 and 5 to 1, this reduction being made by deleting the proper number of intervening scan lines.
A circuit for accomplishing all of this in a small amount of time is needed
SUMMARY OF THE INVENTION
This algorithm is designed to be implemented in a pipe-lined circuit which can average four consecutive pixels to produce one current averaged pixel (resampling in the horizontal direction) and at the same time determine if the pixels on the current scan line should be deleted or output (resampling and resizing in the vertical direction).
In the vertical direction, from the resampling ratio (4 to 1) and from the image size variation (+ or −20%) an algorithm can compute where, on the page, the scan lines should be. For a numerical example, if the input is 400 spots per unit of time, resampling would yield one scan line every {fraction (1/100)} of a unit. If, in addition, the image has to be reduced by 5%, then the final output would be one scan line every {fraction (1/95)}th of a time unit. An algorithm could be constructed so that at each time when there should be a scan line, the nearest actual scan line will be output. This would produce the proper scan line output, but the process would be cumbersome.
This algorithm accomplishes the same result by using a running sum of error terms. Simply stated, if it is known that the previous output scan was output at exactly at the right time, the error is zero, but if the scan was output too soon or too late, there will be an error term. For each new scan that is not output, {fraction (1/400)} of a time unit is added to the error term. Finally, when the error term rises to a predetermined threshold, then the algorithm knows that that is the closest approximation that can be made, the current scan line is output, {fraction (1/95)} of a time unit is subtracted from the running sum, and the algorithm proceeds to the next scans.
The circuit uses a first section for four clock cycles to average the first four input pixels of the current scan, and a second section to do the resampling and resizing on the fifth clock cycle while the first section is starting on the four pixels of the next scan. Thus, the entire pipe-lined circuit operates the speed of the averaging section.
REFERENCES:
patent: 5678155 (1997-10-01), Miyaza
patent: 5845008 (1998-12-01), Katoh et al.
patent: 6067374 (2000-05-01), Fan et al.
patent: 6091844 (2000-07-01), Fujii et al.
patent: 6181813 (2001-01-01), Fan et al.
Chen Mike C.
Fan Zhigang
Phong Kien A.
Wu John W.
Boudreau Leo
Kassa Yosef
Xerox Corporation
LandOfFree
Anti-counterfeit detection method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Anti-counterfeit detection method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Anti-counterfeit detection method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2576809