Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020)

Đề xuất sử dụng phương pháp tiếp cận Pareto
để lựa chọn các điểm ảnh
Bùi Thị Thùy1, Lê Phú Hưng1, Nguyễn Đức Tồn1
1

Khoa Cơng nghệ thông tin - Trường Đại học Tài Nguyên và Môi Trường Hà Nội
Email: ,

Abstract— Trong bài báo này, chúng tôi đề xuất sử

ảnh đại diện. Các hệ thống đó được gọi là truy xuất
hình ảnh dựa trên nội dung (CBIR).[11]
Một hệ thống CBIR điển hình hoạt động như sau.
Đầu tiên, nó thực hiện trích xuất tính năng, tức là
cách liên kết mỗi hình ảnh với một vectơ định lượng.
Vectơ định lượng này được gọi là vectơ đặc trưng
của hình ảnh. Tính năng của tất cả các hình ảnh
trong cơ sở dữ liệu. Sau đó, đối với hình ảnh đầu
vào (thường được gọi là hình ảnh truy vấn), hệ
thống sẽ tính tốn thước đo khoảng cách của các đối
tượng vector với hình ảnh trong cơ sở dữ liệu. Cuối
cùng, những hình ảnh gần nhất có thước đo khoảng
cách nhỏ nhất được trả lại cho người dùng. [4,5,6,7]
Hệ thống CBIR thường thể hiện tính năng của hình
ảnh bằng màu sắc, kết cấu, hình dạng và bố cục
hình ảnh. Sự kết hợp của màu sắc, kết cấu và hình
dạng được đề xuất trong [9]. Mặt khác, trong [10]
sử dụng các thành phần điểm màu. Hơn nữa, phát
hiện cạnh màu và biến đổi wavelet rời rạc được sử

dụng để biểu diễn độ phức tạp của thuật toán [1].
Như vậy, chúng ta thấy xu hướng trong nhiều hệ
thống CBIR là sử dụng kết hợp nhiều tính năng để
truy xuất hình ảnh.Về mặt trực quan, người dùng
khơng dễ dàng nhận ra hình ảnh dựa trên các khía
cạnh như màu sắc và hình dạng, những người khác
nhau với cùng một hình ảnh có thể cho ra 1 hình
ảnh khác nhau. Hình ảnh khác nhau có thể có ý
nghĩa khác nhau hoặc mức độ quan trọng khác nhau
đối với mỗi người. Ví dụ: cho một hình ảnh cho
thấy một con chim trên bầu trời, một số người có
thể quan tâm đến con chim, trong khi những người
khác có thể quan tâm đến bầu trời.
Giả sử rằng mỗi đối tượng được liên kết với một
thước đo khoảng cách, thì mỗi hình ảnh có nhiều
khoảng cách liên quan đến một hình ảnh truy vấn
trong khơng gian tìm kiếm nhiều chiều. Cho một
hình ảnh truy vấn, theo từng đặc điểm của hình ảnh,

dụng phương pháp tiếp cận Pareto để lựa chọn các
điểm ảnh. Phương pháp này thường được sử

dụng trong hệ thống truy xuất hình ảnh dựa trên
nội dung (CBIR) có nhiều tính năng (ví dụ: màu
sắc, hình dạng, kết cấu). Trong phương pháp
này, các hệ thống thường biểu diễn mỗi hình ảnh
dưới dạng vectơ đặc trưng riêng biệt. Từ đó nối
các vectơ đặc trưng thành phần với một ảnh truy
vấn, tính tốn số đo khoảng cách của nó với ảnh
trong cơ sở dữ liệu. Mặc dù đơn giản, phương

pháp này không đề cập đến độ phức tạp của
thuật tốn. Một phương pháp khác thường tính
tốn sự kết hợp tuyến tính có trọng số của các
phép đo khoảng cách riêng lẻ và việc gán trọng
số cho mỗi phép đo dựa trên phản hồi về mức độ
liên quan (RF) từ người dùng để xác định tầm
quan trọng của từng thành phần. Trong bài báo
này, nhóm tác giả đề xuất sử dụng phương pháp
tiếp cận Pareto để lựa chọn các điểm ảnh. Đề
xuất thuật toán tạo ra một tập hợp nhỏ gọn các
điểm ảnh khi so sánh với toàn bộ tập dữ liệu và
tập này cũng chứa các kết quả thu được từ tất cả
tốn tử .
Keywords- Truy xuất hình ảnh dựa trên nội dung
(CBIR), phản hồi mức độ liên quan (RF), phương pháp
tiếp cận Pareto

I.

GIỚI THIỆU

Sự xuất hiện của Internet thay đổi hồn tồn cách
chúng ta tìm kiếm thơng tin. Ví dụ, khi làm việc với
văn bản, chỉ cần gõ từ khóa vào các cơng cụ tìm
kiếm như Google hay Bing, chúng ta có thể nhận
ngay danh sách các trang web phù hợp nhất với chất
lượng (nói chung) có thể chấp nhận được. Một hệ
thống tương đương như vậy cho hình ảnh, tức là lấy
đầu vào hình ảnh từ người dùng, cố gắng sắp xếp
các hình ảnh tương tự nhất trong tập dữ liệu hình

ảnh của nó, sau đó trả lại cho người dùng. Sự tương
đồng ở đây là dựa trên sự tương đồng của các hình

ISBN: 978-604-80-5076-4

50


Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thơng và Cơng nghệ Thơng tin (REV-ECIT2020)

chúng ta có thể tìm một số hình ảnh lân cận [2,3].
Nếu xét bài tốn trong khơng gian nhiều chiều, điểm
ảnh thường là tập con của các điểm lân cận trước đó
liên kết với mỗi chiều. Chức năng được sử dụng để
sắp xếp mức độ phù hợp giữa điểm ảnh đó. Do đó
phải tính tốn số đo khoảng cách tổng hợp cho mỗi
điểm ảnh dựa trên một số thuật tốn kết hợp có
trọng số của các phép đo khoảng cách riêng lẻ.
Trong bài báo này, nhóm tác giả đề xuất sử dụng
phương pháp tiếp cận Pareto để lựa chọn các điểm
ảnh.Thay vì thuật tốn truy vấn cho các hình ảnh có
liên quan đã chọn hoặc chỉ áp dụng phương pháp
SVM. Nhóm tác giả đề xuất một thuật toán nhằm
tạo ra một tập hợp nhỏ gọn các điểm ảnh khi so
sánh với toàn bộ tập dữ liệu và tập này và các kết
quả thu được từ tất cả các phép tính tốn.
Bài báo được trình bày như sau: Phần 2: Cơ sở tốn
học, Phần 3: Đề xuất thuật toán dựa trên phương
pháp tiếp cận Pareto để tối ưu khơng gian tìm kiếm.
Phần cuối là kết luận và tài liệu tham khảo.


mức độ liên quan để hiểu được nhận thức của người
dùng. Bằng cách tương tác với người dùng, phản
hồi về mức độ liên quan cung cấp thêm thơng tin để
chúng tơi có thể suy luận chính xác hơn về sở thích
của người dùng trong số nhiều tính năng, tức là tính
năng nào quan trọng hơn những tính năng khác
trong nhận thức của họ.
2.2. Bài tốn tối ưu trên miền khơng gian độ
đo khoảng cách

Tập Pareto là một tập con của tập các điểm
thoả hiệp của các lời giải trong đó chứa tất cả các
điểm mà có ít nhất một mục tiêu tối ưu trong khi
giữ nguyên mọi mục tiêu khác. Các điểm đó được
gọi là các điểm tối ưu Pareto.
Bài toán tối ưu trên miền không gian độ đo
khoảng cách của truy vấn với các mẫu trong cơ
sở dữ ảnh phát biểu như sau:
min D t (I ),
Q

II.

s.t . I

CƠ SỞ TOÁN HỌC

2.1. Phương pháp tiếp cận Pareto
Phương pháp Pareto có thể được tìm thấy trong

nhiều cơng trình liên quan đến cơ sở dữ liệu [4],
hoặc [5]. Trong [8] đề xuất một kỹ thuật sử dụng
tính tối ưu Pareto để thực hiện q trình lọc trước
nhằm loại bỏ các đối tượng ít đại diện hơn khỏi quá
trình lựa chọn k-láng giềng trong khi vẫn giữ lại
những đối tượng đại diện nhất. Công việc này nhận
được kết quả của một truy vấn bao gồm tất cả các
điểm Pareto. Bộ Pareto bao gồm các đối tượng liên
kết không gian với truy vấn nhiều hơn phương pháp
sử dụng phương pháp đo khoảng cách. Trong bài
báo [2] đã kết hợp hai phương pháp phản hồi mức
độ liên quan dựa vào phương pháp đo dựa trên
khoảng cách.
Bài báo, [9] đã đề xuất một thuật tốn truy xuất
thơng tin nhiều truy vấn kết hợp Pareto với Phương
pháp E Cient (EMR). Đối với mỗi truy vấn, EMR
được sử dụng để tạo ra một danh sách các kết quả
được sắp xếp dựa trên độ đo tương tự. Sau đó,
phương pháp Pareto được xây dựng dựa trên các kết
quả này.

EiF , i {1,..., M }

,

(1)

trong đó truy vấn Q biểu diễn bởi một tập T đặc
trưng và các phần tử ảnh I của tập dữ liệu


E

F

gồm M ảnh bao gồm các đặc trưng tương ứng

như truy vấn. DQt ( I ) D(Qt , It ) là độ đo khoảng
cách giữa đặc trưng thứ t biểu diễn bởi các thành
phần Qt và It.
Định nghĩa 3.1. (Tập Pareto trên độ đo khoảng
cách) Cho truy vấn Q, xác định một quan hệ trội
(ký hiệu là f) trên tập độ đo khoảng cách của hai
ảnh I1 và I2 như sau:

Quan hệ trội yếu, ký hiệu là DQ ( I1 )
khi và chỉ khi:

Ưu điểm của phương pháp Pareto trong hệ
thống CBIR, có thể thu gọn khơng gian tìm kiếm.
Do đó, nó có khả năng cải thiện hiệu suất của hệ
thống CBIR. Chúng tôi đề xuất sử dụng cách tiếp
cận Pareto, kết hợp với phương pháp phản hồi về

ISBN: 978-604-80-5076-4

t {1,...,T}

III.

ĐỀ XUẤT THUẬT TỐN


2.1 Bài tốn:

51

DQ ( I2 )


Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020)

Giả sử chúng ta có hai đặc trưng màu (C) và kết
cấu (T). Độ đo khoảng cách của ba đối tượng 01,
02, 03 tương ứng với truy vấn Q là:

Sau khi sắp xếp T danh sách, thuật toán chỉ
thực hiện trên phép so sánh, lần lượt lấy từng ảnh
chưa được đánh dấu trong mỗi danh sách so sánh
tập độ đo khoảng cách với tập giá trị ngưỡng
aTupleMax. Tập giá trị ngưỡng aTupleMax được
thiết lập sao cho mỗi thành phần của nó có giá trị
cao nhất trong tất cả các điểm Pareto đã tìm được.
Thuật toán đề xuất sử dụng định nghĩa 3.1 kết
hợp với tập giá trị aTupleMax để so sánh lấy ra
các điểm Pareto theo nhiều mức, quá trình tiếp
tục đến khi số điểm cần lấy đạt được k điểm,
được gọi là tập Pareto nhiều mức sâu. Quá trình
tăng dần mức độ sâu đến khi tìm đủ số điểm theo
độ sâu hoặc hết cơ sở dữ liệu.

Khoảng cách toàn cục áp dụng kết hợp tuyến tính

độ đo khoảng cách thành phần của các đặc
trưng màu và kết cấu tương ứng là:

Dễ dàng xếp hạng độ đo khoảng cách là 02, 03,
01. Khi khơng kết hợp tuyến tính độ đo khoảng
cách tồn cục, xếp hạng dựa vào độ đo khoảng
cách thành phần chúng ta chỉ có thể xếp hạng

2.3 Đánh giá độ phức tạp của thuật toán

được 01 , 02 đối tượng 03 khơng thể so sánh được
với hai đối tượng cịn lại.
Như vậy cách xếp hạng sử dụng tổng toàn bộ
độ đo khoảng cách của các thành phần trong kết
quả cuối cùng còn nhiều vấn đề cần xem xét và
cải tiến. Do đó nhóm tác giả đề xuất thuật tốn
sau.

Thuật tốn có độ phức tạp là O(n) , trong đó
các phép tốn được sử dụng chỉ toàn các phép so
sánh nên thời gian thực hiện nhanh.
Theo mệnh đề A, tập Pareto nhiều mức sâu
chứa các điểm có độ đo khoảng cách tối thiểu
theo thành phần và tối thiểu theo cách kết hợp
tuyến tính.
Theo mệnh đề B, các điểm trong cùng một
mức sâu thì khơng thể so sánh với nhau, các điểm
ở mức trong sâu hơn thì bị làm trội ở mức ngồi.
M
Như vậy tập Pareto depth bao được các điểm liên

quan về độ đo khoảng cách mức thấp. Tuỳ thuộc
số mức rìa, tập này có số mẫu nhỏ hơn tồn bộ cơ
sở dữ liệu. Tập Pareto chứa tất cả các điểm không

2.2 Thuật toán
A, Mệnh đề 1

I

E F , DQ (I) , nếu: t0 ,1 t0 T , DQt ( I )
0

Min DQt (I'), thì I PF1.
0

' {EF }

Chứng minh: Giả sử
I

PF 1

I'

EF , 1 t T, Dt(I ') Dt

(I)

trội với các điểm khác trong
B, Mệnh đề 2


PF1.

Thuật toán đề xuất sử dụng mệnh đề 1 và mệnh
đề 2.

ISBN: 978-604-80-5076-4

F

, DQ ( I ) .

Tập này chứa tất cả các phần tử tối thiểu hố
bằng cách kết hợp tuyến tính, nhưng cũng chứa
các phần tử khác mà khơng tìm thấy nếu kết hợp
tuyến tính.

Chứng minh: (i) được suy từ định nghĩa PF1.

(ii) Giả sử I

E

52


Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thơng và Cơng nghệ Thơng tin (REV-ECIT2020)

Thuật tốn đề xuất
Đầu vào:

/*Danh sách sắp thứ tự Tuple có T danh sách N ảnh, mỗi ảnh có T giá độ đo
khoảng cách theo từng đặc trưng với truy vấn Q
*/k /
* Số lượng mẫu trong tập Pareto */
Đầu ra:
ListResult /*Tập rìa Pareto */
/* Biến trung gian */
Result=0; PF=PF_Next= ; aTupleMax =0; aMax=0;
/* Khởi tạo */
1. TopTuple = 0;
2. While (Result 3.
While Ii PF mà ( DQ (I i ) faTupleMax) (Result 4.
For t=1 to T
5.
Lấy ra ảnh Ii chưa được lấy trong danh sách đã sắp thứ tự Tuplet
cùng với T độ đo khoảng cách DQ (I i ) ;
6.
IF aMax DQ (I i ) < aMax = DtQ (I i ) ;
7.
isDominated = false;
8.
While (not(isDominate)) Ij PF chưa được so sánh với Ii)
9.
IF( DQ (I i )) chuyển Ij từ PF vào PF_Next;
10.
End IF;
11.
IF(Ij Ii)

12.
isDominated = true;
13.
Chèn Ii vào PF_Next;
14.
End IF
15.
End While
16.
IF not(isDominated) chèn vào PF;
17.
aTupleMaxt =aMax; /* Đặt lại ngưỡng ở t */
18.
Đưa các ảnh PF mà aTupleMax vào ListResult;
19.
Result = Result+1;
20.
End For
21.
End While
22.
IF (Result23.
PF = PF_Next; PF_Next=θ ;
24.
For all Ii , Ij
PF mà DQ (I i ) f DQ (I j) thì chuyển Ij sang PF_Next;
Đưa các ảnh Ij
PF mà aTupleMax DQ (I i )vào ListResult;
25.

26.
End IF
27. End While

ISBN: 978-604-80-5076-4

53


Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020)

[12] Alberto Nonis, Marco Scortegagna , Alessandro
Nonis , Benedetto Ruperti, “PRaTo: A web-tool to select
optimal primer pairs for qPCR”, 2011, Elsevier Inc. All
rights reserved.

4.KẾT LUẬN

Trong bài báo này, phương pháp tiếp cận
Pareto trong khơng gian tìm kiếm sử dụng hệ thống
CBIR bằng cách sử dụng các mẫu được gắn nhãn
và dữ liệu đầu vào theo thời gian thực. Từ đó khắc
phục những hạn chế với các kỹ thuật mở rộng truy
vấn trong MARS. Để kiểm tra chức năng PRaTo tất
cả mẫu của các cặp từ các thí nghiệm đều được thu
thập
trongcơ
sở
dữ
liệu

qPCR
; [12] được truy xuất và
xử lý bằng thuật tốn PRaTo.Trong tương lai,
nhóm tác giả tiếp tục mở rộng phương pháp Pareto
để giảm tập hợp khơng gian tìm kiếm và áp dụng
cho hình ảnh mục tiêu truy xuất trong dữ liệu lớn.
Tài liệu tham khảo
[1] S. Agarwal, A. K. Verma, and N. Dixit, Content
based image retrieval using color edge detection and
discrete wavelet transform," in Issues and Challenges in
Intelligent Computing Techniques (ICICT), 2014
International Conference on. IEEE, 2014, pp. 368
[2] M. Arevalillo-Herraez, F. J. Ferri, and S. MorenoPicot, Improving distance based image re-trieval using nondominated sorting genetic algorithm," Pattern Recognition
Letters, vol. 53, pp. 109, 2015.
[3] G. Beliakov, A. Pradera, and T. Calvo,
Aggregation functions: a guide for practitioners. Springer,
2007, vol. 221.
[4] J. Chomicki, Querying with intrinsic preferences,"
in Advances in Database TechnologyEDBT 2002. Springer,
2002, pp. 34
[5] L. Fei-Fei, R. Fergus, and P. Perona, Learning
generative visual models from few training examples: An
incremental bayesian approach tested on 101 object
categories," Computer Vision and Image Understanding, vol.
106, no. 1, pp. 59, 2007
[6] P. Fishburn,Preference structures and their
numerical representations," Theoretical Computer Science,
vol. 217, no. 2, pp. 359, 1999.
[7] Y. Freund, R. Schapire, and N. Abe, A short
introduction to boosting," Journal-Japanese Society For Arti

cial Intelligence, vol. 14, no. 771-780, p. 1612, 1999.
[8] P. Hiremath, S. Shivashankar, and J. Pujari,
Wavelet based features for color texture classi ca-tion with
application to cbir," International Journal of Computer
Science and Network Security, vol. 6, no. 9A, pp. 124, 2006.
[9] K.-J. Hsiao, J. Calder, and A. O. Hero, Paretodepth for multiple-query image retrieval," Image Processing,
IEEE Transactions on, vol. 24, no. 2, pp. 583{594, 2015.
[10] J. Huang, S. R. Kumar, M. Mitra, W.-J. Zhu, and
R. Zabih, Image indexing using color correlograms," in
Computer Vision and Pattern Recognition, 1997.
Proceedings., 1997 IEEE Computer Society Conference on.
IEEE, 1997, pp. 762
[11] AfshanLatif, Aqs Rasheed, Umer Sajid, Jameel
Ahmed,
NoumanAli,
Naee
Iqbal
Ratyal,Bushra
Zafar, Saadat Hanif Dar,Muhammad Sajid, and Tehmina
Khalil, “Content-Based Image Retrieval and Feature
Extraction: A Comprehensive Review”, Mathematical
Problems in Engineering , 2019, pp.21.

ISBN: 978-604-80-5076-4

54