大津阈值及其加速原理小结 一、OTSU 算法思想 OTSU 按图像的灰度特性，将图像分成背景和目标 2 部分。背景和目标之间的类间方差 越大，说明构成图像的 2 部分的差别越大,当部分目标错分为背景或部分背景错分为目标都 会导致 2 部分差别变小。因此,使类间方差最大的分割意味着错分概率最小。 二、OTSU 目标 求取图像 ( , I x y 前景(即目标)和背景的分割阈值（记作T ） ) 三、OTSU 求解过程 全图设定： 设灰度级为i 的像素点个数为 in ，则该灰度级的出现概率为： p i  n i  M N 设图像大小为 M N ，所有像素点之和为 alls ，平均灰度为u ，则有如下关系： s all  255  i n i  i  0  u  all 255 s   M N   0 i  i p  i  前景、背景的设定 当阈值为t 时，设前景像素点数占整幅图像的比例记为 0w ，前景像素点平均灰度 0u ， 则有： p i u 0  t  i  0  i p  i  w 0 w 0 t   i  0 同理，对于背景 1w 、 1u 之间也存在同样的关系： w 1  N 1  M N  255  i 1 t   p i u 1  255  i 1 t    i p  i  w 1 w w 1 1  类间关系有： 0 那么前景背景的类间方差为 var ，则有下式：  u  则大津阈值即为 var 取最大时所对应的灰度值T  var w u  w u 1 1    u  0 0 2 2   w w u 0 1 0  u 1 2  代码角度解析算法： 

 v ar w w u  1  u 1 0 2  0       255  i 1 t    i p  i  w 0   i  w 1  p i 2       t  w w  i 0 0 1  可以看出，算法的运算分别有： 步骤一：[0,255] 求取 in 步骤二：[0,255] 求取 ip 步骤三：阈值t 在[0,255] 间遍历 步骤四：跟据阈值t 求类间方差，其中分别有前景[0, ]t 、背景[ t  1,255] 的计算 四、OTSU 算法的加速 加速版本一： 基本思想：尽量利用全图、前景、背景之间的关系将三者计算将为只需计算其二，如避 免背景 1C 的循环计算（即[ t  1,255] 的相关计算），进而达到提升速率的目的 已知： u  255  i p   i i  0 设 U 0  t  i p  i  0  i ，则 Uu 0 w 0  ， 0 u 1  255  i 1 t    i p  i  w 1  255  i  0  i p  i t  i  0   w 1  i p  i   0 u U  w 1 

 var w w u  1  u 1 0 2  t  i  0 255  i 1 t    i p  i  w 0   i p  i  w 1 2       w w 0 1 0          U w   1 w w 0 1 0             2 2   U 0 w 0  0 0  u U  w 1      u U w  0 w w 0 1  0 w w 0 1  2 0 w u U w w 0 0   1 2    w u U  0 w w 1 0 t   0   1  i 2     i  w 0 p i  w u 0  w 0 由上式可以看出：算法需要 步骤一：[0,255] 求取 in 步骤二：[0,255] 求取 ip 、u 步骤三：则接下阈值t 在[0,255] 间遍历时，只需进行前景[0, ]t 的计算，且此循环可以与阈 值t 的遍历合并进行 加速版本二 基本思想：通过尽量减少除法运算、浮点运算达到效率的改善 初步变形： 涉及到的变量：设所有前景、背景的像素点个数总和分别为 0N 、 1N ，灰度值之和分别 为 0s 、 1s ，则有： N 0 N 1 t   i  0 n i w 0  t 0 N   M N   0 i 255   i 1 t   n i w 1  N 1  M N  255  i 1 t   p i p i s 0   i n   i u 0  t i  0 s 1  255  i n  i 1 t    i u 1  s 0 N 0 s 1 N 1 

类间关系有：  var w w u  0 1  u 1  N M N 1   N 0  2 N 0   M N M N 1  M N  2     0 N 1  0  N s N s 1 0 0 1 N N 1  s 0  N    0 2    s 1 N  2 1   至此，已完成变形，将上式简化为求  var  N s N s 1 0 0 1 N N 1   0 2 的最大值则达到目的。 二次变形： 结合版本一的思想，仍可进一步简化为： 2   s 0 2    var     0 0 0    N s N s 1 0 0 1 N N 1  N s N s  1 0 all N N  1   0 N N 1  0   MNs N s 0 all N MN N      2    0 0 0 0   N N s N s 1 0  2   all 步骤一：[0,255] 求取 in 步骤二：[0,255] 求取 alls 步骤三：则接下阈值t 在[0,255] 间遍历时，只需进行前景[0, ]t 的相关计算（ 0N 和 0s ）， 且此循环可以与阈值t 的遍历合并进行 **此方法需注意一点：其中 N s N s 1 0 0 1  2 或 MNs N s 0 all  0 2 的算数值较大，需注意其数 量级 **且此方法经过初步变形后，后期可以通过生成积分图来减少阈值 t 遍历内部的计算，同样 也需要注意其数量级限制 

五、各版本时间对比示例 以下给出 512*512 的 lena 图的大津阈值计算做为示例 图中分别给出： 原始大津阈值； 快速大津阈值版本一； 快速大津阈值版本二（只完成初步变形）； 快速大津阈值_Fast 二（版本二初步变形后结合版本一的思想的结果，即避免 1N 和 1s 的计算） *其中，计算时间以 ms 为单位，是 1000 次运算时间的平均值 可见，最终实现提速的关键步骤即为将全图、前景图、背景图三者的计算减少为 二者的运算方法；但浮点转定点的预处理，在下位机上效率提升效果要明显高于 上位机。