In this paper, we consider the problem of capturing an omnidirectional evader using a differential drive robot in an obstacle-free environment. At the beginning of this game, the evader is at a distance (the capture distance) from the pursuer. The goal of the evader is to keep the pursuer farther than this capture distance for as long as possible. The goal of the pursuer is to capture the evader as soon as possible. In this paper, we make the following contributions. We present closed-form representations of the motion primitives and time-optimal strategies for each player; these strategies are in Nash equilibrium, meaning that any unilateral deviation of each player from these strategies does not provide to such player benefit toward the goal of winning the game. We propose a partition of the playing space into mutually disjoint regions where the strategies of the players are well established. This partition is represented as a graph, which exhibits properties that guarantee global optimality. We also analyze the decision problem of the game and we present the conditions defining the winner.

We present a new Markov random field (MRF) based model for parametric image segmentation. Instead of directly computing a label map, our method computes the probability that the observed data at each pixel is generated by a particular intensity model. Prior information about segmentation smoothness and low entropy of the probability distribution maps is codified in the form of a MRF with quadratic potentials so that the optimal estimator is obtained by solving a quadratic cost function with linear constraints. Although, for segmentation purposes, the mode of the probability distribution at each pixel is naturally used as an optimal estimator, our method permits the use of other estimators, such as the mean or the median, which may be more appropriate for certain applications. Numerical experiments and comparisons with other published schemes are performed, using both synthetic images and real data of brain MRI for which expert hand-made segmentations are available. Finally, we show that the proposed methodology may be easily extended to other problems, such as stereo disparity estimation.

Parametric image segmentation consists of finding a label field that defines a partition of an image into a set of nonoverlapping regions and the parameters of the models that describe the variation of some property within each region. A new Bayesian formulation for the solution of this problem is presented, based on the key idea of using a doubly stochastic prior model for the label field, which allows one to find exact optimal estimators for both this field and the model parameters by the minimization of a differentiable function. An efficient minimization algorithm and comparisons with existing methods on synthetic images are presented, as well as examples of realistic applications to the segmentation of Magnetic Resonance volumes and to motion segmentation.

A new Bayesian formulation for the image segmentation problem is presented. It is based on the key idea of using a doubly stochastic prior model for the label field, which allows one to find exact optimal estimators by the minimization of a differentiable function. Comparisons with existing methods on synthetic images are presented, as well as realistic applications to the segmentation of magnetic resonance volumes, to motion segmentation, and to edge-preserving filtering.

Automatic registration of multimodal images involves algorithmically estimating the coordinate transformation required to align the data sets. Most existing methods in the literature are unable to cope with registration of image pairs with large nonoverlapping field of view (FOV). We propose a robust algorithm, based on matching dominant local frequency image representations, which can cope with image pairs with large nonoverlapping FOV. The local frequency representation naturally allows for processing the data at different scales/resolutions, a very desirable property from a computational efficiency view point. Our algorithm involves minimizing-over all rigid/affine transformations--the integral of the squared error (ISE or L2 E) between a Gaussian model of the residual and its true density function. The residual here refers to the difference between the local frequency representations of the transformed (by an unknown transformation) source and target data. We present implementation results for image data sets, which are misaligned magnetic resonance (MR) brain scans obtained using different image acquisition protocols as well as misaligned MR-computed tomography scans. We experimently show that our L2E-based scheme yields better accuracy over the normalized mutual information.

Automatic three-dimensional (3-D) segmentation of the brain from magnetic resonance (MR) scans is a challenging problem that has received an enormous amount of attention lately. Of the techniques reported in the literature, very few are fully automatic. In this paper, we present an efficient and accurate, fully automatic 3-D segmentation procedure for brain MR scans. It has several salient features; namely, the following. 1) Instead of a single multiplicative bias field that affects all tissue intensities, separate parametric smooth models are used for the intensity of each class. 2) A brain atlas is used in conjunction with a robust registration procedure to find a nonrigid transformation that maps the standard brain to the specimen to be segmented. This transformation is then used to: segment the brain from nonbrain tissue; compute prior probabilities for each class at each voxel location and find an appropriate automatic initialization. 3) Finally, a novel algorithm is presented which is a variant of the expectation-maximization procedure, that incorporates a fast and accurate way to find optimal segmentations, given the intensity models along with the spatial coherence assumption. Experimental results with both synthetic and real data are included, as well as comparisons of the performance of our algorithm with that of other published methods.

We present a class of models, derived from classical discrete Markov random fields, that may be used for the solution of ill-posed problems in image processing and in computational vision. They lead to reconstruction algorithms that are flexible, computationally efficient, and biologically plausible. To illustrate their use, we present their application to the reconstruction of the dominant orientation and direction fields, to the classification of multiband images, and to image quantization and filtering.

A robust method is presented for constructing layered Earth models from surface resistivity data. The algorithm automatically accommodates any number of discontinuities without the need to specify a priori its number or location in the vertical profile. It further includes automatic correction factors for the common segmentation of Schlumberger soundings due to static shift effects.

In the last decade, several authors have proposed edge preserving regularization (EPR) methods for solving ill posed problems in image processing and computer vision. These EPR techniques are based on the minimization of non-quadratic and in some cases non-convex energy functionals. We introduce a new EPR technique that corresponds to an adaptive-rest condition spring system, meaning that at those places where we want an homogeneous smoothing, the rest condition of the springs is close to zero (as a homogeneous spring system), whereas at edges, the rest condition is equal to the size of the corresponding jump.

We present a probabilistic approach for local scale selection. The proposed method computes a probability measure on scale space, which is based on Bayesian estimation theory, and it leads to an efficient computational implementation. At each scale we associate a decomposition likelihood, one for the smoothed image and other for the residual. The scale selection method, based on the minimal description length principle, maximizes the likelihood of the observed image given the local scale, and at the same time, minimizes the residual. Initial experiments show that our approach can be successfully applied to edge detection, and also to adaptive Gaussian filtering and texture segmentation.

We present a new algorithm for the efficient estimation of piecewise parametric models for image segmentation. This algorithm permits the simultaneous estimation of: the number of models; the parameters for each model and the regions where each model is applicable. It is based on Bayesian estimation theory, and is theoretically justified by the use of a specific cost function that decreases at every iteration and by a new model for the posterior marginal distributions which is amenable to the use of fast computational methods.

This paper presents a new method for constructing one-dimensional (1D) electrical conductivity models of the Earth from surface electromagnetic measurements. The construction of these models is a nonlinear inverse problem that can be approached by linearization techniques combined with iterative methods and Tikhonov's regularization. The standard application of these techniques usually leads to smooth models that represent a continuous variation of conductivity with depth. In this work, the authors describe how these methods can be modified to incorporate what is known in computer vision as the line process (LP) decoupling technique, which has the ability to include discontinuities in the models. This results in piecewise smooth models that are often more adequate for representing stratified media. They have implemented a relaxation technique to construct these types of models and present numerical experiments as well as an application to field data. These examples illustrate the performance of the combined LP and Tikhonov's regularization method.

The computation of a piecewise smooth function that approximates a finite set of data points may be decomposed into two decoupled tasks: 1) the computation of the locally smooth models, and hence, the segmentation of the data into classes that consist of the sets of points best approximated by each model; 2) the computation of the normalized discriminant functions for each induced class (which maybe interpreted as relative probabilities). The approximating function may then be computed as the optimal estimator with respect to this measure field. For the first step, we propose a scheme that involves both robust regression and spatial localization using Gaussian windows. The discriminant functions are obtained fitting Gaussian mixture models for the data distribution inside each class. We give an efficient procedure for effecting both computations and for the determination of the optimal number of components. Examples of the application of this scheme to image filtering, surface reconstruction and time series prediction are presented.

The fundamental role that a class of layered probabilistic structures may play in the solution of certain complex approximation problems that appear in the integration of visual information, specifically, those that involve the reconstruction of piecewise smooth functions using information from different channels, is explained. Specific models for these structures in the form of Markovian random fields of probability measures are developed, and practical algorithms are given for their computation. Their implementation is discussed both in terms of analog and digital networks (cellular automata). A simple application of this scheme to the reconstruction of piecewise smooth surfaces is discussed in detail. Its application to the solution of more complex problems that involve the interaction of several computational modules, such as the reconstruction of visible surfaces and automatic learning, is outlined as well.>

A geometric characterization is given of a class of stochastic cellular automata, whose invariant probability measures are Gibbsian distributions (i.e. Markovian random fields). This class, whose members may be considered as the Cartesian product of convex polytopes with a finite number of vertices. contains all known automata of this type (e.g., the Metropolis, Gibbs sampler, and heat bath algorithms), and also a new family, which is characterized by having nonreversible dynamic behavior. The fact that there is a complete geometric structure, instead of isolated points, opens the possibility of using classical techniques (such as convex programming) for the design of optimal automata. Some examples of applications are given, oriented towards the solution of image restoration problems.>