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 sự khích
lệ, động viên, giúp đỡ từ phía thầy cô, cha mẹ và bạn bè xung quanh.
Em xin bày tỏ lòng biết on chân thành nhất tới thầy giáo, PGS. TS Ngô Quốc
Tạo, người đã trực tiếp hướng dẫn em hoàn thành luận văn thạc sỹ này.
Cảm ơn đề tài: " Hệ thống đeo tay hỗ trợ đọc sách tiếng Việt dành cho người
khiếm thị” Mã số VAST01.07/15-16 hỗ trợ trong thực hiện luận văn.
Em xin gửi lời cảm ơn chân thành tới các thầy cô trong trường Đại học Sư
phạm Hà Nội 2.
Em đã cố gắng học tập và hoàn thành luận văn thạc sỹ nhưng có thể luận văn
thạc sỹ vẫn còn thiếu sót. Em rất mong nhận được sự góp ý, chỉ bảo của các thầy cô
và các bạn để luận văn thạc sỹ hoàn thiện hơn.
Hà nội, ngày 01 tháng 07 năm 2015 Tác giả
luận văn

Nguyễn Đức Toàn


2

LỜI CAM ĐOAN

Tôi xin cam đoan rằng số liệu và kết quả nghiên cứu trong luận văn này là
trung thực và không trùng lặp với các đề tài khác. Tôi cũng xin cam đoan rằng mọi sự
giúp đỡ cho việc thực hiện luận văn này đã đuợc cảm ơn và các thông tin trích dẫn
trong luận văn đã đuợc chỉ rõ nguồn gốc.
Hà nội, ngày 01 tháng 07 năm 2015 Tác
giả luận văn

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.
ứng dụng phương pháp phân đoạn cho ảnh tài liệu.

4. Đối tượng và phạm vi nghiên cứu
Đối tượng, phạm vi nghiên cứu về tổng quan về phân đoạn ảnh, các phưong
pháp phân đoạn ảnh và chọn ra phương pháp phân đoạn cho ảnh cụ thể và các ứng
dụng thực tế phân đoạn cho ảnh tài liệu.

5. Phương pháp nghiên cứu
Thu thập tài liệu, phân tích, suy luận, tổng họp, đánh giá. Từ đó đề xuất nghiên
cứu và tìm hiểu: “Nghiên cứu phương pháp phân đoạn ảnh và ứng dụng cho ảnh tài
liệu”.


NỘI DUNG

Con người thu nhận thông tin qua các giác quan, trong đó 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
trở 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 ngành khoa

học mới mẻ so với nhiều ngành khoa học khác nhưng tốc độ phát triển rất nhanh, kích

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á trì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.
Ảnh có thể nhận qua camera màu hoặc đen trắ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 dùng là loại quét dòng ; ảnh tạo ra có dạng hai
chiều. Chất lượng một ảnh thu nhận được phụ thuộc vào thiết bị thu, vào môi trường (ánh
sáng, phong cảnh).

1.2.2.

Tiền xử lý (Image Processing)
Sau bộ thu nhận, ảnh có thể nhiễu độ tương phản thấp nên cần đưa vào bộ tiền xử lý

để nâng cao chất lượng. Chức năng chính của bộ tiền xử lý là lọc nhiễu, nâng độ tương

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.
Ảnh 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)

Nhận dạng ảnh là quá trình xác định ảnh bằng cách so sánh ảnh với
mẫu chuẩn đã được lưu từ trước.
Nội suy là phán đoán theo ý nghĩa trên cơ sở nhận dạng ảnh.

Mô tả ảnh
Từ Hình 1.1, ảnh 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ớ cực 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 đặc tả (biểu diễn) lại (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:

-

•

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ếu (m, n) thuộc R U( m, n) = 0
nếu (m, n) không thuộc R

tới khâu trích chọn đặc trưng. Hình 1.2 cũng chia các nhánh song song như: nâng cao


chất lượng ảnh có hai nhánh phân biệt: nâng cao chất lượng ảnh (tăng độ sáng, độ
tương phản, lọc nhiễu) hoặc khôi phục ảnh (hồi phục lại ảnh thật khi ảnh nhận được
bị méo) v.v...

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

1.3.

Phân đoan ảnh
Phân đoạn ảnh là một thao tác ở mức thấp và là bước then chốt trong quá trình

xử lý ảnh. Giai đoạn này nhằm phân tích ảnh thành những vùng rời rạc có cùng tính
chất nào đó dựa vào việc xác định biên và các vùng liên thông cho từng vùng. Tiêu
chuẩn để xác định các vùng liên thông có thể là cùng mức xám, cùng màu hay cùng
độ nhám... Các vùng ảnh này thông thường sẽ tương ứng với toàn bộ hay từng phần
của đối tượng thật bên trong ảnh.
Mỗi vùng ảnh là một tập họp các điểm có cùng hoặc gần cùng một tính chất
nào đó như mức xám, mức màu, độ nhám... Đường bao quanh một vùng ảnh là biên
ảnh. Các điểm ảnh trong một vùng ảnh có độ biến thiên giá trị mức xám tương đối


đồng đều hay tinh kết cấu tương đồng.
Dựa vào đặc tính vật lý của ảnh người ta có nhiều kỹ thuật phân vùng như
phân vùng dựa theo miền liên thông gọi là phân vùng dựa theo miền đồng nhất hay
miền kề; phân vùng dựa và biên gọi là phân vùng biên. Ngoài ra còn có các kỹ thuật
phân vùng khác dựa vào biên độ, dựa vào kết cấu...



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.
Ảnh màu: trong khuôn khồ lý thuyết ba màu (Red, Blue, Green) để tạo nên
thế giới màu người ta thường dừng 3 byte để mô tả mức màu. Khi đó mỗi điểm ảnh
có thể nhận số giá trị màu là 28*3=224 S316,7 triệu màu.

1.3.4.

Quan hệ giữa các điểm ảnh
Một ảnh số giả sử được biểu diễn bằng hàm f(x,y). Tập con các điểm ảnh là S;

cặp điểm ảnh có quan hệ với nhau là p,q. Để thể hiện quan hệ giữa các điểm ảnh
chúng ta có một sổ khái niệm sau:



Tây
(x-Hl, y-1)

Hình 1.3 Lân cân các điêm ảnh của
Hỉnh 1.3 Lân cận cảc điểm ảnh của tọa độ (x,y)

(x+l,y)
(X+Ly+I)
tọa độ
(x,y)

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+l,y+l); (x+l,y-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.


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:

1. D(p,q) > 0 (Với D(p,q)=0 nếu và chỉ nếu p-q)
2. D(p,q) = D(q,p)

đế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 d của một mã khối là số kí tự khác nhau nhỏ nhất

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.
Ảnh mức xám được áp dụng trong 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. Với lý do đó, hệ thống ban đầu nên chỉ bao gồm các thiết bị thu nhận và hiển
thị ảnh đen trắng. Với ảnh màu, nên sử dụng một hệ thống mới như Hình 1.4, trừ trường
họp cần một camera TV màu và một màn hình đa tần số (ví dụ như NEC Multisync, Sony
Multiscan, hoặc Mitsubishi Diamond Scan) để hiển thị ảnh màu. Nếu khả năng hạn chế, có
thể dùng PC kèm theo vỉ mạch VGA và màn hình VGA, để dựng ảnh được.

1.3.5.
1.3.5.1.

Những vấn đề khác trong xử lỷ ảnh
Biến đổi ảnh (Image Transform)


Trong xử lý ảnh, do số điểm ảnh lớn, các tính toán nhiều (độ phức tạp tính toán
cao) đòi hỏi dung lượng bộ nhớ lớn, thời gian tính toán lâu. Các phương pháp khoa học
kinh điển áp dụng cho xử lý ảnh hầu hết khó khả thi. Vì vậy, chúng ta sử dụng các phép
toán tương đương hoặc biến đổi ảnh sang miền xử lý khác để dễ tính toán.
Sau khi xử lý xong, chúng ta dùng biến đổi ngược để đưa ảnh về miền xác định ban
đầu. Các phép biến đổi thường gặp trong xử lý ảnh gồm:

-

Biến đổi Fourier, Cosin, Sin,

-


■Ảnh PCX: Là một trong những định dạng ảnh cổ điển nhất. Nó sử dụng phương
pháp mã loạt dài RLE (Run Length Encoded) để nén dữ liệu ảnh. Quá trình nén
và giải nén được thực hiện trên từng dòng ảnh.

■Ảnh TIFF: Là ảnh mà dữ liệu chứa trong tệp thường được tổ chức thành các


nhóm dòng (cột) quét của dữ liệu ảnh.

■Ảnh GIF: Dạng ảnh GIF cho chất lượng cao, độ phân giải đồ họa cao và cho phép
hiển thị trên hầu hết các phần cứng.
Tuy các định dạng này khác nhau, song chúng đều tuân theo một cấu trúc chung
nhất là gồm 3 phần:

■Mào đầu tệp (Header): Là phần chứa các thông tin về kiểu ảnh, kích thước, độ
phân giải, so bit dùng cho 1 pixel, cách mã hóa, vị trí bảng màu...

■Dữ liệu nén (Data Compression): số liệu ảnh được mã hóa bởi kiểu mã hóa chỉ ra
trong phần Header.

■Bảng màu (Palette Color): Bảng màu cho biết số màu dùng trong ảnh và sử dụng
trong việc hiển thị màu của ảnh. Ảnh đen trắng không nhất thiết phải có bảng
màu.
CHƯƠNG 2: PHƯƠNG PHÁP PHÂN ĐOẠN ẢNH
•
Phân đoạn ảnh là bước then chốt trong xử lý ảnh. Giai đoạn này nhằm phân tích
ảnh thành những thành phần có cùng tính chất nào đó dựa theo biên hay các vùng liên
thông. Tiêu chuẩn đểxác định các vùng liên thông có thể là cùng mức xám, cùng màu hay
cùng độ nhám... Trước hết cần làm rõ khái niệm "vùng ảnh" (Segment) và đặc điểm vật lý
của vùng. Vùng ảnh là một chi tiết, một thực thể trông toàn cảnh. Nó là một tập họp các


pháp heuristic và hữu ■ Có vấn đề trong việc
hạn.
xác định số lượng các cụm
ban đầu.
■ Khó khăn trong việc điều
chỉnh các cụm sao cho phù
hợp với


các vùng trong ảnh.
Adaptive Clustering

■ Sở hữu tính liên tục trong
■ Cực đại hoá một xác suất
không gian ảnh và tính hậu điều kiện có thể bị sai
thích nghi cục bộ đối với do các cực trị địa phương.
■ Hội tụ chậm.
các vùng ảnh.

■ Sử dụng các ràng buộc về
không gian ảnh.

Histogram thresholding

■ Không cần biết trước bất kỳ
■ Bỏ qua các thông tin về
thông tin nào từ ảnh.

không gian ảnh.

■ Quadtree có thể gây ra các
nhất.

kết quả không như mong
muốn.


Region growing

■ Các vùng ảnh đồng nhất và
■ Tốn kém chi phí sử dụng bộ
liên thông.

nhớ và tính toán.

■ Có một số thuật giải có tốc
■ Gặp khó khăn trong việc thu
độ thực thi khá nhanh.

thập tập các điểm mầm và

cho các ứng dụng nhận xác định các điều kiện
đồng nhất đầy đủ.
dạng và xử lý ảnh y khoa.

■ Chịu ảnh hưởng bởi các đặc
Edge-based

tính tự nhiên của kỹ thuật


đến kếtthời
quảgian
phân vùng.
■ Một số thuật toán có

thực hiện.

tốc độ thực hiện
■ Các đặc trưng cục bộ
nhanh.
Physics-based techniques
đôi khi được sử dụng nhiều

■ Khẳng định tính chắc chắn
■ Bịhơngiới
hạntrưng
vào toàn
mộtcục.
số
các đặc
Neural networks

đối với các vùng bóng lượng nhất định các loại vật
■ Mức độ song song hoá
■ Màu sắc có thể làm
sáng/tối, và vùng bóng chất hình thành nên đối
cao và có tốc độ thực
tăng độ phức tạp của
chuyển tiếp (diffuse hoặc tượng.
thi nhanh.

Việc chọn số lượng màu phân biệt trong không gian màu giảm là một sự trao đổi
giữa sự thể hiện và tốc độ đối với một ứng dụng riêng biệt. Với chỉ mục màu hiệu quả,
số lượng màu ít thì thích họp và nó cũng làm giảm sự tính toán. Dưới đây là bảng gồm
25 màu (theo giác quan) được chọn từ bảng màu RGB chuẩn.

Hình 2.2. Phân đoạn ảnh