Luận văn Nghiên cứu phương pháp kết hợp các đặc trưng màu sắc hình dạng và vị trí để truy vấn ảnh

Chương 1: TỔNG QUAN VỀ TRUY VẤN ẢNH VÀ CÁC HƯỚNG TIẾP CẬN 1.1. Giới thiệu chung Xử lý ảnh là một lĩnh vực nghiên cứu rất sâu rộng và đang phát triển không ngừng. Bởi tính trực quan sinh động cũng như khả năng áp dụng vào thực tế lớn, hiện xử lý ảnh đang rất hấp dẫn sự quan tâm của nhiều nhà nghiên cứu. Trong xử lý ảnh, truy vấn ảnh có thể nói là lĩnh vực đòi hỏi sự nghiên cứu tổng hợp: nghiên cứu xử lý ảnh để rút trích các đặc trưng, áp dụng các tính toán toán học cao cấp để xác định mức độ tương đồng giữa hai ảnh và sự tổ chức sắp xếp chỉ mục cho cơ sở dữ liệu ảnh. Chính vì thế truy vấn ảnh là lĩnh vực nghiên cứu đem lại nhiều thú vị. Hơn nữa, cùng với sự phát triển của phần mềm và phần cứng, khối lượng ảnh phát triển không ngừng và ngày càng lớn. Một số lượng lớn các ảnh đang được sử dụng ở trong thư viện ảnh số (on digital libraries) và trên web. Vì vậy nhu cầu tìm kiếm ảnh là một nhu cầu tất yếu. Hiện tại, truy vấn ảnh ứng dụng trong khá nhiều lĩnh vực như: quản lý nhãn hiệu logo, truy tìm tội phạm, ứng dụng trong y khoa, quân sự … Bài toán tìm kiếm ảnh trong Cơ Sở Dữ Liệu (CSDL) ảnh được đưa ra từ cuối năm 1970 và có nhiều cách giải quyết khác nhau. Cho đến ngày nay đã có rất nhiều hệ thống truy vấn ảnh (cả thương mại lẫn thực nghiệm) đã và đang được phát triển. Có hai dạng CSDL ảnh là: CSDL ảnh tĩnh và CSDL ảnh động (ảnh video…). Trong nghiên cứu này chỉ xin xem xét đến phạm vi ảnh tĩnh. Mục tiêu của hệ thống truy vấn ảnh là tìm ra ảnh đúng với nhu cầu của người dùng: 5 Các hệ thống truy vấn ảnh hiện nay rất đa dạng nhưng nhìn chung thì chúng được phân biệt bởi: các đặc trưng (Image Features) mà hệ thống rút trích từ ảnh để làm cơ sở truy vấn và phương pháp phân đoạn ảnh được sử dụng trong hệ thống truy vấn, cách thức tổ chức chỉ mục cho CSDL ảnh (Image Indexing), độ đo sự tương đồng giữa hai ảnh (Similarity Measure). Độ đo sự tương đồng phải là một hàm số HxH->R+ thỏa các tính chất sau với mọi ảnh I, J, K: Tính tự tương đồng (self similarity): d(I, I) = d(J, J) Tính đối xứng (synmetry): d(I, J) = d(J, I) Tính bắc cầu (triangular inequality): d(I, K) + d(K, J) >= d(I, J) Tính tối tiểu (minimality): d(I, J) >= d(I, I) (theo tài liệu tham khảo [16]) Các hệ thống truy vấn ảnh thường tuân theo một trong các mô hình sau: 6 CSDL ảnh Ảnh truy vấn Yêu cầu truy vấn Rút trích đặc trưng và độ đo sự tương đồng Xuất ra Tập ảnh kết quả Mô hình rút trích đặc trưng real time Mô hình này đơn giản, dễ cài đặt nhưng đưa vào ứng dụng thực tế sẽ chậm vì nhược điểm: khi có một yêu cầu truy vấn ảnh hệ thống không những phải rút trích các đặt trưng của ảnh truy vấn mà còn phải rút trích các đặc trưng của ảnh trong tập ảnh của CSDL ảnh, sau đó tính toán mức độ tương đồng giữa chúng. Mô hình này thích hợp để cài đặt thử nghiệm và ghi nhận kết quả trong quá trình thực nghiệm để lựa chọn các đặc trưng cần rút trích cũng như độ đo tương đồng hiệu quả nhất. 7 Mô hình tách riêng cơ sở dữ liệu đặc trưng Trích chọn đặc trưng CSDL Ảnh truy vấn Đặc trưng của ảnh truy vấn Các đặc trưng Tính độ đo sự tương đồng Xuất ra Trích đặc trưng CSDL Ảnh Tập ảnh kết quả Mô hình này xây dựng nên CSDL các đặc trưng tương ứng với CSDL ảnh nên khi phát sinh một yêu cầu truy vấn, hệ thống chỉ rút trích các đặc trưng của ảnh truy vấn và so sánh với các đặc trưng trong CSDL đặc trưng nên khả năng thực thi nhanh hơn nhưng có sự phức tạp hơn trong cài đặt so với mô hình trên. Mô hình này thích hợp để xây dựng ứng dụng sau khi đã thử nghiệm và lựa chọn độ đo sự tương đồng Similary Measure tối ưu và các đặc trưng cần thiết phải rút trích và lưu giữ thì sẽ có kết quả tốt nhất cho bài toán cần giải quyết. Mô hình này cần một cơ chế để đảm bảo giữa CSDL các đặc trưng và CSDL ảnh phải khớp sau một thời gian sử dụng, tránh trường hợp người dùng vô tình hay cố ý thay đổi CSDL đặc trưng không còn tương ứng với CSDL ảnh. Tóm lại, để xây dựng hệ thống truy vấn ảnh, cần giải quyết 3 vấn đề chính sau: 1. Rút trích các đặc trưng trên ảnh (Feature Exaction) 2. Xác định độ đo sự tương đồng giữa hai ảnh (Similarity Measure) 3. 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: 8 CSDL Ảnh 1.2. Các phương pháp truy vấn ảnh chính 1.2.1 Truy vấn theo lời chú thích (annotation, key words) Các từ khóa hay các lời chú thích được đưa vào để mô tả thông tin trong ảnh và các từ khóa hay lời chú thích cũng được dùng làm chỉ mục. Việc truy vấn ảnh đơn giản chỉ là sự so khớp các từ khóa đó. Cách làm này chỉ thích hợp khi các ảnh trong CSDL ảnh có nội dung không quá phức tạp. Tuy nhiên, hạn chế của cách làm này là khi CSDL ảnh lớn thì việc bổ sung từ khóa hay lời chú thích sẽ tốn nhiều chi phí tính toán và khá khó khăn. Hơn nữa, có trường hợp một số vấn đề sẽ không thể miêu tả bằng lời chú thích, mà chỉ có thể miêu tả bằng thị giác của ảnh. Ngoài ra, các hệ thống truy vấn ảnh dựa trên từ khóa hay lời chú thích sẽ có sự không đồng nhất do những người sử dụng khác nhau sẽ cho ra các từ khóa khác nhau. Bên cạnh việc truy tìm tài liệu văn bản, các bộ máy tìm kiếm của www.search.yahoo.com hay www.google.com đều hỗ trợ truy vấn ảnh dựa theo các từ khóa. Đây chính là các hệ thống truy vấn ảnh dựa trên từ khóa hay lời chú thích 1.2.2 Truy vấn ảnh dựa trên nội dung (CBIR) Hệ thống truy vấn ảnh dựa trên nội dung (Content-Based Image Retrieval viết tắt là CBIR) là hệ thống truy vấn ảnh dựa trên việc tự động rút Rút trích đặc trưng Biểu diễn của ảnh truy vấn Ảnh truy vấn Lập chỉ mục CSDL các đặc trưng Hệ thống truy vấn ảnh Cơ sở tri thức Độ đo sự tương đồng Hệ thống truy vấn ảnh với cơ sở tri thức 9 trích một số thông tin đặc trưng trong ảnh như: màu sắc, kết cấu, vị trí, hình dạng… đã được nhiều người nghiên cứu với rất nhiều cách tiếp cận khác nhau; do đó rất nhiều hệ thống truy vấn ảnh theo nội dung đã ra đời: như QBIC, VisualSeek, WebSeek, và BlobWorld... Tuy khác nhau, song hầu hết các hệ thống truy vấn ảnh dựa trên nội dung thường tuân theo khung làm việc (framework) sau: (theo tài liệu tham khảo [10]) Mỗi hệ thống sẽ truy vấn dựa trên một số đặc trưng nhất định nào đó và có nhiều tùy chọn để người dùng có thể truy vấn ảnh theo màu sắc, kết cấu, hình dạng hay thậm chí là theo keywords. Theo thống kê tại www.aa- 10 lab.cs.uu.nl/cbirsurvey về lựa chọn đặc trưng để truy vấn của một số hệ thống truy vấn ảnh dựa trên nội dung cụ thể như sau: Hệ thống Query Based Image Content (QBIC) là hệ thống truy vấn dựa trên sự phác thảo do IBM phát triển. Người sử dụng xây dựng một phác thảo, vẽ ra và lựa chọn màu cùng kết cấu dựa theo ảnh truy vấn. Các đặc trưng màu sử dụng là giá trị màu trung bình trong không gian RGB. Các đặc trưng về hình dạng sử dụng là dạng tròn, độ lệch tâm và hướng của trục chính. Hệ thống chỉ mục xây dựng dựa vào cấu trúc cây R* Tree. Độ đo tương đồng về màu trung 11 bình là d2avg(x,y)=(xavg-yavg)t(xavg-yavg); còn về hình dạng thì sử dụng độ đo Euclide có trọng số. Hệ thống VisualSeek là hệ thống truy vấn dựa vào các đặc trưng trực quan của ảnh, sử dụng không gian 166 màu HSV. Sự tương đồng giữa hai ảnh được xác định theo sự tương đồng của các vùng trong ảnh. Để tiến hành truy vấn, trước tiên người dùng phải phác hoạ một số vùng trên ảnh. Sau đó chọn màu cho mỗi vùng, đồng thời xác định vị trí, độ lớn của vùng. Hệ thống sẽ sử dụng hàm so khớp sau để tìm các hình giống với ảnh truy vấn d(cq,ct)=(cq- ct)tA(cq-ct), trong đó cq,ct là hai tập màu của hai ảnh và A=(a[i,j]) là ma trận độ tương đồng của các màu. Hệ thống WebSeek là hệ thống truy vấn ảnh trên web theo catalogue ảnh cho trước và sử dụng phép biến đổi wavelet: sưu tập ảnh sau đó phân lớp ảnh, tạo chỉ mục và cuối cùng là tìm kiếm và hiển thị. Người dùng phải chọn chủ đề trong catalogue, hệ thống sẽ sử dụng hàm so khớp sau để tìm kiếm trong chủ đề tương ứng ảnh giống nhất. Hệ thống BlobWorld là hệ thống truy tìm theo ảnh mẫu dựa trên việc rút trích các dữ liệu điểm nguyên thuỷ cùng các đặc tính giống nhau về màu sắc, kết cấu và hình dạng. Màu sắc sẽ được biểu diễn dưới dạng histogram 218 màu, kết cấu đặc trưng bởi sự tương phản và tính không thẳng đứng; còn các đặc trưng hình dạng tính theo vùng với trọng tâm và hướng. Ảnh truy vấn theo sự phác thảo của các vùng riêng biệt. Hàm đo sự tương đồng là d(h1, h2)=(h1- h2)TA(h1-h2), với A=(aij) là ma trận đối xứng thể hiện sự tương đồng giữa màu i và j. 1.2.3 Truy vấn ảnh theo đối tượng (OBIR) Hệ thống truy vấn ảnh dựa vào đối tượng Object Based Image Retrieval (OBIR) đang được nghiên cứu. Rõ ràng truy vấn theo Object sẽ rất gần với nhu cầu thường thấy của người sử dụng và giống theo nhận thức của con người. Ví dụ tìm tất cả vị trí đỗ xe (có biểu tượng Parking)… Tuy vậy chi phí cho việc dò 12 tìm (detect) ra đối tượng (object) là không nhỏ và khả năng trích ra chính xác object trong ảnh cũng không dễ bởi lẽ định nghĩa thế nào là đối tượng trong ảnh cho đúng với ý nghĩa của đối tượng trong thực tế…? Vì thế chỉ riêng việc nhận diện ra đối tượng cũng đang là một đề tài nghiên cứu nóng bỏng và việc nhận dạng mặt người cũng là một đề tài nghiên cứu. Đối với phương pháp này thì yếu tố quyết định là làm sao rút trích ra chính xác cùng một đối tượng trong các ảnh khác nhau (các hoàn cảnh xuất hiện khác nhau của cùng một đối tượng). 1.2.4 Truy vấn ảnh kết hợp với máy học Để cải thiện hiệu quả truy vấn, người ta xây dựng hệ thống truy vấn ảnh kết hợp với máy học có khả năng nhận phản hồi từ người dùng. Nâng cao hiệu quả truy vấn qua quá trình huấn luyện. Ví dụ như truy vấn CSDL ảnh áp dụng mô hình Mediator Markov Model (MMM) của tác giả Nguyễn Hữu Lộc. Kết quả của hệ thống này cho thấy: trong 1048 ảnh thử nghiệm với 40 truy vấn mẫu sau khi đã có 200 phản hồi: số ảnh tìm được gần bằng 795, số ảnh tìm được đúng gần 510 và số ảnh đúng trong CSDL 670. (Nghĩa là tỷ lệ Precision=0.64 và tỷ lệ Recall là 0.76). Trong các hệ thống truy vấn ảnh áp dụng Nơron Netwrok, người dùng và máy sẽ kết hợp để quyết định các trọng số quan hệ giữa các đặc trưng trong ảnh (như màu sắc, hình dáng…). Ví dụ như hệ thống Nơron Netwrok based Flexible Image Retrieval (NNFIR) của HYOUNG K. LEE and SUK I. YOO sử dụng hàm Radial Basis Function (RBF) network để xác lập mối quan hệ phi tuyến giữa các đặc trưng có kết quả truy vấn với tỷ lệ Precision là 81.70% và tỷ lệ recall là 54.22% (theo [19]). Ngoài ra, các nhà nghiên cứu đã thử tìm cách nhúng Fuzzy Logic vào việc truy vấn ảnh nhưng chưa thành công vì chưa có hàm độ đo sự tương đồng thích hợp cho số mờ bởi nguyên nhân các hàm tính toán đơn giản trên số mờ thì tốt còn các tính toán cao cấp phức tạp thì trên số mờ vẫn còn hạn chế. Ví dụ như phương pháp nhúng Fuzzy Logic vào truy vấn ảnh theo nội dung (Embedding Fuzzy Logic in Content Based Image Retrieval) của Constantin 13 Vertan, Nozha Boujemaa truy vấn ảnh dựa trên Fuzzy Histogram thử nghiệm với nhiều độ đo khác nhau (Zadeh, Algebaric, Lukasiewicz, Hamacher , L1…) kết quả truy vấn tỷ lệ Precision đều< 70.00% (theo [17]). Sau này,Yixin Chen và James Z. Wang (2002) đã xây dựng một hệ thống truy vấn ảnh theo vùng dựa vào Fuzzy logic sử dụng độ đo Unified feature matching (UFM) cho kết quả khá khả quan. Bên cạnh đó, sử dụng máy học Support Vector Machine (SVM) dựa trên các phản hồi của người dùng để xác định ảnh kết quả trả về nào là giống với ảnh truy vấn và ảnh kết quả trả về nào là khác với ảnh truy vấn. Sau đó này hệ thống sẽ đưa ra tập kết quả chính xác hơn. Ví dụ như hệ thống “Support Vector machine Learning for Image Retrieval” của Lei Zhang, Fuzong, Bo Zhang cho tỷ lệ recall là 0.743. Phương pháp này đòi hỏi cơ chế ngăn chặn sự phản hồi sai của người dùng, đồng thời cần có một quá trình huấn luyện cho máy học thì hệ thống mới hoạt động tốt được. 1.3. Truy vấn ảnh dựa trên nội dung Truy vấn ảnh dựa trên nội dung là sự truy vấn ảnh trong CSDL ảnh bằng cách tự động rút trích các đặc trưng cơ bản hay ngữ nghĩa trong ảnh truy vấn và so sánh với các đặc trưng của các ảnh trong CSDL. Để rút ra các đặc trưng trong ảnh người ta phải sử dụng các phép biến đổi như Wavelet, Fourier, DCT, hay các bộ lọc Gabor, bộ lọc trung bình,… 1.3.1 Kỹ thuật truy vấn ảnh theo nội dung mức 1 Truy vấn ảnh theo nội dung ở mức 1 là sự truy vấn dựa trên các đặc trưng cơ bản như màu sắc, hình dạng, kết cấu, vị trí của các thành phần trong ảnh. Ví dụ: “tìm các hình có chứa ngôi sao vàng năm cánh” hay “tìm các hình có số điểm ảnh màu đỏ chiếm ¾, còn lại là màu xanh”… Truy vấn ảnh ở mức độ này được áp dụng rộng rãi trong ứng dụng đăng ký logo, tìm bản vẽ thiết kết. Màu sắc (Colour) là một yếu tố rất quan trọng trong ảnh, có rất nhiều phương pháp truy vấn ảnh dựa trên sự tương tự về màu sắc. Thường các 14 phương pháp truy vấn ảnh dựa theo màu sắc dùng histogram màu. Ví dụ hệ thống truy vấn ảnh dựa trên histogram của Lâm Thị Ngọc Châu, Trường Đại Học Khoa Học Tự Nhiên, Khoa Công Nghệ Thông Tin, 2003. Các hệ thống này thường ít bỏ sót, nghĩa là ảnh cần tìm luôn xuất hiện trong tập ảnh kết quả trả ra nhưng tỷ lệ bắt nhầm rất cao > 50%. Kết cấu (texture), việc truy vấn ảnh dựa trên kết cấu có vẻ là không hiệu quả nhưng có thể dùng nó để phân biệt các vùng hay đối tượng có màu sắc tương đồng như bầu trời và biển cả thì rất tốt… Hình dạng (Shape) là khái niệm có định nghĩa tốt (well-defined) hơn texture và các đối tượng tự nhiên có thể phân biệt nhau bởi hình dạng. Các đặc trưng về shape được sử dụng thường phải độc lập về kích thước và hướng. Ví dụ đặc trưng về tỷ số giữa chu vi và diện tích (compact), đường biên, hình dạng tròn… 1.3.2 Truy vấn ảnh theo ngữ nghĩa Truy vấn ảnh dựa theo ngữ nghĩa có hai cấp độ: ngữ nghĩa cấp thấp dựa trên việc rút trích một số đặc tính logic như “tìm tất cả các hình có tháp Eiffel”; còn ngữ nghĩa cấp cao thì dựa trên các thuộc tính trừu tượng như “tìm các hình có người châu Á đang khiêu vũ”. Phần lớn các kỹ thuật truy vấn ảnh trong CBIR hiện nay đều dựa trên các đặc trưng cơ bản ở mức 1. Đã có một số công trình truy vấn ảnh dựa theo ngữ nghĩa cấp thấp như phương pháp của Ranta và Grimson dùng các mối liên hệ về màu sắc rút ra từ sự phân giải cấp thấp của ảnh để xây dựng nên các mẫu do người dùng định nghĩa (using colour neighbourhood information extracted from low-resolution images to construct user-defined templates). Còn các công trình nghiên cứu truy vấn ảnh dựa trên các đặc trưng ngữ nghĩa cấp cao thì rất ít có báo cáo về vấn đề này. Hiện chỉ có một số công trình đang nghiên cứu để nhận biết ảnh hoàng hôn và bình minh hay là ảnh đó thể hiện thời tiết lạnh hay ấm áp… 1.3.3 Các vấn đề thường gặp phải 15 Hệ thống truy vấn ảnh dựa vào ngữ nghĩa thường gặp phải vấn đề về rút trích và nhận dạng đặc trưng ngữ nghĩa trong ảnh và độ tương đồng tổng thể giữa các đặc trưng ngữ nghĩa với nhau. Ví dụ ảnh 1 có bóng đèn tròn màu đỏ, ảnh 2 có bóng đèn tròn màu cam, ảnh ba có bóng đèn elip màu đỏ. Với trường hợp này việc rút trích chính xác các ngữ nghĩa bóng đèn hình gì và màu gì trong mỗi ảnh là không dễ. Hơn nữa, ành 1 sẽ giống ảnh 2 hơn ảnh 3 hay là ngược lại cũng là một vấn đề hệ thống cần xử lý. Vì ảnh 1 khác về màu và giống nhau về hình dạng đèn với ảnh 2 nhưng ảnh 1 lại khác nhau về hình dạng đèn và giống về màu với ảnh 3. Phương pháp truy vấn ảnh dựa trên các đặc trưng cơ bản đã chứng minh được phần nào hiệu quả của nó qua các hệ thống CBIR level 1 đang được triển khai QBIC, VisualSeek, BlobWorld,… với hiệu quả truy vấn tương đối. Nhưng mỗi một cách lựa chọn đặc trưng cơ bản dùng để truy vấn thường cũng chỉ tối ưu trong một số loại ảnh này mà không tốt trong loại ảnh khác. Cụ thể như, nếu dùng histogram sẽ có vô số ảnh khác nhau nhưng lại có cùng histogram, ngược lại nếu dùng hình dạng thì sẽ hạn chế khi thực hiện truy vấn trong một loại tập ảnh có sự khác biệt ít về hình dạng (như tập ảnh về các loại cá). Ngoài ra, các hệ thống đánh chỉ mục cho dữ liệu văn bản thông thường không thể áp dụng cho việc xây dựng chỉ mục cho CSDL ảnh. Áp dụng hệ thống chỉ mục cho dữ liệu nhiều chiều R*-tree [Beckmann et al, 1990], TV-tree [Lin et al, 1994] và SS+-tree [Kurniawati et al, 1997] vào đánh chỉ mục cho CSDL ảnh cũng có những hạn chế nhất định về chi phí tính toán. 1.3.4 Các cách tiếp cận hiện tại và giải pháp được chọn Để nâng cao hiệu quả truy vấn ảnh theo nội dung, gần đây một số hướng tiếp cận mới đang được nghiên cứu và phát triển: Cùng với sự phát triển mạnh mẽ phép biến đổi wavelet, cách tiếp cận truy vấn ảnh dựa trên phép biến đổi này cũng phát triển theo. Một số công trình nghiên cứu theo hướng này đã ra đời và vẫn đang tiếp tục phát triển để cho ra những kết quả truy vấn chính xác hơn. Song, sử dụng phép biến đổi wavelet, cũng như Fourier hay DCT trước đây đòi hỏi chi phí tính toán cao. Cho nên 16 để giai quyết vấn đề này, người ta thường chọn phép biến đổi wavelet haar để giảm bớt chi phí tính toán. Ví dụ hệ thống áp dụng biến đổi wavelet vào truy vấn ảnh trong luận văn của tác giả Nguyễn Văn Diêu thời gian tìm kiếm 10 ảnh trong 1000 ảnh dùng độ đo l1(Z) trên V4 mất 3 phút với kết quả 85%. Một hướng tiếp cận khác khá mới mẽ và đang được quan tâm là kết hợp các đặc trưng cơ bản lại để truy vấn. như phương pháp kết hợp màu sắc và kết cấu (Anh-Minh Hoàng, "Color-texture Analysis for Content-Based Image Retrieval”) Phương pháp này đang trong giai đoạn hoàn thiện: (theo tài liệu tham khảo [7]) Nghiên cứu trên cho thấy việc kết hợp hai hay nhiều đặc trưng để truy vấn là phương pháp hoàn toàn có thể. Trong phạm vi nghiên cứu của luận văn này sẽ kết hợp các đặc trưng về màu sắc, hình dạng, vị trí để truy vấn ảnh. 17 Ta thấy rằng 2 ảnh (1) và (2) sẽ có cùng histogram nên nếu truy vấn dựa trên đặc trưng histogram màu thì không thể phân biệt chúng. Nếu chỉ dùng đặc trưng hình dạng thì ta không thể phân biệt (4) và (5). Thậm chí khi kết hợp màu sắc và hình dạng thì ta vẫn không thể phân biệt được hình (3) và (4) vì nó chỉ khác nhau về vị trí của hình tròn. Kết hợp cả 3 đặc trưng về màu sắc hình dạng và vi trí thì ta hoàn toàn phân biệt được cả 5 hình trên.Vì vậy trong phạm vi đề tài nghiên cứu này sẽ tìm ra phương pháp kết hợp các đặc trưng về màu sắc hình dạng và vị trí. Tuy việc kết hợp các đặc trưng lại với nhau sẽ cải thiện đáng kể kết quả truy vấn nhưng sẽ gặp khó khăn trong việc tìm và chọn độ đo sự tương đồng giữa 2 ảnh (Similary Measure) theo nhiều đặc trưng và xây dựng hệ thống chỉ mục cho CSDL ảnh truy vấn dựa trên nhiều đặc trưng. 1.4. Một số hệ thống truy vấn ảnh cụ thể 1.4.1 Truy vấn ảnh dựa trên histogram màu Histogram của một ảnh là một hàm cung cấp tần suất xuất hiện của mỗi mức xám. Ta có thể biểu diễn histogram trong hệ trục oxy với trục hoành Ox biểu diễn số mức xám từ 0 đến L (số mức xám), trục tung Oy biểu diễn số điểm ảnh cho một mức xám tương ứng. (5) (4) (1) 100.00% (3) 18 Nghĩa là, histogram của ảnh số có mức xám [0,L] là một hàm rời rạc h(rk)=nk với rk : mức xám thứ k và nk là số pixel có mức k. Thường ta sẽ chuẩn hoá histogram là p(rk)=nk/n với n là tổng số pixel trong ảnh. Và lúc này ta có : ⎟⎠ ⎞⎜⎝ ⎛ =∑ = L k krp 0 1)( Độ đo giữa 2 histogram gọi là độ đo phần giao cặp histogram (histogram intersection measure) của ảnh q và ảnh t là: ∑ ∑ ∑ = = =−= L m L m tq L m tq tq mpmp mpmp v 0 0 0 , ))(),(min( ))(),(min( 1 Hệ thống truy vấn ảnh của tác giả Lâm Thị Ngọc Châu sẽ xám hoá ảnh màu RGB về ảnh xám 256 mức từ 0..255. Theo công thức mức xám Y = 0.114*R+0.587*G +0.299*B. Biểu đồ mức xám sẽ phân thành các loại ĐEN, TRẮNG. Với ; ÐEN 255 0 127 0 ∑ ∑ = == i i i i X X TRẮNG ∑ ∑ = == 255 0 255 128 i i i i X X Trong đó, Xi là số pixel có mức xám i. Rồi ĐEN sẽ phân thành Đ1, Đ2,… như sau: HISTOGRAM ĐEN TRẮNG Đ1 Đ2 T1 T2 Đ11 Đ12 Đ21 Đ22 T11 T12 T21 T22 19 Việc tạo chỉ mục sẽ được thực hiện tăng dần theo cột đen và giảm dần theo cột trắng theo 3 mức của cây nhị phân phía trên. 1.4.2 Truy vấn ảnh sử dụng chỉ mục màu sắc, hình dạng và vị trí Hệ thống “Region-based image retrieval using integrated color, shape and location index" B.G. Prasad, K.K. Biswas, và S.K. Gupta là hệ thống truy vấn ảnh dựa theo chỉ mục màu sắc hình dạng và vị trí. Hệ thống có đưa ra được chỉ mục kết hợp nhưng không tìm ra đựơc độ đo sự tương đồng dựa theo màu sắc hình dạng và vị trí mà chỉ dựa theo sự trùng khớp về chỉ mục. Hệ thống sẽ sử dụng không gian màu giảm 25 màu mà mắt người dễ phân biệt (Black, Sea Green,…Organe,White theo Computer Vision and Image Understanding 94(2004) 193-233). Theo bảng tra cứu màu sau: Thứ tự Màu R G B 1 Black 0 0 0 2 Sea green 0 182 0 3 Light green 0 255 170 4 Olive green 36 73 0 5 Aqua 36 146 170 6 Bright green 36 255 0 7 Blue 73 36 170 8 Green 73 146 0 9 Turquoise 73 219 170 10 Brown 109 36 0 11 Blue gray 109 109 170 12 Lime 109 219 0 13 Lavender 146 0 170 14 Plum 146 109 0 15 Teal 146 182 170 16 Dark red 182 0 0 17 Magenta 182 73 170 18 Yellow green 182 182 0 19 Flouro green 182 255 170 20 Red 219 73 0 21 Rose 219 146 170 22 Yellow 219 255 0 23 Pink 255 36 170 24 Orange 255 146 0 25 White 255 255 255 20 Về hình dạng sẽ tiến hành phép quay chuẩn hoá trục và biến đổi tỷ lệ để chuẩn hoá kích thước và hướng. Sau đó tính toán các thông số hình dạng: trục chính, trục phụ, hình chữ nhật cơ sở, độ lệch tâm, trọng tâm, độ bao phủ dòng, bao phủ cột… Về vị trí sẽ chia ảnh làm 9 phân vùng vị trí đánh số như sau: Kết quả thực nghiệm của hệ thống: Dựa trên màu sắc Dựa trên hình dạng Tỉ lệ precision Tỷ lệ recall Tỉ lệ precision Tỷ lệ recall Trung bình 0.743401 0.528 0.58338 0.393825 Độ lệch chuẩn 0.26772 0.218 0.205423 0.187294 Dựa trên màu sắc- hình dạng Dựa trên màu sắc – hình dạng – vị trí Tỉ lệ precision Tỷ lệ recall Tỉ lệ precision Tỷ lệ recall Trung bình 0.932563 0.355601 0.788688 0.593624 Độ lệch chuẩn 0.176627 0.257311 0.279232 0.33318 1.4.3 Truy vấn ảnh dựa trên mạng Nơron Hệ thống “Nơron Netwrok based Flexible Image Retrieval (NNFIR)” của HYOUNG K. LEE, SUK I. YOO sử dụng mạng Nơron đối xứng tâm Radial Basis Function network (RBFN) để kết hợp giá trị các đặc trưng. 21 Các thành phần cơ bản trong NNFIR: Query Image Feature Extrator DB Searcher RBFN Incremental Learning Metric values Combiner using RBFN User Feedback Retrieved Images Tập ảnh kết q (theo tài liệu tham khảo [19]) Rút trích các đặc trưng, mỗi ảnh q đều dùng không gian màu RGB, sẽ được đặc trưng bởi một vector đặc trưng Fq: },...,,{ 2921 qqqq fffF = là các histogram màu Red, Green, Blue xác định như sau: qqq fff 321 ,, uả 0 ngöôïc laïi 0 0 M N vôùi q i x y kq i x y f k − − = = = = ∑ ∑[ ] [ ][ ]{1 1 1 , Với 0<=k<=L và i=1,2,3 trong đó L số mức màu của ảnh. 22 qqq fff 654 ,, và là trung bình và phương sai của các thành phần màu red, green, blue xác định như sau: qqq fff 987 ,, [ ][ ] [ ][ ]( ) 1 1 0 0 21 1 3 0 0 3 , 4,5,6 6 , 7,8,9 M N q i x y M N q q j j x y f q i x y MN khi i f q j x y f MN khi j − − = = − − − = = = − = = − − = ∑∑ ∑∑ Sau đó áp dụng phép biến đổi wavelet song trực giao lên ảnh q đến mức 3 ta được các hệ số sau: xấp xĩ wavelet mức 1, wavelet mức 1 ngang, dọc, đường chéo, wavelet mức 2 ngang, dọc, đường chéo, wavelet mức 3 ngang, dọc, đường chéo. Ta có và là trung bình và phương sai của các hệ số wavelet thu được ở trên. qq ff 1910 ... qq ff 2920 ... Ảnh gốc 23 Ảnh qua biến đổi wavelet song trực giao mức 1 Ảnh qua biến đổi wavelet song trực giao mức 2 24 Ảnh qua biến đổi wavelet song trực giao mức 3 Để so sánh histogram ta dùng độ đo phần giao của hai histogram như sau: [ ] [ ]( ) ( ) 1 1 1 0 0 0 min , 1 min , vôùi ,L L M q t i im i q t i i q q t i i im m t i f m f m v f f f f f f− − − = = = = − = = ∑ ∑ ∑ Với i=1,2,3. Để so sánh các đặc trưng khác ta sử dụng phép trừ đơn giản: , 4,5,...,29q ti i iv f f i= − = Vai trò của mạng Nơron RBF: dùng để kết hợp các giá trị khoảng cách vi. Input của mạng Nơron RBF là tập các khoảng cách vk giữa 2 ảnh I1, I2. Nếu tất cả các đặc trưng của 2 ảnh này giống nhau ta mong muốn Output sẽ là 1 và nếu hoàn toàn khác nhau ta mong muốn Output là 0. Khi nhận được tập ảnh kết quả của ảnh truy vấn thì người dùng có thể phản hồi trên từng ảnh mà mình thấy thoả mãn hay không là alike similar hay different. Hàm RBF là ( ) ( ) 1 R i i i f x c g x x = = −∑ 25 với g là một hàm Gaussian có dạng: ( ) 2exp 2 ii x xg x x σ ⎛ ⎞−− = −⎜ ⎟⎝ ⎠ Mạng Nơron RBF có thể minh họa như sau: Quá trình huấn luyện sẽ điều chỉnh các tham số ci dựa theo phản hồi của người dùng. Từ đó cho kết quả truy vấn ngày càng chính xác hơn. Hệ thống cho kết quả khả quan sau 5 lần phản hồi của người dùng. 26 Kết quả đạt được của hệ thống NNFIR: (theo tài liệu tham khảo [19]) Độ bao phủ (Recall) = Số ảnh đúng trả ra/Tổng số ảnh đúng trong CSDL. Độ chính xác (Precision) = Số ảnh đúng trả ra/Tổng số ảnh trả ra. 27