c++ - 使用递归算法在 OpenCV 中进行连通分量标记

Question

我正在尝试使用递归算法在 OpenCV 中实现连通分量标记。我不确定我实现了什么错误。算法是这样的

B是二值图像，LB是带标签的二值图像

procedure connected_component(B,LB)
{
    LB:=negate(B);
    label:=0;
    findComponents(LB,label);
    display(LB);
}

procedure findComponents(LB,label)
{
    for L:=0 to maxRow
        for P:= 0 to maxCol
            if LB[L,P] == -1 then
              {
               label:=label+1;
               search(LB,label,L,P);
              }
}

procedure search(LB,label,L,P)
{
    LB[L,P]:=label;;
    Nset:= neighbours(L,P);
      for each(L',P') in Nset
      {
        if(LB[L',P'] == -1) then
        search(LB,label,L',P');
      }
}

我在OpenCV中编写的代码如下

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

void findComponents(Mat res, int label);
void search(Mat res, int label, int row, int col);

int main()
{
    Mat src = imread("D:/My Library/test/peppers.bmp",0);
    src.convertTo(src,CV_8S);
    Mat th = src.clone();
    threshold(src,th,128,255,CV_8S);
    Mat res = th.clone();

    for(int i=0;i<res.rows;i++)
        for(int j=0;j<res.cols;j++)
            res.at<signed char>(i,j) = 0 - th.at<signed char>(i,j);

    int label = 0;
    findComponents(res,label);


    waitKey(0);
    return 0;
}

void findComponents(Mat res, int label)
{
    for (int i = 1; i < res.rows - 1; i++)
    {
        for (int j = 1; j < res.cols - 1; j++)
        {
          if (res.at<signed char>(i, j) == -255)
          {
            label++;
            search(res, label, i, j);
          }
        }
    }
    imshow("CC Image", res);

}

void search(Mat res, int label, int row, int col)
{
    res.at<signed char>(row, col) = label;
    if (res.at<signed char>(row, col + 1) == -255) search(res, label, row, col + 1);
    if (res.at<signed char>(row + 1, col + 1) == -255) search(res, label, row+1, col + 1);
    if (res.at<signed char>(row + 1, col) == -255) search(res, label, row + 1, col);
    if (res.at<signed char>(row + 1, col - 1) == -255) search(res, label, row + 1, col - 1);
    else return;

}

该代码不起作用。我在实现算法时犯了什么错误？我是 OpenCV 新手。

Answer 1

您的代码中存在一些问题。最重要的是你不应该使用CV_8S矩阵。为什么？

• 它们的值限制在 [-128, 127] 范围内
• 检查等于 -255 的值将无法正常工作
• 每个图像最多有 127 个连接组件
• threshold不会按预期工作
• 也许其他人...

我重新实现了您的代码以纠正这些问题:

• 您应该使用CV_32S为您的标签。
• 你应该考虑边界
• 您可以使用Mat_<Tp>为了方便访问，而不是 .at<Tp>

下面是代码。我用过applyCustomColorMap更好地可视化结果。

#include <opencv2/opencv.hpp>
#include <algorithm>
#include <vector>
#include <stack>
using namespace cv;

void search(Mat1i& LB, int label, int r, int c)
{
    LB(r, c) = label;

    // 4 connected
    if ((r - 1 > 0) && LB(r - 1, c) == -1)       { search(LB, label, r - 1, c    ); }
    if ((r + 1 < LB.rows) && LB(r + 1, c) == -1) { search(LB, label, r + 1, c    ); }
    if ((c - 1 > 0) && LB(r, c - 1) == -1)       { search(LB, label, r    , c - 1); }
    if ((c + 1 < LB.cols) && LB(r, c + 1) == -1) { search(LB, label, r    , c + 1); }

    // 8 connected
    if ((r - 1 > 0) && (c - 1 > 0) && LB(r - 1, c - 1) == -1)             { search(LB, label, r - 1, c - 1); }
    if ((r - 1 > 0) && (c + 1 < LB.cols) && LB(r - 1, c + 1) == -1)       { search(LB, label, r - 1, c + 1); }
    if ((r + 1 < LB.rows) && (c - 1 > 0) && LB(r + 1, c - 1) == -1)       { search(LB, label, r + 1, c - 1); }
    if ((r + 1 < LB.rows) && (c + 1 < LB.cols) && LB(r + 1, c + 1) == -1) { search(LB, label, r + 1, c + 1); }

}

int findComponents(Mat1i& LB)
{
    int label = 0;

    for (int r = 0; r < LB.rows; ++r) {
        for (int c = 0; c < LB.cols; ++c) {
            if (LB(r, c) == -1) {
                ++label;
                search(LB, label, r, c);
            }
        }
    }
    return label;
}

int connected_components(const Mat1b& B, Mat1i& LB)
{
    // Foreground is > 0
    // Background is 0

    LB = Mat1i(B.rows, B.cols, 0);
    LB.setTo(-1, B > 0);

    // Foreground labels are initialized to -1
    // Background labels are initialized to 0

    return findComponents(LB);
}

void applyCustomColormap(const Mat1i& src, Mat3b& dst);

int main()
{
    // Load grayscale image
    Mat1b img = imread("path_to_image", IMREAD_GRAYSCALE);

    // Binarize the image
    Mat1b bin;
    threshold(img, bin, 127, 255, THRESH_BINARY);

    // Find labels
    Mat1i labels;   
    int n_labels = connected_components(bin, labels);

    // Show results
    Mat3b out;
    applyCustomColormap(labels, out);

    imshow("Labels", out);
    waitKey();

    return 0;
}


