การหาขอบที่เป็นเส้นตรงด้วย Hough Line Transform

เมื่อเราหาขอบ (edge) ของรูปภาพได้แล้ว เราจะทราบได้อย่างไรว่ามีขอบที่เป็นเส้นตรงหรือไม่

เราสามารถใช้ Hough Transform เพื่อตอบคำถามนี้ได้ ดังนี้

ถ้ามีเส้นตรงใดๆ (สีดำ) ตามรูป ที่มีระยะจากจุด (0,0) ไปตั้งฉากกับเส้นตรงนั้นเท่ากับระยะ r โดยเส้นตั้งฉากนี้ทำมุมกับแกน x เป็นมุม T

เส้นตรงปกติจะมีสมการเป็น y = mx + c

แต่เราสามารถเขียนอยู่ในรูปของ polar coordinate คือ
y = (-1/tan(T)) x + (r/sin(T))
y = -cos(T)/sin(T) x  + r/sin(T)
y sin(T) = -x cos(T) + r
หรือ
y sin(T) + x cos(T) = r

โดยทั่วไปแล้ว จะกำหนดค่า T ให้อยู่ในช่วง [0, PI] และค่า r ใน [-D, D] เมื่อ D คือความยาวของเส้นทะแยงมุมของภาพ (ระยะไกลสุดของภาพที่วัดจากจุดกำเนิด)

สมมติว่าเรามีจุดๆหนึ่ง เส้นตรงที่ลากผ่านจุดนี้จะมีได้ไม่จำกัด นั่นคือ จะมีค่า r และ T มากมาย

แต่ถ้ามีจุดสองจุดขึ้นไป เส้นตรงที่ลากผ่านจุดเหล่านี้จะมีได้เส้นเดียว นั่นคือ เส้นที่มีค่า r และ T เท่ากัน

ดังนั้น เมื่อเราคิดใน polar coordinate หลักการหาขอบที่เป็นเส้นตรงด้วย Hough Transform ก็คือ

1. หาขอบของภาพด้วยวิธีิใดๆ เช่น Canny ให้ได้ผลลัพธ์เป็นขาวดำ (ขาว = ขอบ)
2. เริ่มต้นด้วย r=0, T=0 (เส้นตรงที่ทับกับแกน y)  ไล่ตรวจสอบว่ามีพิกเซลสีขาว (ขอบ) ที่อยู่บนแนวเส้นตรงนี้เท่าใด ถ้ามีเกินกว่าค่า threshold ที่กำหนด (เช่น 100 จุด) ก็ให้เก็บค่า (r,T) นี้ไว้
3. เปลี่ยนแปลงค่า r ไปเรื่อยๆ ตรวจสอบเช่นเดิม
4. เปลี่ยนแปลงค่า T ไปเรื่อยๆ ตรวจสอบเช่นเดิม
5. สุดท้ายจะได้ชุดของ (r,T) ซึ่งแต่ละคู่จะเป็นค่าของขอบเส้นตรงที่อยู่ในรูป
6. พลอตเส้นตรงเหล่านั้น

ใน OpenCV เราสามารถใช้คำสั่ง cv2.HoughLines() ดังตัวอย่างต่อไปนี้

import cv2
import numpy as np

img = cv2.imread("building.jpg")
gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
#Appy Gaussian blur to remove some noises
inoise = cv2.GaussianBlur(gray,(3,3),sigmaX=0)

#Canny
lowThresh = 50
upThresh = 200
edge = cv2.Canny(inoise,lowThresh,upThresh)

#Hough Line Transform
lines = cv2.HoughLines(edge,rho=1,theta=np.pi/180,threshold=120)
#rho = resolution of r, here 1 pixel
#theta = resolution of theta, here 1 degree
#threshold =  The minimum number of intersections to detect a line

img2 = img.copy()
#Plot detected lines
for r,theta in lines[0]:
    #(x0,y0) at the intersection point
    x0 = r*np.cos(theta)
    y0 = r*np.sin(theta)
    #(x1,y1) along the line to the left of (x0,y0) for 1000 units
    x1 =  int(x0-1000*np.sin(theta))
    y1 =  int(y0+1000*np.cos(theta))
    #(x2,y2) along the line to the right of (x0,y0) for 1000 units
    x2 =  int(x0+1000*np.sin(theta))
    y2 =  int(y0-1000*np.cos(theta))
    cv2.line(img2,(x1,y1),(x2,y2),(0,255,0),1)

cv2.imshow("Original",img)
cv2.imshow("Edge",edge)
cv2.imshow("Hough Lines",img2)
cv2.waitKey()
cv2.destroyAllWindows()

ให้สังเกตลูปในการพลอตเส้นตรง

ปกติเราสามารถกำหนดจุดสองจุดในการพลอตเส้นตรงใดๆ ได้

เช่นจากรูปข้างต้น เราอาจกำหนดจุดในการพลอตคือ
x1 = 0, y1 = r/sin(T)
x2 = r/cos(T), y2 =0
เพื่อเป็นการพลอตเส้นตรงจากขอบรูปไปยังอีกขอบหนึ่ง
แต่ปัญหาที่อาจจะเกิดขึ้นก็คือ ถ้าเป็นเส้นตรงในแนวนอน (T=0) ค่า y1 จะคำนวณไม่ได้

ดังนั้นในโค้ดของโปรแกรม จึงใช้อีกรูปแบบหนึ่ง ดังรูป

นั่นคือ
x1 = x0 - 1000 sin(T)
y1 = y0 + 1000 cos(T)

x2 = x0 + 1000 sin(T)
y2 = y0 - 1000 cos(T)

โดยที่ค่า 1000 เป็นระยะโดยประมาณครับ สามารถปรับเปลี่ยนได้

ข้อสังเกต

1. ความแม่นยำขึ้นอยู่กับวิธีการหาขอบ (edge detection)
2. ขอบเส้นตรงที่หาเจอ อาจจะไม่ใช่ขอบที่ถูกต้อง เพราะวิธีการนี้ตรวจสอบแค่ว่ามีพิกเซลที่วางตัวอยู่ในแนวเส้นตรงเดียวกันมากน้อยแค่ไหน ดังนั้น ในแนวใดๆ แม้ว่าจะไม่ใช่ขอบเส้นตรงจริงๆ หากมีจำนวนพิกเซลที่เป็นขอบอยู่จำนวนมาก ก็จะถูกกำหนดให้เป็นขอบเส้นตรง ตัวอย่างเช่น ถ้าเป็นต้นไม้พุ่มที่มีใบไม้จำนวนมาก ขอบของใบไม้หลายๆใบที่อยู่ในแนวเดียวกัน อาจจะทำให้ถูกคิดเป็นขอบเส้นตรงได้ ทั้งๆที่ไม่ใช่ เช่น เส้นสีเขียวในรูปด้านล่าง
3. การแก้ปัญหาในข้อ 2 อาจทำได้ เช่น กำหนดระยะห่างสูงสุดระหว่างเส้นสองเส้นในแนวเดียวกัน ถ้าระยะห่างนี้น้อยกว่าที่กำหนดก็ให้ถือว่าเส้นทั้งสองเป็นเส้นตรงเส้นเดียวกัน