DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click

HERE to register or log in.

# Accession Number:

## ADA210106

# Title:

## On Planar Point Matching under Affine Transformation

# Descriptive Note:

## Technical rept.

# Corporate Author:

## CORNELL UNIV ITHACA NY DEPT OF COMPUTER SCIENCE

# Report Date:

## 1989-04-01

# Pagination or Media Count:

##
15.0

# Abstract:

## An important geometric matching problem in machine vision and robotics is to determine whether there exists an affine transformation a general linear transformation and a translation that maps each point of a set A onto a corresponding point of a set B. In the case of matched cardinality point sets, we have developed an optimal Theta n log n algorithm for determining the existence of such a transformation. The method makes use of the fact that an affine transformation preserves the center gravity of a point set, as well as the ratios of triangle areas. If abs. val. A abs. val. B then there can be n- cubed affine transformations from A to B. In general the number of transformations will be much smaller, so we have developed an output sensitive algorithm that runs in time On-sq log n tmlog n, where m abs. val. A, n abs. val. B, and t depends on the number of transformations. The method relies on the affine properties that intersection points and length ratios along a line are preserved.

# Distribution Statement:

## APPROVED FOR PUBLIC RELEASE

#