Fast block matching algorithm based on the winner-update strategy

Block matching is a widely used method for stereo vision, visual tracking, and video compression. Many fast algorithms for block matching have been pr oposed in the past, but most of them do not guarantee that the match found is the globally optimal match in a search range. This paper presents a new fast algorithm based on the winner-update strategy which utilizes an ascend ing lower bound list of the matching error to determine the temporary winne r. Two lower bound lists derived by using partial distance and by using Min kowski's inequality are described in this paper. The basic idea of the winn er-update strategy is to avoid, at each search position, the costly computa tion of matching error when there exists a lower bound larger than the glob al minimum matching error. The proposed algorithm can significantly speed u p the computation of the block matching because 1) computational cost of the lower bound we use is less than that of the ma tching error itself; 2) an element in the ascending lower bound list will be calculated only whe n its preceding element has already been smaller than the minimum matching error computed so far; 3) for many search positions, only the first several lower bounds in the li st need to be calculated. Our experiments have shown that, when applying to motion vector estimation for several widely-used test videos. 92% to 98% o f operations can be saved while still guaranteeing the global optimality, M oreover, the proposed algorithm can be easily modified either to meet the l imited time requirement or to provide an ordered list of best candidate mat ches. Our source codes of the proposed algorithm are available at http://sm art.iis.sinica.edu.tw/html/winu.html.