Abstract: Stereo matching algorithm based on dynamic programming (DP) can meet
real-time constraints even on low-cost hardware. Therefore, it can be used in Robot obstacle
avoidancing system. But the performance of conventional DP has not been satisfactory and
scattered mismatching points occur when the stereo matching is applied. To solve these problems,
the method of initial cost getting and path traversal and backtracking is improved. The energy
aggregation method is proposed which can use the information of object boundary to determine
the disparity changing regions. A highly accurate initial disparity map is obtained, which can make
the subsequent phases of parallax getting get a good performance. In the path traversal and
backtracking phase, the idea of multi-path backtracking to exploit the information gained from DP
more effectively is also introduced. More reliable pixels to reduce the occurrence of mismatch can
be retained. The experiment shows that this method has a high matching accuracy and a fast
speed.

Key words: stereo matching, dynamic programming, parallax region segmentation;
multi-path backtracking