Geometric Matching Algorithms for Terrain Data

Abstract

Computational geometry is a field of theoretical computer science. The main purpose of this field is to design algorithms for problems which are related with geometric figures such as points, lines, polygons, and high-dimensional objects. Computational geometry has risen since 1970s as people found that many existing problems in theoretical computer science could be abstracted to geometric figures and their relations. These abstractions were quite intuitive, enabling people to solve the problems in simple and elegant ways.

Shape matching has been studied for a long time as a main subfield of the computational geometry. The problems in shape matching concern how to measure the similarity between geometric objects and have been widely studied in various applications.

Terrain matching is a variant of shape matching problems that deals with terrain data. Terrain is defined as a 2-dimensional surface in R^3 which is monotone to the z-axis, i.e., every line parallel to the z-axis does not intersect it or intersects it at a point. Terrain matching has been extensively used for various applications to locate the exact position of objects. Aircrafts usually use Inertial Navigation System (INS) to estimating the position. However, to avoid the accumulation of error, periodic fixed of exact position of the aircrafts is necessary so Global Positioning System (GPS) and terrain matching algorithm is used. A typical method applied to find the most similar sub-terrain is the shape matching between features extracted from the terrain data. Linear edges, curves, contour lines, and Gaussian curvatures are widely used as the features. Although using the features describes some local characteristics of a terrain, it has a limitation in fully reflecting the overall geometric properties of the terrain. In this thesis, we study how to solve terrain matching problems while considering the whole geometric properties of terrain data.