BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC
KHOA
Luận văn

Tìm hiểu phương
pháp phân đoạn ảnh
Tìm hiểu phương pháp phân đoạn ảnh
Trường ĐH Dân lập Hải Phòng—SV.Nguyễn Thị Anh Thư
Trang 1
MỤC LỤC

MỤC LỤC 1
LỜI CÁM ƠN 4
DANH MỤC HÌNH VẼ 5
MỞ ĐẦU 6

CHƢƠNG 3 : PHÂN ĐOẠN ẢNH DỰA VÀO ĐỒ THỊ 42
3.1 Giới thiệu 42
3.2 Phân đoạn dựa vào đồ thị 43
3.3 Tính chất của so sánh cặp miền 44
3.4 Thuật toán và các tính chất 45
3.4.1 Định nghĩa 1 45
3.4.2 Định nghĩa 2 46
3.4.3 Tính chất 1 46
3.4.4 Thuật toán 1 47
3.4.5 Bổ đề 1: 48
3.4.6 Định lý 1 48
3.4.7 Định lý 2 48
Tìm hiểu phương pháp phân đoạn ảnh
Trường ĐH Dân lập Hải Phòng—SV.Nguyễn Thị Anh Thư
Trang 3
3.4.8 Định lý 3 49
3.4.9 Độ phức tạp tính toán 50
CHƢƠNG 4: CÀI ĐẶT THỬ NGHIỆM 51
4.1Định dạng ảnh PPM(Portable Pix Map) 51
4.1Cài đặt thử nghiệm 52
4.3 Một số kết quả minh hoạ 59
KẾT LUẬN 61
5.1 Nội dung của đồ án 61
5.1.1 Các kết quả đạt đƣợc 61
5.1.2 Một số hạn chế cần khắc phục 61
5.2 Công việc tiếp theo 62
TÀI LIỆU THAM KHẢO 63

Tìm hiểu phương pháp phân đoạn ảnh
Trường ĐH Dân lập Hải Phòng—SV.Nguyễn Thị Anh Thư

Hình 5. Đường biên lý tưởng 20
Hình 6. Đường biên bậc thang 21
Hình 7. Đường biên thực 21
Hình 8. Minh hoạ một số phương pháp phát hiện biên 29
Hình 9. Liên thông và mã hướng tương ứng 32
Hình 10. Mã hoá theo góc 33
Hình 11. Phương pháp tách cây tứ phân 38
Hình 12. Ví dụ về nhận dạng các vùng ảnh 43 Tìm hiểu phương pháp phân đoạn ảnh
Trường ĐH Dân lập Hải Phòng—SV.Nguyễn Thị Anh Thư
Trang 6
MỞ ĐẦU
Xử lý ảnh (XLA) là một trong những chuyên ngành quan trọng và lâu đời
của Công nghệ thông tin. XLA đƣợc áp dụng trong nhiều lĩnh khác nhau nhƣ y học,
vật lý, hoá hoc, tìm kiếm tội phạm,… Mục đích chung của việc XLA thƣờng là: (1)
xử lý ảnh ban đầu để có đƣợc một bức ảnh mới theo một yêu cầu cụ thể; (2) phân
tích ảnh để thu đƣợc các thông tin đặc trƣng trên ảnh nhằm hỗ trợ cho việc phân loại
và nhận biết ảnh; (3) phân đoạn ảnh (image segmentation) để nhận diện đƣợc các
thành phần trong ảnh nhằm hiểu đƣợc kết cấu của bức ảnh ở mức độ cao hơn. Để
xử lý đƣợc một bức ảnh thì phải trải qua nhiều bƣớc, nhƣng bƣớc quan trọng và khó
khăn nhất đó là phân đoạn ảnh. Nếu bƣớc phân đoạn ảnh không tốt thì dẫn đến việc
nhận diện sai lầm về các đối tƣợng có trong ảnh.
Trong khoảng 30 năm trở lại đây đã có rất nhiều các thuật toán đƣợc đề xuất
để giải quyết bài toán phân đoạn ảnh. Các thuật toán hầu hết đều dựa vào hai thuộc
tính quan trọng của mỗi điểm ảnh so với các điểm lân cận của nó, đó là: sự khác
(dissimilarity) và giống nhau (similarity). Các phƣơng pháp dựa trên sự khác nhau
của các điểm ảnh đƣợc gọi là các phƣơng pháp biên (boundary-based methods) ,
còn các phƣơng pháp dựa trên sự giống nhau của các điểm ảnh đƣợc gọi là phƣơng

Chƣơng 4 đƣa ra các đoạn mã chƣơng trình (code) bằng C++ mã hoá một số
thuật toán đƣợc trình bày trong luận văn.
Khi viết báo cáo này em dã cố gắng hết sức để hoàn thành công việc đƣợc
giao, song điều kiện thời gian và trình độ còn hạn chế nên không tránh khỏi thiếu
sót.Em mong nhận đƣợc sự góp ý của thầy giáo hƣớng dẫn , thầy cô giáo và bạn
bè trong khoa Công nghệ thông tin để em có đƣợc những kinh nghiệm thực tế và bổ
ích để sau này có thể xây dựng đƣợc một chƣơng trình hoàn thiện hơn.

Tìm hiểu phương pháp phân đoạn ảnh
Trường ĐH Dân lập Hải Phòng—SV.Nguyễn Thị Anh Thư
Trang 8
CHƯƠNG 1 : TỔNG QUAN VỀ XỬ LÝ ẢNH
VÀ PHÂN ĐOẠN ẢNH
Xử lý ảnh ngày nay đã trở thành một ngành khoa học lớn và có mặt trong nhiều
lĩnh vực của cuộc sống. Điều này hoàn toàn có thể lý giải được từ một định nghĩa
đơn giản về ngành khoa học này: Xử lý ảnh là ngành khoa học nghiên cứu các quá
trình xử lý thông tin dạng hình ảnh
Error! Reference source not found.
, mà hình ảnh là một
trong những dạng thông tin phong phú nhất đối với chúng ta Trong quá trình xử lý
ảnh bước quan trọng nhất và cũng là có khăn nhất là bước phân đoạn ảnh. Phân
đoạn nhằm mục đích phân tách các đối tượng cấu thành nên ảnh thô để có thể sử
dụng cho các ứng dụng về sau.
1.1 TỔNG QUAN VỀ XỬ LÝ ẢNH
1.1.1 Giới thiệu về Xử lý ảnh
Trong xã hội loài ngƣời, ngôn ngữ là một phƣơng tiện trao đổi thông tin phổ
biến trong quá trình giao tiếp. Bên cạnh ngôn ngữ, hình ảnh cũng là một cách trao
đổi thông tin mang tính chính xác, biểu cảm khá cao và đặc biệt không bị cảm giác
chủ quan của đối tƣợng giao tiếp chi phối. Thông tin trên hình ảnh rất phong phú,
đa dạng và có thể xử lý bằng máy tính. Chính vì vậy, trong những năm gần đây sự

Quá trình XLA có thể đƣợc mô tả bằng sơ đồ sau: Hình 1. Quá trình xử lý ảnh
Thu nhận
ảnh
Tiền XLA
Phân đoạn
ảnh
Biểu diễn và
mô tả ảnh.

CƠ SỞ
TRI
THỨC
Nhận dạng
và giải thích
Tìm hiểu phương pháp phân đoạn ảnh
Trường ĐH Dân lập Hải Phòng—SV.Nguyễn Thị Anh Thư
Trang 10
 Thu nhận ảnh: Đây là công đoạn đầu tiên mang tính quyết định đối với quá trình
