Efficient Nonlinear Image Processing Algorithms

Efficient Nonlinear ImageProcessing AlgorithmsSANJIT K. MITRADepartment of Electrical & Computer EngineeringUniversity of CaliforniaSanta Barbara, California

OutlineQQQIntroductionQuadratic Volterra OperatorsImage Processing Applications– Contrast Enhancement– Impulse Noise Removal– Image Zooming– Image Halftoning

IntroductionQQQLinear image processing algorithmshave received considerable attentionduring the last several decadesThey are easy to implement and arecomputationally less intensiveThe basic hypotheses for thedevelopment of linear models and linearsignal processing algorithms arestationarity and Gaussianity

IntroductionQTo achieve improved performance,algorithms must take into account– nonlinear effects in the human visualsystem– nonlinear behavior of the image acquisitionsystems

IntroductionQQQThe hypotheses of stationarity andGaussianity do not hold in the case ofimage signalsLinear filtering methods applied to animpulse-noise-corrupted image blursharp edges and remove fine detailsLinear algorithms are not able toremove signal-dependent ormultiplicative noise in images

IntroductionQQThis has led to a growing interest in thedevelopment of nonlinear imageprocessing methods in recent yearsDue to rapidly decreasing cost ofcomputing, image storage, imageacquisition, and display, complexnonlinear image processing algorithmshave also become more practical forimplementation

IntroductionQTypes of Nonlinear Algorithms:– Homomorphic filters– Nonlinear mean filters– Morphological filters– Order statistic filters– Polynomial filters– Fuzzy filters– Nonlinear partial differential equationbased filters

Discrete-Time Volterra FiltersQQQThe Volterra filter is a special case ofthe polynomial filtersIt is based upon an input-output relationexpressed in the form of a truncatedVolterra seriesSimplest types are the quadratic filterscorresponding to the first nonlinear termin the Volterra expansion

Discrete-Time Volterra FiltersQTwo attractive and important propertiesof the Volterra filters, and in particular,of the quadratic filters

Discrete-Time VolterraOperatorsFirst PropertyQ Output depends linearly on thecoefficients of the filter itselfQ Is used to analyze the behavior of thefilters, find new realizations, deriveadaptive algorithms, etc.

Discrete-Time VolterraOperatorsSecond PropertyQ Results from the representation of thenonlinearity by means of multidimensional operators working on theproducts of input samplesQ Allows for the frequency domaindescription of the filters by means ofmulti-dimensional convolution

Discrete-Time VolterraOperatorsQThe general form of the Volterra filter isdescribed by the input-output relation: y[n] h0 hˆk ( x[n])k 1Qy[n] and x[n] are, respectively, theoutput and input sequences, and hˆk ( x[n]) . hˆk[i1,., ik ] x[n i1 ] x[n ik ]i1 0 ik 0

Discrete-Time VolterraOperatorsQQQQIn the expression for hˆk ( x[n]) , thediscrete variables i1,., ik are usuallydefined on a causal supporth0 is an offset termhˆk[i1 ] is the impulse response of alinear FIR filterhˆk[i1,., ik ] can be considered as ageneralized k-th order impulse responsecharacterizing the nonlinear behavior

1-D Quadratic Volterra FiltersInfinite Memory Quadratic FiltersQ Input-output relationy[n] h 0 hˆ1( x[n]) hˆ2( x[n]) h 0 h1[i1] x[n i1]i1 0 h2[i1, i2 ] x[n i1] x[n i2 ]i1 0 i2 0

1-D Quadratic Volterra FiltersFinite Memory Quadratic FiltersQ Input-output relationN1 1y[n] h 0 h1[i1] x[n i1]i1 0N 2 1 N 3 1 h2[i1, i2 ] x[n i1] x[n i2 ]i1 0 i2 0

1-D Quadratic Volterra FiltersTransform-Domain RepresentationQ Convolution form of quadratic term y[n] hˆ2( x[n]) h2[i1, i2 ] x[n i1] x[n i2 ]i1 0 i2 0can be expressed as w[n1, n 2] h2[i1, i2 ] v[n1 i1, n2 i1]i1 0 i2 0

1-D Quadratic Volterra FiltersQForv[n1 i1, n2 i2 ] x[n i1] x[n i2 ]andn1 n 2 nso thaty[n] w[n,n]

1-D Quadratic Volterra FiltersQThe two-dimensional (2-D) Fouriertransform of h2[n1,n2 ] given byH 2 (e jω1 , e jω2 ) jω1k1 e jω2 k2h[k,k]e 2 1 2k1 k2 is defined as the frequency responseof the quadratic Volterra filter

