Is it computationally redundant to solve the optimal rigid transformation with joint SVD+RANSAC?

5 views (last 30 days)
I randomly used two sets of 2D point sets to estimate the optimal rigid transform (or similar transform) to performance, and used the MATLAB built-in function estgeotform2d and the OpenCV built-in function estimateAffinePartial2D for comparison, and MATLAB is significantly more time consuming when the number of test points is high.
% 1000 rand sample points test
pts1 = 100*rand(1000,2);
pts2 = 100*rand(1000,2);
% MATLAB
t = tic;
[tform,inlier,status] = estgeotform2d(pts1, pts2, "rigid",... % or use "similarity"
MaxNumTrials=1000,...
Confidence=0.99,...
MaxDistance=1.5);
t1 = toc(t)
% OpenCV-python
pts1 = py.numpy.array(pts1);
pts2 = py.numpy.array(pts2);
t =tic;
out = py.cv2.estimateAffinePartial2D(pts1,pts2,py.None,py.cv2.RANSAC,1.5,uint32(1000),0.99);
t2 = toc(t)
t1 =
0.2382
t2 =
0.0036
It can be seen that t1 takes more time than t2. (t1/t2=67)
After my in-depth investigation found that the MATLAB built-in function estgeotform2d internal at the same time using the SVD + RANSAC algorithm for estimation, while OpenCV only uses the RANSAC algorithm estimation, which leads to a significant difference in the calculation time!
while idxTrial <= numTrials && skipTrials < maxSkipTrials
% Random selection without replacement
indices = randperm(numPts, sampleSize);
% Compute a model from samples
samplePoints = allPoints(indices, :, :);
modelParams = funcs.fitFunc(samplePoints, varargin{:}); % note: only samplePoints pass to SVD,so SVD can't not really working "optimally"?
... omit code
end
Starting from line 65 in “MATLAB_INSTALL_PATH/toolbox/vision/vision/+vision/+interna/+ransac/msac.m” file, the RANSAC algorithm randomly selects the minimum number of fixed points to be given to the fitting function in each iteration, which shows that the SVD algorithm is not really working "optimally" because the minimum number of points is passed to the SVD algorithm each time, so I think this calculation is redundant?
RUN in R2023a

Accepted Answer

cui,xingxing
cui,xingxing on 15 Sep 2023
Edited: cui,xingxing on 27 Apr 2024
By carefully reading the MATLAB and OpenCV source code, fortunately I discovered part of the reason for the time-consuming process, which lies mainly in the differences in the design of the two:
1. Matlab's ransac's fitting function fitFunc solves for the model parameters directly using SVD, whereas OpenCV brings in the solution directly through the analysis results, which does redundancy in computational resources to some extent;
2. the last part of Matlab's ransac also uses recomputing the model parameters based on all the inlier points (recomputeModelFromInliers field name), which increases the time consuming to some extent, but this ensures the robustness of the results, which is more reliable than OpenCV results! In this section, SVD solving for optimal parameters is essential!
3. All geometric transformation functions used by Matlab for estimation are computed based on its own m-language, whereas OpenCV-python uses C++ in underlying.
To summarise: MATLAB is a bit time-consuming (especially when there are a lot of mismatched points), but provides more stable and reliable results than OpenCV.
Reference
robust least squares fit for circle (note: ransac fit based on all inlier points)
-------------------------Off-topic interlude, 2024-------------------------------
I am currently looking for a job in the field of CV algorithm development, based in Shenzhen, Guangdong, China,or a remote support position. I would be very grateful if anyone is willing to offer me a job or make a recommendation. My preliminary resume can be found at: https://cuixing158.github.io/about/ . Thank you!
Email: cuixingxing150@gmail.com

More Answers (0)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!