In turning raw or processed video into useful components for a multimedia project, you will often need to segment the video into coherent chunks. One common method of extracting chunks is based on the identification of cuts between shots. Typically, when the author of a video program chooses to change the camera used or angle, it is a reasonable place to segment the video. Unfortunately, cut detection is a nontrivial task as a number of cinematic techniques are used for switching between shots, including dissolves, fades, and wipes.
In this exercise, you will implement a generic cut detection algorithm and experiment with a number of variations on that algorithm.
Before beginning this exercise, you should spend some time watching common categories of television show, including news and drama. Make a list of the types of transitions you observe and the differences between shots before and after transitions. If you have time, develop a short film that includes cuts that you think will be difficult to detect.
While there are many algorithms for cut detection, most algorithms rely on comparisons of successive frames in the image. In a generic imperative language, we might phrase the algorithm for detecting the cuts in a film as
cuts(film f)
for i = 1 to the number of frames in the film
if difference(frame i of f, frame i+1 of f) > cutoff
report a cut between frame i and i + 1
The success of this cut detection algorithm depends on the algorithm used for comparing two frames and the cutoff value selected. For example, a comparison algorithm that compares individual pixels in the two frames is likely to be confused by pans. A low cutoff tends to mistakenly report cuts when there are none. A high cutoff tends to miss cuts.
Implement a cut detection algorithm that takes the difference function
and cutoff as parameters and test it on your own video clips as well as
the sample video clips supplied
in the Cut Detection folder. We have supplied a number
of comparison routines in that folder, including
comparePixelColors: a pixel-by-pixel comparison, based
on the colors of individual pixels.
comparePixelIntensity: a pixel-by-pixel comparison, based
on the intensity of individual pixels.
compareColorHistogram: a comparison based on the
histogram of colors (the amount of each color that appears in the
scene, independent of where that color appears)
compareIntensityHistogram: a similar comparison, based
on pixel intensities.
The films for the exercise are:
walking: a film of a man walking across the room
panorama: a film of campus, with the camera rotating in
a 360 degree arc.
jump-cuts: a sequence of short scenes with jump cuts
dissolves: the same sequence of short scenes with
dissolves between the scenes
pans: the same sequence of short scenes with
pans between the scenes
There are a number of additional tasks you might perform to further your understanding of this problem or to improve your algorithm. In particular, you might add a history component to the algorithm, develop your own comparison routines, or analyze the variants to determine the types of video clips for which the methods are likely to succeed or fail.
It may be possible to improve this algorithm by looking at longer-term changes to the scene. For example, in a pan shot, there will be a small difference between the histograms of successive scenes. Rather than stopping when this difference gets too big, you might base your notion of "too big" on the previous values. If there tends to be a ten point difference between successive frames, then a difference of fifteen points is not likely to be a cut. However, if there tends to be a one point difference between successive frames, then a difference of fifteen points is likely to be a cut.
Implement an algorithm that takes the history of changes into account.
In a functional language, you may want to use a series of calls to
map or insert, the first to determine the
differences between successive frames, the next to determine the differences
between those differences.
It may be possible to improve the core algorithm by coming up with better comparison algorithms. Try developing your own comparison algorithm, using the image manipulation primitives we've discussed in previous classes. If you can't come up with your own algorithm, try combinations of the other algorithms.