7
\$\begingroup\$

I have another question from same program where is full code, but this question focus only single process/function of that program.

My problem is performance when creating dynamic Image kernel from list of pixels.

List contains multiple single 4 byte Integer which is grayscale of pixel.

I have tried 3 different approach, still not happy with the time what it takes.

I think my basic idea about generating matrices is wrong.

Approach 1

def getKernels(self, pixels, width):
    kernels = []
    pixels = [x for sublist in pixels for x in sublist] #2D list to 1D 
    for i in range(0,len(pixels)):
        x = (i % width) #Calc pixel x-cordinate
        y = math.floor(i / width) #Calc y-cordinate
        try:
            kernel = [pixels[(x-1)+((y-1)*width)],pixels[(x)+((y-1)*width)],pixels[(x+1)+((y-1)*width)],pixels[(x-1)+(y*width)],pixels[(x)+(y*width)],pixels[(x+1)+(y*width)],pixels[(x-1)+((y+1)*width)],pixels[(x)+((y+1)*width)],pixels[(x+1)+((y+1)*width)]]
        except Exception as e:
            kernel = [0] #Cannot create fullsize kernel so just make it black
        kernels.append(kernel) #Add kernel to kernels list
    return kernels

Function execute time 0.2249772548675537 seconds
With this project I can live with that time, but kernel generation is ugly and "hardcoded" so I cant change size of it.

Approach 2

    def getKernels(self, pixels, width):
        kernels = []
        pixels = [x for sublist in pixels for x in sublist]  #2D list to 1D
        for i in range(0,len(pixels)):
            tx = (i % width) #Calc pixel x-cordinate
            ty = math.floor(i / width) #Calc y-cordinate
            kernel = []
            for y, x in self.kernelGenerator(ty,tx,3): #Pass current pixel index cordinates and size of kernel
                try:
                    index = (x)+((y)*width) #Calc index 
                    if index > -1 and index < len(pixels):  #Check that index is in list bounds
                        kernel.append(pixels[index])
                    else: #Out of list bounds make pixel black
                        kernel.append(0)
                except Exception as e:
                    raise e
            kernels.append(kernel)
        return kernels

    def kernelGenerator(self, x, y, size):
        if size % 2 == 0 or size < 3: #Because pixel has to be "center" of my kernel
            print("Kernel size should be odd and greater than 2")
            raise
        kernel = []
        for i in range(math.ceil(-size/2),math.ceil(size/2)):
            for j in range(math.ceil(-size/2),math.ceil(size/2)):
                kernel.append((x+i,y+j))
        return kernel

Function execute time 1.236647605895996 seconds
Ok, now I can change my kernel size but costs time.

Approach 3

    def getKernels(self, pixels):
        kernels = []
        for ty, row in enumerate(pixels): #get pixel Y-cordinate and row
            for tx, px in enumerate(row): #get pixel X-cordinate and px
                kernel = []
                for y, x in self.kernelGenerator(ty,tx,3):
                    try:
                        kernel.append(pixels[y][x])
                    except Exception as e:
                        kernel.append(0)
                kernels.append(kernel)
        return kernels

    def kernelGenerator(self, x, y, size):
        if size % 2 == 0 or size < 3: #Because pixel has to be "center" of my kernel
            print("Kernel size should be odd and greater than 2")
            raise
        kernel = []
        for i in range(math.ceil(-size/2),math.ceil(size/2)):
            for j in range(math.ceil(-size/2),math.ceil(size/2)):
                kernel.append((x+i,y+j))
        return kernel

Function execute time 0.8910479545593262 seconds
Approach 3 is now best. Comments got me thinking this again, still execute time is IMO too much.

Any suggestions to improve it?

\$\endgroup\$
  • \$\begingroup\$ If I understand correctly, pixels is a list of rows, right? \$\endgroup\$ – Mathias Ettinger Nov 24 '16 at 8:04
  • \$\begingroup\$ Yes, in two dimensional list. Then I convert it into one dimensional list. pixels as passed to function [[px,px...][px,px...]] -> converted to one dimensional [px,px,px,px] \$\endgroup\$ – Evus Nov 24 '16 at 8:17
  • \$\begingroup\$ And width is the length of each row, then? \$\endgroup\$ – Mathias Ettinger Nov 24 '16 at 8:18
  • 1
    \$\begingroup\$ Exactly. Now that i think about it, width variable is useless because i could get it from list. \$\endgroup\$ – Evus Nov 24 '16 at 8:19
  • \$\begingroup\$ Added third approach based on @MathiasEttinger comments. Sometimes I overthink these things. Still not happy with results. \$\endgroup\$ – Evus Nov 24 '16 at 8:40
4
\$\begingroup\$

