MỤC LỤC


DANH MỤC HÌNH


LỜI MỞ ĐẦU
Logic mờ được công bố lần đầu tiên tại Mỹ vào năm 1965 bởi giáo sư L.Zadeh.
Kể từ đó, Logic mờ đã có bước phát triển mạnh mẽ trong nhiều lĩnh vực và các ứng
dụng thực tế khác nhau. Đặc biệt, việc ứng dụng Logic mờ trong lĩnh vực xử lý ảnh đã
đem lại những hiệu quả rõ rệt. Bởi vì, với việc áp dụng Logic mờ vào trong xử lý ảnh,
ta đã phần nào xử lý được những yếu tố không chắc chắn thường xuyên xảy ra trong
xử lý ảnh, bởi vì đầu vào ảnh thường có nhiễu và các đối tượng trong ảnh thường
không rõ ràng và nằm chồng lên nhau. Chính vì vậy, việc ứng dụng Logic mờ vào xử
lý ảnh đã trở thành hướng nghiên cứu và quan tâm của rất nhiều nhà khoa học
cũng như người sử dụng.
Với đề tài “Ứng dụng thuật toán phân cụm FCM vào phân đoạn ảnh” ,
đề tài sẽ trình bày một số vấn đề về ứng dụng Logic mờ và phân đoạn ảnh.
Trong đó, đề tài tập trung vào việc sử dụng các thuật toán phân cụm FCM
(Fuzzy C-means) để thực hiện phân đoạn ảnh.
Có nhiều phương pháp khác nhau để phân đoạn ảnh song mỗi phương pháp
đều có những ưu điểm và nhược điểm riêng tùy thuộc vào từng bài tốn cụ thể.
Báo cáo được trình bày trong 3 chương:
Chương 1: Tổng quan về Logic mờ và phân đoạn ảnh
Chương 2: Kỹ thuật phân cụm dữ liệu mờ loại một
Chương 3: Chương trình và ứng dụng
Kết luận: Tóm tắt các vấn đề được tìm hiểu trong báo cáo và các vấn đề liên quan
trong báo cáo, đưa ra phương hướng nghiên cứu tiếp theo.

3

CHƯƠNG 1. TỔNG QUAN VỀ LOGIC MỜ VÀ PHÂN ĐOẠN ẢNH
1.1. Tổng quan về logic mờ
1.1.1. Tập mờ loại một
Logic mờ (FL) theo nghĩa rộng mà ngày nay được dùng rộng rãi, có cùng nghĩa
với lý thuyết tập mờ.
* Định nghĩa tập mờ loại một
Cho X là không gian của các đối tượng x, x là một đối tượng (phần tử) thuộc X.
Một tập cổ điển A, A ∈ X , là tập gồm các phần tử A ∈
thể thuộc tập A hoặc không thuộc tập A.

X , như vậy với mỗi x ∈ X có

x ∈ X có quan hệ với
tập A như sau: Tập cổ điển A là một tập của các cặp phần tử có bậc (x,0) với x ∉  A
Hàm đặc tính (characteristic funtions) cho mỗi đối tượng

hoặc ( x, 1) với x ∈  A . Với cách định nghĩa trên, có thể miêu tả tập cổ điển A thơng
qua hàm đặc tính:

A = {( x, µ A ( x ) ) | x ∈  X}
Trong đó:

µ A ( x)

là hàm đặc tính được xác định:

 0, x ∉ A
µ A ( x) = 
1, x ∈ A


với

∀ x∈ X

* Tập mờ và hàm thuộc
Nếu X là một tập hợp các đối tượng x, x biểu diễn chung cho đối tượng, khi đó
một tập mờ

A ⊆ X được định nghĩa như một tập của các cặp phần tử có bậc:

{

A = ( x, µ A ( x ) ) | x ∈ X
Ở đây:
tử

µ A ( x)

}.

được gọi là hàm thuộc (MF) cho tập mờ A. MF ánh xạ mỗi phần

x ∈ X tới độ thuộc giữa 0 và 1 của MF.

Với định nghĩa trên, không giống như tập cổ điển, tập mờ có hàm đặc tính (theo
nghĩa của tập cổ điển) cho phép có giá trị nằm giữa 0 và 1. Như vậy định nghĩa của tập
mờ là một mở rộng đơn giản của định nghĩa tập cổ điển trong đó hàm thuộc có độ

4



thuộc giữa 0 và 1. Nếu giá trị của hàm thuộc
A chính là tập cổ điển và

µ A ( x)

µ A ( x)

được đưa về chỉ có 0 và 1, khi đó

là một hàm đặc tính của A.

Thơng thường X được xem như là tập nền. X có thể là các đối tượng rời rạc (có
thứ tự hoặc khơng thứ tự) hoặc không gian liên tục.
* Biểu thức và tham số của một số hàm thuộc.
- Hàm thuộc một chiều
Hàm thuộc một chiều là hàm chỉ có một đầu vào. Do vậy, các hàm đưa ra dưới
đây sẽ được hiểu ngầm định là ln ln có một đầu vào.
+ Định nghĩa 1.1: Hàm thuộc Triangular
Một hàm thuộc triangular được đưa ra bởi 3 tham số {a, b, c}
(với a < b < c) như sau:

x≤a
 0,
x−a

, a≤ x≤b
b − a
triangle ( x, a , b, c ) = 

c − x , b ≤ x ≤ c
c − b
 0,
c≤x

Bằng cách dùng min và max, người ta đã đưa biểu diễn biểu thức trên như sau:


 x− a c− x 
triangle ( x, a, b, c ) = max  min 
,
,0 ÷÷
b
−
a
c
−
b



Ở đây: Các tham số {a, b, c} xác định tọa độ x của ba góc của hàm thuộc
Triangular.
Hình 1.2(a) dưới đây minh họa hàm thuộc Triangular được định nghĩa bởi
triangular(x; 20, 60, 80).

5


Hình 1.1: Các ví dụ của bốn loại hàm thuộc

Trong đó (a) Triangle(x; 20, 60, 80); (b) Trapezoid(x; 10, 20, 60, 95); (c)
Gaussian(x; 50, 20); (d) bell(x; 20, 4, 50)
+ Định nghĩa 1.2: Hàm thuộc Trapezoidal (Hình thang)
Một hàm thuộc trapezoidal được đưa ra bởi 4 tham số {a, b, c, d} (với a
< b < c < d ) như sau:
0, x ≤ a
x − a

, a≤x≤b
b − a

trapezoid ( x; a, b, c, d ) = 1, b ≤ x ≤ c
d − x

, c≤x≤d
d − c
0, d ≤ x
Bằng cách dùng min và max, người ta đã đưa ra biểu diễn biểu thức trên như sau:


x−a d −x 
trapezoid ( x; a, b, c, d ) = max  min
,
,0 
b
−
a
d
−
c


 

Ở đây: Các tham số {a, b, c, d} xác định tọa độ x của bốn góc của hàm thuộc
Trapezoidal.
Hình 1.1(b) minh họa hàm thuộc Trapezoidal được định nghĩa bởi trapezoidal(x;
10, 20, 60, 95).
+ Định nghĩa 1.3: Hàm thuộc Gaussian
Hàm thuộc Gaussian được đưa ra bởi 2 tham số

6

{ c, ∂ } :


2

gaussian ( x, c, ∂ ) = e
Ở đây: c miêu tả vị trí trọng tâm và

∂

1  x− c 
− 
÷
2 ∂ 

xác định độ rộng của hàm thuộc Gaussian.

Hình 1.1(c) minh họa hàm thuộc Gaussian được định nghĩa bởi gaussian (x; 50, 20).

+ Định nghĩa 1.4: Hàm thuộc bell – hình chng
Hàm thuộc bell – hình chng được đưa ra bởi 3 tham số {a, b, c}:

bell ( x; a, b, c ) =

1
x−c
1+
a

2b

Ở đây: b luôn luôn dương và tham số c định vị trí trọng tâm của đường cong.
Hình 1.1(d) minh họa hàm thuộc Bell được định nghĩa bởi bell(x; 20, 4, 50).
+ Định nghĩa 1.5: Hàm thuộc sigmoidal
Hàm thuộc sigmoidal được định nghĩa bởi:

sig ( x; a, c) =

1
1 + exp[ − a ( x − c)]

Hàm này phụ thuộc vào dấu của tham số a, có tính mở trái và phải. Do vậy, nó
gần như miêu tả các khái niệm “
” và “
”. Hàm này được khai thác rộng rãi. Tuy
+∞

−∞


nhiên để khai thác được cần biết cách kết hợp các hàm sigmoidal lại với nhau. Ví dụ
dưới đây đưa ra hai cách kết hợp các hàm sigmoidal để tạo ra các hàm thuộc có tính
đóng và tính khơng đối xứng.
+ Định nghĩa 1.6: Hàm thuộc left - right
Hàm thuộc left – right được đưa ra bởi 3 tham số

{ α , β ,c} :

 c− x
 FL  α ÷, x ≤ c

 
LR ( x; c,α , β ) = 
F  x − c , x ≥ c
 R  β ÷

7


Ở đây:

FL ( x ) và FR ( x ) là các hàm số giảm và đơn điệu trên đoạn [ 0,∞ )

với

FL ( x) = lim FR ( x) = 0
FL ( 0 ) = FR ( 0 ) = 1 và lim
x→∞
x→∞
.

* Một số hàm thuộc hai chiều
Hàm thuộc hai chiều là hàm có hai đầu vào. Cách cơ bản để mở rộng hàm thuộc
một chiều thành hàm hai chiều là thông qua mở rộng trụ (cylindrical extension), được
định nghĩa như sau:
+ Định nghĩa 1.7: Mở rộng trụ của hàm thuộc một chiều
Nếu A là tập mờ trong X, khi đó mở rộng trụ của A trong
được định ngha:

C ( A) =

X ìY

XìY

l tp m C(A)

à A ( x ) ( x, y )

Hình 1.2 dưới đây minh họa mở rộng trụ của tập mờ A.

Hình 1.2: (a) Tập mờ cơ sở A; (b) Mở rộng trụ C(A) của A.
+ Định nghĩa 1.8: Các phép chiếu của tập mờ
Cho R là tập mờ hai chiều trên
định nghĩa tương ứng:

X × Y . Khi đó các phép chiếu trên X và Y được

R X = ∫ [ max µ R ( x, y )] x
y


X

8


Hình 1.3: (a) Tập mờ hai chiều R; (b) RX (chiếu của R trên X); (c) RY (chiếu
của R trên Y)
Nói chung, hàm thuộc hai chiều được chia thành hai nhóm: kết hợp và khơng kết
hợp. Nếu hàm thuộc hai chiều có thể được biểu diễn thơng qua hai hàm thuộc một
chiều thì khi đó nó thuộc nhóm kết hợp. Ngược lại thì là nhóm khơng kết hợp.
Ví dụ: Hàm thuộc hai chiều thuộc nhóm kết hợp và khơng kết hợp
Giả sử tập mờ A = “(x, y) is near (3, 4)” được định nghĩa bởi:

  x − 3 2

2
µ A ( x, y ) = exp− 
 − ( y − 4) 
  2 

Đây là hàm thuộc hai chiều thuộc nhóm kết hợp. Do vậy nó có thể được phân
tích thành hai hàm thuộc một chiều như sau:

  x − 3 2 
  y − 4 3 
µ A ( x, y ) = exp− 
  exp− 
 
  2  
  1  


= gaussian ( x;3,2) gaussian ( y;4,1)
Với cách tách như trên thì bây giờ ta có thể biểu diễn tập mờ A như là sự kết nối
giữa hai câu lệnh “x is near 3 AND y is near 4”. Ở đây câu lệnh đầu tiên được định
nghĩa:

µ near 3 ( x ) = gaussian(x;3,2)

( x ) = gaussian(x;4,1) .Và tích giữa hai

µ

Câu lệnh thứ hai được định nghĩa: near 4
hàm thuộc trên được định nghĩa như là toán tử AND giữa câu lệnh.

Một loại hàm thuộc hai chiều khác là khơng kết hợp, ví dụ như tập mờ sau đây:

µ A ( x, y ) =

1
1+ x − 3 y − 4

2.5

Thuộc loại không kết hợp.
1.1.2. Tập mờ loại hai
* Các định nghĩa cơ bản
- Các định nghĩa cơ bản của tập mờ loại hai
Trong phần này, chúng ta định nghĩa tập mờ loại hai và một số khái niệm quan
trọng. Khoảng mờ của hàm thuộc loại một được vẽ trong hình 1.4(a) bằng cách di

chuyển các điểm trên tam giác hoặc tới bên trái hoặc tới bên phải, và khơng cần thiết
phải có số lượng các điểm giống nhau, như hình 1.4(b). Sau đó, ở một giá trị rõ x ta
gọi là x’, nó khơng cịn là giá trị đơn cho hàm thuộc u’, thay thế vào đó hàm thuộc

9


nhận các giá trị ở bất kỳ đâu trên đường thẳng giao với vùng mờ. Các giá trị này không
nhất thiết phải có các trọng số giống nhau. Vì vậy chúng ta có thể chỉ định các biên
phân bố đến tất các điểm đó. Để làm như vậy với tất cả các điểm x ∈ X . Chúng ta tạo
ra một hàm thuộc 3 chiều (hay gọi là hàm thuộc loại hai) là đặc trưng cho tập mờ loại
hai (hình 1.5).

Hình 1.4: (a) Hàm thuộc loại một và (b) Hàm thuộc loại một được
mờ hóa

Hình 1.5: Minh họa hàm thuộc loại hai

10


+ Định nghĩa 1.9: Một tập mờ loại hai, ký hiệu là
loại hai

A%, được đặc trưng bởi hàm thuộc

µ A%( x, u ) , trong đó x ∈ X và u ∈ J x ⊆ [0,1] , …
A%= {(( x, u ), µ A%( x, u )) | x ∈ X , u ∈ J x ⊆ [0,1]}

Trong đó:

Hoặc

(1.1)

0 ≤ µ A%( x, u ) ≤ 1.

A%cũng có thể được miêu tả như sau:
A%=

∫ ∫

x∈ X u∈J x

Trong đó

∫∫

µ A%( x, u ) / ( x, u )

J x ⊆ [0,1]

