Method and apparatus for object recognition

• US 6,424,745 B1
• Filed: 05/19/1998
• Issued: 07/23/2002
• Est. Priority Date: 05/19/1998
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Thomas, Gordon Albert, Mitra, Partha Pratim, Hess, Harald F., Hansen, Mark Henry
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): DESIRE, GREGORY M
• Application Number:
  US09/081,469
• Time in Patent Office: 1,526 Days
• Field of Search: 382/110, 382/164-165, 382/170, 382/190, 382/191, 382/154, 209/580, 209/939, 250/226, 348/89, 356/407, 356/601
• US Class Current: 382/191
• CPC Class Codes: G06V 10/431 Frequency domain transformation; Autocorrelation
• CPC Class Codes: G06V 20/68 Food, e.g. fruit or vegetables

Abstract

A method and system for optically recognizing an object from a reference library of known products based on a spectrum of local radius of curvature of the object. A surface portion of an object is illuminated with a pattern of light that permits the extraction of three dimensional coordinates for a set of points on the surface portion of the object. An image data set of the surface portion of the object is then captured with a capture device that is positioned at an angular offset with respect to a source of the light. That is, the combination of the light pattern and the imaging device together generate a two dimensional captured image, from which it is possible to extract the three dimensional coordinates for the set of points on the surface portion of the object. A set of local radii of curvatures are then determined for selected data points in the image data set. A spectrum representing a distribution of the curvatures is then computed for the set of local radii of curvatures. If the data set is for the generation of a library of spectra, it is processed with a dimension reduction analysis to determine a single set of basis functions representing all of the objects and a corresponding set of basis coefficients for each different type of object. If the data set is for an unknown object, then the dimension reduction analysis and the basis functions are applied to the data set to generate an unidentified set of basis coefficients. This latter set is then statistically compared with the reference library of spectra to identify the product or at least designate the closest known products.

Claims

1. A method for use by a computer for recognizing an object from a reference library of known objects based on a spectrum of local radius of curvature of said object, said method comprising the steps of:

illuminating a surface portion of said object with a pattern of light, wherein said pattern of light is selected from the group consisting of a grid pattern and a pattern of “

X”

s;

capturing an image data set of said surface portion at an angular offset with respect to a source of said pattern of light, wherein said pattern of light and offset image capture permit extraction of three dimensional coordinates for data points in said image data set;

extracting three dimensional coordinates for at least one data point in said image data set;

determining a spectrum of local radii of curvatures for said at least one selected data point in said image data set;

constructing said reference library of known objects by repeating said steps of capturing, extracting and determining with different objects; and

comparing an unknown spectrum of local radius of curvature against said reference library of known objects to make an identification.

2. The method according to claim 1, wherein said source illuminates said object with a series of parallel planes of light.

3. The method according to claim 1, wherein said step of determining computes said spectrum of local radii of curvatures over varying lengths of data points in said image data set.

4. The method according to claim 1, wherein said step of constructing includes repeating said steps of applying, capturing and determining with different orientations of each of said different objects.

5. The method according to claim 1, wherein said step of determining includes the steps of:

extracting a mean local radius of curvature for said object; and

extracting a Gaussian local radius of curvature for said object.

6. The method according to claim 1, wherein said step of determining includes the steps of:

identifying a neighborhood of data points for said at least one selected data point;

rotating said neighborhood of data points such that an outward normal to said surface portion of said object at said at least one selected point is aligned vertically;

fitting a local weighted least square polynomial to said neighborhood of data points; and

calculating at least one measure of local radius of curvature for said at least one selected data point.

7. The method according to claim 6, wherein said step of determining further includes the steps of:

repeating said steps of identifying, rotating, fitting and calculating for each additional selected data point; and

compiling histograms of all measures of local radii of curvatures to form a spectrum representing a distribution of said at least one measure of local radius of curvature.

8. The method according to claim 1, wherein a size of said surface portion is selectable from a range of sizes dependent upon an actual size of said object.

9. The method according to claim 1, wherein a size of said surface portion is relative to an actual size of said object.

10. The method according to claim 1, wherein said step of constructing further includes the step of generating a given set of basis functions for all of said different objects and a corresponding set of basis coefficients for each of said different objects when constructing said reference library of known objects.

11. The method according to claim 10, wherein the step of comparing includes the steps of:

generating a given set of basis coefficients for said object when utilizing said reference library of known objects to identify said object; and

classifying said given set of basis coefficients against said reference library of known objects to identify said corresponding set of basis coefficients most closely matching said given set of basis coefficients.

12. The method according to claim 11, wherein linear discriminant analysis is used to generate said given set of basis functions, said corresponding set of basis coefficients and said given set of basis coefficients.

13. The method according to claim 11, wherein said step of classifying is achieved using a non-negative least squares technique.

14. The method according to claim 11, wherein said step of classifying is achieved using a nearest neighbor technique.

15. The method according to claim 11, wherein penalized discriminant analysis is used to generate said given set of basis functions, said corresponding set of basis coefficients and said given set of basis coefficients.

16. The method according to claim 1, wherein said step of comparing includes the steps of:

generating a ranked order list of object choices;

displaying said ranked order list on a display interface unit; and

selecting one of said object choices on said ranked order list.

17. The method according to claim 16, wherein said step of selecting is automatic.

18. The method according to claim 16, wherein said step of selecting is manual.

19. The method of claim 1, further including the steps of:

characterizing said object using spectroscopic analysis; and

statistically combining said spectroscopic analysis with said step of comparing to produce a ranked order list of most closely matched product choices.

20. An optical recognition system for recognizing an object from a reference library of known objects based on a spectrum of local radius of curvature of said object, said system comprising:

a source for illuminating a surface portion of said object with a pattern of light, wherein said pattern of light is a grid;

an imaging device that is positioned at an angular offset with respect to said source for capturing an image data set of said surface portion, wherein said pattern of light and said imaging device permit the extraction of three dimensional coordinates for data points in said image data set;

a processor for extracting three dimensional coordinates and for determining a spectrum of local radii of curvatures for at least one selected data point in said image data set;

said processor being further operable to construct said reference library of known objects by capturing image data sets of different objects; and

said processor being further operable to compare an unknown spectrum of local radius of curvature against said reference library of known objects to make an identification.

21. The system according to claim 20, wherein said source illuminates said object with a series of parallel planes of light.

22. The system according to claim 20, wherein said processor computes said spectrum of local radii of curvatures over varying lengths of data points in said image data set.

23. The system according to claim 20, wherein said processor constructs said reference library with different orientations of each of said different objects.

24. The system according to claim 20, wherein:

said processor is further operable to identify a neighborhood of data points for said at least one selected data point;

said processor is further operable to rotate said neighborhood of data points such that an outward normal to said surface portion of said object at said at least one selected data point is aligned vertically;

said processor is further operable to fit a local weighted least square polynomial to said neighborhood of data points; and

said processor is further operable to calculate at least one measure of local radius of curvature for said at least one selected data point.

25. The system according to claim 24, wherein said at least one measure of curvature includes a mean local radius of curvature for said object and a Gaussian local radius of curvature for said object and wherein said processor is further operable to compile histograms of all measures of local radii of curvatures to form a spectrum representing a distribution of said at least one measure of local radius of curvature.

26. The system according to claim 20, wherein said source can illuminate varying sizes of said surface portion of said object.

27. The system according to claim 20, wherein:

said processor is further operable to generate a given set of basis functions for all of said different objects and a corresponding set of basis coefficients for each of said different objects when constructing said reference library of known objects;

said processor is further operable to generate a given set of basis coefficients for said object when utilizing said reference library of known objects to identify said object; and

said processor is further operable to classify said given set of basis coefficients against said reference library of known objects to identify said corresponding set of basis coefficients most closely matching said given set of basis coefficients.

28. The system according to claim 27, wherein said processor utilizes linear discriminant analysis to generate said given set of basis functions, said corresponding set of basis coefficients and said given set of basis coefficients and wherein said processor uses non-negative least squares analysis to classify said object.

29. The system according to claim 27, wherein said processor utilizes penalized discriminant analysis to generate said given set of basis functions, said corresponding set of basis coefficients and said given set of basis coefficients and wherein said processor uses nearest neighbor analysis to classify said object.

30. The system according to claim 20, further including a display for displaying a ranked order list of object choices and said display having means for selecting one of said object choices on said ranked order list.

31. The system of claim 20 wherein said illuminating source is a bar-code reader.