三维重构中一种快速全局最优算法  

A New and Fast Globally Optimal Method for Triangulation

作　　者：周果清[1] 王庆[1] 

机构地区：[1]西北工业大学计算机学院,陕西西安710072

出　　处：《西北工业大学学报》2010年第1期77-81,共5页Journal of Northwestern Polytechnical University

基　　金：国家自然科学基金(60873085);国家"863"高新技术研究发展计划(2007AA01Z314);"新世纪优秀人才"计划(NCET-06-0882)

摘　　要：在机器视觉中,三维重构是一个重要问题。基于无穷范数表示的误差函数已经证明可以获得全局最优,但是计算速度很慢。基于二范数的最小二乘法速度虽然很快,但因为误差函数是非凸的,所以无法在理论上证明获得的结果是全局最优的,即使是通过二分迭代等方法,往往也只能获得一个局部最优。文中提出一种判定策略,通过对二范数表示的误差函数的Hessian矩阵进行计算,判断最小二乘法获得的局部最优是否是全局最优。因此在三维重构中,可以先用最小二乘法求解,如果误差函数Hessian矩阵为正则结果是全局最优否则调用无穷范数方法重新求解全局最优,这样既保证了精度又加快了计算速度。实验证明该算法是可行的。Aim. The introduction two types of triangulation method. of the full paper points out what we believe to be the shortcomings of the existing So we propose what we believe to be a new triangulation method that is fast and can ensure globally optimal triangulation. Section 1 briefs the error function; in it, eq. （5） describes the error function mathematically. Section 2 explains in some detail our new and fast globally optimal method for triangula tion; its core consists of： （A） eq. （6） gives the Hessian matrix of the error function or eq. （5） ; （B） to verify whether a local minimum solution is globally optimal, trix of the error function. Section 3 gives a five-step it provides a simple and rapid test involving the Hessian maprocedure for implementing our globally optimal algorithm. Section 4 presents two sets of experiment with real data to verify the accuracy and speed of the globally optimal algorithm. The experimental results, given in Figs. 3 through 6 and Tables 1 and 2, and their discussions show preliminarily that our algorithm speed compared with the can obtain the globally optimal solution for triangulation and greatly raise the calculation algorithm based on L∞ norm.

关 键 词：三维重构 全局最优 HESSIAN矩阵 误差函数 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]