vwcoefs - calculates the coefficients for an nth order polynomial warp using either QR decomposition or singular-value decomposition (SVD)

vwcoefs [-H] [if=<inputfile>] [of=<outputfile>] [o=<value>] [-s] [-v]

Vwcoefs calculates the coefficients of the best fit polynomial equation to the control points inputted by the user using QR decomposition or singular-value decomposition.

Solves the linear least squares problem Ax=b for x, using the QR orthonormal decomposition..

Given: Ax=b, where A is a matrix of basis functions, x is a vector of unknowns, and b is the solution vector. QR=A, where Q is an orthogormal matrix and R is an upper triangle matrix Q=H1’*H2’*...*Hn’, where H is a Householder Q’=Hn*...*H2*H1 matrix. R=Hn*...*H2*H1*A A is of size m by n x is of size n b is of size m

Find: x, where x is min(norm(Ax-b))

Solution: Ax = b ( M’ denotes transpose of M) QRx = b Q’QRx = Q’b Rx = Q’b Q’Ax = Q’b Hn*...*H2*H1*A*x = Hn*...*H2*H1*b Finally, backsolve for x.

SVD solves the linear least squares problem Ax=b for x, as such:

Given: Ax=b, where A is a matrix of basis functions, x is a vector of unknowns, and b is the solution vector. UWV’=A, where U is an MxN column-orthogonal matrix W is an NxN diagonal matrix and V’ is the transpose of an NxN orthgonal matrix (Note: M’ denotes transpose of M)

Find: x, where x is min(norm(Ax-b)) Solution: Ax = b UWV’x = b U*diag(wj)*V’x = b V*diag(1/wj)*U’U*diag(wj)*V’x = V*diag(1/wj)*U’ x = V*diag(1/wj)*U’

Note that once A is decomposed into U, W, and V, any wj that is lower than some small threshold value should be changed to zero to suppress instability/roundoff error.

if=

are the control points provided by the user. These control points are stored in a 2x(2*N) float image with the format:

sx1 sy1 dx1 dy1 sx2 sy2 dx2 dy2 . . . . . dxN dyN

where N is the total number of control points and source and destination points are interleaved.

of=

is the calculated coefficients which will be used by pwmap to calculate the map file that tells how the pixels are mapped between the input image and the output image. The format is

0 1 2 . . . n y 1 b0 b1 b2 . . . bn x 0 a0 a1 a2 . . . an

o=

is the order of the polynomial. This can be specified to force the polynomial to be of a certain order. If unspecified, the order is automatically calculated by the program. The maximum order is 5 due to the instability of polynomial warping.

-s

specifies the program to solve the linear least square problem using singular value decomposition (SVD) method instead of the default QR decomposition method.

-v

verbose mode prints linear least square error.

vwmap(1), vwarp(1)

Benjamin C. Lee, 1998