非自交任意多边形与矩形框的交集面积计算方法

非自交任意多边形与矩形框的交集面积计算方法

1、应用背景

  在对象识别的AI计算时,有时需要限定检测区域,即目标对象落在限定区域内有效,在区域外忽略。
  转换为数学模型为:目标检测框与限定区域(非自交多边形)的交集面积除以目标检测框面积(类似于IOU值),超过门限(如50%),判定为在限定区域内。
  整个问题归结为计算目标检测框与限定区域的交集面积。
  多边形用顶点列表表示:点集P={pi|i=0,1,...,n-1},为顺序的n个点,n>=3,则多边形为:p0->p1->...->pn-1->p0。对于点p(i),p(i-1)表示前一个点,p(i+1)表示后一个点。本文下面涉及到p(i),如果i小于0,则i=(i+n) % n。
  约定输入多边形为非自交的,所谓自交,如ABCD是正常矩形,则ABDC就是自交的。
  限定区域,可以表示为多个多边形的列表(本算法要求限定区域的多边形之间的交集为空,否则需要计算凸多边形之间的交集)。

2、算法步骤

2.1、先计算多边形的方向,是顺时针,还是逆时针。

  图像坐标,X轴方向从左到右,Y轴方向从上到下。顺时针为1,逆时针为-1。
  搜索多变形最左侧点,如果最左侧点有多个,取左侧最下面的点。不妨设该点为p1,对应下标为k,计算点p的叉乘。p0表示p1的前一点,p2表示p1的后一点。
  即向量p0p1与向量p1p2的叉乘:cross_product = (p1.x-p0.x)(p2.y-p1.y) - (p1.y-p0.y)(p2.x-p1.x)
  如果cross_product>0,为顺时针;cross_product<0,则逆时针;cross_product=0,为平行线,即p0,p1,p2三点共线,但p1的取法已确保三点不共线,除非多边形所有点都在一垂直线上,这种情况可以报错处理。
  这样得到的多边形的方向:clockwise值:顺时针为1,逆时针为-1。

2.2、处理凹多边形

  检测多边形的凸性,如果为凹多边形,则切分为多个凸多边形;如果为凸多边形,则返回。
  对于多边形P,逐点计算叉乘,如果cross_product*clockwise 小于等于 0,则认为是凹点,表示多边形为凹多边形。
  针对第一个凹点p(i),从p(i-2)开始反向扫描,检测向量p(i-1)p(i)与向量p(i)p(k)的叉乘,k=i-2,...0,1,..i+1-n,取得反向扫描的第一个凹点p(c-1)的之后一点p(c),即表示最大的凸多边形。切分p(c),...p(i)为新的多边形P1,p(i)p(c)连线为切分线,p(i)、p(c)及余下的点组成剩余多边形P2。
  对于切分得到的多边形P1和P2,递归使用本算法,直到所有多边形都是凸多边形。
  算法的效果图如下:
非自交任意多边形与矩形框的交集面积计算方法
非自交任意多边形与矩形框的交集面积计算方法

2.3、计算所有凸多边形的外接矩形

  针对已得到的凸多边形列表,逐个计算外接矩形。得到外接矩形列表:outBoundRectangeList。外接矩形与凸多边形一一对应。
  使用外接矩形,可以简化后续处理。

2.4、计算外接矩形与目标检测框的交集

  目标检测框为矩形,外接矩形与目标检测框的交集,结果为矩形或空集。如果为空集,表示凸多边形与目标检测框无交,如果交集非空,则进入下一步处理。

2.5、计算交集矩形与凸多边形的交集多边形

  以交集矩形的4条边线所在直线,分别计算直线与凸多边形的交点,按上边线、右边线、下边线、左边线次序。根据交集矩形的生成方法,各边线与凸多边形必然都有交点,如果交点为多边形顶点,则进一步判断顶点的2条边的邻接点是否在边线的同一侧,如果为同一侧,则该顶点算两个点。如果2个邻接点在边线的两侧或有一边在边线上,则计为一个点。这样,每条边线与凸多边形的交点都是两个。
  对于上边的两个交点,y轴的值为rcy1,设x轴的值分别为x1和x2,交集矩形的上边端点x轴值为rcx1和rcx2,则上边线段的交集线段:
  v1=max(rcx1,min(x1,x2))
  v2=min(rcx2,max(x1,x2))
  如果v1>v2,表示线段无交集;如果v1==v2,表示一个交点;如果v1小于v2,则交集上边线段端点(v1,​rxy1)和(v2,​rxy1)。将交点加入交集多边形中,添加顺序,按顺时针次序方向加入,无交集则不加。
  类似方法处理右边线,下边线,左边线。
  最后得到:交集矩形与凸多边形的交集多边形,可能的形状如下:
非自交任意多边形与矩形框的交集面积计算方法

2.6、计算交集多边形面积

  交集多边形为凸多边形,因此面积计算可使用三角形方法,以p0点为固定点,依次取p(i-1)和p(i),i=2,..,n-1,得到三角形列表。
  三角形的面积计算,假设三点分别为p1=(x1,y1),p2=(x2,y2),p3=(x3,y3),则三角形面积为:
  S=(x1y2-x2y1+x3y1-x1y3+x2y3-x3y2)/2=[x1(y2-y3)-x2(y1-y3)+x3(y1-y2)]/2,这个公式可使用行列式表示:

[S=left| begin{array}{cccc} x1 & y1 & 1 \ x2 & y2 & 1 \ x3 & y3 & 1 end{array} right| * 1/2 ]

  利用三角形坐标计算面积的公式推导如下:
  如下图的三角形:
非自交任意多边形与矩形框的交集面积计算方法
  三角形面积等于外接矩形框面积减去三个着色的三角形面积,图像坐标Y轴从上到下,即:
  S=(x2-x3)(y3-y1)-((x2-x1)(y2-y1)+(x2-x3)(y3-y2)+(x1-x3)(y3-y1))/2
  整理后,即可得到之前的三角形面积公式。
  累加交集多边形的所有三角形的面积,得到一个交集多边形的面积。

2.7、计算凸多边形与目标检测框的交集多边形面积

  累加所有凸多边形与目标检测框的交集多边形面积。效果图如下:
非自交任意多边形与矩形框的交集面积计算方法

发表评论

相关文章