ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
NGUYỄN HỒNG PHÚC
ỨNG DỤNG CỦA PHỨC WITNESS
VÀO PHÂN TÍCH DỮ LIỆU ẢNH
Chuyên ngành: ĐẠI SỐ VÀ LÝ THUYẾT SỐ
Mã số: 60 46 05
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC
TS. NGUYỄN PHÚC SƠN
Tp. Hồ Chí Minh - 2012
Lời cảm ơn
Tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy Nguyễn Phúc Sơn. Nhờ sự hướng
dẫn và chỉ bảo tận tình của thầy mà luận văn đã hoàn thành một cách khoa học
và đúng tiến độ. Xin cảm ơn các thầy cô công tác tại trường Khoa Học Tự Nhiên
đã trực tiếp giảng dạy và quan tâm, cảm ơn các bạn bè và gia đình đã động viên
giúp đỡ tôi trong suốt thời gian học tập và nghiên cứu.
Mặc dù có nhiều cố gắng, song luận văn có thể vẫn còn khiếm khuyết, tôi rất
mong sự phê bình góp ý từ phía các thầy cô và các bạn.
Tp.HCM, ngày 25 tháng 8 năm 2012
Học viên
Nguyễn Hồng Phúc
Mục lục
Lời nói đầu 6
1 Kiến thức chuẩn bò 7
1.1 Các đơn hình . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Phức simplicial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1 Phức simplicial trừu tượng S . . . . . . . . . . . . . . . . . 9
1.2.2 Xấp xỉ simplicial . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Phức
˘

0
, a
1
, a
2
, , a
p
, p ∈ R, là những điểm trong R
d
.
Một điểm x =

p
j=0
λ
j
a
j
là một tổ hợp affine của a
j
nếu

p
j=0
λ
j
= 1,
λ
j
∈ R.

Mặt của σ là bao lồi của một tập hợp con khác rỗng của tập hợp gồm các điểm
a
j
, j = 0, 1, , p.
Một mặt là mặt thực sự nếu mặt đó là bao lồi của một tập con thật sự.
7
Trang 8
Hình 1.1: 0-simplex, 1-simplex, 2-simplex, 3-simplex lần lượt được gọi là vertex,
edge, triangle, tetrahedron.
Biên của σ, ký hiệu bdσ, là phần hợp của tất cả các mặt thực sự trong σ.
Phần trong của σ, ký hiệu intσ = σ − bdσ.
Với mỗi điểm x =

p
j=0
λ
j
a
j
∈ σ, ta có x ∈ intσ khi và chỉ khi mọi λ
j
> 0,
j = 0, 1, , p.
1.2 Phức simplicial
Khái niệm 1.2.1. Một phức simplicial K (xem hình 1.2), là tập hợp hữu hạn các
đơn hình trong K thỏa mãn:
-Với σ ∈ K và τ ⊆ σ thì τ ∈ K.
-Với σ, σ
0
∈ K thì σ ∩ σ

ii) Tập đỉnh Z của phức simplicial trừu tượng S, vertZ = {a
0
, a
1
, , a
p
}, p ∈ R.
iii) Nếu p-simplex σ = [a
0
a
1
a
p
] ∈ S, thì tất cả các mặt của σ đều thuộc S. Ở
đây các đỉnh a
0
, a
1
, , a
p
trong Z là phân biệt.
Nguyễn Hồng Phúc - Cao học Đại số K20
Trang 10
1.2.2 Xấp xỉ simplicial
Từ không gian tôpô X, lấy một tập điểm bất kỳ. Từ tập điểm ấy, ta xây dựng
phức simplicial K xấp xỉ cấu trúc tôpô của X.
Ví dụ 1.2.1. Quét tia laser qua một vật rắn X có hình vòng tròn, ta sẽ thu được
một tập gồm vô số điểm trên mặt phẳng:
Hình 1.3: Tập điểm trên mặt phẳng
Chọn ra một mẫu bất kỳ từ tập điểm trên hình 1.3 ta được hình 1.4. Ta sẽ đi

, R/2), j = 0, 1, , p, giao nhau khác φ.
˘
Cech(Z, R) = {σ ⊆ Z|

a
j
∈σ
B(a
j
, R/2) = φ, j = 0, 1, 2, , p} [1]
Chú ý 1.3.1. Cho F là một tập hợp hữu hạn trong không gian ơclid.
Nerve của F là tập hợp các tập con khác rỗng của F mà giao của họ tập con
này là một tập không tầm thường.
NrvF = {X ⊆ F|

X = φ}
Đònh lý 1.3.2. (Nerve) Cho F là một tập lồi, đóng trong không gian ơclid. Khi đó
NrvF và hợp của các tập con trong F có kiểu đồng điều giống nhau.
Từ đònh ngóa Nerve, ta có phức
˘
Cech là Nerve của tập {B(a, R/2), a ∈ Z}.
Vì các quả cầu B(a, R/2) là lồi nên ta có
˘
Cech tương đương đồng luân với
phần hợp của các quả cầu này.
Nguyễn Hồng Phúc - Cao học Đại số K20
Trang 12
1.3.2 Phức Rips
Tập đỉnh là tập dữ liệu Z ⊂ R
d

của tập hợp các siêu lập phương có cạnh là 2R . Khi đó Rips(Z, R) tương đương
đồng luân với phần hợp của những siêu lập phương này.
Ví dụ 1.3.1.
Hình 1.6:
˘
Cech, Rips
Cho một tập hợp gồm nhiều điểm như hình 1.6(A). Ta vẽ các đường tròn có
cùng bán kính, với tâm là những điểm đã cho, thì được hình 1.6(B).
Ứng dụng của phức witness vào phân tích dữ liệu ảnh
Trang 13
Phức
˘
Cech ở hình 1.6(C) được vẽ như sau:
Hai đường tròn có phần giao khác rỗng, như c
1
∩ c
2
= φ, khi đó ta nối tâm
của hai đường tròn lại với nhau thì được một cạnh O
1
O
2
, làm tương tự các trường
hợp còn lại.
Ba đường tròn có phần giao khác rỗng, như c
3
∩ c
4
∩ c
5

6
∩ c
8
= φ nhưng
c
6
∩ c
7
∩ c
8
= φ do đó ta chỉ có tam giác "rỗng ruột" O
6
O
7
O
8
. Làm tương tự các
trường hợp còn lại.
Phức Rips ở hình 1.6(D) được vẽ như sau:
Giống như khi xây dựng
˘
Cech, hai đường tròn có phần giao khác rỗng, như
c
1
∩ c
2
= φ, khi đó ta nối tâm của hai đường tròn lại với nhau thì được một cạnh
O
1
O

8
và O
6
O
8
rồi tô đặc tam giác O
6
O
7
O
8
.
Chú ý 1.3.3. Ta có:
i) Đònh nghóa của phức
˘
Cech và phức Rips được áp dụng đối với mọi không gian
metric.
ii) Cả hai cấu trúc
˘
Cech và Rips đều không thực sự hiệu quả. Thật vậy, khi bán
kính R tăng đến một giá trò nhất đònh, ta sẽ nhận được một khối dày đặc, lúc
đó không thể phân biệt được
˘
Cech và Rips. (hình 1.7)
Nguyễn Hồng Phúc - Cao học Đại số K20
Trang 14
Hình 1.7: Phức
˘
Cech, Rips
Hai phức

∈ Z.
Bước 2: Giả sử đã chọn được các điểm a
1
, a
2
, , a
j−1
∈ Z, ta tiến hành chọn
a
j
∈ Z \ {a
1
, a
2
, , a
j−1
}. Với mỗi x ∈ Z, ta có các khoảng cách
D(x, a
1
), D(x, a
2
), , D(x, a
j−1
). a
j
được chọn theo tiêu chuẩn sau:
a
j
= max
x∈Z

1
, , a
p
, σ = [a
0
a
1
a
p
] là một
p-simplex.
Đònh nghóa 2.1.2. Điểm x ∈ R
d
được gọi là witness mạnh đối với σ trong L nếu
và chỉ nếu x có khoảng cách tới các điểm a
0
, a
1
, , a
p
đều bằng nhau và là khoảng
cách nhỏ nhất trong L. (Hình 2.2)
Hình 2.2: Witness mạnh và witness yếu
Đònh nghóa 2.1.3. Điểm x ∈ R
d
được gọi là witness yếu đối với σ trong L nếu và
chỉ nếu
|x − a
j
| ≤ |x − a|

