n- 
te 
lal 
er 
es 
ly, 
he 
e~ 
li- 
on 
or 
er 
ur 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
. Gray-scale Spatial 
Preprocessing Correction Filtering 
Feature Statistical Interest Edge Texture, 
Extraction Properties Points Extraction Segmentation 
(rsage Patch 
Analysis) 
Matching 
2 Method Cross LS Matching V — S (3D) Symbolic 
Correlation Feature Based Matching 
- Strategy Line Global Surface 
Constraint Approximation| 
Evaluation Results, Confidence 
a Ts Analysis 
  
  
  
| 
images are not resampled but converted on the fly during 
display operation or data processing. Usually, the operator 
moves the floating mark quite slowly. Therefore, the im- 
age patches of a current matching operation may have very 
similar image characteristics like neighboring patches. This 
means that certain parameters of the previous (neighbor- 
ing) matching operation can immediately be used for the 
processing strategy of the current patches. For example, 
surface direction can be approximated at one side of the 
patch, or texture based segment data and basic statistics 
can reveal occlusion situations. 
The patch size in our application is more an implementa- 
tional than algorithmic issue. However, it is still important 
since most matching methods are very timeconsuming and 
our application needs a quasi real-time response (the pro- 
cessing time should not take longer than what an operator 
would need). 
2.2 Structure of the Algorithm 
Based on conditions imposed by our application the default 
matching method is cross correlation (Ackermann, 1984). If 
the current patch has enough texture information, the fore- 
shortening is negligible and there is no occlusion or other 
artifact, then correlation performs well. Since these condi- 
tions are not always met, other methods must be used. A 
first key issue is to find and parametrize the image charac- 
teristics (called actual features in this paper) of the patches. 
Figure 1. 
Flowchart of the DOG system. 
401 
This problem itself is as complex as the matching, because 
ideally it would address many high-level paradigms of scene 
analysis and image interpretation. Because of the lack of a 
robust, scene independent matching scheme, an iterative hi- 
erarchical strategy is proposed. Figure 1 shows the flowchart 
of the proposed DOG method. The suggested system has 
five processing levels: 
e Patch preprocessing 
e Feature extraction - image patch analysis 
e Matching procedure 
e Matching strategy 
Evaluation - result analysis 
The patches may be subject to some image enhancement. 
Scaling the pixel intensities or histogram equalization can 
compensate for bad contrast. Spatial filtering, like median 
or Gauss operators can remove noise or unneccessary details 
which may be important for scale-space algorithms. 
Feature extraction provides clues about the patch and may 
guide the selection of the most appropriate matching method. 
The basic statistical properties, like mean, median, mini- 
mum and maximum intensities, standard deviation, auto- 
correlation, etc. provide additional patch information.