1-D Quadratic Volterra FiltersQQThe properties of the 2-D Fouriertransform can be used to characterizethe quadratic kernel h2[i1, i 2 ]For example, the expression for y[n] canbe derived using the inverse 2-D Fouriertransform1/ 2 1/ 2y[n] H 2 (e 1 / 2 1 / 2j 2 πf1,ej 2 πf 2) X ( f1 ) X ( f 2 ) e j 2 π( f1 f 2 ) df1df 2

1-D Quadratic Volterra FiltersQQwhere X(f) is the Fourier transform ofx[n]Note: If the input to a quadratic filter is aj 2 πf a nsinusoid, i.e. if x[n] A ethen the output isj 2 πf a j 2 πf a j 2 π 2 f a n2y[n] A H 2 e,ee()which is still a sinusoid but with afrequency 2 f a

1-D Quadratic Volterra FiltersQIf the input is a sum of two sinusoidswith frequencies f a and fb , then theoutput contains three sinusoids offrequencies 2 f a , 2 f a , and f a fb

1-D Quadratic Volterra FiltersQAs every kernel can be transformed intoa symmetrical form, we restrict ourattention here to Volterra filters with asymmetric impulse response, i.e.,h2[n1,n2 ]h2[n2 ,n1 ]

Teager’s 1-D OperatorQAn example of the quadratic Volterrafilter is the Teager’s operatory[n] x 2 [n] x[ n 1]x[n 1]QIntroduced by Kaiser to calculate theenergy y[n] of a one-dimensional (1-D)signal x[n]

Teager’s 1-D OperatorQIf the input is x[n] A cos(ωo n φ) , thenthe Teager’s operator generates anoutputy[n] A2 cos 2 (ωo n φ) A2 cos(ωo (n 1) φ) cos(ωo (n 1) φ) A2 sin 2 (ωo ) A2ωo2for small values of ωo

Teager’s 1-D OperatorQThus, for sinusoidal inputs, the Teageroperator develops a constant outputwhich is an estimate of the physicalenergy of a pendulum oscillating with afrequency ωo and an amplitude A

Teager’s 1-D OperatorQUnder some mild conditions, the 1-DTeager operator can be approximatelyrepresented asy[n] µ x (2 x[n] x[n 1] x[n 1])QIn the aboveµ x 1 ( x[n 1] x[n] x[n 1) )3is the local mean

Teager’s 1-D Operatorand the quantity2 x[n] x[n 1] x[n 1]Qis the Laplacian operator which is anFIR highpass filterThus, the 1-D Teager operator behavesas a mean-weighted highpass filter

Teager’s 1-D OperatorQThe 1-D Volterra filters that can berepresented approximately as a localmean-weighted highpass filter satisfythe following three conditions:(1) H 2 (e j 0 , e j 0 ) h2[k1, k2 ] 0k1 k2(2) H 2 (e jω1 , e j 0 ) H 2 (e j 0 , e jω2 )and

Teager’s 1-D Operator(3) h2[k1, k2 ] (h2[k1, k3 ] h2[k1, k3 ])k1 k2k1 k 2 h2 [k1, k2 ] (h2 [k1, k3 ] h2 [k1, k3 ]) 0k1 k2 k3k1 k 2 k 2 k 3QA large class of such filters satisfies theabove three conditions

Teager’s 1-D OperatorThe frequency-domain input-outputrelation of filters belonging to this classcan be expressed as:Y (e jω ) 2µ x H 2 (e jω , e j 0 ) X (e jω )jωjωQ Y (e ) and X (e ) denote, respectively,the 1-D Fourier transforms of the outputy[n] and the input x[n]Q

Teager’s 1-D OperatorQIf H 2 (e jω , e j 0 ) is a highpass filter, thenthe quadratic Volterra filter given byy[n] h2[k1, k2 ]x[n k1] x[n k2 ]k1 k2 satisfying the three conditions statedearlier can be approximated as a localmean-weighted highpass filter

Teager’s 1-D OperatorQQQThe 1-D Teager operatory[n] x 2 [n] x[ n 1]x[n 1]is an example of such a filterIt maps sinusoidal inputs to constantoutputsEvery filter belonging to the class oflocal-mean-weighted highpass filtershas the above property

2-D Teager OperatorQA 2-D extension of the Teager operatoris obtained by applying the filteringoperationy[n] x 2 [n] x[ n 1]x[n 1]along both the vertical and horizontaldirections:y[m, n] 2 x 2 [m, n] x[m 1, n]x[ m 1, n]n x[m, n 1] x[m, n 1]m

2-D Teager OperatorQAnother 2-D extension is obtained byapplying the 1-D operator along the twodiagonal directionsy[m, n] 2 x 2 [m, n] x[m 1, n 1]x[m 1, n 1] xm n xm n [1,1][1,1]nm

2-D Teager OperatorQQBoth of the above two 2-D quadraticfilters can be approximated as a localmean-weighted highpass 2-D filterThe general class of 2-D quadraticVolterra filters that can beapproximately represented as a meanweighted highpass filter is characterizedby three conditions similar to thatsatisfied by the 1-D Teager operator

2-D Teager OperatorQBased on this analysis, a number ofother local-mean-weighted highpass2-D filters have been developedQAnother member of this class, forexample, is the filter defined byy[m, n] 3 x 2 [m, n] 1 x[m 1, n 1]x[m 1, n 1]2 1 x[m 1, n 1] x[m 1, n 1]2 x[m 1, n] x[m 1, n] x[m, n 1] x[m, n 1]

Image ProcessingApplicationsQQThe mean-weighted highpass filteringproperty of the 2-D Teager filters hasbeen exploited in developing a numberof image processing applicationsWe present next four specificapplications

Contrast EnhancementQQThe conceptually simple unsharpmasking approach is a widely usedimage contrast enhancement methodBased on the addition of an amplitudescaled linear highpass filtered version ofthe image to the original image x[ m, n ] µHighpassFiltery[ m , n ]

Contrast EnhancementA commonly used linear highpass filteris the Laplacian operator:y[n1, n 2] 4 x[n1, n 2] x[n1 1, n 2] x[n1 1, n 2]QQ x[n1, n 2 1] x[n1, n 2 1]Its main advantage is computationalsimplicity

Contrast EnhancementQQQThe highpass filter enhances thoseportions of the image that containsmostly high frequency information, suchas edges and textured regionsOften yields visually pleasing results byutilizing an effect called simultaneouscontrastThe perceptual impression is improvedbecause the image appears sharperand better defined

Contrast EnhancementQQQApparent problem of this technique isthat it does not discriminate betweenactual image information and noiseThus, noise is enhanced as wellUnfortunately, visible noise tends to bemostly in the medium to high frequencyrange

Contrast EnhancementQQThe contrast sensitivity function (CSF)of the human visual system (HVS)shows that the eye (and the higher levelprocessing system in the visual cortex)is less sensitive to low frequenciesTo eliminate the noise enhancementproblem we need to make use ofWeber’s law

Contrast EnhancementQA visual phenomenon according towhich the difference in the perceivedbrightness of neighboring regionsdepends on the sharpness of thetransition occurring at edges

Contrast EnhancementQQWe modify the unsharp maskingmethod such that the imageenhancement is dependent on the localaverage pixel intensityIn bright regions we can enhance theimage more because noise and othergray level fluctuations are much lessvisible

Contrast EnhancementQQOn the other hand, in darker regions wewant to suppress the enhancementprocess since it might deteriorate imagequalityThis simple idea indicates the need fora highpass filter that depends on localmean:H (e jω ) H high (e jω ) (local mean)

Contrast EnhancementQQImprovement in the visual quality of theimage obtained using a nonlinearunsharp masking approach in whichthe linear highpass filter is replaced witha 2-D Teager operatorThe filter output depends on the localbackground brightness, and as a result,it follows Weber's Law

Contrast EnhancementOriginal imageEnhanced image

Contrast EnhancementQOutputs of the Teager and theLaplacian filters are shown belowTeager filter outputLaplacian filter output

Contrast EnhancementOriginalContrast Enhanced

Contrast EnhancementOriginalContrast Enhanced

Contrast EnhancementQQThe Laplcian filter output shows auniform response to edges independentof background intensityThe Teager filter output is weaker indarker regions (e.g., the darker areas ofthe roof) and stronger in brighter areas(e.g., the bright wall)

Impulse Noise RemovalQQQGoal: To suppress the impulse noisewhile preserving the edges and thedetailsA number of nonlinear methods havebeen advanced for impulse noiseremovalAmong these, the most common is themedian filtering

Impulse Noise RemovalQQQMedian filtering is computationallyefficient and does suppress impulsecorrupted pixels effectivelyIn median filtering, whether a pixel iscorrupted by impulse noise or not, it isreplaced by its local median within awindowThus, median filtering not only removesthe impulse noise but also introducesdistortion