5.26. Tìm kiếm đường thẳng và đoạn thẳng

Một số đặc trưng cảnh không phải là các vùng màu sắc liên kết mà là các cạnh thẳng có hướng: một đường kẻ sơn trên sàn, đường nối giữa hai bề mặt, cạnh bên của một hình chữ nhật được in, mép của một cửa ra vào. Yêu cầu bộ phát hiện vùng màu tìm chúng là câu hỏi sai -- cạnh rộng một điểm ảnh, thuật toán vùng màu muốn có vùng-với-màu-sắc, và câu trả lời trả về rỗng hoặc nhiễu.

Bộ phát hiện đúng cho các cạnh có hướng là biến đổi đường thẳng Hough. Mô-đun image cung cấp nó theo hai dạng: find_lines() trả về các đường thẳng vô hạn (mỗi đường thẳng kéo dài qua toàn bộ ảnh); find_line_segments() trả về các đoạn hữu hạn (mỗi đường thẳng có điểm cuối bên trong khung hình). Ứng dụng cần loại nào phụ thuộc vào việc các cạnh cần quan tâm có liên tục trên toàn khung hình hay chỉ trải dài một phần.

5.26.1. Biến đổi Hough hoạt động như thế nào

Cả hai bộ phát hiện đều chia sẻ cùng một ý tưởng cốt lõi, vì vậy việc hiểu nó một lần sẽ rất có ích. Mô-đun image trước tiên chạy bộ lọc cạnh kiểu Sobel trên đầu vào để chấm điểm mỗi điểm ảnh theo mức độ có thể nằm trên một cạnh có hướng. Mỗi điểm ảnh cạnh như vậy sau đó bỏ phiếu cho tất cả các đường thẳng mà nó có thể nằm trên đó. Các đường thẳng thu thập nhiều phiếu bầu nhất sẽ thắng.

Một đường thẳng được tham số hóa trong không gian Hough bằng hai số: theta, góc của đường thẳng (0 -- 179 độ), và rho, khoảng cách vuông góc từ gốc ảnh đến đường thẳng (có dấu, tính bằng điểm ảnh). Mỗi đường thẳng trong ảnh là một điểm trong không gian (theta, rho). Mỗi điểm ảnh cạnh trong đầu vào đóng góp một phiếu bầu cho mỗi tổ hợp (theta, rho) phù hợp với vị trí của nó -- về mặt khái niệm, một đường cong qua không gian Hough. Nơi nhiều đường cong như vậy giao nhau, nhiều điểm ảnh cạnh đồng ý về cùng một đường thẳng, và giao điểm đó là một phát hiện.

Bộ phát hiện trả về các cực đại cục bộ trong không gian Hough có tổng phiếu bầu vượt quá một ngưỡng. Mỗi Line được trả về mang cả hai biểu diễn: x1, y1, x2, y2 cho dạng điểm cuối (được cắt về giới hạn ảnh cho trường hợp vô hạn), theta, rho cho dạng Hough, và length và magnitude cho kích thước và số phiếu bầu tương ứng.

5.26.2. Đường thẳng vô hạn

find_lines() chạy biến đổi Hough và trả về các đường thẳng mạnh nhất, mỗi đường được kéo dài qua toàn bộ ảnh:

lines = img.find_lines(threshold=1500, theta_margin=25, rho_margin=25)

for l in lines:
    img.draw_line(l, color=(255, 0, 0))

threshold là tổng phiếu bầu tối thiểu để một đường thẳng được chấp nhận. Tổng phiếu bầu cộng dồn các độ lớn cạnh Sobel của mỗi điểm ảnh đóng góp, vì vậy các giá trị threshold lớn hơn đòi hỏi các cạnh dài hơn hoặc mạnh hơn mới qua -- điều này làm cho giá trị đúng phụ thuộc vào độ phân giải ảnh (một đường dài hơn ở độ phân giải cao hơn tích lũy nhiều phiếu hơn) cũng như cảnh, vì vậy nó phải được tinh chỉnh cho từng ứng dụng cụ thể. Các điểm khởi đầu thô để tinh chỉnh: 1000 cho một đường thẳng vừa phải trong ảnh rõ, 500 hoặc thấp hơn cho độ tương phản yếu hoặc đường ngắn, 2000 hoặc hơn cho các cảnh bận rộn nơi các đường dương tính giả hình thành qua các cụm nhiễu cạnh.

theta_margin và rho_margin kiểm soát việc gộp các cực đại gần nhau. Một cạnh vật lý duy nhất tạo ra một cụm nhỏ các ô có phiếu bầu cao xung quanh (theta, rho) thật của nó, và bộ phát hiện gộp mỗi cụm thành đỉnh của nó trước khi trả về. theta_margin=25 (độ) gộp các đỉnh trong vòng 25 độ hướng; rho_margin=25 (điểm ảnh) gộp các đỉnh trong vòng 25 điểm ảnh khoảng cách. Các giá trị mặc định là hợp lý; tăng chúng trả về ít đường thẳng hơn nhưng rõ ràng hơn và giảm chúng trả về nhiều đường thẳng hơn, đôi khi trùng lặp.

x_stride và y_stride bước qua các điểm ảnh cạnh trong quá trình bỏ phiếu, giống như cách chúng bước qua các điểm ảnh trong find_blobs(). Giá trị mặc định 2 và 1 hoạt động cho trường hợp phổ biến; tăng chúng tăng tốc độ tìm kiếm với chi phí giảm độ phân giải. roi giới hạn tìm kiếm trong một vùng của khung hình, vừa thu hẹp các đường thẳng được trả về vừa giảm khối lượng công việc.

Mỗi đường thẳng được trả về có thể vẽ trực tiếp: đối tượng Line truyền thẳng vào draw_line(), đọc các trường điểm cuối (x1, y1, x2, y2) từ đầu của nó. l.theta là góc tính bằng độ, phân loại đường thẳng là ngang, dọc, hoặc chéo trong một phép so sánh. l.magnitude là tổng phiếu bầu, sắp xếp các đường thẳng được trả về từ mạnh nhất đến yếu nhất.

5.26.3. Đoạn thẳng

find_lines() là bộ phát hiện đúng cho các cạnh trải dài toàn bộ khung hình, nhưng nhiều cạnh thực tế -- cạnh trái của mã vạch được in, cạnh trên của nhãn, mặt nhìn thấy được của thước -- chỉ chạy qua một phần của ảnh. find_line_segments() trả về các đoạn hữu hạn có điểm cuối bên trong khung hình:

segments = img.find_line_segments(merge_distance=5, max_theta_difference=10)

for s in segments:
    img.draw_line(s, color=(0, 255, 0))

Bộ phát hiện đoạn theo dõi trực tiếp dọc theo các điểm ảnh cạnh có hướng, thay vì bỏ phiếu trong không gian Hough, và kết quả là một tập hợp các đoạn thẳng ngắn. merge_distance đặt khoảng cách tối đa tính bằng điểm ảnh mà hai đoạn thẳng ngắn cùng đường thẳng có thể kéo dài và vẫn gộp thành một đoạn được trả về; max_theta_difference đặt số độ hướng mà bộ gộp cho phép giữa các đoạn liền kề. Một lần gộp rộng rãi (merge_distance=10, max_theta_difference=15) trả về một số ít đoạn dài với chi phí đôi khi kết nối các cạnh thực sự tách biệt; một lần gộp chặt chẽ (merge_distance=0, max_theta_difference=5) trả về nhiều đoạn ngắn và để ứng dụng sắp xếp chúng bằng Python.

Các đối tượng kết quả là cùng kiểu Line mà find_lines() trả về, với các thuộc tính giống nhau, vì vậy một quy trình xử lý có thể xử lý cả hai loại phát hiện thông qua cùng một đường dẫn mã hạ nguồn. Sự khác biệt thực tế duy nhất là các điểm cuối của đoạn là các đầu thực tế của đường thẳng trong ảnh, trong khi các điểm cuối của đường thẳng vô hạn là nơi đường thẳng cắt đường viền ảnh.

5.26.4. Khi nào sử dụng từng loại

Sự lựa chọn giữa hai phương pháp phụ thuộc vào một câu hỏi duy nhất: ứng dụng có quan tâm đến nơi đường thẳng dừng lại không?

find_lines() là công cụ đúng khi câu trả lời là không. Một robot đi theo đường thẳng cần biết đường thẳng đang đi theo hướng nào và nơi nó cắt đáy khung hình; bản thân đường thẳng chạy đến đường chân trời và hơn thế nữa. Một bộ phát hiện đường chân trời muốn cạnh có hướng mạnh nhất trong ảnh; nó không cần biết đường chân trời kết thúc ở đâu.

find_line_segments() là công cụ đúng khi câu trả lời là có. Nhận dạng bốn cạnh của một hình chữ nhật được in cần bốn đoạn với điểm cuối đã biết. Theo dõi ngón tay trỏ vào màn hình nghĩa là theo dõi một đoạn ngắn có điểm cuối là đầu và gốc ngón tay. Đo chiều dài của một vết xước nhìn thấy được cần phạm vi thực tế của đoạn tính bằng điểm ảnh.

Cả hai bộ phát hiện đều có một hạn chế chung: chúng cần độ tương phản. Bộ lọc cạnh Sobel mà chúng dựa trên phản hồi với độ dốc độ sáng; một cạnh có màu trên nền sáng ngang bằng (một đường đỏ trên tường xanh lá có độ sáng tương đương) không tạo ra độ dốc và không có phát hiện. Khi trường hợp đó xuất hiện trong thực tế, cách khắc phục là trích xuất một kênh LAB đơn làm ảnh thang xám với độ tương phản đúng trước khi tìm kiếm -- to_grayscale() với kênh b được chọn cô lập màu đỏ trên nền xanh lá nơi kênh độ sáng một mình là phẳng -- và đưa ảnh kênh đó vào bộ phát hiện đường thẳng.