Tài liệu Nghiên cứu một số thuật toán tìm đường đi trong gis ứng dụng logic mờ

    ĐẠI HỌC THÁI NGUYÊN  TRƯỜNG ĐẠI HỌC CNTT&TT THÁI NGUYÊN VŨ THÚY HÀ NGHIÊN CỨU MỘT SỐ THUẬT TOÁN TÌM ĐƯỜNG ĐI TRONG GIS ỨNG DỤNG LOGIC MỜ     Ngành: Công nghệ thông tin  Chuyên ngành: Khoa học máy tính  Mã số: 60 48 01 01  LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC PGS. TS. ĐẶNG VĂN ĐỨC THÁI NGUYÊN, 2016        LỜI CAM ĐOAN   Tên tôi là: Vũ Thúy Hà  Sinh ngày:   Học  viên  lớp  cao  học  CHK13A  -  Trường  Đại  học  Công  nghệ  thông  tin  và  Truyền thông – Đại học Thái Nguyên.  Hiện đang công tác tại:   Xin cam đoan: Đề tài “Nghiên cứu một số thuật toán tìm đường đi trong GIS ứng dụng logic mờ” do Thầy giáo PGS.TS. Đặng Văn Đứchướng dẫn là công trình nghiên  cứu của riêng tôi. Tất cả tài liệu tham khảo đều có nguồn gốc, xuất xứ rõ ràng.  Tác giả xin cam đoan tất cả những nội dung trong luận văn đúng như nội dung  trong đề cương và yêu cầu của thầy giáo hướng dẫn. Nếu sai tôi hoàn toàn chịu trách  nhiệm trước hội đồng khoa học và trước pháp luật.  Thái Nguyên, ngày 26 tháng 06năm 2016    TÁC GIẢ LUẬN VĂN    Vũ Thúy Hà           i          LỜI CẢM ƠN   Sau một thời gian nghiên cứu và làm việc nghiêm túc, được sự động viên, giúp  đỡ và hướng dẫn tận tình của Thầy giáo hướng dẫn PGS.TS. Đặng Văn Đức, luận văn  với đề tài “Nghiên cứu một số thuật toán tìm đường đi trong GIS ứng dụng logic mờ”đã  hoàn thành.  Tôi xin bày tỏ lòng biết ơn sâu sắc đến:  Thầy giáo hướng dẫn PGS.TS. Đặng Văn Đứcđã tận tình chỉ dẫn, giúp đỡ tôi  hoàn thành luận văn này.  Khoa Sau đại học Trường Đại học công nghệ thông tin và truyền thông đã giúp  đỡ tôi trong quá trình học tập cũng như thực hiện luận văn.  Tôi  xin  chân  thành  cảm  ơn  bạn  bè,  đồng  nghiệp  và  gia  đình  đã  động  viên,  khích  lệ,  tạo  điều  kiện  giúp  đỡ  tôi  trong  suốt  quá  trình  học  tập,  thực  hiện  và  hoàn  thành luận văn này.  TÁC GIẢ LUẬN VĂN      Vũ Thúy Hà     ii          MỤC LỤC LỜI CAM ĐOAN ............................................................................................................. i  LỜI CẢM ƠN ................................................................................................................. ii  DANH MỤC CÁC HÌNH ẢNH ..................................................................................... v  DANH MỤC BẢNG BIỂU ............................................................................................ vi  DANH MỤC CÁC TỪ VIẾT TẮT .............................................................................. vii  LỜI MỞ ĐẦU ................................................................................................................. 1  CHƯƠNG 1TỔNG QUAN VỀ  HỆ THỐNG ĐỊA LÝ VÀ LOGIC MỜ ...................... 5  1.1  Hệ thống thông tin địa lý (GIS) ........................................................................ 5  1.1.1  Định nghĩa về hệ thông tin địa lý ..................................................................... 5  1.1.2  Biểu diễn dữ liệu địa lý ..................................................................................... 7  1.1.2.1  Các thành phần của dữ liệu địa lý ..................................................................... 7  1.1.2.2  Mô hình biểu diễn dữ liệu không gian ............................................................ 11  1.1.3  Phân tích và xử lý dữ liệu không gian trong GIS ........................................... 13  1.1.3.1  Tìm kiếm theo vùng ........................................................................................ 13  1.1.3.2  Tìm kiếm lân cận ............................................................................................ 14  1.1.3.3  Phân tích đường đi và dẫn đường ................................................................... 14  1.1.3.4  Tìm kiếm hiện tượng và bài toán chồng phủ .................................................. 14  1.1.4  Ứng dụng của hệ thông tin địa lý ................................................................... 18  1.2  Tổng quan về logic mờ ................................................................................... 20  1.2.1  Giới thiệu ........................................................................................................ 20  1.2.2  Cơ sở toán học của logic mờ .......................................................................... 22  1.2.2.1  Tập mờ ............................................................................................................ 22  1.2.2.2  Các phép toán trên tập mờ .............................................................................. 23  1.2.2.3  Số mờ .............................................................................................................. 25  1.2.2.4  Luật nếu –thì mờ ............................................................................................. 26  1.2.3  Một số hệ mờ tiêu biểu ................................................................................... 28  1.3  Kết luận chương .............................................................................................. 31  CHƯƠNG 2THUẬT TOÁN  ĐƯỜNG ĐI NGẮN NHẤT MỜ TRONG GIS ............. 33  2.1  Khả năng ứng dụng của hệ mờ trong GIS ...................................................... 33  2.1.1  Giới thiệu ........................................................................................................ 33  iii          2.1.2  Tính không rõ ràng trong GIS ........................................................................ 35  2.2  Nghiên cứu một số thuật toán tìm đường đi ngắn nhất ứng dụng logic mờ ... 37  2.2.1  Bài toán tìm đường đi ngắn nhất .................................................................... 37  2.2.2  Một số thuật toán tìm đường đi ngắn nhất kinh điển ...................................... 39  2.2.2.1  Thuật toán Dijkstra ......................................................................................... 39  2.2.2.2  Thuật toán Bellman-Ford ................................................................................ 43  2.2.2.3  Thuật toán A* ................................................................................................. 44  2.2.3  Phân tích một số thuật toán tìm đường đi ngắn nhất mờ ................................ 46  2.2.3.1  Thuật toán FSA ............................................................................................... 46  2.2.3.2  Thuật toán tìm đường đi ngắn nhất trên cơ sở số mờ ..................................... 48  2.2.3.3  Thuật toán Dijkstra mờ ................................................................................... 49  2.3  Kết luận chương .............................................................................................. 55  CHƯƠNG 3XÂY DỰNG CHƯƠNG TRÌNH THỬ NGHIỆM THIẾT KẾ TUYẾN XE  BUS CHO THÀNH PHỐ THÁI NGUYÊN ................................................................. 56  3.1  Mô tả bài toán ................................................................................................. 56  3.2  Phương pháp tiến hành ................................................................................... 57  3.2.1  Các công cụ hỗ trợ .......................................................................................... 57  3.2.1.1  Phần mềm ArcGIS .......................................................................................... 57  3.2.1.2  Phần mềm Matlab R2015a ............................................................................. 58  3.2.2  Các bước thực hiện ......................................................................................... 59  3.2.3  Chương trình minh họa thuật toán  Dijikstra mờ............................................ 62  3.3  Kết luận chương .............................................................................................. 65  KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .................................................................... 66  TÀI LIỆU THAM KHẢO ............................................................................................. 68      iv          DANH MỤC CÁC HÌNH ẢNH Hình 1-1 Hệ thống thông tin địa lý [3] ............................................................................ 6  Hình 1-2 Tầng (layer) bản đồ [3] .................................................................................... 6  Hình 1-3 Ví dụ biểu diễn vị trí nước bị ô nhiễm [1] ....................................................... 8  Hình 1-4 Ví dụ biểu diễn đường [1] ................................................................................ 9  Hình 1-5 Ví dụ biểu diễn khu vực hành chính [1] ........................................................... 9  Hình 1-6 Biểu diễn thế giới bằng mô hình vectơ và raster ........................................... 12  Hình 1-7 Chồng phủ đa giác [1] .................................................................................... 16  Hình 1-8 Tiến trình phủ đa giác [1] ............................................................................... 17  Hình 1-9  Một số dạng hàm liên thuộc cơ bản .............................................................. 23  Hình 1-10  Số mờ tam giác ............................................................................................ 26  Hình 1-11  Hàm liên thuộc của biến ngôn ngữ T(tuổi) ................................................. 27  Hình 1-12  Mô hình suy diễn mờ Mamdani .................................................................. 29  Hình 1-13 Mô hình mờ Sugeno ..................................................................................... 30  Hình 1-14 Mô hình suy luận mờ Tsukamoto ................................................................ 30  Hình 2-1 Tính chất không rõ ràng phát sinh khi xác định ranh giới ............................. 36  Hình 2-2 Đồ thị minh hoạ thuật toán Dijkstra ............................................................... 41  Hình 2-3 Đồ thị minh họa thuật toán Bellman-Ford ..................................................... 43  Hình 2-4 Đồ thị mờ G minh họa  thuật toán FSA ......................................................... 47  Hình 2-5 Các đường đi mờ ngắn nhất của đồ thị mờ G ................................................ 48  Hình 2-6  Cấu trúc mạng lưới giao thông ...................................................................... 52  Hình 3-1  Các bước thực hiện bài toán .......................................................................... 59  Hình 3-2  Bản đồ thành phố Thái nguyên với các thuộc tính trên Arcmap .................. 59  Hình 3-3  Minh họa vị trí có thể đặt trạm xe Bus sau khi xếp chồng dữ liệu ............... 60  Hình 3-4  Minh họa quá trình mờ hóa vị trí điểm đặt trạm ........................................... 60  Hình 3-5  Minh họa quá trình tính khoảng cách mờ ..................................................... 61  Hình 3-6  Giao diện chương trình chính ....................................................................... 62  Hình 3-7  Bản đồ giao thông TP Thái Nguyên.............................................................. 63  Hình 3-8  Các vị trí tiềm năng cho đặt trạm xe Bus trên TP Thái Nguyên ................... 63  Hình 3-9  Mờ hóa dữ liệu .............................................................................................. 64  Hình 3-10  Minh họa thuật toán .................................................................................... 64  v          DANH MỤC BẢNG BIỂU    Bảng 1.1 So sánh mô hình dữ liệu Vector và Raster. .................................................... 12  Bảng 2.1 Trọng số mờ của các nút trong Hình 2-6 ....................................................... 52  Bảng 2.2 Kết quả ba bước đầu của thuật toán Dijkstra mờ ........................................... 53  Bảng 2.3 Kết quả bước cuối (bước 22) của thuật toán Dijkstra mờ .............................. 54      vi            DANH MỤC CÁC TỪ VIẾT TẮT Từ hoặc Từ tiếng Anh  Từ tiếng Việt  BFS  Best-first search  Tìm kiếm theo lựa chọn tốt nhất  BOA  Bisector of Area  Chia đều hai miền mờ  COA  Centroid of Area  Tâm của miền mờ  CSDL    Cơ sở dữ liệu  FL  Fuzzy Logic  Logic mờ  Fuzzy Shortest Path  Thuật toán tìm đường đi ngắn  Algorithm  nhất mờ  Geographic  Hệ thống thông tin địa lý  cụm từ  FSA  GIS  Information System  MF  Membership Function  Hàm liên thuộc  MOM  Mean of maximum  Giá trị cực đại trung bình      vii          LỜI MỞ ĐẦU 1. Tính khoa học và cấp thiết của đề tài Hệ thống thông tin địa lý (Geographic Information System – GIS) ra đời trên cơ  sở phát triển của khoa học máy tính và được ứng dụng rộng rãi trong nhiều ngành khoa  học có liên quan đến xử lý dữ liệu không gian. GIS được hình thành từ những năm 70  của thế kỷ trước và phát triển mạnh mẽ trong một hai chục năm trở lại đây. GIS đã trở  thành  công  cụ  hỗ  trợ  ra  quyết  định hầu  hết trong các hoạt  động  kinh  tế – xã  hội,  an  ninh – quốc phòng, trong quản lý, quy hoạch, thăm dò, khai thác… Trong đó, bài toán  tìm kiếm đường đi tối ưu cho các ứng dụng cứu hộ, cứu nạn, hướng dẫn du lịch, quản  lý mạng giao thông vận tải… đang là chủ đề được nhiều nhà khoa học quan tâm.  Đối với GIS, các dữ liệu thu thập thường không đầy đủ, không rõ ràng, không  chắc  chắn  và  mập  mờ,  điều  đó  dẫn  đến  dữ  liệu  và  thông  tin  trong  GIS  là  dữ  liệu  “không rõ ràng” hay dữ liệu “mờ”. Khái niệm “không rõ ràng – mờ” là đặc trưng vốn  có của dữ liệu địa lý và có thể sinh ra do: Thông tin tương ứng với chúng không đầy  đủ;  sự  xuất  hiện  không  ổn  định  khi  thu  thập  tập  hợp  các  dữ  liệu  thuộc  tính;  việc  sử  dụng các diễn tả định tính đối với các giá trị thuộc tính và các mối quan hệ giữa chúng.   Các hệ GIS truyền thống thường không sẵn sàng cho việc xử lý với các dữ liệu  mờ. Vì thế cần phải có sự mở rộng cả về mô hình dữ liệu, các phép toán và lập luận để  giải quyết với dữ liệu mờ trong GIS làm cho hệ thống trở nên mềm dẻo hơn trong việc  giải các bài toán không gian mà dữ liệu của chúng là các dữ liệu dạng mờ.  Với những lý do trên, tác giả đã chọn đề tài “Nghiên cứu một số thuật toán tìm đường đi trong GIS ứng dụng logic mờ” làm đề tài nghiên cứu luận văn tốt nghiệp  thạc sĩ chuyên ngành Khoa học máy tính.  2. Lịch sử nghiên cứu Bài toán tìm đường đi tối ưu đề cập đến việc tìm kiếm con đường với chi phí tối  thiểu giữa hai điểm. Đây là một vấn đề cơ bản trong lý thuyết đồ thị. Trong bài toán  tìm đường đi tối ưu thông thường, các thông số (khoảng cách, thời gian…) giữa các  nút khác nhau được giả định rằng biết chính xác. Nhưng trong những tình huống thực  1        tế đời  sống,cụ thể  là trong các hệ  GIS,  luôn  luôn  tồn tại sự  không  chắc chắn  về các  thông số giữa các nút khác nhau. Trong trường hợp như vậy, các thông số này được  đại diện bởi số mờ (Zadeh, 1965).  Từ năm 1991, Klein đã đưa ra mô hình mới về tìm đường đi ngắn nhất mờ và  cũng đã đưa ra một thuật toán tổng quát dựa trên quy hoạch động để giải quyết các mô  hình mới này. Lin & Chen (1993) xem xét trường hợp mà khoảng cách được xem là  một  số  mờ  và  đề  xuất  một  thuật  toán  cho  việc  tìm  kiếm  đường  đi  tối  ưu  trong  một  mạng.  Okada  &  Gen  (1994)  đã  thảo  luận  về  các  vấn  đề  xung  quanh  việc  tìm  kiếm  đường đi ngắn nhất từ một nút gốc cố định tới một nút được chỉ định trong một mạng  lưới với các cung biểu diễn như là khoảng số thực. Li và các cộng sự (1996) đã đưa ra  phương pháp sử dụng mạng nơron cho bài toán tìm đường đi ngắn nhất mờ. Gent và  các cộng sự (1997) đã nghiên cứu khả năng sử dụng các thuật toán di truyền để giải  quyết bài toán tìm đường đi ngắn nhất. Okada (2001) tập trung vào bài toán tìm đường  đi ngắn nhất trên mạng, trong đó một số mờ, thay vì một số thực, được gán cho mỗi  khoảng  cách  và  đưa  rakhái  niệm  về  "mức  độ  khả  năng"  để  một  cung  nằm  trên  con  đường ngắn nhất. Liu & Kao (2004) đã nghiên cứu vấn đề lưu lượng mạng trong đó  chiều dài một liên kết của mạng là số mờ. Seda (2005) giải bài toán duyệt cây trên một  đồ thị trong đó một số mờ, thay vì một số thực, được gán cho mỗi cạnh.  Takahashi Yamanaka (2005) thảo luận các vấn đề đường đi ngắn nhất với các  thông số mờ. Ông đề xuất sửa đổi thuật toán Okada (2001), sử dụng một số tính chất  quan  sát  bởi  các  tác  giả  khác.  Ông  cũng  đề  xuất  một  thuật  toán  di  truyền  để  tìm kiếm một giải pháp xấp xỉ đối với các bài toán có quy  mô lớn. Chuang & Kung  (2005) xem xét mỗi cung trong đồ thị là một tập mờ hình tam giác và một thuật toán  mới được đề xuất để tìm đường đi ngắn mờ. Nayeem Pal (2005)coi là một mạng với  độ dài cunglà số không chính xác thay vì một số thực (khoảng số thực và số mờ tam  giác).  Ma  &  Chen  (2005)  đề  xuất  một  thuật  toán  cho  mờ  các  vấn  đề  đường  đi  ngắn  nhất on line. Kung & Chuang (2005) đề xuất một thuật toán mới kết hợp các thủ tục  mờ trong tìm kiếm đường đi ngắn nhất và độ đo tương tự. Gupta & Pal (2006) trình  bày một thuật toán cho các vấn đề đường đi ngắn nhất khi các vòng cung được kết nối  trong một mạng lưới giao thông được đại diện bằng khoảng mờ.  2        Đặc biệt trong lĩnh vực tìm đường trên các hệ thống GIS cũng đã có rất nhiều  công  bố  sử dụng  giải  pháp  tìm  đường  đi  mờ[5] [6] [11] . Petrik  (2007)  đưa  ra  thuật  toán FSA ứng dụng trên GIS. Năm 2012, Yong den và các cộng sự đề xuất khả năng  áp dụng trong GIS của giải thuật Dijkstra mờ (kết hợp biểu diễn cung bằng số mờ tam  giác, hình thang và tìm kiếm theo phương pháp Dijkstra truyền thống).  3. Mục tiêu, đối tượng và phạm vi nghiên cứu của đề tài Đề tài nhằm thực hiện các mục tiêu sau: - Nghiên cứu một số thuật toán tìm đường tối ưu  - Nghiên cứu một số thuật toán tìm đường tối ưu mờ như thuật toán FSA, thuật  toán  tìm  đường  đi  ngắn  nhất  trên  cơ  sở  số  mờ,  thuật  toán  Dijkstra  mờvà  ứng  dụng trong hệ thống thông tin địa lý.  - Cài đặt thử  nghiệm thuật  toán  tìm  đường  đi  tối ưu sử  dụng  logíc mờ  và đánh  giá.  Chính vì vậy, đối tượng của luận văn là: Bài toán tìm đường đi tối ưu trong GIS  sử dụng logic mờ. Luận văn sẽ khảo sát và đánh giá một số thuật toán tìm đường đi tối  ưu mờ ứng dụng trong GIS đã được đề xuất. Lựa chọn thuật toán phù hợp nhất để áp  dụng cho bài toán thiết kế tuyến xe BUS cho thành phố Thái Nguyên.  4. Phương pháp luận nghiên cứu - Phương pháp nghiên cứu lý thuyết: Tổng  hợp,  nghiên  cứu  các  tài  liệu  thuật  toán  tìm  đường  đi  tối  ưu  mờ,  tập  trung  sâu  vào  các  ứng  dụng  của  thuật  toán  trong GIS; Tìm hiểu các kiến thức liên quan.  - Phương pháp nghiên cứu thực nghiệm:  Sau  khi  nghiên  cứu  lý  thuyết,  phát  biểu bài toánthiết kế tuyến xe BUS và đưa ra giải pháp xử lý, luận văn sẽ tập  trung  vào  thu  thập  dữ  liệu  GIS  về  thành  phố  Thái  nguyên;  Mô  phỏng  thử  nghiệm chương trình phần mềm; Đánh giá các kết quả đạt được.  - Phương pháp trao đổi khoa học: Thảo luận, xemina, lấy ý kiến chuyên gia.      3          5. Nội dung và bố cục của luận văn Chương 1: Tổng quan về Hệ thông tin địa lý (GIS) và logic mờ - Nghiên  cứu  về  các  vấn  đề  cơ  bản  của  hệ  thông  tin  địa  lý,  bao  gồm,  các  khái  niệm  cơ  bản, kiến  trúc hệ  thống  GIS, biểu  diễn dữ liệu GIS theo  mô hình  dữ  liệu véc tơ và mô hình dữ liệu raster, các phép toán phân tích không gian trong  hệ GIS, cuối cùng là khả năng ứng dụng của GIS.  - Nghiên cứu các vấn đề cơ bản của logíc mờ và hệ mờ, bao gồm, các khái niệm  cơ bản, tập mờ và các hàm thuộc, các phép toán logíc mờ, hệ suy diễn mờ  Chương 2. Thuật toán đường đi mờ trong GIS - Nghiên cứu về khả năng mở rộng Hệ thông tin địa lý truyền thống theo hướng  tiếp  cận  sử  dụng  logic  mờ.Nghiên  cứu  bài  toán  tìm  đường  đi  tối  ưu,  một  số  thuật toán tìm đường đi tối ưu kinh điển. Từ đó tạo cơ sở để phân tích một số  thuật toán tìm đường tối ưu mờ đã được công bố gần đây như thuật toán FSA,  thuật toán tìm đường đi ngắn nhất trên cơ sở số mờ,thuật toán Dijkstra mờ.  Chương 3. Xây dựng chương trình thử nghiệm thiết kế tuyến xe BUS cho thành phố Thái nguyên - Phát biểu bài toán thiết kế tuyến xe BUS cho thành phố Thái Nguyên  - Thu thập dữ liệu thử nghiệm: dữ liệu GIS về thành phố Thái Nguyên   - Lựa chọn thuật toán Dijkstra mờ cho việc giải quyết bài toán  - Phân  tích  thiết  kế  chương  trình  thử  nghiệm,  phát  triển  chương  trình  thử  nghiệmvà đánh giá kết quả thu được.      4        CHƯƠNG 1 TỔNG QUAN VỀ HỆ THỐNG ĐỊA LÝ VÀ LOGIC MỜ Với định hướng:Nghiên cứu một số thuật toán tìm đường đi trong GIS ứng dụng logic mờ, nội chương này sẽ cung cấp các kiến thức cơ sở nền tảng, tạo điều kiện thuận lợi  cho việc phân tích các thuật toán cũng như triển khai ứng dụng trong các chương kế  tiếp. Phần đầu chương sẽ trình bày tổng quan về GIS bao gồm các định nghĩa về GIS,  cách thức biểu diễn dữ liệu, mô hình biểu diễn dữ liệu GIS trên máy tính, một số bài  toán phân tích và xử lý dữ liệu thường gặp trên GIS (đặc biệt là bài toán chồng phủ  bản đồ), các ứng dụng của GIS trong thực tế. Phần sau của chương tổng kết các kiến  thức  cơ  sở  về logic mờ  như: các khái  niệm  về hàm  thuộc, biến ngôn  ngữ, các  phép  toán trên tập mờ, số mờ, các hệ mờ trong thực tế.  1.1 Hệ thống thông tin địa lý (GIS) 1.1.1 Định nghĩa về hệ thông tin địa lý Theo[1] [12] , GIS là hệ thống phần cứng, phần mềm và các thủ tục được thiết  kế để thu thập, quản lý, xử lý, phân tích, mô hình hóa và hiển thị các dữ liệu qui chiếu  không gian để giải quyết các vấn đề quản lý và lập kế hoạch phức tạp.   Một cách đơn giản, có thể hiểu GIS như một sự kết hợp giữa bản đồ (map) và  cơ sở dữ liệu (database).  GIS = Bản đồ + Cơ sở dữ liệu Ở đây, bản đồ là hình thu nhỏ tương đối chính xác về một khu vực hay cả Trái  Đất, là bản vẽ đơn giản miêu tả một không gian, địa điểm và hiển thị những thông tin  liên quan trực tiếp đến vị trí ấy có liên quan đến khu vực xung quanh.  Bản đồ trong GIS là  một công cụ hữu ích cho phép chỉ ra vị trí của từng địa  điểm. Với sự kết hợp giữa bản đồ và cơ sở dữ liệu, người dùng có thể xem thông tin  chi tiết về từng đối tượng/thành phần tương ứng với địa điểm trên bản đồ thông qua  các dữ liệu đã được lưu trữ trong cơ sở dữ liệu. Ví dụ, khi xem bản đồ về các thành  phố, người dùng có thể chọn để xem thông tin về thành phố đó như diện tích, số dân,  thu nhập bình quân, số quận/huyện của thành phố, …  5        Độ phức tạp của thế giới thực là không gian hữu hạn. Càng quan sát thế giới  gần hơn càng thấy được chi tiết hơn. Con người mong mỏi lưu trữ, quản lý đầy đủ các  dữ liệu về thế giới thực. Điều này dẫn đến yêu cầu phải có cơ sở dữ liệu lớn vô hạn để  lưu trữ mọi thông tin chính xác về chúng. Do vậy, để lưu trữ được dữ liệu không gian  của thế giới thực vào máy tính thì phải giảm số lượng dữ liệu đến mức có thể quản lý  được bằng tiến trình đơn giản hoá hay trừu tượng hoá (Hình 1.1). Trừu tượng là đơn  giản hoá một cách thông minh. Trừu tượng cho ta tổng quát hoá và “ý tưởng” hoá vấn  đề đang xem xét. Chúng loại bỏ đi các chi tiết dư thừa mà chỉ tập trung vào các điểm  chính, cơ bản. Các đặc trưng địa lý phải được biểu diễn bởi các thành phần rời rạc hay  các đối tượng để lưu vào CSDL máy tính.    Hình 1-1 Hệ thống thông tin địa lý[3] GIS lưu trữ thông tin thế giới thực thành các tầng (layer) bản đồ chuyên đề mà  chúng có khả năng liên kết địa lý với nhau. Giả sử ta có vùng quan sát  như trên Hình  1-2.    Hình 1-2Tầng (layer) bản đồ[3] Mỗi nhóm người sử  dụng sẽ quan tâm  đến một hay là vài loại thông tin. Thí  dụ, Sở giao thông công chính sẽ quan tâm nhiều đến hệ thống đường phố. Sở nhà đất  6        quan tâm nhiều đến các khu dân cư và công sở. Sở thương mại quan tâm nhiều đến  phân bổ khách hàng trong vùng. Tư tưởng tách bản đồ thành tầng tuy đơn giản nhưng  khá mềm dẻo và hiệu quả, chúng có khả năng giải quyết rất nhiều vấn đề về thế giới  thực, từ theo dõi điều hành xe cộ giao thông, đến các ứng dụng lập kế hoạch và mô  hình  hoá  lưu  thông.  Ta  có  thể  sử  dụng  tiến  trình  tự  động,  gọi  là  mã  hoá  địa  lý  (geocoding) để liên kết dữ liệu bên ngoài với dữ liệu bản đồ. Thí dụ sử dụng mã hoá  địa lý để ánh xạ thông tin bán hàng bằng mã bưu điện (ZIP) hay chỉ ra địa chỉ khách  hàng trên bản đồ bằng các điểm.  1.1.2 Biểu diễn dữ liệu địa lý 1.1.2.1Các thành phần của dữ liệu địa lý   Trong  GIS,  dữ  liệu  được  chia  làm  hai  loại:  thành  phần  không  gian  và  thành  phần phi không gian (thuộc tính). Hai loại thành phần dữ liệu này được kết hợp thông  qua một chỉ số chung để mô tả một đối tượng thực. Sự kết hợp này thể hiện đặc trưng  không gian của đối tượng, nó cho phép:  - Mô tả “vị trí, hình dạng”: vị trí tham chiếu, đơn vị đo, dạng hình học của thực  thể địa lý.  - Mô tả “quan hệ và tương tác” giữa các thực thể địa lý. Ví dụ những thửa đất  nào liền kề với khu công nghiệp?  - Mô tả “thông tin” của các đối tượng địa lý: ai là chủ sở hữu của thửa đất này?  a. Thành phần không gian 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 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ả  7        chính xác các đối tượng trong không gian. Hệ thống GIS sử dụng các dữ liệu cơ sở  sau để mô tả hay thể hiện các đối tượng[7] :   Ð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-3là 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-3Ví dụ biểu diễn vị trí nước bị ô nhiễm[1]  Ðường – Cung (Line - Arc) Đường được xác định bởi dãy các điểm hoặc bởi 2 điểm đầu và cuối (Hình 1-4).  Đường dùng để mô tả các đối tượng địa lý  dạng tuyến như đường giao thông, sông  ngòi, tuyến cấp điện, cấp nước…  Các  đối  tượng  được  biểu  diễn  bằng  kiểu đường thường  mang  đặc  điểm là có  dãy  các  cặp  tọa  độ,  các  đường  bắt  đầu  và  kết  thúc  hoặc  cắt  nhau  bởi  điểm,  độ  dài  8        đường bằng chính khoảng cách của các điểm. Ví dụ, bản đồ hệ thống đường bộ, sông,  đường biên giới hành  chính, … thường được biểu diễn bởi đường và trên đường có  các điểm (vertex) để xác định vị trí và hình dáng của đường đó.    Hình 1-4Ví dụ biểu diễn đường[1]  Vùng (Polygon) Vùng được xác định bởi ranh giới các đường, có điểm đầu trùng với điểm cuối.  Các  đối  tượng  địa  lý  có  diện  tích  và  được  bao  quanh  bởi  đường  thường  được  biểu  diễn bởi vùng.    Hình 1-5Ví dụ biểu diễn khu vực hành chính[1] Các  đối  tượng  biểu  diễn  bởi  vùng  có  đặc  điểm  là  được  mô  tả  bằng  tập  các  đường bao quanh vùng và điểm nhãn (label point) thuộc vùng để mô tả, xác định cho  9        mỗi vùng. Ví dụ, các khu vực hành chính, hình dạng các công viên, … được mô tả bởi  kiểu dữ liệu vùng. Hình 1-5 mô tả ví dụ cách lưu trữ một đối tượng vùng.   Lưới (Grid) Được mô tả một dãy các ô đều nhau mỗi mắt lưới cách nhau một khoảng cách  nhất định. Các ô ưới có kích thước có thể chia theo mét (kích thước thường 1000 m x  1000 m). Lưới chia theo độ có thể có kích thước (1 độ x 1 độ, 0.5 độ x 0.5 độ). Lưới  phẳng có thể chia theo km hoặc m có thể chia theo kích thước (1 km x 1 km, 100 m x  100 m)...    Lớp (Class - Layer) Là  một  nhóm  các  đối  ượng  có  cùng  tính  chất  được  tổ  chức  cùng  với  nhau  chẳng hạn: Lớp các đường quốc lộ, đường tỉnh lộ, lớp thông tin thuỷ văn, lớp thông  tin hành chính, lớp các thông tin về dân số, ớp thông tin về rừng, lớp thông tin về cầu  phà, lớp thông tin về đường sắt.   Ngoài các đối tượng nêu trên một số các hệ GIS còn có thêm một số các đối  tượng đặc biệt khác như cung, hình tròn, hình chữ nhật, text...để tạo ra các bản đồ có  tính thẩm mỹ cao. Tuy nhiên các phép phân tích và chồng xếp bản đồ người ta thường  quan tâm tới ba dạng đối tượng đặc trưng nhất: điểm, đường, vùng. Một đối tượng có  thể biểu  diễn bởi  các  kiểu  khác  nhau  tùy  thuộc vào  tỷ  lệ của  bản  đồ đó.  Ví dụ,  đối  tượng  công  viên  có  thể  được  biểu  diễn  bởi  điểm  trong  bản  đồ  có  tỷ  lệ  nhỏ,  và  bởi  vùng trong bản đồ có tỷ lệ lớn.   b. Thành phần phi không gian Thành phần dữ liệu phi không gian hay còn gọi là dữ liệu thuộc tính, là những  diễn tả đặc tính, số lượng, mối quan hệ của các hình ảnh bản đồ với vị trí địa lý của  chúng thông qua một cơ chế thống nhất. Hệ thống GIS có cơ chế liên kết dữ liệu không  gian và  phi  không gian của  cùng  một  đối  tượng  với  nhau.  Có  thể  nói,  một trong những  chức năng đặc biệt của công nghệ GIS chính là khả năng liên kết và xử lý đồng thời dữ liệu  bản đồ và dữ liệu thuộc tính.   Dữ liệu thuộc tính trong hệ thống GIS bất kỳ thường phân thành 4 loại sau:   10        - Bộ xác định: có thể là một số duy nhất, liên tục, ngẫu nhiên hoặc chỉ báo địa lý,  số liệu xác định vị trí lưu trữ chung. Bộ xác định cho một thực thể chứa tọa độ  phân bố của nó, số hiệu mảnh bản đồ, mô tả khu vực hay con trỏ đến vị trí lưu  trữ của số liệu liên quan. Bộ xác định thường lưu trữ với các bản ghi tọa độ hay  mô tả khác của hình ảnh không gian và các bản ghi số liệu thuộc tính liên quan.   - Số liệu hiện tượng, tham khảo địa lý:  miêu  tả  thông  tin  danh  mục,  các  hoạt  động liên quan đến các vị trí địa lý xác định (ví dụ như: cho phép xây dựng,  báo  cáo  tai  nạn,  nghiên  cứu  y  tế,…)  Thông  tin  này  được  lưu  trữ  và  quản  lý  trong các tệp/ bảng độc lập, trong đó mỗi bản ghi chứa yếu tố xác định vị trí  của sự kiện hay hiện tượng quản lý.  - Chỉ số địa lý: bao gồm tên, địa chỉ, khối, phương hướng định vị, … liên quan  đến  các  đối  tượng  địa  lý.  Một  chỉ  số  có  thể  bao  gồm  nhiều  bộ  xác  định  cho  thực thể địa lý. Ví dụ: chỉ số địa lý về đường phố và địa chỉ địa lý liên quan  đến phố đó.  - Quan hệ giữa các đối tượng tại một vị trí địa lý cụ thể trong không gian. Đây  là thông tin quan trọng cho các chức năng xử lý của hệ thống thông tin địa lý.  Các mối quan hệ không gian có thể là mối quan hệ đơn giản hay logic, ví dụ  tiếp theo số nhà 101 phải là số nhà 103.   1.1.2.2 Mô hình biểu diễn dữ liệu không gian Hệ  thống  thông tin địa  lý  làm  việc  với  hai dạng  mô  hình dữ liệu  địa lý  khác  nhau về cơ bản là mô hình vector và mô hình raster.   Mô hình vector sử dụng tọa độ 2 chiều (x, y) để lưu trữ hình khối của các thực  thể không gian trên bản đồ 2D. Mô hình này sử dụng các đặc tính rời rạc như điểm,  đường, vùng để mô tả không gian, đồng thời cấu trúc topo của các đối tượng cũng cần  được mô tả chính xác và lưu trữ trong hệ thống.   Mô hình raster hay còn gọi mô hình dạng ảnh (image) biểu diễn các đặc tính dữ  liệu bởi ma trận các ô (cell) trong không gian liên tục (Hình 1-6). Mỗi ô có chỉ số tọa  độ (coordinate) và các thuộc tính liên quan. Mỗi vùng được chia thành các hàng và  cột, mỗi ô có thể là hình vuông hoặc hình chữ nhật và chỉ có duy nhất một giá trị.  11          Hình 1-6 Biểu diễn thế giới bằng mô hình vectơ và raster Cả mô hình vector và raster đều được dùng để lưu dữ liệu địa lý với những ưu  điểm, nhược điểm riêng. Các hệ GIS hiện đại có khả năng quản lý cả hai mô hình này.  Bảng 1.1 so sánh giữa hai mô hình dữ liệu Vector và Raster:   Bảng 1.1So sánh mô hình dữ liệu Vector và Raster. Mô hình Vector   Mô hình Raster   Ưu điểm   Ưu điểm   - Độ chính xác cao   - Cấu trúc dữ liệu đơn giản   - Cấu  trúc  dữ  liệu  dạng  nén  mất  ít  - Hiệu quả trong tính toán   dung lượng để lưu trữ   - Các phép toán chồng xếp xử lý dễ dàng   - Cho  phép  các  quan  hệ  hình  học  - Thích hợp cho việc thể hiện dữ liệu phức  (topological)  như  tính  liền  kê,  liên  tạp, đa dạng   thông.   - Thích hợp cho việc nâng cấp, xử lý ảnh   - Gần gũi với thao tác vẽ bằng tay của  con người.   12