EXTRACTION OF OUTCROP POINTS FROM VISUAL HULLS FOR MOTION ESTIMATION
Masahiro Toyoura†, Masaaki Iiyama‡, Koh Kakusho‡ and Michihiko Minoh‡† Graduate School of Informatics, Kyoto University‡ Academic Center for Computing and Media Studies, Kyoto University†toyo@mm.media.kyoto-u.ac.jp, ‡{iiyama,kakusho,minoh}@media.kyoto-u.ac.jp
ABSTRACTIn this article, we discuss 3D shape reconstruction of an object in a rigid motion with the volume intersection method.
When the object moves rigidly, the cameras change their relative positions to the object at every moment. To estimate themotion correctly, we propose new feature points called outcrop points on the reconstructed 3D shape. These points areguaranteed to be located on the real surface of the object.
If the rigid motion of the object can be correctly estimated, cameras at different moments serve as the cameras indifferent positions virtually. With these cameras in time sequences, we can increase accuracy of the reconstructed 3D
shape without increasing the number of cameras. Based on
this idea, we reconstruct an accurate shape of the object inmotion from images obtained by limited number of cameras.
As the result, we can acquire an accurate shape from images
in time sequences.
1. INTRODUCTION
With the volume intersection method [5], a shape of a 3D
physical object is reconstructed from silhouettes of obtainedimages. The reconstructed shapes are called visual hulls, orVHs. The silhouettes show regions which the object is projected. In the volume intersection method, textures of the objects are not used for the shape reconstruction. It results thatthe method can be applied even for textureless objects.
With the volume intersection method, additional regions,which are not included in the object’s region, decrease withincreasing the number of cameras. Decreasing the additional
regions means that the reconstructed shapes become more accurate. However, it is not realistic to install so many cameras
around the object due to constraints of mounting them.
Let us suppose that the object is in a rigid motion. Whenthe object moves rigidly, cameras change their relative positions to the object at every moment. If the rigid motion of
the object can be correctly estimated, images obtained by thecameras at different moments are treated as the images in different positions virtually. With these virtual images, an accurate VH is reconstructed without increasing the number ofcameras. Based on the idea, Cheung et al. [1] have proposed amethod for reconstructing an accurate shape from silhouettes
in time sequences.
Frontier points [2] [3] [4] [6] [7] are generally used as thefeature points for estimating the motion of the object. Cheunget al. also employ the frontier points. They are extracted fromthe VH. There is a tendency to be extracted a large number ofthe frontier points when the many cameras are used for shapereconstruction. The problem of the motion estimation withthe frontier points is that it costs time to estimate the motion
with the large number of the feature points. To solve the problem, we propose a new kind of feature points called outcrop
points. The outcrop points form a subset of the frontier points.
Imposing a new condition for the frontier points provides theoutcrop points.
To estimate the motion, the feature points at every moment must be the same. When the feature points at a moment
do not correspond to the feature points at the next moment,
it is difficult to estimate the motion accurately. Since the VH
includes the additional regions, the frontier points may be included in the additional regions. When they are included in
the additional regions, they may not be extracted from the VH
at another moment. Compared to the frontier points, the outcrop points are guaranteed to be included in the surface of theobject. With the outcrop points, the outcrop points provide themotion estimation of the object with small number of points.
In Sections 2, we propose to extract new feature points,i.e., the outcrop points. Experimental results are given in Section 3, and future work is discussed in Section 4.
2. EXTRACTING FEATURE POINTS
2.1. Conditions Required for Feature Points
In order to estimate the motion of the object, we have to extract some feature points from the VH at each moment.
Whereas the object region is included in the VH for all thetime during the object moves, the additional regions aroundthe object region change in time sequences due to change relative positions between the object and the cameras. The feature points that are not included in the object region may not
be included in another VH obtained from another pair of silhouettes. The feature points have to be included in the object

Visual hull V

Epipolar line

Epipolar line
Outcrop points
edgem

Frontier points(a) Extraction of frontier points

Frontier points(b) Fault of extraction of frontier points
Fig. 1. Extraction of frontier points.

regions of the VH, and thus they must be included in the VH
at any moment.
However, it is not easy to extract the points that are guaranteed to be in the object regions from the VH itself, because
the additional regions around the object region change at every moment. Any point of the object regions may be occluded
from the additional regions.
2.2. Frontier Points
In the previous work, there are some proposals for extracting
the feature points from silhouettes. These feature points arecalled frontier points or epipolar tangencies [2] [3] [4] [6] [7].
In this subsection, we discuss the problem of these featurepoints.
When the object is observed by a pair of cameras, a pointon the surface of the object and the optical centers of the twocameras form a plane called an epipolar plane. Based on thisepipolar geometry, if the point constitutes the same epipolar
plane together with a point on the contour of the silhouette as
illustrated in Figure 1(a), the point can be considered to be in
the object region. The point is called the frontier point.
The frontier point seems to be useful as a feature pointthat satisfies the condition of the previous subsection, which
they must be included in the VH at any moment. However, thefrontier point is not actually guaranteed to be included in theobject region. Let us suppose the case in which an epipolar
plain has more than one tangent point with the object region
as shown in Figure 1(b). In this case, the point represented by
an open circle in the figure is included in the VH constituted
with the silhouettes of the two cameras. That point is regarded

Image of Cm

Fig. 2. Extraction of outcrop points.

as the frontier point in spite that it is not actually included inthe object region.
The frontier points are extracted based on the epipolar geometry with each pair of cameras. When many cameras areused, many fake feature points are extracted. Let us denotethe number of the feature points is represented by N, it costs
time of O(N 2 ) to estimate the motion of the object to makecorrespondence. To estimate the motion effectively, only thefeature points that are included in the object regions must beextracted.
2.3. Outcrop Points
When a voxel v in the VH satisfies the following conditions,
we define v as outcrop point as illustrated in Figure 2:
1. The projected pixel of v is included in the contour pixelsof the silhouette of at least one image.
2. For each image satisfying 1, the projected pixel of v does
not coincide with the projected pixel of any other voxel of theVH.
The condition 1. corresponds that of extraction of the frontier
points. In Figure 2, edgem is a set of pixels on the contour ofthe silhouette, and V is the VH composed with the silhouettesof all the cameras.
In principle, the outcrop points are guaranteed to be included in the object region. If the voxel v satisfies 1 for animage, at least one voxel of the object region can be projectedto the pixels to which v is projected. When v also satisfies thecondition 2, v is only the voxel that is projected to the pixel. It
means that v is guaranteed to be included in the object region.
The outcrop points are extracted based on the silhouettes
and the VH. Even if the many cameras are used, no fake feature points are extracted as the outcrop points. Due to thedifference between the principles of extraction, the number ofthe outcrop points is smaller than that of the frontier points.
3. EXPERIMENTAL RESULTS
In order to compare our proposed outcrop points with thefrontier points, we show experimental results for some simulated shapes. Since the frontier points and the outcrop points
are extracted from the VH, they are difficult to be extracted forsmooth shapes, which do not represent their features on theobtained silhouettes. We employ the smooth spherical shapes
as follows for our experiments.
 0 x = cosθcosφ
y 0 = sinθcosφ
 0z = sinφ(0 ≤ θ ≤ 2π, −π/2 ≤ φ ≤ π/2)
r = Al cosFl πx0 · cosFl πy 0 · cosFl πz 0
 x = (r + r0 )cosθcosφy = (r + r0 )sinθcosφ
z = (r + r0 )sinφ0where Al denotes the amplitude of the fluctuation on surface,and Fl denotes its frequency. The radius of the sphere r is set
to 50. Since the outstanding points are created by the fluctuation is controlled by Al s and Fl s, the feature points are easy
to be expected with larger Al and larger Fl . Appropriate feature points give accurate reconstructed shapes by integrating
images in time sequences.
The results for Fl = 4, 6 and Al = 2, 4 are shown inFigure 3. In these experiments, the objects are translated by
1 voxel along X,Y,Z-axes and rotated by 2 degrees around Zaxis for each frame. 20 cameras are set on the vertices of adodecahedron surrounding the object. We employ the VH byusing 40000 cameras in order to evaluate the error of eachexperimental result. We call this shape a correct shape of theobject in the volume intersection method, because concavesurfaces of the object can not be reconstructed with volumeintersection method.
Each experimental result is compared with the correct shapebased on the three types of voxels: missing voxels, additionalvoxels and error voxels. The missing voxels are those included in the correct shape yet not in the result, whereas theadditional voxels are those included in the result yet not in
the correct shape. The error voxels are the summations of
the number of the missing voxels and the additional voxels.
Figure 3(c), (f), (i) and (l) illustrate each type of voxels.
If the outcrop points or the frontier points are used for themotion estimation, except for the object with Fl = 4, Al = 2,the error voxels monotonically decrease. The error voxels forthe object with Fl = 4, Al = 2 increase after the numberof the image frames used for shape reconstruction exceeds
nine, because the surface of the object does not have sufficientnumber and length of salient points to keep extracted as theoutcrop points.
For the VH of each object through all frames, the number of the frontier points is 27142 on average. Compared to
the number of the frontier points, only 1182 points are extracted as the outcrop points on average. As the result, theoutcrop points are superior to the frontier points, because bothkinds of the points give almost same motion estimation andthe number of the outcrop points is much smaller than that of
the feature points.

