An improved RANSAC algorithm for 3D wheel alignment

CHENG Wei, ZHU Zhifeng, YAO Yong, WANG Bing, ZHOU Fang, TANG Dezhi

(1. School of Electrical and Information Engineering, Anhui University of Technology, Ma’anshan 243000, China； 2. Anhui FCAR Electronic Technology Co., Ltd., Ma’anshan 243000, China)

Abstract： Aiming at the defects of traditional four-wheel aligner such as many sensors, complex operation and slow detection speed, a fast and accurate 3D four-wheel alignment detection method is studied. Firstly, a new and special circle center target board is designed to calibrate the camera, and then the registration of the homography matrix is optimized by using the improved RANSAC (Random sample consensus) algorithm combined with the designed special target board, and the parameters of the wheel alignment system are adjusted by using the space vector principle. Accurate measurements are made to obtain the parameters of the four-wheel alignment. Design a calibration comparison experiment between the traditional target board and the new type of target board, and conduct a comparative test with the existing four-wheel aligner of the depot. The experimental results show that the use of the new target board-binding optimization algorithm can improve the calibration efficiency by about 9% to 21%, while improving the calibration accuracy by about 10.6% to 17.8%. And through the real vehicle test, it is verified that the use of the new target combined with the optimization algorithm can ensure the accuracy and reliability of the four-wheel positioning. This method has a certain significance in the rapid detection of vehicle four-wheel alignment parameters.

Key words： computer vision； four-wheel alignment； binocular calibration； RANSAC algorithm； homography matrix

0 Introduction

During the driving process of the car, the alignment parameters of the tires change due to some external factors such as collisions, bumps or tire replacement. In order to ensure the safety of car driving, prolong the service life of tires and reduce fuel consumption, it is necessary to perform four-wheel alignment operations for the car, and adjust the positioning parameters to make them conform to the original factory specified values.

Four-wheel alignment is the core technology originally used in the market, such as laser positioning technology, CCD positioning technology, etc. It has been replaced by 3D positioning technology. One of the methods is 3D four-wheel alignment monocular stereo vision matching technology, which can be used to measure the motion state of objects during motion. Its design is very simple, but the calculation of relevant parameter values must be constrained by the target board model, and the calibration accuracy is low. Another method is introduced to determine the three-dimensional motion parameters of objects from binocular sequence images. Although this method has a lower cost, it has higher requirements on the surrounding environment, and it is more sensitive to light intensity and more complicated to calculate.

In this paper, the calibration accuracy of the camera is improved and the key parameters are optimized and solved, which reduces the data acquisition error and improves the detection speed.Firstly, vector detection and three-dimensional perspective theory are used to establish a homography matrix to solve the equation. And then a special circular target board is designed, and the RANSAC algorithm is improved to optimize the homography matrix. Thus the conversion of 2D image data to 3D space data is completed. Finally, the improved algorithm is designed, and the optimal matrix is used to detect the four-wheel alignment. The results show the effectiveness and accuracy of the optimized algorithm.

1 Mathematical model

1.1 Coordinate system transformation

According to the camera imaging model, as shown in Fig.1, the conversion relationship among coordinate systems is established.

Fig.1 Camera imaging model

According to the camera imaging model, the relationship among each coordinate system is established. Firstly, establish the coordinate transformation from the image coordinate system (o-x,y) to the pixel coordinate system (u,v). Secondly, establish the coordinate transformation from the camera coordinate system (OC-XC,YC,ZC) to the image coordinate system. Thirdly, establish the coordinate transformation from the world coordinate transformation between the coordinate system (OW-XW,YW,ZW) to the camera coordinate system. Finally, the coordinate transformation from the world coordinate system to the image pixel coordinate system is completed.

(1)

1.2 Monocular camera calibration

The coordinate system is established on a two-dimensional plane target board, the coordinate axisZW=0, the coordinate of a feature point extracted on the target board isM=(XW,YW,1)T, and the image pixel coordinate after imaging ism=(u,v,1)T. Then the relationship is

(2)

wheresis the scale factor；His the homography matrix；rij(i=0,1,2) is the column vector ofR；Ais an eigenmatrix.

1.3 Optimization of homography matrix

The target board information changing with the wheel movement is collected by using camera, and the two dimensional point coordinates of the image and the three-dimensional point coordinates of the target board are obtained.

(3)

Coupled with the equationh31xi+h32yi+h33=1 deduced by Eq.(4), theHmatrix can be solved. In order to ensure that the calculation results are more accurate, the optimal solution ofHis obtained by using the points on all the plane objects that match the image points.

In order to further optimize theHmatrix, the optimal solution ofHis calculated by using all matched feature points. The RANSAC method is used to determine the optimal homography matrix for the mapping of points on the world coordinate system to the image coordinate system. And Eq.(4) is shown as

(4)

whereHis a 3×3 matrix equation with 9 unknown parameters. One feature point corresponds to 2 equations, and 4 feature points correspond to 8 equations. In theory, four sets of corresponding feature points can be used to solve the homography matrix, but in real application scenarios, the number of feature points is huge and may contain a lot of noise, resulting in deviation of pixel position. Therefore, using four groups of point pairs to calculate homography matrix will have a large error.

Homography matrices are usually calculated for solving nonlinear systems of equations, such as the least squares method, but this method is suitable for situations where the error is small and the amount of data is small. The RANSAC algorithm can robustly estimate the parameter model and high-precision parameters from a data set containing a large number of outliers, so it can well meet the needs of optimizing theHmatrix.

1.4 Improvement of target board

In the traditional random sampling consensus algorithm randomly, 4 non-collinear points are selected from multiple feature points, which makes the computation intensively and slowly. Therefore, a new feature point selection method is designed.

Fig.2 Schematic diagram of traditional target board

The circular target board is used as the camera calibration target board, and the center of the circular target board is used as the feature point. Since RANSAC is used to optimize the matrix, it is necessary to randomly select 4 of all feature points to calculate each time. And according to the arrangement and combination, too many feature points will greatly increase the amount of calculation. The traditional circular target board adopts a 5×5 circular array arrangement as shown in Fig.2. According to the permutation and combination, there are more than 450 000 point selection methods, including a variety of cases where four points are collinear.

Therefore, the newly designed target board is adopted for calibration to optimize the homography matrix. The schematic diagram of the new target board is shown in Fig.3.

Fig.3 Schematic diagram of new target board

There are 8 circular target boards of the same size, and the coordinates of the center of each circular target board are known.

1.5 RANSAC algorithm optimization steps

When the traditional random sampling consensus algorithm determines the threshold, a method of artificially setting a threshold is usually adopted. This leads to certain limitations when processing different data with the same threshold, which is manifestedas the increased number of iterations, long processing time and low precision of the final processing. Aiming at the problem, a dynamic threshold method is proposed based on measurement error, which uses the error of the data set itself to determine the threshold, and improves the accuracy and efficiency of data processing. At the same time, a new judgment iterative judgment method is proposed for the iterative problem of determining the optimal matrix, which reduces the number of iterations and improves the running speed of the algorithm compared with the traditional method.

The specific method of optimizing the homography matrix based on the RANSAC algorithm is shown as 1)-5)：

1) Taking point. There are 9 unknown parameters in the homography matrix, at least 9 linear equations are required to solve. Corresponding to the point position information, a set of point pairs can list 2 equations, which contains at least 4 sets of matched point pairs to get 8 equations. Together withH31xi+H32yi+H33=1, the homography matrixHcan be solved. The design of this target board can ensure that every 3 points in each set of randomly selected feature points are not collinear, and each point has the equationH31xi+H32yi+H33=1, then there are 3 equations. Therefore, only 3 sets of matching point pairs are be chosen to get 9 equations. According to the arrangement and combination, there are a total of 56 point selection methods.

2) CalculatingHifor 56 sets of feature points. According to the two-dimensional data (ui,vi) of the four target board feature points read by the camera, the corresponding homography matrixHiis calculated by using Eq.(3).

(5)

It is also expressed by

(6)

(7)

wheremis the number of sample points. Then the thresholdtcan be obtained by calculation.

4) Determining the maximum number of iterationsK. The number of iterationsKcan be calculated by the mathematical principle of RANSAC. When estimating the model parameters,pis used to represent the probability that the points randomly selected from the data set during some iterations are inliers. The resulting model is likely to be useful at this time, sopalso characterizes the probability that the algorithm produces a useful result. The probability of selecting one interior point from the data set at a time is denoted byw, which is equal to the number of interior points divided by the total number of data. The value ofwis generally unknown, but some robust values can be given. Assuming thatnpoints need to be selected for the estimation model,wnis the probability that allnpoints are interior points. 1-wnis the probability that at least one of thenpoints is an outside point, which indicates that a bad model is estimated in the dataset. log(1-wn)krepresents the probability that the algorithm never selectnpoints to be interior points, which is the same as 1-p. The logarithm of both sides of log(1-wn)kis taken to get that

(8)

Therefore, the number of iterations can be determined according to Eq.(8).pis the confidence level, which generally takes the value of 0.995, andnis the minimum number of samples needed to calculate the model, which is taken asn=4. Assuming that more than half of the 8 feature points of an image are interior points. And assuming that the value ofwis 7/8, the calculated value ofKis 6. When the value ofwis 5/8, the value ofKis calculated as 33. It takes 33 iterations less than 56. If more than half of the 8 feature points are not interior points, it means that the image has a large error and is discarded.

5) Determining the optimalH. ① The homograph matrixHof each feature point group in step 2 is calculated, and then step 4 is used to judge the interior points of the 8 points in the target board. If the number of interior points in one of the feature point groups is less than 4, the set of feature points and the correspondingHis discarded. If more than half of the feature point groups are discarded in an image, it means that the error of the image is too large, and the image is discarded. ② If the number of inliers in one of the feature point groups is greater than 4, the group of 4 feature points and the correspondingHare retained, and the inliers are added to the inlier set I. ③ Let the interior point set corresponding to the first set of feature points be the optimal interior point set I_best, and test the remaining feature point sets according to the same method. If the number of elements in the current interior point set I is greater than the optimal interior point set I_best, then update I_best=I. If the number of elements in the current interior point set I is less than the optimal interior point set I_best, the group of 4 feature points and the correspondingHmay be discarded. If the number of elements in the current interior point set I is equal to the optimal interior point set I_best, then keep the group of 4 feature points and the correspondingHto continue the next group of calculations. ④ If there is no feature point group with repeated inner points during the calculation, theHcorresponding to the last reserved set of feature point groups is the optimal homography matrix. ⑤ If there are multiple sets of feature point groups, then 4 feature points are randomly selected from the retained feature points to form a group, repeat the previous steps until the number of repetitions is greater thanK, and output a set of features obtained by the last cycle. TheHcorresponding to the point group is the optimal homography matrixH.

1.6 Binocular camera calibration

In the joint calibration, the original calibration rod is placed horizontally into the visual area of the left and right cameras, so that the near target boardM1and far target boardM2are imaged in the left and right cameras, respectively. Then, the relative positional relationship between the two cameras can be calculated through the positional relationship of the two target boards, so

(9)

whereR2-1andT2-1are the rotation and translation matrices from theC2coordinate system to theC1coordinate system；RM21indicates that the pose of targetM2is attributed toM1in the left camera vision area, andTM21indicates that the pose ofM2is attributed toM1in the right camera vision area；R1andT1are the rotation matrix and translation vector of the targetM1in the visual area ofC1；R2andT2are the rotation matrix and translation vector of the targetM2in the visual area ofC2.

1.7 Calculation of direction cosine

According to the Rodrigue rotation formula, it can be known that the rotation axis can be obtained according to the rotation matrix, and then the cosine of the direction can be obtained. The vectorv′ can be obtained by rotating the vectorvaround the rotation axisnby an angle ofθ, and its relationship is shown as

v′=(v-v·n)·ncosθ+(n×v)sinθ+(v·n)·n.

(10)

The unit vectornrepresents the rotation axis, andθis the rotation angle.

[p,q,l]R(n,θ)=[p′,q′,l′],

(11)

wherep,q,lare the coordinates of the base vector rotated around the rotation axis in three-dimensional coordinates；Ris the rotation matrix；p′,q′,l′ are the coordinates of the rotated base vector. The expressions to getp′,q′,l′ are

