CN117218389B - Dimensionality reduction parallel image feature matching algorithm integrating principal component analysis and double stack filtering - Google Patents

Abstract

The invention discloses a dimension-reducing parallel image feature matching algorithm integrating principal component analysis and double-stack filtration, which comprises the following steps: projecting a reference feature point set in an image in an original space and a query feature point set in another image to a low-dimensional PCA space by adopting a principal component analysis method; dividing a reference feature point set R' into w subsets in a PCA space; filtering the reference feature points in the w subsets by adopting a double-heap filtering algorithm to generate k nearest neighbor results of each subset; and sequentially adding the k nearest neighbor results of each subset into a maximum heap, and adjusting the maximum heap so as to generate the k nearest neighbor results in the maximum heap. The invention adopts a principal component analysis method to project the feature point set into a low-dimensional space, and adopts a square Euclidean distance with lower calculation cost to carry out ranking estimation; the feature points are purified by using a double-pile filtering algorithm, so that the precision of feature matching is ensured; and a parallel structure is adopted, so that the matching speed of the image characteristic points is improved.

Description

Dimensionality reduction parallel image feature matching algorithm integrating principal component analysis and double stack filtering

Technical Field

The invention relates to the technical field of image feature matching, and in particular to a dimensionality reduction parallel image feature matching algorithm integrating principal component analysis and double-stack filtering.

Background Art

The on-board panoramic view system can significantly improve the intelligent vehicle's perception of the surrounding road environment and driving safety by stitching together local road images captured by multiple on-board camera points and outputting a 360° panoramic view image centered on the current vehicle in real time. The core of the on-board panoramic view technology lies in the efficient matching of high-dimensional feature points between different local road images. Considering the real-time requirements of intelligent driving for road environment perception, how to efficiently and accurately match the massive high-dimensional feature points between local road images has become a hot spot and difficulty in the current intelligent driving field.

At present, some scholars have carried out research on feature matching of high-dimensional images, which can be roughly divided into the following three categories:

(1) Brute force matching method, that is, by comparing the similarity of the feature points to be matched with the reference feature points one by one, the reference feature points with the highest similarity are found as the best match. Tian Jiahe et al. adopted a brute force matching method based on Euclidean distance to compare the similarity of the feature points to be matched, and determined the matching point pairs based on the ratio test of the dynamic threshold, which effectively improved the matching robustness. Xie Hongmei et al. proposed a two-way brute force matching strategy. For the feature point pairs to be matched, the distance ratio between their respective nearest neighbors and second nearest neighbors is calculated, and the threshold is adaptively adjusted according to the change in the number of point pairs to be matched, which effectively solves the "one-to-many" matching problem. This type of algorithm can quickly obtain accurate matching when the number of features is small and the dimension is low, but when faced with high-dimensional feature point matching problems, the matching efficiency of this type of algorithm is limited.

(2) Feature dimensionality reduction method, that is, by converting the high-dimensional feature representation of the image into a low-dimensional feature representation, the computational complexity is reduced and redundant information is removed to achieve more effective and accurate image feature matching. Zhang T et al. introduced a circular area descriptor extraction method based on the SURF algorithm, reduced the dimension of the descriptor, and used the minimum Euclidean distance criterion for matching, which effectively improved the matching speed. Li Xuan et al. proposed a feature dimensionality reduction method based on local linear embedding, which maintained the local linear relationship of the features while reducing the dimension, and enhanced the robustness during deformation and rotation matching. Although such algorithms can optimize the dimension of feature descriptors and improve matching speed to a certain extent, the degree of dimensionality reduction is limited and is not suitable for massive high-dimensional feature points between road images.

(3) Deep learning matching algorithm, that is, to obtain the matching rules between high-dimensional feature points through large-scale data learning, so as to achieve efficient and accurate feature point matching. Duan Yunshan et al. used CNN based on homography transformation to extract feature points, and used a neural network with a cross-attention mechanism to match high-dimensional feature points, which effectively solved the problem of poor feature matching under large parallax and distortion transformation. Song Jiaxuan et al. combined neural network to fuse image grayscale information to form a feature description grid, and used the same-name point to constrain the matching area for group matching, which effectively solved the matching problem caused by the sudden change of image cross-view feature content. This type of algorithm can automatically learn feature representation and process high-dimensional feature relationships, but feature matching based on artificial intelligence requires large computing resources, has poor real-time performance, is sensitive to abnormal data, and is prone to overfitting.

It can be seen that the current algorithms for high-dimensional feature matching have problems of low matching efficiency and poor real-time performance, and there is still a lot of room for improvement before they can be applied in vehicle-mounted panoramic surround view systems. In order to meet the requirements of the vehicle-mounted panoramic surround view system for local road image stitching in terms of real-time performance and matching accuracy, a new image feature matching algorithm needs to be proposed to improve the matching speed of image feature points and ensure the accuracy of feature matching.

Summary of the invention

The technical problem to be solved by the present invention is to provide a dimensionality reduction parallel image feature matching algorithm that integrates principal component analysis and double-pile filtering in response to the deficiencies of the above-mentioned prior art. The algorithm uses principal component analysis to project the feature point set into a low-dimensional space, and uses the squared Euclidean distance with lower computational cost for ranking estimation to perform feature point matching; in order to eliminate mismatching, a double-pile filtering algorithm is used to purify the feature points to ensure the accuracy of feature matching; a parallel structure is adopted, which can be easily extended to multi-core systems, thereby improving the matching speed of image feature points and meeting the real-time requirements of panoramic view technology for local road image fusion.

In order to achieve the above technical objectives, the technical solution adopted by the present invention is:

A dimensionality reduction parallel image feature matching algorithm integrating principal component analysis and double-stack filtering comprises the following steps:

Step 1: The two images to be matched are recorded as and image The feature points in the image are recorded as query feature points. The feature points in are recorded as reference feature points;

Step 2: Use principal component analysis to transform the image in the original space The reference feature point set R and image in The query feature point set Q in is projected into the low-dimensional PCA space to obtain the projected reference feature point set R ^′ and the query feature point set Q ^′ respectively;

Step 3: Determine whether there is a reference feature point in the reference feature point set R that correctly matches the query feature point q _i in the query feature point set Q:

Step 3.1, in the PCA space, divide the reference feature point set R ^′ into w subsets; the projection point of the query feature point q _i onto the low-dimensional PCA space is recorded as the query feature point q _i ^′ ;

Step 3.2: Use the double-heap filtering algorithm to filter the reference feature points in the w subsets respectively, and generate the k nearest neighbor results of each subset;

Step 3.3, add the k nearest neighbor results of each subset to the maximum heap in turn, and adjust the maximum heap so that the k nearest neighbor results are generated in the maximum heap;

