image processing - Why normalize the data set before applying Direct Linear Transform

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?

Answer

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).