# Segmenting Free-Form 3D Objects by a Function Representation in Spherical Coordinates

Segmenting Free-Form 3D Objects by a Function Representation in Spherical Coordinates

¨ Olcay Sertel and Cem Unsalan

Computer Vision Research Laboratory ˙ Yeditepe University, Istanbul 34755, Turkey

Abstract. Segmenting 3D object surfaces is required for various high level computer vision and computer graphics applications. In computer vision, recognizing and estimating poses of 3D objects heavily depend on segmentation results. Similarly, physically meaningful segments of a 3D object may be useful in various computer graphics applications. Therefore, there are many segmentation algorithms proposed in the literature. Unfortunately, most of these algorithms can not perform reliably on freeform objects. In order to segment free-form objects, we introduce a novel method in this study. Di?erent from previous segmentation methods, we ?rst obtain a function representation of the object surface in spherical coordinates. This representation allows detecting smooth edges on the object surface easily by a zero crossing edge detector. Edge detection results lead to segments of the object. We test our method on diverse free-form 3D objects and provide the segmentation results.

1

Introduction

Advances in modern range scanning technologies and integration methods allow us to obtain high precision representations of complex, detailed 3D models of real world objects. These 3D models are widely used for recognition and representation purposes both in computer vision and computer graphics. Computer vision practitioners are shifting their interests to 3D models instead of 2D images or video sequences, due to powerful representation capabilities of these 3D models. Campbell and Flynn [1] provide a through survey on 3D representation and recognition algorithms in computer vision and computer graphics applications. In order to represent 3D objects for recognition purposes, researchers have introduced many segmentation and edge detection methods on range images. The aim is to partition the 3D surface to meaningful subparts. We can divide the range image segmentation methods to three main categories as: region based [2,3,4], edge based [5,6], and hybrid (region and edge based) [7,8,9]. This list is far from being complete, more through review on the subject can be found in [3]. Hoover et. al. [10] o?er a comparison tool for the state of the art range image segmentation methods. They conclude that, segmenting range images is still a major problem in computer vision due to problems in the correct identi?cation of small surfaces and the preservation of the edge location. Unfortunately, these issues are extremely important for 3D object modeling and recognition.

A. Levi et al. (Eds.): ISCIS 2006, LNCS 4263, pp. 343–352, 2006. c Springer-Verlag Berlin Heidelberg 2006

344

¨ O. Sertel and C. Unsalan

To overcome these problems, we introduce a novel free-form 3D object segmentation method in this study. Campbell and Flynn [1] de?ne free-form object as: “a free-form object is often assumed to be composed of one or more nonplanar, nonquadric surfaces”. Most previous work deals with surfaces composed of planar or quadratic surfaces. Although they have fairly good segmentation results, their applicability to free-form objects is relatively poor. Our method is distinct from the previous segmentation methods in the way we represent the object surface by a function form in spherical coordinates. This function representation allows us to detect smooth edges on the object surface reliably. As we obtain the function representation, we apply a Laplacian of Gaussian (LoG) ?lter with an adjustable smoothing parameter to detect edge locations. LoG ?lter also takes into account noise on the object boundary. Finally, we detect zero crossings on the ?lter response and segment the object surface. Although the function representation is applicable to star shaped objects only, we decompose free-form objects to star shaped subparts and apply our method to each separately. Hence, we can obtain segments of free-form objects without any di?culty. We start with explaining the e?ect of changing the coordinate system from cartesian to spherical. Then, we de?ne how to obtain the function representation of star shaped and free-form objects in spherical coordinates. We next de?ne edge detection on the function representation and obtain segments on the object. We test our segmentation method on various free-form 3D objects in the experiments section. Finally, we discuss the results and provide a road map for future studies.

2

The E?ect of Changing the Coordinate System

Most of the commercial range scanners provide the point set of the 3D object in cartesian coordinates. Besides the point set, they also provide the spatial neighborhood of these points encoded by triangulations. There are also many commercial software, providing triangulation if we only have the point set of the 3D surface. For segmentation, we need these triangulation and coordinate information. Researchers have focused on cartesian coordinate representations to introduce segmentation and edge detection for 3D surfaces. Unfortunately, applying edge detection in cartesian coordinates do not provide acceptable results. The main reason for this poor performance is that, most edge detectors are designed for step edges in grayscale images (it is assumed that, these step edges correspond to boundaries of objects in the image) [11]. In range images (3D surfaces), we do not have clear step like changes corresponding to the actual edges of the object. On the contrary, for most objects we have smooth transitions not resembling a step edge. Therefore, applying edge detection on these surfaces do not provide good results. To overcome this problem, we hypothesize that if we represent the same object surface in spherical coordinates, we can detect most smooth edges easily. Therefore applying edge detection on this new representation provides improved

Segmenting Free-Form 3D Objects by a Function Representation

345

results. As we detect edges on the spherical representation, we can obtain the cartesian coordinates of the edges and project them back to actual 3D surface to obtain edge points on the actual surface. Let’s start with a simple example to test our hypothesis. We assume a slice of a generic 3D object (at z = 0) for demonstration purposes. We can represent the point set at this slice by a parametric space curve c(t) = (x(t), y(t), 0) as: c(t) = (cos(t), sin(t), 0) t ∈ [0, π/3) [2π/3, π) (cos(t), sin(t) + 0.3sin(3t ? π), 0) t ∈ [π/3, 2π/3) (1)

This space curve is plotted in Fig. 1 (a). As can be seen, the curve is composed of two parts. However, applying edge detection directly on this representation will not give good results, since we do not have step edge like transition between those two curves.

1.4 1.2 1 0.8 0.6 0.4

1.3 1.25 1.2 1.15

r(θ)

1.1 1.05 1

?0.8 ?0.6 ?0.4 ?0.2 0 0.2 0.4 0.6 0.8

y

0.2 0

0.95 0

0.5

1

1.5

x

θ

2

2.5

3

3.5

(a) c(t) in cartesian coordinates

(b) r(θ) in spherical coordinates

Fig. 1. A simple example emphasizing the e?ect of changing the coordinate system on detecting edges

We can obtain the spherical coordinate representation of c(t) by de?ning θ = t and r(θ) = x2 (θ) + y 2 (θ). Now, our curve becomes: θ ∈ [0, π/3) [2π/3, π) θ ∈ [π/3, 2π/3) (2) As we plot r(θ) in Fig. 1 (b), we observe that the change in the curve characteristics is more emphasized similar to a step edge. This change can easily be detected by an edge detector. Now, we can explore our hypothesis further for 3D objects. r(θ) = 1 1 + 0.6sin(θ)sin(3θ ? π) + 0.09sin2(3θ ? π) 2.1 A Function Representation for Star Shaped Object Surfaces

For an object to be star shaped, the requirement is that there exists at least one center point such that, every surface point (x, y, z) can be seen from it without intersecting other surface points. Therefore, if we apply change of coordinates

346

¨ O. Sertel and C. Unsalan

from cartesian to spherical (taking the center point as the center of our coordinate system) we obtain a function representation, R(θ, φ), in terms of pan (θ) and tilt (φ) angles as: R(θ, φ) = x2 + y 2 + z 2 (3) where θ = arctan y x x2 + y 2 z (4)

φ = arctan

(5)

We will apply edge detection on R(θ, φ). If our object violates star shaped condition, we can not obtain R(θ, φ). We will consider this issue next. 2.2 Multiple Functions for Free-Form Object Surfaces

