Thuật toán phát hiện cạnh Canny trong OpenCV

Có thể bạn chưa biết, khi nói đến nhận diện hình ảnh, mắt người chỉ mất vài phần nghìn giây để xử lý và xác định nội dung của một bức ảnh. Khả năng đáng kinh ngạc này có thể được thực hiện dù dữ liệu là tranh vẽ hay ảnh chụp. Đây cũng là mục đích hướng tới của thị giác máy tính. Một trong những ý tưởng ngày nay là xây dựng một thuật toán có thể phác thảo các cạnh của bất kỳ đối tượng nào có trên một hình ảnh, sử dụng thuật toán phát hiện cạnh Canny (Canny edge detection).

Phát hiện cạnh Canny là gì?

Phát hiện cạnh Canny (Canny edge detector) là một thuật toán bao gồm nhiều giai đoạn để phát hiện một loạt các cạnh trong hình ảnh. Nó được phát triển bởi John F. Canny vào năm 1986. Canny cũng đưa ra một lý thuyết tính toán về phát hiện cạnh giải thích tại sao kỹ thuật này hoạt động.

Thuật toán phát hiện cạnh Canny bao gồm 5 bước:

Giảm nhiễu;
Tính toán Gradient độ xám của ảnh;
Áp dụng Non-maximum suppression;
Ngưỡng kép (Double threshold);
Theo dõi cạnh bằng độ trễ (Edge Tracking by Hysteresis).

Sau khi áp dụng các bước này, ta có thể nhận được kết quả sau

Hình ảnh gốc ở bên trái – Hình ảnh đã xử lý ở bên phải

Một điều quan trọng cuối cùng cần đề cập, đó là thuật toán dựa trên ảnh xám. Do đó, điều kiện tiên quyết là phải chuyển hình ảnh sang thang độ xám trước khi thực hiện các bước nêu trên.

Giảm nhiễu

Việc loại bỏ các yếu tố nhiễu là đặc biệt quan trọng đối với kết quả phát hiện cạnh.

Một cách để loại bỏ nhiễu là áp dụng Gaussian Filter giúp làm mịn ảnh. Để làm như vậy, kỹ thuật tích chập hình ảnh được áp dụng với Gaussian Kernel (kích thước 3×3, 5×5, 7×7, v.v.). Kích thước kernel phụ thuộc vào hiệu ứng làm mờ mong muốn. Về cơ bản, kernel càng nhỏ, hiệu ứng mờ càng ít. Ví dụ dưới đây sử dụng 5 x 5 Gaussian kernel.

Phương trình cho một kernel bộ lọc Gaussian có kích thước (2k + 1) × (2k + 1):

Code Python để tạo Gaussian kernel 5×5: Tham khảo tại đây.

Sau khi áp dụng hiệu ứng mờ Gaussian, ta nhận được kết quả sau:

Hình ảnh gốc (trái) – Hình ảnh bị làm mờ với bộ lọc Gaussian (sigma = 1.4 và kích thước kernel là 5×5)

Tính toán Gradient độ xám

Bước tính toán Gradient độ xám phát hiện các cạnh thông qua cường độ và hướng của gradient độ xám.

Các cạnh tương ứng với sự thay đổi cường độ sáng của pixel. Để phát hiện nó, cách dễ nhất là áp dụng các Filter làm nổi bật sự thay đổi cường độ này theo cả hai hướng: ngang (x) và dọc (y)

Sau Khi hình ảnh được làm mịn, các đạo hàm Ix và Iy w.r.t. x và y được tính. Việc này có thể được thực hiện bằng cách nhân chập I với các Sobel kernel Kx và Ky, tương ứng:

Sobel Filter cho cả hai chiều ngang và dọc

Sau đó, độ lớn G và góc θ của gradient được tính như sau:

Cường độ và hướng của gradient

Tham khảo cách Sobel Filter được áp dụng cho hình ảnh và cách lấy cả ma trận cường độ và hướng của gradient: tại đây

Hình ảnh bị mờ (trái) – Cường độ gradient (phải)

Kết quả gần như là mong đợi, nhưng chúng ta có thể thấy rằng một số cạnh dày và một số cạnh mỏng. Bước non-maximum suppression sẽ giúp ta giảm thiểu các cạnh dày.

Hơn nữa, mức cường độ gradient nằm trong khoảng từ 0 đến 255 nên độ sáng của các cạnh không đồng nhất. Các cạnh trên kết quả cuối cùng phải có cùng cường độ (i-e. Pixel trắng = 255).

Non-maximum suppression

Tốt nhất, hình ảnh cuối cùng nên có các cạnh mỏng. Vì vậy, ta phải thực hiện thuật toán Non-maximum suppression để làm mỏng chúng.

