MÔ HÌNH PHÂN LỚP FCM
TRONG PHÂN ĐOẠN ẢNH VÀ THUẬT TOÁN DCA
TS. NGUYỄN TRỌNG PHÚC
Bộ môn Công nghệ phần mềm
Khoa Công nghệ thông tin
Trường Đại học Giao thông Vận tải
Tóm tắt: Trong bài báo này, chúng tôi giới thiệu một thuật toán nhanh và mềm dẻo trong
bài toán phân đoạn ảnh thông qua mô hình phân lớp Fuzzy C-Means. Cách tiếp cận của
chúng tôi dựa trên lý thuyết DC (hiệu hai hàm lồi) với thuật toán DCA tương ứng. DC và thuật
toán DCA đã xuất hiện từ năm 1986 được phát triển đến nay và được áp dụng trong nhiều lĩnh
vực khoa học liên quan đến các bài toán tối ưu như trong Machine Learning… Với một cách
tiếp cận mềm dẻo, mô hình FCM ban đầu của bài toán được biến đổi thành mô hình mới mà
DC có thể áp dụng được với thuật toán DCA đơn giản tương ứng. Để cải thiện tốc độ của
thuật toán chúng tôi kết hợp thuật toán DCA và thuật toán FCM theo các cách khác nhau.
Hơn nữa, chúng tôi xét đến mối quan hệ giữa các điểm ảnh trong không gian để đưa thêm
thông tin vào trong mô hình bài toán ban đầu nhằm xử lý các ảnh trong thực tế, các ảnh
nhiễu. Thông qua các kết quả thực tế, chúng tôi thấy được ưu điểm của phương pháp tiếp cận
trong việc tăng tốc độ, chất lượng ảnh phân đoạn với các ảnh khác nhau, đặc biệt là ảnh trong
y học.
Summary: We present a fast and robust algorithm for image segmentation problems via
Fuzzy C-Means (FCM) clustering model. Our approach is based on DC (Difference of Convex
functions) programming and DCA (DC Algorithms) that have been successfully applied in a
lot of various fields of Applied Sciences, including Machine Learning. In an elegant way, the
FCM model is reformulated as a DC program for which a very simple DCA scheme is
investigated. For accelerating the DCA, an alternative FCM-DCA procedure is developed.
Moreover, in the case of noisy images, we propose a new model that incorporates spatial
information into the membership function for clustering. Experimental results on noisy images
have illustrated the effectiveness of the proposed algorithm and its superiority with respect to
the standard FCM algorithm in both running-time and quality of solutions.
CNTT-
CB
I. GIỚI THIỆU CHUNG
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 trong y học ([2]; [3]). 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 toán phân đoạn ảnh được đề xuất,
chúng ta có thể chia ra làm 4 loại sau đây ([9]):
- 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).
Bài báo này đề cập đến thuật toán phân đoạn ảnh dựa trên mô hình Fuzzy C-Means (FCM)
với việc áp dụng lý thuyết DC và thuật toán DCA tương ứng để giải quyết bài toán. Mục đích
của chúng tôi là đưa ra một thuật toán nhanh và mềm dẻo để giải quyết bài toán bởi vì mô hình
phân lớp trong bài toán phân đoạn ảnh là một mô hình lớn, nhiều hướng và cần có một thuật
toán hiệu quả. Hơn nữa, với việc xem xét mối quan hệ liên thông giữa các điểm ảnh, chúng tôi
đã áp dụng thuật toán để thực hiện phân đoạn các ảnh nhiễu.
Bài báo bao gồm 4 chương. Chương 1 giới thiệu chung về bài toán và các tiếp cận thực tế.
Chương 2 trình bày về mô hình FCM cũng như mô hình FCM khi quan tâm đến tính liên thông
của các điểm ảnh. Chương 3 giới thiệu về cách phân rã mô hình theo DC và các thuật toán DCA
kết hợp FCM. Chương cuối đề cập đến các kết quả thu nhận được khi thực hiện các thuật toán
trên các ảnh thực tiễn và các nhận xét về các thuật toán.
II. MÔ HÌNH FCM CỦA BÀI TOÁN
2.1. Mô hình FCM của bài toán
Phân lớp Fuzzy C-Means (CFM) 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 ([2]) bởi sự mở rộng của 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. Với cách tiếp cận này, mỗi hình ảnh với nhiều đặc trưng sẽ được
phân lớp thành các nhóm mà tại đó các điểm ảnh có cùng đặc trưng với nhau. 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.
CNTT-CB
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 phải phân
thành c (0<c<n) phân đoạn {C1, x2, ..., Cc} trong đó xk ∈ ℜ d với k=1,2...n biể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
của các điểm ảnh, khi đó k = 1 và bài toán phân đoạn sẽ dựa trên duy nhất một đặc tính là mức
xám.
Xét ma trận phân lớp mờ (Fuzzy Partition Matrix) U = (ui,k)cn trong đó mỗi phần tử ui,k
chỉ ra khả năng thuộc phân lớp i của một điểm ảnh xk. Khi đó, bài toán phân lớp chính là tối ưu
hoá hàm mục tiêu:
2
ik
n
1k
c
1i
m
k,im vxu)V,U(J −= ∑∑
==
(1)
trong đó ||.|| chính là giá trị chuẩn Euclidean trên không gian tương ứng và ma trận Vcd
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,..1k1uc..1i;n,..1k1,0u
vxu)V,U(Jmin
c
1i
k,ik,i
2
ik
n
1k
c
1i
m
k,im
(2)
Một trong những nhược điểm của các thuật toán FCM là không xét đến đặc tính liên thông
của các điểm ảnh trên một hình ảnh, như vậy kết quả thu nhận được thường bị ảnh hưởng vì các
ảnh thông thường là luôn có nhiễu. Ở đây, khi xét đến các điểm ảnh, chúng ta biết rằng các điểm
ảnh thường có mối liên hệ với các điểm xung quanh. Thông thường, các điểm ảnh xung quanh
mỗi điểm ảnh thường có cùng các đặc tính (ví dụ như mức xám) với điểm ảnh đó và khả năng
chúng có cùng phân lớp là rất cao. Hiện nay, có một số bài báo đề cập đến mối quan hệ giữa các
điểm ảnh như một đặc tính của ảnh trong việc phân lớp theo mô hình FCM ([1]; [7]; [8]).
2.2. Mô hình FCM với quan hệ liên thông giữa các điểm ảnh
Trong bài báo này, chúng tôi xét đến quan hệ của mỗi điểm ảnh với các điểm xung quanh
thông qua giá trị mức xám của chúng. Điều này có nghĩa là, khả năng điểm ảnh và các điểm
xung quanh có cùng mức xám là lớn. Nếu xét theo tính liên thông, một điểm ảnh sẽ có 8 điểm
liên thông xung quanh nó. Như vậy, trên mô hình của bài toán, mỗi điểm ảnh sẽ có 2 đặc tính:
mức xám của điểm ảnh và mức xám trung bình của các điểm ảnh xung quanh xk = (xk1, xk2) ∈
ℜ 2d với xk1 biểu diễn mức xám của điểm ảnh xk và xk2 là giá trị trung bình xk2 = (xk1 +
∑i∈Nkxi)/9 trong đó Nk là tập các điểm xung quanh của xk. Khi xét đến đặc tính này, mô hình
bài toán không thay đổi tuy nhiên độ phức tạp đã thay đổi bởi số lượng biến tăng lên 2 lần.
CNTT-
CB
III. GIẢI THUẬT FCM DỰA TRÊN DC VÀ THUẬT TOÁN DCA
Dễ dàng nhận thấy mô hình của bài toán chính là bài toán tối ưu trên miền không lồi và đây
là một bài toán NP-Complete. Để giải bài toán này, chúng tôi dùng phương pháp DC bằng cách
phân rã hàm mục tiêu thành hiệu hai hàm lồi, sau đó áp dụng thuật toán DCA để giải bài toán.
Phương pháp DC và thuật toán DCA được đưa ra bởi Pham D.T. năm 1985 và được áp dụng
trên nhiều bài toán thực tiễn ([6]).
3.1. DC và thuật toán DCA
Lý thuyết chung của DC trong việc tính giá trị của hàm mục tiêu không lồi là phân tích nó
thành hiệu hai hàm lồi trên không gian
ℜ
p. Một cách đơn giản, chúng ta có thể thấy được mô
hình của bài toán:
{
}
)P(x:)x(h)x(g:)x(finf dc
p
ℜ∈−==α
trong đó: f là hàm mục tiêu và g, h là các hàm lồi nửa liên tục trên miền
ℜ
p.
Xét bài toán đối ngẫu (Ddc):
{
}
)D(y:)y(g)y(hinf dc
p**
Dℜ∈−=α
trong đó h* và g* là các hàm liên hợp của hàm h và g với
{
}
p* x:)x(gy,xsup:)y(g ℜ∈−=
Bằng cách giải đồng thời bài toán (Pdc) và bài toán đối ngẫu (Ddc), người ta chứng minh
được rằng sau hữu hạn các bước, chúng ta có thể xác định được điểm tối ưu cục bộ của bài toán
ban đầu khi mà xk hội tụ về giá trị MIN. Thuật toán DCA được mô tả như sau:
Thuật toán DCA-1:
• Chọn xo
∈ℜ
p
• Thực hiện tính toán theo mỗi bước giá trị xk
o Tính yk
∈
∂
h(xk)
o Tính xk+1
∈
argmin
{
g(x) – h(xk) - <x-xk, yk> : x
∈ℜ
p
}
o k <= k+1
• Kiểm tra sự hội tụ của xk.
Các đặc tính hội tụ của thuật toán được chứng minh trong [6].
3.2. Phân tích DC của mô hình FCM
Theo như các phân tích ở trên, để giải được bài toán, chúng ta sẽ xác định một phân rã hàm
mục tiêu thành hiệu của hai hàm lồi.
Xét biến ti,k sao cho ui,k = t2i,k. Khi đó
.1t
c
1i
k,i
2=
∑
=
Mô hình bài toán sẽ được biểu diễn dưới dạng
⎪
⎩
⎪
⎨
⎧
∏=∈∏=∈
−=
==
==
∑∑
i
1i
c
k
1k
n
2
ik
n
1k
c
1i
k,i
m2
m2
R:CVS:ST
vxt)V,T(Jmin (3)
Như vậy chúng ta có: J2m(T,V) = G(T,V) – H(T,V)
với: )V,T(J)V,T(
2
)V,T(HV
2
n
2
)V,T(G m2
22 −
ρ
=
ρ
+
ρ
= (4)
Chứng minh được rằng G và H là hai hàm lồi trên miền không gian của bài toán.
3.3. Thuật toán DCA trên mô hình FCM
CNTT-CB
Áp dụng thuật toán DCA ở trên bằng cách tính các giá trị xk (ở đây chính là (Tk,Vk)) và yk
của hai bài toán đối ngẫu, chúng ta có:
()
()
⎭
⎬
⎫
⎩
⎨
⎧∈
ρ
∈
∂∈
++ BxC)V,T(:Z,Y,V,TV
2
minarg)V,T(
)V,T(H)Z,Y(
kk
2
1k1k
kkkk
Giá trị trên được xác định tường minh bởi việc tính đạo hàm của các hàm, ta có:
)Z
1
(ojPrVand)Y(ojPrT
)t)xv(2,vxtm2()V,T()Z,Y(
k
C
1kk
B
1k
n
1k k,i
m2
ki
2
ik
k,i
1m2kkkk
ρ
==
−−−ρ=
++
=
−∑
(5)
(6)
Thuật toán DCA-2:
• Chọn (To
,Vo)
∈
(
ℜ
cn,
ℜ
cp)
• Thực hiện tính toán theo mỗi bước giá trị (Tk,Vk)
o Tính (Yk,,Zk) theo (5).
o Tính (Tk+1
,Vk+1) theo (5).
o k <= k+1
• Kiểm tra sự hội tụ của (Tk,,Vk).
3.4. Kết hợp thuật toán FCM và thuật toán DCA
Điều chú ý trong thuật toán DCA ở trên đây chính là việc xác định giá trị ban đầu xo của
thuật toán. Từ các bài toán thực tế, người ta thấy rằng việc xác định giá trị này ảnh hưởng khá
lớn đến giá trị tối ưu của bài toán tìm được.
Qua kinh nghiệm thực tế, chúng ta có thể kết hợp các bước của thuật toán DCA với các
bước của thuật toán FCM để thực hiện giải bài toán hoặc có thể thực hiện một số bước của FCM
để xác định giá trị xo ban đầu cho thuật toán DCA.
Thuật toán DCA-3:
CNTT-
CB
• Chọn (Uo
,Vo) ban đầu của bài toán FCM.
• Thực hiện tính toán theo mỗi bước giá trị
o Tính (Uk,,Vk) theo thuật toán FCM.
o Đặt Tk = sqrt(Uk), tính (Tk+1
,Vk+1) theo thuật toán DCA-2.
o k <= k+1
Kiểm tra sự hội tụ của (Uk,,Vk).
Thuật toán DCA-4: