Johan Debayle
email: debayle@emse.fr

Benoît Presles
email: benoit.presles@creatis.insa-lyon.fr

Rigid Image Registration by General Adaptive Neighborhood Matching

Keywords: Block matching, Displacement field, General adaptive neighborhoods, Image registration, Shape metric

This paper aims to propose a new feature and intensity-based image registration method.

The proposed approach is based on the block matching algorithm [1]: a displacement field is locally computed by matching spatially-invariant intensity sub-blocks of the images before performing an optimization algorithm from this vector field to estimate the transformation. Our approach proposes a new way to calculate the displacement field by matching spatially-variant sub-blocks of the images, called General Adaptive Neighborhoods (GANs) [2]. These neighborhoods are adaptive with respect to both the intensities and the spatial structures of the image. They represent the patterns within the grayscale images. This paper also presents a consistent shape metric used to match the GANs. The performed qualitative and quantitative experiments show that the proposed GAN matching method provides accurate displacement fields enabling to perform image rigid registration, even for data from different modalities, that outperforms the classical block matching algorithm with respect to robustness and accuracy criteria.

Introduction

Image registration consists in bringing two images, acquired with the same or different sensors, into spatial alignment. More formally, given two input images, registering the floating (i.e., moving) image to the reference (i.e., fixed) image entails finding the spatial transformation that minimizes the dissimilarity between the transformed floating and reference images. This process is mainly composed of three elements:

• a transformation space, which describes the set of admissible transformations from which one is chosen to apply to the floating image,

• a similarity criterion, which measures the discrepancy between the images, and • an optimization algorithm, which traverses the transformation space, in search of the transformation that minimizes the similarity criterion.

Many registration methods have been developed and/or used in the literature using a large variety of:

• transformation spaces (linear [START_REF] Jenkinson | A global optimisation method for robust affine registration of brain images[END_REF], polyaffine [START_REF] Feldmar | Rigid, affine and locally affine registration of free-form surfaces[END_REF][START_REF] Commowick | An efficient locally affine framework for the smooth registration of anatomical structures[END_REF], elastic [START_REF] Davatzikos | Spatial transformation and registration of brain images using elastically deformable models[END_REF][START_REF] Gallea | Three-dimensional fuzzy kernel regression framework for registration of medical volume data[END_REF], fluid [START_REF] Agostino | A viscous fluid model for multimodal nonrigid image registration using mutual information[END_REF], ...);

• similarity criteria (sum of squared differences [START_REF] Alpert | Improved methods for image registration[END_REF], correlation coefficient [START_REF] Brown | A survey of image registration techniques[END_REF],

correlation ratio [START_REF] Roche | The correlation ratio as a new similarity measure for multimodal image registration[END_REF], mutual information [START_REF] Viola | Alignment by maximisation of mutual information[END_REF], multiscale integral invariants [START_REF] Hong | Shape matching using multiscale integral invariants[END_REF]...); and

• optimization algorithms (Powell method [START_REF] Collignon | Automated multi-modality image registration based on information theory[END_REF], Levenberg-Marquardt method [START_REF] Taubin | An improved algorithm for algebraic curve and surface fitting[END_REF], stochastic search [START_REF] Maintz | A survey of medical image registration[END_REF], ...).

However, registration methods can be classifed into two main categories. The first category, called geometric methods, is based on feature matching, where transformations are calculated using correspondences between points [START_REF] Rangarajan | A robust point-matching algorithm for autoradiograph alignment[END_REF], contours [START_REF] Cohen | Automatic matching of homologous histological sections[END_REF], ... While it could be argued that these techniques enable a better control over the registration process, the feature extraction can be a difficult task [START_REF] Zitova | Image registration methods: a survey[END_REF]. The second category of methods, called iconic methods or intensity-based methods, rely on the intensities associated to pixels/voxels in the input images. Assuming a global relationship between the intensities of the images to register (affine, functional, statistical, ...), the approach consists in maximizing (or minimizing) a specified similarity measure between intensities of the corresponding pixels [START_REF] Davatzikos | Spatial transformation and registration of brain images using elastically deformable models[END_REF][START_REF] Viola | Alignment by maximisation of mutual information[END_REF]. These approaches have several issues [1]. First, all the similarity measures are known to be highly non-convex with respect to the transformation parameters. Thus their global maximization is seldom straightforward. Secondly, the assumption of a global relationship between the image intensities may be violated by the presence of various image artefacts.

Presentation of the problem

