Segmentation and motion estimation are two problems that require accurate estimation for many applications in computer vision and image analysis. This work presents a solution to these two problems simultaneously. Both the segmentation and motion fields are integrated and estimated in parallel to reduce computation time. The presented algorithm is based on producing motion estimates and restored pixel intensity values through an optimization process that uses deterministic mean-field annealing (MFA) framework. The MFA results at different temperature values are used to run a segmentation process using the concept of region-growing-based algorithm. The segmentation process starts at high temperatures and continues in parallel to the annealing process to refine the segmentation process at lower temperatures. The algorithm results are good and dependent on the annealing parameters. Several experimental results from synthetic and real-world sequences are presented.