Image Transformations
Introduction:
Two dimensional unitary transforms play an important role in image processing. The term image transform refers to a class of unitary matrices used for representation of images.
In analogy with I-D signals that can be represented by an orthogonal series of basis functions , we can similarly represent an image in terms of a discrete set of basis arrays called “basis images”. These are generated by unitary matrices.
Alternatively an image can be represented as vector. An image transform provides a set of coordinates or basis vectors for the vector space.
I-D-Transforms:
For a one dimensional sequence representing a vector of size N , a unitary transform is : =
v(k)=, for (1) (1)
where = (unitary)
This implies , =
or, u(n) = , for 0n (2) Equation (2) can be viewed as a series representation of sequence u(n) . The columns of
i.e the vectors are called the “basis vectors” of .
The series coefficients v(k) give a representation of original sequence u(n) and are useful in compression , filtering , feature extraction and other analysis.
Two dimensional Orthogonal and Unitary transforms:
As applied to image processing, a general orthogonal series expansion for an image is a pair of transformations of the form :
v(k,l) = , (3)
u(m,n) = , (4)
where is called an ” image transform.”
It is a set of complete orthogonal discrete basis functions satisfying the properties:-
1)Orthonormality:
=
2) Completeness :
=
The elements v are transform coefficients and is the transformed image.
The orthonomality property assures that any truncated series expansion of the form
, for ,
will minimize the sum of squares error
where coefficients are given by (3).
The completeness property assures that this error will be zero for
Separable Unitary Transforms:
The number of multiplications and additions required to compute transform coefficients in equation(3) is . This is too large for practical size images.
If the transform is restricted to be separable,
i.e
where ,
and are 1D complete orthogonal sets of basis vectors.
On imposition of completeness and orthonormality properties we can show that ,
and are unitary matrices.
i.e
= = and = =
Often one chooses same as
=
= (5)
And =
= (6)
Eqn (5) can be written as =
Eqn (5) can be performed by first transforming each column of and then transforming each row of the result to obtain rows of
.
Basis Images : Let denote column of .
Let us define the matrices and matrix inner product of two matrices and as
=
Then equ (6) and (5) give a series representation.
=
and =
Any image can be expressed as linear combination of matrices. called “basis images”.
Therefore any image can be expanded in a series using a complete set of basis images.
Example: Let = ; =
Transformed image = =
And Basis images are found as outer product of columns ofi.e
=
=
= =
=
The inverse transformation
=
= =
Dimensionality of Image transforms
The computations for can also be reduced by restricting the choice of to fast transforms. This implies that has a structure that allows factorization of the type,
=
where , , are matrices with just a few non zero entries say where
Therefore a multiplication of the type : = is accomplished in operations.
For several transforms like Fourier, Sine, Cosine, Hadamard etc, , and operations reduce to the order of or (for images).
Depending on the transform, an operation is defined as 1 multiplication + 1 addition.
Or, 1 addition or subtraction as in Hadamard Transform.
Kronecker products:
If andareand matrices we defineKronecker product as:
Consider the transform, =
or, = (7)
If anddenote androw vectors of andthen (1) becomes ,
=
= where is the block of
If and are row ordered into vectors and respectively, then = = ()
The number of operations required for implementing equation(7) reduces from to .
Properties of Unitary transforms:-
1) Energy conservation:
In the unitary transformation, = ,
=
Proof
= =
= .
unitary transformation preserves signal energy or equivalently the length of vector in dimensional vector space. That is , every unitary transformation is simply a rotation of in dimensional vector space. Alternatively , a unitary transform is a rotation of basis coordinates and components of are projections of on the new basis. Similarly , for 2D unitary transformations, it can be proved that
=
Example: Consider the vector = and
=
(diagram)
This , = ; =
Transformation = can be written as
= = =
with new basis as , .
For 2D unitary transforms we have
= .
2) Energy Compaction Property:
Most unitary transforms have a tendency to pack a large fraction of average energy of an image into relatively few transform coefficients. Since total energy is preserved this implies that many transform coefficients will contain very little energy. If and denote the mean and covariance of vector then corresponding quantities for are
= =
And =
=
=
=
Variances of the transform coefficients are given by the diagonal elements of i.e =
=
Since is unitary , it implies:
= =
=
and = =
=
=
The average energyof transform coefficientstends to be unevenly distributed, although it may be evenly distributed for input sequence.
For a 2D random field , with meanand covariance , its transform coefficients
satisfy the properties,
=
=
and =
=
If covariance ofis separable i.e
=
Then variances of transform coefficients can be written as a separable product
=
where = ;
3) Decorrelation : When input vector elements are highly correlated , the transform coefficients tend to be uncorrelated. That is , the off-diagonal terms of covariance matrixtend to be small compared to diagonal elements.
4) Other properties : (a) The determinant and eigenvalues of a unitary matrix have unity magnitute.
(b) Entropy of a random vector is observed under unitary transformation average information of the random vector is preserved.
Example:
Given the entropy of an Gaussian random vector
with mean and covariance , as :
=
To show is invariant under any unitary transformation.
Let =
= =
=
Use the definition of we have
=
=
Now =
=
=
Also = =
=
=
=
=
=