Map time difference between two similar videos

Question

Question:

Is there any software, source-code, or well documented and easily implementable research (I am not afraid for a little bit of Python) to do the following:

Take two similar videos from different sources (say a video file obtained from a VHS and a video file ripped from a DVD) and map an estimated time difference between the videos (this may not be based on the audio):

video1 : video2   (in seconds)
0.00   : 2.00
1.00   : 3.10
2.00   : 4.20
3.00   : 5.25
4.00   : 6.30
5.00   : 7.33
6.00   : 8.38
7.00   : 9.40
8.00   : 10.50

Possible avenue for implementation:

Convert video to a 1D time signal:

A simple solution might be to create a 1D signal by taking the average of each frame. Each signal from each video can then be splitted up into windows and be correlated to find the phase difference (the mapping between the two).

We might start by marking the same "start" and "finish" of the videos (it would obvious be at the same timestamps as our signals) and apply a transformation to scale video-signal-2 to the same time-size as video-signal-1. We can then proceed with the window matching as described above, find the mapping we are looking for and then apply the inverse of the transformation on the video 2 side of the mapping.

Here are some results. You can clearly see a correlation between the two video's.

Comparison between two similar video signals (frame# as x-axis):

A video frame comparison:

The videos I used for this example is from the series Heidi: girl in the alps. The frame on the left is from a foreign rip, while the frame on the right is from a Afrikaans DVD I bought in South Africa (http://www.takealot.com/afrikaanse-kinder-bundel-met-heidi-pinocchio-en-nils-holgersson/PLID32819763).

Note the extremely poor quality of the Afrikaans DVD.

It does not work yet:

A question regarding this approach is how do we correlate these signals? I tried normal correlation (the fft route), but unfortunately the signal is not zero-mean and therefore it is quite difficult to obtain a correct phase shift.

I also tried high-pass filter this result, but the resulting signal is quite a mess and still does not correlate well.

Edit: (I got it working)

I used a new metric for the frames - I now used the mean of the right half of the frame minus the mean of the left half (now my data are more zero-mean). I normalise my data and use a high pass filter to convert my signal to a zero-mean signal (3rd order Butterworth filter). This is the result

I initiated a mapping as range(length) (a 1:1 mapping) and shifted the mapping according to the global phase shift (from phase correlating the signals).

I then updated the mapping by repeating the following a few times:

1. chose arbitrary sized (which change every iteration) time windows to chop the two signals into $n$ equal parts,
2. used phase correlation to get the phase differences between part $i$ of signal 1 and signal 2 for $i \in 1,2,...,n$ ,
3. added a Gaussian of that length with amplitude as the phase difference to the mapping (at the appropriate interval),

Finally I applied the mapping to the video.

Here is the final fit between the two time-series (each dot represents a frame):

And here is a graph representing the lag (in frames) between the videos:

Why I want this:

My goal is find a mapping between Afrikaans dubbed videos from VHS, against foreign language DVDs/Blurays of the same video. I want to stretch the Afrikaans audio to fit the DVD/bluray's video according to this obtained mapping and then mux the video and audio tracks. As a result I will have superior video quality (compared to the original VHS video) with an Afrikaans audio track.

One of the foreseeable problems would be where some discontinuity is introduces (such as a advertisement in the VHS recording where a direct scene transition would be in the DVD). I will overcome this by filling discontinued audio with blank noise (or maybe a bit of white noise) in the one case or cutting out some audio in the other.

I have done this once with a video by time-distorting the audio manually, but I currently have a whole folder with such similar videos and thought to maybe write some code to do this automatically.

Answer 1

To compute an offset between the two signals in the first image, I think that phase-correlation will give you much better results, than simply the basic correlation.

You can reuse your fft code but have to normalize your fft coefficients to unit magnitude prior to your inverse-fft, so the phase-correlation is based only on phase information and is insensitive to changes in magnitude/intensity.

Answer 2

Naive question: is it very common for the relationship between the two sequences of timestamps (the "warping function") to be something else than a linear function? I assume it'll be almost always linear, in which case you just need to match two points (say the first and the last non-black frame), and then you can interpolate between that.

If you want to do something more robust, for different types of warping functions, you're on the right track by extracting a 1-D signal from the video. I would suggest the following normalization scheme: $x_{norm}(t) =\frac{x(t) - \mu(t)}{\sigma(t)}$ where $\mu(t)$ and $\sigma(t)$ are the mean and standard deviation of the signal in a 5s or 10s long window centered at time $t$ (replace mean and standard deviation by median and interquartile range if your data is too noisy). This works as a high-pass filter and ensures you're comparing two signals with a similar magnitude. You can then find the optimal alignment between the two with Dynamic Time Warping (DTW). If you know that the warping function between the two signals is piecewise linear (time offset and speed difference), you can fit a line through segments of the optimal path found by DTW to get a time offset and a speed ratio for each of these segments.