METHOD OF CLUSTERING DIGITAL IMAGES, CORRESPONDING SYSTEM, APPARATUS AND COMPUTER PROGRAM PRODUCT

• US 20160307068A1
• Filed: 12/03/2015
• Published: 10/20/2016
• Est. Priority Date: 04/15/2015
• Status: Active Grant

• Current Assignee: STMicroelectronics SRL (STMicroelectronics NV)
• Original Assignee: STMicroelectronics SRL (STMicroelectronics NV)
• Inventors: Plebani, Emanuele, Paliotto, Luca, Pau, Danilo Pietro
• Granted Patent: US 10,489,681 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 18/23213 with fixed number of clusters, e.g. K-means clustering

Abstract

Digital image processing circuitry clusters a set of images into a set of first clusters of images and a set of unclustered images. The set of first clusters are merged, generating a set of second clusters of images. Images in the set of unclustered images are assigned to one of a cluster of the set of second clusters of images and an outlier image cluster. The clustered images may be partitioned into subclusters based on detection of objects in the images.

Claims

1. A method, comprising:

automatically clustering a set of images into a set of first clusters of images and a set of unclustered images;

automatically merging clusters of said set of first clusters of images to produce a set of second clusters of images; and

automatically assigning each image of the set of unclustered images to one of;

a cluster of the set of second clusters of images; and

a respective outlier image cluster.

2. The method of claim 1 wherein the automatically clustering the set of images into the set of first clusters of images comprises:

determining for each image of the set of images similarity scores between said image and other images in the set of images; and

clustering the images in said set of images to produce the set of first clusters of images based on the similarity scores.

3. The method of claim 2, comprising:

generating a matrix S of similarity scores s_ij, where s_ij represents a similarity score between an image i and an image j of the set of images.

4. The method of claim 2 wherein the automatically clustering the set of images into said set of first clusters of images comprises:

automatically comparing a similarity score between an unclustered image of the set of images and an image in one of the clusters of the set of first clusters to a similarity threshold value and adding the unclustered image to the one of the clusters of the set of first clusters based on the comparing.

5. The method of claim 1 wherein the automatically merging clusters of said set of first clusters of images to produce the set of second clusters of images is based on distances between said clusters in said set of first clusters.

6. The method of claim 5 wherein a distance between a pair of clusters of the set of first clusters is an average of distances between images of a first cluster of the pair of clusters and images of a second cluster of the pair of clusters.

7. The method of claim 5 wherein the automatically merging clusters of said set of first clusters to produce the set of second clusters includes:

automatically comparing a distance score between an unmerged cluster of the set of first clusters and a cluster assigned to one of the clusters of the set of second clusters to a distance threshold value and adding the unmerged cluster to the one of the clusters of the set of second clusters based on the comparing.

8. The method of claim 1 wherein the automatically assigning each image of the set of unclustered images comprises:

automatically determining distance scores between an image of the set of unclustered images and respective clusters of the set of second clusters and assigning the image of the set of unclustered images based on the determined distance scores.

9. The method of claim 8 wherein a distance score between the image of the set of unclustered images and a cluster of the set of second clusters is an average value of distance scores between said image of the set of unclustered images and a set of images in said cluster of said set of second clusters.

10. The method of claim 8 wherein the automatically assigning each image of the set of unclustered images comprises:

identifying a cluster of the set of second clusters which is closest to the image of the set of unclustered images based on the distance scores between the image of the set of unclustered images and the respective clusters of the set of second clusters;

comparing a distance score between the image of the set of unclustered images and the identified cluster of the set of second clusters to an outlier threshold value; and

assigning the image of the set of unclustered images to one of the identified cluster of the set of second clusters and the respective outlier image cluster based on the comparing of the distance score between the image of the set of unclustered images and the identified cluster of the set of second clusters to the outlier threshold value.

11. The method of claim 1, comprising:

detecting objects in images of the set of images;

setting respective object flags of images in the set of images based on the detecting; and

partitioning the set of second clusters and the outlier image clusters into sub-clusters based on the respective object flags of the images.

12. A system, comprising:

one or more memories; and

digital image processing circuitry, which, in operation;

clusters a set of images into a set of first clusters of images and a set of unclustered images;

merges clusters of said set of first clusters of images, producing a set of second clusters of images; and

assigns each image of the set of unclustered images to one of;

a cluster of the set of second clusters of images; and

an outlier image cluster.

13. The system of claim 12 wherein the digital image processing circuitry, in operation:

determines for each image of the set of images similarity scores between said image and other images in the set of images; and

clusters the images in said set of images into the set of first clusters of images and the set of unclustered images based on the similarity scores.

14. The system of claim 13 wherein the digital image processing circuitry, in operation:

generates a matrix S of similarity scores s_ij, where s_ij represents a similarity score between an image i and an image j of the set of images.

15. The system of claim 13 wherein the digital image processing circuitry, in operation:

compares a similarity score between an unclustered image of the set of images and an image in one of the clusters of the set of first clusters to a similarity threshold value and selectively adds the unclustered image to the one of the clusters of the set of first clusters based on the comparing.

16. The system of claim 12 wherein the merging clusters of said set of first clusters of images is based on distances between said clusters in said set of first clusters.

17. The system of claim 16 wherein a distance between a pair of clusters of the set of first clusters is an average of distances between images of a first cluster of the pair of clusters and images of a second cluster of the pair of clusters.

18. The system of claim 16 wherein the merging clusters of said set of first clusters comprises:

comparing a distance score between an unmerged cluster of the set of first clusters and a cluster assigned to one of the clusters of the set of second clusters to a distance threshold value and selectively adding the unmerged cluster to the one of the clusters of the set of second clusters based on the comparing.

19. The system of claim 12 wherein the assigning each image of the set of unclustered images comprises:

determining distance scores between an image of the set of unclustered images and respective clusters of the set of second clusters and assigning the image of the set of unclustered images based on the determined distance scores.

20. The system of claim 19 wherein the assigning each image of the set of unclustered images comprises:

identifying a cluster of the set of second clusters which is closest to the image of the set of unclustered images based on the distance scores between the image of the set of unclustered images and the respective clusters of the set of second clusters;

comparing a distance score between the image of the set of unclustered images and the identified cluster of the set of second clusters to an outlier threshold value; and

assigning the image of the set of unclustered images to one of the identified cluster of the set of second clusters and the respective outlier image cluster based on the comparing of the distance score between the image of the set of unclustered images and the identified cluster of the set of second clusters to the outlier threshold value.

21. The system of claim 12 wherein the digital image processing circuitry, in operation:

detects objects in images of the set of images;

sets respective object flags of images in the set of images based on the detecting; and

partitions at least one of the set of second clusters and the outlier image clusters into sub-clusters based on the respective object flags of the images.

22. The system of claim 12 wherein the digital image processing circuitry comprises:

at least one descriptor generator, which, in operation, generates descriptors of images of the set of images.

23. The system of claim 12, comprising at least one of:

an image capture device, which, in operation, generates digital images of the set of images; and

a display, which, in operation, displays one or more images based on the clustering.

24. A device, comprising:

at least one descriptor generator, which, in operation, generates descriptors of images of a set of images; and

digital image processing circuitry, which, in operation;

clusters a set of images into a set of first clusters of images and a set of unclustered images based on the generated descriptors;

merges clusters of said set of first clusters of images, producing a set of second clusters of images; and

assigns each image of the set of unclustered images to one of;

a cluster of the set of second clusters of images; and

an outlier image cluster.

25. The device of claim 24 wherein the digital image processing circuitry, in operation:

determines for each image of the set of images similarity scores between said image and other images in the set of images based on the generated descriptors; and

clusters the images in said set of images into the set of first clusters of images and the set of unclustered images based on the similarity scores.

26. The device of claim 24 wherein the merging clusters of said set of first clusters of images is based on distances between said clusters in said set of first clusters.

27. A non-transitory computer-readable medium containing contents which configure digital image processing circuitry to perform a method, the method comprising:

clustering a set of images into a set of first clusters of images and a set of unclustered images;

merging clusters of said set of first clusters of images, producing a set of second clusters of images; and

assigning each image of the set of unclustered images to one of;

a cluster of the set of second clusters of images; and

an outlier image cluster.

28. The non-transitory computer-readable medium of claim 27 wherein the method comprises:

determining for each image of the set of images similarity scores between said image and other images in the set of images; and

clustering the images in said set of images into the set of first clusters of images and the set of unclustered images based on the similarity scores.

29. The non-transitory computer-readable medium of claim 27 wherein the set of unclustered images is an empty set.