Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
ĐẠ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 Trang 1
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

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 http://www.lrc-tnu.edu.vn

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

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.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 http://www.lrc-tnu.edu.vn

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 http://www.lrc-tnu.edu.vn


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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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 http://www.lrc-tnu.edu.vn


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 http://www.lrc-tnu.edu.vn

*

đườ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 http://www.lrc-tnu.edu.vn

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ẽ

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 http://www.lrc-tnu.edu.vn

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 http://www.lrc-tnu.edu.vn

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.


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 Z
2
. Nếu a = (a1,a2) là một phần tử của A, thì
ta kí hiệu là:

aA

Trang 18
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Tương tự như vậy, trong trường hợp a không phải là phần tử con của A Trang 19
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

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.
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 http://www.lrc-tnu.edu.vn


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.

Trích đoạ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 Tiếp cận ngẫu nhiên Cấu trúc dữ liệu

---