GE2215 Lecture 6 Geometric Transformation PDF

GE2215 Lecture 6 Geometric Transformation Dr. Yan Yingwei Department of Geography National University of Singapore © Copyright National University of Singapore. All Rights Reserved.  Recap: Why coordinate systems matter? It is used for: –...

GE2215 Lecture 6 Geometric Transformation Dr. Yan Yingwei Department of Geography National University of Singapore © Copyright National University of Singapore. All Rights Reserved.  Recap: Why coordinate systems matter? It is used for: – Talking about locations and spatial measurements – Creating a new set of spatial data (e.g., GPS) – Acquiring spatial data from other data sources (e.g., an existing geodatabase) – Overlaying/Displaying two or more map layers. They are not going to register spatially unless they are based on the same coordinate system 2 Slides for education purpose only  Recap: Why coordinate systems matter? Interstate highways in Idaho and Montana based on different coordinate systems Interstate highways in Idaho and Montana based on the same coordinate systems 3 Slides for education purpose only  Recap: Geographic Coordinate Systems The geographic coordinate system (GCS) is defined by longitude and latitude Latitude range Longitude range Parallels and Meridians What shape is the earth? Earth surface Simplification Geoid Approximation Earth ellipsoid 4 Slides for education purpose only  Recap: Datum Datum A datum = an ellipsoid + an origin Local datum and geocentric datum Why do we need a local datum? WGS 84 datum – Used by all GPS satellites Singapore datum – SVY21 datum 5 Slides for education purpose only  Recap: Why map projection? Geographic coordinates are spherical coordinates represented by longitudes and latitudes. It is not easy to calculate the distance, direction and area on a curve surface. The commonly used maps are plane-based, which accord with people’s visual and psychological perceptions, and are convenient for the above measurements. The curved surface of the earth is not spreadable Map projection is needed to turn a curve surface to a plane surface 6 Slides for education purpose only  Recap: Universal Transverse Mercator (UTM) PCS Map scale 1/25,000 – 1/50,000 Six-degree division is adopted. The whole earth is divided into 60 zones >1/10,000 Three-degree division is used. The whole Transverse earth is divided into 120 zones Cylindrical Equal-angle 7 Slides for education purpose only  Recap: Spatial coordinate transformation Often, the data sets we have are in different coordinate systems It is a good idea to transform them to the same coordinate system Projection Geographic coordinate Projected coordinate Reprojection Projected coordinate system 1 Projected coordinate system 2 The algorithms mathematical methods of projections and reprojections are not required to master. This can easily be done in most of GIS software 8 Slides for education purpose only  Outline of this lecture Background about geometric transformation Transformation method Control points Root Mean Square error Resampling 9 Slides for education purpose only  Why geometric transformation? Let’s review the map digitization process first Manual Map scanning vectorization A paper map A scanned map A digitized map Both the scanned map (raster data) and the digitized map (vector data) cannot be aligned spatially with layers in GIS because they don’t have spatial references 10 Slides for education purpose only  Why geometric transformation? Geometric transformation can be used to: Assign coordinate systems to digitized maps and images – Scanned paper maps – Remote sensing images http://libmaps.nus.edu.sg/ 11 Slides for education purpose only  Why geometric transformation? Map or image deformations are inevitable during the production process. Some maps and remote sensing images have high geometric precision, while some have low precision Assume we have one map (Map #1) with high geometric precision and another map (Map #2) with low precision. The precision of Map #2 can be improved by Map #1 and geometric transformation 12 Slides for education purpose only  Why geometric transformation? Correct random (non-systematic) distortion (deformation) Jensen (2016) 13 Slides for education purpose only  Systematic vs. Random distortions Systematic distortions Predictable; can be corrected by mathematical formulas (parametric) Often corrected during preprocessing 14 Slides for education purpose only  Systematic vs. Random distortions Random (non-systematic) distortions Corrected statistically by comparing with ground control points (non- parametric) Often done by end-users 15 Slides for education purpose only  Geographic distortions Geometric distortions in imagery may be due to a variety of factors including one or more of the following: The perspective of the sensor optics The motion of the scanning system The motion and (in)stability of the platform The platform altitude, attitude, and velocity The terrain relief, and The curvature and rotation of the Earth Jensen (2016) 16 Slides for education purpose only  Geographic distortions Shape is only preserved at the nadir Shape is distorted at the edge of an image Source: https://www.ssec.wisc.edu/sose/pirs/pirs_m2_footprint.bak 17 Slides for education purpose only  Geographic distortions (Source: http://earthobservatory.nasa.gov/Features/GlobalLandSurvey/page3.php) 18 Slides for education purpose only  Types of geometric transformation Map-to-map transformation Apply to a digitized map Assign a projected coordinate system to the digitized map Convert the map coordinates (e.g., pixel - row 1 & column 3) to projected coordinates Image-to-map transformation Apply to remotely sensed (RS) images Assign a projected coordinate system to the RS map The original RS image may contain some distortions Georeferencing 19 Slides for education purpose only  Essence of geometric transformation Essence of geometric transformation Building the mapping relationships between a map coordinate (𝑢,𝑣) before transformation and a map coordinate (x, y) after transformation x = 𝑓1 𝑢, 𝑣 𝑦 = 𝑓2 𝑢, 𝑣 𝑓1 and 𝑓2 are the geometric transformation functions with a number of parameters 20 Slides for education purpose only  Essence of geometric transformation General steps of geometric transformation Step 1: Select geometric transformation method (𝑓1 and 𝑓2 form) Step 2: Select a number of ground control points (with known x, 𝑦, u, v values) Step 3: Estimate parameters (coefficients) in 𝑓1 and 𝑓2 Step4: Examine the root mean square (RMS) error which is a quantitative measure which determines the quality of geometric transformation Step 5: Use the estimated coefficients and the transformation equations to compute the new x- and y-coordinates x = 𝑓1 𝑢, 𝑣 𝑦 = 𝑓2 𝑢, 𝑣 A new map or image with a user defined projected coordinate system 21 Slides for education purpose only  Outline of this lecture Background about geometric transformation Transformation method Control points Root Mean Square error Resampling 22 Slides for education purpose only  Affine transformation The affine transformation allows rotation, translation, skew and differential scaling, while preserving line parallelism. It is also called rubber sheeting The affine transformation assumes uniformly distorted input 23 Slides for education purpose only  Outline of this lecture Background about geometric transformation Transformation method Control points Root Mean Square error Resampling 24 Slides for education purpose only  Control points Control points play a key role in determining the accuracy of geometric transformation Ground Corresponding control points points (GCPs) Transformation Point with input coordinates Point with output coordinates Map-to-map Selected on the source map Points selected on the (usually map intersections) reference map Points with known real- world coordinates Image-to-map Selected on the image (features Points on the reference that show up clearly as single map distinct pixels, e.g., road Points with known real- intersections, small ponds) world coordinates 25 Slides for education purpose only  Control points Jensen (2016) 26 Slides for education purpose only  Principles for selecting control points Easily identified on both images and maps Maps: Tic points Images: Road intersections, bends of rivers, small prominent features Evenly distributed on the images or maps Closer to the map features of interest (e.g., GCPs near to NUS as the Area of Interest) 27 Slides for education purpose only  Affine transformation The affine transformation is a pair of first-order polynomial equations: x = Au + Bv + C y = Du + Ev + F Output coordinates Input coordinates A, B, C, D, E, F are the transformation coefficients 3 GCPS The number of equations needed should be the same as the number of coefficients. 29 Slides for education purpose only  Affine transformation Second-order polynomial equations: x = 𝑎0 +𝑎1 u + 𝑎2 v + 𝑎3 uv+𝑎4 𝑢2 +𝑎5 𝑣 2 y = 𝑏0 +𝑏1 u + 𝑏2 v + 𝑏3 uv+𝑏4 𝑢2 +𝑏5 𝑣 2 𝑎0 -𝑎5 , 𝑏0 -𝑏5 are the transformation coefficients 30 Slides for education purpose only  Control points Order of Transformation Minimum GCPs required 1 3 Non-linear transformations 2 6 3 10 4 15 5 21 6 28 7 36 8 45 9 55 10 66 Often, more than the minimum number of GCPs are used to: – Enhance the quality of the geometric transformation 31 Slides for education purpose only  Outline of this lecture Background about geometric transformation Transformation method Control points Root Mean Square error Resampling 32 Slides for education purpose only  Root Mean Square error Root Mean Square (RMS) error is a quantitative measure to determine: – The quality of the geometric transformation – The goodness of the control points RMS error measures the deviation between the actual (true) and estimated locations of the control points 33 Slides for education purpose only  Root Mean Square error What are the actual (true) and estimated locations? x = Au + Bv + C y = Du + Ev + F Output coordinates Input coordinates The estimated location can Actual location (𝑥𝑎𝑐𝑢 , 𝑦𝑎𝑐𝑢 ) deviate from its actual location X residual with the transformation equation RMS error (error distance) Estimated location Y residual (𝑥𝑒𝑠𝑡 ,𝑦𝑒𝑠𝑡 ) 34 Slides for education purpose only  Root Mean Square error The output RMS error of the control point = (𝑥𝑎𝑐𝑢 − 𝑥𝑒𝑠𝑡 )2 +(𝑦𝑎𝑐𝑢 − 𝑦𝑒𝑠𝑡 )2 X residual Y residual If there are 3 control points: The total RMS error (𝑥𝑎𝑐𝑢,1 − 𝑥𝑒𝑠𝑡,1 )2 +(𝑦𝑎𝑐𝑢,1 − 𝑦𝑒𝑠𝑡,1 )2 +(𝑥𝑎𝑐𝑢,2 − 𝑥𝑒𝑠𝑡,2 )2 +(𝑦𝑎𝑐𝑢,2 − 𝑦𝑒𝑠𝑡,2 )2 +(𝑥𝑎𝑐𝑢,3 − 𝑥𝑒𝑠𝑡,3 )2 +(𝑦𝑎𝑐𝑢,3 − 𝑦𝑒𝑠𝑡,3 )2 = 3 35 Slides for education purpose only  Root Mean Square error The total RMS error: 𝑛 𝑛 Output ෍(𝑥𝑎𝑐𝑢,𝑖 − 𝑥𝑒𝑠𝑡,𝑖 )2 + ෍(𝑦𝑎𝑐𝑢,𝑖 − 𝑦𝑒𝑠𝑡,𝑖 )2 /𝑛 𝐼=1 𝐼=1 X residual Y residual RMS error can only be computed when the number of GCPs are more than the minimum number required 36 Slides for education purpose only  Root Mean Square error 37 Slides for education purpose only  Root Mean Square error The smaller RMS error is, the better But never expect the RMS error to be zero To ensure the accuracy of geometric transformation, the RMS error should be within a tolerance value So what tolerance value do you choose? 38 Slides for education purpose only  RMS error tolerance The tolerance value is often defined by the data producer It can vary by the accuracy and the map scale or by the ground resolution of the input data An RMS error (output) of < 6 meters is acceptable if the input map is a 1:24,000 scale USGS quadrangle map An RMS error (input) of < 1 pixel is probably acceptable for a Landsat Thematic Mapper (TM) scene with a ground resolution of 30 meters 39 Slides for education purpose only  RMS error tolerance How to reduce RMS errors? 1. Choose better control points 2. Drop the ones with large RMS errors 3. Choose higher level model 4. Add more control points RMS error 40 Slides for education purpose only  Outline of this lecture Background about geometric transformation Transformation method Control points Root Mean Square error Resampling 41 Slides for education purpose only  Resampling of pixel values (e.g., elevation value, temperature value) x = Au + Bv + C y = Du + Ev + F The affine transformation equations build the mapping relations between the locations of pixels on the original and new images However, the new image has no pixel values (a blank image without pixel values such as temperature values) Resampling means filling each pixel of the new image with a value or derived value from the original image 42 Slides for education purpose only  Resampling of pixel values According to the transformation model, the pixel 𝑃′ in the output product corresponds to coordinate (1.8, 1.3), which represents the (1.8, 1.3) 1.8th row, and the 1.3rd column in the original image. So, what should the cell value be for the coordinate (1.8, 1.3)? x = Au + Bv + C y = Du + Ev + F 43 Slides for education purpose only  Resampling of pixel values Three commonly used resampling methods are: 1. Nearest neighbor resampling 2. Bilinear interpolation (distance-weighted) 3. Cubic convolution (distance-weighted) The above three methods are listed in order of increasing complexity and accuracy 44 Slides for education purpose only  Nearest neighbor resampling Step 1: In the new image, the coordinates of each pixel are transformed using the transformation equation to determine its corresponding location in the original image Step 2: Find the closest pixel to the corresponding location Step 3: Fill the pixel in the new image with the value of the closest pixel mentioned above There is a pixel in the new Easy to understand Quick to compute image, and its corresponding location in the old image is at Not high in pixel accuracy a. The nearest pixel to a is A 45 Slides for education purpose only  Nearest neighbor resampling (1.8, 1.3) What is the closest pixel to (1.8, 1.3)? 46 Slides for education purpose only  Bilinear interpolation Step 1: In the new image, the coordinates of each pixel are transformed using the transformation equation to determine its corresponding location in the original image (the same) Step 2: Find the four nearest pixels to the corresponding location Step 3: Fill the pixel in the new image with the value derived from three linear interpolations and the four nearest pixels mentioned above x = Au + Bv + C y = Du + Ev + F 47 Slides for education purpose only  Bilinear interpolation Smaller distance means larger weight First interpolation: 0.6 0.4 Pixel value 𝑎 = (1 − 0.4) ∗ 5 + (1 − 0.6) ∗ 10 = 7 Second interpolation: 0.5 Pixel value 𝑏 = (1 − 0.4) ∗ 10 + (1 − 0.6) ∗ 15 = 12 Third interpolation: 0.5 Pixel value 𝑥 = 0.5 ∗ 𝑎 + 0.5 ∗ 𝑏 = 9.5 x (2.5, 2.6) corresponds Fast to compute Smoother results to the location in the old image More accurate than nearest neighbor 48 Slides for education purpose only  Cubic convolution Find the 16 nearest pixels Five cubic polynomial interpolations (i.e., non-linear interpolation) to generate the average pixel value Can sharpen the image Produce smoother results (remove noise) than bilinear interpolation Computationally intensive (takes much longer time to process) 49 Slides for education purpose only  Other uses of resampling Resampling is needed whenever there is a change of cell location or cell size between the input raster and the output raster Apart from geometric transformation, resampling is also involved in: Projecting a raster from one coordinate system to another https://source.opennews.org/articles/choosing-right-map-projection/ 50 Slides for education purpose only  Other uses of resampling Resampling is needed whenever there is a change of cell location or cell size between the input raster and the output raster Apart from geometric transformation, resampling is also involved in: Projecting a raster from one coordinate system to another http://www.ai.sri.com/digital-earth/proposal/3d-representation Pyramiding: a common technique for Image pyramiding is used in displaying large raster data sets Google map to speed the displaying process of satellite 51 images Slides for education purpose only  Summary Background about geometric transformation Why geometric transformation? Geographic distortions Two types of geometric transformation Map-to-map and image-to-map transformation Transformation method Affine transformation Control points Minimum number required Principles of selecting control points 52 Slides for education purpose only  Summary Root Mean Square (RMS) error How to compute RMS error? How to reduce RMS error? Resampling What is resampling? Three commonly used resampling methods Nearest neighbor Bilinear interpolation Cubic interpolation Other uses of resampling 53 Slides for education purpose only  THANK YOU 54 Slides for education purpose only