Method and apparatus for performing constrained spectral clustering of digital image data

• US 20070239764A1
• Filed: 03/31/2006
• Published: 10/11/2007
• Est. Priority Date: 03/31/2006
• Status: Active Grant

• Current Assignee: Fujifilm Corporation (Fujifilm Holdings Corporation)
• Original Assignee: Fuji Photo Film Co Limited (Fujifilm Holdings Corporation)
• Inventors: Song, Yang, Leung, Thomas
• Granted Patent: US 7,920,745 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/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts
• CPC Class Codes: G06V 10/7635 based on graphs, e.g. graph cuts or spectral clustering
• CPC Class Codes: G06V 40/10 Human or animal bodies, e.g. vehicle occupants or pedestrians; Body parts, e.g. hands
• CPC Class Codes: G06V 40/172 Classification, e.g. identification

Abstract

A method and an apparatus process digital images. The method according to one embodiment accesses element data representing a plurality of elements belonging to a plurality of digital images; performs a similarity analysis between the elements from the plurality of elements to obtain inter-relational data results relating to the elements; and performs clustering of the plurality of elements, the step of performing clustering including incorporating in the inter-relational data results at least one hard constraint relating to elements from the plurality of elements, to obtain constrained inter-relational data results, performing a spectral analysis to obtain eigenvector results from the constrained inter-relational data results, and performing discretization of the eigenvector results using constrained clustering with a criterion to enforce the at least one hard constraint to obtain clusters.

Claims

1. A digital image processing method, said method comprising:

accessing element data representing a plurality of elements belonging to a plurality of digital images;

performing a similarity analysis between said elements from said plurality of elements to obtain inter-relational data results relating to said elements; and

performing clustering of said plurality of elements, said step of performing clustering including

incorporating in said inter-relational data results at least one hard constraint relating to elements from said plurality of elements, to obtain constrained inter-relational data results,

performing a spectral analysis to obtain eigenvector results from said constrained inter-relational data results, and

performing discretization of said eigenvector results using constrained clustering with a criterion to enforce said at least one hard constraint to obtain clusters.

2. The digital image processing method as recited in claim 1, wherein said sub-step of performing discretization uses constrained K-means clustering.

3. The digital image processing method as recited in claim 1, wherein said elements are people found in said plurality of digital images.

4. The digital image processing method as recited in claim 3, wherein said at least one hard constraint includes a hard negative constraint that two people found in the same image from said plurality of digital images have different identities.

5. The digital image processing method as recited in claim 3, wherein said at least one hard constraint includes a hard positive constraint based on predetermined knowledge that two people found in different images from said plurality of digital images are the same person.

6. The digital image processing method as recited in claim 3, wherein said step of performing a similarity analysis between said elements includes

performing a face similarity analysis between faces of said people to obtain face similarity measures between faces of said people,

performing a clothes similarity analysis between clothes of said people to obtain clothes similarity measures between clothes of said people, and

providing a plurality of formulas for estimating similarity measures for pairs of people from said plurality of digital images to represent the same person, based on availability of said face similarity measures and said clothes similarity measures.

7. The digital image processing method as recited in claim 6, wherein said step of performing a similarity analysis between said elements

selects at least one formula from said plurality of formulas based on a time when images from said plurality of digital images were taken, to obtain a similarity measure between two people for said inter-relational data results,

selects at least one formula from said plurality of formulas based on a place where images from said plurality of digital images were taken, to obtain a similarity measure between two people for said inter-relational data results,

selects at least one formula from said plurality of formulas based on whether more than one person is wearing the same clothes in a single image, to obtain a similarity measure between two people for said inter-relational data results,

selects at least one formula from said plurality of formulas to obtain a similarity measure between two people for said inter-relational data results when only a face similarity measure from said face similarity measures but no clothes similarity measure from said clothes similarity measures is available,

selects at least one formula from said plurality of formulas to obtain a similarity measure between two people for said inter-relational data results when only a clothes similarity measure from said clothes similarity measures but no face similarity measure from said face similarity measures is available, and

selects at least one formula from said plurality of formulas to obtain a similarity measure between two people for said inter-relational data results when a face similarity measure from said face similarity measures and a clothes similarity measure from said clothes similarity measures are available.

8. The digital image processing method as recited in claim 6, further comprising:

segmenting clothes to determine clothes areas in said plurality of digital images via maximizing a difference between neighboring clothes, and

removing clutters from said clothes areas, before said step of performing a similarity analysis.

9. The digital image processing method as recited in claim 8, wherein clothes in said plurality of digital images include at least one of clothing, shoes, watch, and eyeglasses.

10. The digital image processing method as recited in claim 8, further comprising:

performing clothes feature extraction after said step of removing clutters and before said step of performing a similarity analysis, said step of performing clothes feature extraction including

extracting representative image patches from said clothes areas, and

generating feature vectors from frequencies of appearance of said representative image patches in said clothes areas, to obtain numerical representations for said clothes areas for use in said step of performing a similarity analysis between said elements.

11. The digital image processing method as recited in claim 1, wherein number of said clusters is predetermined before said step of performing clustering of said plurality of elements.

12. The digital image processing method as recited in claim 1, wherein

said eigenvector results are a set of numerical elements,

a one-to-one correspondence exists between elements from said plurality of elements and said numerical elements, and

each element from plurality of elements is assigned to a cluster from said clusters to which a corresponding numerical element from said numerical elements was clustered in said sub-step of performing discretization.

13. The digital image processing method as recited in claim 1, wherein

said step of performing a similarity analysis includes

obtaining similarity scores between said elements, and

obtaining an affinity matrix A using said similarity scores;

said sub-step of incorporating includes

incorporating in said affinity matrix A said at least one hard constraint, and

using said affinity matrix A to obtain said constrained inter-relational data results in the form of an inter-relational data matrix L;

said sub-step of performing a spectral analysis includes

selecting a predetermined number of largest eigenvectors of said inter-relational data matrix L,

stacking selected eigenvectors into columns to obtain a matrix X, and

normalizing the rows of said matrix X to unit length to obtain said eigenvector results in the form of a matrix Y; and

said sub-step of performing discretization includes

clustering rows of said matrix Y using constrained K-means clustering using a criterion to enforce said at least one hard constraint to obtain said clusters, and

assigning elements from said plurality of elements to clusters to which rows of said matrix Y associated with said elements are assigned.

14. The digital image processing method as recited in claim 13, wherein

said elements are people found in said plurality of digital images,

said at least one hard constraint includes a negative constraint that two people found in the same image from said plurality of digital images have different identities, and

said step of performing a similarity analysis between said elements includes

performing a similarity analysis between faces of said people to obtain face similarity scores between faces of said people,

performing a similarity analysis between clothes of said people to obtain clothes similarity scores between clothes of said people,

combining said face similarity scores and said clothes similarity scores for pairs of people, to obtain said similarity scores, and

obtaining said affinity matrix A using said similarity scores for said pairs of people.

15. A digital image processing method, said method comprising:

accessing element data representing a plurality of elements belonging to a plurality of digital images;

performing a similarity analysis between said elements from said plurality of elements to obtain inter-relational data results relating to said elements; and

performing clustering of said plurality of elements, said step of performing clustering including

incorporating in said inter-relational data results at least one hard negative constraint relating to dissimilarities between said elements, to obtain constrained inter-relational data results,

performing a spectral analysis to obtain eigenvector results from said constrained inter-relational data results, and

performing discretization of said eigenvector results by clustering said eigenvector results to obtain clusters.

16. The digital image processing method as recited in claim 15, wherein said sub-step of performing discretization uses K-means clustering to cluster said eigenvector results to obtain said clusters.

17. The digital image processing method as recited in claim 16, wherein

said elements are people found in said plurality of digital images, and

said at least one hard negative constraint includes a negative constraint that two people found in the same image from said plurality of digital images have different identities.

18. The digital image processing method as recited in claim 17, wherein said step of performing a similarity analysis between said elements includes

performing a face similarity analysis between faces of said people to obtain face similarity measures between faces of said people,

performing a clothes similarity analysis between clothes of said people to obtain clothes similarity measures between clothes of said people, and

providing a plurality of formulas for estimating similarity measures for pairs of people from said plurality of digital images to represent the same person, based on availability of said face similarity measures and said clothes similarity measures.

19. The digital image processing method as recited in claim 17, further comprising:

segmenting clothes to determine clothes areas in said plurality of digital images via maximizing a difference between neighboring clothes,

removing clutters from said clothes areas, before said step of performing a similarity analysis, and

performing clothes feature extraction before said step of performing a similarity analysis, said step of performing clothes feature extraction including

extracting representative image patches from said clothes areas, and

generating feature vectors from frequencies of appearance of said representative image patches in said clothes areas, to obtain numerical representations for said clothes areas for use in said step of performing a similarity analysis between said elements.

20. The digital image processing method as recited in claim 15, wherein

said step of performing a similarity analysis includes

obtaining similarity scores between said elements, and

obtaining an affinity matrix A using said similarity scores;

said sub-step of incorporating includes

incorporating in said affinity matrix A said at least one hard negative constraint,

generating a repulsion matrix R using said at least one hard negative constraint, and

using said affinity matrix A and said repulsion matrix R to obtain said constrained inter-relational data results in the form of an inter-relational data matrix L;

said sub-step of performing a spectral analysis includes

selecting a predetermined number of largest eigenvectors of said inter-relational data matrix L,

stacking selected eigenvectors into columns to obtain a matrix X, and

normalizing the rows of said matrix X to unit length to obtain said

eigenvector results in the form of a matrix Y; and

said sub-step of performing discretization includes

clustering rows of said matrix Y using K-means clustering to obtain said clusters, and

assigning elements from said plurality of elements to clusters to which rows of said matrix Y associated with said elements are assigned.

21. A digital image processing apparatus, said apparatus comprising:

an image data unit for providing element data representing a plurality of elements belonging to a plurality of digital images;

a similarity analysis unit for performing a similarity analysis between said elements from said plurality of elements to obtain inter-relational data results relating to said elements; and

a clustering unit for performing clustering of said plurality of elements, said clustering unit performing clustering by

incorporating in said inter-relational data results at least one hard constraint relating to elements from said plurality of elements, to obtain constrained inter-relational data results,

performing a spectral analysis to obtain eigenvector results from said constrained inter-relational data results, and

performing discretization of said eigenvector results using constrained clustering with a criterion to enforce said at least one hard constraint to obtain clusters.

22. The apparatus according to claim 21, wherein said clustering unit performs discretization using constrained K-means clustering.

23. The apparatus according to claim 21, wherein said elements are people found in said plurality of digital images.

24. The apparatus according to claim 23, wherein said at least one hard constraint includes a hard negative constraint that two people found in the same image from said plurality of digital images have different identities.

25. The apparatus according to claim 23, wherein said at least one hard constraint includes a hard positive constraint based on predetermined knowledge that two people found in different images from said plurality of digital images are the same person.

26. The apparatus according to claim 23, wherein said similarity analysis unit comprises:

a face unit for performing a face similarity analysis between faces of said people to obtain face similarity measures between faces of said people,

a clothes unit for performing a clothes similarity analysis between clothes of said people to obtain clothes similarity measures between clothes of said people, and

a combination unit for providing a plurality of formulas for estimating similarity measures for pairs of people from said plurality of digital images to represent the same person, based on availability of said face similarity measures and said clothes similarity measures.

27. The apparatus according to claim 26, wherein said combination unit

selects at least one formula from said plurality of formulas based on a time when images from said plurality of digital images were taken, to obtain a similarity measure between two people for said inter-relational data results,

selects at least one formula from said plurality of formulas based on a place where images from said plurality of digital images were taken, to obtain a similarity measure between two people for said inter-relational data results,

selects at least one formula from said plurality of formulas based on whether more than one person is wearing the same clothes in a single image, to obtain a similarity measure between two people for said inter-relational data results,

selects at least one formula from said plurality of formulas to obtain a similarity measure between two people for said inter-relational data results when only a face similarity measure from said face similarity measures but no clothes similarity measure from said clothes similarity measures is available,

selects at least one formula from said plurality of formulas to obtain a similarity measure between two people for said inter-relational data results when only a clothes similarity measure from said clothes similarity measures but no face similarity measure from said face similarity measures is available, and

selects at least one formula from said plurality of formulas to obtain a similarity measure between two people for said inter-relational data results when a face similarity measure from said face similarity measures and a clothes similarity measure from said clothes similarity measures are available.

28. The apparatus according to claim 26, further comprising:

a clothes segmentation unit for determining clothes areas in said plurality of digital images via maximizing a difference between neighboring clothes, and removing clutters from said clothes areas, before said similarity analysis unit performs said similarity analysis.

29. The apparatus according to claim 28, wherein clothes in said plurality of digital images include at least one of clothing, shoes, watch, and eyeglasses.

30. The apparatus according to claim 28, further comprising:

a clothes representation unit for performing clothes feature extraction on said clothes areas by

extracting representative image patches from said clothes areas,

generating feature vectors from frequencies of appearance of said representative image patches in said clothes areas to obtain numerical representations for said clothes areas, and

sending said numerical representations for said clothes areas to said clothes unit.

31. The apparatus according to claim 21, wherein number of said clusters is predetermined before said clustering unit performs clustering of said plurality of elements.

32. The apparatus according to claim 21, wherein

said eigenvector results are a set of numerical elements,

