Method and apparatus for detection of events or novelties over a change of state

• US 6,064,770 A
• Filed: 06/27/1995
• Issued: 05/16/2000
• Est. Priority Date: 06/27/1995
• Status: Expired due to Fees

• Current Assignee: The National Research Council (The National Academies of Science)
• Original Assignee: The National Research Council (The National Academies of Science)
• Inventors: Scarth, Gordon B., Somorjai, R. L.
• Primary Examiner(s): BELLA, MATTHEW C
• Application Number:
  US08/496,132
• Time in Patent Office: 1,785 Days
• Field of Search: 382/225, 382/155-157, 382/159, 382/288, 382/128, 382/254, 382/274, 364/274.9, 364/276.6, 364/972.7, 395/21, 395/23
• US Class Current: 382/225
• CPC Class Codes: G06F 18/10 Pre-processing; Data cleansing
• CPC Class Codes: G06F 18/2321 using statistics or function optimisation, e.g. modelling of probability density functions
• CPC Class Codes: G06F 18/2433 Single-class perspective, e.g. one-against-all classification; Novelty detection; Outlier detection
• CPC Class Codes: G06N 5/048 Fuzzy inferencing
• CPC Class Codes: G06V 10/763 Non-hierarchical techniques, e.g. based on statistics of modelling distributions

Abstract

A significant problem is unsupervised detection of events in the digital image representation of objects or bodies acquired at logically different states. To detect events a set of sample data points is selected, and normalized using a novel technique to desensitize the analysis to the intensity level of the data. The normalized data are presented to a clustering algorithm, preferably the fuzzy C-Means clustering algorithm which groups the data into a user-specified number of clusters. The resulting clusters are not affected by human bias or preconceived notions, since the process is independent of prior knowledge of the events. The cluster centroids identify the characteristics of the events and the cluster maps depict the image domains associated with the events. The invention is equally applicable to normal and abnormal events and is capable of detecting expected and unexpected results.

Claims

1. A method for detecting events or novelties in data representing one or more objects, said method comprising:

providing a data set including plural images comprising respective data arrays representing the one or more objects at logically different states, with each array having plural data points and with corresponding data points in the data arrays having data values that may vary across the arrays;

minimizing intensity variations between the data arrays by normalizing the data using a normalization method selected from the group consisting of percent change normalization, baseline subtraction normalization and robust normalization;

determining data value patterns for sets of corresponding data points across the arrays; and

clustering the data value patterns into plural clusters according to data value patterns across the arrays.

2. A method according to claim 1 comprising clustering the data value patterns using a fuzzy C-means clustering algorithm.

3. A method according to claim 2 including the step of calculating a centroid of each cluster.

4. A method according to claim 2 including the step of calculating a membership map of each cluster.

5. A method according to claim 4 including the step of displaying the membership map of selected ones of the clusters.

6. A method according to claim 1 including the preliminary step of collecting the data of the respective data arrays at different times whereby the data points of each cluster have similar data value behaviors across time.

7. A method according to claim 1 wherein each data array represents an image of an object.

8. A method according to claim 7 including the step of displaying an image of the data points associated with selected ones of the clusters.

9. A method according to claim 8 comprising displaying the data points associated with the selected ones of the clusters in different colours.

10. A method according to claim 3 including the step of displaying the centroids of selected ones of the clusters.

11. A method according to claim 1 including, before clustering the data points, filtering the data to remove selected signal components.

12. A method according to claim 1 including, before clustering the data points, registering the data arrays.

13. A method according to claim 1 comprising registering the arrays before normalization.

14. Apparatus for detecting events or novelties comprising sequential changes in the logical state of one or more objects, said apparatus comprising:

data collection means for collecting a data set, including

means for collecting plural images comprising respective data arrays representing logically different states of said one or more objects, with each array comprising plural data points and with corresponding data points in the data arrays having data values that may vary across the arrays;

data storage means for recording the data set;

normalizing calculator means for minimizing intensity variations between the data arrays by normalizing the data before it is clustered by the clustering calculator means, the normalizing calculator means comprising;

robust normalization means for robust normalization of the data,

percent change normalization means for percent change normalization of the data,

baseline subtraction normalization means for baseline subtraction normalization of the data, and

selector means for selecting one of said normalization means for normalizing the data;

means for determining data value patterns for sets of corresponding data points across the arrays; and

clustering calculator means for clustering the corresponding data value patterns into clusters according to data value patterns across the arrays.

15. Apparatus according to claim 14 including means for identifying uninteresting domains in the data set and means for eliminating the data points of the uninteresting domains from the data points to be clustered.

16. Apparatus according to claim 15 wherein the means for identifying uninteresting domains in the data set comprise means for statistically analyzing the data.

17. Apparatus according to claim 14 including means for filtering the data to remove selected signal components before clustering the data points.

18. Apparatus according to claim 14 including, means for registering the data arrays.

19. Apparatus according to claim 14 wherein the clustering calculator means comprise means for clustering the data with a fuzzy C-means clustering algorithm.

20. Apparatus according to claim 14 wherein the means for collecting plural data arrays comprise means for collecting the respective data arrays at different times whereby the data points of each cluster have similar data value behaviors across time.

21. Apparatus according to claim 20 wherein the means for collecting the plural data arrays comprise means for collecting data representing images of an object.

22. Apparatus according to claim 21 comprising means for registering the data arrays to align the images before normalization.

23. Apparatus according to claim 14 wherein the clustering calculator means include means for calculating the centroids of selected ones of the clusters.

24. Apparatus according to claim 23 including means for displaying the centroid of each selected cluster.

25. Apparatus according to claim 23 wherein the clustering calculator means include means for calculating a membership map of each cluster.

26. Apparatus according to claim 25 including means for displaying the membership maps of selected ones of the clusters.

27. Apparatus according to claim 26 comprising means for displaying the membership maps of the selected ones of the clusters in different colours.

28. Apparatus according to claim 23 including means for selecting clusters and data store means for storing the data values of data points associated with the selected clusters.

29. Apparatus according to claim 28 wherein the data store means comprise means for storing the centroids of the selected clusters.