BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

HÌNH HỮU ĐỨC

NGHIÊN CỨU HỆ THỐNG
TRUY VẤN ẢNH TỰ NHIÊN

LUẬN VĂN THẠC SĨ
KỸ THUẬT TRUYỀN THÔNG

NGƢỜI HƢỚNG DẪN KHOA HỌC :
PGS .TS. NGUYỄN TIẾN DŨNG

HÀ NỘI, Năm 2014


MỤC LỤC
MỤC LỤC ................................................................................................................. 2
DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT ..................................................... 5
DANH MỤC CÁC BẢNG........................................................................................ 6
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ................................................................... 7
LỜI NĨI ĐẦU .......................................................................................................... 9
1

CHƢƠNG I – TỔNG QUAN VỀ TRUY VẤN ẢNH TỰ NHIÊN................ 11
1.1. Giới thiệu về xử lý ảnh .............................................................................. 11
1.2. Hệ thống xử lý ảnh .................................................................................... 12
1.2.1

Ảnh ..................................................................................................... 12

1.2.2

Mô tả hệ thống xử lý ảnh .................................................................... 13

1.3. Các vấn đề cơ bản trong xử lý ảnh số........................................................ 15
1.3.1

Biểu diễn ảnh ...................................................................................... 15

1.3.2

Tăng cƣờng ảnh - khôi phục ảnh ........................................................ 16

1.3.3

Biến đổi ảnh ........................................................................................ 17

1.3.4

Phân tích ảnh ...................................................................................... 18

1.4.

Giới thiệu về truy vấn ảnh tự nhiên .................................................... 18

1.5. Trích chọn đặc tính để truy vấn ảnh .......................................................... 20
1.6. Lập chỉ mục đặc tính (Feature Indexing) .................................................. 24
1.7. Truy vấn ảnh tƣơng tác .............................................................................. 25
2


CHƢƠNG II – CÁC ĐẶC TÍNH TRUY VẤN ẢNH TỰ NHIÊN ................ 28
2.1. Đặc tính màu .............................................................................................. 28
2.1.1

Khơng gian màu.................................................................................. 28

2.1.2

Lƣợng tử hóa màu............................................................................... 30

2.1.3

Mơ tả màu ........................................................................................... 32

2.2. Đặc tính bất biến ........................................................................................ 35

2


2.2.1

Đặc tính bất biến dùng tích phân ........................................................ 37

2.2.2

Các hàm kernel f(X) ........................................................................... 40

2.2.3


Lƣợc đồ đặc tính bất biến ................................................................... 42

2.2.4

Các vector đặc tính bất biến ............................................................... 44

2.2.5

Đặc tính Fourier Mellin bất biến ........................................................ 44

2.3. Co-occurence Matrix ................................................................................. 45
2.4. Đặc tính Gabor........................................................................................... 46
2.5. Đặc tính Tamura ........................................................................................ 48
2.6. Mơ tả cấu trúc tồn bộ ............................................................................... 51
2.7. Đặc tính cục bộ .......................................................................................... 52
2.8. Đặc tính dựa trên vùng (regioned based feature) ...................................... 54
2.9. Các đặc điểm biến đổi PCA....................................................................... 55
2.10. Tƣơng quan giữa các đặc tính khác nhau .................................................. 55
3

CHƢƠNG III- SO SÁNH ĐẶC TÍNH TRUY VẤN ẢNH ............................ 57
3.1. Phƣơng pháp so sánh lƣợc đồ .................................................................... 57
3.1.1

So sánh từng thành phần một (bin-by-bin) ......................................... 57

3.1.2

Phƣơng pháp so sánh chéo thành phần lƣợc đồ (Cross-bin


comparision) .................................................................................................... 61
3.2. So sánh ảnh ................................................................................................ 65
3.2.1

Khoảng cách Euclidean ...................................................................... 65

3.2.2

Khoảng cách tiếp tuyến ...................................................................... 66

3.2.3

Mô hình méo ảnh ................................................................................ 67

3.3. So sánh ảnh dựa trên đặc tính cục bộ ........................................................ 67
3.3.1

Chuyển trực tiếp (Direct Transfer) ..................................................... 67

3.3.2

Mơ hình méo ảnh đặc tính cục bộ (Local Feature Image Distortion

Model) 68

3


3.4. So sánh mô tả dựa trên vùng ..................................................................... 68
3.4.1


Integrated Region Matching (Sánh vùng kết hợp) ............................. 68

3.4.2

Quantized Hungarian Region Matching (Sánh vùng Hugarian lƣợng

tử)

69

3.5. Các đặc tính khác ....................................................................................... 71
4

CHƢƠNG IV- ĐÁNH GIÁ CHẤT LƢỢNG TRUY VẤN ẢNH.................. 72
4.1. Thông số đánh giá chất lƣợng truy vấn ảnh .............................................. 72
4.2. Đánh giá khả năng của các đặc tính và hàm khoảng cách ........................ 75

5

4.2.1

So sánh các hàm khoảng cách khác nhau ........................................... 77

4.2.2

So sánh các đặc tính khác nhau .......................................................... 80

CHƢƠNG V- MƠ PHỎNG CHƢƠNG TRÌNH TRUY VẤN ẢNH BẰNG


MATLAB ................................................................................................................ 85
5.1. Sơ đồ khối chƣơng trình và lý thuyết áp dụng .......................................... 85
5.2. Mơ tả chƣơng trình mơ phỏng ................................................................... 88
5.3. Kết quả truy vấn và đánh giá ..................................................................... 91
5.3.1

Thực nghiệm 1 .................................................................................... 91

5.3.2

Thực nghiệm 2 .................................................................................... 94

5.3.3

Thực nghiệm 3 .................................................................................... 98

KẾT LUẬN ........................................................................................................... 101
TÀI LIỆU THAM KHẢO ..................................................................................... 103

4


DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT

CBIR

Content Based Image Retrieval

CIE


Commision Internationale de l‟Éclairage

DBMS

Database Management System

EMD

Earth Move Distance

HSV

Hue Saturation Value

IRMA

Image Retrieval in Medical Applications

JPEG

Joint Photographic Experts Group

JSD

Jensen Shannon Divergence

KLT

Karhunen-Loeve Transform


MPEG

Moving Picture Experts Group

PCA

Principal component analysis

QBIC

Query by Image Content

SVD

Singular Value Decompostion

5


DANH MỤC CÁC BẢNG
Bảng 2.1 Các hàm đơn thức đƣợc sử dụng cho các vector đặc tính bất biến ......... 44
Bảng 4.1 Tỉ lệ lỗi [%] trên WANG và IRMA-1617 sử dụng các phép đo khác nhau.
Đối với WANG, lƣợc đồ đặc tính bất biến f ( X )  X (4,0).X (0,8) đƣợc sử
dụng, đối với IRMA-1617 lƣợc đồ đặc tính cục bộ đƣợc sử dụng [Ref 4].
.................................................................................................................. 77
Bảng 4.2 Tỉ lệ lỗi [%] trên IRMA-1617 sử dụng các phép so sánh ảnh khác nhau
[Ref 4]. ..................................................................................................... 79
Bảng 4.3 Tỉ lệ lỗi [%] sử dụng đặt tính dựa trên vùng và các phép so sánh khác
nhau [Ref 4] ............................................................................................. 79
Bảng 4.4 Tỉ lệ lỗi [%] sử dụng các đặc tính khác nhau cho WANG [Ref 4]. ........ 81

Bảng 4.5 Tỉ lệ lỗi [%] sử dụng các đặc tính khác nhau cho IRMA-1617 [Ref 4]. . 81
Bảng 4.6 Tỉ lệ lỗi [%] sử dụng lƣợc đồ đặc tính bất biến với biến đổi xoay một
phần cho cơ sở dữ liệu WANG vơi f ( X )  X (4,0).X (0,8) ..................... 83

6


DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 1.1 Các bƣớc chính trong xử lý ảnh số .......................................................... 13
Hình 1.2 Các thành phần chính của hệ thống xử lý ảnh ......................................... 14
Hình 1.3 Ảnh biến dạng do nhiễu ........................................................................... 17
Hình 1.4 Sơ đồ khối hệ thống truy tự nhiên ............................................................ 20
Hình 1.5. Hệ thống truy vấn có tƣơng tác ............................................................... 27
Hình 2.1. Biến đổi TCHSV từ RGB thành HSV và lƣợng tử hóa Qc166 cung cấp 166
màu HSV.................................................................................................. 32
Hình 2.2 Biểu diễn màu phân bố cục bộ ................................................................. 34
Hình 2.3 Đặc tính màu và khơng gian kết hợp tìm ảnh bằng cách so sánh phân bố
khơng gian của các vùng.......................................................................... 35
Hình 2.4 Sơ đồ tính tốn tích phân bất biến ............................................................ 39
Hình 2.5 Hàm kernel f(X) của vùng cục bộ ............................................................ 40
Hình 2.6 Mục đích của lƣợc đồ đặc tính. ................................................................ 43
Hình 2.7 Ảnh ví dụ về đặc tính cấu trúc: a) độ thô lớn b) độ thô nhỏ c) độ tƣơng
phản cao d) độ tƣơng phản thấp e) có tính hƣớng f) khơng có tính hƣớng
.................................................................................................................. 48
Hình 2.8 Trích trọn đặc tính cục bộ ........................................................................ 52
Hình 2.10 Các phân vùng ví dụ của các ảnh với số lƣợng các vùng và k khác nhau
.................................................................................................................. 54
Hình 3.1 Ba lƣợc đồ với khoảng cách thành phần giống nhau từng đôi một ......... 57
Hình 3.2 So sánh lƣợc đồ: Dạng bình phƣơng và EMD ......................................... 64
Hình 3.3 Time warp distance T(Ha,Hb)=6, T(Ha,Hc)=16, T(Hb,Hc)=22 ................. 65

Hình 3.4 Ví dụ về biểu đồ căn chỉnh. a) giữa lƣợc đồ a và b, b) giữa lƣợc đồ a và c
.................................................................................................................. 65
Hình 3.5. Căn vùng để tìm vùng phù hợp bởi Hugarian lƣợng tử hóa ................... 70
Hình 4.1 Tƣơng quan giữa các phép đo chất lƣợng quy theo phạm vị [-100,100] . 75
Hình 4.2 Ví dụ ảnh từ 10 loại ảnh của CSDL WANG [Ref 4]. .............................. 76

7


Hình 4.3 Ví dụ ảnh từ 6 loại ảnh của CSDL IRMA-1617 [Ref 4].......................... 76
Hình 4.4 Một vài ảnh từ loại ảnh “lồng ngực” của CSDL IRMA-1617 [Ref 4]. ... 77
Hình 4.5 Biểu đồ PR sử dụng các hàm khoảng cách khác nhau [Ref 4]. ............... 78
Hình 4.6 Biểu đồ PR cho WANG và IRMA-1617 tƣơng ứng với tỉ lệ lỗi trong
Bảng 4.4 và .............................................................................................. 82
Hình 4.7 Kết quả từ multi-dimensional scaling cho các đặc tính của WANG ....... 83
Hình 4.8 Kết quả từ multi-dimensional scaling cho các đặc tính của IRMA ......... 84
Hình 5.1 Sơ đồ khối mơ tả hoạt động của chƣơng trình ......................................... 85
Hình 5.2 Giao diện chƣơng trình mơ phỏng ........................................................... 89
Hình 5.3 Một số ảnh ví dụ trong tập ảnh ................................................................ 90
Hình 5.5 Kết quả truy vấn thực nghiệm 1a (mức ngƣỡng 1.4*e+004). .................. 92
Hình 5.6 Kết quả truy vấn thực nghiệm 1a (mức ngƣỡng 1.3*e+004) ................... 93
Hình 5.7 Kết quả truy vấn thực nghiệm 1b (mức ngƣỡng 4.5*e+004)................... 93
Hình 5.8 Kết quả truy vấn thực nghiệm 1b (mức ngƣỡng 2.6*e+004)................... 94
Hình 5.10 Kết quả truy vấn thực nghiệm 2a (mức ngƣỡng 3.3*e+004) ................. 94
Hình 5.11 Kết quả truy vấn thực nghiệm 2a (mức ngƣỡng 2.85*e+004) ............... 95
Hình 5.12 Kết quả truy vấn thực nghiệm 2b (mức ngƣỡng 9.9*e+004)................. 96
Hình 5.13 Kết quả truy vấn thực nghiệm 2b (mức ngƣỡng 5*e+004).................... 96
Hình 5.15 Kết quả truy vấn thực nghiệm 2c (mức ngƣỡng 8*e+004) .................... 97
Hình 5.16 Kết quả truy vấn thực nghiệm 2c (mức ngƣỡng 5.4*e+004) ................. 97
Hình 5.18 Kết quả truy vấn thực nghiệm 3 (mức ngƣỡng 2.9*e+004)................... 98

Hình 5.19 Kết quả truy vấn thực nghiệm 3 (mức ngƣỡng 1.9*e+004)................... 99

8