Step 3.4, select the reference feature point closest to the query feature point q _i ^′ in the k nearest neighbor results in the maximum heap, and calculate the pixel distance between it and the query feature point q _i ^′ . If the pixel distance is less than or equal to the preset pixel, then the point corresponding to the reference feature point in the original space is determined to be the reference feature point correctly matched with the query feature point q _i . Otherwise, it is determined that there is no reference feature point correctly matched with the query feature point q _i in the reference feature point set R.

Step 4: According to the method in step 3, determine whether each query feature point in the query feature point set Q has a correctly matched reference feature point, and then obtain all correct matching point pairs to achieve image With image feature matching.

As a further improved technical solution of the present invention, the step 3.2 is specifically as follows:

Step 3.2.1. In the PCA space, calculate the squared Euclidean distance values between all reference feature points in a single subset and the query feature point q′ _i, and sort the squared Euclidean distance values corresponding to the αk nearest neighbors from small to large to form a filter pile; in the original space, calculate the Euclidean distance values between all reference feature points in the subset and the query feature point q _i, and sort the Euclidean distance values corresponding to the k nearest neighbors from small to large to form a verification pile;

Step 3.2.2, filter a single reference feature point: in the PCA space, calculate the square Euclidean distance value between a reference feature point and the query feature point q′ _i ; if the square Euclidean distance value is greater than or equal to the maximum distance in the filter stack, discard the reference feature point; otherwise, calculate the Euclidean distance value between the reference feature point and the query feature point q _i in the original space, if the Euclidean distance value is greater than or equal to the maximum distance in the verification stack, discard the reference feature point; otherwise, insert the square Euclidean distance value calculated in the PCA space in step 3.2.2 into the filter stack to replace the maximum distance in the filter stack and re-sort to obtain a new filter stack, replace the original filter stack with the new filter stack, insert the Euclidean distance value calculated in the original space in step 3.2.2 into the verification stack to replace the maximum distance in the verification stack and re-sort to obtain a new verification stack, and replace the original verification stack with the new verification stack;

Step 3.2.3, return to step 3.2.2, filter each reference feature point in the subset respectively, obtain the latest filter stack, sort according to the distance values in the latest filter stack, select the squared Euclidean distance values corresponding to the k nearest neighbors, which is the k nearest neighbor result of the subset;

Step 3.3.4: Return to step 3.2.1, and filter the reference feature points in the w subsets according to the methods of steps 3.2.1 to 3.2.3, respectively, to generate the k nearest neighbor results for each subset.

As a further improved technical solution of the present invention, the step 3.3 is specifically as follows: the initial maximum heap is an empty set, the k nearest neighbor results of each subset are added to the maximum heap in turn, the distance values in the maximum heap are compared and the maximum heap is continuously adjusted, so that the final maximum heap retains the k nearest neighbor results, that is, the squared Euclidean distance values corresponding to the k nearest neighbors.

As a further improved technical solution of the present invention, the preset pixel value in step 3.4 is 1.5 pixels.

As a further improved technical solution of the present invention, it also includes:

Step 5: Determine whether there is a reference feature point in the reference feature point set R that roughly matches the query feature point q _i in the query feature point set Q:

Step 5.1, in the PCA space, divide the reference feature point set R′ into w subsets; the projection point of the query feature point q _i onto the low-dimensional PCA space is recorded as the query feature point q′ _i ;

Step 5.2, calculate the squared Euclidean distance between all reference feature points in a single subset and the query feature point q _i ^′ , and determine whether there is a reference feature point in the subset that roughly matches the query feature point q _i ^′ based on the ratio of the nearest neighbor distance to the next nearest neighbor distance;

Step 5.3: According to the method in step 5.2, determine whether there is a reference feature point roughly matching the query feature point q _i ^′ in each subset; if none of them exists, determine that there is no reference feature point roughly matching the query feature point q _i in the reference feature point set R; otherwise, obtain all reference feature points roughly matching the query feature point q _i ^′ , select a reference feature point that is the nearest neighbor of the query feature point q _i ^′ from all the obtained reference feature points, and use the point corresponding to the reference feature point in the original space as the rough matching point of the query feature point q _i ;

Step 6: According to the method of step 5, it is determined whether each query feature point in the query feature point set Q has a coarse matching reference feature point, and then all coarse matching point pairs are obtained;

Step 7: Calculate the matching accuracy, which is the percentage of correct matching point pairs to the total matching point pairs, where the total matching point pairs are the coarse matching point pairs.

As a further improved technical solution of the present invention, in the step 5.2, it is determined whether there is a reference feature point roughly matching the query feature point q _i ^′ in the subset according to the ratio of the nearest neighbor distance to the next nearest neighbor distance, specifically:

The formula for the ratio of the nearest neighbor distance to the next nearest neighbor distance (1) is:

Where _dqA represents the square Euclidean distance between the query feature point q _i ^′ and its nearest reference feature point, and _dqB represents the square Euclidean distance between the query feature point q _i ^′ and its second nearest reference feature point. is the distance ratio threshold. If formula (1) is satisfied, the reference feature point closest to the query feature point q _i ^′ is recorded as the reference feature point roughly matched with the query feature point q _i ^′ ; otherwise, there is no reference feature point roughly matched with the query feature point q _i ^′ in the subset.

As a further improved technical solution of the present invention, the step 2 is specifically as follows:

Step 2.1, the feature descriptors of all reference feature points and query feature points in the original space are combined into a matrix S, and the eigenvalues and eigenvectors of the matrix S are obtained by using the singular value decomposition method, and the number of principal components c corresponding to the cumulative contribution rate is obtained according to the eigenvalues and the preset value of the cumulative contribution rate;

Step 2.2, select the eigenvectors corresponding to the first c largest eigenvalues according to the number of principal components c, and form a projection matrix P with the selected eigenvectors;

Step 2.3: According to the projection matrix P, the image in the original space The reference feature point set R and image in The query feature point sets Q in are projected into the low-dimensional PCA space respectively.

As a further improved technical solution of the present invention, in step 2.1, the preset value of the cumulative contribution rate is a preset range value of the cumulative contribution rate, and the range value of the number of principal components c corresponding to the preset range value of the cumulative contribution rate is obtained;

According to the method of steps 3-4 and according to different values of the number of principal components c, the number of correct matching point pairs between the two images to be matched is calculated;

Set the evaluation index, evaluate the matching performance corresponding to different values of the number of principal components c according to the evaluation index, select the value of the number of principal components c corresponding to the optimal matching performance as the final value of the number of principal components c used in step 2 to calculate the projection matrix P, and finally obtain all the correct matching point pairs between the two images.

The beneficial effects of the present invention are:

The present invention proposes a high-performance dimensionality reduction parallel matching algorithm that integrates principal component analysis and double-stack filtering. The feature point set is projected into a low-dimensional space through principal component analysis, and the ranking is estimated using squared Euclidean distance, which effectively reduces the computational complexity in the matching process. At the same time, in order to ensure the accuracy of feature matching, the algorithm of the present invention uses a double-stack filtering algorithm to purify the matching point pairs. In addition, the algorithm of the present invention also adopts a parallel structure, fully utilizes computing resources, and improves the matching speed of the overall algorithm. From the experimental results, the algorithm of the present invention has obvious advantages over traditional image feature matching algorithms in terms of total matching time, matching accuracy, and matching error root mean square. In summary, the algorithm of the present invention has good matching real-time performance while taking into account the matching accuracy, and can be applied to the efficient matching of high-dimensional feature points between local road images.

