Tomislav Pribanic

03-09-1998, 01:16 AM

Dear Biomch-l readers,

Last week I have asked some questions concerning DLT. I thank all of you who tried to help me. I am submiting all responses I have received, although the first

two are the most representive.

But first here is my original question:

I am new biomech postgraduate student. At the present time I am involved

in human motion analysis by means of 3-D reconstruction with DLT.

I am trying to write computer program of my own (although I am aware of contributed packages for Matlab and C on various sites e.g.http://www.kin.ucalgary.ca/isb/software/kinemat/readme1.htm). Currently I am stuck with the issue of camera calibration. According to the basic equations:

u=(L1*X + L2*Y + L3*Z + L4) / (L9*X + L10*Y+ L11*Z + 1)

v=(L5*X + L6*Y + L7*Z + L8) / (L9*X + L10*Y+ L11*Z + 1)

one needs six or more calibration points in order to calculate 11 DLT parameters.

Since we then deal with overdetermined system of equations many authors are therefore mentioning and employing linear least-square techniques to compute DLT

parameters (e.g. Hatze, H. (1988) High-precision three-dimensional photogrammetric calibration and object space reconstruction using a modified DLT-approach.

J. Biomechanics Vol 21. No. 7. pp. 533-538).

However, I have not seen anywhere the exact way how the above mentioned technique is preformed. The essence of linear least-square technique is in the form of

F(a,b)=sum( (y(i)-(a*x(i)+b))^2 ) i=1,...n

y(i),x(i) coordinates of various points

a,b parameters of line y=a*x+b.

Afterwards one takes partial derivate of F(a,b) with a and b in order to compute the parameters of line. One gets two equations with two unknowns and the rest is easy. What I do not understand is how it is applied in case of computing DLT parameters.

Do I have to write the entire thing in the form of:

F(a,b,L1,L2,...L11)=sum( (v(i)-(a*u(i)+b))^2 )

i=1,...n calibration points

u(i)=(L1*X(i) + L2*Y(i) + L3*Z(i) + L4) / (L9*X(i) + L10*Y(i)+ L11*Z(i) + 1)

v(i)=(L5*X(i) + L6*Y(i) + L7*Z(i) + L8) / (L9*X(i) + L10*Y(i)+ L11*Z(i) + 1)?

And then take the partial derivations of function F(a,b,L1,....L11) with a,b,L1,L2,....L11 in order to find parameters?

Or maybe I am supposed to go as follows:

F(L1,L2,...L11)=

sum( (u(i)-(L1*X(i) + L2*Y(i) + L3*Z(i) + L4) / (L9*X(i) + L10*Y(i)+ L11*Z(i) + 1))^2+

+ (v(i)-(L5*X(i) + L6*Y(i) + L7*Z(i) + L8) / (L9*X(i) + L10*Y(i)+ L11*Z(i) + 1))^2 )

and now also preform partial derivations of the L1,L2,..L11 unknowns?

I have tried both ways, but it did not seem to be right direction for all kinds of reasons. Also, once I acquire all parameters and try to gain the space coordinates of the unknown point out of two or more cameras picture I am again dealing with more equations than I need. Do I act in a similar fashion as above?

What is the matematical procedure when is MDLT (Modified DLT) concerned,

rather than conventional DLT?

I would be glad to post on the List all answers I recieve, once I collected them.

Thanks in advance for any help/comments.

RESPONSES:

************************************************** *****************************

Dear Tomislav,

The best way to deal with the problem of solving linear equations with

fewer unknowns than equations

(over-determined system) is to use matrix manipulation . You can use

numerical methods to do that.

For example to deal with a system of three equations with two unknowns that

can be represented by:

[A](subscript: 3x2 ){X}(subscript:

2x1 )= {B}(subscript: 3x1)

(where {X}(subscript: 2x1) is the unknown

matrix)

You multiply both sides of the equation by the transpose of [A] to get:

[A](superscript: T)(subscript: 2x3) [A]

(subscript: 3x2 ){X}(subscript: 2x1 )= [A](superscript: T)(subscript: 2x3)

{B}(subscript: 3x1 )

you will end up with a system of two equations with two unknowns that

should be easy to solve:

[A'](subscript: 2x2 ){X}

(subscript: 2x1 )= {B'}(subscript: 2x1)

This can be applied to get the calibration coefficients for each camera and

also to get the 3D coordinates of

the targets from two or more cameras. Let me know if you have any

questions. Good luck.

Ali M. Elhagediab, PhD

Research Scientist

Aerotek Corp. (in contract with General Motors Corp.)

email: aelhaged@notes.gmr.com

************************************************** *****************************

Dear Tomislav:

I was in a similar situation some time ago when I was a Master's student in

Seoul, Korea. I've read a lot of things since then and finally could figure

out what DLT is all about. I even have written a motion analysis package

based on DLT after that.

For camera calibration with n (>6) control points, the system will be

over-determined. Then the linear system looks like this:

X B = Y

where, X = known 2n x 11 matrix, B = transpose of (L1 .... L11), and Y =

known 2n x 1 matrix made of u and v.

Multiply both sides with the transpose of X, X', to make the matrix in front

of B square. This stage is called normal equation:

(X' X) B = X' Y

Then Multiply both sides with the inverse of (X' X) or (X' X)^-1:

(X' X)^-1 (X' X) B = (X' X)^-1 (X' Y)

Then, the left side of the above equation is the same to the least-square

estimate of B:

B = (X' X)^-1 (X' Y)

With only manipulation of the matrices, you will be able to do the least

square estimation.

This procedure is in fact exactly the same to the multiple linear regression

in statistics. Consult any statistics textbook for this procedure: multiple

linear regression using matrix approach.

You may use exactly the same approach to compute the 3-D coordinates of the

unknown points with more than 2 cameras.

In reality, if you include the additional parameters to correct the optical

distortion and the de-centering distortion due to the optical system, the

situation is much more complex than this. I am in the middle of putting

these things on the web, and I'll let you know when it is done.

Hope this to be helpful.

Young-Hoo

--------------------------------------------------------------

Young-Hoo Kwon, Ph.D.

Assistant Professor

Biomechanics Lab, PL 202

Ball State University

Muncie, IN 47306

U.S.A.

Phone: +1 (765) 285-5126 (O), +1 (765) 284-4880 (H)

Internet: ykwon@bsu-cs.bsu.edu

Homepage: http://www.bsu.edu/cast/biomch/kwon/

--------------------------------------------------------------

************************************************** *******************************

(L9*X + L10*Y+ L11*Z + 1)*u = (L1*X + L2*Y + L3*Z + L4)

This is a LINEAR SYSTEM in the L1--L11 unknown.

The coefficients are Xu,Yu, Zyu X Y Z and 1.

The term on the right side is u.

N. Alberto Borghese

************************************************** *******************************

I used the methods as presented by J.S. Walton (1978)

Close range cine-photogrammetry: another approach to motion analysis.

Pages 69-97 in Terauds, J.S., editor, Sciences in Biomechanics

Cinematography, International Congress of Sports Sciences. Del Mar,

California: Academic Publishers.

************************************************** **********************************

> F(a,b)=sum( (y(i)-(a*x(i)+b))^2 ) i=1,...n

> y(i),x(i) coordinates of various points

> a,b parameters of line y=a*x+b.

> Afterwards one takes partial derivate of F(a,b) with a and b in order to compute the parameters of line. One gets two equations with two unknowns and the rest is easy. What I do not understand is how it is applied in case of computing DLT parameters.

> Do I have to write the entire thing in the form of:

>

> F(a,b,L1,L2,...L11)=sum( (v(i)-(a*u(i)+b))^2 )

>

> i=1,...n calibration points

> u(i)=(L1*X(i) + L2*Y(i) + L3*Z(i) + L4) / (L9*X(i) + L10*Y(i)+ L11*Z(i) + 1)

> v(i)=(L5*X(i) + L6*Y(i) + L7*Z(i) + L8) / (L9*X(i) + L10*Y(i)+ L11*Z(i) + 1)?

Take the two DLT equations, and multiply left and right sides by

(L9*X(i) + L10*Y(i)+ L11*Z(i) + 1). Then you have linear equations.

Define F as:

F = sum( (leftside - rightside)^2 )

(sum over all equations, two equations (u,v) for each calibration point).

Fortunately, Matlab has a builtin linear least squares solver (say 'help slash' for

help). You simply collect the coefficients in a matrix, and use the

backslash operator. This was used in the kinemat functions.

> What is the matematical procedure when is MDLT (Modified DLT) concerned,

> rather than conventional DLT?

> I would be glad to post on the List all answers I recieve, once I collected them.

The MDLT has only 10 calibration parameters (not 11), since it assumes that the

u and v axis in image space are perpendicular. This is true for film and video.

With MDLT, you need at least 5 calibration points, but more is recommended

for reliability. Reference:

Chen, L., Armstrong, C.W., Raftopoulos, D.D., (1994) An investigation on the

accuracy of three-dimensional space reconstruction using the direct linear

transformation technique. J. Biomech. 27:493-500.

[Good paper on performance of the DLT using different sets of calibration

points. It is shown that significant improvement can be gained by

increasing the number of calibration points to 16. More than that

does not help much. Some discussion of nonlinearity and how to

correct for that.]

-- Ton van den Bogert

Department of Biomedical Engineering

Cleveland Clinic Foundation

************************************************** *****************************

I use the singular value decomposition (SVD) method to perform linear least

squares. the book Numerical Recipes in C provides C code to perform these

routines. There is also a Numerical Recipes in Pascal, Fortran, etc....

Once you solve the linear least squares procedure to determine the 11 DLT

parameters, you need to rewrite your equations to obtain XYZ in terms of

U,V, and the eleven parameters. In this way you can again use linear least

squares to find the optimum XYZ positions to fit the digitized UV coordinates.

************************************************** *****************************

Dear Tomislav:

As I told you earlier, here is the URL of my DLT page:

http://www.bsu.edu/cast/biomch/kwon/kwon3d/

It has some information on the DLT method and optical distortion-related

stuffs.

Sincerely,

Young-Hoo

--------------------------------------------------------------

Young-Hoo Kwon, Ph.D.

Assistant Professor

Biomechanics Lab, PL 202

Ball State University

Muncie, IN 47306

U.S.A.

Phone: +1 (765) 285-5126 (O), +1 (765) 284-4880 (H)

Internet: ykwon@bsu-cs.bsu.edu

Homepage: http://www.bsu.edu/cast/biomch/kwon/

--------------------------------------------------------------

************************************************** *****************************

Tomislav Pribanic

Faculty of Electrical Engineering and Computing

University of Zagreb

10 000 Zagreb

CROATIA

E-mail:Tomislav.pribanic@zesoi.fer.hr

Last week I have asked some questions concerning DLT. I thank all of you who tried to help me. I am submiting all responses I have received, although the first

two are the most representive.

But first here is my original question:

I am new biomech postgraduate student. At the present time I am involved

in human motion analysis by means of 3-D reconstruction with DLT.

I am trying to write computer program of my own (although I am aware of contributed packages for Matlab and C on various sites e.g.http://www.kin.ucalgary.ca/isb/software/kinemat/readme1.htm). Currently I am stuck with the issue of camera calibration. According to the basic equations:

u=(L1*X + L2*Y + L3*Z + L4) / (L9*X + L10*Y+ L11*Z + 1)

v=(L5*X + L6*Y + L7*Z + L8) / (L9*X + L10*Y+ L11*Z + 1)

one needs six or more calibration points in order to calculate 11 DLT parameters.

Since we then deal with overdetermined system of equations many authors are therefore mentioning and employing linear least-square techniques to compute DLT

parameters (e.g. Hatze, H. (1988) High-precision three-dimensional photogrammetric calibration and object space reconstruction using a modified DLT-approach.

J. Biomechanics Vol 21. No. 7. pp. 533-538).

However, I have not seen anywhere the exact way how the above mentioned technique is preformed. The essence of linear least-square technique is in the form of

F(a,b)=sum( (y(i)-(a*x(i)+b))^2 ) i=1,...n

y(i),x(i) coordinates of various points

a,b parameters of line y=a*x+b.

Afterwards one takes partial derivate of F(a,b) with a and b in order to compute the parameters of line. One gets two equations with two unknowns and the rest is easy. What I do not understand is how it is applied in case of computing DLT parameters.

Do I have to write the entire thing in the form of:

F(a,b,L1,L2,...L11)=sum( (v(i)-(a*u(i)+b))^2 )

i=1,...n calibration points

u(i)=(L1*X(i) + L2*Y(i) + L3*Z(i) + L4) / (L9*X(i) + L10*Y(i)+ L11*Z(i) + 1)

v(i)=(L5*X(i) + L6*Y(i) + L7*Z(i) + L8) / (L9*X(i) + L10*Y(i)+ L11*Z(i) + 1)?

And then take the partial derivations of function F(a,b,L1,....L11) with a,b,L1,L2,....L11 in order to find parameters?

Or maybe I am supposed to go as follows:

F(L1,L2,...L11)=

sum( (u(i)-(L1*X(i) + L2*Y(i) + L3*Z(i) + L4) / (L9*X(i) + L10*Y(i)+ L11*Z(i) + 1))^2+

+ (v(i)-(L5*X(i) + L6*Y(i) + L7*Z(i) + L8) / (L9*X(i) + L10*Y(i)+ L11*Z(i) + 1))^2 )

and now also preform partial derivations of the L1,L2,..L11 unknowns?

I have tried both ways, but it did not seem to be right direction for all kinds of reasons. Also, once I acquire all parameters and try to gain the space coordinates of the unknown point out of two or more cameras picture I am again dealing with more equations than I need. Do I act in a similar fashion as above?

What is the matematical procedure when is MDLT (Modified DLT) concerned,

rather than conventional DLT?

I would be glad to post on the List all answers I recieve, once I collected them.

Thanks in advance for any help/comments.

RESPONSES:

************************************************** *****************************

Dear Tomislav,

The best way to deal with the problem of solving linear equations with

fewer unknowns than equations

(over-determined system) is to use matrix manipulation . You can use

numerical methods to do that.

For example to deal with a system of three equations with two unknowns that

can be represented by:

[A](subscript: 3x2 ){X}(subscript:

2x1 )= {B}(subscript: 3x1)

(where {X}(subscript: 2x1) is the unknown

matrix)

You multiply both sides of the equation by the transpose of [A] to get:

[A](superscript: T)(subscript: 2x3) [A]

(subscript: 3x2 ){X}(subscript: 2x1 )= [A](superscript: T)(subscript: 2x3)

{B}(subscript: 3x1 )

you will end up with a system of two equations with two unknowns that

should be easy to solve:

[A'](subscript: 2x2 ){X}

(subscript: 2x1 )= {B'}(subscript: 2x1)

This can be applied to get the calibration coefficients for each camera and

also to get the 3D coordinates of

the targets from two or more cameras. Let me know if you have any

questions. Good luck.

Ali M. Elhagediab, PhD

Research Scientist

Aerotek Corp. (in contract with General Motors Corp.)

email: aelhaged@notes.gmr.com

************************************************** *****************************

Dear Tomislav:

I was in a similar situation some time ago when I was a Master's student in

Seoul, Korea. I've read a lot of things since then and finally could figure

out what DLT is all about. I even have written a motion analysis package

based on DLT after that.

For camera calibration with n (>6) control points, the system will be

over-determined. Then the linear system looks like this:

X B = Y

where, X = known 2n x 11 matrix, B = transpose of (L1 .... L11), and Y =

known 2n x 1 matrix made of u and v.

Multiply both sides with the transpose of X, X', to make the matrix in front

of B square. This stage is called normal equation:

(X' X) B = X' Y

Then Multiply both sides with the inverse of (X' X) or (X' X)^-1:

(X' X)^-1 (X' X) B = (X' X)^-1 (X' Y)

Then, the left side of the above equation is the same to the least-square

estimate of B:

B = (X' X)^-1 (X' Y)

With only manipulation of the matrices, you will be able to do the least

square estimation.

This procedure is in fact exactly the same to the multiple linear regression

in statistics. Consult any statistics textbook for this procedure: multiple

linear regression using matrix approach.

You may use exactly the same approach to compute the 3-D coordinates of the

unknown points with more than 2 cameras.

In reality, if you include the additional parameters to correct the optical

distortion and the de-centering distortion due to the optical system, the

situation is much more complex than this. I am in the middle of putting

these things on the web, and I'll let you know when it is done.

Hope this to be helpful.

Young-Hoo

--------------------------------------------------------------

Young-Hoo Kwon, Ph.D.

Assistant Professor

Biomechanics Lab, PL 202

Ball State University

Muncie, IN 47306

U.S.A.

Phone: +1 (765) 285-5126 (O), +1 (765) 284-4880 (H)

Internet: ykwon@bsu-cs.bsu.edu

Homepage: http://www.bsu.edu/cast/biomch/kwon/

--------------------------------------------------------------

************************************************** *******************************

(L9*X + L10*Y+ L11*Z + 1)*u = (L1*X + L2*Y + L3*Z + L4)

This is a LINEAR SYSTEM in the L1--L11 unknown.

The coefficients are Xu,Yu, Zyu X Y Z and 1.

The term on the right side is u.

N. Alberto Borghese

************************************************** *******************************

I used the methods as presented by J.S. Walton (1978)

Close range cine-photogrammetry: another approach to motion analysis.

Pages 69-97 in Terauds, J.S., editor, Sciences in Biomechanics

Cinematography, International Congress of Sports Sciences. Del Mar,

California: Academic Publishers.

************************************************** **********************************

> F(a,b)=sum( (y(i)-(a*x(i)+b))^2 ) i=1,...n

> y(i),x(i) coordinates of various points

> a,b parameters of line y=a*x+b.

> Afterwards one takes partial derivate of F(a,b) with a and b in order to compute the parameters of line. One gets two equations with two unknowns and the rest is easy. What I do not understand is how it is applied in case of computing DLT parameters.

> Do I have to write the entire thing in the form of:

>

> F(a,b,L1,L2,...L11)=sum( (v(i)-(a*u(i)+b))^2 )

>

> i=1,...n calibration points

> u(i)=(L1*X(i) + L2*Y(i) + L3*Z(i) + L4) / (L9*X(i) + L10*Y(i)+ L11*Z(i) + 1)

> v(i)=(L5*X(i) + L6*Y(i) + L7*Z(i) + L8) / (L9*X(i) + L10*Y(i)+ L11*Z(i) + 1)?

Take the two DLT equations, and multiply left and right sides by

(L9*X(i) + L10*Y(i)+ L11*Z(i) + 1). Then you have linear equations.

Define F as:

F = sum( (leftside - rightside)^2 )

(sum over all equations, two equations (u,v) for each calibration point).

Fortunately, Matlab has a builtin linear least squares solver (say 'help slash' for

help). You simply collect the coefficients in a matrix, and use the

backslash operator. This was used in the kinemat functions.

> What is the matematical procedure when is MDLT (Modified DLT) concerned,

> rather than conventional DLT?

> I would be glad to post on the List all answers I recieve, once I collected them.

The MDLT has only 10 calibration parameters (not 11), since it assumes that the

u and v axis in image space are perpendicular. This is true for film and video.

With MDLT, you need at least 5 calibration points, but more is recommended

for reliability. Reference:

Chen, L., Armstrong, C.W., Raftopoulos, D.D., (1994) An investigation on the

accuracy of three-dimensional space reconstruction using the direct linear

transformation technique. J. Biomech. 27:493-500.

[Good paper on performance of the DLT using different sets of calibration

points. It is shown that significant improvement can be gained by

increasing the number of calibration points to 16. More than that

does not help much. Some discussion of nonlinearity and how to

correct for that.]

-- Ton van den Bogert

Department of Biomedical Engineering

Cleveland Clinic Foundation

************************************************** *****************************

I use the singular value decomposition (SVD) method to perform linear least

squares. the book Numerical Recipes in C provides C code to perform these

routines. There is also a Numerical Recipes in Pascal, Fortran, etc....

Once you solve the linear least squares procedure to determine the 11 DLT

parameters, you need to rewrite your equations to obtain XYZ in terms of

U,V, and the eleven parameters. In this way you can again use linear least

squares to find the optimum XYZ positions to fit the digitized UV coordinates.

************************************************** *****************************

Dear Tomislav:

As I told you earlier, here is the URL of my DLT page:

http://www.bsu.edu/cast/biomch/kwon/kwon3d/

It has some information on the DLT method and optical distortion-related

stuffs.

Sincerely,

Young-Hoo

--------------------------------------------------------------

Young-Hoo Kwon, Ph.D.

Assistant Professor

Biomechanics Lab, PL 202

Ball State University

Muncie, IN 47306

U.S.A.

Phone: +1 (765) 285-5126 (O), +1 (765) 284-4880 (H)

Internet: ykwon@bsu-cs.bsu.edu

Homepage: http://www.bsu.edu/cast/biomch/kwon/

--------------------------------------------------------------

************************************************** *****************************

Tomislav Pribanic

Faculty of Electrical Engineering and Computing

University of Zagreb

10 000 Zagreb

CROATIA

E-mail:Tomislav.pribanic@zesoi.fer.hr