XLA. Ảnh đầu vào sẽ đƣợc thu nhận qua các thiết bị nhƣ camera, sensor, máy
scanner, vv …và sau đó các tín hiệu này sẽ đƣợc số hoá. Các thông số quan
trọng ở bƣớc này là độ phân giải, chất lƣợng màu, dung lƣợng bộ nhớ và tốc độ
thu nhận ảnh của các thiết bị.
 Tiền xử lý: Ở bƣớc này, ảnh sẽ đƣợc cải thiện về độ tƣơng phản, khử nhiễu, khử
bóng, khử độ lệch, v.v với mục đích làm cho chất lƣợng ảnh trở nên tốt hơn

dạng ảnh (image recognition) có thể đƣợc nhìn nhận một cách đơn giản là việc
gán nhãn cho các đối tƣợng trong ảnh. Giải thích là công đoạn gán nghĩa cho
một tập các đối tƣợng đã đƣợc nhận biết.
Chúng ta cũng có thể thấy rằng, không phải bất kỳ một ứng dụng XLA nào cũng
bắt buộc phải tuân theo tất cả các bƣớc xử lý đã nêu ở trên, ví dụ nhƣ các ứng dụng
chỉnh sửa ảnh nghệ thuật chỉ dừng lại ở bƣớc tiền xử lý. Một cách tổng quát thì
những chức năng xử lý bao gồm nhận cả nhận dạng và giải thích thƣờng chỉ có mặt
trong hệ thống phân tích ảnh tự động hoặc bán tự động, đƣợc dùng để rút trích ra
những thông tin quan trọng từ ảnh, ví dụ nhƣ các ứng dụng nhận dạng ký tự quang
học, nhận dạng chữ viết tay vv…
1.2. TỔNG QUAN VỀ PHÂN ĐOẠN ẢNH
Để phân tích các đối tƣợng trong ảnh, chúng ta cần phải phân biệt đƣợc các
đối tƣợng cần quan tâm với phần còn lại của ảnh, hay còn gọi là nền ảnh. Những đối
tƣợng này có thể tìm ra đƣợc nhờ các kỹ thuật phân đoạn ảnh, theo nghĩa tách phần
tiền cảnh ra khỏi hậu cảnh trong ảnh. Mỗi một đối tƣợng trong ảnh đƣợc gọi là một
vùng hay miền, đƣờng bao quanh đối tƣợng ta gọi là đƣờng biên. Mỗi một vùng ảnh
phải có các đặc tính đồng nhất (ví dụ: màu sắc, kết cấu, mức xám vv…). Các đặc
tính này tạo nên một véc tơ đặc trƣng riêng của vùng (feature vectors) giúp chúng
ta phân biệt đƣợc các vùng khác nhau.
Nhƣ vậy, hình dáng của một đối tƣợng có thể đƣợc miêu tả hoặc bởi các tham số
của đƣờng biên hoặc các tham số của vùng mà nó chiếm giữ. Sự miêu tả hình dáng
dựa trên thông tin đƣờng biên yêu cầu việc phát hiện biên. Sự mô tả hình dáng dựa
Tìm hiểu phương pháp phân đoạn ảnh
Trường ĐH Dân lập Hải Phòng—SV.Nguyễn Thị Anh Thư
Trang 12
vào vùng đòi hỏi việc phân đoạn ảnh thành một số vùng đồng nhất. Có thể thấy kỹ
thuật phát hiện biên và phân vùng ảnh là hai bài toán đối ngẫu của nhau. Thực vậy,
dò biên để thực hiện phân lớp đối tƣợng và một khi đã phân lớp xong cũng có nghĩa
là đã phân vùng đƣợc ảnh. Ngƣợc lại, khi đã phân vùng, ảnh đƣợc phân lập thành
các đối tƣợng, ta có thể phát hiện biên.

