Graphics Reference
In-Depth Information
where
x
i
is a grey value of the input image and
y
i
∈{−
+
}
is a pixel of the tem-
plate. It is assumed that the black and white areas in the template have an equal num-
ber of pixels, i.e.
i
=
1
y
i
=
1
,
1
0. With a total area of
n
pixels, this simplifies (
1.72
)
to
i
=
1
x
i
y
i
c
=
.
(1.73)
[
i
=
1
x
i
n
(
i
=
1
x
i
)
2
1
−
]
n
This leads to the following optimisation: The pixel sums
i
=
1
x
i
y
i
,
i
=
1
x
i
, and
i
=
1
x
i
are computed using integral images. In an integral image each pixel con-
tains the grey value sum of the top left subimage including the pixel itself. The
respective sum is computed by reading the value of four corner pixels of the area,
which results in a computationally efficient implementation in terms of memory
accesses per pixel. The runtime of this algorithm is independent of the size of the
corner template. This allows for improvements in terms of detection robustness and
subpixel accuracy. As soon as the integral images are computed, the recomputation
of the correlation coefficient takes very little time. One could try different mask
sizes and select one or integrate the results of all of them.
Candidate Filter and Graph Construction
The corner candidates in the correla-
tion coefficient image are obtained by a straightforward non-maximum suppression
followed by false-positive removal. The non-maximum suppression is performed by
counting the number of pixels with a lower absolute value than the centre pixel in
the eight-neighbourhood. If the count exceeds a threshold (default: 6) and the centre
value exceeds another threshold (default: 0
.
75), the pixel is assumed to be a cor-
ner candidate. This simple non-maximum suppression provides a robust detection
with a reasonable amount of false positives. The false positives are the neighbour-
ing pixels of the true positive. Deciding which of the pixels is the true positive is
done during the position estimation at subpixel accuracy. As soon as this position
is available, the same data are used to determine the interpolated cross-correlation
value. The candidate with the larger cross-correlation value is assumed to be the true
positive.
Two algorithms for computing the subpixel position are investigated: Weighted
mean (WM) and bivariate quadratic interpolation (BVI). The subpixel position of
WM is the average of the eight-neighbourhood positions weighted by the corre-
sponding correlation coefficients. The interpolated value is the mean of the cor-
relation coefficients involved. The subpixel position of BVI is the location of the
extremum of the bivariate quadratic function, assuming it is appropriately shaped
and does not form a saddle point. The interpolated cross-correlation value is the
function value at the extremum. This procedure yields the set
V
in (
1.69
). The cor-
responding set
E
is constructed by finding the nearest neighbour
t
of each vertex
s
in the respective direction
d
. The correlation coefficients of
v
s
and
v
t
must be of
opposite sign.
Non-bidirectional Edge Elimination
This procedure consists of deleting all
graph edges
e
=
(s,t,d)
subject to
(t, s,
opposite
(d)) /
∈
E
(cf. Fig.
1.7
b). The func-
Search WWH ::
Custom Search