Star shaped objects belong to a small subset of free-form objects. Therefore, we may not be able to obtain a unique R(θ, φ) function for the overall surface. To overcome this problem, we decompose the free-form object to star shaped subparts using a ray tracing method introduced by Moller and Trumbore [12]. To do so, we start by obtaining the center of mass of the object. From this center, we swipe all pan and tilt angles and apply ray tracing to obtain multiple intersections on the surface. More speci?cally, we test for the ray-triangle intersections and obtain the closest point set on the object. If we obtain more than one radius value for some pan and tilt angle pair, we represent each radius in a di?erent function to obtain di?erent star shaped subparts. We apply this procedure iteratively, until we obtain a full decomposition such that each one is star shaped. Therefore, we obtain multiple non-overlapping R(θ, φ) representations for the same object. We test this decomposition operation on the crocodile object given in Fig. 2. For most of the surface points we do not have multiple radius values except the tail part. As we apply our decomposition method, we obtain two star shaped subparts one representing the body of the crocodile, and the other representing part of the tail (top of the second ?gure). We provide the R(θ, φ) functions for the crocodile in Fig. 3 (a) and (b).

3

Edge Detection on the R(θ, φ) Function

As we obtain R(θ, φ) functions representing the object, segmentation problem simpli?es to detecting edges on these functions separately and combining the ?nal segmentation on the object. In grayscale intensity images, object boundaries can be modeled by step changes. Therefore, most edge detectors are justi?ed for detecting step edges in intensity images to extract object boundaries. As we apply cartesian to spherical coordinate transformation and obtain R(θ, φ) functions, we have similar step like changes corresponding to physically meaningful segments on the actual 3D object. In order to detect these step like

Segmenting Free-Form 3D Objects by a Function Representation

347

Fig. 2. The crocodile object

θ

φ

θ

φ

(a) The ?rst R(θ, φ) function

(b) The second R(θ, φ) function

Fig. 3. Decomposing the crocodile object to two R(θ, φ) functions

changes, we tested di?erent edge detectors on R(θ, φ) functions. Based on the quality of the ?nal segmentations obtained on the 3D object, we picked Marr and Hildreth’s [13] zero crossing edge detector. Zero crossing edge detector is based on ?ltering each R(θ, φ) by the LoG ?lter: F (θ, φ) = 1 πσ 4 θ2 + φ2 θ2 + φ2 ? 1 exp ? 2σ 2 2σ 2 (6)

where σ is the scale (smoothing) parameter of the ?lter. This scale parameter can be adjusted to detect edges in di?erent resolutions, such that a high σ value will lead to coarse edges. Similarly, a low σ value will lead to ?ne edges. To label the edge locations from the LoG ?lter response, we extract zero crossings with high gradient magnitude. Zero crossing based edge detection has many desirable properties. First of all, obtained edge points will form closed boundaries.

348

¨ O. Sertel and C. Unsalan

The zero crossing operation is more robust to noise. Smooth transitions (as in our case) are handled well on zero crossing edge detectors. Besides the desirable properties of zero crossing edge detector, our edge detection method has also some desirable characteristics. If the object is rotated around its center of mass, the corresponding R(θ, φ) function will only translate. Therefore, the new edges obtained will be de?nitely same as in the original representation. As we the label edge points on each R(θ, φ), we project them back to the original 3D object and obtain the ?nal segmentation for the object. In practical applications, one should remember that R(θ, φ) function should be wrapped around since an edge at one corner may correspond to the continuum of another edge at the opposite corner. We handle this wrapping around problem by taking R(θ, φ) function as periodic wrt. (θ, φ) and applying edge detection on more than one period of this function. We provide the edge detection results for the ?rst R(θ, φ) function of the crocodile in Fig. 4 for σ = 1.8 and σ = 4. As can be seen, for σ = 1.8 most of the small changes on the R(θ, φ) function are detected. As we increase σ = 4, more coarse changes are labeled. We will project these edge points on the 3D object and extract corresponding segments in the following section.

θ

φ

θ

φ

(a) Edges by σ = 1.8

(b) Edges by σ = 4

Fig. 4. Edge detection results for the ?rst R(θ, φ) function of the crocodile with two di?erent scales

4

Segmentation Experiments

We test our segmentation method on seven di?erent free-form objects with two di?erent ?lter scale parameters, σ = 1.8 (to obtain a ?ne or detailed segmentation) and σ = 4 (to obtain a coarse segmentation). We provide the coarse and

Segmenting Free-Form 3D Objects by a Function Representation

349

Fig. 5. Coarse segments (with σ = 4.0) obtained from the apple, cow, crocodile, dumbbell, lamb, orange dino, and red dino (for each row)

350

¨ O. Sertel and C. Unsalan

Fig. 6. Fine segments (with σ = 1.8) obtained from the apple, cow, crocodile, dumbbell, lamb, orange dino, and red dino (for each row)

Segmenting Free-Form 3D Objects by a Function Representation

351

?ne segmentation results in Figs. 5 and 6 respectively. We provide three di?erent views of segmentation results for each object in these ?gures. As can be seen from Figs. 5 and 6, our segmentation method works fairly well on seven di?erent free-form 3D objects having fairly diverse characteristics. Almost all the segments labeled on the actual objects correspond to di?erent object parts. In general, there are minor edge detection problems due to the scale of the ?lter for σ = 1.8. At this scale, obtained edges become weaker, hence there may be missing links on some objects. However, this problem can be ?xed by a post processing step.

5

Future Work

We introduced a free-form 3D object segmentation method by changing the coordinate system and representing the object surface as functions in the spherical coordinates. Based on experimental results on diverse objects, we can claim that our method works fairly well in segmenting free-form objects. We plan to use these segments for 3D object recognition in our future studies. Since most of the segments obtained in this study correspond to some physical parts of the actual object, this decomposition may be used for animation purposes in computer graphics applications.

Acknowledgments

We would like to thank Prof. Dr. Patrick J. Flynn for providing the apple, cow, crocodile, dumbbell, lamb, orange dino, red dino objects.

References

1. Campbell, J.R., Flynn, P.J.: A survey of free-form object representation and recognition techniques. Computer Vision and Image Understanding 81 (2001) 166–210 2. Besl, P.J., Jain, R.J.: Segmentation through variable-order surface ?tting. IEEE Trans. on PAMI 10 (1988) 167–192 3. Srikantiah, P., Boyer, K.L., Flynn, P.J.: Saliency sequential surface organization for free-form object recognition. Computer Vision and Image Understanding 88 (2002) 152–188 4. Gotardo, P.F.U., Bellon, R.P.O., Boyer, K.L., Silva, L.: Range image segmentation into planar and quadric surfaces using an improved robust estimator and genetic algorithm. IEEE Trans. on SMC 34 (2004) 2303–2316 5. Wani, M.A., Batchelor, B.G.: Edge region based segmentation of range images. IEEE Trans. on PAMI 16 (1994) 314–319 6. Jiang, X., Bunke, H.: Edge detection in range images based on scan line approximation. Computer Vision and Image Understanding 73 (1999) 183–199 7. Yokoya, N., Levine, M.D.: Range image segmentation based on di?erential geometry: A hybrid approach. IEEE Trans. on PAMI 11 (1989) 643–649 8. Al-Hujazi, E., Sood, A.: Range image segmentation with applications to robot bin-picking using vacuum gripper. IEEE Trans. on SMC 20 (1990) 1313–1325

352

¨ O. Sertel and C. Unsalan

9. Ghosal, S., Mehrotra, R.: An orthogonal moment-based integrated approach. IEEE Trans. on Robotics and Automation 9 (1993) 385–399 10. Hoover, A., Jean-Baptiste, G., Jiang, X., Flynn, P.J., Bunke, H., Goldgof, D.B., Bowyer, K., Eggert, D.W., Fitzgibbon, A., Fisher, R.B.: An experimental comparison of range image segmentation algorithms. IEEE Trans. on PAMI 18 (1996) 673–689 11. Sonka, M., H.V., Boyle, R.: Image Processing, Analysis and Machine Vision. 2. edn. PWS Publications (1999) 12. Moller, T., Trumbore, B.: Fast, minimum storage ray-triangle intersection. Journal of Graphics Tools 2 (1997) 21–28 13. Marr, D., Hildreth, E.C.: Theory of edge detection. Proceedings of the Royal Society of London. Series B, Biological Sciences B-207 (1980) 187–217