如何尽快比较一个像素与其周围的像素？

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) 的算法。对我来说这听起来可能，但我无法构建一个。

所以：

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

编辑:

我使用带有二维数组的图像表示。每个像素（即数组的单元格）都是一个整数元组：红色、绿色、蓝色，介于 0 和 255 之间。
在运行这个算法之前，我“调平”图像：减少图像中存在的不同颜色的数量（通过一种聚类颜色和接近度）
如果周围的每个像素都不同，那么它应该保持相同的颜色（现在通过赋予原始像素颜色更重要的“权重”来实现）

注意：我不确定“将像素与其周围环境进行比较”是描述我想做的事情的最佳方式，所以如果您有改进标题的想法，请告诉我在评论中

Answer 1

根据 Cris Luengo 的评论，我改进了我的算法：

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

所以，输入：image、radius

用 id 替换颜色

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

构建 kernel 和 delta kernel。 Delta 内核包含细胞离开和进入的相对位置，以及它们是离开还是进入

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

注意：这个其实合并在一个循环里，但是为了清楚起见，我把步骤分开了

实际算法

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

重建图像

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

欢迎提出意见、评论和改进想法:)

如何尽快比较一个像素与其周围的像素？

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

python

algorithm

image

image-processing