Tài liệu Nghiên cứu phương pháp tra cứu ảnh con sử dụng kỹ thuật máy học

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 0 -- O O-- NGUYỄN ĐỨC HƢNG NGHIÊN CỨU PHƢƠNG PHÁP TRA CỨU ẢNH CON SỬ DỤNG KỸ THUẬT MÁY HỌC LUẬN VĂN THẠC SĨ : KHOA HỌC MÁY TÍNH Thái Nguyên, tháng 12 năm 2013 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 0 -- O O-- NGUYỄN ĐỨC HƢNG NGHIÊN CỨU PHƢƠNG PHÁP TRA CỨU ẢNH CON SỬ DỤNG KỸ THUẬT MÁY HỌC Chuyên ngành : Khoa Học Máy Tính Mã số : 60480101 LUẬN VĂN THẠC SĨ : CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC 1 : TS. NGUYỄN HỮU QUỲNH Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ LỜI MỞ ĐẦU Những năm gần đây, chúng ta đã chứng kiến sự tăng nhanh lƣợng dữ liệu ảnh cùng với sự phát triển bùng nổ của các ứng dụng trên Internet. Hàng ngày, nhiều cơ quan, tổ chức và cá nhân đã tạo ra nhiều Exa-bytes dữ liệu ảnh và đƣa chúng lên Internet. Khi số lƣợng ảnh trong tập ảnh còn ít, việc nhận diện một bức ảnh hay việc so sánh sự giống và khác nhau giữa các bức ảnh có thể thực hiện đƣợc bằng mắt thƣờng, tuy nhiên khi có số lƣợng rất lớn ảnh thì việc so sánh bằng mắt thƣờng là rất khó khăn, đòi hỏi phải có những phƣơng pháp hiệu quả và chính xác hơn. Việc tìm kiếm đƣợc một bức ảnh mong muốn trong hàng triệu bức ảnh thuộc đủ loại chủ đề khác nhau là rất khó khăn. Vấn đề đặt ra là phải có những phƣơng pháp tổ chức cơ sở dữ liệu ảnh tốt cùng với những kỹ thuật tìm kiếm, tra cứu ảnh hiệu quả, có độ chính xác cao và có hiệu năng tốt. Ban đầu, tra cứu ảnh đƣợc thực hiện dựa trên các mô tả ngắn bằng một tập các thuộc tính độc lập nội dung (tên file, khuôn dạng, loại, cỡ, tên tác giả và vị trí đĩa) của các ảnh. Tuy nhiên, cách tiếp cận này giới hạn các truy vấn vào các thuộc tính đã có. Một sự thay thế khác là sử dụng các chú thích văn bản thủ công hoặc các từ khóa sao cho các kỹ thuật tra cứu thông tin cổ điển có thể đƣợc sử dụng để tìm kiếm các ảnh. Nhƣng cách tiếp cận này vẫn có các vấn đề nhƣ sự nhập nhằng, không đầy đủ và chủ quan. Do dữ liệu ảnh rất phong phú về thông tin, để thu đƣợc nội dung của một ảnh sử dụng một số ít từ khóa là không khả thi, chƣa đề cập đến công việc tẻ nhạt trong quá trình chú thích. Một cách tiếp cận tự động và hiệu quả hơn đƣợc gọi là tra cứu ảnh dựa vào nội dung (CBIR), trong CBIR sử dụng các đặc trƣng ảnh mức thấp để biểu diễn, so sánh và tra cứu các ảnh. Hầu hết các hệ thống CBIR theo cách tiếp cận hai bƣớc để tìm kiếm các cơ sở dữ liệu ảnh. Đầu tiên (đánh chỉ số), một véc tơ đặc trƣng biểu diễn các thuộc tính quan trọng nào đó của ảnh đƣợc trích rút và lƣu trữ nhƣ siêu dữ liệu cho mỗi ảnh cơ sở dữ liệu. Thứ hai (tìm kiếm), một ảnh truy vấn đƣợc cho, các ảnh tƣơng tự nhất với ảnh truy vấn đƣợc trả về cho ngƣời sử dụng bằng việc so sánh các véc tơ đặc trƣng của các ảnh cơ sở dữ liệu với các đặc trƣng của ảnh truy vấn. Tất cả các hệ thống CBIR này thuộc về sơ đồ truy vấn bởi mẫu (QBE). Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Trong khi hầu hết các hệ thống CBIR tra cứu các ảnh dựa trên so sánh toàn bộ ảnh, tức là với một ảnh truy vấn đƣợc cho hệ thống trả về tất cả các ảnh tƣơng tự. Tuy nhiên, những ngƣời sử dụng có thể rất quan tâm đến tìm kiếm đối tƣợng. Trong trƣờng hợp này, ngƣời sử dụng cung cấp một ảnh con truy vấn (có thể là một đối tƣợng) mà hệ thống tra cứu sẽ tìm kiếm các ảnh mà chứa ảnh con truy vấn (theo nhận thức của con ngƣời) từ cơ sở dữ liệu ảnh. Truy vấn ảnh con cũng có thể là bản thân một ảnh. Nhiệm vụ này, gọi là tra cứu ảnh con dựa vào nội dung (CBsIR), là khó giải quyết bởi một loạt các hiệu ứng (nhƣ thay đổi cỡ và khác biệt về các vị trí quan sát,...) gây ra ảnh con mục tiêu khác nhau đáng kể trong các ảnh khác nhau. Một bài toán kết hợp với CBsIR là cách xác định vị trí ảnh con bên trong một ảnh cơ sở dữ liệu hiệu quả. Đề tài nghiên cứu tổng quan về tra cứu ảnh dựa vào nội dung và đi sâu vào nghiên cứu bài toán tra cứu ảnh con dựa vào nội dung (CBsIR) để tìm kiếm các ảnh cơ sở dữ liệu có chứa các ảnh con truy vấn. Bên cạnh đó, đề tài cũng kết hợp kỹ thuật máy học vào quá trình tra cứu ảnh con để đƣợc các kết quả gần với nhận thức của con ngƣời hơn. Trên những cơ sở phƣơng pháp tra cứu ảnh con truy vấn, tiến hành xây dựng chƣơng trình thử nghiệm cho phép đọc vào một ảnh con truy vấn và tìm kiếm những ảnh tƣơng tự với ảnh con truy vấn trong một tập hợp các ảnh cho trƣớc và thú nhận đánh giá phản hồi từ ngƣời dùng. Nội dung luận văn gồm có 3 chƣơng: CHƢƠNG 1: TỔNG QUAN VỀ TRA CỨU ẢNH CON DỰA VÀO NỘI DUNG VÀ HỌC TỪ THÔNG TIN NGƢỜI DÙNG. CHƢƠNG 2: TRA CỨU ẢNH CON DỰA VÀO NỘI DUNG SỬ DỤNG KỸ THUẬT MÁY HỌC, giới thiệu phƣơng pháp tra cứu ảnh con dựa vào cây phân cấp và sự kết hợp giữa tra cứu ảnh con và kỹ thuật máy học. CHƢƠNG 3: CHƢƠNG TRÌNH THỬ NGHIỆM, xây dựng hệ thống và trình bày một số kết quả đạt đƣợc. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ LỜI CẢM ƠN Trong quá trình thực hiện luận văn này, tôi luôn nhận đƣợc sự hƣớng dẫn, chỉ bảo tận tình của TS Nguyễn Hữu Quỳnh, Khoa Công nghệ Thông tin thuộc trƣờng Đại học Điện lực là cán bộ trực tiếp hƣớng dẫn khoa học cho tôi. Thầy đã giành nhiều thời gian trong việc hƣớng dẫn cách nghiên cứu, đọc tài liệu, cài đặt các thuật toán và giúp đỡ về xây dựng hệ thống thực nghiệm. Tôi xin chân thành cảm ơn các Thầy, Cô giáo trong trƣờng Đại học Công nghệ Thông tin và Truyền Thông, Đại học Thái Nguyên đã luôn nhiệt tình giúp đỡ và tạo điều kiện tốt nhất cho tôi trong suốt quá trình học tập tại trƣờng. Xin chân thành cảm ơn các anh, các chị và các bạn học viên lớp Cao học - trƣờng Đại học Công nghệ Thông tin và Truyền Thông thuộc Đại học Thái Nguyên đã luôn động viên, giúp đỡ và nhiệt tình chia sẻ với tôi những kinh nghiệm học tập, công tác trong suốt khoá học. Hà nội, ngày 25 tháng 12 năm 2013 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Ý KIẾN NHẬN XÉT .............................................................................................................. .............................................................................................................. .............................................................................................................. .............................................................................................................. .............................................................................................................. .............................................................................................................. .............................................................................................................. .............................................................................................................. .............................................................................................................. .............................................................................................................. .............................................................................................................. .............................................................................................................. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ MỤC LỤC Lời mở đầu Trang Chƣơng 1: TỔNG QUAN VỀ TRA CỨU ẢNH CON DỰA VÀO NỘI DUNG VÀ HỌC TỪ THÔNG TIN NGƢỜI DÙNG .......................................................................10 1.1 Giới thiệu.............................................................................................................10 1.1.1 Tra cứu ảnh dựa vào nội dung .....................................................................10 1.1.2 Tra cứu ảnh con dựa vào nội dung ..............................................................12 1.2 Tra cứu ảnh dựa vào màu ....................................................................................12 1.2.1 Các không gian màu ....................................................................................13 1.2.2 Biểu diễn và mô tả ảnh dựa vào màu ...........................................................14 1.2.3 Hàm khoảng cách.........................................................................................15 1.3 Tra cứu thông tin .................................................................................................16 1.4 Học từ ngƣời dùng trong tra cứu thông tin .........................................................17 1.5 Một số nghiên cứu liên quan về tra cứu ảnh con dựa vào nội dung ...................21 1.5.1 Tra cứu ảnh con dựa vào phân hoạch ..........................................................21 1.5.2 Tra cứu ảnh con dựa vào điểm.....................................................................23 1.6 Kết luận chƣơng 1 ...............................................................................................24 Chƣơng 2 : TRA CỨU ẢNH CON DỰA VÀO NỘI DUNG SỬ DỤNG KỸ THUẬT MÁY HỌC………………………………………………………………………… 25 2.1 Giới thiệu bài toán ...............................................................................................25 2.2 Kỹ thuật tra cứu ảnh con dựa vào nội dung ........................................................25 2.2.1 Cấu trúc cây và phân hoạch phân cấp của phƣơng pháp HTM ...................26 2.2.2 Trích rút đặc trƣng sử dụng màu trung bình ................................................28 2.2.3 Các hàm khoảng cách véc tơ .......................................................................28 2.2.4 Chiến lƣợc tìm kiếm ....................................................................................31 2.3 Học trong tra cứu ảnh con dựa vào nội dung ......................................................32 2.3.1 Lƣợc đồ đánh lại trọng số ............................................................................33 2.3.2 Cập nhật trọng số .........................................................................................36 2.3.3 Tƣơng tự ảnh................................................................................................37 2.4 Kết luận chƣơng 2 ...............................................................................................39 Chƣơng 3: CHƢƠNG TRÌNH THỬ NGHIỆM ............................................................40 3.1. Biểu đồ hệ thống ................................................................................................40 3.1.1. Sơ đồ hệ thống tra cứu ảnh sử dụng phản hồi liên quan .............................40 3.1.2. Biểu đồ Use Case ........................................................................................41 3.1.3. Biểu đồ trình tự và biểu đồ hoạt động ........................................................41 3.1.4 Thiết kế cơ sở dữ liệu ..................................................................................45 3.2 Mô tả chƣơng trình ..............................................................................................46 3.3 Kết quả đạt đƣợc .................................................................................................47 3.4 Thực nghiệm thu hồi ảnh bằng thông tin phản hồi .............................................49 3.5 Kết luận chƣơng 3 ...............................................................................................51 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN.....................................................................52 TÀI LIỆU THAM KHẢO .............................................................................................53 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ DANH MỤC CÁC BẢNG, SƠ ĐỒ, HÌNH Hình 1.1: Kiến trúc hệ thống tra cứu ảnh dựa vào nội dung ...........................................9 Hình 1.2: Các không gian màu. .....................................................................................11 Hình 1.2.1: Phản hồi liên quan tìm kiếm trên các ảnh. .................................................16 Hình 1.2.2: Truy vấn tối ƣu Rocchio để tách các tài liệu liên quan. .............................17 Hình 1.2.3: Ứng dụng của thuật toán Rocchio’s. ..........................................................19 Hình 2.1: Phân hoạch phân cấp của một ảnh với cấu trúc cây kết quả và chuỗi chỉ số tƣơng ứng cho lƣu trữ. ...................................................................................................25 Hình 2.2: Ví dụ về các cấu trúc cây cho ảnh cơ sở dữ liệu và ảnh con truy vấn. .........28 Hình 2.3: Thuật toán HTM. ...........................................................................................30 Hình 2.4: Hình ảnh thu hồi với thông tin phản hồi của ngƣời dùng. ............................33 Hình 2.5: So sánh độ bất lợi của ảnh. ............................................................................34 Hình 3.1: Sơ đồ hệ thống tra cứu ảnh sử dụng phản hồi. ..............................................38 Hình 3.2: Biểu đồ Use Case. .........................................................................................39 Hình 3.3: Biểu đồ trình tự tác nhân tra cứu ảnh. ...........................................................39 Hình 3.4: Biểu đồ hoạt động của tác nhân tra cứu ảnh..................................................40 Hình 3.5: Biểu đồ trình tự tác nhân phản hồi ảnh. ........................................................41 Hình 3.6: Biểu đồ hoạt động của tác nhân phản hồi ảnh. ..............................................41 Hình 3.7: Biểu đồ trình tự của tác nhân Upload ảnh. ....................................................42 Hình 3.8: Biểu đồ hoạt động của tác nhân Upload ảnh. ................................................43 Hình 3.9 : Bảng cơ sở dữ liệu Image. ............................................................................43 Hình 3.10 : Bảng cơ sở dữ liệu Cluster .........................................................................44 Hình 3.11: Mối quan hệ giữa các bảng..........................................................................44 Hình 3.12: Số liệu các loại ảnh trong cơ sở dữ liệu. .....................................................45 Hình 3.13: Giao diện chính hệ thống tra cứu ảnh..........................................................46 Hình 3.14: Giao diện hiển thị kết quả truy vấn. ............................................................47 Hình 3.15: Hình ảnh truy vấn. .......................................................................................47 Hình 3.16: Hình ảnh thu hồi lần lặp thứ nhất. ...............................................................48 Hình 3.17: Hình ảnh thu hồi lần lặp thứ hai. .................................................................48 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ KÍ HIỆU CÁC CỤM TỪ VIẾT TẮT CBIR Content Base Image Retrieval Tra cứu ảnh dựa vào nội dung QBIC Query By Image Content Truy vấn theo nội dung ảnh CIE Commission internationale de Uỷ ban quốc tế về màu sắc l'éclairage HAC Hierarchical Agglomerative Clustering Phân cụm tích luỹ phân cấp CBC Color Base Clustering Phân cụm dựa vào màu MST Minimum Spainning Tree Cây mở rộng tối thiểu IRM Integrated Region Matching Đối sánh vùng tích hợp CSDL DataBase Cơ Sở Dữ Liệu Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Chƣơng 1: TỔNG QUAN VỀ TRA CỨU ẢNH CON DỰA VÀO NỘI DUNG VÀ HỌC TỪ THÔNG TIN NGƢỜI DÙNG 1.1 Giới thiệu 1.1.1 Tra cứu ảnh dựa vào nội dung Khi ta có nhu cầu tìm kiếm một vài bức ảnh trong một kho dữ liệu ảnh có thể lên tới vài trăm nghìn bức ảnh để minh họa cho một đề tài nào đó thì tuyệt đối không phải là chuyện đơn giản nếu chúng ta tìm kiếm một cách thủ công tức là xem lần lƣợt từng bức ảnh cho tới khi ta tìm thấy đƣợc bức ảnh có nội dung cần tìm. Song song với sự phát triển của các phƣơng tiện kỹ thuật số trong tƣơng lai, số lƣợng ảnh sẽ còn tăng nhiều hơn nữa. Do vậy nhu cầu thật sự đòi hỏi phải có một công cụ hỗ trợ tìm kiếm ảnh chính xác và hiệu quả. Vì vậy tra cứu ảnh dựa vào nội dung ra đời để góp phần đáp ứng nhu cầu này. “Tra cứu ảnh dựa vào nội dung” - Đây là một chủ đề nghiên cứu mới trong lĩnh vực công nghệ thông tin. Mục đích chính của nó là lấy những ảnh từ cơ sở dữ liệu phù hợp với tiêu chí truy vấn. Các yếu tố mô tả nội dung của một bức ảnh có liên quan đến cảm nhận nhƣ màu sắc, kết cấu, hình dạng, cấu trúc, mối liên hệ về không gian và chuyển động. Do vậy, phân tích ảnh, nhận dạng ảnh và thị giác máy tính đóng vai trò cơ bản trong các hệ thống tra cứu ảnh. Nó cho phép tự động trích chọn hầu hết các thông tin cảm nhận, thông qua việc phân tích phân bố điểm ảnh và rút ra các độ đo nội dung trực quan. Các hệ thống truy vấn ảnh dựa vào nội dung hiện nay rất đa dạng nhƣng nhìn chung đƣợc phân biệt bởi: các đặc trƣng mà hệ thống rút trích từ ảnh để làm cơ sở truy vấn, phƣơng pháp trích rút đặc trƣng ảnh đƣợc sử dụng trong hệ thống truy vấn, độ đo sự tƣơng tự giữa hai ảnh, phƣơng pháp đánh chỉ số nhiều chiều để tối ƣu việc tìm kiếm. Một số chức năng chính của một hệ thống tra cứu ảnh dựa vào nội dung: - Phân tích nội dung của nguồn thông tin và biểu diễn nội dung của các nguồn thông tin đƣợc phân tích phù hợp với sự đối sánh truy vấn của ngƣời sử dụng (không gian của thông tin nguồn đƣợc chuyển đổi thành không gian đặc điểm với mục đích đối sánh nhanh trong bƣớc tiếp theo). Bƣớc này thƣờng mất nhiều thời gian cho việc xử lý tuần tự các thông tin nguồn (ảnh) trong cơ sở dữ liệu. Nó chỉ phải làm một lần và có thể làm độc lập. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ - Phân tích các truy vấn của ngƣời dùng và biểu diễn chúng thành các dạng phù hợp với việc đối sánh với cơ sở dữ liệu nguồn. Nhiệm vụ của bƣớc này giống với bƣớc trƣớc nhƣng chỉ đƣợc áp dụng với những ảnh truy vấn. - Xác định chiến lƣợc để đối sánh tìm kiếm truy vấn với thông tin đƣợc lƣu trữ trong cơ sở dữ liệu. Bƣớc này có thể thực hiện trực tuyến và thực hiện rất nhanh. Công nghệ đánh chỉ số có thể đƣợc sử dụng để nhận dạng không gian đặc điểm để tăng tốc độ xử lý đối sánh. - Tạo ra sự điều chỉnh cần thiết trong hệ thống (thƣờng là bằng cách đối chiếu các tham số trong công nghệ đối sánh) dựa trên phản hồi từ ngƣời sử dụng hoặc những hình ảnh đƣợc tra cứu. Mô hình chung của các hệ thống tra cứu ảnh dựa vào nội dung: Thực hiện ngoại tuyến Tạo truy vấn Cơ sở dữ liệu đặc trƣng Trích rút đặc trƣng Đánh chỉ số Ngƣời sử dụng Trích rút đặc trƣng Cơ sở dữ liệu ảnh So sánh độ tƣơng tự Các kết quả tra cứu Đầu ra Phản hồi liên quan Hình 1.1: Kiến trúc hệ thống tra cứu ảnh dựa vào nội dung Chúng ta nhận thấy rằng trên một mặt của một hệ thống tra cứu ảnh dựa vào nội dung, có các nguồn thông tin trực quan ở các khuôn dạng khác nhau và trên mặt kia có các truy vấn ngƣời sử dụng. Hai mặt này đƣợc liên kết thông qua một chuỗi các tác vụ nhƣ đƣợc minh họa trong Hình 1.1. Hai tác vụ phân tích truy vấn ngƣời sử dụng và đánh chỉ số nhiều chiều đƣợc tóm lƣợc ở đây trong khi hai tác vụ quan trọng nhất: “Phân tích các nội dung của thông tin nguồn” (trích rút đặc trƣng) và “Định nghĩa một chiến lƣợc để đối sánh các truy vấn tìm kiếm với thông tin trong cơ sở dữ liệu đƣợc lƣu trữ” (độ đo tƣơng tự). Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 1.1.2 Tra cứu ảnh con dựa vào nội dung Trong khi hầu hết các hệ thống tra cứu ảnh tra cứu các ảnh dựa trên việc so sánh toàn bộ bức ảnh, ngƣời dùng lại muốn quan tâm “tìm kiếm đối tƣợng”, trong đó ngƣời dùng có thể chỉ rõ “vùng con quan tâm” (thƣờng là một đối tƣợng quan tâm) của một ảnh nhƣ một truy vấn. Sau đó hệ thống tra cứu các ảnh chứa vùng con này (theo nhận thức của ngƣời dùng) từ một cơ sở dữ liệu ảnh. Nhiệm vụ này đƣợc gọi là truy vấn ảnh con. Đây là nhiệm vụ có nhiều thách thức, do bị ảnh hƣởng bởi nhiếu yếu tố nhƣ khác nhau về vị trí quan sát, nhiễu camera, che lấp đối tƣợng,... là nguyên nhân của việc cùng một đối tƣợng có các xuất hiện khác nhau trong các ảnh khác nhau. Hệ thống cũng có thể giải quyết đƣợc vấn đề định vị trí, tức là có thể tìm vị trí của đối tƣợng trong một ảnh. Thiếu quá trình phân đoạn ảnh tốt cho các cơ sở dữ liệu ảnh lớn và không thuần nhất, hàm ý rằng các đối tƣợng phải đƣợc định vị trí trong các ảnh không phân đoạn, tạo ra sự khó khăn của bài toán định vị trí. Để xử lý các truy vấn ngƣời dùng, một số hệ thống sử dụng các phƣơng pháp phân hoạch lƣới cố định [1,3]. Để cải tiến tốc độ và độ chính xác của tra cứu dựa vào nội dung, cách tiếp cận đối sánh đa phân giải [2] đã đƣợc đề xuất, Ở đây, ảnh truy vấn có thể là một phác thảo hoặc ảnh quét đƣợc tra cứu. Tuy nhiên, trong nhiều hoàn cảnh, ngƣời dùng chỉ quan tâm hoặc nhớ các nội dung ảnh cục bộ, do đó, xử lý truy vấn ảnh con là cần thiết. Tuy nhiên, không có nhiều hệ quản trị cơ sở dữ liệu ảnh dựa trên sự tƣơng tự màu và không gian. Với các hệ thống có thể đề cập đến các truy vấn ảnh con với cỡ bất kỳ đối sánh đa phân giải không đƣợc sử dụng. 1.2 Tra cứu ảnh dựa vào màu Chọn các đặc trƣng ảnh đúng cho một hệ thống tra cứu ảnh là quan trọng bởi vì các đặc trƣng ảnh ảnh hƣởng đến mọi khía cạnh của toàn bộ quá trình tra cứu. Hầu hết các hệ thống tra cứu ảnh dựa vào nội dung (CBIR) sử dụng các đặc trƣng ảnh mức thấp nhƣ màu, kết cấu, hình,... do chúng có thể đƣợc trích rút tự động. Màu là đặc trƣng mức thấp đƣợc sử dụng phổ biến nhất, bởi vì màu đƣợc con ngƣời nhận thức ngay lập tức khi quan sát một ảnh và các khái niệm liên quan dễ hiểu và dễ cài đặt. Bên cạnh đó, màu là một trong những đặc trƣng nhận thức nổi trội trong phần lớn các lĩnh vực ảnh và sử dụng thông tin màu có thể thu đƣợc các kết quả thỏa mãn. Hầu hết các hệ thống CBIR thƣơng mại bao gồm màu nhƣ một trong các đặc trƣng ảnh (QBIC của IBM [4], Virage [5],..). Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 1.2.1 Các không gian màu Màu của một pixel trong một ảnh số đƣợc biểu diễn bởi ba giá trị, một cho mỗi kênh của không gian màu đƣợc chọn. Một không gian màu là một đặc tả của một hệ tọa độ 3D và không gian con trong hệ tọa độ đó nơi mỗi màu đƣợc biểu diễn bởi một điểm [6]. Bƣớc đầu tiên trong bất cứ một hệ thống tra cứu ảnh dựa vào màu nào là chọn một không gian màu, nới các ảnh sẽ đƣợc biểu diễn và so sánh. Không gian màu đƣợc sử dụng rộng rãi nhất là RGB (Red, Green, Blue)[6, 7]. Không gian màu RGB là phụ thuộc thiết bị (màu hiển thị không chỉ phụ thuộc vào các giá trị RGB, mà còn phụ thuộc vào các đặc tả thiết bị). Hạn chế chính của mô hình này là không đồng nhất về mặt nhận thức (theo một nghĩa nào đó, sự khác biệt về các màu RGB không phản ánh sự khác biệt đƣợc nhận thức bởi con ngƣời). Không gian màu RGB là một khối đƣợc chỉ ra ở hình 1.2 dƣới, ở đây đƣờng chéo chính biểu diễn các giá trị xám từ đen tới trắng, và các điểm bên trong hình khối đƣợc biểu diễn bởi tổng trọng số của R, G, B [8]. Hình 1.2 Các không gian màu. Loại không gian màu khác là các không gian màu đồng nhất, ở đây các khác biệt số giữa các màu phù hợp với các khác biệt đƣợc nhận thức bởi con ngƣời. Mô hình CIE Lab là một ví dụ nhƣ thế. Nhƣ đƣợc chỉ ra trong hình 1(b), không gian màu CIE Lab biểu diễn các khác biệt của ba cặp cơ bản: red-green, yellow-blue và black-white. Khác so với không gian màu RGB, không gian màu CIE Lab độc lập thiết bị. Loại thứ ba đƣợc gọi là không gian màu hƣớng ngƣời dùng [9,10], dựa vào nhận thức của con ngƣời về màu nhƣ hue, saturation và intensity. Một số ví dụ về loại này là không gian màu HSI và HSV. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 1.2.2 Biểu diễn và mô tả ảnh dựa vào màu Để thu đƣợc độ chính xác và tốc độ trong các hệ thống tra cứu ảnh, một mô tả nén và chính xác về phân bố màu và phân bố không gian của các màu trong các ảnh số là cần thiết. Các mô tả này có thể đƣợc giảm về cỡ bằng các phƣơng pháp giảm tĩnh và động. Các phƣơng pháp tĩnh sử dụng lƣợc đồ cỗ định cho mỗi ảnh. Lƣợc đồ đơn giản nhất để giảm số các màu trong một ảnh là sử dụng lƣợng hóa thô và đều cho mỗi kênh màu. Ví thế, các màu thu đƣợc không cần biểu diễn rõ ràng và so sánh các ảnh dễ hơn. Tuy nhiên, có thể các màu xuất hiện trong một ảnh không đƣợc phân bố đều trong không gian màu. Nó cũng không thích hợp cho các không gian màu không đồng nhất nhƣ HSV, do các màu tƣơng tự có thể khác nhau và các màu không tƣơng tự đƣợc phân lớp cùng nhau.Một vấn đề khác là khó thu đƣợc một thỏa hiệp đầy đủ về mật độ của lƣợng hóa cho các màu đƣợc phân bố không nhất thiết đồng nhất trong không gian màu. Các phƣơng pháp giảm động sử dụng nội dung trực quan của các ảnh và dựa trên các kỹ thuật phân đoạn để giảm cả số các màu và số các vị trí không gian trong một ảnh. Mọt kỹ thuật phân đoạn ảnh tiêu biểu nhóm các pixel lân cận có cùng màu với nhau thành các vùng (màu của vùng là màu trung bình của các pixel). Các vùng sau khi đƣợc sinh ra sẽ nén và có ý nghĩa hơn vì chúng có độ tƣơng tự màu cao và hình dạng, cỡ và vị trí không gian đƣợc xác định tốt. Một số kỹ thuật phân đoạn ảnh bao gồm: phát hiện đƣờng biên, phát triên vùng, nhập và tách vùng [6]. Ngay khi mô tả của ảnh đƣợc chọn, một biểu diễn của thông tin này là bƣớc tiếp theo trong các hệ thống tra cứu ảnh. Lƣợc đồ màu đã đƣợc sử dụng rộng rãi để mô tả thông tin màu của các ảnh do nó dễ tính toán, ít nhạy cảm với các thay đổi hƣớng và vị trí, khả thi về mặt bộ nhớ, hiệu quả trong so sánh sử dụng các hàm khoảng cách véc tơ và đủ chính xác cho tra cứu các ảnh dựa trên ấn tƣợng màu tổng thể. Thông tin đƣợc lƣu trữ về nội dung trực quan của một ảnh có thể đƣợc biểu diễn trong ba cách đƣợc mô tả tiếp theo. Các biểu diễn toàn cục mô tả phân bổ màu của toàn bộ ảnh, bỏ qua phân bố không gian của các màu. Biểu diễn toàn cục đƣợc sử dụng phổ biến nhất là lƣợc đồ màu toán cục (GCH) [9,10]. Một GCH đƣợc tính toán bằng việc đếm số các pixel Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ trong ảnh có mỗi màu đƣợc lƣợng hóa. Tuy nhiên, do lƣợc đồ màu toàn cục bỏ qua thông tin không gian, nó bị giới hạn khả năng phân biệt ảnh. Một cách khác để thay thế là sử dụng các biểu diễn dựa vào phân hoạch để mô tả phân bố màu của mỗi phân hoạch đơn lẻ của một ảnh. Nhìn chung, ảnh đƣợc phân hoạch tĩnh thành một tập các khối hình chữ nhật theo lƣợc đồ nào đó và một lƣợc đồ màu cục bộ (LCH) đƣợc sử dụng để mô tả mỗi khối phân hoạch riêng lẻ. Trong loại biểu diễn này, thông tin mở rộng về các thuộc tính không gian của các khối phân hoạch nhƣ cỡ, hình và vị trí không gian đƣợc ghi lại. Một số cách tiếp cận dựa vào phân hoạch cũng sử dụng các loại lƣợc đồ màu khác [11,12]để giới thiệu một số thông tin không gian về nội dung trực quan của các ảnh phân rã chúng thành các khối không gian theo lƣợc đồ cố định. Ngoài hai biểu diễn trên, còn có biểu diễn vùng cho tra cứu ảnh mức đối tƣợng. Dựa trên biểu diễn ảnh, các kỹ thuật tra cứu ảnh dựa vào màu đã có có thể đƣợc phân lớp thành ba loại chính: (1) các cách tiếp cận toàn cục [9,10], (2) các cách tiếp cận dựa vào phân hoạch [11,12], (3) các cách tiếp cận dựa vào vùng [13,14]. Mỗi loại này đƣa ra một thỏa hiệp riêng giữa độ phức tạp của thuật toán phân tích ảnh, lƣợng không gian nhớ đƣợc yêu cầu để biểu diễn các đặc trƣng trực quan đƣợc trích rút từ các ảnh, độ phức tạp của hàm khoảng cách đƣợc sử dụng để so sánh các đặc trƣng này và độ chính xác tra cứu. 1.2.3 Hàm khoảng cách Sự thành công của bài toán tra cứu ảnh phụ thuộc chính vào hai nhân tố. Nhân tố thứ nhất là sự ổn định của các đặc trƣng ảnh đƣợc sử dụng, nhân tố thứ hai là các đặc tính của hàm khoảng cách đƣợc sử dụng cho so sánh các đặc trƣng ảnh. Hàm khoảng cách ảnh hƣởng trực tiếp đến thời gian xử lý truy vấn và độ chính xác tra cứu. Khoảng cách mô phỏng nhận thức về sự tƣơng tự của con ngƣời tốt hơn, hiệu quả hơn thì hệ thống tra cứu ảnh tra cứu các ảnh liên quan dến nhu cầu của ngƣời dùng. Độ phức tạp tính toán của hàm khoảng cách cũng đƣợc xem xét là một nhân tố quan trọng khi xử lý một truy vấn trực quan. Hơn nữa, hàm khoảng cách giới hạn sử dụng các kỹ thuật lọc khác nhau và/hoặc các phƣơng pháp truy cập có thể đƣợc sử dụng để tăng tốc xử lý truy vấn. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Một số hàm khoảng cách véc tơ đƣợc biết rộng rãi [15] gôm: L (City Block):L (a,b) 1 1 k |a b | i i i 1 k 1 L (Euclidean):L (a,b) ( |a b |2 ) 2 i i 2 2 i 1 L (Chebyshev):L (a,b) maxkx 1 | ai bi | Ở đây a=(a1,a2,...,ak) và b=(b1,b2,...,bk), cả hai là các véc tơ đặc trƣng k chiều. Mô hình các véc tơ đặc trƣng trong không gian véc tơ có ƣu điểm rằng khoảng cách hình học đƣợc sử dụng để so sánh hai véc tơ là đơn giản về mặt tính toán. Tuy nhiên, có các trƣờng hợp khác, nhƣ trong các hệ thống tra cứu ảnh dựa vào vùng, nó không thể mô hình các hệ thống tra cứu ảnh phức tạp trong không gian véc tơ. Trong ngữ cảnh đó, một không gian độ đo, không có giới hạn về biểu diễn các đặc trƣng trực quan. Một độ đo đƣợc đề xuất để đo khoảng cách giữa hai phân bố của một số biến ngẫu nhiên trong một ảnh, nhƣ các lƣợc đồ màu, là EMD [16]. EMD phản ảnh lƣợng công việc tối thiểu mà phải đƣợc thực hiện để biến đổi một phân bố thành phân bố khác bằng việc dịch chuyển “khối lƣợng phân bố” xung quanh. Nó bắt nguồn từ bài toán vận tải trong tối ƣu tổ hợp. EMD có thể đƣợc tính bằng việc giải bài toán qui hoạch tuyến tính, vì thế độ phức tạp tính toán cao. Thêm nữa, nghiên cứu gần đây trong thị giác máy tính và tâm lý học hàm ý rằng nhận thức của con ngƣời về sự tƣơng tự mẫu thuẫn với các cách khác nhau với các tiên đề độ đo (quá hạn chế trong ngữ cảnh tìm kiếm tƣơng tự). Một trong những tiên đề độ đo chủ yếu là bất đẳng thức tam giác, tiên đề quan trọng nhất cho các mục tiêu đánh chỉ số [17]. 1.3 Tra cứu thông tin Tra cứu thông tin (IR – Information Retrieval) là việc thu thập các nguồn thông tin liên quan trong một tập các nguồn tài nguyên. Hệ thống tra cứu thông tin tự động đƣợc sử dụng để giảm tình trạng “quá tải thông tin”. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Quá trình tra cứu thông tin bắt đầu với việc ngƣời dùng nhập một truy vấn vào hệ thống. Các truy vấn là những câu lệnh chính thức của thông tin cần tìm. Truy vấn phụ thuộc vào các ứng dụng của các đối tƣợng có thể là văn bản, hình ảnh, audio, bản đồ tƣ duy hoặc video. Thƣờng thì bản thân các tài liệu không đƣợc trực tiếp lƣu trữ trong hệ thống IR mà đƣợc thể hiện trong hệ thống bằng các tài liệu đại diện hoặc các siêu dữ liệu. 1.4 Học từ ngƣời dùng trong tra cứu thông tin Ý tƣởng của học từ ngƣời dùng là bao gồm ngƣời dùng vào quá trình tra cứu để cải tiến tập kết quả cuối cùng. Cụ thể, ngƣời dùng đƣa phản hồi về sự liên quan của các tài liệu trong một tập các kết quả ban đầu. Thủ tục cơ sở là: - Ngƣời dùng tạo một truy vấn. - Hệ thống trả lại một tập các kết quả tra cứu ban đầu. - Ngƣời dùng đánh dấu một số tài liệu đƣợc trả về là tƣơng tự hoặckhông tƣơng tự. - Hệ thống tính toán một đại diện tốt nhất của nhu cầu thông tin (IN – Information Need) dựa trên thông tin từ ngƣời dùng. - Hệ thống hiển thị một tập các kết quả tra cứu đƣợc hiệu chỉnh (tƣơng ứng với các thông tin từ ngƣời dùng). Học từ ngƣời dùng có thể đi qua một hay nhiều vòng lặp của sự sắp xếp này. Quá trình sử dụng ý tƣởng có thể khó để tính một truy vấn tốt khi chúng ta không biết toàn bộ tập tài liệu, nhƣng dễ đánh giá các tài liệu cụ thể. Trong ngữ cảnh nhƣ thế, học từ ngƣời dùng cũng có thể hiệu quả trong theo dõi nhu cầu thông tin của ngƣời dùng: xem một số tài liệu có thể dẫn ngƣời dùng cải tiến hiểu thông tin mà họ đang tìm. Tìm kiếm ảnh cung cấp một ví dụ tốt về học từ ngƣời dùng. Không chỉ là dễ xem các kết quả khi làm việc, mà còn là một lĩnh vực mà ngƣời dùng dễ trình bày nhu cầu thông tin hơn (dùng lời khó biểu diễn nhu cầu thông tin hơn ảnh). Sau khi ngƣời dùng nhập vào một truy vấn khởi tạo là bike. Các kết quả ban đầu đƣợc trả về (giả sử đối với dữ liệu ảnh). Trong Hình 1.2.1a, ngƣời dùng chọn một số ảnh liên quan. Các ảnh liên quan này sẽ đƣợc sử dụng để cải tiến truy vấn, trong khi các kết quả đƣợc hiển thị còn lại không ảnh hƣởng đến kết quả. Hình 1.2.1b, chỉ ra các kết quả đƣợc phân hạng mới đƣợc tính sau vòng phản hồi liên quan. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ (a) (b) Hình 1.2.1 Phản hồi liên quan tìm kiếm trên các ảnh. (a) người dùng xem các kết quả truy vấn ban đầu của truy vấn bike, lựa chọn kết quả thứ nhất, thứ ba và thứ 4 trong dòng trên cùng và kết quả thứ 4 trong dòng cuối cùng là liên quan và gửi phản hồi này. (b) người dùng xem tập kết quả được hiệu chỉnh. Độ chính xác được cải tiến rất nhiều.  Lý thuyết cơ bản: Chúng ta muốn tìm một véc tơ truy vấn, đƣợc biểu thị bằng q , mà cực đại sự tƣơng tự với các tài liệu liên quan trong khi cực tiểu sự tƣơng tự với các tài Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ liệu không liên quan. Nếu Cr là tập các tài liệu liên quan và C nr là tập các tài liệu không liên quan, thì chúng ta muốn tìm:  qopt   arg q max sim(q, Cr ) sim(q, Cnr ) (1.1)   Trong phƣơng trình 1.1, sim(q, C r ) là độ tƣơng tự cosin giữa q và Cr ,      arg max q sim(q, Cr ) sim(q, Cnr ) trả lại q mà sim(q , Cr ) sim(q , Cnr ) đạt cực đại. Véc  tơ truy vấn tối ƣu qopt để tách các tài liệu liên quan và không liên quan là:  qopt 1 Cr  d Cr  dj 1 C nr  dj (1.2)  d Cnr Tức là, truy vấn tối ƣu là hiệu véc tơ giữa các trọng tâm của các tài liệu liên quan và không liên quan . Tuy nhiên, quan sát này rất không hữu ích bởi vì tập các tài liệu liên quan không đƣợc biết (là những gì chúng ta muốn tìm). Hình 1.2.2 Truy vấn tối ưu Rocchio để tách các tài liệu liên quan và không liên quan. Thuật toán Rocchio [36]. Đây là cơ chế học từ ngƣời dùng đƣợc giới thiệu và phổ biến bởi hệ thống SMART của Salton khoảng 1970. Trong ngữ cảnh truy vấn IR thực tế, chúng ta có một truy vấn ngƣời dùng và một phần tri thức về các tài liệu liên quan và  không liên quan. Thuật toán sử dụng truy vấn điều chỉnh q m  qm  q0 1 Dr  dj  d j Dr 1 Dnr  dj  d j Dnr  Ở đây q 0 là véc tơ truy vấn gốc, Dr và Dnr là tập các tài liệu liên quan và không liên quan đã biết tƣơng ứng, và , và là các trọng số đƣợc gắn kèm với các số hạng. Các trọng số này điều khiển sự cân bằng giữa độ tin cậy của tập các tài liệu Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ với truy vấn: nếu chúng ta có nhiều tài liệu tin cậy, chúng ta mong muốn lớn và hơn. Bắt đầu từ q0, truy vấn mới chuyển một số khoảng cách về phía trọng tâm của tài liệu liên quan, một số khoảng cách ra xa tài liệu không liên quan. Truy vấn mới này có thể đƣợc sử dụng cho tra cứu trong mô hình không gian véc tơ chuẩn. Có thể dễ dàng loại bỏ góc phần tƣ dƣơng của không gian véc tơ bằng phép trừ véc tơ của tài liệu không liên quan. Trong thuật toán Rocchio, trọng số thuật ngữ âm bị loại bỏ do đó đƣợc thiết lập bằng 0. Hình 1.3 cho thấy hiệu quả của ứng dụng học từ ngƣời dùng. Học từ ngƣời dùng có thể đƣợc cải thiện cả độ chính xác và độ triệu hồi. Thực tế cho thấy tăng độ triệu hồi hữu ích nhất trong trƣờng hợp độ triệu hồi là quan trọng. Điều này một phần do công nghệ mở rộng các truy vấn, nhƣng một phần cũng do ảnh hƣởng của trƣờng hợp: khi muốn độ triệu hồi cao, ngƣời dùng dự kiến có thể mất thời gian để xem lại các kết quả và lặp lại việc tìm kiếm. Phản hồi tích cực cũng trả về nhiều giá trị hơn phản hồi tiêu cực, do đó mà phần lớn hệ thống IR chọn < . Do đó giá trị =0,75 và = 1, = 0,15. Trong thực tế, nhiều hệ thống , nhƣ hệ thống tìm kiếm ảnh Hình 1.1, chỉ cho phép các phản hồi tích cực tƣơng đƣơng với =0. Trƣờng hợp khác là chỉ đánh dấu các tài liệu không liên quan nhận đƣợc thứ hạng cao nhất từ hệ thống IR nhƣ là phản hồi tiêu cực (ở đây |Dnr| =1 trong biểu thức (1.3). Trong khi rất nhiều các kết quả thực nghiệm so sánh các dạng thông tin phản hồi khác nhau là khá thuyết phục, một số nghiên cứu cho thấy dạng này đƣợc gọi là Ide dec-hi là hiệu quả nhất hoặc ít nhất là biểu diễn ổn định nhất. Hình 1.2.3 Ứng dụng của thuật toán Rocchio’s. Một số tài liệu đã được gán nhãn là liên quan hay không liên quan và véc tơ truy vấn ban đầu đã được dịch chuyển tương ứng từ phản hồi này. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/