This work addresses the problem of fast, online segmentationof moving objects in video. We pose this as a discriminative onlinesemi-supervised appearance learning task, where supervising labelsare autonomously generated by a motion segmentation algorithm. Thecomputational complexity of the approach is signicantly reduced byperforming learning and classication on oversegmented image regions(superpixels), rather than per pixel. In addition, we further exploit thesparse trajectories from the motion segmentation to obtain a simplemodel that encodes the spatial properties and location of objects at eachframe. Fusing these complementary cues produces good object segmentationsat very low computational cost. In contrast to previous work,the proposed approach (1) performs segmentation on-the-y (allowingfor applications where data arrives sequentially), (2) has no prior modelof object types or `objectness', and (3) operates at signicantly reducedcomputational cost. The approach and its ability to learn, disambiguateand segment the moving objects in the scene is evaluated on a numberof benchmark video sequences.