解題區/解題區 - Zerojudge

b438. 裁剪尺寸

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

要讓影像的寬度減少，其一的方案就是每一列刪除一個像素，為了讓刪除更加地完善、盡可能看不出來突兀的地方，採用一個一條由上而下路徑進行刪除。

刪除路徑採用最少費用，這個費用採用 sobel operator，也就是說費用越高表示可能是邊緣像素，減少突兀就是盡可能不要去刪除到邊緣像素，這是顯而易見的方案。接著就是採用貪心方案，依序刪除 n 次路徑。

Sample Input

1
2
3
0
1 1
255 255 255

Sample Output

1
2
1 1
255 255 255

Solution

題目說明最好的選擇方案是一次 n 條不相交的由上而下的路徑，但這個定義是總花費，還是最小化最大花費路徑這是有疑惑的，若單純總花費可以採用最小費用流去完成，但複雜度對這個影像處理會可怕，點數跟邊數都是破萬，複雜度 $O(VE)$ 的算法要跑非常久，因此貪心是個好選擇。

找尋花費最小的路徑是採用 dynamic programming 的方式得到，並且要回溯得到左側最小的一條路徑。每刪除一條路徑後，sobel operator 要重新計算每一個像素的異動，刷新這一塊可以指更動路徑的右側和鄰近路徑的像素即可，這可以大幅度地增加速度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <bits/stdc++.h> 
using namespace std;
class IMAGE {
public:
    struct Pixel {
        int r, g, b;
        Pixel(int x = 0, int y = 0, int z = 0):
            r(x), g(y), b(z) {}
        void read() {
            scanf("%d %d %d", &r, &g, &b);
        }
        Pixel operator-(const Pixel &x) const {
        	return Pixel(r-x.r, g-x.g, b-x.b);
    	}
    	Pixel operator+(const Pixel &x) const {
        	return Pixel(r+x.r, g+x.g, b+x.b);
    	}
    	Pixel operator*(const int x) const {
        	return Pixel(r*x, g*x, b*x);
    	}
        Pixel operator/(const int x) const {
        	return Pixel(r/x, g/x, b/x);
    	}
    	void print() {
    		printf("%d %d %d", r, g, b);
    	}
    	int length() {
    		return abs(r) + abs(g) + abs(b);
    	}
    };
    int W, H;
    static const int MAXN = 256;
    Pixel data[MAXN][MAXN];
    int energy[MAXN][MAXN], dp[MAXN][MAXN];
    void read() {
        scanf("%d %d", &W, &H);
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                data[i][j].read();
    }
    Pixel pabs(Pixel x) {
        return Pixel(fabs(x.r), fabs(x.g), fabs(x.b));
    }
    inline Pixel getPixel(int x, int y) {
        if (x >= 0 && y >= 0 && x < H && y < W)
            return data[x][y];
        if (y < 0)	return data[min(max(x, 0), H-1)][0];
        if (y >= W)	return data[min(max(x, 0), H-1)][W-1];
        if (x < 0)	return data[0][min(max(y, 0), W-1)];
        if (x >= H)	return data[H-1][min(max(y, 0), W-1)];
        return Pixel(0, 0, 0);
    }
    int sobel(int i, int j) {
        const static int dx[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
        const static int dy[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
        const static int xw[] = {-1, 0, 1, -2, 0, 2, -1, 0, 1};
        const static int yw[] = {-1, -2, -1, 0, 0, 0, 1, 2, 1};				
        Pixel Dx(0, 0, 0), Dy(0, 0, 0);
        for (int k = 0; k < 9; k++) {
            if (xw[k])
                Dx = Dx + getPixel(i+dx[k], j+dy[k]) * xw[k];
            if (yw[k])
                Dy = Dy + getPixel(i+dx[k], j+dy[k]) * yw[k];
        }
        return Dx.length() + Dy.length();
    }
    void shrink(int n) {
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                energy[i][j] = sobel(i, j);
        int path[MAXN];
        for (int it = 0; it < n; it++) {
            shrink(path);
            for (int i = 0; i < H; i++) {
                int y = path[i];
                for (int j = y - 3; j < W; j++) {
                    if (j >= 0)
                        energy[i][j] = sobel(i, j);
                }
            }
        }
    }
    void shrink(int path[]) {
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                int &val = dp[i][j];
                if (i == 0)	val = energy[i][j];
                else {	
                    val = dp[i-1][j];
                    if (j-1 >= 0)
                        val = min(val, dp[i-1][j-1]);
                    if (j+1 < W)
                        val = min(val, dp[i-1][j+1]);
                    val += energy[i][j];
                }
            }
        }
        int st = 0;
        for (int i = 0; i < W; i++)
            if (dp[H-1][i] < dp[H-1][st])
                st = i;
        for (int i = H-1; i >= 0; i--) {
            path[i] = st;
            int v = dp[i][st] - energy[i][st];
            for (Pixel *p = &data[i][st], *q = &data[i][st+1], *end = &data[i][W]; q != end; p++, q++)
                *p = *q;
            if (i == 0)	continue;
            if (st-1 >= 0 && v == dp[i-1][st-1])
                st = st-1;
            else if (v == dp[i-1][st])
                st = st;
            else
                st = st+1;
        }
        W--;
    }
    void print() {
        printf("%d %d\n", W, H);
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                data[i][j].print(), printf("%c", j == W-1 ? '\n' : ' ');
    }
} test;
int main() {
    int n;
    scanf("%d", &n);
    test.read();
    test.shrink(n);
    test.print();
    return 0;
}