Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork56.4k
New LevMarq implementation#21018
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
Uh oh!
There was an error while loading.Please reload this page.
Conversation
alalek left a comment
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
We should revise public API.
Keep minimal part which is necessary for user application (tests).
Internal interfaces like "BaseLevMarq::Backend" should be hidden.
modules/3d/include/opencv2/3d.hpp Outdated
| For more details, please refer to Wikipedia page (https://en.wikipedia.org/wiki/Levenberg%E2%80%93Marquardt_algorithm). | ||
| */ | ||
| classCV_EXPORTSLMSolver : public Algorithm | ||
| classCV_EXPORTSBaseLevMarq |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
BaseLevMarq -> LevMarqBase or LevMarqSolver
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Done
Uh oh!
There was an error while loading.Please reload this page.
modules/3d/include/opencv2/3d.hpp Outdated
| Ptr<Backend> pBackend; | ||
| BaseLevMarq(Ptr<Backend> backend_) : |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Again,const reference for all input parameter.
no underscores in names if we don't need them.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
fixed
modules/3d/include/opencv2/3d.hpp Outdated
| // normalize jacobian columns for better conditioning | ||
| // slows down sparse solver, but maybe this'd be useful for some other solver | ||
| bool jacobiScaling; | ||
| // double upFactor until the probe is successful | ||
| bool upDouble; | ||
| // use stepQuality metrics for steps down | ||
| bool useStepQuality; | ||
| // clamp diagonal values added to J^T*J to pre-defined range of values | ||
| bool clampDiagonal; | ||
| // to use squared L2 norm or Inf norm for step size estimation | ||
| bool stepNormInf; | ||
| // to use relEnergyDeltaTolerance or not | ||
| bool checkRelEnergyChange; | ||
| // to use minGradientTolerance or not | ||
| bool checkMinGradient; | ||
| // to use stepNormTolerance or not | ||
| bool checkStepNorm; | ||
| // to use geodesic acceleration or not | ||
| bool geodesic; | ||
| // second directional derivative approximation step for geodesic acceleration | ||
| double hGeo; | ||
| // how much of geodesic acceleration is used | ||
| double geoScale; | ||
| // optimization stops when norm2(dx) drops below this value | ||
| double stepNormTolerance; | ||
| // optimization stops when relative energy change drops below this value | ||
| double relEnergyDeltaTolerance; | ||
| // optimization stops when max gradient value (J^T*b vector) drops below this value | ||
| double minGradientTolerance; | ||
| // optimization stops when energy drops below this value | ||
| double smallEnergyTolerance; | ||
| // optimization stops after a number of iterations performed | ||
| unsignedint maxIterations; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
No fields in public API.
This is the primary requirement of public OpenCV API.
getter/setter should be exposed instead.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
can we try to utilizehttps://github.com/opencv/opencv/wiki/OE-34.-Named-Parameters? It lets to define very nice API for C++ and Python (and maybe Swift after the corresponding binding generator is revised)
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Implemented it as aSettings structure
modules/3d/include/opencv2/3d.hpp Outdated
| double energy; | ||
| }; | ||
| classBackend |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Looks like it is not used by user code directly. Move to src or details.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
The motivation to leave theBackend in public was to let a user to construct solvers that use sparse matrices, params of SE(3) and of more exotic groups, with fixed variables and so on.
I will try to move it to details to keep this possibility.
(However the interface is very complicated for a user)
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Backend is moved to details header
| bool found; | ||
| int iters; | ||
| double energy; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
missing documentation
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Added docs forReport structure
| inline Vec<T,3> DualQuat<T>::getTranslation(QuatAssumeType assumeUnit)const | ||
| { | ||
| Quat<T> trans =2.0 * (getDualPart() *getRealPart().inv(assumeUnit)); | ||
| Quat<T> trans =T(2.0) * (getDualPart() *getRealPart().inv(assumeUnit)); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Such changes should be backported to 4.x
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Backported to#21319 and#3137@contrib
modules/calib/src/calibration.cpp Outdated
| solver.maxIterations = (unsignedint)(termCrit.maxCount *2.1); | ||
| solver.stepNormTolerance = termCrit.epsilon; | ||
| solver.smallEnergyTolerance = termCrit.epsilon * termCrit.epsilon; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
We should have setter with TermCriteria parameter.
maxIterations = (unsigned int)(termCrit.maxCount * 2.1);
2.1
Why?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
2.1 is a compatibility hack. Old impl counts successful iterations only, the new one counts all iterations.
The proportion between them for the same run is different per use case but in average it is 2.1:newIters = oldIters*2.1
I propose three solutions here:
- to leave this hack as is (adding a comment about it in src)
- to find true multiplier for each use case based on iterations elapsed statistics
- remove the multiplier: it's 5.x now, we don't have to maintain such parameters compatibility
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
I think, having such a hack is fine.
- If the problem solved is more or less well-defined (not ill-posed), the solver should converge faster than it will reach the maximum.
- If the problem solved is ill-posed then we will do at least termCrit.maxCount iterations, so this hack may affect the speed, but not the quality. But, I believe, because the new solver uses the sparse structure of matrices, it should run even faster than the previous "dense" implementation.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Multiplier removed, statistics recalculated.
RegardingTermCriteria usage: I'm against it, it has only one epsilon parameter and it's not obvious to what threshold in this LevMarq impl it corresponds to.
modules/3d/include/opencv2/3d.hpp Outdated
| initialLmDownFactor(3.0) | ||
| { } | ||
| booloperator==(const Settings& other)const |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
If users don't need this functionality, then it is better to create internal function.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Removed
(was made to compare a passed arg with default settings constant, default arg is used instead)
modules/3d/include/opencv2/3d.hpp Outdated
| Settings() : | ||
| jacobiScaling(false), | ||
| upDouble(true), | ||
| useStepQuality(true), |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Move ctor implementation to .cpp file.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Done
modules/3d/include/opencv2/3d.hpp Outdated
| Settings&jacobiScalingS (bool v) { jacobiScaling = v;return *this; } | ||
| Settings&upDoubleS (bool v) { upDouble = v;return *this; } | ||
| Settings&useStepQualityS (bool v) { useStepQuality = v;return *this; } |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Why is here 'S' suffix?
Where are you find that?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
S stands for "set" but I didn't want to give them names likesetEpsilon to make method names more compact.
Since you recommended not to use underscores, I seek other ways to name them.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Decided to usesetValue names instead, looks more natural
modules/3d/include/opencv2/3d.hpp Outdated
| return ok; | ||
| } | ||
| Settings&jacobiScalingS (bool v) { jacobiScaling = v;return *this; } |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
inline for all setters
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Done
modules/3d/include/opencv2/3d.hpp Outdated
| Settings&relEnergyDeltaToleranceS(double v) { relEnergyDeltaTolerance = v;return *this; } | ||
| Settings&minGradientToleranceS (double v) { minGradientTolerance = v;return *this; } | ||
| Settings&smallEnergyToleranceS (double v) { smallEnergyTolerance = v;return *this; } | ||
| Settings&maxIterationsS (unsignedint v) { maxIterations = v;return *this; } |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
unsigned int
This type may be non-friendly with bindings.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Replaced by int
modules/3d/include/opencv2/3d.hpp Outdated
| /* | ||
| Defined in details header | ||
| */ | ||
| classCV_EXPORTS Backend | ||
| { | ||
| public: | ||
| virtual~Callback() {} | ||
| /** | ||
| computes error and Jacobian for the specified vector of parameters | ||
| @param param the current vector of parameters | ||
| @param err output vector of errors: err_i = actual_f_i - ideal_f_i | ||
| @param J output Jacobian: J_ij = d(err_i)/d(param_j) | ||
| when J=noArray(), it means that it does not need to be computed. | ||
| Dimensionality of error vector and param vector can be different. | ||
| The callback should explicitly allocate (with "create" method) each output array | ||
| (unless it's noArray()). | ||
| */ | ||
| virtualboolcompute(InputArray param, OutputArray err, OutputArray J)const = 0; | ||
| virtual~Backend() { } |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Defined in
Is it not a definition?
Why does forward declaration not work here?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Backend class removed
modules/3d/include/opencv2/3d.hpp Outdated
| The final vector of parameters (whether the algorithm converged or not) is stored at the same | ||
| vector. The method returns the number of iterations used. If it's equal to the previously specified | ||
| maxIters, there is a big chance the algorithm did not converge. | ||
| LevMarqBase(const Ptr<Backend>& backend,const Settings& settings); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Users don't really need this constructor. As they can't use it.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Fixed, see the comment below
…, no Backend class, Settings() => .cpp, Settings==() removed, Settings.set...() inlines
savuor commentedDec 26, 2021
|
alalek left a comment
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Looks good to me 👍
Uh oh!
There was an error while loading.Please reload this page.
Merge with extra:opencv/opencv_extra#942
Merge with contrib:opencv/opencv_contrib#3127
TODOs:
run(params)for linear, various factories, return report after optimizationDEBUGcode and fulfill allTODOstatementsWhat?
NewLevenberg-Marquadt algorithm implementation replaces the old one.
Why?
Because the old impl isn't as good as we want:
This stops it from using in some complex 3d-related problems such as pose graph optimization.
An algorithm termination deserves its own list offeatures:
This is not OK even for a basic LevMarq solver.
How?
A new code fixes everything:
This code is based on a current pose graph optimization routine. As a result, the pose graph has been rewritten too, now it uses the same LevMarq impl as other OpenCV functions.
Any numbers?
TLDR: new implementation converges more often in less iterations to approximately the same cost function values.
A convergence comparison across various use cases:
Convergence by function
Final energy by function
Iterations elapsed till convergence by function
Other changes in this PR
Submapclass and related stuff (anyway it'll be done using updatedPoseGraphclass)Pull Request Readiness Checklist
See details athttps://github.com/opencv/opencv/wiki/How_to_contribute#making-a-good-pull-request
Patch to opencv_extra has the same branch name.