数值食谱/多维根搜索（使用蝾螈）：如何最小化最大误差
这个问题与《C++ 中的数值食谱》一书相关，因此将保留给对它以及多维优化有一点了解的人。
我正在编写一个需要搜索多维根的程序，为了解决它，我使用多维牛顿根查找方法，即“newt”过程。
对于那些对细节感兴趣的人，我尝试根据一些特征点（两个摄像机看到的特征点）将可变形 3D 模型拟合到对象的立体视图中。
为此，我使用具有以下内容的 newt 过程：
- 11 个输入参数：我的可变形模型可以使用 11 个参数进行建模（由 5 个几何参数和 3D 对象位置的 6 个自由度组成） ：
- 14个输出参数，我需要找到根：基于相机识别的特征点，并给定一组“输入参数”，我可以计算一组之间的距离相机看到的特征点及其理论位置。我有其中 7 个点，所以这给了我 14 个参数（7 个距离乘以 2，因为我计算了两个摄像机上的距离）
我的问题是我的输出参数 (14) 多于输入参数 (11)：每当我调用“newt”，算法总是收敛的，但是它会找到一个解决方案，几乎完美地最小化 11 个第一个输出参数，但在其余 3 个参数上有很多错误。
但是我希望误差能够在输出参数之间统一划分。
我已经尝试过下面描述的方法：
- 尝试将 14 个输出参数组合成 11 个参数（对于 例如，您取一些距离的平均值，而不是使用 两个距离）。然而我对这种方法并不是100%满意，
- 按照以下原则混合几种解决方案：
- 调用 mnewt 并记住找到的根
- 更改14个输出参数的顺序
- 再次调用mnewt并记住找到的root
- 计算找到的两个根的平均值作为解
有谁知道更通用的方法，其中寻根算法会倾向于在输出参数之间均匀划分的误差，而不是倾向于第一个参数？
This question is related to the "numerical recipes in C++" book, so it will be reserved to people knowing a little about it as well as about multidimensional optimization.
I am writing a program that needs to search for a multidimensional root, and in order to solve it, I am using the multidimensional newton root finding method, namely the "newt" procedure.
For those interested in the details, I am trying to fit a deformable 3D model to a steresocopic view of an object, based on a few feature points (feature points which are seen by two cameras).
For this, I am using the newt procedure with the following :
- 11 Input parameters : my deformable model can be modeled with 11 parameters (composed of 5 geometric parameters and 6 deegres of freedom for the 3D object location) :
- 14 Output parameters for which I need to find the root : based on feature points which are identified by the camera, and given a set on "input parameters", I can calculate a set of distances between the feature points seen by the camera and their theoretical location. I have 7 of those points, so that gives me 14 parameters (7 distances times 2, since I calculate the distances on both cameras)
My problem is that I have more output parameters (14) than input parameters (11) : whenever I call "newt", the algorithm always converges, however it will find a solution that minimizes almost perfectly the 11 first output parameters, but that has lots of errors on the 3 remaining parameters.
However I would like the errors to be uniformly divided among the output parameters.
I already tried the approaches described below :
- Try to combine the 14 output parameters into 11 parameter (for
example, you take the average of some distances, instead of using
both distances). However I am not 100% satisfied with this approach - Mix several solutions with the following principle :
- Call mnewt and memorize the found root
- Change the order of the 14 output parameter
- Calling mnewt again and memorize the found root
- Compute a solution is the average of the two found roots
Does anyone know of a more generic approach, in which the root finding algorithm would favor an error that is uniformly divided among the output parameters, instead of favoring the first parameters?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您尝试通过求解
f(x)=0来最小化F(x)，其中x是 m 维向量，f将其映射到一个 n 维向量。如果m <<，则您的优化问题欠定。 n（在您的情况下 11 < 14）。对于此类系统，解决它们的通用方法是最小化
x上的向量范数。您可以通过最小化系统x^TA x + cf(x)^T f(x)相对于x和拉格朗日乘数来实现此目的c。如果没有更多信息，您可以将 A 视为 nxn 单位矩阵。这将找到解决f(x)=0同时具有最小范数的x。有关使用牛顿法执行此操作的更多详细信息，请参阅此论文。
You try to minimize
F(x)by solvingf(x)=0wherexis an m-dimensional vector andfmaps this to an n-dimensional vector. Your optimization problem is underdetermined ifm < n(in your case 11 < 14).For such systems, the generic way to solve them is to minimize a vector norm on
x. You can do this by minimizing the systemx^T A x + c f(x)^T f(x)with respect to bothxand the Lagrange-multiplierc. Without further information, you could take A to be the nxn identity matrix. This will find thexthat solvesf(x)=0while having the smallest norm.For more details on doing this with Newton's method, see e.g. this paper.