tạo thành biên hay còn gọi là đƣờng bao ảnh.
1.3.4 Láng giềng
Trong XLA có một khái niệm rất quan trọng, đó là khái niệm láng giềng. Có
hai loại láng giềng: 4-láng giềng và 8-láng giềng
4-láng giềng của một điểm (x,y) là một tập hợp bao gồm láng giềng dọc và
láng giềng ngang của nó:
N
4
((x,y)) = {(x+1,y), (x-1,y), (x,y+1), (x,y-1)}
(1.1)
8-láng giềng của (x,y) là một tập cha của 4-láng giềng và bao gồm láng
giềng ngang, dọc và chéo:
N
8
((x,y)) = N
4
((x,y)){(x+1,y+1),(x-1,y-1), (x+1,y-1),(x-1,y+1)} (1.2)
1.3.5 Vùng liên thông
Một vùng R đƣợc gọi là liên thông nếu bất kỳ hai điểm (x
A
,y
A
) và (x
B
,y
B
)
thuộc vào R có thể đƣợc nối bởi một đƣờng (x
A
,y

i-1
) và điểm tiếp theo (x
i+1
,y
i+1
) trên đƣờng đó. Một điểm (x
k
,y
k
)
đƣợc gọi là kề với điểm (x
l
,y
l
) nếu (x
l
,y
l
) thuộc vào láng giềng trực tiếp của (x
k
,y
k
).
Tìm hiểu phương pháp phân đoạn ảnh
Trường ĐH Dân lập Hải Phòng—SV.Nguyễn Thị Anh Thư
Trang 14
CHƯƠNG 2 : MỘT SỐ KỸ THUẬT PHÂN
ĐOẠN ẢNH
Phân đoạn (segmentation) là một quá trình chia ảnh ra các vùng con khác
nhau mà trong mỗi vùng chứa các thực thể có ý nghĩa cho việc phân lớp - mỗi thực

Else f[x,y] = Background = 0.
Ngƣợc lại, đối với các đối tƣợng tối trên nền sáng chúng ta có thuật toán sau:
If f[x,y] < T f[x,y] = object = 1
Else f[x,y] = Background = 0.
Vấn đề chính là chúng ta nên chọn ngƣỡng T nhƣ thế nào để việc phân vùng
đạt đƣợc kết quả cao nhất?.
Có rất nhiều thuật toán chọn ngƣỡng: ngƣỡng cố định, dựa trên lƣợc đồ, sử
dụng Entropy, sử dụng tập mờ, chọn ngƣỡng thông qua sự không ổn định của lớp và
tính thuần nhất của vùng vv… Ở đây chúng tôi đề cập đến hai thuật toán chọn
ngƣỡng đó là chọn ngƣỡng cố định và chọn ngƣỡng dựa trên lƣợc đồ.
2.1.2 Chọn ngưỡng cố định
Đây là phƣơng pháp chọn ngƣỡng độc lập với dữ liệu ảnh. Nếu chúng ta biết
trƣớc là chƣơng trình ứng dụng sẽ làm việc với các ảnh có độ tƣơng phản rất cao,
trong đó các đối tƣợng quan tâm rất tối còn nền gần nhƣ là đồng nhất và rất sáng
thì việc chọn ngƣỡng T= 128 (xét trên thang độ sáng từ 0 đến 255) là một giá trị
chọn khá chính xác. Chính xác ở đây hiểu theo nghĩa là số các điểm ảnh bị phân lớp
sai là cực tiểu.
2.1.3 Chọn ngưỡng dựa trên lược đồ (Histogram)
Trong hầu hết các trƣờng hợp, ngƣỡng đƣợc chọn từ lƣợc đồ độ sáng của
vùng hay ảnh cần phân đoạn. Có rất nhiều kỹ thuật chọn ngƣỡng tự động xuất phát
Tìm hiểu phương pháp phân đoạn ảnh
Trường ĐH Dân lập Hải Phòng—SV.Nguyễn Thị Anh Thư
Trang 16
từ lƣợc đồ xám {h[b] | b = 0, 1, , 2
B
-1} đã đƣợc đƣa ra. Những kỹ thuật phổ biến
sẽ đƣợc trình bày dƣới đây. Những kỹ thuật này có thể tận dụng những lợi thế do sự
làm trơn dữ liệu lƣợc đồ ban đầu mang lại nhằm loại bỏ những dao động nhỏ về độ
sáng. Tuy nhiên các thuật toán làm trơn cần phải cẩn thận, không đƣợc làm dịch
chuyển các vị trí đỉnh của lƣợc đồ. Nhận xét này dẫn đến thuật toán làm trơn dƣới

và (m
b,0
) của những điểm ảnh nền.
- B3: Tính các ngƣỡng trung gian theo công thức:
2
1,1, 


kbkf
k
mm

với k = 1, 2, …
(2.2)
- B4: Nếu
1

kk

: Kết thúc, dừng thuật toán.
Ngƣợc lại : Lặp lại bƣớc 2.
2.1.3.2 Thuật toán đối xứng nền
Kỹ thuật này dựa trên sự giả định là tồn tại hai đỉnh phân biệt trong lƣợc đồ
nằm đối xứng nhau qua đỉnh có giá trị lớn nhất trong phần lƣợc đồ thuộc về các
điểm ảnh nền. Kỹ thuật này có thể tận dụng ƣu điểm của việc làm trơn đƣợc mô tả
Tìm hiểu phương pháp phân đoạn ảnh
Trường ĐH Dân lập Hải Phòng—SV.Nguyễn Thị Anh Thư
Trang 17
trong phƣơng trình (2.1). Đỉnh cực đại maxp tìm đƣợc nhờ tiến hành tìm giá trị cực
đại trong lƣợc đồ. Sau đó thuật toán sẽ đƣợc áp dụng ở phía không phải là điểm ảnh

Số điểm ảnh
a
T
Đối tƣợng
Nền
Tìm hiểu phương pháp phân đoạn ảnh
Trường ĐH Dân lập Hải Phòng—SV.Nguyễn Thị Anh Thư
Trang 18
2.1.3.3 Thuật toán tam giác
Khi một ảnh có các điểm ảnh thuộc đối tƣợng tạo nên một đỉnh yếu trong lƣợc
đồ ảnh thì thuật toán tam giác hoạt động rất hiệu quả. Thuật toán này do Zack đề
xuất và đƣợc mô tả nhƣ sau:
- B1: Xây dựng đƣờng thẳng ∆ là đƣờng nối hai điểm (H
max
, b
max
) và (H
min
,
b
min)
, trong đó H
max
là điểm có Histogram lớn nhất ứng với mức xám b
max

và H
min
là điểm có Histogram ứng với độ sáng nhỏ nhất b
min

min
b

d
H
min
H
max

