Giáo trình Xử lý hình ảnh - Đỗ Năng Toàn

Nội dung text: Giáo trình Xử lý hình ảnh - Đỗ Năng Toàn

1. 4o. Phân loại dựa trên mạng nơ-ron nhân tạo. Trong các ứng dụng rõ ràng là không thể chỉ dùng có một cách tiếp cận đơn lẻ để phân loại “tối ưu” do vậy cần sử dụng cùng một lúc nhiều phương pháp và cách tiếp cận khác nhau. Do vậy, các phương thức phân loại tổ hợp hay được sử dụng khi nhận dạng và nay đã có những kết quả có triển vọng dựa trên thiết kế các hệ thống lai (hybrid system) bao gồm nhiều mô hình kết hợp. Việc giải quyết bài toán nhận dạng trong những ứng dụng mới, nảy sinh trong cuộc sống không chỉ tạo ra những thách thức về thuật giải, mà còn đặt ra những yêu cầu về tốc độ tính toán. Đặc điểm chung của tất cả những ứng dụng đó là những đặc điểm đặc trưng cần thiết thường là nhiều, không thể do chuyên gia đề xuất, mà phải được trích chọn dựa trên các thủ tục phân tích dữ liệu. 1.1.2.7 Nén ảnh Nhằm giảm thiểu không gian lưu trữ. Thường được tiến hành theo cả hai cách khuynh hướng là nén có bảo toàn và không bảo toàn thông tin. Nén không bảo toàn thì thường có khả năng nén cao hơn nhưng khả năng phục hồi thì kém hơn. Trên cơ sở hai khuynh hướng, có 4 cách tiếp cận cơ bản trong nén ảnh: • Nén ảnh thống kê: Kỹ thuật nén này dựa vào việc thống kê tần xuất xuất hiện của giá trị các điểm ảnh, trên cơ sở đó mà có chiến lược mã hóa thích hợp. Một ví dụ điển hình cho kỹ thuật mã hóa này là *.TIF • Nén ảnh không gian: Kỹ thuật này dựa vào vị trí không gian của các điểm ảnh để tiến hành mã hóa. Kỹ thuật lợi dụng sự giống nhau của các điểm ảnh trong các vùng gần nhau. Ví dụ cho kỹ thuật này là mã nén *.PCX • Nén ảnh sử dụng phép biến đổi: Đây là kỹ thuật tiếp cận theo hướng nén không bảo toàn và do vậy, kỹ thuật thướng nến hiệu quả hơn. *.JPG chính là tiếp cận theo kỹ thuật nén này. • Nén ảnh Fractal: Sử dụng tính chất Fractal của các đối tượng ảnh, thể hiện sự lặp lại của các chi tiết. Kỹ thuật nén sẽ tính toán để chỉ cần lưu trữ phần gốc ảnh và quy luật sinh ra ảnh theo nguyên lý Fractal 1.2. THU NHẬN VÀ BIỂU DIỄN ẢNH 1.2.1. Thu nhận, các thiết bị thu nhận ảnh 11
2. Các thiết bị thu nhận ảnh bao gồm camera, scanner các thiết bị thu nhận này có thể cho ảnh đen trắng Các thiết bị thu nhận ảnh có 2 loại chính ứng với 2 loại ảnh thông dụng Raster, Vector. Các thiết bị thu nhận ảnh thông thường Raster là camera các thiết bị thu nhận ảnh thông thường Vector là sensor hoặc bàn số hoá Digitalizer hoặc được chuyển đổi từ ảnh Raster. Nhìn chung các hệ thống thu nhận ảnh thực hiện 1 quá trình • Cảm biến: biến đổi năng lượng quang học thành năng lượng điện • Tổng hợp năng lượng điện thành ảnh 1.2.2. Biểu diễn ảnh Ảnh trên máy tính là kết quả thu nhận theo các phương pháp số hoá được nhúng trong các thiết bị kỹ thuật khác nhau. Quá trình lưu trữ ảnh nhằm 2 mục đích: • Tiết kiệm bộ nhớ • Giảm thời gian xử lý Việc lưu trữ thông tin trong bộ nhớ có ảnh hưởng rất lớn đến việc hiển thị, in ấn và xử lý ảnh được xem như là 1 tập hợp các điểm với cùng kích thước nếu sử dụng càng nhiều điểm ảnh thì bức ảnh càng đẹp, càng mịn và càng thể hiện rõ hơn chi tiết của ảnh người ta gọi đặc điểm này là độ phân giải. Việc lựa chọn độ phân giải thích hợp tuỳ thuộc vào nhu cầu sử dụng và đặc trưng của mỗi ảnh cụ thể, trên cơ sở đó các ảnh thường được biểu diễn theo 2 mô hình cơ bản 1.2.2.1. Mô hình Raster Đây là cách biểu diễn ảnh thông dụng nhất hiện nay, ảnh được biểu diễn dưới dạng ma trận các điểm (điểm ảnh). Thường thu nhận qua các thiết bị như camera, scanner. Tuỳ theo yêu cầu thực thế mà mỗi điểm ảnh được biểu diễn qua 1 hay nhiều bít Mô hình Raster thuận lợi cho hiển thị và in ấn. Ngày nay công nghệ phần cứng cung cấp những thiết bị thu nhận ảnh Raster phù hợp với tốc độ nhanh và chất lượng cao cho cả đầu vào và đầu ra. Một thuận lợi cho việc hiển thị trong môi trường Windows là Microsoft đưa ra khuôn dạng ảnh DIB (Device Independent Bitmap) làm trung gian. Hình 1.4 thể hình quy trình chung để hiển thị ảnh Raster thông qua DIB. 12
3. Một trong những hướng nghiên cứu cơ bản trên mô hình biểu diễn này là kỹ thuật nén ảnh các kỹ thuật nén ảnh lại chia ra theo 2 khuynh hướng là nén bảo toàn và không bảo toàn thông tin nén bảo toàn có khả năng phục hồi hoàn toàn dữ liệu ban đầu còn nếu không bảo toàn chỉ có khả năng phục hồi độ sai số cho phép nào đó. Theo cách tiếp cận này người ta đã đề ra nhiều quy cách khác nhau như BMP, TIF, GIF, PCX Hiện nay trên thế giới có trên 50 khuôn dạng ảnh thông dụng bao gồm cả trong đó các kỹ thuật nén có khả năng phục hồi dữ liệu 100% và nén có khả năng phục hồi với độ sai số nhận được. BMP Paint PCC . DIB . Cửa sổ Thay đổi Hình 1.4. Quá trình hiển thị và chỉnh sửa, lưu trữ ảnh thông qua DIB 1.2.2.2. Mô hình Vector Biểu diễn ảnh ngoài mục đích tiết kiệm không gian lưu trữ dễ dàng cho hiển thị và in ấn còn đảm bảo dễ dàng trong lựa chọn sao chép di chuyển tìm kiếm Theo những yêu cầu này kỹ thuật biểu diễn vector tỏ ra ưu việt hơn. Trong mô hình vector người ta sử dụng hướng giữa các vector của điểm ảnh lân cận để mã hoá và tái tạo hình ảnh ban đầu ảnh vector được thu nhận trực tiếp từ các thiết bị số hoá như Digital hoặc được chuyển đổi từ ảnh Raster thông qua các chương trình số hoá Công nghệ phần cứng cung cấp những thiết bị xử lý với tốc độ nhanh và chất lượng cho cả đầu vào và ra nhưng lại chỉ hỗ trợ cho ảnh Raster. Do vậy, những nghiên cứu về biểu diễn vectơ đều tập trung từ chuyển đổi từ ảnh Raster. Vecter Raster RASTER hóa VECTOR hóa RASTER Hình 1.5. Sự chuyển đổi giữa các mô hình biểu diễn ảnh 13
4. Chương 2: CÁC KỸ THUẬT NÂNG CAO CHẤT LƯỢNG ẢNH 2.1. CÁC KỸ THUẬT KHÔNG PHỤ THUỘC KHÔNG GIAN 2.1.1. Giới thiệu Các phép toán không phụ thuộc không gian là các phép toán không phục thuộc vị trí của điểm ảnh. Ví dụ: Phép tăng giảm độ sáng , phép thống kê tần suất, biến đổi tần suất v.v Một trong những khái niệm quan trọng trong xử lý ảnh là biểu đồ tần suất (Histogram) Biểu đồ tần suất của mức xám g của ảnh I là số điểm ảnh có giá trị g của ảnh I. Ký hiệu là h(g) Ví dụ: 1 2 0 4 1 0 0 7 I = 2 2 1 0 4 1 2 1 2 0 1 1 g 0 1 2 4 7 h(g) 5 7 5 2 1 2.1.2. Tăng giảm độ sáng Giả sử ta có I ~ kích thước m × n và số nguyên c Khi đó, kỹ thuật tăng, giảm độc sáng được thể hiện for (i = 0; i 0: ảnh sáng lên • Nếu c < 0: ảnh tối đi 14
5. 2.1.3. Tách ngưỡng Giả sử ta có ảnh I ~ kích thước m × n, hai số Min, Max và ngưỡng θ khi đó: Kỹ thuật tách ngưỡng được thể hiện for (i = 0; i = θ? Max : Min; * Ứng dụng: Nếu Min = 0, Max = 1 kỹ thuật chuyển ảnh thành ảnh đen trắng được ứng dụng khi quét và nhận dạng văn bản có thể xảy ra sai sót nền thành ảnh hoặc ảnh thành nền dẫn đến ảnh bị đứt nét hoặc dính. 2.1.4. Bó cụm Kỹ thuật nhằm giảm bớt số mức xám của ảnh bằng cách nhóm lại số mức xám gần nhau thành 1 nhóm Nếu chỉ có 2 nhóm thì chính là kỹ thuật tách ngưỡng. Thông thường có nhiều nhóm với kích thước khác nhau. Để tổng quát khi biến đổi người ta sẽ lấy cùng 1 kích thước bunch_size h(g) g 0 I [i,j] = I [i,j]/ bunch - size * bunch_size ∀(i,j) Ví dụ: Bó cụm ảnh sau với bunch_size= 3 1 2 4 6 7 2 1 3 4 5 I = 7 2 6 9 1 4 1 2 1 2 15
6. 0 0 3 6 6 0 0 3 3 3 Ikq = 6 0 6 9 0 3 0 0 0 0 2.1.5. Cân bằng histogram Ảnh I được gọi là cân bằng "lý tưởng" nếu với mọi mức xám g, g’ ta có h(g) = h(g’) Giả sử, ta có ảnh I ~ kích thước m × n new_level ~ số mức xám của ảnh cân bằng m× n TB = ~ số điểm ảnh trung bình của mỗi mức xám new_ level của ảnh cân bằng g t(g) = ∑ h(i) i=0 ~ số điểm ảnh có mức xám ≤ g Xác định hàm f: g a f(g) ⎧ ⎛ t(g) ⎞ ⎫ Sao cho: f (g) = max⎨0,round⎜ ⎟ −1⎬ ⎩ ⎝ TB ⎠ ⎭ Ví dụ: Cân bằng ảnh sau với new_level= 4 1 2 4 6 7 2 1 3 4 5 I = 7 2 6 9 1 4 1 2 1 2 g h(g) t(g) f(g) 1 5 5 0 2 5 10 1 3 1 11 1 4 3 14 2 5 1 15 2 6 2 17 2 7 2 19 3 9 1 20 3 16
7. 0 1 2 2 3 1 0 1 2 2 Ikq = 3 1 2 3 0 2 0 1 0 1 Chú ý: Ảnh sau khi thực hiện cân bằng chưa chắc đã là cân bằng "lý tưởng " 2.1.6. Kỹ thuật tách ngưỡng tự động Ngưỡng θ trong kỹ thuật tách ngưỡng thường được cho bởi người sử dụng. Kỹ thuật tách ngưỡng tự động nhằm tìm ra ngưỡng θ một cách tự động dựa vào histogram theo nguyên lý trong vật lý là vật thể tách làm 2 phần nếu tổng độ lệnh trong từng phần là tối thiểu. Giả sử, ta có ảnh I ~ kích thước m × n G ~ là số mức xám của ảnh kể cả khuyết thiếu t(g) ~ số điểm ảnh có mức xám ≤ g 1 g m(g) = ∑i.h(i) t(g) i=0 ~ mômen quán tính TB có mức xám ≤ g Hàm f: g a f (g) t(g) f (g) = []m(g) − m(G −1) 2 mxn − t(g) Tìm θ sao cho: f ()θ = max{f (g)} 0≤g<G−1 Ví dụ: Tìm ngưỡng tự động của ảnh sau 0 1 2 3 4 5 0 0 1 2 3 4 I = 0 0 0 1 2 3 0 0 0 0 1 2 0 0 0 0 0 1 Lập bảng g g h(g) t(g) g.h(g) ∑ih(i) m(g) f(g) i=0 0 15 15 0 0 0 1.35 1 5 20 5 5 0,25 1.66 17
8. 2 4 24 8 13 0,54 1.54 3 3 27 9 22 0,81 1.10 4 2 29 8 30 1,03 0.49 5 1 30 5 35 1,16 ∞ Ngưỡng cần tách θ= 1 ứng với f(θ)= 1.66 2.1.7. Biến đổi cấp xám tổng thể Nếu biết ảnh và hàm biến đổi thì ta có thể tính được ảnh kết quả và do đó ta sẽ có được histogram của ảnh biến đổi. Nhưng thực tế nhiều khi ta chỉ biết histogram của ảnh gốc và hàm biến đổi, câu hỏi đặt ra là liệu ta có thể có được histogram của ảnh biến đổi. Nếu có như vậy ta có thể hiệu chỉnh hàm biến đổi để thu được ảnh kết quả có phân bố histogram như mong muốn. Bài toán đặt ra là biết histogram của ảnh, biết hàm biến đổi hãy vẽ histogram của ảnh mới. Ví dụ: g 1 2 3 4 h(g) 4 2 1 2 g + 1 nếu g ≤ 2 f(g)= g nếu g = 3 g – 1 nếu g > 3 Bước 1: Vẽ Histogram của ảnh cũ f(g) g 0 18
9. Bước 2: Vẽ đồ thị hàm f(g) h(g) 0 g Bước 3: Vẽ Histogram của ảnh mới Đặt q = f(g) h(q) = card ({P| I(P) = q}) = card ({P| I(P) = f(g)}) = card ({P| g = f-1 (I(P))}) = ∑ h(i) i∈ f −1 (q) h(g) f(g) g 0 Histogram của ảnh mới thua được bằng cách chồng hình và tính giá trị theo các q (= f(g)) theo công thức tính trên. Kết quả cuối thu được sau phép quay góc 90 thuận chiều kim đồng hồ. 19
10. 2.2. CÁC KỸ THUẬT PHỤ THUỘC KHÔNG GIAN 2.2.1. Phép cuộn và mẫu Giả sử ta có ảnh I kích thước M × N, mẫu T có kích thước m × n khi đó, ảnh I cuộn theo mẫu T được xác định bởi công thức. m−1 n−1 I ⊗T(x, y) = ∑ ∑ I()()x + i, y + j *T i, j (2.1) i=0 j=0 m−1 n−1 Hoặc I ⊗T(x, y) = ∑ ∑ I()()x − i, y − j *T i, j (2.2) i=0 j=0 VD: 1 2 4 5 8 7 2 1 1 4 2 2 I = 4 5 5 8 8 2 1 2 1 1 4 4 7 2 2 1 5 2 T = 1 0 0 1 1 1 I ⊗T(x, y) = ∑ ∑ I()()()()()()x + i, y + j *T i, j = I x, y *T 0,0 + I x +1, y +1 *T 1,1 i=0 j=0 = I()x, y + I(x +1, y +1) 2 3 8 7 10 * 7 6 9 12 4 * Tính theo (2.1) I ⊗ T = 6 6 6 12 12 * 3 4 2 6 6 * * * * * * * Tính theo công thức 2.2 * * * * * * * 2 3 8 7 10 I ⊗ T = * 7 6 9 12 4 * 6 6 6 12 12 * 3 4 2 6 6 20
11. * Nhận xét: - Trong quá trình thực hiện phép cuộn có một số thao tác ra ngoài ảnh, ảnh không được xác định tại những vị trí đó dẫn đến ảnh thu được có kích thước nhá hơn. - Ảnh thực hiện theo công thức 2.1 và 2.2 chỉ sai khác nhau 1 phép dịch chuyển để đơn giản ta sẽ hiểu phép cuộn là theo công thức 2.1 2.2.2. Một số mẫu thông dụng - Mẫu: 1 1 1 T1 = 1 1 1 1 1 1 ~ Dùng để khử nhiễu ⇒ Các điểm có tần số cao VD1: 1 2 4 5 8 7 2 31 1 4 2 2 I = 4 5 5 8 8 2 1 2 1 1 4 4 7 2 2 1 5 2 55 65 45 46 * * 52 58 34 35 * * I ⊗ T1 = 29 27 35 35 * * * * * * * * * * * * * * Áp dụng kỹ thuật cộng hằng số với c = -27, ta có: 28 38 18 19 * * 25 31 7 8 * * Ikq = 2 0 8 8 * * * * * * * * * * * * * * - Mẫu: 0 -1 0 T2 = -1 4 -1 0 -1 0 21
12. ~ Dùng để phát hiện các điểm có tần số cao VD2: 114 -40 0 -14 * * -22 5 14 16 * * I ⊗ T2 =-1 -6 -10 -2 * * * * * * * * * * * * * * 2.2.3. Lọc trung vị * Định nghĩa 2.1 (Trung vị) Cho dãy x1; x2 ; xn đơn điệu tăng (giảm). Khi đó trung vị của dãy ký hiệu là Med({xn}), được định nghĩa: ⎡n ⎤ + Nếu n lẻ x⎢ + 1⎥ ⎣2 ⎦ ⎡n ⎤ ⎡n⎤ x + 1 + Nếu n chẵn: x⎢ ⎥ hoặc ⎢ ⎥ ⎣2⎦ ⎣2 ⎦ * Mệnh đề 2.1 n ∑ x − xi → min tại Med({xn }) i=1 Chứng minh + Xét trường hợp n chẵn n Đặt M = 2 Ta có: n M M ∑ x − xi = ∑ x − xi + ∑ x − xM +i i=1 i=1 i=1 M M = ∑ ()x − xi + xM +i − x ≥ ∑ xM +i − xi i=1 i=1 M = ∑[]()()xM +1 − xM + xM − xi i=1 M M = ∑∑xM +i − Med(){}xi + xi − Med(){}xi i==11i 22
13. n = ∑ xi − Med(){}xi i=1 + Nếu n lẻ: Bổ sung thêm phần tử Med({xi }) vào dãy. Theo trường hợp n chẵn ta có: n ∑ x − xi + Med(){}xi − Med() {}xi → min tại Med({xn}) i=1 n ∑ x − xi → min tại Med({xn}) i=1 * Kỹ thuật lọc trung vị Giả sử ta có ảnh I ngưìng θ cửa sổ W(P) và điểm ảnh P Khi đó kỹ thuật lọc trung vị phụ thuộc không gian bao gồm các bước cơ bản sau: + Bước 1: Tìm trung vị {I(q)| q ∈ W(P)} → Med (P) + Bước 2: Gán giá trị ⎧I(P) I(P) − Med(P) ≤ θ I(P) = ⎨ ⎩Med(P) Nguoclai Ví dụ: 1 2 3 2 4 16 2 1 I = 4 2 1 1 2 1 2 1 W(3 × 3); θ = 2 1 2 3 2 4 2 2 1 Ikq = 4 2 1 1 2 1 2 1 Giá trị 16, sau phép lọc có giá trị 2, các giá trị còn lại không thay đổi giá trị. 23
14. 2.2.4. Lọc trung bình * Định nghĩa 2.2 (Trung bình) Cho dãy x1, x2 , xn khi đó trung bình của dãy ký hiệu AV({xn}) ddược định nghĩa: ⎛ 1 n ⎞ AV (){}xn = round⎜ ∑ xi ⎟ ⎝ n i=1 ⎠ * Mệnh đề 2.2 n 2 ∑()x − xi → min tại AV ({xn }) i=1 Chứng minh: n 2 Đặt: φ(x) = ∑()x − xi i=1 Ta có: n φ(x) = 2∑()x − xi i=1 ' φ (x) = 0 n ⇔ ∑()x − xi = 0 i=1 1 n ⇔ x = ∑ xi = AV (){}xi n i=1 Mặt khác,φ '' (x) = 2n > 0 ⇒ φ → min tại x = AV ({xi }) Kỹ thuật lọc trung bình Giả sử ta có ảnh I, điểm ảnh P, cửa sổ W(P) và ngưỡng θ. Khi đó kỹ thuật lọc trung bình phụ thuộc không gian bao gồm các bước cơ bản sau: + Bước 1: Tìm trung bình {I(q)| q ∈ W(P)} → AV(P) 24
15. + Bước 2: Gán giá trị ⎧I(P) I(P) − AV (P) ≤ θ I(P) = ⎨ ⎩AV (P) Nguoclai Ví dụ: 1 2 3 2 4 16 2 1 I = 4 2 1 1 2 1 2 1 W(3 × 3); θ = 2 1 2 3 2 4 3 2 1 Ikq = 4 2 1 1 2 1 2 1 Giá trị 16 sau phép lọc trung bình có giá trị 3, các giá trị còn lại giữ nguyên sau phép lọc. 2.2.5. Lọc trung bình theo k giá trị gần nhất Giả sử ta có ảnh I, điểm ảnh P, cửa sổ W(P), ngưỡng θ và số k. Khi đó, lọc trung bình theo k giá trị gần nhất bao gồm các bước sau: + Bước 1: Tìm K giá trị gần nhất {I(q) ⏐q ∈ W(p)} → {k ∼ giá trị gần I(P) nhất} + Bước 2: Tính trung bình {k ∼ giá trị gần I(P) nhất} → AVk(P) + Bước 3: Gán giá trị ⎧I(P) I(P) − AVk (P) ≤ θ I(P) = ⎨ ⎩AVk (P) Nguoclai Ví dụ: 1 2 3 2 4 16 2 1 I = 4 2 1 1 2 1 2 1 W(3 × 3); θ = 2; k = 3 25
16. 1 2 3 2 4 8 2 1 Ikq = 4 2 1 1 2 1 2 1 * Nhận xét: - Nếu k lớn hơn kích thước cửa sổ thì kỹ thuật chính là kỹ thuật lọc trung bình - Nếu k= 1 thì ảnh kết quả không thay đổi ⇒ Chất lượng của kỹ thuật phụ thuộc vào số phân tử lựa chọn k. 2.3. CÁC PHÉP TOÁN HÌNH THÁI HỌC 2.3.1. Các phép toán hình thái cơ bản Hình thái là thuật ngữ chỉ sự nghiên cứu về cấu trúc hay hình học topo của đối tượng trong ảnh. Phần lớn các phép toán của "Hình thái" được định nghĩa từ hai phép toán cơ bản là phép "giãn nở" (Dilation) và phép "co" (Erosion). Các phép toán này được định nghĩa như sau: Giả thiết ta có đối tượng X và phần tử cấu trúc (mẫu) B trong không gian Euclide hai chiều. Kí hiệu Bx là dịch chuyển của B tới vị trí x. Định nghĩa 2.3 (DILATION) Phép "giãn nở" của X theo mẫu B là hợp của tất cả các Bx với x thuộc X. Ta có: X ⊕ B = Bx xU∈X Định nghĩa 2.4 (EROSION) Phép "co" của X theo B là tập hợp tất cả các điểm x sao cho Bx nằm trong X. Ta có: X \ B = {x : Bx ⊆ X} ⎛ 0 x 0 x x ⎞ ⎜ ⎟ ⎜ x 0 x x 0 ⎟ ⎜ 0 x x 0 0 ⎟ B = 8 x Ví dụ: Ta có tập X như sau: X = ⎜ ⎟ ⎜ 0 x 0 x 0 ⎟ ⎜ ⎟ ⎝ 0 x x x 0 ⎠ 26
17. ⎛ 0 x x x x⎞ ⎛ 0 0 0 x 0 ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ x x x x x⎟ ⎜ 0 0 x 0 0 ⎟ ⎜ ⎟ 0 x x x 0 ⎜ 0 x 0 0 0 ⎟ X ⊕ B = ⎜ ⎟ và X\B = ⎜ ⎟ ⎜ 0 x x x x⎟ ⎜ 0 0 0 0 0 ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ 0 x x x x⎠ ⎝ 0 x x 0 0 ⎠ Đình nghĩa 2.5 (OPEN) Phép toán mở (OPEN) của X theo cấu trúc B là tập hợp các điểm của ảnh X sau khi đã co và giãn nở liên liếp theo B. Ta có: OPEN(X,B) = (X \ B) ⊕ B Ví dụ: Với tập X và B trong ví dụ trên ta có ⎛ 0 0 0 x x ⎞ ⎜ ⎟ ⎜ 0 0 x x 0 ⎟ ⎜ ⎟ OPEN(X,B) = (X\B) ⊕ B = ⎜ 0 x x 0 0 ⎟ ⎜ ⎟ ⎜ 0 0 0 0 0 ⎟ ⎜ ⎟ ⎝ 0 x x x 0 ⎠ Định nghĩa 2.6 (CLOSE) Phép toán đóng (CLOSE) của X theo cấu trúc B là tập hợp các điểm của ảnh X sau khi đã giãn nở và co liên tiếp theo B. Ta có: CLOSE(X,B) = (X ⊕ B) \ B Theo ví dụ trên ta có: ⎛ 0 x x x x ⎞ ⎜ ⎟ ⎜ x x x x x ⎟ ⎜ ⎟ CLOSE(X,B) = (X ⊕ B) \ B = ⎜ 0 x x 0 0 ⎟ ⎜ ⎟ ⎜ 0 x x x 0 ⎟ ⎜ ⎟ ⎝ 0 x x x 0 ⎠ 2.3.2. Một số tính chất của phép toán hình thái * Mệnh đề 2.3 [Tính gia tăng]: (i) X ⊆ X’ ⇒ X \ B ⊆ X’ \ B ∀B X ⊕ B ⊆ X’ ⊕ B ∀B (ii) B ⊆ B' ⇒ X \ B ⊇ X \ B' ∀X X ⊕ B ⊆ X ⊕ B’ ∀X 27
18. Chứng minh: (i) X ⊕ B = Bx ⊆ Bx = X '⊕B xU∈X xU∈X ' X \ B = {}x / Bx ⊆ X ⊆ {x / Bx ⊆ X '} = X’ \ B (ii) X ⊕ B = Bx ⊆ B'x = X ⊕ B' xU∈X xU∈X Theo định nghĩa: X \ B’ = {}x / B'x ⊆ X ⊆ {x / Bx ⊆ X} = X \ B . *Mệnh đề 2.4 [Tính phân phối với phép ∪]: (i) X ⊕ (B ∪ B') = (X ⊕ B) ∪ (X ⊕ B') (ii) X\ (B ∪ B') = (X \ B) ∩ (X \B') Chứng minh: (i) X ⊕ (B ∪ B’) = ( X ⊕ B) ∪ (X ⊕ B’) Ta có: B ∪ B’ ⊇ B X ⊕ (B ∪ B’) ⊇ X ⊕ B (tính gia tăng) Tương tự: X ⊕ ( B ∪ B’) ⊇ X ⊕ B’ X ⊕ (B ∪ B’) ⊇ (X ⊕ B) ∪ (X ⊕ B’) (2.3) Mặt khác, ∀ y ∈ X ⊕ (B ∪ B’) ⇒ ∃x ∈ X sao cho y ∈ (B ∪ B’)x ⇒ y ∈ Bx ⇒ y ∈ X ⊕ B y ∈ B’x y ∈ X ⊕ B’ ⇒ y ∈ (X ⊕ B) ∪ (X ⊕ B’) ⇒ X ⊕ (B ∪ B’) ⊆ (X ⊕B ) ∪ (X ⊕B’) (2.4) Từ (2.3) và (2.4) ta có: X ⊕ (B ∪ B’) = (X ⊕ B) ∪ (X ⊕ B’) (ii) X \ (B ∪ B’) = (X \ B) ∩ (X \ B’) Ta có: B ∪ B’ ⊇ B ⇒ X \ (B ∪ B’) ⊆ X \ B (tính gia tăng) Tương tự : X \ (B ∪ B’) ⊆ X \ B’ ⇒ X \ (B ∪ B’) ⊆ (X \ B) ∩ ( X \ B’) (2.5) 28
19. Mặt khác, ∀x ∈ (X \ B) ∩ (X \ B’) Suy ra, x ∈ X \ B ⇒ Bx ⊆ X x ∈ X \ B’ B’x ⊆ X ⇒ ( B ∪ B’)x ⊆ X ⇒ x ∈ X \ (B ∪ B’) ⇒ X \ (B ∪ B’) ⊇ (X \ B) ∩ (X \ B’) (2.6) Từ (2.5) và (2.6) ta có: X \ (B ∪ B’) = (X \ B) ∩ (X \ B’). * Ý nghĩa: Ta có thể phân tích các mẫu phức tạp trở thành các mẫu đơn giản thuận tiện cho việc cài đặt. * Mệnh đề 2.5 [Tính phân phối với phép ∩]: (X ∩ Y) \ B = (X \ B) ∩ (Y \ B) Chứng minh: Ta có, X ∩ Y ⊆ X ⇒ (X ∩ Y) \ B ⊆ X \ B Tương tự: (X ∩ Y) \ B ⊆ Y \ B ⇒ (X ∩ Y) \ B ⊆ (X \ B) ∩ (Y \ B) (2.7) Mặt khác, ∀x ∈ (X \ B) ∩ (Y \ B) Suy ra x ∈ X \ B ⇒ Bx ⊆ X x ∈ Y \ B Bx ⊆ Y ⇒ Bx ⊆ X ∩ Y ⇒ x ∈ ( X ∩ Y) \ B ⇒ (X ∩ Y) \ B ⊇ (X \ B) ∩ (Y \ B) (2.8) Từ (2.7) và (2.8) ta có: (X ∩ Y) \ B = (X \ B) ∩ (Y \ B). * Mệnh đề 2.6 [Tính kết hợp] (i) (X ⊕ B) ⊕ B' = X ⊕ (B ⊕ B') (ii) (X \ B) \ B' = X \ (B ⊕ B') 29
20. Chứng minh: (i) (X ⊕ B) ⊕ B' = X ⊕ (B' ⊕ B) Ta có, (X ⊕ B) ⊕ B' = ( Bx ) ⊕ B' xU∈X ' ' = (Bx ⊕ B ) = (B ⊕ B ) x xU∈X xU∈X = X ⊕ (B' ⊕ B) (i) (X \ B) \ B' = X \ (B ⊕ B') ' ' Trước hết ta đi chứng minh: Bx ⊆ X \ B ⇔ (B ⊕ B) x ⊆ X ' ' Thật vậy, do Bx ⊆ X \ B nên ∀y∈ Bx ⇒ y∈X \ B ⇒ By ⊆ X ⇒ By ⊆ X U' y∈Bx ' ⇒ (B ⊕ B) x ⊆ X ' ' Mặt khác, (B ⊕ B) x ⊆ X ⇔ ( Bx ⊕ B) ⊆ X ⇔ By ⊆ X U' y∈Bx ' ⇒ ∀y∈ Bx ta có By ⊆ X ' ⇒ hay ∀y∈ Bx ta có y ∈ X \ B ' Do đó, Bx ⊆ X \ B Ta có, (X \ B) \ B' = {x / Bx ⊆ X } \ B' ' = {x/ Bx ⊆ X \ B} ' = {x/ (B ⊕ B) x ⊆ X} (do chứng minh ở trên) = X \ (B ⊕ B') . * Định lý 2.1 [X bị chặn bởi các cận OPEN và CLOSE] Giả sử, X là một đối tượng ảnh, B là mẫu, khi đó, X sẽ bị chặn trên bởi tập CLOSE của X theo B và bị chặn dưới bởi tập OPEN của X theo B. Tức là: (X ⊕ B) \ B ⊇ X ⊇ (X \ B) ⊕ B 30
21. Chứng minh: ⊆ Ta có: ∀ x ∈ X ⇒ Bx X ⊕ B (Vì X ⊕ B = Bx ) xU∈X ⇒ x ∈ (X ⊕ B) \ B (theo định nghĩa phép co) ⇒ (X ⊕ B) \ B ⊇ X (2.9) Mặt khác, ∀ y ∈ (X \ B) ⊕ B, suy ra: ∃ x ∈ X \ B sao cho y ∈ Bx (Vì (X\B) ⊕ B = Bx ) x∈UXΘB ⇒ Bx ⊆ X ⇒ y ∈ X Suy ra: X ⊇ (X \ B) ⊕ B (2.10) Từ (2.9) và (2.10) Ta có: (X ⊕ B) \ B ⊇ X ⊇ (X \ B) ⊕ B . *Hệ quả 2.1 [Tính bất biến] : (i) ((X ⊕ B) \B) ⊕ B = X ⊕ B (ii) ((X \ B) ⊕ B) \ B = X\B Chứng minh: (i) Thật vậy, từ định lý 2.1 ta có X ⊆ (X ⊕ B) Ө B ⇒ X ⊕ B ⊆ ((X ⊕ B) \B) ⊕ B (do tính chất gia tăng) (2.11) Mặt khác, cũng từ định lý 2.1 ta có (X \ B) ⊕ B ⊆ X ∀X Do đó, thay X bởi X ⊕ B ta có, ((X ⊕ B) \B) ⊕ B ⊆ X ⊕ B (2.12) Từ (2.11) và (2.12) Ta có: ((X ⊕ B) \B) ⊕ B = X ⊕ B (ii) Thật vậy, từ định lý 2.1 ta có (X \ B) ⊕ B ⊆ X ⇒ ((X \ B) ⊕ B) \ B ⊆ X\B (do tính chất gia tăng) (2.13) Mặt khác, cũng từ định lý 2.1 ta có X ⊆ (X ⊕ B) Ө B ∀X Do đó, thay X bởi X \ B ta có, X\B ⊆ ((X \ B) ⊕ B) \ B (2.14) Từ (2.13) và (2.14) Ta có: ((X \ B) ⊕ B) \ B = X\B (đpcm). 31
22. Chương 3: BIÊN VÀ CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN 3.1. GIỚI THIỆU Biên là vấn đề quan trọng trong trích chọn đặc điểm nhằm tiến tới hiểu ảnh. Cho đến nay chưa có định nghĩa chính xác về biên, trong mỗi ứng dụng người ta đưa ra các độ đo khác nhau về biên, một trong các độ đo đó là độ đo về sự thay đổi đột ngột về cấp xám. Ví dụ: Đối với ảnh đen trắng, một điểm được gọi là điểm biên nếu nó là điểm đen có ít nhất một điểm trắng bên cạnh. Tập hợp các điểm biên tạo nên biên hay đường bao của đối tượng. Xuất phát từ cơ sở này người ta thường sử dụng hai phương pháp phát hiện biên cơ bản: Phát hiện biên trực tiếp: Phương pháp này làm nổi biên dựa vào sự biến thiên mức xám của ảnh. Kỹ thuật chủ yếu dùng để phát hiện biên ở đây là dựa vào sự biến đổi cấp xám theo hướng. Cách tiếp cận theo đạo hàm bậc nhất của ảnh dựa trên kỹ thuật Gradient, nếu lấy đạo hàm bậc hai của ảnh dựa trên biến đổi gia ta có kỹ thuật Laplace. Phát hiện biên gián tiếp: Nếu bằng cách nào đó ta phân được ảnh thành các vùng thì ranh giới giữa các vùng đó gọi là biên. Kỹ thuật dò biên và phân vùng ảnh là hai bài toán đối ngẫu nhau vì dò biên để thực hiện phân lớp đối tượng mà khi đã phân lớp xong nghĩa là đã phân vùng được ảnh và ngược lại, khi đã phân vùng ảnh đã được phân lớp thành các đối tượng, do đó có thể phát hiện được biên. Phương pháp phát hiện biên trực tiếp tỏ ra khá hiệu quả và ít chịu ảnh hưởng của nhiễu, song nếu sự biến thiên độ sáng không đột ngột, phương pháp tỏ ra kém hiệu quả, phương pháp phát hiện biên gián tiếp tuy khó cài đặt, song lại áp dụng khá tốt trong trường hợp này. 3.2. CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN TRỰC TIẾP 3.2.1. Kỹ thuật phát hiện biên Gradient 32