Abstract: Video segmentation is an important preprocessing step for many computer vision and graphics tasks. Its main goal is to group the voxels in the video volume with similar appearance and motion into spatio-temporally consistent supervoxels. In this paper, we formulate video segmentation as an L0 gradient minimization problem, so that the spatio-temporal coherence can be effectively enforced through a gradient sparsity pursuit way. In our method, the appearance and motion descriptor space is first built for over-segmented image patches of each video frame. Then the L0 gradient minimization is performed in the descriptor space, for both spatial and temporal dimensions. To solve the non-convex L0 norm minimization problem, we extend the fused coordinate descent algorithm from 2D image grids to 3D video volume. We conduct quantitative evaluation of our method in a public video segmentation benchmark LIBSVX. The experimental results demonstrate our superior performance to state-of-the-arts in segmentation accuracy and undersegmentation error, and comparable performance in boundary recall and explained variation.