Techniques for automatic photo album generation

• US 8,983,193 B1
• Filed: 09/27/2012
• Issued: 03/17/2015
• Est. Priority Date: 09/27/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Carceroni, Rodrigo, Subramanya, Amarnag, Hua, Wei, Fang, Hui, Ordonez Roman, Vicente Ignacio, Gillenwater, Jennifer Ann
• Primary Examiner(s): Le, Vu
• Assistant Examiner(s): WOLDEMARIAM, AKLILU K
• Application Number:
  US13/628,735
• Time in Patent Office: 901 Days
• Field of Search: 382/118, 382/190, 382/224, 382/225, 382/284, 382/305, 382/274, 382/243, 382/125
• US Class Current: 382/190
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 18/2178 based on feedback of a supervisor
• CPC Class Codes: G06F 18/2415 based on parametric or probabilistic models, e.g. based on likelihood ratio or false acceptance rate versus a false rejection rate
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 10/7784 based on feedback from supervisors
• CPC Class Codes: G06V 20/35 Categorising the entire scene, e.g. birthday party or wedding scene

Abstract

A computer-implemented technique can receive, at a computing device including one or more processors, a plurality of photos. The technique can extract quality features and similarity features for each of the plurality of photos and can obtain weights for the various quality features and similarity features based on an analysis of a reference photo collection. The technique can generate a quality metric for each of the plurality of photos and can generate a similarity matrix for the plurality of photos by analyzing the various quality features and similarity features and using the obtained weights. The technique can perform joint global maximization of photo quality and photo diversity using the quality metrics and the similarity matrix in order to select a subset of the plurality of photos having a high degree of representativeness. The technique can then store the subset of the plurality of photos in a memory.

Claims

1. A computer-implemented method comprising:

receiving, by a computing device including one or more processors, a plurality of photos;

extracting, by the computing device, a set of quality features from each of the plurality of photos, the set of quality features including two or more features, wherein each feature of the set of quality features corresponds to a quality of a specific photo, and wherein the set of quality features includes at least one of photometric features, saliency-based features, and content-based features for a specific photo;

extracting, by the computing device, a set of similarity features from each of the plurality of photos, each of the set of similarity features being indicative of a similarity between a specific photo and another one or more of the plurality of photos, the set of similarity features including at least one of spatial resolution, color resolution, and temporal resolution of the specific photo;

obtaining, by the computing device, a quality weight for each feature of the set of quality features by performing machine learning on a reference photo collection using an L2 regularization with an L2-loss function to obtain a set of quality weights wherein the L2 regularization with an L2-loss function is a machine learning regularization function that uses a squared loss function, the reference photo collection including plurality of reference photos and a quality weight associated with each of the plurality of reference photos;

obtaining, by the computing device, a similarity weight for each feature of the set of similarity features based on an analysis of the reference photo collection to obtain a set of similarity weights, the reference photo collection including a similarity weight associated with each unique pair of reference photos in the reference photo collection;

generating, by the computing device, a quality metric for each of the plurality of photos by analyzing the set of quality features for a specific photo to obtain a set of quality scores and combining the set of quality scores using the set of quality weights to obtain the quality metric;

generating, by the computing device, a similarity matrix for the plurality of photos by analyzing the set of similarity features for each unique pair of photos of the plurality of photos to obtain a set of similarity scores and generating the similarity matrix using the set of similarity scores and the set of similarity weights;

selecting, by the computing device, a subset of the plurality of photos by performing joint global maximization of photo quality and photo diversity based on the quality metrics and the similarity matrix using a determinantal point process (DPP) including a maximum-a-posteriori (MAP) approximation algorithm to determine a number of iterations for performing the selection of the selected subset of photos; and

storing by the computing device, the subset of the plurality of photos.

2. A computer-implemented method comprising:

receiving, by a computing device including one or more processors, a plurality of photos;

extracting, by the computing device, a first set of features from each of the plurality of photos, each feature of the first set of features corresponding to a quality of a specific photo;

extracting, by the computing device, a second set of features from each of the plurality of photos, each feature of the second set of features being indicative of a similarity between a specific photo and another one or more of the plurality of photos;

obtaining, by the computing device, a quality weight for each feature of the first set of features based on an analysis of a reference photo collection to obtain a first set of weights, the reference photo collection including plurality of reference photos and a quality weight associated with each of the plurality of reference photos;

obtaining, by the computing device, a similarity weight for each of the second set of features based on an analysis of the reference photo collection to obtain a second set of weights, the reference photo collection including a similarity weight associated with each unique pair of reference photos in the reference photo collection;

generating, by the computing device, a quality metric for each of the plurality of photos by analyzing the first set of features for a specific photo to obtain a set of quality scores and combining the set of quality scores using the first set of weights to obtain the quality metric;

generating, by the computing device, a similarity matrix for the plurality of photos by analyzing the second set of features for each unique pair of photos of the plurality of photos to obtain a set of similarity metrics and generating the similarity matrix using the set of similarity metrics and the second set of weights;

selecting, by the computing device, a subset of the plurality of photos by performing joint global maximization of photo quality and photo diversity based on the quality metrics and the similarity matrix; and

storing, by the computing device, the subset of the plurality of photos.

3. The computer-implemented method of claim 2, wherein the first set of features for a specific photo includes at least one of photometric features, saliency-based features, and content-based features for the specific photo,

wherein the photometric features for the specific photo include at least one of contrast, hue diversity, sharpness, and brightness of the specific photo,

wherein the saliency-based features for the specific photo include at least one of simplicity, composition quality, and lighting quality of the specific photo, and

wherein the content-based features for the specific photo include a presence of at least one of a specific person, a specific place, and a specific thing.

4. The computer-implemented method of claim 3, wherein extracting a specific saliency-based feature for the specific photo further includes:

filtering, by the computing device, the specific photo to identify a salient portion of the specific photo that encompasses greater than a predetermined amount of a salient object in the specific photo; and

extracting, by the computing device, the specific saliency-based feature for the specific photo using the salient portion.

5. The computer-implemented method of claim 2, wherein the second set of features for a specific photo includes at least one of spatial resolution, color resolution, and temporal resolution of the specific photo.

6. The computer-implemented method of claim 5, wherein extracting a specific feature of the second set of features for the specific photo further includes:

generating, by the computing device, a hierarchical histogram for the specific photo, the hierarchical histogram including one or more visual words;

modifying, by the computing device, the hierarchical histogram by adding a timestamp of the specific photo to obtain a modified hierarchical histogram; and

extracting, by the computing device, the specific feature of the second set of features for the specific photo based on the modified hierarchical histogram.

7. The computer-implemented method of claim 2, wherein obtaining the quality weight for each feature of the first set of features further includes performing machine learning on the reference photo collection using an L2 regularization with an L2-loss function, wherein the L2 regularization with an L2-loss function is a machine learning regularization function that uses a squared loss function.

8. The computer-implemented method of claim 2, wherein selecting the subset of the plurality of photos by performing the joint global maximization of photo quality and photo diversity based on the quality metrics and the similarity matrix includes using a determinantal point process (DPP), wherein the DPP includes calculating:

S_ij=q_if(Ø

_i,Ø

_j)q_j,

where S_i,j is a combined matrix of quality and similarity features, q_i is a quality metric for an i^th element, q_j is a quality metric for a j^th element, Φ

_i is a feature vector corresponding to the i^th element, Φ

_j is a feature vector corresponding to the j^th element, and f(Φ

_i,Φ

_j) is a function for calculating a similarity between feature vector Φ

_i and feature vector Φ

_j using the similarity matrix.

9. The computer-implemented method of claim 8, wherein the DPP further includes performing:

(i) initializing Y={ }, J={ };

(ii) adding eigenvector v_k to J with probability λ

_k/(λ

_k+1);

(iii) while |J|>

0, performing;

10. The computer-implemented method of claim 9, wherein the DPP further includes determining a probability for the selected subset of photos Y by calculating:

11. The computer-implemented method of claim 10, wherein the DPP further includes applying a maximum-a-posteriori (MAP) approximation algorithm to determine a number of iterations for performing the selection of the selected subset of photos Y, and wherein the subset of the plurality of photos includes the selected subset of photos Y after the number of iterations, wherein the MAP approximation algorithm is defined as:

(i) receiving an input X, parameters ⊖

, and a budget B,

(ii) U←

S(X) and Y←

{ },

(iii) while U≠

