Phát triển thuật toán thủy vân mạng đường phố bền vững đối với phép biến đổi co giãn bản đồ

Bài viết đề xuất một thuật toán cải tiến thủy vân mạng đường phố đó để bổ sung tính bền vững của lược đồ thủy vân đối với phép biến đổi co giãn bản đồ. Ngoài ra, thuật toán cải tiến đề xuất có thể giúp cho dấu thủy vân được nhúng vào bản đồ số hiệu quả hơn và cùng có độ phức tạp như thuật toán gốc.
Nội dung trích xuất từ tài liệu:
Phát triển thuật toán thủy vân mạng đường phố bền vững đối với phép biến đổi co giãn bản đồ KHOA HỌC CÔNG NGHỆ - ĐẠI HỌC HÙNG VƯƠNG PHÁT TRIỂN THUẬT TOÁN THỦY VÂN MẠNG ĐƯỜNG PHỐ BỀN VỮNG ĐỐI VỚI PHÉP BIẾN ĐỔI CO GIÃN BẢN ĐỒ Phạm Đức Thọ 1, Đặng Văn Đức 2 1 Trường Đại học Hùng Vương 2 Viện Công nghệ thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam TÓM TẮT Lược đồ thủy vân số bản đồ vector dạng mạng đường phố được đề xuất bởi Yu-Chi Pu & I-Chang Jou có tính ẩn và tính bền vững cao, có khả năng chống được các tấn công như phép giản lược Douglas Peucker, phép cắt xén, đảo thứ tự các đỉnh, thêm nhiễu,… Tuy nhiên, khi bản đồ vector được co giãn (scaling) theo một tỷ lệ nào đó, tương ứng các tọa độ của các điểm được thay đổi theo tỷ lệ đó, thì khóa bí mật là bề rộng các vành - không còn dùng để trích được dữ liệu thủy vân được nữa. Trong báo cáo này chúng tôi đề xuất một thuật toán cải tiến thủy vân mạng đường phố đó để bổ sung tính bền vững của lược đồ thủy vân đối với phép biến đổi co giãn bản đồ. Ngoài ra, thuật toán cải tiến đề xuất có thể giúp cho dấu thủy vân được nhúng vào bản đồ số hiệu quả hơn và cùng có độ phức tạp như thuật toán gốc. Từ khóa: Watermarking, street-network vector map,scale attack. I. MỞ ĐẦU Các lớp bản đồ vector dạng mạng đường phố có nhiều ứng dụng trong các thiết bị di động hiện nay như là tìm đường đi, tìm vị trí đối tượng, v.v... Chúng có một số đặc trưng như có nhiều giao điểm giữa các đường không khép kín, có nhiều đỉnh bậc cao. Các đỉnh có bậc cao thường giữ vị trí quan trọng và ít bị thay đổi qua các phép tấn công vì chúng liên quan đến giá trị sử dụng của bản đồ số, chúng được gọi là các điểm đặc trưng. Do vậy các thuật toán thủy vân căn cứ trên các đỉnh đặc trưng thường có tính bền vững cao qua các phép tấn công lên bản đồ mạng đường phố. Lược đồ thủy vân số bản đồ vector dạng mạng đường phố đã được trình bày bởi Yu-Chi Pu & I- Chang Jou có tính ẩn và tính bền vững cao, có khả năng chống được các tấn công như phép giản lược Douglas Peucker, phép cắt xén, đảo thứ tự các đỉnh, thêm nhiễu, … Tuy nhiên, nó không bền vững đối với phép biến đổi tỷ lệ (co giãn) bản đồ. Khi bản đồ vector được co giãn (đều) theo một tỷ lệ nào đó, tương ứng các tọa độ của các điểm được thay đổi theo tỷ lệ đó, thì khóa bí mật là bề rộng các vành - không còn dùng để trích được dữ liệu thủy vân được nữa. 2. LƯỢC ĐỒ THỦY VÂN MẠNG ĐƯỜNG PHỐ CỦA YU-CHI PU & I-CHANG YOU A. Phân đoạn bản đồ Các bản đồ vector số chứa các thông tin địa lý chi tiết và thường chứa tới hàng chục nghìn đỉnh. Để giảm bớt tính toán và làm tăng tính bền vững, các bản đồ thường được chia thành các bản đồ con hoặc các khối. Một số cách tiếp cận chia bản đồ thành các khối cùng cỡ (cùng số đỉnh). Tuy nhiên chúng gặp phải vấn đề về sự đồng bộ hóa. Phần này chúng tôi trình bày một cách ổn định để phân đoạn (phân nhóm) bản đồ mà không cần sử dụng bản đồ gốc cũng như các điểm tham chiếu. Các bước phân đoạn bản đồ gốc như sau: KHCN 2 (31) - 2014 107 KHOA HỌC CÔNG NGHỆ - ĐẠI HỌC HÙNG VƯƠNG Bước 1. Đơn giản bản đồ bằng thuật toán Douglas-Peucker Phép giản lược Douglas Peucker (DP) được dùng để thu được bản đồ giản lược từ bản đồ gốc, do Douglas và Peucker đề xuất năm 1973. Thuật toán DP khá nổi tiếng cho việc lược giản các bản đồ đa đoạn (polyline). Ta xét một polyline với hai điểm đầu mút A và B và một sai số xấp xỉ . Đầu tiên, tìm một điểm C trên polyline mà có khoảng cách lớn nhất tới đường thẳng A-B. Nếu khoảng cách đó bé hơn thì polyline được xấp xỉ bởi đường thẳng A-B. Nếu không thì lặp lại quá trình xấp xỉ trên với các đường A-C và C-B để thu được xấp xỉ cuối cùng. Giả mã được cho trong Thuật toán 1. Thuật toán 1. Thuật toán Douglas-Peucker. function DouglasPeucker(PointList[], epsilon) //Find the point with the maximum distance dmax = 0; index = 0; for i = 2 to (length(PointList) - 1) d = OrthogonalDistance(PointList[i], Line(PointList[1], PointList[end])); if d > dmax then index = i; dmax = d; endif; endfor; //If max distance is greater than epsilon, recursively simplify if dmax >= epsilon then //Recursive call recResults1[] = DouglasPeucker(PointList[1...index], epsilon); recResults2[] = DouglasPeucker(PointList[index...end], epsilon); // Build the result list ResultList[] = {recResults1[1...end-1] recResults2[1...end]}; else ResultList[] = {PointList[1], PointList[end]}; endif; //Return the result return ResultList[]; end./*Function*/ Hình 1 biểu diễn quá trình giản lược bản đồ bằng thuật toán DP. Để thuận tiện trong tính toán, đồng thời làm tăng tính bền vững của dấu thủy vân với các bản đồ lớn, ta lấy để loại bỏ mọi đỉnh bậc hai của bản đồ. 108 KHCN 2 (31) - 2014  KHOA HỌC CÔNG NGHỆ - ĐẠI HỌC HÙNG VƯƠNG Hình 1: Quá trình lược giản bản đồ bằng thuật toán Douglas-Peucker Bước 2. Chia bản đồ đã giản lược thành các nhóm khác nhau. Nói chung, các điểm với bậc lớn (có nhiều polyline nối với nhau tại điểm này) là các điểm đặc trưng quan trọng trong một bản đồ vector. Chúng ta nghiên cứu các điểm với bậc lớn hơn hoặc bằng một ngưỡng chọn trước trong bản đồ lược giản như là các điểm đặc trưng, gọi là ngưỡng đặc trưng. Một điểm đặc trưng và các điểm láng giềng nối với nó hì ...