Tài liệu Một phương pháp chuẩn hóa các đặc trưng mức thấp áp dụng cho độ đo đánh hạng đa tạp trong truy vấn ảnh theo nội dung - Hoàng Xuân Trung: Công nghệ thông tin & Cơ sở toán học cho tin học
H. X. Trung, , N. V. Quyền, “Một phương pháp chuẩn hóa ảnh theo nội dung.” 162
MỘT PHƯƠNG PHÁP CHUẨN HÓA CÁC ĐẶC TRƯNG MỨC
THẤP ÁP DỤNG CHO ĐỘ ĐO ĐÁNH HẠNG ĐA TẠP TRONG
TRUY VẤN ẢNH THEO NỘI DUNG
Hoàng Xuân Trung1*, Đoàn Văn Hòa2*, Nguyễn Tân Ân3,
Hoàng Văn Quý4, Nguyễn Văn Quyền5
Tóm tắt: Trong vấn đề tra cứu ảnh dựa trên nội dung (CBIR), ảnh được biểu
diễn bằng nhiều đặc trưng mức thấp để mô tả màu sắc, kết cấu và hình dạng của
ảnh. EMR (Độ đo đánh hạng đa tạp hiệu quả) là một thuật toán học bán giám sát
trên các đặc trưng mức thấp của ảnh, đã được sử dụng hiệu quả trong CBIR. Sự kết
hợp nhiều đặc trưng ảnh khác nhau để xây dựng thuật toán EMR thường sử dụng
phép chuẩn hóa dữ liệu đặc trưng để cân bằng khoảng biến thiên của từng đặc
trưng. Bài báo này trình bày một phương pháp chuẩn hóa mới để xây dựng EMR.
Thực nghiệm đã chứng tỏ tính hiệu quả của thuật toán đề xuất cho vấn đề xây dựng
độ đo đánh hạng đa...
13 trang |
Chia sẻ: quangot475 | Lượt xem: 639 | Lượt tải: 0
Bạn đang xem nội dung tài liệu Một phương pháp chuẩn hóa các đặc trưng mức thấp áp dụng cho độ đo đánh hạng đa tạp trong truy vấn ảnh theo nội dung - Hoàng Xuân Trung, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Công nghệ thông tin & Cơ sở toán học cho tin học
H. X. Trung, , N. V. Quyền, “Một phương pháp chuẩn hóa ảnh theo nội dung.” 162
MỘT PHƯƠNG PHÁP CHUẨN HÓA CÁC ĐẶC TRƯNG MỨC
THẤP ÁP DỤNG CHO ĐỘ ĐO ĐÁNH HẠNG ĐA TẠP TRONG
TRUY VẤN ẢNH THEO NỘI DUNG
Hoàng Xuân Trung1*, Đoàn Văn Hòa2*, Nguyễn Tân Ân3,
Hoàng Văn Quý4, Nguyễn Văn Quyền5
Tóm tắt: Trong vấn đề tra cứu ảnh dựa trên nội dung (CBIR), ảnh được biểu
diễn bằng nhiều đặc trưng mức thấp để mô tả màu sắc, kết cấu và hình dạng của
ảnh. EMR (Độ đo đánh hạng đa tạp hiệu quả) là một thuật toán học bán giám sát
trên các đặc trưng mức thấp của ảnh, đã được sử dụng hiệu quả trong CBIR. Sự kết
hợp nhiều đặc trưng ảnh khác nhau để xây dựng thuật toán EMR thường sử dụng
phép chuẩn hóa dữ liệu đặc trưng để cân bằng khoảng biến thiên của từng đặc
trưng. Bài báo này trình bày một phương pháp chuẩn hóa mới để xây dựng EMR.
Thực nghiệm đã chứng tỏ tính hiệu quả của thuật toán đề xuất cho vấn đề xây dựng
độ đo đánh hạng đa tạp, phép chuẩn hóa mới đã tăng chất lượng CBIR so với các
phép chuẩn hóa thông dụng.
Từ khóa: Tra cứu ảnh dựa trên nội dung; Đặc trưng mức thấp; Chuẩn hóa đặc trưng mức thấp; Chuẩn hóa 3-
opt; EMR.
1. MỞ ĐẦU
Truy vấn ảnh dựa vào nội dung (CBIR) trở thành lĩnh vực nghiên cứu tích cực trong
những năm qua. Các hệ thống này thường trích rút các biểu diễn trực quan của ảnh và định
nghĩa các hàm đo độ tương tự của các ảnh để tra cứu theo yêu cầu.
Thông thường việc truy vấn ảnh dựa trên nội dung đòi hỏi phải kết hợp các thông tin
mô tả về màu sắc, kết cấu và hình dạng đồng thời. Mỗi vector đặc trưng trực quan trích rút
được từ một ảnh có các thành phần giá trị số có thể thuộc các khoảng số rất khác nhau, do
đó khi kết hợp nhiều đặc trưng biểu diễn cho các ảnh để xây dựng độ đo tương tự của các
ảnh chúng ta cần phải chuẩn hóa dữ liệu đặc trưng về một miền số chung là đoạn [0,1]
(xem [1, 2]).
Độ đo đánh hạng đa tạp [20] đo độ tương tự của các ảnh được sử dụng rộng rãi trong
CBIR. Với một giả định rằng mỗi điểm dữ liệu trong một không gian đặc trưng có một
mối quan hệ với các điểm dữ liệu khác tương tự trong không gian, Thuật toán trước hết
xây dựng một đồ thị có trọng số cho tất cả các điểm dữ liệu trong không gian đặc trưng ở
đó mỗi cạnh được gán một trọng số để biểu diễn mối liên quan dữ liệu giữa hai điểm. Đầu
tiên, điểm dữ liệu truy vấn ban đầu được gán một giá trị nhất định, các điểm dữ liệu còn lại
có liên quan được gán giá trị 0. Thứ hai, tất cả các điểm dữ liệu lan truyền xếp hạng của
chúng đến các điểm dữ liệu bên cạnh thông qua các đồ thị có trọng số. Quá trình lan
truyền của các điểm số xếp hạng lặp đi lặp lại cho đến khi hội tụ tới một tình trạng ổn định
toàn cục. Các điểm chính thức được xếp hạng đại diện cho việc giống nhau giữa điểm dữ
liệu và điểm truy vấn. Các điểm dữ liệu tương tự như các điểm truy vấn là những điểm xếp
hạng lớn nhất. Các đặc trưng mức thấp được sử dụng trong thuật toán đánh hạng đa tạp
EMR cũng cần sử dụng một phép chuẩn hóa khi tính trọng số của từng cạnh trong đồ thị
được xây dựng bởi thuật toán đánh hạng để tăng độ chính xác của kết quả đánh hạng.
Trong bài báo này chúng tôi đề xuất một phương pháp chuẩn hóa các đặc trưng mức thấp
để tăng hiệu quả của thuật toán đánh hạng đa tạp EMR, phép chuẩn hóa đề xuất thỏa mãn
ba tính chất sau:
(i) Không yêu cầu dữ liệu đặc trưng có phân bố Gaussian.
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN quân sự, Số 58, 12 - 2018 163
(ii) Bảo toàn thứ tự của từng thành phần của vector đặc trưng.
(iii) Dải biến thiên của mỗi thành phần vector đặc trưng trên đoạn [-1,1] được tối ưu hóa.
Phần còn lại của bài báo được tổ chức như sau. Phần 2, một số nghiên cứu liên quan sử
dụng kết hợp đặc trưng, chuẩn hoá đặc trưng. Phần 3 là đề xuất chuẩn hoá đặc trưng cải
tiến của chúng tôi. Các kết quả thực nghiệm đưa ra trong phần 4. Kết luận và hướng
nghiên cứu tiếp theo được trình bày trong phần 5.
2. NGHIÊN CỨU LIÊN QUAN
2.1. Các đặc trưng mức thấp trong CBIR và biểu diễn đối tượng ảnh
Trong CBIR, ảnh mầu hoặc ảnh đa cấp xám được biểu diễn bằng các đặc trưng mức
thấp thuộc nhiều bộ (bộ mô tả về mầu, bộ mô tả về kết cấu hoặc mô tả về hình dạng).
Về các đặc trưng trực quan được sử dụng trong CBIR xem chẳng hạn [8, 9, 10, 11, 12, 13,
2, 14, 15, 16, 17 ]. Dưới đây chúng tôi liệt kê một số đặc trưng mức thấp thông dụng trong
CBIR và trong bài báo này.
Đặc trưng mầu (color features)
Color Moments (vector đặc trưng 81 chiều): Mỗi ảnh được chia thành các vùng 3x3 và
ba moment màu color mean, color variance and color skewness được tính toán cho mỗi
vùng trong mỗi kênh màu HSV tương ứng [11].
Đặc trưng kết cấu (texture features)
Gabor Wavelets Texture (vector đặc trưng 120 chiều): Mỗi ảnh được biểu diễn bởi 40
ảnh con bởi áp dụng biến đổi Gabor với 5 mức tỉ lệ và 8 hướng. Sau đó ba moment sẽ
được tính toán cho mỗi ảnh con [17].
Local Binary Pattern (LBP, vector đặc trưng 59 chiều): Mỗi điểm ảnh được gán nhãn
dựa vào các láng giềng của nó trong cửa sổ 3x3 và được biểu diễn bởi một số nhị phân.
Histogram của các nhãn này được định nghĩa như là độ đo bất biến kết cấu [18].
Đặc trưng hình dạng (shape features)
Edge (vector đặc trưng 37 chiều): Với đặc trưng này, biểu đồ hướng biên được sử dụng.
Thông tin biên chứa trong ảnh được tạo ra và xử lý sử dụng thuật toán phát hiện biên. Biểu
đồ hướng biên sau đó được lượng tử hóa thành 36 bin với 10 độ cho mỗi bin. Một bin
được sử dụng để đếm số lượng các điểm ảnh không có thông tin cạnh [18].
GIST (Global Scene, vector đặc trưng 512 chiều): là một mô tả tổng hợp thông tin
gradient cho các phần khác nhau của ảnh. Với việc nhân chập ảnh với 32 bộ lọc Gabor tại
4 tỉ lệ và 8 hướng, 32 bản đồ đặc trưng cùng cỡ với ảnh gốc được tạo ra. Mỗi bản đồ đặc
trưng này sau đó được chia thành 16 vùng bởi lưới 4x4 và giá trị đặc trưng trung bình của
mỗi vùng được tính toán [18, 19].
2.2. Phép chuẩn hóa đặc trưng mức thấp
Một số phép chuẩn hoá hay được sử dụng trong CBIR [3] như chuẩn hóa min-max về
[0,1] hoặc chuẩn hóa3 về [-1,1]:
'
,
, ,
, ,
,
'
,
min
min max : ' , 1
m min
,dim( )i
ii
i j i j
E
i j
i j
i i j i i j
j
i
i
EE
f E
f
ax E
f f f j f
E
f
(1)
,',', ,
3
3 : ' , 1,dim( )
i j j
i ji i i i j
j
j if f f
m
f j f
f
f
(2)
, trong đó
def def
, ,, arj i j j i jm mean E v E .
Công nghệ thông tin & Cơ sở toán học cho tin học
H. X. Trung, , N. V. Quyền, “Một phương pháp chuẩn hóa ảnh theo nội dung.” 164
Chuẩn hóa theo min – max làm cho hầu hết thông thông tin hữu ích bị chuyển vào một
phạm vi rất hẹp trong [0,1] nếu giá trị ,m
i
i j
E
ax E >> ,min
i
i j
E
E , chuẩn hóa 3σ rải đều
trong [-1,1] nhưng phải yêu cầu dữ liệu đầu vào là một chuỗi Gaussian.
Gần đây trong [3], các tác giả cũng đã đề xuất một phép chuẩn hóa cải tiến của 3σ
được gọi là 3σ-FCM. Phép chuẩn này không yêu cầu dữ liệu đầu vào là một chuỗi
Gaussian, và khi áp dụng đã tăng hiệu quả của phép truy vấn ảnh.
Tuy nhiên 3-FCM vẫn còn điểm hạn chế, đó là miền giá trị của các thành phần
vector sau khi biến đổi vẫn có thể hẹp hơn đáng kể trong đoạn [-1,1] như hình 1.a và 1.b
đã chỉ rõ.
(a)
(b)
Hình 1. Kết quả chuẩn hoá theo 3-FCM. (a) Gabor Wavelet Texture. (b) Gist [3].
2.3. Thuật toán đánh hạng đa tạp EMR [20]
Giả sử V={0,1,,n} và QE Q E là tập n+1 ảnh, Q là ảnh truy vấn.
Chúng ta biểu diễn một đồ thị trọng số G=(V,Ɛ,W) và Ɛ VxV là tập cạnh. Các trọng số
được biểu diễn bằng bằng một ma trận (n+1) x (n+1) W = (wij), ở đó wij=0 nếu (i,j) Ɛ và
nếu có quan hệ kề nhau giữa , 1
T
i t t
E
và , 1
T
j t t
E
thì
2ij , ,1 1w exp ,
TT
i t j tt t
d E E
(3)
Trong thuật toán EMR [20] các tác giả đã xây dựng phép đánh hạng đa tạp sử dụng
quan hệ kề nhau của một vector ảnh dựa trên các điểm neo (anchor) thay vì dựa trên các
vector ảnh k-láng giềng của từng vector ảnh.
3. KỸ THUẬT ĐỀ XUẤT
Cực đại hóa dải biến thiên của phép chuẩn hóa
Cho trrước một cơ sở dữ liệu (CSDL) đặc trưng mức thấp , 1t i i nE E , sử dụng FCM
(về FCM, xem [3, 21-23]) ta phân cụm Et thành C cụm, thuật toán lặp FCM cực tiểu hóa
hàm mục tiêu sau:
( , )tJ V
2
, ,
1 1
min
n C
p
c i t i c
i c
E V
(4)
, trong đó các hằng số p = p(t) > 1, C=C(t) , 2N C , ,dim( )t t im E , 1 i n và độ
đo khoảng cách Euclid,
2
, ,t i t c
E V , ,
1
2
[ ] [ ]
tm
t i t c
j
E j V j
.
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN quân sự, Số 58, 12 - 2018 165
Sau khi phân cụm FCM dữ liệu vector đặc trưng mức thấp t (t{Color moment, LBP,
Gabor Wavelet texture, Edge, GIST} chẳng hạn) của CSDL ảnh E ta nhận được tập các
vector tâm t,c 1 ( ){V } c C t
và bảng các giá trị độ thuộc là , , 1 ,1 ( ){ } tt j c j m c C t . Tiếp theo
chúng ta tính giá trị chuẩn hóa 3 thông thường với từng cụm và kết hợp các giá trị này lại
thành một giá trị đầu ra duy nhất dạng tuyến tính như sau :
Giả sử
1t,j
x
t
m
jt
x
là vector dữ liệu đầu vào, khi đó , or , or , 1
t
m
t n m t n m j j
x x
là vector chuẩn
hóa được xác định có dạng như sau:
or ,
, , , ,
1 1
, , , ,
1,min max ,
3 3
def
n m j
j t c j j t c j
tt t
c C c C
t c j t c j
x j m
x V x V
a b
(5)
, trong đó độ lệch chuẩn
, ,t c j
ở cụm c (1≤c≤C) được tính bằng công thức sau:
def 2
, , , , , ,
1 1
2
, , , ,
2
, ,, ,
1
,
1
,1 , / /( )
n n
p p
t t c j c i t c j c i
i i
t i j t
n n
p p
t c i t c i t c j
i i
i jj m E V VE
(6)
và các tham số at,j, bt,j thỏa mãn:
0 < at < 1, -0.5 bt 0.5 (7)
Phép chuẩn hóa được thiết kế để đảm bảo có không quá 100* %out vector của
CSDL đặc trưng mức thấp bộ t tại mỗi thành phần vector tj 1,dim(E ) rơi ra ngoài đoạn
[-1,1] và độ trải rộng của tập thành phần j của tập vector CSDL trên [-1,1] là lớn nhất.
Với mỗi hệ số thực at, bt và thành phần đặc trưng tj 1,dim(E ) , chúng ta ký hiệu
,
, , ,
# / 1, * [-1,1]
t t
def
t t j t
t a b j
i i n a d b
C
n
(8)
, trong đó:
, , , , , , , ,
,
1 1
, , , ,
min max
3 3
def
i t j t c j i t j t c j
t j
c C c C
t c j t c j
E V E V
d
(9)
và độ trải trên đoạn [-1,1] của tập dữ liệu đặc trưng bộ t, thành phần j sẽ được lấy trung
bình trên toàn bộ t của CSDL E và tất cả các thành phần 1,dim tj E như sau:
, ,
,
2
, ,
1 1 dim( )
* [ 1,1]
, ,
( * )
t
t i j
t t j
n
t t i j t
i j Edef
a d b
t a b
a d b
R
n
(10)
Như vậy việc xác định các hệ số thực at,bt để xây dựng phép chuẩn hóa đặc trưng bộ t
cho một CSDL đặc trưng mức thấp E có thể chuyển thành việc giải bài toán tối ưu đa mục
tiêu xác định hệ số at, bt có các hàm mục tiêu và các ràng buộc như sau:
, , , ax, 1,dim( )t tt a b j tR m j E
(11)
với ràng buộc:
, , , 1,dim( )t tt a b j out tC j E
(12)
Công nghệ thông tin & Cơ sở toán học cho tin học
H. X. Trung, , N. V. Quyền, “Một phương pháp chuẩn hóa ảnh theo nội dung.” 166
Nói chung đây là một bài toán tối ưu đa mục tiêu có dạng đặc biệt, các ràng buộc (12)
là cho các đại lượng rời rạc và các hàm mục tiêu (11) được tính ở công thức (10) cũng có
nhiều điều kiện, vì vậy việc giải bài toán tối ưu đa mục tiêu này là cần một phương pháp
riêng. Để giải bài toán này ý tưởng của chúng tôi là thiết kế một hàm mục tiêu bị chặn
Ft(a,b) cho bài toán tối ưu một mục tiêu sau: được tạo thành thông qua 3 bước thiết kế như
sau:
Bước 1: Kết hợp các giá trị mục tiêu , , , , 1,dim( )t tt a b j tR j E vào một hàm mục tiêu bị
chặn như sau ( , ) mintG a b , trong đó
, , ,
2
, ,
1 1 dim [ 1,1]
1
( , ) (0,1]
( )
1
*dim
t i t i j
def
t n
t i j
i j E ad b
t
G a b
ad b
n E
(13)
Bước 2: Chuyển các ràng buộc (12) thành dạng giá trị “phạt” cộng thêm vào hàm mục
tiêu, ràng buộc (12) được thỏa mãn đầy đủ nghĩa là các giá trị cộng thêm này là 0, và tại
giá trị hàm mục tiêu được xấp xỉ nhỏ nhất thì khả năng là không có “phạt”. Chúng ta có
thể phát biểu chính xác dạng phạt như sau:
“Nếu tại thành phần j của vector đặc trưng bộ t xác suất giá trị chuẩn hóa rơi ra ngoài [-
1,1] của n vector đặc trưng bộ t của CSDL đầu vào mà vượt quá αout thì giá trị phạt là 1,
trái lại là 0 (không phạt)”.
Bước 3: Kết hợp các giá trị phạt vào hàm mục tiêu Gt(a,b), ta có hàm một mục tiêu
( , ) mintF a b không còn ràng buộc (12), trong đó
, , ,
t , ,
2
, ,
1 1 dim [ 1,1]
1
( , ) # j 1,dim(E )/# 1, / * [ 1,1] *
( * )
1
*dim
t i t i j
t t i j outn
t i j
i j E ad b
t
F a b i n a d b n
a d b
n E
(14)
Nhận xét : Hàm Ft(a,b) được thiết kế theo nguyên tắc phạt (tăng thêm giá trị 1.0) tại mỗi
thành phần 1,dim( )tj E mà có lớn hơn 100* %out vector của CSDL đặc trưng mức
thấp bộ t tại thành phần vector rơi ra ngoài đoạn [-1,1]. Như vậy Ft(a,b) sẽ tăng khi có
nhiều thành phần 1,dim( )tj E mà có lớn hơn 100* %out vector của CSDL đặc
trưng mức thấp bộ t tại thành phần vector rơi ra ngoài đoạn [-1,1]
Mệnh đề 1.
(i) 0 ( , ) 1 dim( ) ,t tF a b E a b .
(ii) Nếu Ft(a,b) < 1 thì với mỗi thành phần j trong vector đặc trưng bộ t, 1,dim( )tj E ,
số lượng vector đặc trưng bộ t trong CSDL , 1t i i nE sau khi biến đổi theo công thức
dạng (10) , rơi ra ngoài đoạn [-1,1] không vượt quá n*out.
Chứng minh.
(i) Hiển nhiên.
(ii) Do Ft(a,b) < 1 nên
t , ,# j 1,dim(E )/# 1, / [ 1,1] * 0t i j outi n ad b n ,
nghĩa là tập t , ,j 1,dim(E )/# 1, / [ 1,1] *t i j outi n ad b n
Nên 1,dim( )tj E , ta có , ,# 1, / [ 1,1] *t i j outi n ad b n .
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN quân sự, Số 58, 12 - 2018 167
Tức là số vector ,t iE
có , ,t i jd mà , , [ 1,1]t i jad b không vượt quá n*out.
Hình 2. Mặt Ft(a,b) của đặc trưng Color moments 81 chiều được chia lưới
trên [0,1] x [-0.5,0.5], bước chia 0.05.
Kỹ thuật xây dựng phép chuẩn hóa với tham số tối ưu được thực hiện theo thuật toán 1
như sau:
Thuật toán 1. Phép chuẩn hóa 3-opt (Phép chuẩn hóa với tham số tối ưu hóa).
Input:
1 i ;1, t Tt i n
E
, đặc trưng bộ thứ t, hằng số p = p(t) > 1, C = C(t) , 2N C ,
,dim( ), 1,t t im E i n , ngưỡng phầ n trăm rơi ra ngoài [-1,1] của các thành phần vector
sau khi chuẩn hóa out
Output:
1 i,
N o rm
t i n
E
dữ liệu đã được chuẩn hoá, các tâm , 1 tt c c CV ,
, , 1 ,1 t tt c j c C j m và tham số at, bt.
Bước 1: ,i, 1 i ;1 t T, t c nt tFCM C Ep ta được tập các vector tâm , 1t
C
t c c
V
, và ma trận độ
thuộc , , 1 ,1tt c i c C i n
Bước 2: Tính , , 1 ,1t tt c j c C j m theo công thức (6)
Bước 3: Tính , , 1 ,1t tt c j c C j md theo công thức (9)
Bước 4: Giải tối ưu ( , ) mintF a b , xác định được at (0,1), bt [-0.5,0.5], ở đây
Ft(a,b) xác định theo công thức (14):
4.1: Khởi đầu
1
1
a
C
, 0b .
4.2: Lặp, thay đổi a và b để Ft(a,b) đạt tới giá trị xấp xỉ giá trị nhỏ nhất. (xem [26])
4.3: Gán at = a, bt = b.
Bước 5: Chuẩn hóa về [-1,1]:
Lặp với mỗi vector đặc trưng bộ t của CSDL ,t iE
: lặp với mỗi thành phần j
1, tj m của vecror xt= ,t iE
tính or, , ,
norm
t n t i jmx E theo công thức (5) sử dụng hai hệ số at, bt.
Công nghệ thông tin & Cơ sở toán học cho tin học
H. X. Trung, , N. V. Quyền, “Một phương pháp chuẩn hóa ảnh theo nội dung.” 168
Bước 6: Chuẩn hóa về [0,1]:
Lặp với mỗi vector
or
,
n m
t iE
: 1, tj m tính lại
or, ,
, ,
max , 1 1
min ,1
2
n
t i jnorm
t i j
mE
E
.
Trả về: ,
1 i
norm
t i
n
E
, ,
1 t
t c
c C
V
, , , 1 ,1t tt c j c C j m
, at và bt.
Thuật toán 1 có độ phức tạp O(n), ở đây n là số lượng ảnh của CSDL ảnh E.
Thuật toán đánh hạng đa tạp EMR gốc được thay đổi lại khi sử dụng phép chuẩn hóa 3-
opt như sau:
Thuật toán 2. EMR-3-opt (Thuật toán đánh hạng EMR sử dụng các đặc trưng mức thấp
được chuẩn hóa bằng 3-opt).
Input:
1 1, , i
Norm
t t T ni
E
dữ liệu đã được chuẩn hoá, các tâm , 1 ,1 tt c t T c CV ,
, , 1 1, ,1 t tt c j ct C j mT và tham số tối ưu 1{ }t t Ta , 1{ }t t Tb .
Q=
1 tt T
Q
dữ liệu đặc trưng mức thấp của ảnh truy vấn.
nAnchor: số lượng điểm neo của thuật toán EMR, tham số a (0,1) (a ≈ 1) .
Output: r=
1
, [0,1] 1,ii ni r i nr là thứ hạng tương tự với ảnh Q của ảnh Ei trong
CSDL ảnh E.
Bước 1: Không phụ thuộc truy vấn Q, gọi thủ tục EMR gốc cho
1 1, , i
Norm
t t T ni
E
với
nAnchor điểm neo và ma trận kề W=(wij) để thu được ma trận trọng số Z kích thước
nAnchor x n, ma trận tâm aLandMark gồm nAnchor vector đặc trưng m chiều
(
,1
1
dim( )
T
t
t
m E
).
Bước 2: Đặt
1
Norm Norm
Tt t
Q Q
, trong đó
, , , , , ,or
,
1 1
, , , ,
1,min max ,
3 3
def
t j t c j t j t c jN m
tt j t t
c C c C
t c j t c j
j m
Q V Q V
Q a b
theo công thức (5)
Sau đó gán mới
or,
,
max , 1 1
min ,1
2
n
t jnorm
t j
mQ
Q
.
Bước 3: Mở rộng ma trận Z theo EMR[20] : Sử dụng nAnchor giá trị khoảng cách của
norm
tQ với các phần tử neo của aLandMark (sử dụng khoảng cách Euclid). Chúng ta thu
được ma trận trọng số ZQ mới có kích thước nAnchor x (n+1).
Bước 4: Đặt rQ= n+11 1 , 0 1, , r =1.0ii in r ir n . Từ ma trận trọng số ZQ chúng ta xác
định vector thứ hạng
*
Qr bằng thuật toán EMR [20].
Bước 5: Trả về
*
, 1{r }Q i i nr .
4. THỰC NGHIỆM
Chúng tôi tiến hành các thực nghiệm trên hai tập dữ liệu Corel10K [24, 27], Oliva
[25]. Các tập dữ liệu này được tổ chức thành các lớp ngữ nghĩa theo cách con người nhận
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN quân sự, Số 58, 12 - 2018 169
thức về độ tương tự. Mỗi lớp biểu diễn một chủ đề ngữ nghĩa khác nhau, các ảnh trong
cùng một lớp được xem là liên quan.
Tập dữ liệu thứ nhất Corel10K (ký hiệu là DS1), là tập con của cơ sở dữ liệu Corel
photo gallery. Nó gồm 10000 ảnh được phân thành 100 lớp với 100 ảnh trên một lớp. Hình
3 chỉ ra một số mẫu ảnh trong tập dữ liệu này.
Hình 3. Một số mẫu trong tập dữ liệu ảnh DS1.
Tập dữ liệu thứ hai Oliva (ký hiệu là DS2) bao gồm hơn 2600 ảnh được tổ chức thành 8
lớp: “Coast & Beach”, “open country”, “forest”, “Mountain, highway street”, “city
center”, “Tall building” như chỉ ra trong hình. 4, mỗi lớp có từ 260 đến 409 ảnh.
Hình 4. Một số mẫu trong tập dữ liệu ảnh DS2.
4.1. Trích chọn đặc trưng và chỉ số đánh giá
Trong các thí nghiệm, chúng tôi sử dụng 5 đặc trưng toàn cục để mô tả một ảnh: Color
Moments, LBP, Gabor Wavelets Texture, Edge và GIST.
Tất cả các đặc trưng này được chuẩn hóa để mỗi thành phần nằm trong khoảng [-
1,1] theo thuật toán 1. Khoảng cách Euclid sẽ được sử dụng để tính khoảng cách giữa
các đặc trưng.
Như phần 1 đã đề cập, dữ liệu các bộ đặc trưng mức thấp không có phân bố Gauss.
Chúng tôi sẽ chứng tỏ bằng thực nghiệm kết luận này. Thật vậy, chúng tôi tôi đã tính
các chỉ số skewness và kurtosis của CSDL các bộ đặc trưng mức thấp của tập ảnh DS1
như bảng 1 dưới đây, trong đó phần chữ đậm thể hiện đặc trưng có tham số thể hiện
phân bố Gaussian.
Bảng 1. Giá trị thuộc tính của các đặc trưng trong DS1.
Dữ liệu đặc trưng Giá trị Skewness Giá trị Kurtosis
Color Moments 0.46823 3.0184
LBP 1.1004 5.8707
Gabor Wavelets Texture 0.81677 4.2603
Edge 2.7836 14.175
GIST 1.6962 6.8228
Do phép chuẩn hóa đã đặt ngưỡng tỉ lệ số phần tử rơi ra ngoài đoạn [-1,1] của các thành
phần vector là không vượt quá out , một cách tự nhiên, chúng ta có chỉ số đánh giá hiệu
quả phép chuẩn hóa vector dữ liệu đặc trưng mức thấp bộ t về đoạn [-1,1], cụ thể như sau:
, , ,
2
, ,
1 1 dim [ 1,1]
( )
*dim
t i t i j
n
t i jdef
i j E ad b
t
ad b
RMS
n E
(15)
Công nghệ thông tin & Cơ sở toán học cho tin học
H. X. Trung, , N. V. Quyền, “Một phương pháp chuẩn hóa ảnh theo nội dung.” 170
Chỉ số RMS nói lên độ trải trong đoạn chuẩn hóa [-1,1]. RMS càng lớn chứng tỏ phép
chuẩn hóa càng tốt theo nghĩa độ trải trong đoạn [-1,1] của mọi tập thành phần
, , , 1,dim( )tt i jE j E
là lớn.
4.2. Phép giải tối ưu hàm mục tiêu
Để chọn tham số tối ưu trong bước 4 của thuật toán 1 đề xuất chúng ta có thể sử dụng
một số phương pháp khác nhau như giải thuật di truyền, hoặc phép duyệt vét cạn chia lưới
miền giá trị của tham số. Tuy nhiên bằng thực nghiệm chúng tôi thấy phương pháp kiểu
thủ tục fminsearch của Matlab [26] là phù hợp hơn cả. Quá trình lặp tối ưu hàm mục tiêu
là hội tụ và thường giá trị hội tụ của hàm mục tiêu là thuộc khoảng (0,1) là giá trị lý tưởng
theo mệnh đề 1.
4.3. Các kết quả và luận giải
Bảng 2 và bảng 3 dưới đây trình bày các tham số tuyến tính at, bt tính được cho từng bộ
đặc trưng mức thấp đối với tập dữ liệu ảnh DS1, và chỉ số RMS thể hiện độ trải rộng trong
đoạn chuẩn hóa [-1,1] của 3-opt.
Bảng 2. Tham số tối ưu của 3-opt cho tập DS1 thực hiện
với FCM có số cụm C = 10, out=0.02 (2%).
Dữ liệu đặc trưng at bt
Color Moments 0.5138 0.0096
LBP 0.2315 0.0037
Gabor Wavelets Texture 0.4290 -0.2294
Edge 0.0755 0.500
GIST 0.3377 -0.4953
Bảng 3. Giá trị chỉ số RMS của 3-opt và 3-FCM các đặc trưng mức thấp của DS1
thực hiện với FCM có số cụm C = 10.
Dữ liệu đặc trưng RMS của 3-FCM RMS của 3-opt
Color Moments 0.065946 0.36407
LBP 0.11644 0.28731
Gabor Wavelets Texture 0.089657 0.3881
Edge 0.12538 0.53337
GIST 0.060937 0.54033
Hình 5.a và 5.b dưới đây cho thấy rõ độ trải rộng của các giá trị đặc trưng GIST được
bằng chuẩn hóa bằng 3-opt là rộng hơn so với 3-FCM.
(a)
(b)
Hình 5. Chuẩn hóa đặc trưng GIST của DS1 với số cụm C=10, 3-FCM (a) và 3-opt (b).
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN quân sự, Số 58, 12 - 2018 171
Phép chuẩn hóa 3-FCM phụ thuộc mạnh vào tham số số cụm, tuy nhiên 3-opt thì
không hoàn toàn phụ thuộc vào tham số này. Hình 6.a và 6.b cho thấy rõ điều đó khi chuẩn
hóa dữ liệu vector GIST với giá trị số cụm được chọn là C=5.
(a)
(b)
Hình 6. Chuẩn hóa đặc trưng GIST của DS1 với số cụm C=5, 3-FCM (a) và 3-opt (b).
Điều này là do bản chất hàm mục tiêu Ft(a,b) ở công thức (15) được tối ưu để dữ liệu
thành phần vector sau khi chuẩn hóa trải rộng trên đoạn [-1,1].
4.4. Hiệu quả của 3-opt trong CBIR
Chúng tôi thực nghiệm so sánh hiệu quả của EMR-3-opt và EMR-3-FCM (thay thế
trong EMR-3-opt bằng phép chuẩn hóa 3-FCM). Khi thực hiện thuật toán EMR chúng
tôi vẫn sử dụng các giá trị tham số như trong [20], cụ thể số điểm neo lân cận của một
vector đặc trưng là r=5, a = 0.99. Với tập ảnh DS1 chúng tôi chọn nAnchor là 2000 và với
tập DS2 chúng tôi chọn là 50.
Hình 7 và hình 8 dưới đây minh họa kết quả truy vấn ảnh sử dụng độ đo tương tự ảnh
được đánh hạng bằng EMR sử dụng hai phép chuẩn hóa khác nhau. Kết quả cho thấy
EMR-3-opt có ảnh kết quả truy vấn phù hợp hơn so với EMR-3-FCM.
Hình 7. Truy vấn hình ảnh 170012.jpg trong tập DS1 sử dụng EMR-3-FCM,
xuất hiện 3 ảnh không liên quan trong 20 ảnh có thứ hạng cao nhất.
Công nghệ thông tin & Cơ sở toán học cho tin học
H. X. Trung, , N. V. Quyền, “Một phương pháp chuẩn hóa ảnh theo nội dung.” 172
Hình 8. Kết quả truy vấn sử dụng EMR-3-opt, tất cả trong số 20 ảnh
có thứ hạng cao nhất đều liên quan.
Để đánh giá khách quan hiệu quả của thuật toán EMR-3-opt đề xuất, cũng như trong
công trình [28,7], chúng tôi sử dụng một chỉ số tương tự độ đo Average Precision (chúng
tôi vẫn gọi là AP) được đề xuất bởi NISTTREC video (TRECVID), AP được định nghĩa
trung bình của giá trị độ chính xác thu được sau mỗi ảnh liên quan được tra cứu.
Tập ảnh truy vấn Q được chọn ngẫu nhiên với số lượng 10% theo từng chủ đề của tập
ảnh thử nghiệm DS1 và tập DS2.
Với mỗi ảnh truy vấn q Q , sử dụng các độ đo tương tự cho bởi EMR-3-opt và
EMR-3-FCM, chúng ta chọn N = 100 ảnh có độ tương tự cao nhất. Giá trị độ chính xác
là trung bình tỷ lệ giữa số ảnh liên quan trong N ảnh được trả lại bởi các giá trị tương tự
với từng ảnh q. Gọi tập các phần tử liên quan đến truy vấn q Q là 1 2, ,..., mjd d d , giá
trị mAP trên toàn bộ các truy vấn được tính toán như sau:
1
1
( ) *100
Q
j
j
m
AP Q
Q N
(16)
Bảng 4. AP với 20 ảnh trả về của hai phương pháp đánh hạng.
Tập ảnh AP của EMR-3-FCM AP của EMR-3-opt
DS1 65,3% 69,1%
DS2 73,3% 75,4%
Các kết quả thực nghiệm trên cho thấy thuật toán đánh hạng EMR-3-opt cho hiệu quả
vượt hơn thuật toán EMR-3-FCM. Khi các dữ liệu đặc trưng mức thấp được chuẩn hóa
với độ trải rộng cao trong đoạn chuẩn hóa [-1,1] độ đo tương tự cho bởi thuật toán EMR
đã được học ma trận trọng số tối ưu hơn và dẫn đến kết quả đánh hạng được cải thiện.
5. KẾT LUẬN
Bài báo đã đề xuất một phương pháp chuẩn hóa dữ liệu vector đặc trưng mức thấp,
bảo toàn thứ tự ở các thành phần vector với tham số được chọn để tối ưu độ trải rộng trên
đoạn chuẩn hóa [-1,1], không phụ thuộc tham số số cụm được sử dụng cùng với thuật toán
FCM. Thuật toán EMR đã được cải thiện khi sử dụng phép chuẩn hóa đề xuất..
Thực nghiệm với các CSDL ảnh lớn như Corel, Oliva dựa trên đánh giá trực quan và
chỉ số đánh giá khách quan, kết quả truy vấn ảnh thực tế đã chứng tỏ hiệu quả của phép
đánh hạng tương tự của thuật toán EMR-3-opt.
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN quân sự, Số 58, 12 - 2018 173
TÀI LIỆU THAM KHẢO
[1]. Cong, Kidiyo Kpalma, and Joseph Ronsin. "Color textured image retrieval by
combining texture and color features." Signal Processing Conference (EUSIPCO),
2012 Proceedings of the 20th European. IEEE, 2012
[2]. Rui, Yong, et al. "Relevance feedback: a power tool for interactive content-based
image retrieval." Circuits and Systems for Video Technology, IEEE Transactions on
8.5 (1998): 644-655.
[3]. Vũ Văn Hiệu, Ngô Hoàng Huy, Ngô Quốc Tạo, Nguyễn Hữu Quỳnh, “Một phương
pháp mới chuẩn hóa dữ liệu và hiệu chỉnh trọng số cho tổ hợp đặc trưng trong tra
cứu ảnh theo nội dung”. Tạp chí Công nghệ Thông tin và Truyền thông, tập V-1, Số
15(35) 6-2016, trang 63-75.
[4]. Ciocca, Gianluigi, and Raimondo Schettini. "A relevance feedback mechanism for
content-based image retrieval." Information processing & management 35.5 (1999):
605-632.
[5]. Mehrotra, Sharad, et al. "Multimedia analysis and retrieval system." Proc. of The 3rd
Int. Workshop on Information Retrieval Systems. 1997.
[6]. Ortega, Michael, et al. "Supporting similarity queries in MARS." Proceedings of the
fifth ACM international conference on Multimedia. ACM, 1997.
[7]. Ngo Truong Giang, Ngo Quoc Tao, Nguyen Duc Dung and Ngo Hoang Huy,
“LEARNING INTERACTION MEASURE WITH RELEVANCE FEEDBACK IN
IMAGE RETRIEVAL”. Journal of Computer Science and Cybernetics.
[8]. Smith, John R., and Shih-Fu Chang. "VisualSEEk: a fully automated content-based
image query system." Proceedings of the fourth ACM international conference on
Multimedia. ACM, 1997.
[9]. Gudivada, Venkat N., and Vijay V. Raghavan. "Content based image retrieval
systems." Computer 28.9 (1995): 18-22.
[10]. Deng, Yining, et al. "An efficient color representation for image retrieval." Image
Processing, IEEE Transactions on 10.1 (2001): 140-147.
[11]. Jose, Sebin, and Philumon Joseph. "Content based Image Retrieval System with
Watermarks and Relevance Feedback." International Journal of Computer
Applications 99.11 (2014): 1-6.
[12]. Swain, Michael J., and Dana H. Ballard. "Color indexing." International journal of
computer vision 7.1 (1991): 11-32.
[13]. Rui, Yong, Thomas S. Huang, and Sharad Mehrotra. "Content-based image retrieval
with relevance feedback in MARS." Image Processing, 1997. Proceedings.,
International Conference on. Vol. 2. IEEE, 1997.
[14]. Tamura, Hideyuki, Shunji Mori, and Takashi Yamawaki. "Textural features
corresponding to visual perception." Systems, Man and Cybernetics, IEEE
Transactions on 8.6 (1978): 460-473.
[15]. Mao, Jianchang, and Anil K. Jain. "Texture classification and segmentation using
multiresolution”.
[16]. Ohanian, Philippe P., and Richard C. Dubes. "Performance evaluation for four
classes of textural features." Pattern recognition 25.8 (1992): 819-833.
[17]. T. Ojala, M. Pietikainen, and D. Harwood. “A comparative study of texture measures
with classification based on feature distributions”. 29(1):51–59, January 1996.
[18]. Jianke Zhu, Steven C.H. Hoi, Michael R. Lyu and Shuicheng Yan,"Near-Duplicate
Keyframe Retrieval by Nonrigid Image Matching," ACM Multimedia'2008.
[19]. 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”. IEEE. CVPR 2004, Workshop on Generative-Model Based Vision. 2004
Công nghệ thông tin & Cơ sở toán học cho tin học
H. X. Trung, , N. V. Quyền, “Một phương pháp chuẩn hóa ảnh theo nội dung.” 174
[20]. Bin Xu, Jiajun Bu,Chun Chen, Can Wang,Deng Cai,and Xiaofei He, “EMR: A
Scalable Graph-based Ranking Model for Content-based Image Retrieval”, IEEE
TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 27,
NO. 1, JANUARY 2015.
[21]. Bezdek, James C. “Pattern recognition with fuzzy objective function algorithms”.
Springer Science & Business Media, 2013.
[22]. Bhanu, Bir, and Anlei Dong. "Concepts learning with fuzzy clustering and relevance
feedback." Engineering Applications of Artificial Intelligence 15.2 (2002): 123-138.
[23]. Yang, Miin-Shen, Pei-Yuan Hwang, and De-Hua Chen. "Fuzzy clusterinsg algorithms
for mixed feature variables." Fuzzy Sets and Systems 141.2 (2004): 301-317.
[24]. Z.-H. Zhou, K.-J. Chen, and H.-B. Dai. “Enhancing relevance feedback in image
retrieval using unlabeled data”. ACM Transactions on Information Systems,
24(2):219–244, 2006.
[25]. Hoi, S.C.H.; Lyu, M.R.; Rong Jin, "A unified log-based relevance feedback scheme
for image retrieval," in Knowledge and Data Engineering, IEEE Transactions on ,
vol.18, no.4, pp.509-524, April 2006.
[26]. https://www.mathworks.com/help/matlab/math/optimizing-nonlinear-functions.html
[27].
[28]. Wu, Y., Zhang, A.: “A Feature Re-weighting Approach for Relevance Feedback in
Image Retrieval”, Special issue on Segmentation, Description, and Retrieval of
Video Content, Rochester NewYork (September 2002).
ABSTRACT
A NORMALIZATION METHOD FOR MULTIPLE LOW-LEVEL FEATURES
APPLIED TO MANIFOLD RANKING IN CONTENT BASED IMAGE RETRIEVAL
In CBIR, the image is represented by many low-level features that describe the
color, texture and shape of the image. The combination of different image features
in global similarity measurements requires normalized data sets. In this paper we
proposed a new normalization method for vector number data such as the low level
features of color images. Experimentation has shown the effectiveness of the
proposed algorithm for normalization of the low level features. The dynamic range
of the low level features data is normalized on the [-1,1] segment that is wider than
the corresponding 3sigma-FCM normalization interval. Besides, the experiment
also demonstrates that the new normalization method also increases CBIR quality
when combined with algorithms for measuring analogue images such as EMR.
Keywords: CBIR; Low level features; EMR; 3sigma-opt.
Nhận bài ngày 05 tháng 10 năm 2018
Hoàn thiện ngày 04 tháng 12 năm 2018
Chấp nhận đăng ngày 11 tháng 12 năm 2018
Địa chỉ: 1 Đại học Kinh doanh và Công nghệ Hà Nội;
2 Viện CNTT, Viện Khoa học và Công nghệ quân sự;
3 Học viện Quản lý giáo dục;
4 Đại học Hồng Đức, Thanh Hóa;
5 Đại học Hải Phòng.
* Email: trungvnit@gmail.com; doanvanhoa@gmail.com.
Các file đính kèm theo tài liệu này:
- 19_trung_7836_2150559.pdf