In this work, a novel and unified approach for multi-view video (MVV) object segmentation is presented. In the first stage, a region-based graph-theoretic color segmentation algorithm is proposed, in which the popular Normalized Cuts segmentation method is improved with some modifications on its graph structure. Segmentation is obtained by recursive bi-partitioning of a weighted graph of an initial over-segmentation mask. The available segmentation mask is also utilized during dense depth map estimation step, based on a novel modified plane- and angle-sweeping strategy for each of these regions. Dense depth estimation is achieved by region-wise planarity assumption for the whole scene, in which depth models are estimated for sub-regions. Finally, the multi-view image segmentation algorithm is extended to object segmentation in MVV by the additional optical flow information. The required motion field is obtained via region-based matching that has consistent parameterization with color segmentation and dense depth map estimation algorithms. Experimental results indicate that proposed approach segments semantically meaningful objects in MVV with high precision.