Fast Image Registration for Spacecraft Autonomous Navigation Using Natural Landmarks

2.1. PCA-SURF Description

Here, each column y₁ y₂ … y₆₄ of Y is the principal component. Compressing the dimension of the descriptor, then y_64,y₆₃, … can be removed sequentially, because the smaller the eigenvalues are, the less the information is.

2.2. Application of Image Registration

Image registration task will be completed by using the first m principal components which occupy a large proportion of the contribution rate. In order to find the best value of the cumulative contribution rate, some simulation results are presented in the following.

Figure 2 shows the repeatability of PCA-SURF with different cumulative contribution rates. Different lines in the figure represent the object image with different rotations. Figure 3 presents the remaining dimensions with different cumulative contribution rates. From the above comparison, it can be seen that PCA-SURF worked poorly when the rotation is larger than 20 degrees. When the rotation is less than 20 degree, the cumulative contribution rate can be chosen as 0.95; therefore, it can largely compress the dimension of the SURF descriptor with little accuracy loss.

3.1. Chessboard Segmentation Algorithm

According to [9–11], there are three strategies that can be implemented to speed up the image registration progress. The first strategy is to decrease the dimension of the key points’ descriptors. And the second one is to decompose the task and deal them with multithreads. The third is to decrease the number of key points. Here, in this paper, the latter two methods are used to improve the speed performance.

Chessboard segmentation algorithm, which combined these two ideas, can greatly improve the speed without losing performance of repeatability.

Figure 4 shows an island image that has been segmented into N × M parts. The number in each block represents the amount of SURF features. In order to speed up image registration progress, considering the second idea, the feature extraction tasks in each block will be allocated to different threads. Besides, by considering the third idea, only some representative blocks rather than all of them will be selected. In order to satisfy these requirements, several factors needed to be considered, for example, if the block with the most number of SURF features has been selected, then the weight of blocks around the chosen block should be decreased to make sure that regional distribution is more even. So, a block selection model should be established. The coordinate of each block is defined in Figure 4. And we suppose that S_i,j is the amount of SURF features of block D_i,j.

The entire diagram flow is presented in Figure 5.

The major steps of chessboard segmentation algorithm are as follows.

(1) Image Segmentation. In the first step, CSA splits the source image into N × M blocks. Simultaneously, the SURF features of each block will be extracted with the help of parallel computing technology.

(2) Data Normalization. Then the amount S_i,j of SURF features of each block will be normalized to establish the weight matrix W.

(3) Block Selection. In each step, the block with maximum weight among the candidate set will be selected and then be removed from the candidate set.

(4) Local Attenuation Effect. After the maximum weight has been selected, the weight coefficient around the selected block should minus a threshold T to simulate the local attenuation effect.

Two parameters will affect the stability of CSA: the number of blocks in x and y directions. The experimental determination of the number of blocks that maximizes the stability of CSA is shown in Figure 6, which is based on an image registration task by using a collection of different natural landmarks. The terms N_x and N_y in this figure represent the number of blocks in x direction and y direction. Besides, the size of the object image that needs to be matched with the reference image is 800 × 684. The origin of an image coordinate system is located at the upper left corner of the corresponding image.

Figures 7–9 present the results of CSA with different thresholds. In these figures, the selected blocks have been marked by green color. In Figure 7, the threshold T = 0 means that the local attenuation effect is invalid and illustrates that these blocks whose feature number is not equal to 0 are selected. Figure 8 shows the CSA result with the threshold T = 0.1 or 0.2. And Figure 9 shows the CSA result with automatic determined threshold T = 0.3333. It can be seen that Figure 9 gives the most typical and minimal number of blocks with the result of automatic threshold determination.

3.2. Random Sample Consensus Algorithm

Once the result of image registration is obtained, it is hard to analyze statistically the match ratio because it may have hundreds of matched key points in result. In this section, an algorithm called random sample consensus [12–14] is introduced to deal with the above problem. Besides, this algorithm also can be used to remove the wrong matched key points [15].

3.2.1. Perspective Transformation

Perspective transformation is a commonly used model to represent the relationship between two images from different views.

Figure 10 is a demonstration of perspective transformation. P₁ is a point in plane 1, and its coordinate is (x, y). Q₁ is the corresponding point in plane 2 with coordinate (u, v). In order to get the relationship between P₁ and Q₁, a perspective transformation matrix H is defined as

$$ (14)

Then the relationship between P₁ and Q₁ is

$$ (15)

where λ is the scaling factor. By dividing the first and second rows with the third row, it will achieve

$$ (16)

Then we assume that $$; to transfer the above equation into the matrix form, we can obtain

$$ (17)

In order to solve $$, four or more corresponding pairs are required. So, we suppose that there are four known corresponding groups P₁, P₂, P₃, P₄ and Q₁, Q₂, Q₃, Q₄, and satisfying

$$ (18)

it can be simplified as

$$ (19)

Because of distortion, noise, or other reasons, the above equation may be a contradictory equation. Therefore, the least squares method is applied to find the satisfied result

$$ (20)

Eventually, the perspective transformation matrix H can be recovered from $$.

Assuming that P(x, y) is the key point in the first picture. Q(u, v) is the corresponding matched key point in the second image. H₁ is the perspective transformation matrix between the first and second image. Then we have

$$ (21)

where (x^′, y^′) is the corresponding point after perspective projection transformation on key point P. Then the perspective projection error can be defined as follows:

$$ (22)

