Graph-based Segmentation

Ref: Efficient Graph-Based Image Segmentation, Pedro F. Felzenszwalb and Daniel P. Huttenlocher, International Journal of Computer Vision, 59(2) September 2004.

struct edge {
    float w;	//weight=color_distance
    int a, b;   //vertices=pixel positions;
    edge() {}
    edge(int _a, int _b, float _w): a(_a), b(_b), w(_w) {}
};
bool operator<(const edge &a, const edge &b) {
  return a.w < b.w;
}
#define SQR(x) ((x)*(x)) 
#define DIFF(p,q) \
    (sqrt(SQR(red[(p)]-red[(q)])+SQR(green[(p)]-green[(q)])+SQR(blue[(p)]-blue[(q)])))
int segment_image(CRaster& raster, float c, int min_size, CRaster& out) {
    if (raster.GetBPP() != 24) return 0;
    const CSize sz = raster.GetSize();
    const int width = sz.cx, height = sz.cy;
    std::vector<float> red(width * height);
    std::vector<float> green(width * height);
    std::vector<float> blue(width * height);
    for (int y = 0, curr = 0; y <height; y++) {
        BYTE *p = (BYTE *)raster.GetLinePtr(y);
        for (int x = 0; x < width; x++, curr++) 
            blue[curr] = *p++, green[curr] = *p++, red[curr] = *p++;
    }
    // gaussian smoothing;
    const float sigma = 0.5F;
    smooth(blue,  width, height, sigma);
    smooth(green, width, height, sigma);
    smooth(red,   width, height, sigma);

    std::vector<edge> edges;
    edges.reserve(width * height * 4);
    for (int y = 0, curr = 0; y < height; y++) {
        for (int x = 0; x < width; x++, curr++) {
            if (x < width-1)
                edges.push_back(edge(curr, curr+1, DIFF(curr, curr+1)));
            if (y < height-1) 
                edges.push_back(edge(curr, curr+width, DIFF(curr, curr+width)));
            if ((x < width-1) && (y < height-1))
                edges.push_back(edge(curr, curr+width+1, DIFF(curr, curr+width+1)));
            if ((x < width-1) && (y > 0)) 
                edges.push_back(edge(curr, curr-width+1, DIFF(curr, curr-width+1)));
        }
    }

    if (c < 0) c = 1500; 
    if (min_size < 0) min_size = 10;
    universe *u = segment_graph(width*height, edges, c);
    // join small size regions;
    for (int i = edges.size(); i--> 0;) {
        edge &e = edges[i];
        int a = u->find(e.a), b = u->find(e.b);
        if ((a != b) && ((u->size(a) < min_size) || (u->size(b) < min_size)))
            u->join(a, b);
    }
    int num_rgns = u->count();

    // paint segmented rgns with root pixel color;
    out = raster;
    for (int y = height-1; y-->0;) 
        for (int x = width-1; x-->0;) {
            int a = u->find(y * width + x);
            out.SetPixel0(x, y, RGB(blue[a],green[a],red[a]));
        } 
    delete u;
    return num_rgns;
}
// Segment a graph
// c: constant for treshold function.
universe *segment_graph(int num_vertices, std::vector<edge>& edges, float c) { 
    // sort by weight
    std::sort(edges.begin(), edges.end());
    // disjoint-set
    universe *u = new universe(num_vertices);
    // init thresholds = {c};
    std::vector<float> threshold(num_vertices, c);

    for (int i = 0; i < edges.size(); i++) {
        edge &e = edges[i];
        int a = u->find(e.a), b = u->find(e.b);
        if (a != b)
            if ((e.w <= threshold[a]) && (e.w <= threshold[b])) {
                u->join(a, b);
                a = u->find(a);
                threshold[a] = e.w + c / u->size(a);
            }
    }
    return u;
};

https://kipl.tistory.com/460

Statistical Region Merging