MỤC LỤC

MỤC LỤC ...................................................................................................................1
LỜI CAM ĐOAN .......................................................................................................5
LỜI CÁM ƠN .............................................................................................................6
DANH MỤC CÁC KÍ HIỆU, CHỮ VIẾT TẮT .......................................................7
DANH MỤC CÁC BẢNG BIỂU ...............................................................................8
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ .....................................................................9

Chƣơng 1

TỔNG QUAN ......................................................................... 12

1.1

Giới thiệu.......................................................................................................12

1.2

Bài toán truy vấn ảnh ....................................................................................13

1.3

1.4

1.5

1.2.1

Bài toán truy vấn ảnh tổng quát ............................................................13

1.2.2

Bài toán truy vấn ảnh theo nội dung cho tra cứu sản phẩm ..................13

Một số phương pháp truy vấn ảnh chính ......................................................14
1.3.1

Truy vấn theo lời chú thích (annotation, key words) ............................14

1.3.2

Truy vấn ảnh theo đối tượng (OBIR) ....................................................15

1.3.3

Truy vấn ảnh dựa trên nội dung (CBIR) ...............................................15

Một số hệ thống truy vấn ảnh dựa trên nội dung ..........................................16
1.4.1

Hệ thống QBIC (Query By Image Content) .........................................16

1.4.2

Hệ thống VisualSeek và WebSeek........................................................16

1.4.3

Hệ thống PhotoBook .............................................................................17


1.4.4

Hệ thống RetrievalWare........................................................................17

Xác định phạm vi đề tài ................................................................................17

1


Chƣơng 2

CÁC PHƢƠNG PHÁP TRÍCH CHỌN ĐẶC TRƢNG VÀ

ĐÁNH GIÁ ĐỘ ĐO TƢƠNG ĐỒNG ......................................................... 18
2.1

Một số phương pháp trích chọn đặc trưng ảnh .............................................18
2.1.1

2.1.1.1

Lược đồ Histogram .......................................................................18

2.1.1.2

Vectơ liên kết màu ........................................................................19

2.1.2

Ma trận đồng hiện .........................................................................19


2.1.2.2

Phép biến đổi Wavelet ..................................................................20

2.1.2.3

Các đặc trưng lọc Gabor ...............................................................20

2.1.2.4

Mẫu nhị phân cục bộ .....................................................................20

Trích chọn đặc trưng ảnh dựa trên hình dạng .......................................21

2.1.3.1

Trích chọn đặc trưng theo lược đồ cạnh .......................................21

2.1.3.2

Trích chọn đặc trưng theo vùng ....................................................21

2.1.4

2.3

Trích chọn đặc trưng ảnh dựa trên kết cấu ............................................19

2.1.2.1


2.1.3

2.2

Trích chọn đặc trưng ảnh dựa trên màu sắc ..........................................18

Trích chọn đặc trưng sử dụng điểm đặc trưng (keypoints) ...................22

2.1.4.1

Đặc trưng cục bộ bất biến SIFT ....................................................22

2.1.4.2

Đặc trưng SURF ............................................................................23

Một số phương pháp đánh giá độ đo tương đồng .........................................24
2.2.1

Khoảng cách Euclide ............................................................................24

2.2.2

Khoảng cách Manhattan........................................................................24

2.2.3

Khoảng cách góc ...................................................................................25


2.2.4

Độ đo Cosin...........................................................................................25

Hướng tiếp cận đề xuất trong luận văn .........................................................25

Chƣơng 3

TRÍCH CHỌN ĐẶC TRƢNG CỦA ẢNH CHO VIỆC TÌM

KIẾM ẢNH SẢN PHẨM.............................................................................. 28
2


3.1

Bài toán .........................................................................................................28

3.2

Phương pháp đề xuất .....................................................................................28
3.2.1

3.3

3.4

Trích chọn đặc trưng SURF (Speeded-up Robust Features) ................30

3.2.1.1


Ảnh tích phân ................................................................................31

3.2.1.2

Phát hiện Fast-Hessian ..................................................................31

3.2.1.3

Mô tả đặc trưng SURF ..................................................................36

3.2.1.4

So khớp đặc trưng .........................................................................39

3.2.2

Trích chọn đặc trưng LBP (Local Binary Pattern) ................................39

3.2.3

Kết hợp đặc trưng SURF và đặc trưng LBP .........................................42

Kiểm chứng phương pháp đề xuất ................................................................43
3.3.1

Cơ sở dữ liệu thực nghiệm ....................................................................43

3.3.2


Kết quả ..................................................................................................43

Kết luận .........................................................................................................45

Chƣơng 4

TRUY VẤN ẢNH DÙNG MÔ HÌNH K-LÁNG GIỀNG

GẦN NHẤT SỬ DỤNG BỘ LƢỢNG TỬ HÓA ........................................ 47
4.1

Bài toán .........................................................................................................47

4.2

Mô hình tìm kiếm K-Láng giềng gần nhất sử dụng bộ lượng tử hóa ...........48

4.3

4.2.1

Lượng tử hóa vectơ ...............................................................................48

4.2.2

Tìm kiếm sử dụng lượng tử hóa ............................................................49

Mô hình truy vấn ảnh đề xuất .......................................................................49

Chƣơng 5

5.1

5.2

KẾT QUẢ THỰC NGHIỆM ................................................. 52

Thực nghiệm .................................................................................................52
5.1.1

Cơ sở dữ liệu ảnh ..................................................................................52

5.1.2

Quá trình thực nghiệm ..........................................................................52

Kết quả và đánh giá .......................................................................................53
3


5.3

Nhận xét ........................................................................................................59

5.4

