Method and apparatus for comparing videos
View Patent ↗A method for comparing a query video and a target video includes partitioning frames of the query video and frames of the target video into blocks and calculating the mean intensity value for each block. A plurality of query time series is produced for the query video, each query time series representing temporal variation in mean intensity value for blocks from the same location in different frames of the query video. A plurality of target time series is produced for the target video, each target time series representing temporal variation in mean intensity value for blocks from the same location in different frames of the target video the query time series and the target time series are used in determining if alignment exists between the query video and the target video.
1. A method for comparing a query video and a target video, the method including:
partitioning frames of the query video and frames of the target video into blocks;
calculating the mean intensity values for the blocks;
producing a plurality of query time series for the query video, the query time series representing temporal variation in mean intensity value for blocks from the same location in different frames of the query video;
producing a plurality of target time series for the target video, the target time series representing temporal variation in mean intensity value for blocks from the same location in different frames of the target video;
determining if alignment exists between the query video and the target video using the query time series and the target time series;
segmenting the query time series and the target time series into a respective set of discrete linear segments; and
performing local sequence alignment of those linear segments.
2. The method as claimed in claim 1 , further including selecting major inclines and major declines from the segmented time series and using the major inclines and major declines in performing alignment.
3. The method as claimed in claim 2 wherein the selected major inclines and the major declines exclude jump inclines and jump declines.
4. The method as claimed in claim 1 , further including comparing major inclines and declines of the query video with major inclines and major declines of the target video to obtain approximate alignments with consecutive matched inclines and declines.
5. The method as claimed in claim 4 , further including matching a query video sequence of major inclines/major declines against a target video sequence of major inclines/major declines.
6. The method as claimed in claim 5 , wherein the matching is carried out by creating a matrix having cells with the query video sequence of major inclines/major declines plotted against a target video sequence of major inclines/major declines and, where a match exists, adding a marker in an appropriate cell of the matrix.
7. The method as claimed in claim 6 , wherein after aligning major inclines/major declines, the method further includes extending the major inclines/major declines to neighbour non-major inclines/non-major declines.
8. The method as claimed in claim 7 , further including identifying diagonal lines of consecutive cells having markers and retaining those diagonal lines having a length that is greater than a given threshold for additional alignment processing.
9. The method as claimed in claim 8 , further including selecting the K longest diagonal lines and attempting to join closely located segments included in the top K diagonal lines to form a longer segment.
10. The method as claimed in claim 9 , further including awarding reward scores to diagonal matched lines and penalty scores to gaps in longer lines and, when the combined score of a linked approximate alignment exceeds a given score threshold, checking if previously ignored initial short aligned segments around the linked segments can be joined to form an approximate alignment, and selecting the local approximate alignments having final scores exceeding a final score threshold for further examination.
11. The method as claimed in claim 2 , further including obtaining an approximate alignment of segments to select a set of possible successful alignments and then applying a Smith-Waterman algorithm to the selected set.
12. The method as claimed in claim 11 , further including performing alignment at level for approximate aligned segments not included in the selected set.
13. The method as claimed in claim 1 , further including storing the query video in a video database holding the target video when the query video is determined not to be a duplicate of the target video.
14. A device comprising:
a processor; and
memory storing instructions that, when executed, cause the device to perform a method of:
partitioning frames of the query video and frames of the target video into blocks;
calculating the mean intensity values for the blocks;
producing a plurality of query time series for the query video, the query time series representing temporal variation in mean intensity value for blocks from the same location in different frames of the query video;
producing a plurality of target time series for the target video, the target time series representing temporal variation in mean intensity value for blocks from the same location in different frames of the target video;
determining if alignment exists between the query video and the target video using the query time series and the target time series;
segmenting the query time series and the target time series into a respective set of discrete linear segments; and
performing local sequence alignment of those linear segments.
15. The device as claimed in claim 14 , wherein the method further includes selecting major inclines and major declines from the segmented time series and using the major inclines and major declines in performing alignment.
16. The device as claimed in claim 15 , wherein the selected major inclines and the major declines exclude jump segments.
17. The device as claimed in claim 14 , wherein the method further includes comparing major inclines and declines of the query video with major inclines and major declines of the target video to obtain approximate alignments with consecutive matched inclines and declines.
18. The device as claimed in claim 17 , wherein the method further includes matching a query video sequence of major inclines/major declines against a target video sequence of major inclines/major declines.
19. The device as claimed in claim 18 , wherein the method further includes matching by creating a matrix having cells with the query video sequence of major inclines/major declines plotted against a target video sequence of major inclines/major declines and, where a match exists, adding a marker in an appropriate cell of the matrix.
20. The device as claimed in claim 19 , wherein the method further includes extending the major inclines/major declines to neighbour non-major inclines/non-major declines after aligning major inclines/major declines.
21. The device as claimed in claim 20 , wherein the method further includes identify diagonal lines of consecutive cells having markers and retaining those diagonal lines having a length that is greater than a given threshold for additional alignment processing.
22. The device as claimed in claim 21 , wherein the method further includes select the K longest diagonal lines and attempt to join closely located segments included in the top K diagonal lines to form a longer segment.
23. The device as claimed in claim 22 , wherein the method further includes awarding reward scores to diagonal matched lines and penalty scores to gaps in longer lines and, when the combined score of a linked approximate alignment exceeds a given score threshold, checking if previously ignored initial short aligned segments around the linked segments can be joined to form an approximate alignment, and selecting the local approximate alignments having final scores exceeding a final score threshold for further examination.
24. The device as claimed in claim 14 , wherein the method further includes obtaining an approximate alignment of segments selecting a set of possible successful alignments and then applying a Smith-Waterman algorithm to the selected set.
25. The device as claimed in claim 24 , wherein the method further includes performing alignment at frame level for approximate aligned segments not included in the selected set.
26. The device as claimed in claim 14 , wherein the method further includes the query video in a video database holding the target video when the query video is determined not to be a duplicate of the target video.
27. A non-transitory computer-readable medium storing instructions that, when executed by a computer, cause the computer to:
partition frames of the query video and frames of the target video into blocks;
calculate the mean intensity values for the blocks;
produce a plurality of query time series for the query video, the query time series representing temporal variation in mean intensity value for blocks from the same location in different frames of the query video;
produce a plurality of target time series for the target video, the target time series representing temporal variation in mean intensity value for blocks from the same location in different frames of the target video;
determine if alignment exists between the query video and the target video using the query time series and the target time series;
segment the query time series and the target time series into a respective set of discrete linear segments; and
perform local sequence alignment of those linear segments.