IPOLIPOLhttp://www.ipol.im/feed/IPOL Articles — Latest articles published in IPOL.ikiwiki2018-07-25T21:51:45ZAn Analysis and Implementation of Multigrid Poisson Solvers With Verified Linear
Complexityhttp://www.ipol.im/pub/art/2018/228/Matías Di Martino,
Gabriele Facciolo2018-07-25T21:51:45Z2018-07-25T22:00:00Z
The Poisson equation is the most studied partial differential equation, and it
allows to formulate many useful image processing methods in an elegant and efficient
mathematical framework. Using different variations of data terms and boundary conditions,
Poisson-like problems can be developed, e.g., for local contrast enhancement, inpainting, or
image seamless cloning among many other applications. Multigrid solvers are among the most
efficient numerical solvers for discrete Poisson-like equations. However, their correct
implementation relies on: (i) the proper definition of the discrete problem, (ii) the right
choice of interpolation and restriction operators, and (iii) the adequate
formulation of the problem across different scales and layers. In the present work we address
these aspects, and we provide a mathematical and practical description of multigrid methods. In
addition, we present an alternative to the extended formulation of Poisson equation
proposed in 2011 by Mainberger et al. The proposed formulation of the problem suits better
multigrid methods, in particular, because it has important mathematical properties that can be
exploited to define the problem at different scales in a intuitive and natural way. In
addition, common iterative solvers and Poisson-like problems are empirically analyzed and
compared. For example, the complexity of problems is compared when the topology of Dirichlet
boundary conditions changes in the interior of the regular domain of the image. The main
contribution of this work is the development and detailed description of an implementation of a
multigrid numerical solver which converges in linear time.
Automatic Detection of Internal Copy-Move Forgeries in Imageshttp://www.ipol.im/pub/art/2018/213/Thibaud Ehret2018-07-25T21:31:00Z2018-07-24T22:00:00Z
This article presents an implementation and discussion of the recently proposed 'Efficient Dense-Field Copy-Move Forgery Detection' by Cozzolino et al. This method is a forgery detection based on a dense field of descriptors chosen to be invariant by rotation. Zernike moments were suggested in the original article. An efficient matching of the descriptors is then performed using PatchMatch, which is extremely efficient to find duplicate regions. Regions matched by PatchMatch are processed to find the final detections. This allows a precise and accurate detection of copy-move forgeries inside a single suspicious image. We also extend successfully the method to the use of dense SIFT descriptors and show that they are better at detecting forgeries using Poisson editing.
Video Denoising with Optical Flow Estimationhttp://www.ipol.im/pub/art/2018/224/Antoni Buades,
Jose-Luis Lisani2018-07-22T23:06:29Z2018-07-22T22:00:00Z
In this paper we describe the implementation of state-of-the-art video denoising algorithm SPTWO [A. Buades, J.L. Lisani, M. Miladinovic, Patch Based Video Denoising with Optical Flow Estimation, IEEE Transactions on Image Processing 25 (6), 2573--2586]. This algorithm, inspired by image fusion techniques, uses motion compensation by regularized optical flow methods, which permits robust patch comparison in spatiotemporal volumes. Groups of similar patches are denoised using Principal Component Analysis, which ensures the correct preservation of fine texture and details.
Theory and Practice of Image B-Spline Interpolationhttp://www.ipol.im/pub/art/2018/221/Thibaud Briand,
Pascal Monasse2018-07-22T22:40:52Z2018-07-22T22:00:00Z
We explain how the B-spline interpolation of signals and, in particular, of images can be efficiently performed by linear filtering. Based on the seminal two-step method proposed by Unser et al. in 1991, we propose two slightly different prefiltering algorithms whose precisions are proven to be controlled thanks to a rigorous boundary handling. This paper contains all the information, theoretical and practical, required to perform efficiently B-spline interpolation for any order and any boundary extension. We describe precisely how to evaluate the kernel and to compute the B-spline interpolator parameters. We show experimentally that increasing the order improves the interpolation quality. As a fundamental application we also provide an implementation of homographic transformation of images using B-spline interpolation.
Efficient Large-scale Image Search With a Vocabulary Treehttp://www.ipol.im/pub/art/2018/199/Esteban Uriza,
Francisco Gómez Fernández,
Martín Rais2018-07-22T11:40:36Z2018-06-02T22:00:00Z
The task of searching and recognizing objects in images has become an important research
topic in the area of image processing and computer vision. Looking for similar images in large
data sets given an input query and responding as fast as possible is a very challenging task.
In this work the Bag of Features approach is studied, and an implementation of the visual
vocabulary tree method from Nistér and Stewénius is presented. Images are described using
local invariant descriptor techniques and then indexed in a database using an inverted index
for further queries. The descriptors are quantized according to a visual vocabulary, creating
sparse vectors, which allows to compute very efficiently, for each query, a ranking of similarity
for indexed images. The performance of the method is analyzed varying different
factors, such as the parameters for the vocabulary tree construction, different techniques
of local descriptors extraction and dimensionality reduction with PCA.
It can be observed that the retrieval performance increases
with a richer vocabulary and decays very slowly as the size of the dataset grows.
A MATLAB SMO Implementation to Train a SVM Classifier: Application to Multi-Style License Plate Numbers Recognitionhttp://www.ipol.im/pub/art/2018/173/Pablo Negri2018-07-22T11:40:36Z2018-05-21T22:00:00Z
This paper implements the Support Vector Machine (SVM) training procedure proposed by John Platt denominated Sequential Minimimal Optimization (SMO).
The application of this system involves a multi-style license plate characters recognition identifying numbers from '0' to '9'.
In order to be robust against license plates with different character/background colors, the characters (numbers) visual information is encoded using Histograms of Oriented Gradients (HOG).
A reliability measure to validate the system outputs is also proposed.
Several tests are performed to evaluate the sensitivity of the algorithm to different parameters and kernel functions.
Gestaltic Grouping of Line Segmentshttp://www.ipol.im/pub/art/2018/194/Boshra Rajaei,
Rafael Grompone von Gioi2018-07-22T11:40:36Z2018-03-21T23:00:00Z
Using simple grouping rules in Gestalt theory, one may detect higher level features (geometric
structures) in an image from elementary features. By recursive grouping of already detected
geometric structures a bottom-up pyramid could be built that extracts increasingly complex
geometric features from the input image. Taking advantage of the (recent) advances in
reliable line segment detectors, in this paper, we propose three feature detectors along with their
corresponding detailed algorithms that constitute one step up in this pyramid. For any digital
image, our unsupervised algorithm computes three classic Gestalts from the set of predetected
line segments: good continuations, non-local alignments, and bars. The methodology is based
on a common stochastic a contrario model yielding three simple detection formulas,
characterized by their number of false alarms.
This detection algorithm is illustrated on several digital images.
Contours, Corners and T-Junctions Detection Algorithmhttp://www.ipol.im/pub/art/2018/218/Antoni Buades,
Rafael Grompone von Gioi,
Julia Navarro2018-07-22T11:40:36Z2018-02-26T23:00:00Z
This article describes the implementation of the method by Buades, Grompone and Navarro in 2017 for the detection of line segments, contours, corners and T-junctions. The method is inspired by the mammal visual system. The detection of corners and T-junctions plays a role as part of the process in contour detection. An a contrario validation is applied to select the most meaningful contours without the need of fixing any critical parameter.
The Production of Ground Truths for Evaluating Highly Accurate Stereovision Algorithmshttp://www.ipol.im/pub/art/2018/187/Tristan Dagobert2018-07-22T11:40:36Z2018-01-01T23:00:00Z
The conception and improvement of algorithms for subpixel stereovision requires very precise test databases. The state of the art on the sets of images used extensively by the scientific community shows that they are often incomplete and imprecise compared to the dataset goals. We will present a method based on image synthesis to produce stereoscopic pairs with ground truths such as disparity and occlusion maps reaching an accuracy of about 1e-6 pixels. The a priori noise estimate is also taken into account. This process allows us to deliver a new image database consisting of 66 stereo pairs together with their ground truths.
A Contrario 3D Point Alignment Detection Algorithmhttp://www.ipol.im/pub/art/2017/214/Álvaro Gómez,
Gregory Randall,
Rafael Grompone von Gioi2018-07-22T11:40:36Z2017-12-29T23:00:00Z
In this article we present an algorithm for the detection of perceptually relevant alignments in 3D point clouds. The algorithm is an extension of the algorithm developed by Lezama et al. [J. Lezama, J-M. Morel, G. Randall, R. Grompone von Gioi, A Contrario 2D Point Alignment Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, 37 (3), pp. 499-512, 2015] for the case of sets of 2D points. The algorithm is based on the a contrario detection theory that mathematically formalizes the non-accidentalness principle proposed for perception: an observed structure is relevant if it rarely occurs by chance. This framework has been widely used in different detection tasks and leads to algorithms with a single critical parameter to control the number of false detections.
Local Region Expansion: a Method for Analyzing and Refining Image Matcheshttp://www.ipol.im/pub/art/2017/154/Erez Farhan,
Elad Meir,
Rami Hagege2018-07-22T11:40:36Z2017-12-22T23:00:00Z
We present a novel method for locating large amounts of local matches between images, with highly accurate localization. Point matching is one of the most fundamental tasks in computer vision, extensively used in applications such as object detection, object tracking and structure from motion. The major challenge in point matching is to preserve large numbers of accurate matches between corresponding scene locations under different geometric and radiometric conditions, while keeping the number of false positives low. Recent publications have shown that applying an affine transformation model on local regions is a particularly suitable approach for point matching. Yet, affine invariant methods are not used extensively for two reasons: first, because these methods are computationally demanding; and second because the derived affine estimations have limited accuracy. In this work, we propose a novel method of region expansion that enhances region matches detected by any state-of-the-art method. The method is based on accurate estimation of affine transformations, which are used to predict matching locations beyond initially detected matches. We use the improved estimations of affine transformations to locally verify tentative matches in an efficient way. We systematically reject false matches, while improving the localization of correct matches that are usually rejected by state-of-the-art methods.
Non-Local Patch-Based Image Inpaintinghttp://www.ipol.im/pub/art/2017/189/Alasdair Newson,
Andrés Almansa,
Yann Gousseau,
Patrick Pérez2018-07-22T11:40:36Z2017-12-12T23:00:00Z
Image inpainting is the process of filling in missing regions in an image in a plausible way.
In this contribution, we propose and describe an implementation of a patch-based image inpainting algorithm. The method is actually a two-dimensional version of our video inpainting algorithm proposed in
[A. Newson et al., Video inpainting of complex scenes, SIAM Journal of Imaging Sciences, 7 (2014)].
The algorithm attempts to minimize a highly non-convex functional, first introducted by Wexler et al. in
[Wexler et al., Space-time video completion, CCVPR (2004)].
The functional
specifies that a good solution to the inpainting problem should be an image where each patch is very similar
to its nearest neighbor in the unoccluded area.
Iterations are performed in a multi-scale framework which yields globally coherent results. In this manner two of the major goals of image inpainting, the correct reconstruction
of textures and structures, are addressed.
We address a series of important practical issues which arise when using such an
approach. In particular, we reduce execution times by using the PatchMatch
[C. Barnes, PatchMatch: a randomized correspondence algorithm for structural image editing, ACM Transactions on Graphics, (2009)]
algorithm for nearest neighbor searches, and we propose a modified
patch distance which improves the comparison of textured patches.
We address the crucial issue of initialization and the choice of the
number of pyramid levels, two points which are rarely discussed in
such approaches.
We provide several examples which illustrate the advantages of our algorithm,
and compare our results with those of state-of-the-art methods.
A Sub-Pixel Edge Detector: an Implementation of the Canny/Devernay Algorithmhttp://www.ipol.im/pub/art/2017/216/Rafael Grompone von Gioi,
Gregory Randall2018-07-22T11:40:36Z2017-11-27T23:00:00Z
An image edge detector is described which produces chained edge points with sub-pixel accuracy. The method incorporates the main ideas of the classic Canny and Devernay algorithms. The analysis shows that a slight modification to the original formulation improves the accuracy of the edge points.
Comparison of Motion Smoothing Strategies for Video Stabilization using Parametric Modelshttp://www.ipol.im/pub/art/2017/209/Javier Sánchez2018-07-22T11:40:36Z2017-11-25T23:00:00Z
This paper is devoted to a rigorous implementation and to an exhaustive comparison of video stabilization techniques. These techniques aim at removing the undesirable effects of camera shake. They first estimate a global transform from frame to frame, which can be a translation, a similarity, an affine map or a homography. This generates a signal that can be smoothed and used to compensate the noisy transform signal. This paper compares all classic smoothing methods and their boundary conditions. It also analyzes two algorithms to crop the video after stabilization.
The stabilization results are displayed in a scale-space form permitting to extract valuable information about ego-motion such as its frequencies and its general tendencies.
Multi-Scale DCT Denoisinghttp://www.ipol.im/pub/art/2017/201/Nicola Pierazzo,
Jean-Michel Morel,
Gabriele Facciolo2018-07-22T11:40:36Z2017-10-28T22:00:00Z
DCT denoising is a classic low complexity method built in the JPEG compression norm. Once made translation invariant, this algorithm was still proven to be competitive at the beginning of this century. Since then, it has been outperformed by patch based methods, which are far more complex. This paper proposes a two-step multi-scale version of the algorithm that boosts its performance and reduces its artifacts.
The multi-scale strategy decomposes the image in a dyadic DCT pyramid, which keeps noise white at all scales. The single scale denoising is then applied to all scales, thus giving multiple denoised versions of the low frequency coefficients of the denoised image. A 'multi-scale fusion' of these multiple estimates avoids the ringing artifacts resulting from the pyramid recomposition. The final algorithm attains a good PNSR and much improved visual image quality. It is shown to have a deficit of only 1dB with respect to state of the art algorithms, but its complexity is two orders of magnitude lower.
The Bilateral Filter for Point Cloudshttp://www.ipol.im/pub/art/2017/179/Julie Digne,
Carlo de Franchis2018-07-22T11:40:36Z2017-10-28T22:00:00Z
Point sets obtained by 3D scanners are often corrupted with noise, that can have several causes, such as a tangential acquisition direction, changing environmental lights or a reflective object material. It is thus crucial to design efficient tools to remove noise from the acquired data without removing important information such as sharp edges or shape details. To do so, Fleishman et al. introduced a bilateral filter for meshes adapted from the bilateral filter for gray level images. This anisotropic filter denoises a point with respect to its neighbors by considering not only the distance from the neighbors to the point but also the distance along a normal direction. This simple fact allows for a much better preservation of sharp edges. In this paper, we analyze a parallel implementation of the bilateral filter adapted for point clouds.
An Algorithm for Gaussian Texture Inpaintinghttp://www.ipol.im/pub/art/2017/198/Bruno Galerne,
Arthur Leclaire2018-07-22T11:40:36Z2017-10-08T22:00:00Z
Inpainting consists in computing a plausible completion of missing parts of an image given the available content.
In the case of images composed of a homogeneous microtexture, inpainting can be addressed by relying on Gaussian conditional simulation.
In this paper we describe an algorithm which allows to perform inpainting by Gaussian conditional simulation, in a scalable way.
We provide a detailed numerical study of this algorithm.
2D Filtering of Curvilinear Structures by Ranking the Orientation Responses of Path Operators (RORPO)http://www.ipol.im/pub/art/2017/207/Odyssee Merveille,
Benoît Naegel,
Hugues Talbot,
Laurent Najman,
Nicolas Passat2018-07-22T11:40:36Z2017-09-30T22:00:00Z
We present a filtering method for 2D curvilinear structures, called RORPO (Ranking the Orientation Responses of Path Operators). RORPO is based on path operators, a recently developed family of mathematical morphology filters. Compared with state of the art methods, RORPO is non-local and well adapted to the intrinsic anisotropy of curvilinear structures. Since RORPO does not depend on a linear scale-space framework, it tends to preserve object contours without a blurring effect. Due to these properties, RORPO is a useful low-level filter and can also serve as a curvilinear prior in segmentation frameworks. In this article, after introducing RORPO, we develop the 2D version of the algorithm and present a few applications.
Hyperspectral Image Classification Using Graph Clustering Methodshttp://www.ipol.im/pub/art/2017/204/Zhaoyi Meng,
Ekaterina Merkurjev,
Alice Koniges,
Andrea L. Bertozzi2018-07-22T11:40:36Z2017-08-18T22:00:00Z
Hyperspectral imagery is a challenging modality due to the dimension of the pixels which can range from hundreds to over a thousand frequencies depending on the sensor. Most methods in the literature reduce the dimension of the data using a method such as principal component analysis, however this procedure can lose information. More recently methods have been developed to address classification of large datasets in high dimensions. This paper presents two classes of graph-based classification methods for hyperspectral imagery. Using the full dimensionality of the data, we consider a similarity graph based on pairwise comparisons of pixels. The graph is segmented using a pseudospectral algorithm for graph clustering that requires information about the eigenfunctions of the graph Laplacian but does not require computation of the full graph. We develop a parallel version of the Nyström extension method to randomly sample the graph to construct a low rank approximation of the graph Laplacian. With at most a few hundred eigenfunctions, we can implement the clustering method designed to solve a variational problem for a graph-cut-based semi-supervised or unsupervised classification problem. We implement OpenMP directive-based parallelism in our algorithms and show performance improvement and strong, almost ideal, scaling behavior. The method can handle very large datasets including a video sequence with over a million pixels, and the problem of segmenting a data set into a pre-determined number of classes.
The Image Curvature Microscope: Accurate Curvature Computation at Subpixel Resolutionhttp://www.ipol.im/pub/art/2017/212/Adina Ciomaga,
Pascal Monasse,
Jean-Michel Morel2018-07-22T11:40:36Z2017-07-27T22:00:00Z
We detail in this paper the numerical implementation of the so-called image curvature microscope, an algorithm that computes accurate image curvatures at subpixel resolution, and yields a curvature map conforming with our visual perception. In contrast to standard methods, which would compute the curvature by a finite difference scheme, the curvatures are evaluated directly on the level lines of the bilinearly interpolated image, after their independent smoothing, a step necessary to remove pixelization artifacts. The smoothing step consists in the affine erosion of the level lines through a geometric scheme, and can be applied in parallel to all level lines. The online algorithm allows the user to visualize the image of curvatures at different resolutions, as well as the set of level lines before and after smoothing.
Iterative Hough Transform for Line Detection in 3D Point Cloudshttp://www.ipol.im/pub/art/2017/208/Christoph Dalitz,
Tilman Schramke,
Manuel Jeltsch2018-07-22T11:40:36Z2017-07-18T22:00:00Z
The Hough transform is a voting scheme for locating geometric objects in point clouds. This paper describes its application for detecting lines in three dimensional point clouds. For parameter quantization, a recently proposed method for Hough parameter space regularization is used. The voting process is done in an iterative way by selecting the line with the most votes and removing the corresponding points in each step. To overcome the inherent inaccuracies of the parameter space discretization, each line is estimated with an orthogonal least squares fit among the candidate points returned from the Hough transform.
Realistic Film Grain Renderinghttp://www.ipol.im/pub/art/2017/192/Alasdair Newson,
Noura Faraj,
Bruno Galerne,
Julie Delon2018-07-22T11:40:36Z2017-07-17T22:00:00Z
Film grain is the unique texture which results from the silver halide based analog photographic process. Film emulsions are made up of microscopic photo-sensitive silver grains, and the fluctuating density of these grains leads to what is known as film grain. This texture is valued by photographers and film directors for its artistic value. We present two implementations of a film grain rendering algorithm based on a physically realistic film grain model. The rendering algorithm uses a Monte Carlo simulation to determine the value of each output rendered pixel. A significant advantage of using this model is that the images can be rendered at any resolution, so that arbitrary zoom factors are possible, even to the point where the individual grains can be observed. We provide a method to choose the best implementation automatically, with respect to execution time.
Vanishing Point Detection in Urban Scenes Using Point Alignmentshttp://www.ipol.im/pub/art/2017/148/José Lezama,
Gregory Randall,
Rafael Grompone von Gioi2018-07-22T11:40:36Z2017-07-13T22:00:00Z
We present a method for the automatic detection of vanishing points in urban scenes based
on finding point alignments in a dual space, where converging lines in the image are mapped
to aligned points. To compute this mapping the recently introduced PClines transformation
is used. A robust point alignment detector is run to detect clusters of aligned points in the
dual space. Finally, a post-processing step discriminates relevant from spurious vanishing point
detections with two options: using a simple hypothesis of three orthogonal vanishing points
(Manhattan-world) or the hypothesis that one vertical and multiple horizontal vanishing points
exist. Qualitative and quantitative experimental results are shown. On two public standard
datasets, the method achieves state-of-the-art performances. Finally, an optional procedure for
accelerating the method is presented.
A Fast Approximation of the Bilateral Filter using the Discrete Fourier Transformhttp://www.ipol.im/pub/art/2017/184/Pravin Nair,
Anmol Popli,
Kunal N. Chaudhury2018-07-22T11:40:36Z2017-05-23T22:00:00Z
The bilateral filter is a popular non-linear smoother that has applications in image processing, computer vision, and computational photography.
The novelty of the filter is that a range kernel is used in tandem with a spatial kernel for performing edge-preserving smoothing, where both kernels are usually Gaussian.
A direct implementation of the bilateral filter is computationally expensive, and several fast approximations have been proposed to address this problem.
In particular, it was recently demonstrated in a series of papers that a fast and accurate approximation of the bilateral filter can be obtained by approximating the Gaussian range kernel using polynomials and trigonometric functions. By adopting some of the ideas from this line of work, we propose a fast algorithm based on the discrete Fourier transform of the samples of the range kernel. We develop a parallel C implementation of the resulting algorithm for Gaussian kernels, and analyze the effect of various extrinsic and intrinsic parameters on the approximation quality and the run time. A key component of the implementation are the recursive Gaussian filters of Deriche and Young.
Data Adaptive Dual Domain Denoising: a Method to
Boost State of the Art Denoising Algorithmshttp://www.ipol.im/pub/art/2017/203/Nicola Pierazzo,
Gabriele Facciolo2018-07-22T11:40:36Z2017-05-23T22:00:00Z
This article presents DA3D (Data Adaptive Dual Domain Denoising), a 'last step denoising' method that takes as input a noisy image and as a guide the result of any state-of-the-art denoising algorithm. The method performs frequency domain shrinkage on shape and data-adaptive patches.
DA3D doesn't process all the image samples, which allows it to use large patches (64 x 64 pixels). The shape and data-adaptive patches are dynamically selected, effectively concentrating the computations on areas with more details, thus accelerating the process considerably.
DA3D also reduces the staircasing artifacts sometimes present in smooth parts of the guide images. The effectiveness of DA3D is confirmed by extensive experimentation. DA3D improves the result of almost all state-of-the-art methods, and this improvement requires little additional computation time.