Niblack算法的快速實現技巧－Rocky的部落格

http://blog.csdn.net/ieogxw/article/details/3871750

在許多文本圖像的預處理過程中, 二值化過程是至為關鍵的一個環節。二值化算法的效果會對後續的處理如版面分析，字符定位以及識別等產生決定性的影響。

二值化的算法有很多，大體分為兩類: 全局閾值算法（如otsu算法）和局部閾值算法（如niblack）。而在汗牛充棟的局部閾值算法中，niblack 是實現方法較為簡單，算法效果較為穩定的一種。但傳統的niblack算法需要對圖像中的每個像素計算其鄰域的統計性質（均值與方差），算法復雜度為o(size *area) ，其中size 為圖像像素尺寸大小，area 為鄰域面積。作者嘗試地對計算均值和方差的方法進行了改進，使得總體算法復雜度降低為 o(size)，從而做到與鄰域窗口大小基本無關。

算法的關鍵是對每個像素的局部窗口求和過程的計算方式。圖像實際上可看作是個二維數組，對二維數組中每個元素求局部窗口和的常規方式（C#代碼）如下：

[c-sharp:showcolumns:firstline[1]] view plaincopy 
·········10········20········30········40········50········60········70········80········90········100·······110·······120·······130·······140·······150
/// <summary>  
/// 常規的二維數組元素局部窗口求和程序  
/// </summary>  
/// <param name="array"> 輸入二維數組</param>   
/// <param name="winR">窗口半徑</param>  
/// <returns>輸出結果</returns>  
  
public static int[,] LocalSum_Common(byte[,] array, int winR)  
{  
    int width = array.GetLength(0);  
    int height = array.GetLength(1);  
    int[,] sum = new int[width, height];  
    int temp;  
  
    //不考慮邊界情況，  
      //水平方向：winR行至width-winR行，  
      //垂直方向：winR列至width-winR列  
  
    for (int y = winR; y < height - winR; y++)  
    {  
        for (int x = winR; x < width - winR; x++)  
        {  
            temp =0;  
            //對每個元素計算其周圍半徑為winR窗口內元素的累計和  
            for (int k = -winR; k <= winR; k++)  
            {  
                for (int j = -winR; j <= winR; j++)  
                {  
                    temp += array[x + j, y + j];  
                }  
            }  
            sum[x, y] = temp;  
        }  
    }  
    return sum;  
}  

上述求和的實現過程中包含了大量的重復運算。復雜度為 o(width*height*winR*winR)。由於二維數組中的相鄰元素的局部窗口是相互交叉的，所以後一個元素的求和運算可以利用前一個元素的部分運算結果。為了達到這一目的，考慮將整個運算過程拆分為兩個步驟，先進行垂直（水平）方向的求和再進行垂直（水平）方向的求和。代碼如下

[c-sharp] view plaincopy 
/// <summary>  
/// 快速的二維數組元素局部窗口求和程序  
/// </summary>  
/// <param name="array"> 輸入二維數組</param>   
/// <param name="winR">窗口半徑</param>  
/// <returns>輸出結果</returns>  
/// <summary>  
public static int[,] LocalSum_Fast(byte[,] array, int winR)  
{  
    int width = array.GetLength(0);  
    int height = array.GetLength(1);  
    int[,] temp = new int[width, height];//保存中間結果的數組  
    int[,] sum = new int[width, height];  
  
    //不考慮邊界情況，  
    //水平方向：winR行至width-winR行，  
    //垂直方向：winR列至width-winR列  
  
    //對起始行winR在垂直方向求線性和  
    for (int x = winR; x < width - winR; x++)  
    {  
        for (int k = -winR; k <= winR ; k++)  
        {  
            temp[x, winR] += array[x, winR + k];  
        }  
    }  
    //從winR+1行至末尾行height-winR，依次基於前一行的求和結果進行計算。  
    for (int y = winR + 1; y < height - winR; y++)  
    {  
        for (int x = winR; x < width - winR; x++)  
        {  
            temp[x, y] = temp[x, y - 1] + array[x, y + winR]   
                         - array[x, y - 1 - winR];  
        }  
    }  
      
    //基於保存的垂直方向求和結果，進行水平方向求和  
    //對起始列winR在水平方向求線性和  
    for (int y = winR; y < height - winR; y++)  
    {  
        for (int k = -winR; k <= winR ; k++)  
        {  
            sum[winR, y] += temp[winR + k, y];  
        }  
    }  
    //從winR+1列至末尾列height-winR，依次基於前一列的求和結果進行計算。  
    for (int x = winR + 1; x < width - winR; x++)  
    {  
        for (int y = winR; y < height - winR; y++)  
        {  
            sum[x, y] = sum[x - 1, y] + temp[x + winR, y]   
                        - temp[x - winR - 1, y];  
        }  
    }  
    //運算完成，輸出求和結果。  
    return sum;  
}  