Method and system for fuzzy clustering of images
First Claim
1. 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 Sij between members of each possible pair of images, wherein Sij represents the similarity measure between the ith and jth images with i and j being image indices and Si,j=Sj,i;
means for calculating a total connectivity value for each of the images remaining to be clustered, a 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 said images remaining to be clustered, a maximum total connectivity value tmax corresponding to an image Imax, image Imax belonging to a current cluster C which initially includes all images remaining to be clustered;
means for removing, from the current cluster C, at least one image based on at least one of its similarity measure with image Imax and its total connectivity value within current cluster C;
means for adding, to current cluster C, images having a similarity measure that is grater than a threshold T3 with any image currently in C;
means for calculating, for each image within current cluster C, a total connectivity value based on those images within C;
means for removing, from current cluster C, those images having a total connectivity value less than some threshold T4, wherein said total connectivity value calculating step and said image removing step are repeated until no further images are removed to thereby establish current cluster C as one of the final clusters; and
means for removing all images in current cluster C from further consideration, wherein one or more of said calculating steps, said identifying step, said removing steps, and said adding step are repeating until all N images are assigned to a final cluster.
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.
23 Citations
34 Claims
-
1. 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 Sij between members of each possible pair of images, wherein Sij represents the similarity measure between the ith and jth images with i and j being image indices and Si,j=Sj,i; means for calculating a total connectivity value for each of the images remaining to be clustered, a 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 said images remaining to be clustered, a maximum total connectivity value tmax corresponding to an image Imax, image Imax belonging to a current cluster C which initially includes all images remaining to be clustered; means for removing, from the current cluster C, at least one image based on at least one of its similarity measure with image Imax and its total connectivity value within current cluster C; means for adding, to current cluster C, images having a similarity measure that is grater than a threshold T3 with any image currently in C; means for calculating, for each image within current cluster C, a total connectivity value based on those images within C; means for removing, from current cluster C, those images having a total connectivity value less than some threshold T4, wherein said total connectivity value calculating step and said image removing step are repeated until no further images are removed to thereby establish current cluster C as one of the final clusters; and means for removing all images in current cluster C from further consideration, wherein one or more of said calculating steps, said identifying step, said removing steps, and said adding step are repeating until all N images are assigned to a final cluster. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
-
17. An apparatus for clustering a set of N items 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 possible pair of items, wherein Si,j represents the similarity measure between the ith and jth items with i and j being items indices and Si,j=Sj,i; means for calculating a total connectivity value for each of the items remaining to be clustered, a total connectivity value for each item being defined as a sum of a function f of the similarity measures associated with that item; means for identifying, from among said items remaining to be clustered, a maximum total connectivity value tmax corresponding to an item Imax, item Imax belonging to a current cluster C which initially includes all items remaining to be clustered; means for removing, from the current cluster C, at least one item based on at least one of its similarity measure with item Imax and its total connectivity value within current cluster C; means for adding, to current cluster C, items having a similarity measure that is greater than a threshold T3 with any item currently in C; means for calculating, for each item within current cluster C, a total connectivity value based on those items within C; means for removing, from current cluster C, those items having a total connectivity value less than some threshold T4, wherein said total connectivity value calculating step and said item removing step are repeated until no further items are removed to thereby establish current cluster C as one of the final clusters; and means for removing all items in current cluster C from further consideration, wherein one or more of said calculating steps, said identifying step, said removing steps, and said adding step are repeating until all N items are assigned to a final cluster.
-
-
18. A 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 the steps of a method for clustering a set of N images into P final clusters, where N and P are integers comprising of:
-
(a) calculating at least one similarity measure Si,j between members of each possible pair of images, wherein Si,j represents the similarity measure between the ith and jth images with i and j being image indices and Si,j=Sj,i; (b) calculating a total connectivity value for each of the images remaining to be clustered, a total connectivity value for each image being defined as a sum of a function f of the similarity measures associated with that image; (c) identifying, from among said images remaining to be clustered, a maximum total connectivity value tmax corresponding to an image Imax, image Imax belonging to a current cluster C which initially includes all images remaining to be clustered; (d) removing, from the current cluster C, at least one image based on at least one of its similarity measure with image Imax and its total connectivity value within current cluster C; (e) adding, to current cluster C, images having a similarity measure that is greater than a threshold T3 with any image currently in C; (f) calculating, for each image within current cluster C, a total connectivity value based on those images within C; (g) removing from current cluster C, those images having a total connectivity value less than some threshold T4; (h) repeating steps (f) and (g) until no further images are removed to thereby establish current cluster C as one of the final clusters; (i) removing all images in current cluster C from further consideration; and (j) repeating steps (b)-(i) until all N images are assigned to a final cluster. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33)
-
-
34. A 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 the steps of a method for clustering a set of N items into P final clusters, where N and P are integers comprising of:
-
(a) calculating at least one similarity measure Si,j between members of each possible pair of items, wherein Si,j represents the similarity measure between the ith and jth items with i and j being item indices and Si,j=Sj,i; (b) calculating a total connectivity value for each of the items remaining to be clustered, a total connectivity value for each item being defined as a sum of a function f of the similarity measures associated with that item; (c) identifying, from among said items remaining to be clustered, a maximum total connectivity value tmax corresponding to an item Imax, item Imax belonging to a current cluster C which initially includes all items remaining to be clustered; (d) removing, from the current cluster C, at least one item based on at least one of its similarity measure with item Imax and its total connectivity value within current cluster C; (e) adding, to current cluster C, items having a similarity measure that is greater than a threshold T3 with any item currently in C; (f) calculating, for each item within current cluster C, a total connectivity value based on those items within C; (g) removing, from current cluster C, those items having a total connectivity value less than some threshold T4; (h) repeating steps (f) and (g) until no further items are removed to thereby establish current cluster C as one of the final clusters; (i) removing all items in current cluster C from further consideration; and (j) repeating steps (b)-(i) until all N items are assigned to a final cluster.
-
Specification