Image analysis – Pattern recognition – Template matching
Reexamination Certificate
1999-04-30
2002-04-09
Couso, Jose L. (Department: 2621)
Image analysis
Pattern recognition
Template matching
C358S501000, C358S538000, C382S135000, C382S194000, C382S209000, C399S366000
Reexamination Certificate
active
06370271
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to pattern detection methods and devices, such as copiers or scanners/printers, on which such methods may be implemented. More particularly, the invention relates to digital copiers and digital scanners/printers with features and capabilities for detecting certain patterns present on documents to be copied/printed. The invention is also applicable to image processing that involves comparing an input image to a stored image, especially for the purposes of authenticating the document containing the image, preventing its replication, or initiating other printer/copier related functions based on the results of the comparison.
2. Description of the Related Art
A number of systems have been proposed for recognizing valuable documents both for verification of authenticity and for prevention of forgery. These generally involve storing an accurate representation of a genuine document, scanning a new document and comparing the scanned document to the stored representation. In vending machines and money changing machines, for example, the desire is to prevent the acceptance of counterfeit currency. Bills submitted into the machines are scanned and compared to one or more acceptable currency patterns. If the scanned pattern matches a pattern of one of the genuine bills with a predetermined degree of similarity then the machine accepts the bill and delivers the change or merchandise. One such currency identification system is set forth in U.S. Pat. No. 4,386,432, issued to Nakamura et al. Typical of such systems, Nakamura conveys the currency note or bill at a fixed speed through a fixed scanning area and detects a characteristic of the bill. In this case it is the presence of a metallic element contained in the printing ink forming the printing pattern on the bill. Such systems typically require that the entire bill be scanned in a predetermined direction and a predetermined orientation. While such requirements may not be an important limitation in vending machines or change machines where the user must insert the bill into a fixed dimension slot in a fixed orientation, such requirements make the identification system inoperative where the scanning orientation is not fixed, e.g., on a copier, where the user can place the bill in a variety of positions on the platen glass.
Alternative systems have been proposed that do not rely as much on a specific orientation of the document on the scanning support surface. Instead these systems attempt to recognize a particular aspect of the document that uniquely identifies it as one that should not be duplicated. U.S. Pat. Nos. 5,440,409 and 5,481,378, issued to Sugano et al., detect a particular color of the background of confidential documents. For example, if documents are not intended to be copied the original document is printed on a red background. The document scanning section of the copier is provided with a color-detecting feature which filters out all but a particular color on the scanned document. It then compares the density of the color signal to a pre-stored color table to determine if it matches the background color of documents that are not to be copied. If a match is found copying is prevented. Such systems have limited application to documents in which a particular color can be chosen as a background color and is not applicable to situations where the particular color may appear on documents that can legitimately be copied. For example, the green on a U.S. bill may appear on any number of documents that can be legitimately copied.
U.S. Pat. Nos. 5,379,093 and 5,515,451 issued to Hashimoto et al. and Tsuji et al., respectively, seek to detect a combination of characteristics of one particular feature of the document to be copied. In the technique set forth in these patents, first a particular color is detected. Then, the image pattern having the particular color is compared to pre-stored standard patterns to detect a certain degree of similarity. Then, the pattern is analyzed to determine if it conforms to a particular shape, i.e. a circle. These systems have particular utility in detecting one unique aspect of a document, i.e. the stamp mark on bank notes issued by the Bank of Japan.
Additional systems have been proposed which seek to address the problem of document orientation on the platen glass. U.S. Pat. No. 5,216,724, issued to Suzuki et al., and U.S. Pat. No. 5,533,144, issued to Fan, are typical of such systems. In Suzuki, for example, the document can be placed in any orientation on the platen. The document is scanned and the scanned images are processed such that the four corners of the document are determined and then the angle of the document on the platen is calculated. Then, one particular feature of the document, e.g., the red stamp mark on a Japanese bank note, is compared to a pre-stored standard pattern which corresponds generally to the calculated angle of the document. A number of standard patterns at various orientation angles are pre-stored. Fan proposes a somewhat different system in which the orientation of the document is first calculated and then the pre-stored patterns or templates are rotated to match the angle of the scanned document. In both of these systems the orientation of the document must first be calculated, which requires the detection of edges and corners.
SUMMARY OF THE INVENTION
It is an object of the present invention to overcome the aforementioned problems and disadvantages of conventional systems for recognizing certain types of documents or patterns thereon.
Another object of this invention is to provide an improved system for detecting certain types of patterns present on documents with a high degree of certainty but without a commensurately high amount of processing.
A further object of this invention is to provide an improved system for detecting a document independent of the orientation of the document when it is being scanned or copied.
According to one aspect of this invention, a method is provided for detecting a pattern in an input image. The method comprises the following steps: generating from the input image digital data defined by a plurality of rows of pixels, each pixel defined by an N-bit value; processing at least some of the rows of pixels one row at a time by obtaining a row of pixels, thresholding the N-bit value of each pixel in that row to an M-bit value where M<N, and storing the M-bit pixel values row-by-row in a buffer; performing a specified element finding procedure on a select number of rows of thresholded digital data stored in the buffer to determine if at least a portion of the specified element is present in the stored digital data; and if it is determined that at least a portion of the specified element is present in the stored digital data, performing the following steps: calculating coordinates of a particular characteristic of each specified element, at least a portion of which is identified in the stored digital data, and storing the calculated coordinates in a list; generating a density template for each specific element for which coordinates have been calculated by partitioning an area of the stored digital data containing that specified element including an interior thereof into a plurality of sectors and maintaining a density count for each sector; and performing template matching for each specified element for which a density template has been generated to determine if that density template substantially matches a corresponding reference pattern density template.
According to another aspect of the invention, a method is provided for detecting a pattern in an input image. This method comprises the following steps: generating from the input image digital data defined by a plurality of rows and columns of pixels, each pixel defined by an N-bit value; subsampling the digital data by processing a predetermined number of rows and columns of pixels; thresholding the subsampled digital data; performing an edge detection procedure on the thresholded digital data to dete
Bhattacharjya Anoop
Fu Bin
Couso Jose L.
Desire Gregory
Gabrik Michael T.
LandOfFree
Image processing apparatus and methods for pattern recognition does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image processing apparatus and methods for pattern recognition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image processing apparatus and methods for pattern recognition will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2926488