Device, system, and method of visual inference by collaborative composition

• US 9,218,365 B2
• Filed: 12/13/2012
• Issued: 12/22/2015
• Est. Priority Date: 12/15/2011
• Status: Active Grant

• Current Assignee: Yeda Research and Development Co. Ltd. (Weizmann Institute of Science)
• Original Assignee: Yeda Research and Development Co. Ltd. (Weizmann Institute of Science)
• Inventors: Irani, Michal, Faktor, Alon
• Primary Examiner(s): Tran, Phuoc
• Application Number:
  US13/712,982
• Publication Number:
  US 20130156348A1
• Time in Patent Office: 1,104 Days
• US Class Current: 1/1
• 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 computer implemented method of searching for similar target content-items for a plurality of source content-items, all stored in at least one memory unit 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;

wherein said searching further comprising at least one of;

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

computing similarity-by-composition by measuring similarity of detected shared regions among said source content-items and said target 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 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.

4. The method of claim 3, wherein said randomly sampling comprises at least one of:

uniform random sampling, and

randomly sampling by utilizing a modifiable sampling distribution.

5. The method of claim 4, comprising:

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

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

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

large shared regions, and

statistically significant regions.

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

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

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

_ip (d_i|X),

wherein said d_i are descriptors composing said region R.

11. The method of claim 10, 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 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 spectrogram 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.

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

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

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

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

images, video sequences, and audio items.

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

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

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

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

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

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

22. The method of claim 1, wherein said measuring similarity between each one of said source content-items and said small subset of said target content-items in said dataset comprises summing up savings-in-bits (savings) according to an equation:

savings(Q|Ref)=Σ

_i=1^rsavings (R_i|Ref)

wherein R₁ is region i out of r regions in one of said source content-items Q,

wherein Ref is one of said target content-items which shares at least one similar region.

23. A computing device, having one or more memory units, for searching for similar target content-items for a plurality of source content-items, all stored in at least one of said memory units, the computing device comprising:

a searcher module, stored in at least one of said memory units, configured 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;

an affinity calculator, stored in at least one of said memory units, configured to measure similarity between each one of said source content-items and a small subset of target content-items in said dataset, said small subset is unique to each one of said source content-items and is determined by said collaborative feedback; and

an output unit, configured to output searching results of said searching module.

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

25. The computing device of claim 23, 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.

26. The computing device of claim 25, comprising:

a sampling module, stored in at least one of said memory units, configured to randomly sample for source descriptors of a source content-item, target descriptors among target content-items; and

a propagation module, stored in at least one of said memory units, configured 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.