Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIV về Nghiên cứu cơ bản và ứng dụng Công nghệ thơng tin (FAIR), TP. HCM, ngày 23-24/12/2021
DOI: 10.15625/vap.2021.0076

TÌM KIẾM ẢNH TƯƠNG TỰ VÀ ỨNG DỤNG TRA CỨU THÔNG TIN
HỌC VIÊN QUA HÌNH ẢNH
Đào Xuân Bao1, Nguyễn Thị Định2, Nguyễn Văn Tùng2, Nguyễn Phương Hạc2, Văn Thế Thành1
1

Phòng Quản lý khoa học và Đào tạo sau đại học, Trường ĐH Công nghiệp thực phẩm TP. Hồ Chí Minh
2
Khoa Cơng nghệ thơng tin, Trường ĐH Cơng nghiệp thực phẩm TP. Hồ Chí Minh
{baodx, dinhnt, tungnv, hacnp, thanhvt}@hufi.edu.vn

TĨM TẮT: Bài tốn tìm kiếm ảnh tương tự và ứng dụng tra cứu thông tin đối tượng qua hình ảnh là một vấn đề thời sự và
được nhiều nhóm nghiên cứu quan tâm. Trong bài báo này, chúng tơi thực hiện tìm bài tốn kiếm ảnh tương tự và ứng dụng vào
việc tra cứu thông tin học viên tại Trường Đại học Công nghiệp thực phẩm TP. HCM (HUFI). Để thực hiện vấn đề này, một cấu
trúc KD-Tree được xây dựng nhằm ứng dụng cho bài tốn tìm kiếm ảnh tương tự và trích xuất thơng tin hình ảnh trên Ontology.
Thực nghiệm sử dụng tập dữ liệu ảnh LFW để đánh giá, so sánh với các cơng trình đã cơng bố gần đây. Sau đó, bộ ảnh ST-HUFI
được dùng làm dữ liệu để xây dựng hệ tra cứu thơng tin học viên qua hình ảnh tại HUFI. Theo kết quả thực nghiệm, độ chính xác
tìm kiếm ảnh tương tự trên các bộ dữ liệu LFW và ST-HUFI lần lượt là 86,88%, 72,32%; điều này cho thấy phương pháp đề xuất
của chúng tôi là khả thi và hiệu quả.
Từ khóa: Image retrieval, similar image, Ontology, KD-Tree.

I. GIỚI THIỆU
Tra cứu thơng tin qua hình ảnh là một chủ đề được nhiều nhóm nghiên cứu quan tâm và ứng dụng vào các lĩnh
vực y tế, giáo dục, giao thơng,… Vì vậy, ngày nay đã có nhiều hệ thống giúp tra cứu thơng tin nhanh bằng hình ảnh đã
được triển khai như hệ thống thông tin bệnh viện (HIS), hệ thống thông tin địa lý (GIS),… nhằm sử dụng nguồn tài
nguyên ảnh số đang có, đồng thời mang lại hiệu suất cao về độ chính xác và tối ưu về mặt thời gian. Ảnh số ngày càng
gần gũi với con người và gia tăng nhanh theo thời gian; theo số liệu thống kê của tập đoàn dữ liệu quốc tế IDC
(International Data Group) [1, 2] thì dự đốn đến năm 2025, dữ liệu tồn cầu có thể lên đến 175 (zecta byte); điều này
vừa tạo cơ hội vừa là thách thức cho các bài toán nghiên cứu về lĩnh vực tra cứu thơng tin qua hình ảnh. Bên cạnh đó, việc

tận dụng nguồn tài nguyên ảnh số có sẵn là một trong các yêu cầu trọng điểm của quốc gia trong bối cảnh cần triển khai
hệ thống số ngày nay. Vì vậy, một hệ thống tra cứu thơng tin qua hình ảnh mà người dùng chỉ cần sử dụng thiết bị
Smartphone chụp ảnh đối tượng và đưa vào hệ thống tra cứu thông tin là thật sự cần được triển khai, đặc biệt áp dụng cho
các tổ chức quản lý nhân sự hay quản lý sinh viên tại các trường đại học tại Việt Nam.
Đối với các bài toán xử lý dữ liệu lớn, một cấu trúc dữ liệu lưu trữ đáp ứng được yêu cầu ảnh số gia tăng theo thời
gian là thật sự cần thiết. Hiện nay, có nhiều cấu trúc dữ liệu dạng cây như cây R-Tree [3], SS-Tree [4], KD-Tree [5],… áp
dụng cho việc lưu trữ dữ liệu đa chiều như ảnh số, video và các dữ liệu đa phương tiện khác đã mang lại những kết quả
khả quan. Trong bài báo này, chúng tôi tiến hành xây dựng một cấu trúc dữ liệu đa chiều theo tiếp cận KD-Tree
(k-Dimensional Tree) nhằm lưu trữ dữ liệu hình ảnh và phân lớp cho ảnh đầu vào trước khi thực hiện tra cứu thơng tin.
Đóng góp của bài báo gồm: (1) Thực hiện tiền xử lý dữ liệu bộ ảnh ST-HUFI và trích xuất đặc trưng hình ảnh;
(2) Xây dựng cấu trúc dữ liệu tiếp cận cây KD-Tree nhằm lưu trữ bộ dữ liệu ảnh ST-HUFI [6], LFW [7]; (3) Thực hiện
phân lớp ảnh đầu vào dựa trên cấu trúc KD-Tree đã xây dựng; (4) Tra cứu thơng tin học viên qua hình ảnh được thực
nghiệm trên bộ ảnh ST-HUFI.
Phần còn lại của bài báo gồm: Phần II, khảo sát và phân tích ưu nhược điểm của một số cơng trình liên quan để
chứng minh tính khả thi cho bài tốn tra cứu thơng tin học viên qua hình ảnh; Phần III, trình bày thuật tốn xây dựng
cấu trúc KD-Tree; phân lớp hình ảnh theo mơ hình dạng cây KD-Tree; Mơ hình tra cứu thơng tin qua hình ảnh và thực
nghiệm trên bộ ảnh LFW, ST-HUFI được mô tả trong Phần IV, kết quả thực nghiệm trên bộ ảnh LFW, ST-HUFI được
đánh giá, so sánh với các cơng trình đã cơng bố; Phần V là kết luận và hướng phát triển tiếp theo.
II. CÁC CƠNG TRÌNH LIÊN QUAN
Tra cứu thơng tin qua hình ảnh là một trong các ứng dụng được nhiều đối tượng quan tâm cả về góc độ nhà
quản lý và người dùng cá nhân. Tra cứu thơng tin qua hình ảnh là một bài tốn nối dài và mang tính chất ứng dụng của
bài tốn phân lớp hình ảnh, tìm kiếm tập ảnh tương tự; trong đó tập dữ liệu thực nghiệm là tập hình ảnh thuộc các lĩnh
vực khác nhau như tập ảnh về thực vật, động vật, phong cảnh hay con người,... Hiện nay, có nhiều kỹ thuật khác nhau
để thực hiện bài tốn tra cứu thơng tin qua hình ảnh như: Tra cứu thông tin dựa trên cơ sở dữ liệu bằng cách tìm kiếm
mẫu tương đồng, sử dụng các kỹ thuật học máy, sử dụng Ontology mô tả ngữ nghĩa đối tượng,... Trong đó, một số
cơng trình tra cứu thơng tin qua hình ảnh cơng bố với kết khả quan, cụ thể là:
Yuqian Zhang và cộng sự (2016) [8] sử dụng phương pháp phân chia vùng ảnh để phác thảo và nhận diện khn
mặt. Trong cơng trình này, mỗi hình ảnh trong tập dữ liệu tại pha huấn luyện được chia thành nhiều vùng; cấu trúc KDTree được xây dựng dựa trên tập ảnh phân vùng nhằm phân lớp và lưu trữ dữ liệu hình ảnh. Tại pha kiểm thử, mỗi ảnh
được chia thành nhiều phân vùng và cấu trúc KD-Tree được sử dụng trong quá trình tìm kiếm theo k láng giềng gần



340

TÌM KIẾM ẢNH TƯƠNG TỰ VÀ ỨNG DỤNG TRA CỨU THƠNG TIN HỌC VIÊN QUA HÌNH ẢNH

nhất bằng cách đối sánh các vùng ảnh tìm kiếm với ảnh gốc. Trong cơng trình này, cây KD-Tree được xây dựng theo
cấu trúc chỉ mục nhằm giảm thời gian tìm kiếm đáng kể đồng thời so sánh với thuật tốn tìm kiếm láng giềng k-NN.
Thực nghiệm trên bộ ảnh khuôn mặt phác thảo CUHK (CUFS) với kết quả khả quan.
Chong Wang và cộng sự (2017) [9] đã thực hiện một phương pháp nhận diện khuôn mặt bằng cách dựa vào các
điểm mục tiêu trên khuôn mặt để đối sánh với cơ sở dữ liệu huấn luyện, đồng thời nhóm tác giả ứng dụng vào việc
phân loại khuôn mặt và xác minh thông tin qua hình ảnh. Bên cạnh đó, tác giả cũng chỉ ra các phương pháp lựa chọn
điểm mục tiêu cho bài tốn nhận dạng khn mặt và các vấn đề liên quan. Cuối cùng, thực nghiệm được xây dựng trên
bộ dữ liệu ảnh CASIA-WebFace [19], CelebA [20] và MS-Celeb-1M [21] đã chứng minh tính hiệu quả và khả thi của
phương pháp đề xuất.
Ali Al Kobaisi và cộng sự (2019) [10] đã thực hiện một phương pháp nhận diện khuôn mặt bằng kỹ thuật học
sâu (Deep Learning) kết hợp với hàm băm. Mục đích của cơng trình này là để nhận diện nhanh khuôn mặt thông qua
một tập cơ sở dữ liệu lớn. Đầu tiên, với một ảnh đầu vào sử dụng thuật tốn nhận diện nhằm xác định giới hạn khn
mặt, sau đó hình ảnh được phân đoạn, thay đổi kích thước và được chuyển thành ảnh xám rồi trích xuất thành véctơ
đặc trưng đa chiều; trong đó thành phần cuối cùng được chuyển mã băm nhị phân và dùng làm khóa để truy xuất các
vùng lân cận gần với điểm mục tiêu. Kết quả thực nghiệm trên bộ ảnh khuôn mặt LFW với mã băm có độ dài 64 của 48
mẫu truy vấn.
N. Asim và cộng sự (2019) [11], đã thực hiện phương pháp truy xuất thơng tin qua hình ảnh dựa trên Ontology
áp dụng cho dữ liệu đa phương tiện (hình ảnh, video, audio). Nhóm tác giả đã so sánh hiệu suất với các phương pháp
tiếp cận trước đó về các phương pháp tra cứu thông tin bằng dữ liệu đa phương tiện. Trong cơng trình này, tác giả sử
dụng ngôn ngữ bộ ba RDF để thực hiện lưu trữ và truy vấn trên Ontology. Tuy nhiên, tác giả mới đề xuất mơ hình sử
dụng Ontology để truy vấn dữ liệu đa đối tượng, chưa đề cập đến kết quả thực nghiệm với bộ ảnh cụ thể.
Bên cạnh đó, tra cứu thơng tin qua hình ảnh theo cách tiếp cận Ontology [12, 13, 14] đã được nhiều cơng trình
cơng bố đã đạt hiệu suất cao và thời gian tra cứu nhanh. Zahid Medmood và cộng sự (2017) [12] thực hiện truy xuất
thơng tin và phân tích ngữ nghĩa qua hình ảnh bằng Ontology. Trong cơng trình này, một kỹ thuật từ điển dữ liệu để
ánh xạ giữa ngữ nghĩa thị giác cấp cao và đặc trưng cấp thấp của hình ảnh được sử dụng. Tuy nhiên, trong cơng trình

này nhóm tác giả chưa xây dựng một mơ hình tìm kiếm cũng như chưa thực hiện truy vấn bằng cách tạo câu truy vấn
SPARQL nhằm thực hiện bài tốn tìm kiếm theo ngữ nghĩa hình ảnh. Botao Zhong và cộng sự (2020) [14] đã đề xuất
một phương pháp xác định mối quan hệ giữa các hình ảnh bằng cách thơng qua chú thích và đặc trưng của hình ảnh.
Nhóm tác giả đã xây dựng một framework cho Ontology để truy xuất mối quan hệ của hình ảnh bằng cách thực hiện
trên protégé nhằm phân lớp các đối tượng hình ảnh, phân lớp các thuộc tính đồng thời xác định mối quan hệ giữa các
lớp hình ảnh và lớp đối tượng.
Từ các cơng trình nghiên cứu cho thấy, việc truy xuất thơng tin qua hình ảnh dựa trên nhiều kỹ thuật khác nhau
là hồn tồn khả thi. Tuy nhiên, các cơng trình này chỉ ứng dụng các kỹ thuật đơn lẻ, chưa tích hợp giữa kỹ thuật học
máy vào cấu trúc dữ liệu lưu trữ để tra cứu thông tin qua hình ảnh. Vì vậy, trong cơng trình này chúng tơi thực hiện
một phương pháp phân lớp dữ liệu cho ảnh đầu vào bằng cấu trúc KD-Tree; tìm kiếm tập ảnh tương tự; trên cơ sở này
thực hiện trích xuất véctơ từ thị giác để tra cứu thơng tin hình ảnh bởi Ontology bằng ngôn ngữ truy vấn SPARQL.
III. CẤU TRÚC DỮ LIỆU ĐA CHIỀU KD-TREE
A. Mô tả cấu trúc dữ liệu đa chiều KD-Tree
Trong phần này, chúng tơi trình bày cấu trúc dữ liệu đa chiều KD-Tree được xây dựng nhằm thực hiện phân lớp
cho ảnh đầu vào và lưu trữ dữ liệu hình ảnh. Cây KD-Tree nguyên thủy [15] là một cấu trúc dữ liệu nhị phân, cân bằng,
tại mỗi điểm trên cây lưu trữ các điểm đa chiều trong không gian. Trên cơ sở này, cấu trúc KD-Tree mà chúng tôi xây
dựng là cây đa nhánh cân bằng, dữ liệu lưu trữ tại nút lá, nút trong đóng vai trị phân lớp dữ liệu để hình thành các phân
lớp tại nút lá trên cây. Các thành phần trên cây KD-Tree được mô tả như sau:
a) Nút gốc (Root) là nút khơng có nút cha, có một tập nút con; Root lưu trữ véctơ trọng số w0 và có một mức
level.
b) Nút trong (Nodei) là nút có một nút cha và tập nút con; mỗi Nodei lưu trữ một véctơ trọng số wi và có một
mức level
c) Nút lá (Leaf) là nút chỉ có một nút cha và lưu rữ tập véctơ đặc trưng hình ảnh, mỗi nút lá có một nhãn (label)
và có một mức level.
d) Hai nút gọi là hai nút anh em nếu có cùng một mức: Nodei.level = Nodej.level hoặc Leafi.level = Leafj.level.
e) Hai nút gọi là cha con nếu có một liên kết đến nút cha: Nodei.parent = Nodej hoặc Leafi.parent = Nodej.
B. Nguyên tắc xây dựng cấu trúc dữ liệu đa chiều KD-Tree
Gọi tập véctơ đặc trưng bộ ảnh ST-HUFI là F = {fi: fi = (xi0, xi1, …, xin); i = 1... k}, mỗi véctơ đại diện cho một
hình ảnh gồm 3024 chiều với các đặc trưng khuôn mặt (HOG) được mô tả trong Phần IV.B. Dựa trên cơ sở tập véctơ



Đào Xuân Bao, Nguyễn Thị Định, Nguyễn Phương Hạc, Nguyễn Văn Tùng, Văn Thế Thành

341

đặc trưng của các bộ dữ liệu hình ảnh thực nghiệm, chúng tơi xây dựng cấu trúc dữ liệu đa chiều KD-Tree gồm các
bước sau:
Bước 1: Khởi tạo chiều cao cây bằng h, số nhánh tối đa tại mỗi nút trên KD-Tree là n. Dựa vào số phân lớp của
tập dữ liệu huấn luyện, số nút lá tối đa trên KD-Tree là nk
Bước 2: Khởi tạo tập véctơ trọng số ngẫu nhiên W =< w0 , w1, ..., wh −1 > , mỗi véctơ wi = ( w , w ,..., win ) lưu
i1 i 2
trữ tại các nút trong Nodei.
Bước 3: Tại mỗi Nodei khởi tạo ngưỡng wi .left = 0,5 và wi .right = 0,5 để cây cân bằng.
Bước 4: Giá trị đầu ra cho fj tại Nodei được xác định bởi hàm yi = Sigmoid(wi*fj) và đường đi cho fj đến nhánh
kế tiếp như sau:
Nếu yj < wi.left; tạo nhánh con bên trái của Nodei.
Nếu yj > wi.right; tạo nhánh con bên phải của Nodei.
Nếu wi.left ≤ yj ≤ wi.right hoặc cây đã tạo đủ n nhánh thì fj đi theo nhánh gần nhất. Nhánh gần nhất là nhánh có
giá trị khoảng cách tính từ giá trị đầu ra Sigmoid(wi*fj) đến các giá trị ngưỡng đã tạo nhánh trước đó là nhỏ nhất.
Bước 5: Quá trình ở Bước 3, Bước 4 lặp lại cho đến khi gặp nút lá thì chèn fj vào Leafk.
Quá trình tạo nhánh con trái, nhánh con phải và tìm đường đi đến nhánh gần nhất được minh họa bởi hình 1 - 3.
Cấu trúc KD-Tree đa nhánh cân bằng được mơ tả bởi hình 4.

Hình 1. Q trình tạo nhánh trái

Hình 2. Quá trình tạo nhánh phải

Hình 3. Quá trình tạo nhánh con theo dmin

Hình 4. Cấu trúc KD-Tree đa nhánh cân bằng


C. Thuật toán phân lớp ảnh trên cấu trúc KD-Tree
Vì cấu trúc KD-Tree được xây dựng theo phương pháp phân lớp dữ liệu, các nút trong lưu trữ véctơ trọng số đã
được huấn luyện theo phân cụm để thực hiện phân lớp tại nút lá. Việc phân lớp này bản chất là dùng thuật tốn tìm
kiếm theo láng giềng gần nhất k-NN vì sử dụng phương pháp thống kê tại nút lá rồi gán nhãn nút lá cố định để huấn
luyện; quá trình phân lớp cho một ảnh đầu vào bất kỳ bởi cấu trúc KD-Tree thực hiện theo các bước sau:
Bước 1: Với mỗi ảnh đầu vào J trích xuất véctơ đặc trưng fj, ban đầu fj chưa xác định nhãn (label).
Bước 2: Cấu trúc KD-Tree phân lớp cho ảnh J bằng cách duyệt từ nút gốc đến nút trong tầng kế nút lá.
Bước 3: Tại mỗi Nodei tính giá trị đầu ra cho fj là S = Sigmoid(wi*fj).


TÌM KIẾM ẢNH TƯƠNG TỰ VÀ ỨNG DỤNG TRA CỨU THƠNG TIN HỌC VIÊN QUA HÌNH ẢNH

342

Bước 4: Tính khoảng cách từ S đến tất cả các điểm là cận trái, phải của Nodei.
Bước 5: Tìm khoảng cách nhỏ nhất (dmin) từ S đến các cận này để quyết định nhánh Nodek để đi tiếp.
Bước 6: Lặp lại các Bước 3, 4, 5 đến khi gặp nút lá (Leafk) thì gán leafk.label chính là phân lớp của ảnh J.
Thuật tốn phân lớp ảnh - CLKDT
Đầu vào: Véctơ fi của ảnh I, cấu trúc cây KD-Tree
Đầu ra: Tên phân lớp CLI của ảnh I
Thuật toán phân lớp ảnh dựa trên cấu trúc KD-Tree - CLKDT

0B

Input: Véctơ đặc trưng f i của ảnh I , KD − Tree
Output: Tên phân lớp CLI của ảnh I;
Function CLKDT ( f i , KD − Tree )
Begin
CLI = ∅;


For ( int i = 0; i < h-1; i++) do
LeftRightofWi = [m..n];
ChildofWi = [InNodem..InNoden];
S = Sigmoid(Product(Wi,fj);
Foreach (k in LeftRightofWi) do
d(S,k) = TinhKC(S,k);
If (d(S,k) = dmin)) then CLKDT(fj,KD-Tree.InNodek);
EndForeach;
EndFor;
If ( fi ∈ Leaf k ) then CLI = Leaf k .label;
Return CLI;
End.
Mệnh đề: Độ phức tạp của thuật toán CLKDT là O(h * k ) với h là chiều cao cây KD-Tree và k là số nhánh tối
đa tại iNodei.
Chứng minh: Thuật toán CLKDT lần lượt duyệt qua các tầng của KD-Tree từ nút gốc đến nút lá với chiều cao
h. Tại mỗi Nodei của tầng thứ i thì duyệt qua danh sách các các nút con của Nodei. Do đó, độ phức tạp của thuật tốn
CLKDT là O(h * k ) .
Trên cơ sở phân lớp ảnh bằng cấu trúc KD-Tree, thực nghiệm với các bộ dữ liệu kết quả phân lớp lấy TOP 85%
tập ảnh được trình bày trong bảng 1.
Bảng 1. Độ chính xác phân lớp các bộ dữ liệu thực nghiệm trên KD-Tree
STT
1
2

Tên bộ ảnh
LFW
ST-HUFI

Số lượng ảnh

13,233
2,569

TOP 85% số lượng
ảnh
11,248
2,183

Số phân lớp

Độ chính xác phân lớp (%)

5,749
134

89,25
86,51

IV. ONTOLOGY BIỂU DIỄN THƠNG TIN HÌNH ẢNH
A. Mơ tả dữ liệu ảnh thực nghiệm
Để minh chứng tính hiệu quả của mơ hình tra cứu thơng tin học viên qua hình ảnh được thực nghiệm và đánh
giá trên bộ ảnh LFW, ST-HUFI. Trong bài báo này, chúng tôi thực nghiệm trên bộ ảnh LFW đã được các công trình
trước đây; đồng thời làm căn cứ so sánh với bộ ảnh ST-HUFI. Các bộ ảnh này được mô tả trong bảng 2.
Bảng 2. Mô tả các bộ dữ liệu ảnh thực nghiệm
STT
1
2

Tên bộ ảnh
LFW

ST-HUFI

Số lượng ảnh
13,233
2,569

TOP 85% số lượng ảnh
11,248
2,183

Số phân lớp
5,749
134


Đào Xuân Bao, Nguyễn Thị Định, Nguyễn Phương Hạc, Nguyễn Văn Tùng, Văn Thế Thành

343

Bộ dữ liệu ảnh LFW (Labeled Faces in the Wild) được thành lập vào năm 2007 do Huang và cộng sự thực hiện
trong một phần của dự án Berkeley Faces in the Wild. LFW bao gồm các hình ảnh thu được từ Internet chứ khơng phải
thu được trong một số môi trường được xác định trước. Các khuôn mặt được gắn nhãn trong cơ sở dữ liệu Wild (LFW)
đã được sử dụng rộng rãi làm chuẩn để nghiên cứu xác minh khuôn mặt. Cơ sở dữ liệu ảnh LFW bao gồm 13.233 hình
ảnh khn mặt của 5,749 cá nhân. Điểm hạn chế là các cặp ảnh trong LFW có ánh sáng và ngoại cảnh khác nhau, hầu
hết các hình ảnh đều ở gần chính diện và thiếu các tư thế khác biệt.
Bộ dữ liệu ảnh ST-HUFI (Student HUFI) gồm 2,569 ảnh của 134 sinh viên của Trường Đại học Công nghiệp
thực phẩm TP. HCM thuộc nhiều khoa và các chuyên ngành đang theo học. Mỗi sinh viên có từ 18 đến 20 ảnh và được
lưu trữ trong cùng một thư mục, mỗi thư mục có một ảnh đại diện. Mỗi sinh viên được tổ chức là một phân lớp được
gán nhãn là mã số sinh viên.
B. Trích xuất đặc trưng bộ ảnh sinh viên Trường Đại học Cơng nghiệp thực phẩm TP. HCM (ST-HUFI)

Thực nghiệm trích xuất đặc trưng khuôn mặt cho bộ ảnh LFW, ST-HUFI được minh họa bởi hình 5. Trong đó,
mỗi hình ảnh đuợc trích xuất véctơ đặc trưng HOG (Histrogram of oriented gradient) có 3024 thành phần gồm: Đặc
trưng khn mặt (Face), khuôn mặt và đầu (Face&Head), mắt trái (Left Eye), mắt phải (Right Eye), hai mắt (Fair
Eyes), mũi (Nose), miệng (Mouth), lông mày trái (Left Eyebrows), lông mày phải (Right Eyebrows), hai lông mày (Eye
brows). Các đặc trưng này này được trích xuất theo màu sắc (Color), vị trí đối tượng (Location), hình dạng (Shape),
cấu trúc (Texture). Trong bài báo này, chúng tơi thực hiện trích xuất đặc trưng khn mặt và ứng dụng cho bộ ảnh
LFW, ST-HUFI để tạo ra mỗi hình ảnh một véctơ đặc trưng 3024 chiều. Trên cơ sở véctơ đặc trưng hình ảnh này, cấu
trúc cây KD-Tree đa nhánh cân bằng được xây dựng để thực hiện phân lớp dữ liệu hình ảnh.

Hình 5. Trích xuất đặc trưng khn mặt ảnh 2001190258.jpg bộ ảnh ST-HUFI

(a)

(f)

(b)

(c)

(d)

(e)

(g)

(h)

(i)

(j)


Hình 6. Ảnh phân đoạn trích xuất đặc trưng HOG cho khn mặt ảnh 2001190258.jpg bộ ảnh ST-HUFI


344

TÌM KIẾM ẢNH TƯƠNG TỰ VÀ ỨNG DỤNG TRA CỨU THƠNG TIN HỌC VIÊN QUA HÌNH ẢNH

Kết quả trích xuất véctơ đặc trưng của ảnh 2001190258.jpg bộ ảnh ST-HUFI được thực hiện bằng các ảnh phân
đoạn được mô tả trong hình 6 gồm: (a) ảnh khn mặt (Face); (b) ảnh khuôn mặt và đầu (Face & Head); (c) ảnh mắt
trái (Left Eye); (d) ảnh mắt phải (Right Eye); (e) ảnh phân đoạn mũi (Nose); (f) ảnh phân đoạn miệng (Mouth); (g) ảnh
cả hai mắt (Fair Eyes); (h) ảnh cả hai mày (Eye brows); (i) ảnh mày trái (Left Eyebrows); (j) ảnh mày phải (Right
Eyebrows).
C. Xây dựng Ontology biểu diễn thông tin qua hình ảnh
Để mơ tả thơng tin qua hình ảnh bằng ngữ nghĩa cấp cao, một Ontology được xây dựng cho bộ dữ liệu ảnh STHUFI dựa trên ngôn ngữ bộ ba RDF/XML và OWL. Quá trình tra cứu thơng tin học viên qua hình ảnh được thực hiện
thơng qua Ontology đã xây dựng. Dựa vào các phân lớp của các bộ dữ liệu ảnh, phân cấp lớp con được xây dựng cho
bộ ảnh này. Mỗi hình ảnh là một cá thể/thể hiện (individual/instance) của một hay nhiều phân lớp trong Ontology.
Trong bài báo này, chúng tôi xây dựng Ontology cho bộ dữ liệu ST-HUFI bằng phần mềm Protege minh họa bởi hình
7. Hình 8 là minh họa Ontology dạng ngơn ngữ N3.

Hình 7. Một Ontology cho bộ ảnh ST-HUFI trên phần mềm Protégé

Hình 8. Minh họa Ontology bộ ảnh ST-HUFI bằng ngôn ngữ N3


Đào Xuân Bao, Nguyễn Thị Định, Nguyễn Phương Hạc, Nguyễn Văn Tùng, Văn Thế Thành

345

V. MƠ HÌNH TRA CỨU THƠNG TIN HỌC VIÊN QUA HÌNH ẢNH

A. Mơ hình

Hình 9. Mơ hình tra cứu thơng tin học viên qua hình ảnh

Mơ hình tra cứu thơng tin học viên ST-HUFI qua hình ảnh được mơ tả như hình 9, với mỗi hình ảnh đầu vào
cần tra cứu thông tin, tiến hành phân lớp ảnh, tìm kiếm tập ảnh tương tự dựa trên mơ hình phân lớp dạng cây KD-Tree.
Từ phân lớp ảnh tạo câu truy vấn SPARQL để tra cứu thông tin học viên dựa trên Ontology đã xây dựng.
Pha tiền xử lý:
(1) Trích xuất véctơ đặc trưng của bộ dữ liệu ảnh ST-HUFI và xây dựng cấu trúc dữ liệu KD-Tree;
(2) Xây dựng Ontology cho bộ dữ liệu ảnh ST-HUFI;
Pha truy vấn:
(3) Trích xuất véctơ đặc trưng cho ảnh cần tra cứu thơng tin;
(4) Thực hiện phân lớp hình ảnh dựa vào cấu trúc KD-Tree và véctơ đặc trưng ảnh đầu vào;
(5) Trích xuất tên phân lớp của ảnh tra cứu thông tin;
(6) Dựa trên tên phân lớp ảnh, tạo câu truy vấn SPARQL;
(7) Tra cứu thông tin học viên dựa vào Ontology đã xây dựng;
(8) Trích xuất tập ảnh tương tự và thông tin học viên;
B. Véctơ từ thị giác và câu truy vấn SPARQL
Mỗi hình ảnh được trích xuất bằng véctơ đặc trưng, quá trình phân lớp hình ảnh trên cấu trúc KD-Tree nhằm
xác định phân lớp cho ảnh đầu vào. Mỗi phân lớp được ánh xạ vào phân lớp khái niệm để cho ra một từ thị giác, từ đó
làm cơ sở hình thành véctơ từ thị giác. Vì vậy, mỗi ảnh tra cứu thơng tin dựa trên Ontology bằng câu truy vấn
SPARQL được tạo ra từ véctơ từ thị giác của hình ảnh. Ngơn ngữ SPARQL được sử dụng và mô tả dưới dạng bộ ba
RDF và OWL. Dựa vào véctơ từ thị giác đã trích xuất từ phân lớp ảnh đầu vào, câu truy vấn SPARQL được tạo ra để
truy vấn trên Ontology. Kết quả truy vấn trên Ontology là thông tin cần truy xuất của học viên thơng qua hình ảnh. Câu
truy vấn SPARQL được tạo ra từ véctơ từ thị giác theo hai cách: “UNION Query” hoặc “AND Query” được minh họa
như hình 10. Câu truy vấn SPARQL được tạo ra từ quá trình phân lớp ảnh trên cây KD-Tree và sử dụng câu truy vấn
SPARQL để tra cứu thông tin học viên theo ảnh đầu vào.

Hình 10. Minh họa cấu truy vấn SPARQL



TÌM KIẾM ẢNH TƯƠNG TỰ VÀ ỨNG DỤNG TRA CỨU THƠNG TIN HỌC VIÊN QUA HÌNH ẢNH

346

C. Thuật tốn tra cứu thơng tin qua hình ảnh dựa trên cấu trúc KD-Tree và Ontology
Để tra cứu thơng tin qua hình ảnh, đầu vào là một ảnh bất kỳ của học viên thuộc Trường Đại học Công nghiệp
thực phẩm TP. HCM. Sau khi trích xuất đặc trưng, thực hiện phân lớp ảnh đầu vào. Từ kết quả phân lớp này làm cơ sở
thực hiện tạo câu truy vấn SPARQL để thực hiện tra cứu trên Ontology và trích xuất thơng tin học viên.
Thuật tốn tra cứu thơng tin học viên qua hình ảnh - IRKDT
Đầu vào: Ảnh I của học viên cần tra cứu
Đầu ra: Thông tin học viên
Function IRST-HUFI(I)
Begin
Infomation( I ) = ∅;

fi = ExtractFeature(I);
CLI = CLKDT(fi,KD-Tree);
SPARQL(I) = CreateSPARQL(CLI);
Infomation( I ) = IRetrieval ( SPARQL( I ), Ontology );

End.
VI. THỰC NGHIỆM
A. Mơi trường thực nghiệm
Thực nghiệm trích xuất đặc trưng hình ảnh, phân lớp hình ảnh dựa trên cấu trúc KD-Tree và hệ tra cứu thơng tin
học viên qua hình ảnh (IRST-HUFI) đượ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: Intel(R) Core™ i5-5200U, CPU 2.2GHz, RAM 16GB và
hệ điều hành Windows 10 Professional. Trong bài báo này, chúng tôi tiến hành thực nghiệm trên 2 bộ dữ liệu LFW và
ST-HUFI.
Để tra cứu thông tin học viên qua hình ảnh, đầu tiên cần xây dựng cấu trúc dữ liệu KD-Tree nhằm lưu trữ bộ

ảnh thực nghiệm. Thực nhiệm xây dựng cấu trúc KD-Tree được minh họa như hình 11, trong đó chiều cao cấu trúc
KD-Tree xây dựng (Height of KD-Tree); cây được xây dựng với số nhánh tối đa (Max Brand) tại mỗi nút trong được
xác định theo từng bộ dữ liệu; hiệu suất phân lớp (Classification Performance) trên cây.
Quá trình phân lớp ảnh và tra cứu thơng tin học viên qua hình ảnh được minh họa bởi hình 12, với một ảnh đầu
vào (Load Image) thực hiện trích xuất véctơ đặc trưng khn mặt HOG gồm 3024 chiều, phân lớp ảnh bằng cấu trúc
KD-Tree (Image Classification) cho kết quả là phân lớp ảnh đầu vào. Hiện tại bộ ảnh ST-HUFI với một phân lớp là
một học viên, mỗi phân lớp có một hoặc nhiều ảnh và chọn ảnh đầu tiên của phân lớp làm ảnh đại diện. Tên phân lớp
(ClassName) làm cơ sở tạo câu truy vấn SPARQL (Create SPARQL); từ đó thực hiện tra cứu thông tin học viên dựa
trên Ontology (Information Retrieval). Kết quả tra cứu thông tin học viên minh họa bởi hình 14 gồm các thơng tin như:
mã số, họ tên học viên, ngày sinh, giới tính, địa chỉ, điện thoại, mã lớp, khóa học, tình trạng, điểm tích lũy học tập của
sinh viên. Tập ảnh tương tự của ảnh đầu vào được minh họa bởi hình 13.

Hình 11. Xây dựng cấu trúc KD-Tree cho hệ tra cứu thông tin
học viên IRST-HUFI

Hình 12. Hệ kiếm ảnh tương tự sinh viên 2001180424


Đào Xuân Bao, Nguyễn Thị Định, Nguyễn Phương Hạc, Nguyễn Văn Tùng, Văn Thế Thành

Hình 13. Tập ảnh tương tự của ảnh 2001180424.jpg

347

Hình 14. Thơng tin tra cứu sinh viên qua ảnh 2001180424.jpg

B. Kết quả thực nghiệm
Kết quả phân lớp bộ ảnh LFW và bộ ảnh ST-HUFI thực hiện trên cấu trúc KD-Tree được trình bày trong bảng
1. Từ kết quả này cho thấy, phân lớp ảnh với cấu trúc KD-Tree đề xuất là khả thi và hiệu suất cao hơn kết quả trong
cơng trình [16] và [17] sử dụng kỹ thuật khác trên cùng bộ ảnh.

Kết quả tìm kiếm tập ảnh tương tự của các bộ dữ liệu thực nghiệm được trình bày trong bảng 3 được tính theo
TOP 85% bộ dữ liệu gốc. Đồng thời, thực hiện phân lớp ảnh đầu vào, tra cứu thông tin học viên. Kết quả này cho thấy
phương pháp đề xuất của chúng tơi là hồn tồn khả thi và hiệu quả, áp dụng được cho các bộ ảnh trong nhiều lĩnh vực.
Đồng thời, với cấu trúc dữ liệu đa chiều KD-Tree chúng tơi đề xuất có khả năng mở rộng cho các bộ dữ liệu lớn với số
phân lớp tăng trưởng theo thời gian, đây là một cấu trúc dữ liệu tăng trưởng và hiệu quả cho bài toán phân lớp dữ liệu.
Điều này rất phù hợp cho dữ liệu sinh viên tại các trường đại học ngày càng gia tăng theo thời gian.
Bảng 3. Hiệu suất tìm kiếm ảnh của phương pháp đề xuất trên các bộ dữ liệu
Tập ảnh
LFW
ST-HUFI

Độ chính xác trung bình
(%)
86,88
72,32

Độ phủ trung bình
(%)
74,48
70,18

Độ dung hịa trung bình
(%)
80,20
71,23

Thời gian truy vấn
trung bình (ms)
108,24
38,10


C. Đánh giá kết quả thực nghiệm
Để đánh giá kết quả thực nghiệm, trong bài báo này các đồ thị biểu diễn kết quả tìm kiếm tập ảnh tương tự được
thực hiện trên Matlab 2015. Mỗi đường cong trên đồ thị mô tả kết quả truy vấn với độ chính xác (precision) và độ phủ
(recall) các chủ đề trong bộ dữ liệu LFW và ST-HUFI. Đồ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 15 - 20 mơ tả hiệu suất và tính đúng đắn của kết quả truy vấn trên các bộ ảnh LFW và ST-HUFI. Đồ thị
cho thấy tính chính xác của hệ truy vấn tập ảnh LFW nằm tập trung ở vùng [0.52, 1.0]; độ chính xác của tập ảnh STHUFI nằm tập trung ở vùng [0.63, 1.0]. Đồ thị đường cong ROC biểu diễn các giá trị true positive và false positive
theo độ phủ Recall, các giá trị nằm tập trung trên đường cơ sở, nhiều giá trị nằm trong vùng true positive hơn vùng
false positive.

Hình 15. Precision-Recall và đường cong ROC bộ LFW
(Aaron Eckhart – Fernando Sanz)

Hình 16. Precision-Recall và đường cong ROC bộ LFW
(Fernando Valenzuela – Stephane Delajoux)


348

TÌM KIẾM ẢNH TƯƠNG TỰ VÀ ỨNG DỤNG TRA CỨU THƠNG TIN HỌC VIÊN QUA HÌNH ẢNH

Hình 17. Precision-Recall và đường cong ROC bộ LFW
(Stephane Rochon – Zydrunas Ilgauskas)

Hình 18. Precision-Recall và đường cong ROC bộ ST-HUFI
(2001180069 - 2001200050)

Hình 19. Precision-Recall và đường cong ROC bộ ST-HUFI
(2001200093 - 2001202290)


Hình 20. Precision-Recall và đường cong ROC bộ ST-HUFI
(2001202291 - 2033207471)

Để đánh giá kết quả hệ tra cứu thơng tin qua hình ảnh thực nghiệm trên bộ ảnh ST-HUFI, đồng thời so sánh với
các bộ ảnh thực nghiệm đã công bố trước đây. Chúng tôi thực hiện so sánh kết quả thực nghiệm với một số cơng trình
với các bộ ảnh khác nhau gồm bộ dữ liệu ảnh LFW được trình bày trong bảng 4.
Bảng 4. So sánh hiệu suất truy vấn giữa các phương pháp trên bộ dữ liệu LFW
Phương pháp

Lu Z., 2017 [16]
Renhai Chen, 2020 [17]
IRST-HUFI

Bộ dữ liệu
LFW
LFW
LFW

Độ chính xác trung bình (%)
81,46
86,60
86,88

Kết quả so sánh với các cơng trình nhận diện khuôn mặt thực nghiệm với bộ ảnh LFW cho thấy, hệ truy vấn và
tìm kiếm ảnh tương tự (IRST-HUFI) cao hơn các cơng trình [16] và [17] bởi các lý do sau:
1) Hệ IRST-HUFI thực hiện phân lớp nhiều lần cho đối tượng theo mơ hình cây KD-Tree nên kết quả phân
lớp ảnh cao.
2) Kết quả phân lớp ảnh đầu vào từ hệ được thực hiện tìm kiếm trên Ontology nên hiệu suất tìm kiếm cao.
Như vậy, hệ tìm kiếm ảnh tương tự và tra cứu thơng tin IRST-HUFI là kết hợp các kỹ thuật học máy vào cấu

trúc KD-Tree cho giai đoạn phân lớp hình ảnh để nâng cao hiệu suất truy vấn cũng như tra cứu thơng tin qua hình ảnh
dựa trên Ontology.
VII. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
Trong bài báo này, chúng tôi đã thực hiện một phương pháp tra cứu thông tin học viên qua hình ảnh và ứng
dụng cho bộ ảnh học viên ST-HUFI tại Trường Đại học Công nghiệp thực phẩm TP. HCM. Mỗi ảnh đầu vào được
phân lớp dữ liệu bằng câu trúc KD-Tree đa nhánh cân bằng với độ chính xác trên bộ ảnh LFW, ST-HUFI lần lượt là
89,25%, 86,51%. Sau khi thực hiện phân lớp cho ảnh đầu vào, tên phân lớp ảnh được dùng tạo câu truy vấn SPARQL
để tra cứu thông tin học viên tại HUFI. Chúng tơi xây dựng hệ tìm kiếm tập ảnh tương tự để đánh giá hiệu suất của
phương pháp đề xuất dựa trên Ontology đã xây dựng. Thực nghiệm được xây dựng trên các bộ ảnh LFW, ST-HUFI để
minh chứng tính khả thi của phương pháp đề xuất. Kết quả thực nghiệm tìm kiếm tập ảnh tương tự được đánh giá dựa
trên độ chính xác, độ phủ, độ dung hịa; đồng thời so sánh với các cơng trình đã cơng bố. Kết quả độ chính xác trung
bình tương ứng từng bộ ảnh theo TOP 85% số lượng ảnh lần lượt là: 86,88% và 72,32% cho thấy phương pháp đề xuất
là hiệu quả và có thể áp dụng được cho các hệ thống tìm kiếm ảnh thuộc các lĩnh vực khác nhau. Hướng phát triển tiếp
theo, chúng tôi ứng dụng cho nhiều bộ ảnh cùng lĩnh vực nhằm tra cứu nhanh thông tin cho một ảnh đầu vào bất kỳ,
giúp cải thiện hiệu suất quản lý và số hóa cho các đơn vị hành chính nhà nước trong quản lý nhân sự.
VIII. LỜI CẢM ƠN
Nghiên cứu này do Trường Đại học Công nghiệp thực phẩm Thành phố Hồ Chí Minh bảo trợ và cấp kinh phí
theo Hợp đồng số 147/HĐ-DCT. Chúng tơi xin trân trọng cám ơn nhóm nghiên cứu SBIR-HCM đã góp ý chuyên môn
cho nghiên cứu này. Chúng tôi xin trân trọng cảm ơn Trường Đại học Công nghiệp thực phẩm TP. HCM, Trường Đại
học Sư phạm TP. HCM đã tạo điều kiện về cơ sở vất chất giúp chúng tôi hoàn thành bài nghiên cứu này.


Đào Xuân Bao, Nguyễn Thị Định, Nguyễn Phương Hạc, Nguyễn Văn Tùng, Văn Thế Thành

349

TÀI LIỆU THAM KHẢO
[1] A Patrizio, “Data center explorer”, Network World.
/>[2] David Reinsel, John Gantz, John Rydning, “The Digitization of the World: From Edge to Core” sponsored by Seagate, IDC
Technical Report, 2018.

[3] Haldurai, L., & Vinodhini, V., Parallel Indexing on Color and Texture Feature Extraction using R-Tree for Content Based
Image Retrieval. International Journal of Computer Sciences and Engineering, 3, 11-15, 2015.
[4] White, D. A., Jain, R.: Similarity indexing with the ss-tree. Proceedings of the 12th International Conference on Data
Engineering, ICDE ’96, pp. 516-23. IEEE Computer Society, Washington, DC, USA, 1996.
[5] Gill, S., & Hooda, M., The design perspective of the structures based on KD Tree. Rising Threats in Expert Applications and
Solutions (pp. 515-524). Springer, Singapore, 2021.
[6] ST-HUFI Image Data set: />[7] LFW Image Data set: />[8] Zhang, Yuqian, et al. “Fast face sketch synthesis via KD-tree search”, European Conference on Computer Vision. Springer,
Cham, 2016.
[9] Wang, C., Lan, X., & Zhang, Y., Model distillation with knowledge transfer from face classification to alignment and
verification. arXiv preprint arXiv:1709.02929, 2017.
[10] Al Kobaisi, A., & Wocjan, P. (2019, December). MaxHash for Fast Face Recognition and Retrieval. International Conference
on Computational Science and Computational Intelligence (CSCI) (pp. 652-656), 2019, IEEE.
[11] Asim, Muhammad Nabeel, et al, The use of Ontology in retrieval: a study on textual, multilingual, and multimedia
retrieval, IEEE Access, 7: 21662-21686, 2019.
[12] Mehmood, Zahid; Mahmood, Toqeer; Javid, Muhammad Arshad. Content-based image retrieval and semantic automatic image
annotation based on the weighted average of triangular histograms using support vector machine. Applied Intelligence, 48.1:
166-181, 2018.
[13] Seymour, Z., & Zhang, Z., Image Annotation Retrieval with Text-Domain Label Denoising. Proceedings of the 2018 ACM on
International Conference on Multimedia Retrieval, pp. 240-248, June, 2018.
[14] Zhong, Botao, et al, Ontology-based semantic modeling of knowledge in construction: classification and identification of
hazards implied in images, Journal of Construction Engineering and Management, 2020, 146.4: 04020013.
[15] Bentley, Jon Louis. “Multidimensional binary search trees used for associative searching”, Communications of the ACM 18.9
(1975): 509-517.
[16] Lu, Z., Yang, J., & Liu, Q., Face image retrieval based on shape and texture feature fusion. Computational Visual Media, 3(4),
359-368, 2017.
[17] Chen, R., Li, W., Rao, G., & Feng, Z., A lightweight framework for fast image retrieval on large-scale image datasets. 9th NonVolatile Memory Systems and Applications Symposium (NVMSA), pp. 1-6, August 2020, IEEE.
[18] Nguyễn Thị Định, Văn Thế Thành, Lê Mạnh Thạnh, “Phân lớp ảnh bằng cây KD-Tree cho bài tốn tìm kiếm ảnh tương tự”,
Chun san Các cơng trình nghiên cứu, phát triển và ứng dụng cơng nghệ thông tin và truyền thông, tập 2021, số 1, 2021.
[19] />[20] />[21] />
AN INFORMATION RETRIEVAL SYSTEM OF STUDENT BY IMAGE AND APPLICATION

Dao Xuan Bao, Nguyen Thi Dinh, Nguyen Van Tung, Nguyen Phuong Hac, Van The Thanh

ABSTRACT: Information retireval system by images is a topical issue and is of interest to many research groups. In this
paper, we conduct a method to query information by images and apply to retrieval information of student at the University of Food
Industry in Ho Chi Minh City (HUFI). To accomplish this problem, a KD-Tree structure is built and applied to retrieve a set of
similar images and extracted image information by Ontology. Experiment using LFW image data set evaluates and compares with
the recently published works. After that, ST-HUFI image data set is used as data to build an system of information retrieval at
HUFI. The precision on experimental image data sets including LFW, ST-HUFI of 86.88%, 72.32%, respectively. This result
demonstrate that our proposed method is evaluated as effective.