Geometric Matching of Terrains: Algorithmic Analysis and Implementation

Abstract

Matching is a general method to identify resemblance of given objects in computer science. Numerous applications inspired from the matching utilize the relations of similar objects to make decisions such as in object recognition. We focus on the geometry of terrains as the objects to be matched. The matching of terrains is useful to take the current position of aircraft or missiles in navigation systems for example.

In this thesis, we are given a small patch terrain f and a big database terrain g. Our goal is to find a part of g which is the most similar to f under translation. We consider a terrain as a piecewise linear bivariate function, and each terrain is triangulated such that the triangulation is realistic to represent a terrain. The similarity is measured by L_1 distance of two terrains restricted on the smaller domain. We propose efficient matching algorithms to find an exact solution, and present implementation issues of the matching. We also provide experiments to validate our approaches.

컴퓨터과학에서 매칭은 주어진 물체들의 유사성을 판별하는 일반적인 방법이다. 매칭에서 파생된 많은 응용들은 비슷한 물체들의 관계로부터 예를 들어 물체 인식과 같은 판단을 한다. 우리는 매칭할 물체들로써 지형의 기하학적 구조에 초점을 맞추고자 한다. 지형의 매칭은 예를 들어서 비행체나 미사일의 운항 시스템에서 현재 위치를 알아내는데 유용하다.

이 학위 논문에서는 작은 패치 지형 f와 큰 데이터베이스 지형 g가 주어졌을 때 f와 가장 유사한 부분을 g에서 찾는 것을 목표로 한다. 지형은 구분적 선형 이변수 함수로 표현되며, 각 지형은 지형을 표현하기에 실제적으로 삼각화되어있다. 두 지형의 유사성은 더 작은 정의역으로 제한된 L_inf 거리로 측정한다. 우리는 정확한 해를 찾는 효율적인 알고리즘들을 제안하고 매칭에 관련된 구현 문제들을 다룬다. 또한 우리의 접근 방식의 유효성을 입증하기 위해 실험 결과를 제공한다.