New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Circuits 1

by: Maudie Quitzon

Circuits 1 EE T220

Maudie Quitzon
GPA 3.98


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in Electrical Engineering

This 81 page Class Notes was uploaded by Maudie Quitzon on Saturday September 12, 2015. The Class Notes belongs to EE T220 at West Virginia University taught by Staff in Fall. Since its upload, it has received 34 views. For similar materials see /class/202860/ee-t220-west-virginia-university in Electrical Engineering at West Virginia University.

Similar to EE T220 at WVU

Popular in Electrical Engineering


Reviews for Circuits 1


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/12/15
Computable General Equilibrium CGE Models A Short Course Hodjat Ghadimi Regional Research Institute WWWRRIWVUEDU Spring 2007 Session Two SPECIFICATION Session 2 Speci cation A taxonomy of models Components of a simple CGE Mathematical model statement Review CGE Keywords Multisectoral Nonlinear Economywide Autonomous decision making Walrasian competitive equilibrium Structure of a C JE modal Circular Flow of Income PAYMENTS TO CAPITAL AW LABOR FACTOR PAVMEN39I S OIL REVENUES INDIRECY TAXE INTERMEDMTE INPUTS DEPRECIATION GOV SAVINGS mamsms 7 PRNATE SAVINGS GOV CONSUme mam man0 a arma CONSUMPTION FOREIGK 3AVINGS A taxonomy of models A taxonomy of models Models and Policy Analysis I Policy makers intend to change the way the economy operates rather than just understand it I Policy analysis explain the links between instruments and targets Modelbuilding the process of abstraction and generalization required to provide structure to our empirical observation A taxonomy of models Economic Models Analytic models Stylized numerical models Applied models A taxanomy of madcalis WWI Apply timoretical framewark amp sh stiml me mds a lter nut inessen al details Focus on imgartant mmp ms mum mechanisms Attach numbers tn the variabla a relate them in economic per armance Include mam details mume swim A taxonomy of models Illllllll Wptlnn of reality Strategic Policy Analysis Detailed A taxonomy of models Analytic models I Cast economic relationships into a form susceptible to mathematical analysis Explore the implications of various sets of postulates Deliberater simpli ed to focus on important assumptions and causal mechanisms Empirical realism not an important criterion A taxonomy of models Stylized numerical models Attach numbers to the variables and relate them to economic statistics Larger more complex amp more realistic Used to analyze problems too dif cult to solve analytically Empirical able to explore the size of various effects I Give up simplicity to gain in applicability amp generality A taxonomy of models Applied models Include broader range of stylized facts More speci c and narrow in application Include more institutional details Additional details may obscure the major causal mechanisms without adding any empirically signi cant effects A taxonomy of models CGE models fall into both stylized and applied categories a In addition CGE models I Have strong links with basic economic theory I Work by simulating the interaction of various actors as speci ed in neoclassical general equilibrium theory Derive behavior based on optimization as speci ed in microtheory Are fully clo quotin that the supply and demand sides of all markets are speci ed Components of a simple CGE See a SAM structure Mathematical model statement I 123 MOdEI Graphical Analysis Equations of an applied model Mathematical model statement 123 Model I Capture mechanisms by which external shocks and domestic policies ripple through the economy Many problems and solutions are related to links between external sectors and domestic economy Based on DevarajanGoLewisRonbinson Sinko 1997 Mathematical model statement 123 Model a 1 country 2 activities 3 commodities 2 activities producing D and E u E not consumed domestically Additional commodity M consumed domestically but not produced Mathematical model statement 123 Model Very simplistic stylized model but Mechanisms are transparent Can be solved graphically analytically or with Excel Behavior is similar to that of more complex models Mathematical model statement 123 Model Aggregate GDP X is xed Full employment model Trade balance set exogenously World prices of M and E are xed Total absorption Q is endogenous Mathematical model statement Flows 1GEDSQ f1P Pd 11 R E 1 Equilibrium Conditions 12 DD DS 0 13 QD QS 0 6 YZPXDXRDB 14pmeM pweDEB Mathematical model statement Basic 123 CGE Model Identities 15 PXDX a PM PdDDS 16 PqEQS a P quotDMPdDDD 17 Y5 PqKQD Mathematical model statement Basic 123 CGE Model Endogenous Variables PK Price of aggregate output E Export good Pq Price of composite good M Import good R Exchange rate D5 Supply of domestic good D Demand for domestic good Exogenous Variables Q5 Supply of composite good pwe world price of export good QD Demand for composite good pwm world price of import good Y Total income B Balance of trade PB Domestic price of expert good 0 Import substitution elasticity Pm Domestic price of import good Q Export transformation Pd Domestic price of domestic ElastiCitY good SAM for 123 Model Mathematical model statement EDkPEPD9 PE Rpwe Mathematical model statement MD k PD PM PM R39pwm 123 Programming Model Maximize Q FMD039 with respect to M E DD DS subject to Shadow Prices 1 GE D539 3 2 technology xi Pquot P 1 2 pw M S pwquot E 5 balance of trade itl R P 1 3 DD 3 DS domestic market itd Pd P 1 Mathematical model statement 123 Model PDP Balance of Trade Domestic Market Mathematical model statement Balance of Trade Domes c Market Mathematical model statement 123 CGE Model with Consumption Government and Investment Shantayanan Devarajan Del n S Go Jeffrey D Lewis Sherman Robinson Pekka Sinko Mathematical model statement 123 CGE Model Real Flows 1GEDSQ 2 QS FMDD0 3 QB CZG 4 g g2PePd 5 f219m13d 123 CGE Model 6 T tmDRDpmeM t 1DP 1QD REY teDPeDE 7 Y PXDXtrDPq reDR 8S DYRDl 3Sg 9 CUP 1 t quotDY Mathematical model statement 123 CGE Model Prices 10 P quot 1 DRDpw quot 11 Pe1teRDpwe 12 P 1z 1DP 1 13 P gl 19610quot 14 P9 flP quotPd 151351 123 CGE Model Equilibrium Conditions 16 DD DS 0 17 QD Q 0 18pmeM pweDE ft reB 19 PZDZ S20 20 T PqEG zrmpq DR Sg 0 123 CGE Model Identities 21PXDXEP6DEPquotDDS 22 P IEQS a PmDMPdDDD Endogenous Variables E Export good M Import good DS Supply of domestic good DD Demand for domestic good QS Supply of composite good QD Demand for composite good Pe Domestic price of export good Pm Domestic price of import good Pd Domestic price of domestic good PX Price of aggregate output Pq Price of composite good Pt Sale price of composite good R Exchange rate T Tax revenue Sg Government savings Y Total income C Aggregate consumption S Aggregate savings Z Aggregate real investment Exogenous Variables pwe world price of export good pwm world price of import good tm Tariff rate tX Export tax rate tq Sales tax rate ty Direct tax rate tr Government transfers real ft Foreign transfers to government re Foreign remittances to private sector 3 Average savings rate X Aggregate output GDP G Real government demand B Balance of trade 6 Import substitution elasticity 9 Export transformation elasticity IRAN CGE Structure of a S SE modal Signals prices in a market economy COBBD3UGLAS Digital Image Processing SecandEdilian Review Material Rafael C Gonzalez Richard E Woods Prentice Hall Upper Saddle River NJ 07458 wwwprenhallcomgonzalezwoods or wwwim ageprocessingbookcom Revision history 10 9 8 7 6 5 4 3 2 1 Copyright 19922002 by Rafael C Gonzalez and Richard E Woods Preface The purpose of this brief review is to provide the reader with the necessary background to follow material in the book dealing with matrices and vectors probability and linear systems The review is divided into three main sections each dealing one of the three preceding topics The following material is highly focused to the needs of someone needing a refresher in one of these topics Whenever possible we have used the same notation employed in the text Contents Preface iii 1 A Brief Review of Matrices and Vectors 1 11 Matrices 1 12 Vectors and Vector Spaces 4 13 Eigenvalues and Eigenvectors 9 2 A Brief Review of Probability and Random Variables 13 21 Sets and Set Operations 13 22 Relative Frequency and Probability 16 23 Random Variables 21 24 Expected Value and Moments 24 25 The Gaussian Probability Density Function 26 26 Several Random Variables 27 27 The Multivariate Gaussian Density 29 vi Contents 28 Linear Transformations of Random Vectors 31 3 A Brief Overview of Linear Systems 33 31 Introductory Definitions 33 32 Linear System CharacterizationConvolution 35 1 A Brief Review of Matrices 11 Matrices and Vectors The purpose of this short document is to provide the reader with background suf cient to follow the discussions inDigital Image Processing 2nd ed by Gonzalez and Woods The notation is the same that we use in the book Introductory Definitions We begin with the de nition of a matrix An m X 71 read m by 71 matrix denoted by A is a rectangular array of entries or elements numbers or symbols representing numbers enclosed typically by square brackets In this notation m is the number of horizontal rows and n the number of vertical columns in the array Sometimes m and n are referred to as the dimensions or order of the matrix and we say that matrix A has dimensions m by n or is of order m by n We use the following notation to represent an m X 71 matrix A 111 112 39 39 39 aln 121 122 39 39 39 1127 A aml am2 39 39 39 amn where aij represents the i7 jth entry If m n then A is a square matrix If A is square and aij 0 for all i 7E j and not all a are zero the matrix is said to be diagonal In other words a diagonal matrix is a square matrix in which all elements not on the main diagonal are zero A diagonal matrix in which all diagonal elements are equal to l is called the identity matrix typically denoted by I A matrix in which all elements are 0 is called the zero or null matrix typically denoted by 0 The trace of a matrix A not necessarily diagonal 2 Chapter 1 A Brief Review of Matrices and Vectors denoted trA is the sum of the elements in the main diagonal of A Two matrices A and B are equal if and only if they have the same number of rows and columns and aij bij for alli andj The transpose of an m X 71 matrix A denote AT is an n X m matrix obtained by interchanging the rows and columns of A That is the rst row of A becomes the rst column of AT the second row of A becomes the second column of AT and so on A square matrix for which AT A is said to be symmetric Any matrix X for which XA I and AX I is called the inverse of A Usually the inverse of A is denoted A l Although numerous procedures exist for computing the inverse of a matrix the procedure usually is to use a computer program for this purpose so we will not dwell on this topic here The interested reader can consult any book an matrix theory for extensive theoretical and practical discussions dealing with matrix inverses A matrix that possesses an inverse in the sense just de ned is called a nansingular matrix Associated with matrix inverses is the computation of the determinant of a matrix Al though the determinant is a scalar its de nition is a little more complicated than those discussed in the previous paragraphs Let A be an m X m square matrix The i7 j minar of A denoted Mij deleting the 2th row and the jth column of A The i7 jc0fact0r of A denoted Cij is 71 739Mij The determinant ofa 1 X 1 matrix a denoted det is det 04 1 Finally we de ne the determinant of an m X m matrix A as m det A Zaljolj 3973971 In other words the determinant of a square matrix is the sum of the products of the is the determinant ofthe m7 1 X m7 1 matrix formed by elements in the rst row of the matrix and the cofactors of the rst row As is true of inverses determinants usually are obtained using a computer Basic Matrix Operations Let c be a real or complex number often called a scalar The scalar multiple of scalar c and matrix A denoted cA is obtained by multiplying every elements of A by c If c 7 1 the scalar multiple is called the negative of A Assuming that they have the same number of rows and columns the sum of two matrices A and B denoted A B is the matrix obtained by adding the corresponding elements 3 of the two matrices In other words the sum is an m X 71 matrix whose i jth element is lij HiSimilarly the d erence of two matrices denoted A 7 B has elements aij 7 bi The product AB ofm X 71 matrix A andp gtlt q matrix B is an m X q matrix C whose i jth element is formed by multiplying the entries across the 1th row of A times the entries down the jth column of B In other words Cij ailblj 12392sz ambpj fori 1 2 m andj 1 2 q We see from the preceding equation that matrix multiplication is de ned only if n and p are equal Also as will be shown shortly the sum of products just described is equal to the socalled inner product of rows of A with columns of B Finally we note that division of one matrix by another is not de ned Example 11 Suppose that B 124 13139 71742 5121439 Later in this discussion we will make use of matrix products in which matrix B has Then 0 only one column A simple example is lizllxl Also of special interest are products in which matrices consist of only one row or one am 1112 can dang I column appropriately called row and column matrices respectively In subsequent discussions we refer to these as row vectors or column vectors respectively and denote them by lowercase bold letters with the understanding that they are row or column matrices For example consider two column vectors a and b of dimension m X 1 as follows 0 1 a2 a am and 4 Chapter 1 A Brief Review of Matrices and Vectors b1 112 b m Keeping in mind the matrix dimensions required for matrix products de ned above the product of a and b is a 1 X 1 matrix given by aTb bTa 21111 12112 ambm m Zaibi 11 This particular product is often called the dot or inner product of two vectors We have much more to say about this in the following section B 12 Vectors and Vector Spaces Vectors As introduced in the previous section we refer to an m X 1 column matrix as a column vector Such a vector assumes geometric meaning when we associate geometrical prop erties with its elements For example consider the familiar twodimensional Euclid ean space in which a point is represented by its ac7 y coordinates These coordinates can be expressed in terms of a column vector as follows Geometrically we represent this vector as a directed line segment from the origin to point 17 2 In threedimensional space the vector would have components ac7 y In mdim ensional space we run out of letters and use the same symbol with subscripts to represent the elements of a vector That is an mdimensional vector is represented as 12 Vectors and Vector Spaces 5 When expressed in the form of these column matrices arithmetic operations between vectors follow the same rules as they do for matrices The product of a vector by scalar is obtained simply by multiplying every element of the vector by the scalar The sum of two vectors x and y is formed by the addition of corresponding elements 11 111 2 12 and so on and similarly for subtraction Multiplication of two vectors is as de ned in Example 1 Division of one vector by another is not de ned Vector Spaces De nition of a vector space is both intuitive and straightforward A vector space is de ned as a nonempty set V of entities called vectors and associated scalars that satisfy the conditions outlined in A through C below A vector space is real if the scalars are real numbers it is complex if the scalars are complex numbers Condition A There is in V an operation called vector addition denoted x y that satis es 1 x y y x for all vectors x and y in the space 2 x yz xyzforallx y andz 3 There exists in V a unique vector called the zero vector and denoted 0 such that x0xand0xxforallvectorsx gt For each vector x in V there is a unique vector in V called the negation of x and denoted 7x such that x 7x 0 and 7x x Condition B There is in V an operation called 1 39l 139 In a scalarthm 2 nriate with each scalar c and each vector x in V a unique vector called the product of c and x denoted by ex and xc and which satis es 1 Cdx colx for all scalars c and d and all vectors x 2 c dx cx dx for all scalars c and d and all vectors x 3 CX y cx cy for all scalars c and all vectors x and y Condition C 1x x for all vectors x We are interested particularly in real vector spaces of real m X 1 column matrices with vector addition and multiplication by scalars being as de ned earlier for matrices We shall denote such spaces by 8 Using the notation introduced previously vectors col 6 Chapter 1 A Brief Review of Matrices and Vectors umn matrices in W are written as Example 12 The vector space with which we are most familiar is the twodimensional real vector space 8 32 in which we make frequent use of graphical representations for operations such as vector addition subtraction and multiplication by a scalar For Fifi rpm Using the rules of matrix addition and subtraction we have Figure 11 shows the familiar graphical representation of these operations as well as instance consider the two vectors and and multiplication of vector 21 by scalar c 705 D Consider two real vector spaces V0 and V such that 1 Each element of V0 is also an element of V ie V0 is a subset of V 2 Operations on elements of V0 are the same as on elements of V Under these conditions V0 is said to be a subspace of V A linear combination ofvectors v1 v2 vn is an expression of the form a1v1 agvz anvn where the os are scalars A vector v is said to be linearly dependent on a set S of vectors v1vQ7 vn if and only if v can be written as a linear combination of these vectors Otherwise v is linearly independent of the set of vectors v1 vQ 7vn l 12 Vectors and Vector Spaces A set S of vectors v1vQ7 only if S is a subset of V0 and every vector v0 in V0 is linearly dependent on the vectors 4 3 r39 r a b l 2 h r39 1 Ir 1 2 3 V 05 a r a ll 39 b 1 Figure 11 vn in V is said to span some subspace V0 of V if and in S The set S is said to be a spanning set for V0 A basis for a vector space V is a linearly independent spanning set for V The number of vectors in the basis for a vector space is called the dimension of the vector space If for example the number of vectors in the basis is n we say that the vector space is ndimensional An important aspect of the concepts just discussed lies in the representation of any vector in W as a linear combination of the basis vectors For example any vector 8 33 can be represented as a linear combination of the basis vectors 0 0 1 and 0 0 1 8 Chapter 1 A Brief Review of Matrices and Vectors Vector Norms A vector norm on a vector space V is a function that assigns to each vector v in V a nonnegative real number called the norm of v denoted by By de nition the norm satis es the following conditions 1 gt 0 forv 7E 0 07 2 Hch ici for all scalars c and vectors v and 3 in Vii S iiuii M There are numerous norms that are used in practice In our work the norm most often used is the socalled 2norm which for a vector x in real 8 space is de ned as 1 2 iixiix x xii The reader will recognize this expression as the Euclidean distance from the origin to point x which gives this expression the familiar name of the Euclidean norm The expression also is recognized as the length of a vector x with origin at point 0 Based on the multiplication of two column vectors discussed earlier we see that the norm also can be written as HxH xTx12 The well known CauchySchwartz inequality states that T IX VI S M Hyii In words this result states that the absolute value of the inner product of two vectors never exceeds the product of the norms of the vectors This result is used in several places in the book Another wellknown result used in the book is the expression cos 9 i HXH HYH where 9 is the angle between vectors x and y from which we have that the inner product of two vectors can be written as XTy iixii iiyii 6 Thus the inner product of two vectors can be expressed as a function of the norms of the vectors and the angle between the vectors From the preceding results we have the de nition that two vectors in W are orthogonal if and only if their inner product is zero Two vectors are orthonormal if in addition to being orthogonal the length of each vector is 1 From the concepts just discussed 13 Eigenvalues and Eigenvectors 9 we see that an arbitrary vector a is turned into a vector an of unit length by performing the operation an a Hall Clearly then anH 1 A set of vectors is said to be an orthogonal set if every two vectors in the set are orthogonal A set of vectors is orthonormal if every two vectors in the set are orthonormal Some Important Aspects of Orthogonality Let B V1VQ 7vn be an orthogonal or orthonormal basis in the sense de ned in the previous section Then an important result in vector analysis is that any vector v can be represented with respect to the orthogonal basis B as vor1v1 a2vz Ornvn where the coef cients are given by 04239 The key importance of this result is that if we represent a vector as a linear combination of orthogonal or orthonormal basis vectors we can determine the coef cients directly from simple inner product computations It is possible to convert a linearly independent spanning set of vectors into an orthogonal spanning set by using the wellknown Gram Schmidt process There are numerous programs available that implement the Gram Schmidt and similar processes so we will not dwell on the details here 13 Eigenvalues and Eigenvectors Properties of eigenvalues and eigenvectors are used extensively in Digital Image Process ing 2nd ed The following discussion is a brief overview of material fundamental to a clear understanding of the relevant material discussed in the book We will limit discus sion to real numbers but the following results also are applicable to complex numbers De nition The eigenvalues of a real matrix M are the real numbers for which there is a nonzero vector e such that Me e The eigenvectors of M are the nonzero vectors e for which there is a real number such that Me e If Me e for e 7E 0 then e is an eigenvector of M associated with eigenvalue A and vice versa The eigenvectors and corresponding eigenvalues of M constitute the eigensystem of M Numerous theoretical and truly practical results in the application of matrices and vectors stem from this beautifully simple de nition 10 Chapter 1 A Brief Review of Matrices and Vectors Example 13 Consider the matrix WES It is easy to verify that Mel 1e1 and M62 Ageg for 1 1 A2 2 and In other words e1 is an eigenvector of M with associated eigenvalue 1 and similarly for e2 and A2 D The following properties which we give without proof are essential background in the use of vectors and matrices in digital image processing In each case we assume a real matrix of order m X m although as stated earlier these results are equally applicable to complex numbers We focus on real quantities simply because they play the dominant role in our work 1 If1 A2 Ag q 3 m7 is set of distinct eigenvalues of M and ei is an eigenvec tor ofM with corresponding eigenvalue M i 17 2 7q7 then e17 e2 eq is a linearly independent set of vectors Note an important implication of this property If an m X m matrix M has m distinct eigenvalues its eigenvectors will constitute an orthogonal orthonormal set which means that any mdim ensional vector can be expressed as a linear combination of the eigenvectors of M 2 The numbers along the main diagonal of a diagonal matrix are equal to its eigenval ues It is not di icult to show using the de nition Me e that the eigenvectors can be written by inspection when M is diagonal 3 A real symmetric m X m matrix M has a set of m linearly independent eigenvec tors that may be chosen to form an orthonormal set This property is of particular importance when dealing with covariance matrices eg see Section 114 and our review of probability which are real and symmetric 4 A corollary of Property 3 is that the eigenvalues of an m X m real symmetric matrix are real and the associated eigenvectors may be chosen to form an orthonormal set of m vectors V Suppose that M is a real symmetric m X m matrix and that we form a matrix A whose rows are the m orthonormal eigenvectors of M Then the product AAT I because the rows of A are orthonormal vectors Recall from the discussion on matrix multiplication that the product of two matrices is form ed by the inner product of the rows of one matrix with the column of the other Since the rows of A and columns of AT are orthonormal their inner products are either 0 or 1 Thus we see 13 Eigenvalues and Eigenvectors 11 that A 1 AT when matrix A is formed as wasjust described 6 Consider matrices M and A as de ned in 5 Then the product D AMA 1 AMAT is a diagonal matrix whose elements along the main diagonal are the eigen values of M The eigenvectors of D are the same as the eigenvectors of M Example 14 Suppose that we have a random population of vectors denoted by with covariance matrix see the following chapter on a review of probability Cx Ex 7 mxx 7 mxT where E is the expected value operator and 111K is the mean of the population Covari ance matrices are real square symmetric matrices which from Property 3 are known to have a set of orthonormal eigenvectors Suppose that we perform a transformation of the form y Ax on each vector x where the rows of A are the orthonormal eigenvectors of Cx The covariance matrix of the population y is Cy Eiy myy myTi EAx 7 AmxAx 7 AmxT EAltx 7 mxgtltx 7 moTAT AEX 7 mxx 7 mxTAT ACXAT where A was factored out of the expectation operator because it is a constant matrix From Property 6 we know that Cy ACxAT is a diagonal matrix with the eigenval ues of Cx along its main diagonal Recall that the elements along the main diagonal of a covariance matrix are the variances of the components of the vectors in the popu lation Similarly the off diagonal elements are the covariances of the components of these vectors The fact that the covariance Cy is diagonal means that the elements of the vectors in the population y are uncorrelated their covariances are 0 Thus we see that application of the linear transformation y Ax involving the eigenvectors of Cx decorrelates the data and the elements of Cy along its main diagonal give the variances of the components of the y s along the eigenvectors Basically what has been accom plished here is a coordinate transformation that aligns the data along the eigenvectors of the covariance matrix of the population The preceding concepts are illustrated in Fig 12 Figure 12a shows a data population x in two dimensions along with the eigenvectors of Cx the black dot is the mean The result of performing the transformation y Ax 7 mx on the x s is shown in 12 Chapter 1 A Brief Review of Matrices and Vectors Fig 12b The fact that we subtracted the mean from the x s caused the y s to have zero mean so the population is centered on the coordinate system of the transformed data It is important to note that all we have done here is make the eigenvectors the new coordinate system 111112 Because the covariance matrix of the y s is diagonal this in fact also decorrelated the data The fact that the main data spread is along e1 is due to the fact that the rows of the transformation matrix A were chosen according the order of the eigenvalues with the rst row being the eigenvector corresponding to the largest eigenvalue D x2 J e 39 3 1 e1 y 1 a b Figure 12 2 A Brief Review of Probability and Random Variables The principal objective of the following material is to start with the basic principles of probability and to bring the reader to the level required to be able to follow all probabilitybased developments in the book 21 Sets and Set Operations Probability events are modeled as sets so it is customary to begin a study of probability by de ning sets and some simple operations among sets Sets Informally a set is a collection of objects with each object in a set often referred to as an element or member of the set Familiar examples include the set of all image processing books in the world the set of prime numbers and the set of planets circling the sun Typically sets are represented by uppercase letters such as A B and C and members of sets by lowercase letters such as a b and c We denote the fact that an element 2 belongs to set A by a E A If a is not an element of A then we write a A A set can be speci ed by listing all of its elements or by listing properties common to all elements For example suppose that I is the set of all integers A set B consisting the rst ve nonzero integers is speci ed using the notation B 1234 5 The set of all integers less than 10 is speci ed using the notation CCEIlclt10 14 Chapter 2 A Brief Review of Probability and Random Variables which we read as C is the set of integers such that each members of the set is less than 10 The such that condition is denoted by the symbol l and as is shown in the previous two equations the elements of the set are enclosed by curly brackets The set with no elements is called the empty or null set which we denote by 0 Two sets A and B are said to be equal if and only if they contain the same elements Set equality is denoted by A B If the elements of two sets are not the same we say that the sets are not equal and denote this by A 7E B If every element of B is also an element of A we say that B is a subset of A B Q A where the equality is included to account for the case in which A and B have the same elements If A contains more elements than B then B is said to be apraper subset of A and we use the notation B C A Finally we consider the concept of a universal set which we denote by U and de ne to be the set containing all elements of interest in a given situation For example in an experiment of tossing a coin there are two possible realistic outcomes heads or tails If we denote heads by H and tails by T the universal set in this case is H T Similarly the universal set for the experiment of throwing a single die has six possible outcomes which normally are denoted by the face value of the die so in this case U 1 2 3 4 5 6 For obvious reasons the universal set is frequently called the sample space which we denote by S It then follows that for any set A we assume that g A g S and for any element a a E S anda 0 Some Basic Set Operations The operations on sets associated with basic probability theory are straightforward The union of two sets A and B denoted by A U B is the set of elements that are either in A or in B or in both In other words AUBzlz AorzEB Similarly the intersection of sets A and B denoted by A B is the set of elements common to both A and B39 that is A Bz leAandzEB Two sets having no elements in common are said to be disjoint or mutually exclusive in which case A B0 The complement of set A is de ned as AC 2 l 2 A Clearly ACC A Sometimes the complement of A is denoted as A The difference of two sets A and B denoted A 7 B is the set of elements that belong to A but not to B In other words AiBzleA7 It is easily veri ed that A 7 B A BC The union operation is applicable to multiple sets For example the union of sets A17 A27 An is the set of points that belong to at least one of these sets Similar comments apply to the intersection of multiple sets Table 21 summarizes without proof several important relationships between sets Proofs for these relationships are found in most books dealing with elementary set theory Table 21 Some Important Set Relationships Wamp AUACS A AC AUA A SUS S AUAA A AA AUSS A SA AUBBUA A BB A A BUC A BUA C AUB C AUB AUC AUBUCAUBUCAUBUC A B CA B CA B C It often is quite useful to represent sets and sets operations in a socalled Venn diagram in which S is represented as a rectangle sets are represented as areas typically circles and points are associated with elements The following example shows various uses of Venn diagrams Example 21 Figure 21 shows various examples of Venn diagrams The shaded areas are the result sets of points of the operations indicated in the gure The diagrams in Chapter 2 A Brief Review of Probability and Random Variables the top row are self explanatory The diagrams in the bottom row are used to prove the validity of the expression A BUC A BUA C7A B C which is used in the proof of some probability relationshipsD A Ans AUB A B COD CD Amwvc AnQAnljnc A H AnleMnQAABHCJ Figure 21 22 Relative Frequency and Probability A random experiment is an experiment in which it is not possible to predict the outcome Perhaps the best known random experiment is the tossing of a coin Assuming that the coin is not biased we are used to the concept that on average half the tosses will produce heads H and the others will produce tails This is intuitive and we do not question it In fact few of us have taken the time to verify that this is true If we did we would make use of the concept of relative frequency Let n denote the total number of tosses mg the number of heads that turn up and nT the number of tails Clearly mg nT n Dividing both sides by 71 gives us n H quot T 1 71 71 The term 71 n is called the relative frequency of the event we have denoted by H and similarly for nTn If we performed the tossing experiment a large number of times we would nd that each of these relative frequencies tends toward a stable limiting value We call this value the probability of the event and denoted it by Pevent In the current discussion the probabilities of interest are PH and PT We know in this case that PH PT 12 Note that the event of an experiment need not signify 22 Relative Frequency and Probability 17 a single outcome For example in the tossing experiment we could let D denote the event heads or tails note that the event is now a set and the event E neither heads nor tails Then PD 1 and PE 0 The rst important property of P is that for an event A 0 g PA g 1 That is the probability of an event is a positive number bounded by 0 and 1 For the certain event S PS 1 Here the certain event means that the outcome is from the universal or sample set S Similarly we have that for the impossible event SC PSC 0 This is the probability of an event being outside the sample set In the example given at the end of the previous paragraph S D and SC E Consider a case with the possibilities that events A or B or both or neither can occur The event that either events A or B or both have occurred is simply the union of A and B recall from two paragraphs back that events can be sets Earlier we denoted the union of two sets by A U B One often nds the equivalent notation A B used interchangeably in discussions on probability Similarly the event that both A and B occurred is given by the intersection of A and B which we denoted earlier by A B The equivalent notation AB is used much more frequently to denote the occurrence of both events in an experiment Suppose that we conduct our experiment 71 times Let M be the number of times that only event A occurs 712 the number of times that B occurs 713 the number of times that AB occurs and 714 the number of times that neither A nor B occur Clearly 711 712 713 714 71 Using these numbers we obtain the following relative frequencies 71 7 n1n3 71 71 n3 7 n2n3 71 71 AB 7 3 71 71 and nAUB i n1n2n3 71 71 7 n1n3n2n3n3 71 71A B AB 7 71 71 71 18 Chapter 2 A Brief Review of Probability and Random Variables Using the previous de nition of probability based on relative frequencies we have the important result PAU B PA PB 7 PAB If A and B are mutually exclusive it follows that the set AB is empty and consequently PAB 0 The relative frequency of event A occurring given that event B has occurred is given by m quotAB n n if 71 3 n n This candilianalprababilily is denoted by PA Vifhere we note the use of the symbol to denote conditional occurrence It is common terminology to refer to PA B as the probability of A given B Similarly the relative frequency of B occurring given that A has occurred is w 71 3 n1 713 I We call this relative frequency the probability of B given A and denote it by PB A little manipulation of the preceding results yields the following important relation ships P B AP A PAB 7 PB and PAB PAPBA PBPAB The second expression may be written as P A B P B P B A lt gt PA which is known as Bayes theorem so named after the 18th century mathematician Thomas Bayes Example 22 Suppose that we want to extend the expression PA U B PA PB 7 PAB to three variables A B and C Recalling that AB is the same as A B we replace B by B U C in the preceding equation to obtain PAUB UC PA PBUC 7 PA B UCl The second term in the right can be written as PB U C PB PC 7 PBC 22 Relative Frequency and Probability 19 From Table 21 we know that A B U C A B U A 0 so PA B U 0 PA B U A 0 7 PAB o AC 7 PAB PAC 7 PABC Collecting terms gives us the nal result PA o B o O 7 PA PB PC 7 PAB 7 PAC 7 PBC PABC Proceeding in a similar fashion gives PABC PAPBAPCAB The preceding approach can be used to generalize these expressions to N events D If A and B are statistically independent then PBA PB and it follows that P A B P A PB A PB and PAB PAPB It was stated earlier that if sets events A and B are mutually exclusive then A B Q from which it follows that PAB PA B 0 As was just shown the two sets are statistically independent if PAB PAPB which we assume to be nonzero in general Thus we conclude that for two events to be statistically independent they cannot be mutually exclusive For three events A B and C to be independent it must be true that PAB 7 PAPB PAC 7 PAPC PBC 7 PBPC and PABC PAPBPC In general for N events to be statistically independent it must be true that for all combinationslgigjgkg mgN PAiAj 7 PAiPAJ PAiAJAk 7 PAiPAJPAk PA1A2AN PA1PA2Psz Example 23 a An experiment consists of throwing a single die twice The probability 20 Chapter 2 A Brief Review of Probability and Random Variables of any of the six faces 1 through 6 coming up in either experiment is 16 Suppose that we want to nd the probability that a 2 comes up followed by a 4 These two events are statistically independent the second event does not depend on the outcome of the rst Thus letting A represent a 2 and B a 4 1 PAB PAPB E X Elia 3639 We would have arrived at the same result by de ning 2 followed by 4 to be a single event say 0 The sample set of all possible outcomes of two throws of a die is 36 Then PC 136 b Consider now an experiment in which we draw one card from a standard card deck of 52 cards Let A denote the event that a king is drawn B denote the event that a queen or jack is drawn and C the event that a diamondface card is drawn A brief review of the previous discussion on relative frequencies would show that PA 5 8 H3 7 5 and 13 C 5 Furthermore PAC PA 0 PAPC and Events A and B are mutually exclusive we are drawing only one card so it would be impossible to draw a king and a queen or jack simultaneously Thus it follows from the preceding discussion that PAB PA B 0 and also that PAB 7E PAPB c As a nal experiment consider the deck of 52 cards again and let A17 A27 A37 and A4 represent the events of drawing an ace in each of four successive draws If we replace the card drawn before drawing the next card then the events are statistically independent and it follows that PA1A2A3A4 PA1PA2PA3PA4 4 4 5 7 a N 35 X 10 Suppose now that we do not replace the cards that are drawn The events then are no 23 Random Variables 21 longer statistically independent With reference to the results in Example 22 we write PA1A2A3A4 PA1PA2A3A4A1 PA1PA2A1PA3A4A1A2 PA1PA2A1PA3A1A2PA4A1A2A3 i 4 3 1 3 7 106 5239139503949N39X 39 Thus we see that not replacing the drawn card reduced our chances of drawing fours successive aces by a factor of close to 10 This signi cant difference is perhaps larger than might be expected from intuition D 23 Random Variables Random variables often are a source of confusion when rst encountered This need not be so as the concept of a random variable is in principle quite simple A random variable at is a realvalued function de ned on the events of the sample space S In words for each event in S there is a real number that is the corresponding value of the random variable Viewed yet another way a random variable maps each event in S onto the real line That is it A simple straightforward de nition Part of the confusion o en found in connection with random variables is the fact that they are functions The notation also is partly responsible for the problem In other words although typically the notation used to denote a random variable is as we have shown it here at or some other appropriate variable to be strictly formal a random variable should be written as a function where the argument is a speci c event being considered However this is seldom done and in our experience trying to be formal by using function notation complicates the issue more than the clarity it introduces Thus we will opt for the less formal notation with the warning that it must be keep clearly in mind that random variables are functions Example 24 Consider again the experiment of drawing a single card from a standard deck of 52 cards Suppose that we de ne the following events A a heart39 B a spade39 C a club39 and D a diamond so that S 14 B7 0 D A random variable is easily de ned by letting ac 1 represent event A at 2 represent event B and so on As a second illustration consider the experiment of throwing a single die and observing the value of the upface We can de ne a random variable as the numerical outcome of the experiment ie 1 through 6 but there are many other possibilities For example a binary random variable could be de ned simply by letting ac 0 represent the event 22 Chapter 2 A Brief Review of Probability and Random Variables that the outcome of throw is an even number and ac 1 otherwise Note the important fact in the examples just given that the probability of the events have not changed all a random variable does is map events onto the real line D Thus far we have been concerned with random variables whose values are discrete To handle continuous random variables we need some additional tools In the discrete case the probabilities of events are numbers between 0 and 1 When dealing with continuous quantities which are not denumerable we can no longer talk about the probability of an event because that probability is zero This is not as unfamiliar as it may seem For example given a continuous function we know that the area of the function between two limits a and b is the integral from a to b of the function However the area at a point is zero because the integral fromsay a to a is zero We are dealing with the same concept in the case of continuous random variables Thus instead of talking about the probability of a speci c value we talk about the probability that the value of the random variable lies in a speci ed range In particular we are interested in the probability that the random variable is less than or equal to or similarly greater than or equal to a speci ed constant a We write this as Fa Pac S a If this function is given for all values of a ie 700 lt a lt 00 then the values of random variable as have been de ned Function F is called the cumulative probability distribution function or simply the cumulative distribution function cdf The shortened term distribution function also is used It is important to point out that the notation we have used makes no distinction between a random variable and the values it assumes lf confusion is likely to arise we can use more formal notation in which we let capital letters denote the random variable and lowercase letters denote its values For example the cdf using this notation would be written as FX PX g When confusion is not likely the cdf often is written simply as This notation will be used in the following discussion when speaking generally about the cdf of a random variable Due to the fact that it is a probability the cdf has the following properties F 700 0 t 19 Fool 30311 4F11 F12 if x1lt12 23 Random Variables 23 5 Pac1 lt at S 352 F127 Fac1 6 Fac Fac where 1 at a with a being a positive in nitesimally small number The probability densilyfunc an pdf of random variable as is de ned as the derivative of the cdf dF 1 1930 x The term densizyfunc an is commonly used also The pdf satis es the following prop erties 1 1735 0 for all at 2 ffooop x 1 3 ffoopada where a is a dummy variable 4 Pac1 lt at S 352 f11pxdac We point out that the preceding concepts are applicable to discrete random variables In the discrete case we have a nite number of events and we talk about probabilities rather than probability density functions Also we replace the integrals by summa tions and sometimes subscript the random variables For example in the case of a dis crete variable with N possible values we would denote the probabilities by Paci i 1 2 N In Section 33 ofthe bookwe usedthe notationprk k 01 L 7 1 to denote the histogram of an image with L possible gray levels m k 01 Li 1 where 177 7C is the probability of the kth gray level random event occurring Clearly the discrete random variables in this case are gray levels It generally is clear from the context whether one is working with continuous or discrete random variables and whether the use of subscripting is necessary for clarity Also uppercase letters eg P are frequently used to distinguish between probabilities and probability density func tions eg p when they are used together in the same discussion We will have much more to say about probability density functions in the following sections Before leaving this section however we point out that if a random variable as is transformed by a monotonic transformation function Tac to produce a new random variable y the probability density function of y can be obtained from knowledge of Tac and the probability density function of ac as follows alas cl y my PM 24 Chapter 2 A Brief Review of Probability and Random Variables Where the subscripts on the p s are used to denote the fact that they are different func tions and the vertical bars signify the absolute value Recall that a function Tac is monotonically increasing if Tac1 lt T12 for 311 lt 312 and monotonically decreasing ifTac1 gt T12 for 311 lt 312 The preceding equation is valid ifTac is an increasing or decreasing monotonic function 24 Expected Value and Moments The expected value of a function 9a of a continuos random variable is de ned as El9xl 9xpdx If the random variable is discrete the de nition becomes 1v El9l 29901P1 11 The expected value is one of the operations used most frequently when working with random variables For example the expected value of random variable as is obtained by letting 9a ac 5 m acpacdac when at is continuos and N T m Z 11 when at is discrete The expected value of at is equal to its average or mean value hence the use of the equivalent notation E and m The variance of a random variable denoted by 02 is obtained by letting 9a x2 which gives 00 0392 E12 2pacdac for continuous random variables and N 0392 E12 11 for discrete variables Of particular importance is the variance of random variables that have been normalized by subtracting their mean In this case the variance is 00 a Elias mm as mgt21altxgtdx 00 and N a Elr m 2m mgt2Pltx1gt 11 for continuous and discrete random variables respectively The square root of the vari 24 Expected Value and Moments 25 ance is called the standard deviation and is denoted by 039 We can continue along this line of thought and de ne the nth central moment of a con ar 7 m 00 a EM 7 mm as e m pzdx tinuous random variable by letting 9a and N M EM m l 2m m Pm for discrete variables where we assume that1 2 0 Clearly no 17 n1 07 and n2 02 The term central when referring to moments indicates that the mean of the random variables has been subtracted out The moments de ned above in which the mean is not subtracted out sometimes are called moments about the origin In image processing moments are used for a variety of purposes including histogram processing segmentation and description In general moments are used to characterize the probability density function of a random variable For example the second third and fourth central moments are intimately related to the shape of the probability density function of a random variable The second central moment the centralized variance is a measure of spread of values of a random variable about its mean value the third central moment is a measure of skewness bias to the left or right of the values of at about the mean value and the fourth moment is a relative measure of atness eg see Section 1133 In general knong all the moments of a density speci es that density Example 25 Consider an experiment consisting of repeatedly ring a ri e at a target and suppose that we wish to characterize the behavior of bullet impacts on the target in terms of whether we are shooting high or low We divide the target into an upper and lower region by passing a horizontal line through the bull seye The events of interest are the vertical distances from the center of an impact hole to the horizontal line just described Distances above the line are considered positive and distances below the line are considered negative The distance is zero when a bullet hits the line In this case we de ne a random variable directly as the value of the distances in our sample set Computing the mean of the random variable will tell us whether on average we are shooting high or low If the mean is zero we know that the average of our shots are on the line However the mean does not tell us how far our shots deviated from the horizontal The variance or standard deviation will give us an idea of the spread of the shots A small variance indicates a tight grouping with respect to the mean and in the vertical position a large variance indicates the opposite Finally a third moment 26 Chapter 2 A Brief Review of Probability and Random Variables of zero would tell us that the spread of the shots is symmetric about the mean value a positive third moment would indicate a high bias and a negative third moment would tell us that we are shooting low more than we are shooting high with respect to the mean location B 25 The Gaussian Probability Density Function Because of its importance we will focus in this tutorial on the Gaussian probability density function to illustrate many of the preceding concepts and also as the basis for generalization to more than one random variable in Sections 26 and 27 The reader is referred to Section 522 of the book for examples of other density functions A random variable is called Gaussian if it has a probability density of the form Emmyoi 1990 039 where m and a are as de ned in the previous section The term normal also is used to refer to the Gaussian density A plot and properties of this density function are given in Section 522 of the book From the discussion in Section 23 of this review the cumulative distribution function corresponding to the Gaussian density is x pacdac 1 a 2 2 7 7 aim 7 d E 1 x 277039 200 which as before we interpret as the probability that the random variable lies between minus in nite and an arbitrary value ac This integral has no known closedform solution and it must be solved by numerical or other approximation methods Extensive tables exist for the Gaussian cdf 26 Several Random Variables In Example 25 we used a single random variable to describe the behavior of ri e shots with respect to a horizontal line passing through the bull seye in the target Although this is useful information it certainly leaves a lot to be desired in terms of telling us how well we are shooting with respect to the center of the target In order to do this we need two random variables that will map our events onto the anyplane It is not dif cult to see how if we wanted to describe events in 3D space we would need three random 25 The Gaussian Probability Density Function 27 variables In general we consider in this section the case of 71 random variables which we denote by x1 x2 1 the use of 71 here is not related to our use of the same symbol to denote the nth moment of a random variable It is convenient to use vector notation when dealing with several random variables Thus we represent a vector random variable x as x1 x2 x 1 Then for example the cumulative distribution function introduced earlier becomes Fla Fa17a277an Fifi S alimgazini vngan when using vectors As before when confusion is not likely the cdf of a random vari able vector often is written simply as This notation will be used in the following discussion when speaking generally about the cdf of a random variable vector As in the single variable case the probability density function of a random variable vector is de ned in terms of derivatives of the cdf39 that is PX 1990179027 7 anFx1727 7 311 2 Barn I An example of a multivariable density will follow shortly The expected value of a function of x is de ned basically as before El9Xl El917277nl oo oo oo 990173027n7n1717277nd1d2 39d vn 700700 700 Cases dealing with expectation operations involving pairs of elements of x are particu larly important For example the joint moment about the origin of order kq between variables xi and acj is oo oo nkqij x x pxixjdxidxj 7m7m When working with any two random variables any two elements of x it is common practice to simplify the notation by using at and y to denote the random variables In 28 Chapter 2 A Brief Review of Probability and Random Variables this case the joint moment just de ned becomes 00 00 meg Elxkyql 967qu windy oo 00 It is easy to see that who is the kth moment of ac and veg is the qth moment of y as discussed in Section 24 The moment on E is called the correlation of ac and y As discussed in Chapters 4 and 12 of the book correlation is an important concept in image processing In fact it is important in most areas of signal processing where typically it is given a special symbol such as Racy oo oo Racy 7In Elxyl xypx7ydxdy iwim If the condition Racy Ely holds then the two random variables are said to be uncorrelated From the discussion in Section 22 we know that if at and y are statistically independent then pacy in which case we write Ra Widen 11179le EixlEiyl 700 700 Thus we see that if two random variables are statistically independent then they are also uncorrelated The converse of this statement is not true in general The joint central moment of order kq involving random variables at and y is de ned as Meg mwky 7 mqul as 7 mm 7 mmpmwxdy where mi E and my E are the means of ac and y as de ned earlier We note that 20 mrl2l and 02 myl2l are the variances of ac and y respectively The moment p11 11 mxy myll oooo x 7 WW myPvldacdy 700 700 27 The Multivariate Gaussian Density 29 is called the covariance of ac and y As in the case of correlation the covariance is an important concept usually given a special symbol such as CW By direct expansion of the terms inside the expected value brackets and recalling the mac E and my it is straightforward to show that on 7 Eixyl 7 miEizi 7 mm mxmy 7 Eizyi 7 EixlEiyl 7 Ray 7 EixlEiyl From our discussion on correlation we see that the covariance is zero if the random variables are either uncorrelated 0r statistically independent This is an important result worth rem em bering If we divide the covariance by the square root of the product of the variances we obtain 7 M11 20M02 Cfy may E 957 mac 1 my 03975 try The quantity 7 is called the correlation cae cienl of random variables at and y It can be shown that the correlation coef cient is in the range 7 1 g 7 g 1 see Problem 125 As discussed in Section 1221 the correlation coef cient is used in image processing for m atching 27 The Multivariate Gaussian Density As an illustration of a probability density function of more than one random variable we consider the multivariate Gaussian probability density function de ned as 1 7x7mTC lx7m p x e 1 lt2win2ici12 where n is the dimensionality number of components of the random vector x C is the Cl is the determinant of matrix C m is the covariance matrix to be de ned below mean vector also to be de ned below and T indicates transposition see the review of matrices and vectors The mean vector is de ned as 30 Chapter 2 A Brief Review of Probability and Random Variables and the covariance matrix is de ned as C Ex 7 mx 7 The element of C are the covariances of the elements of x such that 02739 0ch Elm WWW mjl where for example xi is the ith component of x and mi is the ith component of m Covariance matrices are real and symmetric see the review of matrices and vectors The elements along the main diagonal of C are the variances of the elements x such that c 021 When all the elements of x are uncorrelated or statistically independent cij 0 and the covariance matrix becomes a diagonal matrix If all the variances are equal then the covariance matrix becomes proportional to the identity matrix with the constant of proportionality being the variance of the elements of x Example 26 Consider the following bivariate n 2 Gaussian probability density function 1 1 T 1 px eexem C xemi we iCi12 with In m1 m2 and C 011 012 C21 C22 where because C is known to be symmetric C12 91 A schematic diagram of this density is shown in Fig 22a Figure 22b is a horizontal slice of Fig 22a From our review of vectors and matrices we know that the main directions of data spread are in the directions of the eigenvectors of C Furthermore if the variables are uncorrelated or statistically independent the covariance matrix will be diagonal and the eigenvectors will be in the same direction as the coordinate axes x1 and x2 and the ellipse shown in Fig 22b would be oriented along the apl and an axis If in addition the variances along the main diagonal are equal the density would be symmetrical in all directions in the form of a bell and Fig 22b would be a circle Note in Figs 22a and b that the density is centered at the mean values 77117712 D 28 Linear Transformations of Random Vectors 31 28 Linear Transformations of Random Vectors As discussed in Section 13 a linear transformation of a vector x to produce a vector y is of the form y Ax Of particular importance in our work is the case when the rows of A are the eigenvectors of the covariance matrix Because C is real and symmetric we know from the discussion in Section 13 that it is always possible to nd 71 orthonormal eigenvectors from which to form A The implications of this are discussed in considerable detail in Section 13 which we recommend should be reviewed as a conclusion to the present discussion 05 3 1 X 1 quot391 b Figure 22 3 A Brief Overview of Linear Systems Because of their tractability and large body of application areas linear systems play a central role in most branches of science and engineering In image processing linear systems are at the heart of many ltering operations and they provide the basis for analyzing complex problems in areas such as image restoration The pquose of this short review is to enhance the material in Section 26 and to provide the fundamentals for the material in Chapters 4 and 5 In order to keep the discussion as basic as possible we will focus on functions of one variable Extensions of these ideas to images two variables are covered in Chapters 4 and 5 which also contain numerous illustrations 31 Introductory Definitions With reference to Fig 31 we de ne a system as a unit that converts an input function f into an output or response function where at is an independent variable such as time or as in the case of images spatial position We assume for simplicity that at is a continuous variable but the results that will be derived are equally applicable to discrete variables System xx H goo Figure 31 It is required that the system output be determined completely by the input the system properties and a set of initial conditions From Fig 31 we write 91 Hlfxl where H is the system operator de ned as a mapping or assignment of a member of the set of possible outputs to each member of the set of possible inputs 34 Chapter 3 A Brief Overview of Linear Systems In other words the system operator completely characterizes the system response for a given set of inputs An operator H is called a linear operator for a class of inputs if Hiaifi 04jfjl aiHifil ajHifjixl 11292 INNS for all and fj belonging to f Where the as are arbitrary constants and WW Hilefll is the output for an arbitrary input E f The system described by a linear operator is called a linear system with respect to the same class of inputs as the oper ator The property that performing a linear process on the sum of inputs is the same that performing the operations individually and then summing the results is called the property of additivity The property that the response of a linear system to a constant times an input is the same as the response to the original input multiplied by a constant is called the property of homogeneity An operator H is called time invariant if at represents time spatially invariant if at is a spatial variable or simply xed parameter for some class of inputs f if 9MB Hilefll implies that 9MB 0 Hilef fell for all E f and for all are A system described by a xedparameter operator is said to be a xedparameter system Basically all this means is that offsetting the in dependent variable of the input by 350 causes the same offset in the independent variable of the output Hence the inputoutput relationship remains the same An operator H is said to be causal and hence the system described by H is a causal system if there is no output before there is an input In other words fac 0 for at lt 350 implies thatgac 0 for at lt 350 Finally a linear system H is said to be stable if its response to any bounded input is bounded That is if lt K implies that lt cK Where K and c are constants Example 31 Suppose that operator H is the integral operator between the limits 700 and ac Then the output in terms of the input is given by x gm wfwdw 32 Linear System CharacterizationConvolution 35 where w is a dummy variable of integration This system obviously is linear because loo aifiw ajfjwdw xifoo ajoofjwdw aigi aj9j We see also that the system is xed parameter because o gacaco fwacodwaco 7350 fw x0dw foo H f x 360 where dw x0 dw because x0 is a constant Following similar manipulation it is easy to show that this system also is causal and stable Consider now the system operator whose output is the inverse of the input so that 1 1 9 x In this case 1 Haifiac afac l 7 l aifm ajfjw 75 aiHifixl ajHlfjixl so this system is not linear The system however is xed parameter and causal D 32 Linear System CharacterizationConvolution A unit impulsefunclian denoted 6ac 7 a is de nedby the expression mmmimMmn From the previous sections the output of a system is given by 91 H f But we can express f in terms of the impulse function just de ned so 00 91 H fa6ac 7 11104 foo Extending the property of addivity to integrals recall that an integral can be approxi mated by limiting summations allows us to write 00 an vawwimww foo 36 Chapter 3 A Brief Overview of Linear Systems Because f a is independent of ac and using the homogeneity property it follows that 00 930 faHl6 Wider 1 fo hac7 aola 700 The term hac a H6ac 7 04 is called the impulse response of H In other words hac a is the response of the linear system to a unit impulse located at coordinate at the origin of the impulse is the value of a that produces 60 in this case this happens when a at The expression 00 gm fiaihimida is called the superposition or Freclholmoo integral of the rst kind This expression is a fundamental result that is at the core of linear system theory It states that if the response of H to a unit impulse ie hac 04 is known then response to any input f can be computed using the preceding integral In other words the response of a linear system is characterized completely by its impulse response If H is a xedparam eter operator then H6ac 7 04 hac 7 a and the superposition integral becomes 00 gm wow 7 aida This expression is called the convolut ioor integral It states that the response of a linear xedparam eter system is completely characterized by the convolution of the input with the system impulse response As will be seen shortly this is a powerful and most practical result Because the variable a in the preceding equation is integrated out it is customary to write the convolution of f and h both of which are functions of as as 91 f WE In other words 00 fix W fiaigix 7 aida 700 The Fourier transform of this expression is WWW 7fahac7ada my Moo hot 7 ae j27mdx da 32 Linear System CharacterizationConvolution 37 The term inside the inner brackets is the Fourier transform of har 7 1 But S 7 04 Hue 73927ma was hon ma anew2m da 00 oo fae 73927mada 700 We have succeeded in proving that the Fourier transform of the convolution of two func tions is the product of their Fourier transforms Following a similar development it is not dif cult to show that the inverse Fourier transform of the convolution of H and ie x is the product This result is known as the convolution theorem typically written as and MW 4 Ho PM where 42gt is used to indicate that the quantity on the right is obtained by taking the Fourier transform of the quantity on the left and conversely the quantity on the left is obtained by taking the inverse Fourier transform of the quantity on the right The mechanics of convolution are explained in detail in the book We have just lled in the details of the proof of validity in the preceding paragraphs Because the output of our linear xedparam eter system is 91 fx WE if we take the Fourier transform of both sides of this expression it follows from the convolution theorem that The key importance of this result is that instead of performing a convolution to obtain the output of the system we computer the Fourier transform of the impulse response and the input multiply them and then take the inverse Fourier transform of the product to obtain 91 that is 936 S 1lGul S 1l1T1 uFul These results are the basis for all the ltering work done in Chapter 4 and some of the work in Chapter 5 of Digital Image Processing Those chapters extend the results to two dimensions and illustrate their application in considerable detail


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Allison Fischer University of Alabama

"I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.