H
b
Tìm hiểu phương pháp phân đoạn ảnh
Trường ĐH Dân lập Hải Phòng—SV.Nguyễn Thị Anh Thư
Trang 19
nền tối hay đối tƣợng tối trên nền sáng mà phép biến đổi top hat sẽ có một trong hai
dạng sau:
a/ Các đối tƣợng sáng:
))(min(max)(),( AABAABATopHat
B
B
 
(2.4)
b/ Các đối tƣợng tối:
))(max(min)(),( AABAABATopHat
B
B
 
(2.5)
Việc tính toán giá trị cực tiểu địa phƣơng của histogram thì khó nếu
histogram nhiễu. Do đó, trong trƣờng hợp này nên làm trơn histogram, ví dụ sử

sắc, kích thƣớc vv … thì chừng ấy thông tin là chƣa đầy đủ.
Trong toán học, ngƣời ta đƣa ra khái niệm đƣờng biên lý tƣởng nhƣ sau:
Đường biên lý tưởng là sự thay đổi giá trị cấp xám tại một vị trí xác định. Vị trí
của đường biên chính là vị trí thay đổi cấp xám. Thể hiện của định nghĩa là hình
vẽ 2

Hình 5. Đường biên lý tưởng

Một loại đƣờng biên nữa - đƣợc gọi là đƣờng biên bậc thang: Đường biên
bậc thang xuất hiện khi sự thay đổi cấp xám trải rộng qua nhiều điểm ảnh. Vị trí
của đường biên được xem như vị trí chính giữa của đường nối giữa cấp xám
thấp và cấp xám cao. Mức xám
x
Tìm hiểu phương pháp phân đoạn ảnh
Trường ĐH Dân lập Hải Phòng—SV.Nguyễn Thị Anh Thư
Trang 21

Hình 6. Đường biên bậc thang
Trong thực tế đƣờng biên của chúng ta thƣờng có dạng nhƣ sau:
tính theo công thức:
dy
yxfdyyxf
f
y
yxf
dx
yxfydxxf
f
x
yxf
y
x
),(),(),(
),(),(),(








(2.6)
trong đó, dx là khoảng cách giữa các điểm theo hƣớng x (khoảng cách tính
bằng số điểm), dy là khoảng cách giữa các điểm theo hƣớng y. Thực tế, ngƣời ta
hay dùng với dx = dy = 1.
Với một ảnh liên tục f(x,y), các đạo hàm riêng của nó cho phép xác định vị
trí cực đại cục bộ theo hƣớng của biên. Thực vậy, một ảnh liên tục đƣợc biểu diễn
bởi một hàm f(x,y) dọc theo r với góc  (toạ độ cực):


























(2.8)
 là hƣớng của biên khi:
Tìm hiểu phương pháp phân đoạn ảnh
Trường ĐH Dân lập Hải Phòng—SV.Nguyễn Thị Anh Thư
Trang 23


0cossin
0

Thực ra, đạo hàm của ảnh là không tồn tại vì f(x,y) không liên tục. Ở đây, ta
chỉ sử dụng mô phỏng theo ý nghĩa của đạo hàm, việc tính toán là xấp xỉ đạo hàm
bằng kỹ thuật nhân chập. Trong phƣơng pháp gradient, ngƣời ta chia nhỏ thành hai
kỹ thuật (tƣơng ứng với hai toán tử khác nhau):
+ Kỹ thuật gradient dùng toán tử gradient, lấy đạo hàm theo một hƣớng;
+ Kỹ thuật la bàn dùng toán tử la bàn, lấy đạo hàm theo tám hƣớng: Bắc,
Nam, Đông, Tây, và Đông Bắc, Tây Bắc, Đông Nam, Tây Nam.
2.2.2.2 Kỹ thuật Gradient
Kỹ thuật gradient sử dụng một cặp mặt nạ H
1
, H
2
trực giao (theo hai hƣớng
vuông góc). Nếu định nghĩa g
x
, g
y
là gradient tƣơng ứng theo hai hƣớng x, y thì biên
độ của gradient tại điểm (i,j)- ký hiệu là g(i,j) đƣợc tính theo công thức:
),(),(),(
22
0
jigjigAjig
yx

(2.9)





01
10
1
H
,









10
01
2
H

Với mỗi điểm ảnh I(x,y) của I, gọi g
x
, g
y
tƣơng ứng là các đạo hàm theo các
hƣớng x và y, ta có:


Ngƣời ta gọi H
1
, H
2
là mặt nạ Robert.
Trong trƣờng hợp tổng quát, giá trị gradient biên độ g và gradient hƣớng 
r

đƣợc tính bởi công thức (2.9), (2.10). Ngoài ra, để giảm thời gian tính toán ta cũng
có thể dùng các chuẩn sau để tính g(i,j):
),(),(
1
jigjigA
yx

(2.13)
Hoặc
 
),(,),(
2
jigjigMaxA
yx

(2.14)
Một điểm nữa là: khi di chuyển mặt nạ trên ảnh, trƣờng hợp gặp các điểm
biên, thì coi các điểm ứng với mặt nạ ở bên ngoài ảnh có giá trị 0.
+/ Toán tử Solbel:
Toán tử Solbel sử dụng hai mặt nạ H
1
, H





111
000
111
2
H
(2.15)

Trích đoạn Làm mảnh biên Giới thiệu

---