Skip to main content
main-content

Über dieses Buch

This book constitutes the refereed proceedings of the 6th International Conference on Scale Space and Variational Methods in Computer Vision, SSVM 2017, held in Kolding, Denmark, in June 2017. The 55 revised full papers presented were carefully reviewed and selected from 77 submissions. The papers are organized in the following topical sections: Scale Space and PDE Methods; Restoration and Reconstruction; Tomographic Reconstruction; Segmentation; Convex and Non-Convex Modeling and Optimization in Imaging; Optical Flow, Motion Estimation and Registration; 3D Vision.

Inhaltsverzeichnis

Frontmatter

Scale Space and PDE Methods

Frontmatter

Spatio-Temporal Scale Selection in Video Data

We present a theory and a method for simultaneous detection of local spatial and temporal scales in video data. The underlying idea is that if we process video data by spatio-temporal receptive fields at multiple spatial and temporal scales, we would like to generate hypotheses about the spatial extent and the temporal duration of the underlying spatio-temporal image structures that gave rise to the feature responses. For two types of spatio-temporal scale-space representations, (i) a non-causal Gaussian spatio-temporal scale space for offline analysis of pre-recorded video sequences and (ii) a time-causal and time-recursive spatio-temporal scale space for online analysis of real-time video streams, we express sufficient conditions for spatio-temporal feature detectors in terms of spatio-temporal receptive fields to deliver scale covariant and scale invariant feature responses. A theoretical analysis is given of the scale selection properties of six types of spatio-temporal interest point detectors, showing that five of them allow for provable scale covariance and scale invariance. Then, we describe a time-causal and time-recursive algorithm for detecting sparse spatio-temporal interest points from video streams and show that it leads to intuitively reasonable results.

Tony Lindeberg

Dynamic Texture Recognition Using Time-Causal Spatio-Temporal Scale-Space Filters

This work presents an evaluation of using time-causal scale-space filters as primitives for video analysis. For this purpose, we present a new family of video descriptors based on regional statistics of spatio-temporal scale-space filter responses and evaluate this approach on the problem of dynamic texture recognition. Our approach generalises a previously used method, based on joint histograms of receptive field responses, from the spatial to the spatio-temporal domain. We evaluate one member in this family, constituting a joint binary histogram, on two widely used dynamic texture databases. The experimental evaluation shows competitive performance compared to previous methods for dynamic texture recognition, especially on the more complex DynTex database. These results support the descriptive power of time-causal spatio-temporal scale-space filters as primitives for video analysis.

Ylva Jansson, Tony Lindeberg

Corner Detection Using the Affine Morphological Scale Space

We introduce a method for corner estimation based on the affine morphological scale space (AMSS). Using some explicit known formula about corner evolution across AMSS, proven by Alvarez and Morales in 1997, we define a morphological cornerness measure based on the expected evolution of an ideal corner across AMSS. We define a new procedure to track the corner motion across AMSS. To evaluate the accuracy of the method we study in details the results for a collection of synthetic corners with angles from 15 to 160$$^\circ $$. We also present experiments in real images and we show that the proposed method can also automatically handle the case of multiple junctions.

Luis Alvarez

Nonlinear Spectral Image Fusion

In this paper we demonstrate that the framework of nonlinear spectral decompositions based on total variation (TV) regularization is very well suited for image fusion as well as more general image manipulation tasks. The well-localized and edge-preserving spectral TV decomposition allows to select frequencies of a certain image to transfer particular features, such as wrinkles in a face, from one image to another. We illustrate the effectiveness of the proposed approach in several numerical experiments, including a comparison to the competing techniques of Poisson image editing, linear osmosis, wavelet fusion and Laplacian pyramid fusion. We conclude that the proposed spectral TV image decomposition framework is a valuable tool for semi- and fully-automatic image editing and fusion.

Martin Benning, Michael Möller, Raz Z. Nossek, Martin Burger, Daniel Cremers, Guy Gilboa, Carola-Bibiane Schönlieb

Tubular Structure Segmentation Based on Heat Diffusion

This paper proposes an interactive method for tubular structure segmentation. The method is based on the minimal paths obtained from the geodesic distance solved by the heat equation. This distance can be based both on isotropic or anisotropic metric by solving the corresponding heat equation. Thanks to the additional dimension added for the local radius around the centerline, our method can not only detect the centerline of the structure, but also extracts the boundaries of the structures. Our algorithm is tested on both synthetic and real images. The promising results demonstrate the robustness and effectiveness of the algorithm.

Fang Yang, Laurent D. Cohen

Analytic Existence and Uniqueness Results for PDE-Based Image Reconstruction with the Laplacian

Partial differential equations are well suited for dealing with image reconstruction tasks such as inpainting. One of the most successful mathematical frameworks for image reconstruction relies on variations of the Laplace equation with different boundary conditions. In this work we analyse these formulations and discuss the existence and uniqueness of solutions of corresponding boundary value problems, as well as their regularity from an analytic point of view. Our work not only sheds light on useful aspects of the well posedness of several standard problem formulations in image reconstruction but also aggregates them in a common framework. In addition, the performed analysis guides us to specify two new formulations of the classic image reconstruction problem that may give rise to new developments in image reconstruction.

Laurent Hoeltgen, Isaac Harris, Michael Breuß, Andreas Kleefeld

Combining Contrast Invariant L1 Data Fidelities with Nonlinear Spectral Image Decomposition

This paper focuses on multi-scale approaches for variational methods and corresponding gradient flows. Recently, for convex regularization functionals such as total variation, new theory and algorithms for nonlinear eigenvalue problems via nonlinear spectral decompositions have been developed. Those methods open new directions for advanced image filtering. However, for an effective use in image segmentation and shape decomposition, a clear interpretation of the spectral response regarding size and intensity scales is needed but lacking in current approaches. In this context, $$L^1$$ data fidelities are particularly helpful due to their interesting multi-scale properties such as contrast invariance. Hence, the novelty of this work is the combination of $$L^1$$-based multi-scale methods with nonlinear spectral decompositions. We compare $$L^1$$ with $$L^2$$ scale-space methods in view of spectral image representation and decomposition. We show that the contrast invariant multi-scale behavior of $$L^1-TV$$ promotes sparsity in the spectral response providing more informative decompositions. We provide a numerical method and analyze synthetic and biomedical images at which decomposition leads to improved segmentation.

Leonie Zeune, Stephan A. van Gils, Leon W. M. M. Terstappen, Christoph Brune

An Efficient and Stable Two-Pixel Scheme for 2D Forward-and-Backward Diffusion

Image enhancement with forward-and-backward (FAB) diffusion is numerically very challenging due to its negative diffusivities. As a remedy, we first extend the explicit nonstandard scheme by Welk et al. (2009) from the 1D scenario to the practically relevant two-dimensional setting. We prove that under a fairly severe time step restriction, this 2D scheme preserves a maximum–minimum principle. Moreover, we find an interesting Lyapunov sequence which guarantees convergence to a flat steady state. Since a global application of the time step size restriction leads to very slow algorithms and is more restrictive than necessary for most pixels, we introduce a much more efficient scheme with locally adapted time step sizes. It applies diffusive two-pixel interactions in a randomised order and adapts the time step size to the specific pixel pair. These space-variant time steps are synchronised at sync times. Our experiments show that our novel two-pixel scheme allows to compute FAB diffusion with guaranteed $$L^\infty $$-stability at a speed that can be three orders of magnitude larger than its explicit counterpart with a global time step size.

Martin Welk, Joachim Weickert

Restoration and Reconstruction

Frontmatter

Blind Space-Variant Single-Image Restoration of Defocus Blur

We address the problem of blind piecewise space-variant image deblurring where only part of the image is sharp, assuming a shallow depth of field which imposes significant defocus blur.We propose an automatic image recovery approach which segments the sharp and blurred sub-regions, iteratively estimates a non-parametric blur kernel and restores the sharp image via a variational non-blind space variant method.We present a simple and efficient blur measure which emphasizes the blur difference of the sub-regions followed by a blur segmentation procedure based on an evolving level set function.One of the contributions of this work is the extension to the space-variant case of progressive blind deconvolution recently proposed, an iterative process consisting of non-parametric blind kernel estimation and residual blur deblurring. Apparently this progressive strategy is superior to the one step deconvolution procedure. Experimental results on real images demonstrate the effectiveness of the proposed algorithm.

Leah Bar, Nir Sochen, Nahum Kiryati

Denoising by Inpainting

The filling-in effect of diffusion processes has been successfully used in many image analysis applications. Examples include image reconstructions in inpainting-based compression or dense optic flow computations. As an interesting side effect of diffusion-based inpainting, the interpolated data are smooth, even if the known image data are noisy: Inpainting averages information from noisy sources. Since this effect has not been investigated for denoising purposes so far, we propose a general framework for denoising by inpainting. It averages multiple inpainting results from different selections of known data. We evaluate two concrete implementations of this framework: The first one specifies known data on a shifted regular grid, while the second one employs probabilistic densification to optimise the known pixel locations w.r.t. the inpainting quality. For homogeneous diffusion inpainting, we demonstrate that our regular grid method approximates the quality of its corresponding diffusion filter. The densification algorithm with homogeneous diffusion inpainting, however, shows edge-preserving behaviour. It resembles space-variant diffusion and offers better reconstructions than homogeneous diffusion filters.

Robin Dirk Adam, Pascal Peter, Joachim Weickert

Stochastic Image Reconstruction from Local Histograms of Gradient Orientation

Many image processing algorithms rely on local descriptors extracted around selected points of interest. Motivated by privacy issues, several authors have recently studied the possibility of image reconstruction from these descriptors, and proposed reconstruction methods performing local inference using a database of images. In this paper we tackle the problem of image reconstruction from local histograms of gradient orientation, obtained from simplified SIFT descriptors. We propose two reconstruction models based on Poisson editing and on the combination of multiscale orientation fields. These models are able to recover global shapes and many geometric details of images. They compare well to state of the art results, without requiring the use of any external database.

Agnès Desolneux, Arthur Leclaire

A Dynamic Programming Solution to Bounded Dejittering Problems

We propose a dynamic programming solution to image dejittering problems with bounded displacements and obtain efficient algorithms for the removal of line jitter, line pixel jitter, and pixel jitter.

Lukas F. Lang

Robust Blind Deconvolution with Convolution-Spectrum-Based Kernel Regulariser and Poisson-Noise Data Terms

In recent work by Liu, Chang and Ma a variational blind deconvolution approach with alternating estimation of image and point-spread function was presented in which an innovative regulariser for the point-spread function was constructed using the convolution spectrum of the blurred image. Further work by Moser and Welk introduced robust data fidelity terms to this approach but did so at the cost of introducing a mismatch between the data fidelity terms used in image and point-spread function estimation. We propose an improved version of this robust model that avoids the mentioned inconsistency. We extend the model to multi-channel images and show experiments on synthetic and real-world images to compare the robust variants with the method by Liu, Chang and Ma.

Martin Welk

Optimal Patch Assignment for Statistically Constrained Texture Synthesis

This article introduces a new model for patch-based texture synthesis that controls the distribution of patches in the synthesized texture. The proposed approach relies on an optimal assignment of patches over decimated pixel grids. This assignment problem formulates the synthesis as the minimization of a discrepancy measure between input’s and output’s patches through their optimal permutation. The resulting non-convex optimization problem is addressed with an iterative algorithm alternating between a patch assignment step and a patch aggregation step. We show that this model statistically constrains the output texture content, while inheriting the structure-preserving property of patch-based methods. We also propose a relaxed patch assignment extension that increases the robustness to non-stationnary textures.

Jorge Gutierrez, Julien Rabin, Bruno Galerne, Thomas Hurtut

A Correlation-Based Dissimilarity Measure for Noisy Patches

In this work, we address the problem of defining a robust patch dissimilarity measure for an image corrupted by an additive white Gaussi an noise. The whiteness of the noise, despite being a common assumption that is realistic for RAW images, is hardly used to its full potential by classical denoising methods. In particular, the $$L^2$$-norm is very widely used to evaluate distances and similarities between images or patches. However, we claim that a better dissimilarity measure can be defined to convey more structural information. We propose to compute the dissimilarity between patches by using the autocorrelation of their difference. In order to illustrate the usefulness of this measure, we perform three experiments. First, this new criterion is used in a similar patch detection task. Then, we use it on the Non Local Means (NLM) denoising method and show that it improves performances by a large margin. Finally, it is applied to the task of no-reference evaluation of denoising results, where it shows interesting visual properties. In all those applications, the autocorrelation improves over the $$L^2$$-norm.

Paul Riot, Andrés Almansa, Yann Gousseau, Florence Tupin

Analysis of a Physically Realistic Film Grain Model, and a Gaussian Film Grain Synthesis Algorithm

Film grain is a highly valued characteristic of analog images, thus realistic digital film grain synthesis is an important objective for many modern photographers and film-makers. We carry out a theoretical analysis of a physically realistic film grain model, based on a Boolean model, and derive expressions for the expected value and covariance of the film grain texture. We approximate these quantities using a Monte Carlo simulation, and use them to propose a film grain synthesis algorithm based on Gaussian textures. With numerical and visual experiments, we demonstrate the correctness and subjective qualities of the proposed algorithm.

Alasdair Newson, Noura Faraj, Julie Delon, Bruno Galerne

Below the Surface of the Non-local Bayesian Image Denoising Method

The non-local Bayesian (NLB) patch-based approach of Lebrun et al. [12] is considered as a state-of-the-art method for the restoration of (color) images corrupted by white Gaussian noise. It gave rise to numerous ramifications like e.g., possible improvements, processing of various data sets and video. This article is the first attempt to analyse the method in depth in order to understand the main phenomena underlying its effectiveness. Our analysis, corroborated by numerical tests, shows several unexpected facts. In a variational setting, the first-step Bayesian approach to learn the prior for patches is equivalent to a pseudo-Tikhonov regularisation where the regularisation parameters can be positive or negative. Practically very good results in this step are mainly due to the aggregation stage – whose importance needs to be re-evaluated.

Pablo Arias, Mila Nikolova

Directional Total Generalized Variation Regularization for Impulse Noise Removal

A recently suggested regularization method, which combines directional information with total generalized variation (TGV), has been shown to be successful for restoring Gaussian noise corrupted images. We extend the use of this regularizer to impulse noise removal and demonstrate that using this regularizer for directional images is highly advantageous. In order to estimate directions in impulse noise corrupted images, which is much more challenging compared to Gaussian noise corrupted images, we introduce a new Fourier transform-based method. Numerical experiments show that this method is more robust with respect to noise and also more efficient than other direction estimation methods.

Rasmus Dalgas Kongskov, Yiqiu Dong

Tomographic Reconstruction

Frontmatter

A Novel Convex Relaxation for Non-binary Discrete Tomography

We present a novel convex relaxation and a corresponding inference algorithm for the non-binary discrete tomography problem, that is, reconstructing discrete-valued images from few linear measurements. In contrast to state of the art approaches that split the problem into a continuous reconstruction problem for the linear measurement constraints and a discrete labeling problem to enforce discrete-valued reconstructions, we propose a joint formulation that addresses both problems simultaneously, resulting in a tighter convex relaxation. For this purpose a constrained graphical model is set up and evaluated using a novel relaxation optimized by dual decomposition. We evaluate our approach experimentally and show superior solutions both mathematically (tighter relaxation) and experimentally in comparison to previously proposed relaxations.

Jan Kuske, Paul Swoboda, Stefania Petra

Image Reconstruction by Multilabel Propagation

This work presents a non-convex variational approach to joint image reconstruction and labeling. Our regularization strategy, based on the KL-divergence, takes into account the smooth geometry on the space of discrete probability distributions. The proposed objective function is efficiently minimized via DC programming which amounts to solving a sequence of convex programs, with guaranteed convergence to a critical point. Each convex program is solved by a generalized primal dual algorithm. This entails the evaluation of a proximal mapping, evaluated efficiently by a fixed point iteration. We illustrate our approach on few key scenarios in discrete tomography and image deblurring.

Matthias Zisler, Freddie Åström, Stefania Petra, Christoph Schnörr

User-Friendly Simultaneous Tomographic Reconstruction and Segmentation with Class Priors

Simultaneous Reconstruction and Segmentation (SRS) strategies for computed tomography (CT) present a way to combine the two tasks, which in many applications traditionally are performed as two successive and separate steps. A combined model has a potentially positive effect by allowing the two tasks to influence one another, at the expense of a more complicated algorithm. The combined model increases in complexity due to additional parameters and settings requiring tuning, thus complicating the practical usability. This paper takes it outset in a recently published variational algorithm for SRS. We propose a simplification that reduces the number of required parameters, and we perform numerical experiments investigating the effect and the conditions under which this approach is feasible.

