Most minutiae-based matching algorithms confront with the challenge of missing and fake minutiae, and especially the non-linear distortion. Many efforts have been made to cope with these problems while relatively slow improvements achieved. In this paper, we proposed a novel minutiae-based matching scheme which introduced a concept of compatibility to the minutiae triangle structures. And based on the compatibility, we further adopted a relaxation process to adjust the similarity matrix of the minutiae triangle cells between the query and template images. To reduce the effect of non-linear distortion evidently, an extended searching step independent of any linear models was proposed. Results obtained on the FVC2004 B1_A show that the proposed algorithm overcomes the influence of missing and fake minutiae, and meanwhile decreases the time cost of matching saliently.