Tóm tắt 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ố của hàm khoảng cách

i khác với sự tương tự giữa chúng trong không gian đặc trưng. Tức là, các ảnh liên quan về mặt ngữ nghĩa có thể nằm phân tán trong toàn bộ không gian đặc trưng và nằm rải rác ở một số cụm chứ không phải một cụm duy nhất. Trong trường hợp này, cách tiếp cận phản hồi liên quan truyền thống [2,29,61,74] không làm việc tốt (do họ sử dụng cách tiếp cận một điểm truy vấn). Thực hiện phản hồi liên quan đề cập đến việc tính toán một hoặc nhiều điểm truy vấn mới trong không gian đặc trưng và thay đổi hàm khoảng cách. Các phương pháp được trình bày theo cách tiếp cận phản hồi liên quan với truy vấn tách rời đều có ưu điểm cho kết quả là 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. Tuy nhiên, những phương pháp này có những hạn chế: (1) Yêu cầu người dùng phải cung cấp đồng thời các ảnh truy vấn đa dạng, chẳng hạn, để truy vấn chủ đề hoa hồng, người dùng phải cung cấp các ảnh hoa hồng đỏ, hoa hồng vàng, hoa hồng trắng,... làm truy vấn. Nếu điều kiện này không được thỏa mãn, kết quả tra cứu khởi tạo sẽ là các ảnh nằm trong một vùng nào đó chứ không bao gồm các ảnh liên quan nằm trong các vùng khác nhau. Nếu người dùng cung cấp cho hệ thống các ảnh truy vấn là các ảnh hoa hồng màu vàng, kết quả tra cứu khởi tạo chỉ có thể trả về các ảnh hoa hồng màu vàng mà bỏ qua các ảnh hoa hồng màu trắng và màu đỏ. Lý do của việc này là vì trong các hệ thống tra cứu ảnh truyền thống, các ảnh có véc tơ đặc trưng mức thấp tương tự nhau sẽ nằm gần nhau (hay trong cùng một cụm đặc trưng mức thấp). Trên danh sách kết quả khởi tạo gồm có các bông hồng màu vàng, người dùng chỉ có thể chọn được các bông hồng màu vàng. Hệ thống dựa vào các phản hồi là các bông hồng màu vàng để tiếp tục tra cứu. Các pha tra cứu tiếp theo sẽ dịch chuyển đến các vùng màu vàng. Kết quả của hệ thống chỉ có thể thu được các bông hồng màu vàng. Vì vậy, các vùng hoa hồng màu đỏ và trắng sẽ bị bỏ qua, do đó độ chính xác của hệ thống sẽ bị giới hạn cho dù pha tra cứu sau đó có ưu việt đến đâu. 7 (2) Số lần truy vấn cho lần lặp tiếp theo phụ thuộc vào số ảnh liên quan do người dùng cung cấp, do đó có hai khả năng không thuận lợi xảy ra: Khả năng thứ nhất, người dùng chọn quá ít ảnh phản hồi (ít hơn số cụm trong không gian đặc trưng). Trong khả năng này, độ chính xác của hệ thống sẽ không được đảm bảo vì theo lý thuyết phân cụm, nhiều truy vấn sẽ phủ nhiều cụm hơn. Khả năng thứ hai là người dùng chọn quá nhiều ảnh phản hồi. Khả năng này sẽ làm tăng gánh nặng cho pha gộp các danh sách kết quả (mỗi truy vấn sẽ có một danh sách kết quả). Ngoài ra, quá nhiều truy vấn cũng không cải tiến nhiều độ chính xác của hệ thống (thực nghiệm trong [49] đã chỉ ra rằng độ chính xác tăng nhanh từ 1 đến 8 truy vấn và tăng chậm khi số truy vấn từ 8 đến 20). Chẳng hạn, trong cơ sở dữ liệu Corel với chủ đề hoa hồng, mỗi ảnh truy vấn hoa hồng cũng chỉ nằm rải rác trong 4 cụm (mỗi cụm tương ứng với một màu của hoa hồng). (3) Sử dụng các trọng số của các truy vấn ngang bằng nhau, tức là, độ quan trọng của các truy vấn là như nhau cho dù mỗi truy vấn có lân cận khác nhau. (4) Các đặc trưng có trọng số như nhau cho dù mỗi thành phần đặc trưng có một độ quan trọng khác nhau. Những hạn chế này là nguyên nhân chính dẫn đến độ chính xác của hệ thống tra cứu chưa cao. Trên cơ sở phân tích các hạn chế của các phương pháp đã có, luận án đề xuất một phương pháp tra cứu ảnh liên quan ngữ nghĩa. Phương pháp đề xuất có ưu điểm là: (1) Chỉ sử dụng một truy vấn để tạo ra kết quả tra cứu khởi tạo đa dạng, gồm các ảnh nằm trong các vùng khác nhau (giảm gánh nặng cho người dùng trong việc không phải chọn nhiều ảnh truy vấn). (2) Phân cụm các ảnh liên quan với thời gian thấp. (3) Xác định được độ quan trọng ngữ nghĩa của từng truy vấn. (4) Xác định độ quan trọng theo từng đặc trưng. Bốn ưu điểm này đã được thể hiện trong phương pháp đã được công bố trong [CT5, CT6]. 2.2. Sơ đồ phƣơng pháp đề xuất Trên cơ sở các phân tích ở mục 2.1 ở trên, luận án đề xuất sơ đồ của phương pháp như trên Hình 2.5. 8 Hình 2.5. Cấu trúc phƣơng pháp đề xuất. 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à , 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 FSi). Đo khoảng cách giữa hai điểm và (k,l=1..N) và kl ,được ký hiệu là ( ), 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 tương ứ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à nhậ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. 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 là vì các ảnh được chuyển về biểu diễn xám. 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 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ả 9 đặc trưng. Trong không gian này, do đặc trưng mầu không được bao gồm cho nên các ảnh cùng chủ đề (chẳng hạn: bông hoa hồng vàng, trắng và đỏ) sẽ 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 đỏ. Đế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á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ố phương pháp tra cứu ảnh sử dụng phản hồi liên quan được đề xuất. 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 được 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. 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 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. . Thuật toán phân cụm sử dụng k véc tơ 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 for i1 to n do for j1 to n do if (ij) e p ‖ ‖ else  2. Xây dựng ma trận đường chéo và ma trận Laplace L for i1 to n do ∑ 10 L  D-1/2 A D-1/2 3. Tìm k véc tơ riêng lớn nhất 1, x2 k của ma trận Laplace L for i1 to k do  X  [x1T ,x2T kT ] 4. Xây dựng ma trận Y từ X for i1 to n do 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  for i1 to n do   K-Mean(P) 6. Gán các si vào các cụm for i1 to n do if .. Return C1, C2 Ck 2.4.2. Thuật toán đề xuất cho phân cụm gia tăng Sau khi thực hiện phân cụm tập ảnh phản hồi của người dùng, để tránh việc phận cụm lại toàn bộ tập ảnh phản hồi. Luận án thực hiện phân cụm gia tăng cho mỗi cụm. 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 tác giả 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 y (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à Y . Theo luật Bayes, với i là nhãn của nhóm, ta có công thức: (2.9) ∑ (2.10) Giả sử rằng là phân phối chuẩn đa biến với hàm mật độ: = ∑ ∑ (2.11) Trong đó: 11 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) Vì 2 ∑ 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: log log log ∑ (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: log ∑ (2.19) =log [ ∑ ∑ ] ∑ (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 log ∑ ∑ (2.21) Bỏ qua hằng số , ta có hàm mục tiêu: log ∑ ∑ (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. 2.4.3. Công thức đề xuất cho tính khoảng cách cải tiến 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) ớ  . . . 12 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 Đề 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 ∑ ớ  . . . 2.4.5. Thuật toán đề xuất cho tính độ quan trọng đặc trƣng Ý 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ư sau: mỗi ảnh trong một cụm sẽ là một điểm trong không gian đa đặc trưng và các điểm này sẽ có vị trí gần nhau trong không gian đa đặ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 đa đặc trưng là nghịch đảo của phương sai của các điểm theo trục đó. 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. 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. 2.4.7. Thuật toán đề xuất chung cho tra cứu ảnh liên quan ngữ nghĩa Ở phần này, luận án đề xuất một thuật toán, có tên SRIR (Semantic – Related Image Retrieval), không đòi hỏi người dùng phải cung cấp đồng thời nhiều truy vấn đa dạng. Dưới đây là mô tả thuật toán tra cứu các ảnh liên quan ngữ nghĩa SRIR. Thuật toán 2.5. Thuật toán SRIR Input: Tập các ảnh cơ sở dữ liệu DB Ảnh truy vấn Q 13 Số các ảnh được tra c u sau mỗi lần lặp k Không gian đặc trưng F Số đặc trưng m Ouput: Tập ảnh kết quả R C+Q; PMQFC+  ; WMQFC+ ; DMQFC+ (  ) s1 ; C-  ; PMQFC-  ; WMQFC- ; DMQFC- (  ) s2 ; G+  2 ; PMQFG+  ; WMQFG+ ; DMQFG+ (  ) s3 ; G-  ; PMQFG-  ; WMQFG- ; DMQFG- (  ) s4 ; ( ) US ; repeat USUS ; CL ; for i1 to n do  ; ci (CiCL); PMQici for j1 to k do WMQi ụ ∑ ụ DMQid (  ); Ri; SR until User dừng phản hồi return R; Mệnh đề 2. [Độ phức tạp của thuật toán SRIR]: Độ phức tạp của thuật toán SRIR là với N là số các ảnh có trong CSDL. 2.5. Đánh giá thực nghiệm 2.5.1 Môi trƣờng thực nghiệm 14 Cơ sở dữ liệu được sử dụng cho thử nghiệm là tập con của Corel gồm 3.400 ảnh. 2.5.3. Thực hiện truy vấn và đánh giá Để kiểm tra độ chính xác của phương phấp đề xuất Tất cả 3400 ảnh trong tập ảnh được dùng làm các truy vấn. Độ chính xác1 trung bình ở mức 150 ảnh trả về được sử dụng để đánh giá. Trong Bảng 2.2, thể hiện độ chính xác trung bình của bốn phương pháp là Basic C+, JF, MMRF và phương pháp đề xuất SRIR tại các mức 1,4 ,8 ,12, 16 và 20 truy vấn, với số cụm cũng chính là số truy vấn. Bảng 2.2. Bảng kết quả của 3 phƣơng pháp theo số truy vấn trong một lần phản hồi. Phƣơng pháp Độ chính xác theo số truy vấn 1 truy vấn 4 truy vấn 8 truy vấn 12 truy vấn 16 truy vấn 20 truy vấn Basic C+ 0.20 0.22 0.23 0.24 0.245 0.25 JF 0.24 0.29 0.31 0.33 0.34 0.35 MMRF 0.243 0.31 0.315 0.323 0.334 0.365 SRIR 0.36490 0.39789 0.40035 0.40241 0.40360 0.40385 Các kết quả thực nghiệm được chỉ ra trong Hình 2.11. Trục ngang chỉ ra số cụm (có thể là 1, 4, 8, 12, 16, 20). Trục đứng chỉ ra độ chính xác. Ba phương pháp khác nhau gồm Basic C+ , JF, MMRF và SRIR được chỉ ra bởi 3 đường cong. Hình 2.11 với Độ chính xác của các hệ thống tăng lên (trục đứng) cùng với sự tăng của trung ngang (số các cụm). Nhiều cụm được sử dụng trong tra cứu, độ chính xác hệ thống sẽ cao hơn. Dễ thấy, độ chính xác của phương pháp SRIR tốt hơn khi số cụm trong khoảng từ 1 đến 8, cụ thể là 36.490% ở mức 1, 39.789% ở mức 4 và 40.035% ở mức 8. . Hình 2.11. So sánh độ chính xác. 1 Độ chính xác (precision) là tỉ số giữa số các ảnh liên quan với ảnh truy vấn trong tập kết quả trả về trên tổng số các ảnh trả về. 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 1 4 8 12 16 20 Đ ộ c h ín h x ác Số truy vấn phản hồi Basic C+ JF MMRF SRIR 15 Trong phương pháp SRIR, đường cong độ chính xác tăng nhanh từ 1 đến 8 cụm (đặc biệt là từ 1 đến 4) và tăng chậm trong khoảng từ 12 đến 20 cụm, do 8 cụm đã phủ hầu hết các cụm trong không gian đặc trưng. Dù phương pháp JF cũng tăng nhanh trong khoảng từ 1 đến 8 truy vấn [49] nhưng phương pháp đề xuất SRIR có độ chính xác cao hơn hẳn mà không làm tăng thời gian tra cứu. Lý do chính của việc này là trong phương pháp đề xuất, dù số cụm trong khoảng từ 1 đến 8 nhưng tận dụng được thông tin ngữ nghĩa từ số phản hồi của người dùng nhiều hơn 8. 2.6. Kết luận Chƣơng 2 Luận án đã tập trung vào việc phân tích các ưu điểm và hạn chế của các phương pháp đã có. Trên cơ sở đó đề xuất phương pháp, có tên là SRIR, giải quyết bốn vấn đề chính đó là: (1) Chỉ sử dụng một truy vấn để tạo ra kết quả tra cứu khởi tạo đa dạng, gồm các ảnh nằm trong các vùng khác nhau (giảm gánh nặng cho người dùng trong việc không phải chọn nhiều ảnh truy vấn); (2) Phân cụm các ảnh liên quan với thời gian thấp; (3) xác định được độ quan trọng ngữ nghĩa của từng truy vấn và (4) xác định độ quan trọng theo từng đặc trưng. Kết quả thực nghiệm trên cơ sở dữ liệu đặc trưng gồm 3400 ảnh đã chỉ ra rằng phương pháp được đề xuất SRIR cung cấp một độ chính xác cao hơn hẳn so với các phương pháp Basic C+, MMRF và phương pháp JF. 16 Chƣơng 3. PHƢƠNG PHÁP TRA CỨU ẢNH SỬ DỤNG TRỌNG SỐ THÍCH NGHI 3.1. Giới thiệu Chương 2 của luận án đã trình bày phương pháp tra cứu ảnh [CT5] có thể lấy được các điểm ảnh cơ sở dữ liệu nằm rải rác trong toàn bộ không gian đặc trưng và cho kết quả tra cứu cao hơn những phương pháp được so sánh. Tuy nhiên, phương pháp này và những phương pháp hiện có chưa giải quyết được hai hạn chế sau: Thứ nhất, không khai thác đầy đủ thông tin phản hồi (mức độ liên quan của mỗi ảnh) để xác định các điểm truy vấn tối ưu. Chẳng hạn, Hình 3.1 là giao diện chung của các hệ thống hiện có. Giao diện này cho chúng ta thấy, người dùng chỉ có thể tích chọn vào ô ở phía trên của ảnh (nếu ảnh là liên quan) và không tích chọn (nếu ảnh không liên quan), Trong khi người dùng đánh giá ảnh có ID pl_flower\84059 cao hơn ảnh có ID pl_flower\476083. Hình 3.1: Giao diện điển hình của hệ thống CBIR với phản hồi liên quan. Thứ hai, các phương pháp ở trên coi các vùng chứa các điểm truy vấn tối ưu khác nhau là ngang bằng nhau và gán cùng trọng số cho tất cả các điểm lân cận của truy vấn tối ưu. Điều này là không thích hợp vì các vùng khác nhau thường có những thuộc tính riêng biệt. Hình 3.2. Minh họa vùng truy vấn tối ƣu ngang bằng nhau. (a) Hình bên trái: điểm truy vấn thứ nhất. (b) Hình bên phải: điểm truy vấn thứ hai. 17 Dựa trên quan sát này, luận án đã đề xuất một phương pháp tra cứu ảnh thông qua trọng số thích nghi, có tên là AWEIGH (An efficient image retrieval method using adaptive weights) [CT6]. Trong phương pháp này, thay vì sử dụng một véc tơ trọng số giống nhau cho các vùng chứa các điểm truy vấn tối ưu khác nhau, phương pháp tự động tính toán các điểm truy vấn tối ưu và các véc tơ trọng số tối ưu tương ứng với các vùng mà chứa các điểm truy vấn tối ưu dựa vào phản hồi của người dùng. Bên cạnh đó, các phương pháp trước đây thực hiện phân cụm tất cả các ảnh phản hồi, do đó độ phức tạp tính toán của các phương pháp đó sẽ cao. Để giải quyết hạn chế này, phương pháp đề xuất chỉ phân cụm các phản hồi trong lần lặp đầu tiên (từ lần lặp thứ hai, phương pháp chỉ phân lớp các phản hồi vào các cụm) (xem mục 2.3 của Chương 2). Hình 3.3 ở dưới chỉ ra sơ đồ của phương pháp đề xuất trong luận án. Sự khác biệt chính giữa đề xuất này trong luận án và các phương pháp tra cứu ảnh phản hồi liên quan đã có nằm ở ba thành phần chính (thuộc đường biên nét đứt hình chữ nhật bao): (a) Xác định các điểm truy vấn tối ưu, (b) tính toán các véc tơ trọng số và (c) Tính toán các hàm khoảng cách cải tiến. Các thành phần này có thể nhúng vào bất kỳ một hệ thống tra cứu ảnh sử dụng phản hồi liên quan nào, do đó luận án sẽ thực hiện mô tả mỗi thành phần này một cách tách biệt ở các mục tiếp sau. Hình 3.3. Sơ đồ của tra cứu ảnh sử dụng các trọng số thích nghi. Máy tìm kiếm AWEIGHT Xác định các điểm truy vấn tối ưu Xác định các trọng số Máy tìm kiếm Tập kết quả Tập phản hồi Phân cụm các ảnh Tập huấn luyện Tập kết quả Tập phản hồi Gia tăng cụm Tính toán hàm khoảng cách cải tiến Ảnh truy vấn 18 3.2. Thuật toán xác định điểm truy vấn tối ƣu và bộ trọng số thích nghi của hàm khoảng cách cải tiến. Trong phần này, luận án trình bày kỹ thuật đề xuất để xác định điểm truy vấn tối ưu và trọng số thích nghi của hàm khoảng cách. Kỹ thuật xác định điểm truy vấn tối ưu và các trọng số thích nghi theo một cụm các ảnh được cho. Trong trường hợp nhiều cụm, kỹ thuật này được thực hiện cho từng cụm. Ở đây, ta giả sử đã có cụm i (i=1,,g) nào đó, mỗi ảnh trong cụm i được biểu diễn bởi img img img img với j=1n , ma trận M img img (n là số các phần tử trong cụm i) biểu diễn các ảnh trong cụm i. Giả thiết véc tơ truy vấn tối ưu đối với cụm i là q q q q . Giả sử thông tin đánh giá của người dùng dưới dạng mức độ liên quan cho mỗi img (j=1,..,n ) được ký hiệu là lr (ở đây lr  2 , lr cao thì khoảng cách nhỏ hay độ tương tự cao), véc tơ L lr lr . lr sẽ biểu diễn thông tin đánh giá của người dùng dưới dạng mức độ liên quan của cụm M img img . Bài toán tìm điểm truy vấn tối ưu q và ma trận trọng số được đưa về bài toán tối ưu có ràng buộc như sau: min ∑ lr (img q ) img q (3.1) Với ràng buộc det( )=1 Ở đây det( ) là định thức của ma trận (ràng buộc det( )=1 để tránh trường hợp ma trận là ma trận không). Để tìm được nghiệm q và của bài toán trong (3.1), ta sử dụng phương pháp nhân tử Lagrange để giải: - Điểm truy vấn tối ưu q : q ∑ với q ∑ ∑ m . d (3.2) - Ma trận trọng số : det C C (3.3) Với ma trận hiệp phương sai có trọng số của các ảnh trong cụm i: C c với: c ∑ lr img mg̅̅ ̅̅ ̅ img mg̅̅ ̅̅ ̅ (3.4) Từ véc tơ truy vấn tối ưu q và ma trận trọng số W, hàm khoảng cách được xác định như sau: d (img q ) (img q ) (img q ) (3.5) Cho Cpf (q ) là danh sách các điểm trong cụm các mẫu phản hồi dương tương ứng với điểm truy vấn tối ưu thứ i (q tức là danh sách các điểm trong 19 hình ellip tương ứng. Nearest p là danh sách k điểm gần nhất đối với pi. e e Nearest p e Cpf q là các điểm phản hồi dương lân cận k của điểm pi. Hàm khoảng cách đề xuất được viết như sau: d (p q ) d (p q ) (3.6) Khi đó: d (p q ) là khoảng cách cải tiến từ một điểm pi tới điểm truy vấn tối ưu q . d p q là khoảng cách từ pi tới điểm truy vấn tối ưu q theo Thuật toán 3.2. 3.3. Đề xuất thuật toán tra cứu ảnh sử dụng bộ trọng số thích nghi Trên cơ sở các nội dung đã trình bày ở trên, luận án đề xuất một thuật toán tra cứu ảnh sử dụng bộ trọng số thích nghi AWEIGHT sử dụng điểm truy vấn tối ưu, hàm khoảng cách tối ưu và hàm khoảng cách cải tiến. Thuật toán 3.2. Thuật toán AWEIGHT Input: Image set: S Query: Qinitial Number of retrieved images after each interation: k Output: The result set: Result(Qopt) 1. Result(Qinitial) ; 2. Relevant( ,N)Feedback esult N ; 3. CISE(Relevant( ,N), g, IMG) 4. D{ i N } 5. Repeat 5.1 for i1 to g do FQM( , , ) 5.2 Result(Qopt) <g, { , ,... }, { }, , S, k>; 5.3 Relevant( N’)Feedback esult( ) N ; 5.4 For j to N’ do INC(D, imgj  Relevant( N’), i); Add(imgj, ) until (User stops responding); 6. Return Result(Qopt); 3.4. Thử nghiệm và đánh giá kết quả 3.4.1. Môi trƣờng thực nghiệm Cơ sở dữ liệu ảnh Hiệu quả tra cứu của phương pháp đề xuất được đánh giá trên một cơ sở dữ liệu (CSDL) gồm 10.800 ảnh. CSDL ảnh này là tập con của Corel Photo Gallery. 20 3.4.2. Các kết quả thực nghiệm và thảo luận Trong phần thực nghiệm, các tham số được lựa chọn như sau: Hiệu quả tra cứu được đánh giá trên cơ sở dữ liệu ảnh COREL gồm 10.800 ảnh, tất cả các ảnh trong cơ sở dữ liệu được sử dụng để thực hiện các truy vấn. Thực nghiệm thực hiện đánh giá độ chính xác của phương pháp đề xuất dựa trên độ chính xác trung bình của 10.800 ảnh truy vấn. Mỗi truy vấn thực hiện sẽ trả về 100 ảnh, lý do chọn 100 ảnh là bởi vì người dùng thường chỉ xem xét 2 trang màn hình và mỗi trang màn hình chứa 50 ảnh để lựa chọn ảnh phản hồi. Các kết quả, độ chính xác trung bình của 10800 truy vấn, được thể hiện bằng số liệu trong Bảng 3.2 và bằng đồ thị trong Hình 3.5 ở dưới. Chi tiết về độ chính xác của to