Tài liệu Image processing P2 doc

Image Processing: The Fundamentals. Maria Petrou and Panagiota Bosdogianni

Copyright 0 1999 John Wiley & Sons Ltd

Print ISBN 0-471-99883-4 Electronic ISBN 0-470-84190-7

Chapter 2

Image Transformations

What is this chapter about?

This chapter is concerned with the development of some of the most important tools

of linear Image Processing, namely the ways by which we express an image as the

linear superposition of some elementary images.

How can we define an elementary image?

We can define an elementary image as the outer product of two vectors.

What is the outer product of two vectors?

Consider two vectors N X 1:

UT = ('&l, U&?, . . . , UiN)

v: = (vjl, vjujz, . . . , VjN)

Their outer product is defined as:

UilVjl UilVj2 . . . UilVjN

Ui2Vjl ui2vj2 . . . T UiVj = (vjl Vj2 VjN ) = (2.1)

UiN UiNVjl uiNvj2 UiNVjN

Therefore, the outer product of these two vectors is an N X N matrix which can be

thought of as an image.

How can we expand an image in terms of vector outer products?

We saw in the previous chapter that a general separable linear transformation of an

image matrix f can be written as:

g = h3 h, (2.2)

22 Image Processing: The Fundamentals

where g is the output image and h, and h, are the transforming matrices.

We can use the inverse matrices of h: and h, to solve this expression for f in

terms of g as follows: Multiply both sides of the equation with (h:)-' on the left and

h;' on the right:

(h, ) gh,' = (h, ) h, f hrh,' = f T T T (2.3)

Thus we write:

f = (h, 1 &,l

T -l (2.4)

Suppose that we partition matrices (h:)-' and h;l in their column and row

vectors respectively:

Then

We may also write matrix g as a sum of N2, N X N matrices, each one having

only one non-zero element:

0 ... 0 912 ... 0 0 0 ... 0

g= 0 '.' i) + (0 0 .'. !) +...+ (0 0 "' 0 ) (2.7)

0 0 ... 0 0 ... 0 0 ... gNN

Then equation (2.6) can be written as:

NN

i=l j=1

This is an expansion of image f in terms of vector outer products. The outer

product uivT may be interpreted as an "image" so that the sum over all combinations

of the outer products, appropriately weighted by the gij coefficients, represents the

original image f.

Image Transformations 23

Example 2.1

Derive the term i = 2, j = 1 in the right hand side of equation (2.8).

If we substitute g from equation (2.7) into equation (2.6), the right hand side oj

equation (2.6) will consist of N2 terms of similar form. One such term is:

0 0 ... 0

(U1 U2 ... UN) (g: 0 .'. i) (':')

0 0 ... VNT

=(U1 U2 ...

U21 ... UN1

U22 ... UN2

'0 0.

921Vll 921v12 .

\o 0.

...

...

...

.' 0) VNN

.. Q21UlN

.. 0

What is a unitary transform?

If matrices h, and h, are chosen to be unitary, equation (2.2) represents a unitary

transform of f, and g is termed the unitary transform domain of image f.

What is a unitary matrix?

A matrix U is called unitary if its inverse is the complex conjugate of its transpose,

i.e.

UUT* = I (2.9)

24 Image Processing: The Fundamentals

where I is the unit matrix. We often write superscript “H” instead of “TP.

of unitary.

If the elements of the matrix are real numbers, we use the term orthogonal instead

What is the inverse of a unitary transform?

If matrices h, and h, in (2.2) are unitary, then the inverse of it is:

f =

For simplicity, from now on we shall write U instead of h, and V instead of h,, so

that the expansion of an image f in terms of vector outer products can be written as:

f = UgVH (2.10)

How can we construct a unitary matrix?

If we consider equation (2.9) we see that for the matrix U to be unitary the re￾quirement is that the dot product of any two of its columns must be zero while the

magnitude of any of its column vectors must be 1. In other words, U is unitary if its

columns form a set of orthonormal vectors.

How should we choose matrices U and V so that g can be represented by

fewer bits than f?

If we wanted to represent image f with fewer than NZ number of elements, then

we could choose matrices U and V so that the transformed image g was a diagonal

matrix. Then we could represent image f with the help of equation (2.8) using only

the N non-zero elements of g. This can be achieved with a process called matrix

diagonalization, and it is called Singular Value Decomposition (SVD) of the image.

How can we diagonalize a matrix?

It can be shown (see box B2.1) that a matrix g of rank r can be written as:

g = UA4VT (2.11)

where U and V are orthogonal matrices of size N X r and A; is a diagonal r X r

matrix.

Image Transformations 25

Example 2.2

If A is a diagonal 2 X 2 matrix and A” is defined by putting all non-zero

elements of A to the power of m, show that:

A-iAA-i = I and A-iAi = I.

Indeed,

This also shows that A-+ A4 = I

Example 2.3 (B)

Assume that H is a 3 X 3 matrix and partition it in a 2 X 3 submatrix

H1 and a 1 X 3 submatrix H2. Show that:

HTH = H,THl+ H,TH2.

Let us say that

Then:

26 Image Processing: The Fundamentals

Adding HFHl and HTH2 we obtain the same answer as before.

Example 2.4

You are given an image which is represented by a matrix g. Show that

matrix ggT is symmetric.

A matrix is symmetric when it is equal to its transpose. Consider the transpose

of SST .

(9gTIT = (STITST = SST

Example 2.5 (B)

Show that if we partition an N X N matrix S into an r X N submatrix

S1 and an (N - r) X N submatrix S2, the following holds:

( S1AST I S1AS,T

S2AST I S2AS,T

SAST= - - - - - I - - - - -

11 where A is an N X N matrix.