Linear And Non-linear Filtering For Basic Image Processing .
Linear and non-linear filtering for Basic ImageProcessing ApplicationsYao WangTandon School of Engineering, New York University
Summary of Previous Lecture 2D CSFT and DSFT– Think of transform as representing a signal as weighted average of selectedorthonormal basis functions– Many properties of 1D CTFT and DTFT carry over, but there are a few thingsunique to 2D– Meaning of spatial frequency– 2D FT of separable signal product of 1D FT– Rotation in space - rotation in frequency plane 2D linear convolution weighted average of neighboring pixels– Filter Point spread function (impulse response in 2D)– Any LSI (linear and shift invariant) operation can be represented by 2Dconvolution– DSFT of filter frequency response response to complex exponential input Computation of convolution:– boundary treatment, separable filtering Convolution theorem– Interpretation of convolution in the frequency domain! MATLAB function: conv2( ), freqz2( ) Yao Wang, 2016EL-GY 6123: Image and Video Processing2
Outline Noise removalimage sharpeningEdge detectionMedian filteringMorphological filtering Yao Wang, 2016EL-GY 6123: Image and Video Processing3
Typical Image Processing Tasks Noise removal (image smoothing): low pass filterEdge detection: high pass filterImage sharpening: high emphasis filter In image processing, we rarely use very long filtersWe compute convolution directly, instead of using 2D FFTFilter design: For simplicity we often use separable filters, anddesign 1D filter based on the desired frequency response in 1D We do not focus on filter design in this class Yao Wang, 2016EL-GY 6123: Image and Video Processing4
Noise Removal Using Averaging FiltersWindow size controls tradeoff betweennoise removal power and blurring Yao Wang, 2016EL-GY 6123: Image and Video Processing5
Freq. Response Corresponding to AveragingFilters of Different Sizes3x3filter Yao Wang, 20167x7filterEL-GY 6123: Image and Video ProcessingH ones(3,3);Hf freqz2(H);figure(1);mesh(abs(Hf));title('Freq. Response of 3x3Averaging Filter');figure(2);imshow(abs(Hf),[])6
Gaussian Filter Analog form: STD σ controls the smoothing strength Take samples, truncate after a few STD, normalize thesum to 1. Usually σ 1 Size of mask nxn, Recommended: n 6σ 1, odd– Ex: σ 1, n 7.– Show filter mask,– Show frequency response Yao Wang, 2016EL-GY 6123: Image and Video Processing7
function gauss(s)0.00000.00020.00110.00180.00110.00020.0000 Yao Wang, 0.09660.15920.09660.02160.00180.0011 0.0002 0.00000.0131 0.0029 0.00020.0586 0.0131 0.00110.0966 0.0216 0.00180.0586 0.0131 0.00110.0131 0.0029 0.00020.0011 0.0002 0.0000x [-3.0:1.0:3.0];gauss exp(-x. 2/(2*s 2));gauss2 gauss'*gauss;gauss2 gauss2/(sum(sum(gauss2)));H eqz2(gauss2);title('Gaussian Filter \sigma 1');EL-GY 6123: Image and Video Processing8
Gaussian Filter in Freq. Domain Still a Gaussian Function! 1D Gaussian filter 2D Gaussian filter Note that STD β in freq. inversely related to STD σ inspace Yao Wang, 2016EL-GY 6123: Image and Video Processing9
Gaussian Filter in Space and Freq.σ 1σ 2β 0.16 Yao Wang, 2016β 0.08EL-GY 6123: Image and Video Processing10
Image Sharpening (Debluring) Sharpening : to enhance line structures or other detailsin an image Enhanced image original image scaled version ofthe line structures and edges in the image Line structures and edges can be obtained by applyinga high pass filter on the image In frequency domain, the filter has the “high-emphasis”character Yao Wang, 2016EL-GY 6123: Image and Video Processing11
Designing Sharpening Filter Using High PassFilters The desired image is the original plus an appropriatelyscaled high-passed image Sharpening filterf s f λf hhs (m, n) δ (m, n) λhh (m, n) Yao Wang, 2016EL-GY 6123: Image and Video Processing12
Interpretation in Freq Domainhigh emphasis allpass highpassall passhigh pass0 Yao Wang, 2016EL-GY 6123: Image and Video Processingf13
High Emphasis Filter Using Laplacian Operatoras Highpass Filterfs(x) f(x) ag(x)g(x) f(x)*hh(x)f(x)xxx 0 1 0 0 1 0 11H h 1 4 1 H s 1 8 1 with λ 1.44 0 1 0 0 1 0 " 1 1 1 %" 1 1 1 %''1 1 H h 1 8 1 ' H s 1 16 1 ' with λ 1.8 8 '' 1 1 1#&# 1 1 1 & Yao Wang, 2016EL-GY 6123: Image and Video Processing14
Example of Sharpening Using LaplacianOperator 0 1 0 1 H h 1 8 1 4 0 10 Yao Wang, 2016EL-GY 6123: Image and Video Processing15
Challenges of Noise Removal and Image Sharpening How to smooth the noise without blurring the details toomuch? How to enhance edges without amplifying noise? Still a active research area– Wavelet domain processing Yao Wang, 2016EL-GY 6123: Image and Video Processing16
Wavelet-Domain FilteringCourtesy of Ivan Selesnick Yao Wang, 2016EL-GY 6123: Image and Video Processing17
Feature Enhancement by SubtractionTaking an image without injecting a contrast agent first. Then take the image again afterthe organ is injected some special contrast agent (which go into the bloodstreams only).Then subtract the two images --- A popular technique in medical imaging Yao Wang, 2016EL-GY 6123: Image and Video Processing18
Edge Detection What is an edge?Difference between edge and line and pointWith high resolution images, even a thin line will occupy multiplerows/columns have have step edges on both sides Yao Wang, 2016EL-GY 6123: Image and Video Processing19
Characterization of EdgesIdeal step edgeReal edge has a slopeFirst order derivative:Maximum at edge locationSecond order derivative:Zero crossing at edge location Yao Wang, 2016EL-GY 6123: Image and Video Processing20
Edge Detection Based on First OrderDerivativesHigh-pass filtering across edgeLow-pass filtering along edge Edge 1 1 1 h 1 1 1 Non-EdgeNofHg g TYesEdgeWhat if we don’t know edge direction? Yao Wang, 2016EL-GY 6123: Image and Video Processing21
Edge Detection Based on Gradients in TwoOrthogonal Directions Combine results from directional edge detectors in twoorthogonal directions and determine the magnitude anddirection of the edge.Non-EdgefxHxfx2 fy2Hytan-1(fx/fy)g g TOr local maxima?Edgefthetafy Yao Wang, 2016EL-GY 6123: Image and Video Processing22
Directional Edge Detector High-pass (or band-pass) in one direction (simulating first orderderivative) Low pass in the orthogonal direction (smooth noise)LP Prewitt edge detectorBP 1 1 1 1 1 0 1 1 1 1 1 1 H x 0 0 0 0 [1 1 1]; H y 1 0 1 1 [ 1 0 1]3333 1 1 1 1 1 0 1 1 Sobel edge detector 1 2 1 1 1 0 1 1 1 1 1 1 H x 0 0 0 0 [1 2 1]; H y 2 0 2 2 [ 1 0 1]4444 1 2 1 1 1 0 1 1 The sobel filter provides better smoothing along the edge Yao Wang, 2016EL-GY 6123: Image and Video Processing23
Freq. Response of Sobel FilterSobel Filter for Horizontal Edges : 1 2 1 1 11H x 000 0 [1 2 1]44 1 1 21 Frequency Response (DTFT) :()hx [-1 0 1] - H x e j 2πu e j 2πu 2 j sin 2πu()111h y [1 2 1] - H y e j 2πv 2 e j 2πv (1 cos 2πv )442 Hx(u) 0Band-pass Yao Wang, 20161/4 Hy(v) 1/2u01/41/2vLow-passEL-GY 6123: Image and Video Processing24
Spectrum of the Sobel Filter10Hx504040200 02010Hy504040200 020Low pass along the edge, band pass cross the edge Yao Wang, 2016EL-GY 6123: Image and Video Processing25
Example of Sobel Edge DetectorOriginal image Yao Wang, 2016Filtered image by HxEL-GY 6123: Image and Video ProcessingFiltered image by Hy26
How to set threshold? Trial and error According to edge magnitude distribution– E.g assuming only 5% pixels should be edge pixels, then thethreshold should be the 95% percentile of the edge magnitude– Illustrate on board Yao Wang, 2016EL-GY 6123: Image and Video Processing27
Histogram of gmgxgygmT 100T 50T 20250020001500100050000100 Yao Wang, 2016200EL-GY 6123: Image and Video Processing28
DoG Filter for Taking Derivatives Apply Gaussian filtering first to smooth the image, STD dependson noise level or desired smoothing effect– F(x,y)*G(x,y) Then take derivative in horizontal and vertical directions, which isequivalent to apply a difference filtet D(x,y)– F(x,y)*G(x,y)*D(x,y) F(x,y)* (D(x,y)*G(x,y)) Equivalent filter: DoG– H(x,y) D(x,y)*G(x,y)G(x , y) eH x (x , y) x2 y22σ 2 Gx 2e xσ GyH y (x , y) 2e yσ! x2 y2 2σ 2x2 y22σ 2Sample the above continuous filter to get digital filter. Hy is rotatedversion of Hx Yao Wang, 2016EL-GY 6123: Image and Video Processing29
DoG Filter Examplesσ 1, n 3 (similar to Sobel)σ 1, n 79-0.16420.03660.08210-0.0821-0.03660.3679 0.6065 0.3679000-0.3679 -0.6065 -0.3679DoG filters are band-pass filters in one direction, low-pass in orthogonal direction Yao Wang, 2016EL-GY 6123: Image and Video Processing30
DoG Filter ExamplesS 2, n 7 (more smoothing)s 1, n 50.03660.08210-0.0821-0.0366 Yao Wang, .0821-0.03660.0790 0.14770.0985 0.18390.0716 0.13380-0.0716 -0.1338-0.0985 -0.1839-0.0790 -0.14770.2149 0.24350.2676 0.30330.1947 0.2206000-0.1947 -0.2206-0.2676 -0.3033-0.2149 -0.2435EL-GY 6123: Image and Video 9850.0716-0.0716-0.0985-0.079031
Problems of previous approach Cannot locate edges precisely Ramp edges can lead to many edge pixelsdetected depending on the threshold T– T too high: may not detect weak edges– T too small: detected edges too think, noisy pointsfalsely detected Remedy:– Detecting local maximum of g in the normaldirection of the edge, or try all possible 8 direction ina 3x3 neighbor– Only consider pixels with g T Yao Wang, 2016EL-GY 6123: Image and Video Processing32
Edge Detection with Many Directional Filters Instead of using two orthogonal directions, can designmultiple directional filters– 0, 45, 90, 135 See which one gives the highest response in thenormal direction Yao Wang, 2016EL-GY 6123: Image and Video Processing33
Characterization of EdgesIdeal step edgeReal edge has a slopeFirst order derivative:Maximum at edge locationSecond order derivative:Zero crossing at edge location Yao Wang, 2016EL-GY 6123: Image and Video Processing34
Edge Detection Based on Second OrderDerivative Convolve an image with a filter corresponding to takingsecond order derivative (e.g. Laplacian or LoGoperator) Locate zero-crossing in the filtered image Yao Wang, 2016EL-GY 6123: Image and Video Processing35
Laplacian Operator 2 f 2 f 2 2 x y f f ( x 1, y ) f ( x, y ) x 2 f f ( x 1, y ) 2 f ( x, y ) f ( x 1, y )2 x 2 f f ( x, y 1) 2 f ( x, y ) f ( x, y 1)2 y2f 2f [ f ( x 1, y ) f ( x 1, y ) f ( x, y 1) f ( x, y 1)] 4 f ( x, y ) 0 1 0 0 1 0 1 4 1 ; 1 4 1 ; 0 1 0 0 1 0 Yao Wang, 2016EL-GY 6123: Image and Video Processing36
Fourier Transform of Laplacian Operator 0 1 0 1 4 1 0 1 0 1 1 1 1 8 1 1 1 1 81261048624030203020100 0510152025252020100510150Laplacian operator are isotropic, can detect changes in all directions Yao Wang, 2016EL-GY 6123: Image and Video Processing37
Laplacian of Gaussian (LoG) To suppress noise, smooth the signal using a Gaussianfilter first– F(x,y)* G(x,y) Then apply Laplacian filter– F(x,y)*G(x,y)*L(x,y) F(x,y)* (L(x,y)*G(x,y)) Equivalent filter: LoG– H(x,y) L(x,y)*G(x,y) Yao Wang, 2016EL-GY 6123: Image and Video Processing38
Derivation of LoG Filter Continuous form2G ( x, y ) e2 G ( x, y ) x y22σ 22 G 2x 2 G 2 y 22x y 2σσ42e x2 y22σ 2Take samples to create filter mask– Size of mask nxn, n 5σ, odd– Ex: σ 1, n 5. Yao Wang, 2016EL-GY 6123: Image and Video Processing39
LoG Filter Yao Wang, 2016EL-GY 6123: Image and Video Processing40
Laplacian vs. LoG in Freq. Domain 0 1 0 1 4 1 0 1 0 Yao Wang, 2016H 00-1000-1-2-10EL-GY 6123: Image and Video Processing-1 0-2 -116 -2-2 -1-1 000-10041
Laplacian filteredLOG filteredNote that each strong edge in the original image corresponds to a thin stripe with highintensity in one side and low intensity in the other side. Yao Wang, 2016EL-GY 6123: Image and Video Processing42
How to detect zero crossing? For each pixel that has low filtered value, check a 3x3neighbor, to see whether its two neighbors in oppositedirection have opposite sign and their differenceexceeds a threshold (Marr-Hildreth edge detectionmethod) Yao Wang, 2016EL-GY 6123: Image and Video Processing43
Example Yao Wang, 2016EL-GY 6123: Image and Video Processing44
Pros and Cons Can locate edges more accuratelyCan detect edges in various directionBut more prone to noiseRemedy:– Smoothing before applying Laplacian Yao Wang, 2016EL-GY 6123: Image and Video Processing45
Summary of Edge Detection Method First order gradient based:– Using edge detectors in two orthogonal directions For each direction: low-pass along edge, band-pass acrossedge– Using edge detectors in multiple ( 2) directions– Use threshold or detect local maximum across theedge direction Second order gradient based– Laplacian is noise-prone, LoG is better– Detect zero crossing– Isotropic Yao Wang, 2016EL-GY 6123: Image and Video Processing46
More on Edge Detection Methods discussed so far generally cannot yieldconnected thin edge maps Need sophisticated post processing– Thinning– Connecting broken lines Noise can lead to many false edge points Even with many years of research, no perfect edgedetectors exist!– Canny edge detector: Gaussian smoothing along edges, highpass in each possible edge direction For more on edge detection, See Gonzalez Sec. 10.1,10.2 Yao Wang, 2016EL-GY 6123: Image and Video Processing47
Results using MATLAB “edge( )” function Yao Wang, 2016Sobel,T 0.14LOG, T 0.0051canny,T [0.0313,0.0781]Sobel,T 0.1LOG, T 0.01canny,T [0.1,0.15]EL-GY 6123: Image and Video Processing48
Non-Linear Filters Non-linear:– T(f1 f2) T(f1) T(f2)– T(af) a T(f) Median filter Rank-order filter (median is a special case) Morphological filter Yao Wang, 2016EL-GY 6123: Image and Video Processing49
Median Filter Problem with Averaging Filter– Blur edges and details in an image– Not effective for impulse noise (Salt-and-pepper) Median filter:– Taking the median value instead of the average or weightedaverage of pixels in the window Sort all the pixels in an increasing order, take the middle one– The window shape does not need to be a square– Special shapes can preserve line structures Yao Wang, 2016EL-GY 6123: Image and Video Processing50
Median Filter: 3x3 Square Window100100 100100100100200 205203100100195 200200100100200 205195100100100 100100100Windowshape100100 100100100100100 200100100100200 200200100100100 195100100100100 100100100Matlab command: medfilt2(A,[3 3]) Yao Wang, 2016EL-GY 6123: Image and Video Processing51
Median Filter: 3x3 Cross Window100100 100100100100200 205203100100195 200200100100200 205195100100100 100100100Windowshape100100 100100100100195 200200100100200 200200100100195 200195100100100 100100100Note that the edges of the centersquare are better reserved Yao Wang, 2016EL-GY 6123: Image and Video Processing52
Example Yao Wang, 2016EL-GY 6123: Image and Video Processing53
Rank order filters Rank order filters– Instead of taking the mean, rank all pixel values in the window,take the n-th order value.– E.g. max or min or median MATLAB function for median filtering– medfilt2( )– Use help to learn its various options! Yao Wang, 2016EL-GY 6123: Image and Video Processing54
Morphological Processing Morphological operations are originally developed for bilevelimages for shape and structural manipulations.Basic functions are dilation and erosion.Concatenation of dilation and erosion in different orders result inmore high level operations, including closing and opening.Morphological operations can be used for smoothing or edgedetection or extraction of other features.Belongs to the category of spatial domain filter.Gray-scale morphological filters are non-linear filters.Morphological filters are powerful tools and can accomplish variousdesired tasks: noise removal, edge detection, image smoothing, bilevel image shape smoothing. Yao Wang, 2016EL-GY 6123: Image and Video Processing55
Morphological Filtersfor Bilevel Images A binary image can be considered as a set byconsidering “black” pixels (with image value “1”) aselements in the set and “white” pixels (with value “0”) asoutside the set. Morphological filters are essentially set operations Yao Wang, 2016EL-GY 6123: Image and Video Processing56
Dilation Dilation of set F with a structuring element H isrepresented byF H {x : ( Hˆ ) x F Φ}where Φ represent the empty set. G F H is composed of all the points that when Ĥshifts its origin to these points, at least one point of Ĥ isincluded in F. If the origin of H takes value “1”, F F H Dilation enlarges a set! Yao Wang, 2016EL-GY 6123: Image and Video Processing57
Example of Dilation (1)H, 3x3, originat the centerH, 5x3, originat the centerDilation enlarges a set. Yao Wang, 2016EL-GY 6123: Image and Video Processing58
Example of Dilation (2)Note that the narrow ridge is closedFGH, 3x3, origin at the center Yao Wang, 2016EL-GY 6123: Image and Video Processing59
Erosion Erosion of set F with a structuring element H isrepresented by FΘH , and is defined as,FΘH {x : ( H ) x F} G FΘH is composed of points that when H istranslated to these points, every point of H is containedin F. If the origin of H takes value of “1”, FΘH F Erosion shrinks a set! Yao Wang, 2016EL-GY 6123: Image and Video Processing60
Example of Erosion (1)H, 3x3, originat the centerH, 5x3, originat the center Yao Wang, 2016Erosion shrinks a setEL-GY 6123: Image and Video Processing61
Example of Erosion (2)FGH, 3x3, origin at the center Yao Wang, 2016EL-GY 6123: Image and Video Processing62
Structuring element The shape, size, and orientation of the structuringelement depend on application. A symmetrical one will enlarge or shrink the original setin all directions. A vertical one, will only expand or shrink the original setin the vertical direction. Yao Wang, 2016EL-GY 6123: Image and Video Processing63
Closing and Opening ClosingF H ( F H )ΘH– Smooth the contour of an image– Fill small gaps and holes OpeningF H ( FΘH ) H– Smooth the contour of an image– Eliminate false touching, thin ridges and branches Yao Wang, 2016EL-GY 6123: Image and Video Processing64
Example of ClosingFF H( F H )ΘHH, 3x3, origin at the center Yao Wang, 2016EL-GY 6123: Image and Video Processing65
Example of OpeningFFΘH( FΘH ) HH, 3x3, origin at the center Yao Wang, 2016EL-GY 6123: Image and Video Processing66
Example of Opening and Closing Yao Wang, 2016EL-GY 6123: Image and Video Processing67
Morphological Filters for Grayscale Images The structure element h is a 2D grayscale image with afinite domain (Dh), similar to a filter The morphological operations can be defined for bothcontinuous and discrete images. Yao Wang, 2016EL-GY 6123: Image and Video Processing68
Dilation for Grayscale Image( f h)( x, y ) max{ f ( x s, y t ) h( s, t ); ( s, t ) Dh , ( x s, y t ) D f } Similar to linear convolution, with the max operationreplacing the sums of convolution and the additionreplacing the products of convolution. The di
In image processing, we rarely use very long filters We compute convolution directly, instead of using 2D FFT Filter design: For simplicity we often use separable filters, and design 1D filter based on the desired frequency response in 1D We do not focus on filter design in this class .
3 filtering and selective social filtering),6 Algeria (no evidence of filtering),7 and Jordan (selective political filtering and no evidence of social filtering).8 All testing was conducted in the period of January 2-15, 2010.
WebTitan Web Filtering and URL Filtering Categories: The 53 Categories available in Web Titan for Web Filtering and URL Filtering: 1.Alcohol: Web pages that promote, advocate or sell alcohol including beer, wine and hard liquor. 4.Business/Services: General business websites. 7.Community Sites: Newsgroup sites and posting including
SonicWALL Content Filtering feature. A Web browser is used to access the SonicWALL Management interface, and the commands and functions of Content Filtering. The following sections are in this chapter: Accessing the SonicWALL using a Web browser Enabling Content Filtering and Blocking Customizing Content Filtering
Modern edge-aware filtering: local Laplacian pyramids input texture decrease texture increase large texture increase. Tonemapping with edge-aware filtering. Tonemapping with edge-aware filtering local Laplacian pyramids bilateral filter. Non-local means. Redundancy in natural images.
Protects users, networks, and devices with the industry's best web security and parental controls solution. Goes beyond DNS filtering with protection and support at the domain, page-level, and full-path URL. Quick Heal Web Filtering is built to handle infrastructure failures and provide high-quality service. Quick Heal Web Filtering
Keywords: Image filtering, vertically weighted regression, nonlinear filters. 1. Introduction Image filtering and reconstruction algorithms have played the most fundamental role in image processing and ana-lysis. The problem of image filtering and reconstruction is to obtain a better quality image θˆfrom a noisy image y {y
innovator in the sphere of online security and web content filtering. Being IWF Member, SafeDNS includes in its web filtering systems and blocks URLs of indecent images of children and abuse domains from Child Abuse Images and content list (CAIC) compiled by IWF. www.safedns.com Starting from 2015, the efficiency of the SafeDNS web filtering
content-based, which utilize user personal and social data. 3.4 Collaborative filtering The Collaborative filtering method for recommender systems is a method that is solely based on the past interactions that have been recorded between users and items, in order to produce new recommendations. Collaborative Filtering tends to find what similar
