DetectMultiScale函数中合并检测框的策略

本文主要是介绍DetectMultiScale函数中合并检测框的策略，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

为什么要合并？

因为我们目标检测的目的是：

但是实际上只通过分类器检测出来是这样的结果：

所以需要进行检测框的合并。

在DetectMultiScale函数中，调用groupRectangle函数来进行检测框的合并，合并之前，首先需要解决怎样分组的问题，即解决使用什么样的原则把不同的检测框归为一组，该函数中的解决方案是计算了不同检测框之间的相似度。

相似度计算方法

该函数中使用SimilarRects来计算相似度，其方法为：

inline bool operator()(const Rect& r1, const Rect& r2) const{// delta为最小长宽的eps倍double delta = eps*(std::min(r1.width, r2.width) + std::min(r1.height, r2.height))*0.5;// 如果矩形的四个顶点的位置差别都小于delta，则表示相似的矩形return std::abs(r1.x - r2.x) <= delta &&std::abs(r1.y - r2.y) <= delta &&std::abs(r1.x + r1.width - r2.x - r2.width) <= delta &&std::abs(r1.y + r1.height - r2.y - r2.height) <= delta;}

合并流程

定义好窗口相似性函数后，就可以利用并查集合并窗口函数了，大致过程如下：

1. 调用Partiton方法进行窗口分组。在该方法中，首先建立Rect对象的并查集初始结构，然后遍历整个并查集，用SimilarRects::operator()判断每2个窗口相似性，若相似则将这2个窗口放入一个组；
2. 运行完步骤1后会出现几个相互间不相似的窗口的组，当组中的窗口数量小于阈值minNeighbors时，丢弃该组（认为这是零散分布的误检）；
3. 之后剩下若干组由大量重叠窗口组成的比较大的组，分别求每个组中的所有窗口位置的平均值作为最终检测结果，每个组中通过stage的最大值以及最大的权重作为最终合并后的检测框的stage和权重。

Partiton定义

Function: Splits an element set into equivalency classes.

C++:

 template<typename _Tp, class _EqPredicate> int partition(const vector<_Tp>& vec, vector<int>& labels, _EqPredicate predicate=_EqPredicate())

Parameters:

• vec – Set of elements stored as a vector.
• labels – Output vector of labels. It contains as many elements as vec. Each label labels[i] is a 0-based cluster index of vec[i] .
• predicate – Equivalence predicate (pointer to a boolean function of two arguments or an instance of the class that has the method bool operator()(const _Tp& a, const _Tp& b) ). The predicate returns true when the elements are certainly in the same class, and returns false if they may or may not be in the same class.

Description: The generic function partition implements an O(N^2) algorithm for splitting a set of N elements into one or more equivalency classes, as described in http://en.wikipedia.org/wiki/Disjoint-set_data_structure . The function returns the number of equivalency classes.

完整的groupRectangles函数代码解析：

//rectList：带组合的窗口，即作为输入又作为输出
//weights：通过分类器的stage数，一般不小于stage总数-4，也就是之前的rejectLevels
//levelWeights：通过上述stage数的输出权重，也就是通过的stage数的所有node之和，里面即包含left_val又right_val，同一个node只包含其中的一个
//groupThreshold：组合阈值，当没有输入rejectLevels的时候，当待合并的窗口数大于该阈值的时候才可能进行合并，否则放弃；当输入rejectLevels的时候，当前组合下通过检测的stage最大值数大于该阈值的时候才可能进行合并，否则放弃
//eps：待合并的两个窗口的相关性，从矩形所在位置的像素差值考虑，当eps为0的时候不进行合并，直接返回
void groupRectangles(vector<Rect>& rectList, int groupThreshold, double eps, vector<int>* weights, vector<double>* levelWeights)
{if( groupThreshold <= 0 || rectList.empty() ) //判断minNeibors<=0{if( weights )   //如果要输出rejrejectLevels，则令所有的level都为1{size_t i, sz = rectList.size();weights->resize(sz);for( i = 0; i < sz; i++ )(*weights)[i] = 1;}return;}vector<int> labels;//调用partition函数对rectList中的矩形进行分类,nclasses表示组合类别数,有个参数eps是相关性，labels表示每个rect属于哪个类别的int nclasses = partition(rectList, labels, SimilarRects(eps));//存放每一类最后得到的矩形框的vector<Rect> rrects(nclasses);//记录同一类中检测框的个数vector<int> rweights(nclasses, 0);//保存每个类中stage的最大值以及最大权重vector<int> rejectLevels(nclasses, 0);vector<double> rejectWeights(nclasses, DBL_MIN);//DBL_MIN:min positive valueint i, j, nlabels = (int)labels.size();//组合分到同一类别的矩形并保存当前类别下通过stage的最大值以及最大的权重for( i = 0; i < nlabels; i++ ){int cls = labels[i];rrects[cls].x += rectList[i].x;rrects[cls].y += rectList[i].y;rrects[cls].width += rectList[i].width;rrects[cls].height += rectList[i].height;rweights[cls]++;}if ( levelWeights && weights && !weights->empty() && !levelWeights->empty() ){for( i = 0; i < nlabels; i++ ){int cls = labels[i];if( (*weights)[i] > rejectLevels[cls] ) //得到最大stage{rejectLevels[cls] = (*weights)[i];rejectWeights[cls] = (*levelWeights)[i];}else if( ( (*weights)[i] == rejectLevels[cls] ) && ( (*levelWeights)[i] > rejectWeights[cls] ) )rejectWeights[cls] = (*levelWeights)[i]; //得到最大权重}}//组合矩形的方法是去同一类矩形的平均值for( i = 0; i < nclasses; i++ ){Rect r = rrects[i];float s = 1.f/rweights[i];rrects[i] = Rect(saturate_cast<int>(r.x*s),saturate_cast<int>(r.y*s),saturate_cast<int>(r.width*s),saturate_cast<int>(r.height*s));}rectList.clear();if( weights )weights->clear();if( levelWeights )levelWeights->clear();//根据上述合并规则，以及是否存在包含关系输出合并后的矩形for( i = 0; i < nclasses; i++ ){Rect r1 = rrects[i];int n1 = levelWeights ? rejectLevels[i] : rweights[i];double w1 = rejectWeights[i];//这里就是minNeibor起作用的地方if( n1 <= groupThreshold )continue;// filter out small rectangles inside large rectanglesfor( j = 0; j < nclasses; j++ ){int n2 = rweights[j];if( j == i || n2 <= groupThreshold )continue;Rect r2 = rrects[j];//这里好像是用来防止数据溢出的，但是不懂为什么要这么操作int dx = saturate_cast<int>( r2.width * eps );int dy = saturate_cast<int>( r2.height * eps );//前四个判断r1和r2是不是包含关系if( i != j &&r1.x >= r2.x - dx &&r1.y >= r2.y - dy &&r1.x + r1.width <= r2.x + r2.width + dx &&r1.y + r1.height <= r2.y + r2.height + dy &&(n2 > std::max(3, n1) || n1 < 3) )break;}//不存在包含关系的时候，输出合并后的框if( j == nclasses ){rectList.push_back(r1);if( weights )weights->push_back(n1);if( levelWeights )levelWeights->push_back(w1);}}
}

后续工作

通过以上合并流程后并不能完全达到预期的效果，很有可能会出现以下效果：

所以对合并代码做了针对性的修改，在一定程度上减少了上述情况。

参考资料

1. OpenCV中的Haar+Adaboost（四）：利用并查集合并检测结果窗口
2. 并查集详解

这篇关于DetectMultiScale函数中合并检测框的策略的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---