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

CodePudding user response：

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 :)