A Survey of Spatio-Temporal Grouping Techniques
---
paper_title: Video segmentation based on multiple features for interactive and automatic multimedia applications

paper_content:

In this thesis, a novel method for the segmentation of video sequences based on the analysis of multiple image features is presented. A key feature of the system is the distinction between two levels of segmentation, namely region and object segmentation. Regions are homogeneous areas of the images, which are extracted automatically by the computer. Semantically meaningful objects are obtained by grouping regions, automatically or through user interaction, according to the specific application. This splitting relieves the computer of ill-posed semantic problems, and allows a higher level of flexibility in the use of the results. The extraction of the regions is based the multidimensional analysis of several image features by a spatially constrained Fuzzy C-Means algorithm. The relative weighting of the different features is achieved by means of an adaptive system that takes into account the local level of reliability of each feature. The temporal tracking of the obtained regions is performed by means of a dual strategy in which the motion-compensated projection of the segmentation mask from previous frames is used to influence the segmentation of the current frame so as to achieve higher temporal coherence and stability.
---
paper_title: Motion Segmentation by Subspace Separation: Model Selection and Reliability Evaluation

paper_content:

Reformulating the Costeira–Kanade algorithm as a pure mathematical theorem, we present a robust segmentation procedure, which we call subspace separation, by incorporating model selection using the geometric AIC. We then study the problem of estimating the number of independent motions using model selection. Finally, we present criteria for evaluating the reliability of individual segmentation results. Again, model selection plays an important role. We confirm the effectiveness of our method by experiments using synthetic and real images.
---
paper_title: A probabilistic framework for spatio-temporal video representation and indexing

paper_content:

In this work we describe a novel statistical video representation and modeling scheme. Video representation schemes are needed to enable segmenting a video stream into meaningful video-objects, useful for later indexing and retrieval applications. In the proposed methodology, unsupervised clustering via Guassian mixture modeling extracts coherent space-time regions in feature space, and corresponding coherent segments (video-regions) in the video content. A key feature of the system is the analysis of video input as a single entity as opposed to a sequence of separate frames. Space and time are treated uniformly. The extracted space-time regions allow for the detection and recognition of video events. Results of segmenting video content into static vs. dynamic video regions and video content editing are presented.
---
paper_title: Unsupervised video segmentation based on watersheds and temporal tracking

paper_content:

This paper presents a technique for unsupervised video segmentation. This technique consists of two phases: initial segmentation and temporal tracking, similar to a number of existing techniques. However, new algorithms for spatial segmentation, marker extraction, and modified watershed transformation are proposed for the present technique. The new algorithms make this technique differ from existing techniques by the following features: (1) it can effectively track fast moving objects, (2) it can detect the appearance of new objects as well as the disappearance of existing objects, and (3) it is computationally efficient because of the use of watershed transformations and a fast motion estimation algorithm. Simulation results demonstrate that the proposed technique can efficiently segment video sequences with fast moving, newly appearing, or disappearing objects in the scene.
---
paper_title: Concerning Bayesian Motion Segmentation, Model Averaging, Matching and the Trifocal Tensor

paper_content:

Motion segmentation involves identifying regions of the image that correspond to independently moving objects. The number of independently moving objects, and type of motion model for each of the objects is unknown a priori.
---
paper_title: Efficient spatiotemporal grouping using the Nystrom method

paper_content:

Spectral graph theoretic methods have recently shown great promise for the problem of image segmentation, but due to the computational demands, applications of such methods to spatiotemporal data have been slow to appear For even a short video sequence, the set of all pairwise voxel similarities is a huge quantity of data: one second of a 256/spl times/384 sequence captured at 30 Hz entails on the order of 10/sup 13/ pairwise similarities. The contribution of this paper is a method that substantially reduces the computational requirements of grouping algorithms based on spectral partitioning, making it feasible to apply them to very large spatiotemporal grouping problems. Our approach is based on a technique for the numerical solution of eigenfunction problems known as the Nystrom method This method allows extrapolation of the complete grouping solution using only a small number of "typical" samples. In doing so, we successfully exploit the fact that there are far fewer coherent groups in an image sequence than pixels.
---
paper_title: A Compact and Retrieval-Oriented Video Representation Using Mosaics

paper_content:

Compact yet intuitive representations of digital videos are required to combine high quality storage with interactive video indexing and retrieval capabilities. The advent of video mosaicing has provided a natural way to obtain content-based video representations which are both retrieval-oriented and compression-efficient. In this paper, an algorithm for extracting a robust mosaic representation of video content from sparse interest image points is described. The representation, which is obtained via visual motion clustering and segmentation, features the geometric and kinematic description of all salient objects in the scene, being thus well suited for video browsing, indexing and retrieval by visual content. Results of experiments on several TV sequences provide an insight into the main characteristics of the approach.
---
paper_title: Unsupervised Segmentation of Color-Texture Regions in Images and Video

paper_content:

A method for unsupervised segmentation of color-texture regions in images and video is presented. This method, which we refer to as JSEG, consists of two independent steps: color quantization and spatial segmentation. In the first step, colors in the image are quantized to several representative classes that can be used to differentiate regions in the image. The image pixels are then replaced by their corresponding color class labels, thus forming a class-map of the image. The focus of this work is on spatial segmentation, where a criterion for "good" segmentation using the class-map is proposed. Applying the criterion to local windows in the class-map results in the "J-image," in which high and low values correspond to possible boundaries and interiors of color-texture regions. A region growing method is then used to segment the image based on the multiscale J-images. A similar approach is applied to video sequences. An additional region tracking scheme is embedded into the region growing process to achieve consistent segmentation and tracking results, even for scenes with nonrigid object motion. Experiments show the robustness of the JSEG algorithm on real images and video.
---
paper_title: Segmentation using eigenvectors: a unifying view