{ }, performing;

12. A computing device, comprising:

an input/output device configured to receive a plurality of photos;

one or more processors configured to;

extract a first set of features from each of the plurality of photos, each feature of the first set of features corresponding to a quality of a specific photo,

extract a second set of features from each of the plurality of photos, each feature of the second set of features being indicative of a similarity between a specific photo and another one or more of the plurality of photos,

obtain a quality weight for each feature of the first set of features based on an analysis of a reference photo collection to obtain a first set of weights, the reference photo collection including plurality of reference photos and a quality weight associated with each of the plurality of reference photos,

obtain a similarity weight for each of the second set of features based on an analysis of the reference photo collection to obtain a second set of weights, the reference photo collection including a similarity weight associated with each unique pair of reference photos in the reference photo collection,

generate a quality metric for each of the plurality of photos by analyzing the first set of features for a specific photo to obtain a set of quality scores and combining the set of quality scores using the first set of weights to obtain the quality metric,

generate a similarity matrix for the plurality of photos by analyzing the second set of features for each unique pair of photos of the plurality of photos to obtain a set of similarity metrics and generating the similarity matrix using the set of similarity metrics and the second set of weights, and

select a subset of the plurality of photos by performing joint global maximization of photo quality and photo diversity based on the quality metrics and the similarity matrix; and

a memory configured to store the subset of the plurality of photos.

13. The computing device of claim 12, wherein the first set of features for a specific photo includes at least one of photometric features, saliency-based features, and content-based features for the specific photo,

wherein the photometric features for the specific photo include at least one of contrast, hue diversity, sharpness, and brightness of the specific photo,

wherein the saliency-based features for the specific photo include at least one of simplicity, composition quality, and lighting quality of the specific photo, and

wherein the content-based features for the specific photo include a presence of at least one of a specific person, a specific place, and a specific thing.

14. The computing device of claim 13, wherein the one or more processors are configured to extract a specific saliency-based feature for the specific photo by:

filtering the specific photo to identify a salient portion of the specific photo that encompasses greater than a predetermined amount of a salient object in the specific photo; and

extracting the specific saliency-based feature for the specific photo using the salient portion.

15. The computing device of claim 12, wherein the second set of features for a specific photo includes at least one of spatial resolution, color resolution, and temporal resolution of the specific photo.

16. The computing device of claim 15, wherein the one or more processors are configured to extract a specific feature of the second set of features for the specific photo by:

generating a hierarchical histogram for the specific photo, the hierarchical histogram including one or more visual words;

modifying the hierarchical histogram by adding a timestamp of the specific photo to obtain a modified hierarchical histogram; and

extracting the specific feature of the second set of features for the specific photo based on the modified hierarchical histogram.

17. The computing device of claim 13, wherein the one or more processors are configured to select the subset of the plurality of photos by performing the joint global maximization of photo quality and photo diversity based on the quality metrics and the similarity matrix includes using a determinantal point process (DPP), wherein the DPP includes calculating:

S_ij=q_if(Ø

_i,Ø

_j)q_i,

where S_i,j is a combined matrix of quality and similarity features, q_i is a quality metric for an i^th element, q_j is a quality metric for a j^th element, Φ

_i is a feature vector corresponding to the i^th element, Φ

_j is a feature vector corresponding to the j^th element, and f(Φ

_i,Φ

_j) is a function for calculating a similarity between feature vector Φ

_i and feature vector Φ

_j using the similarity matrix.

18. The computing device of claim 17, wherein the DPP further includes performing:

(i) initializing Y={ }, J={ };

(ii) adding eigenvector v_k to J with probability λ

_k/(λ

_k+1);

(iii) while |J|>

0, performing;

19. The computing device of claim 18, wherein the DPP further includes determining a probability for the selected subset of photos Y by calculating:

20. The computing device of claim 19, wherein the DPP further includes applying a maximum-a-posteriori (MAP) approximation algorithm to determine a number of iterations for performing the selection of the selected subset of photos Y, and wherein the subset of the plurality of photos includes the selected subset of photos Y after the number of iterations, wherein the MAP approximation algorithm is defined as:

(i) receiving an input X, parameters ⊖

, and a budget B,

(ii) U←

S(X) and Y←

{ },

(iii) while U≠

{ }, performing;