ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ -----***----- Nguyễn Hữu Quỳnh NGHIÊN CỨU CẢI TIẾN MỘT SỐ PHƯƠNG PHÁP TRA CỨU ẢNH SỬ DỤNG ĐẶC TRƯNG ẢNH Chuyên ngành : Khoa học máy tính Mã số : 62 48 01 01 LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. PGS.TS Ngô Quốc Tạo 2. PGS.TS Đinh Mạnh Tường Hà Nội - 2010 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết quả đƣợc viết chung với các tác giả khác đều đƣợc sự đồng ý của đồng tác giả trƣớc khi đƣa vào luận án. Các kết quả nêu trong luận án là trung thực và chƣa từng đƣợc ai công bố trong các công trình nào khác. Tác giả Nguyễn Hữu Quỳnh 1 Lời cảm ơn Thực hiện luận án tiến sĩ là một việc khó, nhƣng là một nhiệm vụ đáng làm. Tôi rất hạnh phúc khi thực hiện xong luận án tiến sĩ, và quan trọng hơn là những gì tôi đã học đƣợc trong suốt ba năm qua. Bên cạnh kiến thức tôi thu đƣợc, tôi đã học đƣợc phƣơng pháp nghiên cứu một cách độc lập. Sự thành công này không đơn thuần bởi sự nỗ lực của cá nhân tôi, mà còn có sự hỗ trợ và giúp đỡ của thầy giáo hƣớng dẫn và nhiều đồng nghiệp khác. Nhân cơ hội này, tôi muốn bày tỏ lời cảm ơn của tôi đến họ. Đầu tiên, tôi muốn cảm ơn đến hai thầy giáo hƣớng dẫn của tôi, PGS TS Ngô Quốc Tạo và PGS TS Đinh Mạnh Tƣờng, vì sự hƣớng dẫn tận tình và khoa học. Đó là một cơ hội lớn cho tôi để đƣợc nghiên cứu dƣới sự hƣớng dẫn của hai thầy. Cảm ơn rất nhiều tới hai thầy vì sự hƣớng dẫn tôi cách đặt ra các câu hỏi nghiên cứu, hiểu các vấn đề, và viết các bài báo khoa học. Tôi trân trọng cảm ơn Bộ môn Khoa học máy tính, Khoa Công nghệ thông tin, Phòng Đào tạo Sau Đại học - Nghiên cứu Khoa học, Ban giám hiệu trƣờng Đại học Công nghệ đã tạo điều kiện thuận lợi cho tôi trong suốt quá trình thực hiện luận án. Tôi bày tỏ sự cảm ơn đến PGS TS Vũ Đức Thi, PGS TS Lƣơng Chi Mai, PGS TS Nguyễn Thanh Thủy vì sự giúp đỡ của họ cho các đề xuất và các trao đổi trong nghiên cứu của tôi. Tôi cũng bày tỏ sự cảm ơn đến PGS TS Đàm Xuân Hiệp – Hiệu trƣởng trƣờng Đại học Điện lực, ngƣời đã động viên và tạo điều kiện về thời gian và tài chính cho tôi trong việc công bố các bài báo trên các hội nghị và tạp chí quốc tế. Tôi muốn cảm ơn đến các cán bộ, giảng viên trong khoa Công nghệ thông tin – Trƣờng Đại học Điện lực đã cổ vũ động viên và sát cánh bên tôi trong quá trình nghiên cứu. 2 Tôi muốn cảm ơn những thành viên của đề tài nghiên cứu cơ bản NCCB200706 về sự tài trợ tài chính và các góp ý rất hữu ích về các bài báo đƣợc công bố trên các hội nghị và tạp chí quốc tế. Tôi cảm ơn tất cả những ngƣời bạn của tôi. Những ngƣời luôn chia sẻ và cổ vũ tôi trong những lúc khó khăn và tôi luôn ghi nhớ điều đó. Cuối cùng, tôi xin bày tỏ lòng biết ơn vô hạn đối với cha mẹ và gia đình đã luôn ủng hộ, giúp đỡ tôi. 3 MỤC LỤC PHẦN MỞ ĐẦU ..................................................................................................14 1. Tính cấp thiết của luận án .............................................................................. 14 2. Mục tiêu của luận án ...................................................................................... 16 3. Các đóng góp của luận án .............................................................................. 16 4. Bố cục của luận án ......................................................................................... 17 Chƣơng 1. TỔNG QUAN VỀ TRÍCH RÚT ĐẶC TRƢNG VÀ TRA CỨU ẢNH DỰA VÀO ĐẶC TRƢNG ...................................................................................18 1.1 Các đặc trƣng ............................................................................................... 18 1.1.1 Các đặc trƣng toàn cục và cục bộ ........................................................... 18 1.1.2 Các đặc trƣng thị giác trong tra cứu ảnh ................................................. 19 1.2 Kiến trúc của một hệ thống tra cứu ảnh dựa vào đặc trƣng thị giác ............... 19 1.3 Trích rút đặc trƣng ....................................................................................... 21 1.3.1 Đặc trƣng màu ....................................................................................... 21 1.3.2 Lƣợng hóa màu ...................................................................................... 23 1.3.3 Biểu diễn màu ........................................................................................ 23 1.3.3.1 Lƣợc đồ màu ................................................................................... 23 1.3.3.2 Lƣợc đồ màu toàn cục GCH ............................................................ 24 1.3.3.3 Lƣợc đồ màu cục bộ LCH ............................................................... 26 1.3.3.4 Véc tơ gắn kết màu ......................................................................... 28 1.3.3.5 Tƣơng quan màu ............................................................................. 28 1.3.3.6 Các màu trội .................................................................................... 29 1.3.3.7 Mô men màu ................................................................................... 29 1.3.4 Thông tin không gian ............................................................................. 30 4 1.3.5 Phân vùng .............................................................................................. 31 1.4 Các độ đo tƣơng tự ....................................................................................... 32 1.5 Đánh giá hiệu năng tra cứu........................................................................... 37 1.6 Các hệ thống VFBIR .................................................................................... 38 1.7 Kết luận và định hƣớng nghiên cứu .............................................................. 40 Chƣơng 2. PHƢƠNG PHÁP TRA CỨU DỰA VÀO LƢỢC ĐỒ MÀU KHỐI .....42 2.1 Lƣợc đồ màu khối ........................................................................................ 42 2.2 Phƣơng pháp tra cứu dựa vào lƣợc đồ màu khối ........................................... 44 2.2.1 Giới thiệu .............................................................................................. 44 2.2.2 Phƣơng pháp tra cứu đề xuất HG ........................................................... 47 2.2.2.1 Khái niệm về đồ thị hai phía............................................................ 47 2.2.2.2. Phƣơng pháp HG............................................................................ 48 2.3 Phƣơng pháp cải tiến IHG ............................................................................ 53 2.3.1 Khái niệm về sự tƣơng tự lý tƣởng giữa hai dải ..................................... 53 2.3.2 Lý do đề xuất phƣơng pháp IHG ............................................................ 54 2.3.3 Phƣơng pháp IHG .................................................................................. 54 2.4 Các thực nghiệm .......................................................................................... 60 2.4.1 Môi trƣờng thực nghiệm ........................................................................ 60 2.4.2 Các kết quả thực nghiệm........................................................................ 61 2.4.2.1 Kết quả thực nghiệm với phƣơng pháp HG ..................................... 61 2.4.2.2 Kết quả thực nghiệm với phƣơng pháp IHG .................................... 65 2.5 Kết luận ....................................................................................................... 69 Chƣơng 3. PHƢƠNG PHÁP TRA CỨU DỰA VÀO VÙNG ẢNH .....................71 3.1 Biểu diễn ảnh sử dụng phƣơng pháp cây tứ phân ......................................... 71 3.2 Phƣơng pháp tra cứu ảnh sử dụng đặc trƣng của vùng ảnh ........................... 73 3.2.1 Giới thiệu .............................................................................................. 73 5 3.2.2 Trích rút đặc trƣng ................................................................................. 74 3.2.2.1 Trích rút màu và thông tin không gian ............................................. 74 3.2.2.2 Trích rút các cụm màu thuần nhất. .................................................. 82 3.2.3 Độ tƣơng tự giữa hai ảnh ....................................................................... 87 3.2.4 Các thực nghiệm .................................................................................... 88 3.2.4.1 Môi trƣờng thực nghiệm ................................................................. 88 3.2.4.2 Kết quả thực nghiệm ....................................................................... 88 3.3 Kết luận ....................................................................................................... 96 Chƣơng 4. XÂY DỰNG ỨNG DỤNG TRA CỨU ẢNH DỰA VÀO NỘI DUNG98 4.1 Thiết kế hệ thống tổng quát LVFIR .............................................................. 98 4.2 Module tra cứu group1 ............................................................................... 100 4.3 Module tra cứu group2 ............................................................................... 105 4.4 Một số kết quả ........................................................................................... 110 4.4.1 So sánh kỹ thuật LCH, CCH với HG và IHG ....................................... 110 4.4.2 So sánh kỹ thuật QT, CBC và CCV với CSI và CCS ........................... 112 4.5 Kết luận. .................................................................................................... 116 KẾT LUẬN ........................................................................................................ 117 DANH MỤC CÁC CÔNG TRÌNH CÔNG BỐ .................................................. 119 TÀI LIỆU THAM KHẢO .................................................................................. 120 6 DANH MỤC CÁC CHỮ VIẾT TẮT Ký hiệu Diễn giải Black Màu đen CSDL Cơ sở dữ liệu CBC Color Based Cluster CCH Color/Cell Histogram (Lƣợc đồ màu khối) CCS Cluster of Colors and Space (Cụm màu và không gian) CCV Color Coherence Vectors (Véc tơ gắn kết màu) CSI Color and Spatial Information (Màu và thông tin không gian) DistancebyColor Khoảng cách theo màu DRC Distance by Region Comparing EdgeDistance Khoảng cách theo cạnh EMD Earth Mover Distance (Khoảng cách Earth Mover) GCH Global Color Histogram (Lƣợc đồ màu toàn cục) Gray Màu xám HG Histogram Graph (Đồ thị lƣợc đồ) Hue Sắc màu IHG Improving Histogram Graph method (Phƣơng pháp cải tiến đồ thị lƣợc đồ) KLT Karhunen–Loeve transform (Biến đổi Karhunen–Loeve) LCH Local Color Histogram (Lƣợc đồ màu cục bộ) LVFIR Local Visual Feature-based Image Retrieval (Tra cứu ảnh dựa vào đặc trƣng thị giác cục bộ) MCM Minimum Cost Matching (Giá trị đối sánh cực tiểu) MTM Mathematical Transform to Munsell (Biến đổi toán học sang hệ thống màu Munsell) 7 Precision Chính xác Quantization Lƣợng hóa QT Quad Tree (Cây tứ phân) Recall Hồi tƣởng RGB Red (Đỏ), Green (Xanh lục), Blue (xanh lơ) SR Spatial Relationship (Quan hệ không gian) Union Hợp VFBIR Visual Feature Based Image Retrieval (Tra cứu ảnh dựa vào đặc trƣng thị giác) White Màu trắng 8 DANH MỤC CÁC HÌNH Hình 1.1. Kiến trúc hệ thống tra cứu ảnh dựa vào đặc trƣng thị giác. ....................20 Hình 1.2. Hai ảnh khác nhau nhƣng có cùng lƣợc đồ màu. ...................................22 Hình 1.3. Từ trái sang: ảnh gốc sử dụng 256 màu, đƣợc lƣợng hoá trong 8 dải, và đƣợc lƣợng hoá trong 64 dải sử dụng không gian màu RGB. ................................23 Hình 1.4. Ba ảnh I1, I2 và I3 và các lƣợc đồ màu tƣơng ứng của chúng. .................25 Hình 1.5. Tính khoảng cách giữa ảnh I1 và I2 sử dụng LCH, d LCH ( I 1 , I 2 )  1.319 , dGCH ( I 1 , I 2 )  0.088 . ............................................................................................26 Hình 1.6. Tính khoảng cách giữa các ảnh I1 và I3 sử dụng LCH, d LCH ( I 1 , I 3 )  0.707 , dGCH ( I 1 , I 3 )  0.088 . ...........................................................27 Hình 1.7. Tính khoảng cách giữa các ảnh I2 và I3 sử dụng LCH d LCH ( I 2 , I 3 )  0.707 , dGCH ( I 2 , I 3 )  0 . ...............................................................27 Hình 1.8. Recall và Precision cho các kết quả truy vấn. ........................................38 Hình 2.1. Một ảnh đƣợc chia thành 9 khối ảnh và ba lƣợc đồ màu khối của nó. ....43 Hình 2.2. Ảnh I và ảnh I’. .....................................................................................45 Hình 2.3. Lƣợc đồ màu khối theo màu black và white biểu diễn ảnh I. .................45 Hình 2.4. Lƣợc đồ màu khối theo màu black và white biểu diễn ảnh I’. ................45 Hình 2.5. Tính khoảng cách của ảnh I và I’ theo màu black. .................................46 Hình 2.6. Tính khoảng cách của ảnh I và I’ theo màu white. .................................46 Hình 2.7. Các khối ảnh của mỗi ảnh đƣợc đánh số từ trong ra và ngƣợc chiều kim đồng hồ. ...............................................................................................................56 Hình 2.8. Lƣợc đồ màu khối theo màu black của hai ảnh I1 và I2. .........................56 Hình 2.9. Đồ thị hai phía biểu thị mối quan hệ của các dải của lƣợc đồ màu khối của ảnh I1 và I2 theo màu black. ..................................................................................57 9 Hình 2.10. Các ảnh mẫu của các truy vấn từ 1 đến 6. ............................................61 Hình 2.11. So sánh LCH, CCH với HG theo các truy vấn 1, 2, 3 và 4 dƣới dạng Recall - Precision. ................................................................................................63 Hình 2.12. So sánh LCH, CCH với HG theo các truy vấn 5 và 6 dƣới dạng Recall - Precision...............................................................................................................64 Hình 2.13. Các ảnh mẫu của các truy vấn từ 1 đến 6. ............................................65 Hình 2.14. So sánh HG với IHG theo các truy vấn 1 và 2 dƣới dạng Recall – Precision...............................................................................................................67 Hình 2.15. So sánh HG với IHG và SR theo các truy vấn 3, 4, 5 và 6 dƣới dạng Recall-Precision. ..................................................................................................68 Hình 2.16. Biểu đồ so sánh tốc độ của phƣơng pháp HG và IHG. .........................69 Hình 3.1 Ảnh gốc. ................................................................................................71 Hình 3.2. Cây tứ phân biểu diễn ảnh cho trong Hình 3.1. ......................................72 Hình 3.3 Cây biểu diễn ảnh cho trong Hình 3.1. ...................................................73 Hình 3.4. Ảnh I cỡ 1010 điểm ảnh. ...................................................................77 Hình 3.5. Ảnh I sau khi đƣợc tách ra thành hai vùng BR1 và BR2. ......................78 Hình 3.6. Vùng BR2 sau khi đƣợc tách ra thành hai vùng BR2,1 và BR2,2...............80 Hình 3.7. Ảnh gồm 610 điểm ảnh. ......................................................................85 Hình 3.8. Các ảnh mẫu của các truy vấn từ 1 đến 6. ..............................................89 Hình 3.9. So sánh CSI với QT và CBC theo các truy vấn 1 và 2 dƣới dạng Recall- Precision...............................................................................................................90 Hình 3.10. So sánh CSI với QT, CBC và SR theo các truy vấn 3, 4, 5 và 6 dƣới dạng Recall – Precision. .......................................................................................92 Hình 3.11. Các ảnh mẫu của các truy vấn từ 1 đến 6. ............................................93 Hình 3.12. So sánh Recall – Precision theo các truy vấn 1,2 và 3 của CCS với CCV và CSI. .................................................................................................................94 10 Hình 3.13. So sánh Recall-Precision theo các truy vấn 4, 5 và 6 của CCS với CCV, CSI và SR. ............................................................................................................96 Hình 4.1. Kiến trúc của hệ thống LVFIR. .............................................................99 Hình 4.2. Kiến trúc của Module tra cứu group1. ................................................. 100 Hinh 4.3. Màn hình chính của module tra cứu group1. ...................................... 102 Hình 4.4. Giao diện tra cứu khi lựa chọn đặc điểm màu sử dụng LCH. ............... 102 Hình 4.5. Giao diện tra cứu khi lựa chọn đặc điểm màu sử dụng CCH................ 103 Hình 4.6. Giao diện tra cứu khi lựa chọn đặc điểm màu sử dụng HG. ................. 103 Hình 4.7. Giao diện tra cứu khi lựa chọn đặc điểm màu sử dụng IHG. ................ 104 Hình 4.8. Kiến trúc của Module tra cứu group2. ................................................. 105 Hinh 4.9. Giao diện sử dụng kỹ thuật QT, CBC và CCV của module tra cứu group2. ............................................................................................................... 106 Hinh 4.10. Giao diện sử dụng kỹ thuật CSI và CCS của module tra cứu group2.107 Hình 4.11. Giao diện tra cứu khi sử dụng phƣơng pháp QT với ảnh truy vấn. ..... 107 Hình 4.12. Giao diện tra cứu khi sử dụng phƣơng pháp CBC với ảnh truy vấn. ..108 Hình 4.13. Giao diện tra cứu khi sử dụng phƣơng pháp CCV với ảnh truy vấn. ..108 Hình 4.14. Giao diện tra cứu khi sử dụng phƣơng pháp CSI với ảnh truy vấn. .... 109 Hình 4.15. Giao diện tra cứu khi sử dụng phƣơng pháp CCS với ảnh truy vấn....109 Hình 4.16. Kết quả thực hiện truy vấn 1. ............................................................ 110 Hình 4.17. Kết quả thực hiện truy vấn 2. ............................................................ 111 Hình 4.18. Kết quả thực hiện truy vấn 3. ............................................................ 112 Hình 4.19. Kết quả thực hiện truy vấn 1. ............................................................ 113 Hình 4.20. Kết quả thực hiện truy vấn 2. ............................................................ 114 Hình 4.21. Kết quả thực hiện truy vấn 3. ............................................................ 115 11 DANH MỤC CÁC BẢNG Bảng 2.1. Các loại của ảnh truy vấn và các ảnh liên quan. ....................................61 Bảng 2.8. Các loại của ảnh truy vấn và các ảnh liên quan. ...................................65 Bảng 3.1. Tính độ lệch DXselectedrow cho phân hoạch theo dòng của ảnh I . ............78 Bảng 3.2. Tính độ lệch DXselectedcol cho phân hoạch theo cột của ảnh I . ................79 Bảng 3.3. Tính độ lệch DXselectedrow cho phân hoạch theo dòng của vùng BR2 . ......80 Bảng 3.4. Tính độ lệch DXselectedcol cho phân hoạch theo cột của vùng BR2 . ..........81 Bảng 3.5. Tính toán giá trị của vi. .........................................................................85 Bảng 3.6. Tính toán giá trị của hj. .........................................................................86 Bảng 3.7. Các loại của ảnh truy vấn và các ảnh liên quan. ....................................89 Bảng 3.14. Các loại của ảnh truy vấn và tập ảnh liên quan. ...................................92 Bảng 3.17. Các kết quả của truy vấn 3. .................................................................94 Bảng 3.20. Các kết quả của truy vấn 3. .................................................................95 12 13 PHẦN MỞ ĐẦU 1. Tính cấp thiết của luận án Những năm gần đây, chúng ta đã chứng kiến sự tăng nhanh kích cỡ của các tập hợp ảnh số cùng với sự phát triển bùng nổ của các ứng dụng Internet. Hàng ngày, việc sử dụng các thiết bị thu nhận ảnh sinh ra nhiều giga-bytes dữ liệu ảnh. Một lƣợng lớn thông tin ảnh, khoảng hàng trăm triệu ảnh [12, 59, 70, 79], đã đƣợc đƣa lên Internet. Tuy nhiên, không thể truy cập hoặc sử dụng thông tin trong các tập ảnh khổng lồ này, nếu chúng không đƣợc tổ chức để tra cứu hiệu quả trên toàn bộ dữ liệu ảnh. Quản trị cơ sở dữ liệu (CSDL) và thị giác máy là hai cộng đồng có đóng góp chính cho lĩnh vực tra cứu ảnh. Hai cộng đồng này tiếp cận tra cứu ảnh từ hai góc độ khác nhau, dựa vào văn bản mô tả ảnh và dựa vào đặc trƣng thị giác của bản thân ảnh. Sử dụng các kỹ thuật dựa vào văn bản mô tả ảnh hoặc từ khoá mô tả ảnh để quản lý CSDL ảnh là cách đơn giản thƣờng đƣợc sử dụng. Các từ khoá mô tả ảnh cung cấp thông tin nội dung mô tả ảnh trong một CSDL ảnh đã cho, nhƣng để mô tả các ảnh đủ chi tiết, cần một tập từ khoá rất lớn và phức tạp. Một hạn chế nữa của cách tiếp cận này là cần nhân lực đƣợc đào tạo kỹ lƣỡng để xây dựng các từ khoá đối với mỗi ảnh và chọn các từ khoá phù hợp cho tra cứu các ảnh hiệu quả. Công việc mô tả nội dung ảnh thủ công này tốn nhiều thời gian, chi phí cao và phụ thuộc vào cảm nhận chủ quan của chuyên viên kỹ thuật theo nghĩa cùng một nội dung ảnh, những ngƣời khác nhau có thể đƣa ra cảm nhận về ảnh khác nhau. Cảm nhận chủ quan và mô tả nội dung ảnh không chính xác là nguyên nhân làm cho so sánh sai trong lúc tra cứu. Hơn nữa, hệ thống dựa vào từ khoá rất khó thay đổi về sau. Do đó, cần có cách tiếp cận mới để khắc phục các hạn chế này. Để khắc phục các khó khăn ở trên, tra cứu ảnh dựa vào đặc trƣng thị giác của ảnh đã đƣợc đề xuất. Ý tƣởng cơ bản của cách tiếp cận này là sử dụng kỹ thuật trích 14 rút đặc trƣng thị giác một cách tự động để cho ra các mô tả nội dung ảnh một cách trực tiếp từ chính bản thân ảnh. Hệ thống tra cứu ảnh dựa vào đặc trƣng thị giác sẽ xác định các ảnh trong CSDL ảnh có đặc trƣng thị giác tƣơng tự với ảnh truy vấn theo hai pha: Pha 1, tất cả các ảnh trong CSDL đƣợc xử lý, đƣợc trích chọn đặc trƣng thị giác. Quá trình xử lý và trích chọn đặc trƣng thị giác đƣợc thực hiện một cách tự động ngay khi các ảnh đƣợc nhập vào CSDL. Quá trình này gán cho mỗi ảnh một tập các ký hiệu mô tả, các ký hiệu mô tả ảnh này sẽ đƣợc lƣu trữ trong CSDL và đƣợc sử dụng trong pha tiếp theo. Pha 2, trích rút các đặc trƣng thị giác của ảnh truy vấn và so sánh các đặc trƣng này với các đặc trƣng thị giác của ảnh trong CSDL theo một độ đo tƣơng tự nào đó. Các ảnh trong CSDL đƣợc phân hạng theo mức độ tƣơng tự của nó với ảnh truy vấn. Ảnh có hạng cao nhất đƣợc truy xuất. Trích rút nội dung thị giác của các ảnh hiệu quả và đo độ tƣơng tự giữa các ảnh dựa trên đặc trƣng thị giác là hai phần quan trọng trong tra cứu ảnh dựa vào đặc trƣng thị giác. Các nghiên cứu gần đây trong tra cứu ảnh tập trung vào trích chọn đặc trƣng thị giác gồm màu, kết cấu, hình dạng và thông tin không gian. Màu là đặc trƣng đƣợc sử dụng rộng rãi nhất cho tra cứu ảnh do tính toán nhanh, tƣơng đối ổn định với các biến dạng nhỏ, thay đổi về kích thƣớc và hƣớng. Một số phƣơng pháp đã đƣợc đề xuất nhƣ: Phƣơng pháp lƣợc đồ màu toàn cục và lƣợc đồ màu cục bộ [51], phƣơng pháp véc tơ gắn kết màu [16], phƣơng pháp tƣơng quan màu [30], phƣơng pháp lƣợc đồ màu khối [54],… Tuy nhiên, hầu hết các phƣơng pháp này đều gặp phải vấn đề sử dụng nhiều không gian để lƣu trữ các lƣợc đồ màu biểu diễn ảnh, độ chính xác tra cứu không cao, độ phức tạp tính toán lớn, nhạy cảm với quay và dịch chuyển, không cho phép nhận biết các đối tƣợng tƣơng tự có màu khác nhau [7, 40, 52, 69]. Do đó, việc đề xuất các giải pháp tra cứu ảnh dựa vào đặc trƣng thị giác để khắc phục đƣợc các hạn chế ở trên là một nhu cầu cấp thiết. Đó cũng là lý do mà 15 luận án chọn đề tài ―Nghiên cứu cải tiến một số phƣơng pháp tra cứu ảnh sử dụng đặc trƣng ảnh‖. 2. Mục tiêu của luận án Mục tiêu của luận án là nghiên cứu đề xuất một số phƣơng pháp tra cứu ảnh sử dụng đặc trƣng màu và thông tin không gian. Các phƣơng pháp này sẽ hƣớng tới giải quyết các vấn đề về giảm không gian lƣu trữ các lƣợc đồ màu biểu diễn ảnh, ít nhạy cảm với quay và dịch chuyển, giảm độ phức tạp tính toán và tăng độ chính xác tra cứu. 3. Các đóng góp của luận án Trong luận án này, tác giả nghiên cứu đề xuất các kỹ thuật tra cứu ảnh dựa vào đặc trƣng của vùng ảnh gồm: phƣơng pháp HG (Histogram Graph) [42], phƣơng pháp IHG (Improving Histogram Graph) [43], phƣơng pháp CSI (Color and Spatial Information) [45] và phƣơng pháp CCS (Cluster of Colors and Space) [46]: - Phƣơng pháp tra cứu ảnh dựa vào đặc trƣng màu, có tên là HG [42]. Đặc điểm của phƣơng pháp này là sử dụng ít không gian lƣu trữ các lƣợc đồ màu biểu diễn ảnh và ít nhạy cảm với quay và dịch chuyển. - Để tăng cƣờng phƣơng pháp HG, chúng tôi đã đề xuất phƣơng pháp IHG [43], nhằm giảm thời gian và tăng độ chính xác tra cứu của phƣơng pháp HG nhƣng vẫn sử dụng ít không gian lƣu trữ các lƣợc đồ màu biểu diễn ảnh và ít nhạy cảm với quay và dịch chuyển. - Phƣơng pháp CSI [45] trích rút đặc trƣng màu và thông tin không gian của các vùng ảnh và sử dụng trong quá trình tra cứu để nâng cao hiệu năng tra cứu. - Phƣơng pháp CCS [46] phân hoạch ảnh thành các cụm màu thuần nhất (các cụm màu này có thể có kích cỡ khác nhau) và trích rút thông tin màu và không gian của mỗi vùng phục vụ quá trình tra cứu. 16 - Xây dựng hệ thống tra cứu ảnh dựa vào đặc trƣng thị giác có tên là LVFIR (Local Visual Feature-based Image Retrieval) trên cơ sở các kỹ thuật đề xuất của tác giả. Hệ thống này gồm hai module chính là module tiền xử lý và module tra cứu. 4. Bố cục của luận án Luận án này đƣợc bố cục thành bốn chƣơng, gồm 125 trang. Chƣơng 1 giới thiệu tổng quan về trích rút đặc trƣng và tra cứu ảnh dựa vào đặc trƣng thị giác và đƣa ra một số kết luận và định hƣớng cho nghiên cứu. Chƣơng 2 trình bày kỹ thuật tra cứu ảnh dựa vào lƣợc đồ màu khối, có tên là HG [42] và cải tiến của nó, có tên là IHG [43]. Chƣơng 3 trình bày kỹ thuật trích rút đặc trƣng của vùng ảnh sử dụng trong quá trình tra cứu ảnh, có tên là CSI [45] và CCS [46]. Chƣơng 4 trình bày thiết kế và thực hiện hệ thống thực nghiệm tra cứu ảnh dựa vào đặc trƣng thị giác (sử dụng các kỹ thuật đƣợc đề xuất trong Chƣơng 2 và Chƣơng 3) LVFIR, cùng với một số kết quả. Cuối cùng, chúng tôi đƣa ra một số kết luận và đề xuất các nghiên cứu trong tƣơng lai. 17 Chƣơng 1. TỔNG QUAN VỀ TRÍCH RÚT ĐẶC TRƢNG VÀ TRA CỨU ẢNH DỰA VÀO ĐẶC TRƢNG Trong chƣơng này, chúng tôi sẽ giới thiệu một số khái niệm và kỹ thuật cơ bản về trích rút đặc trƣng và tra cứu ảnh dựa vào đặc trƣng thị giác gồm: các đặc trƣng, kiến trúc của hệ thống tra cứu ảnh dựa vào đặc trƣng thị giác, trích rút đặc trƣng, các độ đo tƣơng tự, đánh giá hiệu năng tra cứu và giới thiệu một số hệ thống tra cứu ảnh dựa vào đặc trƣng thị giác. Đặc biệt chúng tôi nhấn mạnh vào đặc trƣng màu. Cuối cùng chúng tôi sẽ đƣa ra một số kết luận và định hƣớng cho nghiên cứu. 1.1 Các đặc trƣng Dữ liệu ảnh thô không đƣợc sử dụng trực tiếp trong hầu hết các hệ thống thị giác máy vì hai lý do: Thứ nhất, tốn nhiều không gian để lƣu trữ ảnh và độ phức tạp tính toán lớn. Thứ hai, nhiều thông tin của ảnh là dƣ thừa và/ hoặc không hữu ích. Thay vì sử dụng toàn bộ ảnh, chúng ta chỉ cần sử dụng một biểu diễn quan trọng nhất. Bƣớc tìm biểu diễn đƣợc gọi là trích rút đặc trưng và kết quả của biểu diễn là véc tơ đặc trƣng. Trích rút đặc trƣng có thể xem nhƣ việc ánh xạ ảnh từ không gian ảnh sang không gian đặc trƣng. Liên quan đến nội dung ảnh, các đặc trƣng ảnh có thể đƣợc phân thành đặc trƣng thị giác và đặc trƣng ngữ nghĩa. Đặc trƣng thị giác có thể đƣợc phân loại tiếp thành đặc trƣng chung và đặc trƣng theo lĩnh vực [12, 70, 79]. Các đặc trƣng thị giác chung gồm màu, kết cấu, hình dạng và quan hệ không gian. Các đặc trƣng theo lĩnh vực bao gồm tri thức về lĩnh vực nhƣ mặt ngƣời, vân tay,... Đặc trƣng ngữ nghĩa không dễ dàng đƣợc trích rút và thƣờng đƣợc suy diễn từ các đặc trƣng mức thấp hoặc sử dụng văn bản mô tả ảnh. 1.1.1 Các đặc trƣng toàn cục và cục bộ Các đặc trƣng ảnh có thể là toàn cục hoặc cục bộ. Nếu các đặc trƣng biểu diễn nội dung thị giác của toàn bộ ảnh, các đặc trƣng này đƣợc gọi là các đặc trƣng toàn 18 cục. Ngƣợc lại, các đặc trƣng biểu diễn nội dung thị giác của một phần ảnh thì đƣợc gọi là đặc trƣng cục bộ. 1.1.2 Các đặc trƣng thị giác trong tra cứu ảnh Đặc trƣng màu: Màu có vai trò quan trọng trong tra cứu ảnh dựa vào đặc trƣng thị giác. Các màu có thể đƣợc biểu diễn trong các không gian màu khác nhau nhƣ RGB, HSV,... Đặc trƣng kết cấu: Kết cấu là tập các điểm trong một vùng thỏa mãn ràng buộc hay qui luật nào đó. Đặc trƣng này khá quan trọng cho tra cứu ảnh. Về cơ bản, các phƣơng pháp biểu diễn kết cấu có thể đƣợc chia thành hai loại: các phƣơng pháp cấu trúc và các phƣơng pháp thống kê. Các toán tử đƣợc dùng phát hiện cấu trúc bao gồm các toán tử hình thái và đồ thị liền kề xác định các kết cấu cơ sở và luật phân bố của chúng. Các phƣơng pháp thống kê bao gồm: Phƣơng pháp phổ năng lƣợng Fourier, Tamura, trƣờng ngẫu nhiên Markov, mô hình fractal, các bộ lọc đa phân giải nhƣ biến đổi Gabor và biến đổi dạng sóng... thể hiện kết cấu bằng sự phân bố thống kê của độ sáng của các điểm ảnh. Đặc trƣng hình dạng: Các đặc trƣng hình dạng có quan hệ chặt chẽ với mô tả vùng hoặc các đối tƣợng đƣợc phân đoạn. Đặc trƣng hình dạng đƣợc trích rút từ các đƣờng bao đối tƣợng hoặc vùng chứa đối tƣợng. 1.2 Kiến trúc của một hệ thống tra cứu ảnh dựa vào đặc trƣng thị giác Quá trình thực hiện của hệ thống tra cứu ảnh dựa vào đặc trƣng thị giác đƣợc chia thành hai giai đoạn: Giai đoạn 1: Tạo lập CSDL ảnh cùng với thông tin đặc trƣng (ngoại tuyến) Trích rút đặc trƣng của ảnh trong CSDL ảnh. Quá trình xử lý gồm lọc, chuẩn hóa, phân đoạn và nhận dạng đối tƣợng. Đầu ra của bƣớc này là một tập các mô tả nội dung các ảnh trong CSDL. Giai đoạn 2: Tra cứu ảnh (trực tuyến) 19