Hans Martin Kjer, Yiqiu Dong, Per Christian Hansen

An Optimal Transport-Based Restoration Method for Q-Ball Imaging

We propose a variational approach for edge-preserving total variation (TV)-based regularization of Q-ball data from high angular resolution diffusion imaging (HARDI). While total variation is among the most popular regularizers for variational problems, its application to orientation distribution functions (ODF), as they naturally arise in Q-ball imaging, is not straightforward. We propose to use an extension that specifically takes into account the metric on the underlying orientation space. The key idea is to write the difference quotients in the TV seminorm in terms of the Wasserstein statistical distance from optimal transport. We combine this regularizer with a matching Wasserstein data fidelity term. Using the Kantorovich-Rubinstein duality, the variational model can be formulated as a convex optimization problem that can be solved using a primal-dual algorithm. We demonstrate the effectiveness of the proposed framework on real and synthetic Q-ball data.

Thomas Vogt, Jan Lellmann

Nonlinear Flows for Displacement Correction and Applications in Tomography

In this paper we derive nonlinear evolution equations associated with a class of non-convex energy functionals which can be used for correcting displacement errors in imaging data. We show a preliminary convergence result of a relaxed convexification of the non-convex optimization problem. Some properties on the behavior of the solutions of these filtering flows are studied by numerical analysis. At the end, we provide examples for correcting angular perturbations in tomographical data.

Guozhi Dong, Otmar Scherzer

Performance Bounds for Cosparse Multichannel Signal Recovery via Collaborative-TV

We consider a new class of regularizers called collaborative total variation (CTV) to cope with the ill-posed nature of multichannel image reconstruction. We recast our reconstruction problem in the analysis framework from compressed sensing. This allows us to derive theoretical measurement bounds that guarantee successful recovery of multichannel signals via CTV regularization. We derive new measurement bounds for two types of CTV from Gaussian measurements. These bounds are proved for multichannel signals of one and two dimensions. We compare them to empirical phase transitions of one-dimensional signals and obtain a good agreement especially when the sparsity of the analysis representation is not very small.

Lukas Kiefer, Stefania Petra

Simultaneous Reconstruction and Segmentation of CT Scans with Shadowed Data

We propose a variational approach for simultaneous reconstruction and multiclass segmentation of X-ray CT images, with limited field of view and missing data. We propose a simple energy minimisation approach, loosely based on a Bayesian rationale. The resulting non convex problem is solved by alternating reconstruction steps using an iterated relaxed proximal gradient, and a proximal approach for the segmentation. Preliminary results on synthetic data demonstrate the potential of the approach for synchrotron imaging applications.

François Lauze, Yvain Quéau, Esben Plenge

Segmentation

Frontmatter

Graphical Model Parameter Learning by Inverse Linear Programming

We introduce two novel methods for learning parameters of graphical models for image labelling. The following two tasks underline both methods: (i) perturb model parameters based on given features and ground truth labelings, so as to exactly reproduce these labelings as optima of the local polytope relaxation of the labelling problem; (ii) train a predictor for the perturbed model parameters so that improved model parameters can be applied to the labelling of novel data. Our first method implements task (i) by inverse linear programming and task (ii) using a regressor e.g. a Gaussian process. Our second approach simultaneously solves tasks (i) and (ii) in a joint manner, while being restricted to linearly parameterised predictors. Experiments demonstrate the merits of both approaches.

Vera Trajkovska, Paul Swoboda, Freddie Åström, Stefania Petra

A Fast MBO Scheme for Multiclass Data Classification

We describe a new variant of the MBO scheme for solving the semi-supervised data classification problem on a weighted graph. The scheme is based on the minimization of the graph heat content energy. The resulting algorithms guarantee dissipation of the graph heat content energy for an extremely wide class of weight matrices. As a result, our method is both flexible and unconditionally stable. Experimental results on benchmark machine learning datasets show that our approach matches or exceeds the performance of current state-of-the-art variational methods while being considerably faster.

Matt Jacobs

Convex Non-Convex Segmentation over Surfaces

The paper addresses the segmentation of real-valued functions having values on a complete, connected, 2-manifold embedded in $${{\mathbb {R}}}^3$$. We present a three-stage segmentation algorithm that first computes a piecewise smooth multi-phase partition function, then applies clusterization on its values, and finally tracks the boundary curves to obtain the segmentation on the manifold. The proposed formulation is based on the minimization of a Convex Non-Convex functional where an ad-hoc non-convex regularization term improves the treatment of the boundary lengths handled by the $$\ell _1$$ norm in [2]. An appropriate numerical scheme based on the Alternating Directions Methods of Multipliers procedure is proposed to efficiently solve the nonlinear optimization problem. Experimental results show the effectiveness of this three-stage procedure.

Martin Huska, Alessandro Lanza, Serena Morigi, Fiorella Sgallari

Numerical Integration of Riemannian Gradient Flows for Image Labeling

The image labeling problem can be described as assigning to each pixel a single element from a finite set of predefined labels. Recently, a smooth geometric approach was proposed [2] by following the Riemannian gradient flow of a given objective function on the so-called assignment manifold. In this paper, we adopt an approach from the literature on uncoupled replicator dynamics and extend it to the geometric labeling flow, that couples the dynamics through Riemannian averaging over spatial neighborhoods. As a result, the gradient flow on the assignment manifold transforms to a flow on a vector space of matrices, such that parallel numerical update schemes can be derived by established numerical integration. A quantitative comparison of various schemes reveals a superior performance of the adaptive scheme originally proposed, regarding both the number of iterations and labeling accuracy.

