Efficient and robust algorithm for video sequence matching

• US 20060182368A1
• Filed: 01/21/2005
• Published: 08/17/2006
• Est. Priority Date: 01/21/2005
• Status: Active Grant

• Current Assignee: Seiko Epson Corporation (Seiko Group)
• Original Assignee: Seiko Epson Corporation (Seiko Group)
• Inventors: Kim, Changick
• Granted Patent: US 7,486,827 B2
• Time in Patent Office: Days
• US Class Current: 382/305
• CPC Class Codes: G06F 16/7847 using low-level visual features of the video content
• CPC Class Codes: G06V 20/48 Matching video sequences
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

A two-step matching technique is embodied in a video-copy-detection algorithm that detects copies of video sequences. The two-step matching technique uses ordinal signatures of frame partitions and their differences from partition mean values. The algorithm of this invention is not only robust to intensity/color variations it can also effectively handle various format conversions, thereby providing robustness regardless of the video dynamics of the frame shots.

Claims

1. A method for detecting whether all or a portion of target video data containing a plurality of frames and sub-sequences matches query video data, the method comprising the steps of:

(a) calculating a first distance between the query video data and a specified one of the sub-sequences of the target video data;

(b) determining if the first distance is less than a first threshold;

if so, calculating a second distance between the query video data and the specified sub-sequence of the target video data,

otherwise, assign a relatively large value to the second distance;

(c) repeating steps (a) and (b) for each sub-sequence of the target video data;

(d) finding local minima from among the second distance values; and

(e) performing copy detection based on the local minima found.

2. A method as recited in claim 1, wherein step (e) comprises comparing each local minimum with a second threshold, and determining which, if any, of the local minima is/are less than the second threshold.

3. A method as recited in claim 1, wherein the calculation of the first and second distances in steps (a) and (b) respectively are each based on a 2×

2 partitioning of each of the frames in the query video data and the target video data.

4. A method as recited in claim 1, wherein the detection method is robust to select modifications applied to one or more frames of the target video data, the select modifications including display format conversion, pixel level boost, and histogram equalization.

5. A device-readable medium embodying a program of instructions for directing a device to perform a process of detecting whether all or a portion of target video data containing a plurality of frames and sub-sequences matches query video data, the program of instructions comprising:

(a) instructions for calculating a first distance between the query video data and a specified one of the sub-sequences of the target video data;

(b) instructions for determining if the first distance is less than a first threshold;

(c) instructions for calculating a second distance between the query video data and the specified sub-sequence of the target video data, the calculating instructions being executed if it is determined that the first distance is less than the first threshold;

(d) instructions for assigning a relatively large value to the second distance, the assigning instructions being executed if it is determined that the first distance is not less than the first threshold;

(e) instructions for repeating steps (a), (b) and either (c) or (d) for each sub-sequence of the target video data;

(f) finding local minima from among the second distance values; and

(g) performing copy detection based on the local minima found.

6. A device-readable medium as recited in claim 5, wherein instructions (g) comprises instructions for comparing each local minimum with a second threshold, and determining which, if any, of the local minima is/are less than the second threshold.

7. A device-readable medium as recited in claim 5, wherein the instructions for calculation of the first and second distances indicate that the calculations are each based on a 2×

2 partitioning of each of the frames in the query video data and the target video data.

8. A device-readable medium as recited in claim 5, wherein the detection process specified by the program of instructions is robust to select modifications applied to one or more frames of the target video data, the select modifications including display format conversion, pixel level boost, and histogram equalization.

9. A device configured to detect whether all or a portion of target video data containing a plurality of frames and sub-sequences matches query video data, the device comprising one or more components or modules to:

calculate, for each sub-sequence of the target video data, a first distance between the query video data and that sub-sequence;

determine, for each sub-sequence of the target video data, if the first distance is less than a first threshold, and (i) if so, calculate a second distance between the query video data and that sub-sequence, and (ii) if not, assign a relatively large value to the second distance;

find local minima from among the second distance values; and

perform copy detection based on the local minima found.

10. A device as recited in claim 9, wherein the one or more components or modules comprises one or more hardware components or modules.

11. A device as recited in claim 9, wherein the one or more components or modules comprises one or more software components or modules.