BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC LẠC HỒNG
* * * Nguyễn Văn Thành PHÂN TÍCH MỘT SỐ PHƢƠNG PHÁP
PHÂN ĐOẠN ẢNH CÓ GIÁM SÁT Luận văn thạc sĩ Công nghệ thông tin

Đồng Nai – 2013 LỜI CẢM ƠN

Trong quá trình làm luận văn vừa qua, được sự giúp đỡ và chỉ bảo nhiệt tình
ca PGS. TS Ngô Quốc Tạo – Viện Công nghệ Thông tin – Viện khoa học Việt
Nam, luận văn ca em đã được hoàn thành. Măc dù đã cố gắng cùng vi sự tậ n tâm
ca thy hưng dẫ n song do th ời gian và khả năng vẫ n còn nhiề u hạn chế nên luậ n
văn không tránh khỏ i nhng thiế u sót.
Em xin bày tỏ lò ng biế t ơn sâu sắ c t i thy PGS. TS Ngô Quốc Tạo đã tận
tình hưng dẫn, chỉ bảo và dành rất nhiều thời gian quí báu ca thy cho em trong
thời gian qua, đã giúp em hoàn thành bài luận văn đúng thời hạn.
Em xin gửi lời cảm ơn đến Ban Giám hiệu, các Thy cô giáo ca Trường Đại
học Lạc Hồng, các Thy cô bộ môn, đã giảng dạy cung cấp, trang bị cho chúng em
nhng kiến thức chuyên ngành, chuyên môn chuyên sâu trong suốt hai năm qua.
Xin cảm ơn gia đình và bạn bè đã động viên cổ vũ em trong suốt quá trình học
tập cũng như thời gian làm luận văn, đã giúp em hoàn thành khóa học, luận văn
theo qui định.
LỜI CAM ĐOAN

Tôi xin cam đoan luận văn là kết quả nghiên cứu ca tôi, không sao chép ca
ai. Nội dung luận văn có tham khảo và sử dụng các tài liệu liên quan, các thông tin
trong tài liệu được đăng tải trên các tạp chí và các trang website theo danh mục tài
liệu ca luận văn.

Tác giả luận văn

1.1.4 Quan hệ cơ bản gia các điểm ảnh. 13
1.2 Tổng quan về phân đoạn ảnh. 16 1.2.1 Gii thiệu. 16
1.2.2 Các phương pháp tiếp cận. 17
1.2.2.1 Phân vùng ảnh theo ngưỡng biên độ. 19
1.2.2.2 Phân vùng theo miền đồng nhất. 20
1.2.2.3 Phân vùng ảnh dựa trên phân tích kết cấu. 24
1.2.2.4 Phân vùng ảnh dựa trên sự phân lp điểm ảnh. 28
1.2.2.5 Phân vùng dựa vào lý thuyết đồ thị. 30
1.2.2.6 Phân vùng ảnh dựa trên biểu diễn và xử lý đa phân giải. 35
CHƢƠNG 2: MỘT SỐ KỸ THUẬT PHÂN ĐOẠN ẢNH CÓ GIÁM SÁT 37
2.1. Gii thiệu về phân đoạn ảnh có giám sát. 37
2.2. Phân đoạn ảnh sử dụng grabcut. 38
2.2.1. Phân đoạn theo năng lượng cực tiểu hóa. 39
2.2.2. Giải thuật phân đoạn GrabCut. 41
2.2.2.1. Mô hình d liệu màu. 41
2.2.2.2. Phân đoạn theo lặp lại cực tiểu năng lượng. 42
2.2.2.3.Tương tác người sử dụng và trimap không đy đ. 44
2.3. Phân đoạn ảnh sử dụng Random Walks. 45
2.3.1. Trọng số cạnh. 46
2.3.2.Vấn đề Dirichlet Tổ hợp 46
2.3.3.Mạch tương tự. 48
2.3.4.Mối quan hệ để khuếch tán. 49
2.4.Phân đoạn ảnh sử dụng Random Walks with Restart. 50
2.4.1.Phương pháp phân đoạn ảnh dựa trên RWR 54
2.4.1.1.Xây dựng đồ thị trọng số cho hình ảnh 55
2.4.1.2.Tính xác suất 56


