Một phương pháp gom cụm dữ liệu cho bài toán tìm kiếm ảnh

Tạp chí Khoa học Công nghệ và Thực phẩm 21 (2) (2021) 202-215 
 MỘT PHƯƠNG PHÁP GOM CỤM DỮ LIỆU 
 CHO BÀI TOÁN TÌM KIẾM ẢNH 
 Nguyễn Thị Thuỳ Trang, Trần Như Ý 
 Huỳnh Thị Châu Lan, Phan Thị Ngọc Mai* 
 Trường Đại học Công nghiệp Thực phẩm TP.HCM 
 *Email: maiptn@hufi.edu.vn 
 Ngày nhận bài: 05/3/2021; Ngày chấp nhận đăng: 24/5/2021 
 TÓM TẮT 
 Trong bài báo này, một cải tiến thuật toán K-Means được đề xuất nhằm phân cụm dữ 
liệu và áp dụng cho bài toán tìm kiếm ảnh tương tự theo nội dung. Để thực hiện được điều 
này, chúng tôi sử dụng một giá trị ngưỡng đo độ tương tự giữa các đối tượng dữ liệu, ngưỡng 
này được kí hiệu là 휃. Trên cơ sở ngưỡng 휃, thuật toán K-Means được cải tiến bằng cách 
không xác định trước số tâm cụm, số cụm dữ liệu tăng trưởng theo sự gia tăng của số lượng 
hình ảnh. Đặc trưng của hình ảnh được trích xuất dưới dạng một véc-tơ có n chiều và là dữ 
liệu đầu vào cho thuật toán K-Means đã được cải tiến để từ đó tìm kiếm các hình ảnh tương 
tự. Nhằm minh chứng cho các đề xuất, chúng tôi thực nghiệm và đánh giá kết quả trên tập dữ 
liệu ảnh COREL (có 1000 ảnh) đồng thời so sánh với các công trình khác đã được công bố 
gần đây trên cùng bộ dữ liệu. Theo như kết quả thực nghiệm, những đề xuất của chúng tôi là 
khả thi và có thể ứng dụng cho các hệ thống tìm kiếm ảnh khác nhau. 
Từ khoá: Phân cụm, K-Means, độ đo tương tự, ảnh tương tự. 
 1. GIỚI THIỆU 
 Trong những năm gần đây, nhiều hệ thống tìm kiếm đã được công bố nhằm giải quyết 
 bài toán tìm kiếm ảnh tương tự trong các cơ sở dữ liệu đa phương tiện. Có nhiều lĩnh vực 
 khác nhau áp dụng kỹ thuật tìm kiếm ảnh như y tế, thời trang, hệ thống giám sát đối tượng, 
 hệ thống thông tin địa lý, thư viện số... [1, 2], nhiều hệ thống tra cứu ảnh dựa trên nội dung 
 CBIR (Content-Based Image Retrieval) đã được giới thiệu [3, 4]. 
 Một số công trình tìm kiếm ảnh đã được công bố như: tìm kiếm ảnh dựa trên thuật toán 
 K-Means [5], tìm kiếm ảnh dựa trên hình dạng, màu sắc, cấu trúc, đối tượng đặc trưng [6, 7]. 
 Các công trình đã khảo sát tập trung vào kỹ thuật trích xuất đặc trưng, kỹ thuật đối sánh và 
 tìm kiếm dựa trên các đặc trưng nên các phương pháp này rất tốn kém nhiều chi phí về 
 thời gian và bộ nhớ để đối sánh hai đối tượng hình ảnh, cần có một phương pháp tra cứu 
 hình ảnh tương tự dựa trên một dữ liệu trung gian để từ đó truy hồi hình ảnh. Mặt khác, việc 
 tìm kiếm dữ liệu trung gian cần sử dụng các phương pháp khai phá dữ liệu để tìm ra tập dữ 
 liệu đại diện cho hình ảnh. Trong đó, phương pháp phân cụm là một trong những kỹ thuật 
 quan trọng trong khai thác dữ liệu và đã được ứng dụng trong nhiều hệ thống tìm kiếm ảnh 
 đã được phát triển cho các cơ sở dữ liệu lớn, một thuật toán tiêu biểu trong phân cụm phân 
 hoạch là K-Means [8]. 
 Tuy nhiên, kết quả phân cụm thu được từ thuật toán K-Means phụ thuộc nhiều vào 
 việc khởi tạo số lượng cụm ban đầu, điều này ảnh hưởng đến độ chính xác của quá trình 
 phân cụm, nghĩa là phụ thuộc vào số lượng tâm cụm đã được chọn ban đầu. Ngoài ra, nếu 
 202 
