โจทย์ทั้งหมด
ยาก 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

การตรวจจับขอบภาพ (ฟิลเตอร์ Sobel)

ใช้ฟิลเตอร์ Sobel กับตารางพิกเซลระดับสีเทา แล้วคืนค่าความเข้มของขอบในทุกพิกเซล

สิ่งที่คุณจะได้เรียนรู้

  • เข้าถึงพื้นที่ 3 × 3 รอบทุกช่อง
  • จัดการพิกเซลที่ขอบภาพด้วยการบีบพิกัดให้อยู่ในช่วง
  • เขียนผลลัพธ์ลงตารางใหม่เพื่อไม่ให้อินพุตถูกเขียนทับ

โจทย์

ห้องแล็บตัดต่อภาพขอให้คุณเน้นขอบในภาพระดับสีเทา แต่ละพิกเซลเป็นค่าความสว่างตั้งแต่ 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

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
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 ทุกตำแหน่ง และผลลัพธ์เป็นศูนย์ทั้งหมด

ตัวอย่างที่ 2
อินพุต:
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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก