Shape feature extraction and classification

• US 20060008151A1
• Filed: 12/03/2004
• Published: 01/12/2006
• Est. Priority Date: 06/30/2004
• Status: Active Grant

• Current Assignee: National Instruments Corporation (Emerson Electric Company)
• Original Assignee: National Instruments Corporation (Emerson Electric Company)
• Inventors: Vazquez, Nicolas, Crotty, Kevin M., Lin, Siming
• Granted Patent: US 7,668,376 B2
• Time in Patent Office: Days
• US Class Current: 382/190
• CPC Class Codes: G06F 18/254 of classification results, e.g. of results related to same input data
• CPC Class Codes: G06V 10/46 Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features colour feature extraction G06V10/56
• CPC Class Codes: G06V 10/809 of classification results, e.g. where the classifiers operate on the same input data

Abstract

System and method for analyzing an image. A received image, comprising an object or objects, is optionally preprocessed. Invariant shape features of the object(s) are extracted using a generalized invariant feature descriptor. The generalized invariant feature descriptor may comprise a generalized invariant feature vector comprising components corresponding to attributes of each object, e.g., related to circularity, elongation, perimeter-ratio-based convexity, area-ratio-based convexity, hole-perimeter-ratio, hole-area-ratio, and/or functions of Hu Moment 1 and/or Hu Moment 2. Non-invariant features, e.g., scale and reflection, may be extracted to form corresponding feature vectors. The object is classified by computing differences between the generalized invariant feature vector (and optionally, non-invariant feature vectors) and respective generalized invariant feature vectors corresponding to reference objects, determining a minimum difference corresponding to a closest reference object or class of reference objects of the plurality of reference objects, and outputting an indication of the closest reference object or class as the classification.

Claims

1. A computer-implemented method for analyzing an image, the method comprising:

receiving an image, wherein the image comprises an object;

extracting invariant shape features of the object using a generalized invariant feature descriptor; and

classifying the object based on the extracted invariant shape features.

2. The method of claim 1, wherein the generalized invariant feature descriptor comprises a generalized invariant feature vector comprising components corresponding to:

roundness of the object;

compactness of the object;

holes of the object; and

Hu moments of the object.

3. The method of claim 2, wherein the generalized invariant feature descriptor comprises a generalized invariant feature vector comprising respective components corresponding to:

circularity of the object;

elongation of the object;

perimeter-ratio-based convexity of the object;

area-ratio-based convexity of the object;

hole-perimeter-ratio of the object;

hole-area-ratio of the object;

a function of Hu Moment 1 of the object; and

a function of Hu Moment 2 of the object.

4. The method of claim 3, wherein the component corresponding to the circularity of the object comprises the reciprocal of the circularity of the object.

5. The method of claim 3, wherein the component corresponding to the elongation of the object comprises a normalized reciprocal of the elongation of the object.

6. The method of claim 3, wherein the function of Hu Moment 1 comprises Hu Moment 1.

7. The method of claim 3, wherein the function of Hu Moment 2 comprises the square root of Hu Moment 2.

8. The method of claim 3, wherein said extracting invariant shape features using a generalized invariant feature descriptor comprises:

determining values for the respective components of the generalized invariant feature descriptor, thereby generating the generalized invariant feature vector corresponding to the object.

9. The method of claim 8, wherein the value for each of the respective components is normalized to a specified range.

10. The method of claim 9, wherein the specified range for each value is approximately zero to approximately one.

11. The method of claim 1, further comprising:

preprocessing the image prior to said extracting invariant shape features.

12. The method of claim 11, wherein the received image comprises a multi-scale image, and wherein said preprocessing comprises thresholding the image to convert the image to a binary image.

13. The method of claim 11, wherein said preprocessing comprises performing edge detection of the image to determine a contour of the object, and wherein said extracting invariant shape features of the object is based on said contour.

14. The method of claim 11, wherein said preprocessing comprises performing color characterization of the image to segment the image, and wherein said extracting invariant shape features of the object is performed based on the segmented image.

15. The method of claim 11, wherein said preprocessing comprises performing texture characterization of the image to segment the image, and wherein said extracting invariant shape features of the object is performed based on the segmented image.

16. The method of claim 1,

wherein the generalized invariant feature descriptor comprises a generalized invariant feature vector comprising respective components corresponding to the extracted invariant shape features, and wherein said classifying the object based on the extracted invariant shape features comprises:

computing a plurality of differences between the generalized invariant feature vector and respective generalized invariant feature vectors corresponding to a plurality of reference objects;

determining a minimum difference from the plurality of differences, wherein the minimum difference corresponds to a closest reference object of the plurality of reference objects; and

outputting an indication of the closest reference object as a classification of the object.

17. The method of claim 1,

wherein the generalized invariant feature descriptor comprises a generalized invariant feature vector comprising respective components corresponding to the extracted invariant shape features, and wherein said classifying the object based on the extracted invariant shape features comprises:

computing a plurality of differences between the generalized invariant feature vector and respective generalized invariant feature vectors corresponding to classes of reference objects of a plurality of reference objects, and wherein each respective generalized invariant feature vector comprises an average of generalized invariant feature vectors for a respective one or more reference objects;

determining a minimum difference from the plurality of differences, wherein the minimum difference corresponds to a closest class of the classes of reference objects; and

outputting an indication of the closest class of reference objects as a classification of the object.

18. The method of claim 1, further comprising:

making a decision based on the classification of the object.

19. The method of claim 18, wherein said making a decision based on the classification of the object comprises:

setting one or more tolerance thresholds for the classification;

determining one or more scores for the classification of the object;

comparing at least one of the one or more scores to at least one of the one or more tolerance thresholds;

if said comparing indicates that the classification is not valid, rejecting the classification; and

if said comparing indicates that the classification is valid, accepting the classification.

20. The method of claim 19, wherein said setting one or more tolerance thresholds, said determining one or more scores, and said comparing comprises:

setting a classification tolerance threshold;

setting an identification tolerance threshold;

determining a classification score for the classification of the object;

comparing the classification score with the classification tolerance threshold;

if said comparing the classification score with the classification tolerance threshold indicates that the classification is not valid,

determining an identification score for the classification of the object;

comparing the identification score with the identification tolerance threshold;

if said comparing the identification score with the identification tolerance threshold indicates that the classification is not valid,

performing said rejecting the classification; and

if said comparing the identification score with the identification tolerance threshold indicates that the classification is valid,

performing said accepting the classification; and

if said comparing the classification score with the classification tolerance threshold indicates that the classification is valid,

performing said accepting the classification.

21. The method of claim 1, wherein the object comprises a blob.

22. The method of claim 1, further comprising:

extracting one or more non-invariant features of the object; and

determining one or more non-invariant feature descriptors for the object based on the extracted one or more non-invariant features of the object.

23. The method of claim 22, wherein said classifying the object based on the extracted invariant shape features comprises:

classifying the object based on the extracted invariant shape features and the extracted one or more non-invariant shape features.

24. The method of claim 23, wherein said classifying the object based on the extracted invariant shape features and the extracted non-invariant shape features comprises:

computing a shape classifier output based on the extracted invariant shape features;

computing one or more respective non-invariant classifier outputs based on the extracted one or more non-invariant features;

weighting the shape classifier output, and each of the respective classifier outputs with respective classifier weighting factors, thereby generating a weighted shape classifier output, and one or more respective weighted non-invariant classifier outputs;

combining the weighted shape classifier output and the one or more respective weighted non-invariant classifier outputs to generate a classifier output; and

classifying the object based on the generated classifier output.

25. The method of claim 24,

wherein the one or more non-invariant features of the object comprise one or more of:

one or more scale features of the object; and

one or more reflection features of the object;

wherein said computing one or more respective non-invariant classifier outputs comprises;

computing a scale classifier output based on the extracted one or more scale features; and

/or

computing a reflection classifier output based on the extracted one or more reflection features

26. The method of claim 24 wherein said computing a shape classifier output based on the extracted invariant shape features and said computing one or more respective non-invariant classifier outputs based on the extracted one or more non-invariant features are performed substantially in parallel.

27. The method of claim 24,

wherein the generalized invariant feature descriptor comprises a generalized invariant feature vector comprising respective components corresponding to the extracted invariant shape features, and wherein said computing a shape classifier output comprises computing a plurality of distances between the generalized invariant feature vector and respective generalized invariant feature vectors corresponding to a plurality of reference objects;

wherein each of the one or more non-invariant feature descriptors comprises a respective non-invariant feature vector comprising at least one component corresponding to at least one of the one or more non-invariant features, and wherein said computing one or more respective non-invariant classifier outputs comprises;

for each of the one or more non-invariant feature descriptors;

computing a plurality of distances between the non-invariant feature vector and respective non-invariant feature vectors corresponding to the plurality of reference objects;

