YaDICs
This article needs additional citations for verification. (May 2015) |
Original author(s) | Coudert Sébastien, Seghir Rian, Witz Jean-françois |
---|---|
Initial release | January 2012 |
Stable release | v04.14a
/ May 27, 2015 |
Image processing | |
License | GPLv2 or later |
Website | yadics |
YaDICs is a program written to perform
Theoretical background
Context
In solid mechanics,
In fluid mechanics a similar method is used, called
In mechanics the displacement or velocity fields are the only concern, registering images is just a side effect. There is another process called image registration using the same algorithms (on monomodal images) but where the goal is to register images and thereby identifying the displacement field is just a side effect.
YaDICs uses the general principle of image registration with a particular attention to the displacement fields basis.
Image registration principle
YaDICs can be explained using the classical image registration framework:[1]
Image registration general scheme
The common idea of image registration and digital image correlation is to find the transformation between a fixed image and a moving one for a given metric using an optimization scheme. While there are many methods to achieve such a goal, Yadics focuses on registering images with the same modality. The idea behind the creation of this software is to be able to process data that comes from a µ-tomograph; i.e.: data cube over 10003 voxels. With such a size it is not possible to use naive approach usually used in a two-dimensional context. In order to get sufficient performances OpenMP parallelism is used and data are not globally stored in memory. As an extensive description of the different algorithms is given in.[1]
Sampling
Contrary to image registration, Digital Image Correlation targets the transformation, one wants to extracted the most accurate transformation from the two images and not just match the images. Yadics uses the whole image as a sampling grid: it is thus a total sampling.
Interpolator
It is possible to choose between bilinear interpolation and bicubic interpolation for the grey level evaluation at non integer coordinates. The bi-cubic interpolation is the recommended one.
Metrics
Sum of squared differences (SSD)
The SSD is also known as mean squared error. The equation below defines the SSD metric:
where is the fixed image, the moving one, the integration area the number of pi(vo)xels (cardinal) and the transformation parametrized by μ
The transformation can be written as:
This metric is the main one used in the YaDICs as it works well with same modality images. One has to find the minimum of this metric
Normalized cross-correlation
The
The NCC is defined by:
where and are the mean values of the fixed and mobile images.
This metric is only used to find local translation in Yadics. This metric with translation transform can be solved using cross-correlation methods, which are non iterative and can be accelerated using Fast Fourier Transform .
Classification of transformations
There are three categories of parametrization: elastic, global and local transformation. The elastic transformations respect the partition of unity, there are no holes created or surfaces counted several times. This is commonly used in Image Registration by the use of
Global
Several global transforms have been implemented:
- Rigid and homogeneous (Tx,Ty,Rz in 2D; Tx,Ty,Tz,Rx,Ry,Rz,Exx,Eyy,Ezz,Eyz,Exz,Exy in 3D)
- Brazilian [8] (Only in 2D),
- Dynamic Flexion,
Elastic
First-order quadrangular finite elements Q4P1 are used in Yadics.
Local
Every global transform can be used on a local mesh.
Optimization
The YaDICs optimization process follows a gradient descent scheme.
The first step is to compute the gradient of the metric regarding the transform parameters
Gradient method
Once the metric gradient has been computed, one has to find an optimization strategy
The gradient method principle is explained below:
The gradient step can be constant or updated at every iteration. , allows one to choose between the following methods :
- steepest descent,
- Gauss-Newton.
Many different methods exist (e.g. BFGS, conjugate gradient, stochastic gradient) but as steepest gradient and Gauss-Newton are the only ones implemented in Yadics these methods are not discussed here.
The Gauss-Newton method is a very efficient method that needs to solve a [M]{U}={F}. On 10003 voxels µ-tomographic image the number of degrees of freedom can reach 1e6 (i.e: on a 12×12×12 mesh), dealing with such a problem is more a matter of numerical scientists and required specific development (using libraries like Petsc or MUMPS) so we don't use Gauss-Newton methods to solve such problems. One has developed a specific steepest gradient algorithm with a specific tuning of the αk scalar parameter at each iteration. The Gauss-Newton method can be used in small problems in 2D.
Pyramidal filter
None of these optimization methods can succeed directly if applied at the last scale as the gradient methods are sensitive to the initial guests. In order to find a global optimum one has to evaluate the transformation on a filtered image. The figure below illustrates how to use the pyramidal filter to find the transformation.[9]
Pyramidal process used in Yadics (and ITK).
Regularization
The metrics is often called image energy; people usually add energy that comes from mechanics assumptions as the Laplacian of displacement (a special case of Tikhonov regularization [10]) or even finite element problems. As one decided not to solve the Gauss-Newton problem for most of cases this solution is far from being CPU efficient. Cachier et al.[11] demonstrated that the problem of minimizing image and mechanical energy can be reformulated in solving the energy image then applying a Gaussian filter at each iteration. We use this strategy in Yadics and we add the median filter as it is massively used in PIV. One notes that the median filter avoids local minima while preserving discontinuities. The filtering process is illustrated in the figure below :
See also
- Image registration
- Optical flow
- Displacement vector
- Particle Image Velocimetry
References
- ^ a b c S. Klein, M. Staring, K. Murphy, M. A. Viergever, and J. P. W. Pluim, "Elastix: a toolbox for intensity-based medical image registration," Medical imaging, IEEE transactions on, vol. 29, issue 1, pp. 196–205, 2010
- ^ J. Réthoré, T. Elguedj, P. Simon, and M. Correct, "On the use of nurbs functions for displacement derivatives measurement by digital image correlation," Experimental mechanics, vol. 50, iss. 7, pp. 1099–1116, 2010.
- ^ G. Besnard, F. Hild, and S. Roux, "Finite-element displacement fields analysis from digital images: application to portevin-le châtelier bands," Experimental mechanics, vol. 46, iss. 6, pp. 789–803, 2006.
- ^ J. Réthoré, S. Roux, and F. Hild, "From pictures to extended finite elements: extended digital image correlation (x-dic)," Comptes rendus mécanique, vol. 335, iss. 3, pp. 131–137, 2007.
- ^ R. Hamam, F. Hild, and S. Roux, "Stress intensity factor gauging by digital image correlation: application in cyclic fatigue," Strain, vol. 43, iss. 3, pp. 181–192, 2007.
- ^ F. Hild and S. Roux, "Measuring stress intensity factors with a camera: integrated digital image correlation (i-dic)," Comptes rendus mécanique, vol. 334, iss. 1, pp. 8–12, 2006.
- ^ F. Hild, S. Roux, N. Guerrero, M. Marante, and J. Flórez-Llópez, "Calibration of constitutive models of steel beams subject to local buckling by using digital image correlation," European journal of mechanics - a/solids, vol. 30, iss. 1, pp. 1–10, 2011.
- ^ F. Hild and S. Roux, "Digital image correlation: from displacement measurement to identification of elastic properties ? a review," Strain, vol. 42, iss. 2, pp. 69–80, 2006.
- ^ T. S. Yoo, M. J. Ackerman, W. E. Lorensen, W. Schroeder, V. Chalana, S. Aylward, Dimitris Metaxas, and R. Whitaker, "Engineering and algorithm design for an image processing api: a technical report on itk - the insight toolkit", pp. 586–592, 2002.
- ^ A. N. Tikhonov and V. B. Glasko, "Use of the regularization method in non-linear problems," \USSR\ computational mathematics and mathematical physics, vol. 5, iss. 3, pp. 93–107, 1965.
- ^ P. Cachier, E. Bardinet, D. Dormont, X. Pennec, and N. Ayache, "Iconic feature based nonrigid registration: the \PASHA\ algorithm," Computer vision and image understanding, vol. 89, issue 2?3, pp. 272–298, 2003.