Graph Cuts
Cắt đồ thị
Green
Màu lục
Grey
Màu xám
Image Processing
Xử lý ảnh
Image Recognition
Nhận dạng ảnh
Intelligent Scissors
Kéo thông minh
Local
Cục bộ
Opening
Phép mở
Pixel
Phn tử ảnh
Random Walk
Bưc đi ngẫu nhiên
Random Walk With Return
Bưc đi ngẫu nhiên vi quay lại
Red
Màu đỏ
Region-Based Methods
Phương pháp dựa vào miền
Scanner
Quét ảnh
Screen Resolution
Độ phân giải màn hình

Bảng 2-1: B_LIN 53
Bảng 2-2 : Phân đoạn ảnh RWR B_LIN 56

iv

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 1.1 Quá trình xử lý ảnh 3
Hình 1.2 Lân cận các điểm ảnh của tọa độ (x,y) 14
Hình 1.3 Một ví dụ về phân vùng ảnh 17
Hình 1.4 Minh họa cách chọn ngưỡng. 20
Hình 1.5 Khái niệm 4 liên thông và 8 liên thông 23
Hình 1.6 Phân tích kết cấu bằng dải tương quan 25
Hình 1.7 Biểu diễn ảnh dưới dạng một đồ thị 31
Hình 1.8 Minh họa cây bao trùm tối thiểu của một đồ thị. 32
Hình 2.1 Một số ví dụ của Grabcut 41
Hình 2.2 Phân đoạn ảnh Lặp đi lặp lại ở GrabCut. 44
Hình 2. 3 Sự Quy tụ cực tiểu hóa lặp đi lặp lại 44
Hình 2.4 Người dùng hiệu chỉnh. 45
Hình 2.5 Kết quả phân đoạn 58
Hình 2.6 So sánh độ phức tạp thuật toán 60
Hình 3.1 Sự thay đổi xác suất trạng thái ổn định r 62
Hình 3.2 Phân đoạn đối với sự biết đổi của các xác suất khởi động lại c trong ảnh
tự nhiên 62
Hình 3.3 So sánh thuật toán GC, RW, RWR cho ảnh có đường biên yếu 65
Hình 3. 4 So sánh phân đoạn cho ảnh có kết cấu yếu giữa các thuật toán GC, RW,
RWR 66
Hình 3.5 So sánh thuật toán GC, RW, RWR trên ảnh tự nhiên 67 1

2

Random Walker Restart (RWR) – chỉ ra phương pháp được đánh giá là hiệu quả
hơn các phương pháp phân đoạn ảnh trưc đây, khắc phục được hai khó khăn quan
trọng trong ảnh tự nhiên là bài toán đường biên yếu và kết cấu yếu.
Phương pháp RWR dựa vào việc coi một bức ảnh như một đồ thị có trọng số.
Sau khi tính xác suất trạng thái ổn định ca mỗi điểm ảnh bằng cách sử dụng kỹ
thuật phân đoạn ảnh chúng ta có thể ưc lượng khả năng phân tách và cuối cùng
gán nhãn vào mỗi điểm ảnh.
Chương 3 phân tích kết quả thực nghiệm phân đoạn ảnh RWR vi các ảnh tự
nhiên có đường biên yếu và kết cấu yếu.

3

CHƢƠNG 1: TỔNG QUAN VỀ XỬ LÝ ẢNH, PHÂN ĐOẠN ẢNH
1.1 Tổng quan về xử lý ảnh
1.1.1 Một số khái niệm cơ bản về xử lý ảnh.
1.1.1.1 Xử lý ảnh là gì ?
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. 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 máy.
Quá trình xử lý ảnh được xem như là quá trình thao tác ảnh đu vào nhằm
cho ra kết quả mong muốn. Kết quả đu ra ca một quá trình xử lý ảnh có thể là một
ảnh “tốt hơn” hoặc một kết luận.
Hình 1.1 Quá trình xử lý ảnh

màu nhất định.
Điểm ảnh được xem như là dấu hiệu hay cường độ sáng tại 1 toạ độ trong
không gian ca đối tượng và ảnh được xem như là 1 tập hợp các điểm ảnh. Kích
thưc và khoảng cách gia các điểm ảnh đó được chọn thích hợp sao cho mắt người
cảm nhận sự liên tục về không gian và mức xám (hoặc màu) ca ảnh số gn như
thật. Mỗi phn tử trong ma trận được gọi là một phn tử ảnh.
Ta cn phân biệt Pixel (phn tử ảnh) vi khái niệm pixel hay đề cập đến
trong hệ thống đồ hoạ máy tính.
1.1.1.3 Mức xám của ảnh.
Mức xám (gray-level) là kết quả ca sự mã hoá tương ứng một cường độ sáng
ca mỗi điểm ảnh vi một giá trị số ca quá trình lượng hoá. Là số các giá trị có
thể có ca các điểm ảnh ca ảnh. Một điểm ảnh (pixel) có hai đặc trưng cơ bản là vị
trí (x, y) ca điểm ảnh và độ xám ca nó. Dưi đây chúng ta xem xét một số khái
niệm và thuật ng thường dùng trong xử lý ảnh.
a) Định nghĩa:
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 đó.
b) Các thang giá trị mức xám thông thƣờng:
16, 32, 64, 128, 256 (Mức 256 là mức phổ dụng.
5

Lý do: từ kỹ thuật máy tính dùng 1 byte (8 bit) để biểu diễn mức xám: Mức
xám dùng 1 byte biểu diễn: 2
8
=256 mức, tức là từ 0 đến 255).
c) Ảnh đen trắng:
Là ảnh có hai màu đen, trắng (không chứa màu khác) vi mức xám ở các điểm
ảnh có thể khác nhau.
d) Ảnh nhị phân:
Ảnh chỉ có 2 mức đen trắng phân biệt tức dùng 1 bit mô tả 2

1.1.2 Các giai đoạn cơ bản trong xử lý ảnh.
1.1.2.1 Biểu diễn ảnh.
Trong biểu diễn ảnh người ta thường dùng các phn tử đặc trưng ca ảnh là
pixel. Nhìn chung có thể xem một hàm hai biến f(x,y) chứa các thông tin như là
biểu diễn ca một ảnh. Các mô hình biểu diễn ảnh cho ta một mô tả logic hay định
lượng các tính chất ca hàm này. Một số mô hình thường được dùng trong biểu diễn
ảnh: mô hình toán, mô hình thống kê. Trong mô hình toán, ảnh hai chiều được biểu
diễn nhờ các hàm hai biến trực giao gọi là các hàm cơ sở. Vi mô hình thống kê,
một ảnh được coi như là một phn tử ca một tập hợp đặc trưng bởi các đại lượng
như: kỳ vọng, hiệp biến, phương sai, moment.
Đây là một bưc quan trọng, tạo tiền đề cho xử lý ảnh. Mục đích chính nhằm
làm nổi bật 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 biên, khuyếch đại ảnh nhằm phục vụ cho việc hiển thị hoặc các quá trình
phân tích tiếp theo. Tùy theo các ứng dụng khác nhau mà chúng ta có các kỹ thuật
nâng cao chất lượng ảnh khác nhau.
Nâng cao chất lượng ảnh có quan hệ gn gũi vi khôi phục ảnh. Khi một ảnh
bị nhiễu thì khôi phục ảnh gốc thường đưa đến nâng cao chất lượng ảnh. Có một số
khác biệt gia khôi phục ảnh và nâng cao chất lượng ảnh. Trong khôi phục ảnh, một
ảnh gốc bị nhiễu thì mục tiêu là làm sao cho ảnh sau khi xử lý càng gn giống ảnh
gốc càng tốt. Còn trong nâng cao chất lượng ảnh thì mục tiêu là làm cho ảnh sau khi
xử lý có được chất lượng tốt hơn khi chưa xử lý. Như vậy một ảnh không bị nhiễu
thì không thể được xử lý bằng các kỹ thuật khôi phục ảnh nhưng ảnh đó có thể được
xử lý bằng các kỹ thuật nâng cao chất lượng ảnh. Nhưng một ảnh bị nhiễu thì nó có
thể được xử lý vừa bằng các kỹ thuật khôi phục ảnh vừa bằng các kỹ thuật nâng cao
chất lượng ảnh.

7

1.1.2.2 Tăng cƣờng, nâng cao chất lƣợng ảnh.
Đây là một bưc quan trọng, tạo tiền đề cho xử lý ảnh.

thiểu (Wiener).
1.1.2.4 Biến đổi ảnh.
Biến đổi ảnh là việc sử dụng một lp các ma trận đơn vị và các kỹ thuật
thường dùng để biến đổi ảnh như: Biến đổi Fourier, Sin, Cosin, tích Kronecker, biến
đổi Karhumen Loeve…
1.1.2.5 Phân tích ảnh.
Là khâu quan trọng trong quá trình xử lý ảnh để tiến ti hiểu ảnh. Trong
phân tích ảnh việc trích chọn đặc điểm là một bưc quan trọng. Các đặc điểm ca
đối tượng được trích chọn tuỳ theo mục đích nhận dạng trong quá trình xử lý ảnh.
Có thể nêu ra một số đặc điểm ca ảnh sau đây:
Đặc điểm không gian: Phân bố mức xám, phân bố xác suất, biên độ, điểm
uốn…
Đặc điểm biến đổi: Các đặc điểm loại này được trích chọn bằng việc thực
hiện lọc vùng (zonal filtering). Các bộ vùng được gọi là “mặt nạ đặc điểm”
(feature mask) thường là các khe hẹp vi hình dạng khác nhau (ch nhật, tam giác,
cung tròn )
Đặc điểm biên và đường biên: Đặc trưng cho đường biên ca đối tượng và
do vậy rất hu ích trong việc trích trọn các thuộc tính bất biến được dùng khi nhận
dạng đối tượng. Các đặc điểm này có thể được trích chọn nhờ toán tử gradient, toán
tử la bàn, toán tử Laplace, toán tử “chéo không” (zero crossing) v.v
Việc trích chọn hiệu quả các đặc điểm giúp cho việc nhận dạng các đối
tượng ảnh chính xác, vi tốc độ tính toán cao và dung lượng nh lưu tr giảm
xuống.
Phân tích ảnh là quá trình suy luận, tính toán dựa vào các đặc tính thể hiện
trên hình ảnh để từ đó rút ra được các thông tin định lượng về hình ảnh.
9

Phân tích ảnh có thể tách biệt các vật thể trên ảnh, đo lường, phân loại, mô
tả, so sánh chúng.
Mặt khác, từ việc phân tích ảnh cũng có thể suy ra các số liệu thống kê về

Nhận dạng đối tượng ảnh quá trình từ không gian biểu diễn lp đối tượng
vào không gian tên gọi ca đối tượng (mỗi đối tượng được gán một cái tên). Hay
nói một cách khác nhận dạng đối tượng chính là quá trình tiến hành phân lp đối
tượng cn nhận dạng vào các lp. Có hai lp phương pháp tiếp cận chính trong quá
trình phân lp các đối tượng, đó là các phương pháp phân lp dựa vào đường ranh
gii phân biệt gia các lp (Nơ ron network, phương pháp véc tơ tựa, boosting,
trường ngẫu nhiên có điều kiện, nhận dạng dựa vào đa nhân…) và các phương pháp
phân lp dựa vào phân bố thống kế ca các lp (mô hình markov ẩn, phương pháp
phân loại thống kê, Bayesian, trường marko ngẫu nhiên). Trên cơ sở các bài toán
thì sẽ có các mô hình nhận dạng phù hợp và các thuật toán đi kèm các mô hình đó.
Ngoài ra còn một số cách tiếp cận khác trong lý thuyết nhận dạng đó là đối sánh
mẫu dựa trên các đặc trưng được trích chọn, nhận dạng cấu trúc (xâu chuỗi, đồ
thị, ) nhận dạng dựa trên biểu diễn ng pháp văn phạm.
Hệ thống nhận dạng tự động bao gồm 4 khâu tương ứng vi bốn giai đoạn
ch yếu sau:
1. Thu nhận d liệu , tiền xử lý, trích chọn đặc tính
2. Biểu diễn d liệu
3. Huấn luyện d liệu
4. Nhận dạng, ra quyết định
Trên 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 bài 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 phục vụ cho việc tự động hóa 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.
Các bài toán và ứng dung nhận dạng rất phong phú như: Nhận dạng Khuôn mặt,
nhận dạng các biểu cảm ca con người, nhận dạng các cử chỉ và hoạt động ca con
11

