Tất cả thử thách
Khó 0 đã giải Tỷ lệ chấp nhận 0%

Phát hiện biên (bộ lọc Sobel)

Áp dụng bộ lọc Sobel lên lưới pixel của ảnh xám và trả về độ mạnh của biên tại từng pixel.

Bạn sẽ học được gì

  • Duyệt vùng lân cận 3 × 3 của mọi ô
  • Xử lý pixel ở biên bằng cách kẹp tọa độ
  • Ghi kết quả vào lưới mới để không ghi đè đầu vào

Đề bài

Xem bản gốc (English)

Một phòng thí nghiệm chỉnh sửa ảnh nhờ bạn làm nổi bật các đường biên trong một bức ảnh xám. Mỗi pixel là một độ sáng từ 0 (đen) đến 255 (trắng). Với mỗi pixel, xét vùng lân cận 3 × 3 của nó và tính hai tổng có trọng số bằng các nhân (kernel) Sobel:

Gx = -1  0  1      Gy = -1 -2 -1
     -2  0  2            0  0  0
     -1  0  1            1  2  1

Tâm của nhân đặt trùng với pixel đang xét, hàng trên của nhân ứng với hàng phía trên, cột trái ứng với cột bên trái. Nhân mỗi pixel lân cận với trọng số tương ứng rồi cộng lại để được gx và gy. Khi một pixel lân cận rơi ra ngoài ảnh, hãy dùng pixel gần nhất trên biên thay cho nó (kẹp chỉ số hàng vào đoạn 0 … rows − 1 và chỉ số cột vào đoạn 0 … cols − 1). Độ mạnh của biên là min(255, |gx| + |gy|), nên nó luôn là số nguyên từ 0 đến 255. Luôn đọc từ ảnh gốc, không đọc từ những pixel bạn đã thay đổi.

Hãy viết edge_detection(image).

Đầu vào

image: Bức ảnh dưới dạng danh sách các hàng; mọi hàng có cùng độ dài.

Đầu ra

Trả về một lưới mới cùng kích thước, mỗi giá trị là độ mạnh của biên tại pixel tương ứng.

Ràng buộc

1 ≤ rows, cols ≤ 50

0 ≤ pixel ≤ 255

Ví dụ

Ví dụ 1
Đầu vào:
image = [
    [10, 10, 10],
    [10, 10, 10],
    [10, 10, 10]
]

Kết quả mong đợi:
expected = [
    [0, 0, 0],
    [0, 0, 0],
    [0, 0, 0]
]
Đầu vào:
std::vector<std::vector<long long>> image = {
    {10, 10, 10},
    {10, 10, 10},
    {10, 10, 10}
};

Kết quả mong đợi:
std::vector<std::vector<long long>> expected = {
    {0, 0, 0},
    {0, 0, 0},
    {0, 0, 0}
};
Đầu vào:
long[][] image = new long[][] {
    new long[] {10, 10, 10},
    new long[] {10, 10, 10},
    new long[] {10, 10, 10}
};

Kết quả mong đợi:
long[][] expected = new long[][] {
    new long[] {0, 0, 0},
    new long[] {0, 0, 0},
    new long[] {0, 0, 0}
};

Giải thích

Mọi vùng lân cận đều phẳng, nên cả hai tổng đều bằng 0 ở mọi nơi và kết quả toàn số 0.

Ví dụ 2
Đầu vào:
image = [
    [0, 0, 100],
    [0, 0, 100],
    [0, 0, 100]
]

Kết quả mong đợi:
expected = [
    [0, 255, 255],
    [0, 255, 255],
    [0, 255, 255]
]
Đầu vào:
std::vector<std::vector<long long>> image = {
    {0, 0, 100},
    {0, 0, 100},
    {0, 0, 100}
};

Kết quả mong đợi:
std::vector<std::vector<long long>> expected = {
    {0, 255, 255},
    {0, 255, 255},
    {0, 255, 255}
};
Đầu vào:
long[][] image = new long[][] {
    new long[] {0, 0, 100},
    new long[] {0, 0, 100},
    new long[] {0, 0, 100}
};

Kết quả mong đợi:
long[][] expected = new long[][] {
    new long[] {0, 255, 255},
    new long[] {0, 255, 255},
    new long[] {0, 255, 255}
};

Giải thích

Với pixel ở giữa, cột phải cộng được 100 + 200 + 100 = 400 còn cột trái cộng được 0, nên gx = 400, gy = 0 và độ mạnh bị chặn ở 255. Các pixel ở cột phải cũng được 255 vì những lân cận bên phải bị thiếu được lấy bằng giá trị biên 100. Các pixel ở cột trái chỉ thấy 0 ở cả hai bên nên vẫn là 0.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Viết một hàm phụ trả về pixel tại (r, c) sau khi đã kẹp r và c vào trong lưới.

Gợi ý 2

gx chỉ dùng cột trái và cột phải của vùng lân cận; gy chỉ dùng hàng trên và hàng dưới.

Gợi ý 3

Ghi kết quả vào một lưới riêng; sửa trực tiếp đầu vào trong lúc duyệt sẽ làm sai các pixel phía sau.

Độ phức tạp mong đợi

thời gian O(rows × cols), bộ nhớ phụ O(rows × cols)

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.