基于Python实现图像分割算法.zip

# 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)$上，也就是坐标和颜色通道组成的特征空间。每个像素在八领域内与八个像素相邻，即具有边。边的距离由特征向量计算得出，一般用欧氏距离。 由此，我实现基于图的图像分割方法流程如下： 1. 将图片的每个像素按照坐标和颜色投影到$(x,y,r,g,b)$特征空间上，初始时每个像素自身属于单独一个区域 2. 计算所有边的权重大小，即八领域内像素的特征向量的欧式距离，并按照距离大小排序 3. 按距离从小到大的顺序，依次将这些边两端的像素合并到同一个区域。能否合并依据上述的$Merge(C_1,C_2)$的公式判断 4. 重复第3步，直到剩余区域数到达设置的下界 5. 遍历剩下的区域，将像素数少于50个的区域和相邻的区域直接合并 由此就能得到划分好区域的图片。我们只需要记录每个区域所含的全部像素的坐标，由这些坐标找到前景图的相应位置，统计前景像素数和背景像素数就能确定该区域应该被判定为前景还是背景。 # 3. 代码实现与说明 该部分的代码全部由自己实现。 ## 3.1 一些功能模块的实现 在实现算法主体流程前，可以预见到，程序需要用多种方式刻画像素和像素、像素和区域之间的关系。为了之后代码的简洁性，我先实现了部分功能模块方便多次调用。首先需要两个全局变量： ```python # 用于查询某个片段内部的所有像素 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)$通过下面的函数实现： ```python # 计算两个片段的片段内距离 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`查询到一个像素所在区域的代表像素，即： ```python # 查询一个像素所属的区域 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个像素的区域时，因为之后不需要用到区域内最大距离，因此不进行计算，可以进行一定的加速。 ```python # 合并两个区域 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 ``` 有了上述操作后，我们可以通过查询两个像