Chapter 8 Introduction to Texture

Description, Segmentation and Classification:

CHAPTER8.MCD

Feature Extraction & Image Processing in Computer Vision

M. S. Nixon and A. S. Aguado

Academic Press, 3rd Edition 2012

This worksheet is more illustrative than a proper worksheet. We shall start with distance measures.

Let's say we have two points:

The Euclidean distance is the distance between the two points:

The Manhattan distance is the city block measure

This is bigger since it takes longer to walk round the sides of a rectangle, rather than straight across it.

As we are not usually working in a 2-dimensional plane, our points are vectors

The Euclidean distance is then

This changes little as it is dominated by the first two components. If we change the last component in the second vector, the distance will now change a lot.

The Manhattan distance over vectors is then

If our vectors are actually samples of points which form a cluster, we can store the co-ordinates of the points in a matrix. Say we have five samples of vector1 then we will store each sample as a row in a matrix

And we have another set of samples, from a different cluster,

One way to measure the distance is as the average Euclidean distance. This is averaged over the number of samples of the vectors

And we obtain

We can formulate this using matrices. First of all we obtain the difference between the matrices

Then we form the differences by multiplying the matrix by its transpose (also called squaring the matrix)

The squared matrix shows the difference between the same vectors along the diagonal, and between different vectors in the off-diagonal

So the (average) squared Euclidean distance is the sum of the diagonal elements (called the trace of the matrix) divided by the number of elements

So the Euclidean distance is

So let's join all the operations together

and see it work

This is the same as before (with slight numeric error)

A confusion matrix shows the difference between the samples

Let now consider more sets of samples

So our averaged distance of the first set of samples from these sets of samples is

So the confusion matrix is now

This gives a nice clear picture of the differences between the sets of samples. The leading diagonal is zero, reflecting the match between each set of samples and itself. The off diagonal elements are greater than zero, indicating that the sets of samples are different.

There are actually several problems here: the numbers might not be in the same range, or start from the same place. In mat4 the second column has 20 added to it, whereas in mat5 the second column is much more random and with a bigger range. To handle where they start from, we can subtract the mean so that they all start from zero. To handle the spread, we can divide by the variance. This is the Mahalanobis distance metric.

First, we need to be able to subtract the means of the measurements. The means of these are then a vector

So when we apply this to our measures

Then we will need to be able to subtract these means from each of the measures

The covariance is a measure of how each measurement varies with another. Since we have samples of four measurements, we end up with a 4x4 covariance matrix

One theoretical property of this matrix is that it is positive definite. We chan check this by the eigenvalues, but a simpler test is that Cholesky decomposition will operate successfully.

So this is fine (if it wasn't, the Cholesky procedure would not work). We will need to invert it, so we should also check that the inverse function is correct.

So there is some imprecision here. Overall, our covariance matrix has the required properties and is invertible.

To determine the Mahalanobis distance between these sets of samples, we need to form the difference between them as

The covariance matrix is the average of the two covariance matrices

The Mahalanobis distance scales the difference by the covariance as

So let us invoke it

and since we are interested in the trace (as for the earlier Euclidean matrix formulation)

so our Mahalanobis distance is then

So, let's join them all together

Let's see the confusion associated with using the Mahalanobis metric

The difference from the Euclidean distance can best be observed by viewing these matrices as images. Rotate the surfaceplots to see the structure too.

This shows that mat4 is considerably different from the others. The range of the numbers is much greater, as is the spacing. In practice, it's a much better measure.

If the covariance matrix is the unity matrix (the elements are zero except for the leading diagonal which are 1.0), the Mahalanobis distance reverts to the matrix version of the Euclidean distance

Ok, we now have different ways of measuring distance. The complexity of the Mahalanoibis distance is well worth it as it explores the structure of the data more deeply.Note that the formulation here is largely contingent on how the data is stored.

Now we shall move to the k-nearest neighbour classifier.

We shall use Euclidean distance

And the code is

Let's do some example test data of 3 and of two classes, 3 samples of each class

Let's do some test points

Let's check it for k=1

And let's check for k=3

More practical code would assign the class as the 1-nearest neighbour when all class items differ for k=3.

Here's the code for the basic Local Binary Patterns operator

Let's read in an image

And the histogram is

The basic LBP is shift invariant. Let's test it

This looks pretty similar

Let's check

These differences are very small!

Here's the co-occurrence matrix generation

So, let's see it go

Then we can derive some image measures as