Image segmentation using statistical clustering with saddle point detection

1. A method for partitioning an image data set comprising a plurality of data points into a plurality of statistically meaningful clusters, the method comprising:

receiving a data set indicative of an external image;

decomposing the data set by a mean shift based data decomposition; and

partitioning the data set by associating each data point with one of a plurality of clusters in response to the mean shift based data decomposition.

2. A method as defined in claim 1 wherein the data set comprises an image and partitioning the data set provides image segmentation.

3. A method as defined in claim 2 wherein the image is segmented as clusters of data points.

4. A method as defined in claim 2 wherein the image is a medical image.

5. A method as defined in claim 2 wherein the image is a video data frame.

6. A method as defined in claim 1 wherein the data set comprises audio data.

7. A method for characterizing the statistical significance of at least one of a plurality of clusters of data points indicative of an external image, the method comprising:

selecting a cluster; and

computing the value of a statistical measure for a saddle point lying on the border of the selected cluster and having the highest density.

8. A method as defined in claim 7 wherein computing the statistical measure comprises detecting a saddle point.

9. A method as defined in claim 8 wherein detecting a saddle point comprises detecting first-order saddle points having a Hessian matrix with one positive eigen-value.

10. A method for merging a plurality of clusters of data points indicative of an external image, the method comprising testing if the value of a statistical measure for a saddle point corresponding to a particular cluster is smaller than a threshold, and if the test is true, then merging the cluster with a neighboring cluster.

11. A method for image segmentation on data indicative of an external image using statistical clustering with saddle point detection, the method comprising:

representing the image data in a joint space of dimension d=r+2 that includes two special coordinates, where r=1 for gray-scale images, r=3 for color images, and r>3 for multi-spectral images;

partitioning the data set comprising a plurality of image data points into a plurality of statistically meaningful clusters by decomposing the data set by a mean shift based data decomposition; and

characterizing a statistical significance of at least one of a plurality of clusters of data points by:

selecting a cluster; and

computing the value of a statistical measure for the saddle point lying on the border of the selected cluster and having the highest density.

12. A method as defined in claim 11 , further comprising testing if the value of the statistical measure for a saddle point corresponding to a particular cluster is smaller than a threshold, and if the test is true, then merging the cluster with a neighboring cluster.

13. A method as defined in claim 11 wherein computing the statistical measure comprises detecting a saddle point.

14. A method as defined in claim 13 wherein detecting a saddle point comprises detecting first-order saddle points having a Hessian matrix with one positive eigen-value.

15. A method as defined in claim 11 wherein the mean shift paths are defined by a mean shift based decomposition, the decomposition comprising:

for each element in the data set, running the mean shift procedure and storing the peak convergence point;

identifying clusters of convergence points by linking together all elements within a distance measure from each other; and

for each element of the cluster set, joining together all the data points having the corresponding convergence point.

16. A method as defined in claim 13 wherein the saddle point is defined by a saddle point detection algorithm comprising:

receiving a data partitioning into a cluster and another set;

following a mean shift path until a predetermined condition is satisfied; and

following a different mean shift path until convergence to the saddle point.

17. A method for characterizing the statistical significance of a border between adjacent clusters of data points indicative of an external image, the method comprising:

analyzing the border between adjacent clusters to find at least one saddle point;

selecting the saddle point with the highest density value;

computing the value of a statistical measure for the selected saddle point on the border; and

if the value of the statistical measure for the selected saddle point of the border is smaller than a threshold, then merging the clusters adjacent to the border into a single cluster.

18. A method as defined in claim 17 wherein the at least one saddle point is a first-order saddle point.

19. A method as defined in claim 17 , further comprising using a statistical test relative to the first-order saddle point to determine the existence of a border between two neighboring clusters.

20. A method as defined in claim 17 , further comprising repeating the step of characterizing for each of a plurality of borders between clusters.

21. A method as defined in claim 17 , further comprising:

repeating the step of characterizing for each of at least one of a plurality of clusters and a plurality of borders between clusters until the confidence level of each cluster or border is greater than a threshold; and

merging adjacent clusters if the confidence level of each cluster or border is less than a threshold.

22. A method for image segmentation on data indicative of an external image using statistical clustering with saddle point detection, the method comprising:

representing the image data in a joint space of dimension d=r+2 that includes two special coordinates, where r=1 for gray-scale images, r=3 for color images, and r>3 for multi-spectral images;

partitioning the data set comprising a plurality of image data points into a plurality of statistically meaningful clusters by decomposing the data set by a mean shift based data decomposition; and

characterizing a statistical significance of a border between adjacent clusters of data points by:

analyzing the border between adjacent clusters to find at least one saddle point;

selecting the saddle point with the highest density value;

computing the value of a statistical measure for the selected saddle point on the border; and

if the value of the statistical measure for the selected saddle point of the border is smaller than a threshold, then merging the clusters adjacent to the border into a single cluster.

23. A method as defined in claim 22 wherein the mean shift paths are defined by a mean shift based decomposition, the decomposition comprising:

for each element in the data set, running the mean shift procedure and storing the peak convergence point;

identifying clusters of convergence points by linking together all elements within a distance measure from each other; and

for each element of the cluster set, joining together all the data points having the corresponding convergence point.

24. A method as defined in claim 22 wherein the saddle point is defined by a saddle point detection algorithm comprising:

receiving a data partitioning into a cluster and another set;

following a mean shift path until a predetermined condition is satisfied; and

following a different mean shift path until convergence to the saddle point.

25. A system for image segmentation on data indicative of an external image using statistical clustering with saddle point detection, the system comprising:

representation means for representing the image data in a joint space of dimension d=r+2 that includes two special coordinates, where r=1 for gray-scale images, r=3 for color images, and r>3 for multi-spectral images;

partitioning means for partitioning the data set comprising a plurality of image data points into a plurality of statistically meaningful clusters by decomposing the data set by a mean shift based data decomposition; and

characterization means for characterizing a statistical significance of at least one of a plurality of clusters of data points by:

selecting a cluster; and

computing the value of a statistical measure for the saddle point lying on the border of the selected cluster and having the highest density.

26. A system for image segmentation on data indicative of an external image using statistical clustering with saddle point detection, the system comprising:

representation means for representing the image data in a joint space of dimension d=r+2 that includes two special coordinates, where r=1 for gray-scale images, r=3 for color images, and r>3 for multi-spectral images;

partitioning means for partitioning the data set comprising a plurality of image data points into a plurality of statistically meaningful clusters by decomposing the data set by a mean shift based data decomposition; and

characterization means for characterizing a statistical significance of a border between adjacent clusters of data points by:

analyzing the border between adjacent clusters to find at least one saddle point;

selecting the saddle point with the highest density value;

computing the value of a statistical measure for the selected saddle point on the border; and

if the value of the statistical measure for the selected saddle point of the border is smaller than a threshold, then merging the clusters adjacent to the border into a single cluster.

27. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform program steps for image segmentation on data indicative of an external image using statistical clustering with saddle point detection, the program steps comprising:

representing the image data in a joint space of dimension d=r+2 that includes two special coordinates, where r=1 for gray-scale images, r=3 for color images, and r>3 for multi-spectral images;

partitioning the data set comprising a plurality of image data points into a plurality of statistically meaningful clusters by decomposing the data set by a mean shift based data decomposition; and

characterizing a statistical significance of at least one of a plurality of clusters of data points by:

selecting a cluster; and

computing the value of a statistical measure for the saddle point lying on the border of the selected cluster and having the highest density.

28. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform program steps for image segmentation on data indicative of an external image using statistical clustering with saddle point detection, the program steps comprising:

representing the image data in a joint space of dimension d=r+2 that includes two special coordinates, where r=1 for gray-scale images, r=3 for color images, and r>3 for multi-spectral images;

partitioning the data set comprising a plurality of image data points into a plurality of statistically meaningful clusters by decomposing the data set by a mean shift based data decomposition; and

characterizing a statistical significance of a border between adjacent clusters of data points by:

analyzing the border between adjacent clusters to find at least one saddle point;

selecting the saddle point with the highest density value;

computing the value of a statistical measure for the selected saddle point on the border; and

if the value of the statistical measure for the selected saddle point of the border is smaller than a threshold, then merging the clusters adjacent to the border into a single cluster.

29. A method for performing image segmentation on data indicative of an external image using statistical clustering with saddle point detection comprising the steps of:

receiving one of image data, video data, speech data, handwriting data and audio data, and extracting feature data points from the data;

partitioning the data into one or more modes and determining a mean/covariance pair for each mode, wherein each data point is associated with a detected mode and a corresponding mean/covariance pair of the mode for each of a plurality of analysis scales;

for each data point, determining the most stable mean/covariance pair associated with the data point; and

for each data point, selecting for output the covariance of the most stable mean/covariance pair for the data point.

30. A method as defined in claim 29 wherein the step of partitioning the data comprises:

decomposing the data set by a mean shift based data decomposition; and

segmenting the data set by associating each data point in response to the mean shift based data decomposition with one of a plurality of clusters.