Transcript Document
Spatial Information Systems (SIS) COMP 30110 Raster-based structures (2) Data conversion Efficiency issues • The simple raster-based structure of the example is inefficient in terms of data storage: regardless of the data distribution it uses the same amount of disk space • This can also degrade data processing • Two issues: – compression methods (efficiently store data) – scan order (how to scan the data in the array) Scan-order methods • Mainly concerned with performance in terms of data processing • They define a total order on the cells of a 2D grid: assign numbers to the cells • Also called Space-filling curves • Some methods partially preserve proximity: two cells that are close in space are likely to be close in the total order • In our examples, we consider space-filling curves on an underlying N X N array of cells (grid), where N = 2d (i.e., a complete quadtree with depth d) Space-filling curves • They define a total order (i.e., a linear order) on the cells of a 2D grid: assign numbers to the cells • In other words we embed a 2-dimensional space into a 1-dimensional space • Cell numbers should be easy to compute Row method Scans one row at a time Row-prime method Scans one row at a time but reverses every second row Morton scan method Morton curve (it orders the quadrants of a quadtree as SW, SE, NW, NE) This method preserves spatial proximity relatively well Morton scan method (cont.d) •Also called Z-buffering: when the reverse order NW,NE, SW, SE is considered this method repeats a Z-like shape with four neighboring cells as a unit and repeats the shape at all levels NW NE SW SE 0 1 4 5 2 3 6 7 8 9 12 13 10 11 14 15 • Other variants are used too Z-order and Z-values • Coding of cells: – Partition the space recursively into two halves (alternating X and Y dimension) – Left and bottom parts are assigned code 0 – Right and top parts are assigned code 1 Z-order and Z-values (cont.d) • Example: 1 0 1 1 1 0 0111 (7) 0 010000 (16) 0 1 0 10 (2) 0 1 • Z-value: (n,l) n = decimal value of the bit code l = level, i.e., number of bits Peano-Hilbert curve Use of a U-like shape that repeats at all levels Remarks Vector data: focus on spatial objects Raster data: focus on the underlying space Vector data: objects are explicitly stored Raster data: objects must be “extracted” Remarks (cont.d) We have seen data structures for vector data and raster data In vector data structures, topology is explicit: a subset of the topological/connectivity relations is explicitly stored In raster data structures, topology is implicit: topological relations must be calculated (generally, use of MBRs) Data conversion Intra-format conversion: – raster-to-raster – vector-to-vector Inter-format conversion: – raster-to-vector – vector-to-raster Raster-to-raster Raster formats differ in the way they are stored: – different layers in different files with same resolution – pixels stored sequentially with all data values (corresponding to different layers) stored after each pixel – etc. Conversion between raster formats requires reorganisation of the raster cells and their corresponding data values (relatively simple operation) Vector-to-vector Different vector formats are based on different data structures Converting from one format to another requires converting from one data structure to another (more tricky) Raster-to-vector This type of conversion must start with assumptions about the raster and vector representation of data For example, in a binary image, if a point occurs inside a cell, the cell value is 1, otherwise is 0 (interior black, exterior white) Connectivity: two different ways to connect adjoining pixels – only orthogonally (4-connected) – orthogonally and diagonally (8-connected) Raster-to-vector (cont.d) 4-connected neighborhood: only pixels located in one of the four positions with respect to a given pixel are considered connected to it: immediately above, below, left, right Raster-to-vector (cont.d) 8-connected neighborhood: adjoining cells that are diagonally located are also considered connected to the pixel Raster-to-vector (cont.d) Other assumptions must be made in relation to the orientation of the resulting vector and its thickness An orthogonal vector (vector parallel to either x or y axis) with unit width can be converted from its raster structure using the 4-connected approach simply by joining adjacent pixels by unit vectors Orthogonal polygons can similarly be constructed Raster-to-vector (cont.d) To extract a non-orthogonal vector with unit width from the corresponding raster structure, the 4-connected approach results in distortion because such a vector can only be represented by horizontal and vertical line segments, which lie in the general direction of the vector as fragmented segments Raster-to-vector (cont.d) Consequently a polygon with several non-orthogonal vectors results in a high degree of distortion 8-connected approach results in a less distorted image Extracting correctly polygons and lines from a raster images is still a semi-automatic process Vector-to-raster Converting a vector to a raster representation involves overlaying the vector to a raster array and identifying the pixels that the vector intersects This approach often produces a stair-step distortion (aliasing) Antialiasing: gray scale pixels according to coverage measures of the pixel by the vector (e.g., length of the intersection)