algorithm - 有效检查图像的两个像素是否相连

Question

假设您有一张任意的黑白图像，请考虑以下示例:

...........     ........... 
...........     ........... 
...........     ........... 
.OOO...O...     ........... 
X...O.O.OOY     XOOO...OOOY 
.....O.....     ........... 
...........     ........... 
...........     ........... 
...........     ........... 

其中"."代表黑色像素，"O", "X", "Y"代表白色像素

左图的 X 和 Y 像素沿着 O 的路径相互连接(根据 Moore's neighbourhood ) .而在右边的图片上，X 和 Y 像素断开连接。通过拥有任意黑白图像，我需要高性能算法来回答某组像素是否连接到另一组像素的问题。我很确定这个问题必须有完善的解决方案，因为这个问题看起来很常见，但我似乎找不到适合我的解决方案。顺便说一下，我知道 Flood Fill算法，但目前我没有考虑它，因为它比回答初始问题所需的工作更多。

如果能引用主题方向的任何信息，我将不胜感激，

附言

为了以防万一你有原始问题的答案，也许你可能有以下问题的答案:

...........
...........
...........
.OOO...O...
X...O.O.OOY
.....O.....
..........Z
..........U
..........V

它也很好(但不是必需的)可以用以下形式回答最初的问题:

像素 X 连接到像素 Y,

像素 X 未连接到像素 Z，

像素 X 未连接到像素 U，

像素 X 未连接到像素 V，

提前致谢!

Answer 1

你是对的，这个问题很常见，并且有一个众所周知的高性能算法，它的运行时间与输入的大小成正比:O(n)(因为每个顶点最多有 8 条边).您只需要遍历图像即可创建图形，其中每个像素都是顶点，当 2 个顶点相邻时，边就是边。

然后有了图表，您只需运行 DFS/BFS在你的图表上，从你的 X 顶点开始，如果你到达 Y，或者你的边界没有任何东西，就停止。

请注意，在这里您还可以利用启发式算法，甚至可以使用 A* algorithm (您的启发式是 manhattan distance )。