COMP343 Fundamentals of Multimedia Computing

Video Processing
Key Frame Extraction

This page contains various different examples of key frame identification and extraction. The first one generates excellent image summaries of all key frames, in one single summary image (such as house_tour.jpg [69k] and blade_runner.jpg [120k] , note the red line to show the path of time). The approach taken by the second student was the suggested approach - the others have added their own ideas. DR


Program Name:
This program could be running under the Windows envirnment with ActivePerl installed. This program will compare the  frames in the Video and extract the keyframes.

Input File Format: MPEG Format
This Program can handle MPEG Format.

Output File Format: PPM Format & TXT Format
This Program can output the keyframe in key0.ppm, key1.ppm, and so on. A summy of the keyframes "shots.ppm" is also given out. The detail of the keyframes is printed out at a plain text file "'.

How to Use:
The Basic Format is as follow:
In Windows 95/98/NT (With ActivePerl Installed)
    perl <input filename>

<input filename>: the input mpeg video

example: perl energy.mpg

How it works:
The program compare and calcuate the similarity of each video frames to consider whether there is a change in the scenary or not. If they is a change, we break the video here and finally we will break the video into shots. We assume the first frame of each shot as the keyframe and output the keyframe to the users. We follow the basic idea of Color Indexing to compare the similarity of two video frame, we first change the RGB color model to HSV color model. We quantize the HSV color axis for faster calcuation and reduce the weighting of the luminance as following: H: 16 colors, S: 16 colors, V: 8 colors. Then we map the color from 3D into 1D and construct the color histogram by counting the number of time each color present in the video frame. The color histogram is then normalized such that its' total area is equal to one. For each video frame, we construct the color histograms. The similary of two vidoe frame can be calculated by the intersection of the color histogram. If we found that the intersection is larger then 0.7. we consider the two as similar, in another word, there is not scency change. After we go through the hold video, the video can be broken into shots and the keyframe is extrected.

The keyframes are then packed into one summary file calle shots.ppm. In this file, the size of the vidoe frames are determinded by its relative length of the shots, in another word, determined by how important that shot is. let L be the length of the longer shot. For shot which lenght is k, if L > k > 2*L/3, the keyframe is displayed in organial size; if 2*L/3 > k > L/3, the keyframe is displayed in 2/3 of the organial size; if  k > L/3, the keyframe is displayed in 1/3 of the organial size; The keyframe is then line up according to there time of persent such that user can have a gernal idea of the video

The result of the video  house_tour.mpg [1.1M]  is as follow:
- The text file: house_tour.txt
- The summary image: house_tour.jpg [69k]

The result of the video  blade_runner.mpg [1.2M] is as follow:
- The text file: blade_runner.txt
- The summary image: blade_runner.jpg [120k]

The result of the video  energy.mpg [18.5M] is as follow:
- The text file: energy.txt

  • - The summary image: energy.jpg [468k]
    • Name: Ho Ying Fong
    perl <input file>
    input file = the input video used to extract the key frames
    This program extracts the keyframes from the input video and output to a ppm file call keyframe.ppm. The key frames in the output file is placed from top to down, which indicating the time.
    How it works:
    The key frame extraction method based on the similarity between cotiguous frames. The similarity calculated is using the same method of assignment 2. i.e. consider the whole frame similarity. The reference and each video frame  being checked are first divided into 7X7 blocks. Then mean and standard deviation (SD) of each block for each color of RGB is calculated. The similarity index is the square root of the sum of the square of the difference between the mean and SD of each block. A similarity which is bigger than a preset threshold indicates a key frame is found . The threshold is set by looking the similarity value between each pair of contiguous frame. It is assumed that the first frame in the video is also the first key frame.
  • An example derived from a Bjork interview is shown here [26k]
  • Name: Akhlesh Agrawal

    Usage :  perl <inputfilename>

    The program extracts keyframes from the input file.


    I used the similarity program as used in Assignment 2, with a few modifications. I decoded the input file into ppm format. Then for each ppm file i found the similarity value compared to the previous frame and stored this in an array. After doing this, i made a histogram making a count for each similarity value how many times it occurred.
    I traversed the list backwards until i found a similarity value which occurred more than 2 times. ( I chose 2, because by random chance sometimes 2 keyframes have the same similarity value)
    This values was the threshhold similarity value.
    I then generated the keyframe .ppm files -, key1.ppm... and so on


    The results were quite good, as my method i think was quite well thought out. For the kylie.mpg [1.15M] file provided in the Assignment page, my program generated all the keyframes listed except for 1 (fin101.ppm), this was because this frame and the previous frame were in fact quite similar and my program would not distinguish it as a new frame. Also at frame fin89.ppm - there was a sudden change in lights, which led my program to believe it was a new scene. Key Frames were determined to occur:

    • At frame 0
    • At frame 41
    • At frame 79
    • At frame 80
    • At frame 89
    • At frame 105
    • At frame 189
    And here are the key frames extracted from kylie.mpg [1.15M]:
    Name: Pong Chi Chiu

    Interesting automatically generated html page summary of frame similarity here.

    Copyright David Rossiter 2000