Reduce running time in Texture analysis using GLCM [Python]
Question: I am working on 6641x2720 image to generate its feature images (Haralick
features like contrast, second moment etc) using a moving GLCM(Grey level Co-
occurrence matrix ) window. But it takes forever to run. **The code works
fine, as I have tested it on smaller images.** But, I need to make it run
faster. Reducing the dimensions to 25% (1661x680) it takes **30 minutes** to
run. How can I make it run faster ? Here's the code:

    
    
    from skimage.feature import greycomatrix, greycoprops
    import matplotlib.pyplot as plt
    import numpy as np
    from PIL import Image
    import time
    start_time = time.time()
    img = Image.open('/home/student/python/test50.jpg').convert('L')
    y=np.asarray(img, dtype=np.uint8)
    #plt.imshow(y, cmap = plt.get_cmap('gray'), vmin = 0, vmax = 255)
    contrast = np.zeros((y.shape[0], y.shape[1]), dtype = float)
    
    for i in range(0,y.shape[0]):
        for j in range(0,y.shape[1]):
            if i < 2 or i > (y.shape[0]-3) or j < 2 or j > (y.shape[1]-3):
                continue
            else:
                s = y[(i-2):(i+3), (j-2):(j+3)]
                glcm = greycomatrix(s, [1], [0],  symmetric = True, normed = True )
                contrast[i,j] = greycoprops(glcm, 'contrast')
    print("--- %s seconds ---" % (time.time() - start_time))
    plt.imshow(contrast, cmap = plt.get_cmap('gray'), vmin = 0, vmax = 255)
    


Answer: Fill a GLCM is a linear operation: you just go through all the pixels on your
image/window and you fill the matching matrix case. Your issue is that you
perform the operation for each pixel, and not just for an image. So in your
case, if the image dimensions are Width x Height and the window dimensions are
NxN, then the total complexity is Width x Height x (NxN + FeaturesComplexity),
which is really bad.

There is a much faster solution, but it's trickier to implement. The goal is
to reduce the matrix filling operations. The idea is to work row by row with a
Forward Front and a Backward Front (principle already use to get fast
mathematical morphology operators, see [here](https://hal.archives-
ouvertes.fr/hal-00692897/document) and
[here](https://www.lrde.epita.fr/~theo/papers/geraud.2010.book.pdf)). When you
fill the matrix for two consecutive pixels, you reuse most of the pixels, in
fact only the ones on the left and right are different, so the backward front
and forward front respectively.

Here is an illustration for a GLCM window of dimensions 3x3:

> x1 x2 x3 x4
>
> x5 p1 p2 x6
>
> x7 x8 x9 x10

When the window is centered on p1, you use the pixels: x1, x2, x3, x5, p2, x7,
x8, x9. When the window is centered on p2, you use the pixels: x2, x3, 4, p1,
x6, x8, x9, x10. So for p1, you use x1, x5 and x7, but you don't use them for
p2, but all the other pixels are the same.

The idea of the algorithm is to compute the matrix normally for p1, but when
you move to p2, you remove the backward front (x1, x2, x5) and you add the
forward front (x4, x6, x10). This reduces dramatically the computation time
(linear instead of quadratic for mathematical morphology operations). Here is
the algorithm:

  1. For each row:
  2. \----- Fill the matrix (as usually) for the first pixel in the row and you compute the features
  3. \----- For each of the following pixels
  4. \----- ----- Add the forward front (new pixels in the window)
  5. \----- ----- Remove the backward front (pixels no longer in the window)
  6. \----- ----- Compute the features

