Density-based distances (DBDs) provide a principled approach to metric learning by defining distances in terms of the underlying data distribution. By employing a Riemannian metric that increases in regions of low probability density, shortest paths naturally follow the data manifold. Fermat distances, a specific type of DBD, have attractive properties, but existing estimators based on nearest neighbor graphs suffer from poor convergence due to inaccurate density estimates. Moreover, graph-based methods scale poorly to high dimensions, as the proposed geodesics are often insufficiently smooth. We address these challenges in two key ways. First, we learn densities using normalizing flows. Second, we refine geodesics through relaxation, guided by a learned score model. Additionally, we introduce a dimension-adapted Fermat distance that scales intuitively to high dimensions and improves numerical stability. Our work paves the way for the practical use of density-based distances, especially in high-dimensional spaces.

We present a novel theoretical framework for understanding the expressive power of normalizing flows. Despite their prevalence in scientific applications, a comprehensive understanding of flows remains elusive due to their restricted architectures. Existing theorems fall short as they require the use of arbitrarily ill-conditioned neural networks, limiting practical applicability. We propose a distributional universality theorem for well-conditioned coupling-based normalizing flows such as RealNVP. In addition, we show that volume-preserving normalizing flows are not universal, what distribution they learn instead, and how to fix their expressivity. Our results support the general wisdom that affine and related couplings are expressive and in general outperform volume-preserving flows, bridging a gap between empirical results and theoretical understanding.

Gaussianization is a simple generative model that can be trained without backpropagation. It has shown compelling performance on low dimensional data. As the dimension increases, however, it has been observed that the convergence speed slows down. We show analytically that the number of required layers scales linearly with the dimension for Gaussian input. We argue that this is because the model is unable to capture dependencies between dimensions. Empirically, we find the same linear increase in cost for arbitrary input $p(x)$, but observe favorable scaling for some distributions. We explore potential speed-ups and formulate challenges for further research.

In structured prediction, target objects have rich internal structure which does not factorize into independent components and violates common i.i.d. assumptions. This challenge becomes apparent through the exponentially large output space in applications such as image segmentation or scene graph generation. We present a novel PAC-Bayesian risk bound for structured prediction wherein the rate of generalization scales not only with the number of structured examples but also with their size. The underlying assumption, conforming to ongoing research on generative models, is that data are generated by the Knothe-Rosenblatt rearrangement of a factorizing reference measure. This allows to explicitly distill the structure between random output variables into a Wasserstein dependency matrix. Our work makes a preliminary step towards leveraging powerful generative models to establish generalization bounds for discriminative downstream tasks in the challenging setting of structured prediction.

Abstract The Turing mechanism describes the emergence of spatial patterns due to spontaneous symmetry breaking in reaction–diffusion processes and underlies many developmental processes. Identifying Turing mechanisms in biological systems defines a challenging problem. This paper introduces an approach to the prediction of Turing parameter values from observed Turing patterns. The parameter values correspond to a parametrized system of reaction–diffusion equations that generate Turing patterns as steady state. The Gierer–Meinhardt model with four parameters is chosen as a case study. A novel invariant pattern representation based on resistance distance histograms is employed, along with Wasserstein kernels, in order to cope with the highly variable arrangement of local pattern structure that depends on the initial conditions which are assumed to be unknown. This enables us to compute physically plausible distances between patterns, to compute clusters of patterns and, above all, model parameter prediction based on training data that can be generated by numerical model evaluation with random initial data: for small training sets, classical state-of-the-art methods including operator-valued kernels outperform neural networks that are applied to raw pattern data, whereas for large training sets the latter are more accurate. A prominent property of our approach is that only a single pattern is required as input data for model parameter predicion. Excellent predictions are obtained for single parameter values and reasonably accurate results for jointly predicting all four parameter values.

Abstract. This paper introduces a novel nonlocal partial difference equation (G-PDE) for labeling metric data on graphs. The G-PDE is derived as a nonlocal reparametrization of the assignment flow approach that was introduced in [ J. Math. Imaging Vision, 58 (2017), pp. 211–238]. Due to this parameterization, solving the G-PDE numerically is shown to be equivalent to computing the Riemannian gradient flow with respect to a nonconvex potential. We devise an entropy-regularized difference of convex (DC) functions decomposition of this potential and show that the basic geometric Euler scheme for integrating the assignment flow is equivalent to solving the G-PDE by an established DC programming scheme. Moreover, the viewpoint of geometric integration reveals a basic way to exploit higher-order information of the vector field that drives the assignment flow, in order to devise a novel accelerated DC programming scheme. A detailed convergence analysis of both numerical schemes is provided and illustrated by numerical experiments.

