Abstract: Traditional stereo matching algorithms are to find the correspondence between left and right pixels by calculating the degree of similarity between pixels. To improve the matching accuracy, the current strategies for solving the stereo matching problems are often transformed into solving the energy equation minimization problem, and then optimize the global space. These algorithms include scanline optimization algorithm, dynamic programming algorithm, graph cut algorithm and belief propagation algorithm, but each algorithm has its own deficiencies. However, only thought from the original model, it is difficult to change their shortcomings. From the perspective of minimizing the energy equation this paper establishes a new model called the shortest path model. The energy equation will be mapped to a directed graph, and then the stereo matching problem can be solved by solving the shortest path. After describing the principle of the algorithm and steps, this paper shows the algorithm diagram from the angle of disparity space. Experiments show that the shortest path algorithm overcomes many inherent defects of the above four methods, and has higher precision and lower time complexity.

Key words: stereo matching, energy equation minimization, global optimization, disparity space, the shortest path

摘要： 传统的双目立体匹配算法, 是通过计算像素点间的相似程度来找出左图像素点和右图像素点的匹配关系。为了提高匹配准确度, 当前策略主要是将立体匹配转化为求解能量方程最小化问题, 再对全局空间的能量进行优化, 如扫描线算法、动态规划算法、图割算法和置信传播算法。然而各个算法有着自身不足, 若仅仅从原有的模型出发, 难以克服缺点。通过对能量方程最小化问题深入研究, 建立了一个最短路径模型, 即将能量方程映射到有向图中, 通过求解图的最短路径来解能量方程的最小化问题, 详细阐述了算法原理后又从视差空间的角度描述了算法的运行图。实验证明最短路径算法克服了上述四种方法的固有缺陷, 在准确度较高的同时, 有较低的时间复杂度。

关键词: 立体匹配, 能量方程最小化, 全局优化, 视差空间, 最短路径