โจทย์
ห้องแล็บตัดต่อภาพขอให้คุณเน้นขอบในภาพระดับสีเทา แต่ละพิกเซลเป็นค่าความสว่างตั้งแต่ 0 (ดำ) ถึง 255 (ขาว) สำหรับทุกพิกเซล ให้ดูพื้นที่ 3 × 3 รอบตัวมัน แล้วคำนวณผลรวมถ่วงน้ำหนักสองค่าด้วย Sobel kernel ดังนี้
Gx = -1 0 1 Gy = -1 -2 -1
-2 0 2 0 0 0
-1 0 1 1 2 1จุดกึ่งกลางของ kernel วางอยู่บนพิกเซลนั้น แถวบนของ kernel อยู่บนแถวด้านบน และคอลัมน์ซ้ายอยู่บนคอลัมน์ทางซ้าย นำพิกเซลข้างเคียงแต่ละตัวคูณกับน้ำหนักที่ตรงกัน แล้วรวมกันเพื่อให้ได้ gx และ gy ถ้าพิกเซลข้างเคียงอยู่นอกภาพ ให้ใช้พิกเซลบนขอบที่ใกล้ที่สุดแทน (บีบแถวให้อยู่ในช่วง 0 … rows − 1 และคอลัมน์ให้อยู่ในช่วง 0 … cols − 1) ความเข้มของขอบคือ min(255, |gx| + |gy|) จึงเป็นจำนวนเต็มระหว่าง 0 ถึง 255 เสมอ ต้องอ่านค่าจากภาพต้นฉบับทุกครั้ง ห้ามอ่านจากพิกเซลที่เปลี่ยนไปแล้ว
จงเขียน edge_detection(image)
อินพุต
image: ภาพในรูปลิสต์ของแถว ทุกแถวยาวเท่ากัน
เอาต์พุต
คืนค่าตารางใหม่ขนาดเท่าเดิม โดยแต่ละค่าคือความเข้มของขอบที่พิกเซลนั้น
เงื่อนไข
1 ≤ rows, cols ≤ 50
0 ≤ pixel ≤ 255
ตัวอย่าง
อินพุต:
image = [
[10, 10, 10],
[10, 10, 10],
[10, 10, 10]
]
ผลลัพธ์ที่คาดหวัง:
expected = [
[0, 0, 0],
[0, 0, 0],
[0, 0, 0]
]
อินพุต:
std::vector<std::vector<long long>> image = {
{10, 10, 10},
{10, 10, 10},
{10, 10, 10}
};
ผลลัพธ์ที่คาดหวัง:
std::vector<std::vector<long long>> expected = {
{0, 0, 0},
{0, 0, 0},
{0, 0, 0}
};
อินพุต:
long[][] image = new long[][] {
new long[] {10, 10, 10},
new long[] {10, 10, 10},
new long[] {10, 10, 10}
};
ผลลัพธ์ที่คาดหวัง:
long[][] expected = new long[][] {
new long[] {0, 0, 0},
new long[] {0, 0, 0},
new long[] {0, 0, 0}
};
คำอธิบาย
ทุกพื้นที่มีค่าเท่ากันหมด ผลรวมทั้งสองจึงเป็น 0 ทุกตำแหน่ง และผลลัพธ์เป็นศูนย์ทั้งหมด
อินพุต:
image = [
[0, 0, 100],
[0, 0, 100],
[0, 0, 100]
]
ผลลัพธ์ที่คาดหวัง:
expected = [
[0, 255, 255],
[0, 255, 255],
[0, 255, 255]
]
อินพุต:
std::vector<std::vector<long long>> image = {
{0, 0, 100},
{0, 0, 100},
{0, 0, 100}
};
ผลลัพธ์ที่คาดหวัง:
std::vector<std::vector<long long>> expected = {
{0, 255, 255},
{0, 255, 255},
{0, 255, 255}
};
อินพุต:
long[][] image = new long[][] {
new long[] {0, 0, 100},
new long[] {0, 0, 100},
new long[] {0, 0, 100}
};
ผลลัพธ์ที่คาดหวัง:
long[][] expected = new long[][] {
new long[] {0, 255, 255},
new long[] {0, 255, 255},
new long[] {0, 255, 255}
};
คำอธิบาย
สำหรับพิกเซลตรงกลาง คอลัมน์ขวาให้ 100 + 200 + 100 = 400 และคอลัมน์ซ้ายให้ 0 จึงได้ gx = 400, gy = 0 และความเข้มถูกจำกัดไว้ที่ 255 พิกเซลในคอลัมน์ขวาก็ได้ 255 เช่นกัน เพราะเพื่อนบ้านทางขวาที่ไม่มีอยู่จะใช้ค่าขอบ 100 แทน ส่วนพิกเซลในคอลัมน์ซ้ายเห็นแต่ 0 ทั้งสองด้าน จึงยังเป็น 0
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
เขียนฟังก์ชันช่วยที่คืนค่าพิกเซลที่ (r, c) หลังจากบีบ r และ c ให้อยู่ในตารางแล้ว
คำใบ้ 2
gx ใช้เฉพาะคอลัมน์ซ้ายและขวาของพื้นที่ข้างเคียง ส่วน gy ใช้เฉพาะแถวบนและล่าง
คำใบ้ 3
สร้างเอาต์พุตในตารางแยกต่างหาก ถ้าแก้อินพุตไประหว่างทาง พิกเซลที่ตามมาจะผิด
ความซับซ้อนที่คาดหวัง
เวลา O(rows × cols), หน่วยความจำเพิ่ม O(rows × cols)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน