Luận án Nâng cao độ chính xác tra cứu ảnh dựa vào nội dung sử dụng kỹ thuật điều chỉnh trọng số hàm khoảng cách

ọng chiều đặc trưng, tính độ quan trọng của mỗi truy vấn và tìm các đại diện cụm được thực hiện để cho ra giá trị độ quan trọng chiều đặc trưng, giá trị độ quan trọng của mỗi truy vấn và các đại diện cụm. Các giá trị này sẽ giúp cải tiến việc tính toán ra các điểm truy vấn tối ưu. Các điểm truy vấn tối ưu ở trên sẽ được dùng để truy vấn ra tập ảnh được tra cứu. Nếu người dùng thỏa mãn, tập T ru y v ấn T ín h to án Tính toán Phản hồi Sắp xếp Phân cụm gia tăng Các cụm Các điểm truy vấn Độ quan trọng đặc trưng Độ quan trọng truy vấn Độ tương tự Tập ảnh được tra cứu Tập phản hồi Cơ sở dữ liệu đặc trưng Véc tơ đặc trưng Ảnh truy vấn Các biểu diễn Đại diện cụm Kết quả 34 ảnh được tra cứu sẽ là tập kết quả cuối cùng. Ngược lại, người dùng sẽ tiếp tục phản hồi. Quá trình này có thể được lặp lại nhiều lần. Phần tiếp theo của luận án sẽ trình bày chi tiết phương pháp đề xuất. Phần tiếp theo cần có một số định nghĩa, do đó luận án đưa ra một số định nghĩa ở đây. Định nghĩa 2.1 (Tập đặc trƣng). Một tập đặc trưng F gồm có N bộ đặc trưng, mỗi bộ gồm m thành phần, mỗi thành phần là một giá trị thực. { } (2.1) Định nghĩa 2.2 (Không gian đặc trƣng). Một không gian đặc trưng FS gồm m chiều, mỗi chiều tương ứng với một thành phần thực của bộ đặc trưng t (t=1..N) thuộc tập đặc trưng F, mỗi điểm pt (t=1..N) trong không gian FS tương ứng với một bộ đặc trưng trong F. { } (2.2) Định nghĩa 2.3 (Không gian đặc trƣng thứ i). Một không gian đặc trưng thứ i, ký hiệu là F , là một không gian đặc trưng gồm n chiều, mỗi điểm trong không gian này được ký hiệu là (t=1..N) có n tọa độ. { } (2.3) Định nghĩa 2.4 (Đo khoảng cách giữa hai điểm trong không gian đặc trƣng FS i ). Đo khoảng cách giữa hai điểm và (k,l=1..N) và kl ,được ký hiệu là D( ), là độ đo khoảng cách nào đó. Ý tưởng chính của phương pháp đề xuất là không đặt các ảnh (bao gồm cả ảnh cơ sở dữ liệu và ảnh truy vấn) trong cùng một không gian đặc trưng mà đặt trong nhiều không gian đặc trưng (trong ngữ cảnh của chương này, luận án ánh xạ mỗi một biểu diễn của ảnh vào một không gian đặc trưng), sau đó thực hiện tra cứu bằng việc truy vấn trên mỗi không gian đặc trưng này và gộp các kết quả tương ứng với các không gian đặc trưng thành một kết quả cuối cùng. 35 Hình 2.6. Bốn biểu diễn của cùng một ảnh Hình 2.6 chỉ ra bốn biểu diễn của một ảnh có ID là 476043.jpg trong cơ sở dữ liệu Corel. Ảnh này sẽ được biến đổi thành bốn biểu diễn là: biểu diễn mầu C+, biểu diễn âm bản của ảnh mầu C-, diểu diễn ảnh xám G+ và và biểu diễn âm bản của ảnh xám G-. Lưu ý ở đây là biểu diễn mầu chính là ảnh mầu gốc. Lý do mà phương pháp trong luận án có thể lấy được các ảnh nằm rải rác trong không gian đặc trưng mầu gốc được minh họa trên Hình 2.7. Trên hình này, 22 ảnh trên Hình 2.2 được chuyển về biểu diễn xám G+. Theo biểu diễn này, các đặc trưng hình dạng và kết cấu sẽ không bị át bởi mầu. Một ảnh hoa hồng (biểu diễn xám) sẽ được ánh xạ thành một điểm trong không gian đặc trưng G+. Trong không gian này, tính chất kết cấu sẽ không bị lấn át bởi mầu cho nên 22 ảnh bông hoa hồng vàng, trắng và đỏ có vị trí gần nhau. Do vậy, phương pháp đề xuất có thể lấy ra được các ảnh hoa hồng mầu đỏ, mầu hồng và mầu vàng tương ứng với ảnh truy vấn mầu đỏ (476043.jpg trong cơ sở dữ liệu Corel). C+ C- G+ G- 36 47604284078 476025476076 476004 84060 84095 476009 476000 476033 476009 476079 476028 476041 476062 476050 476016 476043 476010 476067 84037 476024 Hình 2.7. Không gian đặc trƣng ảnh xám. Đến đây, quá trình tra cứu sẽ đối sánh giữa ảnh truy vấn và ảnh cơ sở dữ liệu trong mỗi một không gian đặc trưng riêng lẻ để có được một danh sách kết quả. Như vậy, ta sẽ có 4 danh sách kết quả. Tiếp theo, bốn danh sách kết quả sẽ được gộp lại để được một danh sách kết quả cuối cùng. 2.3. Phản hồi liên quan với truy vấn đa điểm Các cách tiếp cận ban đầu đối với tra cứu ảnh dựa vào nội dung không thích ứng với tra cứu dựa vào nhận thức của người dùng về độ tương tự trực quan. Để khắc phục vấn đề này, một số kỹ thuật phản hồi liên quan [21,98] đã được đề xuất. Các tác giả đã đánh giá sự liên kết giữa các khái niệm ngữ nghĩa và các đặc trưng ảnh mức thấp và mô hình nhận thức chủ quan của người dùng từ phản hồi của người dùng. Có hai thành phần để học phản hồi liên quan đó là hàm khoảng cách và điểm truy vấn mới. Hàm khoảng cách sẽ thay đổi thông qua việc học các trọng số của các thành phần đặc trưng và điểm truy vấn mới thu được bằng việc học điểm mong muốn mà người dùng tìm kiếm. Dịch chuyển điểm truy vấn đã được áp dụng vào các hệ thống tra cứu ảnh như MARS [85] và MindReader [47] và FQPM [29]. Các hệ thống này biểu diễn 37 truy vấn bằng một điểm trong không gian đặc trưng và dịch chuyển điểm này theo hướng các điểm liên quan và dịch ra xa các điểm không liên quan. Ý tưởng này bắt nguồn từ thuật toán của Rocchio [88], đã được sử dụng thành công trong tra cứu tài liệu. Tiếp theo, các phương pháp điều chỉnh truy vấn sử dụng phản hồi liên quan đa điểm đã được đưa ra. Cách tiếp cận mở rộng truy vấn [85,118] xây dựng các cụm cục bộ cho các điểm liên quan. Trong cách tiếp cận này, tất cả các cụm cục bộ được gộp lại để tạo ra một đường viền rộng phủ tất cả các điểm truy vấn. Bên cạnh đó, cách tiếp cận dịch chuyển điểm truy vấn [52] bỏ qua các cụm và coi tất cả các điểm liên quan là tương đương nhau. Tuy nhiên, cả hai cách tiếp cận thất bại trong việc nhận biết các vùng thích hợp cho các truy vấn phức tạp. Trong [108] đã trình bày FALCOM, mô hình khoảng cách toàn thể để thuận lợi cho việc học các điểm truy vấn lõm và tách rời trong không gian véc tơ cũng như trong không gian độ đo bất kỳ. Tuy nhiên, hàm khoảng cách gộp được đề xuất phụ thuộc vào tri thức kinh nghiệm đặc thù và mô hình này giả thiết rằng tất cả các điểm liên quan là các điểm truy vấn. Chen và cộng sự [122] cũng đưa cách tiếp cận này vào sử dụng đa truy vấn hạt giống nhưng họ sử dụng chúng để mở rộng đường biên xung quanh truy vấn tốt nhất và vẫn chủ yếu tìm kiếm trong một vùng đơn của không gian đặc trưng. Trong [49], Jin và cộng sự đã chỉ ra rằng trong hệ thống CBIR truy vấn đa ảnh, các ảnh mẫu có liên quan về mặt ngữ nghĩa có thể rất khác nhau trong không gian đặc trưng nào đó. Trong suốt phân tích các hiệu năng thực nghiệm, các tác giả khẳng định rằng, tra cứu theo nhiều truy vấn có thể thu được các hiệu quả khác nhau khi các truy vấn có vị trí trong một hoặc nhiều hơn một cụm. Nếu các truy vấn có vị trí trong cùng một cụm, tâm truy vấn có thể giúp cải tiến hiệu năng, nhưng nếu các truy vấn có vị trí ở nhiều cụm khác nhau, tâm truy vấn sẽ giảm hiệu năng. Trong trường hợp này, nó có thể có hiệu quả khác nhau khi các truy vấn có vị trí trong một hoặc nhiều hơn một cụm. Do đó, các tác giả đề xuất phương pháp theo cách tiếp cận truy vấn tách rời (gọi là đa điểm [88]). Trong 38 phương pháp của họ, thay vì tìm một tâm truy vấn cho các mẫu dương được lựa chọn, họ thực hiện các truy vấn riêng lẻ và sau đó nhập các kết quả tương ứng với các truy vấn thành một danh sách tổng hợp. Phương pháp của họ đã thu được kết quả tra cứu tốt mà bao gồm các ảnh liên quan ngữ nghĩa nằm rải rác trong toàn bộ không gian đặc trưng hơn là trong lân cận của một truy vấn đơn điểm. Họ sử dụng các ảnh phản hồi làm các truy vấn tiếp theo hơn là điều chỉnh truy vấn gốc trong tìm kiếm truy vấn ―tốt‖ nhất. Họ tìm kiếm đồng thời trong không gian đặc trưng và gộp kết quả đầu ra để hiển thị cho người dùng cuối. Phương pháp có ưu điểm là cho ra kết quả là các ảnh liên quan ngữ nghĩa nằm trong toàn bộ không gian đặc trưng. Tuy nhiên, phương pháp của họ ngoài việc yêu cầu người dùng nhập đồng thời nhiều ảnh truy vấn đa dạng (gánh nặng cho người dùng) còn chưa tận dụng tốt thông tin ngữ nghĩa của ảnh để nâng cao độ chính xác của tra cứu. 2.4. Thuật toán tra cứu ảnh đề xuất Định nghĩa 2.5 (Truy vấn đa điểm): Một truy vấn đa điểm MQ=<nMQ, PMQ, WMQ, DMQ, DB, k>, với nMQ biểu thị số các điểm truy vấn trong MQ, PMQ={PMQ1,,PMQn} là tập nMQ điểm truy vấn trong không gian tìm kiếm DB, WMQ={wMQ1,,wMQn} là tập các trọng số được kết hợp với PMQ (luận án giả thiết rằng các trọng số được chuẩn hóa tức là ∑ ), DMQ là khoảng cách mà khi được cho hai điểm bất kỳ pi và pj trong không gian đặc trưng sẽ trả lại khoảng cách giữa chúng và k là số các điểm được tra cứu trong mỗi lần lặp. 2.4.1. Phân cụm tập ảnh phản hồi Biểu diễn dữ liệu là bước quan trọng đầu tiên để giải quyết bất cứ một bài toán phân cụm nào. Trong lĩnh vực thị giác máy tính, hai loại biểu diễn được sử dụng rộng rãi nhất [28]. Loại đầu tiên là biểu diễn hình học, trong đó các mục dữ liệu được ánh xạ vào không gian véc tơ thực nào đó. Loại thứ hai là biểu diễn đồ thị nhấn mạnh đến quan hệ cặp. Khi làm việc với các ảnh, biểu diễn hình học có hạn chế: đòi hỏi các ảnh phải được ánh xạ thành các điểm trong không gian véc 39 tơ thực nào đó dẫn đến khó áp dụng cho các khoảng cách không độ đo (nonmetric). Do đó, phương pháp đề xuất sử dụng biểu diễn đồ thị cho tập ảnh. Định nghĩa 2.6 (Một biểu diễn đồ thị của các ảnh lân cận): Một tập gồm n ảnh được biểu diễn bởi một đồ thị vô hướng có trọng số G = (V,E): các nút V = {s1, s2,, sn} biểu diễn các ảnh, các cạnh E = {(si,sj): si, sj  V} được tạo ra giữa mỗi cặp nút, và một trọng số không âm aij của một cạnh (si,sj) chỉ ra độ tương tự giữa hai nút, là một hàm độ tương tự giữa các nút (các ảnh) si và sj. Ma trận affinity A xác định như công thức: ‖ ‖ (2.4) Ở đây tham số tỉ lệ 2 xác định mức độ aij giảm nhanh hay chậm theo khoảng cách giữa si và sj. Sau khi biểu diễn dữ liệu trên một đồ thị, phân cụm có thể được phát biểu như một bài toán phân hoạch đồ thị. Trong các phương pháp phân hoạch đồ thị phổ [48,121] đã được áp dụng thành công với nhiều lĩnh vực trong thị giác máy tính gồm phân tích chuyển động [20], phân đoạn ảnh [48,121] và nhận dạng đối tượng [97]. Có rất nhiều thuật toán phân hoạch đồ thị khác nhau, luận án sử dụng k véc tơ riêng và tính trực tiếp phân hoạch k-way [1]. Mục tiêu của phương pháp phân hoạch đồ thị là tổ chức các nút thành các nhóm sao cho độ tương tự trong phạm vi nhóm là cao, và/hoặc độ tương tự giữa các nhóm là thấp. Với một đồ thị đã cho G = (V,E) có ma trận affinity A, một cách đơn giản để xác định chi phí phân hoạch các nút thành hai tập rời nhau C1 và C2 (C1C2 =  và C1C2 = V) là tổng trọng số của các cạnh kết nối giữa hai tập. Thuật toán phân hoạch đồ thị sử dụng k véc tơ riêng và tính trực tiếp từ phân hoạch k-way thực hiện như sau: Đầu tiên, phương pháp xây dựng ma trận affinity A theo (2.4) và xây dựng ma trận đường chéo D trong đó phần tử Dii (hàng i, cột i ) là tổng các phần tử hàng thứ i của ma trận A. 40 Ma trận đường chéo D với: ∑ (2.5) Tính ma trận Laplace chuẩn hóa: (2.6) Tìm k véc tơ riêng x1, x2, xk lớn nhất của ma trận L, trong đó x1 = (x11, x12, x13, , x1n), x2 = (x21, x22, x23, , x2n),., xk = (xk1, xk2, xk3, , xkn) và xây dựng ma trận X = [x1 T ,x2 T ,,xk T ] Є R n x k , cụ thể: x1 T x2 T x3 T xk T X = x11 x21 x31 xk1 x12 x22 x32 xk2 x13 x23 x33 xk3 x1n x2n x3n xkn Xây dựng ma trận Y từ X bằng việc chuẩn hóa mỗi dòng của X là chiều dài đơn vị của ma trận Y: ∑ Y = y1 y11 y12 y13 y1k y2 y21 y22 y32 y2k y3 y31 y32 y33 y3k yk yn1 yn2 ynk Mỗi dòng của ma trận Y được xem như là một điểm trong không gian véc tơ k chiều. Đến đây, ta sẽ có n điểm trong không gian Rk, phân cụm (yi)i=1n trong không gian R k thành k cụm C1, C2, , Ck thông qua thuật toán K-Means. 41 Cuối cùng, gán điểm si tới cụm j nếu và chỉ nếu hàng thứ i của ma trận Y tưởng ứng với cụm j. Thuật toán 2.1 dưới đây là thuật toán phân cụm sử dụng k véc tơ riêng CISE (Clustering Images Set using Eigenvectors) thực hiện việc phân cụm tập các ảnh thành k cụm. Thuật toán 2.1. Thuật toán phân cụm sử dụng k é ơ riêng Input: - Tập các ảnh S = {s1,s2 sn} với si Rn - Số cụm k Output: k cụm: C1, C2 Ck 1. Xây dựng ma trận affinity 1.1. for i1 to n do 1.2 for j1 to n do if (ij)  ‖ ‖ else  2. Xây dựng ma trậ đường chéo và ma trận Laplace L 2.1. for i1 to n do ∑ L  D-1/2 A D-1/2 3. Tìm k é ơ riêng lớn nhất x1, x2 xk của ma trận Laplace L 3.2. for i1 to k do  X  [x1T ,x2T xkT ] 4. Xây dựng ma trận Y từ X 4.1. for i1 to n do 4.2. for j1 to k do yij  xij/ ∑ )1/2 Y  [y1 ,y2 yk ] 5. Phân thành k cụm thông qua K-Means 5.1.  5.2. for i1 to n do 42    K-Mean(P) 6. Gán các si vào các cụm 6.1. for i1 to n do if 7. Return C1, C2 Ck 2.4.2. Thuật toán đề xuất cho phân cụm gia tăng Có rất nhiều thuật toán phân cụm như K-means [30], K-medoid [62], . được sử dụng trong các thuật toán tra cứu ảnh. Tuy nhiên, trong các phương pháp tra cứu ảnh sử dụng phân cụm [46,60,126] khi một ảnh mới được thêm vào, thuật toán cần phân cụm lại từ đầu. Do đó, các thuật toán này không phù hợp với trường hợp các yêu cầu trực tuyến, chẳng hạn, trường hợp mà áp dụng với một tập nhỏ các ảnh phản hồi nhưng yêu cầu phân cụm tức thì và nhiều ảnh vẫn cần được bổ sung và phân cụm tiếp theo không. Những thuật toán thỏa mãn trường hợp trực tuyến này được gọi là ―gia tăng‖ hoặc ―phân cụm gia tăng‖. Trong thuật toán phân cụm gia tăng, xác định cụm cho một đối tượng là công việc quan trọng nhất. Giả sử dữ liệu có phân phối Gauss. Trong thuật toán này, ta coi mỗi cụm như một nhóm. Khi huấn luyện, ta sẽ ước lượng tâm và ma trận hiệp phương sai. Công việc xác định cụm của một đối tượng được qui về bài toán tìm một ước lượng | sao cho: với một đầu vào được cho , nhãn cụm của nó sẽ được xác định theo: ̂0 | (2.8) Tuy nhiên, | rất khó tính toán, do đó thay vì tính toán | , ta sẽ ước lượng qua | và . Theo luật Bayes, với i là nhãn của nhóm, ta có công thức: 43 | | (2.9) | ∑ | (2.10) (các véc tơ đặc trưng x là độc lập tuyến tính) Giả sử rằng | là phân phối chuẩn đa biến với hàm mật độ: |∑ | |∑ | (2.11) Trong đó: Trung bình của nhóm i ∑ : ma trận hiệp phương sai gộp chung của tất cả các nhóm Giả sử rằng ta biết: (2.12) { } (2.13) Lưu ý: công thức (2.13) là tỉ số của các mẫu huấn luyện của nhóm i trên tổng số mẫu huấn luyện. Đến đây, chúng ta thu được công thức: | (2.14) Vì mẫu số trong (2.14) không phụ thuộc vào i, nên chúng ta có thể coi nó là một hằng số C và thu được công thức. | (2.15) Thay từ (2.11) vào (2.15), ta được: | |∑ | |∑ | (2.16) 44 Vì |∑ | trong (2.16) không phụ thuộc vào i nên ta đặt |∑ | bằng hằng số và ta có: | |∑ | (2.17) và lấy logarit của cả hai vế của (2.17), ta được: | ∑ (2.18) Giá trị của vế phải (2.18) đúng với mọi nhóm i nên ta chỉ quan tâm đến: ∑ (2.19) = [ ∑ ∑ ] ∑ (2.20) Như vậy, mục tiêu của ta là cực đại công thức (2.20) theo i. Do ∑ trong (2.20) không phụ thuộc vào i nên ta coi nó là một hằng số nên (2.20) biến đổi thành ∑ ∑ (2.21) Bỏ qua hằng số , ta có hàm mục tiêu: ∑ ∑ (2.22) Với một đầu vào x, chúng ta dự đoán nhãn của nó là i nếu cao nhất. Thuật toán 2.2 dưới đây, có tên là INC - Incremental Clustering (phân cụm gia tăng), thực hiện việc xác định một đối tượng mới sẽ thuộc cụm nào. Thuật toán INC có đầu vào là một tập ví dụ huấn luyện D và một ảnh cần xác định cụm. Ở phần xử lý, thuật toán thực hiện tính toán giá trị và lấy giá trị i mà có đạt cực đại. Đầu ra của thuật toán là cụm i chứa ảnh . 45 Thuật toán 2.2. Thuật toán INC Input: - D={ N { } }: tập huấn luyện - : ảnh Output: - i: cụm chứa ảnh mới 1. Tách D thành g cụm dựa vào số ượng cụm trong Y 2. Tính trung bình của mỗi cụm { } và của cả tập D 3. Tính ma trận hiệ ươ ủa nhóm { } và ma trận hiệp ươ ộp chung. 4. Tí é ơ ế xác suất tiền nghiệm theo (2.13) 5. Tính , , theo công thức (2.22) 6. Return Để đánh giá tính hiệu quả của thuật toán gia tăng đề xuất, luận án chia làm hai trường hợp. Trường hợp đầu tiên, dựa trên tập dữ liệu Iris (Iris flower dataset) để đánh giá tính hiệu quả về độ chính xác. Trường hợp thứ hai, đánh giá hiệu quả về thời gian dựa trên phương pháp tra cứu ảnh AWEIGHT. Trường hợp 1 (đánh giá độ chính xác): Tập dữ liệu IRIS1 cho thực nghiệm: Tập dữ liệu này bao gồm thông tin của ba loại hoa Iris khác nhau (một loài hoa lan). Ba loại hoa gồm: Iris setosa, Iris virginica và Iris versicolor. Mỗi trong ba loại này có 50 bông hoa. Dữ liệu gồm 4 thông tin: chiều dài, chiều rộng đài hoa (sepal) và chiều dài, chiều rộng cánh hoa (petal). Mỗi điểm dữ liệu trong tập này là một vector 4 chiều. Luận án thực hiện ba phương pháp phân cụm trên tập dữ liệu IRIS gồm: K-means [106], phổ Spectral [1] và thuật toán đề xuất INC. Phương pháp k- mean được thực hiện 3 lần trên 150 mẫu (lý do là hiệu quả của thuật toán K- mean phụ thuộc một phần vào tâm khởi tạo) và kết quả là trung bình của ba lần phân cụm. Phương pháp phổ Spectral được thực hiện 1 lần trên 150 mẫu. Phương pháp đề xuất INC được thực hiện theo 3 vòng: vòng 1 là phân cụm khởi 1 https://archive.ics.uci.edu/ml/datasets/iris 46 tạo với phân cụm phổ trên 50 mẫu; vòng 2 là phân cụm gia tăng lần thứ nhất trên 50 mẫu và vòng 3 là phân cụm trên 50 mẫu còn lại. Kết quả của 03 phương pháp phân cụm được chỉ trên Bảng 2.1. Như thấy trong bảng này, phương pháp K- means có 130 mẫu đúng và 20 mẫu sai, phương pháp phổ Spectral có 131 mẫu đúng và 19 mẫu sai, phương pháp đề xuất INC có 132 mẫu đúng và 18 mẫu sai. Như vậy, số mẫu đúng của ba phương pháp là xấp xỉ nhau, phương pháp INC nhỉnh hơn phương pháp K-means là 02 mẫu và nhỉnh hơn phổ Spectral là 1 mẫu. Bảng 2.1: Kết quả phân cụm của ba phƣơng pháp. STT Phƣơng pháp phân cụm Số mẫu phân cụm đúng Số mẫu phân cụm sai 1 K-means 130 20 2 Phổ Spectral 131 19 3 Gia tăng INC 132 18 Trường hợp 2 (đánh giá thời gian): Trường hợp thứ hai, đánh giá hiệu quả về thời gian dựa trên phương pháp tra cứu ảnh AWEIGHT. Phần này thực hiện đánh giá tính hiệu quả về thời gian trên Aweight là vì hai lý do sau: thứ nhất, phương pháp INC có yếu tố giảm chiều, trong khi tập dữ liệu Iris chỉ có 4 chiều. Thứ hai, số mẫu của tập IRIS chưa đủ lớn (150 mẫu) nên khó phân biệt được tốc độ. Luận án đã đánh giá thời gian thực hiện của INC qua phương pháp tra cứu Aweight trên tập ảnh Corel gồm 10.800 ảnh. Trong thực nghiệm này, thời gian của phương pháp AWEIGHT (có sử dụng phân cụm gia tăng INC) được so sánh với phương pháp Aweight_WRC (Aweight sử dụng phân cụm phổ SPECTRAL). Như thấy trên Hình 3.11, thời gian thực hiện của AWEIGHT nhanh hơn nhiều so với Aweight_WRC. 47 2.4.3. Công thức đề xuất cho tính khoảng cách cải tiến Trong phần này, luận án đề xuất công thức tính khoảng cách từ một ảnh đến truy vấn đa điểm MQ = (Q1, Q2,..Qn). Khoảng cách này (2.23) là cực tiểu của các khoảng cách có trọng số từ một ảnh đến mỗi truy vấn Qi: ( ) (2.23) ớ { } Trong công thức (2.23), Dist( ,Qi ) với i=1..n, j=1..k là khoảng cách từ một ảnh đến một truy vấn Qi với trọng số đặc trưng (xác định theo thuật toán IF ), là trọng số ngữ nghĩa kết hợp với khoảng cách dij (xem cách tính trọng số ngữ nghĩa trong công thức (2.24)). 2.4.4. Công thức đề xuất cho tính trọng số ngữ nghĩa của truy vấn Trong mục này, luận án đề xuất một công thức tính trọng số ngữ nghĩa của truy vấn. Đề xuất được dựa trên nhận thức rằng, trong một cụm chứa nhiều ảnh liên quan ngữ nghĩa sẽ quan trọng hơn các cụm còn lại. Do đó, truy vấn được tạo ra từ cụm đó sẽ có trọng số ngữ nghĩa cao hơn các cụm còn lại. Vì vậy, tác giả đề xuất tính trọng số ngữ nghĩa wij kết hợp với khoảng cách dij từ ảnh đến truy vấn Qi (thuộc cụm ngữ nghĩa i) là tỉ số giữa số ảnh liên quan ngữ nghĩa trong cụm i và tổng số các ảnh liên quan của n cụm ngữ nghĩa. | ụ ứ | ∑ | ụ ứ | ớ { } (2.24) Các trọng số cần thỏa mãn điều kiện ∑ ớ { } Chẳng hạn, với và  { } , chúng ta sẽ có 3 truy vấn tương ứng với 3 cụm (xem Hình 2.8) và trọng số ngữ nghĩa gắn với truy vấn 1, 2 và 3 sẽ được tính theo công thức (2.24) như sau: 48 | ụ | | ụ | | ụ | | ụ | | ụ | | ụ | | ụ | | ụ | | ụ | | ụ | | ụ | | ụ | Hình 2.8. Minh họa tính trọng số ngữ nghĩa từ một ảnh đến 3 truy vấn. 2.4.5. Thuật toán đề xuất cho tính độ quan trọng đặc trƣng Mỗi một ảnh được biểu diễn bởi một điểm trong không gian đặc trưng. Thông thường, các phương pháp trước đây coi các đặc trưng này có độ quan trọng như nhau. Chẳng hạn: khi so sánh các đặc trưng trong cơ sở dữ liệu đặc trưng mà luận án sử dụng (gồm 7 đặc trưng ColorHsvHistogram64, ColorLuvMoment123, ColorHsvCoherence64, CoarsnessVector, Directionality, WaveletTwtTexture, MRSAR), các đặc trưng sẽ được coi là có độ quan trọng ngang bằng nhau. Điều này không phản ảnh đúng thực tế là có một số đặc trưng quan trọng hơn các đặc trưng còn lại. Do đó, tác giả đề xuất cần phải quan tâm tới độ quan trọng của mỗi đặc trưng trong pha so sánh ảnh. Ý tưởng chính của việc xác định độ quan trọng đặc trưng là dựa vào sự phản hồi của người dùng và độ phân tán của các điểm dữ liệu. Khi người dùng phản hồi một số ảnh liên quan ngữ nghĩa với ảnh truy vấn, phương pháp đề xuất sẽ phân cụm các ảnh này thành các cụm và xét mỗi cụm trong số các cụm này : ảnh liên quan ngữ nghĩa : ảnh truy vấn Cụm_3 Cụm_2 Cụm_1 49 như sau: mỗi ảnh trong một cụm sẽ là một điểm trong không gian đặc trưng và các điểm này sẽ có vị trí gần nhau trong không gian đặc trưng. Một hình bao các điểm này sẽ được chiếu xuống các trục tương ứng với các đặc trưng, sau đó tính phương sai của các điểm này theo mỗi trục (độ phân tán dữ liệu theo một trục trong không gian đặc trưng lớn có nghĩa là độ quan trọng theo trục đó nhỏ). Do đó, độ quan trọng của mỗi đặc trưng trong không gian đặc trưng là nghịch đảo của phương sai của các điểm theo trục đó. Thuật toán 2.3 dưới đây, có tên IF (Importance of Feature), sẽ xác định độ quan trọng đặc trưng. Thuật toán tính độ quan trọng của đặc trưng trong không gian đặc trưng FS. Thuật toán 2.3. Thuật toán IF Input: Tập n é ơ đặ ư trong một cụm C Tậ á đặ ư FS Số đặ ư m Ouput: Độ quan trọng củ đặ ư l Weight_l 1. For l1 to m do { 1.1.  ∑ 1.2.  ∑ 1.3. Weight_l  // trọng số đặ ư thứ l } Thuật toán IF lấy đầu vào là n véc tơ đặc trưng trong một cụm trên không gian FS. Lúc này, theo đặc trưng thứ l của không gian đặc trưng FS sẽ có n điểm dữ liệu và thuật toán tính phương sai của n điểm dữ liệu này theo trục l của không gian FS. Sau khi tính được giá trị của phương sai , thuật toán đưa ra độ quan trọng của từng 50 đặc trưng l trong không gian đặc trưng FS. Độ quan trọng của đặc trưng theo trục l sẽ được tính bằng và gán cho Weight_l. 2.4.6. Thuật toán đề xuất cho gộp các danh sách kết quả Với mỗi điểm truy vấn, hệ thống sẽ cho ra một danh sách kết quả. Các danh sách này cần được gộp lại để có một danh sách kết quả cuối cùng. Thuật toán gộp thực hiện công việc này. Dưới đây là thuật toán Combination, nó thực hiện việc gộp các danh sách kết quả Ri thành danh sách kết quả tổng hợp R. Thuật toán 2.4. Thuật toán Combination Input: Danh sách truy vấn: (Q1, Q2 Qn) mỗi Qi có một cụm Ci ươ ứng Số các ảnh trả về : k Danh sách các kết quả: (R1, R2 n) //mỗi Ri gồm Trọng số đặ ư : Weight_l Output: Danh sách kết quả R 1. for mỗi Ri (i=1..n) do 1.1. for j1 to k do 0; 1.2. for i1 to n do 1.2.1.  | ụ ứ | ∑ | ụ ứ | 1.2.2.  (1-wij)*dist( ,Qi,Weight_l); 1.2.3. If ( > )  2. for i1 to n do 2.1. for j1 to k do Sắp xếp các theo thứ tự ă ần về khoảng cách 3. return R 51 Với đầu vào là một danh sách truy vấn Q1, Q2,Qn và danh sách các kết quả tương ứng R1, R2, .Rn mỗi Ri sẽ lấy k ảnh được phân hạng đầu tiên . Thuật toán sẽ tính khoảng cách Dij từ ảnh đến truy vấn Qi thông qua hàm dist( , , ) theo trọng số đặc trưng Weight_l (là đầu ra của thuật toán IF ở trên). Bên cạnh đó, trọng số kết hợp với khoảng cách Dij được tính là số các ảnh liên quan ngữ nghĩa của Cụm_thứ_i chia cho tổng số các ảnh của tất cả n cụm. Khoảng cách cuối cùng từ một ảnh đến các truy vấn Qi là cực tiểu các giá trị khoảng cách từ ảnh đến mỗi truy vấn Qi. Sau đó, thuật toán sắp xếp các ảnh theo thứ tự tăng dần về khoảng cách Dij và loại đi các ảnh trùng nhau để có được kết quả cần gộp R. Mệnh đề 1. [Độ phức tạp của thuật toán Combination]: Độ phức tạp của thuật toán Combination là với n là số danh sách cần kết hợp và k là số ảnh trả về của mỗi danh sách, Chứng minh: Hiển nhiên rằng thời gian thực hiện của thuật toán Combination là thời gi