Coupling-based normalizing flows (e.g. RealNVP) are a popular family of normalizing flow architectures that work surprisingly well in practice. This calls for theoretical understanding. Existing work shows that such flows weakly converge to arbitrary data distributions. However, they make no statement about the stricter convergence criterion used in practice, the maximum likelihood loss. For the first time, we make a quantitative statement about this kind of convergence: We prove that all coupling-based normalizing flows perform whitening of the data distribution (i.e. diagonalize the covariance matrix) and derive corresponding convergence bounds that show a linear convergence rate in the depth of the flow. Numerical experiments demonstrate the implications of our theory and point at open questions.

Abstract At the present time optical coherence tomography (OCT) is among the most commonly used non-invasive imaging methods for the acquisition of large volumetric scans of human retinal tissues and vasculature. The substantial increase of accessible highly resolved 3D samples at the optic nerve head and the macula is directly linked to medical advancements in early detection of eye diseases. To resolve decisive information from extracted OCT volumes and to make it applicable for further diagnostic analysis, the exact measurement of retinal layer thicknesses serves as an essential task be done for each patient separately. However, manual examination of OCT scans is a demanding and time consuming task, which is typically made difficult by the presence of tissue-dependent speckle noise. Therefore, the elaboration of automated segmentation models has become an important task in the field of medical image processing. We propose a novel, purely data driven geometric approach to order-constrained 3D OCT retinal cell layer segmentation which takes as input data in any metric space and can be implemented using only simple, highly parallelizable operations. As opposed to many established retinal layer segmentation methods, we use only locally extracted features as input and do not employ any global shape prior. The physiological order of retinal cell layers and membranes is achieved through the introduction of a smoothed energy term. This is combined with additional regularization of local smoothness to yield highly accurate 3D segmentations. The approach thereby systematically avoid bias pertaining to global shape and is hence suited for the detection of anatomical changes of retinal tissue structure. To demonstrate its robustness, we compare two different choices of features on a data set of manually annotated 3D OCT volumes of healthy human retina. The quality of computed segmentations is compared to the state of the art in automatic retinal layer segmention as well as to manually annotated ground truth data in terms of mean absolute error and Dice similarity coefficient. Visualizations of segmented volumes are also provided.

This paper extends the recently introduced assignment flow approach for supervised image labeling to unsupervised scenarios where no labels are given. The resulting self-assignment flow takes a pairwise data affinity matrix as input data and maximizes the correlation with a low-rank matrix that is parametrized by the variables of the assignment flow, which entails an assignment of the data to themselves through the formation of latent labels (feature prototypes). A single user parameter, the neighborhood size for the geometric regularization of assignments, drives the entire process. By smooth geodesic interpolation between different normalizations of self-assignment matrices on the positive definite matrix manifold, a one-parameter family of self-assignment flows is defined. Accordingly, our approach can be characterized from different viewpoints, e.g., as performing spatially regularized, rank-constrained discrete optimal transport, or as computing spatially regularized normalized spectral cuts. Regarding combinatorial optimization, our approach successfully determines completely positive factorizations of self-assignments in large-scale scenarios, subject to spatial regularization. Various experiments, including the unsupervised learning of patch dictionaries using a locally invariant distance function, illustrate the properties of the approach.

We introduce a novel approach to Maximum A Posteriori (MAP) inference based on discrete graphical models. By utilizing local Wasserstein distances for coupling assignment measures across edges of the underlying graph, a given discrete objective function is smoothly approximated and restricted to the assignment manifold. A corresponding multiplicative update scheme combines in a single process (i) geometric integration of the resulting Riemannian gradient flow, and (ii) rounding to integral solutions that represent valid labelings. Throughout this process, local marginalization constraints known from the established LP relaxation are satisfied, whereas the smooth geometric setting results in rapidly converging iterations that can be carried out in parallel for every edge.

