Một phương pháp tra cứu ảnh hiệu quả sử dụng phân cụm phổ trong phản hồi liên quan

See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/319236116
MỘT PHƯƠNG PHÁP TRA CỨU ẢNH HIỆU QUẢ SỬ DỤNG PHÂN CỤM PHỔ
TRONG PHẢN HỒI LIÊN QUAN
Article · August 2017
CITATIONS
0
READS
163
8 authors, including:
Some of the authors of this publication are also working on these related projects:
Ngô Quốc Tajo and Phạm Việt Bình View project
Content-based image retrieval View project
Quynh Dao Thi Thuy
Posts and Telecommunications Institute of Technology
4 PUBLICATIONS   2 CITATIONS   
SEE PROFILE
Quynh Nguyen Huu
Electric Power University
34 PUBLICATIONS   65 CITATIONS   
SEE PROFILE
Canh Phuong Van
Electric Power University
4 PUBLICATIONS   2 CITATIONS   
SEE PROFILE
Tao Quoc Ngo
Institute of Information Technology/Vietnamese Academy of Scienc
33 PUBLICATIONS   42 CITATIONS   
SEE PROFILE
All content following this page was uploaded by Quynh Nguyen Huu on 23 August 2017.
The user has requested enhancement of the downloaded file.
Đào Thị Thúy Quỳnh, Nguyễn Hữu Quỳnh, Phương Văn Cảnh, Ngô Quốc Tạo
MỘT PHƯƠNG PHÁP TRA CỨU ẢNH HIỆU QUẢ SỬ DỤNG PHÂN CỤM 
PHỔ TRONG PHẢN HỒI LIÊN QUAN 
Đào Thị Thúy Quỳnh *, Nguyễn Hữu Quỳnh **, Phương Văn Cảnh
**, Ngô Quốc Tạo*** 
*Trường Đại học Khoa học, Đại học Thái Nguyên, 
** Khoa Công nghệ thông tin, Trường Đại học Điện lực, 
** *Viện Công nghệ thông tin, Viện Hàn Lâm Khoa học và Công nghệ Việt Nam, 
quynhdtt@tnus.edu.vn, quynhnh@epu.edu.vn, canhpv@epu.edu.vn, nqtao@ioit.ac.vn 
TÓM TẮT- Nhiều kỹ thuật tra cứu ảnh dựa vào nội dung được thiết kế để lấy ra các ảnh trong một lân cận nào đó của ảnh truy vấn 
và do đó bỏ qua các ảnh liên quan nằm trong toàn bộ không gian đặc trưng. Trong bài báo này, chúng tôi đề xuất một phương pháp 
tra cứu ảnh, gọi là SCRF (spectral clustering in relevant feedback) có ưu điểm là không yêu cầu người dùng phải xây dựng truy 
vấn phức tạp mà vẫn lấy được ảnh nằm rải rác trong toàn bộ không gian đặc trưng. Bên cạnh đó, phương pháp khai thác được đầy 
đủ thông tin tương tự giữa các ảnh phản hồi của người dùng hình thành các cụm liên quan ngữ nghĩa để xây dựng truy vấn đa điểm 
ở lần truy vấn tiếp theo. Hơn nữa, thời gian tra cứu của phương pháp cũng không tăng theo số lượng ảnh phản hồi từ người dùng. 
Chúng tôi cũng cung cấp các kết quả thực nghiệm để minh chứng độ chính xác của phương pháp. 
Từ khóa- Tra cứu ảnh dựa vào nội dung, phản hồi liên quan, truy vấn đa điểm, phân cụm phổ. 
I.GIỚI THIỆU 
Tra cứu ảnh dựa vào nội dung (CBIR-Content Based Image Retrieval) đã nhận được nhiều sự quan tâm trong thập kỷ 
qua, do nhu cầu xử lý hiệu quả lượng dữ liệu đa phương tiện khổng lồ và tăng nhanh chóng. Nhiều hệ thống CBIR đã 
được phát triển, gồm QBIC, Photobook, MARS, NeTra, PicHunter, Blobworld, VisualSEEK, SIMPLIcity và những hệ 
thống khác. Trong một hệ thống CBIR tiêu biểu, các đặc trưng ảnh trực quan mức thấp (tức là màu, kết cấu và hình 
dạng) được trích rút tự động cho mục tiêu đánh chỉ số và mô tả ảnh. Đối với cách tiếp cấn truy vấn bởi mẫu, một ảnh 
truy vấn đưa vào hệ thống sẽ được xử lý tương tự như ảnh cơ sở dữ liệu để sinh ra một véc tơ thích hợp. Tra cứu tiếp 
theo được thực hiện bằng việc sinh ra một danh sách các ảnh được phân hạng theo thứ tự giảm dần của độ đo tương tự 
so với ảnh truy vấn. 
Là một vấn đề quan trọng trong CBIR, độ đo tương tự lượng hóa sự giống nhau về nội dung giữa từng cặp ảnh. Phụ 
thuộc vào kiểu đặc trưng mà chúng ta lựa chọn độ đo tương tự thích hợp. Tất cả các kỹ thuật tra cứu dựa vào nội dung 
hiện nay đều thừa nhận thông tin tương hỗ giữa độ đo tương tự ảnh và ngữ nghĩa của ảnh. Bằng các cách khác nhau, độ 
đo tương tự cố gắng nắm được một khía cạnh nào đó của nội dung ảnh, đó là ngữ nghĩa kế thừa từ độ tương tự hay đặc 
trưng mức thấp. Tuy nhiên, ngữ nghĩa kế thừa từ độ tương tự nhiều khi không giống với khái niệm mức cao được 
truyền tải bởi một ảnh (ngữ nghĩa của ảnh). Đó chính là khoảng cách ngữ nghĩa [7], nó phản ánh sự khác biệt giữa năng 
lực mô tả hạn chế của đặc trưng trực quan mức thấp và khái niệm mức cao. Cách tiếp cận dựa vào phản hồi liên quan 
đối với tra cứu ảnh dựa vào nội dung là một lĩnh vực nghiên cứu tích cực trong mấy năm qua nhằm rút ngắn khoảng 
cách ngữ nghĩa. Một số nghiên cứu tốt theo cách tiếp cận này có thể tìm thấy trong [1; 3; 8; 10; 11; 13; 14; 16]. Hầu hết 
các hệ thống CBIR đã có biểu diễn các ảnh bằng các véc tơ đặc trưng sử dụng các đặc trưng trực quan, trong đó hai véc 
tơ được coi là gần nhau nếu hai ảnh tương ứng với hai véc tơ đó sẽ tương tự nhau hơn. Khi các hệ thống CBIR đưa ra 
một tập các ảnh được xem là tương tự với một ảnh truy vấn đã cho, người dùng có thể lấy ra các ảnh liên quan nhất đối 
với truy vấn đã cho và hệ thống điều chỉnh lại truy vấn sử dụng các ảnh liên quan mà người dùng vừa chọn. Các kỹ 
thuật CBIR dựa vào phản hồi liên quan không yêu cầu người dùng cung cấp các truy vấn khởi tạo chính xác nhưng yêu 
cầu người dùng xây dựng truy vấn lý tưởng thông qua đánh giá các ảnh là liên quan hay không. 
Các cách tiếp cận đối với CBIR giả thiết rằng, về nguyên tắc các ảnh liên quan gần với ảnh truy vấn trong không gian 
đặc trưng nào đó. Tuy nhiên, sự tương tự giữa các ảnh mà con người nhận thức lại có sự khác biệt với khoảng cách 
giữa chúng trong không gian đặc trưng. Tức là, các ảnh liên quan về mặt ngữ nghĩa có thể nằm phân tán trong toàn bộ 
không gian đặc trưng và nằm rải rác ở một số cụm chứ không phải một cụm. Trong trường hợp này, các cách tiếp cận 
phản hồi liên quan truyền thống [1; 3; 5; 8; 10; 11; 14; 16; 18; 19] không làm việc tốt khi dịch chuyển tâm truy vấn. 
Thực hiện phản hồi liên quan đề cập đến việc tính toán một hoặc nhiều điểm truy vấn mới trong không gian đặc trưng 
và thay đổi hàm khoảng cách. Như được chỉ ra trong Hình 1(a), các nghiên cứu theo hướng tiếp cận ban đầu [1; 5; 8; 
16] biểu diễn một truy vấn mới bằng một điểm đơn và thay đổi các trọng số của các thành phần đặc trưng để tìm một 
điểm truy vấn tối ưu và một hàm khoảng cách tối ưu. Trong trường hợp này, một điểm đơn được tính toán sử dụng 
trung bình trọng số của tất cả các ảnh liên quan trong không gian đặc trưng. Các đường viền biểu diễn các đường có độ 
tương tự tương đương. Trong khi đó, một cách tiếp cận nghiên cứu sau đó [7; 20; 21; 22; 24] biểu diễn một truy vấn 
mới bằng nhiều điểm để xác định hình của đường viền như Hình 1(b). Cách tiếp cận này sử dụng một phương pháp 
phân cụm [23] để tính toán các điểm truy vấn mới sử dụng các các kết quả truy vấn (các ảnh liên quan) dựa vào đánh 
giá phản hồi của người dùng. Với giả thiết rằng các ảnh liên quan được ánh xạ sang các điểm gần nhau theo độ đo 
tương tự. Một đường viền rộng được xây dựng để phủ tất cả các điểm truy vấn và hệ thống tìm các ảnh tương tự với 
các truy vấn này. Tuy nhiên, nếu không gian đặc trưng và hàm khoảng cách rất khác so với nhận thức của người dùng, 
các ảnh liên quan được ánh xạ sang các vùng có hình dạng bất kỳ tách rời trong không gian đặc trưng. Tức là, các ảnh 
liên quan có thể được phân hạng dưới các ảnh được tra cứu khác theo một truy vấn đã cho. Để hội tụ nhanh đến nhu 
MỘT PHƯƠNG PHÁP TRA CỨU ẢNH HIỆU QUẢ SỬ DỤNG PHÂN CỤM PHỔ TRONG PHẢN HỒI LIÊN QUAN 
cầu thông tin ở mức ngữ nghĩa cao hơn, hệ thống sẽ tìm các ảnh tương tự với bất kỳ các điểm truy vấn nào như trong 
Hình 1(c). Một truy vấn mà tra cứu các ảnh tương tự với bất kỳ các điểm truy vấn nào được gọi là truy vấn tách rời hay 
truy vấn đa điểm. Đặc biệt, một truy vấn ảnh phức tạp được biểu diễn bằng nhiều vùng tách rời do các ảnh liên quan 
ngữ nghĩa có thể nằm rải rác trong một số vùng trực quan hơn là một vùng. 
Hình 1.1. Hình dạng truy vấn. 
(a) Dịch chuyển điểm truy vấn (b) Hình dạng lồi (đa điểm) (c) Hình dạng lõm (đa điểm) 
Tất cả các kỹ thuật CBIR hiện nay đều chắc chắn thừa nhận thông tin tương hỗ giữa độ đo tương tự và ngữ nghĩa của 
ảnh. Một hệ thống CBIR điển hình xếp hạng các ảnh mục tiêu theo độ đo tương tự đối với ảnh truy vấn nên chỉ lấy 
được các ảnh nằm trong lân cận của ảnh truy vấn và bỏ qua những ảnh liên quan nằm rải rác trong toàn bộ không gian 
đặc trưng. Các hạn chế ở trên là động lực để chúng tôi đề xuất phương pháp cải thiện được sự tương tác người dùng với 
các hệ thống tra cứu ảnh bằng cách khai thác đầy đủ thông tin độ tương tự giữa các ảnh trong tập phản hồi. Bên cạnh 
đó không cần đòi hỏi người dùng phải đưa vào nhiều ảnh truy vấn đa dạng thích hợp để biểu diễn nhu cầu thông tin của 
mình. Thời gian tra cứu cũng không tăng theo số lượng ảnh phản hồi của người dùng. 
Phần còn lại của bài báo này được tổ chức như sau: trong phần 2, trình bày chi tiết phương pháp tra cứu ảnh sử dụng 
phân cụm phổ trong phản hồi liên quan. Phần 3, mô tả các kết quả thực nghiệm và cuối cùng là kết luận được đưa ra 
trong phần 4. 
II. PHƯƠNG PHÁP TRA CỨU ẢNH HIỆU QUẢ SỬ DỤNG PHÂN CỤM PHỔ TRONG PHẢN HỒI LIÊN 
QUAN 
Trong phần này, chúng tôi sẽ giới thiệu chung hệ thống đề xuất. Tiếp theo, chúng tôi mô tả chi tiết từng thành 
phần của hệ thống. Cuối cùng, thuật toán tra cứu đề xuất được trình bày. 
2.1. Mô tả chung về phương pháp 
Hình 2.1. Cấu trúc của phương pháp đề xuất. 
Phương pháp SCRF được mô tả bởi sơ đồ trên hình 2.1., quá trình tra cứu bắt đầu từ việc trích rút đặc trưng của 
ảnh truy vấn. Các đặc trưng của ảnh cơ sở dữ liệu thường được trích rút và lưu trữ thành tập các véc tơ đặc trưng. Sử 
dụng các đặc trưng này với một độ đo tương tự đặc trưng, sự tương đồng giữa ảnh truy vấn và ảnh cơ sở dữ liệu được 
so sánh và phân hạng. Tiếp theo, một tập ảnh lân cận với ảnh truy vấn khởi tạo được trả về cho người dùng. Người 
dùng sẽ chọn những ảnh liên quan tới mong muốn của họ để hình thành lên tập ảnh phản hồi. Một thuật toán phân cụm 
sẽ được áp dụng lên tập ảnh phản hồi để hình thành lên các cụm liên quan ngữ nghĩa. Với mỗi cụm vừa tìm được 
phương pháp của chúng tôi sẽ thực hiện tìm đại diện cho mỗi cụm để hình thành truy vấn đa điểm đưa vào thực hiện tra 
cứu ở lần lặp sau. Quá trình được lặp lại cho đến khi người dùng ngừng phản hồi và phương pháp đưa ra tập kết quả. 
SCRF 
Đào Thị Thúy Quỳnh, Nguyễn Hữu Quỳnh, Phương Văn Cảnh, Ngô Quốc Tạo
2.2. Phương pháp đề xuất 
Phương pháp của chúng tôi thay vì tìm một truy vấn trung tâm cho các mẫu tích cực mà người dùng chọn, 
chúng tôi sẽ thực hiện phân cụm tập ảnh phản hồi của người dùng. Sau khi có được các cụm ngữ nghĩa đó, chúng tôi 
tìm đại diện cho mỗi cụm. Mỗi đại diện đó được dùng để hình thành lên truy vấn đa điểm ở lần lặp tra cứu tiếp theo. 
Phương pháp sẽ tìm các ảnh tương tự với bất kỳ điểm nào hay đại diện nào của truy vấn đa điểm để trả về danh sách 
ảnh đa dạng nằm rải rác trong toàn bộ không gian đặc trưng. 
Thuật toán phân cụm tập ảnh phản hồi từ người dùng 
Trong tập ảnh lân cận được trả về bởi truy vấn khởi tạo người dùng sẽ chọn n ảnh liên quan. Để khai thác thông 
tin tương tự giữa các ảnh trong tập ảnh phản hồi chúng ta gọi thuật toán CRISE để hình thành lên các các cụm ngữ 
nghĩa. Mỗi ảnh được chọn để đại diện cho mỗi cụm phải là ảnh mà tương tự nhất với tất cả các ảnh trong cụm. Các đại 
diện của các cụm sẽ hình thành lên truy vấn đa điểm ở lần lặp tra cứu tiếp theo. Quá trình trên được lặp lại cho đến khi 
người dùng dừng phản hồi. 
Biểu diễn và phân cụm tập ảnh phản hồi 
Dưới một biểu diễn đồ thị, phân cụm có thể được phát biểu tự nhiên như một bài toán phân hoạch đồ thị. Trong 
số nhiều phương pháp phân hoạch đồ thị phổ [4; 15; 9; 17] đã được áp dụng thành công với nhiều lĩnh vực trong thị 
giác máy tính gồm phân tích chuyển động [5], phân đoạn ảnh [9; 17] và nhận dạng đối tượng [15]. Trong bài báo này, 
chúng tôi sử dụng phương pháp sử dụng k véc tơ riêng và tính trực tiếp phân hoạch k-way trong [2]. So với phương 
pháp sử dụng một véc tơ riêng tại một thời điểm và gọi đệ qui [9], phương pháp sử dụng k véc tơ riêng được chỉ ra là 
tốt hơn về mặt thực hành. Nói chung, một phương pháp phân hoạch đồ thị cố gắng tổ chức các nút thành các nhóm sao 
cho độ tương tự trong phạm vi nhóm là cao, và/hoặc độ tương tự giữa các nhóm là thấp. Một đồ thị đã cho G=(V,E) với 
ma trận affinity A, một cách đơn giản để định lượng giá cho các nút phân hoạch thành hai tập rời nhau C1 và C2 
(C1C2= và C1C2=V) là tổng có trọng số của các cạnh mà kết nối hai tập. Tiếp theo, chúng tôi trình bày ngắn gọn 
phương pháp dựa trên nghiên cứu của A. Y. Ng và cộng sự (xem chi tiết hơn tại [2]). 
Đầu tiên, từ n điểm dữ liệu ảnh, phương pháp xây dựng ma trận affinity A theo 𝑎𝑖𝑗 = 𝑒
−‖𝑠𝑖−𝑠𝑗‖
2
2𝜎2 (i ≠ j), aii=0) (1). 
Ở đây tham số tỉ lệ 2 điều khiển mức độ ái lực aij giảm nhanh thế nào với khoảng cách giữa si và sj, phương pháp 
chọn tự động có thể xem trong [2]. Một giá trị aij giữa hai ảnh là “cao” nếu hai ảnh là rất tương tự. 
 Xây dựng ma trận đường chéo D trong đó phần tử (i,i) là tổng hàng thứ i của ma trận A. D là một ma trận chéo 
với 𝐷𝑖𝑖 = ∑ 𝑎𝑖𝑗𝑗=1,,𝑛 . 
Tính ma trận Laplace chuẩn hóa : L = D-1/2 A D-1/2. 
Tìm k véc tơ riêng x1,x2,xk lớn nhất của ma trận L, trong đó x1=(x11, x12, x13, , x1n), x2=(x21, x22, x23, , 
x2n), .xk=(xk1, xk2, xk3, , xkn) và xây dựng ma trận X = [x1T ,x2T ,,xkT ] Є Rn x k , cụ thể: 
 x1T x2T x3T  xkT 
 x11 x21 x31  xk1 
 x12 x22 x32  xk2 
 x13 x23 x33  xk3 
 x1n x2n x3n xkn 
Xây dựng ma trận Y từ X bằng việc chuẩn hóa mỗi dòng của X là chiều dài đơn vị của ma trận Y (Yij = 
Xij
(∑ Xij 
2 )j
1
2
 ) 
y1 y11 y12 y13  y1k 
y2 y21 y22 y32  y2k 
y3 y31 y32 y33  y3k 
yk yn1 yn2 ynk 
MỘT PHƯƠNG PHÁP TRA CỨU ẢNH HIỆU QUẢ SỬ DỤNG PHÂN CỤM PHỔ TRONG PHẢN HỒI LIÊN QUAN 
Mỗi dòng của ma trận Y được xem như là một điểm trong không gian véc tơ k chiều. Đến đây, sẽ có n điểm 
trong không gian Rk, phân cụm (yi)i=1n trong không gian Rk thành k cụm C1,C2,,Ck thông qua K-Means. Cuối cùng, 
gán điểm si tới cụm j nếu và chỉ nếu hàng thứ i của ma trận Y tưởng ứng với cụm j. 
Hình 2 dưới đây là thuật toán phân cụm sử dụng k véc tơ riêng CRISE (Clustering Relevant Images Set using 
Eigenvectors) thực hiện việc phân cụm tập các ảnh liên quan mà người dùng chọn thành k cụm. 
Thuật toán CRISE 
Input: -Tập các ảnh S={s1,s2,,sn} với si Rn 
 - Số cụm k 
Output: k cụm: C1,C2,,Ck 
Bước 1: Xây dựng ma trận affinity 
 for i1 to n do 
 for j1 to n do 
 if (i j) 𝑎𝑖𝑗 exp(
−‖𝑠𝑖−𝑠𝑗‖
2
2𝜎2
) 
 else 𝑎𝑖𝑗0 
Bước 2: Xây dựng ma trận đường chéo và ma trận Laplace L 
 for i1 to n do 
 𝑑𝑖𝑖∑ 𝑎𝑖𝑗𝑗=1,,𝑛 
 L  D-1/2 A D-1/2 
Bước 3: Tìm k véc tơ riêng lớn nhất x1,x2,,xk của ma trận Laplace L 
 for i1 to k do 
 𝑥𝑖𝐿𝑎𝑟𝑔𝑒𝑠𝑡_𝑒𝑖𝑔𝑒𝑛_𝑣𝑒𝑐𝑡𝑜𝑟𝑠(𝐿) 
 X  [x1T ,x2T ,,xkT ] 
Bước 4 : Xây dựng ma trận Y từ X 
 for i1 to n do 
 for j1 to k do 
 yij  xij/ (∑ 𝑥𝑖𝑘
2
𝑘 )
1/2 
 Y  [y1 ,y2 ,,yk ] 
