System and method for information seeking in a multimedia collection

• US 8,171,049 B2
• Filed: 02/23/2010
• Issued: 05/01/2012
• Est. Priority Date: 09/18/2009
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Ah-Pine, Julien, Renders, Jean-Michel, Viaud, Marie-Luce
• Primary Examiner(s): Lu, Charles
• Application Number:
  US12/710,783
• Publication Number:
  US 20110072012A1
• Time in Patent Office: 798 Days
• Field of Search: 707/723, 707/736, 707/766, 707/772
• US Class Current: 707/772
• CPC Class Codes: G06F 16/26 Visual data mining; Browsing structured data
• CPC Class Codes: G06F 16/54 Browsing; Visualisation therefor

Abstract

An apparatus and method facilitate combined query based searching with serendipitous browsing in a multimedia collection. A user selects objects to label from a local map, which may include representations of objects retrieved from the collection as being responsive to a text or image base query. The text and image portions of the object can be independently labeled. Unlabeled objects are scored and ranked based on the applied labels of labeled objects, which may take into account cross-media pseudo-relevance and user selectable (or default) parameters, such as a forgetting factor, which tends to place greater weight on more recently labeled objects, and a modality parameter, which laces greater weight on the modality (text, image, or hybrid) currently selected by the user. The local map is modified, based on the ranking, optionally after reranking of objects to improve the diversity of the displayed objects.

Claims

1. A computer-implemented method for information seeking in a multimedia collection of objects comprising:

through a graphical user interface, receiving at least one of an input text query and an input image query;

providing for a user to select a subset of objects from a multimedia collection, at least some of the objects in the collection comprising first and second modalities, wherein the first and second modalities comprise a text modality and an image modality;

displaying representations of objects in the subset on a local map;

at each of a plurality of iterations;

providing for the user to annotate the text and image modalities of an object represented in the local map with a relevance label, wherein an object'"'"'s text modality and image modality are labeled independently;

automatically assigning a default forgetting factor for at least one of the first and second modalities, or providing for the user to select the forgetting factor for the at least one of the first and second modalities;

automatically assigning a default locality factor for at least one annotated object, or providing for the user to select a locality factor for the at least one annotated object;

with a computer processor, computing relevance scores for unlabeled objects in the collection, each relevance score taking into account labels applied to other objects, computed similarity measures between one of the unlabeled objects and the other objects in the collection, the locality factor selected by the user or the default locality factor, and the forgetting factor selected by the user or the default forgetting factor, the forgetting factor placing a greater weight on objects labeled in a more recent iteration;

modifying the local map based on the computed relevance scores; and

displaying the modified local map on a visual display.

2. The method of claim 1, wherein the providing for the user to select a subset of objects from a multimedia collection includes providing for the user to drag one or more objects from a global map into the local map on the graphical user interface, the global map displaying all the objects in the multimedia collection.

3. The method of claim 1, further comprising displaying representations of objects in the subset on a global map on the graphical user interface differently from objects in the multimedia collection that are not part of the subset of objects.

4. The method of claim 1, wherein the labels with which the object modalities are annotated are selected from relevant, non-relevant, and an unsure label.

5. The method of claim 1, wherein the relevance scores for unlabeled objects in the collection take into account:

trans-modality pseudo-relevance terms which consider as relevant, a first modality of an object which has a high computed similarity to another object whose second modality has been labeled as relevant by the user, and vice versa; and

trans-modality pseudo-relevance terms which consider as irrelevant, a first modality of an object which has a high computed similarity to another object whose second modality has been labeled as irrelevant by the user, and vice versa.

6. The method of claim 1, wherein when the user selects a locality factor for an annotated object, the method further comprises automatically selecting one or more of the annotated objects with a locality factor to form nodes in the local map, and wherein the relevance scores take into account whether a labeled object has been assigned a locality factor.

7. The method of claim 1, wherein the method includes providing for the user to select at least one of the first and second modalities and wherein when the user selects one of the first and second modalities, the computed relevance score takes into account the user-selected at least one of the first and second modalities in computing the relevance scores for at least some of the unlabeled objects.

8. The method of claim 1, wherein the method includes providing for the user to select a forgetting factor for at least one of the first and second modalities and wherein when the user selects the forgetting factor for at least one of the first and second modalities, the computed relevance score takes into account the at least one user-selected forgetting factor in computing the relevance scores for at least some of the unlabeled objects.

9. The method of claim 8, wherein the method includes providing for the user to select a first forgetting factor for the first modality and a second forgetting factor for the second modality and wherein when the user selects the first and second forgetting factors, the computed relevance score takes into account at least one of the user-selected first and second forgetting factors in computing the relevance scores for at least some of the unlabeled objects.

10. The method of claim 1, wherein where a first condition is met, a weight vector applied in computing the score for unlabeled objects takes into account the at least one user selected forgetting factor to give a greater weight to a more recently labeled object modality than to a less recently labeled object modality.

11. The method of claim 10, wherein where a second condition is met, the weight vector applied in computing the score for unlabeled objects takes into account that the user has returned to results of a prior iteration.

12. The method of claim 11, wherein where a third condition is met, the weight vector applied in computing the score for unlabeled objects takes into account that the user has selected an object to serve as a node in the local map.

13. The method of claim 1, further comprising reranking unlabeled objects in the collection for which scores have been computed to increase diversity in the subset of objects displayed in the local map.

14. The method of claim 1, wherein, in the local map, the labeled objects are displayed differently depending on applied positive and negative labels for each of the modalities.

15. The method of claim 1, wherein the relevance scores for unlabeled objects in the collection are computed with an equation which includes:

a first term which takes into account relevance feedback and pseudo-relevance feedback of positively labeled text portions of other objects;

a second term which takes into account relevance feedback and pseudo-relevance feedback of negatively labeled text portions of other objects;

a third term which takes into account relevance feedback and pseudo-relevance feedback of positively labeled image portions of other objects; and

a fourth term which takes into account relevance feedback and pseudo-relevance feedback of negatively labeled image portions of other objects.

16. The method of claim 15, wherein in the equation, each term includes a respective normalized weight vector α

_T^t, β

_T^t, α

_I^t, β

_I^t, which, under one condition, is a function of the forgetting factor.

17. The method of claim 15, wherein the equation further includes at least one of:

a weight applied to the first and second terms according to at least one modality selected by the user; and

a weight applied to the third and fourth terms according to at least one modality selected by the user.

18. A non-transitory computer-readable storage medium encoding instructions, which when executed on a computer causes the computer to perform the method of claim 1.

25. The method of claim 1, further comprising:

storing the multimedia collection of objects in computer-readable memory;

storing similarity matrices for text portions and image portions of the objects in the collection in computer-readable memory;

receiving an input user query selected from a text query, an image query, and a combination thereof;

retrieving a subset of the objects in the collection, based on the user query, and displaying representations of the retrieved objects in the subset in the two-dimensional local map on a display;

providing access to an underlying object of a user-selected object representation displayed in the local map;

providing for the user to label at least one of the text part and the image part of the selected object with a relevance label, whereby the image part and text part of a multimedia object are able to be independently labeled with different relevance labels;

wherein in the computing relevance scores for unlabeled objects in the collection, each relevance score is a function of the user-applied relevance labels to other objects in the collection and respective similarity measures retrieved from the similarity matrices;

reranking the relevance scores to increase diversity; and

modifying the local map based on the reranked relevance scores.

19. An apparatus comprising:

a graphical user interface;

memory which stores instructions for;

receiving at least one of an input text query and an input image query through the graphical user interface;

providing for a user to select a subset of objects from a multimedia collection, at least some of the objects in the collection comprising first and second modalities, wherein the first and second modalities comprise a text modality and an image modality;

displaying representations of objects in the subset on a local map;

at each of a plurality of iterations;

providing for the user to annotate the text and image modalities of an object represented in the local map with a relevance label, wherein an object'"'"'s text modality and image modality are labeled independently;

automatically assigning a default forgetting factor for at least one of the first and second modalities, or providing for the user to select the forgetting factor for the at least one of the first and second modalities;

automatically assigning a default locality factor for at least one annotated object, or providing for the user to select a locality factor for the at least one annotated object;

computing relevance scores for unlabeled objects in the collection, each relevance score taking into account labels applied to other objects, computed similarity measures between one of the unlabeled objects and the other objects in the collection, the locality factor selected by the user or the default locality factor, and the forgetting factor selected by the user or the default forgetting factor, the forgetting factor placing a greater weight on objects labeled in a more recent iteration;

modifying the local map based on the computed relevance scores; and

displaying the modified local map on a visual display; and

a processor in communication with the memory for executing the instructions.

20. The apparatus of claim 19, further comprising:

memory which stores a multimedia collection of objects, at least some of the objects in the collection comprising first and second modalities, and stores similarity matrices for the objects in the collection for each of the first and second modalities;

the graphical user interface, which is configured to display a global map and the local map of objects in the multimedia collection, the local map including representations of a subset of the objects in the multimedia collection, the graphical user interface configured to input parameters for relevance scoring selected from a modality parameter, a locality parameter, and the forgetting factor parameter, and inputting relevance labels for objects, whereby an object'"'"'s first modality and second modality are able to be labeled independently; and

the instructions comprising;

a ranking component which computes the relevance scores for unlabeled objects in the collection based on labels applied to other objects, the selected parameters, the similarity matrices; and

a graph layout component for modifying the local map based on the computed relevance scores.

21. The apparatus of claim 20, wherein the ranking component and graph layout component include instructions stored in memory which are executed by an associated computer processor, the apparatus further comprising a text search engine and an image search engine for selectively querying the collection based on an input user query.

22. The apparatus of claim 20, further comprising a reranking component which reranks scored unlabeled objects to increase diversity of objects displayed in the local map, the a graph layout component modifying the local map based on the computed relevance scores are modified by the reranking component.

23. The apparatus of claim 20, wherein the first modality is a text modality and the second modality is an image modality and wherein the ranking component computes relevance scores with an equation which includes:

a first term which takes into account relevance feedback and pseudo-relevance feedback of positively labeled text portions of other objects;

a second term which takes into account relevance feedback and pseudo-relevance feedback of negatively labeled text portions of other objects;

a third term which takes into account relevance feedback and pseudo-relevance feedback of positively labeled image portions of other objects; and

a fourth term which takes into account relevance feedback and pseudo-relevance feedback of negatively labeled image portions of other objects.

24. The method of claim 23, wherein the equation further includes at least one of:

a weight applied to the first and second terms according to at least one of text and image modalities selected by the user; and

a weight applied to the third and fourth terms according to at least one of text and image modalities selected by the user.