Digital Image Processing: Unitary Transforms - Duong Anh Duc

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PPT | Số trang:29

Thêm vào BST

Báo xấu

61
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Digital Image Processing: Unitary Transforms - Duong Anh Duc present about Unitary Transforms; Energy conservation with unitary transforms; Karhunen-Loeve transform; Optimum energy concentration by KL transform; Basis images and eigenimages; Sirovich and Kirby method; Gender recognition using eigenfaces.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Digital Image Processing: Unitary Transforms - Duong Anh Duc

Digital Image Processing Unitary Transforms 21/11/15 Duong Anh Duc - Digital Image Processing 1
Unitary Transforms  Sort samples f(x,y) in an MxN image (or a rectangular block in the image) into colunm vector of length MN  Compute transform coefficients   c Af where A is a matrix of size MNxMN 1 *T H  The transform A is unitary, iff A A   A Hermitian conjugate  If A is real-valued, i.e., A1=A*, transform is „orthonormal“ 21/11/15 Duong Anh Duc - Digital Image Processing 2
Energy conservation with unitary transforms    For any unitary transform c Af we obtain  2 H  H H   2 c c c f A Af f  Interpretation: every unitary transform is simply a rotation of the coordinate system.  Vector lengths („energies“) are conserved. 21/11/15 Duong Anh Duc - Digital Image Processing 3
Energy distribution for unitary transforms  Energy is conserved, but often will be unevenly distributed among coefficients.  Autocorrelation matrix   H H H H Rcc E cc E Af f A AR ff A  Mean squared values („average energies“) of the coefficients ci are on the diagonal of Rcc 2 H Ec i Rcc i ,i AR ff A i ,i 21/11/15 Duong Anh Duc - Digital Image Processing 4
Eigenmatrix of the autocorrelation matrix Definition: eigenmatrix of autocorrelation matrix Rff  is unitary  The columns of form an orthonormalized set of eigenvectors of Rff, i.e., Rff 0 0 1  is a diagonal matrix of eigenvalues. 0 MN 1  Rff is symmetric nonnegative H definite,H hence i 0 for all i R ff R ff R ff R ff  Rff is normal matrix, i.e., , hence unitary eigenmatrix exists 21/11/15 Duong Anh Duc - Digital Image Processing 5
Karhunen-Loeve transform  Unitary transform with matrix A= H where the columns of are ordered according to decreasing eigenvalues.  Transform coefficients are pairwise uncorrelated Rcc = ARffAH = HRff = H =  Energy concentration property:  No other unitary transform packs as much energy into the first J coefficients, where J is arbitrary  Mean squared approximation error by choosing only first J coefficients is minimized. 21/11/15 Duong Anh Duc - Digital Image Processing 6
Optimum energy concentration by KL transform  To show optimum energy concentration property, consider the truncated coefficient vector   b IJc where IJ contain ones on the first J diagonal positions, else zeros.  Energy in first J coefficients for arbitrary transform A J 1 E Tr Rbb Tr I J Rcc I J Tr I J AR ff A H I J akT R ff ak* k 0 where akT is the k th row of A.  Lagrangian cost function to enforce unit-length basis vectors J 1 J 1 J 1 L E k 1 akT ak* akT R ff ak* k 1 akT ak* k 0 k 0 k 0  Differentiating L with respect to aj yields neccessary condition R ff a*j * j j for all j a J 21/11/15 Duong Anh Duc - Digital Image Processing 7
Basis images and eigenimages  For any unitary transform, the inverse transform   H f A c can be interpreted in terms of the superposition of „basis images“ (columns of AH) of size MN.  If the transform is a KL transform, the basis images, which are the eigenvectors of the autocorrelation matrix Rff , are called „eigenimages.“  If energy concentration works well, only a limited number of eigenimages is needed to approximate a set of images with small error. These eigenimages form an optimal linear subspace of dimensionality J. 21/11/15 Duong Anh Duc - Digital Image Processing 8
Computing eigenimages from a training set  How to measure MNxMN autocorrelation matrix?     Use training set 1 , 2 ,  , L     Define training set matrix S 1 , 2 , , L and calculate 1 L  H 1 H R l l SS L l 1 L  Problem 1: Training set size should be L >> MN If L < MN, autocorrelation matrix Rff is rank - deficient  Problem 2: Finding eigenvectors of an MNxMN matrix.  Can we find a small set of the most important eigenimages from a small training set L
Sirovich and Kirby method  Instead of eigenvectors of SSH, consider the eigenvectors of SHS, i.e., H   S Svi v i i    Premultiply both sides by S: SS Svi i Svi H   By inspection, we find that Svi are eigenvectors of SSH  For this gives rise to great computational savings, by  Computing the LxL matrix SHS   Computing L eigenvectors Sv of SHS i  Computing eigenimages corresponding to the L0 L largest  eigenvalues according as Svi 21/11/15 Duong Anh Duc - Digital Image Processing 10
Example: eigenfaces  The first 8 eigenfaces obtained from a training set of 500 frontal views of human faces.  Can be used for face recognition by nearest neighbor search in 8-d „face space.“  Can be used to generate faces by adjusting 8 coefficients. 21/11/15 Duong Anh Duc - Digital Image Processing 11
Gender recognition using eigenfaces  Task: Male or female?  Eigenimages from a data base of 20 and 20 female training images 21/11/15 Duong Anh Duc - Digital Image Processing 12
Gender recognition using eigenfaces (cont.)  Recognition accuracy using 8 eigenimages 21/11/15 Duong Anh Duc - Digital Image Processing 13
Block-wise image processing  Subdivide image into small blocks  Process each block independently from the others  Typical blocksizes: 8x8, 16x16 21/11/15 Duong Anh Duc - Digital Image Processing 14
Separable blockwise transforms  Image block written as a square matrix f (NxN coefficients) c = A .f.A T  This can only be done, if transform is separable in x and y, i.e., (N xN ) 2 AT = A A 2  Inverse transform f = A*.c.AH 21/11/15 Duong Anh Duc - Digital Image Processing 15
Haar transform  Haar transform matrix for sizes N=2,4,8 1 1 1 1 1 2 0 2 0 0 0 Hr2 2 1 1 1 1 2 0 2 0 0 0 1 1 2 0 0 2 0 0 1 1 2 0 1 1 1 2 0 0 2 0 0 1 1 1 2 0 Hr8 Hr4 8 1 1 0 2 0 0 2 0 4 1 1 0 2 1 1 0 2 0 0 2 0 1 1 0 2 1 1 0 2 0 0 0 2 1 1 0 2 0 0 0 2  Can be computed by taking sums and differences  Fast algorithms by recursively applying Hr2 21/11/15 Duong Anh Duc - Digital Image Processing 16
Haar transform example Original Cameraman 256x256 Haar transform 256x256 of Cameraman 21/11/15 Duong Anh Duc - Digital Image Processing 17
Haar transform example Original Einstein 256x256 Haar transform 256x256 of Einstein 21/11/15 Duong Anh Duc - Digital Image Processing 18
Haar transform example Original Lena 512x512 Haar transform 512x512 of Lena 21/11/15 Duong Anh Duc - Digital Image Processing 19
Hadamard transform  Transform matrices can be recursively generated 1 1 1 Hd 2 Hr2 2 1 1 Hd 4 Hd 2 Hd 2 Hd 8 Hd 4 Hd 2 Hd 2 Hd 2 Hd 2   Example 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Note that Hadamard 1 1 1 1 1 1 1 1 1 Coefficients need Hd 8 reordering to concentrate 8 1 1 1 1 1 1 1 1 energy 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 21/11/15 Duong Anh Duc - Digital Image Processing 20