目标融合之

理论基础：

       并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets也叫Union Find Sets）的合并及查询问题。常常在使用中以森林来表示。初始化时，每个元素都是一棵独立的树，合并过程中将具有某种关联关系的树进行合并，即指向规定的一个父节点，最后进行查找过程，判断2个节点是否属于同一个父亲节点，即2个节点是否有联系。

算法主要包括3个处理过程。

       （1）进行所有点集的初始化工作，该过程只需在最开始的时候执行一次即可，时间复杂度为O(N)。

       （2）查找节点中的所有元素，使用其根节点的父亲节点和其建立直接联系

       （3）将其中具有某些联系的元素进行合并，合并到相同的父亲根节点。

       算法整体流程图如下：

举个栗子

       初始化时，(2,4)，(5,7)，(1,3)，(8,9)， (1,2)，(5,6)， (2,3)为原始相关节点。在合并过程中，将两两有关系的进行合并操作。最终，(2,4) (1,2) (2,3)合并为{1,2,3,4}，(5,7) (5,6)合并为{5,6,7}，(8,9)没有进行合并，继续保存为{8,9}。

(2,4) {2,4}

(5,7) {2,4}{5,7}

(1,3) {1,3}{2,4} {5,7}

(8,9) {1,3}{2,4} {5,7} {8,9}

(1,2) {1,2,3,4}{5,7} {8,9}

(5,6) {1,2,3,4}{5,6,7} {8,9}

(2,3) {1,2,3,4}{5,6,7} {8,9}

应用背景：

       在人脸检测，模式识别等应用中，后续会产生许多的目标区域候选框，当然去掉这些候选框也有很多方法。而其中一种就是将满足某种关系的候选框进行合并，用一个大的候选框来代替之前的2个或者多个候选框。例如，opencv中自带的harrs，hog等就是用的这种方法进行后续处理的。这也就是本文要阐述的方法——并查集（Disjoint Sets）。

       当然上面所讲的只是传统的并查集的一种应用。而实际其应用领域还更广。比如，在视频处理领域，可以快速的实现移动目标物（车，行人，其他物体等）的捕捉。真正的实现让运动跟踪来辅助检测识别，让检测识别来指导跟踪，相辅相成，实现高效的智慧城市战略。

       这里贴一张应用的图片，图片右下角的一些信息，我已经擦掉。该图片为从视频中每隔一定帧数抽取的。其中蓝色为原始的候选框，红色为融合后的候选框。从融合效果可以看出基本满足多目标的完美捕捉和跟踪。

opencv源码：

[cpp] view plain copy

print?

1. template<typename _Tp, class _EqPredicate> int  
2. partition( const vector<_Tp>& _vec, vector<int>& labels,  
3.            _EqPredicate predicate=_EqPredicate())  
4. {  
5.     int i, j, N = (int)_vec.size();  
6.     const _Tp* vec = &_vec[0];  
7.   
8.     const int PARENT=0;  
9.     const int RANK=1;  
10.   
11.     vector<int> _nodes(N*2);  
12.     int (*nodes)[2] = (int(*)[2])&_nodes[0];  
13.   
14.     // The first O(N) pass: create N single-vertex trees  
15.     for(i = 0; i < N; i++)  
16.     {  
17.         nodes[i][PARENT]=-1;  
18.         nodes[i][RANK] = 0;  
19.     }  
20.   
21.     // The main O(N^2) pass: merge connected components  
22.     for( i = 0; i < N; i++ )  
23.     {  
24.         int root = i;  
25.   
26.         // find root  
27.         while( nodes[root][PARENT] >= 0 )  
28.             root = nodes[root][PARENT];  
29.   
30.         for( j = 0; j < N; j++ )  
31.         {  
32.             if( i == j || !predicate(vec[i], vec[j]))  
33.                 continue;  
34.             int root2 = j;  
35.   
36.             while( nodes[root2][PARENT] >= 0 )  
37.                 root2 = nodes[root2][PARENT];  
38.   
39.             if( root2 != root )  
40.             {  
41.                 // unite both trees  
42.                 int rank = nodes[root][RANK], rank2 = nodes[root2][RANK];  
43.                 if( rank > rank2 )  
44.                     nodes[root2][PARENT] = root;  
45.                 else  
46.                 {  
47.                     nodes[root][PARENT] = root2;  
48.                     nodes[root2][RANK] += rank == rank2;  
49.                     root = root2;  
50.                 }  
51.                 assert( nodes[root][PARENT] < 0 );  
52.   
53.                 int k = j, parent;  
54.   
55.                 // compress the path from node2 to root  
56.                 while( (parent = nodes[k][PARENT]) >= 0 )  
57.                 {  
58.                     nodes[k][PARENT] = root;  
59.                     k = parent;  
60.                 }  
61.   
62.                 // compress the path from node to root  
63.                 k = i;  
64.                 while( (parent = nodes[k][PARENT]) >= 0 )  
65.                 {  
66.                     nodes[k][PARENT] = root;  
67.                     k = parent;  
68.                 }  
69.             }  
70.         }  
71.     }  
72.   
73.     // Final O(N) pass: enumerate classes  
74.     labels.resize(N);  
75.     int nclasses = 0;  
76.   
77.     for( i = 0; i < N; i++ )  
78.     {  
79.         int root = i;  
80.         while( nodes[root][PARENT] >= 0 )  
81.             root = nodes[root][PARENT];  
82.         // re-use the rank as the class label  
83.         if( nodes[root][RANK] >= 0 )  
84.             nodes[root][RANK] = ~nclasses++;  
85.         labels[i] = ~nodes[root][RANK];  
86.     }  
87.   
88.     return nclasses;  
89. }  

程序解析：

为了验证本文并查集的融合效果，本文使用点的聚合（PointLike）和长方形框的融合（RectLike）进行双重验证。具体如下所示。

PointLike类，定义了partition需要的()重载操作以及聚合为一类后，相应的Disjoint_set_merge操作。

[cpp] view plain copy

print?

1. class PointLike  
2. {  
3. public:  
4.     int thresh;  
5. public:  
6.     PointLike();  
7.     PointLike(int thresh);  
8.     bool operator()(cv::Point p1,cv::Point p2);  
9.     int Disjoint_set_merge(vector<Point>pts,vector<int>& labels,PointLike rLike);  
10.       
11. };  
12.   
13. PointLike::PointLike()  
14. {  
15.     thresh=30;  
16. }  
17. PointLike::PointLike(int thresh)  
18. {  
19.     this->thresh = thresh;  
20. }  
21. bool PointLike::operator()(cv::Point p1,cv::Point p2)  
22. {  
23.     int x = p1.x - p2.x;  
24.     int y = p1.y - p2.y;  
25.     return x*x+y*y <=thresh*thresh;  
26. }  
27. int PointLike::Disjoint_set_merge(vector<Point>pts,vector<int>& labels,PointLike pLike)  
28. {   //并查集方法，实现了点集的合并  
29.     //pts为合并前的点，labels为点的标签，p为合并的置信度  
30.   
31.     int count = cv::partition(pts,labels,pLike);  
32.     return count;  
33.   
34. }  

PointLike的测试，主要实现在600*600的背景区域，随机产生50个位置的点，当点与点之间的距离小于50就聚合为一类。原始点用红色实心小圆点表示。聚合后的点，每一类用一个随机生成的颜色和空心圆表示，并在旁边附所属类别的数字说明。运行效果图如下图所示，随机生成的50个点被聚合为27个类。

[cpp] view plain copy

print?

1. int main()  
2. {  
3.     int image_width=600;  
4.     int image_height=600;  
5.     Mat image(image_height,image_width,CV_8UC3);  
6.     image.setTo(0);  
7.     int sample_num=50;  
8.     srand(time(0));//保证每次产生的随机数不一样   
9.     //PointLike的测试  
10.     PointLike pLike(50);  
11.     vector<int> labels;  
12.     vector<Point>pts;  
13.     for (size_t i=0;i<sample_num;i++)  
14.     {  
15.         pts.push_back(Point(rand()%image_width,rand()%image_height));  
16.     }  
17.   
18.     int count= pLike.Disjoint_set_merge(pts,labels, pLike);  
19.   
20.     for(size_t i = 0;i<pts.size();i++)  
21.     {  
22.         cv::circle(image,pts[i],2,Scalar(0,0,255),-1);  
23.     }  
24.       
25.     vector<Scalar> color;  
26.     for (size_t i=0;i<count;i++)  
27.         color.push_back(Scalar(rand()%255,rand()%255,rand()%255));  
28.     if (count!=labels.size())//说明有合并的  
29.     for(size_t i = 0;i<pts.size();i++)  
30.     {  
31.         cv::circle(image,pts[i],10,color[labels[i]]);  
32.         char text[100];  
33.         sprintf(text,"%d",labels[i]);  
34.         putText(image,text,pts[i],CV_FONT_HERSHEY_COMPLEX, 1,color[labels[i]] );  
35.     }  
36.   
37.     imshow("image",image);  
38.     cout<<"总区域"<<count<<endl;  
39.   
40.     waitKey(0);  
41.     return 0;  
42. }  

RectLike类的定义，每个变量程序都有说明，包含最核心的partition需要的重载()函数。

[cpp] view plain copy

print?

1. class  RectLike{  
2.   
3. public:  
4.     double p;//公共区域所占的百分比，超过该比例则合并  
5.     float start_x,start_y,end_x,end_y;//合并后公共区域的起始点  
6.     float w,h;//r1和r2公共区域的长，宽  
7.   
8. public:  
9.     RectLike();  
10.     RectLike(double p);  
11.     void overlap(Rect &r1,Rect &r2);  
12.     float overlap_area(Rect r1,Rect r2);//判断框出图像的重叠面积  
13.     bool operator()(cv::Rect r1,cv::Rect r2);  
14.     Rect merge(cv::Rect r1,cv::Rect r2);  
15.     int Disjoint_set_merge(vector<Rect> rects,vector<Rect>& merge_rects,vector<int>& labels,RectLike rLike);  
16.     //并查集方法，只现实了区域的合并  
17. };  
18.   
19. RectLike::RectLike()  
20. {  
21.     start_x=0;  
22.     end_x=0;  
23.     start_y=0;  
24.     end_y=0;  
25.     p=0.6;  
26. };  
27. RectLike::RectLike(double p)  
28. {this->p = p;}  
29. void RectLike:: overlap(Rect &r1,Rect &r2)  
30. {  
31.     this->end_x=max(r1.x+r1.width,r2.x+r2.width);  
32.     this->start_x=min(r1.x,r2.x);  
33.     this->end_y=max(r1.y+r1.height,r2.y+r2.height);  
34.     this->start_y=min(r1.y,r2.y);  
35.     this->w=r1.width+r2.width-(end_x-start_x);  
36.     this->h=r1.height+r2.height-(end_y-start_y);  
37. }  
38. float RectLike::overlap_area(Rect r1,Rect r2)  
39. {//判断框出图像的重叠面积  
40.     overlap(r1, r2);  
41.     if (w<=0||h<=0)  
42.         return 0;  
43.     else  
44.     {  
45.         float area=this->w*this->h;  
46.         return area;  
47.     }  
48. }  
49. bool RectLike::operator()(cv::Rect r1,cv::Rect r2)  
50. {  
51.     //方法1，opencv hog,Cascade使用的合并方法  
52.     double delta = p*(std::min(r1.width, r2.width) + std::min(r1.height, r2.height))*0.5;  
53.     return std::abs(r1.x - r2.x) <= delta &&  
54.         std::abs(r1.y - r2.y) <= delta &&  
55.         std::abs(r1.x + r1.width - r2.x - r2.width) <= delta &&  
56.         std::abs(r1.y + r1.height - r2.y - r2.height) <= delta;  
57.     //方法2，求面积的合并方法  
58.     int area1 = r1.area();  
59.     int area2 = r2.area();  
60.     int area = overlap_area(r1,r2);//相交Rect面积  
61.     return area1<area2?area>=p*area1:area>=p*area2;   
62.     //方法3，投影法  
63.     int xlap=40;int ylap=40;  
64.     int x1=r1.x,x2=r1.x+r1.width,x3=r2.x,x4=r2.x+r2.width;  
65.     int y1=r1.y,y2=r1.y+r1.height,y3=r2.y,y4=r2.y+r2.height;  
66.     if (x1<=x3)  
67.     {  
68.         if ((x2<=x3&&x3-x2<=xlap)||(x1<=x3&&x3<=x2&&x2<=x4)||(x1<=x3&&x3<=x4&&x4<=x2))  
69.         {  
70.             if ((y4<=y1&&y1-y4<=ylap)||(y2<=y3&&y3-y2<=ylap)||(y1<=y3&&y3<=min(y2,y4))||(y3<y1&&y1<=min(y2,y4)))  
71.             {  
72.                 return true;  
73.             }  
74.   
75.         }  
76.     }else  
77.     {  
78.         if ((x4<=x1&&x1-x4<=xlap)||(x3<=x1&&x1<=x4&&x4<=x2)||(x3<=x1&&x1<=x2&&x2<=x4))  
79.         {  
80.             if ((y2<=y3&&y3-y2<=ylap)||(y4<=y1&&y1-y4<=ylap)||(y3<=y1&&y1<=min(y4,y2))||(y1<y3&&y3<=min(y4,y2)))  
81.             {  
82.                 return true;  
83.             }  
84.         }  
85.     }  
86.     return false;  
87. }  
88. Rect RectLike::merge(cv::Rect r1,cv::Rect r2)  
89. {  
90.         overlap(r1, r2);  
91.         Rect rect(start_x,start_y,end_x-start_x,end_y-start_y);  
92.         return rect;  
93. }  
94. int RectLike::Disjoint_set_merge(vector<Rect> rects,vector<Rect>& merge_rects,vector<int>& labels,RectLike rLike)  
95. {   //并查集方法，只现实了区域的合并  
96.     //rects为合并前的矩形框，merge_rects为合并后矩形框，labels为矩形框的标签，p为合并的置信度  
97.     vector<int>label_temp;  
98.     for (size_t i=0;i<labels.size();i++)  
99.         label_temp.push_back(1);  
100.     int count = cv::partition(rects,labels,rLike);  
101.     //如果没有合并，还是返回原始的rects,labels，如果合并了，返回以0开始的labels  
102.     if (count!=labels.size())//两者不相等，说明进行了合并  
103.     {  
104.           
105.         for (size_t i=0;i<labels.size();i++)  
106.         {     
107.             if (label_temp[i]==0) continue;  
108.             Rect rect_temp=rects[i];  
109.             label_temp[i]=0;  
110.             for(size_t j=i+1;j<labels.size();j++)  
111.             {  
112.                 if(labels[i]==labels[j])  
113.                 {  
114.                     rect_temp=rLike.merge(rect_temp,rects[j]);  
115.                     label_temp[j]=0;  
116.                 }  
117.   
118.             }  
119.             merge_rects.push_back(rect_temp);  
120.         }  
121.   
122.     }  
123.     return count;  
124.   
125. }  

RectLike类的测试，由于()的实现采用了3种不同的方法，所以这里对三种实现的测试采样固定输入的数据进行测试。其中，黄色为原始框，红色为合并后的框。

       方法1，为opencv的源码，hog,Cascade等对于检测后窗口的合并就是用的该方法。思想为先定义一个delta，当两个矩形框左上角x的差，y的差，矩形框右下角x的差，y的差都小于该delta就进行合并。测试数据的3个矩形框，分别为(80,80,180,120),(130,130,180,120) ,(300,300,50,50)。

       方法2，为面积合并法，当相交的面积大于其中面积较小的矩形的面积*p，就将当前的2个矩形进行合并。测试数据的3个矩形框，分别为(80,80,180,120),(100,100,180,120) ,(300,300,50,50)。

       方法3，为投影法，当矩形框在x轴的投影小于xlap并且在y轴的投影小于ylap，就将这2个比较的框进行合并。测试数据的3个矩形框，分别为(80,80,180,120),(100,270,180,120) ,(300,300,50,50)。

[cpp] view plain copy

print?

1. int main()  
2. {  
3.     int image_width=600;  
4.     int image_height=600;  
5.     Mat image(image_height,image_width,CV_8UC3);  
6.     image.setTo(0);  
7.     int sample_num=5;  
8.     srand(time(0));//保证每次产生的随机数不一样   
9.   
10.     //RectLike的测试  
11.   
12.     vector<Rect> rects;  
13.     vector<Rect> merge_rects;  
14.     vector<int>labels;  
15.   
16.     for (size_t i=0;i<sample_num;i++)  
17.     {  
18.         int x=rand()%(image_width-10);  
19.         int y=rand()%(image_height-10);  
20.         int width=abs(rand()%(image_width-x-10));  
21.         int height=abs(rand()%(image_height-y-10));  
22.         rects.push_back(Rect(x,y,width,height));  
23.         labels.push_back(i);  
24.     }  
25.   
26.     RectLike rLike(0.4);  
27.     int count=rLike.Disjoint_set_merge( rects,merge_rects,labels,rLike);  
28.   
29.     for(size_t i = 0;i<rects.size();i++)  
30.     {  
31.         cv::rectangle(image,rects[i],Scalar(0,255,255),6);  
32.     }  
33.     for(size_t i = 0;i<merge_rects.size();i++)  
34.     {  
35.         cv::rectangle(image,merge_rects[i],Scalar(0,0,255),2);        
36.     }  
37.     imshow("image",image);  
38.     cout<<"总区域"<<count<<endl;  
39.   
40.     waitKey(0);  
41.     return 0;  
42. }  

