Tài liệu Nghiên cứu phương pháp biểu diễn và tra cứu ảnh hiệu quả ứng dụng trong tra cứu ảnh phong cảnh

i ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CNTT & TT THÁI NGUYÊN ---------*****--------- Nguyễn Thị Nhung NGHIÊN CỨU PHƢƠNG PHÁP BIỂU DIỄN VÀ TRA CỨU ẢNH HIỆU QUẢ ỨNG DỤNG TRONG TRA CỨU ẢNH PHONG CẢNH LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH Thái Nguyên – 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ii ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CNTT & TT THÁI NGUYÊN ---------*****--------- Nguyễn Thị Nhung NGHIÊN CỨU PHƢƠNG PHÁP BIỂU DIỄN VÀ TRA CỨU ẢNH HIỆU QUẢ ỨNG DỤNG TRONG TRA CỨU ẢNH PHONG CẢNH Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƢỜI HƢỚNG DẪN KHOA HỌC TS. Nguyễn Hữu Quỳnh Thái Nguyên - 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iii LỜI CAM ĐOAN Tôi xin cam đoan luận văn là kết quả nghiên cứu của riêng tôi, dƣới sự hƣớng dẫn khoa học của TS. Nguyễn Hữu Quỳnh. Các số liệu, kết quả nêu trong luận văn là hoàn toàn trung thực. Thái nguyên, ngày tháng 9 năm 2011 Ngƣời cam đoan Nguyễn Thị Nhung Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iv Lời cảm ơn Trong quá trình thực hiện luận văn này, em luôn nhận đƣợc sự hƣớng dẫn, chỉ bảo tận tình của TS Nguyễn Hữu Quỳnh, Khoa Công nghệ Thông tin thuộc trƣờng Đại học Điện lực là cán bộ trực tiếp hƣớng dẫn khoa học cho em. Thầy đã dành nhiều thời gian trong việc hƣớng dẫn cách nghiên cứu, đọc tài liệu, cài đặt các thuật toán và giúp đỡ về xây dựng hệ thống thực nghiệm. Em xin chân thành cảm ơn các Thầy, Cô giáo trong trƣờng Đại học Công nghệ Thông tin và Truyền Thông, Đại học Thái Nguyên đã luôn nhiệt tình giúp đỡ và tạo điều kiện tốt nhất cho em trong suốt quá trình học tập tại trƣờng. Xin chân thành cảm ơn các anh, các chị và các bạn học viên lớp Cao học trƣờng Đại học Công nghệ Thông tin và Truyền Thông thuộc Đại học Thái Nguyên đã luôn động viên, giúp đỡ và nhiệt tình chia sẻ với tôi những kinh nghiệm học tập, công tác trong suốt khoá học. Tôi cũng xin chân thành cảm ơn các vị lãnh đạo và các bạn đồng nghiệp tại Trƣờng Dự bị Đại học Dân tộc Sầm Sơn đã luôn tạo mọi điều kiện tốt nhất để tôi có thể hoàn thành tốt đẹp khoá học Cao học này. Thái nguyên, ngày tháng 9 năm 2011 Nguyễn Thị Nhung Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn v MỤC LỤC TRANG PHỤ BÌA LỜI CAM ĐOAN LỜI CẢM ƠN MỤC LỤC DANH MỤC CÁC CHỮ VIẾT TẮT ...................................................................... ix DANH MỤC CÁC HÌNH ........................................................................................ ix DANH MỤC CÁC BẢNG ........................................................................................ x Lời mở đầu ................................................................................................................ x Chƣơng 1. TỔNG QUAN VỀ TRA CỨU ẢNH DỰA VÀO NỘI DUNG ............. .1 1.1 Giới thiệu ...........................................................................................................3 1.2 Trích rút đặc trƣng ............................................................................................. 6 1.2.1 Màu .............................................................................................................6 1.2.1.1 Lƣợc đồ màu ............................................................................................ 7 1.2.1.2 Các màu trội ............................................................................................. 8 1.2.1.3 Các mômen màu ......................................................................................9 1.2.2 Kết cấu ......................................................................................................10 1.2.3 Hình dạng ..................................................................................................11 1.2.3.1 Các bất biến mômen ..............................................................................11 1.2.3.2 Các góc uốn ........................................................................................... 12 1.2.3.3 Các ký hiệu mô tả Fourier......................................................................13 1.2.3.4 Hình tròn, độ lệch tâm, và hƣớng trục chính .........................................15 1.2.4 Thông tin không gian ...................................................................................15 1.2.5 Phân đoạn ..................................................................................................16 1.3 Đánh chỉ số ......................................................................................................18 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn vi 1.4 Độ tƣơng tự giữa các ảnh ................................................................................18 1.4.1 Độ đo về màu sắc ......................................................................................18 1.4.2 Độ đo tƣơng đồng cho hình dạng ............................................................ 19 1.4.3 Độ đo tƣơng đồng cho kết cấu ảnh .......................................................... 19 1.4.4 Độ đo tƣơng đồng cho đặc trƣng phân đoạn............................................20 1.5 Các hệ thống CBIR.......................................................................................... 20 1.5.1 QBIC của IBM .......................................................................................... 20 1.5.2 Virage.......................................................................................................22 1.5.3 RetrievalWare ........................................................................................... 23 1.5.4 VisualSeek và WebSeek ...........................................................................23 1.5.5 Photobook .................................................................................................24 1.5.6 Netra ..........................................................................................................24 1.6 Đánh giá hiệu năng tra cứu..............................................................................24 1.7 Kết luận chƣơng 1 ........................................................................................... 26 Chƣơng 2. KỸ THUẬT BIỂU DIỄN VÀ TRA CỨU ẢNH HIỆU QUẢ ............. 28 2.1 Giới thiệu .........................................................................................................28 2.2 Khái niệm về đồ thị hai phía ...........................................................................30 2.3 Một số kỹ thuật tra cứu dựa vào đặc trƣng màu ..............................................31 2.3.1 Kỹ thuật tra cứu dựa vào lƣợc đồ màu toàn bộ - GCH ............................. 31 2.3.2 Kỹ thuật tra cứu dựa vào lƣợc đồ màu cục bộ - LCH............................... 32 2.3.3 Véc tơ gắn kết màu ...................................................................................33 2.3.4 Tƣơng quan màu .......................................................................................34 2.4 Kỹ thuật biểu diễn và tra cứu ảnh hiệu quả .....................................................34 2.4.1 Lƣợc đồ màu dải .......................................................................................34 2.4.2 Phƣơng pháp tra cứu dựa vào lƣợc đồ màu khối ......................................36 2.4.2.1 Giới thiệu ........................................................................................... 36 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn vii 2.4.2.2 Phƣơng pháp tra cứu HG ...................................................................39 2.5 Kết luận chƣơng 2 ........................................................................................... 41 CHƢƠNG 3. HỆ THỐNG TRA CỨU ẢNH DỰA VÀO NỘI DUNG SỬ DỤNG BIỂU DIỄN HIỆU QUẢ ......................................................................................... 43 3.1 Giới thiệu bài toán tra cứu ảnh phong cảnh ....................................................43 3.2. Phân tích bài toán ........................................................................................... 43 3.3 Thiết kế hệ thống ............................................................................................. 44 3.4 Mô tả chƣơng trình .......................................................................................... 45 3.4.1 Khái quát về chƣơng trình ........................................................................45 3.4.2 Các chức năng của chƣơng trình ............................................................. 46 3.4.3 Biểu đồ Use Case ......................................................................................46 3.4.4 Biểu đồ trình tự và biểu đồ hoạt động ......................................................47 3.5 Thiết kế cơ sở dữ liệu ......................................................................................51 3.6 Giao diện chƣơng trình ....................................................................................52 3.7 Xây dựng chƣơng trình: ..................................................................................55 3.8 Đánh giá hiệu quả của các phƣơng pháp ......................................................... 56 3.9 Một số kết quả .................................................................................................57 3.10 Kết luận chƣơng 3 ......................................................................................... 59 KẾT LUẬN ............................................................................................................. 60 TÀI LIỆU THAM KHẢO ....................................................................................... 61 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn viii DANH MỤC CÁC CHỮ VIẾT TẮT Ký hiệu Diễn giải QBE Query by Example (Truy vấn bởi ảnh mẫu) QBF Query by Feature (Truy vấn bởi đặc trƣng) RGB Red Green Blue (Đỏ, Xanh lục, Xanh lơ) HSV Hue, Saturation, Value (Màu, sắc nét, cƣờng độ) CCV Color Coherence Vectors (Véc tơ gắn kết màu) SDF Spectral Distribution Functions (Hàm phân bố phổ) MLE Maximum Likelihood Estimation (Ƣớc lƣợng khả năng nhất) AR MRSAR multi-resolution simultaneous auto-regressive model (Mô hình tự hồi quy đồng thời đa phân giải) SAR Simultaneous Auto-Regressive (Tự hồi quy đồng thời) MRF Markov random field (Trƣờng ngẫu nhiên Markov) LSE Least Square Error (Sai số bình phƣơng tối thiểu) RISAR Rotation-Invariant SAR model(Mô hình SAR bất biến quay) PWT Pyramid-Structured Wavelet Transform (Biến đổi song cấu trúc hình chóp) TWT Tree-Structured Wavelet Transform (Biến đổi song cấu trúc cây) SAQ Successive Approximation Quantization (lƣợng hoá xấp xỉ) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ix DANH MỤC CÁC HÌNH Hình 2.1. Ba ảnh và biểu đồ màu của chúng. .......................................................... 32 Hình 2.2. Một ảnh đƣợc phân hoạch sử dụng một lƣới 3 x 3 và CCH của nó. ....... 35 Hình 2.3. Ảnh I và ảnh I’......................................................................................... 37 Hình 2.4. Lƣợc đồ màu khối theo màu black và white biểu diễn ảnh I. ................. 37 Hình 2.5. Lƣợc đồ màu khối theo màu black và white biểu diễn ảnh I’. ................ 37 Hình 2.6. Tính khoảng cách của ảnh I và I’ theo màu black. .................................. 38 Hình 2.7. Tính khoảng cách của ảnh I và I’ theo màu white. ................................. 38 Hình 3.1. Mô hình hệ thống tra cứu ảnh hiệu quả. .................................................. 46 Hình 3.2. Sơ đồ phân cấp chức năng của chƣơng trình……………………...........46 Hình 3.3. Biểu đồ Use Case. ................................................................................... 47 Hình 3.4. Biểu đồ trình tự của tác nhân tra cứu. ..................................................... 48 Hình 3.5. Biểu đồ hoạt động của tác nhân tra cứu ảnh. .......................................... 49 Hình 3.6. Biểu đồ trình tự của tác nhân Quản lý cơ sở dữ liệu ảnh. ....................... 50 Hình 3.7. Biểu đồ liên kết các bảng trong cơ sở dữ liệu. ........................................ 52 Hình 3.8 Giao diện chính của chƣơng trình. ........................................................... 53 Hình 3.9.Giao diện tra cứu ảnh. .............................................................................. 53 Hình 3.10.Giao diện thêm một ảnh vào cơ sở dữ liệu. ............................................ 54 Hình 3.11.Giao diện thêm một tập ảnh vào cơ sở dữ liệu. ...................................... 54 Hình 3.12.Giao diện xoá một ảnh khỏi cơ sở dữ liệu. ............................................. 55 Hình 3.13.Ảnh truy vấn. .......................................................................................... 57 Hình 3.14. Kết quả tìm kiếm đƣợc với phƣơng pháp GCH. ................................... 57 Hình 3.15 Kết quả tìm kiếm đƣợc với phƣơng pháp LCH. ..................................... 58 Hình 3.16.Kết quả tìm kiếm đƣợc với phƣơng pháp HG. ....................................... 59 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn x DANH MỤC CÁC BẢNG Bảng 3.1 Bảng imgBin ............................................................................................ 51 Bảng 3.2. Bảng imgOri: .......................................................................................... 51 Bảng 3.3. Bảng imgTemp: ...................................................................................... 51 Bảng 3.4. Bảng color: .............................................................................................. 52 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 LỜI MỞ ĐẦU Những năm gần đây việc xử lý ảnh số ngày càng đƣợc nhiều ngƣời quan tâm, một phần là do dung lƣợng của các thiết bị lƣu trữ và thiết bị số hoá tăng nhanh và có giá thành giảm. Thêm nữa là sự phát triển mạnh mẽ công nghệ thông tin và đặc biệt là sự phát triển mạng Internet dẫn đến một số lƣợng khổng lồ các ảnh số đƣợc đƣa lên mạng. Một thực tế khác là khi số lƣợng ảnh trong một bộ sƣu tập còn ít, chúng ta có thể dùng mắt thƣờng để nhận dạng một bức ảnh, tuy nhiên với một số lƣợng ảnh lớn thì việc làm thủ công này sẽ không khả thi. Khi số lƣợng ảnh phong cảnh ngày càng lớn, ngƣời sử dụng muốn tìm kiếm một bức ảnh phong cảnh tƣơng tự với một ảnh phong cảnh đã có là một việc rất khó khăn. Từ những thực tế đó đặt ra vấn đề phải có những phƣơng pháp tổ chức cơ sở dữ liệu ảnh và xây dựng những kỹ thuật tra cứu, so sánh, tìm kiếm ảnh số hiệu quả. Việc tìm kiếm đƣợc một bức ảnh phong cảnh mong muốn trong hàng triệu bức ảnh thuộc các chủ đề khác nhau là rất khó khăn. Việc biểu diễn và trích rút đặc trƣng để nhận dạng đƣợc bức ảnh mong muốn ấy rất quan trọng và nhiều hƣớng nghiên cứu khác nhau đã đƣợc triển khai. Trƣớc năm 1990, ngƣời ta thƣờng sử dụng cách tiếp cận tra cứu ảnh theo văn bản (Text Based Image Retrieval), tuy nhiên cách tiếp cận này cũng khó khả thi trong các cơ sở dữ liệu ảnh lớn và kết quả còn mang tính chủ quan, cảm ngữ cảnh. Một trong những phƣơng pháp đƣợc nhiều ngƣời quan tâm nghiên cứu hiện nay là kỹ thuật "Tra cứu ảnh dựa theo nội dung - Content Based Image Retrieval‖. Kỹ thuật này cho phép trích rút các đặc trƣng của ảnh dựa vào nội dung trực quan của bản thân ảnh nhƣ màu sắc, kết cấu, hình dạng và bố cục không gian của ảnh để làm cơ sở cho việc tra cứu, sắp xếp, tổ chức cơ sở dữ liệu ảnh. Một số hệ thống tra cứu ảnh nổi tiếng nhƣ QBIC (IBM), Virage (Virage Inc.) Photobook (MIT) Visual SEEK (Columbia University) đã áp dụng kỹ thuật này. Tuy nhiên, khi cơ sở dữ liệu ảnh lớn thì việc trích rút đặc trƣng sẽ cho kết quả là một cơ sở dữ liệu đặc trƣng rất lớn. Điều này sẽ dẫn đến việc phải chi phí nhiều Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 không gian lƣu trữ, thời gian so sánh các véc tơ đặc trƣng, và do đó dẫn đến quá trình tra cứu để tìm đƣợc bức ảnh mong muốn sẽ tốn nhiều thời gian. Để giảm chi phí về không gian lƣu trữ, thời gian so sánh các véc tơ đặc trƣng và thời gian tra cứu, cần có kỹ thuật biểu diễn, trích rút và tra cứu ảnh hiệu quả. Đề tài này nghiên cứu cơ sở lý thuyết và các ứng dụng chính của kỹ thuật tra cứu ảnh theo nội dung và kỹ thuật biểu diễn và tra cứu ảnh hiệu quả, trên cơ sở đó thử nghiệm phƣơng pháp cụ thể để xây dựng một phần mềm đọc vào một ảnh phong cảnh mẫu và tìm kiếm những ảnh phong cảnh tƣơng tự với ảnh mẫu trong một tập hợp các ảnh cho trƣớc. Nội dung luận văn gồm 3 chƣơng: Chƣơng 1: Giới thiệu tổng quan về tra cứu ảnh dựa vào nội dung Chƣơng 2: Trình bày kỹ thuật biểu diễn và tra cứu ảnh hiệu quả Chƣơng 3: Giới thiệu một hệ thống thực nghiệm tra cứu ảnh phong cảnh. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 Chƣơng 1. TỔNG QUAN VỀ TRA CỨU ẢNH DỰA VÀO NỘI DUNG 1.1 Giới thiệu Ngày nay, cùng với nhu cầu tìm kiếm văn bản, nhu cầu tìm kiếm ảnh cũng nhận đƣợc nhiều quan tâm của ngƣời sử dụng. Tuy nhiên, với một số lƣợng ảnh quá lớn trên Internet công việc tìm kiếm trở nên vô cùng khó khăn. Để giải quyết vấn đề này, các hệ thống tìm kiếm ảnh đã ra đời nhƣ: Yahoo, MSN, Google Image Search, Bing,…. Các hệ thống này cho phép ngƣời sử dụng truy vấn các ảnh cần quan tâm. Thông qua việc phân tích các văn bản đi kèm ảnh, hệ thống gửi trả các ảnh tƣơng ứng với truy vấn của ngƣời dùng. Tuy nhiên, các phƣơng pháp dựa trên văn bản mô tả ảnh dựa trên các phƣơng pháp tra cứu thông tin văn bản truyền thống và hệ quản trị cơ sở dữ liệu cũng nhƣ sự can thiệp của con ngƣời để trích rút siêu dữ liệu về một đối tƣợng trực quan và kết hợp nó cùng với đối tƣợng trực quan nhƣ một chú thích văn bản. Tuy nhiên, gán các thuộc tính văn bản một cách thủ công cần nhiều thời gian và chi phí. Hơn nữa, các chú thích thủ công thƣờng phụ thuộc rất nhiều vào nhận thức chủ quan của con ngƣời. Nhận thức chủ quan và chú thích thiếu chính xác là nguyên nhân tra cứu không chính xác trong các quá trình tra cứu sau. Các vấn đề đối với việc truy cập các ảnh và video dựa vào văn bản đã thúc đẩy nhanh chóng sự quan tâm phát triển các giải pháp dựa vào nội dung. Với giải pháp này, thay vì đƣợc chú thích một cách thủ công bởi các từ khoá dựa vào văn bản, các ảnh có thể đƣợc trích rút sử dụng một số đặc trƣng trực quan nhƣ màu, kết cấu, hình dạng, và quan hệ không gian giữa các vùng và đƣợc đánh chỉ số dựa trên các đặc trƣng trực quan này. Cách tiếp cận này dựa chủ yếu vào các kết quả từ thị giác máy. Tuy nhiên, không có đặc trƣng riêng lẻ tốt nhất mà cho các kết quả chính xác. Thông thƣờng một sự kết hợp các đặc trƣng một cách tuỳ biến là cần thiết để cung cấp các kết quả tra cứu thích hợp cho ứng dụng tra cứu ảnh dựa vào nội dung. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 Một hệ thống tra cứu ảnh dựa vào nội dung (CBIR – Content Based Image Retrieval) tiêu biểu không chỉ xử lý các nguồn thông tin khác nhau ở các khuôn dạng khác nhau (thí dụ, văn bản, hình ảnh và video) mà còn giải quyết các nhu cầu của ngƣời sử dụng. Về cơ bản hệ thống phân tích cả các nội dung của nguồn thông tin cũng nhƣ các truy vấn sử dụng, và sau đó so sánh các nội dung này để tra cứu các mục tin liên quan. Các chức năng chính của một hệ thống tra cứu ảnh dựa vào nội dung nhƣ sau: 1. Phân tích các nội dung của nguồn thông tin, và biểu diễn các nội dung của các nguồn đƣợc phân tích theo cách thích hợp cho so sánh các truy vấn sử dụng (không gian của nguồn thông tin đƣợc biến đổi thành không gian đặc trƣng cho mục tiêu so sánh nhanh trong bƣớc tiếp theo). Bƣớc này thông thƣờng cần rất nhiều thời gian do nó phải xử lý lần lƣợt tất cả thông tin nguồn (các ảnh) trong cơ sở dữ liệu. Tuy nhiên, bƣớc này đƣợc thực hiện chỉ một lần và có thể đƣợc thực hiện ngoại tuyến. 2. Phân tích các truy vấn ngƣời sử dụng và biểu diễn chúng ở dạng thích hợp cho so sánh với cơ sở dữ liệu nguồn. Bƣớc này là tƣơng tự với bƣớc trƣớc, nhƣng chỉ đƣợc áp dụng với ảnh truy vấn. 3. Định nghĩa một chiến lƣợc để so sánh các truy vấn tìm kiếm với thông tin trong cơ sở dữ liệu đƣợc lƣu trữ. Tra cứu thông tin liên quan theo một cách hiệu quả. Bƣớc này đƣợc thực hiện trực tuyến và đƣợc yêu cầu rất nhanh. Các kỹ thuật đánh chỉ số hiện đại có thể đƣợc sử dụng để tổ chức lại không gian đặc trƣng để tăng tốc quá trình đối sánh. 4. Thực hiện các điều chỉnh cần thiết trong hệ thống (thƣờng bằng điều chỉnh các tham số trong máy đối sánh) dựa trên phản hồi từ ngƣời sử dụng và/hoặc các ảnh đƣợc tra cứu. Có nhiều cách gửi một truy vấn trực quan. Một phƣơng pháp truy vấn tốt là một phƣơng pháp tự nhiên đối với ngƣời sử dụng cũng nhƣ thu đƣợc đủ thông tin từ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 ngƣời sử dụng để trích rút các kết quả có ý nghĩa. Các phƣơng pháp truy vấn dƣới đây đƣợc sử dụng phổ biến trong nghiên cứu tra cứu ảnh dựa vào nội dung: Truy vấn bởi ảnh mẫu (QBE): Trong loại truy vấn này, ngƣời sử dụng hệ thống chỉ rõ một ảnh truy vấn đích, dựa trên ảnh truy vấn đó hệ thống sẽ tìm kiếm trong cơ sở dữ liệu ảnh các ảnh tƣơng tự nhất. Ảnh truy vấn có thể là một ảnh thông thƣờng, một bản quét của một ảnh có độ phân giải thấp, hoặc một phác thảo của ngƣời sử dụng sử dụng các công cụ mô tả giao diện đồ hoạ. Một ƣu điểm chính của loại hệ thống này đó là nó là một cách tự nhiên cho những ngƣời sử dụng chung và chuyên gia để tìm kiếm một cơ sở dữ liệu ảnh. Truy vấn bởi đặc trưng (QBF): Trong hệ thống QBF tiêu biểu, những ngƣời sử dụng chỉ rõ các truy vấn bằng việc chỉ rõ các đặc trƣng họ quan tâm cho tìm kiếm. Thí dụ, một ngƣời sử dụng có thể truy vấn một cơ sở dữ liệu ảnh bằng việc đƣa ra một lệnh để tra cứu tất cả các ảnh có góc phần tƣ trái chứa 25% pixel màu vàng. Truy vấn này đƣợc chỉ rõ bằng việc sử dụng các công cụ giao diện đồ hoạ chuyên dụng. Những ngƣời sử dụng hệ thống tra cứu ảnh chuyên biệt có thể thấy loại truy vấn này là bình thƣờng, nhƣng những ngƣời sử dụng chung thì không thể. QBIC [5] là một ví dụ về một hệ thống tra cứu ảnh dựa vào nội dung sử dụng loại phƣơng pháp truy vấn này. Các truy vấn dựa vào thuộc tính: Các truy vấn dựa vào thuộc tính sử dụng các chú thích văn bản, trích rút trƣớc bởi nỗ lực của con ngƣời, nhƣ một khoá tra cứu chính. Loại biểu diễn này đòi hỏi một độ trừu tƣợng cao khó để thu đƣợc bằng các phƣơng pháp tự động hoàn toàn do một ảnh chứa một số lƣợng lớn các thông tin mà khó tóm tắt khi sử dụng một số ít các từ khoá. Phƣơng pháp này nhìn chung là nhanh hơn và dễ hơn để thực hiện, nhƣng có một độ chủ quan và nhập nhằng cao xuất hiện nhƣ chúng ta đã đề cập. Một ngƣời sử dụng tiêu biểu chắc chắn thích truy vấn các hệ thống tra cứu ảnh dựa vào nội dung bằng việc yêu cầu các câu hỏi tự nhiên nhƣ ―Đƣa cho tôi tất cả các bức ảnh về hoa hồng.‖ hoặc ―Tìm tất cả các ảnh có cầu Tràng Tiền.‖. Ánh xạ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 truy vấn ngôn ngữ tự nhiên này đến một truy vấn trên cơ sở dữ liệu ảnh là vô cùng khó so với việc sử dụng các phƣơng pháp chú thích. Khả năng của các máy tính để thực hiện nhận dạng đối tƣợng tự động trên các ảnh chung vẫn là một vấn đề nghiên cứu mở. Do đó hầu hết các nỗ lực nghiên cứu và thƣơng mại tập trung vào xây dựng các hệ thống thực hiện tốt với các phƣơng pháp QBE. 1.2 Trích rút đặc trƣng Trích rút đặc trƣng là cơ sở của tra cứu ảnh dựa vào nội dung. Theo nghĩa rộng, các đặc trƣng có thể bao gồm cả các đặc trƣng dựa vào văn bản và các đặc trƣng trực quan nhƣ màu, kết cấu, hình dạng. Trong phạm vi đặc trƣng trực quan, các đặc trƣng có thể đƣợc phân loại tiếp thành các đặc trƣng chung và các đặc trƣng lĩnh vực cụ thể. Các đặc trƣng trực quan chung gồm màu, kết cấu, và hình dạng trong khi các đặc trƣng lĩnh vực cụ thể là phụ thuộc ứng dụng và có thể gồm mặt ngƣời và vân tay. Các đặc trƣng lĩnh vực cụ thể bao gồm nhiều tri thức lĩnh vực. Nói chung, không tồn tại một biểu diễn đơn tốt nhất cho một đặc trƣng đã cho. Với mọi đặc trƣng đƣợc cho tồn tại nhiều biểu diễn mô tả đặc trƣng từ các viễn cảnh khác nhau. 1.2.1 Màu Màu là đặc trƣng trực quan quan trọng đầu tiên và đơn giản nhất cho đánh chỉ số và tra cứu các ảnh [19, 17, 18]. Nó cũng là đặc trƣng đƣợc sử dụng phổ biến nhất trong lĩnh vực. Một ảnh màu tiêu biểu đƣợc thu từ một camera số, hoặc đƣợc tải xuống từ Internet thƣờng có ba kênh màu (các ảnh xám chỉ có một kênh, các ảnh đa phổ có thể có nhiều hơn ba kênh). Tuy nhiên, các giá trị của dữ liệu ba chiều từ ảnh màu không cho chúng ta một mô tả chính xác của màu trong ảnh, nhƣng cho vị trí của các pixel này trong không gian màu. Các pixel có các giá trị (1,1,1) sẽ xuất hiện khác nhau về màu trong các không gian màu khác nhau. Vì thế mô tả đầy đủ của một ảnh màu tiêu biểu sẽ bao gồm thông tin không gian hai chiều cho biết nơi của Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 pixel màu là trong miền không gian, chúng ta đang nói đến không gian màu, và dữ liệu màu ba chiều cho biết nơi của pixel màu là trong không gian màu này. Ở đây không gian màu đƣợc giả thiết là cố định, thông tin không gian trong ảnh bị bỏ qua, và thông tin màu trong một ảnh tiêu biểu có thể đƣợc xem nhƣ tín hiệu ba chiều đơn. Các tín hiệu màu một hoặc hai chiều cũng đƣợc sử dụng rộng rãi trong CBIR đặc biệt trong các ứng dụng mà các điều kiện thu ảnh tƣơng phản mạnh là quan trọng. Thông tin màu ở dạng các toạ độ xy hoặc ab của các hệ thống CIE XYZ và CIE LAB có thể đƣợc sử dụng trong các ứng dụng độc lập cƣờng độ. Thông tin màu (Hue) đƣợc sử dụng trong các ứng dụng nơi chỉ sự khác biệt giữa chất liệu của các đối tƣợng trong cảnh là quan trọng. Trong [8, 7] đã chỉ ra rằng màu là bất biến dƣới ánh sáng, bóng, và thay đổi hình học của ngƣời quan sát và các góc chiếu sáng. Nếu coi thông tin màu của một ảnh nhƣ một tín hiệu một, hai, hoặc ba chiều, phân tích tín hiệu bằng việc sử dụng ƣớc lƣợng mật độ xác suất là cách đơn giản nhất để mô tả thông tin màu của ảnh. Lƣợc đồ là công cụ đơn giản nhất. Các cách mô tả thông tin màu khác trong CBIR gồm sử dụng véc tơ gắn kết màu, tƣơng quan màu, các màu trội, hoặc các dấu hiệu màu, và các mômen màu. 1.2.1.1 Lƣợc đồ màu Lƣợc đồ màu cung cấp một biểu diễn hiệu quả của nội dung màu của một ảnh nếu mẫu màu là duy nhất so với phần còn lại của tập dữ liệu. Lƣợc đồ màu là dễ dàng để tính toán và hiệu quả trong mô tả cả phân bố màu toàn cục và cục bộ trong ảnh. Hơn nữa, nó mạnh với quay và dịch chuyển về trục quan sát và thay đổi chậm với tỷ lệ và góc quan sát. Do mọi pixel trong ảnh có thể đƣợc mô tả bởi ba thành phần màu trong một không gian màu nào đó (thí dụ, các thành phần đỏ (red), xanh lam (green) và xanh lơ (blue) trong không gian RGB, hoặc màu (hue), độ sắc nét (saturation) và cƣờng độ (value) trong không gian HSV), một lƣợc đồ (phân bố của số các pixel cho mỗi Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 bin đƣợc lƣợng hoá) có thể đƣợc định nghĩa cho mỗi thành phần. Rõ ràng, một lƣợc đồ màu chứa nhiều bin hơn, nó có khả năng phân biệt tốt hơn. Tuy nhiên, một lƣợc đồ với một số lƣợng lớn các bin sẽ không chỉ tăng chi phí tính toán, mà cũng sẽ không thích hợp để xây dựng các chỉ số hiệu quả cho các cơ sở dữ liệu ảnh. Hơn nữa, số lƣợng bin tốt không cải tiến hiệu năng tra cứu trong nhiều ứng dụng. Một cách để giảm số các bin là sử dụng không gian màu đối lập cho phép độ chói của lƣợc đồ đƣợc lấy mẫu xuống. Một cách khác là sử dụng các phƣơng pháp phân cụm để xác định K màu tốt nhất trong một không gian đã cho với một tập các ảnh đã cho. Mỗi màu tốt nhất này sẽ đƣợc chấp nhận nhƣ một bin lƣợc đồ. Do quá trình phân cụm lấy phân bố màu của các ảnh trên toàn bộ cơ sở dữ liệu ảnh vào xem xét, khả năng các bin lƣợc đồ trong đó không có hoặc có rất ít pixel rơi vào là cực tiểu. Một lựa chọn khác là sử dụng các bin có số pixel lớn nhất do một số nhỏ các bin lƣợc đồ thu đƣợc phần lớn các pixel của một ảnh [23]. Một sự giảm nhƣ thế không làm giảm hiệu năng của đối sánh lƣợc đồ, mà còn có thể tăng cƣờng nó do các bin lƣợc đồ nhỏ coi nhƣ là nhiễu. Khi một cơ sở dữ liệu ảnh chứa một số lƣợng lớn các ảnh, so sánh theo lƣợc đồ sẽ bão hòa sự phân biệt. Để giải quyết vấn đề này, kỹ thuật lƣợc đồ liên kết đƣợc giới thiệu. Ngoài ra, lƣợc đồ màu không đƣa thông tin không gian của các pixel vào xem xét, vì thế các ảnh rất khác nhau có thể có các phân bố màu tƣơng tự. Vấn đề này trở nên đặc biệt sâu sắc với các cơ sở dữ liệu lớn. Để tăng khả năng phân biệt, một số cải tiến đã đƣợc đề xuất để liên kết thông tin không gian. Một cách đơn giản là chia một ảnh thành các vùng con và tính lƣợc đồ cho mỗi vùng con này. Nhƣ đã đƣợc giới thiệu ở trên, cách chia đơn giản là phân hoạch hình chữ nhật, hoặc phức tạp nhƣ phân đoạn vùng hoặc thậm chí phân hoạch đối tƣợng. Tăng số các vùng con sẽ tăng thông tin về vị trí, nhƣng cũng tăng về chi phí bộ nhớ và thời gian tính toán. 1.2.1.2 Các màu trội Dựa trên quan sát rằng các lƣợc đồ màu thì rất thƣa và thông thƣờng một số nhỏ các màu là đủ để miêu tả thông tin màu trong một ảnh màu, các màu trội đƣợc Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 sử dụng để mô tả nội dung màu của một ảnh. Một phân cụm màu đƣợc thực hiện để thu các màu trội đại diện của nó và phần trăm tƣơng ứng của nó. Mỗi màu đại diện và phần trăm tƣơng ứng của nó tạo ra một cặp các thuộc tính mô tả các đặc trƣng màu trong một vùng ảnh. Ký hiệu mô tả đặc trƣng lƣợc đồ màu trội F đƣợc định nghĩa là một tập các cặp sau: F  {ci , pi }, i  1..N  (1  1) Ở đây N là tổng số các cụm màu trong ảnh, ci là một véc tơ màu ba chiều, pi là phần trăm của nó, và i pi  1 . Lƣu ý rằng N có thể thay đổi từ ảnh này sang ảnh khác. 1.2.1.3 Các mômen màu Các mômen màu là các mômen thống kê của các phân bố xác suất của các màu. Các mômen màu đƣợc sử dụng thành công trong nhiều hệ thống tra cứu ảnh nhƣ QBIC [5, 21], đặc biệt khi ảnh chứa chính xác đối tƣợng. Các mômen màu bậc nhất (trung bình), bậc hai (phƣơng sai) và bậc ba (độ lệch), đã đƣợc chứng minh là hiệu quả trong biểu diễn các phân bố màu của các ảnh [13]. Về mặt toán học, ba mômen đầu tiên đƣợc định nghĩa bằng: i  1 N N f j 1 (1  2) ij 1 1  i  (  ( f ij   i ) 2 ) 2 N 1 si  ( N 1 3 3 N ( f j 1 ij  i ) ) (1  3) (1  4) Ở đây f ij là giá trị của thành phần màu thứ i của pixel ảnh j . N là số các pixel trong ảnh. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 Thông thƣờng mômen màu thực hiện tốt hơn nếu nó đƣợc xác định bởi cả hai không gian màu L*u*v* và L*a*b* chứ không chỉ duy nhất bởi không gian màu HSV. Sử dụng thêm mômen bậc ba cải tiến hiệu năng tra cứu so với chỉ sử dụng các mômen bậc nhất và bậc hai. Tuy nhiên, mômen bậc ba này thỉnh thoảng làm cho biểu diễn đặc trƣng nhạy cảm hơn với sự thay đổi cảnh và do đó có thể giảm hiệu năng. Do chỉ 9 số (ba mômen cho mỗi một trong ba thành phần màu) đƣợc sử dụng để biểu diễn nội dung màu của mỗi ảnh, các mômen màu là một biểu diễn rất nén so với các đặc trƣng màu khác. Do biểu diễn rất nén này, nó có thể cũng giảm khả năng phân biệt. Thông thƣờng, các mômen màu có thể đƣợc sử dụng nhƣ sơ duyệt lần đầu để giảm không gian tìm kiếm trƣớc khi các đặc trƣng màu phức tạp khác đƣợc sử dụng cho tra cứu. 1.2.2 Kết cấu Kết cấu là một đặc tính quan trọng khác của ảnh. Các biểu diễn kết cấu đa dạng đã đƣợc nghiên cứu trong nhận dạng mẫu và thị giác máy tính. Về cơ bản, các phƣơng pháp biểu diễn kết cấu có thể đƣợc phân ra thành hai loại: cấu trúc và thống kê. Các phƣơng pháp cấu trúc, gồm toán tử hình thái và đồ thị kề, mô tả kết cấu bởi nhận dạng cấu trúc gốc và các luật sắp đặt của chúng. Chúng có chiều hƣớng hiệu quả nhất khi đƣợc áp dụng với các kết cấu đều. Các phƣơng pháp thống kê, gồm các kỹ thuật phổ năng lƣợng Fourier, các ma trận đồng khả năng, phân tích thành phần chính bất biến - trƣợt, đặc trƣng Tamura, phân rã Wold, trƣờng ngẫu nhiên Markov (Markov random field), mô hình fractal, và lọc đa phân giải nhƣ biến đổi Gabor và sóng, mô tả kết cấu bằng phân bố thống kê của cƣờng độ ảnh. Một số biểu diễn kết cấu [15], đƣợc sử dụng thƣờng xuyên và đã đƣợc chứng minh là hiệu quả trong tra cứu ảnh dựa vào nội dung. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn