Một phương pháp phân lớp cho bài toán tìm kiếm ảnh dựa trên thuật toán k-NN

Tạp chí Khoa học Công nghệ và Thực phẩm 20 (4) (2020) 89-101 
89 
MỘT PHƯƠNG PHÁP PHÂN LỚP CHO BÀI TOÁN 
TÌM KIẾM ẢNH DỰA TRÊN THUẬT TOÁN k-NN 
Huỳnh Thị Châu Lan*, Lê Hữu Hà, Nguyễn Hải Yến 
Trường Đại học Công nghiệp Thực phẩm TP.HCM 
*Email: lanhtc@hufi.edu.vn 
Ngày nhận bài: 06/7/2020; Ngày chấp nhận đăng: 27/8/2020 
TÓM TẮT 
Trong bài báo này, một tiếp cận phân lớp dữ liệu được thực hiện nhằm áp dụng cho bài 
toán tìm kiếm ảnh tương tự qua đặc trưng thị giác túi từ BoVW (Bag of Visual Words). Phương 
pháp phân lớp được thực hiện dựa trên thuật toán k-NN (k-Nearest Neighbor) với dữ liệu đầu 
vào là một vectơ đặc trưng của hình ảnh. Từ một tập dữ liệu ảnh ban đầu, chúng tôi xây dựng 
một cấu trúc túi từ thị giác lưu trữ các hình ảnh có đặc trưng tương đồng theo nội dung. Dựa 
trên việc phân lớp một hình ảnh đầu vào theo phương pháp k-NN, một tập các hình ảnh được 
trích xuất từ cấu trúc túi từ thị giác. Trong phương pháp k-NN, ngoài k phần tử láng giềng gần 
nhất thì một bán kính được sử dụng để thống kê các phân lớp của hình ảnh. Mỗi một túi từ 
chứa nhiều hình ảnh tương đồng về nội dung và có nhiều phân lớp ngữ nghĩa khác nhau; đồng 
thời, mỗi túi từ liên kết đến các túi từ khác qua phân lớp ngữ nghĩa đại diện. Thực nghiệm 
được xây dựng trên bộ ảnh COREL (1.000 ảnh) nhằm đánh giá độ chính xác đồng thời so sánh 
với các công trình khác trên cùng bộ dữ liệu. Theo kết quả thực nghiệm, những đề xuất của nhóm 
tác giả là hiệu quả và có thể áp dụng trong các hệ thống đa phương tiện khác nhau. 
Từ khóa: k-NN, phân lớp, túi từ, ảnh tương tự, độ đo tương tự. 
1. GIỚI THIỆU 
Theo số liệu thống kê của tập đoàn dữ liệu quốc tế IDC (International Data Corporation), 
năm 2018 dung lượng dữ liệu toàn cầu khoảng 33 zettabyte (1 zettabyte = 1 nghìn tỷ gigabyte), 
ước tính đến năm 2025 có khoảng 175 zettabyte; trong đó, 90 zettabyte được tạo ra từ các thiết 
bị IoT, 49% dữ liệu được lưu trữ trên môi trường đám mây, gần 30% dữ liệu sẽ được sử dụng 
để xử lý theo thời gian thực [1, 2]. 
Mặt khác, dữ liệu đa phương tiện (văn bản, hình ảnh, âm thanh và video) đã được phát 
triển nhanh chóng trên nhiều hệ thống khác nhau, như: điện thoại thông minh, hệ thống mô 
phỏng đối tượng 2D, 3D, WWW, và các thiết bị viễn thông... Năm 2015, tổng số hình ảnh toàn 
cầu đạt 3,2 nghìn tỷ; năm 2016, có 3,5 triệu hình ảnh được chia sẻ trong mỗi phút và có 2,5 
nghìn tỷ hình ảnh được chia sẻ và lưu trữ trực tuyến. Trong năm 2017, thế giới đã tạo ra 1,2 
nghìn tỷ hình ảnh và tổng số ảnh toàn cầu đến năm 2017 là 4,7 nghìn tỷ; trong đó, các hình 
ảnh được tạo ra từ thiết bị mobile là 90% [3]. Ảnh số đã trở nên thân thuộc với cuộc sống của 
con người và được ứng dụng trong nhiều hệ thống tra cứu thông tin đa phương tiện như Hệ 
thống thông tin bệnh viện (Hospital Information System), Hệ thống thông tin địa lý 
(Geographic Information System), Hệ thống thư viện số (Digital Library System), ứng dụng y 
sinh, trong giáo dục đào tạo, giải trí [4, 5]. 
Kích thước cũng như số lượng ảnh ngày càng tăng nên cần phải có các hệ thống truy vấn 
ảnh trên các thiết bị cũng như trong các hệ thống đa phương tiện. Việc tra cứu ảnh để tìm ra 
Huỳnh Thị Châu Lan, Lê Hữu Hà, Nguyễn Hải Yến 
90 
tập ảnh tương tự và phân loại hình ảnh là một trong những bài toán quan trọng của nhiều hệ 
thống đa phương tiện [6]. 
Việc tra cứu ảnh có nhiều giai đoạn chính, bao gồm: tiền xử lý ảnh, rút trích đặc trưng, 
phân cụm dữ liệu hình ảnh, phân lớp đối tượng, tìm kiếm tập ảnh tương tự [7, 8]. Trong cách 
tiếp cận của nhóm tác giả, kỹ thuật phân lớp k-NN được áp dụng cho bài toán tìm kiếm ảnh 
dựa trên kỹ thuật chọn phần tử láng giềng và các túi từ thị giác BoVW (Bag of Visual Word) 
nhằm giảm chi phí tính toán và tăng tốc độ tìm kiếm hình ảnh. 
Đóng góp của bài báo là: (1) cải tiến thuật toán k-NN nhằm phân lớp dữ liệu để tạo ra 
các phân loại ngữ nghĩa cho hình ảnh, (2) xây dựng cấu trúc túi từ thị giác để tìm kiếm hình 
ảnh tương tự, (3) thiết kế mô hình tìm kiếm ảnh tương tự dựa trên việc kết hợp thuật toán k-
NN và túi từ thị giác BoVW, (4) xây dựng thực nghiệm và minh chứng tính đúng đắn của đề 
xuất trên một bộ dữ liệu ảnh thông dụng. 
Phần còn lại của bài báo gồm: Phần 2 khảo sát và phân tích ưu nhược điểm của các công 
trình liên quan để chứng minh tính khả thi của bài toán phân lớp và tìm kiếm ảnh tương tự; 
Phần 3 trình bày thuật toán phân lớp k-NN và phương pháp tìm kiếm ảnh tương tự dựa trên 
túi từ thị giác; Thực nghiệm được mô tả trong phần 4 và kết quả được đánh giá trên bộ dữ liệu 
ảnh COREL (1.000 ảnh); Phần 5 là kết luận và hướng phát triển tiếp theo. 
2. CÁC CÔNG TRÌNH LIÊN QUAN 
Gần đây, nhiều công trình sử dụng phương pháp phân lớp dựa trên kỹ thuật k-NN nhằm 
thực hiện bài toán phân lớp và tìm kiếm ảnh như: Truy xuất hình ảnh dựa trên nội dung cho 
bài toán nhận dạng nhiều đối tượng trái cây bằng cách sử dụng k-Means và k-NN [9]; Phương 
pháp trích xuất đặc trưng SIFT để mô tả đặc trưng hình ả ... hực hiện bằng cách ánh xạ vào 
từ mã tương ứng trong túi từ. 
Thuật toán CkNN 
Đầu vào: Một ảnh I, tập đặc trưng ảnh F đã được gom thành m cụm C = {<Fi, 
Ii> | i = 1..m}, bán kính 𝜃 
Đầu ra: Lớp ngữ nghĩa S của ảnh I 
Begin 
 Ƙ = ∅ ; 
 fI = ExtractFeature(I); 
 dmin = Min {Euclide (fi, Ii), i = 1..m}. 
 If (!dmin) then 
 S = Classification (fI, Fi); 
 Else 
 Foreach (fi ∈ 𝐹𝑗) do //Fj là các cụm có khoảng cách từ tâm 
đến I là nhỏ nhất 
 If (Euclide(fi, fI) < 𝜃) then 
 Ƙ = Ƙ ∪ {𝑓𝑖}; 
 EndIf 
Một phương pháp phân lớp cho bài toán tìm kiếm ảnh dựa trên thuật toán k-NN 
95 
 EndForeach 
 S = Classification (fI, Ƙ); 
 EndIf 
 Return S; 
End 
Mệnh đề 2: Độ phức tạp của thuật toán CkNN là 𝑂(𝑛 ∗ 𝑚). Với n số phần tử trong tập 
véc-tơ đặc trưng F , m là số cụm. 
Chứng minh: Gọi n là số véc-tơ đặc trưng trong bộ dữ liệu ảnh. Với mỗi véc-tơ đặc trưng 
fI ∈F thuộc bộ dữ liệu, thuật toán tiến hành đo khoảng cách Euclide giữa fI đến m tâm cụm để 
tìm ra phân lớp cho ảnh đầu vào. Vì vậy độ phức tạp là 𝑂(𝑛 ∗ 𝑚). ◼ 
3.3. Mô hình tra cứu ảnh 
Hình 4. Mô hình tra cứu ảnh 
Trong Hình 4, (1) thực hiện gom cụm tập ảnh thu thập từ nguồn internet theo phương 
pháp K-means; (2) kết quả sau khi thực hiện gom cụm là k cụm; (3) xây dựng túi từ dựa vào k 
cụm; (4) với mỗi ảnh trong CSDL, tiến hành rút trích đặc trưng; (5) phân lớp tập vectơ đặc 
trưng; (6) rút trích đặc trưng của ảnh tra cứu; (7) phân lớp ảnh tra cứu này; (8) nhãn kết quả; 
(9) tìm tập ảnh tương tự; (10) dựa vào nhãn kết quả, tìm trong túi từ; (11) trả về túi từ tương 
ứng với nhãn cần tìm; (12) trả về tập ảnh tương tự với ảnh tra cứu đầu vào. 
3.4. Thuật toán tra cứu ảnh 
Đầu tiên chúng tôi xây dựng các túi từ thị giác cho tập dữ liệu ảnh đầu vào dựa trên vec-
tơ đặc trưng và thuật toán K-Means. Với mỗi ảnh truy vấn đầu vào, thuật toán phân lớp k-NN 
được thực hiện để phân lớp ngữ nghĩa. Dựa vào lớp ngữ nghĩa tìm được, danh sách ảnh tương 
tự được trích xuất từ cấu trúc túi từ. Thuật toán tra cứu ảnh (CBIR) được mô tả như sau: 
Huỳnh Thị Châu Lan, Lê Hữu Hà, Nguyễn Hải Yến 
96 
Thuật toán CBIR 
Đầu vào: Vectơ đặc trưng f của ảnh tìm kiếm I, tập véc-tơ đặc trưng F, Túi từ thị giác. 
Đầu ra: Tập ảnh tương tự SI 
Begin 
 SI = ∅ ; 
 S = CkNN (fI ,F,k, 𝜃); 
 Foreach (𝛺𝑖 ∈ 𝛺) do 
 If (𝛺𝑖 . 𝐿𝑎𝑏𝑒𝑙 = 𝑆) Then 
 SI = SI ∪ 𝛺𝑖; 
 EndForeach 
 Return SI ; 
