RECOGNITION OF FIDUCIAL MARKS

APPLIED TO ROBOTIC SYSTEMS

/Y_ u:-/3 3 3

by

Wayne D. Georges

w

Rensselaer Polytechnic Institute

Electrical, Computer, and Systems Engineering Department

Troy, New York 12180-3590

W

August 1991

CIRSSE REPORT #103

U
L_! _:_ _: _-:' _i-_....

_

Ji iJm

inii

Ha m

iNIiiiiia|

iN

in

HI i

me

[]
1

m

y--

m

CONTENTS

m

L_

= :

m

u

n

J

LIST OF TABLES ................................. iv

LIST OF FIGURES ................................ v

ACKNOWLEDGEMENT ............................. vi

ABSTRACT .................................... vii

i. INTRODUCTION ............................... I

1.1 Overview , ................................. 1

1.2 Literatute Survey ............................. 2

1.3 Author's contribution ........................... 6

2. MATHEMATICAL BACKC;ROUND ..................... 8

2.1 Rotation Matrices In Three-Dimeasional Space ............. 8

2.2 Perspective Transformation ....................... 12

2.3 Homogenous Coordinates ......................... 13

2.4 Coordinate Transformations Using Homogeneous Coordinates .... 15

2.5 Geometric Moments ........................... 16