The problems mentioned above have been addressed by hybrid registration methods. Such methods combine feature and intensity information [1, [START_REF] Cachier | Multisubject non-rigid registration of brain mri using intensity and geometric features[END_REF][START_REF] Hellier | Cooperation between local and global approaches to register brain images[END_REF][START_REF] Johnson | Consistent landmark and intensity-based image registration[END_REF][START_REF] Rohr | Elastic registration of electrophoresis images using intensity information and point landmarks[END_REF][START_REF] Shen | Image registration by local matching histogram[END_REF].

However, these methods still require a pre-segmentation of features or take spatial regions of interest independently of the image context. For example, the block-matching algorithm [1], a local iconic method, determines a displacement field based on intensity similarity on small sub-blocks of the image, before determining a global transformation. The blocks have a fixed size and shape and are determined independently of the local structure of the image. Local displacements cannot be accurately computed in homogeneous areas or for large transformations [START_REF] Commowick | Block-matching strategies for rigid registration of multimodal medical images[END_REF]. It can therefore lead to some outliers in the displacement field estimation. Some specific strategies including interpolation, regularization or robust optimization methods are then required to try to solve these problems [1].

Alternatively, approaches to get a more robust raw displacement field could be investigated. Combining the two strategies (estimating a robust raw displacement field and using a robust optimization method) should lead more easily to the expected transformation. The paper is organized in the following way. Section 2 gives the concepts and definitions of the General Adaptive Neighborhood (GAN) framework. Section 3 describes the GAN-based registration method including the computation of the displacement field and the optimization algorithm to estimate the transformation. Section 4 introduces a shape metric based on [START_REF] Lazebnik | A sparse texture representation using local affine regions[END_REF] that is used to measure the similarity between GANs and therefore to match the GANs. The performance of this metric is evaluated on a dataset of binary images. Finally, some qualitative and quantitatives results are exposed in Section 5 highlighting the accuracy and robustness of the proposed registration method. The last section is devoted to the conclusion. In this study, the method is described in two dimensions (2D) and the geometric transformation is limited to rotations and translations.

Aims and outline of the paper

GAN image representation

This paper deals with 2D intensity images, that is to say image mappings defined on a spatial support D in the Euclidean space R 2 and valued into a gray tone range, which is a real number interval. The General Adaptive Neighborhood paradigm has been introduced [START_REF] Debayle | Spatially Adaptive Morphological Image Filtering using Intrinsic Structuring Elements[END_REF] in order to propose an original image representation for adaptive processing and analysis. The central idea is based on the key notion of adaptivity which is simultaneously associated to the analyzing scales, the spatial structures and the intensity values of the image class to be addressed (see Subsection 2.2). This section aims to recall the concepts and definitions of the GAN framework. The interested reader can look at the references [2, 28] for more details.

GANs sets

In the so-called General Adaptive Neighborhood Image Processing (GANIP) approach [2, 28], a set of General Adaptive Neighborhoods (GANs set) is identified around each point in the image to be analyzed. A GAN is a subset of the spatial support constituted by connected points whose measurement values, in relation to a selected criterion (such as luminance, contrast, thickness, . . . ), fit within a specified homogeneity tolerance. In this way, the computation of a GAN can be done by using a region growing process from the current point. These GANs are used as adaptive windows for image transformations or quantitative image analysis.

Several GANs sets have been defined and each collection satisfies specific properties [2]. This paper only presents the most elementary kind of these ones, denoted V h m (x). For each point x ∈ D and for an image f , the GANs V h m (x) are subsets of D. They are built upon a criterion mapping h (based on a local measurement such as luminance, contrast, thickness, . . . related to f ), in relation with an homogeneity tolerance m ∈ R + . More precisely, V h m (x) is a subset of D fulfilling two conditions :

1. its constituting points have a measurement value close to that of the point x :

∀y ∈ V h m (x) |h(y) -h(x)| ≤ m 2. the set is path-connected (with the usual Euclidean topology on D ⊆ R 2 ).
The GANs are mathematically defined as follows for each point x ∈ D:

V h m (x) = C h -1 ([h(x)-m,h(x)+m]) (x) (1)
where C X (x) denotes the path-connected component [START_REF] Choquet | Topology[END_REF] (with the usual Euclidean Note that two distinct points x and y may lead to the same GAN. For example, if

topology on D ⊆ R 2 ) of X ⊆ D containing x ∈ D.
h(x) = h(y) and x ∈ V h m (y) then V h m (x) = V h m (y).

GAN paradigm

A multiscale image representation such as wavelet decomposition [START_REF] Mallat | A Theory for Multiresolution Decomposition : The Wavelet Representation[END_REF] or isotropic scale-space [START_REF] Lindeberg | Scale-Space Theory: a Basic Tool for Analysing Structures at Different Scales[END_REF], generally takes into account analyzing scales which are global and a priori defined, that is to say extrinsic scales. This kind of multiscale analysis presents a main drawback since a priori knowledge, related to the features of the studied image, is required. On the contrary, the GAN framework is an intrinsic multiscale representation, such as anisotropic scale-space [START_REF] Perona | Scale-Space and Edge Detection using Anisotropic Diffusion[END_REF], where scales are self-determined by the local image structures. Such a decomposition does not need any a priori information. The GAN image representation is thus adaptive with respect to the different scales of the image representation.

Furthermore, the image processing techniques using spatially invariant transformations, with fixed analyzing neighborhoods, give effective and compact computing structures, in the sense where data and operators are independent. Nevertheless, they have several drawbacks such as creating artificial patterns, changing the detailed parts of large objects, damaging transitions or removing significant details [START_REF] Arce | Detail-Preserving ranked-order based filters for image processing[END_REF]. Alternative approaches towards context dependent processing have been proposed [START_REF] Gordon | Feature Enhancement of Mammograms using Fixed and Adaptive Neighborhoods[END_REF]. The GAN image representation is one of them in the sense that it supplies spatially adaptive analyzing neighborhoods which are no longer spatially invariant, but vary over the whole image, taking locally into account the image context. The GAN image representation is thus adaptive with respect to the spatial structures.

The next section exposes the GAN-based image registration method. The proposed approach is focused on the class of rigid transformations. Note that it could be extended to other classes of transformations with appropriate similarity measures and optimization algorithms but it is out of the scope of this paper.

GAN-based image registration

The proposed method takes two images as input: a reference image I and a floating image J. The output is a transformation T bringing the two input images into spatial alignment. It is based on the block-matching strategy, where two successive tasks are performed with a multiscale and iterative scheme (Subsection 3.3):

• computing a displacement field (i.e. a set of displacement vectors) between I and J (Subsection 3.1),

• gathering these displacements to determine the global transformation T using a robust estimator (Subsection 3.2).

GAN matching: computation of the displacement field

A displacement field is determined by computing correspondences between pixels of the two input images I and J. For each pixel x of the spatial support of the image I, the GAN V I m (x) is computed and its best correpondence (with respect to a dissimilarity measure DM) with the GANs V J m (y) is sought in the image J for pixels y within the neighborhood of x. Note that the size m of the GANs is an important parameter to be chosen for this matching. This GAN matching is mathematically defined as:

ŷ = arg min y∈N (x) DM(V I m (x), x, V J m (y), y) (2)
where N (x) is the search neighborhood of x in the image J, and DM is the dissimilarity measure between GANs exposed in Section 4.

The best corresponding GAN V J m (ŷ) allows to define a displacement vector, (x, ŷ) between the pixel x of the reference image and the pixel ŷ of the floating image.

The GAN-matching involves three parameters:

• the grid step size (∆ x , ∆ y ), underlying the spatial support of the image I, is introduced and determines the density of the displacement field. For (∆ x , ∆ y ) =

(1, 1), displacement vectors are calculated for all pixels of the spatial support of the image;

• the size of the neighborhood search N (x) that is constant (fixed-size) over the whole image; and

• the homogeneity tolerance m for the computation of the GANs.

The main difference of this GAN matching algorithm with the block-matching one is the adaptivity of the blocks to be matched: fixed-size and fixed-shape blocks are replaced by variable-size and variable-shape blocks by using GANs.

Least trimmed squares minimization: estimation of the transformation T

The proposed GAN-matching algorithm provides a list of N corresponding 2D points, x k and y k . Assuming that there exists a rigid transformation T between the input images I and J, the problem is to estimate a rotation matrix R and a translation vector t that characterize the displacement. A standard approach to solve such a problem is to perform a Least Squares (LS) minimization on the residuals

r k (R, t) = y k -Rx k -t.
The main advantage of the LS estimator is that the solution is unique and is quickly computed. However, LS is known to have poor robustness properties, in the sense that its solution is sensitive to outliers. M-estimators [START_REF] Zhang | Parameter estimation techniques: a tutorial with application to conic fitting[END_REF] appear to be the most straightforward alternative to LS to get a more robust estimation. In our experiments, the rigid transformation is estimated by Least Trimmed Squares (LTS) minimization [1].

It consists in solving the following minimization problem: Equation 3 is solved by means of a simple iterative LS estimation.

( R, t) = arg min R,t q k=1 ||r (k) (R, t)|| 2 (3)

The iterative and multiscale scheme

For more accuracy, the method follows an iterative scheme [1]. At step n, the transformation T n is estimated, (T n ) -1 is then applied to the floating image J and the process is again performed at step n + 1 between images I and J • (T n ) -1 to obtain the transformation T n+1 . At each iteration, the current transformation is updated according to T n+1 ← T 1 • ... • T n , the new floating image J • T n+1 -1 is therefore obtained by resampling only once the image J. This iterative scheme enables to enhance the accuracy of the registration method.

In order to recover large displacements without considering large search neighborhoods N (x), the method is implemented in a multiscale scheme (coarse-to-fine analysis) [1]. It enables a trade-off between performance and computational cost. In this manner, large but inaccurate displacements are determined at high levels, and small but more accurate ones are found when the scale decreases. The multiscale scheme is based on a pyramidal representation of the two input images I and J. At each level i of the pyramid, a displacement field is computed between the two subsampled images I i and J i and a transformation T i is estimated. (T i ) -1 is then applied at the next level i -1 of the pyramid before calculating a new displacement field between I i-1

and J i-1 • (T i ) -1
. Thereafter, the transformation T i-1 is estimated. The process is repeated up to the lowest level of the pyramid (i.e. at the highest resolution).

This iterative and multiscale scheme involves two additional parameters to the GAN-based image registration:

• the number i of pyramid levels in the multiscale representation; and

• the number n of iterations at each level of the pyramid.

The next section presents the dissimilarity measure for GAN matching, required to compute the displacement field.

The GAN dissimilarity measure

The computation of the displacement field (Eq. 2) between the two input images involves a dissimilarity measure DM between GANs, which are planar shapes of the spatial support of the images. Therefore, it is necessary to use a geometric measure (shape metric) as opposed to intensity-based measures (such as correlation coefficient, mutual information, ...). Note that the GANs are already computed using the image intensities.

Several shape metrics have been proposed in the literature. The Hausdorff distance [START_REF] Huttenlocher | Comparing images using hausdorff distance[END_REF] is a classical shape metric used to determine the degree of ressemblance between two objects that are superimposed. It measures the minimum distance between any point of one set from some point of the other set. This distance is particular in the sense that no descriptor is required. Nevertheless, this distance is not invariant to rigid tranformations and is sensitive to noise [START_REF] Veltkamp | Properties and Performance of Shape Similarity Measures[END_REF].

Other shape metrics are based on the similarity between descriptors of the shapes, where the descriptor should satisfies several conditions:

• invariance: the description of the shape should be invariant to the expected image deformation;

• uniqueness: two different shapes should have different descriptions; and

• continuity: the description of a shape which is slightly deformed in an unknown manner should be close to the description of the original shape.

Many authors used contour-based descriptors of the shapes. Peli [START_REF] Peli | An algorithm for recognition and localization of rotated and scaled objects[END_REF] proposed a simple and fast shape description using radial shape vectors but the usage of this method is limited to star-shape regions only. A generalized shape description in form of a binary matrix was proposed in [START_REF] Goshtasby | Description and discrimination of planar shapes using shape matrices[END_REF]. This shape matrix description is invariant, continuous but time consuming. The Fourier descriptors describe a shape by a fixed number of sample points on the boundary and further transformed to the frequency domain using a Discrete Fourier Transform. Nevertheless, the Fourier descriptors can describe only a single closed curve shape. So, shapes with holes are not considered.

Another group of methods uses region-based descriptors of shapes. Hu [START_REF] Hu | Visual pattern recognition by moment invariants[END_REF] derived seven orthogonal invariant moment descriptors of order 2 and 3. The first six descriptors encode a shape with invariance to translation, scale and rotation. The seventh descriptor ensures skew invariance, which enables to distinguish mirrored images.

Flusser and Suk derived the affine transform invariants [START_REF] Flusser | Pattern recognition by affine moment invariants[END_REF]. These decriptors are easy to implement, little time consuming but not continuous. Tang et al. [START_REF] Tang | Hierarchical kernel-based rotation and scale invariant similarity[END_REF] have recently proposed a rotation and scale invariant similarity measure based on hierarchical kernels but the method needs to define adequate templates which is still an open problem.

In our particular case, the dissimilarity measure DM between GANs should fulfill another condition. Indeed, two GANs V I m (x) and V J m (z) with exactly the same shape but with different seed positions x and z inside the GANs have to be discriminated to avoid bad matches (see Figure 2).

x

y z = = V J m (z) V J m (y) V I m (x)
Figure 2: GAN dissimilarity measure: importance of the seed position inside the GANs. The three GANs V I m (x), V J m (y), V J m (z) have the same geometrical shape. However, the match

(V I m (x), V J m (y)) is correct (DM = 0) while (V I m (x), V J m (z))
is not (DM = 0). Indeed, the GANs of the two seeds y and z are equal (in terms of spatial region) but their descriptors h V J m (y),y and h V J m (z),z are different because the location of the seed point is taken into account.

Therefore, the shape descriptor has to be dependent on a reference point.

Furthermore, the computation of the dissimilarity measure between GANs will be performed a great number of times for the displacement field estimation. So, an additional requirement to the metric is needed: the shape metric should be little time consuming.

The proposed shape metric

The proposed metric for matching two shapes is based on the descriptor presented in [START_REF] Lazebnik | A sparse texture representation using local affine regions[END_REF] but it is here defined for binary images which represent the shapes.

In the following, the definition of the proposed shape metric is firstly given before evaluating its performance.

Definition

Let A and B be two shapes. For defining the descriptor of A, the distance values d(y, x) between points y within A and a reference point x are considered (Fig. 3). The descriptor h A,x of the shape A is mathematically defined as the distribution (histogram) of the distance values d(y, x) from the reference point x.

h A,x (u) = y∈A χ {0} (d(y, x) -u) (4)
where χ is the characteristic function.

In [START_REF] Lazebnik | A sparse texture representation using local affine regions[END_REF], the histogram of gray levels at distance u is used for defining the descriptor of a gray-level image, while here it is the number of pixels at distance u.

The proposed shape metric DM between two shapes A and B, with its two reference points x and y, is then defined as the Manhattan distance between the two descriptors:

DM(A, x, B, y) = d |h A,x (u) -h B,y (u)| (5)
Note that these two shapes A and B will later play the role of two GANs for which the dissimilarity is measured in the displacement field computation (Eq. 2). The descriptor of each GAN will naturally be built with its seed (current) point as reference point.

DM is invariant to rigid transformations (translation and rotation): if T denotes such a transformation, DM(A, x, T (A), T (x)) = 0. Note that it is also invariant to mir-ror transformations which can lead to some ambiguities in certain applications. Computing this distance between two shapes is few time consuming since the descriptor of each shape can be quickly calculated by using a distance map [START_REF] Maurer | A linear time algorithm for computing exact euclidean distance transforms of binary images in arbitrary dimensions[END_REF].

Performance tests

To evaluate the performance of the proposed shape metric DM, a first comparison between pairs of similar shapes -from the Kimia dataset [START_REF] Sharvit | Symmetry-based indexing of image databases[END_REF]-along a continuum is performed (Tab. 1). Thereafter, the distance is tested (Tab. 2) with different categories of animals (fishes, rabbits, birds and camels) from the same dataset [START_REF] Sharvit | Symmetry-based indexing of image databases[END_REF] for shape classification. The distance between shapes are computed by using the equation 5 and the reference points used for the shapes are their barycenters. In this way, the distance between 2 shapes A and B is given by: DM(A, bar(A), B, bar(B)) where bar(A) and bar(B) denote the barycenter of A and B, respectively. Each bin of the histogram counts pixels within a distance range of three pixels for computing the histograms 1, the first rows shows that as the quadrangle moves toward the triangle, the distance increases. An exception is observed for the fourth shape because of a best match with a π rotation angle of the shape. Regarding Table 2, the animals are well categorized. Indeed, for each tested animal (in one row), the three best results are achieved for the animals of its category.

In the following experiments, the noise sensitivity of the proposed shape metric is studied on the whole Kimia dataset. The performance is evaluated by considering two types of noise:

• Pepper noise: a percentage of all the pixels are reassigned as background pixels (black pixels). In the experiments, the noise amount is related to this percentage value going from 0.05 to 0.5 (with a step of 0.05).

• Boundary noise: pixels on the image border are spatially randomly reassigned from their initial location to produce the deformed shape. In the experiments, the noise amount is related to the maximal displacement for both the x and y coordinates, going from -5 to 5 pixels (excluding 0, with a step of 1). malirity measure on the whole Kimia dataset is given as a function of the noise amount which is labeled from 1 to 10 for both boundary and pepper noise parameters. One can notice that the proposed shape metric is more sensitive to pepper noise than boundary noise. Indeed, the proposed descriptor is a region-based descriptor: each value of the histogram can be affected by several pixels for the pepper noise as opposed to the boundary noise.

Note that the Manhattan distance used in the dissimilarity measure DM could be replaced by the Earth mover's distance if one wishes to be less sensitive with respect to a small shift of the reference points of the considered shapes. Indeed, with such a shift, some pixels of a shape counted up to a specific bin of the histogram could move to the neighboring bins. In this case, the Earth mover's distance would be more robust than the Manhattan distance.

All these experiments highlight the performance (continuity, classification accuracy, noise sensitivity) of the proposed shape metric.

Application to GANs

Using the proposed shape metric, it is possible to measure the dissimilarity between two GANs: DM(V I m (x), x, V J m (y), y), so as to find the best match according to Equation 2. As mentioned before, it is important to note that the descriptor of a GAN is naturally built with its seed (current) point from which it has been computed, and not with its barycenter. In this way, GANs with the same geometrical shape but with different seed positions can be discriminated (Fig. 2) to avoid mismatches.

The next section presents some qualitative results for the displacement field computation and thereafter for the registration of MR brain and retinal images, before presenting quantitative results.

Experimental results

This section aims to evaluate the performance of the proposed GAN-based registration method in comparison with the block matching method. Both algorithms firstly give a raw displacement vector field which is further used as input for the robust estimation of the transformation using the least trimmed squares minimization. The results of qualitative and quantitative experiments are given for standard and real images. Regarding Figure 6, the GAN-based displacement vectors are qualitatively accurate. Moreover, contrary to the classical block matching, the proposed method is able to compute accurate displacement vectors inside homogeneous areas as highlighted in the proposed binary images.

Displacement field estimation

As one can notice in Figure 7, the GAN matching method provides well-estimated displacement fields while much more outliers occur with the block matching method. Such a GAN-based displacement field is suitable for image registration.

Qualitative evaluation

Illustration on MR brain images

To qualitatively evaluate the GAN registration results, a rigid registration is performed on MR brain images. Proton density (PD) imaging and T1 imaging are used to discriminate anatomical structures based on their proton density or their T1 relaxation properties. Examples of intra PD/PD (Fig. 8) and inter T1/PD (Fig. 9) MR brain image registration are shown. The reference and floating images are superimposed before and after registration. After registration, the images superimpose perfectly: the rigid transformation is well estimated.

It can be noted that even with dissimilar intensities (Fig. 9), the registration succeeds: it is one of the strength of the proposed method, it is able to register data from different modalities. Indeed, the patterns of the two input images have similar shapes and consequently, GANs are consistently and accurately matched, and the optimization algorithm performed on the resulting displacement field provides the expected transformation.

Illustration on retinal images

In this subsection, an application on retinal images is investigated. The global objective is to reconstruct a comprehensive single image from multiple spatial images acquired from the same patient, in order to facilitate the disease diagnosis and treatment planning. In Figure10, the spatial rigid registration of a pair of retinal images is presented both with the classical block matching and the proposed GAN matching method.

One can note that the rigid transformation is badly estimated with the block matching method, contrary to the proposed GAN matching one. The main reason seems to be related to the presence of several uniform regions. Indeed, local displacements cannot be accurately estimated in homogeneous areas with fixed-size and fixed-shape blocks.

Mismatches between such blocks often occur contrary to the correspondances between

GANs which are spatially adapted to the underlying regions. For a full registration of such a pair or retinal images, note that nonlinear registration methods are required since the retina is not a planar surface (projective transformations are consequently needed for such 2-D images). The GAN matching is here quantitatively evaluated for rigid image registration and compared to the classical block matching on a dataset of twelve standard images of size 256 × 256 pixels, from Matlab (Fig. 11). For both algorithms, the following The metric used for comparing blocks in the block matching algorithm is the sum of squared differences between pixel gray levels.

For each image of the dataset, 100 random rigid transformations T are generated.

T is then applied to the original image I leading to the transformed image J. The registration between I and J is then performed by using the block and GAN matching, giving an estimated transformation T is given.

The registration is evaluated in terms of robustness, capture range and accuracy such as proposed in [START_REF] Commowick | Block-matching strategies for rigid registration of multimodal medical images[END_REF]:

• The robustness is defined as the percentage of random experiments being a success. The registration is considered a success if the final warping index

ω f = 1 #I v∈I ||T (v) -T (v)|| is lower than 1 pixel.
• The capture range of the algorithm is defined as the maximum initial warping

index ω i = 1 #I v∈I ||T (v)
-v|| for which it succeeds.

• The accuracy is defined as the average ω f for which it succeeds.

The performance of the algorithms is evaluated for small, medium and large displacements:

• T small : random rotation in the range [0, 20] degrees and random translation in the range [0, 5] pixels

• T medium : random rotation in the range [START_REF] Cachier | Multisubject non-rigid registration of brain mri using intensity and geometric features[END_REF][START_REF] Hu | Visual pattern recognition by moment invariants[END_REF] degrees and random translation in the range [5, 10] pixels

• T large : random rotation in the range [START_REF] Hu | Visual pattern recognition by moment invariants[END_REF]60] degrees and random translation in the range [START_REF] Brown | A survey of image registration techniques[END_REF][START_REF] Taubin | An improved algorithm for algebraic curve and surface fitting[END_REF] pixels

The results are summarized in Table 3. The different values denote the average for the 100 simulations and the twelve images of the dataset.

These results demonstrate that GAN and block matching algorithms achieve perfect registrations for small displacements with a robustness of 100%. For medium and large displacements, the GAN matching provides better results than the block matching in terms of robustness, capture range and accuracy. Indeed, contrary to the GANs, searching similar spatially-invariant blocks within the original and transformed images for such transformations (rigid displacements) often leads to wrong displacement vectors which explain the difficulty of the block matching to well register the images. In this paragraph, the impact of the GAN homogeneity tolerance m is studied. For these experiments, the 100 transformations are identical for each homogeneity tolerance value m so as to only evaluate the impact of this parameter. The GAN registration is achieved by using different values m varying from 0 to 50 with a step size of 5. The following graph (Fig. 12) shows the robustness of the proposed method as a function of the homogeneity tolerance values m of the GANs for small, medium and large displacements. The computed values denote the average for the 100 simulations and the 12 images of the dataset.

For small and medium displacements, the two curves in Figure 12 are monotonic while a maximum exists for the curve associated to large displacements. The value m = 35 gives good results for the small, medium and large displacements. Note that this value depends on the underlying images: it does not give necessarily the best performance for each individual image.

One can see the decreasing performance from m > 35 for large displacements.

