ImProc Digital Image Processing Lecture Notes PDF

ImProc. Digital Image Processing https://moodle.eurecom.fr/course/view.php?id=415 [email protected] [email protected] (2024)  ImProc Digital Image Processing https://moodle.eurecom.fr/course/view.php?i...

ImProc. Digital Image Processing https://moodle.eurecom.fr/course/view.php?id=415 [email protected] [email protected] (2024)  ImProc Digital Image Processing https://moodle.eurecom.fr/course/view.php?id=306 Lecture 0 (draft) 25 September 2024 From Signal Processing to Image Processing [email protected] (2024) Digital Image Processing (DIP)? Image Processing Compression Analysis Still Images (JPEG) and Moving Picture Interpretation (MPEG) Telecom Medical Remote Multimedia Imaging Sensing Virtual …/... Imaging [email protected] (2024)  Digital Image Processing? Signal Processing Computer Science …/… Mathematics Image Processing Information Theory Optic Electronics Human Vision [email protected] (2024) Human Vision vs. Machine [email protected] (2024)  Human Vision vs. Machine Tichener circles [email protected] (2024) [email protected] (2024)  jkjkj [email protected] (2024)  Baberpole illusion stripes are (apparently!) moving in the direction of its vertical axis rather than around it ambiguous information about its "real" direction of movement In the absence of additional information the visual system prefers the slowest possible motion: i.e., motion orthogonal to the moving line. aperture direction of A vertically movement is elongated aperture usually orthogonal makes vertical to the orientation of motion dominant the stripe [email protected] (2024) Phi phenomenon illusion of movement that arises when stationary objects—light bulbs, for example—are placed side by side and illuminated rapidly one after another. [email protected] (2024) The moving red bar is actually a 150ms flash of a red bar on the left, a gap of 120ms with no bars shown then a 150ms flash of red bar on the right. [email protected] (2024) The phi phenomenon disappears if the gap between the flashes is over about 500ms [email protected] (2024) Phi Color subjects consistently report that the dot changes color halfway through its course [email protected] (2024) Beta movement an optical illusion whereby viewing a rapidly changing series of static images creates the illusion of a smoothly flowing scene https://thebrain.mcgill.ca/flash/a/a_02/a_02_s/a_02_s_vis/a_02_s_vis.html [email protected] (2024) http://mesosyn.com/mental8-14.html In beta movement, you see two stimuli, a and b, in succession, but you perceive the movement of a single object, a , into position b. (TV) Beta movement Phi phenomenon In phi movement, you see the two stimuli a and b in succession, but what you perceive is the motion of something shadowy passing over a and b. (High way) [email protected] (2024)  Image Community Image Community Pictures/Applications Topics Techniques Television Compression Wavelets video Segmentation Mathematical Morphology Medical Restoration 3D ultrasound.../...../.. Remote Sensing multispectrum.../.. [email protected] (2024)  Different types of images Ultrasound Images Aerial Images Synthetic Images Multimedia Images [email protected] (2024)  ImProc: Digital Image Processing Basic Processing Tools Basic Software/libraries (50% lecture) (50% labs.). Filtering. Matlab/Image. Histogram. Python. Edge Detection and Image. OpenCV Segmentation. Motion estimation (optical flow). Hough Transform. Mathematical Morphology. Colors. 3D [email protected] (2024)  OUTLINE From 2-D Signal to Digital Image Sampling - Quantization Histogram Filtering Edge detection (high-pass filtering) Noise reduction (low-pass filtering) linear/non linear filtering (i.e. median filtering) – Frequency Domain (Fourier Transform) – Spatial Domain [email protected] (2024)  Sampling & Quantization  f (0,0) f (0,1).... f (0, N − 1)   f (1,0) f (1,1) :    i = f ( x, y ) =  : :     :   f ( N − 1,0) f (n − 1, N − 1) 2-D Signal Sampling Matrix f(N,N) of pixels i=f(x,y) Quantization pixel: picture element Image sampling = digitization of (x,y) coordinates grey-level quantization = digitization of pixel amplitude [email protected] (2024) Sampling (&Resampling) 1-D 2-D 2-D + t [email protected] (2024)  Moiré effects -aliasing ↓8 ↑8 Video [email protected] (2024) ↓2 ↑2 Low-Res. High-Res. [email protected] (2024)  Image Interpolation and Resampling* nearest-neighbor Synthetic image linear * P. Thévenaz, T. Blu and M. Unser (EPFL) [email protected] (2024)  Image Interpolation and Resampling after 24 x rotation 15° (Paint Shop Pro 6) (x,y) → (x’,y’) is a geometric transformation We are given pixel values at (x,y) and want to interpolate the unknown values at (x’,y’) Usually (x’,y’) are not integers and therefore we can use interpolation to guess their values [email protected] (2024)  Sub/Over - Sampling bilinear interpolation Sub-pixel precision f(n) n f(x) x 1D Zero-order (Replication) f(x) x 1D First-order Interpolation (Linear) [email protected] (2024)  Linear Interpolation Formula f(n) f(n+a)=(1-a)f(n)+af(n+1), 0 spectral overlap 1. Low pass filtering -> aliasing 2. sampling [email protected] (2024)  Scalar Quantization di: decision level (input level) ri: reconstruction level (output level) di - 1 di di +1 r i r i+1 if di  f ( x, y )  di +1 then f q ( x, y ) = ri [email protected] (2024)  Histogram Probability density associated with the grey-level k p(k) = n(k) / n Image Histogram Modifications Equalization Stretch Thresholding …/... [email protected] (2024) Histogram Equalization Enhanced image equiprobable : k , p(k ) = 1/ K + contrast [email protected] (2024) Histogram Equalization Algo. N pixels; K gray levels (0..K-1). Histogram: H(0)…H(K-1) Cumulative Histogram: CH(0)…CH(K-1) k  INT(CH(k) * ((K-1) / N)) [email protected] (2024)  Histogram Equalization (Khoros routine) 4 0 5 7 6 5 1 2 1 0 7 7 6 5 3 4  HISTOGRAM 2 0 7 7 6 7 0 0 14   12 10 0 4 1 0 3 2 1 6 #pixels 8 7 0 2 2 3 0 3 6 6   4 7 3 1 6 7 5 0 0 2 0 1 0 1 5 5 7 2 1 0 1 2 3 4 grey level values 5 6 7   2 7 3 5 6 6 4 4 Imagette of size 8x8 (8 grey levels) [email protected] (2024)  Histogram Equalization (Khoros routine) 4 0 5 7 6 5 1 2 1 0 7 7 6 5 3 4 Cumulative HISTOGRAM  2 0 70 0 7 7 6 7 0 60   50 0 4 1 0 3 2 1 6 # pixels 40 7 0 2 2 3 0 3 6 30   20 7 3 1 6 7 5 0 0 10 1 1 0 1 2 3 4 5 6 7 8 0 1 5 5 7 2   grey level values 2 7 3 5 6 6 4 4 Imagette of size 8x8 (8 grey levels) [email protected] (2024)  Histogram Equalization 0 1 2 3 4 5 6 7   4 1 4 7 5 4 2 2 12 8 7 6 5 7 8 11  2 12 20 27 33 38 45 53 64   1 7 7 5 4 3 4  1 2 2 3 4 4 5 7    2 1 7 7 5 7 1 1   1 4 2 1 3 2 2 5 Histogram - after equalization 7 5 16 1 2 2 3 1 3 14   12 7 3 2 5 7 4 1 1 # pixels 10 2 2 8 1 2 4 4 7 2 6   4 2 4 2 7 3 4 5 5 4 0 0 1 2 3 4 5 6 7 grey level values [email protected] (2024)  Histogram Thresholding T = 128 (average grey-level) if f(x,y) > T then g(x,y) = 1 (black) else g(x,y) = 0 (white) quantization (2 levels) Matlab-Image [email protected] (2024) Fourier Transform (FT) Foreword [email protected] (2024)  Fourier Transform (FT) Foreword (Cont.) Any function that periodically repeats itself can be expressed as the sum of sines and/or cosines of different frequencies each multiplied by a different coefficient; It does not matter how complicated the function is… At right, The function at the bottom is the sum of the four functions above it A function, expressed in Fourier transform can be reconstructed (recovered) completely via an inverse process, with no loss of information. [email protected] (2024)  Fourier Transform (FT) Foreword (Cont.) Analogie with glass prism? Glass prism: separates light into various color components, each depending on its wavelength (or frequency) content Fourier transform = “mathematical prism”: separates a function into various components, each depending on its frequency content [email protected] (2024)  Fourier Transform (FT) 1-D continuous FT function f(x) real real and imaginary components + F (u ) = R (u ) + jI (u ) F ( f ( x)) = F (u ) =  f ( x) exp(−2jux)dx Fourier spectrum − ( F (u ) = R 2 (u ) + I 2 (u ) ) 1/ 2 exp( − j 2ux ) = cos 2ux − j sin 2ux Inverse 1-D FT + F −1 ( F (u )) = f ( x) =  F (u ) exp( 2jux)du − [email protected] (2024) Example (1-D FT) + A F (u ) = sin(uX ) e − juX F (u ) =  f ( x) exp( − j 2ux)dx u − sin(uX ) X = AX =  A exp( − j 2ux)dx (uX ) 0 = j 2u e  − A − j 2ux X 0 =  j 2u e − A − j 2uX −1  = A j 2u   e juX − e − juX e − juX A = sin(uX )e − juX u [email protected] (2024) Example (1-D FT) Cont. [email protected] (2024)  Fourier Transform (FT) 2D continuous Forward/Inverse FT + + F (u, v) =   f ( x; y) exp− 2j (ux + vy)dxdy F ( F (u, v)) = f ( x, y ) =   F (u; v) exp2j (ux + vy )dudv −1 − − Discrete 2-D FT 1 M −1N −1   ux vy  M −1N −1   ux vy  F (u, v) =   f ( x, y ) exp − 2j  +   M N  f ( x, y ) =   F (u, v) exp 2j M +  N  MN x=0 y =0  u = 0 y =0  for u = 0,1,2,...,M − 1 and v = 0,1,2,..., N − 1 for x = 0,1,2,...,M − 1 and y = 0,1,2,..., N − 1 Discrete 2-D FT (NxN) 1 M −1N −1 1 M −1N −1 F (u, v) =   f ( x, y ) exp− 2j (ux + vy ) / N  f ( x, y ) =   F (u, v) exp2j (ux + vy ) / N  N x = 0 y =0 N u =0 y =0 for u, v = 0,1,2,..., N − 1 for x, y = 0,1,2,..., N − 1 [email protected] (2024)  Fourier Transform (FT) Magnitude & Phase Magnitude (spectrum) of the FT: Phase angle (phase spectrum) The MAGNITUDE tells "how much" of a certain frequency component is present and the PHASE tells "where" the frequency component is in the image. The FT images we look at are just the MAGNITUDE images. We generally do not display PHASE images. However, if we want to re-transform the Fourier image into the correct spatial domain after some processing in the frequency domain, we must make sure to preserve both magnitude and phase of the Fourier image. [email protected] (2024) 2-D FT example sin(uX ) sin(vY ) F (u, v) = AXY (uX ) (vY ) [email protected] (2024)  FT properties - DC Value 1 N −1 N −1 N −1 N −1 f ( x, y) = 2  f ( x, y) F (0,0) =  f ( x, y) 1 N x =0 y =0 N x=0 y =0 1 f ( x, y ) = F (0,0) N -Separability - Linearity - …/... [email protected] (2024) Separability: from 2-D to 2 x 1-D 1 M −1N −1 F (u, v) =   f ( x, y) exp− 2j(ux + vy ) / N  N x = 0 y =0 for u, v = 0,1,2,..., N − 1 N −1 1  ux  N −1  vy  F (u, v) = N  exp − j 2 N   f ( x, y) exp − j 2 N  x =0 y for u, v = 0,1,2,..., N − 1 N −1  ux  1 N −1  vy   1 F (u, v) =  F ( x, v) exp − j 2 N  F ( x, v ) = N  f ( x , y ) exp   − j 2  N  N x =0 N y =0 [email protected] (2024)  DISPLAY A picture of the planet Saturn Display of |F(u,v)| Display of log(1+|F(u,v)|) D(u, v) = log(1 + F (u, v) F (u, v) = 0 → D(u, v) = 0 D(u, v)  0 [email protected] (2024)  Rotation spatial vs. frequency domains [email protected] (2024)  FILTERED IMAGE Filtering via FFT IMAGE Forward FFT Filtering Inverse FFT cutoff frequency Lowpass Highpass Bandpass Bandstop Frequency responses of circularly symmetric ideal filters [email protected] (2024)  Low-pass filtering via FFT The FT is symmetrical about the origin so the 1st and 3rd quadrants are the same and the 2nd and 4th quadrants are the same [email protected] (2024)  Frequencies ? Low – uniform areas High – edges – noise [email protected] (2024)  Image Filtering frequency vs. spatial approaches Via FFT −1 f ( x, y) ⎯⎯→ FT F (u, v)  H (u, v) ⎯⎯⎯→ g ( x, y) FT Direct (using convolution) g ( x , y ) = f ( x , y )  h ( x, y ) f ( x)  g ( x)  F (u )G (u ) f ( x) g ( x)  F (u )  G (u ) [email protected] (2024)  Convolution operation Image of size N.N: f(x,y) Template of size (k+1).(k+1): h(x,y) k k p =+ q =+ 2 2 g ( x, y ) = k k f ( x − p, y − q) h( p, q) p =− q =− 2 2 sizeof the template values of coefficients [email protected] (2024)  Direct Low pass filtering by averaging 1 1 1 1 1 4 4 1 1 1 1 1 1   9  averaging 2x2 4 4 1 1 1 averaging 3x3 k −1 k −1 Image smoothing + noise reduction   h ( p, q ) p =0 q =0 =1 - edge smoothing [email protected] (2024)  Spatial Masks  w1 w2 w3    ( x − 1, y − 1) ( x − 1, y ) ( x − 1, y + 1)    w4 w5 w6     ( x, y − 1) ( x, y ) ( x, y + 1)     w w w   7 8 9     ( x + 1, y − 1) ( x + 1, y ) ( x + 1, y + 1)  T  f (x, y ) = w1 f ( x − 1, y − 1) + w2 f ( x − 1, y) Correlation: similarity between two signals + w3 f ( x − 1, y + 1) + w4 f ( x, y − 1) Convolution: effect of one signal on the other signal Correlation is same as convolution, + w5 f ( x, y) + w6 f ( x, y + 1) + w7 f ( x + 1, y − 1) except the signal is not reversed, before the multiplication process. + w8 f ( x + 1, y) + w9 f ( x + 1, y + 1) w1,...,w9: mask coefficients 8-neighbors of (x,y) [email protected] (2024)  Spatial Masks: Exemple low-pass filtering (averaging 3x3) 14 110 1115 1117 111 6 1151 11 12 x x x x x x x x 11 110 1117 1117 111 6 1151 131 14 x...... x     3 4 6 12 1110 1117 1117 111 6 1171 110 10  x 2...... x     10 114 111 10 3 2 1 6 x...... x 7 0 2 2 3 0 3 6 x...... x     7 3 1 6 7 5 0 0 x...... x 1 0 1 5 5 7 2 1 x...... x     2 7 3 5 6 6 4 4  x x x x x x x x  Imagette of size 8x8 (8 grey levels) Imagette of size 8x8 (8 grey levels) after low-pass filtering [email protected] (2024)  Low pass filtering by averaging 3x3 Edge blurring 5x5 7x7 [email protected] (2024)  Gaussian Filtering Gaussian kernels 3x3, 5x5, 7x7 Sigma = 0.8 Note the external factor, which ensures that the total values all add up to 1. This avoids adding any intensity to the image, solely average the pixels without otherwise changing their intensity.  Median Filtering Algorithm 1. Classify S =  f ( xj , yj ), ( xj , yj ) W  2. f ' ( xi, yi ) = med ( S ) Non linear, med (a.I1 + b.I 2 )  a.med ( I1 ) + b.med ( I 2 ) Useful in preserving edges while reducing noise (image smoothing) Used to o remove salt and pepper noise [email protected] (2024)  Median Filtering: Exemple median filtering (3x3) 4 0 5 7 6 5 1 2 x x x x x x x x 1 0 7 7 6 5 3 4 x...... x    2 7 2 0 7 7 6 7 0 0 x...... x     0 4 1 0 3 2 1 6 x...... x 7 0 2 2 3 0 3 6 x...... x     7 3 1 6 7 5 0 0 x...... x 1 0 1 5 5 7 2 1 x...... x     2 7 3 5 6 6 4 4  x x x x x x x x  Imagette of size 8x8 (8 grey levels) 0 0 0 5 1 2 7 57 7 7 7 4 [email protected] (2024) Edges : Gradient & Laplacian f ( x, y )  f    f ( x, y ) =  fx     y    2  f   f  2 f ( x, y ) =   +    x   y   2 f ( x, y )  2 f ( x, y )  f ( x, y ) = 2 + x 2 y 2 Image Sharpening [email protected] (2024)  Gradient Pattern Gradient 0 0 0  0 1 0 Gx  1 0 − 1 G y 0 0 0     0 0 0 0 − 1 0 1 0 − 1  1 0 − 1 if f ( x, y )  Threshold at ( x0 , y0 ) 1 0 − 1  2 0 − 2 then ( x0 , y0 ) is an edge point     else ( x0 , y0 ) is not an edge point 1 0 − 1  1 0 − 1 Sobe Prewitt l [email protected] (2024)  Spatial Masks: Exemple high-pass filtering (3x3) x x x x x x x x x...... x   x...... x   x...... x Gx  x...... x 4 0 5 7 6 5 1 2   x x x x x x x x 1 x...... x  0 7 7 6 5 3 4 x...... x x ...... x  2 0 7 7 6 7 0 0   x...... x    x x x x x x x x    0 4 1 0 3 2 1 6 x...... x 7 0 2 2 3 0 3 6 x x x x x x x x x...... x   x.   7 3 1 6 7 5 0 0 ..... x  x...... x 1 0 1 5 5 7 2 1 x...... x x...... x       2 7 3 5 6 6 4 4 x...... x  x x x x x x x x  Gy  x...... x   x...... x x...... x    x x x x x x x x  Imagette of size 8x8 (8 grey levels) [email protected] (2024)  Gradient Pattern  10 10 10 10 10   10 10 10 10 10    0 0 0 0 0     10 10 10 10 10  − 10 − 10 − 10 − 10 − 10   10 − 10 10 10 6 2  − 10 − 10 − 10 − 10    8 4 0 −4 −8    10 10 10 10 0  0°  −2 −6 − 10 − 10 − 10  10 10 10 0 − 10  − 10 − 10 − 10 − 10 − 10   10 10 0 − 10 − 10    22.5° 10 0 − 10 − 10 − 10   0 − 10 − 10 − 10 − 10  45° [email protected] (2024)  Laplacian Pattern Laplacian  0 +1 0  + 1 - 4 + 1    0 + 1 0  Edges: zero-crossing points  2f (x,y )  f(x + 1,y) + f(x − 1,y) + f(x,y + 1) + f(x,y − 1) − 4f(x,y) [email protected] (2024) References [email protected] (2024) References [email protected] (2024)