2.6 Central _[oments ............................. 17

2.7 Algebraic Invariants ............................ 18

2.8 g, - s curves ................................ 24

3. PROBLEM STATEX[ENT ........................... 26

4. FIDUCIAL .MARK IDENTIFICATION .................... 29

4.1 Design of the Fiducial Marks ....................... 29

4.2 Segmentation of the NIarks from lhe Background ........... 30

4.3 Extracting the Outer. Inner, and X,[iddle Borders ........... 30

4.4 Moments as Feature Parameters ..................... 32

4.4._

4.4.2

4.4.3

4.4.4

._Ioments of a CeneraIized Rectangle .............. 32

5Ioment Calculations for a Generalized Ellipse ......... 36

_[oment Calculations for an Equilateral Triangle ........ 38

.XIoments of ortllogonally l,rojected shapes ........... 40
4.4.5 X[oment approximations d,te to digitization .......... 42

4.5 Curvature as a feature parameter .................... 43

5. EXPERIMENTAL SECTION ......................... 47

5.1 Simulation Results ............................ 47

,5.2 ExperimentaI Results ........................... 50

6. CONCLUSION and FUTURE WORI< .................... 63

LITERATURE CITED ..... : ................... ,: ..... 6.5

m

i

|

i

m

[]

m

m

[]

=

ii

[]

E

II

m

m

II

J

i

E

[]

[]

m

==

[]

I

i:

m

u

i

[]

il

[]

m
= =

u

LIST OF TABLES

m

Table 5.1

Table 5.2

Table 5.3

Table 5.4

Table .5..5

Table 5.6

Table 5.7

Table 5.8

First invariant moment of a rotated and scaled square ..... 48

First invariant moment of a rotated and scaled equilateral

triangle .............................. 48

First invariant _noment of a scaled circle ............ 48

Invariant moments of a rotated and orthogonally projected

49

square ...............................

Invariant moments of a rotated and orthogonally projected

ectuilateral triangle ........................ 49

Invariant moment calculations of fiducial mark ttc. ...... 51

Invariant moment calculations of fiducial mark tst ....... 52

Iuvariant momeut calculations of fiducial mark csc ....... 52

w

w

m

--2

n iV

n
1

m

I

-_ ...... LIST OF FIGURES I!

[]

Figure '2. l

Figure "2.'2

Figure 2.3

Figure 2.4

Figure 2.5

Figure "2.6

Figure 4. [

Figure 4.2

Figure 4.:3

Figure 4.4

Figure 4..5

Figure 4:.6

Figure 4.7

Figure 5. [

Figure 5.2

Figure 5.:3

Figure 5.4

Figure 5..5

Figure 5.6

Figure 5.7

Figure 5.8

Figure 5.9

I_'\;'_,V and XYZ Coordmat¢. • _ Systems 9

Rotation of the UVW coordinate system about the x axis... 10

Pinhole Camera Model ...................... 12

Square and corresponding _, - s curve .............. 24

Circle and corresponding t.' - s curve .............. 25

Equilateral triaugle and corresponding _ - s curve ....... 25

Ceneralized Re,tangle ...................... 33

" _7 ":

Rectangular region in th,' ,t-v plane ............... 33

Etlipse in the u-v plane ...................... 37

Equilateral triaugle in the u-v plane ............... 39

Curvature plot of an ectui]_t.eral triangle ............ 43

C'urvature plot era square . ................... 44

Curvature plot of a circle' . .................... 44

Binary inta.ge c,,ntaining Ii,lucial mark ttc ........... 54

Binary image c(,ntaining fi,lucial mark stc ........... 55

Binary

Bi navy

Binarv

Binary

Binary

Binary

Binary

image containing [-i,lucial mark css ........... 56

image containing fi,lucial mark cts ........... 57

image c_,utaining fi,lucial mark tss ........... 58

image cc,ntaining fi,/ucial mark tst " 59

image c_,utaining li,[ucial mark tsc ........... 60

image c_,ntaining Ii,tucial mark ccc ........... 61

image containing fi,lucial mark tcc ........... 62

B

B

I

I!l

|

i

I

I

I

I

i

[]

I

I

I

I

I

m

I

I
u

ACKNOWLEDGEMENT

I would like to thank my mother, without whose numerous sacrifices and words

of encouragement, I would haw_ never marie it this far. I would like to thank my

father for his constant belief in me. I would like to sincerely thank my entire family

and my friends for their support over the years. I would also like to thank my

thesis advisor Dr. Robert Kelley, for his va luable guidance during the course of this

project. Finally, I would like to thank Sharon for her help and support when it was

needed the most.

I

= =

= =

1 i

m

\'i

w
I

i

ABSTRACT

) The objective of dais pr0]ect i_ to devise, v, method to determine the position and

orientation of the links of a PU),[A .560 using fiducial marks, As a result, it is

necessary to design ficlucia.l marks and a cotresponding feature extraction algorithm.

The marks utilized are composites of du','e basic shapes, a circle, an equilateral

triangle and a square.

Once a mad< iS imaged i} is thresholded and the borders of each shape are

extracted. These borders are suhsequenr[> _tdlized in a feature extraction algorithm.

Two feature extra ctiotl algodth_as are utilized to determine which one produces the

most reliable res_dts. The lit'st algoridun is based on moment invariants and the

second algorithm is based on _;1_,,discrete v,_rsion of the _ - s curve of the boundary.

The latter algorithm is cieatly superior f_n' this application.

I

|

I

i

B

|

[]

m

m

[]

mm

m

mm

m

i1'

l

vii

ORIGINAL PAGE IB

OF POOR QUALITY

m

m

I

m
m

w

m

CHAPTER I

INTRODUCTION

1.1 Overview

Computer vision is an essential part of any intelligent robotic system. It

serves as a means to identify the enviro_t,nent and to verify the robot's location

and orientation. This informati,m pro_'ides t,he parameters to determine the proper

action to be taken by the system.

In the verification of the robot's position and orientation, a means must be

found to identify the position all,:[ oriental i_,n of each joint. The use of fiducial marks

on each link seems to be a.a effective and cost efficient way to accomplish this task.

The marks provide a way of uniquely idenlifying each link and locating a point on

the link. This point along with two calibrated CCD cameras can determine the 3D

location.

There are several criteria the marks must satisfy to be effective tools. They

must be simple enough so that they are ,,I- ' ,entlfia" I_le even under conditions of low

resolution, perspective distortion, rotati, ms, scale changes, and translations. The

above can be stat,_d in another way. There" amst exist an algorithm that can extract

features from the marks that are rotat.io_, translation, and scale invariant, and

the features .should be as inse_sitive a._ l_ossible t_o perspective distortion. For a

discrete image it is not possible lo have fealures that are truly rotationally and scale

invariant. In reality the features are a func_ ion of the resolution of the digitizing grid.

Features that sat ist'y the above constrain_, are sufficient for the task of determining

the status of the link. The position and ,,rientation of a link can be modeled, in

three dimensional space, as an ordered _olation about the x, y, and z axis and a

translation. This _ranstbrma.tio_. _he ]izLk z,ad its corresponding mark are subjected

m

ORIGINAL PAGE IS

OF POOR QUALITY
2

to a projective t.ransformation which is _ noninvertible transformation of threedimensional world space into a two-dimensional image plane. Therefore, every point

in the image is a function of its positon i,l world coordinates, the focal length of

the CCD camera, and the field of view oF the camera. In addition, the image of

the fiducial mark is a function of the distribution of the points around its centroid,

the three rotation angles of the plane thal the marks lie upon, the position of the

centroid, the focal length and the field of view.

Moments provide an excellent way r,o characterize mass distributions: such as

horizontal and vertical centrall_ess, diagol,ality, horizontal and vertical divergence,

and horizontal a ud vertical imbalance..\_tother convenient feature of moments is

their ability to be normalized for scale ch_t,ges and rotations and translations in the

image plane. Many of these invariants can be obtained by using either the theory of

algebric invariant_, introduced l_y Cayley, bIamilton, and Sylvester, or by requiring

that certain lower order too,hems have a pr,'scribed value, and normalizing the other

moments with respect to these lower order moments. Another convenient feature of

moments is their ease of calculation.

U

[]

m

[]

|

|

m

[]

[]

z

[]

Z

m

n

1.2 Literature Survey

Many papel's have been wtitten otL rl,e use of moments in pattern recognition

applications. One of the first is the 1)apor written by Hull]. In this paper Hu

discusses recognilion of t.wo-diTaensional g,,ometric patterns by using the classical

theory of algebric invariants to derive tm,ment invariants that are insensitive to

scale, position, arid ocientation. This ntcll_od uses invariant moments based upon

uniquely determined principal axes and th,' method of absolute moment invariants.

These monient invariants are subsequently stored in a feature vector and compared,

using a minimum dist.ance formulation, to feature vectors of known patterns.

z=

i

m

m

g

m

l

m

m =

I

ORIGINAL PAGE iS

OF POOR QUALITY

In

III
N

m

n

z

u

g

w

Udagawa et alia[2] use m_,ments to identlfy capital letters of the English alphabet. Their method consists of normalizing linearly distorted patterns by setting

certain conditions on the lower order moments. The method essentially normalizes

for any distortion due to an a/:fine transfot'mation. The normalized moments are

used as recognition featut'es.

AltI3 ] uses momet_ts to kl_.ntify lett.er's and numbers. He normalizes each, pattern with respect to position, size, stre_c]tiug and squeezing in the x or y directions

and slanting in _he x direction. The paI_.et'ns are not rotationally invariant. The

rotational variance is done to f_,cilita.te _,lte' discrhnination of 6's and 9's. The slant

invariance is utilized to identify italics a_vl bold faced letters as the same pattern.

Normalization is accomplished by utilizing the standard deviation and the regression coefficient of× on y. Third through sivth order moments are calculated for the

twenty-six capital letters and nine numbers. The discrimination algorithm searches

for gaps in the values of a particular monle,lt. These gaps are discrimination points

that separate certain patterns from others. Once subregions are formed based on

these points, another moment is used to 1;,'eak the subregions into smaller regions.

The process contit_ues l.u_Iti[ eacl_ sul)t'egi<,ii consists of one element.

Casey[4] deals with the p,oblem of ,,ormalizing handprinted characters. Because of the larg_ dispaiitx in handw1i_il,g styles, recognition of characters is a

difficult task. He rnodets the ,tistortiou _,s a.n affine transformation. This information is used t.o dit'ect the dit'ection oF -can of an optical character recognition

device to obtain _ mot'e uniforn_ scan ol" t(',ters. He uses the same methodology as

Udagawa.

Smith and \Vright[.3] uses lhe method of nloments to estimate the location, orientation, length, width, and heading of a sl_ip. The estimates are obtained by taking

moments of a ship photograph and usin$ linear, quadratic, and cubic polynomial

functions of the n_oments as es_ima.tors o1' the ship descriptors. The best moments

u

C,RiG;N.AJ..P,,_O-,EiS

OF pOOR QUg, L|IY
4

for each polynomial are chosen using lillea.r regression. This research verifies the

feasibility of using moments t o interpret _t_ip photographs.

Dudani, Breeding, and ._IcGhee[6] a(Idress the problem of aircraft identification. The images of the airplanes are bine_trized and moment invariants are extracted

from the image. They preproc_'ss the two-dimensional binary image of the threedimensional aircraft, algol extract a clean silhouette and its corresponding boundary.

The algorithm employed is orie,_tation invariant. The dimensionality of the feature

vector is kept as tow as possible aud is shown to be invariant to translation in the

plane normal to the optical a×i._. The mo,,_ent iL_variants employed are the Hu invariants divided by a power of the ractius of gy_ation. They calculate two sets of

moments, one for the silhouette a,_cl one. i'(,, the boundary. The boundary moments

are found to contain a lal'ge amc, unt of inl'c,mation on the high frequency content of

the image. To identify the images they c,'e_,ted a recognizer that consisted of 3,000

live images of six types of aircrafts. Th,'s," samples are obtained by imaging each

aircraft at various orientations. They the,_ map the feature space to a space defined

by 'she set of eige,_vectors corresponding t_, the training sample covariance matrix.

The set of feature compone,_ts is ordered according to the information content. Two

types of decision rules are empIoyed to clas-ify unknown images, Bayes decision rule

and the distance-weighted k-nearest neigl_bor algorit, hm. The results of the algorithms are compared to the decisions m_,,l,' by human observers. Both algorithms

outperfo,'m tlhe humau observers, but ea(l, computer decision took thirty seconds

whereas the human observers take betwee,, ten and fifteen seconds. The algorithm

achieves reasonable accuracy i_ estimati,,- the aircrafts inclination. The errors are

typically between five and ten degrees.

Teague[T] a,:ldresses the issue of classit'ying and manipulating optical information by utilizing moments. He s,tmmarizes the properties of the lower order geometric moments. The' merits of Zer,,ike mom,_,,rs are addressed in relation to rotational

m

[]

i

B

I

m

|

I

m

J

!

m

B

m

M

g

m

m

W

o

ORIGINAL PAGE !.S

OF POOR QUALITY

m

I

l
w

5

invariance and optimal reconst,-uction of an image. It is also shown that Zernike

moments can be easily derived from the geometric moments. He demonstrates the

advantage of using the Orthogoaal moments in image reconstruction.

Wong and Hall[S] use geometric nt_,nent invariants to match radar images

to their corresponding optical images. B_cause the invariants are calculated for

continuous images these mome,_ts are not strictly invariant for digital images. The

amount of discrepancy is a fm_ction oF tl,e amount of the scale, translation and

rotation change. According to their data, _'easonably good results can be obtained

for rotations up to forty-five degrees and s,'ale changes of less than a factor of two.

They designed a hierarchical s'arch tech_iclue to match the radar to the optical

scenes. This scheme consists of extracting a structural set of images, both radar

and optical, which are of decreasing size and resolution. The match sequence starts

with the lower resolution images. A t.hresholding algorithm and decision rule is

utilized to guide the search from a lower resolution level to a higher resolution level.

The rules are selected to find the most promising locations at each level. Only

these areas are tested at the next higher t'osoltttion. A product correlator is used to

match the invariant moments o( the radar _ubimages to their corresponding optical

subimages.

Boyce and Hossack[9] con>truct t'ear_l_'e vectors of arbitrary order while maintaining the significance of the higher order components of the feature vector. The

features are Zernike moments and the rc,r_tional moments. Reconstruction of the

images based upon a finite number of Z_,rt_iI<e moments is discussed. The invariants

used in the feature vector are r,,tational n_oments. The transformation is invariant

to scale, intensity, rotations, and translalio_. The goal is to create features that are

independent and are of approxi_nately ecl_la{ orders to magnitude. This insures that

the information content is not overly sen.,itive to noise. The rotational moments

are used to identi[y the image a,xd the Zer,_ike moments are used to reconstruct the

ORIOJN_, ,-.

OF POOR QUaLiTY
image.

Khotanzad and Hong[iO] describe new rotationatly invariant features using

Zernike moments, and a systema.tic method to select the desired number of features.

This is accomplished bv evaluating the discrimination power of the information content of the ith ordered features of different classes. The patterns are grouped into

pairs. The pairs are subsec[uenIly rotationally aligned, and the Hamming distance

of the information content of the pair is t.aken. A cumulative measur¢of the Hamming distance is obtained, and this is divided by the total number of pixels. This

value is divided by one more tha,_ the feat ure number to provide a measure of the

discrimination power. \\'hen tllis discrimi_Lation power exceeds a preset threshold

then the number of features ne_'ded is l<i,own for the pair. The maximum value of

all the pairs is taken a.s the nuntber of feat_res needed for the given patterns.

1.3 Author's contribution

tt is necessary to identify Ihe positio_ and orientation of the links of a robotic

manipulator (PUMA 560). To a ccomplisl_ this task several fiducial marks will be

placed upon each link. What, r_:mains is r,_ identify each fiducial mark (a pattern

recognition probt_m) and r.o locate a poit,1 associated with each link (the centroid).

The first portioil of the problem consists ,ff designing an adequate number of simple

fiduciaI marks. This is done Io label the, links sufficiently and to facilitate the

extraction of recognizable fea turos undor ct,,tditions of low resolution and perspective

or orthogonal projection.

The marks employed are d,:,signed lro,n simple shapes - such as circles, squares,

and ectuilateral triangles. Since it is necess;_ry to generate a large number of marks

from these basic shapes, the idea of nesting _hapes within shapes is introduced. Each

composite pattern is designed s,_ch that each interior shape is completely contained

in its parent shape, and each interior st,_l>e has a grey level intensity value that

m

l

m

m

m

m

m

m

m

m

[]

m

m

m

I

m

[]

m

m

[]

J

m

m

m

m -
mJ_

w

!

i

W

contrasts with its parent shape. Using this methodology and two level of nesting, it

is possible to generate twenty seven unique fiducial marks.

Since the twenty seven generated fiducial marks are composites of the three

basic shapes, the extraction of _lle borders of each of the shapes contained within

the mark reduces the recognition problem from one of extracting the features from

twenty seven unique patterns to that of extracting features of three shapes. Once

the borders of each of the interior shapes a re identified, the results are combined to

yield the correct identification of the mark.

Moments are e×tracted f_om each of the borders to determine whether they

are reliable [eatul'es. Sitice the momenls are relatively simple to calculate, it is

of interest to determine if they can be _>,'d to identify the shapes in binary, low

resolution, perspective distorted images, ll[s also of interest to determine whether

the normalized moments of orders two ,rod three can be used to accomplish this

recognition problem.

Features based on tl]e &-s curves ot ,he boundary are also used in this stud),.

In particular, the measures of curvature obtained from these functions were used

as features. These curvature m_.asures a.re essentially local feature descriptors, and

therefore are more susceptible to noisy botder extractions and quantization eff'ects.

It is of interest to deter'mine how these te_1 ,_t'es perform under poor image conditions.

w

_=_

ill

---- T

m

u

i ;

OF PO0}_ QU/_LI'pf
z

m

i

_ CHAPTER 2

i: .....

MATHEMATICAL BACKGROUND

2.1 Rotation Matrices In Three-Dimensional Space

In many vision and or robotics applications, it is convenient to represent rotations of bodies or points around arbitrary axes in a convenient matrix form. Following [12], consider the derivation of the rotation matrix for rotations about the

x-, y-, and z-axes (figure 2.1).

A convenie_t way to view this rotalion is to consider two coordinate systems,

XYZ and UV\V ceLltered at the" origin aLacl initially coincident,.

Consider now a point P in r.l_is three-climensional space. It has a representation

in each of the coordinate syst.ems denoted by

Pit,

P_,

Cl'D fl

PZ ._

The point, P is a ssunled to be rigidly attached to the UVW system. The goal is to

find a rotation matrix that represents the _'otation of the UV_V coordinate system

and the point P e_bout the XYZ coordi_,e,I,' system.

The point P_,_._ can be rept'esented _._ a linear combination of the basis vectors

of the UVW system.

(2.1)

To obtain the real)ping of P onto each of tl_e basis vectors of the XYZ axes the dot

product of P is taken wid_ resl_ect to r],, above basis vector. The results are as

follows:

P_.- i.roP = i,.. i.P. + ir • j,_Pv -t- i_, • k,_P_, (2.z)

pt_ -- j, . P = j._ . i.P,, + jy . j,P_ + jv , k_P_. (2.3)

=

[]

II

Z

[]

m

m

!

u

I

B

I

m

i

g

m
-- 9

m

v

w

_x

w

m

i

w

V

_ Y

r

Figure 2.1: U_'W and XYZ Coordinate Systems

m
l0

X

0

Y

m

z

EM

m

U

m

i

m

m

m

I

Figure 2.2: Rotation of the UVW coordinate system about the x axis

P: = k: • P = k. • i,,P,, + k_-• j_P,, +k_. • k_P_,.

This can be expressed in mat.rix form as

.,

P_ = .iy,i= .i:,.*j, j_,k_, P_

P: l<:oi_, l<.oj,, k.*k,,, P,

(._..4)

Keeping in mind that any rotation can 17,, achieved by successive rotations about

each of the three axes in the XYZ systen_, all that needs to be done is to obtain

a matrix representation of rotations abc,_r each of the coordinate axes and then

multiply the three matrices to obtain a ,'omposite rotation matrix. A rotation

around the x axis by an angle o leaves tl,e i_ axes fixed in relationship to the XYZ

coordinate system (figure 2.2). Since th,' i. axis is coincident with the i_ axes,

and the j,. and k,,. are rol.ated by an a_gte o with respect to the jy and lq axes

m

!m

m

m

I

z

I

E

=

!

m

I

i

OF POOR QUALIFY

m

I
-- ll

i

w

respectively, the following rotation matrix is obtained

t 0 0

I .

The same procedure is followed rot rotations about the y-axis to obtain the following

matrix:

Ry,O

\

coso 0 sin(3

0 1 0 J •

sin<5 0 cos_b

Rotation about the z-axis is represented by:

R_p =

cos0 --sin_) 0 /

sin_) cos& 0

0 0 1

A composite rotation ma.trix is obtained by multiplying the matrices together.

Since matrix muplication is not con-u-nutative, the order of multiplication is imporrant. For example, if' one wanted to obt_,in the composite rotation matrix for a

rotation about the z-axis by t). followed l_v a. rotation about the y-axis by _, and

then a rotation about the x-axis by o. tl_e composite rotation matrix would be:

R = R,:,_,R>,.,R:.e. where R=

/1o0 cosa -sina0//cos 0 0 [ 0

0 sinc_ cosa sino 0 cos

cos8 -sin8 0

sin 0 cos 8 0

0 0 1

To represent the rotated 1,oint P,_.,.. in terms of the XYZ coordinate system,

it is premultiplied 1)3 the composite rot_t_i_,n matrix.

P_

P:

&

= Ft p_

P_,

• _ _,j,-d_ .... ,, - ,-,

OF POOR QUALITY
Y

_ PO

Figure 2.3: Pinhole Camera Model

2.2 Perspective Transformation

12

Following [13] the perspective projecl ive transformation for a camera is modeled by a pinhole camera. This model maps points from a three-dimensional world

: SPaCe into a two-dimensional image plane. It is initially assumed that the coordinate

systems for the image points ave coincid('n_ and centered in the image plane. This

is shown in figure 2.3.

From the above, it is readilv observe, l that any imaged point lies on the plane

connecting the object, point to the center o[" the projection. Using this observation,

a relationship belween the imaged point a,,d the object point is obtained:

/,'( P_ - P_i = (PC - Po), (2.5)

0(0/

0 - Yo

f 20

_, - 0 (z.6)

0 f

!

m

U

!

M

i

m

[]

|

[]

m

U

m

U

I

m

a

I

m

I
13

m

L:Vi = -Yo "

f - :o

Solving for image points i_l terms of _bject points, the following is obtained

Solving for k, it. is found tha.t

aYi _ _,

,]' -- _'0

k= _-Z-7--.

finally, solving Lot"the image points il, terms of object points and focal length,

.f,l:0

Xi -- j. -- -'-0

.lvo

yi - .f _ Zo"

2.3 Homogenous Coordinates

The use of homogetteous coorclina.te: is an extremely useful tool for dealing

with coordinate t.ransforma.tions. They p)'ovide an ef_cient matrtix form for the

representation of a combination of perspective transformations, rotations, about the

x, y, or z axis, scale changes, aud translath)ns. As a result the use of homogeneous

coordinate extends to the field o[ comput.,, graphics, robotics, and computer vision.

What follows is a brief introduction to tl)(-' topic.

Homogeneous coordinates essentially t.ransform a nxl vector into a (n+l) xl

vector. This is accomplished by multiplyit,g each of the n elements of the origanal

vector by a const_nt scale factor, denoted l,y w. These scaled quantities become the

the following is obtained:
14

first n elements of the new vector. The (n + t) position of the new Vector is occupied

by the scale factor. This concept can be clarified using the following example. Given

a point in three dimensional cartesian space, denoted by the vector,

Z '

The homogeneous representation ot tfds point would be denoted by

I 7 ;t _

Z ,'1"

?J" j

It is readily observed that a transfot'mation from homogeneous coordinates

back to the original vector space is accomplished by dividing the first n elements

of the homogeneous coordinate rector. An example might prove useful in clarifying

the transformation. Given a homogeneous coordinate vector

f

I,

\,//

The cartesian vector is t'eI,resented as

_t r

\ 4

The above concel)t will prove to be extremely useful in the analysis of coordinate transformations.

z

m

m

m

|

i

i

I

B

m

m

m

[]

B

I

m

==

l

m

i

B

M

L_

m

i

[]
w

15

= :

u

w

B

m

n

I

w

2.4 Coordinate Transformations Using Homogeneous Coordinates

A homogeneous transformation ma.lri× is defined as an nxn matrix that maps

an n dimensional homogeneous vector and transforms it into another homogeneous

vector. In the case of a _x4 _raasformation matrix, a 4xl homogeneous vector

in one coordinate system is mapped into a 4xl homogeneous vector in another

coordinate system.

For the special case of th,ee-dimensional vector manipulations, the homogeneous transformation matrix can be subdivided into four distinct operations: roration, translation, scMing, and perspectiv,, transformation. Combinations of these

transformations can be obtained by multi/flying the matrices of the component transformations.

The rotational transformation can b_. represented as

I R_I R_., R13

R-n R_., R_.3

R=

R3_ 1{3., R33

0 0 0

0

0

0

1

where R is a d_ree dimensional con,l,osite rotation matrix.

The translation transformation is delined as

/ 1000P 00° t c, P:

A scale transformation is represent,',t as

/,:_- 0 0 0

0 /% 0 0

0 0 k: 0

0 0 0 l

m
16

where/c_, k_, and /,:: are scalar factors in _l_e x, y, and z directions respectively.

For the case. of a perspecl ire transt'ot'mation using a pin hole camera model

and back projection, the homogeneous trat_sformation matrix can be represented in

two forms.

f,t ooo _ oo

o fo o

o o f o

-1 0 0 fj

typically, the latter form is employed.

1 0

0 1 0 0

Of'

0 0 1 0

-_ 0 0 1

2.5 Geometric 7Vloments

Moments have been ut.ilized in a wide variety of applications ranging from

aircraft to character ident.ification. They at'e relatively simple to compute and can

be made inva.riant to rotation, scale, and r.r_mslation. They are one of a general class

of shape descriptors. In tlle presentation tl_at follows the two-dimensional moments

are analyzed.

Given a piecewise continuous irradia_ce function, denoted by f(x,y), the (p+q)

ordered mdmengs are

/_ ,._, j/'X

,.,,., = ,'",Ff (z. g) dz dy , (2.7)

.'_ ' X

p,q = 0, 1,2 .....

It should 1)c noted that. t l_e moment sequence mvq is uniquely determined by

the irradiance function f(x.y) given that f(×.y) has nonzero values in a finite portion

of the plane. As a cotlsequenc(', the funcl ion f(x,y) is uniquely determined by its

moment sequence' my, _. To haw. utility in pattern recognition, moments should be

invariant to parallel t.ranslations, rotations in the plane normal to the optical axis,

and scaling.

OF-POOR QU_d-ITY

7_

II

i

E

i

[]

mm

i

il

i

m

i

il '

II

I

II
D

u

17

2.6 Central Moments

It is possible to maI<e the geometric moments invariant to parallel translation. This property is obtained I)y transforming the geometric moments into central

moments. These central moments are defined as

where

#pq = ''_' *L :_(,r -,v)v(t,r - o)qf(x, y)d(z - _)d(y - _2), (2.8)

.3= ,,,,o/,,oo..,) = mo,/moo. (2.9)

The translation invariance o[" th,' central liniments is easily shown consider the mapping

.r/=.r + h (2.10)

y_= ,rj+ _: (2.11)

which transforms the nonzero region A of f(x,y), into A/. The central moments of

AI are

IAl .a,t

where

Since

and

(2.12)

.-_1 .= itTllo/7illoo. /11 -- r111ol/,172100 , (2.13)

m/0, = n,,n + k, (2.14)

mira = ';'lo + h, (2.15)

3[Ioo = M'oo, (2.16)

substitution into 2.12 yields "2.8.

The central moments can be represe_ted in terms of the ordinary moments.

,t,,,, = (,r- :,')"(y - 9)vf(.r,y)dzdy (2.17)

ORIG)N_!L P,_.GE _

OF POOR Q;'AklTY
18

#pq = [ P

q

.-i : p-il ('q j

j=O :

Combining summations

/.tpq = [ P q

×' i=0 j=0 i j

( -2 )P-i(-_)_-J x_yJ]f ( x, y )dxdy

Interchanging summations and integrals

_',_= E _ (-_) "-'(-.°)q-j

/=0 j=0 i j ,2 _,_

(2._s)

From equation '2.7 and ecluatiou 2.20 it i., clear that

(2.19)

x'yJ f(x,y)dxdy (2.20)

_,._= _ S (-._),-'(-_)_-JM, j. (2.21)

i=o .i=o i j

2.7 Algebraic Invariants

Algebraic invariants have surfaced it, the works of Lagrange and were rediscovered in the works of Gauss. but neitlwr of these men decided to develop their

observations into a formal theory. [t was n(,t until Boole, Cayley, and Sytvester that

the study of the theory of a[gel)raic invariants flourished.

Hu is usually credited witlt the application of algebraic invariant theory to the

formulation of rotation aud scale invariaz_l functions of moments. The derivation

that follows is credited to him [t].

Giveu a binary algebraic form of u alld v expressed as

= (a(p_i),i)u v . (2.22)

or using the Cayley notation as

f = (c,,,,,:0,.,-l,_: a_.,,__'.o_)(_,,_')_. (2.23)

m

M

B

g

[]

[]

l

D

|

!

m

i

I

m

m

m

B

m

I

g

=

I
19

A homogeneous polynomiM of the "'a" coefficients is an algebraic invariant of

weight w, if

I(c, o.... = (2.24)

where a%o,..., a/0p are the coefficients obr, ained from substituting the following general af_ne transformation into the original algebraic binary form.

[l= l['t. (2.25)

_" 8 ,5 vl

and A is the determinant of th," linear transformation

± = et; -3-,f # O. (2.26)

If the weight of the invaria.ut is zero, il is an absolute invariant; otherwise it is

a relative invariant. There exist, certain atfine transformations that allow A to be

something other than the cleternfinant of d_e transformation. These transformations

are useful in deriving the necessnry moment invariants. It is also useful to introduce

another pair of variables, x and y, and subject them to the transformation

['1t ]Ixl = . (2.27)

u/ _ ,5 y

Transformation 2.2.5 is re[erred to as the F,mtragredient transformation, and transformation •2.27 is referred to as the cogredien_ transformation. The eight variables

x, y, u, v, ,r/. y/, ,L and _'/share the invariaut relationship

,r+ v!j = v,'.r,' = v/yr. (2.28)

To apply t.he t,heorv of algebraic inv_riants to moments, it is necessary t,o define

an algebraic binary form which has as ir.._ ,oef-ficients the moments of order p. One

such function is the moment geuei:ating fu,_ction which is defined as

.1[,,.,. = ___ ..-5"(v.,' + vy)Pf(x,y)dxdy. (2.29)

#=o P"
20

Interchanging integration and ,_urrunatiol_ In'oduces

M,,,_, -- _._Ll /×[ ,, z'P-iyiuP-%i]f(x,y)dxdy. (2.30)

p=o P? '_ "-'_ -o p - i

Equation 2.30 is equivalent to

p=t, _ (u._o,.... Uo_)( u ,v)'. (2.31)

By combining equations ).....95, 9.27, and ")') _._9 the following is obtained:

3[/(v/. v/)= /'_' "/_: _-_ _(./_'/+ vzy/)Pf/(x/,y/)_Tjldz/dyt

• :': ×' p=O P[

(2.32)

where J is the jacobian of tt'a,_sforn_atio,, 2.27, fI(xt, U) is equal to f(x,y) and

Mt(ul,v¢) is the moment generating func_ic,n of the transformation. Sin&

p%q = L 72(.rl)_'( q/)qJ'(xl, y/)dxtdyl, (2.33)

1 _ Z(,,%o .. " U,,o,)(ut, v/)p" (2.34)

:t.p(._, _,_)= I.]-F_=o_'! '

Combining the results of "2.29. "2.30, 2.31, 2.32 and 2.34 it is shown that if the

binary algebraic [brm of order 1_has an alaebraic invariant then the pth order moments have the same invariant hut multiplied by the absolute value of the Jacobian

of the cogredient t.ransformatiol_. In other words if

[(_,I_o..... alo_) = Z'_I(a_,o.... , a0p), (2.35)

then

/(.% ..... _,%,)= l.] -X'"[(upo,. . . , uop).

Under the scale change denot.ed b\

(2.36)

(2.37)

i

U

i

m

i

B

m

m_

[]

U

i

m

m

n

[]

[]

[]

U

i

i

: U
T

v_

i

D

7:

w

=

m

7

_=

m

21

each coemcient of the binary algebraic fot'm is an invariant

at_ = a"+_apq. (2.38)

Therefore, the relative moment invariaats are muItiplied by the Jacobian of 2.37"

producing

/dl, q = aP+q+:ttpq. (2.39)

To obtain an absolute scale invariant, the value of c_ is obtained from the relationship

between the zeroth order moments.

/tlo0

o - (2,40)

_tO0

substituting 2.40 lato 2.39 ol)I ains:

tc/l'v = /_Pq (2.41)

([.tlOO) ( P"_ + I ) ( ,Lt00 ) ( _+'g'_ "k1 ) "

What follows is a derivation o t"rotational invariance. For a rotational transformation

the contragredient transforma.tion is

c - sin 0 cos 0

and the cogredie_Lt trans[\-_rmat ion is

g/ sin 0 cos 0

]I::l (2.42)

lt:l (2.43)

Since the Jacobian of the cogredient tran.,formation is equal to one, the algebraic

invariant is equivalent to the monle]lt invariant. Therefore, treating the moments

as the coefficient of the binary tbrm

!l_,0, --. •f_.>)(tL,t,)P, (2.44)

and using the following transfoHnation

,;if 1 -i v ,2 5,
22

and

_,./ = .5 t

the following relat.ions are obtained:

I tt/l ?

V/

(2.46)

l_"! = Ue -i'_, _"/--- Ve i°

Substituting 2.47. 2.46, aad 2. t5 into

(r,o ..... Io,.)(u, _)," =

(;_o.... , &_,)(L,,_),' =

([_o..... Io,,)(u. _'); =

equating like teems in 2.49 obea.ins

2.44,

(#,,,,.... ,.o.)(_, _)

(y, o,.. .,_% )( _J,vl)p

lt/,o, ... ,¢%)(Ue-i°, ve-io?

(2.47)

(2.48)

(2.49)

(2.50)

lI,,o = eir° fvo (2.51)

D_,-_.I = eiCO-el°Ip-1,1;...; (2.52)

DI,_,-I = e-i("-2)°Ii,p_l; (2.53)

[/"7' = e-i1'"[Op. (2.54)

From the identity of the first two expressi,,ns, it is clear that ]'p-_,_ is the complex

conjuga.te of I,,e_,. and

[(']--'fpO;/-tp-=:--.:,Ltp-__r,2r)( [. [)r, (,/tp-I.1;,/.tp-,3,3;...;_.,__2r_l,2r._l)(].._, ].)r ...;

(#2_-..,." _,:,.,:.,,_.,,._._: _,0_,)(t.1)']( t, -i_/' p-_-_:t

where p - 2r > 0. and

.[p/'2.p/_.= lt_,o -1-

where p is even.

_tp--4,4_, " • • , +_Op, (2.33)

m

m

m

|

|

R

m

I

t

u

I

m

g

i

m

i

I
w

23

m

and

For rotation and reflect io_l the cogredient transformation is

-"- °

y/ sinO -cosO y

(2.56)

m

II,,,, = e-'p_Io" (2.57)

II,_l.t = e-q'-2)eIl,p_t;... ; (2.58)

[/i,p-t = eq_'-")_/p_l,1; (2.59)

I6. = e;"" t,,o. (2.60)

From the above derivation Hu ol,tains six rotation invariants and one skew invariant.

They are as follows:

/-t._u+/-_o2

(_2o - _o2) 2 + 4_L_1

(_t30 -- 3/._12) 2 + (3¢z2t -- _03) 2

(/,.-,, + #_2) _ + (#:t + #o3) 2

w

(;_ao- :h,t.:)(/,:_o+/,_.:)[(;tao-'-,r._)_- 3(,,2t+ _,o3)2]+

(,;o - ,o;)[(,_o + ,.,;)_ - (,:, + ,,,;:);] + 4,,,[(,_o + ,,_)(,_._,+ _o3)]

(3/,.,,- ,o.._)(/,-_o+/,,:)[(,.,u + ,,-_)2 - 3(,,._+ ,o_)_]-

(,:_o-:3_,,:1(,:_ + ,o31[:_(_,::.. + _,_2) _- (_-,,+ _o3)2].

m

m
24

¢,

B

I

0 t 21 31 41

.<

Figure 2.4: Square and corresponding _b- s curve

2.8 ¢ - s curves

The utilization of _' - s curves is one way to characterize the shape of an image

using its boundary. It is essentially a chain coded representation of the boundary.

is the angle formed between the a reference line and the tangent to the curve, and s

is the arc length as the boundary is tra.ver_ed. It can be shown that staight lines in

an image correspond to horizot_!al lines iu _he _ - s curve and circles correspond to

straight lines with slopes ot !. The _z,-.s curve tbra closed boundary, is periodic with

a discontinuous jump [rom 2r, to 0 as t.IL,-'curve is retraced to the starting point.

Figures 2.4. 2.5. and 2.6 show the g, - s c'_lrves for a square, circle, and equilateral

triangle, respectively.

m

I

II

II

=

|

L

B

II

I

U

l

I

l

I

l

I

I
w

25

i

> $

Figure 2.5: Circle and corresponding _b- s curve

m

_:-4

_=_

i

1 21 31

Figure 2.6: Equilateral triangle and corresponding _b - s curve

_2 OF P_O_._ Q{JRLITY
i

E

l

CHAPTER 3

PROBLEM STATEMENT

The objective consists of' determining tlle position of each link of a PUMA arm

using fiducial marks. Each link should t_,, uniquely identifiable regardless of the

orientation of the arm providin_ that tl:_, link is in the field of view of the camera.

The placement of" multiple fiducial marks on the arm provides an excellent method

m

i

i

to accomplish this task. The methodology behind utilizing multiple fiducial marks

to label each link of the P U.'([A is task effici,,nt and effective. The fiducial mark itself

is a planar object o[ specified dimensions, t:_ecause of the dimensional specification,

the location of each affixed mark is known relative to the arm-centered coordinate

m

m

I

system. This reduces the original objectiw" to one of distinquishing fiducial marks

and locating an associated point..

When the marks are view,,d by the C'CD camera all the points on the fiducial

marks are subjecl ed to a perspective proje,tive transformation that maps the three

dimensional coordinates of the mark into r_vo dimensional points in the image plane.

m

I

This mapping is a noninvertil>h:' transt'or_,_tion. Therefore, any point in the image

plane can correspo::d to an in[ittite numh_'r of points, in the arm-centered coordinate

system that lie upon _he [ine co_necting lit,, in:age point, to the focus of the camera.

However, it is possible to locate the a:'m-c_':_ rered coordinates of the mark by utilizing

two calibrated cameras. If an algorithm is employed to locate a particular point

in both image pla.:Les the, two loca.tion_ c_,n be used in a triangulation algorithm

to identify the lo,:ation of the i)oint in _I_,' arm-centered coordinate system. The

triangulation algorithn: is straightforwar, t. Therefore, it will not be addressed any

further.

If the arm-centered coordinate sysr,_n is aligned with the image coordinate

system, the l)e:'spoctive tra|:sforn:al;ion w(,,tld take the form given in Chapter Two.

m

mM

m

I

m

m

i

I

GR!_N.RL P&CE iS =

OF POOR QUALITY ----

i

=_

aa

m
=

i

w

m

B

27

For the two coordinate syst, em._ to be a.[igned, it is necessary to align the x-axis

and y-axis of the, arm-centered system with the u-axis and v-axis of the image,

respectively. Since this is generally not the case, it is necessary to pre-multiply

the arm-centered coordinates by a compo,,ite rotation and translation matrix that

transforms the original coordi_ates to coordinates relative to a three-dimensional

coordinate system that has its origin aligm'd with the image plane origin, its x-axis

aligned with the u-axis, its y-axis aligned with the v-axis, and its z-axis aligned

with the optical axis. Once the. linear ttansformation is achieved the perspective

l:ransformation given in Chapt_'r Two is vatid. Since the cameras are calibrated

and the transformation is known, obtailTing the coordinates of the point in the

arm-centered coordinate s\,sten_ is accomplished by post-multplying the coordinates

obtained via triangulation with t.tae inverse of the transformation matrix. Therefore,

it is evident that the recognitio_ of the syslem of marks and their associated points

determines the position and orientation of lhe arm. The main emphasis of this work

is the design and recognition of the fiducie, I marks.

The imaging of an object _Lsing a CIC'I) camera produces a substantial amount

of distortion. Perspective tran_forma.tio_, quantization and sampling produce the

most distortion, but. the pincushion and barre[ effect also contribute to the degradation of the object represeutatio_,. As a cow,sequence, it is necessary to design marks

and feature extraction algorith_as that ace insensitive to these effects. Perspective

distortion of a mark occurs when there a.r,, points in the mark that have different

optical axis coordinate values. [r is essenIi_lly the converging railroad effect. It can

transform squares into trapezoids and ,:ir,tes into distorted ellipses. Because it is

proportional to tl_e izlverse of the dispatch,' along the optical axis, it is difficult to

account for without an apl>roxintate knowledge of the position and orientation of

the mark. When a[I _he point._ within a ,,lark lie in a plane perpendicular to the

optical axis only a scale change results. 'l'herefore, if successive images are taken

i

i

OF POON QUALITY
28

of a mark that is ont\" translat,'d in the ,lirection parallel to the optical axis, the

images only differ by a scale L'actor.

Representation of a conti,,uous obj,_c_ by a finite number of pixels inherently

produces an inaccurate represe,_tation.._\s the ratio of the image size to pixel size

decreases, the image distortioa increases. If the ratio of image size to pixel size

becomes too srnatl, the image b,_comes m_r,_cognizable. This effect is similiar to the

aliasing effect tbr one-dimensio,_al periodic signals,

For the particular robotic system employed in this work, the mark will be no

greater than two meters away fr,_m the ca_era.. The resolution of the frame grabber

is 512x480 pixels and the field of view is approximately two square meters. This

produces a pixel resolution of approxitnalely two millimeters when the object is

two meters away from ehe image plane. "[his implies that the marks should be as

large as possible to compensa.te for the large pixel size at that distance, but there

is a limitatioa on the size of the pixets. This limitation is caused by the link size.

Each link has six sides and at t,'a.st four of these sides can be used to affix a mark.

The smallest side of a link is apl)roximat,4v 3.:5 inches. Therefore, this is the upper

bound of the size of the fi,lucial mark.

m

m

i

i

[]

i

i

i

II

!

i

|

|

|

B

E

I

m

I

i

=

[]

I

m

i

i

m

: Ill
i

u

m

w

n

CHAPTER 4

FIDUCIAL MARK IDENTIFICATION

The problem consists of generating a sufl:icient number of fiducial marks to label the

robot arm reqardless of its posi_ioa and orientation in space and the background it

is placed upon.

4.1 Design of the Fiducial Marks

It was decided r_hae mark. based ul)¢,a simple geometric figures might aid in

the identification process. In any recogniT i_,n process involving several patterns it is

necessary to extract a set o[ feat _tres that wlten utilized in a decision making function

will yield a unique value tbr each of the patterns. If this criterion is not satisfied

then two or more of the patterns cannot be distinquished. For this reason the

circle, square, and equilateral tciangle seemed like excellent candidates for flducial

marks. They possess features readily extracted and uniquely determined. Some of

the features that can be extracled are ,no,nent invariants, contour signatures, and

compactness nlea_ttres.

Another cril erion that nee, Is to be a,ld ressed is the size restriction of the marks.

The marks are restricted to a :1.5 inch box. This restriction exists due to the fact

the marks have to be placed on the arm. 1-:ach mark must fit on each face of every

link.

Another criterion tltat ne_,clS to be a,ldressed is the quantity of unique marks

used to label che Iial<s of the arm. The' tl,,-ee basic shapes must generate at least

twenty-seven unique COml)Os[te _hapes ro _,ccomplish the labeling task. This can be

accomplished by aesting shape_ within ,1her shapes. The sizes of the shapes are

chosen to maximize the size of lhe inner sl_a.pe while insuring that there is at least

a three pixet wide border separating the shapes. The inner shape size is maximized

2!)

OF POOR Q|J_kiTg
i

3O

to minimize the distortion due _o digitizin<. As the ratio of the shape size to pixel

== =4 =7=

size is decreased the si'tapi_ Become increasingly more difficult to distinquish. All

the shapes designed consist of _, black sl_ape within a white shape within a black

shape within a white rectangular border. This configuration generates twenty-seven

unique composite figures.

a_. z . ....

4.2 Segmentation of the Marks from the Background

For the algorithm to succeed, it is necessary to segment the mark from its

surroundings. The placement of the shapes within a white rectangular region enables

the composite patterns to remain intact. [f the outer white rectangular region is

not present and the marks are placed up,,n a black background, the outer figure

might be unrecoverable in the image. It is possible for the outer white rectangular

region to be distorted by its background: but this is of no consequence because the

algorithm only searches tbr a white bot,lec and doesn't try to classify the shape.

This algorithm is extremely efficient for backgrounds with a relatively small number

of white regions. After a whit.e region is located, the algorithm searches the inner

region to determit,e the presence of a mark.

4.3 Extracting the Outer, Inner, and Middle Borders

Extraction of each o[' the borders is vitally important in obtaining a reliable

feature space. If an error is produced in rim border extraction process, the subsequent feature space calculations will yield i lta.ccurate results. In general, the method

chosen to extract the borcler depencls Ul),_l, the border definition. For a continuous

image a boundar\ point is usually defined as follows

Definition 1 .4 bo.u_da,'g po,,t o/ a .set _ a point having the property that every

neighborhood o]" i! co,_tain.e poi,,ts in the .s, t and points not in the set.

m

m

i

m

I

|

__=

m

[]

D

m

[]

|

[]

i

m

[]

[]

m

M

[]

I

m

j =

m
u

31

u

m

w

_A

--=

I

m

This definition usually reL'ers to the set of ],oints within some connected region and

the set of points outside the region, where, each region consists of an infinite number

of points, and the neighborhood of each poiat is infinite. For a discrete image every

region contains an finite set of points or pixels and each neighborhood consists of at

most eight pi×els. Because of this distinction, it is necessary to modify the above

definition. Before a definition of the border pixel for a discrete image is given, it is

necessary to define two related t.erms. Ttwse terms are the four-neighbors and the

eight-neighbors of a pixet.

Definition 2 G'i_'e_ o pi.r_t P c,t coordi,,,_es (a,.g), the fo'ur-neighbors of the pizel

are give,, b_ t/,_ j,i.,'e/._w#/, t/,_ _oo,'di,,<,t_.. 5>_,u.), (._,u+U, (_+l,v), and (z,>l).

Definition 3 Gi_'en a pi:rel P ,zt coordi,,tes (.v,_), the eight-neighbors of the pizeI

are given by the .four-neighbor.s of the pi:rr/ a_zd the pixeIs with the additional coordinates (z-l,g+t). (iz'÷l,g+t). (.r÷t,g-l). and (z-l,y-1).

Now, the definition of a border pixe[ can proceed.

Definition 4 .4 pi.rel P tit coo,di_ate.: D..,/) i.s a border pizel if and only if P has at

least two eigh.t-_Teighbors i_ the .ame .'.,el ,.. P. and P does not have more than three

four-neighbors i_ the .same .set ,_s P, wh, ,, the .set P col_tains all of the the pixeIs

that have intemsilies that are al/owed to 1, connected.

For binary images the images ave divide, l into two sets, pixels with a value of one

and pixels with a value of zero.

To ext.ract the boundary of each slta_t_e, the algorithm searches for a boundary

candidate. Once a cax_didate is found it se;,rches the eight-neighbors of this pixel in

a clockwise fashion for another border ca,_didate. If another candidate is found it

searches the eight-neighbors of this pixel. II continues this search until it reaches the

first border element, lf at any l,oint it ,'a_,aot find another border pixe[, it returns

ORIGfN._,LF,:_,¢E ,s

OF POOR QUALITY
i

32

to the previous pixel and searct,es the remaining eight-neighbors. If the algorithm

backtracks to the starting point and ca,,not find any border elements among the

remaining eight-neighbors it ret urns and n_oves on to the other starting points. If

no borders are found ill the adnlissable r,',gion a failed flag is returned.

Once the border from an ez_closing shape is obtained, the algorithm restricts its

search region to tile region enclosed by t l_,, border and searches for border elements

that belong to the opposite inteusity set of the enclosing border.

4.4 Monqents as Feature Parameters

Moments and functiolls o[ moment_ have been utilized as pattern features in

a number of applications involving the r,'cognition of planar objects. Functions of

moments can be utilized t.o obtain fea.tur_.s which are invariant to scale, rotation

and translation. They are considered to l_,_ reliable features if they are insensitive

to image degrading effects such as quant.iz_,tion, and sampling. Moments are global

descriptors which characterize t.lLe distribut ion of the points of an image. One of the

major drawbacks of using morn,mrs is t lw large number of multiplications involved

in the comp,ttat.ional process. lhe straigl_, forward method of calculating moments

requires 10.",IN m,Lltiplicatioas [or an :_[ >,N image. Unless the system has a dedicated

math coprocessor, the extractio_ of t.hes,' I,.atures in real time is infeasible. However,

there have been several fast alg,,rithms devised for this problem.

4.4.1 Moments of a Generalized Rectangle

Consider t.h__ generalized rectangle r_'m'esented by Figure

width. T(al) is tl_e l,"llgth, a,ld T is th¢" .ir,_itla.r3. scale factor.

7

in the u-v plane ropresent_'d b.v figure 4.2

The central moments of tl,e regio,_ are denoted as follows:

1<_,.,= /_,/?:,.rPyTdxdy

qt • 7 +1

: 2 i "_ 5

4.1 where al is the

Consider the region

(4.1)

m

m

i

I

[]

mm

z

mm

m

I

i

=

i

i

l

I

_m

mm

m

[] ,

!

m

mm
-- 33

!

L

_z

m

Figure 4.1:

Ta

Generalized Rectangle

m

w

(Ta , a )

U

m

r_

i

i

m

m

Figure 4.2: Rectangular region in the u-v plane
m

34

m

iI (.p!l #,,,,-- a [p---£-i-IT_Ja,]Yqdy (4.2) --==

Z

r- I:',:_ iF-." I,-1 (4.3) m

t,r,.,,_= tp+ 1 b-/.,,Jtq + 11-,:,1,

m

m

(_>,,),,+1 aT-,-1 -aF' []

p-v 1 ][q + 1 q + 1] (4.4)

m

,"p,,= [(Tat ),,+l

p+l

1

Ftp,,= (_,+ t)(q + l)

[(Tol)"÷'(L- (-1?+l)][aF'(1- (-l)q+')] (4.5)

1 [7"("+_')q(lP+'"+")][(1 -(-1)P+1)(1- (-1)q+')] (4.6)

"_'' = (t,+ t)(q+ 1)

It can be readily seen that: if either , or q is odd then #pq = 0. If p and q is

even then #pq is given by

m

==

m

m

m

1 [4T(p+l)a{p+q+2)]"

P"" = (1, + t)(q + t

(4.7)

To calculate' .V.,,,t. the scal¢' normali_',[ central moments, the following is used

Ytv,t [.1 0 _,

"-_+1 "

Using tile results of _qualion 4.8

7,(-_.5a_ I

lit,. _ --- _._ _

4( : '(_, + _)(q + 1)

(4.9)

(4.10)

(4.11)

[]

m

m

m

n

i

m

m

m

i i

I

i

w

[]
-- 35

The first rotationally invat'iant mom_'nt, _l, is given by =

n

w where q2o is

_. = rl..,u+ r/e2, (4.12)

and qo'2is

T

172o= _ (4.13)

u

As a result.

l (4.14)

r/0.2 t2T

n :

i

_' + 1/T (4.15)

¢' - t2

For the special case of a. square, T=I,

¢t = I/6,

For the case where T=2.

o, = .,/24

the second rot.ationatly invariant, molaent &2 is given by

o., = (r/.,o- ,j,,,)_"+ 471_l.

Since q11=0.

m

_=

m

(T- l/T) -_ (4.16)

o2 - t "2a

It is clear from equations 4.15 and 4,16 that the moment function q_-_ is invariant

for all rectangles.

m
36

4.4.2 Moment Calculations for a Generalized Ellipse

The calculation of the moments of a generalized ellipse is sufficient to obtain

the moments of a circle. It was decided to extract these features. This extraction

may prove to be useful in tile aaalysis of the effects of the distortion of a circle

introduced by orthogonal projection. If tll_" ellipse is represented by Figure 4.3, the

central moments of the region under the cl_ange of variables

z = Trl cos 0

g

m

!

II

m

and

y - 7'_qn 0

is denoted by

lq,,_ = . . (Tr cos 0)P(r sin O)¢TrdrdO.

Orouping r's and extra cthlg the scale factor produces

Cq,,1= (T;'+I ) //'/0,.t,,+q+l) cos p sin q OdvdO

The first iterated integration produces

/_ p,l =

_j_Ip+l)_. (p+'I''''! C 2r

'l / cos 7'sin _0d0

(p+q +'2i .

/0

The evaluation of the second it,.t'ated int,?ural produces

T/_+zl"l/'+'r+:lr (t_- 1)(1_- :_t... 3 - t

]f

_zpq (p+,/+2) t(_,+q,_(p+q_ .,...(p+2)_

for p and q even. and zero othe_'wige.

Substitutioll of 1)=2 and q--0 into _.q,lation

(q-t)...3.1

q-.-4.2

4.t7 yields

7"3p4

171", ,u..,o-

.tSubstitution of p=0 aad q=2 illtoequalio,_ 4.17yields

/'r_ _

/tO2 -- ,_ 4

]2,-r (4.z7)

m

m

==

i

R

I

Z

Ii

I

J

I

l

m

!

M

IR

; i
_" 37

m

i

=

i

U

Figure 4.3: Ellipse in the u-v plane
38

Calculation of the second order scal_" invariant moments produces

T

t]20 ---

4_

1

7]0.2 =-

_Trr

The first and second rotation, scale and 1,anslation invariant moments are

7'+ 1/T

ol - (4.18)

and

o._= IT- tlr]._. (4.19)

It is cleat" from equations 4.18 al,ct :t.19 dial the moment function 4_-¢5_ is invariant

for all ellipses.

m

Z

Ill

i

|

mm

m

I

!

4.4.3

Given the equilazeral triangle in Fig,u'e

moments are defit_ed as follows:

_VIol-nent Calculations for an Equilateral Triangle

4.4 with side length 2a, the central

= t-'''_ i_.+,-_l

"'>" .s_<,i_ J_! ...._i

Performing the first integvat.iol_ yields

-',' ,l.[t.,+ t)

,,,,_-/y - --r_,_>(p+l

Substituting for x.

for p even.

[.1 P'I --"

_1 pq

,rpy _d.r dy

--I r 2_ 1

p +t t iTii'r . 3-It:e (Y- _2a )p+ty_dy

(I' + i)3cp+l)/-' -2 .

f"+-., [9 - •

m

=

II

I

_I

U

ii

ii

!

II
-- 39

= :

u

u

L_

u

M

Figure 4.4:

V

2a / 3 .5

.5

a/3

Equilateral triangle in the u-v plane

I

m
m

4O

Using the binomial expansion.

#Pq = (p+ t)30,+t)/_ "Dr_-_ i=(, i

--ga z

.,p+l-i; - -"

9 t3-i _ ) 9qd9

Performing the second integration yields

--'2 o+I 9p+_+2-i ( _2a.iis.i. _

_" = (p+ L)_,>+,_/_.: j, TTs¥ _ - i" a_i---7" '_-r_

substituting for v.

-2 :"+_" 1 -2al_.fr 2a tp+_+.:,._ i f -a tp+q+2_it

s_,_= (_,+ 1).77,,+,_/__ i;* q+ o_ ir:_i__'_3,I_' - <Ti-m '

4.4.4 NIoments oforthogonally projected shapes

In many sitna.tions, it becomes possible to approximate the perspective projective transformation of a.n inaaging devi,- by an orthogonal transformation. One

such situation is the case when the variati,m in object point distances is negligible

with respect to tl_e object plan,' to imag,' i)laae distance. In this case the distance

of the object along the optical e,xis ma.v b,. considered fixed. For example, since

t' ,

/ ,L o

.I'%

Yi--

, -- .f

and f and zo are fixed, the t ransformatioi_ I,etween object and image points is equivalent to a scale change.

,ri --= /,'.Co

and

where k is the constant __L_

To__f "

gi = i.'.qo

This is ti_e orthograpic projection model, and it

facilitates tile de_;elol)meut o[ t_,oment t,ii_, tions for the basic shapes.

OF PO0_ QUALITY

u

I

B

n

i

i

i

|

m

m

l

m

B

I

i

!

U

i

J

IWl

m

7

il
41

w

w

=

Consider the situation wltere one of the basic shapes is arbitrarily rotated

about the object centered coordinate s vst¢-'m. This can be represented by the multiplication of the composite rota.tion mal,'ix R with each object point [XZo 9/o Z/o],

where R is given by

7"II 7'12 PI3

/"21 1'22 /''23

P31 r.y: 1"33

and ri 7 is a trigol:ornetric ['unct.ion of the rotat[on angles c_ and ¢ given in Chapter

Two. Under t.his rotation and orthogonaT i,rojection,

,r, =/,;(rll,r,', + "12P'o + T_)

:j; = _:(7"2t,rl_) + r2o.:]Io + Tv)

Given the endpoints of two parallol line segments in the object coordinate

system denoted by for line t

(_r,.u_)(:_ + _x.;:,j_+ ,.su)

and for line 2

(.r.,..fj:)(.r: + *.r, _;: + _.c).

Now if both line seglnent_ are sub j,., _ed to the same rotation and orthogonal

projection, the poiuts of line 1 Iransform i,t}o

_'(1"11.'1't + ;'12../]1 + T.- "21,°L -Jr- /'2'2Ul -{- 2-'!/) (4.20)

w

and

/,-(/'_,(.rt+ ,s.,')+ 7",.,(,,,,+ ...x:j)+ 7;. ,.,_(._',+ 6:_.')+ 7";2(y_+ ,_.Xy)+ T_,),

and those of line 2 transform into

t,'(r,,.r. + _',.:.q_ + T .... ":l.r., +/`_-'U_ + T_) (4._.1)

O_" PO;)2 QUAL{TY
42

anal

From equations 4.20 and 4.21 it, is cleat' rhat the slopes of both transformed Iine

segments are equivalent and the slope is given by

_'22A.t,, + r2z_o."

r.at A9 + rtl_.v

The line segment lengths ave given by

_/(,:, ',.,+ ,.,+_,):+ (,:,",,a+ ,',,",h _

Since under t'otation and ,,rthogonal projection, parallel line segments remain

parallel, it is evident that a square under this transformation must be converted to

a rectangle. As a vesttIt, the mo,nents of ;tt_ ort:hogonally projected square are given

by those of the generalized t'ect+t.ngle, where

T = _/'f' + ,h {4.22)

vl,._:+ &

Simitalily. rotation and orthogonal l,t'ojection of a circle produces an ellipse

and T is given by eciuatio_l 4.22.

4.4.5 Moment approximations due t.o digltizatiorl

For digital ilnages, the do,tble int%r;,tion used to define the moments is typicall)" approximat..el by douhte s,t:::mati¢,,+: and the moments are denoted as

._t .V

m_,., = _ y_ .d'yvJ'(x,.tj) (4.23)

_'----.II q--_ll

._I .v

1';..,, = _ ____,(.7"- ."'"'V - O)'.]'(.c,Y), (4.24)

,r=O _=0

where M and *" are the image ,:_lirnet:sio,t-_.

n

[]

[]

i

II

B

I

!

i

I

z

g

=

i

I

=_

lib

M

I

[]

+

II
-- 43

S

Figure 4.5: Curvature plot of an equilateral triangle

Inherent in t.his apl)roxim_L.tion is tl_e loss of strict rotational and scale invariance. For a square it is shown 1)\' Teh and ('bin [ll], that the first invariant moment

is

1 - l,/a a

6

where a. is the ratio of the S(luar_' size to th,' pixel size. It is readily observed that _51

is no longer scale inx'arianT, l_ttl depends c,,I the size of the sampling grid. The toss

of rotational and _cale invariall,e arises I_¢.cause the sampling grid is not adequate

to represent the _hapes. and as a resub ,:l_anges in orientation result in a changed

representation of the object in the image plane.

4.5 Curvature as a feature parameter

Since most il' not all o[ 11_e shape il_l*,)tmation of an image is contained in its

boundary. The use of features 1-,a.sed on ttw t-' - s curves of an image boundary seems

like an exceptabl,' method to ol,tain uni(l,z, _ features. One feature that might yield

promising results is the ctlt'\'atttt-e of the' I_,,undary.

The curvattlre of a l)ound;_t'y is clelim'd as the rate of change of ¢ with respect

0:- POOR QUALITY
44 u

d_

M

B

m

n

Figure 4.6: Curvature plot of a square

m

i

i

I

u

d_

U

[]

lit

Figure 4.7: Curvature plot of a circle

n

m jura

m

m

U

m

u

m

m

[]
w

m

u

w

to the arc length, and it cal_ be easily oblained from the representation of the _, - s

curve of the boundary of a.n inmge. Analyzing the curvature plots in Figures 4.5,

4.6, and 4.T it is readily observed that thet'e are exactly three jump discontinuities

for the triangle, four disco,_tinuities for r,he square, and no discontinuities for the

circle, and in general any quadrilateral will have four discontinuities, any triangle

will have three discontinuities, and any ellipse will have no discontinuities. This

information can be used to cliscdminate' h,,tween the three shapes even if they are

perspectively dis_orted. It' the boundary _f an image is traced and the jumps in

curvature are cot_nted, the shape will be determined. This formulation is based

on the assumption o[" a coT_tin_tous image. Since the image is not continuous, a

modification has Io be devised.

For a discrete image, the typical _: - s curve can be represented as an eight

directional chain code of the a.t_gles. This decreases the feasible angle space of an

image from infinity (in the conlinuous cas_-'i to eight, and _s will either be 1 or v/2.

As a result of the' sampling, straight lines in the actual object will not correspond

to straight lines in the chain coded _;ersion of the image boundary. The chain code

essentially links angles that form an apl,r,,ximation of the slope of the line if the

angles are averaged. If n i_ the uumber of Hnk angles averaged, the approximation

will be within

4- arctic. ( 1/n)

of the actual slop,, of Ihe lin_-'. E-,ing the ditlerence of the average of the links on both

sides of a particuta1' chain code member wilt yield an approximation of the external

angle of the shap,'..-\ thr¢'_ho[,[ can [)e us_,d to determine which values correspond

to a significant ai_gle change. \\i_h a prot,er selection of the threshold the square

and the triangle can he discrimi_mted. Tl,e <luare should have four significant angle

changes and the triangle shoukl have thre,' significant angle changes. The circle is

identified using a slightly digereut approacl,. A digital representation of a circle will

ORIGINAL P:!'_E iS

CF POOR QUALFI'Y
46

contain on average angle chaag_,s of less lhan n-,/2 radians and both the square and

triangle will contain at least, ore" exterior aztgle that is greater than or equivalent to

rr/2 radians. Therefore, counting the nund_er of angles greater than or equal to 7r/2

will determine if the object is a circle. This is assuming of course that the number

of pi,_els averaged does not exceed 1/8 ot the chain code. Of course if the sampling

grid is sufficiently coarse it will be iml)ossible to distinquish any of the shapes.

!

i

I

I

I

I

I

i

I

|

I

it

I

I

m

I

I

I

I
u

m

i

CHAPTER 5

EXPERIMENTAL SECTION

In the sections that follow a labding convem ion for the fiducial marks will be utilized.

Each mark is tabebd with a three letter code, where the first letter of the code is

the first letter in tile name of the outer ._hape, the second letter of the code is the

first letter in the flame of the ndddte shal)e, and the third letter of the code is the

first letter in the name of the i,_ner shap,:. For example, the code 'cct' corresponds

to the mark tl_at contains a circle as the, o,,ter mid middle shapes and a triangle as

the inner shape.

5.1 Simulation Results

Digital rel)resez_atioas of a. square, a. circle, and an equilateral triangle are

created. The shapes are represented initially by a finite set of points. For example,

a square would be rel)resented 1)5."its [o,r vertices. In the first series of tests, the

points are used to obtain a digital representation of tlxe shape, and features are

extracted. In l)a_ticular t.he _,,oment inv,,riants and d_e external angles changes

are extracted to xedfy t},ean_,ly_ica] res,ltls. To simulate the results of orthogonal

projection, the points are rotaled in sl)a_e and appropriately transformed. The

, 2 .

digital representation is obtaim,d, and l l,,, features are extracted. This is done to

observe the [eatule changers umler d_es_' types of transformations. What follows is

the data el)rained [ro,n these si,nulatio,,s.

The first se_ of sim_tlatio_s consist of t'otating the square and equilateral triangie in the image t_la.ne from 0 to 180 ,legrees in increments of 9 degrees. The

invariant momenl s a.ro extract e,[ at every _,rientation. This is repeated for different

scale factors (rati, of image siz," to pixel ,be). The scale factors range from 3 to 20.

The results for scNe l'_ctors of :i. 10, an,t 2,3 are shown in Tables .5.I and 5.2. Since

If

O_G,ir, i,.aL PACE I.':3

OF POOFi QUALITY
n

48

Scale Maximum _linimum

:3 0.187.500 0.[.5')788

10 0.166600 0.[649:31

20 0.166875 0.[65650

i_i leaFl

t

ti. 1836400

i_.t656439

o.1663562

standard deviation

0.01091

5.98 xl0 -4

4.34 xl0 -4

Table 5.1: First invariant monlent of'a rotated and scaled square

'Scale

3

10

20

Maximum _[inimum n,ean

0.2287390 0.173416 0.1915400

0.197430 0.18774[ 0,19279755

0.193099 0.191600 1_.i9251845

standard deviation

0.01765

2.45x10 -a

3.60x10 -4

i

Table 5.2: First invariant moment of a rotated and scaled equilateral

triangle

there is no change in the cligir..[ represe01ation of a circle undergoing rotation in

the image plane, it. is sufficient lo extract Ilte invariant moments once for each scale

factor. TSe resulls for scale faclors of 3. "5. [0.15, and 20 are shown in Table 5.3

It is clear from 'T_bles 5.1..5.2, and ,',.:; that the moment invariants for a digital

image are not stricth in\arianl, but for 1t,," larger scale factors there is a negligible

deviation bet weeJ_ the theoretical vMues a_,d the ones obtained via simulation. For

example with a scale factor of 21), the per,_',|tage error between the theoretical value

=

and the experim,_ntal value ot: 0l for 11,. square, circle, and equi=latera[ triangle

SCale ,>t

:3 .t58750

5 .159024

lO .159[20

[5 .I59136

2O .t59143

i

[]

[]

[]

nl

[]

z

i

Z

i

m

i

[]

|

i

i

Table 5.3: Fh'st invariant moment of a scaled circle

i

i
Table 5.4:

square

(degrees)

27

27

45

(degrees)

'9

27

45

O. [67588

O. 170915

0.209200

_2

0.000502

0.001510

0.016066

¢3

o.oooo0o

0.000000

0.000000

Invariant moments of a rotated and orthogonally projected

¢ (degrees) o (degrees) '"_)()027402 ¢" Ca 27 9 0.009220 0.'0"04566

27 27 0.241427 0.0276,5 0.011028

45 4.3 0.2t5370 0.031400 0.005398

Table 5.5: Invariant moments of a rotated and orthogonally projected

equilateral triangle

are 0.183, 0.0075. and 0.09 , respectively. It is also clear from the data that the

first invariant moment:s are sufficieat to distinquish the shapes obtained via this

simulation.

The next seL'ies of tests _imula_e r_,tation about the x-axis of the objectcentered coordinale s.vstem 1)v an angle of ,_ and about the y-axis of this system by

an angle _. where the values o[a and o \at'y [rotTI 9 tO 45 degrees in increments of

9 degrees. After rotation, the sltapes are _rthogonally projected, and the invariant

moments are extracted. Ta )[es 5.4 and .',.7, show some of the results. Incidentally,

because of t.he similarity betweelt the invariant moments of the circle and the square,

this table was omit t.ed.

It is cleat from Tables 5..'_ a0d 5.4 _l!a.t merely using &t as a decision criteria

yields incorrect results becaus," there ar,_ occasions when the value of ¢1 for the

orthogonally proj_-.cted shapes overlap. 1_,_ the invariant moments can still be used

to discriminate between the three shapes. For example from Tables 5.5 and 5.4,

OF POOR QUALITY
50 u

jit is readily observed that the t.hird ht\ariatlt moment is less than 10 -6 for the

square and is greater than 10 -:_ for the equilateral triangle. Similiarily for the circle,

the third inva.riant moment is less than 1()-6, This test can be used to uniquely

identify the equilateral u'iangle. To differe!ttiate between the circle and the square,

the orthogonat invariant derivecI in Chapter Four can be utilized. This invariant is

given by ¢_-o_.. For a colMnuo_ls square lhe orthogonal invariant is equivalent to _,

For the discrete representations and for a continuous circle it is equivalent r.o _.

of the circle and square, tlle deviation ft'ollt these values are a function of the scale

factor. For a scah' fact.or or thirty, the per,c,ltage error obtained from the calculation

of the orthogonal invarianI for the discrete ,'ircle and square is less than 0.3 percent,

and for a scale factor of twmtty, the percmitage error is less than 0.8 percent. As a

result, The discrimination of the three digit(ally represented shapes under orthogonal

projection can be obtained.

The Simulations that. are performe, l for the moments are repeated using the

features based on the _#,-s data. with the ltotable exception that the scale factor was

never reduced below tO. The a.tgorithln I,erformed well. Circles and squares are

always correcdy classified, and the tria_@,'s are misclassified once.

5.2 Experimental Results

A Javelin C'C'D camera a,,d Data (

grey level images of t wenty-sev,'n fiducia

_tbe frame grabber are utilized to obtain

,harks. The marks are placed at various

orientations within the field or view. l?hc.se images are subsequently thresholded

to obtain binary images. The' border_ of each shape within the fiducial marks

are extracted.-:ihc ceutroid i- obtained from the border of the outer shape and

the moment invariants and the chain cocl,.d representation of the .g, - s curve are

extracted from each of the borders.

m

i

II

m

I

m

M

[]

i

!

i

m

[]

[]

i

I

i

-- i

m

OF POOR QUALITY

i

[]
w 51

m

-:,

01 o.., ¢3

Outer Shape 0.26108,1 0.030719 0.0'0'8405

Middle shape 0.214408 0.004788 0.000631

[nner shape 0.32652.5 0.022299 0.00.5739

Table 5.6: Invariant moment calculations of flducial mark ttc

The rationale behind using the moments as features is to obtain an uncomplicated method to recognize tlte shapes, This is the reason that the approximation of the perspective transfor,na.tion by _tn orthogonal projection is utilized, the

transformation properties oF tl_,' t'norneHl s based on this simplification would make

recognition of th," shapes t'elalively sJ_t_,t,,. Tab]es 5.6, .5.7, and 5.8 contain the

moment invarianls of a few typica.1 fidu(ia[ mark images. From these tables, it

can be clearly obset'xed t.hat, ti,e calcula_,',[ moment invariants do not possess the

convenient properties associate, l with the moments of the orthogonally projected

shapes. This observation leads to conclush_a that to extract reliable features from

the moments is necessary to utilize anoth,tr methodology. One methodology is to

prescribe values [br some oF the higher or, h'r moments (higher than order two) in an

attempt to coml),'i_sale [or l:hc ,'t['ects of rl,e perspective transformation. This does

not completely compensate For lhe etTecl:, imt better results are obtained. The major problem with t l_is approach is it beco,l,.s necessary to solve nonIinear equations

to obtain the val _(-s necessary {,_ fix son_, _,f the higher order moments. This added

complication diminishes the value of _>in,_, the moments as features. As a result,

it is decided to toc, ls ou rh,, ct_a ofltah,,,l ['rot11 the ¢ - s curves to obtain reliable

feat ures.

The feature,, utiliz,,_l to identify _},' marks are based on the g,-s curves of

the boundary of each shape. t'hese prov(, to be more reliable than the moments

invariants. Two experiments at,: devised. In the first experiment, The outer shapes

OF POOR QUAL!TY
52

01 ,a_. ¢3

-Outer shape 0.1934:28 0.000019 0.000071

Middle shape 0.2298.ql 0.011057 0.000982

Inner shape 0.85724.5 0.018707 0.0.566_25:

Table 5.7: Invariant nloment calculations of fiducial mark tst

ah ¢= Ca

Outer shape 0.1824.5. _) 0.00{)161 0.000064

Middle shape 0.1.93400 0.009736 0.000233

Inner shape 0.3t0022 0.02,5384 0.018699

Table 5.8: Invariant moment calculations of fiducial mark csc

are identified i00 l)erceat of tile Time, t h(" _l_idclle shapes are identified 96.3 percent of

=

the time, and the inner shapes are never i(h,ntified. The algorithm fails when trying

. 2

to classify the inner shapes because there i_ an implicit assumption that the length

of a side of a shape is at least twice as large as the sampie size utilized in the chain

code averaging scheme, and since for boul,,lary lengths of approximately twenty or

less the assumptiott is nor corre'ct., the alg,,ritAnn could not compensate. A second

experiment is designed to correctly i(let_l ifx shapes with relatively small boundary

lengths. In this exi)erimet_t, r he squares a 1,,[ triangles are discriminated 100 percent

of the time, but circles are mi_,lassified. ['he circles are classified as squares in 7

out of 9 attempts, and the t'emaining tin,_., they are classified as triangles.

Due to poor mage quality, there ar_' t.Wo occasions when the extraction of a

useful middle border is noi possible. Tlws, cases correspond to the marks 'ttc' and

'stc'. These imaaes at'e st_ow'l ill Fig,Ires 5.1 and 5.2. Examples of images where

the marks are idelltified at(' shown in Fig_lres 5.3, 5.4, 5.6 and 5.5. The case where

the middle shape is not correctly identifie.d is shown in Figure 5.7. From this figure,

the reason the algorithm miscl,_ssified tl,,' square as a triangle is clear. There is

I

I

I

II

i

ml

i

mi

i

|

m

i

|

i

i

i

i

i

i

: oF Poa QU .Lm,"

um
m

a significant amo,_nt of cut'vature on one _ide of the square, and since the exterr_l

angle change at the intersection o[" the curw,d segment and the line segment does

exceed the preset threshold, it is not interpreted as the beginning of a new side. Thi_

problem can be eliminated 1)y a,tjusting the, algorithm's threshold. Exarrtples _&here

the algorithm misciassified the inner circles as squares are shown in Figures 5.8 an4

8.2. It can be seen fl'om these figures that fhere exist some chain averaged external

angle changes that exceed the pt'eset angle threshold. This causes the algorithm to

attempt to classify the shape as either a square or a triangle and it classifies the

shape as being closet' to a squa t'e than a I t'iangle. The algot'ithm misclassifies the

inner circle of fid_lcial maLk 'tc,-' in Figure .5.9 as a triangle. This occurs , using the

same reasoning as previously n_,,ntioned, b,._cause the algorithm classifies the shape

as being closet" to a triangte thai1 a=square.

m

w

o, i OGR -,,
St. i

m

Bi_;_'_ ima_-_. ,-,,t_t;_iuiu$ fiducial mark ttc

I

l

RI

I

m

Ill

I

a

m

m

m

J

I

I

z

u

g

m
m

m

w

Fi_llr_.._.2" Billar.\ ima__' ,'_,l_r;Xil_i_l_ fiC!UCiM ll_ark stc

w
m

m

i

m

_[l/,n ['\ fiduciaI mark css

m

g

m

I

m

I

m

m

i

m

R

l

m

II

m

m

m

I

M

[]

m
5T

m

0

Figll_',' 5, t' Bi II _IF\ image ,-,,ntaining fictucial mark cts
I

|

|

Figu_',. ,'_5 i_it_a:', il_:_g, c_,t_rainill$ fid_ciaI n_ark tss

I

[]

I

m

i

I
!

r!

w

w

gig_11",' .5.!3: 13il_:_i'\ itna$_: c,,ntaining fid_lcial mni'k tst

w
60 u

g

m

i

i

I

Fi_l_'_. 5.v: Bi_lal'" imao_. ,',,_tain]ng Nducial mark tsc

m

U

M

i

fig

i

I

m

ill

i :

g

[] :
6 i

n

r_

w

®

EiZul'e 5.S: imaz-e ,,,,,itainino_fiducinl mark ccc
17-1

iE

Z

g

!

II

Ill

il

I

ill

m

II

ii
w

u

CHAPTER 6

CONCLUSION and FUTURE "WORK

A method is proposed to identit) the p_sition and orientation of the links of the

PUMA 560. To accomplish this task several fiducial marks will be placed on each

link. The goal is to uniquely identify tuvl locate each fiducial mark. Two different recognition algorithms are employed i_, an effort to ascertain the most reliable

method to identi(y the marks.

The first mc_.hod utilized moment ii_variants and the second method utilized

the chain coded version o[ the _.,-s curw'. For this application, the algorithm based

on theg,-s curve outperfotms the algorit.ltut based on the moment invariants. The

latter algorithm does not prove to bevery r,d)ust. The moment algorithm is not able

to compensate for the pe,'spective distorl ion present in the imaged representations

of the shapes. The features based on the _:"-s curve performed reasonably well, but

the algorithm _:an be improved.

To find the limitations of the curfew tiducial mark recognition algorithm, more

images will be examined. This can be acco,nplished by' taking images of the fiducial

marks at many different angles o[ inclina_i,,n with respect to the image plane while

constantly varying the distance to the i_,,ge plane. These images would be used

to determine which positions a_td oriene,tion of t,he marks cause the algorithm to

function poorly. The care[u[ ana.tysis of t l_.se results add insight, into the search for

more robust and (ffficient algori!hms. The tests should encompass the full range of

the PUMA 560.

Utilizing th(" data from Ihe _;"-s curve of the shape boundary, it is possible

to obtain more reliable recognil ion of the, ,harks. Instead of only utilizing the significant angle changes, the entire ¢'-s curve can be utilized by segmenting it into

straight lines. These straight [i_e segmem_l > provide valuable information regarding

OF POOR QiJa,[.ffY
the curvature of the boundary, using this methodology, the percentage of the curved

portion of the boundary is obtained. This provides an efficient method to discriminate the circle fl'om the other shapes. Foi example if 70 percent of a boundary is

sufficiently curved, the shape is probably a circle. To distinquish between a rectangle

and triangle, one can keep track of the positions in the boundary that correspond

tO the end points oi:line segments in the ,_,- s curve. This information is used to

determine whether a particular thee segment in the curve corresponds to a significant

portion of the boundary. If it does not then the segment can be interpreted as the

result of a poor image.

The improvements in the current algot'ithm and the verification of the correspondence of the centtoid in dilt'erent vi,,ws of the same scene are topics that will

be explored.

I

m

g

U

B

!

I

I

i

[]

m

I

I

[]

m

U

i

I

[]

m

I

m

I

=

==

i :

I

m

m

II
[11

[21

[a]

[4J

[5t

[6]

[71

[8]

[9]

[10]

Ill]

[I_9]

LITERATURE CITED

Hu, M. K. Visual pattern recognition by moment invariants. IRE Trans.

[nform. Theo W IT-S: t79-1.87; 1962.

Udagawa, K.:Toriwedd, J.;Sugino, K. Normalization and recognition of

two-dimensional with lineaL' distorti_,n by moments. Electron Commun. Japan

47 (6): 34-36; 1964.

Alt, F. L. Digital pattern recognit.ion by moments. J. Ass. Comput. Mach.

ACMg: 940-258; 1962.

Casey, R. G. _[oment normalization o_ handprinted characters. IBM Y. Res.

Dev. 14: 54,-o0,; 1970.

Smith, F. W. Auton_atic ship photo i,_terpretation by the method of

moments. JEFF D'ans. Comput. C-20: 1089-1094; 1971.

Dudani, S. A.; Breeding, K. J.; Mcghee, R. B. Aircraft identification by

moment invariants. [EEE F,'ans. Co,,_put. C-26: 39-45; 1977.

Teague, M. R. Image anaiysis via. the general theory of moments. J. Opt. Soc.

Am. 70: 920-930; 1980.

Wong, R. Y. Hall, E. L. Scene matching with invariant moments. Comput.

Graphics [mote Process. 8: 16-24; 1978.

Boyce, J. F.: Hossack, W..1. Moment, invariants for pattern recognition.

Pattern Recognition. Let:. 1: 451-45_: [983.

Khotanza.d, A.; Hong Y. H. Rotatio,_ invarianl; image recognition using

features selected via a systmnatic m, atlmd. Pattern Recognition. 28 (10):

1089-1.100; 1990.

Teh, C.-H.; C.'hin. R. T. Ot_ digital approximation of moment invariants.

Cornpt_t. i.ision. G,'ap/_ics. Ira.age P,r,cessin 9 33: 318-326; 1.986.

Fu, K.S.; Gonza[ez R. C.; l,ee C.S.C. Robotics: Control, Sensing, Vision and

Intelligence. McGraw Hill. !.987.

[13] Schalkoff, R...]. Digital [ms:It Proce.ss,,_9 and Computer Vision, Wiley, 1989.

6:F PO,,iq QiJALW'(
I

z

m

J

I

I

==

[]

__m

i

m_m

m

[]

|

m

Ill

m

g

il

[] |

mm |

ii !

I !

m

I