Method for automatic visual identification of a reference site in an image

• US 6,240,208 B1
• Filed: 08/05/1998
• Issued: 05/29/2001
• Est. Priority Date: 07/23/1998
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Taycher, Leonid, Garakani, Arman
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Mariam, Daniel G.
• Application Number:
  US09/129,152
• Time in Patent Office: 1,028 Days
• Field of Search: 382/190, 382/209, 382/261, 382/265, 382/275, 382/160, 382/287, 382/181, 348/607, 348/610
• US Class Current: 382/190
• CPC Class Codes: G06V 10/443 by matching or filtering

Abstract

An efficient and reliable method that identifies possible reference sites in an image is disclosed. The method emphasizes customizing the identification of reference sites for each application by providing for initialization of various parameters, such as the size of the reference site. The method then uses a series of measurable parameters to filter possible reference sites in the image and produces and ordered set of possible reference sites. The highest-ranking site of the ordered set is expected to be chosen as the reference site for production. A preferred implementation is disclosed that uses multi-resolution images to enhance efficiency of the identification and that specifically measures the symmetry, orthogonality and uniqueness of the windows.

Claims

1. A method for automatic visual identification of a reference site in an image comprising:

identifying at least one parameter that indicates an extent of redundancy within a possible reference site, the extent of redundancy within the possible reference site includes representing a degree of balance of image data of the possible reference site;

wherein symmetry is a measure of the degree of balance of the image data within the possible reference site, and wherein orthogonality and the symmetry are measures of the extent of redundancy of the possible reference site, and wherein the at least one parameter includes the symmetry, the orthogonality and uniqueness of the possible reference site;

acquiring the image;

filtering windows in the image using the at least one parameter so as to provide an ordered set of possible reference sites; and

reporting the ordered set of possible reference sites.

2. The method of claim 1,

wherein filtering the windows in the image using the at least one parameter so as to provide the ordered set of possible reference sites further includes:

according to a predetermined sequence of the at least one parameter, using each one of the at least one parameter, in turn, to filter the windows in the image so as to provide the ordered set of possible reference sites.

3. The method of claim 1, further comprising smoothing and sampling the image prior to filtering.

4. The method of claim 1, wherein the ordered set of possible reference sites includes one possible reference site.

5. The method of claim 1, wherein the at least one parameter includes symmetry of a possible reference site, and filtering the windows in the image using the at least one parameter so as to provide the ordered set of possible reference sites further comprises:

smoothing and sampling the image to produce a reduced-resolution image;

measuring similarity of opposed halves of the windows, the opposed halves being defined by an axis of symmetry in at least one direction to provide symmetry values; and

ordering the windows as a function of the symmetry values to provide the ordered set of possible reference sites.

6. The method of claim 1, wherein the at least one parameter includes symmetry of the possible reference site, and filtering the windows in the image using the at leas tone parameter so as to provide the ordered set of possible reference sites further comprises:

performing normalized correlation between halves of the windows to generate at least one correlation coefficient score for each window, the halves being defined by an axis of symmetry in at least one direction, and

filtering the windows so as to order the windows using the at least one correlation coefficient score for each of the windows.

7. The method of claim 1, wherein the at least one parameter includes orthogonality, and filtering the windows in the image using the at least one parameter so as to provide the ordered set of possible reference sites comprises:

applying an edge extraction tool to each of the windows to yield a set of angles for each edge pixel within each of the windows;

transforming the set of angles for each of the windows into a radial histogram;

summing a number of the edge pixels in the radial histogram approximately about two axes to provide an orthogonality score for each of the windows; and

ordering the windows by the orthogonality score.

8. The method of claim 1, wherein user supplied variables are accommodated, the method further comprising:

providing a sampling rate at which to acquire the image, where the sampling rate is a user supplied variable.

9. The method of claim 1, wherein user supplied variables are accommodated, the method further comprising:

providing a window size of the possible reference sites, where the window size is a user supplied variable.

10. The method of claim 1, wherein user supplied variables are accommodated, the method further comprising:

providing a computational method for the at least one parameter, where the computational method is a user supplied variable.

11. The method of claim 1, wherein user supplied variables are accommodated, and wherein choice of averaging method, for each of the at least one parameter, is a user supplied variable.

14. The method of claim 1, wherein filtering the windows in the image further includes:

according to a predetermined sequence of the at least one parameter, using a first one of the at least one parameter to filter the windows so as to provide a subset of the windows that meets the first one of the at least one parameter; and

filtering the subset of the windows using, other than the first one, the at least one parameter, according to the predetermined sequence, so as to provide the ordered set of possible reference sites.

15. The method of claim 5, wherein two sets of the opposed halves of the windows are defined by the x-axis and the y-axis, respectively, and wherein filtering further comprises:

combining the symmetry values for each one of the windows to provide a single similarity value for each one of the windows.

16. The method of claim 5, wherein filtering further comprises:

storing on a symmetry surface, at an origin of each of the windows, the symmetry values, respectively for each of the windows;

thresholding the symmetry surface;

identifying peaks on the symmetry surface;

