Abstract: Point Pattern Matching (PPM) is an important and fundamental issue in computer vision and pattern recognition, which is widely used in stereovision, imaging registration, object recognition and tracking, etc. It is a research hot spot in such kind of fields. This paper presents a novel and robust point pattern matching algorithm in which the invariant feature and probabilistic relaxation labelling (PRL) are combined. A new point-set based invariant feature, Relative Shape Context (RSC), is proposed firstly. Using the test statistic of relative shape context descriptor’s matching scores as the foundation of new compatibility coefficients which are used in probabilistic relaxation labelling, the robust support functions are constructed based on the obtained compatibility coefficients. Finally, the correct matching results are achieved by using the relaxed iterations of matching probabilities matrix and imposing the mapping constraints required by the bijective correspondence. Experiments on both synthetic point-sets and real world data show that the proposed algorithm not only has a higher rate of correct matching under similarity or even perspective transformation between point sets, but also is robust to noise and outliers at the same time.