多边形区域掩码与其轮廓线间的转换

发表于 分类于 评论数： 阅读数： 本文字数： 3.2k 阅读时长 ≈ 8 分钟

在图像语义分割、实例分割中最终的目标轮廓通常有两种表示方法：将轮廓的边界通过一系列点表示成一个闭合的多边形，或者直接把最终图像的每一个像素点都分好类别，形成一个区域掩码的形式。两种表示方法各自有各自的优缺点，所以本文简单整理了一下这两种方法相互转化的算法。

边界转换成掩码

扫描线填充算法

扫描线有序边表算法是计算机图形学中填充的常用算法，从上到下，对图像/数组进行扫描，求出每条扫描线与边界的交点，利用一条线与多边形的边有偶数个交点的性质，对每条线的交点进行排序配对，然后把中间区段填充。

python转换计算代码

这部分转换方法可以利用skimage库提供的polygon函数（具体的实现与扫描线不完全相同，只是利用扫描线与多边形边界的交点个数，在多边形内有奇数个交点，多边形外有偶数个交点，对每一个点进行判定）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
>>> from skimage.draw import polygon
>>> img = np.zeros((10, 10), dtype=np.uint8)
>>> r = np.array([1, 2, 8])
>>> c = np.array([1, 7, 4])
>>> rr, cc = polygon(r, c)
>>> img[rr, cc] = 1
>>> img
array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 1, 1, 1, 1, 1, 1, 0, 0],
       [0, 0, 1, 1, 1, 1, 1, 0, 0, 0],
       [0, 0, 0, 1, 1, 1, 1, 0, 0, 0],
       [0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
       [0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
       [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], dtype=uint8)

掩码转换成边界

The Teh-Chin chain 逼近算法1

一些背景概念

在介绍算法之前，我们先说明一些原论文中使用的定义。原论文中，灰度值为0和1的像素分别称为0像素(0-pixel)和1像素(1-pixel)，由0像素组成的连通域称为0连通域(0-component)，由1像素组成的连通域称为1连通域(1-component)，另外假设空白区域是由0像素来填充的。

4连通：两个像素p和q，如果q在p的4邻域中，称这两个像素是4连通

8连通：两个像素p和q，如果q在p的8邻域中，称这两个像素是8连通

光栅扫描（RasterSCan）：是指从左往右，由上往下，先扫描完一行，再移至下一行起始位置继续扫描。

边界起始点：分为外边界起始点（图2a）和孔边界（图2b），如果两种关系都满足，记为第一种外边界开始点。

NBD是边界的编号，每个边界都有着自己唯一的编号，在光栅扫描过程中，经常需要用到上一个边界的编号，记为LNBD。

算法实现细节

轮廓提取的核心思路就是不断逆时针旋转找下一个点并更新当前点的位置以及像素值。具体操作如下，将初始NBD设置为1（最外圈边界看作第一个轮廓），使用光栅扫描法扫描图像，直到某个像素点的灰度值不为0时执行下列步骤。注意当扫描一个新行时，要将LNBD重置成1。

  1. 依次判断下列情形：

    1. 如图2a的情形，同时，那么(i, j)是外边界开始点，将NBD的值加一，
    2. 如图2b的情形，同时，那么(i,j)是孔边界的起始点，将NBD的值加一，，另外如果，那么
    3. 其他情况，跳到第4步

  2. 根据上一个边界B'和当前遇到的新边界B的类型，我们可以利用表1得到当前边界的父边界

  3. 利用得到的边界起始点开始边界追踪

    1. 以(i, j)为中心，从(i2, j2)开始顺时针查找中心点(i,j)的4(8)邻域中的非零像素点，将第一个非零像素点记为，如果没有找到那么将赋值为-NBD，然后跳转到第四步。
    2. ，
    3. 以为中心逆时针找到第一个非零点
    4. 根据的信息修改的值
      1. 如果（不在当前边界轮廓内），那么
      2. 如果而且，那么
      3. 其他情况不修改值
    5. 如果并且，那么就代表着回到了边界的起始点，跳到第4步。否则，，跳到3.3循环下去。

  4. 如果，则，从(i, j+1)继续扫描直到最右下角的点。

以上就是Teh-Chin chain逼近算法的主要流程，其实原论文中还有第二个算法，专门用来提取最外一层边界（忽略内部孔洞），整个算法的流程和前面类似只是微调了几个小地方。

  1. 边界起始点满足图2a的情形并且
  2. 标记测率与算法1相同，只是NBD和-NBD中“2”和“-2"被取代掉了
  3. 光栅扫描中一直保持LNBD对应最近的一个边界，当扫描到一个新行时，将LNBD记为0。

python转换计算代码

如果只是需要转换的计算结果，我们可以借助opencv的findContours函数，直接调用不需要考虑太多细节，具体输入参数可以参考文档，下面是一个简单示例

1
2
import cv2
contours, hierarchy = cv2.findContours(instance.pred_masks.numpy().squeeze().astype(np.uint8), mode=cv2.RETR_CCOMP, method=cv2.CHAIN_APPROX_TC89_KCOS)

其中contours会返回边界的顶点列表，hierarchy是每个轮廓的拓扑属性，输入参数中，mode是最终边界轮廓的类型，主要区别在于嵌套复杂边界的处理时多层嵌套边界的拓扑结构编号方法，包括只取最外一层边界（cv2.RETR_EXTERNAL）、全部不编号（cv2.RETR_LIST）、按照嵌套的奇偶性二分类（cv2.RETR_CCOMP）以及从外至内每一层一个编号（cv2.RETR_TREE）。method是识别边界的方法，也即包括Teh-Chin chain 算法在其中的几种算法。

  1. Satoshi Suzuki, KeiichiA be, Topological structural analysis of digitized binary images by border following, Computer Vision, Graphics, and Image Processing, Volume 30, Issue 1, 1985, Pages 32-46, ISSN 0734-189X, https://doi.org/10.1016/0734-189X(85)90016-7. (https://www.sciencedirect.com/science/article/pii/0734189X85900167)↩