người, nhận dạng người đi bộ, xây dựng các hệ thống giám sát thông minh, rô bốt,
các hệ thống dự báo dựa vào hình ảnh….
1.1.2.7 Nén ảnh.

về kích thưc và trọng lượng, do đó ảnh nhận được bị giảm chất lượng như bị mờ,
méo hình học và nhiễu nền. Các ảnh đó được xử lý thành công nhờ máy tính số.
Hình ảnh ca mặt trăng và sao hỏa mà chúng ta thấy trong tất cả các tạp chí đều
được xử lý bằng nhng máy tính số. Ngày nay, hu hết các thông tin ảnh đều được
chuyển sang dạng ảnh số. Vì vậy, trong gn như tất cả các lĩnh vực ca các ngành
kỹ thuật đều có ít nhiều liên quan đến ảnh số và sử dụng kỹ thuật xử lý ảnh số. Ứng
dụng ca xử lý ảnh có khả năng tác động mạnh mẽ nhất đến cuộc sống ca chúng ta
là lĩnh vực y tế. Soi chụp ảnh bừng máy tính dựa rteen cơ sở định lý cắt lp (project
slice) được dùng thường xuyên trong xét nghiệm lâm sang, ví dụ phát hiện và nhận
dạng u não. Nhng ứng dụng y khoa khác ca xử lý ảnh gồm cải thiện ảnh X quang
và nhận dạng đường biên mạch máu từ nhng ảnh chụp bằng tia X (angiograms).
Có nhng dụng khác gn gi hơn vi cuộc sông gia đình là cải tiến ảnh tivi.
Hình ảnh mà chúng ta thấy trên màn hình tivi có các khuyết tật do độ phân giải hạn
chế, bi rung rinh, có ảnh ma, nhiều nền và trượt hình do đan dòng ở nhng mức độ
khác nhau. Xử lý ảnh sô có tác động quyết định đến việc cải thiện chất lượng hình
ảnh ca nhng hệ truyền hình hiện tại và làm phát triển nhng hệ truyền hình mi
có độ phân giải cao (HDTV). Một vấn đề na cúa chính truyền thông video như hội
nghị video, điện thoại video là cn có dải tn rộng. Việc mã hóa thẳng chương trình
video chất lượng quảng bá yêu cu đến 100 triệu bit/giây. Nếu hy sinh một phn
chất lượng và dùng các sơ đô mã hóa ảnh số thì có thể đưa ra thị trường nhng hệ
truyền hình chất lượng đ rõ vi nhịp bit chỉ dưi 100 nghìn bit/giây.
Người máy càng ngày đóng vai trò quan trọng trong công nghiệp và gia đinh.
Chúng sẽ thực hiện nhng công việc rất nhàm chán hoặc nguy hiểm và nhng công
việc mà tốc độ và độ chính xác vượt quá khả năng ca con người. Khi người máy
trở nên tinh vi hơn, thị giác máy tinh sẽ đóng vai trò ngày càng quan trọng. Người ta
sẽ đòi hỏi người máy không nhng phát hiện và nhận dạng các bộ phận công
13

nghiệp, mà còn “hiểu” được nhng gì chúng “thấy” và đưa ra nhng hành động phù
hợp. Xử lý ảnh số có tác động rất ln đến thị giác máy tính.

Đông x Tây
Nam
y
Bắc
(x-1,y-1)
(x,y-1)
(x+1,y-1)
(x-1,y)
(x,y)
(x+1,y)
(x-1,y+1)
(x,y+1)
(x+1,y+1)

Hình 1.2 Lân cận các điểm ảnh của tọa độ (x,y)
* Các lân cận chéo: Các điểm lân cận chéo N
P
(p) (Có thể coi lân cận chéo la 4
hưng: Đông-Nam, Đông-Bắc, Tây-Nam, Tây-Bắc)
N
p
(p) = { (x+1, y+1); (x+1, y-1); (x-1, y+1); (x-1, y-1)}
* Tập kết hợp: N
8
(p) = N
4
(p) + N
P
(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 (mép) ảnh; một số điểm sẽ nằm ngoài ảnh.