b460: 判若黑白
Tags : 影像處理
Accepted rate : 7人/19人 ( 37% ) [非即時]
評分方式:
Tolerant

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

Content


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

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



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

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



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



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

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

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

Input

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

Output

請輸出處理過的圖片。

 

Sample Input #1
1 2
128 128 128
127 127 127
Sample Output #1
1 2
255 255 255
0 0 0
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (16%): 1.0s , <1K
公開 測資點#1 (16%): 1.0s , <1K
公開 測資點#2 (16%): 1.0s , <1M
公開 測資點#3 (16%): 1.0s , <1M
公開 測資點#4 (16%): 1.0s , <1M
公開 測資點#5 (20%): 1.0s , <1M
Hint :

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

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

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

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

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


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」