3.2.2. RANSAC Algorithm Progress

Figure 11 shows the diagram flow of RANSAC algorithm. The main stages of RANSAC algorithm are described as follows:

(1) Initialization. The threshold of minimum perspective project error T_ppe should be initialized at first. Besides, the maximum iterator time M_iter should also be initialized here.

(2) Perspective Transformation Solving. The perspective transformation H can be solved by least squares method with four groups of key points, among which four key points are randomly selected from the dataset of source image key points. The other four key points are randomly selected from the dataset of target image key points.

(3) Perspective Matrix Validation. Once a new perspective projection error has been obtained in each iterator, a validation needs to be performed. The minimum of perspective projection error Err between the key points of the source image and the key points of the target image will be calculated. If Err is smaller than the smallest perspective projection error E_min which is stored before, the minimum perspective projection error E_min will be updated.

(4) Loop Termination. If E_min > T_ppe and iterator > M_iter, the loop will go back to step 2; otherwise, the loop will be terminated.

4.1. Time Consumption for Feature Extraction

It is well known that SIFT or SURF algorithms use the sliding window method to detect local extrema. PCA-SURF and CSA-SURF, having the same mechanism, are the improved algorithms based on SURF. However, there are some differences among them. In order to descript more clearly, the width and height of the image are defined as I_w and I_h and the step size is σ. The time for solving the eigenvalue and eigenvector is T_eig. The time for transferring the old feature space to the new feature space is T_tran. The time for computing the local feature is T_local. The extraction times of SURF, PCA-SURF, and CSA-SURF are $$, $$, and $$, respectively. The pseudocodes for the feature extraction progress of SURF, PCA-SURF, and CSA-SURF algorithms are presented as in Pseudocodes 1, 2, and 3.

The relationship of (24) can be proven as follows.

Therefore, (24) has been verified.

4.2. Time Consumption of Matching

For the spacecraft autonomous navigation problem using natural landmarks, only 5 to 10 features satisfying certain relative distance constraints are required; therefore, it is easy to guarantee that(M/N)² < N²/l and then we have $$.

From the above comparison, the proposed CSA-SURF method consumes the least time.

5.1. Evaluation Metrics

In order to descript the repeatability performance, the following evaluation metrics are defined in this section. Positive in this paper means the key points that can be matched. Negative means the key points that cannot be matched.

Then we suppose that γ_TP is the number of positive key points that are correct matches. γ_FP is the number of negative key points that are false matches. γ_TN is the number of negative key points that correct mismatches. And γ_FN is the number of negative key points that are false mismatches. To explain it more clearly, Figure 12 shows the relationship of different symbols.

Precision means the proportion of correct matches to positive. Recall means the proportion of correct matches to matches. Recall and precision are conflicting, so a recall versus precision graph will help in analyzing the repeatability performance.

5.2. Speed Test

The following experiments are tested on Core I5 2.3 GHz CPU, 6GB RAM laptop with Windows 7 operation system. VS2013 and OpenCV2.4 are used to carry out all the experiments. And all datasets are from an open source database called UC Merced Land Use Dataset. And the resolution is 256 × 256.

Figures 13–15 are the matching comparison results of fifty images about SURF, PCA-SURF, and CSA-SURF. It can be seen that PCA-SURF consumes much more time than SURF and CSA-SURF during feature extraction process. The CSA-SURF algorithm works faster than SURF and PCA-SURF algorithms for both feature extraction and matching processes.

5.3. Repeatability Test

Figure 16 shows the repeatability of different methods for different conditions. But recall and precision may be conflict in some condition, so a recall versus precision graph has been established to help us analyze the repeatability performance. The red line is the test under scaling; it can be seen that CSA-SURF performs worse when precision < 0.2 and its performance is not stable when 0.2 < precision < 0.45. For precision < 0.45, it works well with recall = 1. The green line represents the test of CSA-SURF algorithm under rotation. Its performance is much the same as the solid line’s case, while its unstable region is 0.2 < precision < 0.4. The blue line represents the test of CSA-SURF algorithm under salt and pepper noise [16] with a noise density equal to 0.35. It can be seen that CSA-SURF algorithm is not stable under salt and pepper noise, but recall still maintains its value above 0.7.

Furthermore, the above dataset with fifty images is also used to test the repeatability performance of the three methods. Figure 17 is the recall of different methods for these images. The results show that the repeatability of SURF and CSA-SURF is very close. Therefore, CSA-SURF can speed up the registration progress without losing its repeatability performance. However, PCA-SURF is unstable as it can get the correct matches in some conditions.

5.4. Application on Natural Landmark Registration

The major purpose of this paper is to apply the proposed method into natural landmark registration task. Five different kinds of natural landmarks, including island, airport, railway, river, and coastline, are collected for the demonstration testing.

Figure 18 presents the registration results for Hawaiian islands with different algorithms, in which SURF and CSA-SURF work fine but PCA-SURF has a wrong match. Figure 19 shows the matching results of two O’Hare International Airport images with different algorithms, indicating that the PCA-SURF algorithm is unstable as it cannot find any matched key points in this example. Figures 20–22 are the matching results of Qingzang railway, river, and coastline images with different algorithms.

It can be seen from the above testing results that CSA-SURF algorithm works well for different images with significant contour features. The proposed CSA-SURF algorithm, which is improved from SURF, keeps the repeatability of SURF unchanged and improves the image matching speed. Many other pictures have also been tested; however, the results are not presented for the page limitation of the paper.