where the (n1,n2,n3) is cosine direction of the axis of rotation. It can be obtained that

(13)

2 RANSAC algorithm programming

In the three-dimensional four-wheel positioning system, the circular target board installed on the wheel hub is firstly photographed with a camera, and the camera’s internal parameter matrix and the homography matrix are obtained through the calibration program. Then these two parameters can be combined to solve the spatial position and attitude of the target board. Finally, the rotation axis is solved by the Rodrigues formula, and the rotation angle is obtained, so as to solve the four-wheel alignment parameters. Since the internal parameters of the camera are fixed, the optimization of the homography matrix will directly affect the accuracy of the four-wheel alignment parameters. Therefore, the improved RANSAC algorithm is used to optimize the matrix, thereby improving the accuracy of the four-wheel alignment.

This algorithm programming is based on C++ language by using VS2019 to configure OpenCV. The transformation between the three-dimensional coordinates of the feature points on the acquisition target board and the two-dimensional coordinates of the feature points on the camera image plane is realized, and the homography matrix between the two is obtained, and the matrix is optimized.

First, call the function that calculates the homography matrix, including 5 parameters： two-dimensional coordinatesimage_points_seq[i] of feature points on the camera image plane, three-dimensional coordinatesobject_points_seq[i] of feature points on the target board, using RANSAC method, inputting threshold, parameter and confidence. Then, enter the RANSAC optimization function, use the getSubet function to take out the corresponding four sets of coordinate data, calculate its matrix, judge whether the projection error is less than the dynamic threshold, and save the number of returned interior points to the goodcount array. Finally, a set of feature point groups with the maximum number of interior points is found by looping, and the corresponding homography matrix model is output. The pseudo code of the algorithm is shown below.

Input：inputsampleset：m={m1,m2,m3…mn},M={M1,M2,M3…Mn}，datamodel：model,themaximumnumberofiterations：K,Threshold：t,confidence：p

Output： bestmodel

1.ω=Inliers/length{m}

2.K=log(1-p)/log(1-ω4)

3.iterations=0,best_model=null