paper_content:

Automatic grouping and segmentation of images remains a challenging problem in computer vision. Recently, a number of authors have demonstrated good performance on this task using methods that are based on eigenvectors of the affinity matrix. These approaches are extremely attractive in that they are based on simple eigendecomposition algorithms whose stability is well understood. Nevertheless, the use of eigendecompositions in the context of segmentation is far from well understood. In this paper we give a unified treatment of these algorithms, and show the close connections between them while highlighting their distinguishing features. We then prove results on eigenvectors of block matrices that allow us to analyze the performance of these algorithms in simple grouping settings. Finally, we use our analysis to motivate a variation on the existing methods that combines aspects from different eigenvector segmentation algorithms. We illustrate our analysis with results on real and synthetic images.
---
paper_title: A region-level motion-based graph representation and labeling for tracking a spatial image partition

paper_content:

Abstract This paper addresses two image sequence analysis issues under a common framework. These tasks are, first, motion-based segmentation and second, updating and tracking over time of a spatial partition of an image. By spatial partition, we mean that constituent regions display an intensity, color or texture-based homogeneity criterion. Several issues in dynamic scene analysis or in image sequence coding can motivate this kind of development. A general-purpose methodology involving a region-level motion-based graph representation of the partition is presented. This graph is built from the topology of the spatial segmentation map. A statistical motion-based labeling of its nodes is carried out and formalized within a Markovian approach. Groups of spatial regions with consistent motion are identified using this labeling framework, leading to a motion-based segmentation that is both useful in itself and for propagating the spatial partition over time. Results on synthetic and real-world image sequences are shown, and provide a validation of the proposed approach.
---
paper_title: A subspace approach to layer extraction

paper_content:

Representing images with layers has many important applications, such as video compression, motion analysis, and 3D scene analysis. This paper presents an approach to reliably extracting layers from images by taking advantages of the fact that homographies induced by planar patches in the scene form a low dimensional linear subspace. Layers in the input images will be mapped in the subspace, where it is proven that they form well-defined clusters and can be reliably identified by a simple mean-shift based clustering algorithm. Global optimality is achieved since all valid regions are simultaneously taken into account, and noise can be effectively reduced by enforcing the subspace constraint. Good layer descriptions are shown to be extracted in the experimental results.
---
paper_title: Computing occluding and transparent motions

paper_content:

Computing the motions of several moving objects in image sequences involves simultaneous motion analysis and segmentation. This task can become complicated when image motion changes significantly between frames, as with camera vibrations. Such vibrations make tracking in longer sequences harder, as temporal motion constancy cannot be assumed. The problem becomes even more difficult in the case of transparent motions.
---
paper_title: Spatiotemporal Segmentation Based on Region Merging

paper_content:

This paper proposes a technique for spatio-temporal segmentation to identify the objects present in the scene represented in a video sequence. This technique processes two consecutive frames at a time. A region-merging approach is used to identify the objects in the scene. Starting from an oversegmentation of the current frame, the objects are formed by iteratively merging regions together. Regions are merged based on their mutual spatio-temporal similarity. We propose a modified Kolmogorov-Smirnov test for estimating the temporal similarity. The region-merging process is based on a weighted, directed graph. Two complementary graph-based clustering rules are proposed, namely, the strong rule and the weak rule. These rules take advantage of the natural structures present in the graph. Experimental results on different types of scenes demonstrate the ability of the proposed technique to automatically partition the scene into its constituent objects.
---
paper_title: Unsupervised video segmentation based on watersheds and temporal tracking

paper_content:

This paper presents a technique for unsupervised video segmentation. This technique consists of two phases: initial segmentation and temporal tracking, similar to a number of existing techniques. However, new algorithms for spatial segmentation, marker extraction, and modified watershed transformation are proposed for the present technique. The new algorithms make this technique differ from existing techniques by the following features: (1) it can effectively track fast moving objects, (2) it can detect the appearance of new objects as well as the disappearance of existing objects, and (3) it is computationally efficient because of the use of watershed transformations and a fast motion estimation algorithm. Simulation results demonstrate that the proposed technique can efficiently segment video sequences with fast moving, newly appearing, or disappearing objects in the scene.
---
paper_title: Learning flexible sprites in video layers

paper_content:

We propose a technique for automatically learning layers of "flexible sprites" (probabilistic 2-dimensional appearance maps and masks of moving, occluding objects). The model explains each input image as a layered composition of flexible sprites. A variational expectation maximization algorithm is used to learn a mixture of sprites from a video sequence. For each input image, probabilistic inference is used to infer the sprite class, translation, mask values and pixel intensities (including obstructed pixels) in each layer. Exact inference is intractable, but we show how a variational inference technique can be used to process 320/spl times/240 images at 1 frame/second. The only inputs to the learning algorithm are the video sequence, the number of layers and the number of flexible sprites. We give results on several tasks, including summarizing a video sequence with sprites, point-and-click video stabilization, and point-and-click object removal.
---
paper_title: A region-level motion-based graph representation and labeling for tracking a spatial image partition

paper_content:

Abstract This paper addresses two image sequence analysis issues under a common framework. These tasks are, first, motion-based segmentation and second, updating and tracking over time of a spatial partition of an image. By spatial partition, we mean that constituent regions display an intensity, color or texture-based homogeneity criterion. Several issues in dynamic scene analysis or in image sequence coding can motivate this kind of development. A general-purpose methodology involving a region-level motion-based graph representation of the partition is presented. This graph is built from the topology of the spatial segmentation map. A statistical motion-based labeling of its nodes is carried out and formalized within a Markovian approach. Groups of spatial regions with consistent motion are identified using this labeling framework, leading to a motion-based segmentation that is both useful in itself and for propagating the spatial partition over time. Results on synthetic and real-world image sequences are shown, and provide a validation of the proposed approach.
---
paper_title: A subspace approach to layer extraction

paper_content:

Representing images with layers has many important applications, such as video compression, motion analysis, and 3D scene analysis. This paper presents an approach to reliably extracting layers from images by taking advantages of the fact that homographies induced by planar patches in the scene form a low dimensional linear subspace. Layers in the input images will be mapped in the subspace, where it is proven that they form well-defined clusters and can be reliably identified by a simple mean-shift based clustering algorithm. Global optimality is achieved since all valid regions are simultaneously taken into account, and noise can be effectively reduced by enforcing the subspace constraint. Good layer descriptions are shown to be extracted in the experimental results.
---
paper_title: Computing occluding and transparent motions

paper_content:

Computing the motions of several moving objects in image sequences involves simultaneous motion analysis and segmentation. This task can become complicated when image motion changes significantly between frames, as with camera vibrations. Such vibrations make tracking in longer sequences harder, as temporal motion constancy cannot be assumed. The problem becomes even more difficult in the case of transparent motions.
---
paper_title: Spatiotemporal Segmentation Based on Region Merging

paper_content:

This paper proposes a technique for spatio-temporal segmentation to identify the objects present in the scene represented in a video sequence. This technique processes two consecutive frames at a time. A region-merging approach is used to identify the objects in the scene. Starting from an oversegmentation of the current frame, the objects are formed by iteratively merging regions together. Regions are merged based on their mutual spatio-temporal similarity. We propose a modified Kolmogorov-Smirnov test for estimating the temporal similarity. The region-merging process is based on a weighted, directed graph. Two complementary graph-based clustering rules are proposed, namely, the strong rule and the weak rule. These rules take advantage of the natural structures present in the graph. Experimental results on different types of scenes demonstrate the ability of the proposed technique to automatically partition the scene into its constituent objects.
---
paper_title: Smoothness in layers: Motion segmentation using nonparametric mixture estimation

paper_content:

Grouping based on common motion, or "common fate" provides a powerful cue for segmenting image sequences. Recently a number of algorithms have been developed that successfully perform motion segmentation by assuming that the motion of each group can be described by a low dimensional parametric model (e.g. affine). Typically the assumption is that motion segments correspond to planar patches in 3D undergoing rigid motion. Here we develop an alternative approach, where the motion of each group is described by a smooth dense flow field and the stability of the estimation is ensured by means of a prior distribution on the class of flow fields. We present a variant of the EM algorithm that can segment image sequences by fitting multiple smooth flow fields to the spatiotemporal data. Using the method of Green's functions, we show how the estimation of a single smooth flow field can be performed in closed form, thus making the multiple model estimation computationally feasible. Furthermore, the number of models is estimated automatically using similar methods to those used in the parametric approach. We illustrate the algorithm's performance on synthetic and real image sequences.
---
paper_title: Mise en correspondance de partitions en vue du suivi d'objets

paper_content:

In the field of multimedia applications, the incoming standards promote the creation of new ways of communication, access and manipulation of audiovisual information that go far beyond the plain compression obtained by the preceding coding norms. Among the new functionalities, it is expected that the user will be allowed to access the image content by editing and manipulating the objects of interest. Nevertheless, standards are restricted to object representation and coding, leaving opened a large field of development concerning the problem of object extraction and tracking when they move along a video sequence. In a first step, we have proceeded to the study and fine tuning of widespread applicated algorithms for image filtering and segmentation, being these tools at the basis of all contentbased image and video analysis systems. More particularly, we have focused on a novel class of morphological filters known as levelings, as well as on a variant of the segmentation algorithms based on the constrained ooding of a gradient image. Segmentation techniques aim at yielding a partition image as close as possible to the one produced by the human eye, with a view to the later object recognition. Nevertheless, in most cases this last task needs human interaction. However, when we would like to retrieve an object from large collection of images, or when we would like to track an object through a long sequence, the surveillance of each image becomes infeasible. To face these situations, the development of matching algorithms able to propagate the information through a series of images become essential, human interaction being limited to a initialization step. Going from still images to sequences, the core of this thesis is devoted to the study of the partition matching problem. The method we have developed, named Joint Segmentation and Matching technique (JSM), can be defined as being of hybrid nature. It combines classical algorithms of graph matching with new editing techniques based on the hierarchy of partitions resulting from morphological segmentation. This mix provides a very robust algorithm, in spite of the instability classically associated to the segmentation processes. The result of segmenting two images can strongly differ if the segmentation process produces a single partition image, however we have shown that results are much more stable when producing a hierarchy of nested partitions, in which all contours are present and ranked through a weighted value. The JSM technique is considered a very promising approach according to the obtained results. Being flexible and powerful, it allows the recognition of an object when it reappears after occlusion thanks to the management of a memory graph. Although we have particularly focused our interest on the tracking problem, the developed algorithms can be extended to a large field of applications, being specially suited to perform object retrieval from image or video sequences databases. Finally, in the framework of the European project M4M (MPEG f(o)ur mobiles), we have focused on the development and implementation of a real-time demonstrator for detecting, segmenting and tracking the speaker in videophone sequences. In the view of this application, the real-time constraint has become the greatest challenge to overcome, forcing us to simplify and optimize our algorithms. The main interest in terms of new services is twofold : on one hand the automatic segmentation of the speaker permits the object-based coding, reducing the bitrate without loss of quality on the regions of interest ; on the other hand, it allows the user to edit the sequences by changing the scene composition, for example by introducing a new background, or grouping several speakers in a virtual meeting room.
---
paper_title: Unsupervised video segmentation based on watersheds and temporal tracking

paper_content:

This paper presents a technique for unsupervised video segmentation. This technique consists of two phases: initial segmentation and temporal tracking, similar to a number of existing techniques. However, new algorithms for spatial segmentation, marker extraction, and modified watershed transformation are proposed for the present technique. The new algorithms make this technique differ from existing techniques by the following features: (1) it can effectively track fast moving objects, (2) it can detect the appearance of new objects as well as the disappearance of existing objects, and (3) it is computationally efficient because of the use of watershed transformations and a fast motion estimation algorithm. Simulation results demonstrate that the proposed technique can efficiently segment video sequences with fast moving, newly appearing, or disappearing objects in the scene.
---
paper_title: Video retrieval based on dynamics of color flows

paper_content:

Content based video retrieval is particularly challenging because the huge amount of data associated with videos complicates the extraction of salient information content descriptors. Commercials are a video category where a large part of the content depends on low level perceptual features such as colors and color dynamics. These are related to the evolution-in terms of shrinking, growth and translation"of colored regions along consecutive frames. Each colored region, during its evolution, defines a 3D volume: a color flow. In the paper, a system is presented that supports description of color flows based on 3D wavelet decomposition and retrieval of commercials based on color flow similarity.
---
paper_title: NeTra-V: toward an object-based video representation

paper_content:

We present a prototype video analysis and retrieval system, called NeTra-V, that is being developed to build an object-based video representation for functionalities such as search and retrieval of video objects. A region-based content description scheme using low-level visual descriptors is proposed. In order to obtain regions for local feature extraction, a new spatio-temporal segmentation and region-tracking scheme is employed. The segmentation algorithm uses all three visual features: color, texture, and motion in the video data. A group processing scheme similar to the one in the MPEG-2 standard is used to ensure the robustness of the segmentation. The proposed approach can handle complex scenes with large motion. After segmentation, regions are tracked through the video sequence using extracted local features. The results of tracking are sequences of coherent regions, called "subobjects". Subobjects are the fundamental elements in our low-level content description scheme, which can be used to obtain meaningful physical objects in a high-level content description scheme. Experimental results illustrating segmentation and retrieval are provided.
---
paper_title: Unsupervised Segmentation of Color-Texture Regions in Images and Video

paper_content:

A method for unsupervised segmentation of color-texture regions in images and video is presented. This method, which we refer to as JSEG, consists of two independent steps: color quantization and spatial segmentation. In the first step, colors in the image are quantized to several representative classes that can be used to differentiate regions in the image. The image pixels are then replaced by their corresponding color class labels, thus forming a class-map of the image. The focus of this work is on spatial segmentation, where a criterion for "good" segmentation using the class-map is proposed. Applying the criterion to local windows in the class-map results in the "J-image," in which high and low values correspond to possible boundaries and interiors of color-texture regions. A region growing method is then used to segment the image based on the multiscale J-images. A similar approach is applied to video sequences. An additional region tracking scheme is embedded into the region growing process to achieve consistent segmentation and tracking results, even for scenes with nonrigid object motion. Experiments show the robustness of the JSEG algorithm on real images and video.
---
paper_title: Video segmentation based on multiple features for interactive and automatic multimedia applications

paper_content:

In this thesis, a novel method for the segmentation of video sequences based on the analysis of multiple image features is presented. A key feature of the system is the distinction between two levels of segmentation, namely region and object segmentation. Regions are homogeneous areas of the images, which are extracted automatically by the computer. Semantically meaningful objects are obtained by grouping regions, automatically or through user interaction, according to the specific application. This splitting relieves the computer of ill-posed semantic problems, and allows a higher level of flexibility in the use of the results. The extraction of the regions is based the multidimensional analysis of several image features by a spatially constrained Fuzzy C-Means algorithm. The relative weighting of the different features is achieved by means of an adaptive system that takes into account the local level of reliability of each feature. The temporal tracking of the obtained regions is performed by means of a dual strategy in which the motion-compensated projection of the segmentation mask from previous frames is used to influence the segmentation of the current frame so as to achieve higher temporal coherence and stability.
---
paper_title: Learning flexible sprites in video layers

paper_content:

We propose a technique for automatically learning layers of "flexible sprites" (probabilistic 2-dimensional appearance maps and masks of moving, occluding objects). The model explains each input image as a layered composition of flexible sprites. A variational expectation maximization algorithm is used to learn a mixture of sprites from a video sequence. For each input image, probabilistic inference is used to infer the sprite class, translation, mask values and pixel intensities (including obstructed pixels) in each layer. Exact inference is intractable, but we show how a variational inference technique can be used to process 320/spl times/240 images at 1 frame/second. The only inputs to the learning algorithm are the video sequence, the number of layers and the number of flexible sprites. We give results on several tasks, including summarizing a video sequence with sprites, point-and-click video stabilization, and point-and-click object removal.
---
paper_title: Video segmentation by MAP labeling of watershed segments

paper_content:

This paper addresses the problem of spatio-temporal segmentation of video sequences. An initial intensity segmentation method (watershed segmentation) provides a number of initial segments which are subsequently labeled, with a known number of labels, according to motion information. The label field is modeled as a Markov random field where the statistical spatial and and temporal interactions are expressed on the basis of the initial watershed segments. The labeling criterion is the maximization of the conditional a posteriori probability of the label field given the motion hypotheses, the estimate of the label field of the previous frame, and the image intensities. For the optimization, an iterative motion estimation-labeling algorithm is proposed and experimental results are presented.
---
paper_title: Object tracking with Bayesian estimation of dynamic layer representations

paper_content:

Decomposing video frames into coherent 2D motion layers is a powerful method for representing videos. Such a representation provides an intermediate description that enables applications such as object tracking, video summarization and visualization, video insertion, and sprite-based video compression. Previous work on motion layer analysis has largely concentrated on two-frame or multi-frame batch formulations. The temporal coherency of motion layers and the domain constraints on shapes have not been exploited. This paper introduces a complete dynamic motion layer representation in which spatial and temporal constraints on shape, motion and layer appearance are modeled and estimated in a maximum a-posteriori (MAP) framework using the generalized expectation-maximization (EM) algorithm. In order to limit the computational complexity of tracking arbitrarily shaped layer ownership, we propose a shape prior that parameterizes the representation of shape and prevents motion layers from evolving into arbitrary shapes. In this work, a Gaussian shape prior is chosen to specifically develop a near-real-time tracker for vehicle tracking in aerial videos. However, the general idea of using a parametric shape representation as part of the state of a tracker is a powerful one that can be extended to other domains as well. Based on the dynamic layer representation, an iterative algorithm is developed for continuous object tracking over time. The proposed method has been successfully applied in an airborne vehicle tracking system. Its performance is compared with that of a correlation-based tracker and a motion change-based tracker to demonstrate the advantages of the new method. Examples of tracking when the backgrounds are cluttered and the vehicles undergo various rigid motions and complex interactions such as passing, turning, and stop-and-go demonstrate the strength of the complete dynamic layer representation.
---
paper_title: Object detection and tracking using an EM-based motion estimation and segmentation framework

paper_content:

This paper addresses the segmentation and subsequent tracking of the moving objects within a video sequence. The approach is to jointly produce segmentations and motion parameters which minimise the interframe coding rate of the video sequence. This minimisation is performed using a previously proposed framework based on the expectation-maximisation (EM) algorithm and the minimum description length (MDL) estimate. The paper concentrates on extensions of this framework which have been incorporated to ensure spatial and temporal coherence in the output segmentation sequence. The work has been conducted considering video coding applications and in particular, the MPEG-4 standardisation effort.
---
paper_title: Experimental Comparative Evaluation of Feature Point Tracking Algorithms

paper_content:

We consider dynamic scenes with multiple, independently moving objects. The objects are represented by feature points whose motion is tracked in long image sequences. The feature points may temporarily disappear, enter and leave the view field. This situation is typical for surveillance, scene monitoring (Courtney, 1997) and some other applications.
---
paper_title: Motion Segmentation by Subspace Separation: Model Selection and Reliability Evaluation

paper_content:

Reformulating the Costeira–Kanade algorithm as a pure mathematical theorem, we present a robust segmentation procedure, which we call subspace separation, by incorporating model selection using the geometric AIC. We then study the problem of estimating the number of independent motions using model selection. Finally, we present criteria for evaluating the reliability of individual segmentation results. Again, model selection plays an important role. We confirm the effectiveness of our method by experiments using synthetic and real images.
---
paper_title: Good features to track

paper_content:

No feature-based vision system can work unless good features can be identified and tracked from frame to frame. Although tracking itself is by and large a solved problem, selecting features that can be tracked well and correspond to physical points in the world is still hard. We propose a feature selection criterion that is optimal by construction because it is based on how the tracker works, and a feature monitoring method that can detect occlusions, disocclusions, and features that do not correspond to points in the world. These methods are based on a new tracking algorithm that extends previous Newton-Raphson style search methods to work under affine image transformations. We test performance with several simulations and experiments. >
---
paper_title: Concerning Bayesian Motion Segmentation, Model Averaging, Matching and the Trifocal Tensor

paper_content:

Motion segmentation involves identifying regions of the image that correspond to independently moving objects. The number of independently moving objects, and type of motion model for each of the objects is unknown a priori.
---
paper_title: A Compact and Retrieval-Oriented Video Representation Using Mosaics

paper_content:

Compact yet intuitive representations of digital videos are required to combine high quality storage with interactive video indexing and retrieval capabilities. The advent of video mosaicing has provided a natural way to obtain content-based video representations which are both retrieval-oriented and compression-efficient. In this paper, an algorithm for extracting a robust mosaic representation of video content from sparse interest image points is described. The representation, which is obtained via visual motion clustering and segmentation, features the geometric and kinematic description of all salient objects in the scene, being thus well suited for video browsing, indexing and retrieval by visual content. Results of experiments on several TV sequences provide an insight into the main characteristics of the approach.
---
paper_title: A multi-body factorization method for motion analysis

paper_content:

The structure from motion problem has been extensively studied in the field of computer vision. Yet, the bulk of the existing work assumes that the scene contains only a single moving object. The more realistic case where an unknown number of objects move in the scene has received little attention, especially for its theoretical treatment. We present a new method for separating and recovering the motion and shape of multiple independently moving objects in a sequence of images. The method does not require prior knowledge of the number of objects, nor is dependent on any grouping of features into an object at the image level. For this purpose, we introduce a mathematical construct of object shapes, called the shape interaction matrix, which is invariant to both the object motions and the selection of coordinate systems. This invariant structure is computable solely from the observed trajectories of image features without grouping them into individual objects. Once the structure is computed, it allows for segmenting features into objects by the process of transforming it into a canonical form, as well as recovering the shape and motion of each object. >
---
paper_title: Multibody grouping via orthogonal subspace decomposition

paper_content:

Multibody structure from motion could be solved by the factorization approach. However, the noise measurements would make the segmentation difficult when analyzing the shape interaction matrix. This paper presents an orthogonal subspace decomposition and grouping technique to approach such a problem. We decompose the object shape spaces into signal subspaces and noise subspaces. We show that the signal subspaces of the object shape spaces are orthogonal to each other. Instead of using the shape interaction matrix contaminated by noise, we introduce the shape signal subspace distance matrix for shape space grouping. Outliers could be easily identified by this approach. The robustness of the proposed approach lies in the fact that the shape space decomposition alleviates the influence of noise, and has been verified with extensive experiments.
---
paper_title: Motion Segmentation by Subspace Separation: Model Selection and Reliability Evaluation

paper_content:

Reformulating the Costeira–Kanade algorithm as a pure mathematical theorem, we present a robust segmentation procedure, which we call subspace separation, by incorporating model selection using the geometric AIC. We then study the problem of estimating the number of independent motions using model selection. Finally, we present criteria for evaluating the reliability of individual segmentation results. Again, model selection plays an important role. We confirm the effectiveness of our method by experiments using synthetic and real images.
---
paper_title: Principal component analysis with missing data and its application to polyhedral object modeling

paper_content:

Observation-based object modeling often requires integration of shape descriptions from different views. To overcome the problems of errors and their accumulation, we have developed a weighted least-squares (WLS) approach which simultaneously recovers object shape and transformation among different views without recovering interframe motion. We show that object modeling from a range image sequence is a problem of principal component analysis with missing data (PCAMD), which can be generalized as a WLS minimization problem. An efficient algorithm is devised. After we have segmented planar surface regions in each view and tracked them over the image sequence, we construct a normal measurement matrix of surface normals, and a distance measurement matrix of normal distances to the origin for all visible regions over the whole sequence of views, respectively. These two matrices, which have many missing elements due to noise, occlusion, and mismatching, enable us to formulate multiple view merging as a combination of two WLS problems. A two-step algorithm is presented. After surface equations are extracted, spatial connectivity among the surfaces is established to enable the polyhedral object model to be constructed. Experiments using synthetic data and real range images show that our approach is robust against noise and mismatching and generates accurate polyhedral object models. >
---
paper_title: Motion segmentation based on factorization method and discriminant criterion

paper_content:

A motion segmentation algorithm based on factorization method and discriminant criterion is proposed. This method uses a feature with the most useful similarities for grouping, selected using motion information calculated by factorization method and discriminant criterion. A group is extracted based on discriminant analysis for the selected feature's similarities. The same procedure is applied recursively to the remaining features to extract other groups. This grouping is robust against noise and outliers because features with no useful information are automatically rejected. Numerical computation is simple and stable. No prior knowledge is needed on the number of objects. Experimental results are shown for synthetic data and real image sequences.
---
paper_title: Linear fitting with missing data: applications to structure-from-motion and to characterizing intensity images

paper_content:

Several vision problems can be reduced to the problem of fitting a linear surface of low dimension to data, including the problems of structure-from-affine-motion, and of characterizing the intensity images of a Lambertian scene by constructing the intensity manifold. For these problems, one must deal with a data matrix with some missing elements. In structure-from-motion, missing elements will occur if some point features are not visible in some frames. To construct the intensity manifold missing matrix elements will arise when the surface normals of some scene points do not face the light source in some images. We propose a novel method for fitting a low rank matrix to a matrix with missing elements. We show experimentally that our method produces good results in the presence of noise. These results can be either used directly, or can serve as an excellent starting point for an iterative method.
---
paper_title: Feature grouping in moving objects

paper_content:

We address the problem of grouping points or features common to a single object. In this paper we consider the processing of a sequence of two-dimensional orthogonal projections of a three-dimensional scene containing an unknown number of independently-moving rigid objects. We describe a computationally inexpensive algorithm that can determine the number of bodies and which points belong to which body. >
---
paper_title: Segmentation using eigenvectors: a unifying view

paper_content:

Automatic grouping and segmentation of images remains a challenging problem in computer vision. Recently, a number of authors have demonstrated good performance on this task using methods that are based on eigenvectors of the affinity matrix. These approaches are extremely attractive in that they are based on simple eigendecomposition algorithms whose stability is well understood. Nevertheless, the use of eigendecompositions in the context of segmentation is far from well understood. In this paper we give a unified treatment of these algorithms, and show the close connections between them while highlighting their distinguishing features. We then prove results on eigenvectors of block matrices that allow us to analyze the performance of these algorithms in simple grouping settings. Finally, we use our analysis to motivate a variation on the existing methods that combines aspects from different eigenvector segmentation algorithms. We illustrate our analysis with results on real and synthetic images.
---
paper_title: A multi-body factorization method for motion analysis

paper_content:

The structure from motion problem has been extensively studied in the field of computer vision. Yet, the bulk of the existing work assumes that the scene contains only a single moving object. The more realistic case where an unknown number of objects move in the scene has received little attention, especially for its theoretical treatment. We present a new method for separating and recovering the motion and shape of multiple independently moving objects in a sequence of images. The method does not require prior knowledge of the number of objects, nor is dependent on any grouping of features into an object at the image level. For this purpose, we introduce a mathematical construct of object shapes, called the shape interaction matrix, which is invariant to both the object motions and the selection of coordinate systems. This invariant structure is computable solely from the observed trajectories of image features without grouping them into individual objects. Once the structure is computed, it allows for segmenting features into objects by the process of transforming it into a canonical form, as well as recovering the shape and motion of each object. >
---
paper_title: Concerning Bayesian Motion Segmentation, Model Averaging, Matching and the Trifocal Tensor

paper_content:

Motion segmentation involves identifying regions of the image that correspond to independently moving objects. The number of independently moving objects, and type of motion model for each of the objects is unknown a priori.
---
paper_title: A Compact and Retrieval-Oriented Video Representation Using Mosaics

paper_content:

Compact yet intuitive representations of digital videos are required to combine high quality storage with interactive video indexing and retrieval capabilities. The advent of video mosaicing has provided a natural way to obtain content-based video representations which are both retrieval-oriented and compression-efficient. In this paper, an algorithm for extracting a robust mosaic representation of video content from sparse interest image points is described. The representation, which is obtained via visual motion clustering and segmentation, features the geometric and kinematic description of all salient objects in the scene, being thus well suited for video browsing, indexing and retrieval by visual content. Results of experiments on several TV sequences provide an insight into the main characteristics of the approach.
---
paper_title: Concerning Bayesian Motion Segmentation, Model Averaging, Matching and the Trifocal Tensor

