Lựa chọn đặc trưng LBP
Dựa trên q trình học khơng giám sát và
Phương pháp biểu diễn thưa.
Ứng dụng cho bài tốn nhận dạng ảnh kết cấu màu

Trương Hồng Vinh

2019


Mục lục
Danh sách hình vẽ

1

Tóm tắt

2

1 Tổng quan và cơ sở lý thuyết của đề tài
1.1 Biểu diễn ảnh màu . . . . . . . . . . . . .
1.1.1 Hệ màu . . . . . . . . . . . . . . .
1.1.2 Ảnh vân màu . . . . . . . . . . . .
1.1.3 Đặc trưng cho texture màu . . . .
1.1.4 Toán tử Local binary patterns . . .
1.2 Phân loại ảnh texture . . . . . . . . . . . .
1.2.1 Ngữ cảnh học . . . . . . . . . . . .
1.2.2 Rút gọn dữ liệu . . . . . . . . . . .
1.2.3 Bộ phân lớp K-láng giếng gần nhất
1.3 Kết luận . . . . . . . . . . . . . . . . . . .

. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
(K-NN)
. . . . .

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.

3
3
3
5
7
9
11
12
13
14
14

2 Lựa chọn đặc trưng
2.1 Phân nhóm các phương pháp lựa chọn đặc trưng . . . . . . . .
2.1.1 Ngữ cảnh học . . . . . . . . . . . . . . . . . . . . . . .
2.1.2 Kỹ thuật đánh giá . . . . . . . . . . . . . . . . . . . .
2.2 Ký hiệu và biểu diễn dữ liệu . . . . . . . . . . . . . . . . . . .
2.2.1 Biểu diễn dữ liệu dưới dạng đồ thị . . . . . . . . . . .
2.2.2 Xây dựng đồ thị dựa trên phương pháp biểu diễn thưa
2.3 Lựa chọn đặc trưng LBP . . . . . . . . . . . . . . . . . . . . .
2.4 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

16

16
18
19
19
20
21
22
24

3 Đề xuất và Kết quả
3.1 Hệ số thưa cho lựa chọn histogram . . . .
3.1.1 Ngữ cảnh biểu diễn LBP histogram
3.1.2 Hệ số dựa trên biểu diễn thưa . . .
3.2 Kết quả thực nghiệm . . . . . . . . . . . .
3.2.1 Phương pháp đánh giá . . . . . . .
3.2.2 Các bộ ảnh màu chuẩn . . . . . . .
3.2.3 Kết quả . . . . . . . . . . . . . . .
3.3 Kết luận . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

25
25
25
26
26
26
27
29

32

Tài liệu tham khảo

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.

47


1

Danh sách hình vẽ
1.1
1.2
1.3
1.4
1.5
1.6
1.7

Minh họa ảnh màu trong khơng gian màu RGB và 3 kênh màu tương ứng.
Minh họa về sự biểu diễn màu sắc của lá cây trên các hệ màu khác nhau. .
Minh họa các texture khác nhau. . . . . . . . . . . . . . . . . . . . . . . .

Minh họa các điều kiện quan sát khác nhau của một texture. . . . . . . . .
Minh họa phương pháp tính mã LBP. . . . . . . . . . . . . . . . . . . . . .
Điểm ảnh trung tâm với các kích thước khác nhau . . . . . . . . . . . . . .
Minh họa tính tốn LBP màu dựa trên việc kết hợp thông tin từ 3 kênh
màu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.8 Minh họa phương pháp tính Opponent Color LBP . . . . . . . . . . . . . .
1.9 Minh họa hai texture khác nhau . . . . . . . . . . . . . . . . . . . . . . . .
1.10 Sơ đồ phân loại ảnh texture. . . . . . . . . . . . . . . . . . . . . . . . . . .
1.11 Mơ hình phân loại texture với bước rút gọn dữ liệu. . . . . . . . . . . . . .
1.12 Minh họa bộ phân lớp K-NN . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1
2.2
2.3
3.1
3.2
3.3
3.4
3.5
3.6
3.7

Các bước của phương pháp lựa chọn đặc trưng . . . . . . . . . . . . .
Phân loại phương pháp lựa chọn đặc trưng theo (a) ngữ cảnh học and
kỹ thuật đánh giá. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Sơ đồ tổng quát lựa chọn đặc trưng trong ngữ cảnh học có giám sát. .

4
5
5
6

9
10
11
12
13
13
14
14

. . . 17
(b)
. . . 18
. . . 18

Bộ dữ liệu OuTex-TC-00013 với 69 lớp ảnh khác nhau. . . . . . . . . . . .
Minh họa một số lớp của bộ dữ liệu USPTex . . . . . . . . . . . . . . . . .
Minh họa một số lớp của bộ dữ liệu STex . . . . . . . . . . . . . . . . . . .
Minh họa bộ dữ liệu BakTex. . . . . . . . . . . . . . . . . . . . . . . . . .
Bộ ảnh New BarkTex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Độ chính xác và số lượng histogram được chọn với hệ số SpASL với 3 độ đo.
Độ chính xác với số lượng histogram được chọn của bộ dữ liệu New BarkTex
bởi hệ số thưa trong ngữ cảnh lựa chọn có giám sát và khơng giám sát trên
4 hệ màu khác nhau (RGB (a); HSV (b) ; I1 I2 I3 (c); Y Cb Cr (d)) . . . . .
3.8 Độ chính xác với số lượng histogram được chọn của bộ dữ liệu Outex-TC000013 bởi hệ số thưa trong ngữ cảnh lựa chọn có giám sát và khơng giám
sát trên 4 hệ màu khác nhau (RGB (a); HSV (b) ; I1 I2 I3 (c); Y Cb Cr (d))
3.9 Độ chính xác với số lượng histogram được chọn của bộ dữ liệu USPTex bởi
hệ số thưa trong ngữ cảnh lựa chọn có giám sát và khơng giám sát trên 4
hệ màu khác nhau (RGB (a); HSV (b) ; I1 I2 I3 (c); Y Cb Cr (d)) . . . . . .
3.10 Độ chính xác với số lượng histogram được chọn của bộ dữ liệu STex bởi hệ
số thưa trong ngữ cảnh lựa chọn có giám sát và khơng giám sát trên 4 hệ

màu khác nhau (RGB (a); HSV (b) ; I1 I2 I3 (c); Y Cb Cr (d)) . . . . . . .

28
29
30
31
31
32

33

33

34

34


2

TĨM TẮT ĐỀ TÀI
Dữ liệu với số chiều kích thước lớn sẽ làm giảm hiệu suất tính tốn vì trong đó có
khả năng sẽ xuất hiện các biến dữ liệu nhiễu, thừa và trùng lắp. Xử lý và lưu trữ dữ liệu
như thế sẽ là một thách thức và điều cần thiết là cần phải chọn ra hoặc rút gọn một
tập con các biến dữ liệu có ý nghĩa nhất để rút gọn không gian lưu trữ và giảm độ phức
tạp cũng như thời gian tính tốn của hệ thống. Để giải quyết bài toán phân loại ảnh vân
(texture classification), các phương pháp lựa chọn đặc trưng có giám sát đa số dựa vào
nhãn (label) để xác định các biến có ý nghĩa nhất. Trong thập niên qua, có hàng trăm
phương pháp mô tả và biểu diễn đặc trưng ảnh khác nhau đã được đề xuất cho nhiều ứng
dụng khác nhau trong ngành thị giác máy tính. Một trong số đó, tốn tử Local Binary

Patterns (LBP) được đánh giá là khá thành công trong việc biểu diễn ảnh bởi sự đơn
giản và hiệu quả. Mặc dù được áp dụng rộng rãi nhưng LBP vẫn tồn tại một số bất lợi,
trong đó là việc sinh ra chiều dữ liệu khá lớn khi biểu diễn ảnh màu. Nhằm khắc phục
hạn chế đó, đề tài đề xuất nột phương pháp rút gọn chiều dữ liệu của LBP bằng phương
pháp biểu diễn thưa dựa trên q trình học khơng giám sát.
Bằng việc sử dụng đánh giá lựa chọn đặc trưng bằng hệ số biểu diễn thưa trong ngữ
cảnh học không giám sát, đề tài đã cho thấy sự hiệu quả của đề xuất thông qua quá
trình thực nghiệm trên bốn bộ dữ liệu benchmark về ảnh màu: New BarkTex, OuTexTC-00013, USPTex, STex. Kết quả cho thấy rằng độ chính xác của việc lựa chọn đặc
trưng cho histogram LBP trong ngữ cảnh có giám sát và không giám sát là như nhau.


3

Chương 1
Tổng quan và cơ sở lý thuyết của đề
tài

Chương này cung cấp một số khái niệm cơ bản về phân loại ảnh vân (texture classification). Mục 1.1 trình bày sơ lược các vấn đề về biểu diễn ảnh màu, khái niệm ảnh vân
(texture), toán tử Local Binary Pattern. Mục 1.2 giới thiệu về phân loại ảnh texture với
các ngữ cảnh học và bộ phân lớp thường được sử dụng cho bài toán phân loại texture.

1.1

Biểu diễn ảnh màu

Màu sắc là một yếu tố quan trọng trong hệ thị giác mắt người và trong xử lý ảnh kỹ
thuật số. Màu sắc chứa đựng nhiều thông tin hơn ảnh xám và đã được chứng minh rằng
thơng tin hình ảnh trên ảnh màu có ý nghĩa và giúp tăng cường thơng tin sai biệt cho bài
toán nhận dạng về mẫu [4, 57, 38, 37]. Để biểu diễn và mô tả ảnh màu, cần thiết phải có
khơng gian biểu diễn về vân (texture) và màu sắc. Mục này sẽ giới thiệu một số khơng

gian màu phổ biến dùng trong phân tích ảnh, định nghĩa ảnh màu cũng như một số đặc
trưng chính dùng để biểu diễn ảnh màu.

1.1.1

Hệ màu

Màu sắc là cảm giác mang đến cho hệ thần kinh của người từ sự kết hợp tín hiệu của
ba loại tế bào cảm thụ màu ở mắt người. Các dao động của điện trường trong ánh sáng
tác động mạnh đến các tế bào cảm thụ ánh sáng trong mắt người. Có ba loại tế bào cảm
thụ ánh sáng trong mắt người, cảm nhận 3 vùng quang phổ khác nhau (tức ba màu sắc
khác nhau). Sự kết hợp cùng lúc 3 tín hiệu từ ba loại tế bào này tạo nên những cảm giác
màu sắc phong phú. Để tạo ra hình ảnh màu trên màn hình, người ta cũng sử dụng ba
ánh sáng ở 3 vùng quang phổ nhạy cảm của người [79].
Ảnh màu kỹ thuật số bao gồm ba hình ảnh thành phần và màu sắc của từng pixel
được mã hóa trong khơng gian màu ba chiều, xác định bởi hệ tọa độ màu. Hầu hết các
hình ảnh màu được chụp bởi các thiết bị có mã màu trong khơng gian RGB. Một điểm
trong không gian này được đặc trưng bởi ba thành phần của pixel tương ứng là màu đỏ
(R), màu xanh lá cây (G) và màu xanh lam (B ). Hình 1.1 minh họa một ví dụ về hình
ảnh màu với ba thành phần tương ứng. Các khơng gian màu khác có thể được tính từ
khơng gian RGB bằng các phép biến đổi tuyến tính hoặc phi tuyến. Trong vài năm qua,


4
nhiều khơng gian màu, có các đặc tính về vật lý, sinh lý và tâm lý khác nhau đã được dề
xuất. Chúng được chia thành bốn nhóm như sau [76]:

Kênh màu Red

Kênh màu Green


✁nh màu

Kênh màu Blue

Hình 1.1: Minh họa ảnh màu trong không gian màu RGB và 3 kênh màu tương ứng.

1. Khơng gian màu chính được dựa trên lý thuyết ba màu, với giả định rằng có thể
xem là phù hợp với bất kỳ màu nào bằng cách trộn lẫn thành phần của ba màu
chính. Chúng có thể được chia thành các nhóm nhỏ sau:
• hệ màu chính thực, với các hệ màu chính có thể sinh ra tương ứng ở mực thực
thể vật lý. Ví dụ như hệ màu RGB.
• hệ màu chính ảo, các hệ màu này không tồn tại ở mức vật lý. Mỗi hệ màu có
thể được tạo ra từ hệ chính RGB như CIE XYZ [33].
Hệ màu chính có thể được chuẩn hóa bằng cách chia các kênh màu bởi tổng các
thành phần tương ứng từng kênh để thu về một kênh màu chuẩn hóa, ví dụ như hệ
màu rgb [9] và xyz [33].
2. Các khơng gian màu sắc độ chói được bao gồm một thành phần đại diện cho
thông tin sắc nét (luminance), định lượng thơng tin màu sắc với độ chói (chrominance). Các hệ màu tương ứng trong nhóm này có thể liệt kê như: AC1 C2 [24],
bw rg by [72], L∗ a∗ b∗ , L∗ u∗ v ∗ và U V W [33].
3. Các không gian màu độc lập là kết quả của các phương pháp phân tích thống
kê (Karhunen-Loeve Transform (KLT) or Principal Component Analysis (PCA))
nhằm tạo ra các kênh màu ít tương quan nhất, ví dụ như hệ màu I1 I2 I3 được đề
xuất bởi Ohta [53].
4. Các không gian màu nhận thức được tạo ra với sự nỗ lực nhằm định lượng
màu sắc chủ quan của con người bằng các yếu tố như cường độ, màu sắc và các


5
∗

hab ,
thành phần bão hòa. Một số hệ màu thuộc nhóm này như là ACC1 C2 hC1 C2 , L∗ Cab
∗ ∗
bw Crg by hrg by , Y CIQ hIQ , Y CU V hU V , CIE L Suv huv [33] và LCCh1 Ch2 hCh1 Ch2 .

(b) L*a*b*

(a) RGB

(c) I I I

1 2 3

(d) HSV

Hình 1.2: Minh họa về sự biểu diễn màu sắc của lá cây trên các hệ màu khác nhau.
Thật vậy, một ảnh số màu có thể được biểu diễn trên nhiều hệ màu khác nhau. Dựa
trên hệ thị giác của con người, không gian RGB của ảnh (ảnh 1.1) phản ánh những chiếc
lá trong thế giới thực tốt hơn so với các hệ màu khác

1.1.2

Ảnh vân màu

1.1.2.1

Định nghĩa

Ảnh vân (texture image) thông thường sẽ chứa đựng một vật chất hoặc đối tượng nào
đó được biểu diễn bởi một thông tin về vân (texture). Ảnh 1.3 mô tả các minh họa về 4

loại texture khác nhau (đá, gạch, cát và granit) từ bộ dữ liệu USPTex. Texture thực sự
là một yếu tố quan trong của hệ thị giác người. Hệ thống thị giác của con người có thể
phân biệt khá hiệu quả việc mơ tả các đặc điểm họa tiết bằng các tính từ như mịn hoặc
thô, mịn hoặc thô, dạng hạt hoặc dạng sợi, đẳng hướng hoặc khơng đều và tương phản.
Tuy nhiên, rất khó để xác định texture là gì trong khi con người dễ xác định dựa trên hệ
thị giác. Cho tới thời điểm hiện tại, vẫn chưa có định nghĩa về texture sẽ được công nhận
và chấp nhận một cách thống nhất, và nhiều định nghĩa đã được đề xuất trong các tài
liệu về thị giác máy tính:

(a) Hình ✁nh ✂á

(b) Hình ✁nh g✄ch

(c) Hình ✁nh cát

(d) Hình ✁nh granit

Hình 1.3: Minh họa các texture khác nhau.
• Texture là một thuộc tính cơ bản của sự xuất hiện của hầu như tất cả các bề mặt
tự nhiên và đóng vai trị chính trong các hệ thống thị giác máy tính. Texture có
thể cung cấp thơng tin về các tính chất vật lý của các vật thể, như độ mịn hoặc độ
nhám hoặc sự khác biệt về độ phản xạ bề mặt, hoặc các màu sắc khác nhau [74].


6
• Texture có thể được xem như một mơ hình toàn cục phát sinh từ sự lặp lại của các
mẫu con địa phương [86].
• Một vùng trong ảnh có texture khơng đổi nếu một tập hợp các nhóm thành phần
điểm ảnh không đổi hoặc thay đổi chậm [86].
Các định nghĩa khác nhau về texture dẫn đến nhiều cách khác nhau để phân tích và

diễn giải. Làm thế nào để biểu diễn hiệu quả các mẫu texture là một vấn đề nền tảng của
thị giác máy tính và vấn đề này phụ thuộc vào các điều kiện quan sát của các texture
được xem xét.
1.1.2.2

Ảnh hưởng của điều kiện quan sát

