Tài liệu Nghiên cứu kỹ thuật tra cứu cứu ảnh và ứng dụng trong tra cứu cây thuốc

i LỜI CAM ĐOAN Tôi xin cam đoan luận văn với tên đề tài “Nghiên cứu kỹ thuật tra cứu cứu ảnh và ứng dụng trong tra cứu cây thuốc” là kết quả nghiên cứu của bản thân học viên, dựa trên nghiên cứu và thu thập cơ sở dữ liệu thực tiễn dưới sự hướng dẫn khoa học của TS. Nguyễn Văn Tảo. Các số liệu, kết quả nêu trong luận văn là hoàn toàn trung thực, chưa từng được công bố dưới bất cứ hình thức nào. Thái Nguyên, ngày 15 tháng 7 năm 2013 Người cam đoan Nguyễn Thị Bích Hạnh ii LỜI CẢM ƠN Trong suốt thời gian hoàn thành luận văn nghiên cứu, tôi luôn nhận được giúp đỡ tận tình của thầy giáo hướng dẫn và biết bao người thân yêu bên tôi. Nhân dịp này, tôi xin gửi lời cảm ơn và lòng biết ơn sâu sắc nhất tới TS. Nguyễn Văn Tảo về những chỉ dẫn khoa học, những góp ý quý báu và tận tình hướng dẫn tôi trong suốt quá trình thực hiện luận văn tốt nghiệp. Tôi xin chân thành cảm ơn tập thể các Thầy, Cô giáo trong trường Đại học Công nghệ thông tin và Truyền thông đã luôn nhiệt tình quan tâm, giúp đỡ và tạo mọi điều kiện tốt nhất cho tôi trong suốt quá trình học tập tại trường. Xin chân thành cảm ơn tới tập thể các thầy cô và các bạn đồng nghiệp Trung tâm Nghiên cứu và Phát triển Nông Lâm nghiệp miền núi phía Bắc - Trường Đại học Nông Lâm nơi tôi đang công tác; các bạn trường Đại học Y Thái Nguyên đã luôn cổ vũ, động viên và tạo mọi điều kiện thuận lợi để tôi hoàn thành luận văn của mình. Cuối cùng, tôi muốn bày tỏ lòng cảm ơn vô hạn tới bạn bè, tới những người thân yêu luôn bên tôi. Xin bày tỏ lòng cảm ơn sâu sắc tới bố mẹ, chồng, con và những người thân trong gia đình đã là điểm tựa tinh thần lẫn vật chất cho tôi trong những lúc khó khăn, luôn bên cạnh và động viên tôi trong suốt quá trình thực hiện luận văn tốt nghiệp. Xin trân trọng cảm ơn tất cả sự giúp đỡ quý báu đó! Sinh viên Nguyễn Thị Bích Hạnh iii MỤC LỤC LỜI CAM ĐOAN..........................................................................................................i LỜI CẢM ƠN...............................................................................................................ii DANH MỤC CÁC HÌNH...........................................................................................vi DANH MỤC CÁC BẢNG.........................................................................................vii PHẦN MỞ ĐẦU..........................................................................................................1 Chương 1. TỔNG QUAN VỀ TRA CỨU ẢNH DỰA VÀO NỘI DUNG..................3 1.1. Tổng quan về xử lý ảnh....................................................................................3 1.2. Khái quát về tra cứu ảnh.........................................................................................5 1.2.1. Đặc trưng màu .........................................................................................7 1.2.2. Đặc trưng màu vân...................................................................................9 1.2.3. Đặc trưng về hình dạng............................................................................9 1.2.4. Thông tin không gian................................................................................9 1.2.5. Phân đoạn..............................................................................................11 1.3. Các chức năng cơ bản của một hệ thống tra cứu ảnh dựa vào nội dung........12 1.4. Những ứng dụng cơ bản của tra cứu ảnh dựa vào nội dung..........................15 1.5. Một số hệ thống tra cứu ảnh theo nội dung tiêu biểu.....................................16 1.5.1. Hệ thống QBIC.......................................................................................16 1.5.2. Hệ thống Photobook...............................................................................16 1.5.3. Hệ thống VisualSEEK và WebSEEK......................................................16 1.5.4. Hệ thống RetrievalWare.........................................................................17 1.5.5. Hệ thống Imatch.....................................................................................17 1.5.6. Mô tơ tìm kiếm WWW ImageRover.........................................................17 Chương 2. MỘT SỐ KỸ THUẬT TRA CỨU ẢNH DỰA VÀO NỘI DUNG.........18 2.1. Tra cứu ảnh dựa vào màu sắc..........................................................................18 2.1.1. Màu sắc..................................................................................................18 2.1.2. Một số đặc tính đặc biệt về màu sắc.......................................................19 2.1.3. Các không gian màu...............................................................................19 2.1.4. Lượng tử hóa màu và lược đồ màu........................................................24 iv 2.1.5. Đo khoảng cách giữa các lược đồ màu.................................................29 2.2. Tra cứu ảnh dựa vào hình dạng.......................................................................32 2.2.1. Khái niệm về hình dạng..........................................................................32 2.2.2. Đặc điểm hình dạng với việc tìm kiếm ảnh.............................................32 2.2.3. Lược đồ hình dạng..................................................................................34 2.2.4. Biểu diễn hình dạng trên cơ sở vùng và thước đo đồng dạng.................35 2.3. Tra cứu ảnh dựa vào vân..................................................................................39 2.3.1. Vân là gì?...............................................................................................39 2.3.2. Tra cứu ảnh dựa vào vân........................................................................40 2.3.3. Phân hoạch vùng nhị phân cục bộ..........................................................41 2.3.4. Phân đoạn vân........................................................................................41 2.4. Phương pháp tra cứu ảnh sử dụng dấu hiệu nhị phân.....................................41 2.4.1. Giới thiệu................................................................................................41 2.4.2. Kiến trúc hệ thống..................................................................................43 2.4.3. Kỹ thuật tra cứu ảnh theo nội dung dựa vào dấu hiệu nhị phân.............44 2.4.4. Độ đo tương tự.......................................................................................48 Chương 3. XÂY DỰNG CHƯƠNG TRÌNH TRA CỨU ẢNH CÂY THUỐC.........52 3.1. Giới thiệu bài toán tra cứu ảnh cây thuốc .......................................................52 3.2. Phân tích bài toán.............................................................................................53 3.3. Các biểu đồ......................................................................................................57 3.3.1 Biểu đồ Use Case.....................................................................................57 3.3.2. Biểu đồ trình tự và biểu đồ hoạt động....................................................57 3.4. Thiết kế cơ sở dữ liệu.......................................................................................62 3.5. Xây dựng chương trình...................................................................................63 3.5.1. Ngôn ngữ sử dụng...................................................................................63 3.5.2. Giao diện chương trình..........................................................................63 3.6. Thử nghiệm và đánh giá..................................................................................68 PHẦN KẾT LUẬN.....................................................................................................71 TÀI LIỆU THAM KHẢO..........................................................................................72 v DANH MỤC CÁC CHỮ VIẾT TẮT STT Từ Từ viết đầy đủ 1 2 3 4 viết tắt VIR CBIR QBE QBF Visual Information Retrieval Content Based Image Retrieval Query by Example Query by Feature 5 QBIC Query By Image Content 6 7 8 RGB HSV CCV 9 CIE Red Green Blue Hue, Saturation, Value Color Coherence Vectors Commission International d'E 10 11 12 13 14 15 16 CMY CBA VBA GCH LCH GIS CSDL clairage Diễn giải Tra cứu thông tin Tra cứu ảnh dựa vào nội dung Truy vấn bởi ảnh mẫu Truy vấn bởi đặc trưng Truy vấn ảnh dựa vào nội dung Đỏ, Xanh lục, Xanh lơ Màu, độ bão hòa màu, độ sáng Véc tơ gắn kết màu Ủy ban quốc tế về màu sắc Cyan-Magenta-Yellow Lục lam, đỏ tươi, vàng Constant Bin Allocation Variable Bin Allocation Global Color Histogram Local Color Histogram Geographic Information System Cơ sở dữ liệu Phân bổ bin liên tục Phân bổ biến bin Lược đồ màu toàn cục Lược đồ màu cục bộ Hệ thống thông tin địa lý DANH MỤC CÁC HÌNH Hình 1.1: Các bước cơ bản trong một hệ thống xử lý ảnh.........................................3 Hình 1.2: Kiến trúc hệ thống tra cứu ảnh dựa vào nội dung......................................13 Hình 2.1: Mô tả không gian màu RGB......................................................................20 Hình 2.2: Mô tả không gian màu HSV......................................................................21 Hình 2.3: Lược đồ màu HIS cải tiến..........................................................................28 vi Hình 2.4: Khoảng cách dạng Minkowski...................................................................29 Hình 2.5: Khoảng cách dạng toàn phương.................................................................30 Hình 2.6: Hình dạng sau khi đã chồng lưới...............................................................35 Hình 2.7: Hình dạng trên hình 2.6 sau khi đã được chuẩn hóa.................................37 Hình 2.8: Đo hai hình dạng trên cơ sở chỉ mục.........................................................37 Hình 2.9: Một số loại vân tiêu biểu...........................................................................40 Hình 2.10: Kiến trúc của kỹ thuật tra cứu ảnh sử dụng dấu hiệu nhị phân...............43 Hình 2.11: Mẫu thiết lập hình ảnh..............................................................................45 Hình 3.1: Kiến trúc tổng quát của hệ thống tra cứu ảnh............................................54 Hình 3.2: Mô hình chi tiết của hệ thống tra cứu ảnh.................................................55 Hình 3.3: Tiền xử lý ảnh dữ liệu.................................................................................57 Hình 3.4: Biểu đồ Use Case.......................................................................................57 Hình 3.5: Biểu đồ trình tự của tác nhân tra cứu.........................................................58 Hình 3.6: Biểu đồ cộng tác của tác nhân tra cứu.......................................................58 Hình 3.7: Biểu đồ hoạt động của tác nhân tra cứu ảnh..............................................59 Hình 3.8: Biểu đồ trình tự của tác nhân quản lý CSDL ảnh......................................60 Hình 3.9: Biểu đồ cộng tác của tác nhân quản lý CSDL ảnh....................................60 Hình 3.10: Biểu đồ hoạt động của chức năng quản lý cơ sở dữ liệu ảnh..................61 Hình 3.11: Màn hình khởi tạo của chương trình........................................................63 Hình 3.12: Màn hình chọn cơ sở dữ liệu ảnh.............................................................64 Hình 3.13: Màn hình chọn ảnh cần truy vấn 1...........................................................65 Hình 3.14: Màn hình kết quả đối với ảnh truy vấn 1.................................................65 Hình 3.15: Danh sách ảnh hiển thị thông tin được sắp xếp với ảnh truy vấn 1........66 Hình 3.16: Màn hình chọn ảnh truy vấn 2.................................................................67 Hình 3.17: Màn hình kết quả đối với ảnh truy vấn 2.................................................67 Hình 3.18: Danh sách ảnh hiển thị thông tin được sắp xếp với ảnh truy vấn 2........68 DANH MỤC CÁC BẢNG Bảng 2.1: Dấu hiệu nhị phân của hình 2.9 sử dụng CBA..........................................46 Bảng 2.2: Dấu hiệu nhị phân của hình 2.9 sử dụng VBA..........................................47 vii Bảng 2.3: Chuỗi dấu hiệu nhị phân minh họa sự giống và khác nhau của ảnh.........47 Bảng 3.1: Bảng cơ sở dữ liệu ảnh..............................................................................62 Bảng 3.2: Bảng cơ sở dữ liệu nhị phân......................................................................62 Bảng 3.3: Bảng kết quả thực hiện truy vấn 1.............................................................62 Bảng 3.4: Bảng kết quả thực hiện truy vấn 2.............................................................70 1 PHẦN MỞ ĐẦU Ngày nay cùng với sự phát triển của các ngành khoa học khác, ngành công nghệ thông tin cũng có những bước phát triển nhanh chóng, ngày càng có nhiều ứng dụng vào thực tiễn cuộc sống và đem lại hiệu quả cao. Việc quản lý thông tin rất cần tới các công cụ để thu thập, phân loại tổ chức ở các dạng dữ liệu khác nhau một cách hiệu quả. Trong khi các hệ thống quản lý thông tin dựa vào văn bản đã rất thành công nhưng chúng vẫn không đáp ứng được việc quản lý, khai thác và xử lý dữ liệu với khối lượng khổng lồ như hiện nay. Ảnh số ngày càng thu hút được sự quan tâm của nhiều người, một phần là do các thiết bị thu nhận ảnh số ngày càng phổ biến và có giá cả phù hợp, cho phép nhiều người có thể sở hữu và sử dụng. Tra cứu và quản trị cơ sở dữ liệu ảnh thu hút sự quan tâm của nhiều nhà nghiên cứu từ những năm 1970. Với sự tăng nhanh về tốc độ máy tính và giảm chi phí bộ nhớ, các cơ sở dữ liệu ảnh chứa hàng nghìn thậm chí hàng triệu ảnh được sử dụng trong nhiều lĩnh vực ứng dụng khác nhau như y học, ảnh vệ tinh, các cơ sở dữ liệu ảnh sinh học và các cơ sở dữ liệu ảnh phong cảnh... Các ứng dụng này đòi hỏi độ chính xác tra cứu cao. Khi có nhu cầu tra cứu một vài bức ảnh nào đó trong một cơ sở dữ liệu có hàng trăm ngàn ảnh, điều này khó có thể thực hiện được khi ta tra cứu bằng tay theo cách thông thường, nghĩa là xem từng tấm ảnh một cho đến khi thấy ảnh có nội dung cần tìm. Với sự tăng nhanh về số lượng ảnh, cách tiếp cận tra cứu ảnh dựa vào chú thích ảnh thủ công trở nên không khả thi về cả thời gian và chi phí. Do đó, khi số lượng ảnh được lưu trữ trở nên rất lớn thì vấn đề đặt ra là phải có những phương pháp tổ chức cơ sở dữ liệu ảnh tốt cùng với những kỹ thuật tra cứu, tra cứu ảnh hiệu quả, có độ chính xác cao và có hiệu năng tốt mới đáp ứng được nhu cầu ngày càng cao của con người. Việc xây dựng các hệ thống tra cứu ảnh là rất cần thiết. Trong thực tế, bài toán tra cứu ảnh số có rất nhiều ứng dụng quan trọng. Ví dụ trong lĩnh vực ngân hàng việc so sánh chữ ký của khách hàng với mẫu chữ ký đã được lưu trữ sẵn có thể thực hiện rất nhanh và chính xác nếu có được một phần 2 mềm so sánh mẫu chữ ký tốt. Các ứng dụng phức tạp hơn như so sánh mẫu vân tay, tra cứu ảnh tội phạm v.v... là những bài toán tra cứu ảnh được áp dụng trong ngành khoa học hình sự. Vì vậy, việc xây dựng các hệ thống tra cứu và xếp hạng ảnh là rất cần thiết và thực tế đã có nhiều công cụ tra cứu ảnh thương mại xuất hiện. Các công cụ tra cứu ảnh thường dựa vào hai đặc trưng chính là văn bản đi kèm ảnh hoặc nội dung ảnh. Tra cứu ảnh theo nội dung đã nhận được nhiều sự quan tâm của các nhà khoa học do nhu cầu tìm kiếm các cơ sở dữ liệu có cỡ lớn tăng nhanh. Cây thuốc (cây dược liệu) có một vai trò quan trọng đối với đời sống của mỗi con người, đặc biệt trong chăm sóc sức khỏe. Ngày nay, cây dược liệu đã được con người khai thác, khám phá, phát hiện và nhận dạng trên cơ sở công dụng của chúng đối với đời sống chúng ta, đặc biệt là cây dược liệu đem lại giá trị kinh tế cao. Tuy nhiên hiện nay, nguồn cây dược liệu bị khai thác bừa bãi ngày càng nhiều, điều này dẫn đến cạn kiệt dần nguồn tài nguyên dược liệu. Trên thế giới, việc nghiên cứu, phát hiện, khai thác và quản lý cây dược liệu đã nhận được sự quan tâm nghiên cứu của nhiều nhà quản lý, nhà khoa học và nhà y dược. Họ không chỉ thu thập, khai thác, quản lý mà còn xây dựng các cơ chế ứng dụng tiến bộ khoa học và công nghệ vào nhận dạng, quản lý và bảo vệ cũng như bảo tồn cây dược liệu một cách hiệu quả. Ở Việt Nam việc quản lý và khai thác cây dược liệu vẫn chỉ mang tính chất tự phát nên cần có sự quản lý và khai thác đồng bộ trên cơ sở phát hiện, nhận dạng và bảo tồn các loài cây dược liệu quý là một việc làm cấp thiết. Xuất phát từ thực tế nêu trên, luận văn được lựa chọn là: “Nghiên cứu kỹ thuật tra cứu ảnh và ứng dụng trong tra cứu cây thuốc” . Bố cục luận văn gồm 3 phần: Phần mở đầu, phần kết luận và 3 chương nội dung. Chương 1: Tổng quan về tra cứu ảnh dựa vào nội dung. Chương 2: Một số kỹ thuật tra cứu ảnh dựa vào nội dung. Chương 3: Xây dựng chương trình tra cứu ảnh cây thuốc. 3 Chương 1 TỔNG QUAN VỀ TRA CỨU ẢNH DỰA VÀO NỘI DUNG 1.1. Tổng quan về xử lý ảnh Xử lý ảnh là một lĩnh vực mang tính khoa học và công nghệ. Nó là một ngành khoa học mới mẻ so với các ngành khoa học khác nhưng tốc độ phát triển của nó rất nhanh, kích thích các trung tâm nghiên cứu ứng dụng, đặc biệt là máy tính chuyên dụng cho nó. Quá trình xử lý ảnh được xem như là quá trình thao tác ảnh đầu vào nhằm cho ra kết quả mong muốn. Kết quả đầu ra của một quá trình xử lý ảnh có thể là một ảnh “tốt hơn” hoặc một kết luận. Ảnh có thể xem là tập hợp các điểm ảnh và mỗi điểm ảnh được xem như là đặc trưng cường độ sáng hay một dấu hiệu nào đó tại một vị trí nào đó của đối tượng trong không gian và nó có thể xem như một hàm n biến P(c1, c2,..., cn). Do đó, ảnh trong xử lý ảnh có thể xem như ảnh n chiều [1], [2]. Sơ đồ tổng quát của một hệ thống xử lý ảnh: Thu nhận ảnh (Scanner, Camera,Sensor) Tiền xử lý Trích chọn đặc điểm Hệ quyết định Đối sánh rút ra kết luận Hậu xử lý Lưu trữ Hình 1.1: Các bước cơ bản trong một hệ thống xử lý ảnh  Phần thu nhận ảnh Các thiết bị thu nhận ảnh bao gồm camera, scanner các thiết bị thu nhận này có thể cho ảnh đen trắng. Các thiết bị thu nhận ảnh có 2 loại chính ứng với 2 4 loại ảnh thông dụng Raster, Vector. Các thiết bị thu nhận ảnh thông thường Raster là camera, các thiết bị thu nhận ảnh thông thường Vector là sensor hoặc bàn số hoá Digitalizer hoặc được chuyển đổi từ ảnh Raster. Trước đây ảnh thu được qua camera là ảnh tương tự nhưng gần đây với sự phát triển của công nghệ, ảnh màu hay ảnh đen trắng lấy được từ camera sau đó được chuyển trực tiếp thành ảnh số tạo thuận lợi cho xử lý tiếp theo. Mặt khác ảnh có thể thu được từ vệ tinh hoặc máy quét ảnh.  Tiền xử lý Sau bộ thu nhận ảnh có thể bị nhiễu hoặc có độ tương phản thấp nên cần đưa vào bộ tiền xử lý để nâng cao chất lượng. Chức năng của bộ tiền xử lý là lọc nhiễu, nâng cao độ tương phản,…  Trích chọn đặc điểm Các đặc điểm của đối tượng được trích chọn tuỳ theo mục đích nhận dạng trong quá trình xử lý ảnh. Có thể nêu ra một số đặc điểm của ảnh sau đây:  Đặc điểm không gian: Phân bố mức xám, phân bố xác suất, biên độ, điểm uốn v.v..  Đặc điểm biến đổi: Các đặc điểm loại này được trích chọn bằng việc thực hiện lọc vùng (zonal filtering). Các bộ vùng được gọi là “mặt nạ đặc điểm” (feature mask) thường là các khe hẹp với hình dạng khác nhau (chữ nhật, tam giác, cung tròn v.v..)  Đặc điểm biên và đường biên: Đặc trưng cho đường biên của đối tượng và do vậy rất hữu ích trong việc trích trọn các thuộc tính bất biến được dùng khi nhận dạng đối tượng. Các đặc điểm này có thể được trích chọn nhờ toán tử gradient, toán tử la bàn, toán tử Laplace, toán tử “chéo không” (zero crossing) v.v..  Biểu diễn ảnh Ảnh trên máy tính là kết quả thu nhận theo các phương pháp số hoá được 5 nhúng trong các thiết bị kỹ thuật khác nhau. Quá trình lưu trữ ảnh nhằm 2 mục đích là: Tiết kiệm bộ nhớ và giảm thời gian xử lý. Việc lưu trữ thông tin trong bộ nhớ có ảnh hưởng rất lớn đến việc hiển thị, in ấn và xử lý ảnh được xem như là 1 tập hợp các điểm với cùng kích thước nếu sử dụng càng nhiều điểm ảnh thì bức ảnh càng đẹp, càng mịn và càng thể hiện rõ hơn chi tiết của ảnh người ta gọi đặc điểm này là độ phân giải.  Nhận dạng và giải thích ảnh Nhận dạng ảnh là quá trình xác định ảnh. Quá trình được thực hiện nhờ so sánh với mẫu chuẩn đã được học hoặc lưu từ trước. Giải thích là phán đoán theo ý nghĩa trên cơ sở nhận dạng. Ví dụ một loạt chữ số và nét gạch ngang trên bì thư có thể phán đoán là mã điện thoại. Theo lý thuyết về nhận dạng, các mô hình toán học về ảnh được phân loại theo hai loại nhận dạng ảnh cơ bản: Nhận dạng theo tham số và nhận dạng theo cấu trúc. Một số đối tượng nhận dạng ảnh khá phổ biến hiện nay là nhận dạng kí tự (chữ in, chữ viết tay, chữ kí điện tử), nhận dạng vân tay, nhận dạng mã vạch, nhận dạng mặt người [1]. 1.2. Khái quát về tra cứu ảnh Tra cứu ảnh là một quá trình tra cứu trong một cơ sở dữ liệu ảnh những ảnh thỏa mãn một yêu cầu nào đó. Ví dụ người sử dụng có thể tra cứu tất cả các ảnh chủ đề về “Cây thuốc thảo dược” trong một cơ sở dữ liệu ảnh hoặc một người sử dụng khác lại muốn phân loại cơ sở ảnh của mình thành các bộ sưu tập có chủ đề khác nhau. Một ví dụ khác là một người muốn tìm tất cả các ảnh tương tự với một bức ảnh mẫu nào đó trong một cơ sở dữ liệu ảnh. Theo Wikipedia: Hệ thống tra cứu ảnh là một hệ thống máy tính sử dụng để duyệt, tra cứu và tra cứu ảnh từ một cơ sở dữ liệu ảnh số lớn. Trước năm 1990, người ta thường sử dụng phương pháp tra cứu ảnh theo văn bản (Text Based Image Retrieval). Theo cách này người ta sẽ gán cho mỗi bức ảnh 6 một lời chú thích phù hợp với nội dung hoặc một đặc điểm nào đó của ảnh, sau đó việc tra cứu ảnh được thực hiện dựa trên những lời chú thích này. Phương pháp này khá đơn giản. Phương pháp tra cứu ảnh như trên còn được gọi là tra cứu ảnh theo từ khóa. Tuy nhiên, việc tra cứu chỉ dựa vào văn bản đi kèm còn có nhiều nhập nhằng giữa nội dung hiển thị ảnh và nội dung văn bản đi kèm ảnh trong quá trình tra cứu. Ví dụ, với truy vấn “Apple”, máy tra cứu khó phân biệt được người dùng muốn tìm hình ảnh quả táo hay logo của hãng Apple. Bên cạnh đó phương pháp tra cứu ảnh dựa theo văn bản không thể áp dụng để tra cứu các cơ sở dữ liệu ảnh có số lượng ảnh lớn và kết quả tra cứu thì mang tính chủ quan và 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à phương pháp “Tra cứu ảnh dựa theo nội dung” (Content Based Images Retrieval CBIR) [16]. Phương pháp tra cứu ảnh theo nội dung ra đời đã khắc phục được những nhược điểm của phương pháp từ khóa. CBIR là một lĩnh vực khoa học được phát triển dựa trên cơ sở lý thuyết và ứng dụng của xử lý ảnh. Hệ thống cho phép người dùng tra cứu các ảnh tương tự trong một cơ sở dữ liệu hình ảnh. CBIR được thực hiện thông qua việc tính độ tương tự giữa hai bức ảnh được biểu diễn bởi một trong số các đặc trưng mức thấp của ảnh như: Màu sắc, hình dạng, kết cấu… Kết quả đưa ra là tập các bức ảnh tương tự với ảnh truy vấn được sắp xếp theo thứ tự giảm dần độ tương tự. Cụm từ CBIR được T.Kato đưa ra vào năm 1992 trong quá trình thu thập ảnh một cách tự động từ cơ sở dữ liệu dựa trên biểu diễn màu sắc và hình dạng của ảnh. Có hai cách tiếp cận chung đối với các giải pháp cho vấn đề tra cứu thông tin dựa trên dạng thông tin trực quan đó là các phương pháp dựa trên đặc trưng và các phương pháp dựa trên văn bản mô tả ảnh. 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 7 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. 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, hình dạng và kết cấu và được đánh chỉ số dựa trên các 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. Trong luận văn này, em sẽ tập trung vào đặc trưng cụ thể là đặc trưng màu và vector đặc trưng ứng dụng tra cứu ảnh dựa vào nội dung. Một số đặc trưng đã được sử dụng để biểu diễn các ảnh trong các hệ thống CBIR. 1.2.1. Đặc trưng màu Đặc trưng được sử dụng phổ biến nhất là màu. Màu sắc là vấn đề cần tập trung giải quyết nhiều nhất, vì một ảnh màu thì thông tin quan trọng nhất trong ảnh chính là màu sắc. Hơn nữa thông tin về màu sắc là thông tin người dùng quan tâm 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. Lược đồ màu toàn cục (GCH) là cách sử dụng đặc trưng màu đơn giản và hiệu quả. GCH là một véc tơ n chiều (h 1, h2, ...hn), ở đây mỗi thành phần hj biểu diễn phần trăm các pixel có màu j trong ảnh. GCH là bất biến đối với quay và tỉ lệ và tính toán rất đơn giản. Tuy nhiên, GCH có nhược điểm cơ bản là quá tổng quát. Nói cách khác, GCH chỉ đem vào bản miêu tả phân bố các màu mà bỏ qua quan hệ giữa các bin màu [14], [15]. 8 Để tránh một số vấn đề gặp phải đối với GCH, lược đồ màu cục bộ (LCH) đã được đề xuất. Một ảnh được chia thành các khối ảnh có cỡ như nhau và độ tương tự giữa hai ảnh được dựa trên các khoảng cách lược đồ giữa các khối tương ứng. Phương pháp này không có khả năng xử lý đối với các biến đổi hình học như quay và dịch chuyển, bị một số vấn đề về đan chéo và biến đổi với vị trí không gian. Một số giải pháp đã được đề xuất để làm cho cách tiếp cận dựa vào lưới bất biến đối với quay và dịch chuyển nhưng các giải pháp này tốn nhiều thời gian. Natsev và cộng sự thực hiện tra cứu ảnh dựa vào nội dung dựa trên thuộc tính bố cục màu. Mỗi ảnh được chia thành một số ảnh con bằng việc dịch chuyển các cửa sổ có cỡ khác nhau và với mỗi ảnh con, một dấu hiệu bố cục màu được trích rút. Độ tương tự giữa các ảnh được tính toán bằng việc so sánh các dấu hiệu của các ảnh con này. Ưu điểm của hệ thống này là có thể giảm các nhạy cảm với tỉ lệ và trượt, nhược điểm là độ phức tạp tính toán tăng và hệ thống không xem xét đến đặc trưng hình. Smith và Chang đã đề xuất các tập màu. Phương pháp xấp xỉ lược đồ màu để tăng tốc quá trình tra cứu trong trường hợp cơ sở dữ liệu ảnh rất lớn. Tập màu được chọn từ không gian màu được lượng hoá và từ các đặc trưng được biểu diễn như một xâu bít, một cây nhị phân được sử dụng để tăng tốc quá trình tra cứu. Một cách tiếp cận dựa vào màu khác được đề xuất trong, ở đây một ảnh được biểu diễn với sự trợ giúp của ba mô men màu trung bình, phương sai và độ lệch. Kỹ thuật có ưu điểm là tính toán đơn giản và chi phí không gian thấp. Độ tương tự giữa hai ảnh được tính như là tổng trọng số của các sai khác giữa các mô men trong ảnh truy vấn và các mô men của tất cả các ảnh trong cơ sở dữ liệu. Thậm chí thông qua các mô men màu có thể ngăn chặn các ảnh hưởng của lượng hoá (không giống như lược đồ màu). Cách tiếp cận thiếu thông tin không gian. Pass và cộng sự đã đề xuất một phương pháp mới sử dụng véc tơ gắn kết màu (CCV). Họ đã đề xuất một cách tiếp cận dựa vào lược đồ màu kết hợp với thông tin không gian. Ảnh được làm mờ để loại đi các khác biệt nhỏ giữa các pixel và sau đó không gian màu được lượng hoá thành n màu. Các pixel trong phạm vi một bin màu 9 được phân lớp hoặc là gắn kết hoặc là không gắn kết phụ thuộc vào chúng có thuộc vào vùng pixel tương đối lớn hay không. 1.2.2. Đặc trưng màu vân Có những lớp ảnh mà màu sắc không thể giải quyết được, đòi hỏi phải sử dụng đặc trưng vân, ví dụ như những ảnh liên quan đến cấu trúc của điểm ảnh như: cỏ, mây, đá, sợi. Vân sẽ giải quyết tốt cho việc tìm kiếm đối với lớp ảnh này. 1.2.3. Đặc trưng về hình dạng Đối với những lớp ảnh cần tìm mà liên quan đến hình dạng của đối tượng thì đặc trưng vân và màu không thể giải quyết được. Tìm kiếm theo hình dáng thật sự là một cái đích của hệ thống tìm kiếm dựa vào nội dung muốn đạt tới. Các đặc trưng hình dạng của các đối tượng hoặc các vùng đã được sử dụng trong nhiều hệ thống tra cứu ảnh dựa vào nội dung. So với các đặc trưng màu và vân, các đặc trưng hình dạng thường được mô tả sau khi các ảnh được phân đoạn thành các vùng hoặc các đối tượng. Do phân đoạn ảnh mạnh và chính xác là khó đạt được, sử dụng các đặc trưng hình dạng cho tra cứu ảnh bị giới hạn đối với các ứng dụng chuyên biệt, ở đó các đối tượng hoặc các vùng đã sẵn có. 1.2.4. Thông tin không gian Các vùng hoặc đối tượng với các đặc tính màu và kết cấu tương tự có thể được phân biệt dễ dàng bằng việc tận dụng các ràng buộc không gian. Thí dụ, các vùng bầu trời màu xanh và biển xanh có thể có các lược đồ màu tương tự, nhưng các vị trí không gian của chúng trong các ảnh là khác nhau. Do đó, vị trí không gian của các vùng (hoặc các đối tượng) hoặc quan hệ không gian giữa nhiều vùng (hoặc đối tượng) trong một ảnh thì rất hữu ích cho tìm kiếm các ảnh. Thu thông tin không gian của các đối tượng trong một ảnh là một quá trình quan trọng đối với các hệ thống GIS. Quá trình này bao gồm việc biểu diễn vị trí không gian tuyệt đối và cũng bao gồm vị trí không gian tương đối của các đối tượng. Các thao tác như giao và chồng được sử dụng. Bố cục màu kết hợp thông tin không 10 gian với thông tin màu xuất hiện trong ảnh và tạo ra một đặc trưng rất quan trọng trong quá trình tra cứu, gọi là đặc trưng màu – không gian. Biểu diễn quan hệ không gian được sử dụng rộng rãi nhất là các xâu 2D được đề xuất bởi Chang và cộng sự. Nó được xây dựng bởi việc chiếu các ảnh dọc theo các hướng x và y. Hai tập ký hiệu V và A được định nghĩa trên hình chiếu. Mỗi ký hiệu trong V biểu diễn một đối tượng trong ảnh. Mỗi ký hiệu A biểu diễn một loại quan hệ không gian giữa các đối tượng. Do sự biến đổi của nó, xâu 2DG cắt tất cả các đối tượng dọc theo hình hộp tối thiểu của nó và mở rộng các quan hệ không gian thành lập hai toán tử không gian. Một tập định nghĩa các quan hệ không gian cục bộ. Tập còn lại định nghĩa quan hệ không gian toàn cục, chỉ ra rằng hình chiếu của hai đối tượng là tách rời, nối tiếp hoặc định vị tại cùng vị trí. Thêm nữa, xâu 2DC được đề xuất để cực tiểu hóa số các đối tượng cắt. Xâu 2D-B biểu diễn một đối tượng bằng hai ký hiệu, vị trí cho bắt đầu và kết thúc đường bao của đối tượng. Tất cả các phương pháp này có thể hỗ trợ ba loại truy vấn. Loại truy vấn 0 tìm tất cả ảnh chứa đối tượng O 1, O2, ...,On. Loại 1 tìm tất cả các ảnh chứa các đối tượng có quan hệ nào đó giữa chúng nhưng khoảng cách giữa chúng là không đáng kể. Loại 2 tìm tất cả các ảnh có quan hệ khoảng cách nào đó với mỗi ảnh khác. Thêm với xâu 2D, cây tứ phân không gian, và ảnh ký hiệu cũng được sử dụng cho biểu diễn thông tin không gian. Tuy nhiên, tìm kiếm các ảnh dựa trên các quan hệ không gian của các vùng còn lại là một vấn đề nghiên cứu khó trong tra cứu ảnh dựa vào nội dung, do phân đoạn tin cậy của các đối tượng hoặc các vùng thường là không khả thi ngoại trừ các ứng dụng rất giới hạn. Mặc dù một số hệ thống chia các ảnh thành các khối đều, chỉ thu được sự thành công khiêm tốn với các lược đồ chia không gian như thế do hầu hết các ảnh tự nhiên không thể ép thành các khối con đều về không gian. Để giải quyết vấn đề này, một phương pháp dựa vào biến đổi radon, tận dụng phân bố không gian của các đặc trưng trực quan không cần phân đoạn phức tạp. 1.2.5. Phân đoạn 11 Phân đoạn là quá trình phân ảnh ra thành các vùng mà về lý tưởng nó sẽ tương ứng với các đối tượng xuất hiện trong ảnh. Đây là bước rất quan trọng đối với tra cứu ảnh. Cả đặc trưng hình và đặc trưng bố cục phụ thuộc vào phân đoạn tốt. Trong phần này chúng tôi sẽ mô tả một số kỹ thuật phân đoạn đã có được sử dụng trong cả thị giác máy và tra cứu ảnh. Trong, Lybanon và các cộng sự đã nghiên cứu một cách tiếp cận phép toán hình thái học (mở và đóng) trong phân đoạn ảnh. Họ đã kiểm tra cách tiếp cận của họ với các loại ảnh khác nhau, gồm các ảnh thiên văn và các ảnh hồng ngoại. Trong khi cách tiếp cận này là hiệu quả trong xử lý các loại ảnh khoa học ở trên, hiệu năng của nó cần được tiếp tục đánh giá cho các ảnh tự nhiên phức tạp hơn. Li và cộng sự đã đề xuất một cách tiếp cận phân đoạn dựa vào entropy mờ. Cách tiếp cận này dựa trên thực tế rằng entropy cực đại địa phương tương ứng với sự không rõ ràng giữa các vùng khác nhau trong ảnh. Cách tiếp cận này rất hiệu quả cho các ảnh có lược đồ không có các đỉnh và các rãnh rõ ràng. Các kỹ thuật phân đoạn khác dựa trên phép đo đạc tam giác Delaunay (Delaunay triangulation), fractals, và luồng biên (edge flow). Tất cả các thuật toán được đề cập ở trên là tự động. Một ưu điểm chính của các thuật toán phân đoạn loại này là nó trích rút các đường bao từ một số lượng lớn các ảnh mà không chiếm thời gian và nỗ lực của con người. Tuy nhiên, trong một lĩnh vực tự nhiên, với các ảnh không có điều kiện tiên quyết, phân đoạn tự động không luôn luôn tin cậy. Một thuật toán có thể phân đoạn trong trường hợp này chỉ là các vùng, mà không là các đối tượng. Để thu được các đối tượng mức cao, nó cần có sự trợ giúp của con người. Samadani và Han đã đề xuất một cách tiếp cận trích rút đường bao được trợ giúp bởi máy tính, nó kết hợp các đầu vào thủ công từ người sử dụng với các biên ảnh được sinh ra bởi máy tính. Trong khi đó, Daneel và cộng sự đã phát triển một phương pháp cải tiến của các chu tuyến thiết thực. Dựa trên đầu vào của người sử dụng, đầu tiên thuật toán sử dụng một thủ tục tham lam để cung cấp sự hội tụ ban đầu nhanh. 12 Thứ hai, nét ngoài được lọc bằng việc sử dụng quy hoạch động. Rui và cộng sự đã đề xuất một thuật toán dựa vào phân cụm và nhóm trong không gian - màu - kết cấu. Người sử dụng định nghĩa đối tượng quan tâm là ở đâu, và thuật toán nhóm các vùng thành các đối tượng có ý nghĩa. 1.3. Các chức năng cơ bản của một hệ thống tra cứu ảnh dựa vào nội dung 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 (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 [4], [14], [16]. 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:  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ược 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. 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.  Đị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. 13  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 hoặc các ảnh được tra cứu. Hình 1.2: Kiến trúc hệ thống tra cứu ảnh dựa vào nội dung Chúng ta nhận thấy rằng trên một mặt của một hệ thống tra cứu ảnh dựa vào nội dung, có các nguồn thông tin trực quan ở các khuôn dạng khác nhau và trên mặt kia có các truy vấn người sử dụng. Hai mặt này được liên kết thông qua một chuỗi các tác vụ như được minh họa trong Hình 1.2. Hai tác vụ phân tích truy vấn người sử dụng và đánh chỉ số nhiều chiều được tóm lược ở đây trong khi hai tác vụ quan trọng nhất: “Phân tích các nội dung của thông tin nguồn” (trích rút đặc trưng) và “Định nghĩa một chiến lược để đối 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ữ” (các độ đo tương tự). CHƯƠNG 1. Truy vấn người sử dụng 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ừ người sử dụng để trích rút các kết quả có ý nghĩa.