Image pattern detection method and apparatus

• US 6,766,056 B1
• Filed: 11/30/1999
• Issued: 07/20/2004
• Est. Priority Date: 11/30/1998
• Status: Expired due to Term

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Foo, Yoong-Chert, Bell, Peter Leslie, Webb, Michael John, Chen, Yu-Ling, Huang, Kai
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): DESIRE, GREGORY M
• Application Number:
  US09/451,441
• Time in Patent Office: 1,694 Days
• Field of Search: 382/190, 382/276, 382/266, 382/302, 382/165, 382/209, 382/282, 382/288, 380/51, 358/453, 358/538
• US Class Current: 382/190
• CPC Class Codes: G06V 10/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components

Abstract

Disclosed is method of detecting a predetermined mark (30) forming part of an image. A digitized form (48, 49) of the image (21) comprising a plurality of picture elements is provided and within a current region of the image a set of features is determined. The features typically comprise a dominant color feature (44) within the current region; and at least one moment feature (111) based on picture elements pertaining to the predetermined mark within the current region. Each determined feature is compared (113) with a corresponding predetermined feature (114) of the predetermined mark. Using the comparison, a confidence level for a detection of said predetermined mark within the current region calculated. Based on the confidence level, whether or not said predetermined mark is detected in the current region can then be determined. Adjunct to the above method, also disclosed are methods for providing multiple encoded representations (40) of the image, detecting a center location (108, 160) of a predetermined pattern in the image, and determining (170, 171) a moment feature of a portion of the image.

Claims

1. A method of detecting a predetermined mark forming part of an image, said method comprising:

a provide step of providing a digitized form of the image comprising a plurality of picture elements;

a feature determination step of determining within a current region of the image a set of features comprising at least

a dominant color feature, and

at least one moment feature based on picture elements pertaining to the predetermined mark;

a comparison step of comparing each determined feature with a corresponding predetermined feature of the predetermined mark;

a calculation step of calculating, using a result from said comparison step, a confidence level for detecting the predetermined mark within the current region; and

a mark determination step of determining, based on the confidence level calculated in said calculation step, whether the predetermined mark is detected in the current region.

2. A method according to claim 1, wherein said feature determination step includes determining a number of picture elements within the current region not pertaining to the predetermined mark.

3. A method according to claim 1, wherein said comparison step further includes establishing a threshold for each determined feature using a predetermined threshold value.

4. A method according to claim 3, wherein the set of features determined in said feature determination step comprises a range of feature values for each determined feature and the corresponding predetermined threshold value.

5. A method according to claim 1, further comprising a selection step of

selecting a new region of the image as the current region, wherein said feature determination step, said comparison step, said calculation step, and said mark determination step are performed on the new region.

6. A method according to claim 5, wherein selection of the new region comprises a detection step of detecting a center location of a predetermined pattern in the image, and said detection step includes the sub-steps of:

examining a plurality of pixel values at predetermined pixel locations within the image, the predetermined pixel locations being determined by a plurality of groups comprising multiple locations in each group and the groups being configured into a predetermined geometric arrangement having a corresponding geometric center location;

determining an evidence value for each group of examined pixel values;

determining a deviation measure value from the evidence values of substantially all the groups of the geometric arrangement; and

establishing a threshold of the deviation measure value against a predetermined threshold value and outputting a center value, indicating a pixel location corresponding to the center location, if the deviation value for each group is below the predetermined threshold value, or otherwise outputting an invalid value.

7. A method according to claim 1, wherein determining at least one moment feature includes the sub-steps of:

storing a predetermined subset of coefficient values of a moment matrix, wherein the moment matrix has a predetermined symmetry and the predetermined subset of coefficient values being those coefficient values which exploit at least part of the predetermined symmetry;

combining picture element values at selected locations in the current region to provided a combined result, wherein the selected locations are associated with a respective coefficient value of the predetermined subset of coefficient values;

multiplying each combined result with a corresponding coefficient value; and

accumulating each multiplied combined result to determine a moment feature of the current region.

8. An apparatus for detecting a predetermined mark forming part of an image, said apparatus comprising:

input means for providing a region of the image, wherein the image comprises a plurality of pixels and the predetermined mark is distinguishable by a specified pixel arrangement of predetermined colors;

feature determining means for determining within a current region of the image a set of features comprising at least

a dominant color feature, and

at least one moment feature based on the pixels having one of the predetermined colors of the current region; and

comparison means for comparing each determined feature with a corresponding predetermined feature of the predetermined mark;

calculation means for calculating, using a result from said comparison means, a confidence value for detecting the predetermined mark within the current region; and

mark determining means for determining, based on the confidence value calculated by said calculation means, whether the predetermined mark is detected in the current region.

9. An apparatus according to claim 8, wherein the feature determining means further determines a total number of pixels having one of the predetermined colors of the current region.

10. A computer readable medium, having a program recorded thereon, where said program is configured to make a computer execute a method to detect a predetermined mark forming part of an image, wherein the image comprises a plurality of pixels and the predetermined mark is distinguishable by a specified pixel arrangement of predetermined colors, said program comprising:

code for a provide step of providing a digitized form of the image comprising a plurality of picture elements;

code for a feature determination step of determining within a current region of the image a set of features comprising at least

a dominant color feature, and

at least one moment feature based on picture elements pertaining to the predetermined mark;

code for a comparison step of comparing each determined feature with a corresponding predetermined feature of the predetermined mark;

code for a calculation step of calculating, using a result from said comparison step, a confidence level for detecting the predetermined mark within the current region; and

code for a mark determination step of determining, based on the confidence level, whether the predetermined mark is detected in the current region.

11. A computer readable medium according to claim 10, wherein said feature determination step includes determining a number of picture elements within the current region not pertaining to the predetermined mark.

12. A computer readable medium according to claim 10, wherein said comparison step includes establishing a threshold for each determined feature using a predetermined threshold value.

13. A computer readable medium according to claim 10, wherein said feature determining step includes determining a total number of pixels having one of the predetermined colors of the current region.

14. A computer program element comprising computer program code means to make a computer execute a method to detect a predetermined mark forming part of an image, said computer code means comprising:

code for a provide step of providing a digitized form of the image comprising a plurality of picture elements;

code for a feature determining step of determining within a current region of the image a set of features comprising at least

a dominant color feature, and

at least one moment feature based on picture elements pertaining to the predetermined mark; and

code for a comparison step of comparing each determined feature with a corresponding predetermined feature of the predetermined mark;

code for a calculation step of calculating, using a result from said comparison step, a confidence level for detecting the predetermined mark within the current region; and

code for a mark determination step of determining, based on the confidence level calculated in said calculation step, whether the predetermined mark is detected in the current region.

15. A system for detecting a predetermined mark forming part of an image, said system comprising:

memory for storing at least a portion of a digitized form of the image comprising a plurality of picture elements and for storing predetermined features of the predetermined mark; and

a processor coupled to said memory, wherein said processor is programmed to perform;

determining, within a current region of the image, a set of features comprising at least a dominant color and at least one moment feature based on picture elements pertaining to the predetermined mark,

comparing each determined feature with a corresponding one of the predetermined features,

calculating, using a result from the comparing, a confidence level for detecting the predetermined mark within the current region, and

determining, based on the confidence level, whether or not the predetermined mark is detected in the current region.