Tài liệu Nghiên cứu vài kỹ thuật tra cứu ảnh và ứng dụng vào bài toán kiểm chứng cổ vật

MỤC LỤC DANH MỤC CÁC CHỮ VIẾT TẮT ....................................................................................6 MỞ ĐẦU ...............................................................................................................................7 CHƯƠNG 1: TỔNG QUAN VỀ TRA CỨU ẢNH .........................................................11 1.1. VẤN ĐỀ TRA CỨU ẢNH .......................................................................................11 1.2. MỘT SỐ PHƯƠNG PHÁP TRA CỨU ẢNH ..........................................................12 1.2.1. Tra cứu ảnh theo nội dung .................................................................................13 1.2.2. Tra cứu ảnh theo bản thể (ontology-based image retrieval) ..............................15 1.2.3. Tra cứu ảnh theo đồ thị (graph based image retrieval) ......................................17 U CHƯƠNG 2: TRA CỨU ẢNH THEO NỘI DUNG........................................................19 2.1. GIỚI THIỆU .............................................................................................................19 2.2. MÔ HÌNH HỆ THỐNG TRA CỨU ẢNH THEO NỘI DUNG ..............................20 2.3. CÁC PHƯƠNG PHÁP MÔ TẢ NỘI DUNG ẢNH .................................................21 2.3.1. Mô tả các đặc điểm màu sắc ..............................................................................22 2.3.2. Mô tả các đặc điểm kết cấu................................................................................29 2.3.3. Mô tả các đặc điểm hình dạng ...........................................................................40 2.3.4. Thông tin về không gian ....................................................................................55 2.4. ĐÁNH GIÁ ĐỘ TƯƠNG TỰ VÀ XÂY DỰNG SƠ ĐỒ ĐÁNH CHỈ SỐ..............59 2.4.1. Đánh giá độ tương tự .........................................................................................59 2.4.2. Xây dựng sơ đồ đánh chỉ số...............................................................................62 2.5. TƯƠNG TÁC VỚI NGƯỜI SỬ DỤNG ..................................................................67 2.5.1. Đặc tả truy vấn...................................................................................................67 2.5.2. Xử lý phản hồi ...................................................................................................69 2.6. HIỆU NĂNG CỦA HỆ THỐNG TRA CỨU ẢNH .................................................70 U CHƯƠNG 3: ỨNG DỤNG................................................................................................73 3.1. GIỚI THIỆU BÀI TOÁN TRA CỨU CỔ VẬT.......................................................73 3.2. PHÂN TÍCH BÀI TOÁN .........................................................................................74 3.3. XÂY DỰNG CHƯƠNG TRÌNH QUERYIMAGE..................................................75 3.3.1. Sơ đồ khối tổng quát ..........................................................................................75 3.3.2. Tra cứu theo hình dạng ......................................................................................76 3.3.3. Tra cứu theo màu sắc .........................................................................................81 3.3.4. Sử dụng chương trình QueryImage ..................................................................82 3.4. KHẢ NĂNG MỞ RỘNG CỦA CHƯƠNG TRÌNH ................................................84 3.4.1. Những hạn chế của chương trình.......................................................................84 3.4.2. Khả năng mở rộng .............................................................................................84 KẾT LUẬN..........................................................................................................................86 TÀI LIỆU THAM KHẢO ...................................................................................................89 DANH MỤC CÁC CHỮ VIẾT TẮT Chữ tắt Dạng đầy đủ Nghĩa tiếng Việt PCA Principal Component Analysis Phân tích thành phần cơ bản KL Karhumen-Loeve (transform) Biến đổi Karhumen-Loeve Kullback-Leibler SAR Simultaneous Auto-Regressive Tự thoái lui đồng thời MLE Maximum likelihood estimation Phép ước lượng khả năng tối đa LSE Least square error Sai số bình phương tối thiểu PWT Pyramid-structured Biến đổi dạng sóng kiểu hình chóp wavelet transform TWT Tree-structured Biến đổi dạng sóng kiểu hình cây wavelet transform MRF Markov random field Trường ngẫu nhiên Markov DC Direct Current Thành phần một chiều SOM Self Organization Map Bản đồ tự tổ chức AVR Average rank Thứ hạng trung bình MRR Modified retrieval rank Thứ hạng tra cứu sửa đổi NMRR Nomalized retrieval rank Modified Thứ hạng chuẩn hoá tra cứu sửa đổi Mở đầu MỞ ĐẦU Những năm gần đây, ả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. Mặt khác các công nghệ chế tạo thiết bị lưu trữ luôn được cải tiến để cho ra đời các thiết bị lưu trữ có dung lượng lớn và giá thành hạ làm cho việc lưu trữ ảnh dưới dạng các file trở nên phổ biến. Thêm nữa là sự phát triển của mạng Internet làm cho số lượng ảnh số được đưa lên lưu trữ và trao đổi qua Internet là rất lớn. Tuy nhiên khi số lượng ảnh được lưu trữ trở nên rất lớn thì vấn đề 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 tìm kiếm, tra cứu ảnh hiệu quả, có độ chính xác cao và có hiệu năng tốt. Việc tìm kiếm được một bức ảnh mong muốn trong hàng triệu bức ảnh thuộc đủ loại chủ đề khác nhau là rất khó khăn. Khi số lượng ảnh trong một bộ sưu tập còn ít, việc nhận diện một bức ảnh hay việc so sánh sự giống và khác nhau giữa nhiều bức ảnh có thể thực hiện được bằng mắt thường, tuy nhiên khi có số lượng rất lớn ảnh thì việc so sánh bằng mắt thường là rất khó khăn, đòi hỏi phải có những phương pháp hiệu quả và chính xác hơn. 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ụ như 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 mềm so sánh mẫu chữ ký tốt. Thực tế hiện nay tại các ngân hàng ở Việt nam người ta vẫn phải sử dụng phương pháp so sánh bằng mắt thường vì việc so sánh chữ ký bằng phần mềm vẫn chưa thực hiện được. Một ví dụ khác là bài toán quản lý biểu -7- Mở đầu trưng (logo) trong lĩnh vực sở hữu trí tuệ. Khi một đơn vị muốn đăng ký logo riêng cho đơn vị của mình thì cơ quan quản lý phải tiến hành đánh giá xem mẫu logo đó đã được sử dụng hay chưa hoặc có tương tự với mẫu logo nào đó đang được sử dụng hay không. Trong trường hợp này nếu sử dụng mắt thường để duyệt thì sẽ tốn rất nhiều thời gian, nếu có các phần mềm cho phép tìm kiếm trong cơ sở dữ liệu ảnh có sẵn những biểu trưng tương tự với biểu trưng mẫu thì việc đánh giá sự tương tự sẽ dễ dàng hơn nhiều. Các ứng dụng phức tạp hơn như so sánh mẫu vân tay, tìm kiếm ả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ự. Đối với lĩnh vực bảo tồn, bảo tàng, vấn đề lưu trữ và tra cứu ảnh số có vai trò ngày càng quan trọng. Ảnh của các tác phẩm hội hoạ, điêu khắc hoặc các cổ vật được lưu trữ dưới dạng các file ảnh sẽ đảm bảo được chất lượng tốt hơn, thời gian lưu trữ lâu dài hơn và việc trao đổi hay giới thiệu với công chúng cũng dễ dàng hơn. Bài toán tra cứu cổ vật xuất phát từ một thực tế của ngành bảo tồn, bảo tàng là khi sưu tầm được một cổ vật mới, người ta cần xác định hàng loạt các thuộc tính như niên đại, chất liệu, nguồn gốc và có thể là chủ sở hữu của cổ vật đó. Nếu có được sự trợ giúp của phần mềm tra cứu ảnh phù hợp thì người ta có thể dễ dàng xác định xem mẫu cổ vật đó đã được lưu trữ trong cơ sở dữ liệu nào hay chưa, có những loại cổ vật nào tương tự với nó trong kho tàng cổ vật của thế giới và phần mềm có thể đưa ra ảnh của các loại cổ vật có màu sắc, hình dạng, hoa văn tương tự với cổ vật vừa tìm thấy. Những thông tin này sẽ giúp ích rất nhiều cho các chuyên gia trong quá trình phân loại, kiểm chứng một cổ vật. Vấn đề này chính là động lực để chúng tôi tìm hiểu các phương pháp tra cứu ảnh số đang được ứng dụng nhiều trong thực tế và tìm kiếm phương pháp phù hợp nhất để giải quyết bài toán này. 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 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 đó -8- Mở đầu 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, tuy nhiên lại 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 [1]. 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). Ý 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 [1, 6, 10]. Một số hệ thống tra cứu ảnh nổi tiếng như QBIC (IBM), Virage (Virage Inc.), Photobook (MIT), VisualSEEK (Columbia University)... đã áp dụng khá thành công phương pháp tra cứu này [1, 6, 7, 12, 17]. Trên cơ sở của phương pháp tra cứu ảnh theo nội dung người ta còn tìm cách bổ sung, cải tiến để cho ra đời một số phương pháp tra cứu ảnh khác như tra cứu ảnh theo bản thể, tra cứu ảnh theo đồ thị, tra cứu ảnh theo nhận thức v.v... [8, 9] Nội dung của đề tài này giới thiệu cơ sở lý thuyết và các ứng dụng chính của một số phương pháp tra cứu ảnh, trong đó đi sâu vào giới thiệu phương pháp tra cứu ảnh theo nội dung. Trên những cơ sở đó tiến hành thử nghiệm một phương pháp cụ thể để xây dựng một chương trình phần mềm tra cứu cổ vật cho phép đọc vào một ảnh cổ vật mẫu và tìm kiếm những ảnh tương tự với ảnh mẫu trong một tập hợp các ảnh cho trước theo hai đặc điểm là hình dạng và màu sắc của cổ vật. Chương trình sẽ trợ giúp đắc lực cho công tác bảo tồn, bảo tàng cũng như có thể cải tiến để áp dụng cho một số lĩnh vực khác như giáo dục, sở hữu trí tuệ, y học, khoa học hình sự... Nội dung luận văn gồm có ba chương: Chương 1: Trình bày tổng quan vấn đề tra cứu ảnh, giới thiệu sơ lược một số phương pháp tra cứu ảnh và một số hệ thống tra cứu ảnh tiêu biểu . -9- Mở đầu Chương 2: Giới thiệu chi tiết về phương pháp tra cứu ảnh theo nội dung, trong đó giới thiệu mô hình của một hệ thống tra cứu ảnh theo nội dung và một số kỹ thuật cơ bản được sử dụng để xây dựng hệ thống tra cứu ảnh theo nội dung. Chương 3: Giới thiệu một ứng dụng của phương pháp tra cứu ảnh theo nội dung áp dụng vào bài toán tìm kiếm cổ vật; những hạn chế và khả năng mở rộng của chương trình ứng dụng đó. -10- Chương 1: Tổng quan về tra cứu ảnh CHƯƠNG 1: TỔNG QUAN VỀ TRA CỨU ẢNH 1.1. VẤN ĐỀ TRA CỨU ẢNH Những năm gần đây, vấn đề tra cứu ảnh số nhận được sự quan tâm ngày càng lớn. Nguyên nhân một phần là do sự phát triển của công nghệ chế tạo thiết bị thu nhận và lưu trữ ảnh số cũng như sự phát triển mạnh mẽ của mạng Internet. Người sử dụng trong nhiều lĩnh vực khác nhau có cơ hội để truy cập và sử dụng các kho lưu trữ ảnh thuộc đủ loại chủ đề và với nhiều kiểu định dạng ảnh khác nhau. Tuy nhiên người ta cùng nhận thấy rằng việc tìm được một bức ảnh mong muốn trong bộ sưu tập ảnh đa dạng có kích thước lớn là rất khó khăn. Tra cứu ảnh là một quá trình tìm kiếm trong một cơ sở dữ liệu ảnh những ảnh thoả mãn một yêu cầu nào đó. Ví dụ, người sử dụng có thể tìm kiếm tất cả các ảnh về chủ đề về biển 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 về tra cứu ảnh 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. Vấn đề tra cứu ảnh đã được nhìn nhận rộng rãi và việc tìm kiếm các giải pháp cho vấn đề này trở thành một lĩnh vực rất sôi động, thu hút sự quan tâm của nhiều nhà nghiên cứu và phát triển. Những kỹ thuật tra cứu ảnh số đã được nghiên cứu từ cuối những năm 70 của thế kỷ 20. Năm 1979 một cuộc hội thảo chuyên đề về "Các kỹ thuật tổ chức cơ sở dữ liệu cho các ứng dụng đồ hoạ" được tổ chức ở thành phố Florence, Italia. Từ đó đến nay, khả năng ứng dụng cao của các kỹ thuật quản lý cơ sở dữ liệu ảnh đã thu hút sự quan tâm của nhiều nhà nghiên cứu [1]. -11- Chương 1: Tổng quan về tra cứu ảnh 1.2. MỘT SỐ PHƯƠNG PHÁP TRA CỨU ẢNH Các phương pháp tra cứu ảnh được sử dụng đầu tiên không dựa trên các đặc điểm trực quan của ảnh mà dựa trên các chú thích bằng lời của các bức ảnh, đầu tiên người ta gán cho mỗi ảnh một câu chú thích bằng lời (text) dựa trên một đặc điểm nào đó của ảnh, sau đó sử dụng các kỹ thuật tìm kiếm văn bản thông thường để tìm kiếm ảnh. Phương pháp tra cứu ảnh dựa trên văn bản như trên sử dụng các kỹ thuật cơ sở dữ liệu truyền thống để quản lý ảnh. Dựa vào các lời chú thích, người ta có thể tổ chức cơ sở dữ liệu ảnh bằng các phân lớp theo chủ đề hay theo ngữ nghĩa và việc duyệt cơ sở dữ liệu ảnh chỉ dựa trên các truy vấn kiểu Bool thông thường. Phương pháp tra cứu ảnh dựa trên chú thích như trên còn được gọi là tra cứu ảnh theo từ khoá. Do việc xây dựng các thuật toán có khả năng tự động sinh ra các chú thích cho một cơ sở dữ liệu ảnh có nhiều chủ đề là hết sức khó khăn nên nói chung các hệ thống tra cứu ảnh kiểu này vẫn yêu cầu phải chú thích ảnh một cách thủ công và trên thực tế việc chú thích ảnh như vậy tốn rất nhiều công sức và quan trọng hơn là nó mang tính chủ quan, bị ảnh hưởng của hoàn cảnh và thường là không đầy đủ. Vì vậy các hệ thống tra cứu ảnh dựa theo từ khoá không hỗ trợ được những kiểu truy vấn phụ thuộc tác vụ [1, 8, 9] 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ừ khoá. Nội dung chính của phương pháp này là dựa trên sự tương tự của những đặc điểm trực quan của ảnh như màu sắc, hình dạng, kết cấu hay bố cục không gian của ảnh để phân loại, sắp xếp các ảnh trong một cơ sở dữ liệu ảnh. Tuy nhiên những đặc điểm mà phương pháp này trích chọn để tra cứu vẫn là những đặc điểm ở mức thấp, chưa phản ánh được nội dung mang tính ngữ nghĩa của một đối tượng ảnh. Vì vậy người ta đã đưa ra một số cách tiếp cận mới phát triển phương pháp tra cứu ảnh theo nội dung thành các phương pháp tra cứu ảnh theo đồ thị [9] hay tra cứu ảnh theo bản thể [8]... -12- Chương 1: Tổng quan về tra cứu ảnh Phần sau đây giới thiệu sơ lược một số mốc phát triển quan trọng của phương pháp tra cứu ảnh theo nội dung và một số phương pháp tra cứu ảnh cải tiến đang được áp dụng trong các hệ thống tra cứu ảnh. Chi tiết về phương pháp tra cứu ảnh theo nội dung sẽ được đề cập trong chương 2. 1.2.1. Tra cứu ảnh theo nội dung [1, 6, 10] Đầu những năm 1990, do sự phát triển của Internet và các công nghệ ảnh số tiên tiến, số lượng ảnh số trong các lĩnh vực khoa học, giáo dục, y tế, công nghiệp... được tung ra cho người sử dụng truy cập tăng lên một cách nhanh chóng. Điều này làm cho những khó khăn của các hệ thống tra cứu ảnh dựa theo văn bản càng thêm khó giải quyết. Sự cần thiết phải có một hệ thống quản lý hiệu quả các thông tin trực quan là vô cùng cấp bách. Nhu cầu đó chính là động lực thúc đẩy các nhà nghiên cứu vào cuộc mạnh mẽ hơn và cũng là nguyên nhân dẫn đến sự ra đời của phương pháp tra cứu ảnh theo nội dung. Năm 1992, Quỹ Khoa học Quốc gia (National Science Foundation) của Hoa Kỳ đã tổ chức một buổi Hội thảo về các hệ thống quản lý thông tin trực quan để xác định hướng đi mới cho các hệ thống quản lý cơ sở dữ liệu ảnh. Tại buổi hội thảo này người ra phải công nhận với nhau rằng cách hiệu quả nhất để thể hiện và sắp xếp các thông tin trực quan của một bức ảnh là phải dựa trên các thuộc tính được trích chọn từ chính những bức ảnh đó. Các nhà nghiên cứu từ các lĩnh vực khác nhau như thị giác máy tính (computer vision), quản lý cơ sở dữ liệu, giao diện người-máy và tra cứu thông tin đã cùng bị hấp dẫn bới hướng nghiên cứu này [1]. Từ đó đến nay, những công trình nghiên cứu về tra cứu ảnh theo nội dung được triển khai rất nhiều. Từ năm 1997 những kết quả nghiên cứu về tra cứu ảnh theo nội dung như các kỹ thuật trích chọn thông tin trực quan, tổ chức, sắp xếp, thiết kế truy vấn, tương tác -13- Chương 1: Tổng quan về tra cứu ảnh với người dùng, quản lý cơ sở dữ liệu... được công bố ngày một nhiều. Tương tự như vậy, một số lượng lớn các mô hình nghiên cứu cũng như sản phẩm thương mại các hệ thống tra cứu ảnh theo nội dung đã được các trường đại học, các cơ quan nghiên cứu và các công ty tin học cho ra đời. Một số hệ thống tra cứu ảnh theo nội dung tiêu biểu: o QBIC hay Query By Image Content do hãng IBM và Trung tâm nghiên cứu Almaden hợp tác phát triển. Hệ thống này cho phép người sử dụng dùng các công cụ đồ hoạ để mô tả và hiệu chỉnh truy vấn dựa trên nhiều thuộc tính trực quan như màu sắc, kết cấu và hình dạng của đối tượng ảnh. QBIC hỗ trợ các kiểu truy vấn dựa trên ảnh mẫu, dựa trên hình phác thảo hoặc dựa trên các mẫu màu hoặc mẫu kết cấu [17]. o VIR Image Engine do Công ty Virage Inc. phát triển, cũng giống như QBIC, hệ thống này cho phép tra cứu ảnh dựa trên các thuộc tính màu sắc, kết cấu và cấu trúc [17]. o VisualSEEK và WebSEEK do trường Đại học Tổng hợp Columbia (Mỹ) phát triển. Cả hai hệ thống này đều hỗ trợ các cách tìm kiếm theo màu sắc, kết cấu và bố cục không gian [17]. o NeTra do trường Đại học Tổng hợp California (Mỹ) phát triển. Hệ thống này hỗ trợ tìm kiếm theo màu sắc, hình dạng, bố cục không gian và kết cấu cũng như theo sự phân mảnh của ảnh [17]. o MARS hay Multimedia Analysis and Retrieval System do trường Đại học Tổng hợp Illinois phát triển, hỗ trợ tìm kiếm theo màu sắc, bố cục không gian, kết cấu và hình dạng [17]. o Viper hay Visual Information Processing for Enhanced Retrieval do trường Đại học Geneva phát triển, tìm kiếm theo màu sắc và kết cấu [17]. -14- Chương 1: Tổng quan về tra cứu ảnh Ngoài ra người ta còn giới thiệu nhiều phương pháp tra cứu ảnh khác như tra cứu ảnh theo nhận thức (Perception based image retrieval), tra cứu ảnh theo phân đoạn (Segment based image retrieval), tra cứu ảnh theo đồ thị (Graph based image retrieval), tra cứu ảnh theo bản thể (Ontology based image retrieval)...Tuy nhiên phần lớn trong số các phương pháp đó lại sử dụng các nguyên tắc cơ bản của tra cứu ảnh theo nội dung. 1.2.2. Tra cứu ảnh theo bản thể [8] 1.2.2.1. Giới thiệu Cách đơn giản nhất để xuất bản một ảnh lên kho lưu trữ là tạo một giao diện truy vấn dựa trên từ khoá cho một cơ sở dữ liệu. Ở đó người sử dụng có thể chọn giá trị lọc hoặc sử dụng từ khoá cho các trường khác nhau của cơ sở dữ liệu, chẳng hạn như "người tạo" hoặc "thời gian" hoặc cho các mô tả nội dung bao gồm phân loại và nội dung văn bản. Nhiều truy vấn có thể kết hợp bằng cách sử dụng các biểu thức logic [8]. Các phương pháp tìm kiếm theo từ khoá có rất nhiều hạn chế: một từ khoá trong văn bản không chỉ ra được văn bản đó có thích hợp hay không và các văn bản thích hợp lại có thể không chứa một từ khoá nhất định. Các từ đồng nghĩa làm giảm độ thu hồi, các từ đồng âm làm giảm độ chính xác và các quan hệ ngữ nghĩa như quan hệ thượng hạ vị, trái nghĩa, phản nghĩa ... chưa được đề cập đến. Việc tìm kiếm theo từ khoá có ích cho những người sử dụng đã những từ khoá nào được sử dụng để đánh chỉ số ảnh và do đó có thể dễ dàng tạo truy vấn. Tuy nhiên cách tiếp cận này khá khó khăn khi người sử dụng chưa có mục đích rõ ràng, không biết có gì trong cơ sở dữ liệu và kiểu khái niệm ngữ nghĩa có liên quan đến lĩnh vực đang quan tâm. Các vấn đề nảy sinh khi sử dụng phương pháp tìm kiếm bằng từ khoá: -15- Chương 1: Tổng quan về tra cứu ảnh • Cấu thành thông tin cần thiết: người sử dụng không biết chính xác cần phải đặt câu hỏi gì. • Cấu thành truy vấn: người sử dụng không biết phải sử dụng từ khoá gì liên quan với thông tin mà họ muốn tìm kiếm. • Cấu thành kết quả: tạo danh sách các ảnh phù hợp với từ khoá có thể bỏ qua mất một phương diện hay nhất của việc lưu trữ là quan hệ giữa các ảnh trong cơ sở dữ liệu rất đa dạng và phong phú. Công nghệ web ngữ nghĩa (semantic web) hứa hẹn có thể giải quyết được những khó khăn trên. 1.2.2.2. Chú giải ngữ nghĩa Các cách tiếp cận sau thường được sử dụng để chú giải ảnh: - Từ khoá: danh sách các từ được phép sử dụng để chú giải ảnh được hạn chế làm cho việc tìm kiếm dễ dàng hơn. - Phân loại: có nhiều hệ thống phân loại có khả năng phân loại theo nhiều phương diện khác nhau thành các cây phân cấp theo chủ đề. Một ảnh có thể chú thích bằng một tập các chủ đề mô tả ảnh đó. Ví dụ, ảnh trên một chiếc phong bì vẽ một toà lâu đài có thể liên quan tới lớp “phong bì” và lớp “lâu đài”. - Mô tả ảnh: Sử dụng những câu mô tả các đối tượng ảnh có trong ảnh. Hệ thống tra cứu thông tin có nhiệm vụ đánh chỉ số các văn bản này để có thể tìm kiếm bằng từ khoá. 1.2.2.3. Tra cứu ảnh ngữ nghĩa Các bản thể tạo thành hạt nhân của của các hệ thống tra cứu ảnh ngữ nghĩa được sử dụng cho ba mục đích: -16- Chương 1: Tổng quan về tra cứu ảnh o Thuật ngữ chú giải: mô hình bản thể cung cấp thuật ngữ và các khái niệm để diễn tả dữ liệu về dữ liệu (metadata) của các ảnh. o Tìm kiếm theo cách nhìn: các bản thể của một mô hình, chẳng hạn Sự kiện, Con người hoặc Vị trí cho ta các cách nhìn khác nhau vào cùng một nội dung giới thiệu. Mỗi cách nhìn bao gồm các lớp và các trường hợp ví dụ biểu diễn bằng metaphor của một trình duyệt hệ thống file trong đó các lớp tương ứng với các thư mục và các trường hợp ví dụ tương ứng với các file. o Duyệt ngữ nghĩa: Sau khi tìm kiếm được tâm điểm chú ý là một ảnh nào đó, mô hình bản thể ngữ nghĩa cùng với dữ liệu ảnh ví dụ có thể được sử dụng để tìm ra mối quan hệ giữa ảnh được lựa chọn và các ảnh trong cơ sở dữ liệu ảnh. Các ảnh này sẽ được đưa ra cho người sử dụng chọn. Những ảnh đó có thể không phù hợp hoàn toàn với truy vấn nhưng nói chung là tương đối phù hợp. 1.2.3. Tra cứu ảnh theo đồ thị [9] Hạn chế cơ bản của phương pháp tra cứu ảnh theo nội dung và phản hồi thích hợp là chúng dựa trên các đặc điểm mức thấp (màu sắc, kết cấu, hình dạng) của ảnh mà những đặc điểm mức thấp lại rất hạn chế khi thể hiện không chỉ sự tương tự về mặt nội dung mà cả sự tương tự về mặt khái niệm và ngữ cảnh giữa các ảnh với nhau. Mặt khác, các công cụ tra cứu ảnh dựa trên văn bản (text-based) lại bị hạn chế bởi không phải lúc nào ảnh cũng được chú thích đầy đủ và những chú thích nếu có cũng rất khó mô tả đầy đủ được nội dung của một tấm ảnh. Phần sau đây giới thiệu một cách tiếp cận mới xây dựng một hệ thống tra cứu theo nội dung, khái niệm và ngữ cảnh cho phép sử dụng những phản hồi của người -17- Chương 1: Tổng quan về tra cứu ảnh sử dụng về sự thích hợp giữa các ảnh chỉ sử dụng các liên kết giữa các ảnh mà không dựa vào các đặc điểm của ảnh hay các lời chú thích. Như đã giới thiệu ở phần 1.2.1, kỹ thuật tra cứu ảnh theo nội dung dựa vào những đặc điểm mức thấp như màu sắc, kết cấu và hình dạng của đối tượng ảnh. Trong khi các phương pháp mô tả ảnh mức cao có khả năng mô tả gần gũi hơn với trực giác của người sử dụng nhưng việc phát triển những phương pháp đó mới dừng ở mức thử nghiệm và đòi hỏi rất nhiều quá trình xử lý phức tạp. Mặc dù việc mô tả ảnh bằng các đặc điểm mức thấp có thể thực hiện khá hiệu quả và đơn giản nhưng nhược điểm lớn nhất của phương pháp này là không gần gũi với sự cảm nhận trực quan của hầu hết người sử dụng và do đó thường không đủ đáp ứng nhu cầu của người sử dụng. Những ảnh mà ta cảm nhận được sự giống nhau bằng mắt thường nhưng đôi khi lại rất khác nhau nếu so sánh bằng các đặc điểm mức thấp. Động lực của phương pháp này dựa trên một thực tế là những ảnh thích hợp về mặt trực giác thường không có chung những đặc điểm mức thấp nhưng vẫn có sự tương tự về mặt khái niệm và về mặt ngữ cảnh đối với con người. Ví dụ, những ảnh chụp người trong bộ đồ tắm thường có màu sắc, hình dạng và kết cấu rất đa dạng nhưng về mặt khái niệm thì lại được con người cảm nhận là tương tự nhau. Vì vậy phương pháp tra cứu ảnh theo đồ thị được giới thiệu ở đây không dựa trên các đặc điểm ở mức thấp (trừ giai đoạn khởi tạo) mà dựa vào những sự liên kết có tính trực giác giữa các ảnh được thiết lập bởi người sử dụng bằng cách phản hồi thích hợp. Mục tiêu của phương pháp này là xây dựng một sơ đồ để tích luỹ thông tin do những tương tác với người sử dụng theo cách đơn giản hơn phản hồi thích hợp và sử dụng những thông tin này để việc tra cứu ảnh cho những kết quả có ý nghĩa trực giác hơn [8, 9]. -18- Chương 2: Tra cứu ảnh theo nội dung CHƯƠNG 2: TRA CỨU ẢNH THEO NỘI DUNG 2.1. GIỚI THIỆU Phương pháp tra cứu ảnh theo nội dung (Content-Based Image Retrieval) sử dụng các nội dung trực quan của ảnh như màu sắc, hình dạng, kết cấu (texture) và phân bố không gian để thể hiện và đánh chỉ số các ảnh [1, 6, 7, 11]. Trong một hệ thống tra cứu ảnh theo nội dung điển hình (hình vẽ 2.1) các nội dung trực quan của ảnh được trích chọn và mô tả bằng những véc tơ đặc trưng nhiều chiều. Tập hợp các vec tơ đặc trưng của các ảnh trong một cơ sở dữ liệu ảnh tạo thành cơ sở dữ liệu đặc trưng. Quá trình tra cứu ảnh được tiến hành như sau: người sử dụng cung cấp cho hệ thống tra cứu một ảnh mẫu cụ thể hoặc hình vẽ phác thảo của đối tượng ảnh cần tìm. Sau đó hệ thống sẽ chuyển những mẫu này thành các véc tơ đặc trưng và tính toán sự giống nhau (hay độ tương tự) giữa véc tơ đặc trưng của ảnh mẫu và véc tơ đặc trưng của các ảnh trong cơ sở dữ liệu. Sau cùng việc tra cứu được tiến hành với sự trợ giúp của các sơ đồ đánh chỉ số. Sử dụng sơ đồ đánh chỉ số là cách hiệu quả để tìm kiếm trong các cơ sở dữ liệu ảnh. Một số hệ thống tra cứu ảnh mới phát triển gần đây còn tích hợp cả chức năng xử lý phản hồi của người sử dụng để cải tiến các qui trình tra cứu để đưa ra những kết quả tra cứu tốt hơn. -19- Chương 2: Tra cứu ảnh theo nội dung 2.2. MÔ HÌNH HỆ THỐNG TRA CỨU ẢNH THEO NỘI DUNG Phản hồi thích hợp Người sử dụng Tạo truy vấn Cơ sở Dữ liệu ảnh Mô tả Nội dung Trực quan Các Vector Đặc trưng Mô tả Nội dung Trực quan Cơ sở Dữ liệu Đặc trưng Đánh giá độ tương tự Đầu ra Tra cứu và Đánh chỉ số Kết quả tra cứu Hình 2.1: Mô hình hệ thống Tra cứu ảnh theo nội dung Trong mô hình này, người sử dụng sẽ tạo truy vấn bằng cách chọn một ảnh mẫu trong một cơ sở dữ liệu ảnh cho trước hoặc phác thảo một hình vẽ mô tả đối tượng ảnh cần tìm bằng cách sử dụng một giao diện đồ hoạ của hệ thống. Ảnh mẫu đó được đưa qua khối mô tả nội dung trực quan, trong đó người ta sử dụng một phương pháp mô tả nội dung trực quan nào đó để trích chọn một đặc điểm nội dung trực quan để xây dựng thành một véc tơ đặc trưng. Véc tơ đặc trưng của ảnh mẫu sẽ được so sánh với véc tơ đặc trưng tương ứng của các ảnh trong cơ sở dữ liệu ảnh. Kết quả của phép so sánh là một chỉ số đánh giá độ tương tự giữa ảnh mẫu và ảnh lấy ra để so sánh. Dựa vào chỉ số độ tương tự tính toán được ở trên, hệ thống sẽ sắp xếp các ảnh tìm được trong cơ sở dữ liệu ảnh theo một sơ đồ đánh chỉ số nào đó. Danh sách các ảnh tìm được (đã được sắp xếp) được đưa ra đầu ra của hệ thống. -20- Chương 2: Tra cứu ảnh theo nội dung 2.3. CÁC PHƯƠNG PHÁP MÔ TẢ NỘI DUNG ẢNH Nếu nhìn một cách tổng quát thì nội dung của một bức ảnh có thể bao gồm cả nội dung trực quan và nội dung ngữ nghĩa [1]. Nội dung trực quan của ảnh lại được phân làm hai loại là nội dung tổng quan và nội dung đặc tả. Nội dung tổng quan bao gồm màu sắc, kết cấu, hình dạng và các quan hệ không gian giữa các đối tượng ảnh hoặc giữa các vùng ảnh. Nội dung đặc tả thì tuỳ vào từng ứng dụng cụ thể, ví dụ với các ứng dụng tra cứu ảnh người thì mặt người hoặc con mắt là các nội dung đặc tả; với các ứng dụng tra cứu ảnh ô tô thì bánh xe là một nội dung đặc tả [1]. Nội dung ngữ nghĩa có thể phát hiện thông qua các chú thích hoặc sử dụng các phương pháp suy diễn từ nội dung trực quan. Trong khuôn khổ của luận văn này chúng tôi chỉ tập trung vào việc mô tả nội dung trực quan tổng quan của ảnh. Một phương pháp mô tả nội dung trực quan được thiết kế tốt phải có tính bất biến đối với các biến đổi bất thường sinh ra trong quá trình xử lý ảnh (ví dụ như những biến đổi bất thường của độ sáng của cảnh vật). Tuy nhiên cũng cần phải chú ý tới sự cân bằng giữa tính bất biến và khả năng đáp ứng những thay đổi tuỳ ý của các đặc trưng trực quan của ảnh, bởi vì một hệ thống có tính bất biến lớn thì thường là không có tính nhạy cảm, mất khả năng phản ánh những thay đổi nhỏ nhưng rất quan trọng. Một phương pháp mô tả nội dung trực quan có thể là phương pháp toàn cục hoặc phương pháp cục bộ. Phương pháp mô tả nội dung toàn cục sử dụng các đặc trưng trực quan của toàn bộ bức ảnh còn phương pháp mô tả nội dung cục bộ lại sử dụng những đặc trưng trực quan của các vùng ảnh hoặc các đối tượng ảnh để mô tả nội dung của ảnh. Để mô tả được nội dung cục bộ trước hết người ta phải chia ảnh thành các phần riêng biệt. Cách đơn giản nhất để phân chia ảnh là sử dụng một bộ phân hoạch -21- Chương 2: Tra cứu ảnh theo nội dung chia ảnh thành các ô có kích thước và hình dạng giống nhau. Cách phân chia đơn giản như vậy không tạo ra được những vùng ảnh có ý nghĩa thực sự nhưng nó là cách đơn giản để biểu diễn nội dung toàn cục của ảnh với độ chính xác cao hơn. Một phương pháp phân chia tốt hơn là phân chia ảnh thành các vùng đồng nhất dựa vào các tiêu chí sử dụng các thuật toán phân vùng ảnh đã được nghiên cứu và áp dụng trong ngành thị giác máy tính. Một cách phức tạp hơn để phân chia ảnh là thực hiện phân chia theo các đối tượng ảnh để tách ra các đối tượng ảnh có nghĩa thực sự (như quả bóng, cái ô tô hay con ngựa). [1, 10] Phần tiếp theo giới thiệu một số một số kỹ thuật đang được sử dụng rộng rãi để trích chọn các đặc điểm màu sắc, kết cấu, hình dạng và các quan hệ không gian của các đối tượng ảnh. 2.3.1. Mô tả các đặc điểm màu sắc [1, 3, 6] Trên thực tế thì màu sắc được sử dụng nhiều nhất để mô tả nội dung trực quan của ảnh. Lý do là vì màu sắc của ảnh có tác động lớn đến nhận thức của con người về nội dung của ảnh hơn là các đặc điểm khác như hình dạng của các đối tượng ảnh, kết cấu của ảnh hay sự phân bố không gian của các đối tượng ảnh. Màu sắc được biểu diễn thông qua một véc tơ 3 chiều sẽ có khả năng biểu diễn tốt hơn so với việc chỉ sử dụng giá trị độ xám của ảnh (1 chiều). Trước khi xem xét kỹ hơn về các phương pháp mô tả nội dung màu sắc, chúng ta cùng tìm hiểu sơ lược về các không gian màu. 2.3.1.1. Không gian màu Mỗi điểm ảnh trên một bức ảnh có thể được biểu diễn bằng một điểm trong một không gian màu 3 chiều. Những không gian màu được sử dụng nhiều nhất -22- Chương 2: Tra cứu ảnh theo nội dung trong các hệ thống tra cứu ảnh là RGB, CIE L*a*b, CIE L*u*v, HSV và không gian màu đối lập. Người ta cũng chưa chỉ ra được rằng không gian màu nào được sử dụng tốt hơn cho việc tra cứu ảnh. Tuy nhiên tính chất quan trọng nhất để một không gian màu phù hợp để sử dụng trong một hệ thống tra cứu ảnh là tính đồng nhất. Một không gian màu được gọi là có tính đồng nhất nếu các cặp 2 màu tương tự nhau trong không gian màu thì cũng được con người cảm nhận như nhau. Nói một cách khác, khoảng cách đo được giữa hai màu bất kỳ phải có liên quan trực tiếp với độ tương tự sinh học giữa hai màu đó. RGB là không gian màu được sử dụng phổ biến nhất để hiển thị ảnh. Không gian RGB bao gồm 3 thành phần màu là Đỏ (Red), Xanh lá cây (Green) và Xanh lam (Blue). Các thành phần này gọi là màu cộng bởi vì các màu sắc trong không gian RGB đều có thể thu được bằng cách cộng 3 thành phần màu này lại với nhau. Ngược lại, CMY là không gian màu thường sử dụng trong in ấn. Ba thành phần màu của không gian CMY là màu xanh lơ (Cyan), hồng sẫm (Magenta) và vàng (Yellow). Ba thành phần này gọi là các thành phần màu trừ vì mỗi màu trong không gian CMY được sinh ra bởi sự hấp thụ các thành phần màu đó. Cả RGB và CMY đều phụ thuộc thiết bị và không có tính đồng nhất. Các không gian màu CIE L*a*b và CIE L*u*v là các không gian màu không phụ thuộc thiết bị và có thể coi là đồng nhất. Bao gồm các thành phần độ sáng (L) và hai thành phần độ kết tủa màu (sắc độ màu) là a và b hoặc u và v. CIE L*a*b được thiết kế để làm việc với việc trộn các thành phần màu trừ còn CIE L*u*v được thiết kế để làm việc với việc trộn các thành phần màu cộng. Các không gian màu RGB và CIE có thể chuyển đổi với nhau, tức là chúng ta có thể sử dụng các công thức để chuyển đổi một giá trị màu từ không gian màu này sang không gian màu khác. -23- Chương 2: Tra cứu ảnh theo nội dung Không gian màu HSV được sử dụng rộng rãi trong đồ hoạ máy tính và được coi là một phương pháp biểu diễn màu sắc trực quan hơn. Ba thành phần màu là sắc màu (hue), độ bão hoà màu (s) và giá trị độ sáng (v). Thành phần sắc màu không thay đổi khi ta thay đổi độ chiếu sáng hay góc quan sát vì vậy thích hợp để sử dụng trong việc nhận dạng đối tượng ảnh. Cũng có thể dễ dàng chuyển đổi các giá trị từ không gian HSV sang RGB và ngược lại. Không gian màu đối lập sử dụng các trục màu ngược (R-G, 2B-R-G, R+G+B), cách biểu diễn này có ưu điểm là tách được thông tin về độ sáng ra một trục riêng biệt (trục thứ ba). Bằng cách này, hai thành phần kết tủa màu sẽ không bị thay đổi khi thay đổi độ chiếu sáng. Các phần tiếp theo sẽ giới thiệu một số phương pháp mô tả nội dung màu sắc của ảnh: các moment màu, histogram màu, véc tơ gắn kết màu và biểu đồ tương quan màu. 2.3.1.2. Các moment màu Các moment màu đã được sử dụng rất thành công trong nhiều hệ thống tra cứu ảnh đặc biệt là khi ảnh chỉ chứa một đối tượng ảnh. Các thành phần moment bậc nhất (trung vị), bậc hai (phương sai) và bậc ba (độ lệch) đã được chứng minh là có thể được sử dụng rất hiệu quả để biểu diễn sự phân bố màu sắc của ảnh. Công thức toán học để biểu diễn 3 moment này như sau: μi = σi = 1 N N ∑f j =1 1 N (2.1) ij N ∑( f j =1 ij − μi ) 2 (2.2) -24-