Phát hiện đường thẳng với Hough Transform

Hough Transform là thuật toán phát hiện đường thẳng khá hiệu quả trong xử lý ảnh. Ở bài viết này, chúng ta sẽ cùng tìm hiểu về cách thức hoạt động cũng như cách sử dụng Hough Transform để phát hiện đường thẳng trong ảnh bằng thư viện OpenCV.

I. Lý thuyết

Ý tưởng chung của việc phát hiện đường thẳng trong thuật toán này là tạo mapping từ không gian ảnh (A) sang một không gian mới (B) mà mỗi đường thẳng trong không gian (A) sẽ ứng với một điểm trong không gian (B).

1. Phương trình đường thẳng trong không gian ảnh (A)

Như đã học ở cấp 2, phương trình đường thẳng cơ bản sẽ được biểu diễn theo 2 tham số $a$ và $b$ như sau:

y = ax + b

Tuy nhiên, với cách biểu diễn này, giá trị của góc nghiêng $a$ trải dài từ $– \infty$ đến $+ \infty$ . Có thể lấy ví dụ, để có được phương trình đường Oy ( $x=0$ ) thì $a$ phải tiến tới $\infty$ . Thuật toán Hough Transform yêu cầu các giá trị a, b nằm trong một khoảng xác định (hay bị chặn trên dưới), ta phải sử dụng hệ tọa độ cực để biểu diễn phương trình đường thẳng. Cách biểu diễn này cũng nằm trong chương trình toán trung học: $\rho = x\cos(\theta) + y\sin (\theta)$ .

Xét thấy trong phương trình tọa độ cực, giá trị của góc $\theta$ có thể bị chặn lại trong khoảng [0, π). Trên thực tế, không gian ảnh là không gian hữu hạn (bị chặn lại bởi các cạnh của ảnh), do vậy giá trị $\rho$ cũng bị chặn.

2. Mapping giữa không gian ảnh (A) và không gian Hough (B)

Từ một đường thẳng trong không gian ảnh (A) với 2 tham số $\rho$ và $\theta$ , chúng ta sẽ map sang không gian Hough (B) thành một điểm.

Mapping một đường thẳng từ không gian ảnh sang không gian Hough

Từ một điểm trong không gian ảnh, chúng ta lại có được một hình sin trong không gian Hough:

Mapping một điểm từ không gian ảnh sang không gian Hough

Các điểm nằm trên cùng một đường thẳng lại có biểu diễn là các hình sin giao nhau tại một điểm trong không gian Hough. Đây là nơi xuất phát ý tưởng của thuật toán Hough Transform. Chúng ta sẽ dựa vào các điểm giao nhau này để suy ngược lại phương trình đường thẳng trong không gian ảnh.

Mapping nhiều điểm thẳng hàng từ không gian ảnh sang không gian Hough

Mỗi đường thẳng khác nhau sẽ tạo thành một điểm sáng (nơi giao nhau của nhiều hình sin) trên không gian Hough. Dưới đây là sự biểu diễn 2 đường thẳng trong không gian Hough.

Biểu diễn 2 đường thẳng trong không gian Hough

II. Cài đặt thuật toán

Toàn bộ mã nguồn được chia sẻ tại đây.

Tiền xử lý

Hough Transform yêu cầu đầu vào là một ảnh nhị phân. Trên thực tế ảnh sẽ được đưa về dạng ảnh xám, áp dụng các thuật toán lọc biên để xác định các đường biên trong ảnh. Ở đây chúng ta sẽ sử dụng thuật toán Canny để lọc biên.

Bình chọn đường thẳng

Ta chia không gian Hough ra thành một lưới ô vuông nhỏ. Ta sẽ có một lưới ô vuông với các hàng là trục $\rho$ và các cột là trục $\theta$ như hình dưới. Độ chính xác của thuật toán phụ thuộc vào số lượng các ô vuông bạn chọn cho mỗi cạnh. Giả sử bạn muốn độ chính xác của $\theta$ là 1 độ (theta resolution = 1), bạn cần 180 cột. Giá trị $\rho$ bị chặn bởi cạnh chéo của ảnh đầu vào. Do vậy khi lấy độ chính xác của $\rho$ là 1 (pixel) (rho resolution = 1) thì số hàng bằng độ dài đường chéo ảnh theo đơn vị pixel.

Thực hiện voting để tìm đường thẳng

