B ộ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI
HỌC
s ư PHẠM
HÀ NỘI
2
•
•
•
•
===#oljDlGa===

NGUYỄN ĐỨC TOÀN

NGHIÊN CỨU PHƯƠNG PHÁP PHÂN ĐOẠN ẢNH
VÀ ỨNG DỤNG CHO ẢNH TÀI LIỆU

Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01 01

LUẬN VĂN THẠC SĨ MÁY TÍNH
Người hướng dẫn khoa học: PGS. TS. NGÔ QUỐC TẠO

HÀ NỘI, 2015


1

LỜI CẢM ƠN

Trong thời gian thực hiện luận văn thạc sỹ em đã nhận được rất nhiều

3

MỤC LỤC

MỞ ĐẦU........................................................................................................ 8
1. Lý do chọn đề tà i........................................................................................ 8
2. Mục đích nghiên cứu.................................................................................. 8
3. Nhiệm vụ nghiên cứu................................................................................. 8
4. Đổi tượng và phạm vi nghiên cứu.............................................................9
5. Phương pháp nghiên cứu...........................................................................9
CHƯƠNG 1: KHẮT NIỆM VỀ PHÂN ĐOẠN ẢNH...............................11
1.1. Xử lý ảnh, các vấn đề cơ bản trong xử ỉý ảnh................................... 11
1.2. Quá trình xử lý ảnh..............................................................................11
1.2.1. Thu nhận ảnh (Image Acquisition)___________________________13
1.22. Tiền xửỉý (Image Processing).....................................................................14
1.23. Phân đoạn (Segmentation) hay phân vùng ảnh_________________ 14
1.2A. Biểu diễn ảnh (Image Representation) ......................................................15
1.2.5. Nhận dạng và nội suy ảnh (Image Recognition and Interpretation)....15
1.2.6. Cơ sở tri thúc (Knowledge Base) ................................................................16
1.2.7. Mô tả ảnh........................................................................................... 16
1.3. Phân đoan ảnh..................................................................................... 19
1.3.1. Điểm ảnh (Picture Element)________________________________ 19
132. Độ phân giải của ảnh_____________________________________ 20
1.33. Múc xám của
1.3.4. Quan hệ giữa các điểm ảnh .........................................................................21
1.3.4.1. Các lân cận của điểm ảnh (Image Neighbors).............................21
1.3.4.2. Khoảng cách giữa các điểm ảnh...................................................22
1.3.4.3. Các thành phần cơ bản của hệ thống xử lý ảnh......................... 24
1.3.5. Những vấn đề khác trong xử lý ảnh................................................25


•
3.1.

Yêu cầu bài toán: Giải quyết bài viết của học sinh.......................80

3.2. Cách giải quyết yêu cầu của bài toán................................................. 80
3.3. Xây dựng DEMO.................................................................................. 80
3.3.1. Giao diên chính;.................................................................................. 80
■

3.3.2. Nhập hình ảnh..................................................................................... 81
3.3.3. Sử dụng thuật toán Gray................................................................... 81
3.3.4. Sử dụng thuật toán Segmentation.................................................... 82


5

3.3.5. Sử dụng thuật toán Sobel.................................................................. 82
3.4. So sánh vói ảnh phong cảnh.............................................................. 83
3.4.1. Giao diện chính................................................................................... 83
3.4.2. Nhập hình ảnh.................................................................................... 83
3.4.3. Sử dụng thuật toán Gray................................................................... 84
3.4.4. Sử dụng thuật toán Segmentation.................................................... 84
3.4.5. Sử dụng thuật toán Sobel.................................................................. 85
KẾT LUẬN VÀ KIÉN NGHỊ..................................................................... 86
TÀI LIỆU THAM KHẢO........................................................................... 87


6


Bảng 2.9. Giả mã thuật toán và gán nhãn cho các thành phàn liên thông.... 76
Bảng 2.10 ứng dụng thuật toán gán nhãn cho các thành phần liên thông ..78


8