LỜI NĨI ĐẦU
Ảnh đóng vai trị quan trọng trong cuộc sống thơng tin hàng ngày của chúng
ta. Có ngƣời đã từng so sánh: một bức ảnh có thể nói lên nhiều điều hơn dùng ngàn
từ để mô tả. Sự xuất hiện phổ biến của máy ảnh kỹ thuật số hiện nay đã làm gia
tăng nhanh chóng số lƣợng ảnh kỹ thuật số. Khối lƣợng ảnh đồ sồ này không thể
quản lý một cách thủ công bởi con ngƣời đƣợc nữa. Một ngƣời có dễ dàng tìm
kiếm một bức ảnh theo yêu cầu trong cơ sở dữ liệu chỉ gồm 100 bức ảnh. Tuy
nhiên, nếu số lƣợng ảnh là hàng ngàn, hàng chục ngàn thì cơng việc này trở thành
bất khả thi. Sự phát triển của cơng nghệ máy tính ngày nay có thể trợ giúp trong
việc tìm kiếm ảnh cũng giống nhƣ cách thực hiện tìm kiếm văn bản mà ta đã biết.
Một phƣơng thức tìm kiếm ảnh trong cơ sở dữ liệu ảnh là tạo các văn bản
mô tả tất cả ảnh trong cơ sở dữ liệu và sử dụng phƣơng pháp tìm kiếm thơng tin
dựa trên văn bản để tìm ảnh. Phƣơng pháp này cũng khơng hồn tồn khả thi do
việc chú thích cho các ảnh phải thực hiện thủ công và tốn rất nhiều thời gian. Mặt
khác, các chú thích này chƣa hẳn đã mơ tả hết đƣợc nội dung của ảnh.
Vì vậy, cần có một phƣơng pháp khác để tìm kiếm ảnh. Một phạm vi lớn các
ứng dụng cần tìm kiếm ảnh nhƣ: trong y tế, rất nhiều ảnh đƣợc tạo ra và bác sỹ có
thể cần tìm kiếm những hình ảnh tƣơng tự để hiểu về quá trình điều trị của các
bệnh nhân và kết quả điều trị của họ. Một phóng viên có thể tìm kiếm ảnh để minh
họa bài báo của mình. Các ví dụ này cho thấy việc tìm kiếm khơng giống hồn
tồn nhƣ việc tìm kiếm trong các cơ sở dữ liệu truyền thống mà là sự tìm kiếm sự
tƣơng tự. Sự tƣơng tự này cần phải đƣợc xác định một các chính xác để có thể thực
hiện q trình tìm kiếm tự động.
Các kỹ thuật hiện nay quy vào tìm kiếm ảnh một cách tự nhiên (contentbased image retrieval – CBIR). Trong CBIR, cần phải trích chọn các thơng tin hữu


9


ích từ dữ liệu thô để thu đƣợc nội dung của ảnh. Q trình trích chọn các đặc trƣng
nội dung của ảnh sẽ có tác động đến hiệu quả của quá trình truy vấn ảnh tự nhiên.
Luận văn này trình bày các phƣơng pháp trích chọn nội dung của ảnh (các
đặc tính của ảnh), các phƣơng pháp so sánh các đặc tính của ảnh để đánh giá mức
độ tƣơng tự của ảnh yêu cầu so với các ảnh trong cơ sở dữ liệu. Luận văn gồm các
phần chính nhƣ sau:
- Chƣơng I – Tổng quan về truy vấn ảnh tự nhiên : trình bày tổng quan về
xử lý ảnh, các vấn đề cơ bản trong truy vấn ảnh tự nhiên.
- Chƣơng II – Các đặc tính truy vấn ảnh tự nhiên: trình bày các đặc tính khác
nhau đƣợc trích chọn từ ảnh để phục vụ cho việc so sánh ảnh sau này.
- Chƣơng III – So sánh đặc tính truy vấn ảnh: trình bày các phƣơng pháp
khác nhau để đánh giá mức độ tƣơng tự của ảnh.
- Chƣơng IV – Đánh giá chất lƣợng truy vấn ảnh: giới thiệu các phƣơng
pháp đánh giá chất lƣợng truy vấn ảnh
- Chƣơng V – Mô phỏng truy vấn ảnh bằng Matlab: giới thiệu một chƣơng
trình truy vấn đơn giản viết trên Matlab.
Truy vấn ảnh tự nhiên là vấn đề vẫn còn đang đƣợc nghiên cứu để đáp ứng
các yêu cầu khác nhau trong các lĩnh vực áp dụng khác nhau. Trong tƣơng lai, tơi
hi vọng có cơ hội để nghiên cứu, tìm hiểu đầy đủ và chi tiết hơn. Trong phạm vi
của một luận văn cao học và khả năng hiểu biết còn có những hạn chế, luận văn
này khơng thể tránh khỏi những thiếu sót, tơi rất mong nhận đƣợc ý kiến đóng góp
của các thầy cơ và bạn bè để có thể hồn thiện hơn nữa trong những nghiên cứu
sau này.
Tơi xin chân thành cảm ơn thầy giáo PGS .TS. Nguyễn Tiến Dũng, bạn bè,
đồng nghiệp và gia đình đã giúp đỡ tơi hồn thành đƣợc luận văn tốt nghiệp của
mình.


Hà Nội, tháng 04 năm 2014

10


Chƣơng I : Tổng quan về Truy vấn ảnh tự nhiên

CHƢƠNG I – TỔNG QUAN VỀ TRUY VẤN ẢNH TỰ NHIÊN
1.1. Giới thiệu về xử lý ảnh
Xử lý ảnh số có nhiều ứng dụng trong thực tế. Các nghiên cứu về xử lý ảnh
số bắt đầu từ những năm đầu của thập kỷ 60 tại phịng thí nhiệm Jet Propulsion.
Do có sự hạn chế về kích thƣớc và khối lƣợng của các hệ thống chụp hình gắn trên
tàu vũ trũ nên ảnh nhận đƣợc từ các hệ thống này bị giảm chất lƣợng nhƣ bị mờ,
méo hình học và nhiễu nền. Do đó các ảnh này phải đƣợc xử lý để đạt đƣợc chất
lƣợng tốt hơn. Hình ảnh mặt trăng và sao hỏa mà ta thƣờng gặp trong các tạp chí
đều đƣợc xử lý bằng máy tính số.
Ứng dụng của xử lý ảnh có tác động mạnh mẽ đến nhiễu lĩnh vực khác nhƣ:
viễn thám (remotesensing) qua vệ tinh hay tàu vũ trụ; truyền ảnh, lƣu trữ cho các
ứng dụng nội vụ, hành chánh; xử lý y học, radar, somar; xử lý ảnh acoustic,
robotics, giám định tự động các ngành công nghiệp...
Trong ứng dụng y học, xử lý ảnh liên quan đến xử lý các tia X, các ảnh cắt
lớp và các ảnh y học khác từ chụp điện (radiology), cộng hƣởng từ tính hạt nhân
(nuclear magnetic retonance), quét siêu âm (ultrasonic scanning). Các kỹ thuật này
đƣợc dùng để phát hiện các khối u hoặc các bệnh khác của bệnh nhân.
Một ứng dụng khác gần gũi hơn với cuộc sống là cải tiến ảnh tivi. Hình ảnh
hiển thị trên màn hình ti vi có độ phân giải hạn chế, có bóng mờ, nhiễu nền, trƣợt
hình do xen dịng ở những mức độ khác nhau. Hiện nay, tivi số đang có những
bƣớc phát triển dần thay thế tivi truyền thống tƣơng tự và xử lý ảnh số sẽ có tác
động quyết định đến việc cải thiện chất lƣợng hình ảnh của những hệ truyền hình
hiện tại và làm phát triển hệ truyền hình mới nhƣ truyền hình có độ phân giải cao –

HDTV.
Ứng dụng của xử lý ảnh trong truyền thông là nén dữ liệu ảnh, giảm thời
gian kênh truyền và tiết kiệm khơng gian lƣu trữ. Ví dụ nhƣ trong hội nghị video,

11


Chƣơng I – Tổng quan về Truy vấn ảnh tự nhiên
điện thoại video, yêu cầu cần có dải tần rộng. Việc mã hóa thẳng chƣơng trình
video chất lƣợng quảng bá yêu cầu cần đến 100 triệu bít/sec. Nếu hy sinh một phần
chất lƣợng và dùng các sơ đồ mã hóa ảnh số thì có thể đạt đƣợc chất lƣợng đủ rõ
với nhịp bít chỉ dƣới 100 nghìn bít/sec.
Các ứng dụng khác nhƣ: trong sinh học, phân tích ảnh của các mẩu xƣơng,
mô, tế bào, kiểu ADN...; trong an ninh, quốc phòng, xử lý ảnh trinh thám để phát
hiện các mục tiêu nhƣ: phi trƣờng, tàu chiến, dàn phóng hỏa trên các vệ tình. Xử lý
vân tay, nhận dạng nhân thể...; trong nhiếp ảnh, điện ảnh, thay thế các kỹ thuật
phòng tối trong một số trƣờng hợp tạo hiệu quả đặc biệt trong phim ảnh; trong viễn
thám, trắc địa, tái tạo và tăng cƣờng độ rõ, độ sáng cho các ảnh số vệ tinh, lập bản
đồ, phát hiện tài nguyên, quản lý môi trƣờng, theo dõi biến động khi quyển, phát
hiện cháy rừng; trong tự động hóa: kiểm tra chất lƣợng sản phẩm tự động bằng hệ
thống giúp loại bỏ phế phẩm, xây dựng hình ảnh máy cho các rơ bốt.
1.2. Hệ thống xử lý ảnh
1.2.1 Ảnh

Ảnh tĩnh trong không gian 2 chiều đƣợc định nghĩa là một hàm hai biến
S(x,y), với S là giá trị biên độ (đƣợc biểu diễn bằng màu sắc) tại vị trí khơng gian
(x,y). Phân loại ảnh:
+ Ảnh tƣơng tự S(x,y): (x,y) liên tục, S liên tục
+ Ảnh số S(m,n): (m,n) rời rạc, S rời rạc.
Xử lý ảnh số là xử lý các tấm ảnh 2D bằng máy tính, hay nói cách khác là xử

lý số các số liệu 2 chiều. Ảnh số là ma trận của các số thực và số phức đƣợc biểu
diễn bởi số bit hữu hạn.
Trong việc biểu diễn ảnh mức xám (gray-level images), ảnh đƣợc biểu diễn
bởi mảng các con số hai chiều. Mỗi con số thể hiện cƣờng độ hoặc mức xám của
ảnh tại vị trí tƣơng đối. Nếu mỗi mức xám đƣợc biểu diễn bởi 8 bit thì số mức
12


Chƣơng I – Tổng quan về Truy vấn ảnh tự nhiên
xám đƣợc biểu diễn là 28=256 giá trị. Các mức này thông thƣờng đƣợc gán các giá
trị nguyên từ 0 đến 255, với 0 đặc trƣng cho mức tối thấp nhất và 255 đặc trƣng
cho mức xám cao nhất. Mỗi phần tử trong ma trận đƣợc gọi là pixel hoặc PEL.
Trong ảnh màu, cách biểu diễn cũng tƣơng tự, nhƣng tại mỗi vị trí của ma trận con
số sẽ biểu diễn 3 màu cơ bản: red, green, blue (RGB). Đối với việc biểu diễn màu
của 8bit*3 =24 bit tren một pixel thì con số chia làm 3 segments*8 bit. Mỗi
segment biểu diễn cƣờng độ của một trong 3 màu cơ bản.
1.2.2 Mơ tả hệ thống xử lý ảnh

Nhƣ đã trình bày trong phần giới thiệu, xử lý ảnh đƣợc ứng dụng rộng rãi
trong nhiều lĩnh vực của cuộc sống. Việc xử lý ảnh có thể đƣợc thực hiện thơng
qua hệ thống xử lý ảnh chuyên dùng hoặc hệ thống ảnh dùng trong xử lý, đào tạo.
Hình 0.1 mơ tả các bƣớc cơ bản cần thiết trong xử lý ảnh số.
Lƣu trữ

Thiết bị thu
nhận ảnh

Thu nhận
ảnh


Lƣu trữ

Số hố

Nhận
dạng

Phân tích
ảnh

Hệ quyết
định

Hình 0.1 Các bƣớc chính trong xử lý ảnh số
Trƣớc hết là q trình thu nhận ảnh. Ảnh có thể thu nhận qua camera.
Thƣờng ảnh thu nhận qua camera là tín hiệu tƣơng tự (loại camera ống kiểu
CCIR), nhƣng cũng có thể là tín hiệu số hố (loại CCD - Charge Coupled Device).
Ảnh cũng có thể thu nhận từ vệ tinh qua các bộ cảm ứng (sensor), hay ảnh,
tranh đƣợc quét trên scanner. Tiếp theo là q trình số hố (Digitalizer) để biến đổi
13


Chƣơng I – Tổng quan về Truy vấn ảnh tự nhiên
tín hiệu tƣơng tự sang tín hiệu rời rạc (lấy mẫu) và số hoá bằng lƣợng hoá, trƣớc
khi chuyển sang giai đoạn xử lý, phân tích hay lƣu trữ lại.
Quá trình phân tích ảnh thực chất bao gồm nhiều cơng đoạn nhỏ. Trƣớc hết
là công việc tăng cƣờng ảnh để nâng cao chất lƣợng ảnh. Do những nguyên nhân
khác nhau: có thể do chất lƣợng thiết bị thu nhận ảnh, do nguồn sáng hay do nhiễu,
ảnh có thể bị suy biến. Do vậy cần phải tăng cƣờng và khôi phục lại ảnh để làm nổi
bật một số đặc tính chính của ảnh, hay làm cho ảnh gần giống nhất với trạng thái

gốc- trạng thái trƣớc khi ảnh bị biến dạng. Giai đoạn tiếp theo là phát hiện các đặc
tính nhƣ biên, phân vùng ảnh, trích chọn các đặc tính, v.v...
Cuối cùng, tuỳ theo mục đích của ứng dụng, sẽ là giai đoạn nhận dạng, phân
lớp hay các quyết định khác. Với các giai đoạn trên, một hệ thống xử lý ảnh (cấu
trúc phần cứng theo chức năng) gồm các thành phần tối thiểu nhƣ Hình 0.2.
Màn hình
đồ hoạ

Camera

Bộ nhớ
ngồi

Màn hình

Bộ xử lý
tƣơng tự

Bộ nhớ
ảnh

Máy chủ

Bộ xử lý
ảnh số

Bàn phím

Máy in


Hình 0.2 Các thành phần chính của hệ thống xử lý ảnh

14


Chƣơng I – Tổng quan về Truy vấn ảnh tự nhiên
 Đối với một hệ thống xử lý ảnh thu nhận qua camera-camera nhƣ là con mắt
của hệ thống. Có 2 loại camera: camera ống loại CCIR và camera CCD. Loại
camera ứng với chuẩn CCIR quét ảnh với tần số 1/25 và mỗi ảnh gồm 625 dòng.
Loại CCD gồm các photo điốt và làm tƣơng ứng một cƣờng độ sáng tại một điểm
ảnh ứng với một phần tử ảnh (pixel). Nhƣ vậy, ảnh là tập hợp các điểm ảnh. Số
pixel tạo nên một ảnh gọi là độ phân giải (resolution).
 Bộ xử lý tƣơng tự (analog processor). Bộ phận này thực hiện các chức năng
sau:
- Chọn camera thích hợp nếu hệ thống có nhiều camera.
- Chọn màn hình hiển thị tín hiệu
- Thu nhận tín hiệu video thu nhận bởi bộ số hoá(digitalizer). Thực hiện lấy
mẫu và mã hoá.
- Tiền xử lý ảnh khi thu nhận: dùng kỹ thuật bảng tra (Look Up Table LUT).
 Bộ xử lý ảnh số. Gồm nhiều bộ xử lý chuyên dụng: xử lý lọc, trích chọn
đƣờng bao, nhị phân hố ảnh. Các bộ xử lý này làm việc với tốc độ 1/25 giây.
 Máy chủ. Đóng vai trị điều khiển các thành phần miêu tả ở trên.
 Bộ nhớ ngoài: Dữ liệu ảnh cũng nhƣ các kiểu dữ liệu khác, để có thể chuyển
giao cho các q trình khác, nó cần đƣợc lƣu trữ. Để có một ƣớc lƣợng, xét thí dụ
sau: một ảnh đen trắng cỡ 512 x 512 với 256 mức xám chiếm 256K bytes. Với một
ảnh màu cùng kích thƣớc dung lƣợng sẽ tăng gấp 3 lần.
1.3. Các vấn đề cơ bản trong xử lý ảnh số
1.3.1 Biểu diễn ảnh

Trong biểu diễn ảnh, ngƣời ta thƣờng dùng các phần tử đặc trƣng của ảnh là

pixel. Nhìn chung có thể xem một hàm hai biến chứa các thông tin nhƣ biểu diễn
15


Chƣơng I – Tổng quan về Truy vấn ảnh tự nhiên
của một ảnh. Các mơ hình biểu diễn ảnh cho ta một mơ tả lơ gic hay định lƣợng
các tính chất của hàm này. Trong biểu diễn ảnh cần chú ý đến tính trung thực của
ảnh hoặc các tiêu chuẩn “thơng minh” để đo chất lƣợng ảnh hoặc tính hiệu quả của
các kỹ thuật xử lý.
Việc xử lý ảnh số yêu cầu ảnh phải đƣợc mẫu hoá và lƣợng tử hố. Thí dụ
một ảnh ma trận 512 dịng gồm khoảng 512 x 512 pixel. Việc lƣợng tử hoá ảnh là
chuyển đổi tín hiệu tƣơng tự sang tín hiệu số (Analog Digital Convert) của một ảnh
đã lấy mẫu sang một số hữu hạn mức xám.
Một số mơ hình thƣờng đƣợc dùng trong biểu diễn ảnh: mơ hình tốn, mơ
hình thống kê. Trong mơ hình tốn, ảnh hai chiều đƣợc biểu diễn nhờ các hàm hai
biến trực giao gọi là các hàm cơ sở. Với mơ hình thống kê, một ảnh đƣợc coi nhƣ
một phần tử của một tập hợp đặc trƣng bởi các đại lƣợng nhƣ: kỳ vọng toán học,
hiệp biến, phƣơng sai, moment.
1.3.2 Tăng cường ảnh - khôi phục ảnh

Tăng cƣờng ảnh là bƣớc quan trọng, tạo tiền đề cho xử lý ảnh. Nó
gồm một loạt các kỹ thuật nhƣ: lọc độ tƣơng phản, khử nhiễu, nổi màu...
Khôi phục ảnh là nhằm loại bỏ hoặc tối thiểu hóa các xuống cấp trong ảnh.
Với một hệ thống tuyến tính, ảnh của một đối tƣợng có thể biểu diễn bởi:


g(x,y) =

  h( x, y; ,  ) f ( ,  )dd (   ( x, y))




Trong đó:
- (x,y) là hàm biểu diễn nhiễu cộng.
- f(, ) là hàm biểu diễn đối tƣợng.
- g(x,y) là ảnh thu nhận.
- h((x, y; , ) là hàm tán xạ điểm (Point Spread Function - PSF).
16


Chƣơng I – Tổng quan về Truy vấn ảnh tự nhiên

g(x, y)

f(,)
h(x,y; ,)



Ảnh đầu vào
 f(,)


Ảnh đầu ra
g(x, y)

Hệ thống
thu nhận ảnh

y



x


Hình 0.3 Ảnh biến dạng do nhiễu
Hình 0.3 là một thí dụ về sự biến dạng của ảnh do nhiễu.
Một vấn đề khơi phục ảnh tiêu biểu là tìm một xấp xỉ của f(, ) khi PSF
của nó có thể đo lƣờng hay quan sát đƣợc, ảnh mờ và các tính chất xác suất của
q trình nhiễu.
1.3.3 Biến đổi ảnh

Thuật ngữ biến đổi ảnh (Image Transform) thƣờng dùng để nói tới một lớp
các ma trận đơn vị và các kỹ thuật dùng để biến đổi ảnh. Cũng nhƣ các tín hiệu
một chiều đƣợc biểu diễn bởi một chuỗi các hàm cơ sở, ảnh cũng có thể đƣợc biểu
diễn bởi một chuỗi rời rạc các ma trận cơ sở gọi là ảnh cơ sở. Phƣơng trình ảnh cơ
sở có dạng:
A*k,l = ak al*T, với ak là cột thứ k của ma trận A. A là ma trận đơn vị.
Có nghĩa là A A*T = I. Các A*k,l định nghĩa ở trên với k,l = 0,1, ..., N-1 là
ảnh cơ sở. Có nhiều loại biến đổi đƣợc dùng nhƣ :
- Biến đổi Fourier, Sin, Cosin, Hadamard,. . .
- Tích Kronecker
- Biến đổi KL (Karhumen Loeve): biến đổi này có nguồn gốc từ khai triển
của các quá trình ngẫu nhiên gọi là phƣơng pháp trích chọn các thành phần chính.

17


Chƣơng I – Tổng quan về Truy vấn ảnh tự nhiên
Do phải xử lý nhiều thơng tin, các phép tốn nhân và cộng trong khai triển là

khá lớn. Do vậy, các biến đổi trên nhằm làm giảm thứ nguyên của ảnh để việc xử
lý ảnh đƣợc hiệu quả hơn.
1.3.4 Phân tích ảnh

Phân tích ảnh liên quan đến việc xác định các độ đo định lƣợng của một ảnh
để đƣa ra một mô tả đầy đủ về ảnh. Các kỹ thuật đƣợc sử dụng ở đây nhằm mục
đích xác định biên của ảnh. Có nhiều kỹ thuật khác nhau nhƣ lọc vi phân hay dò
theo quy hoạch động.
Ngƣời ta cũng dùng các kỹ thuật để phân vùng ảnh. Từ ảnh thu đƣợc, ngƣời
ta tiến hành kỹ thuật tách (split) hay hợp (fusion) dựa theo các tiêu chuẩn đánh giá
nhƣ: màu sắc, cƣờng độ, v...v. Các phƣơng pháp đƣợc biết đến nhƣ Quad-Tree,
mảnh hoá biên, nhị phân hoá đƣờng biên. Cuối cùng, phải kể đến các kỹ thuật phân
lớp dựa theo cấu trúc.
1.4. Giới thiệu về truy vấn ảnh tự nhiên
Sự phát triển nhanh chóng của cơng nghệ máy tính và viễn thông đã dẫn đến
việc phải lƣu trữ một khối lƣợng khổng lồ các dữ liệu đa phƣơng tiện trong nhiều
lĩnh vực khác nhau nhƣ y tế, viễn thám, giải trí, giáo dục... Điều này cũng giống
nhƣ sự phát triển nhanh chóng khối lƣợng các dữ liệu số liệu trong thời kỳ đầu phát
triển của cơng nghệ máy tính dẫn đến việc phát triển hệ thống quản lý dữ liệu
(DBMS). Các hệ thống quản lý dữ liệu truyền thống đƣợc thiết kế để tổ chức các
dữ liệu số liệu thành các nhóm dữ liệu liên quan để việc lƣu trữ và truy vấn có thể
thực hiện một cách tiện lợi và hiệu quả. Tuy nhiên, kỹ thuật này không phù hợp để
quản lý các dữ liệu đa phƣơng tiện do sự đa dạng về kiểu và định dạng dữ liệu,
kích thƣớc lớn của các đối tƣợng, sự khó khăn khi trích chọn ngữ nghĩa từ dữ liệu.
Để có thể sử dụng các thông tin đa phƣơng tiện hiệu quả cần phải có một phƣơng

18


Chƣơng I – Tổng quan về Truy vấn ảnh tự nhiên

pháp để lƣu trữ, sắp xếp và truy vấn. Các dữ liệu đa phƣơng tiện khác có thể yêu
cầu các công cụ và phƣơng pháp khác nhau.
Từ những năm 1970, truy vấn ảnh đã là lĩnh vực nghiên cứu thực sự trong
hai cộng đồng nghiên cứu chính – quản lý dữ liệu và ảnh máy tính. Các nghiên cứu
về truy vấn ảnh từ hai góc độ khác nhau. Góc độ thứ nhất chủ yếu dựa trên văn bản
(text) cịn góc độ thứ hai dựa trên các đặc tính ảnh của dữ liệu.
Truy vấn ảnh dựa trên văn bản (text-based image retrieval) xuất hiện từ
những năm cuối thập kỷ 1970. Tại thời điểm đó, hình ảnh đƣợc chú thích bằng các
từ khóa và đƣợc lƣu trữ nhƣ là từ khóa truy vấn trong các cơ sở dữ liệu truyền
thống. Có hai vấn đề khiến việc chú thích thủ cơng khơng hiệu quả khi kích thƣớc
cơ sở dữ liệu ảnh trở nên quá lớn. Thứ nhất là giới hạn về số lƣợng nhân cơng để
thực hiện chú thích cho ảnh. Thứ hai là khó khăn trong việc mơ tả nội dung phong
phú của hình ảnh khi chỉ sử dụng số lƣợng từ khóa hạn chế.
Vào những năm đầu của thập kỷ 1990, do sự phát triển các bộ sƣu tập ảnh có
kích thƣớc lớn, phƣơng pháp truy vấn ảnh tự nhiên đƣợc đề xuất để khắc phục
những khó khăn trên. Trong hệ thống CBIR, hình ảnh đƣợc tự động lập chỉ mục
(indexing) bằng việc tổng kết các nội dung ảnh của chúng thơng các đặc tính đƣợc
trích chọn nhƣ màu sắc, cấu trúc, hình dạng. Nhƣ vậy, các đặc tính đƣợc trích chọn
sẽ thay thế cho các chú thích bằng văn bản hay từ khóa. Hệ thống CBIR điển hình
thƣờng tự động trích chọn (và lập chỉ mục) nội dung hình ảnh để đáp ứng yêu cầu
của lĩnh vực áp dụng cụ thể. Một hệ thống truy vấn ảnh tự nhiên điển hình đƣợc
mơ tả trong Hình 0.4.
Cơ sở dữ liệu lƣu trữ các ảnh. Nội dung ảnh (đặc tính ảnh) của các ảnh trong
cơ sở dữ liệu đƣợc trích chọn và đƣợc mơ tả bởi các vector đặc tính đa chiều. Các
vector đặc tính của hình ảnh trong cơ sở dữ liệu hình thành cơ sở dữ liệu đặc tính.
Để truy vấn ảnh, ngƣời sử dụng cung cấp cho hệ thống truy vấn ảnh các ảnh mẫu

19



Chƣơng I – Tổng quan về Truy vấn ảnh tự nhiên
hoặc hình phác thảo. Hệ thống sẽ trích chọn nội dung các ảnh mẫu và biểu diễn bởi
các vector đặc tính. Mức độ tƣơng tự/khoảng cách giữa các vector đặc tính của ảnh
mẫu và các vector đặc tính của ảnh trong cơ sở dữ liệu sẽ đƣợc tính tốn và quá
trình truy vấn sẽ đƣợc thực hiện với sự hỗ trợ của sơ đồ chỉ mục (indexing
scheme). Sơ đồ chỉ mục giúp việc truy vấn hình ảnh trong cơ sở dữ liệu hiệu quả
hơn. Các hệ thống truy vấn hiện nay bao gồm cả phản hồi (feedback) của ngƣời sử
dụng để điều chỉnh quá trình truy vấn để đạt đƣợc kết quả truy vấn tốt hơn.

Phản hồi

Ngƣời
sử dụng

Hình thành
u cầu

Mơ tả nội
dung ảnh

Các vector
đặc tính
So sánh tính
tƣơng tự

Cở sở dữ
liệu ảnh

Mơ tả nội
dung ảnh


Cơ sở dữ
liệu đặc tính
Tra chỉ mục &
Truy vấn

Đầu ra

Kết quả
truy vấn

Hình 0.4 Sơ đồ khối hệ thống truy vấn ảnh tự nhiên
1.5. Trích chọn đặc tính để truy vấn ảnh
Trích chọn đặc tính là cơ sở của hệ thống truy vấn ảnh tự nhiên. Các đặc
điểm này có thể đƣợc ra thành đặc tính chung hoặc riêng. Các đặc tính chung điển
hình bao gồm màu sắc, cấu trúc hình dạng, quan hệ khơng gian, biến dạng cịn các
đặc tính riêng đƣợc áp dụng cho các lĩnh vực cụ thể nhƣ nhận dạng khuôn mặt
hoặc nhận dạng vân tay. Mỗi đặc tính có thể có một vài thể hiện.
20


Chƣơng I – Tổng quan về Truy vấn ảnh tự nhiên
Màu sắc
Màu sắc là một trong những thành phần dễ nhận biết nhất của nội dung hình
ảnh và đƣợc sử dụng rộng rãi để truy vấn ảnh bởi tính bất biến đối với phóng to thu
nhỏ, dịch chuyển và xoay ảnh. Các vấn đề quan trọng trong việc trích chọn màu
bao gồm khơng gian màu, lƣợng tử hóa màu và lựa chọn hàm so sánh tính tƣơng
tự. Đặc tính màu của hình ảnh có thể thể hiện bởi lƣợc đồ màu hoặc moment màu.
Cấu trúc
Cấu trúc là các mẫu ảnh với các đặc tính đồng nhất (khơng phải là tính đồng

nhất của một màu hay mức sáng đơn lẻ). Vỏ cây, đám mây, nƣớc, gạch, vải là ví
dụ về cấu trúc. Đặc tính cấu trúc điển hình bao gồm độ tƣơng phản, tính đồng nhất,
độ thơ, độ ráp, tần suất, mật độ, tính hƣớng. Đặc tính cấu trúc thƣờng chứa các
thông tin quan trọng về sự sắp xếp cấu trúc của bề mặt và mối quan hệ với môi
trƣờng xung quanh.
Có hai loại đặc tính cấu trúc cơ bản: dựa trên mơ hình thống kế và dựa trên
biến đổi. Loại thứ nhất sử dụng sự phụ thuộc không gian mức xám của cấu trúc và
trích chọn các số liệu có ý nghĩa để thể hiện cấu trúc. Ví dụ sự phụ thuộc không
gian mức xám của cấu trúc là ma trận đồng xuất hiện (co-occurence matrix).
Thống kê tỷ lệ góc đƣờng cũng đƣợc sử dụng bằng cách phân tích mối quan hệ
khơng gian của các đƣờng thẳng và đặc tính của đối tƣợng xung quanh. Tamura
cũng nghiên cứu vấn đề này nhƣng theo một cách nhìn khác. Dựa trên cơ sở tâm lý
học, Tamura chỉ ra rằng có sáu đặc tính cấu trúc cơ bản là độ thơ, độ tƣơng phản,
tính hƣớng, tính giống đƣờng thẳng, tính đều đặn, độ ráp. Phƣơng pháp này lựa
chọn các đặc tính tƣơng ứng với đặc điểm hệ thống thị giác của con ngƣời hơn là
đo lƣờng thống kê dữ liệu và vì vậy mà có thể thích hợp để truy vấn các hình ảnh
tự nhiên.

21


Chƣơng I – Tổng quan về Truy vấn ảnh tự nhiên
Một nghiên cƣu về nhận biết cấu trúc của con ngƣời chỉ ra rằng ba chiều
trực giao quan trọng nhất là “sự lặp lại”, tính hƣớng và “tính chất hạt và độ phức
tạp”.
Một số phép biến đổi đƣợc sử dụng để trích chọn đặc tính cấu trúc nhƣ biến
đổi cosin rời rạc DCT, biến đổi Fourier-Mellin, Polar Fourier, biến đổi Gabor và
wavelet.
Hình dạng
Hai bƣớc quan trọng liên quan đến trích chọn đặc tính hình dạng là phân

đoạn ảnh và biểu diễn hình dạng.
Truy vấn ảnh dựa trên hình dạng đối tƣợng là một trong những mảng khó
nhất của truy vấn ảnh tự nhiên do sự khó khăn trong việc phân đoạn ảnh mức thấp
và có nhiều cách thức để chiếu đối tƣợng ba chiều thành hình 2 chiều. Có rất nhiều
kỹ thuật phân đoạn ảnh: dựa trên mức ngƣỡng toàn bộ, kỹ thuật phát triển vùng
(region-growing), kỹ thuật tách hợp, kỹ thuật dựa theo đƣờng biên, kỹ thuật dựa
trên cấu trúc, kỹ thuật dựa trên màu, kỹ thuật dựa trên mơ hình. Nói chúng, khó có
thể phân vùng ảnh một cách chính xác do sự phức tạp về hình dạng của mỗi đối
tƣợng, sự tồn tại của bóng hình, nhiễu...
Khi các đối tƣợng đã đƣợc phân vùng, đặc tính hình dạng của chúng sẽ biểu
diễn và lập chỉ mục. Thông thƣờng, biểu diễn hình dạng đƣợc phân ra thành ba
loại:
-

Biểu diễn dựa trên đƣờng bao (boundary-based representations): các đặc
tính thƣờng dùng là mã xích (chain code), mã Fourier (Fourier descriptor),
và UNL descriptor.

-

Biểu diễn dựa trên vùng: đặc tính bao gồm lƣợng bất biến momen
(moment invariant), đặc tính hình thái học (morphological descriptor),
Zernike moment, pseudo- Zernike)
22


Chƣơng I – Tổng quan về Truy vấn ảnh tự nhiên

-


Biếu diễn kết hợp: kết hợp các biểu diễn cơ bản nhƣ moment invariant
với đặc tính Fourier hoặc với đặc tính UNL.
Đặc tính Fourier đƣợc trích chọn bằng cách áp dụng biến đổi Fourier đối với

đƣờng bao 1D. Do nhiễu đã đƣợc số hóa ảnh hƣởng đáng kể đến kỹ thuật này nên
một phƣơng pháp khác đã đƣợc phát triển, phƣơng pháp này cũng không bị ảnh
hƣởng bởi sự thay đổi hình học.
Kết hợp các đặc tính
Việc sử dụng một loại đặc tính để truy vấn ảnh thƣờng khơng cho kết quả
một cách chính xác. Để nâng cao khả năng truy vấn ảnh cả về tốc độ và chất lƣợng
thì cần phải kết hợp nhiều đặc tính khác nhau.
Có thể phân loại kết hợp đặc tính thành kết hợp nối tiếp hoặc kết hợp song
song. Kết hợp đặc tính nối tiếp, thƣờng đƣợc gọi là lọc đặc tính (feature filtering),
là một q trình nhiều giai đoạn trong đó các đặc tính khác nhau đƣợc lần lƣợt sử
dụng để lọc bớt bộ ảnh ứng viên. Trong phƣơng pháp kết hợp đặc tính song song,
một vài đặc tính đƣợc sử dụng đồng thời trong quá trình truy vấn. Trong phƣơng
pháp này, các trọng số khác nhau sẽ đƣợc gán cho các đặc tính khác nhau do các
đặc tính khác nhau có khả năng phân biệt khác nhau, tùy thuộc theo từng ứng dụng
và nhiệm vụ cụ thể. Phƣơng pháp kết hợp các đặc tính tỏ ra hữu hiệu hơn phƣơng
pháp sử dụng đặc tính đơn lẻ và đƣợc sử dụng trong rất nhiều hệ thống CBIR. Hệ
thống QBIC (Query by Image Content) cho phép ngƣời sử dụng lựa chọn mức độ
quan trọng của các đặc tính màu, cấu trúc và hình dạng.
Hạn chế chủ yếu của việc kết hợp các đặc tính trong hầu hết các hệ thống
CBIR là sự liên quan quá lớn của ngƣời sử dụng không những trong việc lựa chọn
các đặc tính trong mỗi lần truy vấn mà cịn trong việc xác định các trọng số đặc
tính. Một hệ thống thành cơng dựa trên kết hợp đặc tính cần phải rõ hiểu rõ sự phù
hợp của mỗi đặc tính và các trọng số đƣợc sử dụng để cho ra kết quả tốt. Để tạo ra
23



