Image Feature Extraction: Local Binary Patterns with Cython

Introduction

The common goal of feature extraction is to represent the raw data as a reduced set of features that better describe their main features and attributes [1]. This way, we can reduce the dimensionality of the original input and use the new features as an input to train pattern recognition and classification techniques.

Although there are several features that we can extract from a picture, Local Binary Patterns (LBP) is a theoretically simple, yet efficient approach to grayscale and rotation invariant texture classification. They work because the most frequent patterns correspond to primitive microfeatures such as edges, corners, spots, flat regions [2].

In [2], Ojala et al. showed that the discrete occurrence histogram of the uniform patterns is a very powerful texture feature. Image texture is defined as a two-dimensional phenomenon characterized by two properties: (1) spatial structure (pattern) and (2) contrast.

Fig 1. Image used to test the local binary patterns methodology

Methodology

Circularly Symmetric Neighbor Set

A circularly symmetric neighbor set for a given pixel gc is defined by the points with coordinates (i, j) that surround the central point on a circle of radius R, and a number of elements P.

Texture

We define a texture T as the collection of pixels in a gray-scale image

where gp corresponds to the gray value of the p local neighbor.

Interpolation

When a neighbor is not located in the center of a pixel, that neighbor gray value should be calculated by interpolation. Thus, we need to define a function that given a coordinate, returns the interpolated gray value.

Achieving Gray-Scale Invariance

Considering a possible loss of information, it is possible to turn the texture into the joint difference. To calculate it, we subtract the gray value of the central pixel to all of the neighbor set. The joint difference distribution is a highly discriminative texture operator. It records the occurrences of various patterns in the neighborhood of each pixel in a P-dimensional histogram.

where gp is the gray value of the p neighbor. This distribution is invariant against gray-scale shifts.

Local Binary Pattern

LBP_{P,R} operator is by definition invariant against any monotonic transformation of the gray-scale. As long as the order of the gray values stays the same, the output of the LBP_{P,R} operator remains constant.

where

Uniform Local Binary Patterns

In [2], Ojala mentions that in their practical experience LBP is not a good discriminator. They propose just to select the set of local binary patterns such that the number of spatial transitions (bitwise 0/1 changes) does not exceed 2. For example, the pattern ‘1111’ has 0 spatial transitions, the pattern ‘1100’ has 1 spatial transitions and the pattern ‘1101’ has 2 spatial transitions. To each uniform pattern, a unique index is associated. The formula to create the index was borrowed from here.

Now, we can calculate the local binary patterns for a central pixel. The next step is to calculate the local binary patterns for all the pixels.

Hint: For simplicity sake, I am not considering the case where a selected index is negative (i.e. img_gray[-1][0] returns the last pixel of the first column). If we would want to have a more accurate calculation, we should consider this case and treat it.

Cython Code

The previous code is not perfect; however, what makes it really slow is that we iterate through all the image pixels. Waiting 1 minute and 10 seconds to calculate our features is a lot if we take into account that we have also to train a pattern recognition technique. Thus, we need an alternative implementation that must be much faster for loops. In this case, we will use Cython. The code is presented in the next image, it is a big chunk of code. Some parts of it could be improved, but it is already much faster. Please feel free to leave comments if you don’t understand something from the code.

The code is written in such a way that most of it runs entirely in the C API. This strategy speeds up the execution considerably, but also allow us to take advantage of Cython’s parallel module. We will split the job across multiple cores in the CPU.

Using 4 threads, we could calculate the local binary patterns for all the pixels in less than 150 ms. This is so much faster that I won’t even bother to calculate by how many times.

Comparison with a Similar Image

Let’s take another image of bricks, but this one will have a different texture.

Both histograms are very similar, and they should be, in the end both of them are bricks. Nonetheless, features from 20 to 40 are very dissimilar in both images. It means that with a good machine learning algorithm we could correctly classify them.

Conclusion

Local binary patterns are simple but efficient features. The theory behind is not hard to understand and they are easy to code. Nevertheless, if we code them entirely with Python, we will have some performance issues. We tackled the problem with Cython and we got very impressive results. The next step is to collect different texture images and train your favorite machine learning algorithm to classify them.

Jupyter Notebook

https://github.com/ocampor/notebooks/blob/master/notebooks/image/features/local-binary-patterns.ipynb

Bibliography

[1] Marques, O. (2011). Practical image and video processing using MATLAB. John Wiley & Sons.

[2] Ojala, T., Pietikäinen, M., & Mäenpää, T. (2002). Multiresolution gray-scale and rotation invariant texture classification with local binary patterns. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(7), 971–987.