图像连通域标记之Two-Pass方法

作者: rainlin 分类: 算法 发布时间: 2016-12-03 16:03

背景

在完成图像的一系列处理后,得到二值图,一般会统计目标数量,即是获取连通域个数,这里采用TwoPass的方法。

基本思想

在Two-pass连通域标记中,第一次标记(first pass)时从左向右,从上向下扫描,会将各个有效像素置一个label值,判断规则如下(以4邻域为例):
1. 当该像素的左邻像素和上邻像素为无效值时,给该像素置一个新的label值,label ++;
2. 该像素的左邻像素或者上邻像素有一个为有效值时,将有效值像素的label赋给该像素的label值;
3. 当该像素的左邻像素和上邻像素都为有效值时,选取其中较小的label值赋给该像素的label值。
此时,还需维护一个关系表,记录哪些label值属于同一个连通域。这个关系表通常用union-find数据结构来实现。

原文在这
还有个图:
示意图

原文说用union-find结构保存连通域,没仔细看,于是自己用了个数组保存,类似于hash…实现起来也并不是很麻烦,大概这样,在开始建立一个map数组固定大小,一般而言应该与用于标记的最大数一致(注意,这里是标记数,是小于连通域数的),这里取uint16最大值,65535,这样也就意味着连通域数不能太大,估计最大能达到万把个吧,因为不同的图标记数和连通域数关系是不一样的。
在FirstPass时,取周围点的标记最小值,map[标记]=min,这样就构成了map数组,然后根据map数据进行第二次标记。

实现

int ImageAlgorithm::TwoPassConnetedDomin(Mat image) {
    Mat imageFlag;
    imageFlag.create(image.rows, image.cols, CV_16UC1);
    for (int k = 0; k < image.rows; ++k) {
        for (int i = 0; i < image.cols; ++i) {
            imageFlag.at<ushort>(k, i) = UINT16_MAX;
        }
    }
    uint16_t mapp[UINT16_MAX];
    memset(mapp, UINT16_MAX, sizeof(uint16_t));
    //第一次扫描,完成ImageFlag中的标记
    int num = 0;
    for (int i = 0; i < image.rows; ++i) {
        for (int j = 0; j < image.cols; ++j) {
            auto &cu = image.at<Vec3b>(i, j);
            if (cu[0] == 255) {
                uint16_t pos[4];
                auto &up = pos[0];
                auto &left = pos[1];
                auto &ul = pos[2];
                if (i > 0)
                    up = imageFlag.at<ushort>(i - 1, j);
                if (j > 0)
                    left = imageFlag.at<ushort>(i, j - 1);
                if (i > 0 && j > 0)
                    ul = imageFlag.at<ushort>(i - 1, j - 1);

                uint16_t min = pos[0];
                for (int m = 1; m < 3; m++)
                    if (min > pos[m])
                        min = pos[m];
                for (int m = 0; m < 3; m++) {
                    if (mapp[pos[m]] > min)
                        mapp[pos[m]] = min;
                }
                if (min == UINT16_MAX) {
                    imageFlag.at<ushort>(i, j) = num;
                    mapp[num] = num;
                    num++;
                    if(num>=UINT16_MAX)
                        return -1;
                } else {
                    imageFlag.at<ushort>(i, j) = min;
                }

            }
        }
    }
    //第二次扫描,进行标记,以及修改map
    map<ushort, uint32_t> colorMap;
    int total = 0;
    for (int n = 0; n < num; ++n) {
        if (mapp[n] == n) {
            total++;
            uint32_t t = 0;
            for (int i = 0; i < 3; ++i) {
                t += (uint32_t) (rand() / (RAND_MAX + 0.0) * 255) << (i * 8);
            }
            colorMap[n] = t;
        } else
            mapp[n] = mapp[mapp[n]];
    }

    for (int i = 0; i < imageFlag.rows; ++i) {
        for (int j = 0; j < imageFlag.cols; ++j) {
            auto t = imageFlag.at<ushort>(i, j);
            if (t != UINT16_MAX) {
                uint32_t c = colorMap[mapp[t]];
                image.at<Vec3b>(i, j)[0] = (uchar) c;
                image.at<Vec3b>(i, j)[1] = (uchar) (c >> 8);
                image.at<Vec3b>(i, j)[2] = (uchar) (c >> 16);
            }
        }
    }
    return total;
}

 

 

本文链接: http://rainlin.top/archives/98
转载请注明转载自: Rainlin Home

发表评论

邮箱地址不会被公开。 必填项已用*标注