Fabrizio Savarino, Ruben Hühnerbein, Freddie Åström, Judit Recknagel, Christoph Schnörr

MAP Image Labeling Using Wasserstein Messages and Geometric Assignment

Recently, a smooth geometric approach to the image labeling problem was proposed [1] by following the Riemannian gradient flow of a given objective function on the so-called assignment manifold. The approach evaluates user-defined data term and additionally performs Riemannian averaging of the assignment vectors for spatial regularization. In this paper, we consider more elaborate graphical models, given by both data and pairwise regularization terms, and we show how they can be evaluated using the geometric approach. This leads to a novel inference algorithm on the assignment manifold, driven by local Wasserstein flows that are generated by pairwise model parameters. The algorithm is massively edge-parallel and converges to an integral labeling solution.

Freddie Åström, Ruben Hühnerbein, Fabrizio Savarino, Judit Recknagel, Christoph Schnörr

Multinomial Level-Set Framework for Multi-region Image Segmentation

We present a simple and elegant level-set framework for multi-region image segmentation. The key idea is based on replacing the traditional regularized Heaviside function with the multinomial logistic regression function, commonly known as Softmax. Segmentation is addressed by solving an optimization problem which considers the image intensities likelihood, a regularizer, based on boundary smoothness, and a pairwise region interactive term, which is naturally derived from the proposed formulation. We demonstrate our method on challenging multi-modal segmentation of MRI scans (4D) of brain tumor patients. Promising results are obtained for image partition into the different healthy brain tissues and the malignant regions.

Tammy Riklin Raviv

Local Mean Multiphase Segmentation with HMMF Models

This paper presents two similar multiphase segmentation methods for recovery of segments in complex weakly structured images, with local and global bias fields, because they can occur in some X-ray CT imaging modalities. Derived from the Mumford-Shah functional, the proposed methods assume a fixed number of classes. They use local image average as discriminative features. Region labels are modelled by Hidden Markov Measure Field Models. The resulting problems are solved by straightforward alternate minimisation methods, particularly simple in the case of quadratic regularisation of the labels. We demonstrate the proposed methods’ capabilities on synthetic data using classical segmentation criteria as well as criteria specific to geoscience. We also present a few examples using real data.

Jacob Daniel Kirstejn Hansen, François Lauze

An Efficient Lagrangian Algorithm for an Anisotropic Geodesic Active Contour Model

We propose an efficient algorithm to minimize an anisotropic surface energy generalizing the Geodesic Active Contour model for image segmentation. In this energy, the weight function may depend on the normal of the curve/surface. Our algorithm is Lagrangian, but nonparametric. We only use the node and connectivity information for computations. Our approach provides a flexible scheme, in the sense that it allows to easily incorporate the generalized gradients proposed recently, especially those based on the $$H^1$$ scalar product on the surface. However, unlike these approaches, our scheme is applicable in any number of dimensions, such as surfaces in 3d or 4d, and allows weighted $$H^1$$ scalar products, with weights may depending on the normal and the curvature. We derive the second shape derivative of the anisotropic surface energy, and use it as the basis for a new weighted $$H^1$$ scalar product. In this way, we obtain a Newton-type method that not only gives smoother flows, but also converges in fewer iterations and much shorter time.

Günay Doğan

A Probabilistic Framework for Curve Evolution

In this work, we propose a nonparametric probabilistic framework for image segmentation using deformable models. We estimate an underlying probability distributions of image features from regions defined by a deformable curve. We then evolve the curve such that the distance between the distributions is increasing. The resulting active contour resembles a well studied piecewise constant Mumford-Shah model, but in a probabilistic setting. An important property of our framework is that it does not require a particular type of distributions in different image regions. Additional advantages of our approach include ability to handle textured images, simple generalization to multiple regions, and efficiency in computation. We test our probabilistic framework in combination with parametric (snakes) and geometric (level-sets) curves. The experimental results on composed and natural images demonstrate excellent properties of our framework.

Vedrana Andersen Dahl, Anders Bjorholm Dahl

Convex and Non-convex Modeling and Optimization in Imaging

Frontmatter

Denoising of Image Gradients and Constrained Total Generalized Variation

We derive a denoising method that uses higher order derivative information. Our method is motivated by work on denoising of normal vectors to the image which then are used for a better denoising of the image itself. We propose to denoise image gradients instead of image normals, since this leads to a convex optimization problem. We show how the denoising of the image gradient and the image itself can be done simultaneously in one optimization problem. It turns out that the resulting problem is similar to total generalized variation denoising, thus shedding more light on the motivation of the total generalized variation penalties. Our approach, however, works with constraints, rather than penalty functionals. As a consequence, there is a natural way to choose one of the parameters of the problems and we motivate a choice rule for the second involved parameter.

Birgit Komander, Dirk A. Lorenz

Infimal Convolution Coupling of First and Second Order Differences on Manifold-Valued Images

Recently infimal convolution type functions were used in regularization terms of variational models for restoring and decomposing images. This is the first attempt to generalize the infimal convolution of first and second order differences to manifold-valued images. We propose both an extrinsic and an intrinsic approach. Our focus is on the second one since the summands arising in the infimal convolution lie on the manifold themselves and not in the higher dimensional embedding space. We demonstrate by numerical examples that the approach works well on the circle, the 2-sphere, the rotation group, and the manifold of positive definite matrices with the affine invariant metric.

Ronny Bergmann, Jan Henrik Fitschen, Johannes Persch, Gabriele Steidl

Optimal Transport for Manifold-Valued Images

We introduce optimal transport-type distances for manifold-valued images. To do so we lift the initial data to measures on the product space of image domain and signal space, where they can then be compared by optimal transport with a transport cost that combines spatial distance and signal discrepancy. Applying recently introduced ‘unbalanced’ optimal transport models leads to more natural results. We illustrate the benefit of the lifting with numerical examples for interpolation of color images and classification of handwritten digits.

Jan Henrik Fitschen, Friederike Laus, Bernhard Schmitzer

Time Discrete Extrapolation in a Riemannian Space of Images

The Riemannian metamorphosis model introduced and analyzed in [7, 12] is taken into account to develop an image extrapolation tool in the space of images. To this end, the variational time discretization for the geodesic interpolation proposed in [2] is picked up to define a discrete exponential map. For a given weakly differentiable initial image and a sufficiently small initial image variation it is shown how to compute a discrete geodesic extrapolation path in the space of images. The resulting discrete paths are indeed local minimizers of the corresponding discrete path energy. A spatial Galerkin discretization with cubic splines on coarse meshes for image deformations and piecewise bilinear finite elements on fine meshes for image intensity functions is used to derive a fully practical algorithm. The method is applied to real images and image variations recorded with a digital camera.

Alexander Effland, Martin Rumpf, Florian Schäfer

On a Projected Weiszfeld Algorithm

Weiszfeld’s method provides an efficient way for computing the weighted median of anchor points $$p_j \in {\mathbb {R}}^n$$, $$j=1,\ldots ,M$$, i.e., the minimizer of $$\sum _{j=1}^M w_j \Vert x-p_j\Vert _2$$. In certain applications as in unmixing problems it may be required that x lies in addition in a specific set. In other words we have to deal with a constrained median problem. In this paper we are concerned with closed convex sets lying in a hyperplane of $${\mathbb {R}}^n$$ as e.g., the linearly transformed probability simplex. We propose a projected version of the Weiszfeld algorithm to find the minimizer of the constrained median problem and prove the convergence of the algorithm. Here the main contribution is the appropriate handling of iterates taking values in the set of anchor points. A first artificial example shows that the model produces promising results in the presence of different kinds of noise.

Sebastian Neumayer, Max Nimmer, Gabriele Steidl, Henrike Stephani

A Unified Framework for the Restoration of Images Corrupted by Additive White Noise

We propose a robust variational model for the restoration of images corrupted by blur and the general class of additive white noises. The solution of the non-trivial optimization problem, due to the non-smooth non-convex proposed model, is efficiently obtained by an Alternating Directions Method of Multipliers (ADMM), which in particular reduces the solution to a sequence of convex optimization sub-problems. Numerical results show the potentiality of the proposed model for restoring blurred images corrupted by several kinds of additive white noises.

Alessandro Lanza, Federica Sciacchitano, Serena Morigi, Fiorella Sgallari

Learning Filter Functions in Regularisers by Minimising Quotients

Learning approaches have recently become very popular in the field of inverse problems. A large variety of methods has been established in recent years, ranging from bi-level learning to high-dimensional machine learning techniques. Most learning approaches, however, only aim at fitting parametrised models to favourable training data whilst ignoring misfit training data completely. In this paper, we follow up on the idea of learning parametrised regularisation functions by quotient minimisation as established in [3]. We extend the model therein to include higher-dimensional filter functions to be learned and allow for fit- and misfit-training data consisting of multiple functions. We first present results resembling behaviour of well-established derivative-based sparse regularisers like total variation or higher-order total variation in one-dimension. Our second and main contribution is the introduction of novel families of non-derivative-based regularisers. This is accomplished by learning favourable scales and geometric properties while at the same time avoiding unfavourable ones.

Martin Benning, Guy Gilboa, Joana Sarah Grah, Carola-Bibiane Schönlieb

Bregman-Proximal Augmented Lagrangian Approach to Multiphase Image Segmentation

This work studies the optimization problem of assigning multiple labels with the minimum perimeter, namely Potts model, in the spatially continuous setting. It was extensively studied within recent years and used to many different applications of image processing and computer vision, especially image segmentation. The existing convex relaxation approaches use total-variation functionals directly encoding perimeter costs, which result in pixelwise simplex constrained optimization problems and can be efficiently solved under a primal-dual perspective in numerics. Among most efficient approaches, such challenging simplex constraints are tackled either by extra projection steps to the simplex set at each pixel, which requires intensive simplex-projection computations, or by introducing extra dual variables resulting in the dual optimization-based continuous max-flow formulation to the studied convex relaxed Potts model. However, dealing with such extra dual flow variables needs additional loads in both computation and memory; particularly for the cases with many labels. To this end, we propose a novel optimization approach upon the Bregman-Proximal Augmented Lagrangian Method (BPALM), for which the Bregman distance function, instead of the classical quadratic Euclidean distance function, is integrated in the algorithmic framework of Augmented Lagrangian Methods. The new optimization method has significant numerical advantages; it naturally avoids extra computational and memory burden in enforcing the simplex constraints and allows parallel computations over different labels. Numerical experiments show competitive performance in terms of quality and significantly reduced memory load compared to the state-of-the-art convex optimization methods for the convex relaxed Potts model.

Jing Yuan, Ke Yin, Yi-Guang Bai, Xiang-Chu Feng, Xue-Cheng Tai

Optical Flow, Motion Estimation and Registration

Frontmatter

A Comparison of Isotropic and Anisotropic Second Order Regularisers for Optical Flow

In variational optical flow estimation, second order regularisation plays an important role, since it offers advantages in the context of non-fronto-parallel motion. However, in contrast to first order smoothness constraints, most second order regularisers are limited to isotropic concepts. Moreover, the few existing anisotropic concepts are lacking a comparison so far. Hence, our contribution is twofold. (i) First, we juxtapose general concepts for isotropic and anisotropic second order regularization based on direct second order methods, infimal convolution techniques, and indirect coupling models. For all the aforementioned strategies suitable optical flow regularisers are derived. (ii) Second, we show that modelling anisotropic second order smoothness terms gives an additional degree of freedom when penalising deviations from smoothness. This in turn allows us to propose a novel anisotropic strategy which we call double anisotropic regularisation. Experiments on the two KITTI benchmarks show the qualitative differences between the different strategies. Moreover, they demonstrate that the novel concept of double anisotropic regularisation is able to produce excellent results.

Daniel Maurer, Michael Stoll, Sebastian Volz, Patrick Gairing, Andrés Bruhn

Order-Adaptive Regularisation for Variational Optical Flow: Global, Local and in Between

Recent approaches for variational motion estimation typically either rely on first or second order regularisation strategies. While first order strategies are more appropriate for scenes with fronto-parallel motion, second order constraints are superior if it comes to the estimation of affine flow fields. Since using the wrong regularisation order may lead to a significant deterioration of the results, it is surprising that there has not been much effort in the literature so far to determine this order automatically. In our work, we address the aforementioned problem in two ways. (i) First, we discuss two anisotropic smoothness terms of first and second order, respectively, that share important structural properties and that are thus particularly suited for being combined within an order-adaptive variational framework. (ii) Secondly, based on these two smoothness terms, we develop four different variational methods and with it four different strategies for adaptively selecting the regularisation order: a global and a local strategy based on half-quadratic regularisation, a non-local approach that relies on neighbourhood information, and a region based method using level sets. Experiments on recent benchmarks show the benefits of each of the strategies. Moreover, they demonstrate that adaptively combining different regularisation orders not only allows to outperform single-order strategies but also to obtain advantages beyond the ones of a frame-wise selection.

Daniel Maurer, Michael Stoll, Andrés Bruhn

Transport Based Image Morphing with Intensity Modulation

We present a generalized optimal transport model in which the mass-preserving constraint for the $$L^2$$-Wasserstein distance is relaxed by introducing a source term in the continuity equation. The source term is also incorporated in the path energy by means of its squared $$L^2$$-norm in time of a functional with linear growth in space. This extension of the original transport model enables local density modulations, which is a desirable feature in applications such as image warping and blending. A key advantage of the use of a functional with linear growth in space is that it allows for singular sources and sinks, which can be supported on points or lines. On a technical level, the $$L^2$$-norm in time ensures a disintegration of the source in time, which we use to obtain the well-posedness of the model and the existence of geodesic paths. The numerical discretization is based on the proximal splitting approach [18] and selected numerical test cases show the potential of the proposed approach. Furthermore, the approach is applied to the warping and blending of textures.

Jan Maas, Martin Rumpf, Stefan Simon

Vehicle X-ray Scans Registration: A One-Dimensional Optimization Problem

Over the years, image registration has been largely employed in medical applications, robotics and geophysics. More recently, it has increasingly drawn attention of security and defense industries, particularly aiming at threat detection automation. This paper first introduces a short overview of mathematical methods for image registration, with a focus on variational approaches. In a second part, a specific registration task is presented: the optimal alignment between X-ray scans of an inspected vehicle and an empty reference of the same car model. Indeed, while being scanned by dedicated imaging systems, the car speed is not necessarily constant which may entail non-rigid deformations in the resulting image. The paper simply addresses this issue by applying a rigid transform on the reference image before using the variational framework solved in one dimension. For convergence and speed purposes, line-search techniques and a multiscale approach are used.

Abraham Marciano, Laurent D. Cohen, Najib Gadi

Evaluating Data Terms for Variational Multi-frame Super-Resolution

We present the first systematic evaluation of the data terms for multi-frame super-resolution within a variational model. The various data terms are derived by permuting the order of the blur-, downsample-, and warp-operators in the image acquisition model. This yields six different basic models. Our experiments using synthetic images with known ground truth show that two models are preferable: the widely-used warp-blur-downsample model that is physically plausible if atmospheric blur is negligible, and the hardly considered blur-warp-downsample model. We show that the quality of motion estimation plays the decisive role on which of these two models works best: While the classic warp-blur-downsample model requires optimal motion estimation, the rarely-used blur-warp-downsample model should be preferred in practically relevant scenarios when motion estimation is suboptimal. This confirms a widely ignored result by Wang and Qi (2004). Last but not least, we propose a new modification of the blur-warp-downsample model that offers a very significant speed-up without substantial loss in the reconstruction quality.

Kireeti Bodduna, Joachim Weickert

Compressed Motion Sensing

We consider the problem of sparse signal recovery in dynamic sensing scenarios. Specifically, we study the recovery of a sparse time-varying signal from linear measurements of a single static sensor that are taken at two different points in time. This setup can be modelled as observing a single signal using two different sensors – a real one and a virtual one induced by signal motion, and we examine the recovery properties of the resulting combined sensor. We show that not only can the signal be uniquely recovered with overwhelming probability by linear programming, but also the correspondence of signal values (signal motion) can be established between the two points in time. In particular, we show that in our scenario the performance of an undersampling static sensor is doubled or, equivalently, that the number of sufficient measurements of a static sensor is halved.

Robert Dalitz, Stefania Petra, Christoph Schnörr

A Unified Hyperelastic Joint Segmentation/Registration Model Based on Weighted Total Variation and Nonlocal Shape Descriptors

In this paper, we address the issue of designing a unified variational model for joint segmentation and registration in which the shapes to be matched are viewed as hyperelastic materials, and more precisely, as Saint Venant-Kirchhoff ones. The dissimilarity measure relates local and global (or region-based) information, since relying on weighted total variation and on a nonlocal shape descriptor inspired by the Chan-Vese model for segmentation. Theoretical results emphasizing the mathematical and practical soundness of the model are provided, among which relaxation, existence of minimizers, analysis of two numerical methods of resolution, asymptotic results and a $$\varGamma $$-convergence property.

Noémie Debroux, Carole Le Guyader

3D Vision

Frontmatter

Adaptive Discretizations for Non-smooth Variational Vision

Variational problems in vision are solved numerically on the pixel lattice because it provides the simplest computational grid to discretize the input images, even though a uniform grid seldom matches the complexity of the solution. To adapt the complexity of the discretization to the solution, it is necessary to adopt finite-element techniques that match the resolution of piecewise polynomial bases to the resolving power of the variational model, but such techniques have been overlooked for nonsmooth variational models. To address this issue, we investigate the pros and cons of finite-element discretizations for nonsmooth variational problems in vision, their multiresolution properties, and the optimization algorithms to solve them. Our 2 and 3D experiments in image segmentation, optical flow, stereo, and depth fusion reveal the conditions where finite-element can outperform finite-difference discretizations by achieving significant computational savings with a minor loss of accuracy.

Virginia Estellers, Stefano Soatto

The Hessian of Axially Symmetric Functions on SE(3) and Application in 3D Image Analysis

We propose a method for computation of the Hessian of axially symmetric functions on the roto-translation group SE(3). Eigendecomposition of the resulting Hessian is then used for curvature estimation of tubular structures, similar to how the Hessian matrix of 2D or 3D image data can be used for orientation estimation. This paper focuses on a new implementation of a Gaussian regularized Hessian on the roto-translation group. Furthermore we show how eigenanalysis of this Hessian gives rise to exponential curve fits on data on position and orientation (e.g. orientation scores), whose spatial projections provide local fits in 3D data. We quantitatively validate our exponential curve fits by comparing the curvature of the spatially projected fitted curve to ground truth curvature of artificial 3D data. We also show first results on real MRA data. Implementations are available at: http://lieanalysis.nl/orientationscores.html.

Michiel H. J. Janssen, Tom C. J. Dela Haije, Frank C. Martin, Erik J. Bekkers, Remco Duits

Semi-calibrated Near-Light Photometric Stereo

We tackle the nonlinear problem of photometric stereo under close-range pointwise sources, when the intensities of the sources are unknown (so-called semi-calibrated setup). A variational approach aiming at robust joint recovery of depth, albedo and intensities is proposed. The resulting nonconvex model is numerically resolved by a provably convergent alternating minimization scheme, where the construction of each subproblem utilizes an iteratively reweighted least-squares approach. In particular, manifold optimization technique is used in solving the corresponding subproblems over the rank-1 matrix manifold. Experiments on real-world datasets demonstrate that the new approach provides not only theoretical guarantees on convergence, but also more accurate geometry.

Yvain Quéau, Tao Wu, Daniel Cremers

Shape Matching by Time Integration of Partial Differential Equations

The main task in three dimensional shape matching is to retrieve correspondences between two similar three dimensional objects. To this end, a suitable point descriptor which is invariant under isometric transformations is required. A commonly used descriptor class relies on the spectral decomposition of the Laplace-Beltrami operator. Important examples are the heat kernel signature and the more recent wave kernel signature. In previous works, the evaluation of the descriptor is based on eigenfunction expansions. Thereby a significant practical aspect is that computing a complete expansion is very time and memory consuming. Thus additional strategies are usually introduced that enable to employ only part of the full expansion.In this paper we explore an alternative solution strategy. We discretise the underlying partial differential equations (PDEs) not only in space as in the mentioned approaches, but we also tackle temporal parts by using time integration methods. Thus we do not perform eigenfunction expansions and avoid the use of additional strategies and corresponding parameters. We study here the PDEs behind the heat and wave kernel signature, respectively. Our shape matching experiments show that our approach may lead to quality improvements for finding correct correspondences in comparison to the eigenfunction expansion methods.

Robert Dachsel, Michael Breuß, Laurent Hoeltgen

Subspace Least Squares Multidimensional Scaling

Multidimensional Scaling (MDS) is one of the most popular methods for dimensionality reduction and visualization of high dimensional data. Apart from these tasks, it also found applications in the field of geometry processing for the analysis and reconstruction of non-rigid shapes. In this regard, MDS can be thought of as a shape from metric algorithm, consisting of finding a configuration of points in the Euclidean space that realize, as isometrically as possible, some given distance structure. In the present work we cast the least squares variant of MDS (LS-MDS) in the spectral domain. This uncovers a multiresolution property of distance scaling which speeds up the optimization by a significant amount, while producing comparable, and sometimes even better, embeddings.

Amit Boyarski, Alex M. Bronstein, Michael M. Bronstein

Beyond Multi-view Stereo: Shading-Reflectance Decomposition

We introduce a variational framework for separating shading and reflectance from a series of images acquired under different angles, when the geometry has already been estimated by multi-view stereo. Our formulation uses an $$l^1$$-TV variational framework, where a robust photometric-based data term enforces adequation to the images, total variation ensures piecewise-smoothness of the reflectance, and an additional multi-view consistency term is introduced for resolving the arising ambiguities. Optimisation is carried out using an alternating optimisation strategy building upon iteratively reweighted least-squares. Preliminary results on both a synthetic dataset, using various lighting and reflectance scenarios, and a real dataset, confirm the potential of the proposed approach.

Jean Mélou, Yvain Quéau, Jean-Denis Durou, Fabien Castan, Daniel Cremers

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise