C++实现查找图像目标轮廓时间复杂度比findContour小的一种算法以及原理和代码

一种比findContour时间复杂度更小的图像目标轮廓查找算法是Suzuki和Abe提出的连通域标记算法。该算法的原理是对二值化图像中的每个像素进行扫描，找到连通区域并进行标记，最终得到目标轮廓。

该算法的时间复杂度为O(N)，其中N为像素数目。相比之下，findContour算法的时间复杂度为O(NlogN)。

以下是C++代码实现：

void findContours(const Mat& binaryImg, vector<vector<Point>>& contours, vector<Vec4i>& hierarchy)
{
    contours.clear();
    hierarchy.clear();

    int rows = binaryImg.rows;
    int cols = binaryImg.cols;

    Mat label(rows, cols, CV_32SC1, Scalar(0)); // 用于标记每个像素是否已经被扫描过
    int labelNum = 1; // 连通区域的标记数

    // 第一遍扫描，标记连通区域
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (binaryImg.at<uchar>(i, j) == 0) { // 如果当前像素为背景
                label.at<int>(i, j) = -1; // 标记为已扫描过
                continue;
            }
            if (label.at<int>(i, j) != 0) { // 如果当前像素已经被扫描过
                continue;
            }
            queue<Point> q;
            q.push(Point(j, i));
            label.at<int>(i, j) = labelNum;
            while (!q.empty()) {
                Point p = q.front();
                q.pop();
                int x = p.x;
                int y = p.y;
                if (x > 0 && binaryImg.at<uchar>(y, x - 1) != 0 && label.at<int>(y, x - 1) == 0) { // 左边像素
                    q.push(Point(x - 1, y));
                    label.at<int>(y, x - 1) = labelNum;
                }
                if (x < cols - 1 && binaryImg.at<uchar>(y, x + 1) != 0 && label.at<int>(y, x + 1) == 0) { // 右边像素
                    q.push(Point(x + 1, y));
                    label.at<int>(y, x + 1) = labelNum;
                }
                if (y > 0 && binaryImg.at<uchar>(y - 1, x) != 0 && label.at<int>(y - 1, x) == 0) { // 上边像素
                    q.push(Point(x, y - 1));
                    label.at<int>(y - 1, x) = labelNum;
                }
                if (y < rows - 1 && binaryImg.at<uchar>(y + 1, x) != 0 && label.at<int>(y + 1, x) == 0) { // 下边像素
                    q.push(Point(x, y + 1));
                    label.at<int>(y + 1, x) = labelNum;
                }
            }
            labelNum++;
        }
    }

    // 第二遍扫描，得到轮廓
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            int l = label.at<int>(i, j);
            if (l <= 0) {
                continue;
            }
            if (i > 0 && label.at<int>(i - 1, j) != l) { // 上边像素
                contours[l - 1].push_back(Point(j, i));
            }
            else if (i == 0) {
                contours[l - 1].push_back(Point(j, i));
            }
            if (i < rows - 1 && label.at<int>(i + 1, j) != l) { // 下边像素
                contours[l - 1].push_back(Point(j, i + 1));
            }
            else if (i == rows - 1) {
                contours[l - 1].push_back(Point(j, i + 1));
            }
            if (j > 0 && label.at<int>(i, j - 1) != l) { // 左边像素
                contours[l - 1].push_back(Point(j - 1, i));
            }
            else if (j == 0) {
                contours[l - 1].push_back(Point(j - 1, i));
            }
            if (j < cols - 1 && label.at<int>(i, j + 1) != l) { // 右边像素
                contours[l - 1].push_back(Point(j + 1, i));
            }
            else if (j == cols - 1) {
                contours[l - 1].push_back(Point(j + 1, i));
            }
        }
    }

    // 得到轮廓的层级关系
    hierarchy.resize(labelNum - 1);
    for (int i = 0; i < contours.size(); i++) {
        int parent = -1;
        for (int j = 0; j < contours[i].size(); j++) {
            Point p = contours[i][j];
            int l = label.at<int>(p.y, p.x);
            if (l != i + 1) {
                if (parent == -1 || label.at<int>(p.y, p.x) == parent + 1) {
                    parent = l - 1;
                }
            }
        }
        hierarchy[i][3] = parent;
    }
}
``