Abstract. Homogeneous diffusion inpainting can reconstruct missing image areas with high quality from a sparse subset of known pixels, provided that their location as well as their gray or color values are well optimized. This property is exploited in inpainting-based image compression, which is a promising alternative to classical transform-based codecs such as JPEG and JPEG2000. However, optimizing the inpainting data is a challenging task. Current approaches are either fairly slow or do not produce high quality results. As a remedy we propose fast spatial and tonal optimization algorithms for homogeneous diffusion inpainting that efficiently utilize GPU parallelism, with a careful adaptation of some of the most successful numerical concepts. We propose a densification strategy using ideas from error-map dithering combined with a Delaunay triangulation for the spatial optimization. For the tonal optimization we design a domain decomposition solver that solves the corresponding normal equations in a matrix-free fashion and supplement it with a Voronoi-based initialization strategy. With our proposed methods we are able to generate high quality inpainting masks for homogeneous diffusion and optimized tonal values in a runtime that outperforms prior state-of-the-art by a wide margin.

Deep learning has revolutionized the field of computer vision by introducing large scale neural networks with millions of parameters. Training these networks requires massive datasets and leads to intransparent models that can fail to generalize. At the other extreme, models designed from partial differential equations (PDEs) embed specialized domain knowledge into mathematical equations and usually rely on few manually chosen hyperparameters. This makes them transparent by construction and if designed and calibrated carefully, they can generalize well to unseen scenarios. In this paper, we show how to bring model- and data-driven approaches together by combining the explicit PDE-based approaches with convolutional neural networks to obtain the best of both worlds. We illustrate a joint architecture for the task of inpainting optical flow fields and show that the combination of model- and data-driven modeling leads to an effective architecture. Our model outperforms both fully explicit and fully data-driven baselines in terms of reconstruction quality, robustness and amount of required training data. Averaging the endpoint error across different mask densities, our method outperforms the explicit baselines by 11-27%, the GAN baseline by 47% and the Probabilisitic Diffusion baseline by 42%. With that, our method sets a new state of the art for inpainting of optical flow fields from random masks.

Inpainting-based image compression is a promising alternative to classical transform-based lossy codecs. Typically it stores a carefully selected subset of all pixel locations and their colour values. In the decoding phase the missing information is reconstructed by an inpainting process such as homogeneous diffusion inpainting. Optimising the stored data is the key for achieving good performance. A few heuristic approaches also advocate alternative feature types such as derivative data and construct dedicated inpainting concepts. However, one still lacks a general approach that allows to optimise and inpaint the data simultaneously w.r.t. a collection of different feature types, their locations, and their values. Our paper closes this gap. We introduce a generalised inpainting process that can handle arbitrary features which can be expressed as linear equality constraints. This includes e.g. colour values and derivatives of any order. We propose a fully automatic algorithm that aims at finding the optimal features from a given collection as well as their locations and their function values within a specified total feature density. Its performance is demonstrated with a novel set of features that also includes local averages. Our experiments show that it clearly outperforms the popular inpainting with optimised colour data with the same density.

Abstract Diffusion-based inpainting can reconstruct missing image areas with high quality from sparse data, provided that their location and their values are well optimised. This is particularly useful for applications such as image compression, where the original image is known. Selecting the known data constitutes a challenging optimisation problem, that has so far been only investigated with model-based approaches. So far, these methods require a choice between either high quality or high speed since qualitatively convincing algorithms rely on many time-consuming inpaintings. We propose the first neural network architecture that allows fast optimisation of pixel positions and pixel values for homogeneous diffusion inpainting. During training, we combine two optimisation networks with a neural network-based surrogate solver for diffusion inpainting. This novel concept allows us to perform backpropagation based on inpainting results that approximate the solution of the inpainting equation. Without the need for a single inpainting during test time, our deep optimisation accelerates data selection by more than four orders of magnitude compared to common model-based approaches. This provides real-time performance with high quality results.

Inpainting-based compression methods are qualitatively promising alternatives to transform-based codecs, but they suffer from the high computational cost of the inpainting step. This prevents them from being applicable to time-critical scenarios such as real-time inpainting of 4K images. As a remedy, we adapt state-of-the-art numerical algorithms of domain decomposition type to this problem. They decompose the image domain into multiple overlapping blocks that can be inpainted in parallel by means of modern GPUs. In contrast to classical block decompositions such as the ones in JPEG, the global inpainting problem is solved without creating block artefacts. We consider the popular homogeneous diffusion inpainting and supplement it with a multilevel version of an optimised restricted additive Schwarz (ORAS) method that solves the local problems with a conjugate gradient algorithm. This enables us to perform real-time in-painting of 4K colour images on contemporary GPUs, which is substantially more efficient than previous algorithms for diffusion-based inpainting.

We introduce an integrodifferential extension of the edge-enhancing anisotropic diffusion model for image denoising. By accumulating weighted structural information on multiple scales, our model is the first to create anisotropy through multiscale integration. It follows the philosophy of combining the advantages of model-based and data-driven approaches within compact, insightful, and mathematically well-founded models with improved performance. We explore trained results of scale-adaptive weighting and contrast parameters to obtain an explicit modelling by smooth functions. This leads to a transparent model with only three parameters, without significantly decreasing its denoising performance. Experiments demonstrate that it outperforms its diffusion-based predecessors. We show that both multiscale information and anisotropy are crucial for its success.

Inpainting-based image compression is emerging as a promising competitor to transform-based compression techniques. Its key idea is to reconstruct image information from only few known regions through inpainting. Specific partial differential equations (PDEs) such as edge-enhancing diffusion (EED) give high quality reconstructions of image structures with low or medium texture. Even though the strengths of PDE-and transform-based compression are complementary, they have rarely been combined within a hybrid codec. We propose to sparsify blocks of a JPEG compressed image and reconstruct them with EED inpainting. Our codec consistently outperforms JPEG and gives useful indications for successfully developing hybrid codecs further. Furthermore, our method is the first to choose regions rather than pixels as known data for PDE-based compression. It also gives novel insights into the importance of corner regions for EED-based codecs.

Digital image inpainting refers to techniques used to reconstruct a damaged or incomplete image by exploiting available image information. The main goal of this work is to perform the image inpainting process from a set of sparsely distributed image samples with the smoothed particle hydrodynamics (SPH) technique. Because, in its naive formulation, the SPH technique is not even capable of reproducing constant functions, we modify the approach to obtain an approximation which can reproduce constant and linear functions. Furthermore, we examine the use of Voronoi tessellation for defining the necessary parameters in the SPH method as well as selecting optimally located image samples. In addition to this spatial optimization, optimization of data values is also implemented in order to further improve the results. Apart from a traditional Gaussian smoothing kernel, we assess the performance of other kernels on both random and spatially optimized masks. Since the use of isotropic smoothing kernels is not optimal in the presence of objects with a clear preferred orientation in the image, we also examine anisotropic smoothing kernels. Our final algorithm can compete with well-performing sparse inpainting techniques based on homogeneous or anisotropic diffusion processes as well as with exemplar-based approaches.

The rise of machine learning in image processing has created a gap between trainable data-driven and classical model- driven approaches: While learning-based models often show superior performance, classical ones are often more transparent. To reduce this gap, we introduce a generic wavelet shrinkage function for denoising which is adaptive to both the wavelet scales as well as the noise standard deviation. It is inferred from trained results of a tightly parametrised function which is inherited from nonlinear diffusion. Our proposed shrinkage function is smooth and compact while only using two parameters. In contrast to many existing shrinkage functions, it is able to enhance image structures by amplifying wavelet coefficients. Experiments show that it outperforms classical shrinkage functions by a significant margin.

In spite of the fact that efficient compression methods for dense two-dimensional flow fields would be very useful for modern video codecs, hardly any research has been performed in this area so far. Our paper addresses this problem by proposing the first lossy diffusion-based codec for this purpose. It keeps only a few flow vectors on a coarse grid. Additionally stored edge locations ensure the accurate representation of discontinuities. In the decoding step, the missing information is recovered by homogeneous diffusion inpainting that incorporates the stored edges as reflecting boundary conditions. In spite of the simple nature of this codec, our experiments show that it achieves remarkable quality for compression ratios up to 800:1.

We propose a light-weight variational framework for online tracking of object segmentations in videos based on optical flow and image boundaries. While high-end computer vision methods on this task rely on sequence specific training of dedicated CNN architectures, we show the potential of a variational model, based on generic video information from motion and color. Such cues are usually required for tasks such as robot navigation or grasp estimation. We leverage them directly for video object segmentation and thus provide accurate segmentations at potentially very low extra cost. Our simple method can provide competitive results compared to the costly CNN-based methods with parameter tuning. Furthermore, we show that our approach can be combined with state-of-the-art CNN-based segmentations in order to improve over their respective results. We evaluate our method on the datasets DAVIS16,17 and SegTrack v2.

The 3D block matching (BM3D) method is among the state-of-art methods for denoising images corrupted with additive white Gaussian noise. With the help of a novel inter-frame connectivity strategy, we propose an extension of the BM3D method for the scenario where we have multiple images of the same scene. Our proposed extension outperforms all the existing trivial and non-trivial extensions of patch-based denoising methods for multi-frame images. We can achieve a quality difference of as high as 28% over the next best method without using any additional parameters. Our method can also be easily generalised to other similar existing patch-based methods.

Inpainting techniques based on partial differential equations (PDEs), such as diffusion processes, are gaining growing importance as a novel family of image compression methods. Nevertheless, the application of inpainting in the field of hyperspectral imagery has been mainly focused on filling in missing information or dead pixels due to sensor failures. In this letter, we propose a novel PDE-based inpainting algorithm to compress hyperspectral images. The method inpaints separately the known data in the spatial and spectral dimensions. Then, it applies a prediction model to the final inpainting solution to obtain a representation much closer to the original image. Experimental results over a set of hyperspectral images indicate that the proposed algorithm can perform better than a recent proposed extension to prediction-based standard CCSDS-123.0 at low bit rate, better than JPEG 2000 Part 2 with the DWT 9/7 as a spectral transform at all bit rates, and competitive to JPEG 2000 with principal component analysis, the optimal spectral decorrelation transform for Gaussian sources.

The work of Levin et al. (2004) popularized stroke-based methods that add color to gray value images according to a small amount of user-specified color samples. Even though such reconstructions from sparse data suggest a possible use in compression, only few attempts were made so far in this direction. Diffusion-based compression methods pursue a similar idea: they store only few image pixels and inpaint the missing regions. Despite this close relation and a lack of diffusion-based color codecs, colorization ideas were so far only integrated into transform-based approaches such as JPEG. We address this missing link with two contributions. First, we show the relation between the discrete colorization of Levin et al. and continuous diffusion-based inpainting in the YCbCr color space. It decomposes the image into a luma (brightness) channel and two chroma (color) channels. Our luma-guided diffusion framework steers the diffusion inpainting in the chroma channels according to the structure in the luma channel. We show that making the luma-guided colorization anisotropic outperforms the method of Levin et al. significantly. Second, we propose a new luma preference codec that invests a large fraction of the bit budget into an accurate representation of the luma channel. This allows a high-quality reconstruction of color data with our colorization technique. Simultaneously, we exploit the fact that the human visual system is more sensitive to structural than to color information. Our experiments demonstrate that our new codec outperforms the state of the art in diffusion-based image compression and is competitive to transform-based codecs.

In image compression, codecs that rely on interpolation with partial differential equations (PDEs) are becoming increasingly popular. However, there have not been many attempts to transfer this concept to video compression. Since real-time performance is challenging for PDE-based reconstruction, first efficient approaches work on a frame-by-frame basis and focus on parallel implementations without considering coding quality. So far, there is no fully PDE-based video codec that exploits temporal redundancies. As a remedy, we propose a modular framework that combines PDE-based compression with motion compensation: Intra frames are predicted with PDE-based inpainting and inter frames with dense optic flow fields. We use this framework to develop a proof-of-concept codec that combines homogeneous diffusion inpainting with the variational optic flow model of Brox et al. (2004). Even without sophisticated parallelisation, we are able to perform real-time decompression of colour videos for the first time in PDE-based video compression.

Abstract In this paper, we present a general variational method for image fusion. In particular, we combine different images of the same subject to a single composite that offers optimal exposedness, saturation and local contrast. Previous research approaches this task by first pre‐computing application‐specific weights based on the input, and then combining these weights with the images to the final composite later on. In contrast, we design our model assumptions directly on the fusion result. To this end, we formulate the output image as a convex combination of the input and incorporate concepts from perceptually inspired contrast enhancement such as a local and non‐linear response. This output‐driven approach is the key to the versatility of our general image fusion model. In this regard, we demonstrate the performance of our fusion scheme with several applications such as exposure fusion, multispectral imaging and decolourization. For all application domains, we conduct thorough validations that illustrate the improvements compared to state‐of‐the‐art approaches that are tailored to the individual tasks.

Schmaltz et al. (2009) have shown that for reasonably high compression rates, diffusion-based codecs can exceed the quality of transformation-based methods such as JPEG 2000. They store only data at a few optimised pixel locations and in-paint missing data with edge-enhancing anisotropic diffusion (EED). However, research on compression with diffusion methods has mainly focussed on grey-value images, and colour images have been compressed in a straightforward way using anisotropic diffusion in RGB space. So far, there is no sophisticated diffusion-based counterpart to the colour mode of JPEG 2000. To address this shortcoming we introduce an advanced colour compression codec that exploits properties of the human visual system in YCbCr space. Since details in the luma channel Y are perceptually relevant, we invest a large fraction of our bit budget in its encoding with high fidelity. For the chroma channels Cb and Cr, the stored information can be very sparse, if we guide the EED-based inpainting with the high quality diffusion tensor from the luma reconstruction. Experiments demonstrate that our novel codec outperforms JPEG 2000 and compression with RGB-diffusion, both visually and quantitatively.

Camera shakes and moving objects pose a severe problem in the high dynamic range (HDR) reconstruction from differently exposed images. We present the first approach that simultaneously computes the aligned HDR composite as well as accurate displacement maps. In this way, we can not only cope with dynamic scenes but even precisely represent the underlying motion. We design our fully coupled model transparently in a well-founded variational framework. The proposed joint optimisation has beneficial effects, such as intrinsic ghost removal or HDR-coupled smoothing. Both the HDR images and the optic flows benefit substantially from these features and the induced mutual feedback. We demonstrate this with synthetic and real-world experiments.

Abstract The problem of reconstructing a watertight surface from a finite set of oriented points has received much attention over the last decades. In this paper, we propose a general higher order framework for surface reconstruction. It is based on the idea that position and normal defined by each oriented point can be used to construct an implicit local description of the unknown surface. On the one hand, this allows us to systematically explain and relate several popular methods, for example implicit moving least squares, smooth signed distance surface reconstruction as well as (screened) Poisson surface reconstruction. On the other hand, it allows to derive and discuss a number of new approaches for reconstructing either the signed distance or the indicator function of the sought object. All of these approaches are able to achieve competitive results but one of them turns out to be especially promising. To improve reconstructions in difficult real world scenarios where point clouds have been estimated from colour images, we introduce a hull constraint that encourages the surface to stay within a given region. Our framework is implemented on the GPU using a recent cyclic scheme called Fast Jacobi, which combines low implementational effort with high efficiency.