∞
(D) như sau:
Nguyễn Hồng Phúc - Cao học Đại số K20
Trang 18
Khái niệm 2.1.6. Ta có:
Tập đỉnh: {a
1
, a
2
, , a
n
} là tập n điểm landmark.
Cạnh σ = [ab] ∈ W
∞
(D) khi và chỉ khi tồn tại i, 1 ≤ i ≤ N , sao cho D(a, i)
và D(b, i) là các khoảng cách nhỏ nhất trong cột thứ i của ma trận D.
Cho p-simplex σ = [a
0
a
1
a
p
], p ≥ n − 1, giả sử tất cả các mặt của σ đều
nằm trong W
∞
(D), khi đó σ ∈ W
∞
(D) khi và chỉ khi tồn tại i, 1 ≤ i ≤ N, sao
cho D(a
0

nó đều thuộc W
1
(D).
Ví dụ 2.1.1. Cho tập hợp điểm như hình 2.3, chọn landmark gồm {a
0
, a
1
, , a
8
}.
Sau khi quan sát, ta có khoảng cách từ a
0
đến điểm mà ta đặt là i, D(a
1
, i), là
Hình 2.3: Phức witness W
∞
(D)
nhỏ nhất, rồi đến các khoảng cách D(a
2
, i), D(a
0
, i). Khi đó, nối ba điểm a
0
, a
1
,
a
2
thành mặt tam giác a

= [a
5
a
6
] ∈
W
∞
(D) với witness k.
Sự hình thành của hai phức W
1
(D) và W
∞
(D) khác nhau! Ta thấy rõ sự khác
biệt đó ở ví dụ 2.1.2 sau đây
Ví dụ 2.1.2. Cho tập hợp điểm như hình 2.4, chọn landmark gồm {a
0
, a
1
, a
2
, a
3
, a
4
}
Hình 2.4: Phức witness W
1
(D)
Sau khi quan sát, điểm mà ta đặt là i có khoảng cách đến a
0

3
= [a
1
a
2
] ∈ W
1
(D).
Khi đã nối được ba cạnh a
0
a
1
, a
0
a
2
và a
1
a
2
, W
1
(D) cho phép ta tô đặc tam
giác a
0
a
1
a
2
. Khi đó, 3-simplex σ = [a

Trang 20
Tập đỉnh của W (D, R, v) là {a
0
, a
1
, , a
n
}.
Cho đoạn σ = [ab], ta có σ = [ab] ∈ W (D, R, v) nếu tồn tại witness
i ∈ {1, 2, , N } sao cho:
max(D(a, i), D(b, i)) ≤ R + m
i
(∗)
Cho p-simplex σ = [a
0
a
1
a
p
], ta có σ = [a
0
a
1
a
p
] ∈ W (D, R, v) nếu và chỉ
nếu tất cả các cạnh của nó thuộc trong W (D, R, v), điều này tương đương với việc
tồn tại witness i, 1 ≤ i ≤ N sao cho:
max(D(a
0

, i), , D(a
p
, i)) ≤ R + m
i
- Nếu R = 0, ta có: W(D, 0, 2) = W (D).
- Khi cho R tăng ta xây dựng được dãy lọc.
Một cách tiếp cận khác đó là sử dụng phân chùm, tham khảo trong [2]. Nhưng
theo kinh nghiệm của những người từng sử dụng thì cách này không thực sự hiệu
quả, vì phương pháp phân chùm tạo thêm các đặc tính vốn không có trong dữ liệu
gốc.
Ứng dụng của phức witness vào phân tích dữ liệu ảnh
Trang 21
2.2 Đồng điều persistent
2.2.1 Số Betti
Trong phần này ta sẽ tìm hiểu về số betti của đồng điều cổ điển.
Số betti được dùng để phân biệt các không gian tôpô. Số betti là một số tự
nhiên hoặc +∞.
Đònh nghóa 2.2.1. Số betii thứ p của không gian X, ký hiệu β
p
(X), là hạng của
nhóm giao hoán H
p
(X).
Ý nghóa hình học của số betti :
β
0
là số thành phần liên thông.
β
1
là số các lỗ 2-chiều.

1
< r
2
< < r
n
,
r
0
= ∞, với r
j
, j = 1, 2, , n , là các số thực. Khi đó ta có các K
j
:= K(r
j
),, là
các phức con của K và
φ = K
0
⊆ K
1
⊆ ⊆ K
n
= K (∗)
Ta gọi dãy các phức (∗) là dãy lọc.
Ví dụ 2.2.2. Cho φ = K
0
, K
1
, , K
7

(K
k
) ,p là số chiều của đồng điều
Ta có dãy các nhóm đồng điều, ứng với số chiều p, tương ứng với dãy lọc (∗):
0 = H
p
(K
0
)
f
0,1
p
−−−−→ H
p
(K
1
)
f
1,2
p
−−−−→
f
n−1,n
p
−−−−→ H
p
(K
n
) = H
p

).
Nhóm đồng điều persistent H
j,k
p
bao gồm những lớp đồng điều trong K
j
mà
vẫn còn tồn tại trong K
k
, nghóa là:
H
j,k
p
= Z
p
(K
j
)/(B
p
(K
k
) ∩ Z
p
(K
j
))
Gọi γ là một lớp trong H
p
(K
j

p
(K
j
)
Ứng dụng của phức witness vào phân tích dữ liệu ảnh
Trang 25
Ví dụ 2.2.3. Cho K = K
14
là một phức simplicial và K
0
, K
1
, , K
14
là các phức
con của K. (Hình 2.8)
Hình 2.8: Tính số betti
Ta có dãy lọc φ = K
0
⊂ K
1
⊂ ⊂ K
14
= K.
Ta tính được số betti ứng với mỗi phức con của K. Ở đây, β
0
là hạng của
H
0
(K), β

, β
1
= 0, khi đó
ta nói lớp γ
1
chết. Vậy thời gian tồn tại của lớp simplex γ
1
được biểu diễn trong
bảng mã vạch là một đoạn thẳng kéo dài liên tục từ K
6
đến K
8
.
Nguyễn Hồng Phúc - Cao học Đại số K20
Trang 26
Hình 2.9: Mã vạch
Xét lớp simplex γ
2
∈ H
1
(K), γ
2
sinh ra ở K
10
, tồn tại đến K
12
và chết ở K
13
nên đoạn thẳng kéo dài liên tục từ K
10

% success 54 51 99 99 53 100 97
median relative dominance 0.038 0.059 0.620 0.808 0.062 0.600 0.798
median absolute dominance 0.034 0.047 0.347 0.163 0.046 0.318 0.152
median relative dominance 208 199 86 94 208 92 92
12 ĐIỂM LANDMARK ĐƯC CHỌN THEO PHƯƠNG PHÁP MAXMIN
Rips Witness: metric ơclid Witness: metric đồ thò
v = 0 v = 1 v = 2 v = 0 v = 1 v = 2
% success 100 100 100 100 100 100 100
median relative dominance 0.184 0.215 0.752 0.924 0.216 0.744 0.922
median absolute dominance 0.161 0.162 0.519 0.252 0.153 0.466 0.209
median relative dominance 74 78 66 79 82 66 80
Trong bảng trên, thực hiện 100 lần thử nghiệm cho mỗi phương pháp trên
landmark đã được chọn. Kết quả thu được sau các lần thử nghiệm cho ta bốn hằng
số R
0
, R
1
, K
0
và K
1
, cụ thể như sau:
(β
0
, β
1
, β
2
) = (1, 0, 1), khi R ∈ [R
0

đònh.
Khoảng hoạt động của đồng điều là đoạn [0, K
0
], đánh dấu các giá trò của
bán kính R khi đồng điều của phức thay đổi.
Khoảng hoạt động của cell là đoạn [0, K
1
], đánh dấu các giá trò của bán
kính R khi số lượng cell của phức thay đổi.
Nguyễn Hồng Phúc - Cao học Đại số K20