MỞ ĐẦU
1. Lý do chọn đề tài
Trong những năm gần đây công nghệ thông tin phát triển với tốc độ
nhanh chóng. Sự phát triển của công nghệ thông tin đã thúc đẩy sự phát triển
của nhiều lĩnh vực xã hội khác như: y học, giáo dục, giải trí, kinh tế...
Lĩnh vực xử lý ảnh cũng như công nghệ thực tại ảo đã ra đời và thâm
nhập mạnh mẽ vào đời sống của con người.
Anh thu được sau qua trình thu nhận ảnh hoặc các phép biến đổi không
tránh khỏi nhiễu hoặc khuyết thiếu. Sự sai sót này một phần bởi các thiết bị
quang học và điện tử, phần khác bởi bản thân các phép biến đổi không phải là
toàn ánh, nên có sự ánh xạ thiếu hụt đến những điểm trên ảnh kết quả.
Việc khắc phục các nhược điểm này luôn là vấn đề đặt ra cho các hệ
thống xử lý ảnh vì vậy các nhà khoa học đã phân đoạn ảnh ra để làm rõ nét
hơn cho bức ảnh cần xử lý và tăng cường nâng cao chất lượng ảnh.
Xuất phát trong hoàn cảnh đó “Nghiên cứu phương pháp phân đoạn
ảnh và ứng dụng cho ảnh tài liệu” được em chọn làm đề tài.
2. Mục đích nghiên cứu
Tìm hiểu tổng quan về phân đoạn ảnh, các phương pháp phân đoạn ảnh
và chọn ra phương pháp phân đoạn ảnh cụ thể.
Trên cơ sở các kiến thức đã thu thập và nghiên cứu, tổng họp các kỹ
thuật để hướng đến các ứng dụng thực tế phân đoạn cho ảnh tài liệu.
3. Nhiệm vụ nghiên cứu
Tìm hiểu khái niệm phân đoạn ảnh.
Các phương pháp phân đoạn ảnh.

- Yêu càu bài toán: Giải quyết bài viết của học sinh.
- Đặc thù của ảnh sau khi phân đoạn: là ảnh đen trắng (ảnh đơn màu).
- Thử nghiệm với các dữ liệu.


11

CHƯƠNG 1: KHÁI NIỆM VÈ PHÂN ĐOẠN ẢNH
1.1. Xử lý ảnh, các vấn đề cơ bản trong xử lý ảnh.
Con người thu nhận thông tin qua các giác quan, ừong đó thị giác đóng
vai trò quan trọng nhất. Xử lý ảnh là một lĩnh vực mang tính khoa học và
công nghệ. Những năm ừở lại đây với sự phát triển của phần cứng máy tính,
xử lý ảnh và đồ hoạ đó phát triển một cách mạnh mẽ và có nhiều ứng dụng
trong cuộc sống. Xử lý ảnh và đồ hoạ đóng một vai trò quan trọng trong
tương tác người và máy.
Quá trình xử lý ảnh là một quá trình thao tác nhằm phân tích, biến đổi
một ảnh đầu vào để đưa ra một kết quả mong muốn. Kết quả của quá trình xử
lý ảnh có thể là một ảnh tốt hơn hoặc một kết luận. Điều này tùy thuộc vào
mục đích yêu càu của quá trình. Như vậy, mục tiêu của xử lý ảnh có thể phân
làm ba hướng như sau:
■ Xử lý ảnh ban đầu để có được một ảnh mới theo yêu cầu xác định (ví
dụ như ảnh mờ cần xử lý để được ảnh rõ hơn, lọc nhiễu, phân đoạn
ảnh để lấy được những yêu cầu cần thiết...).
■ Phân tích ảnh để thu được các thông tin đặc trưng giúp cho việc phân
loại, nhận dạng ảnh (Ví dụ như phân tích nhận dạng vân tay, nhận
dạng chữ viết, nhận dạng ảnh tài liệu...).
■ Đưa ra một kết luận ở mức cao hơn, sâu hơn (ví dụ như tò ảnh một tai
nạn giao thông phác họa hiện trường tai nạn...
1.2. Quá trình xử lý ảnh
Xử lý ảnh là một lĩnh vực mang tính khoa học và công nghệ, là một

Camera, máy chụp ảnh). Trước đây, ảnh thu qua Camera là các ảnh tương tự
(loại Camera ống kiểu CCIR). Gần đây, với sự phát triển của công nghệ, ảnh
màu hoặc đen ừắng được lấy ra tò Camera, sau đó nó được chuyển trực tiếp
thành ảnh số tạo thuận lợi cho xử lý tiếp theo. (Máy ảnh số hiện nay là một thí


13

dụ gần gũi). Mặt khác, ảnh cũng có thể tiếp nhận tò vệ tinh; có thể quét từ ảnh
chụp bằng máy quét ảnh.
Các phương pháp xử lý ảnh bắt đàu từ các ứng dụng chính như nâng
cao chất lượng ảnh và phân tích ảnh.
Do vậy, quá trình xử lý ảnh bao giờ cũng bắt đàu bằng công việc thu
nhận ảnh và kết thúc là việc nhận dạng ảnh hoặc một phán đoán theo ý nghĩa
trên cơ sở nhận dạng ảnh. Cụ thể, các bước cơ bản trong quá trình xử lý ảnh
được thể hiện thông qua hình dưới đây:

Hình 1.1 Các bước cơ bản trong xử lỷ ảnh
1.2.1. Thu nhận ảnh (Image Acquisition)
Đây là bước đầu tiên trong quá ừình xử lý ảnh. Đầu ra của giai đoạn
này là ảnh đã được số hoá. Vì vậy, công việc cụ thể ở giai đoạn này là thu ảnh
qua một bộ thu ảnh và số hoá những tín hiệu liên tục được sinh ra bởi bộ thu
ảnh đó.
Bộ thu ảnh có thể là máy chụp ảnh đơn sắc hay màu, máy quét ảnh,
máy quay... Nếu bộ thu ảnh cung cấp chưa phải dạng số hoá thì phải chuyển
đổi hay số hoá ảnh.
Anh có thể nhận qua camera màu hoặc đen ừắng. Thường ảnh nhận qua
camera là ảnh tương tự (loại camera ống chuẩn CCIR với tần số 1/25, mỗi ảnh
25 dòng), cũng có loại camera đã số hoá (như loại CCD - Change Coupled
Device) là loại photodiot tạo cường độ sáng tại mỗi điểm ảnh. Camera thường

điểm ảnh thuộc về chính vùng ảnh đó. Trong cả hai trường hợp, sự chuyển đổi


15

dữ liệu thô này thành một dạng thích họp hơn cho việc xử lý trong máy tính là
hết sức cần thiết, nghĩa là nên biểu diễn một vùng ảnh dưới dạng biên hay
dưới dạng một vùng hoàn chính gồm tất cả những điểm ảnh thuộc về nó.
1.2.4. Biểu diễn ảnh (Image Representation)
Đầu ra ảnh sau phân đoạn chứa các điểm ảnh của vùng ảnh (ảnh đã
phân đoạn) cộng với mã liên kết với các vùng lận cận. Việc biến đổi các số
liệu này thành dạng thích họp là cần thiết cho xử lý tiếp theo bằng máy tính.
Việc chọn các tính chất để thể hiện ảnh gọi là trích chọn đặc trưng (Feature
Selection) gắn với việc tách các đặc tính của ảnh dưới dạng các thông tin định
lượng hoặc làm cơ sở để phân biệt lớp đối tượng này với đối tượng khác trong
phạm vi ảnh nhận được.
Ví dụ: trong nhận dạng ký tự trên phong bì thư, chúng ta miêu tả các
đặc trưng của từng ký tự giúp phân biệt ký tự này với ký tự khác.
Anh sau khi số hoá sẽ được lưu vào bộ nhớ hoặc chuyển sang các khâu
tiếp theo để phân tích. Nếu lưu trữ ảnh trực tiếp tò các ảnh thô đòi hỏi dung
lượng bộ nhớ rất lớn và không hiệu quả theo quan điểm ứng dụng và công
nghệ. Thông thường, các ảnh thô đó được biểu diễn lại theo các đặc điểm của
ảnh được gọi là các đặc trưng ảnh như: biên ảnh, vùng ảnh. - Biểu diễn dạng
biên cho một vùng phù họp với những ứng dụng chỉ quan tâm đến các đặc
trưng hình dạng bên ngoài của đối tượng.
Ví dụ như các góc cạnh và điểm uốn trên biên.
Biểu diễn dạng vùng thích hợp cho những ứng dụng khai thác các tính
chất bên trong của đối tượng. Ví dụ như vân ảnh hoặc cấu trúc xương của nó.
Trong một số ứng dụng thì cả hai cách biểu diễn trên đều cần thiết.
1.2.5. Nhận dạng và nội suy ảnh (Image Recognition and Interpretation)

(hay đơn giản là mã hoá) theo các đặc điểm của ảnh được gọi là các đặc trưng
ảnh (Image Features) như: biên ảnh (Boundary), vùng ảnh (Region). Một số
phương pháp biểu diễn thường dùng:


17

• Biểu diễn bằng mã chạy (Run-Length Code)
• Biểu diễn bằng mã xích (Chaîne -Code)
• Biểu diễn bằng mã tá phân (Quad-Tree Code)
- Biểu diễn bằng mã chạy
Phương pháp này thường biểu diễn cho vùng ảnh và áp dụng cho ảnh nhị
phân. Một vùng ảnh R có thể mã hoá đơn giản nhờ một ma trận nhị phân:
U(m, n) = 1 nầi (m, n) thuộc R
U( m,n) = 0 nếu (m, n) không thuộc R
Trong đó: Uịm n), là hàm mô tả mức xám ảnh tại tọa độ (m, n). Với cách
biểu diễn trên, một vùng ảnh được mô tả bằng một tập các chuỗi số 0 hoặc 1.
Giả sử chứng ta mô tả ảnh nhị phân của một vùng ảnh được thể hiện theo toạ
độ (x, y) theo các chiều và đặc tả chỉ đối với giá trị “1 ” khi đó dạng mô tả có
thể là: (x, y)r; trong đó (x, y) là toạ độ, r là số lượng các bit có giá ừị “1 ” liên
tục theo chiều ngang hoặc dọc.
- Biểu diễn bằng mã xích
Phương pháp này thường dùng để biểu diễn đường biên ảnh. Một đường
bất kỳ được chia thành các đoạn nhỏ. Nối các điểm chia, ta có các đoạn thẳng
kế tiếp được gán hướng cho đoạn thẳng đó tạo thành một dây xích gồm các
đoạn. Các hướng có thể chọn 4, 8, 12, 24... mỗi hướng được mã hoá theo số
thập phân hoặc số nhị phân thành mã của hướng.
- Biểu diễn bằng mã tứ phân
Phương pháp mã tứ phân được dùng để mã hoá cho vùng ảnh. Vùng ảnh
đầu tiên được chia làm bốn phần thường là bằng nhau. Nếu mỗi vùng đã đồng

Thống
K ê/
Ấ
cau
trúc

Số
hóa

ỉ ’
Ả nh tương tự

Mô
tả
và
-----► N ôi
suy

Thu nhận ảnh

>

>

r

Hình 1.2 Sơ đô phân tích và xử lý ảnh và lưu đô thông tin giữa các khôi


19

20

và mức xám (hoặc màu) của ảnh số gần như ảnh thật. Mỗi phần tử trong ma
trận được gọi là một phần tử ảnh.
1.3.2. Độ phân giải của ảnh
Định nghĩa
Độ phân giải (Resolution) của ảnh là mật độ điểm ảnh được ấn định
trên một ảnh số được hiển thị.
Theo định nghĩa, khoảng cách giữa các điểm ảnh phải được chọn sao
cho mắt người vẫn thấy được sự liên tục của ảnh. Việc lựa chọn khoảng cách
thích họp tạo nên một mật độ phân bổ, đó chính là độ phân giải và được phân
bố theo trục X , y trong không gian hai chiều.
Ví dụ: Độ phân giải của màn hình CGA (Color Graphic Adaptor) là
một lưới điểm theo chiều ngang màn hình: 320 điểm chiều dọc * 200 điểm
ảnh (320*200). Cùng loại màn hình CGA và ở cùng độ phân giải 320*200, ta
sẽ thấy màn hình CGA 12” mịn hơn màn hình CGA 17” . Lý do chính là ở
cùng một độ phân giải nhưng diện tích màn hình rộng hơn thì độ mịn hay tính
liên tục của các điểm ảnh sẽ thấp hơn
1.3.3. Mức xám của ảnh
Mức xám của điểm ảnh là cường độ sáng của nó được gán bằng giá trị
số tại điểm đó.
Các giá trị mức xám thông thường như: 16, 32, 64, 128, 256. Trong đó,
mức 256 là mức phổ dụng cho các máy tính ngày nay do máy tính dùng 1
byte (8 bit) để biểu diễn mức xám nên sẽ có 28=256 mức.
Ảnh đen trắng: là ảnh có hai màu đen trắng với mức xám ở các điểm
ảnh có thể khác nhau.
Ảnh nhị phân: là ảnh chỉ có 2 mức đen trắng phân biệt dùng 1 bit mô
tả 2 mức khác nhau. Như vậy, mỗi điểm ảnh của ảnh nhị phân chỉ có thể là 0
hoặc 1.


