Matching of modified visual and audio media

• US 8,145,656 B2
• Filed: 02/04/2007
• Issued: 03/27/2012
• Est. Priority Date: 02/07/2006
• Status: Active Grant

• Current Assignee: Flash Networks, Ltd. (Constellation Software Incorporated)
• Original Assignee: Mobixell Networks Incorporated (Constellation Software Incorporated)
• Inventors: Raudnitz, Dan, Cohen, Ran A., Wexler, Yosef, Shatz, Amir
• Primary Examiner(s): Truong, Dennis
• Application Number:
  US12/162,176
• Publication Number:
  US 20090083228A1
• Time in Patent Office: 1,878 Days
• Field of Search: 707999001-999003, 707/707, 707/728, 707/730, 707/736, 707/748, 707/758, 715/741, 386/241, 386/157, 706/15, 382/103, 382/165, 382/181
• US Class Current: 707/758
• CPC Class Codes: G06F 16/634 Query by example, e.g. query by humming
• CPC Class Codes: G06F 16/683 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/71 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/785 using colour or luminescence
• CPC Class Codes: G06V 10/50 by performing operations within image blocks; by using histograms, e.g. histogram of oriented gradients [HoG]; by summing image-intensity values; Projection analysis
• CPC Class Codes: G06V 20/40 in video content extracting overlay text G06V20/62; video retrieval G06F16/70; processing of video elementary streams in video servers H04N21/234; processing of video elementary streams in video clients H04N21/44
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches
• CPC Class Codes: Y10S 707/913 Multimedia

Abstract

A method for matching media objects includes receiving a plurality of reference objects, and computing respective reference feature vectors (104, 106) of one or more of the reference image frames (86, 88) in each of the reference objects. Upon receiving a query object, a respective query feature vector (110) of at least one of the query image frames is computed. The reference feature vectors are searched to find one or more candidate objects among the reference objects, such that a respective reference feature vector of one of the reference image frames in each of the one or more candidate objects matches the query feature vector. At least one additional reference image frame is compared to at least one additional query image frame in order to determine that one of the candidate objects is a match for the query object.

Claims

1. A method for matching media objects, comprising:

receiving a plurality of reference objects, each reference object comprising a respective first sequence of reference image frames;

computing respective reference feature vectors of one or more of the reference image frames in each of the reference objects;

receiving a query object, comprising a second sequence of query image frames;

computing a respective query feature vector of at least one of the query image frames;

searching the reference feature vectors to find one or more candidate objects among the reference objects, using a coarse matching criterion to match a respective reference feature vector of one of the reference image frames in each of the one or more candidate objects to the query feature vector;

comparing at least one additional reference image frame, which follows the one of the reference image frames in each of the one or more candidate objects, to at least one additional query image frame, which follows the at least one of the query image frames in the query object, using a fine matching criterion, different from the coarse matching criterion, in order to determine that one of the candidate objects is a match for the query object; and

outputting a record of the match,

wherein computing the respective reference feature vectors and query feature vector comprises computing multiple feature vectors of at least one frame from among the reference image frames and the query image frames, the multiple feature vectors corresponding to different base characteristics of the query image frames relative to the reference image frames,

wherein the base characteristics are selected from a group of image characteristics consisting of an aspect ratio, image borders, scaling, and shift, and

wherein searching the reference feature vectors comprises identifying, responsively to the base characteristics, a conversion to be applied to one or more of the query and candidate objects in order to satisfy the coarse matching criterion.

2. The method according to claim 1, wherein computing the respective reference and query feature vectors comprises dividing at least one of the reference image frames and the at least one of the query image frames into a predetermined set of blocks, and computing a feature of each of the blocks.

3. The method according to claim 2, wherein the feature comprises an average color value.

4. The method according to claim 1, wherein receiving the query object comprises extracting the query object from a transmission over a communication network.

5. The method according to claim 4, wherein the communication network comprises a telephone network, and wherein the transmission comprises a multimedia message transmitted over the telephone network.

6. The method according to claim 4, wherein the query object comprises an instance of one of the reference objects that has been modified in the transmission over the communication network, and wherein searching the reference feature vectors comprises compensating for modification of the query object so as to identify the one of the reference objects from which the query object is derived.

7. The method according to claim 1, wherein searching the reference feature vectors comprises adjusting at least one of the reference and query feature vectors to compensate for a change in aspect ratio of the query image frames relative to the reference image frames of one of the reference objects from which the query object is derived.

8. The method according to claim 7, wherein the query image frames comprise borders as a result of the change in the aspect ratio, and wherein searching the reference feature vectors comprises removing the borders in order to find the one or more candidate objects.

9. The method according to claim 1, wherein the feature vectors comprise multiple vector elements having respective values, and wherein computing the respective reference feature vectors comprises quantizing the respective values of the vector elements and building a search tree comprising multiple tiers of arrays corresponding respectively to the vector elements of the feature vectors, each array comprising pointers to the arrays in a subsequent tier of the search tree, wherein the pointers are indexed by the respective quantized values of the vector elements, and

wherein searching the reference feature vectors comprises traversing the search tree using the quantized values of the vector elements of the query feature vector as indices, and

wherein traversing the search tree comprises specifying a radius of tolerance, and using additional values of the vector elements that are within the radius of the values of the vector elements of the query feature vector as additional indices to traverse further branches of the search tree.

10. The method according to claim 1, wherein searching the reference feature vectors comprises finding a match between the respective reference feature vector of a first reference image frame and the respective query feature vector of a first query image frame, and wherein applying the fine matching criterion comprises computing and comparing respective query feature vectors of one or more of the query image frames following the first query image frame to the respective reference feature vectors of the one or more of the reference image frames following the first reference image frame.

11. The method according to claim 1, wherein comparing the at least one additional reference image frame comprises aligning the first and second sequences, and comparing the aligned sequences,

wherein aligning the first and second sequences comprises associating each of a plurality of the query image frames with a respective one of the reference image frames, while at least one of the reference image frames in the first sequence has no query image frame associated therewith due to dropping of one or more of the query image frames from the first sequence of the reference image frames of one of the reference objects from which the query object is derived.

12. The method according to claim 11, wherein associating each of the plurality of the query image frames with the respective one of the reference image frames comprises applying dynamic time warping to at least one of the first and second sequences.

13. The method according to claim 1, wherein computing the respective query feature vector comprises identifying one or more constant-color frames from a beginning of the second sequence, and computing the respective query feature vector of at least one of the query image frames following the constant-color frames.

14. The method according to claim 1, wherein comparing the at least one additional reference image frame comprises applying the conversion to one or more of the additional query and reference image frames and then applying the fine matching criterion.

15. The method according to claim 1, wherein using the fine matching criterion comprises:

performing a comparison between the at least one additional query image frame in the second sequence and a corresponding additional reference image frame in the first sequence; and

if the comparison between the at least one additional query image frame and the corresponding additional reference image frame does not yield a match, retrying the comparison between the at least one additional query image frame and one subsequent additional reference image frame, following the corresponding additional reference image frame in the first sequence.

16. Apparatus for matching media objects, comprising:

a memory, which is arranged to store a plurality of reference objects, each reference object comprising a respective first sequence of reference image frames; and

a content tracker, which is configured to compute respective reference feature vectors of one or more of the reference image frames in each of the reference objects, and upon receiving a query object comprising a second sequence of query image frames, to compute a respective query feature vector of at least one of the query image frames, and to search the reference feature vectors to find one or more candidate objects among the reference objects, using a coarse matching criterion to match a respective reference feature vector of one of the reference image frames in each of the one or more candidate objects to the query feature vector, and to compare at least one additional reference image frame, which follows the one of the reference image frames in each of the one or more candidate objects, to at least one additional query image frame, which follows the at least one of the query image frames in the query object, using a fine matching criterion, different from the coarse matching criterion, in order to determine that one of the candidate objects is a match for the query object, and to output a record of the match,

wherein the content tracker is configured to compute multiple feature vectors of at least one frame from among the reference image frames and the query image frames, the multiple feature vectors corresponding to different base characteristics of the query image frames relative to the reference image frames,

wherein the base characteristics are selected from a group of image characteristics consisting of an aspect ratio, image borders, scaling, and shift, and

wherein the content tracker is configured to identify, responsively to the base characteristics, a conversion to be applied to one or more of the query and candidate objects in order to satisfy the coarse matching criterion.

17. A computer software product, comprising a tangible, non-transitory computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to store a plurality of reference objects, each reference object comprising a respective first sequence of reference image frames, to compute respective reference feature vectors of one or more of the reference image frames in each of the reference objects, and upon receiving a query object comprising a second sequence of query image frames, to compute a respective query feature vector of at least one of the query image frames, and to search the reference feature vectors to find one or more candidate objects among the reference objects, using a coarse matching criterion to match a respective reference feature vector of one of the reference image frames in each of the one or more candidate objects to the query feature vector, and to compare at least one additional reference image frame, which follows the one of the reference image frames in each of the one or more candidate objects, to at least one additional query image frame, which follows the at least one of the query image frames in the query object, using a fine matching criterion, different from the coarse matching criterion, in order to determine that one of the candidate objects is a match for the query object, and to output a record of the match,

wherein the instructions cause the computer to compute multiple feature vectors of at least one frame from among the reference image frames and the query image frames, the multiple feature vectors corresponding to different base characteristics of the query image frames relative to the reference image frames,

wherein the base characteristics are selected from a group of image characteristics consisting of an aspect ratio, image borders, scaling, and shift, and

wherein the instructions cause the computer to identify, responsively to the base characteristics, a conversion to be applied to one or more of the query and candidate objects in order to satisfy the coarse matching criterion.

18. A method for matching media objects, comprising:

receiving a plurality of reference objects, each reference object comprising a respective first sequence of reference image frames;

computing respective reference feature vectors of one or more of the reference image frames in each of the reference objects;

receiving a query object, comprising a second sequence of query image frames;

computing a respective query feature vector of at least one of the query image frames;

searching the reference feature vectors to find one or more candidate objects among the reference objects, using a coarse matching criterion to match a respective reference feature vector of one of the reference image frames in each of the one or more candidate objects to the query feature vector;

comparing at least one additional reference image frame, which follows the one of the reference image frames in each of the one or more candidate objects, to at least one additional query image frame, which follows the at least one of the query image frames in the query object, using a fine matching criterion, different from the coarse matching criterion, in order to determine that one of the candidate objects is a match for the query object; and

outputting a record of the match,

wherein using the fine matching criterion comprises;

performing a comparison between the at least one additional query image frame in the second sequence and a corresponding additional reference image frame in the first sequence; and

if the comparison between the at least one additional query image frame and the corresponding additional reference image frame does not yield a match, retrying the comparison between the at least one additional query image frame and one subsequent additional reference image frame, following the corresponding additional reference image frame in the first sequence.