Method and system for fuzzy clustering of images
First Claim
1. A method for clustering a set of N images into P final clusters, where N and P are integers, comprising:
- calculating at least one similarity measure Si,j between members of each pair of images, where the similarity measure Si,j represents the similarity measure between an ith image and an jth image with i and j being image indices;
calculating a total connectivity value for each of the images remaining to be clustered, where the total connectivity value for each image being defined as a sum of a function f of the similarity measures associated with that image;
identifying, from among the images remaining to be clustered, a maximum total connectivity value Tmax corresponding to an image Imax, where the image Imax belonging to a current cluster which initially includes all images remaining to be clustered;
removing, from the current cluster, at least one image based on at least one of its similarity measure with image Imax and its total connectivity value within the current cluster;
adding, to the current cluster, images having similarity measures that are greater than a first threshold;
calculating, for each image within the current cluster, the total connectivity value based on those images within the current cluster;
removing, from the current cluster, those images having the total connectivity value less than a second threshold; and
repeating the calculating of the total connectivity value based on those images within the current cluster and the removing from the current cluster those images having the total connectivity value less than the second threshold until no further images are removed to thereby establish the current cluster as one of the final clusters.
0 Assignments
0 Petitions
Accused Products
Abstract
An approach to clustering a set of images based on similarity measures employs a fuzzy clustering paradigm in which each image is represented by a node in a graph. The graph is ultimately partitioned into subgraphs, each of which represent true clusters among which the various images are distributed. The partitioning is performed in a series of stages by identifying one true cluster at each stage, and removing the nodes belonging to each identified true cluster from further consideration so that the remaining, unclustered nodes may then be grouped. At the beginning of each such stage, the nodes that remain to be clustered are treated as all belonging to a single candidate cluster. Nodes are removed from this single candidate cluster in accordance with similarity and connectivity criteria, to arrive at a true cluster. The member nodes of this true cluster are then removed from further consideration, prior to the next stage in the process.
-
Citations
20 Claims
-
1. A method for clustering a set of N images into P final clusters, where N and P are integers, comprising:
-
calculating at least one similarity measure Si,j between members of each pair of images, where the similarity measure Si,j represents the similarity measure between an ith image and an jth image with i and j being image indices; calculating a total connectivity value for each of the images remaining to be clustered, where the total connectivity value for each image being defined as a sum of a function f of the similarity measures associated with that image; identifying, from among the images remaining to be clustered, a maximum total connectivity value Tmax corresponding to an image Imax, where the image Imax belonging to a current cluster which initially includes all images remaining to be clustered; removing, from the current cluster, at least one image based on at least one of its similarity measure with image Imax and its total connectivity value within the current cluster; adding, to the current cluster, images having similarity measures that are greater than a first threshold; calculating, for each image within the current cluster, the total connectivity value based on those images within the current cluster; removing, from the current cluster, those images having the total connectivity value less than a second threshold; and repeating the calculating of the total connectivity value based on those images within the current cluster and the removing from the current cluster those images having the total connectivity value less than the second threshold until no further images are removed to thereby establish the current cluster as one of the final clusters. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. An apparatus for clustering a set of N images into P final clusters, where N and P are integers, comprising:
-
means for calculating at least one similarity measure Si,j between members of each pair of images, where the similarity measure Si,j represents the similarity measure between an ith image and an jth image with i and j being image indices; means for calculating a total connectivity value for each of the images remaining to be clustered, where the total connectivity value for each image being defined as a sum of a function f of the similarity measures associated with that image; means for identifying, from among the images remaining to be clustered, a maximum total connectivity value tmax corresponding to an image Imax, where the image Imax belonging to a current cluster which initially includes all images remaining to be clustered; means for removing, from the current cluster, at least one image based on at least one of its similarity measure with image Imax and its total connectivity value within the current cluster; means for adding, to the current cluster, images having similarity measures that are greater than a first threshold; means for calculating, for each image within the current cluster, the total connectivity value based on those images within the current cluster; and means for removing, from the current cluster, those images having the total connectivity value less than a second threshold, wherein the total connectivity value calculating and the image removing are repeated until no further images are removed to thereby establish the current cluster as one of the final clusters. - View Dependent Claims (19)
-
-
20. A non-transitory computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to perform steps of a method for clustering a set of N images into P final clusters, where N and P are integers comprising:
-
calculating at least one similarity measure Si,j between members of each pair of images, where the similarity measure Si,j represents the similarity measure between an ith image and an jth image with i and j being image indices; calculating a total connectivity value for each of the images remaining to be clustered, where the total connectivity value for each image being defined as a sum of a function f of the similarity measures associated with that image; identifying, from among the images remaining to be clustered, a maximum total connectivity value Tmax corresponding to an image Imax, where the image Imax belonging to a current cluster which initially includes all images remaining to be clustered; removing, from the current cluster, at least one image based on at least one of its similarity measure with image Imax and its total connectivity value within current cluster; adding, to the current cluster, images having similarity measures that are greater than a first threshold; calculating, for each image within the current cluster, the total connectivity value based on those images within current cluster; removing, from the current cluster, those images having the total connectivity value less than a second threshold; and repeating the calculating of the total connectivity value based on those images within the current cluster and the removing from the current cluster those images having the total connectivity value less than the second threshold until no further images are removed to thereby establish the current cluster as one of the final clusters.
-
Specification