Luận văn: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 (cid:87)(cid:9)(cid:88) 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 (cid:87)(cid:9)(cid:88) 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

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

Nguyễn Bá Công – Nguyễn Hữu Đức

ảnh và video, thư viện số, ảnh vệ tinh, ảnh y học, giáo dục từ xa,…

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

Nguyễn Bá Công – Nguyễn Hữu Đức

iii

ThS.Lý Quốc Ngọc

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

....................................................................................................................................

Nguyễn Bá Công – Nguyễn Hữu Đức

Tp. Hồ Chí Minh, ngày tháng 07 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

Mục lục

Nguyễn Bá Công – Nguyễn Hữu Đứ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

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

Nguyễn Bá Công – Nguyễn Hữu Đức

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

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

Nguyễn Bá Công – Nguyễn Hữu Đức

vii

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 ................................................................... 83 3.4.1.2.2 Vector liên kết hệ số góc......................................................... 83 3.4.1.3 Tìm kiếm kết hợp........................................................................... 84 3.4.1.3.1 Tìm kiếm kết hợp các đặc trưng với nhau dùng toán tử BOOL ................................................................................................................ 85 3.4.1.3.2 Tìm kiếm kết hợp các đặc trưng với nhau dùng trọng số ....... 86 3.4.2 Truy tìm ảnh xét đến tính phân bố cục bộ (yếu tố không gian)............ 87 3.4.2.1 Tìm kiếm xét đến tính cục bộ với việc chia lưới tìm kiếm............ 87 3.4.2.2 Tìm kiếm xét đến tính cục bộ với việc vẽ...................................... 90 Chương 4 TRUY TÌM ẢNH DỰA VÀO ĐẶC TRƯNG CẤP CAO ................... 93 4.1. Bài toán phân đoạn ảnh............................................................................... 94 4.1.1 Chọn đặc trưng để phân đoạn ảnh......................................................... 94 4.1.2 Phân đoạn ảnh ....................................................................................... 96 4.1.3 Các ví dụ về bài toán phân đoạn ảnh .................................................... 98 4.2. Vùng và đặc trưng vùng.............................................................................. 99 4.3. Áp dụng giải thuật phân lớp phân cấp vào bài toán phân lớp vùng.......... 101 4.4. Tạo chỉ mục tìm kiếm ............................................................................... 105 4.5. Các chiến lược truy tìm theo đặc trưng cấp cao ....................................... 105 4.5.1 Giai đoạn nhập dữ liệu ........................................................................ 106 4.5.2 Giai đoạn truy tìm ............................................................................... 110 4.5.3 Giai đoạn sắp hạng (RANKING)........................................................ 110 Chương 5 TRUY TÌM ẢNH DỰA VÀO NGỮ NGHĨA .................................... 112

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

Nguyễn Bá Công – Nguyễn Hữu Đức

viii

Chương 6 CÀI ĐẶT VÀ THỬ NGHIỆM ........................................................... 117 6.1. Cài đặt ....................................................................................................... 118 6.1.1 Chương trình ....................................................................................... 118 6.1.2 Các đặc trưng sử dụng cho chương trình ............................................ 118 6.1.3 Cơ sở dữ liệu ....................................................................................... 119 6.1.3.1 Cơ sở dữ liệu truy tìm theo đặc trưng cấp thấp............................ 119 6.1.3.2 Cơ sở dữ liệu truy tìm theo đặc trưng cấp cao............................. 119 6.1.4 Chức năng truy tìm ảnh....................................................................... 119 6.2. Thử nghiệm ............................................................................................... 120 6.2.1 Tìm kiếm xét đến tính toàn cục........................................................... 120 6.2.1.1 Tìm kiếm theo lược đồ màu......................................................... 120 6.2.1.2 Tìm kiếm theo lược đồ hệ số góc................................................. 121 6.2.1.3 Tìm kiếm theo vector liên kết màu .............................................. 123 6.2.1.4 Tìm kiếm theo vector liên kết hệ số góc...................................... 124 6.2.1.5 Tìm kiếm theo AutoCorrelogram................................................. 125 6.2.1.6 Tìm kiếm ảnh bằng việc kết hợp các đặc trưng với nhau theo tóan tử AND..................................................................................................... 126 6.2.1.7 Tìm kiếm ảnh bằng cách kết hợp các đặc trưng dùng trọng số ... 128 6.2.2 Tìm kiếm dựa trên tính phân bố cục bộ .............................................. 129 6.2.2.1 Tìm kiếm bằng cách chia lưới...................................................... 129 6.2.2.2 Tìm kiếm bằng cách vẽ vùng....................................................... 133 6.2.3 Tìm kiếm dựa theo vùng, đối tượng của ảnh có sẵn ........................... 135 6.2.4 Tìm kiếm dựa theo vùng, đối tượng khi mà người dùng chưa có ý niệm rõ ràng về tấm ảnh........................................................................................ 141 6.2.5 Tìm kiếm dựa vào ngữ nghĩa .............................................................. 144 6.3. Kết quả thực nghiệm của hệ thống ........................................................... 145 6.3.1 Thực nghiệm việc tìm kiếm theo các đặc trưng cấp thấp ................... 146 6.3.2 Thực nghiệm việc tìm kiếm theo đặc trưng cấp cao........................... 147 Chương 7 TỔNG KẾT VÀ HƯỚNG PHÁT TRIỂN .......................................... 148 7.1. Tổng kết .................................................................................................... 149 7.2. Hướng phát triển ....................................................................................... 149 7.3. Kết luận ..................................................................................................... 149 TÀI LIỆU THAM KHẢO ................................................................................... 151

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 các hình

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 1: Mô hình của hệ thống tìm kiếm thế hệ đầu tiên ......................................... 4 Hình 2: Mô hình của hệ thống tìm kiếm thế hệ mới ................................................ 8 Hình 3: Hình gốc 1................................................................................................... 9 Hình 4: Ảnh giống lược đồ màu với ảnh gốc........................................................... 9 Hình 5: Minh họa các vùng của ảnh ........................................................................ 9 Hình 6: Minh họa các vùng của ảnh có gán ngữ nghĩa.......................................... 10 Hình 7:Mô hì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”.................................................................................................................. 12 Hình 8: minh họa 2 ảnh có lược đồ màu giống nhau 89%..................................... 14 Hình 9: minh họa 2 ảnh có vector liên kết màu giống nhau 75%.......................... 15 Hình 10:minh họa 2 ảnh có đặc trưng Correlogram giống nhau 75% ................... 15 Hình 11: minh họa 2 ảnh có lược đồ hệ số góc giống nhau 88% .......................... 16 Hình 12: minh họa 2 ảnh có Vector liên kết hệ số góc giống nhau 78%............... 17 Hình 13: Ảnh minh họa chia lưới 1x3 ................................................................... 17 Hình 14: Ảnh minh họa vẽ vùng tìm kiếm ............................................................ 18 Hình 15: Ảnh minh họa tìm kiếm theo vùng ......................................................... 19 Hình 16: Minh họa tìm kiếm theo vùng khi người dùng có một vài ý niệm về ảnh truy vấn .................................................................................................................. 19 Hình 17: Minh họa việc áp dụng mô hình học vào các vùng của ảnh để tìm kiếm theo ngữ nghĩa........................................................................................................ 20 Hình 18: Hệ màu RGB........................................................................................... 25 Hình 19: Hệ màu CMY.......................................................................................... 26 Hình 20:Hệ màu HSI.............................................................................................. 28 Hình 21: Không gian màu HSI .............................................................................. 29 Hình 22: Minh họa sự thay đổi cường độ sáng trong hệ màu HSI ........................ 29 Hình 23: Ảnh trong hệ màu RGB .......................................................................... 31 Hình 24: Ảnh trong hệ màu HSI ............................................................................ 31 Hình 25: Lược đồ màu của ảnh sau khi lượng hoá ................................................ 32 Hình 26: Ảnh trong hệ màu RGB .......................................................................... 33 Hình 27: Ảnh trong hệ màu HSI ............................................................................ 33 Hình 28: Màu đỏ thể hiện liên kết màu trong ảnh ................................................. 33 Hình 29: Lược đồ vector liên kết màu của ảnh sau khi được lượng hoá ............... 34 Hình 30: Các ví dụ về vân...................................................................................... 39 Hình 31: Decompostion để tạo ra các frequency bands bởi biến đổi Wavelet ...... 42 Hình 32: Đường bao của ảnh ................................................................................. 43 Hình 33: Gradient của ảnh theo hướng θ ............................................................... 45 Hình 34: Mô hình 8 hướng..................................................................................... 45 Hình 35: Ảnh minh họa mảnh biên........................................................................ 47 Hình 36: Ảnh sau khi dùng phương pháp Gradient phát hiện biên ....................... 47 Hình 37: Ảnh sau khi được làm mảnh biên ........................................................... 48 Hình 38: Minh họa nguyên lý Bellman.................................................................. 49

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

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 39: Ảnh minh họa lược đồ hệ số góc ............................................................ 50 Hình 40: Đường biên của ảnh ................................................................................ 50 Hình 41: Lược đồ hệ số góc của ảnh...................................................................... 50 Hình 42: Ảnh minh họa vector liên kết hệ số góc.................................................. 52 Hình 43: Ảnh minh họa sự liên kết giữa các biên cạnh ......................................... 52 Hình 44: Lược đồ vector liên kết hệ số góc của ảnh.............................................. 52 Hình 45: Minh họa vùng của ảnh........................................................................... 55 Hình 46: minh họa 2 lược đồ màu giống nhau ...................................................... 58 Hình 47: Lược đồ màu thể hiện phần giao của 2 lược đồ màu trên....................... 59 Hình 48: Hình minh họa độ đo Euclide ................................................................. 59 Hình 49: Lược đồ màu thể hiện độ khác nhau giữa 2 lược đồ màu trên ............... 60 Hình 50:Cây phân cấp cho việc phân lớp cơ sở dữ liệu ........................................ 71 Hình 51: Cơ sở dữ liệu minh họa thuật toán HAC vào việc phân lớp ảnh theo đặc trưng lược đồ màu .................................................................................................. 72 Hình 52:Cây phân cấp theo lược đồ màu............................................................... 73 Hình 53: Nhóm các ảnh có cùng đặc trưng màu.................................................... 73 Hình 54:Cơ sở dữ liệu phân lớp ảnh theo đặc trưng liên kết màu ......................... 73 Hình 55: Cây phân cấp theo đặc trưng liên kết màu.............................................. 74 Hình 56: Nhóm các ảnh có cùng đặc trưng liên kết màu....................................... 74 Hình 57: Cơ sở dữ liệu minh họa thuật toán HAC đồi với đặc trưng Correlogram ................................................................................................................................ 75 Hình 58: Cây phân cấp theo đặc trưng Correlogram ............................................ 75 Hình 59: Nhóm các ảnh có cùng đặc trưng Correlogram ...................................... 75 Hình 60: Cơ sở dữ liệu minh họa thuật toán HAC đối với đặc trưng lược đồ hệ số góc .......................................................................................................................... 76 Hình 61: Cây phân cấp theo đặc trưng lược đồ hệ số góc ..................................... 76 Hình 62: Nhóm các ảnh có cùng đặc trưng lược đồ hệ số góc .............................. 76 Hình 63: Cơ sở dữ liệu ảnh minh họa thuật toán HAC để phân lớp theo đặc trưng vector liên kết hệ số góc......................................................................................... 77 Hình 64: Cây phân cấp theo đặc trưng liên kết hệ số góc...................................... 77 Hình 65: Nhóm các ảnh có cùng đặc trưng liên kết hệ số góc............................... 77 Hình 66: Cây phân cấp ban đầu ............................................................................. 78 Hình 67: Cây chỉ mục ............................................................................................ 79 Hình 68: Minh họa 2 ảnh có lược đồ màu giống nhau .......................................... 80 Hình 69: Minh họa 2 ảnh giống nhau về lược đồ màu nhưng khác nhau về ngữ nghĩa....................................................................................................................... 80 Hình 70: Minh họa 2 ảnh có lược đồ màu giống nhau nhưng khác nhau về ngữ nghĩa....................................................................................................................... 81 Hình 71: Hình minh họa vector liên kết màu khắc phục tính không duy nhất của lược đồ màu............................................................................................................ 81 Hình 72: Hình minh họa 2 ảnh có đặc trưng tương quan màu giống nhau 81.2% 82 Hình 73: minh hoạ 2 ảnh có lược đồ hệ số góc giống nhau................................... 83 Hình 74:minh họa 2 ảnh có lược đồ hệ số góc giống nhau 80% ........................... 84

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

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 75: Hình minh họa 2 ảnh có vector liên kết hệ số góc khác nhau ................ 84 Hình 76: Hìmh minh họa 2 ảnh giống nhau về lược đồ màu và lược đồ hệ số góc85 Hình 77:Hình minh họa tìm kiếm chia lưới-1........................................................ 87 Hình 78: Minh họa ảnh được chia lưới 3x3 để tìm kiếm-1 ................................... 88 Hình 79: Hình minh họa tìm kiếm chia lưới-2....................................................... 88 Hình 80: Minh hoạ chia lưới 1x2 để tìm kiếm-2 ................................................... 89 Hình 81: Ảnh minh họa tìm kiếm chia lưới-3........................................................ 89 Hình 82: Minh hoạc chia lưới 1x3 cho việc tìm kiếm trên ảnh-3.......................... 89 Hình 83: Ảnh minh họa tìm kiếm vẽ ..................................................................... 90 Hình 84: Chia lưới 3x3 trên ảnh tìm kiếm ............................................................ 90 Hình 85: Minh họa vẽ hình trên ảnh tìm kiếm...................................................... 91 Hình 86: Hỉnh minh họa vẽ trên ảnh tìm kiếm ...................................................... 91 Hình 87: Hình minh hoa vẽ tìm kiếm .................................................................... 92 Hình 88: Hình minh họa vẽ tìm kiếm .................................................................... 92 Hình 89: Hình minh họa cây phân cấp................................................................... 97 Hình 90: Minh họa áp dụng giải thuật HAC vào phân đoạn ảnh-1 ....................... 98 Hình 91: Minh họa áp dụng giải thuật HAC vào phân đoạn ảnh-2 ....................... 99 Hình 92: Minh hoạ dùng thuật toán HAC phân đoạn ảnh-3.................................. 99 Hình 93: Minh họa vùng của ảnh......................................................................... 100 Hình 94: Cơ sở dữ liệu dùng để phân vùng ảnh .................................................. 102 Hình 95: Các vùng của tập ảnh được tách ra bằng giải thuật HAC..................... 103 Hình 96: Cây phân cấp của tập vùng trên ............................................................ 103 Hình 97: Nhóm các vùng giống nhau .................................................................. 103 Hình 98: Cơ sở dữ liệu ảnh phân vùng ................................................................ 104 Hình 99: Các vùng của tập dữ liệu ảnh sau khi được tách bằng giải thuật HAC 104 Hình 100: Cây phân cấp của tập vùng trên .......................................................... 104 Hình 101: Nhóm các vùng giống nhau ................................................................ 105 Hình 102: ảnh minh họa tìm kiếm theo vùng ...................................................... 107 Hình 103: Hình minh họa tìm kiếm theo vùng, đối tượng................................... 108 Hình 104: Câu truy vấn “Bầu trời” AND “ Cỏ” AND “ Hoa màu trắng” ........... 109 Hình 105: Câu truy vấn “Hoa màu vàng” AND NOT “ Lá màu xanh” .............. 109 Hình 106: Các vùng đã được gán nhãn................................................................ 114 Hình 107: Kết quả câu truy vấn “Hoa màu tím”.................................................. 114 Hình 108: Kết quả câu truy vấn “ Hoa mai”........................................................ 115 Hình 109: Kết quả câu truy vấn “ Cỏ” và “ Nhà”............................................... 115 hình 110: Kết quả câu truy vấn “ Sư tử” AND “ Bầu trời” ................................. 116 Hình 111: Mô hình hệ thống................................................................................ 118 Hình 112: Ảnh truy vấn theo lược đồ màu .......................................................... 120 Hình 113: Tập kết quả tìm kiếm theo lược đồ màu ............................................. 121 Hình 114: Kết quả tìm kiếm theo lược đồ màu với độ giống nhau 70% ............. 121 Hình 115:Ảnh truy vấn theo lược đồ hệ số góc ................................................... 121 Hình 116: Tập kết quả tìm kiếm theo lược đồ hệ số góc ..................................... 122 Hình 117: Tập kết quả tìm theo lược đồ hệ số góc với độ giống nhau 89% ....... 122

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

Nguyễn Bá Công – Nguyễn Hữu Đức

xii

Hình 118: Ảnh truy tìm theo đặc trưng vector liên kết màu................................ 123 Hình 119:Tập kết quả tìm theo đặc trưng vector liên kết màu ............................ 123 Hình 120: Kết quả tìm kiếm với độ giống nhau 70% .......................................... 123 Hình 121: Ảnh truy vấn theo đặc trưng vector liên kết hệ số góc ....................... 124 Hình 122: Tập kết quả tìm theo đặc trưng liên kết hệ số góc .............................. 124 Hình 123: Tập kết quả tìm theo đặc trưng liên kết hệ số góc với độ giống nhau 84% ...................................................................................................................... 125 Hình 124: Ảnh truy vấn ....................................................................................... 125 Hình 125: Tập kết quả thu được .......................................................................... 125 Hình 126: Tập kết quả tìm được với độ giống nhau 70%.................................... 126 Hình 127: Ảnh truy vấn ....................................................................................... 126 Hình 128: Tập kết quả tìm được .......................................................................... 126 Hình 129: Tập kết quả tìm được .......................................................................... 127 Hình 130: Tập kết quả tìm được .......................................................................... 127 Hình 131: Ảnh truy vấn ....................................................................................... 127 Hình 132: Tập kết quả tìm được .......................................................................... 128 Hình 133: Ảnh truy vấn ....................................................................................... 128 Hình 134: Tập kết quả tìm được .......................................................................... 128 Hình 135: Ảnh truy vấn ....................................................................................... 129 Hình 136: Tập kết quả tìm được .......................................................................... 129 Hình 137: Ảnh truy vấn tìm kiếm dựa trên tính phân bố cục bộ ......................... 129 Hình 138: Ảnh minh họa chia lưới và vùng được chọn....................................... 130 Hình 139: Tập ảnh kết quả tìm được ................................................................... 130 Hình 140: Ảnh truy vấn ....................................................................................... 130 Hình 141: Ảnh minh hoạ cá vùng đựơc chọ ........................................................ 131 Hình 142: Tập ảnh tìm được ................................................................................ 131 Hình 143: Ảnh truy vấn ....................................................................................... 131 Hình 144: Ảnh sau khi chia lưới .......................................................................... 132 Hình 145: Tập ảnh kết quả tìm được ................................................................... 132 Hình 146: Tập ảnh kết quả tìm được ................................................................... 133 Hình 147: Ảnh truy vấn ...................................................................................... 133 Hình 148: Minh họa vẽ tìm kiếm......................................................................... 134 Hình 149: Tập ảnh tìm được ................................................................................ 134 Hình 150: Tập ảnh tìm được ................................................................................ 135 Hình 151: Ảnh truy vấn theo vùng ...................................................................... 135 Hình 152: Các vùng của ảnh sau khi phân đoạn.................................................. 135 Hình 153: Tập kết quả tìm theo vùng hoa màu tím ............................................. 136 Hình 154: Các vùng của ảnh truy vấn.................................................................. 137 Hình 155: Vùng tìm kiếm .................................................................................... 137 Hình 156: Tập kết quả tìm được theo vùng sư tử ............................................... 138 Hình 157: Minh họa tìm kiếm theo toán tử BOOL.............................................. 138 Hình 158: Tập kết quả thu được .......................................................................... 139 Hình 159: Ảnh sau khi phân đoạn........................................................................ 139

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

Nguyễn Bá Công – Nguyễn Hữu Đức

xiii

Hình 160: Minh họa câu truy vấn ........................................................................ 140 Hình 161: Kết quả tìm được................................................................................. 140 Hình 162: Câu truy vấn........................................................................................ 141 Hình 163: Kết quả thực hiện câu truy vấn trên.................................................... 141 Hình 164: Hình minh họa tìm kiếm theo vùng .................................................... 142 Hình 165: Kết quả tìm được................................................................................. 142 Hình 166: Minh họa câu truy vấn theo vùng ....................................................... 143 Hình 167: Tập Kết quả tìm được ......................................................................... 143 Hình 168:Tập kết quả tìm kiếm với từ khoá” hổ con”......................................... 144 Hình 169: Ảnh minh hoạ tìm kiếm theo ngữ nghĩa, từ khoá “Chúa sơn lâm” .... 145 Hình 170: Kết quả tìm kiếm với từ khoá “ Chúa sơn lâm” với độ giống nhau 64% .............................................................................................................................. 145

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

Thuật ngữ chuyên ngành

Color coherence vector: vectơ liên kết màu

Edge direction coherence vector: vectơ liên kết hệ số góc

Edge direction histogram: lược đồ hệ số góc

Hierarchical Agglomerative Clustering Algorithm (HAC): thuật toán phân lớp

phân cấp

Histogram: lược đồ màu

Nguyễn Bá Công – Nguyễn Hữu Đức

xiv

Texture: vân

Chương 1: Tổng quan

Chương 1 Tổng quan

Nguyễn Bá Công – Nguyễn Hữu Đức

Chương 1: Tổng quan

1.1. Hướng truy tìm ảnh dựa vào nội dung

Truy tìm ảnh dựa vào nội dung là tìm kiếm thông tin trực quan. Truy tìm

thông tin trực quan là chủ đề nghiên cứu mới trong lĩnh vực công nghệ thông tin.

Tương tác với nội dung trực quan là cách thiết yếu nhất để truy tìm thông tin trực

quan. Các yếu tố trực quan như màu sắc, vân, hình dáng đối tượng và các yếu tố

không gian trực tiếp liên quan đến khía cạnh của cảm nhận nội dung ảnh, cùng với

các khái niệm ở mức cao như ý nghĩa đối tượng, khung cảnh trong ảnh, được dùng

như là manh mối cho tìm kiếm hình ảnh với nội dung tương tự từ cơ sở dữ liệu.

Truy tìm ảnh dựa vào nội dung đòi hỏi phải có sự đóng góp từ các lĩnh vực

nghiên cứu khác là rất lớn và đặt ra nhiều thử thách trong nghiên cứu đối với các

nhà khoa học và kỹ sư. Các lĩnh vực nghiên cứu khác nhau, được phát triển một

các độc lập, đóng góp rất lớn cho chủ đề nghiên cứu mới mẽ này. Truy tìm thông

tin, mô hình hóa và thể hiện dữ liệu trực quan, phân tích và xử lý phim/ảnh, nhận

dạng và thị giác máy tính (computer vision), tổ chức cơ sở dữ liệu đa phương tiện

(multimedia), lập chỉ mục đa chiều, mô hình hóa tâm lí hành vi người dùng, hệ

tương tác người-máy và trực quan hóa dữ liệu, là các lĩnh vực nghiên cứu quan

trọng nhất đóng góp cho truy tìm thông tin trực quan.

Các yếu tố mô tả nội dung có liên quan đến các đặc trưng cảm nhận như

màu sắc, vân, hình dạng, cấu trúc, mối liên hệ về không gian và chuyển động. Các

yếu tố cơ sở nguồn gốc của màu sắc như đối tượng, vai trò, sự kiện, hay các thông

tin có liên hệ với màu sắc như cảm giác, cảm tưởng hay ý nghĩa của hình ảnh. Do

vậy, phân tích ảnh, nhận dạng và thị giác máy tính đóng vai trò cơ bản trong các

hệ thống truy tìm thông tin trực quan. 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

Nguyễn Bá Công – Nguyễn Hữu Đức

nội dung trực quan.

Chương 1: Tổng quan

1.2. Hệ thống tìm kiếm ảnh thế hệ đầu tiên (dựa vào văn

bản)

Thế hệ đầu tiên của hệ thống tìm kiếm ảnh dựa vào nội dung cho phép truy

cập trực tiếp đến ảnh thông qua thuộc tính chuỗi. Kho ngữ liệu của hệ thống trong

thế hệ đầu tiên dựa trên chuỗi, sơ đồ trình bày, mô hình quan hệ, cấu trúc khung.

Dữ liệu mô tả và phụ thuộc nội dung được thể hiện thông qua từ khoá hay

nguyên bản. Từ khoá rất thích hợp cho việc xác định: Các thực thể quan trọng

trong hình ảnh (như đối tượng, con người…), các khái niệm hay thuật ngữ phụ

thuộc ngữ cảnh (như: mắt, miệng, gương mặt…) hay khung cảnh thể hiện (cảnh

bãi biển, cảnh núi non, cảnh hoàng hôn…). Nguyên bản là các mô tả bao quát hơn,

thường được viết bởi các chuyên gia, tóm tắt vào từ ngữ những gì thể hiện được và

ý nghĩa của ảnh. Truy tìm thông tin dựa trên các hệ thống tìm kiếm truyền thống

làm việc trên văn bản dùng ngôn ngữ truy vấn như SQL hay tìm kiếm toàn văn

bản.

Do hệ thống tìm kiếm này là dựa vào từ khóa được chú thích bằng văn bản

do đó có những hạn chế sau: Việc tạo từ khóa cho một số lượng lớn ảnh tốn thời

gian, từ khóa thì ngắn không thể mô tả hết các nét cảm nhận nổi bật của các đặc

trưng trực quan và không duy nhất, văn bản không thích hợp cho việc xây dựng độ

đo tương tự về giác quan, những mô tả bằng văn bản chỉ phản ánh quan điểm của

người chú thích chứ không phải người dùng cuối tương tác với hệ thống nhưng

việc nhận thức là một vấn đề chủ quan của từng người. Do những hạn chế trên đã

dẫn đến sự ra đời của hệ thống tìm kiếm ảnh dựa vào nội dung. Thế hệ mới của hệ

thống tìm kiếm ảnh dựa vào nội dung hỗ trợ đầy đủ việc lấy thông tin dựa vào nội

dung thuộc về thị giác. Chúng cho phép phân tích đối tượng, tự động rút trích đặc

trưng.

Những tìm kiếm đặc thù cho những hệ thống dạng này là “ tìm tất cả những

hình ảnh có hình con chó “ hay “ tìm kiếm tất cả những tấm ảnh về biển ở Việt

Nguyễn Bá Công – Nguyễn Hữu Đức

Nam”.

Chương 1: Tổng quan

Những khuyết điểm mà tìm kiếm theo văn bản không thực hiện được khi

người dùng muốn tìm kiếm những tấm ảnh có nội dung “ảnh có hoa màu xanh

xanh” hay “hoa màu vàng có nhụy màu tím ” việc tìm kiếm theo văn bản không

thực hiện được vì có rất nhiều loại hoa màu xanh cũng như hoa màu vàng nhụy

màu tím. Vả lại từ khóa là do quan điểm của người chú thích chứ không phải của

người dùng.

Mô hình hệ thống tìm kiếm thế hệ đầu tiên:

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 1: Mô hình của hệ thống tìm kiếm thế hệ đầu tiên

Chương 1: Tổng quan

1.3. Hệ thống tìm kiếm thông tin trực quan thế hệ mới

Hệ thống tìm kiếm thông tin trực quan thế hệ mới hỗ trợ tìm kiếm hoàn toàn

bằng nội dung trực quan. Truy cập đến thông tin không chỉ ở mức khái niệm dùng

từ khoá và văn bản, mà còn thông qua mức độ cảm nhận dùng các độ đo khách

quan của nội dung trực quan và các mô hình tương tự thích hợp. Trong các hệ

thống này thì xử lý ảnh, nhận dạng và thị giác máy tính làm một phần được tích

hợp vào kiến trúc và vận hành hệ thống. Nó cho phép phân tích khách quan sự

phân bố điểm ảnh và tự động rút trích độ đo từ dữ liệu nhập thô.

1.3.1 Các hệ thống tìm kiếm ảnh tĩnh

Nội dung của ảnh tĩnh bao gồm:

Thuộc tính cảm nhận: màu sắc, vân, hình dạng, yếu tố không

gian.

Các yếu tố nội dung cơ sở: đối tượng, quang cảnh.

Cảm giác, cảm nhận và ý nghĩa được kết hợp với tập các đặc

trưng cảm nhận.

Để tìm ảnh tương ứng với các thuộc tính cảm nhận, mô hình tìm

kiếm đòi hỏi với mỗi ảnh các đặc trưng tiêu biểu (tham số) được tính trước.

Truy vấn được thông qua các mẫu trực quan. Để khởi tạo truy vấn, người

dùng chọn các đặc trưng và phạm vi của các tham số quan trọng và chọn độ

đo tương tự. Mẫu có thể được soạn thảo bởi người dùng hay rút từ các ảnh

mẫu. Hệ thống kiểm tra độ tương tự giữa nội dung trực quan được ngừơi

dùng truy vấn và ảnh trong cơ sở dữ liệu. Vì không thể dự đoán được kết

quả trả về tương ứng với truy vấn có thoả mãn hay không nên kỹ thuật để

cải thiện chất lượng truy vấn là giữ đến mức thấp nhất có thể số thất thoát

(do chi phí của số lượng lớn hơn các truy vấn thất bại) và cho phép một

hình thức tương tác gọi là hồi đáp thích hợp (relevance feedback). Trong đó

Nguyễn Bá Công – Nguyễn Hữu Đức

các mẫu rất cứng nhắc, thiếu độ linh động cần thiết để giải quyết các khái

Chương 1: Tổng quan

niệm và yếu tố màu sắc của hình ảnh. Vì thế, để tìm kiếm ảnh dựa trên các

thuộc tính cấp cao thì phải thực hiện truy vấn lại bằng văn bản.

1.3.2 Các hệ thống tìm kiếm phim ảnh (video)

Khác với ảnh tĩnh, ảnh phim truyền các thông điệp có nhiều thông

tin hơn thông qua nhiều khía cạnh thông tin. Bao gồm cách các khung ảnh

liên kết lại với nhau sử dụng các hiệu ứng soạn thảo (cắt, giảm,phân rã,làm

mờ…) và nội dung thể hiện trong ảnh (nhân vật, nội dung câu chuyện,

thông điệp câu chuyện). Sự thay đổi về màu sắc, vân, hình dạng và chuyển

động (của cả thiết bị thu nhận ảnh, nhân vật và đối tượng) được quan sát

trong nhiều khung ảnh, là quan trọng hơn thông tin được nhúng vào các

khung ảnh đơn. Kỹ thuật dùng để thu nhận phim ảnh cũng góp phần quan

trọng vào thông tin của luồng phim ảnh. Mỗi loại phim ảnh có các đặc

trưng riêng. Điều này được thể hiện trong cách mỗi đơn vị phim ảnh được

rút trích, tổ chức trong cấu trúc kiến thức, chỉ mục và truy cập bởi người

dùng. Trong hệ thống tìm kiếm video việc truy cập có thể được thực hiện

thông qua cả mức cấu trúc lẫn nội dung.

1.3.3 Các hệ thống tìm kiếm ảnh 3 chiều và video

Tập các ảnh 3 chiều và video giờ được dùng rất nhiều trong nhiều

lĩnh vực như y học, CAD (thiết kế bộ phận máy móc), bản đồ địa lý, phân

loại ảnh nghệ thuật (điêu khắc, đối tượng 3D, mô hình…). Việc nghiên cứu

lĩnh vực tìm kiếm này chỉ mới bắt đầu.

1.3.4 Các hệ thống tìm kiếm trên Internet

Môi trừơng mạng phát triển rất nhanh trong đó việc tìm kiếm, truy

cập và truyền tải các thông tin trực quan rất quan trọng. Với các hệ thống

dựa trên web, người dùng có thể tìm kiếm hình ảnh và phim từ nhiều nguồn

Nguyễn Bá Công – Nguyễn Hữu Đức

dữ liệu khác nhau được phân tán trên mạng. Thông tin có thể thu nhận từ:

Chương 1: Tổng quan

URL (tên tập tin ảnh và chủ đề), tập tin HTML, thuộc tính ảnh (loại tập tin,

kích thước, ngày tháng)…

Nói chung, mục đích chính của truy tìm thông tin hình ảnh dựa trên

nội dung ảnh là tìm ra các ảnh tương tự với ảnh mẫu hay phác thảo ảnh

được cung cấp bởi người sử dụng. Để thực hiện điều này thông thường phải

qua các bước sau đây:

Sự biểu thị đặc điểm độc lập lĩnh vực của nội dung trực quan của

hình ảnh.

Kỹ thuật xử lí ảnh để tự động trích các đặc điểm trực quan một cách

tự động.

Tóm tắt biểu thị ngắn gọn cho các đặc điểm này.

Hàm tính độ tương tự để so sánh ảnh một cách hiệu quả.

Kỹ thuật lập chỉ mục để việc truy xuất ảnh trong cơ sở dữ liệu có

hiệu suất cao.

Khuyết điểm: Trong các hệ thống tìm kiếm thế hệ mới này các đặc

trưng tìm kiếm chủ yếu là các đặc trưng cấp thấp, dữ liệu nhận chưa mô

phỏng gần gũi với suy nghĩ của con người, ảnh tìm được có thể mang nội

dung ngữ nghĩa rất khác so với ảnh truy vấn. Điều này làm bất lợi cho

người dùng cũng như hệ thống họat động với hiệu quả không cao. Do đó,

nhu cầu đòi hỏi phải có hệ thống tìm kiếm họat động với hiệu quả cao hơn

cũng như tiện dụng hơn để đáp ứng nhu cầu ngày càng cao của con người.

Để đáp ứng nhu cầu trên, hàng lọat những hệ thống truy tìm ảnh dựa vào

nội dung mới ra đời trong đó có 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”.

Nguyễn Bá Công – Nguyễn Hữu Đức

Mô hình hệ thống tìm kiếm thế hệ mới:

Chương 1: Tổng quan

Hình 2: Mô hình của hệ thống tìm kiếm thế hệ mới

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

Nhằm đáp ứng nhu cầu ngày càng cao của con người trong tìm kiếm ảnh,

nên các hệ thống truy tìm ảnh đã không ngừng nâng cao khả năng tìm kiếm của

mình. Các hệ thống tìm kiếm theo các trưng cấp thấp đang dần được thay thế bằng

các hệ thống tìm kiếm theo đặc trưng cấp thấp kết hợp với đặc trưng cấp cao. Việc

tìm kiếm theo các đặc trưng cấp cao đã khắc phục được các khuyết điểm của việc

tìm kiếm theo các đặc trưng cấp thấp đó là: giải quyết được vấn đề lớn đang cản

trở bước phát triển truy tìm ảnh dựa vào nội dung trong việc dữ liệu nhận mô

Nguyễn Bá Công – Nguyễn Hữu Đức

phỏng gần gũi hơn với suy nghĩ của con người, và ảnh tìm được mang nội dung

Chương 1: Tổng quan

ngữ nghĩa gần hơn so với ảnh truy vấn. Bên cạnh các đặc trưng cấp cao như vùng

(hay còn gọi là vần của ảnh) được tách ra từ ảnh, việc áp dụng mô hình học vào sẽ

làm cho hệ thống tìm kiếm theo nội dung tiến thêm một bước đó là tìm kiếm dựa

vào ngữ nghĩa.

Ví dụ minh họa trong tìm kiếm: Giả sử ta có ảnh ban đầu như sau:

Hình 3: Hình gốc 1 Với việc tìm kiếm theo đặc trưng cấp thấp thì người dùng chỉ có thể

tìm kiếm những tấm ảnh có màu sắc gần giống với tấm ảnh trên như:

Hình 4: Ảnh giống lược đồ màu với ảnh gốc Điều này dẫn đến khả năng xuất hiện những ảnh tuy giống nhau về

màu sắc nhưng khác nhau về ngữ nghĩa, không hiệu quả trong tìm kiếm.

Để tránh khả năng trên xảy ra ta có thể tiến hành tìm kiếm ảnh theo

các đặc trưng cấp cao là vùng. Chúng ta có thể phân đọan ảnh thành các

vùng, và từ đó chọn các vùng cần thiết cho quá trình tìm kiếm. Điều này làm

cho kết quả tìm kiếm cao hơn và hiệu quả hơn do vùng mang ngữ nghĩa hơn

và thể hiện được tính phân bố của các thành phần trong ảnh.

Ví dụ các vùng trong ảnh sau khi phân đoạn ảnh:

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 5: Minh họa các vùng của ảnh

Chương 1: Tổng quan

Việc tìm kiếm theo đặc trưng cấp cao là vùng trong ảnh còn có thể

đưa lên một bước là tìm kiếm theo ngữ nghĩa. Từ tập ảnh cơ sơ dữ liệu ban

đầu qua bước phân đoạn ảnh và gán nhãn tự động cho ảnh ta có được những

vùng ảnh với những ngữ nghĩa xác định. Vì vậy việc tìm kiếm bây giờ chỉ là

đưa ra ngữ nghĩa của ảnh muốn tìm kiếm thông qua tập các nhãn ngữ nghĩa

đã gán ở trên dứơi dạng một câu truy vấn.

Ví dụ các vùng ảnh sau khi gán nhãn ngữ nghĩa:

Hình 6: Minh họa các vùng của ảnh có gán ngữ nghĩa

Với các nhãn được gán trên, khi chúng ta có nhu cầu tìm kiếm

những ảnh có hình con sư tử thì chúng ta chỉ cần thực hiện câu truy vấn “Sư

tử” thì kết quả trả về sẽ là những ảnh chỉ có hình con sư tử. Đây là bước

tiến nhảy vọt trong truy tìm ảnh dựa vào nội dung.

1.5. Một số hệ thống truy tìm ảnh dựa vào nội dung hiện

nay

Trong những năm gần đây, nhiều hệ thống tìm kiếm ảnh dựa vào nội dung

(content-based image retrieval: CBIR) đã được đề xuất và phát triển trong cộng

đồng nghiên cứu như:

QBIC (Query By Image Content) của IBM.

Virage của công ty Virage.

Photobook của phòng thí nghiệm truyền thông MIT.

VisualSEEK của đại học Columbia.

Nguyễn Bá Công – Nguyễn Hữu Đức

RetriecvalWare của tập đòan công nghệ Excalibur.

Chương 1: Tổng quan

Netra của Đại học California, Thư viện ảnh Alexandria.

CORE của Đại học Singapore.

Nhìn chung, các hệ thống trên đa số chỉ ở giai đọan hòan tất việc tìm kiếm

theo đặc trưng cấp thấp, còn đặc trưng cấp cao thì các hệ thống trên chỉ kết thúc

trong giai đọan tìm theo hình dáng ảnh, chưa đến giai đọan tách vùng ảnh. Do đó,

đòi hỏi phải có một hệ thống họat động với hiệu quả cao hơn, dữ liệu mô tả đầu

vào mô phỏng gần gũi với con người hơn. Để đáp ứng yêu cầu đó, một hệ thống

hệ thống “ ruy tìm ảnh dựa vào đặc trưng cấp thấp và T tìm kiếm mới ra đời

đặc trưng cấp cao”. Hệ thống này có thể giải quyết được các khuyết điểm của các

hệ thống trước kia, đồng thời tiến đến “Tìm kiếm theo ngữ nghĩa”, tạo một bước

nhảy vọt trong lĩnh vực truy tìm ảnh dựa vào nội dung.

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”

Giả sử khi có nhu cầu tìm kiếm một vài tấm ảnh trong cơ sở dữ liệu hàng

trăm ngàn ảnh, điều này có thể thực hiện được khi ta tìm kiếm bằng tay theo cách

thông thường, nghĩa là xem từng tấm ảnh cho đến khi tìm thấy ảnh cần tìm. Việc

tìm kiếm này làm tốn rất nhiều thời gian chúng ta. Do đó, nhu cầu đòi hỏi phải có

một công cụ hỗ trợ giúp cho việc tìm kiếm nhanh hơn, hiệu quả hơn. Do đó đề 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”

ra đời để đáp ứng nhu cầu trên.

Truy tìm ảnh dựa vào nội dung là tìm kiếm thông tin trực quan. Tương tác

với nội dung trực quan là cách thiết yếu nhất để truy tìm thông tin hiệu quả nhất.

Các yếu tố trực quan như màu sắc, vân (texture), hình dạng đối tượng và các yếu

tố không gian trực tiếp liên quan đến khía cạnh cảm nhận nội dung ảnh.

Do đó nội dung của đề tài sẽ được giải quyết như sau: truy tìm ảnh dựa vào

các đặc trưng như lược đồ màu (Histogram), Vector liên kết màu (Color

Coherence Vector), Correlogram, lược đồ hệ số góc (Edge Direction Histogram),

Nguyễn Bá Công – Nguyễn Hữu Đức

Vector liên kết hệ số góc (Edge Direction Coherence Vector), vân(texture), vùng.

Chương 1: Tổng quan

Tuy hệ thống này tiến dần đến “Tìm kiếm theo ngữ nghĩa” nhưng các đặc

trưng cấp thấp không thể thiếu trong quá trình xây dựng hệ thống. Việc áp dụng

mô hình học vào hệ thống cũng phải dựa vào các đặc trưng cấp thấp như lược đồ

màu, vector liên kết màu,... .Do đó, đặc trưng cấp thấp là nền tảng để xây dựng các

hệ thống cao hơn và cũng như tìm kiếm theo đặc trưng cấp thấp không bao giờ bị

lạc hậu.

Sau đây là mô hình của hệ thống:

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 7:Mô hì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”

Chương 1: Tổng quan

1.7. Hướng tiếp cận của bài toán

Các vấn đề mà đề tài tập trung giải quyết:

Xây dựng cơ sở dữ liệu ảnh.

Xây dựng hệ thống tìm kiếm ảnh:

o Tìm kiếm theo các đặc trưng cấp thấp: Lược đồ màu

(Histogram), Vector liên kết màu (Color Coherence

Vector), tương quan màu (Correlogram), Vân (Texture),

lược đồ hệ số góc (Edge Direction Histogram), Vector liên

kết hệ số góc (Edge Direction Coherence Vector).

o Tìm kiếm theo vùng, đối tượng.

o Tìm kiếm theo ngữ nghĩa.

1.7.1 Xây dựng cơ sở dữ liệu

Để tăng hiệu quả trong việc tìm kiếm cũng như mô tả trực quan hơn về

các đối tượng ảnh. Chúng em hướng tới xây dựng một cơ sở dữ liệu ảnh nhằm

đưa những ảnh có đặc điểm giống nhau về cùng một nhóm. Ở đây, mỗi đặc

trưng chúng em gom thành một cây, từ đó giúp cho việc tìm kiếm các đối

tượng ảnh một cách dễ dàng, cũng như việc thể hiện chúng sinh động hơn, giúp

người dùng có thể hình dung được tập dữ liệu ảnh của mình. Thuật tóan được

chúng em sử dụng để xây cây là “Thuật tóan phân lớp phân cấp

Hierarchical Agglomerative Clustering Algorithm- HAC . )” (

Chúng em chọn “Thuật tóan phân lớp phân cấp” này cho bài tóan mà

không chọn các thuật tóan khác vì nó có một số ưu điểm sau:

Không cần xác định trước số phân lớp nên ta có thể phân lớp

từ thô cho đến mịn.

Dễ cài đặt.

Nguyễn Bá Công – Nguyễn Hữu Đức

Tốc độ nhanh.

Chương 1: Tổng quan

1.7.2 Xây dựng hệ thống tìm kiếm

1.7.2.1 Tìm kiếm dựa vào sự phân bố mang tính tòan cục

Khi người dùng có nhu cầu tìm kiếm những tấm ảnh có sự giống

nhau về đặc trưng nào đó trong tòan tấm ảnh so với ảnh truy vấn thì người

dùng có thể chọn chức năng tìm kiếm dựa vào sự phân bố tòan cục. Đây

cũng là nền tảng cho các tìm kiếm cấp cao hơn về sau.

1.7.2.1.1 Đặc trưng lược đồ màu

Màu sắc là thông tin gần gũi, trực quan với con người nhất.

Qua đặc trưng màu sắc, có thể lọc được rất nhiều lớp ảnh thông qua

vị trí, không gian, định lượng của màu trong ảnh.

Ví dụ hai ảnh có lược đồ màu giống nhau:

Hình 8: minh họa 2 ảnh có lược đồ màu giống nhau 89%

1.7.2.1.2 Đặc trưng vector liên kết màu (Color Coherence

Vector)

Cũng như đặc trưng lược đồ màu, đặc trưng vector liên kết

màu là thông tin quan trọng trong ảnh. Nó thể hiện rõ ràng mật độ

Nguyễn Bá Công – Nguyễn Hữu Đức

phân bố màu trong ảnh. Với 2 ảnh có thể rất giống nhau về lược đồ

Chương 1: Tổng quan

màu nhưng do khác nhau về sự phân bố màu sắc, nên trong quá trình

tìm kiếm theo lược đồ màu có thể cho ra nhiều ảnh “dư thừa”, khác

nhau về ngữ nghĩa. Nếu trong quá trình tìm kiếm trên ta sử dụng

vector liên kết màu thì sẽ khắc phục được tình trạng trên.

Ví dụ hai ảnh có lược đồ vector liên kết màu giốn nhau:

Hình 9: minh họa 2 ảnh có vector liên kết màu giống nhau 75%

1.7.2.1.3 Đặc trưng tự tương quan màu (AutoCorrelogram) Đây cũng là đặc trưng cấp cao của ảnh. Nó thể hiện tính phân

bố cục bộ về màu. Cũng giống như đặc trưng vector liên kết màu,

đặc trưng này giúp ta có thể phân biệt được những ảnh có thể rất

giống nhau về lược đồ màu khác nhau về ngữ nghĩa.

Ví dụ hai ảnh có đặc trưng correlogram giống nhau:

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 10:minh họa 2 ảnh có đặc trưng Correlogram giống nhau 75%

Chương 1: Tổng quan

1.7.2.1.4 Đặc trưng lược đồ hệ số góc (Edge Direction

Histogram)

Đây là cũng đặc trưng quan trọng của ảnh. Nó thể hiện về

hình dáng của ảnh. Đối với các ảnh muốn tìm kiếm theo hình dáng

thì đặc trưng về màu sắc không thể giải quyết được. Vì vậy trong các

hệ tìm kiếm dựa vào nội dung của ảnh không thể thiếu đặc trưng

này.

Ví dụ hai ảnh có đặc trưng lược đồ hệ số góc giống nhau:

Hình 11: minh họa 2 ảnh có lược đồ hệ số góc giống nhau 88%

1.7.2.1.5 Đặc trưng Vector liên kết hệ số góc (Edge

Direction Coherence Vector)

Cũng như đặc trưng lược đồ hệ số góc, đặc trưng vector liên

kết hệ số góc là đặc trưng cấp cao của ảnh. Nó thể hiện rõ ràng hơn

về hình dáng của ảnh. Ngòai ra nó còn thể hiện mối liên kết chặt chẽ

giữa các điểm biên cạnh (các điểm biên cạnh có cùng góc độ), cũng

Nguyễn Bá Công – Nguyễn Hữu Đức

như là những điểm không phải là biên cạnh.

Chương 1: Tổng quan

Ví dụ hai ảnh có lược đồ vector liên kết hệ số góc giống nhau:

Hình 12: minh họa 2 ảnh có Vector liên kết hệ số góc giống nhau 78%

1.7.2.2 Tìm kiếm dựa vào sự phân bố mang tính cục bộ

Khi người dùng có nhu cầu tìm kiếm một vùng nào đó trong ảnh,

thì việc tìm kiếm mang tính tòan cục không giải quyết được vấn đề trên.

Chính vì vậy chúng em đã giải quyết vấn để này bằng việc cho người

dùng chia lưới hoặc có thể vẽ một vùng nào đó trong ảnh mà họ muốn tìm

kiếm. Vì vậy với cách tìm kiếm này sẽ giúp cho hệ thống họat động hiệu

quả hơn.

Minh họa việc chia lưới tìm kiếm:

Khi người dùng muốn tìm kiếm những tấm ảnh dạng “cảnh

thành phố lúc hòan hôn” thì người dùng có thể chia lưới như sau:

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 13: Ảnh minh họa chia lưới 1x3

Chương 1: Tổng quan

Trong đó block 0 tìm theo luợc đồ màu, còn block 1, 2 tìm

kiếm theo lược đồ hệ số góc.

Minh họa việc vẽ vùng để tìm kiếm:

Khi người dùng muố tìm kiếm những ảnh có bông hoa ở

giữa thì có thể vẽ như sau:

Hình 14: Ảnh minh họa vẽ vùng tìm kiếm

1.7.2.3 Tìm kiếm theo vùng, đối tượng

Đây là bứơc tiến nhảy vọt trong việc truy tìm ảnh dựa vào nội

dung. Vùng là đặc trưng cấp cao của ảnh. Với đặc trưng về vùng, chúng ta

có thể thực hiện được các ý tưởng sau:

Với vùng, sẽ làm cho dữ liệu đầu vào được mô phỏng gần gũi

với chúng ta hơn.

Với vùng, sẽ giúp cho chúng ta có thể tiến thêm một bước

trong vấn đề tìm kiếm ảnh dựa vào nội dung là “Tìm kiếm theo

ngữ nghĩa” bằng việc áp dụng mô hình học vào vùng.

Ở đây việc tìm kiếm theo vùng đối tượng có thể chia ra làm hai

chiến lược:

Tìm kiếm theo vùng, đối tựơng từ ảnh có sẵn: Từ ảnh truy vấn

Nguyễn Bá Công – Nguyễn Hữu Đức

có sẵn ban đầu qua bước phân đọan ảnh, ta có thể chia ảnh

Chương 1: Tổng quan

thành các vùng gọi là vần của ảnh. Từ các vần này ta có thể

chọn ra vài vần cần truy tìm. Và hệ thống có thể tìm ra được

những ảnh phù hợp theo ý muốn của người dùng.

Ví dụ minh họa chia vùng ảnh có sẵn để tìm kiếm:

Hình 15: Ảnh minh họa tìm kiếm theo vùng

Tìm kiếm khi người dùng chưa có ý niệm rõ lắm về tấm ảnh

cần tìm, mà chỉ có một số yêu cầu nào đó về các “vần” cấu

thành nên nó hoặc họ chỉ cần tìm các ảnh tương tự với các vần

chính của ảnh truy vấn chứ không cần sự tương tự toàn cục.

Ví dụ minh họa:

Khi người dùng có ý niệm tìm kiếm những tấm ảnh

như sau: “Cỏ non xanh tận chân trời, cành lê trắng điểm một

vài bông hoa”. Người dùng có thể ghép các vùng lại với nhau

từ tập dữ liệu có sẵn như sau:

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 16: Minh họa tìm kiếm theo vùng khi người dùng có một vài ý niệm về ảnh truy vấn

Chương 1: Tổng quan

1.7.2.4 Tìm kiếm theo ngữ nghĩa

Với việc áp dụng mô hình học vào bài tóan phân vùng ảnh, khi đó

mỗi vùng (vần) trong ảnh có thể mang một ngữ nghĩa nào đó. Điều này

dẫn đến một khả năng truy tìm mới là dựa vào câu truy vấn dạng ngôn

ngữ, liên kết với các vùng đại diện theo một luận lý để truy tìm ảnh. Điều

này giúp cho người dùng có thể thực hiện câu truy vấn dễ dàng.

Ví dụ minh họa tìm kiếm theo ngữ nghĩa:

Hình 17: Minh họa việc áp dụng mô hình học vào các vùng của ảnh để tìm kiếm theo ngữ nghĩa

Với các nhãn ngữ nghĩa trên, khi người dùng muốn tìm kiếm

hoa mai vàng, người dùng chỉ việc đánh từ khóa “hoa mai vàng” để

Nguyễn Bá Công – Nguyễn Hữu Đức

tìm kiếm.

Chương 2: Các khái niệm cơ bản

Chương 2 CÁC KHÁI NIỆM CƠ BẢN

Nguyễn Bá Công – Nguyễn Hữu Đức

Chương 2: Các khái niệm cơ bản

2.1. Màu sắc

2.1.1 Khái niệm về màu sắc

Sự nhận thức về màu sắc là rất quan trọng trong đời sống của con người.

Sự nhận thức về màu sắc phụ thuộc vào cả tính chất vật lý của ánh sáng và quá

trình xử lý của thị giác với sự góp phần rất quan trọng của kinh nghiệm. Con

người có thể dùng thông tin màu sắc để phân biệt đối tượng, vật liệu, đồ ăn, vị

trí, và ngay cả thời gian của ngày, ...

2.1.2 Một số đặc tính vật lý đặc biệt về màu sắc

Con người chỉ có khả năng nhận thức được ánh sáng có bức xạ điện từ

với bước sóng trong khoảng 400 – 700 nanomet. Cơ quan thị giác cảm nhận

được ánh sáng là do bề mặt đối tượng phát ra ánh sáng, là kết quả của sự tương

tác giữa năng lượng chiếu sáng và những phân tử của bề mặt đối tượng. Một

đối tượng màu xanh dương sẽ có bề mặt màu xanh dương khi chiếu ánh sáng

trắng vào. Nhưng đối tượng đó sẽ có màu tím khi chiếu ánh sáng đỏ vào.Với sự

phát triển mạnh mẽ của các thiết bị kinh tế, máy móc xử lý màu sắc trở nên

thông dụng: Chúng ta có các thiết bị như máy quay phim màu, thiết bị chiếu

màu và những phần mềm xử lý ảnh màu. Máy móc có thể dùng màu sắc cho

những mục đích như là con người. Đặc biệt, màu sắc thuận tiện bởi vì nó cung

cấp phép đo lường đa dạng tại mỗi điểm ảnh đơn, có thể phân lớp, phân loại

mà không cần đến những sự xử lý không gian phức tạp để đưa đến quyết định.

Do đó, việc lựa chọn mô hình màu thích hợp và sử dụng lược đồ lượng hoá

màu thích hợp sẽ giảm bớt độ phân giải màu. Đây là các vấn đề quan trọng

trong việc tìm kiếm ảnh dựa trên màu sắc. Màu sắc thường được biểu diễn như

là các điểm trong không gian màu 3 chiều. Hiện tại có rất nhiều mô hình màu

hình học hỗ trợ việc thể hiện màu sắc một cách rõ ràng, dễ lượng hoá .Mô hình

Nguyễn Bá Công – Nguyễn Hữu Đức

màu có thể khác biệt:

Chương 2: Các khái niệm cơ bản

(cid:153) Mô hình dựa trên thiết bị đo màu: Kết quả từ độ đo vật lý hệ số

phản xạ quang phổ sử dụng thiết bị đo màu. Các không gian màu

chuẩn theo CIE (Comission International d’Eclairage) thuộc loại

này.

(cid:153) Mô hình màu dựa trên cảm nhận sinh lí: Kết quả từ các nghiên

cứu về thần kinh. Tồn tại 3 kiểu hình nón phân biệt trong võng

mạc của con người đóng vai trò vào việc sắp xếp màu sắc trong

không gian màu. Các mô hình màu CIE XYZ, RGB và các biến

thể thuộc nhóm này.

(cid:153) Mô hình màu dựa trên tâm lý học: dựa trên cách mà màu sắc hình

thành trong đầu của người quan sát. Các mô hình đối lập dựa trên

các phân tích thực nghiệm phản ứng của con người đối với các

thành phần đối lập cơ sở. Họ các không gian màu HSB (Hue-

Saturation-Brightness) thuộc lớp này.

(cid:153) Mô hình màu có thể phân biệt

o Mô hình hướng thiết bị: Định nghĩa theo thuộc tính của

thiết bị dùng để hiển thì màu như màn hình TiVi, màn hình

máy tính và máy in. Các mô hình màu hướng thiết bị là

RGB, CMY, YIQ. Người dùng rất khó xử lý trên các mô

hình này vì nó không phản ánh trực tiếp các khái niệm trực

giác màu sắc, sắc thái (còn gọi là sắc độ, là độ đậm nhạt

của màu sắc) và cường độ sáng.

o Mô hình hướng ngừơi dùng: Dựa trên khả năng cảm nhận

màu sắc của con người. Con người cảm nhận màu sắc

thông qua các đối tượng trực giác màu sắc, sắc thái và

cường độ sáng. Các mô hình màu hướng ngừơi dùng là

Nguyễn Bá Công – Nguyễn Hữu Đức

HSL, HSV, HCV, HSB, MTM, L*u*v, L*a*b* và L*C*h .

Chương 2: Các khái niệm cơ bản

Không gian màu là một cách biểu diễn toán học một tập các màu.

Các không gian màu có thể được phân vào 2 loại không gian màu:

phụ thuộc thiết bị hay độc lập thiết bị.

o Không gian màu độc lập thiết bị được chia thành nhiều

không gian màu được định theo chuẩn CIE như: XYZ,

L*a*b và L*u*v, ứng dụng chính cho mục đích đo màu .

o Không gian màu phụ thuộc thiết bị được chia vào 3 lớp

rộng: không gian màu in, không gian màu video, và không

gian màu màn hình. Các không gian màu in CMY, CMYK

dựa trên màu mực được dùng trong ngành in và nhiếp ảnh.

Các không gian màu màn hình là các biến thể của không

gian màu RGB, các không gian màu video - tất cả đều

tương tự như không gian màu YUV được phân thành các

không gian màu riêng tuỳ vào ứng dụng.

2.1.3 Các hệ màu thông dụng

2.1.3.1 Hệ màu chuẩn RGB:

Mắt người có thể phân biệt hàng ngàn màu sắc khác nhau, những

con số chính xác hơn vẫn còn đang được bàn cãi nhiều. Ba màu RGB (Red-Green- Blue) mã hóa hệ thống đồ họa sử dụng ba byte 224 hay

khoảng chừng 16 triệu màu phân biệt. Máy tính có thể phân biệt bất kỳ

màu gì sau khi được mã hóa, nhưng việc mã hóa có thể không trình bày

được những sự khác biệt trong thế giới thực. Mỗi điểm ảnh RGB bao gồm

một byte cho màu R, một byte cho màu G và một byte cho màu B. Việc

mã hóa một màu tùy ý trong dãy hiển thị được làm bằng cách tổ hợp ba

màu chính. Ví dụ: Red(255,0,0), Green(0,255,0), Blue(0,0,255),

Black(0,0,0) Hệ thống màu RGB là một hệ thống màu cộng vào bởi vì

mỗi màu được tạo nên bằng cách cộng thêm các phần tử vào màu

Nguyễn Bá Công – Nguyễn Hữu Đức

đen(0,0,0) Khuôn dạng của không gian màu RGB là định dạng phổ biến

Chương 2: Các khái niệm cơ bản

nhất của ảnh số, lý do chính là tính tương thích với màn hình hiển thị

chính là màn hình vi tính. Tuy nhiên không gian màu RGB có hạn chế lớn

nhất là không phù hợp với cách con người cảm nhận về màu sắc. Do đó

không phù hợp cho việc ứng dụng vào tìm kiếm ảnh.

Hình 18: Hệ màu RGB

2.1.3.2 Hệ màu CMY

Không gian màu CMY được dùng trong in ấn. Màu lục lam, màu

đỏ tươi và màu vàng là phần bù của màu đỏ, màu xanh lá cây và màu xanh

dương được gọi là các thành phần cơ sở trừ vì chúng được tạo ra bằng

cách trừ đi độ sáng từ màu trắng. Ví dụ màu lục lam là phần bù của màu

đỏ, tạo ra bằng cách xoá thành phần đỏ từ màu trắng. Có thể chuyển từ

không gian màu RGB sang không gian màu CMY bằng công thức chuyển

đổi đơn giản nhưng không chính xác: C=1-R, M=1-G, Y=1-B. Hệ thống

Nguyễn Bá Công – Nguyễn Hữu Đức

màu CMY dường như là một sự đảo ngược của hệ thống màu RGB. Đặc

Chương 2: Các khái niệm cơ bản

tính của nó là sự đơn giản, ứng dụng nhiều trong thực tế. Tuy nhiên

khuyết điểm của nó cũng tương tự như không gian màu RGB, tức là cách

mã hóa khác với cách mà con người cảm nhận về màu sắc. Không thích

hợp cho bài toán tìm kiếm ảnh dựa vào nội dung.

Hình 19: Hệ màu CMY

2.1.3.3 Hệ màu YIQ

Về cơ bản mô hình màu YIQ là sự biến thể hệ màu RGB bằng cách

chuyển đổi hiệu quả và duy trì sự tương thích với TV đơn sắc chuẩn. Thật

sự, thành phần Y của mô hình màu YIQ cung cấp tất cả các thông tin

video yêu cầu bởi một tập các TV đơn sắc. Công thức chuyển đổi từ RGB

299.0 596.0

275.0

587.0 −

114.0 −

212.0

532.0

−

⎤ ⎥ ⎥ ⎥ ⎦

R ⎡ ⎢ G ⎢ ⎢ ⎣

⎤ ⎥ 321.0 ⎥ ⎥ 311.0 ⎦

⎡ ⎢ ⎢ ⎢ ⎣

⎤ ⎥ ⎥ ⎥ ⎦

Y ⎡ ⎢ I ⎢ ⎢ Q ⎣

sang YIQ:

Để lấy được các giá trị RGB từ tập YIQ, chúng ta chỉ cần thực hiện

toán tử đảo ma trận .Hệ màu YIQ được thiết kế giúp cho sự cảm nhận của

con người về sự thay đổi độ sáng chói tốt hơn sự thay đổi đặc trưng màu

Nguyễn Bá Công – Nguyễn Hữu Đức

sắc (Hue) và độ thuần khiết (Sataration). Lợi thế của YIQ trong việc xử lý

Chương 2: Các khái niệm cơ bản

ảnh là độ sáng chói (Y) và thông tin màu (I và Q) được tách riêng ra. Sự

quan trọng của việc tách riêng này giúp cho việc xử lý thành phần Y của

ảnh có thể không có ảnh hưởng đến nội dung màu.

Không gian màu này đều gây khó khăn cho người sử dụng vì nó

không phản ánh trực tiếp khái niệm giác quan của màu sắc: màu, sắc thái

và độ sáng.

2.1.3.4 Hệ màu Lab:

Mô hình L*a*b được đề cử bởi CIE cho việc lượng hóa sự khác biệt

của màu sắc trong vật chiếu sáng của ánh sáng ban ngày. Tuy nhiên nó có

một sự chuyển đổi được ghi vào để mà tính toán cho việc thích nghi với

những nguồn sáng. Một màu được xác bằng 2 toạ độ x và y. Độ sáng L*

dựa trên độ đo giác quan của thành phần sáng u*, v* là toạ độ màu. Các

màu khác nhau theo một hướng duy nhất là xấp xỉ bằng nhau trong không

gian màu này. Do đó khoảng cách Euclician được dùng để quyết định

khoảng cách tương đối giữa 2 màu. Tuy nhiên, việc chuyển sang không

gian màu RGB là không tuyến tính. Đây là hệ thống màu có sự tách riêng

ánh sáng và màu sắc ra riêng. Do đó, cũng có khả năng lớn cho việc tìm

kiếm dựa vào nội dung.

2.1.3.5 Hệ màu HSI: Hue-Saturation-Intensity

Hệ thống màu HSI mã hóa thông tin màu sắc bằng cách chia giá trị

intensity I từ hai giá trị được mã hóa thuộc về độ hội tụ của màu- hue H và

saturation S. Thành phần không gian màu HSI gồm có ba phần: Hue được

định nghĩa có giá trị 0-2Π, mang thông tin về màu sắc. Saturation có giá

trị 0-1, mang giá trị về độ thuần khiết của thành phần Hue. Intensity

(Value) mang thông tin về độ sáng của điểm ảnh.Ta có thể hình dung

không gian màu HSI như là vật hình nón. Với trục chính biểu thị cường

Nguyễn Bá Công – Nguyễn Hữu Đức

độ sáng Intensity. Khoảng cách đến trục biểu thị độc tập trung Saturation.

Chương 2: Các khái niệm cơ bản

Góc xung quanh trục biểu thị cho sắc màu Hue. Đôi khi, hệ thống màu

HSI được coi như là hệ thống màu HSV dùng Value thay vì Intensity. Hệ

thống màu HSI thì thích hợp hơn với một số thiết kế đồ họa bởi vì nó

cung cấp sự điều khiển trực tiếp đến ánh sáng và hue. Hệ thống màu HSI

cũng hỗ trợ tốt hơn cho những thuật toán xử lý ảnh vì sự tiêu chuẩn hóa về

ánh sáng và tập chung vào hai tham số về độ hội tụ màu, và cường độ

màu. Hệ thống màu HSI có sự phân chia rõ rệt giữa ánh sáng và màu sắc.

Do đó có khả năng rất lớn được áp dụng cho việc tính đặc trưng và so

sánh sự giống nhau về màu sắc của hai ảnh. Do đó nó rất thích hợp cho

việc tìm kiếm ảnh dựa vào màu. Sự giống và khác nhau giữa hai ảnh về

mặt màu sắc đối với mắt người chỉ mang ý nghĩa tương đối. Do đó khi áp

dụng vào bài toán này trên máy tính thì ta cũng giả lập sự tương đối này.

Phương pháp chính của việc tìm kiếm theo màu sắc là dùng lược đồ màu

để làm đặc trưng cho từng ảnh. Do những đặc điểm riêng của mô hình

màu HSI và đặc trưng của việc tìm kiếm nên tính lược đồ màu cũng được

dùng một mô mình rất đặc biệt để phù hợp cho những đặc điểm riêng này.

Hình minh hoạ màu trong không gian màu HSI:

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 20:Hệ màu HSI

Chương 2: Các khái niệm cơ bản

Công thức chuyển đổi từ không gian màu RGB sang HSI:

Cho RGB c1(r, g, b) và HSI c2(h, s, i). Ta có:

, bgr ),

−

i = max(r, g, b),

min( i

Đặt

i − min(

r , bgr ),

i − min(

g , bgr ),

bi − min( , bgr ),

−

khi

max(

, gvàbgr ),

min(

, bgr ),

khi

max(

, gvàbgr ),

min(

, bgr ),

−

≠

gkhi

max(

, bvàbgr ),

min(

, bgr ),

gkhi

max(

, bvàbgr ),

min(

, bgr ),

−

≠

bkhi

max(

, rvàbgr ),

min(

, bgr ),

khác

−

5 ⎧ ⎪ 1 ⎪ ⎪⎪ 1 ⎨ 3 ⎪ ⎪ 3 ⎪ ⎪ 5 ⎩

Minh hoạ thành phần cường độ sáng i thay đổi:

Hình 21: Không gian màu HSI

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 22: Minh họa sự thay đổi cường độ sáng trong hệ màu HSI

Chương 2: Các khái niệm cơ bản

Với các đặc tính trên, mô hình màu HSI có các ưu điểm sau:

o Dễ cảm nhận, phù hợp với cảm nhận mắt người.

o Dễ định lượng, tách bạch thành phần màu và độ sáng.

Với 2 ưu điểm trên, mô hình màu rất thích hợp cho bài tóan truy tìm

ảnh. Do đó, chúng em chọn mô hình màu HSI cho bài tóan truy tìm ảnh dựa

vào đặc trưng màu sắc.

2.1.4 Các đặc trưng về màu sắc

2.1.4.1 Lược đồ màu (Histogram)

Là đại lượng đặc trưng cho phân bố màu cục bộ của ảnh .

)

(

)

CIH D

CIm ( D ( In )

Được định lượng:

Ci là màu của điểm ảnh.

n(ID).Tổng số điểm ảnh trong ảnh.

m(ID,Ci)thể hiện số điểm ảnh có giá trị màu Ci.

H: lược đồ màu của ảnh.

Mặc dù lược đồ màu cần tính là rất lớn (224 màu), tuy nhiên do mức

độ cảm nhận của mắt con người còn hạn chế nên thật sự chúng ta không

thể phân biệt được một lượng màu lớn như vậy. Do đó chúng em đề nghị

sử dụng hệ màu HSI (12 H, 3 S, 3 I) và thêm 5 mức xám. Vì vậy chúng ta có 113 màu đại diện cho 224 màu trong việc tìm kiếm.

Lược đồ màu bất biến đối với phép quay và tịnh tiến ảnh, và nếu

chuẩn hoá lược đồ màu sẽ bất biến đối với phép co giãn .

Độ đo tính tương tự về màu sắc giữa lược đồ màu của ảnh truy vấn

Nguyễn Bá Công – Nguyễn Hữu Đức

H(IQ)và lược đồ màu của ảnh trong cơ sở dữ liệu ảnh H(ID):

Chương 2: Các khái niệm cơ bản

min(

( IH

), IHj (

))

)

∑ ==

( ID H

( IH

)

∑

Công thức trên cho ta thấy, tính tương tự về màu sắc được tính

bằng phần giao của 2 lược đồ màu ảnh truy vấn H(IQ) và ảnh trong cơ sở

dữ liệu ảnh H(ID). Kết quả sẽ là một lược đồ màu thể hiện độ giống nhau

giữa 2 ảnh trên.

Tuy nhiên vì lược đồ màu chỉ thể hiện tính phân bố màu toàn cục

của ảnh mà không xét đến tính phân bố cục bộ của điểm ảnh nên có thể có

2 ảnh trông rất khác nhau nhưng lại có cùng lược đồ màu. Để khắc phục

được tình trạng này, chúng ta dùng phân hoạch lưới ô vuông trên ảnh.

Lược đồ màu của ảnh là không duy nhất.

Ví dụ minh hoạ ảnh trong hệ màu RGB và HSI:

Hình 23: Ảnh trong hệ màu RGB

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 24: Ảnh trong hệ màu HSI

Chương 2: Các khái niệm cơ bản

Hình 25: Lược đồ màu của ảnh sau khi lượng hoá

2.1.4.2 Vector liên kết màu (Color Coherence Vector)

Là lược đồ tinh chế lược đồ màu, chia mỗi ô màu (bin) thành 2

nhóm điểm ảnh: Nhóm liên kết màu (coherence pixels) và nhóm không

liên kết màu (non-coherence pixels)

Một pixel trong 1 ô màu (bin) được gọi là điểm liên kết màu

(coherent) nếu nó thuộc vùng gồm các màu tương tự với kích thướt lớn

(thường bằng khoảng 1%b kích thướt ảnh)

Với mỗi ô màu (bin) giả sử số điểm liên kết màu là α và số điểm

không liên kết màu là β thì vector liên kết màu được xác định:

Vc=[(α1,β1), (α2,β2), …,(αn,βn)], n là số ô màu (bin)

Độ đo tính tương tự giữa 2 ảnh dựa trên đặc trưng vector liên kết

)

−

( ID c

αα − D

β Q

β D

∑

Nhận xét:

màu:

Ngoài việc sử dụng đặc trưng liên kết màu cho việc tìm kiếm

ảnh, đặc trưng này còn có thể được sử dụng cho việc phân biệt cảnh

thiên nhiên và cảnh thành phố:

Ảnh thiên nhiên (núi, cảnh thiên nhiên, hoàng hôn)có khuynh

hướnh có số điểm liên kết màu nhiều hơn số điểm không liên kết

Nguyễn Bá Công – Nguyễn Hữu Đức

màu .Còn cảnh thành phố có khuynh hướng có số điểm liên kết màu

Chương 2: Các khái niệm cơ bản

và số điểm không liên kết màu gần như nhau. Vì vậy có thể dùng

vector liên kết màu làm đặc trưng phân biệt cảnh thiên nhiên và cảnh

thành phố.

Chỉ dùng đặc trưng lược đồ màu khó phân biệt ảnh thiên

nhiên và ảnh thành phố.

Ngòai ra vector liên kết màu còn giúp giải quyết khuyết điểm

về tính không duy nhất của lược đồ màu đối với ảnh. Hai ảnh có thể

có chung lược đồ màu nhưng khác nhau hòan tòan, đây là khuyết

điểm của lược đồ màu. Nhưng với tìm kiếm theo đặc trưng vector

liên kết màu thì nó sẽ giải quyết được khuyết điểm không duy nhất

này.

Ví dụ minh hoạ các điểm liên kết màu trong ảnh:

Hình 26: Ảnh trong hệ màu RGB

Hình 27: Ảnh trong hệ màu HSI

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 28: Màu đỏ thể hiện liên kết màu trong ảnh

Chương 2: Các khái niệm cơ bản

Hình 29: Lược đồ vector liên kết màu của ảnh sau khi được lượng hoá

cos

sin

−

)

(

)

( S

)

] 2/12

[ (

Công thức thể hiện 2 màu giống nhau:

Sau khi tính được akl thì chọn ngưỡng nào đó thoả 2 màu liên kết

nhau.

2.1.4.3 Đặc trưng tự tương quan màu (AutoCorrelogram)

Đặc trưng tương quan màu biểu diễn sự thay đổi mối quan hệ về

không gian giữa các cặp màu theo khoảng cách. Lược đồ màu chỉ ghi

nhận được sự phân bố màu trong ảnh mà không chứa các thông tin mối

quan hệ về khoảng cách.

Ký kiệu:

Gọi I là một ảnh có kích thước n x n. Các màu trong I được

x y ( ,

)

rút gọn vào m khoảng (bin) c1, …cm.

∈ , gọi I(p) là màu của pixel p.

p I p | (

)

Với mỗi pixel

{

} c

p I I p

, (

)

∈

I∈ tương đương với

c =

Đặt

Khi đó, ký hiệu

Để thống nhất, ta sử dụng quy tắc L∞ để đo khoảng cách giữa

Nguyễn Bá Công – Nguyễn Hữu Đức

các pixel. Ví dụ, với các pixel p1=(x1,y1), p2=(x2,y2) thì

Chương 2: Các khái niệm cơ bản

|p1-p2|=max{|x1-x2|,|y1-y2|}.

Quy ước {1,2,…n} = [n].

Định nghĩa:

[ i m∈

]

= ⋅

h n c i

⎡ p I ∈⎣ c i

⎤ ⎦(1)

2 Pr p I ∈

( ) /

là: Lược đồ màu h của I với mỗi

ich I

trong đó với mỗi pixel trong ảnh, là xác suất xuất

i của pixel.

hiện màu c

[ ] n∈

. Khi đó, Correlogram của I Chọn một khoảng cách

∈

−

) ( ) I

p 2

I p p c 2 1

( k γ c c , i

⎡ ⎣

⎤ ⎦ ,

Pr p I p I , ∈ ∈ ci 2 1

, ∀ ∈

∈

được định nghĩa như sau:

[ j m k

]

[

]

)

(2)

c cγ là xác suất tìm thấy một

( k ,i

Với mỗi pixel có màu ci trong ảnh,

pixel có màu cj cách pixel ban đầu một khoảng cách là k. Kích thước của Correlogram là O(m2d).

Khi chọn d để tính Correlogram, chúng ta cần chú ý vấn đề sau:

giá trị d lớn thì cần nhiều chi phí tính toán và không gian lưu trữ, giá trị d

nhỏ có thể làm giảm giá trị của đặc trưng.

Tiếp theo là một số thuật toán tính Correlogram. Các thuật toán

này có thể chia nhỏ để tính toán song song nên có thể tăng tốc tính toán

rất nhiều.

∈

−

) ( ) I

p 1

p 2

Để tính được Correlogram, điều kiện cần là phải tính được:

( k Γ c c , i

I p , c 2 i

{

} k

Nguyễn Bá Công – Nguyễn Hữu Đức

(4)

Chương 2: Các khái niệm cơ bản

I ( )

( ) 8 k ⋅

) ( k γ c c , i

( k =Γ c c , i

h I c i

) ( ) ( I

với . Mẫu số là tổng số số

)

pixel cách pixel có màu ci một khoảng cách là k (hệ số 8k là do tính

chất của L∞ ).

Thuật toán này có ý tưởng chính như sau: với mỗi p1∈I của

màu ci và với mỗi k∈ [d], tính tổng số các p2∈I của màu cj với |p1- p2|L∞=k. Thuật toán này có độ phức tạp O(n2d2).

i y ,

| 0

∈

i ≤ ≤

)

, c h λ ( , x y

Để giảm chi phí tính toán, ta định nghĩa các đại lượng sau:

x y ,

| 0

i ≤ ≤

)

) i + ∈

{ ( { (

} }

, c v λ ( , x y

) ( ) (

(5,6)

Đại lượng này đếm số pixel có màu c cách pixel gốc (x,y) một

khoảng nhỏ hơn k theo chiều ngang (horizontal, hay chiều dọc

(vertical).

c h , x yλ và ( ) ,

c v , x yλ . Khi tính cần chia làm 2 trường hợp đại lượng d có giá trị nhỏ ( ,

)

Khi đó, để tính Correlogram thì trước tiên phải tính

∈

(độ phức tạp O(n2d)) và d có giá trị lớn (độ phức tạp O(n3dw-3) với

w [2,3)).

(cid:153) Quy hoạch động: khi giá trị d nhỏ

)

) 1 − +

c h , λ ( x y ,

c h , λ + ( x k y

) ( ) 0

(7) Để dàng kiểm chứng: ) ( ) (

1= nếu p∈Ic và 0 nếu ngược lại.

( ) c h , 0 pλ

với quy ước

)

( ,c h kλ p

Ta tính cho mọi p∈Ic với mỗi k=1,…d theo

,c v

công thức (7). Khi đó, với mỗi k ta mất chi phí O(n2) nên chi phí tổng cộng là O(n2d).

pλ . Ta có công thức tổng quát:

Nguyễn Bá Công – Nguyễn Hữu Đức

ới Tương tự v

Chương 2: Các khái niệm cơ bản

−

2k −

) ( ) I

)

−

− + 1

( k c c , i

) (

c h , λ j ( − x k y k ,

) (

c v , λ j ( − x k y k ,

) (

c v , λ j ( + x k y k ,

) (

( c h , λ j ( − x k y k ,

)

x y ,

∑ ) ∈ I

(

Độ phức tạp của công thức trên là O(n2). Độ phức tạp của toàn thuật toán là O(n2d) nhưng với hằng số

d nhỏ thì độ phức tạp tương đương O(n2).

(cid:153) Nhân ma trận: khi giá trị d lớn

Khi giá trị d lớn và cách xa nhau thì thuật toán trên không còn

được tối ưu. Khi đó ta sẽ sử dụng phương pháp quy hoạch động

phức tạp hơn – thuật toán nhân ma trận nhanh.

)

( ,c h kλ p

) 1

)

I p (

= ⇔

= . Sau

thành phép nhân ma Trước tiên, ta chuyển việc tính

cI p (

trận. Đặt Ic là ma trận 0–1 cấp n x n với

1 −

k }} 0,...0,1,...,1, 0..., 0

đó định nghĩa N1 là ma trận cấp n x nd với cột thứ (nk+y), y∈ [n],

⎡ ⎢ ⎢ ⎣

⎤ ⎥ ⎥ ⎦

k∈ [d] là . Dễ dàng kiểm chứng

(

)

)[ I N x nk c

]

) ( , c h kλ ( x y ,

Tiếp theo ta dùng ma trận N2 dùng tích luỹ kết quả

cN1 với mỗi khoảng cách k∈ [d] và

n x

k ) (2 )

λ= 1 (

c h , x k y k , −

từ phép nhân I

mỗi cột y∈ [n]. Để tích luỹ tổng này, cột thứ k của N2 có dạng

[1,2,…,2k+1,2k+1,…,2k+1,2k…,1]. Với N2 nhân vào bên phải IcN1,

((

)

]

k (2 )

= Σ

kết quả của n x d phép nhân thể hiện bằng tổng trên

n x

I N N y k c

2 )[

)

λ= 1 (

c h , x k y k , −

−

). (

Ta có (IcN1)N2=Ic(N1N2), mặt khác N1N2=N là ma trận kích

thước n x d. Khi đó, thuật toán tính trước N với n được cho và sử

dụng phép nhân ma trận nhanh để tính IcN. Bằng cách thêm từng cột

k ) (2 )

x y ( ,

c h , λ∈ ) ( x k y k , I −

Nguyễn Bá Công – Nguyễn Hữu Đức

trong phép nhân, chúng ta có thể tính , thành

Chương 2: Các khái niệm cơ bản

) ( ) I

( k ,i c c

phần thứ nhất của . Tương tự, ta có thể tính 3 thành phần

còn lại.

∈

Chi phí của thuật toán này là chi phí của phép nhân IcN, ma

(thực nghiệm, trận 0–1 kích thước n x n với ma trận nguyên kích thước n x d. Do đó, chi phí của thuật toán là O(n3dw-3) với w [2,3)

thuật toán Strassen có w ≈ 2,7).

2.2. Vân (textture)

2.2.1 Khái niệm

Vân (texture), đến nay vẫn chưa có một định nghĩa chính xác cụ thể về

vân, là một đối tượng dùng để phân hoạch ảnh ra thành những vùng được quan

tâm và để phân lớp những vùng đó. Vân cung cấp thông tin sự sắp xếp về mặt

không gian của màu sắc và cường độ của một ảnh. Vân được đặc trưng bởi sự

phân bổ không gian của những mức cường độ trong một khu vực láng giềng

với nhau. Vân của ảnh màu và vân đối với ảnh xám là như nhau. Vân gồm

nhiều vân gốc hay vân phần tử gộp lại, đôi khi được gọi là texel. Xét về vấn đề

phân tích vân, có hai đặc trưng chính yếu nhất:

(cid:131) Cấu trúc vân: vân là tập hợp những texel được sắp xếp theo một số

quy luật nhất định hay có cấu trúc không gian lặp đi lặp lại

(cid:131) Sự thống kê vân được định nghĩa như sau: vân là một độ đo về số

lượng của sự sắp xếp những mức xám hay cường độ sáng trong

vùng. Một vân bất kỳ có thể coi như là một tập của những texel thô

trong một quan hệ không gian đặc biệt nào đó. Một cấu trúc không

gian của một vân bất kỳ sau đó có thể bao gồm một sự mô tả của

texel và một đặc tả về không gian. Những texel đương nhiên phải

được phân đoạn và quan hệ không gian phải được tính toán một cách

thật hiệu quả. Texel là những vùng ảnh có thể trích rút từ một số

Nguyễn Bá Công – Nguyễn Hữu Đức

hàm phân ngưỡng đơn giản. Đặc điểm quan hệ không gian của

Chương 2: Các khái niệm cơ bản

chúng có thể miêu tả như sau: Giả sử rằng chúng ta có tập những

texel, với mỗi phần tử của tập hợp này ta có thể đặc trưng bởi một

điểm ý nghĩa nhất, điểm này gọi là trọng tâm. Đặt S là tập của những

điểm này. Với mỗi cặp điểm P và Q trong tập S, ta có thể xây dựng

đường phân giác trực giao nối chúng lại với nhau. Đường phân giác

trực giao này chia mặt phẳng thành hai nửa mặt phẳng, một trong

chúng là tập của những điểm gần với P hơn và cái còn lại là tập những điểm gần với Q hơn. Đặt HQ(P) là nửa mặt phẳng gần P hơn.

Ta có thể lặp lại quá trình này với mỗi điểm Q trong S. Đa giác

PV (

)

Q PH (

Voronoi của P là vùng đa giác bao gồm tất cả những điểm gần P hơn

= I

PQSQ∈

những điểm khác của S và được định nghĩa: )

2.2.2 Một số loại vân tiêu biểu

Hình 30: Các ví dụ về vân

2.2.3 Ma trận đồng hiện (Co-occurrence Matrix)

Ma trận đồng hiện là ma trận lưu trữ số lần xuất hiện của những cặp

điểm ảnh trên một vùng đang xét. Các cặp điểm này được tính theo những quy

luật cho trước.

Nguyễn Bá Công – Nguyễn Hữu Đức

Ví dụ với ảnh f như sau:

Chương 2: Các khái niệm cơ bản

ta có ma trận đồng hiện p

(1,0), với

)0,1(P

2200

204 022 200

⎤ ⎥ ⎥ ⎥ ⎦

⎡ ⎢ ⎢ ⎢ ⎣

2200

0011 ⎡ ⎢ 0011 ⎢ ⎢ ⎢ ⎣

⎤ ⎥ ⎥ ⎥ ⎥ ⎦

(lưu ý là có rất nhiều ma trận đồng hiện khác nhau cho một ma trận

ban đầu)

Ma trận đồng hiện trên tạo ra bởi những cặp điểm lệch nhau (1,0) –

nghĩa là 2 điểm kế nhau trên cùng hàng. Giá trị tại dòng 0, cột 0 của ma trận

đồng hiện trên là 4 vì ảnh f có 4 cặp điểm 0 0 kế nhau trên cùng một hàng.

Tương tự như vậy, giá trị ở dòng 1, cột 2 của ma trận là 0 vì không có cặp 1 2

nào xuất hiện nhau trên cùng một hàng.

j ],[

cr |],{[|

crf ),(

rfvài (

)

j |}

trong

tđó

(

)

iC t

ct , x

Công thức tổng quát của ma trận đồng hiện là:

Ví dụ với ma trận f đã cho như trên thì khi t=(1,0) ta sẽ có ma trận

đồng hiện như ví dụ trên, và khi t=(1,1), nghĩa là tìm những cặp điểm kế

)1,1(P

202 112 100

⎤ ⎥ ⎥ ⎥ ⎦

⎡ ⎢ ⎢ ⎢ ⎣

nhau trên cùng một đường chéo, ta có ma trận đồng hiện là:

Từ ma trận đồng hiện người ta định nghĩa ra các đặc trưng về vân

như sau:

],[2 j

iP t

∑∑

(cid:153) Energy:

log],[ j

(

])

iP t

,[ iP t

∑∑

(cid:153) Entropy:

(cid:153) Maximan Probability:

iPt

max ji ,

Nguyễn Bá Công – Nguyễn Hữu Đức

],[ j

Chương 2: Các khái niệm cơ bản

],[ j

l iP t

∑∑ − |

(cid:153) Contrast (thông thường k=2 và l=1)

≠

∑∑

l ],[ iP j t k | | i j −

(cid:153) Inverset difference moment:

)(

],[ j

( ui −

−

) iPuj j

∑∑

aa i

])

(cid:153) Correlation

jiP .[ t

∑ ∑ i (

∑ ∑ j (

1 =

((

)

j ],[

ui −

iP t

∑

1 =

((

)

j ],[

uj −

iP t

∑

1 =

Thuật tóan tính ra các đặc trưng vân từ ma trận đồng hiện

(cid:153) Xây dựng các ma trận đồng hiện với nhiều t khác nhau.

(cid:153) Tính 6 đặc trưng của texture ứng với mỗi ma trận đồng hiện đã

xây dựng ở bước 1

2.2.4 Phép biến đổi Wavelet

Vân thu được từ biến đối wavelet được hầu hết các nghiên cứu công

nhận là đặc trưng về vân tốt nhất cho việc phân đoạn ảnh.Từ một vùng kích

thước nxn ta có thể thu được một vector có 3 thành phần đặc trưng cho texture

với biến đối wavelet ở mức 1. Để có được 3 thành phần này, chúng ta áp dụng

biến đổi wavelet Daubechies-4 hoặc bộ lọc Haar với thành phần L của ảnh. Sau

khi áp dụng 1 mức biến đổi, chúng ta sẽ có 4 miền tần số (frequency band) thì

khi đó một thành phần vector sẽ được tính bằng giá trị trung bình của vùng trên

miền tần số tương ứng ấy. Ví dụ, ta xét trên vùng 4x4, thông qua biến đổi

Daubechies-4, ta có 4 miền tần số là LL, HL, LH, HH như ở Hình 4, từ 4 miền

Nguyễn Bá Công – Nguyễn Hữu Đức

đó, ta có được 3 thành phần tương ứng với giá trị ở các miền HL, LH và HH.

Chương 2: Các khái niệm cơ bản

Hình 31: Decompostion để tạo ra các frequency bands bởi biến đổi Wavelet Như vậy với một hình có kích thước 4x4 như trong ví dụ trên thì

cc , , lk k l ,1 +

c , c , lk 1, k +

l 1,1 ++

thành phần ứng với HL (giả sử HL bao gồm ) sẽ được

1 2

(

)

1 1 ∑ ∑ 0 0

1 4

tính:

Tính tóan tương tự cho các vùng LH, HH:

Thuật tóan tính ra các đặc trưng vân theo biến đổi Wavelet:

o Tính biến đổi Wavelet trên toàn ảnh.

o Ứng với mỗi vùng cần tính, ta tính được 3 thành phần ứng

với các miền HL, LH và HH

o Khi áp dụng biến đổi wavelet ở những mức sâu hơn, ta sẽ

có tương ứng 3xV thành phần ứng với V là chiều sâu của

biến đổi Wavelet.

Lưu ý: Một cải tiến khác sẽ đem lại hiệu quả rất nhiều cho việc phân

đọan là áp dụng DWF (discrete wavelet frames). Cách thức trên được khá

Nguyễn Bá Công – Nguyễn Hữu Đức

nhiều nghiên cứu khác đã vận dụng và thành công.

Chương 2: Các khái niệm cơ bản

2.3. Hình dáng

2.3.1 Khái niệm về biên cạnh

Biên cạnh là đối tượng phân cách giữa 2 vùng ảnh thuần nhất có độ

sáng khác nhau (Biên là nơi có biến thiên về độ sáng). Tập hợp các điểm biên

tạo thành biên hay đường bao của ảnh (boundary). Ví dụ, trong một ảnh nhị

phân, một điểm có thể gọi là biên nếu đó là điểm đen và có ít nhất một điểm

trắng lân cận. Trong bài toán truy tìm ảnh, biên được sử dụng cho việc tìm

kiếm những ảnh có cùng hình dáng với nhau. Để hình dung tầm qua trọng của

biên ta xét đến ví dụ sau: khi người hoạ sĩ vẽ một cái bàn gỗ, chỉ cần vài nét

phát thảo về hình dáng như mặt bàn chân bàn mà không cần thêm các chi tiết

khác, người xem đã co 1thể nhận ra đó là cái bàn. Nếu ứng dụng của ta là phân

lớp nhận diện đối tượng, thì coi như nhiệm vụ đã hoàn thành. Tuy nhiên nếu

đòi hỏi thêm các chi tiết khác như vân gỗ hay màu sắc, … thì với chừng ấy

thông tin là chưa đủ. Nhìn chung về mặt toán học, người ta coi điểm biên của

ảnh là điểm có sự biến đổi đột ngột về độ xám. Nhìn chung về mặt toán học,

người ta có thể coi điểm biên của ảnh là điểm có sự biến đổi đột ngột về độ

xám như chỉ ra trong hình sau:

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 32: Đường bao của ảnh

Chương 2: Các khái niệm cơ bản

Như vậy phát hiện biên một cách lý tưởng là xác định được tất cả các

đường bao trong các đối tượng. Định nghĩa toán học của biên ở trên là cơ sỡ

cho các kỹ thuật phát hiện biên.

2.3.2 Các phương pháp phát hiện biên

xfkjh

),(

(

yj ,

)

−

∑ ) yxg ,( Trong đó:

Phương pháp chung:

g(x,y):ảnh kết quả

h(j,k): ảnh góc

f(x-j,y-k): mặt nạ

Có 2 phương pháp phát hiện biên:

2.3.2.1 Phát hiện biên trực tiếp

Phương pháp này nhằm làm nổi biên dựa vào sự biến thiên về giá

trị độ sáng của điểm ảnh. Kỹ thuật chủ yếu dùng phát hiện biên ở đây là

kỹ thuật đạo hàm. Nếu lấy đạo hàm bậc nhất của ảnh ta có phương pháp

gradient, nếu lấy đạo hàm bậc 2 ta có kỹ thuật Laplace.

o phát biểu phương pháp Gradient (Mức độ biến thiên lớn

nhất của hàm ảnh)

Phương pháp gradient là phương pháp dò biên cục bộ

dựa vào cực đại của đạo hàm. Theo định nghĩa gradient là một

vector các thành phần biểu thị tốc độ thay đổi giá trị của điểm

ảnh theo 2 hướng x và y.

Gradient của f(x,y)

▼f(x,y)=[∂f(x,y)/∂x,∂f(x,y)/∂y]=[fx,fy]

2)1/2

Biên độ:

2 + fy

C(x,y)=(fx

Hứơng

Nguyễn Bá Công – Nguyễn Hữu Đức

Ф (x,y)=arctan(fy/fx)

Chương 2: Các khái niệm cơ bản

Hình 33: Gradient của ảnh theo hướng θ

o Phương pháp Laplace:

Toán tử Laplace do gradient theo một số hướng đã

chọn. Nếu ta ký hiệu gk là gradient Laplace theo hướng θ=Л/2

+ 2kЛ với k=0,1,…,7. Do vậy ta đo gradient E theo 8 hướng ngược chiều kim đồng hồ, mỗi hướng cách nhau 450 theo

ngược chiều kim đồng hồ.

Hình 34: Mô hình 8 hướng

▼f(x,y)=[∂f2(x,y)/∂x2,∂f(x,y)2/∂y2]

Rời rạc hoá toán tử Laplace

Nguyễn Bá Công – Nguyễn Hữu Đức

(cid:57) Sai phân bậc 1:

Chương 2: Các khái niệm cơ bản

{

xf yf

yx ),( yx ),(

yxf ),( yxf ),(

Δ Δ

= =

− −

xf y ) ( ,1 − )1 ,( yxf −

),1(

)1,(

),(2 yxfyxfyxfyxf ∇ +−++=

yxf ),(4)1,( yxf −−

(cid:57) Sai phân bậc 2:

Mặt nạ:

1 1 1 0 1 0

1 -8 1 1 -4 1

1 1 1 0 1 0

Lân cận 4 Lân cận 8

Đánh giá 2 phương pháp trên:

Khi độ sáng thay đổi rõ nét thì phương pháp Gradient làm

việc tốt .Phương pháp Laplace làm việc tốt hơn với nhiễu.

Do 2 kỹ thuật trên không hiệu quả với nhiễu nên sau khi cài

xong một trong 2 thuật toán trên ta cần tìm cách làm mảnh biên. Sau

đây là thuật toán làm mảnh biên:

Thuật toán làm mảnh biên (Non Maximal Suppression):

Bước 1: Định lượng Edge Directions trong lân cận 8

Bước 2: Với mỗi pixel có e(x,y)#0, khảo sát 2 điểm lân cận

Nguyễn Bá Công – Nguyễn Hữu Đức

theo hướng cạnh

Chương 2: Các khái niệm cơ bản

Bước 3: Nếu e(x’,y’)>e(x,y) thì đánh dấu (x’,y’ thuộc lân

cận đang xét của x,y)

Bước 4: Duyệt lại toàn bộ ảnh, xóa bỏ các điểm có e(x,y)#0

và bị đánh dấu.

Ví dụ minh họa:

Hình 35: Ảnh minh họa mảnh biên Sau khi dùng phương pháp Gradient phát hiện biên ta được:

Hình 36: Ảnh sau khi dùng phương pháp Gradient phát hiện biên

Nguyễn Bá Công – Nguyễn Hữu Đức

Sau khi dùng thuật tóan làm mảnh biên ta thu được kết quả như sau:

Chương 2: Các khái niệm cơ bản

Hình 37: Ảnh sau khi được làm mảnh biên

Các bộ lọc thông dụng dùng trong kỹ thuật Gradient

Lọc Sobel

1 0 -1 -1 -2 -1

2 0 -2 0 0 0

1 0 -1 2 1 1

Lọc Prewitt

1 1 1 -1 0 1

0 0 -1 0 1

-1 -1 -1 -1 0 1

2.3.2.2 Phương pháp phát hiện biên gián tiếp

Nếu bằng cách nào đấy, ta phân được ảnh thành các vùng thì đường

phân ranh giữa các vùng đó chính là biên. Việc phân vùng ảnh thường

được dựa vào kết cấu (texture) bề mặt của ảnh.

Cần lưu ý rằng kỹ thuật dò biên và phân vùng ảnh là 2 bài toán đối

ngẫu nhau. Thực vậy, dò biên để thực hiện phân lớp đối tượng và một khi

đã phân lớp xong có nghĩa là đã phân vùng được ảnh. Và ngược lại khi đã

phân vùng, ảnh được phân thành các đối tượng, ta có thể phát hiện được

biên. Phương pháp dò biên trực tiếp khá hiệu quả và ít chịu ảnh hưởng của

nhiễu. Song nếu sự biến thiên độ sáng không đột ngột, phương pháp này

tỏ ra kém hiệu quả. Phương pháp dò biên gián tiếp tuy khó cài đặt, song

lại áp dụng khá tốt khi sự biến thiên độ sáng nhỏ.

Nguyễn Bá Công – Nguyễn Hữu Đức

Ngoài ra chúng ta còn có thể dò biên theo Quy Hoạch Động

Chương 2: Các khái niệm cơ bản

Như đã nói dò biên theo phương pháp Gradient là xác định cực trị

cục bộ của Gradient theo các hướng; còn phương pháp Laplace dựa vào

cắt điểm không của đạo hàm bậc 2. Phương pháp dò biên theo Quy Hoạch

Động là phương pháp tìm cực trị tổng thể của các quá trình nhiều bước.

Nó dựa vào nguyên lý tối ưu của Bellman. Nguyên lý này phát biểu như

sau: “ Con đường tối ưu giữa 2 điểm cho trước cũng là tối ưu giữa 2 điểm

bất kỳ nằm trên đường tối ưu đó”.

Thí dụ, nếu C là 1 điểm trên con đường tối ưu giữa A và B thì đoạn

CB cũng là con đường tối ưu từ C đến B không kể đến ta đến C bằng cách

nào.

Hình 38: Minh họa nguyên lý Bellman

2.3.3 Các đặc trưng về biên cạnh

2.3.3.1 Lược đồ hệ số góc (Edge Direction Histogram)

Lược đồ gồm 73 phần tử trong đó:72 phần tử đầu chứa số điểm ảnh

có hệ số gốc từ 0 – 355 độ, các hệ số góc này cách nhau 5 độ. Phần tử

cuối chứa số phần tử không nằm trên biên cạnh .

Cần chuẩn hóa các đặc trưng này để thích hợp với kích thước khác

1,0[

,...,

]71

)

( IH

∈

) i )

( Im ( n

D I

Nguyễn Bá Công – Nguyễn Hữu Đức

nhau của ảnh:

Chương 2: Các khái niệm cơ bản

)72(

H )72( DIn ) (

m(ID,i) là số điểm ảnh thuộc biên cạnh có hệ số gốc là αi=i*5

nE(ID) là tổng số các điểm ảnh thuộc biên cạnh

n(ID) là tổng số điểm ảnh của ảnh ID

Ví dụ minh hoạ về lược đồ hệ số góc của ảnh:

Hình 39: Ảnh minh họa lược đồ hệ số góc

Hình 40: Đường biên của ảnh

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 41: Lược đồ hệ số góc của ảnh

Chương 2: Các khái niệm cơ bản

2.3.3.2 Vector liên kết hệ số góc (Edge Direction Coherence

Vector):

Là lược đồ tinh chế lược đồ hệ số góc, chia mỗi ô chứa (bin) thành

2 nhóm điển ảnh: Nhóm điểm liên kết hệ số góc (coherent pixels) và

nhóm điểm không liên kết hệ số góc (non-coherence pixels).

Một pixel trong một ô chứa (bin) được gọi là điểm liên kết hệ số

góc (coherent) nếu nó thụôc vùng gồm các điểm thuộc cạnh có hệ số góc

tương tự với kích thướt lớn (thường vào khoảng 0.1% kíh thướt ảnh).

Với mỗi ô chứa (bin) giả sử số điêm liên kết hệ số góc là α và số

điểm không liên kết hệ số góc là β thì vector liên kết hệ số góc được xác

định:

VE=[(α1,β1),(α2,β2),..,(αn,βn)], n là số ô màu (bin)

Độ đo tính tương tự giữa 2 ảnh dựa trên đặc trưng vector liên kết

−

IID ,( ) DQE

Q j

D j

Q j

=∑ (| | | + ββαα D j

j 1 =

hệ số góc:

Nhận xét:

Chỉ cần dùng 145 đặc trưng cho mỗi ảnh (72 x2 +1)

Ảnh thành phố có khuynh hướng tạo các điểm liên kết hệ số

góc theo hướng ngang dọc

Ảnh thiên nhiên có khuynh hướng ít tạo các điểm liên kết hệ

số góc theo hướng ngang dọc .

Vì vậy nó là đặc trưng có ưu điểm hơn lược đồ hệ số góc đối

với việc phân lớp ảnh thiên nhiên và thành phố .

Do đó khi tìm kiếm cảnh thành phố người sử dụng nên chọn

đặc trưng lược đồ hệ số góc hay vector liên kết hệ số góc.

Nguyễn Bá Công – Nguyễn Hữu Đức

Ví dụ minh họa ảnh và lược đồ vector liên kết hệ số góc:

Chương 2: Các khái niệm cơ bản

Hình 42: Ảnh minh họa vector liên kết hệ số góc

Hình 43: Ảnh minh họa sự liên kết giữa các biên cạnh

Màu đỏ là thể hiện những điểm liên kết với nhau

Hình 44: Lược đồ vector liên kết hệ số góc của ảnh

2.3.4 Vùng và các đặc trưng về vùng

Ảnh gồm tập hợp các vùng hay còn gọi là vần. Đây là đặc trưng cấp cao

của ảnh. Với đặc trưng vùng sẽ giúp cho chúng ta có thể giải quyết được một

vấn đề lớn đang cản trở bước phát triển việc truy tìm ảnh dựa vào nội dung là

dữ liệu nhập được mô phỏng gần gũi hơn với suy nghĩ của con người và ảnh

tìm được có thể mang nội dung ngữ nghĩa rất khác so với ảnh truy vấn.

Để cho dễ diễn đạt các đặc trưng về vùng, ở đây mỗi ảnh A được chia

Nguyễn Bá Công – Nguyễn Hữu Đức

nhỏ thành các khối con Ki kích thước 4x4 (điểm ảnh). Các đặc trưng trong mỗi

Chương 2: Các khái niệm cơ bản

khối con gồm 3 đặc trưng: màu,3 đặc trưng về vân, và vị trí của các khối Ki

trong ảnh.

Sau khi phân đoạn ảnh thành các vùng thì các đặc trưng về vùng chính

là các đặc trưng cấp cao của ảnh. Sau đây là các đặc trưng về vùng:

2.3.4.1 Đặc trưng màu

Vì vùng Ci bây giờ gồm nhiều khối con Ki có đặc trưng màu tương

tự nhau nên chúng ta không chọn đặc trưng màu cho vùng là đặc trưng

màu trung bình vì sẽ không thể hiện được chính xác phân bố màu trong

vùng , vì vậy chúng em chọn đặc trưng lược đồ màu ứng với mỗi vùng ,

với hệ màu HSI (Hue , Saturation , Intensity ) cùng việc định lượng không

gian màu gồm 12 H , 3 S , 3 I , ta có đặc trưng lược đồ màu:

ich

{ [j] , jє[0..107]},

ich

trong đó [j] là phần tử thứ j của lược đồ màu của vùng c i

2.3.4.2 Đặc trưng vân

Giả sử mỗi vùng có N khối con .Đặc trưng vân của mỗi khối con Ki

là { Vi1 , Vi2 , Vi3},

Đặc trưng vân của vùng Ci là:

,

1 =

1 ⎛ = ∑ ⎜ N ⎝

⎞ ⎟ ⎠

1 ⎛ = ∑ ⎜ N ⎝

⎞ ⎟ ⎠

1 ⎛ = ∑ ⎜ N ⎝

⎞ ⎟ ⎠

2.3.4.3 Đặc trưng hình dáng

Là đặc trưng cấp cao góp phần quan trọng trong việc truy tìm ảnh

phù hợp hơn về mặt ngữ nghĩa.

DTCi

| Ci

| A

| |

Nguyễn Bá Công – Nguyễn Hữu Đức

Đặc trưng thứ nhất đặc tả diện tích của vùng:

Chương 2: Các khái niệm cơ bản

, yx

∑ ) ∈

(

1 iC

| =

là số điểm ảnh trong vùng Ci là số điểm ảnh trong ảnh A

∑ 1 ) Ayx ∈

(

Đặc trưng thứ 2 đặc tả vị trí của vùng:

Vị trí này chính là trọng tâm của vùng , điểm này có thể nằm

trong vùng , tuy nhiên điều này không quan trọng vì khoảng cách

x C

, yx

y C

, yx

∑ ) ∈

(

∑ ) ∈

(

⎞ ⎟ ⎟ ⎠

⎛ ⎜ ⎜ ⎝

so sánh giữa các vùng không phụ thuộc điều này .

x,y là vị trí điểm ảnh trong vùng Ci,

| Ci | số điểm ảnh trong vùng Ci

Đặc trưng thứ 3 diễn tả tính Compact của vùng:

(

)

(

)

−

CCd i

hdw m C

h C

Vw | C v

V C

w vt

VT C

L 1

−

w dt

DT C

com

Com C

Độ đo đối sánh vùng

)

(

)( k

(

))(

)( l

( al ))

−

( hd C

h C

∑∑

1 =

)(k

trong đó:

h iC

là phần tử thứ k của lược đồ màu của vùng ci, N

2/1

cos

−

(

)

(

) sin

sin

−

cos (

)

⎛ ⎜ ⎜ ⎝

⎞ ⎟ ⎟ ⎠

số ô màu của lược đồ màu ,

wwwww vt

com

là các trọng số xác định mức độ

quan trọng của các đặc trưng màu , vân ,vùng

Nguyễn Bá Công – Nguyễn Hữu Đức

Ví dụ minh họa về vùng của ảnh:

Chương 2: Các khái niệm cơ bản

Hình 45: Minh họa vùng của ảnh

2.4. Độ đo

2.4.1 Khái niệm

Có một thuyết rất nổi tiếng viết rằng: Độ đo tương tự về nhận thức của

con người dựa trên một khoảng cách thích hợp trong một không gian metric

thuộc tâm lý học. Trong thuyết này, cho rằng một tập các mô hình đặc trưng

bao gồm các thuộc tính sau cho nó có thể được trình bày như là một điểm trong

một không gian đặc trưng phù hợp. Nếu D là hàm khoảng cách và k,l,m là các

đối tượng thì D cần đáp ứng các tiền đề sau:

(cid:153) D(k,l)=0 (cid:217) k≡l

(cid:153) D(k,l)≥0 khoảng cách là số dương

(cid:153) D(k,l)=D(l,k) khoảng cách có tính đối xứng

Do đó, độ đo có ý nghĩa quan trọng trong tìm kiếm ảnh dựa vào nội

dung. Độ đo mang ý nghĩa quyết định kết quả tìm kiếm sẽ như thế nào, mức

độ chính xác ra sao.

Nguyễn Bá Công – Nguyễn Hữu Đức

(cid:153) D(k,m) ≤ D(k,l) + D(l,m) bất đẳng thức tam giác

Chương 2: Các khái niệm cơ bản

2.4.2 Một số độ đo thông dụng

2.4.2.1 Khoảng cách Minkowsky:

−

),( lkD M

x ik

x il

⎡ = ∑ ⎢ ⎣

⎤ ⎥ ⎦

Trong đó:

D(k,l): là khoảng cách từ đối tượng k đến đối tượng l

d : là số chiều của không gian .

: là toạ độ thứ i của đối tượng k. xik

: là đối tượng thứ i của đối tượng l. xil

2.4.2.2 Độ đo khoảng cách min-max:

Được thực hiện trên ý tưởng lấy phần giao của 2 lược đồ cần so

sánh, ta sẽ được một lược đồ, tính tổng các giá trị có được từ lược đồ này

cho ta được độ đo min-max. Khỏang cách min-max thể hiện sự tương tự

),( lkD

min(

)

, ik x

∑

1 =

giữa 2 lược đồ. Công thức:

2.4.2.3 Khoảng cách Euclide L2:

Được thực hiện trên ý tưởng lấy hiệu giữa các bin của 2 lược đồ.

Khác với khỏang cách min-max, nó thể hiện sự khác nhau giữa 2 lược

2/1

−

(

)

lkD ),( E

1 =

⎡ = ∑ ⎢ ⎣

⎤ ⎥ ⎦

đồ.Công thức như sau:

2.4.2.4 Khoảng cách city-block L1:

−

),( lkD CB

∑

1 =

Nguyễn Bá Công – Nguyễn Hữu Đức

Chương 2: Các khái niệm cơ bản

2.4.3 Các độ đo được sử dụng trong bài tóan

Trong quá trình tìm kiếm dữ liệu ảnh dựa vào nội dung điều quan trọng

là xác định mức độ giống nhau của hai đặc trưng của 2 tấm ảnh cần so sánh.

Do đó, cần một giá trị để biếu thị cho sự giống nhau này, có nhiều cách để tính

giá trị này. Ta gọi những giá trị được tính từ những cách khác nhau này là các

loại độ đo.

Một cách đơn giản, độ đo được coi là một giá trị để biểu thị cho độ so

khớp sự giống nhau của hai đặc trưng. Tùy theo từng trường hợp, từng loại độ

đo mà giá trị này có thể âm hoặc dương, lớn hoặc nhỏ tương ứng với mức độ

giống nhau như thế nào của các loại đặc trưng .

Mỗi loại độ đo có những ưu và khuyết điểm riêng, trong từng trường

hợp cụ thể.

2.4.3.1 Độ đo tương tự giữa 2 bin màu trong hệ màu HSI

cos

sin

−

)

(

)

( S

)

] 2/12

[ (

Trong đó:

k: chỉ bin màu thứ k

l: chỉ bin màu thứ l

các thành phần H, S, I tương ứng là các giá trị thành phần

màu trong hệ màu HSI.

akl là độ tương tự giữa 2 bin màu

2.4.3.2 Độ đo dùng cho lược đồ màu

Gọi h(I) và h(M) tương ứng là 2 lược đồ màu của hai ảnh I và

ảnh M. Khi đó các loại độ đo màu được định nghĩa là một số nguyên

(hoặc số thực) theo các loại độ đo tương ứng như sau:

o Độ đo khoảng cách min-max:

Được thực hiện dựa trên ý tưởng lấy phần giao của của

Nguyễn Bá Công – Nguyễn Hữu Đức

hai lược đồ cần so sánh, ta sẽ được một lược đồ, tính tổng các

Chương 2: Các khái niệm cơ bản

giá trị có được từ lược đồ này cho ta được độ đo min-max.

), MhIhd

((

(

))

( Ih

)[

], jMhj ( )[

]

Đối với độ đo min: ta tính dựa vào giá trị min tại mỗi N bin.

{∑ min

1 =

}

Đối với độ đo max: ta tính dựa vào giá trị max tại mỗi

), MhIhd

((

(

))

( Ih

)[

], jMhj ( )[

]

N bin.

{∑ max

1 =

((

(

))

Matching

), MhIh

max(

])

(( ( Ih

)) ( )[ iMh

), ( MhIhd ∑ ∑ )[ i

}

Ví dụ minh họa: có 2 lược đồ màu như sau:

Hình 46: minh họa 2 lược đồ màu giống nhau

Sau khi dùng độ đo khỏang cách min-max ta sẽ được

Nguyễn Bá Công – Nguyễn Hữu Đức

một lược đồ màu như sau:

Chương 2: Các khái niệm cơ bản

Hình 47: Lược đồ màu thể hiện phần giao của 2 lược đồ màu trên

o Độ đo khoảng cách Euclide:

Đây là cách tính khoảng cách Euclide thông thường

), MhIhd

((

(

))

)[

]

)[ jMh

(

−

( ( Ih

) 2]

∑

1 =

giữa các N bin:

), MhIhd

((

(

))

( Ih

)[

]

)[ jMh

(

]

−

∑

1 =

hoặc có thể là:

Ví dụ: cũng 2 lược đồ màu trên

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 48: Hình minh họa độ đo Euclide

Chương 2: Các khái niệm cơ bản

Sau khi dùng độ đo khỏang các euclide ta sẽ được một

lược đồ màu như sau:

Hình 49: Lược đồ màu thể hiện độ khác nhau giữa 2 lược đồ màu trên

o Độ đo khoảng cách toàn phương:

Với việc sử dụng 2 độ đo trên sẽ có những nhược điểm

như sau: giả sử có 3 màu đỏ, cam và xanh trên hệ trục tọa độ

HSI thì ta có d(đỏ, cam)=d(đỏ, xanh). Nhưng thật ra thì

d(đỏ,cam)

này chúng em đề nghị một độ đo khác là “Độ đo khỏang cách

)

(

)( k

(

))(

)( l

( al ))

−

( hd C

h C

∑∑

1 =

)(k

tòan phương”. Công thức:

h iC

cos

sin

−

)

(

)

( S

)

là phần tử thứ k của lược đồ màu của vùng ci, N

] 2/12

số ô màu của lược đồ màu , [ (

(

)

( gCgCD

(

))

grid

∑=

)(gC Q

o Độ đo khoảng cách khi chia lưới

)(gC D

Trong đó biểu thị màu trong lưới ô vuông g của ảnh I

Nguyễn Bá Công – Nguyễn Hữu Đức

Trong đó biểu thị màu trong lưới ô vuông g của ảnh I

Chương 2: Các khái niệm cơ bản

2.4.3.3 Độ đo dùng cho đặc trưng liên kết màu (Color Coherence

Vector)

o Độ đo khoảng cách min-max:

Đối với độ đo min: ta tính dựa vào giá trị min tại mỗi

)

(min(

)

min(

))

( ID c

, αα Q

, ββ D

∑

N bin.

Trong đó:

α: là số điểm liên kết màu.

β: là số điểm không liên kết màu.

Đối với độ đo max: ta tính dựa vào giá trị max tại mỗi

)

(max(

)

max(

))

, ββ

( ID c

, αα Q

∑

N bin.

o Độ đo khoảng cách L1:

(

)

−

ID c

∑

Đây là cách tính khoảng cách thông thường

Trong đó:

α: là số điểm liên kết màu.

β: là số điểm không liên kết màu.

2.4.3.4 Độ đo dùng cho đặc trưng tự tương quan

màu(AutoCorrelogram)

o Khoảng cách min-max:

min(

[

dc ][

[

dc ][

Độ đo min:

α i

α j

∑∑

1 =

)]

Nguyễn Bá Công – Nguyễn Hữu Đức

Độ đo max:

Chương 2: Các khái niệm cơ bản

max(

[

dc ][

[

dc ][

α i

α j

∑∑

1 =

)]

Trong đó:

n: số bin màu.

m: m={1,3,5,7,9,…,2k+1}.

[

][ dc

]

[

][ dc

]

−

α i

α j

∑∑

1 =

o Khoảng cách L1:

Trong đó:

n: số bin màu.

m: m={1,3,5,7,9,…,2k+1}.

2.4.3.5 Độ đo dùng cho đặc trưng lược đồ hệ số góc (Edge

Direction Histogram)

o Độ đo khoảng cách min-max:

)

min(

)

( ID E

, αα Q

∑

Đối với độ đo min:

Đối với độ đo max: ta tính dựa vào giá trị max tại mỗi N

)

max(

)

( ID E

, αα Q D

∑

bin.

L1 : o Độ đo khoảng cách

)

−

( ID E

α Q

∑

Đây là cách tính khoảng cách euclide thông thường

2.4.3.6 Độ đo dùng cho đặc trưng liên kết hệ số góc (Edge

Direction Coherence Vector)

o Độ đo khoảng cách min-max:

Nguyễn Bá Công – Nguyễn Hữu Đức

Đối với độ đo min:

Chương 2: Các khái niệm cơ bản

)

min(

)

min(

)

ID ( E

, αα Q

, ββ D

= ∑

Đối với độ đo max: ta tính dựa vào giá trị max tại mỗi

(

)

max(

)

max(

N bin.

, ββ

ID E

, αα Q

= ∑

)

Độ đo khoảng cách L1:

)

−

β Q

β D

( ID E

− αα D

= ∑

Nguyễn Bá Công – Nguyễn Hữu Đức

Đây là cách tính khoảng cách thông thường

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

Chương 3 TRUY TÌM ẢNH DỰA VÀO ĐẶC TRƯNG

CẤP THẤP

Nguyễn Bá Công – Nguyễn Hữu Đức

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

3.1. Các đặc trưng được sử dụng để truy tìm ảnh

3.1.1 Đặc trưng về màu sắc

3.1.1.1 Lược đồ màu (histogram)

Lược đồ màu thể hiện màu sắc của ảnh. Màu sắc là thông tin gần gũi

với con người nhất. Do đó, việc tìm kiếm theo lược đồ màu sẽ thân thiện

với người dùng hơn. Dựa vào lược đồ màu có thể giúp cho người dùng

tìm kiếm những tấm ảnh có sự giống nhau về màu sắc.

Độ đo tính tương tự về màu sắc giữa lược đồ màu của ảnh truy vấn

min(

( IH

), IHj

(

))

∑

(

)

( IH

)

∑

H(IQ)và lược đồ màu của ảnh trong cơ sở dữ liệu ảnh H(ID):

Trong đó:

M: tổng số bin màu

Ưu điểm:

Lược đồ màu bất biến đối với phép biến đổi như co, quay,

tịnh tiến…

Khuyế điểm:

Có thể 2 ảnh khác nhau về ngữ nghĩa nhưng có lược đồ màu

giống nhau.

3.1.1.2 Vector liên kết màu (Color Coherence Vector)

Cũng giống như lược đồ màu đặc trưng vector liên kết màu cũng

thể hiện màu sắc của ảnh. Nó thể hiện rõ ràng mật độ phân bố những màu

Nguyễn Bá Công – Nguyễn Hữu Đức

trong ảnh. Với 2 ảnh có thể rất giống nhau về lược đồ màu nhưng do khác

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

nhau về sự phân bố màu sắc, nên trong quá trình tìm kiếm theo lược đồ

màu có thể cho ra nhiều ảnh “dư thừa”. Nếu trong quá trình tìm kiếm trên

ta sử dụng vector liên kết màu thì có thể khắc phục được tình trạng trên.

Với mỗi ô màu (bin) giả sử số điểm liên kết màu là α và số điểm

không liên kết màu là β thì vector liên kết màu được xác định:

Vc=[(α1,β1), (α2,β2), …,(αn,βn)], n là số ô màu (bin)

Độ đo tính tương tự giữa 2 ảnh dựa trên đặc trưng vector liên kết

)

−

( ID c

α Q

β Q

β D

∑

màu:

3.1.1.3 Đặc trưng tự tương quan màu (AutoCorrelogram)

Cũng giống như vector liên kết màu, đặc trưng tương quan màu

cũng thể hiện sự phân bố màu sắc của ảnh. Nó thể hiện rõ ràng mật độ

phân bố màu trong ảnh hơn. Đặc trưng này cũng nhằm giúp giải quyết

việc dư thừa trong tìm kiếm ảnh, giúp tìm kiếm những ảnh có ngữ nghĩa

gần với ảnh truy vấn hơn nhờ các tính chất sau:

(cid:153) Bao gồm các thông tin về sự tương quan về mặt không gian giữa

các màu.

(cid:153) Có thể được dùng để mô tả sự phân bố toàn cục của mối quan hệ

không gian cục bộ giữa các màu.

(cid:153) Kích thước của véctơ đặc trưng có dung lượng lưu trữ nhỏ.

Độ đo tính tương tự về màu sắc giữa đặc trưng tương quan màu của

)

[

][

]

[

][

−

= ∑ ∑

ảnh truy vấn IQ và ảnh trong cơ sở dữ liệu ảnh ID:

Nguyễn Bá Công – Nguyễn Hữu Đức

Trong đó:

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

d={1,3,5,…,2k+1}

N: là tổng số bin màu.

3.1.2 Đặc trưng về hình dáng

3.1.2.1 Lược đồ hệ số góc (Edge Direction Histogram)

Đây cũng là đặc trưng quan trọng của ảnh. Nó thể hiện về hình

dáng của ảnh. Đối với các ảnh muốn tìm kiếm theo hình dáng thì đặc

trưng về màu sắc không thể giải quyết được. Vì vậy trong các hệ tìm kiếm

dựa vào nội dung của ảnh không thể thiếu đặc trưng này.

Độ đo tính tương tự về đặc trưng lược đồ hệ số góc của ảnh truy

( ID

)

min(

)

, αα Q D

∑

vấn IQ và ảnh ID trong cơ sở dữ liệu là:

Trong đó:

n: 73 phần tử.

3.1.2.2 Vector liên kết hệ số góc (Edge Direction Coherence

Vector)

Cũng như đặc trưng lược đồ hệ số góc, vectơ liên kết hệ số góc là

đặc trưng về hình dáng của ảnh. Nó thể hiện rõ ràng hơn về hình dáng của

ảnh: thể hiện mối liên kết chặt chẽ giữa các điểm biên cạnh (các điểm biên

cạnh có cùng góc độ), cũng như là những điểm không phải là biên cạnh.

Vectơ liên kết hệ số góc còn có thể khắc phục được khuyết điểm của lược

đồ hệ số góc đó là: 2 ảnh có lược đồ hệ số góc giống nhau nhưng khác

nhau về ngữ nghĩa. Việc tìm kiếm theo đặc trưng vector liên kết hệ số góc

giúp cho kết quả chính xác hơn, ảnh tìm được mang ngữ nghĩa gần ảnh

truy vấn hơn.

Với mỗi ô chứa (bin) giả sử số điểm liên kết hệ số góc là α và số

điểm không liên kết hệ số góc là β thì vectơ liên kết hệ số góc được xác

Nguyễn Bá Công – Nguyễn Hữu Đức

định:

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

VE=[(α1,β1),(α2,β2),..,(αn,βn)], n là số bin

Độ đo tính tương tự giữa 2 ảnh dựa trên đặc trưng vectơ liên kết hệ

ID (

)

−

số góc:

β Q

∑

Việc chọn đặc trưng vectơ liên kết hệ số góc cho việc tìm kiếm,

giúp ta có thể phân biệt ảnh thiên nhiên và ảnh thành phố.

Ảnh thành phố có khuynh hướng tạo các điểm liên kết hệ số góc

theo hướng ngang dọc. Ảnh thiên nhiên có khuynh hướng ít tạo các điểm

liên kết hệ số góc theo hướng ngang dọc. Vì vậy nó là đặc trưng có ưu

điểm hơn lược đồ hệ số góc đối với việc phân lớp ảnh thiên nhiên và

thành phố.

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

3.2.1 Tổng quan về giải thuật

Giải thuật này giúp ta tạo được một cây phân cấp từ một tập dữ liệu bất

kỳ mà ta có thể xác định khỏang cách giữa các phần tử. Giải thuật này có ưu

điểm nổi bật so với các thuật toán phân lớp phân cấp khác là: số lớp cơ sở

phân cấp không cần xác định trước. Từ đó ta có thể phân lớp từ thô cho đến

mịn một tập dữ liệu nào đó.

3.2.2 Giải thuật

Chi tiết giải thuật phân lớp phân cấp HAC dùng để phân lớp một tập các

đối tượng thành các lớp phân cấp

Nguyễn Bá Công – Nguyễn Hữu Đức

Giải thuật:

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

{

,...,2,1

}

, iK i =

Giả sử ta có tập , với Ki là các đối tượng cần phân

lớp

Giải thuật được thực hiện gồm các giai đọan chính sau:

{

,...2,1

}

Giai đọan khởi động:

R 0

, iK i =

Bước 1: Tạo phân cấp , với Ci = Ki

Bước 2: P0 = P(k)

Trong đó P(k) là ma trận kích thước NxN với P(i, j)=d(Ki,Kj).

Bước 3: t = 0.

Giai đọan phân lớp:

Bước 1: t = t + 1.

r ≠ s

Bước 2: Chọn cặp Ci, Cj sao cho d(Ci, Cj) = min d(Cr, Cs), r, s = 1, 2,

…, N,

(

})

C {

}

−

∪

R t

CC { i ,

1 −

Bước 3: Kết nạp Ci, Cj vào lớp Cq và tạo một phân cấp Rt,

Bước 4: Cập nhật P(t) từ P(t-1) bằng 2 bước:

Xóa các dòng và cột tương ứng với 2 lớp vừa được kết

nạp .

Thêm dòng mới và cột mới chứa khỏang cách giữa lớp

mới tạo và các lớp cũ.

Bước 5: Lặp lại B1 khi nào các Ki đều chưa thuộc cùng một lớp.

Giai đọan chọn số lớp khớp với dữ liệu:

(

)

max{

( Cdia

)},

∀

∈

CCd i

( Cdia i

, CC i ,

R t

dia(C)

y),

max{d(x, =

∈

Chọn thời điểm dừng trong cây phân cấp khi Rt thỏa:

Nguyễn Bá Công – Nguyễn Hữu Đức

Trong đó

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

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 Giải thuật HAC cũng được chúng em áp dụng vào việc phân lớp cơ sở

dữ liệu. Điều này tránh việc truy tìm tuần tự trên cơ sở dữ liệu lớn theo truyền

thống trước đây, đồng thời giúp cho tốc độ tìm kiếm nhanh hơn đáng kể so với

tìm kiếm tuần tự. Các ảnh được xét chỉ là nhóm các ảnh thuộc cùng một lớp có

độ giống nhau về đặc trưng nào đó.

Giải thuật phân lớp phân cấp theo các đặc trưng của ảnh

Giả sử A={Ki,i=1,2,…,N}, với A là cơ sở dữ liệu ảnh, Ki là ảnh thứ i

trong cơ sở dữ liệu.

Gải thuật xây dựng cây gồm các gai doạn:

{

,...2,1

}

Giai đọan khởi động:

R 0

, iK i =

Bước 1: Tạo phân cấp , với Ci = Ki

Bước 2: P0 = P(k)

Trong đó P(k) là ma trận kích thước NxN với P(i, j)=d(Ki,Kj).

Bước 3: t = 0.

Giai đọan phân lớp:

Bước 1: t = t + 1.

r ≠ s

Bước 2: Chọn cặp Ci, Cj sao cho d(Ci, Cj) = min d(Cr, Cs), r, s = 1, 2,

…, N,

(

})

C {

}

−

∪

R t

CC { i ,

1 −

Bước 3: Kết nạp Ci, Cj vào lớp Cq và tạo một phân cấp Rt,

Bước 4: Cập nhật P(t) từ P(t-1) bằng 2 bước:

Xóa các dòng và cột tương ứng với 2 lớp vừa được kết

nạp .

Thêm dòng mới và cột mới chứa khỏang cách giữa lớp

Nguyễn Bá Công – Nguyễn Hữu Đức

mới tạo và các lớp cũ.

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

Bước 5: Lặp lại B1 khi nào các Ki đều chưa thuộc cùng một lớp.

Giai đoạn rút gọn cây:

Sau khi xây dựng câp phân cấp xong, chúng ta cần thực hiện việc

rút gọn cây, để gôm những nút giống nhau về cùng một nhóm. Việc rút

gọn cây được thực hiện như sau:

Giả sử có cây phân cấp:

Node P_l ←{ dmin(nl,nr), dmax(nl,nr)

Node n_l ←{dmin(cl,cr), dmax(cl,cr)

,(min{

∀

),(min d ba

l ba

, blal εε ∀ a

max{

∀

),(max d ba

,( ld a

l b

, blal εε ∀ a

c min

pc ),(

min

p − min c d min

c max

pc ),(

max

p max d

− c max

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 50:Cây phân cấp cho việc phân lớp cơ sở dữ liệu

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

Mỗi nhóm sau khi đuợc gôm lại sẽ được trích chọn một phần

tử đại diện. Phần tử đại diện được chọn là phần tử có tổng khoảng

cách đến các phân tử còn lại nhỏ nhất.

Việc phân lớp này nhằm chuẩn bị cho giai đoạn truy tìm. Nó

giúp rút ngắn thời gian tìm kiếm nhờ vào việc tránh phải duyệt toàn

bộ cơ sở dữ liệu.

Các ví dụ minh hoạ việc phân lớp ảnh theo các đặc trưng :

(cid:131) Về đặc trưng lược đồ màu chúng em minh họa trên cơ sở dữ liệu

gồm 9 ảnh và thu được kết quả như sau như sau:

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 51: Cơ sở dữ liệu minh họa thuật toán HAC vào việc phân lớp ảnh theo đặc trưng lược đồ màu

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

Hình 52:Cây phân cấp theo lược đồ màu

Hình 53: Nhóm các ảnh có cùng đặc trưng màu

(cid:131) Về đặc trưng vector liên kết màu chúng em minh họa dựa trên cơ sở

dữ liệu gồm 8 ảnh và cũng thu được kết quả như sau:

Hình 54:Cơ sở dữ liệu phân lớp ảnh theo đặc trưng liên

Nguyễn Bá Công – Nguyễn Hữu Đức

kết màu

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

Hình 55: Cây phân cấp theo đặc trưng liên kết màu

Hình 56: Nhóm các ảnh có cùng đặc trưng liên kết màu

(cid:131) Về đặc trưng Correlogram cũng được minh họa bằng cơ sở dữ liệu

Nguyễn Bá Công – Nguyễn Hữu Đức

gồm 9 tấm ảnh và kết quả thu được như sau:

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

Hình 57: Cơ sở dữ liệu minh họa thuật toán HAC đồi với

đặc trưng Correlogram

Hình 58: Cây phân cấp theo đặc trưng Correlogram

Hình 59: Nhóm các ảnh có cùng đặc trưng Correlogram

(cid:131) Về đặc trưng lược đồ hệ số góc chúng em minh họa trên cơ sở dữ

Nguyễn Bá Công – Nguyễn Hữu Đức

liệu gồm 8 tấm ảnh và kết quả thu được như sau:

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

Hình 60: Cơ sở dữ liệu minh họa thuật toán HAC đối với

đặc trưng lược đồ hệ số góc

Hình 61: Cây phân cấp theo đặc trưng lược đồ hệ số góc

Hình 62: Nhóm các ảnh có cùng đặc trưng lược đồ hệ số góc

(cid:131) Về đặc trưng vector liên kết hệ số góc chúng em minh họa trên cơ sở

Nguyễn Bá Công – Nguyễn Hữu Đức

dữ liệu gồm 8 tấm ảnh và kết quả thu được như sau:

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

Hình 63: Cơ sở dữ liệu ảnh minh họa thuật toán HAC để phân lớp theo đặc trưng vector liên kết hệ số góc

Hình 64: Cây phân cấp theo đặc trưng liên kết hệ số góc

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 65: Nhóm các ảnh có cùng đặc trưng liên kết hệ số góc

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

3.3. Tạo chỉ mục truy tìm ảnh

Quá trình rút trích đặc trưng của ảnh đòi hỏi phải tốn nhiều thời gian, do đó

khi tìm kiếm trên một cơ sở dữ liệu ảnh lớn thì vấn đề thời gian là một trong

những vấn đề gây khó khăn cho bài toán, do đó cần phải có biện pháp tổ chức cơ

sở dữ liệu hiệu quả giúp cho việc tìm kiếm được nhanh hơn, hiệu quả hơn.

Điều đó đã được giải quyết bằng cách xây dựng cơ sở dữ liệu ảnh chúng ta

thành những cây phân cấp bằng giải thưật HAC, nghĩa là xây dựng cây với các nút

lá là tập các ảnh trong cơ sở dữ liệu có đặc trưng giống nhau tuỳ theo người dùng

muốn về chung một nhóm. Việc tạo cây phân cấp với các nút đuợc gôm lại thành

từng nhóm, mỗi nhóm có một phần tử đại diện giúp cho việc truy tìm có thể loại

bỏ được những nhóm có ảnh không giống với ảnh truy vấn một cách nhanh chóng.

Từ đó việc truy tìm sẽ hiệu quả hơn về thời gian truy xuất. Và như vậy có thể coi

là một chỉ mục để truy tìm ảnh hiệu quả.

Ví dụ minh họa cây phân cấp ban đầu và cây chỉ mục sau khi tiến hành gom

nhóm:

Hình 66: Cây phân cấp ban đầu

Nguyễn Bá Công – Nguyễn Hữu Đức

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

Hình 67: Cây chỉ mục

3.4. Các chiến lược truy tìm ảnh

3.4.1 Truy tìm ảnh xét đến tính phân bố toàn cục

3.4.1.1 Tìm kiếm theo màu sắc

Phương pháp phổ biến để tìm kiếm ảnh trong một tập những ảnh

hỗn tạp cho trước là dựa vào màu sắc của chúng. Đây là cách làm khá đơn

giản, tốc độ tìm kiếm tương đối nhanh nhưng khuyết điểm là kết quả tìm

kiếm lại có độ chính xác không cao. Nhưng đây có thể được xem như là

bước lọc đầu tiên cho những tìm kiếm sau. Muốn được kết quả chính xác

cao đòi hỏi sự kết hợp đồng thời với vân (texture) và hình dáng (shape).

Cho đến nay, để giải quyết vấn đề về màu sắc, cách tiếp cận chính vẫn là

dựa vào các đặc trưng sau: lược đồ màu, vector liên kết màu, lược đồ

tương quan màu.

Hệ màu chúng em sử dụng là hệ màu HSI, với 113 màu đại diện cho 224 màu sẽ giúp ta giảm được không gian lưu trữ rất nhiều, mà không

gây ảnh hưởng nhiều đến mức cảm nhân của con người.

3.4.1.1.1 Lược đồ màu

Tìm kiếm ảnh sử dụng lược đồ màu là phương pháp thông

Nguyễn Bá Công – Nguyễn Hữu Đức

dụng nhât và dễ cảm nhận nhất. Nhưng việc tìm kiếm theo đặc trưng

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

này thất bại trong trường hơp: có thể có 2 ảnh giống nhau về lược đồ

màu nhưng khác nhau nhiều về ngữ nghĩa.

Ví dụ 1: ảnh có lược đồ màu giống nhau với độ giống nhau là

70%.

Hình 68: Minh họa 2 ảnh có lược đồ màu giống nhau

Ví dụ 2: 2 ảnh cũng có độ giống nhau về lược đồ màu là 70%

nhưng khác nhau về ngữ nghĩa

Hình 69: Minh họa 2 ảnh giống nhau về lược đồ màu nhưng khác nhau về ngữ nghĩa

3.4.1.1.2 Vector liên kết màu

Trong tìm kiếm ảnh với việc sử dụng đặc trưng vectơ liên kết

màu sẽ giúp ta tránh được tình trạng hai ảnh có cùng lược đồ màu

nhưng khác nhau hoàn toàn về ngữ nghĩa.

Nguyễn Bá Công – Nguyễn Hữu Đức

Ví dụ minh họa:

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

Cũng giống ví dụ về lược đồ màu ở trên. 2 ảnh sau có độ

giống nhau về lược đồ màu là 70%. Nhưng theo đặc trưng vector

liên kết màu thì 2 ảnh này hòan tòan khác nhau.

Theo đặc trưng Lược đồ màu:

Hình 70: Minh họa 2 ảnh có lược đồ màu giống nhau nhưng khác nhau về ngữ nghĩa

Theo đặc trưng Vector liên kết màu:

Hình 71: Hình minh họa vector liên kết màu khắc phục tính không duy nhất của lược đồ màu

Như vậy, với đặc trưng lược đồ màu thì không thể lọai bỏ

những ảnh có lược đồ màu giống nhau nhưng khác nhau về ngữ

nghĩa. Trái lại với đặc trưng Vector liên kết màu thì khắc phục được

nhược điểm này của lược đồ màu. Do đó, tìm kiếm theo đặc trưng

vector liên kết màu sẽ giảm bớt đáng kể những ảnh dư thừa trong

quá trình tìm kiếm, nâng cao hiệu quả tìm kiếm, kết quả tìm được

Nguyễn Bá Công – Nguyễn Hữu Đức

mang ngữ nghĩa giống với ảnh truy vấn hơn.

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

3.4.1.1.3 Đặc trưng tương quan màu (Correlogram):

Cũng giống như đặc trưng vectơ liên kết màu, đặc trưng

tương quan màu thể hiện mối quan hệ chặt chẽ về sự phân bố màu

trong ảnh. Chính vì vây nếu truy tìm ảnh sử dụng đặc trưng này

cũng tránh được tình trạng mà đặc trưng lược đồ màu vấp phải.

Ví dụ minh hoạ:

Hình 72: Hình minh họa 2 ảnh có đặc trưng tương quan màu giống nhau

81.2%

3.4.1.2 Tìm kiếm theo hình dáng

Với thông tin màu sắc con người có thể tìm kiếm những ảnh giống

nhau về màu sắc mà con người cảm nhận được. Nhưng khi con người có

nhu cầu tìm kiếm những ảnh giống nhau về hình dáng thì thông tin màu

sắc không thể hiện được. Khi đó cần một đặc trưng khác đáp ứng yêu cầu

trên, đó là đặc trưng về hình dáng.

Hình dáng là một đặc trưng cấp cao hơn màu sắc. Nó đòi hỏi sự

phân biệt giữa các vùng để tiến hành xử lý về độ đo của hình dáng. Trong

nhiều trường hợp, sự phân biệt này cần thiết phải làm bằng tay. Nhưng sự

tự động hóa trong một số trường hợp có thể khả thi. Sự so khớp hình dáng

ảnh cũng có thể dùng những kỹ thuật về cấu trúc, trong đó một ảnh được

mô tả bởi những thành phần chính của nó và quan hệ không gian của

chúng. Trong việc tìm kiếm dữ liệu ảnh dựa vào nội dung, ta cần những

phương pháp có thể quyết định sự giống và khác nhau một cách nhanh

chóng. Thông thường, chúng ta luôn đòi hỏi sự bất biến cả đối với kích

thước của ảnh cũng như hướng của ảnh trong không gian. Vì vậy, một đối

Nguyễn Bá Công – Nguyễn Hữu Đức

tượng có thể được xác định trong một số hướng. Tuy nhiên, tính chất này

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

không thường được yêu cầu trong tìm kiếm ảnh. Trong rất nhiều cảnh vật,

hướng của đối tượng thường là không đổi. Ví dụ như: cây cối, nhà cửa, ...

Sau đây là các chiến lược tìm kiếm theo từng đặc trưng về hình dáng:

3.4.1.2.1 Lược đồ hệ số góc

Để tìm kiếm một ảnh mà ta quan tâm nhiều đến khía cạnh

hình dáng của các đối tượng trong ảnh thì nên sử dụng các đặc trưng

về hình dáng. Đặc trưng cơ bản nhất về hình dáng là lược đồ hệ số

góc. Đây là đặc trưng chỉ thể hiện được hình dáng chung của các đối

tượng trong ảnh.

Ví dụ tìm kiếm theo đặc trưng lược đồ hệ số góc:

Hình 73: minh hoạ 2 ảnh có lược đồ hệ số góc giống nhau

3.4.1.2.2 Vector liên kết hệ số góc

Với việc sử dụng đặc trưng vectơ liên kết hệ số góc thay cho

lược đồ hệ số góc giúp cho ta có thể gải quyết được trường hợp 2

ảnh có lược đồ hệ số góc giống nhau nhưng lại khác nhau nhiều về

ngữ nghĩa.

Ví dụ minh họa tìm kiếm theo vectơ liên kết hệ số góc giải

quyết trường hợp mà lược đồ hệ số góc mắc phải:

Hai ảnh có lược đồ hệ số góc giống nhau 86% nhưng có

Nguyễn Bá Công – Nguyễn Hữu Đức

vector liên kết hệ số góc khác nhau:

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

Hình 74:minh họa 2 ảnh có lược đồ hệ số góc giống nhau 80%

Hình 75: Hình minh họa 2 ảnh có vector liên kết hệ số góc khác nhau

3.4.1.3 Tìm kiếm kết hợp

Thừơng tìm kiếm theo từng đặc trưng có thể cho ra kết quả khá

nhiều, xuất hiện những tấm ảnh không cần thiết nên để nâng cao hiệu quả

của việc tìm kiếm, làm cho việc tìm kiếm được chính xác hơn thì chúng ta

nên kết hợp các đặc trưng lại với nhau. Giả sử khi ta muốn tìm kiếm “một

Nguyễn Bá Công – Nguyễn Hữu Đức

ngừơi mặc áo màu vàng và dáng đứng thẳng thì ta có thể kết hợp 2 đặc

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

trưng màu và lược đồ hệ số góc lại với nhau thì sẽ loại bỏ đi những tấm

ảnh có người đó mà không có dáng đứng thẳng”.

Có 2 cách tìm kiếm kết hợp: tìm kiếm kết hợp các đặc trưng với

nhau dùng toán tử BOOL; tìm kiếm kết hợp các đặc trưng với nhau dùng

trọng số.

3.4.1.3.1 Tìm kiếm kết hợp các đặc trưng với nhau dùng

toán tử BOOL

Đây là tìm kiếm kết hợp các đặc trưng lại với nhau dùng toán

tử BOOL. Ví dụ tìm những ảnh có người mặc áo màu vàng và dáng

đứng thẳng dùng toán tử AND nghĩa là: tìm những tấm ảnh sao cho

vừa thoả đặc trưng về màu sắc vừa thoả đặc trưng về hình dáng cần

tìm.

Ví dụ minh hoạ tìm kiếm kết hợp các đặc trưng:

Hình 76: Hìmh minh họa 2 ảnh giống nhau về lược đồ màu và lược đồ hệ số góc

Nhận xét: Cách tìm kiếm này có thể cho ra kết quả rỗng,

nghĩa là không có ảnh nào trong cơ sở dữ liệu thoả yêu cầu tìm

kiếm. Nhưng nếu tồn tại ảnh thì phương pháp này cho ra kết quả

Nguyễn Bá Công – Nguyễn Hữu Đức

chính xác hơn.

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

3.4.1.3.2 Tìm kiếm kết hợp các đặc trưng với nhau dùng

trọng số

Đây cũng là phương pháp tìm kiếm kết hợp các đặc trưng lại

với nhau nhưng khác trên là ở đây ta dùng trọng số. Trọng số ở đây

được hiểu là mức độ ưu tiên của các đặc trưng cần tìm kiếm. Ví dụ

người dùng cần tìm kiếm những tấm ảnh có người mặc áo màu vàng

và có dáng đứng thẳng thì người dùng có thể kết hợp 2 đặc trưng

lược đồ màu (Histogram) và lược đồ hệ số góc (Edge Direction

Histogram) lại với nhau. Nhưng ở đây khác với việc kết hợp dùng

toán tử BOOL là người dùng muốn ưu tiên cho lược đồ màu hơn thì

người dùng có thể chọn độ ưu tiên cho lược đồ màu là 70% còn lược

đồ hệ số góc chỉ có 30% thôi. Khi đó việc truy vấn sẽ trả ra kết quả

thoả mản yêu cầu tìm kiếm.

Id (

)

... ++

Idw ( 11

Idw ( 2

Idw ( n

Công thức tính độ đo giữa 2 ảnh

Trong đó:

w1,w2,…,wn là trọng số các đặc trưng tương ứng.

w1 + w2 + … + wn=1.

d1,d2,…,dn: là khoảng cách giữa 2 ảnh về đặc trưng i

nào đó i∈[1,..,n].

Khác với việc kết hợp dùng toán tử BOOL, việc tìm kiếm kết

hợp theo trọng số này luôn trả ra kết quả cho người dùng. Việc tìm

kiếm này giúp cho chúng ta có thể sắp hạng tập kết quả dễ dàng,

cũng như giúp cho người dùng có thể xem tập kết quả nhanh chóng

Nguyễn Bá Công – Nguyễn Hữu Đức

và hiệu quả hơn.

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

3.4.2 Truy tìm ảnh xét đến tính phân bố cục bộ (yếu tố

không gian) Với việc tìm kiếm dựa vào tính phân bố cục bộ sẽ cho chúng ta thực

hiện được nhiều ý tưởng hơn trong việc tìm kiếm. Đồng thời kết quả tập ảnh

trả về sẽ chính xác hơn cũng như không bị thiếu xót trong quá trình tìm kiếm

(Precision and Recall). Ví dụ, người dùng chỉ muốn tìm một bông hồng nhỏ ở

ngay tại vị trí nào đó trong ảnh thì khi tìm kiếm theo tính phân bố toàn cục thì

có thể có ảnh cũng có bông hồng nhỏ nhưng khác nhau về vị trí hay là cũng có

bông hồng tại vị trí đó nhưng chỉ giống nhau về màu hồng không đủ để 2 ảnh

giống nhau theo yêu cầu về độ giống nhau đưa ra, nên kết quả sẽ không có

bông hồng này. Do đó, để giải quyết vấn đề này ta nghĩ ngay đến việc tìm kiếm

ảnh dựa vào tính phân bố cục bộ. Có 2 phương pháp được đề cử trong việc tìm

kiếm này là: tìm kiếm với việc chia lưới, và tìm kiếm với việc vẽ vùng trên ảnh

để tìm kiếm.

3.4.2.1 Tìm kiếm xét đến tính cục bộ với việc chia lưới tìm kiếm

Với ý tưởng chia ảnh thành nhiều khối nhỏ sẽ giúp cho chúng ta có

thể đưa các đặc trưng tìm kiếm khác nhau vào lưới.Với ý tưởng này người

dùng có thể thực hiện được nhiều ý tưởng khác nhau như: thành phố lúc

hoàng hôn, Vịnh Hạ Long lúc trời mưa…

Ví dụ minh họa tìm kiếm xét đến tình phân bố cục bộ với việc chia lứoi:

Ví dụ 1:

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 77:Hình minh họa tìm kiếm chia lưới-1

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

Khi đó người dùng chỉ muốn tìm những tấm ảnh có đặc trưng

màu là hoa màu tím ngay tại vị trí chính giữa giống như ảnh truy vấn

này khi đó ngừơi dùng có thể chia thành lưới 3x3 như sau:

Hình 78: Minh họa ảnh được chia lưới 3x3 để tìm kiếm-1

Lúc này người dùng chỉ cần chọn block thứ 4 tìm kiếm theo

đặc trưng màu là kết quả có thể giải quyết. Kết quả sẽ cho ra những

tấm ảnh chỉ có màu hoa tím ở chính giữa còn các block khác trên

ảnh không quan tâm.

Ví dụ 2:

Hình 79: Hình minh họa tìm kiếm chia lưới-2

Người dùng muốn tìm kiếm phần trên là nhà, phần dưới là cỏ

Nguyễn Bá Công – Nguyễn Hữu Đức

thì người dùng có thể chia thành lưới 2x1 như sau:

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

Hình 80: Minh hoạ chia lưới 1x2 để tìm kiếm-2

Khi đó người dùng chỉ cần chọn block 0 là tìm theo đặc trưng

lược đố hệ số góc (Edge Direction Histogram) và chọn block 1 là

tìm theo đặc trưng màu. Khi đó kết quả sẽ là những tấm ảnh có phần

trên có hình dáng giống như hình dáng của ngôi nhà đó và phần dưới

có màu là màu bãi cỏ như trong hình.

Ví dụ 3:

Hình 81: Ảnh minh họa tìm kiếm chia lưới-3

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 82: Minh hoạc chia lưới 1x3 cho việc tìm kiếm trên ảnh-3

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

Với việc chia lưới trên người dùng có thể thực hiện ý tưởng

tìm kiếm cảnh thành phố lúc hoàn hôn như sau: người dùng chọn

block 0 tìm kiếm theo đặc trưng màu, block 1 và block 2 tìm kiếm

theo đặc trưng lược đồ hệ số góc.

Nói cách khác tìm kiếm chia lưới sẽ giúp cho ngừơi dùng có thể dễ

dàng tìm kiếm hơn theo ý mình muốn.

3.4.2.2 Tìm kiếm xét đến tính cục bộ với việc vẽ

Việc tìm kiếm chia lưới đã có thể giúp nâng cao hiệu quả tìm kiếm

rất nhiều, nhưng đôi khi việc chia lưới vẫn không phủ hết các đối tượng

cần tìm. Do đó, tìm kiếm với việc cho người dùng vẽ đối tượng cần tìm

trên ảnh sẽ giúp hiệu quả hơn và chính xác hơn trong việc tím kiếm.

Xét ví dụ trên: giả sử ảnh truy vấn ban đầu như sau

Hình 83: Ảnh minh họa tìm kiếm vẽ

Hình 84: Chia lưới 3x3 trên ảnh tìm kiếm

Giả sử đối tượng cần tìm là nguyên một bông hoa ngay chính giữa

Nguyễn Bá Công – Nguyễn Hữu Đức

nhưng có chia lưới như thế nào đi nữa thì vẫn không phủ vừa hết nguyên

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

bông hoa trong cùng một block. Do đó, việc tìm kiếm cho phép người dùng

vẽ trên ảnh sẽ khắc phục tình trạng này, làm cho nhu cầu tìm kiếm cao hơn,

hiệu quả hơn. Với việc vẽ vùng ta được:

Hình 85: Minh họa vẽ hình trên ảnh tìm kiếm

Lúc này người dùng có thể chọn các đặc trưng tìm kiếm theo nhu

cầu của người mình trên khung hình chữ nhật đã vẽ.

Nói tóm lại, tìm kiếm với việc vẽ trên ảnh sẽ giúp cho ta có thể tìm

kiếm một đối tượng nào đó bất kỳ trong ảnh mà người dùng muốn bằng

cách vẽ bao quanh đối tượng đó bằng một hình chữ nhật.

Ví dụ minh hoạ 1:

Hình 86: Hỉnh minh họa vẽ trên ảnh tìm kiếm Khi người dùng muốn tìm những ảnh có bông hoa màu hồng ở chính

giữa thì có thể vẽ vùng như ở trên.

Nguyễn Bá Công – Nguyễn Hữu Đức

Ví dụ minh họa 2:

Chương 3:Truy tìm ảnh dựa vào đặc trưng cấp thấp

Hình 87: Hình minh hoa vẽ tìm kiếm

Với cách vẽ trên người dùng có thể thực hiện tìm kiếm những con sư

tử tại vị trí khung chữ nhật đã vẽ.

Ví dụ 3:

Hình 88: Hình minh họa vẽ tìm kiếm Cũng giống như tìm kiếm dựa trên tính phân bố toàn cục việc tìm

kiếm này cũng có thể cho người dùng kết hợp các đặc trưng lại với nhau

theo toán tử BOOL và theo trọng số.

Các đặc trưng được sử dụng cho việc dựa vào tính phân bố cục bộ

cũng giống như các đặc trưng tìm kiếm dựa trên tính phân bố toàn cục. Các

đặc trưng đó là: Lược đồ màu, Vector liên kết màu, Lược đồ hệ số góc,

Nguyễn Bá Công – Nguyễn Hữu Đức

Vector liên kết hệ số góc, lược đồ tương quan màu.

Chương 4:Truy tìm ảnh dựa vào đặc trưng cấp cao

Chương 4 TRUY TÌM ẢNH DỰA VÀO ĐẶC TRƯNG

CẤP CAO

Nguyễn Bá Công – Nguyễn Hữu Đức

Chương 4:Truy tìm ảnh dựa vào đặc trưng cấp cao

Đặc trưng cấp cao của ảnh ở đây là vùng, hay còn gọi là vần của ảnh.

4.1. Bài toán phân đoạn ảnh

Đối với dạng bài toán này có nhiều cách để giải quyết, như có thể áp dụng

giải thuật người láng giềng gần nhất (K-Min) để tìm ra những điểm mầm của

vùng, rồi từ đó lan ra tìm vùng tương ứng. Nhưng ở đây chúng em sử dụng giải

thuật phân lớp phân cấp HAC để phân đoạn ảnh. Với việc dùng giải thuật này ta

không cần xác định trước số vùng trong ảnh, và ta có thể tiến hành phân vùng từ

thô cho tới mịn dựa trên cây phân cấp thu được.

Mục đích của việc phân đoạn ảnh là tách ảnh ra thành các vùng, giúp cho

người dùng có thể mô phỏng dữ liệu đầu vào dễ dàng hơn, cũng như giúp cho việc

tìm kiếm đạt được hiệu quả cao.

Một bài toán phân đoạn ảnh thường qua hai khâu chính: khâu chọn đặc

trưng để phân đoạn, và khâu phân đoạn ảnh.

4.1.1 Chọn đặc trưng để phân đoạn ảnh

Các đặc trưng được sử dụng cho việc phân đọan ảnh là: Đặc trưng màu,

Đặc trưng vân và đặc trưng vị trí (xét đến tính liên thông).

Mỗi ảnh A được chia nhỏ thành các khối con Ki kích thước 4x4 (điểm

ảnh). Các đặc trưng trong mỗi khối con gồm 3 đặc trưng: màu, 3 đặc trưng về

vân., và vị trí của khối con Ki trong ảnh.

Đặc trưng màu:

Chọn sử dụng hệ màu HSI(Hue , Saturation , Intensity) cùng với

việc định lượng không gian màu gồm 12H , 3S , 3I. Mỗi khối con gồm 3

iH ][

iS ][

iI ][

đặc trưng màu: M1 , M2 , M3:

∑

1 16

, ,

trong đó H[i] , S[i] , I[i] là thành phần H, S, I của điểm ảnh thứ i.

Đặc trưng vân:

Nguyễn Bá Công – Nguyễn Hữu Đức

Mỗi khối con gồm 3 đặc trưng vân: V1 , V2 , V3.

Chương 4:Truy tìm ảnh dựa vào đặc trưng cấp cao

Thực hiện phép biến đổi Wavelet[1] trên khối con 4x4 đối với

thành phần màu I(hoặc trên ảnh độ xám ) , ta được 3 khối kích thước

2x2 tương ứng với khối qua bộ lọc thông thấp của cao (HL) , bộ lọc

thông cao của thấp(LH) , bộ lọc thông cao của cao (HH).

Gọi 4 hệ số của khối qua bộ lọc thông thấp của cao (HL) là:

{hl0,hl1,hl2,hl3}

2/1

ihl

V 1

1 ⎛ = ∑ ⎜ 4 ⎝

⎞ ⎟ ⎠

Đặc trưng V1 trong khối HL:

Gọi 4 hệ số của khối qua bộ lọc thông cao của thấp (LH) là:

{lh0,lh1,lh2,lh3},

2/1

ilh

1 ⎛ = ∑ ⎜ 4 ⎝

⎞ ⎟ ⎠

Đặc trưng V2 trong khối LH:

Gọi 4 hệ số của khối qua bộ lọc thông thấp của cao (HH) là:

{hh0,hh1,hh2,hh3}

2/1

ihh

V 3

1 ⎛ = ∑ ⎜ 4 ⎝

⎞ ⎟ ⎠

Đặc trưng V3 trong khối HH:

Đặc trưng vị trí:

Mỗi khối con i có tâm Ci toạ độ xi,yi .

Việc đưa thêm đặc trưng vị trí giúp phân đoạn được các vùng có

tính liên thông.

Chuẩn hoá các đặc trưng màu , vân , vị trí:

Gọi ƒi là vector đặc trưng của khối con Ki của ảnh ,

ƒi={Mi1,Mi2,Mi3,Vi1,Vi2,Vi3,xi,yi}

Mij , j Є[1..3] là các đặc trưng màu đã được chuẩn hoá của khối

Nguyễn Bá Công – Nguyễn Hữu Đức

con Ki,

Chương 4:Truy tìm ảnh dựa vào đặc trưng cấp cao

Vij , j Є[1..3] là các đặc trưng vân đã được chuẩn hoá của khối

con Ki ,xi , yi là các đặc trưng vị trí đã được chuẩn hoá của khối con Ki.

2/12

(

)

−

( MM −

)

(

)

KKd i

w m

w v

y i

( V il

( ( xw i t

)

∑

1 =

Độ đo đối sánh giữa các khối con:

Trong đó:

Mil là đặc trưng thứ l của khối Ki,

Vil là đặc trưng vân thứ l của khối Ki,

xi,yi là toạ độ trọng tâm của khối Ki,

wm , w v, wi là trọng số xác định mức độ quan trọng của

đặc trưng màu , vân và vị trí

4.1.2 Phân đoạn ảnh

Phân đoạn ảnh thực chất là phân lớp các điểm ảnh. Chúng em chọn

phương pháp phân lớp phân cấp [5] vì nó có khả năng tổ chức vùng theo cấu

trúc phân cấp.

Thuật toán phân đoạn ảnh:

Giả sử A={Ki,i=1,2,…,N}, với A là ảnh, Ki là các khối con thứ i

của ảnh.

Thuật toán chia ra làm 3 giai đoạn chính: giai đoạn khởi động, giai

đoạn phân lớp và giai đoạn rút gọn cây phân cấp.

Giai đoạn khởi động:

Bước 1: Tạo phân cấp R0={Ki, i=1,2,…,N} với Ci=Ki

Bước 2: P0=P(K)

Trong đó P(K) là ma trận kích thước NxN với P(i,j)=d(Ki,Kj).

Nguyễn Bá Công – Nguyễn Hữu Đức

Bước 3: t=0

Chương 4:Truy tìm ảnh dựa vào đặc trưng cấp cao

Giai đoạn phân lớp

Bước 1: t=t+1

r ≠ s

Bước 2: Chọn cặp Ci, Cj sao cho d(Ci,Cj)=mind(Cr,Cs) ,r ,s =1 ,2

,…,N,

Bước 3: Kết nạp Ci, Cj vào lớp Cq và tạo 1 phân cấp Rt

Rt=(Rt-1 – {Ci,Cj}) {C∪ q}

Bước 4: Cập nhật P(t) từ P(t-1) bằng 2 bước

Xoá các dòng và cột tương ứng với 2 lớp vừa được kết nạp

thêm dòng mới và cột mới chứa khoảng cách giữa lớp mới mới tạo

và các lớp cũ

Bước 5: Lặp lại bước bước 1 khi nào các Ki đều chưa cùng thuộc

một lớp.

Giai đoạn rút gọn cây:

Sau khi xây dựng câp phân cấp xong, chúng ta cần thực hiện

thuật tóan rút gọn cây như sau:

Node P_l ←{ dmin(nl,nr), dmax(nl,nr)

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 89: Hình minh họa cây phân cấp

Chương 4:Truy tìm ảnh dựa vào đặc trưng cấp cao

Node n_l ←{dmin(cl,cr), dmax(cl,cr)

,(min{

∀

),(min ba d

l ba

, blal εε ∀ a

max{

∀

),(max ba d

,( ld a

l b

, blal εε ∀ a

c min

),( pc

min

p − min c d min

c max

pc ),(

max

p max d

− c max

4.1.3 Các ví dụ về bài toán phân đoạn ảnh

Ví dụ 1: Áp dụng thuật toán HAC vào việc phân đọan ảnh chúng em thu

được những kết quả như sau:

Nguyễn Bá Công – Nguyễn Hữu Đức

Hình 90: Minh họa áp dụng giải thuật HAC vào phân đoạn ảnh-1

Chương 4:Truy tìm ảnh dựa vào đặc trưng cấp cao

Hình 91: Minh họa áp dụng giải thuật HAC vào phân đoạn ảnh-2

Hình 92: Minh hoạ dùng thuật toán HAC phân đoạn ảnh-3

4.2. Vùng và đặc trưng vùng

Ảnh gồm tập hợp các vùng hay còn gọi là vần. Đây là đặc trưng cấp cao của

ảnh. Với đặc trưng vùng sẽ giúp cho chúng ta có thể giải quyết được một vấn đề

lớn đang cản trở bước phát triển việc truy tìm ảnh dựa vào nội dung là dữ liệu

nhập chưa được mô phỏng gần gũi hơn với suy nghĩ của con người và ảnh tìm

được có thể mang nội dung ngữ nghĩa rất khác so với ảnh truy vấn.

Với đặc trưng vùng con người có thể tiến thêm một bước trong việc truy tìm

ảnh dựa vào nội dung là tìm kiếm dựa vào ngữ nghĩa. Với việc áp dụng mô hình

học vào bài toán vùng. Khi đó, mỗi vùng sẽ mang một ngữ nghĩa, từ đó làm cho

Nguyễn Bá Công – Nguyễn Hữu Đức

dữ liệu đầu vào được mô phỏng gần gũi với con người hơn.

Chương 4:Truy tìm ảnh dựa vào đặc trưng cấp cao

Ví dụ minh họa về vùng của ảnh:

Hình 93: Minh họa vùng của ảnh

(

)

(

)

−

CCd i

hdw m C

h C

Vw | C v

V C

w vt

VT C

L 1

−

w dt

DT C

com

Com C

Độ đo đối sánh vùng

)

(

)( k

(

))(

)( l

( al ))

−

( hd C

h C

∑∑

1 =

)(k

trong đó:

h iC

là phần tử thứ k của lược đồ màu của vùng ci, N số ô

2/1

cos

−

(

)

(

SH − k

1 5

sin

(

)

) SH − k

⎤ ⎥ ⎥ ⎦

⎡ ⎢ ⎢ ⎣

màu của lược đồ màu ,

wwwww vt

com

là các trọng số xác định mức độ quan

Nguyễn Bá Công – Nguyễn Hữu Đức

100

trọng của các đặc trưng màu , vân ,vùng

Chương 4:Truy tìm ảnh dựa vào đặc trưng cấp cao

4.3. Áp dụng giải thuật phân lớp phân cấp vào bài toán

phân lớp vùng

Sau khi phân đoạn ảnh thành các vùng thì các đặc trưng về vùng chính là

các đặc trưn cấp cao và đóng vai trò rất quan trọng giúp chúng ta lấp một phần hố

ngăn cách giữa các đặc trưng cấp thấp và ngữ nghĩa của ảnh.

Các đặc trưng về vùng được chọn để phân lớp vùng gồm: đặc trưng màu,

vân, và hình dáng (diện tích, vị trí, tính Compact).

(

)

(

)

−

CCd i

hdw m C

h C

Vw | C v

V C

w vt

VT C

L 1

−

w dt

DT C

com

Com C

Độ đo đối sánh giữa 2 vùng:

)

(

)( k

(

))(

)( l

( al ))

−

( hd C

h C

∑∑

1 =

)(k

trong đó:

h iC

là phần tử thứ k của lược đồ màu của vùng ci, N số ô

2/1

cos

−

(

)

(

SH − k

1 5

sin

(

)

) SH − k

⎤ ⎥ ⎥ ⎦

⎡ ⎢ ⎢ ⎣

màu của lược đồ màu ,

V: đại diện đặc trưng vân của vùng

VT: vị trí của vùng

DT: diện tích của vùng

Com: tính Compact của vùng.

wwwww vt

com

là các trọng số xác định mức độ quan

trọng của các đặc trưng màu , vân ,vùng

Chúng em thay việc phân lớp ảnh về bài toán phân lớp các vùng cấu thành

Nguyễn Bá Công – Nguyễn Hữu Đức

101

nên ảnh.Chúng em chọn phương pháp phân lớp phân cấp [5].

Chương 4:Truy tìm ảnh dựa vào đặc trưng cấp cao

iCDT

][ j

Chúng em cải tiến việc phân lớp các vùng theo đặc trưng hình học ( )

iCCom

h iC

rồi đến đặc trưng compact ( ), đặc trưng màu ( ),j=1,2,…113) và cuối

iCV

cùng là đặc trưng vân ( ).

Mỗi lớp vùng sẽ được trích chọn một phần tử đại diện .

Việc phân lớp này nhằm chuẩn bị cho giai đoạn truy tìm. Nó giúp rút ngắn

thời gian tìm kiếm nhờ vào việc tránh phải duyệt toàn bộ cơ sở dữ liệu vùng với

độ đo đối sánh trên toàn bộ các đặc trưng của vùng.

Ví dụ minh họa phân lớp vùng:

Chúng em minh họa cơ sở dự liệu gồm 5 tấm ảnh và kết quả thu

được như sau:

Nguyễn Bá Công – Nguyễn Hữu Đức

102

Hình 94: Cơ sở dữ liệu dùng để phân vùng ảnh

Chương 4:Truy tìm ảnh dựa vào đặc trưng cấp cao

Hình 95: Các vùng của tập ảnh được tách ra bằng giải thuật HAC

Hình 96: Cây phân cấp của tập vùng trên

Nguyễn Bá Công – Nguyễn Hữu Đức

103

Hình 97: Nhóm các vùng giống nhau

Chương 4:Truy tìm ảnh dựa vào đặc trưng cấp cao

Ví dụ 2:

Dữ liệu ảnh phân vùng:

Hình 98: Cơ sở dữ liệu ảnh phân vùng

Hình 99: Các vùng của tập dữ liệu ảnh sau khi được tách bằng giải thuật HAC

Nguyễn Bá Công – Nguyễn Hữu Đức

104

Hình 100: Cây phân cấp của tập vùng trên

Chương 4:Truy tìm ảnh dựa vào đặc trưng cấp cao

Hình 101: Nhóm các vùng giống nhau

4.4. Tạo chỉ mục tìm kiếm

Quá trình phân đoạn vùng của ảnh đòi hỏi phải tốn nhiều thời gian, do đó

khi tìm kiếm trên một cơ sở dữ liệu ảnh lớn thì vấn đề thời gian là một trong

những vấn đề gây khó khăn cho bài toán, do đó cần phải có biện pháp tổ chức cơ

sở dữ liệu hiệu quả giúp cho việc tìm kiếm được nhanh hơn, hiệu quả hơn.

Giải thuật HAC cũng được chúng em áp dụng vào việc phân lớp vùng, nghĩa

là xây dựng cây với các nút lá là tập các vùng trong cơ sở dữ liệu. Việc tạo cây

phân cấp với các nút đuợc gôm lại thành từng nhóm, mỗi nhóm có một phần tử

đại diện giúp cho việc truy tìm có thể loại bỏ được những nhóm có vùng không

giống với vùng truy vấn một cách nhanh chóng. Từ đó việc truy tìm sẽ hiệu quả

hơn về thời gian truy xuất. Và như vậy có thể coi là một chỉ mục để truy tìm ảnh

hiệu quả.

4.5. Các chiến lược truy tìm theo đặc trưng cấp cao

Trong việc phát triển truy tìm ảnh dựa vào nội dung, một vấn đề lớn đang

cản trở bước phát triển này là dữ liệu nhận cần phải mô phỏng gần gũi hơn với suy

nghĩ của con người và ảnh tìm được không được mang nội dung ngữ nghĩa quá

khác so với ảnh truy vấn .

Để giải quyết vấn đề này, chúng em tiếp cận theo hướng cho phép dữ liệu

nhập bao gồm các mẫu chính cấu thành nên ảnh truy vấn, và cơ sở dữ liệu ảnh

được phân đoạn và phân lớp theo các mẫu cấu thành, được gọi là vần của ảnh .

Nguyễn Bá Công – Nguyễn Hữu Đức

105

Cách tiếp cận này giúp giải quyết được bốn vấn đề sau:

Chương 4:Truy tìm ảnh dựa vào đặc trưng cấp cao

Người dùng chưa có ý niệm rõ lắm về tấm ảnh cần tìm mà chỉ

có một số yêu cầu nào đó về các vần cấu thành nên nó hoặc họ

chỉ cần tìm các ảnh tương tự với các vần chính của ảnh truy

vấn chứ không cần sự tương tự toàn cục .

Các khó khăn trong bài toán phân lớp ảnh với nội dung phong

phú. Qui bài toán phân lớp ảnh về bài toán phân lớp các vần

cấu thành nên ảnh .

Tránh truy tìm tuần tự trên cơ sở dữ liệu lớn. Các ảnh được xét

chỉ là nhóm các ảnh có các vần thuộc lớp các vần truy vấn .

Tăng độ chính xác và độ trung thực trong kết quả truy tìm .

Kết quả thực nghiệm cho thấy cách tiếp cận trên mang lại hiệu quả truy tìm

tốt hơn so với cách tiếp cận truyền thống chỉ dựa trên các đặc trưng cấp thấp của

toàn ảnh và truy tìm có tính chất tuần tự .

Khi sử dụng các hệ truy tìm ảnh dựa vào nội dung, con người luôn mong

muốn có thể thể hiện được dễ dàng, tương đối đầy đủ nội dung mà họ muốn tìm

kiếm. Một cách truyền thống là họ chọn một ảnh truy vấn phù hợp với yêu cầu,

tuy nhiên họ có thể không có sẵn bức ảnh truy vấn mà chỉ có một số ý niệm nào đó

về bức ảnh (ví dụ họ cần tìm các bức ảnh có dáng vẻ như sau: cỏ non xanh tận

chân trời, cành lê trắng điểm một vài bông hoa), hoặc nhiều khi có được bức ảnh

truy vấn nhưng họ chỉ muốn tìm các ảnh giống một số đối tượng nào đó trong ảnh.

Vấn đề này được giải quyết bằng việc cho người dùng có thể tìm kiếm theo đối

tượng hay còn gọi là vần của ảnh.

Trong quá trình tìm ảnh, hệ thống của chúng em được tổ chức thành 3 giai

đoạn chính: Giai đoạn nhập dữ liệu, giai đoạn truy tìm và giai đoạn kết xuất .

4.5.1 Giai đoạn nhập dữ liệu

Trong giai đoạn này ngừơi sử dụng có thể nhập dữ liệu bằng 2 cách:

Nguyễn Bá Công – Nguyễn Hữu Đức

106

Cách thứ nhất:

Chương 4:Truy tìm ảnh dựa vào đặc trưng cấp cao

Người dùng chọn một số ảnh truy vấn tuỳ ý, sau đó hệ thống tự động

n đoạn các ảnh này, cuối cùng người dùng chọn các vùng cần truy sẽ phâ

tìm và các vùng không cần tìm trong các ảnh này theo lý luận:

D (Sel(Ci) OR Sel(Cj)) AND (Sel(Ck)OR Sel(Cl)) AN

NOT(S el(Cm)OR Sel(Cn))

Trong đó: Sel(Ci): C i được chọn.

dụ minh họa: Các ví

Ví dụ 1:

Hình 102: ảnh minh họa tìm kiếm theo vùng

người dùng có thể chọn một trong 3 vùng của ả Khi đó nh để

m. Ngòai ra người dùng có thể thực hiện câu truy vấn như tìm kiế

sau: (1 AND 2) nghĩa là tìm những ảnh có cả con thú và cỏ hay thực

hiện câu truy vấn (1 NOT 2) nghĩa là có con thú nhưng không có cỏ.

Nguyễn Bá Công – Nguyễn Hữu Đức

107

Ví dụ 2:

Chương 4:Truy tìm ảnh dựa vào đặc trưng cấp cao

Hình 103: Hình minh họa tìm kiếm theo vùng, đối tượng

Cũng như trên người dùng có thể tìm kiếm kết hợp các vùng

lại với nhau. Ví dụ như ngừơi dùng có thể tìm kiếm những tấm ảnh

có dạng “ con sư tử đứng ngòai bầu trời có mây” thì người dùng có

thể thực hiện câu truy vấn như sau: (2 AND 3) hoặc (2 AND 3 AND

Cách thứ hai:

Người dùng chọn các mẫu truy vấn đã có sẵn trong cơ sở dữ liệu ảnh

(trong bước phân lớp vùng) theo lý luận:

(Sel(Ci) OR Sel(Cj)) AND (Sel(Ck)OR Sel(Cl)) AND NOT(Sel(Cm)OR Sel(Cn))

Cụ thể là trong tập cơ sở dữ liệu ảnh ban đầu đã phân thành các

vùng, người dùng muốn chọn vùng nào để tìm kiếm thì chỉ cần người dùng

chọn vùng đó để tìm kiếm. Ví dụ như người dùng muốn tìm kiếm những

tấm ảnh có dạng sau “ Cỏ non xanh tận chân trời, cành lê trắng điểm một

vài bông hoa” thì người dùng có thể chọn các vùng sau: “ cỏ màu xanh

“,”màu bầu trời”, ”cành lê có những bông hoa màu trắng” .

Nguyễn Bá Công – Nguyễn Hữu Đức

108

Các ví dụ minh họa:

Chương 4:Truy tìm ảnh dựa vào đặc trưng cấp cao

Ví dụ 1:

Người dùng muốn tìm kiếm ảnh như sau: “Cỏ non xanh tận

chân trời, cành lê trắng điểm một vài bông hoa” thì người dùng có

thể chọn các vùng sau:

Hình 104: Câu truy vấn “Bầu trời” AND “ Cỏ” AND “ Hoa màu trắng”

Ví dụ 2:

Hoặc là người dùng có ý niệm tìm những ảnh có dạng

sau:”Tìm những ảnh có hoa màu vàng nhưng không có lá màu xanh

bên cạnh”. Yêu cầu sẽ được giải quyết như sau:

Hình 105: Câu truy vấn “Hoa màu vàng” AND NOT “ Lá màu xanh”

Trong cả 2 cách đều có thể chọn mức độ quan trọng của các

(

)

(

)

−

CCd i

h C

Vw | v C

V C

hdw C m i

L 1

Nguyễn Bá Công – Nguyễn Hữu Đức

109

đặc trưng dựa vào các trọng số tương ứng trong độ đo đối sánh vùng:

Chương 4:Truy tìm ảnh dựa vào đặc trưng cấp cao

−

w vt

VT C

w dt

DT C

com

Com C

L 2

L 1

4.5.2 Giai đoạn truy tìm

Với mẫu truy vấn Cq, so sánh với các mẫu đại diện trong cây phân lớp

vùng để lọc bớt các lớp không tương thích với mẫu và chọn được mẫu đại diện

thích hợp với mẫu truy vấn .

Gọi mẫu đại diện khớp với mẫu truy vấn là Cr, lớp đó là Br .

Gọi tập các ảnh có ít nhất một vùng thuộc về lớp Br là TA (Br).

Tập ảnh ứng với câu truy vấn:

(Sel(Ci) OR Sel(Cj)) AND (Sel(Ck)OR Sel(Cl)) AND NOT(Sel(Cm) OR Sel(Cn))

∪

sẽ tương ứng:

∩ (TA(Bk)

Bl))\ (TA(Bm)

n))

TA(Bj)) TA(B TA(B (TA(Bi)

Với cách làm trên,sẽ đạt độ chính xác cao,mức độ tìm sót thấp,đồng

thời tốc độ truy tìm khá nhanh vì không phải duyệt qua toàn bộ cơ sở dữ

liệu ảnh và sử dụng toàn bộ các đặc trưng trong đối xứng ảnh.

4.5.3 Giai đoạn sắp hạng (RANKING)

Tập ảnh kết quả tìm được sẽ đươc sắp hạng theo độ tương tự với ảnh

truy vấn, giúp cho người dùng tìm được ảnh cần tìm nhanh chóng hơn. Độ

tương tự giữa ảnh truy vấn và ảnh trong tập kết quả được xác định như sau:

Giả sử xét 2 ảnh Ai, Aj:

Ai={ Ci0,Ci1, …,CiN-1 }, với Cik, kє[0..N-1] là các vùng của ảnh Ai

Aj={ Cj0,Cj1, …,CjM-1 }, với Cjl, lє[0..N-1] là các vùng của ảnh Aj

Độ đo tương tự giữa các ảnh dựa vào độ đo tương tự giữa các vùng:

d(Ai,Aj)=min{d(Cik,Cjl),kє[0,N],lє[0,M]}

Tuy nhiên độ tương tự trên không phản ánh được độ tương tự thật sự

Nguyễn Bá Công – Nguyễn Hữu Đức

110

giữa các ảnh vì có thể tồn tại 2 vùng rất giống nhau giữa 2 ảnh tuy nhiên lại

Chương 4:Truy tìm ảnh dựa vào đặc trưng cấp cao

có sự khác biệt rất lớn ở những vùng còn lại. Vì vậy cần đưa ra một độ đo

tương tự thể hiện được sự tham gia của các vùng trong cả 2 ảnh .

Sự tương tự giữa 2 ảnh càng cao khi có sự tương tự cao giữa các

− 1

)

( ACdw

( ACdw i

∑

(

)

AAd i

vùng trong 2 ảnh.

N là số vùng của ảnh Ai , M là số vùng của ảnh Aj ,

d(Cik,Aj)=min{d(Cik,Cjl),l=0..M-1, là khoảng cách từ vùng Cik

của ảnh Ai đến ảnh Aj,

d(Cjl,Ai)=min{d(Cjl,Cik),k=0..N-1, là khoảng cách từ vùng Cjl

của ảnh Aj đến ảnh Ai,

wik=Nik/NKi, Nik là số khối trong vùng Cik, NKi số khối con

của ảnh Ai

wjl=Njl/NKj, Njl là số khối trong vùng Cjl, NKj số khối con của

ảnh Aj

wik và wjl thể hiện vai trò quan trọng của vùng có diện tích

lớn trong độ đo đối sánh .

Cách tiếp cận của chúng em là dùng đặc trưng cấp cao là vùng mà

chúng em còn gọi là vần ảnh (cùng với đặc trưng cấp thấp như màu, vân,

hình dáng) để bắc cầu nối giữa đặc trưng cấp thấp và ngữ nghĩa ảnh. Chúng

em xem ảnh gồm các vùng cũng như một đoạn văn gồm các từ. Vì vậy

trong việc truy tìm cũng như trong việc phân lớp, đơn vị phải xử lý là các

vùng của ảnh .

Điều này dẫn đến một khả năng truy tìm mới là dựa vào câu truy vấn

dạng ngôn ngữ, liên kết giữa các vùng đại diện theo một lý luận để truy tìm

Nguyễn Bá Công – Nguyễn Hữu Đức

111

ảnh .

Chương 5:Truy tìm ảnh dựa vào ngữ nghĩa

Chương 5 TRUY TÌM ẢNH DỰA VÀO NGỮ NGHĨA

Nguyễn Bá Công – Nguyễn Hữu Đức

112

Chương 5:Truy tìm ảnh dựa vào ngữ nghĩa

Cách truy vấn này là dùng đặc trưng cấp cao là vùng mà chúng em còn gọi

là vần ảnh (cùng với đặc trưng cấp thấp như màu, vân, hình dáng) để bắt cầu nối

giữa đặc trưng cấp thấp và ngữ nghĩa ảnh. Chúng em xem ảnh gồm các vùng cũng

như một đoạn văn gồm các từ. Vì vậy trong việc truy tìm cũng như trong việc

phân lớp, đơn vị phải xử lý là các vùng của ảnh.

Điều này dẫn đến một khả năng truy tìm mới là dựa vào câu truy vấn dạng

ngôn ngữ, liên kết giữa các vùng đại diện theo một lý luận để truy tìm ảnh.

Trong từng nhóm ảnh đã được phân loại bằng tay, trích ra các vùng đặc thù

cho nhóm ảnh để khi truy vấn ta có thể diễn dịch từ ngôn ngữ sang vần ảnh. Ví dụ

như tìm cảnh bãi biển lúc bình minh, thì liên kết nhóm từ bãi biển với vùng đại

diện cho bãi biển và liên kết nhóm từ bình minh với vùng đại diện cho bình minh

Đây có thể xem là hướng truy tìm ảnh theo phương pháp mới. Với phương

pháp này ta có thể truy tìm ảnh chỉ bằng những câu chữ mà không cần hình ảnh có

sẵn. Việc tìm kiếm này đem đến sự tiện dụng cho người dùng.

Ví dụ minh họa:

Đầu tiên người dùng vào cơ sở dữ liệu gán nhãn cho tất cả các vùng

sau khi được phân lớp ở bước tìm kiếm theo vùng. Ứng với mỗi vùng,

người dùng gán nhãn tương ứng cho vùng đó. Khi tìm kiếm chỉ cần dùng

ngôn ngữ để truy tìm.

Nguyễn Bá Công – Nguyễn Hữu Đức

113

Sau đây là ví dụ minh họa các vùng đã được gán nhãn:

Chương 5:Truy tìm ảnh dựa vào ngữ nghĩa

Hình 106: Các vùng đã được gán nhãn Sau khi người dùng gán nhãn xong, tiếp theo là người dùng có thể

thực hiện câu truy vấn của mình. Ví dụ như người dùng có thể thực hiệc các

câu truy vấn sau:

”Hoa màu tím” sẽ cho kết quả những ảnh có bông hoa có màu tím.

Nguyễn Bá Công – Nguyễn Hữu Đức

114

Hình 107: Kết quả câu truy vấn “Hoa màu tím”

Chương 5:Truy tìm ảnh dựa vào ngữ nghĩa

+”Hoa mai” sẽ cho kết quả những ảnh có hoa

Hình 108: Kết quả câu truy vấn “ Hoa mai”

+”Cỏ” AND “Nhà” sẽ cho kết quả những ảnh có nhà và cỏ

Hình 109: Kết quả câu truy vấn “ Cỏ” và “ Nhà”

Nguyễn Bá Công – Nguyễn Hữu Đức

115

+”Sư tử” và “bầu trời” sẽ cho kết quả như sau:

Chương 5:Truy tìm ảnh dựa vào ngữ nghĩa

Nguyễn Bá Công – Nguyễn Hữu Đức

116

hình 110: Kết quả câu truy vấn “ Sư tử” AND “ Bầu trời”

Chương 6:Cài đặt và thử nghiệm

Chương 6 CÀI ĐẶT VÀ THỬ NGHIỆM

Nguyễn Bá Công – Nguyễn Hữu Đức

117

Chương 6:Cài đặt và thử nghiệm

6.1. Cài đặt

6.1.1 Chương trình

Chương trình được cài đặt trên môi trường Visual C++ 6.0. Chương

trình có sử dụng thư viện IJL15.dll để đọc tập tin JPG.

Chương trình được xây dựng theo mô hình sau:

Hình 111: Mô hình hệ thống

6.1.2 Các đặc trưng sử dụng cho chương trình

Các đặc trưng được sử dụng trong bài tóan là:

(cid:131) Đặc trưng màu sắc: Đặc trưng lược đồ màu, đặc trưng lược vector

liên kết màu, đặc trưng Correlogram.

(cid:131) Đặc trưng hình dáng: đặc trưng lược đồ hệ số góc, đặc trưng vector

Nguyễn Bá Công – Nguyễn Hữu Đức

118

liên kết hệ số góc.

Chương 6:Cài đặt và thử nghiệm

(cid:131) Về đặc trưng được sử dụng để phân vùng: Đặc trưng màu, đặc trưng

vân, đặc trưng vị trí.

6.1.3 Cơ sở dữ liệu

Việc xây dựng cây phân cấp các đặc trưng chúng em cài đúng theo thuật

tóan phân lớp phânc cấp (HAC). Kết quả thu được khá khả quan.

6.1.3.1 Cơ sở dữ liệu truy tìm theo đặc trưng cấp thấp

Cơ sở dữ liệu dùng chung cho đặc trưng cấp thấp gồm 5091 ảnh.

Đặc trưng Số nhóm (Cluster)

Lược đồ màu 724

Vector liên kết màu 747

Tương quan màu 626

Lược đồ hệ số góc 227

Vector liên kết hệ số góc 204

6.1.3.2 Cơ sở dữ liệu truy tìm theo đặc trưng cấp cao

Cơ sở dữ liệu ảnh phân vùng gồm 1494 ảnh, phân đoạn ảnh được

4156 vùng, và phân thành nhóm.

6.1.4 Chức năng truy tìm ảnh

Chương trình gồm 5 modul tìm kiếm riêng biệt:

(cid:131) Tìm kiếm dạng cơ bản: gồm các đặc trưng lược đồ màu (Histogram),

lược đồ hệ số góc (Edge Direction Histogram), Vector liên kết màu

(Color Coherence Vector), Vector liên kết hệ số góc(Edge Direcrion

Coherence Vector), Correlogram. Trong phần này người dùng có thể

kết hợp các đặc trưng này lại với nhau dùng tóan tử AND hay dùng

Nguyễn Bá Công – Nguyễn Hữu Đức

119

trọng số.

Chương 6:Cài đặt và thử nghiệm

(cid:131) Tìm kiếm có chia lưới hay cho người dùng vẽ hình chữ nhật trên ảnh

truy vấn để tìm kiếm. Vẫn sử dụng các đặc trưng cơ bản trên.

(cid:131) Tìm kiếm theo vùng, đối tượng: Từ ảnh truy vấn có sẵn, chương

trình tách thành các vùng (vần) cấu thành nên ảnh, tiếp theo người

dùng chọn các vùng cần thiết cho việc tìm kiếm.

(cid:131) Tìm kiếm theo vùng, đối tượng khi mà người dùng chưa có ý niệm

về tấm ảnh cần tìm kiếm

(cid:131) Người dùng chưa có ý niệm rõ lắm về tấm ảnh cần tìm mà chỉ có

một số yêu cầu nào đó về các vần cấu thành nên nó hoặc họ chỉ cần

tìm các ảnh tương tự với các vần chính của ảnh truy vấn chứ không

cần sự tương tự toàn cục.

(cid:131) Tìm kiếm dựa vào đánh nhãn các vùng: sau khi tách các vùng của

từng ảnh, chúng ta sẽ gán nhãn cho từng vùng. Sau đó, người dùng

dùng ngôn ngữ để truy vấn

6.2. Thử nghiệm

6.2.1 Tìm kiếm xét đến tính toàn cục

6.2.1.1 Tìm kiếm theo lược đồ màu

Ảnh truy vấn

Hình 112: Ảnh truy vấn theo lược đồ màu

Khi người dùng chọn tìm kiếm theo đặc trưng Histogram với độ

Nguyễn Bá Công – Nguyễn Hữu Đức

120

giống nhau giữa 2 ảnh là 55% sẽ cho kết quả như sau:

Chương 6:Cài đặt và thử nghiệm

Hình 113: Tập kết quả tìm kiếm theo lược đồ màu

Nhưng khi người dùng tăng độ giống nhau giữa 2 ảnh lên là 70% thì sẽ cho

kết quả như sau:

Hình 114: Kết quả tìm kiếm theo lược đồ màu với độ giống nhau 70%

6.2.1.2 Tìm kiếm theo lược đồ hệ số góc

Với ảnh truy vấn ban đầu như sau:

Nguyễn Bá Công – Nguyễn Hữu Đức

121

Hình 115:Ảnh truy vấn theo lược đồ hệ số góc

Chương 6:Cài đặt và thử nghiệm

Khi người dùng chọn độ giống nhau giữa 2 ảnh theo đặc trưng lược

đồ hệ số góc là 85% sẽ cho kết quả như sau:

Hình 116: Tập kết quả tìm kiếm theo lược đồ hệ số góc

Nhưng khi người dùng tăng độ giống nhau giữa 2 ảnh lên 89% thì

cho kết quả như sau:

Nguyễn Bá Công – Nguyễn Hữu Đức

122

Hình 117: Tập kết quả tìm theo lược đồ hệ số góc với độ giống nhau 89%

Chương 6:Cài đặt và thử nghiệm

6.2.1.3 Tìm kiếm theo vector liên kết màu Vẫn là ảnh tìm kiếm theo lược đồ màu

Hình 118: Ảnh truy tìm theo đặc trưng vector liên kết màu

Người dùng vẫn chọn độ giống nhau giữa 2 ảnh là 55% nhưng ở đây

theo đặc trưng Vector liên kết màu. Có kết quả như sau:

Hình 119:Tập kết quả tìm theo đặc trưng vector liên kết màu

Như vậy, ở đây cho kết quả chính xác hơn so với tìm theo đặc trưng

lược đồ màu.

Khi người dùng tìm theo đặc trưng này nhưng độ chính xác giữa 2

ảnh là 70% sẽ cho kết quả như sau:

Nguyễn Bá Công – Nguyễn Hữu Đức

123

Hình 120: Kết quả tìm kiếm với độ giống nhau 70%

Chương 6:Cài đặt và thử nghiệm

6.2.1.4 Tìm kiếm theo vector liên kết hệ số góc

Vẫn là ảnh tìm theo lược đồ hệ số góc nhưng người dùng không tìm

theo lược đồ hệ số góc mà tìm theo Vector liên kết hệ số góc. Ở đây độ

giống nhau là 79%

Hình 121: Ảnh truy vấn theo đặc trưng vector liên kết hệ số góc

Kết quả cho sẽ như sau:

Hình 122: Tập kết quả tìm theo đặc trưng liên kết hệ số góc

Ở đây, có thể cho kết quả chính xác hơn so với tìm theo lược đồ hệ

số góc mặc dù là theo độ giống nhau chỉ có 79%. Khi tăng độ giống nhau

Nguyễn Bá Công – Nguyễn Hữu Đức

124

lên 84% thì kết quả như sau:

Chương 6:Cài đặt và thử nghiệm

Hình 123: Tập kết quả tìm theo đặc trưng liên kết hệ số góc với độ

giống nhau 84%

6.2.1.5 Tìm kiếm theo AutoCorrelogram

Vẫn là ảnh tìm theo lược đồ màu, nhưng đây tìm theo đặc trưng

Correlogram cũng với độ giống nhau là 55%.

Ả nh truy vấn

Hình 124: Ảnh truy vấn Kết quả tìm được:

Nguyễn Bá Công – Nguyễn Hữu Đức

125

Hình 125: Tập kết quả thu được

Chương 6:Cài đặt và thử nghiệm

Nhưng khi người dùng tăng độ chính xác lên 70% thì kết quả như

Hình 126: Tập kết quả tìm được với độ giống nhau 70%

6.2.1.6 Tìm kiếm ảnh bằng việc kết hợp các đặc trưng với nhau

theo tóan tử AND

Vẫn là ảnh tìm theo lược đồ màu.

Hình 127: Ảnh truy vấn Nhưng ở đây tìm theo đặc trưng màu (Histogram) là 55% và

lược đồ hệ số góc (Edge Direction Histogram)là 75%. Kết quả cho

như sau:

Nguyễn Bá Công – Nguyễn Hữu Đức

126

Hình 128: Tập kết quả tìm được

Chương 6:Cài đặt và thử nghiệm

Khi người dùng tìm theo đặc trưng Correlogram 50% và

vector liên kết hệ số góc 65% thì kết quả như sau:

Hình 129: Tập kết quả tìm được

Khi người dùng tìm kiếm theo đặc trưng liên kết màu 50% và

đặc trưng liên kết hệ số góc 65% thì kết quả như sau:

Hình 130: Tập kết quả tìm được

Ví dụ khác:

Ảnh truy vấn ban đầu

Nguyễn Bá Công – Nguyễn Hữu Đức

127

Hình 131: Ảnh truy vấn

Chương 6:Cài đặt và thử nghiệm

Khi người dùng tìm kiếm theo đặc trưng histogram 47% và

đặc trưng lược đồ hệ số góc thì kết quả như sau:

Hình 132: Tập kết quả tìm được

6.2.1.7 Tìm kiếm ảnh bằng cách kết hợp các đặc trưng dùng

trọng số

V ẫn là ảnh trên

Hình 133: Ảnh truy vấn

Nhưng ở đây người dùng tìm kiếm theo lược đồ màu với độ ưu tiên

là 0.6 và đặc trưng lược đồ hệ số góc với độ ưu tiên là 0.4 và độ đo chung là

70% thì sẽ cho kết quả như sau:

Hình 134: Tập kết quả tìm được

Nguyễn Bá Công – Nguyễn Hữu Đức

128

Ví dụ khác:

Chương 6:Cài đặt và thử nghiệm

Ảnh truy vấn ban đầu

Hình 135: Ảnh truy vấn Khi tìm theo đặc trưng liên kết màu với độ ưu tiên là 45% và

đặc trưng liên kết hệ số góc với độ ưu tiên 55% và độ giống nhau

giữa 2 ảnh là 63% sẽ cho kết quả như sau:

Hình 136: Tập kết quả tìm được

6.2.2 Tìm kiếm dựa trên tính phân bố cục bộ

6.2.2.1 Tìm kiếm bằng cách chia lưới

Ví dụ 1: Ả nh truy vấn

Hình 137: Ảnh truy vấn tìm kiếm dựa trên tính phân bố cục bộ

Người dùng muốn tìm kiếm những ảnh có màu giống như

màu của bông hoa màu tím và vị trí là ở giữa hình thì người dùng có

Nguyễn Bá Công – Nguyễn Hữu Đức

129

thể chia thành lưới 3x3 như sau:

Chương 6:Cài đặt và thử nghiệm

Hình 138: Ảnh minh họa chia lưới và vùng được chọn

Khi đó người dùng chọn block thứ 4 tìm theo lược đồ màu với

độ giống nhau là 50% thì sẽ cho kết quả như sau:

Hình 139: Tập ảnh kết quả tìm được

Ví dụ khác:

Ả nh truy vấn

Hình 140: Ảnh truy vấn

Người dùng tìm kiếm những tấm ảnh có bông hoa ở giữa và

Nguyễn Bá Công – Nguyễn Hữu Đức

130

bên cạnh có lá thì người dùng có thể chia thành lưới như sau

Chương 6:Cài đặt và thử nghiệm

Hình 141: Ảnh minh hoạ cá vùng đựơc chọ Người dùng tìm kiếm block thứ 4 theo đặc trưng lược đồ màu

là 50% và block thứ 5 cũng theo đặc trưng lược đồ màu với độ giống

nhau là 60% thì cho kết quả như sau:

Hình 142: Tập ảnh tìm được Ví dụ 3:

Ảnh truy vấn:

Nguyễn Bá Công – Nguyễn Hữu Đức

131

Hình 143: Ảnh truy vấn

Chương 6:Cài đặt và thử nghiệm

Ảnh sau khi chia lưới 2x1

Hình 144: Ảnh sau khi chia lưới

Khi người dùng muốn tìm kiếm những ảnh có bầu trời thì người

dùng chọn block 0 với đặc trưng màu là 45% thì sẽ cho kết quả như sau:

Nguyễn Bá Công – Nguyễn Hữu Đức

132

Hình 145: Tập ảnh kết quả tìm được

Chương 6:Cài đặt và thử nghiệm

Nhưng khi người dùng kết hợp với block thứ 1 theo đặc trưng vector

liên kết góc với độ giống nhau là 55% sẽ cho kết quả sau:

Hình 146: Tập ảnh kết quả tìm được

6.2.2.2 Tìm kiếm bằng cách vẽ vùng

Ví dụ :

Nguyễn Bá Công – Nguyễn Hữu Đức

133

Hình 147: Ảnh truy vấn

Chương 6:Cài đặt và thử nghiệm

Hình 148: Minh họa vẽ tìm kiếm

Khi người dùng muốn tìm theo đặc trưng lược đồ màu với độ giống

nhau là 64% sẽ cho kết quả như sau:

Hình 149: Tập ảnh tìm được

Vẫn ảnh truy vấn trên nhưng người dùng tìm theo đặc trưng màu với

độ giống nhau là 64% và đặc trưng liên kết hệ số góc với độ giống nhau là

Nguyễn Bá Công – Nguyễn Hữu Đức

134

60% thì sẽ cho kết quả như sau:

Chương 6:Cài đặt và thử nghiệm

Hình 150: Tập ảnh tìm được

6.2.3 Tìm kiếm dựa theo vùng, đối tượng của ảnh có sẵn

Trong phần này cơ sở dữ liệu ảnh chúng em gồm 500 tấm ảnh Ví dụ 1:

Ả nh truy vấn ban đầu

Hình 151: Ảnh truy vấn theo vùng

Sau khi phân đọan ảnh ta được các vùng của ảnh như sau:

Nguyễn Bá Công – Nguyễn Hữu Đức

135

Hình 152: Các vùng của ảnh sau khi phân đoạn

Chương 6:Cài đặt và thử nghiệm

Chọn vùng truy tìm

Kết quả thu được:

Hình 153: Tập kết quả tìm theo vùng hoa màu tím

Ví dụ 2:

Nguyễn Bá Công – Nguyễn Hữu Đức

136

Ảnh truy vấn ban đầu

Chương 6:Cài đặt và thử nghiệm

Sau khi phân đọan ảnh ta thu được các vùng của ảnh như sau:

Hình 154: Các vùng của ảnh truy vấn

Khi người dùng muốn tìm kiếm những tấm ảnh có vùng là con sư tử với độ giống

nhau là 65%:

Hình 155: Vùng tìm kiếm

Nguyễn Bá Công – Nguyễn Hữu Đức

137

Kết quả tìm được những con sư tử có độ giống nhau 65%:

Chương 6:Cài đặt và thử nghiệm

Hình 156: Tập kết quả tìm được theo vùng sư tử

Để lọai bớt những tấm ảnh dư thừa trong tìm kiếm cũng như cho kết quả

chính xác hơn người dùng có thể chọn thêm vùng tìm kiếm hay tăng ngưỡng trong

tìm kiếm.

Ví dụ người dùng chọn thêm vùng bầu trời cho việc tìm kiếm:

Hình 157: Minh họa tìm kiếm theo toán tử BOOL

Nguyễn Bá Công – Nguyễn Hữu Đức

138

Kết quả thu được như sau:

Chương 6:Cài đặt và thử nghiệm

Hình 158: Tập kết quả thu được

Ví dụ 3: Ảnh ban đầu

Nguyễn Bá Công – Nguyễn Hữu Đức

139

Hình 159: Ảnh sau khi phân đoạn

Chương 6:Cài đặt và thử nghiệm

Người dùng có thể tìm kiếm bằng câu truy vấn

Hình 160: Minh họa câu truy vấn

Kết quả tìm được:

Hình 161: Kết quả tìm được

Nguyễn Bá Công – Nguyễn Hữu Đức

140

Khi người dùng tìm kiếm theo câu truy vấn sau:

Chương 6:Cài đặt và thử nghiệm

Hình 162: Câu truy vấn

Kết quả thu được:

Hình 163: Kết quả thực hiện câu truy vấn trên

6.2.4 Tìm kiếm dựa theo vùng, đối tượng khi mà người

dùng chưa có ý niệm rõ ràng về tấm ảnh

Ví du 1: Khi người dùng muốn tìm những ảnh có nền xanh thì người

Nguyễn Bá Công – Nguyễn Hữu Đức

141

dùng có thể chọn vùng và câu truy vấn dạng sau:

Chương 6:Cài đặt và thử nghiệm

Hình 164: Hình minh họa tìm kiếm theo vùng

Kết quả thu được:

Hình 165: Kết quả tìm được

Ví dụ 2: Khi người dùng muốn tìm những ảnh có bông hoa màu vàng và

Nguyễn Bá Công – Nguyễn Hữu Đức

142

nền màu xanh:

Chương 6:Cài đặt và thử nghiệm

Hình 166: Minh họa câu truy vấn theo vùng

Kết quả thu được:

Nguyễn Bá Công – Nguyễn Hữu Đức

143

Hình 167: Tập Kết quả tìm được

Chương 6:Cài đặt và thử nghiệm

6.2.5 Tìm kiếm dựa vào ngữ nghĩa

Ví dụ 1: với nhãn hổ con được gán cho vùng sau trong cơ sở dữ liệu:

Khi muốn tìm kiếm những hình có con hổ thì người dùng chỉ việc đánh từ khoá “hổ con” để tìm kiếm.

Kết quả tìm kiếm với từ khoá hổ con như sau:

Hình 168:Tập kết quả tìm kiếm với từ khoá” hổ con”

Ví dụ 2:

Với từ khoá “Chúa sơn lâm” được gán cho sư tử trong cơ sở dữ liệu.

Khi muốn tìm kiếm những con sư tử, người dùng có thể thực hiện từ khóa “

Nguyễn Bá Công – Nguyễn Hữu Đức

144

Chúa sơn lâm” cho con sư tử

Chương 6:Cài đặt và thử nghiệm

Hình 169: Ảnh minh hoạ tìm kiếm theo ngữ nghĩa, từ khoá “Chúa sơn lâm”

Kết quả tìm kiếm như sau:

Hình 170: Kết quả tìm kiếm với từ khoá “ Chúa sơn lâm” với độ giống nhau 64%

6.3. Kết quả thực nghiệm của hệ thống

Để đánh giá tính hiệu quả của hệ thống chúng em sử dụng 2 đại lượng:

Nguyễn Bá Công – Nguyễn Hữu Đức

145

(cid:131) Độ chính xác = Số ảnh tìm được đúng / Số ảnh tìm được

Chương 6:Cài đặt và thử nghiệm

(cid:131) Độ trung thực = Số ảnh tìm được đúng / Tổng số ảnh đúng thực có

6.3.1 Thực nghiệm việc tìm kiếm theo các đặc trưng cấp

thấp

Phương pháp nhập liệu Số mẫu thử Độ chính xác Độ trung thực

Phương pháp truy tìm trung bình trung bình

Chọn ảnh truy vấn 200 90 83

Truy tìm dựa vào lược đồ

màu

Chọn ảnh truy vấn 200 82 78

Truy tìm dựa vào lươc đồ hệ

số góc

Chọn ảnh truy vấn 200 86 80

Truy tìm dựa vào lược đồ

liên kết hệ số góc

Chọn ảnh truy vấn 200 92 84

Truy tìm dựa vào lược đồ

vector liên kết màu

Chọn ảnh truy vấn 200 90 84

Truy tìm dựa vào

correlogram

Chọn ảnh truy vấn 200 91 83

Truy tìm bằng cách chia lưới

Chọn ảnh truy vấn 200 92 83

Nguyễn Bá Công – Nguyễn Hữu Đức

146

Truy tìm bằng cách vẽ vùng

Chương 6:Cài đặt và thử nghiệm

6.3.2 Thực nghiệm việc tìm kiếm theo đặc trưng cấp cao

Phương pháp nhập liệu Số mẫu Độ chính xác Độ trung thực

Phương pháp truy tìm trung bình trung bình thử

Chọn vùng của ảnh truy vấn 94 150 91

Truy tìm dựa vào độ đo đối

sánh vùng

92 Chọn các mẫu truy vấn có sẵn 150 95

Truy tìm dựa vào độ đo đối

sánh vùng

Chọn ngữ nghĩa của vùng 150 95 92

Truy tìm dựa vào độ đo đối

Nguyễn Bá Công – Nguyễn Hữu Đức

147

sánh vùng

Chương 7:Tổng kết và hướng phát triển

Chương 7 TỔNG KẾT VÀ HƯỚNG PHÁT TRIỂN

Nguyễn Bá Công – Nguyễn Hữu Đức

148

Chương 7:Tổng kết và hướng phát triển

7.1. Tổng kết

Hiện nay 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” có khả năng:

(cid:131) Tìm kiếm ảnh dựa vào các đặc trưng cấp thấp (hay tìm kiếm ảnh dựa

vào tính phân bố tòan cục).

(cid:131) Tìm kiếm ảnh dựa vào tính phân bố cục bộ (tìm kiếm bằng việc chia

lưới hay cho người dùng vẽ trên ảnh truy vấn).

(cid:131) Tìm kiếm ảnh dựa vào vùng, đối tượng ảnh có sẵn.

(cid:131) Tìm kiếm dựa vào vùng,đối tượng khi mà người dùng chưa có ý

niệm rõ ràng về ảnh cần tìm kiếm.

(cid:131) Tìm kiếm dựa vào ngữ nghĩa (bán tự động).

Với các chức năng trên hệ thống đã hòan thành các mục tiêu đề ra ban đầu

là xây dựng hệ thống truy tìm ảnh dựa vào đặc trưng cấp thấp, đặc trưng cấp cao

và hướng tới việc tìm kiếm ảnh dựa vào ngữ nghĩa.

7.2. Hướng phát triển

Với hệ thống này, chúng em đã xây dựng được một nền tảng vững chắc

giúp ta lấp dần hố ngăn cách giữa các đặc trưng cấp thấp, cấp cao với ngữ nghĩa

của ảnh. Đây cũng là một hệ thống mở, tạo tiền đề cho việc tiến lên ngữ nghĩa một

cách dễ dàng. Cụ thể là hệ thống có thể phát triển lên thành hệ thống dịch ảnh tự

động chỉ thông qua việc học mẫu để gán nhãn cho vùng. Cùng với đó kết hợp với

việc xây dựng một bộ luật ngôn ngữ riêng, giúp ta tiến lên một bước truy tìm ảnh

cao hơn là: truy tìm ảnh chỉ bằng câu truy vấn dạng ngôn thông thường.

7.3. Kết luận

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à một công trình rất có ý nghĩa. Đây là một sản phẩm thể hiện trí tuệ Việt Nam,

Nguyễn Bá Công – Nguyễn Hữu Đức

149

và là sản phẩm của con người Việt Nam hoà vào trào lưu phát triển chung của thế

Chương 7:Tổng kết và hướng phát triển

giới. Nhận thức rõ ý nghĩa to lớn này, chúng em nguyện cố gắng nhiều hơn nữa,

Nguyễn Bá Công – Nguyễn Hữu Đức

150

tìm hiểu cải tiến chất lượng cho hệ thống càng hòan thiện hơn.

Tài liệu tham khảo

TÀI LIỆU THAM KHẢO

[1] Alberto Del Bimbo,”Visual Information Retrieval”, Morgan Publishers,

Inc.1999

[2] D .BimBo

Visual information Retrieval. Morgan Kaufmann ,1999

[3] Ihtisham Kabir

Ihtisham Kabir,”High Performance Computer Imaging”, Manning Publiccations

Company, 1996.

[4] Lý Quốc Ngọc

Truy tìm thông tin thị giác dựa vào nội dung bằng phương pháp gán nhãn ngữ

nghĩa cho ảnh.

Tạp chí phát triển khoa học công nghệ, tập 7, tháng 4&5 năm 2004.

[5] Nguyễn Lãm, Lý Quốc Ngọc, Dương Anh Đức, Nguyễn Bá Công, Nguyễn

Hữu Đức

Truy tìm hình ảnh dựa vào nội dung bằng phương pháp đánh vần ảnh.

Tạp chí phát triển khoa học công nghệ.

[6] Rafael C.Gonzalez, Richard E.Woods

Digital Image Processing. Second Edition, Prentice – Hall, Inc.2002

[7] Quoc Ngoc Ly, Anh Duc Duong.

Hierarchical Algorithm Clustering in Content-Based-Image-Retrieval Proceedings

of The International Technical Conference on Circuits/Systems, Computers, and

Communication (ITC- CSCC 2005), July 4, 2005. Korea.

[8] Quoc Ngoc Ly, Anh Duc Duong.

Hierarchical Data Model in Content-based Image Retrieval.

International Journal of Information Technology,

International Conference on Intelligent Computing, 23-28 August, 2005 China.

Nguyễn Bá Công – Nguyễn Hữu Đức

151

[9] Sergios Theodoridis, Konstantinos Koutroumbas

Tài liệu tham khảo

Nguyễn Bá Công – Nguyễn Hữu Đức

152

Pattern Recognition, Academic Press, 1999