Discretizing the heat equationMapping the image to a vectorBoundary ConditionsStabilityPerona-MalikIntroductionWeaknesses of the standard scale-space paradigmInhomogeneous diffusionProperties of inhomogeneous diffusionNext ClasslogoMedical Image AnalysisCS 593 / 791Computer Science and Electrical Engineering Dept.West Virginia University20th January 2006logoDiscretization Perona-MalikOutline1Discretizing the heat equation2Perona-MaliklogoDiscretization Perona-MalikOutline1Discretizing the heat equationMapping the image to a vectorBoundary ConditionsStability2Perona-MaliklogoDiscretization Perona-MalikRecall : The heat equationIn 1D∂I∂t=∂2I∂x2logoDiscretization Perona-MalikRecall : Numerical DerivativesFirst order forward difference:I0(x0) ≈ I(x0+ 1) − I(x0)First order backward difference:I0(x0) ≈ I(x0) − I(x0− 1)Second order, second centered difference:I00(x0) ≈ I(x0+ 1) − 2I(x0) + I(x0− 1)logoDiscretization Perona-MalikDiscretized 1D Heat Equation : ExplicitUsing the forward difference in time we getExplicit formulationIt+δx= Itx+ δ(Itx+1− 2Itx+ Itx−1)Explicit : Update Itusing derivatives computed at time t.Form a vector, w of image values, so that wi= I(i)logoDiscretization Perona-MalikDiscretized 1D Heat Equation : ExplicitWe can rewrite the discretized heat equation as the system oflinear equations:wt+δi= [δ, 1 − 2δ, δ]wti− 1wtiwti+ 1This is equivalent towt+δi= [0, δ, 1 − 2δ, δ, 0]wti− 2wti− 1wtiwti+ 1wti+ 2We can continue padding the row vector of coefficients with 0entries until...logoDiscretization Perona-MalikDiscretized 1D Heat Equation : Explicitwt+δi= [0, . . . , 0, δ, 1 − 2δ, δ, 0, . . . , 0]wt= aiwtWhere (1 − 2δ) is in the i-th column, since it multiplies wti.We can write the whole system of equations by forming amatrix A whose i-th row is aiwt+1= AwtA is a tridiagonal matrix.logoDiscretization Perona-MalikDiscretized 1D Heat Equation : Explicitwt+δi= [0, . . . , 0, δ, 1 − 2δ, δ, 0, . . . , 0]wt= aiwtWhere (1 − 2δ) is in the i-th column, since it multiplies wti.We can write the whole system of equations by forming amatrix A whose i-th row is aiwt+1= AwtA is a tridiagonal matrix.logoDiscretization Perona-MalikDiscretized 2D Heat Equation : ExplicitRecall the 2D heat equation∂I∂t=∂2I∂x2+∂2I∂y2Using the forward difference in time we getExplicit formulationIt+δx,y= Itx,y+ δ(Itx+1,y− 4Itx,y+ Itx−1,y+ Itx,y+1+ Itx,y−1)Update Itusing derivatives computed at time t.logoDiscretization Perona-MalikDiscretized 2D Heat Equation : ImplicitRecall the heat equation∂I∂t=∂2I∂x2+∂2I∂y2Using the backward difference in time we getExplicit formulationIt+δx,y= Itx,y+ δ(It+δx+1,y− 4It+δx,y+ It+δx−1,y+ It+δx,y+1+ It+δx,y−1)Implicit : Update Itusing derivatives computed at time t + δ.logoDiscretization Perona-MalikMapping the image to a vector2D image indices to 1D image indexMap 2d coordinates of I(x, y)(0, 0) (1, 0) (2, 0)(0, 1) (1, 1) (2, 1)(0, 2) (1, 2) (2, 2)to 1d coordinates of w(i)0 3 61 4 72 5 8The coordinate transformation is given byi(x, y) = nx + yfor an n × n image.logoDiscretization Perona-MalikMapping the image to a vectorWriting central differences in 1D vector formFor the coordinate transformation functioni(x, y) = nx + yIf I(x, y) → w(i), then I(x, y + 1) → w(i + 1), sincei(x, y + 1) = nx + y + 1 = i(x, y) + 1.If I(x, y) → w(i), then I(x + 1, y) → w(i + n), sincei(x + 1, y) = n(x + 1) + y = i(x, y) + n.logoDiscretization Perona-MalikMapping the image to a vectorWriting central differences in 1D vector formFor the coordinate transformation functioni(x, y) = nx + yIf I(x, y) → w(i), then I(x, y + 1) → w(i + 1), sincei(x, y + 1) = nx + y + 1 = i(x, y) + 1.If I(x, y) → w(i), then I(x + 1, y) → w(i + n), sincei(x + 1, y) = n(x + 1) + y = i(x, y) + n.logoDiscretization Perona-MalikMapping the image to a vectorWriting central differences in 1D vector formFor the coordinate transformation functioni(x, y) = nx + yIf I(x, y) → w(i), then I(x, y + 1) → w(i + 1), sincei(x, y + 1) = nx + y + 1 = i(x, y) + 1.If I(x, y) → w(i), then I(x + 1, y) → w(i + n), sincei(x + 1, y) = n(x + 1) + y = i(x, y) + n.logoDiscretization Perona-MalikMapping the image to a vectorWriting central differences in 1D vector formFor the coordinate transformation functioni(x, y) = nx + yIf I(x, y) → w(i), then I(x, y + 1) → w(i + 1), sincei(x, y + 1) = nx + y + 1 = i(x, y) + 1.If I(x, y) → w(i), then I(x + 1, y) → w(i + n), sincei(x + 1, y) = n(x + 1) + y = i(x, y) + n.logoDiscretization Perona-MalikMapping the image to a vectorWriting central differences in 1D vector formFor the coordinate transformation functioni(x, y) = nx + yIf I(x, y) → w(i), then I(x, y + 1) → w(i + 1), sincei(x, y + 1) = nx + y + 1 = i(x, y) + 1.If I(x, y) → w(i), then I(x + 1, y) → w(i + n), sincei(x + 1, y) = n(x + 1) + y = i(x, y) + n.logoDiscretization Perona-MalikMapping the image to a vectorWriting central differences in 1D vector formFor the coordinate transformation functioni(x, y) = nx + ySo,∂I2∂y2(x, y) ≈ I(x, y + 1) − 2I(x, y) + I(x, y − 1)≈ w(i + 1) − 2w(i) + w(i − 1)and∂I2∂x2(x, y) ≈ I(x + 1, y) − 2I(x, y) + I(x − 1, y)≈ w(i + n) − 2w(i) + w(i − n)logoDiscretization Perona-MalikMapping the image to a vectorWriting central differences in 1D vector formFor the coordinate transformation functioni(x, y) = nx + ySo,∂I2∂y2(x, y) ≈ I(x, y + 1) − 2I(x, y) + I(x, y − 1)≈ w(i + 1) − 2w(i) + w(i − 1)and∂I2∂x2(x, y) ≈ I(x + 1, y) − 2I(x, y) + I(x − 1, y)≈ w(i + n) − 2w(i) + w(i − n)logoDiscretization Perona-MalikMapping the image to a vectorWriting difference equations in matrix formThe implicit formulation of the heat equation involves solving n2simultaneous equations:wti= wt+δi+ δ(wt+δi+ 1− 4wt+δi+ wt+δi− 1+ wt+δi+ n+ wt+δi− n)......wti......=............................ . . δ . . . δ 1 − 4δ δ . . . δ . . ...............................wt+δi−n...wt+δi−1wt+δiwt+δi+1...wt+δi+n...What to do when w(i ± 1) or w(i ± n) falls outside the imageboundaries?logoDiscretization Perona-MalikBoundary ConditionsConstant