wherein said combining the weighted shape classifier output and the one or more respective weighted non-invariant classifier outputs to generate a classifier output comprises;

averaging respective distances of the weighted shape classifier output and the one or more respective weighted non-invariant classifier outputs corresponding to each of the plurality of reference objects, thereby computing a plurality of weighted average distances corresponding to the plurality of reference objects; and

wherein said classifying the object based on the generated classifier output comprises;

determining a minimum weighted average distance from the plurality of weighted average distances, wherein the minimum weighted average distance corresponds to a closest reference object of the plurality of reference objects; and

outputting an indication of the closest reference object as a classification of the object.

28. The method of claim 27,

wherein the distances between the generalized invariant feature vector and respective generalized invariant feature vectors corresponding to a plurality of reference objects each comprises a metric distance;

and

wherein the distances between the non-invariant feature vector and respective non-invariant feature vectors corresponding to the plurality of reference objects each comprises a respective non-metric distance.

29. The method of claim 24,

wherein the generalized invariant feature descriptor comprises a generalized invariant feature vector comprising respective components corresponding to the extracted invariant shape features, wherein said computing a shape classifier output comprises computing a plurality of distances between the generalized invariant feature vector and respective generalized invariant feature vectors corresponding to classes of reference objects of a plurality of reference objects, and wherein each respective generalized invariant feature vector comprises an average of generalized invariant feature vectors for a respective one or more reference objects;

wherein each of the one or more non-invariant feature descriptors comprises a respective non-invariant feature vector comprising at least one component corresponding to at least one of the one or more non-invariant features, and wherein said computing one or more respective non-invariant classifier outputs comprises;

for each of the one or more non-invariant feature descriptors;

computing a plurality of distances between the non-invariant feature vector and respective non-invariant feature vectors corresponding to the classes of reference objects;

wherein said combining the weighted shape classifier output and the one or more respective weighted non-invariant classifier outputs to generate a classifier output comprises;

averaging respective distances of the weighted shape classifier output and the one or more respective weighted non-invariant classifier outputs corresponding to each of the classes of reference objects, thereby computing a plurality of weighted average distances corresponding to the classes of reference objects; and

wherein said classifying the object based on the generated classifier output comprises;

determining a minimum weighted average distance from the plurality of weighted average distances, wherein the minimum weighted average distance corresponds to a closest class of the classes of reference objects; and

outputting an indication of the closest class of reference objects as a classification of the object.

30. The method of claim 29,

wherein the distances between the generalized invariant feature vector and respective generalized invariant feature vectors corresponding to classes of reference objects each comprises a metric distance;

and

wherein the distances between the non-invariant feature vector and respective non-invariant feature vectors corresponding to the classes of reference objects each comprises a respective non-metric distance.

31. The method of claim 1, further comprising:

determining if the object is to be classified using scale dependent features; and

if the object is to be classified using scale dependent features, determining a scale feature of the object.

32. The method of claim 31, wherein the scale feature of the object comprises:

an area of the object.

33. The method of claim 1, further comprising:

determining if the object is to be classified using reflection dependent features; and

if the object is to be classified using reflection dependent features, determining one or more reflection features of the object.

34. The method of claim 33, wherein said determining if the object is to be classified using reflection dependent features comprises:

computing a symmetry factor of the object; and

determining if the symmetry factor is less than a specified tolerance, wherein the symmetry factor being less than the specified tolerance indicates that object is to be classified using reflection dependent features.

35. The method of claim 34, wherein said determining one or more reflection features of the object comprises:

determining an orientation of the object;

determining an orientation of one or more maximum Feret diameters of the object;

determining a difference between the orientation of the object and the orientation of each of the one or more maximum Feret diameters of the object; and

if there is more than one maximum Feret diameter of the object, determining a minimum difference between the orientation of the object and the orientations of the one or more maximum Feret diameters of the object, wherein the one or more reflection features of the object comprises the minimum difference.

36. The method of claim 1, wherein the image comprises a plurality of objects, the method further comprising:

performing said extracting invariant shape features and said classifying for each of the plurality of objects.

37. A medium configured for analyzing an image, wherein the medium is configured to implement:

storing an image, wherein the image comprises an object;

extracting invariant shape features of the object using a generalized invariant feature descriptor; and

classifying the object based on the extracted invariant shape features.

38. The method of claim 37, wherein the generalized invariant feature descriptor comprises a generalized invariant feature vector comprising components corresponding to:

roundness of the object;

compactness of the object;

holes of the object; and

Hu Moments of the object.

39. The medium of claim 38, wherein the generalized invariant feature descriptor comprises a generalized invariant feature vector comprising respective components corresponding to:

circularity of the object;

elongation of the object;

perimeter-ratio-based convexity of the object;

area-ratio-based convexity of the object;

hole-perimeter-ratio of the object;

hole-area-ratio of the object;

a function of Hu Moment 1 of the object; and

a function of Hu Moment 2 of the object.

40. The medium of claim 37, wherein the medium is further configured to implement:

extracting one or more non-invariant features of the object; and

determining one or more non-invariant feature descriptors for the object based on the extracted one or more non-invariant features of the object.

41. The medium of claim 40, wherein said classifying the object based on the extracted invariant shape features comprises:

classifying the object based on the extracted invariant shape features and the extracted one or more non-invariant shape features.

42. The medium of claim 41, wherein said classifying the object based on the extracted invariant shape features and the extracted non-invariant shape features comprises:

computing a shape classifier output based on the extracted invariant shape features;

computing one or more respective non-invariant classifier outputs based on the extracted one or more non-invariant features;

weighting the shape classifier output, and each of the respective classifier outputs with respective classifier weighting factors, thereby generating a weighted shape classifier output, and one or more respective weighted non-invariant classifier outputs;

combining the weighted shape classifier output and the one or more respective weighted non-invariant classifier outputs to generate a classifier output; and

classifying the object based on the generated classifier output.

43. The medium of claim 42,

wherein the one or more non-invariant features of the object comprise one or more of:

one or more scale features of the object; and

one or more reflection features of the object;

wherein said computing one or more respective non-invariant classifier outputs comprises;

computing a scale classifier output based on the extracted one or more scale features; and

/or

computing a reflection classifier output based on the extracted one or more reflection features.

44. The medium of claim 42 wherein said computing a shape classifier output based on the extracted invariant shape features and said computing one or more respective non-invariant classifier outputs based on the extracted one or more non-invariant features are performed substantially in parallel.

45. The medium of claim 37, wherein the medium comprises a memory medium.

46. The medium of claim 37, wherein the medium comprises a carrier medium.

47. A system for performing object analysis, the system comprising:

a processor;

a memory medium coupled to the processor, wherein the memory medium stores an image, wherein the image comprises an object, and wherein the memory medium stores program instructions which are executable by the processor to;

extract invariant shape features of the object using a generalized invariant feature descriptor; and

classify the object based on the extracted invariant shape features.

48. The method of claim 47, wherein the generalized invariant feature descriptor comprises a generalized invariant feature vector comprising components corresponding to:

roundness of the object;

compactness of the object;

holes of the object; and

Hu Moments of the object.

49. The system of claim 48, wherein the generalized invariant feature descriptor comprises a generalized invariant feature vector comprising respective components corresponding to:

circularity of the object;

elongation of the object;

perimeter-ratio-based convexity of the object;

area-ratio-based convexity of the object;

hole-perimeter-ratio of the object;

hole-area-ratio of the object;

a function of Hu Moment 1 of the object; and

a function of Hu Moment 2 of the object.

50. The method of claim 47, further comprising:

extracting one or more non-invariant features of the object; and

determining one or more non-invariant feature descriptors for the object based on the extracted one or more non-invariant features of the object.

51. A system for analyzing an image, the system comprising:

means for receiving an image, wherein the image comprises an object;

means for extracting invariant shape features of the object using a generalized invariant feature descriptor; and

means for classifying the object based on the extracted invariant shape features.

52. The method of claim 51, wherein the generalized invariant feature descriptor comprises a generalized invariant feature vector comprising components corresponding to:

roundness of the object;

compactness of the object;

holes of the object; and

Hu Moments of the object.

54. The method of claim 51, further comprising:

extracting one or more non-invariant features of the object; and

determining one or more non-invariant feature descriptors for the object based on the extracted one or more non-invariant features of the object.

53. The system of clam 52, wherein the generalized invariant feature descriptor comprises a generalized invariant feature vector comprising respective components corresponding to:

circularity of the object;

elongation of the object;

perimeter-ratio-based convexity of the object;

area-ratio-based convexity of the object;

hole-perimeter-ratio of the object;

hole-area-ratio of the object;

a function of Hu Moment 1 of the object; and

a function of Hu Moment 2 of the object.