Retrieval system and method leveraging category-level labels

• US 9,075,824 B2
• Filed: 04/27/2012
• Issued: 07/07/2015
• Est. Priority Date: 04/27/2012
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Gordo, Albert, Rodriguez Serrano, Jose Antonio, Perronnin, Florent
• Primary Examiner(s): Vincent, David
• Assistant Examiner(s): BUSS, BENJAMIN J
• Application Number:
  US13/458,183
• Publication Number:
  US 20130290222A1
• Time in Patent Office: 1,166 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 18/2135 based on approximation criteria, e.g. principal component analysis
• CPC Class Codes: G06F 18/2155 characterised by the incorporation of unlabelled data, e.g. multiple instance learning [MIL], semi-supervised techniques using expectation-maximisation [EM] or naïve labelling

Abstract

An instance-level retrieval method and system are provided. A representation of a query image is embedded in a multi-dimensional space using a learned projection. The projection is learned using category-labeled training data to optimize a classification rate on the training data. The joint learning of the projection and the classifiers improves the computation of similarity/distance between images by embedding them in a subspace where the similarity computation outputs more accurate results. An input query image can thus be used to retrieve similar instances in a database by computing the comparison measure in the embedding space.

Claims

1. A retrieval method comprising:

learning a projection for embedding an original image representation in an embedding space, the original image representation being based on features extracted from the image, the projection being learned from category-labeled training data to optimize a classification rate on the training data, the learning of the projection including, for a plurality of iterations;

selecting a sample from the training data;

embedding the sample with a current projection;

scoring the embedded sample with current first and second classifiers, the first classifier corresponding to a category of the label of the sample, the second classifier corresponding to a different category, selected from a set of categories;

updated the current projection and at least one of the current first and second classifier for iterations where the second classifier generates a higher score than the first classifier, the updated projection serving as the current projection for a subsequent iteration, each of the updated classifiers serving as the current classifier for the respective category for a subsequent iteration; and

storing one of the updated projections as the learned projection; and

with a processor, for each of plurality of database images, computing a comparison measure between a query image and the database image, the comparison measure being computed in the embedding space, respective original image representations of the query image and the database image being embedded in the embedding space with the projection; and

providing for retrieving at least one of the database images based on the comparison.

2. The method of claim 1, wherein the learning of the projection is performed jointly with learning a respective classifier for each of a set of the categories.

3. The method of claim 1, wherein the learning of the projection includes optimizing an objective function which sums, over a set of samples and categories, a function of a score of the sample on the classifier corresponding to its category and a score of the sample on a classifier not corresponding to its category.

4. The method of claim 3, wherein the learning of the projection includes optimizing the objective function with stochastic gradient descent.

5. The method of claim 1, wherein the classifiers are updated as a function of the embedded sample and a learning rate.

6. The method of claim 1, wherein the classifiers are updated as according to the expressions:

w_y+←

w_y++η

Uq

and

w_y−

←

w_y−

−

η

Uq

where η

represents a learning rate, Uq represents the sample embedded with the projection, w_y+ represents the first classifier and w_y−

represents the second classifier.

7. The method of claim 1, wherein the projection is updated as a function of the first and second classifiers and a learning rate.

8. The method of claim 1, wherein the projection is updated according to the expression:

U←

U+η

(w_y+−

w_y−

)q′

where η

represents a learning rate, U represents the projection matrix, q is a feature-based representation of the sample, w_y+ represents the first classifier and w_y−

represents the second classifier.

9. The method of claim 1, further comprising generating an original representation of the query image based on the extracted features and wherein the computing of the comparison between the query image and the database image comprises embedding the original representation of the query image with the projection matrix.

10. The method of claim 1, wherein the original representation comprises a statistical representation of the extracted features.

11. The method of claim 10, wherein the original representation comprises at least one of a Fisher Vector and a Bag-of-Visual-words representation.

12. The method of claim 1, wherein the original representation is of higher dimensionality than the embedded representation.

13. The method of claim 1, wherein the comparison measure is a distance measure and the computing of the distance measure includes computing a dot product between the query image and the database image embedded in the embedding space.

14. The method of claim 1, wherein the projection comprises a projection matrix.

15. The method of claim 1, further comprising outputting at least one of:

at least one of the retrieved images, and

a decision based on at least one of the retrieved images.

16. The method of claim 15, wherein the decision is used for at least one of duplicate removal and copy detection.

17. A computer program product comprising a non-transitory recoding medium storing instructions which when executed by a computer, perform the method of claim 1.

18. A system comprising memory which stores instructions for performing the method of claim 1 and a processor in communication with the memory which implements the instructions.

19. A retrieval method comprising:

with a processor, learning a projection for embedding an original image representation in an embedding space, the original image representation being based on features extracted from the image, the projection being learned from category-labeled training data to optimize a classification rate on the training data, the learning of the projection including optimizing an objective function of the form;

Σ

<sub>(q,y+,y−

)</sub>min{0,t−

s(q,y+)+s(q,y−

)}

where t represents a predetermined threshold, q represents a sample, s(q,y+) represents a score of the sample on the classifier corresponding to its category and s(q,y−

) represents a score of the sample on a classifier not corresponding to its category; and

for each of plurality of data base images, computing a comparison measure between a query image and the database image, the comparison measure being computed in the embedding space, respective original image representations of the query image and the database image being embedded in the embedding space with the projection; and

providing for retrieving at least one of the database images based on the comparison.

20. The method of claim 19, wherein the learning of the projection includes, for a plurality of iterations:

selecting a sample from the training data;

embedding the sample with a current projection;

scoring the embedded sample with current first and second classifiers, the first classifier corresponding to a category of the label of the sample, the second classifier corresponding to a different category, selected from a set of categories; and

updating the current projection and at least one of the current first and second classifiers for iterations where the second classifier generates a higher score than the first classifier, the updated projection serving as the current projection for a subsequent iteration, each of the updated classifiers serving as the current classifier for the respective category for a subsequent iteration; and

storing an updated projection as the learned projection.

21. A retrieval system comprising:

memory which stores;

a projection matrix for embedding image features in an embedding space, the projection matrix having been learned from category-labeled training data to optimize a classification rate on the training data, including, for a plurality of iterations;

selecting a sample from the training data;

embedding the sample with a current projection;

scoring the embedded sample with current first and second classifiers, the first classifier corresponding to a category of the label of the sample, the second classifier corresponding to a different category, selected from a set of categories;

updating the current projection and at least one of the current first and second classifiers for iterations where the second classifier generates a higher score than the first classifier, the updated projection serving as the current projection for a subsequent iteration, each of the updated classifiers serving as the current classifier for the respective category for a subsequent iteration; and

storing an updated projection as the learned projection; and

instructions for computing a comparison between a query image and a database image whose respective features are embedded in the embedding space with the projection matrix; and

a processor in communication with the memory which implements the instructions.

22. The system of claim 21, further comprising a database which stores a set of the database images.

23. The system of claim 21, wherein the database image comprises a plurality of database images and the instructions include instructions for identifying fewer than all of the plurality of database images as similar to the query image.

24. The system of claim 23, further comprising an output device for outputting at least one of:

at least one of the identified similar database images, and

a decision based on at least one of the identified similar database images.

25. A retrieval method comprising:

providing a feature-based representation and a category label for each of a set of training images, each of the category labels corresponding to a respective one of a set of categories;

jointly learning a projection and set of classifiers based on the feature-based representations and category labels, the learning optimizing a classification of the training images by the set of classifiers in an embedding space into which the feature-based representations are embedded with the projection, the set of classifiers including a classifier for each of the categories;

storing the projection for embedding a query image and database images into the embedding space;

receiving a query image; and

without using the learned set of classifiers, retrieving at least one the database images based on a computed comparison measure between the query image and the database images embedded in the embedding space with the learned projection.

26. The method of claim 25, wherein the projection comprises a projection matrix.

27. The method of claim 26, wherein the projection matrix is an R×

D projection matrix, where R is a number of dimensions in the embedding space and D is a number of dimensions in each of the feature-based representations and where D is greater than R.