Matrix: Yoshiyasu/image_interp

Description: image editting problem, Y. Yoshiyasu, Keio Univ, Japan

 (bipartite graph drawing)

• Home page of the UF Sparse Matrix Collection
• Matrix group: Yoshiyasu
• Click here for a description of the Yoshiyasu group.
• Click here for a list of all matrices
• Click here for a list of all matrix groups
• download as a MATLAB mat-file, file size: 3 MB. Use UFget(2248) or UFget('Yoshiyasu/image_interp') in MATLAB.
• download in Matrix Market format, file size: 4 MB.
• download in Rutherford/Boeing format, file size: 4 MB.

 Matrix properties number of rows 240,000 number of columns 120,000 nonzeros 711,683 structural full rank? yes structural rank 120,000 # of blocks from dmperm 1 # strongly connected comp. 7,516 explicit zero entries 0 nonzero pattern symmetry 0% numeric value symmetry 0% type real structure rectangular Cholesky candidate? no positive definite? no

 author Y Yoshiyasu editor T. Davis date 2009 kind computer graphics/vision problem 2D/3D problem? yes

 Additional fields size and type b full 240000-by-2

Notes:

```The problem is template-mesh deformation to match with silhouettes.  In this
process, there are two kinds of linear systems to solve.  This system
(Yoshiyasu/image_interp) is a smooth vector field construction from images,
which is harmonic interpolation (minimizing laplacian: Lx=0) of intensity
gradient field p.  This can be solved by normal equation and cholesky
factorization, x=(A1'*A1)/(A1'*b1), where A1=[L;C] and
b1=[zeros(size(length(L),1);1);C*p]. C is a square diagonal matrix containing
weights.  This is for a 400x300 image, so Ix=reshape(x,400,300) must be done
to get the vector field. After solving y direction for Iy, the result is
visualized with quiver(Ix,Iy).   At each iteration the both C submatrix and
the right-hand-side change but L remains unchanged.  [Note by T. Davis:
since C is of high rank, update/downdate will not be effective, since it is
meant for low-rank changes.]
```

 Ordering statistics: result nnz(V) for QR, upper bound nnz(L) for LU, with COLAMD 316,991,703 nnz(R) for QR, upper bound nnz(U) for LU, with COLAMD 12,952,004

For a description of the statistics displayed above, click here.

Maintained by Tim Davis, last updated 12-Mar-2014.
Matrix pictures by cspy, a MATLAB function in the CSparse package.
Matrix graphs by Yifan Hu, AT&T Labs Visualization Group.