Một số kết quả tiêu biểu ................................................................................60

Chƣơng 6

KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ............................ 67


6.1

Kết luận .........................................................................................................67

6.2

Hướng phát triển ...........................................................................................68

DANH MỤC CÁC CÔNG TRÌNH LIÊN QUAN....................................................69
TÀI LIỆU THAM KHẢO .........................................................................................70
PHỤ LỤC ..................................................................................................................74
Phụ lục 1: Tập cơ sở dữ liệu CalTech256 ..............................................................74
Phụ lục 2: Danh mục công trình liên quan .............................................................75

4


LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của bản thân. Các số liệu, kết
quả trình bày trong luận văn là trung thực. Các tư liệu được sử dụng trong luận văn
có nguồn gốc và trích dẫn rõ ràng, đầy đủ.

Phan Thị Trinh

5


LỜI CÁM ƠN
Đầu tiên, tôi xin chân thành cám ơn sâu sắc đến PGS.TS. Lê Hoàng Thái,

người đã trực tiếp hướng dẫn, tận tình chỉ bảo, giúp đỡ tôi hoàn thành luận văn.
Tôi xin trân trọng cám ơn các thầy- cô Trường Đại học Công nghệ Thông tin
đã truyền đạt những kiến thức, kinh nghiệm học tập quý báu và phong phú cho tôi
trong suốt quá trình học.
Xin cám ơn các thầy cô, các anh chị và các bạn đồng nghiệp trong Khoa Công
nghệ thông tin, trường Cao đẳng Công nghệ Thủ Đức đã giúp đỡ, tạo điều kiện tốt
nhất để tôi có thể hoàn thành luận văn.
Luận văn này như món quà tri ân đến tất cả.
Chân thành cám ơn!
TP. Hồ Chí Minh, tháng 10 năm 2015

Phan Thị Trinh

6


DANH MỤC CÁC KÍ HIỆU, CHỮ VIẾT TẮT
Content-Based Image Retrieval (CBIR): Hệ thống truy vấn ảnh dựa trên nội
dung.
K-Nearest Neighbor (K-NN): K - Láng giềng gần nhất.
Local Binary Pattern (LBP): Mẫu nhị phân cục bộ.
Object Based Image Retrieval (OBIR): Hệ thống truy vấn ảnh dựa vào đối
tượng.
Scale-Invariant Feature Transform (SIFT): Đặc trưng SIFT.
Speeded-up Robust Features (SURF): Đặc trưng SURF.

7


DANH MỤC CÁC BẢNG BIỂU

Bảng 3.1. So sánh độ chính xác trung bình giữa các phương pháp trích chọn đặc
trưng ..........................................................................................................................43
Bảng 3.2. So sánh thời gian thực hiện giữa các phương pháp trích chọn đặc trưng 44
Bảng 5.1. Kết quả thực nghiệm truy vấn với từng loại sản phẩm............................55
Bảng 5.2. Kết quả thực nghiệm 10 truy vấn ngẫu nhiên ..........................................57
Bảng 5.3. Bảng so sánh giữa các phương pháp truy vấn ảnh ..................................58

8


DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 1.1. Ví dụ về một mô hình truy vấn ảnh đơn giản ..........................................13
Hình 1.2. Minh họa hệ thống tra cứu sản phẩm sử dụng truy vấn ảnh dựa trên nội
dung ...........................................................................................................................14
Hình 1.3. Cấu trúc cơ bản của hệ thống truy vấn ảnh dựa trên nội dung..................16
Hình 2.1. Mô hình truy vấn ảnh đề xuất ..................................................................27
Hình 3.1. Tính tổng cường độ pixel vùng ABCD sử dụng ảnh tích phân ...............31
Hình 3.2. Xấp xỉ đạo hàm bậc 2 của hàm Gaussian bằng hộp lọc theo các hướng x,
y và xy [2] .................................................................................................................32
Hình 3.3. Thay vì lặp đi lặp lại việc giảm kích thước ảnh (hình trái), việc sử dụng
ảnh tích phân cho phép tăng tỉ lệ của bộ lọc với chi phí không đổi (ảnh phải) [2]...33
Hình 3.4. Hộp lọc Dyy (hình trên) và hộp lọc Dxy (hình dưới) với hai kích thước
9x9 và 15x15 [2] .......................................................................................................34
Hình 3.5. Các điểm cực đại và cực tiểu được xác định bằng cách so sánh mỗi điểm
ảnh với 26 láng giềng của nó [2] ................................................................................35
Hình 3.6. Lọc Haar Wavelet để tính sự ảnh hưởng trên hai hướng x và y. Vùng tối
có trọng số là -1, vùng sáng là +1 [2].......................................................................36
Hình 3.7. Vùng hình tròn xung quanh và hướng đại diện cho điểm đặc trưng [2] ..37
Hình 3.8. 4x4 hình vuông con xung quanh điểm đặc trưng [2] ...............................38
Hình 3.9. Hình minh họa trích chọn đặc trưng SURF. Ảnh trái là ảnh đầu vào. Ảnh

bên phải là ảnh sau khi đã trích chọn các điểm đặc trưng. .......................................38
Hình 3.10. Ví dụ sự tính toán LBP [16] ....................................................................39
Hình 3.11. Minh họa toán tử LBP mở rộng với các giá trị P và R khác nhau. Giá trị
các pixel được nội suy cho các điểm không nằm trong tâm của một pixel [17] ........40
Hình 3.12. Từ trái sang phải, các mẫu vân cơ bản: điểm chấm, điểm chấm nhạt,
điểm cuối đường thẳng, biên cạnh, góc được phát hiện bởi LBPu [17] ....................41

