Due to line fragmentation, occlusion and projection of conjoint coplanar space straight lines, there are many “one-to-multiple” and even “multiple-to-multiple” mappings between two features sets in the process of stereo matching, but few reliable methods exist to deal with these cases. In this paper, an algorithm based on feature grouping is proposed to solve these problems. Different from the existing approaches, feature grouping is implemented among the feature set which is composed of linear features extracted from two images, and each feature group contains its associated matching relationships. Therefore, stereo matching becomes equivalent to extracting a set of mutually compatible feature groups from the two images. Two major steps involve in the whole matching process. As much putative feature groups as possible are constructed and their match measures are computed by exploiting some viable geometric and photometric constraints, and then a subset of feature groups is searched so that the sum of the associated match measures is the maximum under the condition that any extracted linear feature at most belongs to only a selected feature group. In order to solve the integer optimization problem, a two-stage method is devised. First, the whole problem is divided into many sub-problems. Second, for each sub-problem, a branch-and-bound method is implemented to find the optimal solution. The proposed algorithm is applied to match straight lines extracted from many pairs of real stereo images, and satisfying experimental results are obtained.