模型与约定
全局阈值分割是一种简单的分割方法:选取一个数 t,将每个像素的强度与它比较,标为暗或亮。规则忽略像素位置,只看强度值,因此只看直方图。本节明确有限图像模型,推导 Otsu 阈值法则使用的目标函数,并说明它能保证什么、不能保证什么。
设图像有 N≥2 个像素,实数强度为 x1,…,xN,下标的排列可以任意。阈值 t∈R 定义
C0(t)={i:xi≤t},C1(t)={i:xi>t}.等号的约定很重要:xi=t 的像素归入低强度类 C0。若两类均非空,称阈值可取。对可取的 t,记 nk=∣Ck∣、wk=nk/N,于是 w0+w1=1 且 0<wk<1。再定义
μk=nk1i∈Ck∑xi,vk=nk1i∈Ck∑(xi−μk)2,μ=N1i=1∑Nxi,vT=N1i=1∑N(xi−μ)2.
这里所有方差均按总体方差归一化:除以项数,而非项数减一。这是方法定义的一部分,下面的恒等式依赖它。非空条件也不是多余的:若 nk=0,则 μk 无定义,涉及它的公式也就没有意义。
用两个常数拟合
固定一个可取阈值。假设用分段常数拟合图像强度:C0 中每个像素以 c0 近似,C1 中每个像素以 c1 近似。平方误差为
E(c0,c1)=i∈C0∑(xi−c0)2+i∈C1∑(xi−c1)2.
对单个类和任意常数 c,利用 xi−c=(xi−μk)+(μk−c) 并展开:
i∈Ck∑(xi−c)2=i∈Ck∑(xi−μk)2+2(μk−c)i∈Ck∑(xi−μk)+nk(μk−c)2.
根据 μk 的定义,中间的和等于 Ck∑xi−nkμk=0。所以误差为 nkvk+nk(μk−c)2,恰在 c=μk 处最小。最佳双常数拟合的误差因此为
c0,c1minE=n0v0+n1v1=N(w0v0+w1v1)=NW,
其中 W=w0v0+w1v1 称为类内方差。选择使 W 最小的阈值,就是寻找一个明暗划分,使其最佳双强度近似的平方误差和(SSE)最小。这是该规则的建模含义:它拟合强度,并没有识别物体。
方差分解
对每个可取阈值 t,
μ=w0μ0+w1μ1,vT=w0v0+w1v1+w0w1(μ0−μ1)2.记类间方差 B=w0w1(μ0−μ1)2,则 vT=W+B。
均值。 C0 和 C1 划分 {1,…,N},因此
Nμ=i∈C0∑xi+i∈C1∑xi=n0μ0+n1μ1.两边除以 N 得 μ=w0μ0+w1μ1。
方差。 对上一节的逐类展开式取 c=μ。因为 Ck∑(xi−μk)=0,交叉项仍然消失,所以
i∈Ck∑(xi−μ)2=nkvk+nk(μk−μ)2.对 k=0,1 相加并除以 N:
vT=w0v0+w1v1+w0(μ0−μ)2+w1(μ1−μ)2.只需化简最后两项。由均值恒等式和 w0+w1=1,
μ0−μ=μ0−w0μ0−w1μ1=w1(μ0−μ1),μ1−μ=w0(μ1−μ0).因此
w0(μ0−μ)2+w1(μ1−μ)2=w0w12(μ0−μ1)2+w1w02(μ0−μ1)2=w0w1(w0+w1)(μ0−μ1)2,即 w0w1(μ0−μ1)2。■
证明透视
同一个展开式用了两次
证明只有一个计算想法:把 Ck∑(xi−c)2 围绕类均值展开。上一节对任意常数 c 使用它,说明 μk 是最佳常数;证明中再取 c=μ 使用一次。两次交叉项消失的原因相同,都是 Ck∑(xi−μk)=0。
各个假设在明确的位置起作用。非空条件是 μk 和 vk 存在的前提。划分性质用了两次:把 Nμ 拆成两类之和,以及把两类的展开式加成总和 NvT。总体归一化使每类的项写成 nkvk,于是除以 N 恰好得到均值恒等式中同样出现的权重 wk=nk/N。若改用除数 nk−1,同样的和所带的权重就是 (nk−1)/N 而非 wk,恒等式对 w0s02+w1s12 不再成立。
最后一步把两个“到总均值的距离”项化为一个“两类均值之间的距离”项,只用到由均值恒等式移项得到的 μ0−μ=w1(μ0−μ1),以及 w0+w1=1。
因为 vT 不依赖 t,每个可取阈值均满足 W(t)=vT−B(t)。所以最小化 W 和最大化 B 选出完全相同的阈值。此等价关系要求 W、B 和 vT 都使用同一批像素及总体方差归一化;混用其他归一化会破坏它。
在图像的可取阈值中,Otsu 阈值法则选取使类间方差 B 最大的阈值,等价地选取使类内方差 W 最小的阈值。
把 vk 换成样本方差 sk2=SSEk/(nk−1) 看似无害,但加权和 Ws=w0s02+w1s12 并不等于 vT−B。因此最小化 Ws 与最大化 B 可能选出不同阈值;而且只要某类只有一个像素,Ws 就无定义。下面以数据 (0,6,7,7,10,10) 为例的练习同时展示这两种现象。该法则中的每个方差都按总体方差归一化。
哪些阈值确实不同
设不同的观测强度为 z1<z2<⋯<zm。划分 (C0(t),C1(t)) 只取决于哪些强度满足 zj≤t。分三种情况:
- 若 t<z1,则 C0 为空。
- 若 t≥zm,则 C1 为空。
- 若对某个 1≤j≤m−1 有 zj≤t<zj+1,则 C0 由强度不超过 zj 的像素组成。
因此可取阈值构成 [z1,zm),恰好产生 m−1 种不同划分 P1,…,Pm−1。半开区间 [zj,zj+1) 内每个 t 给出相同标签。B 只依赖划分,所以在各这样的区间上为常数。
存在性。 若 m≥2,可取划分组成非空有限集,B 必定在其中取得最大值。最优阈值集合是若干区间 [zj,zj+1) 的并。若需报告一个代表,可选最大的暗强度 zj,也可选区间中点;这只是约定,没有额外数学意义。
常数图像。 若 m=1,即每个 xi=c,则 t<c 使 C0 为空,而 t≥c 使 C1 为空。此时没有可取阈值,法则无定义;不能说它“返回 c”。常数图像没有可供选择的二类划分。
不同划分并列。 不同划分可以达到同一最大值。例如数据 (0,1,2) 的两个候选为 P1={0}∣{1,2} 和 P2={0,1}∣{2}。两者均有 w0w1=2/9 和 ∣μ0−μ1∣=3/2,因此 B=92⋅49=21。必须明确并列处理规则,例如“取最小的 j”,否则输出未被唯一确定。
相同强度。 强度相同的像素总归入同一类,因为阈值不能分开相同数值。若改用约定 C0={xi<t},可实现的划分族相同,但现在由 t∈(zj,zj+1] 标记。报告的阈值改变,而可实现的标签不变。
例题 11.1.4
(强度为 0,1,1,3 的四个像素)
这里 N=4,强度级为 z=(0,1,3),μ=5/4,且
vT=41[(45)2+2(41)2+(47)2]=41⋅1625+1+1+49=1619.候选 t∈[0,1)。 类别为 C0={0} 和 C1={1,1,3},故 w=(1/4,3/4)、μ0=0、μ1=5/3。验证:41⋅0+43⋅35=45。C1 内偏差为 −32,−32,34,故 SSE1=94+4+16=38 且 SSE0=0。因此
W=48/3=32,B=41⋅43⋅925=4825.候选 t∈[1,3)。 类别为 C0={0,1,1} 和 C1={3},故 w=(3/4,1/4)、μ0=2/3、μ1=3。验证:43⋅32+41⋅3=45。C0 内偏差为 −32,31,31,故 SSE0=96=32,SSE1=0。因此
W=42/3=61,B=43⋅41⋅(37)2=4849.两行均满足 W+B=4857=1619,符合定理。第二种划分胜出。每个 t∈[1,3) 都给出最优标签 (0,0,0,1),因此 t=1 与 t=2 同样有效。t=3 会使 C1 为空,故不可取;任何 t<0 也不可取。
下面的互动图可编辑八个强度级的直方图,并对每个候选划分精确检验 W+B=vT,包括并列的情形、没有可取阈值的常数图像,以及强度的正仿射变换。
强度的正仿射变换
假设强度变为 yi=axi+b,其中 a>0,例如改变显示单位,或作线性增益与偏移。
设 yi=axi+b,其中 a>0。阈值 t 对 x 可取,当且仅当 at+b 对 y 可取,并且两者产生相同的像素划分。在每个这样的划分上,W 和 B 都乘以 a2。因此 y 的最优阈值集合是 x 的最优阈值集合在 t↦at+b 下的像。
因为 a>0,所以 xi≤t⟺yi≤at+b。y 可实现的划分恰与 x 相同,而阈值 t 对应 at+b。
对固定划分,类均值按 μk↦aμk+b 变换。每个偏差 yi−μk(y) 等于 a(xi−μk),故每个方差乘以 a2,权重不变。因此 W↦a2W、B↦a2B。所有得分乘以同一个正常数不改变排序,所以最大化的划分相同,最优阈值区间按 t↦at+b 变换。
若 a<0,强度顺序反转,明暗标签互换。由于 B 对两类对称,相同的无序划分仍最优,但等号约定此时附于另一侧。
高效计算目标函数
设强度级 zj 出现 hj 次,构造前缀计数和强度前缀和
n0(j)=l≤j∑hl,S0(j)=l≤j∑hlzl,
并令 n1=N−n0、S1=S−S0,其中 S=i∑xi。于是 μ0−μ1=n0n1n1S0−n0S1,从而
N2Bj=n0n1(μ0−μ1)2=n0n1(n1S0−n0S1)2,j=1,…,m−1.
只计算 1≤j≤m−1,自动排除空类。由于前缀按完整强度级而非单个排序像素取值,它也绝不会拆开相同强度。
若程序先把像素排序,再在每个像素位置之后(而非每个不同强度级之后)计算得分,就会同时给拆开相同强度的划分打分。对 (0,1,1,3),在第一个 1 之后切开得到 C0={0,1}、C1={1,3} 和 B=41⋅(23)2=169,但没有任何阈值产生这个划分:每个 t∈[1,3) 都把两个值为 1 的像素放入 C0。若这种划分得分最高,报告的阈值就无法重现被打分的标签。应按强度级 zj 累加,或跳过下一个排序值与当前值相等的位置。
对于任意实数数据,排序成本为 O(NlogN),扫描成本为 O(N)。对于属于 {0,…,L−1} 的整数强度,构造直方图成本为 O(N),扫描为 O(L)。整数数据下,上式分子为整数;若整数表示足够大而不溢出,可以在精确运算中交叉相乘比较有理数得分。
浮点运算中,当数值很大且彼此接近时,用“平方的均值减均值的平方”计算方差可能产生消去误差。若强度有共同的大偏移,上面的和之差也可能发生消去。累加前中心化可以减轻问题,但仍可能需要稳定求和和足够精度。
这些做法都不提供统计保证。精确运算中,程序仅计算给定有限目标的一个最优解;浮点计算可能改变接近的得分之间的比较。
与二均值聚类的关系
对固定划分,NW 正好是二均值代价,因为每类中心最优地取在该类均值。区别在于搜索哪些划分。二均值聚类允许把像素任意分成两个非空组;阈值法只允许 m−1 种有序划分,即所有暗强度都低于所有亮强度。阈值法因而精确优化一个受限的划分族。不受限制的最优解是否总在该族中,是需要独立证明的另一问题;本节不使用这一断言。
直方图看不到什么
反例模式
相同直方图,不同空间结构
考虑两个一维像素行:
行 A=(0,0,3,3),行 B=(0,3,0,3).两行均含两个强度 0 和两个强度 3 的像素。唯一可取划分由 t∈[0,3) 给出。两行均有 w=(1/2,1/2)、μ0=0、μ1=3、W=0 和 B=vT=9/4。
行 A 的输出标签为 (0,0,1,1),行 B 的为 (0,1,0,1)。行 A 只有一对相邻像素标签不同,行 B 则有三对。两者得分相同,因为 B 从未使用邻接关系。规则没有平滑项,因此不能据此推断形状、连通性或边界。
下面的计算从其他方向展示同一局限。
例题 11.1.6
(噪声把干净的划分变成交替标签)
设一行像素的预期标签为 (0,0,0,1,1,1),干净强度为 (10,10,10,30,30,30);现观测强度为 (10,22,10,30,18,30),所以 μ=20。三个候选为:
中间划分胜出,其标签为 (0,1,0,1,0,1),在第 2、5 个位置与预期不符。输出还逐像素交替,因为目标函数不阻止这种情况。
考虑九个像素:六个强度 0、两个强度 4、一个强度 20。假设预期前景为全部三个非零像素。
- 划分 {0}∣{4,4,20} 给出 B=32⋅31⋅(328)2=811568。
- 划分 {0,4}∣{20} 给出 B=98⋅91⋅192=812888。
因此法则将单个明亮像素单独分出,把两个强度 4 的像素归为背景,与预期标签相反。小类若离其余像素很远,可能通过因子 (μ0−μ1)2 主导目标函数。
光照不均。 考虑行 (0,2,3,5),预期标签依次为背景、物体、背景、物体。这里右半边照得更亮。预期物体集合的强度是 {2,5},不可能对任何 t 写成 {x>t},因为 3 介于 2 与 5 之间。无论最优与否,没有全局阈值能产生这些标签。
阈值法划分强度,并不识别物体,也不保证符合特定的预期分割。
练习
练习 11.1.8
(对强度 (0,0,2,2),找出所有可取阈值,以类均值的加权和计算 μ,计算 W、B 和 vT,并讨论并列。)
基础
解答(3)
1列出可取阈值
强度级为 0 和 2,故可取阈值为 t∈[0,2),它们都产生同一划分 {0,0}∣{2,2}。当 t<0 时 C0 为空;当 t≥2 时 C1 为空。
2在该划分上计算得分
此时 w=(1/2,1/2)、μ0=0、μ1=2,所以 μ=21⋅0+21⋅2=1。两类均为常数,故 v0=v1=0、W=0。类间方差为 B=41⋅4=1。每个值离 μ 的偏差是 ±1,因此 vT=1=W+B。
3解释并列
所有 t∈[0,2) 均并列,但这只是因为它们给出相同标签。只有一种划分,故不同划分之间没有并列。W=0 达到可能的最小值。
练习 11.1.9
(对 (0,1,1,3) 在 y=2x+5 下验证仿射不变性命题。)
基础
解答(3)
1变换数据和候选区间
变换后的数据为 (5,7,7,11),其 μ(y)=15/2=2⋅45+5。候选阈值区间是 s∈[5,7) 和 s∈[7,11),分别为 [0,1) 和 [1,3) 在 t↦2t+5 下的像。
2给两个候选打分
对于 s∈[7,11),两类是均值为 19/3 的 {5,7,7} 及 {11},所以 B=163(314)2=1249=4⋅4849。对于 s∈[5,7),类均值为 5 和 25/3,故 B=163⋅9100=1225=4⋅4825。
3与原得分比较
两个得分都是原得分乘以 a2=4,故同一划分胜出,最优区间为 [1,3) 的像 [7,11)。
练习 11.1.10
(对 (0,6,7,7,10,10),分别用 W 和 Ws=w0s02+w1s12(其中 sk2=SSEk/(nk−1))比较 t=6 与 t=7,并讨论整体最优值及值为 7 的像素。)
核心
解答(4)
1给阈值 t=6 打分
两类分别为 {0,6}(SSE=18)和 {7,7,10,10}(SSE=9)。于是 W=27/6=9/2,而 Ws=31⋅18+32⋅3=8。
2给阈值 t=7 打分
两类分别为均值 5、SSE=34 的 {0,6,7,7} 和 SSE=0 的 {10,10}。故 W=34/6=17/3,而 Ws=32⋅334=968≈7.56。
3比较两种排序
关键一步
总体归一化准则偏好 t=6,样本归一化版本却偏好 t=7,顺序发生反转;把恒等式 vT=W+B 中的 W 换成 Ws 后,该式一般不成立。
4确定整体最优和不可分的像素
在所有候选中,总体准则的最优阈值为 t∈[0,6),此时 SSE=0+14,W=7/3。此时 C0={0},s02 需要除以零,因此 Ws 在真正的最优处无定义。两个值为 7 的像素不能分开:“一个 7 暗、另一个 7 亮”并非阈值产生的划分,故不会被打分。
练习 11.1.11
(比较 2×2 图像 I=(0505) 和 J=(0550),再证明置换像素位置会以同一方式置换输出标签。)
核心
解答(3)
1给两张图像打分
两张图像均含两个强度 0 和两个强度 5 的像素。唯一可取划分对两者都给出 w0w1=1/4、(μ0−μ1)2=25 和 B=25/4。
2统计边界边
在四邻域关系下,2×2 网格有四条边。I 中有两条边连接不同标签,J 中四条边均如此。虽然边界结构不同,得分却相同。
3证明一般命题
设 σ 是下标置换,令 xi′=xσ(i)。强度的多重集合不变;nk、μk、vk 和 B 都是阈值两侧多重集合的对称函数,因此每个阈值的得分相同,最优阈值集合不变。像素 i 的标签为 [xi′>t]=[xσ(i)>t],即原像素 σ(i) 的标签。因此这一规则无法看到空间重排。