BRIEF DESCRIPTION OF THE DRAWINGS

Figure 1 is a schematic diagram of three-dimensional feature points and their projection in PCA space.

FIG2 is a schematic diagram of the mismatch phenomenon.

FIG3 is a schematic diagram of a dual-pile filtering algorithm.

Figure 4 is a diagram of the multi-core parallel matching strategy.

FIG5 is a schematic diagram showing the effect of parameters c and α on algorithm performance.

FIG6 is a schematic diagram showing the effect of the number of divided subsets on the algorithm performance.

FIG7 is a schematic diagram showing the comparison results of matching time of different algorithms.

FIG8 is a schematic diagram showing the comparison results of the matching accuracy of different algorithms.

FIG9 (a) is a schematic diagram of a query image.

FIG9( b ) is a schematic diagram of a reference image.

FIG9( c ) is a schematic diagram of the matching effect of the SIFT algorithm.

Figure 9 (d) is a schematic diagram of the matching effect of the SURF algorithm.

FIG9(e) is a schematic diagram of the matching effect of the SUPD algorithm.

FIG10 is a schematic diagram showing the comparison results of the root mean square matching errors of different algorithms.

DETAILED DESCRIPTION

The specific embodiments of the present invention are further described below according to the accompanying drawings:

Based on the SURF algorithm, this paper provides a dimensionality reduction parallel image feature matching algorithm that integrates principal component analysis and double heap filtering, namely the SUPD (SURF combining PCA and DHF) algorithm. In order to solve the computational complexity caused by the high-dimensional descriptors of the traditional SURF algorithm, the SUPD algorithm uses principal component analysis (PCA) to project the feature point set into a low-dimensional space, and uses the square Euclidean distance (SED) with lower computational cost for ranking estimation to match feature points. At the same time, in order to eliminate mismatching, the SUPD algorithm also uses the double heap filter (DHF) algorithm to purify the feature points to ensure the accuracy of feature matching. Since the SUPD algorithm adopts a parallel structure, it can be easily extended to multi-core systems to improve the matching speed of image feature points and meet the real-time requirements of panoramic surround view technology for local road image fusion.

1. System model:

Consider the local road image captured by the neighboring vehicle camera points _Li and _Lj at time t and The matching process. Definition is time t The feature points labeled k _i are in the image The feature point set in can be expressed as set up To query the feature point set, is the reference feature point set. In the matching process, the total number of matching point pairs is obtained by the ratio of the nearest neighbor to the next nearest neighbor distance, which is expressed as In order to realize the local road image and To correctly stitch together The feature point coordinates on are mapped to The corresponding feature point coordinates on the image are obtained to establish the geometric correspondence between the two images. Let the matrix H be and Nh is the transformation matrix between them, and _Nh is the number of matching point pairs that satisfy the transformation matrix H.

Definition 1 (feature point matching time): Define σ _i (k _i ) as the query feature point The time to complete the matching, that is, The time consumed to find the closest reference feature point is then the total time t to complete the matching of all query feature points is shown in formula (1).

in, is the total number of query feature points.

Definition 2 (matching accuracy): Define the matching accuracy ξ as the number of matching point pairs N _h that satisfy the transformation matrix H to the total number of matching point pairs The percentage is shown in formula (2).

Definition 3 (matching efficiency): Matching efficiency E is defined as the matching accuracy ξ divided by the feature point matching time t. Based on the above definition, the matching process of the local road image can be described as a mathematical optimization problem as shown in formula (3).

Among them, formula (3) is the objective function for completing feature point matching in the process of local road image matching. The higher the value of E, the better the matching efficiency of the algorithm. Constraint (4) requires that the number of correctly matched feature point pairs Satisfy the conditions for generating the transformation matrix.

2. SUPD algorithm:

In order to meet the requirements of the panoramic surround view system in terms of matching accuracy and real-time performance, this paper proposes a new surround view image feature matching algorithm, called the SUPD algorithm. This algorithm combines the advantages of the PCA algorithm and the DHF algorithm, and aims to reduce the dimension of the high-dimensional feature points and filter and purify them. At the same time, the parallel matching strategy makes full use of computing resources to further accelerate the matching efficiency of the algorithm.

2.1. Distance ranking based on PCA dimensionality reduction:

Principal component analysis is a commonly used dimensionality reduction method. Its basic idea is to project high-dimensional data into low-dimensional space, extract main features and reduce redundant information, so as to provide more concise and efficient data representation in the subsequent data analysis and modeling process. It is applied to the field of feature point matching, that is, using the projection matrix P, the feature point set in the high-dimensional original space is projected into the low-dimensional space (PCA space) for distance estimation, and then the similarity between the query feature point and the reference feature point is predicted.

In this paper, singular value decomposition is used to obtain the projection matrix P. For the matrix S composed of the feature descriptors of all reference feature points and query feature points in the original space, its singular value decomposition formula is shown in formula (5).

S = UZV ^T (5);

Among them, U and V are the eigenvectors of ^SST and ^STS respectively, Z=diag( _γ1 , _γ2 ,…, _γn ) is a diagonal matrix, and the elements on the diagonal of the diagonal matrix Z are the square roots of the eigenvalues of the matrix S.

The eigenvalue and corresponding eigenvector of S can be obtained from formula (5), and the cumulative contribution rate and the number of principal components c corresponding to the cumulative contribution rate can be calculated based on the eigenvalue of S. The calculation formula is shown in formula (6).

Among them, m is the total number of principal components, μ is the cumulative contribution rate, and the value of μ is generally 85% to 95%. _{λ e} represents the eigenvalue of S; e is the number of principal components, that is, the eigenvalue index, which ranges from 1 to m.

Since each principal component corresponds to an eigenvalue and an eigenvector in principal component analysis, according to the value of the principal component number c when the cumulative contribution rate is reached, the eigenvectors corresponding to the first c largest eigenvalues are selected according to the number of principal components c, and the projection matrix P is composed of the selected eigenvectors; each column of the projection matrix P is an eigenvector of a principal component.

After obtaining the projection matrix P, the reference feature point set R = {r ₁ , r ₂ , ..., r _n } and the query feature point q _i can be projected into the low-dimensional PCA space, as shown in formula (7).

After the projection is completed, the distance between each reference feature point _ri ′ and the query feature point q′ _i can be calculated in the PCA space. In order to reduce the computational overhead, this paper uses the squared Euclidean distance SED( _ri ′,q′ _i ) to estimate the distance between feature points _ri ′ and q′, as shown in formula (8).

