b441. 延展尺寸 - 高中生程式解題系統

內容

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

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

小正方形重疊一半的寬度（四捨五入）。於重疊區域當中，找到像素差異總和最小的路徑（兩個像素的顏色差異，設定為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
公開測資點#0 (20%): 1.0s , <1M
公開測資點#1 (20%): 1.0s , <1M
公開測資點#2 (20%): 1.0s , <1M
公開測資點#3 (20%): 1.0s , <1M
公開測資點#4 (20%): 1.0s , <1M

提示：

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

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

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

標籤:

影像處理

出處:

[管理者： DJWS (...) ]

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