Tài liệu 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: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
LUẬN VĂN THẠC SỸ KỸ THUẬT
ĐỀ TÀI: TÌM HIỂU PHÉP TOÁN HÌNH THÁI, PHƯƠNG PHÁP DI TRUYỀN VÀ
ỨNG DỤNG
HỌC VIÊN THỰC HIỆN: PHẠM ĐĂNG TỨ
GIÁO VIÊN HƯỚNG DẪN: PGS.TS. NGÔ QUỐC TẠO
THÁI NGUYÊN – NĂM 2009
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
LỜI CẢM ƠN
Trong lời đầu tiên của báo cáo luận văn tốt nghiệp “Tìm hiểu phép toán hình
thái, phương pháp di truyền và ứng dụng” này, tôi muốn gửi những lời cảm ơn và
biết ơn chân thành của mình tới tất cả những người đã hỗ trợ, giúp đỡ tôi về chuyên
môn, vật chất và tinh thần trong quá trình thực hiện luận văn.
Trước hết, tôi xin chân thành cảm ơn PGS. TS. Ngô Quốc Tạo thuộc viện
Công nghệ thông tin, người đã trực tiếp hướng dẫn, nhận xét, giúp đỡ tôi trong suốt
quá trình thực hiện luận văn.
Xin chân thành cảm ơn Khoa Công nghệ thông tin, Viện Công nghệ thông
tin đã giúp đỡ tôi trong suốt quá trình học tập v...
72 trang |
Chia sẻ: hunglv | Lượt xem: 1214 | Lượt tải: 0
Bạn đang xem trước 20 trang mẫu tài liệu 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, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
LUẬN VĂN THẠC SỸ KỸ THUẬT
ĐỀ TÀI: TÌM HIỂU PHÉP TOÁN HÌNH THÁI, PHƯƠNG PHÁP DI TRUYỀN VÀ
ỨNG DỤNG
HỌC VIÊN THỰC HIỆN: PHẠM ĐĂNG TỨ
GIÁO VIÊN HƯỚNG DẪN: PGS.TS. NGÔ QUỐC TẠO
THÁI NGUYÊN – NĂM 2009
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
LỜI CẢM ƠN
Trong lời đầu tiên của báo cáo luận văn tốt nghiệp “Tìm hiểu phép toán hình
thái, phương pháp di truyền và ứng dụng” này, tôi muốn gửi những lời cảm ơn và
biết ơn chân thành của mình tới tất cả những người đã hỗ trợ, giúp đỡ tôi về chuyên
môn, vật chất và tinh thần trong quá trình thực hiện luận văn.
Trước hết, tôi xin chân thành cảm ơn PGS. TS. Ngô Quốc Tạo thuộc viện
Công nghệ thông tin, người đã trực tiếp hướng dẫn, nhận xét, giúp đỡ tôi trong suốt
quá trình thực hiện luận văn.
Xin chân thành cảm ơn Khoa Công nghệ thông tin, Viện Công nghệ thông
tin đã giúp đỡ tôi trong suốt quá trình học tập và nghiên cứu.
Tôi cũng xin bày tỏ lòng biết ơn đến gia đình và những người bạn thân đã
giúp đỡ, động viên tôi rất nhiều trong suốt quá trình học tập và làm luận văn tốt
nghiệp.
Do thời gian thực hiện có hạn, kiến thức chuyên môn còn nhiều hạn chế nên
đồ án tôi thực hiện chắc chắn không tránh khỏi những thiếu sót nhất định. Tôi rất
mong nhận được ý kiến đóng góp của thầy, cô giáo và các bạn.
Xin chân thành cảm ơn !
Thái Nguyên, tháng 11/2009
Phạm Đăng Tứ
Trang 1
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
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 ảnh
7
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ái
11
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ảnh
13
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
Trang 2
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
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
Trang 3
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
DANH MỤC CÁC HÌNH VẼ
Hình I.1. Sơ đồ quy trình xử lý ảnh 8
Hình I.2. Mô hình tổng quát của hệ thống nhận dạng ảnh 13
Hình II.1.1. Ảnh nhị phân 16
Hình II.1.2. Ảnh đa cấp xám 17
Hình II.1.3. Các phép toán cơ bản trên tập hợp 19
HÌnh II.1.4. Các phép toán cơ bản 20
Hình II.2.1. Phép toán dilation 22
Hình II.2.2. Ứng dụng của phép toán dilation 22
Hình II.2.3. Loại bỏ thành phần nhiễu 23
Hình II.2.4. Phép toán Opening 24
Hình II.2.5. Phép toán Closing 24
Hình II.2.6. Phép toán Opening và Closing 25
Hình II.2.7. Xử lý nhiễu trong ảnh vân tay 26
Hình II.2.8. Phép toán Hit ỏ Miss 27
Hình II.3.1. Trích chọn biên 29
Hình II.3.2. Ảnh được trích chọn biên 30
Hình II.3.3. Ví dụ thuật toán tô miền . 31
Hình II.3.4. Tìm các thành phần liên thông trong ảnh 32
Hình II.3.5. Xác định vật thể lạ trong ảnh 33
Hình II.3.6. Làm mảnh ảnh 34
Hình II.3.7. Làm dầy ảnh 35
Hình II.3.8. Tìm xương của ảnh 36
Hình III.1. Mô phỏng quá trình tiến hóa 40
Hình III.2. Lai ghép một điểm 42
Hình III.3. Lai ghép hai điểm 42
Hình III.4. Cắt và ghép 42
Hình III.5. Ví dụ về phép lai . 43
Hình III.6. Đột biến tại bít thứ 6 44
Trang 4
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình III.7. Mô tả hoạt động thuật toán 45
Hình IV.1. Cấu trúc dữ liệu 53
Hình IV.2. Ví dụ về cắt và ghép nối 58
Trang 5
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
LỜI NÓI ĐẦ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 chủ yếu thông qua hình dạng. Chính
vì vậy, biểu diễn hình dạng 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.
Xử lý ảnh quan tâm chủ yếu đến việc trích chọn các thông tin hữu ích
từ trong ảnh. Các thuật toán xử lý ảnh được phân ra làm 3 mức. Mức thấp
nhất là các phương pháp thao tác trực tiếp với các dữ liệu thô, các giá trị điểm
ảnh có thể bị nhiễu. Mức thứ hai là tận dụng các kết quả ở mức 1 để đưa ra
các kết quả tốt hơn như: phân đoạn ảnh, liên kết ảnh. Mức thứ ba là các
phương pháp trích trọn ngữ nghĩa các thông tin dựa trên các kết quả của các
mức thấp hơn, ví dụ như: nhận dạng chữ viết tay, nhận dạng mặt người.
Toán học hình thái (Mathematic Morphology) là một lĩnh vực riêng
biệt trong xử lý ảnh. Không giống như các cách tiếp cận khác thiên về toán
học tính toán, MM dựa trên cấu trúc và hình dạng, dùng các toán hình thái cơ
bản để làm đơn giản ảnh nhưng vẫn giữ lại những đặc trưng chính. MM còn là
một công cụ cơ bản để trích chọn các thành phần ảnh, như biên ảnh, xương
ảnh, rất hữu dụng cho việc biểu diễn các các vùng khác nhau trên một ảnh.
Những kỹ thuật dùng toán hình thái như lọc ảnh, làm mảnh ảnh hay làm dầy
ảnh có sử dụng toán học hình thái cũng được sử dụng trong quá trình tiền xử
lý ảnh. Ngoài ra, một trong các ứng dụng quan trọng mà tôi đề cập chính
trong luận văn này là: Phân rã phần tử cấu trúc thành các phần tử cấu trúc nhỏ
hơn. Phần tử cấu trúc là phần tử tham gia trong các phép toán hình thái, và
việc phân rã phần tử cấu trúc hoặc nói một cách khác là ma trận điểm ảnh có
ba lợi ích quan trọng: Thứ nhất, làm giảm phép toán trong các ứng dụng mà
phần tử đó tham gia. Thứ hai, giảm không gian lưu trữ ảnh. Thứ ba, đối với
Trang 6
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
các hệ thống chỉ hỗ trợ tập lệnh SIMD trên các phần tử nhỏ hơn nhiều phần tử
cấu trúc, thì việc phân rã phần tử cấu trúc thành các phần tử cấu trúc nhỏ hơn
là cần thiết.
Trong khuôn khổ của luận văn này tôi đi tìm hiểu các khái niệm cơ
bản về toán học hình thái như phép toán làm béo, làm gầy dựa vào cấu trúc
mẫu, một số thuật toán dựa trên phép toán hình thái; Tìm hiểu về thuật toán di
truyền, lai ghép, đột biến tái sinh và lựa chọn, phương pháp phân rã phần tử
cấu trúc mẫu dựa trên thuật toán di truyền ..vv. Bố cục của luận văn được tổ
chức như sau:
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 ảnh.
Chƣơng II: Trình bày các khái niệm cơ bản về toán học hình thái.
Chƣơng III: Trình bày các khái niệm liên quan đến thuật toán di
truyền.
Chƣơng IV: 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 V: Trình bày kết quả thực nghiệm
Trang 7
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
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 ẢNH
1. Giới thiệu chung về xử lý ảnh
Cũng như xử lý dữ liệu bằng đồ hoạ, xử lý ảnh số 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 số 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)
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
Trang 8
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyê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 được tiến hành theo sơ đồ sau:
Hình I.1 Sơ đồ quy trình xử lý ảnh
Trước hết là qúa 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).
Ảnh có thể thu nhận từ vệ tinh qua các bộ cảm ứng (sensor), hay ảnh,
tranh đượ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.
Trang 9
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
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 tính (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 I.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 thu nhập
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 30
kiểu 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.
2.1. Một số khái niệ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 số hoá, ngươì ta biến đổi tín hiêụ 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.
Trang 10
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
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.
* Với ảnh xám.
Nếu dùng 8 bít (1 byte) để biểu diễn mức xám thì số các mức xám có thể
biểu diễn được là 28 hay 256. Mỗi mức xám được biểu diễn dưới dạng là một
số nguyên nằm trong khoảng từ 0 đến 255, với mức 0 biểu diễn chúc mức
cường độ tối nhất và mức 255 biểu diễn cho mức cường độ sáng nhất.
* Với ảnh mầu.
Cách biểu diễn cũng tương tự như với ảnh đen trắng, chỉ khác là các số
tại mỗi phần tử của ma trận biểu diễn cho ba mầu riêng rẽ gồm: đỏ(red),
lục(green) và lam(blue). Để biểu diễn cho một điểm ảnh mầu cần 24 bít, 24
bít này được chia thành ba khoảng 8 bít. Mỗi khoảng này biểu diễn cho cường
độ sáng của một trong các mầu chính tổ hợp của các mầu ta được nhiều mức
biểu diễn, như vậy mỗi điểm ảnh có thể được mô tả rõ giá trị màu tự nhiên
của nó (true color).
Trang 11
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
* Ảnh đa cấp xám
Ảnh đa cấp xám được áp dụng tronh nhiều lĩnh vực như sinh vật học
hoặc trong công nghiệp. Thực tế chỉ ra rằng bất kỳ ứng dụng nào trên ảnh
mức xám cũng ứng dụng được trên ảnh mầu. Ta có thể biến đổi ảnh mầu về
ảnh xám. Mỗi điểm ảnh mầu có 3 giá trị (Red, Green, Blue), nếu 3 giá trị này
bằng nhau thi ta có màu xám(Grey), khi đó với mỗi điểm ảnh ta chỉ cần lưu 1
giá trị.
Việc xử lý ảnh nhị phân là một bước tiền xử lý các ảnh, để phân đoạn và
tách ra các đặc tính. Nhờ vậy ta có thể biết được mối quan hệ tôpô giữa các
điểm ảnh cũng như thực hiện các phép biến đổi ảnh không tuyến tính đạt hiệu
quả; trong quá trình xử lý ảnh các phép biến đổi này dẫn đến sự đơn giản hóa
việc đánh giá ảnh. Việc đếm các điểm ảnh trên ảnh nhị phân đã qua biến đổi
tạo điều kiện thuận lợi cho việc tách ra các đặc tính. Bằng cách sử dụng các
ảnh nhị phân đã qua xử lý như là những mặt nạ đối với các ảnh xám, ta có thể
tách ra các vùng đáng quan tâm của một ảnh xám từ tập hợp các ảnh.
Để tạo ra một ảnh nhị phân, một ảnh xám cần phải được biến đổi thành
một ảnh nhị phân nhờ một quá trình phân đoạn thích hợp. Muốn thế phương
pháp đơn giản nhất là phương pháp tách ngưỡng. Các giá trị nằm ở bên trên
ngưỡng được gán giá trị 1 còn ở bên dưới ngưỡng thì được gán giá trị 0. Việc
tìm giá trị ngưỡng có thể thực hiện tự động nhờ kỹ thuật tách ngưỡng tự động.
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á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
Trang 12
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
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.2).., 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 cuả một
đường thuộc một 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 đó.
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, 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.
Trang 13
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
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ảnh
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). 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...
Hình I.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 xương của đường nét Phương
pháp trích chọn đặc điểm sử dụng ảnh đã mảnh được sử dụng nhiều vì việc
Trang 14
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
trích chọn đặc điểm trở nên dễ dàng. Sau bước này các đường nét đã mảnh
được véctơ hoá ảnh phục vụ việc nén dữ liệu, nhằm giảm thiểu yêu cầu về
không gian lưu trữ, xử lý và thời gian xử lý. Kỹ thuật làm mảnh là một trong
nhiều ứng dụng của phép toán hình thái học (Morphology) sẽ giải quyết một
số vấn đề cuả bài toán nêu trên trong công đoạn tiền xử lý ảnh.
3. Khái quát về phƣơng pháp nâng cao chất lƣợng hình ảnh.
Nâng cao chất lượng hình ảnh là một bước quan trọng tạo tiền đề cho xử
lý ảnh. Mục đích chính là nhằm làm nổi một số đặc tính của ảnh như thay đổi
độ tương phản, lọc nhiễu, nổi biên, làm trơn ảnh, khuếch đại ảnh, ... tăng
cường ảnh và khôi phục ảnh là hai quá trình khác nhau về mục đích.
Tăng cường ảnh bao gồm một loạt các phương pháp nhằm hoàn thiện
trạng thái quan sát của một ảnh. Tập hợp các kỹ thuật này tạo nên giai đoạn
tiền xử lý ảnh. Nhiệm vụ của tăng cường ảnh không phải là làm tăng lượng
thông tin vốn có trong ảnh mà làm nổi bật các đặc trưng đã chọn làm sao để
có thể phát hiện tốt hơn, tạo thành quá trình tiền xử lý cho phân tích ảnh.
Khôi phục ảnh nhằm khôi phục ảnh gần với ảnh thực nhất trước khi nó
bị biến dạng do nhiều nguyên nhân khác nhau. Khôi phục ảnh đề cập tới các
kỹ thuật loại bỏ hay tối thiểu hóa các ảnh hưởng của môi trường hay các hệ
thống thu nhận, phát hiện và lưu trữ ảnh đến ảnh thu nhận được. Ở đây, ta có
thể liệt kê các nguyên nhân biến dạng: do nhiễu bộ phận cảm nhận tín hiệu,
ảnh mờ do Camera, nhiễu ngẫu nhiên của khí quyển, ... khôi phục ảnh bao
gồm nhiều quá trình như: lọc ảnh, khử nhiễu nhằm làm giảm các biến dạng để
có thể khôi phục lại ảnh gần giống ảnh gốc tùy theo các nguyên nhân gây ra
biến dạng.
Về nguyên tắc khôi phục ảnh nhằm xác định mô hình toán học của quá
trình đã gây ra biến dạng, tiếp theo là dùng ánh xạ ngược để xác định lại ảnh.
Trang 15
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Việc xác định mô hình có thể thực hiện theo hai hướng: trước và sau. Theo
hướng thưc nhất, một mô hình sẽ được xây dựng từ các ảnh kiêm nghiệm để
xác định đáp ứng xung của hệ thống nhiễu. Theo hướng thứ 2 người ta thực
hiện các phép đo trên ảnh. Nói chung là mô hình không biết trước. các mô
hình toán học dùng cho cả hai phương pháp là rất phức tạp.
Trang 16
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
CHƢƠNG II: CÁC KHÁI NIỆM CƠ BẢN VỀ TOÁN HỌC HÌNH THÁI
1. 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.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.
Hình II.1.1. Ảnh nhị phân
Trang 17
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
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 đó. Hình II.1.2 mô tả một thể hiện
đơn giản của ảnh đa cấp xám
Hình II.1.2. Ả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.
1.1. 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 Z2. Nếu a = (a1,a2) là một phần tử của A, thì
ta kí hiệu là:
a A
Trang 18
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
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
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ụ như khi ta
viết C =
,w w d d D
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 và kí hiệu là:
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 :
C = A
B
Trang 19
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình II.1.3. 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
A
c
=
w w A
Hiệu của A vả B, kí hiệu là A-B được định nghĩa bởi
w w A,w cA B B A B
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:
{ | , }B w w b b B
và tập tịnh tiến của 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:
,zA c c a z a A
Trang 20
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
1.2. 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. Hình II.1.4 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.
HìnhII.1.4. Các phép toán cơ bản
Trang 21
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2. 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.
2.1. Làm béo
Với A và B là 2 tập trong Z2, tập béo của A gây bởi tập B được ký hiệu
là:
{ | ( ) }zA B z B 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.
Hình II.2.1(a) thể hiện ảnh tham gia thuật toán làm béo, hình II.2.1(b)
mô tả phần tử cấu trúc và tập ngược của nó( những điểm chấm đen mô tả các
phần tử gốc). 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.
Trang 22
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình II.2.1. 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. Hình II.2.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.
HìnhII.2.2. Ứng dụng của phép toán dilation
Trang 23
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2.2. Làm gầy
Cho tập A và B trong Z2, 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. Hình II.2.3 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 II.2.3. Loại bỏ thành phần nhiễu
2.3. 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.
Trang 24
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
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
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.
{( ) }zA B B A
Hình II.2.4. 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.
Hình II.2.5. Phép toán Closing
Trang 25
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình II.2.6. 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 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. Tôi 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ỳ thuộc vào mục tiêu cũng
như các ứng dụ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 đại diện 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 phải 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úng ta có thể giả
thuyết rằng chỉ có các điểm còn lại sau khi ta thực hiện phép toán làm gầy bởi
phần tử cấu trúc 5x5 là thành phần của xương. Kết quả của quá trình làm gầy
là ảnh II.3.5(c). Chúng ta thực hiện việc đánh nhãn các đối tượng còn lại bằng
cách tách các thành phần liên thông. Có tất cả 15 thành phần liên thông trong
Trang 33
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
đó có 3 thành phần bị loại bỏ do kích thước quá nhỏ không có ý nghĩa. Kết
hợp với ảnh gốc ban đầu, ta dễ dàng xác định được vị trí của các vật lạ.
Hình II.3.5. Xác định vật thể lạ trong ảnh
3.4. Làm mảnh
Mảnh của tập A gây bởi phần tử cấu trúc B, được ký hiệu là A
B,
được định nghĩa thông qua biến đổi hit-or-miss:
A
B = A – (A*B)
= A
(A*B)
c
(II.3-4)
Như trong phần trước đã nói, chúng ta chỉ quan tâm đến các mẫu phù
hợp với các phần tử cấu trúc, bởi vậy không một phép toán nền nào được yêu
cầu trong biến đổi hit-or-miss. Một cách biểu diễn hình học hữu ích cho việc
làm mảnh ảnh A là dựa trên dãy các phần tử cấu trúc:
{B} = {B1,B2,..., Bn}
Trong đó Bi chính là phần tử Bi-1 nhưng được xoay đi. Sử dụng khái
niệm này, chúng ta có thể xây dựng quá trình làm mảnh bởi một dãy các phần
tử cấu trúc.
Trang 34
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
A ⊗ {B} = ((...(( A⊗ B1) ⊗ B2)...) ⊗ Bn) (II.3-5)
Hình II.3.6. Làm mảnh ảnh
Quá trình để làm mảnh A bắt đầu bằng việc làm mảnh A bởi B1, sau đó
tiếp tục với B2, quá trình làm mảnh kết thúc cho đến khi không có sự thay đổi
nào xảy ra.
Hình II.3.6(a) thể hiện tập tất cả các phần tử cấu trúc thường được sử
dụng cho quá trình làm mảnh và II.3.6(b) biểu diễn ảnh A sau khi được làm
mảnh bởi dãy các phần tử cấu trúc trong hình II.3.6(a).
3.5. Làm dầy
Quá trình làm dầy một ảnh được thể hiện bởi công thức
(I.3-6)
Trong đó B là phần tử cấu trúc phù hợp. Tương tự như quá trình làm
Trang 35
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
mảnh, làm dầy có thể được định nghĩa dưới dạng một dãy các phép toán.
A ⊙ {B} = ((...(( A⊙ B1) ⊙ B2)...) ⊙ Bn) (I.3-7)
Các phần tử cấu trúc được sử dụng trong phép toán làm dầy có cùng
cấu trúc như các phần tử cấu trúc trong hình II.3.6(a), nhưng có sự chuyển đổi
giá trị tại mỗi điểm ảnh. Nói cách khác là tương phản của nhau. Tuy nhiên
thuật toán làm dầy hiếm khi được sử dụng trong thực tế. Thay vào đó người ta
thường làm mảnh nền của ảnh để thu được hiệu quả làm dầy ảnh.
Hình II.3.7. Làm dầy ảnh
3.6. Tìm xƣơng của ảnh
Như trong hình (II.3.8) ký hiệu xương là S A( ) . Xương của ảnh A có
thể được biểu diễn dưới tập các phép toán làm gầy kết hợp với phép toán
opening:
0
( ) ( )
K
k
i
S A S A
(II.3-8)
với
( ) ( ) ( )kS A A kB A kB B
(II.3-9)
Trong đó B là phần tử cấu trúc và
Trang 36
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
( ) (...( ) ) ...)A kB A B B B
(II.3-10)
với K là bước áp dụng cuối cùng trước khi A bị suy biến thành tập
rỗng. Hay nói cách khác thì:
K= max{k|(A
kB) } (II.3-11)
Hình II.3.8. Tìm xương của ảnh
Công thức cho bởi hai phương trình trên thể hiện rằng S(A) có thể đạt được
bằng cách lấy hợp của các tập xương con Sk(A) . Nó cũng chỉ ra rằng A có thể
được xây dựng lại từ các tập con này bằng cách sử dụng phương trình
0
( ( ) )
K
k
i
A S A kB
(II.3-12)
Trang 37
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
CHƢƠNG III. THUẬT TOÁN DI TRUYỀN
1. Thuật toán di truyền là gì?
Có rất nhiều bài toán tối ưu mà người ta chưa tìm được thuật toán đa
thức để giải quyết chúng ví dụ như bài toán xếp lịch, bài toán sắp xếp đồ vật
hay các bài toán quy hoạch. Đối với các bài toán dạng này, người ta thường
tìm một lời giải cho kết quả chấp nhận được. Với một số bài toán quy hoạch
khó, ta cũng có thể dùng các thuật toán xác suất, những thuật toán này không
đảm bảo cho ra kết quả tối ưu, nhưng bằng cách chọn ngẫu nhiên đủ nhiều
“bằng chứng”, ta có thể giảm tùy thích xác suất sai của kết quả.
Nói một cách trừu tượng, việc giải một bài toán có thể xem như việc
tìm kiếm trong một không gian các lời giải có thể. Vì cái đích của chúng ta là
“lời giải tốt nhất”, ta có thể coi công việc này là một quá trình tối ưu hóa. Đối
với không gian nhỏ, phương pháp “vét cạn” cổ điển là đủ dùng; còn những
không gian lớn hơn đòi hỏi các phương pháp trí tuệ nhân tạo đặc biệt. Các
thuật toán di truyền nằm trong số các phương pháp đặc biệt đó.
2. Sử dụng thuật toán di truyền trong toán học hình thái
Thuật toán di truyền là một trong những kỹ thuật phổ biến trong các bài
toán hình thái có những ràng buộc yêu cần việc tối ưu hóa một tiêu chuẩn nào
đó. Ngoài bài toán phân rã phần tử cấu trúc sẽ được trình bày chi tiết trong
chương 3, người ta còn dùng thuật toán di truyền trong việc thiết kế các bộ lọc
cho ảnh đa cấp xám và thiết kế các giải thuật đối với các ảnh nhị phân. Hơn
nữa MM còn cung cấp các nền tảng cho việc phát triển giả thuyết di truyền.
Chúng ta sẽ mô tả những ý tưởng đó như sau:
Phân rã phần tử cấu trúc
Một phần tử cấu trúc có thể được phân rã thành các phần tử cấu trúc có
kích thước nhỏ hơn. Điều này rất có ích trong một số ứng dụng như: lưu trữ
Trang 38
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
hay tăng tốc độ tính toán.
Thiết kế các bộ lọc cho ảnh đa cấp xám
Thiết kế bộ lọc cho ảnh đa cấp xám là một bài toán tối ưu khó giải bằng
thuật toán đa thức. Các tác giả Harvay và Marshall trong tài liệu [21,22,23,24]
đã trình bày một cách tiếp cận thuật toán di truyền trong việc thiết kế bộ lọc
ảnh đa cấp xám. Hơn nữa, nghiên cứu đó đã dẫn tới một cách tiếp cận mang
tính cách mạng trong việc thiết kế giải thuật hình thái để tìm một dãy các
phép toán hình thái phù hợp.
Thiết kế giải thuật hình thái cho ảnh nhị phân
Yu [25] đã trình bày một cách tiếp cận đơn giản cho bài toán phân đoạn
ảnh sử dụng thuật toán di truyền. Ảnh được xem như là một tập hợp các đối
tượng được nhúng vào một nền thuần nhất và bị gây nhiễu. Quá trình phân
đoạn ảnh được thực hiện trên các ảnh 16x16 không chồng lấn. Các ảnh con
sau khi được phân đoạn sẽ được kết hợp lại với nhau để đưa ra được phân
đoạn lớn của ảnh. Hàm thích nghi đo độ tương tự của mỗi cá thể ảnh đối với
ảnh gốc ban đầu. Nó cũng bao gồm cả hàm phạt để giảm tần số nhiễu trong
các kết quả được phân đoạn.
3. Hoạt động của thuật toán di truyền
Hoạt động của thuật toán di truyền dựa trên thuyết chọn lọc tự nhiên.
Theo thuyết này thì quá trình tiến hóa tự nhiên là quá trình hoàn hảo nhất.
Quá trình tiến hóa diễn ra trên nhiều thế hệ, thế hệ sau được sinh ra thường tốt
hơn thế hệ trước do được kế thừa những mặt tốt của bố mẹ. Xuất phát từ ý
tưởng đó, thuật toán di truyền đã được ra đời, kế thừa những tư tưởng của lý
thuyết chọn lọc tự nhiên. Chúng ta sẽ nói về các “cá thể” trong một quần thể:
thường thì các cá thể này còn được gọi là xâu hoặc nhiễm sắc thể. Mỗi tế bào
trong cơ thể của một loại nào đó chứa một số nhất định nhiễm sắc thể (ví dụ
Trang 39
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
trong cơ thể người có 46 nhiễm sắc thể); tuy nhiên, trong bài này thì ta chỉ nói
về các cá thể chỉ chứa đúng một nhiễm sắc thể. Mỗi nhiễm sắc thể bao gồm
các đơn vị - gen – xếp liên tiếp; mỗi gen điều khiển sự thừa kế của một hoặc
vài tính trạng. Gen của tính trạng nhất định có vị trí xác định trên nhiễm sắc
thể, vị trí đó được gọi là loci (vị trí trên xâu). Một tính trạng bất kỳ (thí dụ
màu mắt) có thể được thể hiện với nhiều mức độ khác nhau; ta nói gen đó có
nhiều trạng thái (gọi là allete).
Mỗi nhiễm sắc thể (cá thể) sẽ biểu thị một lời giải có thể của một bài
toán (ý nghĩa của mỗi nhiễm sắc thể, nghĩa là kiểu gen của nó, được quy ước
bởi người lập trình); một qúa trình tiến hóa được thực hiện trên một quần thể
nhiễm sắc thể là tương đương với sự tìm kiếm trong một không gian các lời
giải có thể. Sự tìm kiếm này đòi hỏi sự cân bằng giữa hai mục đích: khai thác
lời giải tốt nhất và khám phá không gian tìm kiếm. Phương pháp “leo núi” là
một ví dụ về chiến lược khai thác lời giải tốt nhất theo các hướng cải tiến.
Tìm kiếm ngẫu nhiên là một ví dụ điển hình của sự khám phá không gian tìm
kiếm, không chú trọng khai thác các miền hứa hẹn trong không gian tìm
kiếm. Thuật toán di truyền là lớp các phương pháp tìm kiếm tổng quát (không
phụ thuộc vào miền xác định) với sự cân bằng đáng kể giữa khai thác và
khám phá không gian tìm kiếm.
Trang 40
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình III.1. Mô phỏng quá trình tiến hóa
Thuật toán dị truyền, cũng như các thuật toán tiến hóa nói chung, hình
thành dựa trên quan niệm cho rằng, quá trình tiến hóa tự nhiên là hoàn hảo
nhất, hợp lý nhất và tự nó đã mang tính tối ưu. Quan niệm này có thể được
xem như là một tiên đề đúng, không chứng minh được, nhưng phù hợp với
thực tế khách quan. Quá trình tiến hóa thể hiển tính tối ưu ở chỗ, thế hệ sau
Trang 41
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
bao giờ cũng tốt hơn, phát triển hơn, hoàn thiện hơn thế hệ trước. Tiến hóa tự
nhiên được duy trì nhờ hai quá trình cơ bản: sinh sản và chọn lọc tự nhiên.
Xuyên suốt quá trình tiến hóa tự nhiên, các thế hệ mới luôn được sinh ra để
bổ xung và thay thế thế hệ cũ. Cá thể nào phát triển hơn, thích ứng hơn với
môi trường sẽ tồn tại, cá thể nào không thích ứng với môi trường sẽ bị đào
thải. Sự thay đổi môi trường là động lực thúc đẩy quá trình tiến hóa. Ngược
lại, tiến hóa cũng tác động trở lại góp phần làm thay đổi môi trường.
Trong thuật giải di truyền, các cá thể mới liên tục được sinh ra trong
quá trình tiến hóa nhờ sự lai ghép ở thế hệ cha mẹ. Một các thể mới có thể
mang những tính trạng của cha mẹ (di truyền), cũng có thể mang những tính
trạng hoàn toàn mới (đột biến). Di truyền và đột biến là hai cơ chế có vai trò
quan trọng như nhau trong tiến hóa, dù rằng đột biến xay ra với xác xuất nhỏ
hơn nhiều so với hiện tượng di truyền. Các thuật toán tiến hóa, tuy có những
đặc điểm khác biết, nhưng đề mô phỏng bốn quá trình cơ bản: Lai ghép, đột
biến, sinh sản và chọn lọc tự nhiên.
Như vậy quá trình tiến hóa càng lâu thì càng có điều kiện cho các cá
thể tốt được sinh ra, và chất lượng của các cá thể càng được nâng lên.
3.1. Quá trình lai ghép (phép lai)
Phép lai là quá trình hình thành nhiếm sắc thể mới trên cơ sở các nhiễm
sắc thể của cha mẹ, bằng cách ghép một hay nhiều đoạn gen của hai (hay
nhiều) nhiễm sắc thể cha mẹ với nhau.
Lai ghép một điểm
Trên nhiễm sắc thể của cơ thể cha mẹ sẽ chọn ra một vị trí (điểm lai).
Dữ liệu ở các phía của điểm lai sẽ được hoán chuyển cho nhau giữa hai nhiễm
sắc thể của cha mẹ. Kết quả ta sẽ có nhiễm sắc thể của thế hệ con.
Trang 42
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình III.2. Lai ghép một điểm
Lai ghép hai điểm
Trên cơ thể của cha mẹ được xác định hai điểm lai ghép. Mọi dữ liệu
giữa hai điểm lai ghép đó được hoán đổi cho nhau trong nhiễm sắc thể của hai
cha mẹ, tạo ra hai nhiễm sắc thể của thế hệ con
Hình II.3. Lai ghép hai điểm
Cắt và ghép
Không giống như hai kiểu trên, với phương pháp lai “cắt và ghép” cho
ta kết quả hai cơ thể con có độ dài nhiễm sắc thể khác nhau, lý do của sự khác
biệt này chính là mỗi nhiễm sắc thể của cha mẹ đều có điểm lai khác nhau.
Trang 43
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Ví dụ về phép lai
Ví dụ về một phép lại một điểm với xác suất Pc có thể mô phỏng như
sau:
Hình III.5. Ví dụ về phép lai
- Chọn ngẫu nhiên hai (hay nhiều) các thể bất kì trong quần thể. Giả
sử các nhiễm sắc thể của cha mẹ đều có m gen.
- Tạo một số ngẫu nhiên trong khoảng từ 1 đến m-1 (ta gọi là điểm lai).
Điểm lai chia các chuỗi cha mẹ dài m thành 2 nhóm chuỗi con dài m1 và m2.
Hai chuỗi nhiễm sắc thể con mới sẽ là m11+m22 và m12+m21.
- Đưa hai cá thể mới này vào quần thể để tham gia các quá trình tiến
hóa tiếp theo.
Trang 44
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
3.2. Quá trình đột biến (phép đột biến)
Đột biến là hiện tượng cá thể con mang một số tính trạng không có
trong mã di truyền của cha mẹ. Mục đích của phép đột biến trong thuật toán
di truyền là giúp cho thuật toán tránh được các cực trị cục bộ. Phép đột biến
xảy ra với xác suất Pm nhỏ hơn rất nhiều so với xác suất Pc. Một phép đột
biến có thể mô phỏng như sau:
Hình III.6 Đột biến tại bít thứ 6
- Chọn ngẫu nhiên một cá thể cha mẹ bất kì trong quần thể.
- Tạo một số ngẫu nhiên k trong khoảng từ 1 đến m (1≤k≤m).
- Thay đổi gen thứ k và trả cá thể này về quần thể để tham gia quá trình
tiến hóa tiếp theo.
3.3. Quá trình sinh sản và chọn lọc (phép tái sinh và phép chọn)
Phép tái sinh là quá trình trong đó các cá thể được sao chép trên cơ sở
độ thích nghi của nó. Còn phép chọn là quá trình loại bỏ các cá thể xấu trong
quần thể để giữ lại trong quần thể các cá thể tốt. Phép chọn lọc có thể mô
phỏng như sau:
- Sắp xếp quần thể theo thứ tự độ tốt giảm dần.
- Loại bỏ các cá thể cuối dãy để chỉ giữ lại m cá thể có độ thích nghi tốt
nhất, ở đây ta giả sử quần thể có kích thước cố định m.
4. Mô hình thuật toán
Trang 45
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Trang 46
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình III.7. Mô tả hoạt động thuật toán
Điều kiện kết thúc thuật toán thường bao gồm:
Số lượng thế hệ được sinh ra.
Một cá thể thỏa mãn các tiêu chuẩn của bài toán.
Giá trị thích nghi cao nhất của cá thể được tìm thấy.
Trang 47
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
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
Trong một số hệ thống song song cổ điển thì việc sử dụng các phần tử
cấu trúc lớn là không hiệu quả, ví dụ như trên hệ thống SIMD, chỉ cho phép
thực hiện các phép toán trên các lân cận nhỏ hơn nhiều so với kích thước của
phần tử cấu trúc; hoặc các đặc trưng khác nhau của những hệ thống mục đích
chung (serial) và hệ thống song song, yêu cầu những kỹ thuật khác nhau để
phát huy những tính chất phần cứng đặc thù của mỗi hệ thống.
Định nghĩa 1. Cho một tập các phần tử cấu trúc cơ bản Fi {i=1,..,M}.
Phần tử cấu trúc B được gọi là lồi trên tập Fi đối với phép toán dãn ảnh nếu
như B có thể biểu diễn được dưới dạng một chuỗi các phép toán làm béo liên
tiếp trên tập các phần tử cấu trúc cơ bản.
1 2 3 ...k k k kmB F F F F
, với kj [1..M], cho j=1,...,m (1)
Ngược lại nếu B không thể biểu diễn dưới dạng chuỗi các phép toán
dãn ảnh trên tập phần tử cấu trúc cho trước thì B được gọi là không lồi. Trong
trường hợp này b có thể được biểu diễn dưới dạng:
1 2 3 ...... ZB C C C C
(2)
đại diện cho một phép toán boolean nào đó ví dụ như phép hợp hay phép
giao.
Trong phần này, chúng tôi đề cập đến vấn đề sử dụng cách tiếp cận
ngẫu nhiên dựa trên thuật toán di truyền: bắt đầu từ một tập quần thể (các cá
thể) của các lời giải có khả năng được xác định thông qua thuật toán vét cạn,
một quá trình lặp biến đổi các cá thể hiện tại và/hoặc tạo ra các cá thể mới
phù hợp với tập các toán tử di truyền được áp dụng một cách ngẫu nhiên. Các
cá thể tối thiểu hóa hàm giá có xu hướng thay thế các cá thể khác và sau một
Trang 48
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
số bước lặp đủ lớn, thì thuật toán có xu hướng hội tụ tới lời giải tối ưu. Trong
thực tế, mục đích chính của công việc này chính là để phát triển công cụ có
thể cho câu trả lời sơ bộ về vấn đề phân rã tối ưu của tập các phần tử cấu trúc
không lồi thành chuỗi các phép toán cơ sở.
Một số tính chất quan trọng của phép toán dãn ảnh
( ) ( ) ( )A B C A B A C
( ) ( ) ( )A B C A B A C
Như vậy, các phần tử cấu trúc không lồi được phân rã sử dụng chuỗi
phép hợp của tập phần tử cấu trúc lồi.
Dưới đây ta sẽ xét một ví dụ chứng tỏ sự ưu việt của việc phân rã các
phần tử cấu trúc lớn thành các phần tử cấu trúc nhỏ hơn.
Trong phép toán dãn ảnh để thực hiện phép dãn ảnh A B ta phải cần
thực hiện card(A)*card(B) phép toán. Giả sử A , B lần lượt là ma trận
(3)
Số phép toán cần thực hiện là 15.12=180 phép toán
Nhưng nếu bằng cách nào đó ta có thể phân rã tập B thành 2 tập con
nhỏ hơn như ví dụ dưới đây:
Và sử dụng luật kết hợp:
1 2 1 2 2( ) ( )R A B A B B A B B R B
(4)
Trang 49
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Trong đó:
Như vậy số phép tính để tính là: 15*3+25*4=145.
Ta xét một ví dụ khác đối với các phần tử cấu trúc không lồi. Như phần
trước đã trình bày, phần tử B không lồi có thể được biểu diễn thành chuỗi các
phần tử cấu trúc cơ bản liên kết với nhau bởi phép toán dãn ảnh và phép toán
logic.
1 2B C C
(5)
(6)
Trong đó, C1, C2 là các tập lồi trên tập các phần tử cấu trúc cơ bản cho
trước IS.
(7)
Do vậy, theo cách này, phép toán dãn ảnh của phần tử cấu trúc B tác
động lên ảnh A
1 2( )R A B A C C
(8)
có thể được thực hiện với 6 phép dãn cơ bản và 1 phép hợp logic. Đây là giải
pháp 1 mức, chỉ bao gồm một mức đơn của hợp các phép dãn, hay còn gọi là
tổng của các phép nhân. Hiển nhiên rằng, giải pháp đa mức có thể dẫn đến
một kết quả tốt hơn.
Trang 50
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Ví dụ việc sử dụng tính chất quy tắc của chuỗi R= A
B có thể được
biểu diễn theo giải pháp hai mức:
(9)
Giải pháp được mô tả ở trên chỉ đòi hỏi 5 phép dãn ảnh và một phép
hợp logic.
Một ứng dụng khác có thể liệt kê ra ở đây đó chính là việc lưu trữ. Ví
dụ như ta có một ảnh thể hiện một nét bút. Thay vì việc ta lưu trữ toàn bộ ảnh
của nét bút đó, ta chỉ cần lưu trữ các thành phần của nó. Một ví dụ khác, giả
sử ta muốn lưu trữ hình một chiếc bút, ta phân chia thành ba phần khác nhau:
đầu bút, thân bút và cuối bút. Ta xét thân bút để thấy rõ tại sao ta có thể lưu
trữ chiếc bút với ít bộ nhớ hơn. Do thân bút là bộ phận đều nhất theo nghĩa
hình khối, thay vì ta lưu trữ cả thân bút, ta chỉ cần lưu giữ chiều dài và chiều
rộng của thân bút. Như vậy tiết kiệm được không gian lưu trữ.
Qua các ví dụ ở trên, ta có thể thấy việc phân rã của các phần tử cấu
trúc có thể nhằm vào nhiều mục đích khác nhau như:
- Cực tiểu số các tập phân rã (để rút gọn số các phép dãn ảnh)
- Cực tiểu tổng số phép tính toán (nâng cao tốc độ);
- Cực tiểu tổng số phần tử trong tập phân rã (giảm kích cỡ cấu
trúc dữ liệu và do đó cũng giảm đòi hỏi về bộ nhớ trong hệ thống tuần tự;
Trang 51
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Khả năng cài đặt các phép toán hình thái phức tạp trện các hệ thống
song song mà tập các chỉ dẫn của nó được dựa vào phép toán cơ sở đơn giản
(để khắc phục vấn đề bị gây ra bởi kết nối tôpô bên trong mà nó giới hạn kích
thước các phần tử cấu trúc có thể có). Hoặc thậm chí là việc xác định các
nhân tử với hình dạng đã cho (nhằm trợ giúp cho việc nhận dạng các đối
tượng hai chiều).
Tiêu chuẩn tối ưu được nói tới trong luận văn này có thể thay đổi do tác
động các tham biến của hàm mục tiêu.
1. Tiếp cận ngẫu nhiên
Thuật toán di truyền (GAs) được sử dụng rộng rãi trong nhiều lĩnh vực,
là thuật toán tối ưu dựa trên thuật toán ngẫu nhiên, các toán tử di truyền trên
quần thể là các giải pháp có thể có của vấn đề được xem xét (các cá thể). Cấu
trúc dữ liệu chính là bộ gen (Genome) và nhiễm sắc thể (Chromosome) - là
tập bao gồm tập các Gen (Genes) và giá trị thích nghi (Fitness value). Trong
quần thể các lời giải có thể có, tập các cá thể mới được tạo ra bởi toán tử di
truyền được gọi l cá thể con.
Để đánh giá các cá thể trong mỗi thế hệ một hàm thích nghi được định
nghĩa để đo độ “thích nghi” của cá thể đó. Mỗi cá thể được cho là sẽ đem lại
một độ đo thích hợp về hệ số thích nghi của nó, có nghĩa là “mặt tốt” của lời
giải mà nó biểu diễn. Tại mỗi phép lặp (thế hệ) việc đánh giá hệ số thích nghi
được thực hiện trên tất cả các cá thể. Nên ở tại bước lặp tiếp theo, quần thể
mới được sinh ra, bắt đầu từ các cá thể có sự thích nghi cao nhất và thay thế
hoàn toàn hoặc một bộ phận của thế hệ trước. Các toán tử di truyền đã được
sử dụng để tạo ra các cá thể mới được chia nhỏ thành hai phạm trù chính:
phép toán một ngôi (unary) tạo ra các cá thể mới, thay thế các cá thể hiện tại
với kiểu đã được thay đổi (chẳng hạn như đột biến, sự thay đổi ngẫu nhiên
của gene), và phép toán hai ngôi (binary), tạo ra cá thể mới thông qua việc
Trang 52
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
kết hợp dữ liệu của hai cá thể (ví dụ như lai ghép, trao đổi nhiễm sắc thể giữa
hai cá thể). Mỗi bước lặp được gọi là một thế hệ.
Việc nghiên cứu thuật toán GAs dẫn đến nhiều chương trình tiến hoá
tổng quát (EPs) hơn , hay tổng quát hoá GAs. Trong các GAs chuẩn, một cá
thể được biểu diễn bởi bằng xâu nhị phân có độ dài cố định, mã hoá tập tham
số tương ứng với lời giải mà nó biểu diễn; toán tử di truyền tác động lên các
mã nhị phân này. Trong chương trình tiến hoá, các cá thể được biểu diễn bởi
cấu trúc dữ liệu tổng quát hoá mà không có sự bắt buộc về độ dài cố định.
2. Cấu trúc dữ liệu
Như phát biểu ở trên, cấu trúc dữ liệu biểu diễn một cá thể cần phải mô
tả theo cách mềm dẻo là hợp các phần tử lồi như trong, cần phải chỉ ra hình
dạng của nó và sự phân rã thành các phần tử (factors), nhưng cũng cần tạo ra
pha đánh giá nhanh và đơn giản. Biểu diễn này biến đổi theo độ dài, vì số z
các phân hoạch bao gồm việc phân rã nhiễm sắc thể J không bị chặn trên; mặt
khác nhắc lại biểu thức (1), số m và hình dạng nhân tử Fkj tạo nên thành phần
Ckj phụ thuộc trực tiếp vào Ck.
Vì những lý do này, một cá thể được biểu diễn bằng chuỗi gen dài tuỳ
ý, mỗi gen biểu diễn một phân hoạch của phần tử cấu trúc đầu vào (xem hình
IV.1). Hợp lôgic của tất cả các gen tạo nên cá thể.
Việc cài đặt đơn giản nhất bao gồm việc biểu diễn mỗi cá thể riêng với
cấu trúc dữ liệu mà các trường của nó chứa toàn bộ các thông tin ở trên.
Ngược lại, cấu trúc dữ liệu phân cấp phức tạp hơn được phát triển để vừa sử
dụng dung lượng nhớ thấp hơn cho mỗi cá thể vừa làm dễ dàng và tăng tốc độ
xác định các lời giải mới tốt hơn. Mặc dù việc quản lý cấu trúc dữ liệu này rõ
ràng là phức tạp nhưng nó cho phép phát hiện phần giao nhau có thể có trong
số các cá thể của quần thể. Mỗi mức phân cấp chỉ giải mã các thông tin thật
Trang 53
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
sự cần thiết cho mức độ đó. Ba mức phân cấp được chỉ ra trong Hình IV.1.
Mức phần tử (Factor level): Các thành phần cơ bản là các toán tử
hình thái cơ sở (tức các thành phần của tập chỉ dẫn): Một số nguyên cho biết
phần tử nào của tập chỉ dẫn được sử dụng, trong khi con trỏ cho phép đi
theo chuỗi các phần tử.
Mức độ gen (Gen level): Một gen gồm một hay nhiều các nhân tử
(factors) và ó tương ứng với một chuỗi các phép dãn của các nhân tử; một số
nguyên chỉ ra gốc của phân hoạch được mô tả bởi gen, vì vậy nó chỉ ra phép
dịch chuyển được yêu cầu để khớp gen lên tập các phần tử cấu trúc khởi tạo
và một con trỏ xác định gen tiếp theo.
Mức độ cá thể (Individual level): Một hay nhiều gen sẽ hình thành cá
thể tươngứng với một phép hợp của chuỗi các phép dãn, tương đương với
việc phân rã, hoặc thông thường hơn, đối với một phần của sự phân rã. Số
nguyên chỉ tổng số các gen hợp thành cá thể, con trỏ chỉ ra vị trí của gen đầu
tiên của chuỗi, trong khi số chính xác gấp đôi chứa giá trị thích nghi của cá
thể.
Khởi tạo quần thể
Định nghĩa 1: Tập IS là tập bao gồm M phần tử tử IS = {Fi, i=1,..,M}.
Tập IS trong đa trường hợp là biểu diễn các cấu trúc hình khối hoặc các cấu
trúc được chéo hoá. Việc sử dụng các cấu trúc hình khối hoặc được chéo hoá
sẽ tiết kiệm được không gian lưu trữ và đồng thời giảm được số phép toán cần
thực hiện trong các hệ thống đòi hỏi thao tác trên các ma trậm cỡ lớn.
Định nghĩa 2: Ký hiệu H(x,y) thay cho H
{(x,y)}
Trang 54
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình IV.1. Cấu trúc dữ liệu
Định nghĩa 3: Cho ảnh di truyền H. Ký hiệu
...nHAH H
(n thành phần, n≥0)
Định nghĩa 4: Cho ảnh di truyền H, OH biểu diễn gốc cuả ảnh di truyền
H.
Dưới đây, B là phần tử cấu trúc đầu vào, Bi là tập con di truyền của B
với gốc giống nhau và H đại diện cho bất kỳ tập di truyền nào, lồi tương ứng
với tập chỉ dẫn (IS).
1 1 2 2... ...i i M MH q F q F q F q F
(10)
Nếu OFi Fi đối với mỗi Fi thuộc tập chỉ dẫn, thì OH H. Việc xử lý
bắt đầu bằng cách nhận dạng mỗi phần tử của tập hợp C(B), được xác định
như sau:
(h,k)( ){H|HC B B
đối với vài (h,k)} (11)
Trang 55
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Vì mỗi phần tử của C(B) có thể đại diện cho một gen có thể có, việc
tìm kiếm này phải được xác định và vét cạn. Vì OFiFi, tập các cặp có thể
(h,k) được cho bởi tập tất cả những phần tử của B; đối với một ảnh di truyền
H, nếu cặp (h,k) B H, thì H(h,k) C(B). Vì vậy, thuật toán sẽ duyệt tất cả
các điểm ảnh của phần tử cấu trúc và xác định những phần tử nào có thể tạo
nên chuỗi phép toán dãn nở hợp lý từ điểm ảnh đó.
Xây dựng hàm thích nghi
Hàm thích nghi f(I) được sử dụng để đánh giá mỗi cá thể I trong thuật
toán tìm kiếm. Giả sử I được phân rã thành n phép hợp của các phần tử cấu
trúc hình khối B B1, ,...,2Bn thì:
1
( ) ( )
n
i
i
f I f B
với f(Bi) = (k+l) * AConst (12)
Trong đó AConst là một hằng số, đại lượng này sẽ tùy thuộc vào cỡ
của ma trận đem làm dầy với ma trận cấu trúc B ban đầu, (k,l) là cỡ của ma
trận Bi.
Trong cài đặt này, mỗi nhân tử bị giới hạn kích cỡ 3x3 và OFi Fi
Để đánh giá một cá thể I, ta dựa trên khái niệm hàm giá fC(I). fC(I) =
f(I) nếu và chỉ nếu B = { |i= 1, 2,... } , Bi là phân hoạch chung tạo nên lời giải
I của độ dài N. Hàm như vậy phải có một số tính chất sau:
1)Đối với lời giải phù hợp thì nó bằng f(I);
2)Nó cũng được xác định cho những lời giải không phù hợp (tức là
những lời giải không phủ hoàn toàn phần tử cấu trúc gốc), do vậy mở rộng
không gian tìm kiếm;
3)Dễ dàng cài đặt như hàm phạt.
Hàm phạt được sử dụng trong các bài toán có ràng buộc cao, khi nhu
Trang 56
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
cầu của việc đánh giá những lời giải không phù hợp bằng cách phạt chúng
đồng thời đề cao những lời giải phù hợp. Như vậy, hàm giá bao gồm hệ số
phạt:
fc = af(I) + bfp(I) (13)
ở đây, a = 1 nếu và chỉ nếu Bi = B(B={Bi|i=1,2,...N)}), như phát biểu trên,
ngược lại a có thể được biểu diễn bởi một phân số đối với tỉ số giữa số lượng
các phần tử có mặt trong lời giải và tổng các phần tử có trong B. Qua các
tham số do người sử dụng định nghĩa, hệ số b có liên hệ với kích cỡ của quần
thể hiện tại, và fp là hàm phạt liên hệ với số phần trăm phủ B.
Như ta đã nói mục đích của việc xử lý là nhận được sự phân rã làm cực
tiểu số các phép tính cần thiết để tính các phép dãn của một ảnh di truyền với
phần tử cấu trúc B, hàm thích nghi f(I) chủ yếu được cấu tạo bởi tổng giá của
mỗi phân hoạch Bj; thêm vào đó, cũng cần tính đến số phép toán hợp lôgic
được yêu cầu và làm nặng lên bởi một hệ số thích hợp.
3. Giải thuật dựa trên thuật toán tìm kiếm di truyền
Cấu trúc của thuật toán được và chu trình xử lý đơn gồm 4 giai đoạn:
+ Khởi tạo tập các cá thể con ban đầu;
+ Toán tử lựa chọn: Lựa chọn hai cá thể trong quần thể vì mục đích tái
tạo;
+ Toán tử di truyền hai ngôi: Kết hợp theo các cách khác nhau, các
nhiễm sắc thể của cha và mẹ để nhận được con (tức là một hoặc hai con);
+ Các toán tử so sánh: lập phép đấu giữa thế cha mẹ và thế hệ con để
chọn ra cá thể tốt nhất cho thế hệ tiếp theo;
Giải thuật có thể có điều kiện dừng khác nhau, có thể việc lựa chọn ra
hai cá thể với mục đích tái tạo dựa trên phép toán vét cạn, tức là mỗi cá thể đã
Trang 57
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
được lựa chọn để tái sinh, quần thể vừa mới được tạo ra trải qua cùng một
cách xử lý giống nhau: Quá trình hình thành các thế hệ này ngừng khi số thế
hệ đã đạt tới một giá trị cực đại. Mặt khác ta có thể chia không gian cá thể tại
mỗi thế hệ thành một số tập con rồi sau đó thực hiện lựa chọn ngẫu nhiên một
số cá thể con trong tập được phân chia. Việc phân chia đó để đảm bảo tính
ngẫu nhiên của thuật toán. Dưới đây tóm tắt lại các toán tử đã được trình bày:
Khởi tạo tập cá thể con ban đầu
Các cá thể con ở thế hệ thứ nhất chính là tập IS ban đầu. Nhớ rằng tập
IS này là tập các phần tử cấu trúc hình khối. Đối với ảnh nhị phân B ban đầu,
tập các cá thể khối là con của tập B có thể được tìm kiếm bằng cách duyệt
từng điểm ảnh của B và tìm tất cả các cấu trúc hình khối có thể được xây
dựng từ điểm gốc đó.
Đối với các ma trận kích thước lớn, ta có thể lựa chọn ngẫu nhiên một
số điểm ảnh trong ma trận B, từ các điểm ảnh đó ta sẽ xác định các cá thể ban
đầu.
Toán tử lựa chọn
Trong bài , nhóm tác giả Giovanni Anelli, Alberto broggi và Giulioi
Destri đưa ra toán tử dựa trên sơ đồ lựa chọn thi đấu như đã được đưa ra trong
luận án tiến sỹ của tác giả R. Van Den Boomgard “Extension toward
Computer vision, PhD thesis” với kích thước vòng đấu của hai bên. Sơ đồ cài
đặt tận dụng một phiên bản được hiệu chỉnh nhỏ của kỹ thuật đám đông lựa
chọn di truyền (genic selective crowding) buộc các cá thể thi đấu với cá thể
khác có ít nhất các điểm ảnh chung. Theo cách như vậy, một áp lực được duy
trì làm cho đối tượng giống nhau thi đấu với đối tượng giống nhau, và bằng
cách này làm tăng ý nghĩa của vòng đấu. Tuy nhiên cách tiếp cận này, theo tôi
là khó cài đặt và tốc độ hội tụ chậm do tính tổng quát của nó. Nhớ lại rằng
Trang 58
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
mục đích của chúng ta là phân rã ảnh nhị phân thành tổng các thành phần khối
hoặc các thành phần chéo hoá và từ các thành phần này ta sẽ xây dựng được
dãy tích các thành phần cấu trúc cơ bản phục vụ cho việc lưu trữ hoặc trong
việc tăng tốc độ tính toán. Vì vậy, theo tôi các cá thể ban đầu là tối quan
trọng, tại mỗi thế hệ để đảm bảo thuật toán
có thể đi tới một kết quả chấp nhận được thì việc lai tạo giữa cá thể hiện thời
với các cá thể ở thế hệ thứ nhất như là một đảm bảo thế hệ tiếp theo sau tốt
hơn thế hệ hiện thời.
Các toán tử di truyền hai ngôi
Để nhận được các cá thể phủ phần tử cấu trúc trong pha khởi tạo, chúng
ta cần một toán tử biến đổi một cách đáng kể độ dài các nhiễm sắc thể của cá
thể. Ngược lại, sau pha này khi độ dài trung bình của các cá thể xấp xỉ với cá
thể tối ưu, chúng ta quan tâm về chất lượng của nhiễm sắc thể; vì lý do này,
hai toán tử khác nhau đã được hình thành.
Toán tử đầu tiên dựa trên toán tử cắt và ghép nối. Cho λ là số gen tạo
nên nhiễm sắc thể: Toán tử này cắt ngẫu nhiên nhiễm sắc thể tương ứng với
một trong λ điểm có thể. Nếu một trong λ-1 điểm nối hai gen liên tục được
chọn, thì nhiễm sắc thể bị tách thành hai phần; ngược lại với xác suất 1/λ,
không thay đổi. Hai, ba hoặc bốn đoạn nhiễm sắc thể của hai cá thể khác nhau
được đặt trong ngăn xếp (stack); giai đoạn lai ghép hoặc hợp hai phần tử đầu
tiên ở đỉnh ngăn xếp này theo cách này tạo nên một con đơn nhất, hoặc cải
biến mỗi phần tử thành cá thể đầy đủ. Điều này chỉ ra cách mà số cá thể trong
thế hệ theo sau có thể được thay đổi. Ví dụ được chỉ ra trong hình IV.2
Trang 59
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình IV.2 Ví dụ về cắt và ghép nối
(a)Lai ghép thay thế, (b)Các toán tử
Toán tử so sánh
Ở giai đoạn này toán tử lựa chọn trong số các bố mẹ và con những cá
thể được chèn vào trong thế hệ tiếp theo.Trong [8], tác giả X. Zhuang và R.M.
Haralick đưa ra một sơ đồ dựa trên sơ đồ đa số quyết định.
Toán tử di truyền một ngôi
Trong GA chuẩn toán tử một ngôi là sự đột biến, nó chỉ đảo ngẫu nhiên
một hay nhiều bit của xâu biểu diễn nhiễm sắc thể. Mặt khác cài đặt của
chúng ta về phép đột biến có mục tiêu chủ yếu là chèn lại các gen đã bị bỏ
trước đó và những gen bị mất; Tiêu biểu đây là trường hợp phân hoạch nhỏ
mà sự đóng góp của nó để cải thiện hệ số thích nghi bị đánh giá thấp trong
pha thực hiện trước. Đóng góp này có thể là cần sau này để đạt được phủ của
toàn bộ B. Gen được rút ra từ mảng gen (chứa tất cả các gen có thể) và được
lưu trữ trong bộ nhớ để cho mỗi gen được lựa chọn theo chu kỳ. Hai toán tử
đã được tạo:
Đột biến 1: Toán tử này so sánh mỗi gen tạo ra nhiễm sắc thể của các
cá thể với gen g của mảng. Gen g thay thế một gen giống nhất trong chuỗi, đó
là gen làm cực đại phần giao giữa hai gen như ví dụ dưới đây.
Trang 60
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Đột biến 2: Toán tử này buộc gen g phải được tính đến việc loại bỏ các
gen trùng lên nó. Nó có thể làm cho kém thích nghi nhưng nó có lợi để tăng
sự đa dạng của nhiễm sắc thể như trong ví dụ dưới đây
Giả sử ta có phần tử cấu trúc B được định nghĩa :
{( , , ( , )) : 1, , 1, }B x y f x y x m y n
trong đó:
2( , ) : {0,1}f x y Z
Ta xây dựng mã giả của thuật toán như sau:
Mã giả (presedo-code)
//initialize population
P:={};
For each (x,y) in B :
Determine Trange={T:T is trange and T B };
Add(P,T);// add all the elements of T to P
//Choose randomly a number of elements in P
Initilize randomly Q = { :q q P} ; numGen=0;
Loop until numGen> threshold
Choose some(A,B) Q2: Make offspring A1,A2,B1,B2 between A and
Trang 61
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
B
Calculate fitness values of A1,A2,B1,B2
Add A1,A2,B1,B2 into current genration
Q:={}, Choose the best individuals in current generation to make next
generation
numGen++;
if(best(individual)= =B) exit;
End Loop;
Print best(individual);
Trang 62
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
CHƢƠNG V. THỰC NGHIỆM
Trong chương này, tôi sẽ trình bày cấu trúc của chương trình thực
nghiệm và một số kết quả dựa trên thuật toán đã đưa ra trong chương IV
1. Mô tả bài toán và giả thuyết
Ma trận phần tử cấu trúc đầu vào là ma trận có kích thước mxn được
nhập từ file. Cấu trúc của file được mô tả dưới đây:
- Dòng đầu bao gồm 2 số nguyên thể hiện kích thước của ma trận
- Bắt đầu từ dòng thứ 2 đến dòng thứ n biểu diễn các giá trị tại mỗi
điểm ảnh. Các giá trị điểm ảnh được phân biệt với nhau bởi dấu tab.
Với giả thuyết phân rã ma trận cấu trúc ban đầu thành các phần tử cấu
trúc kích thước 3x3. Kết quả cũng được lưu trữ dưới dạng file.
2. Giao diện chính của chƣơng trình
Bước đầu, người dùng cần nhập vào file chứa thông tin về phần tử cấu
trúc bằng cách nhấp vào nút “Nhập từ file” trên màn hình giao diện, sau đó
chỉ tới nơi chứa file text chứa ma trận đầu vào.
Sau khi kết thúc phần chọn file dữ liệu đầu vào, người dùng chọn các
Trang 63
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
tùy chọn, bao gồm: số thế hệ cá thể được sinh ra, số lượng cá thể lấy ngẫu
nhiên tại mỗi thế hệ để thực hiện việc tạo ra các thế hệ tiếp sau, hệ số phạt.
Cuối cùng người dùng nhấp vào nút phân rã để thực hiện việc phân rã
ma trận đầu vào thành các ma trận với kích thước nhỏ hơn. Kết quả sẽ được
lưu vào file C:\\result.txt và được pop-up ra ngoài màn hình.
3. Một số kết quả thử nghiệm
Trong phần thực nghiệm này, ta sử dụng hàm mục tiêu được định nghĩa
như sau:
( ) ( ) ( )c pf I af I bf I
Ta xét với
( )
( )
card I
a
card B
, b=1 và AConst = 10
( ( ) ( ))
( ) *40
( )
p
abs card I card B
f I
card B
Trong các ví dụ sau, ta quy ước phép toán làm béo có độ ưu tiên cao
hơn phép lấy hợp.
Trang 64
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
3. Một số kết quả thử nghiệm
Trong phần thực nghiệm này, ta sử dụng hàm mục tiêu được định nghĩa
như sau:
( ) ( ) ( )c pf I af I bf I
Ta xét với
( )
( )
card I
a
card B
, b=1 và AConst = 10
( ( ) ( ))
( ) *40
( )
p
abs card I card B
f I
card B
Trong các ví dụ sau, ta quy ước phép toán làm béo có độ ưu tiên cao
hơn phép lấy hợp.
Ví dụ 1. ta xét ví dụ đầu tiên với ma trận B có dạng như sau
Thử nghiệm trên bộ xử lý pentum 4 tốc độ 3.0GHz, 512 MB RAM.
Thời gian chạy chương trình 2 phút. Ta thu được kết quả như sau:
Ma trận B phân rã được thành hợp của 6 phần tử cấu trúc khối
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Trang 65
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Như vậy chuỗi phân rã của B dưới dạng các phần tử cấu trúc kích thước
3x3 sẽ như sau:
0 0 0 1 0 0 0 0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 1 0 0 0 0 0
1 1 1 1 0 0 1 1 1 1 0 0 1 1 1
1 1 0 0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 1 1 1 1 0 1 1 1
B
2
1 1 1 1 0 1 1 0 0 1 0 0
0 0 0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0 0 0
Ví dụ 2. Giả sử ma trận B là ma trận cỡ 9x9 có dạng sau
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 0 0
1 1 1 0 0 0 0 0 0
1 1 1 1 0 0 1 0 0
1 1 1 1 0 0 1 0 0
1 1 1 1 1 0 0 1 1
1 1 1 1 1 0 0 1 1
Ma trận B được phân rã thành hợp các phần tử cấu trúc hình khối sau:
0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Trang 66
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0
Tương tự như vậy chuỗi phân rã của B dưới dạng các phần tử cấu trúc
kích thước 3x3 sẽ như sau
2
2
0 1 0 0 0 0 1 1 1 1 0 1 1 1 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 1 1 0 0
0 1 1 0 1 0 0 1 1 0 0 1 1 0 0
0 1 1 0 1 0 0 0 0 0 0 0 1 0 0
B
2
1 0 0 1 1 1
0 0 0 0 0 0
1 0 0 0 0 0
Trang 67
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
VI. KẾT LUẬN
Trong khuôn khổ của luận văn này, tôi đã trình bày một cách có hệ
thống các khái niệm từ cơ bản đến nâng cao trong việc ứng dụng phép toán
hình thái trong xử lý ảnh. Đồng thời, tôi cũng trình bày các khái niệm cơ bản
nhất của thuật toán di truyền. Phần quan trọng nhất là trình bày một tiếp cận
để phân rã các phần tử cấu trúc hình thái nhị phân có dạng tuỳ ý thành chuỗi
các nhân tử cơ bản sử thuật toán di truyền. Việc áp dụng của kỹ thuật này đối
với phần tử cấu trúc lồi đã chỉ ra phân rã tối ưu đã được thảo luận trong tài
liệu. Ngoài ra luận văn này cũng cung cấp một cách phân rã các phần tử cấu
trúc không lồi.
Đối với các ma trận lớn, thuật toán lộ rõ nhược điểm là thời gian chạy
chương trình là khá lớn. Một trong các cách giải quyết là xây dựng các thuật
toán song song để có thể chạy được trên các máy tính đa CPU. Việc phân rã
được quản lý bởi tiến trình “chủ”, mà tiến trình này sinh ra các tiến trình con
trên các nút khác nhau của các cụm trạm làm việc; mỗi tiến trình con gánh
vác một phần riêng đặc thù của công việc xử lý, mà tiến trình đó được thực
hiện song song với tất cả các tiến trình khác. Việc cài đặt song song cho phép
nâng cao tốc độ xử lý và phân rã các phần tử cấu trúc rất lớn.
Do giải pháp là dựa trên cách tiếp cận ngẫu nhiên nên mỗi lần thực hiện
thuật toán kết quả có thể ra là khác nhau, do đó độ “tốt” của mỗi phân rã do
đó mà khác nhau. Người dùng có thể thực hiện việc phân rã nhiều lần, sau đó
chọn lấy một cách phân rã tối ưu nhất. Điều này có thể thực hiện được dựa
trên hàm mục tiêu.
Trang 68
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Tài liệu tham khảo
[1] P. Angeline, G. Saunders, and J. Pollack, “An Evolutionary Algorithm.
That Constructs Recurrent Neural Networks,” IEEE Trans. Neural Networks,
vol. 5, pp. 54-65, Jan. 1994.
[2] A. Broggi, “ Speeding-Up Mathematical Morphology Computations with
Special-Purpose Array Processors,” Proc. 27th Hawaii Int’l Conf. System
Sciences, T.N. Mudge and B.D. Shriver, eds., vol. 1, pp. 321-330, Maui,
Hawaii, Jan. 4-7 1994. Los Alamitos, Calif.: IEEE Computer Society.
[3] E. Falkenauer, “A New Representation and Operators for Genetic
Algorithms Applied to Grouping Problems,” Evolutionary Computation, vol. 2
no. 2, 1994.
[4] Giovanni Anelli, Alberto Broggi, Giulio Destri, "Decomposition of
Arbitrarily Shaped Binary Morphological Structuring Elements Using Genetic
Algorithms," IEEE Transactions on Pattern Analysis and Machine
Intelligence, vol. 20, no. 2, pp. 217-224, Feb., 1998.
[5] Marcos Quintana, “Genetic programming applied to morphological image
processing”, PhD thesis, pp. 9-30, 2004.
[6] D.E. Goldberg, B. Korb, and K. Deb, “Messy Genetic Algorithms:
Motivation, Analysis, and First Results,” Complex Systems, vol. 3, pp. 493-
530, 1989.
[7] D.E. Goldberg, B. Korb, and K. Deb, “Messy Genetic Algorithms
Revisited: Studies in Mixed Size and Scale,” Complex Systems, vol. 4, pp.
415-444, 1990.
[8] R.M. Haralick, S.R. Sternberg, and X. Zhuang, “ Image Analysis Using
Mathematical Morphology,” IEEE Trans. Pattern Analysis and Machine
Intelligence, vol. 9, no. 4, pp. 532-550, Apr. 1987.
[9] J. Holland, Adaption Natural and Artificial Systems. Ann Arbor, Mich.:
Univ. of Michigan Press, 1975.
Trang 69
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
[10] S.W. Mahfoud, “Crossover Interactions Among Niches,” Proc. First
IEEE Conf. on Evolutionary Computation, pp. 188-193, 1994.
[11] G. Matheron, Random Sets and Integral Geometry. New York: John
Wiley, 1975.
[12] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution
Programs. Berlin: Springer-Verlag, 1992.
[13] H. Park and R.T. Chin, “Optimal Decomposition of Convex Structuring
Elements for a 4-Connected Parallel Array Processor,” IEEE Trans. Pattern
Analysis and Machine Intelligence, vol. 16, no. 3, Mar. 1994.
[14] H. Park and R.T. Chin, “Decomposition of Arbitrarily Shaped
Morphological Structuring Elements,” IEEE Trans. Pattern Analysis and
Machine Intelligence, vol. 17, no. 1, Jan. 1995.
[15] J. Serra, Image Analysis and Mathematical Morphology. London:
Academic Press, 1982.
[16] M. Srinivas and L. Patnaik, “Adaptive Probabilities of Crossover and
Mutation in Genetic Algorithm,” IEEE Trans. System, Man, and Cybernetics,
vol. 24, no. 4, Apr. 1994.
[17] R. van den Boomgaard, Mathematical Morphology: Extensions Towards
Computer Vision, PhD thesis, Universiteit Van Amsterdam, 1992.
[18] R. van den Boomgaard and R. van Balen, “Methods for Fast
Morphological Image Transforms Using Bitmapped Binary Images,”
Computer Vision, Graphics, and Image Processing: Graphical Models and
Image Processing, vol. 54, no. 3, pp. 252-258, May 1992.
[19] S.S. Wilson, “ Theory of Matrix Morphology,” IEEE Trans. Pattern
Analysis and Machine Intelligence, vol. 14, no. 6, pp. 636-652, June 1992.
[20] X. Zhuang and R.M. Haralick, “Morphological Structuring Element
Decomposition,” Computer Vision, Graphics, and Image Processing, vol. 35,
pp. 370-382, Sept. 1986.
Trang 70
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
[21] N. R. Harvey. New Techniques for the Design of Morphological Filters
using Genetic Algorithms. PhD thesis, University of Strathclyde, Glasgow,
UK, 1997.
[22] N. R. Harvey and S. Marshall. Mathematical Morphology and Its
Applications to Image Procesing, chapter Using Genetic Algorithms in the
Design of Morphological Filters, pages 53-59. Kluwer Academic Publishers,
1994.
[23] N. R. Harvey and S. Marshall. Rank-order morphological _lters: A new
class of _lters. In IEEE Workshop on nonlinear signal and image processing,
pages 975-978,Halkidiki, Greece, 1994.
[24] N. R. Harvey and S. Marshall. The use of genetic algorithms in
morphological _filter design. Signal Processing: Image Communication,
8(1):55-72, Jan 1996.
[25] M. Yu, N. Eua-anant, A. Saudagar, and L. Udpa. Genetic algorithm
approach to image segmentation using morphological operations. In
International Conference on Image Processing, volume 3, pages 775-779,
1998.
[26] GONALEZ RC WOOD, Digital image processing, 2002 by Prentice Hall
Upper Saddle River, New Jersey, Chapter 9.
Các file đính kèm theo tài liệu này:
- 8LV09_CNTT_KHMTPhamDangTu.pdf