Đặc tính của một texture hoàn toàn phụ thuộc vào một hai tham số bao gồm mức độ
nhận thức và điều kiện quan sát. Liên quan đến mức độ nhận thức, có hai thang đo của
texture có thể được xác định như sau:
• Quan sát ở mức Microscopic: cho thấy cấu trúc không đều hoặc hỗn loạn của
các điểm ảnh màu trên ảnh. Hình 1.4 a tương ứng với texture ở mức quan sát
Microscopic.
• Quan sát ở mức Macroscopic: liên quan đến khái niệm về một mơ hình cơ bản hoặc
một hướng riêng biệt nào đó của các điểm ảnh. Hình 1.4 b tương ứng với texture ở
mức quan sát Microscopic.

(a) Plastic ✁ m✂c quan sát microscopic

(b) Plastic ✁ m✂c quan sát macroscopic

(c) Thay ✄ i h✆☎ng ch✞p c✟a plastic

(d) Thay ✄ i ánh sáng c✟a plastic

Hình 1.4: Minh họa các điều kiện quan sát khác nhau của một texture.


7


Bên cạnh mức độ nhận thức ảnh hưởng đến đặc tính của texture, thơng tin của texture
cũng có thể phụ thuộc vào các điều kiện quan sát như ánh sáng và độ xoay. Ảnh 1.4b với
một góc xoay 90 độ và ảnh 1.4d với sự thay đổi điều kiện ánh sáng (dùng nguồn chiếu
sáng với 4000K thay vì ánh sáng tự nhiên). Do đó, các điều kiện thu thập ảnh với các mức
độ khác nhaucó thể ảnh hưởng đến việc lựa chọn các đặc trưng (mô tả) được sử dụng để
biểu diễn thơng tin texture. Ví dụ, một texture khơng đều sẽ được biểu diễn tốt hơn bởi
các đặc trưng mang tính thống kê, trong khi một kết cấu thơng thường sẽ được mô tả tốt
về các đặc trưng mang tính hình học và dựa trên tần số.
Trong phần tiếp theo, một số đặc trưng phổ biến cho biểu diễn ảnh texture màu sẽ
giới thiệu và phân tích sơ lược.

1.1.3

Đặc trưng cho texture màu

Màu sắc và texture là hai đặc tính có liên quan đến nhau của hình ảnh, nhưng những
đặc điểm này thường được phân tích riêng. Nhiều cơng trình [22, 57, 10] chứng minh rằng
các tính năng texture kết hợp thơng tin màu sắc có thể cải thiện sự phân biệt, đặc biệt là
khi xử lý các texture ảnh tự nhiên được quan sát trong các điều kiện ánh sáng cố định.
1.1.3.1

Sự kết hợp giữa màu sắc và texture

Hai phương pháp chính có thể được xem xét để kết hợp màu sắc và thông tin texture:
xử lý thông tin màu sắc và texture riêng biệt và các phương pháp phân tích kết hợp màu
sắc và texture cùng nhau [52, 19]. Trong cách tiếp cận đầu tiên, các đặc trưng texture
đại diện cho phân bố khơng gian của hình ảnh độ chói được sử dụng cùng với các đặc
trưng khác mô tả phân bố màu trong một không gian màu nhất định [58, 56, 31]. Xét ký
hiệu chung của một không gian màu 3D nhất định (C1 , C2 , C3 ). Ngồi ra cịn cách phương
pháp khác để kết hợp màu sắc và texture bằng cách kết hợp bộ phân lớp để tính tốn sự

tương đồng giữa vector đặc trưng texture và đặc trưng màu [58].
Trong cách tiếp cận thứ hai, các thành phần màu của các điểm ảnh được phân tích.
Nó cho phép cùng đặc trưng phân bố không gian và màu sắc. Trong vài năm qua, một số
nghiên cứu đã được hướng đến vấn đề đại diện chung về kết cấu và màu sắc và ba hướng
khác nhau đã được đề xuất:
• Hướng đầu tiên bao gồm việc đánh giá các tính năng texture trong mỗi thành phần
màu của một hình ảnh (mối quan hệ bên trong thành phần) một cách độc lập, mà
không xem xét các tương tác không gian giữa các cấp độ của hai thành phần màu
sắc riêng biệt. Trong trường hợp này, các tính năng kết cấu được xác định cho hình
ảnh độ chói được áp dụng cho từng trong ba thành phần màu một cách độc lập.
• Hướng thứ hai bao gồm việc đánh giá mức độ phân phối điểm ảnh trong mỗi thành
phần màu của một không gian màu nhất định và giữa các thành phần màu khác
nhau (bên trong và giữa các kênh) [3, 60, 48, 80, 2].
• Cuối cùng, phương pháp thứ ba bao gồm phân tích các tương tác không gian giữa
các màu của điểm ảnh, dựa trên việc xem xét mối quan hệ thứ tự màu xác định độ
lớn giữa các giá trị điểm ảnh màu [63, 42].
Các phương pháp được phát triển trong ngữ cảnh của đề tài dựa trên hướng thứ hai.
Tuy nhiên, hướng này làm tăng số lượng đặc trưng, đặc biệt là khi các mối quan hệ bên


8
trong và giữa các kênh màu được phân tích. Do đó, các phương pháp mà đề tài đề xuất là
nhằm mục đích giảm kích thước của các đặc trưng và khắc phục nhược điểm này. Nhiều
tính năng, ban đầu được xác định để phân tích hình ảnh mức xám, đã được mở rộng cho
một hoặc một số chiến lược kết hợp màu sắc và kết cấu. Chúng tôi đề xuất trong phần
tiếp theo để mô tả các mô tả kết cấu màu chính, trong khn khổ chung của phân loại
kết cấu màu, độc lập với chiến lược kết hợp màu sắc và kết cấu.
1.1.3.2

Đặc trưng texture màu


Phân tích texture là một nhánh nghiên cứu quan trọng của ngành thị giác máy tính,
trong những năm qua, hàng loạt các đặc trưng mô tả ảnh màu đã được đề xuất [68, 75].
Các đặc trưng có thể được phân chia thành ba nhóm tiêu biểu như sau: hình học, khơng
gian tần số và thống kê [74].
• Đăc trưng hình học: Các đăc trưng này có tính đến cấu trúc của ảnh thường
dùng để mô tả và biểu diễn các texture ở múc quan sát quan sát macroscopic. Mơ
tả hình học của một texture bao gồm trích xuất một số đặc trưng gốc như: góc,
cạnh, điểm, đường, đường cong và quy tắc vị trí cho các đặc trưng gốc đó. Zheng et
al. [84] đã đề xuất một tập hợp các đặc trưng hình học cụ thể cho texture của ảnh
về thịt. Tuy nhiên, loại đăc trưng này không cho phép mô tả các texture khơng đều
thường thấy trong các hình ảnh tự nhiên.
• Đặc trưng khơng gian tần số: có thể được chia thành ba miền: miền không gian,
miền tần số và miền tần số không gian.
1. Miền không gian liên quan đến các đăc trưng nhằm đặc trưng hóa texture theo
số lượng chuyển đổi trên một đơn vị diện tích. Các bộ lọc Cumani, Laplace và
Sobel [40] là tất cả các ví dụ về bộ lọc được sử dụng rộng rãi để phát hiện các
cạnh màu. Tuy nhiên, loại đăc trưng này chưa bao giờ được áp dụng để phân
loại hình ảnh texture màu.
2. Biến đổi Fourier hoặc biến đổi cosine rời rạc mang lại một biểu diễn texture
thay thế hoàn toàn dựa trên miền tần số. Các đăc trưng này phù hợp với trường
hợp hình ảnh chứa texture dạng thơ, trong đó có sự liên tục đáng kể giữa các
cấp độ của từng thành phần màu của điểm ảnh. Drimbarean và cộng sự [22]
đã sử dụng phép biến đổi cosine ở mức độ xám và phần mở rộng màu của nó
để mơ tả các texture trong phần thực ngiệm của họ
3. Miền tần số không gian liên quan đến các đặc trưng kết hợp các biểu diễn khác
nhau như đã trình bày ở mục trên. Biến đổi Gabor và biến đổi wavelet được
sử dụng rộng rãi nhất trong phân loại ảnh texture màu, vì chúng có hiệu quả
để phân tích cả macrotextures và microtextures. Một số tác giả đã nghiên cứu
việc sử dụng bộ lọc Gabor trên hình ảnh màu và cho thấy việc sử dụng này

có thể cải thiện kết quả phân loại so với việc sử dụng các đăc trưng ở độ màu
xám [70]. Tuy nhiên, phương pháp này đưa ra các nhược điểm: sự cần thiết
phải cài đặt tham số cho các bộ lọc và thời gian tính tốn nhiều để biểu diễn
các texture nhất định.
• Đặc trưng thống kê có thể được sử dụng để mơ tả bất kỳ loại texture nào. Một
texture được xác định theo mức độ màu xám hoặc biến đổi màu sắc trong một vùng
lân cận các điểm ảnh. Khá nhiều cácđăc trưng thống kê được sử dụng để phân loại


9
ảnh texture màu, bao gồm thống kê hình ảnh (image statistics), biểu đồ hình ảnh
(image histograms), ma trận phối hợp màu sắc (chromatic co-occurrence matrices)
và tổng chênh lệch biểu đồ (sum and difference histograms), mơ hình nhị phân cục
bộ (local binary patterns). Các đặc trưng này có thể được phân nhóm thành một
số loại dựa trên thứ tự tương tác giữa các điểm ảnh của chúng[59, 52].
Trong những năm gần đây, có khá nhiều đặc trưng mơ tả ảnh màu được đề xuất cho
nhiều ứng dụng khác nhau và có những đóng góp quan trọng trong việc phân tích và xử lý
ảnh màu. Một trong số các đặc trưng nổi tiếng có thể kể đến là bộ lọc Gabor [70], mơ hình
Markov ngẫu nhiên [77], Color Descriptors (DCD) [38], Three-Dimensional Adaptive Sum
and Difference Histograms (3D-ASDH) [69], Color Local Binary Pattern [51, 52]. Trong
số đó, tốn tử LBP được chú ý vì khá thành cơng và được áp dụng cho nhiều bài toán xử
lý ảnh texture màu. Phần tiếp theo của báo cáo sẽ trình bày về khái niệm LBP và các
vấn đề liên quan đến toán tử này.

1.1.4

Toán tử Local binary patterns

1.1.4.1


Toán tử LBP gốc

Ojala và cộng sự [55] đề xuất mã hóa mã nhị phân LBP dựa trên nhóm gồm 9 điểm
ảnh xám. Điểm ảnh trung tâm sẽ so sánh với 8 điểm ảnh lân cận và mã hóa thành mã
nhị phân 8 bit và chuyển đổi thành mã LBP. Nếu giá trị điểm ảnh lân cận lớn hơn hoặc
bằng giá trị điểm ảnh trung tâm thì thu về bit 1, ngược lại sẽ là bit 0. Hình 1.5 mơ tả
cách tính mã LBP từ 9 điểm ảnh xám.

Nhóm 3 x 3
điểm ảnh xám

Mã nhị phân
00110100

3

3

32

0

6

10

23

0


1

13

8

0

0

1

LBP = 4 + 8 +32 = 44

1

1

1

128

0

64

2

32


4

0

8

0

16

0

0

4
8

32

0

Nhân

Nhị phân hóa

Hình 1.5: Minh họa phương pháp tính mã LBP.
Một cách tổng qt, tốn tử LBP có thể áp dụng để tính mã LBP trong một lân cận
số lượng điểm ảnh khác nhau. Cho bán kính R và P số lượng điểm ảnh cần so sánh với
điểm ảnh trung tâm dựa trên giá trị xám mã LBPP,R (xc , yc ) của từng điểm ảnh được tính
bằng cách so sánh giá trị trung tâm gc và giá trị trong một lân cận các điểm {gi }P−1

i=0 với
P điểm ảnh, ta có cơng thức như sau:
P−1

Φ(gi − gc ) × 2i

(1.1)

1 nếu (gi − gc ) ≥ 0,
0 ngược lại.

(1.2)

LBPP,R (xc , yc ) =
i=0

với Φ là hàm phân ngưỡng:
Φ(gi − gc ) =


10
Bằng cách thay đổi giá trị R và P, ta có thể mã hóa mã LBP ở nhiều mức độ khác
nhau. Ví dụ với LBP16,2 , tương ứng với bán kính số lượng điểm ảnh trong một lân cận 16
điểm ảnh và bán kính có giá trị là 2, mã LBP sẽ sinh ra 2P giá trị khác nhau, tương ứng
với một histogram có kích thước số chiều là 2P . Hình 1.6 minh họa cách tính mã LBP
dựa trên sự thay đổi về bán kính và số điểm ảnh lân cận.

0

2

1
3

7
5
6

(a) LBP8,1

4

(b) LBP16,2

Hình 1.6: Điểm ảnh trung tâm với các kích thước khác nhau : (a) LBP8,1 và (b) LBP16,2 .
Mặc dù LBP có một số ưu điểm nhưng cũng có những nhược điểm đáng kể: nó nhạy
cảm với xoay hình ảnh và nhiễu, nó chỉ thu được texture rất cục bộ và không phát hiện
ra cấu trúc của các texture quy mơ lớn [73]. Kể từ cơng trình của Ojala, nhiều biến thể
của toán tử LBP đã được đề xuất để cải thiện hiệu năng cũng như chống nhiễu và tăng
khả năng ứng dụng vào các loại vấn đề khác nhau như phân tích hình ảnh khn mặt,
sinh trắc học, phân tích hình ảnh y tế, phân tích chuyển động và truy xuất dựa trên nội
dung [45].
1.1.4.2

LBP cho ảnh màu

Tính tốn mã hóa LBP xuất phát điểm dựa trên hình ảnh xám. Tuy nhiên, một số
cơng trình đã chứng minh rằng thông tin màu sắc rất quan trọng để thể hiện các texture,
đặc biệt là trong biểu diễn các texture tự nhiên [25]. Một số biến thể LBP cho ảnh màu
đã được đề xuất, trong phạm vi đề tài của vấn đề rút gọn dữ liệu, hai biến thể quan trọng
và phổ biến nhất được giới thiệu như sau:

• Phương pháp thứ nhất bao gồm việc áp dụng toán tử LBP một cách độc lập trên
mỗi ba kênh của hình ảnh màu, mà khơng xem xét các tương tác không gian giữa
các điểm ảnh với các cấp độ của hai thành phần màu khác nhau. Bộ mô tả kết
texture được bằng cách ghép ba biểu đồ LBP lại với nhau dưới dạng một histogram
nối dài. Hình 1.7 minh họa phương pháp này trên kênh màu (C1 , C2 , C3 ). Một số
cơng trình đã áp dụng phương pháp này để mô tả ảnh màu như [59, 28, 16, 6, 85].
• Phương pháp thứ hai bao gồm việc tính đến các tương tác khơng gian của các điểm
ảnh bên trong và giữa các thành phần màu. Để mô tả texture màu, một dạng LBP
màu (Opponent Color LBP) đã được đề xuất [52]. LBP được áp dụng trên từng
điểm ảnh và cho từng cặp điểm ảnh (Ck , Ck ), k, k ∈ {1, 2, 3}. Các cặp (C1 , C2 ) và
(C2 , C1 ) được xem là trùng thông tin và chỉ sử dụng một trong hai. Điều này dẫn
đến việc mô tả một kết cấu chỉ với sáu cặp histogram ((C1 , C1 ), (C2 , C2 ), (C3 , C3 ),
(C1 , C2 ), (C1 , C3 ), (C2 , C3 )). Tuy nhiên, với bài toán lựa chọn đặc trưng và rút gọn
dữ liệu, 9 histogram được quan tâm hơn vì nó sẽ chứa đựng được nhiều thông tin để


11
Color
image
nh màu

Kênh
màu C
Component
image
1

nhimage
LBP cofa
LBP

C
màu
thekênh
component
C1
1

Kênhimage
màu C
Component

LBPnhimage
LBP cof a
the kênh
màu C
C2 component
2

Component
Kênhimage
màu C3
2

LBPofc a
LBP nh
image
màu C
the Ckênh
3 component
3


K TH P
CONCATENATION

Hình 1.7: Minh họa tính tốn LBP màu dựa trên việc kết hợp thông tin từ 3 kênh màu.
mô tả ảnh, bao gồm 3 cặp histogram cho các kênh ((C1 , C1 ), (C2 , C2 ), (C3 , C3 )) và 6
cặp cho các kênh ((C1 , C2 ), (C2 , C1 ), (C1 , C3 ), (C3 , C1 ), (C2 , C3 ), (C3 , C2 )). Một số
cơng trình đã áp dụng phương pháp này như [52, 14, 15, 62, 61, 36]. Hình 1.8 mơ
tả các bước tính tốn LBP màu cho trường hợp này.

1.2

Phân loại ảnh texture

