Fundamentals of Image Processing

1 Fundamentals of Image Mathematical Foundations .. : : : Vector : : Inner Products and Projections [*] : Linear Transforms [*]1. Discrete-Time Signals and Systems .. : Discrete-Time : Discrete-Time : Linear Time-Invariant Systems2. Linear Time-Invariant Systems .. : Space: Convolution : Frequency: Fourier Transform3. Sampling: Continuous to Discrete (and back) .. : Continuous to Discrete: : Continuous to Discrete: : Discrete to Continuous4. digital Filter Design .. : Choosing a Frequency : Frequency : : Weighted Least-Squares5. Photons to Pixels .. : Pinhole : : CCD6. Point-Wise Operations .. : Lookup : : Gamma : : Histogram Equalize7. Linear Filtering .. : : Derivative : Steerable : Edge : Wiener Filter8. Non-Linear Filtering.

2 : Median : Dithering9. Multi-Scale Transforms [*] .. 6310. Motion Estimation .. : Differential : Differential Stereo11. Useful Tools .. : : Principal Component Analysis [*] : Independent Component Analysis [*][*]In progress0. Mathematical Vector Inner Linear VectorsFrom the preface of Linear Algebra and its Applications: Linear algebra is a fantastic subject. On the one handit is clean and beautiful. Gilbert StrangThis wonderful branch of mathematics is both beautiful and use-ful. It is the cornerstone upon which signal and Image processingis built. This short chapter can not be a comprehensive surveyof linear algebra; it is meant only as a brief introduction and re-view. The ideas and presentation order are modeled after Strang shighly recommended Linear Algebra and its +y=52x y=1(x,y)=(2,3)Figure Row solu-tion(2,1)( 1,1)(1,5)(4,2)( 3,3)Figure Column solutionAt the heart of linear algebra is machinery for solvinglinear equa-tions.

3 In the simplest case, the number of unknowns equals thenumber of equations. For example, here are a two equations intwo unknowns:2x y= 1x+y= 5.(1)There are at least two ways in which we can think of solving theseequations forxandy. The first is to consider each equation asdescribing a line, with the solution being at the intersection of thelines: in this case the point (2,3), Figure This solution istermed a row solution because the equations are considered inisolation of one another. This is in contrast to a column solutionin which the equations are rewritten invectorform: 21 x+ 11 y= 15 .(2)The solution reduces to finding values forxandythatscalethevectors (2,1) and ( 1,1) so that theirsumis equal to the vector(1,5), Figure Of course the solution is againx= 2 andy= solutions generalize to higher dimensions.

4 Here is anexam-ple withn= 3 unknowns and equations:2u+v+w= 54u 6v+ 0w= 2(3) 2u+ 7v+ 2w= equation now corresponds to a plane, and the row solutioncorresponds to the intersection of the planes ( , the intersectionof two planes is a line, and that line intersects the third plane ata point: in this case, the pointu= 1,v= 1,w= 2). In vectorform, the equations take the form:(5, 2,9)Figure Column solution 24 2 u+ 1 67 v+ 102 w= 5 29 .(4)The solution again amounts to finding values foru,v, andwthatscale the vectors on the left so that their sum is equal to the vectoron the right, Figure the context of solving linear equations we have introduced thenotion of avector,scalar multiplicationof a vector, andvectorsum. In its most general form, an-dimensionalcolumn vectorisrepresented as:~x= ,(5)and an-dimensionalrow vectoras:~y= (y1y2.)

5 Yn).(6)Scalar multiplicationof a vector~xby a scalar valuec, scales thelength of the vector by an amountc(Figure ) and is given by:c~v= .(7)Thevector sum~w=~x+~yis computed via the parallelogramconstruction or by stacking the vectors head to tail (Figure )and is computed by a pairwise addition of the individual vectorcomponents: = x1+y1x2+ +yn .(8)Thelinear combinationof vectors by vector addition and scalarmultiplication is one of the central ideas in linear algebra(moreon this later). MatricesIn solvingnlinear equations innunknowns there are three quan-tities to consider. For example consider again the following set ofequations:2u+v+w= 54u 6v+ 0w= 2(9) 2u+ 7v+ 2w= the right is the column vector: 5 29 ,(10)and on the left are the three unknowns that can also be writtenas a column vector: uvw.

6 (11)The set of nine coefficients (3 rows, 3 columns) can be written inmatrixform: 2 1 14 6 0 2 7 2 (12)Matrices, like vectors, can be added and scalar , since we may think of a vector as a skinny matrix:amatrix with only one column. Consider the following 3 3 matrix:A= a1a2a3a4a5a6a7a8a9 .(13)The matrixcA, wherecis a scalar value, is given by:cA= ca1ca2ca3ca4ca5ca6ca7ca8ca9 .(14)And the sum of two matrices,A=B+C, is given by: a1a2a3a4a5a6a7a8a9 = b1+c1b2+c2b3+c3b4+c4b5+c5b6+c6b7+c7b8+c8 b9+c9 .(15)5 With the vector and matrix notation we can rewrite the threeequations in the more compact form ofA~x=~b: 2 1 14 6 0 2 7 2 uvw = 5 29 .(16)Where the multiplication of the matrixAwith vector~xmust besuch that the three original equations are reproduced.

7 The firstcomponent of the product comes from multiplying the first rowofA(a row vector) with the column vector~xas follows:( 2 1 1 ) uvw = ( 2u+ 1v+ 1w).(17)This quantity is equal to 5, the first component of~b, and is simplythe first of the three original equations. The full product iscom-puted by multiplying each row of the matrixAwith the vector~xas follows: 2 1 14 6 0 2 7 2 uvw = 2u+ 1v+ 1w4u 6v+ 0w 2u+ 7v+ 2w = 5 29 .(18)In its most general form the product of am nmatrix with andimensional column vector is amdimensional column vectorwhoseithcomponent is:nXj=1aijxj,(19)whereaijis the matrix component in theithrow sum along theithrow of the matrix is referred to as theinnerproductordot productbetween the matrix row (itself a vector) andthe column vector~x.

8 Inner products are another central idea inlinear algebra (more on this later). The computation for multi-plying two matrices extends naturally from that of multiplying amatrix and a vector. Consider for example the following 3 4 and4 2 matrices:A= a11a12a13a14a21a22a23a24a31a32a33a34 andB= b11b12b21b22b31b32b41b42 .(20)The productC=ABis a 3 2 matrix given by: a11b11+a12b21+a13b31+a14b41a11b12+a12b22 +a13b32+a14b42a21b11+a22b21+a23b31+a24b4 1a21b12+a22b22+a23b32+a24b42a31b11+a32b2 1+a33b31+a34b41a31b12+a32b22+a33b32+a34b 42!.(21)6 That is, thei, jcomponent of the productCis computed froman inner product of theithrow of matrixAand thejthcolumnof matrixB. Notice that this definition is completely consistentwith the product of a matrix and vector. In order to multiplytwo matricesAandB(or a matrix and a vector), the columndimension ofAmust equal the row dimension ofB.

9 In other wordsifAis of sizem n, thenBmust be of sizen p(the product isof sizem p). This constraint immediately suggests that matrixmultiplication is not commutative: usuallyAB6=BA. Howevermatrix multiplication is both associative (AB)C=A(BC) anddistributiveA(B+C) =AB+ matrixIis a special matrix with 1 on the diagonaland zero elsewhere:I= 1 0..0 00 1..0 0..0 1 .(22)Given the definition of matrix multiplication, it is easily seen thatfor any vector~x,I~x=~x, and for any suitably sized matrix,IA=AandBI= the context of solving linear equations we have introduced thenotion of avectorand amatrix. The result is a compact notationfor representing linear equations,A~x=~b. Multiplying both sidesby thematrix inverseA 1yields the desired solution to the linearequations:A 1A~x=A 1~bI~x=A 1~b~x=A 1~b(23)A matrixAisinvertibleif there exists1a matrixBsuch thatBA=IandAB=I, whereIis the identity matrix.

10 The ma-trixBis the inverse ofAand is denoted asA 1. Note that thiscommutative property limits the discussion of matrix inverses tosquare all matrices have inverses. Let s consider some simple exam-ples. The inverse of a 1 1 matrixA= (a) isA 1= ( 1/a);but the inverse does not exist whena= 0. The inverse of a 2 21 The inverse of a matrix is unique: assume thatBandCare both theinverse of matrixA, then by definitionB=B(AC) = (BA)C=C, so thatBmust can be calculated as: a bc d 1=1ad bc d b c a ,(24)but does not exist whenad bc= 0. Any diagonal matrix isinvertible:A= andA 1= 1 ,(25)as long as all the diagonal components are non-zero. The inverseof a product of matricesABis (AB) 1=B 1A 1. This is easilyproved using the associativity of matrix of an arbitrary matrix, if it exists, can itself be calculatedby solving a collection of linear equations.