b441. 延展尺寸
標籤 : 影像處理
通過比率 : 10人/11人 ( 91% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-08-27 16:54

內容

 

 



圖片邊界繼續綿延,變成更大張的圖片。

方法很簡單,採用拼圖方式,從原圖片隨機擷取多個相同尺寸的小正方形,拼成更大的圖片。拼圖順序是由左到右,再由上到下。本題簡化問題難度,只做由左到右。

小正方形重疊一半的寬度(四捨五入)。於重疊區域當中,找到像素差異總和最小的路徑(兩個像素的顏色差異,設定為RGB的直線距離四捨五入),作為拼圖接縫(接縫及接縫以右,屬於新的小正方形)。起點在上緣某個像素,終點在下緣某個像素,每步只能走向「左下↙」、「下↓」、「右下↘」的相鄰像素,每步只能選擇其中一個方向前進。




當上述的最佳路徑,像素差異總和大於等於round(L*255/8),表示拼起來效果太差。此時捨棄當前的小正方形,重新找一個小正方形。如果連續捨棄50次,則放棄處理,輸出原始圖片。

另外,為了符合 ZeroJudge 的批改模式,請大家一律採用相同的亂數生成器,擷取小正方形的左上角座標。一步步拼圖、視需要擷取。

long long int seed = 0;

int random() {
return seed = ( seed * 9301 + 49297 ) % 233280;
}

void getSquarePosition(int& x, int& y) {
x = (W <= L) ? 0 : random() % (W - L); // 寬的方向
y = (H <= L) ? 0 : random() % (H - L); // 高的方向
}
輸入說明

首先是一道指令:兩個整數 L N (2 <= L <= W, H) (1 <= N <= 5),L是小正方形尺寸,N是小正方形數量。

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

輸出說明

請輸出處理後的圖片。

 

範例輸入 #1
2 1
2 2
1 2 3 4 5 6
7 8 9 10 11 12
範例輸出 #1
2 2
1 2 3 4 5 6
7 8 9 10 11 12
測資資訊:
記憶體限制: 64 MB
提示 :

1. 路徑的概念,也出現在「b438: 裁剪尺寸」。

2. 學術上,此問題稱作 Texture Synthesis,此演算法稱作 Image Quilting。原理是:拼圖,讓接縫處誤差越小越好。

3. 本題的最短路徑,等價於平面圖最小割。

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

本題狀況 本題討論 排行

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