Đồ án Tra cứu ảnh dựa trên nội dung với phản hồi liên quan sử dụng mô hình học trên đồ thị

Bé GI¸O DôC & §µO T¹O

TR¦êNG §¹I HäC D¢N LËP H¶I PHßNG

-------o0o-------

ĐỒ ÁN TỐT NGHIỆP

Ngành công nghệ thông tin

HẢI PHÕNG 2015

BỘ GIÁO DỤC & ĐÀO TẠO

TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÕNG

-------o0o-------

TRA CỨU ẢNH DỰA TRÊN NỘI DUNG VỚI PHẢN HỒI

LIÊN QUAN SỬ DỤNG MÔ HÌNH HỌC TRÊN ĐỒ THỊ

ĐỒ ÁN TỐT NGHIỆP

Ngành Công nghệ Thông tin

HẢI PHÕNG - 2015

BỘ GIÁO DỤC & ĐÀO TẠO

Tr êng ®¹i häc d©n lËp h¶i phßng

-------o0o-------

TRA CỨU ẢNH DỰA TRÊN NỘI DUNG VỚI PHẢN HỒI

LIÊN QUAN SỬ DỤNG MÔ HÌNH HỌC TRÊN ĐỒ THỊ

ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY

Ngành : Công nghệ Thông tin

Sinh viên thực hiện: PHẠM ANH TOÀN

Giáo viên hƣớng dẫn: NGÔ TRƢỜNG GIANG

Mã sinh viên : 1112101005

H¶i Phßng - 2015

CỘNG HÕA XÃ HỘI CHỦ NGHĨA VIỆT NAM

Độc lập – Tự do – Hạnh phúc

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÕNG

-------o0o-------

nhiÖm vô thiÕt kÕ tèt nghiÖp

M· sè : 1112101005

Sinh viªn : PH¹M ANH TOµN

Ngµnh: C«ng nghÖ Th«ng tin

Líp : CT1501

Tªn ®Ò tµi : TRA CøU ¶NH VíI PH¶N HåI LI£N QUAN Sö DôNG M¤ H×NH

HäC TR£N §å THÞ

nhiÖm vô ®Ò tµi

1. Néi dung vµ c¸c yªu cÇu cÇn gi¶i quyÕt trong nhiÖm vô ®Ò tµi tèt nghiÖp

a. Néi dung:

- Tổng quan về Tra cứu ảnh dựa trên nội dung với phản hồi liên quan

- Tổng quan về mô hình học trên đồ thị.

- Ứng dụng học trên đồ thị cho bài toán tra cứu ảnh.

- Cài đặt chƣơng trình thử nghiệm.

b. C¸c yªu cÇu cÇn gi¶i quyÕt

- Hiểu quy trình của một hệ thống tra cứu ảnh dựa trên nội dung, các phƣơng

pháp cơ bản trong tra cứu ảnh dựa trên nội dung.

- Hiểu đƣợc một số mô hình học dựa trên đồ thị và áp dụng cho cải thiện hiệu

quả tra cứu.

- Cài đặt chƣơng trình thử nghiệm

2. C¸c sè liÖu cÇn thiÕt ®Ó thiÕt kÕ, tÝnh to¸n

3. §Þa ®iÓm thùc tËp

c¸n bé h íng dÉn ®Ò tµi tèt nghiÖp

Ng êi h íng dÉn thø nhÊt :

Hä vµ tªn: ………………………………………………………………………………

Häc hµm, häc vÞ: …………………………………….…………………………………

C¬ quan c«ng t¸c: ……………………………………………………………………..

Néi dung h íng dÉn:

……………………………………………………………………………………………

Ng êi h íng dÉn thø hai:

Hä vµ tªn : ………………………………………………………………………………

Häc hµm, học vị :………………………………………………………………………

C¬ quan c«ng t¸c: ……………………………………………………………………..

Néi dung h íng dÉn:

