IPOLIPOLhttp://www.ipol.im/feed/IPOL Articles — Latest articles published in IPOL.ikiwiki2018-10-03T10:26:21ZAn Analysis and Implementation of the Harris Corner Detectorhttp://www.ipol.im/pub/art/2018/229/Javier Sánchez,
Nelson Monzón,
Agustín Salgado2018-10-03T10:26:21Z2018-10-02T22:00:00Z
In this work, we present an implementation and thorough study of the Harris corner detector. This feature detector relies on the analysis of the eigenvalues of the autocorrelation matrix. The algorithm comprises seven steps, including several measures for the classification of corners, a generic non-maximum suppression method for selecting interest points, and the possibility to obtain the corners position with subpixel accuracy. We study each step in detail and propose several alternatives for improving the precision and speed. The experiments analyze the repeatability rate of the detector using different types of transformations.
Estimating an Image's Blur Kernel Using Natural Image Statistics, and Deblurring it: An Analysis of the Goldstein-Fattal Methodhttp://www.ipol.im/pub/art/2018/211/Jérémy Anger,
Gabriele Facciolo,
Mauricio Delbracio2018-09-26T21:47:21Z2018-09-25T22:00:00Z
Despite the significant improvement in image quality resulting from improvement in optical sensors and general electronics, camera shake blur significantly undermines the quality of hand-held photographs. In this work, we present a detailed description and implementation of the blur kernel estimation algorithm introduced by Goldstein and Fattal in 2012. Unlike most methods that attempt to solve an inverse problem through a variational formulation (e.g. through a Maximum A Posteriori estimation), this method directly estimates the blur kernel by modeling statistical irregularities in the power spectrum of blurred natural images. The adopted mathematical model extends the well-known power-law by contemplating the presence of dominant strong edges in particular directions. The blur kernel is retrieved from an estimation of its power spectrum, by solving a phase retrieval problem using additional constraints associated with the particular nature of camera shake blur kernels (e.g. non-negativity and small spatial support). Although the algorithm is conceptually simple, its numerical implementation presents several challenges. This work contributes to a detailed anatomy of the Goldstein and Fattal method, its algorithmic description, and its parameters.
Fast Affine Invariant Image Matchinghttp://www.ipol.im/pub/art/2018/225/Mariano Rodríguez,
Julie Delon,
Jean-Michel Morel2018-09-30T21:43:24Z2018-09-23T22:00:00Z
Methods performing Image Matching by Affine Simulation (IMAS) attain affine invariance by applying a finite set of affine transforms to the images before comparing them with a Scale Invariant Image Matching (SIIM) method like SIFT or SURF. We describe here how to optimize IMAS methods. First, we detail an algorithm computing a minimal discrete set of affine transforms to be applied to each image before comparison. It yields a full practical affine invariance at the lowest computational cost. The matching complexity of current IMAS algorithms is divided by about 4. Our approach also associates to each image an affine invariant set of descriptors, which is twice smaller than the set of descriptors usually used in IMAS methods, and only 6.4 times larger than the set of similarity invariant descriptors of SIIM methods. In order to reduce the number of false matches, which are inherently more frequent in IMAS approaches than in SIIM, we introduce the notion of hyper-descriptor, which groups descriptors whose keypoints are spatially close. Finally, we also propose a matching criterion allowing each keypoint of the query image to be matched with several keypoints of the target image, in order to deal with situations where an object is repeated several times in the target image.
Numerical Simulation of Landscape Evolution Modelshttp://www.ipol.im/pub/art/2018/205/Marc Lebrun,
Miguel Colom,
Jérôme Darbon,
Jean-Michel Morel2018-09-03T19:51:45Z2018-09-02T22:00:00Z
This paper gives the complete numerical schemes implementing the main physical laws proposed in landscape evolution models (LEMs). These laws can be modeled by a system of three partial differential equations governing water runoff, stream incision, hill slope evolution and sedimentation. The goal of the presented algorithm, code and online demo is to be able to test these equations on digital elevation models (DEMs) of any resolution, and to illustrate its potential to simulate the fine structure of the river network, and to understand the landscape morphology and its causes. The equations simulate plausible evolutions. We illustrate experiments on DEMs of several sites, including one site, La Réunion where the DEM is given at three different resolutions: the SRTM resolution (90m), and then 12m and 4m on DEMs derived from several Pléiades pairs. Other many DEMs are proposed in the online demo, which allows to upload and tests other DEMs.
An Analysis and Implementation of Multigrid Poisson Solvers With Verified Linear
Complexityhttp://www.ipol.im/pub/art/2018/228/Matías Di Martino,
Gabriele Facciolo2018-09-04T21:52:26Z2018-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-09-04T21:52:26Z2018-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-09-04T21:52:26Z2018-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-09-04T21:52:26Z2018-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-09-04T21:52:26Z2018-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.