Hexagonal discrete global GRID systems for geospatial computing

• Autorzy: Sahr K.
• Języki publikacji: EN

Abstrakty

EN

Advanced geospatial applications often involve complex computing operations performed under sometimes severe resource constraints. These applications primarily rely on traditional raster and vector data structures based on square lattices. But there is a significant body of research that indicates that data structures based on hexagonal lattices may be a superior alternative for efficient representation and processing of raster and vector data in high performance applications. The advantages of hexagonal rasters for image processing are discussed, and hexagonal discrete global grid systems for location coding are introduced. The combination provides an efficient, unified approach to location representation and processing in geospatial systems.

Słowa kluczowe

EN

mapping; integration; modelling; data structures; representation; global; multiresolution

PL

mapowanie; integracja; modelowanie; struktura danych; reprezentacja; multirozdzielczość; globalność

• Wydawca: Zarząd Główny Stowarzyszenia Geodetów Polskich
• Czasopismo: Archiwum Fotogrametrii, Kartografii i Teledetekcji
• Rocznik: 2011
• Tom: Vol. 22
• Strony: 363--376
• Opis fizyczny: Bibliogr. 70 poz.

Twórcy

autor

Sahr K.

• Department of Computer Science, Southern Oregon University, Ashland, Oregon, 97520 USA

Bibliografia

