1057-7149 (c) 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TIP.2017.2681421, IEEE
Transactions on Image Processing
FEDOROV AND BALLESTER: AFFINE NON-LOCAL MEANS IMAGE DENOISING 3
Fig. 2. Affine covariant neighborhoods (patches) computed at corresponding
points in two images taken from different viewpoints. Despite the change in
appearance, patches capture the same visual information.
Fig. 3. An affine invariant patch comparison which is achieved by normalizing
the patches to discs and aligning them with suitable rotations.
When the tensor is affine covariant, we have that
AB
u
A
(x, r) = B
u
(Ax, r). This means that the tensors can
be used to define affine covariant regions which transform
appropriately via an affinity. We will refer to these regions as
shape-adaptive or elliptical patches to distinguish them from
the square patches of fixed size. Fig. 2 illustrates the patches
defined by the affine covariant tensors of [13], computed for
a set of corresponding points in two images related by a
homography. Note that even though the transformation is not
an affinity, the patches still match, since a homography can be
locally approximated by an affinity.
Affine covariant tensors at two corresponding locations
allow us to extract the affine distortion between corresponding
elliptical patches, up to a rotation, as shown in [13]. Indeed, for
any affine transformation A, there exists an orthogonal matrix
R such that
A = T
u
(Ax)
−
1
2
RT
u
A
(x)
1
2
. (5)
This last equation provides an intuitive geometric relationship
between the tensors, the associated elliptical patches and the
affinity. Consider a point x and the corresponding affine
covariant elliptical patch B
u
A
(x). Mapping B
u
A
(x) by the
affinity yields B
u
(Ax). The application of A can be decom-
posed in three steps. First, applying T
u
A
(x)
1
2
, we transform
B
u
A
(x) into a disc or radius r . We refer to the resulting
patch as a normalized patch. Then, a rotation is applied to
the normalized patch. Finally, T
u
(Ax)
−
1
2
maps the rotated
normalized patch to the elliptical patch B
u
(Ax).
To fully determine the affinity A, one needs to find the
rotation R. Any rotation would yield an affinity that maps the
elliptical patch associated to T
u
A
at x to the one associated
to T
u
at Ax. For a wrong value of the rotation, the image
content inside both patches will not match. Therefore, the
right value for the rotation can be computed by aligning the
image content of both patches. For this aim, we decompose the
rotation as R = R
u
(Ax)R
−1
u
A
(x), where R
u
(Ax) and R
u
A
(x)
are estimated from the image content inside the patches.
In practice, we calculate them by aligning the dominant
orientation of the normalized patches to the horizontal axis.
To compute the dominant orientation we use histograms of
gradient orientations as in the SIFT descriptors [22].
C. Computation of Affine Covariant Tensors
In this work, we use the particular dense field of affine co-
variant tensors and associated neighborhoods proposed in [13],
which are computed from the following iterative algorithm:
T
(k)
u
(x) =
R
B
(k−1)
u
(x,r)
Du(y) ⊗ Du(y) dy
Area(B
(k−1)
u
(x, r))
, (6)
where u is the given image and B
(k)
u
is the elliptical patch
related to T
(k)
u
, defined by
B
(k)
u
(x, r) = {y : hT
(k)
u
(x)(y − x), (y − x)i ≤ r
2
} (7)
for k ≥ 1, and
B
(0)
u
(x, r) = {y : |Du(x)
T
(y − x)| ≤ r} (8)
for k = 0. To simplify notation in the following, let us
denote by T
u
(x) the affine covariant structure tensor T
(k)
u
(x)
for a fixed value of k (in our experiments k = 30, as
in [13]) and a fixed value of r (notice that r > 0 is a free
parameter). Similarly, we denote by B
u
(x) the affine covariant
neighborhood B
(k)
u
(x, r).
D. An Affine Invariant Patch Similarity
We are interested in comparing patches of an image. Let us
generalize and consider the problem of comparing the patches
around two points x, y defined in images u and v, respectively.
We begin with an intuition behind the proposed similarity
measure. The patches are defined by the local metric given
by the tensors T
u
(x) and T
v
(y). In order to compare both
patches, equation (5) suggests the following mapping between
them:
C(x, y) = T
v
(y)
−
1
2
R
v
(y)R
−1
u
(x)T
u
(x)
1
2
. (9)
We can interpret C(x, y) as an affinity, mapping the elliptical
patch associated to T
u
(x) into the one associated to T
v
(y).
If u in the vicinity of x is an affinely transformed version
of v in the vicinity of y, then C(x, y) recovers the true
affinity. Intuitively, an affine invariant patch similarity could
be computed as the distance between the elliptical patch at y
and the result of applying C(x, y) to the patch at x. In practice,
it is more suitable to transform both elliptical patches to discs
of radius r (as depicted in Fig. 3) and to compare the aligned
normalized patches:
D
a
(t, x, y) =
Z
∆
t
g
t
(h)
u(x + T
−
1
2
u
R
u
(x)h) − v(y + T
−
1
2
v
R
v
(y)h)
2
dh,
(10)
where ∆
t
denotes a disc centered at the origin with radius
proportional to t > 0 (the so-called scale) and big enough
such that the weighting function g
t
has effective support in
∆
t
. D
a
is a multiscale affine invariant patch distance which
intrinsically extends the set of available patches.