Giáo trình Xử lý ảnh

158 trang phuongnguyen 6700

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Xử lý ảnh", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_xu_ly_anh.doc

Nội dung text: Giáo trình Xử lý ảnh

ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN GIÁO TRÌNH MÔN HỌC XỬ LÝ ẢNH Người soạn : PGS. TS. ĐỖ NĂNG TOÀN, TS. PHẠM VIỆT BÌNH Thái Nguyên, Tháng 11 năm 2007 1
LỜI NÓI ĐẦU Khoảng hơn mười năm trở lại đây, phần cứng máy tính và các thiết bị liên quan đã có sự tiến bộ vượt bậc về tốc độ tính toán, dung lượng chứa, khả năng xử lý v.v và giá cả đã giảm đến mức máy tính và các thiết bị liên quan đến xử lý ảnh đã không còn là thiết bị chuyên dụng nữa. Khái niệm ảnh số đã trở nên thông dụng với hầu hết mọi người trong xã hội và việc thu nhận ảnh số bằng các thiết bị cá nhân hay chuyên dụng cùng với việc đưa vào máy tính xử lý đã trở nên đơn giản. Trong hoàn cảnh đó, xử lý ảnh là một lĩnh vực đang được quan tâm và đã trở thành môn học chuyên ngành của sinh viên ngành công nghệ thông tin trong nhiều trường đại học trên cả nước. Tuy nhiên, tài liệu giáo trình còn là một điều khó khăn. Hiện tại chỉ có một số ít tài liệu bằng tiếng Anh hoặc tiếng Pháp, tài liệu bằng tiếng Việt thì rất hiếm. Với mong muốn đóng góp vào sự nghiệp đào tạo và nghiên cứu trong lĩnh vực này, chúng tôi biên soạn cuốn giáo trình Xử lý ảnh dựa trên đề cương môn học đã được duyệt. Cuốn sách tập trung vào các vấn đề cơ bản của xử lý ảnh nhằm cung cấp một nền tảng kiến thức đầy đủ và chọn lọc nhằm giúp người đọc có thể tự tìm hiểu và xây dựng các chương trình ứng dụng liên quan đến xử lý ảnh. Giáo trình được chia làm 5 chương và phần phụ lục: Chương 1, trình bày Tổng quan về xử lý ảnh, các khai niệm cơ bản, sơ đồ tổng quát của một hệ thống xử lý ảnh và các vấn đề cơ bản trong xử lý ảnh. Chương 2, trình bày các kỹ thuật nâng cao chất lượng ảnh dựa vào các thao tác với điểm ảnh, nâng cao chất lượng ảnh thông qua việc xử lý các điểm ảnh trong lân cận điểm ảnh đang xét. Chương này cũng trình bày các kỹ thuật nâng cao chất lượng ảnh nhờ vào các phép toán hình thái. Chương 3, trình bày các kỹ thuật cơ bản trong việc phát hiện biên của các đối tượng ảnh theo cả hai khuynh hướng: Phát hiện biên trực tiếp và phát hiện biên gián tiếp. Chương 4 thể hiện cách kỹ thuật tìm xương theo khuynh hướng tính toán trục trung vị và hướng tiếp cận xấp xỉ nhờ các thuật toán làm mảnh song song và gián tiếp. Và cuối cùng là Chương 5 với các kỹ thuật hậu xử lý. Giáo trình được biên soạn dựa trên kinh nghiệm giảng dạy của tác giả trong nhiều năm tại các khóa đại học và cao học của ĐH Công nghệ - ĐHQG Hà Nội, ĐH Khoa học tự nhiên – ĐHQG Hà Nội, Khoa Công nghệ thông tin – ĐH Thái Nguyên v.v Cuốn sách có thể làm tài liệu tham khảo cho sinh viên các hệ kỹ sư, cử nhân và các bạn quan tâm đến vấn đề nhận dạng và xử lý ảnh. 2
Các tác giả bày tỏ lòng biết ơn chân thành tới các bạn đồng nghiệp trong Phòng Nhận dạng và công nghệ tri thức, Viện Công nghệ thông tin, Bộ môn Hệ thống thông tin, Khoa Công nghệ thông tin, ĐH Thái Nguyên, Khoa Công nghệ thông tin, ĐH Công nghệ, ĐHQG Hà Nội, Khoa Toán – Cơ – Tin, ĐH Khoa học tự nhiên, ĐHQG Hà Nội đã động viên, góp ý và giúp đỡ để hoàn chỉnh nội dung cuốn sách này. Xin cám ơn Lãnh đạo Khoa Công nghệ thông tin, ĐH Thái Nguyên, Ban Giám đốc ĐH Thái Nguyên đã hỗ trợ và tạo điều kiện để cho ra đời giáo trình này. Mặc dù rất cố gắng nhưng tài liệu này chắc chắn không tránh khỏi những sai sót. Chúng tôi xin trân trọng tiếp thu tất cả những ý kiến đóng góp của bạn đọc cũng như các bạn đồng nghiệp để có chỉnh lý kịp thời. Thư góp ý xin gửi về: Phạm Việt Bình, Khoa Công nghệ thông tin – ĐH Thái nguyên. Xã Quyết Thắng, Tp. Thái Nguyên Điện thoại: 0280.846506 Email: pvbinh@ictu.edu.vn Thái Nguyên, ngày 22 tháng 11 năm 2007 CÁC TÁC GIẢ 3
MỤC LỤC LỜI NÓI ĐẦU 2 MỤC LỤC 4 Chương 1: TỔNG QUAN VỀ XỬ LÝ ẢNH 9 1.1. XỬ LÝ ẢNH, CÁC VẤN ĐỀ CƠ BẢN TRONG XỬ LÝ ẢNH 9 1.1.1. Xử lý ảnh là gì? 9 1.1.2. Các vấn đề cơ bản trong xử lý ảnh 10 1.1.2.1. Một số khái niệm cơ bản 10 1.1.2.2. Nắn chỉnh biến dạng 10 1.1.2.3. Khử nhiễu 11 1.1.2.4. Chỉnh mức xám 11 1.1.2.5. Phân tích ảnh 11 1.1.2.6. Nhận dạng 12 1.1.2.7. Nén ảnh 13 1.2. THU NHẬN VÀ BIỂU DIỄN ẢNH 14 1.2.1. Màu sắc 14 1.2.1.1. Mô hình màu RGB (Red, Green, Bule) 14 1.2.1.2. Mô hình màu CMY (Cyan, Magenta, Yellow) 15 1.2.1.3. Mô hình màu HSV (Hue, Saturation, Value) 16 1.2.1.4. Mô hình màu HLS 19 1.2.2. Thu nhận, các thiết bị thu nhận ảnh 22 1.2.2.1. Giai đoạn lấy mẫu 23 1.2.2.2. Lượng tử hóa 24 1.2.3. Biểu diễn ảnh 24 1.2.3.1. Mô hình Raster 24 1.2.3.2. Mô hình Vector 25 Chương 2: CÁC KỸ THUẬT NÂNG CAO CHẤT LƯỢNG ẢNH 26 2.1. CÁC KỸ THUẬT KHÔNG PHỤ THUỘC KHÔNG GIAN 26 2.1.1. Giới thiệu 26 2.1.2. Tăng giảm độ sáng 26 4
2.1.3. Tách ngưỡng 27 2.1.4. Bó cụm 27 2.1.5. Cân bằng histogram 28 2.1.6. Kỹ thuật tìm tách ngưỡng tự động 29 2.1.7. Biến đổi cấp xám tổng thể 30 2.2. CÁC KỸ THUẬT PHỤ THUỘC KHÔNG GIAN 31 2.2.1. Phép nhân chập và mẫu 31 2.2.2. Một số mẫu thông dụng 33 2.2.3. Lọc trung vị 34 2.2.4. Lọc trung bình 36 2.2.5. Lọc trung bình theo k giá trị gần nhất 37 2.3. CÁC PHÉP TOÁN HÌNH THÁI HỌC 38 2.3.1. Các phép toán hình thái cơ bản 38 2.3.2. Một số tính chất của phép toán hình thái 39 Chương 3: BIÊN VÀ CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN 44 3.1. GIỚI THIỆU 44 3.2. CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN TRỰC TIẾP 44 3.2.1. Kỹ thuật phát hiện biên Gradient 44 3.2.1.1. Kỹ thuật Prewitt 46 3.2.1.2. Kỹ thuật Sobel 47 3.2.1.3. Kỹ thuật la bàn 47 3.2.2. Kỹ thuật phát hiện biên Laplace 48 3.2.3. Kỹ thuật Canny 49 3.3. PHÁT HIỆN BIÊN GIÁN TIẾP 50 3.3.1 Một số khái niệm cơ bản 50 3.3.2. Chu tuyến của một đối tượng ảnh 51 3.3.3. Thuật toán dò biên tổng quát 53 3.4. PHÁT HIỆN BIÊN DỰA VÀO TRUNG BÌNH CỤC BỘ 56 3.4.1. Biên và độ biến đổi về mức xám 56 3.4.2. Phát hiện biên dựa vào trung bình cục bộ 57 5
3.5. PHÁT HIỆN BIÊN DỰA VÀO CÁC PHÉP TOÁN HÌNH THÁI 60 3.5.1. Xấp xỉ trên và xấp xỉ dưới đối tượng ảnh 60 3.5.1. Thuật toán phát hiện biên dựa vào phép toán hình thái 61 Chương 4: XƯƠNG VÀ CÁC KỸ THUẬT TÌM XƯƠNG 63 4.1. GIỚI THIỆU 63 4.2. TÌM XƯƠNG DỰA TRÊN LÀM MẢNH 63 4.2.1. Sơ lược về thuật toán làm mảnh 63 4.2.2. Một số thuật toán làm mảnh 65 4.3. TÌM XƯƠNG KHÔNG DỰA TRÊN LÀM MẢNH 65 4.3.1. Khái quát về lược đồ Voronoi 66 4.3.2. Trục trung vị Voronoi rời rạc 66 4.3.3. Xương Voronoi rời rạc 67 4.3.4. Thuật toán tìm xương 68 Chương 5: CÁC KỸ THUẬT HẬU XỬ LÝ 71 5.1. RÚT GỌN SỐ LƯỢNG ĐIỂM BIỂU DIỄN 71 5.1.1. Giới thiệu 71 5.1.2. Thuật toán Douglas Peucker 71 5.1.2.1. Ý tưởng 71 5.1.2.2. Chương trình 72 5.1.3. Thuật toán Band width 73 5.1.3.1. Ý tưởng 73 5.1.3.2. Chương trình 75 5.1.4. Thuật toán Angles 76 5.1.4.1. Ý tưởng 76 5.1.4.2. Chương trình 76 5.2. XẤP XỈ ĐA GIÁC BỞI CÁC HÌNH CƠ SỞ 77 5.2.1 Xấp xỉ đa giác theo bất biến đồng dạng 78 5.2.1.1. Xấp xỉ đa giác bằng đường tròn 80 5.2.1.2. Xấp xỉ đa giác bằng ellipse 80 5.2.1.3. Xấp xỉ đa giác bởi hình chữ nhật 80 5.2.1.4. Xấp xỉ đa giác bởi đa giác đều n cạnh 81 5.2.2 Xấp xỉ đa giác theo bất biến aphin 81 6
5.3. BIẾN ĐỔI HOUGH 82 5.3.1. Biến đổi Hongh cho đường thẳng 82 5.3.2. Biến đổi Hough cho đường thẳng trong tọa độ cực 84 Chương 6: ỨNG DỤNG XỬ LÝ ẢNH 85 6.1. PHÁT HIỆN GÓC NGHIÊNG VĂN BẢN DỰA VÀO CHU TUYẾN 85 6.1.1. Tính toán kích thước chủ đạo của các đối tượng ảnh 85 6.1.2. Biến đổi Hough và phát hiện góc nghiêng văn bản 87 6.1.2.1. Áp dụng biến đổi Hough trong phát hiện góc nghiêng văn bản 87 6.1.2.2. Thuật toán phát hiện và hiệu chỉnh góc nghiêng văn bản 88 6.1.2.3. Thực nghiệm và kết quả 91 6.2. PHÂN TÍCH TRANG TÀI LIỆU 93 6.2.1. Quan hệ Q 93 6.2.2. Phân tích trang văn bản nhờ khoảng cách Hausdorff bởi quan hệ Q 94 6.2.3. Phân tích trang văn bản dựa vào mẫu 96 6.2.3.1. Đánh giá độ lệch cấu trúc văn bản theo mẫu 96 6.2.3.2. Thuật toán phân tích trang văn bản dựa vào mẫu 99 6.3. CẮT CHỮ IN DÍNH DỰA VÀO CHU TUYẾN 101 6.3.1. Đặt vấn đề 101 6.3.2. Một số khái niệm cơ bản 103 6.3.3. Thuật toán cắt chữ in dính dựa vào chu tuyến 104 6.3.3.1. Phân tích bài toán 104 6.3.3.2. Thuật toán CutCHARACTER cắt chữ in dính dựa vào chu tuyến 106 6.4. NHẬN DẠNG CHỮ VIẾT 107 6.5. TÁCH CÁC ĐỐI TƯỢNG HÌNH HỌC TRONG PHIẾU ĐIỀU TRA DẠNG DẤU 108 6.5.1. Giới thiệu 108 6.5.2. Tách các đối tượng nhờ sử dụng chu tuyến 109 6.6. TÁCH BẢNG DỰA TRÊN TẬP CÁC HÌNH CHỮ NHẬT RỜI RẠC 110 7
6.6.1. Phân tích bài toán 111 6.7. PHÁT HIỆN ĐỐI TƯỢNG CHUYỂN ĐỘNG 113 6.7.1. Phát hiện đối tượng chuyển động dựa theo hướng tiếp cận trừ khung hình liền kề 113 6.7.2. Phát hiện đối tượng chuyển động theo hướng tiếp cận kết hợp 117 6.7.2.1. Trừ ảnh và đánh dấu Iwb 117 6.7.2.2. Lọc nhiễu và phát hiện độ dịch chuyển 118 6.7.2.3. Phát hiện biên ảnh đa cấp xám Igc 118 6.7.2.4. Kết hợp ảnh Igc với Iwb 119 Phụ lục 1: MỘT SỐ ĐỊNH DẠNG TRONG XỬ LÝ ẢNH 121 1. Định dạng ảnh IMG 121 2. Định dạng ảnh PCX 122 3. Định dạng ảnh TIFF 123 4. Định dạng file ảnh BITMAP 125 Phụ lục 2: CÁC BƯỚC THAO TÁC VỚI FILE AVI 127 1. Bước 1: Mở và đóng thư viện 127 2. Bước 2: Mở và đóng file AVI để thao tác: 127 3. Bước 3: Mở dòng dữ liệu để thao tác 128 4. Bước 4: Trường hợp thao tác với dữ liệu hình của phim 128 5. Bước 5: Thao tác với frame 128 Phụ lục 3: MỘT SỐ MODUL CHƯƠNG TRÌNH 129 1. Nhóm đọc, ghi và hiển thị ảnh 129 1.1. Nhóm đọc ảnh 129 1.2. Nhóm ghi ảnh 137 1.3. Nhóm hiển thị ảnh 139 2. Nhóm phát hiện góc nghiêng văn bản 144 TÀI LIỆU THAM KHẢO 157 8
Chương 1: TỔNG QUAN VỀ XỬ LÝ ẢNH 1.1. XỬ LÝ ẢNH, CÁC VẤN ĐỀ CƠ BẢN TRONG XỬ LÝ ẢNH 1.1.1. Xử lý ảnh là gì? Con người thu nhận thông tin qua các giác quan, trong đó thị giác đóng vai trò quan trọng nhất. Những năm trở lại đây với sự phát triển của phần cứng máy tính, xử lý ảnh và đồ hoạ đó phát triển một cách mạnh mẽ và có nhiều ứng dụng trong cuộc sống. Xử lý ảnh và đồ hoạ đóng một vai trò quan trọng trong tương tác người máy. Quá trình xử lý ảnh được xem như là quá trình thao tác ảnh đầu vào nhằm cho ra kết quả mong muốn. Kết quả đầu ra của một quá trình xử lý ảnh có thể là một ảnh “tốt hơn” hoặc một kết luận. Ảnh “Tốt hơn” Ảnh XỬ LÝ ẢNH Kết luận Hình 1.1. Quá trình xử lý ảnh Ảnh có thể xem là tập hợp các điểm ảnh và mỗi điểm ảnh được xem như là đặc trưng cường độ sáng hay một dấu hiệu nào đó tại một vị trí nào đó của đối tượng trong không gian và nó có thể xem như một hàm n biến P(c1, c2, , cn). Do đó, ảnh trong xử lý ảnh có thể xem như ảnh n chiều. Sơ đồ tổng quát của một hệ thống xử lý ảnh: Hệ quyết định Thu nhận ảnh Trích chọn Hậu Đối sánh rút (Scanner, Tiền xử lý ra kết luận Camera,Sensor) đặc điểm xử lý Lưu trữ Hình 1.2. Các bước cơ bản trong một hệ thống xử lý ảnh 1.1.2. Các vấn đề cơ bản trong xử lý ảnh 9
1.1.2.1. Một số khái niệm cơ bản * Ảnh và điểm ảnh: Điểm ảnh được xem như là dấu hiệu hay cường độ sáng tại 1 toạ độ trong không gian của đối tượng và ảnh được xem như là 1 tập hợp các điểm ảnh. * Mức xám, màu Là số các giá trị có thể có của các điểm ảnh của ảnh 1.1.2.2. Nắn chỉnh biến dạng Ảnh thu nhận thường bị biến dạng do các thiết bị quang học và điện tử. P’ Pi i f(Pi) Ảnh thu nhận Ảnh mong muốn Hình 1.3. Ảnh thu nhận và ảnh mong muốn Để khắc phục người ta sử dụng các phép chiếu, các phép chiếu thường được xây dựng trên tập các điểm điều khiển. Giả sử (Pi, Pi’) i = 1, n có n các tập điều khiển Tìm hàm f: Pi f (Pi) sao cho n ' 2  f (Pi ) Pi min i 1 Giả sử ảnh bị biến đổi chỉ bao gồm: Tịnh tiến, quay, tỷ lệ, biến dạng bậc nhất tuyến tính. Khi đó hàm f có dạng: f (x, y) = (a1x + b1y + c1, a2x + b2y + c2) Ta có: n n ' 2 ' 2 ' 2  ( f (Pi) Pi )  a1xi b1 yi c1 xi a2 xi b2 yi c2 yi  i 1 i 1 Để cho  min 10
n n n n  2 ' 0 a1 xi b1 xi yi c1 xi xi xi a     1 i 1 i 1 i 1 i 1 n n n n  2 ' 0  a1 xi yi b1 yi c1 yi  yi xi b1 i 1 i 1 i 1 i 1 n n n  ' 0  a1 xi b1 yi nc1  xi c1 i 1 i 1 i 1 Giải hệ phương trình tuyến tính tìm đượca 1, b1, c1 Tương tự tìm đượca 2, b2, c2 Xác định được hàm f 1.1.2.3. Khử nhiễu Có 2 loại nhiễu cơ bản trong quá trình thu nhận ảnh Nhiều hệ thống: là nhiễu có quy luật có thể khử bằng các phép biến đổi Nhiễu ngẫu nhiên: vết bẩn không rõ nguyên nhân khắc phục bằng các phép lọc 1.1.2.4. Chỉnh mức xám Nhằm khắc phục tính không đồng đều của hệ thống gây ra. Thông thường có 2 hướng tiếp cận: Giảm số mức xám: Thực hiện bằng cách nhóm các mức xám gần nhau thành một bó. Trường hợp chỉ có 2 mức xám thì chính là chuyển về ảnh đen trắng. Ứng dụng: In ảnh màu ra máy in đen trắng. Tăng số mức xám: Thực hiện nội suy ra các mức xám trung gian bằng kỹ thuật nội suy. Kỹ thuật này nhằm tăng cường độ mịn cho ảnh 1.1.2.5. Phân tích ảnh Là khâu quan trọng trong quá trình xử lý ảnh để tiến tới hiểu ảnh. Trong phân tích ảnh việc trích chọn đặc điểm là một bước quan trọng. Các đặc điểm của đối tượng được trích chọn tuỳ theo mục đích nhận dạng trong quá trình xử lý ảnh. Có thể nêu ra một số đặc điểm của ảnh sau đây: Đặc điểm không gian: Phân bố mức xám, phân bố xác suất, biên độ, điểm uốn v.v Đặc điểm biến đổi: Các đặc điểm loại này được trích chọn bằng việc thực hiện lọc vùng (zonal filtering). Các bộ vùng được gọi là “mặt nạ đặc 11
điểm” (feature mask) thường là các khe hẹp với hình dạng khác nhau (chữ nhật, tam giác, cung tròn v.v ) Đặc điểm biên và đường biên: Đặc trưng cho đường biên của đối tượng và do vậy rất hữu ích trong việc trích trọn các thuộc tính bất biến được dùng khi nhận dạng đối tượng. Các đặc điểm này có thể được trích chọn nhờ toán tử gradient, toán tử la bàn, toán tử Laplace, toán tử “chéo không” (zero crossing) v.v Việc trích chọn hiệu quả các đặc điểm giúp cho việc nhận dạng các đối tượng ảnh chính xác, với tốc độ tính toán cao và dung lượng nhớ lưu trữ giảm xuống. 1.1.2.6. Nhận dạng Nhận dạng tự động (automatic recognition), mô tả đối tượng, phân loại và phân nhóm các mẫu là những vấn đề quan trọng trong thị giác máy, được ứng dụng trong nhiều ngành khoa học khác nhau. Tuy nhiên, một câu hỏi đặt ra là: mẫu (pattern) là gì? Watanabe, một trong những người đi đầu trong lĩnh vực này đã định nghĩa: “Ngược lại với hỗn loạn (chaos), mẫu là một thực thể (entity), được xác định một cách ang áng (vaguely defined) và có thể gán cho nó một tên gọi nào đó”. Ví dụ mẫu có thể là ảnh của vân tay, ảnh của một vật nào đó được chụp, một chữ viết, khuôn mặt người hoặc một ký đồ tín hiệu tiếng nói. Khi biết một mẫu nào đó, để nhận dạng hoặc phân loại mẫu đó có thể: Hoặc phân loại có mẫu (supervised classification), chẳng hạn phân tích phân biệt (discriminant analyis), trong đó mẫu đầu vào được định danh như một thành phần của một lớp đã xác định. Hoặc phân loại không có mẫu (unsupervised classification hay clustering) trong đó các mẫu được gán vào các lớp khác nhau dựa trên một tiêu chuẩn đồng dạng nào đó. Các lớp này cho đến thời điểm phân loại vẫn chưa biết hay chưa được định danh. Hệ thống nhận dạng tự động bao gồm ba khâu tương ứng với ba giai đoạn chủ yếu sau đây: 1o. Thu nhận dữ liệu và tiền xử lý. 2o. Biểu diễn dữ liệu. 3o. Nhận dạng, ra quyết định. Bốn cách tiếp cận khác nhau trong lý thuyết nhận dạng là: 1o. Đối sánh mẫu dựa trên các đặc trưng được trích chọn. 2o. Phân loại thống kê. 3o. Đối sánh cấu trúc. 12
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 13
1.2. THU NHẬN VÀ BIỂU DIỄN ẢNH 1.2.1. Màu sắc Mắt người có thể phân biệt được vài chục màu nhưng chỉ có thể cảm nhận được hàng ngàn màu. Ba thuộc tính của một màu đó là: Sắc (Hue), Độ thuần khiết (Saturation), và độ sáng hay độ chói (Itensity). Trong xử lý ảnh và đồ họa, mô hình màu là một chỉ số kỹ thuật của một hệ tọa độ màu 3 chiều với tập các màu nhỏ thành phần có thể trông thấy được trong hệ thống tọa độ màu thuộc một gam màu đặc trưng. Ví dụ như mô hình màu RGB (Red, Green, Blue): là một đơn vị tập các màu thành phần sắp xếp theo hình lập phương của hệ trục tọa độ Đề các. Mục đích của mô hình màu là cho phép các chỉ số kỹ thuật quy ước của một số loại màu sắc thích hợp với các màu sắc của một số gam màu khác. Chúng ta có thể nhìn thấy trong mô hình màu này, không gian màu là một tập hợp nhỏ hơn của không gian các màu có thể nhìn thấy được, vì vậy một mô hình màu không thể được sử dụng để định rõ tất cả có thể nhìn thấy. Sau đây, ta xem xét một số mô hình hay được sử dụng nhất. 1.2.1.1. Mô hình màu RGB (Red, Green, Bule) Màu đỏ, lục – xanh lá cây, lam – xanh da trời (RGB) được sử dụng phổ biến nhất. Những màu gốc RGB được thêm vào những màu gốc khác điều đó tạo nên sự đóng góp riêng của từng màu gốc được thêm cùng nhau để mang lại kết qaủ. Tập hợp màu nhỏ thành phần sắp xếp theo khối lập phương đơn vị. Đường chéo chính của khối lập phương với sự cân bằng về số lượng từng màu gốc tương ứng với các mức độ xám với đen là (0,0,0) và trắng (1,1,1). Blue(0,255) (0, 0, 1) (0,0,0) (0,1,0) green (1,0,0) Red Hình 1.4. Mô hình màu RGB 14
1.2.1.2. Mô hình màu CMY (Cyan, Magenta, Yellow) Là phần bù tương ứng cho các màu đỏ, lục, lam và cúng được sử dụng như những bộ lọc loại trừ các màu này từ ánh sáng trắng. Vì vậy CMY còn được gọi là các phần bù loại trừ của màu gốc. Tập hợp màu thành phần biểu diễn trong hệ tọa độ Đề-các cho mô hình mầu CMY cũng giống như cho mô hình màu RGB ngoại trừ màu trắng (ánh sáng trắng), được thay thế màu đen (không có ánh sáng) ở tại nguồn sáng. Các màu thường được tạo thành bằng cách loại bỏ hoặc được bù từ ánh sáng trắng hơn là được thêm vào những màu tối. Green Yellow Cyan Black Red Blue Magenta Hình 1.5. Các màu gốc bù và sự pha trộn giữa chúng Khi bề mặt được bao phủ bởi lớp mực màu xanh tím, sẽ không có tia màu đỏ phản chiếu từ bề mặt đó. Màu xanh tím đã loại bỏ phần màu đỏ phản xạ khi có tia sáng trắng, mà bản chất là tổng của 3 màu đỏ, lục, lam. Vì thế ta có thể coi màu Cyan là màu trắng trừ đi màu đỏ và đó cũng là màu lam cộng màu lục. Tương tự như vậy ta có màu đỏ thẫm (magenta) hấp thụ màu lục, vì thế nó tương đương với màu đỏ cộng màu lam. Và cuối cùng màu vàng (yellow) hấp thụ màu lam, nó sẽ bằng màu đỏ cộng với lục. Khi bề mặt của thực thể được bao phủ bởi xanh tím và vàng, chúng sẽ hấp thụ hết các phần màu đỏ và xanh lam của bề mặt. Khi đó chỉ tồn tại duy nhất màu lục bị phản xạ từ sự chiếu sáng của ánh sáng trắng. Trong trường hợp khi bề mặt được bao phủ bởi cả 3 màu xanh tím, vàng, đỏ thẫm, hiện tượng hấp thụ xảy ra trên cả 3 màu đỏ, lục và lam. Do đó, màu đen sẽ màu của bề mặt. Những mối liên hệ này có thể được miêu tả bởi: C 1 R M 1 G Y 1 B Hình 1.6. Sự biến đổi từ RGB thành CMY 15
1.2.1.3. Mô hình màu HSV (Hue, Saturation, Value) Các mô hình màu RGB, CMY được định hướng cho phần cứng trái ngược với mô hình màu HSV của Smith hay còn được gọi là mẫu HSB với B là Brightness (độ sáng), được định hướng người sử dụng dựa trên cơ sở nền tảng về trực giác về tông màu, sắc độ và sắc thái mỹ thuật. Hệ thống tọa độ có dạng hình trụ và tập màu thành phần của không gian bên trong mô hình màu được xác định là hình nón hoặc hình chóp sáu cạnh như trong hình 1.7. Đỉnh hình chóp là sáu cạnh khi V= 1 chứa đựng mối quan hệ giữa các màu sáng và những màu trên mặt phẳng với V= 1 đều có màu sáng. Hình 1.7. Mô hình màu HSV Sắc màu (hue) hoặc H được đo bởi góc quanh trục đứng với màu đỏ là 0o, màu lục là 120o, màu lam là 240o (xem hình 1.7). Các màu bổ sung trong hình chóp HSV ở 180o đối diện với màu khác. Giá trị của S là một tập các giá trị đi từ 0 trên đường trục tâm (trục V) đến 1 trên các mặt bên tại đỉnh của hình chóp sáu cạnh. Sự bão hòa được đo tương đối cho gam màu tương ứng với mô hình màu này. Mô hình màu dạng hình chóp sáu cạnh này đường cao V với đỉnh là điểm gốc tọa độ (0,0). Điểm ở đỉnh là màu đen có giá trị tọa độ màu V= 0, tại các điểm này giá trị của H và S là không liên quan với nhau. Khi điểm có S= 0 và V= 1 là điểm màu trắng, những giá trị trung gian của V đối với S= 0 (trên đường thẳng qua tâm) là các màu xám. Khi S= 0 giá trị của H phụ thuộc được gọi bởi các quy ước không xác định, ngược lại khi S khác 0 giá trị của H sẽ là phụ thuộc. Như vậy một màu nào đó V= 1, S= 1 là giốg như màu thuần khiết trong mỹ thuật được sử dụng như điểm khởi đầu trong các màu pha trên. Thêm màu trắng phù hợp để giảm S (không có sự thay đổi V) tạo nên sự thay đổi sắc thái của gam màu. Sự chuyển màu được tạo ra bởi việc giữ S= 1 và giảm V tạo nên sự thay đổi ề sắc độ và tông màu tạo thành bởi việc thay đổi cả hai S và V. 16
Chuyển đổi từ RGB sang HSV Hàm RGB_HSV_Conversion H: Sắc độ màu [0-360] với màu đỏ tại điểm 0 S: Độ bão hòa [0-1] V: Giá trị cường độ sáng [0-1] Max: Hàm lấy giá trị cực đại Min: Hàm lấy giá trị nhỏ nhất { //Xác định giá trị cường độ sáng V= Max(R,G,B) //Xác định độ bão hòa Temp= Min(R,G,B) If V=0 than S= 0 Else S= (V-Temp)/V End //Xác định sắc màu IF s=0 THEN H= Undefined Else Cr= (V-R)/(V-Temp); Cg= (V-G)/(V-Temp); Cb= (V-B)/(V-Temp); // Màu nằm trong khoảng giữa vàng (Yellow) và đỏ tía (Magenta) If R=V then H= Cb-Cg // Màu nằm trong khoảng giữa xanh tím (cyan) và vàng (yellow) If G= V then H= 2+Cr-Cb // Màu nằm trong khoảng giữa đỏ tươi (magenta) và xanh (cyan) 17
If B=V then H= 4+ Cg – Cr H= 60*H // Chuyển sang độ //Loại các giá trị âm If H < 0 then H= H+360 } Chuyển đổi từ HSV sang RGB Hàm HSV_RGB_Conversion() H: Sắc độ màu [0-360] với màu đỏ tại điểm 0 S: Độ bão hòa [0-1] V: Giá trị cường độ sáng [0-1] { //Kiểm tra trường hợp ánh sáng không màu If S=0 then If H=Undifined then R= V G= V B= V Endif Else If H=360 then H= 0 Else H= H/60 endif I= Floor(H) F= H-I M= V*(1-S) N= V*(1-S*F) K= V*(1-S*(1-F)) 18
//(R,G,B)=(V,K,M) R= V; C= K; B= M If I=0 then (R,G,B)=(V,K,M); If I=1 then (R,G,B)=(N,V,M); If I=2 then (R,G,B)=(M,V,K); If I=3 then (R,G,B)=(M,N,V); If I=4 then (R,G,B)=(K,M,V); If I=5 then (R,G,B)=(V,M,N); } 1.2.1.4. Mô hình màu HLS Mô hình màu HLS được xác định bởi tập hợp hình chóp sáu cạnh đôi của không gian hình trụ. Sắc màu là góc quanh trục đứng cảu hình chóp sáu cạnh đôi với màu đỏ tại góc 0o. Các màu sẽ xác định theo thứ tự giống như trong biểu đồ CIE khi ranh giới của nó bị xoay ngược chiều kim đồng hồ: Màu đỏ, màu vàng, màu lục, màu xanh tím, màu lam và đỏ thẫm. Điều này cũng giống như thứ tự sắc xếp trong mẫu hình chóp sáu cạnh đơn HSV. Hình 1.8. Mô hình màu HLS 19
Chúng ta có thể xem mẫu HLS như một sự biến dạng cảu mẫu HSV mà trong đó mãu này màu trắng được kéo hướng lên hình chóp sáu cạnh phía trên từ mặt V= 1. Như với mẫu hình chóp sáu cạnh đơn, phần bổ sung của một màu sắc được đặt ở vị trí 180 o hơn là xunh quanh hình chóp sáu cạnh đôi, sự bão hòa được đo xung quanh trục đứng, từ 0 trên trục tới 1 trên bề mặt. Độ sáng bằng không cho màu đen và bằng một cho màu trắng. Chuyển đổi từ RGB sang HLS Hàm RGB_HLS_Conversion() H: Sắc độ màu [0-360] với màu đỏ tại điểm 0 S: Độ bão hòa [0-1] V: Giá trị cường độ sáng [0-1] Max: Hàm lấy giá trị cực đại Min: Hàm lấy giá trị nhỏ nhất { //Xác định độ sáng M1= Max(R,G,B) M2= Min(R,G,B) L= (M1+M2) //Xác định độ bão hòa If M1=M2 //Trường hợp không màu S= 0 H= Undefined Else If L <= 0.5 then //Trường hợp màu S= (M1-M2)/(M1+M2) Else S= (M1-M2)/(2-M1-M2) Endif //Xác định sắc độ Cr= (M1-R)/(M1-M2) Cg= (M1-G)/(M1-M2) Cb= (M1-B)/(M1-M2) if R=M1 then 20
H= Cb-Cg If G=M1 then H= 2+Cr-Cb If B=M1 then H= 4+Cg-Cr H= H*60 if H<0 then H= H+360 endif } Chuyển đổi từ HLS sang RGB Hàm HLS_RGB_Conversion() H: Sắc độ màu [0-360] với màu đỏ tại điểm 0 S: Độ bão hòa [0-1] V: Giá trị cường độ sáng [0-1] { If L <= 0.5 then M2= L*(1+S) Else M2= L+S-L*S Endif M1= 2*L-M2 //Kiểm tra độ bão hòa = 0 If S=0 then If H=Undefined R=L G=L B=L Else //Error: Dữ liệu nhập sai Endif Else //Xác định giá trị của RGB 21
RGB(H+120, M1,M2,Value) R= Value RGB(H, M1,M2,Value) G= Value RGB(H-120, M1,M2,Value) B= Value Endif } //Hàm điều chỉnh giá trị của H cho phù hợp khoảng xác định Hàm RGB(H, M1, M2, Value) { If H =60 and H = 180 and H 240 and H <= 360 then Value= M1 Return } 1.2.2. Thu nhận, các thiết bị thu nhận ảnh 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. 22
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 (giai đoạn lấy mẫu) Tổng hợp năng lượng điện thành ảnh (giai đoạn lượng tử hóa) 1.2.2.1. Giai đoạn lấy mẫu Người ta sử dụng bộ cảm biến hoặc máy quét để biến tín hiệu quang của ảnh thành tín hiệu điện liên tục. Phương pháp sử dụng máy quét phổ biến hơn. Máy quét sẽ quét theo chiều ngang để tạo ra tín hiệu điện của ảnh, kết quả cho ra một tín hiệu điện hai chiều f(x,y) liên tục. δnh chδa tín hiδu quang Dạng tín hiệu ảnh hδc Xét ảnh liên tục được biểu diễn bởi hàm f(x, y), gọi x là khoảng cách giữa hai điểm được giữ lại theo trục x, gọi y là khoảng cách giữa hai điểm được giữ lại theo trục y. y , x được gọi là chu kỳ lấy mẫu theo trục x và y. Giai đoạn lấy mẫu sẽ biến hàm liên tục f(x,y) f(n x , m y ). Với m,n là nguyên. Theo SHANON để đảm bảo không xảy ra hiện tượng chồng phổ, cho phép tái tạo lại ảnh gốc từ ảnh đã số hóa: - Gọi fx =1 là tần số lấy mẫu theo trục x. x - Gọi fy =1 là tần số lấy mẫu theo trục y. y Để không xảy ra hiện tượng chồng phổ thì tần số lấy mẫu phải ít nhất phải lớn hơn hoặc bằng 2 tần số cao nhất của tín hiệu ảnh. Tức là: fx >= 2fxmax fy >= 2fymax Trong đó fxmax, fymax là tần số cao nhất của tín hiệu theo trục x, y. 23
1.2.2.2. Lượng tử hóa Ảnh sau khi lấy mẫu sẽ có dạng f(m,n) với m, n là nguyên nhưng giá trị f(m, n) vẫn là giá trị vật lý liên tục. Quá trình biến đổi giá trị f(m,n) thành một số nguyên thích hợp để lưu trữ gọi là lượng tử hoá. Đây là quá trình ánh xạ một biến liên tục u vào biến rời rạc u* thuộc tập hữu hạn [u 1, u2, uL] xác định trước, L là mức lượng tử hoá được tạo ra. Ví dụ: + Tạo ảnh đa cấp xám thì L=256, f(m,n) = g 0, 255 + Tạo ảnh 224 thì L=224, f(m, n) = g 0, 224 1 1.2.3. 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.3.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. 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 24
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.9. Quá trình hiển thị và chỉnh sửa, lưu trữ ảnh thông qua DIB 1.2.3.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.10. Sự chuyển đổi giữa các mô hình biểu diễn ảnh 25
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 2.1.3. Tách ngưỡng 26
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 27
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 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 28
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ìm 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ìm 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 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 29
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 30
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ồ. 2.2. CÁC KỸ THUẬT PHỤ THUỘC KHÔNG GIAN 2.2.1. Phép nhân chập 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 nhân chập 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 31
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 * Nhận xét: - Trong quá trình thực hiện phép nhân chập 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 nhân chập là theo công thức 2.1 2.2.2. Một số mẫu thông dụng - Mẫu: 32
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 ~ 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ị 33
* Đị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 1 i 1 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 34
* 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ị. 35
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 x min  i 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) 36
+ 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 37
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 B x với x thuộc X. Ta có: X  B = Bx x 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 B x 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 =  x Ví dụ: Ta có tập X như sau: X = 0 x 0 x 0 0 x x x 0 38
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 39
Chứng minh: (i) X  B = Bx  Bx X 'B x X x X ' X  B = x / Bx  X  x / Bx  X ' = X’  B (ii) X  B = Bx  B'x X  B' x X x 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) 40
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 B x  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') 41
Chứng minh: (i) (X  B)  B' = X  (B'  B) Ta có, (X  B)  B' = ( Bx )  B' x X ' ' = (Bx  B ) = (B  B ) x x X x X = X  (B'  B) (i) (X  B)  B' = X  (B  B') ' ' Trước hết ta đi chứng minh: B xX  B  X(B  B) x ' ' Thật vậy, do B xX  B nên y Bx y X  B By  X  By  X ' y Bx ' (B X B) x ' ' Mặt khác, (B X B )(x B)  X Bx  By  X ' y Bx ' y Bx ta có By  X ' hay y Bx ta có y X  B ' Do đó, B xX  B Ta có, (X  B)  B' = x / Bx  X   B' ' = {x/ Bx  X  B} ' = {x/ (B X} B(do) x 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 42
Chứng minh:  Ta có:  x X Bx X  B (Vì X  B =  Bx ) x 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 X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). 43
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à kỹ thuật lấy đạo hàm. Nếu lấy đạo hàm bậc nhất của ảnh ta có các kỹ thuật Gradient, nếu lấy đạo hàm bậc hai của ảnh ta có kỹ thuật Laplace. Ngoài ra còn có một số các tiếp cận khác 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. Sự khác biệt cơ bản giữa hai phương pháp này là: Phương pháp phát hiện biên trực tiếp cho ta kết quả là ảnh biên, còn phương pháp phát hiện biên trực tiếp cho ta kết quả là đường biên. 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 Theo định nghĩa, gradient là một véctơ có các thành phần biểu thị tốc độ thay đổi giá trị của điểm ảnh, ta có: 44
f (x, y) f (x dx, y) f (x, y) fx x dx f (x, y) f (x, y dy) f (x, y) fy y dy Trong đó, dx, dy là khoảng cách (tính bằng số điểm) theo hướng x và y. * Nhận xét: Tuy ta nói là lấy đạo hàm nhưng thực chất chỉ là mô phỏng và xấp xỉ đạo hàm bằng các kỹ thuật nhân chập vì ảnh số là tín hiệu rời rạc nên đạo hàm không tồn tại. Ví dụ: Với dx = dy = 1, ta có: f f x 1, y f x, y x f f x, y 1 f x, y y Do đó, mặt nạ nhân chập theo hướng x là A= 1 1 1 và hướng y là B= 1 Chẳng hạn: 0 0 0 0 0 3 3 3 I = 0 3 3 3 0 3 3 3 Ta có, 0 0 0 * 0 3 3 * I  A = 3 0 0 * ; I  B= 0 0 0 * 3 0 0 * 0 0 0 * 45
0 0 0 * I  A + I  B= 3 0 0 * 3 0 0 * 3.2.1.1. Kỹ thuật Prewitt Kỹ thuật sử dụng 2 mặt nạ nhập chập xấp xỉ đạo hàm theo 2 hướng x và y là: -1 0 1 Hx = -1 0 1 -1 0 1 -1 -1 -1 Hy = 0 0 0 1 1 1 Các bước tính toán của kỹ thuật Prewitt + Bước 1: Tính I  Hx và I  Hy + Bước 2: Tính I  Hx + I  Hy Ví dụ: 0 0 0 0 0 0 5 5 5 5 0 0 5 5 5 5 0 0 I = 5 5 5 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -10 -10 * * 0 0 -15 -15 * * I  Hx = 0 0 -10 -10 * * 0 0 -5 -5 * * 46
15 15 10 5 * * 0 0 0 0 * * -15 -15 -10 -5 * * I  Hy = -15 -15 -10 -5 * * 15 15 0 -5 * * 0 0 -15 -15 * * I  Hx + I  Hy = -15 -15 -20 -15 * * -15 -15 -15 -10 * * 3.2.1.2. Kỹ thuật Sobel Tương tự như kỹ thuật Prewitt kỹ thuật Sobel sử dụng 2 mặt nạ nhân chập theo 2 hướng x, y là: -1 0 1 Hx = -2 0 2 -1 0 1 -1 -2 -1 Hy = 0 0 0 1 2 1 Các bước tính toán tương tự Prewitt + Bước 1: Tính I  Hx và I  Hy + Bước 2: Tính I  Hx + I  Hy 3.2.1.3. Kỹ thuật la bàn Kỹ thuật sử dụng 8 mặt nạ nhân chập theo 8 hướng 0 0, 450, 900, 1350, 1800, 2250, 2700, 3150 5 5 -3 5 5 5 H1 = 5 0 -3 H2 = -3 0 -3 -3 -3 -3 -3 -3 -3 -3 5 5 -3 -3 5 H3 = -3 0 5 H4 = -3 0 5 -3 -3 -3 -3 -3 5 -3 -3 -3 -3 -3 -3 47
H5 = -3 0 5 H6 = -3 0 -3 -3 5 5 5 5 5 -3 -3 -3 5 -3 -3 H7 = 5 0 -3 H8 = 5 0 -3 5 5 -3 5 -3 -3 Các bước tính toán thuật toán La bàn + Bước 1: Tính I  Hi ; i = 1,8 8 + Bước 2:  I  H i i 1 3.2.2. Kỹ thuật phát hiện biên Laplace Các phương pháp đánh giá gradient ở trên làm việc khá tốt khi mà độ sáng thay đổi rõ nét. Khi mức xám thay đổi chậm, miền chuyển tiếp trải rộng, phương pháp cho hiệu quả hơn đó là phương pháp sử dụng đạo hàm bậc hai Laplace. Toán tử Laplace được định nghĩa như sau: Ta có:  2 f  2 f 2 f x2 y 2  2 f  f  f (x 1, y) f (x, y) x 2 x x x  f (x 1, y) f (x, y)  f (x, y) f (x 1, y) f (x 1, y) 2 f (x, y) f (x 1, y) Tương tự,  2 f  f  f (x, y 1) f (x, y) 2 y y y y  f (x, y 1) f (x, y)  f (x, y) f (x, y 1) f (x, y 1) 2 f (x, y) f (x, y 1) Vậy: 2 f= f(x+1,y) + f(x,y+1) - 4f(x,y) + f(x-1,y) + f(x,y-1) 48
Dẫn tới: 0 1 0 H 1 4 1 0 1 0 Trong thực tế, người ta thường dùng nhiều kiểu mặt nạ khác nhau để xấp xỉ rời rạc đạo hàm bậc hai Laplace. Dưới đây là ba kiểu mặt nạ thường dùng: 0 1 0 1 1 1 1 2 1 H1 1 4 1 H 2 1 8 1 H3 2 4 2 0 1 0 1 1 1 1 2 1 VD: 0 0 0 0 0 0 5 5 5 5 0 0 I = 5 5 5 5 0 0 5 5 5 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3.2.3. Kỹ thuật Canny Đây là một thuật toán tương đối tốt, có khả năng đưa ra đường biên mảnh, và phát hiện chính xác điểm biên với điểm nhiễu. Thuật toán + Bước 1: Làm trơn ảnh Tính I  H, với: 2 4 5 4 2 4 9 12 9 4 1 H 5 12 15 12 5 115 4 9 12 9 4 2 4 5 4 2 Gọi G là kết quả lọc nhiễu: G= I  H +Bước 2: Tính gradient của ảnh bằng mặt nạ PreWitt, kết quả đặt vào Gx,Gy. 49
Gx = G  Hx, Gy = G  Hy + Bước3: Tính gradient hướng tại mỗi điểm (i,j) của ảnh. Hướng này sẽ được nguyên hóa để nằm trong 8 hướng [0 7], tương đương với 8 lân cận của một điểm ảnh. + Bước 4: Dùng ràng buộc “loại bỏ những điểm không phải là cực đại” để xóa bỏ những điểm không là biên. Xét (i,j),  là gradient hướng tại (i,j). I1, I2 là hai điểm lân cận của (i,j) theo hướng . Theo định nghĩa điểm biên cục bộ thì (i,j) là biên nếu I(i,j) cực đại địa phương theo hướng gradient Nếu I(i,j) > I1 và I(i,j) > I2 thì mới giữ lại I(i,j), ngược lại xóa I(i,j) về điểm ảnh nền. + Bước 5: Phân ngưỡng. Với các điểm được giữ lại, thực hiện lấy ngưỡng gradient biên độ lần cuối để xác định các điểm biên thực sự. 3.3. PHÁT HIỆN BIÊN GIÁN TIẾP 3.3.1 Một số khái niệm cơ bản *Ảnh và điểm ảnh Ảnh số là một mảng số thực 2 chiều (I ij) có kích thước (M N), trong đó mỗi phần tử I ij(i = 1, ,M; j = 1, ,N) biểu thị mức xám của ảnh tại (i,j) tương ứng. Ảnh được gọi là ảnh nhị phân nếu các giá trị Iij chỉ nhận giá trị 0 hoặc 1. Ở đây ta chỉ xét tới ảnh nhị phân vì ảnh bất kỳ có thể đưa về dạng nhị phân bằng kỹ thuật phân ngưỡng. Ta ký hiệu  là tập các điểm vùng (điểm đen) và là tập các điểm nền (điểm trắng). *Các điểm 4 và 8-láng giềng Giả sử (i,j) là một điểm ảnh, các điểm 4-láng giềng là các điểm kề trên, dưới, trái, phải của (i,j): N4(i,j) = {(i’,j’) : |i-i’|+|j-j’| = 1}, và những điểm 8-láng giềng gồm: N8(i,j) = {(i’,j’) : max(|i-i’|,|j-j’|) =1}. Trong Hình 3.1 biểu diễn ma trận 8 láng giềng kề nhau, các điểm P 0, P2, P4, P6 là các 4-láng giềng của điểm P, còn các điểm P0, P1, P2, P3, P4, P5, P6, P7 là các 8-láng giềng của P. 50
P3 P2 P1 P4 P P0 P5 P6 P7 Hình 3.1. Ma trận 8-láng giềng kề nhau *Đối tượng ảnh Hai điểm Ps, Pe E, E   hoặc  được gọi là 8-liên thông (hoặc 4- liên thông) trong E nếu tồn tại tập các điểm được gọi là đường đi (io,jo) (in,jn) sao cho (io,jo)= Ps, (in,jn)= Pe, (ir,jr) E và (ir,jr) là 8-láng giềng (hoặc 4-láng giềng tương ứng) của (ir-1,jr-1) với r = 1,2, ,n Nhận xét: Quan hệ k-liên thông trong E (k=4,8) là một quan hệ phản xạ, đối xứng và bắc cầu. Bởi vậy đó là một quan hệ tương đương. Mỗi lớp tương đương được gọi là một thành phần k-liên thông của ảnh. Về sau ta sẽ gọi mỗi thành phần k-liên thông của ảnh là một đối tượng ảnh. 3.3.2. Chu tuyến của một đối tượng ảnh Định nghĩa 3.1: [Chu tuyến] Chu tuyến của một đối tượng ảnh là dãy các điểm của đối tượng ảnh P1,,Pn sao cho Pi và Pi+1 là các 8-láng giềng của nhau (i=1, ,n-1) và P1 là 8-láng giềng của Pn, i Q không thuộc đối tượng ảnh và Q là 4-láng giềng của Pi (hay nói cách khác i thì Pi là biên 4). Kí hiệu . Tổng các khoảng cách giữa hai điểm kế tiếp của chu tuyến là độ dài của chu tuyến và kí hiệu Len(C) và hướng PiPi+1 là hướng chẵn nếu Pi và Pi+1 là các 4 – láng giềng (trường hợp còn lại thì PiPi+1 là hướng lẻ). Hình 3.2 dưới đây biểu diễn chu tuyến của ảnh, trong đó, P là điểm khởi đầu chu tuyến. P Hình 3.2. Ví dụ về chu tuyến của đối tượng ảnh 51
Định nghĩa 3.2 [Chu tuyến đối ngẫu]  Hai chu tuyến C= và C = được gọi là đối ngẫu của nhau nếu và chỉ nếu i j sao cho: (i) Pi và Qj là 4-láng giềng của nhau. (ii)Các điểm Pi là vùng thì Qj là nền và ngược lại. Định nghĩa 3.3 [Chu tuyến ngoài] Chu tuyến C được gọi là chu tuyến ngoài (Hình 3.3a) nếu và chỉ nếu (i) Chu tuyến đối ngẫu C là chu tuyến của các điểm nền (ii)Độ dài của C nhỏ hơn độ dài C Định nghĩa 3.4 [Chu tuyến trong] Chu tuyến C được gọi là chu tuyến trong (Hình 3.3b) nếu và chỉ nếu: (i) Chu tuyến đối ngẫu C là chu tuyến của các điểm nền (ii)Độ dài của C lớn hơn độ dài C Chu tuyÕn C Chu tuyÕn C Chu tuyÕn C Chu tuyÕn C a) Chu tuyến ngoài b) Chu tuyến trong Hình 3.3. Chu tuyến trong, chu tuyến ngoài Định nghĩa 3.5 [Điểm trong và điểm ngoài chu tuyến] Giả sử C= là chu tuyến của một đối tượng ảnh và P là một điểm ảnh. Khi đó: (i) Nếu nửa đường thẳng xuất phát từ P sẽ cắt chu tuyến C tại số lẻ lần, thì P được gọi là điểm trong chu tuyến C và kí hiệu in(P,C) (ii)Nếu P C và P không phải là điểm trong của C, thì P được gọi là điểm ngoài chu tuyến C và kí hiệu out(P,C). Bổ đề 3.1 [Chu tuyến đối ngẫu] Giả sử E   là một đối tượng ảnh và C= là chu tuyến của  E, C = là chu tuyến đối ngẫu tương ứng. Khi đó: (i) Nếu C là chu tuyến trong thì in(Qi,C) i (i=1, ,m) 52
 (ii)Nếu C là chu tuyến ngoài thì in(Pi,C ) i (i=1, ,n) Bổ đề 3.2 [Phần trong/ngoài của chu tuyến] Giả sử E   là một đối tượng ảnh và C là chu tuyến của E. Khi đó: (i) Nếu C là chu tuyến ngoài thì x E sao cho x C, ta có in(x,C) (ii)Nếu C là chu tuyến trong thì x E sao cho x C, ta có out(x,C) Định lý 3.1 [Tính duy nhất của chu tuyến ngoài] Giả sử E   là một đối tượng ảnh và C E là chu tuyến ngoài của E. Khi đó CE là duy nhất. 3.3.3. Thuật toán dò biên tổng quát Biểu diễn đối tượng ảnh theo chu tuyến thường dựa trên các kỹ thuật dò biên. Có hai kỹ thuật dò biên cơ bản. Kỹ thuật thứ nhất xét ảnh biên thu được từ ảnh vùng sau một lần duyệt như một đồ thị, sau đó áp dụng các thuật toán duyệt cạnh đồ thị. Kỹ thuật thứ hai dựa trên ảnh vùng, kết hợp đồng thời quá trình dò biên và tách biên. Ở đây ta quan tâm cách tiếp cận thứ hai. Trước hết, giả sử ảnh được xét chỉ bao gồm một vùng ảnh 8-liên thông , được bao bọc bởi một vành đai các điểm nền. Dễ thấy  là một vùng 4- liên thông chỉ là một trường riêng của trường hợp trên. Về cơ bản, các thuật toán dò biên trên một vùng đều bao gồm các bước sau: Xác định điểm biên xuất phát Dự báo và xác định điểm biên tiếp theo Lặp bước 2 cho đến khi gặp điểm xuất phát Do xuất phát từ những tiêu chuẩn và định nghĩa khác nhau về điểm biên, và quan hệ liên thông, các thuật toán dò biên cho ta các đường biên mang các sắc thái rất khác nhau. Kết quả tác động của toán tử dò biên lên một điểm biên ri là điểm biên ri+1 (8-láng giềng của ri). Thông thường các toán tử này được xây dựng như một hàm đại số Boolean trên các 8-láng giềng của r i. Mỗi cách xây dựng các toán tử đều phụ thuộc vào định nghĩa quan hệ liên thông và điểm biên. Do đó sẽ gây khó khăn cho việc khảo sát các tính chất của đường biên. Ngoài ra, vì mỗi bước dò biên đều phải kiểm tra tất cả các 8-láng giềng của mỗi điểm nên thuật toán thường kém hiệu quả. Để khắc phục các hạn chế trên, thay vì sử dụng một điểm biên ta sử dụng cặp điểm biên (một thuộc , một thuộc  ), các cặp điểm này tạo nên tập nền vùng, kí hiệu là NV và phân tích toán tử dò biên thành 2 bước: Xác định cặp điểm nền vùng tiếp theo. 53
Lựa chọn điểm biên Trong đó bước thứ nhất thực hiện chức năng của một ánh xạ trên tập NV lên NV và bước thứ hai thực hiện chức năng chọn điểm biên. Thuật toán dò biên tổng quát Bước 1: Xác định cặp nền-vùng xuất phát Bước 2: Xác định cặp nền-vùng tiếp theo Bước 3: Lựa chọn điểm biên vùng Bước 4: Nếu gặp lại cặp xuất phát thì dừng, nếu không quay lại bước 2. Việc xác định cặp nền-vùng xuất phát được thực hiện bằng cách duyệt ảnh lần lượt từ trên xuống dưới và từ trái qua phải rồi kiểm tra điều kiện lựa chọn cặp nền-vùng. Do việc chọn điểm biên chỉ mang tính chất quy ước, nên ta gọi ánh xạ xác định cặp nền-vùng tiếp theo là toán tử dò biên. Định nghĩa 3.6 [Toán tử dò biên] Giả sử T là một ánh xạ như sau: T: NV NV (b,r) (b’,r’) Gọi T là một toán tử dò biên cơ sở nếu nó thoả mãn điều kiện: b’,r’ là các 8-láng giềng của r. Giả sử (b,r) NV; gọi K(b,r) là hàm chọn điểm biên. Biên của một dạng  có thể định nghĩa theo một trong ba cách: Tập những điểm thuộc  có mặt trên NV, tức là K(b,r)= r Tập những điểm thuộc  có trên NV, tức là K(b,r)= b Tập những điểm ảo nằm giữa cặp nền-vùng, tức là K(b,r) là những điểm nằm giữa hai điểm b và r. Cách định nghĩa thứ ba tương ứng mỗi cặp nền-vùng với một điểm biên. Còn đối với cách định nghĩa thứ nhất và thứ hai một số cặp nền- vùng có thể có chung một điểm biên. Bởi vậy, quá trình chọn điểm biên được thực hiện như sau: i:= 1; (bi,ri):= (bo,ro); While K(bi,ri)<>K(bn,rn) and i 8 do Begin (bi+1,ri+1)= T(bi,ri); i:= i+1; End; 54
Điều kiện dừng Cặp nền-vùng thứ n trùng với cặp nền vùng xuất phát: (bn,rn)= (bo,ro) * Xác định cặp nền – vùng xuất phát Cặp nền vùng xuất phát được xác định bằng cách duyệt ảnh lần lượt từ trên xuống dưới và từ trái sang phải điểm đem đầu tiên gặp được cùng với điểm trắng trước đó (theo hướng 4) để tạo nên cặp nền vùng xuất phát. * Xác định cặp nền vùng tiếp theo Đầu vào: pt, dir Ví dụ: (3, 2) 4 Point orient ]= (1,0);(1;-1);(0;-1);(-1;-1);(-1;0);(-1,1);(0,1);(1,1); //Hàm tìm hướng có điểm đen gần nhất BYTE GextNextDir(POINT pt, BYTE dir) { BYTE pdir= (dir + 7)%8; do{ if(getpixel(pt. x+orient pdir. x,pt.y+orient pdir. y))==BLACK) return pdir; pdir = (pdir + 7) %8; }while(pdir ! = dir); return. ERR; //Điểm cô lập } //Gán giá trị cho bước tiếp theo pdir = GetNextDir(pt, dir); if(pdir==ERR) //Kiểm tra có là điểm cô lập không? return. ERR; //Điểm cô lập pt. x = pt. x + orient pdir. x; pt. y = pt. y + orient pdir. y ; 55
Để tính giá trị cho hướng tiếp theo ta lập bảng dựa trên giá trị pdir đã tính được trước đó theo các khả năng có thể xảy ra: pdir Điểm trắng trước đó Trắng so với đen mới 0 1 2 1 2 4 2 3 4 3 4 6 4 5 6 5 6 0 6 7 0 7 0 2 Do đó công thức để tính hướng tiếp theo sẽ là : dir= ((pdir+3)/ 2 * 2)%8 ; 3.4. PHÁT HIỆN BIÊN DỰA VÀO TRUNG BÌNH CỤC BỘ 3.4.1. Biên và độ biến đổi về mức xám Như đã trình bày ở trên, trong thực tế người ta thường dùng hai phương pháp pháp hiện biên cơ bản là: Phát hiện biên trực tiếp và gián tiếp. Phần này đề cập đến kỹ thuật mới dựa vào trung bình cục bộ trên cơ sở đánh giá độ chênh lệch về giá trị mức xám của điểm ảnh so với các điểm lân cận do đó kết hợp được ưu điểm của cả hai khuynh hướng trực tiếp và gián tiếp. Đối với các ảnh màu theo mô hình nào đó đều có thể chuyển sang mô hình gồm 3 thành phần mầu R, G, B. Sau đó dễ dàng chuyển các ảnh màu sang dạng ảnh đa cấp xám. Chẳng hạn: Gray = ( R + G + B ) / 3 Việc xử lý, thao tác trên các ảnh xám có một ưu điểm là dễ xử lý hơn các ảnh màu mà vẫn giữ được các đặc tính của ảnh. Các ảnh trắng đen tuy dễ xử lý nhất nhưng sẽ bị mất nhiều chi tiết sau khi chuyển đổi. Một cách lý tưởng đồ thị biến thiên mức xám của điểm ảnh khi qua biên phải có dạng: Mδc xám 0 x 56
Trong thực tế dạng đồ thị này chỉ gặp trong các ảnh trắng đen (ảnh xám có hai màu), còn với các ảnh thực thì đồ thị của nó có dạng: Mδc xám 0 x Khó khăn cho việc phân tích các ảnh thực là ở chỗ do sự biến thiên về mức xám của điểm ảnh không phải chỉ được thể hiện theo một hướng duy nhất mà phải xét theo cả tám hướng của các điểm ảnh láng giềng, tại các vùng biên và lân cận biên sự biến thiên mức xám của các điểm ảnh thường không đột ngột mà trải qua một khoảng biến thiên không đều nhưng có tốc độ biến thiên nhanh. Chúng ta có thể xác định được các đường biên như thế này bằng kỹ thuật Laplace nhưng như ở trên đã nói kỹ thuật này rất nhạy cảm với nhiễu mà nhiễu hầu như lại là vấn đề mà ở trong bức ảnh nào cũng có. Ngoài ra, trong thực tế khi dò biên cho các ảnh xám tùy theo mục đích xử lý sau này mà người ta có thể muốn lấy biên của tất cả các đối tượng trong ảnh hoặc chỉ một số đối tượng chính trong ảnh. Các kỹ thuật đạo hàm do sử dụng các mặt nạ là các ma trận nhân chập nên khó điều chỉnh độ chi tiết của ảnh biên thu được. Muốn làm được điều này lại phải tính toán lại các giá trị của các phần tử trong ma trận theo các công thức nhất định, rất phức tạp và tốn kém. Không những thế ảnh thu được sau khi lọc không làm mất đi được tất cả các điểm không thuộc đường biên mà chỉ làm nổi lên các điểm nằm trên biên và muốn nhận dạng được các đối tượng thì ta còn phải xử lý thêm một vài bước nữa thì mới thu được ảnh biên thực sự. Có thể nhận thấy là các thuật toán dò biên truyền thống mà chúng ta hay dùng vẫn chưa đạt được sự hoàn thiện như mong muốn [3,8]. 3.4.2. Phát hiện biên dựa vào trung bình cục bộ Ý tưởng chính của thuật toán được đề xuất là: Xác định tất cả các điểm nằm trên biên không theo hướng tìm kiếm và sử dụng các ma trận lọc, thông qua việc so sánh độ chênh lệch về mức xám của nó so với mức xám chung của các điểm ảnh lân cận (mức xám nền). Trước hết giá trị xám trung bình của các điểm ảnh nằm trong phạm vi của ma trận 3×3 hoặc 5×5 có tâm là điểm ảnh đang xét sẽ được tính toán. Nếu như độ chênh lệch mức xám giữa điểm đang xét với giá trị xám trung bình thỏa mãn lớn hơn một mức tối thiểu δ1 nào đó (PTB+ δ1< P) thì chúng ta sẽ coi nó là điểm biên và ghi nhận lại, còn các điểm không thỏa mãn điều kiện trên sẽ được coi là điểm nền. 57
δ 1 N=5 a) Ma trận điểm ảnh trước khi lọc b) Ma trận điểm ảnh sau khi lọc Hình 3.4. Ma trận điểm ảnh trước và sau lọc Thuật toán có thể được mô tả như sau: for (i=0; i 9*GetPoint(pOrgImg,i,j)+δ1) SetPoint(pBdImg,i,j,BLACK); } Trong đó: biWidth, biHeight: là chiều rộng và chiều cao của ảnh tính theo đơn vị Pixel. pOrgImg, pBdImg: lần lượt là các con trỏ trỏ đến các vùng dữ liệu của ảnh gốc và ảnh biên. tt_GrayScale: là tổng giá trị độ xám của các điểm ảnh thuộc ma trận 3×3 có tâm là điểm ảnh đang xét. δ 1: là độ chênh lệch mức xám của điểm ảnh đang xét so với giá trị xám trung bình của ma trận. SetPoint() và GetPoint(): là các hàm đọc, ghi giá trị điểm ảnh. Chúng ta có thể so sánh được hiệu quả của thuật toán phát hiện biên này so với các thuật toán phát hiện biên truyền thống thông qua các hình minh họa dưới đây. Hình 3.5a là ảnh gốc, Hình 3.5b là ảnh biên qua lọc Sobel Hx, Hình 3.5c là ảnh biên qua lọc Sobel Hy, Hình 3.5d là ảnh biên qua lọc Kirsh, Hình 3.5e là ảnh biên qua lọc Laplace. Hình 3.6 là các ảnh biên thu được khi sử dụng thuật toán phát hiện biên đề xuất dựa vào trung 58
bình cục bộ với giá trị δ1 khác nhau. Hình 3.6a là ảnh biên thu được với δ1= 25, Hình 3.6b là ảnh biên thu được với δ1= 250. a) Ảnh gốc b) Ảnh qua lọc Sobel Hx c) Ảnh qua lọc Sobel Hy d) Ảnh qua lọc Kirsh e) Ảnh qua lọc Laplace Hình 3.5. Các ảnh biên theo các thuật toán phát hiện biên truyền thống a) Ảnh biên thu được với δ1= 25 b) Ảnh biên thu được với δ1= 250 Hình 3.6. Các ảnh biên kết quả thu được theo thuật toán đề xuất *Nhận xét: Chúng ta có nhận xét là ảnh gốc sử dụng trong chương trình có mầu nền khá tối và có rất nhiều nhiễu. Các bộ lọc sử dụng trong minh họa trên đều mắc phải vấn đề này. Thuật toán dò biên sử dụng trong chương trình tuy đã hạn chế được nhiều nhiễu so với việc sử dụng các bộ lọc và làm nổi rõ các đường biên nhưng vẫn không loại bỏ được hầu hết các nhiễu. Khi áp dụng thuật toán trên chúng ta vẫn có thể làm giảm bớt nhiễu đi nhiều hơn nữa bằng cách tăng giá trị của hệ số delta lên. Nhưng khi đó các đường biên thu được cũng bị đứt đoạn và mờ đi nhiều. Thuật toán có độ phức tạp tỷ lệ với kích thước ảnh và kích thước cửa sổ. Với độ phức tạp của thuật toán là O(n2) nên nó thực hiện việc tìm biên khá nhanh, ảnh biên thu được chỉ gồm các điểm ảnh và điểm biên nên dễ 59
xử lý, bản thân thuật toán này cũng ít chịu ảnh hưởng của nhiễu hơn là kỹ thuật Sobel mặc dù nó có khả năng phát hiện khá tốt các vùng biên nhiễu. Nhưng cũng giống các phương pháp phát hiện biên trực tiếp khác là nó cho kết quả đường biên có độ dày không đều. 3.5. PHÁT HIỆN BIÊN DỰA VÀO CÁC PHÉP TOÁN HÌNH THÁI 3.5.1. Xấp xỉ trên và xấp xỉ dưới đối tượng ảnh Biên là vấn đề quan trọng trong xử lý ảnh và nhận dạng, vì các đặc điểm trích chọn trong quá trình nhận dạng chủ yếu dựa vào biên. Trong thực tế người ta thường dùng hai phương pháp pháp hiện biên cơ bản là: Phát hiện biên trực tiếp và gián tiếp. Phần này đề cập đến một tiếp cận mới trong phát hiện biên dựa vào các phép toán hình thái thông qua các kỹ thuật xấp xỉ trên và xấp xỉ dưới đối tượng. Trong [2,7] cũng đã đề cập đến kỹ thuật phát hiện biên dựa vào phép toán hình thái. Nhưng các kỹ thuật phát hiện biên trực tiếp, gián tiếp và dựa vào các phép toán hình thái kể trên đều xuất phát từ quan điểm biên của đối tượng là một tập hợp con của đối tượng. Trong thực tế chúng ta thường hiểu đường biên là khu vực ranh giới bao gồm cả hai phần thuộc đối tượng và không thuộc đối tượng. Ở phần dưới đây, chúng tôi đề xuất một kỹ thuật phát hiện biên dựa vào phép toán hình thái theo quan niệm này, xuất phát từ cơ sở định lý 2.1 đã được chứng minh ở trên. Biên (hay đường biên) có thể hiểu đơn giản là các đường bao của các đối tượng trong ảnh chính là ranh giới giữa đối tượng và nền. Việc xem ranh giới là phần được tạo lập bởi các điểm thuộc đối tượng và thuộc nền cho phép ta xác định biên dựa trên các phép toán hình thái [2,7]. Theo định lý 2.1 ta có: (XB)B  X B Như vậy, tập CLOSE(X,B) = (XB)B có thể được xem như là xấp xỉ trên của tập X theo mẫu B (Hình 3.7). 60
CLOSE(X,B)= (XB)B Xấp xỉ trên của X (chứa X) X B = CLOSE(X,B)\ OPEN(X,B) Xấp xỉ biên của X theo mẫu B OPEN(X,B)= ((XB)B) Xấp xỉ dưới của X (thuộc X) Hình 3.7. Xấp xỉ trên và dưới theo mẫu B của X Cũng theo định lý 2.1 ta có, (XB)B  X B Do vậy, tập OPEN(X,B) = (XB)B có thể được xem như là xấp xỉ dưới của tập X theo mẫu B. Từ đó, tập CLOSE(X,B)\ OPEN(X,B) có thể được xem như là xấp xỉ biên của tập X theo mẫu và quá trình xấp xỉ biên của X theo mẫu B kí hiệu là X B. Để tăng độ chính xác, người ta thường xem B là dãy các phần tử cấu trúc. B = {Bi, 1 i n } Và xấp xỉ biên của X theo tập cấu trúc B được xác định: n XB  XBi i 1 3.5.1. Thuật toán phát hiện biên dựa vào phép toán hình thái Vào : Ảnh X và dãy mẫu B= {Bi, 1 i n }; Ra : Biên của đối tượng theo mẫu B Phương pháp: Bước 1: Tính X  Bi i=1,n n Bước 2: Tính  X Bi i 1 Trong Hình 3.8a dưới đây là ảnh gốc với 256 mức xám, Hình 3.8b là ảnh biên thu được qua phát hiện biên bằng Sobel, Hình 3.8c là ảnh biên thu được qua phát hiện biên bằng Laplace. Hình 3.8d là ảnh biên kết quả 61
thực hiện bởi thuật toán phát hiện biên bằng các phép toán hình thái với ngưỡng tách  = 128 và các mẫu tách biên Bi là: = = = = B1  B2  B3  B4  a) Ảnh gốc đa cấp xám b) Ảnh biên thu được qua Sobel c) Ảnh biên thu được qua Laplace d) Ảnh biên kết quả dựa vào phép toán hình thái Hình 3.8. Phát hiện biên bởi thuật toán dựa vào phép toán hình thái 62
Chương 4: XƯƠNG VÀ CÁC KỸ THUẬT TÌM XƯƠNG 4.1. GIỚI THIỆU Xương được coi như hình dạng cơ bản của một đối tượng, với số ít các điểm ảnh cơ bản. Ta có thể lấy được các thông tin về hình dạng nguyên bản của một đối tượng thông qua xương. Một định nghĩa xúc tích về xương dựa trên tính continuum (tương tự như hiện tượng cháy đồng cỏ) được đưa ra bởi Blum (1976) như sau: Giả thiết rằng đối tượng là đồng nhất được phủ bởi cỏ khô và sau đó dựng lên một vòng biên lửa. Xương được định nghĩa như nơi gặp của các vệt lửa và tại đó chúng được dập tắt. a) Ảnh gốc b) Ảnh xương Hình 4.1. Ví dụ về ảnh và xương Kỹ thuật tìm xương luôn là chủ đề nghiên cứu trong xử lý ảnh những năm gần đây. Mặc dù có những nỗ lực cho việc phát triển các thuật toán tìm xương, nhưng các phương pháp được đưa ra đều bị mất mát thông tin. Có thể chia thành hai loại thuật toán tìm xương cơ bản: Các thuật toán tìm xương dựa trên làm mảnh Các thuật toán tìm xương không dựa trên làm mảnh 4.2. TÌM XƯƠNG DỰA TRÊN LÀM MẢNH 4.2.1. Sơ lược về thuật toán làm mảnh Thuật toán làm mảnh ảnh số nhị phân là một trong các thuật toán quan trọng trong xử lý ảnh và nhận dạng. Xương chứa những thông tin bất biến về cấu trúc của ảnh, giúp cho quá trình nhận dạng hoặc vectơ hoá sau này. 63
Thuật toán làm mảnh là quá trình lặp duyệt và kiểm tra tất cả các điểm thuộc đối tượng. Trong mỗi lần lặp tất cả các điểm của đối tượng sẽ được kiểm tra: nếu như chúng thoả mãn điều kiện xoá nào đó tuỳ thuộc vào mỗi thuật toán thì nó sẽ bị xoá đi. Quá trình cứ lặp lại cho đến khi không còn điểm biên nào được xoá. Đối tượng được bóc dần lớp biên cho đến khi nào bị thu mảnh lại chỉ còn các điểm biên. Các thuật toán làm mảnh được phân loại dựa trên phương pháp xử lý các điểm là thuật toán làm mảnh song song và thuật toán làm mảnh tuần tự. Thuật toán làm mảnh song song, là thuật toán mà trong đó các điểm được xử lý theo phương pháp song song, tức là được xử lý cùng một lúc. Giá trị của mỗi điểm sau một lần lặp chỉ phụ thuộc vào giá trị của các láng giềng bên cạnh (thường là 8-láng giềng) mà giá trị của các điểm này đã được xác định trong lần lặp trước đó. Trong máy có nhiều bộ vi xử lý mỗi vi xử lý sẽ xử lý một vùng của đối tượng, nó có quyền đọc từ các điểm ở vùng khác nhưng chỉ được ghi trên vùng của nó xử lý. Trong thuật toán làm mảnh tuần tự các điểm thuộc đối tượng sẽ được kiểm tra theo một thứ tự nào đó (chẳng hạn các điểm được xét từ trái qua phải, từ trên xuống dưới). Giá trị của điểm sau mỗi lần lặp không những phụ thuộc vào giá trị của các láng giềng bên cạnh mà còn phụ thuộc vào các điểm đã được xét trước đó trong chính lần lặp đang xét. Chất lượng của thuật toán làm mảnh được đánh giá theo các tiêu chuẩn được liệt kê dưới đây nhưng không nhất thiết phải thoả mãn đồng thời tất cả các tiêu chuẩn. Bảo toàn tính liên thông của đối tượng và phần bù của đối tượng Sự tương hợp giữa xương và cấu trúc của ảnh đối tượng Bảo toàn các thành phần liên thông Bảo toàn các điểm cụt Xương chỉ gồm các điểm biên, càng mảnh càng tốt Bền vững đối với nhiễu Xương cho phép khôi phục ảnh ban đầu của đối tượng Xương thu được ở chính giữa đường nét của đối tượng được làm mảnh Xương nhận được bất biến với phép quay. 64
4.2.2. Một số thuật toán làm mảnh Trong phần này điểm qua một số đặc điểm, ưu và khuyết điểm của các thuật toán đã được nghiên cứu. 1o. Thuật toán làm mảnh cổ điển là thuật toán song song, tạo ra xương 8 liên thông, tuy nhiên nó rất chậm, gây đứt nét, xoá hoàn toàn một số cấu hình nhỏ. 2o. Thuật toán làm mảnh của Toumazet bảo toàn tất cả các điểm cụt không gây đứt nét đối tượng. Tuy nhiên, thuật toán có nhược điểm là rất chậm, rất nhạy cảm với nhiễu, xương chỉ là 4-liên thông và không làm mảnh được với một số cấu hình phức tạp 3o. Thuật toán làm mảnh của Y.Xia dựa trên đường biên của đối tượng, có thể cài đặt theo cả phương pháp song song và tuần tự. Tốc độ của thuật toán rất nhanh. Nó có nhược điểm là gây đứt nét, xương tạo ra là xương giả (có độ dày là 2 phần tử ảnh). 4o. Thuật toán làm mảnh của N.J.Naccache và R.Shinghal. Thuật toán có ưu điểm là nhanh, xương tạo ra có khả năng khôi phục ảnh ban đầu của đối tượng. Nhược điểm chính của thuật toán là rất nhạy với nhiễu, xương nhận được phản ánh cấu trúc của đối tượng thấp. 5o. Thuật toán làm mảnh của H.E.Lu P.S.P Wang tương đối nhanh, giữ được tính liên thông của ảnh, nhưng lại có nhược điểm là xương tạo ra là xương 4-liên thông và xoá mất một số cấu hình nhỏ. 6o. Thuật toán làm mảnh của P.S.P Wang và Y.Y.Zhang dựa trên đường biên của đối tượng, có thể cài đặt theo phương pháp song song hoặc tuần tự, xương là 8-liên thông, ít chịu ảnh hưởng của nhiễu. Nhược điểm chính của thuật toán là tốc độ chậm. 7o. Thuật toán làm mảnh song song thuần tuý nhanh nhất trong các thuật toán trên, bảo toàn tính liên thông, ít chịu ảnh hưởng của nhiễu. Nhược điểm là xoá hoàn toàn một số cấu hình nhỏ, xương tạo ra là xương 4-liên thông. 4.3. TÌM XƯƠNG KHÔNG DỰA TRÊN LÀM MẢNH Để tách được xương của đối tượng có thể sử dụng đường biên của đối tượng. Với điểm p bất kỳ trên đối tượng, ta bao nó bởi một đường biên. Nếu như có nhiều điểm biên có cùng khoảng cách ngắn nhất tới p thì p nằm trên trục trung vị. Tập tất cả các điểm như vậy lập thành trục trung vị hay xương của đối tượng. Việc xác định xương được tiến hành thông qua hai bước: 65
Bước thứ nhất, tính khoảng cách từ mỗi điểm ảnh của đối tượng đến điểm biên gần nhất. Như vậy cần phải tính toán khoảng cách tới tất cả các điểm biên của ảnh. Bước thứ hai, khoảng cách ảnh đã được tính toán và các điểm ảnh có giá trị lớn nhất được xem là nằm trên xương của đối tượng. 4.3.1. Khái quát về lược đồ Voronoi Lược đồ Voronoi là một công cụ hiệu quả trong hình học tính toán. Cho hai điểm Pi, Pj là hai phần tử của tập  gồm n điểm trong mặt phẳng. Tập các điểm trong mặt phẳng gần P i hơn Pj là nửa mặt phẳng H(Pi, Pj) chứa điểm P i và bị giới hạn bởi đường trung trực của đoạn thẳng P iPj. Do đó, tập các điểm gần P i hơn bất kỳ điểm P j nào có thể thu được bằng cách giao n-1 các nửa mặt phẳng H(Pi, Pj): V(Pi) =  H(Pi, Pj) i j (i= 1, ,n) (4.1) Định nghĩa 4.1 [Đa giác/Sơ đồ Voronoi] Sơ đồ Voronoi của  là hợp của tất cả các V(Pi) Vor() =  V(Pi) Pi  (là một đa giác) (4.2) Định nghĩa 4.2 [Đa giác Voronoi tổng quát] Cho tập các điểm , đa giác Voronoi của tập con U của  được định nghĩa như sau: V(U) = P v U, w  \ U : d(P,v) < d(P,w) =  V(Pi) Pi U (4.3) 4.3.2. Trục trung vị Voronoi rời rạc Định nghĩa 4.3 [Bản đồ khoảng cách - Distance Map] Cho đối tượng S, đối với mỗi (x, y) S, ta tính giá trị khoảng cách map(x, y) với hàm khoảng cách d(.,.) như sau: (x, y) S: map(x, y) = min d[(x, y), (xi, yi)] (4.4) i trong đó (xi, yi) B(S) - tập các điểm biên của S Tập tất cả các map(x, y), kí hiệu là DM(S), được gọi là bản đồ khoảng cách của S. Chú ý: Nếu hàm khoảng cách d(.,.) là khoảng cách Euclide, thì phương trình (4.4) chính là khoảng cách ngắn nhất từ một điểm bên trong đối tượng tới biên. Do đó, bản đồ khoảng cách được gọi là bản đồ khoảng cách Euclide EDM(S) của S. Định nghĩa trên được dùng cho cả hình rời rạc lẫn liên tục. 66
Định nghĩa 4.4 [Tập các điểm biên sinh] Cho map(x, y) là khoảng cách ngắn nhất từ (x, y) đến biên (theo định nghĩa 4.3). Ta định nghĩa: map-1(x, y) = p p B(S), d(p, (x, y)):=map(x, y) Khi đó tập các điểm biên sinh ^B(S) được định nghĩa bởi: ^B(S) = map-1(x, y), (x, y) S (4.5) Do S có thể chứa các đường biên rời nhau, nên ^B(S) bao gồm nhiều tập con, mỗi tập mô tả một đường biên phân biệt: ^B(S)= B1(S), BN(S) (4.6) Định nghĩa 4.5 [Trục trung vị Voronoi rời rạc (DVMA)] Trục trung vị Voronoi rời rạc được định nghĩa là kết quả của sơ đồ Voronoi bậc nhất rời rạc của tập các điểm biên sinh giao với hình sinh S : DVMA(^B(S)) = Vor(^B(S))  S (4.7) 4.3.3. Xương Voronoi rời rạc Định nghĩa 4.6 [Xương Voronoi rời rạc - DiscreteVoronoi Skeleton] Xương Voronoi rời rạc theo ngưỡng T, kí hiệu là Ske DVMA(^B(S),T) (hoặc Ske(^B(S),T)) là một tập con của trục trung vị Voronoi: SkeDVMA(^B(S),T)= {(x,y)| (x,y) DVMA(^B(S)), (x,y) > T} (4.8) : là hàm hiệu chỉnh. Dễ thấy nếu ngưỡng T càng lớn thì càng thì số lượng điểm tham gia trong xương Vonoroi càng ít (Hình 4.2). a) b) c) d) Hình 4.2. Xương Voronoi rời rạc ảnh hưởng của các hàm hiệu chỉnh khác nhau. (a) Ảnh nhị phân. (b) Sơ đồ Voronoi. (c) Hiệu chỉnh bởi hàm Potential, T=9.0. (d) Hiệu chỉnh bởi hàm Potential, T=18.0 67
4.3.4. Thuật toán tìm xương Trong mục này sẽ trình bày ý tưởng cơ bản của thuật toán tìm xương và mô tả bằng ngôn ngữ tựa Pascal. Tăng trưởng: Việc tính toán sơ đồ Voronoi được bắt đầu từ một điểm sinh trong mặt phẳng. Sau đó điểm sinh thứ hai được thêm vào và quá trình tính toán tiếp tục với đa giác Voronoi đã tìm được với điểm vừa được thêm vào đó. Cứ như thế, quá trình tính toán sơ đồ Voronoi được thực hiện cho đến khi không còn điểm sinh nào được thêm vào. Nhược điểm của chiến lược này là mỗi khi một điểm mới được thêm vào, nó có thể gây ra sự phân vùng toàn bộ các đa giác Voronoi đã được tính. Chia để trị: Tập các điểm biên đầu tiên được chia thành hai tập điểm có kích cỡ bằng nhau. Sau đó thuật toán tính toán sơ đồ Voronoi cho cả hai tập con điểm biên đó. Cuối cùng, người ta thực hiện việc ghép cả hai sơ đồ Voronoi trên để thu được kết quả mong muốn. Tuy nhiên, việc chia tập các điểm biên thành hai phần không phải được thực hiện một lần, mà được lặp lại nhiều lần cho đến khi việc tính toán sơ đồ Voronoi trở nên đơn giản. Vì thế, việc tính sơ đồ Voronoi trở thành vấn đề làm thế nào để trộn hai sơ đồ Voronoi lại với nhau. Thuật toán sẽ trình bày ở đây là sự kết hợp của hai ý tưởng ở trên. Tuy nhiên, nó sẽ mang nhiều dáng dấp của thuật toán chia để trị. Hình 4.3 minh hoạ ý tưởng của thuật toán này. Mười một điểm biên được chia thành hai phần (bên trái: 1- 6, bên phải: 7-11) bởi đường gấp khúc , và hai sơ đồ Voronoi tương ứng Vor(S L) và Vor(SR). Để thu được sơ đồ Vornonoi Vor(SL  SR), ta thực hiện việc trộn hai sơ đồ trên và xác định lại một số đa giác sẽ bị sửa đổi do ảnh hưởng của các điểm bên cạnh thuộc sơ đồ kia. Mỗi phần tử của  sẽ là một bộ phận của đường trung trực nối hai điểm mà một điểm thuộc Vor(S L) và một thuộc Vor(S R). Trước khi xây dựng , ta tìm ra phần tử đầu và cuối của nó. Nhìn vào hình trên, ta nhận thấy rằng cạnh  1 và 5 là các tia. Dễ nhận thấy rằng việc tìm ra các cạnh đầu và cuối của  trở thành việc tìm cạnh vào t và cạnh ra t.  3 1 t 7 CH(SL) 1 6 11 CH(SR 4 ) 9 2 10 t 5  8 5 Hình 4.3. Minh hoạ thuật toán trộn hai sơ đồ Voronoi 68
Sau khi đã tìm được t và t, các điểm cuối của t được sử dụng để xây dựng phần tử đầu tiên của  ( 1 trong hình trên). Sau đó thuật toán tìm điểm giao của  với Vor(S L) và Vor(SR). Trong ví dụ trên,  đầu tiên giao với V(3). Kể từ đây, các điểm nằm trên phần kéo dài  sẽ gần điểm 6 hơn điểm 3. Do đó, phần tử tiếp theo 2 của  sẽ thuộc vào đường trung trực của điểm 6 và điểm 7. Sau đó điểm giao tiếp theo của  sẽ thuộc và Vor(S L);  bây giờ sẽ đi vào V(9) và  2 sẽ được thay thế bởi  3. Quá trình này sẽ kết thúc khi  gặp phần tử cuối 5. Trên đây chỉ là minh hoạ cho thuật trộn hai sơ đồ Voronoi trong chiến lược chia để trị. Tuy nhiên, trong thuật toán sẽ trình bày ở đây thì sự thực hiện có khác một chút. Tập các điểm ảnh không phải được đưa vào ngay từ đầu mà sẽ được quét vào từng dòng một. Giả sử tại bước thứ i, ta đã thu được một sơ đồ Voronoi gồm i-1 hàng các điểm sinh Vor(Si-1). Tiếp theo, ta quét lấy một hàng Li các điểm ảnh từ tập các điểm biên còn lại. Thực hiện việc tính sơ đồ Voronoi Vor(Li) cho hàng này, sau đó trộn Vor(S i-1) với Vor(Li). Kết quả ta sẽ được một sơ đồ mới, và lại thực hiện việc quét hàng Li+1 các điểm sinh còn lại v.v Quá trình này sẽ kết thúc khi không còn điểm biên nào để thêm vào sơ đồ Voronoi. Do Vor(Li) sẽ có dạng răng lược (nếu Li có k điểm thì Vor(L i) sẽ gồm k-1 đường thẳng đứng), nên việc trộn Vor(Si-1) với Vor(Li) có phần đơn giản hơn. v5 p8 p9 v2 p10 v p6 v 1  t 4 v3 p7 t p5 p4 v6 p1 p2 Các điδm thuδc p3 Si-1 Các điδm Hìnhthuδc 4.4. Minh Li hoạ thuật toán thêm một điểm biên vào sơ đồ Voronoi Giải thuật trên có thể được mô tả bằng ngôn ngữ tựa Pascal như sau: Procedure VORONOI (*Si: Tập các điểm của i dòng quét đầu tiên, 0 <= i <=iMAX, Vor(Si) sơ đồ Vorronoi của Si *) 69
Begin i:=0; Si:=rỗng; While (i<imax  Si  straight_line) do Begin (*Khởi tạo sơ đồ Voronoi cho đến khi nó chứa ít nhất một đỉnh*) increment i; GetScanLine Li; Vor(Si) = VoroPreScan(Vor(Si-1, Li)); End While (i < imax) do Begin Increment i; GetScanLine Li; Vor(Li) := các đường trung trực sinh bởi các điểm sinh thuộc Li Vor(Si) := VoroLink(Vor(Si-1), Vor(Li)); End End. Giả sử xét trên hệ toạ độ thực. Ảnh vào được quét từ dưới lên. Toạ độ y (biến i) tương ứng với từng dòng quét được tăng dần theo từng dòng. Trong thủ tục trên, hàm quan trọng nhất là hàm VoroLink, hàm này thực hiện việc trộn sơ đồ Voronoi của L i-1 dòng đã được quét trước đó với sơ đồ Voronoi của dòng hiện tại thứ i. Trong vòng lặp trên, hàm VoroPreScan là một biến thể của hàm VoroLink, có nhiệm vụ khởi tạo sơ đồ Voronoi và thoát khỏi vòng lặp ngay khi nó thành lập được sơ đồ Voronoi chứa ít nhất một đỉnh. Hàm VoroLink thực hiện việc trộn hai sơ đồ Voronoi Vor(S i-1) và Vor(Li) với nhau để thành Vor(Si). 70
Chương 5: CÁC KỸ THUẬT HẬU XỬ LÝ 5.1. RÚT GỌN SỐ LƯỢNG ĐIỂM BIỂU DIỄN 5.1.1. Giới thiệu Rút gọn số lượng điểm biểu diễn là kỹ thuật thuộc phần hậu xử lý. Kết quả của phần dò biên hay trích xương thu được 1 dãy các điểm liên tiếp. Vấn đề đặt ra là hiệu có thể bá bớt các điểm thu được để giảm thiểu không quan lưu trữ và thuận tiện cho việc đối sách hay không. Bài toán: Cho đường cong gồm n điểm trong mặt phẳng (x1, y1), (x2, y2) (xn,yn). Hãy bỏ bớt 1 số điểm thuộc đường cong sao cho đường cong mới nhận được là (Xi1; Yi1), (Xi2; Yi2) (Xim; Yim) “gần giống” với đường cong ban đầu. * Một số độ đo “gần giống” + Chiều dài (chiều rộng) của hình chữ nhật nhá nhất chứa đường cong + Khoảng cách lớn nhất từ đường cong đến đoạn thẳng nối 2 đầu mót của đường cong + Tỷ lệ giữa chiều dài và chiều rộng của hình chữ nhật nhá nhất chứa đường con + Số lần đường cong cắt đoạn thẳng nối 2 đầu mót 5.1.2. Thuật toán Douglas Peucker 5.1.2.1. Ý tưởng h >   Hình 5.1. Đơn giản hóa đường công theo thuật toán Douglas Peucker Ý tưởng cơ bản của thuật toán Douglas-Peucker là xét xem khoảng cách lớn nhất từ đường cong tới đoạn thẳng nối hai đầu mút đường cong (xem Hình 5.1) có lớn hơn ngưỡng  không. Nếu điều này đúng thì điểm xa nhất được giữ lại làm điểm chia đường cong và thuật toán được thực hiện 71
tương tự với hai đường cong vừa tìm được. Trong trường hợp ngược lại, kết quả của thuật toán đơn giản hoá là hai điểm đầu mút của đường cong. Thuật toán Douglas-Peucker: Bước 1: Chọn ngưỡng . Bước 2: Tìm khoảng cách lớn nhất từ đường cong tới đoạn thẳng nối hai đầu đoạn đường cong h. Bước 3: Nếu h  thì dừng. Bước 4: Nếu h >  thì giữ lại điểm đạt cực đại này và quay trở lại bước 1. Nhận xét: Thuật toán này tỏ ra thuận lợi đối với các đường cong thu nhận được mà gốc là các đoạn thẳng, phù hợp với việc đơn giản hoá trong quá trình véctơ các bản vẽ kỹ thuật, sơ đồ thiết kế mạch in v.v 5.1.2.2. Chương trình //Hàm tính đường cao từ dinh đến đoạn thẳng nối hai điểm dau, cuoi float Tinhduongcao (POINT dau, POINT cuoi, POINT dinh) { floot h; tính đường cao returm h ; } //Hàm đệ quy nhằm đánh dấu loại bỏ các điểm trong đường cong void DPSimple(POINT *pLINE,int dau,int cuoi,BOOL *chiso,float ) int i, index = dau; float h, hmax = 0; for(i = dau + 1; i hmax) hmax = h; index = i; 72
 } if(hmax ≤ ) for(i= dau + 1; i < cuoi, i++) chisoi = FALSE; else DPSimple(PLINE, dau, index, chiso, ); DPSimple(PLINE, index, cuoi, chiso, ) ;  } //Hàm rút gọn số lượng điểm DouglasPeucker int DouglasPeucker(POINT *pLINE, int n, float ) int i, j; BOOL chiso MAX_PT; for(i = 0; i < m; i++) //Tất cả các điểm được giữ lại chisoi = TRUE; DPSimple(pLINE, 0, n – 1, chiso, ); for(i = j = 0; i < n; i ++) if (chiso i ==TRUE) pLINEj++ = pLINEi; return j; } 5.1.3. Thuật toán Band width 5.1.3.1. Ý tưởng Trong thuật toán Band Width, ta hình dung có một dải băng di chuyển từ đầu mút đường cong dọc theo đường cong sao cho đường cong nằm trong di băng đó cho đến khi có điểm thuộc đường cong chạm vào biên của dải băng, điểm này sẽ được giữ lại. Quá trình này được thực hiện với phần còn lại của đường cong bắt đầu từ điểm vừa tìm được cho đến khi hết đường cong. Cụ thể như sau: 73
