8
$\begingroup$

Direct Linear Transform (DLT for short) is a method of homography estimation, it solves the overdetermined linear system via SVD $$Ah=b$$to find a solution $h$ under constraint $\|h\|=1$. Actually it finds the least square solution which minimize $\|Ah - b\|$.

I understand the basic idea of this algorithm, but it is recommended to normalize the data set before applying DLT on it, and here is a intro about how to do the normalization. It is lectured that data normalization is important to DLT, without normalization the results from DLT is not stable.

I wonder why? Just because DLT involves solving the linear system using SVD and $A$ might be singular?

|improve this question
$\endgroup$
11
$\begingroup$

The normalization is basically a preconditioning to decrease condition number of the matrix $A$ (the larger the condition number, the nearer the matrix is to the singular matrix).

The normalizing transform is also represented by a matrix in the case of homography estimation, and this happens to be usable as a good preconditioner matrix. The reason why is that is more elaborate and is explained briefly in H&Z book (4.4.4, p. 107: Why is normalization essential?) or in more detail in the paper "In Defense of the Eight-point Algorithm".

Put it simply, the matrix $A$ consists of products of image coordinates which can have different scale. If the scale differs by factor of $10$, the products differ by a factor of $10^2$.

The source and target coordinate data are usually noisy. Without normalization, the data from source would can have two orders of magnitude larger variance than from target (or vice versa).

The homography estimation usually finds parameters in a least-squares sense - hence the best statistical estimate is found only if variances of the parameters are the same (or known beforehand, but it is more practical just to normalize the input).

Direct solvers do not like poorly scaled problems because numerical instabilities appear (e.g. dividing very large number by a very small number easily leads to numerical overflow).

Iterative solvers struggle with badly conditioned matrices by needing more iterations.

So normalization is essential not only for numerical stability, but also for more accurate estimation in presence of noise and faster solution (in case of iterative solver).

|improve this answer
$\endgroup$
  • $\begingroup$ And further I wonder why the preconditioned matrix is less singular than before? By standardizing, the condition number of the preconditioned matrix will reduce? $\endgroup$ – avocado Sep 29 '13 at 23:55
  • 1
    $\begingroup$ Because the errors in data will not affect results that much. Imagine estimating position of hand on clock by two points on the clock face. If one point is very near the center and the other is on the border, fluctuations in the position of point near center affects the result significantly while the point on the border affects hand position mildly. Normalization is basically putting both points on the border which makes the solution more stable and puts it further from the center of the clock face (the singularity point). $\endgroup$ – Libor Sep 30 '13 at 18:00
2
$\begingroup$

The Wikipedia article states:

"What makes the direct linear transformation problem distinct..is the fact that the left [X] and right [AY] sides of the defining equation [X = AY] can differ by an unknown multiplicative factor which is dependent on k"

In the above X, A, Y are matrices.

So to avoid having to estimate the factor, you simply normalise all the data you have.

|improve this answer
$\endgroup$
  • $\begingroup$ This doesn't sound right... If we could normalize to make the factor unimportant, the problem could be solved using regular method of $A=XY^T(YY^T)^{-1}$. $\endgroup$ – Michael Litvin Jul 24 '14 at 17:00
1
$\begingroup$

It's a matter of numerical accuracy. By normalizing the data set, you center your data and give it unit variance. These conditions are better handled by the solbver then.

|improve this answer
$\endgroup$
  • $\begingroup$ By better handled by the solver, do you mean when I solve this kind of linear system via SVD, I should always normalize the data set? $\endgroup$ – avocado Sep 29 '13 at 1:39
  • $\begingroup$ Note that normalization affects even the SVD computation (moe stable). You should then get smaller ratios between singular values. Also note the data set is usually noisy and it is better to have same variance for all points to obtain more accurate estimate. $\endgroup$ – Libor Sep 29 '13 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.