连通分量标记算法

• 下载源代码

目录

• 概述
  • 五秒钟内
  • 五分钟内
• 预期功能
• 代码
• 工作原理
• 分步详解
• 棘手部分：合并标签

概述

五秒钟内 

检测图像中的连通对象，主要用于图像分析和 OCR。

五分钟内

连通分量标记（也称为连通分量分析、斑点提取、区域标记、斑点发现或区域提取）是图论的一种算法应用，其中根据给定的启发式方法对连通分量的子集进行唯一标记。连通分量标记不应与分割混淆。

连通分量标记用于计算机视觉，以检测二值数字图像中的连通区域，尽管也可以处理彩色图像和更高维度的数据。^[1][2]当集成到图像识别系统或人机交互界面中时，连通分量标记可以处理各种信息。^[3][4]斑点提取通常在阈值化步骤产生的二值图像上进行。斑点可以被计数、过滤和跟踪。

斑点提取与斑点检测相关但有所区别。

预期

输入

包含两个形状的图像

输出

现在每个形状都被分离成单独的图像

代码

接口 IConnectedComponentLabeling 包含一个函数，该函数接受一个 Bitmap 作为输入，并返回一个发现的对象集合。 

public interface IConnectedComponentLabeling
{
    IDictionary<int, Bitmap> Process(Bitmap input);
}

用法

IConnectedComponentLabeling target = new CCL();
Bitmap input = new Bitmap(AppDomain.CurrentDomain.BaseDirectory + @"\Test.bmp");

var images= target.Process(input);
foreach (var image in images)
{
    image.Value.Save(savePath + image.Key + ".bmp");
}

实现类包含虚函数 CheckIsBackGround()，因此您可以扩展该类，并覆盖此方法以适应图像的背景条件。

#region Protected Functions

protected virtual bool CheckIsBackGround(Pixel currentPixel)
{
    return currentPixel.color.A == 255 && currentPixel.color.R == 255 && 
             currentPixel.color.G == 255 && currentPixel.color.B == 255;
}

#endregion

工作原理

第一次扫描（分配标签）

第二次扫描（聚合）

分步详解

开始时，我们有这张图像，currentLabelCount 从 1 开始。

我们找到了非背景像素

获取其非背景邻居

邻居还没有被标记，我们将当前像素设置为 currentLabelCount 并将标签的父项设置为它本身（我们稍后会详细介绍）。

继续处理下一个像素，这个像素有一个邻居已经被标记。

将像素的父项标签分配给邻居的标签。

我们继续，这个像素的邻居都没有被标记。

我们增加 currentLabelCount 并将其分配给像素，同样，其父项设置为它本身：

这里变得有趣了，当邻居有不同的标签时。

 

1. 我们选择主标签，即：在发现的列表中最小的标签 --> (1)。
2. 我们将其设置为其他标签的父项。

 

再进行几次迭代，我们应该得到这样的结果。注意右上角的蓝色数字，那是父项标签，是我们稍后进行聚合的事实标签。

就是这样，现在我们要做的就是再次逐像素遍历图像，获取每个（如果已标记）的根，并将其存储在我们的模式列表中。

private Dictionary<int, List<Pixel>> AggregatePatterns(Dictionary<int, 
          Label> allLabels, int width, int height)
{
    var patterns = new Dictionary<int, List<Pixel>>();

    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            int patternNumber = _board[j, i];

            if (patternNumber != 0)
            {
                patternNumber = allLabels[patternNumber].GetRoot().Name;

                if (!patterns.ContainsKey(patternNumber))
                {
                    patterns.Add(patternNumber, new List<Pixel>());
                }

                patterns[patternNumber].Add(new Pixel(new Point(j, i), Color.Black));
            }
        }
    }

    return patterns;
}

棘手部分：合并标签  

为了连接同一集合中的标签，我们有以下类（它实现了并查集算法）

using System;
using System.Collections.Generic;
using System.Text;

namespace ConnectedComponentLabeling
{
    internal class Label
    {
        #region Public Properties

        public int Name { get; set; }

        public Label Root { get; set; }

        public int Rank { get; set; }

        #endregion

        #region Constructor

        public Label(int Name)
        {
            this.Name = Name;
            this.Root = this;
            this.Rank = 0;
        }

        #endregion

        #region Public Methods

        internal Label GetRoot()
        {
            if (this.Root != this)
            {
                this.Root = this.Root.GetRoot();//Compact tree
            }

            return this.Root;
        }

        internal void Join(Label root2)
        {
            if (root2.Rank < this.Rank)//is the rank of Root2 less than that of Root1 ?
            {
                root2.Root = this;//yes! then Root1 is the parent of Root2 (since it has the higher rank)
            }
            else //rank of Root2 is greater than or equal to that of Root1
            {
                this.Root = root2;//make Root2 the parent

                if (this.Rank == root2.Rank)//both ranks are equal ?
                {
                    root2.Rank++;//increment Root2, we need to reach a single root for the whole tree
                }
            }
        }

        #endregion
    }
}

特别注意递归函数 GetRoot()，这就是我们如何找到任何标签的父项。

还记得这部分吗？这就是 Join(Label root) 函数的作用。现在假设我们有三个标签，1、2 和 3，我们选择了 1 作为当前标签；我们所要做的就是遍历其他标签，如果它们的根不匹配，则将其根设置为我们刚刚选择的标签的根。 

结论

希望我能清晰地解释，请随时评论或提问 。由 zwibbler 绘制