Method and apparatus for the scanning of spatial objects and to create a three di- mensional computer model Field of the Invention The object of the invention is a method and an apparatus for the scanning of a spatial object and to create a three dimensional computer model in the course of which the ob- ject is illuminated from at least one direction, picture recordings are taken from the il- luminated object from different directions relative to the direction of illumination by rotating it in a predetermined way around a predetermined axis, the pictures are re- corded on a data medium, every part of the recorded picture containing an illuminated profile of the object is selected as shaped line information and from the shaped line in- formation polygonal mesh is produced by an in itself known picture processing program and the polygonal mesh is provided with a texture from the original picture information.

Background of the Invention Up to now very expensive systems and devices of high technical precision, among this optical or mechanical scanners have served for the digitization of irregular spatial shapes, for example a human face, preventing the widespread use of the computer mod- els which may be produced by this means.

The system of Immersion Corporation in the USA named"Microscribe"is equipped with a four axis robot arm, having a rotation sensor mounted on every link (joint). The object to be scanned has to be placed beside the arm and by sliding the free end of the arm on the surface of the object the spatial position of the tactile point can be unambi- guously calculated by computational means from the positions of the sensors.

An apparatus named"PICZA"of Roland DGA Corporation, USA also uses mechanical scanning, deviating among other things from the previous device in the fact that while the former device is a hand operated and direct contact equipment, an automatic solu- tion is used here, which is not in contact with the object to be scanned. The object to be scanned, which is placed onto the base of the device, is scanned by an automatically moved equipped with a piezo distance sensor.

Summary of the Invention A common and well known deficiency of all the mechanic equipment is that their use is limited primarily to objects of solid surfaces and the velocity of scanning is usually slow.

To eliminate the above deficiencies optical scanning devices have been developed, which mostly illuminate the object placed before the scanner with a structured pattern drawn by a laser beam, which is directed with the help of a controllable position mirror.

The signal of a recording means, mostly a CCD camera, which is placed at a given dis- tance from the mirror, is processed by a microprocessor based processing unit. The cal- culation is based on the known principle of triangulation distance measurement. The US company MetaCreation Corporation is currently marketing such a device under the brand name of"RTG".

Optical laser scanning is also employed by the device named"VIT"of the National Re- search Council Institute for Information Technology, which is a so called a synchro- nized laser scanning device. A mirror with reflective surfaces on both sides is used in this device to project the laser beam, and at the same time to divert the light reflected from the object towards the optics of the CCD sensor of the recording means. The laser beam is transmitted via an optical fiber to a moving scanning mirror, the movement of which is controlled by a motor in a layout constructed according to the principle used in galvanometers. The mirror is attached to the shaft of the motor and the controlled motor spreads the beam in a fan like motion, thus generating a plane in space. This light is projected by an other standing mirror onto the object to be scanned. The light reflected from here reaches a third, also standing mirror and from there, via the back surface of the moving mirror reaches the optics of the CCD sensor. Due to the symmetric layout, the reflected light results in a brighter straight line on the sensor, the length of which depends on the object distance, therefore in the named application a CCD line array is used instead of a two dimensional sensor. The electronic processing unit connected to the CCD sensor measures the maximum value corresponding to the length of the bright line and from the amount of this signal, by knowing the instantaneous position of the motor, i. e. the projection angle, and by using the exact geometry of the measuring lay- out the spatial coordinate of the light spot falling on the object may be unanimously cal- culated. The signals of the linear CCD, the maximum value detector and the signals of

the controlled motor are evaluated by a very fast real time microprocessor based control unit.

The largest disadvantage of the optical, more precisely laser scanning devices is that while they are capable of solving the problem suitably and with high precision, they are so complicated that only specialist of sufficient training may use them for professional purposes.

Ordinary light is used for scanning a spatial object by the device named"Sphinx"of the 3D-Systems GmbH, which in essence consists of the rotating plate holding the object to be scanned, the camera used as recording means and a computer containing a video digitizing card (frame grabber card), as well as a program package that has been devel- oped to carry out the method. To generate the computer model, the object is placed onto the plate, is illuminated and with the help of a camera that is advantageously placed ex- actly opposite to the light source, the rotated object is photographed under computer control from different directions. From the pictures thus taken, more exactly from the recorded silhouettes of the object, the three dimensional computer model is calculated by the program package. This solution is certainly simpler than the laser scanning de- vices, but still places to high requirements on the hardware, as it presupposes a Silicon Graphics or Sun SPARC Workstation computer, which for a specialist unanimously qualifies the requirements. An other disadvantage is that the surface cavities, unless they can be seen on the silhouettes, do not show up properly.

The purpose of the invention is primarily the three dimensional computer modeling of real spatial objects and within this the scanning of irregular shaped objects in a wide spread personal computer environment.

The invention is based on the idea that by using normal light and a proper layout of ob- ject, light source and recording means and by a relatively simple processing of the ob- tained information a spatial effect, three dimensional picture my be constructed and dis- played from two dimensional projections of the scanned object.

During the solution of the task aimed at, a method has been used as base for scanning the spatial object and for generating the three dimensional model, in the course of which the object is illuminated from at least one direction, pictures are taken from the illumi- nated object from different directions relative to the direction of illumination by rotating

it in a predetermined way around a predetermined axis, the pictures are recorded on a data medium, every part of the recorded picture containing an illuminated profile of the object is selected as a shaped line, from the shaped line information a polygonal mesh is produced by an in itself known picture processing program and the polygonal mesh is provided with a texture from the original picture information. This was developed fur- ther in the sense of the invention by illuminating the object with a white line of light matched to the axis of rotation and parallel to it, and further on during the selection of the details and their recording as information a matrix containing black and white pic- ture points is formed and the thickness of the shaped line is reduced by averaging to a picture point in order to increase the accuracy, the eventual breaks in the shaped line are terminated by computation, the space coordinates of the points making up the shaped line are calculated based on the exact position of the object, the recording means and the illuminating light source.

In an advantageous implementation of the method according to the invention the even- tual breaks (discontinuities) in the shaped line are terminated by using an incremental algorithm.

In a further advantageous implementation of the method according to the invention the eventual breaks in the shaped line are terminated by an approximation with the original profile curves.

It is also advantageous in the sense of the invention if more than one light sources of different positions are used to reduce the effect of details of the object blanking other parts of the object as seen from the point of view of the recording means. This might happen advantageously alternatively, and in this case a separate picture is taken with each light source.

It is further advantageous if for the reduction of perspective distortion the recording means is placed at possibly the largest distance from the object defined by the quality of the picture recording and the distance is determined by placing a reference grid in place of the object, within its depth range, and a record is taken from it and by comparing the recorded picture and the reference grid the correction of the horizontal and vertical co- ordinates are carried out after which this comparison is repeated by replacing the refer- ence grid within the depth range of the object and by this the correction of the depth co- ordinate is also determined.

Besides the above, it is also advantageous if the vertical resolution of the recorded im- age is increased by setting the more sensitive direction of the optics of the recording means parallel to the axis of rotation of the object.

Further on, during the solution of the tasked aimed at, a device has been taken as a basis for implementing the method according to the invention, which possesses a device for illuminating the object to be scanned from at least one direction, a recording means taking picture records of the object to be scanned form a direction which is different from the direction of illumination, a device for setting the distance of the recording means relative to the perimeter of the object as well as a device for coordinating the in- dividual image recordings and the individual positions of the object to be scanned rela- tive to the recording means, a device for creating a matrix containing black and white picture elements from every image taken, thinning the thickness of the shaped line cor- responding to the illuminated profile of the object to the width of one picture point, eliminating the eventual breaks in the shaped line and computing the picture points forming the space coordinates of the shaped line according to the position of the object, the recording means and the illuminating light source, creating a polygonal mesh from the picture points and providing the polygonal mesh with a texture from the original im- age information.

Brief Description of the Drawings The innovation shall be detailed with the help of the drawing attached on which we have shown a way of implementation of the method as an example. In the drawing Figure 1 shows the working principle of the method according to the invention, Figure 2 shows a possible layout of the disk corresponding to the element holding the object to be scanned-the rotating table-of the device im- plementing the method, with one synchronizing hole, Figure 3 is a possible electrical connection of the angle position encoder, Figure 4 shows the shaped lines generated by the pixels of the image recorded, Figure 5 shows the polygonal mesh generated by the shaped lines of Fig. 4., Figure 6 shows the finished computer model with the texture from the original image information,

Figure 7 shows a possible layout of the program window used for selecting the detail containing the illuminated profile of the object from the re- corded picture, and Figure 8 shows a possible block diagram of the method suggested.

Detailed Description of the Preferred Embodiment Generally and in advance we may state that in the case shown an object 1 to be scanned is placed onto a rotating table 2 and is illuminated with a narrow, vertical line of light 4 directed toward the selected axis of rotation 3 of the object 1. The line of light 4 is gen- erated by means of a light source 5 and an optical slit 6. Rotating the table 2 the image of the profile of the object 1 is recorded for every few degrees by a camera used as a re- cording means 7 and with the help of commercially available well known frame grabber card not shown on the Figure inside a computer 8. The computer 8 has also only been shown symbolically. From the motifs thus obtained, with the exact knowledge of the position of the object 1, the recording means 7 and the light source 5, the three dimen- sional coordinates of the points on the surface bounding the object 1 are calculated and from the data thus obtained a three dimensional model is made.

The display of the three dimensional model on the computer 8 is handled by projecting the two dimensional projection of the three dimensional shape by some image sensing means. The most well known such means is a video camera containing a CCD sensor which generates a video signal containing the image information. The coupling of the analog video signal into the computer 8 is made possible by a so called video digitizing card (frame grabber). The digitizing process is controlled from the computer 8. The suc- cessive image frames, i. e. the digital moving picture, are recorded on the data medium of the computer 8, mostly on the hard disk for later processing. In the course of the pic- ture processing the projection errors, distortions are corrected by various picture correc- tion methods and the noise effects are filtered.

The basis of the computerized body modeling is the mathematical model describing the construction of the objects. If the aim is the visual display of an object 1 it is sufficient to describe its visible outer surface. One of the most well known methods of surface modeling is the use of polygonal meshes. The polygonal mesh is a collection consisting of edges, vertexes and polygons, in which the polygons are linked in such a way that at

most two polygons share one edge, one edge connects two vertexes and a polygon is a closed series of edges, one vertex contains at least two edges, and every edge is part of at least one polygon.

The signal output of the scanning devices, more commonly known as scanners, used nowadays is a cloud of points constituting the coordinates of vertex points. The polygo- nal mesh is fitted to these vertex points with a known image display program. It is obvi- ous that the more point is given on the surface of an object 1, the more the model will resemble reality. The number of points for an irregular shaped object 1 may be several hundred thousand, and to construct such a model by hand is almost impossible.

The three dimensional effect on the monitor is achieved by successively displaying the two dimensional projections of the object 1.

For recording the required number of profiles of the object 1 we have to change the relative position of object 1 and recording means 7, and it is advantageous to automate this operation. From the point of view of the result it is irrelevant if the object 1 is ro- tated in relation to a fixed recording means 7 or the opposite. However, the position of the object 1 has to be known so it is advisable to connect an encoder 9 to it or to the ro- tary table 2.

On Fig. 2 a disk 10 of the encoder 9 is shown, while Fig. 3 shows a possible electrical connection of the electronics of the encoder 9.

The disk 10 is a measuring element of very high precision produced by photographic means on a glass substrate on the perimeter of which a scaling by degrees may be found. This scaling serves the purpose of determining the rotation angle of the table 2.

On the disk 10 there is a so called synchronizing hole 11, which for every revolution passes before the phototransistor sensing the synchronizing position-see Fig. 3. This signal enables the output of encoder 9. The other synchronizing signal disables the out- put of encoder 9, thus after a complete turn no more signals arrive at the frame grabber card.

If disk 10 is rotated with even angular velocity a nearly sinusoidal voltage change can be detected at the outputs of the phototransistors. The sinusoidal signals are converted by a 74LS14 type ICI comparator into digital signals. At the start of sampling the 74LS74 type IC2 D-latch is set to ground state by a RESET signal, thus its Q outputs

are set to 0 state. If Q I=0, then-Q 1-=R1=R2=1 and the outputs of the 74LS93 type four bit IC3 counter are QA=QB=QC=QD=0. On appearance of the synchronizing signal the -Q2-=1 connected to the DI input is written into the IC2 D-latch: Ql=l, and -Ql--0=Rl=R2 enable IC3 counter. The IC3 counter divides the rotation sensing sig- nals connected to its input and its output is, depending on the processing program, con- nected for example to the serial or parallel line of the computer 8, or as in the present case, is connected with the help of a reed relay contact in parallel with the button of the mouse used as pointing device, and imitates the operation of the mouse. On the appear- ance of a new synchronizing signal the-Q2-=0 on the D 1 input is written into the IC2 D-latch and Q1=1 is again disabling counter IC3.

To record a human face as object 1 we are usually sampling at every two degrees with a 640X480 pixel resolution, e. g. in AVI format. The program reads the recorded frames from the AVI moving picture file. It is an important task is to distinguish the illuminat- ing line from the background. Therefore the analysis is performed for every picture in the AVI file and the spatial coordinates of the points are calculated after improving the quality of the picture. We obtain as a result a file in VRML format that my be viewed and rotated with some known browser program (for example GLView, CosmoPlayer, Netscape Live three dimensional plug-in, WorldView) or can be further refined and ed- ited with the help of a three dimensional editor.

If the recording means 7 is not capable of proper focusing, or the light falls in nearly parallel with the surface of object 1 then the line of light looks blurred. Therefore the picture is made more precise by a line thinning algorithm (averaging) that improves the quality of spatial models. Averaging eliminates in some measure the glints also, pro- vided that the light spot from the glint is fainter then the light strip itself.

In the course of our experiments we have digitized many objects and found that the light strip often breaks (is discontinuous). In some cases it is outside the viewing angle of the camera because some protruding part of object 1 blanks or shadows it or a darker sur- face part absorbs the light. For eliminating this problem, we have to find the eventual breaks and, if possible we have to correct them. This is easiest solved by an incremental algorithm. It is more complicated but more precise if the original profile is approxi- mated by curves. Both solutions consist of operations well known to experts. For the calculation of the spatial x, y, z coordinates it is necessary to know the position of the

axis of rotation, as well as the angle spanned by the light source and the camera. The last step is to fit a polygonal mesh to the vertexes.

The steps of a method which is shown in more detail below and in Fig. 8 are the fol- lowing: -Reading in of the files containing the frame records.

-Black and white conversion -Connection of the breaks by an incremental algorithm -Calculation of the rectangular coordinates -Generation of the polygonal mesh -Writing of the three dimensional data into file -Display of the file as a computer model.

1. Reading the AVI file In step 81 we start the method, in step 82 the process parameters are read in and in step 83 the heading of the video file is read. The input of the processing operation is a stan- dard non compressed, Y8 color format Microsoft (r) AVI video file without any sound.

As a result of the analysis we store the data of the header and the position (offset) of the frames, in order that it should not be necessary to look for them in the file during the processing phase and in step 84 the next frame may be read immediately instead. We skip the unnecessary information, thus a larger file containing several 10 megabytes can also be handled swiftly.

A possible routine solving the task: Input: Path of the AVI file Output: mP = *number of frames* mX = *width of frames* mY = *height of frames* v-offset (mP): a numeric vector containing the position of frames furtheron: Input:

k = *serial number of the frame to be read in* voffset mX, mY Output: vframe (mY) vector storing the individual lines of a frame 2. Black and white conversion In step 85 a matrix containing black and white points are generated, thus it becomes evident with every pixel whether it belongs to the background or to the light strip. In the Y8 color format the brightness code of every pixel is stored in 8 bits (1 byte). The higher a brightness code of a pixel is, the more closer its color is to white (the bright- ness code of black is 0 and that of white is 255). Therefore a frame can be stored in so many bytes as many picture points it consists of. The color values of the pixels are stored one after the other, from left to right and from top to bottom. If the value of a color code is larger than a preset limit, i. e. it is brighter than the limit then we take it as white and in the opposite case we consider it as black.

On the picture thus generated the original line thickness may be seen. In order to in- crease the accuracy the light strip has to be thinned to a thickness of one pixel, which is realized in step 86 in a way that in every line we calculate the average of the white pix- els.

The routine for solving the task: Input: vframe vector mX, mY limit xl, axis (= x2) Output: vaverage (mY) vector containing the individual profiles The operation is demonstrated by the pseudo code algorithm below : for y=l to mY for x=xl to axis

if *the (x, y) pixel is brighter than the limit* sum = sum + x divider = divider + I end if next x vaverage (y) = sum/divider next y 3. Connection of the breaks with incremental algorithm In step 87 we look for breaks in the light strip. In the empty picture lines (where no white pixels have been recorded) the average result is obviously 0. The light strip is continued in the picture line, where the average is larger than zero. If we succeeded in finding the start and the end of the break then we connect the two points with a straight line. In case of short breaks this approximation does not cause a large error. There exist algorithms generating approximating curves requiring more computation, which more precisely approximate the original curve. In the first and last lines of the picture the al- gorithm cannot perform the connection due to the lack of a starting or end point.

The principle of connection may be most simply put in the following way: Let the coor- dinates of the last still visible white point be Xu, Yu and that of the already visible white point Xt, Yt. There is a break between them. The slope of the connecting line is m= (Xt-Xu)/ (Yt-Yu). For every picture line, moving vertically down from Yu to Yt and increasing the value of X by m, the new average is determined one by one.

The routine for solving the task: Input: vaverage (mY) mY Output : v average () vector containing the profiles without breaks The operation is demonstrated by the pseudo code algorithm below: ux =-1 for y = 1 to mY

x = vaverage (y) ifx=0 if ux >-1 do until v average (y) > 0 y = y + loop dx = (v_ average (y)-uX)/ (y-uY) fory2=uY+ 1 toy-l v average (y2) = v average (y2-1) + dx next y2 end if y=y-1 else uY=y uX=x end if next y In step 88 we examine if every pixel has been processed or not, if not then the described operational steps are repeated from step 84, i. e. the reading of the next frame. After this, in step 89 the rectangular coordinates are calculated.

