seed-filling

思想

种子填充方法来源于计算机图形学，常用于对某个图形进行填充。思路：选取一个前景像素点作为种子，然后根据连通区域的两个基本条件（像素值相同、位置相邻）将与种子相邻的前景像素合并到同一个像素集合中，最后得到的该像素集合则为一个连通区域。

（1）扫描图像，直到当前像素点B(x,y) == 1：

a、将B(x,y)作为种子（像素位置），并赋予其一个label，然后将该种子相邻的所有前景像素都压入栈中；
b、弹出栈顶像素，赋予其相同的label，然后再将与该栈顶像素相邻的所有前景像素都压入栈中；
c、重复b步骤，直到栈为空；此时，便找到了图像B中的一个连通区域，该区域内的像素值被标记为label；

（2）重复第（1）步，直到扫描结束；

扫描结束后，就可以得到图像B中所有的连通区域；

代码实现

#include<opencv2\opencv.hpp>
#include<iostream>
#include<stack>
using namespace std;
using namespace cv;


void pushToStack(Mat &src,Mat &out,int flag,stack<Point2i> &pos)
{
    if (pos.empty())
    {
        return;
    }
        
    int row = src.rows; int col = src.cols;
    //将栈顶弹出，用flag 标记
    Point2i p = pos.top();
    pos.pop();
    out.at<int>(p.x, p.y) = flag;
    //将白色邻域加入栈中
    for (int i = 0; i < 3; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            int dx = 1 - i; int dy = 1 - j;
            int x = p.x - dx; int y = p.y - dy;
            if (x >= 0 && x < row && y >= 0 && y < col)
            {
                //非当前点，白色，未标记
                if (!(dx==0 && dy==0) && src.at<uchar>(x, y) == 255 && out.at<int>(x, y) == 0)
                {
                    Point2i tmp(x, y);
                    pos.push(tmp);
                }
            }
        }
    }
    //递归
    pushToStack(src, out, flag,pos);
}

//实现八连通阈标记，种子填充
void label(Mat &src, Mat &out)
{
    int flag = 1;
    stack<Point2i> pos;
    //Mat tmp(src.rows, src.cols, CV_32SC1);
    int row = src.rows; int col = src.cols;
    for (int i = 0; i < row; ++i)
    {
        for (int j = 0; j < col; ++j)
        {
            //找到一个为255，且没用被标记的像素点，给与新的标记，随后将其邻域的白色像素压栈
            if (src.at<uchar>(i, j) == 255 && out.at<int>(i, j) == 0)
            {
                cout << "here" << i << " " << j << endl;
                pos.push(Point2i(i, j));
                cout << pos.size() << endl;
                pushToStack(src, out, flag, pos);
                flag++;
            }       
        }
    }
}
int main()
{
    Mat src = imread("F:\\out.jpg", 0);
    threshold(src, src, 0, 255, THRESH_OTSU);
    imshow("src", src);
    Mat out(src.rows,src.cols,CV_32SC1);
    out = Scalar::all(0);

    label(src, out);

    map<int, int> area;
    for (int i = 0; i < out.rows; i++)
    {
        for (int j = 0; j < out.cols; ++j)
        {
            if (out.at<int>(i, j) > 0)
            {

                int tmp = out.at<int>(i, j);
                //cout << "tmp " << tmp << endl;
                if (area.find(tmp) == area.end())
                {
                    area[tmp] = 1;
                }
                else
                {
                    area[tmp] += 1;
                }
            }
        }
    }
    map<int, int>::iterator it;
    it = area.begin();
    cout << "map size" << area.size() << endl;
    while (it != area.end())
    {
        cout << it->first << " "<<it->second << endl;
        it++;
    }
    
    waitKey(0);
    return 0;
}

可能会出现stack overflow的问题，可以将stack的大小设置大一点