9


Hình 3.13. Từ trái sang phải, từ trên xuống dưới: ảnh gốc, ảnh xám, ảnh LBP cơ
bản, ảnh LBP đồng nhất ............................................................................................41
Hình 3.14. Minh họa quá trình rút trích đặc trưng SURT_LBP của ảnh ..................42
Hình 3.15. Đồ thị so sánh độ chính xác trung bình giữa các phương pháp rút trích
đặc trưng ....................................................................................................................44
Hình 3.16. Đồ thị so sánh thời gian thực hiện trung bình giữa các phương pháp rút
trích đặc trưng ...........................................................................................................45
Hình 3.17. Sơ đồ minh họa phương pháp trích chọn đặc trưng SURF_LBP ...........46
Hình 4.1. Mô hình truy vấn ảnh đề xuất ...................................................................50
Hình 5.1. Hình minh họa ảnh trong tập cơ sở dữ liệu và ảnh truy vấn ....................52
Hình 5.2. Kết quả truy vấn từng loại sản phẩm trên Top-5, Top-10, Top-15 ..........56
Hình 5.3. Kết quả truy vấn ngẫu nhiên trên Top-5, Top-10, Top-15.......................58
Hình 5.4.

Kết quả so sánh giữa các phương pháp truy vấn ảnh trong tập

CalTech256 ...............................................................................................................59
Hình 5.5. Kết quả truy vấn cái ca trên Top-15 với phương pháp sử dụng đặc trưng
kết hợp SURF_LBP ..................................................................................................60
Hình 5.6. Kết quả truy vấn đồng hồ trên Top-15 với phương pháp sử dụng đặc

trưng kết hợp SURF_LBP .........................................................................................61
Hình 5.7. Kết quả truy vấn gấu bông trên Top-15 với phương pháp sử dụng đặc
trưng kết hợp SURF_LBP .........................................................................................62
Hình 5.8. Kết quả truy vấn áo thun trên Top-15 với phương pháp sử dụng đặc trưng
kết hợp SURF_LBP ..................................................................................................63
Hình 5.9. Kết quả truy vấn ba lô trên Top-15 với phương pháp sử dụng đặc trưng
kết hợp SURF_LBP ..................................................................................................64
Hình 5.10. Kết quả truy vấn giày trên Top-10 với phương pháp sử dụng đặc trưng
kết hợp SURF_LBP ..................................................................................................65

10


Hình 5.11. Kết quả truy vấn máy DVD trên Top-10 với phương pháp sử dụng đặc
trưng kết hợp SURF_LBP .........................................................................................66

11


Chương 1 – Tổng quan

Chƣơng 1
TỔNG QUAN
1.1 Giới thiệu
Thị giác máy tính là lĩnh vực nghiên cứu đang phát triển không ngừng bởi tính
trực quan sinh động cũng như khả năng áp dụng vào thực tế lớn. Hiện thị giác máy
tính đang giành được nhiều sự quan tâm của các nhà nghiên cứu trong và ngoài
nước. Trong thị giác máy tính, truy vấn ảnh có thể nói là lĩnh vực đòi hỏi sự nghiên
cứu tổng hợp: nghiên cứu xử lý ảnh để rút trích các đặc trưng, áp dụng các tính toán
toán học cao cấp để xác định mức độ tương đồng giữa hai ảnh và sự tổ chức sắp xếp

chỉ mục cho cơ sở dữ liệu ảnh.
Cùng với sự bùng nổ thông tin trên web và sự phát triển của công nghệ kỹ
thuật số, lượng ảnh lưu trữ trên Web, và thư viện số cũng tăng một cách nhanh
chóng. Vì vậy, việc xây dựng các hệ thống tra cứu và xếp hạng ảnh là rất cần thiết
và thực tế đã có nhiều công cụ tra cứu ảnh thương mại xuất hiện. Các công cụ tra
cứu ảnh thường dựa vào hai đặc trưng chính là văn bản đi kèm ảnh hoặc nội dung
ảnh. Một số công cụ tìm kiếm ảnh theo văn bản đi kèm như Google Image Search,
Yahoo!, MSN,…Một số công cụ tìm kiếm ảnh dựa vào nội dung ảnh như Google
Image Swirl, Bing, Tiltomo, Tineye,…Tuy nhiên, việc tra cứu chỉ dựa vào văn bản
đi kèm còn có nhiều nhập nhằng giữa nội dung hiển thị ảnh và nội dung văn bản đi
kèm ảnh trong quá trình tìm kiếm. Ví dụ, với truy vấn “Apple”, máy tra cứu khó
phân biệt được người dùng muốn tìm hình ảnh quả táo hay logo của hãng Apple.
Những công cụ tra cứu ảnh theo nội dung của các bức ảnh ra đời tỏ ra ưu thế vì hạn
chế được những nhập nhằng trên. Một số lượng lớn các ảnh đang được sử dụng ở
trong thư viện ảnh số và trên web. Vì vậy nhu cầu tìm kiếm ảnh là một nhu cầu tất
yếu. Hiện tại, truy vấn ảnh ứng dụng trong khá nhiều lĩnh vực như: quản lý nhãn
hiệu logo, truy tìm tội phạm, ứng dụng trong y khoa, quân sự….Có hai dạng cơ sở
dữ liệu (CSDL) ảnh là: cơ sở dữ liệu ảnh tĩnh và cơ sở dữ liệu ảnh động (ảnh
video…). Trong nghiên cứu này chỉ xin xem xét đến phạm vi ảnh tĩnh.

12


Chương 1 – Tổng quan

1.2 Bài toán truy vấn ảnh
1.2.1 Bài toán truy vấn ảnh tổng quát
Bài toán truy vấn ảnh yêu cầu như sau:
Nhập (Input): Yêu cầu truy vấn ảnh (từ khóa, bức ảnh, …).
Xuất (Output): Các ảnh kết quả thỏa yêu cầu tìm được từ CSDL ảnh

Hệ thống
Yêu cầu truy Nhập vào
vấn ảnh
truy vấn ảnh

Xuất ra

Tập ảnh kết
quả

CSDL
ảnh

Hình 1.1. Ví dụ về một mô hình truy vấn ảnh đơn giản

1.2.2 Bài toán truy vấn ảnh theo nội dung cho tra cứu sản phẩm
Bài toán truy vấn ảnh cho tra cứu sản phẩm yêu cầu như sau:
 Nhập (Input): Ảnh truy vấn (Query Image), cụ thể là ảnh một sản phẩm
 Xuất (Output): Kết quả là các ảnh cùng loại ảnh cần truy vấn

13


Chương 1 – Tổng quan

Nhập vào

Hệ thống tra cứu sản

Xuất ra


Kết quả

phẩm sử dụng truy vấn
ảnh dựa trên nội dung

CSDL ảnh sản phẩm

Hình 1.2. Minh họa hệ thống tra cứu sản phẩm sử dụng truy vấn ảnh dựa trên
nội dung

1.3

Một số phƣơng pháp truy vấn ảnh chính

1.3.1 Truy vấn theo lời chú thích (annotation, key words)
Các từ khóa hay các lời chú thích được đưa vào để mô tả thông tin trong ảnh
và cũng được dùng làm chỉ mục. Việc truy vấn ảnh đơn giản chỉ là sự so khớp các
từ khóa đó. Cách làm này chỉ thích hợp khi các ảnh trong cơ sở dữ liệu ảnh có nội
dung không quá phức tạp. Tuy nhiên, hạn chế của cách làm này là khi cơ sở dữ liệu
ảnh lớn thì việc bổ sung từ khóa hay lời chú thích sẽ tốn nhiều chi phí tính toán và
khá khó khăn. Hơn nữa, có vấn đề sẽ không thể miêu tả bằng lời chú thích mà phải
thể hiện bằng thị giác của ảnh. Ngoài ra, các hệ thống truy vấn ảnh dựa trên từ khóa
hay lời chú thích sẽ có sự không đồng nhất do những người sử dụng khác nhau sẽ
cho ra các từ khóa khác nhau.

14


Chương 1 – Tổng quan


1.3.2 Truy vấn ảnh theo đối tƣợng (OBIR)
Hệ thống truy vấn ảnh dựa vào đối tượng Object Based Image Retrieval
(OBIR) đang được nghiên cứu. Rõ ràng truy vấn theo đối tượng sẽ rất gần với nhu
cầu thường thấy của người sử dụng và giống theo nhận thức của con người. Ví dụ
tìm tất cả các vị trí đỗ xe (có biểu tượng Parking)… Tuy vậy chi phí cho việc dò tìm
ra đối tượng là không nhỏ và khả năng trích ra chính xác đối tượng trong ảnh cũng
không dễ bởi lẽ định nghĩa thế nào là đối tượng trong ảnh cho đúng với ý nghĩa của
đối tượng trong thực tế. Vì thế chỉ riêng việc nhận diện ra đối tượng hay nhận dạng
mặt người cũng là một đề tài nghiên cứu. Đối với phương pháp này thì yếu tố quyết
định là làm sao rút trích ra chính xác cùng một đối tượng trong các ảnh khác nhau
(các hoàn cảnh xuất hiện khác nhau của cùng một đối tượng).

1.3.3 Truy vấn ảnh dựa trên nội dung (CBIR)
Hệ thống truy vấn ảnh dựa trên nội dung (Content-Based Image Retrieval viết
tắt là CBIR) là hệ thống truy vấn ảnh dựa trên việc tự động rút trích một số thông
tin đặc trưng trong ảnh như: màu sắc, kết cấu, vị trí, hình dạng. Các yếu tố trực quan
như màu sắc, kết cấu, hình dạng và bố cục không gian trực tiếp liên quan đến khía
cạnh của cảm nhận nội dung ảnh, cùng với các khái niệm ở mức cao như ý nghĩa
đối tượng, khung cảnh trong ảnh, được dùng như là manh mối cho tra cứu hình ảnh
với nội dung tương tự từ cơ sở dữ liệu. Phương pháp này đã được nhiều người
nghiên cứu với rất nhiều cách tiếp cận khác nhau; do đó rất nhiều hệ thống truy vấn
ảnh dựa trên nội dung đã ra đời như: QBIC, VisualSeek, WebSeek và PhotoBook...
Phương pháp tổng quát để truy vấn ảnh dựa trên nội dung thông thường gồm 2
bước xử lý: trích chọn đặc trưng ảnh và truy vấn ảnh dựa vào độ đo tương đồng
giữa ảnh cần truy vấn và các ảnh trong tập cơ sở dữ liệu.

15



Chương 1 – Tổng quan

Tính độ đo
Ảnh
truy
vấn

sự tương
Trích chọn

đồng giữa

đặc trưng

ảnh truy vấn

ảnh

và tập ảnh
CSDL

Tập
ảnh
kết
quả

Hình 1.3. Cấu trúc cơ bản của hệ thống truy vấn ảnh dựa trên nội dung

1.4 Một số hệ thống truy vấn ảnh dựa trên nội dung
1.4.1 Hệ thống QBIC (Query By Image Content)

Hệ thống QBIC của hãng IBM là một hệ thống tra cứu ảnh thương mại đầu
tiên và nổi tiếng nhất trong số các hệ thống tra cứu ảnh dựa trên nội dung. Nó cho
phép người sử dụng tra cứu ảnh dựa vào màu sắc, hình dạng và kết cấu. QBIC cung
cấp một số phương pháp: Simple, Multi-feature, và Multi-pass. Trong phương pháp
truy vấn Simple chỉ sử dụng một đặc điểm. Truy vấn Multi-feature bao gồm nhiều
hơn một đặc điểm và mọi đặc điểm đều có trọng số như nhau trong suốt quá trình
tìm kiếm. Truy vấn Multi-pass sử dụng đầu ra của các truy vấn trước làm cơ sở cho
bước tiếp theo. Người sử dụng có thể vẽ ra và chỉ định màu, kết cấu mẫu của hình
ảnh yêu cầu. Trong hệ thống QBIC màu tương tự được tính toán bằng thước đo bình
phương sử dụng biểu đồ màu k phần tử (k-element) và màu trung bình được sử
dụng như là bộ lọc để cải tiến hiệu quả của truy vấn.

1.4.2 Hệ thống VisualSeek và WebSeek
Cả hai hệ thống này đều được phát triển tại trường Đại học Colombia.
VisualSEEK là hệ thống cơ sở dữ liệu ảnh. Nó cho phép người sử dụng tra cứu ảnh
dựa trên màu sắc, không gian miền và đặc điểm kết cấu. Tập màu và chuyển đổi
wavelet dựa trên kết cấu được sử dụng để thực hiện những đặc điểm này. Thêm vào
đó VisualSEEK còn cho phép người sử dụng tạo truy vấn bằng việc chỉ định vùng
màu và những không gian vị trí của chúng. WebSEEK là một catalog ảnh và là công

16


Chương 1 – Tổng quan

cụ tìm kiếm cho web. Hệ thống này cung cấp mẫu cho danh sách ảnh và video trên
trang web sử dụng kết hợp xử lý dựa trên text và phân tích dựa trên nội dung.

1.4.3 Hệ thống PhotoBook
Hệ thống này được phát triển ở Massachusetts Institute of Technology cho

phép người sử dụng tra cứu ảnh dựa trên màu sắc, hình dạng và kết cấu. Hệ thống
này cung cấp một tập các thuật toán đối sánh gồm: Euclidean, mahalanobis, vector
space angle, histogram, Fourier peak, và wavelet tree distance như là những đơn vị
đo khoảng cách. Trong hầu hết các phiên bản đã có thể định nghĩa những thuật toán
đối sánh của họ. Hệ thống như là một công cụ bán tự động và có thể sinh ra một
mẫu truy vấn dựa vào những ảnh mẫu được cung cấp bởi người sử dụng. Điều này
cho phép người sử dụng trực tiếp đưa những yêu cầu truy vấn của họ với những lĩnh
vực khác nhau, và mỗi lĩnh vực họ có thể thu được những mẫu truy vấn tối ưu.

1.4.4 Hệ thống RetrievalWare
Hệ thống này được phát triển bởi tập đoàn công nghệ Excalibur cho phép
người sử dụng tra cứu ảnh bởi nội dung màu, hình dạng, kết cấu, độ sáng, kết cấu
màu và hệ số co dãn. Người sử dụng có thể điều chỉnh tỉ trọng của những đặc điểm
này trong suốt quá trình tìm kiếm.

1.5 Xác định phạm vi đề tài
Luận văn này tập trung nghiên cứu và đề xuất một phương pháp hiệu quả cho
việc tra cứu ảnh sản phẩm. Luận văn sẽ giới hạn phạm vi của bài toán như sau:
-

Tập dữ liệu là tập ảnh tĩnh.

-

Ảnh được chụp trong điều kiện ánh sáng bình thường.

17


Chương 2 – Các phương pháp trích chọn đặc trưng và đánh giá độ đo tương đồng


Chƣơng 2
CÁC PHƢƠNG PHÁP TRÍCH CHỌN ĐẶC TRƢNG VÀ ĐÁNH GIÁ
ĐỘ ĐO TƢƠNG ĐỒNG
2.1 Một số phƣơng pháp trích chọn đặc trƣng ảnh
2.1.1 Trích chọn đặc trƣng ảnh dựa trên màu sắc
2.1.1.1 Lƣợc đồ Histogram
Lược đồ Histogram [4, 7, 25, 34] là đại lượng đặc trưng cho phân bố màu của
ảnh. Độ đo tính tương đồng về màu sắc được tính bằng phần giao của hai lược đồ
màu ảnh truy vấn H(IQ) và ảnh trong cơ sở dữ liệu ảnh H(ID). Kết quả sẽ là một lược
đồ màu thể hiện độ giống nhau giữa hai ảnh trên. Một số công trình tiêu biểu:
-

Hussain và các đồng sự [7] đã thực hiện việc chia ảnh truy vấn thành hai
khối, tương tự mỗi hình ảnh trong cơ sở dữ liệu ảnh cũng được chia làm
hai khối và lược đồ histogram cũng được tính riêng biệt cho các khối này.
Sau đó đánh giá độ tương đồng giữa lược đồ histogram của các khối của
ảnh truy vấn và lược đồ histogram của các khối của từng ảnh trong tập cơ
sở dữ liệu ảnh và sắp thứ tự các lược đồ này theo độ tương đồng nhất. Kết
quả cuối cùng là được hiển thị từ thứ tự sắp xếp này.

-

Lining Zhang và các đồng sự [34] sử dụng lược đồ histogram để biểu diễn
thông tin màu. Họ đã tìm lược đồ histogram trong không gian HSV. Màu
sắc (hue) và độ bão hòa (saturation) được lượng tử hóa thành dãy nhị phân
8 bit và giá trị (value) thành 4 bit.