Nguyên tắc rất đơn giản: thuật toán đi qua tất cả các điểm trên ma trận cường độ gradient và tìm các pixel có giá trị lớn nhất theo các hướng cạnh.

Hãy lấy một ví dụ dễ hiểu:

Hộp màu đỏ ở góc trên bên trái đại diện cho một pixel cường độ của ma trận Cường độ Gradient đang được xử lý. Hướng gradient tương ứng được biểu diễn bằng mũi tên màu cam với góc -pi radian (+/- 180 độ).

Tập trung vào khu vực pixel trong hộp màu đỏ góc trên bên trái

Hướng gradient là đường chấm màu cam (nằm ngang từ trái sang phải). Mục đích của thuật toán là để kiểm tra xem các pixel trên cùng một hướng có cường độ cao hơn hay thấp hơn các pixel đang được xử lý. Trong ví dụ trên, pixel (i, j) đang được xử lý và các pixel trên cùng một hướng được đánh dấu bằng màu xanh lam (i, j-1) và (i, j + 1). Nếu một trong hai pixel đó có cường độ cao hơn pixel đang được xử lý, thì chỉ có một pixel có cường độ cao hơn được giữ lại. Pixel (i, j-1) có vẻ sáng hơn, vì nó có màu trắng (giá trị 255). Do đó, giá trị cường độ của pixel hiện tại (i, j) được đặt thành 0. Nếu không có pixel nào ở hướng cạnh có giá trị cường độ cao hơn thì giá trị của pixel hiện tại được giữ nguyên.

Bây giờ chúng ta hãy tập trung vào một ví dụ khác:

Trong trường hợp này, hướng là đường chéo chấm màu cam. Do đó, pixel cường độ cao nhất theo hướng này là pixel (i-1, j + 1).

Tóm gọn lại, mỗi pixel được đánh giá bằng 2 tiêu chí chính (hướng cạnh tính bằng radian và cường độ pixel (từ 0–255). Dựa trên các đầu vào này, các bước non-maximum suppression là:

Tạo một ma trận được khởi tạo bằng 0 có cùng kích thước của ma trận cường độ gradient ban đầu;
Xác định hướng của gradient dựa trên giá trị góc từ ma trận góc;
Kiểm tra xem pixel ở cùng một hướng có cường độ cao hơn pixel hiện đang được xử lý hay không;
Trả lại hình ảnh được xử lý bằng thuật toán non-maximum suppression.

Tham khảo code tại đây.

Kết quả là cùng một hình ảnh với các cạnh mỏng hơn. Tuy nhiên, ta vẫn có thể nhận thấy sự không đồng đều trong cường độ của các cạnh: một số pixel có vẻ sáng hơn những pixel khác và điều này sẽ được khắc phục bằng hai bước cuối cùng

Kết quả của thuật toán non-maximum suppression

Ngưỡng kép (Double threshold)

Bước này nhằm mục đích xác định 3 loại pixel: mạnh, yếu và ngoại lai:

Pixel mạnh là pixel có cường độ cao và trực tiếp góp phần vào sự hình thành cạnh.
Pixel yếu là pixel có giá trị cường độ không đủ để được coi là mạnh nhưng chưa đủ nhỏ để được coi là ngoại lai.
Các pixel khác được coi là ngoại lai.

Bây giờ bạn có thể thấy vai trò của ngưỡng kép:

Ngưỡng cao được sử dụng để xác định các pixel mạnh (cường độ cao hơn ngưỡng cao)
Ngưỡng thấp được sử dụng để xác định các pixel ngoại lai (cường độ thấp hơn ngưỡng thấp)
Tất cả các điểm ảnh có cường độ giữa cả hai ngưỡng đều được gắn là yếu. Cơ chế Độ trễ (bước tiếp theo) sẽ giúp ta xác định xem các Pixel yếu sẽ được giữ lại như các pixel mạnh hay bị loại bỏ như pixel ngoại lai.

Tham khảo code bước này tại đây.

Kết quả của bước này là một hình ảnh chỉ có 2 giá trị cường độ pixel (mạnh và yếu):

Hình ảnh trước non-maximum suppression (trái) – Kết quả (phải): pixel yếu có màu xám và pixel mạnh có màu trắng.

Theo dõi cạnh theo độ trễ (Edge Tracking by Hysteresis)

Dựa trên kết quả sau khi áp dụng ngưỡng, Hysteresis Tracking chuyển đổi các pixel yếu thành mạnh, khi và chỉ khi ít nhất một trong các pixel xung quanh pixel đang xét là pixel mạnh, các pixel yếu còn lại bị loại bỏ, như được mô tả bên dưới: