Tài liệu Nghiên cứu phương pháp tra cứu ảnh dựa trên nội dung và xây dựng hệ thống tra cứu cây thuốc

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- NGUYỄN HUY HOÀNG NGHIÊN CỨU PHƯƠNG PHÁP TRA CỨU ẢNH DỰA TRÊN NỘI DUNG VÀ XÂY DỰNG HỆ THỐNG TRA CỨU CÂY THUỐC Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 60.48.01 TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI – 2013 Luận văn được hoàn thành tại: HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Người hướng dẫn khoa học: ……………………………… (Ghi rõ học hàm, học vị) Phản biện 1: ……………………………………………… Phản biện 2: …………………………………………….. Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công nghệ Bưu chính Viễn thông Vào lúc: ..... giờ ...... ngày ....... tháng ....... .. năm ............... Có thể tìm hiểu luận văn tại: - Thư viện của Học viện Công nghệ Bưu chính Viễn thông 1 MỤC LỤC MỞ ĐẦU .........................................................................4 CHƯƠNG 1 .....................................................................7 TỔNG QUAN VỀ TRA CỨU ẢNH DỰA TRÊN NỘI DUNG (CONTENT-BASED IMAGE RETRIEVAL CBIR) ..............................................................................7 1.1. Giới thiệu truy vấn ảnh dựa trên nội dung ............7 1.2. Mô hình xử lý ......................................................8 1.3. Các thành phần chính của một hệ thống CBIR .....9 1.4. Các chức năng cơ bản của hệ thống CBIR.......... 10 1.5. Một số hệ thống tra cứu ảnh dựa trên nội ........... 10 1.5.1. Hệ thống QBIC(Query By Image Content)10 1.5.2. Hệ thống Virage ....................................... 10 1.5.3. Hệ thống RetrievalWare ........................... 10 1.5.4. Hệ thống VisualSeek và WebSeek............ 10 1.5.5. Hệ thống Photobook ................................. 10 CHƯƠNG 2 ...................................................................11 PHƯƠNG PHÁP TRÍCH CHỌN ĐẶC TRƯNG ẢNH ..11 2.1. Trích chọn đặc trưng ảnh dựa trên màu sắc ........ 11 2.1.1. Lược đồ màu (Histogram) ........................ 11 2.1.2. Vector liên kết màu (Color Coherence Vector) ................................................................... 12 2.2. Trích chọn đặc trưng ảnh dựa trên kết cấu .......... 12 2.2.1. Ma trận đồng hiện (Co-occurence Matrix) 13 2 2.2.2. Phép biến đổi Wavelet .............................. 13 2.2.3. Các đặc trưng lọc Gabor .......................... 14 2.2.4. Các đặc trưng biến đổi sóng .................... 14 2.3. Trích chọn đặc trưng ảnh dựa trên hình dạng ..... 15 2.3.1. Trích chọn đặc trưng theo biên ................. 15 2.3.1.1. Lược đồ hệ số góc ............................ 15 2.3.1.2. Vector liên kết hệ số góc (Edge Direction Coherence Vector)......................... 16 2.3.2. Trích chọn đặc trưng theo vùng ................ 17 2.4. Trích chọn sử dụng điểm nổi bật ........................ 17 2.4.1. Đặc trưng cục bộ bất biến (SIFT) ............. 17 2.4.2. SURF ....................................................... 19 CHƯƠNG 3 ...................................................................20 CÀI ĐẶT THỬ NGHIỆM VÀ ỨNG DỤNG .................20 3.1. Cài đặt thử nghiệm ............................................. 20 3.1.1. Môi trường phát triển, cơ sở dữ liệu ......... 20 3.1.2. Phương pháp thực nghiệm ........................ 21 3.1.2.1. Lựa chọn mẫu thử nghiệm ................ 21 3.1.2.2. Phương pháp đánh giá ...................... 21 3.1.3. Thử nghiệm và kết quả ............................. 22 3.1.3.1. Tìm kiếm theo lược đồ màu .............. 22 3.1.3.2. Tìm kiếm theo lược đồ hệ số góc ...... 22 3.1.3.3. Tìm kiếm theo vector liên kết màu ... 22 3.1.3.4. Tìm kiếm theo AutoCorrelogram ...... 22 3 3.1.3.5. Tìm kiếm theo các đặc trưng cục bộ bất biến (SIFT) ................................................... 22 3.1.3.6. Tìm kiếm với SURF ......................... 22 3.1.4. Kết quả thực nghiệm và đánh giá.............. 22 3.2. Ứng dụng tra cứu cây thuốc ............................... 24 3.2.1. Phân tích yêu cầu ..................................... 24 3.2.2. Chức năng ứng dụng ................................ 24 3.2.3. Đánh giá ứng dụng ................................... 25 KẾT LUẬN ...................................................................26 4 MỞ ĐẦU Cùng với sự phát triển của công nghệ, đã có rất nhiều phương pháp được nghiên cứu để truy vấn thông tin dựa vào hình ảnh. Tuy nhiên, 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à phương pháp “Tra cứu ảnh dựa theo nội dung” (Content Based Image Retrieval - CBIR). Ý tưởng phương pháp này là trích chọn các đặc điểm dựa vào nội dung trực quan của ả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. Tra cứu ảnh dựa trên hình dạng sử dụng các đặc trưng hình dạng của các ảnh mục tiêu để tìm kiếm, nó là một khía cạnh rất quan trọng của tra cứu ảnh dựa trên nội dung. Hiện nay có nhiều hệ thống cho phép tra cứu thông tin dựa trên hình ảnh như như Google Image Swirl, Bing, Tiltomo, Tineye, Pixolution…Các hệ thống trên đã đưa ra các kết quả tìm kiếm rất tốt dựa trên ảnh mẫu. Tuy nhiên, hạn chế của các hệ thống trên là vẫn tồn tại sự nhập nhằng về dữ liệu, các thông tin chưa cô đọng theo chủ đề xác định, với bài toán đặt ra ở đây là cây thuốc. Với mục đích cuối cùng có thể xây dựng được một 5 hệ thống tra cứu cây thuốc dựa trên hình ảnh. Cho phép người Việt Nam nhận biết và sử dụng hiệu quả về các cây thuốc ở Việt Nam thông qua hình ảnh. Luận văn này sẽ đi sâu vào những nhiệm vụ chính như sau: - Nội dung + Nghiên cứu và đánh giá các kỹ thuật tra cứu ảnh theo nội dung. + Tìm hiểu cách thức nhận biết cây thuốc thông thường trong cuộc sống như qua lá, hoa, thân hay rễ…để từ đó có thể giới hạn đối tượng làm mẫu và truy vấn + Đề xuất sử dụng một số kỹ thuật khác và đưa ra sự so sánh với các hệ thống ảnh trước đó. + Từ đó đưa ra các phương pháp cải tiến và khắc phục những hạn chế hiện tại. + Thử nghiệm chương trình tra cứu ảnh theo nội dung thông qua mô hình truy vấn đề xuất và các kết quả đạt được như độ chính xác, tốc độ xử lý… - Yêu cầu cần giải quyết + Tìm hiểu kiến thức về các kỹ thuật xử lý ảnh. + Đưa ra được phạm vi đối tượng thực hiện để làm mẫu nhận dạng là lá, cây, hoa, hay tất cả. 6 + Xây dựng tập mẫu ảnh dựa trên đối tượng đã lựa chọn ở trên + Tham khảo các mã nguồn mở về xử lý ảnh cho quá trình cài đặt. + Nghiên cứu về tra cứu ảnh theo nội dung và các phương pháp trích chọn đặc trưng dựa trên các tài liệu nghiên cứu trước đó. Từ đó triển khai cài đặt thuật toán tra cứu. + Thực nghiệm dựa trên xây dựng và đánh giá các kết quả nghiên cứu. + Xây dựng hệ thống tra cứu ảnh dựa trên thực nghiệm và các đánh giá đã có. 7 CHƯƠNG 1 TỔNG QUAN VỀ TRA CỨU ẢNH DỰA TRÊN NỘI DUNG (CONTENT-BASED IMAGE RETRIEVAL - CBIR) Chương 1 luận văn giới thiệu tổng quan về phương pháp “Tra cứu ảnh dựa theo nội dung - CBIR” bao gồm khái niệm, mục đích, mô hình, thành phần, chức năng và một số hệ thống tra cứu ảnh dự trên nội dung. 1.1. Giới thiệu truy vấn ảnh dựa trên nội dung Tra cứu ảnh dựa theo nội dung (CBIR) có nguồn gốc từ năm 1992. Tra cứu ảnh theo nội dung là tra cứu thông tin trực quan (VIR - Visual Information Retrieval). Các yếu tố trực quan như màu sắc, kết cấu, hình dạng và bố cục 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. 8 1.2. Mô hình xử lý Để xây dựng hệ thống truy vấn ảnh, cần giải quyết 3 vấn đề chính sau • Rút trích các đặc trưng trên ảnh (Feature Exaction) • Xác định độ đo sự tương đồng giữa hai ảnh (Similarity Measure) • Lập chỉ mục cho CSDL ảnh (Image Indexing) Từ đó xây dựng nên các thành phần cho hệ thống truy vấn ảnh: Hệ thống truy vấn ảnh với cơ sở tri thức 9 1.3. Các thành phần chính của một hệ thống CBIR Hiện nay, trọng tâm chính của CBIR là nghiên cứu chủ yếu trên 3 chủ đề chính: Trích chọn đặc trưng: Các đặc trưng của hình ảnh bao gồm các đặc trưng nguyên thủy và các đặc trưng ngữ nghĩa/đặc trưng logic. Đặc trưng nguyên thủy như màu sắc, hình dạng, kết cấu và các mối quan hệ không gian được định lượng trong tự nhiên, chúng có thể được trích xuất tự động hoặc bán tự động. Đặc trưng logic cung cấp mô tả trừu tượng của dữ liệu hình ảnh ở các cấp độ khác nhau. Lập chỉ số hiệu quả: Để tạo điều kiện truy vấn hiệu quả và xử lý tìm kiếm, các chỉ số hình ảnh cần thiết được tổ chức thành các cấu trúc dữ liệu hiệu quả. Các cấu trúc như k-d-tree, R-tree family, R *- tree, quad-tree, và grid file (tập lưới) thường được sử dụng. Giao diện người dùng: Giao diện người dùng bao gồm một bộ xử lý truy vấn và trình duyệt để cung cấp các công cụ đồ họa tương tác, cơ chế truy vấn và truy cập cơ sở dữ liệu, theo thứ tự định sẵn. 10 1.4. Các chức năng cơ bản của hệ thống CBIR Những chức năng chính của một hệ thống bao gồm các nội dung sau: - Phân tích nội dung của nguồn thông tin và biểu diễn nội dung của các nguồn thông tin. - Phân tích các truy vấn của người dùng và biểu diễn chúng thành các dạng phù hợp với việc đối sánh với cơ sở sữ liệu nguồn. - Xác định chiến lược để đối sánh tìm kiếm truy vấn với thông tin được lưu trữ trong cơ sở dữ liệu. - Thực hiện các điều chỉnh cần thiết trong hệ thống dựa trên phản hồi từ người sử dụng hoặc những hình ảnh được tra cứu. 1.5. Một số hệ thống tra cứu ảnh dựa trên nội 1.5.1. Hệ thống QBIC (Query By Image Content) 1.5.2. Hệ thống Virage 1.5.3. Hệ thống RetrievalWare 1.5.4. Hệ thống VisualSeek và WebSeek 1.5.5. Hệ thống Photobook 11 CHƯƠNG 2 PHƯƠNG PHÁP TRÍCH CHỌN ĐẶC TRƯNG ẢNH Chương 2 sẽ đưa ra một số khái niệm liên quan đến các thuộc tính, kỹ thuật của việc truy vấn theo nội dung ảnh. Qua đó làm tiền đề để nghiên cứu xâu hơn các kỹ thuật trích chọn nội dung ảnh và đối sánh ảnh. 2.1. Trích chọn đặc trưng ảnh dựa trên màu sắc 2.1.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 . Độ đo 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. 12 2.1.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 (noncoherence pixels) 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 hoàn toàn, đâ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. 2.2. Trích chọn đặc trưng ảnh dựa trên kết cấu Kết cấu hay còn gọi là vân (texture), 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í dụ cấu trúc của vân của một số loại lá cây 13 Cấu trúc vân của lá cây 2.2.1. Ma trận đồng hiện (Co-occurence 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. Ví dụ với ảnh f như sau: 1100 
 1 1 0 0  ta có ma trận đồng hiện P(1,0) với 0022 402 P(1,0)=  2 2 0  002 2.2.2. 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. 14 Thuật toán tính ra các đặc trưng vân theo biến đổi Wavelet: • Tính biến đổi Wavelet trên toàn ảnh. • Ứ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 • 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. 2.2.3. Các đặc trưng lọc Gabor Lọc Gabor được sử dụng rộng rãi để trích rút các đặc trưng ảnh, đặc biệt là các đặc trưng kết cấu. Nó tối ưu về mặt cực tiểu hoá sự không chắc chắn chung trong miền không gian và miền tần số, và thường được sử dụng như một hướng và tỷ lệ biên điều hướng và phát hiện đường. Có nhiều cách tiếp cận đã được đề xuất để mô tả các kết cấu của các ảnh dựa trên các lọc Gabor. 2.2.4. Các đặc trưng biến đổi sóng Tương tự với lọc Gabor, biến đổi sóng cung cấp một cách tiếp cận đa độ phân giải đối với phân tích kết cấu và phân lớp. Các biến đổi sóng phân rã một tín hiệu 15 với một họ các hàm cơ sở   thu được thông qua dịch chuyển và sự co giãn của sóng     2 2    Hơn nữa, theo so sánh của các đặc trưng biến đổi sóng khác nhau, chọn riêng lọc sóng không là then chốt cho phân tích kết cấu. 2.3. Trích chọn đặc trưng ảnh dựa trên hình dạng 2.3.1. Trích chọn đặc trưng theo biên 2.3.1.1. Lược đồ hệ số góc 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 . Ảnh minh họa lược đồ hệ số góc 16 Đường biên của ảnh 2.3.1.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ích thước ảnh). Ảnh minh họa vector liên kết hệ số góc 17 Ảnh minh họa sự liên kết giữa các biên cạnh 2.3.2. Trích chọn đặc trưng theo vùng Ảnh gồm tập hợp các vùng hay còn gọi là đoạn. Đây là đặc trưng đặc biệt 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. 2.4. Trích chọn sử dụng điểm nổi bật Phương pháp này dựa trên các điểm nổi bật, là các điểm bất biến với sự thay đổi của ảnh như xoay, co giãn, che lấp một phần… Có 2 phương pháp tiêu biểu nhất là SIFT và SURF 2.4.1. Đặc trưng cục bộ bất biến (SIFT) 18 SIFT là viết tắt của cụm từ Scale-Invariant Invariant Feature Transform là một trong những thuật toán nổi ổi tiếng ti nhất hiện nay dùng để phát hiện và mô tả các đặc trưng ưng của c ảnh số. Thuật toán này được công bố bởii David Lowe vào v năm 1999[19]. Hai hình trên có thể được nhận ra là củ ủa cùng 1 cảnh bởi SIFT Giống như nhiều thuật toán về xử lý ảnh, SIFT là l thuật toán khá phức tạp, phải trải qua nhiều bướ ớc xử lý và sử dụng nhiều kiến thức về toán học. Sau đây ssẽ là các bước chính trong thuật toán: 1. Xây dựng không gian scale 2. Xác đinh vị trí điểm đặc trưng 3. Thêm hướng cho điểm đặc trưng 4. Mô tả điểm đặc trưng