解題區/解題區 - Zerojudge

b424. 圖片縮放

contents

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

Problem

此題有精準度誤差，未能提交成功。

進行圖片縮放，有兩種方案來補足缺失或者是簡化的像素計算。不管縮放如何，在新的坐標系的點可以對應到舊坐標系中，並且會有四個像素點 (正方形) 包含這個對應點，有可能會有所缺失，但至少包含一個點。

  • 最近鄰點法 (nearest-neighbor approach)
    找正方形中哪個點最靠近新的對應點，就令其像素顏色等於最靠近的點。
  • 雙線性內插 (bi-linear interpolation)
    顏色由相鄰四個點決定，使用雙性內插來得到新的像素顏色。

特別注意，雖然邊長根據縮放四捨五入，但在計算時先不考慮最終結果的長寬，否則縮放倍率也會跟著四捨五入。

可以參考 中央大學影像處理實驗室 課程 講義第二章

Sample Input

1
2
3
2 2 0
2 1 
1 2 3 255 4 5 6 255

Sample Output

1
2
3
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

Solution

除了陷阱的邊長四捨五入外，精準度根據雙性內插影響。

雙線性內插可以由下列兩種方案，或者還有其他的

  • 兩次 lerp 插值，先水平後垂直或者先垂直後水平
  • 特別的 $f(x, y) = (1-a)(1-b) g(j, k) + a(1-b) g(j+1, k) + (1-a) b g(j, k+1) + a b g(j+1, k+1)$

特別發現到，第二種方案沒有用到除法運算，但乘法運算的優先順序會影響到誤差。然而我的代碼是混用造成難以評估的誤差。關於第二種方案的坐標系，可以參考講義中的圖示。

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
#include <bits/stdc++.h> 
using namespace std;
const double eps = 1e-18;
class IMAGE {
public:
    struct Pixel {
        long double r, g, b, a;
        Pixel(long double x = 0, long double y = 0, long double z = 0, long double w = 0):
            r(x), g(y), b(z), a(w) {}
        void read() {
            int p1, p2, p3, p4;
            scanf("%d %d %d %d", &p1, &p2, &p3, &p4);
            r = p1, g = p2, b = p3, a = p4;
        }
        Pixel operator-(const Pixel &x) const {
        	return Pixel(r-x.r, g-x.g, b-x.b, a-x.a);
    	}
    	Pixel operator+(const Pixel &x) const {
        	return Pixel(r+x.r, g+x.g, b+x.b, a+x.a);
    	}
    	Pixel operator*(const long double x) const {
        	return Pixel(r*x, g*x, b*x, a*x);
    	}
        Pixel operator/(const long double x) const {
        	return Pixel(r/x, g/x, b/x, a/x);
    	}
    	void print() {
    		double p1 = r, p2 = g, p3 = b, p4 = a;
    		printf("%.0lf %.0lf %.0lf %.0lf", p1 + eps, p2 + eps, p3 + eps, p4 + eps);
    	}
    };
    int W, H;
    static const int MAXN = 512;
    Pixel data[MAXN][MAXN], tmp[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();
    }
    int isValid(int x, int y) {
        return x >= 0 && y >= 0 && x < H && y < W;
    }
    void resize(long double SX, long double SY, int trans = 0) {
        if (trans != 0 && trans != 1)
            return ;			
        int rW = (int) round(SX * W);
        int rH = (int) round(SY * H);
        if (rW > 256 || rH > 256 || rW <= 0 || rH <= 0)
            return ;
        for (int i = 0; i < rH; i++) {
            for (int j = 0; j < rW; j++) {
                long double x = i / SY;
                long double y = j / SX;
                int lx, rx, ly, ry;
                lx = floor(x), rx = ceil(x);
                ly = floor(y), ry = ceil(y);
                
                Pixel v[] = {data[lx][ly], data[lx][ry], data[rx][ly], data[rx][ry]};
                int px[] = {lx, lx, rx, rx};
                int py[] = {ly, ry, ly, ry};
                if (trans == 0) {
                    Pixel t1, t2;
                    if (isValid(px[0], py[0]) && isValid(px[1], py[1]) && isValid(px[2], py[2]) && isValid(px[3], py[3])) {
                        long double a = x - lx, b = y - ly;
                        tmp[i][j] = v[0] * (1 - a) * (1 - b) + v[2] * a * (1 - b)
                                    + v[1] * (1 - a) * b + v[3] * a * b;
                    } else if (isValid(px[0], py[0]) && isValid(px[2], py[2])) {
                        if (rx != lx)
                            tmp[i][j] = v[0] + (v[2] - v[0]) * ((x - lx) / (rx - lx));
                        else
                            tmp[i][j] = v[0];
                    } else if (isValid(px[0], py[0]) && isValid(px[1], py[1])) {
                        if (ry != ly)
                            tmp[i][j] = v[0] + (v[1] - v[0]) * ((y - ly) / (ry - ly));
                        else
                            tmp[i][j] = v[0];
                    } else if (isValid(px[0], py[0])) {
                        tmp[i][j] = v[0];
                    } else {
                        puts("WTF");
                    }
                } else {
                    int c = -1;
                    double mndist;
                    for (int k = 0; k < 4; k++) {
                        if (!isValid(px[k], py[k]))
                            continue;
                        double d = (x-px[k])*(x-px[k])+(y-py[k])*(y-py[k]);
                        if (c == -1 || mndist > d)
                            c = k, mndist = d;
                    }
                    tmp[i][j] = data[px[c]][py[c]];
                }
            }
        }
        W = rW, H = rH;
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                data[i][j] = tmp[i][j];
    }
    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() {
    double X, Y;
    int TYPE;
    scanf("%lf %lf %d", &X, &Y, &TYPE);
    test.read();
    test.resize(X, Y, TYPE);
    test.print();
    return 0;
}