Interdependent learning of template map and similarity metric for object identification

• US 8,249,361 B1
• Filed: 04/22/2010
• Issued: 08/21/2012
• Est. Priority Date: 04/22/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Steffens, Johannes B.
• Primary Examiner(s): MARIAM, DANIEL G
• Application Number:
  US12/765,728
• Time in Patent Office: 852 Days
• Field of Search: 382/103, 382/118, 382/159, 382/209, 382/218
• US Class Current: 382/209
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: G06V 10/761 Proximity, similarity or dissimilarity measures
• CPC Class Codes: G06V 10/774 Generating sets of training patterns; Bootstrap methods, e.g. bagging or boosting

Abstract

An object identification system iteratively learns both a template map used to transform a template describing an object in an image, and a related similarity metric used in comparing one transformed object template to another. This automatic learning eliminates the need to manually devise a transformation and metric that are effective for a given image corpus. The template map and the similarity metric are learned together, such that the incremental component to be added to the template map at a given iteration of the learning process is based at least in part on the components of the similarity metric, and vice-versa.

Claims

1. A computer-implemented method of generating a template map and a similarity metric used to determine a degree of visual similarity of two digital objects, comprising:

storing a set of raw object templates, each raw object template representing image features derived from an object within a digital image of a corpus;

iteratively performing an incremental learning process comprising;

at each iteration, adding a map component to a template map that transforms a raw object template to a reduced object template, the reduced object template being stored in less memory than the raw object template;

at each iteration, adding a metric component to a similarity metric that accepts as input two reduced object templates produced by the template map from raw object templates and produces as output a similarity score representing visual similarity of the objects represented by the two reduced object templates;

wherein the metric component is added to the similarity metric based at least in part on values of the template map, and the map component is added to the template map based at least in part on values of the similarity metric; and

storing the template map and the similarity metric.

2. The method of claim 1, wherein the template map employs a linear map matrix that maps a raw object template to a modified object template having fewer elements than the raw object template.

3. The method of claim 2, wherein the similarity metric employs one or more matrices, and wherein the template map further employs a quantizer function that maps elements of the modified object template to integers representing index values indexing into the one or more matrices of the similarity metric, thereby producing the reduced object template.

4. The method of claim 1, wherein adding the map component to the template map and adding the metric component to the similarity metric comprise:

specifying a pool of candidate components, the pool comprising candidate map components and candidate metric components;

for pairs of the candidate map components and candidate metric components, computing loss values corresponding to amounts of identification error of each of the pairs when identifying objects corresponding to the set of raw object templates;

identifying optimal pairs based at least in part on the computed loss values; and

responsive to the identifying, incorporating the identified optimal pairs into the template map and the similarity metric.

5. The method of claim 4, further comprising terminating the learning process responsive to at least one of:

a predetermined number of iterations being reached; and

a loss value of the identified optimal pairs being at least as great as a loss value of identified optimal components from a previous iteration.

6. The method of claim 4, wherein the pool of candidate components is specified dynamically at each iteration.

7. The method of claim 4, wherein the pool of candidate components is the same at each iteration.

8. The method of claim 4, wherein the loss values are obtained from a loss function for which a closed-form solution exists.

9. The method of claim 1, wherein the raw object templates are vectors, each vector element describing visual characteristics of a different portion of the object.

10. The method of claim 9, wherein the visual characteristics comprise one or more of color information, texture information, and edge information.

11. The method of claim 1, wherein the reduced object templates are stored within one kilobyte of memory or less.

12. The method of claim 1, further comprising:

receiving a first reduced template representing a first object, and a second reduced template representing a second object; and

applying the learned template map and the learned similarity metric to compute a similarity score representing visual similarity of the first reduced template and the second reduced template.

13. An object identification system for learning how to identify objects in a corpus of digital images, comprising:

a data repository comprising a set of raw object templates, each raw object template representing image features derived from an object within a digital image of the corpus; and

a learning module configured to;

iteratively perform an incremental learning process comprising;

at each iteration, adding a map component to a template map that transforms a raw object template to a reduced object template, the reduced object template being stored in less memory than the raw object template;

at each iteration, adding a metric component to a similarity metric that accepts as input two reduced object templates produced by the template map from raw object templates and produces as output a similarity score representing visual similarity of the objects represented by the two reduced object templates;

wherein the metric component is added to the similarity metric based at least in part on values of the template map, and the map component is added to the template map based at least in part on values of the similarity metric; and

store the template map and the similarity metric in the data repository.