Most researchers agree that invariances are desirable in computer vision systems. However, one always has to keep in mind that this is at the expense of accuracy: By construction, all invariances inevitably discard information. The concept of morphological invariance is a good example for this trade-off and will be in the focus of this paper. Our goal is to develop a descriptor of local image structure that carries the maximally possible amount of local image information under this invariance. To fulfill this requirement, our descriptor has to encode the full ordering of the pixel intensities in the local neighbourhood. As a solution, we introduce the complete rank transform, which stores the intensity rank of every pixel in the local patch. As a proof of concept, we embed our novel descriptor in a prototypical TV−L1-type energy functional for optical flow computation, which we minimise with a traditional coarse-to-fine warping scheme. In this straightforward framework, we demonstrate that our descriptor is preferable over related features that exhibit the same invariance. Finally, we show by means of public benchmark systems that our method produces in spite of its simplicity results of competitive quality.

The reliable estimation of the Lagrangian stress tensor from an image sequence is a challenging problem in mechanical engineering. Since this tensor involves first order motion derivatives, it appears tempting to estimate the optical flow field with a highly accurate variational model and compute its derivatives afterwards. In this paper we explain why this idea is inappropriate due to lower order smoothness assumptions and the ill-posedness of differentiation. As a remedy, we propose a variational framework that performs higher order regularisation of the optical flow field and directly computes the Lagrangian stress tensor from the image measurements. Due to its recursive structure, this framework is very generic. It can incorporate smoothness assumptions of arbitrary high order and allows to compute derivatives of any desired order in a stable way. With a biaxial tensile experiment with an elastomer we demonstrate that our novel approach gives substantially better results for the Lagrangian stress tensor than computing derivatives of the optical flow field. Moreover, it also outperforms a frequently used commercial software that marks the state-of-the-art for Lagrangian stress tensor computation.

Algorithms based on partial differential equations (PDEs) constitute a relatively novel class of lossy image compression methods. In this paper we introduce a practically relevant extension: We demonstrate how to incorporate progressive modes into these codecs. Since the data in PDE-based codecs is only available at irregular locations, this is a challenging task. We propose two progressive modes: The first one changes the order in which the grey values are stored, while the second additionally distributes the stored information more evenly over the file. Our experiments show that the novel codecs can outperform JPEG and even JPEG 2000 for high compression ratios.

Abstract Electrostatic halftoning, a sampling algorithm based on electrostatic principles, is among the leading methods for stippling, dithering and sampling. However, this approach is only applicable for a single class of dots with a uniform size and colour. In our work, we complement these ideas by advanced features for real‐world applications. We propose a versatile framework for colour halftoning, hatching and multi‐class importance sampling with individual weights. Our novel approach is the first method that globally optimizes the distribution of different objects in varying sizes relative to multiple given density functions. The quality, versatility and adaptability of our approach is demonstrated in various experiments.

Abstract 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.

This paper proposes two alternative formulations to reduce the high computational complexity of tensor voting, a robust perceptual grouping technique used to extract salient information from noisy data. The first scheme consists of numerical approximations of the votes, which have been derived from an in-depth analysis of the plate and ball voting processes. The second scheme simplifies the formulation while keeping the same perceptual meaning of the original tensor voting: The stick tensor voting and the stick component of the plate tensor voting must reinforce surfaceness, the plate components of both the plate and ball tensor voting must boost curveness, whereas junctionness must be strengthened by the ball component of the ball tensor voting. Two new parameters have been proposed for the second formulation in order to control the potentially conflictive influence of the stick component of the plate vote and the ball component of the ball vote. Results show that the proposed formulations can be used in applications where efficiency is an issue since they have a complexity of order O(1). Moreover, the second proposed formulation has been shown to be more appropriate than the original tensor voting for estimating saliencies by appropriately setting the two new parameters.

Motivated by a recent halftoning method which is based on electrostatic principles, we analyze a halftoning framework where one minimizes a functional consisting of the difference of two convex functions. One describes attracting forces caused by the image's gray values; the other one enforces repulsion between points. In one dimension, the minimizers of our functional can be computed analytically and have the following desired properties: The points are pairwise distinct, lie within the image frame, and can be placed at grid points. In the two-dimensional setting, we prove some useful properties of our functional, such as its coercivity, and propose computing a minimizer by a forward-backward splitting algorithm. We suggest computing the special sums occurring in each iteration step of our dithering algorithm by a fast summation technique based on the fast Fourier transform at nonequispaced knots, which requires only $\mathcal{O}(m\log m)$ arithmetic operations for m points. Finally, we present numerical results showing the excellent performance of our dithering method.

