Đề tài Thiết kế hệ thống truy tìm ảnh dựa vào đặc trưng cấp thấp và đặc trưng cấp cao

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ TRI THỨC W X NGUYỄN BÁ CÔNG NGUYỄN HỮU ĐỨC THIẾT KẾ HỆ THỐNG TRUY TÌM ẢNH DỰA VÀO ĐẶC TRƯNG CẤP THẤP VÀ ĐẶC TRƯNG CẤP CAO LUẬN VĂN CỬ NHÂN TIN HỌC Tp. Hồ Chí Minh –Năm 2005 TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ TRI THỨC W X NGUYỄN BÁ CÔNG -0112127 NGUYỄN HỮU ĐỨC -0112168 THIẾT KẾ HỆ THỐNG TRUY TÌM ẢNH DỰA VÀO ĐẶC TRƯNG CẤP THẤP VÀ ĐẶC TRƯNG CẤP CAO LUẬN VĂN CỬ NHÂN TIN HỌC Giảng viên hướng dẫn Ths – Lý Quốc Ngọc Tp. Hồ Chí Minh –Năm 2005 Hệ thống truy tìm ảnh dựa vào đặc trưng cấp thấp và đặc trưng cấp cao Lời cảm ơn Đầu tiên chúng em xin chân thành gửi lời cảm ơn đến Thầy Lý Quốc Ngọc, người đã tận tình hướng dẫn, động viên và giúp đỡ chúng em trong suốt thời gian qua. Nếu không có lời chỉ dẫn, những tài liệu, những lời động viên khích lệ của Thầy thì luận văn này khó lòng hòan thiện được. Một lần nữa chúng em xin tỏ lòng biết ơn Thầy. Cũng xin gửi lời cảm ơn đến gia đình, bạn bè và những ngừơi thân đã ủng hộ động viên tinh thần chúng em để luận văn được hòan thành. Chúng em cũng xin chân thành cảm ơn các thầy cô trong khoa Công nghệ thông tin đã tận tình chỉ bảo và giúp đỡ chúng em trong suốt thời gian chúng em học đại học và trong suốt quá trình chúng em làm luận văn. Tp. Hồ Chí Minh, tháng 7 năm 2005 Nguyễn Bá Công – Nguyễn Hữu Đức Nguyễn Bá Công – Nguyễn Hữu Đức i Hệ thống truy tìm ảnh dựa vào đặc trưng cấp thấp và đặc trưng cấp cao Lời mở đầu Cùng với sự mở rộng của multimedia, với khối lượng hình ảnh và phim lưu trữ ngày càng lớn, cùng với sự phát triển vượt bậc của các thiết bị Điện Tử, Tin Học và Viễn Thông đã thu hút ngày càng nhiều những chuyên gia đi vào nghiên cứu những công cụ cung cấp cho việc lấy thông tin dữ liệu ảnh từ nội dung của chúng. Hiện nay trên thế giới việc truy tìm ảnh đã bước sang thời kỳ mới, thời kỳ truy tìm ảnh dựa vào nội dung .Việc truy tìm dữ liệu hình ảnh dựa vào nội dung ảnh ngày càng phát triển mạnh mẽ, nó khắc phục khuyết điểm của việc truy tìm ảnh dựa vào văn bản kí tự. Dữ liệu đầu vào được mô phỏng gần gũi với con người hơn, kết quả ảnh trả về mang ngữ nghĩa gần đúng với ảnh truy vấn hơn. Nằm trong xu hướng đó, trong luận văn này chúng em trình bày một mô hình truy tìm thông tin hình ảnh dựa vào nội dung thông qua đặc trưng cấp thấp và đặc trưng cấp cao của ảnh. Nó có thể được sử dụng bởi các tổ chức sở hữu tư liệu ảnh và video, thư viện số, ảnh vệ tinh, ảnh y học, giáo dục từ xa,… Nguyễn Bá Công – Nguyễn Hữu Đức ii Hệ thống truy tìm ảnh dựa vào đặc trưng cấp thấp và đặc trưng cấp cao NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... Tp. Hồ Chí Minh, ngày tháng 07 năm 2005 ThS.Lý Quốc Ngọc Nguyễn Bá Công – Nguyễn Hữu Đức iii Hệ thống truy tìm ảnh dựa vào đặc trưng cấp thấp và đặc trưng cấp cao NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... .................................................................................................................................... Tp. Hồ Chí Minh, ngày tháng 07 năm 2005 Nguyễn Bá Công – Nguyễn Hữu Đức iv Hệ thống truy tìm ảnh dựa vào đặc trưng cấp thấp và đặc trưng cấp cao Mục lục Lời cảm ơn ................................................................................................................ i Lời mở đầu ............................................................................................................... ii NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN.................................................... iii NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN....................................................... iv Mục lục .................................................................................................................... v Mục lục các hình ..................................................................................................... ix Thuật ngữ chuyên ngành....................................................................................... xiv Chương 1 Tổng quan ............................................................................................... 1 1.1. Hướng truy tìm ảnh dựa vào nội dung.......................................................... 2 1.2. Hệ thống tìm kiếm ảnh thế hệ đầu tiên (dựa vào văn bản) ........................... 3 1.3. Hệ thống tìm kiếm thông tin trực quan thế hệ mới....................................... 5 1.3.1 Các hệ thống tìm kiếm ảnh tĩnh .............................................................. 5 1.3.2 Các hệ thống tìm kiếm phim ảnh (video) ............................................... 6 1.3.3 Các hệ thống tìm kiếm ảnh 3 chiều và video.......................................... 6 1.3.4 Các hệ thống tìm kiếm trên Internet ....................................................... 6 1.4. Xu hướng phát triển từ đặc trưng cấp thấp đến đặc trưng cấp cao và tiến dần đến ngữ nghĩa....................................................................................................... 8 1.5. Một số hệ thống truy tìm ảnh dựa vào nội dung hiện nay .......................... 10 1.6. Sự hình thành “Hệ thống truy tìm ảnh dựa vào đặc trưng cấp thấp và đặc trưng cấp cao” .................................................................................................... 11 1.7. Hướng tiếp cận của bài toán........................................................................ 13 1.7.1 Xây dựng cơ sở dữ liệu ......................................................................... 13 1.7.2 Xây dựng hệ thống tìm kiếm ................................................................ 14 1.7.2.1 Tìm kiếm dựa vào sự phân bố mang tính tòan cục ........................ 14 1.7.2.1.1 Đặc trưng lược đồ màu ........................................................... 14 1.7.2.1.2 Đặc trưng vector liên kết màu (Color Coherence Vector)...... 14 1.7.2.1.3 Đặc trưng tự tương quan màu (AutoCorrelogram)................. 15 1.7.2.1.4 Đặc trưng lược đồ hệ số góc (Edge Direction Histogram) ..... 16 1.7.2.1.5 Đặc trưng Vector liên kết hệ số góc (Edge Direction Coherence Vector) ................................................................................................... 16 1.7.2.2 Tìm kiếm dựa vào sự phân bố mang tính cục bộ ........................... 17 1.7.2.3 Tìm kiếm theo vùng, đối tượng ..................................................... 18 1.7.2.4 Tìm kiếm theo ngữ nghĩa............................................................... 20 Chương 2 CÁC KHÁI NIỆM CƠ BẢN ................................................................ 21 2.1. Màu sắc ....................................................................................................... 22 2.1.1 Khái niệm về màu sắc ........................................................................... 22 2.1.2 Một số đặc tính vật lý đặc biệt về màu sắc ........................................... 22 2.1.3 Các hệ màu thông dụng......................................................................... 24 2.1.3.1 Hệ màu chuẩn RGB: ...................................................................... 24 2.1.3.2 Hệ màu CMY................................................................................. 25 2.1.3.3 Hệ màu YIQ................................................................................... 26 Nguyễn Bá Công – Nguyễn Hữu Đức v Hệ thống truy tìm ảnh dựa vào đặc trưng cấp thấp và đặc trưng cấp cao 2.1.3.4 Hệ màu L*a*b:............................................................................... 27 2.1.3.5 Hệ màu HSI: Hue-Saturation-Intensity.......................................... 27 2.1.4 Các đặc trưng về màu sắc ..................................................................... 30 2.1.4.1 Lược đồ màu (Histogram).............................................................. 30 2.1.4.2 Vector liên kết màu (Color Coherence Vector) ............................. 32 2.1.4.3 Đặc trưng tự tương quan màu (AutoCorrelogram)........................ 34 2.2. Vân (textture) .............................................................................................. 38 2.2.1 Khái niệm.............................................................................................. 38 2.2.2 Một số loại vân tiêu biểu....................................................................... 39 2.2.3 Ma trận đồng hiện (Co-occurrence Matrix) .......................................... 39 2.2.4 Phép biến đổi Wavelet .......................................................................... 41 2.3. Hình dáng.................................................................................................... 43 2.3.1 Khái niệm về biên cạnh......................................................................... 43 2.3.2 Các phương pháp phát hiện biên........................................................... 44 2.3.2.1 Phát hiện biên trực tiếp .................................................................. 44 2.3.2.2 Phương pháp phát hiện biên gián tiếp............................................ 48 2.3.3 Các đặc trưng về biên cạnh................................................................... 49 2.3.3.1 Lược đồ hệ số góc (Edge Direction Histogram) ............................ 49 2.3.3.2 Vector liên kết hệ số góc (Edge Direction Coherence Vector): .... 51 2.3.4 Vùng và các đặc trưng về vùng............................................................. 52 2.3.4.1 Đặc trưng màu................................................................................ 53 2.3.4.2 Đặc trưng vân................................................................................. 53 2.3.4.3 Đặc trưng hình dáng....................................................................... 53 2.4. Độ đo........................................................................................................... 55 2.4.1 Khái niệm.............................................................................................. 55 2.4.2 Một số độ đo thông dụng ...................................................................... 56 2.4.2.1 Khoảng cách Minkowsky: ............................................................. 56 2.4.2.2 Độ đo khoảng cách min-max: ........................................................ 56 2.4.2.3 Khoảng cách Euclide L2:............................................................... 56 2.4.2.4 Khoảng cách city-block L1:........................................................... 56 2.4.3 Các độ đo được sử dụng trong bài tóan ................................................ 57 2.4.3.1 Độ đo tương tự giữa 2 bin màu trong hệ màu HSI ........................ 57 2.4.3.2 Độ đo dùng cho lược đồ màu......................................................... 57 2.4.3.3 Độ đo dùng cho đặc trưng liên kết màu (Color Coherence Vector) .................................................................................................................... 61 2.4.3.4 Độ đo dùng cho đặc trưng tự tương quan màu(AutoCorrelogram)61 2.4.3.5 Độ đo dùng cho đặc trưng lược đồ hệ số góc (Edge Direction Histogram) ................................................................................................. 62 2.4.3.6 Độ đo dùng cho đặc trưng liên kết hệ số góc (Edge Direction Coherence Vector) ..................................................................................... 62 Chương 3 TRUY TÌM ẢNH DỰA VÀO ĐẶC TRƯNG CẤP THẤP ................. 64 3.1. Các đặc trưng được sử dụng để truy tìm ảnh .............................................. 65 3.1.1 Đặc trưng về màu sắc............................................................................ 65 Nguyễn Bá Công – Nguyễn Hữu Đức vi Hệ thống truy tìm ảnh dựa vào đặc trưng cấp thấp và đặc trưng cấp cao 3.1.1.1 Lược đồ màu (histogram) .............................................................. 65 3.1.1.2 Vector liên kết màu (Color Coherence Vector) ............................. 65 3.1.1.3 Đặc trưng tự tương quan màu (AutoCorrelogram)........................ 66 3.1.2 Đặc trưng về hình dáng......................................................................... 67 3.1.2.1 Lược đồ hệ số góc (Edge Direction Histogram) ............................ 67 3.1.2.2 Vector liên kết hệ số góc (Edge Direction Coherence Vector)...... 67 3.2. Giải thuật phân lớp phân cấp (Hierarchical Agglomerative Clustering Algorithm- HAC) và áp dụng giải thuật trong phân lớp ảnh theo các đặc trưng của ảnh ............................................................................................................... 68 3.2.1 Tổng quan về giải thuật......................................................................... 68 3.2.2 Giải thuật............................................................................................... 68 3.2.3 Áp dụng giải thuật phân lớp phân cấp vào việc xây dựng cây phân cấp theo các đặc trưng của ảnh............................................................................. 70 3.3. Tạo chỉ mục truy tìm ảnh ............................................................................ 78 3.4. Các chiến lược truy tìm ảnh........................................................................ 79 3.4.1 Truy tìm ảnh xét đến tính phân bố toàn cục ......................................... 79 3.4.1.1 Tìm kiếm theo màu sắc .................................................................. 79 3.4.1.1.1 Lược đồ màu ........................................................................... 79 3.4.1.1.2 Vector liên kết màu................................................................. 80 3.4.1.1.3 Đặc trưng tương quan màu (Correlogram): ............................ 82 3.4.1.2 Tìm kiếm theo hình dáng ............................................................... 82 3.4.1.2.1 Lược đồ hệ số góc............