(1.2

ký hiệu hợp của tất cả các giá trị có thể có của x và u. Trong cơng

thức trên nếu tập nền X là rời rạc thì

∫

sẽ được thay thế bằng ∑ .


Trong công thức (1.1), ràng buộc đầu tiên là

∀ u ∈ J x ⊆ [0,1]

phù hợp với ràng

0 ≤ µ ( x, u) ≤ 1

A%
buộc loại một đó là
, …, khi thông tin không chắc chắn không xuất
hiện trong hàm thuộc loại hai thì chúng ta sẽ có hàm thuộc loại một, khi đó biến u sẽ

bằng

µ A%( x, u )

và

0 ≤ µ A%( x, u ) ≤ 1

, chiều thứ ba sẽ không xuất hiện. Giới hạn thứ hai

0 ≤ µ A%( x, u ) ≤ 1 phù hợp với thực tế µ A%( x, u ) luôn nằm trong đoạn [0,1].
+ Định nghĩa 1.10: Với mỗi giá trị của x, tại x = x ’, mặt phẳng 2D mà có hai trục là u
và

µ A%( x ', u )


được gọi là nhát cắt đứng (vertical slice) của

µ A%( x, u ) . Một hàm thuộc

phụ (secondary membership function) là một nhát cắt đứng của

µ A%( x, u )

tại x = x’, hay

µ A%( x = x ', u )

với x ∈

µ A%( x, u ) . Nó chính là

X và u ∈ J x ⊆ [0,1] .

µ A%( x = x ', u ) ≡ µ A%( x ') =

11

∫

u∈ J x

f x ' (u ) / u

J x ' ⊆ [0,1]


(1.3)


Trong đó

µ A%( x ')

0 ≤ f x ' (u) ≤ 1 . Bởi vì ∀ x ' ∈ X , chúng ta bỏ dấu phẩy trong ký hiệu
µ A%( x)

ta sẽ có
là hàm phụ, đó chính là tập mờ loại một, tập mà chúng ta tham
chiếu tới như là tập phụ (secondary set)

A%theo các nhát cắt đứng như sau:

Chúng ta có thể viết lại

A%= {( x, µ A%( x)) | x ∈ X }

(1.4)

Hoặc

A%=

∫

x∈ X


µ A%( x) / x =



f
(
u
)
/
u
 ∫ x
 x
 u∈ J


∫

x∈ X

J x ⊆ [0,1]

x

(1.5)

+ Định nghĩa 1.11: Miền của hàm thuộc phụ được gọi là hàm thuộc chính (primary
membership) của x. Trong (1.5)

Jx


là hàm thuộc chính của x, trong đó

J x ⊆ [0,1] với

∀ x∈ X .
- Các phép toán cơ bản trên tập mờ loại hai
+ Hợp của hai tập mờ loại hai

A%∪ B%⇔ µ A%∪ B%( x) =

∫ ∫

f x (u ) • g x (w) / v

u∈ J xu w∈ J xw

≡ µ A%( x) C µ B%( x)
Trong đó v= u ∨ w và
tốn min hay tích t-norm.

C

∨

∀ x∈ X

ký hiệu là phép tốn max t-conorm. Ký hiệu • là phép

là ký hiệu của phép toán Join.


+ Giao của hai tập mờ loại hai

A%∩ B%⇔ µ A%∩ B%( x) =
Trong đó v = u ∧ w ,
của phép tốn Meet.

∧

∫ ∫

u∈ J xu

f x (u ) • g x (w) / v

w∈ J xw

≡ µ A%( x) ∏ µ B%( x)

là ký hiệu của toán tử min hay toán tử nhân.

+ Phần bù của tập mờ loại hai
Phần bù của tập mờ loại hai được miêu tả như sau:

12

∀ x∈ X

∏

là ký hiệu



µ A%( x) =
Trong đó

¬

∫

f x (u ) / (1 u ) ơ à A%( x)

u J x

x X

u

là phép tốn phủ định. Trong tính tốn, với mỗi x

hàm thuộc chính của tập mờ loại hai sẽ là 1- u, với độ thuộc phụ là

∈ X , phần bù của
f x (u ) .

1.1.3. Mơ hình hóa bài tốn
Phân đoạn ảnh giữ một vai trị rất quan trọng trong nhiều ứng dụng như các bài
toán nhận dạng hay các bài toán xử lý ảnh. Phân đoạn ảnh là một bước cơ bản để có
thể thực hiện việc phân tích các ảnh thu được. Một cách tổng quát, phân đoạn ảnh
được định nghĩa như việc chia hình ảnh thành các đối tượng độc lập với nhau dựa trên
các đặc tính của ảnh như mức xám hay kết cấu của ảnh. Có rất nhiều các thuật tốn

phân đoạn ảnh được đề xuất, chúng ta có thể chia ra làm 4 loại sau đây:
- Phương pháp cơ bản: Phân ngưỡng, phát triển vùng, tách biên…
- Phương pháp thống kê: Maximum Likelihood Classifier (MLC)…
- Phương pháp dựa trên mạng Neural.
- Phương pháp dựa trên logic mờ (Fuzzy Clustering).
Chúng ta sẽ tập trung vào phương pháp trên logic mờ dựa trên mơ hình phân cụm
mờ Fuzzy C-means (FCM)
Phân lớp Fuzzy C-Means (FCM) là một trong những phương pháp được ứng
dụng rộng rãi nhất trong Logic mờ. Được đưa ra bởi Bezdek bằng cách mở rộng thuật
toán Dunn năm 1973, FCM là một trong những thuật toán hiệu quả trong bài toán phân
lớp và đặc biệt là trong các bài toán phân đoạn ảnh. Như vậy, bài toán phân lớp sẽ dẫn
đến việc giải bài toán xác định giá trị min của tổng khoảng cách của các điểm ảnh đến
tâm của mỗi phân đoạn trên miền đặc trưng của ảnh.
Giả sử rằng X:= {x1, x2, ..., xn} định nghĩa tập các điểm ảnh của một ảnh cần

xk ∈ R d với k=1,2...n

phải phân thành c (0biểu diễn các đặc tính của điểm ảnh. Trong các ảnh thông thường, chúng ta thường hay
xét đến giá trị mức xám, giá trị màu RGB của các điểm ảnh.
Xét ma trận phân lớp mờ (Fuzzy Partition Matrix)

U = ( uik ) cxn

u

phần tử ik chỉ ra khả năng thuộc phân lớp i của một điểm ảnh
phân lớp chính là tối ưu hoá hàm mục tiêu:
n

c

J m ( U ,V ) = ∑ ∑ uikm xk − vi
k =1 i =1

13

2

trong đó mỗi

xk . Khi đó, bài tốn


Trong đó ||.|| chính là giá trị chuẩn Euclidean trên không gian tương ứng và ma
trận V biểu diễn tập hợp các điểm tâm của các phân lớp trong không gian này còn
tham số m được gọi là tham số mờ của các tập dữ liệu. Khi đó, mơ hình của bài toán
phân đoạn ảnh được biểu diễn:
n c

2
m
J
U
,
V
=
u
x
−

v
(
)
∑∑
m
ik
k
i


k =1 i =1

c
u ∈ [0,1], k = 1..n, i = 1..c, u = 1
∑
ik
 ik
i =1

14


1.2. Tổng quan về phân đoạn ảnh
1.2.1. Giới thiệu
Phân vùng ả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 tồn cảnh. Nó 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 đó: Mức xám, mức

màu, độ nhám… Vùng ảnh là một trong hai thuộc tính của ảnh. Nói đến vùng ảnh là
nói đến tính chất bề mặt. Đường bao quanh một vùng ảnh (Boundary) là biên ảnh. Các
điểm trong một vùng ảnh có độ biến thiên giá trị mức xám tương đối đồng đều hay
tính kết cấu tương đồng.
Vùng ảnh là tập hợp các điểm ảnh có thuộc tính tương tự. Ta có thể xem một
ảnh X chính là một tập các điểm ảnh pi, ký hiệu X= { p i }, i∈ [1, N.M], với N.M là
kích thước của hình ảnh. Như vậy, phân vùng ảnh là quá trình tìm các tập con R i ={ tập
các điểm ảnh có thuộc tính tương tự} của các vùng ảnh sao cho:
UKi=1 Ri = X và Ri ∩ Rj, i≠ j, i, j = 1…K, với K là số vùng của ảnh X.
Phân vùng ảnh là quá trình xử lý một ảnh số thành một tập các vùng, mỗi vùng
là một tập hợp các điểm ảnh. Chính xác hơn, phân vùng ảnh là quá trình gán nhãn cho
mỗi điểm ảnh trong ảnh sao cho các điểm ảnh có các thuộc tính tương tự nhau thì có
cùng một nhãn. Đường bao quanh một vùng ảnh được gọi là đường biên.
Cơ sở toán học ở đây là chỉ tiêu phân vùng dựa trên độ đo sự tương tự giữa các
thuộc tính. Thuộc tính quan trọng là thuộc tính biên độ của hàm độ sáng.

a) Ảnh gốc

b) Kết quả sau khi phân vùng

Hình 1.6: Ví dụ về phân vùng ảnh

15


1.2.2. Các phương pháp tiếp cận
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: 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ào 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 độ, phân vùng dựa theo kết cấu. Phương pháp phân vùng ảnh

được chia thành hai hướng:
- Phương pháp phân vùng trực tiếp: (phân vùng dựa trên độ tương tự về thuộc tính):
Có nhiều phương pháp phân vùng ảnh như phân vùng ảnh dựa vào ngưỡng biên
bộ, phân vùng dựa theo miền liên thơng hay cịn gọi là phân vùng dựa theo miền đồng
nhất hoặc là phân vùng miền liền kề, có thể liệt kê các phương pháp như sau:
+ Phân vùng ảnh theo ngưỡng biên độ
+ Phân lớp điểm ảnh
+ Phân vùng dựa trên cấu trúc đồ thị
+ Phân vùng dựa trên xử lý đa phân giải
+ Phân vùng dựa trên phân tích kết cấu
+ Phân vùng dựa vào phát hiện đối tượng trong ảnh
+ Phương pháp cấu trúc
- Phương pháp phân vùng gián tiếp: (Phân vùng dựa trên tách biên).
Phân vùng dựa trên tách biên. Hay nói một cách khác, phân vùng ảnh và đường
biên có tính chất đối ngẫu, nếu như ta phát hiện được đường biên thì dựa vào biên có
thể xác định vùng ảnh hoặc nếu như ta phân vùng ảnh thì đường bao quanh vùng ảnh
đó được gọi là đường biên. Ngồi ra cịn có các phương pháp phân vùng khác như
phân vùng ảnh sử dụng bộ lọc tối ưu; phân vùng ảnh thông qua biểu diễn bề mặt.
Việc phân vùng ảnh dựa vào đường biên thì có ưu điểm nhanh, đơn giản. Ngồi
ra phân vùng ảnh dựa vào ngưỡng biên bộ thì rất nhạy cảm với nhiễu. Đối với các loại
ảnh tự nhiên thì đường biểu diễn biên của các vùng rất phức tạp (đường răng cưa).
Chính vì thế phương pháp dựa vào ngưỡng không hiệu quả trong phân vùng những
loại ảnh này. Thông thường, kỹ thuật phân ngưỡng theo biên độ rất có lợi đối với ảnh
nhị phân như văn bản in, đồ họa, ảnh màu hay ảnh X-quang. Việc chọn ngưỡng rất
quan trọng và bao gồm nhiều bước. Như vậy, có thể dùng ngưỡng biên độ để phân
vùng khi biên độ đủ lớn.
* Phân vùng ảnh theo ngưỡng biên độ
Các đặc tính đơn giản, cần thiết nhất của ảnh là biên độ và các tính chất vật lý
như: Độ tương phản, độ truyền sáng, màu sắc hoặc đáp ứng phổ. Như vậy, có thể dùng
ngưỡng biên độ để phân vùng khi biên độ đủ lớn đặc trưng cho ảnh. Ví dụ, biên độ

trong bộ cảm biến ảnh hồng ngoại có thể phản ánh vùng có nhiệt độ thấp hay vùng có
nhiệt độ cao. Kỹ thuật phân ngưỡng theo biên độ rất có lợi đối vớ ảnh nhị phân như
văn bản in, đồ họa, ảnh màu hay ảnh X-quang. Việc chọn ngưỡng rất quan trọng. Nó
bao gồm các bước:

16


- Xem xét lược đồ xám của ảnh để xác định các đỉnh và các khe. Nếu ảnh dạng
rắn lượn (nhiều đỉnh và khe), các khe có thể dùng để chọn ngưỡng.
- Chọn ngưỡng t sao cho một phần xác định trước η của toàn bộ số mẫu là thấp
hơn t.
- Điều chỉnh ngưỡng dựa trên lược đồ xám của các điểm lân cận.
- Chọn ngưỡng theo lược đồ xám của nhữg điểm thỏa mãn tiêu chuẩn chọn. Ví
dụ, với ảnh có độ tương phản thấp, lược đồ của những điểm có biên độ Laplace g(m,n)
lớn hơn giá trị t định trước (sao cho từ 5% đến 10% số điểm ảnh với Gradient lớn nhất
sẽ coi như biên) sẽ cho phép xác định các đặc tính ảnh lưỡng cực tốt hơn ảnh gốc.
- Khi có mơ hình phân lớp xác suất, việc xác định ngưỡng dựa vào tiêu chuẩn xác
suất nhằm cực tiểu xác suất sai số hoặc dựa vào một số tính chất khác của luật Bayes.
- Để hiểu rõ hơn nguyên tắc phân vùng dựa vào ngưỡng biên độ, xét thí dụ sau:

Hình 1.7: Minh họa cách chọn ngưỡng
Giả sử ảnh có lược đồ xám như Hình 1.7, chọn các ngưỡng như hình trên với:
T0 =Lmin,…,T4=Lmax. Ta có 5 ngưỡng và phân ảnh thành 4 vùng, ký hiệu C k là
vùng thứ k của ảnh, với k=1,2,3,4. Thì ta sẽ có được cách phân vùng theo nguyên tắc
như sau:
P(m,n) ∈ Ck nếu Tk-1 ≤ P(m,n) < Tk, k=1,2,3,4.
Khi phân vùng xong, nếu ảnh rõ nét thì việc phân vùng coi như kết thúc. Nếu
không, cần điều chỉnh ngưỡng.
* Phân vùng theo miền đồng nhất

Kỹ thuật phân vùng ảnh thành các miền đồng nhất dựa vào các tính chất quan
trọng nào đó của miền ảnh. Việc lựa chọn các tính chất của miền sẽ xác định tiêu
chuẩn phân vùng. Tính đồng nhất của một miền ảnh là điểm chủ yếu xác định tính hiệu
quả của việc phân vùng. Các tiêu chuẩn hay được dùng là sự thuần nhất về mức xám,
màu sắc đối với ảnh màu, kết cấu sợi và chuyển động.
Các phương pháp phân vùng ảnh theo miền đồng nhất thường áp dụng là:
- Phương pháp tách cây tứ phân
- Phương pháp cục bộ

17


- Phương pháp tổng hợp
a) Phương pháp tách cây tứ phân
Về nguyên tắc, phương pháp này kiểm tra tính đúng đắn của tiêu chuẩn đề ra
một cách tổng thể trên miền lớn của ảnh. Nếu tiêu chuẩn được thỏa mãn, việc phân
đoạn coi như kết thúc. Trong trường hợp ngược lại, chia miền đang xét thành 4 miền
nhỏ hơn. Với mỗi miền nhỏ, áp dụng một cách đệ quy phương pháp trên cho đến khi
tất cả các miền đều thỏa mãn điều kiện.
Phương pháp này có thể mơ tả như sau:
Procedure PhanDoan(Mien)
Begin
If miền đang xét không thõa mãn then
Begin
Chia miền đang xét thành 4 miền: Z1, Z2, Z3, Z4
For i=1 to 4 do PhanDoan (Zi)
End
Else exit
End.
Tiêu chuẩn xét miền đồng nhất ở đây có thể dựa vào mức xám. Ngồi ra, có thể

dựa vào độ lệch chuẩn hay độ chênh giữa giá trị mức xám lớn nhất và giá trị mức xám
nhỏ nhất.
Giả sử Max và Min là giá trị mức xám lớn nhất và nhỏ nhất trong miền đang
xét. Nếu:|Max – Min| < T (ngưỡng) ta coi miền đang xét là đồng nhất. Trường hợp
ngược lại, miền đang xét không là miền đồng nhất và sẽ được chia làm 4 phần.

18


Thuật toán kiểm tra tiêu chuẩn dựa vào độ chênh lệch max, min được viết:
Function Examin_Criteria(I, N1, M1, N2, M2, T)
/* Giả thiết ảnh có tối đa 255 mức xám. (N1, M1), (N2, M2) là tọa độ điểm đầu
và điểm cuối của miền; T là ngưỡng. */
Begin
1. Max=0 ; Min=255
2. For i = N1 to N2 do
If I[i,j] < Min Then Min=I[i,j] ;
If I[i,j] < Max Then Max=I[i,j] ;
3. If ABS(Max–Min)Else Examin_Criteria=1 ;
End.
Nếu hàm trả về giá trị 0, có nghĩa vùng đang xét là đồng nhất, nếu khơng thì
khơng đồng nhất. Trong giải thuật trên, khi miền là đồng nhất cần tính lại giá trị trung
bình và cập nhật lại ảnh đầu ra. Giá trị trung bình được tính bởi:
Tổng giá trị mức xám / tổng số điểm ảnh trong vùng
Thuật toán này tạo nên một cây mà mỗi nút cha có 4 nút con ở mọi mức trừ
mức ngồi cùng. Vì thế, cây này có tên là cây tứ phân. Cây cho ta hình ảnh rõ nét về
cấu trúc phân cấp của các vùng tương ứng với tiêu chuẩn.
Một vùng thõa mãn điều kiện sẽ tạo nên một nút lá; nếu khơng nó sẽ tạo nên
một nút trong và 4 nút con tương ứng. Tiếp tục như vậy cho đến khi phân chia xong để

đạt các vùng đồng nhất.
b) Phân vùng ảnh dựa vào phát triển vùng cục bộ.
Ý tưởng của phương pháp là xét ảnh từ các miền nhỏ nhất rồi nối chúng lại nếu
thỏa mãn tiêu chuẩn để được một miền đồng nhất lớn hơn. Tiếp tục với các miền thu
được cho đến khi khơng thể nối thêm được nữa. Số miền cịn lại cho ta kết quả phân
đoạn. Như vậy, miền nhỏ nhất của bước xuất phát là điểm ảnh. Phương pháp này hoàn
toàn ngược với phương pháp tách. Song điều quan trọng ở đây là nguyên lý nối 2
vùng. Việc nối 2 vùng được thực hiện theo nguyên tắc sau:
- Hai vùng phải đáp ứng tiêu chuẩn, thí dụ như cùng màu hay cùng mức xám.
- Hai vùng phải kế cận nhau.

19


Khái niệm kế cận: Trong xử lý ảnh, người ta dùng khái niệm liên thơng để xác
định tính chất kế cận. Có hai khái niệm về liên thơng là 4 liên thông và 8 liên thông.
Với 4 liên thông một điểm ảnh I(x,y) sẽ có 4 kế cận theo 2 hướng x và y ; trong khi đó
với 8 liên thơng, điểm I(x,y) sẽ có 4 liên thơng theo 2 hướng x, y và 4 liên thông khác
theo hướng chéo 450.

(a) 4 liên thơng

(b) 8 liên thơng

Hình 1.8: Khái niệm 4 liên thông và 8 liên thông
Dựa theo nguyên lý của phương pháp nối, ta có 2 thuật tốn:
- Thuật tốn tơ màu (Blob Coloring): Sử dụng khái niệm 4 liên thông, dùng một
cửa sổ di chuyển trên ảnh để so sánh với tiêu chuẩn nối.
- Thuật toán đệ quy cực bộ: Sử dụng phương pháp tìm kiếm trong một cây để
làm tăng kích thước vùng.

* Phân vùng ảnh dựa trên phân tích kết cấu
Kết cấu thường được nhận biết trên bề mặt của các đối tượng như gỗ, cát, vải…
Kết cấu là thuật ngữ phản ánh sự lặp lại của các phân tử mẩu kết cấu cơ bản. Sự lặp lại
có thể ngẫu nhiên hay có tính chu kỳ hoặc gần chu kỳ. Một mẫu kết cấu chứa rất nhiều
điểm ảnh. Trong phân tích ảnh, kết cấu được chia làm hai loại chính là: Loại thống kê
và lọa cấu trúc.
- Phương pháp thống kê
Tính kết cấu ngẫu nhiên rất phù hợp với các đặc trưng thống kê. Vậy, người ta
có thể dùng các đặc trưng ngẫu nhiên để đo nó như: Hàm tự tương quan
(AutoCorrelation Function- ACF), các biến đổi mật độ giờ, ma trận tương tranh,…
Theo cách tiếp cận bằng hàm tự tương quan, độ thô của kết cấu sợi tỉ lệ vớ độ rộng của
ACF, được biểu diễn bởi khoảng cách x0, y0 sao cho r(x0,0) = r(0,y0) = 1. Người ta
cũng dùng cách đo nhánh của ACF nhờ hàm khởi sinh moment:

M(k, l) = n – 1)k (m – 2)r(n,m)
Với 1 = .r(n,m) và 2 = .r(n,m)

20


Các đặc trưng của kết cấu sợi như độ thô, độ mịn hay hướng có thể ước lượng
nhờ các biến đổi ảnh bằng kỹ thuật lọc tuyến tính. Một mơ hình đơn giản trong trường
hợp ngẫu nhiên cho việc phân tích tính kết cấu được mơ tả trong hình dưới đây:

Hình 1.9: Phân tích kết cấu bằng dải tương quan
Trong mơ hình này, trường kết cấu sợi trước tiên được giải chập bởi bộ lọc lấy
từ đầu ra của ACF. Như vậy, Như vậy, nếu r(m,n) là ACF thì u(n, m) ⊗ a(n, m) = ε(n,
m) là trường ngẫu nhiên không tương quan.
Các đặc trưng của lược đồ bậc một của ε(n, m) chẳng hạn như trung bình m1,
độ phân tán cũng hay được sử dụng. Ngoài các đặc trưng trên, có thể đưa thêm một số

khái niệm và định nghĩa các đại lượng dựa trên đó như: Lược đồ mức xám (Histogram
Grey Level Difference), ma trận xuất hiện mức xám.
- Tiếp cận theo tính kết cấu
Khi đối tượng xuất hiện trên một nền có tính kết cấu cao, việc phân đoạn dựa
vào tính kết cấu trở nên quan trọng. Nguyên nhân là kết cấu sợi thường chứa mật độ
cao các gờ (edge) làm cho phân đoạn theo biên kém hiệu quả, trừ khi ta loại tính kết
cấu. Việc phân đoạn dựa vào miền đồng nhất cũng có thể áp dụng cho các đặc trưng
kết cấu và có thể dùng để phân đoạn các miền có tính kết cấu.
Nhìn chung, việc phân loại và phân vùng dựa vào kết cấu là một vấn đề phức tạp.

