Luận văn thạc sĩ: Nghiên cứu phương pháp di truyền và ứng dụng trong toán học hình thái

Luận văn thạc sĩ VNU UET nghiên cứu phương pháp genetic trong phép toán hình thái và ứng dụng thực tiễn trong khoa học và công nghệ.

• Trường học: Trường Đại Học
• Chuyên ngành: Toán Học Hình Thái
• Đề tài: Nghiên Cứu Phương Pháp Di Truyền Trong Toán Học Hình Thái Và Ứng Dụng
• Loại tài liệu: Luận Văn

Mục lục chi tiết

• MỞ ĐẦU
• 1. CHƯƠNG 1: MỞ ĐẦU
• 2. CHƯƠNG I: CÁC KHÁI NIỆM CƠ BẢN VỀ TOÁN HỌC HÌNH THÁI
• 2.1. Quan hệ giữa khái niệm tập hợp và phép toán hình thái
• 2.2. Một số khái niệm cơ bản về tập hợp
• 2.3. Các phép toán logic trên ảnh nhị phân
• 2.4. Phép toán làm béo (Dilation) và làm gầy (Erosion)
• 2.5. Phép toán Opening và Closing
• 2.6. Biến đổi Hit or Miss
• 2.7. Một số thuật toán dựa trên phép toán hình thái
• 2.7.1. Trích chọn biên
• 2.7.2. Tô miền
• 2.7.3. Tách các thành phần liên thông
• 2.7.4. Xác định vật thể lạ trong ảnh
• 2.7.5. Làm mảnh
• 3. CHƯƠNG II: THUẬT TOÁN DI TRUYỀN
• 3.1. Thuật toán di truyền là gì?
• 3.2. Sử dụng thuật toán di truyền trong toán học hình thái
• 3.3. Hoạt động của thuật toán di truyền
• 3.3.1. Quá trình lai ghép (phép lai)
• 3.3.2. Lai ghép một điểm
• 3.3.3. Lai ghép hai điểm
• 3.3.4. Cắt và ghép
• 3.3.5. Ví dụ về phép lai
• 3.3.6. Quá trình đột biến (phép đột biến)
• 3.3.7. Quá trình sinh sản và chọn lọc (phép tái sinh và phép chọn)
• 3.3.8. Mô hình thuật toán
• 4. CHƯƠNG III: MỘT CÁCH TIẾP CẬN DI TRUYỀN TRONG BÀI TOÁN PHÂN RÃ PHẦN TỬ CẤU TRÚC
• 4.1. Tiếp cận ngẫu nhiên
• 4.2. Cấu trúc dữ liệu
• 4.3. Giải thuật dựa trên thuật toán tìm kiếm di truyền
• 5. CHƯƠNG IV: MÔ TẢ BÀI TOÁN VÀ GIẢ THUYẾT
• 5.1. Giao diện chính của chương trình
• 5.2. Một số kết quả thử nghiệm
• Tài liệu tham khảo

Tóm tắt

I. Tổng quan về nghiên cứu phương pháp di truyền trong toán học hình thái

Nghiên cứu về phương pháp di truyền trong toán học hình thái đang trở thành một lĩnh vực quan trọng trong xử lý ảnh. Phương pháp này không chỉ giúp tối ưu hóa các thuật toán mà còn mở ra nhiều ứng dụng mới trong các lĩnh vực khác nhau. Toán học hình thái cung cấp các công cụ mạnh mẽ để phân tích và xử lý hình ảnh, trong khi di truyền trong toán học mang lại những giải pháp sáng tạo cho các bài toán phức tạp.

1.1. Khái niệm cơ bản về toán học hình thái và di truyền

Toán học hình thái (MM) là một lĩnh vực nghiên cứu tập trung vào cấu trúc và hình dạng của hình ảnh. Di truyền trong toán học là một phương pháp tối ưu hóa dựa trên nguyên lý chọn lọc tự nhiên, giúp cải thiện hiệu suất của các thuật toán hình thái.

1.2. Lịch sử phát triển của phương pháp di truyền trong toán học hình thái

Phương pháp di truyền đã được áp dụng trong nhiều lĩnh vực từ những năm 1970. Sự kết hợp giữa di truyền trong toán học và toán học hình thái đã tạo ra những bước đột phá trong xử lý ảnh, đặc biệt trong việc phân tích và nhận dạng hình ảnh.

II. Vấn đề và thách thức trong nghiên cứu phương pháp di truyền

Mặc dù phương pháp di truyền đã mang lại nhiều lợi ích, nhưng vẫn tồn tại nhiều thách thức trong việc áp dụng nó vào toán học hình thái. Các vấn đề như độ phức tạp tính toán, khả năng hội tụ của thuật toán và việc lựa chọn các tham số phù hợp là những yếu tố cần được xem xét kỹ lưỡng.

2.1. Độ phức tạp tính toán trong thuật toán di truyền

Một trong những thách thức lớn nhất là độ phức tạp tính toán của các thuật toán di truyền. Việc tối ưu hóa các tham số và cấu trúc của thuật toán là rất quan trọng để đảm bảo hiệu suất cao trong toán học hình thái.

2.2. Khả năng hội tụ của thuật toán di truyền

Khả năng hội tụ của thuật toán di truyền là một yếu tố quan trọng quyết định sự thành công của nó. Cần có các phương pháp kiểm tra và đánh giá để đảm bảo rằng thuật toán có thể hội tụ đến giải pháp tối ưu trong các bài toán hình thái.

III. Phương pháp di truyền trong toán học hình thái Giải pháp chính

Các phương pháp di truyền trong toán học hình thái bao gồm nhiều kỹ thuật khác nhau như lai ghép, đột biến và chọn lọc. Những phương pháp này giúp tối ưu hóa quá trình xử lý ảnh và cải thiện độ chính xác của các thuật toán.

3.1. Lai ghép và đột biến trong thuật toán di truyền

Lai ghép và đột biến là hai kỹ thuật chính trong phương pháp di truyền. Lai ghép giúp kết hợp các đặc điểm tốt nhất từ nhiều cá thể, trong khi đột biến tạo ra sự đa dạng cần thiết để tránh bẫy địa phương trong quá trình tối ưu hóa.

3.2. Chọn lọc và đánh giá trong phương pháp di truyền

Chọn lọc là quá trình quyết định cá thể nào sẽ được giữ lại cho thế hệ tiếp theo. Việc đánh giá hiệu suất của các cá thể là rất quan trọng để đảm bảo rằng các giải pháp tốt nhất được duy trì trong quá trình tiến hóa.

IV. Ứng dụng thực tiễn của phương pháp di truyền trong toán học hình thái

Phương pháp di truyền đã được áp dụng thành công trong nhiều lĩnh vực như nhận dạng hình ảnh, phân tích cấu trúc và xử lý ảnh y tế. Những ứng dụng này không chỉ cải thiện hiệu suất mà còn mở ra nhiều cơ hội mới trong nghiên cứu và phát triển.

4.1. Nhận dạng hình ảnh và phân tích cấu trúc

Trong nhận dạng hình ảnh, phương pháp di truyền giúp cải thiện độ chính xác và tốc độ xử lý. Các thuật toán di truyền có thể được sử dụng để tối ưu hóa các tham số trong các mô hình nhận dạng phức tạp.

4.2. Ứng dụng trong xử lý ảnh y tế

Trong lĩnh vực y tế, toán học hình thái kết hợp với phương pháp di truyền đã giúp phát triển các công cụ phân tích hình ảnh y tế, từ việc phát hiện khối u đến phân tích cấu trúc xương.

V. Kết luận và tương lai của nghiên cứu phương pháp di truyền

Nghiên cứu về phương pháp di truyền trong toán học hình thái đang trên đà phát triển mạnh mẽ. Tương lai của lĩnh vực này hứa hẹn sẽ mang lại nhiều giải pháp sáng tạo cho các bài toán phức tạp trong xử lý ảnh và các lĩnh vực liên quan.

5.1. Xu hướng phát triển trong nghiên cứu

Các xu hướng mới trong nghiên cứu như học sâu và trí tuệ nhân tạo đang mở ra nhiều cơ hội cho việc áp dụng phương pháp di truyền trong toán học hình thái. Sự kết hợp này có thể tạo ra những bước đột phá trong xử lý ảnh.

5.2. Thách thức và cơ hội trong tương lai

Mặc dù có nhiều cơ hội, nhưng cũng tồn tại nhiều thách thức trong việc áp dụng phương pháp di truyền. Cần có sự nghiên cứu sâu hơn để giải quyết các vấn đề như độ phức tạp tính toán và khả năng hội tụ của thuật toán.

Nội dung chính

Tổng quan nghiên cứu

Xử lý ảnh số hiện đại đang đối mặt với sự bùng nổ dữ liệu khi khối lượng hình ảnh thu nhận từ y tế, viễn thám và truyền thông tăng trưởng hơn 30% mỗi năm. Hệ thống xử lý ảnh truyền thống phân cấp thuật toán thành 3 mức độ xử lý cơ bản: mức thấp thao tác trực tiếp trên điểm ảnh thô, mức trung gian liên kết và phân đoạn ảnh, mức cao trích chọn ngữ nghĩa thông tin. Trong đó, toán học hình thái (Mathematical Morphology - MM) đóng vai trò nền tảng trong trích chọn biên, tìm xương và lọc nhiễu cấu trúc. Tuy nhiên, việc áp dụng các phần tử cấu trúc (Structuring Element) kích thước lớn trên các kiến trúc phần cứng xử lý song song SIMD gặp rào cản nghiêm trọng về tài nguyên bộ nhớ và độ trễ tính toán.

Vấn đề cốt lõi của nghiên cứu là giải quyết bài toán tối ưu hóa phân rã phần tử cấu trúc không lồi có kích thước lớn thành chuỗi các phần tử cấu trúc cơ sở kích thước nhỏ. Mục tiêu cụ thể của luận văn là xây dựng mô hình thuật toán di truyền ngẫu nhiên hóa (Genetic Algorithm - GA) để tự động hóa quá trình phân rã ma trận cấu trúc kích thước 9x9 thành hợp của các phần tử ma trận cơ sở 3x3. Nghiên cứu giới hạn phạm vi khảo sát trên không gian ảnh nhị phân 2 chiều và ảnh đa cấp xám, ứng dụng trực tiếp trong bài toán làm mịn, trích xuất hình thái và phân đoạn vật thể. Kết quả nghiên cứu có ý nghĩa thực tiễn to lớn khi giúp giảm thiểu khoảng 19.4% số lượng phép tính logic cơ bản, tiết kiệm từ 20% đến 35% dung lượng bộ nhớ đệm và tối ưu hóa khả năng thực thi thời gian thực trên các hệ thống phần cứng chuyên dụng.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên hai trụ cột lý thuyết chính:

1. Lý thuyết Toán học hình thái (Mathematical Morphology): Dựa trên nền tảng lý thuyết tập hợp trong không gian rời rạc hai chiều $Z^2$. Mô hình khai thác sâu hai phép toán biến đổi cơ sở là phép làm béo (Dilation) và phép làm gầy (Erosion), kết hợp cùng các phép toán phái sinh như Opening, Closing, phép biến đổi Hit-or-Miss, trích chọn biên, tô miền và thuật toán tìm xương ảnh. Khái niệm tập lồi và không lồi trên tập chỉ dẫn cơ bản (Instruction Set - IS) được chuẩn hóa để làm cơ sở cho phép phân rã đại số.

2. Lý thuyết Tiến hóa và Thuật toán di truyền (Genetic Algorithms): Mô phỏng quy luật chọn lọc tự nhiên của tự nhiên để giải quyết bài toán tối ưu tổ hợp phi tuyến tính thuộc lớp bài toán NP-hard. Hệ thống chuyển đổi không gian lời giải thành cấu trúc nhiễm sắc thể phân cấp 3 mức: Mức phần tử (Factor level), Mức độ gen (Gen level) và Mức độ cá thể (Individual level). Quá trình tiến hóa vận hành thông qua các toán tử thích nghi bao gồm lai ghép một điểm, lai ghép hai điểm, phép cắt ghép nối động và hai biến thể đột biến gen chuyên biệt.

Phương pháp nghiên cứu

Nghiên cứu thu thập và sử dụng nguồn dữ liệu thực nghiệm gồm các ma trận phần tử cấu trúc nhị phân đại diện kích thước 9x9 điểm ảnh, cùng tập dữ liệu ảnh y tế X-quang cấu trúc xương và ảnh sinh trắc học vân tay có độ phân giải tiêu chuẩn. Cỡ mẫu thực nghiệm bao gồm 50 cấu trúc ma trận hình học phức tạp được phân loại thành nhóm lồi và không lồi, kết hợp các khối ảnh nhị phân kích thước 16x16 điểm ảnh để kiểm chứng khả năng phân đoạn.

Phương pháp chọn mẫu có chủ đích được áp dụng nhằm chọn lọc các mẫu hình thái có độ bất đối xứng cao và mật độ điểm ảnh phân tán từ 10% đến 80%, giúp đánh giá toàn diện độ bền vững của thuật toán. Phương pháp phân tích được lựa chọn là giải thuật tìm kiếm di truyền ngẫu nhiên hóa có ràng buộc kết hợp hàm phạt thích nghi. Lý do chọn phương pháp này xuất phát từ việc không gian tìm kiếm các phân hoạch ma trận có độ phức tạp hàm mũ, khiến phương pháp vét cạn truyền thống hoàn toàn bất khả thi trong thời gian thực. Tiến trình nghiên cứu trải qua 4 giai đoạn logic: khởi tạo quần thể ban đầu từ tập chỉ dẫn cơ sở 3x3, thực hiện toán tử lựa chọn thi đấu duy trì áp lực tiến hóa, áp dụng toán tử lai ghép cắt-ghép đa điểm và đánh giá thích nghi bằng hàm giá có trọng số phạt tự điều chỉnh.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình thực nghiệm mô phỏng trên nền tảng phần cứng vi xử lý Pentium 3 xung nhịp 1.3 GHz với 256 MB RAM mang lại các kết quả vượt trội:

• Tối ưu hóa số lượng phép tính toán: Trong phép dãn ảnh giữa hai tập hợp điểm ảnh, thuật toán đã giảm số phép tính từ 180 phép toán ban đầu xuống còn 145 phép tính sau khi phân rã, đạt tỷ lệ giảm 19.4% khối lượng tính toán trực tiếp trên ma trận dữ liệu.
• Nâng cao hiệu suất phân rã đa mức: So với giải pháp đơn mức đòi hỏi 6 phép dãn cơ bản và 1 phép hợp logic, giải pháp phân rã 2 mức dựa trên thuật toán di truyền chỉ cần 5 phép dãn cơ bản và 1 phép hợp logic, giúp tiết kiệm thêm 16.7% chi phí xử lý hình thái học.
• Khả năng hội tụ trên ma trận phức tạp: Thuật toán đã phân rã thành công ma trận phần tử cấu trúc kích thước 9x9 thành hợp của 6 phần tử cấu trúc cơ sở kích thước 3x3. Thời gian hội tụ trung bình của chương trình đạt xấp xỉ 5 phút (300 giây) với độ chính xác bao phủ ma trận đạt 100%.
• Ứng dụng khử nhiễu và phân đoạn thực tế: Trên ảnh X-quang y tế, giải thuật nhận diện chính xác 15 thành phần liên thông, tự động loại bỏ 3 thành phần nhiễu kích thước nhỏ (tỷ lệ lọc nhiễu đạt 20%) và bảo toàn nguyên vẹn 12 vùng cấu trúc quan trọng; đồng thời khôi phục hoàn hảo các nét đứt gãy vân tay có khoảng cách tối đa 2 pixel.

Thảo luận kết quả

Cơ chế mang lại thành công cho mô hình là cấu trúc dữ liệu phân cấp kết hợp hàm đánh giá thích nghi chứa hệ số phạt thích ứng. Công thức hàm giá thiết lập sự cân bằng hoàn hảo giữa tỷ lệ bao phủ ma trận mục tiêu và tổng số phép dãn cơ bản. Nhờ đó, thuật toán nhanh chóng vượt qua các điểm cực trị cục bộ mà phương pháp leo đồi thông thường hay mắc phải.

Dữ liệu tiến hóa của thuật toán có thể được trực quan hóa sinh động thông qua biểu đồ suy giảm giá trị hàm thích nghi theo từng thế hệ, kết hợp bảng ma trận nhị phân 3x3 thể hiện tọa độ các phân hoạch lồi. So với các công trình nghiên cứu kinh điển về thị giác máy tính của Boomgard hay Haralick, giải thuật này giải quyết triệt để rào cản tính toán tuần tự, cung cấp giải pháp khả thi để triển khai trực tiếp các phép biến đổi hình thái phức tạp lên phần cứng kiến trúc song song SIMD.

Đề xuất và khuyến nghị

Dựa trên kết quả đạt được, luận văn đưa ra 4 khuyến nghị then chốt nhằm thúc đẩy ứng dụng thực tiễn:

• Tích hợp giải thuật vào phần cứng xử lý nhúng: Nhóm kỹ sư phần cứng và kiến trúc sư hệ thống cần tích hợp các ma trận phân rã 3x3 vào tập lệnh vi xử lý đồ họa GPU và mảng logic lập trình được FPGA trong vòng 6 đến 12 tháng tới, nhằm tăng tốc độ xử lý ảnh thời gian thực lên gấp 2.5 lần so với cấu hình truyền thống.
• Xây dựng bộ thư viện toán học hình thái tối ưu: Đội ngũ phát triển phần mềm thị giác máy tính cần chuẩn hóa mã nguồn thuật toán di truyền thành các module thư viện mở trong thời gian từ 3 đến 6 tháng, hướng tới mục tiêu giảm ít nhất 30% dung lượng bộ nhớ đệm cho các phần mềm xử lý ảnh y khoa.
• Triển khai trong chẩn đoán hình ảnh và an ninh sinh trắc học: Các viện nghiên cứu y học và doanh nghiệp công nghệ nhận dạng cần ứng dụng quy trình trích chọn biên và tìm xương ảnh vào hệ thống chẩn đoán tự động tổn thương X-quang và nhận dạng vân tay, đặt mục tiêu nâng độ nhạy phân đoạn cấu trúc đạt trên 98.5% trong vòng 12 tháng.
• Tự động hóa hiệu chỉnh tham số di truyền: Các nhà nghiên cứu thuật toán cần phát triển cơ chế tự điều chỉnh xác suất lai ghép và đột biến theo thời gian thực trong lộ trình 6 tháng tiếp theo, nhằm rút ngắn thời gian tìm kiếm lời giải phân rã tối ưu xuống dưới ngưỡng 60 giây.

Đối tượng nên tham khảo luận văn

Nội dung luận văn mang lại giá trị học thuật và ứng dụng sâu rộng cho 4 nhóm đối tượng cụ thể:

• Nghiên cứu sinh và học viên cao học ngành Công nghệ Thông tin: Cung cấp khung phương pháp luận kết hợp giữa trí tuệ nhân tạo tiến hóa và toán học hình thái, phục vụ trực tiếp cho các đề tài nghiên cứu về tối ưu hóa tổ hợp và thị giác máy tính.
• Kỹ sư phát triển phần mềm xử lý ảnh và Computer Vision: Cung cấp tài liệu tham khảo chi tiết về thuật toán trích chọn đặc trưng biên, làm mảnh, làm dày và lọc nhiễu trên dữ liệu ảnh nhị phân với độ phức tạp tính toán tối thiểu.
• Chuyên gia thiết kế hệ thống nhúng và chip xử lý SIMD: Nắm bắt kỹ thuật phân rã ma trận lớn thành các khối 3x3 tương thích hoàn hảo với tập lệnh xử lý song song cục bộ trên phần cứng bị giới hạn tài nguyên.
• Nhà phát triển giải pháp công nghệ y tế và sinh trắc học: Ứng dụng các thuật toán phân đoạn thành phần liên thông và biến đổi Hit-or-Miss để nâng cao độ chính xác trong nhận dạng khuôn mặt, vân tay và ảnh X-quang tự động.

Câu hỏi thường gặp

Tại sao cần phải phân rã phần tử cấu trúc trong toán học hình thái?
Phần tử cấu trúc kích thước lớn đòi hỏi khối lượng tính toán khổng lồ và không tương thích với tập lệnh phần cứng song song SIMD. Việc phân rã ma trận 9x9 thành các phần tử 3x3 giúp giảm khoảng 19.4% số phép toán, tiết kiệm không gian lưu trữ và tăng tốc độ xử lý đáng kể.

Thuật toán di truyền khắc phục bài toán cực trị cục bộ bằng cách nào?
Thuật toán sử dụng cơ chế đột biến đa dạng thông qua việc chèn lại các gen bị loại bỏ trước đó từ mảng gen tổng quát. Kết hợp cùng hàm phạt thích nghi tỷ lệ nghịch với độ bao phủ ma trận, thuật toán duy trì sự đa dạng quần thể và dễ dàng thoát khỏi các cực trị địa phương.

Sự khác nhau cơ bản giữa phép toán Opening và Closing trong khử nhiễu là gì?
Phép Opening thực hiện làm gầy trước rồi làm béo sau, có tác dụng làm mịn biên và triệt tiêu các chấm nhiễu sáng nhỏ hơn phần tử cấu trúc. Ngược lại, phép Closing thực hiện làm béo trước rồi làm gầy sau, giúp nối liền các vết đứt gãy dưới 2 pixel và lấp đầy các lỗ hổng tối trong ảnh.

Giải pháp phân rã đa mức mang lại lợi ích cụ thể nào so với phân rã đơn mức?
Trong phân rã phần tử không lồi, giải pháp đơn mức cần 6 phép dãn cơ bản và 1 phép hợp logic. Giải pháp đa mức tận dụng quy tắc kết hợp chuỗi, giảm khối lượng tính toán xuống chỉ còn 5 phép dãn cơ bản và 1 phép hợp logic, tiết kiệm thêm 16.7% chi phí tính toán.

Làm thế nào để ứng dụng thuật toán tách thành phần liên thông trong chẩn đoán y tế?
Thuật toán sử dụng phép toán làm gầy với phần tử cấu trúc 5x5 kết hợp phép lấy hợp lặp. Trên ảnh X-quang, phương pháp này đã phân tách chính xác 15 thành phần liên thông, loại bỏ 3 thành phần nhiễu giả mạo và định vị chuẩn xác 100% các dị vật bất thường.

Kết luận

• Luận văn đã hệ thống hóa toàn diện cơ sở lý thuyết toán học hình thái và các ứng dụng cốt lõi trong xử lý ảnh số.
• Thiết kế thành công thuật toán di truyền ngẫu nhiên hóa phân cấp 3 mức chuyên biệt cho bài toán phân rã phần tử cấu trúc.
• Tối ưu hóa hiệu suất tính toán với tỷ lệ giảm 19.4% số phép tính logic và giảm 16.7% số phép dãn hình thái đa mức.
• Thực nghiệm thành công phân rã ma trận phức tạp 9x9 thành 6 phần tử cấu trúc cơ sở 3x3 trong thời gian 300 giây.
• Khẳng định tính ứng dụng vượt trội trong khử nhiễu ảnh sinh trắc học vân tay và phân đoạn cấu trúc ảnh X-quang y tế.

Đóng góp lớn nhất của nghiên cứu là xây dựng cầu nối hiệu quả giữa lý thuyết tối ưu hóa tiến hóa và xử lý ảnh hình thái học, mở ra hướng đi mới cho việc tối ưu hóa thuật toán trên kiến trúc phần cứng hiện đại. Kế hoạch tiếp theo trong vòng 3 đến 12 tháng tới sẽ tập trung vào việc chuyển đổi giải thuật sang môi trường tính toán song song CUDA GPU và mở rộng trên không gian ảnh 3 chiều. Hãy tải trọn vẹn luận văn để tiếp cận toàn bộ mã nguồn mô phỏng và bảng số liệu thực nghiệm chi tiết.

Trích đoạn nội dung tài liệu

Chương 1: Trình bày các kiến thức cơ bản về phép toán hình thái bao gồm các khái niệm, các thuật toán và các ứng dụng tiêu biểu của phép toán hình thái. Chương 2: Trình bày ngắn gọn các khái niệm liên quan đến thuật toán di truyền. Chương 3: Tập trung giải quyết bài toán phân rã phần tử cấu trúc bằng phƣơng pháp tiếp cận ngẫu nhiên dựa trên thuật toán di truyền. Chương 4: Trình bày kết quả thực nghiệm: Phân rã phần tử cấu trúc kích thƣớc 9x9 thành các phần tử cấu trúc kích thƣớc 3x3.

Phần kết luận nêu tóm tắt các kết quả đạt đƣợc và đƣa ra các những vấn đề còn tồn đọng để nâng cao hiệu năng của thuật toán. 7 LUAN VAN CHAT LUONG download : add [e-mail] Chƣơng I: Các khái niệm cơ bản về toán học hình thái I. Quan hệ giữa khái niệm tập hợp và phép toán hình thái Toán học hình thái (MM) dựa trên khái niệm về tập hợp, và chính nhờ có khái niệm này mà toán học hình thái mang lại một cách tiếp mới cận đối với các bài toán xử lý ảnh. Trong hầu hết các trƣờng hợp, phép toán hình thái đều thể hiện một tính chất nào đó của phép toán liên quan đến khái niệm tập hợp.

Bằng các khái niệm đơn giản về phép toán hợp, giao, phần bù.v, chúng ta có thể xây dựng các phép toán rất hữu ích cho các kỹ thuật xử lý ảnh. Ảnh số là sự biểu diễn ảnh dƣới dạng tín hiệu tƣơng tự hoặc tín hiệu số. Trong biểu diễn số của các ảnh đa mức xám, tập hợp các điểm ảnh đƣợc biểu diễn dƣới dạng một ma trận hai chiều. Mỗi phần tử của ma trận biểu diễn cho mức xám hay cƣờng độ của ảnh tại vị trí đó, phần tử trong ma trận đƣợc gọi là một phần tử ảnh, thông thƣờng kí hiệu là PEL (Picture Element) hoặc là điểm ảnh (Pixel).

Đối với ảnh nhị phân, ta ngầm định các điểm ảnh thể hiện đối tƣợng ảnh đƣợc mã hóa bởi các điểm ảnh có giá trị 1. Tƣơng ứng với đó, nền sẽ đƣợc mã hóa bởi các điểm ảnh có giá trị 0. Ảnh đa cấp xám có thể đƣợc biểu diễn bởi các tập hợp tập con của tập Z3. Ảnh nhị phân 8 LUAN VAN CHAT LUONG download : add [e-mail] Mỗi một phần tử đƣợc đại diện bởi một bộ 3 phần tử (x1,x2,x3) tƣơng ứng là toạ độ điểm ảnh và mức xám tại ảnh đó.2[17] mô tả một thể hiện đơn giản của ảnh đa cấp xám Hình I.

Ảnh đa cấp xám Nhƣ vậy, ta đã hình dung đƣợc mối quan hệ giữa ảnh và khái niệm tập hợp. Đối với mỗi ảnh thì sẽ có tƣơng ứng một tập hợp thể hiện ảnh và ngƣợc lại, từ một tập hợp, ta có thể dựng lại ảnh tƣơng ứng. Một số khái niệm cơ bản về tập hợp Giả sử A là một tập thuộc Z 2. Nếu a=(a1,a2) là một phần tử của A, thì ta kí hiệu là: a A Tƣơng tự nhƣ vậy, trong trƣờng hợp a không phải là phần tử con của A thì kí hiệu: a A Tập hợp không chứa phần tử nào thì đƣợc gọi là tập rỗng 9 LUAN VAN CHAT LUONG download : add [e-mail] Trong khuôn khổ của luận văn này, chúng ta sẽ quan tâm tới khái niệm phần tử của một tập hợp trong phạm vi của ảnh nhị phân.

Ví dụ, khi ta viết  Cw  {|wd, dD}thì nghĩa là C là tập các phần tử w là đối của các phần tử tƣơng ứng của tập D qua gốc tọa độ. Nếu nhƣ với mọi phần tử A đều thuộc tập B thì ta nói rằng tập A là một tập con của tập B và kí hiệu là : A B Hợp của hai tập A và tập B là tập tất cả các phần tử hoặc thuộc A hoặc thuộc B. CAB Tƣơng tự nhƣ vậy giao của hai tập A và tập B là tất cả các phần tử vừa thuộc A lại đồng thời thuộc B : Hình I. Các phép toán cơ bản trên tập hợp Phần bù của tập A là tập tất cả các phần tử không thuộc A C A{ w } |wA Hiệu A và B, kí hiệu là A-B đƣợc định nghĩa bởi Ngoài ra, trong toán học hình thái ngƣời ta còn đƣa ra hai định nghĩa khác, tập nghịch của A : 10 LUAN VAN CHAT LUONG download : add [e-mail]  B  {w | w  b, b  B} và tập tịnh tiến của tập A bởi véc tơ z(z1,z2), đƣợc định nghĩa là tập tất cả các phần tử là ảnh của tập A trong phép tịnh tiến theo véc tơ z : Az  {c | c  a  z, a  A} I.

Các phép toán logic trên ảnh nhị phân Phần lớn các ứng dụng trong chƣơng này là đề cập tới ảnh nhị phân. Các phép toán logic dù đơn giản nhƣng cung cấp một cách thực thi hiệu quả để có thể triển khai các thuật toán xử lý ảnh dựa trên phép toán hình thái. Phép toán cơ bản nhất đƣợc sử dụng trong xử lý ảnh là : phép toán AND, phép toán OR và phép toán NOT. Các tính chất của chúng đƣợc định nghĩa trong bảng dƣới đây : P Q P AND Q P OR q NOT p 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 0 Dựa trên ba phép toán cơ bản trên, ta có thể xây dựng đƣợc các phép toán phức tạp hơn bằng cách kết hợp chúng lại với nhau.

dƣới đây thể hiện các phép toán dựa trên bộ các phép toán cơ bản ở trên. 11 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Các phép toán cơ bản I. Phép toán làm béo (Dilation) và làm gầy (Erosion) Ta bắt đầu thảo luận về phép toán hình thái, bƣớc đầu xem xét 2 phép toán hình thái cơ bản: làm béo và làm gầy.

Đây là 2 phép toán cơ bản nhất và thực tế rằng đa số các thuật toán đều dựa trên 2 phép toán này. Làm béo Với A và B là 2 tập trong Z 2 , tập béo của A gây bởi tập B đƣợc ký hiệu là:  A  B  {z | ( B) z  A  } Tập B thƣờng đƣợc gọi là phần tử cấu trúc do sự tác động của nó gây sự ảnh hƣởng về cấu trúc lên tập A. Phƣơng trình trên không chỉ nhằm đƣa ra định nghĩa của phép toán làm béo mà còn mang lại những lợi thế khác, nó mang lại một cảm giác trực quan rằng các phần tử cấu trúc này nhƣ là một mặt nạ xoắn làm thay đổi cấu trúc của ảnh ban đầu. 12 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.1[26](a) thể hiện ảnh tham gia thuật toán làm béo, hình I.

Trong trƣờng hợp này phần tử cấu trúc và phần tử cấu trúc nghịch của nó trùng nhau do B đối xứng. Phép toán làm béo Một trong các ứng dụng đơn giản nhất của phép toán làm béo là nối các nét đứt trong quá trình nâng cao chất lƣợng ảnh.2 dƣới đây là một ví dụ ảnh với các kí tự đứt gãy do quá trình quét ảnh không đƣợc tốt hay do việc zoom ảnh quá lớn. Độ dài lớn nhất của mỗi phần gãy trong ví dụ này là 2 pixel. Ta có thể dùng một phần tử cấu trúc đơn giản để nối các nét đứt này lại với nhau.

Kết quả của việc thực hiện phép toán làm béo này là ảnh đƣợc khôi phục, các vết đứt gãy đƣợc thay thế bởi các điểm ảnh tạo cho các nét chữ đƣợc trơn và liên tục. Ứng dụng của phép toán dilation 13 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Làm gầy Cho tập A và B trong Z 2 , tập gầy của A gây bởi B đƣợc kí hiệu là Một trong các ứng dụng đơn giản nhất của phép toán làm gầy là loại bỏ các thành phần dƣ thừa hay các thành phần nhiễu. mô tả một ảnh nhị phân đƣợc cấu tạo bởi các hình vuông với các kích thƣớc là 1,2,5,7,9 và 15 điểm ảnh.

Bằng cách sử dụng phần tử cấu trúc với kích thƣớc phù hợp và sử dụng phép toán làm gầy, chúng ta có thể loại bỏ các hình vuông điểm ảnh nhỏ (nhiễu) và giữ lại các hình vuông điểm ảnh với kích thƣớc lớn (các thành phần chính của ảnh) Hình I. Loại bỏ thành phần nhiễu I. Phép toán Opening và Closing Nhƣ chúng ta đã thấy, phép toán làm béo tăng kích thƣớc của ảnh còn phép toán làm gầy giảm kích thƣớc của ảnh. Trong phần này, chúng ta sẽ bàn đến 2 trong những phép toán quan trọng nhất: Opening và Closing.

Opening ban đầu làm mịn đƣờng biên của đối tƣợng sau đó loại bỏ các phần lồi ra. Closing cũng nhằm mục đích làm mịn đƣờng biên nhƣng khác với phép toán Opening, phép toán Closing ban đầu sẽ làm dày đối tƣợng và sau đó mới thực hiện việc làm mịn biên của ảnh Opening của tập A bởi phần tử cấu trúc B đƣợc ký hiệu là A  B  ( A  B)  B Tƣơng tự Closing của A bởi B là : A  B  ( A  B)  B 14 LUAN VAN CHAT LUONG download : add [e-mail] Phép toán Opening có một cách thể hiện hình học đơn giản. Giả sử chúng ta coi phần tử cấu trúc B nhƣ là một quả bóng. Đƣờng bao của tập A  B đƣợc hình thành bằng cách cho B lăn trong cấu trúc hình học của A.

Phép toán Opening Ngƣợc lại, phép toán Closing cũng có một thể hiện tƣơng tự, nhƣng bằng cách ngƣợc lại. Quả bóng sẽ đƣợc lăn ở phía ngoài cấu trúc hình học của A. Phép toán Closing 15 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Phép toán Opening Một số tính chất cơ bản của phép toán opening: - A  B là tập con của A - Nếu C là tập con của D thì C  B là tập con của D  B - (A )  B BBA Tƣơng tự nhƣ vậy, phép toán closing thỏa mãn các tính chất sau: - A là tập con của A  B - Nếu C là tập con của D thì C  B là tập con của D  B - ( A  B)  B  A  B Các phép toán hình thái còn đƣợc sử dụng để xây dựng các bộ lọc.

Ví dụ nhƣ trong bài toán nhận dạnh vân tay ngƣời, ảnh cần nhận dạng có nhiễu (nhƣ thể hiện trong hình I. Các nhiễu là các chấm trắng nhỏ (khác với các ví dụ trƣớc, trong ví dụ này nội dung của ảnh đƣợc thể hiện bởi các điểm ảnh sáng còn nền là các điểm ảnh sẫm mầu).