DEVICE, SYSTEM, AND METHOD OF VISUAL INFERENCE BY COLLABORATIVE COMPOSITION

• US 20130156348A1
• Filed: 12/13/2012
• Published: 06/20/2013
• Est. Priority Date: 12/15/2011
• Status: Active Grant

• Current Assignee: Yeda Research and Development Co. Ltd. (Weizmann Institute of Science)
• Original Assignee: Michal Irani
• Inventors: IRANI, Michal, FAKTOR, Alon
• Granted Patent: US 9,218,365 B2
• Time in Patent Office: Days
• US Class Current: 382/305
• CPC Class Codes: G06F 16/53 Querying
• CPC Class Codes: G06F 16/55 Clustering; Classification
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06V 10/464 using a plurality of salient features, e.g. bag-of-words [BoW] representations
• CPC Class Codes: G06V 10/761 Proximity, similarity or dissimilarity measures
• CPC Class Codes: G06V 10/762 using clustering, e.g. of similar faces in social networks
• CPC Class Codes: G06V 20/30 in albums, collections or shared content, e.g. social network photos or video

Abstract

Device, system, and method of visual inference by collaborative composition. A method of searching for similar target content-items for a plurality of source content-items, the method implementable on a computing device, comprises: for each of said plurality of source content-items, searching for similar target content-items in a dataset, while taking into account collaborative feedback exchanged among at least some of currently-searched said plurality of source content-items.

Claims

1. A method of searching for similar target content-items for a plurality of source content-items, the method implementable on a computing device, the method comprising:

for each of said plurality of source content-items, searching for similar target content-items in a dataset, while taking into account collaborative feedback exchanged among at least some of currently-searched said plurality of source content-items.

2. The method of claim 1, wherein said plurality of source content-items are contained in said dataset of target content-items.

3. The method of claim 1, wherein said searching comprises:

measuring similarity between each one of said source content-items and a small subset of target content-items in said dataset, wherein said small subset is unique to each one of said source content-items and is determined by collaborative feedback exchanged among said plurality of source content-items.

4. The method of claim 1, wherein said searching comprises computing similarity-by-composition, wherein said computing similarity-by-composition comprises measuring similarity of detected shared regions among said source content-items and said target content-items.

5. The method of claim 4, wherein detecting said shared regions comprises:

for source descriptors of a source content-item, randomly sampling target descriptors among target content-items; and

propagating good matches of source-target descriptors to neighboring descriptors in said source content-item and in one or more matching target content-items.

6. The method of claim 5, wherein said randomly sampling comprises at least one of:

uniform random sampling, and

randomly sampling by utilizing a modifiable sampling distribution.

7. The method of claim 6, comprising:

dynamically modifying said modifiable sampling distribution between two consecutive search iterations, based on said collaborative feedback.

8. The method of claim 6, wherein said modifiable sampling distribution is specific to said source content-item.

9. The method of claim 4, wherein said detected shared regions are at least one of:

large shared regions, and

statistically significant regions.

10. The method of claim 4, wherein said measuring similarity of detected shared regions comprises computing a likelihood ratio according to an equation:

11. The method of claim 10, wherein said degree of similarity is a function of at least one of the following:

sum-of-differences, sum-of-squared differences, sum-of-absolute-differences, an Lp norm measure, mutual information, correlation, normalized correlation, a robust measure, a histogram comparison measure, a motion consistency measure, and a probability measure.

12. The method of claim 10, wherein p(R|X)=Π

_ip(d_i|X),

wherein said d_i are descriptors composing said region R.

13. The method of claim 12, wherein said descriptors are at least one of:

an image descriptor, a Scale-Invariant Feature Transform (SIFT) descriptor, a Speeded Up Robust Features (SURF) descriptor, a Histogram Oriented Gradients (HOG) descriptor, a shape-context descriptor, a self-similarity descriptor, a local-binary pattern descriptor, a color descriptor, a greyscale descriptor, a normalized color descriptor, a normalized greyscale descriptor, a gradient based descriptor, a normalized gradient based descriptor, a video descriptor, a HOG-3D descriptor, a Histogram of Optical Flow (HOF) descriptor, a a flow field based descriptor, a normal flow based descriptor, a motion based descriptor, a temporal derivative based descriptor, a normalized temporal derivative based descriptor, an audio descriptor, a spectogram based descriptor, a Cepstrum based descriptors, a Mel-Frequency Cepstral Coefficient (MFCC), a Short Time Fourier Transform (STFT) descriptor, a Constant Q-Transform (CQT) descriptor, a descriptor in the spectral domain of an audio signal.

14. The method of claim 10, wherein said p(R|H₀) is estimated by utilizing an error of descriptors composing said region R with respect to a quantized codebook of descriptors.

15. The method of claim 14, wherein said error of at least one of said descriptors is an error computed with respect to at least one nearest neighbor of said at least one of said descriptors in said quantized codebook.

16. The method of claim 14, comprising:

generating said quantized codebook from a collection of descriptors by at least one of;

k-means clustering of said collection of descriptors,

hierarchal clustering of said collection of descriptors,

random sampling from said collection of descriptors.

17. The method of claim 1, wherein said content-items comprise at least one of:

images, video sequences, and audio items.

18. The method of claim 3, wherein said small subset comprises also a randomly sampled small subset generated by randomly sampling based on a sampling distribution, wherein said sampling distribution comprises at least one of:

a uniform distribution,

a non-uniform distribution, and

a dynamically modifiable sampling distribution based on said collaborative feedback.

19. The method of claim 18, comprising:

updating said modifiable sampling distribution, for a particular source content-item, by utilizing a function that comprises at least one of the following;

a first sampling distribution component corresponding to a subset in which said particular source content-item found other similar content items;

a second sampling distribution component corresponding to a subset in which another, similar, content-item found similar content-items; and

a third sampling distribution component corresponding to uniform sampling of said dataset.

20. The method of claim 3, wherein said small subset comprises one or more target content-items that are suggested for searching based on collaborative feedback from one or more source content-items.

21. The method of claim 1, wherein the collaborative feedback comprises suggestions obtained from source content-items indicating to each other where to sample in said dataset in a subsequent search iteration.

22. The method of claim 1, wherein the collaborative feedback comprises at least a sparse set of meaningful affinities among source content-items.

23. The method of claim 1, comprising:

based on affinity output of the searching, performing at least one of;

content-item clustering, content-item classification, content-item retrieval, detecting informative content-items, localization of information within content-items, label transfer, annotation, and generating links between content-items.

24. A computing device for searching for similar target content-items for a plurality of source content-items, the computing device comprising:

a searcher module to search, for each of said plurality of source content-items, for similar target content-items in a dataset, while taking into account collaborative feedback exchanged among at least some of currently-searched said plurality of source content-items.

25. The computing device of claim 24, wherein said plurality of source content-items are contained in said dataset of target content-items.

26. The computing device of claim 24, comprising:

an affinity calculator to measure similarity between each one of said source content-items and a small subset of target content-items in said dataset, wherein said small subset is unique to each one of said source content-items and is determined by collaborative feedback exchanged among said plurality of source content-items.

27. The computing device of claim 24, wherein said affinity calculator computes similarity-by-composition by measuring similarity of detected shared regions among said source content-items and said target content-items.

28. The computing device of claim 27, comprising:

a sampling module to randomly sample, for source descriptors of a source content-item, target descriptors among target content-items; and

a propagation module to propagate good matches of source-target descriptors to neighboring descriptors in said source content-item and in one or more matching target content-items.