各项异性扩散由来及原理

8 Anisotropic diffusion filteringImages contain of the image itself and noiseNoise: random, little disturbances of the imageTo improve the segmentation: the noise should be reduced Condition:•Remove noise•But: keep the imageinformation unchangedDiffusionPhysical process for balancing concentration changes Now:•the image intensity can be seen as a “concentration”•The noise can be modelled as little concentrationinhomogeneitiesThese inhomogeneities could be smoothed by diffusion Diffusion should only be perpendicular e.g. to edgesPhysical background of diffusionGiven: a concentration distribution u Fick’s law:Concentration gradient causes a flux j j aims to compensate the gradientD : diffusion tensor, in general a positive definite, symmetric matrixu∇⋅−=D jPhysical background of diffusion (2) Diffusion is mass transport without destroying mass or creating new massContinuity equationt denotes the time, t u the deviation of u with respect to t∂∂+∂∂−=−=∂y x u t j j j divPhysical background of diffusion (3) diffusion equationApplication in many physical transport process, e.g. for heat transfer it is called heat-transfer-equation Image processing:Identify the concentration with the grey value at a certain location()u u t ∇⋅=∂D divPhysical background of diffusion(4)Diffusion tensor:•Constant over the whole image: homogeneous (orlinear) diffusion•Often it is a function of the structure of the image itself: nonlinear diffusion•Isotropic: j and the concentration gradient are parallel•Anisotropic: otherwiseLinear isotropic diffusionMostly used for smoothing images The image I itself is the initial starting for the diffusion processWe use D = 1 since D only influences the speed of the diffusion),()0,,(div y x I y x u uu t ==∂Linear isotropic diffusion(2)t=4t=8t=12t=20t=16t=24t=40t=0Linear isotropic diffusion(3)Advantages:•Continuously simplifying of the image•Reducing the noise in the imageDisadvantages:•Linear isotropic diffusion does not only reduce noise •It also blues important features like edges•No a-priori knowledge is taken into account•Result: it makes edges harder to identify8.3 Nonlinear diffusionNonlinear diffusionImprovement:•Preservation of the edges, only smooting between edges •Need to assign a position specific diffusivityAdapting the diffusivity g to the gradient in the actualimage u(x,y,t)We obtain the equation()u()∂2div gu=∇u∇tu for 1u for0→∇→∞→∇→g g Nonlinear diffusion (2)Conditions for gPerona & Malik:()22211λu u g ∇+=∇Nonlinear diffusion (3)t=4t=8t=12t=20t=16t=24t=40t=0Nonlinear diffusion (4)t=4t=20t=40t=40t=20t=4LineardiffusionNonlineardiffusionNonlinear diffusion(5)Advantages•Steering of the diffusion at each point of the image is possible•So diffusion can be reduced on edges•The result: edge-preserving image smoothing•But: the smoothing of the edges cannot be completely circumventedNext: anisotropic approachesNonlinear anisotropic diffusionUntil now: determination of the amount of diffusion depending on local features (here: the gradient).Other features could be possibleIdea: we could define the diffusion tensor so that the diffusion goes around some structuresHere: diffusion should preserve edges•On edges: no diffusion over edges, but diffusion parallel to edges should be enabledNonlinear anisotropic diffusion(2)Combination of two features•Non-linearity-The diffusion at border is much less than thediffusion elsewhere•Anisotropy-Diffusion should be perpendicular to edge-No diffusion over edgesNonlinear anisotropic diffusion(3)How to define the diffusion tensor D?Remember: D is a positive definite symmetric matrix •It has two different eigenvalues and two eigenvectors•Therewith the eigenvectors are perpendicular•The eigenvectors gives the main diffusion direction•The corresponding eigenvalues the strength of diffusion in the direction of the eigenvectors.Definition of the eigenvectorsWe want to stop the diffusion over the edge. Therewith we need as one eigenvector the direction of the gradient. The second is perpendicular and can be seen as thetangential vector to the edge [][]−=∇∇=x y v v v u u v 1121Nonlinear anisotropic diffusion (4)u v uv ∇⊥∇21||Definition of the eigenvaluesFirst: We want to stop the diffusion over the edge (direction v1). We use the non-linearity and definePerpendicular to the edge the diffusion should not bestopped ()21ug ∇=λNonlinear anisotropic diffusion (5)12=λNow, we obtain D asResult is an edge-enhancing anisotropic diffusionT⋅⋅ =||||00||||212121v v v v D λλNonlinear anisotropic diffusion (6)Nonlinear anisotropic diffusion (7)t=4t=8t=12t=20t=16t=24t=40t=0Nonlinear anisotropic diffusion (8)t=4t=20t=40t=40t=20t=4NonlineardiffusionNonlinearanisotropicdiffusionNumerical implementationWe haveLooking for a solution u(x,y,t)Either for a specific t = t 0Or for tProblem: the equation cannot be analytically solved Numerical solution is necessary),()0,,(y x I y x u =1. step: discretizing the time axis•Determination of a time step-depends on the numerical stability •only the timesare taken into accountWe obtain u(x,y,t i )Numerical implementation (2)τ∆⋅==i t t i2. step: finding an approximation for the derivative with respect to tThe Taylor serie for u(x,y,t) leads toNeglecting the remain and transform the equation leads to ()ζττR t y x u tt y x u t y x u +∂∂⋅∆+=∆+),,(),,(),,(Numerical implementation (3)),,(),,(),,(1i i i t y x u tt y x u t y x u ∂∂⋅∆+=+τConditions to the step size:Dimensions: m , grid width: hCosts per iteration: very lowEfficiency: low (many iterations needed to get a result)mh 22<∆τNumerical implementation (4)Until now we used the so-called explicit scheme Other notationwith •I : identity matrix•u i values of u(x,y,t i )stacked in vector form•A l (u k )matrix version of the diffusion tensors Notation()i ml i l i u u A I u⋅ ⋅∆+= =+11τSemi-implicit schemeAdditive operator splitting()i ml i l i uu A I u ⋅ ⋅∆−=−=+ 111τImprovements()()i m l i l i m m u u A I u ⋅⋅∆⋅−=−=+ 1111τSemi-implicit scheme: We can write the derivative of u with respect to t asImplicit: because u i+1is usedSemi-implicit: operator A l (u i )is combined with u i+1 Transformation of the equation leads to ()111+=+⋅=∆− i ml i l i i A u u u u τSemi-implicit scheme()i m l i l i u u A I u⋅ ⋅∆−=−=+ 111τSemi-implicit scheme(2)Features:•Stable for < , but: convergence usually becomesslower for too large•Cost per iteratorion: high, because the matrix must bebuilt and inverted in each iteration, O(n2)•Efficiency: medium(better than the explicit schemebecause of the possible larger , but further improvement is possible)Question: How could the invertion of the matrix be more effective•Hint: each A l is a simple tri-diagonal matrixAdditive operator splitting(AOS)Objective: split the derivation operator for each spatial directionThen we get for each direction a simple tri-diagonal matrix Such matrices can be very efficiently invertedAdvantage:•Keep the unrestrictedness of•Make the calculation more effectiveOne can writeas()⋅∆− =ml i l 1u A I τAdditive operator splitting (2)()[]=⋅⋅∆−m l i m m 111u A I τFor the computation of the inverse matrix we use the approximationThenow occuring error is •onlyof second and higher order •This means: the first derivatives have no errors()111−−−+≈+B A B A Additive operator splitting (3)And we approximate the inverse matrix byTherewith we obtain the equation()()[]111111−=−= ⋅⋅∆−≈ ⋅∆−m l i m l i l m m u A I u A I ττAdditive operator splitting (4)()[]i m l i i m m u u A I u 11111−=+ ⋅⋅∆−=τAdditive operator splitting(5)Differences and improvements•A split in the operator for each spatial direction has been performed•The pixels can be arranged for each operator separately •As result each operator is tri-diagonal matrix and isinverted separately.•Such 3-diagonal matrices can be inverted in linear time O(n), not in O(n2)Additive operator splitting(6)Features•Stable for <•Cost per iteratorion: low, but a little higher than for the explicit schemeEfficiency: highhigh low <AOS medium high < Semi-implicitlow very low explicitefficiency Cost per iteration Stability SchemeConclusionm h 22<∆τ。