Progressive Transmission of Vector Map Data over the World Wide Web
Tóm tắt
Within distributed computing environments, access to very large geospatial datasets often suffers from slow or unreliable network connections. To allow users to start working with a partially delivered dataset, progressive transmission methods are a viable solution. While incremental and progressive methods have been applied successfully to the transmission of raster images over the World Wide Web, and, in the form of prototypes, of triangular meshes, the transmission of vector map datasets has lacked a similar attention. This paper introduces a solution to the progressive transmission of vector map data that allows users to apply analytical GIS methods to partially transmitted data sets. The architecture follows a client-server model with multiple map representations at the server side, and a thin client that compiles transmitted increments into a topologically consistent format. This paper describes the concepts, develops an architecture, and discusses implementation concerns.
Tài liệu tham khảo
C.L. Bajaj, V. Pascucci, and G. Zhuang. “Single resolution compression of arbitrary triangular meshes with properties,” IEEE Data Compression Conference, 247-256, 1999a.
C.L. Bajaj, V. Pascucci, and G. Zhuang. “Progressive compression and transmission of arbitrary triangular meshes,” Technical Report, Department of Computer Science, University of Texas at Austin, Austin, TX.http://king.ticam.utexas.edu/CCV/papers/cpm-all.pdf, 1999b.
D.H. Ballard. “Strip trees: A hierarchical representation for curves,” Communications of the ACM, Vol. 24(5):310-321, 1981.
M. Barnsley. Fractals Everywhere, Academic Press: San Diego, 1989.
J.L. Bentley and T.A. Ottman. “Algorithms for reporting and counting geometric intersections,” IEEE Transactions on Computers, Vol. 28(9):643-647, 1979.
M. Bertolotto, L. De Floriani, and E. Puppo. “Multiresolution topological maps,” in M. Molenaar and S. De Hoop (Eds.), Advanced Geographic Data Modelling—Spatial Data Modelling and Query Languages for 2D and 3D Applications, Netherland Geodetic Commission, Publications on Geodesy—New Series, 40, 179-190, 1994.
M. Bertolotto. “Geometric modeling of spatial entities at multiple levels of resolution,” Ph.D. Thesis, Department of Computer and Information Sciences, University of Genova, Italy, 1998.
M. Bertolotto and M. Egenhofer. “Progressive vector transmission,” Proceedings ACMGIS99, Kansas City, MO, 152-157, 1999.
B. Buttenfield. “Scale-dependence and self-similarity in cartographic lines,” Cartographica, Vol. 26(1):79-100, 1989.
B. Buttenfield. “Progressive transmission of vector data on the Internet: A cartographic solution,” proceeding 18th International Cartographic Conference, Ottawa, Canada, 1999.
B. Buttenfield and R. McMaster. “Map generalization: Making rules for knowledge representation,” Longman: London, 1991.
B. Chazelle and H. Edelsbrunner. “An optimal algorithm for intersecting line segments in the plane,” Journal of the Association for Computing Machinery, Vol. 39(1):1-54, 1992
J.W. Cooley and J.W. Tukey. “An algorithm for the machine calculation of complex fourier series,” Math. of Comput., Vol. 19:297-301, 1965.
G. Davis and A. Nosratinia. “Wavelet-based image coding: An overview,” Applied and Computational Control, Signals, and Circuits, Vol. 1(1): 1998.
G. Davis. “A wavelet-based analysis of fractal image compression,” IEEE Transactions on Image Processing, Vol. 7(2):141-154, 1998.
G. Davis. “Implicit image models in fractal image compression,” SPIE Conference on Wavelet Applications in Signal and Image Processing IV, Denver, TX, 1996.
L. De Floriani and E. Puppo. “Hierarchical triangulation for multiresolution surface description,” ACM Transaction on Graphics, Vol. 14(4):363-411, 1995.
L. De Floriani, P. Magillo, and E. Puppo. “Efficient implementation of multi-triangulations,” Proceedings IEEE Visualization '98, Research Triangle Park, NC, USA, 43-50, 1998.
L. De Floriani, P. Marzano, and E. Puppo. “Spatial queries and data models,” in A.U. Frank, I. Campari (Eds.), Spatial Information Theory—A theoretical basis for GIS, Lecture Notes in Computer Science N. 716, Springer-Verlag, 113-138, 1993.
G. Dettori and E. Puppo. “How generalization interacts with the topological and geometric structure of maps,” Proceedings Spatial Data Handling '96, Delft, The Netherlands, 1996.
D.H. Douglas and T.K. Peucker. “Algorithms for the reduction of the number of points required to represent a digitized line or its caricature,” The Canadian Cartographer, Vol. 10(2):112-122, 1973.
M. Eck, T. DeRose, T. Duchamp, and H. Hoppe. “Multiresolution analysis of arbitrary meshes,” Computer Graphics (Proceedings SIGGRAPH '95), 173-182, 1995.
M. Egenhofer. “Spatial SQL: A query and presentation language,” IEEE Transactions on Knowledge and Data Engineering, Vol. 6:86-95, 1994.
M. Egenhofer, A. Frank, and J.P. Jackson. “A topological model for spatial databases,” Proceedings SSD89, Lecture Notes in Computer Science N. Vol. 409:271-286, 1989.
M. Egenhofer and R. Franzosa. “Point-set topological spatial relations,” International Journal of Geographic Information Systems, Vol. 5(2):161-174, 1991.
Y. Fisher (Ed.), Fractal Image Compression: Theory and Application to Digital Images, Springer Verlag: New York, 1995.
D. Flewelling. “Comparing Subsets from Digital Spatial Archives: Point Set Similarity,” Ph.D. Thesis, Department of Spatial Information Science and Engineering, University of Maine, Orono, ME, 1997.
D. Flewelling and M. Egenhofer. “Using digital spatial archives effectively,” International Journal of Geographical Information Science, Vol. 13(8):1-8, 1999.
A. Frank and W. Kuhn. “Cell graph: A provable correct method for the storage of geometry,” Proceedings Spatial Data Handling '86, Seattle, WA, 1986.
R.C. Gonzales and R.E. Woods. Digital Image Processing, Addison-Wesley 1993.
M.F. Goodchild and J. Proctor. “Scale in digital geographic world,” Geographical & Environmental Modelling, Vol. 1(1):5-23, 1997.
R. Güting and M. Schneider. “Realm-based spatial data types: The Rose algebra,” VLDB Journal, Vol. 4:243-286, 1995.
C. Hofmann. “A multi tier framework for accessing distributed, heterogeneous spatial data in a federation based EIS,” Proceedings ACMGIS99, Kansas City, MO, 140-145, 1999.
S. de Hoop, P. van Oosterom, and M. Molenaar. “Topological querying of multiple map layers,” in A.U. Frank, I. Campari (Eds.), Spatial Information Theory—A theoretical basis for GIS, Lecture Notes in Computer Science N. 716, Springer-Verlag, 139-157, 1993.
H. Hoppe. “Progressive meshes,” Proceedings SIGGRAPH96, 99-108, 1996.
B. Junger and J. Snoeyink. “Importance measures for TIN simplification by parallel decimation,” Proceedings Spatial Data Handling '98, Vancouver, Canada, 637-646, 1998a.
B. Junger and J. Snoeyink. “Selecting independent vertices for terrain simplification,” Proceedings WSCG '98, Plzen, Czech Republic, 1998b.
P. Kern and J.D. Carswell. “An investigation into the use of JPEG image compression for digital photogrammetry: Does the compression of images affect measurement accuracy,” Proceedings EGIS94, Paris, France, 1994.
R. Kramer, R. Nikolai, A. Koschel, C. Rolker, P. Lockermann, A. Keitel, R. Legat, and K. Zirm. “WWWUDK: A Web-based environmental metainformation system,” ACM SIGMOD Record, 26(1), 1997.
V. Kumar, A. Bugacov, M. Countinho, and R. Neches. “Integrating geographic information systems, spatial digital libraries and information spaces for conducting humanitarian assistance and disaster relief operations in urban environments,” Proceedings ACMGIS99, Kansas City, MO, 146-151, 1999.
R.B. McMaster and K.S. Shea. “Generalization in digital cartography, Washington DC,” Association of American Geographers, 1992.
J. Morlet and A. Grossman. “Decomposition of hardy functions into square integrable wavelets of constant shape,” Siam. J. Math, Anal., Vol. 15(4):723-736, 1984.
J.C. Müller, R. Weibel, J.P. Lagrange, and F. Salgé. “Generalization: State of the art and issues,” in J.C. Müller, J.P. Lagrange, R. Weibel (Eds.), GIS and Generalization: Methodology and Practice, Taylor and Francis, 3-7, 1995.
OGC (OpenGIS Consortium). “The OpenGIS guide,” introduction to interoperable geoprocessing, Part 1, http://www.ogis.org/guide/guide1.html, 1996a.
OGC (OpenGIS Consortium). “The OpenGIS abstract specification,” http://www.opengis.org/public/abstract.html, 1996b.
F. Preparata and M. Shamos. “Computational geometry: An introduction,” Springer-Verlag, 1985.
E. Puppo and G. Dettori. “Towards a formal model for multiresolution spatial maps,” in M.J. Egenhofer, J.R. Herring (Eds.), Advances in Spatial Databases, Lecture Notes in Computer Science N. 951, Springer Verlag, 152-169, 1995.
U. Rauschenbach, and H. Schumann. “Demand-driven image transmission with levels of detail and regions of interest,” Computers and Graphics, Vol. 23(6):857-866, 1999.
A.H. Robinson, R.D. Sale, J.L. Morrison, and P.C. Muehrcke. “Elements of cartography,” John Wiley: New York, 5th edition, 1984.
A. Saalfeld. “Topologically consistent line simplification with the Douglas-Peucker algorithm,” Cartography and Geographic Information Science, Vol. 26(1):7-18, 1999
H. Samet. The Design and Analysis of Spatial Data Structures, Addison-Wesley: Reading, MA, 1990a.
H. Samet. Applications of Spatial Data Structures, Addison-Wesley: Reading, MA, 1990b.
M. Sondheim, K. Gardels, and K. Buehler. “GIS interoperability,” in P. Longley, M.F. Goodchild, D.J. Maguire and D.W. Rhind (Eds.), Geographical Information Systems: Principles, Techniques, Management and Applications, Second Edition, GeoInformation International: Cambridge, 347-358, 1999.
B.S. Srinivas, R. Ladner, M. Azizoglu, and E.A. Riskin. “Progressive transmission of images using MAP detection over channels with memory,” IEEE Transactions on Image Processing, Vol. 8(4):462-475, 1999.
E.C. Titchmarsh. “Introduction to the theory of Fourier intervals,” Oxford University Press: New York, 1948.
UCGIS (University Consortium for Geographic Information Science). “The UCGIS research agenda: Interoperability”, http://www.ucgis.org, 1996.
M. van Kreveld. “Digital elevation models and TIN algorithms,” Notes for CISM Advanced School on Algorithmic Foundations of GIS, 1996.
H. Wactlar, M. Christel, Y. Gong, and A. Hauptmann. “Lessons learned from building a terabyte digital video library,” IEEE Computer, Vol. 32(2):66-73, 1999.
R. Weibel and G. Dutton. “Generalising spatial data and dealing with multiple representations,” in P. Longley, M.F. Goodchild, D.J. Maguire and D.W. Rhind (Eds.), Geographical Information Systems: Principles, Techniques, Management and Applications, Second Edition, GeoInformation International: Cambridge, 125-155, 1999.
M. Worboys. “A generic model for planar geographic objects,” International Journal of Geographic Information Systems, Vol. 6(5):353-372, 1992.
Y. Zhao and B. Yuan. “A hybrid image compression scheme combining block-based fractal coding and DCT,” Signal Processing: Image Communication, Vol. 8(2):73-78, 1996.
D. Zorin, P. Shroder, and W. Sweldens. “Interactive multiresolution mesh editing,” Computer Graphics (Proceedings SIGGRAPH '97), 259-268, 1997.