基于Python实现图像分割算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了基于Python实现图像分割算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

资源下载地址：https://download.csdn.net/download/sheziqiong/86763995
资源下载地址：https://download.csdn.net/download/sheziqiong/86763995文章来源地址https://www.toymoban.com/news/detail-447689.html

1. 问题描述

结合“Lecture 7 Segmentation”内容及参考文献[1]，实现基于 Graph-based image segmentation 方法（可以参考开源代码，建议自己实现），通过设定恰当的阈值将每张图分割为 50~70 个区域，同时修改算法要求任一分割区域的像素个数不能少于 50 个（即面积太小的区域需与周围相近区域合并）。结合GT 中给定的前景 mask，将每一个分割区域标记为前景（区域 50%以上的像素
在 GT 中标为 255）或背景（50%以上的像素被标为 0）。区域标记的意思为将该区域内所有像素置为 0 或 255。要求对测试图像子集生成相应处理图像的前景标注并计算生成的前景 mask 和 GT 前景 mask 的 IOU 比例。假设生成的前景区域为 R1，该图像的 GT 前景区域为 R2，则IOU = (𝑅1∩𝑅2)/(𝑅1∪𝑅2)

2. 求解过程与算法

假设有无向图 $G = (V, E)$ ，每条边有权重 $w(v_i,v_j)$ 表示距离， $S$ 是原图的子图，有： $S=G'=(V,E')\quad E'\sub E$ ，且将 $G$ 分到成了不同的集群。使用谓词 $D$ 决定是否存在分段边界，也就是说，使用 $D$ 作为标准判断不同集群的相似性，如果两个集群的集群间相似性小于集群内的相似性，则进行合并：
$Merge(C_1,C_2)=\left\{\begin{matrix} True,dif(C_1,C_2)<in(C_1,C_2)\\ False,otherwise \end{matrix}\right.\\ dif(C_1,C_2)=\min_{v_i\in C_1,v_j\in C_2,(C_1,C_2)\in E}w(v_i,v_j)\\ in(C_1,C_2)=\min_{C\in\{C_1,C_2\}}[\max_{v_i,v_j\in C}[w(v_i,v_j)+\frac k{|C|}]]$
也就是说，如果两个集群中点的距离的最小值小于两个集群内的点的距离最大值更小的那一个则进行合并。其中 $k /∣ C ∣$ 设置了内部节点的差异性。如果 $k$ 较大，则集群规模往往更大，否则更小。

对于一张图像，我们可以将每个像素投影到特征空间 $(x, y, r, g, b)$ 上，也就是坐标和颜色通道组成的特征空间。每个像素在八领域内与八个像素相邻，即具有边。边的距离由特征向量计算得出，一般用欧氏距离。

由此，我实现基于图的图像分割方法流程如下：

将图片的每个像素按照坐标和颜色投影到 $(x, y, r, g, b)$ 特征空间上，初始时每个像素自身属于单独一个区域
计算所有边的权重大小，即八领域内像素的特征向量的欧式距离，并按照距离大小排序
按距离从小到大的顺序，依次将这些边两端的像素合并到同一个区域。能否合并依据上述的 $Merge(C_1,C_2)$ 的公式判断
重复第3步，直到剩余区域数到达设置的下界
遍历剩下的区域，将像素数少于50个的区域和相邻的区域直接合并

由此就能得到划分好区域的图片。我们只需要记录每个区域所含的全部像素的坐标，由这些坐标找到前景图的相应位置，统计前景像素数和背景像素数就能确定该区域应该被判定为前景还是背景。

3. 代码实现与说明

该部分的代码全部由自己实现。

3.1 一些功能模块的实现

在实现算法主体流程前，可以预见到，程序需要用多种方式刻画像素和像素、像素和区域之间的关系。为了之后代码的简洁性，我先实现了部分功能模块方便多次调用。首先需要两个全局变量：

# 用于查询某个片段内部的所有像素
SEG_GROUP = dict()
# 每个片段内的最大距离
INNER_WEIGHT = dict()

其中SEG_GROUP是字典，用于表示区域以及查询区域内的全部像素。如果像素坐标为[x,y]，则表示某个区域时，使用该区域中所有像素的x值最小的那个作为“代表”表示该区域。如果有多个x相同的像素，则找y值最小的。因此，SEG_GROUP[(x1,y1)]=[(x1,y1),(x2,y2),...]表示以(x1,y1)这个像素点为代表的区域中包含着(x1,y1)、(x2,y2)…这些像素点。该区域的键值只能用(x1,y1)表示，而不能用(x2,y2)等其他的像素点表示。因此SEG_GROUP的键值数量就表示了区域的数量。初始化时，该字典中包含所有像素坐标，且每个像素坐标对应的区域中只含有自己这一个像素。

而每个集合中需要计算集合内部的最大距离，即上述的 $in(C_1,C_2)$ 中的 $max(w(v_i,v_j))$ ，该值用INNER_WEIGHT表示，其键值也和上述的一样，用该区域的坐标最小的像素表示。实际的 $in(C_1,C_2)$ 通过下面的函数实现：

# 计算两个片段的片段内距离
def internalDif(coord1, coord2, img_array, segment_coord):
    global INNER_WEIGHT, SEG_GROUP
    coord1 = getSegment(coord1, segment_coord)
    coord2 = getSegment(coord2, segment_coord)
    k = 100
    dist1 = INNER_WEIGHT[(coord1[0],coord1[1])] + k/len(SEG_GROUP[(coord1[0],coord1[1])])
    dist2 = INNER_WEIGHT[(coord2[0],coord2[1])] + k/len(SEG_GROUP[(coord2[0],coord2[1])])
    return min(dist1, dist2)

上述关系描述了如何用一个“代表像素”找到其对应的区域，然后区域就能用SEG_GROUP来查询该区域中所有的像素了。然而这只能由区域查询到像素，并不能直接知道某个像素属于哪个区域，因此我们还需要另一个字典segment_coord表示像素的所属区域。segment_coord[(x1,y1)]=(x2,y2)表示像素(x1,y1)的区域和(x2,y2)相同。每个像素的segment_coord初始化为自己，当两个区域合并时，只需要将一个区域的代表像素的segment_coord指向另一个区域的任一像素即可。这样一来，对于合并的两个区域，总有一个区域的代表像素是不变的，因此其segment_coord值总是指向自身。如此一来，当一个像素满足segment_coord[(xi,yi)]=(xi,yi)时，我们就能知道：该像素为代表像素，从而找到了该区域。如果不是，则可以查询上一个像素的segment_coord，直到键值和所指向的值相同。通过上述的合并规则不难发现，像素查询其实是一个树状结构，我们总能通过segment_coord查询到一个像素所在区域的代表像素，即：

# 查询一个像素所属的区域
def getSegment(coord, segment_coord):
    coord = np.array(coord)
    tmp = coord.copy()
    # 一直向上查询，直到找到代表像素
    while (segment_coord[coord[0]][coord[1]] != coord).any():
        coord = segment_coord[coord[0]][coord[1]]
    # 直接将上一个像素指向代表像素以加速之后查找
    segment_coord[tmp[0]][tmp[1]] = coord   
    return np.array((coord[0], coord[1]))

合并的代码如下，需要提供合并的两个区域分别的任一像素。flag用于控制是否更新区域内最大距离。在合并不足50个像素的区域时，因为之后不需要用到区域内最大距离，因此不进行计算，可以进行一定的加速。

# 合并两个区域
def mergeSegment(coord1, coord2, img_array, segment_coord, flag=True):
    global INNER_WEIGHT, SEG_GROUP
    # 查询这两个像素所在区域的代表像素
    coord1 = getSegment(coord1, segment_coord)
    coord2 = getSegment(coord2, segment_coord)
    # 更新区域代表
    segment_coord[coord2[0]][coord2[1]] = coord1
    # 更新区域内部最大距离
    if flag:
        if (coord2[0],coord2[1]) in INNER_WEIGHT.keys():
            del INNER_WEIGHT[(coord2[0],coord2[1])]
        for vi in SEG_GROUP[(coord1[0],coord1[1])]:
            for vj in SEG_GROUP[(coord2[0],coord2[1])]:
                tmp = distance(vi,vj,img_array)
                if tmp > INNER_WEIGHT[(coord1[0],coord1[1])]:
                    INNER_WEIGHT[(coord1[0],coord1[1])] = tmp
    # 合并区域，删除原来的区域
    SEG_GROUP[(coord1[0],coord1[1])] += SEG_GROUP[(coord2[0],coord2[1])]
    del SEG_GROUP[(coord2[0],coord2[1])]
    return

有了上述操作后，我们可以通过查询两个像素所属区域的代表像素，通过二者的代表像素是否相同，来判断二者是否在同一个区域中。如果当前检索到的两个顶点属于同一个区域，则不需要进行合并操作。判断像素是否属于同一区域的代码如下：

# 判断两个像素是否属于同一个区域
def isSameSegment(coord1, coord2, segment_coord):
    coord1 = getSegment(coord1, segment_coord)
    coord2 = getSegment(coord2, segment_coord)
    return (coord1 == coord2).all()

除此之外，还需要计算任意两个像素距离的函数。依据这两个像素的坐标和RGB颜色值，将二者转换到 $(x, y, r, g, b)$ 空间，再计算欧氏距离，即特征向量各个分量相减后求平方和再开根即可，可以通过调用numpy模块中的范式功能实现，代码如下：

# 计算两个相邻像素在特征空间(x,y,r,g,b)的欧式距离
def distance(coord1,coord2,img_array):
    vec1 = np.array([coord1[0],coord1[1],img_array[coord1[0]][coord1[1]][0],
            img_array[coord1[0]][coord1[1]][1],img_array[coord1[0]][coord1[1]][2]])
    vec2 = np.array([coord2[0],coord2[1],img_array[coord2[0]][coord2[1]][0],
            img_array[coord2[0]][coord2[1]][1],img_array[coord2[0]][coord2[1]][2]])
    return np.linalg.norm(vec1-vec2)

3.2 分区算法实现的主体部分

算法实现的主体部分由函数segment实现。首先，对各个变量进行初始化操作，包括将区域数量初始化为总的像素数、将segment_coord字典初始化为各个像素自身的坐标、每个区域内部的距离为0：

# 初始时，区域数等于像素数
segment_num = img.size[0] * img.size[1]
# segment_coord[i][j]表示i,j位置的像素属于的区域，用一个统一的坐标表示
segment_coord = np.zeros((img_array.shape[0], img_array.shape[1],2)).astype(np.int16)
for i in range(img_array.shape[0]):
    for j in range(img_array.shape[1]):
        # 初始时，每个像素属于自己所在的区域
        segment_coord[i][j] = [i,j]
        SEG_GROUP[(i,j)] = [(i,j)]
        INNER_WEIGHT[(i,j)] = 0

每次合并时，我们需要找到权值最小的边，将边两边的像素所属的区域进行合并。为了防止繁琐的权重计算和排序，我考虑一开始将所有的边的权重都计算出来，并且进行从小到大的排序，从而就能由小到大的权值依次遍历各个边，对像素区域进行合并：

# 计算所有边的权重并按大小排序
weight = []
for i in range(img_array.shape[0]):
    for j in range(img_array.shape[1]):
        # 每个像素只计算四个方向的边，防止重复
        if j < img_array.shape[1]-1:    # 右边的邻居
            weight.append([(i,j),(i,j+1),distance((i,j),(i,j+1),img_array)])
            if i < img_array.shape[0]-1:# 右下的邻居
                weight.append([(i,j),(i+1,j+1),distance((i,j),(i+1,j+1),img_array)])
        if i < img_array.shape[0]-1:    # 下边的邻居
            weight.append([(i,j),(i+1,j),distance((i,j),(i+1,j),img_array)])
            if j > 0:
                weight.append([(i,j),(i+1,j-1),distance((i,j),(i+1,j-1),img_array)])
weight.sort(key = lambda x:x[2])

需要注意的是，所谓的“边”只能出现在某个像素的八邻域内，也就是说，如果不出界的话，每个像素只能和它左上、上、右上、左、右、左下、下、右下这八个相邻的像素连接。当遍历每个像素，将像素延伸出去的这八条边都考虑进去的话，每条边会计算两次，从而产生重复。考虑到每个条的表示方法为[(顶点1坐标),(顶点2坐标),边的权重]，遍历每个像素时只考虑它右边的和下面一排的共四个像素产生的边，这样可以保证每条边只计入一次，且顶点1和顶点2的坐标是按照升序顺序排列的。当然，边界情况要另外讨论。

然后就能开始进行图片的区域合并了。因为事先实现了上面的功能模块，这里基本只需要进行简单的调用即可。从小到大依次遍历各个边，如果该边的两端的顶点像素不属于同一个区域，且满足在理论部分提及的 $Merge(C_1,C_2)$ 条件的话，就对二者进行合并。因为之后还要合并像素少于50个的区域，所以这里是对整个图片区域的初步划分，当区域数量小于一定值就退出循环。该值我对不同的图片进行了不同的设置，即代码中的 SEGMENT_NUM变量：