RETRIEVAL SYSTEM AND METHOD LEVERAGING CATEGORY-LEVEL LABELS

• US 20130290222A1
• Filed: 04/27/2012
• Published: 10/31/2013
• Est. Priority Date: 04/27/2012
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Gordo, Albert, Perronnin, Florent, Rodriguez Serrano, Jos Antonio
• Granted Patent: US 9,075,824 B2
• Time in Patent Office: Days
• US Class Current: 706/12
• 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:

providing 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 having been learned from category-labeled training data to optimize a classification rate on the training data; 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, further comprising learning the projection.

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

4. The method of claim 2, 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.

5. The method of claim 4, wherein the learning of the projection includes optimizing an objective function of the form:

Σ

<sub>(q,y+,y−

)</sub>min{0,t−

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

)} 

 

(3)

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.

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

7. The method of claim 2, 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.

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

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

w_y+←

w_y++η

Uq 

 

(4)

w_y−

←

w_y−

−

η

Uq 

 

(5)

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.

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

11. The method of claim 7, wherein the projection is updated according to the expression:

U←

U+η

(w_y+−

w_y−

)q′

 

 

(6)

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.

12. 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.

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

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

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

16. 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.

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

18. 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.

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

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

21. 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.

22. 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; 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.

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

24. The system of claim 22, 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.

25. The system of claim 24, 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.

26. A method of generating a retrieval system, 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; and

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

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

28. The method of claim 27, 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.