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

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

Answer 1

[cui,xingxing]

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: [e-mail]