Indeed, the GANs are truncated by the image borders caused by the transformation which is too large for the observation window. It means that for large displacements the spatial regions are not identical in the two images to be registered. It consequently leads to mismatches with the proposed shape distance. Using another distance between GANs, less sensitive to truncations or occlusions such as proposed in [START_REF] Hong | Shape matching using multiscale integral invariants[END_REF] for example, would probably increase the value of m from which the robustness starts to decrease.

For small and medium displacements, the same behavior would probably appear but for larger m values (m > 50). Indeed, the larger the homogeneity tolerance value m is, the larger the GANs are. For small and medium displacements, mainly very large spatial regions (i.e. GANs computed with large values m) will be truncated by the observation window.

Noise sensitivity

In this subsection, the performance of the proposed rigid image registration is evaluated in the presence of noise. In Figure 14 the robustness of the GAN matching and block matching methods is given as a function of the noise amount for small, medium and large displacements. As in the previous experiments, the computed values denote the average for the 100 simulations and the 12 images of the dataset. Both the reference and floating images are damaged by an additive Gaussian noise. The noise amount is related to its variance going from 0 to 0.02 with a step of 0.005. Figure 13 illustrates two damaged images of 'Lena' with the minimal (0.005) and maximal (0.02) amount of noise. The results show that in noisy conditions the GAN matching method outperforms the block matching one. Moreover, the proposed method is less sensitive to Gaussian noise than the classical method: the overall approximated slope of each GAN matching curve is lower than its corresponding block matching curve.

