自适应阈值算法

自适应阈值算法¹用到了积分图（Integral Image）的概念。积分图中任意一点$(x,y)$的值是从图左上角到该点形成的矩形区域内所有值的和。即：
$$I(x,y)=\sum _{\begin{array}{c}{x}^{\prime }\le x\\ y^{\prime }\le y\end{array}}i(x^{\prime },y^{\prime })$$
比如下图中的 $9$，就是左上角的 $4+1+0+4$

自适应算法的主要思想是以一个像素点为中心设置大小为 $s\times s$ 的滑窗，滑窗扫过整张图像，每次扫描均对窗口内的像素求均值，并将均值的 $1-t\%$ 作为局部阈值 。若窗口中心的像素值低于局部阈值 ，赋值0；高于局部阈值 ，赋值为255。这种算法需要对很多相互有重叠的区域进行多次加和计算。而积分图的使用可以有效地降低计算的复杂度和操作总次数。

为了计算积分图，需要在每个位置存储其左边和上方所有 $f(x,y)$ 值的总和：
$$I(x,y)=f(x,y)+I(x-1,y)+I(x,y-1)-I(x-1,y-1)$$
得出积分图之后，从滑窗左上角$(x_1,y_1)$到滑窗右下角$(x_2,y_2)$的矩形内的数值总和均可以使用式（1.1）计算：
$$\sum _{x=x_1}^{x_2}\sum _{y=y_1}^{y2}f(x,y)=I(x_2,y_2)-I(x_2,y_1-1)-I(x_1-1,y_2)+I(x_1-1,y_1-1)(1.1)$$

如下图中左上角$(x_1,y_1)$到右下角$(x_2,y_2)$的矩形$D$内的数值总和由它左边$C$和上边$B$以及左上角$A$的矩形算得：$(A+B+C+D)-(A+B)-(A+C)+A$

或者仍然用下面这张图来理解吧：

如果红色方框为滑窗区域，在原始数据中的和是 $4+1+1+0=6$。如果要通过右边的积分图来运算的话，就是 $16-7-7+4=6$。可以看到用积分图计算出来的结果是准确的。

滑窗矩形区域的均值则为：
$$m(x,y)=\frac{{\sum }_{x=x_1}^{x_2}{\sum }_{y=y_1}^{y2}f(x,y)}{(x_2-x_1)\cdot (y_2-y_1)}(1.2)$$

接着，就可以计算局部阈值了：
$$T(x,y)=m(x,y)\cdot \frac{100-t}{100}(1.3)$$

整个自适应阈值算法的过程共扫描全图2次：

1. 第一次扫描获得积分图；
2. 第二次扫描根据式 (1.1) 和 (1.2) 计算每次扫描窗口内像素值的平均值，然后根据 (1.3) 计算局部阈值。若窗口内某一像素点的值大于该阈值，则对应输出255，反之则输出0。

Niblack算法

Niblack算法同样是根据窗口内的像素值来计算局部阈值的，不同之处在于它不仅考虑到区域内像素点的均值和方差，还考虑到用一个事先设定的修正系数$k$来决定影响程度。
$$T(x,y)=m(x,y)+k\cdot s(x,y)$$

• $T(x,y)$为阈值；
• $m(x,y)$为均值；
• $s(x,y)$为方差？标准差；

上式的定义的阈值的含义为与窗口内像素值的均值相差$k$个标准差的值。小于阈值的判定为北京，反之则判定为前景。

Niblack算法的缺陷主要有两方面：

1. $r\times r$ 的滑窗会导致在边界区域 $(r-1)/2$ 的像素方位内无法求取阈值；
2. 如果 $r\times r$ 滑窗内全部是背景，那么该算法必然会使该区域一部分像素点成为前景，形成伪噪声。

因此，滑窗的边长 $r$ 的选取非常关键——若窗口太小，则可能会被背景包含，从而不能有效的抑制噪声；若窗口太大，则会导致细节丢失。

Sauvola算法

Sauvola算法²使针对文档二值化处理，在Niblack算法基础上的改进：
$$T=m\left[1+k(\frac{s}{R}-1)\right](3.1)$$

• $R$ 是标准方差的动态范围，若当前输入图像是8位灰度图像，则 $R=128$。

Sauvola算法在处理光线不均匀或染色图像时，比Niblack算法拥有更好的表现，因为（3.1）式以自适应的方式放大了标准差的作用。
乘以 $m$ 系数会降低背景区域阈值的范围，这可以有效地减少染色、污渍等带来的影响。

从上图可以看出，在光照不均匀的情况下，Sauvola算法比Niblack能保留更多的细节。

---

1. Bradley D, Roth G. Adaptive Thresholding using the Integral Image. Journal of Graphics Tools ,2007, 12:2, 13-21. DOI: 10.1080/2151237X.2007.10129236 ↩︎

2. Lazzra G, Geraud T. Efficient Multiscale Sauvola Binarizaiton. International Journal on Document Analysis and Recognition, 2014, 17(2); 105-123. DOI: 10.1007/s10032-013-0209-0 ↩︎