在「b458: 非黑即白」當中,題目直接給定臨界值。能不能寫程式自動找到臨界值呢?答案是肯定的!
理想的臨界值,把直方圖切成左右兩側,左側盡量集中、右側盡量集中。外觀有如兩座山峰。
統計學裡面,集中、分散的重要指標,叫做變異數。變異數是「數值與平均數的差平方」的平均數。平均數是數值總和除以數值數量。
理想的臨界值,以統計學的術語重新描述:左側變異數、右側變異數,兩者的加權平均數,越小越好。權重是左側、右側的出現次數總和。
左右兩側各自集中,相對來說,就是左右兩側跨距明顯。依此想法,方才的數學式子,經過嚴謹的推導,可以重新改寫成兩者的平均數的差平方,乘上加權,越大越好。
現在請你依照前人推導出來的數學結果,寫程式自動找到臨界值,並且令圖片二值化。
臨界值是整數。窮舉各種臨界值,從中找到最好的臨界值。如果最好的臨界值有許多個,那麼請找到最小的臨界值。最極端的例子是整張圖片只有一個像素,此時該像素直接變成白色。
本題的亮度定義成 (R+G+B)/3。計算直方圖,亮度需四捨五入;計算變異數、平均數、二值化,亮度不需四捨五入。
一張圖片:兩個整數 W H (1 <= W, H <= 256),是圖片的寬和高;接下來的 H 行,每行有 W*3 個整數,是每個像素的 RGB 值 (0 <= R, G, B <= 255)。
請輸出處理過的圖片。
1 2 128 128 128 127 127 127
1 2 255 255 255 0 0 0
1. 如果不熟悉直方圖,可以先試試看「b459: 圖片的直方圖」。
2. 學術上,此問題稱作 Image Thresholding,此演算法稱作 Otsu's method。
3. threshold value,中文翻譯成「門檻值」、「閾值」、「臨界值」。另外還有個積非成是的「閥值」。
4. 下面左圖是環形漸層顏色,右圖是使用本題的演算法實施二值化,結果卻莫名其妙多了一條線。你能解釋原因嗎?
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|