一、前言

为了挑战一下OpenCV的学习成果,最经一直在找各类项目进行实践。机缘巧合之下,得到了以下的需求:

要求从以下图片中找出所有的近似矩形的点并计数,重叠点需要拆分单独计数。

二、解题思路

1.图片作二值化处理

auto image = cv::imread("points.jpg");
cv::Mat border;
// 为了将图片边缘的点加入计算,将图片整体扩大十个单位
cv::copyMakeBorder(image, border, 10, 10, 10, 10, cv::BORDER_CONSTANT, cv::Scalar(255, 255, 255));

// 灰度化
cv::Mat gray;
cv::cvtColor(border, gray, cv::COLOR_BGR2GRAY);
//二值化
cv::Mat binary;
cv::threshold(gray, binary, 10, 255, cv::THRESH_BINARY);

得到以下结果:

2.腐蚀

可以看到二值化后多数点的形状残缺。会对轮廓查找造成影响,主要就是锯齿和空洞。为了解决这个问题,可以采用腐蚀方法,得到边缘较为光滑的点。

cv::Mat erosion;
cv::Mat kernel = cv::Mat(3, 3, CV_8UC1, cv::Scalar(1));
cv::erode(binary, erosion, kernel, cv::Point(-1, -1), 1) ; // 腐蚀

3.提取所有点的轮廓并计数

std::vector<cv::Mat>contours;
cv::findContours(erosion, contours, cv::RETR_TREE,cv::CHAIN_APPROX_SIMPLE) ;// 轮廓提取

用黄色笔迹绘制出所有的轮廓,如下图所示:

至此,基本能够得到点的数量了,前提是没有重叠点,直接获取contours的数量即可。当然重叠点的问题肯定要解决。接下来采用面积判断法解决该问题。

重叠部分探索

从图中我们可以看出,大部分独立点的面积是近似的,重叠点处的点数基本可以近似于重叠处的面积除以标准独立点的面积。此外,采用面积法也可以过滤一些面积较小的噪点。

1.标准独立点面积的获取

如何找到那个较为标准的点的面积呢?可以使用众数作为标准值。但由于点面积的离散性,不一定能够找到一个完美的众数。所以这里写了一个分组找中位数的方法来找这个标准值。

首先,计算出各个轮廓的面积,并过滤噪点,此处小于30的将视为噪点:

std::vector<double> listArea;
std::vector<cv::Mat> listContour;
std::vector<double> listLength;
auto count = contours.size();
for(int i = 1; i < count; i++)
{
    auto contour = contours[i];
    auto area = cv::contourArea(contour);
    if (area < 30)
        continue;
    listArea.push_back(area);
    listContour.push_back(contour);
    auto arcLen = cv::arcLength(contour, true);
    listLength.push_back(arcLen);
}

其次,将所有面积分组,分组个数等于总个数的平方根:

int groupByStep(const nc::NdArray<double> &nclt, QMap<double, QList<double>> &map)
{
    auto minV = nc::min(nclt)[0];
    auto maxV = nc::max(nclt)[0];
    auto range = maxV - minV;//极差
    auto count = nclt.size();
    auto group = sqrt(count);//分组数量
    int step =  range / group;//分组步长

    for(size_t i = 0; i < count;  i++)
    {
        auto v = nclt[i];
        auto key = (int)((v - minV) / step);
        map[key].push_back(v);
    }
    return group;
}

接着,找到数量最大的组的索引:

int findMaxCountIdx(QMap<double, QList<double>> &map)
{
    int maxIdx = 0;
    auto maxCount = 0;
    auto ks = map.keys();
    auto count = ks.size();
    for(int i = 0; i < count;  i++)
    {
        auto k = ks[i];
        auto vs = map.value(k);
        if(maxCount < vs.size())
        {
            maxCount = vs.size();
            maxIdx = i;
        }
        qDebug() << __FUNCTION__ << k << vs.size();
    }
    return maxIdx;
}

再者,以上一步的索引为起始点,逐步探求前后的索引组,直至索引组中点数大于总点数的一半:

/**
 * @brief accumulate 累加获取选中分组中点的总个数
 * @param idxs
 * @param vss
 * @return
 */
int accumulate(QList<int> &idxs,  QList < QList<double >> &vss)
{
    auto c = 0;
    foreach (auto idx, idxs)
    {
        c += vss[idx].size();
    }
    return c;
}
/**
 * @brief findMoreThanHalfIdxs 获取分组点数量和大于总点一半时的索引
 * @param idxs
 * @param count
 * @param vss
 */
void findMoreThanHalfIdxs(QList<int> &idxs, int count, QList < QList<double >> &vss)
{
    QList<int> idxsTmp = idxs;
    auto l = idxs.first() - 1;
    auto r = idxs.last() + 1;
    auto count_2 = count / 2;
    auto lb = false;
    auto rb = false;

    if(l > -1)
    {
        idxsTmp.insert(0, l);
        auto cnt = accumulate(idxsTmp, vss);
        if(cnt > count_2)
        {
            lb = true;
        }
    }
    if(r < count)
    {
        idxsTmp << r;
        auto cnt = accumulate(idxsTmp, vss);
        if(cnt > count_2)
        {
            rb = true;
        }
    }
    if(lb && rb)
    {
        auto lc = vss[l].size();
        auto rc = vss[r].size();
        if(lc > rc)
        {
            idxs.insert(0, l);
        }
        else
        {
            idxs << r;
        }
    }
    else if (lb)
    {
        idxs.insert(0, l);
    }
    else if (rb)
    {
        idxs << r;
    }
    else
    {
        idxs.insert(0, l);
        idxs << r;
        findMoreThanHalfIdxs(idxs, count, vss);
    }
}

最后,从索引组中找到中位数,即是我们要找的标准值:

/**
 * @brief majority 舍弃极值后再求中位数
 * @param lt
 * @return
 */
double majority(std::vector<double> &lt)
{
    if(!lt.size())return 0;
    auto count = lt.size();
    std::vector<double> sortLt = lt;
    std::sort(sortLt.begin(), sortLt.end(), std::less<double>());//排序
    auto nclt = nc::NdArray<double>(sortLt);
    QMap<double, QList<double>>map;//分组容器
    groupByStep(lt, map);
    auto idx = findMaxCountIdx(map);//个数最多的组的索引
    auto vss = map.values();
    QList<int> idxs{idx};
    findMoreThanHalfIdxs(idxs, count, vss);//以idx为起点,搜寻数量过半的索引
    QList<double> idxVs;//数量过半的值
    foreach (auto idx, idxs)
    {
        idxVs << vss[idx];
    }
    std::sort(idxVs.begin(), idxVs.end(), std::less<double>());//排序
    std::vector<double> idxVsStd;
    toStd(idxVs, idxVsStd);
    nclt = nc::NdArray<double>(idxVsStd);
    auto ret = nc::median(nclt)[0];//中位数
    return ret;
}

2.重叠处点个数的获取

在上一步,我们获取了标准面积auto stdArea = majority(listArea);。接下来只用作简单的除法运算就可以得到点的个数:

 auto countAlone = 0;
auto countLinked = 0;
count = listArea.size();
for(size_t i = 1; i < count; i++)
{
    auto area = listArea[i];
    auto contour = listContour[i];
    auto c = getRectCount(area, stdArea, contour);
    auto m = cv::moments(contour);
    auto cX = int(m.m10 / m.m00);
    auto cY = int(m.m01 / m.m00);
    cv::putText(border, QString::number(c).toStdString(), cv::Point(cX, cY),
                cv::FONT_HERSHEY_COMPLEX, 0.5, cv::Scalar(0, 100, 255), 1);
    auto rect = cv::minAreaRect(contour);
    if (c == 1)
        countAlone += c;
    else
        countLinked += c;
    cv::drawContours(border, listContour, i, cv::Scalar(0, 255, 255), 1);
    // 获取最小外接矩形的4个顶点坐标(ps: cv2.boxPoints(rect) for OpenCV 3.x)
    cv::Mat box;
    cv::boxPoints(rect, box);
    cv::Mat boxInt;
    box.convertTo(boxInt, CV_32S);
    cv::drawContours(border, std::vector<cv::Mat> {boxInt}, 0, cv::Scalar(255, 0, 0), 1);
}
cv::imshow("contoursImg", border);
cv::waitKey();

在以上的步骤中,我们得筛选出独立点,将他们排除在重叠点的个数计算之外。否则,独立点的个数大概率将被计算为:0.6、1.5、1.2…这样的值,会对最终结果产生极大的影响。独立点采用以下方法判断:

bool isOneRectPoint(double &area, cv::Mat &contour)
{
    auto rect = minAreaRect(contour);//最小外接矩形
    auto areaRect = rect.size.height * rect.size.width;//矩形面积
    auto scale = rect.size.height / rect.size.width;//矩形长宽比。假设矩形是正方形,该值接近1
    scale = std::abs(scale - 1);//为了直观判断,此处减1。假设矩形是正方形,那么该值接近0
    auto scaleArea = area / areaRect;//假设矩形是独立矩形,该值接近1
    scaleArea = std::abs(scaleArea - 1);//为了直观判断,此处减1。假设矩形是独立矩形,该值接近0
    return scale < 0.1 && scaleArea < 0.2;//两个判断都接近0,说明该矩形是个独立矩形
}

至于点个数,采用以下方法简单计算即可:

int getRectCount(double &area, double &stdArea, cv::Mat &contour)
{
    auto isRect = isOneRectPoint(area, contour);
    if (isRect)
        return 1;
    auto c = std::max(1.0, round(area / stdArea));
    return c;
}

三、总结

以上是个人对该问题的一些思考与实践。运用到了一些图像处理、几何、统计等相关的知识,此处既作为记录,也更加希望该方法对您有所帮助。困难点在于重叠处点个数的统计,本文采用面积法计算个数,是一种较为简单的方法。当然,如果有更加巧妙的方法,欢迎探讨交流。