……………………………………………………………………………………………

§Ò tµi tèt nghiÖp ® îc giao ngµy 06 th¸ng 04 n¨m 2015

Yªu cÇu ph¶i hoµn thµnh tr íc ngµy 11 th¸ng 07 n¨m 2015

§· nhËn nhiÖm vô: §.T.T.N

Sinh viªn

§· nhËn nhiÖm vô: §.T.T.N

C¸n bé h íng dÉn §.T.T.N

Hải Phòng, ngày.…tháng…..năm 2015

HiÖu tr ëng

GS.TS.NG•T TrÇn H÷u NghÞ

PHẦN NHẬN XÉT TÓM TẮT CỦA CÁN BỘ HƢỚNG DẪN

1. Tinh thÇn th¸i ®é cña sinh viªn trong qu¸ tr×nh lµm ®Ò tµi tèt nghiÖp:

...............................................................................................................

2. §¸nh gi¸ chÊt l îng cña ®Ò tµi tèt nghiÖp (so víi néi dung yªu cÇu ®· ®Ò ra trong

nhiÖm vô ®Ò tµi tèt nghiÖp)

...............................................................................................................

3. Cho ®iÓm cña c¸n bé h íng dÉn:

( §iÓm ghi b»ng sè vµ ch÷ )

....................................................................................................................

Ngµy.......th¸ng.........n¨m 2015

C¸n bé h íng dÉn chÝnh

( Ký, ghi râ hä tªn )

PHẦN NHẬN XÉT ĐÁNH GIÁ CỦA CÁN BỘ CHẤM PHẢN BIỆN ĐỀ TÀI

TỐT NGHIỆP

1. Đánh giá chất lƣợng đề tài (về các mặt nhƣ cơ sở lý luận, thuyết minh chƣơng

trình, giá trị thực tế…)

........................................................................................................................

2. Cho ®iÓm cña c¸n bé ph¶n biÖn

( §iÓm ghi b»ng sè vµ ch÷ )

........................................................................................................................

Ngµy.......th¸ng.........n¨m 2015

C¸n bé chÊm ph¶n biÖn

( Ký, ghi râ hä tªn )

Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị

LỜI CẢM ƠN

Em xin chân thành cảm ơn Thầy giáo, Thạc sĩ Ngô Trường Giang đã hướng

dẫn tận tình chỉ bảo em rất nhiều trong suốt quá trình tìm hiểu nghiên cứu và hoàn

thành đồ án này từ lý thuyết đến ứng dụng. Sự hướng dẫn của thầy đã giúp em có

thêm kiến thức về lập trình và kiến thức về lĩnh vực xử lý ảnh. Đồng thời, em xin

chân thành cám ơn các thầy cô trong khoa Công nghệ thông tin – Trường Đại Học

Dân Lập Hải Phòng, cũng như các thầy cô trong trường đã trang bị cho em những

kiến thức cơ bản cần thiết trong suốt thời gian học tập tại trường để em hoàn thành

tốt đồ án này. Em xin chân thành cảm ơn GS.TS.NGƯT Trần Hữu Nghị, Hiệu

trưởng Trường Đại học Dân Lập Hải Phòng, ban giám hiệu nhà trường, khoa Công

nghệ thông tin, các phòng ban nhà trường đã tạo điều kiện tốt nhất trong suốt thời

gian em học tập và làm tốt nghiệp. Trong quá trình học cũng như trong suốt thời

gian làm đồ án tốt nghiệp không tránh khỏi những thiếu sót, em rất mong được sự

góp ý quý báu của các thầy cô cũng như tất cả các bạn để kết quả của em được

hoàn thiện hơn. Sau cùng, em xin gửi lời cảm ơn đến gia đình, bạn bè đã tạo mọi

điều kiện để em xây dựng thành công đồ án này.

Em xin chân thành cảm ơn !

Phạm Anh Toàn – CT1501

