A novel on-line video object segmentation scheme based on illumination-invariant color-texture feature extraction and marker prediction is proposed in this paper. First, the location of the object of interest is initialized based on user-specified markers. Superpixels are generated in the next available frame of the input video to extract the illumination-invariant color-texture features of the object of interest. The proposed object marker prediction scheme consists of estimating the user-specified markers and locating the object of interest in the next available frame via superpixel motion prediction using illumination-invariant optical flow, marker superpixel candidate generation using short-term superpixel affinity, and maximum likelihood computation using long-term superpixel affinity. The experimental results obtained when the proposed method is applied to several challenging video clips demonstrate that the proposed approach is competitive with several other state-of-the-art methods, especially when the illumination and object motion change dramatically.