We consider the energy minimization problem for undirected graphical models, also known as MAP-inference problem for Markov random fields which is NP-hard in general. We propose a novel polynomial time algorithm to obtain a part of its optimal non-relaxed integral solution. Our algorithm is initialized with variables taking integral values in the solution of a convex relaxation of the MAP-inference problem and iteratively prunes those, which do not satisfy our criterion for partial optimality. We show that our pruning strategy is in a certain sense theoretically optimal. Also empirically our method outperforms previous approaches in terms of the number of persistently labelled variables. The method is very general, as it is applicable to models with arbitrary factors of an arbitrary order and can employ any solver for the considered relaxed problem. Our method's runtime is determined by the runtime of the convex relaxation solver for the MAP-inference problem.

We consider the energy minimization problem for undirected graphical models, also known as MAP-inference problem for Markov random Fields which is NP-hard in general. We propose a novel polynomial time algorithm to obtain a part of its optimal nonrelaxed integral solution. Our algorithm is initialized with variables taking integral values in the solution of a convex relaxation of the MAP-inference problem and iteratively prunes those, which do not satisfy our criterion for partial optimality. We show that our pruning strategy is in a certain sense theoretically optimal. Also empirically our method outperforms previous ap proaches in terms of the number of persistently labelled variables. The method is very general, as it is applicable to models with arbitrary factors of an arbitrary order and can employ any solver for the considered relaxed problem. Our method's runtime is determined by the runtime of the convex relaxation solver for the MAP-inference problem.

We study unique recovery of cosparse signals from limited-view tomographic measurements of two- and three-dimensional domains. Admissible signals belong to the union of subspaces defined by all cosupports of maximal cardinality ℓ with respect to the discrete gradient operator. We relate ℓ both to the number of measurements and to a nullspace condition with respect to the measurement matrix, so as to achieve unique recovery by linear programming. These results are supported by comprehensive numerical experiments that show a high correlation of performance in practice and theoretical predictions. Despite poor properties of the measurement matrix from the viewpoint of compressed sensing, the class of uniquely recoverable signals basically seems large enough to cover practical applications, like contactless quality inspection of compound solid bodies composed of few materials.

We consider a class of quasi-variational inequalities (QVIs) for adaptive image restoration, where the adaptivity is described via solution-dependent constraint sets. In previous work we studied both theoretical and numerical issues. While we were able to show the existence of solutions for a relatively broad class of problems, we encountered difficulties concerning uniqueness of the solution as well as convergence of existing algorithms for solving QVIs. In particular, it seemed that with increasing image size the growing condition number of the involved differential operator posed severe problems. In the present paper we prove uniqueness for a larger class of problems, particularly independent of the image size. Moreover, we provide a numerical algorithm with proved convergence. Experimental results support our theoretical findings.

Even years ago, Szeliski et al. published an influential study on energy minimization methods for Markov random fields (MRF). This study provided valuable insights in choosing the best optimization technique for certain classes of problems. While these insights remain generally useful today, the phenominal success of random field models means that the kinds of inference problems we solve have changed significantly. Specifically, the models today often include higher order interactions, flexible connectivity structures, large label-spaces of different cardinalities, or learned energy tables. To reflect these changes, we provide a modernized and enlarged study. We present an empirical comparison of 24 state-of-art techniques on a corpus of 2,300 energy minimization instances from 20 diverse computer vision applications. To ensure reproducibility, we evaluate all methods in the OpenGM2 framework and report extensive results regarding runtime and solution quality. Key insights from our study agree with the results of Szeliski et al. for the types of models they studied. However, on new and challenging types of models our findings disagree and suggest that polyhedral methods and integer programming solvers are competitive in terms of runtime and solution quality over a large range of model types.

Discrete graphical models (also known as discrete Markov random fields) are a major conceptual tool to model the structure of optimization problems in computer vision. While in the last decade research has focused on fast approximative methods, algorithms that provide globally optimal solutions have come more into the research focus in the last years. However, large scale computer vision problems seemed to be out of reach for such methods. In this paper we introduce a promising way to bridge this gap based on partial optimality and structural properties of the underlying problem factorization. Combining these preprocessing steps, we are able to solve grids of size 2048×2048 in less than 90 seconds. On the hitherto unsolvable Chinese character dataset of Nowozin et. al we obtain provably optimal results in 56% of the instances and achieve competitive runtimes on other recent benchmark problems. While in the present work only generalized Potts models are considered, an extension to general graphical models seems to be feasible.

We consider energy minimization for undirected graphical models, also known as MAP-inference problem for Markov random fields. Although combinatorial methods, which return a provably optimal integral solution of the problem, made a big progress in the past decade, they are still typically unable to cope with large-scale datasets. On the other hand, large scale datasets are typically defined on sparse graphs, and convex relaxation methods, such as linear programming relaxations often provide good approximations to integral solutions. We propose a novel method of combining combinatorial and convex programming techniques to obtain a global solution of the initial combinatorial problem. Based on the information obtained from the solution of the convex relaxation, our method confines application of the combinatorial solver to a small fraction of the initial graphical model, which allows to optimally solve big problems. We demonstrate the power of our approach on a computer vision energy minimization benchmark.

We analyze representative ill-posed scenarios of tomographic PIV (particle image velocimetry) with a focus on conditions for unique volume reconstruction. Based on sparse random seedings of a region of interest with small particles, the corresponding systems of linear projection equations are probabilistically analyzed in order to determine: (i) the ability of unique reconstruction in terms of the imaging geometry and the critical sparsity parameter, and (ii) sharpness of the transition to non-unique reconstruction with ghost particles when choosing the sparsity parameter improperly. The sparsity parameter directly relates to the seeding density used for PIV in experimental fluids dynamics that is chosen empirically to date. Our results provide a basic mathematical characterization of the PIV volume reconstruction problem that is an essential prerequisite for any algorithm used to actually compute the reconstruction. Moreover, we connect the sparse volume function reconstruction problem from few tomographic projections to major developments in compressed sensing.

We present a novel variational approach to image restoration (e.g., denoising, inpainting, labeling) that enables us to complement established variational approaches with a histogram-based prior, enforcing closeness of the solution to some given empirical measure. By minimizing a single objective function, the approach utilizes simultaneously two quite different sources of information for restoration: spatial context in terms of some smoothness prior and nonspatial statistics in terms of the novel prior utilizing the Wasserstein distance between probability measures. We study the combination of the functional lifting technique with two different relaxations of the histogram prior and derive a jointly convex variational approach. Mathematical equivalence of both relaxations is established, and cases where optimality holds are discussed. Additionally, we present an efficient algorithmic scheme for the numerical treatment of the presented model. Experiments using the basic total variation based denoising approach as a case study demonstrate our novel regularization approach.

Approximate inference by decomposition of discrete graphical models and Lagrangian relaxation has become a key technique in computer vision. The resulting dual objective function is convenient from the optimization point-of-view, in principle. Due to its inherent non-smoothness, however, it is not directly amenable to efficient convex optimization. Related work either weakens the relaxation by smoothing or applies variations of the inefficient projected subgradient methods. In either case, heuristic choices of tuning parameters influence the performance and significantly depend on the specific problem at hand. In this paper, we introduce a novel approach based on bundle methods from the field of combinatorial optimization. It is directly based on the non-smooth dual objective function, requires no tuning parameters and showed a markedly improved efficiency uniformly over a large variety of problem instances including benchmark experiments. Our code will be publicly available after publication of this paper.

A variational approach is presented to the estimation of turbulent fluid flow from particle image sequences in experimental fluid mechanics. The approach comprises two coupled optimizations for adapting size and shape of a Gaussian correlation window at each location and for estimating the flow, respectively. The method copes with a wide range of particle densities and image noise levels without any data-specific parameter tuning. Based on a careful implementation of a multiscale nonlinear optimization technique, we demonstrate robustness of the solution over typical experimental scenarios and highest estimation accuracy for an international benchmark data set (PIV Challenge).

In the above paper (ibid., vol. 21, no. 6, pp. 3053-3065, Jun. 2012), several corrections requested by the authors were omitted. The IEEE regrets the error. On pp. 3058 and 3059, the algorithms were not indented corrected. They are corrected here.

We study the MAP-labeling problem for graphical models by optimizing a dual problem obtained by Lagrangian decomposition. In this paper, we focus specifically on Nes-terov's optimal first-order optimization scheme for non-smooth convex programs, that has been studied for a range of other problems in computer vision and machine learning in recent years. We show that in order to obtain an efficiently convergent iteration, this approach should be augmented with a dynamic estimation of a corresponding Lip-schitz constant, leading to a runtime complexity of O(1/ϵ) in terms of the desired precision ϵ. Additionally, we devise a stopping criterion based on a duality gap as a sound basis for competitive comparison and show how to compute it efficiently. We evaluate our results using the publicly available Middlebury database and a set of computer generated graphical models that highlight specific aspects, along with other state-of-the-art methods for MAP-inference.

We present an approach to jointly estimating camera motion and dense scene structure in terms of depth maps from monocular image sequences in driver-assistance scenarios. For two consecutive frames of a sequence taken with a single fast moving camera, the approach combines numerical estimation of egomotion on the Euclidean manifold of motion parameters with variational regularization of dense depth map estimation. Embedding this online joint estimator into a recursive framework achieves a pronounced spatio-temporal filtering effect and robustness. We report the evaluation of thousands of images taken from a car moving at speed up to 100 km/h. The results compare favorably with two alternative settings that require more input data: stereo based scene reconstruction and camera motion estimation in batch mode using multiple frames. The employed benchmark dataset is publicly available.

We study convex relaxations of the image labeling problem on a continuous domain with regularizers based on metric interaction potentials. The generic framework ensures existence of minimizers and covers a wide range of relaxations of the original combinatorial problem. We focus on two specific relaxations that differ in flexibility and simplicity—one can be used to tightly relax any metric interaction potential, while the other covers only Euclidean metrics but requires less computational effort. For solving the nonsmooth discretized problem, we propose a globally convergent Douglas–Rachford scheme and show that a sequence of dual iterates can be recovered in order to provide a posteriori optimality bounds. In a quantitative comparison to two other first-order methods, the approach shows competitive performance on synthetic and real-world images. By combining the method with an improved rounding technique for nonstandard potentials, we were able to routinely recover integral solutions within $1\%$–$5\%$ of the global optimum for the combinatorial image labeling problem.

This paper presents a novel pedestrian detection system for intelligent vehicles. We propose the use of dense stereo for both the generation of regions of interest and pedestrian classification. Dense stereo allows the dynamic estimation of camera parameters and the road profile, which, in turn, provides strong scene constraints on possible pedestrian locations. For classification, we extract spatial features (gradient orientation histograms) directly from dense depth and intensity images. Both modalities are represented in terms of individual feature spaces, in which discriminative classifiers (linear support vector machines) are learned. We refrain from the construction of a joint feature space but instead employ a fusion of depth and intensity on the classifier level. Our experiments involve challenging image data captured in complex urban environments (i.e., undulating roads and speed bumps). Our results show a performance improvement by up to a factor of 7.5 at the classification level and up to a factor of 5 at the tracking level (reduction in false alarms at constant detection rates) over a system with static scene constraints and intensity-only classification.

Imaging plays an important role in experimental fluid dynamics. It is equally important both for scientific research and a range of industrial applications. It is known, however, that estimated velocity fields of fluids often suffer from various types of corruptions like missing data, for instance, that make their physical interpretation questionable. We present an algorithm that accepts a wide variety of corrupted 2-D vector fields as input data and allows to recover missing data fragments and to remove noise in a physically plausible way. Our approach essentially exploits the physical properties of incompressible fluid flows and does not rely upon any particular model of noise. As a result, the developed algorithm performs well and robust for different types of noise and estimation errors. The computational algorithm is sufficiently simple to scale up to large 3-D problems.

This paper studies automatic segmentation of multiple motions from tracked feature points through spectral embedding and clustering of linear subspaces. We show that the dimension of the ambient space is crucial for separability, and that low dimensions chosen in prior work are not optimal. We suggest lower and upper bounds together with a data-driven procedure for choosing the optimal ambient dimension. Application of our approach to the Hopkins155 video benchmark database uniformly outperforms a range of state-of-the-art methods both in terms of segmentation accuracy and computational speed.

We introduce a linearly weighted variant of the total variation for vector fields in order to formulate regularizers for multi-class labeling problems with non-trivial interclass distances. We characterize the possible distances, show that Euclidean distances can be exactly represented, and review some methods to approximate non-Euclidean distances in order to define novel total variation based regularizers. We show that the convex relaxed problem can be efficiently optimized to a prescribed accuracy with optimality certificates using Nesterov's method, and evaluate and compare our approach on several synthetical and real-world examples.

