ĐẠ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
Indexed
Query
information items
features
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ệ
Xây dựng cơ sở dữ liệu ảnh
Ảnh kết quả
Cơ sở dữ liệu ảnh
Dữ liệu ảnh
Trích chọn các đặc trưng ảnh
Cơ sở dữ liệu đặc trưng
Đo mức độ tương tự
Truy vấn
Ảnh mẫu truy vấn
Trích chọn các đặc trưng
Các đặc trưng đã được trích chọn
thống đa phương tiệ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
(1.1)
được biểu diễn như các véctơ n-chiều của các trọng số
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ỏ
(1.2)
hay cosine càng lớn thì hai ảnh càng tương tự nhau.
(1.3)
Độ đo khoảng cách Lp (Minkowski): Ví dụ cho trước hai véc tơ n-chiều
(1.4)
Khoảng cách Minkowski được tính theo công thức sau:
Trong CSDL ảnh có thể sử dụng giá trị p như sau:
(1.5)
Nếu p=1 ta có khoảng cách Manhattan hay khoảng cách City block:
9
(1.6)
Với p=2 ta có khoảng cách Euclid:
Đá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
(1.7)
Độ trung thực được tính như sau:
(1.8)
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
Độ chính xác được tính bởi công thức:
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
13
Ðườ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à điểm
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…
Hình 1.5 Ví dụ biểu diễn đường
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 đườ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 đó.
14
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.
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 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.
Hình 1.6 Ví dụ biểu diễn khu vực hành chính
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.
Trong mô hình vector, thông tin về điểm, đường và vùng được mã hoá và lưu
dưới dạng tập hợp các toạ độ (x,y). Vị trí của đối tượng điểm, như lỗ khoan,
15
có thể được biểu diễn bởi một toạ độ đơn x,y. Ðối tượng dạng đường, như
đường giao thông, sông suối, có thể được lưu dưới dạng tập hợp các toạ độ
điểm. Ðối tượng dạng vùng, như khu vực buôn bán hay vùng lưu vực sông,
được lưu như một vòng khép kín của các điểm toạ độ.
*. Cấu trúc dl không gian vecto
Mô hình dữ liệu vector xem các sự vật, hiện tượng là tập các thực thể
không gian cơ sở và tổ hợp của chúng. Trong mô hình 2D thì các thực thể cơ
sở bao gồm: điểm (point), đường (line), vùng (polygon). Các thực thể sở
đẳng được hình thành trên cở sở các vector hay toạ độ của các điểm trong
một hệ trục toạ độ nào đó.
Loại thực thể cơ sở được sử dụng phụ thuộc vào tỷ lệ quan sát hay
mức độ khái quát. Với bản đồ có tỷ lệ nhỏ thì thành phố được biểu diễn
bằng điểm (point), đường đi, sông ngòi được biểu diễn bằng đường (line).
Khi tỷ lệ thay đổi kéo theo sự thay đổi về thực thể biểu diễn. Thành phố lúc
này sẽ được biểu diễn bởi vùng có đường ranh giới. Khi tỷ lệ lớn hơn, thành
phố có thể được biểu diễn bởi tập các thực thể tạo nên các đối tượng nhà
cửa, đường sá, các trình tiện ích,… Nói chung mô hình dữ liệu vector sử
dụng các đoạn thẳng hay các điểm rời rạc để nhận biết các vị trí của thế giới
thực.
Trong mô hình vector người ta trừu tượng hoá các sự vật hiện tượng
và gọi chúng là các feature. Các feature được biểu diễn bằng các đối tượng
hình học: point, line, polygon. Các biểu diễn này áp dụng cho những đối
tượng đơn có hình dạng và đường bao cụ thể.
16
Hình 1.7 Ví dụ về bểu diễn các Feature trên bản đồ
Trong cách biểu diễn này, người ta định nghĩa:
Feature là một đối tượng trên bản đồ có hình dạng và vị trí xác định, có các
thuộc tính cùng với hành vi cụ thể.
Feature Class là một tập các feature có cùng kiểu tức là tập các point, line,
hay polygon. Các feature class tương đương với một lớp trên bản đồ.
Polygons: được dùng để biểu diễn các feature có miền bao xác định: ruộng
đất, ao, hồ hay các đơn vị hành chính…
hệ toạ độ. Feature dataset tương đương với một bản đồ.
Các thành phần dữ liệu
Trong feature dataset, mỗi point được lưu dưới một toạ độ đơn tương
ứng, line được lưu dưới một chuỗi các điểm có toạ độ (x, y) cho trước,
polygon được lưu thành một tập các điểm có toạ độ (x, y) xác định những
đoạn thẳng và đóng kín.
Points : biểu diễn các feature không có miền bao hay độ dài, nhiều khi nó
biểu diễn các feature có kích thước quá nhỏ so với tỷ lệ của bản đồ.
17
Hình 1.8: Đối tượng point trên bản đồ.
Lines: dùng để biểu diễn các feature có chiều dài xác định nhưng không có
miền bao hay những feature rất hẹp so với tỷ lệ bản đồ
Hình 1.9: Đối tượng line trên bản đồ.
Polygons: được dùng để biểu diễn các feature có miền bao xác định: ruộng
đất, ao, hồ hay các đơn vị hành chính…
Hình 1.10: Đối tượng polyon trên bản đồ.
18
Chương I đã trình bày tổng quan về hệ thống tìm kiếm đối tượng ảnh
theo nội dung. Các vấn đề cần giải quyết chính là kiến trúc hệ phống, các pha
hoạt động của hệ thống, vần đề trích chọn đặc trưng, đối sánh tương tự giữa
các đối tượng và các tiêu chí đánh giá hiệu năng hệ thống. Sau đó luận văn
đã trình bày nguyên lý cơ bản biểu diễn bản đồ vaesc tơ trong GIS. Phạm vi
quan tâm của luận văn là các vùng trong bản đồ véc tơ. Các kiến thức trình
bày trong chương này là cơ sở khoa học cho việc xây dựng hệ thống tìm
kiếm vùng trên bản đồ có hình dạng tương tự với ảnh véc tơ đầu vào.
Chương tiếp theo trình bày các kỹ thuật cơ bản trong việc đối sánh tương tự
giữa các vùng.
19
CHƯƠNG 2
MỘT SỐ KỸ THUẬT TÌM KIẾM ĐỐI TƯỢNG VÙNG TRONG
BẢN ĐỒ VECTƠ
Như đã trình bày ở Chương I, việc tìm kiếm ra các vùng mong muốn
trên cơ sở đối sánh các véc tơ đặc trưng của vùng. Nội dung chương này sẽ
trình bày các kỹ thuật trích chọn đặc trưng vùng, bao gồm: bộ mô tả Fourier,
Momen bất biến, lưới vùng…
2.1 Khái quát về tìm kiếm đối tượng trên cơ sở hình dạng
Có nhiều kỹ thuật chỉ số hóa và truy tìm ảnh, bao gồm (1) trên cơ sở
thuộc tính có cấu trúc của ảnh, (2) nhận dạng đối tượng trên ảnh, (3) văn bản
mô tả ảnh và (4) các đặc trưng ảnh mức thấp như lược đồ cấp xám, bộ mô tả
Fourier của ảnh. Với tiệm cận thứ nhất, dựa trên cơ sở thuộc tính ảnh, có thể
sử dụng các hệ DBMS truyền thống để chỉ số hóa và truy tìm ảnh. Tiệm cận
thứ hai chưa được chín muồi, nó phụ thuộc vào tự động nhận dạng đối tượng.
Tiệm cần thứ 3 có thể sử dụng các hệ thống tìm kiếm văn bản để tìm kiếm
ảnh. Luận văn này tập trung vào tiệm cận thứ tư.
Màu sắc và kết cấu là những thuộc tính có khái niệm toàn cục
trong một ảnh. Trong khi đó, hình dạng không phải là một thuộc tính
của ảnh. Nói tới hình dạng không phải là nhắc đến hình dạng của một
ảnh. Thay vì vậy, hình dạng có khuynh hướng chỉ đến một khu vực đặc
biệt trong ảnh, hay hình dạng chỉ là biên của một đối tượng nào đó trong ảnh.
Trong tìm kiếm ảnh theo nội dung, hình dạng là một cấp cao hơn so với màu
sắc và kết cấu. Nó đòi hỏi sự phân biệt giữa các vùng để tiến hành xử lý
về độ đo của hình dạng.
Tiệm cận trên cơ sở nội dung mức thấp đòi hỏi trích chọn đặc trưng ảnh
mức thấp. Các đặc trưng chung được sử dụng là màu, hình dạng đối tượng và
20
texture. Luận văn này giới hạn nghiên cứu khảo sát một số kỹ thuật tìm kiếm
ảnh dựa trên hình dạng đối tượng trên ảnh.
Hình dạng đối tượng chứa trong ảnh là đặc trưng mức thấp quan trọng.
Với tìm kiếm trên cơ sở hình dạng, các ảnh phải được phân đoạn thành các
đối tượng riêng rẽ nhờ phương pháp nào đó. Mặc dù phân đoạn ảnh là chủ đề
quan trọng, nhưng không được tập trung trao đổi ở phần này. Sau khi phân
đoạn, nhiệm vụ chủ yếu của truy tìm hình ảnh trên cơ sở hình dạng là biểu
diễn hình dạng và đo mức tương đồng giữa các biểu diễn hình dạng. Luận văn
này tập trung tìm kiếm đối tượng trên cơ sở bản đồ véc tơ nên không cần quan
tâm đến phân đoạn.
Biểu diễn hình dạng và đo mức tương đồng tốt cho mục đích nhận dạng
và tìm kiếm thì cần phải có hai đặc tính quan trọng sau:
Mỗi hình dạng cần có đại diện duy nhất, bất biến khi chúng biến đổi
như dịch chuyển, xoay và co dãn. Đặc tính này cho phép nhận biết đối tượng
với kích thước khác nhau và ở vị trí, hướng khác nhau.
Các hình dạng tương tự cần phải có đại diện tương tự sao cho truy tìm
thực hiện được trên cơ sở khoảng cách giữa các đại diện hình dạng.
Tìm kiếm đối tượng trên bản đồ véc tơ tương tự các hệ thống tìm kiếm
ảnh thông thường, sử dụng các kỹ thuật đối sánh tốt nhất thay cho đối sánh
chính xác. Trong quá trình tìm kiếm, người sử dụng chọn đối tượng làm mẫu
“thí dụ” hay phác họa hình dạng mà họ quan tâm. Sau đó nhập đối tượng này
vào hệ thống tìm kiếm. Hệ thống tìm kiếm ra các đối tượng có hình dạng
tương tự để trình diễn cho người sử dụng theo thứ tự tính tương đồng giảm
dần. Do vậy, quan trọng là các đối tượng tương tự phải có số đo tương tự;
khoảng cách giữa hai hình dạng tương tự phải nhỏ hơn khoảng cách giữa hai
hình dạng không tương tự. Nói cách khác, thước đo tương tự giữa hai đại diện
hình dạng phải phù hợp với cảm nhận của con người.
21
Các hệ thống tìm kiếm ảnh theo nội dung thường khai thác hai nhóm
biểu diễn hình dạng sau :
Biểu diễn hình dạng theo đường biên (cotour-based descriptor): Biểu
diễn các đường biên bao bên ngoài
Biểu diễn theo vùng (region-based descriptor): Biểu diễn một vùng
toàn vẹn
Sau đây là mô tả một vài tiệm cận đến biểu diễn hình dạng và thước đo tính
tương tự trong hệ thống tìm kiếm đối tượng trong ảnh có thể áp dụng cho bản
đồ véc tơ.
2.2 Đặc trưng hình dạng đơn giản
Bất kỳ đối tượng nào trên ảnh hay bản đồ, ta đều có thể tìm ra các đặc
trưng sau đây [7]:
Trục chính: Đoạn thẳng nối hai điểm trên biên xa nhất của đối tượng
Trục phụ: Đoạn thẳng vuông góc với trục chính. Chữ nhật mà nó có các cạnh
song song với trục chính và song song với trục phụ, độ dài cạnh của nó bằng
độ dài trục chính và độ dài trục phụ sẽ là chữ nhật bao biên hình dạng.
Chữ nhật cơ sở: Chữ nhật nói trên được hình thành bởi trục chính và trục
phụ gọi là chữ nhật cơ sở.
Độ lệch tâm (Eccentricity) của biên: Là tỷ lệ giữa trục chính và trục phụ.
Các thước đo hình dạng trên đây cho ta khả năng trình diễn hình dạng thô. Nó
có thể được sử dụng vào chỉ mục và tìm kiếm hình dạng đối tượng trên bản
đồ. Tuy nhiên, vì nó không mô tả chi tiết hình dạng cho nên nó thường được
sử dụng kết hợp với cách biểu diễn hình dạng khác để tăng độ chính xác tìm
kiếm. Thí dụ, hệ thống QBIC (Query by Image Content) của IBM sử dụng
diện tích, chu vi, hướng của trục chính và bất biến moment của hình dạng để
chỉ mục và tìm kiếm ảnh.
22
2.3 Moment bất biến
Các moment được sử dụng để nhận ra ảnh và được sử dụng trong nhiều hệ
thống tìm kiếm ảnh. Với ảnh số f(x, y), moment bậc (p+q) được định nghĩa
như sau:
(2.1)
trong đó, x, y là vị trí pixel trong ảnh, f(x, y) là cường độ pixel.
Nếu và được định nghĩa là trọng tâm ảnh, như sau:
(2.2)
thì các moment trọng tâm được biểu diễn bởi:
(2.3)
Các moment trọng tâm bậc 3 được định nghĩa như sau:
(2.4)
Ký hiệu moment trọng tâm chuẩn hóa bậc (p+q) là Eta ŋpq và được định nghĩa
như sau:
(2.5)
23
gamma trong đó là:
(2.6) với p+q=2, 3,...
Bảy moment sau đây đã được chứng minh là bất biến với các phép biến đổi
ảnh như dịch chuyển, quay và co dãn ảnh:
(2.7)
Bảy moment này được sử dụng để mô tả hình dạng. Khoảng cách giữa
hai mô tả hình dạng được sử dụng làm khoảng cách giữa hai hình. Tuy nhiên,
các moment tương đồng không đảm bảo hình dạng tương tự. Do vậy, hiệu
năng của chỉ mục và truy tìm hình dạng trên cơ sở moment không cao.
24
Bắt đầu
Đầu vào: Ảnh chứa đối tượng tìm kiếm
Tính trọng tâm ảnh theo
công thức (2.2)
Tính moment trọng tâm theo công thức (2.3)
Tính moment trọng tâm bậc 3 theo công thức (2.4)
Tính 7 moment theo công thức (2.7)
Đầu ra: 7 giá trị moment (là vectơ đặc trưng của ảnh để đối sánh)
Kết thúc
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
25
2.5 Phương pháp bộ mô tả Fourier
Trong phương pháp trên cơ sở mô tả Fourier[3][7,8], hình dạng trước
hết được biểu diễn bởi hàm đặc trưng gọi là dấu hiệu (signature) hình dạng.
Biến đổi Fourier rời rạc được áp dụng để có được bộ mô tả Fourier(Fourier
descriptors - FD) của hình dạng. Các FD này được sử dụng để chỉ mục hình
dạng và tính toán mức độ tương đồng hình dạng.
Biến đổi Fourier rời rạc của dấu hiệu hình dạng f(i) được cho bởi:
(2.8)
với u=0 đến N-1, trong đó N là tổng số mẫu f(i).
Có nhiều loại dấu hiệu hình dạng. Các loại dấu hiệu hình dạng hay sử
dụng là trên cơ sở độ cong, bán kính, tọa độ biên hình dạng (Hình 2.1). Hiệu
năng phân lớp hình dạng trên cơ sở ba loại dấu hiệu này không khác nhau
nhiều. Dấu hiệu trên cơ sở bán kính là đơn giản và dễ cài đặt nhất.
Hình 2.2 Hàm dấu hiệu của hình dạng
Trên hình 2.2 là hàm đặc trưng góc tích lũy mô tả đường biên hình
dạng. Với t là tham số, góc tích lũy được tính như sau:
26
(t)
(2.9)
y
z(t)
z(0)
(t)
(0)
x
Hình 2.3 Hàm góc tích lũy
Hình 2.4 Hàm tính diện tích
Trên hình 2.3 là hàm tính diện tích của đối tượng. Với t là tham số, hàm tính
diện tích của quả táo như sau:
27
(2.10)
Dấu hiệu trên cơ sở bán kính bao gồm một số khoảng cách theo thứ tự từ tâm
hình dạng đến các điểm trên biên (gọi là radii - các bán kính). Radii được
định nghĩa như sau:
(2.11)
trong đó, (xc, yc) là tọa độ tâm ảnh, (xi, yi) với i=0 đến 63 là tọa độ của 64
điểm mẫu theo biên hình dạng. Các điểm biên được lấy mẫu sao cho tổng số
điểm ảnh theo biên giữa hai điểm láng giềng là như nhau.
Radii hình dạng và biến đổi giữa chúng là bất biến dịch chuyển. Chú ý
rằng các hình dạng không chuẩn hóa hướng trước khi sử dụng radii hình
dạng.
Khi biến đổi Fourier, ta thực hiện chuẩn hóa bằng cách bỏ qua các giá
trị pha của FD. Xoay hình dạng được phản ánh trong thông tin pha của Fu và
độ lớn của Fu, hay |Fu| là bất biến với quay. |F0| phản ánh năng lượng của
radii hình dạng, vậy |Fu|/|F0| sẽ bất biến co dãn. Do vậy, ta sử dụng véctơ đặc
trưng sau (nó bất biến với dịch chuyển, quay, và co dãn) để chỉ mục hình
dạng:
(2.12)
Khoảng cách gữa các hình dạng được tính toán bằng khoảng cách
Euclid giữa các véc tơ đặc trưng của chúng.
Tại sao ta sử dụng FD để chỉ mục hình dạng thay cho trực tiếp radii? Lý do
chính là biểu diễn trực tiếp là rất nhạy với thay đổi nhỏ và nhiễu, dẫn tới hiệu
năng truy tìm rất thấp. Nếu 64 độ dài bán kính sử dụng trực tiếp làm chỉ mục,
28
có thể sẽ rất khó co dãn và chuẩn hóa quay. Có thể thực hiện chuẩn hóa quay
bằng nhận ra bán kính ngắn nhất (hay dài nhất) và thực hiện chuẩn hóa co dãn
bằng cố định độ dài của bán kính ngắn nhất. Nhưng chuẩn hóa này không ổn
định vì với thay đổi nhỏ trên đường biên sẽ ảnh hưởng đến vị trí bán kính nhỏ
nhất và các vị trí của điểm mẫu, dẫn tới chỉ mục rất khác nhau và khoảng cách
rất lớn giữa các hình dạng do thay đổi nhỏ. Mục tiêu sử dụng FD là chuyển
đổi độ dài bán kính nhạy cảm vào miền tần số nơi dữ liệu bền vững hơn với
thay đổi nhỏ và nhiễu.
29
Bắt đầu
Đầu vào: Ảnh (đã xử lý để có biên đối tượng)
Lựa chọn hàm đặc trưng hình dạng (hàm bán kính, hàm tính diện tích) Chọn 64 giá trị
Biến đối Fourier hàm đặc trưng hình
dạng (Có 64 hệ số Fourier)
Tính toán bộ mô tả Fourier theo công thức (2.12)
Đầu ra: FD= [f1, f2, …, f63] (là vectơ đặc trưng của ảnh để đối sánh)
Kết thúc
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
30
2.6 Biểu diễn hình dạng trên cơ sở lưới vùng
Tổng quát thì việc đo hình đồng dạng trên cơ sở biểu diễn hình dạng
mô tả trên đây không phù hợp với cảm nhận của con người [7]. Các nghiên
cứu đã so sánh đo tính tương tự hình dạng bằng moment đại số, khoảng cách
đường cong spline, góc quay tích lũy, dấu độ cong, khoảng cách Hausdorff
với kết luận đồng dạng của con người. Đã chứng minh rằng đồng dạng tính
toán trên cơ sở các thước đo này không phù hợp hoàn toàn với đánh giá của
con người.
Sau đây sẽ mô tả biểu diễn hình dạng trên cơ sở vùng và thước đo
đồng dạng. Phương pháp này được xem là có hiệu năng truy tìm cao.
Ý tưởng chính của biểu diễn hình dạng trên cơ sở vùng
x
y
Cho trước hình dạng, hãy xếp chồng lưới trên chúng như hình 2.6.
Hình 2.6. Ví dụ xếp chồng
lưới Không gian lưới bao gồm các tế bào vuông kích thước cố định, nó đủ lớn để
phủ hoàn toàn hình dạng. Một vài tế bào lưới phủ hoàn toàn hay phủ một
phần một vài tế bào khác không phủ hình dạng. Gán giá trị 1 cho tế bào có ít
nhất 25% điểm ảnh bị phủ và giá trị 0 cho các tế bào còn lại. Sau đó đọc các
giá trị 1 và 0 từ góc trên trái của hình dạng để có trình tự nhị phân cho hình
dạng. Thí dụ, hình 2.6 được biểu diễn bởi dãy 11100000 11111000 01111110
01111111.
31
Rõ ràng rằng, tế bào càng nhỏ thì độ chính xác biểu diễn hình dạng càng cao
nhưng đòi hỏi tính toán, lưu trữ càng lớn. Kích thước tế bào thích hợp là
10x10 đến 20x20 pixel qua thực nghiệm [7].
Biểu diễn trên đây đảm bảo hướng duy nhất nhưng co dãn và xoay là không
bất biến. Do vậy, dãy nhị phân được chuẩn hóa cho co dãn và quay nếu chúng
ta muốn sử dụng nó để biểu diễn hình dạng.
Chuẩn hóa quay
Mục đích của chuẩn hóa quay là đặt hình dạng vào hướng chung duy
nhất. Chúng ta quay hình dạng sao cho trục chính của nó song song với trục x.
Còn hai khả năng đặt hình dạng: một trong các điểm xa nhất đặt bên trái hay
bên phải. Điều này đòi hỏi quay 1800. Thí dụ hình 2.6 có thể đặt vào 1 trong
hai vị hướng như trên hình 2.7
32
A
A
B
y
B
A
Hình 2.7: Ví dụ về chuẩn hóa co dãn
Biểu diễn hai hướng hình dạng như hình vẽ 2.7 cần hai dãy nhị phân
khác nhau. Vì các dãy nhị phân được sử dụng để chỉ mục các dãy trong hệ
thống truy tìm dẫn tới việc lưu trữ cho mỗi hình dạng cần gấp đôi không gian
lưu trữ. Để tiết kiệm không gian lưu trữ, ta chỉ cần có và lưu trữ một trong hai
dãy nhị phân. Sử dụng dãy nào là không quan trọng, nó được xác định khi cài
đặt. Hai hướng được quan tâm khi truy tìm bằng cách biểu diễn nó trong câu
truy vấn hình dạng bằng hai dãy nhị phân, chúng được so sánh với từng chỉ
mục hình dạng lưu trữ trong CSDL.
33
Chuẩn hóa co dãn
Để đạt được chuẩn hóa co dãn, chúng ta co dãn mọi hình dạng sao
cho các trục chính của chúng có cùng độ dài cố định. Thí dụ, độ dài cố định
có thể là 192 pixel [7].
Biểu diễn hình dạng duy nhất - Chỉ mục hình dạng
Sau khi chuẩn hóa quay và co dãn, chọn lựa kích thước lưới tế bào,
chúng ta có được dãy nhị phân duy nhất cho hình dạng với giả sử rằng mỗi
dãy có trục chính duy nhất. Dãy nhị phân này được sử dụng để biểu diễn hay
chỉ mục hình dạng. Thí dụ, chỉ mục hình dạng trên hình 2.7 (đã chuẩn hóa
theo hình 2.6) sẽ là 11111111 01111110 00011000 hay 00111110 111111111
11111111.
Vì ta sử dụng lưới tế bào đủ lớn để bao trùm hình dạng chuẩn hóa, khi
quyết định kích thước tế bào, tổng số tế bào lưới theo trục x là cố định. Tổng
số tế bào theo hướng y phụ thuộc vào độ lệch tâm của hình dạng. Giá trị cực
đại là cùng giá trị với trục x. Thí dụ khi kích thước lưới tế bào là 24x24 pixel,
tổng số tế bào theo trục x là 8, tổng số tế bào theo trục y từ 1 đến 8, phụ thuộc
vào độ lệch tâm.
Đo độ tương tự
Nhiệm vụ tiếp theo là đo độ tương tự giữa các hình dạng trên cơ sở
chỉ mục của chúng như thế nào. Vì chỉ mục chỉ ra vị trí của tế bào bao phủ
hình dạng, khoảng cách giữa hai hình dạng được xác định bằng số các vị trí
các tế bào không cùng bao phủ hai hình dạng này. Quay 1800 và các thao tác
hình dạng khác được xem xét sau. Trên cơ sở độ lệch tâm, có ba cách tính
toán độ tương tự như sau:
Nếu hai hình dạng chuẩn hóa có cùng chữ nhật cơ sở, chúng ta so sánh từng
bit các chỉ mục của hai hình dạng, khoảng cách giữa chúng sau đó sẽ bằng
34
tổng vị trí có giá trị khác nhau. Thí dụ, hình dạng A và B có cùng độ lệch tâm
là 4 và dãy nhị phân là 11111111 11100000 và 11111111 11111100 thì
khoảng cách giữa A và B là 3.
Nếu hai hình dạng chuẩn hóa có các chữ nhật rất khác nhau (chúng có
độ dài trục bé rất khác nhau), chúng ta không cần tính toán độ tương tự của
chúng vì ta có thể kết luận rằng hai hình dạng này rất khác nhau. Thí dụ, nếu
độ lệch tâm của A là 8 và của B là 2, thì ta có thể kết luận hai hình dạng này
khác nhau và không có ý nghĩa khi tiếp tục truy tìm hình dạng. Ngưỡng khác
nhau giữa các trục nhỏ phụ thuộc vào từng ứng dụng và kích thước tế bào.
Thông thường, nếu hiệu số độ dài các trục nhỏ của hai hình lớn hơn 3 thì hai
x
H
ìn
h
6.
7
#
1
9
y
x
B
A
y
hình được xem là khác nhau.
Hình 2.8. Ví dụ về đo độ tương tự
35
Nếu hai hình dạng chuẩn hóa có hình chữ nhật cơ sở không khác nhau nhiều
thì có khả năng cảm giác chúng là tương tự. Ta bổ sung các số 0 vào chỉ mục
hình dạng của trục bé ngắn hơn sao cho chỉ mục có cùng độ dài với hình kia.
Khoảng cách giữa hai hình dạng được tính toán như trường hợp thứ nhất. Thí
dụ, nếu độ dài của trục nhỏ và dãy nhị phân của hình A là 2 và 11111111
11110000 và độ dài và dãy nhị phân của hình B là 3 và 11111111 111111000
11100000, thì ta kéo dài số nhị phân của hình A thành 11111111 11110000
00000000. Khoảng cách giữa A và B sẽ là 4.
Để dễ dàng tính toán khoảng cách khi truy tìm, độ lệch hình dạng được
lưu trữ cùng với dãy nhị phân duy nhất. Chúng hình thành nên cái gọi là chỉ
mục của hình dạng.
Các thao tác hình dạng khác
Để bổ sung vào quay hình dạng 1800, hai thao tác khác là flip ngang và
dọc. Hình 2.8 chỉ ra hai hình kết quả của hai thao tác trên hình dạng có từ hình
2.7. Hai hình dạng này cảm nhận tương tự với hình dạng trên hình 2.6.
Để sử dụng hai thao tác này và vẫn tiết kiệm lưu trữ, ta chỉ cần lưu một
chỉ mục cho mỗi hình nhưng ta sẽ sinh ra bốn dãy nhị phân cho mỗi hình
dạng trong câu truy vấn khi truy tìm. Trong trường hợp này, hình dạng cảm
giác tương tự được tìm ra từ kết quả của quay 1800, lật (flip) ngang và lật dọc.
Quản lý đa trục chính
Trên đây ta giả sử rằng mỗi hình dạng chỉ có một trục chính. Thực tế,
hình dạng có thể có nhiều trục chính với cùng độ dài. Có thể sinh ra các số nhị
phân khác nhau từ cùng hình dạng, nó phụ thuộc vào trục chính nào được sử
dụng để chuẩn hóa quay.
Để giải quyết vấn đề này, chuẩn hóa quay được thực hiện theo từng trục
và các số nhị phân cho mỗi trục được sử dụng làm chỉ mục hình dạng.
36
Khoảng cách giữa hai hình dạng là khoảng cách tối thiểu giữa mỗi cặp số nhị
phân của hai hình dạng này.
37
Bắt đầu
Đầu vào: Ảnh
Tính trục chính của
đối tượng trên ảnh
Chuẩn hóa: Xoay ảnh để trục chính song song với trục tọa độ Ox Co /dãn ảnh sao cho trục chính có độ dài 192 pixel
Phủ lưới tế bào hình vuông
(chọn kích thước tế bào16 x16)
Biểu diễn tế bào bằng các giá trị 0/1 (Nếu hình dạng chiếm 25% thì gán giá trị 1. ngược lại gán giá trị 0)
Đầu ra: Ma trận 0/1 lưới tế bào phủ lên hình dạng
Kết thúc
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
38
Tóm tắt về tiến trình truy tìm và chỉ mục
Trên đây là mô tả về biểu diễn hình dạng trên cơ sở vùng bất biến với các
thao tác dịch chuyển, co dãn, quay và lấy phản chiếu và thước đo tương tự của
chúng. Trong hệ thống truy tìm, mọi hình dạng trong CSDL đều được chỉ
mục. Trong khi truy tìm, hình dạng truy vấn cũng được chỉ mục. Sau đó so
sánh chỉ mục truy vấn với chỉ mục hình dạng trong CSDL để tìm ra các hình
dạng tương tự.
Mỗi hình dạng trong CSDL được xử lý và chỉ mục như sau (với giả sử
mỗi hình dạng chỉ có một trục chính):
Tìm kiếm trục chính, trục con và độ lệch tâm của hình dạng.
Quay hình dạng để đặt trục chính theo chiều x, hình dạng được co
dãn sao cho trục chính có độ dài chuẩn cố định.
Không gian lưới với kích thước tế bào cố định được xếp trên đỉnh
của hình dạng đã chuẩn hóa.
Gán giá trị 1 cho các tế bào phủ trên hình và giá trị 0 cho các tế bào
còn lại. Bằng cách đọc giá trị 1 và 0 từ trái sang phải và từ trên
xuống dưới dể có dãy nhị phân của hình.
Dãy nhị phân của trục chính được lưu trữ làm chỉ mục của hình
dạng.
Trong khi truy tìm, các bước sau đây được sử dụng để biểu diễn hình dạng
truy tìm và thực hiện so sánh tính tương tự.
Hình dạng truy vấn được biểu diễn bằng độ dài cố định của trục
chính và các dãy nhị phân sử dụng cùng thủ tục như trong tiến trình
chỉ mục hóa nói trên. Nhưng chú ý rằng có bốn dãy nhị phân cho mỗi
truy vấn để có quay 1800 và các thao tác flip theo chiều đứng và
chiều ngang.
39
Vì lý do hiệu quả, bốn dãy nhị phân này được so sánh với dãy nhị
phân của hình dạng trong CSDL với cùng độ lệch tâm tương tự.
Khoảng cách giữa truy vấn và hình dạng trong CSDL được tính toán
như tổng số các vị trí với các giá trị khác nhau trong dãy nhị phân
của nó.
Các hình dạng tương tự được hiển thị hay truy tìm theo thứ tự tăng
dần của khoảng cách hình dạng.
Trên đây là tiệm cận đơn giản và tương tự với cách so sánh hình dạng
thông thường. Để so sánh hai hình dạng, ta muốn chúng có cùng hay kích
thước tương tự (chuẩn hóa co dãn). Sau đó ta quay một trong các hình sao cho
chúng có cùng hướng (chuẩn hóa quay). Cuối cùng, ta xác định chúng khác
bao nhiêu trên cơ sở chúng có bao nhiêu không phủ lấp.
*) Thuật toán tìm kiếm vùng tương tự dựa trên cơ sở momet hình dang,
bộ mô tả Fourier, lưới vùng
- Input: CSDL danh sách vùng, vùng được chọn để tìm kiếm.
- Output: Vùng tương tự với vùng đầu vào.
- Thuật toán:
40
Hình 2.10: Lưu đồ thuật toán tìm kiếm vùng tương tự
41
CHƯƠNG 3
XÂY DỰNG CHƯƠNG TRÌNH THỬ NGHIỆM
3.1 Quy trình tổng quan
Hình 3.1: Sơ đồ hệ thống.
Nhiệm vụ chính: Từ vùng đầu vào, hệ thống duyệt trong CSDL địa lý tập
các vùng đã có, tính độ tương đồng và lấy ra vùng tương tự.
42
Hình 3.2: Màn hình chính chương trình.
CSDL địa lý: shape file tỉnh Quảng Ninh
Các tính năng tính của chương trình:
- Hiển thị các vùng từ CSDL địa lý.
- View danh sách vùng đầu vào.
- Hiển thị vùng đầu vào được chọn.
- Tìm kiếm và đánh dấu vùng đầu vào tương tự.
43
3.2.Trích xuất các vùng từ CSDL địa lý
Dữ liệu địa lý về tỉnh Quảng Ninh chứa trong tập các file:
DuongDiaGioi_Clip.cpg
DuongDiaGioi_Clip.dbf
DuongDiaGioi_Clip.prj
DuongDiaGioi_Clip.sbn
DuongDiaGioi_Clip.sbx
DuongDiaGioi_Clip.shp
DuongDiaGioi_Clip.shp.xml
DuongDiaGioi_Clip.shx
Dữ liệu lưu trong thư mục “data”
Nhiệm vụ: trích xuất dữ liệu thông tin (địa giới hành chính) và dữ liệu
hình học và hiển thị trên màn hình
Thư viện sử dụng: EGIS
Mã truy xuất thông tin địa lý vùng:
44
3.3.Hiển thị dữ liệu địa lý
Bản đồ các vùng tỉnh Quảng Ninh
Hình 3.3: Bản đồ các vùng tỉnh Quảng Ninh.
45
3.4.Hiển thị vùng đầu vào được chọn
Các vùng đầu vào được được lưu sẵn trong mỗi file trong thư mục
“input”:
Hình 3.4: Các vùng đầu vào.
Nội dung file đầu vào là dữ liệu hình học của vùng đầu vào:
Hình 3.5: Dữ liệu hình học vùng đầu vào.
46
Hiển thị vùng đầu vào được chọn:
Hình 3.6: Hiển thị vùng đầu vào được chọn.
3.5.Tìm kiếm vùng tương tự
Phát biểu bài toán;
- Đầu vào: CSDL danh sách vùng, vùng được chọn để tìm kiếm.
- Đầu ra: Vùng tương tự với vùng đầu vào.
Các nhiệm vụ cần thực hiện như sau:
Tính ma trân 0..1 sử dụng thuật toán phủ lưới
Tính độ tương tự giữa hai ma trận 0..1
Tìm vùng tương tự với vùng đầu vào
47
3.6.Thử nghiệm với một số vùng đầu vào
*) Mô tả phần mềm sử dụng
B1: Chọn vùng DL từ danh sách vùng (cột bên trái), vùng DL này sẽ hiển
thị trên màn hình phía dưới bên phải.
B2: Nháy chuột vào nút “Tìm vùng tương tự”
B3: Kết quả: Vùng tương tự với vùng đầu vào sẽ hiển thị trên màn hỉnh
phía trên, bên phải, đồng thời thông tin hành chính về vùng này sẽ
được hiển thị phía nút “Tìm vùng tương tự”
Hình 3.7: Kết quả tìm vùng tương tự với vùng 13.
48
Hình 3.8: Kết quả tìm vùng tương tự với vùng 2.
49
Hình 3.9: Kết quả tìm vùng tương tự với vùng 3.
50
Hình 3.10: Kết quả tìm vùng tương tự với vùng 6.
51
Hình 3.11: Kết quả tìm vùng tương tự với vùng 1.
52
Hình 3.12: Kết quả tìm vùng tương tự với vùng 15.
53
Hình 3.13: Kết quả tìm vùng tương tự với vùng 16.
54
Hình 3.14: Kết quả tìm vùng tương tự với vùng 20.
55
Hình 3.15: Kết quả tìm vùng tương tự với vùng 22.
56
3.7.Kết chương
Trong chương 3, luận văn đã trình bày quy trình thử nghiệm cho bài toán
tìm kiếm đối tượng vùng. Trước hết, chương 3 trình bày sơ đồ xử lý của bài
toán với hai nhiệm vụ chính. Một là, truy cập dữ liệu địa lý lấy ra thông tin
chung và thông tin hình dạng để đưa vào cơ sở dữ liệu. Hai là, tìm kiếm trong
cơ sở dữ liệu đối tượng vùng có hình dạng tương tự với vùng đầu vào. Ngoài
ra, chương trình thử nghiệm còn cho phép hiển thị bản đồ các vùng từ cơ sở
dữ liệu liệu địa lý, vùng đầu vào và vùng tương tự tìm thấy trên bản đồ.
Chương trình thử nghiệm sử dụng thuật toán phủ lưới (đã trình bày trong
chương 2) để kiểm tra độ tượng tự giữa các vùng. Các kết quả thử nghiệm cho
thấy chương trình làm việc tốt, tìm kiếm được vùng tương tự và hiển thị lên
màn hình.
57
TÀI LIỆU THAM KHẢO
Tiếng Việt
[1] Đặng Văn Đức (2001), Hệ thống thông tin địa lý, NXB Khoa học và Kỹ
Thuật, Hà Nội.
Tiếng Anh
[2] Adrijit Basu (2015), Shape Based Image Representation and Retrieval,
International Journal of Emerging Research in Management &Technology
[3] Aratrika Sarkar, PallabiBhatttacharjee (2014), A Shape Based Image Search
Technique, International Journal of Advanced Computer Science and
Applications.
[4] Arvind M. Bhave (2016), Shape Based Descriptors for Image Retrieval, [
IOSR Journal of Computer Engineering.
[5] Arulmozhi P., S.Abirami (2014), Shape Based Image Retrieval: A Review, [
International Journal on Computer Science and Engineering (IJCSE)
[6] Jhansi Rani S. and V. Vallikumari (2016),Survey on Content Based Image [
Retrieval Techniques, International Journal of Trend in Research and
Development.
[7] Guojun Lu (1999), Multimedia Database Management Systems, Artech [
House, Boston – London.
[8] Santhosh P Mathew, Philip Samuel (2010), A Novel Image Retrieval [
System Using an Effective RegionBased Shape Representation Technique,
International Journal of Image Processing (IJIP).
[9] Shashi Shekhar, Sanjay Chawla (2001), A Tour Of Spatial Databases,
Department of Computer Science, University of Minnesota.
58
PHỤ LỤC: Cấu trúc file Shapefile
1. Main file header
Main file header có độ dài 100 bytes. ... chỉ ra các trường trong file header với
vị trí byte, giá trị, kiểu và thứ tự byte của chúng. Trong bảng này, vị trí được
là tương đối tính từ vị trí bắt đầu file.
Bảng P-1. Mô tả của Main file header
Position Field Value Type Byte
Order
Byte 0 File Code 9994 Integer Big
Byte 4 Unused 0 Integer Big
Byte 8 Unused 0 Integer Big
Byte 12 Unused 0 Integer Big
Byte 16 Unused 0 Integer Big
Byte 20 Unused 0 Integer Big
Big Byte 24 File Length File Length Integer
Byte 28 Version 1000 Integer Little
Byte 32 Shape Type Shape Type Integer Little
Byte 36 Bounding Box Xmin Double Little
Byte 44 Bounding Box Ymin Double Little
Byte 52 Bounding Box Xmax Double Little
Byte 60 Bounding Box Ymax Double Little
Byte 68* Bounding Box Zmin Double Little
Byte 76* Bounding Box Zmax Double Little
Byte 84* Bounding Box Mmin Double Little
Byte 92* Bounding Box Mmax Double Little
59
* Không dùng nếu có giá trị 0.0, nếu không thì là độ đo hoặc kiểu Z.
Giá trị của độ dài file là tổng độ dài của file theo đơn vị là các từ 16-bit, trong
đó bao gồm 50 từ (tức là 100 byte) của file header. Tất cả các hình dạng
không null trong một shapefile phải có cùng kiểu shape. Các giá trị của kiểu
được cho trong
Bảng P-2. Các giá trị của shape type.
Giá trị Kiểu Shape
0 Null Shape
1 Point
3 PolyLine
5 Polygon
8 MultiPoint
11 PointZ
13 PolyLineZ
15 PolygonZ
18 MultiPointZ
21 PointM
23 PolyLineM
25 PolygonM
28 MultiPointM
31 MultiPatch
Hộp biên (Bounding Box) trong main file header chứa phạm vi thực sự của
các shape trong file: Hình chữ nhật bé nhất phủ toàn bộ các shape có cạnh
song song với trục X và Y (và có khả năng mở rộng với trục M và Z). Nếu
shapefile là rỗng (không có bản ghi nào) thì giá trị của Xmin, Ymin, Xmax,
và Ymax không được xác định.
60
2. Các header bản ghi
Header cho mỗi bản ghi chứa số hiệu bản ghi và độ dài nội dung của
bản ghi đó. Các header bản ghi có độ dài cố định là 8 byte. Bảng P- mô tả các
trường của header bản ghi, với vị trí được tính từ đầu của bản ghi tương ứng.
Bảng P-3. Mô tả header bản ghi.
Position Field Value Type Byte Order
Byte 0 Record Số hiệu bản ghi Integer Big
Number
Byte 4 Content Length Độ dài nội dung Integer Big
Số hiệu bản ghi bắt đầu từ 1. Độ dài nội dung bản ghi là độ dài của phần
nội dung bản ghi theo đơn vị từ 16-bit. Do đó, mỗi bản ghi sẽ đóng góp số
lượng từ 16-bit là (4 + độ dài nội dung) vào tổng độ dài của file (được chứa ở
Byte 24 trong file header).
PL3.3. Nội dung bản ghi
Nội dung bản ghi shapefile bao gồm một kiểu shape, theo sau bởi dữ liệu
hình học của shape đó. Độ dài của nội dung bản ghi phụ thuộc vào số thành
phần và số đỉnh trong shape.
Tiếp sau đây trình bày một số nội dung bản ghi theo các kiểu shape trong
hệ quy chiếu X, Y.
Kiểu Point (điểm). Một điểm bao gồm một cặp tọa độ kiểu double-
precision theo thứ tự X, Y.
Point
{
Double X // X coordinate
Double Y // Y coordinate
}
61
Bảng P-4. Nội dung bản ghi biểu diễn điểm.
Position Field Value Type Number Byte Order
Byte 0 Shape Type 1 Integer 1 Little
Byte 4 X X Double 1 Little
Byte 12 Y Y Double 1 Little
Kiểu MultiPoint (đa điểm). Biểu diễn một tập các điểm, như sau:
MultiPoint
{
Double[4] Box // Bounding Box
Integer NumPoints // Number of Points
Point[NumPoints] Points // The Points in the Set
}
Hộp Biên (Bounding Box) được lưu theo thứ tự Xmin, Ymin, Xmax, Ymax.
Bảng P-5. Nội dung bản ghi biểu diễn đa điểm.
Position Field Value Type Number Byte Order
Byte 0 Shape 8 Integer 1 Little
Type
Byte 4 Box Box Double 4 Little
Byte 36 NumPoints NumPoints Integer 1 Little
Byte 40 Points Points Point NumPoints Little
Kiểu PolyLine (đa đoạn). Một PolyLine là một tập có thứ tự các đỉnh bao
gồm một hoặc nhiều thành phần. Một phần là một thành phần liên thông gồm
ít nhất hai đỉnh. Các phần có thể hoặc không liên thông với phần khác. Các
62
phần có thể hoặc không cắt nhau với phần khác. Do là đặc tả này không cấm
các điểm liên tục với các tọa độ trùng nhau, nên khi đọc shapefile phải kiểm
soát được các trường hợp như vậy. Việc dẫn tới các phần thoái hóa có độ dài
bằng không là không được phép.
PolyLine
{
Double[4] Box // Bounding Box
Integer NumParts // Number of Parts
Integer NumPoints // Total Number of Points
Integer[NumParts] Parts // Index to First Point in Part
Point[NumPoints] Points // Points for All Parts
}
Các trường của một PolyLine được mô tả chi tiết sau đây:
Box: Hộp Biên cho PolyLine được lưu theo thứ tự Xmin, Ymin, Xmax,
Ymax.
NumParts: Số các phần trong PolyLine.
NumPoints: Tổng số các điểm trong tất cả các phần của PolyLine.
Parts: Một mảng có độ dài NumParts chứa chỉ số của điểm đầu tiên của
nó trong mảng các điểm. Các chỉ số mảng được đánh từ 0.
Points: Một mảng cú độ dài NumPoints.
...
63
Bảng P-6. Nội dung bản ghi chi tiết đa đoạn.
Position Field Value Type Number Byte
Order
Byte 0 Shape 3 Integer 1 Little
Type
Byte 4 Box Box Double 4 Little
Byte 36 NumParts NumParts Integer 1 Little
Byte 40 NumPoints NumPoints Integer 1 Little
Little Byte 44 Parts Parts Integer NumParts
Byte X Points Points Point NumPoints Little
Chú ý: X = 44 + 4 * NumParts.
Kiểu Polygon (Đa giác)
Một đa giác bao gồm một hoặc hơn một vành. Một vành là một chuỗi
đóng liên thông của ít nhất 4 điểm, không tự cắt. Một đa giác có thể chứa
nhiều vành ngoài. Thứ tự của các định hoặc hướng của một vành chỉ ra mặt
nào của vành là phía trong của đa giác. Lân cận bên phải của người quan sát
đi dọc theo vành theo thứ tự đỉnh là thuộc vùng phía trong của đa giác. Các
đỉnh của các vành định nghĩa lỗ rỗng trong đa giác theo hướng ngược chiều
kim đồng hồ. Các đỉnh của vành đơn do đó luôn có thứ tự thuận chiều kim
đồng hồ. Các vành của một đa giác được cho bởi các part (phần) của nó.
Lưu ý là các điểm liên tiếp không nhất thiết phải phân biệt, nên khi đọc
shapefile phải xử lý tình huống này. Cấu trúc của đa giác cũng giống như cấu
trúc đa đoạn, như sau
64
Polygon
{
Double[4] Box // Bounding Box
Integer NumParts // Number of Parts
Integer NumPoints // Total Number of Points
Integer[NumParts] Parts // Index to First Point in Part
Point[NumPoints] Points // Points for All Parts
}
Các trường của một đa giác được mô tả chi tiết như sau:
Box: Hộp biên của đa giác theo thứ tự Xmin, Ymin, Xmax, Ymax.
NumParts: Số vành trong đa giác.
NumPoints: Tổng số điểm trong tất cả các vành.
Parts: Một mảng gồm NumParts phần tử, chứa chỉ số điểm đầu tiên của
mỗi vành trong mảng Points.
Points: Một mảng gồm NumPoints phần tử. Các điểm cho vành 2 nối
tiếp các điểm của vành 1 và cứ như vậy.
Một ví dụ về đa giác gồm 2 vành và 10 điểm như sau:
Hình P-1. Ví dụ một đa giác gồm hai vành.
65
Thứ tự các đỉnh được lưu trữ trong shape file được minh họa bởi Hình P-.
Hình P-2. Lưu trữ đa giác trong shapefile.
Bảng P-7. Nội dung bản ghi đa giác.
Position Field Value Type Number Byte
Order
Byte 0 Shape Type 5 Integer 1 Little
Byte 4 Box Box Double 4 Little
Byte 36 NumParts NumParts Integer 1 Little
Byte 40 NumPoints NumPoints Integer 1 Little
Byte 44 Parts Parts Integer NumParts Little
Byte X Points Points Point NumPoints Little
Chú ý: X = 44 + 4 * NumParts.
Ngoài ra shapefile còn có các cấu trúc shape khác như: PointM, MultiPointM,
PolyLineM, PolygonM (M là độ đo), PointZ, MultiPointZ, PolyLineZ,
PolygonZ (trong hệ quy chiếu X, Y, Z) và cấu trúc MultiPatch (đa mảnh).