14. The system of claim 13, wherein the template map employs a linear map matrix that maps a raw object template to a modified object template having fewer elements than the raw object template.

15. The system of claim 14, wherein the similarity metric employs one or more matrices, and wherein the template map further employs a quantizer function that maps elements of the modified object template to integers representing index values indexing into the one or more matrices of the similarity metric, thereby producing the reduced object template.

16. The system of claim 13, wherein adding the map component to the template map and adding the metric component to the similarity metric comprise:

specifying a pool of candidate components, the pool comprising candidate map components and candidate metric components;

for pairs of the candidate map components and candidate metric components, computing loss values corresponding to amounts of identification error of each of the pairs when identifying objects corresponding to the set of raw object templates;

identifying optimal pairs based at least in part on the computed loss values; and

responsive to the identifying, incorporating the identified optimal pairs into the template map and the similarity metric.

17. A non-transitory computer readable storage medium storing a computer program executable by a processor for learning how to identify objects in a corpus of digital images, the action of the computer program comprising:

storing a set of raw object templates, each raw object template representing image features derived from an object within a digital image of the corpus;

iteratively performing an incremental learning process comprising;

at each iteration, adding a map component to a template map that transforms a raw object template to a reduced object template, the reduced object template being stored in less memory than the raw object template;

at each iteration, adding a metric component to a similarity metric that accepts as input two reduced object templates produced by the template map from raw object templates and produces as output a similarity score representing visual similarity of the objects represented by the two reduced object templates;

wherein the metric component is added to the similarity metric based at least in part on values of the template map, and the map component is added to the template map based at least in part on values of the similarity metric; and

storing the template map and the similarity metric.

18. The computer readable storage medium of claim 17, wherein adding the map component to the template map and adding the metric component to the similarity metric comprise:

specifying a pool of candidate components, the pool comprising candidate map components and candidate metric components;

for pairs of the candidate map components and candidate metric components, computing loss values corresponding to amounts of identification error of each of the pairs when identifying objects corresponding to the set of raw object templates;

identifying optimal pairs based at least in part on the computed loss values; and

responsive to the identifying, incorporating the identified optimal pairs into the template map and the similarity metric.

19. The computer readable storage medium of claim 17, wherein the reduced object templates are stored within one kilobyte of memory or less.

20. A computer-implemented method of generating a template map and a similarity metric for determining a measure of visual similarity of two images, the method comprising:

initializing a template map for producing, from a plurality of real value features derived from the image, a reduced plurality of features that includes a plurality of integer value features representing the image;

initializing a similarity metric that compares the reduced plurality of features of a first image to the reduced plurality of features of a second image;

updating the template map and the similarity metric by iteratively performing the steps of;

selecting a map component from a group of candidate map components;

selecting a metric component from a group of candidate metric components;

comparing a first image and a second image using the template map, the selected map component, the similarity metric, and the selected metric component;

generating a measure of recognition accuracy for the comparison;

responsive to the measure of recognition accuracy having at least a threshold value, selectively adding the map component to the template map and selectively adding the selected metric component to the similarity metric; and

storing the generated template map and the generated similarity metric.

21. A computer-implemented method of learning to compute degrees of similarity between human faces in digital images, comprising:

storing a plurality of training images containing a human face;

from each training image, associating with the training image a raw face template representing the face in the training image, thereby producing training face templates, the raw face template being a vector having n elements, for some integer n;

initializing the following to empty;

a linear map matrix adapted to store row vectors having n elements,

a quantizer function adapted to map a scalar value to an index integer of one of a set of ranges, and

a similarity matrix set adapted to store a plurality of matrices each having q rows and q columns, for some integer q;

iteratively performing the following operations;

specifying a plurality of candidate vectors having n elements, and a plurality of candidate matrices having q rows and q columns;

for a candidate vector of the selected plurality of candidate vectors and a candidate matrix of the selected plurality of candidate matrices;

computing a loss value quantifying face identification inaccuracy based at least in part on the candidate vector, the candidate matrix, the training face templates, the linear map matrix, the quantizer function, and the similarity matrix set;

determining that the candidate vector and the candidate matrix produce a lowest loss value with respect to others of the candidate vectors and candidate matrices;

appending the candidate vector to the linear map matrix;

appending the candidate matrix to the similarity matrix set;

terminating the iterative performing of the operations responsive to one or more of;

having performed a number of iterations exceeding a threshold number of iterations, and

the computed loss value not being a threshold amount lower than a loss value from a directly preceding iteration; and

storing the linear map matrix, the quantizer function, and the similarity matrix set.