Xử lý ảnh số: Dùng biến đổi hough để xác định cạnh

BÀI TẬP THỰC HÀNH LỚN BÀI THỰC HÀNH 11 DÙNG BIẾN ĐỔI HOUGH ĐỂ XÁC ĐỊNH CẠNH Phần 1: Lý thuyết biến đổi Hough. Biến đổi Hough được sử dụng như trung bình của các cạnh nối, biến đổi Hough gồm sự biến đổi của một đường trong không gian Decard sang không gian Polar. Hình 17.4-6a, một đường thẳng được mô tả tham số: ρ = xcosϴ +ysinϴ với ρ là khoảng cách của đường thẳng đến gốc tọa độ và ϴ là gốc hợp bởi đường khỏang cách đó với trục x. biến đổi Hough của đường này là 1 điểm tại tọa độ (ρ, ϴ) trong miền cực như trong hình 17.4-6b, tập những đường đi qua một điểm trong hình 17.4-6c có biến đổi Hough là tập những điểm (ρ, ϴ) như trong hình 17.4-6d. bây giờ chúng ta xem xét 3 điểm thẳng hàng trong hình 17.4-6e, biến đổi hough của họ các đường cong qua 3 điểm này là một tập 3 đường cong tham số trong không gian ρ - ϴ như hình 17.4-6f. ba đường này cùng qua một điểm (ρ0,ϴ0) tương ứng với những đường không liền nét qua 3 điểm thẳng hàng này. Hình 17.4-6 Biến đổi Hough Phiên bản Duda và Hart. Duda va Hart đã dùng kỉ thuật biến đổi Hough để xác định đường thẳng và đường cong trong những ảnh nhị phân rời rạc. Mỗi dữ liệu điểm không âm trong miền ảnh được chuyển đổi thành một đường cong trong miền ρ - ϴ , mà được lượng tử hóa thành những ô. Nếu một yếu tố của đường cong rơi vào một ô, những ô cụ thể này được gia tăng lên mỗi lần. Sau khi tất cả những điểm dữ liệu đã được biến đổi, những ô ρ - ϴ này đã được khảo sát. Độ lớn của những ô đếm tương ứng với những điểm dữ liệu thẳng hàng mà có thể vẽ thành đường thẳng với những tham số xấp xỉ ρ - ϴ, số nhỏ những điểm cô lập có thể bỏ được. Hình 17.4-7a là mô tả hình học sử dụng cho sự phát triển của một thuật toán phiên bản Duda và Hart của biến đổi Hough. Theo khái niệm được chấp nhận trong bài 13.1, một ảnh gốc được thiết lập tại góc cao bên trái ảnh. Tọa độ Đecac của điểm ảnh (i , j) là : xj=j+12 yk=k+12 Hình 17.4-7 Tính toán hình học của biến đổi Hough Xem xét một đoạn thẳng trong ảnh nhị phân F(j,k), chứa 1 điểm tại (j,k) tạo góc Ф với trục nằm ngang. Khi đó đoạn thẳng được xem xét, nó cắt với đường có chiều dài ρ bắt nguồn từ gốc tạo một góc ϴ với trục hoành. Mảng Hough H(m,n) gồm những ô của các biến đã lượng tử hóa ρm và Фn với: -ρmax2≤ρm≤ρmax -п2≤Фn≤п Với ρmax=xj2+yk212 Để thuận tiện, xem hình 17.4-7 là đối xứng, và tập M và N là những số nguyên lẽ thì ô trung tâm của ma trận Hough là ρm=0 và Фn=0 thuật toán biến đổi Hough (D&H) như sau: 1. Khởi tạo giá trị ban đầu cho ma trận Hough bằng 0 2. Mỗi (j,k) mà cho F(j,k) =1 tính: ρn=xjcos ϴn+yksin ϴn Với ϴn= п-2пN-nN-1 Và 1≤n≤N Ф-п2≤ ϴn≤ Ф+п2 Ф=arctan{ykxj} 3. Xác định chỉ số m của giá trị lượng tử hóa m=M-ρmax-ρnM-12ρmaxN Với .N là giá trị số nguyên gần nhất của chính nó 4. Tăng H(m,n) = H(m,n) + 1 Cần quan trọng khi xem xét sự hạn chế ở 17.4-6, không phải tất cả sự kết hợp trong ρ - ϴ là hợp lý đối với một pixel cho trước có tọa độ (j,k). Sự tính tóan của ma trận Hough phụ thuộc bậc của ước lượng N của 17.4-4 đến 17.4-6 cho mỗi pixel không âm của F(j,k). Kích thước của ma trận Hough không phụ thuộc hòan toàn vào kích thước của ma trận ảnh. Ma trận Hough ít nhất là ¼ ma trận ảnh thì mới cho những kết quả có độ chính xác hợp lý. Hình 17.4-8 mô tả vài ví dụ phiên bản D&H của biến đổi Hough, ở đây M = N = 127 và J = K = 512. Hình 17.4-8 cho phiên bản Duda và Hart cho biến đổi Hough Ba điểm thẳng hàng Biến đổi Hough Đường thẳng Biến đổi Hough Đường không liền nét Biến đổi Hough Phiên bản O’Gorman và Clowes. O’Gorman và Clowes đưa ra sự sửa đổi của biến đổi Hough cho việc liên kết cạnh từ những điểm trong một ảnh. Trong thủ tục của họ, góc ϴ đưa vào trong không gian ρ-ϴ thu được từ gradient trực tiếp của một cạnh. Giá trị ρ tương ứng được tính toán sau từ Eq. 17.4-4 cho một cạnh tọa độ (j,k). Thay vì tăng những ô (ρ,ϴ) lên 1, những ô này được tăng lên bởi độ lớn gradient của cạnh này theo bậc để thấy những cạnh lớn (strong edges) quan trọng hơn những cạnh mãnh (weak edges). Đây là thuật toán cho việc tính toán phiên bản O’Gorman và Clowes của biến đổi Hough. Hình 17.4-7a chỉ rõ những góc của cạnh này dùng tham khảo cho thuật toán. 1. Khởi tạo giá trị ban đầu cho ma trận Hough bằng 0 2. Cho trước một ảnh mức xám F(j,k), lấy đạo hàm bậc nhất ma trận gadient cạnh G(j,k) và một ma trận góc gadient cạnh γ(j,k) dùng một hệ xác định cạnh bất kì mô trình bày trong 15.2.1 3. Mỗi (j,k) mà G(j,k) > T, T là ngưỡng của hệ xác định cạnh, tính: ρj,k=xjcosθj,k+ yksin⁡{θj,k} Với: θ=ψ+π2 với ψ<Фψ+π2 với ψ≥Ф Và Ф=arctanykxj Và ψ=γ+3π2 với -π≤γ<-π2γ+π2 với -π2≤γ< π2γ-π2 với π2 ≤γ<π 4. Xác định chỉ số m và n của giá trị lượng tử hóa rho và theta m=M-ρmax-ρj,kM-12ρmaxN n=N-π-ФN-12πN 5. Tăng ma trận Hough H(m,n) = H(m,n) + G(j,k) Hình 17.4-9 cho một ví dụ về phiên bản O’Gorman và Clowes của biến đổi Hough. Ảnh gốc gồm 512×512 pixels và ma trận Hough gồm 511×511 ô ảnh gốc b) Sobel edge gradient c) ma trận Hough Hình 17.4-9 Phiên bản O’Gorman và Clowes của biến đổi Hough của ảnh 1 cao ốc. Kesidis và Papamarkos đã phát triển một thuật toán cho việc tính toán biến đổi Hough ngược (IHT) của một ảnh nhị phân. Thuật toán này xác định những đỉnh của những đường cong hình sin trong không gian biến đổi Hough(HT) và phân tích mỗi đường hình sin để cho ra một ảnh đồng nhất với ảnh gốc ngọai trừ những lượng tử hóa có tác động lỗi nhỏ. Họ đề xuất một bộ lọc trong không gian HT như là trung bình của các cạnh trích ra trong ảnh trên chuẩn cơ bản của chúng, sự định hướng và định vị Công việc xác định những đường thẳng được công thức hóa bởi Aggarwal và Karl như một bài toán ngược. Sự hình thành công thức này trên cơ sở của sự biến đổi Radon ngược, có liên quan đến sự định vị miền và hướng của biên ảnh của một ảnh vào như là sự bắt buộc có thể được thiết lập để khử nhiểu ảnh. Phần 2: Ứng dụng biến đổi Hough để xác định những cạnh là đoạn thẳng trong một ảnh xám. Input: ảnh xám bất kì. Tìm bản đồ cạnh bằng phương pháp Canny Tính toán ma trận biến đổi Hough Xác định vùng với ngưỡng T Xác định giá trị Minlength và Fillgap Xác định những đoạn thẳng từ ma trận Hough Out put: ảnh đã được xác định các đoạn thẳng Ví dụ: ảnh ‘test.jpg’ Xác định biên ảnh bằng phương pháp Canny: Code mathlab: clear % ######################################################################### % # Image file introducing (image must be balck and white or gray mode). % ######################################################################### [filename, pathname] = uigetfile( ... { '*.*', 'All Files (*.*)'}, ... 'Import first image'); filename=strcat(char(pathname),char(filename)); % ######################################################################### % # Edge detection stage, so result is a binary file. % ######################################################################### I=imread(filename); BW = edge(I,'Canny'); figure(1), imshow(I); figure(2), imshow(BW); Biến đổi Hough của ảnh bản đồ cạnh: Code matlab: [H,T,R] = hough(BW); imshow(H,[],'XData',T,'YData',R,'InitialMagnification','fit'); xlabel('\theta'), ylabel('\rho'); axis on, axis normal, hold on; P = houghpeaks(H,100000,'threshold',ceil(0.3*max(H(:)))); x = T(P(:,2)); y = R(P(:,1)); plot(x,y,'s','color','white'); Từ ma trận biến đổi Hough xác định những đường trên bản đồ cạnh: Code matlab: % Find lines and plot them lines = houghlines(BW,T,R,P,'FillGap',3,'MinLength',1); figure, imshow(BW), hold on max_len = 0; for k = 1:length(lines) xy = [lines(k).point1; lines(k).point2]; plot(xy(:,1),xy(:,2),'LineWidth',2,'Color','blue'); % Determine the endpoints of the longest line segment len = norm(lines(k).point1 - lines(k).point2); if ( len > max_len) max_len = len; xy_long = xy; end end % highlight the longest line segment plot(xy_long(:,1),xy_long(:,2),'LineWidth',2,'Color','blue'); figure, imshow(I), hold on max_len = 0; for k = 1:length(lines) xy = [lines(k).point1; lines(k).point2]; plot(xy(:,1),xy(:,2),'LineWidth',2,'Color','blue'); % Determine the endpoints of the longest line segment len = norm(lines(k).point1 - lines(k).point2); if ( len > max_len) max_len = len; xy_long = xy; end end % highlight the longest line segment plot(xy_long(:,1),xy_long(:,2),'LineWidth',2,'Color','blue'); Out put: Có thể dùng một ảnh xám khác: bằng cách chạy file Hough.m trong thư mục Sourcecode.