An integrated approach for range image segmentation and representation

(1)

An

0954-1810(95)00035-6

integrated approach for range image segmentation and representation

S. K. Bose*

institut

fir Photogrammetrie. Universitiit Bonn, Nujaliee 15, D-53115 Bonn, Germany

K. K. Biswas & S. K. Gupta

Department of Computer Science and Engineering, IIT Delhi, New Delhi 110016, India

This paper proposes an efficient method for the segmentation and representation of 3D rigid, solid objects from its range images using differential invariants derived from classical differential geometry. An efficient algorithm for derivation of surface curvatures, which are atline invariants, at smooth surface patches is proposed. The surface is approximated by Bezier and Beta-splines to compare qualitatively the proposed segmentation scheme. This scheme leads to derivation of surface features, which provides a very robust surface segmentation. An integrated approach represents the surface in terms of plane, quadric and superquadric surface.

Experiments show excellent performance and together with the inherent parallelism make the scheme a promising one. Present experiments were conducted on some real range images where most of the parts of the object are planar.

Key words: range image segmentation, invariants, 3D object recognition.

1 INTRODUCTION

There has been a lot of interest in surface characterization based on curvature properties as a primary step towards range image segmentation and description.‘-3 This is attributed to the following reasons:

(1) Both the signs and values of the surface curvatures provide a great variety of affine invariant surface description, even free-form, object surfaces.

(2) More and more 3D imagery devices are available owing to the development of active or passive 3D sensing technology.

However, the majority of the range image segmentation techniques have restriction on the types of expected surface shapes.4-6

This paper proposes an integrated approach for range image segmentation and description. The underlying theory of the proposed segmentation scheme is to

*Present address: Department of Computer Science and Engineering, IIT Delhi, New Delhi 110016, India.

243

exploit the powerful differential invariants for the segmentation of range images and not to impose strict restriction of surface shapes. Once the image is segmented into various surface patches, we are then describing the surfaces through variable order surface fitting technique. The planar, quadric and superquadric surfaces are included in surface fitting mechanism. The salient feature of this method is that the description is independent of the viewpoint. Experimental results on real dense range data demonstrate significant robustness of the scheme. These results can also be applied directly to the recognition of 3D objects from range images.

The present scheme is more suitable for the industrial environment and especially for an object consisting of planar parts. A block diagram of the proposed scheme is given in Fig. 1.

The paper is organized as follows. The differential invariants are introduced in section 2. Section 3 reviews the range image segmentation techniques. The merits and demerits of various surface description schemes is given in section 4. Section 5 discusses the process of range image segmentation and extraction of surfaces

(2)

244 S. K. Bose, K. K. Biswas, S. K. Gupta

SMOOTHING

1

SURFACE PATCH

1

SURFACE CURVATURE

COMPUTATION

I SURFACE

SEGMENTATION

I PLANE FrrTlNG

6

^A

EXTRACT REMAINING

r--t

NON DESCRIBED SURFACES

YES

EXTRACT REMAINING

NON DESCRIBED --D I

SURFACES - DESCRIBED -

SURFACES

REMAIN TO BE

Fig. 1. Block diagram of surface segmentation and description.

from range images. The surface representation of range images is presented in section 6. Experimental results are presented in section 7.

2 DIFFERENTIAL INVARIANTS

The study of differential invariants concerns the study of the invariance of certain functions of differential parameters (of curves and surfaces) under various transformations. For example, it has been shown in Ref. 7 that seventh order functions of curvature k of a curve are invariant under projective transformation.

2.1 Nature and scope of differential invariants

Just like their algebraic counterparts, differential invariants provide us with a powerful tool from the viewpoint of independent representation. However, these two types of invariants differ markedly in their nature and scope. The algebraic invariants are global in nature, and therefore not very well suited for scenes with objects in cluttered environments, some being partially occluded. Differential invariants, on the other

hand, are local in their nature, and are therefore quite handy for objects in cluttered environments. A for- midable limitation with differential invariants is that seventh order derivatives are required for Euclidean invariants, while fifth order derivatives are required for affine invariants (called Wilcyznski invariants8) and so a number of methods have been derived for matching smooth curves avoiding high order derivatives. Go01 et al.9 and Brill et al.” trade the high order of derivatives with an extra reference point. They define and use what are termed semi-differential invariants, defined by taking into account an extra reference point. Further, they propose a large variety of these invariants differing in the number of reference points, and order of derivatives at reference and general points.

2.2 Applications of differential invariants in vision A lot of work using a differential geometric approach and differential invariants have been reported in the literature. Liang and Todhunter” used the invariance of fundamental coefficients when lines of curvature are used as intrinsic parametric curves for segmentation and representation of surfaces. Go01 et al.” use

(3)

An integrated approach for range image segmentation and representation 245 semi-differential invariants to trade off the higher order

derivatives and Kriegman and Ponce12 study 3D curve recognition from image contours. Bruckstein and Netravali13 use differential invariants of planar curves for recognizing partially occluded shapes.

To compute differential invariants of curves, we can represent the curve in parametric form, x(t) = xi(t), where i= 1,2,3,4 for space curves and i= 1,2,3 for plane curves. One then seeks a differential equation whose solution is the curve xi( t ). The advantage of differential equations is that some constants are eliminated. Here, the aim is to compute differential invariants of surfaces. The surfaces can be any general surface. Details of computation are given in the subsequent sections.

3 REVIEW OF RANGE IMAGE SEGMENTATION This section briefly reviews some of the important range image segmentation techniques. The crux of a segmentation technique is to detect surface discontinuities and smooth surface regions in a range image. Likewise, most surface segmentation techniques can be classified as either edge-based or region-based, depending on whether they emphasize the detection of surface discontinuities or the detection of smooth surface regions, respectively.

3.1 Edge-baaed segmentation

The basic idea behind edge-based range image segmentation techniques is to detect significant surface discontinuities and categorize them as: jump edges, crease edges or curvature edges.14 Langridgei4 describes the problem of detecting and locating discontinuities in the first order derivatives of surfaces determined from arbitrarily spaced data. He has demonstrated his technique on two synthetic range images.

Inokuchi et a1.15 presented an edge-region segmentation operator for range images. A ring operator extracts a one-dimensional periodic function of depth values that surround a given pixel. This function is transformed into the frequency domain using an FFT algorithm. The technique is computationally feasible only with dedi- cated FFT hardware. The operator has been demonstrated on synthetic range images of polyhedral objects.

Mitiche and Aggarwal16 describe a range edge detection technique based on Bayesian optimization. They have demonstrated their segmentation technique on synthetic range data artificially corrupted by additive Gaussian noise.

Fan et al.” describe an edge detection technique based on computation of the principal surface curvatures. Two edge-based segmentation techniques have been described, one suited for noisy range images and the other for relatively noise free images. This technique has been demonstrated on several synthetic and real

range images with satisfactory result. Ponce and Brady”

have also proposed an edge-based segmentation scheme based on surface curvature properties. Their approach determines the surface curvature at each point on the range image. Curves with significant curvature values are used to infer surface boundaries.

A primary drawback of edge-based segmentation techniques is the inevitable fragmentation of the edges in noisy images. If the edges are fragmented or discontin- uous, they must be linked using heuristic techniques.

For this reason, edge-based segmentation techniques have proved to be less popular than region-based segmentation techniques.

3.2 Region-based segmentation

The key idea behind region-based range image segmentation is to estimate the surface curvature at each range pixel and cluster range pixels with homogeneous surface curvature properties to form smooth surface regions. Miligrim and Bjorkland” presented a scheme for the extraction of planar surfaces from range images created by an imaging laser radar. Their system was planned for vehicle navigation. Henderson2’ has developed a method for finding planar faces in lists of xyz points from range data. This method can be used either for range data segmentation or object reconstruction. In this method, curved surfaces are approximated by many polygons.

Faugeras et ak2’ developed a method for the segmentation of range images into planar or quadric patches. This approach is based on a region growing algorithm. Ittner and Jain22 proposed a method for surface curvature characterization based on clustering and local surface curvature measures computed from a normal vector. Range data points are assumed to be in xyz form used in Refs 20, 23, 24 and are first segmented into groups based on 3D coordinates and surface normal vectors using a mean square error criterion.

Vemuri et a1.25 presented a technique that fits tension splines to x, y, z range data and then classifies surface points as parabolic, elliptic, hyperbolic, spherical umbilic and planar umbilic based on spline surfaces.

Experimental results are shown for a polyhedron, a cylinder, a balloon and a light bulb. Hoffman and Jain26 describes a three stage segmentation technique that uses surface curvature values computed to detect convex, concave and planar regions of a range image. Experi- mental results have shown a variety of real and synthetic range images.

In Besl and Jain2’, the surface curvature based segmentation approach is treated as a coarse segmentation and is used to extract a seed region, which would usually lie in the interior of a surface. Then this seed region is iteratively grown in order to find the equation and extent of the corresponding surface. The region growing algorithm needs various types of compatibility, which lead to better segmentation of the surface. The

(4)

246 S. K, Bose. K. K. Biswas, S. K. Gupta Table 1

Peak Ridge Saddle ridge Minimal Saddle valley Valley Pit Flat

H K

<o >o

<o =o

<o <o

=o <o

>o <o

>o =o

>o >o

=o =o

region merging and description algorithms are simple and susceptible to noise and errors. Bes13 presented another algorithm that simultaneously segments a large class of images into regions of arbitrary shape and approximates image data with bivariate functions. The sign of Gaussian (K) and mean (H) curvatures are used to help coarsely segment into the eight basic fundamental surface types shown in Table 1.

4 SURFACE DESCRIPTIONS

The surface description schemes can be broadly classified into two major categories as follows:

(1)

(2)

Global surface descriptions. Here an attempt is made to extract properties of surface directly from images, e.g. the extended Gaussian image (EGI) scheme proposed by Horn28 and others.29-3’ These schemes are highly sensitive to noise and occlusion, since the descriptions are global. Algebraic descriptions are generally global in nature.

Local surface descriptions. Here, an attempt is made to segment the visible surfaces of objects into surface patches, and the information about surfaces is computed from these patches, e.g. local description through segmented patches proposed by Brady et a1.32 Since these descriptions consist of combinations of smaller patch descriptions, they are in general less sensitive to occlusion than the global. A further classification of local surface descriptions is discussed in the following subsections:

4.1 Approximation by simple surfaces

In this method surfaces patches are approximated by planar or simple analytical surfaces, e.g. Coons, Bicubic, B-spline, etc.23,33 Such methods generally do not attempt to find significant surface features prior to approximation, rather the surface is segmented arbitrarily whenever a fit is satisfactory. These methods are found to be inefficient for the surface based description of 3D objects.34

4.2 !3egmented surface descriptions

Here surfaces of range images are segmented at significant physical features, such as prominent discontinuities.‘49’7Y3s These descriptions are found to be better than the earlier ones as they are more stable with respect to small perturbations on the observed surfaces.

We exploit this scheme for the proposed segmentation and description of a range images paradigm. Most existing methods attempt to approximate the segmented patches through simple surfaces. But in our proposed scheme we will try to approximate the surface patches through planar, quadric and superquadric surfaces, which are found to be more accurate for representing physical surfaces.36

In range image segmentation and description, surface curvatures (Gaussian and mean curvatures) have been known to be extremely useful - as they are viewing direction independent. Local surface shapes can be classified into eight different fundamental types on the basis of the surface curvature signs2’ Further, surface curvature histograms can categorize surfaces into more specific types such as plane, spherical, elliptical, cylin- drical, conical, toroidal, etc. Due to the aforementioned advantages of surface curvatures, they are being widely applied for the purpose of range image classification and segmentation, 3D object recognition and 3D scene analysis. In most applications, the signs of both Gaussian and mean curvatures are simultaneously used for local surface classification.

However, since surface curvatures include second order derivatives, they are very sensitive to noise. Very often when one deals with real range images that suffer both from quantization error and noise, this drawback of surface curvatures makes even the differentiation of planar surface from a curved one a fairly complex process. Because of the inevitable noise in the process of capturing range images, the setting of a proper threshold between zero and non-zero curvatures is not easy.

Although smoothing range images before computing surface curvatures can alleviate this sensitivity problem to some extent, it still remains an annoying problem.

5 SURFACE SEGMENTATION AND EXTRACTION

Segmentation of images into regions corresponding to single objects is one of the difficult problems in computer vision. The crux of a segmentation technique is to detect surface discontinuities and smooth surface regions in a range image. Here, we are interested in a region-based approach because of its numerous advantages.’

The underlying theme of region-based surface segmentation is the classification of surfaces based on the sign of Gaussian (K) and mean (H) curvatures and K and H are found to be afine invariant. The most crucial

(5)

An integrated approach for range image segmentation and representation 247

part of surface curvature computation is the formula- tion of a mathematical model of the surfaces whose derivatives can be easily derived. Given range images are usually arrays of the distances from the sensor planes to the observed surfaces, as given by rij=d(Ui,vj); i= 1,2 ,..., m; j= 1,2 ,..., n, where (ui, vi) denotes a sample point on the sensor plane and m,n denote the size of the sensor plane. The surface formula provides a direct representation for the surface functions. It is given by X(U, V) = [u, V,

f (u, v)lT.

Then, the Gaussian (K) and mean (H) curvatures are evaluated as

K = (f"..L

43

(1 +f,2

+fv2,,

HZ LAW +.L +f,,fv'+"Lvfu' - 2ALLLL)

2(1

+f2 +f2)3'2 u v

Now, we compute the partial derivative of 3D digital surfaces through Bezier and Beta-spline approximation of surfaces. The basic approach to obtain the partial derivatives from range images is to determine a continuous differentiable function that best fits the data with respect to some criteria; compute the derivatives of the continuous function analytically and evaluate them at the corresponding discrete points. The function to be used for our purpose must be at least a biquadratic, as it is the minimal degree polynomial surface type needed to estimate first and second order partial derivatives.

We take 4 x 4 patch of range image to fit a Bezier surface, and estimate the partial derivatives at the centre of a Bezier surface patch. For noisy images, we fit a Beta-spline surface to handle the noise through its parameters ,f3i and p2. The above two parameters govern the overall shape of the surface and can be used to ‘fine tune’ the shape of the surface. The theory behind these approximation techniques can be found in any standard text on computer graphics. Therefore, only the final vectors required for computing the derivatives at the centre of a fitted patch are mentioned below:

For the Bezier surface, the vectors are

F” = [3 -3 -3 31

and for the Beta-spline, the vectors are functions of parameters ,f3i and pZ. For the special case of pi = 1 and p2 = 0, the vector changes to

[

1 23 23 1

F=48484848

1

Once the range image is segmented into eight different types of surface patches, we extract the seed regions from various patches using an HK sign map for the purpose of region growing.3

6 SURFACE REPRESENTATION OF RANGE IMAGES

In the previous section, we described the segmentation of range images into eight different types of surface patches and then we extracted the seed regions from various patches from the HK sign map. In this section we discuss a region growing from seed regions. We consider representation of these surface patches using a variable order surface fitting technique such as plane fitting, quadric surface fitting and superquadric surface fitting.

6.1 Region growing

Each isolated seed region is given as input to the iterative region growing algorithm based on variable order surface fitting. The other input to the region growing algorithm is the raw range map. The seed regions are used to serve only as the starting point of region growing, after that the new range data are used to drive the region growing.

Initially a plane is fitted to every small seed region in the range image using a standard least squares technique. The mathematical surface description so obtained is used to grow the seed into a larger region using two criteria. First, a pixel is a candidate for inclusion in the larger region only if it is connected to the original region. Secondly, the actual depth value at that pixel must be closer to the surface fit to the seed, i.e.

the magnitude of the difference between the value of Z predicted by using the equation obtained by least squares method and the actual data input value at that pixel must be less than a certain threshold.

The fitting is done in two passes. In the first pass, pixels are examined from left-to-right, top-to-bottom, in which the right, bottom and bottom right neighbours are used. For symmetrical growth during the second pass, pixels are examined from right to left, bottom to top, in which the left, top and top left neighbours are tested.

After growing the seed region, the new region is again passed to the least squares fitting routine. The pixels included in the region are now tested with the new fit parameters, and the pixels which do not lie within the threshold are removed from the region. Then the region is grown again. Thus, the growing region can not only increase, but may also decrease in size, and thus adapt well to regions with complicated shapes. The region

(6)

248 S. K. Bose, K. K. Biswas, S. K. Gupta growing process is allowed to iterate till the region size

stabilizes.

When the surface cannot grow any further, we increase the order of the surface and from this point, we try to fit a quadric surface. The quadric surface is grown in the same way as the planar surface, except for one difference. The quadric surface is constrained to grow monotonically, i.e. we do not remove a pixel, once included in the region.

The regions which respond to planar and quadric fit are removed from the segmented scene and the rest we try fitting through superquadric surfaces.37 The fitting of a superquadric is done through a non-linear least squares fitting technique. Superquadrics can model a large set of standard building blocks, like cylinders, parallelepipeds and other shapes in between.

A question arises at this point. Why not fit a superquadric surface or higher order surface straight- away to the region in the beginning? There are two main reasons for this. First, for a superquadric surface the equations are more complex, which involve a lot of computation for a least squares fit. Secondly, if we only try to fit a higher order surface, while actually the region can be described by a lower order equation, the coefficients of the higher order terms will tend to zero.

But due to numerical limitations of the digital computer, these do not become exactly zero. The small residual values of these terms lead to errors in the approximation of the lower order terms also, and thus to an overall poor surface fit. Therefore, we first try to grow the region to a plane, and then switch to a higher order surface. But of course, if we have a priori information about nature of the surface, we could exploit it.

Once a region cannot be grown any further, the iteration terminates and the algorithm outputs the equations describing the region. The patches corresponding to the pixels included in the region are removed from scratch copies of the HK sign map. The raw range image and the modified HK sign map are used to extract the next surface. The algorithm terminates when the number of patches remaining in the HK sign map falls below a specified limit.

6.2 Surface fitting

In this section, we discuss how the segmented surface patches can be approximated by algebraic surfaces.

6.2.1 Plane fitting

We perform least squares fitting using the standard normal equations method.38 For the sake of complete- ness, the equation of a plane and its normal equations are given below.

The equation of a plane surface of the form z =f(x,y) is

and the corresponding normal equations for least squares fitting are

c

^{xz =}a0 c x + al c x2 + a2 c xY

This system of equations is solved analytically for ao, al and a2 in terms of the summations, and the explicit expressions are used in our computations.

6.2.2 Quadric surface fitting

The general equation of a quadric surface is F(x, y, z) = ax2 + by2 + cz2 + dxy + eyz +fix

+gx+hy+iz+j=O

Using a least squares method the error E of the above equation can be written as

E =

C F2(Xi,

^Yi,^zi)

i

The coefficients are obtained by minimizing the error E using the eigenvectors of the scatter matrices.38

6.2.3 Superquadric surface fitting

Superquadrics are a family of parametric shapes that were discovered by Danish designer Peit Hein as an extension of basic quadric surfaces.39 Superquadrics have been used or proposed for use as primitives for shape representation in graphics,37 CAD design@ and computer vision4’

A superquadric surface is defined by the following 3D vector.

/al cos $’ cos wt2 \

- ?T<W<P -

The d originates in the coordinate centre and sweeps out a closed surface in space when the two independent parameters, angles 7 and w, change in the given interval;

w is the angle between the x-axis and the projection vector d in the xy-plane, q is the angle between vector 2 and its projection in the xy-plane. Parameters 7 and w correspond to the latitude and longitude angles of x’

expressed in spherical coordinates. Parameters al, a2, a3 define the superquadric size in x, y and z coordinates respectively, el and e2 are the squareness parameters in the longitude and latitude plane respectively. Since the function values of cosine and sine are negative for some angles 11 and w, the first component of vector J? should be written as sgn (cos n - cos w)j_cos q)‘] ) cos w I’?. This prevents components of vector X from having complex values, which are in general a result of a negative

(7)

Based on the above implicit equation of the superquadric surface, the following function is defined.

number raised to a real power. The same holds for the two components of vector x’.

Superquadrics can model a large set of standard building blocks, like spheres, cylinders, parallelepipeds and many shapes in between. Flat leveled shapes are produced when either et or ~2 = 2 and pinched shapes are produced when either e1 or e2 > 2. Modelling capabilities of superquadrics can be enhanced by deforming them in different ways, including tapering, twisting, bending and making cavities.

The additional component exponent e1 does not change the superquadric surface itself but is necessary if the function is used for shape recovery with a least squares minimization method!2

By eliminating parameters 77 and w from the parametric equations of a superquadric surface, we get the

following implicit equation. 7 EXPERIMENTAL RESULTS

To illustrate the proposed scheme, we have performed experiments based on range data. The results of two sample experiments are reported here.

03 W

W m

Fig. 2. (a) Original range image; (b), (c), (d), (e) and (f) are extracted planar surfaces.

(8)

250 S. K. Bose, K. K. Biswas, S. K. Gupta In the first experiment, we have taken range data which

correspond to the range image (Fig. 2(a)). It has been observed that all planar surfaces are segmented in the first iteration itself, i.e. in fit order 1 (Figs 2(b), 2(c), 2(d), 2(e) and 2(f)). Since there are no more planar surfaces, we remove all the segmented surfaces from the original range images. Now we increase the fit order on the remaining image to segment the rest of the surfaces. Here, we increase the fit order to 3, and try to segment through a superquadric surfaces fitting technique. The spherical surface patches of the object become segmented and the shape parameters of the superquadric surfaces cl to 1.00745 and c2 to 0.98826 and the size parameters al, u2, a3 to constant are obtained. Our present scheme is unable to find a mathematical description of the whole of the image. The current surface segmentation scheme can be improved to tackle such situations.

In the second experiment, we consider the range image (Fig. 3(a)). Again, it is noticed that all planar surfaces are segmented out in the first iteration, i.e. in fit order 1 (Fig. 3(b), 3(c), 3(d) and 3(e)). For the remaining surfaces, we increase our fit order to 3 and try to segment through a superquadric surface fitting technique. The fit result returns its shape parameters to cl = 0.10443 and e2 = 1.02046. Our present algorithm is not yet implemented for bending and tapering of superquadrics. Therefore, we are unable to describe the rest of the surfaces of the image (Fig. 3(a)).

The above experimental results are found to be similar for both Bezier- and Beta-spline surface approxi- mations. The Beta-spline surface approximation may be suitable for noisy range images, where the noise can be controlled through its control parameters. We believe that the proposed algorithm will work with various

(e)

Fig. 3. (a) Original range image; (b), (c), (d) and (e) are extracted planar surfaces.

(9)

degrees of acceptability for free form surfaces. We have not tested for general free form surfaces such as a human form or face. However, we have obtained encouraging results for regular surfaces. Further tests are required to ascertain the acceptibility for general surfaces.

8 CONCLUSIONS

The viewing direction in a scene poses a very serious problem to object recognition. The present study is a successful and novel step towards the pose independent representation of a 3D scene from its range images. In this paper, we have presented a new integrated approach to range image segmentation and description using differential surface invariant properties. Noise in range images is inevitable, which restricts us to affine invariants for our present approach. The general differential invariants require higher order derivatives.

But the higher derivatives are more sensitive to noise.

Here, the noisy images are handled suitably through a Beta-spline surface patch fitting to raw range images, where the noise can be controlled through its control parameters. We have also tried through Bezier surface patch fitting to raw range images after it is smoothed for the comparison of results.

The present approach segments the surfaces alge- braically quite well in terms of planar, quadric and superquadric surfaces. Presently, the segmentation module of the approach uses a large number of thresholds. Therefore, some neural network or genetic algorithm based approach is suitable to optimize the thresholds. The algorithm is successfully tested on real range images of man made objects. The work reported here is an ongoing project. We are presently developing many more modules to make the system more robust.

We are also experimenting with various combination of objects. But the objects consisting of planar surfaces have shown excellent results. The present work is suitable for the automatic recognition of 3D objects.

These results can be also used for the generic modelling of 3D objects.

ACKNOWLEDGEMENT

S. K. Bose would like to acknowledge Professor W.

FGrstner of Institut fi.ir Photogrammetrie, Universitgt Bonn, for his critical comments and suggestions.

REFERENCES

1. Arman, F. & Aggarwal, J. K., Model based object recognition in dense range images - a review. ACM Computing Surveys, 1993, 25(l), S-43.

2. Jolin, J. M., Computer vision methodologies. CVGZP:

Image Understanding, 1994, 49(l), 53-71.

3.

4.

5.

6.

10.

11.

12.

13.

14.

Besl, P. J., Surfaces in Range Image Understanding.

Springer-Verlag, New York, 1988.

Boulanger, P. & Rioux, M., Segmentation of planar and quadric surfaces, In Intelligence Robots and Computer Vision: Sixth in series, Proc. of SPZE 848, Cambridge, MA, Nov. 2-6, 1987, pp. 395-403.

Han, J., Voltz, R. A. & Mudge, T. N., Range image segmentation and surface parameter extraction for 3D object recognition of industrial parts. Proc. IEEE Conf. on Robotics and Automation, New York, 1987, pp. 380-6.

Taylor, R. W., Savini, M. & Reeves, A. P., First segmentation of range imagery into planar region, CVGZP, 1989, 45,42-60.

Weiss, I., Projective invariants of shapes. Proc. DARPA ZUW, 1988, pp. 1125-34.

Lane, E., A Treatment on Projective Dtflerential Geometry.

The University of Chicago Press, 1941.

Van Go01 et al., Semi differential invariants. In Geometric Invariance in Computer Vision, ed. J. L. Mundy 8c A. Zisserman. MIT Press, Cambridge, MA, 1992, pp. 297-3 14.

Brill, M. M. et al., Projective invariance in two and three dimensions. In Geometric Invariance in Computer Vision, ed. J. L. Mundy & A. Zisserman. MIT Press, Cambridge, MA, 1992, 197-218.

Liang, P. & Todhunter, J. S., Three dimensional shape reconstruction from intensity image by minimum energy principle. Proc. 2nd Conf. on Artificial Intelligence Applications, 1985, pp. 100-5.

Kriegman, D. J. & Ponce, J., On recognizing and positioning curved 3D objects from image contours.

IEEE PAMZ-12, 1990, 1127-37.

Bruckstein, A. M. & Netravali, A. N., On differential invariants of planar curves and recognising partially occluded planar objects. TR, AT and T, 1990.

Langridge, D. J., Detection of discontinuities in the first derivatives of surfaces. CVGZP, 1984, 27, 291-9.

15. Inokuchi, S., Nita, T., Matsuda, F. & Saknrai, Y., A three dimensional edge-region operator for range images. Proc.

6th ZCPR, 1982, pp. 912-20.

16. Mitiche, A. & Agganval, J. K., Detection of edges using range information. IEEE PAMZ, 1983, 5, 174-8.

17. Fan, T. J., Medioni, G. & Nevatia, R., Matching 3D objects using surface descriptions. Proc. IEEE Znt. Conf. on Robotics and Automation, Pennsylvania, 1988, pp. 1400-6.

18. Ponce, J. & Brady, M., Towards a surface primal sketch.

Proc. IEEE Znt. Conf. on Robotics and Automation, St Louis, 1985, pp. 420-5.

19. Miligrim, D. L. & Bjorklund, C. M., Range image processing: planar surface extraction. Proc. 5th ZCPR, 1980, pp. 912-19.

20. Henderson, T. C., Efficient 3D object representation for industrial vision systems. IEEE PAMZ, 1983, 5(6), 609-17.

21. Faugeras, 0. D., Hebert, M. & Pauchon, E., Segmentation of range data into planar and quadric patches. Proc. 3rd CVPR, 1983, pp. 8-13.

22. Ittner, D. J. & Jain, A. K., 3D surface description from local curvature measured. Proc. CVPR, New York, 1985, pp. 119-23.

23. Bhanu, B., Representation and shape matching of 3D objects. IEEE PAMZ, 1984, 6, 340-51.

24. Faugeras, 0. D. & Herbert, M., The representation, recognition and locating of 3D objects. International Journal of Robotics Research, 1986, 5(3), 27-52.

25. Vemuri, B. C., Mitiche, A. & Aggarwal, J. K., Curvature based representation of objects from range data. Image and Vision Computing, 1986, 4, 107-44.

(10)

252 S. K. Bose, K. K. Biswas, S. K. Gupta

26. Hoffman, R. & Jain, A. K., Segmentation and classification of range images. IEEE PAMI-9, 1987, 608-20.

27. Besl, P. J. & Jain, R. C., Invariant surface characteristic for 3D object recognition in range images. CVGZP, 1986, 33(l), 33-80.

28. Horn, B. K. P., Extended Gaussian images. Proc. IEEE, Dec. 1984,72, 1656-78.

29. Laffey, T. J., Haralick, V. M. & Watson, L. T., Topographic classification of digital image intensity surfaces. IEEE Proc. Workshop on Computer Vision:

Representation and Control, 1982, pp. 171-7.

30. Lin, C. & Perry, M. J., Shape description using surface triangulation. IEEE Proc. Workshop on Computer Vision:

Representation and Control, 1982, pp. 38-43.

31. Sethi, I. K. & Jayaapamamurthy, S. N., Surface classification on using characteristic contours. Proc. of ICPR, August 1984, pp. 438-445.

32. Brady, M., Ponce, J., Yuilie, A. & Asada, H., Describing surfaces. Proc. 2nd International Symposium on Robotics Research. MIT Press, Cambridge, MA, 1985.

33. Oshima, M. & Shirai, Y., A scene description method using three dimensional information. Pattern Recognition, 1979, 11,9-17.

34. Boult, T. E., Energy based segmentation of very sparse range surfaces. Proc. IEEE Int. Conf. Robotics and Automatica, 1990, pp. 232-7.

35. Gupta, A. & Bajcsy, R., Part description and segmentation using surface and volumetric primitives. Tech Report MS-CIS-89-33, University of Pennsylvania, 1989.

36. Bose, S. K., Biswas, K. K. & Gupta, S. K., Range image segmentation and description using differential invariants. Accepted for presentation in Third European Congress on Intelligent Techniques and Soft Computing - EU-FIT’95 Aachen, Germany, Aug. 28-31, 1995.

37. Barr, A. H., Superquadrics and angle preserving transformations. IEEE Computer Graphics and Applications, 1981,1,11-23.

38. Press, W. H., Flannery, B. P., Teukolsky, S. A. & Vettering, W. T., Numerical Recipes. Cambridge University Press, Cambridge, 1986.

39. Gardiner, M., The superellipse: A curve that lies between ellipse and the rectangle. Scientific American, 1965, 231, 222-34.

40. Elliot, I., Discussion and implementation description of experimental interactive superquadric based 3D drawing system. Internal Report LP2/IME4, European Computer Industry Research Center, Munich, 1986.

41. Pentland, A. P., Perceptual organization and the representation of natural form. Artzj7cial Intelligence, 1986, 28, 293-331.

42. Solina, F., Shape recovery and segmentation of range images. PhD thesis, University of Pennsylvania, 1987.