設定與約定
全局閾值分割是最簡單的分割方法:選一個數 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,包括並列的情形、沒有可用閾值的常數圖像,以及強度的正仿射變換。
探究MATH3360 · v_T = W + B
每個候選分割都滿足 v_T = W + B
編輯強度 0 至 7 的直方圖。對相鄰兩個實際出現的強度之間的每個分割,表格列出權重、類平均值、類內變異數 W 與類間變異數 B,並把 W + B 與總變異數 v_T 對照。所有數值都是精確分數,並採用母體標準化(除以像素個數)。
直方圖預設 正仿射變換 x → αx + β
長條高度是該強度級的像素個數;標籤為強度 αx + β。虛線是相鄰兩個實際強度之間的候選切點,以 j 編號;實線標示所選分割。下表給出相同的資訊。
直方圖| 強度級 x | 強度 αx + β | 像素個數 |
|---|
| 0 | 0 | 1 |
|---|
| 1 | 1 | 2 |
|---|
| 2 | 2 | 0 |
|---|
| 3 | 3 | 1 |
|---|
| 4 | 4 | 0 |
|---|
| 5 | 5 | 0 |
|---|
| 6 | 6 | 0 |
|---|
| 7 | 7 | 0 |
|---|
候選分割| j | 閾值 t 屬於 | w₀ | w₁ | μ₀ | μ₁ | W | B | W + B = v_T | 所選 |
|---|
| 1 | [0, 1) | 1/4 | 3/4 | 0 | 5/3 | 2/3 | 25/48 | 是 | 否 |
|---|
| 2 | [1, 3) | 3/4 | 1/4 | 2/3 | 3 | 1/6 | 49/48 | 是 | 是 |
|---|
- 像素個數 N
- 4
- 平均值 μ
- 5/4
- 總變異數 v_T
- 19/16
- 所選分割 j
- 2
- 最優閾值
- [1, 3)
- B 的最大值
- 49/48
- 分割之間並列
- 否
- 每個分割都有 W + B = v_T
- 是
- B 與 (n₁S₀ − n₀S₁)²/(N²n₀n₁) 一致
- 是
- 經 x → αx + β 後最優分割不變
- 是
- 每個 B 都乘以 α²
- 是
- 因子 α²
- 1
分割 j = 2 的 B = 49/48 最大;區間 [1, 3) 內每個閾值 t 都選出它。對全部 2 個分割,W + B = v_T = 19/16。
為何 W + B = v_T,以及為何只有 m − 1 個分割要緊
在固定的分割上,把 x − μ 寫成 (x − μₖ) + (μₖ − μ)。在每一類上求平方和,交叉項因相對 μₖ 的偏差之和為零而消失,得 v_T = w₀v₀ + w₁v₁ + w₀(μ₀ − μ)² + w₁(μ₁ − μ)² = W + w₀w₁(μ₀ − μ₁)²。全程採用母體標準化。
閾值 t 給出分割「強度 ≤ t」,所以有 m 個相異的實際強度 z₁ < … < zₘ 時,只有相鄰強度之間的 m − 1 個切點不同。t < z₁ 令 C₀ 為空,t ≥ zₘ 令 C₁ 為空,這些閾值不可用;B 在每個區間 [zⱼ, zⱼ₊₁) 上為常數。不同的 j 取得相同最大值時,須明確訂出並列法則。
在 α > 0 的 x → αx + β 下,像素的次序不變,所以分割相同、權重相同,每個 μₖ 變為 αμₖ + β,每個偏差乘以 α。因此 W 與 B 都乘以 α²,排序不變,最優區間移到 [αzⱼ + β, αzⱼ₊₁ + β)。
範圍:八個強度級,每級至多九個像素,即至多 72 個像素。α 為正整數、β 為整數,使每個數值都保持為精確分數。並列法則取「最小的 j」;另一條明確訂出的法則會給出另一個有效閾值,但 B 相同。
強度的正仿射變換
假設強度重新縮放為 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} 和 {10,10}(SSE=0)。因此 W=34/6=17/3,而 Ws=32⋅334=968≈7.56。
3比較兩種排名
關鍵一步
母體準則較喜歡 t=6,樣本標準化版本卻較喜歡 t=7:排名反轉。一般而言,把 W 換成 Ws 後,恆等式 vT=W+B 不再成立。
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) 的標籤。因此空間重排對此法則不可見。