be well suited for picking CCPs in satellite or aerial imagery
in terms of speed and required accuracy [Luhmann and
Altrogge 1986].
The Moravec operator locates points with high variances in
all directions by calculating the square of grey value
differences in the four principal directions. If the minimum
of the four squared differences, called the interest value
(IV), exceeds a given threshold, a CCP is detected at the
center of the operator's window:
IV = min
S( G i.j-°i.i + i) 2
IXj-Gi*,/
X(Gi.j- G i+ , j +1 ) 2
S(G, j -G i „. j . 1 ) 2 .
CCP matching
The next step in the registration process is the matching of
CCPs between the reference and subject images. For each
point in the reference image, there should be a corresponding
one in the subject image. We currently use a "quick and
dirty” algorithm to accomplish this via nearest neighbor and
interest value comparison.
The process is as follows: For each point in the reference
CCP list, the CCP list from the subject image is scanned to
find those points whose image coordinates are close to its
coordinates ("closeness" is defined by a distance threshold
input by the user) and also have a similar IV (again user
defined by a threshold). If more than one point in the subject
list is found, the one with the greatest IV is considered to be
the corresponding point. Those points, in either list, which
have not found matches are removed from further
consideration.
Where i = n-k...n+k, j = m-k...m+k, k = size of operator
window, G n m is the pixel grey value at image coordinates
n,m.
It is desired that the interest operator should extract CCPs
with a relatively even dispersal throughout the image in order
to get the optimum rectification results. Unfortunately, the
Moravec operator extracts points only in regions of highest
image contrast. As a result, extracted points tend to lie in
compact clusters in certain areas of the image - leaving other
areas nearly void of CCPs (figure la).
To solve this problem, the Moravec operator is forced to
extract points from low contrast areas. This is accomplished
by partitioning the image into small subsets, then requiring
the Moravec operator to extract a certain number of points
from each. Only the points with the highest interest values
are chosen. By partitioning, CCPs are selected relatively
evenly throughout the image so that no part of the image is
neglected (figure lb).
+ +
+
+
+
4
+ +
+
+
+ +
+
+
+
+
+
+
: +
?
+
+ +
+
4
(b) Partitioned
Figure 1. Image partitioning for CCP distribution
As another refinement to the Moravec operator, those CCPs
which are connected (i.e. adjacent) to a CCP with a greater
interest value are also deleted from the list. Since the
Moravec operator tends to select CCPs in connected groups
of two or more, this helps avoid confusion and mismatches
in the following correspondence operation.
This approach to finding corresponding points has two
inherent drawbacks: First, using nearest neighborhood will
not work if there is too much rotational and/or translational
difference between the two images from which the candidate
point lists are drawn (more about this will be discussed
later). Second, it is a one-way correspondence algorithm.
Although each point in the reference list will only find one
corresponding point in the subject list, the opposite is not
necessarily true. There will most likely be several points in
the subject list which have more than one corresponding
point in the reference list. Note that this problem would be
compounded if we did not eliminate CCPs extracted adjacent
to each other in the previous step.
Fine tuning the matched CCPs
Once the CCP lists have been matched, it is then necessary
to eliminate mismatches and determine more accurately the
location of the corresponding CCPs in the subject image. A
cross product moment correlation coefficient algorithm is
employed for this task [Ehlers 1985]. If there is a high
correlation of a reference window (placed about the CCP in
the reference image) within a search window (placed about
the corresponding CCP in the subject image), the CCP in the
subject image is moved to the location within the search
window with the highest coefficient. This location is
calculated to subpixel accuracy, which may be necessary in
order to create a sufficiently accurate registration.
If the coefficient is less than a user-defined threshold, the
corresponding points are considered to be a false match and
are deleted. In addition, the fine tuning process also
eliminates many cases where a single subject image CCP is
matched to more than one reference image CCP. Each
reference point, when correlated, would most likely move
the same corresponding point to different locations, creating
two separate subject image CCPs from one and removing the
original ambiguity.
THE "LA GRANGE" SOFTWARE PACKAGE
A prototype image matching software package, called "La
Grange," has been written in FORTRAN 77 and
implemented on a Dell 386 microcomputer in the ERDAS
v7.3 environment. It incorporates steps 2 through 4 in the
matching process. The remaining steps are performed using
existing ERDAS image processing software (figure 2).
446