Hierarchical Video Segmentation using Morse-Smale Complexes
Steve Gu, Ying Zheng and Carlo Tomasi
In this paper, we regard a space-time block of video data as a piecewise-linear 3-manifold, and we interpret video segmentation as the computation of the Morse-Smale complex for the block. In the generic case, this complex is a decomposition of space-time data into 3-dimensional cells shaped like crystals, and separated by quadrangular faces. The vertices of these are Morse critical points. In practice, video data is discrete, and we devise an algorithm that adapts Morse theory to this reality. The resulting cell decomposition provides an efficient representation of the space-time data, and separates topology from geometry. Critical points paired by the edges of the complex identify topological features and their importance. We use topological persistence over the Morse-Smale complex to build a video segmentation hierarchy through successive simplification. This hierarchy provides a new, promising handle for visual saliency, useful for video summarization, simplification, and recognition. We present an O(n log n), practically efficient algorithm to construct the Morse-Smale complex, and show results on real video.