Tuy nhiên vì lược đồ màu chỉ thể hiện tính phân bố màu toàn cục của ảnh mà
không xét đến tính phân bố cục bộ của điểm ảnh nên có thể có hai ảnh trông rất

khác nhau nhưng lại có cùng lược đồ màu.

18


Chương 2 – Các phương pháp trích chọn đặc trưng và đánh giá độ đo tương đồng

2.1.1.2 Vectơ liên kết màu
Vectơ liên kết màu (Color Coherence Vector) [23] là lược đồ tinh chế lược đồ
màu, chia mỗi ô màu (bin) thành hai nhóm

điểm ảnh: nhóm liên kết màu

(coherence pixels) và nhóm không liên kết màu (noncoherence pixels).
Vectơ liên kết màu còn giúp giải quyết khuyết điểm về tính không duy nhất
của lược đồ màu đối với ảnh. Hai ảnh có thể có chung lược đồ màu nhưng khác
nhau hoàn toàn, đây là khuyết điểm của lược đồ màu. Nhưng với tìm kiếm theo đặc
trưng vectơ liên kết màu thì nó sẽ giải quyết được khuyết điểm không duy nhất này.
Tiêu biểu là công trình của Reza Ravani và các đồng sự [23] : nhóm tác giả đã
phân tích hiệu suất của phương pháp vectơ liên kết màu trong các giai đoạn khác
nhau như: xác định không gian màu, giá trị ngưỡng và kích thước của vectơ liên kết
màu. Sau khi nghiên cứu các thông số, nhóm đã tối ưu hóa thuật toán và phân đoạn
phù hợp để tăng hiệu suất lên 30% so với phương pháp sử dụng vectơ liên kết màu
thông thường.
Nhìn chung các đặc trưng màu có tính toán hiệu quả cao và bất biến với các
phép quay (rotation) và phép co dãn (scale). Tuy nhiên, các đặc trưng này lại không
xem xét đến các nội dung của ảnh và phân bố không gian của màu sắc. Ngoài ra,
đặc trưng màu lại không hiệu quả đối với các ảnh nhiễu, mờ, và bị biến dạng do đó
hướng tiếp cận này không phù hợp với bài toán truy vấn ảnh áp dụng cho tra cứu
ảnh sản phẩm.


2.1.2 Trích chọn đặc trƣng ảnh dựa trên kết cấu
2.1.2.1 Ma trận đồng hiện
Ma trận đồng hiện (Co-occurence Matrix) [20, 33] là ma trận lưu trữ số lần
xuất hiện của những cặp điểm ảnh trên một vùng đang xét. Các cặp điểm này được
tính theo những quy luật cho trước. Ma trận đồng hiện cho ra các đặc trưng kết cấu:
độ nhiễu (entropy), năng lượng (energy), độ tương phản (contrast), độ đồng nhất

19


Chương 2 – Các phương pháp trích chọn đặc trưng và đánh giá độ đo tương đồng

(homogeneity). Tiêu biểu cho hướng tiếp cận này là nhóm tác giả WangXing-yuan
[33] và nhóm tác giả Felci Rajam [20].
Nhóm tác giả Felci Rajam [20] đã sử dụng ma trận đồng hiện mức xám để
trích chọn đặc trưng kết cấu, sau đó kết hợp phương pháp Quick SVM và cây nhị
phân quyết định để truy vấn ảnh.
Nhóm tác giả WangXing-yuan [33] đã sử dụng ma trận đồng hiện màu (Color
Co-occurence Matrix) để trích chọn đặc trưng kết cấu. Do các thông tin màu được
xem xét nên đặc trưng thu được không chỉ phản ánh mối tương quan kết cấu mà còn
đại diện cho các thông tin màu sắc, do đó phương pháp này vượt trội hơn so với
phương pháp sử dụng ma trận đồng hiện mức xám (Gray-level Co-occurence
Matrix) và phương pháp lược đồ histogram.
2.1.2.2 Phép biến đổi Wavelet
Vân thu được từ biến đổi Wavelet [10] được hầu hết các nghiên cứu công
nhận là đặc trưng về vân tốt cho việc phân đoạn ảnh. Tiêu biểu cho hướng tiếp cận
này gần đây là công trình của nhóm tác giả Yu-Gang Jiang [10] đã sử dụng phép
biến đổi Wavelet để truy vấn ảnh theo nội dung và ghi chú video.
2.1.2.3 Các đặc trƣng lọc Gabor

Lọc Gabor [21, 22, 24] được sử dụng rộng rãi để trích rút các đặc trưng ảnh,
đặc biệt là các đặc trưng kết cấu. Nó tối ưu về mặt cực tiểu hoá sự không chắc chắn
chung trong miền không gian và miền tần số, và thường được sử dụng như một
hướng và tỷ lệ biên điều hướng và phát hiện đường. Có nhiều cách tiếp cận đã được
đề xuất để mô tả các kết cấu của các ảnh dựa trên các lọc Gabor. Nhóm tác giả
Rahman [21, 22] đã đề xuất một cải tiến của lọc Gabor cho các ảnh bất biến với
phép xoay (rotation) và phép co dãn (scale).
2.1.2.4 Mẫu nhị phân cục bộ
LBP (Local Binary Patern - LBP) [16, 17, 30] là một toán tử kernel 3×3, nó
tổng quát hóa cấu trúc không gian cục bộ của một ảnh. Ojala và các đồng sự [16,
20


Chương 2 – Các phương pháp trích chọn đặc trưng và đánh giá độ đo tương đồng

17] đã chỉ ra rằng phương pháp LBP có khả năng phân tách cao cho sự phân lớp
vân. Bởi vì khả năng phân tách và chi phí tính toán thấp, LBP trở nên rất phổ biến
trong nhận dạng mẫu. LBP đã được áp dụng cho phát hiện khuôn mặt, nhận dạng
khuôn mặt, xác thực khuôn mặt, truy vấn ảnh. Toán tử LBP là bất biến với sự thay
đổi chiếu sáng và độ tương phản trong ảnh. Tiêu biểu cho hướng tiếp cận này là
nhóm tác giả Vatamanu O.A. [30]. Nhóm tác giả đã dựa trên LBP, lược đồ màu, và
vectơ liên kết màu để áp dụng truy vấn ảnh siêu âm.
Các đặc trưng kết cấu có thể mô tả các biến không gian trong cường độ điểm
ảnh và các đặc điểm bề mặt của đối tượng. Tuy nhiên việc phân đoạn kết cấu vẫn
còn là một vấn đề khó khăn để đáp ứng nhận thức của con người.

2.1.3 Trích chọn đặc trƣng ảnh dựa trên hình dạng
2.1.3.1 Trích chọn đặc trƣng theo lƣợc đồ cạnh
Các lược đồ cạnh [20, 28, 34] nắm bắt những thông tin hình dạng tổng quát
trong ảnh. Các thông tin cạnh trong hình có thể thu được dựa vào các thuật toán dò

tìm cạnh như Canny, Sobel, … Để có tính bất biến với phép co dãn, lược đồ phải
được chuẩn hóa tương ứng với số lượng điểm ảnh trong ảnh. Lược đồ phải được
làm mịn để giảm bị ảnh hưởng với phép quay. Tiêu biểu cho hướng tiếp cận này là
các nhóm tác giả Felci Rajam [20], nhóm tác giả Lining Zhang [34], nhóm tác giả
Ja-Hwung Su [28].
2.1.3.2 Trích chọn đặc trƣng theo vùng
Ảnh gồm tập hợp các vùng hay còn gọi là đoạn. Đây là đặc trưng đặc biệt của
ảnh. Với đặc trưng vùng sẽ giúp cho chúng ta có thể giải quyết được một vấn đề lớn
đang cản trở bước phát triển việc truy tìm ảnh dựa vào nội dung là dữ liệu nhập
được mô phỏng gần gũi hơn với suy nghĩ của con người và ảnh tìm được có thể
mang nội dung ngữ nghĩa rất khác so với ảnh truy vấn. Tiêu biểu cho hướng tiếp
cận này là các nhóm tác giả Ja-Hwung Su [28].

21


Chương 2 – Các phương pháp trích chọn đặc trưng và đánh giá độ đo tương đồng

Đặc trưng hình dạng là tương đối phù hợp với cảm giác trực quan nhưng thiếu
cơ sở toán học hoàn hảo cho các các đối tượng biến dạng. Do đó, hướng tiếp cận
này không phù hợp với bài toán truy vấn ảnh áp dụng cho tra cứu ảnh sản phẩm.

2.1.4 Trích chọn đặc trƣng sử dụng điểm đặc trƣng (keypoints)
Phương pháp này dựa trên các điểm đặc trưng, là các điểm bất biến với phép
xoay, phép co dãn, phép tịnh tiến, che lấp một phần… Có hai phương pháp tiêu
biểu nhất là SIFT và SURF.
2.1.4.1 Đặc trƣng cục bộ bất biến SIFT
SIFT là viết tắt của cụm từ Scale-Invariant Feature Transform [11, 12, 13, 14]
là một trong những thuật toán nổi tiếng nhất hiện nay dùng để phát hiện và mô tả
các đặc trưng của ảnh số. Thuật toán này được công bố bởi David Lowe [14].

Giống như nhiều thuật toán về xử lý ảnh, SIFT là thuật toán khá phức tạp, phải
trải qua nhiều bước xử lý và sử dụng nhiều kiến thức về toán học. Sau đây sẽ là các
bước chính trong thuật toán:
1. Dò tìm điểm cực trị trong không gian tỉ lệ
2. Lọc và trích xuất điểm đặc trưng
3. Gán hướng cho điểm đặc trưng
4. Mô tả điểm đặc trưng
Đặc trưng SIFT là bất biến với phép quay, phép tịnh tiến, phép co dãn và phép
biến dạng nhỏ. Các công trình gần đây cho hướng tiếp cận này:
-

Nhóm tác giả Bin Li [13]: ảnh truy vấn ban đầu được gọi là ảnh toàn cục
và được chia thành các ảnh con gọi là ảnh cục bộ. Truy vấn được dựa trên
đánh giá độ tương đồng giữa đặc trưng SIFT trên ảnh toàn cục và ảnh cục
bộ của ảnh truy vấn với đặc trưng SIFT trên ảnh toàn cục và ảnh cục bộ
của tập cơ sở dữ liệu ảnh.

22


Chương 2 – Các phương pháp trích chọn đặc trưng và đánh giá độ đo tương đồng

-

Nhóm tác giả Shraddha Kumar [12]: nhóm tác giả đã sử dụng RBF
(Radial Basis Function) để thực hiện việc truy vấn dựa trên đặc trưng
SIFT.

2.1.4.2 Đặc trƣng SURF
SURF (Speeded Up Robust Features) [1, 2, 31] được giới thiệu bởi nhóm tác

giả Herbert Bay [2]. Cách tiếp cận của phương pháp này tương đối giống với SIFT.
SURF cũng sử dụng không gian tỉ lệ để tìm điểm đặc trưng, các đặc trưng được mô
tả dưới dạng vectơ và có kèm thêm hướng. Hai phần chính trong thuật toán này là
“phát hiện” (detection) và “mô tả” (description).
Phát hiện: Việc phát hiện đặc trưng dựa trên không gian tỉ lệ và sử dụng ma
trận Hessian, tuy nhiên để đơn giản cho việc tính toán tác giả chỉ sử dụng một xấp
xỉ của ma trận này và tính toán trên ảnh tích phân (integral images) thay cho ảnh
ban đầu.
Mô tả: Việc mô tả đặc trưng sử dụng đặc trưng Haar Wavelet. Một lần nữa
ảnh tích phân lại được sử dụng để tăng tốc độ tính toán. Mỗi điểm đặc trưng sẽ được
thêm một hướng dùng để nhận dạng khi ảnh bị xoay. Mô tả điểm đặc trưng được thể
hiện dưới dạng vectơ gồm 64 thành phần.
Những công trình tiêu biểu gần đây là các công trình của các nhóm tác giả
K.Velmurugan [31], nhóm tác giả Abdelkhalak Bahri [1].
Phương pháp trích chọn đặc trưng theo điểm đặc trưng có ưu điểm là bất biến
với phép xoay, phép co dãn, phép tịnh tiến, che lấp một phần, … Vì vậy phương
pháp này khá phù hợp với bài toán truy vấn ảnh áp dụng cho việc tra cứu sản phẩm.
Phương pháp trích chọn đặc trưng SIFT xác định được nhiều điểm đặc trưng
hơn SURF, nhưng chi phí tính toán lại cao hơn. Phương pháp trích chọn đặc trưng
SURF dựa trên ý tưởng của SIFT nhưng thời gian tính toán tối ưu hơn đồng thời
vẫn đảm bảo trích chọn ra những điểm đặc trưng nổi bật nhất của đối tượng. Do đó,
trong luận văn sẽ tiến hành nghiên cứu và thực nghiệm phương pháp SURF. Tuy

23


Chương 2 – Các phương pháp trích chọn đặc trưng và đánh giá độ đo tương đồng

nhiên, phương pháp trích chọn đặc trưng theo điểm đặc trưng SURF có nhược điểm
là sẽ cho kết quả kém khi ảnh mờ hoặc ảnh bị nhiễu. Vì vậy, luận văn nghiên cứu

phương pháp kết hợp thêm với phương pháp trích chọn khác để khắc phục nhược
điểm này.

2.2 Một số phƣơng pháp đánh giá độ đo tƣơng đồng
Độ đo tương đồng [19, 29] dùng để so sánh sự tương đồng giữa hai ảnh. Có rất
nhiều phương pháp đánh giá độ đo tương đồng, tùy vào từng đặc trưng khác nhau sẽ
có những độ đo thích hợp. Sau đây là một số độ đo thường được sử dụng trong các
hệ thống truy vấn ảnh theo nội dung.

2.2.1 Khoảng cách Euclide
Khoảng cách Euclide [19, 29] được tính bởi công thức sau:
(

)

√∑

(2.1)

với x, y là hai vectơ đặc trưng
Khoảng cách Euclide thường được sử dụng làm độ đo tương đồng cho các đặc
trưng về màu sắc, đặc trưng kết cấu, đặc trưng cục bộ bất biến.

2.2.2 Khoảng cách Manhattan
Khoảng cách Manhattan [29] được tính bởi công thức sau:
(

)

∑


(2.2)

với x, y là hai vectơ đặc trưng
Khoảng cách Manhattan thường được sử dụng làm độ đo tương đồng cho các
đặc trưng về màu sắc, đặc trưng kết cấu, đặc trưng cục bộ bất biến.

24


Chương 2 – Các phương pháp trích chọn đặc trưng và đánh giá độ đo tương đồng

2.2.3 Khoảng cách góc
Khoảng cách góc [19] được tính bởi công thức sau:
(

)

(

)

(2.3)

với x, y là hai vectơ đặc trưng
Khoảng cách góc thường được sử dụng làm độ đo tương đồng cho đặc trưng
cục bộ bất biến.

2.2.4 Độ đo Cosin
Độ đo Cosin [19] được tính bởi công thức sau:

(

)

(2.4)

với x, y là hai vectơ đặc trưng
Độ đo Cosin thường được sử dụng làm độ đo tương đồng cho đặc trưng cục bộ
bất biến.

2.3 Hƣớng tiếp cận đề xuất trong luận văn
Mỗi hướng tiếp cận trình bày trong phần trên đều có những ưu điểm và
nhược điểm riêng. Trong đó, các nhược điểm dẫn đến kết quả truy vấn chưa tốt chủ
yếu do các yếu tố như phép xoay, phép co dãn, thay đổi cường độ sáng ánh sáng,
ảnh bị nhiễu, bị mờ .... Trong bài toán truy vấn ảnh cho việc tìm kiếm sản phẩm,
việc tìm phương pháp trích chọn các đặc trưng bất biến với phép xoay, phép co dãn,
ảnh hưởng của ánh sáng, độ tương phản hoặc ảnh bị mờ, bị nhiễu rất quan trọng.
Để giải quyết khó khăn nêu trên, luận văn này đề xuất phương pháp kết hợp
trích chọn đặc trưng sử dụng điểm đặc trưng (keypoints) SURF và đặc trưng LBP
để có thể trích chọn ra những đặc trưng bất biến với phép xoay, phép co dãn, phép
tịnh tiến, thay đổi cường độ chiếu ánh sáng và độ tương phản hoặc ảnh bị nhiễu, bị
mờ.

25