Methods and systems for identifying and localizing objects based on features of the objects that are mapped to a vector

• US 7,958,063 B2
• Filed: 04/25/2007
• Issued: 06/07/2011
• Est. Priority Date: 11/11/2004
• Status: Expired due to Fees

• Current Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Cleveland, W. Louis, Long, Xi, Yao, Y. Lawrence
• Primary Examiner(s): STARKS, WILBERT L
• Application Number:
  US11/789,571
• Publication Number:
  US 20080082468A1
• Time in Patent Office: 1,504 Days
• Field of Search: 706/12, 706/45
• US Class Current: 706/12
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 10/774 Generating sets of training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06V 20/698 Matching; Classification

Abstract

A method of identifying and localizing objects belonging to one of three or more classes, includes deriving vectors, each being mapped to one of the objects, where each of the vectors is an element of an N-dimensional space. The method includes training an ensemble of binary classifiers with a CISS technique, using an ECOC technique. For each object corresponding to a class, the method includes calculating a probability that the associated vector belongs to a particular class, using an ECOC probability estimation technique. In another embodiment, increased detection accuracy is achieved by using images obtained with different contrast methods. A nonlinear dimensional reduction technique, Kernel PCA, was employed to extract features from the multi-contrast composite image. The Kernel PCA preprocessing shows improvements over traditional linear PCA preprocessing possibly due to its ability to capture high-order, nonlinear correlations in the high dimensional image space.

Claims

1. A method of identifying one or more objects, wherein each of the one or more objects belongs to a first class or to a second class, the first class being heterogeneous and having C subclasses, the second class being less heterogenous than the first class, comprising:

deriving a plurality of vectors each being mapped to one of the one or more objects, wherein each of the plurality of vectors is an element of an N-dimensional space;

preprocessing each of the plurality of vectors using a Fisher Linear Discriminant, wherein the preprocessing reduces the dimensionality of each of the plurality of vectors to M dimensions, wherein M is less than or equal to C; and

,

classifying the preprocessed vectors by (i) grouping the preprocessed vectors belonging to any of the C subclasses of the first class into a first set of vectors, and (ii) grouping the preprocessed vectors belonging to the second class into a second set of vectors.

2. The method of claim 1, wherein each of the plurality of vectors includes information mapped from a digital image.

3. The method of claim 2, wherein the information mapped from a digital image includes a pixel patch.

4. The method of claim 1, wherein the preprocessed vectors are classified with at least one of a support vector machine and an artificial neural network.

5. The method of claim 4, further including training the support vector machine with a compensatory iterative sample selection technique.

6. The method of claim 5, wherein the compensatory iterative sample selection technique comprises:

(a) selecting a first working set of pre-classified objects from a set of training objects;

(b) training the support vector machine with the first working set;

(c) testing the support vector machine with pre-classified objects from the set of training objects not included in the first working set so as to produce a set of correctly classified objects and a set of incorrectly classified objects;

(d) selecting a replacement set of pre-classified objects from the set of incorrectly classified objects, and replacing a subset of the working set with the replacement set;

(e) repeating steps (b), (c) and (d) until the set of incorrectly classified objects does not decrease in size for subsequent iterations of steps (b), (c) and (d).

7. A method of identifying one or more objects in a digital image, wherein each of the one or more objects belongs to a first class or to a second class, the first class being heterogeneous and having C subclasses, and the second class being less heterogeneous than the first class, comprising:

deriving a plurality of pixel patches from the digital image, each being mapped to one of the one or more objects, wherein each of the plurality of pixel patches is an element of an N-dimensional space;

preprocessing each of the plurality of pixel patches using a Fisher Linear Discriminant, wherein the preprocessing reduces the dimensionality of each of the pixel patches to M dimensions, wherein M is less than or equal to C; and

,

classifying the preprocessed pixel patches by (i) grouping the preprocessed pixel patches belonging to any of the C subclasses of the first class into a first set of pixel patches, and (ii) grouping the preprocessed pixel patches belonging to the second class into a second set of pixel patches.

8. The method of claim 7, wherein the preprocessed pixel patches are classified with a support vector machine.

9. The method of claim 8, further including training the support vector machine with a compensatory iterative sample selection technique.

10. The method of claim 9, wherein the compensatory iterative sample selection technique comprises:

(a) selecting a first working set of pre-classified objects from a set of training objects;

(b) training the support vector machine with the first working set;

(c) testing the support vector machine with pre-classified objects from the set of training objects not included in the first working set so as to produce a set of correctly classified objects and a set of incorrectly classified objects;

(d) selecting a replacement set of pre-classified objects from the set of incorrectly classified objects, and replacing a subset of the working set with the replacement set;

(e) repeating steps (b), (c) and (d) until the set of incorrectly classified objects does not decrease in size for subsequent iterations of steps (b), (c) and (d).

11. The method of claim 7, further including localizing an object in the digital image by identifying a pixel patch having an object that is centered within the pixel patch.

12. The method of claim 7, wherein the first class homogeneous class includes cells, and the second heterogeneous class includes non-cells.

13. A method of identifying and localizing one or more objects, wherein each of the one or more objects belongs to either a first class or a second class, comprising:

deriving a plurality of vectors each being mapped to one of the one or more objects, wherein each of the plurality of vectors is an element of an N-dimensional space;

training a support vector machine with a compensatory iterative sample selection technique; and

,

processing the plurality of vectors with the support vector machine, so as to classify each of the plurality of vectors into either the first class or the second class.

14. The method of claim 13, wherein each of the plurality of vectors includes information mapped from a digital image.

15. The method of claim 14, wherein the information mapped from a digital image includes a pixel patch.

16. The method of claim 13, wherein the compensatory iterative sample selection technique comprises:

(a) selecting a first working set of pre-classified objects from a set of training objects;

(b) training the support vector machine with the first working set;

(c) testing the support vector machine with pre-classified objects from the set of training objects not included in the first working set so as to produce a set of correctly classified objects and a set of incorrectly classified objects;

(d) selecting a replacement set of pre-classified objects from the set of incorrectly classified objects, and replacing a subset of the working set with the replacement set;

(e) repeating steps (b), (c) and (d) until the set of incorrectly classified objects does not decrease in size for subsequent iterations of steps (b), (c) and (d).

17. The method of claim 13, wherein the objects are in a digital image.

18. The method of claim 17, wherein the objects are cells.

19. A method of identifying and localizing one or more objects in a digital image, wherein each of the one or more objects belongs to one of three or more classes, comprising:

deriving a plurality of pixel patches from the digital image, each of the plurality of pixel patches being mapped to one of the one or more objects, wherein each of the plurality of pixel patches is an element of an N-dimensional space;

training an ensemble of binary classifiers using an Error Correcting Output Coding technique; and

,

for each object, calculating a probability that the pixel patch associated with the object belongs to a particular one of the three or more classes, using the Error Correcting Output Coding probability estimation technique;

generating a confidence map for each class using the probability calculated for the pixel patch as a confidence value within the confidence map;

comparing peaks in the confidence map for the class with corresponding peaks in confidence maps for other classes, and using a highest peak to assign class membership; and

,

determining localization of the object corresponding to the highest peak by determining pixel coordinates of the highest peak.

20. A computer readable medium including stored instructions adapted for execution on a processor, comprising:

instructions for deriving a plurality of vectors each being mapped to one of the one or more objects, wherein each of the plurality of vectors is an element of an N-dimensional space;

instructions for preprocessing each of the plurality of vectors using a Fisher Linear Discriminant, wherein the preprocessing reduces the dimensionality of each of the plurality of vectors to M dimensions, wherein M is less than or equal to C; and

,

instructions for classifying the preprocessed vectors by (i) grouping the preprocessed vectors belonging to any of the C subclasses of the first class into a first set of vectors, and (ii) grouping the preprocessed vectors belonging to the second class into a second set of vectors.

21. A computer readable medium including stored instructions adapted for execution on a processor, comprising:

instructions for deriving a plurality of pixel patches from the digital image, each being mapped to one of the one or more objects, wherein each of the plurality of pixel patches is an element of an N-dimensional space;

instructions for preprocessing each of the plurality of pixel patches using a Fisher Linear Discriminant, wherein the preprocessing reduces the dimensionality of each of the pixel patches to M dimensions, wherein M is less than or equal to C; and

,

instructions for classifying the preprocessed pixel patches by (i) grouping the preprocessed pixel patches belonging to any of the C subclasses of the first class into a first set of pixel patches, and (ii) grouping the preprocessed pixel patches belonging to the second class into a second set of pixel patches.

22. A computer readable medium including stored instructions adapted for execution on a processor, comprising:

instructions for deriving a plurality of pixel patches from the digital image, each of the plurality of pixel patches being mapped to one of the one or more objects, wherein each of the plurality of pixel patches is an element of an N-dimensional space;

instructions for training an ensemble of binary classifiers with a compensatory iterative sample selection technique, using an Error Correcting Output Coding technique;

instructions for calculating for each object, a probability that the pixel patch belongs to a particular one of the three or more classes, using the Error Correcting Output Coding probability estimation technique;

instructions for generating a confidence map for each class using the probability calculated for the pixel patch as a confidence value within the confidence map;

instructions for comparing peaks in the confidence map for the class with corresponding peaks in confidence maps for other classes, and using a highest peak to assign class membership; and

,

instructions for determining localization of the object corresponding to the highest peak by determining pixel coordinates of the highest peak.

23. A method of classifying one or more cells in a specimen, wherein each of the one or more cells belongs to one of two or more classes, comprising:

deriving a plurality of vectors from a plurality of pixel patches, including at least pixel patches from a digital image of the specimen that is of a first contrast type, and pixel patches from a digital image of the specimen that is of a second contrast type distinct from the first contrast type;

preprocessing the plurality of vectors using a non-linear feature extraction method, wherein the preprocessing reduces the dimensionality of the vectors;

generating a plurality of confidence maps, based on the plurality of vectors, wherein each of the plurality of confidence maps corresponds to a particular one of the two or more classes, and wherein each confidence value in that confidence map corresponds to a probability that a vector belongs to that class;

identifying a cell at a location of a peak in a confidence map; and

assigning the cell to the particular one of the two or more classes corresponding to the highest peak among the plurality of confidence maps at the location.

24. The method of claim 23 wherein the non-linear feature extraction method is Kernel Principal Component Analysis.

25. The method of claim 23 wherein the first contrast type is at least one of bright field, phase contrast, and Hoffman modulation contrast.

26. The method of claim 23 wherein the second contrast type is at least one of bright field, phase contrast, and Hoffman modulation contrast.

27. The method of claim 23 wherein the probability that a vector belongs to a class is generated using Error Correcting Output Code probability estimation.

28. The method of claim 23 further comprising the step of:

determining localization of the cell corresponding to the highest peak by determining pixel coordinates of the highest peak.

29. A computer readable medium including stored instructions adapted for execution on a processor, comprising:

instructions for deriving a plurality of vectors from a plurality of pixel patches, including at least pixel patches from a digital image of the specimen that is of a first contrast type, and pixel patches from a digital image of the specimen that is of a second contrast type distinct from the first contrast type;

instructions for preprocessing the plurality of vectors using a non-linear feature extraction method, wherein the preprocessing reduces the dimensionality of the vectors;

instructions for generating a plurality of confidence maps, based on the plurality of vectors, wherein each of the plurality of confidence maps corresponds to a particular one of the two or more classes, and wherein each confidence value in that confidence map corresponds to a probability that a vector belongs to that class;

instructions for identifying a cell at a location of a peak in a confidence map; and

instructions for assigning the cell to the particular one of the two or more classes corresponding to the highest peak among the plurality of confidence maps at the location.

30. A system of identifying one or more objects, wherein each of the one or more objects belongs to a first class or to a second class, the first class being heterogeneous and having C subclasses, the second class being less heterogenous than the first class, comprising:

means for deriving a plurality of vectors each being mapped to one of the one or more objects, wherein each of the plurality of vectors is an element of an N-dimensional space;

