Efficient Suboptimal Solutions to the Optimal Triangulation
Efficient Suboptimal Solutions to the Optimal Triangulation
复制标题
DOI：
10.1007/s11263-010-0378-y
复制
发表时间：
2010
影响因子：
19.5
通讯作者：
Fuchao Wu;Qiong Zhang;Zhanyi Hu
中科院分区：
文献类型：
--
作者：
Fuchao Wu;Qiong Zhang;Zhanyi Hu
给定两幅图像，测量对应点对的最优三角剖分是基本求出6次多项式的真实的根。由于对于每个点对，都应该进行这种求根过程，因此整个图像的最佳三角剖分是计算密集型的。本文通过基本矩阵的三维锥表示（称为基本锥），结合拉格朗日乘子法，将最优三角剖分问题重新表述。在此基础上，将测量点对的最优三角剖分问题转化为在联合图像空间中寻找基锥上距离测量点最近的点，提出了3种严格满足两幅图像对极约束的次优算法。在我们的第一个次优算法中，用生成锥上离测量点最近的点作为最优解的逼近，即求出一个4次多项式的真实的根;在我们的第二个次优算法中，生成线上与测量点最近的点被用作最优解的近似，也就是求一个二次多项式的真实的根。最后，在我们的第三次最优算法中，Sampson逼近序列的收敛点被用作最优解的近似。模拟数据和真实的图像的实验表明，我们提出的3个次优算法可以达到与原来的最佳三角剖分相比，估计精度，但计算量少得多。例如，我们的第二个和第三个次优算法只需要原始最优解的1/5运行时间。此外，在我们的新公式下，不是针对每个测量点对重新计算两个欧几里得变换矩阵，而是针对所有图像点对使用固定的欧几里得变换矩阵，除了其数学优雅性和计算效率之外，其还能够去除所得多项式的次数对第一图像或第二图像中的极线束的参数化的依赖性，这是原始最优三角测量中的一个缺点。
Given two images, the optimal triangulation of a measured corresponding point pair is to basically find out the real roots of a 6-degree polynomial. Since for each point pair, this root finding process should be done, the optimal triangulation for the whole image is computationally intensive. In this work, via the 3D cone expression of fundamental matrix, called the fundamental cone, together with the Lagrange’s multiplier method, the optimal triangulation problem is reformulated. Under this new formulation, the optimal triangulation for a measured point pair is converted to finding out the closest point on the fundamental cone to the measured point in the joint image space, then 3 efficient suboptimal algorithms, each of them can satisfy strictly the epipolar constraint of the two images, are proposed. In our first suboptimal algorithm, the closest point on the generating cone to the measured point is used as the approximation of the optimal solution, which is to find out the real roots of a 4-degree polynomial; in our second suboptimal algorithm, the closest point on the generating line to the measured point is used as the approximation of the optimal solution, which is to find out the real roots of a 2-degree polynomial. Finally, in our third suboptimal algorithm, the converging point of the Sampson approximation sequence is used as the approximation of the optimal solution. Experiments with simulated data as well as real images show that our proposed 3 suboptimal algorithms can achieve comparable estimation accuracy compared with the original optimal triangulation, but with much less computational load. For example, our second and third suboptimal algorithms take only about a 1/5 runtime of the original optimal solution. Besides, under our new formulation, rather than recompute the two Euclidian transformation matrices for each measured point pair, a fixed Euclidian transformation matrix is used for all image point pairs, which, in addition to its mathematical elegance and computational efficiency, is able to remove the dependency of the resulting polynomial’s degree on the parameterization of the epipolar pencil in either the first image or in the second image, a drawback in the original optimal triangulation.