We present a parallel implementation of a probabilistic algorithm for real time tracking of segments in noisy edge images. Given an initial solution -a set of segments that reasonably describe the input binary edge image-, the algorithm efficiently updates the parameters of these segments to track the movements of objects in the image in successive image frames. The proposed method is based on the EM algorithm -a technique for parameter estimation of statistical distributions in presence of incomplete data-, used here to estimate the parameters of a mixture density. The algorithm is highly susceptible of parallelization, because of the uncoupled nature of the computations needed on its main data structures. This property is exploited in order to make an efficient version for parallel-distributed memory environments, under the message-passing paradigm. We carefully describe the details of the implementation, and finally, we show an evaluation of the algorithm in a NOW (Network of Workstations), using the standard Message Passing Interface (MPI) library. Our evaluation shows that the reached speedup is very close to the ideal optimum.