assigning windows corresponding to the peaks as the possible reference sites, and ordering the possible reference sites by a magnitude of the peaks corresponding thereto.

17. The method of claim 5, wherein filtering further comprises:

storing on a symmetry surface, at an origin of each of the windows, the symmetry values, respectively for each of the windows;

thresholding the symmetry surface;

identifying peaks on the symmetry surface;

calculating second derivatives of the peaks as symmetry scores for the windows corresponding to the peaks; and

wherein ordering further comprises ordering the windows by the symmetry scores.

18. The method of claim 17, wherein filtering further comprises:

assigning a smaller of the second derivatives for each of the peaks as the symmetry scores, respectively, of each of the peaks.

19. The method of claim 1, wherein filtering further comprises:

measuring each of the at least one parameter for each of the windows to provide scores;

filtering the windows using a function of the scores so as to provide the ordered set of possible reference sites.

20. The method of claim 1, wherein reporting the ordered set of possible reference sites further includes:

reporting the ordered set of possible reference sites as a plurality of reference sites from which a user can choose one of the plurality of reference sites as the reference site.

21. The method of claim 1, wherein reporting further comprises:

reporting a highest ordered possible reference site from the ordered set of possible reference sites as the reference site.

32. The method of claim 14, wherein filtering windows in the image using the at least one parameter in the predetermined sequence so as to provide an ordered set of possible reference sites comprises:

measuring each of the at least one parameter for each of the windows to provide scores;

weighting the score of each of the at least one parameter for each of the windows to provide weighted scores;

combining the weighted scores for each of the windows to yield a combined score for each of the windows; and

generating the ordered set of possible reference sites using the combined score for each of the windows.

12. A method for automatic visual identification of a reference site in an image comprising:

identifying a plurality of measurable parameters that characterize a good reference site, at least one of the plurality of measurable parameters adapted to measure an extent of redundancy, including balance of image data, within a possible reference site;

wherein symmetry is a measure of the balance of the image data within the possible reference site, and wherein orthogonality and the symmetry are measures of the extent of redundancy of the possible reference site, and wherein the plurality of measurable parameters include the symmetry, the orthogonality and uniqueness of the possible reference site;

selecting a sequence of the plurality of measurable parameters to be used for filtering;

acquiring the image;

filtering windows in the image using the plurality of measurable parameters in the sequence so as to provide an ordered set of possible reference sites; and

reporting the ordered set of possible reference sites.

22. The method of claim 12, wherein the plurality of measurable parameters include symmetry of the possible reference site, and filtering the windows further comprises:

performing normalized correlation between halves of the windows to generate at least one correlation coefficient score for each of the windows to generate at least one correlation coefficient score for each of the windows, the halves being defined by an axis of symmetry in at least one direction, and

filtering the windows so as to order the windows using the at least one correlation coefficient score for each of the windows.

23. The method of claim 12, wherein user supplied variables are accommodated, the method further comprising:

providing a sampling rate at which to acquire the image, where the sampling rate is a user supplied variable.

24. The method of claim 12, wherein user supplied variables are accommodated, the method further comprising:

providing a window size of the possible reference sites, where the window size is a user supplied variable.

13. A method for automatic visual identification of a reference site in an image comprising:

providing a redundancy parameter that characterizes balance of image data within an window;

wherein symmetry is a measure of the balance of image data within the possible reference site, and wherein orthogonality and the symmetry are measures of an extent of the redundancy of the possible reference site, and wherein the redundancy parameter includes the symmetry and the orthogonality of the possible reference site;

providing a uniqueness parameter that characterizes uniqueness of a window in the image;

acquiring the image;

filtering windows in the image using the redundancy parameter followed by the uniqueness parameter so as to provide an ordered set of possible reference sites; and

reporting the ordered set of possible reference sites.

25. The method of claim 13, wherein providing the redundancy parameter further comprises:

providing the redundancy parameter that characterizes positional stability of the window.

26. The method of claim 13, wherein providing the redundancy parameter further comprises:

providing a plurality of redundancy parameters, at least one of the plurality of redundancy parameters characterizes the balance of the image data.

27. The method of claim 26, wherein at least one of the plurality of redundancy parameters characterizes positional stability of the window.

28. The method of claim 13, wherein filtering further includes:

filtering the windows using the redundancy parameter so as to provide a subset of the windows that have adequate redundancy; and

filtering the subset of the windows using the uniqueness parameter.

29. The method of claim 13, wherein the redundancy parameter includes symmetry of the possible reference site, and filtering the windows in the image further comprises:

performing normalized correlation between halves of the windows to generate at least one correlation coefficient score for each of the windows, the halves being defined by an axis of symmetry in at least one direction, and

filtering the windows using the at least one correlation coefficient score for each of the windows so as to provide a sub-set of possible reference sites to be evaluated by the uniqueness parameter.

30. The method of claim 13, wherein user supplied variables are accommodated, the method further comprising:

providing a sampling rate at which to acquire the image, where the sampling rate is a user supplied variable.

31. The method of claim 13, wherein user supplied variables are accommodated, the method further comprising:

providing a window size of the possible reference sites, where the window size is a user supplied variable.