An efficient block segmentation algorithm for true motion estimation

Determining true motion (including identifying occluded and uncovered regions) is vital for applications such as image sequence restoration and motion-compensated frame-rate conversion. Block-based motion estimation provides true motion only in blocks which do not contain motion discontinuities. A strategy for obtaining true motion for an entire image is to initialise the motion field using a block-based technique, to identify blocks where the assumption of constant motion fails (model failure blocks), and to correct the motion field within those blocks. Orchard (1993) provides a framework for correcting the motion field in model failure blocks by segmenting those blocks into two arbitrarily shaped regions each corresponding to a unique motion (obtained from neighbouring blocks). He proposes two hard constraints on any such segmentation: each region must be contiguous, and connected to the neighbouring block whose motion vector it takes. These regions are found by minimising an objective function consisting of a squared error term and a term related to segmentation boundary length. This minimisation must be performed by computationally demanding stochastic minimisation techniques, and in practice the result is not guaranteed to meet the hard segmentation criteria. The technique which we propose permits a less general segmentation, but the segmentation can be performed using an efficient, deterministic algorithm, and we are able to guarantee that the resulting segmentation satisfies Orchard´s hard constraints. We are also, unlike Orchard, able to able to identify uncovered background