1. 简介
近年来随着RCNN及其衍生算法在物体识别领域受到越来越广泛的认可和青睐，RCNN所依赖的图像分割算法——2004年Felzenszwalb发表的graph-based算法，也吸引了许多研究者的研究。网络上对这片论文的解读博客已有许多，其中几篇深入浅出，讲的十分透彻。笔者不拟在诸多博文上再添加一篇，这里主要分享一下研究Felzenszwalb论文第6节的一些感想，并附上代码作为探讨。
2. 基于ANN生成图并分割图像
在Efficient Graph-based图像分割算法论文第6节中，Felzenszwalb提出了使用近似最近邻算法寻找距离像素点最近的K个像素点，并以该包含K个像素点的球半径作为类内距离（ internal difierence），以两个球中距离最短的像素点之间的距离作为类间距离（difference between components）生成图。最后以此图作为基础分割图像。但由于作者在文中未分条写清算法步骤，且众多开源算法（skikit-image、OpenCV）中未实现这个小众算法，缺少参考，导致这个算法让人理解不透。只能动手操作一下，才好弄清楚具体的操作步骤了。
算法步骤
- 使用向量 p=(r, g, b, x, y) 表示坐标是(x, y)的像素点，其中：
r, g, b: 分别是像素点的颜色R、G、B值
x: 像素点所在的行数（从上往下数）
y: 像素点所在的列数（从左往右数） - 使用KD树寻找每个像素点的K个近似最近邻像素点，两个像素点间的距离用欧式距离度量，这里就得到了Kwidthheight条边；
- 对所有边按它所代表的距离升序排序；
- 使用并查集合并像素点，合并原则同论文第三章：被合并的两个部分需满足类间距离小于任意一个部分的类内距离；
- 返回得到的并查集。
3. 数值结果
可以看到使用KD树的时候即使有竹叶遮挡，熊猫的脸部会被划分到完整的一个部分中；使用Gride-based算法时，竹叶的遮挡会使熊猫的脸部被分隔到不同的部分。
这个例子表明使用KD树进行图的生成，对图像分割结果有显著影响，在空间上有分隔、但是颜色相近的部分能被划分到同一部分中。
4. 一些细节
1. 需要归一化吗？
p=(r, g, b, x, y) 中r、g、b的范围通常在0到255之间，而x、y则因图像高度和宽度而异，是否要将r, g, b, x, y归一化到[0, 1]之间再进行后续操作是值得考量的问题。笔者在操作中尝试了归一化的方法，但因归一化后的合并条件需要进行少许修改，暂用x、y乘以分别一个缩放系数，代码中分别用xZoom、yZoom表示，来调整计算距离时像素点坐标(x, y)所占的比重。但相信归一化是更robust的做法。
2. 生成KD树时为什么是按下标轮动选择而不是按方差最大选择？
标准的KD树生成应选择方差最大的维度进行划分，但实践中发现很多图片的颜色(r, g,b)方差很小，坐标(x, y)的方差较大。按方差最大原则选择划分为杜，会使在生成树时频繁使用(x, y)划分子树，导致相邻的像素点x或y只相差1，但被划分到不同子树中。这样分割后的图像有很多锯齿状子区域，比较粗糙。按下标轮动的方式，即按r->g->b->x->y->r->...的顺序周期性的重复选择不同维度划分子树，得到的结果区域轮廓更精细。
3. p=(r, g, b, x, y)还是(x, y, r, g, b)？
交换一下元素的位置本质上对向量表示的像素点没有影响，但如果生成KD树时第一次划分维度就选择x，最后的分割结果会有一条明显的竖线将图像左右分割成两部分。原因同第2点中提到的，KD树的根节点使用x划分，很容易使相邻的像素点落到不同子树中，在查找K个近似最近点时如果没有访问另一个分支子树，就会出现相邻像素点不在同一区域中的现象。
5. 结论与改进方向
- 虽然使用近似最近邻算法可以扩展区域划分的粒度，将几何上色彩不连续的区域合并到一个区域，但也有误分的可能，例如在上述算例中熊猫的右眼和鼻子和身体被划分在同一个区域；
- 生成、查找KD树增加了算法时间复杂度，相同条件下，计算时间增加。
6. 参考资料
[1] 本文代码地址：https://github.com/meliurc/kd_tree/
[2] Felzenszwalb原文：http://cs.brown.edu/people/pfelzens/segment/
[3] 推荐博客：https://blog.csdn.net/ttransposition/article/details/38024557
