International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B5. Istanbul 2004 
  
4.1 Creating the Surface Voxel List 
The surface voxel list (SVL) is designed to contain all voxels, 
which lie on the object's surface. Compared to the total amount 
of object voxels, the SVL contains only a small percentage, 
therefore creating the SVL might speed up some operations 
tremendously. Depending on the neighborhood order fewer or 
more voxels are considered to be surface voxels and the whole 
set becomes more or less dense. If noise is likely to be the case 
but not desired a surface voxel can be defined as follows: 
1. The voxel itself is and object voxel 
2. Atleast one neighbor is not an object voxel 
3. Atleast one other neighbor is again an object voxel 
Nevertheless, the set of all surface voxels forms the surface 
voxel list (SVL). The simplest solution constructs a dynamic 
double-linked list where each item contains the voxels 
coordinates and each item has a reference to its predecessor and 
its successor. 
4.2 Surface Normal Vector 
The surface normal vector gives information of the direction 
where a voxel is facing (Figure 4). So it can serve as a quality 
measure for visibility related to a certain viewpoint. When we 
perform image matching, we would like to decide, whether a 
certain voxel is a sensible candidate. If it looks away from the 
camera, we can expect a highly distorted pattern, but when it 
looks in the direction of the camera it might give a good result. 
  
Figure 4: Surface normal vectors on a large voxel surface 
Our approach for derivation of surface normal vector calculates 
a least-squares adjustment on a specific subset of surface voxels 
for the plane equation (x - p) = 0 or: 
a-x+b-y+c-z+d=90 (1) 
We define a certain radius and we take all the surface voxels in 
this radius and write them into the matrix A, with: 
A= X) Va 7 (2) 
a n, 
X =|hb|=|n, {3) 
c n, 
Since we are only interested in the direction of the tangential 
surface, the unknown vector contains only the three elements a, 
b and c, which directly correspond to the elements of the 
surface normal vector. 
We have to solve the equation 4-X=0. We will use the singular 
value decomposition (SVD) to compute the best solution, with 
X=0 (Hartley, Zisserman, 2000). The SVD will be used to split 
the design matrix A into three new matrices U, D and W”, such 
that A=U-D-V", where U and V are orthogonal matrices and D 
is a diagonal matrix with non-negative entries. The solution of 
the above equation can be written down as the following steps: 
e Perform the SVD for the A matrix. 
e Let i be the index of the smallest value in the D 
matrix. 
e The solution vector X corresponds to the i.th column 
in the V matrix which are the elements of the desired 
normal vector. 
When we calculate the angle between the surface normal and 
the ray of sight, it can tell us whether the voxel is ‘looking in 
our direction’ or not. Hence, if the angle is small, it is facing the 
image, and if it exceeds 90° it can be considered hidden. 
Now, let P be the vector of projection, along which the voxel 
of interest is projected onto the image plane. 
n 
lt x 
i Ps 4 
i s N 
e 3 E 
Figure 5: Angle a between the surface normal n and the 
projection vector P 
We can now compute the angle between the surface normal 
vector 7 and the projection vector P (see Figure 5) according 
to the scalar product (or dot product): 
ap 
Fil 
  
COS = 
(4) 
    
HOFRETETE 
  
a) original b) gray 
(light pixels = small angle) 
Figure 6: Visualization of the angle between surface normal and 
projection vector 
Figure 6 is a visual validation of the surface normal vector 
computation. The left picture is an original digital image, 
captured by the camera. The right picture shows the angle 
    
International 
dled rtd ai! 
according tc 
where the lig 
4.3 Line Tr 
When compt 
The voxel lin 
Z,) and eithe 
case there is 
Since line tra 
sensible geon 
e Each wv 
e Not loo 
With the hel 
derived. 
/ voxel 
For a simple 
define a start 
assumption, 
earest cornc 
whole cube. I 
the distance 
minimum an 
will be global 
  
i 
i 
= 
———— - 
| 
| 
b 
| i 
| | 
| | 
Figure 7:1 
Connectivity 
the connectiv 
There are diff 
the thickness 
18-, or 24-c 
between a 6-c 
in 2D) An a 
(Amanatides : 
We use co 
corresponden: 
information tl 
matching, the 
separately mi; 
In general we 
approaches ir 
channels into 
result. Secon 
channel separ 
correlation an 
matching algo