Bài 27: Thu nhỏ ảnh mà không làm méo người – Thuật toán seam carving và quy hoạch động

Bạn có một bức ảnh ngang muốn đăng lên mạng xã hội dạng dọc. Cắt bớt thì mất người ở rìa, co lại thì mọi người bị "béo lùn". Năm 2007, hai nhà khoa học đưa ra một cách thông minh: chỉ xóa những phần "nhàm chán" của bức ảnh, từng đường một.

Bài thứ hai mươi bảy của chuyên mục "Thuật toán trong đời sống": thuật toán seam carving, năng lượng ảnh và quy hoạch động.

1. Ý tưởng của seam carving

Tại hội nghị đồ họa máy tính SIGGRAPH 2007, Shai Avidan và Ariel Shamir công bố bài báo "Seam Carving for Content-Aware Image Resizing". Ý tưởng:

1. Tính năng lượng của mỗi điểm ảnh: điểm khác biệt nhiều so với xung quanh (cạnh người, đồ vật) có năng lượng cao; điểm thuộc nền trời, mặt nước đồng màu có năng lượng thấp.
2. Tìm một đường nối (seam) từ trên xuống dưới, mỗi hàng một điểm, hai hàng liền nhau lệch tối đa 1 cột, sao cho tổng năng lượng nhỏ nhất.
3. Xóa đường nối đó – ảnh hẹp đi 1 cột. Lặp lại đến khi đủ kích thước.

2. Tìm đường nối bằng quy hoạch động

Gọi dp[r][c] là năng lượng nhỏ nhất của một đường đi từ hàng trên cùng xuống điểm (r, c). Khi đó:

dp[r][c] = năng_lượng[r][c] + min(dp[r-1][c-1], dp[r-1][c], dp[r-1][c+1])

Ô nhỏ nhất ở hàng cuối là điểm kết thúc của đường nối tốt nhất; ta truy vết ngược lên để biết cả đường. Mỗi lần tìm chỉ mất thời gian tỉ lệ với số điểm ảnh – đây đúng là dạng bài "đường đi trên lưới" quen thuộc.

Thử với một "bức ảnh" xám 5 × 10: hai "người" sáng ở cột 2 và cột 7 (giá trị 9 và 8), nền trời giá trị 1 và một đám mây nhỏ (giá trị 2):

Seam carving: thu hẹp ảnh 3 cột

#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<int>> Grid;
// Năng lượng = tổng độ chênh sáng với 4 ô kề
Grid energy(const Grid& a){
    int H = a.size(), W = a[0].size(); Grid e(H, vector<int>(W));
    auto g = [&](int r, int c){ return a[min(max(r, 0), H-1)][min(max(c, 0), W-1)]; };
    int dr[] = {0, 0, 1, -1}, dc[] = {1, -1, 0, 0};
    for(int r = 0; r < H; r++) for(int c = 0; c < W; c++)
        for(int k = 0; k < 4; k++) e[r][c] += abs(g(r, c) - g(r + dr[k], c + dc[k]));
    return e;
}
int main(){
    Grid img = {{1,1,9,1,1,1,1,8,1,1},
                {1,1,9,1,2,1,1,8,1,1},
                {1,1,9,1,2,2,1,8,1,1},
                {1,1,9,1,1,1,1,8,1,1},
                {1,1,9,1,1,1,1,8,1,1}};          // hai "người" sáng trên nền trời
    for(int step = 1; step <= 3; step++){
        Grid e = energy(img); int H = e.size(), W = e[0].size();
        Grid dp = e;                               // dp[r][c]: đường năng lượng nhỏ nhất tới (r, c)
        for(int r = 1; r < H; r++) for(int c = 0; c < W; c++){
            int best = INT_MAX;
            for(int k = c - 1; k <= c + 1; k++) if(k >= 0 && k < W) best = min(best, dp[r-1][k]);
            dp[r][c] += best;
        }
        int c = min_element(dp[H-1].begin(), dp[H-1].end()) - dp[H-1].begin();
        int cost = dp[H-1][c];
        vector<int> seam(H); seam[H-1] = c;
        for(int r = H - 1; r > 0; r--){            // truy vết ngược
            int bk = -1;
            for(int k = c - 1; k <= c + 1; k++) if(k >= 0 && k < W && (bk < 0 || dp[r-1][k] < dp[r-1][bk])) bk = k;
            c = bk; seam[r-1] = c;
        }
        printf("Lan %d: xoa duong cot [", step);
        for(int r = 0; r < H; r++) printf("%d%s", seam[r], r + 1 < H ? ", " : "");
        printf("], nang luong %d\n", cost);
        for(int r = 0; r < H; r++) img[r].erase(img[r].begin() + seam[r]);
    }
    for(auto& row : img){ for(int i = 0; i < (int)row.size(); i++) printf("%d%c", row[i], i + 1 < (int)row.size() ? ' ' : '\n'); }
}

# Ảnh xám 5 x 10 (độ sáng 0–9): hai "người" sáng (cột 2 và cột 7) trên nền trời, có một đám mây nhỏ
img = [[1, 1, 9, 1, 1, 1, 1, 8, 1, 1],
       [1, 1, 9, 1, 2, 1, 1, 8, 1, 1],
       [1, 1, 9, 1, 2, 2, 1, 8, 1, 1],
       [1, 1, 9, 1, 1, 1, 1, 8, 1, 1],
       [1, 1, 9, 1, 1, 1, 1, 8, 1, 1]]

def energy(a):
    # Năng lượng = tổng độ chênh sáng với 4 ô kề (trái, phải, trên, dưới)
    H, W = len(a), len(a[0])
    g = lambda r, c: a[min(max(r, 0), H - 1)][min(max(c, 0), W - 1)]
    return [[sum(abs(g(r, c) - g(r + dr, c + dc)) for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)))
             for c in range(W)] for r in range(H)]

def find_seam(e):
    # Quy hoạch động: dp[r][c] = năng lượng nhỏ nhất của đường từ hàng 0 xuống ô (r, c)
    H, W = len(e), len(e[0])
    dp = [e[0][:]] + [[0] * W for _ in range(H - 1)]
    for r in range(1, H):
        for c in range(W):
            dp[r][c] = e[r][c] + min(dp[r - 1][k] for k in (c - 1, c, c + 1) if 0 <= k < W)
    c = min(range(W), key=lambda k: dp[H - 1][k])          # truy vết ngược từ hàng cuối
    seam = [c]
    for r in range(H - 1, 0, -1):
        c = min((k for k in (c - 1, c, c + 1) if 0 <= k < W), key=lambda k: dp[r - 1][k])
        seam.append(c)
    return seam[::-1], min(dp[H - 1])

for step in range(3):                                      # thu hẹp ảnh 3 cột
    seam, cost = find_seam(energy(img))
    print(f"Lan {step + 1}: xoa duong cot {seam}, nang luong {cost}")
    img = [row[:c] + row[c + 1:] for row, c in zip(img, seam)]
for row in img: print(" ".join(map(str, row)))

Kết quả chạy:

Lan 1: xoa duong cot [0, 0, 0, 0, 0], nang luong 0
Lan 2: xoa duong cot [8, 8, 8, 8, 8], nang luong 0
Lan 3: xoa duong cot [4, 4, 3, 3, 3], nang luong 5
1 9 1 1 1 8 1
1 9 1 2 1 8 1
1 9 1 2 1 8 1
1 9 1 1 1 8 1
1 9 1 1 1 8 1

Sau 3 lần, ảnh hẹp từ 10 xuống 7 cột nhưng hai "người" (giá trị 9 và 8) vẫn nguyên vẹn. Hai lần đầu xóa nền trời ở hai mép ảnh. Ở lần thứ ba, phần trời còn lại đều nằm sát hai "người" hoặc đám mây, nên đường nối uốn cong (cột 4 rồi cột 3) và chỉ lấy đi một ô của đám mây nhỏ – phần ít quan trọng nhất còn lại.

So sánh: nếu co ảnh đều, mọi cột bị ép lại và hai "người" bị biến dạng; nếu cắt mép, có thể mất người đứng ở rìa ảnh. Seam carving chỉ lấy đi những phần ít thông tin nhất.

3. Từ phòng thí nghiệm đến Photoshop

• Adobe Photoshop có công cụ Content-Aware Scale: thay đổi kích thước ảnh mà vẫn giữ các chi tiết quan trọng, người dùng còn có thể đánh dấu vùng cần bảo vệ. Theo Wikipedia, tính năng này xuất hiện từ Photoshop CS4, sau khi Adobe được cấp phép công nghệ seam carving.
• Seam carving được dùng làm ví dụ dạy quy hoạch động ở nhiều trường đại học, ví dụ khóa 18.S191 của MIT (bài giảng của Grant Sanderson – kênh 3Blue1Brown) và bài tập lớn của môn COS 226 tại Đại học Princeton.

4. Bạn học được gì từ đây?

• Một bài toán xử lý ảnh trông phức tạp hóa ra là quy hoạch động trên lưới – dạng bài bạn có thể gặp trong đề HSG.
• Định nghĩa đúng "năng lượng" (thế nào là quan trọng) là chìa khóa của thuật toán.
• Truy vết ngược bảng quy hoạch động giúp tìm ra chính lời giải, không chỉ giá trị tối ưu.

Bài tập luyện tập

• CSES – Grid Paths I (đếm đường đi trên lưới bằng quy hoạch động)
• Sửa code để xóa đường nối ngang (giảm chiều cao ảnh).
• Thử tự tính năng lượng cho một bức ảnh thật bằng thư viện Pillow (Python).

📖 ĐỌC TIẾP: THUẬT TOÁN TRONG ĐỜI SỐNG

Bài 1: Google Maps tìm đường nhanh nhất thế nào? Thuật toán Dijkstra và A* trong đời sống

Đọc tiếp: Google Maps & Dijkstra →

← Bài trước: xếp thùng & cái túiXem tất cả 27 bài →

Nguồn tham khảo

• Avidan & Shamir (2007) – Seam Carving for Content-Aware Image Resizing, ACM SIGGRAPH
• Adobe Help – Content-Aware Scale in Photoshop
• Wikipedia – Seam carving
• 3Blue1Brown / MIT 18.S191 – Seam carving
• Princeton COS 226 – Seam Carving assignment