基于种子点的图像最近邻像素分割算法优化咨询

需求描述 #

实现一种基于种子点的图像分割方法，将每个像素分配给距离最近的种子点（采用曼哈顿距离）。示例如下：

输入 #

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

当前问题 #

现有实现采用三重循环，时间复杂度为O(宽度×高度×种子点数)。处理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;
    }
}

高效替代方案 #

1. 多源BFS（广度优先搜索） #

曼哈顿距离下，所有种子点同时作为起点进行BFS扩展：

• 初始化结果数组，将种子点位置标记为对应索引，其余位置设为未访问状态。
• 用队列存储所有种子点的坐标及对应索引。
• 每次从队列取出一个像素，遍历其上下左右邻域：若邻域未被访问，标记为当前种子索引并加入队列。
• 时间复杂度为O(宽度×高度)，每个像素仅被访问一次，效率远高于三重循环。

2. 线性时间距离变换算法 #

针对曼哈顿距离，可采用Saito提出的线性时间距离变换算法：

• 先对每行做一维距离变换，计算每行内每个像素到最近种子点的距离与索引。
• 再对每列做一维距离变换，结合行变换结果得到全局最近的种子点索引。
• 全程仅需两次遍历图像，时间复杂度同样为O(宽度×高度)。

3. 现有代码快速优化（无需更换核心算法） #

若暂时不想替换核心逻辑，可通过以下技巧大幅提升性能：

• 缓存种子坐标：提前将所有种子点的中心坐标提取到数组中，避免循环内频繁的对象访问与类型转换。
• 整数计算距离：曼哈顿距离为整数，用int替代double可消除浮点运算开销。
• 并行化循环：利用多核CPU并行处理每行计算，压缩整体耗时。

优化后的代码示例：

// 提前缓存种子点坐标
int seedCount = elements.Count;
int[] seedY = new int[seedCount];
int[] seedX = new int[seedCount];
for (int m = 0; m < seedCount; m++)
{
    CircleROI circle = roiResized[m];
    seedY[m] = circle.Center.Y;
    seedX[m] = circle.Center.X;
}

// 并行处理每行
Parallel.For(0, height, i =>
{
    int rowOffset = i * width;
    for (int j = 0; j < width; j++)
    {
        byte index = 0;
        int minDistance = int.MaxValue;
        for (int m = 0; m < seedCount; m++)
        {
            int currentDistance = Math.Abs(i - seedY[m]) + Math.Abs(j - seedX[m]);
            if (currentDistance < minDistance)
            {
                minDistance = currentDistance;
                index = (byte)m;
            }
        }
        data[rowOffset + j] = index;
    }
});

效果预期 #

多源BFS或距离变换方法处理相同规模图像，耗时可降至1秒以内；即使是优化后的三重循环，也能将耗时减少30%-50%。

内容的提问来源于stack exchange，提问作者Lamp