b438: 裁剪尺寸
Tags : 影像處理
Accepted rate : 11人/15人 ( 73% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-10-27 22:12

Content


有辦法縮小圖片,但是不壓扁景物嗎?

那就去掉圖片最平凡的地方吧!最平凡的地方,也許就是變化最小的地方。變化最小的地方,也許就是梯度最小的地方。實驗看看吧!

運用 Sobel Operator,每個像素的變化量,設定成|SXR| + |SYR| + |SXG| + |SYG| + |SXB| + |SYB|。嘗試找到一條變化總和最小的路徑,起點在圖片上緣某個像素,終點在圖片下緣某個像素,每步只能走向「左下↙」、「下↓」、「右下↘」的相鄰像素,每步只能選擇其中一個方向前進。


刪除一條變化總和最小的路徑,圖片寬度剛好減少一!反覆刪除路徑,直到圖片變成預定尺寸。

如果變化總和最小的路徑有許多條,以尾端最靠左的路徑為主。

Input

首先是一個整數 N (0 <= N < W),請刪除 N 條路徑。

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

Output

請輸出處理後的圖片。

 

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

1. 關於Sobel operator的細節,請參考「b436: 圖片的梯度再進化」。

2. 學術上,此問題稱作 Content-Aware Image Resizing,此演算法稱作 Seam Carving。原理是:讓路徑盡量不要穿越景物輪廓,那麼刪除此路徑便不會影響景物形狀。

3. 一口氣找到N條路徑,一口氣刪除N條路徑,理論上才是最佳結果。因為演算法時間複雜度很高(雖然是多項式時間),所以沒有人這麼做,而是採用本題的greedy策略,逐次找到一條路徑,逐次刪除一條路徑。

4. 並不是所有圖片都適合套用此演算法。例如這張:

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


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