means for preprocessing each of the plurality of vectors using a Fisher Linear Discriminant, wherein the preprocessing reduces the dimensionality of each of the plurality of vectors to M dimensions, wherein M is less than or equal to C; and

,

means for classifying the preprocessed vectors by (i) grouping the preprocessed vectors belonging to any of the C subclasses of the first class into a first set of vectors, and (ii) grouping the preprocessed vectors belonging to the second class into a second set of vectors.

31. The system of claim 30 wherein each of the plurality of vectors includes information mapped from a digital image.

32. The system of claim 31, wherein the information mapped from a digital image includes a pixel patch.

33. The system of claim 30, wherein the preprocessed vectors are classified with at least one of a support vector machine and an artificial neural network.

34. The system of claim 33, further including means for training the support vector machine with a compensatory iterative sample selection technique.

35. The system of claim 34, wherein the compensatory iterative sample selection technique comprises:

(a) means for selecting a first working set of pre-classified objects from a set of training objects;

(b) means for training the support vector machine with the first working set;

(c) means for testing the support vector machine with pre-classified objects from the set of training objects not included in the first working set so as to produce a set of correctly classified objects and a set of incorrectly classified objects;

(d) means for selecting a replacement set of pre-classified objects from the set of incorrectly classified objects, and replacing a subset of the working set with the replacement set;

(e) means for repeating the operations of (b), (c) and (d) until the set of incorrectly classified objects does not decrease in size for subsequent iterations of the operations of (b), (c) and (d).

36. A system of identifying one or more objects in a digital image, wherein each of the one or more objects belongs to a first class or to a second class, the first class being heterogeneous and having C subclasses, and the second class being less heterogeneous than the first class, comprising:

means for deriving a plurality of pixel patches from the digital image, each being mapped to one of the one or more objects, wherein each of the plurality of pixel patches is an element of an N-dimensional space;

means for preprocessing each of the plurality of pixel patches using a Fisher Linear Discriminant, wherein the preprocessing reduces the dimensionality of each of the pixel patches to M dimensions, wherein M is less than or equal to C; and

,

means for classifying the preprocessed pixel patches by (i) grouping the preprocessed pixel patches belonging to any of the C subclasses of the first class into a first set of pixel patches, and (ii) grouping the preprocessed pixel patches belonging to the second class into a second set of pixel patches.

37. The system of claim 36, wherein the preprocessed pixel patches are classified with at least one of a support vector machine and an artificial neural network.

38. The system of claim 37, further including means for training the support vector machine with a compensatory iterative sample selection technique.

39. The system of claim 38, wherein the compensatory iterative sample selection technique comprises:

(a) means for selecting a first working set of pre-classified objects from a set of training objects;

(b) means for training the support vector machine with the first working set;

(c) means for testing the support vector machine with pre-classified objects from the set of training objects not included in the first working set so as to produce a set of correctly classified objects and a set of incorrectly classified objects;

(d) means for selecting a replacement set of pre-classified objects from the set of incorrectly classified objects, and replacing a subset of the working set with the replacement set;

(e) means for repeating the operations of (b), (c) and (d) until the set of incorrectly classified objects does not decrease in size for subsequent iterations of operations of (b), (c) and (d).

40. A system of classifying one or more cells in a specimen, wherein each of the one or more cells belongs to one of two or more classes, comprising:

means for deriving a plurality of vectors from a plurality of pixel patches, including at least pixel patches from a digital image of the specimen that is of a first contrast type, and pixel patches from a digital image of the specimen that is of a second contrast type distinct from the first contrast type;

means for preprocessing the plurality of vectors using a non-linear feature extraction method, wherein the preprocessing reduces the dimensionality of the vectors;

means for generating a plurality of confidence maps, based on the plurality of vectors, wherein each of the plurality of confidence maps corresponds to a particular one of the two or more classes, and wherein each confidence value in that confidence map corresponds to a probability that a vector belongs to that class;

means for identifying a cell at a location of a peak in a confidence map; and

means for assigning the cell to the particular one of the two or more classes corresponding to the highest peak among the plurality of confidence maps at the location.