基于局部直方图相关算法的近似优化和提速。

标签：Shift 模糊算法提速直方图 64 Radius

基于局部直方图的算法有很多很多，比如中值模糊、表面模糊、选择性模糊等等，这类算法有个通病，就是即使选择使用SIMD指令加速，因为其内在的特性，速度还是不能很快，但是又找不到其他合适的构架来优化他，还必须使用直方图技术，本文介绍了一种简单的方法来计算该类算法的加速和优化。

　　基于局部直方图的算法有很多很多，我们已经研究这类算法有以下一些：

　　 1、中值滤波

　　2、表面模糊

　　3、选择性模糊

　　4、中值锐化

　　5、图像局部熵

这类算法有个通病，就是即使选择使用SIMD指令加速，因为其内在的特性，速度还是不能很快，但是又找不到其他合适的构架来优化他，还必须使用直方图技术，比如我们的中值滤波，我尝试过各种商业软件，其速度都和我博客里提到的那个优化速度差不多，说明大家基本上都是那个套路。你们当确实某个场景需要更快的速度时，我们是否能有其他方法来加速呢，或者使用某个近似的方法来替代呢，经过个人的实践，我觉得还是可以有的。

　　一个简单的方法就是减少直方图的数量，常规状态下我们直方图有256个元素，因为基于局部直方图的算法基本都是一些统计类算法，是大面积像素的统计信息，所以最终的结果其实也是个统计结果。那么我们压缩直方图的量级，只要压缩量合理，最后的结果可能差异不是很大。

　　我们可以把直方图压缩为128等级、64等级、32等级，更小的等级可能信息损失量过大，当压缩时，对应的直方图统计工作不会减少，可能计算量还会稍微有点增加，如下面的代码所示：

for (int Y = 0; Y < Height; Y++)
{
    if (Y == 0)                                            //    第一行的列直方图,要重头计算
    {
        for (int K = -Radius; K <= Radius; K++)
        {
            unsigned char *LinePS = Src + ColOffset[K + Radius] * Stride;
            for (int X = -Radius; X < Width + Radius; X++)
            {
                ColHist[(X + Radius) * HistAmount + (LinePS[RowOffset[X + Radius]] >> Shift)]++;
            }
        }
    }
    else                                                //    其他行的列直方图，更新就可以了
    {
        unsigned char *LinePS = Src + ColOffset[Y - 1] * Stride;
        for (int X = -Radius; X < Width + Radius; X++)        // 删除移出范围内的那一行的直方图数据
        {
            ColHist[(X + Radius) * HistAmount + (LinePS[RowOffset[X + Radius]] >> Shift)]--;
        }

        LinePS = Src + ColOffset[Y + Radius + Radius] * Stride;
        for (int X = -Radius; X < Width + Radius; X++)        // 增加进入范围内的那一行的直方图数据
        {
            ColHist[(X + Radius) * HistAmount + (LinePS[RowOffset[X + Radius]] >> Shift)]++;
        }
    }
　　.........
}

　　很明显，每个像素点都有右移Shift的计算，这个计算是凭空增加的，幸好，移位的计算量很小。

这个直方图更新的耗时的轻微增加，换来的是后续，累计直方图统计的数据量的集聚变小，以及计算过程的集聚下降，如下代码所示：

for (int X = 0; X < Width; X++)
{
    if (X == 0)
    {
        for (int K = -Radius; K <= Radius; K++)            //    行第一个像素，需要重新计算    
            HistgramAddShort_PureC(ColHist + (K + Radius) * HistAmount, Hist, Shift);
    }
    else
    {
        HistgramSubAddShort_PureC(ColHist + (RowOffset[X - 1] + Radius) * HistAmount, ColHist + (RowOffset[X + Radius + Radius] + Radius) * HistAmount, Hist, Shift);  //    行内其他像素，依次删除和增加就可以了
    }
    IM_Calc_SB_PureC(Hist, Intensity + HistAmount - 1 - (LinePS[X] >> Shift), LinePD + X, Shift);
}

　　HistgramAddShort_PureC和HistgramSubAddShort_PureC里的计算量随着移位量的增加而变少，IM_Calc_SB_PureC里的计算量也同步变少。

　我们用一副1920*1080的灰度图做测试，以表明模糊为例，当不压缩实现时，平均耗时276ms，压缩到128等级时，用时160ms，64等级时，用时95ms，32等级时，用时51ms。

基于局部直方图相关算法的近似优化和提速。_中值

基于局部直方图相关算法的近似优化和提速。_局部直方图_02

基于局部直方图相关算法的近似优化和提速。_ide_03

　　　　　　　　原始图像　　　　　　　　　　　　　　　　　　　　　　　　 256级表面模糊　　　　　　　　　　　　　　　　　　 128级表面模糊

基于局部直方图相关算法的近似优化和提速。_中值_04

基于局部直方图相关算法的近似优化和提速。_局部直方图_05

基于局部直方图相关算法的近似优化和提速。_局部直方图_06

　　　　　　　　　　64级表面模糊　　　　　　　　　　　　　　　　　　　　　　　　32级表面模糊　　　　　　　　　　　　　　　　　　　　　　16级表面模糊

　　可见，对于表面模糊，甚至16级的效果都是可以接受的。

　　对于选择性模糊、局部熵等算法，也是同样的道理。

上面的几个算法，其结果值都是某个权重累加值除以权重，其中间结果其实是个浮点数，因此，等级量化后对结果不是影响很大。

对于中值模糊，情况又有所不同，因为中值是将直方图分为细分直方图和粗分直方图，而最终得到的结果是一个整形值，这个时候如果我们降低直方图的色阶精度，得到的结果可能会存在一定的瑕疵，特别是用在比较平滑的区域内，像素信息比较少，这个时候可以看到有较为明显的过渡色阶。比如我们把色阶调整为64阶，那么细分则有64个元素，粗分有8个元素，这个时候算法的速度大概能提高一倍，不过效果会有一定差异，实际使用时这个差异是否在容许的范围，就要看具体的应用了。

　　比如1920*1080的灰度图，正常C语言满色阶中值模糊大概要200ms，如果调整为64色阶，大概在100ms实现。对于普通信息比较丰满的图，他们的效果差异也不大，如下图所示：

基于局部直方图相关算法的近似优化和提速。_ide_07