一种实用性较强的求IOU的算法（任意多边形之间的IOU）_多边形iou

PS：要转载请注明出处，本人版权所有。

PS: 这个只是基于《我自己》的理解，

如果和你的原则及想法相冲突，请谅解，勿喷。

环境说明

  无

前言

---

  提到IOU，如果接触过目标检测，应该是很熟悉的，这个东西简直就是标配了。但是我之前见到的求IOU都是求两个矩形的IOU，由于矩形的特殊性，其IOU可以很简单的求。

  突然有一天，我要求一个矩形和一个多边形的IOU，这就让我突然有点懵，参考原来求两个矩形的IOU方式，完全无解。经过了询问大佬以及网上冲浪后，在某不起眼的地方发现了一个思路，一个匿名网友貌似提供了一句MATLAB的代码，给了我不错的启发。

  因此本文用c++和opencv实现了这部分代码。下面将会从IOU概念，两矩形的IOU，以及任意多边形之间的IOU顺序进行讲解。

交并比（Intersection of Union，IOU）

---

  我们定义一个多边形的面积为Area0，另外一个多边形的面积为Area1。那么IOU的数学定义为$IOU=\frac{Are{a}_0\cap Are{a}_1}{Are{a}_0\cup Are{a}_1}$。

  下面我们用一个示例图清晰的表达这个概念：

  其中B类区域就是两个多边形的交集。IOU求的是B类区域在A,B,C类区域中的占比。注意这里是占比。

两个矩形之间的IOU求法

---

  两个矩形的IOU求法其实交简单，根据一些性质，我们可以直接求出交集区域的宽和高，然后直接得到交集面积即可，这些都是常规写法。详情见如下代码：

float IOU(const cv::Rect &r0, const cv::Rect &r1)
{

    if (r0.x > r1.x + r1.width) return 0.f;//top-x  r0 在r1右边
    if (r0.y > r1.y + r1.height) return 0.f;//top-y r0 在r1下边
    if (r0.x + r0.width < r1.x) return 0.f;//bottom-x r0 在r1左边
    if (r0.y + r0.height < r1.y) return 0.f;//bottom-y r0 在r1上边

    // 此时必定相交
    float _overlap_w = std::min(r0.x + r0.width, r1.x + r1.width) - std::max(r0.x, r1.x);//得到相交矩形w

    float _overlap_h = std::min(r0.y + r0.height, r1.y + r1.height) - std::max(r0.y, r1.y);//得到相交矩形h

    // maybe overflow
    return (_overlap_w * _overlap_h)/(float)((r0.width*r0.height) + (r1.width*r1.height));

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

  如上可知，可以直接根据相关面积，求出IOU。

两个多边形之间的IOU求法

---

  我们需要求两个多边形的IOU，这个时候我们根据两个矩形的思路想想，貌似不好弄。这个时候我们可以转变一下思路。

  我们首先肯定是知道两个多边形的最大外接矩形的，这个时候我们得到最大的外界矩形宽和高（注意，这里的宽和高一般是固定的，所以一般我们都不需要去求外接矩）。然后我们创建三个宽和高等于我们预设的一维矩阵M_A, M_B，M_C，并将其所有元素置为0。这个时候，我们分别将矩阵一用多边形P1来来填充M_A，在P1内的元素置为1，外的元素不变。对M_B用同样的方式去填充。这个时候我们去计算M_C，具体计算方法是将对应的M_A，M_B同一位置的元素相与后赋值给M_C(表达式为:$M_C(x,y)=M_A(x,y)\&M_B(x,y)$)。这个时候我们去统计M_A,M_B,M_C中1的个数，其实就得到了对应的面积（也可以叫做像素面积），这个时候我们就可以方便的求出IOU，值得注意的是opencv中提供了我们所需要的所有操作。

  下面我们用c++来实现以上的流程（注意，以下代码是实现的是N个多边形和M个多边形的IOU，若自己的需求不一样，请修改为对应的场景，代码是随手写的，未仔细验证，原理是这样的）。

float IoU(const std::vector<std::vector<cv::Point>> &poly_array0, const std::vector<std::vector<cv::Point>> &poly_array1, int max_w, int max_h){

        cv::Mat _poly0 = cv::Mat::zeros(max_h, max_w, CV_8UC1);
        cv::Mat _poly1 = cv::Mat::zeros(max_h, max_w, CV_8UC1);
        cv::Mat _result;

        std::vector<cv::Point *> _pts0;
        std::vector<int> _npts0;

        for(auto &_v:poly_array0){

                if (_v.size() < 3)//invalid poly
                        return -1.f;

                _pts0.push_back((cv::Point *)&_v[0]);
                _npts0.push_back((int)_v.size());
        }

        std::vector<cv::Point *> _pts1;
        std::vector<int> _npts1;
        for(auto &_v:poly_array1){

                if (_v.size() < 3)//invalid poly
                        return -1.f;

                _pts1.push_back((cv::Point *)&_v[0]);
                _npts1.push_back((int)_v.size());
        }
/*

void cv::fillPoly	(	Mat & 	img,
const Point ** 	pts,
const int * 	npts,
int 	ncontours,
const Scalar & 	color,
int 	lineType = LINE_8,
int 	shift = 0,
Point 	offset = Point() 
)	
*/
        cv::fillPoly(_poly0, (const cv::Point **)&_pts0[0], &_npts0[0], _npts0.size(), cv::Scalar(1));

        cv::fillPoly(_poly0, (const cv::Point **)&_pts1[0], &_npts1[0], _npts1.size(), cv::Scalar(1));

        cv::bitwise_and(_poly0, _poly1, _result);

        int _area0 = cv::countNonZero(_poly0);
        int _area1 = cv::countNonZero(_poly1);
        int _intersection_area = cv::countNonZero(_result);

        // float _iou = (float)_intersection_area/(float)(_area0 + _area1 - _intersection_area);
        float _iou = (float)_intersection_area/(float)_area1;

        return _iou;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

  通过如上代码，我们用opencv就实现了我们预想的效果。

后记

---

  注意，这里需要延伸一点，求IOU，我们一般是用交集除以并集，但是有些时候，可能我们会用交集除以其中一个集合。比如：一个小矩形，一个大多边形的iou，其实按照标准写法来看，iou的数值不处理的话，不是那么可爱的。

  其实这里的几种用法还可以延伸出来，比如算两个立方体的重合度等等。

参考文献

• https://docs.opencv.org/3.4/d6/d6e/group__imgproc__draw.html

PS: 请尊重原创，不喜勿喷。

PS: 要转载请注明出处，本人版权所有。

PS: 有问题请留言，看到后我会第一时间回复。