查找相邻像素 [Python]

Question

请耐心等待，因为这是我长期（未注册）该网站的用户后的第一个 post。

我有一个图像文件，其中感兴趣的图像中有特定区域。通过单独测试每个 pixel/cell 并确定它是否感兴趣 - 将感兴趣的区域附加到新列表来识别这些区域。

所以我有一个表格列表：

[[22,25], [22,29], [23,24], ...]

其中包含我所有特殊像素的索引，如果我要将这些图像绘制为黑色图像上的白色图像，那么在宏观尺度上；我基本上会有两个连续的白色团块。我想将此列表排序到另一个嵌套列表中，其中它们按连续性分组。也就是说，所有与白色块相关联的像素都将组合在一个嵌套列表中

我的想法是只抓取第一个点 (fpoint)，然后通过测试 x 和 y 索引来测试与该点相关的所有其他点 (pts)，看看这两个点的差异是否不是x 和 y 都大于 1。所以每个测试都是这样的：

if ( (np.absolute(fpoint[0] - pts[0]) <= 1) and (np.absolute(fpoint[1] - pts[1]) <= 1) ):
     #add this point to the same nested list as my fpoint
     #remove this point from the initial list and continue to chisel down the original list until it is all sorted into my new list

鉴于这种方法一次通过我可能会得到最多 8 个相邻点，我需要跟踪这些点以单独测试它们中的每一个，因为我已将它们从我的旧列表中删除。

所以到最后我希望有这样的东西：

groupedList = [[[22,23], [21,24], [20,24], ...], [[102, 51], [102, 50], [100, 55]...]]

在一维情况下重申：

假设我有一个列表：

[1, 22, 5, 20, 3, 4, 21, 2]

在我的函数结束时，我希望有一个类似于以下的列表：

[ [1, 5, 3, 4, 2], [22, 20, 21] ]

因为作为一个集合，1、5、3、4 和 2 与 22、20 和 21 一样 'contiguous'。我不关心数字的顺序，只要分开就可以了。

关于递归代码的一些事情听起来像是解决我的问题的优雅解决方案，但我就是无法生成它。感谢您的时间，希思 M.

解决方案

认可Anders Munch

根据安德斯·蒙克给我的东西，我能够达到令人满意的这一点！

def candidate_neighbors(node):
    return ((node[0]-1, node[1]-1), (node[0]-1, node[1]), (node[0]-1, node[1]+1), (node[0], node[1]-1), 
            (node[0], node[1]+1), (node[0]+1, node[1]-1), (node[0]+1, node[1]), (node[0]+1, node[1]+1))

def neighboring_groups(nodes):
    remain = set(nodes)
    while len(remain) > 0:
        visit = [remain.pop()]
        group = []
        while len(visit) > 0:
            node = visit.pop()
            group.append(node)
            for nb in candidate_neighbors(node):
                if nb in remain:
                    remain.remove(nb)
                    visit.append(nb)
        yield tuple(group)

nodes = ((22, 23), (22, 24), (21, 23), (1, 5), (2, 6), (21, 22), (3, 5))

print(tuple(neighboring_groups(nodes)))

(((1, 5), (2, 6), (3, 5)), ((22, 24), (22, 23), (21, 22), (21, 23)))

Answer 1

您的初始方法的一个问题是它 O(n²)。您建议将每个点与每个其他点进行比较，这会很快变慢。您需要一种更快的方法来找到给定点的邻居，在 Python 中更快通常意味着使用 dict，或者在这种情况下它的近亲 set.

这可以看作是一个图论问题：您有一组节点（点）最多连接到 8 个相邻节点。在图论术语中，如果我没记错的话，任务是找到这个图的连通子图。该算法非常简单：通过选择任意节点开始子图，然后继续访问子图中已有节点的邻居，直到不再有邻居为止。然后你从下一个子图重新开始。

长话短说，这里是一维案例的代码：

def candidate_neighbors(node):
    return [node-1, node+1]

def neighboring_groups(nodes):
    remain = set(nodes)
    while len(remain) > 0:
        visit = [remain.pop()]
        group = []
        while len(visit) > 0:
            node = visit.pop()
            group.append(node)
            for nb in candidate_neighbors(node):
                if nb in remain:
                    remain.remove(nb)
                    visit.append(nb)
        yield group

nodes = [1, 22, 5, 20, 3, 4, 21, 2]
print(list(neighboring_groups(nodes)))

二维情况只是将 candidate_neighbors 函数替换为产生像素位置的 8 个候选邻域的函数。您将需要使用一种略有不同的点表示法，一种可散列且可以放入 set 中的点。但这很简单，只需使用 2 元素元组而不是 2 元素列表。

查找相邻像素 [Python]

Finding Neighboring Pixels [Python]

python

sorting

pixel

cell

contiguous

解决方案