📚Local Binary Pattern Algorithm: The Math Behind It❗️

This post goes in-depth analysis and application of LBP (Local Binary Patterns) for image feature extraction.

LBP

👉 Introduction

The main idea behind LBP is to describe the neighborhood of image elements using binary codes. This method is usually used to study their local properties and identify the characteristics of individual parts of the image.

This algorithm is a combination of statistical and structural methods. It was first proposed by T. Ojala, M. Pietikanen, T. Mehpaa from Oulu University in Finland in 1994. It is considered a theoretically time-effective and straightforward method, showing excellent results in many studies.

👉 How it works❓

As the name suggests, Local Binary Pattern (LBP for short) is a feature of the local representation of an image. It is composed of relative values ​​by comparing each pixel with its neighboring pixels.

The main characteristics of LBP are:

1-Low calculation cost

2-Resistance to fluctuations in image gray scale values

A lot of improvements have been made since the first proposal in 1994. Especially in non-deep learning systems, it is widely used for facial image recognition, texture segmentation, and other image analysis applications.

The LBP detects microstructures such as edges, lines, spots, flat areas, which can be estimated by the histogram.

*LBP method steps*

image by the author

1- Convert the image into grayscale space.

2- For each pixel(gp) in the image, select the P neighborhoods that surround the central pixel. the coordinates of gp are given by

(gc_x-Rsin(2πp/P),gc_y + Rcos(2πp/P))

3- Take the center pixel (gc) and set it as a threshold for its P neighbors.

4- Set to 1 if the value of the adjacent pixel is greater than or equal to the value of the center pixel, 0 otherwise.

5- Now compute the LBP value: Sequentially counterclockwise, write a binary number consisting of digits adjacent to the center pixel. This binary number (or its decimal equivalent) is called LBP-central pixel code and, further, is used as a characteristic selected local texture.

Uniform LBP formula

gc- the intensity value of the central pixel

gp- the intensity of the neighboring pixel with index p

the function S can be expressed as:

threshold (step) function

P- number of sampling points on a circle of radius R(circular neighborhood).

P- controls the quantization of the method.

R- determines the spatial resolution of the method or operator.

The gray values of neighbors which do not fall exactly in the center of a pixel(block) are estimated by interpolation.

*Detailed example*

Now let’s take, for instance, the following chunk of a grayscale image:

image by the author

you can express the size of this window(3x3) in terms of The radius of the circle which equals (2*R + 1), if the radius is 1, then we get a 3x3 matrix.

The coordinates of the central pixel denoted by gc(gc_x,gc_y) are (1,1) according to the coordinated axis of the matrix(3x3). The value of this pixel is 33(center) gc =33. Let’s take for our example 8 neighbor samples (P=8). The coordinates of each sample point can be expressed as

(gc_x-Rsin(2πp/P),gc_y + Rcos(2πp/P))

P = 8

p = 0, 1 ,2 …,P-1

gc_x = gc_y = 1

So for the previous matrix, we have the following coordinates for each sample:

(gp_x,gp_y)
(g0_x,g0_y) => (1.0, 2.0)
(g1_x,g1_y) =>(0.2929, 1.7071)
.
.
.
(g7_x,g7_y) =>(1.7071, 1.7071)

image by the author

Lets denote by Theta_i = 2πp/P => Theta=

0
pi/4
pi/2
3pi/4
pi
pi+pi/4
3pi/2
7pi/4

Now we need to compare, as the formula suggests, the intensity of each neighbor pixel with the intensity of the central one, gc.

g0 = 80
g1 = ?(on the circle at angle pi/4)
g2 = 41
g3 = ?
g4 = 29
g5 = ?
g6 = 56
g7 = ?
g0 = 80 > gc = 33 ==> put 1
g2 = 41 > gc = 33 ==> put 1
g4 = 29 < gc = 33 ==> put 0
g6 = 56 > gc = 33 ==> put 1

image by the author

Now the problem is to find the intensity values of g1, g3, g5, g7

In order to find these values, the paper suggests applying an interpolation.

Since we have a 2d space(2-dimensional image), so we need a 2d interpolation method.

Now one of the methods that I do remember from my education in numerical analysis is the bilinear interpolation.

*bilinear interpolation*

The term Interpolation is a way to calculate the intermediate value of a function from several of its already known values.

Bilinear interpolation is a linear interpolation of the function of two variables, that is, four-point interpolation. If the values ​​of the function at these points are known f(x1,y1),f(x2,y1),f(x1,y2),f(x2,y2)

It is reasonable to assume that the value at some point (x, y) located in the square bounded by these points can be found by interpolating twice, first by the x coordinate for two pairs of points, and then by the y coordinate, using the previous result.

In order to compute the intensity of g1, g3, g5, g7, we need to find the coordinates of the outer box containing the unknown pixel value.

So for example, g1, which lies in between theta = 0 and theta = pi/2, the figure would look like the following:

image by the author

The pixel value of g1 can be interpolated using the formulas:

Back to our example:

[[25 41 24]
[29 33 80]
[38 56 65]]
q11 = gc = 33
q21 = 80
q22 = 24
q12 = 41

We can translate the coordinated system to the origin => this will imply that

x1=y1=0(origin point)

x2=y2=1(one pixel away from the center in both axis)

x and y values of the unknown point need to be translated into the regular coordinated system(90 degrees counterclockwise rotation, which means new_x = old_y and new_y = - old_x )

applying this formula on the unknown samples we can find :

g1 = 39 (this seems to be logically true, because it lies inside the boundries 33 , 80, 24, 41)
g3 = 29
g5 = 39
g7 = 63

Now the threshold matrix is equal to:

image by the author

now applying the LBP formulas

LBP = (2⁰)*1 + (2¹)*1 + (2²)*1 +(2³)*0 +(2⁴)*0 +(2⁵)*1 +(2⁶)*1+ (2⁷)*1 = 1 + 2 + 4 + 32 + 64 + 128 = 231

image by the author

This process will repeat for each block of the image (along x and y axes)

⚠️ Note that the size of the image is reduced by a factor of 2*R lines and 2*R columns like in our example we have a 9x9 image would result in a 7x7 image (R=1 for this example)

In order to find if a pixel needs an interpolation or not, we can compute the fractional part of gpx and gpy, if the fractional part for both x and y is zero(like g0, g2, g4, g6) then, the pixel lies perfectly in the center of the block, otherwise we need to do an interpolation(g1, g3, g5, g7). For this example we have 4 pixels needs to perform the bilinear interpolation, and the other four points don’t need it since the value of this pixel is already given by the matrix.

*Pseudo-code*

TO implement this method in python for the purpose of the visualization of the LBP, you are required 3 for loops :

For i in height range:
     For j in width range:
          Select a chunck of the image to compute its LBP value
          For each block neighbors:
              check if interpolation is needed
              Compute_LBP(bock)
              Add the result
          Update the matrix with the value of LBP

For python implementation, you can check out my code on GitHub, under Visualize_LBP class.

*Vectorization*

Vectorization is the core of the internal implementation of NumPy. Vectorization is the absence of an explicit loop in code development. The loops themselves cannot be avoided, but their internal implementation is replaced with other constructs in the code.

The vectorization application makes the code more capacious and readable. Thanks to vectorization, many operations take a more mathematical form. For example, NumPy allows you to express the multiplication or addition of two matrices like this:

C = A*B
C = np.add(A, B, casting="unsafe")
#if A and B have two different types(like int16,float32), use casting="unsafe"

Now we can write our program using only one for loop to cycle through the neighbors' samples

code on Github

This code groups all the neighbors of the image together for each iteration of the For loop. the following illustration will clarify the mechanism of this algorithm.

I have translated this code from the original one written in Matlab(source)

Vectorized LBP

👉 Conclusion

Experimental studies have shown that the application of LBP can significantly reduce time and computing costs for feature extraction(which will be discussed in future work).

If you find this post useful, feel free to share it, and follow me to tune in for my future posts.

Finally, You can check out the code on my repo.

Moral: “If you don't know enough, you may be beaten by the ignorant!”

Peace ✋