paper_content:

Motion segmentation involves identifying regions of the image that correspond to independently moving objects. The number of independently moving objects, and type of motion model for each of the objects is unknown a priori.
---
paper_title: A probabilistic framework for spatio-temporal video representation and indexing

paper_content:

In this work we describe a novel statistical video representation and modeling scheme. Video representation schemes are needed to enable segmenting a video stream into meaningful video-objects, useful for later indexing and retrieval applications. In the proposed methodology, unsupervised clustering via Guassian mixture modeling extracts coherent space-time regions in feature space, and corresponding coherent segments (video-regions) in the video content. A key feature of the system is the analysis of video input as a single entity as opposed to a sequence of separate frames. Space and time are treated uniformly. The extracted space-time regions allow for the detection and recognition of video events. Results of segmenting video content into static vs. dynamic video regions and video content editing are presented.
---
paper_title: Motion segmentation and tracking using normalized cuts

paper_content:

We propose a motion segmentation algorithm that aims to break a scene into its most prominent moving groups. A weighted graph is constructed on the image sequence by connecting pixels that are in the spatiotemporal neighborhood of each other. At each pixel, we define motion profile vectors which capture the probability distribution of the image velocity. The distance between motion profiles is used to assign a weight on the graph edges. Using normalised cuts we find the most salient partitions of the spatiotemporal graph formed by the image sequence. For segmenting long image sequences, we have developed a recursive update procedure that incorporates knowledge of segmentation in previous frames for efficiently finding the group correspondence in the new frame.
---
paper_title: The emergence of visual objects in space–time

paper_content:

It is natural to think that in perceiving dynamic scenes, vision takes a series of snapshots. Motion perception can ensue when the snapshots are different. The snapshot metaphor suggests two questions: (i) How does the visual system put together elements within each snapshot to form objects? This is the spatial grouping problem. (ii) When the snapshots are different, how does the visual system know which element in one snapshot corresponds to which element in the next? This is the temporal grouping problem. The snapshot metaphor is a caricature of the dominant model in the field—the sequential model—according to which spatial and temporal grouping are independent. The model we propose here is an interactive model, according to which the two grouping mechanisms are not separable. Currently, the experiments that support the interactive model are not conclusive because they use stimuli that are excessively specialized. To overcome this weakness, we created a new type of stimulus—spatiotemporal dot lattices—which allow us to independently manipulate the strength of spatial and temporal groupings. For these stimuli, sequential models make one fundamental assumption: if the spatial configuration of the stimulus remains constant, the perception of spatial grouping cannot be affected by manipulations of the temporal configuration of the stimulus. Our data are inconsistent with this assumption.
---
paper_title: Efficient spatiotemporal grouping using the Nystrom method

paper_content:

Spectral graph theoretic methods have recently shown great promise for the problem of image segmentation, but due to the computational demands, applications of such methods to spatiotemporal data have been slow to appear For even a short video sequence, the set of all pairwise voxel similarities is a huge quantity of data: one second of a 256/spl times/384 sequence captured at 30 Hz entails on the order of 10/sup 13/ pairwise similarities. The contribution of this paper is a method that substantially reduces the computational requirements of grouping algorithms based on spectral partitioning, making it feasible to apply them to very large spatiotemporal grouping problems. Our approach is based on a technique for the numerical solution of eigenfunction problems known as the Nystrom method This method allows extrapolation of the complete grouping solution using only a small number of "typical" samples. In doing so, we successfully exploit the fact that there are far fewer coherent groups in an image sequence than pixels.
---
paper_title: A probabilistic framework for spatio-temporal video representation and indexing

paper_content:

In this work we describe a novel statistical video representation and modeling scheme. Video representation schemes are needed to enable segmenting a video stream into meaningful video-objects, useful for later indexing and retrieval applications. In the proposed methodology, unsupervised clustering via Guassian mixture modeling extracts coherent space-time regions in feature space, and corresponding coherent segments (video-regions) in the video content. A key feature of the system is the analysis of video input as a single entity as opposed to a sequence of separate frames. Space and time are treated uniformly. The extracted space-time regions allow for the detection and recognition of video events. Results of segmenting video content into static vs. dynamic video regions and video content editing are presented.
---
paper_title: Motion segmentation and tracking using normalized cuts

paper_content:

We propose a motion segmentation algorithm that aims to break a scene into its most prominent moving groups. A weighted graph is constructed on the image sequence by connecting pixels that are in the spatiotemporal neighborhood of each other. At each pixel, we define motion profile vectors which capture the probability distribution of the image velocity. The distance between motion profiles is used to assign a weight on the graph edges. Using normalised cuts we find the most salient partitions of the spatiotemporal graph formed by the image sequence. For segmenting long image sequences, we have developed a recursive update procedure that incorporates knowledge of segmentation in previous frames for efficiently finding the group correspondence in the new frame.
---
paper_title: Normalized cuts and image segmentation

paper_content:

We propose a novel approach for solving the perceptual grouping problem in vision. Rather than focusing on local features and their consistencies in the image data, our approach aims at extracting the global impression of an image. We treat image segmentation as a graph partitioning problem and propose a novel global criterion, the normalized cut, for segmenting the graph. The normalized cut criterion measures both the total dissimilarity between the different groups as well as the total similarity within the groups. We show that an efficient computational technique based on a generalized eigenvalue problem can be used to optimize this criterion. We have applied this approach to segmenting static images and found results very encouraging.
---
paper_title: Efficient spatiotemporal grouping using the Nystrom method

paper_content:

