Sparse and dense matching algorithms give different results on narrow and wide baseline stereo pairs.
Sparse matching algorithms are used to establish a set of robust matches between an image pair. These sparse matches may then be used to compute the epipolar geometry, using techniques such as the RANSAC (random sampling) method. Two sparse matching algorithms were developed, one based on the KLT tracking algorithm, and another based on computing correlation scores for a region of potential matches. The former is fast and accurate, and is best suited to narrow baseline image pairs where the images comprising the image pair are sequential images of a digitised video sequence. The latter is better suited to images separated by a larger baseline.
Dense matching algorithms are used to find matches for all points in the images. The search for a match is constrained by the epipolar geometry derived from the set of sparse matches. Two dense matching algorithms were developed. The first assumes that an approximate solution for a match is known, and it is well suited to narrow baseline images. The second algorithm is suited to wider baseline images, and is based on computing the match score along the corresponding epipolar line. It can make use of both standard matching metrics, as well as non-parametric transforms. The dense matching algorithm has been incorporated into an overall framework for matching, in which points are matched in order of most ``interesting'' to least interesting, match probabilities are updated depending on their neighbours, and a number of constraints are used to remove incorrect matches. In addition, the algorithm allows for the results obtained from a number of match window sizes are combined into a single result. The algorithm returns a disparity map, as well as an image of match ``flags'' indicating whether or not each point was successfully matched, and if not, the reason why matching was not successful.
The figure below shows a pair of images from the Bornholm sequence, the
results of sparse matching and epipolar geometry computed from these sparse
matches, and the dense disparity map.