In this paper we propose a novel prior-based variational object segmentation method in a global minimization framework which unifies image segmentation and image denoising. The idea of the proposed method is to convexify the energy functional of the Chan-Vese method in order to find a global minimizer, so called continuous graph cuts. The method is extended by adding an additional shape constraint into the convex energy functional in order to segment an object using prior information. We show that the energy functional including a shape prior term can be relaxed from optimization over characteristic functions to optimization over arbitrary functions followed by a thresholding at an arbitrarily chosen level between 0 and 1. Experimental results demonstrate the performance and robustness of the method to segment objects in real images.

This paper presents a robust multicue approach to the integrated detection and tracking of pedestrians in a cluttered urban environment. A novel spatiotemporal object representation is proposed, which combines a generative shape model and a discriminative texture classifier, both of which are composed of a mixture of pose-specific submodels. Shape is represented by a set of linear subspace models, which is an extension of point distribution models, with shape transitions being modeled by a first-order Markov process. Texture, i.e., the shape-normalized intensity pattern, is represented by a manifold that is implicitly delimited by a set of pattern classifiers, whereas texture transition is modeled by a random walk. Direct 3-D measurements that are provided by a stereo system are further incorporated into the observation density function. We employ a Bayesian framework based on particle filtering to achieve integrated object detection and tracking. Large-scale experiments that involve pedestrian detection and tracking from a moving vehicle demonstrate the benefit of the proposed approach.

We exploit the biconvex nature of the Euclidean non-negative matrix factorization (NMF) optimization problem to derive optimization schemes based on sequential quadratic and second order cone programming. We show that for ordinary NMF, our approach performs as well as existing state-of-the-art algorithms, while for sparsity-constrained NMF, as recently proposed by P. O. Hoyer in JMLR 5 (2004), it outperforms previous methods. In addition, we show how to extend NMF learning within the same optimization framework in order to make use of class membership information in supervised learning problems.

Example-based learning of codes that statistically encode general image classes is of vital importance for computational vision. Recently non negative matrix factorization (NMF) was suggested to provide image code that was both sparse and localized, in contrast to established non local methods like PCA. In this paper, we adopt and generalize this approach to develop a novel learning framework that allows to efficiently compute sparsity-controlled invariant image codes by a well defined sequence of convex conic programs. Applying the corresponding parameter-free algorithm to various image classes results in semantically relevant and transformation-invariant image representations that are remarkably robust against noise and quantization

This paper investigates the usefulness of bidirectional multigrid methods for variational optical flow computations. Although these numerical schemes are among the fastest methods for solving equation systems, they are rarely applied in the field of computer vision. We demonstrate how to employ those numerical methods for the treatment of variational optical flow formulations and show that the efficiency of this approach even allows for real-time performance on standard PCs. As a representative for variational optic flow methods, we consider the recently introduced combined local-global method. It can be considered as a noise-robust generalization of the Horn and Schunck technique. We present a decoupled, as well as a coupled, version of the classical Gauss-Seidel solver, and we develop several multgrid implementations based on a discretization coarse grid approximation. In contrast, with standard bidirectional multigrid algorithms, we take advantage of intergrid transfer operators that allow for nondyadic grid hierarchies. As a consequence, no restrictions concerning the image size or the number of traversed levels have to be imposed. In the experimental section, we juxtapose the developed multigrid schemes and demonstrate their superior performance when compared to unidirectional multgrid methods and nonhierachical solvers. For the well-known 316 x 252 Yosemite sequence, we succeeded in computing the complete set of dense flow fields in three quarters of a second on a 3.06-GHz Pentium4 PC. This corresponds to a frame rate of 18 flow fields per second which outperforms the widely-used Gauss-Seidel method by almost three orders of magnitude.

We present an approach to parallel variational optical-flow computation by using an arbitrary partition of the image plane and iteratively solving related local variational problems associated with each subdomain. The approach is particularly suited for implementations on PC clusters because interprocess communication is minimized by restricting the exchange of data to a lower dimensional interface. Our mathematical formulation supports various generalizations to linear/nonlinear convex variational approaches, three-dimensional image sequences, spatiotemporal regularization, and unstructured geometries and triangulations. Results concerning the effects of interface preconditioning, as well as runtime and communication volume measurements on a PC cluster, are presented. Our approach provides a major step toward real-time two-dimensional image processing using off-the-shelf PC hardware and facilitates the efficient application of variational approaches to large-scale image processing problems.

