Tài liệu Nghiên cứu phương pháp tra cứu ảnh từ trong tài liệu

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2 --------------------------- TRẦN NGỌC ĐỒNG NGHIÊN CỨU PHƢƠNG PHÁP TRA CỨU ẢNH TỪ TRONG ẢNH TÀI LIỆU LUẬN VĂN THẠC SĨ MÁY TÍNH HÀ NỘI, 2015 LỜI CẢM ƠN Trƣớc hết, em xin bày tỏ lòng biết ơn sâu sắc đến thầy hƣớng dẫn PGS.Tiến Sĩ Ngô Quốc Tạo, ngƣời đã tận tình chỉ bảo, giúp đỡ em trong quá trình hình thành đề tài của luận văn. Thầy đã hƣớng dẫn phƣơng hƣớng triển khai đề tài, cách sử dụng tài liệu và tổng kết các kết quả nghiên cứu một cách có hệ thống. Em xin trân thành cảm ơn tới tất cả các thầy cô giáo tại Trƣơng đại học Sƣ Phạm Hà Nội 2 đã đem tri thức và tâm huyết của mình để truyền đạt vốn kiến thức quý báu cho chúng em và luôn luôn tạo mọi điều kiện tốt nhất cho chúng em trong suốt quá trình theo học tại trƣờng. Em xin chân thành cảm ơn quý Thầy, Cô giáo và Ban lãnh đạo trƣờng! Cảm ơn đề tài: “Hệ thống đeo tay hỗ trợ đọc sách tiếng Việt dành cho ngƣời khiếm thị ” Mã số VAST01.07/15-16 hỗ trợ trong thực hiện luận văn. Luận văn hoàn thành, ngoài sự cố gắng của bản thân còn có sự động viên, giúp đỡ và kích lệ về tinh thần của bạn bè đồng nghiệp và gia đình giúp cho em vƣợt qua những khó khăn trong thời gian thực hiện luận văn. Em xin trân thành cảm ơn tới tất cả mọi ngƣời. Hà nội, ngày 20 tháng 05 năm 2015 Học viên Trần Ngọc Đồng LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi, với sự hỗ trợ từ ngƣời hƣớng dẫn khoa học PGS.TS NGÔ QUỐC TẠO Các số liệu, kết quả nêu trong luận văn là trung thực và chƣa từng đƣợc ai công bố trong bất kỳ công trình nào khác. Việc sử dụng những dữ liệu có trong luận văn đƣợc thu thập từ các nguồn thông tin khác nhau có ghi trong phần tài liệu tham khảo. Nếu phát hiện bất kỳ sự gian lận nào, tôi xin chịu trách nhiệm trƣớc Hội đồng, cũng nhƣ kết quả luận văn của mình. Tác giả Trần Ngọc Đồng MỤC LỤC MỞ ĐẦU ......................................................................................................... 1 1. Lý do chọn đề tài ......................................................................................... 1 2. Mục đích nghiên cứu ................................................................................... 2 3. Nhiệm vụ nghiên cứu .................................................................................. 2 4. Đối tƣợng và phạm vi nghiên cứu .............................................................. 2 5. Phƣơng pháp nghiên cứu ............................................................................. 2 6. Bố cục luận văn ........................................................................................... 3 NỘI DUNG ..................................................................................................... 4 CHƢƠNG 1: TỔNG QUAN VỀ TRA CỨU ẢNH ........................................ 4 1.1. Một số vấn đề cơ bản trong hệ thống xử lý ảnh ................................... 4 1.1.1. Xử lý ảnh ....................................................................................... 4 1.1.2. Ảnh và điểm ảnh ............................................................................ 5 1.1.3. Khái niệm ảnh đen trắng và ảnh màu ........................................... 8 1.1.4. Không gian màu ............................................................................ 9 1.2. Giới thiệu kiến trúc chung về hệ thống tra cứu ảnh ........................... 10 1.2.1. Tra cứu thông tin......................................................................... 10 1.2.2. Tra cứu ảnh dựa vào nội dung .................................................... 11 1.3. Hệ thống đề xuất ................................................................................ 15 CHƢƠNG 2: PHƢƠNG PHÁP TRA CỨU ẢNH TỪ TRONG ẢNH TÀI LIỆU ...................................................................................................... 17 2.1. Chuyển từ ảnh màu sang ảnh nhị phân .............................................. 17 2.1.1 Chuyển từ ảnh màu sang ảnh xám ............................................... 17 2.1.2. Chuyển từ ảnh xám sang ảnh nhị phân....................................... 17 2.1.3. Thao tác với ảnh nhị phân .......................................................... 24 2.2. Trích chọn đặc trƣng và đối sánh từ .................................................. 33 2.2.1. Đặc trưng về vùng của đối tượng ............................................... 33 2.2.2. Những đặc trưng của hệ thống đối sánh ..................................... 41 2.3. Thuật toán dùng để đối sánh từ .......................................................... 47 CHƢƠNG 3: XÂY DỰNG CHƢƠNG TRÌNH THỬ NGHIỆM................. 49 3.1. Môi trƣờng phát triển và CSDL ......................................................... 49 3.2. Giao diện chƣơng trình ...................................................................... 49 3.3. Đánh giá hệ thống .............................................................................. 53 KẾT LUẬN ................................................................................................... 55 DANH MỤC TÀI LIỆU THAM KHẢO ...................................................... 56 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT RGB: Red, Green, Blue CMY: Cyan-Magenta-Yellow CBIR: Content Baased Image Retrieval CSDL: Cơ Sở Dữ Liệu DANH MỤC CÁC BẢNG Bảng 1.1: Định nghĩa histogram ..................................................................... ..8 Bảng 2.1: Định nghĩa ảnh nhị phân đƣợc tạo từ ảnh xám .............................. 18 Bảng 2.2: Định nghĩa thành phần liên thông .................................................. 25 Bảng 3.1: Thống kê kết quả tra cứu ............................................................ …53 DANH MỤC HÌNH VẼ Hình 1.1. Quá trình xử lý ảnh ........................................................................... 4 Hình 1.2. Các bƣớc cơ bản trong một hệ thống xử lý ảnh .............................. . 4 Hình 1.3. Hai dạng lƣợc đồ mức sáng............................................................... 7 Hình 1.4: Lƣợc đồ mô tả các bƣớc liên quan trong hệ thống tra cứu ảnh dựa vào nội dung ................................................................................................... 13 Hình 1.5: Cấu trúc chung hệ thống đề xuất tìm từ trong ảnh tài liệu ............. 15 Hình 2.1: Ảnh màu đƣợc chuyển sang ảnh xám tính theo công thức trên ...... 17 Hình 2.2. Ví dụ về histogram và ma trận ánh sáng [3] ................................... 20 Hình 2.3: Biểu đồ histogram cho những giá trị màu nhỏ hơn ........................ 20 Hình 2.4: Biểu đồ histogram cho những giá trị màu lớn hơn ngƣỡng t=3 [3] .....21 Hình 2.5: Tính toán giá trị phƣơng sai bên trong một lớp ứng với tứng giá trị mức xám [3] .................................................................................................. 22 Hình 2.6: Kết quả sau khi sử dụng phƣơng pháp Otsu [3] ............................. 22 Hình 2.7:Ảnh sau khi đƣợc tách ngƣỡng bằngOtsu ........................................ 23 Hình 2.8: Hai định nghĩa về các điểm láng riềng phổ biến ............................ 24 Hình 2.9: Ví dụ về ảnh nhị phân ..................................................................... 26 Hình 2.10: Ảnh nhị phân và nhãn của các thành phần.................................... 26 Hình 2.11:Cấu trúc Union - Find với hai tập nhãn [7] ................................... 27 Hình 2.12: Giả mã cho thủ tục Find ................................................................ 28 Hình 2.13: Giả mã cho thủ tục Union ............................................................. 28 Hình 2.14: Giả mã thuật toán tìm và gán nhãn cho các thành liên thông ....... 30 Hình 2.15 giải thích ứng dụng thuật toán tìm nhãn các thành phần liên thông với cấu trúc Union-Find cho ảnh nhị phân ở hình ......................................... 31 Hình 2.16: Bức ảnh tài liệu có nhiều nhiễu ..................................................... 32 Hình 2.17: Tìm các thành phần liên thông trong ảnh ..................................... 32 Hình 2.18: Loại bỏ nhiễu ................................................................................ 32 Hình 2.19: Mở rộng kích thƣớc hình chữ nhật biên theo hai hƣớng trái và phải 32 Hình 2.20: Xác định từ .................................................................................... 33 Hình 2.21: Các vùng đã đƣợc gán nhãn trong tài liệu ................................... 36 Hình 2.22: Các đặc trƣng của 3 vùng ở hình 2.21 ........................................ 36 Hình 2.23. Tám điểm cực trị của một vùng nằm trên hình chữ nhật biên. Cắt đƣờng chéo đứt đoạn là trục các điểm cực trị ............................ 37 Hình 2.24: Moment của một trục đƣợc tính bằng bình phƣơng khoảng cách từ mỗi điểm đến trục đó [7] ............................................................................... 39 Hình 2.25: Xác định tỉ lệ chiều rộng và cao dựa vào hình chữ nhật biên của vùng trong từ .................................................................................................. 41 Hình 2.26: Ảnh tính toán phép chiếu dọc ..................................................... 43 Hình 2.27: Ảnh biểu diễn thao tác với đặc trƣng ghép chiều trên và dƣới của từ ................................................................................................. 45 Hình 2.28: Ảnh biểu diễn thao tác với đặc trung thông tin về phần bên trên và bên trên và phần bên dƣới của từ .......................................... 46 Hình 2.29: Vector đặc trƣng dùng để đối sánh từ ........................................... 47 Hình 3.1: Giao diện chƣơng trình ................................................................... 49 Hình 3.2: Giao diện chức năng “Thêm ảnh vào CSDL” ................................ 50 Hình 3.3: Cập nhật ảnh vào CSDL thành công ............................................... 51 Hình 3.4: Kết quả tìm kiếm ............................................................................. 52 Hình 3.5: Chi tiết các từ có trong ảnh tài liệu đƣợc bôi đậm .......................... 52 Hình 3.6: Tỉ lệ precision trung bình là 79,6%................................................. 54 Hình 3.7: Tỉ lệ recall trung bình là 96,1% ...................................................... 54 1 MỞ ĐẦU 1. Lý do chọn đề tài Hiện nay, các thành tựu của tin học đƣợc áp dụng ở hầu hết các lĩnh vực hoạt động của xã hội và đem lại nhiều hiệu quả to lớn. Mối quan hệ tƣơng tác giữa các nhu cầu của xã hội ngày càng đa dạng, cùng với sự phát triển của các thiết bị đa phƣơng tiện (multimedia) nhƣ máy ảnh, máy scan, máy quay phim, điện thoại, ipad… với khối lƣợng hình ảnh và phim lƣu trữ ngày càng lớn, cùng với sự phát triển của các thiết bị điện tử, tin học và viễn thông đã thu hút ngày càng nhiều những chuyên gia đi vào nghiên cứu những công cụ cung cấp cho việc lấy thông tin dữ liệu ảnh từ nội dung của chúng. Trong thực tế, bài toán tra cứu ảnh có rất nhiều ứng dụng quan trọng. Các ứng dụng phức tạp nhƣ so sánh mẫu vân tay, tìm kiếm ảnh tội phạm…. đƣợc áp dụng trong ngành khoa học hình sự, cơ sở dữ liệu ảnh về địa lý, y học… làm cho lĩnh vực nghiên cứu này phát triển nhanh trong công nghệ thông tin. Với số lƣợng ảnh đƣợc lƣu trữ trên các thiết bị nhớ trở nên 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. Tùy vào mục đích tìm kiếm khác nhau mà có các hình thức tra cứu ảnh khác nhau. Hệ thống tra cứu ảnh từ trong ảnh tài liệu chỉ là một dạng của hệ thống tra cứu ảnh nói chung. Mục đích của hệ thống tìm kiếm từ trong ảnh tài liệu là đƣa ra những ảnh tài liệu liên quan với từ mà ngƣời dùng cung cấp. Trong luận văn này sẽ trình bày một hệ thống tra cứu ảnh từ trong ảnh tài liệu giúp ngƣời dùng có thể tìm kiếm thông tin từ ảnh tài liệu từ câu truy vấn. Hệ thống đƣa ra việc tìm kiếm trên ngôn ngữ là Tiếng anh. Xuất phát trong hoàn cảnh đó “Nghiên cứu phƣơng pháp tra cứu ảnh từ trong ảnh tài liệu” đƣợc em chọn làm đề tài. 2 2. Mục đích nghiên cứu Mục đích của hệ thống truy tìm từ trong ảnh là đƣa ra những ảnh tài liệu liên quan với từ mà ngƣời dùng cung cấp. Trong đồ án này sẽ trình bày một hệ thống truy tìm ảnh tài liệu giúp ngƣời dùng có thể truy tìm thông tin từ ảnh tài liệu, hoặc ảnh in từ câu truy vấn. Hệ thống đƣa ra việc tìm kiếm trên ngôn ngữ là Tiếng anh. 3. Nhiệm vụ nghiên cứu - Tìm hiểu những khái niệm chung, cơ bản về xử lý ảnh và phƣơng pháp dùng để tra cứu ảnh tài liệu. - Nghiên cứu kiến trúc, những khó khăn, thách thức, và lĩnh vực ứng dụng của hệ thống truy tìm từ trong ảnh tài liệu. - Trình bày các thao tác dùng để nhận dạng các từ trong văn bản của hình ảnh tài liệu và các đặc trƣng chung hay dùng để đối sánh đối tƣợng. - Trình bày phần cài đặt hệ thống. Đánh giá một số từ truy vấn đối với hệ thống. 4. Đối tƣợng và phạm vi nghiên cứu Đối tƣợng, phạm vi nghiên cứu: Tổng quan về ảnh và tra cứu ảnh, phƣơng pháp tra cứu ảnh và chọn ra phƣơng pháp, kỹ thuật tra cứu ảnh cụ thể và các ứng dụng thực tế để tra cứu ảnh. 5. Phƣơng pháp nghiên cứu - Phƣơng pháp đặt vấn đề - Phƣơng pháp phân tích tổng hợp. - Phƣơng pháp so sánh đối chiếu. - Phƣơng pháp thực nghiệm Sử dụng các phƣơng pháp trên để nghiên cứu và tìm hiểu: “Nghiên cứu phương pháp tra cứu ảnh từ trong ảnh tài liệu” 3 6. Bố cục luận văn Luận văn đƣợc chia thành ba phần MỞ ĐẦU NỘI DUNG Chƣơng 1: TỔNG QUAN VỀ TRA CỨU ẢNH Chƣơng này sẽ đƣa ra những khái niệm cơ bản về xử lý ảnh và kiến trúc của hệ thống tra cứu ảnh dựa vào nội dung. Dựa vào kiến trúc chung đó xây dựng hệ thống đề xuất tìm kiếm ảnh từ trong ảnh tài liệu. Chƣơng 2: PHƢƠNG PHÁP TRA CỨU ẢNH TỪ TRONG ẢNH TÀI LIỆU Chƣơng này sẽ đi sâu vào từng phần có trong hệ thống đề xuất đƣợc nêu ra ở Chƣơng 1. Đƣa ra các thuật toán để chuyển đổi sang ảnh nhị phân, thao tác với ảnh nhị phân để nhận dạng đƣợc các từ có trong ảnh tài liệu, đồng thời trích chọn các đặc trƣng để đem ra đối sánh. Chƣơng 3: XÂY DỰNG CHƢƠNG TRÌNH THỬ NGHIỆM Chƣơng này sẽ trình bày các chức năng của chƣơng trình thử nghiệm ứng với mục đích nghiên cứu của luận văn. Đánh giá một số từ truy vấn đối với hệ thống. KẾT LUẬN Nhìn chung, luận văn đã đƣa ra những khái niệm cơ bản về hệ thống tra cứu ảnh từ trong tài liệu với một hệ thống tìm kiếm từ trong ảnh tài liệu cụ thể đã đƣợc đề xuất. Các bƣớc trong hệ thống đƣợc trình bày lần lƣợt ở các chƣơng. Tuy nhiên, do thời gian thực hiện còn hạn hẹp, kiến thức còn hạn chế nên luận văn không tránh khỏi thiếu sót. Rất mong nhận đƣợc sự giúp đỡ của các thầy cô và các bạn quan tâm đến vấn đề này để em có thể hoàn thiện hơn kiến thức của mình. 4 NỘI DUNG CHƢƠNG 1: TỔNG QUAN VỀ TRA CỨU ẢNH 1.1. Một số vấn đề cơ bản trong hệ thống xử lý ảnh 1.1.1. Xử lý ảnh Con ngƣời thu nhận thông tin qua các giác quan, trong đó thị giác đóng vai trò quan trọng nhất. Những năm trở lại đây với sự phát triển của phần cứng máy tính, xử lý ảnh và đồ hoạ đó phát triển một cách mạnh mẽ và có nhiều ứng dụng trong cuộc sống. Xử lý ảnh và đồ hoạ đóng một vai trò quan trọng trong tƣơng tác ngƣời máy. 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 “Tốt hơn” Ảnh Xử lý Ảnh Kết luận Hình 1.1. Quá trình xử lý ảnh Ả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. Sơ đồ tổng quát của một hệ thống xử lý ảnh: Hình 1.2. Các bƣớc cơ bản trong một hệ thống xử lý ảnh 5 Xử lý ảnh là một môn học liên quan đến nhiều lĩnh vực và cần nhiều kiến thức cơ sở khác nhau. Có thể kể đến đầu tiên là xử lý tín hiệu số, môn học hết sức cơ bản cho xử lý tín hiệu chung. Các khái niệm về tính chập, các biến đổi Fouricer, Laplace, các bộ lọc hữu hạn… Tiếp đến là các công cụ tính toán nhƣ Đại số tuyến tính, xác suất thống kê. Các kiến thức cần thiết nhƣ trí tuệ nhân tạo, mạng nơ ron nhân tạo cũng đƣợc đề cập trong quá trình phân tích và nhận dạng ảnh. Các phƣơng pháp xử lý ảnh bắt đầu từ các ứng dụng chính là nâng cao chất lƣợng ảnh và phân tích ảnh. Ứng dụng đầu tiên đƣợc biết đến là nâng cao chất lƣợng ảnh báo đƣợc truyền qua cáp từ London đến NewYork từ những năm 1920. Vấn đề nâng cao chất lƣợng ảnh có liên quan tới phân bố mức sáng và độ phân giải ảnh. Vấn đề này đã đƣợc giải quyết vào những năm 1995. Năm 1964 máy tính đã có khả năng xử lý và nâng cao chất lƣợng ảnh từ mặt trăng và vệ tinh Ranger 7 của Mỹ bao gồm : làm nối đƣờng biên, lƣu ảnh. Từ năm 1964 đến nay, các phƣơng tiện xử lý nâng cao chất lƣợng, nhận dạng ảnh không ngừng phát triển và hoàn thiện hơn. 1.1.2. Ảnh và điểm ảnh Ảnh trong thực thế là một ảnh liên tục về không gian và giá trị độ sáng. Để có thể xử lý bằng máy tính cần thiết phải đƣa về dạng ảnh số. Trong quá trình số hóa, ngƣời ta biến đổi tín hiệu liên tục sang tín hiệu rời rạc thông qua quá trình lấy mẫu (rời rạc hóa không gian) và lƣợng tử hóa thành phần giá trị (rời rạc hóa biên độ giá trị) mà về nguyên tắc mắt thƣờng không phân biệt đƣợc hai điểm kề nhau. Trong quá trình này ngƣời ta sử dụng khái niệm là Picture Element mà ta quen gọi là pixel. Ảnh thƣờng có kích thƣớc vuông và đƣợc mô tả là N N m-bit điểm ảnh, trong đó N là số điểm và m là số các giá trị mức sáng. Việc sử dụng m bit đƣa ra khoảng 2m giá trị mức sáng từ 0 đến 2m – 1. Trong khuôn khổ ảnh hai chiều, mỗi Pixel ứng với cặp tọa độ(x,y). 6 Định nghĩa : Điểm ảnh (pixel) là một phần tử của ảnh số tại tọa độ (x,y) với tọa độ xám hoặc màu nhất định. Kích thƣớc và khoảng cách giữa các điểm ảnh đó đƣợc chọn thích hợp sao cho mắt ngƣời cảm nhận sự liên tục về không gian và mức xám (hoặc màu) của ảnh số gần nhƣ ảnh thật. Mỗi phần tử trong ma trận đƣợc gọi là một phần tử ảnh. * Độ phân giải ảnh Định nghĩa: Độ phân giải (Resolution) của ảnh là mật độ điểm ảnh đƣợc ấn định trên một ảnh số đƣợc hiển thị. Trong quá trình xử lý ảnh việc chọn giá trị phù hợp về kích thƣớc N của ảnh cũng khá phức tạp và quan trọng. Chúng ta chọn N đủ lớn sẽ giải quyết những mức độ yêu cầu về độ chi tiết của bức ảnh. Nhƣng N quá nhỏ , ảnh có chất lƣợng xấu: những đƣờng nét sẽ xuất hiện nhƣ những khối và nhiều chi tiết bị mất. Những giá trị lớn hơn của N đƣa ra nhiều chi tiết hơn, nhƣng cần nhiều không gian bộ nhớ hơn để lƣu trữ ảnh, và ảnh sẽ đƣợc xử lý lâu hơn do có nhiều điểm ảnh. * Mức xám của ảnh Một điểm ảnh (pixel) có hai đặc trƣng cơ bản là vị trí (x,y) của điểm ảnh và độ xám của nó. Định nghĩa : Mức xám của ảnh là cƣờng độ sáng của nó đƣợc gán bằng giá trị tại điểm đó. Các thang giá trị mức xám thông thƣờng : 16,32,64,128,256 (Mức 256 là mức phổ dụng). Ảnh đen trắng : là ảnh có hai màu đen và trắng (không chứa màu sắc khác) với mức xám ở các điểm ảnh có thể khác nhau. Ảnh nhị phân : ảnh chỉ có 2 mức đen trắng phân biệt, tức là dùng 1 bit mô tả 21 mức khác nhau. Tức là mỗi điểm ảnh của ảnh nhị phân chỉ có thể là 0 hoặc 1. 7 Ảnh màu: Trong khuôn khổ lý thuyết ba màu (Red, Blue, Green) để tạo nên thế giới màu, ngƣời ta thƣờng dung 3 byte để mô tả mức màu, khi đó các giá trị màu: 28*3 = 224 = 16,7 triệu màu. * Histogram Histogram là một lƣợc đồ biểu diễn độ sáng của một bức ảnh. Lƣợc đồ này bao gồm trục hoảnh biểu diễn mức sáng và trục tung biểu diễn số lƣợng điểm sáng tƣơng ứng. Đối với ảnh xám thông thƣờng, giá trị của trục hoành nằm trong khoảng từ 0-255. Hình 1.3: Hai dạng lƣợc đồ mức xám Hình bên tay trái là histogram cho ảnh màu xám, hình bên tay phải là histogram cho ảnh màu. Nhìn vào biểu đồ ta có thể biết đƣợc phân bố cƣờng độ sáng của một ảnh, với những ảnh mà phân bố histogram lệch về bên phải thì ảnh đó là một ảnh có độ sáng tốt. Ngƣợc lại ảnh đó là một ảnh tối. Dựa vào các yếu tố trên ta có định nghĩa histogram của ảnh xám 8 Định nghĩa : Cho ảnh mức xám I có giá trị màu nằm trong khoảng MIN và MAX Histogram của ảnh mức xám I là số điểm ảnh trong ảnh I có giá trị m. Trong đó : m là tất cả giá trị mức xám của ảnh và m r , c là chỉ số hàng và cột của điểm ảnh trong ảnh Bảng 1.1: Định nghĩa histogram 1.1.3. Khái niệm ảnh đen trắng và ảnh màu Ảnh có thể biểu diễn dƣới dạng tƣơng tự hoặc tín hiệu số. Trong biểu diễn số của các ảnh đa mức xám thì một ảnh đƣợc biểu diễn dƣới dạng một ma trận hai chiều. Mỗi phần tử của ma trận biểu diễn cho mức xám hay cƣờng độ của ảnh tại vị trí đó. Một lƣới chia ô vuông đƣợc đặt lên ảnh. Độ lớn mỗi ô vuông của lƣới xác định kích thƣớc của một điểm ảnh. Mức xám của một điểm đƣợc tính bằng cƣờng độ xám trung bình tại mỗi ô vuông này. Mắt lƣới càng nhỏ thì chất lƣợng ảnh càng cao. Trong kỹ thuật tƣơng tự, một bức ảnh thƣờng đƣợc biểu diễn dƣới dạng các dòng nằm ngang kế tiếp nhau. Mỗi dòng là một tín hiệu tƣơng tự mang theo các thông tin về cƣờng độ sáng dọc theo một đƣờng nằm ngang trong ảnh gốc. * Ảnh đen trắng Ảnh đen trắng chỉ bao gồm hai màu : màu đen và màu trắng. Ngƣời ta phân mức đen trắng đó thành L mức nếu sử dụng số bit B = 8 bit để mã hóa mức đen trắng (hay mức xám) thì L đƣợc xác định : L=2B 9 Nếu L=2, B=1, nghĩa là chỉ có 2 mức: mức 0 và mức 1, còn gọi là ảnh nhị phân. Mức 1 ứng với màu sáng, còn mức 0 ứng với màu tối. Nếu L lớn hơn 2 ta có ảnh đa cấp xám. Với ảnh nhị phân mỗi điểm ảnh đƣợc mã hóa trên 1bit, còn với ảnh 256 mức, mỗi điểm ảnh đƣợc mã hóa trên 8 bit. Nhƣ vậy, với ảnh đen trắng: nếu dùng 8 bit (1 byte) để biểu diễn mức xám thì số mức xám có thể biểu diễn sẽ là 256. Mỗi mức xám đƣợc biểu diễn dƣới dạng số nguyên nằm trong khoảng từ 0-255, với mức 0 biểu diễn cho mức cƣờng độ đen nhất và mức 255 biểu diễn cho mức cƣờng độ sáng nhất. Ảnh nhị phân khá đơn giản, các phần tử ảnh có thể coi là các phần tử logic. Ứng dụng chính của nó đƣợc dùng để phân biệt đối tƣợng ảnh với nền hay để phân biệt điểm biên với các điểm khác. * Ảnh màu Theo lý thuyết của Thomas thì ảnh màu là ảnh tổ hợp từ 3 màu cơ bản là Red, Green, Blue và thu nhận trên các dải bang tần khác nhau. Với ảnh màu thì cách biểu diễn cũng tƣơng tự nhƣ ảnh đen trắng, chỉ khác là các số tại mỗi phần tử của ma trận biểu diễn cho ba màu riêng rẽ. Để biểu diễn cho một điểm ảnh màu cần 24 bit. 24 bit này đƣợc chia thành ba khoảng 8 bit. Mỗi màu cũng phân thành L cấp màu khác nhau (thƣờng L = 256). Mỗi khoảng này biểu diễn cho cƣờng độ sáng của một trong các màu chính. Do đó, để lƣu trữ ảnh màu ngƣời ta có thể lƣu trữ từng màu riêng biệt, mỗi màu lƣu trữ một ảnh đa cấp xám. Chính vì vậy không gian nhớ dành cho một ảnh màu lớn gấp 3 lần một ảnh đa cấp xám cùng kích cỡ. 1.1.4. Không gian màu * Không gian màu RGB 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) 10 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. * Không gian màu CMY CMY là viết tắt của Cyan-Magenta-Yellow (màu lục lam ,màu đỏ tƣơi, màu vàng),đó là ba màu chính tƣơng ứng với ba màu mựcin. * Không gian màu HSx Các không gian màu HSI, HSV, HSB và HSL (quy ƣớc gọi là HSx) là gần với nhận thức của ngƣời hơn không gian màu RGB, nhƣng vẫn không là đồng nhất nhận thức. Các trục từ các không gian màu HSx biểu diễn các đặc trƣng màu (hue), độ bão hòa (saturation), và độ sáng (lightness)(cũng đƣợc gọi là value, brightness và intensity). Sự khác biệt giữa các không gian màu trong HSx là cách chúng biến đổi từ không gian màu RGB. Chúng thƣờng đƣợc biểu diễn bởi các hình thức khác nhau (ví dụ nhƣ hình nón, hình trụ). 1.2. Giới thiệu kiến trúc chung về hệ thống tra cứu ảnh 1.2.1. Tra cứu thông tin Tra cứu thông tin về ảnh là quá trình tìm kiếm trong một cơ sở dữ liệu ảnh những ảnh thỏa mãn một yêu cầu nào đó. Tra cứu thông tin về ảnh thƣờng dựa vào hai đặc trƣng chính là văn bản mô tả đi kèm ảnh hoặc nội dung ảnh. Một số công cụ tìm kiếm ảnh theo văn bản mô tả đi kèm nhƣ Google Image Search, Yahoo, MSN,…Một số công cụ tìm kiếm ảnh dựa vào nội dung ảnh nhƣ Google Image Swirl, Bing,… 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 11 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à phƣơng pháp tra cứu ảnh theo từ khóa. Do vậy 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 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, 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 bởi hoàn cảnh và không đầy đủ. Phƣơng pháp tra cứu ảnh dựa theo nội dung ra đời đã khắc phục đƣợc nhƣợc điểm của phƣơng pháp tra cứu ảnh dựa vào văn bản đi kèm. Phƣơng pháp "Tra cứu ảnh dựa theo nội dung" (Content Based Image Retrieval) cho phép trích chọn các đặc trƣng 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. Một số hệ thống tra cứu ảnh nổi tiếng nhƣ QBIC (IBM), Virage (Virage Inc.) Photobook (MIT) Visual SEEK (Columbia University) đã áp dụng thành công kỹ thuật này. Tra cứu ảnh dựa theo nội dung đã nhận đƣợc nhiều sự quan tâm của các nhà khoa học. 1.2.2. Tra cứu ảnh dựa vào nội dung 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. Nhận thức chủ