Tài liệu Nghiên cứu trích chọn đặc trưng ứng dụng cho tìm kiếm từ trong ảnh tài liệu

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG LÊ XUÂN LONG NGHIÊN CỨU TRÍCH CHỌN ĐẶC TRƯNG ỨNG DỤNG CHO TÌM KIẾM TỪ TRONG ẢNH TÀI LIỆU LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - 2017 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG LÊ XUÂN LONG NGHIÊN CỨU TRÍCH CHỌN ĐẶC TRƯNG ỨNG DỤNG CHO TÌM KIẾM TỪ TRONG ẢNH TÀI LIỆU Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: PGS.TS Ngô Quốc Tạo THÁI NGUYÊN - 2017 i 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.TS Ngô Quốc Tạo, là người trực tiếp hướng dẫn, 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. Em xin trân thành cảm ơn tới tất cả các thầygiáo, cô giáo và Ban lãnh đạo trường Đại học Công nghệ Thông tin và Truyền thông Thái Nguyên đã đ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. Cám ơn đề tài Phòng thí nghiệm trọng điểm: " Nghiên cứu phương pháp tra cứu ảnh dựa vào đa truy vấn" mã số PTNTĐ17.04 đã 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ọc viên Lê Xuân Long ii 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. 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. Thái Nguyên, tháng 12 năm 2017 Người cam đoan Lê Xuân Long iii MỤC LỤC LỜI CẢM ƠN ............................................................................................................ i LỜI CAM ĐOAN ..................................................................................................... ii MỤC LỤC ................................................................................................................ iii DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT........................................ vi DANH MỤC HÌNH VẼ ......................................................................................... vii MỞ ĐẦU ....................................................................................................................1 1. Lý do chọn đề tài .....................................................................................................1 2. Đối tượng và phạm vi nghiên cứu ...........................................................................1 3. Hướng nghiên cứu của đề tài ..................................................................................2 4. Ý nghĩa khoa học và thực tiễn của đề tài ................................................................2 5. Phương pháp nghiên cứu .........................................................................................2 CHƯƠNG 1: TỔNG QUAN VỀ TRA CỨU ẢNH TÀI LIỆU ..............................4 1.1. Tổng quan về tra cứu ảnh tài liệu .........................................................................4 1.1.1. Truy vấn người sử dụng ............................................................................6 1.1.2. Trích chọn đặc trưng ảnh ..........................................................................6 1.1.3. Đánh chỉ số nhiều chiều ............................................................................8 1.2. Một số khái niệm cơ bản trong xử lý ảnh ............................................................9 1.2.1. Ảnh đen trắng và ảnh màu ......................................................................13 1.2.2. Không gian màu ......................................................................................14 1.2.3. Phân tích ảnh ...........................................................................................16 1.2.4.Tra cứu ảnh ..............................................................................................17 1.2.5. Nhận dạng ảnh.........................................................................................18 1.3. Tra cứu thông tin ................................................................................................18 1.4. Những thách thức trong thiết kế và thực thi hệ thống tìm kiếm ảnh tài liệu .....19 1.4.1.Tốc độ tính toán .......................................................................................19 1.4.2.Các tài liệu kém chất lượng......................................................................19 1.4.3.Ngôn ngữ trong tài liệu ............................................................................19 iv 1.5. Hệ thống đề xuất ................................................................................................19 CHƯƠNG 2: MỘT SỐ VẤN ĐỀ VỀ TÌM KIẾM TỪ TRONG ẢNH TÀI LIỆU VÀ PHƯƠNG PHÁP TRÍCH CHỌN ĐẶC TRƯNG ..........................................22 2.1.Tiền xử lý ảnh .....................................................................................................22 2.1.1.Nhiễu ảnh và lọc nhiễu .............................................................................22 2.1.2.Chuẩn hóa kích thước ảnh ........................................................................23 2.1.3.Làm trơn biên chữ ....................................................................................24 2.1.4.Làm đầy chữ .............................................................................................24 2.1.5.Làm mảnh chữ ..........................................................................................24 2.1.6.Điều chỉnh độ nghiêng của văn bản .........................................................25 2.2.Các phương pháp trích chọn đặc trưng cơ bản cho ảnh tài liệu ..........................25 2.3.Trích chọn đặc trưng ứng dụng cho tìm kiếm từ trong ảnh tài liệu ....................29 2.3.1.Chuyển ảnh xám .......................................................................................29 2.3.2. Ảnh nhị phân, nhị phân hóa với ngưỡng động ........................................30 2.3.3.Một số thao tác trên ảnh nhị phân ............................................................34 2.3.3.1. Các lân cận của điểm ảnh( Image Neighbors) .....................................34 2.3.3.2.Gán nhãn các thành phần liên thông (CCL-Connected Components Labeling ) ..........................................................................................................35 2.3.3.3.Phân đoạn từ trong ảnh tài liệu .............................................................41 2.3.3.4. Đặc trưng về vùng của đối tượng .........................................................43 2.3.3.5. Hình chữ nhật bao và các điểm cực trị .................................................47 2.3.3.6. Moment không gian .............................................................................48 2.3.3.7. Phép chiếu ............................................................................................50 2.4. Đối sánh những đặc trưng trong hệ thống đề xuất .............................................51 2.4.1. Tỉ lệ về chiều cao và chiều rộng (Width to Height Ratio) ......................51 2.4.2. Mật độ vùng của từ (Word Area Density) ..............................................51 2.4.3. Điểm trọng tâm của từ ( Center of Gravity )...........................................51 2.4.4. Phép chiếu dọc (Vertical Projection) ......................................................52 2.4.5. Phép chiếu hình dạng trên và dưới (Top – Bottom Shape Projections) ..55 v 2.4.6. Những đặc trưng phần bên trên và bên dưới của từ (Upper - Down Grid Features ) ...........................................................................................................56 2.5. Thực hiện công việc đối sánh trong hệ thống đề xuất ...............................58 CHƯƠNG 3: ............................................................................................................61 CHƯƠNG TRÌNH THỬ NGHIỆM TÌM KIẾM TỪ TRONG ẢNH TÀI LIỆU TRÊN CƠ SỞ LÝ THUYẾT ĐÃ XÂY DỰNG ....................................................61 3.1.Môi trường cài đặt ...............................................................................................61 3.2. Hệ thống mô tả chương trình thử nghiệm ..........................................................61 3.3. Giao diện chính của chương trình tìm kiếm từ trong ảnh tài liệu ......................63 3.4. Một số kết quả ....................................................................................................66 3.5. Đánh giá .............................................................................................................67 DANH MỤC TÀI LIỆU THAM KHẢO ...............................................................70 vi 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 vii DANH MỤC HÌNH VẼ Hình 1.1 Lược đồ mô tả hệ thống tra cứu ảnh dựa vào nội dung .....................................5 Hình 1.2 Các giai đoạn cơ bản trong xử lý ảnh [2] ...................................................10 Hình 1.3 Hình người đi bộ với các kích thước ảnh khác nhau .................................12 Hình 1.4 Không gian màu RGB ................................................................................15 Hình 1.5 Không gian màu HSV được trực quan hóa như một hình nón ..................16 Hình 1.6 Cấu trúc chung hệ thống đề xuất tìm từ trong ảnh tài liệu ........................20 Hình 2.1 Nhiễu đốm và nhiễu vệt .............................................................................23 Hình 2.2 Chuẩn hóa kích thước ảnh các ký tự “A” và “P” .......................................24 Hình 2.3 Làm mảnh chữ ............................................................................................24 Hình 2.4 Hiệu chỉnh độ nghiêng của văn bản ..........................................................25 Hình 2.5 Ảnh màu được chuyển sang ảnh xám tính theo công thức trên ................29 Hình 2.6 Biểu đồ mức xám của ảnh .........................................................................31 Hình 2.7 Ví dụ về Histogram và ma trận ảnh xám [3] .............................................32 Hình 2.8 biểu đồ histogram và công thức tính cho những giá trị màu nhỏ hơn hoặc bằng ngưỡng t=3 [3] ..................................................................................................32 Hình 2.9 Biểu đồ histogram và công thức tính cho những giá trị màu lớn hơn hoặc bằng ngưỡng t=3 [3] ..................................................................................................32 Hình 2.10 Tính toán giá trị phương sai trong một lớp ứng với từng giá trị mức xám [3] ...................................................................................................................................33 Hình 2.11 Kết quả thu được sau khi sử dụng phương pháp Otsu [3] ......................33 Hình 2.12 ảnh xám của từ chứa nhiều nhiễu (được khoanh đỏ trong hình trên) ......33 Hình 2.13 Ảnh đã được bỏ nhiễu và chuyển sang ảnh nhị phân nhờ phương pháp Otsu 34 Hình 2.14 Lân cận các điểm ảnh của tọa độ (x, y) ....................................................35 Hình 2.15 Các khả năng liên thông được sử dụng ....................................................35 viii Hình 2.16 Ảnh nhị phân và gán nhãn cho các thành phần liên kết ..........................36 Hình 2.17 Nhị phân và ma trận nhãn của điểm ảnh nổi (Foreground pixel ) được khởi tạo tăng dần .......................................................................................................37 Hình 2.18 Cấu trúc Union-Find thể hiện qua mảng PARENT .................................37 Hình 2.19 Áp dụng Find cho toàn bộ nốt ta có PARENT .......................................38 Hình 2.20 Ứng dụng thuật toán gán nhãn cho các thành phần liên thông ...............41 Hình 2.21 Ảnh tài liệu có nhiều nhiễu ......................................................................42 Hình 2.22 Tìm các thành phần liên thông trong ảnh tài liệu ....................................42 Hình 2.23 Loại bỏ nhiễu............................................................................................42 Hình 2.24 Mở rộng kích thước hình chữ nhật bao theo hai hướng trái và phải ........43 Hình 2.25 Xác định từ ...............................................................................................43 Hình 2.26 Các vùng đã được gán nhãn trong ảnh tài liệu .........................................46 Hình 2.27 Các đặc trưng của 3 vùng ở hình 2.26......................................................46 Hình 2.28 Tám điểm cực trị của một vùng nằm trên Hình chữ nhật bao. Các đường chéo đứt đoạn là trục các điểm cực trị ......................................................................47 Hình 2.29 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 đó ........................................................................................................49 Hình 2.30 Ảnh nhị phân của con thằn lằn với phép chiếu ngang và dọc .................50 Hình 2.31 Xác định tỉ lệ chiều rộng và cao dựa vào hình chữ nhật bao của vùng trong từ ......................................................................................................................51 Hình 2.32 Ảnh tính toán phép chiếu dọc : (a) là ảnh gốc; (b) là phép chiếu dọc; (c) là phép chiếu đã được làm trơn và sử dụng ma trận mặt nạ 5×1. .............................53 Hình 2.33 Ảnh bàn cờ lý tưởng và ảnh bàn cờ có nhiễu. Sau đó ảnh được khử nhiễu bằng cách làm trơn ảnh sử dụng ma trận mặt nạ 5x5 ................................................54 Hình 2.34 Ảnh biểu diễn thao tác với đặc trưng phép chiếu trên và dưới của từ ....56 ix Hình 2.35 Ảnh biểu diễn thao tác với đặc trưng thông tin về phần bên trên và phần bên dưới của từ ..........................................................................................................57 Hình 2.36 Mô hình 93 thành phần theo thứ tự cấu trúc ............................................58 Hình 2.37 Thủ tục đối sánh từ ..................................................................................59 Hình 3.2 và hình 3.3 giao diện chức năng thêm ảnh vào CSDL ...............................63 Hình 3.4 giao diện khi thêm ảnh vào CSDL thành công ..........................................64 Hình 3.5 kết quả tìm kiếm từ ....................................................................................65 Hình 3.6 từ cần tìm kiếm có trong ảnh tài liệu được bôi màu vàng ..........................65 Bảng 3.1 kết quả tìm kiếm từ ....................................................................................66 Bảng 3.2 ba mươi từ ngẫu nhiên được dùng trong đánh giá .....................................67 Bảng 3.3 Giá trị độ chính xác và khả năng thu hồi của ba mươi từ ngẫu nhiên được dùng trong đánh giá ...................................................................................................67 Hình 3.7 sự thay đổi độ chính xác và thu hồi cho các tìm kiếm . Độ chính xác là 87.8% và khả năng thu hồi là 99.26%KẾT LUẬN ...................................................68 KẾT LUẬN ...............................................................................................................69 1 MỞ ĐẦU 1. Lý do chọn đề tài Ngày này chúng ta đang sống trong thế giới bùng nổ về các công nghệ hiện đại. Các thiết bị số ngày càng phổ biến, các thiết bị như máy ảnh số, máy quay phim, di động (có chức năng camera).... có thể giúp chúng ta dễ dàng lưu trữ thông tin dưới dạng ảnh hoặc video. Tuy nhiên, với số lượng các ảnh quá nhiều, việc tìm kiếm thông tin trở nên khó khăn và mất rất nhiều thời gian. Để giúp con người tìm kiếm thông tin dễ dàng hơn trong ảnh, hệ thống tìm kiếm nội dung trong ảnh đã được ra đời. Mục đích của hệ thống là tìm những bức ảnh liên quan từ những thông tin, mà được cung cấp bởi người dùng. Thông thường trong hệ thống tìm kiếm ảnh, những nội dung có thể nhìn thấy như màu sắc, hình dạng, kết cấu, bố cục không gian thường được chọn lọc, đánh chỉ số và biểu diễn dưới dạng vector đặc trưng nhiều chiều. Những đặc trưng này sẽ được sử dụng để đối sánh và tìm những bức ảnh khác có liên quan. Tùy vào mục đích tìm kiếm khác nhau mà có các hình thức tìm kiếm ảnh khác nhau. Hệ thống tìm từ trong ảnh tài liệu chỉ là một dạng của hệ thống tìm kiếm ả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 số phương pháp trích chọn đặc trưng và ứng dụng cho tìm kiếm từ trong ả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. Với những lý do trên đây nên học viên đã mạnh dạn nhận đề tài: “Nghiên cứu trích chọn đặc trưng ứng dụng cho tìm kiếm từ trong ảnh tài liệu”. 2. Đối tượng và phạm vi nghiên cứu Hiểu được các phương pháp trích chọn đặc trưng cho tìm kiếm từ trong ảnh tài liệu. Từ đó đưa ra những nhận xét, so sánh giữa các phương pháp. Lựa chọn công cụ phát triển phù hợp cài đặt ứng dụng. 2 3. Hướng nghiên cứu của đề tài Tìm hiểu một vài phương pháp trích chọn đặc trưng cho tìm kiếm từ trong ảnh tài liệu về mặt lý thuyết, từ đó lựa chọn phương pháp cài đặt ứng dụng vào thực tế. Áp dụng đối với ảnh tài liệu. 4. Ý nghĩa khoa học và thực tiễn của đề tài Hệ thống hoá các kiến thức về xử lý ảnh và phương pháp trích chọn đặc trưng cho tìm kiếm từ trong ảnh tài liệu . Việc tìm hiểu và phát triển ứng dụng thành công giúp cho việc tìm kiếm ảnh tài liệu trở nên đơn giản và dễ dàng hơn. 5. Phương pháp nghiên cứu - Phương pháp nghiên cứu lý thuyết: Tìm hiểu tài liệu, đọc hiểu các kiến thức cơ bản đến xử lý ảnh và trích chọn đặc trưng, đề xuất các phương pháp cài đặt trên ngôn ngữ lập trình. - Phương pháp nghiên cứu thực nghiệm: Cài đặt thử nghiệm chương trình tìm kiếm từ trong ảnh tài liệu. - Phương pháp trao đổi khoa học: Trao đổi hướng nghiên cứu với người hướng dẫn, các đồng nghiệp để đề xuất và giải quyết các nội dung luận văn đề ra. Luận văn gồm có 3 chương và phần kết luận: Chương 1: TỔNG QUAN VỀ TRA CỨU ẢNH TÀI LIỆU Chương này sẽ đưa ra những khái niệm chung, cơ bản nhất về xử lý ảnh và phương pháp sử dụng để tra cứu ảnh. Mục đích là đưa cho người đọc những hiểu biết chung về xử lý ảnh và những khó khăn, thách thức trong ứng dụng của chương trình tìm kiếm từ trong ảnh tài liệu. Chương 2: MỘT SỐ VẤN ĐỀ VỀ TÌM KIẾM TỪ TRONG ẢNH TÀI LIỆU VÀ PHƯƠNG PHÁP TRÍCH CHỌN ĐẶC TRƯNG Chương này chủ yế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à tìm hiểu hiểu được các trích chọn đặc trưng chung hay dùng để đối sánh đối tượng. 3 Chương 3: CHƯƠNG TRÌNH THỬ NGHIỆM TÌM KIẾM TỪ TRONG ẢNH TÀI LIỆU TRÊN CƠ SỞ LÝ THUYẾT ĐÃ XÂY DỰNG Chương này sẽ trình bày phần cài đặt chương trình. Đánh giá một số từ truy vấn đối với chương trình. KẾT LUẬN Phần cuối cùng là kết luận tóm tắt các vấn đề đã nghiên cứu và hướng phát triển tiếp theo. Luận văn đã đưa ra các khái niệm chung và cơ bản về xử lý ảnh và phương pháp sử dụng để tra cứu ảnh, một số phương pháp nghiên cứu trích chọn đặc trưng của ảnh, ứng dụng với một chương trình tìm kiếm từ trong ảnh tài liệu cụ thể đã được đề xuất. Được trình bày lần lượt ở các chương. Do thời gian thực hiện có hạn, 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 để học viên có thể hoàn thiện hơn kiến thức của mình. 4 CHƯƠNG 1: TỔNG QUAN VỀ TRA CỨU ẢNH TÀI LIỆU 1.1. Tổng quan về tra cứu ảnh tài liệu Trong những năm gần đây, sự gia tăng nhanh chóng về mặt số lượng các tài liệu đa phương tiện đặc biệt là dữ liệu ảnh. Những dữ liệu dạng này tăng nhanh do việc tạo ra chúng dễ dàng nhờ sử dụng máy quét (Scanner) và máy ảnh kỹ thuật số (Digital camera). Do đó, các văn bản có thể được chụp hoặc quét và được lưu dưới dạng ảnh tài liệu (Document image). Nhưng những thông tin này không được đánh chỉ số cho nên việc tìm kiếm thông tin trở nên khó khăn. Việc tìm kiếm thông tin trong ảnh tài liệu là một lĩnh vực nghiên cứu hấp dẫn với sự phát triển ngày càng tăng nhanh. Những tài liệu dạng này đóng một vai trò quan trọng trong cuộc sống hằng ngày của chúng ta. Những tài liệu phức tạp hơn đưa ra những thử thách lớn hơn cho lĩnh vực nhận dạng và tìm kiếm ảnh tài liệu. Sự hiện diện của các loại nhiễu, chữ viết tay, chữ ký, logo, chữ in trong cùng một tài liệu với các loại font khác nhau cũng như việc quy định viết chữ theo dòng đã gây nhiều hạn chế đến các thuật toán mà đơn thuần làm việc trên những bức ảnh tài liệu đơn giản. Công việc chính của quá trình xử lý ảnh tài liệu phức tạp là tách biệt những nội dung khác nhau có trong ảnh tài liệu. Một khi những nội dung đã được phân tách, thì chúng có thể được đánh chỉ số để sẵn dùng bởi hệ thống tìm kiếm ảnh. Sự hiểu biết nội dung của ảnh tài liệu như là tài liệu về kiểm tra tài khoản ngân hàng, thư trong doanh nghiệp, các mẫu điền thông tin, và các bài báo kĩ thuật đã dần trở thành những lĩnh vực nghiên cứu hấp dẫn. Trong chương này sẽ đưa ra kiến thức chung nhất về hệ thống tra cứu ảnh tài liệu và một số vấn đề liên quan đến xử lý ảnh. Các thách thức đặt ra với hệ thống tìm kiếm ảnh nói chung và hệ thống các đề xuất. 5 Hình 1.1 Lược đồ mô tả hệ thống tra cứu ảnh dựa vào nội dung Chúng ta thấy rằng trên 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à có các truy vấn người sử dụng. Chúng đượ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 trên. Sau đây chúng ta sẽ đưa ra cái nhìn khái quát về một số tác vụ chính của một hệ thống tra cứu ảnh bao gồm các nội dung sau: Phân tích nội dung của các nguồn thông tin và biểu diễn các nội dung được phân tích theo cách thích hợp cho so sánh các truy vấn sử dụng. Bước này thường cần nhiều thời gian nhất vì nó phải xử lý lần lượt các ảnh đưa vào cơ sở dữ liệu và được thực hiện một lần. Phân tích các truy vấn người sử dụng và biểu diễn ở dạng thích hợp cho so sánh với cơ sở dữ liệu nguồn, chỉ áp dụng với ảnh truy vấn. So sánh các truy vấn tìm kiếm thông tin trong cơ sở dữ liệu nguồn, tra cứu thông tin liên quan theo cách hiệu quả nhất. Được thực hiện trực tiếp và 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ốc độ đối sánh được nhanh hơn. Điều chỉnh cần thiết ở hệ thống dựa vào phản hồi từ người sử dụng hoặc các ảnh được tra cứu. 6 1.1.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à 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. Các phương pháp truy vấn dưới đây được sử dụng phổ biến trong nghiên cứu tra cứu ảnh dựa vào nội dung. Truy vấn bởi ảnh mẫu (QBE - Query By Example): trong loại truy vấn này, người sử dụng hệ thống chỉ rõ một ảnh truy vấn cần tìm , dựa trên ảnh đó hệ thống sẽ tìm kiếm trong cơ sở dự liệu ảnh các ảnh tương tự nhất. Ưu điểm của hệ thống này là một cách tự nhiên cho những người sử dụng chung và tra cứu trong cơ sở dữ liệu. Truy vấn bởi đặc trưng (QBF – Query By Feature): trong hệ thống QBF tiêu biểu, những người sử dụng các truy vấn bằng việc chỉ rõ các đặc trưng họ quan tâm cho tìm kiếm. Truy vấn này được chỉ rõ bằng việc sử dụng các công cụ giao diện đồ họa chuyên dụng. Những người sử dụng hệ thống tra cứu ảnh chuyên nghiệp thì có thể thấy loại truy vấn này là bình thường còn người sử dụng chung thì không thể. Các truy vấn dựa vào thuộc tính ( Attribute – Based queries): Các truy vấn dựa vào thuộc tính sử dụng các chú thích văn bản, trích rút trước bởi nỗ lực con người, như một khóa tra cứu chính. Phương pháp này nhanh và dễ thực hiện, nhưng chủ quan và nhập nhằng cao xuất hiện như đã đề cập. 1.1.2. Trích chọn đặc trưng ảnh Trích chọn đặc trưng liên quan đến việc trích chọn những thông tin hữu ích từ ảnh. Vì vậy nó giảm yêu cầu về bộ nhớ cấn thiết và do đó làm hệ thống trở nên nhanh hơn và tìm kiếm ảnh hiệu quả hơn. Mỗi khi một hoặc nhiều đặc trưng được trích chọn, chúng là được lưu trữ trong cơ sở dữ liệu để sử dụng cho công việc sau này. Số lượng thông tin hữu ích mà một máy tính lấy ra từ ảnh là yếu tố rất quan trọng quyết định tính thông minh, cũng như hiệu quả của hệ thống tìm kiếm ảnh. Một ưu điểm lớn nhất của việc trích chọn đặc trưng đó là nó bỏ đi những thông tin không cần thiết và chỉ giữ lại những thông tin cần thiết để có thể biểu diễn nội dung cho ảnh. 7 a)Trích chọn đặc trưng theo mầu sắc tổng thể và cục bộ Tra cứu ảnh dựa trên màu sắc hầu hết là biến đổi dựa trên ý tưởng giống nhau của các biểu đồ màu. Mỗi ảnh khi đưa vào tập hợp ảnh đều được phân tích, tính toán một biểu đồ màu. Sau đó, biểu đồ màu của mỗi ảnh sẽ được lưu trữ trong cơ sở dữ liệu. Khi tìm kiếm, người sử dụng có thể xác định tỷ lệ của mỗi màu mong muốn (ví dụ 75% Blue, 25% Red) hoặc đưa ra một ảnh mẫu với biểu đồ màu đã được tính toán. Quá trình tra cứu sẽ đối sánh biểu đồ màu này với biểu đồ màu trong cơ sở dữ liệu để tìm ra kết quả tương tự nhất. Kỹ thuật đối sánh được sử dụng phổ biến nhất là biểu đồ màu giao nhau được phát triển đầu tiên bởi Swain. Những kỹ thuật cải tiến từ kỹ thuật này ngày nay được sử dụng rộng rãi trong các hệ thống ra cứu ảnh hiện thời. Kết quả của các hệ thống này đã tạo những ấn tượng khá sâu sắc. b)Trích chọn đặc trưng theo kết cấu Kết cấu (texture) là một tính chất quan trọng khác của ảnh. Kết cấu là một thành phần có ảnh hưởng rất quan trọng đối với sự nhận thức trực quan của con người. Tất cả mọi người đều có thể nhận ra kết cấu nhưng lại rất khó có thể định nghĩa chính xác nó là gì. Không giống như màu sắc, kết cấu “xảy ra” trên một vùng chứ không phải tại một điểm ảnh và thường được định nghĩa bằng các mức xám. Rất nhiều cách thể hiện kết cấu đã được nghiên cứu trong lĩnh vực nhận dạng và thị giác máy tính. Xét một cách cơ bản, các phương pháp biểu diễn kết cấu có thể được chia thành hai loại: Phương pháp cấu trúc và phương pháp thống kê. * Các phương pháp cấu trúc bao gồm: các toán tử hình thái và đồ thị liền kề, mô tả kết cấu bằng cách định nghĩa các nguyên thuỷ cấu trúc và luật sắp đặt của chúng. Các phương pháp này tỏ ra có hiệu quả khi áp dụng trong trường hợp kết cấu thông thường. * Các phương pháp thống kê bao gồm: Phương pháp phổ năng lượng Fourier, ma trận đồng khả năng, Tamura, Phân tích Wold, trường ngẫu nhiên Markov, mô hình fractal, các bộ lọc đa phân giải như biến đổi Gabor và biến đổi dạng sóng... thể hiện kết cấu bằng sự phân bố thống kê của độ sáng của các điểm ảnh. 8 c)Trích chọn đặc trưng theo hình dạng Các đặc điểm phát hiện biên của các vùng ảnh và các đối tượng ảnh được sử dụng trong rất nhiều hệ thống tra cứu ảnh. So với các đặc điểm về màu sắc và các đặc điểm về kết cấu thì các đặc điểm về hình dạng thường chỉ được sử dụng sau khi ảnh đã phân thành các vùng hoặc các đối tượng ảnh. Nhưng do việc phân vùng và tách đối tượng ảnh khó thu được kết quả tốt nên việc sử dụng các đặc điểm hình dạng để tra cứu ảnh thường bị bó hẹp trong một số ứng dụng mà ở đó các vùng ảnh hoặc đối tượng ảnh đã được tách biệt rõ ràng. Các phương pháp trích chọn đặc điểm hình dạng thường được chia thành hai loại là trích chọn dựa theo đường biên (xấp xỉ đa giác, mô hình phần tử hữu hạn, mô tả hình dạng theo Fourier) và trích chọn dựa theo vùng ảnh (mô hình thống kê). Một phương pháp trích chọn đặc điểm hình dạng tốt phải đảm bảo yêu cầu là phải không phụ thuộc vào vị trí, góc quay hay sự co giãn của đối tượng ảnh. Trước khi áp dụng các phương pháp trích chọn đặc điểm hình dạng, các đối tượng ảnh cần phải được tách ra khỏi ảnh. Giả sử là trong mỗi ảnh chỉ có một đối tượng ảnh duy nhất, nhiệm vụ của hệ thống trước hết là phải tách được đối tượng ảnh ra khỏi nền ảnh. Cách biểu diễn hình dạng của đối tượng ảnh có thể chia thành hai kiểu: Theo đường bao quanh (biên) và theo vùng Cách biểu diễn theo đường viền bao quanh chỉ sử dụng đường biên bên ngoài của hình dạng, điều này có thể thực hiện được bằng cách mô tả vùng đang quan tâm bằng cách đặc tính bên ngoài của nó tức là các điểm ảnh dọc theo đường viền bao quanh đối tượng ảnh. Cách biểu diễn theo vùng sử dụng cả vùng ảnh bằng cách mô tả vùng đang quan tâm bằng các đặc tính bên trong tức là các điểm ảnh ở bên trong vùng đó. 1.1.3. Đánh chỉ số nhiều chiều Để thực hiện việc tra cứu dựa vào nội dung đối với các cơ sở dữ liệu ảnh lớn, các kỹ thuật đánh chỉ số nhiều chiều cần được sử dụng. Có ba cộng đồng nghiên cứu chính đóng góp vào lĩnh vực này: hình học tính toán, quản trị cơ sở dữ liệu và nhận dạng mẫu. Các kỹ thuật đánh chỉ số nhiều chiều phổ biến như thuật toán bucketing, cây K-D, cây K-D ưu tiên, cây tứ phân, cây K-D-B, cây hB.v.v... 9 1.2. Một số khái niệm cơ bản trong xử lý ảnh Trước khi đi vào tìm hiểu một cách tổng quan về các quá trình xử lý ảnh, ta cần quan tâm tới một số khái niệm cơ bản. Để thực hiện được các bước của quá trình xử lý ảnh thì trước hết ta phải hiểu: xử lý ảnh là gì ? ảnh là gì ?...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. [1] 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 nhiều 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 riêng cho nó.[2] Trên đây là các thành phần cơ bản trong các khâu xử lý ảnh. Trong thực tế, các quá trình sử dụng ảnh số không nhất thiết phải qua hết các khâu đó tùy theo đặc điểm ứng dụng. Hình 1.3 sơ đồ phân tích và xử lý ảnh và lưu đồ thông tin giữa các khối một cách khá đầy đủ. Ảnh sau khi được số hóa được nén, lưu lại để truyền cho các hệ thống khác sử dụng hoặc để xử lý tiếp theo. Mặt khác, ảnh sau khi số hóa có thể bỏ qua công đoạn nâng cao chất lượng (khi ảnh đủ chất lượng theo một yêu cầu nào đó) để chuyển tới khâu phân đoạn hoặc bỏ tiếp khâu phân đoạn chuyển trực tiếp tới khâu trích chọn đặc trưng. Hình 1.3 cũng chia các nhánh song song như: nâng cao chất lượng ảnh có hai nhánh phân biệt: nâng cao chất lượng ảnh (tăng độsáng, độ tương phản, lọc nhiễu) hoặc khôi phục ảnh (hồi phục lại ảnh thật khi ảnh nhận được bị méo) v.v…[2]