Stereo matching is a problem that has been studied over several decades in computer vision and many researchers have worked at solving it. The proposed approaches can be broadly classified into feature- and correlation-based approaches [37]. Some important feature based approaches were proposed by Marr and Poggio [107], Grimson [55], Pollard, Mayhem and Frisby [130] (all relaxation based methods), Gimmel'Farb [53] and Baker and Binford [7] and Ohta and Kanade [126] (using dynamic programming).
Successful correlation based approaches were for example proposed by Okutomi and Kanade [127] or Cox et al.[26]. The latter was recently refined by Koch [86] and Falkenhagen [38,39]. It is this last algorithm that will be presented in this section. Another approach based on optical flow was proposed by Proesmans et al. [159].