Luận văn Thạc sĩ Khoa học máy tính: Tìm kiếm đối tượng vùng trong GIS véc tơ

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:73

Thêm vào BST

Báo xấu

26
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn sử dụng các phương pháp, thuật toán đã được nghiên cứu cho tìm kiếm kiếm ảnh trên cơ sở vùng trong CSDL ảnh để giải quyết bài toán tìm kiếm đối tượng địa lý dạng vùng trên bản đồ tương tự với hình dạng đối tượng cho trước. Đối tượng cho trước có thể được sinh ra bằng phác họa trên màn hình máy tính hay một tệp chứa ảnh, vùng bản đồ cần tìm. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: Tìm kiếm đối tượng vùng trong GIS véc tơ

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN THỊ THÚY NGA TÌM KIẾM ĐỐI TƯỢNG VÙNG TRONG GIS VÉC TƠ 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 NGUYỄN THỊ THÚY NGA TÌM KIẾM ĐỐI TƯỢNG VÙNG TRONG GIS VÉC TƠ 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 VĂN ĐỨC THÁI NGUYÊN - 2017
i LỜI CAM ĐOAN Tôi xin cam đoan tất cả các nội dung của luận văn này hoàn toàn được hình thành và phát triển từ quan điểm của chính cá nhân tôi, dưới sự hướng dẫn chỉ bảo của PGS.TS Đặng Văn Đức. Các số liệu kết quả có được trong luận văn tốt nghiệp là hoàn toàn trung thực. Học viên Nguyễn Thị Thúy Nga
ii LỜI CẢM ƠN Tôi xin gửi lời cảm ơn sâu sắc tới PGS.TS.ĐặngVăn Đức, Viện Công nghệ thông tin – Viện Hàn lâm Khoa học và Công nghệ Việt Nam,Thầy đã tận tình chỉ bảo giúp đỡ tôi trong suốt quá trình nghiên cứu và hoàn thành luận văn. Xin chân thành cảm ơn quý Thầy Cô và cán bộ nhân viên Phòng Đào Trường Đại học Công nghệ Thông tin và Truyền thông, Đại học Thái Nguyên đã nhiệt tình giảng dạy, trang bị cho tôi những kiến thức quý báu và giúp đỡ về mọi mặt trong suốt thời gian học tập tại trường. Xin cảm ơn các bạn cùng lớp và đồng nghiệp nơi tôi công tác đã tạo điều kiện cho tôi hoàn thành luận văn này. Xin gửi lời cảm ơn tới gia đình tôi đã động viên tôi trong suốt quá trình học tập và hoàn thành luận văn.
iii MỤC LỤC LỜI CAM ĐOAN .............................................................................................. i LỜI CẢM ƠN ................................................................................................... ii MỤC LỤC ........................................................................................................iii MỤC CÁC HÌNH VẼ, ĐỒ THỊ....................................................................... iv MỞ ĐẦU ........................................................................................................... 1 CHƯƠNG 1:TỔNG QUAN VỀ HỆ THỐNG TÌM KIẾM NỘI DUNG VÀ DỮ LIỆU KHÔNG GIAN VECTƠ .................................................................. 4 1.1.Mô hình tổng quát hệ thống tìm kiếm trên cơ sở nội dung ......................... 5 1.2. Biểu diễn và cấu trúc dữ liệu không gian vectơ ...................................... 11 CHƯƠNG 2: MỘT SỐ KỸ THUẬT TÌM KIẾM ĐỐI TƯỢNG VÙNG TRONG BẢN ĐỒ VECTƠ ............................................................................ 19 2.1 Khái quát về tìm kiếm đối tượng trên cơ sở hình dạng............................. 19 2.2 Đặc trưng hình dạng đơn giản ................................................................... 21 2.3 Moment bất biến ....................................................................................... 22 2.4. Phương pháp bộ mô tả Fourier................................................................. 25 2.5.Biểu diễn hình dạng trên cơ sở lưới vùng ................................................. 30 CHƯƠNG 3: XÂY DỰNG CHƯƠNG TRÌNH THỬ NGHIỆM................... 40 3.1 Quy trình tổng quan .................................................................................. 40 3.2.Trích xuất các vùng từ CSDL địa lý ......................................................... 42 3.3.Hiển thị dữ liệu địa lý................................................................................ 43 3.4.Hiển thị vùng đầu vào được chọn ............................................................. 44 3.5.Tìm kiếm vùng tương tự ........................................................................... 45 3.6.Thử nghiệm với một số vùng đầu vào ...................................................... 46 TÀI LIỆU THAM KHẢO ............................................................................... 56 PHỤ LỤC ........................................................................................................ 57
iv MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình1.1: Mô hình tổng thể hệ thống tìm kiếm thông tin .................................. 5 Hình1.2: Kiến trúc tổng thể của hệ thống tìm kiếm ảnh ................................... 6 Hình 1.3: Đánh giá hiệu năng hệ thống .......................................................... 10 Hình 1.4: Ví dụ biểu diễn vị trí nước bị ô nhiễm ............................................ 12 Hình 1.5: Ví dụ biểu diễn đường..................................................................... 13 Hình 1.6: Ví dụ biểu diễn khu vực hành chính ............................................... 14 Hình 1.7: Ví dụ về biểu diễn các Feature trên bản đồ..................................... 16 Hình 1.8: Đối tượng point trên bản đồ. ........................................................... 17 Hình 1.9: Đối tượng Line trên bản đồ ............................................................ 17 Hình 1.10: Đối tượng polyon trên bản đồ ..................................................... 17 Hình 2.1: Lưu đồ thuật toán tìm ra đặc trưng của ảnh sử dụng momet hình dạng ............................................................................................................. 24 Hình 2.2: Hàm dấu hiệu của hình dạng .......................................................... 25 Hình 2.3: Hàm góc tích lũy ............................................................................ 26 Hình 2.4: Hàm tính diện tích .......................................................................... 26 Hình 2.5: Lưu đồ thuật toán tìm ra đặc trưng của ảnh sử dụng bộ mô tả Fourier ............................................................................................................. 29 Hình 2.6:Ví dụ xếp chồng .............................................................................. 30 Hình 2.7: Ví dụ chuẩn hóa co giãn ................................................................. 32 Hình 2.8: Ví dụ về đo độ tương tự ................................................................. 34 Hình 2.9: Lưu đồ thuật toán tìm ra đặc trưng của ảnh sử dụng lưới vùng ... 37 Hình 2.10: Lưu đồ thuật toán tìm kiếm vùng tương tự ................................ 40 Hình 3.1: Sơ đồ hệ thống. ............................................................................... 41 Hình 3.2: Màn hình chính chương trình ......................................................... 42 Hình 3.3: Bản đồ các vùng tỉnh Quảng Ninh ................................................. 44
v Hình 3.4: Các vùng đầu vào ........................................................................... 45 Hình 3.5: Dữ liệu hình học vùng đầu vào ...................................................... 45 Hình 3.6: Hiển thị vùng đầu vào được chọn ................................................... 46 Hình 3.7: Kết quả tìm vùng tương tự với vùng 13. ........................................ 47 Hình 3.8: Kết quả tìm vùng tương tự với vùng 2. .......................................... 48 Hình 3.19: Kết quả tìm vùng tương tự với vùng 3. ........................................ 49 Hình 3.10: Kết quả tìm vùng tương tự với vùng 6. ........................................ 50 Hình 3.11: Kết quả tìm vùng tương tự với vùng 1. ........................................ 51 Hình 3.12: Kết quả tìm vùng tương tự với vùng 15. ...................................... 52 Hình 3.13: Kết quả tìm vùng tương tự với vùng 16. ...................................... 53 Hình 3.14: Kết quả tìm vùng tương tự với vùng 20. ...................................... 54 Hình 3.15: Kết quả tìm vùng tương tự với vùng 22. ...................................... 55 Hình P-1: Ví dụ một đa giác gồm hai vành. ................................................... 64 Hình P-2: Lưu trữ đa giác trong shapefile. ..................................................... 65
vi DANH MỤC BẢNG BIỂU Bảng P-1. Mô tả của Main file header .......................................................... 58 Bảng P-2. Các giá trị của shape type. ........................................................... 59 Bảng P-3. Mô tả header bản ghi. .................................................................. 60 Bảng P-4. Nội dung bản ghi biểu diễn điểm. ................................................ 61 Bảng P-5. Nội dung bản ghi biểu diễn đa điểm ........................................... .62 Bảng P-6. Nội dung bản ghi chi tiết đa đoạn. ............................................... 63 Bảng P-7. Nội dung bản ghi đa giác. ............................................................ 65
1 MỞ ĐẦU 1. Đặt vấn đề Hệ thống thông tin địa lý (GIS - Geograpgic Information System) đã bắt đầu được sử dụng rộng rãi ở các nước phát triển từ nhiều thập niên qua, đây là một dạng ứng dụng công nghệ thông tin nhằm mô tả thế giới thực (Real World) mà loài người đang sống-tìm hiểu-khai thác. Với những tính năng ưu việt của mình, kỹ thuật GIS ngày nay đang được ứng dụng trong nhiều lãnh vực nghiên cứu và quản lý, đặc biệt trong quản lý và quy hoạch sử dụng-khai thác các nguồn tài nguyên một cách bền vững và hợp lý. GIS được chia làm hai loại chính: GIS véc tơ và GIS raster. GIS véc tơ ngày nay được sử dụng nhiều hơn cả. Nền tảng của GIS là bản đồ véc tơ. Các bản đồ này được hình thành từ các đối tượng cơ bản như điểm, đường vùng. Dạng vùng thường được biểu diễn các đơn vị hành chính, ao hồ, thửa ruộng, các hòn đảo trên biển… Số lượng các đối tượng này thường rất lớn trong một bản đồ của hệ thống GIS. Một bài toán đặt ra cho người sử dụng GIS trong thực tế là: Hãy tìm kiếm theo nội dung các đối tượng dạng vùng trên bản đồ tương tự với đối tượng dạng vùng cho trước trên cơ sở topo, hướng, khoảng cách [9]. Như vậy bài toán này tương tự với bài toán tìm kiếm ảnh theo nội dung. Luận văn sử dụng các phương pháp, thuật toán đã được nghiên cứu cho tìm kiếm kiếm ảnh trên cơ sở vùng [2-5] trong CSDL ảnh để giải quyết bài toán tìm kiếm đối tượng địa lý dạng vùng trên bản đồ tương tự với hình dạng đối tượng cho trước. Đối tượng cho trước có thể được sinh ra bằng phác họa trên màn hình máy tính hay một tệp chứa ảnh, vùng bản đồ cần tìm. Vậy, nội dung nghiên cứu chính của luận văn “Tìm kiếm đối tượng vùng trong GIS véc tơ” bao gồm: - Một số vấn đề cơ bản về GIS véc tơ để thấy rõ cấu trúc dữ liệu các đối
2 tượng dạng vùng trong CSDL cần tìm kiếm, - Kiến trúc hệ thống tìm kiếm ảnh theo nội dung, - Các thuật toán tìm kiếm ảnh theo nội dung trên cơ sở vùng, - Xây dựng chương trình thử nghiệm. 2. Đối tượng và phạm vi nghiên cứu - Mô hình tổng quát hệ thống tìm kiếm trên cơ sở nội dung - Biểu diễn và cấu trúc dữ liệu không gian vectơ - Các lớp thuật toán đảm bảm tính nhất quán dữ liệu để từ đó nghiên cứu, đề xuất thuật toán tối ưu đảm bảo nhất quán dữ liệu. - Một số kỹ thuật ứng dụng tìm kiếm đối tượng vùng trong bản đồ vectơ 3. Hướng nghiên cứu của đề tài - Nghiên cứu kỹ thuật liên quan đến tìm kiếm ảnh trên cơ sở hình dạng. - Nghiên cứu phương pháp biểu diễn hình dạng và các đặc trưng hình dạng - Nghiên cứu giải pháp công nghệ cài đặt chương trình thử nghiệm. 4. Những nội dung nghiên cứu chính Ngoài phần mở đầu giới thiệu bài toán cần giải quyết của luận văn, phương pháp nghiên cứu và phần kết luận trình vày các kết quả thu được và các nghiên cứu tiếp theo để giải quyết các hạn chế của chúng, nội dung luận văn được chia thành ba chương như sau: Chương 1: Trình bày tổng quan về hệ thống tìm kiếm ảnh theo nội dung và dữ liệu không gian véc tơ. Bao gồm: mô hình hệ thống tìm kiếm thông tin theo nội dung, biểu diễn và cấu trúc dữ liệu không gian trong GIS. Chương 2: Trình bày một số kỹ thuật tìm kiếm ảnh trên cơ sở vùng áp dụng trong việc tìm kiếm đối tượng dạng vùng trong GIS vec tơ. Bao gồm thuật toán tìm kiếm đối tượng trên cơ sở biểu diễn vùng, thuật toán bộ mô tả
3 Fourier, mô ment ảnh. Chương 3: Trình bày chương trình thử nghiệm, bao gồm: dữ liệu bản đồ hành chính tỉnh Quảng Ninh, kiến trúc hệ thống thử nghiệm, đánh giá kết quả thử nghiệm. 5. Phương pháp nghiên cứu - Phương pháp nghiên cứu lý thuyết: thu thập, tổng hợp các tài liệu đã công bố, so sánh để tìm ra vấn đề phù hợp để nghiên cứu học hỏi và đề xuất các phương pháp cài đặt trên ngôn ngữ lập trình Matlab, C # - Liên hệ thường xuyên với giáo viên hướng dẫn và các chuyên gia để thực hiện luận văn cho đúng hướng, đúng tiến độ - Phương pháp thực nghiệm để minh chứng hiệu quả của giải pháp lựa chọn thông qua các nhận xét, phân tích đánh giá kết quả thử nghiệm. 6. Ý nghĩa khoa học của đề tài - Luận văn nghiên cứu kỹ thuật tìm kiếm đối tượng vùng trong GIS vectơ - Cài đặt thử nghiệm các kỹ thuật tìm kiếm đối tượng vùng trong bản đồ vectơ - Giải quyết bài toán tìm kiếm đối tượng vùng trong GIS vectơ
4 CHƯƠNG 1 TỔNG QUAN VỀ HỆ THỐNG TÌM KIẾM NỘI DUNG VÀ DỮ LIỆU KHÔNG GIAN VECTƠ 1.1.Mô hình tổng quát hệ thống tìm kiếm trên cơ sở nội dung Chúng ta đang đối mặt với sự bùng nổ thông tin đa phương tiện. Thí dụ tồn tại một số lượng lớn ảnh và video trên Internet. Rất nhiều tranh vẽ, ảnh chụp đang được chuyển sang dạng số để dễ xử lý và phân tán, bảo quản. Các bức ảnh từ bản tin TV và trên báo cũng đang được chuyển sang dạng số để dễ dàng quản lý. Lượng lớn ảnh y tế, ảnh vệ tinh đang được thu thập hàng ngày. Xu thế này thúc đẩy phát triển công nghệ số lưu trữ và trình diễn. Không thể sử dụng nhanh và hiệu quả các thông tin đa phương tiện này nếu chúng không được tổ chức tốt để truy tìm nhanh. Các hệ thống tự động truy tìm thông tin (IR-InformationRetrieval) đã được phát triển ban đầu để quản lý khối lượng lớn tài liệu khoa học từ những năm 40 của thế kỷ XX [7].Chức năng chính của hệ thống IR là lưu trữ và quản trị khối lượng văn bản lớn theo cách sao cho dễ dàng truy vấn (query) tài liệu mà người sử dụng quan tâm. Hệ thống tự động tìm kiếm thông tin đã được mở rộng về sau để có thể lưu trữ, chỉ mục và tìm kiếm theo nội dung các loại dữ liệu văn bản, hình ảnh, âm thanh và video. Các thao tác của một hệ thống tìm kiếm đa phương tiện nói chung và hệ thống tìm kiếm ảnh nói riêng được mô tả khái quát trên hình 1.1 [7]. Hệ thống bao gồm hai nửa: Hoạt động offline (bên phải) và hoạt động online (phần bên trái hình). Bên offline, các mục thông tin(Information Item) được tiền xử lý để trích chọn đặc trưng và nội dung ngữ nghĩa để lưu vào CSDL. Sau đó chúng được chỉ số hóa trên cơ sở đặc trưng và ngữ nghĩa này.
5 Queries Information Items Processing and feature extraction Preprocessing and indexing Query Indexed features information items Similarity computation Retrieval of similar items Hình 1.1 Mô hình tổng thể hệ thống tìm kiếm thông tin đa phương tiện Trong pha tìm kiếm thông tin (online), câu truy vấn của người sử dụng được xử lý và các đặc trưng của nó được trích chọn. Đối với hệ thống tìm kiếm ảnh, câu truy vấn có thể là ảnh phác họa hay một ảnh chụp làm ví dụ (query by example). Các đặc trưng vừa trích chọn sau đó được so sánh (đối sánh) với các đặc trưng hay chỉ mục dữ liệu trong CSDL. Các mục thông tin nào có đặc trưng gần giống nhất với các đặc trưng của câu truy vấn thì được tìm ra và trình diễn cho người sử dụng làm kết quả. Mô hình trên đây cho thấy rất nhiều nhiệm vụ phải thực hiện trong một hệ thống tìm kiếm dữ liệu đa phương tiện theo nội dung, thí dụ: Trích chọn đặc trưng từ các dữ liệu đa phương tiện này như thế nào? Các đặc trưng được lưu trữ và cấu trúc như thế nào để truy tìm hiệu quả? Đo tính “tương tự” giữa hai đối tượng đa phương tiện như thế nào? Thiết kế giao diện như thế nào để nó có thể chấp nhận các câu truy vấn phức tạp, mờ và mềm dẻo? So sánh hiệu năng giữa các hệ thống tìm kiếm đa phương tiện bằng
6 cách nào? Các vấn đề trên đây cần được quan tâm nghiên cứu để phát triển hệ thống đa phương tiện. Xây dựng cơ Ảnh kết sở dữ liệu ảnh quả Cơ sở dữ liệu Dữ liệu ảnh ảnh Trích chọn các Cơ sở dữ liệu đặc trưng ảnh đặc trưng Đo mức độ tương tự Truy vấn Ảnh mẫu Trích chọn các Các đặc trưng đã truy vấn đặc trưng được trích chọn Hình 1.2 Kiến trúc tổng thể của hệ thống tìm kiếm ảnh Kiến trúc của một hệ thống tìm kiếm ảnh theo nội dung được mô tả trên hình 1.2. Ảnh là một loại dữ liệu đa phương tiện được thu thập, quản lý, xử lý nhiều nhất. Đã có nhiều công trình công bố liên quan đến tìm kiếm ảnh trong CSDL [7]. Ảnh có thể trong khuôn mẫu raster hay khuôn mẫu véc tơ. Ảnh có thể thu thập từ chụp ảnh, sinh ra từ máy tính hay một dạng của bản đồ trong hệ thống thông tin địa lý. Hệ thống tìm kiếm ảnh cơ bản gồm hai pha: Pha xây dựng CSDL ảnh thực hiện offline và pha truy vấn ảnh thực hiện online. Trong pha Offline người sử dụng thu thập ảnh (bản đồ) để lưu trữ trong CSDL. Ảnh đầu vào được trích chọn đặc trưng ví dụ trích chọn biểu đồ màu, hình dạng đối tượng, bộ mô tả Fourier… để đối sánh sau này. Các đặc trưng
7 có kích thước nhỏ hơn nhiều so với dữ liệu ảnh gốc để đối sánh cho nhanh. Có nhiều nghiên cứu về việc lựa chọn và kỹ thuật trích chọn đặc trưng được công bố. Đặc trưng nào được sử dụng trong hệ thống ảnh phụ thuộc vào loại ảnh được quản lý trong CSDL [7]. Trong luận văn này, đầu vào là các đối tượng dạng vùng của một bản đồ véc tơ như đơn vị hành chính (ví dụ cấp xã), ao, hồ, các đảo ngoài khơi… Các đặc trưng có thể phù hợp cho loại ảnh véc tơ này là bộ mô tả Fourier, moment ảnh, lưới vùng… Dữ liệu ảnh gốc đầu vào và các đặc trưng tương ứng được lưu trữ trong CSDL ảnh. Thông thường các đặc trưng ảnh được biểu diễn dưới dạng véc tơ đa chiều. Số lương dữ liệu là rất lớn, do vậy, chúng phải được lưu trữ trong CSDL theo cách nào đó để truy vấn nhanh. Các cấu trúc dữ liệu dạng cây được lựa chọn để giảm thiểu thời gian xâm nhập đĩa, tránh tìm kiếm tuyến tính để đối sánh trong CSDL. Các cấu trúc dữ liệu như cây đa chiều, hay cây R là phù hợp hơn cả [7]. Trong pha online (pha truy vấn), người sử dụng tạo ra câu truy vấn để tìm kiếm ảnh mong muốn trong CSDL. Kỹ thuật hay được sử dụng là “tìm kiếm theo ví dụ” (Query by example). Đầu vào pha tìm kiếm là một ảnh mẫu làm ví dụ để tìm kiếm theo nó. Ảnh mẫu có thể được phác họa trên máy tính bằng thiết bị nào đó như bút ánh sáng, thậm chí bằng con chuột máy tính. Ảnh đầu vào cũng có thể là một ảnh có sẵn trong máy để tìm ra ảnh tương tự trong CSDL. Ảnh mẫu này được trích chọn đặc trưng để hình thành các véc tơ đặc trưng. Đặc trưng được sử dụng tương ứng với các đặc trưng được trích chọn trong pha offline. Véc tơ đặc trưng của ảnh mẫu được đối sánh với các đặc trưng trong CSDL. Do các véc tơ đặc trưng đã được lưu trữ trong cấu trúc dạng cây nên việc đối sánh không cần tuần tự, làm tăng hiệu năng hệ thống.
8 Đo mức độ tương tự giữa các ảnh Đây là nhiệm vụ quan trọng trong hệ thống tìm kiếm ảnh. Đối sánh trong CSDL ảnh không phải là đối sánh chính xác như trong CSDL truyền thống. Ở đây là đối sánh tương tự để xác định mức độ tương tự của véc tơ truy vấn với các véc tơ đặc trưng trong CSDL, sau đó xếp hạng để người sử dụng quyết định ảnh kết quả mong muốn. Các độ đo khác nhau được lựa chọn để sử dụng như độ đo cosine, khoảng cách Lp (Minkowski),… Khoảng cách cosine: Với ảnh trong CSDL Di và ảnh mẫu truy vấn Qj được biểu diễn như các véctơ n-chiều của các trọng số Di  Ti1 , Ti 2 ,..., Tik ,..., TiN  (1.1)  Q j  Q j1 , Q j 2 ,..., Q jk ,..., Q jN  Mức độ tương tự của hai ảnh được xác định bởi cosine của góc giữa hai véc tơ này. Khoảng cách này được gọi là khoảng cách cosine. Góc càng nhỏ hay cosine càng lớn thì hai ảnh càng tương tự nhau. N Di .Q j T ik .Q jk (1.2) S ( Di , Q j )  cos   k 1 | Di || Q j | N N  Tik2 . k 1 Q k 1 2 jk Độ đo khoảng cách Lp (Minkowski): Ví dụ cho trước hai véc tơ n-chiều I  [i1 , i2 ,..., in ]T H  [h1 , h2 ,..., hn ]T (1.3) Khoảng cách Minkowski được tính theo công thức sau: 1/ p  n p  Lp   | ii  hi |   (1.4)  i 1    Trong CSDL ảnh có thể sử dụng giá trị p như sau: Nếu p=1 ta có khoảng cách Manhattan hay khoảng cách City block: n d p 1 ( I , H )  | il  hl | (1.5) l 1
9 Với p=2 ta có khoảng cách Euclid: n (1.6) d p 2 ( I , H )   [il  hl ]2 l 1 Đánh giá hiệu năng hệ thống Bất cứ hệ thống thông tin nào được xây dựng cũng cần được đánh giá hiệu năng để khuyến cáo sử dụng. Đánh giá hiệu năng một hệ thống thông tin bằng nhiều độ đo khác nhau, có thể là đánh giá theo các chức năng, đánh giá theo các yêu cầu phi chức năng của hệ thống (ví dụ với các ứng dụng Web). Trong hệ thống tìm kiếm ảnh, thông thường hệ thống được đánh giá theo ba tiêu chí sau: a. Tốc độ xử lý: Hệ thống chạy càng nhanh thì hiệu năng càng cao. Tốc độ xử lý có thể được xác định bằng độ phức tạp của thuật toán hay kiến trúc hệ thống được xây dựng b. Độ trung thực (Recall): Tính toán (đo) công suất tìm kiếm các ảnh trong CSDL liên quan đến ảnh mẫu đầu vào truy vấn. Chúng được xác định bởi tỷ lệ giữa tổng số ảnh liên quan được tìm ra và toàn bộ số các ảnh liên quan trong CSDL. Recall càng cao thì hiệu năng càng cao. c. Độ chính xác (Precision): Một tiêu chuẩn nữa của hiệu năng hệ thống là đo độ chính xác tìm kiếm trong CSDL. Độc chính xác được xác định bởi tỷ lệ giữa số ảnh được tìm ra mà người sử dụng thỏa mãntrên tổng số ảnh được hệ thống tìm thấy. Độ chính xác càng cao thì hiệu năng hệ thống càng cao. Tính toán độ trung thực và độ chính xác như sau:
10 Giả sử ta có một tập ảnh để test (tập mẫu), đã biết trước tổng số ảnh và số lượng ảnh phù hợp với yêu cầu của người sử dụng như trên hình 1.3. Pert – Tập con ảnh phù hợp trong thực tế, người sử dụng mong muốn Retr - Tập con ảnh mà hệ thống tìm ra Độ trung thực được tính như sau: (1.7) Pert  Retr  0,1 Pert Độ chính xác được tính bởi công thức: Pert  Retr (1.8)  0,1 Retr Tậpảnh phù hợp đối với users Tậpảnhdo hệ thống tìm thấy Tập ảnh thử nghiệm Hình 1.3 Đánh giá hiệu năng hệ thống Khi đánh giá hiệu năng hệ thống thông tin, cần đánh giá đồng thời hai tiêu chí này. Nếu độ trung thực và độ chính xác càng cao thì hiệu năng hệ thống càng cao. Ba tiêu chí đánh giá hiệu năng hệ thống trên đây, bao gồm, tốc độ thực hiện, độ trung thực (độ nhạy) và độ chính xác được áp dụng trong luận văn này. Các ảnh mô tả trên đây được xem như các đối tượng dạng vùng trên bản đồ véc tơ.
11 1.2. Biểu diễn và cấu trúc dữ liệu không gian vectơ Hệ thống thông tin địa lý (GIS) được xem như hệ thống thông tin có khả năng mã hóa, lưu trữ, chuyển đổi, phân tích và hiển thị dữ liệu địa lý (dữ liệu có tham chiếu không gian) [1]. Nền tảng hoạt động của GIS là bản đồ. Các đối tượng trên bản đồ (ví dụ như sông ngòi, các đơn vị hành chính, đất trồng trọt,…) có thể được được biểu diễn bới các giá trị khác nhau của điểm ảnh (hay còn gọi là tế bào). Mỗi tế bào gắn theo giá trị thuộc tính của đối tượng trên bản đồ. GIS trên cơ sở bản đồ như vậy được gọi là GIS raster. Các đối tượng trên bản đồ cũng có thể được biểu diễn bới các đối tượng hình học cơ bản: điểm, đường, vùng. Mỗi đối tượng hình học cơ bản này được biểu diễn bới các tọa độ hay véc tơ trong hệ tọa độ qui chiếu sử dụng trong hệ thống. GIS được xây dựng trên cơ sở dữ liệu bản đồ véc tơ được gọi là GIS véc tơ. Cả hai trong phạm vi luận văn này, bản đồ có cấu trúc véctơ. Phần này trình bày phương pháp biểu diễn và cấu trúc dữ liệu không gian véc tơ. Trên cơ sở đó, các thuật toán tìm kiếm hình dạng trên bản đồ được tìm hiểu và thử nghiệm. *. Biểu diễn dữ liệu không gian vectơ Thành phần dữ liệu không gian hay còn gọi là dữ liệu bản đồ, là dữ liệu về đối tượng mà vị trí của nó được xác định trên bề mặt trái đất. Dữ liệu không gian sử dụng trong hệ thống địa lý luôn được xây dựng trên một hệ thống tọa độ, bao gồm tọa độ, quy luật và các ký hiệu dùng để xác định một hình ảnh bản đồ cụ thể trên mỗi bản đồ. Hệ thống GIS dùng thành phần dữ liệu không gian để tạo ra bản đồ hay hình ảnh bản đồ trên màn hình hoặc trên giấy thông qua thiết bị ngoại vi. Mỗi hệ thống GIS có thể dùng các mô hình khác nhau để mô hình hóa thế giới
12 thực sao cho giảm thiểu sự phức tạp của không gian nhưng không mất đi các dữ liệu cần thiết để mô tả chính xác các đối tượng trong không gian. Hệ thống GIS hai chiều 2D dùng ba kiểu dữ liệu cơ sở sau để mô tả hay thể hiện các đối tượng trên bản đồ vector, đó là: Ðiểm (Point) Điểm được xác định bởi cặp giá trị tọa độ (x, y). Các đối tượng đơn với thông tin về địa lý chỉ bao gồm vị trí thường được mô tả bằng đối tượng điểm. Các đối tượng biểu diễn bằng kiểu điểm thường mang đặc tính chỉ có tọa độ đơn (x, y) và không cần thể hiện chiều dài và diện tích. Ví dụ, trên bản đồ, các vị trí của bệnh viện, các trạm rút tiền tự động ATM, các cây xăng,… có thể được biểu diễn bởi các điểm. Hình 1.3 là ví dụ về vị trí nước bị ô nhiễm. Mỗi vị trí được biểu diễn bởi 1 điểm gồm cặp tọa độ (x, y) và tương ứng với mỗi vị trí đó có thuộc tính độ sâu và tổng số nước bị nhiễm bẩn. Các vị trí này được biểu diễn trên bản đồ và lưu trữ trong các bảng dữ liệu. Hình 1.4 Ví dụ biểu diễn vị trí nước bị ô nhiễm