ISPRS Commission III, Vol.34, Part 3A ,,Photogrammetric Computer Vision“, Graz, 2002
Select the first unit in the U list
Return success if no more unit is left in the U list
For each potential label according to FTAB
Add current (u, l) to R and return success if this is the last
unit in the U list
Call forward check to update FTAB w.r.t. current labeling
If total match from current to future larger than a threshold
Call Consistent. label to search along the branch
Add current (u, 1) to R if search along branch is success
End If
End For
If total match from current to future larger than a threshold
Call Consistent. label to search along branch
Add (u, no. label) to R if search along the branch is success
End If
Return fail (no more expansion for this unit and down, backtrack)
3.2.4. FTAB for Feature Matching
For consistent labeling of M units matching with N labels, FTAB is
a M x N array with each element represents the error of labeling
unit 4 with label /. For interest point matching, the size of image
search window is used to initialize FTAB as a binary map to prune
non-potential labels for all units. In the case of MISR, local image
patches are defined according to image navigation and the average
elevation of the local surface. The static and dynamic errors in the
navigation data propagate to an uncertainty of [/ 0 TAL sg£As] in
the local image extraction. MISR cameras also contain a diverse
range of pointing in the along-track direction
(0.0°, +26.1°, £45.6, 60.0, 170.5? ), which creates image dis-
parities for surface features that are off the local average elevation.
Combining both factors, a search window is determined for each
pair of local image patches and used to define candidate labels of
all unit features.
Next, the error value of each candidate pair in the initial FTAB is
replaced with the unary constraints. First, the local distinctness of
an interest point is represented by its interest value w. Conjugate
interest points surrounded by similar image patterns tend to have
similar interest values for locally detected interest points. The first
unary constraint for matching is defined as the relative difference
of the interest values:
W,—W
E l u Q)
sim j
min(wy, wi
The next unary constraint is the radiometric similarity of local
images, defined by a cheap area-based similarity measurement:
fabs tm c)- img] = [img, (r, c)— img |
{A
A
Reim = 5, 4)
where w defines a 5 x 5 similarity window centered at the interest
point, img(r, c) is the image value at pixel (7, c), img is the mean
image value within the similarity window, and 0 I is the sigma of
image values within the label similarity window. The total unary
constraint is the summary of the distinctness similarity and radio-
metric similarity, normalized by a factor of two.
Before a tree search starts, the unit list is ordered such that units
with less labeling candidates are listed first to prune out a portion
of unnecessary search tree. During a tree search, FTAB is updated
according to a topological binary relationship between interest
points. Topological relationship is used because local rotational
distortion is relatively small for small scale imagery. For each pair
of interest points, the topological binary distances are
D, = | and D, sv where i and j are
intéfest point indices, x and )'àre interest point coordinates, s. and
s. are pixel resolution of the image. The topological binary con-
straints are:
Zo (2), . (2x), 2s (o, T (2) (5)
i (Dax), Vij ( max),
where Dax) and (D nx, "€ relaxed pixels for this con-
straint. For smáll scale imagery, they are about two to three pixels.
3.2.5. Tie Point Merge:
The relational-based feature matching results in a list of matched
interest points for each image pair. Combining all match lists
together is simply a sorting process. For example, in the case of
MISR, local image patches from nine cameras are paired by either
adjacent or every other adjacent cameras to provide closer geomet-
ric and radiometric similarity. This results in total 15 image pairs:
DfCf, CfBf, BfAf, AfAn, AnAa, AaBa, BaCa, CaDa, DfBf, CfAf,
BfAn, AfAa, AnBa, AaCa, BaDa. Assume interest point pair (0, 4)
is on the match list of image pair DfCf, (0, 2) is a point pair on the
list of image pair DfBf, a new TP with (tp. id — 0, Df — 0, Cf — 4,
Bf — 2) is created. TP merge also provides a reliability assurance.
If (4, 1) is also a point pair on the match list of camera pair CfBf.
The insertion of this pair would result in an inconsistency in the
TP table, therefore any match related to TP tp. id = 0 is discharged
as a blunder. The algorithm used to sort the pair-wise matched
interest points and create TPs across multiple image patches is the
determination of equivalent class from Numerical Recipes in C by
Press. et. al [1992].
3.3. Precise Match
The accuracy of relational-based feature matching is about two
pixels due to both image distortions and the relaxed geometric
constraints. Area-based matchers then refine the accuracy to sub-
pixels. A refined TP must be precisely matched on a minimum
number of local image patches. MISR triangulation requires a TP
be precisely matched on a minimum of five cameras with 0.2 pix-
els accuracy, while the rest of cameras could be relaxed. If a mini-
mum number of TPs are precisely matched according to the
cluster requirement from triangulation, precise match will stop to
refine the rest of feature-matched TPs.
The main criteria for precise matching is high precision and reli-
ability. First, cross-correlations are computed for each TP. The
template window for a TP is centered at the interest point with the
A - 427