• Abu-Bakar, S., Green, R. J., 1996. Detection of edges based on hexagonal pixel formats. 3rd International Conference on Signal Processing Proceedings (ICSP-96), Beijing, China, pp. 1114–1117.
• Allen, J.D., 2005. Perfect reconstruction filter banks for the hexagon grid, Proceedings of the Fifth International Conference on Information, Communications and Signal Processing, pp. 73–76.
• Anderson, H.L., 1979. Time projection spectrometer, Informal Report LA-8165-MS, Los Alamos Scientific Laboratory, Los Alamos, NM.
• Bell, S.B.M., Holroyd, F.C., 1991. Tesseral amalgamators and hierarchical tessellations. Image and Vision Computing, 9, pp. 313-328.
• Burt, P.J., 1980. Tree and pyramid structures for coding hexagonally sampled binary images. Computer Graphics and Image Processing, 14, pp. 271–280.
• Christaller, W. (1966). Central places in southern Germany. Prentice Hall, Englewood Cliffs, NJ.
• Coleman, S.A., Scotney, B.W., Herron, M.G., 2004. A systematic design procedure for scalable nearcircular Laplacian of Gaussian operators. Proceedings of the International Conference on Pattern Recognition (ICPR2004), Cambridge, MA, pp. 700-703.
• Coleman, S.A., Scotney, B.W., Gardiner, B., 2009. Design of feature extraction operators for use on biologically motivated hexagonal image structures. Proceedings of the IAPR Conference on Machine Vision and Applications (MVA), Japan, pp. 178-181.
• Conway, J.H., Sloane, N.J.A., 2010. Sphere packings, lattices and groups. 3rd ed., Springer Verlag, New York, 703 pp.
• Cressie, N., Johannesson, G., 2008. Fixed rank kriging for very large spatial data sets. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 70(1), pp. 209–226.
• Dacey, M.F., 1965. The geometry of central place theory. Geografiska Annaler: Series B, Human Geography, 47(2), pp. 111-124.
• Davies, E.R., 1984. Circularity - a new principle underlying the design of accurate edge orientation operators. Image and Vision Computing, 2(3), pp. 134 -142.
• Delbrueck, T., 1993. Silicon retina with correlation-based, velocity-tuned pixels. IEEE Transactions on Neural Networks, 4(3), pp. 529-541.
• Dersanambika, K.S., Krithivasan, K., Martín-Vide, C., Subramanian, K.G., 2005. Local and recognizable hexagonal picture languages. International Journal of Pattern Recognition and Artificial Intelligence, 19(7), pp. 853-871.
• Dutton, G., 1999. A hierarchical coordinate system for geoprocessing and cartography. Springer Verlag, New York, 230 pp.
• Gardiner, B., Coleman, S.A., Scotney, B.W., 2008. Multi-scale feature extraction in a sub-pixel virtual hexagonal environment. Proceedings of the International Machine Vision and Image Processing Conference, pp. 111-116.
• Gardiner, B., Coleman, S.A., Scotney, B.W., 2009. Fast multiscale operator development for hexagonal images. Proceedings of the 31st Annual Pattern Recognition Symposium of the German Association for Pattern Recognition (DAGM 2009), Jena, Germany, pp. 282-291.
• Gardiner, B., Coleman, S.A., Scotney, B.W., 2010. Comparison of hexagonal image resampling techniques. Proceedings of the 14th International Machine Vision and Image Processing Conference (IMVIP 2010), Limerick, Ireland, pp. 102-115.
• Gargantini, I., 1982. An effective way to represent quadtrees. Communications of the Association for Computing Machinery, 25(12), pp. 905-910.
• Gibson, L., Lucas, D., 1982. Spatial data processing using generalized balanced ternary. Proceedings of the IEEE Computer Society Conference on Pattern Recognition and Image Processing, Las Vegas, NV, pp. 566-571.
• Golay, M.J.E., 1969. Hexagonal parallel pattern transformations. IEEE Transactions on Computers, 18(8), pp. 733-740. Grigoryan, A.M., 2002. Efficient algorithms for computing 2-D hexagonal Fourier transforms. IEEE Transactions on Signal Processing, 50, pp. 1438– 1448.
• Guyon, O., Roddier, F., 2002. A nulling wide field imager for exoplanets detection and general astrophysics. Astronomy & Astrophysics, 391(379).
• Hauschild, R., Hosticka, B.J., Müller, S., Schwarz, M., 1996. A CMOS optical sensor system performing image sampling on a hexagonal grid. Proceedings of the 22nd European Solid-State Circuits Conference.
• He, X., Jia, W., Wu, Q., Hintz, T., 2006. Description of the cardiac movement using hexagonal image structures. Computerized Medical Imaging and Graphics, 30(6-7), pp. 377-382.
• He, X., Wu, Q., Jia, W., Hintz, T., 2008. Edge detection on hexagonal structure. Journal of Algorithms & Computational Technology, 2(1), pp. 61-78.
• Hoedlmoser, H., Varner, G., Cooney, M., 2009. Hexagonal pixel detector with time encoded binary readout. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment, 599(2-3), pp. 152-160.
• Hoffmann M, Hilton-Taylor C., Angulo A., Böhm M., Brooks T.M., Butchart S.H., Carpenter K.E., Chanson J., Collen B., Cox N.A., Darwall W.R., Dulvy N.K., Harrison L.R., Katariya V., Pollock C.M., Quader S., Richman N.I., Rodrigues A.S., Tognelli M.F., Vié J.C., Aguiar J.M., Allen D.J., Allen G.R., Amori G., Ananjeva N.B., Andreone F., Andrew P., Aquino Ortiz A.L., Baillie J.E., Baldi R., Bell B.D., Biju S.D., Bird J.P., Black-Decima P., Blanc J.J., Bolaños F., Bolivar-G W., Burfield I.J., Burton J.A., Capper D.R., Castro F., Catullo G., Cavanagh R.D., Channing A., Chao N.L., Chenery A.M., Chiozza F., Clausnitzer V., Collar N.J., Collett L.C., Collette B.B., Cortez Fernandez C.F., Craig M.T., Crosby M.J., Cumberlidge N., Cuttelod A., Derocher A.E., Diesmos A.C., Donaldson J.S., Duckworth J.W., Dutson G., Dutta S.K., Emslie R.H., Farjon A., Fowler S., Freyhof J., Garshelis D.L., Gerlach J., Gower D.J., Grant T.D., Hammerson G.A., Harris R.B., Heaney L.R., Hedges S.B., Hero J.M., Hughes B., Hussain S.A., Icochea M.J., Inger R.F., Ishii N., Iskandar D.T., Jenkins R.K., Kaneko Y., Kottelat M., Kovacs K.M., Kuzmin S.L., La Marca E., Lamoreux J.F., Lau M.W., Lavilla E.O., Leus K., Lewison R.L., Lichtenstein G., Livingstone S.R., Lukoschek V., Mallon D.P., McGowan P.J., McIvor A., Moehlman P.D., Molur S., Muñoz Alonso A., Musick JA., Nowell K., Nussbaum R.A., Olech W., Orlov N.L., Papenfuss T.J., Parra-Olea G., Perrin W.F., Polidoro B.A., Pourkazemi M., Racey P.A., Ragle J.S., Ram M., Rathbun G., Reynolds R.P., Rhodin A.G., Richards S.J., Rodríguez L.O., Ron S.R., Rondinini C., Rylands A.B., Sadovy de Mitcheson Y., Sanciangco J.C., Sanders K.L., Santos-Barrera G., Schipper J., Self-Sullivan C., Shi Y., Shoemaker A., Short F.T., Sillero-Zubiri C., Silvano D.L., Smith K.G., Smith A.T., Snoeks J., Stattersfield A.J., Symes A.J., Taber A.B., Talukdar B.K., Temple H.J., Timmins R., Tobias J.A., Tsytsulina K., Tweddle D., Ubeda C., Valenti S.V., van Dijk P.P., Veiga L.M., Veloso A., Wege D.C., Wilkinson M., Williamson E.A., Xie F., Young B.E., Akçakaya H.R., Bennun L., Blackburn T.M., Boitani L., Dublin H.T., da Fonseca G.A., Gascon C., Lacher T.E Jr., Mace G.M., Mainka S.A., McNeely J.A., Mittermeier R.A., Reid G.M., Rodriguez J.P., Rosenberg A.A., Samways M.J., Smart J., Stein B.A., Stuart S.N., 2010. The impact of conservation on the status of the world’s vertebrates. Science, 330(6610), pp. 1503-1509.
• Iwanczyk, J.S., Patt, B.E., Tull, C.R., Segal, J.D., Keme, C.J., Bradley, J., Hedman, B., Hodgson, K.O., 1999. Large area silicon drift detectors for X-rays — new results. IEEE Transactions on Nuclear Science, 46, pp. 284-288.
• Jiang, Q., 2009. Orthogonal and Biorthogonal √3-Refinement Wavelets for hexagonal data processing. IEEE Transactions on Signal Processing, 57(11), pp. 4304 - 4313.
• Jiang, Z., Qinghui, X., Linghong, Z., 2010. 3D reconstruction based on hexagonal pixel’s dense stereo matching. Applied Mechanics and Materials, 20-23, pp. 487-492.
• Knuth, D., 1998. The art of computer programming; Volume 2: Seminumerical algorithms. Addision-Wesley, Menlo Park, CA, 762 pp.
• Laine, A.F., Schuler, S., Huda, W., Honeyman-Buck, J.C., Steinbach, B.G., 1993. Hexagonal wavelet processing of digital mammography. Proceedings of Medical Imaging 1993: Image Processing, Newport Beach, CA.
• Luczak, E., Rosenfeld, A., 1976. Distance on a hexagonal grid. IEEE Transactions on Computers, 25(5), pp. 532-533.
• Mersereau, R.M., 1979. The processing of hexagonally sampled two-dimensional signals. Proceedings of the IEEE, 67, pp. 930-949.
• Middleton, L., Sivaswamy, J., 2001. Edge detection in a hexagonal-image processing framework. Image and Vision Computing, 19, pp. 1071-1081.
• Middleton, L., 2002. The co-occurrence matrix in square and hexagonal lattices. Proceedings of the 7th International Conference on Control, Automation, Robotics and Vision, ICARV 2002, Singapore, pp. 90-95.
• Middleton, L., Sivaswamy, J., 2005. Hexagonal Image Processing; A Practical Approach, Springer-Verlag, London, 254 pp.
• Miller, E., 1999. Alternative tilings for improved surface area estimates by local counting algorithms. Computer Vision and Image Understanding (CVIU), 74, pp. 193-211.
• Petersen, D.P., Middleton, D., 1962. Sampling and reconstruction of wave-number-limited functions in N-dimensional Euclidean spaces. Information Control, 5, pp. 279-323.
• Riley, D.T., Harmann, W.M., Barrett, S.F., Wright, C.H.G., 2008. Musca domestica inspired machine vision sensor with hyperacuity. Bioinspiration and Biomimetics, 3(2).
• Rogers, C.A., 1964. Packing and Covering. Cambridge University Press, 111 pp.
• Roorda, A., Metha, A.B., Lennie, P., Williams, D.R., 2001. Packing arrangement of the three cone classes in primate retina. Vision Research, 41, pp. 1291-1306.
• Rosenfeld, A., 1970. Connectivity in digital pictures. Journal of the Association for Computing Machinery, 17, pp. 146-160.
• Sahr, K., 2002. DGGRID version 3.1b: User documentation for discrete global grid software. Retrieved July 14, 2011, from http://discreteglobalgrids.org/dggrid/docs/dggriddoc31.pdf.
• Sahr, K., White, D., Kimerling, A.J., 2003. Geodesic discrete global grid systems. Cartography and Geographic Information Science, 30(2), pp. 121–134.
• Sahr, K., 2008. Location coding on icosahedral aperture 3 hexagon discrete global grids. Computers, Environment and Urban Systems, 32(3), pp. 174-187.
• Sahr, K., 2010. Central Place Indexing Systems, U.S. Patent Application 2010/054550.
• Sahr, K., White, D., 2010. The superfund_21ha indexing system. Unpublished documentation, Southern Oregon University, Ashland, Oregon.
• Scotney, B.W., Coleman, S.A., 2007. Improving angular error via systematically designed nearcircular Gaussian-based feature extraction operators. Pattern Recognition, 40(5), pp. 1451-1465.
• Shima, T., Saito, S., Nakajima, M., 2009. Design and evaluation of more accurate gradient operators on hexagonal lattices. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(6), pp. 961-973.
• Shima, T., Sugimoto, S., Okutomi, M., 2010. Comparison of image alignment on hexagonal and square lattices. Proceedings of the 17th IEEE International Conference on Image Processing, pp. 141-144.
• Siromoney, G., Siromoney, R., 1976. Hexagonal arrays and rectangular blocks. Computer Graphics and Image Processing, 5, pp. 353-381
• Smeraldi, F., Rob, M.A., 2003. Ranklets on hexagonal pixel lattices. Proceedings of the British Machine Vision Conference, Norwich, UK, vol. 1, pp. 163-170.
• Snyder, W., Qi, H., Sander, W., 1999. A coordinate system for hexagonal pixels. Proceedings of SPIE, the International Society for Optical Engineering, 3661, pp. 716–727.
• Sossa-Azuela, J.H., Cuevas-Jiménez, E.V., Zaldivar-Navarro, D., 2010. Computation of the Euler number of a binary image composed of hexagonal cells. Journal of Applied Research and Technology, 8(3), pp. 340-351.
• Staunton, R.C., 1989. The design of hexagonal sampling structures for image digitization and their use with local operators. Image and Vision Computing, 7(3), pp. 162-166.
• Subramanian, K.G., 1979. Hexagonal array grammars. Computer Graphics and Image Processing, 10(4), pp. 388-394.
• Suess, M., Matos, P., Gutierrez, A., Zundo, M., Martin-Neira, M., 2004. Processing of SMOS level 1c data onto a discrete global grid. Proceedings of the IEEE International Geoscience and Remote Sensing Symposium, pp. 1914-1917.
• Tong, X., Ben, J., Wang, Y., 2010. A new effective hexagonal discrete global grid system: hexagonal quad balanced structure. Proceedings of Geoinformatics 2010, pp. 1-6.
• Tremblay, M., d'Anjou, M., Poussart, D., 1993. Hexagonal sensor with imbedded analog image processing for pattern recognition. Custom Integrated Circuits Conference, Proceedings of the IEEE 1993, San Diego, CA, pp. 12.7.1-12.7.4.
• Veni, S., Narayanankutty, K.A., Fayas., A, 2011. Employing hexagonal wavelets for detecting microcalcification in digital mammography. ICGST International Journal on Graphics, Vision and Image Processing, GVIP, 11(I), pp. 59-66.
• Verbrugge, C., 1997. Hex grids. Unpublished manuscript, McGill University, Montreal, Quebec, Canada.
• Vince, A., Zheng, X., 2007. Computing the discrete Fourier transform on a hexagonal lattice. Journal of Mathematical Imaging and Vision, 28, pp. 125-133.
• Vince, A., Zheng, X., 2009. Arithmetic and Fourier transform for the PYXIS multi-resolution digital earth model. International Journal of Digital Earth, 2(1), pp. 59-79.
• Vitulli, R., 2002. Aliasing effects mitigation by optimized sampling grids and impact on image acquisition chains. Geoscience and Remote Sensing Symposium, pp. 979-981.
• White, D., Kimerling, A.J., Overton, W.S., 1992. Cartographic and geometric components of a global sampling design for environmental monitoring. Cartography and Geographic Information Systems, 19(1), pp. 5-22.
• White, D., 2000. Global grids from recursive diamond subdivisions of the surface of an octahedron or icosahedrons. Environmental Monitoring and Assessment, 64(1), pp. 93-103.
• Woldenberg, M.J., 1979. A periodic table of spatial hierarchies. In: Philosophy in Geography. D. Reidel, Dordrecht, Netherlands, pp. 429-456.
• Wuthrich, C.A., Stucki, P., 1991. An algorithmic comparison between square- and hexagonal-based grids. CVGIP: Graphical Models and Image Processing, 53(4), pp. 324-339.
• Yale, P.B., 1968. Geometry and symmetry. Holden-Day, San Francisco, 288 pp.