Patent ID: 7260263

Claim:
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 ij between members of each possible pair of images, wherein S ij represents the similarity measure between the ith and jth images 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 current cluster C; means for adding, to current cluster C, images having a similarity measure that is grater than a threshold T 3 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 T 4 , 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.