Computational time

In this subsection, some experiments have been done to give the computational time for both the block matching and GAN matching methods. The algorithms have been run on a 64 bits Dual Intel Xeon X5650 Processor (2 x 6 cores at 2.66Ghz) with the Matlab software running in parallel on 22 threads. In Table 4, the average CPU time per image (computed on the image database for which the registration is a success) are given in seconds. The rotations R and translations t have been fixed to (R = 10 o , t = 2.5px), (R = 30 o , t = 7.5px), (R = 50 o , t = 12.5px) to represent a small, medium and large displacements, respectively. One can note that the GAN matching is less efficient with respect to computation time than the block matching but it provides better results in terms of robustness and accuracy. It is also interesting to note that the computational time for GAN matching does not increase with the size of the deformation.

Conclusion

In for image rigid registration and opens large perspectives for nonlinear approaches [START_REF] Modersitzki | FAIR: Flexible Algorithms for Image Registration[END_REF].

Indeed, for nonlinear registration, the same process could be applied in order to extract a robust vector field. The main constraint concerns the dissimilarity measure used for matching GANs that should be modified so as to get new invariance and/or robustness properties [START_REF] Hong | Shape matching using multiscale integral invariants[END_REF] with respect to the expected tranformation.

  This paper aims to propose a new hybrid (feature and intensity-based) registration method. It is based on the block matching algorithm [1]: but contrary to the latter, it computes and matches spatially-variant sub-blocks of the images, called General Adaptive Neighborhoods (GANs) [2], before determining a global transformation. These neighborhoods represent the patterns within the grayscale images: they are adaptive with respect to the image intensities and the image spatial structures. The GANs are determined by the image itself and should provide a more robust and accurate estimation of the displacement field.

