Generating matrix/image kernel from List

Question

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?

Answer 1

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.

Answer 2

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