Đề bài
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 1Tâ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ụ
Đầ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.
Đầ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.