Bước 5: Phân thành k cụm thông qua K-Means 
 𝑃 
 for i1 to n do 
 𝑝𝑖𝑦𝑖 
 𝑃𝑃𝑝𝑖 
 K-Mean(P) 
Bước 6: Gán các si vào các cụm 
 for i1 to n do 
 if 𝑝𝑖 ∈ (𝐶𝑗)𝑖=1,..𝑘 
 𝐶𝑗 ← 𝐶𝑗 ∪ 𝑠𝑖 
 Return C1,C2,,Ck 
Hình 2.2: Thuật toán CRISE. 
Tìm ảnh đại diện cho cụm 
Để thực hiện việc tra cứu ảnh hiệu quả, một ảnh đại diện thích hợp phải thu được cho mỗi cụm. Ở đây, một ảnh 
được chọn là đại diện cho một cụm phải là ảnh mà tương tự nhất với tất cả các ảnh trong cụm. Phát bi ... o G=(V,E) với ma trận affinity A, cho tập 
các cụm ảnh là {C1,C2,,Ck} (tập các cụm này cũng này cũng là một phân hoạch của V, tức là Ci ∩ Cj = ∅, i ≠ 𝑗 và 
⋃ 𝐶𝑖
𝑘
𝑖=1 = 𝑉) thì ảnh đại diện của 𝐶𝑖 là 
𝑎𝑟𝑔 max
𝑗∈𝐶𝑖
∑ 𝑎𝑗∈𝐶𝑖
𝑗𝑡
 (2) 
