Phát hiện đường thẳng bằng Hough Transform (Hough Line)

  May 4, 2019      2m      0   

 

OpenCV - tut 12: Tự hiện thực Hough Transform

Môi trường "hành sự"

• Linux (bài viết sử dụng Ubuntu 16.04)
• OpenCV (bài viết sử dụng OpenCV 3.4.1)
• Python (bài viết sử dụng Python 3.5.5)
• Ảnh mẫu để xử lý: geometry.jpg

Bạn có thể download ảnh mẫu về:

geometry.jpg (Nguồn: Lụm trên mạng)

Giải thuật phát hiện đường thẳng - Hough Transform

Ý tưởng chính của giải thuật phát hiện đường thẳng Hough Transform đó là:

• Dựa trên kết quả phát hiện cạnh để tiến hành phát hiện đường thẳng. Giải thuật phát hiện cạnh phổ biến là Canny Edge Detection.
• Trên mỗi pixel cạnh (pixel thuộc cạnh được phát hiện trong ảnh), ta lần lượt thử các phương trình đường thẳng đi qua pixel đó. Số phương trình đường thẳng ta thử càng nhiều thì sẽ cho ra kết quả phát hiện đường thẳng càng tốt (ít bỏ lỡ đường thẳng có trong ảnh hơn). Pixel cạnh đó sẽ "vote" thêm 1 giá trị vào ma trận thống kê.
• Sau khi duyệt hết tất cả các pixel cạnh, ta sẽ lọc theo một giá trị ngưỡng (xác định trước) trên ma trận thống kê để giữ lại (để xác định được) các phương trình đường thẳng có trong ảnh.

Sau khi xác định được các đường thẳng, việc còn lại đơn giản ta chỉ việc vẽ các đường thẳng đó lên ảnh.

Tuần tự các bước trong giải thuật Hough Transform phát hiện đường thẳng bạn tham khảo thêm tại link sau đây:

• https://docs.opencv.org/master/d6/d10/tutorial_py_houghlines.html

Hough Transform trong OpenCV

Các hàm cần thiết để dùng giải thuật Hough Transform đều đã được hiện thực trong thư viện OpenCV:

• cv2.Canny: trích cạnh bằng giải thuật Canny
• cv2.HoughLines: phát hiện đường thẳng bằng giải thuật Hough Transform
• cv2.line: vẽ đường thẳng

Các siêu tham số để dùng hiệu quả cho trường hợp của bạn, bạn cần phải đọc tài liệu (documentation) của OpenCV để điều chỉnh cho hợp lý nhé. Các siêu tham số này ảnh hưởng rất nhiều đến kết quả đạt được, điều chỉnh thường dựa vào kinh nghiệm hoặc thử sai.

Đoạn code ngắn sau thì bạn đã dùng xong Hough Transorm rồi nhé, quá là siêu cấp đơn giản luôn ^^:

# read image
img = cv2.imread('geometry.jpg')
# convert to gray scale
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY) # color -> gray
edges = cv2.Canny(gray, 50, 150, apertureSize=3)
lines = cv2.HoughLines(edges, rho=1, theta=np.pi/180, threshold=100)
for line in lines:
    rho, theta = line[0]
    a = np.cos(theta)
    b = np.sin(theta)
    x0 = a*rho
    y0 = b*rho
    x1 = int(x0 + 1000*(-b))
    y1 = int(y0 + 1000*(a))
    x2 = int(x0 - 1000*(-b))
    y2 = int(y0 - 1000*(a))
    cv2.line(img,(x1,y1),(x2,y2),(0,0,255),2)    
cv2.imwrite('geo_hough.jpg',img)

Hiện thực Hough Transorm

Một trong những phần thú vị và thử thách nhất cho người viết blog là đây. Tự hiện thực giải thuật Hough Transorm! Dĩ nhiên, giải thuật mọi người đều đã nắm trong tay. Vậy làm sao để hiện thực Hough Line để phát hiện đường thẳng đây?! Hôm nay mình sẽ viết dài dòng hơn một chút, nói nhiều hơn một chút để mọi người nắm được và có thể áp dụng cho bản thân thay vì chỉ cung cấp code để chạy.

