Tài liệu Nghiên cứu vài thuật toán song song ứng dụng trong GIS

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ BÙI ANH TÚ NGHIÊN CỨU MỘT SỐ THUẬT TOÁN SONG SONG ỨNG DỤNG TRONG GIS LUẬN VĂN THẠC SĨ Hà Nội - 2011 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ BÙI ANH TÚ NGHIÊN CỨU MỘT SỐ THUẬT TOÁN SONG SONG ỨNG DỤNG TRONG GIS Ngành: Công nghệ thông tin Chuyên ngành: Công nghệ phần mềm Mã số: 1.01.10 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. Đăng Văn Đức Hà Nội - 2011 LỜI MỞ ĐẦU ................................................................... 1 CHƯƠNG 1: KHÁI QUÁT VỀ GIS VÀ XỬ LÝ SONG SONG ................................................................................ 3 1.1 Hệ thống thông tin địa lý GIS .......................................................................3 1.1.1. Lịch sử ra đời .......................................................................................3 1.1.2. Định nghĩa GIS .....................................................................................5 1.1.3. Các thành phần GIS ..............................................................................5 1.1.4. Tổng quan các chức năng của hệ thống thông tin địa lý ........................9 1.1.5 Các ứng dụng phổ biến của GIS........................................................... 16 1.2. Tổng quan về xử lý song song ................................................................... 20 1.2.1. Tại sao phải xử lý song song ............................................................... 20 1.2.2. Phân biệt xử lý song song ................................................................... 20 1.2.3. Mục đích của xử lý song song ............................................................. 21 1.2.4. Kiến trúc máy tính .............................................................................. 21 1.2.4.1. Kiến trúc máy tính kiểu Voneument ................................................ 21 1.2.4.2. Phân loại máy tính song song ........................................................... 22 1.2.4.3. Song song hoá trong máy tính tuần tự .............................................. 25 1.2.4.4. Một số vấn đề cần quan tâm trong kiến trúc MTSS .......................... 27 CHƯƠNG 2: MỘT SỐ THUẬT TOÁN XỬ LÝ SONG SONG ỨNG DỤNG TRONG GIS................................. 29 2.1. Tại sao lại áp dụng xử lý song song trong GIS .......................................... 29 2.1.1. Ý nghĩa thực tiễn của xử lý song song ................................................ 29 2.1.2. Đặc điểm riêng của GIS ...................................................................... 29 78 2.2. Xây dựng thuật toán xử lý song song ứng dụng trong GIS ........................ 30 2.2.1. Nguyên lý thiết kế thuật toán song song(TTSS) .................................. 30 2.2.2. Các cách tiếp cận thiết giải thuật song song và đánh giá giải thuật song song.............................................................................................................. 32 2.3. Xây dựng một số thuật toán song song áp dụng trong GIS ........................ 33 2.3.1. Thuật toán sắp xếp song song bitonic.................................................. 33 2.3.3. Tìm kiếm đường đi ngắn nhất ứng dụng trong GIS ............................. 53 2.3.4. Xây dựng thuật toán tìm kiếm dữ liệu song song ................................ 58 2.3.5. Thuật toán sắp xếp Quicksort song song ............................................. 62 CHƯƠNG 3: PHÁT TRIỂN CHƯƠNG TRÌNH THỬ NGHIỆM THUẬT TOÁN SONG SONG TRONG GIS65 3.1. Thực nghiệm áp dụng xử lý song song trong GIS và Bản đồ số ................. 65 3.1.1. Thực nghiệm áp dụng thuật toán Bitonic trong việc sắp xếp dữ liệu đầu vào ............................................................................................................... 65 3.1.2. Thực nghiệm với tìm kiếm dữ liệu thô ................................................ 66 3.1.3. Thực nghiệm sắp xếp lại dữ liệu song song ......................................... 68 3.1.3. Thực nghiệm tìm kiếm dữ liệu sau khi đã tổ chức lại dữ liệu .............. 69 3.1.4. Thực nghiệm tìm đường đi ngắn nhất từ 1 đỉnh đến tất cả các đỉnh ..... 70 3.2. Xây dựng Bản đồ số áp dụng..................................................................... 72 3.3. Một số hình ảnh chương trình ................................................................... 74 KẾT LUẬN ..................................................................... 76 TÀI LIỆU THAM KHẢO.............................................. 77 79 LỜI MỞ ĐẦU Một trong những nghành phát triển rất mạnh mẽ hiện nay phải kể đến đó là ngành Công nghệ Thông tin, một trong những ngành mũi nhọn của nhiều quốc gia trên thế giới. Sự phát triển không ngừng của công nghệ thông tin mang lại hiệu quả cao cho con người, đồng thời cũng giúp chính bản thân nghành công nghệ thông tin phát triển, sự phát triển cả về phần cứng cũng như các phần mềm tiện ích kèm theo. Sự phát triển đó đã kéo theo rất nhiều các ngành khác phát triền theo, trong đó có lĩnh vực nghiên cứu khoa học. Tuy công nghệ ngày càng phát triển, tốc độ xử lý của các thiết bị cũng không ngừng tăng cao, nhưng nhu cầu tính toán của con người vẫn còn rất lớn. Cho đến hiện nay vẫn còn rất nhiều vấn đề mà các nhà khoa học cùng với khả năng tính toán của các máy tính hiện nay vẫn chưa giải quyết được hay giải quyết được nhưng với thời gian rất lớn. Các vấn đề đó có thể là : - Mô hình hóa và giả lập. - Xử lý thao tác trên các dữ liệu rất lớn. - Các vấn đề “grand challenge” (các vấn đề không thể giải quyết trong thời gian hợp lý). Lời giải cho những vấn đề này đã dẫn đến sự ra đời của các thế hệ siêu máy tính. Tuy nhiên việc đầu tư phát triển cho các thiết bị này gần như là điều quá khó khăn đối với nhiều người, tổ chức, trường học…. Chính vì lẽ đó mà ngày nay người ta đang tập trung nghiên cứu cách cách sử dụng các tài nguyên phân bố một cách hợp lý để tận dụng được khả năng tính toán của các máy tính đơn. Những giải pháp này được biết đến với nhiều tên gọi khác nhau như parallel computing, meta-computing, salable-computing, globalcomputing, Internet computing và gần nhất hiện nay là peer to peer computing hay Grid computing. Đây là phương pháp nhằm tận dụng khả năng của các máy tính trên toàn mạng thành một máy tính “ảo” duy nhất, nhằm hợp nhất tài nguyên tính toán ở nhiều nơi trên thế giới để tạo ra một khả năng tính toán khổng lồ, góp phần 1 giải quyết các vấn đề khó khăn trong khoa học và công nghệ. Ngày nay nó đang càng được sự hỗ trợ mạnh hơn của các thiết bị phần cứng, băng thông… Xử lý song song được quan tâm đầu tư rất lớn hiện nay kể cả phần cứng cũng như phần mềm. Chính vì vậy việc áp dụng xử lý song song trong các nghành, các lĩnh vực cũng phát triển rộng rãi, đem lại hiệu quả cao. Hệ thống thông tin địa lý GIS được hình thành vào những năm 1960 và phát triển rất rộng rãi trong 10 năm lại đây. GIS ngày nay là công cụ trợ giúp quyết định trong nhiều hoạt động kinh tế - xã hội, quốc phòng của nhiều quốc gia trên thế giới. GIS có khả năng trợ giúp các cơ quan chính phủ, các nhà quản lý, các doanh nghiệp, các cá nhân... đánh giá được hiện trạng của các quá trình, các thực thể tự nhiên, kinh tế -xã hội thông qua các chức năng thu thập, quản lý, truy vấn, phân tích và tích hợp các thông tin được gắn với một nền hình học (bản đồ) nhất quán trên cơ sở toạ độ của các dữ liệu đầu vào. Với ý nghĩa sâu rộng của GIS thì việc làm thế nào áp dụng cho tốt, ứng dụng sao đem lại hiệu quả cao là một vấn đề cần lưu tâm. Mục tiêu của luận văn là tìm hiểu về xử lý song song, và qua đó vận dụng các kiến thức có được để đưa ra giải pháp, ứng dụng tính toán song song vào việc xử lý thông tin trong GIS, nhằm giải quyết các vấn đề về thời gian, hiệu quả xử lý hệ thống GIS khi dữ liệu đầu vào là tương đối lớn. Luận văn bao gồm 3 chương: Chương 1: Khái quát về GIS và xử lý song song. Chương 2: Một số thuật toán song song ứng dụng trong GIS. Chương 3: Phát triển chương trình thử nghiệm thuật toán song song trong GIS. 2 CHƢƠNG 1: KHÁI QUÁT VỀ GIS VÀ XỬ LÝ SONG SONG 1.1 Hệ thống thông tin địa lý GIS Hệ thống thông tin Địa lý (GIS: Geograpgic Information System) đã được sử dụng rộng rãi ở các nước phát triển, đây là một dạng ứng dụng công nghệ tin nhằm mô tả thế giới thực mà chúng ta đang sống, khám phá và khai thác. Với những tính năng ưu việt của nó mà các hệ thống thông tin khác không có được như công nghệ GIS kết hợp các thao tác cơ sở dữ liệu thông thường và các phép phân tích thống kê, phân tích dữ liệu không gian và thuộc tính. Những khả năng này phân biệt GIS với các hệ thống thông tin khác và khiến cho GIS ngày nay đang được ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau trong nghiên cứu và quản lý (phân tích các sự kiện, dự đoán tác động và hoạch định chiến lược), đặc biệt trong lĩnh vực phát triển nông thôn nhằm quản lý và quy hoạch sử dụng và khai thác các nguồn tài nguyên thiên nhiên một cách có hiệu quả, bền vững và hợp lý. Hệ thống thông tin địa lý GIS có rất nhiều ứng dụng, nếu con người biết sử dụng và khai thác tiềm năng rộng lớn của nó thì GIS sẽ như lắp thêm đôi mắt, đôi tay, đôi cánh giúp con người nhìn thế giới trực quan hơn, chính xác hơn và nhanh chóng chinh phục được thế giới trong tiềm năng vốn có của mình. 1.1.1. Lịch sử ra đời Từ xa xưa con người đã biết cách biểu diễn các thông tin địa lý bằng cách thu nhỏ các sự vật theo một kích thước nào đó, rồi vẽ lên mặt phẳng. Để đánh dấu các đặc tính của sự vật, người ta dùng các loại ký hiệu khác nhau như độ cao được biểu diễn bằng những đường bình độ, một số đối tượng được biểu thị bởi các loại màu sắc tương ứng hoặc bằng chú thích cùng các số hiệu đi kèm. Sự biểu thị kết quả thể hiện các ý tưởng đó được gọi là bản đồ. Trên cơ sở của hệ thông tin bản đồ, những năm đầu của thập kỷ 60(1963-1964) các nhà khoa học Canada đã cho ra đời hệ thống thông tin địa lý hay còn gọi là GIS 3 (Geographical Information Systems - GIS). GIS kế thừa mọi thành tựu trong ngành bản đồ cả về ý tưởng lẫn thành tựu của kỹ thuật bản đồ. GIS bắt đầu hoạt động cũng bằng việc thu thập dữ liệu theo định hướng tuỳ thuộc vào muc tiêu đặt ra. Hệ thông tin đia lý (GIS) có thể hiểu một cách đơn giản là tập hợp các thông tin có liên quan đến các yếu tố địa lý một cách đồng bộ và logic. Trong những năm 70 ở Bắc Mỹ đã có sự quan tâm nhiều hơn đến việc bảo vệ môi trường và phát triển GIS. Thời kỳ này hàng loạt thay đổi một cách thuận lợi cho sự phát triển của GIS, đặc biệt là sự gia tăng ứng dụng của máy tính với kích thước bộ nhớ và tốc độ tăng. Chính những thuận lợi này mà GIS dần dần được thương mại hoá. Năm 1977 đã có nhiều hệ thông tin địa lý khác nhau trên thế giới. Bên cạnh GIS thời kỳ này còn phát triển mạnh mẽ các kỹ thuật xử lý ảnh viễn thám. Một hướng nghiên cứu kết hợp giữa GIS và viễn thám được đặt ra. Thập kỷ 80 được đánh dấu bởi các nhu cầu sử dụng GIS ngày càng tăng với các quy mô khác nhau. Người ta tiếp tục giải quyết những tồn tại của những năm trước mà nổi lên là vấn đề số hoá dữ liệu. Thập kỷ này đánh dấu bởi sự nảy sinh các nhu cầu mới trong ứng dụng GIS như: theo dõi sử dụng tối ưu các nguồn tài nguyên, đánh giá khả thi các phương án quy hoạch, các bài toán giao thông… GIS trở thành một công cụ hữu hiệu trong công tác quản lý và trợ giúp quyết định. Những năm đầu của thập kỷ 90 được đánh dấu bằng việc nghiên cứu hoà nhập giữa viễn thám và GIS. Các nước Bắc Mỹ và châu Âu thu được nhiều thành công trong lĩnh vực này. Khu vực châu Á Thái Bình Dương cũng đã thành lập nhiều trung tâm nghiên cứu viễn thám và GIS. Ở các nước như Trung Quốc, Nhật Bản, Thái Lan… đã chú ý nghiên cứu đến GIS chủ yếu vào lĩnh vực quản lý, đánh giá tài nguyên thiên nhiên và môi trường. Ở Việt Nam việc nghiên cứu và ứng dụng hệ thông tin địa lý cũng mới chỉ bắt đầu, và chỉ được triển khai ở những cơ quan lớn như tổng cục địa chính, trường Đại học mỏ Địa chất, Viện Điều tra quy hoạch rừng, Viện địa chất…Đồng thời mức độ ứng dụng còn hạn chế, và mới chỉ có ý nghĩa nghiên cứu hoặc ứng dụng để giải quyết một số các nhiệm vụ trước mắt. 4 Như vậy hầu hết các nước trên thế giới trong đó có Việt nam đều quan tâm nghiên cứu hệ thông tin địa lý và ứng dụng nó vào nhiều ngành, trong đó có ngành Lâm nghiệp. Ngày nay, phần mềm GIS đang hướng tới đưa công nghệ GIS trở thành hệ tự động thành lập bản đồ và xử lý dữ liệu ngày càng đạt hiệu quả cao về tốc độ và độ chính xác. 1.1.2. Định nghĩa GIS Hiện nay có rất nhiều định nghĩa về GIS, nhưng chúng đều có điểm giống nhau như: bao hàm khái niệm dữ liệu không gian, phân biệt giữa hệ thông tin quản lý (Management Information System - MIS) và GIS. Về khía cạnh của bản đồ học thì GIS là kết hợp của lập bản đồ trợ giúp máy tính và công nghệ cơ sở dữ liệu (CSDL). So với bản đồ thì GIS có lợi thế là lưu trữ dữ liệu và biểu diễn chúng là hai công việc tách biệt nhau. Do vậy GIS cho khả năng quan sát từ các góc độ khác nhau trên cùng tập dữ liệu. GIS là một bộ công cụ đầy sức mạnh để tuyển chọn, lưu trữ, phục hồi, chuyển đổi và hiển thị số liệu không gian từ thế giới thực đáp ứng cho một số mục đích cụ thể Nhận xét GIS:  GIS liên quan đến cơ sở dữ liệu: Tất cả các thông tin trong một GIS được liên kết với nhau.  Kỹ thuật hợp nhất GIS: Phân tích không ảnh, ảnh Vệ tinh, tạo ra mô hình hoặc là làm ra các bản đồ chuyên đề.  GIS như là một bộ sử lý cơ sở dữ liệu. 1.1.3. Các thành phần GIS Hệ thống GIS có năm thành tố chính bao gồm: con người, phương pháp, phần cứng tin học, phần mềm tin học và dữ liệu. Tầm quan trọng của mỗi thành tố và các quan hệ giữa chúng được trình bày chi tiết trong các phần tiếp theo đây. 5 Hình 1.1 Các thành phần hệ thống GIS 1.1.3.1. Con ngƣời Con người là chuyên viên tin học, các chuyên gia về các lĩnh vực khác nhau, chuyên gia GIS, thao tác viên GIS, phát triển ứng dụng GIS. Người sử dụng hệ thống (system user) là những người sử dụng GIS để giải quyết các vấn đề không gian. Họ thường là những người được đào tạo tốt về lĩnh vực GIS hay GIS chuyên dụng. Nhiệm vụ chủ yếu của họ là số hóa bản đồ, kiểm tra lỗi, soạn thảo, phân tích các dữ liệu thô và đưa ra các giải pháp cuối cùng để truy vấn dữ liệu địa lý. Thao tác viên hệ thống (system operator) có trách nhiệm vận hành hệ thống hàng ngày để người sử dụng hệ thống làm việc hiệu quả. Công việc của họ là sửa chữa khi chương trình bị tắc ngẽn hay là công việc trợ giúp nhân viên thực hiện các phân tích có độ phức tạp cao. Nhà cung cấp GIS (GIS supplier) có trách nhiệm cung cấp phần mềm, cập nhật phần mềm, phương pháp nâng cấp cho hệ thống. Đôi khi tham gia huấn luyện người dùng GIS thông qua các hợp đồng với quản trị hệ thống. Nhà cung cấp dữ liệu (data supplier) có thể là tổ chức Nhà nước hay tư nhân. Thông thường các công ty tư nhân cung cấp dữ liệu sửa đổi từ dữ liệu các cơ quan Nhà nước để cho phù hợp với ứng dụng cụ thể. Thông thường các cơ quan Nhà 6 nước cung cấp dữ liệu được xây dựng cho chính nhu cầu của họ, nhưng dữ liệu này có thể được sử dụng trong các cơ quan, tổ chức khác. Một số dữ liệu này được bán với giá rẻ hay cho không tới các dự án GIS phi lợi nhuận. Người phát triển ứng dụng (application developer) là những lập trình viên được đào tạo. Họ xây dựng các giao diện người dùng, làm giảm khó khăn khi thực hiện các thao tác cụ thể trên các hệ thống GIS chuyên nghiệp. Hình 1.2 Quản lý dự án GIS Chuyên viên phân tích hệ thống GIS (GIS systems analysts) là nhóm người chuyên nghiên cứu thiết kế hệ thống. Phần lớn họ là đội ngũ chuyên nghiệp, có trách nhiệm xác định mục tiêu của hệ GIS trong cơ quan, hiệu chỉnh hệ thống, đề xuất kỹ thuật phân tích đúng đắn, đảm bảo tích hợp thắng lợi hệ thống trong cơ quan. 1.1.3.2. Dữ liệu Với bất kỳ hệ thông tin nào cũng phải hiểu rõ các loại dữ liệu khác nhau lưu trữ trong chúng. Dữ liệu (các biến) thống kê gắn theo các hiện tượng tự nhiên với mức độ chính xác khác nhau. Hệ thống thước đo của chúng bao gồm các biến tên, số thứ tự, khoảng và tỷ lệ. Mỗi hệ GIS cần phải hiểu được dữ liệu trong các khuôn mẫu khác nhau, không chỉ hiểu khuôn mẫu dữ liệu riêng của hệ thống. Thí dụ, đường biên bản đồ có thể trong khuôn mẫu tệp DXF của AutoCAD hay BNA của AtlasGIS. Thông thường, GIS hiểu ngay khuôn mẫu DXF mà không cần sửa đổi nào. Tương tự, GIS 7 phải hiểu ngay khuôn mẫu DBF của các thuộc tính được lưu trữ kèm theo. Lý tưởng thì phần mềm GIS phải có khả năng đọc các khuôn mẫu dữ liệu raster (DEN, GIFF, TIFF, JPEG, EPS) và khuôn mẫu vectơ (TIGER, HPGL, DXF, Postscript, DLG). Với dữ liệu ba chiều, phần lớn phần mềm GIS trợ giúp lưới tam giác không đều (TIN). Một số khác trợ giúp cấu trúc raster trên cơ sở lưới bao gồm cây tứ phân và khả năng chuyển đổi toàn bộ hay một phần dữ liệu vào cấu trúc này. Một vài phần mềm GIS chỉ trợ giúp khuôn mẫu riêng, chúng phụ thuộc vào nhà sản xuất phần mềm. 1.1.3.3. Công cụ phần mềm Một hệ thống GIS bao gồm nhiều môđun phần mềm. Khả năng lưu trữ, quản lý dữ liệu không gian bằng hệ quản trị CSDL địa lý là khía cạnh quan trọng nhất của GIS. Các môđun khác là công cụ phân tích dữ liệu, làm báo cáo và truyền tin. Hình 1.3 Phần mềm của GIS 1.1.3.4. Giao diện ngƣời dùng Giao diện đồ họa cho phép người dùng dễ dàng thực hiện các thao tác địa lý và các thao tác khác như truy nhập CSDL, làm báo cáo. 1.1.3.5. Phần cứng Ngày nay, có thể tìm thấy GIS trên mọi loại hình máy tính, từ máy tính cá nhân đến các trạm làm việc và máy tính đa người dùng. GIS đòi hỏi các thiết bị ngoại vi 8 đặc biệt như bàn số hóa, máy vẽ, máy quét ảnh để vào/ra dữ liệu. Các thiết bị này có thể được nối với nhau thông qua thiết bị truyền tin hay mạng cục bộ. Hình 1.4 Phần cứng GIS 1.1.4. Tổng quan các chức năng của hệ thống thông tin địa lý Phần này mô tả các khả năng của bộ chương trình GIS thương mại. Các chức năng của chúng được phân chia thành năm loại sau đây: - Thu thập dữ liệu. - Xử lý sơ bộ dữ liệu. - Lưu trữ và truy nhập dữ liệu. - Tìm kiếm và phân tích không gian. - Hiển thị đồ họa và tương tác. Sức mạnh của các chức năng của hệ thống GIS khác nhau là khác nhau. Kỹ thuật xây dựng các chức năng trên cũng rất khác nhau. Hình 1.5 mô tả quan hệ giữa các nhóm chức năng và cách biểu diễn thông tin khác nhau của GIS. Chức năng thu thập dữ liệu tạo ra dữ liệu từ các quan sát hiện tượng thế giới thực và từ các tài liệu, bản đồ giấy, đôi khi chúng có sẵn dưới dạng số. Kết quả ta có tập "dữ liệu thô", có nghĩa là dữ liệu này không được phép áp dụng trực tiếp cho chức năng truy nhập và phân tích của hệ thống. Chức năng xử lý sơ bộ dữ liệu sẽ biến đổi dữ liệu thô thành dữ liệu có cấu trúc để sử dụng trực tiếp các chức năng tìm kiếm và 9 phân tích không gian. Kết quả tìm kiếm và phân tích được xem như diễn giải dữ liệu, đó là tổ hợp hay biến đổi đặc biệt của dữ liệu có cấu trúc. Hệ thống GIS phải có phần mềm công cụ để tổ chức và lưu trữ các loại dữ liệu khác nhau, từ dữ liệu thô đến dữ liệu diễn giải. Phần mềm công cụ này phải có các thao tác lưu trữ, truy nhập; đồng thời có khả năng hiển thị, tương tác đồ họa với tất cả loại dữ liệu. Hình 1.5 Các nhóm chức năng trong GIS 1.1.4.1. Thu thập dữ liệu Thu thập dữ liệu là tiến trình thu nhận dữ liệu theo khuôn mẫu áp dụng được cho GIS. Mức độ đơn giản nhất của thu thập dữ liệu là chuyển đổi khuôn mẫu dữ liệu có sẵn từ các nguồn bên ngoài. Trong trường hợp này, GIS phải có môđun chương trình hiểu được các khuôn mẫu dữ liệu chuẩn khác nhau để trao đổi như DLG, DXF hay các dữ liệu là đầu ra của các hệ thống GIS khác như MapInfo, 10 Arc/Info... GIS còn phải có khả năng nhập các ảnh bản đồ trong các khuôn mẫu như TIFF, GIF... Thực tế, nhiều kỹ thuật trắc đạc được áp dụng để thu thập dữ liệu thô. Chúng bao gồm thu thập dữ liệu về bề mặt Trái đất như địa hình, địa chất học và thảm thực vật nhờ trắc đạc bằng vệ tinh và máy bay. Các dữ liệu kinh tế - xã hội thu thập từ điều tra, phỏng vấn hay chuyển đổi từ các tài liệu viết. Những bản đồ vẽ bằng tay trên giấy phải được số hóa. Việc sử dụng dữ liệu ảnh từ vệ tinh hay ảnh chụp từ máy bay được xem là nguồn dữ liệu quan trọng nhất khi nghiên cứu tài nguyên thiên nhiên và đo vẽ bản đồ địa hình. Phần lớn các ảnh vệ tinh sử dụng trong GIS có độ phân giải mặt đất từ 10-80m. Chúng đặc biệt hiệu quả khi nghiên cứu các biến môi trường như thảm cỏ hay hệ thống thủy lợi, nhưng chúng chỉ được ứng dụng cho bản đồ địa hình với tỷ lệ 1:50000 hay nhỏ hơn. Còn ảnh máy bay sẽ cho số liệu chính xác hơn và được áp dụng để lập bản đồ tỷ lệ lớn hơn, thí dụ tỷ lệ 1:500 hay 1:1000. Phần lớn nguồn gốc thông tin không gian là các bản đồ in hay bản đồ dưới khuôn mẫu tương tự. Để các dữ liệu này được sử dụng trong GIS thì phải số hóa chúng. Các công việc này có thể là số hóa thủ công các hình dạng đặc trưng bản đồ và nhập thuộc tính mô tả các đặc trưng đó. Cách tiếp cận với mức tự động hóa cao hơn là số hóa bản đồ bằng máy quét để phát sinh ra ảnh số bản đồ đầy đủ. Đầu ra của máy quét là ma trận của các giá trị điểm ảnh 2D, nó có thể được sử dụng cho công việc vectơ hóa để tạo ra bản đồ vectơ với các đặc trưng điểm, đường, vùng hay xâu ký tự. Trình tự số hóa bao gồm mã hóa dữ liệu, kiểm chứng và sửa lỗi để có được dữ liệu phù hợp với GIS. Nói chung, công đoạn thu thập dữ liệu không gian là nhiệm vụ khó khăn, nặng nề nhất trong quá trình xây dựng ứng dụng GIS. 1.1.4.2. Xử lý dữ liệu thô Hai khía cạnh chính của xử lý dữ liệu thô bao gồm: - Phát sinh dữ liệu có cấu trúc tôpô. - Trường hợp dữ liệu ảnh vệ tinh thì phải phân lớp các đặc trưng trong ảnh thành các hiện tượng quan tâm. 11 Mô hình quan niệm của thông tin không gian bao gồm mô hình hướng đối tượng, mạng và bề mặt. Quá trình phân tích trên cơ sở cách nhìn khác nhau đòi hỏi dữ liệu phải được biểu diễn và tổ chức cho phù hợp. Vì vậy, cần thiết cung cấp phương tiện cho người sử dụng GIS thay đổi cấu trúc dữ liệu để thích nghi với các yêu cầu khác nhau. Điều này đòi hỏi không chỉ chức năng tạo lập mô hình dữ liệu vectơ có cấu trúc tôpô và mô hình dữ liệu raster, mà còn có khả năng thay đổi cách biểu diễn, thay đổi phân lớp và sơ đồ mẫu, làm đơn giản hóa hay tổng quát hóa dữ liệu, biến đổi giữa hệ thống trục tọa độ khác nhau và biến đổi các phép chiếu bản đồ (hình 1.6). Các thao tác kể trên được xem như tiền thao tác cho phân tích không gian. Mức độ xử lý dữ liệu thô là khác nhau, phụ thuộc vào mục đích của ứng dụng GIS. 12 Hình 1.6 Xử lý dữ liệu thô Một số công cụ phân tích của GIS phụ thuộc chặt chẽ vào mô hình dữ liệu raster, do vậy nó đòi hỏi quá trình biến đổi mô hình dữ liệu vectơ sang dữ liệu raster, hay còn gọi là raster hóa (hình 1.6c). Biến đổi từ raster sang mô hình vectơ, hay còn gọi là vectơ hóa, đặc biệt cần thiết khi tự động quét ảnh (hình 1.6d). Raster hóa là tiến trình chia đường hay vùng thành các tế bào. Ngược lại, vectơ hóa là tập hợp các tế bào (pixel) để tạo thành đường hay vùng. Nếu dữ liệu raster không có cấu trúc tốt, thí dụ ảnh vệ tinh, thì việc nhận dạng mẫu sẽ rất phức tạp. Thủ tục biến đổi các đối tượng rời rạc trong khuôn mẫu vectơ sang các tế bào vuông của mô hình raster là rõ ràng, nhưng thủ tục biến đổi điểm dữ liệu có vị trí tùy ý thành lưới đều sẽ ít chính xác (hình 1.6e). Lấy mẫu lại các điểm phân tán không đều có thể thực hiện bằng các kỹ thuật nội suy. Có nghĩa là mô hình hóa dữ liệu 13 thống kê tại các vị trí không lấy mẫu thành hàm số của các điểm mẫu. Cách khác là xây dựng lưới tam giác không đều (TIN) (hình 1.6f). Khi so sánh dữ liệu từ các nguồn khác nhau, vấn đề chung nảy sinh là sử dụng hai hay nhiều phân lớp hay sơ đồ mã hóa cho cùng hiện tượng. Để nhận ra các khía cạnh khác nhau của hiện tượng với dữ liệu có mức độ chi tiết khác nhau, cần phải có tiến trình xấp xỉ hóa hay đơn giản hóa để biến đổi về cùng một sơ đồ. Cách mã hóa lại khá đơn giản, nó là tái phân lớp để tổ hợp một vài lớp thành lớp ít chi tiết hơn hay tổng quát hơn (hình 1.6g). Thí dụ, trên bản đồ biên loại đất hay bản đồ địa chất, một vài vùng con bên trong được loại bỏ để tạo ra các đa giác lớn hơn. Kết quả là chúng có thể được nhận biết nhờ thao tác phân lớp ở mức cao hơn. Vấn đề lớn nảy sinh khi tích hợp dữ liệu bản đồ (thí dụ, bản đồ của các nước khác nhau) là hệ thống tọa độ của chúng được đo vẽ trên cơ sở nhiều phép chiếu bản đồ khác nhau. Các dữ liệu này không thể tích hợp trên cùng bản đồ nếu không biến đổi chúng về cùng hệ trục tọa độ. Bước thứ nhất của biến đổi tọa độ là từ dữ liệu gốc hay dữ liệu vừa số hóa sang đơn vị đo thế giới thực của phép chiếu bản đồ. Đây là phần việc rất quan trọng của tiến trình thu thập dữ liệu bằng cách số hóa bản đồ giấy có sẵn. 1.1.4.3. Lƣu trữ và truy cập dữ liệu Chức năng lưu trữ dữ liệu trong GIS liên quan đến tạo lập CSDL không gian. Nội dung của CSDL này có thể bao gồm tổ hợp dữ liệu vectơ hoặc/và dữ liệu raster, dữ liệu thuộc tính để nhận danh hiện tượng tham chiếu không gian. Thông thường dữ liệu thuộc tính của GIS trên cơ cở đối tượng được lưu trong bảng (tệp), chúng chứa chỉ danh duy nhất tương ứng với đối tượng không gian, kèm theo rất nhiều mục dữ liệu thuộc tính khác nhau. Chỉ danh đối tượng không gian duy nhất được dùng để liên kết giữa dữ liệu thuộc tính và dữ liệu không gian tương ứng. Đôi khi mục dữ liệu trong bảng thuộc tính bao gồm cả giá trị không gian như độ dài đường, diện tích vùng mà chúng đã dược dẫn xuất từ biểu diễn dữ liệu hình học (hình 1.7). Trong mô hình dữ liệu raster thì các tệp thuộc tính thông thường chứa dữ liệu liên quan đến lớp hiện tượng tự nhiên như loại đất, thảm thực vật thay cho đối tượng rời 14 rạc. Việc lựa chọn mô hình raster hay vectơ để tổ chức dữ liệu không gian được thực hiện khi thu thập dữ liệu vì mỗi mô hình tương ứng với cách tiệm cận khác nhau đến việc lấy mẫu và mô tả thông tin. Tuy nhiên rất nhiều CSDL của GIS cho khả năng quản trị cả hai mô hình không gian nói trên. Khi xây dựng CSDL không gian thì cần phải liên kết bảng dữ liệu liên quan đến hiện tượng tự nhiên tương ứng. Một số hệ thống GIS được sử dụng rộng rãi, thí dụ Arc/Info, xây dựng CSDL trên cơ sở tổ hợp các mô hình sau: - Mô hình quan hệ quản lý thuộc tính phi hình học. - Lược đồ chuyên dụng, phi quan hệ để lưu trữ, xử lý dữ liệu không gian. Hình 1.7 Liên kết dữ liệu thuộc hình học Một vài GIS khác đã lợi dụng các phương tiện của lược đồ lưu trữ CSDL quan hệ để quản lý cả hai loại dữ liệu: hình học và phi hình học. Phương tiện truy nhập trong CSDL GIS cần bao gồm cả phương tiện có sẵn của CSDL quan hệ chuẩn, thí dụ, trích chọn dữ liệu đã lưu trữ trên cơ sở một thuộc tính nào đó như tên hay lớp hiện tượng (thành phố, vùng hành chính, loại đường quốc lộ...). Chúng còn có khả năng xây dựng câu hỏi truy vấn (query) để tìm thông tin mà giá trị của nó bằng hay nằm trong khoảng xác định (dân số trên 50000, số người trên 15 60 tuổi...). Đặc tính đặc biệt của câu hỏi được sử dụng trong CSDL GIS là khả năng xác định dữ liệu theo vị trí trong hệ tọa độ nào đó và theo các quan hệ không gian. Vì nhu cầu khai thác thông tin trên cơ sở vị trí cho nên CSDL không gian thường bao gồm phương pháp chỉ số không gian đặc biệt. Câu hỏi không gian thông thường là tìm ra các đối tượng nằm trong hay nằm phía trên các biên của cửa sổ chữ nhật. Khai thác dữ liệu trên cơ sở vị trí hay quan hệ không gian được xem như nền tảng quá trình xâm nhập cơ sở dữ liệu của hệ GIS. 1.1.4.4. Tìm kiếm và phân tích không gian Việc thu thập, lưu trữ dữ liệu trong GIS là để nhằm sử dụng vào giải quyết các vấn đề hay lập quyết định liên quan tới ứng dụng cụ thể. Rất nhiều hệ GIS bao hàm hay có liên quan đến việc mô hình hóa dữ liệu và các chức năng thống kê chuyên dụng cho loại ứng dụng nào đó. Tuy nhiên, cốt lõi chung nhất của GIS phải đáp ứng đòi hỏi của mọi ứng dụng 1.1.5 Các ứng dụng phổ biến của GIS Vì GIS được thiết kế như một hệ thống chung để quản lý dữ liệu không gian, nó có rất nhiều ứng dụng trong việc phát triển đô thị và môi trường tự nhiên như là: quy hoạch đô thị, quản lý nhân lực, nông nghiệp, điều hành hệ thống công ích, lộ trình, nhân khẩu, bản đồ, giám sát vùng biển, cứu hoả và bệnh tật. Trong phần lớn lĩnh vực này, GIS đóng vai trò như là một công cụ hỗ trợ quyết định cho việc lập kế hoạch hoạt động. Môi trƣờng 16