Video object segmentation (VOS) has been a hot research topic in multimedia processing, because it is foundation of other video technologies and has many applications such as video matting, surveillance and video editing. Among them, the actual surveillance usually requires to read the real-time videos. However, many existing VOS algorithms are off-line, and they cannot suit the needs. Therefore, it is valuable to focus the research on the on-line VOS. There are also many branches of VOS: video object segmentation under extreme cases (e.g. extreme occlusion, rapid deformation and illumination changing etc.), video object co-segmentation and video multi object segmentation. In this thesis, we propose an on-line video object segmentation algorithm (OL-VOS) which is robust to illumination changing, an on-line video co-segmentation algorithm (OL-VCS) and an on-line video multi object segmentation algorithm (OL-VMOS). First of all, for the purpose to simplify the computation and extract the initial object contour, we initially segment every frame into a set of superpixels. Among these three algorithms, first, an illumination-invariant color-texture region feature is proposed to segment out the object in the clips with illumination changing; second, a robust OLVCS scheme is presented to segment the common objects from a set of video clips; third, a novel OL-VMOS algorithm based on skeleton model is proposed. Experiments are conducted to evaluate the performance of the proposed algorithms with some state-of-the-art video object segmentation methods. The video object segmentation based on illumination-invariant region feature is proven to be robust against the illumination changing. Experimental results also show that the proposed video object co-segmentation algorithm is able to segment out the common objects iii from videos and efficient in execution time. Finally, we show that the proposed video multi object segmentation is both robust in segmenting multi objects and efficient in execution time.