Trước tiên, các bạn đọc kỹ hướng dẫn giải thuật trong tutorial Hough Transform của OpenCV. Mình sẽ dẫn dắt cách hiện thực từng bước một. Đầu tiên, phương trình một đường thẳng có thể được mô tả bằng rho và theta. Góc theta có giá trị từ 0 -> 180, do đó nếu ta muốn thử các đường thẳng mà mỗi đường thẳng lệch nhau chỉ 1 độ (tức đường thẳng 1, theta = 0 độ; đường thẳng 2, theta = 1 độ, đường thẳng 3, theta = 2 độ; …) thì ta sẽ có 180 đường thẳng có thể thử. Góc theta để đặc tả một đường thẳng là chưa đủ, ta cần thêm khoảng cách rho (đọc là rô) để xác định khoảng cách từ đường thẳng đến gốc tọa độ O (từ O ta chiếu vuông góc đến đường thẳng). Giá trị tối đa của rho bằng đường chéo của ảnh (diagonal_length), mà rho lại có thể mang giá trị âm, do đó rho có giá trị trong đoạn [-diagonal_length, diagonal_length]. Dĩ nhiên, để đạt kết quả tốt, ta có thể set độ khít của rho = 1 pixel thì ta sẽ có tổng số rho có thể thử trên ảnh là 2 x int(diagonal_length / rho) + 1 (cộng thêm một là do ta phải tính luôn cả giá trị zero).

Từ các thông tin trên, ta xác định được ma trận thống kê (khởi tạo các phần tử trong ma trận này có giá trị zero) có kích thước là: số trường hợp rho x số trường hợp theta. Tiếp theo, ta cần phải duyệt trên mỗi pixel cạnh xem có thể có bao nhiêu phương trình đường thẳng (xác định bởi cặp số (rho, theta)) đi qua được nó. Ý tưởng cho việc hiện thực đó là với mỗi pixel cạnh (x,y), ta tính giá trị rho tương ứng cho chúng lần lượt cho các giá trị theta (180 giá trị theta). Ví dụ cụ thể cho dễ hiểu, giả sử ta có 4000 pixel được cho là cạnh bởi giải thuật Canny, thì ta sẽ có 4000 cặp giá trị (x,y) –> mô tả bằng ma trận A có kích thước [4000, 2]. Sau đó, với mỗi cặp (x,y) ta lại muốn thử 180 giá trị theta theo phương trình đường thẳng ρ = xcosθ + ysinθ để tính ra 180 giá trị rho. Để làm được điều đó, ta chỉ cần dựng ma trận B có kích thước [2, 180] chứa các cosθ (dòng 1) và sinθ (dòng 2) để sau đó tính theo dot product nhằm thu được một ma trận chứa các giá trị rho là C có kích thước [4000, 180].

Ta chỉ cần duyệt mỗi phần tử trên ma trận C để "vote" vào ma trận thống kê X bằng cách xác định dòng và cột phù hợp để +1 đơn vị. Giá trị rho nằm từ [-num_rho, num_rho] trong khi index các dòng của X bắt đầu từ 0, vì vậy rho_pos đối với X sẽ bằng int(round(vote_matrix[vr, vc]))+num_rho. Sau khi duyệt xong để vote vào X thì ta lọc theo ngưỡng xác định trước để giữ lại các đường thẳng có trong ảnh. Lọc theo ngưỡng trên ma trận X (edge_matrix) ta sẽ được các index của dòng và index của cột. Từ các giá trị index này ta phải convert về rho và theta (radian) để hàm cv2.line có thể vẽ đúng!

Phí trên là dòng suy nghĩ để tiến đến hiện thực thành code như bên dưới, các bạn có thể chạy thử thì hàm tự hiện thực sẽ cho ra kết quả xấp xỉ hàm của OpenCV. Cụ thể OpenCV vẽ ra được 18 line, trong khi hàm của mình vẽ tận 21 line. Điểm khác biệt là do chi tiết hiện thực. OpenCV cũng đã được tối ưu, nó chạy nhanh hơn giải thuật tự hiện thực của mình.