Building on recent progress in modeling filter response statistics of natural images we integrate a statistical model into a variational framework for image segmentation. Incorporated in a sound probabilistic distance measure the model drives level sets toward meaningful segmentations of complex textures and natural scenes. Since each region comprises two model parameters only the approach is computationally efficient and enables the application of variational segmentation to a considerably larger class of real-world images. We validate the statistical basis of our approach on thousands of natural images and demonstrate that our model outperforms recent variational segmentation methods based on second-order statistics.

We introduce a novel optimization method based on semidefinite programming relaxations to the field of computer vision and apply it to the combinatorial problem of minimizing quadratic functionals in binary decision variables subject to linear constraints. The approach is (tuning) parameter-free and computes high-quality combinatorial solutions using interior-point methods (convex programming) and a randomized hyperplane technique. Apart from a symmetry condition, no assumptions (such as metric pairwise interactions) are made with respect to the objective criterion. As a consequence, the approach can be applied to a wide range of problems. Applications to unsupervised partitioning, figure-ground discrimination, and binary restoration are presented along with extensive ground-truth experiments. From the viewpoint of relaxation of the underlying combinatorial problem, we show the superiority of our approach to relaxations based on spectral graph theory and prove performance bounds.

We investigate several iterative numerical schemes for nonlinear variational image smoothing and segmentation implemented in parallel. A general iterative framework subsuming these schemes is suggested for which global convergence irrespective of the starting point can be shown. We characterize various edge-preserving regularization methods from the image processing literature involving auxiliary variables as special cases of this general framework. As a by-product, global convergence can be proven under conditions slightly weaker than these stated in the literature. Efficient Krylov subspace solvers for the linear parts of these schemes have been implemented on a multiprocessor machine. The performance of these parallel implementations has been assessed and empirical results concerning convergence rates and speed-up factors are reported.

The paper presentsanewparameter-free approach to non-rigid image registration, where displacements, obtained through a mapping of boundary structures in the source and target image, are incorporated as hard constraints for elastic image deformation. As a consequence, our approach does not contain any parameters of the deformation model (elastic constants). The approach guarantees the exact correspondence of boundary structures after elastic transformation provided that correct input data are available. We describe a linear and an incremental model, the latter model allows to cope also with large deformations. Experimental results for 2-D and 3-D synthetic as well as real medical images are presented. 1

A robust, iterative approach is introduced for finding the dominant plane in a scene using binocular vision. Neither camera calibration nor stereo correspondence is required. Recently L. Cohen (1996) formalized a framework guaranteeing (local) convergence of iterative two-step methods. In this paper, the framework is adopted, with a global step using tentative matches to estimate the planar projectivity, and a local step attempting to solve the stereo correspondence. A detected point in the first image is matched to an auxiliary point in the second image, on the line joining the transformed first image point, and its closest detected second image point. Convergence is assured, while achieving robustness to both mismatching and non-coplanar points.

This paper proposes a general framework for learning motion representations from low-level spatiotemporal features. The concept is based on a self-organizing map (SOM). The authors show how the SOM can be used for predicting object movements, and how additional information of the environment can be related to the inherent model of the movement to obtain generalized motion representations for objects. Traffic scenes are used to test the performance of the system.

A minimization problem is proposed to combine smoothing of locally computed motion data (e.g. normal flow) with the detection of motion boundaries. The continuous formulation of the cost functional allows one to incorporate arbitrary continuity-equations which locally determine apparent motion, and a nonlinear smoothing term adapts to the magnitude of the flow-gradient or to its components divergence, rotation, and shear. The approach has been designed such that gradient descent converges to a unique solution.

The modification by H.H. Nagel (1987) of the approach developed by B.K.P. Horn and B.G. Schunck (1981) for determining optical flow is generalized to the case where local motion information is given by more than one constraint equation. Applying this scheme to three constraint equations reported in the literature, as a special case, a generalization of Nagel's approach is obtained. An existence and uniqueness result of solutions under very general conditions that, in turn, ensures the applicability of standard techniques to compute an approximate solution is presented.>