A new spatio-temporal segmentation approach for moving object(s) detection and tracking from a video sequence is described. Spatial segmentation is carried out using rough entropy maximization, where we use the quad-tree decomposition, resulting in unequal image granulation which is closer to natural granulation. A three point estimation based on Beta Distribution is formulated for background estimation during temporal segmentation. Reconstruction and tracking of the object in the target frame is performed after combining the two segmentation outputs using its color and shift information. The algorithm is more robust to noise and gradual illumination change, because their presence is less likely to affect both its spatial and temporal segments inside the search window. The proposed methods for spatial and temporal segmentation are seen to be superior to several related methods. The accuracy of reconstruction has been significantly high. © 2012 Elsevier B.V. All rights reserved.