1

Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị

MỤC LỤC

MỘT SỐ TỪ VIẾT TẮ T ................................................................................ 4

MỞ ĐẦU .......................................................................................................... 5

CH ƢƠ NG 1: Tổng quan về tra cứu ảnh dựa trên nội dung với

phản hồi liên qua n ........................................................................................... 6

1.1 Khái niệm tra cứu ảnh dựa trên nội dung ............................................. 6

1.2 Những thành phần của một hệ thống tra cứu ảnh dựa trên nội dung .... 6

1.2.1 Các đặc trƣng hình ảnh mức thấp ................................................. 7

1.2.2 Đánh chỉ số .................................................................................... 9

1.2.3 T ƣơ ng tác ng ƣời dùn g ................................................................. 10

1.3 Khoảng cách ngữ nghĩa ...................................................................... 12

1.4 Kỹ thuật phản hồi liên quan trong CBI R ............................................ 13

1.4.1 Khái niệm phản hồi liên quan ..................................................... 13

1.4.2 Kiến trúc tổng quan của hệ thống CBIR với phản hồi liên quan 14

1.4.3 Các ph ƣơng pháp tiếp cận phản hồi liên qua n ............................ 17

1.4.4 Những thách thức trong phản hồi liên quan ................................ 19

1.5 Các lĩnh vực ứng dụng của tra cứu ảnh dựa trên nội dun g ................. 20

CH ƢƠ NG 2: Mô hình học bán giám sát dựa trên đồ thị ..................... 22

2.1 Khái niệm học máy ............................................................................. 22

2.2 Học bán giám sát ................................................................................. 24

2.3 Học bán giám sát dựa trên đồ thị ........................................................ 27

2.3.1 Thuật toán lan truyền nhãn .......................................................... 27

2.3.2 Xây dựng đồ thị ........................................................................... 30

2.3.3 Tr ƣờng ngẫu nhiên Gauss và hàm điều hòa ................................ 30

2.4 Kết hợp học bán giám sát với học chủ động (Active Learning)......... 35

2.5 Học siêu tham số của đồ thị (Graph Hyperparameter Learning)........ 39

2.5.1 Ph ƣơng pháp tối đa Evidence ..................................................... 39

2.5.2 Ph ƣơng pháp tối thiểu Entropy ................................................... 39

CH ƢƠ NG 3: Áp dụng cài đặt thử nghiệm ............................................. 41

3.1 Cài đặt ................................................................................................. 41

Phạm Anh Toàn – CT1501

2

Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị

3.1.1 Nền tảng và ngôn ngữ lập trình ................................................... 41

3.1.2 Các th ƣ viện sử dụng ................................................................... 41

3.1.3 C ơ sở dữ liệu ............................................................................... 41

3.2 Giao diện và các chức năng chính của chƣơ ng trìn h .......................... 42

3.2.1 Giao diện chính ........................................................................... 42

3.2.2 Các chức năng chính của chƣơ ng trình....................................... 42

3.3 Một số kết quả thực nghiệm ................................................................ 44

3.3.1 Kết quả thực nghiệm số 1 ............................................................ 44

3.3.2 Kết quả thực nghiệm số 2 ............................................................ 46

KẾT LUẬ N .................................................................................................... 52

TÀI LIỆU THAM KHẢO ............................................................................ 53

Phạm Anh Toàn – CT1501

3

Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị

MỘT SỐ TỪ VIẾT TẮT

STT

Từ viết tắt

Mô tả

1

2

3

4

5

6

7

CBIR

EM

Content-Based Image Retrieval

Expectation Maximization

Principal Component Analysis

Relevance Feedback

PCA

RF

RGB

SVM

TSVM

Red-Green-Blue

Support Vector Machine

Transductive Support Vector Machine

Phạm Anh Toàn – CT1501

4

Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị

MỞ ĐẦU

Với sự phát triển của Internet cũng nhƣ các thiết bị ghi và lƣu trữ ảnh,

kích thƣớc của các tập ảnh số đƣợc gia tăng một cách nhanh chóng. Hiệu quả

của các công cụ tìm kiếm, tra cứu ảnh đƣợc yêu cầu từ rất nhiều lĩnh vực khác

nhau bao gồm : trinh sát, thời trang, phòng chống tội phạm, xuất bản, kiến

trúc, y tế v.v… Cùng chung mục đích này, rất nhiều các hệ thống tra cứu ảnh

đã đƣợc phát triển. Có hai nền tảng là : dựa trên văn bản (text-based) và dựa

trên nội dung (content-based).

Các phƣơng pháp tiếp cận dựa trên văn bản đƣợc sử dụng từ những năm

1970. Trong đó các ảnh đƣợc chú thích bởi các mô tả văn bản một cách thủ

công, sau đó đƣợc sử dụng bởi các hệ thống quản lý cơ sở dữ liệu để thực

hiện việc tra cứu ảnh. Có hai nhƣợc điểm cho quá trình tra cứu ảnh dựa trên

văn bản. Đầu tiên là yêu cầu về mức lao động đáng kể của con ngƣời cho việc

chú thích thủ công. Thứ hai là vấn đề chú thích không chính xác do nhận thức

chủ quan của con ngƣời. Để khắc phục hai nhƣợc điểm trên của hệ thống tra

cứu ảnh dựa trên văn bản, khái niệm tra cứu ảnh dựa trên nội dung đƣợc giới

thiệu vào đầu những năm 1980.

Đồ án trình bày kỹ thuật tra cứu ảnh dựa trên nội dung sử dụng phản hồi

có liên quan với mô hình học dựa trên đồ thị, Đồ án bao gồm có 3 phần :

Chƣơng 1 : Tổng quan về hệ thống tra cứu ảnh dựa trên nội dung với

phản hồi liên quan.

Chƣơng 2 : Mô hình học bán giám sát dựa trên đồ thị.

Chƣơng 3 : Áp dụng cài đặt chƣơng trình và một số kết quả thực

nghiệm.

Phạm Anh Toàn – CT1501

5

Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị

CHƢƠNG 1: Tổng quan về tra cứu ảnh

dựa trên nội dung với phản hồi liên quan

1.1 Khái niệm tra cứu ảnh dựa trên nội dung

Một hệ thống CBIR đƣợc dùng để tìm kiếm các ảnh số trong một cơ sở

dữ liệu lớn và tra cứu những ảnh liên quan dựa trên nội dung thực tế của nó.

Nội dung có thể ở dạng các đặc trƣng mức thấp hoặc bất kỳ thông tin nào có

đƣợc từ hình ảnh. Trong CBIR, hình ảnh đƣợc trích chọn các đặc trƣng mức

thấp một cách tự động để biểu diễn nội dung trực quan, sau đó hệ thống sử

dụng các véc-tơ đặc trƣng để đánh giá độ tƣơng tự giữa các ảnh.

1.2 Những thành phần của một hệ thống tra cứu ảnh dựa trên nội dung

Một hệ thống tra cứu ảnh đòi hỏi các thành phần nhƣ trong hình 1-1 [5].

Trong đó có ba thành phần quan trọng nhất trong tra cứu ảnh dựa trên nội

dung : trích chọn đặc trƣng, đánh chỉ số và giao diện truy vấn cho ngƣời dùng.

Hình 1-1: Kiến trúc tổng quan về hệ thống tra cứu ảnh dựa trên nội dung

Phạm Anh Toàn – CT1501

6

Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị

Các bƣớc tra cứu ảnh trong CBIR thƣờng bao gồm :

Tiếp nhận truy vấn của ngƣời dùng (dƣới dạng ảnh hoặc phác thảo).

Trích chọn đặc trƣng của truy vấn và lƣu trữ vào cơ sở dữ liệu đặc trƣng

nhƣ là một véc-tơ hoặc không gian đặc trƣng.

So sánh độ tƣơng tự giữa các đặc trƣng trong cơ sở dữ liệu với nhau

từng đôi một.

Lập chỉ mục cho các véc-tơ để nâng hiệu quả tra cứu.

Trả lại kết quả tra cứu cho ngƣời dùng.

1.2.1 Các đặc trƣng hình ảnh mức thấp

Các đặc trƣng của ảnh bao gồm các đặc tính cơ bản và các đặc tính ngữ

nghĩa/logic. Các đặc tính cơ bản đó là: màu sắc (color), hình dạng (shape), kết

cấu (texture), vị trí không gian (spatial location). Chúng có thể đƣợc trích xuất

tự động hoặc bán tự động. Đặc tính logic cung cấp mô tả trừu tƣợng của dữ

liệu hình ảnh ở các cấp độ khác nhau. Thông thƣờng, các đặc tính logic đƣợc

trích chọn bằng tay hoặc bán tự động. Một hoặc nhiều đặc trƣng có thể đƣợc

sử dụng trong ứng dụng cụ thể.

1.2.1.1 Đặc trƣng màu sắc

Đặc trƣng màu sắc là một trong những đặc trƣng đƣợc sử dụng phổ biến

trong tra cứu ảnh. Màu sắc đƣợc định nghĩa trên một không gian màu. Có rất

nhiều không gian màu đã đƣợc xây dựng sẵn, chúng thƣờng đƣợc dùng cho

các ứng dụng khác nhau. Những không gian màu gần gũi hơn với nhận thức

của con ngƣời và đƣợc sử dụng rộng rãi trong CBIR bao gồm RGB, LAB,

LUV, HSV, HSL ... Vào năm 1999, Gevers và cộng sự đã quan tâm đến các

đối tƣợng lấy từ các điểm quan sát khác nhau và sự chiếu sáng. Theo kết quả,

một tập các điểm bất biến đặc trƣng màu đã đƣợc tính toán. Các bất biến màu

đƣợc xây dựng trên cơ sở hue, cặp hue-hue, và ba đặc trƣng màu đƣợc tính

Phạm Anh Toàn – CT1501

7

Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị

toán từ các mô hình đối xứng. Các đặc trƣng màu sắc mặc dù mô tả màu sắc

rất hiệu quả nhƣng không trực tiếp liên quan đến các ngữ nghĩa mức cao.

1.2.1.2 Đặc trƣng kết cấu

Kết cấu không đƣợc định nghĩa đầy đủ nhƣ là đặc trƣng màu sắc, vì thế

mà một số hệ thống không sử dụng đặc trƣng kết cấu. Tuy nhiên, kết cấu cung

cấp các thông tin quan trọng trong việc phân loại ảnh, vì nó mô tả nội dung

của nhiều ảnh thực nhƣ là: vỏ trái cây, mây, cây, gạch ... Do đó, kết cấu là

một đặc trƣng quan trọng trong việc định nghĩa ngữ nghĩa mức cao cho mục

đích tra cứu ảnh [5]. Các đặc trƣng kết cấu thƣờng đƣợc sử dụng trong hệ

thống tra cứu ảnh bao gồm các đặc trƣng phổ, chẳng hạn nhƣ các đặc trƣng

đƣợc bao gồm sử dụng lọc Gabor hoặc biến đổi wavelet, thống kê đặc trƣng

kết cấu trong các cách đo độ thống kê cục bộ, nhƣ sáu đặc trƣng kết cấu

Tamura, và đặc trƣng wold đƣợc đề xuất bởi Liu và các cộng sự vào năm

1996.

1.2.1.3 Đặc trƣng hình dạng

Hình dạng là một khái niệm đƣợc định nghĩa khá tốt. Đặc trƣng hình