4. Calculation of the rectangular coordinates Input: v average () vectors Output: Set of points describing the surface of the three dimensional model Operation: The input of the algorithm are mP pieces of vectors, each one of them de- scribing a two dimensional profile. The data set is most easily stored in a cylindrical co- ordinate system. In the cylindrical coordinate system the coordinates are characterized by the m height (index of vaverage () vectors), the radius r (elements of v_ average () vectors) and the ALFA rotation angle (number of v_ average () vector: from 1 to mP).

From this three data the rectangular coordinates Xd, Yd, and Zd my be calculated with the help of the following formula: Xd = r * SIN (ALFA) Yd = r * COS (ALFA) Zd=y The set of pints thus obtained constitute a spatial cloud of points. As the points (ver- texes) do not have a surface, for the sake of visibility a surface has to be fitted to the cloud (see Fig. 4).

5. The generation of the polygonal mesh In 90 step the three dimensional surface is covered with small rectangles. A rectangle is determined by its four vertexes and every rectangle has a common edge with four adja- cent rectangles. This method ensures full coverage by creating a completely closed three dimensional surface, see Figs 5 and 6. Following this the three dimensional model is written to disk in step 91 and the method is terminated in step 92.

6. Wiring the three dimensional data into file Input: A set of points describing the surface of the three dimensional model Output: A file containing the three dimensional model in the selected format, for example VRML, DXF, ASCII.

We implement the suggested method with a program written in Visual Basic program language and its results may be also checked visually, see Fig. 7. During the program run it can be traced exactly in which phase the processing actually is.

After the realization of the method, i. e. after starting the program, the following most important input data have to be given : -the path of the video file storing the profiles -the path of the output file storing the data of the three dimensional model -the angle between the recording means 7 and the light source 5 -the placement of the axis of rotation 3

-the limit value for distinguishing the brightness levels -the angle between the profiles at sampling (optional) -only every nth profile of those recorded are processed -only every kth line of the recorded pictures should be processed -the number of the first and the last profile to be processed in order to produce a mask -the color of three dimensional model -other parameters for setting the quality, the speed and the file size.

Optionally there is a possibility for sampling from the video file before processing. This feature aids the user in setting the three axes of rotation and the coordinates of the frame cutting. With the help of the routine the original picture frame is drawn (see Fig. 7), the two bit converted image, the calculated line thinning and no break data The realizable resolution can easily be improved by improving the optical circle (disk) or the electronics, by using a high resolution camera and by building in various algo- rithms. The resolution reached as an example is the following: object A: 10 cm high cylinder of 5 cm radius object B: human face resolution: object A object B vertical: 0.2 mm 0.4 mm horizontal: 0.9 mm 1.7 mm A recording can be made within half a minute, processing lasts for about one-one and a half minutes depending on the complexity of the model and the resolution.

As the object 1 is illuminated by white light, the exposition may be made in color and the image of the surface can be recorded in color. The texture thus obtained can be pro- jected with an editor program onto the polygonal mesh, thus not only the original form but also the color and figuring can be displayed.

In order to create easily editable bodies (shapes) it is worth while to use some kind of CAD program, because here a cube may given by its eight vertexes, what a scanner would otherwise build up of several ten thousand of points. Of course the two tech- niques may be used in a mixed way to build up our world.

The current version does not consider the perspective distortions. If the view angle of the camera is set properly, for example it is set the furthest away possible and we zoom on it then the distortion effect can be decreased.

The vertical resolution may be increased by rotating the camera by 90 degrees. The CCD camera namely has more horizontal pixels than vertical. By using conventional hand cameras the theoretical limit arising out of the TV standard is 768 pixels. Accord- ing to this a 0,13 mm resolution could be achieved in case of a 10 cm high object 1.

The third dimension provides a significant added value compared to the two dimen- sional display. The suggested method and device can be used advantageously and could become an inexpensive tool for an artist working in three dimension and for people ed- iting WEB pages. By using this device new horizons open up for shape designers in the practical application of spatial modeling and new educational means may be con- structed. Biology teachers may show the three dimensional image of organs of living creatures, and in a class of fine arts a virtual gallery of statues may be created. The product catalogs of virtual department stores and the advertisements my be made more exciting by using three dimensional pictures. In the case of making three dimensional PC games this data input device makes it possible to digitize organic shapes by scan- ning human faces or even plasticine figures, and further more it should become possible for everyone to"customize"the characters of computer games at home.