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

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