void applyCustomColormap(const Mat1i& src, Mat3b& dst)
{
    // Create JET colormap

    double m;
    minMaxLoc(src, nullptr, &m);
    m++;

    int n = ceil(m / 4);
    Mat1d u(n * 3 - 1, 1, double(1.0));

    for (int i = 1; i <= n; ++i) {
        u(i - 1) = double(i) / n;
        u((n * 3 - 1) - i) = double(i) / n;
    }

    std::vector<double> g(n * 3 - 1, 1);
    std::vector<double> r(n * 3 - 1, 1);
    std::vector<double> b(n * 3 - 1, 1);
    for (int i = 0; i < g.size(); ++i)
    {
        g[i] = ceil(double(n) / 2) - (int(m) % 4 == 1 ? 1 : 0) + i + 1;
        r[i] = g[i] + n;
        b[i] = g[i] - n;
    }

    g.erase(std::remove_if(g.begin(), g.end(), [m](double v){ return v > m; }), g.end());
    r.erase(std::remove_if(r.begin(), r.end(), [m](double v){ return v > m; }), r.end());
    b.erase(std::remove_if(b.begin(), b.end(), [](double v){ return v < 1.0; }), b.end());

    Mat1d cmap(m, 3, double(0.0));
    for (int i = 0; i < r.size(); ++i) { cmap(int(r[i]) - 1, 0) = u(i); }
    for (int i = 0; i < g.size(); ++i) { cmap(int(g[i]) - 1, 1) = u(i); }
    for (int i = 0; i < b.size(); ++i) { cmap(int(b[i]) - 1, 2) = u(u.rows - b.size() + i); }

    Mat3d cmap3 = cmap.reshape(3);

    Mat3b colormap;
    cmap3.convertTo(colormap, CV_8U, 255.0);

    // Apply color mapping
    dst = Mat3b(src.rows, src.cols, Vec3b(0, 0, 0));
    for (int r = 0; r < src.rows; ++r)
    {
        for (int c = 0; c < src.cols; ++c)
        {
            dst(r, c) = colormap(src(r, c));
        }
    }
}

---

请注意，递归实现对于标记来说不是一个好主意:

• 速度很慢
• 如果你的递归太深入，它可能会失败，即你的组件非常大

我建议使用另一种算法。这是(几乎)您的算法的迭代形式的实现。我强烈推荐这个而不是你的。可以简单地将其修改为将每个连接组件的点输出为 vector<vector<Point>> ，就像 cv::findContours会做:

int connected_components2(const Mat1b& img, Mat1i& labels)
{
    Mat1b src = img > 0;
    labels = Mat1i(img.rows, img.cols, 0);

    int label = 0;
    int w = src.cols;
    int h = src.rows;
    int i;

    cv::Point point;
    for (int y = 0; y<h; y++)
    {
        for (int x = 0; x<w; x++)
        {
            if ((src(y, x)) > 0)   // Seed found
            {
                std::stack<int, std::vector<int>> stack2;
                i = x + y*w;
                stack2.push(i);

                // Current component
                std::vector<cv::Point> comp;

                while (!stack2.empty())
                {
                    i = stack2.top();
                    stack2.pop();

                    int x2 = i%w;
                    int y2 = i / w;

                    src(y2, x2) = 0;

                    point.x = x2;
                    point.y = y2;
                    comp.push_back(point);

                    // 4 connected
                    if (x2 > 0 && (src(y2, x2 - 1) != 0))
                    {
                        stack2.push(i - 1);
                        src(y2, x2 - 1) = 0;
                    }
                    if (y2 > 0 && (src(y2 - 1, x2) != 0))
                    {
                        stack2.push(i - w);
                        src(y2 - 1, x2) = 0;
                    }
                    if (y2 < h - 1 && (src(y2 + 1, x2) != 0))
                    {
                        stack2.push(i + w);
                        src(y2 + 1, x2) = 0;
                    }
                    if (x2 < w - 1 && (src(y2, x2 + 1) != 0))
                    {
                        stack2.push(i + 1);
                        src(y2, x2 + 1) = 0;
                    }

                    // 8 connected
                    if (x2 > 0 && y2 > 0 && (src(y2 - 1, x2 - 1) != 0))
                    {
                        stack2.push(i - w - 1);
                        src(y2 - 1, x2 - 1) = 0;
                    }
                    if (x2 > 0 && y2 < h - 1 && (src(y2 + 1, x2 - 1) != 0))
                    {
                        stack2.push(i + w - 1);
                        src(y2 + 1, x2 - 1) = 0;
                    }
                    if (x2 < w - 1 && y2>0 && (src(y2 - 1, x2 + 1) != 0))
                    {
                        stack2.push(i - w + 1);
                        src(y2 - 1, x2 + 1) = 0;
                    }
                    if (x2 < w - 1 && y2 < h - 1 && (src(y2 + 1, x2 + 1) != 0))
                    {
                        stack2.push(i + w + 1);
                        src(y2 + 1, x2 + 1) = 0;
                    }
                }

                ++label;
                for (int k = 0; k <comp.size(); ++k)
                {
                    labels(comp[k]) = label;
                }
            }
        }
    }

    return label;
}