Determine consecutive video clips

I a long video stream, but unfortunately, it's in the form of 1000 15-second long randomly-named clips. I'd like to reconstruct the original video based on some measure of "similarity" of two such 15s clips, something answer开发者_高级运维ing the question of "the activity in clip 2 seems like an extension of clip 1". There are small gaps between clips --- a few hundred milliseconds or so each. I can also manually fix up the results if they're sufficiently good, so results needn't be perfect.

A very simplistic approach can be:

(a) Create an automated process to extract the first and last frame of each video-clip in a known image format (e.g. JPG) and name them according to video-clip names, e.g. if you have the video clips:

clipA.avi, clipB.avi, clipC.avi

you may create the following frame-images:

clipA_first.jpg, clipA_last.jpg, clipB_first.jpg, clipB_last.jpg, clipC_first.jpg, clipC_last.jpg

(b) The sorting "algorithm":

1. Create a 'Clips' list of Clip-Records containing each:

(a) clip-name (string)
(b) prev-clip-name (string)
(c) prev-clip-diff (float)
(d) next-clip-name (string)
(e) next-clip-diff (float)

2. Apply the following processing:

for Each ClipX having ClipX.next-clip-name == "" do:
{
    ClipX.next-clip-diff = <a big enough number>;
    for Each ClipY having ClipY.prev-clip-name == "" do:
    {
       float ImageDif =  ImageDif(ClipX.last-frame.jpg, ClipY.first_frame.jpg);
       if (ImageDif < ClipX.next-clip-diff)
       {
           ClipX.next-clip-name = ClipY.clip-name;
           ClipX.next-clip-diff = ImageDif;
       }
    }
    Clips[ClipX.next-clip-name].prev-clip-name = ClipX.clip-name;
    Clips[ClipX.next-clip-name].prev-clip-diff = ClipX.next-clip-diff;
}

3. Scan the Clips list to find the record(s) with no <prev-clip-name> or 
   (if all records have a <prev-clip-name> find the record with the max <prev-clip-dif>.
   This is a good candidate(s) to be the first clip in sequence.

4. Begin from the clip(s) found in step (3) and rename the clip-files by adding 
   a 5 digits number (00001, 00002, etc) at the beginning of its filename and going 
   from aClip to aClip.next-clip-name and removing the clip from the list.

5. Repeat steps 3,4 until there are no clips in the list.

6. Voila! You have your sorted clips list in the form of sorted video filenames! 
   ...or you may end up with more than one sorted lists (if you have enough 
   'time-gap' between your video clips).

Very simplistic... but I think it can be effective...

PS1: Regarding the ImageDif() function: You can create a new DifImage, which is the difference of Images ClipX.last-frame.jpg, ClipY.first_frame.jpg and then then sum all pixels of DifImage to a single floating point ImageDif value. You can also optimize the process to abort the difference (or sum process) if your sum is bigger than some limit: You are actually interested in small differences. A ImageDif value which is larger than an (experimental) limit, means that the 2 images differs so much that the 2 clips cannot be one next each other.

PS2: The sorting algorithm order of complexity must be approximately O(n*log(n)), therefore for 1000 video clips it will perform about 3000 image comparisons (or a little more if you optimize the algorithm and you allow it to not find a match for some clips)