a2) United States Patent
`US 6,611,617 B1
`(10) Patent No.:
`
`Crampton Aug. 26, 2003 (45) Date of Patent:
`
`
`US006611617B1
`
`(54) SCANNING APPARATUS AND METHOD
`
`(76)
`
`Inventor: Stephen James Crampton, 9
`Broadfields, Goffs Oak, Waltham Cross,
`Herts EN7 5JU (GB)
`
`*)
`
`otice:
`Noti
`
`this
`disclaimer, the term of
`ubject to any
`f thi
`y disclai
`h
`Subj
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.:
`
`09/000,215
`
`(22) PCT Filed:
`
`Jul. 25, 1996
`
`(86) PCT No.:
`
`PCT/GB96/01868
`
`§ 371 (<)Q),
`(2), (4) Date: May 26, 1998
`
`(87) PCT Pub. No.: WO97/05449
`
`PCT Pub. Date: Feb. 13, 1997
`
`(30)
`
`Foreign Application Priority Data
`
`FOREIGN PATENT DOCUMENTS
`
`DE
`DE
`EP
`FR
`GB
`GB
`GB
`WoO
`WO
`
`3938714 Al
`PCT/AT91/00115
`0159187 Al
`PCT/FR90/00090
`2264601 A
`2264602 A
`PCT/GB95/01994
`PCT/US91/07511
`WO 96/10205
`
`$/1991
`5/1992
`10/1985
`9/1990
`9/1993
`9/1993
`2/1996
`4/1992
`4/1996
`
`OTHER PUBLICATIONS
`
`Sakaguchiet al., “Acquisition of Entire Surface Data Based
`on Fusion of Range Data,” IEICE Transactions, vol. E 74,
`No. 10 (1991).
`Fisher et al., “A Hand-held Optical Surface Scanner for
`Environmental Modeling and Virtual Reality,” Department
`of Artificial Intelligence, University of Edinburgh.
`Besl, PJ. and N.D. McKay, “A Method for Registration of
`3-D Shapes”, JEEF Transactions on Pattern Analysis and
`Machine Intelligence, vol. 4, No. 2, pp. 239-256, Feb. 1992.
`
`Jul. 26,1995
`
`(GB) ooeeeeec cece cece cee ceeneeeeenes 9515311
`
`* cited by examiner
`
`Int. C1? vee G06K 9/00; GO1D 11/14
`(51)
`(52) US. Ch. eens 382/154; 382/153; 356/614
`(58) Field of Search 0.0...ee 382/154, 153,
`382/100, 118, 232, 260, 199, 203, 266,
`312; 345/421, 425, 430, 422, 514, 516,
`427, 627, 589; 356/614, 3.14, 141.4
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`......... 702/153
`3/1987 Krouglicof et al.
`4,649,504 A *
`4/1989 Merz ou. eee eee 345/589
`4,825,391 A *
`1/1991 Inoue et al.
`............ 250/559.22
`4,982,102 A
`2/1991 Inoue etal. wo... 356/607
`4,993,835 A
`2/1992 Donaldson ..
`... 356/376
`5,090,811 A
`12/1992 Field, Jr.
`....
`.. 382/103
`5,168,528 A
`3/1993 Quick etal. .
`.. 345/427
`5,191,642 A *
`3/1993 Schulz ...........
`... 356/614
`5,198,877 A *
`
`.
`. 345/564
`5,251,296 A * 10/1993 Rhoden et al.
`TOM993 Boyles wvvccessenervossenvossee 348/95
`5,255,096 A
`5,264,578 A
`11/1993 Powell etal. .......... 219/130.01
`5,268,996 A * 12/1993 Steiner et al... 257/586
`
`.. 345/627
`5,357,599 A * 10/1994 Luken ............
`5,886,703 A *
`3/1999 Mauldin ....... 345/423
`
`
`
`Primary Examiner—Andrew W. Johns
`Assistant Examiner—Duy M. Dang
`(74) Attorney, Agent, or Firm—Christensen O’Connor
`Johnson Kindness PLLC
`
`(57)
`
`ABSTRACT
`
`A scanning apparatus and method for generating computer
`models of three-dimensional objects comprising, means for
`scanning the object to capture data from a plurality of points
`on the surface of the object so that the scanning may capture
`data from two or more points simultaneously, sensing the
`position of the scanning means, generating intermediate data
`structures from the data, combining intermediate data struc-
`tures to provide the model; display, and manually operating
`the scanning apparatus. The signal generated is structured
`light in the form of a stripe or an area from illumination
`sources such as a laser diode or bulbs which enable data for
`the position and color of the surface to be determined. The
`object may be on a turnable and may be viewedin real time
`as rendered polygons on a monitor as the object is scanned.
`
`11 Claims, 23 Drawing Sheets
`
`
`
`Shenzhen Tuozhu 1009
`
`1
`
`Shenzhen Tuozhu 1009
`
`

