Documentation

Table of contents:


 

Code documentation

The documentation has been generated using the tool doxygen. It contains a detailed description of all classes and functions of the Yadics library. If you have downloaded the Yadics package, you actually have a local copy of these pages in the Yadics/DOCUMENTATION/html.

Find here, the Yadics library documentation.

The possibilities of Yadics are summarized in the diagram below :

Yadics theoretical background

Image Registration Principle

YaDICs can be explained using the classical Image Registration framework [1] :

alt-text

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 a lot of 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 1000³ voxels. With such a size it is not possible to use naive approach usually used in a 2D- 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] , this documentation will only deal with the Yadics approach.

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 linear and bi-cubic interpolations for the grey level evaluation at non integer coordinates. The bi-cubic interpolation is the recommended one.

Metrics

Sum of Squared differences (SSD)

The  equation below defines the SSD metric :

SSD(\mu,\mathcal{I_F},\mathcal{I_M})=\dfrac{1}{\left | \Omega_F \right |} \sum_{x_i \in \Omega_F} \left( \mathcal{I_F}(x_i) - \mathcal{I_M}({T}_{\mu}(x_i))\right)^{2}

where \mathcal{I_F} is the fixed image, \mathcal{I_M} the moving one, \Omega_F the integration area \left | \Omega_F \right | the number of pi(vo)xels (cardinal)  and {T}_{\mu} the transformation parametrized by \mu

The transformation can be written as :

T_{\mu}(x)=x + \left \{\Phi(x)\right \}^{t} \left \{\mu \right \}

This metric is the main used in the Yadics as it works well with same modality images. One has to find the minimum of this metric

Normalized Cross Correlation (NCC)

The NCC is used when one cannot assure the optical flow conservation, it happens in case of change of lighting or if particles disappear from the scene can occur in Particule Images Velocimetry (PIV).

The NCC is defined by :

NCC(\mu,\mathcal{I_F},\mathcal{I_M})=\dfrac{\sum_{x_i \in \Omega_F} \left( \mathcal{I_F}(x_i) - \overline{\mathcal{I_F}}\right) \left( \mathcal{I_M}({T}_{\mu}(x_i)) - \overline{\mathcal{I_M}}\right)}{\sqrt{\sum_{x_i \in \Omega_F} \left( \mathcal{I_F}(x_i) - \overline{\mathcal{I_F}}\right)^{2}\sum_{x_i \in \Omega_F} \left(\mathcal{I_M}({T}_{\mu}(x_i))- \overline{\mathcal{I_M}}\right)^{2}}}

where \overline{\mathcal{I_F}}\ and \overline{\mathcal{I_M}}\ 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 B-Splines [1, 2] and in solid mechanics with finite element basis [3, 4]. The global transformations are defined on the whole picture using rigid body or affine transformation (which is equivalent to homogeneous strain transformation). More complex transformations can be defined such as mechanically based one. These transformations have been used for stress intensity factor identification by [5, 6] and for rod strain by [7]. The local transformation can be considered as the same global transformation defined on several Zone Of Interest (ZOI) of the fixed image.

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

\begin{array}{lcl}\dfrac{\partial SSD(\mu,\mathcal{I_F},\mathcal{I_M})}{\partial \mu} &=&\dfrac{2}{\left | \Omega_F \right |} \sum_{x_i \in \Omega_F} \left( \mathcal{I_F}(x_i) - \mathcal{I_M}({T}_{\mu}(x_i))\right)\dfrac{\partial \mathcal{I_M}( {T}_{\mu}(x_i)}{\partial \mu} \\ &=& \dfrac{2}{\left | \Omega_F \right |} \sum_{x_i \in \Omega_F} \left( \mathcal{I_F}(x_i) - \mathcal{I_M}({T}_{\mu}(x_i))\right) \left( \dfrac{\partial {T}_{\mu}(x_i)}{\partial \mu} \right )^{t} \dfrac{\partial \mathcal{I_M}( {T}_{\mu}(x_i))}{\partial x} \\\end{array}

Gradient method

Once the metric gradient has been computed, one has to find an optimization strategy

The gradient method principle is explained below :

\mu_{k+1}=\mu_k+\alpha_k d_k

The gradient step \alpha_k can be constant or updated at every iteration.

d_k=-\gamma_k \dfrac{\partial \mathcal{C}(\mu,\mathcal{I_F},\mathcal{I_M})}{\partial \mu}, \gamma_k allows one to choose between the following methods

  •  \gamma_k=1 \Longrightarrow steepest descent,
  • \gamma_k=\left [ \dfrac{\partial \mathcal{C}(\mu,\mathcal{I_F},\mathcal{I_M})}{\partial \mu}\dfrac{\partial \mathcal{C}(\mu,\mathcal{I_F},\mathcal{I_M})}{\partial \mu}^{t} \right ]^{-1} \Longrightarrow Gauss-Newton,

A lot of  different methods exist (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 1000³ voxels  µ-tomographic image the number of Degrees of Freedom can reach 1e6 (i.e: on a 12x12x12 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. We have developed a specific steepest gradient algorithm with a specific tuning of the  \alpha_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].

alt-text

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 we 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

[1] [doi] 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, iss. 1, pp. 196-205, 2010.
[Bibtex]
@ARTICLE{KleStar10,
author = {Klein, S. and Staring, M. and Murphy, K. and Viergever, M.A. and
Pluim, J. P W},
title = {elastix: A Toolbox for Intensity-Based Medical Image Registration},
journal = {Medical Imaging, IEEE Transactions on},
year = {2010},
volume = {29},
pages = {196-205},
number = {1},
doi = {10.1109/TMI.2009.2035616},
issn = {0278-0062},
keywords = {biomedical MRI;computerised tomography;image registration;medical
computing;medical image processing;public domain software;automated
data processing;command-line interface;computed tomography;elastix;intensity-based
medical image registration;magnetic resonance imaging;scripting;Application
software;Biomedical imaging;Cost function;Image processing;Image
registration;Image segmentation;MONOS devices;Open source software;Optimization
methods;Spatial resolution;elastix;image registration;medical imaging;open
source;software;Diagnostic Imaging;Humans;Image Processing, Computer-Assisted;Models,
Biological;Normal Distribution;Software},
url = {http://dx.doi.org/10.1109/TMI.2009.2035616}
}
[2] [doi] J. Réthoré, T. Elguedj, P. Simon, and M. Coret, "On the use of nurbs functions for displacement derivatives measurement by digital image correlation," Experimental mechanics, vol. 50, iss. 7, pp. 1099-1116, 2010.
[Bibtex]
@ARTICLE{ReEl2010,
author = {R\'{e}thor\'{e}, J. and Elguedj, T. and Simon, P. and Coret, M.},
title = {On the Use of NURBS Functions for Displacement Derivatives Measurement
by Digital Image Correlation},
journal = {Experimental Mechanics},
year = {2010},
volume = {50},
pages = {1099-1116},
number = {7},
doi = {10.1007/s11340-009-9304-z},
issn = {0014-4851},
keywords = {Digital image correlation; Beam; B-splines},
language = {English},
publisher = {Springer US},
url = {http://dx.doi.org/10.1007/s11340-009-9304-z}
}
[3] [doi] 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.
[Bibtex]
@ARTICLE{BeHiRo06,
author = {Gilles Besnard and Fran\c{c}ois Hild and St{\'e}phane Roux},
title = {Finite-Element Displacement Fields Analysis from Digital Images:
Application to Portevin-Le Ch{\^a}telier Bands},
journal = {Experimental Mechanics},
year = {2006},
volume = {46},
pages = {789--803},
number = {6},
doi = {DOI:.1007/s11340-006-9824-8},
issn = { 0014-4851},
url = {http://dx.doi.org/10.1016/0262-8856(83)90064-1}
}
[4] [doi] 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.
[Bibtex]
@ARTICLE{ReRo2007,
author = {Julien R\'{e}thor\'{e} and St\'{e}phane Roux and Fran�ois Hild},
title = {From pictures to extended finite elements: extended digital image
correlation (X-DIC) },
journal = {Comptes Rendus M\'{e}canique },
year = {2007},
volume = {335},
pages = {131 - 137},
number = {3},
doi = {10.1016/j.crme.2007.02.003},
issn = {1631-0721},
keywords = {Rupture},
url = {http://dx.doi.org/10.1016/j.crme.2007.02.003}
}
[5] [doi] 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.
[Bibtex]
@ARTICLE{haRoHi2007,
author = {Hamam, Rami and Hild, Fran{\c{c}}ois and Roux, St{\'e}phane},
title = {Stress intensity factor gauging by digital image correlation: Application
in cyclic fatigue},
journal = {Strain},
year = {2007},
volume = {43},
pages = {181--192},
number = {3},
doi = {0.1111/j.1475-1305.2007.00345.x},
publisher = {Wiley Online Library},
url = {http://dx.doi.org/0.1111/j.1475-1305.2007.00345.x}
}
[6] [doi] 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.
[Bibtex]
@ARTICLE{HiRoIDIC,
author = {Fran�ois Hild and St\'{e}phane Roux},
title = {Measuring stress intensity factors with a camera: Integrated digital
image correlation (I-DIC) },
journal = {Comptes Rendus M\'{e}canique },
year = {2006},
volume = {334},
pages = {8 - 12},
number = {1},
doi = {http://dx.doi.org/10.1016/j.crme.2005.11.002},
issn = {1631-0721},
keywords = {Rupture},
url = {http://www.sciencedirect.com/science/article/pii/S163107210500210X}
}
[7] [doi] 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.
[Bibtex]
@ARTICLE{HiRoLo,
author = {Fran�ois Hild and St\'{e}phane Roux and N\'{e}stor Guerrero and Maria
Eugenia Marante and Julio Fl\'{o}rez-Ll\'{o}pez},
title = {Calibration of constitutive models of steel beams subject to local
buckling by using digital image correlation },
journal = {European Journal of Mechanics - A/Solids },
year = {2011},
volume = {30},
pages = {1 - 10},
number = {1},
doi = {http://dx.doi.org/10.1016/j.euromechsol.2010.09.007},
issn = {0997-7538},
keywords = {Digital image correlation},
url = {http://www.sciencedirect.com/science/article/pii/S0997753810001142}
}
[8] [doi] 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.
[Bibtex]
@ARTICLE{HiRoBraz,
author = {Hild, F. and Roux, S.},
title = {Digital Image Correlation: from Displacement Measurement to Identification
of Elastic Properties ? a Review},
journal = {Strain},
year = {2006},
volume = {42},
pages = {69--80},
number = {2},
doi = {10.1111/j.1475-1305.2006.00258.x},
issn = {1475-1305},
keywords = {Brazilian disk test, correlation algorithm, integrated approach, kinematic
measurements, photomechanics},
publisher = {Blackwell Publishing Ltd},
url = {http://dx.doi.org/10.1111/j.1475-1305.2006.00258.x}
}
[9] 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.
[Bibtex]
@ARTICLE{ITK2002,
author = {Terry S. Yoo and Michael J. Ackerman and William E. Lorensen and
Will Schroeder and Vikram Chalana and Stephen Aylward and Dimitris
Metaxas and Ross Whitaker},
title = {Engineering and Algorithm Design for an Image Processing API: A Technical
Report on ITK - the Insight Toolkit},
year = {2002},
pages = {586--592},
month = {01},
abstract = {We present the detailed planning and execution of the Insight Toolkit
(ITK), an application programmers interface (API) for the segmentation
and registration of medical image data. This public resource has
been developed through the NLM Visible Human Project, and is in beta
test as an open-source software offering under cost-free licensing.
The toolkit concentrates on 3D medical data segmentation and registration
algorithms, multimodal and multiresolution capabilities, and portable
platform independent support for Windows, Linux/Unix systems. This
toolkit was built using current practices in software engineering.
Specifically, we embraced the concept of generic programming during
the development of these tools, working extensively with C++ templates
and the freedom and flexibility they allow. Additional software development
tools for distributed consortium-based code development have been
created and are available from the project. In this paper, we discuss
our assumptions, design decisions, and some of the lessons we have
learned.},
institution = {National Library of Medicine, National Institutes of Health, Bethesda},
publisher = {Proc. of Medicine Meets Virtual Reality, J. Westwood, ed., IOS Press
Amsterdam},
url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.1280}
}
[10] [doi] 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.
[Bibtex]
@ARTICLE{Tikhonov1965,
author = {A.N. Tikhonov and V.B. Glasko},
title = {Use of the regularization method in non-linear problems },
journal = {\{USSR\} Computational Mathematics and Mathematical Physics },
year = {1965},
volume = {5},
pages = {93 - 107},
number = {3},
doi = {http://dx.doi.org/10.1016/0041-5553(65)90150-3},
issn = {0041-5553},
url = {http://www.sciencedirect.com/science/article/pii/0041555365901503}
}
[11] [doi] 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, iss. 2?3, pp. 272-298, 2003.
[Bibtex]
@ARTICLE{Cachier2003,
author = {Pascal Cachier and Eric Bardinet and Didier Dormont and Xavier Pennec
and Nicholas Ayache},
title = {Iconic feature based nonrigid registration: the \{PASHA\} algorithm
},
journal = {Computer Vision and Image Understanding },
year = {2003},
volume = {89},
pages = {272 - 298},
number = {2?3},
note = {<ce:title>Nonrigid Image Registration</ce:title> },
doi = {10.1016/S1077-3142(03)00002-X},
issn = {1077-3142},
keywords = {Nonrigid registration},
url = {http://dx.doi.org/10.1016/S1077-3142(03)00002-X}
}