Phân loại texture là một vấn đề cho phép gán một nhãn nhất định cho một nhóm
texture . Đây là một vấn đề nền tảng của thị giác máy tính, đóng một vai trị quan trọng
trong nhiều ứng dụng như phân tích hình ảnh y sinh, kiểm tra cơng nghiệp, phân tích
hình ảnh vệ tinh hoặc trên khơng, phân tích tài liệu, phân tích khn mặt, sinh trắc học
và nhiều hơn nữa. Phân loại texture màu đã trở thành một chủ đề đầy thách thức bởi vì
hình ảnh trong thế giới thực thường thể hiện mức độ phức tạp, ngẫu nhiên. Ví dụ: hai
hình ảnh chứa cùng một màu với các mẫu texture khác nhau hoặc cùng một mẫu texture
nhưng các màu khác nhau được coi là các texture màu khác nhau [22]. Hình 1.9 (a-b)
minh họa hai hình cùng màu sắc nhưng với các texture khác nhau 1.9 (c) và 1.9 (d) biểu


12
The analysed pixel
m color
nh màu
ofithe

imagephân
and tích
9 i m nh
its 3 xv3 ineighborhood

Color
components

C1

20

30

C2

C3

10

Phân
ngưỡng
Thresholding

Trọng số

((C( 1 , ,C2))

Thresholding
Phân

ngưỡng

Trọng số

(C
( 2 ,, C1)

Thresholding
Phân
ngưỡng

Trọng số

(C1 , C3)

Thresholding
Phân
ngưỡng

(C
, ,C11))
((C11,C

10

Trọng số

Hình 1.8: Các bước khác nhau để tính các cặp (C1 , C1 ), (C1 , C2 ), (C2 , C1 ) và (C1 , C3 ) cho
1 điểm ảnh được xem xét.
diễn ảnh của texture viên đá với màu sắc khác nhau.

Phân loại texture màu thường được chia thành hai nhóm biểu diễn đăc trưng và phân
lớp 1.10. Bước tạo đặc trưng cho phép mô tả hình ảnh nhờ vào đặc trưng texture và bước
quyết định gán đặc trưng này cho một trong các lớp texture. Đề tài sẽ tập trung vào việc
đề xuất các giải pháp ở bước tạo và mô tả đặc trưng.

1.2.1

Ngữ cảnh học

Dựa vào nhãn của dữ liệu được cung cấp để huấn luyện mơ hình, sẽ có ba ngữ cảnh
học khác nhau như sau [34]:


13

(a )

(b )

(c )

(d )

Hình 1.9: Minh họa hai texture khác nhau cùng màu sắc (a-b) và cùng một texture với
hai màu sắc khác nhau (c-d).
nh
texture

T o
c tr ng


c tr ng

Quy t

nh

Nhãn

Hình 1.10: Sơ đồ phân loại ảnh texture.
1. Học có giám sát (Supervised classification): dữ liệu đầu vào cần có nhãn để huấn
luyện. Q trình này có thể được đánh giá thành hai bước, huấn luyện và quyết
định. Trong bước huyấn luyện, việc tạo đặc trưng được áp dụng trên một số hình
ảnh texture màu với nhãn đã biết. Bước dự đốn sẽ gán nhãn cho hình ảnh này,
dựa trên thước đo tương đồng giữa vector đặc trưng được hụyấn luyện và vector
đặc trưng của hình ảnh kiểm tra.
2. Học không giám sát (Unsupervised classification): việc tạo đặc trưng hồn tồn
khơng dùng đến nhãn dữ liệu mà chỉ phụ thuộc hoàn toàn vào giá trị đầu vào được
cung cấp. Mơ hình hồn tồn khơng trải qua bước huấn luyện mà đi thẳng vào bước
quyết định.
3. Học nữa giám sát (Semi-supervised classification): việc huyấn kuyện được dựa trên
nhãn được cung cấp một phần hoặc rất hạn chế.

1.2.2

Rút gọn dữ liệu

Với ba ngữ cảnh học khác nhau cho bài toán phân loại texture, ta có thể bổ sung một
bước rút gọn kích thước dữ liệu trước bước ra quyết định (như hình 1.11). Việc rút gọn
này có thể cho phép chúng ta có được một mơ hình tốt hơn và gọn nhẹ. Ví dụ về việc

biểu diễn mơ tả ảnh màu bằng đặc trưng EOCLBP màu, ta cần phải có 256 × 9 = 2.304
bins (hay đặc trưng) để biểu diễn một ảnh màu. Rõ ràng, không hẳn 2.304 đặc trưng này
sẽ cùng đóng góp cho việc xây dựng mơ hình, có thể một số đặc trưng là khơng cần thiết


14
và thừa. Do đó việc rút gọn là khá cần thiết. Nhiều cơng trình đã đề cập và giải quyết
vấn đề rút gọn chiều dữ liệu cho đặc trưng LBP màu.

nh
texture

T o
c tr ng

c
tr ng

Rút g n
kích th c

c tr ng
rút g n

Quyết định

Nhãn

Hình 1.11: Mơ hình phân loại texture với bước rút gọn dữ liệu.
Dựa vào đặc trưng gốc ban đầu có bị chuyển đổi sang miền khơng gian khác hay

khơng, ta có thể phân phương pháp rút gọn dữ liệu thành hai nhóm: biến đổi đặc trưng
(feature extraction) và lựa chọn đặc trưng (feature selection). Đề tài này sẽ tập trung vào
việc giải quyết vấn đề lựa chọn đặc trưng cho LBP màu trong ngữ cảnh học không giám
sát. Các phương pháp này sẽ được giới thiệu chi tiết ở chương 2.

1.2.3

Bộ phân lớp K-láng giếng gần nhất (K-NN)

Một bộ phân lớp là một hàm số sử dụng các đặc trưng là biến đầu vào với biến đầu ra
là nhãn của đặc trưng này. Có khá nhiều bộ phân lớp khác nhau [43] đã được đề xuất. Với
bài toán phân loại đặc trưng và rút gọn dữ liệu thì K-NN là một trong số các bộ phân lớp
được sử dụng thường xuyên nhất[18, 1]. Trên miền không gian đặc trưng, khoảng cách
giữa mỗi ảnh kiểm tra và ảnh huấn luyện trong một lân cận K được tính tốn và so sánh.
Ảnh kiểm tra sẽ được gán cho nhãn gần nó nhất trùng với số lượng K ảnh huấn luyện.
Bộ phân lớp này phụ thuộc vào một số tham số như giá trị K và độ đo khoảng cách được
sử dụng để tính tốn. Nhìn chung, so với các bộ phân lớp khác thì K-NN vẫn đơn giản
hơn về mặt tính tốn và vẫn thường được xem là một bộ phân lớp phi tham số khi giá
trị K=1. Ví dụ minh họa về bộ phân lớp K-NN được minh họa ở hình 1.12. Dựa vào giá
tri của K, ảnh kiểm tra (đại diện bởi ngôi sao màu xanh) seẽ được gán theo nhãn của
lớp A hoặc lớp B. Nếu K=3, ảnh này sẽ thuộc về nhóm A, ngược lại, khi K=5, ảnh này
sẽ thuộc về nhóm A.
L pA
L pB

?

Hình 1.12: Minh họa 3-NN và 5-NN.

1.3


Kết luận

Bài toán phân loại ảnh texture là một trong những chủ đề quan trọng và là vấn đề
nền tảng của ngành thị giác máy tính. Biểu diễn ảnh texture đi từ ảnh xám chuyển sang
ảnh màu vì nó chứa đựng nhiều thơng tin hơn và có khả năng đóng góp hiệu quả cho việc


15
phân loại hoặc nhận dạng. Đặc trưng LBP là một trong những nỗ lực nhằm đề xuất ra
một mơ hình biểu diễn đặc trưng cho ảnh texture. Các biến thể LBP màu đã được đề xuất
khá hiệu quả nhưng nó lại bộc lộ một nhược điểm về chiều của dữ liệu khá lớn. Nhằm
khắc phục vấn đề đó, một số phương pháp đề xuất rút gọn dữ liệu LBP màu. Chương
tiếp theo của báo cáo sẽ trình bày về phương pháp lựa chọn đặc trưng thường được sử
dụng để rút gọn kích thước dữ liệu.


16

Chương 2
Lựa chọn đặc trưng
Các bài toán trong lĩnh vực máy học (machine learning) nói chung hay thị giác máy
tính nói riêng thường gặp phải vấn đề xử lý dữ liệu với kích thước lớn. Trên thực tế,
khơng hẳm tất cả những đặc trưng dữ liệu đều đóng góp vào phần kết quả , trong số đó
sẽ có một số đặc trưng không liên quan đến việc biểu diễn mô hình. Với vấn đề biểu diễn
ảnh màu bằng đặc trưng LBP, số chiều sẽ càng lớn khi số lượng điểm ảnh lân cận được
sử dụng nhiều hơn. Do đó việc rút gọn kích thước LBP là một vấn đề cần thiết.
Các phương pháp rút gọn kích thước dữ liệu được phân thành hai họ chính: biến đổi
đặc trưng và lựa chọn đặc trưng. Trong số đó phương pháp biến đổi đặc trưng biến đổi
tập dữ liệu sang một không gian mới và có kích thước ngắn hơn ban đầu bằng các phương

pháp tuyến tính hoặc phi tuyến. Sự biến đổi này làm mất đi ý nghĩa vật lý ban đầu của
đặc trưng trên miền không gian chuyển đổi. Một số phương pháp biến đổi đặc trưng phổ
biến có thể kể ra đó là Principal Component Analysis (PCA) [23], Locality Preserving
Projections (LPP) [30]. Ngược lại với phương pháp biến đổi đặc trưng, phép lựa chọn đặc
trưng vẫn giữ nguyên và không thay đôi giá trị của các đặc trưng gốc. Trong những năm
gần đây, lựa chọn đặc trưng đã được áp dụng cho nhiều lĩnh vực khác nhau như máy
học [49], phân tích dữ liệu [21], truy vấn và nhận dạng thông tin đa phương tiện [67] hoặc
theo dõi đối tượng [83]. Đề tài sẽ tập trung vào việc lựa chọn đặc trưng LBP màu cho bài
toán nhận dạng ản texture.
Phần tiếp theo của chương được tổ chức như sau. Mục 2.1 giới thiệu sơ lược về lựa
chọn đặc trưng với các khái niệm cơ bản và ngữ cảnh học khác nhau. Mục 2.2 trình bày
các ký hiệu và phương pháp biểu diễn đặc trưng. Tiếp theo là phần trình bày về các kỹ
thuật sắp xếp đặc trưng ở mục ??. Mục 2.4giới thiệu các phương pháp rút gọn đặc trưng
LBP.

2.1

Phân nhóm các phương pháp lựa chọn đặc trưng

Lựa chọn đặc trưng là một tiến trình nhằm chọn ra một tập con đặc trưng tốt nhất
của tập dữ liệu từ một tập gốc ban đầu. Có hai loại đặc trưng được định nghĩa là : đặc
trưng có liên quan và đặc trưng khơng liên quan [35]. Với bài tốn phân lớp, đặc trưng
có liên quan là những đặc trưng chứa đựng các thơng tin phân biệt (trong ngữ cảnh học
có giám sát) hoặc cụm (ngữ cảnh học không giám sát). Ngược lại, đặc trưng không liên
quan là những đặc trưng gây nhiễu thông tin hoặc các đặc trưng trùng nhau và gây khó
khăn cho sự phân lớp. Việc loại bỏ những đặc trưng không liên quan nhằm tăng cường
hiệu quả của việc phân lớp cũng như giảm kích thước lưu trữ dữ liệu.


17

Dựa theo Dash và Liu, lựa chọn đặc trưng là một tiến trình bao gồm 4 bước (như
minh họa ở hình 2.1 [20]).

Hình 2.1: Các bước của phương pháp lựa chọn đặc trưng [20].

1. Bước khởi tạo dựa trên các kỹ thuật tìm kiếm nhằm đánh giá các tập con đặc
trưng được sinh ra. Mục tiêu của bước này nhằm tìm kiếm một tập con các đặc
trưng tối ưu nhất. Các kỹ thuật tìm kiếm thường dựa trên ba kỹ thuật: đầy đủ,
tuần tự và ngẫu nhiên [44]:
• Đầy đủ tìm kiếm tất cả các tập con sinh ra được từ tập đặc trưng gốc. Nếu
dữ liệu có kích thước là D đặc trưng, sẽ sinh ra 2D tập con đặc trưng có thể
sinh ra. Phương pháp này khá tốn kém về mặt thời gian tính tốn vì nó phải
qt hết tất cả các trường hợp kết hợp các tập đặc trưng có thể sinh ra.
• Tuần tự: Xuất phát từ một tập đặc trưng rỗng, lần lượt bổ sung các đặc trưng
từ dưới lên trên hoặc từ trên xuống. Có hai phương pháp thường sử dụng nhấ là
Sequential Forward Selection (SFS) và Sequential Backward Selection (SBS).
• Ngẫu nhiên: Xuất phát từ một tập đặc trưng ngẫu nhiên và thêm vào hoặc
xóa các đặc trưng vào tập đó một cách ngẫu nhiên.
2. Bước đánh giá sẽ tính tốn tập các đặc trưng được sinh ra từ bước khởi tạo. Nó
sẽ so sánh với các tập đã được đánh giá trước đó, nhằm thay thế nếu tìm ra tập con
tốt hơn. Bước này có thể độc lập với bộ phân lớp hoặc sử dụng bộ phân lớp như là
một phương tiện để đánh giá [39].
3. Tiêu chuẩn dừng quyết định khi nào thuật toán ngưng tại mỗi bước lặp để quyết
định tiến trình lựa chọn đặc trưng cịn tiếp tục nữa hay khơng ? Nếu khơng có một
tiêu chuẩn dừng cụ thể, thuật tốn sẽ chạy vơ hạn. Các bước khởi tạo và đánh giá
ảnh hưởng rất nhiều đến việc lựa chon tiêu chuẩn dừng. Tiêu chuẩn này có thể bao
gồm: số lượng các đặc trưng đã đạt được, số lần lặp được chọn trước.
4. Bước hợp lệ xác định tập con đặc trưng có phì hợp hay khơng ngay sau khi tiêu
chuẩn dừng kết thúc.
Dựa vào các phương pháp lựa chọn đặc trưng, ta có thể chia ra thành 2 nhóm chính

dựa trên 2 tiêu chuẩn đó là kỹ thuật đánh giá và ngữ cảnh học. Hình 2.2a và figure 2.2b
mơ tả 2 nhóm này. Phần tiếp theo sẽ đi sâu vào trình bày kỹ thuật đánh giá và ngữ cảnh
học của phương pháp lựa chọn đặc trưng.


18
L✁ c

Có giám sát
Ng✂ c✄nh
h✁c

N✂a giám sát

Kỹ thuật
☎ánh giá

Cuốn
Lai

Khơng giám sát

(b)

(a)

Hình 2.2: Phân loại phương pháp lựa chọn đặc trưng theo (a) ngữ cảnh học and (b) kỹ
thuật đánh giá.

2.1.1


Ngữ cảnh học

Dựa vào thông tin huấn luyện được cung cấp, lựa chọn đặc trưng có thể chia ra thành
3 nhóm: học có giám sát, nữa giám sát và khơng giám sát [8]. Hầu hết các phương pháp
lựa chọn đặc trưng trong ngữ cảnh học có giám sát và nữa giám sát đều dựa trên nhãn
của dữ liệu để đánh giá mức độ liên quan của đặc trưng.
• Phương pháp có giám sát: Nhãn của dữ liệu sẽ quyết định độ tương quan của
các đặc trưng. Hình 2.3 mơ tả sơ đồ tổng quát của lựa chọn đặc trưng trong ngữ
cảnh học có giám sát. Các tập đặc trưng được chọn sẽ được dùng cho tập dữ liệu
huấn luyện để đưa ra quyết định và dựa đoán nhãn. Phương pháp này phụ thuộc
hồn tồn vào cơng đoạn đánh nhãn, vốn được thực hiện bởi con người và đôi khi
mang ý chủ quan.
Giai o n h c
Nhãn
D li u

c tr ng
sinh ra

L a ch n
c tr ng

c tr ng
c
l a ch n

Xây d ng bộ
phân lớp


T p hu n luy n

D li u

Đặc trưng
sinh ra

c tr ng
liên quan

Quy t nh

d

Nhãn
oán

T p ki m tra
Giai o n phân lớp

Hình 2.3: Sơ đồ tổng quát lựa chọn đặc trưng trong ngữ cảnh học có giám sát.
• Khơng giám sát: là một ngữ cảnh thách thức hơn vì thiếu nhãn huấn luyện. Các
tập con đặc trưng được chọn dựa trên sự tương đồng của dữ liệu để xác định mức
độ liên quan. Sau bước lựa chọn đặc trưng, thuật toán phân cụm được áp dụng để
ra quyết định.
• Nữa giám sát: Trên thực tế, nhãn của dữ liệu bị hạn chế và tốn nhiều chi phí cho
việc đánh nhãn tồn bộ dữ liệu. Đơi khi chỉ có một phần dữ liệu được gán nhãn.


19

Ngữ cảnh học nữa giám sát khai thác dữ liệu của hai ngữ cảnh giám sát với một
phần (hạn chế) dữ liệu và một phần khơng giám sát để tìm ra tập con đặc trưng.

2.1.2

Kỹ thuật đánh giá

Dựa trên các kỹ thuật đánh giá, lựa chọn đặc trưng được chia theo 3 nhóm sau: phương
pháp lọc (filter), cuốn (wrapper) và lai (hybrid) [27].
• Phương pháp lọc được xem như là một phương pháp tiền xử lý dữ liệu và hoàn
toàn độc lập với bộ phân lớp. Ở bước đầu tiên, các đặc trưng được sắp xếp dựa
trên các tiêu chuẩn được chọn, có thể theo từng đặc trưng riêng lẻ hoặc một nhóm
các đặc trưng. Phương pháp này chủ yếu dựa trên đặc tính và giá trị của dữ liệu.
Ở bước tiếp theo, các đặc trưng không ưu tiên sẽ được loại bỏ và chỉ giữ lại các
đặc trưng có ý nghĩa nhất. Tuy nhiên phương pháp này có hạn chế là có thể loại bỏ
một số đặc trưng liên quan đến bộ phân lớp. Một số phương pháp lọc phổ biến là
Variance [11], Laplacian [29] và Fisher [26]/
• Phương pháp cuốn đánh giá tập con đặc trưng được sinh ra dựa trên bộ phân
lớp bằng tiêu chuẩn độ chính xác. Phương pháp này khá tốn về thời gian tính tốn
nếu dữa liệu có kích thức lớn, tuy nhiên kết quả thường tốt hơn so với phương pháp
khác.
• Phương pháp lai kết hợp cả hai phương pháp lọc và cuốn để tạo ra một mơ hình
hiệu quả và tốt hơn việc sử dụng riêng lẻ [50]. Phương pháp lọc sẽ đánh giá sơ bộ
các đặc trưng trước khi đưa vào phương pháp cuốn để xác định độ chính xác của
mơ hình ước lượng.
Trong số các phương pháp lựa chọn đặc trưng dựa trên kỹ thuật đánh giá, đề tài quan
tâm đến phương pháp lai với những ưu thế đã phân tích. Phần tiếp theo sẽ trình bày các
phương pháp lựa chọn đặc trưng cho vấn đề phân loại ảnh texture trong các ngữ cảnh
khác nhau. Trước khi trìn bày các phương pháp này, các ký hiệu toán học dùng để biểu
diễn được trình bày trước.


2.2

Ký hiệu và biểu diễn dữ liệu

Trong ngữ cảnh liên quan đến bài toán lựa chọn đặc trưng, ta có một tập dữ liệu với
N ảnh texture màu được định nghĩa trong một không gian D đặc trưng. Các ký hiệu viết
nghiêng biểu thị cho các thành phần vô hướng, ký hiệu in đậm biểu thị cho vector hoặc
ma trận (ví dụ như, x, x, X). Ta ký hiệu X = (xri ), i ∈ {1, ..., N }; r ∈ {1, ..., D} tương
ứng một ma trận được mô tả như công thức 2.1, với xri là giá trị đặc trưng r của ảnh màu
Ii .

  1

x1
x1 ... xr1 ... xD
1
 ...   ... ... ... ... ... 

  1

1
r
D
r
D 
 
X=
(2.1)
 xi  =  xi ... xi ... xi  = f ... f ... f

 ...   ... ... ... ... ... 
xN
x1N ... xrN ... xD
N


20
Mỗi dòng của N dòng của ma trận X đại diện cho một ảnh màu tương ứng với
D
xi = (x1i , ..., xri , ..., xD
i ) ∈ R , mỗi D cột của ma trận X đại diện cho một vector đặc trưng
r
f , được định nghĩa như sau:
 r   r 
x1
f1
 ...   ... 
 r   r 
 

fr = 
(2.2)
 xi  =  f i 
 ...   ... 
xrN
fNr
Trong trường hợp học không giám sát, thông tin về nhãn của từng lớp ảnh được cung
cấp. Cho vector y đại diện cho nhãn của các ảnh khác nhau và được xác định bới:



y1
 ... 



y
y=
(2.3)
i


 ... 
yN
với yi ∈ {1, .., c, ..., C}, C là số lượng lớp ảnh của dữ liệu đầu vào. Với mỗi ảnh màu
Ii , ta có vector đặc trưng xi tương ứng với nhãn dữ liệu yi .
Biểu diễn dữ liệu dưới dạng một cấu trúc đồ thị xây dựng trên miền không gian đặc
trưng sẽ phản ánh tốt các đặc tính của dữ liệu và từ đó có thể rút gọn số chiều [46]. Lý
thuyết đồ thị phổ được đề xuất là một công cụ khá hiệu quả cho việc rút gọn dữ liệu.
Các phương pháp lựa chọn đặc trưng của đề tài dựa trên nền tảng của lý thuyết đồ thị.
Phần tiếp theo của báo cáo sẽ tập trung vào giới thiệu các phương pháp xây dựng đồ thị
có liên quan đến hướng tiếp cận này.

2.2.1

Biểu diễn dữ liệu dưới dạng đồ thị

Cho tập dữ liệu X, với G = (V, E) là một đồ thị vô hướng được xây dựng từ ma trận
X, với V = {v1 , ..., vN } là các đỉnh và E là tập các cạnh của đồ thị. Mỗi đỉnh vi đại diện
cho một ảnh xi và mỗi cạnh đại diện cho một cặp đỉnh được xác định bởi một trọng số
sij ≥ 0. Độ tương đồng của ma trận là S = (sij )i,j=1,...,N , do G vơ hướng nên ta ln có

sij = sji . Có nhiều cách để chuyển một tập dữ liệu sang dạng biểu diễn đồ thị với độ
tương đồng sij . Trong đó có 3 cách phổ biến là đồ thị lân cận , k -láng giềng gần nhất và
đồ thị đầy đủ [47, 7, 17].
• lân cận : các điểm dữ liệu trong cùng một khối cầu có tâm là xi với một bán
kính sẽ hình thành một độ thị tương đồng. Các điểm dữ liệu phải có khoảng cách
(tương đồng) nhỏ hơn ngưỡng giá trị được định nghĩa.
• k -láng giềng gần nhất: một cạnh được tạo ra nếu hai điểm xi và xj gần nhau và
xi nằm trong khoảng k điểm lân cận gần nhất với xj .
• kết nối đầy đủ: mọi điểm dữ liệu sẽ được kết nối với nhau và tính độ tương đồng
giữa các cạnh bởi sij . Có nhiều cách khác nhau để tính tốn độ tương đồng. Belkin
và Niyogi [7] áp dụng hàm kernel với các phương sai Gaussian khác nhau của giá
trị σ nhu sau:
sij = e−

xi −xj 2
2σ 2

(2.4)


21
với σ là giá trị kiểm soát độ rộng khoảng cách của các điểm và xi − xj là độ đo
khoảng cách của 2 điểm xi and xj . Khi giá trị σ → ∞ thì trọng số tiến về giá trị 1.
Cortes và Mohri [17] đề xuất sử dụng nghịch đảo độ đo khoảng cách như sau:
sij =

1
,
xi − xj


xi = xj

(2.5)

Ngồi ra, độ tương đồng cịn được tính dưới dạng hàm cosine. Nó thường được sử
dụng để tính góc giữa hai vector với cơng thức như sau:
sij = |cos(xi , xj )| =

|xTi xj |
xi xj

(2.6)

Số độ của đỉnh đồ thị được xác định dựa trên tổng số các cạnh nối tới đỉnh này. Nó
được định nghĩa bởi ma trận đường chéo D = (di )i=1...N , được tính như sau:
N

di =

sij

(2.7)

j=1

Độ đo di của một đỉnh i có thể xem như là độ đo mật độ cục bộ tại điểm dữ liệu xi .
Ma trận Laplacian L của X được xác định bởi:
L=D−S

(2.8)


Một trong những bất cập của các phương pháp trên là nó phụ thuộc vào giá trị các
tham số khác nhau như , k, σ hoặc độ đo khoảng cách. Nếu không xác định được giá trị
tối ưu, ma trận độ tương đồng sẽ không phản ánh thực tế độ tương đồng giữa các điểm dữ
liệu. Gần đây, để giải quyết vấn đề ràng buộc tham số, một số phương pháp đã được đề
xuất với mơ hình phi tham số, tiêu biểu trong đó là phương pháp biểu diễn thưa, nhằm
xây dựng độ tương đồng hồn tồn dựa trên giá trị dữ liệu và khơng phụ thuộc vào các
tham số. Phần tiếp theo sẽ trình bày về phương pháp biểu diễn thưa.

2.2.2

Xây dựng đồ thị dựa trên phương pháp biểu diễn thưa

Phương pháp biểu diễn thưa nhận được nhiều sự quan tâm trong lĩnh vực thị giác
máy tính trong vài năm gần đây. Nó chứng tỏ sự hiệu quả cho nhiều ứng dụng như nén
ảnh và mả hóa [71, 82], xử lý ảnh và tín hiệu [12]. Một cách tổng quát, phương pháp
biểu diễn thưa cho phép tìm ra cấu trúc biểu diễn compact nhất cho dữ liệu gốc. Qiao và
cộng sự đã đề xuất đầu tiên [66] kỹ thuật xây dựng độ tương đồng dựa trên phương pháp
biểu diễn thưa. Bằng việc chuẩn hóa tối tiểu dựa trên chuẩn l1 , một đồ thị tương ứng với
trọng số các cạnh sẽ được sinh ra. Đây là một cách làm hồn tồn mới vì nó không dựa
vào các tham số (độ đo khoảng cách Eulice hay Cosine) mà hoàn toàn dựa vào giá trị tự
thân của dữ liệu. Kỹ thuật này đã được đánh giá về mặt thực nghiệm là khá thành công
cho việc biểu diễn độ tương đồng của các điểm dữ liệu [81]
Cho ma trận X = [x1 , ..., xi , .., xN ]T ∈ RD×N với các điểm dữ liệu biểu diễn dưới dạng
cột, ta muốn xây dựng mỗi điểm dữ liệu xi , (ví dụ mỗi điểm dữ liệu là một ảnh màu được
biểu diễn trong miền không gian đặc trưng), và sử dụng ít X nhất có thể. Vấn đề này có
thể biểu diễn về mặt tốn học như sau:


22


min si
si

0

s.t. xi = Xsi ,

(2.9)

với si = [si1 , ..., si(i−1) , 0, si(i+1) , ..., siN ]T là một vector hệ số có kích thước N và phần
tử thứ ith tương ứng giá trị 0 (xác định bởi một xi bị loại bỏ từ X) và phần tử sij (i = j)
ký hiệu sự đóng góp trong việc tạo nên độ tương đồng bởi xj và xi , . 0 ký hiệu cho chuẩn
l0 , bằng với số lượng thành phần khác không trong si .
Nhắc lại rằng, giải pháp cho công thức 2.9 là NP-hard trong trường hợp tổng quát.
Một vector thưa si có thể được xấp xỉ bởi phương pháp cực tiểu hóa bằng chuẩn l1 :
min si
si

1

s.t. xi = Xsi , 1 = 1T si ,

(2.10)

với, . 1 ký hiệu cho chuẩn l1 , ; 1 ∈ RN là vector chỉ toàn giá trị 1.
Trong thực tế, ràng buộc xi = Xsi trong công thức 2.10 khơng ln ln đảm bảo
vì có sự hiện diện của phần thông tin bị nhiễu. Hàm mục tiêu được định nghĩa lại như
sau [78]:
min si

si

1

s.t.

xi − Xsi

2

< ξ, 1 = 1T si ,

(2.11)

với ξ đại diện cho ngưỡng chấp nhận. Một vector thưa si sẽ được tính từ mỗi mẫu xi .
Giá trị tối ưu của công thức 2.11 cho mỗi mẫu xi là một vector thưa ˆsi . Kết quả này cho
phép chúng ta xây dựng một ma trận độ tương đồng S = (ˆ
si,j )N ×N xác định bởi:
S = [ˆs1 , ..., ˆsi , ..., ˆsN ]T

(2.12)

Vấn đề cực tiểu hóa bằng chuẩn l1 có thể được giải quyết bằng các phương pháp đại
số tuyến tính. Do vector ˆsi thưa nên nhiều thành phần của vector này mang giá trị 0.
Điều đó có nghĩa là điểm dữ liệu ở xa tín hiệu đầu vào sẽ có hệ số bằng 0 hoặc gia trị rất
nhỏ. Phương pháp này có thể phản ánh đúng bản chất đặc tính của giá trị dữ liệu ban
đầu. Trong trường hợp vắng mặt của nhãn dữ liệu, thơng tin phân biệt có thể thu được
một cách tự nhiên từ ma trận S.

2.3


Lựa chọn đặc trưng LBP

Lựa chon và rút gọn đặc trưng LBP được phân thành 2 nhóm chính: (1) nhóm rút
gọn dựa trên độ dài các mẫu nhị phân (binary patter) được định nghĩa trước bởi một số
quy tắc nào đó như LBP uniform, (2) nhòm sử dụng cá phương pháp lựa chọn đặc trưng
sau khi trích xuất đầy đủ các mẫu nhị phân. Trong đó hóm thứ hai vì đây là kỹ thuật
cho ra độ chính xác tốt hơn, tuy nhiên lại địi hỏi một q trình huấn luyện offline.
Trong số các phương pháp rút gọn và lựa chọn đặc trưng LBP, đề tài quan tâm đến
nhóm các phương pháp rút gọn tồn bộ histogram (thay vì lựa chọn một số đặc trưng)
được đề xuất lần đầu tiên bởi Porebski và cộng sự [64]. Phương pháp này đánh giá các
histogram LBP của ảnh màu bằng các hệ số bởi kỹ thuật lọc (filter), độ chính xác được
áp dụng để chọn số lượng histogram cần thiết để tạo tập con đặc trưng. Tiếp theo sau
đó Kalakech và cộng sự đề xuất cải tiến dựa trên hệ số Laplacian với tên gọi Adapt the
Supervised Laplacian (ASL) [36]. Phương pháp này dựa trên độ tương đồng giữa hai điểm
dữ liệu có cùng một nhãn (hay cùng một lớp) sẽ có giá trị là 1. Độ đo Jeffrey được dùng


23
để khoảng cách được dùng để đo khoảng cách giữa hai histogram được xác định như sau:
Q

DJef (Hri , Hrj )

Hir (k)log

=
k=1

Q


Hir (k)

Hjr (k)log

+

Hir (k)+Hjr (k)
2

k=1

Hjr (k)
Hir (k)+Hjr (k)
2

(2.13)

Giá trị hội tụ của Jeffrey giữa hai historgram là nhỏ tương ứng với hai ảnh là tương
đồng với nhau. Từ đó hệ số ASL được đề xuất như sau. Với mỗi histogram Hr ta sẽ có
được một hệ số:
r
SASL

=

N
i=1

N

j=1
N
i=1

DJef (Hri , Hrj )sij

DJef (Hri , Hr )di

(2.14)

với
• N là tổng số ảnh,
• sij là phần tử của ma trận tương đồng S. Trong ngữ cảnh học có giám sát, mỗi ảnh
Ii sẽ có tương ứng một nhãn yi . Độ tương đồng giữa hai ảnh Ii và Ij được xác định
bởi:
1 nếu yi = yj ,
sij =
(2.15)
0 ngược lại
• di là độ đo của ảnh Ii :
N

di =

sij ,

(2.16)

N
r

i=1 Hi di
N
i=1 di

(2.17)

j=1

• Hr là giá trị histogram bình qn:
r

H =

Sau khi các hệ số được tính cho từng histogram theo cơng thức 2.14, chúng sẽ được
sắp xếp theo chiều tăng dần để xác định những histogram có liên quan nhất.
Với bộ dưẽ liệu gồm N ảnh thuộc về C lớp. Ta có thể viết lại cơng thức 2.14 dưới
dạng biểu diễn như sau:
r
SASL

=

C
c=1
C
c=1

Nc
rc
rc c

i,j=1 DJef (Hi , Hj )sij
rc c
Nc
rc
i=1 DJef (Hi , H )di

(2.18)

với:
• Nc là số ảnh thuộc về lớp thứ cth ,
• Sc = scij là ma trận tương đồng trong lớp c, được định nghĩa bởi công thức 2.15.
Trong trường hợp này, Sc là ma trận 1 và ma trận đường chéo Dc = dcii = Ic là ma
trận đơn vị.
• Hrc la histogram bình qn của lớp c