`

`U.S. Patent
`
`Aug.26, 2003
`
`Sheet 1 of 23
`
`US 6,611,617 B1
`
`Figure |
`
`
`
`Figure 2
`
`261
`
`3
`
`7
`
`13
`
`S1
`
`260
`
`261
`
`262
`
`2
`
`

`

`U.S. Patent
`
`Aug.26, 2003
`
`Sheet 2 of 23
`
`US 6,611,617 B1
`
`Figure 3(a)
`
`Figure 3(b)
`
`Figure 3(c)
`
`|
`
`.
`
`28'
`
`31
`
`Figure 3(d)
`I
`
`Al
`
`A2
`
`3
`
`

`

`U.S. Patent
`
`Aug.26, 2003
`
`Sheet 3 of 23
`
`US 6,611,617 B1
`
`Figure 4
`
`
`
`4
`
`

`

`U.S. Patent
`
`Aug.26, 2003
`
`Sheet 4 of 23
`
`US 6,611,617 B1
`
`Figure 5(d)
`
`Figure 5(b)
`
`NON-COPLANARITY
`164
`
`163a
`
`165
`
`(CxCy)
`
`Figure 5(c)
`COPLANARITY
`
`165
`
`a
`
`5
`
`

`

`U.S. Patent
`
`Aug.26, 2003
`
`Sheet 5 of 23
`
`US 6,611,617 B1
`
`Figure 6
`
`60
`
`61
`
`35
`
`29
`
`63
`
`64
`
`62
`
`65
`
`22
`
`6
`
`

`

`U.S. Patent
`
`Aug.26, 2003
`
`Sheet 6 of 23
`
`US 6,611,617 B1
`
`Figure 7
`
`HIGH
`
`LOW
`ON
`
`OFF
`OPEN
`
`SHUT.
`OPEN
`
`SHUT
`
`61
`
`SYN
`
`-
`
`C
`
`M
`
`'
`
`:
`
`0
`
`20 MSECS
`
`7
`
`

`

`U.S. Patent
`
`Aug. 26, 2003
`
`Sheet 7 of 23
`
`US 6,611,617 BI
`
`Figure 8
`
`wwweweweeewewowewe
`
`waleeo
`
`ae
`eee ew wee me ee ee ee
`
`31
`
`50
`
`52
`
`ee ee we we ee em
`
`50
`
`8
`
`
`
`
`

`

`U.S. Patent
`
`Aug.26, 2003
`
`Sheet 8 of 23
`
`US 6,611,617 B1
`
`Figure 9
`212 216
`
`Figure 10
`1
`
`210
`
`9
`
`

`

`U.S. Patent
`
`Aug.26, 2003
`
`Sheet 9 of 23
`
`US 6,611,617 B1
`
`Figure 11
`
`
`
`221
`
`222
`
`10
`
`

`

`U.S. Patent
`
`Aug.26, 2003
`
`Sheet 10 of 23
`
`US 6,611,617 B1
`
`Figure 12
`
`231
`
`230
`
`233
`
`932
`
`11
`
`

`

`U.S. Patent
`
`Aug. 26, 2003
`
`Sheet 11 of 23
`
`US 6,611,617 BI
`
`Figure 13
`
`Figure 14(a)
`
`Figure 14(b)
`
`12
`
`12
`
`
`
`
`

`

`U.S. Patent
`
`Aug. 26, 2003
`
`Sheet 12 of 23
`
`US 6,611,617 BI
`
`Figure 15
`
`Figure 16
`
`NEGATIVEPOINT
`
`113. 114
`
`115
`
`Mi
`
`1l5a
`
`13a
`
`13
`
`13
`
`
`
`

`

`U.S. Patent
`
`Aug.26, 2003
`
`Sheet 13 of 23
`
`US 6,611,617 B1
`
`Figure 17
`
`BYTES
`
`10
`
`N - NORMAL
`
`I - INTENSITY
`
`Z - DEPTH VALUE
`
`14
`
`

`