P3 P 2 P di 4 dk P1 P5 Hình 5.2. Đơn giản hóa đường cong với thuật toán Band Width Bắt đầu bằng việc xác định điểm đầu tiên trên đường cong và coi đó như là một điểm chốt (P 1). Điểm thứ ba (P 3) được coi là điểm động. Điểm giữa điểm chốt và điểm động (P2) là điểm trung gian. Ban đầu khoảng cách từ điểm trung gian đến đoạn thẳng nối điểm chốt và điểm động được tính toán và kiếm tra. Nếu khoảng cách tính được này nhỏ hơn một ngưỡng  cho trước thì điểm trung gian có thể bỏ đi, tiến trình tiếp tục với điểm chốt là điểm chốt cũ, điểm trung gian là điểm động cũ và điểm động là điểm kế tiếp sau điểm động cũ. Trong trường hợp ngược lại, khoảng cách tính được lớn hơn ngưỡng  cho trước thì điểm trung gian sẽ được giữ lại, tiến trình tiếp tục với điểm chốt là điển trung gian, điểm trung gian là điểm động cũ và điểm động là điểm kế tiếp sau điểm động cũ. Tiến trình được lặp cho đến hết đường cong (Hình 5.2 minh họa thuật toán Band-Width). Thuật toán Band-Width: Bước 1: Xác định điểm đầu tiên trên đường cong và coi đó như là một điểm chốt (P1). Điểm thứ ba (P3) được coi là điểm động. Điểm giữa điểm chốt và điểm động (P2) là điểm trung gian. Bước 2: Tính khoảng cách từ điểm trung gian đến đoạn thẳng nối hai điểm chốt và điểm động. Bước 3: Kiểm tra khoảng cách tìm được nếu nhỏ hơn một ngưỡng  cho trước thì điểm trung gian có thể bỏ đi. Trong trường hợp ngược lại điểm chốt chuyển đến điểm trung gian. Bước 4: Chu trình được lặp lại thì điểm trung gian được chuyển đến điểm động và điểm kế tiếp sau điểm động được chỉ định làm điểm động mới Nhận xét: Thuật toán này tăng tốc độ trong trường hợp đường ống chứa nhiều điểm, điều đó có nghĩa là độ lệch giữa các điểm trong đường thẳng là nhỏ, hay độ dày nét của đường được véctơ hoá là mảnh. 74
5.1.3.2. Chương trình //Hàm tính đường cao từ đỉnh đến đoạn thẳng nối hai điểm dau, cuoi float Tinhduongcao(POINT dau, POINT cuoi, POINT dinh) { floot h; tính đường cao returm h ; } //Hàm đệ quy nhằm đánh dấu loại bỏ các điểm trong đường cong void BWSimple(POINT *pLINE, int chot, int tg, BOOL *chiso, float , int n) { if(Tinhduongcao(pLINEchot, pLINEtg+1, pLINEtg) ≤ ) chisotg = 0; else chot = tg; tg = tg + 1 if(tg < n - 1) BWSimple (pLINE, chot, tg, chiso, , n) ; } //Hàm rút gọn số lượng điểm BandWidth int BandWidth(POINT *pLINE, int n, floot ) int i, j; BOOL chiso MAX_PT; for (i = 0; i < n; i++) chisoi= TRUE; //Tất cả các điểm được giữ lại BWSimple(pLINE, 0, 1, chiso, , n); for(i= j= 0; i < n; i++) if(chiso i== TRUE) pLINE j ++1 = pLINE i; 75
return j; } 5.1.4. Thuật toán Angles 5.1.4.1. Ý tưởng Tương tự như thuật toán Band Width nhưng thay việc tính toán khoảng cách bởi tính góc. Cụ thể thuật toán bắt đầu với điểm đầu đường cong (P1) là điểm chốt. P3 k P2 i P4 P5 P1 Hình 5.3. Đơn giản hóa đường cong với thuật toán Angles Điểm thứ 3 của đường cong (P 3) là điểm động, điểm giữa điểm chốt và điểm động (P2) là điểm trung gian Góc tạo bởi điểm chốt, trung gian, động với điểm trung gian là đỉnh việc tính toán và kiểm tra Nếu thì điểm trung gian có thể bỏ đi trong trường hợp ngược lại điểm chốt sẽ là điểm trung gian cũ và quá trình lặp với điểm trung gian là điểm động cũ, điểm động mới là điểm kế tiếp sau điểm động cũ. Tiến trình thực hiện cho đến hết đường cong. 5.1.4.2. Chương trình //Hàm tính đường cao từ đỉnh đến đoạn thẳng nối hai điểm dau, cuoi float Tinhgoc(POINT dau, POINT cuoi, POINT dinh) { float ; tinhgoc (tự viết) return ; } //Hàm đệ quy nhằm đánh dấu loại bỏ các điểm trong đường cong void ALSimple(POINT *pLINE,int chot,int tg,BOOL *chiso,float ,int n) { if(Tinhgoc(pLINEchot, pLINEtg, pLINEtg+1) > ) 76
chisotg = FALSE; else chot = tg; tg = tg + 1; if(tg < n - 1) ALSimple(pLINE, chot, tg, chiso, , n); } //Hàm rút gọn số lượng điểm Angles int Angles(POINT *pLINE, int n, float ) int i, j, chiso MAX; for (i = 0; i < n; i++) //Tất cả các điểm được giữ lại chisoi= TRUE; ALSiple (PLINE, 0, 1 chiso, , n) ; for (i = j = 0; i < n; i++) if (chiso ==TRUE) pLINEj++= pLINE i; return j; } * Chú ý: Với = 0 thuật toán DouglasPeucker và BandWidth sẽ bỏ đi các điểm giữa thẳng hàng. Thuật toán Angles phải có = 180o để bỏ đi các điểm giữa thẳng hàng. 5.2. XẤP XỈ ĐA GIÁC BỞI CÁC HÌNH CƠ SỞ Các đối tượng hình học được phát hiện thường thông qua các kỹ thuật dò biên, kết quả tìm được này là các đường biên xác định đối tượng. Đó là, một dãy các điểm liên tiếp đóng kính, sử dụng các thuật toán đơn giản hoá như Douglas Peucker, Band Width, Angle v.v ta sẽ thu được một polyline hay nói khác đi là thu được một đa giác xác định đối tượng dấu. Vấn đề là ta cần phải xác định xem đối tượng có phải là đối tượng cần tách hay không? Như ta đã biết một đa giác có thể có hình dạng tựa như một hình cơ sở, có thể có nhiều cách tiếp cận xấp xỉ khác nhau. Cách xấp xỉ dựa trên các đặc trưng cơ bản sau: 77
Đặc trưng toàn cục: Các mô men thống kê, số đo hình học như chu vi, diện tích, tập tối ưu các hình chữ nhật phủ hay nội tiếp đa giác v.v Đặc trưng địa phương: Các số đo đặc trưng của đường cong như góc, điểm lồi, lõm, uốn, cực trị v.v Nhδn dδng đδi tưδng Bất biến Bδt biδn đồng dạng Aphin Đưδng tròn Ellipse Ellipse Tam giác Hình chữ nhật Tδ giác Tam giác đδu Đa giác Hình 5.4. Sơ đồ phân loại các đối tượng theo bất biến Việc xấp xỉ tỏ ra rất có hiệu quả đối với một số hình phẳng đặc biệt như tam giác, đường tròn, hình chữ nhật, hình vuông, hình ellipse, hình tròn và một đa giác mẫu. 5.2.1 Xấp xỉ đa giác theo bất biến đồng dạng Hình 5.5. Xấp xỉ đa giác bởi một đa giác mẫu Một đa giác với các đỉnh V0, ,Vm-1 được xấp xỉ với đa giác mẫu U0, ,Un-1 với độ đo xấp xỉ như sau: E(V ,U) min d , 0 d m 1 n 78
Trong đó n 1 2 area(V0Vm 1 ) d min kRU j a V( j d ) mod m , k , với R  là 0  2 , R2  j 0 area(U 0U n 1 ) d phép quay quanh gốc toạ độ một góc . Trong đó, d được tính hiệu quả bằng công thức sau: n 1 n 1 n 1 n 1 2 1 2 2 2 d |V( j d ) mod m | |V( j d ) mod m | k |U j | 2k|U jV( j d ) mod m | j 0 n j 0 j 0 j 0 d Ở đây Uj, Vj được hiểu là các số phức tại các đỉnh tương ứng. Khi m >> n thì độ phức tạp tính toán rất lớn. Với các hình đặc biệt như hình tròn, ellipse, hình chữ nhật, hình xác định duy nhất bởi tâm và một đỉnh (đa giác đều ) ta có thể vận dụng các phương pháp đơn giản hơn như bình phương tối thiểu, các bất biến thống kê và hình học. Định nghĩa 5.1 Cho đa giác Pg có các đỉnh U0, U1, , Un(U0 Un) Khi đó mô men bậc p+q được xác định như sau: p q M pq x y dxdy . Pg Trong thực hành để tính tích phân trên người ta thường sử dụng công thức Green hoặc có thể phân tích phần bên trong đa giác thành tổng đại số của các tam giác có hướng OUiUi+1 . U2 U1 f (x, y)x p y q dxdy - Pg n 1 U0 U3  sign(xi yi 1 xi 1 yi ) O(0,0) i 0 p q -  f (x, y)x y dxdy OUiUi 1 Un- Hình 5.6. Phân tích miền1 đa giác thành tổng đại số các miền tam giác 79
5.2.1.1. Xấp xỉ đa giác bằng đường tròn Dùng phương pháp bình phương tối thiểu, ta có độ đo xấp xỉ: n 1 2 2 2 E(Pg,Cr)=min (xi yi axi byi c) a,b,c R  n i 1 Hình 5.7. Xấp xỉ đa giác bằng đường tròn 5.2.1.2. Xấp xỉ đa giác bằng ellipse Cũng như đối với đường tròn phương trình xấp xỉ đối với ellipse được cho bởi công thức: n 1 2 2 2 E(Pg,El)= min (xi ayi bxi yi cxi dyi e) a,b,c,d ,e R  n i 1 Một biến thể khác của phương pháp bình phương tối thiểu khi xấp xỉ các đường cong bậc hai được đưa ra trong [7]. 5.2.1.3. Xấp xỉ đa giác bởi hình chữ nhật Sử dụng tính chất diện tích bất biến qua phép quay, xấp xỉ theo diện tích như sau: Gọi 11 ,20 ,02 là các mô men bậc hai của đa giác (tính theo diện tích). Khi đó góc quay được tính bởi công thức sau: 2 tg2 11 20 - 02 . Gọi diện tích của hình chữ nhật nhỏ nhất có các cạnh song song với các trục quán tính và bao quanh đa giác Pg là S. Kí hiệu E(Pg, Rect)= S area(Pg) y x Hình 5.8. Xấp xỉ đa giác bằng hình chữ nhật 80
5.2.1.4. Xấp xỉ đa giác bởi đa giác đều n cạnh Gọi M(x0,y0) là trọng tâm của đa giác, lấy một đỉnh Q tuỳ ý của đa giác, xét đa giác đều n cạnh Pg’ tạo bởi đỉnh Q với tâm là M. Kí hiệu E(Pg, Pg’)= area(Pg) area(Pg') E(Pg, En)=min E(Pg,Pg’) khi Q chạy khắp các đỉnh của đa giác. 5.2.2 Xấp xỉ đa giác theo bất biến aphin Trong [7] đưa ra mô hình chuẩn tắc về bất biến aphin, cho phép chúng ta có thể chuyển bài toán xấp xỉ đối tượng bởi bất biến aphin về bài toán xấp xỉ mẫu trên các dạng chuẩn tắc. Như vậy có thể đưa việc đối sánh các đối tượng với mẫu bởi các bất biến đồng dạng, chẳng hạn việc xấp xỉ bởi tam giác, hình bình hành, ellipse tương đương với xấp xỉ tam giác đều, hình vuông, hình tròn v.v Thủ tục xấp xỉ theo bất biến aphin một đa giác với hình cơ sở được thực hiện tuần tự như sau: + Bước 0: Phân loại bất biến aphin các dạng hình cơ sở Dạng hình cơ sở Dạng chuẩn tắc Tam giác Tam giác đều Hình bình hành Hình vuông Ellipse Đường tròn   + Bước 1: Tìm dạng chuẩn tắc cơ sở Pg' thoả mãn điều kiện: m m 0 (phép tịnh tiến) 01 10 m02 m20 1 (phép co dãn theo hai trục x, y) ( ) m13 m31 0 + Bước 2: Xác định biến đổi aphin T chuyển đa giác thành đa giác Pg ở dạng chuẩn tắc (thoả mãn tính chất ( )). Xấp xỉ đa giác Pg với dạng chuẩn tắc cơ sở Pg’ tìm được ở bước 1 với độ đo xấp xỉ E(Pg,Pg’). + Bước 3: Kết luận, đa giác ban đầu xấp xỉ T-1(Pg’) với độ đo xấp xỉ E(Pg,Pg’). 81
Đối với bước 1 trong [7] đã đưa ra hai ví dụ sau: Ví dụ 1: Tồn tại duy nhất tam giác đều P1P2P3 thoả mãn tính chất ( ) là 4 2 8 3 P1=(0,-2 ),P2=( 3 , ) , P3= ( 3 , ) ,3 . Ví dụ 2: Tồn tại hai hình vuông  P1P2 P3 P4 thoả mãn tính chất ( ) Hình vuông thứ nhất có 4 đỉnh tương ứng là (-p,-p),(-p,p), (p,- 3 4 p),(p,p), với p= 4 Hình vuông thứ hai có 4 đỉnh tương ứng là (-p,0),(p,0), (0,-p),(0,p), với p=4 3 . 5.3. BIẾN ĐỔI HOUGH 5.3.1. Biến đổi Hongh cho đường thẳng Bằng cách nào đó ta thu được một số điểm vấn đề đặt ra là cần phải kiểm tra xem các điểm có là đường thẳng hay không Bài toán: Cho n điểm (x i; yi) i = 1, n và ngưỡng  hãy kiểm tra n điểm có tạo thành đường thẳng hay không? * Ý tưởng Giả sử n điểm nằm trên cùng một đường thẳng và đường thẳng có phương trình y = ax + b Vì (xi, yi) i = 1, n thuộc đường thẳng nên y1 = ax1 + b, i = 1, n b = - xia + y1; i = 1, n Như vậy, mỗi điểm (x i; yi) trong mặt phẳng sẽ tương ứng với một số đường thẳng b = - xia + yi trong mặt phẳng tham số a, b. n điểm (x i; yi) i = 1, n thuộc đường thẳng trong mặt phẳng tương ứng với n đường thẳng trong mặt phẳng tham số a, b giao nhau tại 1 điểm và điểm giao chính là a, b. Chính là hệ số xác định phương trình của đường thẳng mà các điểm nằm vào. 82
* Phương pháp: - Xây dựng mảng chỉ số a, b và gán giá trị 0 ban đầu cho tất cả các phân tử của mảng - Với mỗi (xi; yi) và a, b là chỉ số của phần tử mảng thoả mãn b = - xia + yi tăng giá trị của phân tử mảng tương ứng lên 1 - Tìm phần tử mảng có giá trị lớn nhất nếu giá trị lớn nhất tìm được so với số phân tử lớn hơn hoặc bằng ngưìng  cho trước thì ta có thể kết luận các điểm nằm trên cùng 1 đường thẳng và đường thẳng có phương trình y = ax + b trong đó a, b tương ứng là chỉ số của phần tử mảng có giá trị lớn nhất tìm được: Ví dụ: Cho 5 điểm (0, 1); (1, 3); (2, 5); (3, 5); (4, 9) và  = 80%. Hãy kiểm tra xem 5 điểm đã cho có nằm trên cùng một đường thẳng hay không? Hãy cho biết phương trình đường thẳng nếu có? - Lập bảng chỉ số a, b và gán giá trị 0 + (0, 1): b = 1 + (1, 3): b = -a + 3 + (2, 5): b = -2a + 5 + (3, 5): b = -3a + 5 + (4, 9): b = -4a + 9 - Tìm phần tử lớn nhất có giá trị 4 4/5 = 80% - Kết luận: 5 điểm này nằm trên cùng 1 đường thẳng Phương trình: y = 2x + 1 83
5.3.2. Biến đổi Hough cho đường thẳng trong tọa độ cực 0 y r x.cos +y.sin =r H x Hình 5.9. Đường thẳng Hough trong toạ độ cực Mỗi điểm (x,y) trong mặt phẳng được biểu diễn bởi cặp (r, ) trong tọa độ cực. Tương tự mỗi đường thẳng trong mặt phẳng cũng có thể biểu diễn bởi một cặp (r, ) trong tọa độ cực với r là khoảng cách từ gốc tọa độ tới đường thẳng đó và là góc tạo bởi trục 0X với đường thẳng vuông góc với nó, hình 5.9 biểu diễn đường thẳng hough trong tọa độ Decard. Ngược lại, mỗi một cặp (r, ) trong toạ độ cực cũng tương ứng biểu diễm một đường thẳng trong mặt phẳng. Giả sử M(x,y) là mộ điểm thuộc đường thẳng được biểu diễn bởi (r, ), gọi H(X,Y) là hình chiếu của gốc toạ độ O trên đường thẳng ta có: X= r. cos và Y= r.sin Mặt khác, ta có: OH.HA=0 Từ đó ta có mối liên hệ giữa (x,y) và (r, ) như sau: x*cos +y*sin = r. Xét n điểm thẳng hàng trong tọa độ Đề các có phương trình x*cos 0+y*sin 0= r0. Biến đổi Hough ánh xạ n điểm này thành n đường sin trong tọa độ cực mà các đường này đều đi qua (r0, 0). Giao điểm (r0, 0) của n đường sin sẽ xác định một đường thẳng trong hệ tọa độ đề các. Như vậy, những đường thẳng đi qua điểm (x,y) sẽ cho duy nhất một cặp (r, ) và có bao nhiêu đường qua (x,y) sẽ có bấy nhiêu cặp giá trị (r, ). 84
Chương 6: ỨNG DỤNG XỬ LÝ ẢNH 6.1. PHÁT HIỆN GÓC NGHIÊNG VĂN BẢN DỰA VÀO CHU TUYẾN Góc nghiêng văn bản là một bài toán kinh điển trong xử lý ảnh văn bản. Một hệ thống xử lý ảnh văn bản thường phải giải quyết bài toán phát hiện góc nghiêng như một bước đầu tiên và tất yếu. Chính vì vậy, cùng với sự phát triển của xử lý ảnh nói chung và xử lý ảnh văn bản nói riêng, bài toán góc nghiêng văn bản cũng được quan tâm ngày càng nhiều và dưới nhiều góc độ khác nhau. Có rất nhiều hướng tiếp cận cho bài toán góc nghiêng văn bản từ trước tới nay. Các thuật toán phát hiện góc nghiêng thường được xây dựng cho các hệ thống phân tích ảnh văn bản khác nhau nên chỉ giải quyết cho những loại ảnh văn bản cụ thể. Có thể chia ra một số hướng tiếp cận cơ bản cho bài toán góc nghiêng văn bản như sau: Các thuật toán dựa vào phân tích hình chiếu (Projection Profile) Các thuật toán dựa vào biến đổi Hough (Hough Transform) Các thuật toán phân tích láng giềng (Nearest Neighbour Clustering) Phương pháp dùng các phép toán hình thái Dựa vào tính chất mỗi đối tượng ảnh có duy nhất một chu tuyến ngoài và quan niệm con người nhận ra độ nghiêng của văn bản dựa vào cỡ chữ chiếm chủ đạo trong văn bản. Mục này đề cập đến việc tính toán kích thước chủ đạo của các đối tượng ảnh trong văn bản thông qua kỹ thuật tính biểu đồ tần xuất kích thước hình chữ nhật nhỏ nhất bao quanh đối tượng ảnh. Việc xác định góc nghiêng văn bản sẽ được xác định nhờ phép biến đổi Hough cho những điểm giữa đáy của hình chữ nhật nhỏ nhất bao quanh đối tượng ảnh cho các đối tượng ảnh có kích thước chủ đạo. 6.1.1. Tính toán kích thước chủ đạo của các đối tượng ảnh Như đã nói từ các phần trên, góc nghiêng được xác định dựa vào biến đổi Hough. Ở đây, chúng ta chỉ áp dụng biến đổi Hough cho những điểm giữa đáy của các hình chữ nhật ngoại tiếp các đối tượng có kích thước chủ đạo trong ảnh. Như vậy, công việc đầu tiên cần thực hiện là xác định được các hình chữ nhật ngoại tiếp các đối tượng hay nói cách khác là xác định biên các đối tượng. 85