From this experimental results, Fl should be larger than
6 or Al should be larger than 4 in order to increase accuracyof the 3D shape with the outcrop points as well as with thefrontier points. Since we set r to be 50, Al = 4 corresponds
to 8% of the length of the whole object, and 6.24 pixels inthe silhouettes. In the shape with Fl = 6, salient points exist
every 30 degrees on the surface. These are the conditions
required for the object shapes for increasing accuracy withthe outcrop points.
4. CONCLUSIONS AND DISCUSSION
In this paper, we introduce a method for increasing accuracyof the reconstructed shape by using the rigid motion of theobject. In order to estimate the motion of the object from theVH at each moment correctly, we proposed new feature points
called the outcrop points. In the experiments with the simulated objects, it is shown that the outcrop points are effective
for the motion estimating of the objects. By integrating images in time sequences based on the estimated motion, thereconstructed shape is more accurate than that from imagesof a single frame. Compared from the frontier points, the outcrop points represents the feature of the object with the small
number of points.
Similar to extraction of the frontier points, extraction of
the outcrop points is sensitive to the error of image processing for extracting the silhouettes. It is necessary to improveimage processing for extracting the correct silhouette in realenvironment.
5. REFERENCES[1] German K.M. Cheung, Simon Baker and Takeo Kanade, “Visual Hull Alignment and Refinement Across Time : A 3D
Reconstruction Algorithm Combining Shape-From-Silhouettewith Stereo, ” Proc. CVPR, pp.77-84, 2003.
[2] R.Cipolla, K.E.Astrom and P.J.Giblin, “Motion from the frontier of curved surfaces, ” Proc. ICCV, pp.269-275, 1995.
[3] Y. Furukawa, A. Sethi, J. Ponce and D. Kriegman, “Structureand Motion from Images of Smooth Textureless Objects, ”
Proc. ECCV, vol. 2, pp. 287-298, 2004.
[4] C. Hernández Esteban and F. Schmitt, “Using Silhouette Coherence for 3D Image-based Object Modeling under Circular Motion, ” Technical report 2003D011, Ecole Nationale
Supérieure des Télécommunications, September, 2003.
[5] W.N.Martin and J.K.Aggarwal, “Volumetric Description ofObjects from Multiple Views, ” TPAMI, vol.5, no.2, pp.150–
158, 1983.
[6] Dan Snow, Paul Viola and Ramin Zabih, “Exact Voxel Occupancy with Graph Cuts, ” Proc. CVPR, 2000.
[7] Sundar Vedula, Simon Baker, Steven Seitz and Takeo Kanade,“Shape and Motion Carving in 6D, ” Proc. CVPR, 2000.

(a)(b)

(d)

(c)

(g)

(f)

(h)

(i)

(e)

(j)

(k)(l)

Fig. 3. Integratation for images of 18 frames : (a) An object shape of F l =4, Al =2. (d) Fl =4, Al =4. (g) Fl =6, Al =2. (j) Fl =6,Al =4. (b), (e), (h) and (k) are outcrop points (OPs) for each shape. (c), (f), (i) and (l) show ratios of error voxels of integrated
VHs. In (c), summations of additional voxels and missing voxels are increasing after 9th frame, even if the frontier points (FPs)are used. In (f), (i) and (l), the summations are decreasing until 18th frame with both kinds of feature points.