Đề xuất sử dụng phương pháp tiếp cận Pareto để lựa chọn các điểm ảnh

Nội dung text: Đề xuất sử dụng phương pháp tiếp cận Pareto để lựa chọn các điểm ảnh

1. Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020) Đề xuất sử dụng phương pháp tiếp cận Pareto để lựa chọn các điểm ảnh Bùi Thị Thùy1, Lê Phú Hưng1, Nguyễn Đức Toàn1 1Khoa Công nghệ thông tin - Trường Đại học Tài Nguyên và Môi Trường Hà Nội Email: btthuy@hunre.edu.vn lphung@hunre.edu.vn,ndtoan@hunre.edu.vn Abstract— Trong bài báo này, chúng tôi đề xuất sử ảnh đại diện. Các hệ thống đó được gọi là truy xuất dụng phương pháp tiếp cận Pareto để lựa chọn các hình ảnh dựa trên nội dung (CBIR).[11] điểm ảnh. Phương pháp này thường được sử Một hệ thống CBIR điển hình hoạt động như sau. dụng trong hệ thống truy xuất hình ảnh dựa trên Đầu tiên, nó thực hiện trích xuất tính năng, tức là nội dung (CBIR) có nhiều tính năng (ví dụ: màu sắc, hình dạng, kết cấu). Trong phương pháp cách liên kết mỗi hình ảnh với một vectơ định lượng. này, các hệ thống thường biểu diễn mỗi hình ảnh Vectơ định lượng này được gọi là vectơ đặc trưng dưới dạng vectơ đặc trưng riêng biệt. Từ đó nối của hình ảnh. Tính năng của tất cả các hình ảnh các vectơ đặc trưng thành phần với một ảnh truy trong cơ sở dữ liệu. Sau đó, đối với hình ảnh đầu vấn, tính toán số đo khoảng cách của nó với ảnh vào (thường được gọi là hình ảnh truy vấn), hệ trong cơ sở dữ liệu. Mặc dù đơn giản, phương thống sẽ tính toán thước đo khoảng cách của các đối pháp này không đề cập đến độ phức tạp của thuật toán. Một phương pháp khác thường tính tượng vector với hình ảnh trong cơ sở dữ liệu. Cuối toán sự kết hợp tuyến tính có trọng số của các cùng, những hình ảnh gần nhất có thước đo khoảng phép đo khoảng cách riêng lẻ và việc gán trọng cách nhỏ nhất được trả lại cho người dùng. [4,5,6,7] số cho mỗi phép đo dựa trên phản hồi về mức độ Hệ thống CBIR thường thể hiện tính năng của hình liên quan (RF) từ người dùng để xác định tầm ảnh bằng màu sắc, kết cấu, hình dạng và bố cục quan trọng của từng thành phần. Trong bài báo hình ảnh. Sự kết hợp của màu sắc, kết cấu và hình này, nhóm tác giả đề xuất sử dụng phương pháp dạng được đề xuất trong [9]. Mặt khác, trong [10] tiếp cận Pareto để lựa chọn các điểm ảnh. Đề xuất thuật toán tạo ra một tập hợp nhỏ gọn các sử dụng các thành phần điểm màu. Hơn nữa, phát điểm ảnh khi so sánh với toàn bộ tập dữ liệu và hiện cạnh màu và biến đổi wavelet rời rạc được sử tập này cũng chứa các kết quả thu được từ tất cả dụng để biểu diễn độ phức tạp của thuật toán [1]. toán tử . Như vậy, chúng ta thấy xu hướng trong nhiều hệ thống CBIR là sử dụng kết hợp nhiều tính năng để Keywords- Truy xuất hình ảnh dựa trên nội dung (CBIR), phản hồi mức độ liên quan (RF), phương pháp truy xuất hình ảnh.Về mặt trực quan, người dùng tiếp cận Pareto không dễ dàng nhận ra hình ảnh dựa trên các khía cạnh như màu sắc và hình dạng, những người khác I. GIỚI THIỆU nhau với cùng một hình ảnh có thể cho ra 1 hình Sự xuất hiện của Internet thay đổi hoàn toàn cách ảnh khác nhau. Hình ảnh khác nhau có thể có ý chúng ta tìm kiếm thông tin. Ví dụ, khi làm việc với nghĩa khác nhau hoặc mức độ quan trọng khác nhau văn bản, chỉ cần gõ từ khóa vào các công cụ tìm đối với mỗi người. Ví dụ: cho một hình ảnh cho kiếm như Google hay Bing, chúng ta có thể nhận thấy một con chim trên bầu trời, một số người có ngay danh sách các trang web phù hợp nhất với chất thể quan tâm đến con chim, trong khi những người lượng (nói chung) có thể chấp nhận được. Một hệ khác có thể quan tâm đến bầu trời. thống tương đương như vậy cho hình ảnh, tức là lấy Giả sử rằng mỗi đối tượng được liên kết với một đầu vào hình ảnh từ người dùng, cố gắng sắp xếp thước đo khoảng cách, thì mỗi hình ảnh có nhiều các hình ảnh tương tự nhất trong tập dữ liệu hình khoảng cách liên quan đến một hình ảnh truy vấn ảnh của nó, sau đó trả lại cho người dùng. Sự tương trong không gian tìm kiếm nhiều chiều. Cho một đồng ở đây là dựa trên sự tương đồng của các hình hình ảnh truy vấn, theo từng đặc điểm của hình ảnh, ISBN: 978-604-80-5076-4 50
2. Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020) chúng ta có thể tìm một số hình ảnh lân cận [2,3]. mức độ liên quan để hiểu được nhận thức của người Nếu xét bài toán trong không gian nhiều chiều, điểm dùng. Bằng cách tương tác với người dùng, phản ảnh thường là tập con của các điểm lân cận trước đó hồi về mức độ liên quan cung cấp thêm thông tin để chúng tôi có thể suy luận chính xác hơn về sở thích liên kết với mỗi chiều. Chức năng được sử dụng để của người dùng trong số nhiều tính năng, tức là tính sắp xếp mức độ phù hợp giữa điểm ảnh đó. Do đó năng nào quan trọng hơn những tính năng khác phải tính toán số đo khoảng cách tổng hợp cho mỗi trong nhận thức của họ. điểm ảnh dựa trên một số thuật toán kết hợp có trọng số của các phép đo khoảng cách riêng lẻ. 2.2. Bài toán tối ưu trên miền không gian độ Trong bài báo này, nhóm tác giả đề xuất sử dụng đo khoảng cách phương pháp tiếp cận Pareto để lựa chọn các điểm Tập Pareto là một tập con của tập các điểm ảnh.Thay vì thuật toán truy vấn cho các hình ảnh có liên quan đã chọn hoặc chỉ áp dụng phương pháp thoả hiệp của các lời giải trong đó chứa tất cả các SVM. Nhóm tác giả đề xuất một thuật toán nhằm điểm mà có ít nhất một mục tiêu tối ưu trong khi tạo ra một tập hợp nhỏ gọn các điểm ảnh khi so giữ nguyên mọi mục tiêu khác. Các điểm đó được sánh với toàn bộ tập dữ liệu và tập này và các kết gọi là các điểm tối ưu Pareto. quả thu được từ tất cả các phép tính toán. Bài toán tối ưu trên miền không gian độ đo Bài báo được trình bày như sau: Phần 2: Cơ sở toán khoảng cách của truy vấn với các mẫu trong cơ học, Phần 3: Đề xuất thuật toán dựa trên phương sở dữ ảnh phát biểu như sau: pháp tiếp cận Pareto để tối ưu không gian tìm kiếm. Phần cuối là kết luận và tài liệu tham khảo. min D t (I ), t {1, ,T} Q , (1) F s.t . I Ei , i {1, , M } II. CƠ SỞ TOÁN HỌC 2.1. Phương pháp tiếp cận Pareto trong đó truy vấn Q biểu diễn bởi một tập T đặc Phương pháp Pareto có thể được tìm thấy trong nhiều công trình liên quan đến cơ sở dữ liệu [4], trưng và các phần tử ảnh I của tập dữ liệu E F hoặc [5]. Trong [8] đề xuất một kỹ thuật sử dụng tính tối ưu Pareto để thực hiện quá trình lọc trước gồm M ảnh bao gồm các đặc trưng tương ứng nhằm loại bỏ các đối tượng ít đại diện hơn khỏi quá t như truy vấn. DQ ( I ) D(Qt , It ) là độ đo khoảng trình lựa chọn k-láng giềng trong khi vẫn giữ lại cách giữa đặc trưng thứ t biểu diễn bởi các thành những đối tượng đại diện nhất. Công việc này nhận được kết quả của một truy vấn bao gồm tất cả các phần Qt và It. điểm Pareto. Bộ Pareto bao gồm các đối tượng liên Định nghĩa 3.1. (Tập Pareto trên độ đo khoảng kết không gian với truy vấn nhiều hơn phương pháp cách) Cho truy vấn Q, xác định một quan hệ trội sử dụng phương pháp đo khoảng cách. Trong bài báo [2] đã kết hợp hai phương pháp phản hồi mức (ký hiệu là f) trên tập độ đo khoảng cách của hai độ liên quan dựa vào phương pháp đo dựa trên ảnh I1 và I2 như sau: khoảng cách. Bài báo, [9] đã đề xuất một thuật toán truy xuất thông tin nhiều truy vấn kết hợp Pareto với Phương pháp E Cient (EMR). Đối với mỗi truy vấn, EMR được sử dụng để tạo ra một danh sách các kết quả được sắp xếp dựa trên độ đo tương tự. Sau đó, Quan hệ trội yếu, ký hiệu là DQ ( I1 ) DQ ( I2 ) phương pháp Pareto được xây dựng dựa trên các kết khi và chỉ khi: quả này. Ưu điểm của phương pháp Pareto trong hệ thống CBIR, có thể thu gọn không gian tìm kiếm. Do đó, nó có khả năng cải thiện hiệu suất của hệ III. ĐỀ XUẤT THUẬT TOÁN thống CBIR. Chúng tôi đề xuất sử dụng cách tiếp cận Pareto, kết hợp với phương pháp phản hồi về 2.1 Bài toán: ISBN: 978-604-80-5076-4 51
3. Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020) Giả sử chúng ta có hai đặc trưng màu (C) và kết Sau khi sắp xếp T danh sách, thuật toán chỉ cấu (T). Độ đo khoảng cách của ba đối tượng 01, thực hiện trên phép so sánh, lần lượt lấy từng ảnh 02, 03 tương ứng với truy vấn Q là: chưa được đánh dấu trong mỗi danh sách so sánh tập độ đo khoảng cách với tập giá trị ngưỡng aTupleMax. Tập giá trị ngưỡng aTupleMax được thiết lập sao cho mỗi thành phần của nó có giá trị Khoảng cách toàn cục áp dụng kết hợp tuyến tính cao nhất trong tất cả các điểm Pareto đã tìm được. độ đo khoảng cách thành phần của các đặc Thuật toán đề xuất sử dụng định nghĩa 3.1 kết trưng màu và kết cấu tương ứng là: hợp với tập giá trị aTupleMax để so sánh lấy ra các điểm Pareto theo nhiều mức, quá trình tiếp tục đến khi số điểm cần lấy đạt được k điểm, Dễ dàng xếp hạng độ đo khoảng cách là 02, 03, được gọi là tập Pareto nhiều mức sâu. Quá trình 01. Khi không kết hợp tuyến tính độ đo khoảng tăng dần mức độ sâu đến khi tìm đủ số điểm theo cách toàn cục, xếp hạng dựa vào độ đo khoảng độ sâu hoặc hết cơ sở dữ liệu. cách thành phần chúng ta chỉ có thể xếp hạng 2.3 Đánh giá độ phức tạp của thuật toán được 01 , 02 đối tượng 03 không thể so sánh được với hai đối tượng còn lại. Thuật toán có độ phức tạp là O(n) , trong đó Như vậy cách xếp hạng sử dụng tổng toàn bộ các phép toán được sử dụng chỉ toàn các phép so độ đo khoảng cách của các thành phần trong kết sánh nên thời gian thực hiện nhanh. quả cuối cùng còn nhiều vấn đề cần xem xét và Theo mệnh đề A, tập Pareto nhiều mức sâu cải tiến. Do đó nhóm tác giả đề xuất thuật toán chứa các điểm có độ đo khoảng cách tối thiểu sau. theo thành phần và tối thiểu theo cách kết hợp 2.2 Thuật toán tuyến tính. A, Mệnh đề 1 Theo mệnh đề B, các điểm trong cùng một mức sâu thì không thể so sánh với nhau, các điểm F t I E , DQ (I), nếu:t0 ,1 t0 T , DQ 0 ( I ) ở mức trong sâu hơn thì bị làm trội ở mức ngoài. M t 1 Như vậy tập Pareto depth bao được các điểm liên Min DQ 0 (I'), thì I PF . '{EF } quan về độ đo khoảng cách mức thấp. Tuỳ thuộc Chứng minh: Giả sử số mức rìa, tập này có số mẫu nhỏ hơn toàn bộ cơ I PF 1 I ' EF , 1 t T, Dt(I ') Dt (I) sở dữ liệu. Tập Pareto chứa tất cả các điểm không F trội với các điểm khác trong E , DQ ( I ). B, Mệnh đề 2 Tập này chứa tất cả các phần tử tối thiểu hoá bằng cách kết hợp tuyến tính, nhưng cũng chứa các phần tử khác mà không tìm thấy nếu kết hợp tuyến tính. Chứng minh: (i) được suy từ định nghĩa PF1. (ii) Giả sử I PF1. Thuật toán đề xuất sử dụng mệnh đề 1 và mệnh đề 2. ISBN: 978-604-80-5076-4 52
4. Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020) Thuật toán đề xuất Đầu vào: /*Danh sách sắp thứ tự Tuple có T danh sách N ảnh, mỗi ảnh có T giá độ đo khoảng cách theo từng đặc trưng với truy vấn Q */k / * Số lượng mẫu trong tập Pareto */ Đầu ra: ListResult /*Tập rìa Pareto */ /* Biến trung gian */ Result=0; PF=PF_Next= ; aTupleMax =0; aMax=0; /* Khởi tạo */ 1. TopTuple = 0; 2. While (Result <k) 3. While Ii PF mà ( DQ (I i ) faTupleMax) (Result <k) 4. For t=1 to T 5. Lấy ra ảnh Ii chưa được lấy trong danh sách đã sắp thứ tự Tuplet cùng với T độ đo khoảng cách DQ (I i ) ; t 6. IF aMax DQ (I i ) < aMax = D Q (I i ) ; 7. isDominated = false; 8. While (not(isDominate)) Ij PF chưa được so sánh với Ii) 9. IF( DQ (I i )) chuyển Ij từ PF vào PF_Next; 10. End IF; 11. IF(Ij Ii) 12. isDominated = true; 13. Chèn Ii vào PF_Next; 14. End IF 15. End While 16. IF not(isDominated) chèn vào PF; 17. aTupleMaxt =aMax; /* Đặt lại ngưỡng ở t */ 18. Đưa các ảnh PF mà aTupleMax vào ListResult; 19. Result = Result+1; 20. End For 21. End While 22. IF (Result<k) 23. PF = PF_Next; PF_Next=θ ; 24. For all Ii , Ij PF mà DQ (I i ) f DQ (I j) thì chuyển Ij sang PF_Next; 25. Đưa các ảnh Ij PF mà aTupleMax DQ (I i )vào ListResult; 26. End IF 27. End While ISBN: 978-604-80-5076-4 53
5. Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020) 4.KẾT LUẬN [12] Alberto Nonis, Marco Scortegagna , Alessandro Trong bài báo này, phương pháp tiếp cận Nonis , Benedetto Ruperti, “PRaTo: A web-tool to select Pareto trong không gian tìm kiếm sử dụng hệ thống optimal primer pairs for qPCR”, 2011, Elsevier Inc. All rights reserved. CBIR bằng cách sử dụng các mẫu được gắn nhãn và dữ liệu đầu vào theo thời gian thực. Từ đó khắc phục những hạn chế với các kỹ thuật mở rộng truy vấn trong MARS. Để kiểm tra chức năng PRaTo tất cả mẫu của các cặp từ các thí nghiệm đều được thu thập trongcơ sở dữ liệu qPCR [12] được truy xuất và xử lý bằng thuật toán PRaTo.Trong tương lai, nhóm tác giả tiếp tục mở rộng phương pháp Pareto để giảm tập hợp không gian tìm kiếm và áp dụng cho hình ảnh mục tiêu truy xuất trong dữ liệu lớn. Tài liệu tham khảo [1] S. Agarwal, A. K. Verma, and N. Dixit, Content based image retrieval using color edge detection and discrete wavelet transform," in Issues and Challenges in Intelligent Computing Techniques (ICICT), 2014 International Conference on. IEEE, 2014, pp. 368 [2] M. Arevalillo-Herraez, F. J. Ferri, and S. Moreno- Picot, Improving distance based image re-trieval using non- dominated sorting genetic algorithm," Pattern Recognition Letters, vol. 53, pp. 109, 2015. [3] G. Beliakov, A. Pradera, and T. Calvo, Aggregation functions: a guide for practitioners. Springer, 2007, vol. 221. [4] J. Chomicki, Querying with intrinsic preferences," in Advances in Database TechnologyEDBT 2002. Springer, 2002, pp. 34 [5] 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," Computer Vision and Image Understanding, vol. 106, no. 1, pp. 59, 2007 [6] P. Fishburn,Preference structures and their numerical representations," Theoretical Computer Science, vol. 217, no. 2, pp. 359, 1999. [7] Y. Freund, R. Schapire, and N. Abe, A short introduction to boosting," Journal-Japanese Society For Arti cial Intelligence, vol. 14, no. 771-780, p. 1612, 1999. [8] P. Hiremath, S. Shivashankar, and J. Pujari, Wavelet based features for color texture classi ca-tion with application to cbir," International Journal of Computer Science and Network Security, vol. 6, no. 9A, pp. 124, 2006. [9] K.-J. Hsiao, J. Calder, and A. O. Hero, Pareto- depth for multiple-query image retrieval," Image Processing, IEEE Transactions on, vol. 24, no. 2, pp. 583{594, 2015. [10] J. Huang, S. R. Kumar, M. Mitra, W.-J. Zhu, and R. Zabih, Image indexing using color correlograms," in Computer Vision and Pattern Recognition, 1997. Proceedings., 1997 IEEE Computer Society Conference on. IEEE, 1997, pp. 762 [11] AfshanLatif, Aqs Rasheed, Umer Sajid, Jameel Ahmed, NoumanAli, Naee Iqbal Ratyal,Bushra Zafar, Saadat Hanif Dar,Muhammad Sajid, and Tehmina Khalil, “Content-Based Image Retrieval and Feature Extraction: A Comprehensive Review”, Mathematical Problems in Engineering , 2019, pp.21. ISBN: 978-604-80-5076-4 54