MATCHING OF MODIFIED VISUAL AND AUDIO MEDIA

• US 20090083228A1
• Filed: 02/04/2007
• Published: 03/26/2009
• 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: Cohen, Ran A., Wexler, Yosef, Shatz, Amir, Raudnitz, Dan
• Granted Patent: US 8,145,656 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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, 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;

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, in order to determine that one of the candidate objects is a match for the query object; and

outputting a record of the match.

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.

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

13. The method according to claim 11, 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.

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

17. 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 comparing the at least one additional reference image frame 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.

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

20. The method according to claim 18, 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.

7-10. -10. (canceled)

12. (canceled)

14. (canceled)

16. (canceled)

19. (canceled)

21-23. -23. (canceled)

24. A method for matching media objects, comprising:

receiving a plurality of reference objects, comprising respective reference audio segments;

computing respective reference feature vectors of the reference audio segments that are indicative of first spectral distributions of energy in the reference audio segment over a first sequence of time-domain windows, each comprising no more than 512 audio samples, by applying a frequency transform to each of the time-domain windows;

receiving a query object, comprising a query audio segment;

computing a query feature vector that is indicative of a second spectral distribution of the energy in the query audio segment by applying the frequency transform to a second sequence of the time-domain windows;

searching the reference feature vectors to find one of the reference objects having a respective reference feature vector that matches the query feature vector; and

outputting a record indicating that the one of the reference objects matched the query object.

27. The method according to claim 24, wherein the query object comprises an instance of one of the reference objects that has been modified in transmission over a 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.

29. The method according to claim 24, wherein each of the time-domain windows comprises 128 samples, and wherein the time-domain windows in each of the sequences are mutually overlapping, with a separation of 64 samples between successive windows.

30. The method according to claim 24, wherein computing the spectral distributions comprises computing a respective moving average of the energy in each of a plurality of frequency bands over successive sequences of the windows.

25-26. -26. (canceled)

28. (canceled)

31-36. -36. (canceled)

37. 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, 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, 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 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.

38-59. -59. (canceled)

60. Apparatus for matching media objects, comprising:

a memory, which is arranged to store a plurality of reference objects, comprising respective reference audio segments; and

a content tracker, which is configured to compute respective reference feature vectors of the reference audio segments that are indicative of first spectral distributions of energy in the reference audio segment over a first sequence of time-domain windows, each comprising no more than 512 audio samples, by applying a frequency transform to each of the time-domain windows, and upon receiving a query object comprising a query audio segment, to compute a query feature vector that is indicative of a second spectral distribution of the energy in the query audio segment by applying the frequency transform to a second sequence of the time-domain windows, and to search the reference feature vectors to find one of the reference objects having a respective reference feature vector that matches the query feature vector, and to output a record indicating that the one of the reference objects matched the query object.

61-72. -72. (canceled)

73. A computer software product, comprising a 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, 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, 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 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.

74-95. -95. (canceled)

96. A computer software product, comprising a 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, comprising respective reference audio segments, and to compute respective reference feature vectors of the reference audio segments that are indicative of first spectral distributions of energy in the reference audio segment over a first sequence of time-domain windows, each comprising no more than 512 audio samples, by applying a frequency transform to each of the time-domain windows, and upon receiving a query object comprising a query audio segment, to compute a query feature vector that is indicative of a second spectral distribution of the energy in the query audio segment by applying the frequency transform to a second sequence of the time-domain windows, and to search the reference feature vectors to find one of the reference objects having a respective reference feature vector that matches the query feature vector, and to output a record indicating that the one of the reference objects matched the query object.

97-108. -108. (canceled)