Abstract: Traditional video segmentation methods based on depth statistics often fail in case of moving camera or overlap between depth ranges of foreground and background. In this paper we propose a geodesic-based method that is suitable for RGB-D video segmentation. The segmentation process is initialized by motion detection, then for each two consecutive frames, a geodesic spatio-temporal graph is constructed, with seed nodes selected based on image feature detection, temporal links built via feature matching and the 8 spatial neighborhoods of pixels used as spatial links. The segmentation result of previous frame then is propagated to the current frame via geodesic spatio-temporal propagation, which is conducted efficiently by generalized geodesic distance transform. Accumulated errors are eliminated by alternatively launching the process of propagation and motion detection. Experiments demonstrate the robust segmentation results for videos of complex scenes and moving camera.