Một phương pháp gom cụm dữ liệu cho bài toán tìm kiếm ảnh 
 bổ sung phần tử mới vào cụm thì thuật toán K-Means cần phải được xác định lại tâm cụm 
 mới, điều này làm cho tốn nhiều chi phí trong quá trình thực thi. Bên cạnh đó, nếu dữ liệu 
 tăng trưởng ngày càng lớn thì việc xác định trước số lượng tâm cụm ban đầu là không phù 
 hợp bởi vì có thể dẫn đến hai phần tử trong cùng một cụm có khoảng cách khá lớn [9]. Do 
 đó, trong bài báo này, nhóm tác giả đã cải tiến thuật toán K-Means và áp dụng cho bài toán 
 tìm kiếm ảnh tương tự theo nội dung. Trong cải tiến này, số lượng tâm cụm không cần phải 
 xác định trước mà tăng dần khi thỏa một điều kiện cho trước và theo sự tăng trưởng của bộ 
 dữ liệu. 
 Trong bài báo này, chúng tôi sử dụng một giá trị ngưỡng 휃 để đánh giá độ tương tự 
 giữa các đối tượng dữ liệu. Thuật toán K-Means được cải tiến bằng cách không cần xác định 
 trước số tâm cụm và số cụm dữ liệu tăng trưởng theo sự gia tăng của số lượng hình ảnh. 
 Trên cơ sở này, chúng tôi áp dụng thuật toán K-Means cải tiến để phân cụm các dữ liệu của 
 hình ảnh để thực hiện bài toán tìm kiếm ảnh tương tự theo nội dung. Ngoài ra, chúng tôi đề 
 xuất mô hình thực nghiệm và xây dựng ứng dụng thực nghiệm trên bộ ảnh COREL để đánh 
 giá độ chính xác và tính khả thi cho những đề xuất. 
 Đóng góp của bài báo bao gồm: (1) Xây dựng một phương pháp gom cụm cải tiến dựa 
 trên K-Means nhằm tạo ra một mô hình phân loại dữ liệu cũng như giúp quá trình tìm kiếm 
 được hiệu quả về tốc độ và độ chính xác; (2) Xây dựng mô hình tìm kiếm ảnh tương tự theo 
 nội dung dựa trên thuật toán K-Means cải tiến; (3) Xây dựng mô hình thực nghiệm và thực 
 thi trên một bộ dữ liệu phổ dụng nhằm minh chứng tính đúng đắn của lý thuyết đề xuất. 
 2. CÁC CÔNG TRÌNH LIÊN QUAN 
 Nhiều công trình sử dụng phương pháp gom cụm dựa trên K-Means nhằm thực hiện bài 
toán tìm kiếm ảnh đã được công bố gần đây như: Sử dụng thuật toán ... ính cụm 푡 
 EndIf; 
 207 
Nguyễn Thị Thùy Trang, Trần Như Ý, Huỳnh Thị Châu Lan, Phan Thị Ngọc Mai 
 Else //Tạo cụm mới có tâm là 푣푖 
 = 푣푖; 
 푅 = 휃; 
  =  ∪ Ck; 
 EndIf; 
 EndIf; 
 EndFor; 
 Return ; 
End. 
 Mệnh đề 1. Thuật toán CTIR có độ phức tạp (푛 ∗ ), với 푛, lần lượt là bộ dữ liệu 