dạng của các ứng dụng nói chung bao gồm: tỷ lệ aspect, tuần hoàn, mô tả

Fourier, bất biến thời điểm, phân đoạn đƣờng bao liên tiếp [8], v.v.. Đặc trƣng

hình dạng là đặc trƣng ảnh quan trọng, mặc dù chúng chƣa đƣợc sử dụng rộng

rãi trong CBIR nhƣ là đặc trƣng màu và đặc trƣng kết cấu [5]. Đặc trƣng hình

dạng đã thể hiện tính hữu ích trong nhiều miền ảnh đặc biệt nhƣ là các đối

tƣợng nhân tạo. Ảnh màu đƣợc sử dụng phổ biến trong nhiều tài liệu, tuy

nhiên lại khó khăn để áp dụng đặc trƣng hình dạng so với màu sắc và kết cấu

do sự thiếu chính xác của phân đoạn. Mặc dù gặp khó khăn, đặc trƣng hình

dạng vẫn đƣợc sử dụng trong một số hệ thống và cho thấy tiềm năng trong

RBIR (Region-based image retrieval).

Phạm Anh Toàn – CT1501

8

Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị

1.2.1.4 Đặc trƣng vị trí không gian

Các vùng hoặc đối tƣợng với thuộc tính màu sắc và kết cấu tƣơng tự có

thể đƣợc nhận ra một cách dễ dàng bởi ràng buộc không gian [5]. Ví dụ “bầu

trời” và “biển” có thể có cùng đặc trƣng về màu sắc và kết cấu nhƣng lại có vị

trí không gian trong ảnh khác nhau. Bầu trời thƣờng xuất hiện ở phía trên của

ảnh trong khi biển thƣờng nằm ở dƣới cùng. Đặc trƣng không gian thƣờng

đƣợc định nghĩa một cách đơn giản nhƣ là “trên, dƣới” tùy theo vị trí các

vùng trong ảnh.

Mối quan hệ không gian tƣơng đối là quan trọng hơn vị trí không gian

tuyệt đối. 2D-string và một số biến thể của nó là cấu trúc chung phổ biến để

biểu diễn mối quan hệ về phƣơng hƣớng giữa các đối tƣợng nhƣ là

“trái/phải”, “trên/dƣới”.

1.2.2 Đánh chỉ số

Một vấn đề quan trọng khác trong tra cứu ảnh dựa trên nội dung là đánh

chỉ số và tìm kiếm nhanh ảnh dựa trên đặc trƣng trực quan. Bởi vì, các véc-tơ

đặc trƣng của ảnh có xu hƣớng có số chiều cao và do đó nó không thích hợp

cho các cấu trúc đánh chỉ số truyền thống. Việc giảm số chiều thƣờng xuyên

đƣợc sử dụng trƣớc khi lên kế hoạch đánh chỉ số.

Một trong những công nghệ đƣợc sử dụng phổ biến cho việc giảm số

chiều là phân tích thành phần chính PCA [5]. Nó là một công nghệ tối ƣu

trong việc ánh xạ tuyến tính dữ liệu đầu vào một không gian toạ độ, các trục

đƣợc thẳng hàng để phản ánh các biến thể lớn nhất trong dữ liệu. Hệ thống

QBIC sử dụng PCA để làm giảm véc-tơ đặc trƣng hình dạng có 20 chiều

thành hai hoặc ba chiều. Ngoài công nghệ PCA ra, nhiều nhà nghiên cứu còn

sử dụng biến đổi KL để làm giảm số chiều trong không gian đặc trƣng. Mặc

dù, biến đổi KL có một số thuộc tính hữu dụng nhƣ khả năng xác định vị trí

hầu hết không gian con quan trọng, các thuộc tính đặc trƣng mà quan trọng

Phạm Anh Toàn – CT1501

9

Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị

đối với việc xác định mô hình tƣơng tự có thể bị phá huỷ trong suốt quá trình