4.while(iterations

5.consensus_set=emptyset

6.maybeInliers=pick4pointsrandomlyamong{m},{M}

7.maybe_model=runKernel(maybeInliers)

8.formaybeOutliersdo

10.addpointtoconsensus_set

11.ifnumeberofconsensus_set>4then

12.betterModel∶=modelparametersfittedtoallpointsinconsensus_set

13.goodCount=numeberofconsensus_set

14.if(goodCount>maxgoodCount)then

15.best_model=better_model

16.maxgoodCount=goodCount

17.endif

18.else

19.giveup

20.endif

21.incrementiterationsendwhile

The algorithm flow chart is shown in Fig.4.

Fig.4 RANSAC algorithm flow chart

3 Results and discussion

3.1 H matrix optimization test

The camera used in this article is a USB industrial camera. When using, the target board is placed in front of the camera, and the left and right cameras are separated by an appropriate distance. Connect the camera to the PC software on the PC, and adjust the target board position so that the left and right cameras can capture clear bright and low-exposure images.The left and right cameras are used to capture new target board simultaneously by the first group. After collecting a picture, the posture of the target board is adjusted to ensure that the relative position of each target board picture and the camera is different, and 12 target board images are collected as shown in Fig.5. The calibration program is called to process the new target board images, and the parameters of the camera and the homography matrixHare obtained. The second group uses the left and right cameras to shoot traditional target board in the same way, collecting a total of 12 target board images, as shown in Fig.6. Similarly, the calibration program is called to process the traditional target board images, and the parameters of the camera and the homography matrix are obtained.

Fig.5 Novel target board images

Fig.6 Traditional target board images

In camera calibration, the size of the reprojection error is usually used to determine the quality of camera calibration. Therefore, during the experiment, the optimization effect is determined by comparing the reprojection errors obtained by the non-optimized algorithm and the optimized algorithm. The optimized and unoptimized algorithms are used to calibrate the new target board images in Fig.3, respectively. And the parameters of the camera, the reprojection error and the time required for calibration are obtained. The experimental results are shown in Table 1. The traditional target board images in Fig.4 is calibrated, and the experimental results are shown in Table 2.

Table 1 Novel target board calibration data

Table 2 Traditional target board calibration data

The calibration time in the experimental data is analyzed, as shown in Fig.7. It can be clearly seen from Fig.7 that the calibration time using the new target board is shorter than that of using the traditional target board. Combined with the quantitative analysis of the experimental data, it is concluded that the calibration efficiency using the new target board is increased by about 9%-21%.

The calibration time after using the optimization algorithm is also less than the calibration time without the optimization algorithm. Combined with the quantitative analysis of the experimental data, it is concluded that the calibration efficiency using the optimization algorithm is increased by about 11.6%-16.6%.

Fig.7 Calibration time comparison chart

The reprojection error in the experimental data is further analyzed, and the error map is shown in Fig.8.

Fig.8 Error comparison analysis chart

The abscissa represents the type of error, and 1 and 2 represent the average error of each target image of the left and right cameras, respectively. 3 and 4 represent the average error of each pixel of the left and right cameras, respectively. It can be seen that the error after using the optimization algorithm is slightly smaller than that without the optimization algorithm, and the error of using the new target board calibration is smaller than that of the traditional target board calibration. Combined with the quantitative analysis of the experimental data, it is concluded that the optimization algorithm can improve the calibration accuracy by about 10.6%-17.8%.

3.2 Wheel alignment test

In the real vehicle test, the selected model is the Skoda sedan, and the new target board instrument is fixed on the car hub at a certain angle by using a fixture. The real vehicle test is shown in Fig.9. The left and right cameras are 5-megapixel industrial cameras. Move the vehicle back and forth, and take pictures with the camera. At the same time, the status of the target board is displayed on the computer screen. The target board monitoring diagram is shown in Fig.10.

Fig.9 Real car test chart

Fig.10 Target board monitoring chart

In order to avoid the problem of erroneous experimental data due to too few experiments, the caris tested six times. After each experiment, the vehicle is moved a certain distance and the body is turned by a certain angle. Test whether the use of novel target boards affects the acquisition of target boards when the vehicle is placed at different distances and angles, thereby affecting the accuracy of the calibration. The results of the 6 tests are compared with the standard data of the car manufacturer. The data comparison results are shown in Table 3.

It can be seen from the results in Table 3 that when the vehicle is 2 m-2.5 m away from the calibration device, and the body rotation angle is within the range of 0°-10°, the results of the six experiments are basically the same, and the error is small compared with the simulated experimental data. The reliability of the four-wheel alignment detection using the new calibration target board is shown. The validity of the detection device and method designed in this paper is verified.

4 Conclusions

Computer vision theory is applied to study a process of solving four-wheel positioning parameters, and the methods of homography matrix optimization and rotation matrix singular value decomposition are proposed. Then, the RANSAC algorithm is used in combination with the designed special target board to optimize the registration of the homography matrix. The use of 8 target board points reduces the amount of calculation and optimizes the iterative method for selecting the optimal matrix. Compared with the traditional target plate, the calibration efficiency is improved by about 9%-21%. At the same time, the dynamic selection of the threshold value makes the calculation result of the homography matrix more accurate, which improves the calibration accuracy by about 10.6% to 17.8%. Finally, the wheel rotation axis is calculated by the space vector method, and the four-wheel alignment parameters are obtained. According to the field test data, within the range of 2 m-2.5 m from the vehicle distance calibration device and 0°-10° of vehicle body angle deflection, it can well meet the four-wheel alignment detection requirements. Therefore, the 3D four-wheel positioning detection method proposed in this paper is different from the traditional detection method, and has certain application prospects.

For the experimental error, it may be solved by the following methods. The target board board may be calibrated by moving the target board or adjusting the position of the camera. The experimental parameters may be set according to the lighting environment of the experimental site. Providing lift measurement may overcome, the experimental deviation caused by the unequal factors of the experimental site and the parking position of the vehicle. Therefore, the algorithm can be further optimized by changing the relevant facility conditions of the experimental environment to make the test results more accurate.