và số cụm tạo ra. 
 Chứng minh: Giả sử có 푛 phần tử trong bộ dữ liệu được phân thành cụm. Thuật 
toán cần phải duyệt qua 푛 phần tử dữ liệu, với mỗi phần tử cần phải duyệt qua cụm để 
phân bố dữ liệu. Trong trường hợp xấu nhất, thuật toán CTIR có số lần duyệt là 푛 ∗ để 
phân bố các phần tử vào các cụm. Khi số phần tử dữ liệu lớn, giá trị 푛 và rất lớn thì độ 
phức tạp của thuật toán CTIR là (푛 ∗ ) 
3.3. Thuật toán tìm kiếm ảnh 
 Trên cơ sở tập các cụm  đã được phân hoạch theo thuật toán CTIR, quá trình tìm 
kiếm ảnh được thực hiện bằng cách chọn ra cụm Cm có tâm gần nhất với ảnh tra cứu. Tuy 
nhiên, chúng tôi chọn thêm các cụm láng giềng của Cm dựa trên độ đo giữa các tâm cụm để 
tăng số lượng kết quả ảnh tra cứu. Khi đó các bước thuật toán tìm kiếm ảnh như sau: 
 − Bước 1: Tìm cụm Cm có tâm gần với véc-tơ ảnh tra cứu nhất. 
 − Bước 2: Tìm h cụm láng giềng với cụm Cm. Tập ¥ chứa h cụm láng giềng và 
 cụm Cm. 
 − Bước 3: Tìm tập £ chứa tất cả các véc-tơ trong ¥. 
 − Bước 4: Sắp xếp £ tăng dần theo độ đo. 
 Thuật toán SEIR: 
 − Đầu vào: véc-tơ đặc trưng p (ảnh tìm kiếm), tập cụm  và ngưỡng tìm kiếm 휎. 
 − Đầu ra: tập  chứa các id (định danh) của các ảnh tương tự với ảnh tìm kiếm. 
 Function ClusterRetrieval( p ,  , 휎 ) 
 Begin 
 Khởi tạo  = ; 
 Tìm cụm Ck  :  (p ,vk ) = min{  (p,vi ), i= 1, ... , m}; 
 (với m là số lượng cụm, vi là véc-tơ tâm của cụm Ci ) 
 //Tìm h cụm láng giềng với Ck 
 Sắp xếp  tăng dần theo  ( vt,vk ) - (Ct.R+Ck.R) 
 (với Ct, vt là cụm và tâm của cụm thứ t, t=1, ... , m) 
 Khởi tạo £=∅; 
 208 
Một phương pháp gom cụm dữ liệu cho bài toán tìm kiếm ảnh 
 If ( (vi,vk) - (Ci.R + Ck.R)<휎) then 
 £= £ ∪Ci với i=0,..m-1. 
 EndIf 
 Sắp xếp tập £ theo  (l ,p ) với ∀l ∈ £ 
 Tạo tập định danh hình ảnh  theo thứ tự sắp xếp của tập £. 
 Return  ; 
 End. 
 Mệnh đề 2. Thuật toán SEIR có độ phức tạp ( ^2), với là số cụm tạo ra. 
 Chứng minh: Giả sử tập cụm đầu vào cho thuật toán SEIR có cụm, khi đó thuật toán 
thực hiện việc tìm cụm gần nhất đối với ảnh đầu vào. Quá trình tìm kiếm này cần duyệt qua 
từng cụm, nghĩa là số lần so sánh là tương ứng với cụm. Sau khi thực hiện tìm cụm gần 
nhất với ảnh láng giềng, thuật toán SEIR tìm các cụm lân cận bằng cách sắp xếp lại tập cụm 
theo độ tương tự của cụm đã tìm được, số phép toán tối đa trong việc sắp xếp này là 
 ( ^2). Sau khi thực hiện tìm kiếm các cụm láng giềng, thuật toán thực hiện việc sắp xếp 
các hình ảnh theo độ đo tương tự với ảnh đầu vào (tuy nhiên việc sắp xếp này có thể xử lý 
bên ngoài thuật toán nên độ phức tạp thuật toán SEIR có thể không bao gồm việc sắp xếp 
các hình ảnh theo độ đo tương tự). Vì vậy, độ phức tạp của thuật toán SEIR là ( ^2). 
 4. MÔ HÌNH TÌM KIẾM ẢNH 
4.1. Mô tả mô hình 
 Hình 3. Mô hình của hệ thống tìm kiếm ảnh 
 Trong Hình 3 mô tả 2 giai đoạn được xử lý bao gồm: tiền xử lý để tạo dữ liệu cụm và 
tìm kiếm tập ảnh tương tự. 
4.1.1. Tiền xử lý 
 − Bước 1: tạo véc-tơ đặc trưng thị giác cho mỗi hình ảnh trong tập dữ liệu ảnh. 
 − Bước 2: gom cụm các véc-tơ theo độ đo tương tự dựa trên thuật toán đã đề xuất. 
 209 
Nguyễn Thị Thùy Trang, Trần Như Ý, Huỳnh Thị Châu Lan, Phan Thị Ngọc Mai 
4.1.2. Tìm kiếm ảnh tương tự 
 − Bước 1: từ một ảnh truy vấn, tạo véc-tơ đặc trưng cho ảnh này. 
 − Bước 2: thực hiện tìm kiếm một cụm gần nhất với ảnh truy vấn. 
 − Bước 3: kết xuất các ảnh kết quả sắp xếp theo độ đo tương tự với ảnh truy vấn. 
4.2. Ví dụ thực nghiệm 
 Giả sử, bộ dữ liệu ảnh ban đầu gồm 17 ảnh biểu diễn bằng tập L gồm 17 véc-tơ đặc trưng. 
Chúng tôi tiến hành phân cụm bằng thuật toán cải tiến từ K-Means với ngưỡng 휃 = 0,2. Kết quả 
sau khi phân cụm: số cụm thu được là 4 cụm như Hình 4. 
 Kết qu ả 
 Hình 4. Tập véc-tơ đặc trưng của 17 ảnh và kết quả phân cụm từ tập véc-tơ đặc trưng ban đầu 
 5. THỰC NGHIỆM 
5.1. Môi trường thực nghiệm 
 Thực nghiệm gồm: (1) Giai đoạn tiền xử lý nhằm tạo ra tập véc-tơ đặc trưng cho tập dữ 
liệu hình ảnh; (2) gom cụm tập các véc-tơ dựa trên thuật toán đã được đề xuất; (3) tìm kiếm 
ảnh tương tự với một ảnh cho trước. Tất cả các ứng dụng thực nghiệm được xây dựng trên 
nền tảng dotNET Framework 4.5, ngôn ngữ lập trình C#. Các đồ thị được xây dựng trên 
Mathlab 2015. Cấu hình máy tính thực nghiệm: Core i3-7100U CPU @2.40GHz,8.0 GB 
RAM, hệ điều hành Windows 10 Pro 64 bit. 
5.2. Ứng dụng thực nghiệm 
 Trong bài báo này, chúng tôi tiến hành thực nghiệm trên bộ ảnh COREL có 1000 ảnh, 
kích thước 30.3 MB được chia thành 10 chủ đề: beach, bus, castle, dinosaur, elephant, 
flower, horse, meal, mountain, peoples. Hệ thống giúp truy vấn ảnh, với mỗi hình ảnh truy 
vấn sẽ được trích lọc trên tập dữ liệu ảnh COREL và tìm ra các hình ảnh có độ tương tự 
nhiều nhất với hình ảnh truy vấn như Hình 5. 
 210 
Một phương pháp gom cụm dữ liệu cho bài toán tìm kiếm ảnh 
 Hình 5. Một kết quả mẫu về truy vấn ảnh tương tự 
5.3. Kết quả thực nghiệm 
 Mỗi đường cong trên đồ thị (hình 6) mô tả kết quả truy vấn độ chính xác (precision) và 
độ phủ (recall) tương ứng với từng tập dữ liệu ảnh theo phân lớp trong bộ dữ liệu COREL. 
Đồng thời, đường cong tương ứng trong đồ thị ROC cho biết tỷ lệ kết quả truy vấn đúng và 
sai, nghĩa là diện tích dưới đường cong này đánh giá được tính đúng đắn của các kết quả truy 
vấn. 
 Hình 6. Precision-Recall và đường cong ROC trên tập ảnh COREL 
 211 
Nguyễn Thị Thùy Trang, Trần Như Ý, Huỳnh Thị Châu Lan, Phan Thị Ngọc Mai 
 Hình 7. Giá trị trung bình của Precision, Recall, F-measure của tập dữ liệu COREL 
 Hình 8. Thời gian truy vấn trung bình (milliseconds) trên bộ ảnh COREL 
 Các giá trị về hiệu suất, thời gian tìm kiếm theo từng chủ đề và đánh giá so sánh cũng 
được trình bày cụ thể trong Bảng 2, 3 và 4. Theo như kết quả thực nghiệm trong các bảng 
này, phương pháp đề xuất của chúng tôi cho bài toán tìm kiếm ảnh tương tự là hiệu quả với 
độ chính xác trung bình là 71,70%. 
 Bảng 2. Bảng mô tả hiệu suất truy vấn trên các phân lớp của bộ ảnh COREL 
 Phân lớp ảnh Ave. Precision Ave.Recall Ave.F-measure 
 Beach 0,618961457 0,48 0,540695031 
 Bus 0,782222222 0,7392 0,760102828 
 Castle 0,616233333 0,5282 0,568830769 
 Dinosaur 0,9944509 0,902225 0,946095707 
 Elephant 0,541933333 0,4434 0,48774 
 Flower 0,748883333 0,6419 0,691276923 
 Horse 0,871888889 0,7847 0,826 
 Meal 0,662222222 0,596 0,627368421 
 Mountain 0,584888889 0,5264 0,554105263 
 People 0,748444444 0,6736 0,709052632 
 212 
Một phương pháp gom cụm dữ liệu cho bài toán tìm kiếm ảnh 
 Bảng 3. Bảng mô tả thời gian truy vấn trung bình trên bộ ảnh COREL 
 Phân lớp ảnh Ave.time (milliseconds) 
 Beach 1,540088 
 Bus 1,640091 
 Castle 1,800112 
 Dinosaur 0,380025 
 Elephant 1,330072 
 Flower 1,7301 
 Horse 1,620093 
 Meal 1,490086 
 Mountain 1,8481034 
 People 1,670093 
 Bảng 4. Giá trị hiệu suất, thời gian truy vấn trung bình trên bộ ảnh COREL 
 Ave. Precision Ave.Recall Ave.F-measure Ave.Time (milliseconds) 
 0,717012902 0,6315625 0,671126757 1,50488634 
 Kết quả thực nghiệm cho thấy, thuật toán CTIR thực hiện gom cụm theo ngưỡng  đã 
xây dựng được chương trình tìm kiếm ảnh hiệu quả, nghĩa là thời gian tìm kiếm nhanh và có 
độ chính xác cao. Để minh chứng cho mô hình truy vấn ảnh được đề xuất là hiệu quả, chúng 
tôi so sánh kết quả thực nghiệm với một số công trình gần đây trên cùng bộ dữ liệu trong 
Bảng 5. 
 Bảng 5. So sánh hiệu suất truy vấn giữa các phương pháp trên bộ dữ liệu COREL 
 Phương pháp Ave. Precision 
 A. Huneiti, 2015 [3] 55,88% 
 Bella M. I. T., 2019 [4] 60,90% 
 Phương pháp đề xuất 71,70% 
 Kết quả thực nghiệm cho thấy, phương pháp của chúng tôi đề xuất có độ chính xác 
trung bình là 71,7% và thời gian tìm kiếm trung bình là 1,5 milli giây. So sánh kết quả này 
với các phương pháp khác trên cùng một bộ dữ liệu mẫu thì thấy phương pháp tra cứu ảnh 
của chúng tôi đề xuất có độ chính xác cao hơn hai phương pháp: A. Huneiti (2015) với độ 
chính xác là 55,88% [3] và Bella M.I.T (2019) với độ chính xác là 60,90% [4]. Thuật toán 
K-Means được cải tiến bằng cách không xác định trước số tâm cụm, vì vậy khi tăng số lượng 
phần tử ảnh thì số cụm sẽ tăng trưởng theo thay vì phải gom cụm lại từ đầu như thuật toán 
K-Means, giúp giảm thời gian của quá trình gom cụm. Tuy nhiên, khi xuất hiện các cụm có 
quá nhiều phần tử sẽ ảnh hưởng đến độ chính xác trong quá trình truy vấn. Chẳng hạn, phân 
lớp Elephant có độ chính xác truy vấn tương đối thấp (48,77%). 
 6. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 
 Bài báo đã đề xuất một cải tiến thuật toán K-Means thực hiện gom cụm nhằm tăng hiệu 
suất tìm kiếm ảnh tương tự. Trên cơ sở lý thuyết đã được đề xuất, nhóm tác giả xây dựng hệ 
 213 
Nguyễn Thị Thùy Trang, Trần Như Ý, Huỳnh Thị Châu Lan, Phan Thị Ngọc Mai 
truy vấn ảnh theo nội dung. 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ả. Trên cơ sở ngưỡng 휃, thuật toán K-Means được cải tiến bằng cách không 
xác định trước số tâm cụm. Vì vậy, số cụm dữ liệu tăng trưởng theo sự gia tăng của số lượng 
hình ảnh đã giảm được đáng kể thời gian của quá trình gom cụm so với thuật toán K-Means. 
Tuy nhiên, việc này dẫn đến xuất hiện các cụm có quá nhiều phần tử, ảnh hưởng đến độ 
chính xác của hệ thống. Hướng phát triển tiếp theo của nghiên cứu là xây dựng thuật tách 
cụm lớn thành 2 cụm nhỏ nhằm đảm bảo các phần tử trong cùng một cụm phải tương tự 
nhau. 
Lời cảm ơn: Nhóm tác giả chân thành cảm ơn Trường Đại học Sư phạm TP. HCM, Trường 
Đại học Công nghiệp Thực phẩm TP. HCM là những nơi bảo trợ cho nghiên cứu này. Chúng 
tôi trân trọng cảm ơn nhóm nghiên cứu SBIR-HCM đã hỗ trợ về chuyên môn giúp chúng tôi 
hoàn thành bài nghiên cứu này. 
 TÀI LIỆU THAM KHẢO 
 1. Muneesawang P., Zhang N., Guan L. - Multimedia database retrieval: Technology 
 and applications, Graduate Texts in Mathematics, Springer, New York Dordrecht 
 London (2014). 
 2. 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) (2018) 2362-2377. 
 3. Huneiti A., Daoud M. - Content-based image retrieval using SOM and DWT, Journal 
 of software Engineering and Applications 8 (02) (2015) 51. 
 4. Bella M. I. T., & Vasuki A. - An efficient image retrieval framework using fused 
 information feature, Computers & Electrical Engineering 75 (2019) 46-60. 
 5. Lin C.-H., Chen C.-C., Lee H.-L., Liao J.-R. - Fast K-means algorithm based on a 
 level histogram for image retrieval, Expert Systems with Applications 41 (7) (2014) 
 3276-3283. 
 6. Kim S., Park S., Kim M. - Central object extraction for object-based image retrieval, 
 In: Bakker E.M., Lew M.S., Huang T.S., Sebe N., Zhou X.S. (eds) Image and Video 
 Retrieval, CIVR 2003, Lecture Notes in Computer Science 2728, Springer (2003) 
 39-49. 
 7. Yoo H.W., Jung S.H., Jang D.S., Na Y.K. - Extraction of major object features using 
 VQ clustering for content-based image retrieval, Pattern Recognition 35 (5) (2002) 
 1115-1126. 
 8. Kumar R.R., Prasad A.B. - K means clustering algorithm for partitioning data sets 
 evaluated from horizontal aggregations, IOSR Journal of Computer Engineering 12 
 (5) (2013) 45-48. 
 9. Yadav A., Sing S.K. - An improved K-Means clustering algorithm, International 
 Journal of Computing Academic Research 5 (2) (2016) 88-103. 
 10. Maur Harleen Kaur, Puneet Jain - Content based image retrieval system using K-
 Means clustering algorithm and SVM classifier technique, International Journal of 
 Advance Research, Ideas and Innovations in Technology 5 (2) (2019) 39-43. 
 11. Juli Rejito, Atje Setiawan Abdullah, Akmal, Deni Setiana and Budi Nurani Ruchjana 
 - Image indexing using color histogram and k-means clustering for optimization 
 214 
