IMAGE PROCESSING APPARATUS AND METHODS FOR PATTERN RECOGNITION

• US 20020009229A1
• Filed: 04/30/1999
• Published: 01/24/2002
• Est. Priority Date: 04/30/1999
• Status: Active Grant

• Current Assignee: Seiko Epson Corporation (Seiko Group)
• Original Assignee: Seiko Epson Corporation (Seiko Group)
• Inventors: FU, BIN, BHATTACHARJYA, ANOOP
• Granted Patent: US 6,370,271 B2
• Time in Patent Office: Days
• US Class Current: 382/199
• CPC Class Codes: G06V 10/40 Extraction of image or video features

Abstract

Pattern detection methods, which may be embodied in copiers or scanners/printers, examine documents to be copied or printed to determine whether the documents contain one or more targeted patterns. The pattern detection methods include algorithms that look for certain features and geometric relationships between the features in determining whether one or more of the targeted patterns are present.

Claims

1. A method for detecting a pattern in an input image, comprising:

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.

2. The method of claim 1, wherein N is 24 and M is greater than or equal to 1 and less than or equal to 8.

3. The method of claim 2, wherein M is based on the pattern to be detected.

4. The method of claim 1, wherein the specified element is a circle and the specified element finding procedure is an edge-based circle finding procedure that is performed on the predetermined number of rows of thresholded digital data stored in the buffer to determine if at least a portion of a circle is present in the stored digital data.

5. The method of claim 4, wherein, if it is determined in the specified element finding procedure performing step that at least a portion of a circle is present in the stored digital data, the following additional step is performed:

determining, based on the calculated coordinates of the particular characteristic of the circle, at least a portion of which is determined to be present in the stored digital data, whether that circle corresponds to an existing circle or a new circle.

6. The method of claim 1, wherein, in the density template generating step, each density template generated is a density matrix and each corresponding reference pattern density template is a reference pattern density matrix.

7. The method of claim 6, wherein the template matching performing step comprises comparing each density matrix generated with the corresponding reference pattern density matrix.

8. A method for detecting a pattern in an input image, comprising:

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 detect and store edge pixels;

performing a specified element identification procedure on a region of digital data comprising a select number of rows of stored, edge-detected pixels by calculating a correlation between the region of digital data and a corresponding sector template to determine if at least a portion of the specified element is present in the region of digital data; and

if the calculated correlation is greater than a predetermined trigger threshold, performing the following steps;

performing an acceptance test on an area of digital data containing each specified element, at least a portion of which is identified in the region of digital data;

generating a density template for each accepted specific element by partitioning the area of 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.

9. The method of claim 8, wherein the thresholding step comprises thresholding the N-bit value of each pixel of the subsampled digital data to an M-bit value where M<

N.

10. The method of claim 9, wherein N is 24 and M is greater than or equal to 1 and less than or equal to 8.

11. The method of claim 10, wherein M is based on the pattern to be detected.

12. The method of claim 8, wherein, in the density template generating step, each density template generated is a density matrix and each corresponding reference pattern density template is a reference pattern density matrix.

13. The method of claim 12, wherein the template matching performing step comprises comparing each density matrix generated with the corresponding reference pattern density matrix.

14. An apparatus for detecting at least one pattern in an input image represented by digital data defined by a plurality of N-bit value pixels, comprising:

a thresholding unit that thresholds at least some of the plurality of N-bit value pixels to M-bit value pixels where M<

N, and stores the thresholded M-bit value pixels;

a first database in communication with the thresholding unit, the database storing threshold values for at least one reference pattern;

means for determining if at least a portion of a specified element is present in the stored digital data;

means for determining a characteristic of the specified element, if it is determined that at least a portion of the specified element is present in the stored digital data and storing the determined characteristic;

a template matcher that generates a density template for each specific element for which the characteristic was determined and compares that density template with a corresponding reference pattern density template to determine if that density template substantially matches the corresponding reference pattern density template.

15. The apparatus of claim 14, further comprising a second database that stores each corresponding reference pattern template.

16. A medium readable by a device embodying a program of instructions for execution by said device to perform a method for detecting a pattern in an input image, the method comprising:

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.