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

Claim 2

A digital image processing method for performing clustering of digital image data by utilizing one or more processors, 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, using at least one processor, 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.

Claim 3

The digital image processing method for performing clustering of digital image data by utilizing one or more processors as recited in claim 1 , wherein said sub-step of performing discretization uses constrained K-means clustering.

Claim 4

The digital image processing method for performing clustering of digital image data by utilizing one or more processors as recited in claim 1 , wherein said elements are people found in said plurality of digital images.

Claim 5

The digital image processing method for performing clustering of digital image data by utilizing one or more processors 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.

Claim 6

The digital image processing method for performing clustering of digital image data by utilizing one or more processors 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.

Claim 7

The digital image processing method for performing clustering of digital image data by utilizing one or more processors 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.

Claim 8

The digital image processing method for performing clustering of digital image data by utilizing one or more processors 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.

Claim 9

The digital image processing method for performing clustering of digital image data by utilizing one or more processors 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.

Claim 10

The digital image processing method for performing clustering of digital image data by utilizing one or more processors as recited in claim 8 , wherein clothes in said plurality of digital images include at least one of clothing, shoes, watch, and eyeglasses.

Claim 11

The digital image processing method for performing clustering of digital image data by utilizing one or more processors 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.

Claim 12

The digital image processing method for performing clustering of digital image data by utilizing one or more processors as recited in claim 1 , wherein number of said clusters is predetermined before said step of performing clustering of said plurality of elements.

Claim 13

The digital image processing method for performing clustering of digital image data by utilizing one or more processors 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.

Claim 14

The digital image processing method for performing clustering of digital image data by utilizing one or more processors 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.

Claim 15

The digital image processing method for performing clustering of digital image data by utilizing one or more processors 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.

Claim 16

A digital image processing method for performing clustering of digital image data by utilizing one or more processors, 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, using at least one processor, 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, wherein clustering is performed to enforce said hard constraint.

Claim 17

A digital image processing method for performing clustering of digital image data by utilizing one or more processors, 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, using at least one processor, 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, wherein clustering is performed to enforce said hard constraint.

Claim 18

The digital image processing method for performing clustering of digital image data by utilizing one or more processors 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.

Claim 19

The digital image processing method for performing clustering of digital image data by utilizing one or more processors 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.

Claim 20

The digital image processing method for performing clustering of digital image data by utilizing one or more processors 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.

Claim 21

The digital image processing method for performing clustering of digital image data by utilizing one or more processors 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.

Claim 22

The digital image processing method for performing clustering of digital image data by utilizing one or more processors 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.

Claim 23

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.

Claim 24

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.

Claim 25

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

Claim 26

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

Claim 27

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.

Claim 28

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.

Claim 29

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.

Claim 30

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.

Claim 31

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.

Claim 32

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

Claim 33

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.

Claim 34

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

Claim 35

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.

Claim 36

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.

Claim 37

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.

Claim 38

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, wherein clustering is performed to enforce said hard constraint.

Claim 39

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, wherein clustering is performed to enforce said hard constraint.

Claim 40

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

Claim 41

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.

Claim 42

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.

Claim 43

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.

Claim 44

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.