5

m

m

DEVELOPMENT OF TECHNIQUES

REQUIRED FOR THE

APPLICATION OF A LASER TO

THREE DIMENSIONAL

VISUAL SENSING

A/_£ a3-/3 3 3

lira

Ill by

Arthur M. Ryan and Lester A. Gerhardt

Rensselaer Polytechnic Institute

Electrical, Computer, and Systems Engineering Department

Troy, New York 12180-3590

August 1991

INN

m

CIRSSE REPORT #101

=

\
ii!ii

_,__ _, _ii_il_•

!

_Bi|M|m

Bmm|

[]

iimii

mm|ilV
w

Contents

m

i

m

w

List of Figures 3

List of Tables 4

Introduct ion 5

1.1 Description of CIRSSE Testbed ................. 5

1.2 History and Development of Laser Research Conducted at

CIRSSE .............................. 6

3

4

Calibration of a Laser Scanner

2.1

2.2

2.3

2.4

2.5

9

The MathematicM Model of a Laser Scanner ......... 10

Calibration of the Intrinsic Parameters ............. 12

Calibration of the Extrinsic Parameters using an LSE Method 13

Direct Geometric Method for Calibrating a Laser Scanner . . 15

Appraisal of Calibration Method Performance ......... 21

Point Estimation with a Calibrated Laser and Camera 23

3.1 Point-Estimation Using Least Squared Error .......... 24

3.2 Point Estimation Using Midpoint of Common Normal .... 26

3.3 Appraisal of Point Estimation Methods ............ 29

Locating a Laser Spot in a Camera Image 31

4.1 Application of Region Growing algorithm to a Camera Image 33

4.2 Region Selection Based on Intensity and Size ......... 35

4.3 Region Selection Based on Laser/Camera Triangulation . . . 35

4.4 Region Selection Based on Movement ............. 37

4.5 Evaluation of Laser Region Identification Performance .... 38

4.5.1 Analysis of Test Battery 1 Results ........... 40

4.5.2 Analysis of Test Battery 2 Results ........... 42

w .

L_

\

\

\
m

u

m

4.5.3 Analysis of Test Battery 3 Results ........... 43

4.5.4 Analysis of Test Battery 4 Results ........... 44

4.5.5 Conclusions about Laser $'election Performance .... 46

Conclusions and Future Research 48

I

M

l

i

I

m

|

I

R

m

m

i

i

m

m

m

i

B

m

m

u

m
t_

L

n

n

r_

List of Figures

2.1 Internal Arrangement of a Laser Scanner ............ 10

2.2 Effect of Pincushion Distortion ................. 11

2.3 Determination of a Laser Scanner's Euler Angles ....... 16

2.4 Transformation Parameters from Frame F to Frame W . . . 17

2.5 Relationship Between the F!oor and F's zy Plane ....... 18

4.1 Region Growing Algorithm ................... 34

4.2 Algorithm for elimination of regions based on movement . . . 37

W

L

u

w

m

\

\

3
g

mm

m

M

List of Tables

2.1 Typical Ca_ibr_tipn=Parameter Values for Direct Geometric

Method 22

4.1 Parameters used for Test Batteries ............... 39

4.2 Results of Test Battery One ..... , . ............. 41

4.3 Results of Test Battery Two 42

4.4 Results of Test Battery Three .................. 43

4'5 Results of Test Battery Four .................. 45

m

I

m

l

[]

l

=--

R

m

m

I

I

m

m

R

I

i :

I

f
m

m

w Chapter 1

Introduction

w

z 2

= =

m

- 2

me..

u

.-_::

J

The ongoing vision research at the Center for Intelligent Robotic Systems for

Space Exploration (CIRSSE) is directed toward identifying and addressing

the relevant issues involved in applying visual sensing to space assembly

tasks. A considerable amount of effort has been devoted to passive sensing

techniques such as using multiple cameras to identify objects in a scene.

To compliment the capabilities of the passive visual system in the CIRSSE

robotics testbed, research is being conducted in active sensing techniques.

This report is a description oI" the research associated with the testbed's

laser scanner and its application as an active sensing device. The report is

comprised of five major topics. First is a brief description of the CIRSSE

visual system and a summary of the active sensing sensing research that has

been conducted up to this point. Second, some of the methods currently

used to calibrate CIRSSE's laser scanner are described as well as an appraisal

of the effectiveness of these methods. Third, is a discussion of how the

laser scanner can be employed in concert with a camera to provide a three

dimensional point estimation capability. Fourth, there is a description of

methods that can be used to detect the presence of the laser beam in a

cluttered camera image. Finally, there will be a summary of the current

state of this research and a description of research planned for the future.

1.1 Description of CIRSSE Testbed

The CIRSSE robotic testbed is designed to support research in robotic assembly tasks for space applications. The centerpiece of the testbed is a pair

of PUMA robots each of which is mounted on a movable cart. Both carts

m

w
M

-=_

D

are mounted on a track; thereby permitting the robots to operate over a

large work volume. The testbed is also equipped with a multi-camera vision

system which provides a three dimensional visual sensing capability. The vision system is equipped with five cameras (two mounted above the testbed,

two mounted onthe wrist of one PUMA robot and 9he camera mounted

on the second PUMA robot). The vision system is also equipped with a

laser scanner (also mounted above the testbed) manufactured by General

Scanning [1]. This laser scanner provides the capability to direct a laser

beam by deflecting it with a pair of mirrors that can be controlled by computer. The entire vision system is controlled by an image processing system

manufactured by Datacube.

The CIRSSE vision system provides the capability to support research

in both passive and active techniques. A passive technique is one that uses

avilable light sources (i.e. general illumination) while an active technique

employs the projection of some externally supplied prestructured light [2].

The laser scanner provides a unique active sensing capability that complements and enhances the passive sensing capa-b_ties of t:he CIRSSEVision

system. Such an enhancement is possible by virtue of the laser's ability to

inject a pre-defined signature into the workspace tha_ a camera can subsequently detect. A laser beam has specific direction, intensity, wavelength,

and predictable behavior when it reflects off of objects. Further, because

the laser is an active sensor, it can operate undercertain lighting and environmental conditions in which a strictly passive system would be unable to

function.

For the purpose s of system calibration and three dimensional point estimation, the CIRSSE testbed has a well defined world origin point. This

point is located at the center of the track utilized by the robot carts. The

exact location and orientation of this point is described in a CIRSSE technical memorandum [3]. This report will refer to the testbed's world point

as either the world origin or the world coordinate system.

1.2 History and Development of Laser Research

Conducted at CIRSSE

Research involving the laser scanner began shortly after the vision system

was installed in the CIRSSE testbed. Initially, the laser scanner was used

=

to generate discrete or continuous patterns such as grid lines or predefined

I

I

|

m

m

u

[]

L

R

!

i

[]

=_

m

i i

i T

F

M

l

B

l

6

m z

J

u

u

m

|
m

i

I

r

m

L

W

L

'e

m

m

shapes. This pattern generating capability is possible since the laser scanner

is equipped with a shutter that can block the laser beam when blanking is

required between points. At this early phase of the research, the laser could

be controlled only in terms of its scanning mirrors, Initially, there was no

ability to control the laser in terms of cartesian space.

The next phase of the research was directed towards using a camera as

a feedback mechanism to direct the laser at a specific pixel coordinate. The

laser was directed in the field of view of a camera and the camera was used

to identify the reflection of the laser beam offobjects in the workspace (this

reflection is colloquially referred to as the laser spot). Control of the laser

was still in terms of the angles of the scanning mirrors and these angles were

repeatedly adjusted by the computer until the laser spot was centered onto

the desired pixeI coordinates. The process of locating the laser spot in the

camera image was premised on the assumption that the laser spot was the

brightest object in the image. Hence, this laser and camera configuration

operated best under subdued lighting conditions. This work highlighted

several issues that served as the basis for the current laser research:

• The CII_SSE vision was capable of using the laser and cameras in a

well coordinated manner.

Using a camera to detect the laser spot can be a valuable sensing

capability since the laser could illuminate objects that the camera

might otherwise be unable to distinguish.

The current camera feedback method assumed that the laser spot is

the brightest object in the image. Methods must be developed that

circumvent this assumption to permit a laser and camera to operate

in a wider variety of environmental conditions.

If the laser could be calibrated to the same coordinate system as the

camera, it would then be possible to directly place the laser at a worm

point and use a calibrated camera to confirm the proper placement of

the laser. Further, because the laser would be calibrated, it would be

unnecessary to repeatedly direct the laser to settle on a desired point.

With these ideas in mind the laser research was directed toward accomplishing three major tasks. First, calibrate the laser to a level of accuracy

comparable to that of the passive multiple camera system. Second, adapt

r

i

mw
the point estimation techniques used by the multiple camera system for use

with a calibrated laser and camera. Third, create techniques thatpermit a

camerat0 detect a laser spot in a cluttered environment under normal lighting conditions. The result of these three goals would be an active sensing

capability that can complement the existing multiple camera system, and

provide avenues for future research in active three dimensional ranging and

structured light.

I

m

[]

i

W

I

z

m

B

z

I

m

I

i

R

l

!

i

i

m

8

m

U

g

m

i z

I +

I
= ;

w

m

Chapter 2

R

rw

I

W

w

Calibration of a Laser

Scanner

A laser is useful in 3-D visual sensing because it provides an active sensing capability. The laser emits a beam of light that a camera can detect

as it reflects off of objects within the camera's field of view. An active

sensing configuration, such as a laser and camera, can enhance the reliability and flexibility of a vision system since it can generate structured light

and "ground truth". In some applications, the laser does not have to be

calibrated[2], but calibration is necessary to fully utilize the capabilities of

the laser.

The phrase "calibrated laser" is misleading in that the laser itself is

not calibrated. It is usually incorporated in an assembly that can direct

the laser beam in some well-defined manner. When the laser is calibrated,

the entire assembly is actually calibrated. One useful laser assembly is a

laser scanner[I] which uses mirrors to deflect the laser beam in a controlled

manner.

Calibrating a laser scanner is similar to calibrating a camera in that both

devices have intrinsic and extrinsic parameters. For a laser scanner, intrinsic parameters include the distance between the scanner's mirrors and the

relationships between the mirror's rotation and the voltage applied to their

rotational mechanisms (galvanometers). A laser scanner's extrinsic parameters describe the pose of the laser scanner with respect to some coordinate

frame. To better understand the process of laser scanner calibration, it is

instructive to examine the internal arrangement of the device and identify

the mathematical relationships that describe its operation.
2.1 The Mathematical Model of a Laser Scanner

The internal arrangement of the laser scanner is depicted in Figure 2.1. The

device consists of a laser and two scanning mirrors. Each mirror is connected

to a galvanometer that rotates the mirror as a function of a control voltage

applied to it. The mirrors are configured such that their rotational axes are

mutually orthogonal. The rotational axis of the 0==mirror is parallel with

the z axis of the laser scanner, and the rotational axis of the _ mirror is

parallel to the z a_s of the laser scanner.

x

oO°

I z

Figure 2.1: Internal Arrangement of a Laser Scanner

Prior research with laser scanners, [4], highlighted the problems associated with creating mathematical relationships between the deflection of the

scanning mirrors and the vector of the outgoing laser ray in closed form. If

the laser and mirrors are placed at arbitrary locations and orientations, these

mathematical relationships become intractable. This is due, in part, to the

difficulty in determining the values of some of the necessary parameters[4].

To alleviate these problems, two constraints on the placement of the laser

and mirrors must be established. First, the beam emitted by the laser must

be parallel to the rotational a.x.is of the 0 9 mirror. Second, the laser beam

must intersect each mirror at a point along its rotational axis. These constraints are reasonable and practical when one considers that a laser scanner

can be assembled with high precision using current manufacturing technology. These constraints reduce the mathematical relationships between the

scanning mirrors and the outgoing laser ray to two simple relationships which

are described later in more detail.

l0

i

I

i

[]

I

I

[]

i

i

=_

m

I

|

I

I

I

i

ii

i

m

|
w

F

z =

N

h _

m

i

m

w

With Pincushion Compensation

Y

Without Pincushion Compensation

Figure 2.2: Effect of Pincushion Distortion

When the laser beam is scanned onto a plane normal to the laser's z aAs

and at some fixed distance from the laser's origin, it is possible to determine

the (z, y) coordinates of the laser spot as a function of the mirror's angular

deflection. In this situation, the y coordinate of the laser spot is strictly a

function of 0_ and the distance to the plane as shown below:

y = z tan0_ (2.1)

where z is the distance from the laser's origin (L) to the plane normal to

the laser's z axis.

If the z coordinate of the spot is assumed to be independent of 0y,

then the laser exhibits pincushion distortion (as depicted in Figure 2.2). In

reality, the z coordinate of the spot is a function of both 0= and 0y. This

interdependency is due to the fact that the laser beam strikes the 0y mirror

after it is deflected by the 0= mirror (see Figure 2.1). The expression for the

z coordinate of the laser spot is

z = (zsec 0_ + e) tan 0= (2.2)

where z is the distance from L as in (2.1), and e is the distance between the

two scanning mirrors. Note that the zsec 0_ term increases as 10y[ increases.

Hence, the displacement of the laser spot "flares out" away from the origin

in the z direction as the spot moves away from the origin in the y direction.

Equations (2.1) and (2.2) provide the necessary relationships to direct the

laser spot to any 3-D point defined with respect to the laser coordinate frame

without pincushion distortion.

The mathematical relationships presented above describe the direction

of the laser ray. Hence, while it is possible to determine the value of the

11

=

i
U

scanning mirrors angles given a three dimensional point, the mathematical

relationships are not closed s!nce a given set of mirror angles does not relate

to a unique three dimensional point. This is an inherent property of the

laser scanner since the mirrors control the direction of the laser beam, and

there are an infinite number of three dimensional points that are col]near

with this beam. Closed form solutions are only possible if one of the axes

(usually the Z n.y..is) of the three dimensional point is fixed.

2.2 Calibration of the Intrinsic Parameters

The distance between the two mirrors (e) Can be obtained by direct measurement. The degree to which errors in this measurement will affect the

accuracy of the scanner depends onthe environment in which it will be used.

If the laser scanner is situated at a large z distance from the workspace, then

the effects of error in the measurement of e will be reduced. This is the case

in the CIRSSE Testbed, since the distance between the scanning mirrors is

5 mm and the z distance to the workspace is typically 2000 ram. If the laser

scanner is used in situations where z is small, then the distance between the

scanning m]rrors should be deier_ne_analyt_cally. This cart be done in

conjunction with determining the laser's extrinsic parameters (see Section

::7

2.3).

Calibrating the scanning mirrors is critical to proper operation of the

laser scanner. Each mirror is rotated with a galvanometer, which transforms a control voltage into an angular rotation of the mirror. Zero volts

is assumed to correspond to a mirror angle of zero degrees (e.g., the laser

beam is assumed to coincide with the laser's z a._dSwhen both galvanometers

have zero input). The 8_ mirror is calibrated by directing the beam onto a

plane at a tL_:ed z distance from the ias_r_th respect to the laser's origin

(L). With _, fixed at zero, the 8y mirror is rotated with a fixed voltage and

the amount of y displ_.cement on the plane is recorded. Using this information an_! (2.1) it is possible to determine By. Assuming the relationship

between voltage and mirror rotation is linear, mirror rotation is determined

by dividing _ by the voltage app!ied to the mirror = Toconfirm th e l]nearity

of the galvanometers, the y mirror should be displace_: toseveral :different

positions and the relationship should be verified to not change within measurement error. The 8, mirror is calibrated in the same manner except that

9_ is fixed at zero (so there will be no pincushion distortion) and (2.2) is

used to determine _=.

Q

m

g

I

I

m

m

i

i

m

I

m

r_n

[] 

M

[] F

m

! E

m

g

u

12
m

r_

[]

!

w

m

i

/.

m

L

m

u

n

2.3 Calibration of the Extrinsic Parameters using an LSE Method

The extrinsic parameters of a laser scanner can be obtained using an LSE

method as follows. Direct the laser at a set of 3-D points and record the

scanning mirror angles at each point. These points and associated mirror

angles can then be used to solve an overdetermined system of linear equations to obtain the laser's extrinsic parameters. The method described in

this section is analogous to an LSE approach proposed by Roger Tsai[5] for

the calibration of cameras, except that the terms of the linear equations are

different for a laser.

The extrinsic parameters of the laser scanner consist of the rotation

and translation of the laser coordinate frame with respect to some other

fixed coordinate frame. This rotation and translation should ultimately be

represented as a 4 x 4 homogeneous transform (of the type defined by Craig[6]

of the form

rl r2 r3 t_

_T= r4 rs r6 t_ (2.3)

r7 r8 r9 tz

0 0 0 1

The homogeneous transform _T is primarily composed of a 3 x 3 rotation matrix and a 3 x 1 translation vector which define the orientation and

position of frame b with respect to frame a. To calibrate the laser we need

to find t_T, which is the transformation from the laser coordinate frame to

a desired world coordinate frame. What is required is a mathematical relationship that will determine these parameters given a set of points defined

in the world coordinate frame and a set of corresponding scanning mirror

angles. A point ft,, defined in the world coordinate frame is transformed to

the laser coordinate frame using (2.4) to produce /_ (fit and /_, are 3 x 1

vectors):

" (2.4) fit = Yt = _TP_ = _T Yw = r4z_ + rsy_ + r6z._ + t_

zt zw rrxw + rsy_ + rgzw + tz

Also, zl and y_ can be expressed in terms of the scanning mirrors using

(2.1) and (2.2) with (2.4) as shown below:

(zlsecO_ + e)tan_z = rlx_ + r2y_ + r3zw + tz (2.5)

zl tan Oy = r4xw + rsyu_ + r6zw + ty (2.6)

13
Substitutingtheexpressionfor z,_ in (2.4) into (2.5) and (2.6) results in:

((rTx_ + rsy_ -F rgz_ + t.)sec#_ -F e) tanS:= =

_'i=_ ÷ T2y_ + r3z_ + t= (2.7)

(r_'xw + rsyw + r9zw + t=) tansy =

r4xw + rsyw + r6zw + ty (2.8)

Simplifying (2.7) : and ............ (2.8) and then dividing through by t_ (t_ # 0):

tan 8z r7 tan 8z rs

cos 8_ t_

tan 8_ r 9 tan 0_ e

z_-- -F -- -F tan 8_

cos 8y t_ cos 8_

z w t an 8y rT rs

+ y_ tan 8_ + tz

Zw tan #y _ + tan 8y

ez

rl r2 r3 tz (2.9)

r i r2 r3

= _U + Y_U + _ tU+ _(2.1o)t.

Equations (2.9) and (2.10) can be expressed in the form Az = b, where

A is 2n x 12, b is 2n x 1, n is the number of data points collected, and z is

a 12 x 1 vector of unknowns. Note that this system of equations not only

determines the laser's extrinsic parameters, but also the distance between

the scanning mirrors (e). The final form (for tz # 0) is presented below:

tanS_l -x,_l -Y,_I -zw.2 0 0 0

0 0 0 0 -z_i -Ywl -zwl

: : : ....

tansy. -x_. -y_. -zw. 0 0 0

0 0 0 0 -zw. -y_. -z_.

14

l

m,,

I

m

B

|

i

|

i

m

mm

I

I

I

[]

u

m,,

mm

I

m

W

I

m

a

m

m

m_m

m
I

= =

U

L

U

tan Ox, tan Ox, t.._L Z

xw_ tan OyI Yw_ tan 0_ zw I tan 0_ 0 -1

• . .. • .

tan 0_: tan 0:= tan 0.= -i o

xw. tanO_. Yw. tanO_, z_tanOu_ 0 -i

_e 7

i r2

Cos 0:= 1

tan 0_,_

i r_ t,

! r7 cos 0_,_

r8 .tan 0_,_.

r9

tz

After solving (2.11) using singular value decomposition [7], It_[ can be found

from 1

lt, I = (2.12)

Once [tz[ is determined, it is a straightforward process to obtain e, rl,

through rg, tz and t_. With several hundred data points, this method produces reliable results provided that the data points are measured accurately

(i.e., measurement error is < 1 mm). The major flaw in this calibration

method is that it treats the twelve parameters as being independent (which

is obviously incorrect) and thereby fails to meet the constraints inherent in

the rotation matrix.

(2.1z)

w

=

u

rE

u

2.4 Direct Geometric Method for Calibrating a

Laser Scanner

The LSE approach described in the previous section requires a large number

of accurate data points to generate an accurate solution. A solution typically

occurs when the values generated by the LSE method are stable as the

number of data points increases. Usually, two to three hundred points are

required to generate a stable solution. There are situations where it is

impractical to collect a large number of data points. However, it is possible

to measure the laser scanner's extrinsic parameters directly since the laser

emits a beam of light that can be measured with respect to a reference point.

The method presented in this section treats laser scanner calibration as a

15
g

geometrical problem in which the laser scanner's Euler angles and location

with respect to the world coordinate frame are measured directly. It should

be emphasized that the objective of this calibration method is identical to

that of the LSE method: to determine the homogeneous transform from the

laser coordinate frame to some world coordinate frame.

The laser coordinate frame (L) is located at the center of the 8_ mirror

and is oriented as in Figure 2.1. The pose of the world coordinate frame (W)

is arbitrary. To assist in calibr_ting t_ae::[aser,=an intermect_ate coordinate

_ frame F is defined whose origin is Iocated directiy below the center of the

laser scanner's aperture. The frame F is located by suspending a plumb

line from the laser scantier to some fL'<ed plane (the floor is used in the

CIRSSE system). This plumb line constitutes the z a:ds of the F coordinate

frame. Note that while F's origin is on the floor, F's x and y axes are

not-necessarily cop]ana.r_with_:the_ff00r: The location Of F iS selected in

this manner to simplify the measurement of the laser scanner's orientation.

The calibration procedure involves measuring twelve parameters, which are

depicted in Figures 2.3 and 2.4 and defined as:

:z\

! \:::

• T

I Z .'" "

z d_:

L, y

dy2

.-

o*';

d_ \\ "" :

°* "

\..'x'" :

•::,:\, , -

•.. . y ' i.]o{......f" ......'" :"-d"

Z '°-° =

dy,

Figure 2.3: Determination of a Laser Scanner's Euler Angles. (Note: F is

not necessarily coplanar with the floor).

16

z

i

i

II

=_

I

m

l

m

m

am

n

I

|

u

i

Ht

m

m

U

i

m

In
w

m

=

U

u

w

w

= =

g

z

7 W

Figure 2.4: Transformation Parameters from Frame F to Frame W. (Note:

F is not necessarily coplanar with the floor).

d: The distance from F to/_ along F's z a.,cis.

d_ The z coordinate of the point where the undeflected laser beam intersects the floor, measured with respect to the origin of F.

d_ The y coordinate of the point where the undefiected laser beam intersects

the floor, measured with respect to the origin of F.

d_, The y coordinate of the point pl on the floor, measured with respect to

the origin of F.

d_ The y coordinate of the point p2 on the floor, measured with respect to

the origin of F.

d_ The length of the projection of the line segment joining Pl and P2 onto

the vector formed by projecting the z a.,ds of frame F onto the plane

of the floor.

p The rotation about F's z a:ds from F's zy plane to the floor.

The rotation about F's y axis from F's zy plane to the floor.

_t The translation vector from F to W.

a The pitch angle about F's z ax.is from frame F to frame W

The yaw angle about F's y a.'ds from frame F to frame W

7 The roll angle about F's z axis from frame F to frame W

The above twelve parameters provide all the information required to

determine the transformation from the laser coordinate frame to the world

I

coordinate frame: _,T. The calculations are broken into two steps:

1T

B
w

_--L

I

1. Determining ST

2. Determining _T

Once these transformsare known, itwillbe possibleto determine IT from

IT = r.{r (2.13)

_R can be determined by deriving the orientation of frame F with respect

to the laser in terms of the Euler angles pitch, yaw and roll (¢,8,¢) about the

laser's x, y, and z axes, respectively. Figure 2.3 shows how the Euler angles

are measured independently of one another. The laser's scanning mirrors are

set to zero and the coordinates of the point where the laser beam intersects

the floor are measured (d=, d_). It is assumed that any offset of the scanning

mirrors from zero is negligible compared to the mag-nitude of the Euler angles

being measured. Since the mirrors are assumed to be in their undeflected

state, the beam is coincident with the laser's z axis, and the point (d=, dy)

is invariant to rotations about L's z a_s. we will therefore assume that the

laser coordinate frame is rotated about z by an amount ¢ (to be determined)

so that the projection of the laser's y axis onto F's zy plane is coincident

with F's y axis. Such an orientation implies that d= is only a function of 8

and dy is only a function of 0.

dz

F

O_Floo r

jo rl _ _

Figure 2.5: Relationship Between the Floor and F's xy Plane

When calculating 0 and 8,it cannot be assumed that the floor correctly

defines the my plane of F. Indeed, since d.. was measured with a plumb bob,

F's z a_xJs is aligned with earth's local gravity vector, but the floor may not

be orthogonal to this vector. By using a level it is possible to determine the

angles p and _ about F's z and y axes, respectively, between the plane of

18

I

m

B

|

m

mm

[]

i

q

i

m

[]

B

m

I

==

[]

m

i

k--

M

i

m

I |

j
r_

m

_= :

L

u

m

=

E :

J

the floor and the zy plane of F. The situation is depicted in Figure 2.5 for

the Euler angle _/,. The formulas for determining ¢ and 0 can be derived

directly from the figure and are presented below:

_b = tan-l[ d_c°sp+d_s'nptanp]dz (2.14)

0 = tan -1 [d_cos_ +d,sin_tan_]d_ (2.15)

At this point it is necessary to determine ¢ so that the laser's y axis

can be aligned with F's y ax_is. The 0x mirror is repeatedly rotated by

an arbitrary amount while the 0_ mirror is set to zero, resulting in a line

segment traced on the floor. The Slope of this line determines ¢ and is

found by measuring two arbitrary points (Pl and P2) on the line segment

(this yields the parameters d_l, dm and d').

The primary issue with determining ¢ in this manner is ensuring the

slope of the line segment to be a function only of ¢ and not of other vari-

: ables, such as ¢, 0, or 0_ (which .... pincushion distortion). Because we causes

have assumed 8y = O, the slope of the line segment will not be altered by

pincushion distortion. The Euler angle 8 affects the laser's x and z components of the beam direction. _ ci_ange:in the z direction will not affect the

slope of the line since the line ultimately will lie in F's zy plane. Further,

distortion in z will tend to move the line segment by some constant value,

leaving the slope unchanged. The Euler angle _b affects the laser's y and z

components of the beam direction. The distortion in z will not affect the

measurements for the same reasons stated for 0. The distortion in y due

to ¢ consists of a constant translation of the line segment along F's y axis.

The slope of the line is a function of the relative change in y from points pl

to P2, so the effects of _b will not change the slope since Pl and p2 will be

translated in y by the same amount. Hence, the slope of the line segment is

a function only of _.

Since the measurements used to determine ¢ were taken from the floor,

they will have to be corrected for the effects of p and 6 for the same reasons

that the corrections were n.ecessary for determining ¢ and 8. The final

equation for _b is presented below:

¢ co ;+ os,÷

L d_ cos _ + d_ sin g tan 1

(2.16)

19

L_

m
m

l

t

M

At this point the Euler angles _, 8, ¢ have been determined, and it is now

possible to create the rotation matrix _R from the laser to the F coordinate

frame. Each Euler angle changes four parameters in the rotational matrix.

The most straightforward approach is to determine separate rotational matrices for each Euler angle and then multiply them together to obtain _R.

The individual matrices for R(X,_b), 1R.(Y,#) and R(Z,¢) are:

I 0 0 ]

R(X,g,) = 0 cos_b -sin_ (2.17)

0 sin ¢ cos g,

cosO 0 sinO ]

R(Y,e) = -sin00 01 cosO0 ] (2.18)

R(z,¢) Ic°s sin !l = sin ¢ cos ¢

0 0

(2.19)

= R(X,g/)R(Y,(_)R(Z,¢) (2.20)

As is apparent from (2.20), JR is obtained by combining the rotation

matrices in the order roll, yaw, pitch. This ordering is essential for this calibration procedure. Applying the roll rotation first will align the projections

of the laser's y a_s to the F coordinate frame's y axis. This condition was

assumed when the Euler angles _b and $ were determined.

At this point, _R has been determined, but to obtain _,T it is necessary

to determine the translational component _t from the laser's origin to F

with respect to the laser. Given the configuration of the CiRSSE testbed

and the available measuring equipment, it is difficult to directly measure this

value with any degree of accuracy. However, it is not necessary to directly

measure this value. The translation vector it from F to the laser can be

determined since F is located directly _eiow the aperture of the laser, and

dz is known. The resulting value of it is [0, 0, d:] T.

At this point IT can be determined by combining the inverse of JR

(for a rotation matrix, R -1 = R T) with the translation vector [t. It is

then possible to obtain _T by taking the inverse of IT. This relationship is

i

[]

B

--ram

im

m

i

il

i

m

H

mm

m

i

i

I

m

J

m

i

mm

_a

i

2O

g

m

I

i
= =

i..a

m

m

m

"2_

L_

w

g

defined as

-1

tiT=

tlRT {t

0 0 0 1

(z2 )

With _T defined, the next step is to determine _T. W should be chosen

so that the Euler angles a,/3, and 7 can be easily measured. If W is chosen

such that its z axis is plumb (as in the case with F), then the Euler angles

from F to W can be readily determined. By applying (2.17) through (2.20),

it is possible to determine /R, and this matrix can be combined with _t

(which is one of the twelve calibration parameters) to obtain _T. At this

point, tT can be determined by matrix multiplication:

t_T = }T._T (2.22)

This concludes the calibration of the laser's extrinsic parameters. It is

now possible to transform points defined in the world coordinate frame into

points defined in the laser coordinate frame. Additionally, points in the laser

frame can be transformed into the world frame using the inverse of _T.

2.5 Appraisal of Calibration Method Performance

When presented with two alternatives for calibrating the laser's extrinsic

parameters, the question arises as to which method is best. The answer

depends on how and where the laser scanner will be used. The transform

obtained using the direct geometrical method typically results in errors of

less than 0.5%. This accuracy has consistently been obtained in the CIP_SSE

testbed where this method is currently implemented in software. Typical

values for the calibration parameters are presented in table 2.1 This level

of accuracy is sufficient for many visual sensing tasks. Further, the geometric approach achieves its results in a simple systematic manner. Hence,

calibrating the laser using this method requires less effort than the LSE

method.

Since the LSE method generates a solution based on a large set of data

points, measurement errors among individual points should have less affect

on the LSE solution. This is in contrast to the geometric method which uses

a small number of measurements to obtain its results, and, hence, these few

-- 21
J

m

i

Parameter Value

d_: 5.0 mm

dr 101.1 mm

d, 2597.0 mm

p 0.0 radians

0.0 radians

dr, -10.0 mm

d_n 0.0 mm _

dx I 946.0 mm

a 0.0 radians

fl r radians

3' 0.0 radians

/_t_: 1409.9 mm

_ty 887.65 mm

_t. 0.0 mm

e 5.0 mm

Table 2.1: Typical Calibration Parameter Values for Direct Geometric

Method

points must be more accurately measured. The LSE method has been simulated in software and tested with simulated sets of data points containing

differing degrees of error. The results of these simulations indicate that if it

is possible to collect a large number of points with high accuracy, the LSE

could produce more accurate results than the direct geometric method. At

the time t h_!s:_ese_rch_ was c6nducted, the CiRssE ieStbed::had no means to

collect a large number of highly accurate data points, but the LSE method

has the potential to be highly effective When the testbed acquires the necessary data collection capability. --

i

I

i

I

l

m

m

i

m

i

w

E

i '

22

,I

i

i

i

J

m

m

I
m

t_

E .

= =

Chapter 3

Point Estimation with a

Calibrated Laser and

Camera

m

Once the laser scanner is calibrated to a world coordinate frame it is possible

to use it in concert with a calibrated camera to perform three dimensional

sensing. Three dimensional sensing with a camera and a laser is different

from strictly passive methods such as dual cameras. In a dual camera system, features identified in one camera image are correlated to similar features

in the other camera image. The pixel coordinates of these features are then

used to determine the three dimensional point of the object corresponding

to the feature in the images.

Three dimensional sensing with a laser and camera, however, employs

a slightly different approach. The laser directs its beam into the field of

view of the camera and the camera image is scanned for the reflection of the

laser beam off of an object in the image. The pixel coordinates of the laser

beam's reflection (usually referred to as the laser spot) axe correlated to the

mirror angles of the laser scanner to obtain the three dimensional point of

the object in the workspace.

Methods for estimating three dimensional points using dual cameras have

been developed by Repko, Sood, and Kelly [8] and Noseworthy[9]. One

method solves an overdetermined set of equations to obtain a lease squared

estimate of the three dimensional point, while a second method calculates

two three dimensional rays projecting from the image planes of the cameras,

i : 23
i

and estimates the coordinates of the corresponding point by determining the

midpoint of the common normal of the rays.

These two methods for point estimation can be readily adapted for use

with a calibrated camera and laser. In order to do this, the mathematical

relationships contributed by one camera are substituted with mathematical

relationships for the laser expressed in the same form as the camera. Hence,

in order to prove that these point estimation methods will work with a laser

and a camera, it is only necessary to show that the laser's mathematical

model can be expressed in such a way as to be compatible with each method.

3.1 Point-Estimation Using Least Squared Error

The overdetermined system of linear equations approach for dual cameras[9]

can readily be adapted to a camera and a laser scanner. What is needed

is a relationship for the laser between the scanning mirror angles and the

coordinates of a three dimensional point (/3w) defined in the world frame.

Such a relationship was derived in Section 2.3 as part of the LSE method

for calibrating the laser (see equations (2.7) and (2.8)). Ultimately, the

equations contributed by the laser will be included in a system of linear

equations of the form Az = b where z is a three row by one column vector

representing the x, y, and z coordinates of the estimated three dimensional

point.

In the context of laser calibration, the unknown variables were the distance between the scanning mirrors (e) and the rotation and translation

components of the transformation from the laser coordinate frame to the

world coordinate frame. Since the laser is assumed to be calibrated at this

point, all these values are known. Additionally, the angles of the scanning

mirrors are known. What is not known are the z. y, and z coordbaates of

the world point. The terms in__(2"7) and (2.8) can be regrouped into a form

that is more suitable for point estimation:

r 7 -- _ w r8 -- 'r9 -- =

_COSOy 7"i + _COSOy 1"2 _COSOy/ ) yw Jr" I'3 Zw

tan 0=

t= - t, e tan 0_

COS Oy

(rr tan Oy - r4) x_ + (rstan09

(3.1)

-rs)yw + (r9 tan0_ - r6) zw =

ty - t, tan 09 (3.2)

24

i

m

B

m

[]

=_

g

M

i

4

D

-.-2

i

i

m

i

m

eli

im

m

i

m

[]

m

i

[]
Therefore,the lasercontributes two equations with the same three unknowns as the camera equations (assuming that the laser and camera are

calibrated to the same world coordinate frame). These two equations can be

combine with the two equations contributed by the camera[9]. For sake of

brevity, the full derivation of the camera's equations will not be given here

(see Noseworthy(1991)[9]), but the final result is given by equations (3.3)

and (3.4).

L .

L_

,L

-2_:

• _ (_z. - f_x) + y_ (_s_. - f_3) + -'_(_:_ - f_3) =

ft_ - t:. (3.3)

x_ (rTyu - fr4) + Y_ (rsyu - frs) + z_ (rgyu - fr6) =

fry - t_y_, (3.4)

Where zu and y_, are camera pLxel coordinates, f is the focal length of

the camera, and rl - rg, t_, ty and tz are elements of the homogeneous transformation C_T from the camera's coordinate space to the world coordinate

space. Equations (3.3), (3.4), (3.1), and (3.2) can be expressed as a system

of linear equations of the form Az = b:

(rTx_ - frl) (rsx_ - fr3)

(rry_- rr4) (rsy_- frs)

(t___._o r :t_____o _o_O r rl) -r2) _ cos Ou r8

(rrtanO_-r4) (rstan0 u-rs)

 r9..3 11]

(rgy_ - fr6) | x_

ta_O_

Zw

(r9 tan O_ - rs)J

(/t_ - t_u_)

(t=- tZcosO _--_°u -- etan o_)

(ty - tz tan 0u)

.m

(3.5)

The system of equations presented in (3.5) can be solved using singular value decomposition[7]. Care must be taken, however, in interpreting the results of the LSE solution[9]. The LSE approach solves for z

by minimizing the expression: (b- Az) r (b- Az) where z = (A TA) -_

ATb where the quantity (ATA)-I is the pseudo-inverse of A. Minimizing

(b - Ax) T (b - .4x) does not mean that the error between the actual point

25

L=

r_

w

w
=_

I

and the estimated point has been minimized. Since this is "implicit" estimation, the error is minimized, and by so doing, it is assumed that the

parameter of interest (z) is optimized in the process.

3.2 Point Estimation Using Midpoint of Common Normal

Another method for estimating three dimensional points was developed by

Noseworthy[9]. This method calculates a ray projecting from the camera's

image plane into the three dimensional environment. A brief summary of

this work is presented below followed by a description of how this method

can be adapted for use with a laser

A three dimensional point is calculated by determining the midpoint to

the common normal of the rays calculated from two different cameras, the

ray for each camera is expressed as a linear parametric equation of the form:

= + (3.6)

Where (5c is the 3 × 1 vector describing the location of the origin of

the camera with respect to the world coordinate system, and a_c is a 3 × 1

vector describing the direction of the ray projected from the camera's image

plane with respect to the world coordinate system. These two terms can be

further expressed as:

i

do = _'R y_ sc (3.T)

L

6c = yRyt (3.s)

_R and It can be obtained from the inverse of the homogeneous transform _,T, and z_ and y_, are camera pixel coordinates. Once these parametric

equations have been determined it is possible to calculate the unit direction,

in world coordinates, of the common normal to the rays from two cameras

as:

g

m

i

J

mi

m

m

m

i

Ii

m

i

i

m

el

i

m

J

J

26

m

m

ibm

i

I

m
w

==

w

= :

w

x Zo,

I de,x de2I

l d-c, x de2 I_ 0 (3.9)

The shortest distance between r-c, and r-c2, l, can be determined by projecting Oc_ - (_2 in the h direction. Mr. Noseworthy points out that r'c_

and r-c2 are assumed to be skew (i.e. I d_c,x d_ I# 0). l is determined using

the following expression:

l = (3.10)

I x I

Finally, a 3 x 1 vector, rh, representing the coordinates of the midpoint

to the common normal of r_, and f'¢c_ is determined by:

'The midpoint -to the common:n6rmal method can also be used with a

calibrated camera and laser scanner: To do this, it is necessary to derive

a parametric equation for the 3-D ray of the laser beam. This equation is

expressed as

= st_ + dz (3.].2)

where Ot is the origin of the laser beam in terms of the world coordinate

frame, _ is the direction vector of the laser ray and st is a parameter.

Equation (3.12) is of the same form as (3.6). To use the midpoint to

the common normal method with a calibrated laser, it is necessary to derive expressions for Or, _ and st. Once these values are determined, the

mathematical relationships for the midpoint of the common normal for two

cameras will also work for a calibrated camera and laser.

(_t can be determined based on the values of the intrinsic and extrinsic

parameters of the laser scanner. Specifically, the required parameters are

the distance between the scanning mirrors, and the transformation _T from

the laser coordinate frame to the world coordinate frame. The laser calibration assumes the laser's origin to be at the center of the 8_ mirror. The

coordinates of the laser's origi n with respect to the world coordinate frame

27

m
m

), :

can be derived by extracting the translational component of the inverse of

t

the _T. This translation vector is defined as _t.

The origin of the laser has one additional component. Recalling the

arrangement of the laser scanner described in Section 2.1, the _== mirror

deflects the laser beam along the rotational a.,ds of the 0r mirror. Since

the origin of the laser scanner is defined to be on the 0y mirror, the origin

of the laser ray is translated along the Z a_s of the laser scanner (this is

the:rotational a.vSs o_:t_e::_y mirror i by't-he rota.tion of the _= mirror. The

translation of the laser's origin as a function of _z with respect to the laser's

coordinate frame can be expressed as a 3 x 1 vector:

= o (3.13)

0

The term e tam 8_ from (2.2) defines the z coordinate of the laser beam

with respect to the laser's coordinate frame given a set of mirror angles and

a specific z coordinate. The vector _ is defined in terms of the laser coordinate frame; hence it must be transformed into a translation with respect to

the world coordinate frame. This is accomplished by multiplying _ by the

rotation matrix _R contained in the inverse of the homogeneous transform

_T. This yields a new translation vector defined in the world coordinate

frame:

G, =rR.G (3.t4)

Therefore, the final value for (Yt can be expressed as

Ot = j_t 4- t',_,_ (3.1.5)

The next.step is to determine d_ from (2.2) and (2.1). Since 1;he expression f0r Ot already compenssates for the translation of the laser's orion

due to rotation of the 8= mirror, the e tan-#= _erm in_(2.2) can be removed.

Hence, the direction of the laser ray with respect to the laser coordinate

frame can be expressed as a 3x I vector of the form

zsec0_ tan 0_ 1

d_ z tan _ (3.16)

z

28

n

i

i

i

m

m

i

m

m

I

! !

J

i

!

J

i

m

i

J

i

m

i

!

E

i

D

m

z
m

o,'_

r

i

w

The direction vector is currently defined with respect to the laser coordinate frame. In order to use it in determining the midpoint of the common

normal, it will have to be transformed with respect to the world coordinate

frame. This can be done simply by multiplying _ by the rotation matrix

_R. Further, the z term in _ can be factored out and used as the variable

parameter st. Therefore, the parametric equation for the 3-D laser ray can

be expressed as

= _Rdtz. +(gt (3.17)

Equation (3.17) can be used in place of the parametric equation for

the second camera to determine the midpoint of the common normal for a

camera and a laser scanner. The remaining mathematical expressions for

the midpoint of the common normal calculation remain valid.

3.3 Appraisal of Point Estimation Methods

As mentioned previously, the LSE point estimation method generates a solution by attempting to optimize the value of z. Because this method attempts

to determine an optimized solution, it can accommodate minor errors in the

camera and laser calibration parameters. This property of the LSE method

can be useful in that minor calibration errors will not necessarily result in

poor point estimates.

The midpoint to the common normal method attempts to model the

exact behavior of the laser and camera. Specifically, it projects rays from

the laser and the camera into space based on the mirror angles of the laser

scanner and the pixel coordinates on the camera's image plane. If all the

calibration parameters for the laser and camera are perfectly accurate, the

rays should intersect, but in reality, the rays do not intersect due to errors

in calibration, and hence, the midpoint of the common normal to these two

rays is used as the estimate of the three dimensional point.

The decision as to which method to use for point estimation depends on

the nature of the application in which the method will be used. Since the

LSE method is more robust in terms of accommodating calibration errors it

may be useful in situations where the accuracy of calibration parameters is

questionable. However, it is not clear at what point calibration errors will

severely affect the performance of the LSE method.

While the midpoint to the common normal method is less tolerant of

calibration errors, it does Mtve one significant quality. Since this method is

29
N

J

a direct representation of the geometry of the point estimation scenario, it

may be possible to use this method as a means of predicting how calibration

errors will affect performance.:]fperformaace can be predicted aheadof time

it might be possible to modify the point estimates to account for calibration

error. Future research in this area will be necessary to better understand

the appropriate application of these two point estimation methods.

m

m

i

m

g

m

m

m

t

m

i

I

g

R

i

I

u

m

U

g

I

3O

u

m

D
o +

m

Chapter 4

Locating a Laser Spot in a

Camera Image

L

w

w

To use a calibrated laser scanner in concert with a camera, it is necessary

to be able to locate the laser spot in the camera image. This is a simple

problem if one can guarantee that the laser spot is the brightest region in

the image. However, such an assumption restricts the utility of a calibrated

laser by placing illumination constraints on the image. If techniques can be

employed to locate the laser spot in the presence of "noise" (e.g. pixels of

similar intensity), then a calibrated laser can be used in a wider variety of

situations. The method developed by the author to locate the laser spot

in a noisy image is a heuristic approach whereby regions in the image are

successively eliminated based on a set of criterion tests.

The first step in locating the laser spot is to perform region growing over

some selected area of the image. This results in a list of regions, their area,

and their centroids. The laser spot should be one of the regions in this list.

To isolate the laser spot it is necessary to eliminate all those regions that

are not attributa:ble to the laser. There are four different tests that can be

applied to the region list to perform this elimination. Each test returns a

list of the regions that passed the test. The laser spot should be the only

region that passes all four tests.

The first test is to eliminate all regions that do not fall within a specified

intensity range. Since the laser will appear as a small bright spot, it will

be one of the brighter re_ons in the image. However, there is no guarantee

that the laser spot wiU be among :the brightest. Indeed, if the laser beam is

illuminating a matte (low reflectivity) object, such as a piece of cloth, then

31

+

w
U

the intensity of the laser spot will be lower than if the beam was reflecting

off a piece of metal. Additionally, specular reflections of ambient light off of

high reflectivity objects can exhibit the same intensity as the laser spot.

A second test that can be applied to the region list is to eliminate regions

that do not fall within a certain range of sizes. The laser spot typically

occupies between two pixels and twenty pixels depending on the reflectance

of the object the laser beam is striking. The tests for size and intensity can

detect the presence of a laser spot in the image in most cases. Problems

arise when there are other regions in the image that have the same size and

intensity characteristics as the laser, such as specular reflections.

If after application of the intensity and size tests the region list still has

more than one candidate region, two more tests can be applied to further

reduce the list. One of these tests is to take the centroid coordinates of each

region and the known scanning mirror angles, run them through a point

estimation algorithm, and eliminate the regions that generate solutions that

fall outside of the workspace. This method does assume that some a priori

knowledge ex.ists about the expected location of the laser spot. The more

that is known about the expected location of the laser spot, the _eater

the chance of correctly identify!ng it. =Usually, little a priori knowledge is

required to locate the laser spot, since only thoseregions that lie along the

laser ray will generate results that are reasonable.

A final test can be employed if all the previous tests have failedt 0 return

a unique solution for the laser spot. The laser beam can be moved and another image acquired. The new image is passed through the region growing

algorithm just as the first image. If the scene is static, the only region that

should have moved is the laser spot.

It is important to note that it is not necessary to. use all four tests. If

a subset of tests yields one region, then the remaining tests do not have to

be run. Further, there are situations where it may be impossible to locate

the laser spot. If the laser spot is within the bounds of a bright region,

the camera may not be able to distinguish it. This problem is particularly

acute if the camera's aperture is too wide, since bright regions could then

saturate the camera's CCD element. The laser spot is also undetectable if

it is physically occluded by an object i1{ ti_e Workspace. It should be noted

that these four tests do not necessarily have to be performed in the order

stated above. Indeed, part of the evaluations presented later in this chapter

address the question of an optimal ordering for these tests

J

[]

[]

J

[]

i

i

m

l

B

i

m

mm

I

[]

M

m

U

[]

32

q

l

!
m

4.1 Application of Region Growing Algorithm to

a Camera Image

Once a camera image is acquired, a region of interest is selected whose

boundaries are such that it encompasses the laser region. The pixels within

the region of interest are grouped into regions of similar intensity. The

algorithm employed in this research is similar to the blob coloring algorithm

proposed by Ballard and Brown [10]. The specific heuristic algorithm used

in this application is described in figure 4.1.

A pixel is considered part of a unique region if its intensity is similar (by

T_gio,_) to its top, left, or top-left neighbors. The algorithm generates a list

of regions identified in the image. Each entry in the list contains data on

the regions size (in pixels), ma._dmum intensity, centroid, and equivalence to

another region in the list. The concept of region equivalency deserves more

explanation. Envision performing this algorithm on an image that contained

a region that is shaped like the letter "U". As the pixels are scanned the

top portion of the "U" would be identified as two distinct vertical regions.

At the point where the pixels form the curve at the bottom of the "U', the

algorithm will find that the two regions its has been growing are actually

the same region. In this case, an equivalency pointer in one region is set to

the value of the other region.

The number of regions that are generated by this algorithm depends

on the values of Thick and T_gio,_. Thick essentially dictates how much of

the image is eligible for region growing; while T_gio,_ determines how much

contrast is required between pixels before a new region is detected. While

the specific values for these variables depends on lighting conditions and

image complexity, the values used in the CIRSSE testbed for room lighting

conditions are typically {150 < Tb,,ck < 190}, {8 < Tre_io,_ < 10}.

After the region list is constructed, it is assumed that any of the regions

could be the laser spot. The next step after region growing is to eliminate

from consideration all those regions that are equivalent to other regions (i.e.

those regions that do not have the equivalency pointer equal to itself). At

this point, the equivalency list contains a list of N unique regions.

33
u

m

a

W

I

for each pixel from left to right and top to bottom do:

ifpixel intensitY..> - background threshold Tb,_ck

if pixel directly above current pixel is part of a region and intensity of current pixel is similar to pixel directly above to

within a given threshold T_egio,_

• Mark current pixet as belonging to the same region as the

pi×el directly above it

else if pixel to left is part of a region and intensity of current pixel is similar to pixet directly above to within a given

threshold T_egio,_

• Mark current pixel as belon_ng to the same region as the

pixel directly above it

else if pixel to the top left is part of a region and intensity

of current pixel is similar to pixel directly above to within a

given threshold T_gio,_

• Mark current pixel as belonging to the same region as the

top-left pixel

else

• Current pixel is part of a new region

else

pixel is part of the back_ound

/* Check for region equivalence */

if {pixet to left of current pixel is part of a region} and {pixel above is

part of a different region} and {the intensities of the two regions

are similar to within T_egio,_}

• Region to left of current pixeI is equivalent to the region above

the current pixel.

end loop

Figure 4.1: Region Growing Algorithm

I

i

m

r

R

m

Q

m

m

m

u

m

l

!

l

m

m

m

i

u

I

34

_=

i
4.2 Region Selection Based on Intensity and Size

Regions can be eliminated based on intensity and size criterion. This process

is straightforward in that each region in the list is checked to see if it falls

within a range of intensity values or within a range of size values depending

on which criteria is being used. To ensure efficient performance, the size

and intensity tests should be performed only on those regions that have not

been eliminated as possible laser regions.

The execution time of the intensity algorithm can be expressed as:

w

m

m

r_

F( intensity) = Co,rid(N) + Ci,_t_,,_itu( ntl )

{0 < ,,_, < N} (4.t)

Where Cvatid represents the execution time required to determine if a

region is a possible laser region and Ci,_t_,_it_ represents the time required

to determine if the region's intensity falls within the specified limits. Since

both of these operations consist of if/then comparisons the computation

times for these operations can be expressed as constants, nt_ represents the

number of regions in the list that have not been eliminated as laser regions.

Similarly, the execution time to eliminate re_ons by size can be expressed

as:

{0 < nl2 _< iV} (4.2)

Where C_i.., is the execution time to determine if a region's size falls within

specified limits, and this value is also a constant. In practice, Csi_, and

Ci,_te,_it:, are approxJmately equal, and hence, so are F( intensity) and F(size).

The execution time analysis for these two algorithms is trivial, yet, as will be

discussed later, the performance of these algorithms is critical in determining

the order of execution for all the selection criteria.

4.3 Region Selection Based on Laser/Camera Triangulation

Another method for determining the laser region is to apply the three dimensional point estimation algorithms specified in chapter 3 to each region

35
I

=--

N

in the region list. Assuming the deflection of the laser scanner's mirrors is

known, and the laser and camera are caUbrated, the centroid data from each

region can be used to estimate the three dimensional location of each region.

If there is some knowledge ts to the three dimensional location of the laser

spot, the three dimensional point estimates can be successively eliminated

until only those points that are consistent with the expected value remain.

The primary issue at hand is how much knowledge of the three dimensional location of the laser spot is needed to yield a unique solution. In

practice, the laser region must lie along the projection of the laser ray across

the camera's image plane. If the centroid of a region deviates from this projected line, then the point estimation algorithm will be trying to triangulate

two divergent rays.

In practice, the three dimensional point estimates for regions other than

the laser spot become highly irregular and minimal knowledge of the laser

spot location is needed to reduce the set of point estimates to a unique

solution. For example, in the cIRSSE testbed, the world origin is located

about 10cm above the floor with the Z axis directed up at the ceiling. If a

point estimate yields a Z Of-80cm, this implies that the laser spot is located

somewhere in or under the concrete floor of the testbed, and such a condition

is dearly impossible.

The implementation of the triangulation algorithm currently used by the

author employs the LSE point estimation algorithm described in section 3.1.

Each region that has not been eliminated as a possible laser region is passed

through the point estimation algorithm and the region is either eliminated

or accepted if the estimated point lies within a specific three dimensional

volume. Typically, this volume is centered about an estimated position of

the laser spot and is constrained to +/- (5-10cm) in each a.xJs about this

position.

The execution time of this algorithm can be expressed as:

F(triangle) = C.ol_d(,V) + Ctr_.gL, nt3

{0 < _L3_ _V} (4.3)

Where hi3 is the number of regions in the region List that are possible

laser regions and Ct_i_,_gte is a constant representing the computat]on:tlme

to estimate a three dimensional point for an arbitrary region. The C_i_,_gl_

36

I

[]

[]

I

i

i

u

=--

I

m

I

t

M

g

I

m

M

i

[]
T: E

for each region in current region list do

if current region X has not been eliminated as a candidate laser

region

for ith region {0 _< i < N} in previous region list do

if distance between centroid of region X and region i <

MazDistance and difference between size of region X

and size of region i < MaxSizeDiff and difference between intensity of region X and intensity of region i _<

M az lntensityD if f

• ELiminate region X as a possible laser region

= =

w

Figure 4.2: Algorithm for elimination of regions based on movement

term deserves more explanation. The LSE point estimation algorithm uses

singular value decomposition to calculate the estimated point. The execution time of the algorithm is dependent on the size of the A and b matrices.

The size of these matrices is dependent on the number of sensing devices

used to estimate the three dimensional point. In the case of one laser and a

camera, the A matrix is four rows by three columns wide and the b matrix

is four rows by one column. Since the number and type of sensing devices

should not change during the middle of the triangulation algorithm, the dimensions of the A and b matrices will not change. Hence, the execution

time for the singular value decomposition algorithm will be the same for

each estimated point, and this value can be expressed as a constant. It is

also important to mention that the value of Ct_i_gte is much larger than

either Ci,_t_,uity or C, iz,. Hence, while all three algorithms execute in O(N)

time, the triangulation algorithm requires geater time to execute that the

size or intensity algorithms.

4.4 Region Selection Based on Movement

Another method of determining the laser region is to acquire one image,

move the laser, acquire a second image, and then eliminate all those regions

that did not move. The algorithm used to determine if a region has moved

is presented in figure 4.2

_z

w

37
B

Thealgorithmin figure4.2will identifynewregionsin thecurrentregion

list as regionsthat havemoved.This is due to the fact that a newregion

in the currentlist cannotbecorrelatedto aregionin the previousfist. This

characteristicof the algorithmis neithera drawbacknor an advantageas

much asit is necessaryto understandthat the algorithmbehavesin sucha

manner.The executiontimeof the algorithmcanbeexpressedas:

r(movement) = c.._,dxC.._....t + C._o._m_,_,nl4:Vpr.,,,o_,.

{0 _< nl4 <_Ncur_e,_t} (4.4)

As one might expect, iVc_,_e,_i a_nd Npr_;i;,_s:-are the number of regions

detected in the current image and the previous image respectively, and

Crnovernent is the execution time required to determine if a single region

have moved from the previous frame. Assuming that Nc,,_,_,_t _ Np_,io_,s

the algorithm in figure 4.2 executes as O(Nc_,_,_t 2) in the worst case.

4.5 Evaluation of Laser Region Identification Performance

A treatment_of the issueof detectinga laserspot in a camera image would

not be complete without a thorough evaluationof the performance of the

algorithms under experimentalconditions.The regionselectionalgorithms

were combined intoa singleprogram thatdirectsthe laserto specificthree

dimensional pointsand subsequentlyacquiresimages of the workspace for

each point using a camera. This program was subjected to four different

batteries of tests to determine the behavior of the laser spot selection algorithms to varying experimental conditions. The descriptions of the four test

batteries are presented below:

• Test Battery I: While maintaining constant lighting and region detection parameters, vary the comple,,dty of the image by adding objects

of differing size, and reflectance qualities. Low comple:dty images had

few objects such cable, a few bits of metal and so forth, while more

complex images contained everything in the low comple_ty images

plus struts and unpainted metal nodes.

• Test Battery 2: While maintaining constant scene comple.,dty and region detection parameters, vary the location and intensity of scene

illumination.

38

E

m

R

M

l

N

M

I

m

m

i

U

i

B

M

m

I

R

m

m

B

D
Intensity Min 210

Max 255

Size Min 4 pixels

Max 50 pixels

Movement MaxDistanceDiff 5 pixels

Ma.vIntensityDiff 15

MaxSizeDiff 10 pixels

Triangulation

Tests 1,2,4

Test 3

{-50 < X < 50} mm

{-50 _< Y _< 50} mm

{-50 < Z _< 100} mm

{-200 < X < 200} mm

{-200 _< Y _< 200} mm

{-350 _< Z < 500} mm

Table 4.1: Parameters used for Test Batteries

• Test Battery 3: While maintaining constant scene complemity and illumination, place objects over a wide range of three dimensional locations in the workspace. The objective here is to determine how the

triangulation algorithm performs when the valid three dimensional

volume is set to encompass a large portion of the workspace.

• Test Battery 4: While maintaining constant scene comple:dty and illumination, vary the order in which the region selection algorithms are

executed.

The parameters used for the region selection algorithms are summarized in

table 4.1. The X, Y, and Z parameters for the triangulation algorithm define

the valid three dimensional volume for region point estimates. The volume

is defined with respect to the X, Y, and Z coordinates of the expected

location of the laser spot. The expected location of the laser is determined

by instructing the program to direct the laser beam at a specific world point.

The three dimensional volume was changed for test battery three since the

objective of these tests is to determine if the triangulation algorithm will

work with a large valid volume.

The results of each test are encapsulated in eleven parameters defined

as follows:

39

w
U

B

A vgRegion The average number of regions detected by the region growing algorithm over all test trials.

• AvgEquiv The average number of regions criminated as the laser region

due to equivalency over all test trials.

AvgIntensity The average number of regions eliminated as the laser

region due to selection by intensity over all test trims.

• AvgSize The average number of regions eliminated as the laser region

due to selection by size over all test trials.

• AvgMovement The average number of regions eliminated as the laser

region due to selection by movement over all test trials.

• AvgTriangle The average number of regions eliminated as the laser

region due to selection by triangulation over all test trials.

• NoLaser The number Of test trials where no laser region was found.

• Laser1 The number of test trials where one laser region was found.

• Laser2 The number of test trials where two laser regions were found.

• Laser3 The number of test trials where three laser regions were found.

• LaserGT3 The number of test trials where more than three laser regions were found.

Each test in each test battery consisted of one hundred laser points.

Tb=_k and Tr,_io,_ were set to 190 and 10 respectively.

4.5.1 AnalYsiS of Test Battery i ReSults

The first battery of tests were designed to study the behavior of the laser

spot selection algorithms to images of va_ing c0mpie.,dty. The first test

was conducted on a scene of low comple.,dty that contained a few metal

objects and a cable. The second test was conducted on a scene of higher

comple:dty that-included more muiti'faceted metai objects and a few hand

tools. Finally, the third test was conducted oll a highly complex scene that

included struts and nodes, grippers from the CIRSSE robot arms and a

metal plate. The results of each test are presented in table 4.2.

i

[]

g

m

I

g

|

|

g

i

I

R

|,

i

M

4O

N

B

zm

m

i
w

m

°;_

r_,.-

Parameter Test

A vgRegion 96

AvgEquiv 15

A vgIntensity 36

A vgSize 33

A vg,_Iovement 10

A vg Triangle O 1

NoLaser 3

£aserl 97

Laser2 0

Laser3 0

LaserGT3 0

Image Complex.ity Low

Test 2 Test 3

129 546

17 89

52 200

45 203

12 49

0/1 2

4 8

96 90

0 2

0 0

0 0

Moderate High

Table 4.2: Results of Test Battery One

The results of the three experiments indicates that elimination by size

and by intensity had the greatest effect in reducing the number of regions

in the image. Further, the triangulation algorithm was not required for

the first two tests, which implies that size, intensity, and movement are

sufficient criteria for identifying the laser in simple or moderately complex

images. What is most significant about the test results is the number of

times the laser spot was identified. The worst case results indicate that the

selection algorithms produced a unique solution for the laser spot 90% of

the time. What is even more interesting, is that there are few instances of

identifying more than one region as the laser. Indeed, the results indicate

that the selection algorithms either found a single laser spot or none at all.

The instances where the laser was not found can be attributed, in most

cases, to effects of illumination or occlusion that prevented the camera from

distinguishing the laser region. For example, it was observed in several

instances that the laser spot was projected near an object such that the

object occluded the laser spot from the camera's field of view. Further,

there were regions in the image that registered as full intensity (i.e. 255)

and when the laser was direct_ed into these regions, the camera was unable to

distinguish tile laser spot since it was embedded in a region that saturated

the CCD array. In short, failure to detect the laser region altogether is due

mostly to the inherent limitations of the equipment used to perform the test

and not to the performance of the algorithms.

E

w

41
i

I

4.5.2 Analysis of Test Battery 2 Results

The second test battery" was designed to study the effects of illumination

on the selection algorithms' performance. The first test in this set was

performed on an image of moderate complexity (similar to test 2 in the

first test battery) under normal room_ lighting conditions. This first test

provided a baseline for ¢,,,a,,_,in=_,..._, performance on other tests. The second

test was conducted with the lights off. The third test was conducted with

a single light source projected from one end of the scene (the top of the

image} and oriented to place strong shadows on the objects in the scene. In

the final test, a single light source was oriented not only" to project strong

shadows on the objects in the scenel but also to project reflection spots and

halo effects into the camera's ietis. The results ofthese tes{s are presented

in table _.3. =............... ....

Parameter Test 3 Test 4

A vgRegion

AvgEquiv

A vgIntensity

A vgSize

A vgMovement

A vg Triangle

NoLaser

Laser1

Laser2

Laser3

LaserG T3

Illumination

Test 1 Test 2

474 3

6a 0/1

213 0/1

159 i

al 0/1

s oil

5 1

93 99

2 0

0 0

0 0

Normal No 5ghts

368

46

154

127

37

1

5

94

1

0

0

Shadow

568

131

176

227

28

3

15

84

1

0

0

Shadow & lens reflection

Table 4.3: Results of Test Battery Two

The results indicate that for the first three tests, the selection algorithms

were largely resilient to changes-in ambient light, in that the selection algorithms achieved a unique solution in more that 93% of the trials. What

is particularly interesting is how performance degraded !n test 4. It is not

surprising that performance would degrade if Light is directed in the camera,

but what is interesting is that the pattern of performance is nearly identical

to the results obtained in the most complex image of the first test battery'.

While the similarity in the exact numbers may' be a coincidence, the pattern indicates that the performance of the selection algorithms degrades in a

42

I

[]

I

=

m

l

m

= =

a

I

!

==

l

I

M

g

i

B

I

B

I
r

l

J

i

=

m

Parameter Test

A vgRegion

A vgEquiv

A vgIntensity

A vgSize

A vgMovement

A vg Triangle

NoLaser

Laser1

Laser2

Laser3

LaserGT3

1 Test 2

499 189

103 41

208 74

132 52

43 17

9 2

17 8

68 79

5 11

4 2

6 0

Table 4.4: Results of Test Battery Three

consistent manner. That is, the algorithms either achieve a unique solution

for the laser spot or none at all. When test 4 was actually conducted, it

was observed that the laser region was lost when the laser was directed into

a region of the scene that was highly illuminated (to the point where the

camera was saturated) or the laser was directed into a region of the image

that contained a lens reflection. In both of these cases, the intensity of the

image registered as 255 which is the ma_mum intensity value for the vision

system, and therefore, the laser spot was visually indistinguishable from the

surrounding image.

4.5.3 Analysis of Test Battery 3 Results

The third test battery was designed to test the effectiveness of the triangulation algorithm if the valid three dimensional volume was enlarged to

cover a greater portion of the testbed. In this test, objects were placed in

the workspace in such a way as to ensure that specular reflections and other

noise were present over a wide three dimensional volume in the workspace.

This arrangement was adopted to increase the chance that specular reflections would lie along the laser ray thereby increasing the probability that

the selection algorithms would misidentify some of these regions as being

attributable to the laser. The results for test battery three are presented in

table 4.4. The two tests were virtually identical, although the arrangement

of objects in the scene was altered between tests to provide different scenes

of similar comple.,dty.

43
u

i

There are two significant observations that can be made about these resuits. First, while enlarging the valid three dimensional volume does increase

the probability that more than one region in an image will be identified as

the laser spot, in the large majority of cases the selection algorithms either

achieved a unique solution for the laser spot or could not find the laser region at all. In other wordsl the general behavior of the selection algorithms

in this battery of tests is similar to the the other test batteries.

A second observation was made while studying the behavior of the selection algorithms as the experiments were conducted. In cases where the

selection algorithm generated multiple solutions for the laser spot the regions in question were either in close pro:dmity to the actual laser spot (to

within a few millimeters) or were a significant distance away from the actual laser spot and situated along the projection of the laser ray through

the image. These observations are not surprising when one considers that

the laser ray and the projected ray from the camera to these regions are not

significantly divergent. To eliminate regions that do not result in divergent

rays, it is necessary to be able to make accurate estimates of where the

laser spot is expected. However, as is apparent by these test results, even a

rough estimate of the valid three dimensional volume results in reasonable

performance.

4.5.4 Analysis of Test Battery 4 Results

The fourth test battery was designed to determine if changing the execution

order of the selection algorithms resulted in a significant change in performance. The results of these tests are presented in table 4.5.

The results of these tests indicate that while the pattern of region elimination differs between the different orders of algorithm execution, the final

results for identifying the laser spot are virtually identical across all the

tests. The implications of this result is that the order of execution can be

arranged to optimize the overall performance of the selection algorithms

Without sacrificing reliability.

To optimize performance of the selection algorithms it is necessary: to

examine the equations for execution time of each algorithm that were derived

previously. The total execution time of the laser selection process is the sum

of these individual equations as indicated below:

44

i

[]

a

[]

g

m

m

i

m

i

i

[]

[]

g

N

i

i f

u i

m

i

i
Parameter Test [ Test 2 Test 3

A vgRegion

A vgEqu iv

,4 vgIntensity

A vgSize

A vgMovernent

A vg Triangle

NoLaser

Laser1

Laser2

Laser3

LaserG 7"3

Order of

Execution

362

38

ll5

174

30

1

6

92

2

0/1

0/1

363

38

6

286

29

1

5

94

i

o/t

o/1

Intensity

Size

Movement

Triangle

Size

Intensity

Movement

Triangle

364

38

6

15

306

1

5

93

2

0

0

Movement

Size

In tensity

Triangle

Table 4.5: Results of Test Battery Four

.°--

2

= -

f...,

r(totat) =

F(movemerzt) + r(triangle)

F(intensity)

r(size)

F( movernent )

Cmovernent n l4 _Vprevioua

r(triangle) =

F(intensity) + F(size) +

= C_=Lid(,V)+ Ci,,u,_,ityfna)

= CuaLid(N) + Csize(nl2)

= CvalidNcurrent +

C_,_ud( N) + Ct,i,,,gl_nt3

(4.5)

(4.6)

(4.7)

(4.s)

(4.9)

where the expressions for r(intenaity),. F(size), r(movement),

and F(triangIe) are restated here for convenience. The total execution time

is dependent on the total number of regions in the image (N) and the number of possible laser regions passed to the individual selection algorithms

(nn, nt2, nta, hi4). Recall from the previous discussion that F(movement)

executes in O(N 2) time in the worst case and Ctri=n_le >> {Cintensity, Csize}.

Therefore, the best way to reduce overall execution time is to reduce the contribution of the r(rnovement) and Ctr_,,,_gt, terms. This can be accomplished

by keeping nla and nt4 small. In other words, use the size and intensity al45
u

m

gorithms to eliminate as many regions as possible before executing the more

computationally complexmbvement and triangulation algorithms. Since the

execution time for the intensity and size algorithms are roughly equivalent

(see section 4.2), the order in which these algorithms are executed will have

little effect on performance.

At this point, it is clear that the intensity and size algorithms should be

executed first to reduce the number of possible laser regions that must be

sent through the m0vement and triangulation algorithms. The next issue is

whether the movement algorithm or the triangulation algorithm should be

executed next. The results from all the tests indicates that {hi3 _ at4} <<

N, and, hence, the movement algorithm's execution time willmore closely

appro_mate O( N) instead of O( N2).

The execution time of the triangulation algorithm also approximates

O(N). It was mentioned previously that the value of Ctri,,_Sl_ is significantly larger than Cintensity and C,ize. In fact, Ctria_gt, is also much larger

than than Cmo,,_¢nt which represents the execution time of a small number of comparisons to determine if two regions are equivalent. When at3 is

small, the value of the the execution time for the triangulation algorithm

is comparable to that of the movement algorithm despite the fact that the

movement algorithm theoretically should be Iess efficient. Therefore, the

total execution time of the laser selection algorithms will be relatively constant regardless of whether movement is executed before triangulation or

vice-ve_a.

4.5.5 Conclusions about Laser Selection Performance

The results presented in the previous sections have provided a plethora of

information about the behavior of the laser selection algorithms, both individually and in concert with each other. From the results and the subsequent

analysis it is possible to draw several conclusions about the performance of

these algorithms.

1. The combination of all four selection algorithms locates the laser spot

reliably under normal lighting conditions and moderate to high scene

complexity,

2. Degradation of algor!:!hmperformance results in a decreased potential

for locating the laser spot in the image as opposed to inadvertently

selecting multiple regions as the laser spot.

46

I

m

[]

i

[]

m

[]

I

[]

--i m

u

I

m

m

m

I

m

I

m

m

m

[]
m

3. Algorithm performance is most affected by occlusion of the laser spot

in the workspace and saturation of the camera's CCD array due to

aperture setting.

4. Laser selection algorithms operate most efficiently when the intensity

and size selections are executed first followed by movement and triangulation.

-:LL

? 2

There are other properties of the laser spot that may be useful in enhancing the discrimination of the spot in a camera image. First, the laser

spot has a specific spectral wavelength and if the camera were fitted with a

filter that is sensitive only to the wavelength of the laser, it would be easier

to locate the laser spot. Additionally, the laser spot has an elliptical geometry. Therefore, if the region growing algorithm were modified to record more

information about the geometry of each region such as the length of the region's perimeter and the region's moments of inertia, it might be possible

to eleiminate regions that do not resemble a small ellipse.

Overall, the techniques discussed in this section for locating a laser spot

in an image offer a reliable method for laser tracking under a variety of

lighting and scene conditions. These methods will permit a calibrated laser

and camera to operate under the same conditions as multiple camera configurations. Such a capability permits a laser and camera to not only be a

useful active three dimensional sensing device in its own right, but it also

provides the ability to verify results obtained by passive techniques.

47
g

m

Chapter 5

Conclusions and Future

Research

U

!

I

n

[]

I

[]

The laser research has successfully fulfilled the major objectives described

in section 1.2. Specifically, methods have been developed to calibrate the

laser to a level of accuracy that is comparable to the multiple camera system.

Second, the laser can operate in concert with a calibrated camera to perform

three dimensional point estimation. Finally, techniques are now available to

permit a camera to locate the laser spot under a variety of conditions.

With these capabilities in place, there are many opportunities to use the

laser in future rese_.rch. In the near term, research will be focusing on three

major areas. First, the laser and a camera will be used to perform three

dimensional ranging. Under this arrangement, the laser can be used to scan

the workspace to detect objects or major features' For example, recalling the

case studies performed in November of 1990, the experiments were performed

on a work surface that was covered with 0. black cloth. If the partially

completed triangle was not on the work surface, it would be impossible

for the camera system to know where the work surface is located because

a plain black image offers no features to identify and extract. However,

a calibrated laser C0uid scan over the work surface and by employing the

point estimation algorithms described in chapter 3 it would be possible to

determine the location and orientation of the work surface.

A second avenue of research to be examined in the near term [s the

use of the laser to highlight objects or features already identified by the

multiple camera system. This capability could be incorporated in future

vision research as a method of verifying the performance Of the vision system,

48

[]

u

I

m

m

88

I

[]

m

m

I
w

and hence, improving its reliability. As part of this research, the laser could

be integrated into the current CIRSSE testbed applications for assembly of

structures.

Another area of research is to continue exploring the effects of lighting

not only on the laser and camera configuration, but also on passive multiple

camera configurations. This area of research should include both quantitaive and qualitative analysis of lighting and the development of methods

to compensate for its effects.

Finally, effort will be directed toward creating and testing a set of mathematical models that can predict the effects of calibration error on system

performance. Such models can serve several purposes. First, by predicting how the laser will behave under certain conditions, it may be possible to

determine how the laser can be used in an optimal manner. Second, a mathematical model for the laser can be used to determine a level of reliability

for the three dimensional data generated by a camera and laser. Finally,

these models can shed light on the appropriate use of the point estimation

alorithms as discussed in section 3.3

w

°_

=

r--

49
M

m

t

0

Bibliography

[1] K. Pelsue, "Precision, post-objectiv e, two-a_vds, galvanometer scanning," in High Speed READ/Write Techniques for Advanced Printing

and Data Handling, SPIE Proceedings, (Los Angeles, California), p. 70,

January 1983. , -: .... :

[2] J. R. Noseworthy and L. A. Gerhardt, "Three dimensional vision - requirements and applications in a space environment," in Symposium

on Advances in Intelligent Systems, SP[E Proceedings, (Boston, Massachusetts), p. 1387, November 1990.

[3] J. Watson, "Testbed kinematics and routines." CIRSSE Technical

Memorandum, March 1991.

[4] W. J..'Vlistretta, "Analysis, enhancement, and application of a three

dimensional inspection system in computer integrated manufacturing,"

Master's thesis, Rensselaer Polytechnic Institute, Electrical & Computer Systems Engineering Dept., Troy, NY 12180-3590, December

1989.

[5] R. Y. Tsai, "A versatile camera Calibration technique for high-accuracy

3d machine vision metrology using off-the-shelf tv cameras and lenses,"

[EEE Journal of Robotics and Automation, vol. RA-3, pp. 323-344,

August 1987.

[6] J. J. Craig, Introduction to Robotics, Mechanics, _' Control. Reading,

MA: Addison-Wesley Publishing Company, 1986.

[7] W. H. Press, B. R. Flannery. S..4,. Tauk01sky, and W. T. Vetterling,

Numerical Recipes in C: The .4 rt of Scientific Computing. Cambridge

University Press, 1990.

m

I

[]

M

[]

B

I

i

!

I

m

J

i

I

m

I

50

g

w

I

|
L

[8] D. Sood, M. C. ltepko, and R. B. Kelley, "An implementation of a

camera technique to obtain three-dimensional (3d) vision information

for simple assemb|y tasks," C[RSSE Report 76, Rensselaer Polytechnic

Institute, Troy, NY, November 1990.

[9] J. 1t. Noseworthy, "Inaccuracies of three dimensional vision systems -

theory and practice," Master's thesis, Rensselaer Polytechnic Institute,

Electrical & Computer Systems Engineering Dept., Troy, NY 12180-

3590, August 1991.

[10] D. H. Ballard and C. M. Brown, Computer Vision. Englewood Cliffs,

N J: Prentice-Hall Inc., 1982.

===

7

w

51

w
Im

II

• _L* |IIII

IImmIIWB

_

m_

mm_

ii

II _

w