giảm các chiều mù. Ngoài hai công nghệ biến đổi PCA và KL, thì mạng nơ-

ron cũng là công cụ hữu ích cho việc giảm số chiều đặc trƣng.

Sau khi đã giảm số chiều thì dữ liệu đa chiều đƣợc đánh chỉ số. Có nhiều

phƣơng pháp tiếp cận bao gồm : R-tree, linear quad-trees, K-d-B tree, grid

files … Hầu hết các phƣơng pháp này cho hiệu quả hợp lý với không gian có

số chiều nhỏ.

1.2.3 Tƣơng tác ngƣời dùng

Đối với tra cứu ảnh dựa trên nội dung, ngƣời dùng tƣơng tác với các hệ

thống tra cứu là rất quan trọng khi các hình thức và thay đổi linh hoạt của truy

vấn chỉ có thể thu đƣợc bằng cách liên hệ với ngƣời sử dụng trong các thủ tục

tra cứu. Giao diện ngƣời dùng trong các hệ thống tra cứu hình ảnh thông

thƣờng bao gồm phần xây dựng truy vấn và phần trình bày kết quả.

1.2.3.1 Xác định truy vấn

Để xác định những loại hình ảnh ngƣời sử dụng muốn lấy từ cơ sở dữ

liệu thì có thể thực hiện bằng nhiều cách. Và những cách thông thƣờng nhất

đƣợc sử dụng là: duyệt qua, truy vấn bởi khái niệm, truy vấn bởi bản phác

thảo, và truy vấn bởi ví dụ.

Duyệt qua là phƣơng pháp duyệt qua toàn bộ cơ sở dữ liệu theo danh

mục các ảnh. Với mục đích này, ảnh trong cơ sở dữ liệu đƣợc phân loại thành

nhiều mục khác nhau theo ngữ nghĩa hoặc nội dung trực quan. Truy vấn bởi

khái niệm là tra cứu ảnh theo mô tả khái niệm liên quan với từng ảnh trong cơ

sở dữ liệu [5].

Truy vấn bởi bản phác thảo và truy vấn bởi ví dụ là vẽ ra một bản phác

thảo hoặc cung cấp một ảnh ví dụ từ những ảnh với độ tƣơng tự đặc trƣng

trực quan sẽ đƣợc trích chọn từ cơ sở dữ liệu.

Phạm Anh Toàn – CT1501

10

Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị

Truy vấn bằng cách phác thảo cho phép ngƣời sử dụng vẽ một bức phác

họa một hình ảnh với một công cụ chỉnh sửa đồ họa cung cấp bởi hệ thống tra

cứu hoặc bằng một số phần mềm khác. Truy vấn có thể đƣợc hình thành bằng

cách vẽ một số đối tƣợng có tính chất nhất định nhƣ màu sắc, kết cấu, hình

dạng, kích thƣớc và vị trí. Trong hầu hết các trƣờng hợp, một bản phác thảo

thô là đủ, các truy vấn có thể đƣợc chọn lọc dựa trên kết quả tra cứu.

Truy vấn bằng ví dụ cho phép ngƣời sử dụng xây dựng một truy vấn

bằng cách cung cấp một hình ảnh ví dụ. Hệ thống chuyển đổi hình ảnh ví dụ

thành một đại diện các đặc trƣng nội bộ. Sau đó những hình ảnh đƣợc lƣu trữ

trong cơ sở dữ liệu với các đặc trƣng tƣơng tự đƣợc tìm kiếm. Truy vấn bằng

ví dụ có thể đƣợc phân chia thành truy vấn bằng ví dụ bên ngoài, nếu hình

ảnh truy vấn không có trong cơ sở dữ liệu, và truy vấn bằng ví dụ bên trong,

nếu ngƣợc lại. Đối với truy vấn bằng hình ảnh bên trong, tất cả các mối quan

