ngo_li2507
New Member
Download Luận văn Tìm hiểu phép toán hình thái, phương pháp di truyền và ứng dụng
MỤC LỤC
DANH MỤC CÁC HÌNH VẼ
LỜI NÓI ĐẦU 5
Chương I. Giới thiệu chung về xử lý ảnh và phương pháp nâng
cao chất lượng hình ảnh7
1. Giới thiệu chung về xử lý ảnh 7
2. Giới thiệu ảnh nhị phân 9
2.1. Một số khái niệm 9
2.2. Đặt bài toán nâng cao chất lượng ảnh bằng các phép toán hình thái11
2.3. Đặt bài toán nâng cao chất lượng ảnh bằng kỹ thuật tìm xương và làm mảnh13
3. Khái quát về phương pháp nâng cao chất lưởng hình ảnh 14
Chương II: Các khái niệm cơ bản về toán học hình thái 16
1. Quan hệ giữa khái niệm tập hợp và phép toán hình thái 16
1.1. Một số khái niệm cơ bản về tập hợp 17
1.2. Các phép toán logic trên ảnh nhị phân 20
2. Phép toán làm béo (Dilation) và làm gầy (Erosion) 21
2.1. Làm béo 21
2.2. Làm gầy 23
2.3. Phép toán Opening và Closing 23
2.4. Biến đổi Hit or Miss 27
3. Một số thuật toán dựa trên phép toán hình thái 28
3.1. Trích chọn biên 28
3.2. Tô miền 30
3.3. Tách các thành phần liên thông 31
3.4. Làm mảnh 33
3.5. Làm dầy 34
3.6. Tìm xương của ảnh 35
Chương III: Thuật toán di truyền 37
1. Thuật toán di truyền là gì? 37
2. Sử dụng thuật toán di truyền trong toán học hình thái 37
3. Hoạt động của thuật toán di truyền 38
3.1. Quá trình lai ghép (phép lai) 41
3.2. Quá trình đột biến (phép đột biến) 43
3.3. Quá trình sinh sản và chọn lọc (phép tái sinh và phép chọn) 44
4. Mô hình thuật toán 44
Chương IV: 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 46
1. Tiếp cận ngẫu nhiên 50
2. Cấu trúc dữ liệu 51
3. Giải thuật dựa trên thuật toán tìm kiếm di truyền 55
Chương V: Thực nghiệm 61
1. Mô tả bài toán và giả thuyết 61
2. Giao diện chính của chương trình 61
3. Một số kết quả thử nghiệm 62
Chương VI: Kết luận 67
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
-
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 B A B
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
Trang 26
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
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ạng vân tay người, ảnh cần nhận dạng có nhiễu
(như thể hiện trong hình II.2.7(a). Các nhiễu là các chấm trắng nhỏ (khác với
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). Mục tiêu của quá trình tiền xử lý ảnh
trước khi nhận dạng là việc lọc các thành phần nhiễu nhưng đồng thời phải
đảm bảo sự ảnh hưởng đến các thành phần vân tay ít nhất có thể. Để lọc các
thành phần nhiễu, ta sử dụng phần tử cấu trúc được mô tả trong hình II.2.7(b)
Toàn bộ hình II.2.7 thể hiện từng bước của quá trình lọc ảnh. Các nhiễu được
hoàn toàn loại bỏ trong phép toán làm gầy ở giai đoạn đầu do kích thước của
các điểm nhiễu là nhỏ hơn kích thước của phần tử cấu trúc và sau đó được
khôi phục lại nguyên dạng như ảnh lúc đầu. Chú ý rằng, sau quá trình này gần
như toàn bộ các thành phần nhiễu đã bị lọc bỏ.
Hình II.2.7. Xử lý nhiễu trong ảnh vân tay
Trang 27
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2.4. Biến đổi Hit or Miss
Biến đổi Hit or Miss là một công cụ cơ bản để dò tìm ảnh. tui giới
thiệu khái niệm này với sự trợ giúp của hình I.2.8. Trong hình, tập A bao gồm
3 ảnh X, Y, Z. mục tiêu là tìm vị trí của một trong 3 ảnh trên, giả sử là X
Giả sử gốc của mỗi ảnh là tại trung tâm của ảnh. Giả sử X được bao bởi
một cửa sổ nhỏ W. Ta định nghĩa nền của tập X trên ảnh W là tập tất cả các
điểm ảnh thuộc W mà không thuộc X, ký hiệu là W-X như được mô tả trong
hình II.2.8(b). Trong hình II.2.8(c) mô tả phần bù của tập A. Hình II.2.8(d)
thể hiện tập A gầy . Nhớ lại rằng tập gầy A bởi X là tập tất cả các vị trí của
điểm gốc X sao cho X hoàn toàn nằm trong tập A. Hiểu theo cách hình học
thuần túy thì AӨX có thể coi như là tập hợp tất cả các điểm gốc của X mà tại
đó X giao (match) với tập A. Hình II.2.8 thể hiện việc làm gầy phần bù tập A
bởi phần tử cấu trúc (W − X ) . Phần tối phía ngoài trong hình II.2.8(e) là
phần bị ăn mòn.
Trang 28
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình II.2.8. Phép toán Hit or Miss
Chú ý rằng trong hình II.2.8(d) và (e), tập tất cả các vị trí mà X hoàn
toàn nằm trong A là giao của ảnh gầy A bởi X với ảnh gầy AC bởi (W − X )
như trong hình II.2.8(f). Nói một cách khác nếu ký hiệu B là tập cấu thành lên
X và nền của nó, tập các điểm phù hợp (match) của B trong A, ký hiệu là
được định nghĩa bởi:
Chúng ta có thể ký hiệu B=(B1, B2), trong đó B1 là tập được tạo thành
từ B và đối tượng, còn B2 được tạo thành từ B và nền. Khi đó, công thức trên
có dạng biến đổi khác:
3. Một số thuật toán dựa trên phép toán hình thái
3.1. Trích chọn biên
Biên của A được ký hiệu là β(A) có thể đạt được bằng cách ban đầu làm
gầy A bởi B sau đó thực hiện phép trừ A.
() ( )AAAB
(II.3-1)
với B là phần tử cấu trúc thích hợp.
Hình II.3.1. mô tả cơ chế của thuật toán trích chọn biên. Sử dụng thuật toán
trên đối với đối tượng đơn giản A và phần tử cấu trúc B, kết quả đạt được là
biên của đối tượng A như đã thấy ở hình II.3.1(d)
Trang 29
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình II.3.1. Trích chọn biên
Mặc dù phần tử cấu trúc B ở trong ví dụ được cho bởi hình II.3.1 là một
trong các phần tử cấu trúc được sử dụng nhiều nhất, tuy nhiên, tùy theo đặc
điểm của ảnh cần được trích chọn, mà ta chọn các phần tử cấu trúc khác cho
phù hợp. Biên của hình A trong ví dụ này có độ dày là 1 điểm ảnh, nhưng với
phần tử cấu trúc kích thước là 5 x 5, thì biên của A sẽ có độ dày là 2 và 3
điểm ảnh. Như vậy, với các phần tử cấu trúc khác nhau thì cho ta kết quả khác
nhau. Do vậy, việc chọn các phần tử cấu trúc tuỳ từng trường hợp vào mục tiêu cũng
như các ứng công cụ thể.
Hình II.3.2 cho ta một ứng dụng thuật toán tách biên cụ thể hơn. Trong
ví dụ này, phần tử 1 thay mặt cho điểm ảnh trắng, phần tử 0 tương ứng với
điểm ảnh đen. Do phần tử cấu trúc là phần tử cấu trúc trong ví dụ ở hình
II.3.1, cho nên biên của ảnh đạt được chỉ có kích thước là một điểm ảnh.
Trang 30
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình II.3.2. Ảnh được trích chọn biên
3.2. Tô miền
Trong hình I.3.3, tập A chứa một tập con mà các phần tử liên thông 8.
Xuất phát với một điểm p nằm bên trong, mục tiêu là tô toàn bộ miền có biên
bởi các điểm đó.
Ta xây dựng thuật toán như sau:
1( )
c
k kX X B A
(I.3-2)
Trong đó X0=P và B là phần tử cấu trúc đối xứng như ở trên hình I.3.3.
Thuật toán kết thúc tại bước k nếu Xk= Xk-1. Miền được tô chính là hợp của
tập A và Xk
Trang 31
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình II.3.3. Ví dụ thuật toán tô miền
3.3. Tách các thành phần liên thông
Trong rất nhiều ứng dụng, việc phân tích ảnh đòi hỏi ta phải tách các
thành phần liên thông để phục vụ cho tác vụ xử lý. Ví dụ như trong ứng dụng
nhận dạng mặt người, việc đầu tiên cần xử lý là phải tách các thành phần
liên thông, sau đó thực hiện việc nhận dạng trên các thành phần đó.
Giả sử A chứa thành phần liên thông Y và p là một điểm của Y đã được
biết trước.
Thuật toán được mô tả bởi phương trình sau:
Xk = (Xk-1 B) A k = 1,2,3, .... (I.3-3)
Trong đó X0 = p và B là phần tử cấu trúc thích hợp. Nếu Xk= Xk-1 thì
thuật toán hội tụ Y = Xk.
Phương trình trên trên có cấu trúc giống như phương trình (II.3-2), tuy
nhiên trong phương trình (II.3-3), thành phần A tham gia thuật toán, ngược
Trang 32
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
lại, trong phương trình (II.3-2) thành phần bù của tập A tham gia thuật toán.
Hình II.3.4. Tìm các thành phần liên thông trong ảnh
Thành phần liên thông được sử dụng rộng rãi trong chẩn đoán tự động.
Hình II.3.5(a) thể hiện ảnh X quang cấu trúc xương của một con cá. Mục tiêu
là phải xác định được vật lạ trong quá trình xử lý cá trước khi đóng gói và gửi
đi. Trong trường hợp này, các điểm ảnh thể hiện đối tượng (xương và vật lạ)
có mật độ nhiều hơn so với mật độ các điểm ảnh cấu thành nền. Như vậy dẫn
tới mức xám của đối tượng so với nền của ảnh sẽ có sự chênh lệch. Bằng cách
đưa ra một ngưỡng đơn, ta có thể táchđược đối tượng ra khỏi nền. Kết quả
của quá trình tách nền được thể hiện trên hình II.3.5(b).
Đặc trưng quan trọng nhất của các hình phía dưới đó chính là các điểm
cấu thành xương chứ không phải là các cô lập, các vật lạ. Chú...
Download miễn phí Luận văn Tìm hiểu phép toán hình thái, phương pháp di truyền và ứng dụng
MỤC LỤC
DANH MỤC CÁC HÌNH VẼ
LỜI NÓI ĐẦU 5
Chương I. Giới thiệu chung về xử lý ảnh và phương pháp nâng
cao chất lượng hình ảnh7
1. Giới thiệu chung về xử lý ảnh 7
2. Giới thiệu ảnh nhị phân 9
2.1. Một số khái niệm 9
2.2. Đặt bài toán nâng cao chất lượng ảnh bằng các phép toán hình thái11
2.3. Đặt bài toán nâng cao chất lượng ảnh bằng kỹ thuật tìm xương và làm mảnh13
3. Khái quát về phương pháp nâng cao chất lưởng hình ảnh 14
Chương II: Các khái niệm cơ bản về toán học hình thái 16
1. Quan hệ giữa khái niệm tập hợp và phép toán hình thái 16
1.1. Một số khái niệm cơ bản về tập hợp 17
1.2. Các phép toán logic trên ảnh nhị phân 20
2. Phép toán làm béo (Dilation) và làm gầy (Erosion) 21
2.1. Làm béo 21
2.2. Làm gầy 23
2.3. Phép toán Opening và Closing 23
2.4. Biến đổi Hit or Miss 27
3. Một số thuật toán dựa trên phép toán hình thái 28
3.1. Trích chọn biên 28
3.2. Tô miền 30
3.3. Tách các thành phần liên thông 31
3.4. Làm mảnh 33
3.5. Làm dầy 34
3.6. Tìm xương của ảnh 35
Chương III: Thuật toán di truyền 37
1. Thuật toán di truyền là gì? 37
2. Sử dụng thuật toán di truyền trong toán học hình thái 37
3. Hoạt động của thuật toán di truyền 38
3.1. Quá trình lai ghép (phép lai) 41
3.2. Quá trình đột biến (phép đột biến) 43
3.3. Quá trình sinh sản và chọn lọc (phép tái sinh và phép chọn) 44
4. Mô hình thuật toán 44
Chương IV: 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 46
1. Tiếp cận ngẫu nhiên 50
2. Cấu trúc dữ liệu 51
3. Giải thuật dựa trên thuật toán tìm kiếm di truyền 55
Chương V: Thực nghiệm 61
1. Mô tả bài toán và giả thuyết 61
2. Giao diện chính của chương trình 61
3. Một số kết quả thử nghiệm 62
Chương VI: Kết luận 67
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung:
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 B A B
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
Trang 26
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
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ạng vân tay người, ảnh cần nhận dạng có nhiễu
(như thể hiện trong hình II.2.7(a). Các nhiễu là các chấm trắng nhỏ (khác với
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). Mục tiêu của quá trình tiền xử lý ảnh
trước khi nhận dạng là việc lọc các thành phần nhiễu nhưng đồng thời phải
đảm bảo sự ảnh hưởng đến các thành phần vân tay ít nhất có thể. Để lọc các
thành phần nhiễu, ta sử dụng phần tử cấu trúc được mô tả trong hình II.2.7(b)
Toàn bộ hình II.2.7 thể hiện từng bước của quá trình lọc ảnh. Các nhiễu được
hoàn toàn loại bỏ trong phép toán làm gầy ở giai đoạn đầu do kích thước của
các điểm nhiễu là nhỏ hơn kích thước của phần tử cấu trúc và sau đó được
khôi phục lại nguyên dạng như ảnh lúc đầu. Chú ý rằng, sau quá trình này gần
như toàn bộ các thành phần nhiễu đã bị lọc bỏ.
Hình II.2.7. Xử lý nhiễu trong ảnh vân tay
Trang 27
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2.4. Biến đổi Hit or Miss
Biến đổi Hit or Miss là một công cụ cơ bản để dò tìm ảnh. tui giới
thiệu khái niệm này với sự trợ giúp của hình I.2.8. Trong hình, tập A bao gồm
3 ảnh X, Y, Z. mục tiêu là tìm vị trí của một trong 3 ảnh trên, giả sử là X
Giả sử gốc của mỗi ảnh là tại trung tâm của ảnh. Giả sử X được bao bởi
một cửa sổ nhỏ W. Ta định nghĩa nền của tập X trên ảnh W là tập tất cả các
điểm ảnh thuộc W mà không thuộc X, ký hiệu là W-X như được mô tả trong
hình II.2.8(b). Trong hình II.2.8(c) mô tả phần bù của tập A. Hình II.2.8(d)
thể hiện tập A gầy . Nhớ lại rằng tập gầy A bởi X là tập tất cả các vị trí của
điểm gốc X sao cho X hoàn toàn nằm trong tập A. Hiểu theo cách hình học
thuần túy thì AӨX có thể coi như là tập hợp tất cả các điểm gốc của X mà tại
đó X giao (match) với tập A. Hình II.2.8 thể hiện việc làm gầy phần bù tập A
bởi phần tử cấu trúc (W − X ) . Phần tối phía ngoài trong hình II.2.8(e) là
phần bị ăn mòn.
Trang 28
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình II.2.8. Phép toán Hit or Miss
Chú ý rằng trong hình II.2.8(d) và (e), tập tất cả các vị trí mà X hoàn
toàn nằm trong A là giao của ảnh gầy A bởi X với ảnh gầy AC bởi (W − X )
như trong hình II.2.8(f). Nói một cách khác nếu ký hiệu B là tập cấu thành lên
X và nền của nó, tập các điểm phù hợp (match) của B trong A, ký hiệu là
được định nghĩa bởi:
Chúng ta có thể ký hiệu B=(B1, B2), trong đó B1 là tập được tạo thành
từ B và đối tượng, còn B2 được tạo thành từ B và nền. Khi đó, công thức trên
có dạng biến đổi khác:
3. Một số thuật toán dựa trên phép toán hình thái
3.1. Trích chọn biên
Biên của A được ký hiệu là β(A) có thể đạt được bằng cách ban đầu làm
gầy A bởi B sau đó thực hiện phép trừ A.
() ( )AAAB
(II.3-1)
với B là phần tử cấu trúc thích hợp.
Hình II.3.1. mô tả cơ chế của thuật toán trích chọn biên. Sử dụng thuật toán
trên đối với đối tượng đơn giản A và phần tử cấu trúc B, kết quả đạt được là
biên của đối tượng A như đã thấy ở hình II.3.1(d)
Trang 29
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình II.3.1. Trích chọn biên
Mặc dù phần tử cấu trúc B ở trong ví dụ được cho bởi hình II.3.1 là một
trong các phần tử cấu trúc được sử dụng nhiều nhất, tuy nhiên, tùy theo đặc
điểm của ảnh cần được trích chọn, mà ta chọn các phần tử cấu trúc khác cho
phù hợp. Biên của hình A trong ví dụ này có độ dày là 1 điểm ảnh, nhưng với
phần tử cấu trúc kích thước là 5 x 5, thì biên của A sẽ có độ dày là 2 và 3
điểm ảnh. Như vậy, với các phần tử cấu trúc khác nhau thì cho ta kết quả khác
nhau. Do vậy, việc chọn các phần tử cấu trúc tuỳ từng trường hợp vào mục tiêu cũng
như các ứng công cụ thể.
Hình II.3.2 cho ta một ứng dụng thuật toán tách biên cụ thể hơn. Trong
ví dụ này, phần tử 1 thay mặt cho điểm ảnh trắng, phần tử 0 tương ứng với
điểm ảnh đen. Do phần tử cấu trúc là phần tử cấu trúc trong ví dụ ở hình
II.3.1, cho nên biên của ảnh đạt được chỉ có kích thước là một điểm ảnh.
Trang 30
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình II.3.2. Ảnh được trích chọn biên
3.2. Tô miền
Trong hình I.3.3, tập A chứa một tập con mà các phần tử liên thông 8.
Xuất phát với một điểm p nằm bên trong, mục tiêu là tô toàn bộ miền có biên
bởi các điểm đó.
Ta xây dựng thuật toán như sau:
1( )
c
k kX X B A
(I.3-2)
Trong đó X0=P và B là phần tử cấu trúc đối xứng như ở trên hình I.3.3.
Thuật toán kết thúc tại bước k nếu Xk= Xk-1. Miền được tô chính là hợp của
tập A và Xk
Trang 31
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình II.3.3. Ví dụ thuật toán tô miền
3.3. Tách các thành phần liên thông
Trong rất nhiều ứng dụng, việc phân tích ảnh đòi hỏi ta phải tách các
thành phần liên thông để phục vụ cho tác vụ xử lý. Ví dụ như trong ứng dụng
nhận dạng mặt người, việc đầu tiên cần xử lý là phải tách các thành phần
liên thông, sau đó thực hiện việc nhận dạng trên các thành phần đó.
Giả sử A chứa thành phần liên thông Y và p là một điểm của Y đã được
biết trước.
Thuật toán được mô tả bởi phương trình sau:
Xk = (Xk-1 B) A k = 1,2,3, .... (I.3-3)
Trong đó X0 = p và B là phần tử cấu trúc thích hợp. Nếu Xk= Xk-1 thì
thuật toán hội tụ Y = Xk.
Phương trình trên trên có cấu trúc giống như phương trình (II.3-2), tuy
nhiên trong phương trình (II.3-3), thành phần A tham gia thuật toán, ngược
Trang 32
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
lại, trong phương trình (II.3-2) thành phần bù của tập A tham gia thuật toán.
Hình II.3.4. Tìm các thành phần liên thông trong ảnh
Thành phần liên thông được sử dụng rộng rãi trong chẩn đoán tự động.
Hình II.3.5(a) thể hiện ảnh X quang cấu trúc xương của một con cá. Mục tiêu
là phải xác định được vật lạ trong quá trình xử lý cá trước khi đóng gói và gửi
đi. Trong trường hợp này, các điểm ảnh thể hiện đối tượng (xương và vật lạ)
có mật độ nhiều hơn so với mật độ các điểm ảnh cấu thành nền. Như vậy dẫn
tới mức xám của đối tượng so với nền của ảnh sẽ có sự chênh lệch. Bằng cách
đưa ra một ngưỡng đơn, ta có thể táchđược đối tượng ra khỏi nền. Kết quả
của quá trình tách nền được thể hiện trên hình II.3.5(b).
Đặc trưng quan trọng nhất của các hình phía dưới đó chính là các điểm
cấu thành xương chứ không phải là các cô lập, các vật lạ. Chú...