用vc++实现连通区域标记
用阳卡争｜饕现唐≯’雾蓬通区匆《稼萄参Ｉ｜ｉ
｜ｉ。；：：
一、引言
用图像处理方法做目标检测的一般顺序是：图像预处理、边缘检测、阈值分割、区域标记、形状判断分析。
进行区域标记之前的图像一般已经被处理为二值图像。如图１所示，二值图像中可能有多个连通区域。进行图像检测的时候往往关心的是每个连通区域各自的特性。这就需要使用区域标记的方法把不同的连通区域区分开来。
图１经过前期处理所得到的二值图像
二、连通区域
像素间的连通性是确定区域的一个重要概念。在二维图像中，假设目标像素周围有ｍ（ｍ＜＝８）个相邻的像素，如果该像素灰度与这ｍ个像素中某～个点Ａ的灰度相等，那么称该像素与点Ａ具有连通性。常用的连通性有４连通和８连通。４连通一般选取目标像素的上、下、左、右四个点。８连通则选取目标像素在二维空间中所有的相邻像素。我们以下讨论的都采用了在实践中常选用的８连通区域。
将所有具有连通性的像素作为一个区域则构成了一个连通区域。那么对于图１，每个分离的白色目标区域被认为是一个连通区域。要注意的是，黑色背景同时也是一个连通区域。当然背景也可能被目标分成多个连通区域。目标和背景都是相对而言的。
三、标记算法
图像处理中有很多不同的标记算法。有些简单的算法只
玉案静。。豫玲。褰建永金赞
适合标记方形、圆形等规则的形状，并不是很实用。像素标记法和游程连通性分析是两种实用的方法，能够标记出符合连通性质的所有连通区域。这里我们只介绍易于理解的像素标记法，游程连通性分析可以参看《图像处理和分析上册》章毓晋编著Ｐ．２０６的介绍。
假设图像中目标像素的灰度为１，背景像素灰度为ｏ。标记算法只对目标像素进行标记，而不针对背景像素。
首先对一幅图像从左到右、从上到下进行扫描。假如当前像素的灰度值为０，就移到下一个扫描位置。假如当前像素的灰度值为１，检查它左、左上、上、右上这４个相邻像素（根据所采用的扫描次序，当我们到达当前像素时这４个相邻像素已经被处理过）。如果上述４个相邻像素的灰度值都为０，就给当前像素一个新的标记值。如果４个相邻像素中只有一个像素Ｐ的灰度值为ｌ，就把Ｐ像素的标记值赋给当前像素。如果４个相邻像素中有ｍ（１＜ｍ＜＝４）个像素的灰度值为ｌ，则按照左、左上、上、右上的优先顺序，确定当前像素的标记值。然后对这ｍ个像素所拥有的标记值做等价对，并将其归入一个等价对数组中。例如，４个像素的灰度值都为１时，将左边像素的标记值赋给当前像素，然后做出左等价左上，左等价上，左等价右上三个等价对，最后将这三个等价对加入等价对数组。第一次扫描结束后，所有灰度值为１的点都已经被标记过，但有些标记是等价的。
整理等价对数组，把等价对整理为等价关系。进行第二次图像扫描，根据整理所得的等价关系来进行重新标记。第二次扫描结束之后，所有灰度值为１的目标区域都被标记了不同的标记值。根据不同的标记值就可以区分不同的连通区域。
四、算法实现
本文采用Ｖｃ＋＋实现“像素标记法”。这里所处理的图像为二值化之后的８位ＢＭＰ图像。关于图像的读入、显示等方面，很多文章都有详细的叙述，这里就不再赘述了。
利用ＶＣ＋＋的Ｃｌａｓｓｗｉｚａｒｄ创建ｃＩｍａｇｅ类，增加如下成员变量。
Ｉｏｎｇｍ＿ＪｎｇＷｌｄｔｈ：／／图像宽
Ｉｏｎｇｍ＿ＪｎｇｗｌｄｔｈＢｙｔｅｓ：／／图像宽所占字节数
Ｉｏｎｇｍ＿ｊｎｇＨｅｉｇｈｔ：／／图像高
ｌｏｎｇｍ』ＩｎｇＢｌｔｓＣｏｕｎｔ：／／图像数据所占ｂｉｔ数
ＬＰＢＹＴＥｍ＿ＪｐＩｍｇＢｉｔｓ：／／图像数据区域指针
ＬＰＢＹＴＥｍ＿ＪｐＩｍｇＢｉｔｓＭｏｖｅ：／／数据区域移动指针
ｍ｝ｍＪｐｎＭａｒｋ：／／标记数组指针
Ｉｎｔ｝ｍＪｐｎＭａｒｋＭｏｖｅ：／／标记数组移动指针
ｉｎｔｍ』ＭａｒｋＮｕｍｂｅｒｓ：／／标记的区域个数
给ｃＩｒｒ－ａｇｅ类增加ＲｅａｄＢＭＰＦｉｌｅ（）成员函数来得到ＢＭＰ文件数据，初始化ⅡＵｎｇｗｉｄｔｈ、ｍ＿ｌｎｇｗｉｄｔｈＢｙｔｅｓ、Ⅱｄ“ｇＨｅｉｇｈｔ、ｍ』ｌｎ班ｉｔｓｃｏｕｎｔ、ＨｄｐＩｍｇＢｉｔｓ等成员变量。增加ｓｈｏｗＢＭＰＦｉｌｅ（）成员函数来显示ＢＭＰ文件。
由于版面原因，ＲｅａｄＢＭＰＦｉｌｅ（）和ＳｈｏｗＢＭＰＦｉｌｅ（）成员函数的具体实现就不在此给出了，读者可以向杂志社购买源代码光盘或直接发信到ｗｈｏｌｅｈ叩ｅ＠ｍａｉｌｓｔ．ｘｊｔｕ．ｅｄｕ．ｃｎ来要索取本文的完整代码。
为了保持原来图像数据的完整性，标记值不对原来的图像数据造成破坏。程序中另外申请一块与图像数据大小相同的ｉｎｔ型内存区域来存放标记，并将这段内存区域初始化为０。
像素标记算法的编程难点是对第一次找出的所有等价对进行判断，整理出全部的等价关系并做出重新映射。而第一次扫描时，进行等价对的寻找则相对简单的多。
填加两个ｓｔｒｕｃｔ，用于完成等价变换。
／／定义ＭａｒｋＭａｐ结构，用来存放等价对
ｔｙｐｅｄｅｆｓｔｒｕｃｔｔａｇＥｑｕａｌＭａｒｋ
｛ｍＭａｒｋＶａＩｕｅｌ：／／标记值１
ｉｎｔＭａｒｋＶａＩｕｅ２：／／标记值２
）ＥｑｕａｌＭａｒｋ：
／／定义ＭａｒｋＭａｐ结构，用来存放标记映射关系
ｔｙｐｅｄｅｆｓｔｒｕｃｔｔａｇＭａｒｋＭａｐｐｉｎｇ
｛ｊｎｔｎ０ｒｌｇｉｎａＭａｒｋ：／／第一次扫描后的标记
ｍｎＭａｐｐｌｎｇＭａｒｋ：／／等价整理之后对应标记
）ＭａｒｋＭａｐｐｉｎｇ：
下面给出ＭａｒｋＩｍａｇｅ（）成员函数较为完整的代码。
ＬｏｎｇＣＩｍａｇｅ：：ＭａｒｋＩｍａｇｅ（ＢＹＴＥｂｏｂｊｅｃｔＧｒａｙ）
｛
／／ｂｏｂｊｅｃｔＧｒａｙ为目标的灰度值，文本可以设为２５５
／＋申请标记数组空间，记得要在ＣＩｍａｇｅ类的构造函数中将ｍ－ｊｐｎＭａｒｋ初始化为ＮＵＬＬ｛／
ｉｆ（ｍ＿ｊｐｎＭａｒｋ＝＝ＮＵＬＬ）
（ｍ＿ＪｐｎＭａｒｋ＝ｎｅｗｉｎｔ【ｍ』ＩｎｇＢｉｔｓＣｏｕｎｔ１：
ＡＳＳＥＲＴ｛ｍ－』ｐｎＭａｒｋ！＝ＮＵＬＬ）：
ｍＪｐｎＭａｒｋＭｏｖｅ＝ｍ＿ＪｐｎＭａｒｋ：
）
：：ｍｅｍｓｅｔ《（ＬＰＢＹＴＥ）ｍ＿ｊｐｎＭａｒｋ，０，ｍ』ＩｎｇＢｉｔｓＣｏｕｎｔ木４）：
ｉｎｔｎＭａｒｋＶａＩｕｅ＝１：
／＋每次标识的值．ｎＭａｒｋＶａｌｕｅ会在后边递增．来表示不同的区域，从１开始标记＊／
ＩｎｔｎＭａ×ＭａｒｋＶａｌｕｅ＝Ｏ：／／记录最大的标识的值ｉｎｔｉ，ｊ：／／循环控制变量
／＋定义存放等价对的链表，其元素是ＥｑｕａＩＭａｒｋ类型，定义Ｉｉｓｔ是为了节约存储空问要使用Ｃ｜ｉｓｔ，应该＃ｌｎｃＩｕｄｅ＜Ａｆｘ－ｔｅｍＯｌｈ＞｝／
ＣＬｉｓｔ＜ＥｑｕａＩＭａｒｋ，ＥｑｕａｌＭａｒｋ＞『ＥｑｕａｌＭａｒｋ：
／／初始化图像移动指针
ｍ＿ＪｐＩｍｇＢｉｔｓＭｏｖｅ＝ｍ＿ＪｐｌｍｇＢｉｔｓ：
／＋进行第一次扫描，将所得的等价对《ＥｑｕａＩＭａｒｋ类型）加到ｌＥｑｕａｌＭａｒｋ链表中使用ｎＭａｒｋＶａｌｕｅ来进行每一次新的标记，标记之后将其值加１
由于版面关系，这部分代码也同样略去不写。作者提出以下几点编程时要注意的地方。
Ｎｏｔｅｌ：图像的四周像素并不会有８个相邻的像素。这时就要根据上、下、左、右四种不同的情况做不同的寻找等价对的判断。
Ｎｏｔｅ２：可以先对等价对进行排序，每次都保证ＭａｒｋＶａｌ—ｕｅｌ＜ＭａｒｋＶａｌｕｅ２，这样易于管理等价对。
Ｎｏｔｅ３：在实际工作中，连续寻找出的等价对很容易重复，将本次找出的等价对和链表中保存的最后一个等价对相比较，如果不相等的话再存入等价对链表，这样可以大大降低链表中等价对的重复。
Ｎｏｔｅ４：第一次扫描之后，ｎＭａｒｋＶａｌｕｅ一１即为ｎＭａ）【Ｍａｒｋ—Ｖａｌｕｅ。
／＊定义双层链表的外层链表，它的元素是一个指向内层链表的指针内层链表的型别也是ＣｐｔｒＬｉｓｔ，其元素是标记值＋／
ＣＰｔｒＬｌｓｔｅ×Ｌｉｓｔ：
ＣＰｔｒＬｉｓｔ水ＤｌｎｎｅｒＬｉｓｔ：
ＰＯＳＩＴｆ０ＮｐＯｓＥ×Ｅｌｅｍ：
ｉｆ（１ＥａｕａＩＭａｒｋＧｅｔＣｏｕｎｔ（）！＝Ｏ）
｛
／／ｐＩｎｎｅｒＬｉｓｔＡｄｄ，每次向ｅｘＬｉｓｔ中添加的新元素
ＣＰｔｒＬｉｓｔ。ｐＩｎｎｅｒＬｉｓｔＡｄｄ＝ｎｅｗＣＰｔｒＬｉｓｔ：
ＡＳＳＥＲＴ（ｐＩｎｎｅｒＬｊｓｔＡｄｄ！＝ＮＵＬＬ）：
／＋添加第一个等价对到ｅ×Ｌｌｓｔ的第一个元素所指向的ｈｎｅｒＬ』ｊｓｔ中￥／
ｐＪｎｎｅｒＬｊｓｔＡｄｄ一）ＡｄｄＴａＪＩ（ｆｖｏｊｄ半）ＪＥｑｕａＩＭａｒｋＧｅｔＨｅａｄｆ）ＭａｒｋＶａｌｕｅｌ）：
ＤｌｎｎｅｒＬｌｓｔＡｄｄ一＞ＡｄｄＴａｌＩ（《ｖｏｉｄ｛）ＩＥｑｕａｌＭａｒｋＧｅｔＨｅａｄ（）ＭａｒｋＶａＩｕｅ２）：
ｅｘＬｌｓｔＡｄｄＴａｉｆ（（ｖｏＩｄ￥）ｐｌｎｎｅｒＬｌｓｔＡｄｄ）：
ｌＥａｕａＩＭａｒｋＲｅｍｏｖｅＨｅａｄ（）：
／￥定义ｐＦｉｎｄＶａＩｕｅｌ和ｐＦｉｎｄＶａＩｕｅ２．存放在所有内层链表中找到特定值的某个内层链表的头指针，也就是外层链表的某个元素值：＊／
ＣＰｔｒＬｉｓｔ半ＤＦｌｎｄＶａｌｕｅｌ＝ＮＵＬＬ：
ＣＰｔｒＬｉｓｔ：。ＤＦｌｎｄＶａｌｕｅ２＝ＮＵＬＬ：
／／整理剩余的等价对
ｗｈｉｌｅ（！｛ＥｑｕａｌＭａｒｋｌｓＥｍｐｔｙ（））
（
ｐｏｓＥｘＥＩｅｍ＝ｅｘＬｊｓｔ．ＧｅｔＨｅａｄＰｏｓＪｔｊｏｎｆ）ｊ
ｐＦｌｎｄＶａＩｕｅｌ＝ＮｕＬＬ：
ｐＦｌｎｄＶａＩｕｅ２＝ＮｕＬＬ：
ｗｈｆｆｅ（ｐｏｓＥ×Ｅｆｅｍｊｆ｛ＩｐｌｎｎｅｒＬｉｓｔ＝（ｃＰｔｒＬｉｓｔ｛）ｅｘＬｉｓｔＧｅｔＡｔ｛ｐｏｓＥ×Ｅｌｅｍ）：
ｉｆ《ｐＩｎｎｅｒＬｉｓｔ一＞Ｆｉｎｄ（（ｖｏｉｄ术）ＩＥｑｕａＩＭａｒｋＧｅｔＨｅａｄ《）．Ｍａｒｋ—Ｐ…Ｊ｛
ｐＦｉｎｄＶａＩｕｅｌ＝ｐＩｎｎｅｒＬｉｓｔ：
｝
ｉｆ（ｐｆｎｎｅｒＬｉｓｔ一＞Ｆｌｎｄ（（ｖｏｉｄ￥）『ＥｑｕａｌＭａｒｋ．ＧｅｔＨｅａｄ（）Ｍａｒｋ．ｆｖａＪｕｅ２））Ｉ｛
ｐＦｉｎｄＶａｌｕｅ２＝ｐｌｎｎｅｒＬｉｓｔ：
｝
ｅｘＬｊｓｔＧｅｔＮｅｘｔｆｐｏｓＥ×ＥＪｅｍ）：
）Ｉ／／该等价对中两个值都在已经整理过的等价关系中
ｆｆ（ｐＦｉｎｄＶａｆｕｅｌ＆＆ｐＦｉｎｄＶａＩｕｅ２）ｉｆ／／当两个地址不一样时，对链表进行调整
ｉｆ（ｐＦｉｎｄＶａｌｕｅ１１＝ｐＦｉｎｄＶａｌｕｅ２）
｛
ｐＦｉｎｄＶａＩｕｅｌ一＞ＡｄｄＴａｌｌ（ｐＦｉｎｄＶａＩｕｅ２）：
／８清除链表元素，通过ｎｅｗ得到的ｃｐｔｒＬｉｓｔ类型，必须采用ｌｄｅＩｅｔｅ进行删除，否则会造成内存泄露．。／ＩＰｏｓｍｏＮｐｏｓＤｅｌｅｔｅ＝ｅｘＬ随Ｆｉｎｄ（（Ｖｏｉｄ术）听ｎｄＶａＩｕｅ２）：
ｐＦｉｎｄＶａ『ｕｅ２一＞ＲｅｍｏＶｅＡ｜｜（）：ＩｄｅＪｅｔｅｐＦＩｎｄＶａＪｕｅ２ｊＩｅｘＬＩｓｔＲｅｍｏｖｅＡｔ（ｐｏｓＤｅＩｅｔｅ）：
；）
／８只在已经整理过的等价关系中找到Ｖａｆｕｅｌ，那么将ｖａｕｆｅ２
加到ＶａＩｕｅｌ所在的链表中＊／
ｅＩｓｅｉｆ（ｐＦｉｎｄＶａｌｕｅｌ）
１
ｐＦ｝ｎｄＶａＪｕｅｌ一＞Ａｄｄ下ａ』ｆ（（ｖｏｆｄ￥）ｉＥｑｕａｆＭａｒｋＧｅｔＨｅａｄ（）Ｍａｒｋ、Ｐ２卜
）
ｅＩｓｅｌｆ（ｐＦｉｎｄＶａｌｕｅ２）
（
ｐＦＩｎｄＶａＩｕｅ２一＞ＡｄｄＴａｌＩ（（ＶｏＩｄ：＃）ＩＥｑｕａＩＭａｒｋＧｅｔＨｅａｄｆ）Ｍａｒｋ．Ｐ¨：１）
／。：等价对中两个值在整理过的等价关系中都没有找到，则在｜ｅｘＬｉｓｔ中增加新元素二一／
芦，ｏ
ｃＰｔｒＬｉｓｔ８ｐｆｎｎｅｆＬｆｓｔＡｄｄ＝ｎｅｗｃＰｔｒＬｉｓｔ：
ｐＩｎｎｅｒＬＩｓｔＡｄｄ一＞ＡｄｄＴａ｛Ｉ（ｆＶｏＩｄ￥）ＪＥｑｕａＪＭａｒｋＧｅｔＨｅａｄ（）Ｍａｒｋ—
ｖａｌｕｅｌ）：
ｐＩｎｎｅｒＬｆｓｔＡｄｄ一＞ＡｄｄＴａｉｆ（ｆｖｏｆｄ￥｝ｆＥｑｕａｆＭａｒｋＧｅｔＨｅａｄ（ＪＭａｒｋ—ＶａＩｕｅ２）：
ｅ×ＬｉｓｔＡｄｄＴａｉｌ（（ｖｏｉｄ半）ｐＩｎｎｅｒＬｉｓｔＡｄｄ）：
）
／／去掉此时等价对的头元素
ＩＥｑｕａＩＭａｒｋＲｅｍｏｖｅＨｅａｄ｛）：
｝／／ｗｈｉＩｅ（！ｌＥｑｕａｌＭａｒｋＩｓＥｍｐｔｙ｛））循环结束
｝／／ｉｆ（１ＥｑｕａＩＭａｒｋＧｅｔＣｏｕｎｔ（）！＝０）语句结束
／＊等价对链表大小为Ｏ，说明第一次扫描之后没有产生等价对，标记已经完成．＊／
ｅ１Ｓｅ
（ｒｅｔｕｍＴＲＵＥ：｝
／ｓ等价关系整理完成，下面建立第一次扫描的标记值和第二次扫描的标记值之间的映射关系ｍ／
ｉｎｔｎＴｏｔａＩＥｑｕａＩＮｕｍ＝Ｏ：／／列入等价关系的标记个数
ｉｎｔｎＭａｒｋＲｅｇｉｏｎ＝Ｏ：／／图像中连通区域个数
ｐｏｓＥｘＥｆｅｍ＝ｅｘＬｉｓｔ．ＧｅｔＨｅａｄＰｏｓｉｔｆｏｎ（｝：
ｗｈｊＩｅｆｐｏｓＥｘＥＪｅｍ）
（
ｐＩｎｎｅｒＬｉｓｔ＝《ＣＰｔｒＬｉｓｔ｛）ｅｘＬｉｓｔＧｅｔＡｔ（ｐｏｓＥ×ＥＩｅｍ）：
ｎＴｏｔａＩＥｑｕａＩＮｕｍ＋＝ｐｆｎｎｅｒＬｉｓｔ一＞ＧｅｔＣｏｕｎｔ（）：
ｅｘＬｊｓｔ．ＧｅｔＮｅｘｔｆｐｏｓＥｘＥｊｅｍ）：
）
ｎＭａｒｋＲｅｇｉＯｎ＝ｎＭａ×ＭａｒｋＶａＩｕｅ—ｎＴＯｔａＩＥａｕａｌＮｕｍ＋ｅｘＬｉｓｔ
ＧｅｔＣｏｕｎ“）：
／＋定义第一次扫描和第二次扫描之间的映射向量，要使用
Ｖｅｃｔｏｒ，应该＃ｉｎｃｌｕｄｅ＜Ｖｅｃｔｏｒ＞并且使用ｓｔｄ命名空间．｝／
Ｖｅｃｔｏｒ＜ＭａｒｋＭａｐｐｉｎｇ＞ｖＭａｒｋＭａｐ｛ｎＭａｘＭａｒｋＶａＩｕｅ）：
／／初始化映射向量，令其做自身映射
ｆｏｒｆｊ＝Ｏ：ｊ＜ｎＭａｘＭａｒｋＶａＪｕｅ：ｊ＋＋）
｛
ＶＭａｒｋＭａｐ【ｉ】ｎＯｒｉｇｉｎａｌＭａｒｋ＝ｉ＋１：
ＶＭａｒｋＭａｐ［ｉＪｎＭａｐｐｉｎｇＭａｒｋ＝ｌ＋１：
）
ＰＯＳｍ０Ｎｐｏｓｌｎｎｅ旧ｅｍ：／／ＩｎｎｅｒＬｊｓｔ中元素的位置
ｉｎｔｎＭｌｎ：／／１ｎｎｅｒＬｉｓｔ中最／Ｊ＼值
ｉｎｔｎｆｎｄｅ×＝Ｏ：
ｐｏｓＥｘＥＪｅｍ＝ｅｘＬＪｓｔＧｅｔＨｅａｄＰｏｓｉｔｊｏｎｆ）：
／４ｗｈ¨ｅ循环实现了如下功能：找到每个等价组中最小的标
记值，然后将映射向量中ｎＭａｐｐｉｎｇＭａｒｋ设定为其所在等价组的最小的标记值。／
ｗｈｊＪｅｆｐｏｓＥｘＥｊｅｍ）
｛
ｐｌｎｎｅｒＬｉｓｔ＝（ＣＰｔｒＬｉｓｔ｝）ｅｘＬｉｓｔＧｅｔＡｔ（ｐｏｓＥ×ＥＪｅｍ）：
ｎＭｉｎ＝（ｉｎｔ）ｐＩｎｎｅｒＬｉｓｔ一＞ＧｅｔＨｅａｄ（）：
ｐｏｓＪｎｎｅｒＥＪｅｍ＝ｐＪｎｎｅｒＬｆｓｔ一＞ＧｅｔＨｅａｄＰｏｓｉｔｉｏｎｆＪ：
ｐＩｎｎｅｒＬｊｓｔ一＞ＧｅｔＮｅｘｔ《ｐｏｓＩｎｎｅｒＥＩｅｍ）：
ｗ…ｅ《ｐｏｓｌｎｎｅｒＥｌｅｍ）
（
Ｊｆｆｆｆｎｔ）ｐＪｎｎｅｒＬｉｓｔ一＞ＧｅｔＡｔｆｐｏｓｆｎｎｅｒＥｆｅｍ）＜ｎＭ『ｎ）
ｆ
ｎＭｉｎ＝（ｉｎｔ）ｐＩｎｎｅｒＬｉｓｔ一＞ＧｅｔＡｔ（ｐｏｓｌｎｎｅｒＥｌｅｍ）：
｝
ｐｌｎｎｅｒＬｉｓｔ一＞ＧｅｔＮｅｘｔ（ｐｏｓＩｎｎｅｒＥＩｅｍ）：
／＋根据每组等价关系中的最小的标记值对Ｍａｐｐｉｎｇ向量做出调整。／
ｐｏｓＩｎｎｅｒＥＩｅｍ＝ｐＩｎｎｅｒＬｌｓｔ一＞ＧｅｔＨｅａｄＰｏｓｉｔｌｏｎ（）：
ｗｈｉＩｅ（ｐｏｓｌｎｎｅｒＥＩｅｍ）
｛
ｎＩｎｄｅｘ＝（ｉｎｔ）ｐＩｎｎｅｒＬｉｓｔ一＞ＧｅｔＡｔ（ｐｏｓＩｎｎｅｒＥＩｅｍ）一１：
ｖＭａｒｋＭａｐ【ｎＩｎｄｅｘ】ｎＭａｐｐｉｎｇＭａｒｋ＝ｎＭｉｎ：
ｐＩｎｎｅｒＬｉｓｔ一＞ＧｅｔＮｅ×ｔ（ｐｏｓＩｎｎｅｒＥｌｅｍ）：
）
ｅｘＬｉｓｔＧｅｔＮｅｘｔ（ｐｏｓＥ×ＥＩｅｍ）：
｝
／￥将映射向量ｎＭａｐｐｉｎｇＭａｒｋ中不重复的部分找出并对其进行排序使用们ｄ（）和ｓｏｒｔ（）这两种泛型算法，应该＃ＩｎｃＩｕｄｅ＜ａＩｇＯｒｉｔｈｍ＞．￥／
ｖｅｃｔｏｒ＜ｉｎｔ＞ｖＳｏｒｔＭａｒｋ｛ｎＭａｒｋＲｅｇｉｏｎ）：／／排序向量
ｎｌｎｄｅｘ＝０：
ｆｏｒ（ｉ＝Ｏ：ｉ＜ｎＭａｘＭａｒｋＶａｌｕｅ：ｌ＋＋）
｛
ｊｆ（ｆｌｎｄ（ｖＳｏｒｔＭａｒｋ．ｂｅｇｉｎ（），ｖＳｏｒｔＭａｒｋｅｎｄ《），ｖＭａｒｋＭａｐ【ｉ】ｎＭａｐｐｉｎｇＭａｒｋ）＝＝ｖＳｏｒｔＭａｒｋｅｎｄ｛））
（
ｖＳｏｒｔＭａｒｋ［ｎＩｎｄｅ×＋＋】＝ｖＭａｒｋＭａｐ【ｉ】ｎＭａｐｐｉｎｇＭａｒｋ：）
｝
ｓｏｒｔ（ｖＳｏｒｔＭａｒｋｂｅｇｌｎ（），ｖＳｏｒｔＭａｒｋｅｎｄ（））：
／＊根据排序后的标记在ｖＳｏｒｔＭａｒｋ向量中的位置，对映射向量做出重新调整。／
ｖｅｃｔｏｒ＜ｉｎｔ＞：：ｉｔｅｒａｔｏｒｉｔＦｉｎｄ：
ＶｅｃｔＯｒ＜ｉｎｔ＞：：ｉｔｅｒａｔＯｒｉｔＢｅｇｉｎ：
ｉｔＢｅｇｍ＝ｖＳｏｒｔＭａｒｋｂｅｇｍ（）：
ｆＯｒ（１＝Ｏ：ｉ＜ｎＭａ×ＭａｒｋＶａＩｕｅ：ｉ＋＋）
｛
ｉｔＦｉｎｄ＝ｆｉｎｄ（ＶＳｏｒｔＭａｒｋｂｅｇｌｎ（），ＶＳｏｒｔＭａｒｋｅｎｄ《），ＶＭａｒｋＭａｐ【ｉ】．ｎＭａｐｐｉｎｇＭａｒｋ）：
ｖＭａｒｋＭａｐ【ｉ】．ｎＭａｐｐｉｎｇＭａｒｋ＝（ｉｔＦｉｎｄ—ｉｔＢｅｇｉｎ＋１）：
）
／／根据映射向量对标记数组进行调整
ｆｏｒｆｊ＝Ｏ刊＜ｍＪｎｇＨｅｊｇｈｔ“＋＋）
｛
ｍ＿ＪｐｎＭａｒｋＭｏＶｅ＝ｍ＿ｊｐｎＭａｒｋ＋ｊ半ｍ－ｊｎｇＷｉｄｔｈＢｙｔｅｓ：
ｆｏｒ（ｉ＝Ｏ：ｌ＜ｍ－ｊｎｇＷｉｄｔｈ：ｌ＋＋）
｛
ｉｆ（｝ｍ＿ｊｐｎＭａｒｋＭｏｖｅ！＝Ｏ）
（
￥ｍＪｐｎＭａｒｋＭｏｖｅ＝ｖＭａｒｋＭａｐ［￥ｍ－ｊｐｎＭａｒｋＭｏｖｅ一１］ｎＭａｐｐｍｇＭａｒｋ：
｝
ｍＪｐｎＭａｒｋＭｏｖｅ＋＋：
）
｝
／／删除链表结构中通过ｎｅｗ得到的元素
ｐｏｓＥ×Ｅｌｅｍ＝ｅｘＬｉｓｔＧｅｔＨｅａｄＰｏｓｉｔｉｏｎ（）：
ｗｈｉＩｅ（ｐｏｓＥ×ＥＩｅｍ）
｛
ｐｌｎｎｅｒＬｉｓｔ＝《ＣＰｔｒＬｉｓｔ六）ｅ×ＬｌｓｔＧｅｔＡｔ（ｐｏｓＥ×ＥＩｅｍ
ｐｌｎｎｅｒＬｉｓｔ一＞ＲｅｍｏｖｅＡ¨（）：
ｄｅｌｅｔｅｐＪｎｎｅｒＬｉｓｔ：
ｅｘＬｉｓｔＧｅｔＮｅ×ｔ（ｐｏｓＥｘＥＩｅｍ）：
｝
ｅｘＬｉｓｔ．ＲｅｍｏｖｅＡ｜｜《）：
／／通过类成员变量来记录连通区域的个数
ｍ－ｎＭａｒｋＮｕｍｂｅｒｓ＝ｎＭａｒｋＲｅｇｉｏｎ：
ｒｅｔｕｒｎ｛Ｉｏｎｇ）ＴＲＵＥ：
）
五、小结
通过像素标记法可以准确地标出图像中各个连通区域。图像对应的标记数组中所被标记过的点之和就是目标像素总和。标记数组中最大值就是图像中连通区域的个数。通过扫描特定的标记值就可以得到特定的连通区域，从而对这个连通区域做出更多的判断，比如面积、形状、直径等等。这就为进一步的处理工作铺平了道路。
图２是对图１进行像素标记之后，对不同连通区域采用不同的灰度值来显示的结果。对标记之后的图像进行显示、保存等用到的辅助函数也包括在源代码中。
图２经过图像标记所得到的灰度图像
参考文献
１．章毓晋编著．图像处理和分析．清华大学出版社
２．何斌、马天予等编著．Ｖｉｓｕａｌｃ＋＋数字图像处理．人民邮电出版社
（收稿日期：２００２午１１月２日）
用VC++实现图像连通区域标记
作者：王安静， 陈玲， 宋建永， 金赞
作者单位：
刊名：
电脑编程技巧与维护
英文刊名：COMPUTER PROGRAMMING SKILLS & MAINTENANCE
年，卷(期)：2003，""(1)
被引用次数：6次
参考文献(2条)
1.章毓晋图像处理和分析
2.何斌.马天予VisualC++数字图像处理
引证文献(6条)
1.同兰娟.蒋晓瑜.宋小杉.汪熙.龙佩基于"猫眼效应"激光成像的目标探测[期刊论文]-激光与红外 2009(9)
2.黄建清.李中益.张利珍基于视频车辆目标检测的阴影去除的研究[期刊论文]-广西轻工业 2007(5)
3.谢滔.陈斌.曾首义基于图像分析的陶瓷碎片二维形状测量研究[期刊论文]-防护工程 2006(5)
4.鲍东来微型监控系统及其运动目标检测算法的研究[学位论文]硕士 2006
5.王鲲鹏序列图像运动目标检测算法研究[学位论文]硕士 2005
6.伍友龙基于图像分析的高速公路交通事件检测算法研究[学位论文]硕士 2005
本文链接：https://www.wendangku.net/doc/a33695611.html,/Periodical_dnbcjqywh200301022.aspx
授权使用：黄小强(wfxadz)，授权号：d1c4b542-c130-4fd2-8755-9e28009e0dac
下载时间：2010年11月8日
二值图像连通域标记算法与代码
二值图像连通域标记算法与代码 这里列举二值图像连通域标记算法包括直接扫描标记算法和二值图像连通域标记快速算法 一、直接扫描标记算法把连续区域作同一个标记，常见的四邻域标记算法和八邻域标记算法。 1、四邻域标记算法： 1）判断此点四邻域中的最左，最上有没有点，如果都没有点，则表示一个新的区域的开始。 2）如果此点四邻域中的最左有点，最上没有点，则标记此点为最左点的值；如果此点四邻域中的最左没有点，最上有点，则标记此点为最上点的值。 3）如果此点四邻域中的最左有点，最上都有点，则标记此点为这两个中的最小的标记点，并修改大标记为小标记。 2、八邻域标记算法： 1）判断此点八邻域中的最左，左上，最上，上右点的情况。如果都没有点，则表示一个新的区域的开始。 2）如果此点八邻域中的最左有点，上右都有点，则标记此点为这两个中的最小的标记点，并修改大标记为小标记。 3）如果此点八邻域中的左上有点，上右都有点，则标记此点为这两个中的最小的标记点，并修改大标记为小标记。 4）否则按照最左，左上，最上，上右的顺序，标记此点为四个中的一个。代码实现： #include #include
基于FPGA的二值图像连通域标记快速算法实现
基于FPGA的二值图像连通域标记快速算法实现 摘要：在图像自动目标识别和跟踪过程中，首先对图像目标进行阈值分割提取，得到的二值图像通常包含多个连通区域，系统利用图像目标的形状特性对可疑高威胁的飞行目标进行自动识别。因此，需要对各连通区域块进行分别检测判断，本文采用改进的适合FPGA实现的快速标记算法对各连通域进行检测提取。 关键词：FPGA，二值图像连通域，快速标记算法，可编程逻辑 贺明 1 引言 在图像自动目标识别和跟踪过程中，首先对图像目标进行阈值分割提取，得到的二值图像通常包含多个连通区域，系统利用图像目标的形状特性对可疑高威胁的飞行目标进行自动识别。因此，需要对各连通区域块进行分别检测判断，本文采用改进的适合FPGA实现的快速标记算法对各连通域进行检测提取。 实现二值图像连通体检测通常采用的方法有下几种[1] [2] [3]：区域生长法：首先对图像进行逐行(列)扫描，每遇到一个未标记的“1”像素点，就分配其一个未使用过的标号，然后对其领域进行检测，如有未标记过的“1”像素，则赋予相同的标号。反复进行这一操作．直到不存在应该传播标号的“1”像素。然后继续图像行(列)扫描，如检测判未标记的“1”像素则赋予其新的标号，并进行与以上相同的处理。整个图像扫描结束，算法也就终止。这种方法可准确地检测出各种类型的连通体．但处理时间也较长．因为要逐一检测每一“1”像素的邻域，且出现“1”像素的重复扫描。跟踪算法：二值图像中每个取值为“1”的像素被标记一个与其坐标相关的标号，如由n，m串构成的数。热后，扫描标记后的图像，并将每十像素的标号改为其邻域内的最小标号。反复执行这个过程，直到不需要作标记更改为止。用这种方法处理小而凸的目标时，收敛速度较慢。 本文以适合FPGA实现为目的，提出一种具有计算规则性的快速二值图像连通域标记算法。与传统的二值图像标记算法相比，该算法具有运算简单性、规则性和可扩展性的特点，适合以FPGA实现。选用在100MHz工作时钟下，处理384×288像素的红外图像能够达到400帧／秒以上的标记速度，足够满足实时目标识别系统的要求。处理速度可以满足大部分实时目标识别系统的要求。该算法同样可以软件编程方式应用于嵌入式DSP系统中。 2 算法描述 首先，在进行标记算法以前，利用硬件开辟独立的图像标记缓存和连通关系数组，接着在视频流的采集传输过程中，以流水线的方式按照视频传输顺序对图像进行逐行像素扫描，然后对每个像素的邻域分别按照逆时针方向和水平方向进行连通性检测和等价标记关系合并，检测出的结果对标记等价数组和标记缓存进行更新，在一帧图像采集传输结束后，得到图像的
(整理)MATLAB 标注连通域.
matlab 标注连通域 clear; clc; f=imread('c:\1.jpg'); gray_level=graythresh(f); f=im2bw(f,gray_level); [l,n]=bwlabel(f,8) imshow(f) hold on for k=1:n [r,c]=find(l==k); rbar=mean(r); cbar=mean(c); plot(cbar,rbar,'Marker','o','MarkerEdgeColor','k','MarkerFaceColor','k','MarkerSize',10); plot(cbar,rbar,'Marker','*','MarkerEdgecolor','w'); end 主要概念： 1. 2.4连接 8连接 0 1 0 1 p 1 ===> 4连接，p为当前像素点。 0 1 0 1 1 1 1 p 1 ====》8连接，p为当前像素点。 1 1 1 3.bwlabel()函数 语法： [ L, num]=bwlabel(f,conn) 其中f是一副二值图像，conn用来指定期望的连接（不是4就是8），默认为8，输出L称为标记矩阵，参数num给出所找到连接分量的总数。 4.find()函数 该函数非常有用，会返回指定条件的索引值，在标记矩阵中的作用是返回对应对象的索引。 I = FIND(X) returns the linear indices corresponding to the nonzero entries of the array X. X may be a logical expression. Use IND2SUB(SIZE(X),I) to calculate multiple subscripts from the linear indices I. find（bwlabel（bw）==2）表示的意思是连通域2中的数值所在向量的位置。
二值化图像8联通域标记
//基于区域生长法的连通域标记（C语言） 区域生长法利用区域生长的思想，一次生长过程可以标记一整个连通区，只需对图像进行一次扫描就能标记出所有连通区。算法描述如下： Step1、输入待标记图像bitmap(二值化原图，SDRAM内,u16，只有0x0000与0xffff)，初始化一个与输入图像同样尺寸的标记矩阵labelmap(SDRAM内，大小与二值化原图相同,u16，初值0x0000)，一个队列queue(SDRAM内，大小与二值化原图相同)以及标记计数labelIndex （unsigned char，最大值255,初值0）； Step2、按从左至右、从上至下的顺序扫描bitmap，当扫描到一个未被标记的前景像素p时（0xffff，2个字节，unsigned short int），labelIndex加1，并在labelmap中标记p（相应点的值赋为labelIndex），同时，扫描p的八邻域点，若存在未被标记的前景像素，则在labelmap 中进行标记，并放入queue中，作为区域生长的种子； Step3、当queue不为空时，从queue中取出一个生长种子点p1，扫描p1的八邻域点，若存在未被标记过的前景像素，则在labelmap中进行标记，并放入queue中； Step4、重复Step3直至queue为空，一个连通区标记完成； Step5、转到Step2，直至整幅图像被扫描完毕，得到标记矩阵labelmap和连通区的个数labelIndex。 该算法最坏情况下，将对每个像素点都进行一次八邻域搜索，算法复杂度为O(n)。 //辅助队列 typedef struct QNode { int data; struct QNode *next; }QNode; typedef struct Queue { struct QNode* first; struct QNode* last; }Queue; void PushQueue(Queue *queue, int data) { QNode *p = NULL; //p = (QNode*)malloc(sizeof(QNode)); p->data = data; if(queue->first == NULL) { queue->first = p; queue->last = p; p->next = NULL; } else
二值图像连通域标记算法与代码 收藏
二值图像连通域标记算法与代码收藏 10:19:42二值图像连通域标记算法与代码 这里列举二值图像连通域标记算法包括直接扫描标记算法和二值图像连通域标记快速算法 一、直接扫描标记算法把连续区域作同一个标记，常见的四邻域标记算法和八邻域标记算法。 1、四邻域标记算法： 1）判断此点四邻域中的最左，最上有没有点，如果都没有点，则表示一个新的区域的开始。 2）如果此点四邻域中的最左有点，最上没有点，则标记此点为最左点的值；如果此点四邻域中的最左没有点，最上有点，则标记此点为最上点的值。 3）如果此点四邻域中的最左有点，最上都有点，则标记此点为这两个中的最小的标记点，并修改大标记为小标记。 2、八邻域标记算法： 1）判断此点八邻域中的最左，左上，最上，上右点的情况。如果都没有点，则表示一个新的区域的开始。 2）如果此点八邻域中的最左有点，上右都有点，则标记此点为这两个中的最小的标记点，并修改大标记为小标记。 3）如果此点八邻域中的左上有点，上右都有点，则标记此点为这两个中的最小的标记点，并修改大标记为小标记。 4）否则按照最左，左上，最上，上右的顺序，标记此点为四个中的一个。 代码实现： #include #include
{ std::list
用vc++实现连通区域标记
用阳卡争｜饕现唐≯’雾蓬通区匆《稼萄参Ｉ｜ｉ ｜ｉ。；：： 一、引言 用图像处理方法做目标检测的一般顺序是：图像预处理、边缘检测、阈值分割、区域标记、形状判断分析。 进行区域标记之前的图像一般已经被处理为二值图像。如图１所示，二值图像中可能有多个连通区域。进行图像检测的时候往往关心的是每个连通区域各自的特性。这就需要使用区域标记的方法把不同的连通区域区分开来。 图１经过前期处理所得到的二值图像 二、连通区域 像素间的连通性是确定区域的一个重要概念。在二维图像中，假设目标像素周围有ｍ（ｍ＜＝８）个相邻的像素，如果该像素灰度与这ｍ个像素中某～个点Ａ的灰度相等，那么称该像素与点Ａ具有连通性。常用的连通性有４连通和８连通。４连通一般选取目标像素的上、下、左、右四个点。８连通则选取目标像素在二维空间中所有的相邻像素。我们以下讨论的都采用了在实践中常选用的８连通区域。 将所有具有连通性的像素作为一个区域则构成了一个连通区域。那么对于图１，每个分离的白色目标区域被认为是一个连通区域。要注意的是，黑色背景同时也是一个连通区域。当然背景也可能被目标分成多个连通区域。目标和背景都是相对而言的。 三、标记算法 图像处理中有很多不同的标记算法。有些简单的算法只 玉案静。。豫玲。褰建永金赞 适合标记方形、圆形等规则的形状，并不是很实用。像素标记法和游程连通性分析是两种实用的方法，能够标记出符合连通性质的所有连通区域。这里我们只介绍易于理解的像素标记法，游程连通性分析可以参看《图像处理和分析上册》章毓晋编著Ｐ．２０６的介绍。 假设图像中目标像素的灰度为１，背景像素灰度为ｏ。标记算法只对目标像素进行标记，而不针对背景像素。 首先对一幅图像从左到右、从上到下进行扫描。假如当前像素的灰度值为０，就移到下一个扫描位置。假如当前像素的灰度值为１，检查它左、左上、上、右上这４个相邻像素（根据所采用的扫描次序，当我们到达当前像素时这４个相邻像素已经被处理过）。如果上述４个相邻像素的灰度值都为０，就给当前像素一个新的标记值。如果４个相邻像素中只有一个像素Ｐ的灰度值为ｌ，就把Ｐ像素的标记值赋给当前像素。如果４个相邻像素中有ｍ（１＜ｍ＜＝４）个像素的灰度值为ｌ，则按照左、左上、上、右上的优先顺序，确定当前像素的标记值。然后对这ｍ个像素所拥有的标记值做等价对，并将其归入一个等价对数组中。例如，４个像素的灰度值都为１时，将左边像素的标记值赋给当前像素，然后做出左等价左上，左等价上，左等价右上三个等价对，最后将这三个等价对加入等价对数组。第一次扫描结束后，所有灰度值为１的点都已经被标记过，但有些标记是等价的。 整理等价对数组，把等价对整理为等价关系。进行第二次图像扫描，根据整理所得的等价关系来进行重新标记。第二次扫描结束之后，所有灰度值为１的目标区域都被标记了不同的标记值。根据不同的标记值就可以区分不同的连通区域。 四、算法实现 本文采用Ｖｃ＋＋实现“像素标记法”。这里所处理的图像为二值化之后的８位ＢＭＰ图像。关于图像的读入、显示等方面，很多文章都有详细的叙述，这里就不再赘述了。 利用ＶＣ＋＋的Ｃｌａｓｓｗｉｚａｒｄ创建ｃＩｍａｇｅ类，增加如下成员变量。 Ｉｏｎｇｍ＿ＪｎｇＷｌｄｔｈ：／／图像宽 Ｉｏｎｇｍ＿ＪｎｇｗｌｄｔｈＢｙｔｅｓ：／／图像宽所占字节数
计算连通域的面积
计算连通域的面积 matlab函数_连通区域 1、 matlab函数bwareaopen——删除小面积对象 格式：BW2 = bwareaopen(BW,P,conn) 作用：删除二值图像BW中面积小于P的对象，默认情况下使用8邻域。 算法： (1)Determine the connected components. L = bwlabeln(BW, conn); (2)Compute the area of each component. S = regionprops(L, 'Area'); (3)Remove small objects. bw2 = ismember(L, find([S.Area] >= P)); 2、matlab函数bwarea——计算对象面积 格式：total = bwarea(BW) 作用：估计二值图像中对象的面积。 注：该面积和二值图像中对象的像素数目不一定相等。 3、matlab函数imclearborder——边界对象抑制 格式：IM2 = imclearborder(IM,conn) 作用：抑制和图像边界相连的亮对象。若IM是二值图，imclearborder将删除和图像边界相连的对象。默认情况conn=8。 注：For grayscale images, imclearborder tends to reduce the overall intensity level in addition to suppressing border structures. 算法： (1)Mask image is the input image. (2)Marker image is zero everywhere except along the border, where it equals the mask image. 4、matlab函数bwboundaries——获取对象轮廓 格式：B = bwboundaries(BW,conn)（基本格式） 作用：获取二值图中对象的轮廓，和OpenCV中cvFindContours函数功能类似。B是一个P ×1的cell数组，P为对象个数，每个cell 是Q×2的矩阵，对应于对象轮廓像素的坐标。 5、matlab函数imregionalmin——获取极小值区域 格式：BW = imregionalmin(I,conn) 作用：寻找图像I的极小值区域（regional maxima），默认情况conn=8。 Regional minima are connected components of pixels with a constant intensity value, and whose external boundary pixels all have a higher value. 6、matlab函数bwulterode——距离变换的极大值 格式：BW2 = bwulterode(BW,method,conn) 作用：终极腐蚀。寻找二值图像BW的距离变换图的区域极大值（regional maxima）。用于距离变换的距离默认为euclidean，连通性为8邻域。
二值图像连通域标记快速算法实现
二值图像连通域标记快速算法实现 算法描述 首先，在进行标记算法以前，利用硬件开辟独立的图像标记缓存和连通关系数组，接着在视频流的采集传输过程中，以流水线的方式按照视频传输顺序对图像进行逐行像素扫描，然后对每个像素的邻域分别按照逆时针方向和水平方向进行连通性检测和等价标记关系合并，检测出的结果对标记等价数组和标记缓存进行更新，在一帧图像采集传输结束后，得到图像的初步标记结果以及初步标记之间的连通关系，最后，根据标号对连通关系数组从小到大的传递过程进行标号的归并，利用归并后的连通关系数组对图像标记缓存中的标号进行替换，替换后的图像为最终标记结果，并且连通域按照扫描顺序被赋予唯一的连续自然数。 图 1 标记算法流程 本文快速二值图像连通域标记算法分为三个环节： 1.图像初步标记：为每个像素赋予临时标记，并且将临时标记的等价关系记录在等价表中 2.整理等价表：这一环节分为两个步骤： （1）将具有等价关系的临时标记全部等价为其中的最小值； （2）对连通区域以自然数顺序重新编号，得到临时标记与最终标记之间的等价关系。 3.图像代换：对图像进行逐像素代换，将临时标记代换为最终标记．经过3个环节处理后，算法输出标记后的图像，图像中连通域按照由上到下，由左至右出现的顺序被标以连续的自然数。 1 图像初始标记 标记算法符号约定：算法在逆时钟方向检测连通域时用w1，w2表示连续两行的图像数据，在紧接着的顺时钟方向连通域检测时用k0，k表示连续两行经过
逆时钟方向标记后的图像数据。其在工作窗口的位置在图2、3中分别说明；对初始逆时针方向临时标记用Z表示。Z初始标记值为1。 二值图像连通域标记算法采用8连通判断准则，通过缩小标记范围剔除了图像的边界效应。为了简化标记处理过程，使标记处理在硬件对一帧图像传输操作时间内结束，标记处理利用中间数据缓存分为连续的两种类型，其中类型1用于直接图像序列传输，硬件发起图像序列传输时，类型1采用逆时钟顺序连通域检测，对2×3工作窗口中的二值像素进行初始标记。类型2对经过类型1初始标记过的图像数据再进行水平方向的连通域检测和归并，然后把标记结果存入图像存储区。 图像初始标记类型1： 步骤1读取像素w1（2）、w1（1）、w1（0）、w0（2）、w0（1），以及相应的二值像素值。 步骤2读取像素w0（1），按照逆时针方向依次与w1（0）、w1（1）、w1（2）、w0（2）比较，若w0（1）= w1（0），则k0（1）=k（2）；若w0（1）= w1（1），则k0（1）=k（1）；若w0（1）= w1（2），则k0（1）=k（0）；若w0（1）= w0（2），则k0（1）=k0（0）；否则（即w0（1）≠（w1（2）、w1（1）、w1（0）、w0（2）），k0（1）= Z；Z ++。 步骤3写入等价关系表，以Z为地址将Z写入等价关系数组。 图 2 逆时钟方向初始标记的工作窗 图像初始标记类型2： 步骤1判断经过逆时针方向标记后，如果w0（1）= w0（2）= 1，而标记灰度k0（1）≠k0（0），则进行下一步骤。 步骤2 假设k0（1）> k0（0），判断lab（k0（1））=k0（1）或者lab（k0（1））=k0（0），则lab（k0（1））=k0（0），否则对标记数组进行追踪置换。跳转至步骤3。 步骤3 假设k0（1）< k0（0），判断lab（k0（0））=k0（0）或者lab（k0（0））=k0（1），则lab（k0（0））=k0（1），否则对标记数组进行追踪置换。 追踪置换方法：步骤2的追踪置换令t= lab（k0（0））；若lab（t）≠t，则
基于连通域算法的区域测量
第8卷 第9期 2008年5月1671-1819(2008)9-2492-03 科 学 技 术 与 工 程 S c i e n c e T e c h n o l o g ya n d E n g i n e e r i n g V o l .8 N o .9 M a y 2008 2008 S c i .T e c h .E n g n g . 基于连通域算法的区域测量 李仪芳 刘景琳 (广东技术师范学院电子与信息学院,广州510665) 摘 要 基于数字图像处理的原理,提出用八连通域算法对有多个连通区域的二值图像进行面积测量。通过逐行逐列地扫描图像,按照一定的规则标记连通区域,得到对象的个数,同时统计每个区域所含的像素,通过标尺转换可以得出区域的面积。结果表明,该算法能有效地提取八连通区域,可用于计算显微图像颗粒物的面积和粒径。关键词 区域标记 像素测量 八连通域算法中图法分类号 T P 391.77; 文献标识码 A 2008年1月21日收到 广东省第二批产业技术研究研发计划 项目(2007B 010200041)资助 第一作者简介:李仪芳(1983—),女,广东三水人,广东技术师范学院助教,硕士,研究方向:图像处理和光电技术。E -m a i l :a n g e l i -n a 2008@y a h o o .c o m .c n 二值图像中连通域的提取是图像处理和分析中的一个重要处理过程,可以用于显微图像的对象识别和测量,红外图像的目标定位等领域。灰度图像经过阈值分割后常包括多个连通的区域,需要将连通区域搜索标记出来以便测量。但常见算法是关于四连通区域的研究,其中文献[1,2]中描述或采用的是区域标号法,但文献[1]中描述的算法在实现时并不能达到预定的结果。而且区域生长法计算复杂度过高;像素标记法和行程标记法必须全部扫描完图像才能得到连通域,随着图像幅度和连通域个数的增加,计算复杂度增长。现提出用八连通域算法 [3] ,它不仅能在对图像一次扫描中标记连 通域即计算对象的个数,而且可实现边扫描边提取像素,即累计每个连通域所含像素的个数。 1 区域标记 算法实现逐行逐列扫描,对图像内每个连通的黑色区域进行标记操作,求得对象的数目。图1为6×12图像点阵,图中有三个连通区域,即三个对 象,分别用1,2,3标号。设前景点灰度取1,背景点取值为0。在算法中,定义了多个数组N (i ),其中i 代表连通区域的标号,∑N (i )表示区域内部包含的像素个数。如第1个区域,∑N (1)=7;对第2个区域,∑N (2)=6。下面以标记区域1为例,说明标记的具体算法。 图1 八连通域算法说明图 ① 初始化N (i )=0,i =0。② 从左到右,从上到下逐行扫描图像;如果没有遇到“1”,则继续扫描。若遇到“1”,如(1,1),则依次判断该像素点的