# Automatic Registration in Isis 3.0

**Draft Version 0.2**

**Tuesday, May 03, 2006**

## 

## Table of Contents

[Automatic Registration in Isis 3.0
1](#automatic-registration-in-isis-3.0)

[Table of Contents 2](#table-of-contents)

[Introduction 3](#introduction)

[Plugins and PVL 3](#plugins-and-pvl)

[Chips 3](#chips)

[Pattern Chip 3](#pattern-chip)

[Search Chip 4](#search-chip)

[Restrictions 4](#restrictions)

[Match Algorithms 4](#match-algorithms)

[Minimum Difference 5](#minimum-difference)

[Maximum Correlation 5](#maximum-correlation)

[Tolerance 6](#tolerance)

[Creating a Fit Chip 7](#creating-a-fit-chip)

[Dense Walk 7](#dense-walk)

[Sparse Walk 8](#sparse-walk-future-option)

[Sub-Pixel Accuracy 8](#sub-pixel-accuracy)

[Surface Modeling 8](#surface-modeling)

[Finding a Local Minimum/Maximum 8](#finding-a-local-minimummaximum)

[Advanced Features 9](#advanced-features)

[Restricting Pixel Ranges 9](#restricting-pixel-ranges)

[Valid Pixel Count 10](#valid-pixel-count)

[Reduction of Pattern Cubes 10](#reduction-of-pattern-cubes)

[Geometric Warping of Pattern Cubes
11](#geometric-warping-of-pattern-cubes)

[Sampling in the Match Algorithm 11](#sampling-in-the-match-algorithm)

[Z-Score Test 12](#z-score-test)

## 

##  

## Introduction

This document attempts to describe how automatic registration is
accomplished in Isis 3. In simple terms, automatic registration is the
attempt to match a pattern in a cube. For example, given a reseau
template pattern, we would like to find positions in a cube which match
the reseau. Similarly, if we extract from a cube a ground feature (e.g.
crater, fault line, etc) as a pattern, we would like to find the same
feature in another overlapping cube to define match points.

### Plugins and PVL

Automatic registration is a tricky subject. Algorithms and parameters
that successfully work for one pattern are likely not to work for other
conditions. In Isis 3, we do not want to restrict our registration
programs (e.g., coreg, coregpr, qmatch, etc) to a single algorithm. We
would view this similar to map projections or camera models. That is, if
a particular registration algorithm meets our needs we can choose to use
it, however, if none meet our needs a new algorithm can be developed. A
key element is we want the new algorithm immediately available in all
applications without the need to modify them. We will facilitate this
requirement through plugins and the use of Parameter Value Language
(PVL) definition files. The PVL syntax will be introduced gradually as
the overall discussion of automatic registration progresses.

## Chips

There are two chips used in automatic registration, the pattern chip and
the search chip. We will discuss each in the following sections. For now
we describe the basic elements of a chip, which is nothing more than a
sub-area of cube, generally small in size. That is, an NxM chip is
defined to be an N sample by M line region of a cube. Some key elements
about a chip are:

1.  N and M are natural numbers (1, 2, 3, ...)

2.  Like cubes, chip coordinates are sample/line and 1-based

3.  The center of the chip is (N-1)/2+1 and (M-1)/2+1.

Because a chip is a region of a cube, there must a technique to "load"
the chip. The primary method is to specify a cube coordinate
(sample/line) to be loaded at the center of the chip.

### Pattern Chip

A pattern chip will contain the data you would like to match. In the
past we have called this the truth chip or hold chip. Both of these
terms can be confusing. The term truth has different meanings in regards
to match points and term hold is misleading as a pattern chip actually
floats through the search chip. So we refrain from their use and stick
with the term pattern chip. The PVL for a pattern chip is

Object = AutoRegistration

Group = PatternChip

Samples = 5

Lines = 5

End_Group

End_Object

### Search Chip

The search chip is the area of the cube we believe the pattern will fall
in. That is, we will walk the pattern chip through the search chip
looking for the best match. Hopefully it is obvious the search chip must
be larger than the pattern chip. However, note that by restricting the
search chip size, we effectively define how far the pattern chip is
allowed deviate from a desired center search spot.

Object = AutoRegistration

Group = PatternChip

Samples = 5

Lines = 5

End_Group

Group = SearchChip

Samples = 21

Lines = 21

End_Group

End_Object

### Restrictions

Because the pattern chip and search chip are tightly coupled there are
some restrictions that must be put in place. There are:

1.  N+M\>=3 must be satisfied for the pattern chip. This ensures the
    pattern is not a single pixel. However, in practice, small pattern
    chips often match too many areas in a search chip.

2.  We must satisfy N~search~ \>= N~pattern~+2 and similarly for M. This
    ensures that the pattern chip spans at least a 3x3 window in the
    search chip. This is subtle but important requirement for surface
    fitting in order to compute sub-pixel accuracy (which will be
    discussed later in this document).

## Match Algorithms

An objective of the Isis 3 automatic registration design is to allow for
a variety of match algorithms. For example, an algorithm could be
developed that works best for matching MGS/MOC wide angle and Odyssey
Themis IR cameras. For this objective to be met we will utilize
applications which allow automatic registration plugins. This is
identical to applications which utilize camera and/or map projection
plugins such as cam2map, map2map, etc.

The plugin algorithm will receive the pattern chip and a sub-region of
the search chip. This sub-region will have the same dimensions as the
pattern chip to allow for a pixel-by-pixel comparison of the chips. The
algorithm is expected to return single value that represents the
goodness of fit (GOF) between the two chips. The definition of the GOF
is algorithm dependent. For clarity, we present two types of match
algorithms in this document with the understanding that more algorithms
may be developed in the future.

### Minimum Difference

This match algorithm would perform a subtraction of the pattern chip and
the sub-region of the search chip over the valid pixel count. It
measures the average absolute difference per pixel. The actual equation
would be:

GOF = pattern(i,j) -- subregion(i,j) / count

In this case, a GOF value of zero indicates a perfect match, while
larger values indicate a less likely match. Obviously, negative values
could never occur. This would be represented in PVL as:

Object = AutoRegistration

Group = PatternChip

Samples = 5

Lines = 5

End_Group

Group = SearchChip

Samples = 21

Lines = 21

End_Group

Group = Algorithm

Name = MinimumDifference

End_Group

End_Object

### Maximum Correlation

This match algorithm would compute the correlation coefficient, R,
between the pattern chip and the sub-region of the search chip as
follows:

Covariance (pattern,subregion)

R =

> Variance(pattern) \* Variance(subregion))

where -1.0 \<= R \<= 1.0

GOF = R

In this case, the goodness of fit will range from no correlation (zero)
to perfect correlation (one). The PVL for this example would be:

Object = AutoRegistration

Group = PatternChip

Samples = 5

Lines = 5

End_Group

Group = SearchChip

Samples = 21

Lines = 21

End_Group

Group = Algorithm

Name = MaximumCorrelation

End_Group

End_Object

### Tolerance

In both algorithms we will want to define a tolerance for goodness of
fit. The tolerance test must be made by the plugin as the direction of
the test is dependent on the algorithm. In our two examples
MinimumDifference would use a test for "less than" Tolerance while the
MaximumCorrelation would use "greater than" Tolerance. This is
represented in PVL in the following fashion:

Object = AutoRegistration

Group = PatternChip

Samples = 5

Lines = 5

End_Group

Group = SearchChip

Samples = 21

Lines = 21

End_Group

Group = Algorithm

Name = MaximumCorrelation

Tolerance = 0.7

End_Group

End_Object

In fact, the plugin will have significant control such that one, two, or
more tolerances or test conditions must be satisfied to accept the
match. For example,

Group = Algorithm

Name = SuperSpecialRegistration

Tolerance = 0.7

ChiSquare = 2.5

R = 0.6

T = 95.0

End_Group

## Creating a Fit Chip

We define a third chip, the fit chip, which represents the goodness of
fit at each equivalent position in the search chip. That is, we can
think of the pattern chip walking through the search chip and at each
position extract a sub-region to be used for computing a fit value.
After walking and computing at each position we have a chip filled with
goodness of fit values that are in 1-1 correspondence with pixels in the
search chip. An example of the pattern chip weaving its way through the
search chip is given:

![](media/image1.png){width="2.0625in" height="1.9375in"}

How the pattern chip walks the search chip can vary; currently we define
two methods, a dense and sparse walk.

### Dense Walk

In the obvious case, we walk every possible position in the search chip
by starting in the upper-left corner and moving over by one sample. When
we come to the right edge we will move down one line and reset to the
left edge. However, we do not test where the pattern would lie outside
the search chip. For example,

![](media/image2.png){width="2.2604166666666665in"
height="2.0729166666666665in"}

In other words, we only test the pattern if it is fully inside of the
search chip. This will be true for all walking scenarios. Therefore, if
we have 3x3 pattern chip and a 7x7 search chip, we compute fits for 25
of the 49 pixels in the search chip.

### Sparse Walk (Future Option)

A sparse walk uses a sample and line increment to move the pattern chip.
The resultant fit chip will have a sparse sampling of data. The walking
algorithm will search for the best goodness of fit value in the sparse
fit chip and then compute densely around that point. The advantage is
that sparse walking will reduce the number of computations, especially
for large chips. This is facilitated through PVL as:

Group = SearchChip

Samples = 21

Lines = 21

Density = (2,3)

End_Group

In this case, every other sample and every third line will be tested in
the search chip. If density is not specified it defaults to (1,1) which
is a dense walk. It is important to recognize there is a risk using the
sparse walk. The algorithm can miss the best fit and compute an
incorrect pixel match. So there is a speed versus accuracy tradeoff.

## Sub-Pixel Accuracy

Upon walking the pattern chip through the search chip we will have
created the fit chip. The highest (or lowest) goodness of fit value
generally represents the position that best matched between the pattern
and search area. It is however only good to one pixel accuracy.

In many cases, the actual registration may lie somewhere between two
pixels. This is due to the fact that we are using a set of finite data
to estimate something that is in fact continuous.

### Surface Modeling

To get around this problem, we can model a continuous mathematical
surface based on the data in the fit chip. By calculating a 2^nd^ degree
2-dimentional polynomial given an NxN window of points, we have a
reasonable approximation under a given tolerance of the underlying
structure. We can then estimate the true registration position of the
chip on that surface.

Optionally, the window size and tolerance may be supplied through PVL:

Group = SurfaceModel

DistanceTolerance = 2.5

WindowSize = 7

End_Group

The distance tolerance in pixels must be greater than 0 and is defaulted
to 1.0. The window size must be an odd number greater than 2 and is
defaulted to 3.

### Finding a Local Minimum/Maximum

After a surface is modeled over the data, we can use a number of
techniques to calculate the local extreme. For example, when using the
MinimumDifference algorithm the registration occurs at the minimal value
on the surface. The result should fall within one pixel of the best
calculated fit.

It is important to note that while the surface modeling option is on by
default it is possible to turn it off by using the SubpixelAccuracy
keyword. Example:

Group = Algorithm

Name = MaximumCorrelation

Tolerance = 0.7

SubpixelAccuracy = False

End_Group

In this case, the whole pixel with the best fit is returned.

Also, if an ideal goodness of fit is found (e.g. 0.0 for
MinimumDifference or 1.0 for MaximumCorrelation), we have a perfect fit
and, thus, know it is in the best position. In this case, the sub-pixel
accuracy phase is omitted.

## Advanced Features

This section covers advanced features of automatic registration. While
these features are not necessary in order to accomplish the
registration, they can be used to significantly improve the chance of
success and/or the accuracy of the match.

### Restricting Pixel Ranges

Pixels may be excluded from the match algorithm if they fall outside of
a specified range. This range is independent for both the pattern and
search chip. It is handled via the PVL as follows:

Object = AutoRegistration

Group = PatternChip

Samples = 5

Lines = 5

ValidMinimum = 0.1

ValidMaximum = 0.4

End_Group

Group = SearchChip

Samples = 21

Lines = 21

ValidMinimum = 2.5

ValidMaximum = 10.5

End_Group

...

End_Object

If values are not given in the PVL then all pixels are considered valid
(with the exception of special pixels).

### Valid Pixel Count

Prior to the match algorithm being invoked during the walk process, a
simple test is performed to ensure there are enough pixels to work with.
Pixels are deemed valid if they are in the minimum/maximum range and/or
they are not special pixels. The pattern chip is only checked once. If
it does not contain enough valid pixels the match is deemed to fail. As
the walk through occurs, the sub-region is extracted from the search
chip. If this sub-region does not have enough valid pixels a match will
be deemed to fail at that search location. In the following PVL example
we have a 5x5 chip with 25 pixels of which 80% or more must be valid,

Group = PatternChip

Samples = 5

Lines = 5

ValidMinimum = 0.1

ValidMaximum = 0.4

ValidPercent = 80

End_Group

We only need to specify the percent for the pattern chip as the
sub-region chip of the search area will use the same value.

### Reduction of Pattern Cubes

A technique for improving the accuracy of the automatic registration is
the repeated reduction of the pattern chip. The strategy is to use the
initial size of the pattern chip to estimate the sub-pixel sample/line
in the search cube. Then reduce the size of the pattern chip and
re-match about the estimated point within a limited area. The technique
can be done iteratively all the while searching for the "best" goodness
of fit value among the shrinking pattern chips. This can be accomplished
in PVL as follows:

Group = PatternChip

Samples = (21,17,11)

Lines = (21,17,11)

End_Group

The above example finds an initial estimate using a 21x21 chip and then
refines using a 17x17 and 11x11 around the estimate.

The amount the reduced chip can move is specified as a percentage of the
previous chips area. This is done by using the FloatPercent keyword. If
a single value is entered for the FloatPercent keyword, it is used for
all reduced pattern chips. For example,

Group = PatternChip

Samples = (21,17,11)

Lines = (21,17,11)

FloatPercent = 50

End_Group

In this example, each reduced chip is allowed to move with an area that
is 50% the size of the previous chip. So the 17x17 chip is allowed to
move within a 10x10 area and the 11x11 chip an 8x8 area.

It is also possible to specify a unique value for each reduced pattern
chip. This allows the user greater control over the final results. An
example is:

Group = PatternChip

Samples = (21,17,11)

Lines = (21,17,11)

FloatPercent = (100,25)

End_Group

Here, the 17x17 chip is limited to a 21x21 area (100% of the 21x21 chip)
and the 11x11 chip a 4x4 area (25% of the 17x17 chip).

The ability to reduce the pattern chip has direct implications to the
valid pixel count. That is, the specified percentage will be used for
each chip. For example,

Group = PatternChip

Samples = (10,9)

Lines = (10,9)

FloatPercent = 50

ValidPercent = 60

End_Group

In this case a 10x10 chip has 100 pixels of which 60% must be valid.
This will apply to all pattern chips and therefore the 9x9 chips must
have at least 49 valid pixels (60% of 81).

### Geometric Warping of Pattern Cubes

The pattern cube can be forced to match the geometry of the search cube
by using map projections and/or camera models. Additionally, rotations
can be applied to the pattern cube. The warping is application dependent
and therefore is under the control of the programmer. That is, there is
no PVL mechanism for warp selection/de-selection.

### Sampling in the Match Algorithm

To increase the speed of the match algorithm data in the pattern chip
and the sub-region of the search chip can be sampled. While the sampling
may cause the algorithm to run faster it may be at the expense of
finding the best registration. In Pvl,

Group = PatternChip

Samples = 10

Lines = 10

Sampling = 50

End_Group

In the above example, half of the data would be compared in the matching
algorithm. So, instead of looking at all 100 pixels, the algorithm will
compare 50 evenly spaced values. If the sampling keyword is not present
then 100 is assumed and all data will be used.

### Z-Score Test

To guarantee an accurate match, we first need to check if the pattern
chip has enough variation to perform the algorithm on. This is done by
calculating the z-score of both the minimum and maximum values of the
chip. The z-score measures the number of standard deviations the value
is away from the mean. If the z-score for either value is greater than
the specified minimum value, then it is an acceptable pattern chip. For
example,

Group = PatternChip

MinimumZScore = 1.5

End_Group

In this case, the chip's extreme values must be more than 1.5 standard
deviations away from the mean. If the MinimumZScore keyword is not
included, the default value of 1 standard deviation is used.