[db:标题]

因未测试其他作者的算法时间和效率，本文不敢自称是最快的，但是速度也可以肯定说是相当快的，在一台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 ，当时觉得论文的实现起来可能没有我自己构思的快，也就没有去深究。 论文的实现步骤也是基于行列分离的，即先进行行方向的一维运算，然后再对结果进行列方向的一维计算，具体的理论描述大家去研究论文吧。 那其实论文的核心就是下面这个图。 　In表示一维行方向的输入数据，g/h分别运算过程中的两个中间数据，和输入数据大小一样。 如上图所示，我们假定需要进行计算的核大小为R，那么将一行分为多个大小为 D =（2R+1) 的分段，例如图中R=2, D=5 ，对每一个分段进行预处理，其中 x 号位置存放的是箭头所在直线段上的点中的最大值（最小值），如此处理得到 g 和 h 两个数组，那么对于某个点（索引为I），其半径R内的最大（小）值为：Max/ Min(g(I+R),h(I-R))。 过程好简单。 我们拿一组数据来说明上述过程，假如一行数据如下,我们要进行膨胀操作（最大值），核半径为2： 　　　　 In:　　20　　12　　35　　9　　10　　7　　32　　15　　20　　45　　28 　　对应的g/h为： 　　　　 g:　　20　　20　　35　　35　　35　　7　 32　　32　　32　　45　　45 　　　　　　 h:　 35　　35　　35　　10　　9　　45　45　　45　　45　　45　　28　 如果我们要计算第4个点的半径为2的最大值，则对应 g(I+R) = g(4+2) = 7,h(I-R)=h(4-2)=35, 得到结果为max(7,35) = 35; 如果我们要计算第6个点的半径为2的最大值，则对应 g(I+R) = g(6+2) = 32,h(I-R)=h(6-2)=10, 得到结果为max(32,10) = 32; 注意上面索引是以1位小标计数起点的。 边缘处理： 注意到在边缘处，比如左侧边缘，当要计算的点的索引小于R时，这时h值是无效的，而在右侧边缘，g值是无法取到的，但是仔细观察，问题很简单，还拿上述数据为例，如果要计算索引为2处半径为2的最值，由于h(2-2)是超出索引的（前面说了本例以1为下标起点），因此不能用前述的方式，那我们回归到问题的本质，计算2处半径为2的最值，就是计算max(In(1),In(2),In(3),In(4)), 而这个值不就是g数据中索引为2+2处的数据吗，在这之前就已经帮我们算法，直接取值就可以了。 在数据尾部（右侧），情况有所不同，我们应该从H中取值。 从上述的分析可知，这个算法有个特性，就是半径越大，算法的耗时会越小，因为对边缘的处理只需要拷贝数据，而没有了更多的计算，可能很多人不信吧。 算法实现： 　　有了上面的描述，要实现一个快速的腐蚀或膨胀算法相信对部分来说应该是一件非常容易的事情，先行方向处理，在列方向，好简单。 　　 最近我是迷上了SSE算法优化，于是就思考了这个算法的SSE优化，以前在看SSE的函数时，就一直在想_mm_max_epi8/_mm_min_epi8这种一次性能获取16个字节数据的最值的函数是否能用在腐蚀和膨胀上，不过由于他们是对两个连续数据的比较，在行方向上是难以运用的，但是如果数据比较是列方向上，那不就可以使用了吗。 我们上述算法就有列方向的比较，不就有了用武之地了。