本文程序的github下载链接为，https://github.com/watersink/Disjoint-Sets-Union-Find，最后希望本文会对您产生一些帮助。

PS:

对于Opencv中合并其实就是基于上面的模版类partition实现的。当然这个程序也写的很牛，直接用循环代替了递归，实现了很好的融合效果。在实际应用中，好多开源的国外大牛的程序其实都是自己实现的类似这样的功能，包括partition和后期的融合等。

       本人也自己写了一个融合的子函数。有些时候真的觉得思维是很重要的。刚开始也是想的递归，后来改成了下面的程序，该程序的巧妙之处就在于，后面只要有一个合并的，就对已经循环的Rect中标签没有排除的重新进行扫描，从而改变了递归策略。下面的这一个函数接口实现了上面所有的功能。

       通过将该函数接口和上文的RectLike融合中的方法3进行对比，两者实现了同样的融合效果。并且实际经过多段视频的测试，证明该函数的正确性。

       其中，boundRect 待合并的长方形框，boundRectFlag待合并长方形框的标志,和boundRect维度一样，初始化全部为1，MergeBoundRect合并后的框，xlap,x方向小于该值就合并，ylap，y方向小于该值就合并。

       合并的示意图如下:

[cpp] view plain copy

print?

1. void MergeContours(vector<Rect> boundRect,vector<int>& boundRectFlag,vector<Rect>& MergeBoundRect,int xlap=40,int ylap=40)  
2. {  
3.     for (int i=0;i<boundRect.size();i++)  
4.     {     
5.         if(boundRectFlag[i]==0)  
6.             continue;  
7.         Rect recttmp=boundRect[i];  
8.         boundRectFlag[i]=0;  
9.         for (int j=i+1;j<boundRect.size();j++)  
10.         {  
11.             if (boundRectFlag[j]!=0)  
12.             {  
13.                 int x1=recttmp.x,x2=recttmp.x+recttmp.width,x3=boundRect[j].x,x4=boundRect[j].x+boundRect[j].width;  
14.                 int y1=recttmp.y,y2=recttmp.y+recttmp.height,y3=boundRect[j].y,y4=boundRect[j].y+boundRect[j].height;  
15.                 if (x1<=x3)  
16.                 {  
17.                     if ((x2<=x3&&x3-x2<=xlap)||(x1<=x3&&x3<=x2&&x2<=x4)||(x1<=x3&&x3<=x4&&x4<=x2))  
18.                     {  
19.                         if ((y4<=y1&&y1-y4<=ylap)||(y2<=y3&&y3-y2<=ylap)||(y1<=y3&&y3<=min(y2,y4))||(y3<y1&&y1<=min(y2,y4)))  
20.                         {  
21.                             recttmp.x=min(x1,x3);recttmp.width=max(x2,x4)-min(x1,x3);  
22.                             recttmp.y=min(y1,y3);recttmp.height=max(y2,y4)-min(y1,y3);  
23.                             boundRectFlag[j]=0;  
24.                             j=i;  
25.                         }  
26.   
27.                     }  
28.                 }else  
29.                 {  
30.                     if ((x4<=x1&&x1-x4<=xlap)||(x3<=x1&&x1<=x4&&x4<=x2)||(x3<=x1&&x1<=x2&&x2<=x4))  
31.                     {  
32.                         if ((y2<=y3&&y3-y2<=ylap)||(y4<=y1&&y1-y4<=ylap)||(y3<=y1&&y1<=min(y4,y2))||(y1<y3&&y3<=min(y4,y2)))  
33.                         {  
34.                                                         recttmp.x=min(x3,x1);recttmp.width=max(x2,x4)-min(x3,x1);  
35.                             recttmp.y=min(y3,y1);recttmp.height=max(y4,y2)-min(y3,y1);  
36.                             boundRectFlag[j]=0;  
37.                             j=i;  
38.                         }  
39.                     }  
40.                 }  
41.             }  
42.   
43.   
44.         }  
45.         MergeBoundRect.push_back(recttmp);  
46.   
47.     }  
48. }