Hough Transform — จุดในภาพ กลายเป็นเส้นโค้งใน Parameter Space ได้อย่างไร

จุดหนึ่งจุดในภาพผ่านเส้นตรงได้ หลายแบบไม่จำกัด (สโลปไหนก็ได้) — Hough transform แปลง "จุดนั้นอาจอยู่บนเส้นตรงไหนได้บ้าง" ให้กลายเป็นเส้นโค้ง/เส้นตรงหนึ่งเส้นใน parameter space

โดเมนที่คุ้นเคย: y = mx + c — จุด (x,y) หนึ่งจุด กลายเป็นเส้นตรง c = y − m·x ในปริภูมิ (m, c) แทน (สลับบทบาท x,y กับ m,c)

ปัญหาของ (m,c): เส้นตั้งฉาก (vertical) มี slope m = ∞ ซึ่งไม่มีที่ยืนในกราฟที่มีขอบเขตจำกัด — ลองพรีเซ็ต "เส้นเกือบตั้งฉาก" ดูที่ข้อ 2

ทางแก้: parametrize ด้วย ρ = x·cosθ + y·sinθ แทน — จุด (x,y) กลายเป็นเส้นโค้ง sine curve ในปริภูมิ (θ, ρ) ซึ่ง θ ครอบคลุมทุกทิศทางได้โดยไม่มีค่า infinite เลย

จุดที่collinear กันจริง ไม่ว่าจะมองในโดเมนไหน เส้นโค้ง/เส้นตรงของทุกจุดจะไปตัดกันที่ตำแหน่งพารามิเตอร์เดียวกันเสมอ — จุดตัดสะสมโหวตสูง กลายเป็น peak ที่บอกว่าเส้นไหนคือคำตอบ

จุด noise ที่ไม่ได้อยู่บนเส้นไหนเลย ก็ยังโหวตเหมือนกัน แต่เส้นโค้ง/เส้นตรงของมันกระจายไม่ตรงกับใคร จึงไม่สะสมเป็น peak — ลองเอาเมาส์ชี้จุดในข้อ 1 ดูเส้นของมันเด่นขึ้นมาในทั้งสองโดเมน

จุดหนึ่งจุดในภาพผ่านวงกลมได้ หลายแบบไม่จำกัด (ศูนย์กลาง/รัศมีต่างกัน) — โมเดลสมการวงกลม (x−a)² + (y−b)² = r² มี 3 พารามิเตอร์ (a, b, r)

เดโมนี้กำหนด r คงที่ค่าหนึ่งก่อน (เลื่อนดูได้) — จุด (x,y) โหวตเป็น วงกลมรัศมี r เดียวกัน รอบจุดนั้นเองในปริภูมิ (a, b) ของศูนย์กลางที่เป็นไปได้ — ความสมมาตรที่สวยงามของปัญหานี้

จุดที่อยู่บนวงกลมขนาดเดียวกันจริง วงกลมโหวตของทุกจุดจะไปตัดกันที่ตำแหน่ง (a,b) เดียวกันเสมอ เมื่อ r ที่เลือกตรงกับรัศมีจริง

ลองเลื่อน r ไปเรื่อย ๆ — โหวตสูงสุดจะแหลมที่สุดพอดีที่รัศมีจริง ของวงกลมในภาพ แล้วอ่อนลงทันทีถ้า r ผิดไปแม้เพียงเล็กน้อย

จุด noise ก็ยังโหวตเหมือนกัน แต่วงกลมของมันกระจายไม่ตรงกับใคร จึงไม่สะสมเป็น peak — แม้มีแค่บางส่วนของวงกลม (ส่วนโค้ง) ก็ยังหาศูนย์กลางเจอได้

ลองเอาเมาส์ชี้จุดในข้อ 1 ดูวงกลมโหวตของมันเด่นขึ้นมาในข้อ 2 แล้วดูกราฟโหวตสูงสุดเทียบกับ r ว่ายอดแหลมอยู่ตรงไหน