Figure 1

 1 Figure 1 illustrates the GANs of two points computed with the luminance criterion on a retina image. The GANs are self-determined by the local structures of the image.

  Figure 1: The GANs of the two selected points of the original image (a) are homogeneous with respect to the luminance criterion (b) using the tolerance m = 10.

  based on the ordered residuals ||r (1) || ≤ ||r (2) || ≤ • • • ≤ ||r (N ) || where ||.|| denotes the Euclidean norm. The value of the parameter q is fixed to 0.7 × N in this paper to achieve a 70% breakdown point.

Figure 3 :

 3 Figure 3: Points y within the shape A whose distance to the specific point x is equal to u.

h

  A,bar(A) and h B,bar(B) of the shapes A and B.

Table 1 :

 1 Metric comparison between pairs of shapes along a continuum. For a better readability, the values have been divided by 20000. The first rows shows that as the quadrangle moves toward the triangle, the distance increases. An exception is observed for the fourth shape because of a best match with a π rotation angle of the shape (DM is invariant to mirror transformations).

Figure 4 Figure 4 :

 44 Figure 4 illustrates these two kinds of noise with the minimal and maximal amount of noise according to the selected parameters. In Figure 5 the average value of the dissi-

Figure 5 :

 5 Figure 5: Noise sensitivity of the proposed dissimilarity measure. The resulting values have been normalized by the area of the original image. The noise amount is labeled from 1 to 10 for both boundary and pepper noise parameters.

Figures 6

 6 Figures 6 and 7 compare the raw displacement fields computed with the block and GAN matching algorithms at the first iteration with the pyramidal level of highest resolution.

  (a) reference image I 1 and displacement field computed with block matching (b) reference image I 1 and displacement field computed with GAN matching (c) floating image J 1 (d) reference image I 2 and displacement field computed with block matching (e) reference image I 2 and displacement field computed with GAN matching (f) floating image J 2

Figure 6 :Figure 7 :

 67 Figure 6: Displacement field computation between two binary images (I 1 , J 1 ) and (I 2 , J 2 ) using block and GAN matching. The parameter m of the GAN is fixed to 0 while the size of the blocks is fixed to r = 7 and the vectors are only computed for pixels within the object. Contrary to the classical block matching, the proposed GAN-based method is able to compute accurate displacement vectors inside homogeneous areas.

Figure 8 :Figure 9 :

 89 Figure 8: PD/PD registration of MR images. The rigid transformation is well-estimated thanks to the GAN matching.

Figure 10 :

 10 Figure 10: Rigid registration of a pair or retinal images by comparing the block matching and the GAN matching. One can note that the classical method fails contrary to the proposed GAN-based method.

5. 3 .

 3 Quantitative evaluation 5.3.1. GAN vs. block matching