`U.S. Patent
`
`Aug.26, 2003
`
`Sheet 14 of 23
`
`US 6,611,617 B1
`
`Figure 18
`
`Z
`
`(\
`
`oeSEG
`
`9
`
`\
`
`15
`
`

`

`U.S. Patent
`
`Aug.26, 2003
`
`Sheet 15 of 23
`
`US 6,611,617 B1
`
`Figure 19
`
`Z
`
`Y
`
`12
`
`x
`
`121
`
`123
`
`120
`
`16
`
`16
`
`

`

`U.S. Patent
`
`Aug.26, 2003
`
`Sheet 16 of 23
`
`US 6,611,617 B1
`
`Figure 20(a)
`
`282
`Consotopga
`
`bC
`
`c d®
`
`°e
`
`es
`e-
`
`e&%e@
`
`Dag
`
`281
`
`Figure 20(b)
`
`Figure 20(c)
`302 —~ °-2
`
`Figure 20(e)
`307 Ln @a
`e-b
`
`Figure 20(f)
`308
`307a
`“* 307b
`
`Figure 20(g)
`
`303!
`
`17
`
`Figure 20(d)
`302a
`302b
`
`303.
`
`gonho
`
`-
`
`302c
`302d
`304g
`302h
`302i
`302)
`302)
`305
`302k
`
`3021
`
`:
`
`vs
`
`309
`
`17
`
`

`

`U.S. Patent
`
`Aug.26, 2003
`
`Sheet 17 of 23
`
`US 6,611,617 B1
`
`Figure 21
`
`272
`
`Figure 22
`
`321<ay
`
`320a
`
`323b
`
`323a
`
`320b
`
`18
`
`

`

`U.S. Patent
`
`Aug. 26, 2003
`
`Sheet 18 of 23
`
`US 6,611,617 BI
`
`Figure 23
`
`wewewwwrwewewewem==
`weeeewewwwe——eo
`
`time
`
`Figure 24
`
`240
`
`24
`
`25
`
`241
`
`242
`
`19
`
`19
`
`

`

`U.S. Patent
`
`Aug.26, 2003
`
`Sheet 19 of 23
`
`US 6,611,617 B1
`
`Figure 25
`
`4
`
`131
`
`xX
`
`130
`
`132
`
`133
`
`20
`
`20
`
`

`

`U.S. Patent
`
`Aug.26, 2003
`
`Sheet 20 of 23
`
`US 6,611,617 B1
`
`Figure 26(a)
`
`Figure 26(b)
`
`3
`
`333 “NL
`
`LY“™ 333
`
`331 7
`
`3
`
`21
`
`21
`
`

`

`U.S. Patent
`
`Aug.26, 2003
`
`Sheet 21 of 23
`
`US 6,611,617 B1
`
`Figure 27
`
`
`
`i44
`
`142
`
`22
`
`22
`
`

`

`U.S. Patent
`
`Aug. 26, 2003
`
`Sheet 22 of 23
`
`US 6,611,617 BI
`
`Figure 28(a)
`
`Figure 28(b)
`
`Figure 28(c)
`
`23
`
`23
`
`
`
`

`

`U.S. Patent
`
`Aug.26, 2003
`
`Sheet 23 of 23
`
`US 6,611,617 B1
`
`Figure 29(a)
`
`360
`
`Figure 29(b)
`
`362
`
`365
`
`360
`
`24
`
`24
`
`

