ISPRS Commission III, Vol.34, Part 3A ,,Photogrammetric Computer Vision", Graz, 2002 
  
or local gravity center of image gray level. The original Forstner 
operator is computational expansive and requires an empirical 
threshold upon image conditions. We determined that Forstner 
operator should only be applied locally for detecting features that 
are distinct to local environment. Such detections are likely to be 
invariant relative to local image context even with large geometric 
and radiometric distortions. Selection of a 64 x 64 pixels square 
provides an adequate local region for interest point detection, 
which sets the dimension of the multiple local image patches for 
the generic TP detector. In addition to local application, a basic 
interest points are first selected at pixels with Robert gradients 
Vg(i, j) » w, egn» Where w is the mean magnitude of the 
Robert gradient over the local image patch. Forstner interest oper- 
ator is then applied to basic interest points. This hierarchical 
approach not only reduces the computation significantly, but also 
improves the quality of detection with a simple weight threshold 
of one. Last, the window size for the suppression of local non- 
maximum interest values is set dynamically according to the num- 
ber of the basic interest points as well as the diverse range of Forst- 
ner interest values within the local image patch. This dynamically 
controls the invariance of interest point detection, with respect to 
various global surface types that MISR covers, and various image 
qualities across MISR cameras. 
32. Feature Match 
A relational-based matching algorithm was designed that trans- 
lates the problem of mapping of one set of features with another 
into a consistent labeling process. 
3.2.1. Consistent Labeling Problem 
According to [Haralick and Shapiro, 1993], an N-ary consistent- 
labeling problem (CPL) is a 4 tuple CPL - (U, L, T, R). Compo- 
nent U is a set of M units U = (1,..., M), which are the objects to be 
labeled. Component Z is the set of possible labels. Component 7 is 
the unit-constraint relations over the unit set U. R is the unit-label 
constraints over the set U x L of unit-label pairs. A labeling of a 
subset U = {uy uy, ..., up} of Uis a mapping f: Ü —L from Ü 
to L. A labeling f of a subset U of units is consistent if whenever 
,uy are in Ü and the N-tuple (uy, uy, UN) is in 7, 
soe (Upp, I] in R. 
Ups Uns oon 
then [Gus f) (t^, f (5), ... 
Now let A and B be two sets. Let 7 c a be an N-ary relation 
over set À. Let f: A — B bea function that maps elements of set A 
into set B. The composition of T with fis defined by: 
To f~ tb; n Dy) € B| there exists 
1 
(ay, aap) € A with f(a;) = bi = 1, Me ) 
Let Sc BY be a second N-ary relation. A relational homomor- 
phism from T' to S is a mapping f: 4 — B thatsatisfies T^» fc S. 
A relational homomorphism maps the elements of 4 to a subset of 
the elements of B having all the same interrelationships that the 
original elements of 4 had. The relational homomorphism prob- 
lem fits the consistent-labeling model well. If we regard one data 
set A, such as a list of image features, as a unit set and another data 
set B, such as another list of features from a conjugate image 
patch, as the label set, the unit-constraint relation is simply the 
relation T of the relational homomorphism problem with unit-label 
relation" given "by R= LG. 1), (us, I»), e np Il 
(up, ty, os up) e 7 and (4, I», i In) eS. 
3.2.2. Tree Search 
To solve for a consistent labeling problem, we look for the set of 
all consistent labeling f: U — L that satisfy the constraints speci- 
fied by T and R. In the context of feature matching, there are M 
features from one image patch, N features from a conjugate patch, 
and M € N . Choosing M set of features as the unit set, and N set 
of features as the label set, the labeling of the unit set to the label 
set constructs a problem space which can be represented by a tree 
with a depth of M. Each node in the tree represents one labeling or 
pairing of a unit to a label. Each branch from the root to the leaf 
M M-1 
represents one of total Y. II (N- j) possible branches, only 
i=0j=0 
one of them is a consistent labeling representing the correct match. 
The key of feature matching is to search for the consistent label- 
ling and reject the inconsistent labelling efficiently. Due to image 
distortations, it is unlikely for features extracted from different 
images to have the same attributes and relations. Therefore feature 
matching may contain ambiguous solutions. For example, a unit 
set of 10 features is matching with a label set of 12 features. Tree 
search finds no branch with consistent labelling but two branches 
are partial consistent, one with three consistent labeled nodes and 
the other with eight. Obviously the branch that contains the maxi- 
mum number of potential matches leads to the correct match. 
In the discipline of artificial intelligence, one of the basic heuristic 
methods for pruning trees is to expand on a node according to its 
benefit function, defined as: 
f(n) = g(n) + h(n) (2) 
where g(n) is the benefit from the root of the tree to the current 
node and h(n) is the estimated benefit from the current node to 
the final leaf. For image matching, g(n) is defined to be the num- 
ber of consistent labelling from the root to the current node, and 
h(n) is the number of potential consistent labelling from the cur- 
rent node to the leaf if the current node is expanded. In this pro- 
cess, the future benefit is estimated according to a future-error- 
table (FTAB). Each element in the FTAB represents the error a 
pairing that deviates from the labeling constraints specified by 7 
and R. When this error is large enough, a labeling is considered to 
be impossible. When the total number of consistent labelling from 
both past and future is too small, we stop expand along the current 
branch and backtrack for another node to expand. 
3.2.3. Consistent Labeling Algorithm 
The algorithm for solving the consistent labeling problem is based 
on the forward checking tree search by Haralick and Shapiro 
[1993], modified for expanding along a potential branch according 
to its total benefit. 
Consistent labeling(U list, U patch, L list, L patch, T, FTAB, R) 
A - 426