To confirm the efficiency of our model estimation algorithm we 
have compared it with another possible overlap detection 
scheme which is based on sample consensus technique. Having 
two overlapping images and a set of putative matches, we apply 
sample consensus to estimate the shift-and-rotation model. We 
have chosen PROSAC among other sample consensus methods 
due to its high convergence speed, ability to cope with high 
outlier’s level and suitability to our task: provided putative 
matches, it is possible to sort them using Euclidean distance 
between descriptors as a quality function. 
We conducted our experiments on both synthetic and real data. 
Their detailed description is given below. 
Applying the described procedure, two tests have been made, 
both using N = 1000 matches with k = 200 most reliable of 
them employed for angle detection. The two experiments differ 
in the level of noise added to inliers: the first test was held with 
the maximum deviation of 4 pixels, while 8 pixels were used in 
the second one. The threshold for PROSAC was set according 
to this noise level parameter. For both methods, after inlier 
detection, the model was refined using the least-squares fitting. 
If the relative error between the found model (X,Y,0) and the 
true one (X,Y,0) was less than 4%, i.e. 
5.2 
there are too many matches, thus it is reasonable to select only 
the first k matches, which are the most reliable ones, for this 
process. 
In 
we 
ov< 
dif 
dig 
vai 
fiel 
do 
pei 
anj 
To 
ma 
5.1 Synthetic tests 
The synthetic test consists of a number of trials (we used 1000), 
with the full process of image pair matching being modeled at 
each trial. First, we randomly choose shift and rotation angle for 
the pre-selected percentage of image overlap, thus defining the 
correct transformation. A number of points are placed in the 
overlap area of the first image and transferred to the second 
image. This forms the correct matches (inliers), which are then 
perturbed by noise. After that, false matches (outliers) are 
added, being placed randomly within the images. The number 
of inliers and outliers is chosen in such a way that the 
percentage of inliers is equal to the percentage of overlap area 
and the total number of matches equals the desired value N . 
The important aspect that must be considered in synthetic tests 
is the need of match ordering for PROSAC method. We take 
this into account by using the following procedure. The correct 
matches are assigned random descriptor distances according to 
the distribution provided in (Labe et al., 2006). We modeled it 
with the Rayleigh distribution with o = 1 and scaled by a factor 
of 10000. The incorrect matches are assigned uniformly 
distributed distances from the [10 5 ,3 • 10 6 ] interval. The used 
values for descriptors distances are characteristic for the SIFT 
(Lowe, 2004) descriptor that we use for the real data (see 
Section 5.2). As it was already mentioned in the previous 
section, match ordering can also be employed by the proposed 
method to save computational resources. At the stage of angle 
estimation the number of combinations can become huge if 
X - X 
V ( 
W 
Y-Y 
\ 2 
V " y 
' - 0 - ;zj - n 
\ 2 
2n 
< 0.04, 
then the match was considered successful. Here W and H are 
image width and height respectively. The results for varying 
overlap percentage are shown in Figure 4. 
Due to the least-squares refinement of the final result, the 
choice of bin size and smoothing parameter for the proposed 
method does not affect the result in a wide range of values. 
Thus we used 5% of parameter range ([0,2;r] for angle and 
[-W,W]x[-tf,//] for shift) for the Gaussian filter width, 
while the bin size was equal to 1 degree for angle and to 1% of 
image dimensions in pixels for shift. 
As graphs indicate, the PROSAC method performs quite well in 
both cases if overlap area is not less than 15% of an image size. 
But with the decrease of overlap percentage the performance 
deteriorates quickly, especially in case of stronger noise. In fact, 
this does not necessarily mean that PROSAC is unable to find 
inliers. More often it means that the found model differs too 
much from the real one. PROSAC tends to select a small subset 
of inliers, while the proposed method either does not find them 
at all (quite rarely) or finds almost all of them. This allows our 
method to tolerate greater noise and to achieve much better 
precision. Also, as it was said before, it does not require the 
noise threshold to be set at all. 
100 
C3 
B 
>» 
80 
60 
40 
20 
0 
Noise level 4 pixels 
_g_ l - -Ja- 
“V 
-â- 
-û 
/ 
/ 
A 
—B— Our method 
-A - PROSAC 
5 10 15 20 25 30 
Overlap, % 
(a) 
Noise level 8 pixels 
(b) 
Figure 4. The comparative results of our algorithm and PROSAC on synthetic data. Note that the proposed method is more reliable 
in case of low overlap (less than 15%) 
19 
uni 
a PI 
nei 
dis 
(Li 
ne: 
Fi 
16