Abstract

The content-plot of a video clip is created by positioning sev- eral key frames in two-dimensions and connecting them with lines. It is constructed so that it should be possible to follow the events shown in the video by moving along the lines. Content plots were previously computed by clustering together frames that are contiguous in time. We propose to cluster together frames if they are related by a short chain of simi- larly looking frames even if they are not adjacent on the time-line. The computational problem can be formulated as a graph clustering problem that we solve by extending the classic k-means technique to graphs. This new graph clustering algorithm is the main technical contribution of this paper.