Where d is the dimension of the PCA space.

According to the ranking of SED, the reference feature point _ri ′ closest to the query feature point q′ _i can be obtained to generate a matching point pair. Since the principal component retains the key information between points in the original space, the distance ranking between any two points _qi , _rj in the high-dimensional space is similar to the distance ranking between the corresponding projection points _qi ′, _rj ′ in the low-dimensional space.

As shown in Figure 1, take a three-dimensional vector as an example, where q is the query feature point, A, B, C, and D are reference feature points. All feature points are projected into the PCA space for dimensionality reduction, and the projection points are q′, A′, B′, C′, and D′. The distance ranking is shown in Table 1. In the PCA space, the order of the reference feature points based on the SED ranking is A′-B′-C′-D′, which is the same as the Euclidean distance (ED) ranking A-B-C-D in the original three-dimensional space. Finally, the coarse matching point pair is determined by the distance ratio between the nearest neighbor and the next nearest neighbor. Its calculation formula is shown in formula (9).

Where _dqA represents the distance between the query feature point q and its nearest point A, and _dqB represents the distance between the query feature point q and its second nearest point B. is the distance ratio threshold, generally taken as

Table 1. Correct ranking estimation of 3D feature points:

3D Space Euclidean distance Distance Ranking PCA space Squared Euclidean distance Distance Ranking q - - q′ - - A 2.7 1 A′ 3.1 1 B 4.1 2 B′ 16.9 2 C 6.3 3 C′ 35.5 3 D 7.8 4 D′ 61.2 4

2.2. Double-heap filtering algorithm:

Although the similarity between the query feature point and the reference feature point can be predicted by using the squared Euclidean distance ranking method in the low-dimensional PCA space, incorrect matching may occur occasionally. As shown in Figure 2 and Table 2, the distance ranking in the PCA space is A′-B′-C′-D′, but the distance ranking in the original three-dimensional space is B-A-C-D. If matching is performed only based on the distance ranking in the PCA space, incorrect matching point pairs may be generated.

Table 2. Error ranking estimation of 3D feature points:

To solve the above problems, this paper proposes a dual-heap filtering algorithm (DHF) based on PCA ranking prediction, that is, two screening heaps are maintained, the one in the PCA space is called the filtering heap, and the one in the original space is called the verification heap. The two heaps retain their own αk and k nearest neighbor distance results respectively, and filter the projected feature points. The structure of the filtering heap and the verification heap is shown in Figure 3. In the PCA space, in a single set, the square Euclidean distance values between all reference feature points and the query feature point q′ _i are calculated, and the square Euclidean distance values corresponding to the αk nearest neighbors are sorted from small to large to form a filtering heap, that is, the filtering heap contains the first αk square Euclidean distance values d ₁ , d ₂ , d ₃ ... d _αk ; In the original space, in a single set, the Euclidean distance values between all reference feature points and the query feature point q _i are calculated, and the Euclidean distance values corresponding to the k nearest neighbors are sorted from small to large to form a verification heap, that is, the verification heap contains the first k Euclidean distance values d ₁ , d ₂ , d ₃ , etc. . . . . d _k .

When DHF filters feature points, first, it calculates the square Euclidean distance SED between the reference feature point and the query point projection in the PCA space. If the distance is greater than or equal to the maximum distance in the filter heap, the reference feature point is discarded. If the distance is less than the maximum value in the filter heap, the Euclidean distance ED between the reference feature point and the query feature point in the original space is further calculated. If the distance is greater than or equal to the maximum distance in the verification heap, the reference feature point is discarded. If it is less than the maximum value, it is considered that the judgment is correct, and the Euclidean distance value and the projected square Euclidean distance value are respectively inserted into the verification heap and the filter heap to replace their respective initial maximum values and reorder them.

The relationship between the adjustment factor α in DHF and the number of nearest neighbors is k′=αk. α is used to adjust the size of the filter stack, which can effectively reduce the phenomenon of poor algorithm filtering performance caused by using only part of the principal component information. The values of α and k will be determined through experimental analysis in the future.

The matching point pairs filtered by the DHF algorithm can effectively avoid the false matching phenomenon in Figure 2. The DHF algorithm adopts a heap structure based on KNN, which can reduce the number of distance calculations and comparisons, improve query efficiency, and further improve the real-time performance of the overall algorithm.

2.3. Multi-core parallel matching strategy:

Traditional matching algorithms usually need to match according to the index order of reference feature points, and can only match one reference point as a unit. For example, the matching algorithm based on the kd tree needs to continuously search for reference feature points according to the tree index, but due to the large number of reference feature points, this matching method will result in a huge amount of calculation in the matching process of a single query point, making it difficult to balance the system load.

Since the matching task of each reference feature point in this paper's matching algorithm is relatively independent, it is particularly suitable for parallel processing when processing a large number of reference feature points. To this end, this paper designs a multi-core parallel matching strategy, as shown in Figure 4.

When matching feature points, the projected reference feature point set R′ in the PCA space is first divided into w subsets. Then, when matching each projected query feature point q′ _i in sequence, these subsets are assigned to different threads in the system and calculated in parallel, and each subset generates its own k nearest neighbor result through the double heap filtering algorithm. Finally, a maximum heap of size k is maintained, and the k nearest neighbor result obtained from each subset is used as the initial element of the maximum heap. The maximum heap is continuously adjusted by comparing the distance metric value to generate the final k nearest neighbor result. The nearest reference feature point in the k nearest neighbor result is selected for comparison with the query feature point. If the pixel distance is less than or equal to 1.5 pixels, it is determined to be a correct match. This parallel matching strategy can make full use of computing resources and improve the matching efficiency of feature points.

In summary, the dimensionality reduction parallel image feature matching algorithm integrating principal component analysis and double stack filtering provided in this paper includes the following steps:

Step 1: The two images to be matched are recorded as and image The feature points in the image are recorded as query feature points. The feature points in are recorded as reference feature points.

Step 2: Use principal component analysis to transform the image in the original space The reference feature point set R and image in The query feature point set Q in is projected into the low-dimensional PCA space to obtain the projected reference feature point set R′ and the query feature point set Q′.

Step 3: Determine whether there is a reference feature point in the reference feature point set R that correctly matches the query feature point q _i in the query feature point set Q:

Step 3.1, in the PCA space, divide the reference feature point set R′ into w subsets; the projection point of the query feature point q _i onto the low-dimensional PCA space is recorded as the query feature point q′ _i ;

Step 3.2: Use the double-heap filtering algorithm to filter the reference feature points in the w subsets respectively, and generate the k nearest neighbor results for each subset:

Step 3.2.1. In the PCA space, calculate the squared Euclidean distance values between all reference feature points in a single subset and the query feature point q′ _i, and sort the squared Euclidean distance values corresponding to the αk nearest neighbors from small to large to form a filter pile; in the original space, calculate the Euclidean distance values between all reference feature points in the subset and the query feature point q _i, and sort the Euclidean distance values corresponding to the k nearest neighbors from small to large to form a verification pile;