End. 
Mệnh đề 3: Độ phức tạp của thuật toán CBIR là 𝑂(𝑛 ∗ 𝑚 ∗ 𝑘). Với n số phần tử trong 
tập véc-tơ đặc trưng F , m cụm và k túi từ. 
Chứng minh: Với vectơ đặc trưng fI của ảnh đầu vào, hệ thống sử dụng thuật toán CkNN 
tiến hành phân lớp ảnh dựa vào tập véc-tơ đặc trưng F với độ phức tạp 𝑂(𝑛 ∗ 𝑚) (chứng minh 
trên). Sau đó hệ thống duyệt qua k túi từ để tìm kiếm tập ảnh tương tự với ảnh đầu vào. Vì 
vậy, độ phức tạp là 𝑂(𝑛 ∗ 𝑚 ∗ 𝑘). ◼ 
4. THỰC NGHIỆM 
4.1. Mô tả thực nghiệm 
Hệ thống được thử nghiệm trên bộ dữ liệu ảnh COREL (1000 ảnh) (được lấy từ nguồn 
www.corel.com), trong đó bộ ảnh được chia thành 10 phân lớp, gồm các phân lớp đối tượng 
và ảnh phong cảnh: Beach, Bus, Castle, Dinosaur, Elephant, Flower, Horse, Meal, Mountain, 
People. Trong thực nghiệm này, nhóm tác giả sẽ lần lượt truy vấn từng ảnh trên bộ dữ liệu 
COREL và đánh giá hiệu suất phân lớp cũng như thời gian truy vấn ảnh tương tự. 
Thực nghiệm gồm 2 giai đoạn: (1) giai đoạn tiền xử lý rút trích tập các vectơ đặc trưng 
từ bộ dữ liệu ảnh và xây dựng các túi từ bằng thuật toán CBVW; (2) giai đoạn tra cứu và tìm 
tập các ảnh tương tự thông qua kỹ thuật k-NN kết hợp BoVW. Các ứng dụng thực nghiệm 
được xây dựng trên nền tảng dotNET Framework 3.5, ngôn ngữ lập trình C#. Thực nghiệm 
trên máy PC CPU Intel (R) Core i5-2430M CPU @2.40GHz, 4.0 GB RAM, hệ điều hành 
Windows 7 Pro 64 bit. 
Trong Hình 5, các vectơ đặc trưng được trích xuất từ các vùng của ảnh, với các đặc trưng 
này bao gồm vị trí, màu sắc, chu vi đối tượng, diện tích đối tượng. Độ tương tự được thực hiện 
dựa trên khoảng cách trung bình của các vectơ đặc trưng theo từng nhóm đặc tính và được tính 
toán theo độ đo Euclide. Mỗi hình ảnh được phân lớp dựa trên thuật toán k-NN đã được đề 
xuất để tìm ra các tập ảnh tương tự theo phân lớp đó. Hình 6 mô tả một kết quả truy vấn ảnh 
dựa trên kết quả phân lớp của Hình 5, với các hình ảnh trong Hình 6 được trích xuất từ một túi 
từ thị giác bao gồm các hình ảnh tương ứng với các ngữ nghĩa phân lớp ban đầu. 
Một phương pháp phân lớp cho bài toán tìm kiếm ảnh dựa trên thuật toán k-NN 
97 
Hình 5. Giao diện chính ứng dụng phân lớp và tra cứu ảnh 
Hình 6. Một kết quả tra cứu ảnh 
4.2. Đánh giá kết quả thực nghiệm 
Kết quả thực nghiệm được đo đạc trực tiếp từ chương trình dựa trên bộ ảnh kiểm thử theo 
từng phân lớp của bộ ảnh COREL. Sau đó, các giá trị thực nghiệm được thống kê và tính giá 
trị trung bình, trong đó độ chính xác và thời gian truy vấn được mô tả trong Bảng 1 và 2. Kết 
quả thực nghiệm cho thấy phương pháp phân lớp và truy vấn ảnh đạt được độ chính xác cao 
và thực hiện với tốc độ tương đối nhanh; với thời gian thực hiện trung bình thử nghiệm trên 
bộ ảnh COREL là 50,54 ms (milisecond), độ chính xác trung bình là 67,7%. 
Huỳnh Thị Châu Lan, Lê Hữu Hà, Nguyễn Hải Yến 
98 
Bảng 1. Độ chính xác và thời gian thực hiện thuật toán trên bộ ảnh COREL 
Phân lớp ảnh Độ chính xác (%) Thời gian (ms) 
Beach 49 49,98 
Bus 74 62,30 
Castle 56 49,91 
Dinosaur 100 48,65 
Elephant 72 49,05 
Flower 88 49,12 
Horse 95 48,98 
Meal 51 49,30 
Mountain 49 48,56 
People 43 49,63 
Trung bình 67,70 50,54 
Hình 7. Biểu đồ thể hiện độ chính xác trên bộ ảnh COREL 
Hình 8. Biểu đồ thể hiện thời gian thực hiện thuật toán trên bộ ảnh COREL 
0,49
0,74
0,56
1
0,72
0,88
0,95
0,51 0,49
0,43
0
0,2
0,4
0,6
0,8
1
1,2
Độ chính xác (%)
0
10
20
30
40
50
60
70
Thời gian (ms)
Một phương pháp phân lớp cho bài toán tìm kiếm ảnh dựa trên thuật toán k-NN 
99 
Hình 7 và Hình 8 mô tả độ chính xác phân lớp trung bình và thời gian truy vấn theo ms 
(milisecond), trong đó trục ngang của đồ thị mô tả tên phân lớp của bộ ảnh COREL, trục đứng 
của đồ thị lần lượt mô tả độ chính xác và thời gian truy vấn ảnh. 
Qua số liệu về thời gian thực thi và độ chính xác của thuật toán trên bộ dữ liệu COREL 
(Bảng 1, 2) và Hình 3, 4 cho thấy độ chính xác trên bộ Dinosaur, Horse, Flower, Bus khá cao 
(100%, 95%, 88%, 74%), tức là phương pháp truy vấn rất khả thi cho các hình ảnh đối tượng. 
Tuy nhiên, trên các bộ Beach, People, Mountain còn hạn chế, tức là trong các bộ ảnh về phong 
cảnh thì phương pháp truy vấn đã đề xuất cần phải được cải tiến. Thời gian thực thi trung bình 
của thuật toán trên các bộ là khá tốt. 
Bảng 2. So sánh độ chính xác giữa các phương pháp trên bộ dữ liệu CIFAR-10 
Phương pháp Độ chính xác trung bình (MAP) 
Imran M., 2014 [16] 0,5890 
Huneiti A., 2015 [18] 0,5588 
Shrinivasacharya P., 2015 [19] 0,6537 
Phương pháp của chúng tôi 0,6670 
Nhóm nghiên cứu Imran và cộng sự (2014) sử dụng bố cục màu MPEG-7 và kết cấu làm 
cơ sở để trích xuất đặc trưng [16]. Tuy nhiên, việc sử dụng chủ yếu đặc trưng màu sắc để so 
sánh dẫn đến kết quả truy vấn (P@10) chỉ đạt 58,9%. Tại thời điểm truy vấn, hình ảnh không 
được phân lớp, nên những bộ ảnh như Bus, Horse chỉ đạt 34% và 53%, trong khi kết quả của 
chúng tôi là vượt trội hơn nhiều với độ chính xác lần lượt là 74% và 95%. 
Nhóm nghiên cứu của Huneiti và cộng sự (2015) thực hiện phân nhóm hình ảnh dựa trên 
hệ số màu trước khi thực hiện so sánh vectơ đặc trưng kết cấu của hình ảnh truy vấn, do đó 
nhóm ảnh có sự phân biệt về màu sắc rõ ràng như Flower cho độ chính xác khá cao (82,8%), 
trong khi đề xuất của nhóm tác giả có kết quả cho bộ Flower là 88%. Bộ ảnh về Dinosaur có 
màu sắc tương đồng thì việc phân biệt về kết cấu của Huneiti và cộng sự không cho kết quả 
cao (52,6%), và đề xuất trong bài báo này của nhóm tác giả là 100%. Qua đó cho thấy, những 
đề xuất của nhóm tác giả trong bài báo này về việc truy vấn hình ảnh dựa vào phân lớp hình 
ảnh theo túi từ có kết quả tốt hơn nhóm nghiên cứu Huneiti và cộng sự. 
Khi so sánh với các nghiên cứu kể trên cho thấy kết quả nghiên cứu của nhóm tác giả là 
hiệu quả. 
5. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 
Trong bài báo này, nhóm tác giả đã đề xuất một cải tiến thuật toán k-NN và mô hình truy 
vấn ảnh dựa trên túi từ nhằm phân lớp dữ liệu để tạo ra các phân loại ngữ nghĩa cho hình ảnh, 
xây dựng cấu trúc túi từ thị giác để tìm kiếm hình ảnh tương tự. Kết quả thực nghiệm trên bộ 
dữ liệu ảnh COREL được đánh giá và so sánh với các công trình khác trên cùng một tập dữ 
liệu ảnh đã cho thấy phương pháp đề xuất là hiệu quả. Kết quả thực nghiệm cho thấy, thời gian 
truy vấn và độ chính xác phân lớp ảnh của bài toán tìm kiếm ảnh là khả thi. Chúng tôi đã cải 
tiến thuật toán k-NN và kết hợp với mô hình túi từ để giải quyết bài toán là một phương pháp 
hiệu quả và có thể áp dụng được trong các hệ truy vấn ảnh. Hướng cải tiến tiếp theo là nhóm 
tác giả sẽ trích xuất đặc trưng phù hợp với hình ảnh phong cảnh, đồng thời truy vấn ngữ nghĩa 
của các phân lớp hình ảnh trên Ontology để tạo ra các ngữ nghĩa liên quan với các đối tượng 
trên ảnh. 
Huỳnh Thị Châu Lan, Lê Hữu Hà, Nguyễn Hải Yến 
100 
TÀI LIỆU THAM KHẢO 
1. Patrizio A. - IDC: Expect 175 zettabytes of data worldwide, Network World, Dec 3, 2018. 
https://www.networkworld.com/article/3325397/idc-expect-175-zettabytes-of-data-
worldwide-by-2025.html. 
2. David R., John G., John R. - The digitization of the world: from edge to core, 
sponsored by Seagate, IDC Technical Report (2018). 
https://www.seagate.com/as/en/our-story/data-age-2025/. 
3. Deloitte, Photo sharing: trillions and rising, Deloitte Touche Tohmatsu Limited, 
Deloitte Global, 2016. 
4. Muneesawang P., Zhang N., Guan L. - Multimedia database retrieval: Technology 
and applications, Springer, New York Dordrecht London (2014). 
5. Xie X., Cai X., Zhou J., Cao N., Wu Y. - A semantic-based method for visualizing 
large image collections, IEEE Transactions on Visualization and Computer Graphics 
25 (7) (2019) 2362-2377. 
6. Deligiannidis L., Arabnia H.R. - Emerging trends in image processing, computer 
vision, and pattern recognition, Elsevier, USA: Morgan Kaufmann, Waltham, MA 
02451 (2015). 
7. Liu Y., Zhang D., Lu G., Ma W.Y. - A survey of content-based image retrieval with 
high-level semantics, Pattern Recognition Journal 40 (2007) 262 - 283. 
8. Alzu’bi A., Amira A., Ramzan N. - Semantic content-based image retrieval: A 
comprehensive study, J Vis Commun Image Represent 32 (2015) 20-54. 
9. Erwin Fachrurrozi M., Ahmad F., Bahardiansyah R.S., Rachmad A., Anggina P. - 
Content based image retrieval for multi-objects fruits recognition using k-means and 
k-nearest neighbor, 2017 International Conference on Data and Software Engineering 
(ICoDSE), Palembang (2017) 1-6. 
10. Kumar M., Payal C., Naresh K. G. - An efficient content based image retrieval system 
using BayesNet and K-NN, Multimedia Tools and Applications 77 (16) (2018) 
21557-21570. 
11. Shichao K., Lihui C., Xinwei Z., Yigang C., Zhenmin Z. Hengyou W. - A supervised 
learning to index model for approximate nearest neighbor image retrieval, Signal 
Processing: Image Communication 78 (2019) 494-502. 
12. Yanchun M., Wing X., Yongjian L., Shengwu X. - A weighted KNN-based automatic 
image annotation method, Neural Computing and Applications (2019) 1-12. 
13. Alqasemi F. A., Alabbasi H.Q., Sabeha F., Alawadhi A., Kahlid S., Zahary A. - 
Feature selection approach using KNN supervised learning for content-based image 
retrieval, 2019 First International Conference of Intelligent Computing and 
Engineering (ICOICE), Hadhramout, Yemen (2019)1-5. 
14. Zhang H., Serkan K., and Moncef G. - A k-nearest neighbor multilabel ranking 
algorithm with application to content-based image retrieval, 2017 IEEE International 
Conference on Acoustics, Speech and Signal Processing (ICASSP), New Orleans, LA 
(2017) 2587-2591. 
15. Xiaohui S., Zhe L., Jonathan B., Ying W. - Spatially-constrained similarity 
measurefor large-scale object retrieval, IEEE Transactions on Pattern Analysis and 
Machine Intelligence 36 (6) (2013) 1229-1241. 
Một phương pháp phân lớp cho bài toán tìm kiếm ảnh dựa trên thuật toán k-NN 
101 
16. Imran M., Hashim R., Abd Khalid N. E. - Content based image retrieval using MPEG-7 
and histogram, In: Herawan T., Ghazali R., Deris M. (eds.) Recent Advances on 
Soft Computing and Data Mining, Advances in Intelligent Systems and 
Computing 287, Springer International Publishing, Switzerland (2014) 453-465. 
17. Li D., Mooi C.C. - A novel unsupervised 2-stage k-NN re-ranking algorithm for image 
retrieval, IEEE International Symposium on Multimedia (ISM), Miami, FL (2015) 
160-165. 
18. Huneiti A., Daoud M. - Content-based image retrieval using SOM and DWT, Journal 
of software Engineering and Applications 8 (2) (2015) 51-61. 
19. Shrinivasacharya P., Sudhamani M. V. - Content based image retrieval using self 
organizing map, In: Proceedings of the Fourth International Conference on Signal and 
Image Processing (2015) 535-546. 
20. Zhang H., Serkan K., and Moncef G. - A k-nearest neighbor multilabel ranking 
algorithm with application to content-based image retrieval, 2017 IEEE International 
Conference on Acoustics, Speech and Signal Processing (ICASSP), New Orleans, LA 
(2017) 2587-2591. 
21. Shuang J., Lin M., Xuezhi T., Danyang Q. - Bag-of-visual words based improved 
image retrieval algorithm for vision indoor positioning, IEEE 91st Vehicular 
Technology Conference (VTC2020-Spring), Antwerp, Belgium (2020) 1-4. 
ABSTRACT 
A METHOD OF CLASSIFICATION FOR K-NN BASED IMAGE RETRIEVAL 
Huynh Thi Chau Lan*, Le Huu Ha, Nguyen Hai Yen 
Ho Chi Minh City University of Food Industry 
*Email: lanhtc@hufi.edu.vn 
In this paper, a stratified data approach was applied to a similar image search problem 
through a bag vision feature from BoVW (Bag of Visual Words). The classification method is 
based on the k-NN (k-Nearest Neighbor) algorithm with the input data being a feature vector 
of the image. From an initial image data set, we construct a bag of visual words to stores 
images that are substantially similar in content. After classifying the input image by the k-NN 
method, a set of similar images is extracted from BoVW. In the k-NN method, in addition to 
k nearest neighbors, a radius θ is used to statistically classify the image. Each BoVW links to 
other word bags through its representative semantic class. Experiments were built on COREL 
image database (1,000 images) to evaluate the accuracy and compare with other related works 
on the same data set. According to empirical results, our recommendations are effective and 
can be applied in various multimedia systems. 
Keywords: k-NN (k-Nearest Neighbor), classification, bag of words, similar image, similarity 
measure.