Motion segmentation refers to the task of segmenting moving objects subject to their motion in order to dis- tinguish and track them in a video. This is a challenging task in situations where different objects share similar movement patterns, or in cases where one object is occluded by others in part of the scene. In such cases, un- supervised motion segmentation fails and additional information is needed to boost the performance. Based on a formulation of the clustering task as an optimization problem using a multi-labeled Markov Random Field, we develop a semi-supervised motion segmentation algorithm by setting up a framework for incorpo- rating prior knowledge into the segmentation algorithm. Prior knowledge is given in the form of manually la- belling trajectories that belong to the various objects in one or more frames of the video. Clearly, one wishes to limit the amount of manual labelling in order for the algorithm to be as autonomous as possible. Towards that end, we propose a particle matching procedure that extends the prior knowledge by automatically matching particles in frames over which fast motion or occlusion occur. The performance of the proposed method is studied through a variety of experiments on videos involving fast and complicated motion, occlusion and re-appearance, and low quality film. The qualitative and quantitative results confirm reliable performance on the types of applications our method is designed for.