用于跟踪二维数组边界的算法

Question

我有一个2D整数数组,表示2D表面上的分组(晶粒).这样的事情: (该图像的每个像素根据其所属的组分配一个整数,因此每个红色像素分配1,例如,每个蓝色为2)

给定两个这样的分组之间的边界上的X,Y坐标(用户点击那里)如何在这两个分组之间追踪边界,保存沿着边界的每个像素坐标并得到两个端点坐标(我不是关注没有端点但没有端点的机箱的情况)

我提出的任何算法似乎都很难实现,我无法想象之前没有人这样做过.有帮助吗？优选地是c#中的解决方案,但是非常感谢关于算法的任何提示.

编辑:

我本来应该说我要实现一个算法来像这样向量化该行:

1. 两个端点之间定义一条线
2. 得到距离当前线最远的边界点,如果它比d更远,则此时分割线,所以有两个线段
3. 重复直到没有边界点比线条上的d更远

我认为这很容易实现,这就是为什么我没有陈述它.为了达到目的,我只需要解决当前的问题......

关于问题:

原始数据是如何格式化的？- 它很简单short[,] labeling;,大小约为250x150,如下所示:

11111112222
11111222222
11112222222
11112222222 <- user clicks on leftmost 2 or rightmost 1 -> I want to trace that border
11111122222                                                down to the first
11111133322                                                encountered 3 and up to the
11333333333                                                frame-border

什么是端点？ - 正如我一直在考虑全局解决方案,我可以将端点描述为:2x2区域,其中4个像素由color1,color2和至少三分之一的不同颜色组成.

什么是连续的连接？ - 这对算法的其余部分并不重要,见下文

那些y形区域呢？ - 我不关心它们,你可以假设边框后面的color1区域至少有2个像素宽,这就是为什么如果我们谈论4或8个邻域也没关系.

我现在有什么？ - 起初我尝试了一种"行走"算法,就像mvds发布的那样,但发现我在所有4个方向上进行踩踏,邻居计算和检查,这很乏味,看起来很糟糕.我没有找到一个很好的表示"这是最后一步来自的方向,不要检查邻域的像素".

然后我放弃了行走算法并尝试了一种全局方法(如过滤器):对于每个像素检查它是否为color1并且在其4邻域中具有color2.有了这个,我得到了color1和color2之间的所有边界.我打算通过某种类型的填充删除所有与用户点击坐标无关的边界,但后来我遇到了问题:端点在哪里？

我仍然感谢更多的投入.现在我将看到我可以用mvds的算法走多远.

Answer 1

我假设您已经确定了有问题的 2 种颜色，例如“mvds”所描述的，作为预处理步骤。

我认为您会发现使用坐标系很有帮助，其中每个 (x,y) 代表的不是一个像素，而是 4 个像素接触的点。然后你可以编写一个函数来确定北是否是边界像素边界，同样对于南、东、西（或者也许你更喜欢术语上/下/左/右）。

从边界上的一点开始，例如扫描 4x4 邻域以查找以 N/S/E/W 之一作为边界的点。沿着这个边界到达下一个点，然后扫描除了你进来的方向之外的所有 4 个方向，寻找下一个像素边界。重复此操作，直到用完像素边界。然后您就知道您已到达一个端点。

返回起点，沿着与最初方向不同的方向追踪边界，直到到达另一个端点。

这将为您提供所有像素边框。每个像素边框的一侧为颜色 1，另一侧为颜色 2。

（我原以为矢量化会比识别边界困难得多，但这不是你的问题主要涉及的，对吧？为此，我将从端点开始并遵循像素边界的序列逐条边界，在每个点检查从终点到当前点的直线是否与像素边界匹配。如果不匹配，则表示一行结束，然后开始新一行。）