BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI NGUYỄN XUÂN HẠNH NGHIÊN CỨU PHÉP TÍNH TỐN HÌNH THÁI VÀ PHÂN TÁCH CÁC PẦN TỬ CẤU TRÚC LUẬN VĂN THẠC SĨ NGÀNH ĐẢM BẢO TỐN HỌC CHO MÁY TÍNH VÀ HỆ THƠNG TÍNH TỐN Hà Nội, 2010 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI NGUYỄN XUÂN HẠNH NGHIÊN CỨU PHÉP TÍNH TỐN HÌNH THÁI VÀ PHÂN TÁCH CÁC PẦN TỬ CẤU TRÚC LUẬN VĂN THẠC SĨ NGÀNH ĐẢM BẢO TỐN HỌC CHO MÁY TÍNH VÀ HỆ THƠNG TÍNH TỐN NGƯỜI HƯỚNG DẪN: TS NGƠ QUỐC TẠO Hà Nội, 2010 MỤC LỤC MỤC LỤC Chương - Giới thiệu phép tốn hình thái 1.1 Giới thiệu xử lý ảnh 1.1.1 Tổng quan hệ thống xử lý ảnh 1.1.2 Các vấn đề xử lý ảnh 11 1.1.2.1 Một số khái niệm .11 1.1.2.2 Biểu diễn ảnh 12 1.1.2.3 Tăng cường ảnh – khôi phục ảnh 13 1.1.2.4 Biến đổi ảnh 13 1.1.2.5 Phân tích ảnh 14 1.1.2.6 Nhận dạng ảnh 14 1.1.2.7 Nén ảnh 16 1.2 Tổng quan phép tốn hình thái .16 1.2.1 Một số khái niệm tập hợp 17 1.2.1.1 Một số phép toán ảnh nhị phân 17 1.2.1.2 Các phép toán logic ảnh nhị phân 19 1.2.2 Các khái niệm hình thái 20 1.2.3 Bốn nguyên tắc hình thái 24 Chương - Các tính chất phép tốn hình thái .26 2.1 Các phép tốn hình thái nhị phân 26 2.1.1 Phép giãn (Dilation) 26 2.1.2 Phép co (Erosion) 27 2.1.3 Phép biến đổi trúng hay trượt (Hit-or- miss transformation) 28 2.1.4 Phép mở (Opening) phép đóng (Closing) 29 2.2 Tính chất phép tốn hình thái .29 2.2.1 Phép giãn (Dilation) 29 2.2.2 Phép co (Erosion) 31 2.2.3 Phép mở (Opening) phép đóng (Closing) 32 2.3 Các phép tốn hình thái cho ảnh đa cấp xám 32 2.3.1 Phép giãn co đa cấp xám 32 2.3.2 Lý thuyết đối ngẫu phép giãn co đa cấp xám 35 2.3.3 Phép mở đóng đa cấp xám 36 Chương - Ứng dụng phép tốn hình thái 37 3.1 Ứng dụng làm trơn ảnh .37 3.2 Phát biên 38 3.3 Làm mảnh ảnh 39 3.4 Làm béo .42 3.5 Tô miền .42 3.6 Trích chọn thành phần liên thông .44 3.7 Tìm xương ảnh 45 3.8 Đếm vùng ảnh 46 Chương - Tách phần tử cấu trúc 48 4.1 Tổng quan tách phần tử cấu trúc 48 4.1.1 Tách phần tử cấu trúc có dạng hình học .48 4.1.1.1 Định nghĩa dạng phần tử cấu trúc 48 4.1.1.2 Các tính chất phép tách 52 4.1.1.3 Các phần tử cấu trúc dạnh hình học chiều .54 4.1.1.4 Các phần tử cấu trúc dạnh hình học hai chiều 59 4.1.1.5 Tách phần tử cấu trúc tuần hoàn Cosine biến đổi lớn 63 4.1.1.6 Tách phần tử cấu trúc hai chiều thành phần tử cấu trúc chiều 63 4.2 Phép toán GAs 64 4.2.1 Giới thiệu GAs .64 4.2.2 Thuật giải di truyền 65 4.2.3 Thể giả thuyết .68 4.2.4 Các toán tử di truyền 70 4.2.5 Hàm thích nghi chọn lọc 72 4.3 Tách phần tử cấu trúc 73 4.3.1 Tách phần tử cấu trúc nhị phân 73 4.3.1.1 Tổng quan phép tách sử dụng GAs 74 4.3.1.2 Ưu điểm phép tách phần tử cấu trúc 75 4.3.1.3 Kỹ thuật tách sử dụng GAs 76 4.3.2 Tách phần tử cấu trúc đa cấp xám 81 4.3.2.1 Các tính chất tổng quát phép tách phần tử cấu trúc 82 4.3.2.2 Tách phần tử cấu trúc đa cấp xám tùy ý chiều 83 4.3.2.3 Tách phần tử cấu trúc đa cấp xám tùy ý hai chiều 88 Chương - Cài đặt ứng dụng .92 5.1 Chương trình .92 5.2 Các bước thực 92 5.3 Kết 93 5.4 Đánh giá kết 95 Lời nói đầu Xử lý ảnh tốn học hình thái ngày phát triển chiếm vị trí quan trọng nhiều lĩnh vực Bởi ngày ảnh số đa phương tiện bao gồm nhận dạng đối tượng, kiểm tra, phát tự động sử dụng rộng rãi Để nhận dạng phân tích ảnh, người ta thường biến đổi ảnh sang dạng biểu diễn khác tốt Các kỹ thuật xử lý ảnh phát triển nhanh năm thập kỷ gần đây, theo chúng, toán học hình thái ln có đóng góp to lớn cung cấp miêu tả định lượng cấu trúc hình học hình dạng miêu tả toán học đại số, topo, xác suất hình học tích phân Tốn tử hình thái biết nhánh sinh học mà liên quan đến hình dạng cấu trúc động vật thực vật Nó hỗ trợ phân tích dạng hình dạng đối tượng Tốn tử hình thái dựa lý thuyết tập, topo, dàn đại số, hàm ,… sử dụng công cụ cho trích chọn thành phần ảnh mà sử dụng biểu diễn miêu tả hình dạng đối tượng Tốn tử hình thái sử dụng trình tiền xử lý ảnh, tăng cường cấu trúc đối tượng… Ngoài ứng dụng quan trọng mà tơi đề cập luận văn phần tác phần tử cấu trúc thành phần tử cấu trúc nhỏ Việc tách phần tử cấu trúc có lợi ích sau: Thứ nhất, làm giảm phép toán ứng dụng mà phần tử tham gia Thứ hai, giảm khơng gian lưu trữ ảnh Thứ ba, hệ thống hỗ trợ tập lệnh SIDM (Single Instruction Multiple Data) phần tử nhỏ nhiều phần tử cấu trúc, việc phân rã phần tử cấu trúc thành phần tử nhỏ cần thiết Nội dung đề tài giới thiệu sở lý thuyết, khái niệm tốn học hình thái phép giãn, phép co,…; tính chất ứng dụng phép tốn hình thái; tìm hiểu thuật toán di truyền, lai ghép, đột biến tái sinh lựa chọn; tách phần tử cấu trúc, sâu vào khái niệm, tính chất phần tử cấu trúc từ đưa phương pháp, tính chất thuật tốn tách phần tử cấu trúc Nội dung luận văn gồm có chương: Chương : Giới thiệu phép tốn hình thái Chương : Các tính chất phép tốn hình thái Chương 3: Ứng dụng phép tốn hình thái Chương 4: Tách phần tử cấu trúc Chương 5: Cài đặt ứng dụng Danh mục hình Hình 1.1 Các giai đoạn xử lý ảnh 10 Hình 1.2 Các thành phần hệ thống xử lý ảnh .11 Hình 1.3 Phép đảo ảnh .18 Hình 1.4 Ví dụ tập điểm 22 Hình 1.5 Các phần tử cấu trúc 23 Hình 1.6 Tịnh tiến với véc tơ 23 Hình 2.1 Phép giãn 27 Hình 2.2 Phép co 27 Hình 2.3 Phép biến đổi trúng hay trượt 29 Hình 2.4 Phép giãn mà điểm biểu diễn không thuộc phần tử cấu trúc 30 Hình 2.5 Phép Umbra .33 Hình 3.1 Làm trơn ảnh đa cấp xám 38 Hình 3.2 Kết phép tách biên 39 Hình 3.3 Chuỗi phần tử cấu trúc 40 Hình 3.4 Làm gầy hình thái .41 Hình 3.5 Tơ miền .43 Hình 3.6 Trích chọn thành phần liên thơng tốn học hình thái 45 Hình 3.8 Một phép tìm xương hình thái 46 Hình 3.9 Đếm vùng 47 Hình 4.1 Một phần tử cấu trúc dốc tuyến tính 49 Hình 4.2 Một ảnh nhị phân f phần tử cấu trúc cosine lớn k 50 Hình 4.3 Một phần tử cấu trúc lồi 51 Hình 4.4 Một phần tử cấu trúc lõm 52 Hình 4.5 Một ví dụ phép co giãn nhị phân phần tử cấu trúc lồi 58 Hình 4.6 Thuật giải di truyền mẫu 67 Hình 4.7 Sơ đồ thuật toán tách 75 Hình 4.8 Các vị trí tương ứng với gen .78 Hình 4.9 Phép lai điểm phần tử cấu trúc kích thước 3x3 79 Hình 4.10 Đột biến điểm 80 Hình 4.11 Sơ đồ thuật tốn tách 81 Hình 4.12 phép giãn phần tử cấu trúc định lý 4.8 85 Hình 4.13 Sơ đồ tách phần tử cấu trúc chiều 87 Hình 4.14 Tách theo hàng phần tử cấu trúc hai chiều .89 Hình 4.15 Biểu diễn phép quay 89 Hình 4.16 Biểu đồ tách kết hợp hàng vào cột 90 Hình 5.1 Ảnh đầu vào 93 Hình 5.2 Các ảnh đầu 93 Hình 5.3 Ảnh đầu vào 94 Hình 5.4 Các ảnh đầu .94 Danh mục bảng Bảng 1.1 Bảng chân lý phép AND, OR, NOT, NAND, NOR, XOR 20 Bảng 4.1 Các phần tử cấu trúc dạng hình học chiều 56 Bảng 4.2Các phần tử cấu trúc dạng hình học hai chiều 60 Bảng 4.3 Các toán tử chung cho thuật giải di truyền 71 semihyperbola Gausian giới thiệu Shih Wu [1992] Trong phần này, giới thiệu phương pháp tách tổng quát để tách phần tử cấu trúc tùy ý chiều Cho gốc phần tử cấu trúc được xác định điểm bên trái Phép tách phần tử cấu trúc có kích thước lẻ n biểu diễn sau: [a1, a2, a3, … , an] = [ b11 , b21 , b31 ] ⊕ [ b12 , b22 , b32 ] ⊕ … ⊕ [ b1( n−1) / , b2( n−1) / , b3( n−1) / ] (4.58) Và tách phần tử cấu trúc có kích thước chẵn m biểu diễn sau: [a1, a2, a3, … , am] =[c1, c2] ⊕ [ b11 , b21 , b31 ] ⊕ [ b12 , b22 , b32 ] ⊕ … ⊕ [ b1( m−2) / , b2( m−2) / , b3( m−2) / ] (4.59) Với ai, b kj cl hệ số phần tử cấu trúc Chú ý b kj hệ số thứ j phần tử cấu trúc thứ k, với j (1 ≤ j ≤ 3) k (1 ≤ k ≤ (n-1)/2) số nguyên Ví dụ, phần tử cấu trúc có kích thước tách phép giãn ba phần tử cấu trúc nhỏ kích thước 3, b21 hệ số thứ hai phần tử cấu trúc thứ Định lý 4.8: Nếu phần tử cấu trúc thỏa mãn hai điều kiện sau, tách phương trình 4.58 4.59 Cho SN = [a1, a2, a3, … , ac…, aN], với ac phần tử đỉnh, N số lẻ Hai điều kiện là: a1 ≤ a2 ≤ a3 ≤ … ≤ ac ac ≥ ac+1 ≥ …≥ aN a2 – a1 ≥ a3 - a2 ≥ … ac - ac-1 ac - ac+1 ≤ ac+1 - ac+2 ≤ …≤ aN-1 - aN Chứng minh: Giả sử SN tách thành SN-2 S3, với SN-2 = [a1, a2, a3, … ,aN-2] nhận cách lấy N-2 phần tử SN, S3 = [c1, c2, c3] tính tốn sử dụng c1 = 0, c2 = aN-1 – aN-2 c3 = aN – aN-2 Chúng ta chứng minh điều cách chọn SN-2 S3 theo cách này, SN = SN-2 ⊕ S3 Cho ay-2, ay-1, ay ba phần tử liên tiếp SN-2 Bằng cách tìm vị trí ay SN-2 ⊕ S3 hình 4.12 có ba giá trị: ay, (aN-1 – aN-2) + ay-1, (aN – aN-2) + ay-2 84 Chúng ta cần chứng minh ay giá trị lớn Bằng cách trừ ay từ ba giá trị, có 0, (aN-1 – aN-2) + (ay-1 - ay), (aN – aN-2) + (ay-2 - ay) Ta chứng minh (aN-1 – aN-2) + (ay-1 - ay) ≤ 0, (aN – aN-2) + (ay-2 - ay) ≤ theo ba trường hợp sau: Nếu ay-2 phía bên phải ac (có nghĩa aN-2 phía bên phải ac) Từ điều kiện (a),chúng ta có ac ≥ ay-2 ≥ ay-1 ≥ ay ≥…≥ aN-2 ≥ aN-1 ≥ aN Bằng cách kết hợp C3 (a) Trong ay : SN-2 S3 = [ aN-1 – aN-2 = [ a1, a2,…, ay-2 C1 C2 , , aN – aN-2 ay-1 , , ay ] ,…, aN-2] (b) kết phép giãn: a y −2 + (a N − a N −2 ),  (a y −2 − a y ) + (a N − a N −2 ),      max a y −1 + (a N −1 − a N −2 ) = max (a y −1 − a y ) + (a N −1 − a N −2 )     0   a y + Hình 4.12 phép giãn phần tử cấu trúc định lý 4.8 điều kiện (b), có có ay-1 – ay ≤ aN-2 – aN-1 ay-2 – ay-1 ≤ aN-1 – aN Từ hai bất đẳng thức ta có (aN-1 – aN-2) + (ay-1 - ay) ≤ 0, (aN – aN-2) + (ay-2 - ay) ≤ Nếu ay aN nằm phía phải ac: Chúng ta có ay-1 – ay ≤ ay-2 – ay ≤ a1 ≤…≤ ay-2 ≤ ay-1 ≤ ay ≤ ac Chúng ta có aN – aN-1 ≤ ay – ay-1 aN – aN-2 ≤ ay – ay-2 a2 – a1 ≥ a3 - a2 ≥ … ac - ac-1 a1 ≤…≤ ay-2 ≤ ay-1 ≤ ay ≤ …≤ aN-2 ≤ aN-1 ≤ aN ≤ ac Do có (aN-1 – aN-2) + (ay-1 - ay) ≤ 0, (aN – aN-2) + (ay-2 - ay) ≤ Nếu ay phía bên trái cuả ac, aN-2 phía bên phải ac: Chúng ta có aN-1 - aN-2 ≤ aN - aN-2 ≤ a1 ≤…≤ ay-2 ≤ ay-1 ≤ ay ≤ ac Do đó,chúng ta có (aN-1 – aN-2) + (ay-1 - ay) ≤ 0, (aN – aN-2) + (ay-2 - ay) ≤ Tương tự, tiếp tục tách SN-2 tách đên phần tử có kích thước Từ ta có điều phải chứng minh 85 Để ý hai điều kiện định lý 4.8 gọi tăng lồi theo tâm Nếu phần tử cấu trúc thuộc dạng này, tách phương trình 4.58 4.59 Chúng ta tách phần tử cấu trúc đa cấp xám tùy ý thành dạng phương trình 4.60 4.61, n m số lẻ chẵn tương ứng Giả sử (a) (b) kà trường hợp riêng phép tách tổng quát phần tử cấu trúc đa cấp xám tùy ý Bằng cách áp dụng thuật toán ra, phần tử cấu trúc thỏa mãn giả thiết (a) (b), phép giãn cho kết thành hai thành phần tách giống phần tử cấu trúc ban đầu, tốn tốn lớn không cần thiết Như kết quả, thành phần tách tương đương sử dụng phương trình 4.58 4.59 [ a1 , a , a3 , , a n ] = ([b1(1,1) , b2(1,1) , b3(1,1) ] ⊕ [b1(1, ) , b2(1, ) , b3(1, ) ] ⊕ ⊕ [b1(1,n −1) / , b2(1,n −1) / , b3(1,n −1) / ]) ( ) ,   ( 2,1) ( 2,1) ( 2,1)  (4.60) ( 2, ) ( 2, ) ( 2, ) ( , n −3) / , b2( 2,n −3) / , b3( 2,n −3) / ]) ( ) , ([b1 , b2 , b3 ] ⊕ [b1 , b2 , b3 ] ⊕ ⊕ [b1 max     ([b (( n −1) / 2,1) , b (( n −1) / 2,1) , b (( n −1) / 2,1) ])  ( n −3 )   [a1 , a2 , a3 , , am ] = (c1 , c2 ) ⊕ ([b1(1,1) , b2(1,1) , b3(1,1) ] ⊕ [b1(1, ) , b2(1, ) , b3(1, ) ] ⊕ ⊕ [b1(1,m−2 ) / , b2(1,m−2 ) / , b3(1,m−2 ) / ]) ( ) ,   ( 2,1) ( 2,1) ( 2,1) ( 2, ) ( 2, ) ( 2, ) ( 2,m−2 ) / , b2( 2,m−2 ) / , b3( 2,m−2 ) / ]) (1) ,  ([b1 , b2 , b3 ] ⊕ [b1 , b2 , b3 ] ⊕ ⊕ [b1   ( 3,1) ( 3,1) ( 3,1) ( 3, ) ( 3, ) ( 3, ) ( 3, m − ) / ( 3, m − ) / ( 3, m − ) / , b2 , b3 ]) (1) ,  ([b , b2 , b3 ] ⊕ [b1 , b2 , b3 ] ⊕ ⊕ [b1 max   (4.61)     ( m / 2,1) ( m / 2,1) ( m / 2,1) , b2 , b3 ]) ( m−4 ) ,  ([b1  ([×, ×, e]) ( m−3)   Với e, c1, c2 b (j t , k ) hệ số phần tử cấu trúc b (j t , k ) hệ số thứ j phần tử cấu trúc thứ k phép tách thứ t Cho SN phần tử cấu trúc kích thước N Thuật tốn để tách phần tử cấu trúc chiều biểu diễn đây, có biểu đồ hình 4.13 86 Start Chẵn hay lẻ Chẵn Tách SN SN = max(SN-1 ⊕ S2,SN) lẻ Đúng Kích thước SN >3? Gán SN = SN-1 Sai Nhận kết Tách SN SN = max(SN-2 ⊕ S3,SN) Gán SN = SN-2 Hình 4.13 Sơ đồ tách phần tử cấu trúc chiều Thuật toán tách chiều: Nếu SN chẵn, chuyển đến bước Tách SN = [a1, a2, a3,…,aN] thành SN-1 S2, với SN-1= [a1, a2, a3,…,aN-1] nhận cách lấy N-1 phần tử SN, S2 = [d1, d2] tính sử dụng d1 = d2 = aN - aN-1 So sánh SN SN-1 ⊕ S2 Nếu chúng nhau, có SN = SN-1 ⊕ S2; ngược lại, SN = max{ SN-1 ⊕ [0, X], [X, aN](N-2)} Để ý là, khơng số thuật tốn có, thuật tốn biểu diễn khơng cần kiểm tra dạng phần tử cấu trúc trước tách phần tử cấu trúc Trong thực tế, kết phép so sánh SN SN-1 ⊕ S2 thực không quan tâm phần tử cấu trúc có tách hay không Gán SN = SN-1 Nếu N ≤ 3, chuyển đến bước Tách SN = [a1, a2, a3,…,aN] thánh SN-2 S3,với SN-2= [a1, a2, a3,…,aN-2] nhận cách lấy N-2 phần tử SN, S3 = [c1, c2, c3] tính sử dụng c1 = 0, c2 = aN-1 - aN-2, c3 = aN - aN-2 So sánh SN SN-2 ⊕ S3 Nếu chúng nhau, có SN = SN-2 ⊕ S3; ngược lại, SN = max{SN-2 ⊕ [0, 0, X],[X, aN-1, aN-2](N-3)} Gán SN = SN-2 quay lại bước Lấy kết phép tách Cho m k số nguyên ≤ k ≤ m Với phần tử cấu trúc kích thước lẻ, SN = max{ Qk, Pk}, với kích 87 thước chẳn, SN = max{Pk} với Pk = S 31 ⊕ S 32 ⊕ ⊕ S 3k Qk = S ⊕ S 31 ⊕ S 32 ⊕ ⊕ S 3k Ví dụ: Cho S = [0, 2, 4, 6, 5, 4, 3] Từ đây, S phần tử cấu trúc dốc tuyến tính Áp dụng thuật tốn tách, ta có kết quả: S = [b11 , b21 , b31 ]⊕ [b12 , b22 , b32 ] ⊕ [b13 , b23 , b331 ] = [0, 2, 4] ⊕ [0, 2, 1] ⊕ [0, -1, -2] 4.3.2.3 Tách phần tử cấu trúc đa cấp xám tùy ý hai chiều Chúng ta tách phần tử cấu trúc đa cấp xám tùy ý hai chiều hai phương pháp Một phương pháp tách chúng thành tập phần tử cấu trúc hàng hay cột chiều, phần tử tiếp tục tách sử dụng phương pháp đề cập phần Hình 4.14 tách hàng, với phần tử cấu trúc hàng dịch (x, y) Phép tịnh tiến giải thích hình 4.15 với (a) miêu tả hệ trục tọa độ, (b) phép tịnh tiến (2, 0), (c) phép tịnh tiến (0, 2) Một phương pháp khác, gọi hướng tiếp cận kết hợp hàng cột, để tách phần tử cấu trúc đa cáp xám hai chiều biểu diễn sau Nó lặp tách phần tử cấu trúc đa cấp xám hai chiều thành phép giãn thành phần cấu trúc hàng chiều cột chiều phần tử cấu trúc ban đầu xây dựng lại phép hợp tất phép giãn cặp thành phần cấu trúc đa cấp xám chiều hàng cột Lược đồ biểu diễn hình 4.16 Cho SN×N phần tử cấu trúc hai chiều kích thước N×N, cho BN×1 C1×N thành phần cấu trúc cột hang chiều kích thước N tương ứng Thuật tốn tách kết hợp cột hàng hai chiều: Chọn hàng cột thực tách SN×N = max{BN×1 C1×N, S N' × N } Chúng ta thấy tách hàng Tách cột nhận tương tự 88 8 9 10 11 10 10 5      = max            = max      ⊕ 11 10 5 5 -1 -2 (0,2) ⊕ (0,0) 2 ⊕ 3 (0,-2)    (0,1)   (0,-1)  (0,2) 10 10 (0,0) (0,-2) ⊕ ⊕ -2 -3   (0,1)    (0,-1)    Hình 4.14 Tách theo hàng phần tử cấu trúc hai chiều (-,+) x x x x Y x x x x (+,+) x x x x x x x x x x x x X (-,-) (+,-) (2,0) b a 3 (0,2) x x x x x x x x x x x x x x x x x x x x c Hình 4.15 Biểu diễn phép quay 89 Start Tách SN×N SN×N = max{BN×1 ⊕ C1×N, S N' × N } Gán SN×N = S N' × N Sai Tất phần tử SN×N “x” Đúng Tách phần tử BN×1 C1×N Nhận kết Hình 4.16 Biểu đồ tách kết hợp hàng vào cột Chúng ta chọn hàng, giả sử BN×1, lớn tổng phần tử hàng SN×N C1×N nhận cách chọn nhỏ hàng ma trận sinh từ phép trừ hàng SN×N với BN×1 Tạo S N' × N cách so sánh SN×N BN×1 ⊕ C1×N Tức gán S ('i , j ) thành X giá trị tương ứng S N' × N [BN×1 ⊕ C1×N](i,j) giống nhau; ngược lại gán S ('i , j ) = S(i,j) Để ý là, (i, j) hàng thứ i cột thứ j hệ tọa độ Nếu tất phần tử S N' × N là, chuyển đên bước Gán SN×N = S N' × N quay lại bước Tách BN×1và C1×N thành phần tử cấu trúc nhỏ với kích thước sử dụng thuật toán đề cập phần trước 90 Chương - Cài đặt ứng dụng 5.1 Chương trình Chương trình cài đặt ngơn ngữ Visual C++ 2008 thuộc Microsoft Visual Studio NET 2008 sử dụng thư viện OpenCV 1.1 Chương trình chạy dạng Console Sử dụng: Với ảnh đầu vào có chứa phần tử với màu khác màu ảnh Sau thực chạy chương trình, kết cho ảnh phần tử chứa ảnh gốc 5.2 Các bước thực o Tiền xử lý Với ảnh đầu vào, thực tăng độ tương phản ảnh biến đổi tuyến tính Xóa nhiễu hàm cvSmooth (áp dụng lọc Gaussian) o Xử lý Lựa chọn thuật tốn, tìm tham số thích hợp để cài đặt Mỗi thuật tốn khác input, output, parameter Vấn đề khó khăn tìm thuật tốn tham số hợp lý cho nhiều ảnh input Một thuật toán khơng hiệu kết hợp nhiều thuật toán xử lý khác để đạt mục đích Trong chương trình tơi áp dụng thuật tốn Canny để tìm biên (Canny có tham số quan trọng ngưỡng) o Hậu xử lý Sau thực xử lý chính, cần hiệu chỉnh kết : Sử dụng morphology, giảm bớt lỗi, dán nhãn miền (region labeling), tạo mặt nạ (mask) cho objects, … Trong chương trình, sử dụng toán tử Dilate Erode để làm tốt kết sau Canny (Dilate để nối đoạn biên chưa liên tục sau Canny, điều làm tăng độ dày biên Ta sử dụng Erode để giảm độ dày biên.).Sau dùng cvFloodFill để tìm mask ảnh 92 5.3 Kết Với ảnh đầu vào Hình 5.1 Ảnh đầu vào Cho ta ảnh đầu Hình 5.2 Các ảnh đầu 93 Với ảnh đầu vào Hình 5.3 Ảnh đầu vào Cho kết Hình 5.4 Các ảnh đầu 94 5.4 Đánh giá kết Với vật có màu khác với màu chương trình cho kết tương đối tốt Ảnh vật tách cịn có viền theo vật phần phát biên điền đầy vùng chưa tốt 95 Kết luận Bản luận văn trình bày cách có hệ thống khái niệm sở, đến nâng cao việc ứng dụng phép toán hình thái xử lý ảnh Đồng thời nêu tính chất ứng dụng phép tốn hình thái Phần quan trọng luận văn trình bày tách phần tử cấu trúc Luận văn nêu khái niệm tính chất phần tử cấu trúc, khái niệm giải thuật di truyền Với cách tiếp cận từ ảnh nhị phân đến ảnh đa cấp xám Từ ảnh đa cấp xám tùy ý chiều đến ảnh đến ảnh đa cấp xám tùy ý hai chiều, với phần đưa sơ đồ thuật toán thuật toán để tách phần tử cấu trúc tương ứng Phần cuối luận văn đưa chương trình ứng dụng tách phần tử ảnh Với ảnh đầu vào chứa phần tử Kết chương trình cho ảnh phần tử ảnh Các kết đạt luận văn: o o o o o o o Giới thiệu tổng quan xử lý ảnh phép toán hình thái Các kiến thức sở phép tốn hình thái Các khái niệm nâng cao, tính chất phép tốn hình thái Các ứng dụng phép tốn hình thái Các khái niệm giải thuật di truyền Nghiên cứu phép tách phần tử cấu trúc Áp dụng kiến thức nghiên cứu đề tài cài đặt chương trình ứng dụng Những vấn đề tồn tại: Do thời gian tìm hiểu đề tài chưa nhiều nên phần ứng dụng cho kết chưa tốt Chưa thực cài đặt thuật toán tách phần tử cấu trúc đa cấp xám tùy ý hai chiều 96 Trong thời gian tới tơi hy vọng giải vấn đề tồn trên, tiếp trục nghiên cứu thêm tốn học hình thái để xây dựng số ứng dụng hữu ích 97 Tài liệu tham khảo Tiếng Việt Lương Mạnh Bá, Nguyễn Thanh Thủy (2003), Nhập môn xử lý ảnh số, Nxb Khoa học kỹ thuật, Hà Nội Nguyễn Đình Thúc, Lập trình tiến hố, NXB Giáo dục Tiếng Anh William K Pratt (2007), Digital Image Processing - 4th Edition, PixelSoft, Inc Los Altos, California Tinku Acharya, Ajoy K Ray (2005), Image Processin Principles and Applications, John Wiley & Sons Inc., Hoboken, New Jersey Ian T Young, Jan J Gerbrands,Lucas J van Vliet, Fundamentals of Image Processing (1998), The Netherlands at the Delft University of Technology.-Up Mathematical Morphology Computations with Special-Purpose Array Processors,Sciences, T.N Mudge and B.D Shriver, eds., vol 1, pp 321-330, Maui, Hawaii, Jan 4-7 1994 Los Alamitos, Calif.: IEEE Computer Society G Matheron, Random Sets and Integral Geometry New York: John Wiley, 1975 Rafael C Gonzalez, Richard E Woods, Steven L Eddins (2003), Digital Image Processing Using Matlab, Prentice Hall Tinku Acharya, Ajoy K Ray (2005), Image Processin Principles and Applications, John Wiley & Sons Inc., Hoboken, New Jersey John C Russ (2006), The Image Processing Handbook, CRC Press, English 10 Milan SonKa, Vaclav Hlavac, Roger Boyle (2008), Image Processing, Analysis, and Machine Vision, International Student Edition, Thomson Learning, USA 98 11 A.Broggi (1994), “Speeding-Up Mathematical Morphology Computations with Special-Purpose Array Processors ”,Sciences, T.N Mudge and B.D Shriver, eds., vol 1, pp 321-330, Maui, Hawaii, Jan Los Alamitos, Calif.: IEEE Computer Society 12 Frank Y Shih (2009), Image Processing and Mathematical Morphology: Fundamentals and Applications, CRC Press, USA 13 X.Zhuang and R.M Haralick (1986), “Morphological Structuring Element Decomposition”, Computer Vision, Graphics, and Image Processing, vol.35,pp.370-382, Sept 14 H Park and R.T.Chin (1995), “Decomposition of Arbitrarity Shaped Morphological Structuring Elements”,IEEE Trans Pattern Analysis and Machine Intelligence, vol 17, no 1, Jan 15 J Serra (1982), Image Analysis and Mathematical Morphology, Academic Press, London 16 Anelli, G., Broggi, A., and Destri (1998), “Decomposition of arbitrarily shaped binary morphological structuring elements using genetic algorithms,” IEEE Trans Pattern Analysis and Machine Intelligence, vol 20, no 2, pp 217–224 17 Hollar (1975) Adaptation in Natural and Artii cial Systems, The University of Michigan Press, Ann Arbor, MI 18 http://www.google.com.vn/ 99 ... thành phần cấu trúc nhỏ Trong phần này, giới thiệu số kỹ thuật sử dụng tách phần tử cấu trúc hình thái 4.1.1 Tách phần tử cấu trúc có dạng hình học Một số ứng dụng rộng sử dụng phần tử cấu trúc hình. .. Sơ đồ thuật toán tách 81 Hình 4.12 phép giãn phần tử cấu trúc định lý 4.8 85 Hình 4.13 Sơ đồ tách phần tử cấu trúc chiều 87 Hình 4.14 Tách theo hàng phần tử cấu trúc hai chiều... Các phần tử cấu trúc dạnh hình học hai chiều 59 4.1.1.5 Tách phần tử cấu trúc tuần hoàn Cosine biến đổi lớn 63 4.1.1.6 Tách phần tử cấu trúc hai chiều thành phần tử cấu trúc chiều 63 4.2 Phép