Motion-based Video Segmentation

1. Static Segmentation

The watershed technique is one of the classics in the field of topography. It regards the gradient magnitude image as a landscape and where the brightness values correspond to the elevation. Areas where a rain drop would drain to the same minimum are denoted as catchment basins, and the lines separating adjacent catchment basins are called dividing lines or watersheds.

In static segmentation, the watershed algorithm of mathematical morphology is a powerful method. Early watershed algorithms are developed to process digital elevation models and are based on local neighborhood operations on square grids. Improved gradient following methods are devised to overcome plateaus and square pixel grids[Gauch, 1999], its basical steps follow as: (1) Identify the local intensity minima, which define the bottoms of watersheds. Here the pre-smoothing filter is needed to eliminate the plateaus in the image. (2) Calculate the image gradient, the 8-neighbors of each point are searched to determine the most steeply uphill and most steeply downhill directions. These directions are encoded and stored in a temporary image. (3) Partititon the input image into watersheds. For each of the remaining points in the image, the gradient information is used to follow the downhill to some intensity minimum. The identifier of this extremum is then recorded in the ouptut pixel corresponding to this starting point. Note that the input image is the gradient image from the partial derivatives of the intensity image.

Other approaches use ``immersion simulations`` to identify watershed segments by flooding the image with water starting at intensity minima [Vincent, 1991]. The operation of their technique can simply be described by figuring that holes are pierced in each local minimum of the topographic relief. At the end, the surface is slowly immersed into a 'lake', by that filling all the catchment basins, starting from the basin that is associated to the global minimum. While two catchment basins tend to merge, a dam is built. The process results in a partitioning of the image in many catchment basins, of which the borders define the watersheds.

A severe drawback to the computation of watershed images is over-segmentation, so here watershed merging is performed based on thresholding the difference of adjacent subregions¡¯intensity mean values.

We have realized the above two watershed algorithms. Details see our publications(pdf): IWISAP'2000 and IMVIP'2000. Below some results are shown.

2. Motion Segmentation

There are two major groups of approaches to separate image sequences into multiple significant scene strutures and objects[Sawhney, 1996]. One group solves the problem by letting multiple models simultaneously compete for the description of the every motion measurements, and in the second group, multiple models are estimated sequentially by solving for a dominant model at each stage. For the former method, its difficulties occur at determination of the number of models or uncertainty of mixture models. The latter one may confront puzzles in the case of absence of dominant motion, and it yet lacks competition amongst the motion models.

Most of methods for motion segmentation operate on a pixel level basis and either do not consider spatial constraints or they result into complex and computationally demanding algorithms[Sawhney, 1996][Wang, 1994]. To improve motion segmentation, recently a number of researchers have attempted to combine an initial segmentation with motion, which take into account the spatial coherence to get more robust result[Weiss, 1996][Patras, 1998].

The sequential dominant motion model-based method used for segmention, compared to the multiple model competition method, is more efficient because it does not need to consider how many objects occur in the scene and looks simpler from its algorithmic form. But it may be confronted with the absence of dominant motion. As well it fails to delineate similar motions to different layers because of the lack of competition amongst the motion models. So, the sequential methods are applied only in some simple application cases, such as single object tracking, image mosaicing for panorama view, camera motion compensation ( for stabilization and registration) or background/ foreground segmentation.

We have put forward our methods on both sequential and competition approaches. Details see our publications(pdf): IWISAP'2000 and IMVIP'2000. Below also some results are given.