Các ô trong lưới ô vuông, được đặt giá trị ban đầu là 0. Xét các điểm trên ảnh đầu vào (chính là ảnh nhị phân thu được sau quá trình lọc biên sử dụng Canny), với mỗi điểm sáng, ta xét $\theta$ trong khoảng [0, 180). Vì đã biết tọa độ điểm (x, y), ta dễ dàng tính được giá trị $\rho$ . Với mỗi cặp ( $\theta$ , $\rho$ ), ta thực hiện vote (tăng giá trị tương ứng trên lưới ô vuông lên 1 đơn vị). Cuối cùng ta lấy một ngưỡng (threshold) để xác định trên lưới ô vuông, cặp giá trị ( $\theta$ , $\rho$ ) nào ứng với một đường thẳng trên thực tế. Quá trình voting được mô tả qua hình ảnh bên dưới (nguồn: http://homepages.inf.ed.ac.uk/amos/hough.html):

Cài đặt thuật toán với Python sử dụng thư viện OpenCV:

cdst = src.copy()
cdstP = src.copy()

lines = cv.HoughLines(edges, 1, np.pi / 180, 150, None, 0, 0)

if lines is not None:
    for i in range(0, len(lines)):
        rho = lines[i][0][0]
        theta = lines[i][0][1]
        a = math.cos(theta)
        b = math.sin(theta)
        x0 = a * rho
        y0 = b * rho
        pt1 = (int(x0 + 1000*(-b)), int(y0 + 1000*(a)))
        pt2 = (int(x0 - 1000*(-b)), int(y0 - 1000*(a)))
        cv.line(cdst, pt1, pt2, (0,0,255), 3, cv.LINE_AA)


linesP = cv.HoughLinesP(edges, 1, np.pi / 180, 100, None, 90, 60)

if linesP is not None:
    for i in range(0, len(linesP)):
        l = linesP[i][0]
        cv.line(cdstP, (l[0], l[1]), (l[2], l[3]), (0,0,255), 3, cv.LINE_AA)

*Giải thích:

Áp dụng bộ lọc Hough Line Transform để lọc đường thẳng:

#  Standard Hough Line Transform
lines = cv.HoughLines(edges), 1, np.pi / 180, 150, None, 0, 0)

Các tham số được sử dụng lần lượt là:

edges: Đầu ra của bộ lọc biên.
lines: Vector lưu kết quả dưới dạng ( $\rho$ , $\theta$ ).
rho: Độ phân giải của $\rho$ theo đơn vị pixel. Ở đây có giá trị 1 (pixel).
theta: Độ phân giải của $\theta$ tính theo radian. Giá trị sử dụng ở đây là 1 độ (np.pi/180).
threshold: Số lượng voting tối thiểu để xác định một đường thẳng.
srn, stn: 2 tham số cuối. Khi chúng ta sử dụng thuật toán Hough transform nguyên bản, 2 tham số này bằng 0.
Ngoài ra thư viện OpenCV còn hỗ trợ thêm Probabilistic Hough Line Transform, là một bản chỉnh sửa, thêm vào các chức năng lọc kết quả:

# Probabilistic Line Transform
linesP = cv.HoughLinesP(edges), 1, np.pi / 180, 50, None, 50, 10)

Hàm này ngoài các tham số giống cv.HoughLines như edges, rho, theta, threshold còn có thêm:

minLinLength: số điểm tối thiểu tạo nên một đường thẳng. Các đường tìm được có số điểm nhỏ hơn số này sẽ được loại bỏ khỏi kết qủa.
maxLineGap: Khoảng cách lớn nhất giữa 2 điểm để có thể coi chúng vẫn cùng một đường thẳng. Trong ảnh gốc rất có thể nhiều đường thẳng bị mờ, nhiễu, khi cho qua bộ lọc biên Canny, các đường thẳng sẽ trở thành các đường đứt quãng (hay các điểm riêng biệt). Tham số này quyết định việc có coi các đoạn đứt quãng đó thuộc cùng một đường hay không.

Kết quả thu được khi chạy Standard Hough Line Transform và Probabilistic Line Transform được mô tả qua 2 hình ảnh sau (xem ảnh gốc):

Các bạn có thể xem mã nguồn đầy đủ và thử với các hình ảnh khác tại đây.

Bài tập thực hành

Các bạn có thể thực hành bằng cách sử dụng Hough Line Transform để lọc vạch kẻ đường trong các hình bên dưới.

Phát hiện đường thẳng với Hough Transform - OpenCV