何謂「Otsu」?
如何使用「Otsu」?
如何計算「Otsu」?
多值化使用「Otsu」
何謂「Otsu」
Otsu是一種自動門檻值決定法則
常用在選擇影像二值化的閥值上
當然Otsu並不是只能使用在影像二值化上
只要是選擇門檻值都能使用Otsu
如何使用「Otsu」
因為Otsu是一個閥值選擇準則
所以要使用Otsu之前
我們必需取得我們要用閥值分割之狀態空間的分佈
這或許有點難理解
我們以使用Otsu進行影像二值化為例
因為要進行分割的是像素值
因此我們要取得的是像素值的分佈 (也就是像素的直方圖)
而利用Otsu進行影像二值化的流程如下：
Step 1. 取得影像的直方圖
Step 2. 利用Otsu對直方圖找出最佳的閥值
(此為示意圖 不代表該直方圖的Otsu閥值位置)
Step 3. 利用找出來的閥值將影像二值化
而Otsu的任務就是從狀態分佈找到最佳的閥值也就是Step 2
如何計算「Otsu」
基本上利用Otsu所選擇的閥值具有以下特性
- 不同類之間具有最大變異量
- 同類之類具有最小變異量
其實這是因為Otsu就是延著「群內最小變異、群間最大變異」的思維來進行閥值的選擇
以下說明一下Otsu中會使用的公式
h(i) 代表直方圖第i點的值
如下圖：h(150) = 0.24 h(155) = 0.16
公式(1)、(2)代表著以「T*」為閥值，第一類和第二類的平均值
公式(3)、(4)為，以「T*」為閥值，第一類和第二類的變異量
公式(5)為，以「T*」為閥值，群內變異的總和
而公式(6)為Otsu的目標，找到一個「T*」群內變異的總和是最小的 (這邊尋找群內變異最小和群間變異最大是相同的)
最後我們將最好的「T*」視為閥值「T」
那要如何搜尋「T*」呢
基本上就是使用全部搜尋的方式
例如：直方圖有256個值
就是將「T*」從0到255都計算過
簡單的虛擬碼如下
T = null
minVariant = MAX_INT
for (T* = 0; T* < 255; T*++)
{
計算平均值 // 公式(1)、(2)
計算變異量 // 公式(3)、(4)
計算群內變異量總和 // 公式(5)
if (群內變異量總和 < minVariance)
{
T = T*
minVariance = 群內變異量總和
}
}
多值化使用「Otsu」
基本上Otsu除了可以進行影像的二值化以外
也可以使用在影像的多值化上(三值化、四值化…)
只是搜尋的「T*」增加為多個
三值化的大概虛擬碼
for (T1* = 0; T1* < 255; T1*++)
{
for (T2* = T1* + 1; T2* < 255; T2*++)
{
計算平均值
計算變異量
計算群內變異量總和
判斷是否找到更好閥值
}
}而影像的D值化需要D-1個閥值
所需要的迴圈數為D-1層
依複雜度來看
影像二值化搜尋「T*」的複雜度為 O(n) (以256灰階影像來說n = 256)
計算上還算是非常簡單
但如果是三值化的話
複雜度增加為 O(n^2)
可以發現複雜度增加了非常多
而D值化的複雜度為 O( n^(D-1) )
在影像的多值化上
完全搜尋效果並不是非常的好
因此使用超啟發式演算法來進行搜尋是個不錯的方式
新手發文如有錯誤，煩請指正！