Chƣơng I – Tổng quan về Truy vấn ảnh tự nhiên
các yêu cầu để có kết quả truy vấn tốt đơi khi rất khó khăn. Hệ thống CBIR tƣơng
tác có thể đƣợc thiết kế để đơn giản hóa vấn đề này.
1.6. Lập chỉ mục đặc tính (Feature Indexing)
Thơng thƣờng, các đặc tính ảnh đƣợc biểu diễn bởi các vector đa chiều, các
vector này đƣợc sử dụng để so sánh sự tƣơng tự giữa hai bƣớc ảnh bằng cách tính
khoảng cách đặc tính. Khi số lƣợng hình ảnh trong cơ sở dữ liệu nhỏ, việc tìm
kiếm tuần tự có thể chấp nhận đƣợc về mặt thời gian và chất lƣợng tìm kiếm. Tuy
nhiên, với các cơ sở dữ liệu ảnh lớn, việc lập chỉ mục (indexing) hỗ trợ việc tìm
kiếm hiệu quả dựa trên nội dung ảnh hoặc đặc tính đƣợc trích chọn. Trong hệ
thống quản lý dữ liệu liên quan truyền thống (RDBMS), các kỹ thuật lập chỉ mục
phổ biến là B-tree, hay dùng là B+ tree. B-tree cho phép tìm kiếm một cách hiệu
quả khi khóa tìm là vơ hƣớng. Tuy nhiên, kỹ thuật này khơng thích hợp cho việc
lập chỉ mục nội dung ảnh biểu diễn bởi các đặc tính đa chiều. Kỹ thuật R-tree và
các biến thể là các kỹ thuật indexing đa chiều phổ biến nhất.
Giảm thiểu số chiều
Kinh nghiệm chỉ ra rằng R-Tree và R*-Tree chỉ hoạt động tốt cho truy vấn
khi số chiều của các khóa indexing nhỏ hơn 20. Đối với khơng gian nhiều chiều
hơn, khả năng thực hiện của kỹ thuật này suy giảm nhanh chóng. Mặc dù số chiều
vector đặc tính có đƣợc do kết hợp nhiều đặc tính thƣờng là bậc của 10 2, số lƣợng
các chiều không dƣ thừa thực sự ít hơn nhiều. Vì vậy, việc giảm số chiều phải
đƣợc thực hiện trƣớc khi lập chỉ mục các vector đặc tính. Có hai phƣơng pháp
đƣợc sử dụng rộng rãi để giảm số chiều là biến đổi KL (Karhunen-Loeve
Transform -KLT) và phân nhóm theo cột (Column-wise Clustering).
KLT đƣợc sử dụng trong nhiều phạm vi nhƣ đặc tính để nhận diện khn
mặt, principal component analysis. Do KLT là thuật tốn u cầu tính tốn nhiều

24



Chƣơng I – Tổng quan về Truy vấn ảnh tự nhiên
nên một số tính tốn xấp xỉ đƣợc sử dụng để lập chỉ mục bao gồm xấp xỉ nhanh
cho KLT, SVD mức thấp (low-rank singular value decompostion).
Phân nhóm (clustering) là một phƣơng pháp hữu ích khác để giảm chiều
vector. Ý tƣởng chính của việc phân nhóm là nhóm một bộ các đối tƣợng có đặc
điểm tƣơng tự thành một nhóm.
Kỹ thuật lập chỉ mục
Các kỹ thuật lập chỉ mục rất đa dạng và phong phú: thuật toán gầu nƣớc
(bucketing algorithm), k-d tree, quad-tree, K-D-B tree, hB-tree, R-tree và biến thể
R+-tree, R*-tree. Trong số đó, R-tree và các biến thể là phổ biến nhất. Nhƣợc
điểm chính của R-tree là các hình chữ nhật có thể trùm lên nhau vì vậy mà có
nhiều hơn một cây phụ dƣới một node đƣợc kiểm tra qua trong một lần tìm kiếm.
Điều này có thể là giảm khả năng tìm kiếm. R*-tree giảm thiểu các node trùm nhau
vì vậy cho kết quả tốt hơn.
1.7. Truy vấn ảnh tƣơng tác
Trong thời kỳ đầu phát triển của CBIR, các nghiên cứu chỉ yếu tập trung vào
việc biểu diễn các đặc tính khác nhau để tìm ra cách biểu diễn tốt nhất. Trong các
hệ thống này, ngƣời sử dụng đầu tiên phải lựa chọn một số đặt tính ảnh và sau đó
các định trọng số cho mỗi đặc tính. Ngƣời sử dụng cần phải có kiến thức sâu sắc về
việc biểu diễn các đặc tính mức thấp trong hệ thống truy vấn. Có hai lý do chính
khiến các hệ thống này bị hạn chế: khó khăn khi biểu diễn ngữ nghĩa của ảnh bằng
các đặc tính mức thấp và tính chủ quan của hệ thống thị giác con ngƣời.
Khoảng cách giữa ngữ nghĩa mức cao của ảnh và các đặc tính mức thấp.
Q trình truy vấn trong hệ thống gồm việc tìm kiếm các ảnh phù hợp nhất trong
kho ảnh theo các đặc tính mức thấp đƣợc tính toán từ các ảnh mẫu yêu cầu đầu
vào. Tuy nhiên, ngƣời sử dụng thƣờng mong muốn truy vấn cơ sở dữ liệu dựa trên
ngữ nghĩa của ảnh chẳng hạn nhƣ “tìm kiếm ảnh hồng hơn” chứ khơng phải dựa
25