基于minmaxKKT条件的三维重构方法

机器视觉中, 三维重构是一个重要问题. 基于2范数的最小二乘法速度较快, 但因误差代价函数非凸, 理论上无法获得全局最优解, 即使通过分支限界等方法, 往往也只能获得局部最优. 无穷范数表示的误差代价函数理论上可以获得全局最优, 但是计算速度很慢. 本文提出一种基于最小最大库恩塔克条件(minmaxKKT)的三维重构方法. 该方法利用minmaxKKT条件对基于2范数的三维重构结果进行全局最优判别, 对陷入局部最优的结果运用混合最速下降法进行全局寻优. 该方法可以获得全局最优, 相对于无穷范数算法具有更高的计算效率. 对标准数据集和真实数据的实验结果证明了本文算法的可行性和优点.

A Triangulation Method Based on minmaxKKT

Triangulation is one of important issues in machine vision. Although L₂ norm based least square method is reasonably fast, the globally optimal solution cannot be obtained theoretically due to its non-convexity of the objective function. Even if some optimization strategies, such as branch and bound, are adopted, the result is locally optimal in most cases. In theoretical,L_∞ norm based approach can produce global optimal solution, however, its computational cost increases rapidly according to the size of measurement data. In this paper, we proposed a minmaxKKT based triangulation method. The minmaxKTT condition is first utilized to verify whether the solution by L₂ norm is globally optimal. If the decision is negative, we apply hybrid steepest decent algorithm to pursuit global optimum. The proposed method can not only achieve global optimum but also raise the computational speed greatly compared to L_∞ based approach. Experimental results on benchmark data and real world scene have proven the feasibility and merit of the proposed method.