On Calibrating Computer Controlled Cameras for Perceiving 3-D Scenes

Introduction

Image analysis for 3-D scene perception is comput­ ationally expensive. It is thus important that a computer which moves its sensor be able to predict changes in the images of objects it has already seen without having to completely re-recognize them. We will present a solution to this problem that has been implemented at Stanfor4 for a visually guided manip­ ulator system.

T The Stanford hand-eye project is organized around a dual-processor PDP-10/PDP-6 computer system. Two elec­ trically-powered mechanical arms and two standard TV cameras with pan-tilt heads are interfaced to the com­ puter; they serve as hands and eyes respectively. In addition, the central part of the work space is a "lazy susan" turntable (see figure 1). To have the capability to visually locate objects in 3 dimensions, it is desireable to be able to see any point in the work space from two distinct viewpoints. In general this requi res several fixed cameras, and/or a highly mobile camera, and/or the ability for manipulating the environment so as to turn things around to see them better. The two cameras with pan-tilt heads, and the lazy susan, facilitate this. The computer is capable of moving the "arms, turntable, and cameras, and sensing the position of all moveable joints. Information flow is schematized for the "right half" of the system in figure 2. One camera is fitted with a zoom lens, while the other has a rotatable turret with 4 lenses. Both are fitted with color wheels. Zoom, turret-lens-selec­ tion, and color-filter-selection are under computer control. Also under computer control are focus, iris (on the zoom camera), and vidicon sensitivity. Visual information is transmitted to the computer by quantiz­ ing a TV image into an array of 250 x 333 samples. Each sample is a 4-bit number representing 1 of 16 possible light levels. A whole image or any rectangular subfield may be read into the computer memory from a camera.

This discussion deals with only one aspect of the find expressions for the camera geometry parameters in terms of the control variables. These expressions al­ ways contain fixed, but unknown, parameters which must be measured. The process of satisfactorily measuring these fixed parameters is what we call calibration. Since we are interested in developping a predictive model, it is desireable to find a set of such param­ eters that best accounts for images of known object configurations . An analytical derivation of such a "best" set typically leads to complicated simultaneous transcendental equations which do not yield to closed form solution. Moreover, the form of these equations depends strongly upon camera geometry and the number and type of control variables.

*The research reported here was performed at the Stan­ ford Artificial Intelligence Project and was supported in part by the Advanced Research Projects Agency of the Office of the Secretary of Defense under Contract SD183

To be more precise, modelling can be described as follows: Write down the transformation relating the 3-D coordinates of objects to the 2-D coordinates of their images. This depends upon the position and orien­ tation of the camera in object space - so-called ex­ ternal geometry - and on its internal geometry. All elements of external and internal camera geometry under computer control, should be expressed as functions of the computer Is control variables a = ·(Cl! ···· ·Clu). These will typically be outputs of feedback sensors. The transformation is schematized in figure 4. Typical geo­ metric variables for a camera on a pan-tilt head are the angles of PAN and TILT, and f which is the distance from the lens rear nodal point to the image. f is affected by both zooming and focusing motions. The corresponding control variables are potentiometer or shaft-encoder readings. They are usually linearly - but not always - related to the geometric quantities. e.g.

The camera transform can be represented by the vector equation

where p = (h,v) is the vector of image coordinates and F = (X,Y,Z) is the vector of object coordinates. This is equivalent to the following scalar equations: (2)

The particular form of Ch and Cv is determined both by camera geometry, and the relations of the a's to their corresponding geometric variables. Whatever this form it will always contain parameters S = (S1 , ··· ,Sm) not explicitly shown in (2). Usually these are neither under computer control nor directly measureable by the computer. To determine Ch and Cv for any particular moveable camera arrangement, one must nave some way of measuring these. The process of measuring S camera calibration. The S's are hopefully fixed or vary only infrequently, so that calibration need be done once and updated only if the S's drift ot the geometry is mod­ ified. S1 , ··· ,Sm are typically

1. numbers which relate sensor (pot or shaft­ encoder) readings to angles and/or distance e.g. S1.S2 of (1)

or

or

1. offset angles and/or distances between fixed elements of the camera mechanism
2. scale factors expressing distance ratios or quantization units

The Calibration System

At Stanford we designed and constructed an operational system 30 ' 31 for calibration of a camera with a zoom lens on a pan-tilt head (see figure 5)~ There are in fact m = 18 S's:

• 8 in class (a) above - 2 each for relating sensor outputs to geometric quantities associated with pan, tilt, zoom, focus.
• Of the remaining 10, 7 represent the external camera geometry and fall into class (b) above, while 3 represent the internal camera geometry - 2 in (b) and 1 in (c).

There are n = 4 control variables (a's) for pan, tilt, focus, and zoom. The system calculates a "best" S vector given 10 or more object-image point-pairs and their associated a's. It is divided into two parts: data collection and model optimization (see figure 6).

For data collection, pictures are taken of reference objects,with known shape (usually cubic) and location that are provided to the program by a human operator. At the time an image is transferred to the computer, the program reads the camera-control feedback sensors (pan, tilt, zoom, and focus pots? to ascertain the cur­ rent a. An edge-follower program 7 ' 25 then processes the image to extract boundary points of the object. A polygon is fit to the points. The polygon vertices are ordered to match up with the object space coordinates. Thus for the jth picture of a reference cube, the col­ lection routines will generate the data

where 2 < j < N is the image number and 1 ~ i ~ 6 is the point index within an image

This is stored on a data file for use in the optimiza­ tion calculation.

For model optimization, several data files are ac­ cumulated covering the working ranges of the a's. The calculation is a direct-search optimization 33 prog­ ram. It starts with an initial set of S's and computes a set of predicted image points

which is just equation (2) rewritten with S made ex­ plicit. The program compares these predictions with actual image-coordinates

measured by the image processing input routines, and computes a mean-squared prediction-error:

S is then systematically varied so as to minimize the the error E2 ·

To get an idea of how E 2 is affected by the number of images and points/image, note that a data triplet (P,a,p) yields 2 scalar constraint equations for the unknown 1):

*The turret camera is a special case of this wherein the zoom control is discrete instead of continuous.

These are ~ifferent from (3) in that h,v are measure­ ments and S is to be calculated. Assuming non-degener­ ate equations, we nee~ at least 18/2=9 such triplets to completely constrain S. The triplets should also be independent in the sense that each triplet yields new information (e.g. 2 P's in the same image along the same central ray yield the same p and are not indepen­ dent).

We can get an idea of the minimum number images (i. e. distinct values of a) needed, by using the fact that there are 10 basic geometric parameters for a fixed camera 0l = const): A, PAN, TILT, SWING, fMu, MRAT, and ~o. We can write constraint equations similar to (5) with the S's replaced by the geome~ric parameters, and deduce that we need 10/2=5 points P to completely solve for these. Of these basic parameters, MRAT, po, and SWING, are also S's. Another image, taken with different values for all the a's, will only have 6 £arameters unknown : (A, PAN, TILT, fMy), and only 6/2=3 P's will be needed to solve for the. new values. They may in fact be part of the original 5. The two_values of A are sufficient to solve for 6 more S's DP,Po to bring the total to 10. The two values each of PAN and TILT are also sufficient to solve for their 4 associa­ ted S's, leaving only the 4 S's relating the focus and zoom pots to fMy. Unfortunately each new image, created by changing focus and/or zoom gives us only one new equation in f~. Thus we need at least 2 more images of one point P, not on the camera axis, to get a total of 4 values for fMv and associated pot readings to give a soluble system oi 4 equations in the remaining 4 S's. In summary we have a specific method of solving for the 18 S's using 4 images using 5+3+1+1=10 data triples. The total number of distinct points can be the original 5. Thus though considerations of numbers of variables and constraint equations tell us that 9 data triples are necessary, the form of the equations seems to say that we need at least 10, arranged in 4 images as explained.

One of the features of the ~ptimization program is that it is interactive:

• 1 - It has a rather elaborate dynamic display (figure 6b).
• 2 - It allows the user to restrict the search to any specified subspace of a space.
• 3 - It allows him to choose between two search algo­ rithms4·30,31.
• 4 - It allows him to initialize a to any values he cares to.
• 5 - It allows the search to be interrupted at any time and the residual error/image to be dis­ played as a function of any of the a's. This is to see if there systematic deviations w.r.t. any given control variable. Such a deviation would indicate a defect in the model or the equipment associated with that a.
• 6 - It has a test mode for exploring the convergence of the optimization algorithms in the neighbor­ hood of any desired a. The user can either man­ ually input a or take a typical valu~arrived at from data. URon entering test mode, p replaces p, forcing E to zero. The user is then allowed to add a simulated distortion function to the new p if he chooses. He is finally asked to per­ turb a and observe the resulting convergence back to the ideal point.

The search is complicated by the fact that subsets of parameters are interdependent - e.g. to first order accuracy, changes in E 2 due to changes in po, can be offset by the PAN and TILT offset S's. It has been emp­ irically determined that there are multiple minima of E 2 , but they are spaced sufficiently far apart so that pur initial guesses are good enough not to go astray. Starting points are usually arrived at from rough manual measurements and calculations of ~he system geometry. A typical optimization sequence consists of:

• 1 - reading in about 10 data sets
• 2 - If a previous initial a has not been stored with the data, it must now be typed !n.
• 3 - choosing an appropriate subspace of S-space to search (maybe all of it)
• 4 - letting the first algorithm (usually more efficient) converge
• 5 - applying the second algorithm to try to improve the result if not good enough
• 6 - possibly returning to 3 and changing the sub­ space (optimizing over the whole space if not done)

The residual rms error E is a measure of the good­ ness of the model, and is typically 1 to 2 picture elements (pixels), which corresponds to 1.5 to 3.0 milliradians on the camera axis - with the particular optics used. Convergence typically takes about 5 min. of PDP-10 cpu time for all 18 parameters. The resid­ ual errors are due mainly to mechanical vibration of the optical system and electrical jitter of the scan electronics. These have so far masked lens and scan distortions.

The Future

At present there is a program at the hand-eye pro­ ject to expand the scope and efficiency of the cali­ bration system. The first step is to elimenate .the operator to manually measure and specify reference­ object coordinates (see figure 6a). We hope to do this by using the mechanical arm to place the objects ac~ cording to a prespecified calibration sequence. The resulting scheme will look as shown in figure 7. The prediction error in effect then becomes a "coordina­ tion error" between the hand and eye; the arm control­ ler will be reporting the object vertex positions PQR to the precision of the model relating its control variables aarm to requested hand position and orien­ tation. Meanwhile the camera calibration will be using the reported position information PQR(ciarm·~arm) to predict image coordinates. Gill 12 measured this coor­ dination error in his system for precise object mani­ pulation. He adjusted several camera S's suspected of drifting so as to minimize it.

* In this system, predicted image coordinates .pij are

These will be in error due to errors in both arm and camera calibrations aarm·a (see figu~e 7). The a errors cannot be seperated from the Sarm in the func­ tion E 2 of (4). Thus for smallest coordination error, it is desireable to jointly minimize both arm and camera models - about 40-50 parameters. This is a for­ midable optimization problem for 2 reasons:

• 1 - The behavior of the overall error function E 2 w.r.t. all these has not been investigated - in particular, for the presence of local minima near the global minimum.
• 2 - Unless the initial E 2 is already quite small, our current optimization procedures may well bog down on so many parameters, so as to be useless.

This strongly suggests that we use joint optimiza­ tion only as a last refinement, and even then possibly with approximate transform equations for faster conver­ gence near the minimum. Joint calibration is ultimately desireable, since the principal use of camera calibra­ tion is to get world coordinates for the purpose of guiding the arm.

Another system being considered utilizes two came­ ras, and optimizes their relative orientation based upon simultaneous measurement of the same calibration object from two different viewpoints. Thus, if a first camera has been calibrated relative to the reference object-space, a second can be calibrated relative to it etc. This technique is used extensively in photogram­ metry2 for compiling maps from large numbers of aerial photographs. A two-camera system, once calibrated, pro­ vides a 3-D measuring tool which can in turn be used for basic arm calibration.

What is really needed to simplify and speed-up opt­ imization is a separable error function . For example, something of the form

or even

which is more likely, would allow us to separately op­ timize parts of the system while still guarantying minimum overall error.

Yet another direction for improvement is that of calibration-updating; that is, re-calibrating the sys­ tem rapidly whenever observations in the course of nor­ mal operation show that errors have grown intolerably large. The emphasis here is on the word rapid - hope­ fully near real-time. One way to accomplish this is to collect data from measurements made during normal op­ eration of the system.

The fully automatic calibration system of the future will probably go through a bootstrapping phase; either an arm or a pair of eyes - whichever is more accurate will first be calibrated. This will be done possibly with the aid of a special calibration device for pro­ viding highly accurate reference data. The calibrated half of the system will then 'be used to provide data for calibrating the other half, at which point the to­ tal system will be jointly optimized to minimize coordination errors.

References and Bibliography

1. Agin, G., "Representation and Description of Curved Objects", PhD. thesis Elec. Eng. Dept. Stanford Univ. July 72. Available as AIM-173 from Stanford A. I. Project
2. American Society of Photogrammetry, Manual of Photo­ grammetry, 2 vols., Falls Church, Va., Jrd Ed., 1966 (see esp. Vol. 1 Ch. X on Analytical Photo­ grammetry) .
3. Baumgart, B., forthcoming PhD. thesis on Computer Graphics and Visual Perception, Stanford Univ. Computer Science Dept.
4. Brent, R. P. ,. "Algorithms for Finding Zeros and Ext­ rema of Functions Without Calculating Derivativ­ es", PhD. thesis, C.S. Dept., Stanford U., Mar. 1971, available as CS-198
5. Duda, R., Hart, P., book in press: Pattern Classi­ fication and Scene Analysis, Dec., 1970, avail. in preprint form from Stanford Research Insti­ tute.
6. 6. Earnest, L.E., "On Coosing an Eye for a Computer", Stanford AIM-51, April 1967
7. Falk, G., "Machine Analysis of Multi-Body Scenes", PhD. thesis, Stanford U.,c.s. Dept. 1970, avail. as CS-180 and AIM-132
8. Feldman, J .A., et. al., "The Stanford Hand-Eye Pro­ ject", Proc. First Int. Conf. on A. I., Wasil . , D.C., 1969
9. Feldman, J.A., "Getting a Computer to See Simple Scenes", IEEE Student Jour., Sept. 1970
10. Gibson, J.J., The Senses Considered as Perceptual Systems, Houghton-Miflin, Boston 1966
11. Gibson, J.J.,.Perception of the Visual World, Houghton-Miflin, Boston, 1950
12. Gill, A., "Visual Feedback and Related Problems in Computer Controlled Hand-Eye Coordination", PhD thesis, Elec. Eng. Dept., Stanford U., avail. AIM-178 from Stanford A.I. Project
13. Grape, G., "Computer Vision Through Sequential Abstractions", Internal Stanford A.I. Project Memo (SAILON) June, 1969
14. Grape, G., "Computer Vision Through Sequential Abstractions", forthcoming PhD. thesis, C.S. Dept., Stanford U.
15. Horn, B.K.P, "Focusing", MIT Project MAC A. I. Memo No. 160, May 1968
16. Horn, B.K. P., "Shape from Shading", MIT PhD. thesis, avail. from MIT A.I. Project as MAC TR-79, Nov. 1970 for geometry see "VISMEM: A bag of "robotics" ----formulae, MIT A.I.Lab. Memo (Dec. 1972)
17. Hueckel, M.H., "An Operator Which Locates Edges in Digitized Pictures", JACM, V. 18, NO. 1, Jan. 1971, pp. 113-125. Also Stanford AIM-105
18. Kahn, M., "Optimal Control of a Hydraulic Arm", PhD. thesis, Stanford M.E. Dept. 1969, avail. as Stanford AIM-106
19. Nilsson, N.J ., "A Mobile Automaton: An Application of Artificial Intelligence Techniques", Proc. IJCAI, pp.S09-515, May 1969
20. Paul, R., Falk, G., Feldman, J., "The Computer Representation of Simply Described Scenes", Proc. Illinois Graphics Conf., U. of Ill., Urbana, Ill. April 1969
21. Paul, R., "Studies With a Computer Controlled Arm", PhD. thesis, C.S.Dept., Stanford U. Aug. 1972 Avail. as Stanford AIM-
22. Perkins, D., MIT PhD. thesis Math. Dept. on Stereo Perception of Line Drawing Pairs, Oct. 1970
23. 23 . Pieper, D.L., "The Kinematics of Manipulators Under Computer Control", M.E . PhD. thesis, Stanford U., Oct. 1968, avail. as Stanford AIM-72

1. Pingle, K., Singer, J., Wichman, W., "Computer Con~ trol of a Mechanical Arm Through Visual Input", Proc. IFIP Congress 1968 Vol.2
2. Pingle, K., "Visual Perception by a Computer", in Automatic Interpretation and Classification of Images, Ed. Grasselli, Academic Press, N.Y., London 1969, pp. 277-284. see also "System Manual for Hand-Eye Hackers", Stanford A.I. Project Internal Memo (SAILON) June 1971
3. Roberts,L.G., "Machine Perception of Three-Dimen­ sional Solids", MIT Lincoln Lab., Lexington, Mass. Tech. Rpt. No. 315, May 1963
4. Roberts, L.G. "Homogeneous Matrix Representation and Manipulation of N-Dimensional Constructs", MIT Lincoln Lab., Lexington, Mass., Memo MS1405 May, 1965
5. Scheinman, V.D., "Design of a Computer-Controlled Manipulator", Engr. thesis M.E. Dept. Stanford U., avail. as Stanford AIM-92, June 1969
6. Schmidt, R., "A Study of the Real-Time Control of a Computer Driven Vehicle", PhD. thesis Stanford U. Elec. Eng. Dept., Aug. 1971, avail as Stanford AIM-149/CS-231
7. Sobel, I.E., "Camera Models and Machine Perception" PhD. thesis, Stanford U., Elec. Eng. Dept. May, 1970, avail. as AIM-121
8. Sobel, I.E., "Operating Manual for Camera Calib­ ration", Stanford A.I. Project Internal Memo Oct. 1972
9. Springer, C.E., Geometry and Analysis of Projective Spaces, W.H. Freeman and Co., San Francisco, 1964 (see sections 5.2 and 7.1)
10. Ternes, G.C., Calahan, D.A., "Computer Aided Network Optimization- The State of the Art", Proc. IEEE Vol. 55, No.ll, Nov. 1967, pp.l832-63
11. Tenenbaum, J.M., "Accomodation in Machine Percep­ tion", PhD. thesis, Stanford U. Elec. Eng. Dept. Aug. 1970, avail. as Stanford AIM-134/CS-182
12. Von Senden, M., Space and Sight, The Free Press, Glencoe, Ill., 1960 edition
13. Wichman, W., "Use of Optical Feedback in the Computer Control of an Arm", Engr. thesis, Stanford U. Elec. Eng. Dept. Aug. 1967, avail as Stanford AIM-56

TV MONITOR