连通部件标记算法有问题

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’表示您的当前位置。)

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

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

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

警告:当我说你可以做图片中的所有事情时，你将你的标签限制在254个对象上。

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