Spectral graph theoretic methods have recently shown great promise for the problem of image segmentation, but due to the computational demands, applications of such methods to spatiotemporal data have been slow to appear For even a short video sequence, the set of all pairwise voxel similarities is a huge quantity of data: one second of a 256/spl times/384 sequence captured at 30 Hz entails on the order of 10/sup 13/ pairwise similarities. The contribution of this paper is a method that substantially reduces the computational requirements of grouping algorithms based on spectral partitioning, making it feasible to apply them to very large spatiotemporal grouping problems. Our approach is based on a technique for the numerical solution of eigenfunction problems known as the Nystrom method This method allows extrapolation of the complete grouping solution using only a small number of "typical" samples. In doing so, we successfully exploit the fact that there are far fewer coherent groups in an image sequence than pixels.
---
paper_title: Segmentation using eigenvectors: a unifying view

paper_content:

Automatic grouping and segmentation of images remains a challenging problem in computer vision. Recently, a number of authors have demonstrated good performance on this task using methods that are based on eigenvectors of the affinity matrix. These approaches are extremely attractive in that they are based on simple eigendecomposition algorithms whose stability is well understood. Nevertheless, the use of eigendecompositions in the context of segmentation is far from well understood. In this paper we give a unified treatment of these algorithms, and show the close connections between them while highlighting their distinguishing features. We then prove results on eigenvectors of block matrices that allow us to analyze the performance of these algorithms in simple grouping settings. Finally, we use our analysis to motivate a variation on the existing methods that combines aspects from different eigenvector segmentation algorithms. We illustrate our analysis with results on real and synthetic images.
---
paper_title: The Visual Analysis of Human Movement: A Survey

paper_content:

The ability to recognize humans and their activities by vision is key for a machine to interact intelligently and effortlessly with a human-inhabited environment. Because of many potentially important applications, “looking at people” is currently one of the most active application domains in computer vision. This survey identifies a number of promising applications and provides an overview of recent developments in this domain. The scope of this survey is limited to work on whole-body or hand motion; it does not include work on human faces. The emphasis is on discussing the various methodologies; they are grouped in 2-D approaches with or without explicit shape models and 3-D approaches. Where appropriate, systems are reviewed. We conclude with some thoughts about future directions.
---
paper_title: Probabilistic Data Association Methods for Tracking Complex Visual Objects

paper_content:

We describe a framework that explicitly reasons about data association to improve tracking performance in many difficult visual environments. A hierarchy of tracking strategies results from ascribing ambiguous or missing data to: 1) noise-like visual occurrences, 2) persistent, known scene elements (i.e., other tracked objects), or 3) persistent, unknown scene elements. First, we introduce a randomized tracking algorithm adapted from an existing probabilistic data association filter (PDAF) that is resistant to clutter and follows agile motion. The algorithm is applied to three different tracking modalities-homogeneous regions, textured regions, and snakes-and extensibly defined for straightforward inclusion of other methods. Second, we add the capacity to track multiple objects by adapting to vision a joint PDAF which oversees correspondence choices between same-modality trackers and image features. We then derive a related technique that allows mixed tracker modalities and handles object overlaps robustly. Finally, we represent complex objects as conjunctions of cues that are diverse both geometrically (e.g., parts) and qualitatively (e.g., attributes). Rigid and hinge constraints between part trackers and multiple descriptive attributes for individual parts render the whole object more distinctive, reducing susceptibility to mistracking. Results are given for diverse objects such as people, microscopic cells, and chess pieces.
---

Title: A Survey of Spatio-Temporal Grouping Techniques

Section 1: Introduction
Description 1: Write an introduction explaining the importance of spatio-temporal grouping in video processing, including applications and challenges.

Section 2: Overview of Classification
Description 2: Describe the different approaches to spatio-temporal grouping, including segregation based on spatial and temporal dimensions, along with the order of operations.

Section 3: Building Blocks of the Grouping Process
Description 3: Discuss the fundamental elements used by various grouping methods, such as individual pixels or regions.

Section 4: Segmentation with Spatial Priority
Description 4: Explain methods that prioritize spatial segmentation before temporal grouping, including both motion and color/texture-based segmentation.

Section 5: Sequential Motion Segmentation
Description 5: Detail how spatio-temporal segmentation based on instantaneous motion works, including framewise motion segmentation and how temporal coherence is maintained.

Section 6: Framewise Motion Segmentation
Description 6: Discuss the techniques used in motion similarity and motion model fitting, emphasizing different motion parameter spaces and contextual similarities.

Section 7: Spatial Segmentation using Color/Texture
Description 7: Describe methods that rely on visual features such as color and texture for segmentation, and how these are merged temporally.

Section 8: Temporal Coherence
Description 8: Explain techniques for maintaining temporal coherence in spatio-temporal segmentation.

Section 9: Trajectory Grouping
Description 9: Describe methods that use long-term motion information by estimating and grouping trajectories.

Section 10: Direct Comparison of Trajectories
Description 10: Elaborate on methods that directly compare trajectories to define similarities and group them accordingly.

Section 11: Subspace Factorization
Description 11: Explain how subspace factorization is used to group trajectories based on their motion in matrix space.

Section 12: Hypothesize and Test
Description 12: Describe hypothesize and test methods, including RANSAC, and how they are used to validate trajectory groupings.

Section 13: Motion Mixture Models
Description 13: Discuss motion mixture models for associating trajectories with parametric motion models using an EM approach.

Section 14: Joint Spatial and Temporal Segmentation 
Description 14: Overview methods that simultaneously consider spatial and temporal dimensions for video segmentation, including different clustering and graph-based approaches.

Section 15: Clustering in Feature Space
Description 15: Describe the approach of clustering pixels based on a multi-dimensional feature space that includes color, spatial, and temporal information.

Section 16: Graph-Based Segmentation
Description 16: Explain graph-based segmentation techniques and their application to spatio-temporal volumes using graph cut methods.

Section 17: Concluding Remarks
Description 17: Summarize the survey, discussing the categories of methods, their strengths and weaknesses, and potential areas for future research.