b460. 判若黑白
標籤 : 影像處理
通過比率 : 8人/20人 ( 40% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-10-28 07:48

內容


在「b458: 非黑即白」當中,題目直接給定臨界值。能不能寫程式自動找到臨界值呢?答案是肯定的!

理想的臨界值,把直方圖切成左右兩側,左側盡量集中、右側盡量集中。外觀有如兩座山峰。



統計學裡面,集中、分散的重要指標,叫做變異數。變異數是「數值與平均數的差平方」的平均數。平均數是數值總和除以數值數量。

理想的臨界值,以統計學的術語重新描述:左側變異數、右側變異數,兩者的加權平均數,越小越好。權重是左側、右側的出現次數總和。



左右兩側各自集中,相對來說,就是左右兩側跨距明顯。依此想法,方才的數學式子,經過嚴謹的推導,可以重新改寫成兩者的平均數的差平方,乘上加權,越大越好。



現在請你依照前人推導出來的數學結果,寫程式自動找到臨界值,並且令圖片二值化。

臨界值是整數。窮舉各種臨界值,從中找到最好的臨界值。如果最好的臨界值有許多個,那麼請找到最小的臨界值。最極端的例子是整張圖片只有一個像素,此時該像素直接變成白色。

本題的亮度定義成 (R+G+B)/3。計算直方圖,亮度需四捨五入;計算變異數、平均數、二值化,亮度不需四捨五入。

輸入說明

一張圖片:兩個整數 W H (1 <= W, H <= 256),是圖片的寬和高;接下來的 H 行,每行有 W*3 個整數,是每個像素的 RGB 值 (0 <= R, G, B <= 255)。

輸出說明

請輸出處理過的圖片。

 

範例輸入 #1
1 2
128 128 128
127 127 127
範例輸出 #1
1 2
255 255 255
0 0 0
測資資訊:
記憶體限制: 64 MB
提示 :

1. 如果不熟悉直方圖,可以先試試看「b459: 圖片的直方圖」。

2. 學術上,此問題稱作 Image Thresholding,此演算法稱作 Otsu's method

3. threshold value,中文翻譯成「門檻值」、「閾值」、「臨界值」。另外還有個積非成是的「閥值」。

4. 下面左圖是環形漸層顏色,右圖是使用本題的演算法實施二值化,結果卻莫名其妙多了一條線。你能解釋原因嗎?

標籤:
影像處理
出處:
[管理者: DJWS (...) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」