Một phương pháp gom cụm dữ liệu cho bài toán tìm kiếm ảnh 
 CBIR in image database, The Asian Mathematical Conference 2016 (AMC 2016), 
 IOP Conf. Series: Journal of Physics: Conf. Series 893 (2017) 012055. 
 12. Mohamed Ouhda, Khalid El Asnaoui, Mohammed Ouanan and Brahim Aksasse - A 
 content based image retrieval method based on K-Means clustering technique, 
 Journal of Electronic Commerce in Organizations 16 (1) (2018) 82-96. 
 13. Wei Zhang, Lihua Tian, Shanmin Pang, Chen Li - Multiple Cartesian K-medoids for 
 a fine quantization, IEEE 22nd International Conference on Parallel and Distributed 
 Systems (2016) 1216-1220. 
 14. Mostafa G. Saeed, Fahad Layth Malallah, Zaid Ahmed Aljawaryy - Content-based 
 image retrieval by multifeatures extraction and K-Means clustering, International 
 Journal of Electrical, Electronics and Computers (EEC Journal) 3 (2017) 1-11. 
 15. Tongtong Yuan, Weihong Deng, Jiani Hu, Zhanfu An, Yinan Tang - Unsupervised 
 adaptive hashing based on feature clustering, Neurocomputing (2018) 1-41. 
 16. Annrose J., Christopher C.S. - Content based image retrieval using query based 
 feature reduction with K-means cluster index, Asian Journal of Research in Social 
 Sciences and Humanities 6 (12) (2016) 852-872. 
 17. Jain A.K. - Data clustering: 50 years beyond K-means, Pattern Recognition 
 Letters 31 (8) (2010) 651-666. 
 18. Lin C.H., Chen C.C., Lee H.L., & Liao J.R. - Fast K-means algorithm based on a 
 level histogram for image retrieval, Expert Systems with Applications 41 (7) (2014) 
 3276-3283. 
 ABSTRACT 
 A METHOD OF CLUSTERING FOR CONTENT-BASED IMAGE RETRIEVAL 
 Nguyen Thi Thuy Trang, Tran Nhu Y 
 Huynh Thi Chau Lan, Phan Thi Ngoc Mai* 
 Ho Chi Minh City University of Food Industry 
 *Email: maiptn@hufi.edu.vn 
 In this paper, an improvement in K-Means algorithm was proposed to cluster and 
applied to the problem of searching similar images by content. To accomplish this, we used a 
threshold value that measured the similarity between data objects, which is called as θ. 
K-Means algorithm was improved by not pre-determining the number of cluster centers, the 
number of data clusters grow with the increase in the number of images. The image was 
extracted as a n-dimensional vector and was an input for the improved K-Means algorithm 
from which to search for similar images. In order to demonstrate the proposals, we 
experimented and evaluated the results on the COREL image data set (1000 images) and 
compared to other recently published works on the same dataset. According to the 
experimental results, our proposals are feasible and applicable to different image retrieval 
systems. 
Keywords: Cluster, K-Means, similarity measure, similar images, image retrieval. 
 215