namlunoy

Posted on by mtoplistChuyên mục:Top List

II – Thuật toán

Tên phương pháp mà chúng ta đang nghiên cứu tên là Gradient Based Method!
Vậy Gradient ở đây là cái gì?

Gradient

Gradient là một vector có các thành phần biểu thị tốc độ thay đổi giá trị của điểm ảnh theo 2 hướng x và y, hay có thể nói là nó đại diện cho sự thay đổi về hướng và độ lớn của một vùng ảnh.
Các thành phần của gradient được tính như sau: (Tính như công thức tính đạo hàm thông thường thôi!)

namlunoy_edge_detection_gradient_02

Như vậy ta có ta có vector gradient là G(f’x,f’y).
[Đến đây ta đã hiểu Gradient là cái gì và cách tính nó ra sao! Ở đây ta tạm gác lại câu hỏi f(x,y) nó là gì và tính như thế nào! Ta nên xem kỹ lại công thức 1 lần nữa cho thấm!]

Với dx, dy lần lượt là khoảng cách giữa 2 điểm lân cận theo chiều x và chiều y.
(Ta có thể xem dx, dy là số lượng điểm ảnh giữa 2 điểm.)

Thực tế ta chọn dx = dy = 1 (ta tính lân cận tức là điểm ngay cạnh nó, nên có thể coi khoảng cách của chúng là 1) tại điểm có tọa độ là (i,j), thay vào công thức trên ta được:

namlunoy_edge_detection_gradient_03

[Sau khi thay vào thì công thức nó chỉ còn đơn giản thế này thôi! Thay thử vào mà xem đúng không?!]

Do tính chất phức tạp trong tính toán khi áp dụng phương pháp Gradient trong xử lý ảnh, người ta sử dụng kỹ thuật Gradient dùng cặp mặt nạ Hx, Hy trực giao (theo 2 hướng vuông góc).

Nếu định nghĩa g1 (f’x), g2 (f’y) là Gradient (vector gradient thành G(g1,g2)) theo hai hướng x, y tướng ứng thì biên độ (tức độ lớn) g(m,n) và hướng của biên tại điểm (m,n) được tính như sau:

namlunoy_edge_detection_gradient_04namlunoy_edge_detection_gradient_08

Để giảm độ phức tạp tính toán, A0 được tính gần đúng như sau:

namlunoy_edge_detection_gradient_05

Việc tính xấp xỉ đạo hàm bậc nhất (f’x và f’y ở đây là g1 và g2) theo các hướng x và y được thực hiện thông qua 2 mặt nạ nhân chập (toán tử đạo hàm), tương ứng sẽ cho ta các kỹ thuật phát hiện biên khác nhau tương ứng với mặt nạ mà nó sử dụng (Roberts, Sobel, Prewitt,..).

[Như vậy công việc tiếp theo của chúng ta là phải tính g1, g2 thông qua 2 cái mặt nạ H1 và H2 mà chúng ta chọn]

Chọn mặt nạ/toán tử – Edge Operators

Trong phương pháp này chúng ta có nhiều loại mặt nạ (toán tử) để chọn! Sau đây là một số loại mặt nạ tiêu biểu!
Robert Operator (Robert Cross)
namlunoy_edge_detection_gradient_09
http://homepages.inf.ed.ac.uk/rbf/HIPR2/roberts.htm

Sobel Operator
namlunoy_edge_detection_gradient_10
http://en.wikipedia.org/wiki/Sobel_operator

Prewitt Operator
namlunoy_edge_detection_gradient_11
http://en.wikipedia.org/wiki/Prewitt_operator

Thuật toán

Đầu vào:
– Ma trận ảnh.
– Ma trận toán tử/mặt nạ.
– Ngưỡng
Đầu ra:
– Ma trận ảnh gồm các đường biên.

Giải thuật

FOR(các điểm của ảnh : I(i,j))
{
     if(nếu là điểm nằm trên đường viền)
           I(i,j) = 0;
     else{
          - Tính Gx (g1) : Nhân chập với Hx
          - Tính Gy (g2) : Nhân chập với Hy
          - Tính A = |Gx| + |Gy|
          - I(i,j) = A >= ngưỡng ? 0 : 1;
     }
}



Cách tính với mặt nạ


Chúng ta đã qua 2 phần khó khăn nhất! Giờ chỉ còn công việc lập trình thôi! Tiếp…


(Một số kỹ thuật khác như kỹ thuật “La Bàn” thì tính theo cả 8 hướng. Ở đây ta làm với phương pháp 2 hướng trước.)

mtoplist