21


* Phân vùng ảnh dựa trên sự phân lớp điểm ảnh
- Mơ hình bài tốn:
Cho ảnh X ={pi}, i ∈ [1,N.M], với N là chiều rộng của ảnh và M là chiều cao
của ảnh, pi là điểm ảnh thứ I và A(pi) là thuộc tính của pi. Đối tượng phân lớp ở đây là
các Pi.
Phân vùng ảnh X chính là phân lớp tập X thành các lớp Ci sao cho từ Ci phát triển thành
các vùng Ri. Chỉ tiêu phân lớp ở đây chính là độ đồng đều về thuộc tính của các điểm ảnh.
Q trình phân lớp có thể sử dụng các phương pháp học máy và quyết định phân lớp.
- Phân lớp điểm ảnh trong không gian thuộc tính một chiều.
Thuật tốn ISODATA trong phân vùng ảnh:
Đầu vào: X={pi}, i∈[1,N.M], A(pi) là giá trị mức xám của pi.
Đầu ra: Số vùng ảnh
Phương pháp:
Bước 1. Khởi tạo: (t=0)
+ Đoán nhận số vùng K (số lớp) trên cơ sở lược đồ phân bố mức xám
(histogram). Trong đó lmin là giá trị mức xám thấp nhất và l max là mức xám giá trị cao
nhất của ảnh X.

+ Chọn các giá trị ngưỡng ban đầu của các lớp theo nguyên tắc sau:
T0=lmin, Tk=lmax và Ti(t)= i. + T0, với i=1…K-1
Bước 2. Lặp
+ Thực hiện phân lớp điểm theo các ngưỡng Ti(t-1)
PiCk nếu Ti(t-1) A(pi)Ti+1(t-l), k[l,k]
+ Tính giá trị trung bình của mỗi lớp tại điểm t

+ Tính lại các giá trị ngưỡng giữa các lớp theo quan hệ sau:

22


+ Kiểm tra điều kiện lặp
Nếu mi(t)mi(t-1) thì dừng.
Bước 3. Phân lớp các lớp Ck theo các Ti, i=1…K-1 đã ổn định.
Hình thành các vùng Rk từ các lớp Ck. Gán nhãn các vùng theo giá trị trung bình
của lớp và hiển thị ảnh các vùng đã phân bố.
* Phân vùng dựa vào lý thuyết đồ thị
Trong thời gian gần đây, các nhà nghiên cứu đã đưa ra một số phương pháp
phân vùng dựa trên những hướng tiếp cận mới, trong đó có hướng tiếp cận phân vùng
dựa trên đồ thị. Đối với phương pháp này, hình ảnh sẽ được mô tả như một đồ thị với
các đỉnh của đồ thị là các điểm ảnh và các cạnh trên đồ thị nối các điểm ảnh lân cận
với nhau.
- Biểu diễn ảnh như là một đồ thị
Kỹ thuật phân vùng ảnh dựa trên lý thuyết đồ thị biểu diễn ảnh như là một
đồ thị G = (V, E). Trong đó, V là tập hợp các đỉnh và E là tập hợp các cạnh của đồ thị.
Mỗi đỉnh vi ∈ V tương ứng với các điểm ảnh và các cạnh (v i,vj) ∈ E tương ứng
là cạnh kết nối các cặp điểm ảnh lân cận. Mỗi cạnh (v i,vj) ∈ E có một trọng số
tương ứng là sự khác nhau về màu sắc, cường độ giữa hai điểm ảnh lân cận v i, vj và
được ký hiệu là w(vi,vj).

V: Tập đỉnh

Ảnh = {Điểm ảnh}

E: Tập các cạnh kết nối

Điểm ảnh tương tự

Hình 1.10: Biểu diễn ảnh dưới dạng một đồ thị
+ Đỉnh liền kề
Hai đỉnh vi và vj của đồ thị G được gọi là kề nhau nếu (v i,vj) là cạnh của đồ thị G.
Nếu e = (vi, vj) là cạnh của đồ thị ta nói cạnh này nối đỉnh v i và đỉnh vj, đồng thời các
đỉnh vi và vj sẽ được gọi là các đỉnh đầu của cạnh (vi, vj). Khi đó, bậc deg(v) của đỉnh v

23


là số cạnh nối với nó. Đỉnh bậc 0 được gọi là đỉnh cơ lập, cịn đỉnh bậc 1 gọi là đỉnh
treo.

24


+ Đồ thị con và đồ thị riêng
Đồ thị G’ = (V’, E’) được gọi là đồ thị con của đồ thị G nếu V’⊆ V và E’= E ∩ (V’
× V’).
Đồ thị G”= (V, E”) vớ E” ⊆ E, được gọi là đồ thị riêng của đồ thị G.
Mỗi tập con các đỉnh V’ của đồ thị tương ứng duy nhất với một đồ thị con, do
vậy để xác định một đồ thị con ta chỉ cần nêu tập đỉnh của nó. Cịn đồ thị riêng là đồ

thị giữ nguyên tập đỉnh và bỏ bớt đi một số cạnh.

25