# Point matching based on affine invariant centroid trees – EURASIP Journal on Advances in Signal Processing

#### ByWei Wang, Xingwei Yan, Ge Zhao, Jianhua Shi and Jin Liu

Sep 6, 2022 In this section, AICT is coupled with DOPM to get a descriptor, which is named AICT-DOPM. We perform experiments both on synthetic data and real data to compare the performance of AICT-DOPM with state-of-the-art algorithms including SC, ICP, and TPS-PRM.

### Fundamental experiments on synthetic data

In synthetic data experiments, we generate a point set, in which 100 points uniformly distribute in 2D space with mean distance between neighbor points is normalized to 1. The point set is treated as the model, and target point sets are obtained under different levels of affine transformations, noise and outliers, respectively. To get noisy target point sets, the model points are firstly transformed by a random affine transformation, and then, the coordinates of deformed points are shifted in the range of ([ – e,e]). The level of noise is defined as

where d is the minimum distance between the point to the others in the point set. The outlier measurement, denoted by ODR, is defined as the ratio of the number of outlier to the number of original points. Figure 3 shows the distortions between the model and target point sets. The model is from Chui database.

The matching accuracy of descriptors is evaluated by the number of correct matches with respect to the number of currently existing matches. In addition, the correspondences between two point sets are used to estimate the affine transformation (T^{prime}). The matching error is quantified as the average Euclidean distance between the points in the transformed model point set under (T^{prime}) and (T). All results given in this subsection are the average results based on 100 independent trials.

#### Effect of depth on the performance

As described in Sect. 2, an AICT with depth (n) contains (2^{n} – 1) affine invariant points. Apparently, the deeper the AICT is, the stronger ability it has to capture the inherent structure of the point set. However, whether we can get better performance while the depth increases, and which depth is the best choice while the performance and computational complexity are both considered. To answer these questions, we test the effect of depth on the performance of AICT-DOPM when the points in AICT are all used to construct the SPS. The performance of AICT with various depth under affine transformations, outliers and noise are given in Fig. 4. Figure 4a1, a2, the matching accuracy and matching error of AICT-DOPM, denotes that the descriptor has excellent performance when the depth of the AICT is larger than 3. In these circumstances, the matching accuracy nearly all reach 100% while the matching error drop to 0. AICT with depth 3 has poor performance if the target point set is polluted by outliers (Fig. 4b1, b2). Though the performance is becoming bad as ODR increases, it is highly improved when the depth of the AICT is larger than 5. In addition, the performance just only fluctuates slightly if the depth continues to increase. The reason is that the AICT with depth 5 can represent the global structure of the point set well. Therefore, we prefer 5 to other larger value to be the depth of the AICT for point matching under outliers. Similarly, for point matching under noise (Fig. 4c1, c2), 5 is also an available option for the depth of the AICT.

#### Performance to affine transformations, outliers and noise

In this subsection, the performance of AICT with depth 5 is compared with SC, ICP and TPS-RPM.

##### Performance to affine transformations

An affine transformation includes rotation, scaling, and shearing transformations. The behavior of algorithms with respect to rotation is first tested. The target point sets are generated while the model point sets are rotated from 0° to 180° with 20° intervals. Experimental results in Fig. 5a1, a2 show that AICT-DOPM can nearly find all correspondences, whereas the matching accuracy and error of other algorithms fluctuate when the rotation angle changes. Especially for ICP and TPS-RPM, which highly depend on the initial correspondence, their performance get worse when the rotation angle is larger.

Then, the sensitivity of the descriptors with respect to scaling is evaluated. To obtain the target point sets, the model point sets are transformed while different non-uniform scaling values (i.e., (s_{x} /s_{y})) change from 1.2 to 3 in step of 0.2. The performance of algorithms on point matching is compared in Fig. 5b1, b2, and they denote that AICT-DOPM is more robust to non-uniform scaling.

To evaluate the behavior of the algorithms in relation to shearing, the target point sets are obtained when the model point sets are transformed according to different shearing factor (k), which are − 3, − 2, − 1, 0, 1, 2, 3. The matching results summarized in Fig. 5c1, c2 verify the invariance of AICT-DOPM to shearing.

##### Performance to outliers

The sensitivity of algorithms to outliers is tested when different numbers of outliers are added onto the random affine transformed model. Figure 5d1, d2 shows the matching accuracy and error against outliers, respectively. They depict that the accuracy of all algorithms decreases as the ODR increases, and AICT-DOPM has the best performance against outliers.

##### Performance to noise

Finally, the effect of noise on algorithms is observed. Figure 5e1, e2, the matching accuracy and error, denotes that AICT-DOPM is most robust to noise.

### Extended experiments on real data

The proposed algorithm can be used for object recognition once the objects are represented by point sets. In this subsection, the template image (Fig. 6a) and input image (Fig. 6b) are adopted to test the performance of our proposed algorithm on water region recognition. The two images, the real data taken over areas of Taiwan, were acquired by different sensors. The 11 water regions in the input image all have correspondences in the template image which has 24 regions. The closed water regions, which are extracted automatically by a simply threshold segmentation, are numbered, and their contours are labeled by white color in Fig. 6. In the experiment, the water regions are treated as point sets while the contours are sampled with 100 points by uniform spacing. For each region pair, the correspondences between contour points are found by algorithms to estimate the transformations between the two images, and then, the input region is transformed to be close to the template region. Finally, the registration accuracy is measured via the ratio of the area of common domain between the template and transformed input regions to the area of the template region. The larger the registration accuracy, the similar the two regions are. Figure 7 shows the matching results between the No. 7 water region in the template image (blue plus sign) and the No. 2 water region in the input image (red cycle) using different algorithms. The point matching results are given in the top row, and in the bottom row, contours of transformed regions are plotted on the templates to show the performance of algorithms intuitively. Furthermore, the water region recognition results of algorithms are summarized in Table 1. It demonstrates that AICT-DOPM is much better at point-based object recognition than SC, ICP and TPS-RPM.

## Rights and permissions

##### Disclaimer: 