Abstract We introduce a new global approach for image dithering, stippling, screening and sampling. It is inspired by the physical principles of electrostatics. Repelling forces between equally charged particles create a homogeneous distribution in flat areas, while attracting forces from the image brightness values ensure a high approximation quality. Our model is transparent and uses only two intuitive parameters: One steers the granularity of our halftoning approach, and the other its regularity. We evaluate two versions of our algorithm: A discrete version for dithering that ties points to grid positions, as well as a continuous one which does not have this restriction, and can thus be used for stippling or sampling density functions. Our methods create very few visual artefacts, reveal favourable blue‐noise behaviour in the frequency domain, and have a lower approximation error under Gaussian convolution than state‐of‐the‐art methods.

This work deals with modeling and markerless tracking of athletes interacting with sports gear. In contrast to classical markerless tracking, the interaction with sports gear comes along with joint movement restrictions due to additional constraints: while humans can generally use all their joints, interaction with the equipment imposes a coupling between certain joints. A cyclist who performs a cycling pattern is one example: The feet are supposed to stay on the pedals, which are again restricted to move along a circular trajectory in 3D-space. In this paper, we present a markerless motion capture system that takes the lower-dimensional pose manifold into account by modeling the motion restrictions via soft constraints during pose optimization. Experiments with two different models, a cyclist and a snowboarder, demonstrate the applicability of the method. Moreover, we present motion capture results for challenging outdoor scenes including shadows and strong illumination changes.

MOTIVATION: An approach for identifying similarities of protein-protein binding sites is presented. The geometric shape of a binding site is described by computing a feature vector based on moment invariants. In order to search for similarities, feature vectors of binding sites are compared. Similar feature vectors indicate binding sites with similar shapes. RESULTS: The approach is validated on a representative set of protein-protein binding sites, extracted from the SCOPPI database. When querying binding sites from a representative set, we search for known similarities among 2819 binding sites. A median area under the ROC curve of 0.98 is observed. For half of the queries, a similar binding site is identified among the first two of 2819 when sorting all binding sites according the proposed similarity measure. Typical examples identified by this method are analyzed and discussed. The nitrogenase iron protein-like SCOP family is clustered hierarchically according to the proposed similarity measure as a case study. AVAILABILITY: Python code is available on request from the authors.

The popularity of level sets for segmentation is mainly based on the sound and convenient treatment of regions and their boundaries. Unfortunately, this convenience is so far not known from level set methods when applied to images with more than two regions. This communication introduces a comparatively simple way how to extend active contours to multiple regions keeping the familiar quality of the two-phase case. We further suggest a strategy to determine the optimum number of regions as well as initializations for the contours.

Although variational methods are among the most accurate techniques for estimating the optical flow, they have not yet entered the field of real-time vision. Main reason is the great popularity of standard numerical schemes that are easy to implement, however, at the expense of being too slow for real-time performance. In our paper we address this problem in two ways: (i) we present an improved version of the highly accurate technique of Brox et al. (2004). Thereby we show that a separate robustification of the constancy assumptions is very useful, in particular if the I-norm is used as penalizer. As a result, a method is obtained that yields the lowest angular errors in the literature, (ii) We develop an efficient numerical scheme for the proposed approach that allows real-time performance for sequences of size 160 /spl times/ 720. To this end, we combine two hierarchical strategies: a coarse-to-fine warping strategy as implementation of a fixed point iteration for a non-convex optimisation problem and a nonlinear full multigrid method - a so called full approximation scheme (FAS) - for solving the highly nonlinear equation systems at each warping level. In the experimental section the advantage of the proposed approach becomes obvious: Outperforming standard numerical schemes by two orders of magnitude frame rates of six high quality flow fields per second are obtained on a 3.06 GHz Pentium4 PC.

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.

Udgivelsesdato: June

We propose an approach to the segmentation of video objects based on motion cues. Motion analysis is performed by estimating local orientations in the spatiotemporal domain using the three-dimensional structure tensor. These estimates are integrated as an external force into an active contour model, thus stopping the evolving curve when it reaches the moving object's boundary. To enable simultaneous detection of several objects, we reformulate the tensor-based active contour model using the level-set technique. In addition, a contour refinement technique has been developed to better approximate the real boundary of the moving object. We provide promising experimental results calculated on real-world video sequences widely used within the computer vision community.

This article investigates Renyi's (1976) generalized entropies under linear and nonlinear scale-space evolutions of images. Scale-spaces are useful computer vision concepts for both scale analysis and image restoration. We regard images as densities and prove monotony and smoothness properties for the generalized entropies. The scale-space extended generalized entropies are applied to global scale selection and size estimations. Finally, we introduce an entropy-based fingerprint description for textures.

In MR brain images, segmentation using intensity values is severely limited owing to field inhomogeneities, susceptibility artifacts and partial volume effects. Edge based segmentation methods suffer from spurious edges and gaps in boundaries. A method is presented which combines the advantages of edge based and region based segmentation. First a multiscale image representation, is constructed which favors intratissue diffusion over inter-tissue diffusion by exploiting local contrast. Subsequently a multiscale linking model (the hyperstack) is used to group voxels into a number of segments. This facilitates segmentation of grey matter, white matter and cerebrospinal fluid with minimal user interaction. Using a supervised segmentation, technique and MR simulations of a brain phantom as validation it is shown that the errors are in the order of or smaller than reported in literature.

The isophote curvature times the gradient magnitude to some power has been studied in the literature as a measure of cornerness in images, and stability in terms of sampling noise has been proposed by selecting corners in these measures at high scale and locating them at fine scale. We will examine the problem of tracking extrema of these measures in the linear scale-space and conclude that annihilations and creations generically occurs, so that corners in general cannot be tracked to arbitrarily fine/coarse scale. However, there are quantitatively differences, and the analysis indicates that isophote curvature times the gradient magnitude is best suited for binary images.

Nonlinear diffusion filtering in image processing is usually performed with explicit schemes. They are only stable for very small time steps, which leads to poor efficiency and limits their practical use. Based on a discrete nonlinear diffusion scale-space framework we present semi-implicit schemes which are stable for all time steps. These novel schemes use an additive operator splitting (AOS), which guarantees equal treatment of all coordinate axes. They can be implemented easily in arbitrary dimensions, have good rotational invariance and reveal a computational complexity and memory requirement which is linear in the number of pixels. Examples demonstrate that, under typical accuracy requirements, AOS schemes are at least ten times more efficient than the widely used explicit schemes.

In most cases nonlinear diffusion filtering is implemented by means of explicit finite difference schemes. These algorithms are not very efficient, since they are only stable for small time steps. We address this problem by presenting unconditionally stable semi-implicit schemes which are based on an additive operator splitting (AOS). They are very efficient since they can be implemented by recursive filtering, and their separability allows a straightforward implementation in any dimension. We analyse their behaviour on a parallel computer and demonstrate that parallel AOS schemes on a modern shared-memory multiprocessor system with 8 processors allow a speed-up of two orders of magnitude in comparison to the widely-used explicit scheme on a single processor.

Many image processing applications require one to solve problems such as denoising with edge enhancement, preprocessing for segmentation, or the completion of interrupted lines. This may be accomplished by applying a suitable nonlinear anisotropic diffusion process to the image. Its diffusion tensor is adapted to the differential structure of the underlying image. Although being image enhancement tools, filters of this class are well-posed. The temporal evolution of the diffusion process creates a scale-space whose causality properties can be understood in a deterministic, stochastic, information theory based and Fourier based way. The well-posedness and scale-space results carry over to the discrete setting, which gives rise to reliable algorithms preserving all properties of the continuous framework.