Piecewise-Smooth Dense Optical Flow via Level Sets

We propose a new algorithm for dense optical flow computation. Dense optical flow schemes are challenged by the presence of motion discontinuities. In state of the art optical flow methods, over-smoothing of flow discontinuities accounts for most of the error. A breakthrough in the performance of optical flow computation has recently been achieved by Brox et~al. Our algorithm embeds their functional within a two phase active contour segmentation framework. Piecewise-smooth flow fields are accommodated and flow boundaries are crisp. Experimental results show the superiority of our algorithm with respect to alternative techniques. We also study a special case of optical flow computation, in which the camera is static. In this case we utilize a known background image to separate the moving elements in the sequence from the static elements. Tests with challenging real world sequences demonstrate the performance gains made possible by incorporating the static camera assumption in our algorithm.     

Variational optic flow on the Sony PlayStation 3

While modern variational methods for optic flow computation offer dense flow fields and highly accurate results, their computational complexity has prevented their use in many real-time applications. With cheap modern parallel hardware such as the Cell Processor of the Sony PlayStation 3, new possibilities arise. For a linear and a nonlinear variant of the popular combined local-global method, we present specific algorithms on this architecture that are tailored towards real-time performance. They are based on bidirectional full multigrid methods with a full approximation scheme in the nonlinear setting. Their parallel design on the Cell hardware uses a temporal instead of a spatial decomposition, and processes operations in a vector-based manner. Memory latencies are reduced by a locality-preserving cache management and optimised access patterns. For images of size 316 × 252 pixels, we obtain dense flow fields for up to 210 frames per second.     

Lucas/Kanade Meets Horn/Schunck: Combining Local and Global Optic Flow Methods

Differential methods belong to the most widely used techniques for optic flow computation in image sequences. They can be classified into local methods such as the Lucas–Kanade technique or Bigün's structure tensor method, and into global methods such as the Horn/Schunck approach and its extensions. Often local methods are more robust under noise, while global techniques yield dense flow fields. The goal of this paper is to contribute to a better understanding and the design of novel differential methods in four ways; (i) We juxtapose the role of smoothing/regularisation processes that are required in local and global differential methods for optic flow computation. (ii) This discussion motivates us to describe and evaluate a novel method that combines important advantages of local and global approaches: It yields dense flow fields that are robust against noise. (iii) Spatiotemporal and nonlinear extensions as well as multiresolution frameworks are presented for this hybrid method. (iv) We propose a simple confidence measure for optic flow methods that minimise energy functionals. It allows to sparsify a dense flow field gradually, depending on the reliability required for the resulting flow. Comparisons with experiments from the literature demonstrate the favourable performance of the proposed methods and the confidence measure.     

Over-Parameterized Variational Optical Flow

A novel optical flow estimation process based on a spatio-temporal model with varying coefficients multiplying a set of basis functions at each pixel is introduced. Previous optical flow estimation methodologies did not use such an over parameterized representation of the flow field as the problem is ill-posed even without introducing any additional parameters: Neighborhood based methods of the Lucas–Kanade type determine the flow at each pixel by constraining the flow to be described by a few parameters in small neighborhoods. Modern variational methods represent the optic flow directly via the flow field components at each pixel. The benefit of over-parametrization becomes evident in the smoothness term, which instead of directly penalizing for changes in the optic flow, accumulates a cost of deviating from the assumed optic flow model. Our proposed method is very general and the classical variational optical flow techniques are special cases of it, when used in conjunction with constant basis functions. Experimental results with the novel flow estimation process yield significant improvements with respect to the best results published so far.     

Dense versus Sparse Approaches for Estimating the Fundamental Matrix

There are two main strategies for solving correspondence problems in computer vision: sparse local feature based approaches and dense global energy based methods. While sparse feature based methods are often used for estimating the fundamental matrix by matching a small set of sophistically optimised interest points, dense energy based methods mark the state of the art in optical flow computation. The goal of our paper is to show that this separation into different application domains is unnecessary and can be bridged in a natural way. As a first contribution we present a new application of dense optical flow for estimating the fundamental matrix. Comparing our results with those obtained by feature based techniques we identify cases in which dense methods have advantages over sparse approaches. Motivated by these promising results we propose, as a second contribution, a new variational model that recovers the fundamental matrix and the optical flow simultaneously as the minimisers of a single energy functional. In experiments we show that our coupled approach is able to further improve the estimates of both the fundamental matrix and the optical flow. Our results prove that dense variational methods can be a serious alternative even in classical application domains of sparse feature based approaches.     

A parallel stereo algorithm that produces dense depth maps and preserves image features

To compute reliable dense depth maps, a stereo algorithm must preserve depth discontinuities and avoid gross errors. In this paper, we show how simple and parallel techniques can be combined to achieve this goal and deal with complex real world scenes. Our algorithm relies on correlation followed by interpolation. During the correlation phase the two images play a symmetric role and we use a validity criterion for the matches that eliminate gross errors: at places where the images cannot be correlated reliably, due to lack of texture of occlusions for example, the algorithm does not produce wrong matches but a very sparse disparity map as opposed to a dense one when the correlation is successful. To generate a dense depth map, the information is then propagated across the featureless areas, but not across discontinuities, by an interpolation scheme that takes image grey levels into account to preserve image features. We show that our algorithm performs very well on difficult images such as faces and cluttered ground level scenes. Because all the algorithms described here are parallel and very regular they could be implemented in hardware and lead to extremely fast stereo systems.This research was supported in part under the Centre National d'Etudes Spatiales VAP contract and in part under a Defence Advanced Research Projects Agency contract at SRI     

IStar: a raster representation for scalable image and volume data

Topology has been an important tool for analyzing scalar data and flow fields in visualization. In this work, we analyze the topology of multivariate image and volume data sets with discontinuities in order to create an efficient, raster-based representation we call IStar. Specifically, the topology information is used to create a dual structure that contains nodes and connectivity information for every segmentable region in the original data set. This graph structure, along with a sampled representation of the segmented data set, is embedded into a standard raster image which can then be substantially downsampled and compressed. During rendering, the raster image is upsampled and the dual graph is used to reconstruct the original function. Unlike traditional raster approaches, our representation can preserve sharp discontinuities at any level of magnification, much like scalable vector graphics. However, because our representation is raster-based, it is well suited to the real-time rendering pipeline. We demonstrate this by reconstructing our data sets on graphics hardware at real-time rates.     

Silhouette‐Aware Warping for Image‐Based Rendering

Image‐based rendering (IBR) techniques allow capture and display of 3D environments using photographs. Modern IBR pipelines reconstruct proxy geometry using multi‐view stereo, reproject the photographs onto the proxy and blend them to create novel views. The success of these methods depends on accurate 3D proxies, which are difficult to obtain for complex objects such as trees and cars. Large number of input images do not improve reconstruction proportionally; surface extraction is challenging even from dense range scans for scenes containing such objects. Our approach does not depend on dense accurate geometric reconstruction; instead we compensate for sparse 3D information by variational image warping. In particular, we formulate silhouette‐aware warps that preserve salient depth discontinuities. This improves the rendering of difficult foreground objects, even when deviating from view interpolation. We use a semi‐automatic step to identify depth discontinuities and extract a sparse set of depth constraints used to guide the warp. Our framework is lightweight and results in good quality IBR for previously challenging environments.     

Highly Accurate Optic Flow Computation with Theoretically Justified Warping

In this paper, we suggest a variational model for optic flow computation based on non-linearised and higher order constancy assumptions. Besides the common grey value constancy assumption, also gradient constancy, as well as the constancy of the Hessian and the Laplacian are proposed. Since the model strictly refrains from a linearisation of these assumptions, it is also capable to deal with large displacements. For the minimisation of the rather complex energy functional, we present an efficient numerical scheme employing two nested fixed point iterations. Following a coarse-to-fine strategy it turns out that there is a theoretical foundation of so-called warping techniques hitherto justified only on an experimental basis. Since our algorithm consists of the integration of various concepts, ranging from different constancy assumptions to numerical implementation issues, a detailed account of the effect of each of these concepts is included in the experimental section. The superior performance of the proposed method shows up by significantly smaller estimation errors when compared to previous techniques. Further experiments also confirm excellent robustness under noise and insensitivity to parameter variations.     

Variational Optic Flow Computation with a Spatio-Temporal Smoothness Constraint

Nonquadratic variational regularization is a well-known and powerful approach for the discontinuity-preserving computation of optic flow. In the present paper, we consider an extension of flow-driven spatial smoothness terms to spatio-temporal regularizers. Our method leads to a rotationally invariant and time symmetric convex optimization problem. It has a unique minimum that can be found in a stable way by standard algorithms such as gradient descent. Since the convexity guarantees global convergence, the result does not depend on the flow initialization. Two iterative algorithms are presented that are not difficult to implement. Qualitative and quantitative results for synthetic and real-world scenes show that our spatio-temporal approach (i) improves optic flow fields significantly, (ii) smoothes out background noise efficiently, and (iii) preserves true motion boundaries. The computational costs are only 50% higher than for a pure spatial approach applied to all subsequent image pairs of the sequence.     

A Theoretical Framework for Convex Regularizers in PDE-Based Computation of Image Motion

Many differential methods for the recovery of the optic flow field from an image sequence can be expressed in terms of a variational problem where the optic flow minimizes some energy. Typically, these energy functionals consist of two terms: a data term, which requires e.g. that a brightness constancy assumption holds, and a regularizer that encourages global or piecewise smoothness of the flow field. In this paper we present a systematic classification of rotation invariant convex regularizers by exploring their connection to diffusion filters for multichannel images. This taxonomy provides a unifying framework for data-driven and flow-driven, isotropic and anisotropic, as well as spatial and spatio-temporal regularizers. While some of these techniques are classic methods from the literature, others are derived here for the first time. We prove that all these methods are well-posed: they posses a unique solution that depends in a continuous way on the initial data. An interesting structural relation between isotropic and anisotropic flow-driven regularizers is identified, and a design criterion is proposed for constructing anisotropic flow-driven regularizers in a simple and direct way from isotropic ones. Its use is illustrated by several examples.     

An extended residual-based variational multiscale method for two-phase flow including surface tension

In this study, an extended residual-based variational multiscale method is proposed for two-phase flow including surface tension. The extended residual-based variational multiscale method combines a residual-based form of the variational multiscale method and the extended finite element method (XFEM). By extending the solution spaces, it is possible to reproduce discontinuities of the solution fields inside elements intersected by the interface. In particular, we propose a quasi-static enrichment to reproduce time-dependent discontinuities. Kink enrichments of both velocity and pressure as well as kink enrichments of velocity combined with jump enrichments of pressure are considered here. To capture the interface between the phases on a fixed grid, a level-set approach is used. A residual-based variational multiscale method is employed for computing both flow and interface motion. The presented method is tested for various two-phase flow examples exhibiting small and large density and viscosity ratios, with and without surface tension: a two-phase Couette flow, a Rayleigh–Taylor instability, a sloshing tank and a three-dimensional rising bubble. To the best of our knowledge, these are the first simulation results for representative time-dependent three-dimensional two-phase flow problems using an extended finite element method. Stable and accurate results are obtained for all test examples.     

The State of the Art in Flow Visualization: Dense and Texture-Based Techniques

Flow visualization has been a very attractive component of scientific visualization research for a long time. Usually very large multivariate datasets require processing. These datasets often consist of a large number of sample locations and several time steps. The steadily increasing performance of computers has recently become a driving factor for a reemergence in flow visualization research, especially in texture‐based techniques. In this paper, dense, texture‐based flow visualization techniques are discussed. This class of techniques attempts to provide a complete, dense representation of the flow field with high spatio‐temporal coherency. An attempt of categorizing closely related solutions is incorporated and presented. Fundamentals are shortly addressed as well as advantages and disadvantages of the methods.     

Freehand HDR Imaging of Moving Scenes with Simultaneous Resolution Enhancement

Despite their high popularity, common high dynamic range (HDR) methods are still limited in their practical applicability: They assume that the input images are perfectly aligned, which is often violated in practise. Our paper does not only free the user from this unrealistic limitation, but even turns the missing alignment into an advantage: By exploiting the multiple exposures, we can create a super‐resolution image. The alignment step is performed by a modern energy‐based optic flow approach that takes into account the varying exposure conditions. Moreover, it produces dense displacement fields with subpixel precision. As a consequence, our approach can handle arbitrary complex motion patterns, caused by severe camera shake and moving objects. Additionally, it benefits from several advantages over existing strategies: (i) It is robust under outliers (noise, occlusions, saturation problems) and allows for sharp discontinuities in the displacement field. (ii) The alignment step neither requires camera calibration nor knowledge of the exposure times. (iii) It can be efficiently implemented on CPU and GPU architectures. After the alignment is performed, we use the obtained subpixel accurate displacement fields as input for an energy‐based, joint super‐resolution and HDR (SR‐HDR) approach. It introduces robust data terms and anisotropic smoothness terms in the SR‐HDR literature. Our experiments with challenging real world data demonstrate that these novelties are pivotal for the favourable performance of our approach.     

Optic flow based on multi-scale anchor point movement and discontinuity-preserving regularization

We introduce a new method to determine the flow field of an image sequence using multi-scale anchor points. These anchor points manifest themselves in the scale-space representation of an image. The novelty of our method lies largely in the fact that the relation between the scale-space anchor points and the flow field is formulated in terms of soft constraints in a variational method. This leads to an algorithm for the computation of the flow field that differs fundamentally from previously proposed ones based on hard constraints. We show a significant performance increase when our method is applied to the Yosemite image sequence, a standard and well-established benchmark sequence in optic flow research. Also, it is shown that this performance is not sensitive to slight changes in the two parameters used and that, with the same parameter values, our method yields very good results in the Rubber Whale image sequence as well.     

A Variational Aggregation Framework for Patch-Based Optical Flow Estimation

We propose a variational aggregation method for optical flow estimation. It consists of a two-step framework, first estimating a collection of parametric motion models to generate motion candidates, and then reconstructing a global dense motion field. The aggregation step is designed as a motion reconstruction problem from spatially varying sets of motion candidates given by parametric motion models. Our method is designed to capture large displacements in a variational framework without requiring any coarse-to-fine strategy. We handle occlusion with a motion inpainting approach in the candidates computation step. By performing parametric motion estimation, we combine the robustness to noise of local parametric methods with the accuracy yielded by global regularization. We demonstrate the performance of our aggregation approach by comparing it to standard variational methods and a discrete aggregation approach on the Middlebury and MPI Sintel datasets.     

FALDOI: A New Minimization Strategy for Large Displacement Variational Optical Flow

We propose a large displacement optical flow method that introduces a new strategy to compute a good local minimum of any optical flow energy functional. The method requires a given set of discrete matches, which can be extremely sparse, and an energy functional which locally guides the interpolation from those matches. In particular, the matches are used to guide a structured coordinate descent of the energy functional around these keypoints. It results in a two-step minimization method at the finest scale which is very robust to the inevitable outliers of the sparse matcher and able to capture large displacements of small objects. Its benefits over other variational methods that also rely on a set of sparse matches are its robustness against very few matches, high levels of noise, and outliers. We validate our proposal using several optical flow variational models. The results consistently outperform the coarse-to-fine approaches and achieve good qualitative and quantitative performance on the standard optical flow benchmarks.     

Direct detection of flow discontinuities by 3D curvature operators

We present an approach for the direct detection of flow discontinuities which avoids explicit computation of a dense optic flow field. It is based on regarding the time varying image as a hypersurface in four-dimensional space and on using the Gaussian curvature properties of this hypersurface as a direct indicator for the presence of motion discontinuities. An easy to implement, nonlinear operator is suggested and possible extensions of the basic scheme are discussed.     

面向运动分割优化的变分光流计算方法研究

面向运动分割的需求,围绕变分光流计算中的运动边缘保留问题,对反应-扩散式光流计算模型中的扩散张量设计与改进方法进行系统深入研究。 在分析已有设计方法的基础上,提出了一种融合图像和流场信息驱动的扩散张量设计方法,并利用该扩散张量建立光流计算模型,然后在多尺度计算框架下给出了相应的偏微分方程数值计算方法。 理论分析与对比实验结果表明,这种设计方法能有效克服现有方法提取运动边缘不精确的缺点,更准确地刻画出运动边缘,提高光流的计算精度。