如何尽可能快地将像素与其周围进行比较

Question

我正试图找到一种快速算法，例如：

• 输入：Image (width w x height h)、radius R

• 内容：对于每个像素(x，y(作为

  • x在[R，w-R]
  • y在[R，h-R]中

  在半径为R和圆心(x，y(的圆中找到最具代表性的颜色。(图片中(

• 输出：Image (w-2R x h-2R)根据结果构建的图像

目前，我已经在python中实现了它的基本算法，它的复杂性为O(n*R^2)(带有n = w*h(。

我现在想知道是否存在复杂度为O(n)的算法。对我来说，这听起来是可能的，但我无法建造一个。

因此：

• 你认为可能存在这样的算法吗
  • 如果是，他会使用什么/如何工作
  • 否则，为什么
• 如何加快算法的执行速度(以算法方式，即不考虑并行化(

编辑：

• 我使用一个二维数组的图像表示。每个像素(即数组的单元(是int的元组：红色、绿色、蓝色，介于0和255之间
• 在运行该算法之前；电平"；图像：减少图像中不同颜色的数量(通过对颜色和接近度进行聚类(
• 如果周围的每个像素都不同，那么它应该保持相同的颜色(目前通过对原始像素的颜色赋予更重要的"权重"来实现(

注意：我不确定"将像素与其周围的"像素"进行比较；是描述我想做什么的最佳方式，所以如果你有改进标题的想法，请在评论中告诉我

Answer 1

基于Cris-Luengo的评论，我改进了我的算法：

• 将数据结构的内容从int的元组替换为簇的id
• 使用"；移动内核"：从像素(x，y(到(x+1，y(，只更新离开和进入内核的单元格的内容
  • 随着半径R的增大，这种改进更加明显

因此，输入：image、radius

1. 用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. 构建kernel和delta kernel。德尔塔核包含细胞离开和进入的相对位置，以及它们是否离开或进入

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

   注意：这实际上是合并在一个循环中的，但为了清晰起见，我将步骤分离了

3. 实际算法

   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. 重建图像

   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]]
   

欢迎评论、意见和改进意见：(