Tài liệu Nâng cao chất lượng ảnh nhị phân bằng phương pháp morphotogy

MỤC LỤC Lời Cảm Ơn ! ....................................................................... Error! Bookmark not defined. DANH MỤC HÌNH VẼ BẢNG BIỂU SỬ DỤNG TRONG ĐỒ ÁN........................... 2 Lời Mở Đầu ! ................................................................................................................. 1 CHƢƠNG I. TỔNG QUAN VỀ PHƢƠNG PHÁP NÂNG CAO CHẤT LƢỢNG ẢNH .... 4 1.1 Giới thiệu chung về xử lý ảnh .................................................................................... 4 1.2 Giới thiệu ảnh nhị phân .............................................................................................. 6 1.2.1 Một số khái miệm .................................................................................................. 6 1.2.2 Nâng cao chất lƣợng ảnh bằng kỹ thuật phát hiện biên và tìm xƣơng .................. 7 1.2.2.1 Phƣơng pháp phát hiện biên. ........................................................................ 8 1.2.2.2 Kỹ thuật tìm xƣơng. ................................................................................... 12 1.2.3 Nâng cao chất lƣợng ảnh bằng các phép toán hình thái. ..................................... 15 1.2.4 Kết luận và vấn đề nghiên cứu: ........................................................................... 16 CHƢƠNG II. NÂNG CAO CHẤT LƢỢNG ẢNH BẰNG PHÉP TOÁN HÌNH THÁI .... 18 2.1. Khái niệm cơ bản ...................................................................................................... 19 2.2. Các phép toán Logic liên quan đến ảnh nhị phân ..................................................... 23 2.3. Phép giãn nhị phân (Dilation) ................................................................................... 27 2.4. Phép co nhị phân (Erosion) ....................................................................................... 30 2.5. Một số tính chất của phép toán hình thái .................................................................. 33 2.5.1. Các mệnh đề....................................................................................................... 33 2.5.2. Định lý ............................................................................................................... 34 2.5.3. Hệ quả ................................................................................................................ 35 2.6. Phép mở ảnh (Opening) và phép đóng ảnh (Closing)............................................... 35 2.6.1. Phép mở ảnh ...................................................................................................... 36 2.6.2. Phép đóng ảnh .................................................................................................... 38 2.6.3. Các tính chất của Phép mở ảnh và phép đóng ảnh ............................................ 40 2.7. Phép Biến đổi trúng hoặc trƣợt (Hit-or-Miss) .......................................................... 41 2.8. Các thuật toán cơ bản của hình thái học ................................................................... 42 2.8.1. Trích biên ( Boundary Extraction ) .................................................................... 43 2.8.2. Làm đầy (Region Filling) .................................................................................. 44 2.8.3. Trích chọn liên thông (Extraction of Connected Components) ......................... 46 2.8.4. Bao Lồi (Convex Hull) ...................................................................................... 48 2.8.5. Làm mảnh(Thinning) ......................................................................................... 50 2.8.6. Tìm khung xƣơng (Skeletonization) .................................................................. 52 CHƢƠNG III. ỨNG DỤNG CỦA PHÉP TOÁN HÌNH THÁI .......................................... 55 3.1. Nâng cao chất lƣợng biên ảnh dựa vào phép toán hình thái ..................................... 55 3.2. Sử dụng phép toán hình thái trong nối chữ đứt nét. .................................................. 57 3.2.1. Mô tả phƣơng pháp ............................................................................................ 58 3.2.2. Áp dụng phép toán hình thái .............................................................................. 58 3.3. Thực Nghiệm ............................................................................................................ 61 3.4 Giới thiệu chƣơng trình.............................................................................................. 67 Kết luận ................................................................................................................................ 73 Tài liệu tham khảo: .............................................................................................................. 75 DANH MỤC HÌNH VẼ BẢNG BIỂU SỬ DỤNG TRONG ĐỒ ÁN Hình 1.1: Các giai đoạn chính trong xử lý ảnh. ............................................................. 5 Hình 1.2 Mô hình tổng quát của hệ thống nhận dạng ảnh ............................................. 8 Hình 1.3. Ví dụ về ảnh và xƣơng ................................. Error! Bookmark not defined. Hình 1.4. Một số dạng biểu diễn đƣờng thẳng trong các bản vẽ kỹ thuật ................... 12 Hình 2.1: Ảnh và đối tƣợng trong ảnh. ........................................................................ 19 Hình 2.2: Quan hệ giữa hai tập hợp ............................................................................. 20 Hình 2.3: Phép biến đổi của tập hợp .................................................... 1_Toc293129659 Hình 2.4: Một số phép toán logic giữa các hình ảnh nhị phân. ................................... 25 Hình 2.5: Một vài ví dụvề các phần tử cấu trúc. .......................................................... 26 Hình 2.6: Phép giãn nhị phân....................................................................................... 28 Hình 2.7: Quá trình quét của phần tử cấu trúc trên hình ảnh nhị phân. ....................... 29 Hình 2.8: Phép co nhị phân trên hai đối tƣợng ............................................................ 30 Hình 2.9: Quá trình lọc đối tƣợng sử dụng phép co nhị phân và phép giãn nhị phân. 32 Hình 2.10: Ứng dụng của phép co ảnh dƣới dạng số nhị phân. ................................... 33 Hình 2.11: Quá trình thực hiệp phép mở ảnh. ............................................................. 37 Hình 2.12: Phép mở ảnh trên phƣơng diện ý nghĩa hình học. ..................................... 37 Hình 2.13: Quá trình thực hiện phép đóng ảnh. ........................................................... 39 Hình 2.14: Minh họa phép đóng ảnh trên phƣơng diện ý nghĩa hình học. .................. 40 Hình 2.15: Minh họa phép biến đổi trúng hoặc trƣợt .................................................. 40 Hình 2.16: Quá trình tìm biên của đối tƣợng trên ảnh nhị phân. ................................. 44 Hình 2.17: Quá trình làm đầy đối tƣợng trong ảnh. ..................................................... 46 Hình 2.18: Quá trình tách các thành phần liên thông trong ảnh bằng phép toán hình thái. .................................................................................................................... 47 Hình 2.19: Một quá trình trong phép bao lồi. .............................................................. 49 Hình 2.20: Phép bao lồi đối với đối tƣợng trong ảnh. ................................................. 50 Hình 2.21: Quá trình làm mảnh đối tƣợng trong hình ảnh. ......................................... 50 Hình 2.22: Quá trình thực hiện thuật toán tìm xƣơng. ................................................. 54 Hình 3.1. Kết quả của phép toán giãn nở ..................................................................... 59 Hình 3.2: Kết quả của phép toán co ảnh ...................................................................... 60 Hình 3.3: Sơ đồ thuật toán nâng cấp ảnh nét đứt. ........ Error! Bookmark not defined. Hình 3.4: Ảnh chữ photocopy bị đứt nét ..................................................................... 61 Hình 3.5: Ảnh chữ photocopy nối nét và tái hiện ........................................................ 61 Hình 3.6: Thực nghiệm giãn nhị phân hình ảnh với cấu trúc 4x4. .............................. 59 Hình 3.7: Thực hiện giãn nhị phân hình ảnh với phần tử cấu trúc 7x7. ...................... 59 Hình 3.8: Thực nghiệm phép co nhị phân trên hình ảnh với phần tử cấu trúc 4x4. .... 63 Hình 3.9 Thực nghiệm phép mở ảnh trên hình ảnh với phần tử cấu trúc tròn 7x7. ..... 64 Hình 3.10: Thực nghiệm mở ảnh làm trơn góc của đối tƣợng trong ảnh nhị phân. .... 64 Hình 3.11: Thực nghiệm phép mở ảnh với phần tử cấu trúc hình chữ thập, kích thƣớc 7x7. .................................................................................................................... 65 Hình 3.12: Thực nghiệm phép đóng ảnh trên phần tử cấu trúc tròn 7x7. .................... 65 Hình 3.13: Thực nghiệm phép đóng ảnh với phần tử cấu trúc hình dạng chữ thập, kích thƣớc 7x7. ................................................................................................................ 66 Hình 3.14AB: Sơ đồ thuật toán tìm xƣơng dựa vào phép toán hình thái,thực nghiệm Error! Bookmark not defined. Hình 3.15: Thực nghiệm tìm biên của đối tƣợng. ........................................................ 67 Hình 3.16: Giao diện chính của chƣơng trình. ............. Error! Bookmark not defined. Hình 3.17: Ảnh đầu vào cần xử lý. ............................................................................. 67 Hình 3.18: Chuyển ảnh màu sang nhị phân. ................ Error! Bookmark not defined. Hình 3.19: Chuyển ảnh màu sang ảnh xám. ................................................................ 67 Hình 3.20: Phép toán tác động lên ảnh gốc. ................ Error! Bookmark not defined. Hình 3.21: Cấu trúc tác động lên ảnh gốc.................................................................... 67 Hình 3.22: Nâng cấp chất lƣợng ảnh bằng phép toán Morphology .. Error! Bookmark not defined. Hình 3.23: Tìm biên ảnh bằng phép toán Morphology................................................ 70 1 Lời Mở Đầu ! Trong thực tế hình dạng thƣờng đƣợc chú trọng hơn kích thƣớc và con ngƣời nhận ra các đối tƣợng xung quanh cũng chủ yếu thông qua hình ảnh. Hình ảnh là một dạng dữ liệu đóng vai trò quan trọng trong việc trao đổi, xử lý, lƣu giữ thông tin...Trong chúng ta có lẽ không có ai đã không từng sử dụng hình ảnh cho một mục đích nào đấy. Trong nhiều ngành nghề, trong một số các loại hình công việc, ngƣời ta điều cần đến hình ảnh để mô tả, minh chứng hay diễn đạt những điều mà đôi khi chữ viết hay ngôn ngữ nói không diễn tả hết đƣợc. Đặc biệt trong một số ngành nghề nhƣ: cơ khí chế tạo, sản xuất, học tập, báo chí, việc đọc hình ảnh có thể nói là thƣờng xuyên và cực kỳ quan trọng. Bản vẽ kỹ thuật (một dạng của hình ảnh), tài liệu điện tử (giáo trình tham khảo) chính là kết quả ngôn ngữ kỹ thuật. Mà qua nó, một qui trình công nghệ phải đƣợc xây dựng trong quá trình sản xuất, cũng nhƣ nó chính là cơ sở cho việc nghiệm thu cho bất kỳ sản phẩm nào. Để lƣu ảnh của các tài liệu, các bản vẽ hoặc sửa đổi chúng và chuyển chúng sang các dạng đồ hoạ khác tiện cho việc nhận dạng, đối sánh mẫu để sử dụng sau này là điều cần thiết. Nhƣng phải tổ chức việc lƣu các dạng hình ảnh này nhƣ thế nào? Có cần xử lý trƣớc khi lƣu chúng không? Câu trả lời là có. Do vậy tiền xử lý ảnh là việc cần làm. Có nhiều phƣơng pháp, nhiều công cụ, nhiều phần mềm xử lý ảnh đã ra đời. Tăng cƣờng chất lƣợng ảnh, mà công đoạn đầu tiên là một bƣớc tiền xử lý nhằm xác định ảnh, khắc phục những khiếm khuyết do bƣớc thu nhận ảnh không tốt là việc làm quan trọng. Có nhiều phƣơng pháp cho việc nâng cao chất lƣợng ảnh nói chung và tiền xử lý nói riêng. Trong luận văn này em chỉ mô tả một vài phƣơng pháp tiền xử lý hình ảnh (chú trọng đến ảnh nhị phân, bởi ảnh của các bản vẽ kỹ thuật và sách scan thƣờng chỉ là ảnh 2 màu: đen, trắng) nhằm cải thiện chất lƣợng hình ảnh bằng các thao tác Hình thái học (Morphology) để ứng dụng vào chƣơng trình nâng cao chất lƣợng ảnh Scan tài liệu giáo trình điện tử tại thƣ viện Trƣờng Đại học Lạc Hồng. Các thao tác Hình thái học nói chung,đặc biệt là Hình thái học số đƣợc sử dụng chủ yếu vào việc cải thiện ảnh bằng cách làm rõ (tái hiện) những nét đặc trƣng 2 của các hình dạng, do vậy mà có thể tính toán đƣợc hay nhận biết đƣợc chúng một cách dễ dàng. Việc sử dụng các thao tác hình thái và ứng dụng của chúng, đặc biệt là ứng dụng nâng cao chất lƣợng hình ảnh cho bƣớc tiền xử lý, trƣớc khi thực hiện những bƣớc kế tiếp cho công việc xử lý ảnh . Chính vì vậy em đã lựa chọn đề tài nghiên cứu “Nâng cao chất lƣợng ảnh nhị phân bằng phép toán hình thái học morphology”. Mục tiêu của đề tài nghiên cứu là tìm hiểu nghiên cứu một số kỹ thuật nâng cao chất lƣợng ảnh nhị phân vào xử lý các đối tƣợng trong hình ảnh và xây dựng chƣơng trình ứng dụng thực tế. Báo cáo đề tài nghiên cứu đƣợc chia làm 3 chƣơng: Chƣơng I. Tổng quan về phƣơng pháp nâng cao chất lƣợng ảnh: Chƣơng này gồm có các khái niệm ban đầu về xử lý ảnh, ảnh nhị phân, tầm quan trọng, biểu diễn hình dạng cơ bản theo biên và xƣơng và các bƣớc đƣợc thực hiện trong quá trình xử lý ảnh.Sau đó nêu mục tiêu trong chƣơng 2 là sử dụng các phép toán hình thái trong việc xử lý ảnh. Chƣơng II. Nâng cao chất lƣợng ảnh bằng phép toán hình thái: Chƣơng này gồm có các phép toán hình thái nâng cao chất lƣợng ảnh, từ cơ bản đến những khái niệm nâng cao và ứng dụng trong thực tế. Đầu tiên là các khái niệm tập hợp nhƣ các quan hệ phép hợp, phép giao, phép bù… sau đó là các phép toán logic liên quan đến quá trình xử lý ảnh nhị phân, để tiện cho việc phân tích và chứng minh các công thức chính của phép toán hình thái. Toàn bộ chƣơng tập trung làm rõ các khái niệm về: phép co nhị phân, phép giãn nhị phân, phép đóng ảnh, phép mở ảnh, phép trúng hoặc trƣợt (Hit-or-Miss), phép trích biên, phép làm đầy, phép tách các thành phần liên thông, phép bao lồi, phép làm mảnh và tìm xƣơng. Chƣơng III. Ứng dụng của phép toán hình thái trong nâng cao chất lƣợng ảnh: Chƣơng này so sánh cách tiếp cận của đề tài, các ứng dụng của phép toán hình thái đã tìm hiểu trong xử lý ảnh. Trên cơ sở lý thuyết đã tìm hiểu xây dựng chƣơng trình xử lý ảnh sử dụng các phép toán: phép co nhị phân, phép giãn nhị phân, phép 3 đóng ảnh, phép mở ảnh, tìm biên ảnh và tìm xƣơng làm mảnh các đối tƣợng trên ảnh nhị phân và thực nghiệm. 4 CHƢƠNG I. TỔNG QUAN VỀ PHƢƠNG PHÁP NÂNG CAO CHẤT LƢỢNG ẢNH Trong ngành khoa học máy tính, xử lý ảnh là một dạng của xử lý tín hiệu cho đầu vào là một ảnh hoặc các frame của phim ảnh. Đầu ra có thể là một hình ảnh, hoặc tập hợp các ký tự hoặc các tham số liên quan tới hình ảnh. Thƣờng thì kỹ thuật xử lý ảnh có liên quan tới xử lý tín hiệu hai chiều và đƣợc áp dụng bằng một chuẩn riêng về kỹ thuật xử lý ảnh cho nó. Các khái niệm cơ bản để xử lý tín hiệu nhƣ, khái niệm về tích chập, các biến đổi Fourier, biến đổi Laplace, các bộ lọc hữu hạn… Ngoài ra còn cần tới các công cụ toán học nhƣ đại số tuyến tính, sác xuất, thống kê. Và một số kiến thức cần thiết nhƣ trí tuệ nhân tao, mạng nơron nhân tạo cũng đƣợc đề cập trong quá trình phân tích và nhận dạng ảnh. 1.1 Giới thiệu chung về xử lý ảnh Cũng nhƣ xử lý dữ liệu bằng đồ hoạ, xử lý ảnh là một lĩnh vực của tin học ứng dụng. Xử lý dữ liệu bằng đồ họa đề cập đến những ảnh nhân tạo, các ảnh này đƣợc xem xét nhƣ là một cấu trúc dữ liệu và đƣợc tạo ra bởi các chƣơng trình. Xử lý ảnh bao gồm các phƣơng pháp và kỹ thuật để biến đổi, để truyền tải hoặc mã hóa các ảnh tự nhiên. Mục đích của xử lý ảnh gồm: Thứ nhất, biến đổi ảnh và làm đẹp ảnh. Thứ hai, tự động nhận dạng ảnh hay đoán nhận ảnh và đánh giá các nội dung của ảnh. Nhận dạng ảnh là quá trình liên quan đến các mô tả đối tƣợng mà ngƣời ta muốn đặc tả nó. Quá trình nhận dạng thƣờng đi sau quá trình trích chọn các đặc tính chủ yếu của đối tƣợng. Có hai kiểu mô tả đối tƣợng: - Mô tả tham số (nhận dạng theo tham số). - Mô tả theo cấu trúc(nhận dạng theo cấu trúc). 5 Nhận biết và đánh giá các nội dung của ảnh là sự phân tích một hình ảnh thành những phần có nghĩa để phân biệt đối tƣợng này với đối tƣợng khác. Dựa vào đó ta có thể mô tả cấu trúc của hình ảnh ban đầu. Có thể liệt kê một số phƣơng pháp nhận dạng cơ bản nhƣ nhận dạng biên của một đối tƣợng trên ảnh, tách cạnh, phân đoạn hình ảnh ... Kỹ thuật này đƣợc sử dụng nhiều trong y học (xử lý tế bào, nhiễm sắc thể). Trong thực tế ngƣời ta đã áp dụng kỹ thuật nhận dạng khá thành công với nhiều đối tƣợng khác nhau nhƣ: nhận dạng ảnh vân tay, nhận dạng chữ (chữ cái, chữ số, chữ có dấu). Nhận dạng chữ in hoặc đánh máy trong văn bản phục vụ cho việc tự động hoá quá trình đọc tài liệu, tăng nhanh tốc độ và chất lƣợng thu nhận thông tin từ máy tính, nhận dạng chữ viết tay (với mức độ ràng buộc khác nhau về cách viết, kiểu chữ, ...). Các quá trình của xử lý ảnh: Các quá trình của xử lý ảnh[1] đƣợc tiến hành theo sơ đồ sau: Lƣu trữ Lƣu trữ Camera Thu nhận ảnh Số hoá Nhận dạng Phân tích ảnh Sensor Hệ quyết định Hình 1.1: Các giai đoạn chính trong xử lý ảnh Trƣớc hết là quá trình thu nhận ảnh. Ảnh có thể thu nhận qua camera. Thƣờng ảnh thu nhận qua camera là tín hiệu tƣơng tự (loại camera ống kiểu CCIR), nhƣng cũng có thể là tín hiệu số hoá (loại CCD - Charge Coupled Device). 6 Ảnh có thể thu nhận từ vệ tinh qua các bộ cảm ứng (sensor), hay ảnh, sách đƣợc quét qua scanner. Tiếp theo là quá trình số hóa (Digitalizer) để biến đổi tín hiệu tƣơng tự sang tín hiệu rời rạc (lấy mẫu) và số hóa bằng lƣợng hóa, trƣớc khi chuyển sang giai đoạn xử lý, phân tích hay lƣu trữ lại. Quá trình phân tích ảnh thực chất bao gồm nhiều công đoạn nhỏ. Trƣớc hết là công việc tăng cƣờng hình ảnh (Image Enhancement) để nâng cao chất lƣợng hình ảnh. Do những nguyên nhân khác nhau: có thể do thiết bị thu nhận ảnh, do nguồn sáng hay do nhiễu, ảnh có thể bị suy biến. Do vậy cần phải tăng cƣờng và khôi phục (Image Restoration) lại ảnh để làm nổi bật một số đặc tính chính của ảnh, hay làm cho ảnh gần giống với trạng thái gốc- trạng thái trƣớc khi ảnh bị biến dạng. Giai đoạn tiếp theo là phát hiện các đặc tính nhƣ biên (Edge Detection), phân vùng ảnh (Image Segmentation), trích chọn các đặc trƣng (Feature Extraction),v.v... Cuối cùng, tuỳ theo mục đích của ứng dụng, sẽ là giai đoạn nhận dạng, phân lớp hay các quyết định khác. Các giai đoạn chính của quá trình xử lý ảnh có thể mô tả ở hình 1.1, việc nâng cao chất lƣợng ảnh trƣớc khi nhận dạng hay đối sánh là việc cần phải giải quyết. 1.2 Giới thiệu ảnh nhị phân Nhƣ đã giới thiệu ở trên. Trong quá trình xử lý ảnh, một ảnh đƣợc nhận vào máy tính phải đƣợc mã hoá. Hình ảnh khi lƣu trữ dƣới dạng tập tin phải đƣợc số hoá. Tiêu chuẩn đặt ra là ảnh phải lƣu trữ thế nào sao cho các ứng dụng khác nhau có thể thao tác trên các loại dữ liệu này. Hiện nay có trên 50 quy cách lƣu trữ ảnh khác nhau, trong đó ta thƣờng gặp các dạng ảnh sau: TIFF, GIF, BMP, PCX, JPEG, ... Nói chung mỗi kiểu lƣu ảnh có ƣu điểm riêng. 1.2.1 Một số khái miệm Pixel (Picture Element): Phần tử ảnh Ảnh trong thực tế là một ảnh liên tục về không gian và về giá trị độ sáng. Để có thể xử lý ảnh bằng máy tính cần thiết phải tiến hành số hoá ảnh. Trong quá trình 7 số hoá, ngƣời ta biến đổi tín hiệu liên tục sang tín hiệu rời rạc thông qua quá trình lấy mẫu (rời rạc hoá về không gian) và lƣợng hoá thành phần giá trị mà về nguyên tắc, mắt thƣờng không phân biệt đƣợc hai điểm kề nhau. Trong quá trình này, ngƣời ta sử dụng khái niệm Picture Element mà ta quen gọi hay viết là pixel – phần tử ảnh. Nhƣ vậy một ảnh là một tập hợp các pixel. Ở đây cũng cần phân biệt khái niệm pixel hay đề cập đến trong các hệ thống đồ hoạ máy tính. Để tránh nhầm lẫn ta tạm gọi khái niệm pixel này là pixel thiết bị. Khái niệm pixel thiết bị có thể xem xét nhƣ sau: khi ta quan sát màn hình (trong chế độ đồ hoạ), màn hình không liên tục mà gồm nhiều điểm nhỏ, gọi là pixel. Mỗi pixel gồm một cặp toạ độ (x,y) và màu. Ảnh nhị phân: Tuỳ theo vùng các giá trị mức xám của điểm ảnh, mà các ảnh đƣợc phân chia ra thành ảnh màu, ảnh xám, hay ảnh nhị phân. Khi trên một ảnh chỉ có giá trị 0 hoặc 1 thì ta nói đó là một ảnh nhị phân hoặc ảnh đen trắng và các điểm ảnh của nó gọi là điểm ảnh nhị phân. 1.2.2 Nâng cao chất lƣợng ảnh bằng kỹ thuật phát hiện biên và tìm xƣơng Trong xử lý ảnh và nhận dạng ảnh, có một số loại ảnh đƣờng nét gồm các đối tƣợng (objects) là các đƣờng cong có độ dài lớn hơn nhiều so với độ dày của nó, ví dụ nhƣ là ảnh các kí tự, dấu vân tay, sơ đồ mạch điện tử, bản vẽ kỹ thuật, bản đồ v.v... Để xử lý các loại ảnh này ngƣời ta thƣờng xây dựng các hệ mô phỏng theo cách phân tích ảnh của con ngƣời gọi là hệ thống thị giác máy (Computer Vision System[10]). Có nhiều hệ thống đƣợc cài đặt theo phƣơng pháp này nhƣ hệ thống nhận dạng chữ viết bằng thiết bị quang học OCR (Optical Character Recognition ), hệ thống nhận dạng vân tay AFIS (Automated fingerprint Identification System) v.v... 8 §äc ¶nh TiÒn (Scanner/Camera) xö lý (N©ng cÊp vµ kh«i phôc) TrÝch trän ®Æc ®iÓm §èi s¸nh NhËn d¹ng Hình 1.2 Mô hình tổng quát của hệ thống nhận dạng ảnh Có nhiều phƣơng pháp trích chọn đặc điểm đƣợc biết tới nhƣ phƣơng pháp sử dụng sóng ngắn (Wavelet), sử dụng hệ số Fourier, sử dụng các mô men bất biến, sử dụng các đặc trƣng của biên nhƣ tính trơn và các điểm đặc biệt, sử dụng các đặc trƣng tôpô dựa trên phát hiện biên và tìm xƣơng của đƣờng nét ảnh Phƣơng pháp trích chọn đặc điểm sử dụng ảnh đƣợc sử dụng nhiều. Kỹ thuật phát hiện biên và tìm xƣơng là một trong nhiều ứng dụng nghiên cứu và giải quyết một số vấn đề của bài toán nêu trên trong công đoạn tiền xử lý ảnh. 1.2.2.1 Phƣơng pháp phát hiện biên. 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. Về mặt toán học ngƣời ta xem điểm biên là điểm có sự thay đổi đột ngột về mức 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. 9 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: a) Phát hiện biên trực tiếp: Phƣơng pháp này làm nổi biên dựa vào sự biến thiên mức xám của ảnh. Kỹ thuật chủ yếu dùng để phát hiện biên ở đây là dựa vào sự biến đổi theo hƣớng. Nếu lấy đạo hàm bậc nhất của ảnh ta có kỹ thuật Gradient, nếu lấy đạo hàm bậc hai của ảnh ta có kỹ thuật Laplace.  Kỹ thuật phát hiện biên Gradient: Theo định nghĩa gradient[3] 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ó: 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 Với dx là khoảng cách giữa các điểm theo hƣớng x (khoảng cách tính bằng số điểm) và tƣơng tự với dy. Việc xấp xỉ đạo hàm bậc nhất theo các hƣớng x và y đƣợc thực hiện thông qua 2 mặt nạ nhân chập tƣơng ứng sẽ cho ta các kỹ thuật phát hiện biên khác nhau( kỹ thuật Sobel, kỹ thuật Prewitt…).  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[3] đƣợc định nghĩa nhƣ sau: 10 2 f 2 f  f  2  2 dx dy 2 Ta có: 2 f  2 f ( x, y )  f ( x  1, y )  f ( x  1, y ) x 2 2 f  2 f ( x, y )  f ( x, y  1)  f ( x, y  1) y 2 Vậy: 2 f= -f(x-1,y) - f(x,y-1) + 4f(x,y) - f(x,y+1) - f(x+1,y) b) 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. 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. Về cơ bản, các thuật toán dò biên[5] 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 11 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 là điểm biên +1. 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 điểm biên. 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 (ngoài và trong), các cặp điểm này tạo nên tập nền vùng, tiếp theo 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. - 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 nền vùng lên nền vùng tiếp theo 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 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ềnvù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. 12 c) Kết luậ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. 1.2.2.2 Kỹ thuật tìm xƣơng. 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(tƣơng tự nhƣ hiện tƣợng cháy đồng cỏ) đƣợc đƣa ra bởi Blum (1976)[3] 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 1.3: 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: 13 a) Các thuật toán tìm xƣơng gián tiếp dựa trê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. 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[10] 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ự[10] 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. 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. 14  Thuật toán làm mảnh cổ điển là thuật toán song song[10], 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ỏ.  Thuật toán làm mảnh của Toumazet[8] 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  Thuật toán làm mảnh của Y.Xia[10] 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).  Thuật toán làm mảnh của N.J.Naccache và R.Shinghal[8,12]. 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.  Thuật toán làm mảnh của H.E.Lu P.S.P Wang [8,12]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ỏ.  Thuật toán làm mảnh của P.S.P Wang và Y.Y.Zhang[8,7] 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.  Thuật toán làm mảnh song song thuần tuý[8,12] 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. 15 b) Các thuật toán tìm xƣơng trực tiếp không dựa trên làm mảnh Để tách đƣợc xƣơng của đối tƣợng không dựa trên làm mảnh (lƣợc đồ Voronoi[9]) 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 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. 1.2.3 Nâng cao chất lƣợng ảnh bằng các phép toán hình thái. Hình ảnh trong thực tế khi nhận đƣợc qua các thiết bị nhƣ: Photocopy, Fax, .. ít nhiều đều bị nhiễu, thậm chí có thể biến dạng đến mức độ có thể khiến ngƣời nhận đƣợc hiểu sai về mặt ý nghĩa. Nhƣ chúng ta đã biết trong các ngành thiết kế kỹ thuật nhƣ: thiết kế máy, thiết kế xây dựng, thiết kế mạch điện v.v. dù là theo TCVN (tiêu chuẩn Việt Nam) hay ISO(International Standard Oganize), một bản vẽ đƣợc thể hiện chỉ xoay quanh một số dạng đƣờng nhƣ: đƣờng thẳng, đƣờng cong khép kín,đƣờng cong mở (có thể lồi hoặc lõm), các cung tròn, elip, đƣờng ZigZag...Các dạng đƣờng nhƣ thế đƣợc biểu diễn bằng những nét vẽ. Nét vẽ có thể là nét liền (Continuous), có thể là nét đứt (dash), có thể là nét chấm gạch nhƣ đƣờng tâm (Center), có thể là đƣờng khuất (Hide)... (Hình 1.4), Mỗi độ lớn (high) của nét vẽ (nét mảnh hoặc nét đậm), có khi thể hiện một ý nghiã khác nhau. Nhƣ trong thể hiện của đƣờng ren của một bulon chẳng hạn: đƣờng chân ren phải đƣợc thể hiện bằng một nét liền mảnh, trong khi đƣờng đỉnh của ren lại phải thể hiện bằng một nét đậm. Hoặc một đƣờng khuất, sẽ thể hiện cho hình chiếu của một đƣờng thuộc một 16 mặt đƣợc nằm ở phía sau của một mặt khác theo góc nhìn vuông góc với mặt phẳng chiếu. Trong khi đó, nét liền sử dụng để biểu diễn cho hình chiếu cuả đối tƣợng ở mặt trƣớc đó. Nét liền mảnh Nét đứt Đƣờng tâm Hình 1.4: Một số dạng biểu diễn đƣờng thẳng trong các bản vẽ kỹ thuật Do vậy, nếu nhƣ nét vẽ của một đƣờng thẳng lẽ ra là một nét vẽ liền trong khi đó đƣờng mà chúng ta nhận đƣợc lại là một nét đứt thì việc đọc các thông tin trên bản vẽ sẽ dẫn đến việc hiểu sai về mặt ý nghĩa là điều không tránh khỏi. Để giải quyết bài toán này nhƣ: nối liền những nét đứt, nối liền chữ, làm trơn biên ảnh ... các phép toán hình thái nhị phân đã ra đời, thông qua đó các phép đóng ảnh, mở ảnh cũng đƣợc định nghĩa để giải quyết bài toán nêu trên. 1.2.4 Kết luận và vấn đề nghiên cứu: Nâng cao chất lƣợng ảnh là một vấn đề quan trọng và không thể thiếu trong quá trình nhận dạng đối tƣợng. Trong thực tế, hình dạng thƣờng đƣợc chú trọng hơn kích thƣớc và con ngƣời nhận ra các đối tƣợng xung quanh chủ yếu thông qua hình dạng. Chƣơng này đã trình bày hệ thống về các phƣơng pháp nâng cao chất lƣợng ảnh theo xƣơng và biên và giới thiệu sơ lƣợc về phép toán Hình thái học. Các phép toán hình thái học là các phép toán kinh điển trong toán học đã có nhiều ứng dụng trong toán học. Và trong chƣơng kế tiếp sẽ ứng dụng các phép toán hình thái vào việc nâng cao chất lƣợng ảnh trƣớc khi lƣu trữ và đối sánh. 17 So sánh kết quả giữa các thuật toán, sử dụng phép toán hình thái cho ảnh tìm biên khá rõ và nét tốt. Trong hình 1.5a dƣới đây là ảnh gốc, hình 1.5b là ảnh biên thu đƣợc qua phát hiện biên bằng Sobel, hình 1.5c qua Laplace. Hình 1.5d là ảnh biên kết quả 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 trên với ngƣỡng tách  = 128 a) Ảnh gốc đa cấp xám c)Ảnh biên thu đƣợc qua Laplace b)Ảnh biên thu đƣợc qua Sobel d) Ảnh kết quả Hình 1.5. So sánh phát hiện biên bởi các thuật toán