分类导航

基于SSE实现的极速的矩形核腐蚀和膨胀（最大值和最小值）算法。

发布时间：2017年06月22日作者： IT网络文摘 (该文来自笔记，点击查看原文)

因未测试其他作者的算法时间和效率，本文不敢自称是最快的，但是速度也可以肯定说是相当快的，在一台I5机器上占用单核的资源处理 3000 * 2000的灰度数据用时约 20ms，并且算法和核心的大小是无关的，即所谓的o(1)算法。

在实现本算法之前，也曾经参考何凯明在暗通道去雾时提出的一篇参考论文中的算法： STREAMING MAXIMUM-MINIMUM FILTER USING NO MORE THAN THREE COMPARISONS PER ELEMENT ，这篇文章所描述的过程也是o(1)的，速度也相当快，不过还是不够快。

我曾经自己构思了一个想法，也是基于行列分离的，在速度上比上文的代码又要快，并且也是o(1)算法，但是算法速度和图片的内容有关，比如对一个图进行了一次算法后，再次对结果执行相同的算法，可能后一次就要慢很多，这和我改进的算法本身有关系，但是这种情况是很少见的。

本文所要介绍的算法也是在很久以前就看到过的，但是一直没有引起我的重视，其对应的参考论文是 A fast algorithm for local minimum and maximum filters on rectangular and octagonal kernels ，当时觉得论文的实现起来可能没有我自己构思的快，也就没有去深究。

论文的实现步骤也是基于行列分离的，即先进行行方向的一维运算，然后再对结果进行列方向的一维计算，具体的理论描述大家去研究论文吧。

那其实论文的核心就是下面这个图。