My code for a LocalBinaryPatern in python is running very slow. Any tips?

Question

My code for a LocalBinaryPatern in python is running very slow. I tried optimizing it with tips from online. I'am still getting used to python, and programming in General so any tips are very welcome! Here is the code:

def localbinarypattern(image, radius=2):
    h, w = image.shape
    if radius == 1:
        return 0
    else:
        abase = math.pi/4
        xshift, yshift = [0 for _ in range(8)], [0 for _ in range(8)]

        for i in range(8):
            xshift[i] = - radius * sin(i*abase)
            yshift[i] = radius * cos(i*abase)

        feat = [0 for _ in range(255)]
        lbp = [0 for _ in range(8)]
        base = [1, 2, 4,8, 16, 32, 64, 128]
        for y in (range(radius, (h-radius))):
            for x in (range(radius, (w-radius))):
                lbp = [0 for _ in range(8)]
                for i in range(8):
                    cx = xshift[i]+x
                    cy = yshift[i]+y
                    ry = int(cy+0.5)
                    rx = int(cx + 0.5)

                    if image[ry][rx] > 0:
                        lbp[i] = 1
                
                bits = 0
                for i in range(8):
                    bits += int(lbp[i]*base[i])

                if bits < 255:
                    feat[bits] += 1

        sum_lbp = 0
        for i in range(len(feat)):
            sum_lbp += feat[i]
        if sum_lbp ==0:
            print ("warning: the sum of LBP feature is zero!\n")
        else:
            for i in range(len(feat)):
                feat[i] /= sum_lbp
        return feat

Answer 1

No else after return

You have code like

if x:
    return 0
else:
    ...

Just drop the else, because you previously already returned. Use else branches only if the code converges again after the two branches, not if you exit the function (raise, return or exit()).

Double Initialization

You have code creating two lists:

        xshift, yshift = [0 for _ in range(8)], [0 for _ in range(8)]

        for i in range(8):
            xshift[i] = - radius * sin(i*abase)
            yshift[i] = radius * cos(i*abase)

You can combine those:

xshift = [-radius * sin(i * abase) for i in range(8)]
xshift = [ radius * cos(i * abase) for i in range(8)]

Further Dead Code

• Initialization of h, w at the beginning can be moved down, after checking the radius.
• lbp = [0 for _ in range(8)] -- you're doing that once before the loop and then in every iteration.

C-isms in Loop Iteration

It looks like you're used to writing in C (or a similar language) where you can only access an array by index. It shows e.g. in this code:

sum_lbp = 0
for i in range(len(feat)):
    sum_lbp += feat[i]

In Python, you would write this loop like this instead:

sum_lbp = 0
for value in feat:
    sum_lbp += value

An additional minor improvement specific to this case is to write it in one line:

sum_lbp = sum(feat)

Get familiar with the tools Python gives you at hand, they can make your life easier. In this case it's just the sum() function, but also you're not making use of e.g. dictionaries, which could make this code cleaner.

Redundant Parentheses

Here are two redundant pairs of partheses:

for x in (range(radius, (w-radius))):

Same code without them:

for x in range(radius, w - radius):

Redundant Type Conversions

Looking at int(lbp[i]*base[i]), I wonder why you int() the product. Both only contain integers, as far as I can tell.

Off-by-one Error

This code looks suspicious:

feat = [0 for _ in range(255)]
...
bits = 0
for i in range(8):
    bits += int(lbp[i]*base[i])

if bits < 255:
    feat[bits] += 1

Since an octet can take 256 different values, I'd expect feat to have 256 values as well. That way you could eliminate the bits < 255 check. Another way to simplify this is to reuse the sum() function again. Also, base[i] is 1 << i and lbp[i] is either zero or one, so you can also write this lbp[i] << i eliminating base entirely.

Further Redundant Code

Look at the inner loop:

# init `lbp` with zeroes
lbp = [0 for _ in range(8)]
# actually fill `lbp`
for i in range(8):
    ...
    if image[ry][rx] > 0:
        lbp[i] = 1
# compute values from `lbp`                
bits = 0
for i in range(8):
    bits += int(lbp[i]*base[i])

This uses too many temporaries. Instead, try this approach:

bits = 0
for i in range(8):
    ...
    if image[ry][rx] > 0:
        bits += 1 << i