Mục đích cuối cùng của việc tự hiện thực đó là giúp mình hiểu rõ đến từng chi tiết của giải thuật Hough Transform!

hough.py

import math
import cv2
import numpy as np

# reference: https://docs.opencv.org/master/d6/d10/tutorial_py_houghlines.html
def my_hough(img, rho=1, theta=np.pi/180, threshold=100):
    img_height, img_width = img.shape[:2]
    diagonal_length = int(math.sqrt(img_height*img_height + img_width*img_width))
    
    print('[My Hough] Img Height: %d | Img Width: %d | Img Diagonal Length: %d' % (img_height, img_width, diagonal_length))
    
    num_rho = int(diagonal_length / rho)
    num_theta = int(np.pi / theta)
    
    edge_matrix = np.zeros([2*num_rho+1, num_theta]) # dim: num_rho x num_theta
    
    print('[My Hough] Edge Matrix Dim: %d x %d' % (edge_matrix.shape[0], edge_matrix.shape[1]))
    
    idx	= np.squeeze(cv2.findNonZero(img)) # dim: 4468 x 2 (example, number of rows = number of white pixel on image processed by canny edge algorithm!)
    
    range_theta = np.arange(0, np.pi, theta)
    theta_matrix = np.stack((np.cos(np.copy(range_theta)), np.sin(np.copy(range_theta))), axis=-1) # dim: 180 x 2
    
    vote_matrix = np.dot(idx, np.transpose(theta_matrix)) # => (4468 x 2) * (180 x 2)T = (4468 x 2) * (2 x 180) = 4468 x 180
    print('[My Hough] Vote Matrix Dim: %d x %d' % (vote_matrix.shape[0], vote_matrix.shape[1]))
    
    # loop on vote matrix and accumulate values on edge matrix
    for vr in range(vote_matrix.shape[0]):
        for vc in range(vote_matrix.shape[1]):
            rho_pos = int(round(vote_matrix[vr, vc]))+num_rho
            edge_matrix[rho_pos, vc] += 1
    
    print('[My Hough] Sum of Edge Matrix = %d | Max = %d | Min = %d' % (int(np.sum(edge_matrix)), int(np.max(edge_matrix)), int(np.min(edge_matrix))))
    
    line_idx = np.where(edge_matrix > threshold)
    
    rho_values = list(line_idx[0])
    rho_values = [r-num_rho for r in rho_values]
    theta_values = list(line_idx[1])
    theta_values = [t/180.0*np.pi for t in theta_values]
    
    line_idx = list(zip(rho_values, theta_values))
    line_idx = [[li] for li in line_idx]
    return line_idx

def main():
    # read image
    img = cv2.imread('geometry.jpg')
    # convert to gray scale
    gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY) # color -> gray
    edges = cv2.Canny(gray, 50, 150, apertureSize=3) # https://docs.opencv.org/2.4/modules/imgproc/doc/feature_detection.html?highlight=canny#canny
    cv2.imwrite('geo_canny.jpg', edges)

    # USE BUILT-IN OPENCV HOUGH ALGORITHM
    lines = cv2.HoughLines(edges, rho=1, theta=np.pi/180, threshold=100) # https://docs.opencv.org/master/dd/d1a/group__imgproc__feature.html#ga46b4e588934f6c8dfd509cc6e0e4545a
    for line in lines:
        rho, theta = line[0]
        a = np.cos(theta)
        b = np.sin(theta)
        x0 = a*rho
        y0 = b*rho
        x1 = int(x0 + 1000*(-b))
        y1 = int(y0 + 1000*(a))
        x2 = int(x0 - 1000*(-b))
        y2 = int(y0 - 1000*(a))
        cv2.line(img,(x1,y1),(x2,y2),(0,0,255),2)    
    cv2.imwrite('geo_hough.jpg',img)
    print('[OpenCV Hough] Number of lines: %d' % len(lines))
    
    # IMPLEMENT HOUGH ALGORITHM MYSELF!
    lines = my_hough(edges, rho=1, theta=np.pi/180, threshold=100)
    for line in lines:
        rho, theta = line[0]
        a = np.cos(theta)
        b = np.sin(theta)
        x0 = a*rho
        y0 = b*rho
        x1 = int(x0 + 1000*(-b))
        y1 = int(y0 + 1000*(a))
        x2 = int(x0 - 1000*(-b))
        y2 = int(y0 - 1000*(a))
        cv2.line(img,(x1,y1),(x2,y2),(0,0,255),2)    
    cv2.imwrite('geo_myhough.jpg',img)
    print('[My Hough] Number of lines: %d' % len(lines))