Figure 11 :

 11 Figure 11: Image dataset for the performance evaluation of the proposed GAN matching algorithm.

Figure 12 :

 12 Figure 12: Impact of the homogeneity tolerance for GAN rigid registration with small, medium and large displacements.

Figure 13 :

 13 Figure 13: Damaged images with an additive Gaussian noise using the minimal (var=0.005) and maximal (var=0.02) amount of noise according to the selected parameters.

Figure 14 :

 14 Figure 14: Noise robustness of the block and GAN matching methods as a function of the noise variance for small, medium and large displacements.

  this paper, a new hybrid (feature and intensity-based) image registration algorithm has been presented. It is based on the block matching algorithm and proposes a new way to calculate the displacement field by matching spatially-variant sub-blocks of the images, called General Adaptive Neighborhoods (GANs) [2]. These neighborhoods represent the patterns within the grayscale images: they are adaptive with respect to the intensities and the spatial structures of the image. The GANs are determined by the image itself and consequently enable a robust and accurate estimation of the displacementfield by GAN matching. A consistent shape metric has also been introduced so as to match the GANs. It provides a good trade-off between performance and computational cost. Several tests have been carried out on a shape dataset to evaluate the performance of the proposed metric. Thereafter, all information of the computed displacement field have been gathered to estimate (by an optimization algorithm) the transformation between two images for image registration. According to the performed experiments, the proposed GAN-based registration method works better than the classical BM method

Table 2 :

 2 Metric for the dataset. For a better readability, the values have been divided by 10000. The animals are well categorized: for each tested animal (in one row), the three best results are achieved for the animals of its category.

	0.00	0.07	0.07	0.16	0.13	0.20	0.24	0.17	0.18	0.46	0.51	0.50
	0.07	0.00	0.03	0.14	0.08	0.13	0.17	0.10	0.11	0.39	0.44	0.43
	0.07	0.03	0.00	0.14	0.09	0.14	0.17	0.11	0.11	0.39	0.44	0.43
	0.16	0.14	0.14	0.00	0.08	0.06	0.13	0.08	0.09	0.29	0.34	0.33
	0.13	0.08	0.09	0.08	0.00	0.06	0.14	0.09	0.10	0.32	0.37	0.36
	0.20	0.13	0.14	0.06	0.06	0.00	0.11	0.08	0.09	0.26	0.31	0.30
	0.24	0.17	0.17	0.13	0.14	0.11	0.00	0.08	0.09	0.25	0.32	0.30
	0.17	0.10	0.11	0.08	0.09	0.08	0.08	0.00	0.04	0.29	0.34	0.33
	0.18	0.11	0.11	0.09	0.10	0.09	0.09	0.04	0.00	0.27	0.33	0.32
	0.46	0.39	0.39	0.29	0.32	0.26	0.25	0.29	0.27	0.00	0.08	0.08
	0.51	0.44	0.44	0.34	0.37	0.31	0.32	0.34	0.33	0.08	0.00	0.07
	0.50	0.43	0.43	0.33	0.36	0.30	0.30	0.33	0.32	0.08	0.07	0.00

Table 3 :

 3 Quantitative evaluation of the proposed GAN matching (GM) algorithm with comparison to the block matching (BM) for 100 simulated transformations on a dataset of twelve images.

	Displacement Algorithm Robustness (%) Cap range (px) Accuracy (px)
	BM	100.00	33.41	0.24
	Small
	GM	100.00	33.41	0.20
	BM	93.58	65.62	0.27
	Medium
	GM	99.92	65.95	0.19
	BM	64.42	91.71	0.27
	Large
	GM	81.08	95.43	0.19
	5.3.2. Impact of the GAN homogeneity tolerance

Table 4 :

 4 Computational time (in average per image) of the proposed GAN matching (GM) algorithm with comparison to the block matching (BM) algorithm for small, medium and large displacements.

	Displacement Algorithm Time (s)
	BM	19
	Small
	GM	182
	BM	28
	Medium
	GM	172
	BM	34
	Large
	GM	195

Acknowledgment

The authors would like to thank Professor P. Gain from the University Hospital Center of Saint-Etienne in France who has kindly supplied the retinal images proposed in this paper. [1] S. Ourselin, A. Roche, S. Prima, N. Ayache, Block matching: A general framework to improve robustness of rigid registration of medical images, in: International Conference of Medical Robotics, Imaging And Computer Assisted Surgery, Vol. 1935 of Lectures Notes in Computer Science, Springer, Pittsburg, Pennsylvanie, USA, 2000, pp. 557-566. [2] J. Debayle, J. C. Pinoli, General Adaptive Neighborhood Image Processing -Part I: Introduction and Theoretical Aspects, Journal of Mathematical Imaging and Vision 25 (2) (2006) 245-266.