 |
Description  |
|
|
MICROFICHE APPENDIX
Submitted herewith is an Appendix of one microfiche of fifty (50) frames.
BACKGROUND OF THE INVENTION
Many industries today are fast growing and have a very short product design
life. A typical example of such an industry is the computer and
electronics field.
Printed circuit boards, from which computers are built, are being
frequently redesigned. Thus the manufacturing lines that build these
boards need to be changed often. Factory automation is one answer to this
need for flexibility in production.
Many mass produced products have been built using hard or fixed automation.
However, the increase in design turnover requires a more flexible
solution.
The problem of printed circuit board assembly has previously been
investigated using flexible automation. A typical assembly application is
the insertion of nonstandard long leaded components. This problem has been
partially solved by various methods where blind insertion is applied using
precise fixturing of the boards while the leads are inserted using
mechanical guides. Miller, D. "Robotic Assembly in Electronic
Manufacturing" Robotics Today, Vol. 5, No. 6, pp. 28-32, December 1983.
Sanderson, A. C., Perry, G. "Sensor-Based Robotic Assembly Systems:
Research and Applications in Electronic Manufacturing", Proceedings of
IEEE, Vol. 71, No. 7, pp. 856-872, July 1983. Although this method is
effective, the large size of the guiding mechanism required for the leads
hinders the assembly of components which are very densely packed. In
addition, if it is desired to insert components with varying numbers of
leads, the end effector must be changed for each class of parts. Another
solution uses two television cameras, one looking at each lead from below
Asano, T. et al "Vision System of an Automatic Inserter for Printed
Circuit Board Assembly" Proceedings 2nd International Conference on Robot
Vision and Sensory Controls, pp. 63-73, November 1982. This method works
well when inserting two leaded components but would not be suitable or
practical for multi-leaded parts.
SUMMARY OF THE INVENTION
The invention is directed to the use of a robot manipulator adapted to
recognize at least two distinct regions on an object and the subsequent
placement of the object. A unitary vision system is used in combination
with a robot arm to view the object held by a gripper. Broadly, the
invention embodies a robotic manipulator where an object having at least
two identifiable features is acquired by a gripper at an acquisition site.
A vision system records images of the features in two different
orientations and the location of at least one of the features in space is
established. The location of the feature with respect to the robot
coordinate system is determined and subsequently expressed as a tool
transform. The object is placed at the target site. Preferably, the
recording of the feature, the determination of the location of the feature
with respect to the robot coordinate system and the expression of the
location of the feature(s) as a tool transform is done while the object is
being moved from the acquisition site to the target site. The movement of
the object is continuous (although it may be continual if desired). This
feature, of continuous movement, is believed, further distinguishes the
invention from prior art systems such as exemplified in U.S. Pat. Nos.
4,305,130; 4,402,053 and 4,412,293 wherein once an object has been
acquired it is moved to and held in a presentation pose. While in the
presentation pose data is acquired and the object subsequently moved to a
target site.
The invention will be described in reference to the acquisition of
multi-leaded parts and their subsequent insertion into a circuit board. In
an embodiment of the invention, a stereo triangulation procedure is used
in combination with a procedure for determining the correspondence of
image points in two images. In a preferred embodiment of the invention, a
unique camera (vision system) is fixed to the arm of a robot manipulator
and a transform is used to account for the relationship between the object
and the camera during image acquisition and placement. Additional
transforms, in a preferred embodiment, are used both to facilitate
measurements on the image plane and to account for the discretization of
the image plane.
In a particularly preferred embodiment an intermediate transform is used to
insure better accuracy during camera calibration.
In the preferred embodiment of the invention using a single camera (vision
system) fixed to the robot arm, the acquired object is rotated from a
first position to a second position about a known axis, viewed by the
single camera and first and second images are recorded.
The invention overcomes the prior art problems described above and provides
a method and apparatus for three dimensional locating of at least two
defined regions on an object using a single camera and the subsequent
placement of that object in a desired location.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a perspective view of a gripper, robot arm and a two leaded
component used to illustrate the invention;
FIG. 2 is a perspective view of a camera used with the invention;
FIG. 3 is a schematic illustration of a pinhole camera model;
FIG. 4 is a schematic illustration of a pinhole camera expressed to a robot
base;
FIG. 5 is a representation of various image plane coordinates;
FIG. 6 is an illustration of an alternate camera model;
FIG. 7 is a flow chart of the program CALIBRATE;
FIG. 8 is a flow chart of the program FORWARD;
FIG. 9 is an illustration of a dual camera stereo arrangement;
FIG. 10 is an illustration of stereo rangefinding using a single camera;
FIG. 11 is a flowchart of the program STEREO;
FIGS. 12 and 13 are binary images of lead ends;
FIGS. 14a, 14b and 14c are flow charts of the program LEADFIND;
FIG. 15 is a flow chart of the program GRABBYTE;
FIG. 16 is a flow chart of the program GETBIT;
FIGS. 17a and 17b are flow charts of the program OUTLINE;
FIG. 18 is an image of two lead components as viewed by the camera.
DESCRIPTION OF THE PREFERRED EMBODIMENT(S)
The invention will be described with reference to an illustrative example
where a robot manipulator with a camera mounted on its arm. The acquired
object is a two-leaded electrical component. A computer vision algorithm
determines the presence of the leads so that they may be properly inserted
in a circuit board.
In FIG. 1 the robot manipulator is shown as 10 and comprises a robot arm
12, a motor 14 to control the rotation of a gripper 16. A two-leaded
object 18 is held by the gripper 16. A camera 20 is fixed to the arm 12 by
a plate 22.
The Camera
The camera 20 is positioned such that the ends of the component leads 18
are visible when the component 18 is picked up by the manipulator 10. The
lead end locations are determined using a stereoscopic rangefinding
technique. The need for a second camera is eliminated by rotating the
component with the robot manipulator. The camera takes a second image of
the lead ends in a different pose.
The camera gives a binary output and is of the dynamic RAM variety.
In the following description the camera and computer vision algorithms are
implemented on an Apple IIe microcomputer. Briefly the triangulation
algorithm finds corresponding lead ends in two images of the component.
This procedure yields the lead locations as tool transformations with
respect to the robot manipulator. The robot manipulator used was a PUMA
robot.
The camera model, calibration and stereoscopic triangulation procedures are
based on the methods described in Duda, R. O., Hart, P. E. Pattern
Classification and Scene Analysis, John Wiley and Sons, New York 1983 with
the following modifications. An additional transformation is added to
account for mounting the camera model on the robot manipulator. Two other
transforms are appended to the model to make measurements on the image
plane easier as well as to account for the discretization of the image
plane. Another contribution is the acquisition of the second image for
stereo analysis. Instead of using a second camera, a rotation of the
object was performed about the last axis of the robot and a second image
taken using the same camera.
The camera 20 attached to the robot arm is mobile and may be repositioned
using the manipulator. The camera 20 can be moved close to the object
being looked at thereby increasing the effective resolution. Loughlin, C.
et al "Eye-in-Hand Vision Scores Over Fixed Camera" Sensor Review, Vol. 3,
No. 1, pp 23-26, January 1983. That is, as the camera is moved closer to
the scene, each pixel of the image represents a smaller area of the
object. Therefore, knowing the tolerance needed for a particular
application, this tolerance can be achieved by moving the camera closer to
the object. This is assuming that the camera can be focused at the
required distance.
Several robot mounted camera applications have been performed using
standard size television cameras. Agin, J. et al "Servoing with Visual
Feedback" Machine Intelligence Research Application to Industrial
Automation, Sixth Report, Stanford Research Institute. Yakimovski, Y. et
al "A System for Extracting 3-Dimensional Measurements From a Stereo Pair
of TV Cameras" Jet Propulsion Laboratory Technical Memorandum, Vol. 33,
No. 769, California Institute of Technology, May 1976, Hill, J., Park, W.
T. "Real Time Control of Robot with a Mobile Camera" 9th International
Symposium on Industrial Robots, pp. 233-246, March 1979. The cameras are
too large to be used efficiently and, therefore, as part of the present
invention, a camera was designed.
Referring to FIG. 2 the camera 20 is shown in greater detail and comprises
a dynamic RAM sensing element 30 (Micron Technologies 64K Optic RAM Type
1S32). The element 30 produces a binary image with each pixel being either
on or off depending on the amount of light falling on it. The camera 20
uses the drive hardware and software for the Apple IIe computer. The
element 30 is received in a housing 32, at the rear portion thereof (top
of housing not shown). The RAM is assembled with an 16 pin IC carrier, a
100 pF disc capacitor and a 470 pF disc capacitor and a 16 way ribbon
cable (not shown). A lens 40 (D.O. Industries 13 mm F 1.8 Micro Lens) is
secured to the front of the housing 32. It has a focusing range of about
three inches to infinity.
In order to use a binary image, the scene which is being operated on must
have a sharp change in contrast between the objects and the background.
This is true with the component lead problem if the component is held
against a dark background. A benefit of using a binary image is that the
image algorithms used to find the objects in the scene can operate very
fast since an object boundary is located where the scene changes from
light to dark and vice versa.
The resolution of the dynamic RAM (integrated circuit) element is
128.times.256 pixels. The camera software allows sampling of every second
pixel to yield a 64.times.128 image. This option was chosen since a
fourfold reduction in image data and corresponding image processing time
results.
It was found that in order to do an insertion of a typical electronic
component a position accuracy of 0.005 to 0.010 inches (0.125 to 0.250 mm)
is required, Sanderson et al supra. At a distance of 4 inches from an
object, the camera has a field of view of approximately 1/4.times.11/4
inches. Using a 64.times.128 resolution image gives an effective
resolution of approximately 0.005 times 0.010 inches (0.125.times.0.250
mm). Therefore positioning the camera at a distance of 4 inches from the
leads will give an adequate tolerance to insert the leads. Because of
physical constraints, the camera was only allowed to be positioned at 12
inches from the leads in the tests described hereinafter. This gives an
effective resolution of approximately 0.013.times.0.029 inches
(0.33.times.0.74 mm).
The other performance feature of the camera which should be noted is the
speed of response of the camera or the time taken to obtain an image. The
camera is a binary device. The pixels will either turn on or off depending
on the intensity as well as the time which light is allowed to hit them.
Therefore, in an atmosphere with a constant amount of light, a time
threshold is used to give the best contrast between object and background.
In typical room lighting, the time threshold as well as the image
acquisition time was found to be generally between 100 and 200
milliseconds.
CAMERA MODELING AND CALIBRATION
A pinhole camera was chosen as a mathematical representation for the actual
camera. This model was used to perform a camera calibration, which
expresses the relationship between an object in world coordinates to it's
corresponding camera coordinates.
There are several reasons for choosing a pinhole camera representation.
Firstly, it is the most commonly used model in the literature Duda, R. O.
supra, Nevatia, R., Machine Perception, Prentice-Hall, Inc., Englewood
Cliffs, N.J., 1982. Another reason is that it is a relatively simple model
to develop, especially if homogeneous coordinate transformations are used.
An additional feature of this model is that it is easy to visualize.
As a result of this inherent simplicity, one of the questions which is
commonly posed when using this model is that of accuracy. This question
was investigated at great depth at the University of Rhode Island. Several
alternative camera models were derived using two calibration planes. These
models were tested for error and compared with the pinhole camera model
Martins, H. "Vision Algorithms to Acquire Workpieces From a Bin of Parts",
PhD Thesis, University of Rhode Island, 1982. These tests were done using
several focal length lenses and several different cameras, of both solid
state and vidicon varieties. The conclusion was that the vidicon cameras
performed very poorly using the pinhole camera model, and performed
significantly better using the two plane models. However, the solid state
cameras were found to correspond well to the pinhole model, with an error
of about one half of one pixel of the effective resolution. The two plane
models applied to the solid state cameras did not show a significant
improvement in accuracy.
Therefore, it was concluded that the pinhole camera model would be a
reasonable one for this application since the optic RAM being used is a
solid state device.
The following derivation of the forward and inverse camera models and
camera calibration is based on the method presented in Duda, R. O. supra,
with several enhancements which are noted in the following disclosure.
(Note all cited publications are incorporated by reference in their
entireties in this disclosure).
Forward Camera Model
The pinhole camera model as shown in FIG. 3, consists of an image plane and
a pinhole lens at a distance f from the image plane. In this model, when
light is reflected off of an object at V, it travels along a projecting
ray, passes through the pinhole lens and intersects the image plane at
V.sub.p. It is assumed that all rays of light which enter the camera and
hit the image plane pass through the pinhole lens center. Therefore, in
order to describe the pinhole camera physically, all that is required is
to express the position and orientation of the image plane as well as the
position of the pinhole lens in space.
As can be seen, if the position of an object in space is known, it is
possible to determine where the corresponding image point on the image
plane will lie. However, if the position of an image point which
corresponds to an object in space is known, it is only possible to specify
a ray along which the object must lie. The distance along the ray to the
object, and hence the three dimensional position of the object, must be
determined by other means. In order to express the pinhole camera
mathematically, the image plane is shifted to a position a distance f in
front of the lens center as shown in FIG. 4. This image plane gives an
identical image to FIG. 3, but it is not inverted. This is called the
front image plane. In addition, a cartesian coordinate system has been
placed at the intersection of the front image plane and the principal ray,
which is the ray from the lens perpendicular to the image plane.
Using the method of similar triangles, a relationship between the object
point V and the image point V.sub.p can be found as follows
##EQU1##
If the vector V=(x,y,z).sup.t is expressed in homogeneous coordinates as
V=(x,y,z,1) the image vector V.sub.p may be expressed as V multiplied by
the perspective transformation, P, where
##EQU2##
Therefore V.sub.p may be expressed as
##EQU3##
Notice that this agrees with eq. 2 except that the second component is not
equal to 0. This fact will be discussed further when the Inverse Camera
Model is explained. The remainder of this section is a deviation from the
method in Duda, R. O. supra.
Since the camera is actually mounted on the robot manipulator, it is
desired to express an object in space with respect to the base frame of
the robot, instead of a frame on the image plane. In order to do this it
is assumed that the camera is mounted on the n.sup.th link of the
manipulator. It is also assumed that the camera will be translated and
rotated with respect to the coordinate from on the n.sup.th link of the
robot, but the camera will not be rotated about it's principal axis. This
is a reasonable assumption which makes later analysis simpler.
To allow a point described with respect to the robot base frame to be
expressed with respect to the camera frame, FIG. 4 the following
expression is used.
##EQU4##
T.sub.n.sup.-1 =func(.theta..sub.1, .theta..sub.2, . . . , .theta..sub.n:
which is manipulator dependent
V.sub.o =object point expressed with respect to manipulator base frame.
Here the transformation R represents a rotation of .theta. about the z
axis, followed by a rotation of .phi. about the x axis. The T transform
represents a translation of t.sub.1, t.sub.2, t.sub.3 along the x, y and z
axes, respectively. T.sub.n.sup.-1 represents the transformation from the
base frame to the n.sup.th frame of the robot.
Now, the setup using a Puma robot (Model No. 600) will be described
assuming the camera is mounted on the third link of the robot. This
defines n to be 3. T.sub.n.sup.-1 can now be expressed as
T.sub.n.sup.-1 =T.sub.3.sup.-1 =(A.sub.1 A.sub.2 A.sub.3).sup.-1
where A.sub.1, A.sub.2 and A.sub.3 are matrices from the kinematic joint
solution which describe the transformations from the base to first, first
to second and second to third frames, respectively.
It is inconvenient, however, to express the image coordinates with respect
to the coordinate system through the principal axis of the lens, since the
rows and columns of the image are measured from one corner. A second
translation matrix is introduced to translate the camera reference frame
to the lower left corner of the image plane as shown in FIG. 5. Also a
scaling matrix must be used since the pixels on the image plane are
discrete units instead of continuous space. The transformations are
applied to the camera model in the following way.
V.sub.i =SO V.sub.p =SOPRTT.sub.3.sup.-1 V.sub.o (9)
where
##EQU5##
The multiplication of OPRT for the actual camera model is set forth below.
The forward camera transformation from world coordinates to image
coordinates can be expressed as
V.sub.i =SOPRTT.sub.3.sup.-1 V.sub.o
where
V.sub.i =image coordinates of a point expressed in homogeneous coordinates
V.sub.o =world coordinates of the same point expressed in homogeneous
coordinates
##EQU6##
In order to simplify the determination of unknown parameters in OPRT by
calibration, eq. A-1 will be expressed as
S.sup.-1 V.sub.i =[OPRT]T.sub.3.sup.-1 V.sub.o
To simplify the calculation of OPRT, the following substitutions are made
in R
r.sub.1 =cos .theta.
r.sub.2 =sin .theta.
r.sub.3 =cos .phi.
r.sub.4 =sin .phi.
It should be noted that the common trigonometric identity
cos .theta.=1/sin .theta.
is not used here. This is because the values of the parameter matrix which
will be yielded by the calibration procedure will be approximate and there
will be no guarantee that the identity will be true. Therefore R
simplifies to
##EQU7##
Before multiplying OPRT, the calculations of OP and RT are done as shown.
##EQU8##
The product of OPRT is given by
##EQU9##
where
A.sub.11 =r.sub.1 +(-o.sub.1 r.sub.2 r.sub.3)/f
A.sub.12 =R.sub.2 +(o.sub.1 r.sub.1 r.sub.3)/f
A.sub.13 =(o.sub.1 r.sub.4)/f
A.sub.14 =t.sub.1 r.sub.1 +t.sub.2 r.sub.2 +o.sub.1 ([(-t.sub.1 r.sub.2
r.sub.3 +t.sub.2 r.sub.1 r.sub.3 +t.sub.3 r.sub.4)/f]+1)
A.sub.21 =-r.sub.2 r.sub.3
A.sub.22 =r.sub.1 r.sub.3
A.sub.23 =r.sub.4
A.sub.24 =-t.sub.1 r.sub.2 r.sub.3 +t.sub.2 r.sub.1 r.sub.3 +t.sub.3
r.sub.4
A.sub.31 =r.sub.2 r.sub.4 +(-o.sub.3 r.sub.2 r.sub.3)/f
A.sub.32 =-r.sub.1 r.sub.4 +(o.sub.3 r.sub.1 r.sub.3)/f
A.sub.33 =r.sub.3 +(o.sub.3 r.sub.4)/f
A.sub.34 =t.sub.1 r.sub.2 r.sub.4 -t.sub.2 r.sub.1 r.sub.4 +t.sub.3 r.sub.3
+o.sub.3 ([(-t.sub.1 r.sub.2 r.sub.3 +t.sub.2 r.sub.1 r.sub.3 +t.sub.3
r.sub.4)/f]+1)
A.sub.41 =-(r.sub.2 r.sub.3)/f
A.sub.42 =(r.sub.1 r.sub.3)/f
A.sub.43 =r.sub.4 /f
A.sub.44 =[(-t.sub.1 r.sub.2 r.sub.3 +t.sub.2 r.sub.1 r.sub.3 +t.sub.3
r.sub.4)/f]+1
Inverse Camera Model
If the coordinates of a point in space are known with respect to a base
frame, the corresponding image coordinates may be determined using eq. 9.
However, in general, the image coordinates of the object in space are
known with respect to the image frame from the camera. It is the
coordinates of the object in space which are required. In order to yield
this information, the inverse of eq. 4 is taken to give
##EQU10##
When using the forward camera model, y.sub.p, the second coordinate of the
image point as calculated with forward perspective transformation eq. 5
does not correspond to the actual camera where y.sub.p =0 (eq. 2).
Therefore a question to be answered is: When using the inverse perspective
transformation (eq. 12) what should be used for the second component of
V.sub.p ? It can be shown that if y.sub.p =0 is used for the image point
in eq. 12, it yields V=(x.sub.p,0,z.sub.p). This is not reasonable since
what is desired is to map a point on the image plane into a ray in space
instead of a single point.
Therefore, as suggested by eq. 5, y.sub.p is entered into eq. 12 with
##EQU11##
This suggests that y.sub.p should be used as a free parameter which is
related to y, the distance between the object point and the image plane
(FIG. 4). If eq. 13 is substituted into eq. 12 as y.sub.p, the result for
V is
##EQU12##
This is the same result which was obtained using the similar triangle
approach in eq. 1.
It can be shown that as y is varied, y.sub.p from eq. 13 will exhibit the
following behavior. At the lens center, when y=-f, y.sub.p =-.infin. When
y=O, at the picture plane, y.sub.p =0. Far out along an image ray, when
y=.infin., y.sub.p =f.
The reason for this apparent discontinuity in the free parameter stems from
the fact that the homogeneous coordinate transformation is meant to map
from one three dimensional space to another. In the case of the camera
model, the transform is actually mapping from three dimensions (the object
space) to two dimensions (the image space). There is a loss of one
dimension in the forward camera model. Therefore, when the inverse camera
model is used, a free parameter must be entered to allow for this lost
dimension. This free parameter must be determined by other means such as
knowing which plane an object lies on, or by using laser or stereoscopic
rangefinding techniques.
The inverse perspective transformation can be expressed in an alternate
form (FIG. 6) by rewriting V as
V=L+lam(V.sub.p -L) (15)
where L is the lens center which is found by letting y.sub.p approach minus
infinity in eq. 12 V.sub.p is the image point on the image plane, with
respect to the reference frame. This is found by setting y.sub.p =0 in eq.
12. This is a convenient form, as the object point can be found by
following a ray in the direction of V.sub.p -L from L by a distance lam
which is related to y.
This discussion can be applied to the situation where the camera is mounted
on the third link of the manipulator. To derive the inverse camera
transform for this case, the inverse of eq. 9 is taken, yielding
V.sub.o =T.sub.3 T.sup.-1 R.sup.-1 P.sup.-1 O.sup.-1 S.sup.-1 V.sub.i (16)
To form eq. 15 for this case, L and V.sub.p are found by letting y.sub.i
=-.infin. and O, respectively. A sample calculation of L and V.sub.p, is
set forth below.
The inverse camera transformation from image coordinates to world
coordinates is given by
V.sub.o =T.sub.3 T.sup.-1 R.sup.-1 P.sup.-1 O.sup.-1 S.sup.-1 V.sub.i (B-
1)
This may be represented by
##EQU13##
The coordinates of an image point on the image plane, with respect to the
robot base frame are found by letting y.sub.i =0. Letting y.sub.i =0 in
eq. B-2 and renaming this to V.sub.p gives
##EQU14##
The coordinates of the lens, with respect to the robot base frame are
found by letting y.sub.i =.infin.. Making this substitution and renaming
as L gives
##EQU15##
CAMERA CALIBRATION
Determination Of Parameter Matrix
A suitable mathematical model for the camera has now been developed, the
parameters which define this model (such as O, O, t.sub.1, t.sub.2,
t.sub.3, f, etc.) must be determined. One method of doing this is to
physically measure the parameters. This is not feasible for most of these
parameters since the quantities that are being measured, such as lens
center and principal axis, are quite abstract. A more reasonable method
would be to gather a number of world point locations as well as their
corresponding image locations and use a statistical method, such as least
squares, to determine the best correlation between the parameters.
In order to lessen the number of parameters which must be determined, the
two elements of the scaling matrix, S, may be calculated based on the data
which is distributed with the DRAM chips. These parameters were found to
be
##EQU16##
The matrix T.sub.3.sup.-1 is also known by measuring the first 3 joint
coordinates of the robot, assuming that these joint angles did not change
during calibration. It is assumed that n correspondences will be found
between object and image points.
To find the remaining parameters, the following expression will be used
from the forward camera model
S.sup.-1 V.sub.i =OPRT(T.sub.3).sup.-1 V.sub.o (18)
This equation is restated in the following form.
V'=HV (19)
(3.times.n) (3.times.4)(4.times.n)
where V' is a 3.times.n matrix whose columns consist of the n vectors
S.sup.-1 V.sub.i expressed in homogeneous coordinates v is a 4.times.n
matrix whose columns are the n vectors of T.sub.3.sup.-1 V.sub.o. H is
defined to be the product of OPRT with the second row deleted. The second
row of OPRT must be deleted when forming H since when measuring V' the
values of the free parameter y.sub.p are not known and thus must be
ignored. The values of the second row of OPRT must be determined by an
alternate method.
This situation is more correctly defined as
HV=V'D (20)
where D is a diagonal scaling matrix. This matrix is necessary since the
scaling of the last component of each point in homogeneous coordinates may
not be the same. The optimal solution is given from Duda, R. O., supra as
A=V.sup.t (VV.sup.t).sup.-1 V-I (21)
Q=(V').sup.t V' (22)
Let S be a matrix whose (i,j)th element s.sub.ij =a.sub.ij dq.sub.ji. Note
that this is not common matrix multiplication. Let the n dimensional
vector d have as its components the n diagonal elements of D. The solution
to D is found from the homogeneous system
Sd=0 (23)
The matrix H may then be determined from
H=V'DV.sup.t (VV.sup.t).sup.-1 (24)
Determination Of Focal Length Parameter F
The parameter matrix, H, has been computed, which is equivalent to the
product of OPRT with the second row deleted. In order to calculate the
second row of OPRT, the parameter f must be determined.
The procedure to find f is to equate respective elements of H and OPRT.
This yields 12 equations in 10 unknowns which may be solved for the
parameter f. The result is a nonlinear equation in f and the known
elements of H. This equation is solved for f using the method of bisection
with a reasonable starting segment. This procedure is set forth below.
H as calculated by the CALIBRATE program can be defined as
##EQU17##
Equating elements of H and OPRT given in Appendix 1 gives
h.sub.11 =r.sub.1 +(-o.sub.1 r.sub.2 r.sub.3)/f (C-2a)
h.sub.12 =r.sub.2 +(o.sub.1 r.sub.1 r.sub.3)/f (C-2b)
h.sub.13 =(o.sub.1 r.sub.4)/f (C-2c)
h.sub.14 =t.sub.1 r.sub.1 +t.sub.2 r.sub.2 +o.sub.1 ([(-t.sub.1 r.sub.2
r.sub.3 +t.sub.2 r.sub.1 r.sub.3 +t.sub.3 r.sub.4)/f]+1) (C-2d)
h.sub.21 =r.sub.2 r.sub.4 +(o.sub.3 r.sub.2 r.sub.3)/f (C-2e)
h.sub.22 =-r.sub.1 r.sub.4 +(o.sub.3 r.sub.1 r.sub.3)/f (C-2f)
h.sub.23 =r.sub.3 +(o.sub.3 r.sub.4)/f (C-2g)
H.sub.24 =t.sub.1 r.sub.2 r.sub.4 -t.sub.2 r.sub.1 r.sub.4 +t.sub.3 r.sub.3
+o.sub.3 ([(-t.sub.1 r.sub.2 r.sub.3 +t.sub.2 r.sub.1 r.sub.3 +t.sub.3
r.sub.4)/f]+1) (C-2h)
h.sub.31 =-(r.sub.2 r.sub.3)/f (C-2i)
h.sub.32 =(r.sub.1 r.sub.3)/f (C-2j)
h.sub.33 =r.sub.4 /f (C-2k)
h.sub.34 =[(-t.sub.1 r.sub.2 r.sub.3 +t.sub.2 r.sub.1 r.sub.3 +t.sub.3
r.sub.4)/f]+1 (C-2l)
From eqs. C-2k, C-2j, C-2i, respectively
r.sub.4 =fh.sub.33 (C- 3a)
r.sub.1 r.sub.3 =fh.sub.32 (C- 3b)
r.sub.2 r.sub.3 =-fh.sub.31 (C- 3c)
Eqs. C-2a and C-2b give r.sub.1 and r.sub.2 as
r.sub.1 =h.sub.11 -o.sub.1 h.sub.31 (C- 3d)
r.sub.2 =h.sub.12 -o.sub.1 h.sub.32 (C- 3e)
Substituting eqs. C-3d into C-3b yields r.sub.3 below
r.sub.3 =fh.sub.32 /(h.sub.11 -o.sub.1 h.sub.31) (C-3f)
Substituting eqs. C-3d and C-3e into C-2e and C-2f gives
h.sub.21 =h.sub.12 fh.sub.33 -o.sub.1 h.sub.32 fh.sub.33 +o.sub.3 h.sub.31
(C- 3g)
h.sub.22 =-h.sub.11 fh.sub.33 +o.sub.1 h.sub.31 fh.sub.33 +o.sub.3 h.sub.32
(C- 3H)
Multiplying eq. C-3h by h.sub.31 and substracting it from the product of
eq. C-3g and h.sub.32 gives o.sub.1 as
##EQU18##
Multiplying eq. C-3h by h.sub.32 and adding it to the product of eq. C-3g
and h.sub.31 gives o.sub.3 as
##EQU19##
Substituting C-3f, C-3j, C-3a and C-3i into eq. C-2g gives a nonlinear
equation in f as
F(f)=((h.sub.11 -h.sub.31 [(B/A)+(C/(fh.sub.33 A))])(h.sub.23 -fh.sub.33
D+E]h.sub.33 /A)/h.sub.32)-f (C-4)
where A, B, C, D and E are defined as follows
A=h.sub.32.sup.2 +h.sub.31 .sup.2
B=h.sub.32 h.sub.12 +h.sub.11 h.sub.31
C=h.sub.22 h.sub.31 -h.sub.32 h.sub.21
D=h.sub.32 h.sub.11 -h.sub.31 h.sub.12
E=h.sub.31 h.sub.21 +h.sub.32 h.sub.22
This equation is used in a bisection routine to determine f.
Once the parameter f is found, the remaining elements of OPRT may be
computed. This matrix may now be inverted to yield the inverse camera
model, which is the final product of the calibration procedure.
SOFTWARE
In the following two sections, the calibration program and the forward
camera model program will be presented. Complete program listings are set
forth in the Appendix. The calibration program is used to determine the
parameters of the camera model as outlined in the previous section. The
forward camera model program is used after the calibration routine to
determine the adequacy of the computed camera model. The FORWARD routine
calculates the pixel coordinates of a point in world space and may then be
compared to an actual image of the point in world space. If the camera
model is good, there should be a discrepancy of not more than one pixel
between the images.
Because the camera hardware interfaces with the Apple IIe microcomputer,
the high level routines were written in Applesoft Basic. These routines
use matrix algebra since this is the form of the homogeneous coordinate
representation. However, a separate matrix multiplication subroutine was
not written since the Applesoft Basic language does not allow passing of
variable arguments in subroutines. Each matrix multiplication therefore
was written directly in the main program and makes the programs much
longer than they would have been if a matrix algebra subroutine was
available.
Another facet of the Apple IIe which should be mentioned is the limited
amount of memory available. The CALIBRATE program and it's associated
variables are of sufficient size such that when the program is run, a
portion of the memory where the low level machine language routines are
stored is overwritten. These machine language routines are mainly used to
obtain the image from the camera and to extract the relevant data from the
image. Therefore, in use the CAMERA program must be run and it's data must
be stored | | |