hệ giữa các hình ảnh có thể đƣợc tính toán trƣớc. Ƣu điểm chính của truy vấn

bằng ví dụ là ngƣời dùng không cần phải cung cấp một mô tả rõ ràng về mục

tiêu, nó đƣợc tính toán bởi hệ thống. Nó phù hợp cho các ứng dụng mà mục

tiêu là một hình ảnh của cùng một đối tƣợng, hoặc thiết lập các đối tƣợng theo

các điều kiện xem khác nhau. Hầu hết các hệ thống hiện tại cung cấp các truy

vấn hình thức này.

Truy vấn bằng một nhóm ví dụ cho phép ngƣời dùng lựa chọn nhiều

hình ảnh. Sau đó hệ thống sẽ tìm những hình ảnh phù hợp nhất với đặc điểm

chung của nhóm các ví dụ. Bằng cách này, một mục tiêu có thể đƣợc xác định

chính xác hơn bằng cách xác định các biến thể đặc trƣng liên quan và loại bỏ

các biến thể không thích hợp trong các truy vấn. Ngoài ra, các thuộc tính của

nhóm có thể đƣợc chọn lọc bằng cách thêm những mẫu dƣơng. Nhiều hệ

thống phát triển gần đây cung cấp truy vấn bằng cả mẫu dƣơng và mẫu âm.

Phạm Anh Toàn – CT1501

11

Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị

1.2.3.2 Phản hồi liên quan

Khái niệm phản hồi liên quan đã đƣợc giới thiệu trong tra cứu ảnh dựa

trên nội dung từ khái niệm tra cứu thông tin dựa trên văn bản vào năm 1998

và sau đó đã trở thành một kỹ thuật phổ biến cho CBIR để giảm khoảng cách

ngữ nghĩa. Nói chung, phản hồi liên quan nhằm mục đích cải thiện hiệu năng

tra cứu với sự tham gia điều chỉnh của ngƣời dùng trên kết quả tra cứu.

1.3 Khoảng cách ngữ nghĩa

Trở ngại lớn trong tra cứu ảnh trên nội dung đó là khoảng cách ngữ

nghĩa. Con ngƣời có xu hƣớng sử dụng các khái niệm mức cao ví dụ nhƣ từ

khóa, mô tả bằng văn bản để diễn tả các hình ảnh và đo sự tƣơng tự giữa

chúng. Trong khi đó việc trích chọn đặc trƣng một cách tự động sử dụng các

kỹ thuật thị giác máy hầu hết là các đặc trƣng mức thấp (màu sắc, kết cấu,

hình dạng, bố cục không gian…). Nói chung không có một mối liên hệ trực

tiếp nào giữa các khái niệm mức cao và đặc trƣng mức thấp.

Mặc dù đã có rất nhiều thuật toán phức tạp đƣợc thiết kế để mô tả các

đặc trƣng về màu sắc, hình dạng, kết cấu, tuy nhiên những thuật toán này vẫn

không thể mô tả đầy đủ ngữ nghĩa của hình ảnh và có nhiều hạn chế khi làm

việc với một cơ sở dữ liệu lớn [2]. Thí nghiệm rộng rãi trên hệ thống CBIR

cho thấy các nội dung mức thấp thƣờng không mô tả đƣợc các khái niệm ngữ

nghĩa mức cao trong suy nghĩ của ngƣời sử dụng [3]. Do đó, hiệu suất của

CBIR vẫn còn xa sự mong đợi của ngƣời dùng.

Trong [1] Eakins đã đề cập tới ba cấp độ truy vấn trong CBIR :

Cấp độ 1 : Tra cứu bằng các đặc trƣng nguyên thủy nhƣ màu sắc, kết

cấu, hình dạng hoặc vị trí không gian của các yếu tố hình ảnh. Điển

hình là các truy vấn bằng ví dụ, „tìm ảnh giống nhƣ thế này‟

Phạm Anh Toàn – CT1501

12