The French aircraft industry began paying attention to CAD/CAM before 1960, and the car builders soon followed suit, but their problem was somewhat different It can be said that, from the start, the aim was to obtain a complete description of the shape of the heet-metal parts , i.e. car body elements, and to use it to carry information throughout the entire process, fromstyling to inspection of stamped and assembled parts One of the first and foremost conditions was to adopt a mathemtical solution that could be easily understood and operated by designers, draughtsmen and machine-tool operators Consequently, the system should not be used to translate an already existing set of' drawings, but to directly express with figures and numbers the shape previously defined, be it scantly, by small or large scale sketches and 3D mockups Now, numerical data are carried from R.& D. division to those of Production Engineering and tool shops; it is compulsory, too, that the system be compatible with those of subcontractors and suppliers To get full advanta9e of CAD/CAM, it is often necessary to bring important and radical change in the functioning of R..& D. and Production of' the company , and sometimes to other divisions

Curves and surfaces play a key role in computer vision. In this paper, some of the concepts and developments highlighting this role are described.

Using the concept of synmietric algorithms, we construct a new patch representation for bivariate polynomials: the B-patch. B-patches share many properties with B-spline segments: They are characterized by their control points and by a 3-parameter family of knots. If the knots in each family coincide, we obtain the Bezier representation of a hivariate polynomial over a triangle. Therefore B-patches are a generalization of Bezier patches. B-patches have a de Boor-like evaluation algorithm, and, as in the case of B-spline curves, the control points of a B-patch can be expressed by simpy inserting a sequence of knots into the corresponding polar form. B-patches can be joined smoothly and they have an algorithm for knot insertion that is completely similar to Boehm's algorithm for curves.

Q uadric surfaces such as cylinders and spheres play a fundamental role in CAGD. This paper describes a new method for creating triangular surface patches on a quadric surface. The surface patches are defined using a restricted type of quadratic Bezier control polyhedron. The control polyhedron and the resulting quadric surface patch satisfy all of the standard properties of parametric Bezier surfaces, including interpolation of the corners of the control polyhedron and the convex hull property. A new technique for creating a C1 mesh of these quadric surface patches is also introduced.

In order to interpolate a large network of curves, the Lagrange, cardinal spline, and sinc blending functions are introduced in the present paper.

A smooth and rigid curved surface patch is undergoing 3-D rotational, as well as translational motion. Given two sets of sparse measurements of depth values on the surface at arbitrary points on the image plane at times t = ti and t2, we are required to estimate the corresponding affine transformation. It may be noted that there may not be any direct point correspondence between two such data sets as the range. finder may scan the surface at different locations at two different time instants. In order to solve the problem, we reconstruct a globally smooth surface from scattered data set at time t = t2 and determine the motion parameters by matching the data set at t = t1 on the reconstructed surface. We present a fast algorithm for a globally smooth interpolation of a visual surface from scattered range data. This method is based on matching lower order spatial moments, where the reconstructed surface is given by a linear combination of Legendre polynomials. A stochastic optimization scheme is used as the estimates of the motion parameters are iteratively updated until the data set at t = 1 best matches the shape of the surface at time t2.

Our objective is to show that tetrahedronalization of a convex volume of which we know some points in its surface is an efficient way of triangulating the surface.

In this paper, we present two methods to interpolate the numerical data that describe the reflector surface. The first method is a local method which expresses the surface as a finite series of optimal local spline interpolants with the data values being the coefficient of the spline series. The surface parameters can be efficiently computed by table look up. Without further modification, this method can only be applied to gridded data. The second method is a global method expressing the surface as a series of radial basis functions. The coefficients of the series are determined by solving a simple matrix equation. The matrix of the system is generally full and the computational efficiency is low. However, this method is applicable to surface interpolation from scattered data.

We introduce a subdivision algorithm for shape preserving function interpolation in 111 and JR2 . The method is based on iterative knot insertion and guarantees preservation of convexity. Starting from data points, a sequence of piecewise linear function is generated. The sequence can be shown to be convergent to a C1 function. The process is specially suitted for curve and surface generation in CAGD since it is local and the computation can be stopped whenever the desired visual effect is attained.

A method of solving the uniform bicubic B-spline surface fitting algorithm is proposed which introduces parallelism in a way that may be effectively exploited by a suitable parallel architecture. This method is based on the observation that a tensor product spline surface fitting problem can be split into two spline curve fitting problems and each of these problems can be realized by a macropipeline of fixed size VLSI arrays. In fact, the heart of curve fitting problem consists of a block tridiagonal linear system. Based on the state-of-art electronic and packaging technologies, the size of VLSI arithmetic devices is limited due to the bounded chip area and I/O packaging constraints. A modular approach to achieve VLSI matrix arithmetic solution for the block tridiagonal linear system is amenable from the viewpoints of feasibility and applicability. A matrix partitioning approach is presented to overcome those technological constraints imposed by the number of I/O pins. A block tridiagonal linear system of size mn is then divided into m simple tridiagonal systems of size n and n simple tridiagonal systems of size m by the Dc Boor partitioning theorem. Each of the simple tridiagonal linear systems could be partitioned and mappied into a series of two fixed size primitive VLSI matrix arithmetic arrays including L-U decomposer and triangular system solver. The L-U decomposer and triangular system solver could be realized by a hex-connected processor array and an inverse perfect shuffle machine respectively. It would be shown that a B-spline surface fitting problem for a grid of mn points can be solved by m hex-connected processor arrays having 4 processors, m inverse perfect shuffle machines having n processors and n inverse perfect shuffle machines having m processors in (3(m+n)+2({logzn1 +flog2n)+4J units of time.

Algorithms are presented for constructing G' continuous meshes of degree two (quadric) and degree three (cubic) implicitly defined, piecewise algebraic surfaces, which exactly fit any given collection of points and algebraic space curves, of arbitrary degree. A combination of techniques are used from computational algebraic geometry and numerical approximation theory which reduces the problem to solving coupled systems of linear equations and low degree, polynomial equations.

Transfinite interpolation techniques have been extended to cover rectangular patches having interior constraints. Interior constraints are specified along isoparametric lines defined partly are wholly over the parametric range. The technique helps incorporate additional data for controlling both the shape and parainetrisation of the interior of a surface. An immediate application for the technique is found in the area of computational fluid dynamics (CFD) where these techniques are used to discretise the computational domain. In CFD the isopararnetric surfaces are made to coincide with the boundary of domain and fluid dynamic data at grid points (Points of intersection of isoparametric lines) is computed by solving partial differential equations governing fluid flow. The technique suggested in this paper gives powerful control over the grid generation process. The use of this technique is demonstrated by interpolating doubly curved analytical surfaces such as ellipsoids using contour plots for comparison.

In recent years there has been a renewed interest in concrete aspects of Algebraic Geometry brought on by its applications to engineering and computer science. Especially for modeling problems it is useful to know whether a given algebraic curve or surface can be parametrized by rational or polynomial functions, and if so then how to find such a parametrization.

A method for reconstructing three dimensional objects from given cross-sectional data is described. The method utilizes both volumetric and surface techniques, and produces a triangular facet approximation to the surface of the object. Branching is automatically dealt with. The method, which uses univariate splines as an essential tool, also provides a very compact way of storing the reconstruction.

This paper introduces a new symbolic representation for planar curves. Our approach unifies the problems of curve smoothing, curvature measurement, and curve decomposition. The technique is based on a smoothing operation which causes no perturbation if applied to data composed of ideal model primitives. Thus for natural data, potential model fits are not skewed by the results of the smoothing operation. The representation is based in a decomposition of the curve into regions of roughly uniform curvature. A family of functions is defined that extract the segments of the curve as part of the smoothing process. The representation decomposes the curve at multiple scales and the parts produced appear to correspond to a natural decomposition of the curve. It also allows for multiple descriptions of some parts of the curve. The final representation can be rendered compact, avoids several common disadvantages in noisy curve description, and should be useful for recognition. It is multi-scale, allows arbitrary degrees of precision in describing the underlying data and intuitive appeal. The representation has been tested in a limited curve matching algorithm and preliminary results are promising. Several issues relating to the measurement of curvature information within this framework are presented briefly. The questions of the simplification of the ensuing representation and the extension to three-dimensional surface description are also addressed.

In this paper, we discuss a hierarchical method for object boundary detection and description for a gray-level image. Lower level algorithms focus on the object boundary detection, and higher level algorithms focus on the boundary feature extraction and description. A one pixel wide close-form boundary is first extracted by recursive histogram-based binarization. The histogram is formed with the graylevels of an initial set of edge points obtained by a gradient operator. The purpose of this approach is to facilitate the selection of a set of good corner points. With this set of corner points, a parametric description of the object boundary is generated. In the high level representation, a cubic spline curve between every two boundary corner points is generated. The entire object boundary can then be represented as the connection of a set of spline curve. Since a cubic spline curve needs only 4 parameters, the final representation of the object boundary is very efficient. Difference between the close-form boundary by recursive binarization and the spline representattion is also compared and discussed.

Rational curves and splines are one of the building blocks of computer graphics and geometric modeling. Although a rational curve is more flexible than its polynomial counterpart, many properties of polynomial curves are not applicable to it. For this reason it is very useful to know if a curve presented as a rational space curve has a polynomial parametrization. In this paper, we present an algorithm to decide if a polynomial parametrization exists, and to compute the parametrization. In algebraic geometry it is known that a rational algebraic curve is polynomially parametrizable if it has one place at infinity. This criterion has been used in earlier methods to test polynomial parametrizability of space curves. These methods project the curve into the plane and test parametrizability there. But this gives only a sufficient condition for the original curve. In this paper we give a simple condition which is both necessary and sufficient for polynomial parametrizability. The calculation of the polynomial parametrization is simple, and involves only a rational reparametrization of the curve.

Smoothing spline preserving discontinuities, are defined by standard energy minimization problems except that discontinuities are allowed at some fixed breakpoints. A natural approach to locate discontinuities is to further minimize the spline energy also with respect to the breakpoints. Such approaches have been much studied in computer vision (Blake and Zisserman, 1987). We show that, in the case ofn equally spaced data points and large n, such a highly nonconvex minimization problem has strong connections with the usual template matching techniques, and that it can be exactly solved by 0(n) direct algorithms (even for not equally spaced abscissae) provided all the breakpoints are distant enough compared to the smoothing scale. Otherwise a few (Gaus-Seidel type) iterations, based on the previous algorithms, are sufficient in many cases.

The Binary Hough Transform (BHT) is a variation of the standard Hough transform for line detection with slope/intercept parameterization which, for image and accumulator arrays whose dimensions are integer powers of two, needs only additions and binary shifts during its calculation, allows full precision for the representation of the parameters and uses integer arithmetic without rounding errors. This paper presents the BHT and its implementation in hardware (two systolic array architectures and their combination) and software (a sequential algorithm).

Chain coding families are a collection of line drawing representation techniques which use the square grid for sampling and quantization. They include chain codes, generalized chain codes, and polycurve codes. For optimal selection among these techniques, it is important to investigate the properties of the chain coding families. In this paper, we evaluate comparatively precision of chain coding families by applying a stochastic line drawing model. Experimental results show that polycurve codes improve precision over chain codes and generalized chain codes.

In most literatures, contour of a region R is defined as the set of pixels in R that have at least a neighbor outside R . Applying this definition to images with multi-labels, for example, results of segmentation, one will end up with nonoverlapping boundaries between regions. This contradicts with the definition of contour in analog plane and makes shape analysis among regions difficult. This paper uses the concept of extended boundary [FP75][Pa77] and presents a new, efficient contour tracing algorithm that maintains common boundaries between regions. It is shown that, in additional to the common boundary representation, the new algorithm has many advantages over the old approaches.

We consider the problem of determining motion (three-dimensional rotation and translation) of rigid objects from their imagestaken at two time instants. The locations of the perspective projection of each of n feature points onto the image plane from the surface of the rigid body are assumed to be known at those times. We state some results of previous work, and in the important n = 5 case show how all the solutions can be obtained nearly six times as quickly as before. In the cases n =6 and n = 7, all the solutions can be obtained approximately fifteen and thirty times more quickly, respectively, than by the previous method.

We present a new approach to effect the transition between local and global representations. It is based on the notion of a covering, or a collection of objects whose union is equivalent to the full one. The mathematics of computing global coverings are developed in the context of curve detection, where an intermediate representation (the tangent field) provides a reliable local description of curve structure. This local information is put together globally in the form of a potential distribution. The elements of the covering are then short curves, each of which evolves in parallel to seek the valleys of the potential distribution. The initial curve positions are also derived from the tangent field, and their evolution is governed by variational principles. When stationary configurations are achieved, the global dynamic covering is defined by the union of the local dynamic curves.

Orthonormal wavelet bases recently constructed by Ingrid Daubechies provide an efficient means of discretely representing curves and surfaces for computer vision and graphics. Advantages of this representation implied by the scaling, finite extent, and vanishing moment properties of the basis functions include multi-level algorithms, spatially adaptive resolution, and high order approximations with respect to Sobelev norms. This paper reviews the construction of these wavelet bases and describes wavelet discretization methods. It discusses two specific applications to surface estimation and reconstruction and presents preliminary numerical results.

Gaussian curvature K and mean curvature H are stringent properties of surfaces. Surfaces can be segmented based on the (K,H) sign pair, which classifies surfaces into eight types. To obtain a good KH sign image from raw depth data, it requires a surface approximation up to the degree of curvature signs. The conventional Hermite's interpolation, which can produce an approximation version up to given derivatives at certain surface nodes, is no use for this task because 1) there is only data for surface depth and nothing for derivatives at all; 2) noise in raw data should be reduced rather than be retained in approximation. These suggest that using depth data alone to approximate a surface up to the degree of curvature signs is an underconditioned fitting problem. In practice, a feasible approximation can be obtained by using a recursive piecewise surface fitting with a set of selected low order basis functions, where the surface fitting is decomposed into 1-D polygonal fittings associated with parabolic corrections. In this paper five lemmas, a theorem and two corollaries are given to discuss the feasibility of such a solution.

This paper discusses a new algorithmic approach to computer graphics which significantly reduces the time-circuitry complexity producL Our approach eliminates the redundancy found in current representations of piecewise polynomial splines (curves, surfaces and volumes). We are able to obtain exactly the same results as current graphics systems with only a fraction of the computation (1/10 for curves, 1/100 for surfaces, 1/1000 for volumes). We present algorithms for curve and surface generation, refinement and, transformation of graphics images (rotation, translation, scaling). A complexity analysis is provided for comparison to current approaches.

A new approach to multiple target tracking is considered in this paper. We consider a frame of data to consist of target positions and intensities measured on a focal plane at a discrete sample time. By superimposing data points from multiple frames, an image plane is formed in which target tracks appear as digitized lines or curves. Our model for the target trajectories contains accelerations so the tracks appear as quadratic curves. We view these curves in the image plane as planes in a three-dimensional space by introducing a third variable as a function of one of the planar coordinates. The 3-D Radon transform of the intensity function is taken with respect to these specially defined planes. A curve detection algorithm based on the Radon transform domain is then developed. We present simulation results to show the performance of the algorithm and discuss implementation and future work.

A new algorithm for the Generalized Hough transform is presented. The information available in the distribution of image points is used to optimize the computation of the transform. The calculated parameters are those associated with a single image point and all other image points in combinations of the minimum number of points necessary to define an instance of the shape under detection. The method requires only one dimensional accumulation of evidence. Using the algorithm, the transform of sparse images is more efficiently calculated. Dense images may be segmented and similarly processed. In two dimensions, the method provides a feedback mechanism between image and transform space whereby contiguity of feature points and endpoints of curves may be determined.

Random fractal surfaces (Mandeibrot surfaces) are finding more and more applications in computer graphics, image analysis and the simulation of naturally occurring topologies. A random fractal as a fractional geometry whose statistical properties are scale invarient. In other words, the object looks similar (statistically) at all magnifications. The generation of a random fractal surface involves the user having to input two essential parameters: (i) the Fractal Dimension (a decimal number D where 2 < D < 3) which controls the surface roughness and (ii) the seed of a random number generator which determines the structure of the surface. By changing the seed, the user can generate different surfaces and by increasing the fractal dimension the surface roughness can be increased. In practice, algorithms of this type do not allow the user to construct a random fractal with specific topological features. Hence, in respect of the surface obtained, the user is ultimately at the mercy of a random number generator. In this paper, we address the problem of how to incorporate a priori information into a Mandelbrot surface in such a way that the end product is still fractal. A solution is provided to this problem which provides the user with control over the general topology of the surface. We demonstrate its application for incorporating low resolution data obtained from geographical/geological survey maps on the topology of a given area. Also, we show how the method can be used to generate synthetic terrain databases for the validation of certain surveying algorithms. The technique employs the Fourier Synthesis Method for generating Mandelbrot surfaces and is based on transmitting a predetermined proportion of the complex Fourier coefficients used to describe a given topology. In addition to its use as a complex terrain modeller, it is also shown how the same technique can be used for data compression of general topologies. The idea here is to describe a surface in terms of a few essential coordinate parameters (a prior information), a given seed and a specific fractal dimension.

The precise specification of surface geometry of an aircraft is one of the most important and major activities inits design. An initial design, defined by the fundamental requirements, is iteratively analysed and modified till a satisfactory configuration is obtained. Very often in the early stages the need to rapidly make modifications to the geometry for immediate analysis overrides the stringency of smoothness and correctness ofthe surfaces. This paper describes the design of an interactive system which enables the designer to quickly specify the surface geometry and to modify it easily and rapidly. In particular, the software engineering aspects are emphasized. The system uses B-splines for the representation of complex geometry. Surfaces of revolution, required to model certain parts ofthe aircraft, and other simple geometric primitives are also supported. Apart from the usual modeller facilities, features such as camber, twist and form constraints such as tangent or curvature control at a point, etc., are also provided. The system enables easy input and rapid editing of geomeiry through the use of a number of innovative concepts which aim at simplifying and speeding up the man-machine interaction. Multiple window display of entities, augmented by plots of curvature, cross sections etc. provide the visualization tool necessary to assist the designer in decision making.

This paper describes the use of computer graphics modeling to simulate laser range and reflectance images. Applications of image processing techniques to computer-generated (C-G) laser images are described and advantages of this system over a physical device are discussed. An example is presented in which laser imaging algorithms are developed and applied to robotic navigation.

A surface measurement performed using a coordinate measuring machine with a mechanical probe may result in errors due to the contact point not being coincident with the recording point on the probe. The error between the recorded point and the surface is a function of the probe geometry and the surface shape. Typically the measured surface is represented by a point table recorded at equal intervals. A conventional way of generating the 'true' surface from the recorded points is based on parametric surface patches. This is applicable as the points are regularly distributed on the surface. All the information necessary to identify the real surface is provided by the orthogonal vector to the surface together with the probe shape. The disadvantages of this method are computational inefficiency, but more importantly there is loss of information resulting from the interpolation techniques used. This information could be vital, especially where surface discontinuities occur. The method proposed in this paper does not use surface patches as the basis of its approach. The information about the 'true' surface is directly extracted from the measured point table by a simple search algorithm. This paper presents the search algorithm results to verify it.

Recently, physically-based models have been used to simulate fractures in solid objects. Due to the finite grid used in this type of simulation, aliasing artifacts occur at fracture edges revealing the structure of the grid. We have developed a method for identifying the fractured edges based on the specific grid structure of the model. We then use arbitrary order Bezier curves to modify the grid structure, concealing it at fracture edges. This results in a more convincing fracture edge.

This paper describes a method concerned with the design and construction of a systeL to measure and record discrete surface locations from actual physical objects. It also investigates different image processing techniques, compaction of graphical data algorithms and 3-D object reconstruction and manipulation, from a laser scanner for the reconstruction of the human soft tissue of the face out of the skull. It is a robotic laser ranging system that automatically generates three dimensional surface co-ordinates starting from homemorphic surfaced objects. The principle of the digitising process is based on triangulation between a laser point, illuminated on the surface of the object and two custom-built light sensors. Given the geometry of the system, one of the light sensors detects the small spot on the object and then calculates a representative point in Euclidean three space. A two degree-offreedom electro-mechanical system translates the laser and rotates the object in order to discretise the entire object. Representations of complex real objects have been generated in a relatively short time with very good resolution. For example, a human skull can be digitised, representing over 5000 surface points, in a little over one hour. The data representations can then be viewed and manipulated in real time on high performance graphics devices or viewed and then animated as a realistic image on raster graphics. The principal aim of this project is to develop Artificial Intelligence and Knowledge based system techniques to infer the depth of the soft tissue and its associated relationship with the skull.

Nonuniform, rational B-splines (NUItBs) are the basis functions used to represent both free-form curves and surfaces and precise quadric primitives such as conics. NURBs are defined as ratios of linear combinations of nonuniform B-spline functions. In this paper, we present a new high-speed algorithm for the computation of nonuniform rational spline curves. We demonstrate this technique on a simple example and provide a computational complexity analysis.

A graph based scene representation scheme is described. The representation scheme is hierarchical, various levels in the hierarchy representing object parts, objects and relationships among objects in the scene. Representation features for each level of representation are discussed. Graph-algebraic operations are defined for deriving the representation features of a particular level of the hierarchy in terms of lower level descriptions. Graph operations are also defined to realise hierarchical model-matching for scene component identification from sensor imagery.

We present a method for making accurate measurements of the instantaneous fractal dimension of (1) images modeled as fractal Brownian surfaces, and (2) images of physical surfaces modeled as fractal Brownian surfaces. Fractal Brownian surfaces have the property that their apparent roughness increases as the viewing distance decreases. Since this true of many natural surfaces, fractal Brownian surfaces are excellent candithtes for modeling rough surfaces. To obtain accurate local values of the fractal dimension, spatio-spectrally localized measurements are necessary. Our method employs Gabor filters, which optimize the conflicting goals of spatial and speciral localization as constrained by the functional uncertainty principle. The outputs from multiple Gabor filters are fitted to a fractal power-law curve whose parameters determine the fractal dimension. The algorithm produces a local value of the fractal dimension for every point in the image. We also introduce a variational technique for producing a fractal dimension function which varies smoothly across the image. This technique is implemented using an iterative relaxation algorithm. A test of the method on 50 synthetic images of known global fractal dimensions shows that the method is accurate with an error of approximately 4.5% for fractal Brownian images and approximately 8.5% for images of physical fractal Brownian surfaces.

A specification of the curvatures at all points determines the surface of an object uniquely except for a translation and a rotation. The aim of this study is to determine the curvatures at different points on various objects in the scene. This is done by a lighting arrangement, wherein the surface of objects are illuminated by a source of light beams which pass through a reference grid structure. The distance information is obtained by finding the intersection points between the lines backprojected from the image to the object and lines projected from the reference grid. The curvature of the surface at a point is calculated by using the information regarding the relative distances of the grid lines as seen on the object around the point. The surface is now uniquely determined as both distance information and curvature is known for different points on the surface. The method presented can be used to obtain the 'curvature image' for machine vision and object recognition applications.

There are currently a number of methods for solving variants of the following problem: Given a triangulated polyhedron P in three-space with or without boundary, construct a smooth surface that interpolates the vertices of P. Problems of this variety arise in numerous areas of application such as medical imaging, scattered data fitting, and geometric modeling. In general, while the techniques satisfy the continuity and interpolation requirements of the problem, they often fail to produce pleasing shapes. Our interest in studying this problem has necessitated the construction of a flexible software testbed that allows rapid implementation and testing of new surface fitting methods and analysis techniques. The testbed is written entirely in the C programming language and is highly portable. Other relevant features of the testbed are discussed, and recommendations for improving the shape characteristics of several interpolation methods are given.

A set of methods is presented for detecting complex surfaces, using collections of simple, uniform processes. The methods are designed to detect surfaces in range data with parameters that can be estimated from local regions (for example, natural quadrics such as spheres). The system uses combinations oflocal estimates of zeroth and first derivative properties, to produce votes for specific parameterizations. Accumulations of votes lead to hypothesized surfaces. A conflict resolution strategy is used to separate the true surface hypotheses from the false ones. The overall approach is based on the ideas ofthe Hough transform and parameter space methods, but is designed to explicitly address shortcomings of these techniques, while maintaining their modularity and efficiency. Examples of these techniques, used to detect natural quadrics in real, low resolution range data scenes, are presented.