`

`US 6,611,617 Bl
`
`1
`SCANNING APPARATUS AND METHOD
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`This is a United States national application corresponding
`to copending international application PCT/GB96/01868,
`filed July 25, 1996, which designates the United States, the
`benefit of the filing date of which is hereby claimed under 35
`U.S.C. §371, which in turn claims the benefit of British
`Application No. 9515311.0, filed July 26, 1995, the benefit
`of thefiling date of which is hereby claimed under 35 U.S.C.
`119.
`
`FIELD OF THE INVENTION
`
`This invention relates to an apparatus and method for
`scanning a three dimensional object.
`
`BACKGROUND OF THE INVENTION
`
`Real-world, three-dimensional objects whether with natu-
`ral form (e.g. geographical, plant, human or animal-like) or
`man-imagined form (e.g. sculptures, reliefs, cars, boats,
`planes or consumer products) are difficult to scan. This is
`because of features such as rapidly varying surface normals
`and surfaces for which a line of sight is difficult because it
`is partially obscured by other parts of the object.
`Scanning machines—also known as digitizing
`machines—for scanning objects or parts of objects can be
`categorised into two types: computer numerically controlled
`(CNC) and manually operated. Ascanning machine includes
`a unit that contains a sensing means commonlyreferred to
`as a probe.
`Objects or parts of objects can be scanned on CNC
`scanning machines with a number of computer numerically
`controlled (CNC) linear and rotating motor-driven axes.
`Different CNC machines can move/reorient the probe or the
`object—or both—by a combination of translation and rota-
`tion about these axes. Different machine designs are suited
`to different classes of objects. Probes can be temporarily or
`permanently attached to most types of CNC machine tool or
`CNCcoordinate measuring machine which can then be used
`for scanning. As examples, small and simple 3-axis CNC
`milling machines may be used or large, complex 5-axis
`machines may be used. The points captured by CNC
`machines are usually on a regular grid and the rate varies
`from around 1 point per second up to around 20,000 points
`per second depending on the technology being used and the
`object being scanned. The points from these scanning
`machines are accurate to the order of 0.05 mm. CNC
`machines with probes scan by executing one or more
`programs that move the axes of the machine such that there
`is relative motion between the probe and the object.
`CNC machines are expensive, partly because of the
`incorporation of motors and the associated equipment for
`assuring rejection motion such as linear guides and drive
`screws. Few CNC machinesare flexible enough so that the
`probe can be oriented in six degrees of freedomso as to scan
`the complete surface of a complex object. Even when a CNC
`machine has six degrees of freedom, it is often not suffi-
`ciently flexible so as to position the probe to scan the
`complete surface of the object without colliding with the
`object. When the object is a person or expensive, the risk of
`using a CNC machine may be unacceptable and there would
`be a necessity to make a machine to meet both the safety and
`scanning requirements of the application. The programming
`of a CNC machine so that
`the surface of the object is
`
`10
`
`5
`
`20
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`completely scanned without a collision of the probe or
`machine with the object is often highly complex. Usually the
`design of the machine and the degrees of freedom inherent
`in the design and limitations in the probe design such as the
`standoff distance during scanning between the probe and the
`object, meanthatit is impossible to come up with a scanning
`strategy that will scan the complete surface of the object. It
`is commonthat the object has to be manually picked up and
`replaced in a different position and or orientation one or
`more times during scanning. Each time that this occurs, the
`object has to be registered to a uniform coordinate system
`such that the data from the different scans can be accurately
`combined.
`
`Manually operated scanning machines can be categorised
`into three types: horizontal arm machines, multiply jointed
`arms and devices based on remote position sensing means.
`Manoually driven, horizontal arm measuring machines
`usually have three orthogonal axes and are usually based on
`a travelling column design. These machinesare usually quite
`large with the bed being at floor level so large items such as
`cars can easily be moved onto and off them. Often motors
`can be engaged on one or more axes to aid the manual
`movementof the machine. The probe is normally mounted
`at a fixed orientation on the end of the horizontal arm. This
`orientation may be changed and various devices may be
`attached betweenthe end of the horizontal arm and the probe
`to aid the changing of the orientation, most of these devices
`having two axes. Horizontal arm machines have the disad-
`vantage of not being able to easily orient the probe in six
`degrees of freedom. The limited flexibility in the design of
`a horizontal arm machine makes mostofthe far side of the
`object unscannable.
`Multiply jointed arms commonly comprise multiple link-
`ages and are available for scanning complex objects. A
`multiply jointed arm typically has 6 joint axes but may have
`more or less joint axes. At the end of the multiply jointed
`arm there is usually a tip reference point—such as a sphere
`whose centre is the reference point or a cone ending in a
`point. Scanningis carried out by bringing the point or sphere
`into contact with the object being scanned. The computer
`monitoring the multiply joined arm then measures the angles
`at all the joints of the multiply jointed arm and calculates the
`position of that reference point in space. ‘Ihe direction of the
`last
`link in the multiply jointed arm is also calculated.
`Positions can typically be output continuously at a rate of
`around 100 points per second, but the rate can be much more
`or much less. The accuracy is of the order of 0.1 to 0.5 mm.
`Thepoints from the arm are usually sparse and unorganised.
`The sparseness and lack of organisation of the points makes
`it difficult to provide enough information for constructing a
`computer modelof the object that is of acceptable quality. A
`multiply jointed arm with multiple linkages has a limited
`working volume. In general, if a larger working volumeis
`required, the arms become very expensive, less accurate and
`tiring, difficult to operate. The limited working volume can
`be increased by leapfrogging in which the whole arm/baseis
`moved to access another volume, but this requires a time
`consuming, systemof registering at least 3 points each time
`the arm is moved and recombining the data sets from each
`arm position. Manufacturer’s of multiplying jointed arms
`provided pre-calibrated arms and test methodsthat the user
`may employ to make sure that the arm is still calibrated to
`an acceptable accuracy. Such test methods use for example
`the standard tip reference point at the end of the arm and a
`reference sphere or a ball-bar which is a rod with two
`cylindrical cups that has a precise knowndistance between
`a homeball and a end of arm ball. As the arm tip at the end
`
`25
`
`25
`
`

`

`US 6,611,617 Bl
`
`3
`of the ball bar is moved on the surface of spherical domain
`the arm records positions which are later compared to a
`perfect sphere and error estimates for the arm are output.
`Remote position sensing devices include hand-held
`devices that transmit or receive position information in a
`calibrated reference volume using different physical meth-
`ods including electromagnetic pulses and sound waves. A
`hand-held device may be connected to the rest of the system
`by means of a cable. These devices are prone to generating
`scanned points with very large errors and some devices
`cannot work when the object being scanned has metallic
`components. They are less accurate than multiply jointed
`arms with accuracies of the order of 0.5 um upwards.
`There are three broad categories of scanning probe that
`could be mounted on the end of a multiply jointed scanning
`machine: point, stripe and area probes. Point probes measure
`a single point at a time and technologies include mechanical
`contact methodsand optical distance measurement methods.
`Stripe probes measure a number of points in a line either
`simultaneously or rapidly in a scanned sequence; the most
`commonstripe technology islaser stripe triangulation. Area
`probes measure a two-dimensional array of points on a
`surface either simultaneously or in a scanned sequence; the
`most commontechnologics are interference fringe and mul-
`tiple stripe projection. Some area methodsrequire the device
`to be heldstill for a few seconds during data capture. Stripe
`and area methods have an in-built speed advantage over
`point methodsas there are less motion of the proberelative
`to the object. There are differences between the methods in
`terms of accuracy and cost but these do not generalise with
`category, for example a particular area technology may be
`cheaper and more accurate than another point technology.
`Meansof capturing independent reference/feature points
`by contact are well known and efficient. Structured light
`using stripe or area methods is not good at capturing
`independent feature points because there is no way for the
`operator to align a known point on the object with a point on
`the stripe or in the area.
`Geometrical errors in the scanning process stem from
`many sources. CCD cameras can typically capture video at
`25 frames per second. One major disadvantage in normal use
`is that from any given demand for a frame there is a
`variability of 40 msecs until the start of capture of that
`frame. If the probe is being moved at for example 100
`mm/sec, this can lead to a geometrical error of 4 mm in the
`probe’s data. The duration of frame capture depends upon
`the shutter speed e.g. “oo sec is 10 msecs. One major
`disadvantage in normal use is that if the probe is being
`moved with a slow shutter speed, an additional geometrical
`error is created. An arm is typically connected to a computer
`by aserial cable with arms typically generating positions at
`125 posilions per second as they move;at this rate there is
`a variability of 8 msecs between when a position is needed
`at the computer and whenit arrives. This can also introduce
`a geometrical error when the probe is moving. The total
`variabilities of the CCD camera and the arm can cause large
`ageregate errors.
`There is a wide range of formats for 3D information in
`current use. These include the general categories: point
`formats, polygon formats and complex surface formats.
`Point formats include: independent points, lines of points
`where a plane intersects with a surface, 2.5D areas of points
`which are commonly known as range images which are
`single valued in Z and 3D point arrays which are often
`generated by medical scanners. The point formats have
`many standard representations including the Range Image
`
`5
`
`20
`
`40
`
`45
`
`50
`
`55
`
`60
`
`4
`resulting from the European ESPRIT
`Standard (RIS)
`Research & Development Project 6911, IGES and DXF
`published by AutoDesk Inc in the USA.
`Polygon formats include polygonsof different geometri-
`cal form. Polygons maybe 3 or more sided and formats may
`include mixed numbers of sides or always the same number
`of sides. Special cases such as Delaunay triangulation can
`specify the positioning of vertices and the relative lengths of
`sides of polygons. Standard representations of polygon
`formats include STL published by 3D Systems Inc in the
`USA, IGES, OBJ published by Wavefront Inc in the USA
`and DXF.
`
`Complex surface formats include Bezier, NURBS, and
`COONSpatches. Standard representations of complex stan-
`dards formats include IGES, VDA-FS, SET, STEP and DXF.
`The objective of scanning can be simply to gather a
`number of three-dimensional points on the surface of the
`object, or it may be to create a computer modelin a format
`that is fuseful for the application in which the model is to be
`used. It is generally true that a cloud of points alone is not
`much use in many applications and that more structure is
`needed to make a computer modelefficient to manipulate in
`typical applications such as visualisation, animation, mor-
`phing and surface or solid modeling.
`There are often benefits to be gained from reducing the
`size of the files associated with the model formats. Anyfile,
`whatever its format can be compressed using standard
`reversible utilities such as PKZIP/PKUNZIP from PKWare
`in the USA. With 3D point arrays, an octet format can be
`used to reduce the size of the arrays that represent a surface;
`an octet format splits a cubic volume into eight, smaller
`cubes and only further subdivides cubes by eight if they
`contain information; an octet format is reversible. Moving
`from unstructured point representation to polygon or com-
`plex surface formats often produces large compressions but
`relies on approximations so the process is nearly always
`irreversible and it is also difficult to automate so as to give
`good enoughresults. Chordal tolerancing is a commonly
`used method of reducing the quantity of discrete points in a
`2D or 3D polyline. As an intermediate data structure it has
`disadvantages in that: the intermediate data structure does
`not record the oricntation of cach stripe, it docs not record
`breaks in the data but assumes that all
`the points are
`connected by a surface and it does not record jumps in the
`data such as those caused by occlusions.
`Most scans today are carried out using a multiply jointed
`arm with a tip reference point. It is usual to firsf mark the
`object to be scanned with a permanent or temporary marking
`device such as an ink pen or scribe to create a polygonal
`network of splines. A single point is then scanned at each
`network intersection. On the computer, the points are linked
`together into a polygonal structure. The overall process
`(marking, scanning and linking) of creating a 3D polygonal
`modelis at a typical rate of 1 point (or vertex on the modcl)
`every 3 seconds. In some implementations, the network is
`not marked on, but appears on a computer display as each
`point is scanned; with this implementation, the network is
`built up interactively. This method is suitable for models
`with a relatively small number of vertices i.e. hundreds and
`thousands. The method is very slow, requires skill, patience
`and concentration, is expensive in human time particularly
`for large, detailed objects that can take 3 weeks to scan.
`An alternative method of scanning with a multiply jointed
`arm and contact tip reference point has often been tried in
`which independent points are rapidly captured without the
`aid of network. The points are then input into a surfacing
`
`26
`
`26
`
`

`

`US 6,611,617 Bl
`
`5
`software package which then constructs a polygonal net-
`work between the points. However, the ‘polygonisation’ of
`unorganised data points is usually very slow and speed
`decreases significantly as the number of points increases.
`‘The results are usually so poor as to be unacceptable. ‘here
`is usually a significant amount of hand editing of the data
`required.
`Where a CNC scanning machineis used, the intermediate
`data structures are usually range images. A number of
`unregistered range images may be registered, polygonised
`and integrated together. The raw data is a numberof range
`images of an object: typically from 5 to 20 in number, with
`each one either being a cylindrical or a linear range image.
`The process is not automatic and requires a combination of
`operator guidance and automated execution of algorithms.
`The operator first
`tries to align (ie. register) the range
`images to each other on the computer using a graphics
`display. This process is not accurate and is followed by an
`automatic least squaresfitting process that attempts to adjust
`the position and orientation of each range image such that
`they fit together as well as possible; this process is lengthy
`often taking hours on a powerful computer. Each range
`image is then independently polygonised into a network of
`2.5D triangular polygons. Finally, the networksof triangular
`polygons are integrated together. The output is a single, 3D
`polygon dataset. The process is expensive both in terms of
`capital equipmentcost and people time. It can take up to two
`years to becomeskilled enough to scan objects to produce
`good enough models. It can work and produce good results
`for detailed objects.
`For smooth objects, where the objective is to create
`complex surface formats, a coordinate measuring machine
`with a contact tip reference point is commonly used. It is
`usual to mark up the object with the desired surface patch
`boundaries by using a marking device such as a pen or a
`scribe. ‘These patch boundaries are then hand digitised with
`the contact point probe. The software package then gener-
`ates a CNC scanning program that automatically takes more
`points along the boundaries and inside the patches. The
`software then automatically generates a first attempt at the
`surface model. This method is used becauseit is quicker and
`easier for the operator to define patch boundaries that will
`lead to a surface model with the desired structure before
`scanning than to define the patch boundaries after scanning
`using a software package on a computer with a display
`showing the scanned points. It can take several days and
`often weeks to create patch boundaries which are usually
`splines and then create the patches and then trim the patches
`to form a surface model by using only the scanned points
`and a computer.
`Scanned data points have been displayed in real-time. The
`display of points has the disadvantages of easily becoming
`confusing to interpret and also that the observer does not
`know whenparts of the object’s surface have been missed
`during scanning.
`SUMMARY OF THE INVENTION
`
`According, to the present invention, there is provided a
`scanning apparatus for scanning an object
`to provide a
`computer model thereof, comprising means for scanning the
`object to capture data from a plurality of points on the
`surface of the object where the scanning meanscaptures data
`from two or more points simultaneously; means for gener-
`ating intermediate data structures therefrom; means for
`combining the intermediate data structures to provide the
`model; means for display and means for manually operating
`the scanning apparatus.
`
`10
`
`5
`
`20
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`The apparatus is mostefficient in the quest to reduce the
`time and cost of generating a computer model from a real
`world object by means of scanning with both time and cost
`reductions of an order of magnitude achieved over conven-
`tional
`techniques. The model
`is generated automatically
`from the intermediate data in a form that may be immedi-
`ately usable in a wide range of applications.
`The scanning means may usestructured light to more
`quickly scan the surface of the object. The scanning means
`may also be operable to sense the colour of the surface of the
`object, resulting in a model morelike the real world object.
`Preferably the scanning means therein comprises means
`for generating a signal for scanning the object, signal
`detection means for detecting the signal reflected from the
`object and means operable in response to the detected signal
`to provide the data for the intermediate data structure.
`The structured light is preferably projected as a plane of
`light such that a stripe is formed on a viewing plane that is
`situated normal to the projection axis of the signal generat-
`ing meansandsituated at the average stand-off distance from
`the signal generating means.
`Alternatively the structured light may be projected such
`that a pattern is formed on an area of a viewing plane that
`is situated normal
`to the projection axis of the signal
`generating means and situated at
`the average stand-off
`distance from the signal generating means.
`The signal generating means may be an illumination
`source such as a laser diode or one or more bulbs.
`
`During scanning, the operator may see the surface he has
`scanned appearing in real-time as rendered polygons on the
`display such that he may more easily scan the object. The
`operator may mount the object on a turntable and then he
`may scan from a seated position rather than walking around
`the object. The scanning means can be mounted on many
`different types of manual machines, giving enhanced flex-
`ibility for objects ranging in size from small to very large.
`The scanning means can be mounted on a multiply jointed
`arm for accurate scanning. The scanning mcans may be a
`self-contained unit that contains a remote position sensor
`and incorporates a display to give the most flexibility in
`scanning.
`According to the invention there is also provided a
`method for scanning an object to provide a computer model
`thereof, comprising the following steps:
`manually scanning the object with a signal by manual
`operation of a signal generating means:
`detecting the reflected signal
`generating intermediate data structures for the points;
`combining the intermediate data structures to provide the
`model; and
`displaying the data, wherein the data is captured from a
`plurality of points on the surface of the object simul-
`taneously.
`According to a further aspect of this method of the
`invention the colour datais also captured from the object and
`then mapped on to the model.
`Preferably the data is displayed simultaneously as a
`plurality of display polygons.
`The invention will now be described, by way of example
`only, with reference to the accompanying Figures, of which:
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a schematic representation of a scanning appa-
`ratus according to the invention;
`FIG. 2 is a schematic perspective drawing of a probe;
`
`27
`
`27
`
`

`

`US 6,611,617 Bl
`
`7
`FIG. 3a illustrates a first embodimentof the configuration
`of the optical elements housed in a probe;
`FIG. 30 illustrates a lamp configuration;
`FIG. 3c illustrates an alternative to the lamp configuration
`of FIG. 3b;
`FIG. 3d is a graphillustrating intensity as a function of
`distance along the line Al—A2 of FIG. 3a;
`FIG. 4 illustrates a second embodiment of the configura-
`tion of the optical elements housed in a probe;
`FIGS. 5a to 5d illustrate a method of calibrating the
`colour of the scanning apparatus of FIG. 1;
`FIG. 6 is a schematic block diagram illustrating the
`capture of colour and position data;
`FIG. 7 is a schematic representation illustrating how the
`detection of the colour and position data is synchronised;
`TIG. 8 is a schematic representation of the end of the
`multiply jointed arm of the apparatus of FIG. 1;
`FIG. 9 is a schematic illustration of the turntable and
`
`the
`
`the
`
`multiply jointed arm of the apparatus of FIG. 1;
`FIG. 10 illustrates the mounting of the probe on
`multiply jointed arm;
`FIG. 11 illustrates the alignment of the mount on the
`multiply jointed arm;
`FIG. 12 illustrates the alignment of the probe on
`multiply jointed arm;
`FIG. 13 illustrates a linear range image;
`FIGS. 14a, 145 illustrates cylindrical range images;
`FIG. 15 illustrates the range image placing method;
`FIG. 16 illustrates the surface normal extension method;
`FIG. 17 represents the structure of a single point in a range
`image;
`FIG. 18 illustrates the representation of an object by three
`range images;
`FIG. 19 illustrates the range image updating method;
`FIGS. 20a and 20b illustrate first and second stripes
`captured on a CCD array;
`FIGS. 20c, 20d, 20e and 20f illustrate the respective
`captured data points and strings of data points from the first
`and second stripes of FIGS. 20a and 20b;
`FIG. 20g illustrates polygons generated from these
`strings;
`FIG. 21 illustrates a probe mounted on a head and a
`head-up display;
`FIG. 22 illustrates colour image mapping;
`FIG. 23 illustrates the timing for position interpolation;
`FIG. 24 illustrates the triggering of the arm position
`measurement;
`FIG. 25 illustrates an object with markedlines thereon;
`FIG. 26a illustrates a probe mounted on a multiply jointed
`arm which is mounted on a horizontal arm machine;
`FIG. 265 illustrates two opposing horizontal arm
`machines;
`FIG. 27 illustrates a human foot being scanned;
`FIG. 28a illustrates stripe sections of a pipe network and
`panel;
`FIG. 28b illustrates partial polygon models of a pipe
`network and panel;
`FIG. 28c illustrates extrapolated polygon modelof a pipe
`network;
`FIG. 29a illustrates stripe scanning;
`FIG. 296 illustrates area scanning;
`
`8
`DETAILED DESCRIPTION OF EMBODIMENTS
`
`Referring now to FIG. 1, a scanning apparatus 100
`comprises a multiply jointed arm 1 with an arm control unit
`2 and a probe 3. The control unit 2, which includes a
`processing unit 10 is coupled to a computer or processing
`unit 4 and colour monitor 7. The probe 3 is also coupled to
`a probe control unit 5 that
`is likewise coupled to the
`computer 4, The intermediate data is displayed on the colour
`monitor 7 as rendered polygons 13. The probe 3 provides a
`stripe 8, which is projected onto an object 9 positioned on a
`turntable 14. The stripe 8 is in the form of a plane of light.
`Buttons 6 are also provided to control data capture. A colour
`frame grabber 11 in the computer 4 is mounted on a standard
`bus 12 and coupled to the probe 3.
`The computer 4, probe control unit 5, arm control unit 2,
`buttons 6, colour frame grabber 11 and monitor 7 are
`provided separately, for example, the computer 4 and moni-
`tor 7 may be a personal computer and VDU,although, for
`certain applications, it may be more convenient for one or all
`of them to be provided on the probe 3.
`The multiply jointed arm 1 and the probe 3 are coupled to
`the computer 4 by meansofthe control units 2, 5 discussed
`above. The computer 4 receives information from the scan-
`ning stripe 8, the position/orientation of the arm 1 in terms
`of X, Y, Z coordinates, with the coordinates I,J,K of the
`surface normal of the probe 3 and colour data if required.
`Referring now to FIG. 2, an embodiment of the probe 3
`for use with remote position sensor 261 is shown. The probe
`3 is lightweight and resilient so as to withstand being
`knocked without losing its calibration.
`Referring now to FIG. 29a, the structured light is preter-
`ably projected as a plane of light 364 such that a stri