a one-to-one correspondence exists between elements from said plurality of elements and said numerical elements, and

said clustering unit assigns each element from said plurality of elements to a cluster from said clusters to which a corresponding numerical element from said numerical elements was clustered.

33. The apparatus according to claim 21, wherein

said similarity analysis unit performs a similarity analysis between said elements by

obtaining similarity scores between said elements, and

obtaining an affinity matrix A using said similarity scores;

and

said clustering unit performs clustering of said plurality of elements by

incorporating in said affinity matrix A said at least one hard constraint,

using said affinity matrix A to obtain said constrained inter-relational data results in the form of an inter-relational data matrix L,

selecting a predetermined number of largest eigenvectors of said inter-relational data matrix L,

stacking selected eigenvectors into columns to obtain a matrix X,

normalizing the rows of said matrix X to unit length to obtain said eigenvector results in the form of a matrix Y,

clustering rows of said matrix Y using constrained K-means clustering using a criterion to enforce said at least one hard constraint to obtain said clusters, and

assigning elements from said plurality of elements to clusters to which rows of said matrix Y associated with said elements are assigned.

34. The apparatus according to claim 33, wherein

said elements are people found in said plurality of digital images,

said at least one hard constraint includes a hard negative constraint that two people found in the same image from said plurality of digital images have different identities, and

said similarity analysis unit performs said similarity analysis between said elements by

performing a similarity analysis between faces of said people to obtain face similarity scores between faces of said people,

performing a similarity analysis between clothes of said people to obtain clothes similarity scores between clothes of said people,

combining said face similarity scores and said clothes similarity scores for pairs of people, to obtain said similarity scores, and

obtaining said affinity matrix A using said similarity scores for said pairs of people.

35. A digital image processing apparatus, said apparatus comprising:

an image data unit for providing element data representing a plurality of elements belonging to a plurality of digital images;

a similarity analysis unit for performing a similarity analysis between said elements from said plurality of elements to obtain inter-relational data results relating to said elements; and

a clustering unit for performing clustering of said plurality of elements, said clustering unit performing clustering by

incorporating in said inter-relational data results at least one hard negative constraint relating to dissimilarities between said elements, to obtain constrained inter-relational data results,

performing a spectral analysis to obtain eigenvector results from said constrained inter-relational data results, and

performing discretization of said eigenvector results by clustering said eigenvector results to obtain clusters.

36. The apparatus according to claim 35, wherein said clustering unit uses K-means clustering to cluster said eigenvector results to obtain said clusters.

37. The apparatus according to claim 36, wherein

said elements are people found in said plurality of digital images, and

said at least one hard negative constraint includes a negative constraint that two people found in the same image from said plurality of digital images have different identities.

38. The apparatus according to claim 37, wherein said similarity analysis unit comprises:

a face unit for performing a face similarity analysis between faces of said people to obtain face similarity measures between faces of said people,

a clothes unit for performing a clothes similarity analysis between clothes of said people to obtain clothes similarity measures between clothes of said people, and

a combination unit for providing a plurality of formulas for estimating similarity measures for pairs of people from said plurality of digital images to represent the same person, based on availability of said face similarity measures and said clothes similarity measures.

39. The apparatus according to claim 37, further comprising:

a clothes segmentation unit for determining clothes areas in said plurality of digital images via maximizing a difference between neighboring clothes, and removing clutters from said clothes areas, and

a clothes representation unit for performing clothes feature extraction on said clothes areas by

extracting representative image patches from said clothes areas,

generating feature vectors from frequencies of appearance of said representative image patches in said clothes areas to obtain numerical representations for said clothes areas, and

sending said numerical representations for said clothes areas to said similarity analysis unit.

40. The apparatus according to claim 35, wherein

said similarity analysis unit performs a similarity analysis between said elements by

obtaining similarity scores between said elements, and

obtaining an affinity matrix A using said similarity scores;

and

said clustering unit performs clustering of said plurality of elements by

incorporating in said affinity matrix A said at least one hard negative constraint,

generating a repulsion matrix R using said at least one hard negative constraint,

using said affinity matrix A and said repulsion matrix R to obtain said constrained inter-relational data results in the form of an inter-relational data matrix L,

selecting a predetermined number of largest eigenvectors of said inter-relational data matrix L,

stacking selected eigenvectors into columns to obtain a matrix X,

normalizing the rows of said matrix X to unit length to obtain said eigenvector results in the form of a matrix Y,

clustering rows of said matrix Y using K-means clustering to obtain said clusters, and

assigning elements from said plurality of elements to clusters to which rows of said matrix Y associated with said elements are assigned.