Hierarchical clustering using correlation metric and spatial continuity constraint
Large data sets are analyzed by hierarchical clustering using correlation as a similarity measure. This provides results that are superior to those obtained using a Euclidean distance similarity measure. A spatial continuity constraint may be applied in hierarchical clustering analysis of images.
1. A computer-implemented method for processing a data set composed of a plurality of data vectors that each includes a plurality of data values respectively associated with a plurality of variables in a variable space, comprising:
Populating a first data structure with a plurality of entries that correspond to respective ones of said data vectors; and
iteratively repeating operations of:
performing correlation calculations to determine for every pair of entries in said first data structure a correlation value indicative of a correlation between the associated pair of data vectors,
using the correlation values to identify one said pair of entries that has an associated pair of data vectors are closer to one another in the variable space than any other pair of data vectors associated with any other pair of entries,
recording the identified pair of entries in a second data structure,
merging the pair of data vectors associated with the identified pair of entries to define a merged data vector, and
replacing the identified pair of entries in the first data structure with an entry corresponding to the merged data vector.
2. The method of claim 1 , wherein said performing correlation calculations includes calculating for each said data vector of each said pair a mean value and a standard deviation value associated with the data values of said data vector.
3. The method of claim 1 , wherein said data set includes electron backscattered diffraction (EBSD) data.
4. A computer-readable storage medium which provides instructions that, when executes by a machine, cause the machine to perform operations to process a data set composed of a plurality of data vectors that each includes a plurality of data values respectively associated with a plurality of variables in a variable space, said operations comprising:
Populating a first data structure with a plurality of entries that correspond to respective ones of said data vectors; and
iteratively repeating operations of:
performing correlation calculations to determine for every pair of entries in said first data structure a correlation value indicative of a correlation between the associated pair of data vectors,
using the correlation values to identify one said pair of entries that has an associated pair of data vectors are closer to one another in the variable space than any other pair of data vectors associated with any other pair of entries,
recording the identified pair of entries in a second data structure,
merging the pair of data vectors associated with the identified pair of entries to define a merged data vector, and
replacing the identified pair of entries in the first data structure with an entry corresponding to the merged data vector.
5. The storage medium of claim 4 , wherein said performing correlation calculations includes calculating for each said data vector of each said pair a mean value and a standard deviation value associated with the data values of said data vector.
6. An apparatus for processing a data set composed of a plurality of data vectors that each includes a plurality of data values respectively associated with a plurality of variables in a variable space, comprising:
An input for receiving said plurality of data vectors; and
A data processing apparatus coupled to said input, said data processing apparatus configured to
Populating a first data structure with a plurality of entries that correspond to respective ones of said data vectors; and
iteratively repeating operations of:
performing correlation calculations to determine for every pair of entries in said first data structure a correlation value indicative of a correlation between the associated pair of data vectors,
using the correlation values to identify one said pair of entries that has an associated pair of data vectors are closer to one another in the variable space than any other pair of data vectors associated with any other pair of entries,
recording the identified pair of entries in a second data structure,
merging the pair of data vectors associated with the identified pair of entries to define a merged data vector, and
replacing the identified pair of entries in the first data structure with an entry corresponding to the merged data vector.
7. The apparatus of claim 1 , wherein said performing correlation calculations includes calculating for each said data vector of each said pair a mean value and a standard deviation value associated with the data values of said data vector.
8. A computer-implemented method for processing an image represented by an array of pixel vectors that each represents a respective spatial portion of the image and includes a plurality of data values respectively associated with a plurality of variables in an image variable space, comprising:
populating a first data structure with a plurality of entries that correspond to respective to respective ones of said pixel vectors; and
iteratively performing operations of:
for each entry in the first data structure, using a proximity metric to associate the entry with another entry and thereby identify a pair of entries, wherein said another entry is selected from a subset of entries that has an respectively associated pixel vectors represent spatial portions of the image that respectively border a spatial
portion of the image represented by the pixel vector associated with the entry, and wherein the pixel vector associated with said another entry is, among the pixel vectors associated with the subset of entries, closest in the image variable space to the pixel vector associated with the entry,
using the proximity metric to identify one said pair of entries whose associated pair of pixel vectors are closer to one another in the image variable space than any other pair of pixel vectors associated with any other pair of entries,
recording the identified pair of entries in a second data structure,
merging the pair of pixel vectors associated with the identified pair of entries to define a merged pixel vector that represents a spatial portion of the image jointly represented by the pair of pixel vectors associated with the identified pair of entries, and
replacing the identified pair of entries in the first data structure with an entry corresponding to the merged pixel vector.
9. The method of claim 8 , wherein said using a proximity metric to associate the entry with another entry and thereby identify a pair of entries includes performing a correlation calculation to determine for the pair of entries a correlation value indicative of a correlation between the associated pair of pixel vectors.
10. The method of claim 9 , wherein said performing a correlation calculation includes calculating for each of said associated pair of pixel vectors a mean value and a standard deviation value associated with the data values of said pixel vector.
11. The method of claim 8 , wherein the image is an image of an electron backscattered diffraction (EBSD) pattern.
12. A computer-readable storage medium which provides instructions that, when executes by a machine, cause the machine to perform operations to process an image represented by an array of pixel vectors that each represents a respective spatial portion of the image and includes a plurality of data values respectively associated with a plurality of variables in an image variable space, said operations comprising:
populating a first data structure with a plurality of entries that correspond to respective to respective ones of said pixel vectors; and
iteratively performing operations of:
for each entry in the first data structure, using a proximity metric to associate the entry with another entry and thereby identify a pair of entries, wherein said another entry is selected from a subset of entries that has an respectively associated pixel vectors represent spatial portions of the image that respectively border a spatial
portion of the image represented by the pixel vector associated with the entry, and wherein the pixel vector associated with said another entry is, among the pixel vectors associated with the subset of entries, closest in the image variable space to the pixel vector associated
with the entry,
using the proximity metric to identify one said pair of entries whose associated pair of pixel vectors are closer to one another in the image variable space than any other pair of pixel vectors associated with any other pair of entries,
recording the identified pair of entries in a second data structure,
merging the pair of pixel vectors associated with the identified pair of entries to define a merged pixel vector that represents a spatial portion of the image jointly represented by the pair of pixel vectors associated with the identified pair of entries, and
replacing the identified pair of entries in the first data structure with an entry corresponding to the merged pixel vector.
13. The storage medium of claim 12 , wherein said using a proximity metric to associate the entry with another entry and thereby identify a pair of entries includes performing a correlation calculation to determine for the pair of entries a correlation value indicative of a correlation between the associated pair of pixel vectors.
14. The storage medium of claim 13 , wherein said performing a correlation calculation includes calculating for each of said associated pair of pixel vectors a mean value and a standard deviation value associated with the data values of said pixel vector.
15. An apparatus for processing an image represented by an array of pixel vectors that each represents a respective spatial portion of the image and includes a plurality of data values respectively associated with a plurality of variables in an image variable space, comprising:
populating a first data structure with a plurality of entries that correspond to respective to respective ones of said pixel vectors; and
iteratively performing operations of:
for each entry in the first data structure, using a proximity metric to associate the entry with another entry and thereby identify a pair of entries, wherein said another entry is selected from a subset of entries that has an respectively associated pixel vectors represent spatial portions of the image that respectively border a spatial portion of the image represented by the pixel vector associated with the entry, and wherein the pixel vector associated with said another entry is, among the pixel vectors associated with the subset of entries, closest in the image variable space to the pixel vector associated with the entry,
using the proximity metric to identify one said pair of entries whose associated pair of pixel vectors are closer to one another in the image variable space than any other pair of pixel vectors associated with any other pair of entries,
recording the identified pair of entries in a second data structure,
merging the pair of pixel vectors associated with the identified pair of entries to define a merged pixel vector that represents a spatial portion of the image jointly represented by the pair of pixel vectors associated with the identified pair of entries, and
replacing the identified pair of entries in the first data structure with an entry corresponding to the merged pixel vector.
16. The apparatus of claim 15 , wherein said using a proximity metric to associate the entry with another entry and thereby identify a pair of entries includes performing a correlation calculation to determine for the pair of entries a correlation value indicative of a correlation between the associated pair of pixel vectors.
17. The apparatus of claim 16 , wherein said performing a correlation calculation includes calculating for each of said associated pair of pixel vectors a mean value and a standard deviation value associated with the data values of said pixel vector.