- 78 - 
• gray, if the corresponding cube is a boundary cube, i.e., 
belongs partly to the object and partly to the background. 
In this case the node is divided into 8 child nodes (octants) 
representing 8 equally sized sub-cubes of the original cube 
All leaf nodes are either black or white and all intermediate 
nodes are gray. An example of a simple 3D object and the 
corresponding octree is shown in Figure 3. 
This octree contains binary information in the leaf nodes and 
therefore it is called a binary octree and it is suitable for 
representation of 3D objects where the shape of the object is the 
only object property that needs to be modeled by the octree. 
Non-binary octrees can contain other information in the leaf 
nodes, e.g., the cube color in RGB-space. For the Shape from 
Silhouette algorithm presented, a binary octree model is 
sufficient to represent 3D objects, and in the remainder of this 
paper the term octree will always refer to a binary octree. 
Figure 3. A simple object (a) and the corresponding octree (b) 
3.1 Construction of an octree 
The algorithm builds up a 3D model of an object in the follow 
ing way: first, all input images are transformed into binary 
images where a "black" pixel belongs to the object observed 
and a "white" one to the background (Figure 4a). In the 
implementation, black means background and white means 
object, but it is more intuitive to describe an object pixel as 
"black" and a background pixel as "white". Then, the initial 
octree is created with a single root node (Figure 4b) repre 
senting the whole object space, which will be "carved out" 
corresponding to the shape of the object observed. 
(c) Octree node projection (d) Intersection test result (e) Final octree 
Figure 4. Algorithm overview 
Then, the octree is processed in a level-by-level manner: 
starting from level 0 (with root node as the only node), all 
octree nodes of the current level marked as "black", i.e., 
belonging to the object, are projected into the first input image 
(Figure 4c) and tested for intersection with the object's image 
silhouette. Depending on the result of the intersection test, a 
node can remain to be "black", it can be marked as "white" 
(belonging to the background) or in case it belongs partly to the 
object and partly to the background, it is marked as "grey" and 
divided into 8 black child nodes of the next higher level (Figure 
4d). The remainder of the black nodes of the current level is 
then projected into the next input image where the procedure of 
ntersection testing with the object's silhouette is repeated. Once 
all input images have been processed for the current octree 
level, the current level is incremented by one and the whole 
procedure (starting from the projection of the black nodes of the 
current level into the first input image) is repeated, until the 
maximal octree level has been reached. The remaining octree 
after the processing of the last level is the final 3D model of the 
object (Figure 4e). 
We define the following coordinate systems relevant for the 
projection of an octree node into the image plane: 
• octree coordinate system : rooted at the intersection of the 
rotational axis of the turntable and its rotational plane. For 
the first input image, it is identical to the object coordinate 
system and it rotates with the object observed 
• object coordinate system : rooted at the same point as the 
octree coordinate system, but it is static, i.e., it doesn't 
rotate with the object. The y axis is the rotation axis of the 
turntable and the z axis is orthogonal to the image plane 
• image coordinate system : lies in the image plane and it is 
rooted at the image center point 
Figure 5 depicts these coordinate systems and their relative 
positions to one another. 
3.2 Determination of octree nodes 
An octree node is projected into the image plane in the follow 
ing way: as a preprocessing step, the translation and rotation 
matrices and are multiplied for all possible view angles a, and 
the resulting matrices of these multiplications are stored in a 
lookup table. This is done before any processing of octree nodes 
starts. Once it starts, all vertices of the current node are project 
ed into the image plane by multiplying their octree coordinates 
with the matrix from the lookup table corresponding to the 
current view angle and then multiplying the result with the 
appropriate scaling matrix. The result of the projection of an 
octree node into the image plane are image coordinates of all of 
the vertices of the node's corresponding cube. In the general 
case, the projection of a node looks like a hexagon, as depicted 
in Figure 6(a). To find the hexagon corresponding to the eight 
projected vertices is a costly task, because it requires to deter-