Exercise 1: Praktikum Machine Learning

Exercises in Praktikum Machine Learning
0. General information
• The goal of this exercise sheet is to implement in MATLAB the extraction of standard
features at each pixel from a given image.
• The functions that are computing a feature vector
x(i, j) =
x1(i, j),..., xNf eatures(i, j)]
must return a cell array X of size 1×Nf eatures. X {k} is an image such that [X {k}] (i, j) is
the value of the feature xk at the location (i, j).
• The features you are computing must be extracted from a grayscale image of your choice.
The value of a given feature over the image can be displayed using the function imagesc.
• The size a of patches or kernels must always be an odd number a = 2ρ+1. The centre of
the patch/kernel is then clearly defined as the pixel (ρ+1,ρ+1).
• Some questions are asked to be solved using a cross-correlation product, generally between
an image I of size nrows ×ncols and a kernel K of size a×a with a = 2ρ+1. As a reminder,
the cross-correlation product ? between I and K is the image of size nrows ×ncols defined as
[I ?K] (i, j) = ∑
−ρ≤α,β≤ρ
I(i+α, j +β)K(α,β)
Up to a symmetry applied to the kernel, it is equivalent to a convolution product ∗, defined
as
[I ∗K] (i, j) = ∑
−ρ≤α,β≤ρ
I(i−α, j −β)K(α,β)
We recommend to perform cross-correlation products using the syntax
imfilter(I,K,’replicate’,’same’)
which automatically pads the image I on the boundaries.
– 2 –
1. Bank of filters
This section is dedicated to the extraction of features that can be seen as filters over the image. The
value of such a feature xk(i, j) is a linear combination of the intensities within the neighbourhood
of (i, j). More formally, we can write
xk(i, j) = ∑
−ρ≤α,β≤ρ
I(i+α, j +β)K(α,β)
where K, called the cross-correlation kernel, defines the coefficients of this linear combination.
a) Implement a function standard_filters.m taking as parameters:
• the image I
• a cell array F of strings
• the side a of the square used as kernel (used for ‘mean’ and ‘std’)
• a standard deviation σ (used for ‘gaussian’ and ‘LoG’)
that returns the cell array X giving the feature responses for the filters specified in the cell
array F . The user must be able to choose one or several strings among the following:
• ‘straight derivatives’ : gives the derivative along rows and columns at each pixel. As
an example, the derivation along rows can be defined as:
∂I
∂i
(i, j) = 1
2
(I(i+1, j)−I(i−1, j))
• ‘diagonal derivatives’ : gives the derivative along the two diagonals at each pixel.
• ‘mean’ : gives the mean of intensities over the patch of size a.
• ‘std’ : gives the standard deviation of intensities over the patch of size a. Consider
applying the mean filter to the squared image.
• ‘gaussian’ : Gaussian kernel of standard deviation σ. You can choose 6σ + 1 as the
size of the patch.
• ‘LoG’ : Laplacian-of-Gaussian kernel of standard deviation σ. You can choose 6σ+1
as the size of the patch.
• ‘all’ : returns all the previous filters for the given a and σ.
Some predefined kernels can be found using fspecial. The cell array X contains at most 8
components (if ’all’ is selected).
2. Features based on integral images
Integral images are an elegant and fast way to compute the sum (or the mean) of intensities over a
rectangle. This section is dedicated to the computation of features based on this principle.
a) From an image I of size n× p, we can define the integral image ˜I of size (n+1)×(p+1)
by
˜I(i,1) = 0 for i ∈ {1,...,n+1}
˜I(1, j) = 0 for j ∈ {1,..., p+1}
˜I(i, j) = ∑
i
0<i
j
0<j
I(i
0
, j
0
) for i 1 and j 1
– 3 –
Implement a function integral_image.m taking as input parameter an image I and returning
its integral image ˜I. You can use for this the following identity (valid for i 1 and j 1)
˜I(i, j) = I(i−1, j −1) + ˜I(i−1, j) + ˜I(i, j −1)− ˜I(i−1, j −1)
b) Implement a function mean_patch.m taking as input arguments
• an integral image ˜I
• the side of a patch a
• the coordinates (α,β) of this patch
that returns the mean of intensities of I over the patch of side a centered on (α,β). For this,
you can notice that, in the configuration of the Figure 1, the sum of intensities of I over the
gray rectangle is given by
∑
x1≤x≤x2
y1≤y≤y2
I(y, x) = ˜I(y2 +1, x2 +1)− ˜I(y2 +1, x1)− ˜I(y1, x2 +1) + ˜I(y1, x1)
Figure 1: The integral image ˜I allows a very fast computation of the sum over the gray rectangle
of the intensities of I
c) We take a patch of side a centered on the pixel (i, j) of interest and we consider its 8 neighbouring patches as described in Figure 2. By using mean_patch.m and a loop over the patch
indexes, implement a function mean_features.m taking as input arguments
• an integral image ˜I
• the side of the patches a
that returns the feature vector
x(i, j) = [µ1(i, j),µ2(i, j),...,µ9(i, j)]
as a cell array X of size 1×9 where µn(i, j) is the average of the intensities over the patch
Pn(i, j).
d) With a similar approach, implement a function lbp.m (for Local Binary Patterns) taking as
input arguments
• an integral image ˜I
• the side of the patches a
– 4 –
that extracts the binary feature vector
x(i, j) = [x1(i, j),..., x4(i, j), x6(i, j),..., x9(i, j)]
as a cell array X of size 1 × 8, where xn(i, j) = 1 if µn(i, j) ≥ µ5(i, j) and xn(i, j) = 0 if
µn(i, j) < µ5(i, j).
e) We propose to compute now the same kind of features but on longer range.
(i) Implement a function long_range_offset.m taking as input arguments
• an integral image ˜I
• a side of patches a
• an offset vector w = [u, v]
that returns the feature vector x(i, j) = [x1(i, j), x2(i, j)] as a cell array X of size 1×2
where:
• x1(i, j) = µw(i, j) − µ5(i, j), where µw(i, j) is the mean over the patch of side a
centered on the pixel (i+u, j +v)
• x2(i, j) is the binarised version of x1(i, j): if x1(i, j) ≥ 0 then x2(i, j) = 1, else
x2(i, j) = 0
(ii) Implement a similar function long_range_two_offsets.m taking as input arguments
• an integral image ˜I
• a side of patches a
• a first offset vector w1 = [u1, v1]
• a second offset vector w2 = [u2, v2]
that returns the difference between the means of the patches centered on (i+u1, j+v1)
and on (i + u2, j + v2), and its binary version. Again, the output is a cell array X of
size 1×2.
Figure 2: A patch of size a = 3 centered on the pixel (i, j) of interest and its 8 neighbouring
patches