In this paper, the authors propose a refined Branch-and-Bound algorithm for affine-transformation based image registration. Given two feature point-sets in two images respectively, the authors first extract a sequence of high-probability matched point-pairs by considering well-defined features. Each resultant point-pair can be regarded as a constraint in the search space of Branch-and-Bound algorithm guiding the search process. The authors carry out Branch-and-Bound search with the constraint of a pair-point selected by using Monte Carlo sampling according to the match measures of point-pairs. If such one cannot lead to correct result, additional candidate is chosen to start another search. High-probability matched point-pairs usually results in fewer loops and the search process is accelerated greatly. Experimental results verify the high efficiency and robustness of the authors approach.