How to compare a pixel with its surounding as fast as possible?

user_12102246 0
Viewed 145

I am trying to find a fast algorithm such as :

  • input: Image (width w x height h), radius R

  • content: for each pixel (x,y) as

    • x in [R, w-R]
    • y in [R, h-R]

    find the most represented color in the circle of radius R and center (x,y). (In the image)

  • output: Image (w-2R x h-2R) the image built from the results

I have, for now, implemented the base algorithm of that in python, that has a complexity O(n*R^2) (with n = w*h).

I'm now wondering if an algorithm of complexity O(n) may exist. It sounds possible to me, but I cannot manage to build one.

So:

  • Do you think a such algorithm may exist ?
    • If so, what would he use / how would he work ?
    • Otherwise, why ?
  • How can I speed up the execution of my algorithm ? (in an algorithm way, i.e. regardless of parallelization)

Edits:

  • I use an image representation with a 2 dimensions array. Each pixel (i.e. cell of the array) is a tuple of ints: Red, Green, Blue, between 0 and 255.
  • Before running this algorithm, I "level" the image: reduce the number of different colors present in the image (by a kind of clustering on color and proximity)
  • If every pixel is different in the surrounding, then it should remain with the same color (for now implemented by giving a "weight" more important to the original pixel's color)

Note: I am not sure that "comparing a pixel with its surrounding" is the best way to describe what I want to do, so if you have ideas to improve the title, let me know in the comments

image-processing image algorithm python
1 Answers

Based on Cris Luengo comments, I improved my algorithm by:

  • Replacing data structure's content from tuples of int to ids of clusters
  • Using a "moving kernel": from pixel (x,y) to (x+1, y), only updating the content about the cells leaving and entering the kernel
    • This improvement is more visible as the radius R grows

So, input: image, radius

  1. Replace colors by ids

    colors = {}
id_counter = 0
raw = np.zeros((image.width, image.height))
data = image.load()
for x in range(image.width):
    for y in range(image.height):
        color = data[x,y]
        id = colors.get(color, -1)
        if id == -1:
            id = id_counter
            id_counter += 1
            colors[color] = id
        raw[x,y] = id

  2. Build kernel and delta kernel. Delta kernel contains the relative positions of cells leaving and entering, and if they are leaving or entering

    kernel = []
for dx in range(-radius, radius+1):
    for dy in range(-radius, radius+1):
        if dx*dx + dy*dy <= radius*radius:
            kernel.append((dx,dy))

delta_kernel = []
for dx in range(-radius, radius+1):
    mini = None
    for dy in range(-radius, radius+1):
        if dx*dx + dy*dy <= radius*radius:
            mini = dy - 1
            break
    delta_kernel.append((dx, mini, -1))

for dx in range(-radius, radius+1):
    maxi = -9999
    for dy in range(-radius, radius+1):
        if dx*dx + dy*dy <= radius*radius:
            maxi = max(dy, maxi)
    delta_kernel .append((dx, maxi, 1))

    Note: this is actually merged in one loop, but for sake of clarity, I separated the steps

  3. Actual algorithm

    counter = {} # Map counting occurrences
new_raw = np.zeros((raw.shape[0] - radius*2, raw.shape[1] - radius*2))

direction = +1 # Y direction +/-1
y = radius
for x in range(radius, raw.shape[0]-radius):
    if x == radius: # First time: full kernel
        for (dx, dy) in kernel:
            key = raw[x+dx, y+dy]
            counter[key] = counter.get(key, 0) + 1
    else: # move to the right (x++): delta kernel horizontally
        for (dy, dx, sign) in delta_kernel:
            key = raw[x + dx, y + direction*dy]
            new_val = counter.get(key,0) + sign
            if new_val <= 0:
                counter.pop(key) # Remove key to useless key values in the map
            else:
                counter[key] = new_val

    for i in range(raw.shape[1]-2*radius):
        if i > 0:
            # y moves forward: delta radius (on y=0, x moved forward not y)
            for (dx, dy, sign) in delta_kernel:
                key = raw[x + dx, y + direction*dy]
                new_val = counter.get(key,0) + sign
                if new_val <= 0:
                    counter.pop(key)
                else:
                    counter[key] = new_val

        # Find most represented value
        winner_item = max(counter.items(), key=lambda i:i[1])
        if winner_item[1] == 1: # Every pixels are different: take the center one by default.
            winner_key = raw[x,y]
        else:
            winner_key = winner_item[0]
        new_raw[x-radius, y-radius] = winner_key
        y += direction
    y -= direction # Prevent y to go out from range

    direction *= -1

  4. Rebuild an image

    reversed_color_map = {}
for key, value in colors.items():
    reversed_color_map[value] = key

result = Image.new(mode=image.mode, size=(image.width-2*radius, image.height-2*radius))
out_data = result.load()
for x in range(raw.shape[0]):
    for y in range(raw.shape[1]):
        out_data[x,y] = reversed_color_map[raw[x,y]]

Comments, remarks, ideas for improvement are welcome :)

user_121022460
Related