如何使用一组点对图像进行分割，并将每个像素分配给最近的点？

Question

我尝试实现一种使用种子点分割图像的方法，并将每个像素分配给最近的点。

例如，如果像素靠近1，则设置为1。

输入：

0 0 0 0 0 3 0
0 1 0 0 0 0 0
0 0 0 0 2 0 0
0 0 0 0 0 0 0

输出：

1 1 1 3 3 3 3
1 1 1 2 2 3 3
1 1 1 2 2 2 2
1 1 1 2 2 2 2

目前的方法需要计算 (宽度 * 高度 * 点数) 次，花费时间太长了，有什么算法可以更快吗？

---

处理 5 9478 * 1868 张图像，点数为 8，需要 7 秒的时间。

            for (int i = 0; i < height; i++)
            {
                for (int j = 0; j < width; j++)
                {
                    byte index = 0;
                    double distance = double.MaxValue;
                    for (int m = 0; m < elements.Count; m++)
                    {
                        CircleROI circle = roiResized[m];
                        double currentDistance = Math.Abs(i - circle.Center.Y) +
                            Math.Abs(j - circle.Center.X);
                        if (currentDistance < distance)
                        {
                            distance = currentDistance;
                            index = (byte)m;
                        }
                    }

                    *data++ = index;
                }
            }

- Lamp

---

我们要处理多少个“numPoints”？如果数量很小，我认为任何数据结构的开销都会比“numPoints”因素更糟糕。也许如果您发布您的代码，我们可以找到其他可能的优化方法。 - MrSmith42

@MrSmith42 我不同意。如果numPoints接近于与width * height成比例，那么width * height * numPoints就表示二次时间。而使用高效数据结构的线性时间方法可以轻松地快得多。 - Stef

@Stef：这正是我的问题，如果numPoints非常小（或者受到“小”值的限制），例如队列的开销可能会产生比numPoints因素更大的开销。如果它是无界的或与宽度或高度相似，那么您的答案将更快，因为它是O（width * height）而不是O（width * height * numPoints）。 - MrSmith42

我希望你不是在计算平方根来计算和比较距离。（那将会非常昂贵且无用） - MrSmith42

@MrSmith42，numPoints 很小，目前没有开方的 power 需要 9 秒，简单的加法只需要 7 秒。 - Lamp

我建议尝试使用性能分析来确定访问 circle.Center.Y、circle.Center.X 或 Math.Abs(..) 是否会花费大量时间。distance 可以是整数（性能分析可以告诉我们这是否有任何影响）。 - MrSmith42

Answer 1

您可以使您的程序按像素数量的比例工作。

维护一个正在“处理”的像素队列。

初始化这个队列，使其包含最初非零的所有像素。

然后在队列非空时循环执行以下操作:

• 从队列中弹出一个像素(x, y);
• 将(x, y)的每个零相邻像素涂上与(x, y)相同的颜色;
• 将您着色的每个像素添加到队列中。

- Stef

Answer 2

那实际上是一种“沃罗诺伊镶嵌”，因此您可以使用该术语来研究最佳方法。

您可以通过采用以下方式进行演示：

• 红色代表您的颜色1，坐标为（1,1）
• 酸橙绿色代表您的颜色2，坐标为（4,2）
• 蓝色代表您的颜色3，坐标为（5,0）

然后将输入图形按比例缩放10倍，以使结果足够大。然后在终端中使用ImageMagick绘制它：

magick -size 60x30 xc: \
   -sparse-color  Voronoi '10,10 red  40,20 lime  50,0 blue' \
   result.png

如果您只想使用单通道灰度而不是彩色，可以使用以下代码：

magick -size 60x30- xc: \
    -sparse-color  Voronoi '10,10 black 40,20 gray 50,0 white' result.png

这里有一篇关于这个和类似技术的优秀讨论和教程，作者是Anthony Thyssen 在这里。

它与"Delaunay Triangulation"相关，虽然我没有测试过，但我预计OpenCV实现会非常快速。

- Mark Setchell