We address the problem of annotating a video sequence with partial supervision. Given the pixel-wise annotations in the first frame, we aim to propagate these labels ideally throughout the whole video. While some labels can be propagated using optical flow, disocclusion and unreliable flow in some areas require additional cues. To this end, we propose to train localized classifiers on the annotated frame. In contrast to a global classifier, localized classifiers allow to distinguish colors that appear in both the foreground and the background but at very different locations. We design a multi-scale hierarchy of localized random forests, which collectively takes a decision. Cues from optical flow and the classifier are combined in a variational framework. The approach can deal with multiple objects in a video. We present qualitative and quantitative results on the Berkeley Motion Segmentation Dataset.