Như vậy, với một cụm, ảnh đại diện là ảnh mà có tổng độ tương tự trong phạm vi cụm là cực đại. 
Khoảng cách từ một ảnh đến truy vấn đa điểm 
Khác với các phương pháp tra cứu ảnh khác , phương pháp của chúng tôi sẽ hình thành lên truy vấn truy vấn đa 
điểm MQ=(Q1, Q2,..Qk) từ các đại diện của mỗi cụm. Khi đó, khoảng cách từ một ảnh 𝐷𝐼𝑖 đến truy vấn đa điểm 
MQ=(Q1, Q2,..Qk) là cực tiểu của các khoảng cách có trọng số từ một ảnh 𝐷𝐼𝑖 đến mỗi Qj trong truy vấn đa điểm và 
được tính theo công thức (3): 
𝐷(𝐷𝐼𝑖 , 𝑀𝑄) = 𝑚𝑖𝑛𝑗=1..𝑘𝒅𝒊𝒔𝒕(𝐷𝐼𝑖 , 𝑄𝑗) (3) 
Trong công thức (3), 𝒅𝒊𝒔𝒕(𝐷𝐼𝑖 , 𝑄𝑗) với i=1..N, j=1..k là khoảng cách từ một ảnh 𝐷𝐼𝑖 đến một điểm truy vấn Qj 
trong truy vấn đa điểm MQ. 
Thuật toán tra cứu ảnh sử dụng phân cụm phổ trong phản hồi liên quan 
Hình 2.2 dưới đây mô tả Thuật toán tra cứu ảnh hiệu quả sử dụng phân cụm phổ trong phản hồi, có tên SCRF. 
Khi người dùng thực hiện truy vấn, phương pháp sẽ sử dụng thuật toán MQMRBR [12] để tra cứu trên tập các ảnh cơ 
Đào Thị Thúy Quỳnh, Nguyễn Hữu Quỳnh, Phương Văn Cảnh, Ngô Quốc Tạo
sở dữ liệu DI và cho kết quả là tập các ảnh S. Người dùng thực hiện việc chọn tập các ảnh liên quan E trong tập S thông 
qua hàm 𝑼𝒔𝒆𝒓_𝑪𝒉𝒐𝒐𝒔𝒆_𝑹𝒆𝒍𝒆𝒗𝒂𝒏𝒄𝒆𝑰𝒎𝒂𝒈𝒆(), phương pháp sẽ phân cụm tập E này thành k cụm thông qua thuật 
toán CRIES và tìm đại diện cho k cụm đó thông qua hàm 𝑪𝒐𝒎𝒑𝒖𝒕𝒆_𝑹𝒆𝒑𝒓𝒆𝒔𝒆𝒏𝒕𝒂𝒕𝒊𝒗𝒆() và gán cho tập đại diện. 
Khoảng cách giữa ảnh cơ sở dữ liệu DIi và truy vấn đa điểm MQ được tính theo công thức (3). Quá trình này tiếp tục 
cho đến khi người dùng dừng việc chọn các ảnh liên quan. 
Thuật toán tra cứu ảnh hiệu quả sử dụng phân cụm phổ trong phản hồi liên quan 
Input: 
Tập N ảnh cơ sở dữ liệu DI 
Ảnh truy vấn Q 
Ouput: 
Tập ảnh kết quả S’ 
MQMRBR(DI, Q, S) // Thực hiện trên tập ảnh DI với truy vấn Q để cho ra tập kết quả S 
Repeat 
𝐸𝑼𝒔𝒆𝒓_𝑪𝒉𝒐𝒐𝒔𝒆_𝑹𝒆𝒍𝒆𝒗𝒂𝒏𝒄𝒆𝑰𝒎𝒂𝒈𝒆(S, n) // người dùng chọn các ảnh liên quan từ tập ảnh S 
𝐶𝑪𝑹𝑰𝑬𝑺(E, k) // phân tập ảnh liên quan E thành k cụm 
RI𝑪𝒐𝒎𝒑𝒖𝒕𝒆_𝑹𝒆𝒑𝒓𝒆𝒔𝒆𝒏𝒕𝒂𝒕𝒊𝒗𝒆(C, M) 
For i←1 to N do 
For j1 to k do 
Tính disi theo công thức sau : 
𝑑𝑖𝑠𝑖 = 𝑚𝑖𝑛𝑗=1..𝑘𝑑𝑖𝑠𝑖𝑗 
 Sort(DI) // sắp xếp các ảnh trong tập ảnh cơ sở dữ liệu DI theo thứ tự tăng dần của khoảng cách so với 
truy vấn đa điểm MQ. 
Return S’ // danh sách ảnh có khoảng cách nhỏ nhất với MQ 
 Until (User dừng phản hồi) 
Hình 2.3: Thuật toán tra cứu ảnh hiệu quả sử dụng phân cụm phổ trong phản hồi liên quan SCRF. 
3. THỰC NGHIỆM 
3.1. Môi trường thực nghiệm 
Cơ sở dữ liệu ảnh: 
Cơ sở dữ liệu được sử dụng cho thử nghiệm được chúng tôi tổ chức lại từ tập con của Corel Photo Gallery. Tập 
này gồm 80 loại1, ví dụ như là: mùa thu, hàng không, cây cảnh, lâu đài, đám mây, chó, voi, núi băng, linh trưởng, tàu, 
nhũ đá, hỏa tiến, hổ, tàu hỏa, thác nước,. Tất cả các ảnh trong tập ảnh này có tính chất là đều chứa đối tượng tiền 
cảnh nổi bật. Đa số nhóm đều gồm 100 ảnh, có một vài nhóm có hơn 100 hình ảnh. Cỡ của các ảnh có max(chiều rộng, 
chiều cao)=120 và min(chiều rộng, chiều cao)=80. 
Véc tơ đặc trưng: 
Các đặc trưng được chia làm hai loại là: các đặc trưng màu và các đặc trưng kết cấu (xem Bảng 1 ở dưới). 
Bảng 1. Các loại đặc trưng. 
Các loại đặc trưng Tên đặc trưng Độ dài 
Loại đặc trưng màu 
Lược đồ màu hsvHistogram 32 
Tương quan màu color auto correlogram 64 
Gắn kết màu colorMoments 6 
Loại đặc trưng kết 
cấu 
Biến đổi wavelet waveletTransform 40 
gabor Wavelet gaborWavelet 48 
Biểu diễn ảnh: 
Mỗi ảnh được sử dụng biểu diễn bởi năm đặc trưng trực quan gồm ba đặc trưng màu và hai đặc trưng kết cấu. 
Các véc tơ đặc trưng tương ứng với mỗi kênh là một bảng hai chiều gồm 10800 dòng (mỗi dòng chứa một véc tơ đặc 
trưng của ảnh) và 190 cột (độ dài tổng của một véc tơ đặc trưng). 
Tập tin cậy nền (ground truth): 
Tập tin cậy nền Corel được sử dụng rộng rãi trong đánh giá CBIR, do đó chúng tôi cũng sử dụng phân loại 
Corel làm tin cậy nền, tức là chúng tôi xem tất cả các ảnh trong cùng loại Corel là liên quan. Tập tin cậy nền này gồm 3 
cột (có tiêu đề: ID ảnh truy vấn, ID ảnh và Sự liên quan) và gồm 1,981,320 dòng. 
3.2. Chiến lược mô phỏng phản hồi liên quan 
Để bắt chước hành vi của con người, chúng tôi thực hiện mô phỏng phản hồi liên quan trong thử nghiệm. Đầu 
tiên, truy vấn khởi tạo sẽ được thực hiện để tạo ra kết quả truy vấn. Chúng tôi mô phỏng tương tác người dùng bằng 
việc chọn n ảnh liên quan từ kết quả tra cứu khởi tạo dựa vào tập tin cậy nền (ground truth). Những ảnh liên quan từ 
1 https://sites.google.com/site/dctresearch/Home/content-based-image-retrieval (Download lúc 6:32 AM ngày 
25/12/2016) 
MỘT PHƯƠNG PHÁP TRA CỨU ẢNH HIỆU QUẢ SỬ DỤNG PHÂN CỤM PHỔ TRONG PHẢN HỒI LIÊN QUAN 
lần lặp phản hồi đầu tiên sẽ được phân thành k cụm và thực hiện tìm đại diện cho k cụm này. Sau đó k đại diện được 
dùng để xây dựng truy đa điểm phục vụ cho tra cứu tiếp theo. Sau đó những kết quả tra cứu được gộp lại để tạo ra một 
danh sách kết quả tổng hợp theo chiến lược truy vấn đa điểm tách rời. 
Phản hồi liên quan được thực hiện theo chiến lược chọn những ảnh liên quan đầu tiên (dựa vào tập tin cậy nền) 
trong danh sách kết quả. Trong chiến lược này, trường hợp xấu nhất là không có ảnh liên quan nào ngoài ảnh truy vấn 
và trường hợp tốt nhất là có n-1 ảnh liên quan ngoài ảnh truy vấn. Do đó, số lượng ảnh liên quan có thể dao động từ 1 
đến n ảnh (bao gồm cả ảnh truy vấn). Chiến lược này được sử dụng để mô phỏng người dùng thực tế trong thực 
nghiệm của chúng tôi. 
3.3. Thực hiện truy vấn và đánh giá 
Trong thực nghiệm của chúng tôi, các yếu tố đó được lựa chọn như sau: 
Một truy vấn khởi tạo được đưa vào hệ thống, kết quả tương ứng với truy vấn đó được hiển thị cho người dùng. Sau 
đó, người dùng sẽ phản hổi trên danh sách kết quả tương ứng với truy vấn khởi tạo để hình thành danh sách ảnh phản 
hồi. Hệ thống sẽ thực hiện phân cụm danh sách ảnh phản hồi và tìm đại diễn cho mỗi cụm. Đại diện của mỗi cụm sẽ 
xây dựng lên truy vấn đa điểm ở lần lặp truy vấn tiếp theo. Trong pha tính khoảng cách, khoảng cách từ một ảnh trong 
cơ sở dữ liệu đến truy vấn đa điểm là giá trị cực tiểu của các khoảng cách từ ảnh cơ sở dữ liệu tới một đại diện của truy 
vấn đa điểm để lấy được các ảnh nằm rải rác trong toàn bộ không gian đặc trưng. Quá trình sẽ dừng lại khi người dùng 
không tiếp tục phản hồi. Mô hình hệ thống thực hiện quá trình này được thể hiện trên Hình 3.3. 
Hình 3.3. Mô hình hệ thống 
Độ chính xác2 trung bình ở mức 100 ảnh trả về được sử dụng để đánh giá. Bốn thiết lập phản hồi được sử dụng 
để so sánh là 1, 2, 3, 4 số đại diện của một truy vấn đa điểm và một chiến lược phản hồi, do đó sẽ có 4 cấu hình. Ba 
phương pháp khác nhau được sử dụng để so sánh bao gồm Jin&French (phương pháp sử dụng truy vấn tách rời) [6], 
hệ thống ERIN [12] với hệ thống SCRF mà chúng tôi đề xuất. 
Bảng 2. Bảng kết quả của 3 phương pháp số đại diện của truy vấn đa điểm trong một lần phản hồi. 
Phương pháp 
Độ chính xác theo số đại diện của truy vấn đa điểm 
1 2 3 4 
Jin&French 0.24 0.266 0.28 0.29 
ERIN 0.24 0.29 0.31 0.33 
SCRF 0.35168 0.43178 0.48154 0.48278 
Trong Bảng 2, thể hiện độ chính xác trung bình của ba phương pháp là Jin&French, ERIN và phương pháp SCRF 
của chúng tôi tại các mức 1, 2, 3, 4 số đại diện của truy vấn đa điểm với phương pháp của chúng tôi số cụm cũng chính 
là số truy vấn. 
IV. Kết luận 
Chúng tôi đã tập trung vào đề xuất phương pháp, có tên là SCRF, giải quyết hai vấn đề chính đó là: (1) tìm các 
ảnh liên quan ngữ nghĩa nằm rải rác trong toàn bộ không gian đặc trưng với độ chính xác cao và (2) thời gian tra cứu 
không tăng theo số phản hồi của người dùng. Để giải quyết được hai vấn đề này, chúng tôi đã tận dụng sự đánh giá của 
người dùng để hình thành tập ảnh liên quan và phân cụm chúng thành các cụm ngữ nghĩa nằm rải rác trong toàn bộ 
không gian đặc trưng và đại diện của mỗi cụm hình thành lên truy vấn đa điểm. Phương pháp sử dụng một thuật toán 
phân cụm phổ có ưu điểm phân cụm các ảnh được kết nối với nhau nhưng không nhất thiết phải nhóm vào trong một 
đường bao lồi nên thực hiện tốt hơn các thuật toán phân cụm truyền thống. Từ đó có thể tra cứu được các ảnh nằm rải 
rác trong toàn bộ không gian đặc trưng và nâng cao độ chính xác. 
Kết quả thực nghiệm của chúng tôi trên cơ sở dữ liệu đặc trưng gồm 10.800 ảnh đã chỉ ra rằng phương pháp được 
đề xuất SCRF cung cấp một độ chính xác cao hơn hẳn so với các phương pháp Jin&French và phương pháp ERIN. 
2 Độ chính xác là tỉ số giữa số các ảnh liên quan với ảnh truy vấn trong tập kết quả trả về trên tổng số các ảnh trả về. 
Q R 
Phân cụm 
các ảnh 
phản hồi 
Tìm đại 
diện 
Q1 
Q2 
Qk 
Máy tìm 
kiếm Máy 
tìm 
kiếm 
S 
Đào Thị Thúy Quỳnh, Nguyễn Hữu Quỳnh, Phương Văn Cảnh, Ngô Quốc Tạo
Chúng tôi xin chân thành cảm ơn đề tài: “Nghiên cứu phương pháp tra cứu ảnh dựa vào đa truy vấn”, mã số 
PTNTDD17.04 đã hộ trợ. 
TÀI LIỆU THAM KHẢO 
[1] Andre B, Vercauteren T, Buchner AM, Wallace MB, Ayache N (2012). Learning semantic and visual similarity for 
endomicroscopy video retrieval. IEEE Transactions on Medical Imaging. 31(6):1276–88. 
[2] A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: Analysis and algorithm. In Proceedings Of Neural 
Information Processing Systems (NIPS), 2001. 
[3] A.W.M. Smeulders, M. Worring, A. Gupta, R. Jain, Content-based image retrieval at the end of the early years, 
IEEE Trans. Pattern Anal. Mach. Intell. 22 (12) (2000) 1349–1380. 
[4] Bartolini, I., Ciacci, P., Waas, F., (2001). Feedbackbypass: A new approach to interactive similarity query 
processing. In: Proceedings of the 27th VLDB Conference, Roma, Italy, pp. 201–210. 
[5] J. Costeira and T. Kanade,“A multibody factorization method for motion analysis,”inProc. Int. Conf. Computer 
Vision, 1995, pp. 1071–1076. 
[6] Jin, X., & French, J.C, (2005). "Improving Image Retrieval Effectiveness via Multiple Queries," Multimedia Tools 
and Applications, vol. 26, pp. 221-245. 
[7] K. A. Hua, N. Yu, and D. Liu (2006). Query Decomposition: A Multiple Neighborhood Approach to Relevance 
Feedback Processing in Content-based Image Retrieval. InProceedings of the IEEE ICDE Conference. 
[8] Ishikawa, Y., Subramanya, R., Faloutsos, C., (1998). Mind Reader: Querying databases through multiple examples. 
In: Proceedings of the 24th VLDB Conference, New York, USA, pp. 218–227. 
[9] J. Shi and J. Malik,“Normalized cuts and image segmentation,”IEEE Trans. Pattern Anal. Mach. Intell., vol. 22, no. 
8, pp. 888–905, Aug. 2000. 
[10] Norton, D.; Heath, D.; and Ventura, D. (2016). Annotating images with emotional adjectives using features that 
summarize local interest points.IEEE Transactions on Affective Computing, Under Review. 
[11] M. Ortega-Binderberger and S. Mehrotra (2004). Relevance feedback techniques in the MARS image retrieval 
systems. Multimedia Systems, 9(6):535–547. 
[12] Quynh N.H., Quynh D.T.T., Tao N.Q., Dung C.V., Canh P.V., Sơn A.H. (2016). Một phương pháp tra cứu ảnh 
biểu diễn nhu cầu thông tin người dùng hiệu quả, Kỷ yếu hội nghị Quốc gia lần thứ 9 về Nghiên cứu cơ bản và ứng 
dụng trong Công nghệ thông tin (FAIR). 
[13] Rui, Y., Huang, T., Ortega, M., Mehrotra, S., (1998). Relevance feedback: A power tool for interactive content-
based image retrieval. IEEE Transactions on Circuits and Systems for Video Technology 8 (5), pp. 644–655. 
[14] Rui, Y., Huang, T., Chang, S.F., (1999). Image Retrieval: current techniques, promising directions and open 
issues. Journal of Visual Communication and Image Representation 10, 39–62. 
[15] S. Sarkar and P. Soundararajan,“Supervised learning of large percep-tual organization: graph spectral partitioning 
and learning automata,”IEEE Trans. Pattern Anal. Mach. Intell., vol. 22, no. 5, pp. 504–525,May 2000. 
[16] T. Gevers and A. Smeulders (2004). Content-based image retrieval: An overview. In G. Medioni and S. B. Kang, 
editors, Emerging Topics in Computer Vision. Prentice Hall. 
[17] Y. Weiss,“Segmentation using eigenvectors: a unifying view,”inProc. Int. Conf. Computer Vision, 1999, pp. 975–
982. 
[18] Flickner, M., Sawhney, H., Niblack, W., et al., (1995). Query by image and video content: The QBIC system. 
IEEE Computer Magazine 28 (9), 23–32. 
[19] Rocchio, J.J., (1971). Relevance feedback in information retrieval. In: Salton, G. (Ed.), The SMART Retrieval 
System—Experiments in Automatic Document Processing. Prentice Hall, Englewood Cliffs, NJ, pp. 313–323. 
[20] O. Chum, J. Philbin, J. Sivic, M. Isard, and A. Zisserman (2007). Total recall: Automatic query expansion with a 
generative feature model for object retrieval. In Proc. ICCV. 
[21] Porkaew, K., Chakrabarti, K., (1999). Query refinement for multimedia similarity retrieval in MARS. In: 
Proceedings of the 7th ACM Multimedia Conference, Orlando, Florida, pp. 235–238. 
[22] R. Arandjelovi´c and A. Zisserman (2012). Three things everyone should know to improve object retrieval. In 
Proc. CVPR. 
[23] Charikar, M., Chekuri, C., Feder, T., Motwani, R., (1997). Incremental clustering and dynamic information 
retrieval. In: Proceedings of the ACM STOC Conference, pp. 626–635. 
MỘT PHƯƠNG PHÁP TRA CỨU ẢNH HIỆU QUẢ SỬ DỤNG PHÂN CỤM PHỔ TRONG PHẢN HỒI LIÊN QUAN 
[24] Quynh Dao Thi Thuy, Quynh Nguyen Huu, Canh Phuong Van, Tao Ngo Quoc (2017), An efficient semantic – 
Related image retrieval method, Expert Systems with Applications, Volume 72, pp. 30-41. 
AN EFFICIENT IMAGE RETRIEVAL METHOD USING SPECTRAL 
CLUSTERING IN RELEVANT FEEDBACK 
 Nguyen Huu Quynh*, Dao Thi Thuy Quynh**, Phương Văn Cảnh*, Ngo Quoc Tao*** 
*Information Technology Faculty, Electric Power University, 
**Thainguyen University of Science, 
** *Institute of Information Technology, Vietnamese Academy of Science and Technology, 
quynhnh@epu.edu.vn, quynhdtt@tnus.edu.vn, canhpv@epu.edu.vn, nqtao@ioit.ac.vn 
Abstract - Many previous techniques were designed to retrieve images in a certain neighborhood of the query image, 
thus bypassing the related images in the whole feature space. Besides, some designed techniques only care about 
similarity between query image and data image that neglects similarities among data images. In this paper, we propose 
an efficient image retrieval method using spectral clustering in relevant feedback (SCRF) which has advantages that do 
not require the user to provide initial queries correctly but also retrieve relevant images in the entire feature space. In 
addition, our method fully exploit the similarity information of feedback image and contrust multipoints query in next 
query. Furthermore, the retrieval time of our method also is not increase with the number of user feedback. We also 
provide experimental results to demonstrate the effectiveness of our method. 
Keywords- Content based image retrieval, relevant feedback, multiponts query, spectral clustering. 
View publication stats