Method and system for fuzzy clustering of images

• US 7,460,717 B2
• Filed: 08/14/2007
• Issued: 12/02/2008
• Est. Priority Date: 03/28/2001
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Jafarkhani, Hamid, Tarokh, Vahid
• Primary Examiner(s): Carter; Aaron W
• Application Number:
  US11/838,668
• Publication Number:
  US 20070274597A1
• Time in Patent Office: 476 Days
• Field of Search: 382155-161, 382224-228, 382232-253, 706 1- 9, 706/52, 706/900, 704/245
• US Class Current: 382/224
• CPC Class Codes: G06F 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts

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.

Claims

1. A method for clustering a set of N images into P final clusters, where N and P are integers, the method comprising:

(a) calculating at least one similarity measure S_i,j between members of each pair of images, wherein S_i,j represents the similarity measure between an ith image and an jth image with i and j being image indices and S_i,j=S_j,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 T_max corresponding to an image I_max, image I_max 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 I_max and its total connectivity value within current cluster C;

(e) adding, to the current cluster C, images having a similarity measure that is greater than a threshold T3 with any image currently in cluster C;

(f) calculating, for each image within the current cluster C, a total connectivity value based on those images within C;

(g) removing, from the current cluster C, those images having a total connectivity value less than a threshold T4;

(h) repeating said steps (f) and (g) until no further images are removed to thereby establish the current cluster C as one of the final clusters;

(i) removing all images in the current cluster C from further consideration; and

(j) repeating steps (b)-(i) until all N images are assigned to a final cluster.

2. The method according to claim 1, further comprising:

applying a non-linear function to each similarity measure, prior to calculating the total connectivity value.

3. The method according to claim 2, wherein the non-linear function is a transcendental function.

4. The method according to claim 3, wherein the transcendental function is a hyperbolic tangent.

5. The method according to claim 4, wherein each similarity measure S_i,j is transformed according to a formula tanh(5 ×

S_i,j), prior to calculating a total connectivity value.

6. The method according to claim 1, wherein the function f is an identity function.

7. The method according to claim 1, wherein the function f is a nonlinear function.

8. The method according to claim 1, wherein in step (e), at least one image is removed from the current cluster based on its similarity measure with image I_max, and then at least one other image is removed from the current cluster based on its total connectivity value within the current cluster.

9. The method according to claim 1, wherein in step (e), at least one image is removed from the current cluster based on its total connectivity value within the current cluster, and then at least one other image is removed from the current cluster based on its similarity measure with image I_max.

10. The method according to claim 1, wherein in step (a), images having a similarity measure with I_max that is less than a threshold T1 are removed from the current cluster.

11. The method according to claim 1, wherein in step (e), a number N1 images having the N1 lowest similarity measures with I_max are removed from the current cluster.

12. The method according to claim 1, wherein in step (e), images having a total connectivity value which differs from t_max by more than a threshold T2 are removed from the current cluster.

13. The method according to claim 12, wherein images having a similarity measure with I_max that is less than a threshold T1 are removed from the current cluster.

14. The method according to claim 13, wherein at least one image is removed from the current cluster based on its similarity measure with image I_max, and then at least one other image is removed from the current cluster based on its total connectivity value within the current cluster.

15. The method according to claim 12, wherein a number N1 images having the N1 lowest similarity measures with I_max are removed from the current cluster.

16. The method according to claim 15, wherein at least one image is removed from the current cluster based on its similarity measure with image I_max, and then at least one other image is removed from the current cluster based on its total connectivity value within the current cluster.

17. 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 S_i,j between members of each pair of images, wherein S_i,j represents the similarity measure between an ith image and an jth image with i and j being image indices and S_i,j=S_j,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 t_max corresponding to an image I_max, image I_max 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 I_max and its total connectivity value within the current cluster C;

means for adding, to the current cluster C, images having a similarity measure that is greater than a threshold T3 with any image currently in cluster C;

means for calculating, for each image within the current cluster C, a total connectivity value based on those images within cluster C;

means for removing, from the current cluster C, those images having a total connectivity value less than a 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 the current cluster C as one of the final clusters; and

means for removing all images in the 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.

18. The apparatus of claim 17, further comprising:

means for applying a non-linear function to each similarity measure, prior to calculating the total connectivity value.

19. The apparatus of claim 18, wherein the non-linear function is a transcendental function.

20. 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 S_i,j between members of each pair of images, wherein S_i,j represents the similarity measure between an ith image and an jth image with i and j being image indices and S_i,j=S_j,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 T_max corresponding to an image I_max, image I_max 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 I_max and its total connectivity value within current cluster C;

(e) adding, to the current cluster C, images having a similarity measure that is greater than a threshold T3 with any image currently in cluster C;

(f) calculating, for each image within the current cluster C, a total connectivity value based on those images within C;

(g) removing, from the current cluster C, those images having a total connectivity value less than a threshold T4;

(h) repeating said steps (f) and (g) until no further images are removed to thereby establish the current cluster C as one of the final clusters;

(i) removing all images in the current cluster C from further consideration; and

(j) repeating steps (b)-(i) until all N images are assigned to a final cluster.