【转载】分水岭超像素

前言：

超像素这个概念被提出以来，各种方法层出不穷~在计算机视觉和模式识别中也被广泛的应用。最近几年，CVPR，ICCV，PAMI，TIP，ICIP等各种期刊、会议关于超像素的论文超多。其实，这也说明了一个问题，超像素的实现其实很简单，所以才蹦出那么多算法的文章来....

其实早在2010年冬天，帮同学下载一篇论文，就是大名鼎鼎的 Turbo Pixel，PAMI上的一篇文章，同学是想把这个跟遥感结合以下，搞来应用一下。论文下载下来一看，我去...这不是很普通嘛，为啥能发PAMI。顺便去下载了作者的代码，那叫一个慢啊......以我这个性，480*320的图一秒钟跑不出来结果我就直接关掉了...

因为我本身是搞遥感图像处理的，对什么分水岭算法、Meanshift算法、多尺度区域合并等等钻研的比较多，各种算法也都自己实现了一遍。转念一想，这玩意儿有啥难啊？我现有的算法加点儿料，就能出同样的效果了....然后就开始动手改我自己写的分水岭算法... 结果当天晚上就搞定了....算法效率比Turbopixel快了不知道多少倍，普通大小481*321的图片一点就开，毫无延迟，顺便就把TurboPixel鄙视了一番。搞遥感的人对计算机视觉的热点一点都不敏感...直到第二年又发现了PAMI上出了SLIC的文章，又是一篇超像素的文章...于是决定动手把这个写个文章。奈何写作水平就那样，原理太简单了，都没啥高深的理论，墨迹了很久终于墨迹出来两页纸，哪儿也投不了。最后终于找到一个收短文的期刊，Electrics Letters, 正合我意，却不想被人家鄙视了，连审稿意见都没有....从此这个文章就沉默了三年半。直到14年底，某师兄说投了个ICIP的论文，有没有材料再搞一个？反正注册一个人可以覆盖3篇论文的费用...于是又重新搞出来，跟师兄一起扩充到了5页。这里不得不说，写作能力很重要，我就只能写2页，被师兄指导着写成了5页...然后..就中了。。

正题：

传统的分水岭，特别是Meyer的标记分水岭算法，是以影像的梯度级作为地形表面，梯度值高的地方地形高。这么一看，就形成了一系列坑坑洼洼的盆地。如果从坑里冒水出来了，那么这些盆地就会蓄水，形成一堆堆的水坑。水一直涨，不同的水坑就会合并，如果强制修筑堤坝，不让这些水坑连在一起，那么一个个的水坑最后就成为匀质的区域。那么在水从底部开始积累的时候，总是会先淹没地形的低洼处（梯度值较小的地方），因此，可以理解为这些低洼处具有较高的优先级。（这里如果不明白，可以参考一下分水岭算法的具体原理，用必应搜索 watershed transform，有个主页讲这个）。

但是，实际中，大家可以发现，荷叶上的水珠，总是呈现出比较规整的外形，为什么呢？其实是 因为水滴的外形不仅受重力作用的影响会流向低处，还会受到内在的张力约束而保持紧凑的外形。因此，如果从微观的角度来重新考虑标记分水岭算法，水坑形成的过程就不仅仅只流向梯度最低处了，还应该有形状上的约束。那么，我们要做的就是考虑怎么加入这个形状约束？

跟传统的超像素类似，首先我们设定一些均匀分布的种子点。假设水只能从这些洞洞中涌出来，然后去形成水坑，使水坑继续膨胀。那么，当水从坑的底部冒出来的时候，其必然使水坑变大，往外扩张。这时候，我们给他一个力，使之往外扩的时候，受到张力的影响而保持紧凑。当然，当水珠越小的时候，张力越大，水珠越大的时候，外围的张力越小。

因此，我们定义这样一个公式：

红框里面表示由梯度决定的优先级，蓝色框里面表示由张力决定的优先级。（水滴膨大过程中，从优先级最高的点开始向外扩张）。

我们定义以上公式来描述张力，即距离越远，优先级越低。同时，为了保护边缘，使得边缘越强，优先级更低。E(x,y)表示边缘的强度。

最后梳理一下这个算法的步骤：

（1） 计算梯度

（2）根据超像素个数，均匀的布设种子点（泉水眼）；

（3）模拟泛洪过程，淹没整个地形。跟传统标记分水岭唯一不同的就是在定义像素的处理优先级上，动了一点手脚。

由于分水岭本身超高的效率，使用这个算法的优点也没明显，高效！

最后，给出两张论文图：

有兴趣的同学同学可以参考论文： Watershed Superpixel,  IEEE ICIP2015

相关的可执行代码可以去这里下载：

http://download.csdn.net/detail/guzenyel/9197835