b424: 圖片縮放
Tags : 影像處理
Accepted rate : 9人/12人 ( 75% ) [非即時]
評分方式:
Special

最近更新 : 2022-10-27 20:21

Content

圖片縮放隨處可見。微軟小畫家、Word、PowerPoint都有圖片縮放功能。圖片縮放乍看稀鬆平常,其實裡頭大有學問。

首先,左上角像素座標訂為(0,0),右下角像素座標訂為(W-1,H-1),W與H是圖片寬高。

狀況一:圖片放大3倍,像素座標乘以3,得到一張沒有填滿的圖片。沒有填滿的地方,應該設定成什麼顏色呢?



數學家將之連結到函數內插的概念。高中數學曾經談過一元函數的內插,演算法是線性內插法。圖片縮放需要二元函數的內插,演算法非常多種,而本題採用雙線性內插法、最近鄰居內插法。


狀況二:圖片放大3.3倍,像素座標乘以3.3,可是像素座標必須是整數。怎麼辦?

採用反推回去的方式。針對新圖片的一個像素座標,逆向縮放座標。然後找出鄰近四個像素,進行內插。



雙線性內插法,即是兩次線性內插,先橫向,再直向。內插需要兩個端點,如果不幸欠缺其中一個端點,則直接設定為另一端點的數值。不可能同時欠缺兩個端點。

最近鄰居內插法,直接拷貝距離最近的像素。如果距離一樣,優先順序是左上、右上、左下、右下。



至此就是圖片縮放的演算法過程。


本題當中,圖片縮放的指令格式如下:

SX SY TYPE

SX SY 分別是橫向與直向的縮放倍率。縮放結果四捨五入。

TYPE 是功能類型,只有 0 與 1 兩種。0 是雙線性內插法,1 是最近鄰居內插法。RGBA 分頭計算,計算結果四捨五入。

例外處理:SX SY 是負數,不處理,令圖片保持原樣。TYPE 不是 0 與 1,不處理,令圖片保持原樣。最終圖片長寬大於 256、小於等於0,不處理,令圖片保持原樣。

指令範例:2 2 0,圖片寬高變兩倍,採用雙線性內插法。

Input

首先是一道指令:兩個浮點數 SX SY、一個整數 TYPE (-231 <= TYPE <= 231-1)。

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

Output

請輸出處理後的圖片。

由於雙線性內插有多種計算公式,所以雙線性內插採用Special Judge:一個像素的RGBA值,差異超過±1視為NA,未超過±1視為誤差。所有像素的誤差,總計超過5%視為NA,未超過5%視為AC。

Sample Input #1
2 2 0
2 1
1 2 3 255 4 5 6 255
Sample Output #1
4 2
1 2 3 255 3 4 5 255 4 5 6 255 4 5 6 255
1 2 3 255 3 4 5 255 4 5 6 255 4 5 6 255
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (8%): 1.0s , <1M
公開 測資點#1 (8%): 1.0s , <1M
公開 測資點#2 (8%): 1.0s , <1M
公開 測資點#3 (8%): 1.0s , <1M
公開 測資點#4 (8%): 1.0s , <1M
公開 測資點#5 (8%): 1.0s , <1M
公開 測資點#6 (8%): 1.0s , <1M
公開 測資點#7 (8%): 1.0s , <1M
公開 測資點#8 (8%): 1.0s , <1M
公開 測資點#9 (8%): 1.0s , <1M
公開 測資點#10 (8%): 1.0s , <1M
公開 測資點#11 (12%): 1.0s , <1M
Hint :

1. 圖片放大再縮小,通常不會得到原本圖片!因為過程當中有四捨五入!解決此題之後,大家應該有更深刻的理解。

2. 雙線性內插,無論哪個方向先內插,理論上結果一樣。但是實務上卻有浮點數誤差。

3. 圖片縮放最主要的課題是抗鋸齒。近鄰內插、雙線性內插的抗鋸齒效果都很差。維基百科「Image Scaling」介紹了其他演算法,有興趣的人可以進一步鑽研。例如2×SaI演算法,就是任天堂Gameboy模擬器、畫面放大兩倍的演算法。

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


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