08-01-2013, 11:06 AM
Unitary Transforms
Unitary Transforms.ppt (Size: 491.5 KB / Downloads: 25)
Why Do Transforms?
Fast computation
E.g., convolution vs. multiplication for filter with wide support
Conceptual insights for various image processing
E.g., spatial frequency info. (smooth, moderate change, fast change, etc.)
Obtain transformed data as measurement
E.g., blurred images, radiology images (medical and astrophysics)
Often need inverse transform
May need to get assistance from other transforms
For efficient storage and transmission
Pick a few “representatives” (basis)
Just store/send the “contribution” from each basis
Properties of 1-D Unitary Transform
Energy Compaction
Many common unitary transforms tend to pack a large fraction of signal energy into just a few transform coefficients
Decorrelation
Highly correlated input elements quite uncorrelated output coefficients
Covariance matrix E[ ( y – E(y) ) ( y – E(y) )*T ]
small correlation implies small off-diagonal terms
Example: recall the effect of DFT
Question: What unitary transform gives the best compaction and decorrelation?
Will revisit this issue in a few lectures
2-D DCT
Separable orthogonal transform
Apply 1-D DCT to each row, then to each column
Y = C X CT X = CT Y C = mn y(m,n) Bm,n
DCT basis images:
Equivalent to represent an NxN image with a set of orthonormal NxN “basis images”
Each DCT coefficient indicates the contribution from (or similarity to) the corresponding basis image
Summary and Review (1)
1-D transform of a vector
Represent an N-sample sequence as a vector in N-dimension vector space
Transform
Different representation of this vector in the space via different basis
e.g., 1-D DFT from time domain to frequency domain
Forward transform
In the form of inner product
Project a vector onto a new set of basis to obtain N “coefficients”
Inverse transform
Use linear combination of basis vectors weighted by transform coeff. to represent the original signal
2-D transform of a matrix
Rewrite the matrix into a vector and apply 1-D transform
Separable transform allows applying transform to rows then columns
Clarifications
“Dimension”
Dimension of a signal ~ # of index variables
audio and speech is 1-D signal, image is 2-D, video is 3-D
Dimension of a vector space ~ # of basis vectors in it
Eigenvalues of unitary transform
All eigenvalues have unit magnitude (could be complex valued)
By definition of eigenvalues ~ A x = x
By energy perservation of unitary ~ | A x | = |x|
Eigenvalues here are different from the eigenvalues in K-L transform
K-L concerns the eigen of covariance matrix of random vector
Eigenvectors ~ we generally consider the orthonormalized ones