# Feature-based alignment

Unlike direct methods, feature-based alignment relies on feature correspondences between images. Commonly, a detector detects interest points in images, while a descriptor describes the area around these keypoints. A matching scheme then extracts correspondences $X_1\leftrightarrow X_2$ between keypoints based on similarities between the respective descriptors. The optimum transform that explains these correspondences, up to some tolerance, is finally obtained by:

$\arg\min_W D(X_1,WX_2)$

where $D$ is the average point-wise distance between two point sets and $W$ the transform from one image plane to the other. Notice that the image should be of sufficient texture in order to detect and describe keypoints.

## Matlab examples

Let us load the following pair of images that are related by an affine transform:

 Template Image (to be warped)

 ```>> tmp = imread('textTemplate.png'); >> img = imread('textImage.png');```

An efficient, well-performing algorithm for keypoint detection-description is the SURF algorithm [1]. In order to extract SURFs from the images, we work as follows:

 ```>> [d1, l1]=iat_surf(img); >> [d2, l2]=iat_surf(tmp);```

iat_surf returns to `d1` and `l1` the descriptors and their locations (the first two columns of `l1`) of the keypoints of `img` (likewise for `tmp`). Since the image is highly-textured, too many SURFs are detected and matching is time consuming. Therefore, we use the MEX file of the function iat_match_features with the angle-ratio (the upper bound of the ratio second-best/best matching angle) being $0.7$:

 ```>> [map, matches, imgInd, tmpInd]=iat_match_features_mex(d1,d2,.7); >> X1 = l1(imgInd,1:2); >> X2 = l2(tmpInd,1:2);```

`X1` and `X2` contain corresponding points in `img` and `tmp` respectively. To see the correspondences, run the following command:

 `>> iat_plot_correspondences(img, tmp, X1', X2');`

 Correspondences

As shown, there are false positives in matching results (outliers). A direct estimation of the transform that relates the keypoints in the global sense may be affected by mismatches. To avoid such an influence, a RANSAC [2] scheme is invoked that finds the largest consensus set of correspondences and estimates the transform based on this set. In order to run the RANSAC algorithm, please type:

 ```>> X1h = iat_homogeneous_coords (X1'); >> X2h = iat_homogeneous_coords (X2'); [inliers, ransacWarp]=iat_ransac( X2h, X1h,'affine','tol',.05, 'maxInvalidCount', 10);```

The filtered correspondences owing to the RANSAC algorithm can be drawn by:

 `>> iat_plot_correspondences(img,tmp,X1(inliers,:)',X2(inliers,:)');`

 RANSAC-filtered correspondences

The function iat_ransac also returns the optimum warp, `ransacWarp` based on filtered correspondences, so that the warped image can be computed as follows:

 ```>> [M,N] = size(tmp); >> [wimage, support] = iat_inverse_warping(img, ransacWarp, 'affine', 1:N, 1:M); >> figure; imshow(tmp); figure; imshow(uint8(image));```

 Template Warped image

Pixel-wise error here might not be the best case to qualitatively assess the alignment owing to the image content (text). However, one can run it following the code provided here.

Demos – Matlab scripts

IAT provides Matlab scripts (demos) that automatically run alignment and display results.

Relevant demos: featureBasedAlignmentDemo, areaVsFeatureAlignmentDemo

## References

[1] H.Bay, A.Ess, T.Tuytelaars, L.V.Gool, “SURF: Speeded Up Robust Features”, Computer Vision and Image Understanding (CVIU), Vol. 110, No. 3, pp. 346–359, 2008

[2] Martin A. Fischler and Robert C. Bolles (June 1981). “Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography”. Comm. of the ACM 24 (6): 381–395