if __name__ == "__main__":
    main()
    print('* Follow me @ ' + "\x1b[1;%dm" % (34) + ' https://www.facebook.com/minhng.info/' + "\x1b[0m")
    print('* Join GVGroup for discussion @ ' + "\x1b[1;%dm" % (34) + 'https://www.facebook.com/groups/ip.gvgroup/' + "\x1b[0m")
    print('* Thank you ^^~')    

geo_canny.jpg

geo_hough.jpg

---

Cảm ơn bạn đã theo dõi bài viết. Hãy kết nối với tớ nhé!

• Minh: https://www.facebook.com/minhng.info
• Khám phá xử lý ảnh - GVGroup: https://www.facebook.com/groups/ip.gvgroup

Khám phá xử lý ảnh - GVGroup

Danh sách bài viết series OpenCV:

• Hashtag #OpenCV
• Tut 1: Xử lý ảnh - OpenCV đọc ghi hình ảnh (code Python và C++)
• Tut 1.1: Xử lý ảnh - Cấu trúc dữ liệu ảnh trong OpenCV. Pixel là gì?
• Tut 1.2: Xử lý ảnh - Chuyển đổi ảnh OpenCV sang Pillow và ngược lại
• Tut 2: Xử lý ảnh - OpenCV resize, crop và padding hình ảnh (code Python và C++)
• Tut 3: Xử lý ảnh - OpenCV biến đổi mức sáng hình ảnh (code Python)
• Tut 4: Xử lý ảnh - OpenCV vùng quan tâm (ROI) là gì? (code Python)
• Tut 4.1: Xử lý ảnh - OpenCV: vẽ văn bản, đường thẳng, mũi tên, hình chữ nhật, hình tròn, ellipse, đa giác
• Tut 4.2: Xử lý ảnh - Pha trộn ảnh trong OpenCV (blending)
• Tut 5: Xử lý ảnh - OpenCV ảnh nhị phân
• Tut 6: Xử lý ảnh - OpenCV cân bằng sáng (histogram equalization)
• Tut 7: Xử lý ảnh - OpenCV kỹ thuật cửa sổ trượt (sliding window)
• Tut 8: Xử lý ảnh - Convolution là gì?
• Tut 9: Xử lý ảnh - Làm mờ ảnh (blur)
• Tut 10: Xử lý ảnh - Gradient của ảnh là gì?
• Tut 11: Xử lý ảnh - Phát hiện cạnh Canny (Canny Edge Detection)
• Tut 12: Xử lý ảnh - Phát hiện đường thẳng bằng Hough Transform (Hough Line)
• Tut 13: Xử lý ảnh - Hiện thực phát hiện đoạn thẳng dùng Hough Transform (Hough Line)
• Tut 14: Xử lý ảnh - Giải thuật phân vùng Region Growing trên ảnh màu
• Tut 15: Xử lý ảnh - Giải thuật Background Subtraction trên ảnh màu
• Tut 16: Xử lý ảnh - Frame Subtraction để phát hiện chuyển động trong video
• Tut 17: Xử lý ảnh - HOG - Histograms of Oriented Gradients
• Tut 18: Xử lý ảnh - HOG - Huấn luyện mô hình phân loại người
• Tut 19: Xử lý ảnh - HOG - Phát hiện người
• Tut 20: Xử lý ảnh - Tổng hợp kinh nghiệm xử lý ảnh (End)
• Tut 21: Xử lý ảnh - Hiện thực trích đặc trưng Local Binary Patterns (LBP)
• Tut 22: Xử lý ảnh - Trích đặc trưng Gabor filters

Minh Nguyen

Share this:

      

• #xulyanh
• #opencv
• #imageprocessing