Step 3.2.2, filter a single reference feature point: in the PCA space, calculate the square Euclidean distance value between a reference feature point and the query feature point q′ _i ; if the square Euclidean distance value is greater than or equal to the maximum distance in the filter stack, discard the reference feature point; otherwise, calculate the Euclidean distance value between the reference feature point and the query feature point q _i in the original space, if the Euclidean distance value is greater than or equal to the maximum distance in the verification stack, discard the reference feature point; otherwise, insert the square Euclidean distance value calculated in the PCA space in step 3.2.2 into the filter stack to replace the maximum distance in the filter stack and re-sort to obtain a new filter stack, replace the original filter stack with the new filter stack, insert the Euclidean distance value calculated in the original space in step 3.2.2 into the verification stack to replace the maximum distance in the verification stack and re-sort to obtain a new verification stack, and replace the original verification stack with the new verification stack;

Step 3.2.3, return to step 3.2.2, filter each reference feature point in the subset respectively, obtain the latest filter stack, sort according to the distance values in the latest filter stack, select the squared Euclidean distance values corresponding to the k nearest neighbors, which is the k nearest neighbor result of the subset;

Step 3.3.4, return to step 3.2.1, filter the reference feature points in the w subsets according to the methods of steps 3.2.1-3.2.3, and generate the k nearest neighbor results for each subset;

Step 3.3, add the k nearest neighbor results of each subset to the maximum heap in turn, compare the distance values in the maximum heap and continuously adjust the maximum heap so that the final maximum heap retains the k nearest neighbor results, that is, the squared Euclidean distance values corresponding to the k nearest neighbors. Initially, the maximum heap is empty. Then, the distance values in the k nearest neighbor results generated by each subset are added to the maximum heap in turn. When adding new elements, the maximum heap will automatically adjust to ensure that the element with the largest distance is always at the top of the heap. If the new distance metric is less than the maximum value at the top of the heap, the maximum value at the top of the heap will be deleted, and then the new distance value will be inserted and the heap will be readjusted. This process is repeated until the k nearest neighbor results of all subsets are processed, ensuring that the k distance values in the maximum heap always represent the closest k distances.

Step 3.4, select the reference feature point closest to the query feature point _qi ^′ from the k nearest neighbor results in the maximum heap, and calculate the pixel distance between it and the query feature point _qi ^′ . If the pixel distance is less than or equal to 1.5 pixels, then the point corresponding to the reference feature point in the original space is determined to be the reference feature point that correctly matches the query feature point _qi . Otherwise, then it is determined that there is no reference feature point in the reference feature point set R that correctly matches the query feature point _qi .

Step 4: According to the method in step 3, determine whether each query feature point in the query feature point set Q has a correctly matched reference feature point, and then obtain all correct matching point pairs, and finally realize image With image feature matching.

Step 5: Determine whether there is a reference feature point in the reference feature point set R that roughly matches the query feature point q _i in the query feature point set Q:

Step 5.1, in the PCA space, divide the reference feature point set R ^′ into w subsets; the projection point of the query feature point q _i onto the low-dimensional PCA space is recorded as the query feature point q _i ^′ ;

Step 5.2: Calculate the squared Euclidean distance between all reference feature points in a single subset and the query feature point q _i ^′ , and determine whether there is a reference feature point in the subset that roughly matches the query feature point q _i ^′ based on the ratio of the nearest neighbor distance to the next nearest neighbor distance:

The ratio of the nearest neighbor distance to the next nearest neighbor distance is:

Where _dqA represents the squared Euclidean distance between the query feature point _q′i and its nearest reference feature point, and _dqB represents the squared Euclidean distance between the query feature point _q′i and its second nearest reference feature point. is the distance ratio threshold, if it satisfies the formula The reference feature point closest to the query feature point q′ _i is recorded as the reference feature point roughly matched with the query feature point q′ _i ; otherwise, there is no reference feature point roughly matched with the query feature point q′ _i in the subset;

Step 5.3. Determine in each subset whether there is a reference feature point that roughly matches the query feature point q′ _i according to the method in step 5.2; if none exists, determine that there is no reference feature point that roughly matches the query feature point q _i in the reference feature point set R; otherwise, obtain all reference feature points that roughly match the query feature point q′ _i , and select a reference feature point that is the nearest neighbor of the query feature point q′ _i from all the obtained reference feature points, and the point corresponding to the reference feature point in the original space is used as the coarse matching point of the query feature point q _i .

Step 6: According to the method of step 5, determine whether there is a coarse matching reference feature point for each query feature point in the query feature point set Q, and then obtain all coarse matching point pairs.

Step 7: Calculate the matching accuracy, which is the percentage of correct matching point pairs to the total matching point pairs, where the total matching point pairs are the coarse matching point pairs.

3. Performance analysis:

3.1、Time and space complexity analysis:

This section will use brute force search (BF) as a comparison algorithm to analyze the time and space complexity of the algorithm in this paper. For the matching of a single query feature point, the BF algorithm calculates and matches the distance of all reference feature points in the original space through exhaustive method. Due to the high dimensionality of the original space, the BF algorithm needs to traverse all reference feature points, resulting in a high space complexity of O(ND), where N is the number of reference feature points and D is the dimension of the original high-dimensional space.

However, in the actual matching process, if most of the unnecessary distance calculations are avoided, the algorithm performance will be greatly improved. The SUPD algorithm has this feature. The algorithm projects the feature points into the low-dimensional PCA space and uses the DHP algorithm based on KNN for filtering. Among them, the space complexity of the KNN algorithm mainly comes from the construction of the kd tree, and the search process of the kd tree does not require additional storage space. Therefore, the space complexity after dimensionality reduction and filtering is O(Nd), where d is the dimension of the PCA space. From the subsequent experimental results, it can be concluded that d is much smaller than D. At the same time, in order to make full use of computing resources, this paper divides the reference feature point set into w subsets and assigns them to each thread for parallel matching, which further reduces the space complexity to only O(Nd/w).

Assuming that the total time required by the BF algorithm to complete all distance calculations for a query feature point in the original space is _TD , the proposed algorithm successfully shortens this time through dimensionality reduction and multi-core parallel matching, and the shortened total time is d· _TD /Dw. This shows that the operating efficiency of the proposed algorithm is much better than that of the BF algorithm, and after subsequent experimental verification, the proposed algorithm meets the real-time requirements of vehicle-mounted camera equipment.

3.2 Parameter analysis:

The main parameters of the SUPD algorithm include the number of principal components c that reach the cumulative contribution rate, the number of nearest neighbors k and the adjustment factor α of the double stack filtering, and the number of subsets w into which the projected reference feature point set is divided. In this section, the specific value range of each parameter will be analyzed to prepare for the subsequent parameter setting experiments.

First, when using principal component analysis (PCA) for dimensionality reduction, it is necessary to determine the number of principal components to be retained, that is, the dimension after dimensionality reduction. Too many principal components (large c value) will cause the data after dimensionality reduction to remain at a higher dimension, increase the computational and storage overhead, and may also introduce noise. Too few principal components will cause the data after dimensionality reduction to be unable to fully express the characteristics of the original data, resulting in information loss. Therefore, it is crucial to select the appropriate number of principal components c. The number of principal components c retained can be determined by calculating the cumulative contribution rate μ. According to existing literature, the general value range is 85% to 95%. This paper recommends selecting the number of principal components c _l corresponding to μ of 65% as the lower limit, and the number of principal components c _u corresponding to μ of 95% as the upper limit, setting the range of c value to [c _l , c _u ], and determining the most appropriate c value through experiments to achieve the best dimensionality reduction effect.

Next, the double heap filtering algorithm (DHP) is used to refine the extracted matching point pairs. The size of the filter heap is α×k, where k is the number of nearest neighbors in the validation heap. The validation heap is used to verify the matching point pairs initially purified in the filter heap, so the k value should not be too large. In most knn-based feature matching algorithms, k is usually set to 2, so this paper also sets k to 2. The adjustment factor α of the filter heap affects the number of matching point pairs obtained by the initial filtering. If α is set too large, since the calculation of the validation heap uses the Euclidean distance in the original high-dimensional space, this will increase the computational complexity and seriously affect the real-time performance of the algorithm. If α is set too small, incorrect filtering may occur, that is, the distance between a reference feature point in the projection space (PCA space) and the query point is greater than the maximum value of the filter heap, but the distance between the point and the query point in the original space is less than the maximum value of the validation heap, resulting in the point being incorrectly filtered out during actual matching. And when α=1, the size of the filter heap is the same as that of the validation heap, and the role of the filter heap cannot be reflected. Therefore, this paper sets the α selection range to [2,5], and determines the most appropriate α value through experiments to achieve the best filtering effect.

Finally, the projected reference feature point set is divided into w subsets for parallel matching. The number of subset divisions w affects whether the computing resources can be used to the maximum extent, thereby improving the performance of the algorithm. The number of subset divisions determines the granularity of parallel tasks. Smaller task granularity leads to better data locality, reduces memory access conflicts, and is also easier to achieve balanced load. However, it is not advisable to divide it too small. Too small task granularity will also lead to frequent communication and synchronization operations, increasing computing overhead. At the same time, when dividing the number of subsets w, the number of cores of the experimental platform should also be considered. The number of cores reflects the upper limit of tasks that can be executed in parallel. Therefore, in order to maximize the use of computing resources and achieve optimal parallel performance, this paper sets the range of the number of subset divisions w to in is the maximum number of cores of the experimental platform, and the most appropriate w value is determined through experiments to achieve the goal of optimizing algorithm performance.

4. Results and analysis:

4.1 Experimental preparation:

4.1.1 Experimental platform:

The hardware platform of this experiment is AMD Opteron Processor 6376CPU@2.30GHz, 16MB L3 cache, 16 cores, 32 logical processors, and 128GB memory; the software platform is Windows 10 64-bit operating system, Visual Studio Code, and Opencv4.

4.1.2 Experimental data:

To meet the research needs, this paper uses a self-constructed dataset, which consists of 100 sets of local road images with a certain degree of overlap. These images cover a variety of road scenarios and show obvious diversity in terms of viewing angle, lighting conditions, and weather conditions.

4.1.3 Experimental evaluation indicators:

1) Total matching time (tota_time): The sum of the time consumed by feature extraction and feature matching, where the feature matching time includes the time consumed by eliminating false matches and performing local optimization. Its definition is shown in formula (10).

tota_time = _Te + _Tm (10);

Among them, _Te is the feature extraction time and _Tm is the feature matching time.

2) Matching accuracy (matching_accuracy): As an evaluation index of algorithm accuracy, matching accuracy is the percentage of correct matching point pairs to the total matching point pairs. Its definition is shown in formula (11).

Among them, _Nc is the number of correct matching point pairs, and _Ns is the total number of matching point pairs.

3) Matching error root mean square (MERD): As the matching evaluation index of the overall matching point pairs between the query image and the reference image, the smaller the MERD, the better the overall matching quality, and vice versa. Its definition is shown in formula (10).

Among them, ( _xi , _yi ) is the query feature point coordinate, ( _xi ′, _yi ′) is the reference feature point coordinate, and _fh (x) is the projection transformation model.

4.2. Determination of parameters:

This section will use experiments to define the exact values of each parameter when the algorithm reaches the optimal performance state based on the parameter range analyzed in Section 3.2. Before conducting the experiment, we first clarify the evaluation indicators for parameter selection, which are defined as follows.

a) Improvement ratio: the matching time of brute force matching divided by the matching time of the proposed algorithm.

b) Speedup ratio: the algorithm’s serial matching time divided by its parallel matching time.

c) Comprehensive performance index: the improvement ratio multiplied by the matching accuracy, taking into account the algorithm's running time and matching accuracy.

According to the analysis and calculation in Section 3.2, when the cumulative contribution rate is 65% and 95%, the number of principal components corresponding to the self-constructed data set is 5 and 20 respectively. Therefore, this paper selects the number of principal components c in the interval [5,20] for analysis to evaluate its impact on the performance of the algorithm. In addition, given that the number of principal components c and the adjustment factor α of the filter stack may affect each other in different value ranges, while the number of subset divisions w is relatively independent. Therefore, under the premise of setting w = 10, the impact of the number of principal components c and the adjustment factor α on the performance of the algorithm is analyzed through comprehensive experiments.

The experimental results are shown in Figure 5. Under different filter stack adjustment factors α, the transformation trend between the comprehensive performance index and the number of principal components is similar, and within the set range, the smaller the value of α, the larger the overall comprehensive performance index. At the same time, as the number of principal components c increases, the retained feature information also increases accordingly, and the matching accuracy also increases significantly, which increases the comprehensive performance index. However, when the c value exceeds a certain threshold, the improvement in matching accuracy gradually stabilizes, while the matching time increases accordingly, resulting in a decrease in the comprehensive performance index. Therefore, based on the experimental results, the best (c, α) suitable for the data set in this paper is (14, 2).

Since the number of subset partitions w has high independence and is not affected by the number of principal components and the filter stack adjustment factor, this paper will conduct experiments on it separately to analyze its impact on the algorithm performance.

The experimental results are shown in Figure 6. As w increases, the speedup ratio increases. When w reaches the maximum number of cores of the experimental platform, the speedup ratio reaches its extreme value, which indicates that the computing resources are optimally utilized at this time, thereby minimizing the matching time. However, it is worth noting that once w exceeds the maximum number of cores, it may cause parallel computing problems such as increased scheduling overhead and load imbalance, resulting in a gradual decrease in the speedup ratio and a gradual increase in the matching time. Therefore, based on the experimental results, the most appropriate number of subset partitions w is 16.

4.3 Experimental results:

To verify the performance of the SUPD algorithm, this paper divides the data set into 5 groups according to the complexity of color, texture, etc. The complexity of the experimental groups increases from 1 to 5. The average value of each group of experimental data is taken, and the performance tests of total matching time, matching accuracy, and root mean square of matching error are performed. At the same time, comparative experiments are also conducted with traditional SIFT and SURF algorithms to obtain more comprehensive performance comparison results. Both SIFT and SURF algorithms are used with the brute force matching algorithm built into OpenCV for feature matching.

4.3.1、Total matching time analysis:

As an important indicator, the total matching time can effectively measure the real-time performance of the algorithm. Figure 7 shows the comparison results of the total matching time of the SUPD algorithm and the other two traditional algorithms. It can be seen that the SUPD algorithm is significantly better than the traditional SIFT and SURF algorithms in terms of total matching time, shortening the time by 77% to 80%. This improvement in real-time performance stems from the specific design of the SUPD algorithm. The algorithm uses the principal component analysis method to reduce the dimension of feature descriptors, thereby effectively reducing the computational complexity. In addition, the SUPD algorithm introduces a multi-core parallel matching strategy, which enables multiple processing cores to perform matching operations simultaneously. This not only speeds up the calculation process, but also improves the system throughput, thereby significantly improving the running speed of the overall algorithm.

Therefore, compared with traditional SIFT and SURF algorithms, the SUPD algorithm achieves significant performance advantages in total matching time through the introduction of principal component analysis dimensionality reduction and multi-core parallel matching strategy, and demonstrates better real-time performance.

4.3.2 Matching accuracy analysis:

The matching accuracy can effectively reflect the precision and robustness of the feature matching algorithm. Its calculation method is shown in formula (11). Figure 8 shows the matching accuracy comparison results of the SUPD algorithm and the other two traditional algorithms. By comparison, it can be found that compared with the traditional SIFT and SURF algorithms, the SUPD algorithm has improved the accuracy by 5% to 15%. In order to more intuitively display the matching accuracy comparison results, this paper takes the matching effect of the first experiment in the third group as an example to analyze the advantages and disadvantages of the SUPD algorithm and the traditional SIFT and SURF algorithms in terms of matching accuracy, as shown in Figure 9.

As can be seen from (c) and (d) in Figure 9, the traditional SIFT and SURF algorithms have many mismatching phenomena such as cross-matching and repeated matching, which leads to a low matching accuracy rate. The matching effect of the SUPD algorithm is shown in (e) in Figure 9. The algorithm filters and purifies the matching point pairs through the two screening stacks maintained in the DHF algorithm, effectively improving the mismatching phenomenon and ensuring a high matching accuracy rate. Therefore, compared with the traditional SIFT and SURF algorithms, the SUPD algorithm has obvious advantages in matching accuracy.

4.3.3、RMS analysis of matching error:

In order to more intuitively reflect the matching quality between the overall feature point pairs, this paper introduces the matching error root mean square (MERD) as an evaluation index. The smaller the value of MERD, the higher the matching quality of the overall feature point pairs, and vice versa. The calculation formula of MERD is shown in formula (12). Figure 10 shows the comparison results of the SUPD algorithm and the other two traditional algorithms on MERD. It can be seen that the MERD values of the SUPD algorithm are lower than those of the SIFT and SURF algorithms, and are reduced by 12% to 32% respectively. This shows that the SUPD algorithm shows better performance in matching the overall feature point pairs, so that it can more accurately match the massive high-dimensional features between local road images, especially when facing local road images with changes in illumination and perspective, the performance of the SUPD algorithm is more robust.

The algorithm in this paper uses principal component analysis to map the feature point set to a low-dimensional space, and uses the squared Euclidean distance with lower computational cost to match the feature points, which significantly reduces the computational complexity. At the same time, to ensure the accuracy of feature matching, the algorithm uses a double-heap filtering algorithm to filter and purify the matching point pairs. In addition, in order to further improve the matching speed and maximize the use of computing resources, the algorithm also introduces a multi-core parallel matching strategy, which greatly improves the efficiency of feature point matching. Compared with traditional SIFT and SURF algorithms, the algorithm in this paper shortens the matching time by 77% to 80%, and at the same time increases the matching accuracy by 5% to 15%. Experimental results show that the algorithm in this paper has excellent matching real-time performance and accuracy, and can meet the requirements of vehicle-mounted panoramic surround view systems for feature matching.

5. Conclusion:

In view of the fact that traditional image feature matching algorithms cannot meet the requirements of efficient matching of high-dimensional feature points between local road images, this paper proposes a high-performance dimensionality reduction parallel matching algorithm that integrates principal component analysis and double-stack filtering. The feature point set is projected into a low-dimensional space through principal component analysis, and the ranking is estimated using squared Euclidean distance, which effectively reduces the computational complexity of the matching process. At the same time, in order to ensure the accuracy of feature matching, the algorithm in this paper uses a double-stack filtering algorithm to purify the matching point pairs. In addition, the algorithm in this paper also adopts a parallel structure, fully utilizes computing resources, and improves the matching speed of the overall algorithm. From the experimental results, the algorithm in this paper has obvious advantages over traditional image feature matching algorithms in terms of total matching time, matching accuracy, and matching error root mean square. In summary, the algorithm in this paper has good matching real-time performance while taking into account the matching accuracy, and can be applied to the efficient matching of high-dimensional feature points between local road images.

The protection scope of the present invention includes but is not limited to the above embodiments. The protection scope of the present invention shall be based on the claims. Any replacement, deformation, and improvement of the technology that can be easily thought of by technicians in this field shall fall within the protection scope of the present invention.

Claims (7)

1. A dimension-reducing parallel image feature matching algorithm integrating principal component analysis and double-pile filtering is characterized by comprising the following steps:

step 1, respectively marking two images to be matched as AndImage ofThe feature points in the image are marked as query feature points, and the imageThe feature points in (a) are marked as reference feature points;

Step 2, adopting a principal component analysis method to carry out image analysis on the original space Reference feature point set in (a)And an imageIn a query feature point setProjecting to a low-dimensional PCA space to respectively obtain a projected reference feature point setAnd query feature point set；

Step 3, judging the reference feature point setIn (1) whether there is a feature point set with the queryQuerying feature pointsCorrectly matched reference feature points:

step 3.1, in the PCA space, the reference feature points are collected Divided intoA subset of the plurality; querying feature pointsProjection points projected into a low-dimensional PCA space are marked as query feature points；

Step 3.2, adopting a double-pile filtering algorithm to respectively pairFiltering the reference feature points in each subset to generate each subsetNearest neighbor results; the method comprises the following steps:

Step 3.2.1, in PCA space, calculating all reference feature points and query feature points in the single subset The squared euclidean distance value between them willThe squared Euclidean distance values corresponding to the nearest neighbors are ranked from small to large to form a filter stack; in the original space, all the reference feature points and query feature points in the subset are calculatedThe Euclidean distance value between the two willSorting Euclidean distance values corresponding to the nearest neighbors from small to large to form a verification stack;

Step 3.2.2, filtering single reference feature points: in PCA space, calculating a certain reference feature point and a query feature point A squared euclidean distance value between; if the square Euclidean distance value is larger than or equal to the distance maximum value in the filter stack, discarding the reference feature point; otherwise, calculating the reference feature point and the query feature point in the original spaceIf the Euclidean distance value is larger than or equal to the distance maximum value in the verification stack, discarding the reference feature point; otherwise, inserting the squared Euclidean distance value calculated in the PCA space in the step 3.2.2 into the filter stack so as to replace the distance maximum value in the filter stack and re-ordering to obtain a new filter stack, replacing the original filter stack with the new filter stack, inserting the Euclidean distance value calculated in the original space in the step 3.2.2 into the verification stack so as to replace the distance maximum value in the verification stack and re-ordering to obtain a new verification stack, and replacing the original verification stack with the new verification stack;

step 3.2.3, returning to step 3.2.2, filtering each reference feature point in the subset to obtain the latest filter stack, and selecting according to the distance value sequence in the latest filter stack The nearest neighbor corresponding squared Euclidean distance value is the subsetNearest neighbor results;

Step 3.3.4, returning to step 3.2.1, and respectively carrying out the steps of 3.2.1 to 3.2.3 Filtering the reference feature points in each subset to generate each subsetNearest neighbor results;

Step 3.3, combining each subset The nearest neighbor results are added to the maximum heap in turn, and the maximum heap is adjusted so that the maximum in-heap generation is achievedNearest neighbor results;

step 3.4, selecting the characteristic points of the k nearest neighbor results in the maximum heap and the query The nearest reference feature point is calculated and the reference feature point and the query feature point are calculatedIf the pixel distance is smaller than or equal to the preset pixel, determining the corresponding point of the reference feature point in the original space as the query feature pointIf not, judging the reference feature point setIn the absence and inquiry of characteristic pointsCorrectly matched reference feature points;

step 4, respectively judging the query feature point sets according to the method of step 3 Whether each query feature point has a correctly matched reference feature point or not can further obtain all correct matching point pairs, and further realize imagesAnd imageIs a feature match of (a).

2. The algorithm for matching feature of reduced-dimension parallel images by combining principal component analysis and double-stack filtering according to claim 1, wherein the step 3.3 is specifically: the initial maximum heap is the empty set, each subset will beThe nearest neighbor results are sequentially added into the maximum pile, the distance values in the maximum pile are compared, and the maximum pile is continuously adjusted, so that the final maximum pile is reservedNearest neighbor results, i.eThe nearest neighbors correspond to squared euclidean distance values.

3. The algorithm for feature matching of a dimensionality reduction parallel image for fusion principal component analysis and dual stack filtering of claim 1, wherein the preset pixel value in step 3.4 is 1.5 pixels.

4. The fused principal component analysis and dual stack filtered dimension-reduction parallel image feature matching algorithm of claim 1, further comprising:

step 5: judging the set of the reference feature points In (1) whether there is a feature point set with the queryQuerying feature pointsCoarse matching reference feature points:

Step 5.1, in the PCA space, the reference feature points are collected Divided intoA subset of the plurality; querying feature pointsProjection points projected into a low-dimensional PCA space are marked as query feature points；

Step 5.2, calculating all reference feature points and query feature points in the single subsetThe squared Euclidean distance of (2) judges whether the feature points are inquired or not in the subset according to the ratio of the nearest neighbor distance to the next nearest neighbor distanceCoarse matching of reference feature points;

step 5.3, judging whether the characteristic points are in the query feature points in each subset according to the method of step 5.2 Coarse matching of reference feature points; if none exist, judging that the reference feature point set isDoes not exist and inquires about characteristic pointsCoarse matching of reference feature points; otherwise, acquiring and inquiring the feature pointsSelecting and inquiring feature points from all the obtained reference feature points by rough matchingNearest neighbor reference feature point, corresponding point in original space of the reference feature point is used as query feature pointIs a coarse matching point of (2);

step 6, according to the method of step 5, respectively judging the query feature point sets Whether each inquiry feature point has rough matching reference feature points or not is judged, and all rough matching point pairs are obtained;

Step 7: and calculating the matching accuracy, wherein the matching accuracy is the percentage of the correct matching point logarithm to the total matching point logarithm, and the total matching point logarithm is the coarse matching point logarithm.

5. The algorithm of feature matching of reduced-dimension parallel images with fused principal component analysis and dual-stack filtering as claimed in claim 4, wherein in step 5.2, it is determined whether there is a feature point to be queried in the subset according to the ratio of nearest neighbor distance to next nearest neighbor distanceThe reference feature points of coarse matching are specifically as follows:

the ratio formula (1) of the nearest neighbor distance to the next nearest neighbor distance is:

；

wherein, Representing query feature pointsThe squared euclidean distance between the reference feature points nearest to it,Representing query feature pointsThe squared euclidean distance between the reference feature points that are the next closest to it,If the distance ratio threshold value satisfies the formula (1), the query feature points are to be compared withThe nearest reference feature point is marked as the query feature pointCoarse matching of reference feature points; otherwise, no feature points are present in the subsetAnd (5) roughly matching the reference feature points.

6. The algorithm for matching feature of reduced-dimension parallel images by combining principal component analysis and double-stack filtering according to claim 1, wherein the step 2 is specifically:

Step 2.1, forming a matrix by feature descriptors of all reference feature points and query feature points in the original space Singular value decomposition method is adopted to calculate matrixAccording to the characteristic value and the preset value of the cumulative contribution rate, obtaining the number of the corresponding principal components when reaching the cumulative contribution rate；

Step 2.2, according to the number of main componentsBefore selectingThe feature vector corresponding to the largest feature value forms a projection matrix by the selected feature vector；

Step 2.3, according to the projection matrixTo image in original spaceReference feature point set in (a)And an imageIn a query feature point setRespectively projected into a low-dimensional PCA space.

7. The feature matching algorithm for merging principal component analysis and dual-stack filtering dimension-reduction parallel images according to claim 6, wherein in step 2.1, the preset value of the cumulative contribution rate is a preset range value of the cumulative contribution rate, and the number of principal components corresponding to the preset range value of the cumulative contribution rate is calculatedIs a range value of (2);

According to the method of step 3-4 and according to different numbers of main components Calculating the value of the matching point pair number to obtain the correct matching point pair number between the two images to be matched;

setting an evaluation index, and evaluating different numbers of main components according to the evaluation index The matching performance corresponding to the value of (2) is selected, and the number of the corresponding principal components is selected when the matching performance is optimalAs the final number of principal componentsThe values of (2) are used in step 2 to calculate a projection matrixAnd finally, obtaining all correct matching point pairs between the two images.