( x+ i, y-1)

(x -1, y)

(X, y)

(x+l,y)

(x-l,y+!)

(x?y + l )

(x+i,y+l)

Hình L3 Lân cùn các đi êm ảnh cua to tí đô (x,y)

Hình 1.3 Lân cận các điểm ảnh của tọa độ (x,ỵ)
Các điểm lân cận chéo Np(p) (Có thể coi lân cận chéo là 4 hướng:
Đông-Nam, Đông-Bắc, Tây-Nam, Tây-Bắc)
NP(p) = {(x + ly + l); (x + ly-l); (x-l,y+l); (x-l.y-l)ỉ
Tập kết hợp: Ns(p) - NẶp) + Np(p) là tập hợp 8 lân cận của điểm ảnh p.


22

Chú ý: Nếu (x,y) nằm ở biên ảnh thì một số điểm lân cận sẽ nằm ngoài
ảnh.
I.3.4.2. Khoảng cách giữa các điểm ảnh
Định nghĩa: Khoảng cách D(p,q) giữa hai điểm ảnh p tọa độ (x,y), q
tọa độ (s,t) là hàm khoảng cách (Distance) nếu:

23

Khoảng cách khối: Khoảng cách D4(p,q) được gọi là khoảng cách
khối đồ thị (City - Block Distance) và được xác định như sau:
D4(p,q) = I x-s\ + lj-íl
Giá trị khoảng cách giữa các điểm ảnh r: giá trị bán kính r giữa điểm
ảnh từ tâm điểm ảnh đến tâm điểm ảnh q khác. Ví dụ: màn hình CGA 12”
(12”*2,54cm=30,48cm=304,8mm) độ phân giải 320*200; tỷ lệ 4/3 (Chiều
dài/Chiều rộng). Theo định lý Pitago về tam giác vuông, đường chéo sẽ lấy tỷ
lệ 5 phần (5/4/3: đường chéo/chiều dài/chiều rộng); khi đó độ dài thật là
(505/244/183) chiều rộng màn hình 183mm ứng với màn hình CGA 200 điểm
ảnh theo chiều dọc. Như vậy, khoảng cách điểm ảnh lân cận của CGA 12” là
~ lmm.
Khoảng cách hay khoảng cách nhỏ nhất ứ của một mã khối là số kí tự khác
nhau nhỏ nhất giữa hai mã tự bất kì, và khoảng cách tương đối ỏ là tỉ lệ d Ịn .
Một cách cụ thể hơn, với hai mã tự C1: c2 £ ^ , đặt^Mci 1 cz)là khoảng cách
Hamming giữa

và c2 , nghĩa là số vị trí khác nhau giữa

và c2 . Định nghĩa

khoảng cách nhỏ nhất d của mã Cìà
d :=

min

A(C(jTZi),C(jTZ2 ))

Do mọi mã đều là đơn ánh, khoảng cách nhỏ nhất luôn lớn hơn hoặc

ảnh cơ bản có thể gồm: máy tính cá nhân kèm theo vỉ mạch chuyển đổi đồ
hoạ VGA hoặc SVGA, đĩa chứa các ảnh dùng để kiểm tra các thuật toán và
một màn hình có hỗ trợ VGA hoặc SVGA.