Image processing apparatus and methods for pattern recognition

Claim 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 12 or fewer rows of pixels one row at a time, each row containing at most 100 pixels, 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, wherein M is based on the pattern to be detected; performing a specified element finding procedure on the processed 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, wherein the specified element is a geometric shape that forms a part of the pattern; 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 specified 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.

Claim 2

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 12 or fewer rows of pixels one row at a time, each row containing at most 100 pixels, 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, wherein M is based on the pattern to be detected; performing a specified element finding procedure on the processed 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, wherein the specified element is a geometric shape that forms a part of the pattern; 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 specified 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.

Claim 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 only processing pixels in every Q row and pixels in every Q column, where Q≧2; 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, wherein the specified element is a geometric shape that forms a part of the pattern; 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 specified 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.

Claim 9

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 only processing pixels in every Q row and pixels in every Q column, where Q≧2; 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, wherein the specified element is a geometric shape that forms a part of the pattern; 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 specified 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.

Claim 15

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 processes 12 or fewer rows of pixels, one row at a time, each row containing at most 100 pixels, by obtaining a row of pixels, thresholding the N-bit value of each pixel in that row to an M-bit value pixel where M<N, and storing the thresholded M-bit value pixels row by row in a buffer, wherein M is based on the pattern to be detected; 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, wherein the specified element is a geometric shape that forms a part of the pattern; 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 specified 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; wherein the template matcher partitions an area of the stored digital data containing the specified element including an interior thereof into a plurality of sectors and maintaining a density count for each sector.

Claim 16

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 processes 12 or fewer rows of pixels, one row at a time, each row containing at most 100 pixels, by obtaining a row of pixels, thresholding the N-bit value of each pixel in that row to an M-bit value pixel where M<N, and storing the thresholded M-bit value pixels row by row in a buffer, wherein M is based on the pattern to be detected; 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, wherein the specified element is a geometric shape that forms a part of the pattern; 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 specified 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; wherein the template matcher partitions an area of the stored digital data containing the specified element including an interior thereof into a plurality of sectors and maintaining a density count for each sector.

Claim 18

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 12 or fewer rows of pixels one row at a time, each row containing at most 100 pixels, 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, wherein M is based on the pattern to be detected; 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, wherein the specified element is a geometric shape that forms a part of the pattern; 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 specified 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.

Claim 19

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 12 or fewer rows of pixels one row at a time, each row containing at most 100 pixels, 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, wherein M is based on the pattern to be detected; 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, wherein the specified element is a geometric shape that forms a part of the pattern; 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 specified 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.