Istanbul 2004 
the tangential 
e elements a, 
nents of the 
e the singular 
solution, with 
> used to split 
and V, such 
atrices and D 
1e solution of 
wing steps: 
lue in the D 
e i.th column 
Xf the desired 
> normal and 
s “looking in 
t is facing the 
dden. 
ich the voxel 
UU» 
? and the 
rface normal 
5) according 
(4) 
  
ill angle) 
e normal and 
ormal vector 
gital image, 
vs the angle 
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part BS. Istanbul 2004 
according to the approximated volume intersection model 
where the lighter the pixel, the smaller the angle. 
43 Line Tracing 
When computing a voxel's visibility we perform line tracing. 
The voxel line is defined by the image projection center (X;, Y; 
Z;) and either a voxel (Vy, V7) or-a pixel (i, k, -c). In our 
case there is no information outside the defined voxel cube. 
Since line tracing a time consuming process, we should define a 
sensible geometric limitation with two preconditions: 
e Fach voxel must be covered by the line. 
e Not too much empty space should be swept by the line. 
With the help of the equation below several approaches can be 
derived. 
X X% 7 X% X 0 
Y] SK Au rh le A (5) 
Z voxel p pixel 9 
For a simple approach, we will choose two values for A, to 
define a start- and an end-point for the line. It is based on the 
assumption, that a A-factor according to the farthest and the 
nearest corner of the voxel cube will completely enclose the 
whole cube. For this definition, all we have to do is to calculate 
the distance to each of the eight corners, and determine the 
minimum and maximum of these values. Those two A-factors 
will be globally valid for all pixels of one image. 
  
f 
P 
  
Hm UT 
| P 
  
  
1 
1 
| 
i 
i 
  
j 
| i 
i | 
| i 
| 
| 
EEE fe cata 
" 
2 
= 
| 
| 
| 
i 
i 
i 
| 
| 
+ 
{ 
| 
| 
— 
i 
| 
  
Figure 7: 18-connected (dark pixels) and 6-connected line 
(light+dark pixels) in 2D 
Connectivity is an important issue in line tracing. By choosing 
the connectivity of the line, we traverse fewer or more voxels. 
There are different degrees of neighborhoods, which will affect 
the thickness of the line. In three dimensions we can define 6-, 
18-, or 24-connected lines. Figure 7 shows the difference 
between a 6-connected and an 18-connected line (for simplicity 
in 2D). An algorithm for a 6-connected line can be found in 
(Amanatides and Woo, 1987). 
5. IMAGE MATCHING 
We use color image matching to search for image 
correspondences since an RGB-triplet contains more 
information than a single gray value. When we perform image 
matching, the consideration of red, green and blue channels 
separately might reveal texture information more clearly. 
In general we might classify the possible color image matching 
approaches into two groups. First, we can throw all color 
channels into one equation and get one correlation factor as a 
result. Second, we calculate a correlation factor for each 
channel separately. Here we will only present the single vector 
correlation and the difference correlation as our color image 
matching algorithms. 
S.J Single Vector Correlation 
Several tests have shown us that the simplest and at the same 
time the most reliable solution is the correlation of all the input 
data in one vector. Assuming the normal case of having three 
channels of color (RGB, CMY, IHS), we will now have three 
times as many observations as in gray images: 
n — width . height .3 
The idea is to put all these observation in one vector, resulting 
in one single correlation coefficient: 
2.2. Lis mg s. r2. ) 
e ory x 
Ez 
XXe AR 
chix 
  
  
(6) 
where: g is the density (gray value) and g is the arithmetic 
mean of densities and ch denotes the color channels. 
5.2 Difference Correlation 
For this method, we can apply the same approaches, as for the 
normalized cross correlation. Hence, we can calculate one value 
by summing up all the differences over the three channels, or 
we can derive three separate values and calculate a weighted 
and a non-weighted mean value. We only consider the single 
vector variant for this approach: 
2.2.2 Abs(g, ~ 2.) 
ch xy 
]- ; 
3. width. height (2... — Zn ) 
  
(7) 
DE 
5.3 Introducing Knowledge about the Approximate Shape 
In area-based image matching, large base line would cause high 
patch deformations due to perspective distortions; as a result 
image matching would fail. However, in our proposed 
knowledge based patch distortion, this effect is reduced since 
these deformations are considered and accordingly transformed 
patches are grabbed for image matching. 
  
   
  
Figure 8: Creating a tangential surface patch