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 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: [email protected]; [email protected].