c# - 连接组件标记算法有问题

Question

所以我一直在尝试编写一个连接组件标记算法，但它没有给我想要的结果。现在我有一张包含 3 朵玫瑰(不重叠)的图像，我想用自己的灰度值标记每朵玫瑰。在我应用标记算法之前，我使用一个阈值来去除背景并只保留玫瑰。玫瑰的灰度值为 1(全白)，背景的灰度值为 0(全黑)。这是它的样子的图像:

完成此操作后，我应用了标记算法。它应该根据给玫瑰的标签赋予玫瑰三种不同的灰度值。但相反，该算法在前两朵玫瑰上创建了这种奇怪的渐变模式，而最后一朵似乎是一个单一的灰度值。这是一张图片:

该算法可能看起来很复杂，但实际上非常简单。我先在列上递归，然后在行上递归，对于每个非背景像素，我检查它的任何邻居是否已经被标记(意味着它们的 objectArray 值不为零)。如果是这样，我将它们添加到邻居列表中。然后我继续检查这个列表是否不为空，如果是，我通过递增对象值并将其值分配给当前像素的标签值来唯一地标记当前像素，并且我还将当前像素的父值设置为这个唯一标签。如果不为空，则确定邻居列表中最小的标签值，将所有邻居的父值设置为该标签值，并将当前像素的标签和父值设置为该标签值。我对每个像素重复此操作，直到标记了整个图像。

完成此操作后，我再次递归处理像素值，这次是将每个像素的标签值设置为其父值。然后我继续根据其标签值为像素分配一个新的灰度值。

我不明白为什么算法没有正确标记玫瑰。有人可以帮帮我吗？这是算法:

public void label()
{
    int objects = 1;
    int[,] objectArray = new int[colors.GetLength(1), colors.GetLength(0)];
    DisjointSets disjointSet = new DisjointSets();
    int[,] parents = new int[colors.GetLength(1), colors.GetLength(0)];
    List<List<int>> eqSet = new List<List<int>>();
    for (int i = 0; i < colors.GetLength(1); i++) for (int j = 0; j < colors.GetLength(0); j++)
    {
        if (this[i, j].Gray == 1)
        {
            List<Label> neighbors = new List<Label>();
            if (i > 0)
            {
                if (this[i - 1, j].Gray == 1)
                {
                    if (objectArray[i - 1, j] != 0)
                    {
                        neighbors.Add(new Label(i - 1, j, 0));
                    }
                }
                if (j > 0)
                {
                    if (this[i - 1, j - 1].Gray == 1)
                    {
                        if (objectArray[i - 1, j - 1] != 0)
                        {
                            neighbors.Add(new Label(i - 1, j - 1, 0));
                        }
                    }
                }
                if (j < colors.GetLength(0))
                {
                    if (this[i - 1, j + 1].Gray == 1)
                    {
                        if (objectArray[i - 1, j] != 0)
                        {
                            neighbors.Add(new Label(i - 1, j, 0));
                        }
                    }
                }
            }
            if (j > 0)
            {
                if (this[i, j - 1].Gray == 1)
                {
                    if (objectArray[i, j - 1] != 0)
                    {
                        neighbors.Add(new Label(i, j - 1, 0));
                    }
                }
                if (i < colors.GetLength(1))
                {
                    if (this[i + 1, j - 1].Gray == 1)
                    {
                        if (objectArray[i + 1, j - 1] != 0)
                        {
                            neighbors.Add(new Label(i + 1, j - 1, 0));
                        }
                    }
                }
            }
            if (i < colors.GetLength(1))
            {
                if (this[i + 1, j].Gray == 1)
                {
                    if (objectArray[i + 1, j] != 0)
                    {
                        neighbors.Add(new Label(i + 1, j, 0));
                    }
                }
                if (this[i + 1, j + 1].Gray == 1)
                {
                    if (objectArray[i + 1, j + 1] != 0)
                    {
                        neighbors.Add(new Label(i + 1, j + 1, 0));
                    }
                }
            }
            if (j < colors.GetLength(0))
            {
                if (this[i, j + 1].Gray == 1)
                {
                    if (objectArray[i, j + 1] != 0)
                    {
                        neighbors.Add(new Label(i, j + 1, 0));
                    }
                }
            }

            if (neighbors.Count == 0)
            {
                objects++;
                objectArray[i, j] = objects;
                parents[i, j] = objects;
            }
            if (neighbors.Count > 0)
            {
                int smallestLabel = 10000;
                foreach (Label x in neighbors)
                    if (objectArray[x.X, x.Y] < smallestLabel)
                        smallestLabel = objectArray[x.X, x.Y];

                foreach (Label x in neighbors)
                    parents[x.X, x.Y] = smallestLabel;

                objectArray[i, j] = smallestLabel;
                parents[i, j] = smallestLabel;
            }
        }
    }
    for (int i = 0; i < colors.GetLength(1); i++) for (int j = 0; j < colors.GetLength(0); j++)
    {
        if (this[i, j].Gray == 1)
        {
            if (objectArray[i, j] != 0)
            {
                objectArray[i, j] = parents[i, j];
                ColorWrap c = this[i, j];
                c.X = (float)objectArray[i, j] / objects;
                c.Y = (float)objectArray[i, j] / objects;
                c.Z = (float)objectArray[i, j] / objects;
                this[i, j] = c;
            }
        }
    }
}

Answer 1

检查第三个邻居时出现索引错误:

                if (this[i - 1, j + 1].Gray == 1)
                {
                    if (objectArray[i - 1, j] != 0)
                    {
                        neighbors.Add(new Label(i - 1, j, 0));
                    }
                }

这三个点都应该是“j + 1”。

但这并不能解决您的问题。当您的算法遇到西北方向为黑色而东南方向为白色的对角线边缘时，您的算法就会出现问题。

您从左到右按列扫描图像，从上到下按行扫描每列。您检查了八个潜在的邻居，但实际上，您只能将像素添加到您已经通过的邻居列表，即左侧列中的三个像素和当前位置上方的像素。其他四个相邻像素的父级(或对象索引)为 0。

现在考虑这样的边:

          #######...
          ######....
          #####.....
          ####......
          ###O......
          ###.......
          ##x.......
          #xx.......

('#' 是黑色，'.' 是未分配的白色，'x' 是已分配父级的白色，'O' 标记您当前的位置。)

您只会发现黑色或未分配的相邻图 block 。您的邻居列表将为空，这意味着您的算法创建了一个新对象，尽管它在逻辑上应该属于东南方尚未发现的对象。

(您尝试通过为所有相邻像素分配新组的值来回溯，但这只会修复一个像素。它还可以创建空组，即没有对应像素的对象。)

无论如何，我认为您的方法太复杂了。它也不考虑组件主体上方和左侧的角落。不需要创建额外的数据结构，如果您使用灰度图像，您可以在图片本身中进行标记。将图像转为纯黑白后，将所有像素点传一次。如果一个像素是白色的，从那里用对应于下一个对象的正灰度值填充图片并增加对象的数量。然后再次通过所有像素，并根据物体id和物体数量调整灰度值。

警告:当我说您可以在图片中做任何事情时，您将标签限制为 254 个对象。

旁白:您可能需要稍微清理一下代码。您没有使用 eqSet 和 disjointSet，因此请将它们从您的代码中删除。两个数组 objectArray 和 parents 并列用于同一件事；将它们合并为一个。您还应该将查找八个相邻像素的过程重构为一个函数(对每个潜在的相邻像素进行一次调用)，以使内容更易于阅读并避免如上所述的索引错误。