Style

  • put spaces after comas to improve readability;
  • remove unnecessary parenthesis;
  • put spaces around operators;
  • put two spaces before and one space after the comment sign (#);
  • remove the 0 in range(0, <whatever>) as it is the default value;
  • except Exception as e is bad here as you are only actually expecting IndexError; plus the as e part is unnecessary as you don't use e (well, you do in the second snippet, but you could just raise with nothing more, even though the whole except: raise is useless as it adds nothing over the default behaviour);
  • range(len(<something>)) is often a red flag as it is better to iterate over elements than indices; but here, I don't think you have a choice anyway;
  • divmod can help you get rid of math.ceil.

In fact, only changing your first snippet to using divmod yield a 5% speedup on my machine:

def get_kernel(pixels, width):
    kernels = []
    pixels = [x for row in pixels for x in row]  # 2D list to 1D 
    for i in range(len(pixels)):
        y, x = divmod(i, width)
        try:
            kernel = [
                    pixels[(y-1) * width + x - 1], pixels[(y-1) * width + x], pixels[(y-1) * width + x + 1],
                    pixels[y * width + x - 1], pixels[y * width + x], pixels[y * width + x + 1],
                    pixels[(y+1) * width + x - 1], pixels[(y+1) * width + x], pixels[(y+1) * width + x + 1],
            ]
        except IndexError:
            kernel = [0]
        kernels.append(kernel)  # Add kernel to kernels list
    return kernels

Algorithm

There is one thing that bothers you about this snippet: it is not generic enough to allow for kernels of various radius. There is an other thing that bothers me, it is how it warps around the edges of the image but the bottom. The fact that some_list[-x] will return the \$x^{th}\$ element of some_list starting from the end combined to the flattening of the list will make it so that when at the top row or when reaching a pixel at the right or the left of the image, the coordinates involved will always be a valid index in pixels. But for the last row, (y+1) * width + x will exceed the number of elements in pixels and raise IndexError. This inconsistent behaviour bothers me.

Looking at how you handle your kernels in your other question, we can see that kernels that are not full-sized are discarded. Great, let's generate kernels of lower size for the edges of the image. The key idea here is knowing that slicing a list will always return a list:

>>> a = list(range(20))
>>> a[4:8]
[4, 5, 6, 7]
>>> a[18:50]
[18, 19]
>>> a[-8:5]
[]

Also, slicing a list of lists will not copy inner list but only references to them, so it is rather fast:

def get_kernels(pixels, width, radius=1):
    kernels = []
    for y in range(len(pixels)):
        y_min = y - radius
        y_max = y + radius + 1
        for x in range(width):
            x_min = x - radius
            x_max = x + radius + 1
            kernels.append([
                    pixel for row in pixels[y_min:y_max]
                    for pixel in row[x_min:x_max]])
    return kernels

This version is 5 to 10% slower than your first one but has two advantages:

  1. It is more readable;
  2. It is more generic.

I chose to parametrize it with the kernel radius rather than its diameter to avoid the parity check and simplify the computations.

I also chose to keep the width parameter since you seemed to already have it handy. But if you want to remove it, you can still add:

def get_kernels(pixels, radius=1):
    if not pixels:
        return []
    width = len(pixels[0])

at the beginning of the function.

Going further

Your use case of such function seems only to be able to iterate over the returned value. In such case, you would gain more performances by turning this into a generator instead of building a list element by element.

The code is nearly identical, just remove the kernels list and use the yield keyword instead of the append function. And voilà. What it does is that it will compute the kernels on demand, during the iteration; removing the need for extra storage (and handling of that storage):

def get_kernels(pixels, radius=1):
    if not pixels:
        return

    width = len(pixels[0])
    for y in range(len(pixels)):
        y_min = y - radius
        y_max = y + radius + 1
        for x in range(width):
            x_min = x - radius
            x_max = x + radius + 1
            yield [
                pixel for row in pixels[y_min:y_max]
                for pixel in row[x_min:x_max]]

Oh yes, you might have noticed that I removed the self parameter as it is unused. This might interfere with the fact that you are using this as a method on your class. But I probably should explain what is wrong with that in that other question of yours.

\$\endgroup\$
  • \$\begingroup\$ But I probably should explain what is wrong with that in that other question of yours. It's good to hear constructive feedback, but I am little bit of scared now \$\endgroup\$ – Evus Nov 25 '16 at 3:27
  • \$\begingroup\$ This is type of answer what I was looking for. Thank you for style comments and pointing out my aberration on algorithm. I am beginner with Python and dont have a clue with generators, start looking into them now. Your last codes yield has parenthesis at the end, which will cause syntax error. Also should there be extra linebreak after return? I dont know how I can time generator but on my machine, last algorithm code function execution time with same sample is ~0.19, so better than my first approach. \$\endgroup\$ – Evus Nov 25 '16 at 3:48
  • 1
    \$\begingroup\$ @Evus You can't time a generator since no code is executed until you iterate over it. You can still time list(get_kernels()) to get an approximation. But since the point is to not build a list in the first place using generators, that's not ideal. You can use cProfile on the whole algorithm to know how much time you spent in each function though. \$\endgroup\$ – Mathias Ettinger Nov 25 '16 at 7:12
2
\$\begingroup\$

You can simplify and speed up kernel generation by 2 things:

1. Using itertools

2 converting it to generator

So your kernel_generator should look like this:

import math
from itertools import combinations_with_replacement

def kernel_generator(self, x, y, size):
    if size % 2 == 0 or size < 3:  # Because pixel has to be "center" of my kernel
        print("Kernel size should be odd and greater than 2")
        raise

    _range = range(math.ceil(-size / 2), math.ceil(size / 2))
    for i, j in combinations_with_replacement(_range, 2):
        yield x+i, y+j

Please note that python functions/methods are using underscore as naming separtor. Please read PEP8

\$\endgroup\$
  • \$\begingroup\$ Execution time is ~0.527s. I think it is still little high or am I wrong? Maybe i'm asking too much from python? Also thank you @Alex for correcting naming and noted PEP8. \$\endgroup\$ – Evus Nov 24 '16 at 16:20
  • \$\begingroup\$ @Evus which time you need? what is your goal? Also can I have a sample you test against so I can do benchmarks while improving the code? \$\endgroup\$ – Alex Nov 24 '16 at 16:24
  • \$\begingroup\$ well closer to approach 1 so about ~0.2. Sample list length is 67838. I linked another question, you can get full code and sample image from there. Function execute time is timed only getKernels()-function, not from whole program. \$\endgroup\$ – Evus Nov 24 '16 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.